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