1 //===- MachineLICM.cpp - Machine Loop Invariant Code Motion Pass ----------===// 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 // 9 // This pass performs loop invariant code motion on machine instructions. We 10 // attempt to remove as much code from the body of a loop as possible. 11 // 12 // This pass is not intended to be a replacement or a complete alternative 13 // for the LLVM-IR-level LICM pass. It is only designed to hoist simple 14 // constructs that are not exposed before lowering and instruction selection. 15 // 16 //===----------------------------------------------------------------------===// 17 18 #include "llvm/ADT/BitVector.h" 19 #include "llvm/ADT/DenseMap.h" 20 #include "llvm/ADT/STLExtras.h" 21 #include "llvm/ADT/SmallSet.h" 22 #include "llvm/ADT/SmallVector.h" 23 #include "llvm/ADT/Statistic.h" 24 #include "llvm/Analysis/AliasAnalysis.h" 25 #include "llvm/CodeGen/MachineBasicBlock.h" 26 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 27 #include "llvm/CodeGen/MachineDominators.h" 28 #include "llvm/CodeGen/MachineFrameInfo.h" 29 #include "llvm/CodeGen/MachineFunction.h" 30 #include "llvm/CodeGen/MachineFunctionPass.h" 31 #include "llvm/CodeGen/MachineInstr.h" 32 #include "llvm/CodeGen/MachineLoopInfo.h" 33 #include "llvm/CodeGen/MachineMemOperand.h" 34 #include "llvm/CodeGen/MachineOperand.h" 35 #include "llvm/CodeGen/MachineRegisterInfo.h" 36 #include "llvm/CodeGen/PseudoSourceValue.h" 37 #include "llvm/CodeGen/TargetInstrInfo.h" 38 #include "llvm/CodeGen/TargetLowering.h" 39 #include "llvm/CodeGen/TargetRegisterInfo.h" 40 #include "llvm/CodeGen/TargetSchedule.h" 41 #include "llvm/CodeGen/TargetSubtargetInfo.h" 42 #include "llvm/IR/DebugLoc.h" 43 #include "llvm/InitializePasses.h" 44 #include "llvm/MC/MCInstrDesc.h" 45 #include "llvm/MC/MCRegister.h" 46 #include "llvm/MC/MCRegisterInfo.h" 47 #include "llvm/Pass.h" 48 #include "llvm/Support/Casting.h" 49 #include "llvm/Support/CommandLine.h" 50 #include "llvm/Support/Debug.h" 51 #include "llvm/Support/raw_ostream.h" 52 #include <algorithm> 53 #include <cassert> 54 #include <limits> 55 #include <vector> 56 57 using namespace llvm; 58 59 #define DEBUG_TYPE "machinelicm" 60 61 static cl::opt<bool> 62 AvoidSpeculation("avoid-speculation", 63 cl::desc("MachineLICM should avoid speculation"), 64 cl::init(true), cl::Hidden); 65 66 static cl::opt<bool> 67 HoistCheapInsts("hoist-cheap-insts", 68 cl::desc("MachineLICM should hoist even cheap instructions"), 69 cl::init(false), cl::Hidden); 70 71 static cl::opt<bool> 72 HoistConstStores("hoist-const-stores", 73 cl::desc("Hoist invariant stores"), 74 cl::init(true), cl::Hidden); 75 // The default threshold of 100 (i.e. if target block is 100 times hotter) 76 // is based on empirical data on a single target and is subject to tuning. 77 static cl::opt<unsigned> 78 BlockFrequencyRatioThreshold("block-freq-ratio-threshold", 79 cl::desc("Do not hoist instructions if target" 80 "block is N times hotter than the source."), 81 cl::init(100), cl::Hidden); 82 83 enum class UseBFI { None, PGO, All }; 84 85 static cl::opt<UseBFI> 86 DisableHoistingToHotterBlocks("disable-hoisting-to-hotter-blocks", 87 cl::desc("Disable hoisting instructions to" 88 " hotter blocks"), 89 cl::init(UseBFI::PGO), cl::Hidden, 90 cl::values(clEnumValN(UseBFI::None, "none", 91 "disable the feature"), 92 clEnumValN(UseBFI::PGO, "pgo", 93 "enable the feature when using profile data"), 94 clEnumValN(UseBFI::All, "all", 95 "enable the feature with/wo profile data"))); 96 97 STATISTIC(NumHoisted, 98 "Number of machine instructions hoisted out of loops"); 99 STATISTIC(NumLowRP, 100 "Number of instructions hoisted in low reg pressure situation"); 101 STATISTIC(NumHighLatency, 102 "Number of high latency instructions hoisted"); 103 STATISTIC(NumCSEed, 104 "Number of hoisted machine instructions CSEed"); 105 STATISTIC(NumPostRAHoisted, 106 "Number of machine instructions hoisted out of loops post regalloc"); 107 STATISTIC(NumStoreConst, 108 "Number of stores of const phys reg hoisted out of loops"); 109 STATISTIC(NumNotHoistedDueToHotness, 110 "Number of instructions not hoisted due to block frequency"); 111 112 namespace { 113 114 class MachineLICMBase : public MachineFunctionPass { 115 const TargetInstrInfo *TII; 116 const TargetLoweringBase *TLI; 117 const TargetRegisterInfo *TRI; 118 const MachineFrameInfo *MFI; 119 MachineRegisterInfo *MRI; 120 TargetSchedModel SchedModel; 121 bool PreRegAlloc; 122 bool HasProfileData; 123 124 // Various analyses that we use... 125 AliasAnalysis *AA; // Alias analysis info. 126 MachineBlockFrequencyInfo *MBFI; // Machine block frequncy info 127 MachineLoopInfo *MLI; // Current MachineLoopInfo 128 MachineDominatorTree *DT; // Machine dominator tree for the cur loop 129 130 // State that is updated as we process loops 131 bool Changed; // True if a loop is changed. 132 bool FirstInLoop; // True if it's the first LICM in the loop. 133 MachineLoop *CurLoop; // The current loop we are working on. 134 MachineBasicBlock *CurPreheader; // The preheader for CurLoop. 135 136 // Exit blocks for CurLoop. 137 SmallVector<MachineBasicBlock *, 8> ExitBlocks; 138 139 bool isExitBlock(const MachineBasicBlock *MBB) const { 140 return is_contained(ExitBlocks, MBB); 141 } 142 143 // Track 'estimated' register pressure. 144 SmallSet<Register, 32> RegSeen; 145 SmallVector<unsigned, 8> RegPressure; 146 147 // Register pressure "limit" per register pressure set. If the pressure 148 // is higher than the limit, then it's considered high. 149 SmallVector<unsigned, 8> RegLimit; 150 151 // Register pressure on path leading from loop preheader to current BB. 152 SmallVector<SmallVector<unsigned, 8>, 16> BackTrace; 153 154 // For each opcode, keep a list of potential CSE instructions. 155 DenseMap<unsigned, std::vector<MachineInstr *>> CSEMap; 156 157 enum { 158 SpeculateFalse = 0, 159 SpeculateTrue = 1, 160 SpeculateUnknown = 2 161 }; 162 163 // If a MBB does not dominate loop exiting blocks then it may not safe 164 // to hoist loads from this block. 165 // Tri-state: 0 - false, 1 - true, 2 - unknown 166 unsigned SpeculationState; 167 168 public: 169 MachineLICMBase(char &PassID, bool PreRegAlloc) 170 : MachineFunctionPass(PassID), PreRegAlloc(PreRegAlloc) {} 171 172 bool runOnMachineFunction(MachineFunction &MF) override; 173 174 void getAnalysisUsage(AnalysisUsage &AU) const override { 175 AU.addRequired<MachineLoopInfo>(); 176 if (DisableHoistingToHotterBlocks != UseBFI::None) 177 AU.addRequired<MachineBlockFrequencyInfo>(); 178 AU.addRequired<MachineDominatorTree>(); 179 AU.addRequired<AAResultsWrapperPass>(); 180 AU.addPreserved<MachineLoopInfo>(); 181 MachineFunctionPass::getAnalysisUsage(AU); 182 } 183 184 void releaseMemory() override { 185 RegSeen.clear(); 186 RegPressure.clear(); 187 RegLimit.clear(); 188 BackTrace.clear(); 189 CSEMap.clear(); 190 } 191 192 private: 193 /// Keep track of information about hoisting candidates. 194 struct CandidateInfo { 195 MachineInstr *MI; 196 unsigned Def; 197 int FI; 198 199 CandidateInfo(MachineInstr *mi, unsigned def, int fi) 200 : MI(mi), Def(def), FI(fi) {} 201 }; 202 203 void HoistRegionPostRA(); 204 205 void HoistPostRA(MachineInstr *MI, unsigned Def); 206 207 void ProcessMI(MachineInstr *MI, BitVector &PhysRegDefs, 208 BitVector &PhysRegClobbers, SmallSet<int, 32> &StoredFIs, 209 SmallVectorImpl<CandidateInfo> &Candidates); 210 211 void AddToLiveIns(MCRegister Reg); 212 213 bool IsLICMCandidate(MachineInstr &I); 214 215 bool IsLoopInvariantInst(MachineInstr &I); 216 217 bool HasLoopPHIUse(const MachineInstr *MI) const; 218 219 bool HasHighOperandLatency(MachineInstr &MI, unsigned DefIdx, 220 Register Reg) const; 221 222 bool IsCheapInstruction(MachineInstr &MI) const; 223 224 bool CanCauseHighRegPressure(const DenseMap<unsigned, int> &Cost, 225 bool Cheap); 226 227 void UpdateBackTraceRegPressure(const MachineInstr *MI); 228 229 bool IsProfitableToHoist(MachineInstr &MI); 230 231 bool IsGuaranteedToExecute(MachineBasicBlock *BB); 232 233 bool isTriviallyReMaterializable(const MachineInstr &MI, 234 AAResults *AA) const; 235 236 void EnterScope(MachineBasicBlock *MBB); 237 238 void ExitScope(MachineBasicBlock *MBB); 239 240 void ExitScopeIfDone( 241 MachineDomTreeNode *Node, 242 DenseMap<MachineDomTreeNode *, unsigned> &OpenChildren, 243 DenseMap<MachineDomTreeNode *, MachineDomTreeNode *> &ParentMap); 244 245 void HoistOutOfLoop(MachineDomTreeNode *HeaderN); 246 247 void InitRegPressure(MachineBasicBlock *BB); 248 249 DenseMap<unsigned, int> calcRegisterCost(const MachineInstr *MI, 250 bool ConsiderSeen, 251 bool ConsiderUnseenAsDef); 252 253 void UpdateRegPressure(const MachineInstr *MI, 254 bool ConsiderUnseenAsDef = false); 255 256 MachineInstr *ExtractHoistableLoad(MachineInstr *MI); 257 258 MachineInstr *LookForDuplicate(const MachineInstr *MI, 259 std::vector<MachineInstr *> &PrevMIs); 260 261 bool 262 EliminateCSE(MachineInstr *MI, 263 DenseMap<unsigned, std::vector<MachineInstr *>>::iterator &CI); 264 265 bool MayCSE(MachineInstr *MI); 266 267 bool Hoist(MachineInstr *MI, MachineBasicBlock *Preheader); 268 269 void InitCSEMap(MachineBasicBlock *BB); 270 271 bool isTgtHotterThanSrc(MachineBasicBlock *SrcBlock, 272 MachineBasicBlock *TgtBlock); 273 MachineBasicBlock *getCurPreheader(); 274 }; 275 276 class MachineLICM : public MachineLICMBase { 277 public: 278 static char ID; 279 MachineLICM() : MachineLICMBase(ID, false) { 280 initializeMachineLICMPass(*PassRegistry::getPassRegistry()); 281 } 282 }; 283 284 class EarlyMachineLICM : public MachineLICMBase { 285 public: 286 static char ID; 287 EarlyMachineLICM() : MachineLICMBase(ID, true) { 288 initializeEarlyMachineLICMPass(*PassRegistry::getPassRegistry()); 289 } 290 }; 291 292 } // end anonymous namespace 293 294 char MachineLICM::ID; 295 char EarlyMachineLICM::ID; 296 297 char &llvm::MachineLICMID = MachineLICM::ID; 298 char &llvm::EarlyMachineLICMID = EarlyMachineLICM::ID; 299 300 INITIALIZE_PASS_BEGIN(MachineLICM, DEBUG_TYPE, 301 "Machine Loop Invariant Code Motion", false, false) 302 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 303 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 304 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 305 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 306 INITIALIZE_PASS_END(MachineLICM, DEBUG_TYPE, 307 "Machine Loop Invariant Code Motion", false, false) 308 309 INITIALIZE_PASS_BEGIN(EarlyMachineLICM, "early-machinelicm", 310 "Early Machine Loop Invariant Code Motion", false, false) 311 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 312 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 313 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 314 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 315 INITIALIZE_PASS_END(EarlyMachineLICM, "early-machinelicm", 316 "Early Machine Loop Invariant Code Motion", false, false) 317 318 /// Test if the given loop is the outer-most loop that has a unique predecessor. 319 static bool LoopIsOuterMostWithPredecessor(MachineLoop *CurLoop) { 320 // Check whether this loop even has a unique predecessor. 321 if (!CurLoop->getLoopPredecessor()) 322 return false; 323 // Ok, now check to see if any of its outer loops do. 324 for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop()) 325 if (L->getLoopPredecessor()) 326 return false; 327 // None of them did, so this is the outermost with a unique predecessor. 328 return true; 329 } 330 331 bool MachineLICMBase::runOnMachineFunction(MachineFunction &MF) { 332 if (skipFunction(MF.getFunction())) 333 return false; 334 335 Changed = FirstInLoop = false; 336 const TargetSubtargetInfo &ST = MF.getSubtarget(); 337 TII = ST.getInstrInfo(); 338 TLI = ST.getTargetLowering(); 339 TRI = ST.getRegisterInfo(); 340 MFI = &MF.getFrameInfo(); 341 MRI = &MF.getRegInfo(); 342 SchedModel.init(&ST); 343 344 PreRegAlloc = MRI->isSSA(); 345 HasProfileData = MF.getFunction().hasProfileData(); 346 347 if (PreRegAlloc) 348 LLVM_DEBUG(dbgs() << "******** Pre-regalloc Machine LICM: "); 349 else 350 LLVM_DEBUG(dbgs() << "******** Post-regalloc Machine LICM: "); 351 LLVM_DEBUG(dbgs() << MF.getName() << " ********\n"); 352 353 if (PreRegAlloc) { 354 // Estimate register pressure during pre-regalloc pass. 355 unsigned NumRPS = TRI->getNumRegPressureSets(); 356 RegPressure.resize(NumRPS); 357 std::fill(RegPressure.begin(), RegPressure.end(), 0); 358 RegLimit.resize(NumRPS); 359 for (unsigned i = 0, e = NumRPS; i != e; ++i) 360 RegLimit[i] = TRI->getRegPressureSetLimit(MF, i); 361 } 362 363 // Get our Loop information... 364 if (DisableHoistingToHotterBlocks != UseBFI::None) 365 MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 366 MLI = &getAnalysis<MachineLoopInfo>(); 367 DT = &getAnalysis<MachineDominatorTree>(); 368 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); 369 370 SmallVector<MachineLoop *, 8> Worklist(MLI->begin(), MLI->end()); 371 while (!Worklist.empty()) { 372 CurLoop = Worklist.pop_back_val(); 373 CurPreheader = nullptr; 374 ExitBlocks.clear(); 375 376 // If this is done before regalloc, only visit outer-most preheader-sporting 377 // loops. 378 if (PreRegAlloc && !LoopIsOuterMostWithPredecessor(CurLoop)) { 379 Worklist.append(CurLoop->begin(), CurLoop->end()); 380 continue; 381 } 382 383 CurLoop->getExitBlocks(ExitBlocks); 384 385 if (!PreRegAlloc) 386 HoistRegionPostRA(); 387 else { 388 // CSEMap is initialized for loop header when the first instruction is 389 // being hoisted. 390 MachineDomTreeNode *N = DT->getNode(CurLoop->getHeader()); 391 FirstInLoop = true; 392 HoistOutOfLoop(N); 393 CSEMap.clear(); 394 } 395 } 396 397 return Changed; 398 } 399 400 /// Return true if instruction stores to the specified frame. 401 static bool InstructionStoresToFI(const MachineInstr *MI, int FI) { 402 // Check mayStore before memory operands so that e.g. DBG_VALUEs will return 403 // true since they have no memory operands. 404 if (!MI->mayStore()) 405 return false; 406 // If we lost memory operands, conservatively assume that the instruction 407 // writes to all slots. 408 if (MI->memoperands_empty()) 409 return true; 410 for (const MachineMemOperand *MemOp : MI->memoperands()) { 411 if (!MemOp->isStore() || !MemOp->getPseudoValue()) 412 continue; 413 if (const FixedStackPseudoSourceValue *Value = 414 dyn_cast<FixedStackPseudoSourceValue>(MemOp->getPseudoValue())) { 415 if (Value->getFrameIndex() == FI) 416 return true; 417 } 418 } 419 return false; 420 } 421 422 /// Examine the instruction for potentai LICM candidate. Also 423 /// gather register def and frame object update information. 424 void MachineLICMBase::ProcessMI(MachineInstr *MI, 425 BitVector &PhysRegDefs, 426 BitVector &PhysRegClobbers, 427 SmallSet<int, 32> &StoredFIs, 428 SmallVectorImpl<CandidateInfo> &Candidates) { 429 bool RuledOut = false; 430 bool HasNonInvariantUse = false; 431 unsigned Def = 0; 432 for (const MachineOperand &MO : MI->operands()) { 433 if (MO.isFI()) { 434 // Remember if the instruction stores to the frame index. 435 int FI = MO.getIndex(); 436 if (!StoredFIs.count(FI) && 437 MFI->isSpillSlotObjectIndex(FI) && 438 InstructionStoresToFI(MI, FI)) 439 StoredFIs.insert(FI); 440 HasNonInvariantUse = true; 441 continue; 442 } 443 444 // We can't hoist an instruction defining a physreg that is clobbered in 445 // the loop. 446 if (MO.isRegMask()) { 447 PhysRegClobbers.setBitsNotInMask(MO.getRegMask()); 448 continue; 449 } 450 451 if (!MO.isReg()) 452 continue; 453 Register Reg = MO.getReg(); 454 if (!Reg) 455 continue; 456 assert(Register::isPhysicalRegister(Reg) && 457 "Not expecting virtual register!"); 458 459 if (!MO.isDef()) { 460 if (Reg && (PhysRegDefs.test(Reg) || PhysRegClobbers.test(Reg))) 461 // If it's using a non-loop-invariant register, then it's obviously not 462 // safe to hoist. 463 HasNonInvariantUse = true; 464 continue; 465 } 466 467 if (MO.isImplicit()) { 468 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 469 PhysRegClobbers.set(*AI); 470 if (!MO.isDead()) 471 // Non-dead implicit def? This cannot be hoisted. 472 RuledOut = true; 473 // No need to check if a dead implicit def is also defined by 474 // another instruction. 475 continue; 476 } 477 478 // FIXME: For now, avoid instructions with multiple defs, unless 479 // it's a dead implicit def. 480 if (Def) 481 RuledOut = true; 482 else 483 Def = Reg; 484 485 // If we have already seen another instruction that defines the same 486 // register, then this is not safe. Two defs is indicated by setting a 487 // PhysRegClobbers bit. 488 for (MCRegAliasIterator AS(Reg, TRI, true); AS.isValid(); ++AS) { 489 if (PhysRegDefs.test(*AS)) 490 PhysRegClobbers.set(*AS); 491 } 492 // Need a second loop because MCRegAliasIterator can visit the same 493 // register twice. 494 for (MCRegAliasIterator AS(Reg, TRI, true); AS.isValid(); ++AS) 495 PhysRegDefs.set(*AS); 496 497 if (PhysRegClobbers.test(Reg)) 498 // MI defined register is seen defined by another instruction in 499 // the loop, it cannot be a LICM candidate. 500 RuledOut = true; 501 } 502 503 // Only consider reloads for now and remats which do not have register 504 // operands. FIXME: Consider unfold load folding instructions. 505 if (Def && !RuledOut) { 506 int FI = std::numeric_limits<int>::min(); 507 if ((!HasNonInvariantUse && IsLICMCandidate(*MI)) || 508 (TII->isLoadFromStackSlot(*MI, FI) && MFI->isSpillSlotObjectIndex(FI))) 509 Candidates.push_back(CandidateInfo(MI, Def, FI)); 510 } 511 } 512 513 /// Walk the specified region of the CFG and hoist loop invariants out to the 514 /// preheader. 515 void MachineLICMBase::HoistRegionPostRA() { 516 MachineBasicBlock *Preheader = getCurPreheader(); 517 if (!Preheader) 518 return; 519 520 unsigned NumRegs = TRI->getNumRegs(); 521 BitVector PhysRegDefs(NumRegs); // Regs defined once in the loop. 522 BitVector PhysRegClobbers(NumRegs); // Regs defined more than once. 523 524 SmallVector<CandidateInfo, 32> Candidates; 525 SmallSet<int, 32> StoredFIs; 526 527 // Walk the entire region, count number of defs for each register, and 528 // collect potential LICM candidates. 529 for (MachineBasicBlock *BB : CurLoop->getBlocks()) { 530 // If the header of the loop containing this basic block is a landing pad, 531 // then don't try to hoist instructions out of this loop. 532 const MachineLoop *ML = MLI->getLoopFor(BB); 533 if (ML && ML->getHeader()->isEHPad()) continue; 534 535 // Conservatively treat live-in's as an external def. 536 // FIXME: That means a reload that're reused in successor block(s) will not 537 // be LICM'ed. 538 for (const auto &LI : BB->liveins()) { 539 for (MCRegAliasIterator AI(LI.PhysReg, TRI, true); AI.isValid(); ++AI) 540 PhysRegDefs.set(*AI); 541 } 542 543 SpeculationState = SpeculateUnknown; 544 for (MachineInstr &MI : *BB) 545 ProcessMI(&MI, PhysRegDefs, PhysRegClobbers, StoredFIs, Candidates); 546 } 547 548 // Gather the registers read / clobbered by the terminator. 549 BitVector TermRegs(NumRegs); 550 MachineBasicBlock::iterator TI = Preheader->getFirstTerminator(); 551 if (TI != Preheader->end()) { 552 for (const MachineOperand &MO : TI->operands()) { 553 if (!MO.isReg()) 554 continue; 555 Register Reg = MO.getReg(); 556 if (!Reg) 557 continue; 558 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 559 TermRegs.set(*AI); 560 } 561 } 562 563 // Now evaluate whether the potential candidates qualify. 564 // 1. Check if the candidate defined register is defined by another 565 // instruction in the loop. 566 // 2. If the candidate is a load from stack slot (always true for now), 567 // check if the slot is stored anywhere in the loop. 568 // 3. Make sure candidate def should not clobber 569 // registers read by the terminator. Similarly its def should not be 570 // clobbered by the terminator. 571 for (CandidateInfo &Candidate : Candidates) { 572 if (Candidate.FI != std::numeric_limits<int>::min() && 573 StoredFIs.count(Candidate.FI)) 574 continue; 575 576 unsigned Def = Candidate.Def; 577 if (!PhysRegClobbers.test(Def) && !TermRegs.test(Def)) { 578 bool Safe = true; 579 MachineInstr *MI = Candidate.MI; 580 for (const MachineOperand &MO : MI->operands()) { 581 if (!MO.isReg() || MO.isDef() || !MO.getReg()) 582 continue; 583 Register Reg = MO.getReg(); 584 if (PhysRegDefs.test(Reg) || 585 PhysRegClobbers.test(Reg)) { 586 // If it's using a non-loop-invariant register, then it's obviously 587 // not safe to hoist. 588 Safe = false; 589 break; 590 } 591 } 592 if (Safe) 593 HoistPostRA(MI, Candidate.Def); 594 } 595 } 596 } 597 598 /// Add register 'Reg' to the livein sets of BBs in the current loop, and make 599 /// sure it is not killed by any instructions in the loop. 600 void MachineLICMBase::AddToLiveIns(MCRegister Reg) { 601 for (MachineBasicBlock *BB : CurLoop->getBlocks()) { 602 if (!BB->isLiveIn(Reg)) 603 BB->addLiveIn(Reg); 604 for (MachineInstr &MI : *BB) { 605 for (MachineOperand &MO : MI.operands()) { 606 if (!MO.isReg() || !MO.getReg() || MO.isDef()) continue; 607 if (MO.getReg() == Reg || TRI->isSuperRegister(Reg, MO.getReg())) 608 MO.setIsKill(false); 609 } 610 } 611 } 612 } 613 614 /// When an instruction is found to only use loop invariant operands that is 615 /// safe to hoist, this instruction is called to do the dirty work. 616 void MachineLICMBase::HoistPostRA(MachineInstr *MI, unsigned Def) { 617 MachineBasicBlock *Preheader = getCurPreheader(); 618 619 // Now move the instructions to the predecessor, inserting it before any 620 // terminator instructions. 621 LLVM_DEBUG(dbgs() << "Hoisting to " << printMBBReference(*Preheader) 622 << " from " << printMBBReference(*MI->getParent()) << ": " 623 << *MI); 624 625 // Splice the instruction to the preheader. 626 MachineBasicBlock *MBB = MI->getParent(); 627 Preheader->splice(Preheader->getFirstTerminator(), MBB, MI); 628 629 // Since we are moving the instruction out of its basic block, we do not 630 // retain its debug location. Doing so would degrade the debugging 631 // experience and adversely affect the accuracy of profiling information. 632 assert(!MI->isDebugInstr() && "Should not hoist debug inst"); 633 MI->setDebugLoc(DebugLoc()); 634 635 // Add register to livein list to all the BBs in the current loop since a 636 // loop invariant must be kept live throughout the whole loop. This is 637 // important to ensure later passes do not scavenge the def register. 638 AddToLiveIns(Def); 639 640 ++NumPostRAHoisted; 641 Changed = true; 642 } 643 644 /// Check if this mbb is guaranteed to execute. If not then a load from this mbb 645 /// may not be safe to hoist. 646 bool MachineLICMBase::IsGuaranteedToExecute(MachineBasicBlock *BB) { 647 if (SpeculationState != SpeculateUnknown) 648 return SpeculationState == SpeculateFalse; 649 650 if (BB != CurLoop->getHeader()) { 651 // Check loop exiting blocks. 652 SmallVector<MachineBasicBlock*, 8> CurrentLoopExitingBlocks; 653 CurLoop->getExitingBlocks(CurrentLoopExitingBlocks); 654 for (MachineBasicBlock *CurrentLoopExitingBlock : CurrentLoopExitingBlocks) 655 if (!DT->dominates(BB, CurrentLoopExitingBlock)) { 656 SpeculationState = SpeculateTrue; 657 return false; 658 } 659 } 660 661 SpeculationState = SpeculateFalse; 662 return true; 663 } 664 665 /// Check if \p MI is trivially remateralizable and if it does not have any 666 /// virtual register uses. Even though rematerializable RA might not actually 667 /// rematerialize it in this scenario. In that case we do not want to hoist such 668 /// instruction out of the loop in a belief RA will sink it back if needed. 669 bool MachineLICMBase::isTriviallyReMaterializable(const MachineInstr &MI, 670 AAResults *AA) const { 671 if (!TII->isTriviallyReMaterializable(MI, AA)) 672 return false; 673 674 for (const MachineOperand &MO : MI.operands()) { 675 if (MO.isReg() && MO.isUse() && MO.getReg().isVirtual()) 676 return false; 677 } 678 679 return true; 680 } 681 682 void MachineLICMBase::EnterScope(MachineBasicBlock *MBB) { 683 LLVM_DEBUG(dbgs() << "Entering " << printMBBReference(*MBB) << '\n'); 684 685 // Remember livein register pressure. 686 BackTrace.push_back(RegPressure); 687 } 688 689 void MachineLICMBase::ExitScope(MachineBasicBlock *MBB) { 690 LLVM_DEBUG(dbgs() << "Exiting " << printMBBReference(*MBB) << '\n'); 691 BackTrace.pop_back(); 692 } 693 694 /// Destroy scope for the MBB that corresponds to the given dominator tree node 695 /// if its a leaf or all of its children are done. Walk up the dominator tree to 696 /// destroy ancestors which are now done. 697 void MachineLICMBase::ExitScopeIfDone(MachineDomTreeNode *Node, 698 DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren, 699 DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> &ParentMap) { 700 if (OpenChildren[Node]) 701 return; 702 703 // Pop scope. 704 ExitScope(Node->getBlock()); 705 706 // Now traverse upwards to pop ancestors whose offsprings are all done. 707 while (MachineDomTreeNode *Parent = ParentMap[Node]) { 708 unsigned Left = --OpenChildren[Parent]; 709 if (Left != 0) 710 break; 711 ExitScope(Parent->getBlock()); 712 Node = Parent; 713 } 714 } 715 716 /// Walk the specified loop in the CFG (defined by all blocks dominated by the 717 /// specified header block, and that are in the current loop) in depth first 718 /// order w.r.t the DominatorTree. This allows us to visit definitions before 719 /// uses, allowing us to hoist a loop body in one pass without iteration. 720 void MachineLICMBase::HoistOutOfLoop(MachineDomTreeNode *HeaderN) { 721 MachineBasicBlock *Preheader = getCurPreheader(); 722 if (!Preheader) 723 return; 724 725 SmallVector<MachineDomTreeNode*, 32> Scopes; 726 SmallVector<MachineDomTreeNode*, 8> WorkList; 727 DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> ParentMap; 728 DenseMap<MachineDomTreeNode*, unsigned> OpenChildren; 729 730 // Perform a DFS walk to determine the order of visit. 731 WorkList.push_back(HeaderN); 732 while (!WorkList.empty()) { 733 MachineDomTreeNode *Node = WorkList.pop_back_val(); 734 assert(Node && "Null dominator tree node?"); 735 MachineBasicBlock *BB = Node->getBlock(); 736 737 // If the header of the loop containing this basic block is a landing pad, 738 // then don't try to hoist instructions out of this loop. 739 const MachineLoop *ML = MLI->getLoopFor(BB); 740 if (ML && ML->getHeader()->isEHPad()) 741 continue; 742 743 // If this subregion is not in the top level loop at all, exit. 744 if (!CurLoop->contains(BB)) 745 continue; 746 747 Scopes.push_back(Node); 748 unsigned NumChildren = Node->getNumChildren(); 749 750 // Don't hoist things out of a large switch statement. This often causes 751 // code to be hoisted that wasn't going to be executed, and increases 752 // register pressure in a situation where it's likely to matter. 753 if (BB->succ_size() >= 25) 754 NumChildren = 0; 755 756 OpenChildren[Node] = NumChildren; 757 if (NumChildren) { 758 // Add children in reverse order as then the next popped worklist node is 759 // the first child of this node. This means we ultimately traverse the 760 // DOM tree in exactly the same order as if we'd recursed. 761 for (MachineDomTreeNode *Child : reverse(Node->children())) { 762 ParentMap[Child] = Node; 763 WorkList.push_back(Child); 764 } 765 } 766 } 767 768 if (Scopes.size() == 0) 769 return; 770 771 // Compute registers which are livein into the loop headers. 772 RegSeen.clear(); 773 BackTrace.clear(); 774 InitRegPressure(Preheader); 775 776 // Now perform LICM. 777 for (MachineDomTreeNode *Node : Scopes) { 778 MachineBasicBlock *MBB = Node->getBlock(); 779 780 EnterScope(MBB); 781 782 // Process the block 783 SpeculationState = SpeculateUnknown; 784 for (MachineInstr &MI : llvm::make_early_inc_range(*MBB)) { 785 if (!Hoist(&MI, Preheader)) 786 UpdateRegPressure(&MI); 787 // If we have hoisted an instruction that may store, it can only be a 788 // constant store. 789 } 790 791 // If it's a leaf node, it's done. Traverse upwards to pop ancestors. 792 ExitScopeIfDone(Node, OpenChildren, ParentMap); 793 } 794 } 795 796 static bool isOperandKill(const MachineOperand &MO, MachineRegisterInfo *MRI) { 797 return MO.isKill() || MRI->hasOneNonDBGUse(MO.getReg()); 798 } 799 800 /// Find all virtual register references that are liveout of the preheader to 801 /// initialize the starting "register pressure". Note this does not count live 802 /// through (livein but not used) registers. 803 void MachineLICMBase::InitRegPressure(MachineBasicBlock *BB) { 804 std::fill(RegPressure.begin(), RegPressure.end(), 0); 805 806 // If the preheader has only a single predecessor and it ends with a 807 // fallthrough or an unconditional branch, then scan its predecessor for live 808 // defs as well. This happens whenever the preheader is created by splitting 809 // the critical edge from the loop predecessor to the loop header. 810 if (BB->pred_size() == 1) { 811 MachineBasicBlock *TBB = nullptr, *FBB = nullptr; 812 SmallVector<MachineOperand, 4> Cond; 813 if (!TII->analyzeBranch(*BB, TBB, FBB, Cond, false) && Cond.empty()) 814 InitRegPressure(*BB->pred_begin()); 815 } 816 817 for (const MachineInstr &MI : *BB) 818 UpdateRegPressure(&MI, /*ConsiderUnseenAsDef=*/true); 819 } 820 821 /// Update estimate of register pressure after the specified instruction. 822 void MachineLICMBase::UpdateRegPressure(const MachineInstr *MI, 823 bool ConsiderUnseenAsDef) { 824 auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/true, ConsiderUnseenAsDef); 825 for (const auto &RPIdAndCost : Cost) { 826 unsigned Class = RPIdAndCost.first; 827 if (static_cast<int>(RegPressure[Class]) < -RPIdAndCost.second) 828 RegPressure[Class] = 0; 829 else 830 RegPressure[Class] += RPIdAndCost.second; 831 } 832 } 833 834 /// Calculate the additional register pressure that the registers used in MI 835 /// cause. 836 /// 837 /// If 'ConsiderSeen' is true, updates 'RegSeen' and uses the information to 838 /// figure out which usages are live-ins. 839 /// FIXME: Figure out a way to consider 'RegSeen' from all code paths. 840 DenseMap<unsigned, int> 841 MachineLICMBase::calcRegisterCost(const MachineInstr *MI, bool ConsiderSeen, 842 bool ConsiderUnseenAsDef) { 843 DenseMap<unsigned, int> Cost; 844 if (MI->isImplicitDef()) 845 return Cost; 846 for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) { 847 const MachineOperand &MO = MI->getOperand(i); 848 if (!MO.isReg() || MO.isImplicit()) 849 continue; 850 Register Reg = MO.getReg(); 851 if (!Register::isVirtualRegister(Reg)) 852 continue; 853 854 // FIXME: It seems bad to use RegSeen only for some of these calculations. 855 bool isNew = ConsiderSeen ? RegSeen.insert(Reg).second : false; 856 const TargetRegisterClass *RC = MRI->getRegClass(Reg); 857 858 RegClassWeight W = TRI->getRegClassWeight(RC); 859 int RCCost = 0; 860 if (MO.isDef()) 861 RCCost = W.RegWeight; 862 else { 863 bool isKill = isOperandKill(MO, MRI); 864 if (isNew && !isKill && ConsiderUnseenAsDef) 865 // Haven't seen this, it must be a livein. 866 RCCost = W.RegWeight; 867 else if (!isNew && isKill) 868 RCCost = -W.RegWeight; 869 } 870 if (RCCost == 0) 871 continue; 872 const int *PS = TRI->getRegClassPressureSets(RC); 873 for (; *PS != -1; ++PS) { 874 if (Cost.find(*PS) == Cost.end()) 875 Cost[*PS] = RCCost; 876 else 877 Cost[*PS] += RCCost; 878 } 879 } 880 return Cost; 881 } 882 883 /// Return true if this machine instruction loads from global offset table or 884 /// constant pool. 885 static bool mayLoadFromGOTOrConstantPool(MachineInstr &MI) { 886 assert(MI.mayLoad() && "Expected MI that loads!"); 887 888 // If we lost memory operands, conservatively assume that the instruction 889 // reads from everything.. 890 if (MI.memoperands_empty()) 891 return true; 892 893 for (MachineMemOperand *MemOp : MI.memoperands()) 894 if (const PseudoSourceValue *PSV = MemOp->getPseudoValue()) 895 if (PSV->isGOT() || PSV->isConstantPool()) 896 return true; 897 898 return false; 899 } 900 901 // This function iterates through all the operands of the input store MI and 902 // checks that each register operand statisfies isCallerPreservedPhysReg. 903 // This means, the value being stored and the address where it is being stored 904 // is constant throughout the body of the function (not including prologue and 905 // epilogue). When called with an MI that isn't a store, it returns false. 906 // A future improvement can be to check if the store registers are constant 907 // throughout the loop rather than throughout the funtion. 908 static bool isInvariantStore(const MachineInstr &MI, 909 const TargetRegisterInfo *TRI, 910 const MachineRegisterInfo *MRI) { 911 912 bool FoundCallerPresReg = false; 913 if (!MI.mayStore() || MI.hasUnmodeledSideEffects() || 914 (MI.getNumOperands() == 0)) 915 return false; 916 917 // Check that all register operands are caller-preserved physical registers. 918 for (const MachineOperand &MO : MI.operands()) { 919 if (MO.isReg()) { 920 Register Reg = MO.getReg(); 921 // If operand is a virtual register, check if it comes from a copy of a 922 // physical register. 923 if (Register::isVirtualRegister(Reg)) 924 Reg = TRI->lookThruCopyLike(MO.getReg(), MRI); 925 if (Register::isVirtualRegister(Reg)) 926 return false; 927 if (!TRI->isCallerPreservedPhysReg(Reg.asMCReg(), *MI.getMF())) 928 return false; 929 else 930 FoundCallerPresReg = true; 931 } else if (!MO.isImm()) { 932 return false; 933 } 934 } 935 return FoundCallerPresReg; 936 } 937 938 // Return true if the input MI is a copy instruction that feeds an invariant 939 // store instruction. This means that the src of the copy has to satisfy 940 // isCallerPreservedPhysReg and atleast one of it's users should satisfy 941 // isInvariantStore. 942 static bool isCopyFeedingInvariantStore(const MachineInstr &MI, 943 const MachineRegisterInfo *MRI, 944 const TargetRegisterInfo *TRI) { 945 946 // FIXME: If targets would like to look through instructions that aren't 947 // pure copies, this can be updated to a query. 948 if (!MI.isCopy()) 949 return false; 950 951 const MachineFunction *MF = MI.getMF(); 952 // Check that we are copying a constant physical register. 953 Register CopySrcReg = MI.getOperand(1).getReg(); 954 if (Register::isVirtualRegister(CopySrcReg)) 955 return false; 956 957 if (!TRI->isCallerPreservedPhysReg(CopySrcReg.asMCReg(), *MF)) 958 return false; 959 960 Register CopyDstReg = MI.getOperand(0).getReg(); 961 // Check if any of the uses of the copy are invariant stores. 962 assert(Register::isVirtualRegister(CopyDstReg) && 963 "copy dst is not a virtual reg"); 964 965 for (MachineInstr &UseMI : MRI->use_instructions(CopyDstReg)) { 966 if (UseMI.mayStore() && isInvariantStore(UseMI, TRI, MRI)) 967 return true; 968 } 969 return false; 970 } 971 972 /// Returns true if the instruction may be a suitable candidate for LICM. 973 /// e.g. If the instruction is a call, then it's obviously not safe to hoist it. 974 bool MachineLICMBase::IsLICMCandidate(MachineInstr &I) { 975 // Check if it's safe to move the instruction. 976 bool DontMoveAcrossStore = true; 977 if ((!I.isSafeToMove(AA, DontMoveAcrossStore)) && 978 !(HoistConstStores && isInvariantStore(I, TRI, MRI))) { 979 LLVM_DEBUG(dbgs() << "LICM: Instruction not safe to move.\n"); 980 return false; 981 } 982 983 // If it is a load then check if it is guaranteed to execute by making sure 984 // that it dominates all exiting blocks. If it doesn't, then there is a path 985 // out of the loop which does not execute this load, so we can't hoist it. 986 // Loads from constant memory are safe to speculate, for example indexed load 987 // from a jump table. 988 // Stores and side effects are already checked by isSafeToMove. 989 if (I.mayLoad() && !mayLoadFromGOTOrConstantPool(I) && 990 !IsGuaranteedToExecute(I.getParent())) { 991 LLVM_DEBUG(dbgs() << "LICM: Load not guaranteed to execute.\n"); 992 return false; 993 } 994 995 // Convergent attribute has been used on operations that involve inter-thread 996 // communication which results are implicitly affected by the enclosing 997 // control flows. It is not safe to hoist or sink such operations across 998 // control flow. 999 if (I.isConvergent()) 1000 return false; 1001 1002 return true; 1003 } 1004 1005 /// Returns true if the instruction is loop invariant. 1006 bool MachineLICMBase::IsLoopInvariantInst(MachineInstr &I) { 1007 if (!IsLICMCandidate(I)) { 1008 LLVM_DEBUG(dbgs() << "LICM: Instruction not a LICM candidate\n"); 1009 return false; 1010 } 1011 return CurLoop->isLoopInvariant(I); 1012 } 1013 1014 /// Return true if the specified instruction is used by a phi node and hoisting 1015 /// it could cause a copy to be inserted. 1016 bool MachineLICMBase::HasLoopPHIUse(const MachineInstr *MI) const { 1017 SmallVector<const MachineInstr*, 8> Work(1, MI); 1018 do { 1019 MI = Work.pop_back_val(); 1020 for (const MachineOperand &MO : MI->operands()) { 1021 if (!MO.isReg() || !MO.isDef()) 1022 continue; 1023 Register Reg = MO.getReg(); 1024 if (!Register::isVirtualRegister(Reg)) 1025 continue; 1026 for (MachineInstr &UseMI : MRI->use_instructions(Reg)) { 1027 // A PHI may cause a copy to be inserted. 1028 if (UseMI.isPHI()) { 1029 // A PHI inside the loop causes a copy because the live range of Reg is 1030 // extended across the PHI. 1031 if (CurLoop->contains(&UseMI)) 1032 return true; 1033 // A PHI in an exit block can cause a copy to be inserted if the PHI 1034 // has multiple predecessors in the loop with different values. 1035 // For now, approximate by rejecting all exit blocks. 1036 if (isExitBlock(UseMI.getParent())) 1037 return true; 1038 continue; 1039 } 1040 // Look past copies as well. 1041 if (UseMI.isCopy() && CurLoop->contains(&UseMI)) 1042 Work.push_back(&UseMI); 1043 } 1044 } 1045 } while (!Work.empty()); 1046 return false; 1047 } 1048 1049 /// Compute operand latency between a def of 'Reg' and an use in the current 1050 /// loop, return true if the target considered it high. 1051 bool MachineLICMBase::HasHighOperandLatency(MachineInstr &MI, unsigned DefIdx, 1052 Register Reg) const { 1053 if (MRI->use_nodbg_empty(Reg)) 1054 return false; 1055 1056 for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg)) { 1057 if (UseMI.isCopyLike()) 1058 continue; 1059 if (!CurLoop->contains(UseMI.getParent())) 1060 continue; 1061 for (unsigned i = 0, e = UseMI.getNumOperands(); i != e; ++i) { 1062 const MachineOperand &MO = UseMI.getOperand(i); 1063 if (!MO.isReg() || !MO.isUse()) 1064 continue; 1065 Register MOReg = MO.getReg(); 1066 if (MOReg != Reg) 1067 continue; 1068 1069 if (TII->hasHighOperandLatency(SchedModel, MRI, MI, DefIdx, UseMI, i)) 1070 return true; 1071 } 1072 1073 // Only look at the first in loop use. 1074 break; 1075 } 1076 1077 return false; 1078 } 1079 1080 /// Return true if the instruction is marked "cheap" or the operand latency 1081 /// between its def and a use is one or less. 1082 bool MachineLICMBase::IsCheapInstruction(MachineInstr &MI) const { 1083 if (TII->isAsCheapAsAMove(MI) || MI.isCopyLike()) 1084 return true; 1085 1086 bool isCheap = false; 1087 unsigned NumDefs = MI.getDesc().getNumDefs(); 1088 for (unsigned i = 0, e = MI.getNumOperands(); NumDefs && i != e; ++i) { 1089 MachineOperand &DefMO = MI.getOperand(i); 1090 if (!DefMO.isReg() || !DefMO.isDef()) 1091 continue; 1092 --NumDefs; 1093 Register Reg = DefMO.getReg(); 1094 if (Register::isPhysicalRegister(Reg)) 1095 continue; 1096 1097 if (!TII->hasLowDefLatency(SchedModel, MI, i)) 1098 return false; 1099 isCheap = true; 1100 } 1101 1102 return isCheap; 1103 } 1104 1105 /// Visit BBs from header to current BB, check if hoisting an instruction of the 1106 /// given cost matrix can cause high register pressure. 1107 bool 1108 MachineLICMBase::CanCauseHighRegPressure(const DenseMap<unsigned, int>& Cost, 1109 bool CheapInstr) { 1110 for (const auto &RPIdAndCost : Cost) { 1111 if (RPIdAndCost.second <= 0) 1112 continue; 1113 1114 unsigned Class = RPIdAndCost.first; 1115 int Limit = RegLimit[Class]; 1116 1117 // Don't hoist cheap instructions if they would increase register pressure, 1118 // even if we're under the limit. 1119 if (CheapInstr && !HoistCheapInsts) 1120 return true; 1121 1122 for (const auto &RP : BackTrace) 1123 if (static_cast<int>(RP[Class]) + RPIdAndCost.second >= Limit) 1124 return true; 1125 } 1126 1127 return false; 1128 } 1129 1130 /// Traverse the back trace from header to the current block and update their 1131 /// register pressures to reflect the effect of hoisting MI from the current 1132 /// block to the preheader. 1133 void MachineLICMBase::UpdateBackTraceRegPressure(const MachineInstr *MI) { 1134 // First compute the 'cost' of the instruction, i.e. its contribution 1135 // to register pressure. 1136 auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/false, 1137 /*ConsiderUnseenAsDef=*/false); 1138 1139 // Update register pressure of blocks from loop header to current block. 1140 for (auto &RP : BackTrace) 1141 for (const auto &RPIdAndCost : Cost) 1142 RP[RPIdAndCost.first] += RPIdAndCost.second; 1143 } 1144 1145 /// Return true if it is potentially profitable to hoist the given loop 1146 /// invariant. 1147 bool MachineLICMBase::IsProfitableToHoist(MachineInstr &MI) { 1148 if (MI.isImplicitDef()) 1149 return true; 1150 1151 // Besides removing computation from the loop, hoisting an instruction has 1152 // these effects: 1153 // 1154 // - The value defined by the instruction becomes live across the entire 1155 // loop. This increases register pressure in the loop. 1156 // 1157 // - If the value is used by a PHI in the loop, a copy will be required for 1158 // lowering the PHI after extending the live range. 1159 // 1160 // - When hoisting the last use of a value in the loop, that value no longer 1161 // needs to be live in the loop. This lowers register pressure in the loop. 1162 1163 if (HoistConstStores && isCopyFeedingInvariantStore(MI, MRI, TRI)) 1164 return true; 1165 1166 bool CheapInstr = IsCheapInstruction(MI); 1167 bool CreatesCopy = HasLoopPHIUse(&MI); 1168 1169 // Don't hoist a cheap instruction if it would create a copy in the loop. 1170 if (CheapInstr && CreatesCopy) { 1171 LLVM_DEBUG(dbgs() << "Won't hoist cheap instr with loop PHI use: " << MI); 1172 return false; 1173 } 1174 1175 // Rematerializable instructions should always be hoisted providing the 1176 // register allocator can just pull them down again when needed. 1177 if (isTriviallyReMaterializable(MI, AA)) 1178 return true; 1179 1180 // FIXME: If there are long latency loop-invariant instructions inside the 1181 // loop at this point, why didn't the optimizer's LICM hoist them? 1182 for (unsigned i = 0, e = MI.getDesc().getNumOperands(); i != e; ++i) { 1183 const MachineOperand &MO = MI.getOperand(i); 1184 if (!MO.isReg() || MO.isImplicit()) 1185 continue; 1186 Register Reg = MO.getReg(); 1187 if (!Register::isVirtualRegister(Reg)) 1188 continue; 1189 if (MO.isDef() && HasHighOperandLatency(MI, i, Reg)) { 1190 LLVM_DEBUG(dbgs() << "Hoist High Latency: " << MI); 1191 ++NumHighLatency; 1192 return true; 1193 } 1194 } 1195 1196 // Estimate register pressure to determine whether to LICM the instruction. 1197 // In low register pressure situation, we can be more aggressive about 1198 // hoisting. Also, favors hoisting long latency instructions even in 1199 // moderately high pressure situation. 1200 // Cheap instructions will only be hoisted if they don't increase register 1201 // pressure at all. 1202 auto Cost = calcRegisterCost(&MI, /*ConsiderSeen=*/false, 1203 /*ConsiderUnseenAsDef=*/false); 1204 1205 // Visit BBs from header to current BB, if hoisting this doesn't cause 1206 // high register pressure, then it's safe to proceed. 1207 if (!CanCauseHighRegPressure(Cost, CheapInstr)) { 1208 LLVM_DEBUG(dbgs() << "Hoist non-reg-pressure: " << MI); 1209 ++NumLowRP; 1210 return true; 1211 } 1212 1213 // Don't risk increasing register pressure if it would create copies. 1214 if (CreatesCopy) { 1215 LLVM_DEBUG(dbgs() << "Won't hoist instr with loop PHI use: " << MI); 1216 return false; 1217 } 1218 1219 // Do not "speculate" in high register pressure situation. If an 1220 // instruction is not guaranteed to be executed in the loop, it's best to be 1221 // conservative. 1222 if (AvoidSpeculation && 1223 (!IsGuaranteedToExecute(MI.getParent()) && !MayCSE(&MI))) { 1224 LLVM_DEBUG(dbgs() << "Won't speculate: " << MI); 1225 return false; 1226 } 1227 1228 // High register pressure situation, only hoist if the instruction is going 1229 // to be remat'ed. 1230 if (!isTriviallyReMaterializable(MI, AA) && 1231 !MI.isDereferenceableInvariantLoad(AA)) { 1232 LLVM_DEBUG(dbgs() << "Can't remat / high reg-pressure: " << MI); 1233 return false; 1234 } 1235 1236 return true; 1237 } 1238 1239 /// Unfold a load from the given machineinstr if the load itself could be 1240 /// hoisted. Return the unfolded and hoistable load, or null if the load 1241 /// couldn't be unfolded or if it wouldn't be hoistable. 1242 MachineInstr *MachineLICMBase::ExtractHoistableLoad(MachineInstr *MI) { 1243 // Don't unfold simple loads. 1244 if (MI->canFoldAsLoad()) 1245 return nullptr; 1246 1247 // If not, we may be able to unfold a load and hoist that. 1248 // First test whether the instruction is loading from an amenable 1249 // memory location. 1250 if (!MI->isDereferenceableInvariantLoad(AA)) 1251 return nullptr; 1252 1253 // Next determine the register class for a temporary register. 1254 unsigned LoadRegIndex; 1255 unsigned NewOpc = 1256 TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(), 1257 /*UnfoldLoad=*/true, 1258 /*UnfoldStore=*/false, 1259 &LoadRegIndex); 1260 if (NewOpc == 0) return nullptr; 1261 const MCInstrDesc &MID = TII->get(NewOpc); 1262 MachineFunction &MF = *MI->getMF(); 1263 const TargetRegisterClass *RC = TII->getRegClass(MID, LoadRegIndex, TRI, MF); 1264 // Ok, we're unfolding. Create a temporary register and do the unfold. 1265 Register Reg = MRI->createVirtualRegister(RC); 1266 1267 SmallVector<MachineInstr *, 2> NewMIs; 1268 bool Success = TII->unfoldMemoryOperand(MF, *MI, Reg, 1269 /*UnfoldLoad=*/true, 1270 /*UnfoldStore=*/false, NewMIs); 1271 (void)Success; 1272 assert(Success && 1273 "unfoldMemoryOperand failed when getOpcodeAfterMemoryUnfold " 1274 "succeeded!"); 1275 assert(NewMIs.size() == 2 && 1276 "Unfolded a load into multiple instructions!"); 1277 MachineBasicBlock *MBB = MI->getParent(); 1278 MachineBasicBlock::iterator Pos = MI; 1279 MBB->insert(Pos, NewMIs[0]); 1280 MBB->insert(Pos, NewMIs[1]); 1281 // If unfolding produced a load that wasn't loop-invariant or profitable to 1282 // hoist, discard the new instructions and bail. 1283 if (!IsLoopInvariantInst(*NewMIs[0]) || !IsProfitableToHoist(*NewMIs[0])) { 1284 NewMIs[0]->eraseFromParent(); 1285 NewMIs[1]->eraseFromParent(); 1286 return nullptr; 1287 } 1288 1289 // Update register pressure for the unfolded instruction. 1290 UpdateRegPressure(NewMIs[1]); 1291 1292 // Otherwise we successfully unfolded a load that we can hoist. 1293 1294 // Update the call site info. 1295 if (MI->shouldUpdateCallSiteInfo()) 1296 MF.eraseCallSiteInfo(MI); 1297 1298 MI->eraseFromParent(); 1299 return NewMIs[0]; 1300 } 1301 1302 /// Initialize the CSE map with instructions that are in the current loop 1303 /// preheader that may become duplicates of instructions that are hoisted 1304 /// out of the loop. 1305 void MachineLICMBase::InitCSEMap(MachineBasicBlock *BB) { 1306 for (MachineInstr &MI : *BB) 1307 CSEMap[MI.getOpcode()].push_back(&MI); 1308 } 1309 1310 /// Find an instruction amount PrevMIs that is a duplicate of MI. 1311 /// Return this instruction if it's found. 1312 MachineInstr * 1313 MachineLICMBase::LookForDuplicate(const MachineInstr *MI, 1314 std::vector<MachineInstr *> &PrevMIs) { 1315 for (MachineInstr *PrevMI : PrevMIs) 1316 if (TII->produceSameValue(*MI, *PrevMI, (PreRegAlloc ? MRI : nullptr))) 1317 return PrevMI; 1318 1319 return nullptr; 1320 } 1321 1322 /// Given a LICM'ed instruction, look for an instruction on the preheader that 1323 /// computes the same value. If it's found, do a RAU on with the definition of 1324 /// the existing instruction rather than hoisting the instruction to the 1325 /// preheader. 1326 bool MachineLICMBase::EliminateCSE( 1327 MachineInstr *MI, 1328 DenseMap<unsigned, std::vector<MachineInstr *>>::iterator &CI) { 1329 // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate 1330 // the undef property onto uses. 1331 if (CI == CSEMap.end() || MI->isImplicitDef()) 1332 return false; 1333 1334 if (MachineInstr *Dup = LookForDuplicate(MI, CI->second)) { 1335 LLVM_DEBUG(dbgs() << "CSEing " << *MI << " with " << *Dup); 1336 1337 // Replace virtual registers defined by MI by their counterparts defined 1338 // by Dup. 1339 SmallVector<unsigned, 2> Defs; 1340 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1341 const MachineOperand &MO = MI->getOperand(i); 1342 1343 // Physical registers may not differ here. 1344 assert((!MO.isReg() || MO.getReg() == 0 || 1345 !Register::isPhysicalRegister(MO.getReg()) || 1346 MO.getReg() == Dup->getOperand(i).getReg()) && 1347 "Instructions with different phys regs are not identical!"); 1348 1349 if (MO.isReg() && MO.isDef() && 1350 !Register::isPhysicalRegister(MO.getReg())) 1351 Defs.push_back(i); 1352 } 1353 1354 SmallVector<const TargetRegisterClass*, 2> OrigRCs; 1355 for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 1356 unsigned Idx = Defs[i]; 1357 Register Reg = MI->getOperand(Idx).getReg(); 1358 Register DupReg = Dup->getOperand(Idx).getReg(); 1359 OrigRCs.push_back(MRI->getRegClass(DupReg)); 1360 1361 if (!MRI->constrainRegClass(DupReg, MRI->getRegClass(Reg))) { 1362 // Restore old RCs if more than one defs. 1363 for (unsigned j = 0; j != i; ++j) 1364 MRI->setRegClass(Dup->getOperand(Defs[j]).getReg(), OrigRCs[j]); 1365 return false; 1366 } 1367 } 1368 1369 for (unsigned Idx : Defs) { 1370 Register Reg = MI->getOperand(Idx).getReg(); 1371 Register DupReg = Dup->getOperand(Idx).getReg(); 1372 MRI->replaceRegWith(Reg, DupReg); 1373 MRI->clearKillFlags(DupReg); 1374 // Clear Dup dead flag if any, we reuse it for Reg. 1375 if (!MRI->use_nodbg_empty(DupReg)) 1376 Dup->getOperand(Idx).setIsDead(false); 1377 } 1378 1379 MI->eraseFromParent(); 1380 ++NumCSEed; 1381 return true; 1382 } 1383 return false; 1384 } 1385 1386 /// Return true if the given instruction will be CSE'd if it's hoisted out of 1387 /// the loop. 1388 bool MachineLICMBase::MayCSE(MachineInstr *MI) { 1389 unsigned Opcode = MI->getOpcode(); 1390 DenseMap<unsigned, std::vector<MachineInstr *>>::iterator CI = 1391 CSEMap.find(Opcode); 1392 // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate 1393 // the undef property onto uses. 1394 if (CI == CSEMap.end() || MI->isImplicitDef()) 1395 return false; 1396 1397 return LookForDuplicate(MI, CI->second) != nullptr; 1398 } 1399 1400 /// When an instruction is found to use only loop invariant operands 1401 /// that are safe to hoist, this instruction is called to do the dirty work. 1402 /// It returns true if the instruction is hoisted. 1403 bool MachineLICMBase::Hoist(MachineInstr *MI, MachineBasicBlock *Preheader) { 1404 MachineBasicBlock *SrcBlock = MI->getParent(); 1405 1406 // Disable the instruction hoisting due to block hotness 1407 if ((DisableHoistingToHotterBlocks == UseBFI::All || 1408 (DisableHoistingToHotterBlocks == UseBFI::PGO && HasProfileData)) && 1409 isTgtHotterThanSrc(SrcBlock, Preheader)) { 1410 ++NumNotHoistedDueToHotness; 1411 return false; 1412 } 1413 // First check whether we should hoist this instruction. 1414 if (!IsLoopInvariantInst(*MI) || !IsProfitableToHoist(*MI)) { 1415 // If not, try unfolding a hoistable load. 1416 MI = ExtractHoistableLoad(MI); 1417 if (!MI) return false; 1418 } 1419 1420 // If we have hoisted an instruction that may store, it can only be a constant 1421 // store. 1422 if (MI->mayStore()) 1423 NumStoreConst++; 1424 1425 // Now move the instructions to the predecessor, inserting it before any 1426 // terminator instructions. 1427 LLVM_DEBUG({ 1428 dbgs() << "Hoisting " << *MI; 1429 if (MI->getParent()->getBasicBlock()) 1430 dbgs() << " from " << printMBBReference(*MI->getParent()); 1431 if (Preheader->getBasicBlock()) 1432 dbgs() << " to " << printMBBReference(*Preheader); 1433 dbgs() << "\n"; 1434 }); 1435 1436 // If this is the first instruction being hoisted to the preheader, 1437 // initialize the CSE map with potential common expressions. 1438 if (FirstInLoop) { 1439 InitCSEMap(Preheader); 1440 FirstInLoop = false; 1441 } 1442 1443 // Look for opportunity to CSE the hoisted instruction. 1444 unsigned Opcode = MI->getOpcode(); 1445 DenseMap<unsigned, std::vector<MachineInstr *>>::iterator CI = 1446 CSEMap.find(Opcode); 1447 if (!EliminateCSE(MI, CI)) { 1448 // Otherwise, splice the instruction to the preheader. 1449 Preheader->splice(Preheader->getFirstTerminator(),MI->getParent(),MI); 1450 1451 // Since we are moving the instruction out of its basic block, we do not 1452 // retain its debug location. Doing so would degrade the debugging 1453 // experience and adversely affect the accuracy of profiling information. 1454 assert(!MI->isDebugInstr() && "Should not hoist debug inst"); 1455 MI->setDebugLoc(DebugLoc()); 1456 1457 // Update register pressure for BBs from header to this block. 1458 UpdateBackTraceRegPressure(MI); 1459 1460 // Clear the kill flags of any register this instruction defines, 1461 // since they may need to be live throughout the entire loop 1462 // rather than just live for part of it. 1463 for (MachineOperand &MO : MI->operands()) 1464 if (MO.isReg() && MO.isDef() && !MO.isDead()) 1465 MRI->clearKillFlags(MO.getReg()); 1466 1467 // Add to the CSE map. 1468 if (CI != CSEMap.end()) 1469 CI->second.push_back(MI); 1470 else 1471 CSEMap[Opcode].push_back(MI); 1472 } 1473 1474 ++NumHoisted; 1475 Changed = true; 1476 1477 return true; 1478 } 1479 1480 /// Get the preheader for the current loop, splitting a critical edge if needed. 1481 MachineBasicBlock *MachineLICMBase::getCurPreheader() { 1482 // Determine the block to which to hoist instructions. If we can't find a 1483 // suitable loop predecessor, we can't do any hoisting. 1484 1485 // If we've tried to get a preheader and failed, don't try again. 1486 if (CurPreheader == reinterpret_cast<MachineBasicBlock *>(-1)) 1487 return nullptr; 1488 1489 if (!CurPreheader) { 1490 CurPreheader = CurLoop->getLoopPreheader(); 1491 if (!CurPreheader) { 1492 MachineBasicBlock *Pred = CurLoop->getLoopPredecessor(); 1493 if (!Pred) { 1494 CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1); 1495 return nullptr; 1496 } 1497 1498 CurPreheader = Pred->SplitCriticalEdge(CurLoop->getHeader(), *this); 1499 if (!CurPreheader) { 1500 CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1); 1501 return nullptr; 1502 } 1503 } 1504 } 1505 return CurPreheader; 1506 } 1507 1508 /// Is the target basic block at least "BlockFrequencyRatioThreshold" 1509 /// times hotter than the source basic block. 1510 bool MachineLICMBase::isTgtHotterThanSrc(MachineBasicBlock *SrcBlock, 1511 MachineBasicBlock *TgtBlock) { 1512 // Parse source and target basic block frequency from MBFI 1513 uint64_t SrcBF = MBFI->getBlockFreq(SrcBlock).getFrequency(); 1514 uint64_t DstBF = MBFI->getBlockFreq(TgtBlock).getFrequency(); 1515 1516 // Disable the hoisting if source block frequency is zero 1517 if (!SrcBF) 1518 return true; 1519 1520 double Ratio = (double)DstBF / SrcBF; 1521 1522 // Compare the block frequency ratio with the threshold 1523 return Ratio > BlockFrequencyRatioThreshold; 1524 } 1525