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