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