contrib/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 "RDFGraph.h"
  16 #include "RDFLiveness.h"
  17 #include "RDFRegisters.h"
  18 #include "llvm/ADT/DenseMap.h"
  19 #include "llvm/ADT/DenseSet.h"
  20 #include "llvm/ADT/StringRef.h"
  21 #include "llvm/CodeGen/MachineBasicBlock.h"
  22 #include "llvm/CodeGen/MachineDominanceFrontier.h"
  23 #include "llvm/CodeGen/MachineDominators.h"
  24 #include "llvm/CodeGen/MachineFunction.h"
  25 #include "llvm/CodeGen/MachineFunctionPass.h"
  26 #include "llvm/CodeGen/MachineInstr.h"
  27 #include "llvm/CodeGen/MachineInstrBuilder.h"
  28 #include "llvm/CodeGen/MachineOperand.h"
  29 #include "llvm/CodeGen/MachineRegisterInfo.h"
  30 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  31 #include "llvm/MC/MCInstrDesc.h"
  32 #include "llvm/Pass.h"
  33 #include "llvm/Support/CommandLine.h"
  34 #include "llvm/Support/Debug.h"
  35 #include "llvm/Support/ErrorHandling.h"
  36 #include "llvm/Support/raw_ostream.h"
  37 #include <cassert>
  38 #include <cstdint>
  39
  40 #define DEBUG_TYPE "opt-addr-mode"
  41
  42 using namespace llvm;
  43 using namespace rdf;
  44
  45 static cl::opt<int> CodeGrowthLimit("hexagon-amode-growth-limit",
  46   cl::Hidden, cl::init(0), cl::desc("Code growth limit for address mode "
  47   "optimization"));
  48
  49 namespace llvm {
  50
  51   FunctionPass *createHexagonOptAddrMode();
  52   void initializeHexagonOptAddrModePass(PassRegistry&);
  53
  54 } // end namespace llvm
  55
  56 namespace {
  57
  58 class HexagonOptAddrMode : public MachineFunctionPass {
  59 public:
  60   static char ID;
  61
  62   HexagonOptAddrMode() : MachineFunctionPass(ID) {}
  63
  64   StringRef getPassName() const override {
  65     return "Optimize addressing mode of load/store";
  66   }
  67
  68   void getAnalysisUsage(AnalysisUsage &AU) const override {
  69     MachineFunctionPass::getAnalysisUsage(AU);
  70     AU.addRequired<MachineDominatorTree>();
  71     AU.addRequired<MachineDominanceFrontier>();
  72     AU.setPreservesAll();
  73   }
  74
  75   bool runOnMachineFunction(MachineFunction &MF) override;
  76
  77 private:
  78   using MISetType = DenseSet<MachineInstr *>;
  79   using InstrEvalMap = DenseMap<MachineInstr *, bool>;
  80
  81   MachineRegisterInfo *MRI = nullptr;
  82   const HexagonInstrInfo *HII = nullptr;
  83   const HexagonRegisterInfo *HRI = nullptr;
  84   MachineDominatorTree *MDT = nullptr;
  85   DataFlowGraph *DFG = nullptr;
  86   DataFlowGraph::DefStackMap DefM;
  87   Liveness *LV = nullptr;
  88   MISetType Deleted;
  89
  90   bool processBlock(NodeAddr<BlockNode *> BA);
  91   bool xformUseMI(MachineInstr *TfrMI, MachineInstr *UseMI,
  92                   NodeAddr<UseNode *> UseN, unsigned UseMOnum);
  93   bool processAddUses(NodeAddr<StmtNode *> AddSN, MachineInstr *AddMI,
  94                       const NodeList &UNodeList);
  95   bool updateAddUses(MachineInstr *AddMI, MachineInstr *UseMI);
  96   bool analyzeUses(unsigned DefR, const NodeList &UNodeList,
  97                    InstrEvalMap &InstrEvalResult, short &SizeInc);
  98   bool hasRepForm(MachineInstr &MI, unsigned TfrDefR);
  99   bool canRemoveAddasl(NodeAddr<StmtNode *> AddAslSN, MachineInstr &MI,
 100                        const NodeList &UNodeList);
 101   bool isSafeToExtLR(NodeAddr<StmtNode *> SN, MachineInstr *MI,
 102                      unsigned LRExtReg, const NodeList &UNodeList);
 103   void getAllRealUses(NodeAddr<StmtNode *> SN, NodeList &UNodeList);
 104   bool allValidCandidates(NodeAddr<StmtNode *> SA, NodeList &UNodeList);
 105   short getBaseWithLongOffset(const MachineInstr &MI) const;
 106   bool changeStore(MachineInstr *OldMI, MachineOperand ImmOp,
 107                    unsigned ImmOpNum);
 108   bool changeLoad(MachineInstr *OldMI, MachineOperand ImmOp, unsigned ImmOpNum);
 109   bool changeAddAsl(NodeAddr<UseNode *> AddAslUN, MachineInstr *AddAslMI,
 110                     const MachineOperand &ImmOp, unsigned ImmOpNum);
 111   bool isValidOffset(MachineInstr *MI, int Offset);
 112 };
 113
 114 } // end anonymous namespace
 115
 116 char HexagonOptAddrMode::ID = 0;
 117
 118 INITIALIZE_PASS_BEGIN(HexagonOptAddrMode, "amode-opt",
 119                       "Optimize addressing mode", false, false)
 120 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 121 INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
 122 INITIALIZE_PASS_END(HexagonOptAddrMode, "amode-opt", "Optimize addressing mode",
 123                     false, false)
 124
 125 bool HexagonOptAddrMode::hasRepForm(MachineInstr &MI, unsigned TfrDefR) {
 126   const MCInstrDesc &MID = MI.getDesc();
 127
 128   if ((!MID.mayStore() && !MID.mayLoad()) || HII->isPredicated(MI))
 129     return false;
 130
 131   if (MID.mayStore()) {
 132     MachineOperand StOp = MI.getOperand(MI.getNumOperands() - 1);
 133     if (StOp.isReg() && StOp.getReg() == TfrDefR)
 134       return false;
 135   }
 136
 137   if (HII->getAddrMode(MI) == HexagonII::BaseRegOffset)
 138     // Tranform to Absolute plus register offset.
 139     return (HII->changeAddrMode_rr_ur(MI) >= 0);
 140   else if (HII->getAddrMode(MI) == HexagonII::BaseImmOffset)
 141     // Tranform to absolute addressing mode.
 142     return (HII->changeAddrMode_io_abs(MI) >= 0);
 143
 144   return false;
 145 }
 146
 147 // Check if addasl instruction can be removed. This is possible only
 148 // if it's feeding to only load/store instructions with base + register
 149 // offset as these instruction can be tranformed to use 'absolute plus
 150 // shifted register offset'.
 151 // ex:
 152 // Rs = ##foo
 153 // Rx = addasl(Rs, Rt, #2)
 154 // Rd = memw(Rx + #28)
 155 // Above three instructions can be replaced with Rd = memw(Rt<<#2 + ##foo+28)
 156
 157 bool HexagonOptAddrMode::canRemoveAddasl(NodeAddr<StmtNode *> AddAslSN,
 158                                          MachineInstr &MI,
 159                                          const NodeList &UNodeList) {
 160   // check offset size in addasl. if 'offset > 3' return false
 161   const MachineOperand &OffsetOp = MI.getOperand(3);
 162   if (!OffsetOp.isImm() || OffsetOp.getImm() > 3)
 163     return false;
 164
 165   unsigned OffsetReg = MI.getOperand(2).getReg();
 166   RegisterRef OffsetRR;
 167   NodeId OffsetRegRD = 0;
 168   for (NodeAddr<UseNode *> UA : AddAslSN.Addr->members_if(DFG->IsUse, *DFG)) {
 169     RegisterRef RR = UA.Addr->getRegRef(*DFG);
 170     if (OffsetReg == RR.Reg) {
 171       OffsetRR = RR;
 172       OffsetRegRD = UA.Addr->getReachingDef();
 173     }
 174   }
 175
 176   for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
 177     NodeAddr<UseNode *> UA = *I;
 178     NodeAddr<InstrNode *> IA = UA.Addr->getOwner(*DFG);
 179     if (UA.Addr->getFlags() & NodeAttrs::PhiRef)
 180       return false;
 181     NodeAddr<RefNode*> AA = LV->getNearestAliasedRef(OffsetRR, IA);
 182     if ((DFG->IsDef(AA) && AA.Id != OffsetRegRD) ||
 183          AA.Addr->getReachingDef() != OffsetRegRD)
 184       return false;
 185
 186     MachineInstr &UseMI = *NodeAddr<StmtNode *>(IA).Addr->getCode();
 187     NodeAddr<DefNode *> OffsetRegDN = DFG->addr<DefNode *>(OffsetRegRD);
 188     // Reaching Def to an offset register can't be a phi.
 189     if ((OffsetRegDN.Addr->getFlags() & NodeAttrs::PhiRef) &&
 190         MI.getParent() != UseMI.getParent())
 191     return false;
 192
 193     const MCInstrDesc &UseMID = UseMI.getDesc();
 194     if ((!UseMID.mayLoad() && !UseMID.mayStore()) ||
 195         HII->getAddrMode(UseMI) != HexagonII::BaseImmOffset ||
 196         getBaseWithLongOffset(UseMI) < 0)
 197       return false;
 198
 199     // Addasl output can't be a store value.
 200     if (UseMID.mayStore() && UseMI.getOperand(2).isReg() &&
 201         UseMI.getOperand(2).getReg() == MI.getOperand(0).getReg())
 202       return false;
 203
 204     for (auto &Mo : UseMI.operands())
 205       if (Mo.isFI())
 206         return false;
 207   }
 208   return true;
 209 }
 210
 211 bool HexagonOptAddrMode::allValidCandidates(NodeAddr<StmtNode *> SA,
 212                                             NodeList &UNodeList) {
 213   for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
 214     NodeAddr<UseNode *> UN = *I;
 215     RegisterRef UR = UN.Addr->getRegRef(*DFG);
 216     NodeSet Visited, Defs;
 217     const auto &P = LV->getAllReachingDefsRec(UR, UN, Visited, Defs);
 218     if (!P.second) {
 219       LLVM_DEBUG({
 220         dbgs() << "*** Unable to collect all reaching defs for use ***\n"
 221                << PrintNode<UseNode*>(UN, *DFG) << '\n'
 222                << "The program's complexity may exceed the limits.\n";
 223       });
 224       return false;
 225     }
 226     const auto &ReachingDefs = P.first;
 227     if (ReachingDefs.size() > 1) {
 228       LLVM_DEBUG({
 229         dbgs() << "*** Multiple Reaching Defs found!!! ***\n";
 230         for (auto DI : ReachingDefs) {
 231           NodeAddr<UseNode *> DA = DFG->addr<UseNode *>(DI);
 232           NodeAddr<StmtNode *> TempIA = DA.Addr->getOwner(*DFG);
 233           dbgs() << "\t\t[Reaching Def]: "
 234                  << Print<NodeAddr<InstrNode *>>(TempIA, *DFG) << "\n";
 235         }
 236       });
 237       return false;
 238     }
 239   }
 240   return true;
 241 }
 242
 243 void HexagonOptAddrMode::getAllRealUses(NodeAddr<StmtNode *> SA,
 244                                         NodeList &UNodeList) {
 245   for (NodeAddr<DefNode *> DA : SA.Addr->members_if(DFG->IsDef, *DFG)) {
 246     LLVM_DEBUG(dbgs() << "\t\t[DefNode]: "
 247                       << Print<NodeAddr<DefNode *>>(DA, *DFG) << "\n");
 248     RegisterRef DR = DFG->getPRI().normalize(DA.Addr->getRegRef(*DFG));
 249
 250     auto UseSet = LV->getAllReachedUses(DR, DA);
 251
 252     for (auto UI : UseSet) {
 253       NodeAddr<UseNode *> UA = DFG->addr<UseNode *>(UI);
 254       LLVM_DEBUG({
 255         NodeAddr<StmtNode *> TempIA = UA.Addr->getOwner(*DFG);
 256         dbgs() << "\t\t\t[Reached Use]: "
 257                << Print<NodeAddr<InstrNode *>>(TempIA, *DFG) << "\n";
 258       });
 259
 260       if (UA.Addr->getFlags() & NodeAttrs::PhiRef) {
 261         NodeAddr<PhiNode *> PA = UA.Addr->getOwner(*DFG);
 262         NodeId id = PA.Id;
 263         const Liveness::RefMap &phiUse = LV->getRealUses(id);
 264         LLVM_DEBUG(dbgs() << "\t\t\t\tphi real Uses"
 265                           << Print<Liveness::RefMap>(phiUse, *DFG) << "\n");
 266         if (!phiUse.empty()) {
 267           for (auto I : phiUse) {
 268             if (!DFG->getPRI().alias(RegisterRef(I.first), DR))
 269               continue;
 270             auto phiUseSet = I.second;
 271             for (auto phiUI : phiUseSet) {
 272               NodeAddr<UseNode *> phiUA = DFG->addr<UseNode *>(phiUI.first);
 273               UNodeList.push_back(phiUA);
 274             }
 275           }
 276         }
 277       } else
 278         UNodeList.push_back(UA);
 279     }
 280   }
 281 }
 282
 283 bool HexagonOptAddrMode::isSafeToExtLR(NodeAddr<StmtNode *> SN,
 284                                        MachineInstr *MI, unsigned LRExtReg,
 285                                        const NodeList &UNodeList) {
 286   RegisterRef LRExtRR;
 287   NodeId LRExtRegRD = 0;
 288   // Iterate through all the UseNodes in SN and find the reaching def
 289   // for the LRExtReg.
 290   for (NodeAddr<UseNode *> UA : SN.Addr->members_if(DFG->IsUse, *DFG)) {
 291     RegisterRef RR = UA.Addr->getRegRef(*DFG);
 292     if (LRExtReg == RR.Reg) {
 293       LRExtRR = RR;
 294       LRExtRegRD = UA.Addr->getReachingDef();
 295     }
 296   }
 297
 298   for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
 299     NodeAddr<UseNode *> UA = *I;
 300     NodeAddr<InstrNode *> IA = UA.Addr->getOwner(*DFG);
 301     // The reaching def of LRExtRR at load/store node should be same as the
 302     // one reaching at the SN.
 303     if (UA.Addr->getFlags() & NodeAttrs::PhiRef)
 304       return false;
 305     NodeAddr<RefNode*> AA = LV->getNearestAliasedRef(LRExtRR, IA);
 306     if ((DFG->IsDef(AA) && AA.Id != LRExtRegRD) ||
 307         AA.Addr->getReachingDef() != LRExtRegRD) {
 308       LLVM_DEBUG(
 309           dbgs() << "isSafeToExtLR: Returning false; another reaching def\n");
 310       return false;
 311     }
 312
 313     MachineInstr *UseMI = NodeAddr<StmtNode *>(IA).Addr->getCode();
 314     NodeAddr<DefNode *> LRExtRegDN = DFG->addr<DefNode *>(LRExtRegRD);
 315     // Reaching Def to LRExtReg can't be a phi.
 316     if ((LRExtRegDN.Addr->getFlags() & NodeAttrs::PhiRef) &&
 317         MI->getParent() != UseMI->getParent())
 318     return false;
 319   }
 320   return true;
 321 }
 322
 323 bool HexagonOptAddrMode::isValidOffset(MachineInstr *MI, int Offset) {
 324   unsigned AlignMask = 0;
 325   switch (HII->getMemAccessSize(*MI)) {
 326   case HexagonII::MemAccessSize::DoubleWordAccess:
 327     AlignMask = 0x7;
 328     break;
 329   case HexagonII::MemAccessSize::WordAccess:
 330     AlignMask = 0x3;
 331     break;
 332   case HexagonII::MemAccessSize::HalfWordAccess:
 333     AlignMask = 0x1;
 334     break;
 335   case HexagonII::MemAccessSize::ByteAccess:
 336     AlignMask = 0x0;
 337     break;
 338   default:
 339     return false;
 340   }
 341
 342   if ((AlignMask & Offset) != 0)
 343     return false;
 344   return HII->isValidOffset(MI->getOpcode(), Offset, HRI, false);
 345 }
 346
 347 bool HexagonOptAddrMode::processAddUses(NodeAddr<StmtNode *> AddSN,
 348                                         MachineInstr *AddMI,
 349                                         const NodeList &UNodeList) {
 350
 351   unsigned AddDefR = AddMI->getOperand(0).getReg();
 352   for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
 353     NodeAddr<UseNode *> UN = *I;
 354     NodeAddr<StmtNode *> SN = UN.Addr->getOwner(*DFG);
 355     MachineInstr *MI = SN.Addr->getCode();
 356     const MCInstrDesc &MID = MI->getDesc();
 357     if ((!MID.mayLoad() && !MID.mayStore()) ||
 358         HII->getAddrMode(*MI) != HexagonII::BaseImmOffset ||
 359         HII->isHVXVec(*MI))
 360       return false;
 361
 362     MachineOperand BaseOp = MID.mayLoad() ? MI->getOperand(1)
 363                                           : MI->getOperand(0);
 364
 365     if (!BaseOp.isReg() || BaseOp.getReg() != AddDefR)
 366       return false;
 367
 368     MachineOperand OffsetOp = MID.mayLoad() ? MI->getOperand(2)
 369                                             : MI->getOperand(1);
 370     if (!OffsetOp.isImm())
 371       return false;
 372
 373     int64_t newOffset = OffsetOp.getImm() + AddMI->getOperand(2).getImm();
 374     if (!isValidOffset(MI, newOffset))
 375       return false;
 376
 377     // Since we'll be extending the live range of Rt in the following example,
 378     // make sure that is safe. another definition of Rt doesn't exist between 'add'
 379     // and load/store instruction.
 380     //
 381     // Ex: Rx= add(Rt,#10)
 382     //     memw(Rx+#0) = Rs
 383     // will be replaced with =>  memw(Rt+#10) = Rs
 384     unsigned BaseReg = AddMI->getOperand(1).getReg();
 385     if (!isSafeToExtLR(AddSN, AddMI, BaseReg, UNodeList))
 386       return false;
 387   }
 388
 389   // Update all the uses of 'add' with the appropriate base and offset
 390   // values.
 391   bool Changed = false;
 392   for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
 393     NodeAddr<UseNode *> UseN = *I;
 394     assert(!(UseN.Addr->getFlags() & NodeAttrs::PhiRef) &&
 395            "Found a PhiRef node as a real reached use!!");
 396
 397     NodeAddr<StmtNode *> OwnerN = UseN.Addr->getOwner(*DFG);
 398     MachineInstr *UseMI = OwnerN.Addr->getCode();
 399     LLVM_DEBUG(dbgs() << "\t\t[MI <BB#" << UseMI->getParent()->getNumber()
 400                       << ">]: " << *UseMI << "\n");
 401     Changed |= updateAddUses(AddMI, UseMI);
 402   }
 403
 404   if (Changed)
 405     Deleted.insert(AddMI);
 406
 407   return Changed;
 408 }
 409
 410 bool HexagonOptAddrMode::updateAddUses(MachineInstr *AddMI,
 411                                         MachineInstr *UseMI) {
 412   const MachineOperand ImmOp = AddMI->getOperand(2);
 413   const MachineOperand AddRegOp = AddMI->getOperand(1);
 414   unsigned newReg = AddRegOp.getReg();
 415   const MCInstrDesc &MID = UseMI->getDesc();
 416
 417   MachineOperand &BaseOp = MID.mayLoad() ? UseMI->getOperand(1)
 418                                          : UseMI->getOperand(0);
 419   MachineOperand &OffsetOp = MID.mayLoad() ? UseMI->getOperand(2)
 420                                            : UseMI->getOperand(1);
 421   BaseOp.setReg(newReg);
 422   BaseOp.setIsUndef(AddRegOp.isUndef());
 423   BaseOp.setImplicit(AddRegOp.isImplicit());
 424   OffsetOp.setImm(ImmOp.getImm() + OffsetOp.getImm());
 425   MRI->clearKillFlags(newReg);
 426
 427   return true;
 428 }
 429
 430 bool HexagonOptAddrMode::analyzeUses(unsigned tfrDefR,
 431                                      const NodeList &UNodeList,
 432                                      InstrEvalMap &InstrEvalResult,
 433                                      short &SizeInc) {
 434   bool KeepTfr = false;
 435   bool HasRepInstr = false;
 436   InstrEvalResult.clear();
 437
 438   for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
 439     bool CanBeReplaced = false;
 440     NodeAddr<UseNode *> UN = *I;
 441     NodeAddr<StmtNode *> SN = UN.Addr->getOwner(*DFG);
 442     MachineInstr &MI = *SN.Addr->getCode();
 443     const MCInstrDesc &MID = MI.getDesc();
 444     if ((MID.mayLoad() || MID.mayStore())) {
 445       if (!hasRepForm(MI, tfrDefR)) {
 446         KeepTfr = true;
 447         continue;
 448       }
 449       SizeInc++;
 450       CanBeReplaced = true;
 451     } else if (MI.getOpcode() == Hexagon::S2_addasl_rrri) {
 452       NodeList AddaslUseList;
 453
 454       LLVM_DEBUG(dbgs() << "\nGetting ReachedUses for === " << MI << "\n");
 455       getAllRealUses(SN, AddaslUseList);
 456       // Process phi nodes.
 457       if (allValidCandidates(SN, AddaslUseList) &&
 458           canRemoveAddasl(SN, MI, AddaslUseList)) {
 459         SizeInc += AddaslUseList.size();
 460         SizeInc -= 1; // Reduce size by 1 as addasl itself can be removed.
 461         CanBeReplaced = true;
 462       } else
 463         SizeInc++;
 464     } else
 465       // Currently, only load/store and addasl are handled.
 466       // Some other instructions to consider -
 467       // A2_add -> A2_addi
 468       // M4_mpyrr_addr -> M4_mpyrr_addi
 469       KeepTfr = true;
 470
 471     InstrEvalResult[&MI] = CanBeReplaced;
 472     HasRepInstr |= CanBeReplaced;
 473   }
 474
 475   // Reduce total size by 2 if original tfr can be deleted.
 476   if (!KeepTfr)
 477     SizeInc -= 2;
 478
 479   return HasRepInstr;
 480 }
 481
 482 bool HexagonOptAddrMode::changeLoad(MachineInstr *OldMI, MachineOperand ImmOp,
 483                                     unsigned ImmOpNum) {
 484   bool Changed = false;
 485   MachineBasicBlock *BB = OldMI->getParent();
 486   auto UsePos = MachineBasicBlock::iterator(OldMI);
 487   MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
 488   ++InsertPt;
 489   unsigned OpStart;
 490   unsigned OpEnd = OldMI->getNumOperands();
 491   MachineInstrBuilder MIB;
 492
 493   if (ImmOpNum == 1) {
 494     if (HII->getAddrMode(*OldMI) == HexagonII::BaseRegOffset) {
 495       short NewOpCode = HII->changeAddrMode_rr_ur(*OldMI);
 496       assert(NewOpCode >= 0 && "Invalid New opcode\n");
 497       MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
 498       MIB.add(OldMI->getOperand(0));
 499       MIB.add(OldMI->getOperand(2));
 500       MIB.add(OldMI->getOperand(3));
 501       MIB.add(ImmOp);
 502       OpStart = 4;
 503       Changed = true;
 504     } else if (HII->getAddrMode(*OldMI) == HexagonII::BaseImmOffset &&
 505                OldMI->getOperand(2).isImm()) {
 506       short NewOpCode = HII->changeAddrMode_io_abs(*OldMI);
 507       assert(NewOpCode >= 0 && "Invalid New opcode\n");
 508       MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode))
 509                 .add(OldMI->getOperand(0));
 510       const GlobalValue *GV = ImmOp.getGlobal();
 511       int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(2).getImm();
 512
 513       MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags());
 514       OpStart = 3;
 515       Changed = true;
 516     } else
 517       Changed = false;
 518
 519     LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
 520     LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
 521   } else if (ImmOpNum == 2) {
 522     if (OldMI->getOperand(3).isImm() && OldMI->getOperand(3).getImm() == 0) {
 523       short NewOpCode = HII->changeAddrMode_rr_io(*OldMI);
 524       assert(NewOpCode >= 0 && "Invalid New opcode\n");
 525       MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
 526       MIB.add(OldMI->getOperand(0));
 527       MIB.add(OldMI->getOperand(1));
 528       MIB.add(ImmOp);
 529       OpStart = 4;
 530       Changed = true;
 531       LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
 532       LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
 533     }
 534   }
 535
 536   if (Changed)
 537     for (unsigned i = OpStart; i < OpEnd; ++i)
 538       MIB.add(OldMI->getOperand(i));
 539
 540   return Changed;
 541 }
 542
 543 bool HexagonOptAddrMode::changeStore(MachineInstr *OldMI, MachineOperand ImmOp,
 544                                      unsigned ImmOpNum) {
 545   bool Changed = false;
 546   unsigned OpStart;
 547   unsigned OpEnd = OldMI->getNumOperands();
 548   MachineBasicBlock *BB = OldMI->getParent();
 549   auto UsePos = MachineBasicBlock::iterator(OldMI);
 550   MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
 551   ++InsertPt;
 552   MachineInstrBuilder MIB;
 553   if (ImmOpNum == 0) {
 554     if (HII->getAddrMode(*OldMI) == HexagonII::BaseRegOffset) {
 555       short NewOpCode = HII->changeAddrMode_rr_ur(*OldMI);
 556       assert(NewOpCode >= 0 && "Invalid New opcode\n");
 557       MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
 558       MIB.add(OldMI->getOperand(1));
 559       MIB.add(OldMI->getOperand(2));
 560       MIB.add(ImmOp);
 561       MIB.add(OldMI->getOperand(3));
 562       OpStart = 4;
 563     } else if (HII->getAddrMode(*OldMI) == HexagonII::BaseImmOffset) {
 564       short NewOpCode = HII->changeAddrMode_io_abs(*OldMI);
 565       assert(NewOpCode >= 0 && "Invalid New opcode\n");
 566       MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
 567       const GlobalValue *GV = ImmOp.getGlobal();
 568       int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(1).getImm();
 569       MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags());
 570       MIB.add(OldMI->getOperand(2));
 571       OpStart = 3;
 572     }
 573     Changed = true;
 574     LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
 575     LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
 576   } else if (ImmOpNum == 1 && OldMI->getOperand(2).getImm() == 0) {
 577     short NewOpCode = HII->changeAddrMode_rr_io(*OldMI);
 578     assert(NewOpCode >= 0 && "Invalid New opcode\n");
 579     MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
 580     MIB.add(OldMI->getOperand(0));
 581     MIB.add(ImmOp);
 582     OpStart = 3;
 583     Changed = true;
 584     LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
 585     LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
 586   }
 587   if (Changed)
 588     for (unsigned i = OpStart; i < OpEnd; ++i)
 589       MIB.add(OldMI->getOperand(i));
 590
 591   return Changed;
 592 }
 593
 594 short HexagonOptAddrMode::getBaseWithLongOffset(const MachineInstr &MI) const {
 595   if (HII->getAddrMode(MI) == HexagonII::BaseImmOffset) {
 596     short TempOpCode = HII->changeAddrMode_io_rr(MI);
 597     return HII->changeAddrMode_rr_ur(TempOpCode);
 598   }
 599   return HII->changeAddrMode_rr_ur(MI);
 600 }
 601
 602 bool HexagonOptAddrMode::changeAddAsl(NodeAddr<UseNode *> AddAslUN,
 603                                       MachineInstr *AddAslMI,
 604                                       const MachineOperand &ImmOp,
 605                                       unsigned ImmOpNum) {
 606   NodeAddr<StmtNode *> SA = AddAslUN.Addr->getOwner(*DFG);
 607
 608   LLVM_DEBUG(dbgs() << "Processing addasl :" << *AddAslMI << "\n");
 609
 610   NodeList UNodeList;
 611   getAllRealUses(SA, UNodeList);
 612
 613   for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
 614     NodeAddr<UseNode *> UseUN = *I;
 615     assert(!(UseUN.Addr->getFlags() & NodeAttrs::PhiRef) &&
 616            "Can't transform this 'AddAsl' instruction!");
 617
 618     NodeAddr<StmtNode *> UseIA = UseUN.Addr->getOwner(*DFG);
 619     LLVM_DEBUG(dbgs() << "[InstrNode]: "
 620                       << Print<NodeAddr<InstrNode *>>(UseIA, *DFG) << "\n");
 621     MachineInstr *UseMI = UseIA.Addr->getCode();
 622     LLVM_DEBUG(dbgs() << "[MI <" << printMBBReference(*UseMI->getParent())
 623                       << ">]: " << *UseMI << "\n");
 624     const MCInstrDesc &UseMID = UseMI->getDesc();
 625     assert(HII->getAddrMode(*UseMI) == HexagonII::BaseImmOffset);
 626
 627     auto UsePos = MachineBasicBlock::iterator(UseMI);
 628     MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
 629     short NewOpCode = getBaseWithLongOffset(*UseMI);
 630     assert(NewOpCode >= 0 && "Invalid New opcode\n");
 631
 632     unsigned OpStart;
 633     unsigned OpEnd = UseMI->getNumOperands();
 634
 635     MachineBasicBlock *BB = UseMI->getParent();
 636     MachineInstrBuilder MIB =
 637         BuildMI(*BB, InsertPt, UseMI->getDebugLoc(), HII->get(NewOpCode));
 638     // change mem(Rs + # ) -> mem(Rt << # + ##)
 639     if (UseMID.mayLoad()) {
 640       MIB.add(UseMI->getOperand(0));
 641       MIB.add(AddAslMI->getOperand(2));
 642       MIB.add(AddAslMI->getOperand(3));
 643       const GlobalValue *GV = ImmOp.getGlobal();
 644       MIB.addGlobalAddress(GV, UseMI->getOperand(2).getImm()+ImmOp.getOffset(),
 645                            ImmOp.getTargetFlags());
 646       OpStart = 3;
 647     } else if (UseMID.mayStore()) {
 648       MIB.add(AddAslMI->getOperand(2));
 649       MIB.add(AddAslMI->getOperand(3));
 650       const GlobalValue *GV = ImmOp.getGlobal();
 651       MIB.addGlobalAddress(GV, UseMI->getOperand(1).getImm()+ImmOp.getOffset(),
 652                            ImmOp.getTargetFlags());
 653       MIB.add(UseMI->getOperand(2));
 654       OpStart = 3;
 655     } else
 656       llvm_unreachable("Unhandled instruction");
 657
 658     for (unsigned i = OpStart; i < OpEnd; ++i)
 659       MIB.add(UseMI->getOperand(i));
 660
 661     Deleted.insert(UseMI);
 662   }
 663
 664   return true;
 665 }
 666
 667 bool HexagonOptAddrMode::xformUseMI(MachineInstr *TfrMI, MachineInstr *UseMI,
 668                                     NodeAddr<UseNode *> UseN,
 669                                     unsigned UseMOnum) {
 670   const MachineOperand ImmOp = TfrMI->getOperand(1);
 671   const MCInstrDesc &MID = UseMI->getDesc();
 672   unsigned Changed = false;
 673   if (MID.mayLoad())
 674     Changed = changeLoad(UseMI, ImmOp, UseMOnum);
 675   else if (MID.mayStore())
 676     Changed = changeStore(UseMI, ImmOp, UseMOnum);
 677   else if (UseMI->getOpcode() == Hexagon::S2_addasl_rrri)
 678     Changed = changeAddAsl(UseN, UseMI, ImmOp, UseMOnum);
 679
 680   if (Changed)
 681     Deleted.insert(UseMI);
 682
 683   return Changed;
 684 }
 685
 686 bool HexagonOptAddrMode::processBlock(NodeAddr<BlockNode *> BA) {
 687   bool Changed = false;
 688
 689   for (auto IA : BA.Addr->members(*DFG)) {
 690     if (!DFG->IsCode<NodeAttrs::Stmt>(IA))
 691       continue;
 692
 693     NodeAddr<StmtNode *> SA = IA;
 694     MachineInstr *MI = SA.Addr->getCode();
 695     if ((MI->getOpcode() != Hexagon::A2_tfrsi ||
 696          !MI->getOperand(1).isGlobal()) &&
 697         (MI->getOpcode() != Hexagon::A2_addi ||
 698          !MI->getOperand(2).isImm() || HII->isConstExtended(*MI)))
 699     continue;
 700
 701     LLVM_DEBUG(dbgs() << "[Analyzing " << HII->getName(MI->getOpcode())
 702                       << "]: " << *MI << "\n\t[InstrNode]: "
 703                       << Print<NodeAddr<InstrNode *>>(IA, *DFG) << '\n');
 704
 705     NodeList UNodeList;
 706     getAllRealUses(SA, UNodeList);
 707
 708     if (!allValidCandidates(SA, UNodeList))
 709       continue;
 710
 711     // Analyze all uses of 'add'. If the output of 'add' is used as an address
 712     // in the base+immediate addressing mode load/store instructions, see if
 713     // they can be updated to use the immediate value as an offet. Thus,
 714     // providing us the opportunity to eliminate 'add'.
 715     // Ex: Rx= add(Rt,#12)
 716     //     memw(Rx+#0) = Rs
 717     // This can be replaced with memw(Rt+#12) = Rs
 718     //
 719     // This transformation is only performed if all uses can be updated and
 720     // the offset isn't required to be constant extended.
 721     if (MI->getOpcode() == Hexagon::A2_addi) {
 722       Changed |= processAddUses(SA, MI, UNodeList);
 723       continue;
 724     }
 725
 726     short SizeInc = 0;
 727     unsigned DefR = MI->getOperand(0).getReg();
 728     InstrEvalMap InstrEvalResult;
 729
 730     // Analyze all uses and calculate increase in size. Perform the optimization
 731     // only if there is no increase in size.
 732     if (!analyzeUses(DefR, UNodeList, InstrEvalResult, SizeInc))
 733       continue;
 734     if (SizeInc > CodeGrowthLimit)
 735       continue;
 736
 737     bool KeepTfr = false;
 738
 739     LLVM_DEBUG(dbgs() << "\t[Total reached uses] : " << UNodeList.size()
 740                       << "\n");
 741     LLVM_DEBUG(dbgs() << "\t[Processing Reached Uses] ===\n");
 742     for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
 743       NodeAddr<UseNode *> UseN = *I;
 744       assert(!(UseN.Addr->getFlags() & NodeAttrs::PhiRef) &&
 745              "Found a PhiRef node as a real reached use!!");
 746
 747       NodeAddr<StmtNode *> OwnerN = UseN.Addr->getOwner(*DFG);
 748       MachineInstr *UseMI = OwnerN.Addr->getCode();
 749       LLVM_DEBUG(dbgs() << "\t\t[MI <" << printMBBReference(*UseMI->getParent())
 750                         << ">]: " << *UseMI << "\n");
 751
 752       int UseMOnum = -1;
 753       unsigned NumOperands = UseMI->getNumOperands();
 754       for (unsigned j = 0; j < NumOperands - 1; ++j) {
 755         const MachineOperand &op = UseMI->getOperand(j);
 756         if (op.isReg() && op.isUse() && DefR == op.getReg())
 757           UseMOnum = j;
 758       }
 759       // It is possible that the register will not be found in any operand.
 760       // This could happen, for example, when DefR = R4, but the used
 761       // register is D2.
 762
 763       // Change UseMI if replacement is possible. If any replacement failed,
 764       // or wasn't attempted, make sure to keep the TFR.
 765       bool Xformed = false;
 766       if (UseMOnum >= 0 && InstrEvalResult[UseMI])
 767         Xformed = xformUseMI(MI, UseMI, UseN, UseMOnum);
 768       Changed |=  Xformed;
 769       KeepTfr |= !Xformed;
 770     }
 771     if (!KeepTfr)
 772       Deleted.insert(MI);
 773   }
 774   return Changed;
 775 }
 776
 777 bool HexagonOptAddrMode::runOnMachineFunction(MachineFunction &MF) {
 778   if (skipFunction(MF.getFunction()))
 779     return false;
 780
 781   bool Changed = false;
 782   auto &HST = MF.getSubtarget<HexagonSubtarget>();
 783   MRI = &MF.getRegInfo();
 784   HII = HST.getInstrInfo();
 785   HRI = HST.getRegisterInfo();
 786   const auto &MDF = getAnalysis<MachineDominanceFrontier>();
 787   MDT = &getAnalysis<MachineDominatorTree>();
 788   const TargetOperandInfo TOI(*HII);
 789
 790   DataFlowGraph G(MF, *HII, *HRI, *MDT, MDF, TOI);
 791   // Need to keep dead phis because we can propagate uses of registers into
 792   // nodes dominated by those would-be phis.
 793   G.build(BuildOptions::KeepDeadPhis);
 794   DFG = &G;
 795
 796   Liveness L(*MRI, *DFG);
 797   L.computePhiInfo();
 798   LV = &L;
 799
 800   Deleted.clear();
 801   NodeAddr<FuncNode *> FA = DFG->getFunc();
 802   LLVM_DEBUG(dbgs() << "==== [RefMap#]=====:\n "
 803                     << Print<NodeAddr<FuncNode *>>(FA, *DFG) << "\n");
 804
 805   for (NodeAddr<BlockNode *> BA : FA.Addr->members(*DFG))
 806     Changed |= processBlock(BA);
 807
 808   for (auto MI : Deleted)
 809     MI->eraseFromParent();
 810
 811   if (Changed) {
 812     G.build();
 813     L.computeLiveIns();
 814     L.resetLiveIns();
 815     L.resetKills();
 816   }
 817
 818   return Changed;
 819 }
 820
 821 //===----------------------------------------------------------------------===//
 822 //                         Public Constructor Functions
 823 //===----------------------------------------------------------------------===//
 824
 825 FunctionPass *llvm::createHexagonOptAddrMode() {
 826   return new HexagonOptAddrMode();
 827 }