Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/Hexagon/HexagonOptAddrMode.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- HexagonOptAddrMode.cpp ---------------------------------------------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
// This implements a Hexagon-specific pass to optimize addressing mode for
9
// load/store instructions.
10
//===----------------------------------------------------------------------===//
11
12
#include "HexagonInstrInfo.h"
13
#include "HexagonSubtarget.h"
14
#include "MCTargetDesc/HexagonBaseInfo.h"
15
#include "RDFGraph.h"
16
#include "RDFLiveness.h"
17
#include "RDFRegisters.h"
18
#include "llvm/ADT/DenseMap.h"
19
#include "llvm/ADT/DenseSet.h"
20
#include "llvm/ADT/StringRef.h"
21
#include "llvm/CodeGen/MachineBasicBlock.h"
22
#include "llvm/CodeGen/MachineDominanceFrontier.h"
23
#include "llvm/CodeGen/MachineDominators.h"
24
#include "llvm/CodeGen/MachineFunction.h"
25
#include "llvm/CodeGen/MachineFunctionPass.h"
26
#include "llvm/CodeGen/MachineInstr.h"
27
#include "llvm/CodeGen/MachineInstrBuilder.h"
28
#include "llvm/CodeGen/MachineOperand.h"
29
#include "llvm/CodeGen/MachineRegisterInfo.h"
30
#include "llvm/CodeGen/TargetSubtargetInfo.h"
31
#include "llvm/MC/MCInstrDesc.h"
32
#include "llvm/Pass.h"
33
#include "llvm/Support/CommandLine.h"
34
#include "llvm/Support/Debug.h"
35
#include "llvm/Support/ErrorHandling.h"
36
#include "llvm/Support/raw_ostream.h"
37
#include <cassert>
38
#include <cstdint>
39
40
#define DEBUG_TYPE "opt-addr-mode"
41
42
using namespace llvm;
43
using namespace rdf;
44
45
static cl::opt<int> CodeGrowthLimit("hexagon-amode-growth-limit",
46
  cl::Hidden, cl::init(0), cl::desc("Code growth limit for address mode "
47
  "optimization"));
48
49
namespace llvm {
50
51
  FunctionPass *createHexagonOptAddrMode();
52
  void initializeHexagonOptAddrModePass(PassRegistry&);
53
54
} // end namespace llvm
55
56
namespace {
57
58
class HexagonOptAddrMode : public MachineFunctionPass {
59
public:
60
  static char ID;
61
62
862
  HexagonOptAddrMode() : MachineFunctionPass(ID) {}
63
64
4.21k
  StringRef getPassName() const override {
65
4.21k
    return "Optimize addressing mode of load/store";
66
4.21k
  }
67
68
855
  void getAnalysisUsage(AnalysisUsage &AU) const override {
69
855
    MachineFunctionPass::getAnalysisUsage(AU);
70
855
    AU.addRequired<MachineDominatorTree>();
71
855
    AU.addRequired<MachineDominanceFrontier>();
72
855
    AU.setPreservesAll();
73
855
  }
74
75
  bool runOnMachineFunction(MachineFunction &MF) override;
76
77
private:
78
  using MISetType = DenseSet<MachineInstr *>;
79
  using InstrEvalMap = DenseMap<MachineInstr *, bool>;
80
81
  MachineRegisterInfo *MRI = nullptr;
82
  const HexagonInstrInfo *HII = nullptr;
83
  const HexagonRegisterInfo *HRI = nullptr;
84
  MachineDominatorTree *MDT = nullptr;
85
  DataFlowGraph *DFG = nullptr;
86
  DataFlowGraph::DefStackMap DefM;
87
  Liveness *LV = nullptr;
88
  MISetType Deleted;
89
90
  bool processBlock(NodeAddr<BlockNode *> BA);
91
  bool xformUseMI(MachineInstr *TfrMI, MachineInstr *UseMI,
92
                  NodeAddr<UseNode *> UseN, unsigned UseMOnum);
93
  bool processAddUses(NodeAddr<StmtNode *> AddSN, MachineInstr *AddMI,
94
                      const NodeList &UNodeList);
95
  bool updateAddUses(MachineInstr *AddMI, MachineInstr *UseMI);
96
  bool analyzeUses(unsigned DefR, const NodeList &UNodeList,
97
                   InstrEvalMap &InstrEvalResult, short &SizeInc);
98
  bool hasRepForm(MachineInstr &MI, unsigned TfrDefR);
99
  bool canRemoveAddasl(NodeAddr<StmtNode *> AddAslSN, MachineInstr &MI,
100
                       const NodeList &UNodeList);
101
  bool isSafeToExtLR(NodeAddr<StmtNode *> SN, MachineInstr *MI,
102
                     unsigned LRExtReg, const NodeList &UNodeList);
103
  void getAllRealUses(NodeAddr<StmtNode *> SN, NodeList &UNodeList);
104
  bool allValidCandidates(NodeAddr<StmtNode *> SA, NodeList &UNodeList);
105
  short getBaseWithLongOffset(const MachineInstr &MI) const;
106
  bool changeStore(MachineInstr *OldMI, MachineOperand ImmOp,
107
                   unsigned ImmOpNum);
108
  bool changeLoad(MachineInstr *OldMI, MachineOperand ImmOp, unsigned ImmOpNum);
109
  bool changeAddAsl(NodeAddr<UseNode *> AddAslUN, MachineInstr *AddAslMI,
110
                    const MachineOperand &ImmOp, unsigned ImmOpNum);
111
  bool isValidOffset(MachineInstr *MI, int Offset);
112
};
113
114
} // end anonymous namespace
115
116
char HexagonOptAddrMode::ID = 0;
117
118
101k
INITIALIZE_PASS_BEGIN(HexagonOptAddrMode, "amode-opt",
119
101k
                      "Optimize addressing mode", false, false)
