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