lib/Target/Hexagon/HexagonOptAddrMode.cpp

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