120
101k
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
121
101k
INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
122
101k
INITIALIZE_PASS_END(HexagonOptAddrMode, "amode-opt", "Optimize addressing mode",
123
                    false, false)
124
125
1.55k
bool HexagonOptAddrMode::hasRepForm(MachineInstr &MI, unsigned TfrDefR) {
126
1.55k
  const MCInstrDesc &MID = MI.getDesc();
127
1.55k
128
1.55k
  if ((!MID.mayStore() && 
!MID.mayLoad()427
) || HII->isPredicated(MI))
129
2
    return false;
130
1.55k
131
1.55k
  if (MID.mayStore()) {
132
1.12k
    MachineOperand StOp = MI.getOperand(MI.getNumOperands() - 1);
133
1.12k
    if (StOp.isReg() && 
StOp.getReg() == TfrDefR1.04k
)
134
73
      return false;
135
1.48k
  }
136
1.48k
137
1.48k
  if (HII->getAddrMode(MI) == HexagonII::BaseRegOffset)
138
26
    // Tranform to Absolute plus register offset.
139
26
    return (HII->changeAddrMode_rr_ur(MI) >= 0);
140
1.45k
  else if (HII->getAddrMode(MI) == HexagonII::BaseImmOffset)
141
1.37k
    // Tranform to absolute addressing mode.
142
1.37k
    return (HII->changeAddrMode_io_abs(MI) >= 0);
143
86
144
86
  return false;
145
86
}
146
147
// Check if addasl instruction can be removed. This is possible only
148
// if it's feeding to only load/store instructions with base + register
149
// offset as these instruction can be tranformed to use 'absolute plus
150
// shifted register offset'.
151
// ex:
152
// Rs = ##foo
153
// Rx = addasl(Rs, Rt, #2)
154
// Rd = memw(Rx + #28)
155
// Above three instructions can be replaced with Rd = memw(Rt<<#2 + ##foo+28)
156
157
bool HexagonOptAddrMode::canRemoveAddasl(NodeAddr<StmtNode *> AddAslSN,
158
                                         MachineInstr &MI,
159
12
                                         const NodeList &UNodeList) {
160
12
  // check offset size in addasl. if 'offset > 3' return false
161
12
  const MachineOperand &OffsetOp = MI.getOperand(3);
162
12
  if (!OffsetOp.isImm() || OffsetOp.getImm() > 3)
163
0
    return false;
164
12
165
12
  unsigned OffsetReg = MI.getOperand(2).getReg();
166
12
  RegisterRef OffsetRR;
167
12
  NodeId OffsetRegRD = 0;
168
24
  for (NodeAddr<UseNode *> UA : AddAslSN.Addr->members_if(DFG->IsUse, *DFG)) {
169
24
    RegisterRef RR = UA.Addr->getRegRef(*DFG);
170
24
    if (OffsetReg == RR.Reg) {
171
12
      OffsetRR = RR;
172
12
      OffsetRegRD = UA.Addr->getReachingDef();
173
12
    }
174
24
  }
175
12
176
15
  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; 
++I3
) {
177
14
    NodeAddr<UseNode *> UA = *I;
178
14
    NodeAddr<InstrNode *> IA = UA.Addr->getOwner(*DFG);
179
14
    if (UA.Addr->getFlags() & NodeAttrs::PhiRef)
180
0
      return false;
181
14
    NodeAddr<RefNode*> AA = LV->getNearestAliasedRef(OffsetRR, IA);
182
14
    if ((DFG->IsDef(AA) && 
AA.Id != OffsetRegRD8
) ||
183
14
         
AA.Addr->getReachingDef() != OffsetRegRD6
)
184
8
      return false;
185
6
186
6
    MachineInstr &UseMI = *NodeAddr<StmtNode *>(IA).Addr->getCode();
187
6
    NodeAddr<DefNode *> OffsetRegDN = DFG->addr<DefNode *>(OffsetRegRD);
188
6
    // Reaching Def to an offset register can't be a phi.
189
6
    if ((OffsetRegDN.Addr->getFlags() & NodeAttrs::PhiRef) &&
190
6
        
MI.getParent() != UseMI.getParent()2
)
191
1
    return false;
192
5
193
5
    const MCInstrDesc &UseMID = UseMI.getDesc();
194
5
    if ((!UseMID.mayLoad() && 
!UseMID.mayStore()3
) ||
195
5
        
HII->getAddrMode(UseMI) != HexagonII::BaseImmOffset3
||
196
5
        
getBaseWithLongOffset(UseMI) < 03
)
197
2
      return false;
198
3
199
3
    // Addasl output can't be a store value.
200
3
    if (UseMID.mayStore() && 
UseMI.getOperand(2).isReg()1
&&
201
3
        
UseMI.getOperand(2).getReg() == MI.getOperand(0).getReg()1
)
202
0
      return false;
203
3
204
3
    for (auto &Mo : UseMI.operands())
205
9
      if (Mo.isFI())
206
0
        return false;
207
3
  }
208
12
  
