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