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