return true1
;
209
12
}
210
211
bool HexagonOptAddrMode::allValidCandidates(NodeAddr<StmtNode *> SA,
212
1.66k
                                            NodeList &UNodeList) {
213
4.79k
  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; 
++I3.12k
) {
214
3.53k
    NodeAddr<UseNode *> UN = *I;
215
3.53k
    RegisterRef UR = UN.Addr->getRegRef(*DFG);
216
3.53k
    NodeSet Visited, Defs;
217
3.53k
    const auto &P = LV->getAllReachingDefsRec(UR, UN, Visited, Defs);
218
3.53k
    if (!P.second) {
219
0
      LLVM_DEBUG({
220
0
        dbgs() << "*** Unable to collect all reaching defs for use ***\n"
221
0
               << PrintNode<UseNode*>(UN, *DFG) << '\n'
222
0
               << "The program's complexity may exceed the limits.\n";
223
0
      });
224
0
      return false;
225
0
    }
226
3.53k
    const auto &ReachingDefs = P.first;
227
3.53k
    if (ReachingDefs.size() > 1) {
228
411
      LLVM_DEBUG({
229
411
        dbgs() << "*** Multiple Reaching Defs found!!! ***\n";
230
411
        for (auto DI : ReachingDefs) {
231
411
          NodeAddr<UseNode *> DA = DFG->addr<UseNode *>(DI);
232
411
          NodeAddr<StmtNode *> TempIA = DA.Addr->getOwner(*DFG);
233
411
          dbgs() << "\t\t[Reaching Def]: "
234
411
                 << Print<NodeAddr<InstrNode *>>(TempIA, *DFG) << "\n";
235
411
        }
236
411
      });
237
411
      return false;
238
411
    }
239
3.53k
  }
240
1.66k
  
return true1.25k
;
241
1.66k
}
242
243
void HexagonOptAddrMode::getAllRealUses(NodeAddr<StmtNode *> SA,
244
1.66k
                                        NodeList &UNodeList) {
245
1.66k
  for (NodeAddr<DefNode *> DA : SA.Addr->members_if(DFG->IsDef, *DFG)) {
246
1.66k
    LLVM_DEBUG(dbgs() << "\t\t[DefNode]: "
247
1.66k
                      << Print<NodeAddr<DefNode *>>(DA, *DFG) << "\n");
248
1.66k
    RegisterRef DR = DFG->getPRI().normalize(DA.Addr->getRegRef(*DFG));
249
1.66k
250
1.66k
    auto UseSet = LV->getAllReachedUses(DR, DA);
251
1.66k
252
4.25k
    for (auto UI : UseSet) {
253
4.25k
      NodeAddr<UseNode *> UA = DFG->addr<UseNode *>(UI);
254
4.25k
      LLVM_DEBUG({
255
4.25k
        NodeAddr<StmtNode *> TempIA = UA.Addr->getOwner(*DFG);
256
4.25k
        dbgs() << "\t\t\t[Reached Use]: "
257
4.25k
               << Print<NodeAddr<InstrNode *>>(TempIA, *DFG) << "\n";
258
4.25k
      });
259
4.25k
260
4.25k
      if (UA.Addr->getFlags() & NodeAttrs::PhiRef) {
261
998
        NodeAddr<PhiNode *> PA = UA.Addr->getOwner(*DFG);
262
998
        NodeId id = PA.Id;
263
998
        const Liveness::RefMap &phiUse = LV->getRealUses(id);
264
998
        LLVM_DEBUG(dbgs() << "\t\t\t\tphi real Uses"
265
998
                          << Print<Liveness::RefMap>(phiUse, *DFG) << "\n");
266
998
        if (!phiUse.empty()) {
267
1.85k
          for (auto I : phiUse) {
268
1.85k
            if (!DFG->getPRI().alias(RegisterRef(I.first), DR))
269
1.36k
              continue;
270
491
            auto phiUseSet = I.second;
271
1.31k
            for (auto phiUI : phiUseSet) {
272
1.31k
              NodeAddr<UseNode *> phiUA = DFG->addr<UseNode *>(phiUI.first);
273
1.31k
              UNodeList.push_back(phiUA);
274
1.31k
            }
275
491
          }
276
512
        }
277
998
      } else
278
3.25k
        UNodeList.push_back(UA);
279
4.25k
    }
280
1.66k
  }
281
1.66k
}
282
283
bool HexagonOptAddrMode::isSafeToExtLR(NodeAddr<StmtNode *> SN,
284
                                       MachineInstr *MI, unsigned LRExtReg,
285
8
                                       const NodeList &UNodeList) {
286
8
  RegisterRef LRExtRR;
287
8
  NodeId LRExtRegRD = 0;
288
8
  // Iterate through all the UseNodes in SN and find the reaching def
289
8
  // for the LRExtReg.
290
8
  for (NodeAddr<UseNode *> UA : SN.Addr->members_if(DFG->IsUse, *DFG)) {
291
8
    RegisterRef RR = UA.Addr->getRegRef(*DFG);
292
8
    if (LRExtReg == RR.Reg) {
293
8
      LRExtRR = RR;
294
8
      LRExtRegRD = UA.Addr->getReachingDef();
295
8
    }
296
8
  }
297
8
298
10
  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; 
++I2
) {
299
8
    NodeAddr<UseNode *> UA = *I;
300
8
    NodeAddr<InstrNode *> IA = UA.Addr->getOwner(*DFG);
301
8
    // The reaching def of LRExtRR at load/store node should be same as the
302
8
    // one reaching at the SN.
303
8
    if (UA.Addr->getFlags() & NodeAttrs::PhiRef)
304
0
      return false;
305
8
    NodeAddr<RefNode*> AA = LV->getNearestAliasedRef(LRExtRR, IA);
306
8
    if ((DFG->IsDef(AA) && 
AA.Id != LRExtRegRD6
) ||
307
8
        
AA.Addr->getReachingDef() != LRExtRegRD2
) {
308
6
      LLVM_DEBUG(
309
6
          dbgs() << "isSafeToExtLR: Returning false; another reaching def\n");
310
6
      return false;
311
6
    }
312
2
313
2
    MachineInstr *UseMI = NodeAddr<StmtNode *>(IA).Addr->getCode();
314
2
    NodeAddr<DefNode *> LRExtRegDN = DFG->addr<DefNode *>(LRExtRegRD);
315
2
    // Reaching Def to LRExtReg can't be a phi.
316
2
    if ((LRExtRegDN.Addr->getFlags() & NodeAttrs::PhiRef) &&
317
2
        
MI->getParent() != UseMI->getParent()0
)
318
0
    return false;
319
2
  }
