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