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/MachineRegisterInfo.h" 31 #include "llvm/CodeGen/TargetSubtargetInfo.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 unsigned 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 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 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 DEBUG(dbgs() << "\t\t[DefNode]: " << Print<NodeAddr<DefNode *>>(DA, *DFG) 248 << "\n"); 249 RegisterRef DR = DFG->getPRI().normalize(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 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 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 DEBUG(dbgs() << "isSafeToExtLR: Returning false; another reaching def\n"); 310 return false; 311 } 312 313 MachineInstr *UseMI = NodeAddr<StmtNode *>(IA).Addr->getCode(); 314 NodeAddr<DefNode *> LRExtRegDN = DFG->addr<DefNode *>(LRExtRegRD); 315 // Reaching Def to LRExtReg can't be a phi. 316 if ((LRExtRegDN.Addr->getFlags() & NodeAttrs::PhiRef) && 317 MI->getParent() != UseMI->getParent()) 318 return false; 319 } 320 return true; 321 } 322 323 bool HexagonOptAddrMode::isValidOffset(MachineInstr *MI, int Offset) { 324 unsigned AlignMask = 0; 325 switch (HII->getMemAccessSize(*MI)) { 326 case HexagonII::MemAccessSize::DoubleWordAccess: 327 AlignMask = 0x7; 328 break; 329 case HexagonII::MemAccessSize::WordAccess: 330 AlignMask = 0x3; 331 break; 332 case HexagonII::MemAccessSize::HalfWordAccess: 333 AlignMask = 0x1; 334 break; 335 case HexagonII::MemAccessSize::ByteAccess: 336 AlignMask = 0x0; 337 break; 338 default: 339 return false; 340 } 341 342 if ((AlignMask & Offset) != 0) 343 return false; 344 return HII->isValidOffset(MI->getOpcode(), Offset, HRI, false); 345 } 346 347 bool HexagonOptAddrMode::processAddUses(NodeAddr<StmtNode *> AddSN, 348 MachineInstr *AddMI, 349 const NodeList &UNodeList) { 350 351 unsigned AddDefR = AddMI->getOperand(0).getReg(); 352 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) { 353 NodeAddr<UseNode *> UN = *I; 354 NodeAddr<StmtNode *> SN = UN.Addr->getOwner(*DFG); 355 MachineInstr *MI = SN.Addr->getCode(); 356 const MCInstrDesc &MID = MI->getDesc(); 357 if ((!MID.mayLoad() && !MID.mayStore()) || 358 HII->getAddrMode(*MI) != HexagonII::BaseImmOffset || 359 HII->isHVXVec(*MI)) 360 return false; 361 362 MachineOperand BaseOp = MID.mayLoad() ? MI->getOperand(1) 363 : MI->getOperand(0); 364 365 if (!BaseOp.isReg() || BaseOp.getReg() != AddDefR) 366 return false; 367 368 MachineOperand OffsetOp = MID.mayLoad() ? MI->getOperand(2) 369 : MI->getOperand(1); 370 if (!OffsetOp.isImm()) 371 return false; 372 373 int64_t newOffset = OffsetOp.getImm() + AddMI->getOperand(2).getImm(); 374 if (!isValidOffset(MI, newOffset)) 375 return false; 376 377 // Since we'll be extending the live range of Rt in the following example, 378 // make sure that is safe. another definition of Rt doesn't exist between 'add' 379 // and load/store instruction. 380 // 381 // Ex: Rx= add(Rt,#10) 382 // memw(Rx+#0) = Rs 383 // will be replaced with => memw(Rt+#10) = Rs 384 unsigned BaseReg = AddMI->getOperand(1).getReg(); 385 if (!isSafeToExtLR(AddSN, AddMI, BaseReg, UNodeList)) 386 return false; 387 } 388 389 // Update all the uses of 'add' with the appropriate base and offset 390 // values. 391 bool Changed = false; 392 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) { 393 NodeAddr<UseNode *> UseN = *I; 394 assert(!(UseN.Addr->getFlags() & NodeAttrs::PhiRef) && 395 "Found a PhiRef node as a real reached use!!"); 396 397 NodeAddr<StmtNode *> OwnerN = UseN.Addr->getOwner(*DFG); 398 MachineInstr *UseMI = OwnerN.Addr->getCode(); 399 DEBUG(dbgs() << "\t\t[MI <BB#" << UseMI->getParent()->getNumber() 400 << ">]: " << *UseMI << "\n"); 401 Changed |= updateAddUses(AddMI, UseMI); 402 } 403 404 if (Changed) 405 Deleted.insert(AddMI); 406 407 return Changed; 408 } 409 410 bool HexagonOptAddrMode::updateAddUses(MachineInstr *AddMI, 411 MachineInstr *UseMI) { 412 const MachineOperand ImmOp = AddMI->getOperand(2); 413 const MachineOperand AddRegOp = AddMI->getOperand(1); 414 unsigned newReg = AddRegOp.getReg(); 415 const MCInstrDesc &MID = UseMI->getDesc(); 416 417 MachineOperand &BaseOp = MID.mayLoad() ? UseMI->getOperand(1) 418 : UseMI->getOperand(0); 419 MachineOperand &OffsetOp = MID.mayLoad() ? UseMI->getOperand(2) 420 : UseMI->getOperand(1); 421 BaseOp.setReg(newReg); 422 BaseOp.setIsUndef(AddRegOp.isUndef()); 423 BaseOp.setImplicit(AddRegOp.isImplicit()); 424 OffsetOp.setImm(ImmOp.getImm() + OffsetOp.getImm()); 425 MRI->clearKillFlags(newReg); 426 427 return true; 428 } 429 430 bool HexagonOptAddrMode::analyzeUses(unsigned tfrDefR, 431 const NodeList &UNodeList, 432 InstrEvalMap &InstrEvalResult, 433 short &SizeInc) { 434 bool KeepTfr = false; 435 bool HasRepInstr = false; 436 InstrEvalResult.clear(); 437 438 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) { 439 bool CanBeReplaced = false; 440 NodeAddr<UseNode *> UN = *I; 441 NodeAddr<StmtNode *> SN = UN.Addr->getOwner(*DFG); 442 MachineInstr &MI = *SN.Addr->getCode(); 443 const MCInstrDesc &MID = MI.getDesc(); 444 if ((MID.mayLoad() || MID.mayStore())) { 445 if (!hasRepForm(MI, tfrDefR)) { 446 KeepTfr = true; 447 continue; 448 } 449 SizeInc++; 450 CanBeReplaced = true; 451 } else if (MI.getOpcode() == Hexagon::S2_addasl_rrri) { 452 NodeList AddaslUseList; 453 454 DEBUG(dbgs() << "\nGetting ReachedUses for === " << MI << "\n"); 455 getAllRealUses(SN, AddaslUseList); 456 // Process phi nodes. 457 if (allValidCandidates(SN, AddaslUseList) && 458 canRemoveAddasl(SN, MI, AddaslUseList)) { 459 SizeInc += AddaslUseList.size(); 460 SizeInc -= 1; // Reduce size by 1 as addasl itself can be removed. 461 CanBeReplaced = true; 462 } else 463 SizeInc++; 464 } else 465 // Currently, only load/store and addasl are handled. 466 // Some other instructions to consider - 467 // A2_add -> A2_addi 468 // M4_mpyrr_addr -> M4_mpyrr_addi 469 KeepTfr = true; 470 471 InstrEvalResult[&MI] = CanBeReplaced; 472 HasRepInstr |= CanBeReplaced; 473 } 474 475 // Reduce total size by 2 if original tfr can be deleted. 476 if (!KeepTfr) 477 SizeInc -= 2; 478 479 return HasRepInstr; 480 } 481 482 bool HexagonOptAddrMode::changeLoad(MachineInstr *OldMI, MachineOperand ImmOp, 483 unsigned ImmOpNum) { 484 bool Changed = false; 485 MachineBasicBlock *BB = OldMI->getParent(); 486 auto UsePos = MachineBasicBlock::iterator(OldMI); 487 MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator(); 488 ++InsertPt; 489 unsigned OpStart; 490 unsigned OpEnd = OldMI->getNumOperands(); 491 MachineInstrBuilder MIB; 492 493 if (ImmOpNum == 1) { 494 if (HII->getAddrMode(*OldMI) == HexagonII::BaseRegOffset) { 495 short NewOpCode = HII->changeAddrMode_rr_ur(*OldMI); 496 assert(NewOpCode >= 0 && "Invalid New opcode\n"); 497 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode)); 498 MIB.add(OldMI->getOperand(0)); 499 MIB.add(OldMI->getOperand(2)); 500 MIB.add(OldMI->getOperand(3)); 501 MIB.add(ImmOp); 502 OpStart = 4; 503 Changed = true; 504 } else if (HII->getAddrMode(*OldMI) == HexagonII::BaseImmOffset) { 505 short NewOpCode = HII->changeAddrMode_io_abs(*OldMI); 506 assert(NewOpCode >= 0 && "Invalid New opcode\n"); 507 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode)) 508 .add(OldMI->getOperand(0)); 509 const GlobalValue *GV = ImmOp.getGlobal(); 510 int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(2).getImm(); 511 512 MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags()); 513 OpStart = 3; 514 Changed = true; 515 } else 516 Changed = false; 517 518 DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n"); 519 DEBUG(dbgs() << "[TO]: " << *MIB << "\n"); 520 } else if (ImmOpNum == 2 && OldMI->getOperand(3).getImm() == 0) { 521 short NewOpCode = HII->changeAddrMode_rr_io(*OldMI); 522 assert(NewOpCode >= 0 && "Invalid New opcode\n"); 523 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode)); 524 MIB.add(OldMI->getOperand(0)); 525 MIB.add(OldMI->getOperand(1)); 526 MIB.add(ImmOp); 527 OpStart = 4; 528 Changed = true; 529 DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n"); 530 DEBUG(dbgs() << "[TO]: " << *MIB << "\n"); 531 } 532 533 if (Changed) 534 for (unsigned i = OpStart; i < OpEnd; ++i) 535 MIB.add(OldMI->getOperand(i)); 536 537 return Changed; 538 } 539 540 bool HexagonOptAddrMode::changeStore(MachineInstr *OldMI, MachineOperand ImmOp, 541 unsigned ImmOpNum) { 542 bool Changed = false; 543 unsigned OpStart; 544 unsigned OpEnd = OldMI->getNumOperands(); 545 MachineBasicBlock *BB = OldMI->getParent(); 546 auto UsePos = MachineBasicBlock::iterator(OldMI); 547 MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator(); 548 ++InsertPt; 549 MachineInstrBuilder MIB; 550 if (ImmOpNum == 0) { 551 if (HII->getAddrMode(*OldMI) == HexagonII::BaseRegOffset) { 552 short NewOpCode = HII->changeAddrMode_rr_ur(*OldMI); 553 assert(NewOpCode >= 0 && "Invalid New opcode\n"); 554 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode)); 555 MIB.add(OldMI->getOperand(1)); 556 MIB.add(OldMI->getOperand(2)); 557 MIB.add(ImmOp); 558 MIB.add(OldMI->getOperand(3)); 559 OpStart = 4; 560 } else if (HII->getAddrMode(*OldMI) == HexagonII::BaseImmOffset) { 561 short NewOpCode = HII->changeAddrMode_io_abs(*OldMI); 562 assert(NewOpCode >= 0 && "Invalid New opcode\n"); 563 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode)); 564 const GlobalValue *GV = ImmOp.getGlobal(); 565 int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(1).getImm(); 566 MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags()); 567 MIB.add(OldMI->getOperand(2)); 568 OpStart = 3; 569 } 570 Changed = true; 571 DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n"); 572 DEBUG(dbgs() << "[TO]: " << *MIB << "\n"); 573 } else if (ImmOpNum == 1 && OldMI->getOperand(2).getImm() == 0) { 574 short NewOpCode = HII->changeAddrMode_rr_io(*OldMI); 575 assert(NewOpCode >= 0 && "Invalid New opcode\n"); 576 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode)); 577 MIB.add(OldMI->getOperand(0)); 578 MIB.add(ImmOp); 579 OpStart = 3; 580 Changed = true; 581 DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n"); 582 DEBUG(dbgs() << "[TO]: " << *MIB << "\n"); 583 } 584 if (Changed) 585 for (unsigned i = OpStart; i < OpEnd; ++i) 586 MIB.add(OldMI->getOperand(i)); 587 588 return Changed; 589 } 590 591 short HexagonOptAddrMode::getBaseWithLongOffset(const MachineInstr &MI) const { 592 if (HII->getAddrMode(MI) == HexagonII::BaseImmOffset) { 593 short TempOpCode = HII->changeAddrMode_io_rr(MI); 594 return HII->changeAddrMode_rr_ur(TempOpCode); 595 } 596 return HII->changeAddrMode_rr_ur(MI); 597 } 598 599 bool HexagonOptAddrMode::changeAddAsl(NodeAddr<UseNode *> AddAslUN, 600 MachineInstr *AddAslMI, 601 const MachineOperand &ImmOp, 602 unsigned ImmOpNum) { 603 NodeAddr<StmtNode *> SA = AddAslUN.Addr->getOwner(*DFG); 604 605 DEBUG(dbgs() << "Processing addasl :" << *AddAslMI << "\n"); 606 607 NodeList UNodeList; 608 getAllRealUses(SA, UNodeList); 609 610 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) { 611 NodeAddr<UseNode *> UseUN = *I; 612 assert(!(UseUN.Addr->getFlags() & NodeAttrs::PhiRef) && 613 "Can't transform this 'AddAsl' instruction!"); 614 615 NodeAddr<StmtNode *> UseIA = UseUN.Addr->getOwner(*DFG); 616 DEBUG(dbgs() << "[InstrNode]: " << Print<NodeAddr<InstrNode *>>(UseIA, *DFG) 617 << "\n"); 618 MachineInstr *UseMI = UseIA.Addr->getCode(); 619 DEBUG(dbgs() << "[MI <" << printMBBReference(*UseMI->getParent()) 620 << ">]: " << *UseMI << "\n"); 621 const MCInstrDesc &UseMID = UseMI->getDesc(); 622 assert(HII->getAddrMode(*UseMI) == HexagonII::BaseImmOffset); 623 624 auto UsePos = MachineBasicBlock::iterator(UseMI); 625 MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator(); 626 short NewOpCode = getBaseWithLongOffset(*UseMI); 627 assert(NewOpCode >= 0 && "Invalid New opcode\n"); 628 629 unsigned OpStart; 630 unsigned OpEnd = UseMI->getNumOperands(); 631 632 MachineBasicBlock *BB = UseMI->getParent(); 633 MachineInstrBuilder MIB = 634 BuildMI(*BB, InsertPt, UseMI->getDebugLoc(), HII->get(NewOpCode)); 635 // change mem(Rs + # ) -> mem(Rt << # + ##) 636 if (UseMID.mayLoad()) { 637 MIB.add(UseMI->getOperand(0)); 638 MIB.add(AddAslMI->getOperand(2)); 639 MIB.add(AddAslMI->getOperand(3)); 640 const GlobalValue *GV = ImmOp.getGlobal(); 641 MIB.addGlobalAddress(GV, UseMI->getOperand(2).getImm()+ImmOp.getOffset(), 642 ImmOp.getTargetFlags()); 643 OpStart = 3; 644 } else if (UseMID.mayStore()) { 645 MIB.add(AddAslMI->getOperand(2)); 646 MIB.add(AddAslMI->getOperand(3)); 647 const GlobalValue *GV = ImmOp.getGlobal(); 648 MIB.addGlobalAddress(GV, UseMI->getOperand(1).getImm()+ImmOp.getOffset(), 649 ImmOp.getTargetFlags()); 650 MIB.add(UseMI->getOperand(2)); 651 OpStart = 3; 652 } else 653 llvm_unreachable("Unhandled instruction"); 654 655 for (unsigned i = OpStart; i < OpEnd; ++i) 656 MIB.add(UseMI->getOperand(i)); 657 658 Deleted.insert(UseMI); 659 } 660 661 return true; 662 } 663 664 bool HexagonOptAddrMode::xformUseMI(MachineInstr *TfrMI, MachineInstr *UseMI, 665 NodeAddr<UseNode *> UseN, 666 unsigned UseMOnum) { 667 const MachineOperand ImmOp = TfrMI->getOperand(1); 668 const MCInstrDesc &MID = UseMI->getDesc(); 669 unsigned Changed = false; 670 if (MID.mayLoad()) 671 Changed = changeLoad(UseMI, ImmOp, UseMOnum); 672 else if (MID.mayStore()) 673 Changed = changeStore(UseMI, ImmOp, UseMOnum); 674 else if (UseMI->getOpcode() == Hexagon::S2_addasl_rrri) 675 Changed = changeAddAsl(UseN, UseMI, ImmOp, UseMOnum); 676 677 if (Changed) 678 Deleted.insert(UseMI); 679 680 return Changed; 681 } 682 683 bool HexagonOptAddrMode::processBlock(NodeAddr<BlockNode *> BA) { 684 bool Changed = false; 685 686 for (auto IA : BA.Addr->members(*DFG)) { 687 if (!DFG->IsCode<NodeAttrs::Stmt>(IA)) 688 continue; 689 690 NodeAddr<StmtNode *> SA = IA; 691 MachineInstr *MI = SA.Addr->getCode(); 692 if ((MI->getOpcode() != Hexagon::A2_tfrsi || 693 !MI->getOperand(1).isGlobal()) && 694 (MI->getOpcode() != Hexagon::A2_addi || 695 !MI->getOperand(2).isImm() || HII->isConstExtended(*MI))) 696 continue; 697 698 DEBUG(dbgs() << "[Analyzing " << HII->getName(MI->getOpcode()) << "]: " 699 << *MI << "\n\t[InstrNode]: " 700 << Print<NodeAddr<InstrNode *>>(IA, *DFG) << '\n'); 701 702 NodeList UNodeList; 703 getAllRealUses(SA, UNodeList); 704 705 if (!allValidCandidates(SA, UNodeList)) 706 continue; 707 708 // Analyze all uses of 'add'. If the output of 'add' is used as an address 709 // in the base+immediate addressing mode load/store instructions, see if 710 // they can be updated to use the immediate value as an offet. Thus, 711 // providing us the opportunity to eliminate 'add'. 712 // Ex: Rx= add(Rt,#12) 713 // memw(Rx+#0) = Rs 714 // This can be replaced with memw(Rt+#12) = Rs 715 // 716 // This transformation is only performed if all uses can be updated and 717 // the offset isn't required to be constant extended. 718 if (MI->getOpcode() == Hexagon::A2_addi) { 719 Changed |= processAddUses(SA, MI, UNodeList); 720 continue; 721 } 722 723 short SizeInc = 0; 724 unsigned DefR = MI->getOperand(0).getReg(); 725 InstrEvalMap InstrEvalResult; 726 727 // Analyze all uses and calculate increase in size. Perform the optimization 728 // only if there is no increase in size. 729 if (!analyzeUses(DefR, UNodeList, InstrEvalResult, SizeInc)) 730 continue; 731 if (SizeInc > CodeGrowthLimit) 732 continue; 733 734 bool KeepTfr = false; 735 736 DEBUG(dbgs() << "\t[Total reached uses] : " << UNodeList.size() << "\n"); 737 DEBUG(dbgs() << "\t[Processing Reached Uses] ===\n"); 738 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) { 739 NodeAddr<UseNode *> UseN = *I; 740 assert(!(UseN.Addr->getFlags() & NodeAttrs::PhiRef) && 741 "Found a PhiRef node as a real reached use!!"); 742 743 NodeAddr<StmtNode *> OwnerN = UseN.Addr->getOwner(*DFG); 744 MachineInstr *UseMI = OwnerN.Addr->getCode(); 745 DEBUG(dbgs() << "\t\t[MI <" << printMBBReference(*UseMI->getParent()) 746 << ">]: " << *UseMI << "\n"); 747 748 int UseMOnum = -1; 749 unsigned NumOperands = UseMI->getNumOperands(); 750 for (unsigned j = 0; j < NumOperands - 1; ++j) { 751 const MachineOperand &op = UseMI->getOperand(j); 752 if (op.isReg() && op.isUse() && DefR == op.getReg()) 753 UseMOnum = j; 754 } 755 // It is possible that the register will not be found in any operand. 756 // This could happen, for example, when DefR = R4, but the used 757 // register is D2. 758 759 if (UseMOnum >= 0 && InstrEvalResult[UseMI]) 760 // Change UseMI if replacement is possible. 761 Changed |= xformUseMI(MI, UseMI, UseN, UseMOnum); 762 else 763 KeepTfr = true; 764 } 765 if (!KeepTfr) 766 Deleted.insert(MI); 767 } 768 return Changed; 769 } 770 771 bool HexagonOptAddrMode::runOnMachineFunction(MachineFunction &MF) { 772 if (skipFunction(MF.getFunction())) 773 return false; 774 775 bool Changed = false; 776 auto &HST = MF.getSubtarget<HexagonSubtarget>(); 777 MRI = &MF.getRegInfo(); 778 HII = HST.getInstrInfo(); 779 HRI = HST.getRegisterInfo(); 780 const auto &MDF = getAnalysis<MachineDominanceFrontier>(); 781 MDT = &getAnalysis<MachineDominatorTree>(); 782 const TargetOperandInfo TOI(*HII); 783 784 DataFlowGraph G(MF, *HII, *HRI, *MDT, MDF, TOI); 785 // Need to keep dead phis because we can propagate uses of registers into 786 // nodes dominated by those would-be phis. 787 G.build(BuildOptions::KeepDeadPhis); 788 DFG = &G; 789 790 Liveness L(*MRI, *DFG); 791 L.computePhiInfo(); 792 LV = &L; 793 794 Deleted.clear(); 795 NodeAddr<FuncNode *> FA = DFG->getFunc(); 796 DEBUG(dbgs() << "==== [RefMap#]=====:\n " 797 << Print<NodeAddr<FuncNode *>>(FA, *DFG) << "\n"); 798 799 for (NodeAddr<BlockNode *> BA : FA.Addr->members(*DFG)) 800 Changed |= processBlock(BA); 801 802 for (auto MI : Deleted) 803 MI->eraseFromParent(); 804 805 if (Changed) { 806 G.build(); 807 L.computeLiveIns(); 808 L.resetLiveIns(); 809 L.resetKills(); 810 } 811 812 return Changed; 813 } 814 815 //===----------------------------------------------------------------------===// 816 // Public Constructor Functions 817 //===----------------------------------------------------------------------===// 818 819 FunctionPass *llvm::createHexagonOptAddrMode() { 820 return new HexagonOptAddrMode(); 821 } 822