320
8
  
return true2
;
321
8
}
322
323
17
bool HexagonOptAddrMode::isValidOffset(MachineInstr *MI, int Offset) {
324
17
  unsigned AlignMask = 0;
325
17
  switch (HII->getMemAccessSize(*MI)) {
326
17
  case HexagonII::MemAccessSize::DoubleWordAccess:
327
6
    AlignMask = 0x7;
328
6
    break;
329
17
  case HexagonII::MemAccessSize::WordAccess:
330
0
    AlignMask = 0x3;
331
0
    break;
332
17
  case HexagonII::MemAccessSize::HalfWordAccess:
333
4
    AlignMask = 0x1;
334
4
    break;
335
17
  case HexagonII::MemAccessSize::ByteAccess:
336
4
    AlignMask = 0x0;
337
4
    break;
338
17
  default:
339
3
    return false;
340
14
  }
341
14
342
14
  if ((AlignMask & Offset) != 0)
343
4
    return false;
344
10
  return HII->isValidOffset(MI->getOpcode(), Offset, HRI, false);
345
10
}
346
347
bool HexagonOptAddrMode::processAddUses(NodeAddr<StmtNode *> AddSN,
348
                                        MachineInstr *AddMI,
349
558
                                        const NodeList &UNodeList) {
350
558
351
558
  unsigned AddDefR = AddMI->getOperand(0).getReg();
352
560
  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; 
++I2
) {
353
558
    NodeAddr<UseNode *> UN = *I;
354
558
    NodeAddr<StmtNode *> SN = UN.Addr->getOwner(*DFG);
355
558
    MachineInstr *MI = SN.Addr->getCode();
356
558
    const MCInstrDesc &MID = MI->getDesc();
357
558
    if ((!MID.mayLoad() && 
!MID.mayStore()465
) ||
358
558
        
HII->getAddrMode(*MI) != HexagonII::BaseImmOffset184
||
359
558
        
HII->isHVXVec(*MI)108
)
360
525
      return false;
361
33
362
33
    MachineOperand BaseOp = MID.mayLoad() ? 
MI->getOperand(1)11
363
33
                                          : 
MI->getOperand(0)22
;
364
33
365
33
    if (!BaseOp.isReg() || 
BaseOp.getReg() != AddDefR31
)
366
16
      return false;
367
17
368
17
    MachineOperand OffsetOp = MID.mayLoad() ? 
MI->getOperand(2)9
369
17
                                            : 
MI->getOperand(1)8
;
370
17
    if (!OffsetOp.isImm())
371
0
      return false;
372
17
373
17
    int64_t newOffset = OffsetOp.getImm() + AddMI->getOperand(2).getImm();
374
17
    if (!isValidOffset(MI, newOffset))
375
9
      return false;
376
8
377
8
    // Since we'll be extending the live range of Rt in the following example,
378
8
    // make sure that is safe. another definition of Rt doesn't exist between 'add'
379
8
    // and load/store instruction.
380
8
    //
381
8
    // Ex: Rx= add(Rt,#10)
382
8
    //     memw(Rx+#0) = Rs
383
8
    // will be replaced with =>  memw(Rt+#10) = Rs
384
8
    unsigned BaseReg = AddMI->getOperand(1).getReg();
385
8
    if (!isSafeToExtLR(AddSN, AddMI, BaseReg, UNodeList))
386
6
      return false;
387
8
  }
388
558
389
558
  // Update all the uses of 'add' with the appropriate base and offset
390
558
  // values.
391
558
  bool Changed = false;
392
4
  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; 
++I2
) {
393
2
    NodeAddr<UseNode *> UseN = *I;
394
2
    assert(!(UseN.Addr->getFlags() & NodeAttrs::PhiRef) &&
395
2
           "Found a PhiRef node as a real reached use!!");
396
2
397
2
    NodeAddr<StmtNode *> OwnerN = UseN.Addr->getOwner(*DFG);
398
2
    MachineInstr *UseMI = OwnerN.Addr->getCode();
399
2
    LLVM_DEBUG(dbgs() << "\t\t[MI <BB#" << UseMI->getParent()->getNumber()
400
2
                      << ">]: " << *UseMI << "\n");
401
2
    Changed |= updateAddUses(AddMI, UseMI);
402
2
  }
403
2
404
2
  if (Changed)
405
2
    Deleted.insert(AddMI);
406
2
407
2
  return Changed;
