Home | History | Annotate | Download | only in Hexagon 
      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;
     50   HexagonOptAddrMode()
     51       : MachineFunctionPass(ID), HII(0), MDT(0), DFG(0), LV(0) {
     52     PassRegistry &R = *PassRegistry::getPassRegistry();
     53     initializeHexagonOptAddrModePass(R);
     54   }
     55   const char *getPassName() const override {
     56     return "Optimize addressing mode of load/store";
     57   }
     58   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)
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    414 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 
    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 
    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 
    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 
    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 
    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 
    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 
    661 FunctionPass *llvm::createHexagonOptAddrMode() {
    662   return new HexagonOptAddrMode();
    663 }
    664