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