408
558
}
409
410
bool HexagonOptAddrMode::updateAddUses(MachineInstr *AddMI,
411
2
                                        MachineInstr *UseMI) {
412
2
  const MachineOperand ImmOp = AddMI->getOperand(2);
413
2
  const MachineOperand AddRegOp = AddMI->getOperand(1);
414
2
  unsigned newReg = AddRegOp.getReg();
415
2
  const MCInstrDesc &MID = UseMI->getDesc();
416
2
417
2
  MachineOperand &BaseOp = MID.mayLoad() ? 
UseMI->getOperand(1)0
418
2
                                         : UseMI->getOperand(0);
419
2
  MachineOperand &OffsetOp = MID.mayLoad() ? 
UseMI->getOperand(2)0
420
2
                                           : UseMI->getOperand(1);
421
2
  BaseOp.setReg(newReg);
422
2
  BaseOp.setIsUndef(AddRegOp.isUndef());
423
2
  BaseOp.setImplicit(AddRegOp.isImplicit());
424
2
  OffsetOp.setImm(ImmOp.getImm() + OffsetOp.getImm());
425
2
  MRI->clearKillFlags(newReg);
426
2
427
2
  return true;
428
2
}
429
430
bool HexagonOptAddrMode::analyzeUses(unsigned tfrDefR,
431
                                     const NodeList &UNodeList,
432
                                     InstrEvalMap &InstrEvalResult,
433
681
                                     short &SizeInc) {
434
681
  bool KeepTfr = false;
435
681
  bool HasRepInstr = false;
436
681
  InstrEvalResult.clear();
437
681
438
2.45k
  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; 
++I1.77k
) {
439
1.77k
    bool CanBeReplaced = false;
440
1.77k
    NodeAddr<UseNode *> UN = *I;
441
1.77k
    NodeAddr<StmtNode *> SN = UN.Addr->getOwner(*DFG);
442
1.77k
    MachineInstr &MI = *SN.Addr->getCode();
443
1.77k
    const MCInstrDesc &MID = MI.getDesc();
444
1.77k
    if ((MID.mayLoad() || 
MID.mayStore()1.12k
)) {
445
1.55k
      if (!hasRepForm(MI, tfrDefR)) {
446
1.16k
        KeepTfr = true;
447
1.16k
        continue;
448
1.16k
      }
449
393
      SizeInc++;
450
393
      CanBeReplaced = true;
451
393
    } else 
if (216
MI.getOpcode() == Hexagon::S2_addasl_rrri216
) {
452
12
      NodeList AddaslUseList;
453
12
454
12
      LLVM_DEBUG(dbgs() << "\nGetting ReachedUses for === " << MI << "\n");
455
12
      getAllRealUses(SN, AddaslUseList);
456
12
      // Process phi nodes.
457
12
      if (allValidCandidates(SN, AddaslUseList) &&
458
12
          canRemoveAddasl(SN, MI, AddaslUseList)) {
459
1
        SizeInc += AddaslUseList.size();
460
1
        SizeInc -= 1; // Reduce size by 1 as addasl itself can be removed.
461
1
        CanBeReplaced = true;
462
1
      } else
463
11
        SizeInc++;
464
12
    } else
465
204
      // Currently, only load/store and addasl are handled.
466
204
      // Some other instructions to consider -
467
204
      // A2_add -> A2_addi
468
204
      // M4_mpyrr_addr -> M4_mpyrr_addi
469
204
      KeepTfr = true;
470
1.77k
471
1.77k
    InstrEvalResult[&MI] = CanBeReplaced;
472
609
    HasRepInstr |= CanBeReplaced;
473
609
  }
474
681
475
681
  // Reduce total size by 2 if original tfr can be deleted.
476
681
  if (!KeepTfr)
477
31
    SizeInc -= 2;
478
681
479
681
  return HasRepInstr;
480
681
}
481
482
bool HexagonOptAddrMode::changeLoad(MachineInstr *OldMI, MachineOperand ImmOp,
483
4
                                    unsigned ImmOpNum) {
484
4
  bool Changed = false;
485
4
  MachineBasicBlock *BB = OldMI->getParent();
486
4
  auto UsePos = MachineBasicBlock::iterator(OldMI);
487
4
  MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
488
4
  ++InsertPt;
489
4
  unsigned OpStart;
490
4
  unsigned OpEnd = OldMI->getNumOperands();
491
4
  MachineInstrBuilder MIB;
492
4
493
4
  if (ImmOpNum == 1) {
494
4
    if (HII->getAddrMode(*OldMI) == HexagonII::BaseRegOffset) {
495
0
      short NewOpCode = HII->changeAddrMode_rr_ur(*OldMI);
496
0
      assert(NewOpCode >= 0 && "Invalid New opcode\n");
497
0
      MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
498
0
      MIB.add(OldMI->getOperand(0));
499
0
      MIB.add(OldMI->getOperand(2));
500
0
      MIB.add(OldMI->getOperand(3));
501
0
      MIB.add(ImmOp);
502
0
      OpStart = 4;
503
0
      Changed = true;
504
4
    } else if (HII->getAddrMode(*OldMI) == HexagonII::BaseImmOffset &&
505
4
               OldMI->getOperand(2).isImm()) {
506
4
      short NewOpCode = HII->changeAddrMode_io_abs(*OldMI);
507
4
      assert(NewOpCode >= 0 && "Invalid New opcode\n");
508
4
      MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode))
509
4
                .add(OldMI->getOperand(0));
510
4
      const GlobalValue *GV = ImmOp.getGlobal();
511
4
      int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(2).getImm();
512
4
513
4
      MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags());
514
4
      OpStart = 3;
515
4
      Changed = true;
516
4
    } else
