contrib/llvm/lib/Target/Hexagon/HexagonOptAddrMode.cpp

   1 //===- HexagonOptAddrMode.cpp ---------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 // This implements a Hexagon-specific pass to optimize addressing mode for
  10 // load/store instructions.
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "HexagonInstrInfo.h"
  14 #include "HexagonSubtarget.h"
  15 #include "MCTargetDesc/HexagonBaseInfo.h"
  16 #include "RDFGraph.h"
  17 #include "RDFLiveness.h"
  18 #include "RDFRegisters.h"
  19 #include "llvm/ADT/DenseMap.h"
  20 #include "llvm/ADT/DenseSet.h"
  21 #include "llvm/ADT/StringRef.h"
  22 #include "llvm/CodeGen/MachineBasicBlock.h"
  23 #include "llvm/CodeGen/MachineDominanceFrontier.h"
  24 #include "llvm/CodeGen/MachineDominators.h"
  25 #include "llvm/CodeGen/MachineFunction.h"
  26 #include "llvm/CodeGen/MachineFunctionPass.h"
  27 #include "llvm/CodeGen/MachineInstr.h"
  28 #include "llvm/CodeGen/MachineInstrBuilder.h"
  29 #include "llvm/CodeGen/MachineOperand.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   const HexagonInstrInfo *HII = nullptr;
  82   MachineDominatorTree *MDT = nullptr;
  83   DataFlowGraph *DFG = nullptr;
  84   DataFlowGraph::DefStackMap DefM;
  85   Liveness *LV = nullptr;
  86   MISetType Deleted;
  87
  88   bool processBlock(NodeAddr<BlockNode *> BA);
  89   bool xformUseMI(MachineInstr *TfrMI, MachineInstr *UseMI,
  90                   NodeAddr<UseNode *> UseN, unsigned UseMOnum);
  91   bool analyzeUses(unsigned DefR, const NodeList &UNodeList,
  92                    InstrEvalMap &InstrEvalResult, short &SizeInc);
  93   bool hasRepForm(MachineInstr &MI, unsigned TfrDefR);
  94   bool canRemoveAddasl(NodeAddr<StmtNode *> AddAslSN, MachineInstr &MI,
  95                        const NodeList &UNodeList);
  96   void getAllRealUses(NodeAddr<StmtNode *> SN, NodeList &UNodeList);
  97   bool allValidCandidates(NodeAddr<StmtNode *> SA, NodeList &UNodeList);
  98   short getBaseWithLongOffset(const MachineInstr &MI) const;
  99   bool changeStore(MachineInstr *OldMI, MachineOperand ImmOp,
 100                    unsigned ImmOpNum);
 101   bool changeLoad(MachineInstr *OldMI, MachineOperand ImmOp, unsigned ImmOpNum);
 102   bool changeAddAsl(NodeAddr<UseNode *> AddAslUN, MachineInstr *AddAslMI,
 103                     const MachineOperand &ImmOp, unsigned ImmOpNum);
 104 };
 105
 106 } // end anonymous namespace
 107
 108 char HexagonOptAddrMode::ID = 0;
 109
 110 INITIALIZE_PASS_BEGIN(HexagonOptAddrMode, "amode-opt",
 111                       "Optimize addressing mode", false, false)
 112 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 113 INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
 114 INITIALIZE_PASS_END(HexagonOptAddrMode, "amode-opt", "Optimize addressing mode",
 115                     false, false)
 116
 117 bool HexagonOptAddrMode::hasRepForm(MachineInstr &MI, unsigned TfrDefR) {
 118   const MCInstrDesc &MID = MI.getDesc();
 119
 120   if ((!MID.mayStore() && !MID.mayLoad()) || HII->isPredicated(MI))
 121     return false;
 122
 123   if (MID.mayStore()) {
 124     MachineOperand StOp = MI.getOperand(MI.getNumOperands() - 1);
 125     if (StOp.isReg() && StOp.getReg() == TfrDefR)
 126       return false;
 127   }
 128
 129   if (HII->getAddrMode(MI) == HexagonII::BaseRegOffset)
 130     // Tranform to Absolute plus register offset.
 131     return (HII->changeAddrMode_rr_ur(MI) >= 0);
 132   else if (HII->getAddrMode(MI) == HexagonII::BaseImmOffset)
 133     // Tranform to absolute addressing mode.
 134     return (HII->changeAddrMode_io_abs(MI) >= 0);
 135
 136   return false;
 137 }
 138
 139 // Check if addasl instruction can be removed. This is possible only
 140 // if it's feeding to only load/store instructions with base + register
 141 // offset as these instruction can be tranformed to use 'absolute plus
 142 // shifted register offset'.
 143 // ex:
 144 // Rs = ##foo
 145 // Rx = addasl(Rs, Rt, #2)
 146 // Rd = memw(Rx + #28)
 147 // Above three instructions can be replaced with Rd = memw(Rt<<#2 + ##foo+28)
 148
 149 bool HexagonOptAddrMode::canRemoveAddasl(NodeAddr<StmtNode *> AddAslSN,
 150                                          MachineInstr &MI,
 151                                          const NodeList &UNodeList) {
 152   // check offset size in addasl. if 'offset > 3' return false
 153   const MachineOperand &OffsetOp = MI.getOperand(3);
 154   if (!OffsetOp.isImm() || OffsetOp.getImm() > 3)
 155     return false;
 156
 157   unsigned OffsetReg = MI.getOperand(2).getReg();
 158   RegisterRef OffsetRR;
 159   NodeId OffsetRegRD = 0;
 160   for (NodeAddr<UseNode *> UA : AddAslSN.Addr->members_if(DFG->IsUse, *DFG)) {
 161     RegisterRef RR = UA.Addr->getRegRef(*DFG);
 162     if (OffsetReg == RR.Reg) {
 163       OffsetRR = RR;
 164       OffsetRegRD = UA.Addr->getReachingDef();
 165     }
 166   }
 167
 168   for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
 169     NodeAddr<UseNode *> UA = *I;
 170     NodeAddr<InstrNode *> IA = UA.Addr->getOwner(*DFG);
 171     if (UA.Addr->getFlags() & NodeAttrs::PhiRef)
 172       return false;
 173     NodeAddr<RefNode*> AA = LV->getNearestAliasedRef(OffsetRR, IA);
 174     if ((DFG->IsDef(AA) && AA.Id != OffsetRegRD) ||
 175          AA.Addr->getReachingDef() != OffsetRegRD)
 176       return false;
 177
 178     MachineInstr &UseMI = *NodeAddr<StmtNode *>(IA).Addr->getCode();
 179     NodeAddr<DefNode *> OffsetRegDN = DFG->addr<DefNode *>(OffsetRegRD);
 180     // Reaching Def to an offset register can't be a phi.
 181     if ((OffsetRegDN.Addr->getFlags() & NodeAttrs::PhiRef) &&
 182         MI.getParent() != UseMI.getParent())
 183     return false;
 184
 185     const MCInstrDesc &UseMID = UseMI.getDesc();
 186     if ((!UseMID.mayLoad() && !UseMID.mayStore()) ||
 187         HII->getAddrMode(UseMI) != HexagonII::BaseImmOffset ||
 188         getBaseWithLongOffset(UseMI) < 0)
 189       return false;
 190
 191     // Addasl output can't be a store value.
 192     if (UseMID.mayStore() && UseMI.getOperand(2).isReg() &&
 193         UseMI.getOperand(2).getReg() == MI.getOperand(0).getReg())
 194       return false;
 195
 196     for (auto &Mo : UseMI.operands())
 197       if (Mo.isFI())
 198         return false;
 199   }
 200   return true;
 201 }
 202
 203 bool HexagonOptAddrMode::allValidCandidates(NodeAddr<StmtNode *> SA,
 204                                             NodeList &UNodeList) {
 205   for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
 206     NodeAddr<UseNode *> UN = *I;
 207     RegisterRef UR = UN.Addr->getRegRef(*DFG);
 208     NodeSet Visited, Defs;
 209     const auto &P = LV->getAllReachingDefsRec(UR, UN, Visited, Defs);
 210     if (!P.second) {
 211       DEBUG({
 212         dbgs() << "*** Unable to collect all reaching defs for use ***\n"
 213                << PrintNode<UseNode*>(UN, *DFG) << '\n'
 214                << "The program's complexity may exceed the limits.\n";
 215       });
 216       return false;
 217     }
 218     const auto &ReachingDefs = P.first;
 219     if (ReachingDefs.size() > 1) {
 220       DEBUG({
 221         dbgs() << "*** Multiple Reaching Defs found!!! ***\n";
 222         for (auto DI : ReachingDefs) {
 223           NodeAddr<UseNode *> DA = DFG->addr<UseNode *>(DI);
 224           NodeAddr<StmtNode *> TempIA = DA.Addr->getOwner(*DFG);
 225           dbgs() << "\t\t[Reaching Def]: "
 226                  << Print<NodeAddr<InstrNode *>>(TempIA, *DFG) << "\n";
 227         }
 228       });
 229       return false;
 230     }
 231   }
 232   return true;
 233 }
 234
 235 void HexagonOptAddrMode::getAllRealUses(NodeAddr<StmtNode *> SA,
 236                                         NodeList &UNodeList) {
 237   for (NodeAddr<DefNode *> DA : SA.Addr->members_if(DFG->IsDef, *DFG)) {
 238     DEBUG(dbgs() << "\t\t[DefNode]: " << Print<NodeAddr<DefNode *>>(DA, *DFG)
 239                  << "\n");
 240     RegisterRef DR = DFG->getPRI().normalize(DA.Addr->getRegRef(*DFG));
 241
 242     auto UseSet = LV->getAllReachedUses(DR, DA);
 243
 244     for (auto UI : UseSet) {
 245       NodeAddr<UseNode *> UA = DFG->addr<UseNode *>(UI);
 246       DEBUG({
 247         NodeAddr<StmtNode *> TempIA = UA.Addr->getOwner(*DFG);
 248         dbgs() << "\t\t\t[Reached Use]: "
 249                << Print<NodeAddr<InstrNode *>>(TempIA, *DFG) << "\n";
 250       });
 251
 252       if (UA.Addr->getFlags() & NodeAttrs::PhiRef) {
 253         NodeAddr<PhiNode *> PA = UA.Addr->getOwner(*DFG);
 254         NodeId id = PA.Id;
 255         const Liveness::RefMap &phiUse = LV->getRealUses(id);
 256         DEBUG(dbgs() << "\t\t\t\tphi real Uses"
 257                      << Print<Liveness::RefMap>(phiUse, *DFG) << "\n");
 258         if (!phiUse.empty()) {
 259           for (auto I : phiUse) {
 260             if (!DFG->getPRI().alias(RegisterRef(I.first), DR))
 261               continue;
 262             auto phiUseSet = I.second;
 263             for (auto phiUI : phiUseSet) {
 264               NodeAddr<UseNode *> phiUA = DFG->addr<UseNode *>(phiUI.first);
 265               UNodeList.push_back(phiUA);
 266             }
 267           }
 268         }
 269       } else
 270         UNodeList.push_back(UA);
 271     }
 272   }
 273 }
 274
 275 bool HexagonOptAddrMode::analyzeUses(unsigned tfrDefR,
 276                                      const NodeList &UNodeList,
 277                                      InstrEvalMap &InstrEvalResult,
 278                                      short &SizeInc) {
 279   bool KeepTfr = false;
 280   bool HasRepInstr = false;
 281   InstrEvalResult.clear();
 282
 283   for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
 284     bool CanBeReplaced = false;
 285     NodeAddr<UseNode *> UN = *I;
 286     NodeAddr<StmtNode *> SN = UN.Addr->getOwner(*DFG);
 287     MachineInstr &MI = *SN.Addr->getCode();
 288     const MCInstrDesc &MID = MI.getDesc();
 289     if ((MID.mayLoad() || MID.mayStore())) {
 290       if (!hasRepForm(MI, tfrDefR)) {
 291         KeepTfr = true;
 292         continue;
 293       }
 294       SizeInc++;
 295       CanBeReplaced = true;
 296     } else if (MI.getOpcode() == Hexagon::S2_addasl_rrri) {
 297       NodeList AddaslUseList;
 298
 299       DEBUG(dbgs() << "\nGetting ReachedUses for === " << MI << "\n");
 300       getAllRealUses(SN, AddaslUseList);
 301       // Process phi nodes.
 302       if (allValidCandidates(SN, AddaslUseList) &&
 303           canRemoveAddasl(SN, MI, AddaslUseList)) {
 304         SizeInc += AddaslUseList.size();
 305         SizeInc -= 1; // Reduce size by 1 as addasl itself can be removed.
 306         CanBeReplaced = true;
 307       } else
 308         SizeInc++;
 309     } else
 310       // Currently, only load/store and addasl are handled.
 311       // Some other instructions to consider -
 312       // A2_add -> A2_addi
 313       // M4_mpyrr_addr -> M4_mpyrr_addi
 314       KeepTfr = true;
 315
 316     InstrEvalResult[&MI] = CanBeReplaced;
 317     HasRepInstr |= CanBeReplaced;
 318   }
 319
 320   // Reduce total size by 2 if original tfr can be deleted.
 321   if (!KeepTfr)
 322     SizeInc -= 2;
 323
 324   return HasRepInstr;
 325 }
 326
 327 bool HexagonOptAddrMode::changeLoad(MachineInstr *OldMI, MachineOperand ImmOp,
 328                                     unsigned ImmOpNum) {
 329   bool Changed = false;
 330   MachineBasicBlock *BB = OldMI->getParent();
 331   auto UsePos = MachineBasicBlock::iterator(OldMI);
 332   MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
 333   ++InsertPt;
 334   unsigned OpStart;
 335   unsigned OpEnd = OldMI->getNumOperands();
 336   MachineInstrBuilder MIB;
 337
 338   if (ImmOpNum == 1) {
 339     if (HII->getAddrMode(*OldMI) == HexagonII::BaseRegOffset) {
 340       short NewOpCode = HII->changeAddrMode_rr_ur(*OldMI);
 341       assert(NewOpCode >= 0 && "Invalid New opcode\n");
 342       MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
 343       MIB.add(OldMI->getOperand(0));
 344       MIB.add(OldMI->getOperand(2));
 345       MIB.add(OldMI->getOperand(3));
 346       MIB.add(ImmOp);
 347       OpStart = 4;
 348       Changed = true;
 349     } else if (HII->getAddrMode(*OldMI) == HexagonII::BaseImmOffset) {
 350       short NewOpCode = HII->changeAddrMode_io_abs(*OldMI);
 351       assert(NewOpCode >= 0 && "Invalid New opcode\n");
 352       MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode))
 353                 .add(OldMI->getOperand(0));
 354       const GlobalValue *GV = ImmOp.getGlobal();
 355       int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(2).getImm();
 356
 357       MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags());
 358       OpStart = 3;
 359       Changed = true;
 360     } else
 361       Changed = false;
 362
 363     DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
 364     DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
 365   } else if (ImmOpNum == 2 && OldMI->getOperand(3).getImm() == 0) {
 366     short NewOpCode = HII->changeAddrMode_rr_io(*OldMI);
 367     assert(NewOpCode >= 0 && "Invalid New opcode\n");
 368     MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
 369     MIB.add(OldMI->getOperand(0));
 370     MIB.add(OldMI->getOperand(1));
 371     MIB.add(ImmOp);
 372     OpStart = 4;
 373     Changed = true;
 374     DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
 375     DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
 376   }
 377
 378   if (Changed)
 379     for (unsigned i = OpStart; i < OpEnd; ++i)
 380       MIB.add(OldMI->getOperand(i));
 381
 382   return Changed;
 383 }
 384
 385 bool HexagonOptAddrMode::changeStore(MachineInstr *OldMI, MachineOperand ImmOp,
 386                                      unsigned ImmOpNum) {
 387   bool Changed = false;
 388   unsigned OpStart;
 389   unsigned OpEnd = OldMI->getNumOperands();
 390   MachineBasicBlock *BB = OldMI->getParent();
 391   auto UsePos = MachineBasicBlock::iterator(OldMI);
 392   MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
 393   ++InsertPt;
 394   MachineInstrBuilder MIB;
 395   if (ImmOpNum == 0) {
 396     if (HII->getAddrMode(*OldMI) == HexagonII::BaseRegOffset) {
 397       short NewOpCode = HII->changeAddrMode_rr_ur(*OldMI);
 398       assert(NewOpCode >= 0 && "Invalid New opcode\n");
 399       MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
 400       MIB.add(OldMI->getOperand(1));
 401       MIB.add(OldMI->getOperand(2));
 402       MIB.add(ImmOp);
 403       MIB.add(OldMI->getOperand(3));
 404       OpStart = 4;
 405     } else if (HII->getAddrMode(*OldMI) == HexagonII::BaseImmOffset) {
 406       short NewOpCode = HII->changeAddrMode_io_abs(*OldMI);
 407       assert(NewOpCode >= 0 && "Invalid New opcode\n");
 408       MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
 409       const GlobalValue *GV = ImmOp.getGlobal();
 410       int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(1).getImm();
 411       MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags());
 412       MIB.add(OldMI->getOperand(2));
 413       OpStart = 3;
 414     }
 415     Changed = true;
 416     DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
 417     DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
 418   } else if (ImmOpNum == 1 && OldMI->getOperand(2).getImm() == 0) {
 419     short NewOpCode = HII->changeAddrMode_rr_io(*OldMI);
 420     assert(NewOpCode >= 0 && "Invalid New opcode\n");
 421     MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
 422     MIB.add(OldMI->getOperand(0));
 423     MIB.add(ImmOp);
 424     OpStart = 3;
 425     Changed = true;
 426     DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
 427     DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
 428   }
 429   if (Changed)
 430     for (unsigned i = OpStart; i < OpEnd; ++i)
 431       MIB.add(OldMI->getOperand(i));
 432
 433   return Changed;
 434 }
 435
 436 short HexagonOptAddrMode::getBaseWithLongOffset(const MachineInstr &MI) const {
 437   if (HII->getAddrMode(MI) == HexagonII::BaseImmOffset) {
 438     short TempOpCode = HII->changeAddrMode_io_rr(MI);
 439     return HII->changeAddrMode_rr_ur(TempOpCode);
 440   }
 441   return HII->changeAddrMode_rr_ur(MI);
 442 }
 443
 444 bool HexagonOptAddrMode::changeAddAsl(NodeAddr<UseNode *> AddAslUN,
 445                                       MachineInstr *AddAslMI,
 446                                       const MachineOperand &ImmOp,
 447                                       unsigned ImmOpNum) {
 448   NodeAddr<StmtNode *> SA = AddAslUN.Addr->getOwner(*DFG);
 449
 450   DEBUG(dbgs() << "Processing addasl :" << *AddAslMI << "\n");
 451
 452   NodeList UNodeList;
 453   getAllRealUses(SA, UNodeList);
 454
 455   for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
 456     NodeAddr<UseNode *> UseUN = *I;
 457     assert(!(UseUN.Addr->getFlags() & NodeAttrs::PhiRef) &&
 458            "Can't transform this 'AddAsl' instruction!");
 459
 460     NodeAddr<StmtNode *> UseIA = UseUN.Addr->getOwner(*DFG);
 461     DEBUG(dbgs() << "[InstrNode]: " << Print<NodeAddr<InstrNode *>>(UseIA, *DFG)
 462                  << "\n");
 463     MachineInstr *UseMI = UseIA.Addr->getCode();
 464     DEBUG(dbgs() << "[MI <" << printMBBReference(*UseMI->getParent())
 465                  << ">]: " << *UseMI << "\n");
 466     const MCInstrDesc &UseMID = UseMI->getDesc();
 467     assert(HII->getAddrMode(*UseMI) == HexagonII::BaseImmOffset);
 468
 469     auto UsePos = MachineBasicBlock::iterator(UseMI);
 470     MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
 471     short NewOpCode = getBaseWithLongOffset(*UseMI);
 472     assert(NewOpCode >= 0 && "Invalid New opcode\n");
 473
 474     unsigned OpStart;
 475     unsigned OpEnd = UseMI->getNumOperands();
 476
 477     MachineBasicBlock *BB = UseMI->getParent();
 478     MachineInstrBuilder MIB =
 479         BuildMI(*BB, InsertPt, UseMI->getDebugLoc(), HII->get(NewOpCode));
 480     // change mem(Rs + # ) -> mem(Rt << # + ##)
 481     if (UseMID.mayLoad()) {
 482       MIB.add(UseMI->getOperand(0));
 483       MIB.add(AddAslMI->getOperand(2));
 484       MIB.add(AddAslMI->getOperand(3));
 485       const GlobalValue *GV = ImmOp.getGlobal();
 486       MIB.addGlobalAddress(GV, UseMI->getOperand(2).getImm()+ImmOp.getOffset(),
 487                            ImmOp.getTargetFlags());
 488       OpStart = 3;
 489     } else if (UseMID.mayStore()) {
 490       MIB.add(AddAslMI->getOperand(2));
 491       MIB.add(AddAslMI->getOperand(3));
 492       const GlobalValue *GV = ImmOp.getGlobal();
 493       MIB.addGlobalAddress(GV, UseMI->getOperand(1).getImm()+ImmOp.getOffset(),
 494                            ImmOp.getTargetFlags());
 495       MIB.add(UseMI->getOperand(2));
 496       OpStart = 3;
 497     } else
 498       llvm_unreachable("Unhandled instruction");
 499
 500     for (unsigned i = OpStart; i < OpEnd; ++i)
 501       MIB.add(UseMI->getOperand(i));
 502
 503     Deleted.insert(UseMI);
 504   }
 505
 506   return true;
 507 }
 508
 509 bool HexagonOptAddrMode::xformUseMI(MachineInstr *TfrMI, MachineInstr *UseMI,
 510                                     NodeAddr<UseNode *> UseN,
 511                                     unsigned UseMOnum) {
 512   const MachineOperand ImmOp = TfrMI->getOperand(1);
 513   const MCInstrDesc &MID = UseMI->getDesc();
 514   unsigned Changed = false;
 515   if (MID.mayLoad())
 516     Changed = changeLoad(UseMI, ImmOp, UseMOnum);
 517   else if (MID.mayStore())
 518     Changed = changeStore(UseMI, ImmOp, UseMOnum);
 519   else if (UseMI->getOpcode() == Hexagon::S2_addasl_rrri)
 520     Changed = changeAddAsl(UseN, UseMI, ImmOp, UseMOnum);
 521
 522   if (Changed)
 523     Deleted.insert(UseMI);
 524
 525   return Changed;
 526 }
 527
 528 bool HexagonOptAddrMode::processBlock(NodeAddr<BlockNode *> BA) {
 529   bool Changed = false;
 530
 531   for (auto IA : BA.Addr->members(*DFG)) {
 532     if (!DFG->IsCode<NodeAttrs::Stmt>(IA))
 533       continue;
 534
 535     NodeAddr<StmtNode *> SA = IA;
 536     MachineInstr *MI = SA.Addr->getCode();
 537     if (MI->getOpcode() != Hexagon::A2_tfrsi ||
 538         !MI->getOperand(1).isGlobal())
 539       continue;
 540
 541     DEBUG(dbgs() << "[Analyzing " << HII->getName(MI->getOpcode()) << "]: "
 542                  << *MI << "\n\t[InstrNode]: "
 543                  << Print<NodeAddr<InstrNode *>>(IA, *DFG) << '\n');
 544
 545     NodeList UNodeList;
 546     getAllRealUses(SA, UNodeList);
 547
 548     if (!allValidCandidates(SA, UNodeList))
 549       continue;
 550
 551     short SizeInc = 0;
 552     unsigned DefR = MI->getOperand(0).getReg();
 553     InstrEvalMap InstrEvalResult;
 554
 555     // Analyze all uses and calculate increase in size. Perform the optimization
 556     // only if there is no increase in size.
 557     if (!analyzeUses(DefR, UNodeList, InstrEvalResult, SizeInc))
 558       continue;
 559     if (SizeInc > CodeGrowthLimit)
 560       continue;
 561
 562     bool KeepTfr = false;
 563
 564     DEBUG(dbgs() << "\t[Total reached uses] : " << UNodeList.size() << "\n");
 565     DEBUG(dbgs() << "\t[Processing Reached Uses] ===\n");
 566     for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
 567       NodeAddr<UseNode *> UseN = *I;
 568       assert(!(UseN.Addr->getFlags() & NodeAttrs::PhiRef) &&
 569              "Found a PhiRef node as a real reached use!!");
 570
 571       NodeAddr<StmtNode *> OwnerN = UseN.Addr->getOwner(*DFG);
 572       MachineInstr *UseMI = OwnerN.Addr->getCode();
 573       DEBUG(dbgs() << "\t\t[MI <" << printMBBReference(*UseMI->getParent())
 574                    << ">]: " << *UseMI << "\n");
 575
 576       int UseMOnum = -1;
 577       unsigned NumOperands = UseMI->getNumOperands();
 578       for (unsigned j = 0; j < NumOperands - 1; ++j) {
 579         const MachineOperand &op = UseMI->getOperand(j);
 580         if (op.isReg() && op.isUse() && DefR == op.getReg())
 581           UseMOnum = j;
 582       }
 583       assert(UseMOnum >= 0 && "Invalid reached use!");
 584
 585       if (InstrEvalResult[UseMI])
 586         // Change UseMI if replacement is possible.
 587         Changed |= xformUseMI(MI, UseMI, UseN, UseMOnum);
 588       else
 589         KeepTfr = true;
 590     }
 591     if (!KeepTfr)
 592       Deleted.insert(MI);
 593   }
 594   return Changed;
 595 }
 596
 597 bool HexagonOptAddrMode::runOnMachineFunction(MachineFunction &MF) {
 598   if (skipFunction(MF.getFunction()))
 599     return false;
 600
 601   bool Changed = false;
 602   auto &HST = MF.getSubtarget<HexagonSubtarget>();
 603   auto &MRI = MF.getRegInfo();
 604   HII = HST.getInstrInfo();
 605   const auto &MDF = getAnalysis<MachineDominanceFrontier>();
 606   MDT = &getAnalysis<MachineDominatorTree>();
 607   const auto &TRI = *MF.getSubtarget().getRegisterInfo();
 608   const TargetOperandInfo TOI(*HII);
 609
 610   DataFlowGraph G(MF, *HII, TRI, *MDT, MDF, TOI);
 611   // Need to keep dead phis because we can propagate uses of registers into
 612   // nodes dominated by those would-be phis.
 613   G.build(BuildOptions::KeepDeadPhis);
 614   DFG = &G;
 615
 616   Liveness L(MRI, *DFG);
 617   L.computePhiInfo();
 618   LV = &L;
 619
 620   Deleted.clear();
 621   NodeAddr<FuncNode *> FA = DFG->getFunc();
 622   DEBUG(dbgs() << "==== [RefMap#]=====:\n "
 623                << Print<NodeAddr<FuncNode *>>(FA, *DFG) << "\n");
 624
 625   for (NodeAddr<BlockNode *> BA : FA.Addr->members(*DFG))
 626     Changed |= processBlock(BA);
 627
 628   for (auto MI : Deleted)
 629     MI->eraseFromParent();
 630
 631   if (Changed) {
 632     G.build();
 633     L.computeLiveIns();
 634     L.resetLiveIns();
 635     L.resetKills();
 636   }
 637
 638   return Changed;
 639 }
 640
 641 //===----------------------------------------------------------------------===//
 642 //                         Public Constructor Functions
 643 //===----------------------------------------------------------------------===//
 644
 645 FunctionPass *llvm::createHexagonOptAddrMode() {
 646   return new HexagonOptAddrMode();
 647 }