• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===--- HexagonOptAddrMode.cpp -------------------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 // This implements a Hexagon-specific pass to optimize addressing mode for
10 // load/store instructions.
11 //===----------------------------------------------------------------------===//
12 
13 #define DEBUG_TYPE "opt-addr-mode"
14 
15 #include "HexagonTargetMachine.h"
16 #include "RDFGraph.h"
17 #include "RDFLiveness.h"
18 
19 #include "llvm/ADT/DenseSet.h"
20 #include "llvm/CodeGen/MachineBasicBlock.h"
21 #include "llvm/CodeGen/MachineDominanceFrontier.h"
22 #include "llvm/CodeGen/MachineDominators.h"
23 #include "llvm/CodeGen/MachineFunction.h"
24 #include "llvm/CodeGen/MachineInstrBuilder.h"
25 #include "llvm/CodeGen/MachineRegisterInfo.h"
26 #include "llvm/CodeGen/Passes.h"
27 #include "llvm/Support/CommandLine.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/raw_ostream.h"
30 #include "llvm/Target/TargetInstrInfo.h"
31 #include "llvm/Target/TargetMachine.h"
32 #include "llvm/Target/TargetRegisterInfo.h"
33 
34 static cl::opt<int> CodeGrowthLimit("hexagon-amode-growth-limit",
35   cl::Hidden, cl::init(0), cl::desc("Code growth limit for address mode "
36   "optimization"));
37 
38 using namespace llvm;
39 using namespace rdf;
40 
41 namespace llvm {
42   FunctionPass *createHexagonOptAddrMode();
43   void initializeHexagonOptAddrModePass(PassRegistry &);
44 }
45 
46 namespace {
47 class HexagonOptAddrMode : public MachineFunctionPass {
48 public:
49   static char ID;
HexagonOptAddrMode()50   HexagonOptAddrMode()
51       : MachineFunctionPass(ID), HII(0), MDT(0), DFG(0), LV(0) {
52     PassRegistry &R = *PassRegistry::getPassRegistry();
53     initializeHexagonOptAddrModePass(R);
54   }
getPassName() const55   const char *getPassName() const override {
56     return "Optimize addressing mode of load/store";
57   }
getAnalysisUsage(AnalysisUsage & AU) const58   void getAnalysisUsage(AnalysisUsage &AU) const override {
59     MachineFunctionPass::getAnalysisUsage(AU);
60     AU.addRequired<MachineDominatorTree>();
61     AU.addRequired<MachineDominanceFrontier>();
62     AU.setPreservesAll();
63   }
64   bool runOnMachineFunction(MachineFunction &MF) override;
65 
66 private:
67   typedef DenseSet<MachineInstr *> MISetType;
68   typedef DenseMap<MachineInstr *, bool> InstrEvalMap;
69   const HexagonInstrInfo *HII;
70   MachineDominatorTree *MDT;
71   DataFlowGraph *DFG;
72   DataFlowGraph::DefStackMap DefM;
73   std::map<RegisterRef, std::map<NodeId, NodeId>> RDefMap;
74   Liveness *LV;
75   MISetType Deleted;
76 
77   bool processBlock(NodeAddr<BlockNode *> BA);
78   bool xformUseMI(MachineInstr *TfrMI, MachineInstr *UseMI,
79                   NodeAddr<UseNode *> UseN, unsigned UseMOnum);
80   bool analyzeUses(unsigned DefR, const NodeList &UNodeList,
81                    InstrEvalMap &InstrEvalResult, short &SizeInc);
82   bool hasRepForm(MachineInstr *MI, unsigned TfrDefR);
83   bool canRemoveAddasl(NodeAddr<StmtNode *> AddAslSN, MachineInstr *MI,
84                        const NodeList &UNodeList);
85   void getAllRealUses(NodeAddr<StmtNode *> SN, NodeList &UNodeList);
86   bool allValidCandidates(NodeAddr<StmtNode *> SA, NodeList &UNodeList);
87   short getBaseWithLongOffset(const MachineInstr *MI) const;
88   void updateMap(NodeAddr<InstrNode *> IA);
89   bool constructDefMap(MachineBasicBlock *B);
90   bool changeStore(MachineInstr *OldMI, MachineOperand ImmOp,
91                    unsigned ImmOpNum);
92   bool changeLoad(MachineInstr *OldMI, MachineOperand ImmOp, unsigned ImmOpNum);
93   bool changeAddAsl(NodeAddr<UseNode *> AddAslUN, MachineInstr *AddAslMI,
94                     const MachineOperand &ImmOp, unsigned ImmOpNum);
95 };
96 }
97 
98 char HexagonOptAddrMode::ID = 0;
99 
100 INITIALIZE_PASS_BEGIN(HexagonOptAddrMode, "opt-amode",
101                       "Optimize addressing mode", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)102 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
103 INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
104 INITIALIZE_PASS_END(HexagonOptAddrMode, "opt-amode", "Optimize addressing mode",
105                     false, false)
106 
107 bool HexagonOptAddrMode::hasRepForm(MachineInstr *MI, unsigned TfrDefR) {
108   const MCInstrDesc &MID = MI->getDesc();
109 
110   if ((!MID.mayStore() && !MID.mayLoad()) || HII->isPredicated(*MI))
111     return false;
112 
113   if (MID.mayStore()) {
114     MachineOperand StOp = MI->getOperand(MI->getNumOperands() - 1);
115     if (StOp.isReg() && StOp.getReg() == TfrDefR)
116       return false;
117   }
118 
119   if (HII->getAddrMode(MI) == HexagonII::BaseRegOffset)
120     // Tranform to Absolute plus register offset.
121     return (HII->getBaseWithLongOffset(MI) >= 0);
122   else if (HII->getAddrMode(MI) == HexagonII::BaseImmOffset)
123     // Tranform to absolute addressing mode.
124     return (HII->getAbsoluteForm(MI) >= 0);
125 
126   return false;
127 }
128 
129 // Check if addasl instruction can be removed. This is possible only
130 // if it's feeding to only load/store instructions with base + register
131 // offset as these instruction can be tranformed to use 'absolute plus
132 // shifted register offset'.
133 // ex:
134 // Rs = ##foo
135 // Rx = addasl(Rs, Rt, #2)
136 // Rd = memw(Rx + #28)
137 // Above three instructions can be replaced with Rd = memw(Rt<<#2 + ##foo+28)
138 
canRemoveAddasl(NodeAddr<StmtNode * > AddAslSN,MachineInstr * MI,const NodeList & UNodeList)139 bool HexagonOptAddrMode::canRemoveAddasl(NodeAddr<StmtNode *> AddAslSN,
140                                          MachineInstr *MI,
141                                          const NodeList &UNodeList) {
142   // check offset size in addasl. if 'offset > 3' return false
143   const MachineOperand &OffsetOp = MI->getOperand(3);
144   if (!OffsetOp.isImm() || OffsetOp.getImm() > 3)
145     return false;
146 
147   unsigned OffsetReg = MI->getOperand(2).getReg();
148   RegisterRef OffsetRR;
149   NodeId OffsetRegRD = 0;
150   for (NodeAddr<UseNode *> UA : AddAslSN.Addr->members_if(DFG->IsUse, *DFG)) {
151     RegisterRef RR = UA.Addr->getRegRef();
152     if (OffsetReg == RR.Reg) {
153       OffsetRR = RR;
154       OffsetRegRD = UA.Addr->getReachingDef();
155     }
156   }
157 
158   for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
159     NodeAddr<UseNode *> UA = *I;
160     NodeAddr<InstrNode *> IA = UA.Addr->getOwner(*DFG);
161     if ((UA.Addr->getFlags() & NodeAttrs::PhiRef) ||
162         RDefMap[OffsetRR][IA.Id] != OffsetRegRD)
163       return false;
164 
165     MachineInstr *UseMI = NodeAddr<StmtNode *>(IA).Addr->getCode();
166     NodeAddr<DefNode *> OffsetRegDN = DFG->addr<DefNode *>(OffsetRegRD);
167     // Reaching Def to an offset register can't be a phi.
168     if ((OffsetRegDN.Addr->getFlags() & NodeAttrs::PhiRef) &&
169         MI->getParent() != UseMI->getParent())
170     return false;
171 
172     const MCInstrDesc &UseMID = UseMI->getDesc();
173     if ((!UseMID.mayLoad() && !UseMID.mayStore()) ||
174         HII->getAddrMode(UseMI) != HexagonII::BaseImmOffset ||
175         getBaseWithLongOffset(UseMI) < 0)
176       return false;
177 
178     // Addasl output can't be a store value.
179     if (UseMID.mayStore() && UseMI->getOperand(2).isReg() &&
180         UseMI->getOperand(2).getReg() == MI->getOperand(0).getReg())
181       return false;
182 
183     for (auto &Mo : UseMI->operands())
184       if (Mo.isFI())
185         return false;
186   }
187   return true;
188 }
189 
allValidCandidates(NodeAddr<StmtNode * > SA,NodeList & UNodeList)190 bool HexagonOptAddrMode::allValidCandidates(NodeAddr<StmtNode *> SA,
191                                             NodeList &UNodeList) {
192   for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
193     NodeAddr<UseNode *> UN = *I;
194     RegisterRef UR = UN.Addr->getRegRef();
195     NodeSet Visited, Defs;
196     const auto &ReachingDefs = LV->getAllReachingDefsRec(UR, UN, Visited, Defs);
197     if (ReachingDefs.size() > 1) {
198       DEBUG({
199         dbgs() << "*** Multiple Reaching Defs found!!! ***\n";
200         for (auto DI : ReachingDefs) {
201           NodeAddr<UseNode *> DA = DFG->addr<UseNode *>(DI);
202           NodeAddr<StmtNode *> TempIA = DA.Addr->getOwner(*DFG);
203           dbgs() << "\t\t[Reaching Def]: "
204                  << Print<NodeAddr<InstrNode *>>(TempIA, *DFG) << "\n";
205         }
206       });
207       return false;
208     }
209   }
210   return true;
211 }
212 
getAllRealUses(NodeAddr<StmtNode * > SA,NodeList & UNodeList)213 void HexagonOptAddrMode::getAllRealUses(NodeAddr<StmtNode *> SA,
214                                         NodeList &UNodeList) {
215   for (NodeAddr<DefNode *> DA : SA.Addr->members_if(DFG->IsDef, *DFG)) {
216     DEBUG(dbgs() << "\t\t[DefNode]: " << Print<NodeAddr<DefNode *>>(DA, *DFG)
217                  << "\n");
218     RegisterRef DR = DA.Addr->getRegRef();
219     auto UseSet = LV->getAllReachedUses(DR, DA);
220 
221     for (auto UI : UseSet) {
222       NodeAddr<UseNode *> UA = DFG->addr<UseNode *>(UI);
223       DEBUG({
224         NodeAddr<StmtNode *> TempIA = UA.Addr->getOwner(*DFG);
225         dbgs() << "\t\t\t[Reached Use]: "
226                << Print<NodeAddr<InstrNode *>>(TempIA, *DFG) << "\n";
227       });
228 
229       if (UA.Addr->getFlags() & NodeAttrs::PhiRef) {
230         NodeAddr<PhiNode *> PA = UA.Addr->getOwner(*DFG);
231         NodeId id = PA.Id;
232         const Liveness::RefMap &phiUse = LV->getRealUses(id);
233         DEBUG(dbgs() << "\t\t\t\tphi real Uses"
234                      << Print<Liveness::RefMap>(phiUse, *DFG) << "\n");
235         if (phiUse.size() > 0) {
236           for (auto I : phiUse) {
237             if (DR != I.first)
238               continue;
239             auto phiUseSet = I.second;
240             for (auto phiUI : phiUseSet) {
241               NodeAddr<UseNode *> phiUA = DFG->addr<UseNode *>(phiUI);
242               UNodeList.push_back(phiUA);
243             }
244           }
245         }
246       } else
247         UNodeList.push_back(UA);
248     }
249   }
250 }
251 
analyzeUses(unsigned tfrDefR,const NodeList & UNodeList,InstrEvalMap & InstrEvalResult,short & SizeInc)252 bool HexagonOptAddrMode::analyzeUses(unsigned tfrDefR,
253                                      const NodeList &UNodeList,
254                                      InstrEvalMap &InstrEvalResult,
255                                      short &SizeInc) {
256   bool KeepTfr = false;
257   bool HasRepInstr = false;
258   InstrEvalResult.clear();
259 
260   for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
261     bool CanBeReplaced = false;
262     NodeAddr<UseNode *> UN = *I;
263     NodeAddr<StmtNode *> SN = UN.Addr->getOwner(*DFG);
264     MachineInstr *MI = SN.Addr->getCode();
265     const MCInstrDesc &MID = MI->getDesc();
266     if ((MID.mayLoad() || MID.mayStore())) {
267       if (!hasRepForm(MI, tfrDefR)) {
268         KeepTfr = true;
269         continue;
270       }
271       SizeInc++;
272       CanBeReplaced = true;
273     } else if (MI->getOpcode() == Hexagon::S2_addasl_rrri) {
274       NodeList AddaslUseList;
275 
276       DEBUG(dbgs() << "\nGetting ReachedUses for === " << *MI << "\n");
277       getAllRealUses(SN, AddaslUseList);
278       // Process phi nodes.
279       if (allValidCandidates(SN, AddaslUseList) &&
280           canRemoveAddasl(SN, MI, AddaslUseList)) {
281         SizeInc += AddaslUseList.size();
282         SizeInc -= 1; // Reduce size by 1 as addasl itself can be removed.
283         CanBeReplaced = true;
284       } else
285         SizeInc++;
286     } else
287       // Currently, only load/store and addasl are handled.
288       // Some other instructions to consider -
289       // A2_add -> A2_addi
290       // M4_mpyrr_addr -> M4_mpyrr_addi
291       KeepTfr = true;
292 
293     InstrEvalResult[MI] = CanBeReplaced;
294     HasRepInstr |= CanBeReplaced;
295   }
296 
297   // Reduce total size by 2 if original tfr can be deleted.
298   if (!KeepTfr)
299     SizeInc -= 2;
300 
301   return HasRepInstr;
302 }
303 
changeLoad(MachineInstr * OldMI,MachineOperand ImmOp,unsigned ImmOpNum)304 bool HexagonOptAddrMode::changeLoad(MachineInstr *OldMI, MachineOperand ImmOp,
305                                     unsigned ImmOpNum) {
306   bool Changed = false;
307   MachineBasicBlock *BB = OldMI->getParent();
308   auto UsePos = MachineBasicBlock::iterator(OldMI);
309   MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
310   ++InsertPt;
311   unsigned OpStart;
312   unsigned OpEnd = OldMI->getNumOperands();
313   MachineInstrBuilder MIB;
314 
315   if (ImmOpNum == 1) {
316     if (HII->getAddrMode(OldMI) == HexagonII::BaseRegOffset) {
317       short NewOpCode = HII->getBaseWithLongOffset(OldMI);
318       assert(NewOpCode >= 0 && "Invalid New opcode\n");
319       MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
320       MIB.addOperand(OldMI->getOperand(0));
321       MIB.addOperand(OldMI->getOperand(2));
322       MIB.addOperand(OldMI->getOperand(3));
323       MIB.addOperand(ImmOp);
324       OpStart = 4;
325       Changed = true;
326     } else if (HII->getAddrMode(OldMI) == HexagonII::BaseImmOffset) {
327       short NewOpCode = HII->getAbsoluteForm(OldMI);
328       assert(NewOpCode >= 0 && "Invalid New opcode\n");
329       MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode))
330                 .addOperand(OldMI->getOperand(0));
331       const GlobalValue *GV = ImmOp.getGlobal();
332       int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(2).getImm();
333 
334       MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags());
335       OpStart = 3;
336       Changed = true;
337     } else
338       Changed = false;
339 
340     DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
341     DEBUG(dbgs() << "[TO]: " << MIB << "\n");
342   } else if (ImmOpNum == 2 && OldMI->getOperand(3).getImm() == 0) {
343     short NewOpCode = HII->xformRegToImmOffset(OldMI);
344     assert(NewOpCode >= 0 && "Invalid New opcode\n");
345     MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
346     MIB.addOperand(OldMI->getOperand(0));
347     MIB.addOperand(OldMI->getOperand(1));
348     MIB.addOperand(ImmOp);
349     OpStart = 4;
350     Changed = true;
351     DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
352     DEBUG(dbgs() << "[TO]: " << MIB << "\n");
353   }
354 
355   if (Changed)
356     for (unsigned i = OpStart; i < OpEnd; ++i)
357       MIB.addOperand(OldMI->getOperand(i));
358 
359   return Changed;
360 }
361 
changeStore(MachineInstr * OldMI,MachineOperand ImmOp,unsigned ImmOpNum)362 bool HexagonOptAddrMode::changeStore(MachineInstr *OldMI, MachineOperand ImmOp,
363                                      unsigned ImmOpNum) {
364   bool Changed = false;
365   unsigned OpStart;
366   unsigned OpEnd = OldMI->getNumOperands();
367   MachineBasicBlock *BB = OldMI->getParent();
368   auto UsePos = MachineBasicBlock::iterator(OldMI);
369   MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
370   ++InsertPt;
371   MachineInstrBuilder MIB;
372   if (ImmOpNum == 0) {
373     if (HII->getAddrMode(OldMI) == HexagonII::BaseRegOffset) {
374       short NewOpCode = HII->getBaseWithLongOffset(OldMI);
375       assert(NewOpCode >= 0 && "Invalid New opcode\n");
376       MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
377       MIB.addOperand(OldMI->getOperand(1));
378       MIB.addOperand(OldMI->getOperand(2));
379       MIB.addOperand(ImmOp);
380       MIB.addOperand(OldMI->getOperand(3));
381       OpStart = 4;
382     } else if (HII->getAddrMode(OldMI) == HexagonII::BaseImmOffset) {
383       short NewOpCode = HII->getAbsoluteForm(OldMI);
384       assert(NewOpCode >= 0 && "Invalid New opcode\n");
385       MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
386       const GlobalValue *GV = ImmOp.getGlobal();
387       int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(1).getImm();
388       MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags());
389       MIB.addOperand(OldMI->getOperand(2));
390       OpStart = 3;
391     }
392     Changed = true;
393     DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
394     DEBUG(dbgs() << "[TO]: " << MIB << "\n");
395   } else if (ImmOpNum == 1 && OldMI->getOperand(2).getImm() == 0) {
396     short NewOpCode = HII->xformRegToImmOffset(OldMI);
397     assert(NewOpCode >= 0 && "Invalid New opcode\n");
398     MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
399     MIB.addOperand(OldMI->getOperand(0));
400     MIB.addOperand(ImmOp);
401     MIB.addOperand(OldMI->getOperand(1));
402     OpStart = 2;
403     Changed = true;
404     DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
405     DEBUG(dbgs() << "[TO]: " << MIB << "\n");
406   }
407   if (Changed)
408     for (unsigned i = OpStart; i < OpEnd; ++i)
409       MIB.addOperand(OldMI->getOperand(i));
410 
411   return Changed;
412 }
413 
getBaseWithLongOffset(const MachineInstr * MI) const414 short HexagonOptAddrMode::getBaseWithLongOffset(const MachineInstr *MI) const {
415   if (HII->getAddrMode(MI) == HexagonII::BaseImmOffset) {
416     short TempOpCode = HII->getBaseWithRegOffset(MI);
417     return HII->getBaseWithLongOffset(TempOpCode);
418   } else
419     return HII->getBaseWithLongOffset(MI);
420 }
421 
changeAddAsl(NodeAddr<UseNode * > AddAslUN,MachineInstr * AddAslMI,const MachineOperand & ImmOp,unsigned ImmOpNum)422 bool HexagonOptAddrMode::changeAddAsl(NodeAddr<UseNode *> AddAslUN,
423                                       MachineInstr *AddAslMI,
424                                       const MachineOperand &ImmOp,
425                                       unsigned ImmOpNum) {
426   NodeAddr<StmtNode *> SA = AddAslUN.Addr->getOwner(*DFG);
427 
428   DEBUG(dbgs() << "Processing addasl :" << *AddAslMI << "\n");
429 
430   NodeList UNodeList;
431   getAllRealUses(SA, UNodeList);
432 
433   for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
434     NodeAddr<UseNode *> UseUN = *I;
435     assert(!(UseUN.Addr->getFlags() & NodeAttrs::PhiRef) &&
436            "Can't transform this 'AddAsl' instruction!");
437 
438     NodeAddr<StmtNode *> UseIA = UseUN.Addr->getOwner(*DFG);
439     DEBUG(dbgs() << "[InstrNode]: " << Print<NodeAddr<InstrNode *>>(UseIA, *DFG)
440                  << "\n");
441     MachineInstr *UseMI = UseIA.Addr->getCode();
442     DEBUG(dbgs() << "[MI <BB#" << UseMI->getParent()->getNumber()
443                  << ">]: " << *UseMI << "\n");
444     const MCInstrDesc &UseMID = UseMI->getDesc();
445     assert(HII->getAddrMode(UseMI) == HexagonII::BaseImmOffset);
446 
447     auto UsePos = MachineBasicBlock::iterator(UseMI);
448     MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
449     short NewOpCode = getBaseWithLongOffset(UseMI);
450     assert(NewOpCode >= 0 && "Invalid New opcode\n");
451 
452     unsigned OpStart;
453     unsigned OpEnd = UseMI->getNumOperands();
454 
455     MachineBasicBlock *BB = UseMI->getParent();
456     MachineInstrBuilder MIB =
457         BuildMI(*BB, InsertPt, UseMI->getDebugLoc(), HII->get(NewOpCode));
458     // change mem(Rs + # ) -> mem(Rt << # + ##)
459     if (UseMID.mayLoad()) {
460       MIB.addOperand(UseMI->getOperand(0));
461       MIB.addOperand(AddAslMI->getOperand(2));
462       MIB.addOperand(AddAslMI->getOperand(3));
463       const GlobalValue *GV = ImmOp.getGlobal();
464       MIB.addGlobalAddress(GV, UseMI->getOperand(2).getImm(),
465                            ImmOp.getTargetFlags());
466       OpStart = 3;
467     } else if (UseMID.mayStore()) {
468       MIB.addOperand(AddAslMI->getOperand(2));
469       MIB.addOperand(AddAslMI->getOperand(3));
470       const GlobalValue *GV = ImmOp.getGlobal();
471       MIB.addGlobalAddress(GV, UseMI->getOperand(1).getImm(),
472                            ImmOp.getTargetFlags());
473       MIB.addOperand(UseMI->getOperand(2));
474       OpStart = 3;
475     } else
476       llvm_unreachable("Unhandled instruction");
477 
478     for (unsigned i = OpStart; i < OpEnd; ++i)
479       MIB.addOperand(UseMI->getOperand(i));
480 
481     Deleted.insert(UseMI);
482   }
483 
484   return true;
485 }
486 
xformUseMI(MachineInstr * TfrMI,MachineInstr * UseMI,NodeAddr<UseNode * > UseN,unsigned UseMOnum)487 bool HexagonOptAddrMode::xformUseMI(MachineInstr *TfrMI, MachineInstr *UseMI,
488                                     NodeAddr<UseNode *> UseN,
489                                     unsigned UseMOnum) {
490   const MachineOperand ImmOp = TfrMI->getOperand(1);
491   const MCInstrDesc &MID = UseMI->getDesc();
492   unsigned Changed = false;
493   if (MID.mayLoad())
494     Changed = changeLoad(UseMI, ImmOp, UseMOnum);
495   else if (MID.mayStore())
496     Changed = changeStore(UseMI, ImmOp, UseMOnum);
497   else if (UseMI->getOpcode() == Hexagon::S2_addasl_rrri)
498     Changed = changeAddAsl(UseN, UseMI, ImmOp, UseMOnum);
499 
500   if (Changed)
501     Deleted.insert(UseMI);
502 
503   return Changed;
504 }
505 
processBlock(NodeAddr<BlockNode * > BA)506 bool HexagonOptAddrMode::processBlock(NodeAddr<BlockNode *> BA) {
507   bool Changed = false;
508 
509   for (auto IA : BA.Addr->members(*DFG)) {
510     if (!DFG->IsCode<NodeAttrs::Stmt>(IA))
511       continue;
512 
513     NodeAddr<StmtNode *> SA = IA;
514     MachineInstr *MI = SA.Addr->getCode();
515     if (MI->getOpcode() != Hexagon::A2_tfrsi ||
516         !MI->getOperand(1).isGlobal())
517       continue;
518 
519     DEBUG(dbgs() << "[Analyzing A2_tfrsi]: " << *MI << "\n");
520     DEBUG(dbgs() << "\t[InstrNode]: " << Print<NodeAddr<InstrNode *>>(IA, *DFG)
521                  << "\n");
522 
523     NodeList UNodeList;
524     getAllRealUses(SA, UNodeList);
525 
526     if (!allValidCandidates(SA, UNodeList))
527       continue;
528 
529     short SizeInc = 0;
530     unsigned DefR = MI->getOperand(0).getReg();
531     InstrEvalMap InstrEvalResult;
532 
533     // Analyze all uses and calculate increase in size. Perform the optimization
534     // only if there is no increase in size.
535     if (!analyzeUses(DefR, UNodeList, InstrEvalResult, SizeInc))
536       continue;
537     if (SizeInc > CodeGrowthLimit)
538       continue;
539 
540     bool KeepTfr = false;
541 
542     DEBUG(dbgs() << "\t[Total reached uses] : " << UNodeList.size() << "\n");
543     DEBUG(dbgs() << "\t[Processing Reached Uses] ===\n");
544     for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
545       NodeAddr<UseNode *> UseN = *I;
546       assert(!(UseN.Addr->getFlags() & NodeAttrs::PhiRef) &&
547              "Found a PhiRef node as a real reached use!!");
548 
549       NodeAddr<StmtNode *> OwnerN = UseN.Addr->getOwner(*DFG);
550       MachineInstr *UseMI = OwnerN.Addr->getCode();
551       DEBUG(dbgs() << "\t\t[MI <BB#" << UseMI->getParent()->getNumber()
552                    << ">]: " << *UseMI << "\n");
553 
554       int UseMOnum = -1;
555       unsigned NumOperands = UseMI->getNumOperands();
556       for (unsigned j = 0; j < NumOperands - 1; ++j) {
557         const MachineOperand &op = UseMI->getOperand(j);
558         if (op.isReg() && op.isUse() && DefR == op.getReg())
559           UseMOnum = j;
560       }
561       assert(UseMOnum >= 0 && "Invalid reached use!");
562 
563       if (InstrEvalResult[UseMI])
564         // Change UseMI if replacement is possible.
565         Changed |= xformUseMI(MI, UseMI, UseN, UseMOnum);
566       else
567         KeepTfr = true;
568     }
569     if (!KeepTfr)
570       Deleted.insert(MI);
571   }
572   return Changed;
573 }
574 
updateMap(NodeAddr<InstrNode * > IA)575 void HexagonOptAddrMode::updateMap(NodeAddr<InstrNode *> IA) {
576   RegisterSet RRs;
577   for (NodeAddr<RefNode *> RA : IA.Addr->members(*DFG))
578     RRs.insert(RA.Addr->getRegRef());
579   bool Common = false;
580   for (auto &R : RDefMap) {
581     if (!RRs.count(R.first))
582       continue;
583     Common = true;
584     break;
585   }
586   if (!Common)
587     return;
588 
589   for (auto &R : RDefMap) {
590     auto F = DefM.find(R.first);
591     if (F == DefM.end() || F->second.empty())
592       continue;
593     R.second[IA.Id] = F->second.top()->Id;
594   }
595 }
596 
constructDefMap(MachineBasicBlock * B)597 bool HexagonOptAddrMode::constructDefMap(MachineBasicBlock *B) {
598   bool Changed = false;
599   auto BA = DFG->getFunc().Addr->findBlock(B, *DFG);
600   DFG->markBlock(BA.Id, DefM);
601 
602   for (NodeAddr<InstrNode *> IA : BA.Addr->members(*DFG)) {
603     updateMap(IA);
604     DFG->pushDefs(IA, DefM);
605   }
606 
607   MachineDomTreeNode *N = MDT->getNode(B);
608   for (auto I : *N)
609     Changed |= constructDefMap(I->getBlock());
610 
611   DFG->releaseBlock(BA.Id, DefM);
612   return Changed;
613 }
614 
runOnMachineFunction(MachineFunction & MF)615 bool HexagonOptAddrMode::runOnMachineFunction(MachineFunction &MF) {
616   bool Changed = false;
617   auto &HST = MF.getSubtarget<HexagonSubtarget>();
618   auto &MRI = MF.getRegInfo();
619   HII = HST.getInstrInfo();
620   const auto &MDF = getAnalysis<MachineDominanceFrontier>();
621   MDT = &getAnalysis<MachineDominatorTree>();
622   const auto &TRI = *MF.getSubtarget().getRegisterInfo();
623   const TargetOperandInfo TOI(*HII);
624 
625   RegisterAliasInfo RAI(TRI);
626   DataFlowGraph G(MF, *HII, TRI, *MDT, MDF, RAI, TOI);
627   G.build();
628   DFG = &G;
629 
630   Liveness L(MRI, *DFG);
631   L.computePhiInfo();
632   LV = &L;
633 
634   constructDefMap(&DFG->getMF().front());
635 
636   Deleted.clear();
637   NodeAddr<FuncNode *> FA = DFG->getFunc();
638   DEBUG(dbgs() << "==== [RefMap#]=====:\n "
639                << Print<NodeAddr<FuncNode *>>(FA, *DFG) << "\n");
640 
641   for (NodeAddr<BlockNode *> BA : FA.Addr->members(*DFG))
642     Changed |= processBlock(BA);
643 
644   for (auto MI : Deleted)
645     MI->eraseFromParent();
646 
647   if (Changed) {
648     G.build();
649     L.computeLiveIns();
650     L.resetLiveIns();
651     L.resetKills();
652   }
653 
654   return Changed;
655 }
656 
657 //===----------------------------------------------------------------------===//
658 //                         Public Constructor Functions
659 //===----------------------------------------------------------------------===//
660 
createHexagonOptAddrMode()661 FunctionPass *llvm::createHexagonOptAddrMode() {
662   return new HexagonOptAddrMode();
663 }
664