517
0
      Changed = false;
518
4
519
4
    LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
520
4
    LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
521
4
  } else 
if (0
ImmOpNum == 20
) {
522
0
    if (OldMI->getOperand(3).isImm() && OldMI->getOperand(3).getImm() == 0) {
523
0
      short NewOpCode = HII->changeAddrMode_rr_io(*OldMI);
524
0
      assert(NewOpCode >= 0 && "Invalid New opcode\n");
525
0
      MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
526
0
      MIB.add(OldMI->getOperand(0));
527
0
      MIB.add(OldMI->getOperand(1));
528
0
      MIB.add(ImmOp);
529
0
      OpStart = 4;
530
0
      Changed = true;
531
0
      LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
532
0
      LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
533
0
    }
534
0
  }
535
4
536
4
  if (Changed)
537
4
    for (unsigned i = OpStart; i < OpEnd; 
++i0
)
538
0
      MIB.add(OldMI->getOperand(i));
539
4
540
4
  return Changed;
541
4
}
542
543
bool HexagonOptAddrMode::changeStore(MachineInstr *OldMI, MachineOperand ImmOp,
544
3
                                     unsigned ImmOpNum) {
545
3
  bool Changed = false;
546
3
  unsigned OpStart;
547
3
  unsigned OpEnd = OldMI->getNumOperands();
548
3
  MachineBasicBlock *BB = OldMI->getParent();
549
3
  auto UsePos = MachineBasicBlock::iterator(OldMI);
550
3
  MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
551
3
  ++InsertPt;
552
3
  MachineInstrBuilder MIB;
553
3
  if (ImmOpNum == 0) {
554
2
    if (HII->getAddrMode(*OldMI) == HexagonII::BaseRegOffset) {
555
2
      short NewOpCode = HII->changeAddrMode_rr_ur(*OldMI);
556
2
      assert(NewOpCode >= 0 && "Invalid New opcode\n");
557
2
      MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
558
2
      MIB.add(OldMI->getOperand(1));
559
2
      MIB.add(OldMI->getOperand(2));
560
2
      MIB.add(ImmOp);
561
2
      MIB.add(OldMI->getOperand(3));
562
2
      OpStart = 4;
563
2
    } else 
if (0
HII->getAddrMode(*OldMI) == HexagonII::BaseImmOffset0
) {
564
0
      short NewOpCode = HII->changeAddrMode_io_abs(*OldMI);
565
0
      assert(NewOpCode >= 0 && "Invalid New opcode\n");
566
0
      MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
567
0
      const GlobalValue *GV = ImmOp.getGlobal();
568
0
      int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(1).getImm();
569
0
      MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags());
570
0
      MIB.add(OldMI->getOperand(2));
571
0
      OpStart = 3;
572
0
    }
573
2
    Changed = true;
574
2
    LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
575
2
    LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
576
2
  } else 
if (1
ImmOpNum == 11
&&
OldMI->getOperand(2).getImm() == 01
) {
577
1
    short NewOpCode = HII->changeAddrMode_rr_io(*OldMI);
578
1
    assert(NewOpCode >= 0 && "Invalid New opcode\n");
579
1
    MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
580
1
    MIB.add(OldMI->getOperand(0));
581
1
    MIB.add(ImmOp);
582
1
    OpStart = 3;
583
1
    Changed = true;
584
1
    LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
585
1
    LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
586
1
  }
587
3
  if (Changed)
588
4
    
for (unsigned i = OpStart; 3
i < OpEnd;
++i1
)
589
1
      MIB.add(OldMI->getOperand(i));
590
3
591
3
  return Changed;
