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