lib/Target/Hexagon/HexagonOptAddrMode.cpp

   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 }