592
3
}
593
594
4
short HexagonOptAddrMode::getBaseWithLongOffset(const MachineInstr &MI) const {
595
4
  if (HII->getAddrMode(MI) == HexagonII::BaseImmOffset) {
596
4
    short TempOpCode = HII->changeAddrMode_io_rr(MI);
597
4
    return HII->changeAddrMode_rr_ur(TempOpCode);
598
4
  }
599
0
  return HII->changeAddrMode_rr_ur(MI);
600
0
}
601
602
bool HexagonOptAddrMode::changeAddAsl(NodeAddr<UseNode *> AddAslUN,
603
                                      MachineInstr *AddAslMI,
604
                                      const MachineOperand &ImmOp,
605
1
                                      unsigned ImmOpNum) {
606
1
  NodeAddr<StmtNode *> SA = AddAslUN.Addr->getOwner(*DFG);
607
1
608
1
  LLVM_DEBUG(dbgs() << "Processing addasl :" << *AddAslMI << "\n");
609
1
610
1
  NodeList UNodeList;
611
1
  getAllRealUses(SA, UNodeList);
612
1
613
2
  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; 
++I1
) {
614
1
    NodeAddr<UseNode *> UseUN = *I;
615
1
    assert(!(UseUN.Addr->getFlags() & NodeAttrs::PhiRef) &&
616
1
           "Can't transform this 'AddAsl' instruction!");
617
1
618
1
    NodeAddr<StmtNode *> UseIA = UseUN.Addr->getOwner(*DFG);
619
1
    LLVM_DEBUG(dbgs() << "[InstrNode]: "
620
1
                      << Print<NodeAddr<InstrNode *>>(UseIA, *DFG) << "\n");
621
1
    MachineInstr *UseMI = UseIA.Addr->getCode();
622
1
    LLVM_DEBUG(dbgs() << "[MI <" << printMBBReference(*UseMI->getParent())
623
1
                      << ">]: " << *UseMI << "\n");
624
1
    const MCInstrDesc &UseMID = UseMI->getDesc();
625
1
    assert(HII->getAddrMode(*UseMI) == HexagonII::BaseImmOffset);
626
1
627
1
    auto UsePos = MachineBasicBlock::iterator(UseMI);
628
1
    MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
629
1
    short NewOpCode = getBaseWithLongOffset(*UseMI);
630
1
    assert(NewOpCode >= 0 && "Invalid New opcode\n");
631
1
632
1
    unsigned OpStart;
633
1
    unsigned OpEnd = UseMI->getNumOperands();
634
1
635
1
    MachineBasicBlock *BB = UseMI->getParent();
636
1
    MachineInstrBuilder MIB =
637
1
        BuildMI(*BB, InsertPt, UseMI->getDebugLoc(), HII->get(NewOpCode));
638
1
    // change mem(Rs + # ) -> mem(Rt << # + ##)
639
1
    if (UseMID.mayLoad()) {
640
0
      MIB.add(UseMI->getOperand(0));
641
0
      MIB.add(AddAslMI->getOperand(2));
642
0
      MIB.add(AddAslMI->getOperand(3));
643
0
      const GlobalValue *GV = ImmOp.getGlobal();
644
0
      MIB.addGlobalAddress(GV, UseMI->getOperand(2).getImm()+ImmOp.getOffset(),
645
0
                           ImmOp.getTargetFlags());
646
0
      OpStart = 3;
647
1
    } else if (UseMID.mayStore()) {
648
1
      MIB.add(AddAslMI->getOperand(2));
649
1
      MIB.add(AddAslMI->getOperand(3));
650
1
      const GlobalValue *GV = ImmOp.getGlobal();
651
1
      MIB.addGlobalAddress(GV, UseMI->getOperand(1).getImm()+ImmOp.getOffset(),
652
1
                           ImmOp.getTargetFlags());
653
1
      MIB.add(UseMI->getOperand(2));
654
1
      OpStart = 3;
655
1
    } else
656
1
      
llvm_unreachable0
("Unhandled instruction");
657
1
658
1
    for (unsigned i = OpStart; i < OpEnd; 
++i0
)
659
0
      MIB.add(UseMI->getOperand(i));
660
1
661
1
    Deleted.insert(UseMI);
662
1
  }
663
1
664
1
  return true;
665
1
}
666
667
bool HexagonOptAddrMode::xformUseMI(MachineInstr *TfrMI, MachineInstr *UseMI,
668
                                    NodeAddr<UseNode *> UseN,
669
8
                                    unsigned UseMOnum) {
670
8
  const MachineOperand ImmOp = TfrMI->getOperand(1);
671
8
  const MCInstrDesc &MID = UseMI->getDesc();
672
8
  unsigned Changed = false;
673
8
  if (MID.mayLoad())
674
4
    Changed = changeLoad(UseMI, ImmOp, UseMOnum);
675
4
  else if (MID.mayStore())
676
3
    Changed = changeStore(UseMI, ImmOp, UseMOnum);
677
1
  else if (UseMI->getOpcode() == Hexagon::S2_addasl_rrri)
678
1
    Changed = changeAddAsl(UseN, UseMI, ImmOp, UseMOnum);
679
8
680
8
  if (Changed)
681
8
    Deleted.insert(UseMI);
682
8
683
8
  return Changed;
684
8
}
685
686
5.54k
bool HexagonOptAddrMode::processBlock(NodeAddr<BlockNode *> BA) {
687
5.54k
  bool Changed = false;
688
5.54k
689
41.2k
  for (auto IA : BA.Addr->members(*DFG)) {
690
41.2k
    if (!DFG->IsCode<NodeAttrs::Stmt>(IA))
691
11.8k
      continue;
692
29.4k
693
29.4k
    NodeAddr<StmtNode *> SA = IA;
694
29.4k
    MachineInstr *MI = SA.Addr->getCode();
695
29.4k
    if ((MI->getOpcode() != Hexagon::A2_tfrsi ||
696
29.4k
         
!MI->getOperand(1).isGlobal()2.88k
) &&
697
29.4k
        
(28.7k
MI->getOpcode() != Hexagon::A2_addi28.7k
||
698
28.7k
         
!MI->getOperand(2).isImm()954
||
HII->isConstExtended(*MI)943
))
699
27.8k
    continue;
700
1.65k
701
1.65k
    LLVM_DEBUG(dbgs() << "[Analyzing " << HII->getName(MI->getOpcode())
702
1.65k
                      << "]: " << *MI << "\n\t[InstrNode]: "
703
1.65k
                      << Print<NodeAddr<InstrNode *>>(IA, *DFG) << '\n');
704
1.65k
705
1.65k
    NodeList UNodeList;
706
1.65k
    getAllRealUses(SA, UNodeList);
707
1.65k
708
1.65k
    if (!allValidCandidates(SA, UNodeList))
709
411
      continue;
710
1.23k
711
1.23k
    // Analyze all uses of 'add'. If the output of 'add' is used as an address
712
1.23k
    // in the base+immediate addressing mode load/store instructions, see if
713
1.23k
    // they can be updated to use the immediate value as an offet. Thus,
714
1.23k
    // providing us the opportunity to eliminate 'add'.
715
1.23k
    // Ex: Rx= add(Rt,#12)
716
1.23k
    //     memw(Rx+#0) = Rs
717
1.23k
    // This can be replaced with memw(Rt+#12) = Rs
718
1.23k
    //
719
1.23k
    // This transformation is only performed if all uses can be updated and
720
1.23k
    // the offset isn't required to be constant extended.
721
1.23k
    if (MI->getOpcode() == Hexagon::A2_addi) {
722
558
      Changed |= processAddUses(SA, MI, UNodeList);
723
558
      continue;
724
558
    }
725
681
726
681
    short SizeInc = 0;
727
681
    unsigned DefR = MI->getOperand(0).getReg();
728
681
    InstrEvalMap InstrEvalResult;
729
681
730
681
    // Analyze all uses and calculate increase in size. Perform the optimization
731
681
    // only if there is no increase in size.
732
681
    if (!analyzeUses(DefR, UNodeList, InstrEvalResult, SizeInc))
733
650
      continue;
734
31
    if (SizeInc > CodeGrowthLimit)
735
24
      continue;
736
7
737
7
    bool KeepTfr = false;
738
7
739
7
    LLVM_DEBUG(dbgs() << "\t[Total reached uses] : " << UNodeList.size()
740
7
                      << "\n");
741
7
    LLVM_DEBUG(dbgs() << "\t[Processing Reached Uses] ===\n");
742
15
    for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; 
++I8
) {
743
8
      NodeAddr<UseNode *> UseN = *I;
744
8
      assert(!(UseN.Addr->getFlags() & NodeAttrs::PhiRef) &&
745
8
             "Found a PhiRef node as a real reached use!!");
746
8
747
8
      NodeAddr<StmtNode *> OwnerN = UseN.Addr->getOwner(*DFG);
748
8
      MachineInstr *UseMI = OwnerN.Addr->getCode();
749
8
      LLVM_DEBUG(dbgs() << "\t\t[MI <" << printMBBReference(*UseMI->getParent())
750
8
                        << ">]: " << *UseMI << "\n");
751
8
752
8
      int UseMOnum = -1;
753
8
      unsigned NumOperands = UseMI->getNumOperands();
754
28
      for (unsigned j = 0; j < NumOperands - 1; 
++j20
) {
755
20
        const MachineOperand &op = UseMI->getOperand(j);
756
20
        if (op.isReg() && 
op.isUse()17
&&
DefR == op.getReg()12
)
757
8
          UseMOnum = j;
758
20
      }
759
8
      // It is possible that the register will not be found in any operand.
760
8
      // This could happen, for example, when DefR = R4, but the used
761
8
      // register is D2.
762
8
763
8
      // Change UseMI if replacement is possible. If any replacement failed,
764
8
      // or wasn't attempted, make sure to keep the TFR.
765
8
      bool Xformed = false;
766
8
      if (UseMOnum >= 0 && InstrEvalResult[UseMI])
767
8
        Xformed = xformUseMI(MI, UseMI, UseN, UseMOnum);
768
8
      Changed |=  Xformed;
769
8
      KeepTfr |= !Xformed;
770
8
    }
771
7
    if (!KeepTfr)
772
7
      Deleted.insert(MI);
773
7
  }
