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