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