774
5.54k
  return Changed;
775
5.54k
}
776
777
3.35k
bool HexagonOptAddrMode::runOnMachineFunction(MachineFunction &MF) {
778
3.35k
  if (skipFunction(MF.getFunction()))
779
10
    return false;
780
3.34k
781
3.34k
  bool Changed = false;
782
3.34k
  auto &HST = MF.getSubtarget<HexagonSubtarget>();
783
3.34k
  MRI = &MF.getRegInfo();
784
3.34k
  HII = HST.getInstrInfo();
785
3.34k
  HRI = HST.getRegisterInfo();
786
3.34k
  const auto &MDF = getAnalysis<MachineDominanceFrontier>();
787
3.34k
  MDT = &getAnalysis<MachineDominatorTree>();
788
3.34k
  const TargetOperandInfo TOI(*HII);
789
3.34k
790
3.34k
  DataFlowGraph G(MF, *HII, *HRI, *MDT, MDF, TOI);
791
3.34k
  // Need to keep dead phis because we can propagate uses of registers into
792
3.34k
  // nodes dominated by those would-be phis.
793
3.34k
  G.build(BuildOptions::KeepDeadPhis);
794
3.34k
  DFG = &G;
795
3.34k
796
3.34k
  Liveness L(*MRI, *DFG);
797
3.34k
  L.computePhiInfo();
798
3.34k
  LV = &L;
799
3.34k
800
3.34k
  Deleted.clear();
801
3.34k
  NodeAddr<FuncNode *> FA = DFG->getFunc();
802
3.34k
  LLVM_DEBUG(dbgs() << "==== [RefMap#]=====:\n "
803
3.34k
                    << Print<NodeAddr<FuncNode *>>(FA, *DFG) << "\n");
804
3.34k
805
3.34k
  for (NodeAddr<BlockNode *> BA : FA.Addr->members(*DFG))
806
5.54k
    Changed |= processBlock(BA);
807
3.34k
808
3.34k
  for (auto MI : Deleted)
809
18
    MI->eraseFromParent();
810
3.34k
811
3.34k
  if (Changed) {
812
9
    G.build();
813
9
    L.computeLiveIns();
814
9
    L.resetLiveIns();
815
9
    L.resetKills();
816
9
  }
817
3.34k
818
3.34k
  return Changed;
819
3.34k
}
820
821
//===----------------------------------------------------------------------===//
822
//                         Public Constructor Functions
823
//===----------------------------------------------------------------------===//
824
825
859
FunctionPass *llvm::createHexagonOptAddrMode() {
826
859
  return new HexagonOptAddrMode();
827
859
}