LLVM  9.0.0svn
HexagonOptAddrMode.cpp
Go to the documentation of this file.
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"
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"
31 #include "llvm/MC/MCInstrDesc.h"
32 #include "llvm/Pass.h"
34 #include "llvm/Support/Debug.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 
53 
54 } // end namespace llvm
55 
56 namespace {
57 
58 class HexagonOptAddrMode : public MachineFunctionPass {
59 public:
60  static char ID;
61 
62  HexagonOptAddrMode() : MachineFunctionPass(ID) {}
63 
64  StringRef getPassName() const override {
65  return "Optimize addressing mode of load/store";
66  }
67 
68  void getAnalysisUsage(AnalysisUsage &AU) const override {
72  AU.setPreservesAll();
73  }
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;
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 INITIALIZE_PASS_BEGIN(HexagonOptAddrMode, "amode-opt",
119  "Optimize addressing mode", false, false)
122 INITIALIZE_PASS_END(HexagonOptAddrMode, "amode-opt", "Optimize addressing mode",
123  false, false)
124 
125 bool HexagonOptAddrMode::hasRepForm(MachineInstr &MI, unsigned TfrDefR) {
126  const MCInstrDesc &MID = MI.getDesc();
127 
128  if ((!MID.mayStore() && !MID.mayLoad()) || HII->isPredicated(MI))
129  return false;
130 
131  if (MID.mayStore()) {
132  MachineOperand StOp = MI.getOperand(MI.getNumOperands() - 1);
133  if (StOp.isReg() && StOp.getReg() == TfrDefR)
134  return false;
135  }
136 
137  if (HII->getAddrMode(MI) == HexagonII::BaseRegOffset)
138  // Tranform to Absolute plus register offset.
139  return (HII->changeAddrMode_rr_ur(MI) >= 0);
140  else if (HII->getAddrMode(MI) == HexagonII::BaseImmOffset)
141  // Tranform to absolute addressing mode.
142  return (HII->changeAddrMode_io_abs(MI) >= 0);
143 
144  return false;
145 }
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  const NodeList &UNodeList) {
160  // check offset size in addasl. if 'offset > 3' return false
161  const MachineOperand &OffsetOp = MI.getOperand(3);
162  if (!OffsetOp.isImm() || OffsetOp.getImm() > 3)
163  return false;
164 
165  unsigned OffsetReg = MI.getOperand(2).getReg();
166  RegisterRef OffsetRR;
167  NodeId OffsetRegRD = 0;
168  for (NodeAddr<UseNode *> UA : AddAslSN.Addr->members_if(DFG->IsUse, *DFG)) {
169  RegisterRef RR = UA.Addr->getRegRef(*DFG);
170  if (OffsetReg == RR.Reg) {
171  OffsetRR = RR;
172  OffsetRegRD = UA.Addr->getReachingDef();
173  }
174  }
175 
176  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
177  NodeAddr<UseNode *> UA = *I;
178  NodeAddr<InstrNode *> IA = UA.Addr->getOwner(*DFG);
179  if (UA.Addr->getFlags() & NodeAttrs::PhiRef)
180  return false;
181  NodeAddr<RefNode*> AA = LV->getNearestAliasedRef(OffsetRR, IA);
182  if ((DFG->IsDef(AA) && AA.Id != OffsetRegRD) ||
183  AA.Addr->getReachingDef() != OffsetRegRD)
184  return false;
185 
186  MachineInstr &UseMI = *NodeAddr<StmtNode *>(IA).Addr->getCode();
187  NodeAddr<DefNode *> OffsetRegDN = DFG->addr<DefNode *>(OffsetRegRD);
188  // Reaching Def to an offset register can't be a phi.
189  if ((OffsetRegDN.Addr->getFlags() & NodeAttrs::PhiRef) &&
190  MI.getParent() != UseMI.getParent())
191  return false;
192 
193  const MCInstrDesc &UseMID = UseMI.getDesc();
194  if ((!UseMID.mayLoad() && !UseMID.mayStore()) ||
195  HII->getAddrMode(UseMI) != HexagonII::BaseImmOffset ||
196  getBaseWithLongOffset(UseMI) < 0)
197  return false;
198 
199  // Addasl output can't be a store value.
200  if (UseMID.mayStore() && UseMI.getOperand(2).isReg() &&
201  UseMI.getOperand(2).getReg() == MI.getOperand(0).getReg())
202  return false;
203 
204  for (auto &Mo : UseMI.operands())
205  if (Mo.isFI())
206  return false;
207  }
208  return true;
209 }
210 
211 bool HexagonOptAddrMode::allValidCandidates(NodeAddr<StmtNode *> SA,
212  NodeList &UNodeList) {
213  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
214  NodeAddr<UseNode *> UN = *I;
215  RegisterRef UR = UN.Addr->getRegRef(*DFG);
216  NodeSet Visited, Defs;
217  const auto &P = LV->getAllReachingDefsRec(UR, UN, Visited, Defs);
218  if (!P.second) {
219  LLVM_DEBUG({
220  dbgs() << "*** Unable to collect all reaching defs for use ***\n"
221  << PrintNode<UseNode*>(UN, *DFG) << '\n'
222  << "The program's complexity may exceed the limits.\n";
223  });
224  return false;
225  }
226  const auto &ReachingDefs = P.first;
227  if (ReachingDefs.size() > 1) {
228  LLVM_DEBUG({
229  dbgs() << "*** Multiple Reaching Defs found!!! ***\n";
230  for (auto DI : ReachingDefs) {
231  NodeAddr<UseNode *> DA = DFG->addr<UseNode *>(DI);
232  NodeAddr<StmtNode *> TempIA = DA.Addr->getOwner(*DFG);
233  dbgs() << "\t\t[Reaching Def]: "
234  << Print<NodeAddr<InstrNode *>>(TempIA, *DFG) << "\n";
235  }
236  });
237  return false;
238  }
239  }
240  return true;
241 }
242 
243 void HexagonOptAddrMode::getAllRealUses(NodeAddr<StmtNode *> SA,
244  NodeList &UNodeList) {
245  for (NodeAddr<DefNode *> DA : SA.Addr->members_if(DFG->IsDef, *DFG)) {
246  LLVM_DEBUG(dbgs() << "\t\t[DefNode]: "
247  << Print<NodeAddr<DefNode *>>(DA, *DFG) << "\n");
248  RegisterRef DR = DFG->getPRI().normalize(DA.Addr->getRegRef(*DFG));
249 
250  auto UseSet = LV->getAllReachedUses(DR, DA);
251 
252  for (auto UI : UseSet) {
253  NodeAddr<UseNode *> UA = DFG->addr<UseNode *>(UI);
254  LLVM_DEBUG({
255  NodeAddr<StmtNode *> TempIA = UA.Addr->getOwner(*DFG);
256  dbgs() << "\t\t\t[Reached Use]: "
257  << Print<NodeAddr<InstrNode *>>(TempIA, *DFG) << "\n";
258  });
259 
260  if (UA.Addr->getFlags() & NodeAttrs::PhiRef) {
261  NodeAddr<PhiNode *> PA = UA.Addr->getOwner(*DFG);
262  NodeId id = PA.Id;
263  const Liveness::RefMap &phiUse = LV->getRealUses(id);
264  LLVM_DEBUG(dbgs() << "\t\t\t\tphi real Uses"
265  << Print<Liveness::RefMap>(phiUse, *DFG) << "\n");
266  if (!phiUse.empty()) {
267  for (auto I : phiUse) {
268  if (!DFG->getPRI().alias(RegisterRef(I.first), DR))
269  continue;
270  auto phiUseSet = I.second;
271  for (auto phiUI : phiUseSet) {
272  NodeAddr<UseNode *> phiUA = DFG->addr<UseNode *>(phiUI.first);
273  UNodeList.push_back(phiUA);
274  }
275  }
276  }
277  } else
278  UNodeList.push_back(UA);
279  }
280  }
281 }
282 
283 bool HexagonOptAddrMode::isSafeToExtLR(NodeAddr<StmtNode *> SN,
284  MachineInstr *MI, unsigned LRExtReg,
285  const NodeList &UNodeList) {
286  RegisterRef LRExtRR;
287  NodeId LRExtRegRD = 0;
288  // Iterate through all the UseNodes in SN and find the reaching def
289  // for the LRExtReg.
290  for (NodeAddr<UseNode *> UA : SN.Addr->members_if(DFG->IsUse, *DFG)) {
291  RegisterRef RR = UA.Addr->getRegRef(*DFG);
292  if (LRExtReg == RR.Reg) {
293  LRExtRR = RR;
294  LRExtRegRD = UA.Addr->getReachingDef();
295  }
296  }
297 
298  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
299  NodeAddr<UseNode *> UA = *I;
300  NodeAddr<InstrNode *> IA = UA.Addr->getOwner(*DFG);
301  // The reaching def of LRExtRR at load/store node should be same as the
302  // one reaching at the SN.
303  if (UA.Addr->getFlags() & NodeAttrs::PhiRef)
304  return false;
305  NodeAddr<RefNode*> AA = LV->getNearestAliasedRef(LRExtRR, IA);
306  if ((DFG->IsDef(AA) && AA.Id != LRExtRegRD) ||
307  AA.Addr->getReachingDef() != LRExtRegRD) {
308  LLVM_DEBUG(
309  dbgs() << "isSafeToExtLR: Returning false; another reaching def\n");
310  return false;
311  }
312 
313  MachineInstr *UseMI = NodeAddr<StmtNode *>(IA).Addr->getCode();
314  NodeAddr<DefNode *> LRExtRegDN = DFG->addr<DefNode *>(LRExtRegRD);
315  // Reaching Def to LRExtReg can't be a phi.
316  if ((LRExtRegDN.Addr->getFlags() & NodeAttrs::PhiRef) &&
317  MI->getParent() != UseMI->getParent())
318  return false;
319  }
320  return true;
321 }
322 
323 bool HexagonOptAddrMode::isValidOffset(MachineInstr *MI, int Offset) {
324  unsigned AlignMask = 0;
325  switch (HII->getMemAccessSize(*MI)) {
327  AlignMask = 0x7;
328  break;
330  AlignMask = 0x3;
331  break;
333  AlignMask = 0x1;
334  break;
336  AlignMask = 0x0;
337  break;
338  default:
339  return false;
340  }
341 
342  if ((AlignMask & Offset) != 0)
343  return false;
344  return HII->isValidOffset(MI->getOpcode(), Offset, HRI, false);
345 }
346 
347 bool HexagonOptAddrMode::processAddUses(NodeAddr<StmtNode *> AddSN,
348  MachineInstr *AddMI,
349  const NodeList &UNodeList) {
350 
351  unsigned AddDefR = AddMI->getOperand(0).getReg();
352  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
353  NodeAddr<UseNode *> UN = *I;
354  NodeAddr<StmtNode *> SN = UN.Addr->getOwner(*DFG);
355  MachineInstr *MI = SN.Addr->getCode();
356  const MCInstrDesc &MID = MI->getDesc();
357  if ((!MID.mayLoad() && !MID.mayStore()) ||
358  HII->getAddrMode(*MI) != HexagonII::BaseImmOffset ||
359  HII->isHVXVec(*MI))
360  return false;
361 
362  MachineOperand BaseOp = MID.mayLoad() ? MI->getOperand(1)
363  : MI->getOperand(0);
364 
365  if (!BaseOp.isReg() || BaseOp.getReg() != AddDefR)
366  return false;
367 
368  MachineOperand OffsetOp = MID.mayLoad() ? MI->getOperand(2)
369  : MI->getOperand(1);
370  if (!OffsetOp.isImm())
371  return false;
372 
373  int64_t newOffset = OffsetOp.getImm() + AddMI->getOperand(2).getImm();
374  if (!isValidOffset(MI, newOffset))
375  return false;
376 
377  // Since we'll be extending the live range of Rt in the following example,
378  // make sure that is safe. another definition of Rt doesn't exist between 'add'
379  // and load/store instruction.
380  //
381  // Ex: Rx= add(Rt,#10)
382  // memw(Rx+#0) = Rs
383  // will be replaced with => memw(Rt+#10) = Rs
384  unsigned BaseReg = AddMI->getOperand(1).getReg();
385  if (!isSafeToExtLR(AddSN, AddMI, BaseReg, UNodeList))
386  return false;
387  }
388 
389  // Update all the uses of 'add' with the appropriate base and offset
390  // values.
391  bool Changed = false;
392  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
393  NodeAddr<UseNode *> UseN = *I;
394  assert(!(UseN.Addr->getFlags() & NodeAttrs::PhiRef) &&
395  "Found a PhiRef node as a real reached use!!");
396 
397  NodeAddr<StmtNode *> OwnerN = UseN.Addr->getOwner(*DFG);
398  MachineInstr *UseMI = OwnerN.Addr->getCode();
399  LLVM_DEBUG(dbgs() << "\t\t[MI <BB#" << UseMI->getParent()->getNumber()
400  << ">]: " << *UseMI << "\n");
401  Changed |= updateAddUses(AddMI, UseMI);
402  }
403 
404  if (Changed)
405  Deleted.insert(AddMI);
406 
407  return Changed;
408 }
409 
410 bool HexagonOptAddrMode::updateAddUses(MachineInstr *AddMI,
411  MachineInstr *UseMI) {
412  const MachineOperand ImmOp = AddMI->getOperand(2);
413  const MachineOperand AddRegOp = AddMI->getOperand(1);
414  unsigned newReg = AddRegOp.getReg();
415  const MCInstrDesc &MID = UseMI->getDesc();
416 
417  MachineOperand &BaseOp = MID.mayLoad() ? UseMI->getOperand(1)
418  : UseMI->getOperand(0);
419  MachineOperand &OffsetOp = MID.mayLoad() ? UseMI->getOperand(2)
420  : UseMI->getOperand(1);
421  BaseOp.setReg(newReg);
422  BaseOp.setIsUndef(AddRegOp.isUndef());
423  BaseOp.setImplicit(AddRegOp.isImplicit());
424  OffsetOp.setImm(ImmOp.getImm() + OffsetOp.getImm());
425  MRI->clearKillFlags(newReg);
426 
427  return true;
428 }
429 
430 bool HexagonOptAddrMode::analyzeUses(unsigned tfrDefR,
431  const NodeList &UNodeList,
432  InstrEvalMap &InstrEvalResult,
433  short &SizeInc) {
434  bool KeepTfr = false;
435  bool HasRepInstr = false;
436  InstrEvalResult.clear();
437 
438  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
439  bool CanBeReplaced = false;
440  NodeAddr<UseNode *> UN = *I;
441  NodeAddr<StmtNode *> SN = UN.Addr->getOwner(*DFG);
442  MachineInstr &MI = *SN.Addr->getCode();
443  const MCInstrDesc &MID = MI.getDesc();
444  if ((MID.mayLoad() || MID.mayStore())) {
445  if (!hasRepForm(MI, tfrDefR)) {
446  KeepTfr = true;
447  continue;
448  }
449  SizeInc++;
450  CanBeReplaced = true;
451  } else if (MI.getOpcode() == Hexagon::S2_addasl_rrri) {
452  NodeList AddaslUseList;
453 
454  LLVM_DEBUG(dbgs() << "\nGetting ReachedUses for === " << MI << "\n");
455  getAllRealUses(SN, AddaslUseList);
456  // Process phi nodes.
457  if (allValidCandidates(SN, AddaslUseList) &&
458  canRemoveAddasl(SN, MI, AddaslUseList)) {
459  SizeInc += AddaslUseList.size();
460  SizeInc -= 1; // Reduce size by 1 as addasl itself can be removed.
461  CanBeReplaced = true;
462  } else
463  SizeInc++;
464  } else
465  // Currently, only load/store and addasl are handled.
466  // Some other instructions to consider -
467  // A2_add -> A2_addi
468  // M4_mpyrr_addr -> M4_mpyrr_addi
469  KeepTfr = true;
470 
471  InstrEvalResult[&MI] = CanBeReplaced;
472  HasRepInstr |= CanBeReplaced;
473  }
474 
475  // Reduce total size by 2 if original tfr can be deleted.
476  if (!KeepTfr)
477  SizeInc -= 2;
478 
479  return HasRepInstr;
480 }
481 
482 bool HexagonOptAddrMode::changeLoad(MachineInstr *OldMI, MachineOperand ImmOp,
483  unsigned ImmOpNum) {
484  bool Changed = false;
485  MachineBasicBlock *BB = OldMI->getParent();
486  auto UsePos = MachineBasicBlock::iterator(OldMI);
487  MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
488  ++InsertPt;
489  unsigned OpStart;
490  unsigned OpEnd = OldMI->getNumOperands();
492 
493  if (ImmOpNum == 1) {
494  if (HII->getAddrMode(*OldMI) == HexagonII::BaseRegOffset) {
495  short NewOpCode = HII->changeAddrMode_rr_ur(*OldMI);
496  assert(NewOpCode >= 0 && "Invalid New opcode\n");
497  MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
498  MIB.add(OldMI->getOperand(0));
499  MIB.add(OldMI->getOperand(2));
500  MIB.add(OldMI->getOperand(3));
501  MIB.add(ImmOp);
502  OpStart = 4;
503  Changed = true;
504  } else if (HII->getAddrMode(*OldMI) == HexagonII::BaseImmOffset &&
505  OldMI->getOperand(2).isImm()) {
506  short NewOpCode = HII->changeAddrMode_io_abs(*OldMI);
507  assert(NewOpCode >= 0 && "Invalid New opcode\n");
508  MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode))
509  .add(OldMI->getOperand(0));
510  const GlobalValue *GV = ImmOp.getGlobal();
511  int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(2).getImm();
512 
513  MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags());
514  OpStart = 3;
515  Changed = true;
516  } else
517  Changed = false;
518 
519  LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
520  LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
521  } else if (ImmOpNum == 2) {
522  if (OldMI->getOperand(3).isImm() && OldMI->getOperand(3).getImm() == 0) {
523  short NewOpCode = HII->changeAddrMode_rr_io(*OldMI);
524  assert(NewOpCode >= 0 && "Invalid New opcode\n");
525  MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
526  MIB.add(OldMI->getOperand(0));
527  MIB.add(OldMI->getOperand(1));
528  MIB.add(ImmOp);
529  OpStart = 4;
530  Changed = true;
531  LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
532  LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
533  }
534  }
535 
536  if (Changed)
537  for (unsigned i = OpStart; i < OpEnd; ++i)
538  MIB.add(OldMI->getOperand(i));
539 
540  return Changed;
541 }
542 
543 bool HexagonOptAddrMode::changeStore(MachineInstr *OldMI, MachineOperand ImmOp,
544  unsigned ImmOpNum) {
545  bool Changed = false;
546  unsigned OpStart;
547  unsigned OpEnd = OldMI->getNumOperands();
548  MachineBasicBlock *BB = OldMI->getParent();
549  auto UsePos = MachineBasicBlock::iterator(OldMI);
550  MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
551  ++InsertPt;
553  if (ImmOpNum == 0) {
554  if (HII->getAddrMode(*OldMI) == HexagonII::BaseRegOffset) {
555  short NewOpCode = HII->changeAddrMode_rr_ur(*OldMI);
556  assert(NewOpCode >= 0 && "Invalid New opcode\n");
557  MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
558  MIB.add(OldMI->getOperand(1));
559  MIB.add(OldMI->getOperand(2));
560  MIB.add(ImmOp);
561  MIB.add(OldMI->getOperand(3));
562  OpStart = 4;
563  } else if (HII->getAddrMode(*OldMI) == HexagonII::BaseImmOffset) {
564  short NewOpCode = HII->changeAddrMode_io_abs(*OldMI);
565  assert(NewOpCode >= 0 && "Invalid New opcode\n");
566  MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
567  const GlobalValue *GV = ImmOp.getGlobal();
568  int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(1).getImm();
569  MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags());
570  MIB.add(OldMI->getOperand(2));
571  OpStart = 3;
572  }
573  Changed = true;
574  LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
575  LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
576  } else if (ImmOpNum == 1 && OldMI->getOperand(2).getImm() == 0) {
577  short NewOpCode = HII->changeAddrMode_rr_io(*OldMI);
578  assert(NewOpCode >= 0 && "Invalid New opcode\n");
579  MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
580  MIB.add(OldMI->getOperand(0));
581  MIB.add(ImmOp);
582  OpStart = 3;
583  Changed = true;
584  LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
585  LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
586  }
587  if (Changed)
588  for (unsigned i = OpStart; i < OpEnd; ++i)
589  MIB.add(OldMI->getOperand(i));
590 
591  return Changed;
592 }
593 
594 short HexagonOptAddrMode::getBaseWithLongOffset(const MachineInstr &MI) const {
595  if (HII->getAddrMode(MI) == HexagonII::BaseImmOffset) {
596  short TempOpCode = HII->changeAddrMode_io_rr(MI);
597  return HII->changeAddrMode_rr_ur(TempOpCode);
598  }
599  return HII->changeAddrMode_rr_ur(MI);
600 }
601 
602 bool HexagonOptAddrMode::changeAddAsl(NodeAddr<UseNode *> AddAslUN,
603  MachineInstr *AddAslMI,
604  const MachineOperand &ImmOp,
605  unsigned ImmOpNum) {
606  NodeAddr<StmtNode *> SA = AddAslUN.Addr->getOwner(*DFG);
607 
608  LLVM_DEBUG(dbgs() << "Processing addasl :" << *AddAslMI << "\n");
609 
610  NodeList UNodeList;
611  getAllRealUses(SA, UNodeList);
612 
613  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
614  NodeAddr<UseNode *> UseUN = *I;
615  assert(!(UseUN.Addr->getFlags() & NodeAttrs::PhiRef) &&
616  "Can't transform this 'AddAsl' instruction!");
617 
618  NodeAddr<StmtNode *> UseIA = UseUN.Addr->getOwner(*DFG);
619  LLVM_DEBUG(dbgs() << "[InstrNode]: "
620  << Print<NodeAddr<InstrNode *>>(UseIA, *DFG) << "\n");
621  MachineInstr *UseMI = UseIA.Addr->getCode();
622  LLVM_DEBUG(dbgs() << "[MI <" << printMBBReference(*UseMI->getParent())
623  << ">]: " << *UseMI << "\n");
624  const MCInstrDesc &UseMID = UseMI->getDesc();
625  assert(HII->getAddrMode(*UseMI) == HexagonII::BaseImmOffset);
626 
627  auto UsePos = MachineBasicBlock::iterator(UseMI);
628  MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
629  short NewOpCode = getBaseWithLongOffset(*UseMI);
630  assert(NewOpCode >= 0 && "Invalid New opcode\n");
631 
632  unsigned OpStart;
633  unsigned OpEnd = UseMI->getNumOperands();
634 
635  MachineBasicBlock *BB = UseMI->getParent();
636  MachineInstrBuilder MIB =
637  BuildMI(*BB, InsertPt, UseMI->getDebugLoc(), HII->get(NewOpCode));
638  // change mem(Rs + # ) -> mem(Rt << # + ##)
639  if (UseMID.mayLoad()) {
640  MIB.add(UseMI->getOperand(0));
641  MIB.add(AddAslMI->getOperand(2));
642  MIB.add(AddAslMI->getOperand(3));
643  const GlobalValue *GV = ImmOp.getGlobal();
644  MIB.addGlobalAddress(GV, UseMI->getOperand(2).getImm()+ImmOp.getOffset(),
645  ImmOp.getTargetFlags());
646  OpStart = 3;
647  } else if (UseMID.mayStore()) {
648  MIB.add(AddAslMI->getOperand(2));
649  MIB.add(AddAslMI->getOperand(3));
650  const GlobalValue *GV = ImmOp.getGlobal();
651  MIB.addGlobalAddress(GV, UseMI->getOperand(1).getImm()+ImmOp.getOffset(),
652  ImmOp.getTargetFlags());
653  MIB.add(UseMI->getOperand(2));
654  OpStart = 3;
655  } else
656  llvm_unreachable("Unhandled instruction");
657 
658  for (unsigned i = OpStart; i < OpEnd; ++i)
659  MIB.add(UseMI->getOperand(i));
660 
661  Deleted.insert(UseMI);
662  }
663 
664  return true;
665 }
666 
667 bool HexagonOptAddrMode::xformUseMI(MachineInstr *TfrMI, MachineInstr *UseMI,
668  NodeAddr<UseNode *> UseN,
669  unsigned UseMOnum) {
670  const MachineOperand ImmOp = TfrMI->getOperand(1);
671  const MCInstrDesc &MID = UseMI->getDesc();
672  unsigned Changed = false;
673  if (MID.mayLoad())
674  Changed = changeLoad(UseMI, ImmOp, UseMOnum);
675  else if (MID.mayStore())
676  Changed = changeStore(UseMI, ImmOp, UseMOnum);
677  else if (UseMI->getOpcode() == Hexagon::S2_addasl_rrri)
678  Changed = changeAddAsl(UseN, UseMI, ImmOp, UseMOnum);
679 
680  if (Changed)
681  Deleted.insert(UseMI);
682 
683  return Changed;
684 }
685 
686 bool HexagonOptAddrMode::processBlock(NodeAddr<BlockNode *> BA) {
687  bool Changed = false;
688 
689  for (auto IA : BA.Addr->members(*DFG)) {
690  if (!DFG->IsCode<NodeAttrs::Stmt>(IA))
691  continue;
692 
693  NodeAddr<StmtNode *> SA = IA;
694  MachineInstr *MI = SA.Addr->getCode();
695  if ((MI->getOpcode() != Hexagon::A2_tfrsi ||
696  !MI->getOperand(1).isGlobal()) &&
697  (MI->getOpcode() != Hexagon::A2_addi ||
698  !MI->getOperand(2).isImm() || HII->isConstExtended(*MI)))
699  continue;
700 
701  LLVM_DEBUG(dbgs() << "[Analyzing " << HII->getName(MI->getOpcode())
702  << "]: " << *MI << "\n\t[InstrNode]: "
703  << Print<NodeAddr<InstrNode *>>(IA, *DFG) << '\n');
704 
705  NodeList UNodeList;
706  getAllRealUses(SA, UNodeList);
707 
708  if (!allValidCandidates(SA, UNodeList))
709  continue;
710 
711  // Analyze all uses of 'add'. If the output of 'add' is used as an address
712  // in the base+immediate addressing mode load/store instructions, see if
713  // they can be updated to use the immediate value as an offet. Thus,
714  // providing us the opportunity to eliminate 'add'.
715  // Ex: Rx= add(Rt,#12)
716  // memw(Rx+#0) = Rs
717  // This can be replaced with memw(Rt+#12) = Rs
718  //
719  // This transformation is only performed if all uses can be updated and
720  // the offset isn't required to be constant extended.
721  if (MI->getOpcode() == Hexagon::A2_addi) {
722  Changed |= processAddUses(SA, MI, UNodeList);
723  continue;
724  }
725 
726  short SizeInc = 0;
727  unsigned DefR = MI->getOperand(0).getReg();
728  InstrEvalMap InstrEvalResult;
729 
730  // Analyze all uses and calculate increase in size. Perform the optimization
731  // only if there is no increase in size.
732  if (!analyzeUses(DefR, UNodeList, InstrEvalResult, SizeInc))
733  continue;
734  if (SizeInc > CodeGrowthLimit)
735  continue;
736 
737  bool KeepTfr = false;
738 
739  LLVM_DEBUG(dbgs() << "\t[Total reached uses] : " << UNodeList.size()
740  << "\n");
741  LLVM_DEBUG(dbgs() << "\t[Processing Reached Uses] ===\n");
742  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
743  NodeAddr<UseNode *> UseN = *I;
744  assert(!(UseN.Addr->getFlags() & NodeAttrs::PhiRef) &&
745  "Found a PhiRef node as a real reached use!!");
746 
747  NodeAddr<StmtNode *> OwnerN = UseN.Addr->getOwner(*DFG);
748  MachineInstr *UseMI = OwnerN.Addr->getCode();
749  LLVM_DEBUG(dbgs() << "\t\t[MI <" << printMBBReference(*UseMI->getParent())
750  << ">]: " << *UseMI << "\n");
751 
752  int UseMOnum = -1;
753  unsigned NumOperands = UseMI->getNumOperands();
754  for (unsigned j = 0; j < NumOperands - 1; ++j) {
755  const MachineOperand &op = UseMI->getOperand(j);
756  if (op.isReg() && op.isUse() && DefR == op.getReg())
757  UseMOnum = j;
758  }
759  // It is possible that the register will not be found in any operand.
760  // This could happen, for example, when DefR = R4, but the used
761  // register is D2.
762 
763  // Change UseMI if replacement is possible. If any replacement failed,
764  // or wasn't attempted, make sure to keep the TFR.
765  bool Xformed = false;
766  if (UseMOnum >= 0 && InstrEvalResult[UseMI])
767  Xformed = xformUseMI(MI, UseMI, UseN, UseMOnum);
768  Changed |= Xformed;
769  KeepTfr |= !Xformed;
770  }
771  if (!KeepTfr)
772  Deleted.insert(MI);
773  }
774  return Changed;
775 }
776 
777 bool HexagonOptAddrMode::runOnMachineFunction(MachineFunction &MF) {
778  if (skipFunction(MF.getFunction()))
779  return false;
780 
781  bool Changed = false;
782  auto &HST = MF.getSubtarget<HexagonSubtarget>();
783  MRI = &MF.getRegInfo();
784  HII = HST.getInstrInfo();
785  HRI = HST.getRegisterInfo();
786  const auto &MDF = getAnalysis<MachineDominanceFrontier>();
787  MDT = &getAnalysis<MachineDominatorTree>();
788  const TargetOperandInfo TOI(*HII);
789 
790  DataFlowGraph G(MF, *HII, *HRI, *MDT, MDF, TOI);
791  // Need to keep dead phis because we can propagate uses of registers into
792  // nodes dominated by those would-be phis.
794  DFG = &G;
795 
796  Liveness L(*MRI, *DFG);
797  L.computePhiInfo();
798  LV = &L;
799 
800  Deleted.clear();
801  NodeAddr<FuncNode *> FA = DFG->getFunc();
802  LLVM_DEBUG(dbgs() << "==== [RefMap#]=====:\n "
803  << Print<NodeAddr<FuncNode *>>(FA, *DFG) << "\n");
804 
805  for (NodeAddr<BlockNode *> BA : FA.Addr->members(*DFG))
806  Changed |= processBlock(BA);
807 
808  for (auto MI : Deleted)
809  MI->eraseFromParent();
810 
811  if (Changed) {
812  G.build();
813  L.computeLiveIns();
814  L.resetLiveIns();
815  L.resetKills();
816  }
817 
818  return Changed;
819 }
820 
821 //===----------------------------------------------------------------------===//
822 // Public Constructor Functions
823 //===----------------------------------------------------------------------===//
824 
826  return new HexagonOptAddrMode();
827 }
unsigned getTargetFlags() const
const MachineInstrBuilder & add(const MachineOperand &MO) const
uint16_t getFlags() const
Definition: RDFGraph.h:456
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:382
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:163
unsigned getReg() const
getReg - Returns the register number.
void setIsUndef(bool Val=true)
uint32_t NodeId
Definition: RDFGraph.h:260
const MachineInstrBuilder & addGlobalAddress(const GlobalValue *GV, int64_t Offset=0, unsigned char TargetFlags=0) const
#define op(i)
bool mayLoad() const
Return true if this instruction could possibly read memory.
Definition: MCInstrDesc.h:398
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:458
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
amode Optimize addressing mode
INITIALIZE_PASS_BEGIN(HexagonOptAddrMode, "amode-opt", "Optimize addressing mode", false, false) INITIALIZE_PASS_END(HexagonOptAddrMode
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:411
RegisterRef getRegRef(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:408
void setImplicit(bool Val=true)
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:408
static cl::opt< int > CodeGrowthLimit("hexagon-amode-growth-limit", cl::Hidden, cl::init(0), cl::desc("Code growth limit for address mode " "optimization"))
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:405
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1165
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
MachineInstrBundleIterator< MachineInstr > iterator
unsigned const MachineRegisterInfo * MRI
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
MachineInstrBuilder & UseMI
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const GlobalValue * getGlobal() const
amode opt
Represent the analysis usage information of a pass.
MachineInstr * getCode() const
Definition: RDFGraph.h:621
void setImm(int64_t immVal)
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
NodeList members_if(Predicate P, const DataFlowGraph &G) const
Definition: RDFGraph.h:913
NodeList members(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:527
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Iterator for intrusive lists based on ilist_node.
bool isGlobal() const
isGlobal - Tests if this is a MO_GlobalAddress operand.
static uint64_t add(uint64_t LeftOp, uint64_t RightOp)
Definition: FileCheck.cpp:125
MachineOperand class - Representation of each machine instruction operand.
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
int64_t getImm() const
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
std::map< RegisterId, NodeRefSet > RefMap
Definition: RDFLiveness.h:52
void setPreservesAll()
Set by analyses that do not transform their input at all.
bool mayStore() const
Return true if this instruction could possibly modify memory.
Definition: MCInstrDesc.h:404
void initializeHexagonOptAddrModePass(PassRegistry &)
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:253
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:63
NodeId getReachingDef() const
Definition: RDFGraph.h:528
NodeAddr< NodeBase * > getOwner(const DataFlowGraph &G)
Definition: RDFGraph.cpp:434
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
int64_t getOffset() const
Return the offset from the symbol in this operand.
void setReg(unsigned Reg)
Change the register this operand corresponds to.
#define I(x, y, z)
Definition: MD5.cpp:58
void build(unsigned Options=BuildOptions::None)
Definition: RDFGraph.cpp:866
bool isReg() const
isReg - Tests if this is a MO_Register operand.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
FunctionPass * createHexagonOptAddrMode()
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:413
std::unordered_map< RegisterId, DefStack > DefStackMap
Definition: RDFGraph.h:733
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
bool isImplicit() const
A NodeSet contains a set of SUnit DAG nodes with additional information that assigns a priority to th...