llvm/lib/Target/Hexagon/HexagonOptAddrMode.cpp

   1 //===- HexagonOptAddrMode.cpp ---------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 // This implements a Hexagon-specific pass to optimize addressing mode for
   9 // load/store instructions.
  10 //===----------------------------------------------------------------------===//
  11
  12 #include "HexagonInstrInfo.h"
  13 #include "HexagonSubtarget.h"
  14 #include "MCTargetDesc/HexagonBaseInfo.h"
  15 #include "llvm/ADT/DenseMap.h"
  16 #include "llvm/ADT/DenseSet.h"
  17 #include "llvm/ADT/StringRef.h"
  18 #include "llvm/CodeGen/MachineBasicBlock.h"
  19 #include "llvm/CodeGen/MachineDominanceFrontier.h"
  20 #include "llvm/CodeGen/MachineDominators.h"
  21 #include "llvm/CodeGen/MachineFunction.h"
  22 #include "llvm/CodeGen/MachineFunctionPass.h"
  23 #include "llvm/CodeGen/MachineInstr.h"
  24 #include "llvm/CodeGen/MachineInstrBuilder.h"
  25 #include "llvm/CodeGen/MachineOperand.h"
  26 #include "llvm/CodeGen/MachineRegisterInfo.h"
  27 #include "llvm/CodeGen/RDFGraph.h"
  28 #include "llvm/CodeGen/RDFLiveness.h"
  29 #include "llvm/CodeGen/RDFRegisters.h"
  30 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  31 #include "llvm/InitializePasses.h"
  32 #include "llvm/MC/MCInstrDesc.h"
  33 #include "llvm/Pass.h"
  34 #include "llvm/Support/CommandLine.h"
  35 #include "llvm/Support/Debug.h"
  36 #include "llvm/Support/ErrorHandling.h"
  37 #include "llvm/Support/raw_ostream.h"
  38 #include <algorithm>
  39 #include <cassert>
  40 #include <cstdint>
  41
  42 #define DEBUG_TYPE "opt-addr-mode"
  43
  44 using namespace llvm;
  45 using namespace rdf;
  46
  47 static cl::opt<int> CodeGrowthLimit("hexagon-amode-growth-limit",
  48   cl::Hidden, cl::init(0), cl::desc("Code growth limit for address mode "
  49   "optimization"));
  50
  51 extern cl::opt<unsigned> RDFFuncBlockLimit;
  52
  53 namespace llvm {
  54
  55   FunctionPass *createHexagonOptAddrMode();
  56   void initializeHexagonOptAddrModePass(PassRegistry&);
  57
  58 } // end namespace llvm
  59
  60 namespace {
  61
  62 class HexagonOptAddrMode : public MachineFunctionPass {
  63 public:
  64   static char ID;
  65
  66   HexagonOptAddrMode() : MachineFunctionPass(ID) {}
  67
  68   StringRef getPassName() const override {
  69     return "Optimize addressing mode of load/store";
  70   }
  71
  72   void getAnalysisUsage(AnalysisUsage &AU) const override {
  73     MachineFunctionPass::getAnalysisUsage(AU);
  74     AU.addRequired<MachineDominatorTreeWrapperPass>();
  75     AU.addRequired<MachineDominanceFrontier>();
  76     AU.setPreservesAll();
  77   }
  78
  79   bool runOnMachineFunction(MachineFunction &MF) override;
  80
  81 private:
  82   using MISetType = DenseSet<MachineInstr *>;
  83   using InstrEvalMap = DenseMap<MachineInstr *, bool>;
  84   DenseSet<MachineInstr *> ProcessedAddiInsts;
  85
  86   MachineRegisterInfo *MRI = nullptr;
  87   const TargetRegisterInfo *TRI = nullptr;
  88   const HexagonInstrInfo *HII = nullptr;
  89   const HexagonRegisterInfo *HRI = nullptr;
  90   MachineDominatorTree *MDT = nullptr;
  91   DataFlowGraph *DFG = nullptr;
  92   DataFlowGraph::DefStackMap DefM;
  93   Liveness *LV = nullptr;
  94   MISetType Deleted;
  95
  96   bool processBlock(NodeAddr<BlockNode *> BA);
  97   bool xformUseMI(MachineInstr *TfrMI, MachineInstr *UseMI,
  98                   NodeAddr<UseNode *> UseN, unsigned UseMOnum);
  99   bool processAddBases(NodeAddr<StmtNode *> AddSN, MachineInstr *AddMI);
 100   bool usedInLoadStore(NodeAddr<StmtNode *> CurrentInstSN, int64_t NewOffset);
 101   bool findFirstReachedInst(
 102       MachineInstr *AddMI,
 103       std::vector<std::pair<NodeAddr<StmtNode *>, NodeAddr<UseNode *>>>
 104           &AddiList,
 105       NodeAddr<StmtNode *> &UseSN);
 106   bool updateAddBases(MachineInstr *CurrentMI, MachineInstr *FirstReachedMI,
 107                       int64_t NewOffset);
 108   bool processAddUses(NodeAddr<StmtNode *> AddSN, MachineInstr *AddMI,
 109                       const NodeList &UNodeList);
 110   bool updateAddUses(MachineInstr *AddMI, MachineInstr *UseMI);
 111   bool analyzeUses(unsigned DefR, const NodeList &UNodeList,
 112                    InstrEvalMap &InstrEvalResult, short &SizeInc);
 113   bool hasRepForm(MachineInstr &MI, unsigned TfrDefR);
 114   bool canRemoveAddasl(NodeAddr<StmtNode *> AddAslSN, MachineInstr &MI,
 115                        const NodeList &UNodeList);
 116   bool isSafeToExtLR(NodeAddr<StmtNode *> SN, MachineInstr *MI,
 117                      unsigned LRExtReg, const NodeList &UNodeList);
 118   void getAllRealUses(NodeAddr<StmtNode *> SN, NodeList &UNodeList);
 119   bool allValidCandidates(NodeAddr<StmtNode *> SA, NodeList &UNodeList);
 120   short getBaseWithLongOffset(const MachineInstr &MI) const;
 121   bool changeStore(MachineInstr *OldMI, MachineOperand ImmOp,
 122                    unsigned ImmOpNum);
 123   bool changeLoad(MachineInstr *OldMI, MachineOperand ImmOp, unsigned ImmOpNum);
 124   bool changeAddAsl(NodeAddr<UseNode *> AddAslUN, MachineInstr *AddAslMI,
 125                     const MachineOperand &ImmOp, unsigned ImmOpNum);
 126   bool isValidOffset(MachineInstr *MI, int Offset);
 127   unsigned getBaseOpPosition(MachineInstr *MI);
 128   unsigned getOffsetOpPosition(MachineInstr *MI);
 129 };
 130
 131 } // end anonymous namespace
 132
 133 char HexagonOptAddrMode::ID = 0;
 134
 135 INITIALIZE_PASS_BEGIN(HexagonOptAddrMode, "amode-opt",
 136                       "Optimize addressing mode", false, false)
 137 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
 138 INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
 139 INITIALIZE_PASS_END(HexagonOptAddrMode, "amode-opt", "Optimize addressing mode",
 140                     false, false)
 141
 142 bool HexagonOptAddrMode::hasRepForm(MachineInstr &MI, unsigned TfrDefR) {
 143   const MCInstrDesc &MID = MI.getDesc();
 144
 145   if ((!MID.mayStore() && !MID.mayLoad()) || HII->isPredicated(MI))
 146     return false;
 147
 148   if (MID.mayStore()) {
 149     MachineOperand StOp = MI.getOperand(MI.getNumOperands() - 1);
 150     if (StOp.isReg() && StOp.getReg() == TfrDefR)
 151       return false;
 152   }
 153
 154   if (HII->getAddrMode(MI) == HexagonII::BaseRegOffset)
 155     // Tranform to Absolute plus register offset.
 156     return (HII->changeAddrMode_rr_ur(MI) >= 0);
 157   else if (HII->getAddrMode(MI) == HexagonII::BaseImmOffset)
 158     // Tranform to absolute addressing mode.
 159     return (HII->changeAddrMode_io_abs(MI) >= 0);
 160
 161   return false;
 162 }
 163
 164 // Check if addasl instruction can be removed. This is possible only
 165 // if it's feeding to only load/store instructions with base + register
 166 // offset as these instruction can be tranformed to use 'absolute plus
 167 // shifted register offset'.
 168 // ex:
 169 // Rs = ##foo
 170 // Rx = addasl(Rs, Rt, #2)
 171 // Rd = memw(Rx + #28)
 172 // Above three instructions can be replaced with Rd = memw(Rt<<#2 + ##foo+28)
 173
 174 bool HexagonOptAddrMode::canRemoveAddasl(NodeAddr<StmtNode *> AddAslSN,
 175                                          MachineInstr &MI,
 176                                          const NodeList &UNodeList) {
 177   // check offset size in addasl. if 'offset > 3' return false
 178   const MachineOperand &OffsetOp = MI.getOperand(3);
 179   if (!OffsetOp.isImm() || OffsetOp.getImm() > 3)
 180     return false;
 181
 182   Register OffsetReg = MI.getOperand(2).getReg();
 183   RegisterRef OffsetRR;
 184   NodeId OffsetRegRD = 0;
 185   for (NodeAddr<UseNode *> UA : AddAslSN.Addr->members_if(DFG->IsUse, *DFG)) {
 186     RegisterRef RR = UA.Addr->getRegRef(*DFG);
 187     if (OffsetReg == RR.Reg) {
 188       OffsetRR = RR;
 189       OffsetRegRD = UA.Addr->getReachingDef();
 190     }
 191   }
 192
 193   for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
 194     NodeAddr<UseNode *> UA = *I;
 195     NodeAddr<InstrNode *> IA = UA.Addr->getOwner(*DFG);
 196     if (UA.Addr->getFlags() & NodeAttrs::PhiRef)
 197       return false;
 198     NodeAddr<RefNode*> AA = LV->getNearestAliasedRef(OffsetRR, IA);
 199     if ((DFG->IsDef(AA) && AA.Id != OffsetRegRD) ||
 200          AA.Addr->getReachingDef() != OffsetRegRD)
 201       return false;
 202
 203     MachineInstr &UseMI = *NodeAddr<StmtNode *>(IA).Addr->getCode();
 204     NodeAddr<DefNode *> OffsetRegDN = DFG->addr<DefNode *>(OffsetRegRD);
 205     // Reaching Def to an offset register can't be a phi.
 206     if ((OffsetRegDN.Addr->getFlags() & NodeAttrs::PhiRef) &&
 207         MI.getParent() != UseMI.getParent())
 208     return false;
 209
 210     const MCInstrDesc &UseMID = UseMI.getDesc();
 211     if ((!UseMID.mayLoad() && !UseMID.mayStore()) ||
 212         HII->getAddrMode(UseMI) != HexagonII::BaseImmOffset ||
 213         getBaseWithLongOffset(UseMI) < 0)
 214       return false;
 215
 216     // Addasl output can't be a store value.
 217     if (UseMID.mayStore() && UseMI.getOperand(2).isReg() &&
 218         UseMI.getOperand(2).getReg() == MI.getOperand(0).getReg())
 219       return false;
 220
 221     for (auto &Mo : UseMI.operands())
 222       // Is it a frame index?
 223       if (Mo.isFI())
 224         return false;
 225     // Is the OffsetReg definition actually reaches UseMI?
 226     if (!UseMI.getParent()->isLiveIn(OffsetReg) &&
 227         MI.getParent() != UseMI.getParent()) {
 228       LLVM_DEBUG(dbgs() << "  The offset reg " << printReg(OffsetReg, TRI)
 229                         << " is NOT live in to MBB "
 230                         << UseMI.getParent()->getName() << "\n");
 231       return false;
 232     }
 233   }
 234   return true;
 235 }
 236
 237 bool HexagonOptAddrMode::allValidCandidates(NodeAddr<StmtNode *> SA,
 238                                             NodeList &UNodeList) {
 239   for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
 240     NodeAddr<UseNode *> UN = *I;
 241     RegisterRef UR = UN.Addr->getRegRef(*DFG);
 242     NodeSet Visited, Defs;
 243     const auto &P = LV->getAllReachingDefsRec(UR, UN, Visited, Defs);
 244     if (!P.second) {
 245       LLVM_DEBUG({
 246         dbgs() << "*** Unable to collect all reaching defs for use ***\n"
 247                << PrintNode<UseNode*>(UN, *DFG) << '\n'
 248                << "The program's complexity may exceed the limits.\n";
 249       });
 250       return false;
 251     }
 252     const auto &ReachingDefs = P.first;
 253     if (ReachingDefs.size() > 1) {
 254       LLVM_DEBUG({
 255         dbgs() << "*** Multiple Reaching Defs found!!! ***\n";
 256         for (auto DI : ReachingDefs) {
 257           NodeAddr<UseNode *> DA = DFG->addr<UseNode *>(DI);
 258           NodeAddr<StmtNode *> TempIA = DA.Addr->getOwner(*DFG);
 259           dbgs() << "\t\t[Reaching Def]: "
 260                  << Print<NodeAddr<InstrNode *>>(TempIA, *DFG) << "\n";
 261         }
 262       });
 263       return false;
 264     }
 265   }
 266   return true;
 267 }
 268
 269 void HexagonOptAddrMode::getAllRealUses(NodeAddr<StmtNode *> SA,
 270                                         NodeList &UNodeList) {
 271   for (NodeAddr<DefNode *> DA : SA.Addr->members_if(DFG->IsDef, *DFG)) {
 272     LLVM_DEBUG(dbgs() << "\t\t[DefNode]: "
 273                       << Print<NodeAddr<DefNode *>>(DA, *DFG) << "\n");
 274     RegisterRef DR = DA.Addr->getRegRef(*DFG);
 275
 276     auto UseSet = LV->getAllReachedUses(DR, DA);
 277
 278     for (auto UI : UseSet) {
 279       NodeAddr<UseNode *> UA = DFG->addr<UseNode *>(UI);
 280       LLVM_DEBUG({
 281         NodeAddr<StmtNode *> TempIA = UA.Addr->getOwner(*DFG);
 282         dbgs() << "\t\t\t[Reached Use]: "
 283                << Print<NodeAddr<InstrNode *>>(TempIA, *DFG) << "\n";
 284       });
 285
 286       if (UA.Addr->getFlags() & NodeAttrs::PhiRef) {
 287         NodeAddr<PhiNode *> PA = UA.Addr->getOwner(*DFG);
 288         NodeId id = PA.Id;
 289         const Liveness::RefMap &phiUse = LV->getRealUses(id);
 290         LLVM_DEBUG(dbgs() << "\t\t\t\tphi real Uses"
 291                           << Print<Liveness::RefMap>(phiUse, *DFG) << "\n");
 292         if (!phiUse.empty()) {
 293           for (auto I : phiUse) {
 294             if (!DFG->getPRI().alias(RegisterRef(I.first), DR))
 295               continue;
 296             auto phiUseSet = I.second;
 297             for (auto phiUI : phiUseSet) {
 298               NodeAddr<UseNode *> phiUA = DFG->addr<UseNode *>(phiUI.first);
 299               UNodeList.push_back(phiUA);
 300             }
 301           }
 302         }
 303       } else
 304         UNodeList.push_back(UA);
 305     }
 306   }
 307 }
 308
 309 bool HexagonOptAddrMode::isSafeToExtLR(NodeAddr<StmtNode *> SN,
 310                                        MachineInstr *MI, unsigned LRExtReg,
 311                                        const NodeList &UNodeList) {
 312   RegisterRef LRExtRR;
 313   NodeId LRExtRegRD = 0;
 314   // Iterate through all the UseNodes in SN and find the reaching def
 315   // for the LRExtReg.
 316   for (NodeAddr<UseNode *> UA : SN.Addr->members_if(DFG->IsUse, *DFG)) {
 317     RegisterRef RR = UA.Addr->getRegRef(*DFG);
 318     if (LRExtReg == RR.Reg) {
 319       LRExtRR = RR;
 320       LRExtRegRD = UA.Addr->getReachingDef();
 321     }
 322   }
 323
 324   for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
 325     NodeAddr<UseNode *> UA = *I;
 326     NodeAddr<InstrNode *> IA = UA.Addr->getOwner(*DFG);
 327     // The reaching def of LRExtRR at load/store node should be same as the
 328     // one reaching at the SN.
 329     if (UA.Addr->getFlags() & NodeAttrs::PhiRef)
 330       return false;
 331     NodeAddr<RefNode*> AA = LV->getNearestAliasedRef(LRExtRR, IA);
 332     if ((DFG->IsDef(AA) && AA.Id != LRExtRegRD) ||
 333         AA.Addr->getReachingDef() != LRExtRegRD) {
 334       LLVM_DEBUG(
 335           dbgs() << "isSafeToExtLR: Returning false; another reaching def\n");
 336       return false;
 337     }
 338
 339     // If the register is undefined (for example if it's a reserved register),
 340     // it may still be possible to extend the range, but it's safer to be
 341     // conservative and just punt.
 342     if (LRExtRegRD == 0)
 343       return false;
 344
 345     MachineInstr *UseMI = NodeAddr<StmtNode *>(IA).Addr->getCode();
 346     NodeAddr<DefNode *> LRExtRegDN = DFG->addr<DefNode *>(LRExtRegRD);
 347     // Reaching Def to LRExtReg can't be a phi.
 348     if ((LRExtRegDN.Addr->getFlags() & NodeAttrs::PhiRef) &&
 349         MI->getParent() != UseMI->getParent())
 350       return false;
 351     // Is the OffsetReg definition actually reaches UseMI?
 352     if (!UseMI->getParent()->isLiveIn(LRExtReg) &&
 353         MI->getParent() != UseMI->getParent()) {
 354       LLVM_DEBUG(dbgs() << "  The LRExtReg reg " << printReg(LRExtReg, TRI)
 355                         << " is NOT live in to MBB "
 356                         << UseMI->getParent()->getName() << "\n");
 357       return false;
 358     }
 359   }
 360   return true;
 361 }
 362
 363 bool HexagonOptAddrMode::isValidOffset(MachineInstr *MI, int Offset) {
 364   if (HII->isHVXVec(*MI)) {
 365     // only HVX vgather instructions handled
 366     // TODO: extend the pass to other vector load/store operations
 367     switch (MI->getOpcode()) {
 368     case Hexagon::V6_vgathermh_pseudo:
 369     case Hexagon::V6_vgathermw_pseudo:
 370     case Hexagon::V6_vgathermhw_pseudo:
 371     case Hexagon::V6_vgathermhq_pseudo:
 372     case Hexagon::V6_vgathermwq_pseudo:
 373     case Hexagon::V6_vgathermhwq_pseudo:
 374       return HII->isValidOffset(MI->getOpcode(), Offset, HRI, false);
 375     default:
 376       if (HII->getAddrMode(*MI) == HexagonII::BaseImmOffset) {
 377         // The immediates are mentioned in multiples of vector counts
 378         unsigned AlignMask = HII->getMemAccessSize(*MI) - 1;
 379         if ((AlignMask & Offset) == 0)
 380           return HII->isValidOffset(MI->getOpcode(), Offset, HRI, false);
 381       }
 382       return false;
 383     }
 384   }
 385
 386   if (HII->getAddrMode(*MI) != HexagonII::BaseImmOffset)
 387     return false;
 388
 389   unsigned AlignMask = 0;
 390   switch (HII->getMemAccessSize(*MI)) {
 391   case HexagonII::MemAccessSize::DoubleWordAccess:
 392     AlignMask = 0x7;
 393     break;
 394   case HexagonII::MemAccessSize::WordAccess:
 395     AlignMask = 0x3;
 396     break;
 397   case HexagonII::MemAccessSize::HalfWordAccess:
 398     AlignMask = 0x1;
 399     break;
 400   case HexagonII::MemAccessSize::ByteAccess:
 401     AlignMask = 0x0;
 402     break;
 403   default:
 404     return false;
 405   }
 406
 407   if ((AlignMask & Offset) != 0)
 408     return false;
 409   return HII->isValidOffset(MI->getOpcode(), Offset, HRI, false);
 410 }
 411
 412 unsigned HexagonOptAddrMode::getBaseOpPosition(MachineInstr *MI) {
 413   const MCInstrDesc &MID = MI->getDesc();
 414   switch (MI->getOpcode()) {
 415   // vgather pseudos are mayLoad and mayStore
 416   // hence need to explicitly specify Base and
 417   // Offset operand positions
 418   case Hexagon::V6_vgathermh_pseudo:
 419   case Hexagon::V6_vgathermw_pseudo:
 420   case Hexagon::V6_vgathermhw_pseudo:
 421   case Hexagon::V6_vgathermhq_pseudo:
 422   case Hexagon::V6_vgathermwq_pseudo:
 423   case Hexagon::V6_vgathermhwq_pseudo:
 424     return 0;
 425   default:
 426     return MID.mayLoad() ? 1 : 0;
 427   }
 428 }
 429
 430 unsigned HexagonOptAddrMode::getOffsetOpPosition(MachineInstr *MI) {
 431   assert(
 432       (HII->getAddrMode(*MI) == HexagonII::BaseImmOffset) &&
 433       "Looking for an offset in non-BaseImmOffset addressing mode instruction");
 434
 435   const MCInstrDesc &MID = MI->getDesc();
 436   switch (MI->getOpcode()) {
 437   // vgather pseudos are mayLoad and mayStore
 438   // hence need to explicitly specify Base and
 439   // Offset operand positions
 440   case Hexagon::V6_vgathermh_pseudo:
 441   case Hexagon::V6_vgathermw_pseudo:
 442   case Hexagon::V6_vgathermhw_pseudo:
 443   case Hexagon::V6_vgathermhq_pseudo:
 444   case Hexagon::V6_vgathermwq_pseudo:
 445   case Hexagon::V6_vgathermhwq_pseudo:
 446     return 1;
 447   default:
 448     return MID.mayLoad() ? 2 : 1;
 449   }
 450 }
 451
 452 bool HexagonOptAddrMode::usedInLoadStore(NodeAddr<StmtNode *> CurrentInstSN,
 453                                          int64_t NewOffset) {
 454   NodeList LoadStoreUseList;
 455
 456   getAllRealUses(CurrentInstSN, LoadStoreUseList);
 457   bool FoundLoadStoreUse = false;
 458   for (auto I = LoadStoreUseList.begin(), E = LoadStoreUseList.end(); I != E;
 459        ++I) {
 460     NodeAddr<UseNode *> UN = *I;
 461     NodeAddr<StmtNode *> SN = UN.Addr->getOwner(*DFG);
 462     MachineInstr *LoadStoreMI = SN.Addr->getCode();
 463     const MCInstrDesc &MID = LoadStoreMI->getDesc();
 464     if ((MID.mayLoad() || MID.mayStore()) &&
 465         isValidOffset(LoadStoreMI, NewOffset)) {
 466       FoundLoadStoreUse = true;
 467       break;
 468     }
 469   }
 470   return FoundLoadStoreUse;
 471 }
 472
 473 bool HexagonOptAddrMode::findFirstReachedInst(
 474     MachineInstr *AddMI,
 475     std::vector<std::pair<NodeAddr<StmtNode *>, NodeAddr<UseNode *>>> &AddiList,
 476     NodeAddr<StmtNode *> &UseSN) {
 477   // Find the very first Addi instruction in the current basic block among the
 478   // AddiList This is the Addi that should be preserved so that we do not need
 479   // to handle the complexity of moving instructions
 480   //
 481   // TODO: find Addi instructions across basic blocks
 482   //
 483   // TODO: Try to remove this and add a solution that optimizes the number of
 484   // Addi instructions that can be modified.
 485   // This change requires choosing the Addi with the median offset value, but
 486   // would also require moving that instruction above the others. Since this
 487   // pass runs after register allocation, there might be multiple cases that
 488   // need to be handled if we move instructions around
 489   MachineBasicBlock *CurrentMBB = AddMI->getParent();
 490   for (auto &InstIter : *CurrentMBB) {
 491     // If the instruction is an Addi and is in the AddiList
 492     if (InstIter.getOpcode() == Hexagon::A2_addi) {
 493       auto Iter = std::find_if(
 494           AddiList.begin(), AddiList.end(), [&InstIter](const auto &SUPair) {
 495             return SUPair.first.Addr->getCode() == &InstIter;
 496           });
 497       if (Iter != AddiList.end()) {
 498         UseSN = Iter->first;
 499         return true;
 500       }
 501     }
 502   }
 503   return false;
 504 }
 505
 506 // This function tries to modify the immediate value in Hexagon::Addi
 507 // instructions, so that the immediates could then be moved into a load/store
 508 // instruction with offset and the add removed completely when we call
 509 // processAddUses
 510 //
 511 // For Example, If we have the below sequence of instructions:
 512 //
 513 //         r1 = add(r2,#1024)
 514 //               ...
 515 //         r3 = add(r2,#1152)
 516 //               ...
 517 //         r4 = add(r2,#1280)
 518 //
 519 // Where the register r2 has the same reaching definition, They get modified to
 520 // the below sequence:
 521 //
 522 //         r1 = add(r2,#1024)
 523 //              ...
 524 //         r3 = add(r1,#128)
 525 //              ...
 526 //         r4 = add(r1,#256)
 527 //
 528 //  The below change helps the processAddUses method to later move the
 529 //  immediates #128 and #256 into a load/store instruction that can take an
 530 //  offset, like the Vd = mem(Rt+#s4)
 531 bool HexagonOptAddrMode::processAddBases(NodeAddr<StmtNode *> AddSN,
 532                                          MachineInstr *AddMI) {
 533
 534   bool Changed = false;
 535
 536   LLVM_DEBUG(dbgs() << "\n\t\t[Processing Addi]: " << *AddMI << "\n");
 537
 538   auto Processed =
 539       [](const MachineInstr *MI,
 540          const DenseSet<MachineInstr *> &ProcessedAddiInsts) -> bool {
 541     // If we've already processed this Addi, just return
 542     if (ProcessedAddiInsts.find(MI) != ProcessedAddiInsts.end()) {
 543       LLVM_DEBUG(dbgs() << "\t\t\tAddi already found in ProcessedAddiInsts: "
 544                         << *MI << "\n\t\t\tSkipping...");
 545       return true;
 546     }
 547     return false;
 548   };
 549
 550   if (Processed(AddMI, ProcessedAddiInsts))
 551     return Changed;
 552   ProcessedAddiInsts.insert(AddMI);
 553
 554   // Get the base register that would be shared by other Addi Intructions
 555   Register BaseReg = AddMI->getOperand(1).getReg();
 556
 557   // Store a list of all Addi instructions that share the above common base
 558   // register
 559   std::vector<std::pair<NodeAddr<StmtNode *>, NodeAddr<UseNode *>>> AddiList;
 560
 561   NodeId UAReachingDefID;
 562   // Find the UseNode that contains the base register and it's reachingDef
 563   for (NodeAddr<UseNode *> UA : AddSN.Addr->members_if(DFG->IsUse, *DFG)) {
 564     RegisterRef URR = UA.Addr->getRegRef(*DFG);
 565     if (BaseReg != URR.Reg)
 566       continue;
 567
 568     UAReachingDefID = UA.Addr->getReachingDef();
 569     NodeAddr<DefNode *> UADef = DFG->addr<DefNode *>(UAReachingDefID);
 570     if (!UAReachingDefID || UADef.Addr->getFlags() & NodeAttrs::PhiRef) {
 571       LLVM_DEBUG(dbgs() << "\t\t\t Could not find reachingDef. Skipping...\n");
 572       return false;
 573     }
 574   }
 575
 576   NodeAddr<DefNode *> UAReachingDef = DFG->addr<DefNode *>(UAReachingDefID);
 577   NodeAddr<StmtNode *> ReachingDefStmt = UAReachingDef.Addr->getOwner(*DFG);
 578
 579   // If the reaching definition is a predicated instruction, this might not be
 580   // the only definition of our base register, so return immediately.
 581   MachineInstr *ReachingDefInstr = ReachingDefStmt.Addr->getCode();
 582   if (HII->isPredicated(*ReachingDefInstr))
 583     return false;
 584
 585   NodeList AddiUseList;
 586
 587   // Find all Addi instructions that share the same base register and add them
 588   // to the AddiList
 589   getAllRealUses(ReachingDefStmt, AddiUseList);
 590   for (auto I = AddiUseList.begin(), E = AddiUseList.end(); I != E; ++I) {
 591     NodeAddr<UseNode *> UN = *I;
 592     NodeAddr<StmtNode *> SN = UN.Addr->getOwner(*DFG);
 593     MachineInstr *MI = SN.Addr->getCode();
 594
 595     // Only add instructions if it's an Addi and it's not already processed.
 596     if (MI->getOpcode() == Hexagon::A2_addi &&
 597         !(MI != AddMI && Processed(MI, ProcessedAddiInsts))) {
 598       AddiList.push_back({SN, UN});
 599
 600       // This ensures that we process each instruction only once
 601       ProcessedAddiInsts.insert(MI);
 602     }
 603   }
 604
 605   // If there's only one Addi instruction, nothing to do here
 606   if (AddiList.size() <= 1)
 607     return Changed;
 608
 609   NodeAddr<StmtNode *> FirstReachedUseSN;
 610   // Find the first reached use of Addi instruction from the list
 611   if (!findFirstReachedInst(AddMI, AddiList, FirstReachedUseSN))
 612     return Changed;
 613
 614   // If we reach this point we know that the StmtNode FirstReachedUseSN is for
 615   // an Addi instruction. So, we're guaranteed to have just one DefNode, and
 616   // hence we can access the front() directly without checks
 617   NodeAddr<DefNode *> FirstReachedUseDN =
 618       FirstReachedUseSN.Addr->members_if(DFG->IsDef, *DFG).front();
 619
 620   MachineInstr *FirstReachedMI = FirstReachedUseSN.Addr->getCode();
 621   const MachineOperand FirstReachedMIImmOp = FirstReachedMI->getOperand(2);
 622   if (!FirstReachedMIImmOp.isImm())
 623     return false;
 624
 625   for (auto &I : AddiList) {
 626     NodeAddr<StmtNode *> CurrentInstSN = I.first;
 627     NodeAddr<UseNode *> CurrentInstUN = I.second;
 628
 629     MachineInstr *CurrentMI = CurrentInstSN.Addr->getCode();
 630     MachineOperand &CurrentMIImmOp = CurrentMI->getOperand(2);
 631
 632     int64_t NewOffset;
 633
 634     // Even though we know it's an Addi instruction, the second operand could be
 635     // a global value and not an immediate
 636     if (!CurrentMIImmOp.isImm())
 637       continue;
 638
 639     NewOffset = CurrentMIImmOp.getImm() - FirstReachedMIImmOp.getImm();
 640
 641     // This is the first occuring Addi, so skip modifying this
 642     if (CurrentMI == FirstReachedMI) {
 643       continue;
 644     }
 645
 646     if (CurrentMI->getParent() != FirstReachedMI->getParent())
 647       continue;
 648
 649     // Modify the Addi instruction only if it could be used to modify a
 650     // future load/store instruction and get removed
 651     //
 652     // This check is needed because, if we modify the current Addi instruction
 653     // we create RAW dependence between the FirstReached Addi and the current
 654     // one, which could result in extra packets. So we only do this change if
 655     // we know the current Addi would get removed later
 656     if (!usedInLoadStore(CurrentInstSN, NewOffset)) {
 657       return false;
 658     }
 659
 660     // Verify whether the First Addi's definition register is still live when
 661     // we reach the current Addi
 662     RegisterRef FirstReachedDefRR = FirstReachedUseDN.Addr->getRegRef(*DFG);
 663     NodeAddr<InstrNode *> CurrentAddiIN = CurrentInstUN.Addr->getOwner(*DFG);
 664     NodeAddr<RefNode *> NearestAA =
 665         LV->getNearestAliasedRef(FirstReachedDefRR, CurrentAddiIN);
 666     if ((DFG->IsDef(NearestAA) && NearestAA.Id != FirstReachedUseDN.Id) ||
 667         (!DFG->IsDef(NearestAA) &&
 668          NearestAA.Addr->getReachingDef() != FirstReachedUseDN.Id)) {
 669       // Found another definition of FirstReachedDef
 670       LLVM_DEBUG(dbgs() << "\t\t\tCould not modify below Addi since the first "
 671                            "defined Addi register was redefined\n");
 672       continue;
 673     }
 674
 675     MachineOperand CurrentMIBaseOp = CurrentMI->getOperand(1);
 676     if (CurrentMIBaseOp.getReg() != FirstReachedMI->getOperand(1).getReg()) {
 677       continue;
 678     }
 679
 680     // If we reached this point, then we can modify MI to use the result of
 681     // FirstReachedMI
 682     Changed |= updateAddBases(CurrentMI, FirstReachedMI, NewOffset);
 683
 684     // Update the reachingDef of the Current AddI use after change
 685     CurrentInstUN.Addr->linkToDef(CurrentInstUN.Id, FirstReachedUseDN);
 686   }
 687
 688   return Changed;
 689 }
 690
 691 bool HexagonOptAddrMode::updateAddBases(MachineInstr *CurrentMI,
 692                                         MachineInstr *FirstReachedMI,
 693                                         int64_t NewOffset) {
 694   LLVM_DEBUG(dbgs() << "[About to modify the Addi]: " << *CurrentMI << "\n");
 695   const MachineOperand FirstReachedDef = FirstReachedMI->getOperand(0);
 696   Register FirstDefRegister = FirstReachedDef.getReg();
 697
 698   MachineOperand &CurrentMIBaseOp = CurrentMI->getOperand(1);
 699   MachineOperand &CurrentMIImmOp = CurrentMI->getOperand(2);
 700
 701   CurrentMIBaseOp.setReg(FirstDefRegister);
 702   CurrentMIBaseOp.setIsUndef(FirstReachedDef.isUndef());
 703   CurrentMIBaseOp.setImplicit(FirstReachedDef.isImplicit());
 704   CurrentMIImmOp.setImm(NewOffset);
 705   ProcessedAddiInsts.insert(CurrentMI);
 706   MRI->clearKillFlags(FirstDefRegister);
 707   return true;
 708 }
 709
 710 bool HexagonOptAddrMode::processAddUses(NodeAddr<StmtNode *> AddSN,
 711                                         MachineInstr *AddMI,
 712                                         const NodeList &UNodeList) {
 713
 714   Register AddDefR = AddMI->getOperand(0).getReg();
 715   Register BaseReg = AddMI->getOperand(1).getReg();
 716   for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
 717     NodeAddr<UseNode *> UN = *I;
 718     NodeAddr<StmtNode *> SN = UN.Addr->getOwner(*DFG);
 719     MachineInstr *MI = SN.Addr->getCode();
 720     const MCInstrDesc &MID = MI->getDesc();
 721     if ((!MID.mayLoad() && !MID.mayStore()) ||
 722         HII->getAddrMode(*MI) != HexagonII::BaseImmOffset)
 723       return false;
 724
 725     MachineOperand BaseOp = MI->getOperand(getBaseOpPosition(MI));
 726
 727     if (!BaseOp.isReg() || BaseOp.getReg() != AddDefR)
 728       return false;
 729
 730     MachineOperand OffsetOp = MI->getOperand(getOffsetOpPosition(MI));
 731     if (!OffsetOp.isImm())
 732       return false;
 733
 734     int64_t newOffset = OffsetOp.getImm() + AddMI->getOperand(2).getImm();
 735     if (!isValidOffset(MI, newOffset))
 736       return false;
 737
 738     // Since we'll be extending the live range of Rt in the following example,
 739     // make sure that is safe. another definition of Rt doesn't exist between 'add'
 740     // and load/store instruction.
 741     //
 742     // Ex: Rx= add(Rt,#10)
 743     //     memw(Rx+#0) = Rs
 744     // will be replaced with =>  memw(Rt+#10) = Rs
 745     if (!isSafeToExtLR(AddSN, AddMI, BaseReg, UNodeList))
 746       return false;
 747   }
 748
 749   NodeId LRExtRegRD = 0;
 750   // Iterate through all the UseNodes in SN and find the reaching def
 751   // for the LRExtReg.
 752   for (NodeAddr<UseNode *> UA : AddSN.Addr->members_if(DFG->IsUse, *DFG)) {
 753     RegisterRef RR = UA.Addr->getRegRef(*DFG);
 754     if (BaseReg == RR.Reg)
 755       LRExtRegRD = UA.Addr->getReachingDef();
 756   }
 757
 758   // Update all the uses of 'add' with the appropriate base and offset
 759   // values.
 760   bool Changed = false;
 761   for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
 762     NodeAddr<UseNode *> UseN = *I;
 763     assert(!(UseN.Addr->getFlags() & NodeAttrs::PhiRef) &&
 764            "Found a PhiRef node as a real reached use!!");
 765
 766     NodeAddr<StmtNode *> OwnerN = UseN.Addr->getOwner(*DFG);
 767     MachineInstr *UseMI = OwnerN.Addr->getCode();
 768     LLVM_DEBUG(dbgs() << "\t\t[MI <BB#" << UseMI->getParent()->getNumber()
 769                       << ">]: " << *UseMI << "\n");
 770     Changed |= updateAddUses(AddMI, UseMI);
 771
 772     // Set the reachingDef for UseNode under consideration
 773     // after updating the Add use. This local change is
 774     // to avoid rebuilding of the RDF graph after update.
 775     NodeAddr<DefNode *> LRExtRegDN = DFG->addr<DefNode *>(LRExtRegRD);
 776     UseN.Addr->linkToDef(UseN.Id, LRExtRegDN);
 777   }
 778
 779   if (Changed)
 780     Deleted.insert(AddMI);
 781
 782   return Changed;
 783 }
 784
 785 bool HexagonOptAddrMode::updateAddUses(MachineInstr *AddMI,
 786                                        MachineInstr *UseMI) {
 787   const MachineOperand ImmOp = AddMI->getOperand(2);
 788   const MachineOperand AddRegOp = AddMI->getOperand(1);
 789   Register NewReg = AddRegOp.getReg();
 790
 791   MachineOperand &BaseOp = UseMI->getOperand(getBaseOpPosition(UseMI));
 792   MachineOperand &OffsetOp = UseMI->getOperand(getOffsetOpPosition(UseMI));
 793   BaseOp.setReg(NewReg);
 794   BaseOp.setIsUndef(AddRegOp.isUndef());
 795   BaseOp.setImplicit(AddRegOp.isImplicit());
 796   OffsetOp.setImm(ImmOp.getImm() + OffsetOp.getImm());
 797   MRI->clearKillFlags(NewReg);
 798
 799   return true;
 800 }
 801
 802 bool HexagonOptAddrMode::analyzeUses(unsigned tfrDefR,
 803                                      const NodeList &UNodeList,
 804                                      InstrEvalMap &InstrEvalResult,
 805                                      short &SizeInc) {
 806   bool KeepTfr = false;
 807   bool HasRepInstr = false;
 808   InstrEvalResult.clear();
 809
 810   for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
 811     bool CanBeReplaced = false;
 812     NodeAddr<UseNode *> UN = *I;
 813     NodeAddr<StmtNode *> SN = UN.Addr->getOwner(*DFG);
 814     MachineInstr &MI = *SN.Addr->getCode();
 815     const MCInstrDesc &MID = MI.getDesc();
 816     if ((MID.mayLoad() || MID.mayStore())) {
 817       if (!hasRepForm(MI, tfrDefR)) {
 818         KeepTfr = true;
 819         continue;
 820       }
 821       SizeInc++;
 822       CanBeReplaced = true;
 823     } else if (MI.getOpcode() == Hexagon::S2_addasl_rrri) {
 824       NodeList AddaslUseList;
 825
 826       LLVM_DEBUG(dbgs() << "\nGetting ReachedUses for === " << MI << "\n");
 827       getAllRealUses(SN, AddaslUseList);
 828       // Process phi nodes.
 829       if (allValidCandidates(SN, AddaslUseList) &&
 830           canRemoveAddasl(SN, MI, AddaslUseList)) {
 831         SizeInc += AddaslUseList.size();
 832         SizeInc -= 1; // Reduce size by 1 as addasl itself can be removed.
 833         CanBeReplaced = true;
 834       } else
 835         SizeInc++;
 836     } else
 837       // Currently, only load/store and addasl are handled.
 838       // Some other instructions to consider -
 839       // A2_add -> A2_addi
 840       // M4_mpyrr_addr -> M4_mpyrr_addi
 841       KeepTfr = true;
 842
 843     InstrEvalResult[&MI] = CanBeReplaced;
 844     HasRepInstr |= CanBeReplaced;
 845   }
 846
 847   // Reduce total size by 2 if original tfr can be deleted.
 848   if (!KeepTfr)
 849     SizeInc -= 2;
 850
 851   return HasRepInstr;
 852 }
 853
 854 bool HexagonOptAddrMode::changeLoad(MachineInstr *OldMI, MachineOperand ImmOp,
 855                                     unsigned ImmOpNum) {
 856   bool Changed = false;
 857   MachineBasicBlock *BB = OldMI->getParent();
 858   auto UsePos = MachineBasicBlock::iterator(OldMI);
 859   MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
 860   ++InsertPt;
 861   unsigned OpStart;
 862   unsigned OpEnd = OldMI->getNumOperands();
 863   MachineInstrBuilder MIB;
 864
 865   if (ImmOpNum == 1) {
 866     if (HII->getAddrMode(*OldMI) == HexagonII::BaseRegOffset) {
 867       short NewOpCode = HII->changeAddrMode_rr_ur(*OldMI);
 868       assert(NewOpCode >= 0 && "Invalid New opcode\n");
 869       MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
 870       MIB.add(OldMI->getOperand(0));
 871       MIB.add(OldMI->getOperand(2));
 872       MIB.add(OldMI->getOperand(3));
 873       MIB.add(ImmOp);
 874       OpStart = 4;
 875       Changed = true;
 876     } else if (HII->getAddrMode(*OldMI) == HexagonII::BaseImmOffset &&
 877                OldMI->getOperand(2).isImm()) {
 878       short NewOpCode = HII->changeAddrMode_io_abs(*OldMI);
 879       assert(NewOpCode >= 0 && "Invalid New opcode\n");
 880       MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode))
 881                 .add(OldMI->getOperand(0));
 882       const GlobalValue *GV = ImmOp.getGlobal();
 883       int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(2).getImm();
 884
 885       MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags());
 886       OpStart = 3;
 887       Changed = true;
 888     } else
 889       Changed = false;
 890
 891     LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
 892     LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
 893   } else if (ImmOpNum == 2) {
 894     if (OldMI->getOperand(3).isImm() && OldMI->getOperand(3).getImm() == 0) {
 895       short NewOpCode = HII->changeAddrMode_rr_io(*OldMI);
 896       assert(NewOpCode >= 0 && "Invalid New opcode\n");
 897       MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
 898       MIB.add(OldMI->getOperand(0));
 899       MIB.add(OldMI->getOperand(1));
 900       MIB.add(ImmOp);
 901       OpStart = 4;
 902       Changed = true;
 903       LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
 904       LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
 905     }
 906   }
 907
 908   if (Changed)
 909     for (unsigned i = OpStart; i < OpEnd; ++i)
 910       MIB.add(OldMI->getOperand(i));
 911
 912   return Changed;
 913 }
 914
 915 bool HexagonOptAddrMode::changeStore(MachineInstr *OldMI, MachineOperand ImmOp,
 916                                      unsigned ImmOpNum) {
 917   bool Changed = false;
 918   unsigned OpStart = 0;
 919   unsigned OpEnd = OldMI->getNumOperands();
 920   MachineBasicBlock *BB = OldMI->getParent();
 921   auto UsePos = MachineBasicBlock::iterator(OldMI);
 922   MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
 923   ++InsertPt;
 924   MachineInstrBuilder MIB;
 925   if (ImmOpNum == 0) {
 926     if (HII->getAddrMode(*OldMI) == HexagonII::BaseRegOffset) {
 927       short NewOpCode = HII->changeAddrMode_rr_ur(*OldMI);
 928       assert(NewOpCode >= 0 && "Invalid New opcode\n");
 929       MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
 930       MIB.add(OldMI->getOperand(1));
 931       MIB.add(OldMI->getOperand(2));
 932       MIB.add(ImmOp);
 933       MIB.add(OldMI->getOperand(3));
 934       OpStart = 4;
 935       Changed = true;
 936     } else if (HII->getAddrMode(*OldMI) == HexagonII::BaseImmOffset) {
 937       short NewOpCode = HII->changeAddrMode_io_abs(*OldMI);
 938       assert(NewOpCode >= 0 && "Invalid New opcode\n");
 939       MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
 940       const GlobalValue *GV = ImmOp.getGlobal();
 941       int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(1).getImm();
 942       MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags());
 943       MIB.add(OldMI->getOperand(2));
 944       OpStart = 3;
 945       Changed = true;
 946     }
 947   } else if (ImmOpNum == 1 && OldMI->getOperand(2).getImm() == 0) {
 948     short NewOpCode = HII->changeAddrMode_rr_io(*OldMI);
 949     assert(NewOpCode >= 0 && "Invalid New opcode\n");
 950     MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
 951     MIB.add(OldMI->getOperand(0));
 952     MIB.add(ImmOp);
 953     OpStart = 3;
 954     Changed = true;
 955   }
 956   if (Changed) {
 957     LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
 958     LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
 959
 960     for (unsigned i = OpStart; i < OpEnd; ++i)
 961       MIB.add(OldMI->getOperand(i));
 962   }
 963
 964   return Changed;
 965 }
 966
 967 short HexagonOptAddrMode::getBaseWithLongOffset(const MachineInstr &MI) const {
 968   if (HII->getAddrMode(MI) == HexagonII::BaseImmOffset) {
 969     short TempOpCode = HII->changeAddrMode_io_rr(MI);
 970     return HII->changeAddrMode_rr_ur(TempOpCode);
 971   }
 972   return HII->changeAddrMode_rr_ur(MI);
 973 }
 974
 975 bool HexagonOptAddrMode::changeAddAsl(NodeAddr<UseNode *> AddAslUN,
 976                                       MachineInstr *AddAslMI,
 977                                       const MachineOperand &ImmOp,
 978                                       unsigned ImmOpNum) {
 979   NodeAddr<StmtNode *> SA = AddAslUN.Addr->getOwner(*DFG);
 980
 981   LLVM_DEBUG(dbgs() << "Processing addasl :" << *AddAslMI << "\n");
 982
 983   NodeList UNodeList;
 984   getAllRealUses(SA, UNodeList);
 985
 986   for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
 987     NodeAddr<UseNode *> UseUN = *I;
 988     assert(!(UseUN.Addr->getFlags() & NodeAttrs::PhiRef) &&
 989            "Can't transform this 'AddAsl' instruction!");
 990
 991     NodeAddr<StmtNode *> UseIA = UseUN.Addr->getOwner(*DFG);
 992     LLVM_DEBUG(dbgs() << "[InstrNode]: "
 993                       << Print<NodeAddr<InstrNode *>>(UseIA, *DFG) << "\n");
 994     MachineInstr *UseMI = UseIA.Addr->getCode();
 995     LLVM_DEBUG(dbgs() << "[MI <" << printMBBReference(*UseMI->getParent())
 996                       << ">]: " << *UseMI << "\n");
 997     const MCInstrDesc &UseMID = UseMI->getDesc();
 998     assert(HII->getAddrMode(*UseMI) == HexagonII::BaseImmOffset);
 999
1000     auto UsePos = MachineBasicBlock::iterator(UseMI);
1001     MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
1002     short NewOpCode = getBaseWithLongOffset(*UseMI);
1003     assert(NewOpCode >= 0 && "Invalid New opcode\n");
1004
1005     unsigned OpStart;
1006     unsigned OpEnd = UseMI->getNumOperands();
1007
1008     MachineBasicBlock *BB = UseMI->getParent();
1009     MachineInstrBuilder MIB =
1010         BuildMI(*BB, InsertPt, UseMI->getDebugLoc(), HII->get(NewOpCode));
1011     // change mem(Rs + # ) -> mem(Rt << # + ##)
1012     if (UseMID.mayLoad()) {
1013       MIB.add(UseMI->getOperand(0));
1014       MIB.add(AddAslMI->getOperand(2));
1015       MIB.add(AddAslMI->getOperand(3));
1016       const GlobalValue *GV = ImmOp.getGlobal();
1017       MIB.addGlobalAddress(GV, UseMI->getOperand(2).getImm()+ImmOp.getOffset(),
1018                            ImmOp.getTargetFlags());
1019       OpStart = 3;
1020     } else if (UseMID.mayStore()) {
1021       MIB.add(AddAslMI->getOperand(2));
1022       MIB.add(AddAslMI->getOperand(3));
1023       const GlobalValue *GV = ImmOp.getGlobal();
1024       MIB.addGlobalAddress(GV, UseMI->getOperand(1).getImm()+ImmOp.getOffset(),
1025                            ImmOp.getTargetFlags());
1026       MIB.add(UseMI->getOperand(2));
1027       OpStart = 3;
1028     } else
1029       llvm_unreachable("Unhandled instruction");
1030
1031     for (unsigned i = OpStart; i < OpEnd; ++i)
1032       MIB.add(UseMI->getOperand(i));
1033     Deleted.insert(UseMI);
1034   }
1035
1036   return true;
1037 }
1038
1039 bool HexagonOptAddrMode::xformUseMI(MachineInstr *TfrMI, MachineInstr *UseMI,
1040                                     NodeAddr<UseNode *> UseN,
1041                                     unsigned UseMOnum) {
1042   const MachineOperand ImmOp = TfrMI->getOperand(1);
1043   const MCInstrDesc &MID = UseMI->getDesc();
1044   unsigned Changed = false;
1045   if (MID.mayLoad())
1046     Changed = changeLoad(UseMI, ImmOp, UseMOnum);
1047   else if (MID.mayStore())
1048     Changed = changeStore(UseMI, ImmOp, UseMOnum);
1049   else if (UseMI->getOpcode() == Hexagon::S2_addasl_rrri)
1050     Changed = changeAddAsl(UseN, UseMI, ImmOp, UseMOnum);
1051
1052   if (Changed)
1053     Deleted.insert(UseMI);
1054
1055   return Changed;
1056 }
1057
1058 bool HexagonOptAddrMode::processBlock(NodeAddr<BlockNode *> BA) {
1059   bool Changed = false;
1060
1061   for (auto IA : BA.Addr->members(*DFG)) {
1062     if (!DFG->IsCode<NodeAttrs::Stmt>(IA))
1063       continue;
1064
1065     NodeAddr<StmtNode *> SA = IA;
1066     MachineInstr *MI = SA.Addr->getCode();
1067     if ((MI->getOpcode() != Hexagon::A2_tfrsi ||
1068          !MI->getOperand(1).isGlobal()) &&
1069         (MI->getOpcode() != Hexagon::A2_addi ||
1070          !MI->getOperand(2).isImm() || HII->isConstExtended(*MI)))
1071     continue;
1072
1073     LLVM_DEBUG(dbgs() << "[Analyzing " << HII->getName(MI->getOpcode())
1074                       << "]: " << *MI << "\n\t[InstrNode]: "
1075                       << Print<NodeAddr<InstrNode *>>(IA, *DFG) << '\n');
1076
1077     if (MI->getOpcode() == Hexagon::A2_addi)
1078       Changed |= processAddBases(SA, MI);
1079     NodeList UNodeList;
1080     getAllRealUses(SA, UNodeList);
1081
1082     if (!allValidCandidates(SA, UNodeList))
1083       continue;
1084
1085     // Analyze all uses of 'add'. If the output of 'add' is used as an address
1086     // in the base+immediate addressing mode load/store instructions, see if
1087     // they can be updated to use the immediate value as an offet. Thus,
1088     // providing us the opportunity to eliminate 'add'.
1089     // Ex: Rx= add(Rt,#12)
1090     //     memw(Rx+#0) = Rs
1091     // This can be replaced with memw(Rt+#12) = Rs
1092     //
1093     // This transformation is only performed if all uses can be updated and
1094     // the offset isn't required to be constant extended.
1095     if (MI->getOpcode() == Hexagon::A2_addi) {
1096       Changed |= processAddUses(SA, MI, UNodeList);
1097       continue;
1098     }
1099
1100     short SizeInc = 0;
1101     Register DefR = MI->getOperand(0).getReg();
1102     InstrEvalMap InstrEvalResult;
1103
1104     // Analyze all uses and calculate increase in size. Perform the optimization
1105     // only if there is no increase in size.
1106     if (!analyzeUses(DefR, UNodeList, InstrEvalResult, SizeInc))
1107       continue;
1108     if (SizeInc > CodeGrowthLimit)
1109       continue;
1110
1111     bool KeepTfr = false;
1112
1113     LLVM_DEBUG(dbgs() << "\t[Total reached uses] : " << UNodeList.size()
1114                       << "\n");
1115     LLVM_DEBUG(dbgs() << "\t[Processing Reached Uses] ===\n");
1116     for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
1117       NodeAddr<UseNode *> UseN = *I;
1118       assert(!(UseN.Addr->getFlags() & NodeAttrs::PhiRef) &&
1119              "Found a PhiRef node as a real reached use!!");
1120
1121       NodeAddr<StmtNode *> OwnerN = UseN.Addr->getOwner(*DFG);
1122       MachineInstr *UseMI = OwnerN.Addr->getCode();
1123       LLVM_DEBUG(dbgs() << "\t\t[MI <" << printMBBReference(*UseMI->getParent())
1124                         << ">]: " << *UseMI << "\n");
1125
1126       int UseMOnum = -1;
1127       unsigned NumOperands = UseMI->getNumOperands();
1128       for (unsigned j = 0; j < NumOperands - 1; ++j) {
1129         const MachineOperand &op = UseMI->getOperand(j);
1130         if (op.isReg() && op.isUse() && DefR == op.getReg())
1131           UseMOnum = j;
1132       }
1133       // It is possible that the register will not be found in any operand.
1134       // This could happen, for example, when DefR = R4, but the used
1135       // register is D2.
1136
1137       // Change UseMI if replacement is possible. If any replacement failed,
1138       // or wasn't attempted, make sure to keep the TFR.
1139       bool Xformed = false;
1140       if (UseMOnum >= 0 && InstrEvalResult[UseMI])
1141         Xformed = xformUseMI(MI, UseMI, UseN, UseMOnum);
1142       Changed |=  Xformed;
1143       KeepTfr |= !Xformed;
1144     }
1145     if (!KeepTfr)
1146       Deleted.insert(MI);
1147   }
1148   return Changed;
1149 }
1150
1151 bool HexagonOptAddrMode::runOnMachineFunction(MachineFunction &MF) {
1152   if (skipFunction(MF.getFunction()))
1153     return false;
1154
1155   // Perform RDF optimizations only if number of basic blocks in the
1156   // function is less than the limit
1157   if (MF.size() > RDFFuncBlockLimit) {
1158     LLVM_DEBUG(dbgs() << "Skipping " << getPassName()
1159                       << ": too many basic blocks\n");
1160     return false;
1161   }
1162
1163   bool Changed = false;
1164   auto &HST = MF.getSubtarget<HexagonSubtarget>();
1165   MRI = &MF.getRegInfo();
1166   TRI = MF.getSubtarget().getRegisterInfo();
1167   HII = HST.getInstrInfo();
1168   HRI = HST.getRegisterInfo();
1169   const auto &MDF = getAnalysis<MachineDominanceFrontier>();
1170   MDT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
1171
1172   DataFlowGraph G(MF, *HII, *HRI, *MDT, MDF);
1173   // Need to keep dead phis because we can propagate uses of registers into
1174   // nodes dominated by those would-be phis.
1175   G.build(BuildOptions::KeepDeadPhis);
1176   DFG = &G;
1177
1178   Liveness L(*MRI, *DFG);
1179   L.computePhiInfo();
1180   LV = &L;
1181
1182   Deleted.clear();
1183   ProcessedAddiInsts.clear();
1184   NodeAddr<FuncNode *> FA = DFG->getFunc();
1185   LLVM_DEBUG(dbgs() << "==== [RefMap#]=====:\n "
1186                     << Print<NodeAddr<FuncNode *>>(FA, *DFG) << "\n");
1187
1188   for (NodeAddr<BlockNode *> BA : FA.Addr->members(*DFG))
1189     Changed |= processBlock(BA);
1190
1191   for (auto *MI : Deleted)
1192     MI->eraseFromParent();
1193
1194   if (Changed) {
1195     G.build();
1196     L.computeLiveIns();
1197     L.resetLiveIns();
1198     L.resetKills();
1199   }
1200
1201   return Changed;
1202 }
1203
1204 //===----------------------------------------------------------------------===//
1205 //                         Public Constructor Functions
1206 //===----------------------------------------------------------------------===//
1207
1208 FunctionPass *llvm::createHexagonOptAddrMode() {
1209   return new HexagonOptAddrMode();
1210 }