MachineLICM.cpp revision 221345
160812Sps//===-- MachineLICM.cpp - Machine Loop Invariant Code Motion Pass ---------===// 260786Sps// 3128348Stjr// The LLVM Compiler Infrastructure 460786Sps// 560786Sps// This file is distributed under the University of Illinois Open Source 660786Sps// License. See LICENSE.TXT for details. 760786Sps// 860786Sps//===----------------------------------------------------------------------===// 960786Sps// 1060786Sps// This pass performs loop invariant code motion on machine instructions. We 1160786Sps// attempt to remove as much code from the body of a loop as possible. 1260786Sps// 1360786Sps// This pass does not attempt to throttle itself to limit register pressure. 1460786Sps// The register allocation phases are expected to perform rematerialization 1560786Sps// to recover when register pressure is high. 1660786Sps// 1760786Sps// This pass is not intended to be a replacement or a complete alternative 1889022Sps// for the LLVM-IR-level LICM pass. It is only designed to hoist simple 1989022Sps// constructs that are not exposed before lowering and instruction selection. 2089022Sps// 2160786Sps//===----------------------------------------------------------------------===// 2260786Sps 2360786Sps#define DEBUG_TYPE "machine-licm" 2460786Sps#include "llvm/CodeGen/Passes.h" 2560786Sps#include "llvm/CodeGen/MachineDominators.h" 2660786Sps#include "llvm/CodeGen/MachineFrameInfo.h" 2760786Sps#include "llvm/CodeGen/MachineLoopInfo.h" 2860786Sps#include "llvm/CodeGen/MachineMemOperand.h" 2960786Sps#include "llvm/CodeGen/MachineRegisterInfo.h" 3060786Sps#include "llvm/CodeGen/PseudoSourceValue.h" 3160786Sps#include "llvm/Target/TargetLowering.h" 3260786Sps#include "llvm/Target/TargetRegisterInfo.h" 3360786Sps#include "llvm/Target/TargetInstrInfo.h" 3460786Sps#include "llvm/Target/TargetInstrItineraries.h" 3560786Sps#include "llvm/Target/TargetMachine.h" 3660812Sps#include "llvm/Analysis/AliasAnalysis.h" 3760786Sps#include "llvm/ADT/DenseMap.h" 3860786Sps#include "llvm/ADT/SmallSet.h" 3960786Sps#include "llvm/ADT/Statistic.h" 4060786Sps#include "llvm/Support/Debug.h" 4160786Sps#include "llvm/Support/raw_ostream.h" 4260786Spsusing namespace llvm; 4360786Sps 4460786SpsSTATISTIC(NumHoisted, 4560786Sps "Number of machine instructions hoisted out of loops"); 4660786SpsSTATISTIC(NumLowRP, 4760786Sps "Number of instructions hoisted in low reg pressure situation"); 4860786SpsSTATISTIC(NumHighLatency, 4960786Sps "Number of high latency instructions hoisted"); 5089022SpsSTATISTIC(NumCSEed, 5160786Sps "Number of hoisted machine instructions CSEed"); 5260786SpsSTATISTIC(NumPostRAHoisted, 5360786Sps "Number of machine instructions hoisted out of loops post regalloc"); 5460786Sps 5589022Spsnamespace { 5689022Sps class MachineLICM : public MachineFunctionPass { 5789022Sps bool PreRegAlloc; 5889022Sps 5960786Sps const TargetMachine *TM; 6060786Sps const TargetInstrInfo *TII; 6160786Sps const TargetLowering *TLI; 6260786Sps const TargetRegisterInfo *TRI; 6360786Sps const MachineFrameInfo *MFI; 6460786Sps MachineRegisterInfo *MRI; 6560786Sps const InstrItineraryData *InstrItins; 6660786Sps 6760786Sps // Various analyses that we use... 6860786Sps AliasAnalysis *AA; // Alias analysis info. 6960786Sps MachineLoopInfo *MLI; // Current MachineLoopInfo 7060786Sps MachineDominatorTree *DT; // Machine dominator tree for the cur loop 7160786Sps 7260786Sps // State that is updated as we process loops 7360812Sps bool Changed; // True if a loop is changed. 7460786Sps bool FirstInLoop; // True if it's the first LICM in the loop. 7560786Sps MachineLoop *CurLoop; // The current loop we are working on. 7660786Sps MachineBasicBlock *CurPreheader; // The preheader for CurLoop. 7760786Sps 7860786Sps BitVector AllocatableSet; 7960786Sps 8060786Sps // Track 'estimated' register pressure. 8160786Sps SmallSet<unsigned, 32> RegSeen; 8260786Sps SmallVector<unsigned, 8> RegPressure; 8360786Sps 8460786Sps // Register pressure "limit" per register class. If the pressure 8560786Sps // is higher than the limit, then it's considered high. 8660786Sps SmallVector<unsigned, 8> RegLimit; 8760786Sps 8860786Sps // Register pressure on path leading from loop preheader to current BB. 8960786Sps SmallVector<SmallVector<unsigned, 8>, 16> BackTrace; 9060786Sps 9160786Sps // For each opcode, keep a list of potential CSE instructions. 9260786Sps DenseMap<unsigned, std::vector<const MachineInstr*> > CSEMap; 9360786Sps 9460786Sps public: 9560786Sps static char ID; // Pass identification, replacement for typeid 9660786Sps MachineLICM() : 9760786Sps MachineFunctionPass(ID), PreRegAlloc(true) { 9860786Sps initializeMachineLICMPass(*PassRegistry::getPassRegistry()); 9960786Sps } 10060786Sps 10160786Sps explicit MachineLICM(bool PreRA) : 10260786Sps MachineFunctionPass(ID), PreRegAlloc(PreRA) { 10360786Sps initializeMachineLICMPass(*PassRegistry::getPassRegistry()); 10460786Sps } 10560786Sps 10660786Sps virtual bool runOnMachineFunction(MachineFunction &MF); 10789022Sps 10860786Sps const char *getPassName() const { return "Machine Instruction LICM"; } 10960786Sps 11060786Sps virtual void getAnalysisUsage(AnalysisUsage &AU) const { 11160786Sps AU.addRequired<MachineLoopInfo>(); 11260786Sps AU.addRequired<MachineDominatorTree>(); 11360786Sps AU.addRequired<AliasAnalysis>(); 11460812Sps AU.addPreserved<MachineLoopInfo>(); 11560812Sps AU.addPreserved<MachineDominatorTree>(); 11660812Sps MachineFunctionPass::getAnalysisUsage(AU); 11760786Sps } 11860786Sps 11960786Sps virtual void releaseMemory() { 12060786Sps RegSeen.clear(); 12160786Sps RegPressure.clear(); 12260786Sps RegLimit.clear(); 12360786Sps BackTrace.clear(); 12460812Sps for (DenseMap<unsigned,std::vector<const MachineInstr*> >::iterator 12560812Sps CI = CSEMap.begin(), CE = CSEMap.end(); CI != CE; ++CI) 12660812Sps CI->second.clear(); 12760812Sps CSEMap.clear(); 12860812Sps } 12960812Sps 13060812Sps private: 13160812Sps /// CandidateInfo - Keep track of information about hoisting candidates. 13260812Sps struct CandidateInfo { 13360812Sps MachineInstr *MI; 13460786Sps unsigned Def; 13560786Sps int FI; 13660786Sps CandidateInfo(MachineInstr *mi, unsigned def, int fi) 13760786Sps : MI(mi), Def(def), FI(fi) {} 13860786Sps }; 13960786Sps 14060786Sps /// HoistRegionPostRA - Walk the specified region of the CFG and hoist loop 14160786Sps /// invariants out to the preheader. 14260786Sps void HoistRegionPostRA(); 14360786Sps 14460786Sps /// HoistPostRA - When an instruction is found to only use loop invariant 14560786Sps /// operands that is safe to hoist, this instruction is called to do the 14660786Sps /// dirty work. 14760786Sps void HoistPostRA(MachineInstr *MI, unsigned Def); 14860786Sps 14960786Sps /// ProcessMI - Examine the instruction for potentai LICM candidate. Also 15060786Sps /// gather register def and frame object update information. 15160786Sps void ProcessMI(MachineInstr *MI, unsigned *PhysRegDefs, 15260786Sps SmallSet<int, 32> &StoredFIs, 15360786Sps SmallVector<CandidateInfo, 32> &Candidates); 15460786Sps 15560786Sps /// AddToLiveIns - Add register 'Reg' to the livein sets of BBs in the 15660786Sps /// current loop. 15760786Sps void AddToLiveIns(unsigned Reg); 15860786Sps 15960786Sps /// IsLICMCandidate - Returns true if the instruction may be a suitable 16060786Sps /// candidate for LICM. e.g. If the instruction is a call, then it's 16160786Sps /// obviously not safe to hoist it. 16260786Sps bool IsLICMCandidate(MachineInstr &I); 16360786Sps 16460786Sps /// IsLoopInvariantInst - Returns true if the instruction is loop 16560786Sps /// invariant. I.e., all virtual register operands are defined outside of 16660786Sps /// the loop, physical registers aren't accessed (explicitly or implicitly), 16760786Sps /// and the instruction is hoistable. 16860786Sps /// 16960786Sps bool IsLoopInvariantInst(MachineInstr &I); 17060786Sps 17160786Sps /// HasAnyPHIUse - Return true if the specified register is used by any 17260786Sps /// phi node. 17360786Sps bool HasAnyPHIUse(unsigned Reg) const; 17460786Sps 17560786Sps /// HasHighOperandLatency - Compute operand latency between a def of 'Reg' 17660786Sps /// and an use in the current loop, return true if the target considered 17760786Sps /// it 'high'. 17860786Sps bool HasHighOperandLatency(MachineInstr &MI, unsigned DefIdx, 17960786Sps unsigned Reg) const; 180128348Stjr 18189022Sps bool IsCheapInstruction(MachineInstr &MI) const; 18260786Sps 18360786Sps /// CanCauseHighRegPressure - Visit BBs from header to current BB, 18460786Sps /// check if hoisting an instruction of the given cost matrix can cause high 18560786Sps /// register pressure. 18660786Sps bool CanCauseHighRegPressure(DenseMap<unsigned, int> &Cost); 18760786Sps 18860786Sps /// UpdateBackTraceRegPressure - Traverse the back trace from header to 18960786Sps /// the current block and update their register pressures to reflect the 19060786Sps /// effect of hoisting MI from the current block to the preheader. 19160786Sps void UpdateBackTraceRegPressure(const MachineInstr *MI); 19260786Sps 19360786Sps /// IsProfitableToHoist - Return true if it is potentially profitable to 19460786Sps /// hoist the given loop invariant. 195128348Stjr bool IsProfitableToHoist(MachineInstr &MI); 196128348Stjr 197128348Stjr /// HoistRegion - Walk the specified region of the CFG (defined by all 198128348Stjr /// blocks dominated by the specified block, and that are in the current 19960786Sps /// loop) in depth first order w.r.t the DominatorTree. This allows us to 20060786Sps /// visit definitions before uses, allowing us to hoist a loop body in one 201128348Stjr /// pass without iteration. 202128348Stjr /// 203128348Stjr void HoistRegion(MachineDomTreeNode *N, bool IsHeader = false); 204128348Stjr 205128348Stjr /// InitRegPressure - Find all virtual register references that are liveout 206128348Stjr /// of the preheader to initialize the starting "register pressure". Note 20760786Sps /// this does not count live through (livein but not used) registers. 20860786Sps void InitRegPressure(MachineBasicBlock *BB); 20960786Sps 21060786Sps /// UpdateRegPressure - Update estimate of register pressure after the 21160786Sps /// specified instruction. 21260786Sps void UpdateRegPressure(const MachineInstr *MI); 21360786Sps 21460786Sps /// ExtractHoistableLoad - Unfold a load from the given machineinstr if 21560786Sps /// the load itself could be hoisted. Return the unfolded and hoistable 21660786Sps /// load, or null if the load couldn't be unfolded or if it wouldn't 21760786Sps /// be hoistable. 21860786Sps MachineInstr *ExtractHoistableLoad(MachineInstr *MI); 21960786Sps 22060786Sps /// LookForDuplicate - Find an instruction amount PrevMIs that is a 22160786Sps /// duplicate of MI. Return this instruction if it's found. 22260786Sps const MachineInstr *LookForDuplicate(const MachineInstr *MI, 22360786Sps std::vector<const MachineInstr*> &PrevMIs); 22460786Sps 22560786Sps /// EliminateCSE - Given a LICM'ed instruction, look for an instruction on 22660786Sps /// the preheader that compute the same value. If it's found, do a RAU on 22760786Sps /// with the definition of the existing instruction rather than hoisting 22860786Sps /// the instruction to the preheader. 22960786Sps bool EliminateCSE(MachineInstr *MI, 23060786Sps DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator &CI); 23160786Sps 23260812Sps /// Hoist - When an instruction is found to only use loop invariant operands 23360786Sps /// that is safe to hoist, this instruction is called to do the dirty work. 23460786Sps /// It returns true if the instruction is hoisted. 235128348Stjr bool Hoist(MachineInstr *MI, MachineBasicBlock *Preheader); 23660786Sps 23760786Sps /// InitCSEMap - Initialize the CSE map with instructions that are in the 23860786Sps /// current loop preheader that may become duplicates of instructions that 23960786Sps /// are hoisted out of the loop. 24060786Sps void InitCSEMap(MachineBasicBlock *BB); 24160786Sps 24260786Sps /// getCurPreheader - Get the preheader for the current loop, splitting 24389022Sps /// a critical edge if needed. 24460786Sps MachineBasicBlock *getCurPreheader(); 24560786Sps }; 24660786Sps} // end anonymous namespace 24760786Sps 24860786Spschar MachineLICM::ID = 0; 24960786SpsINITIALIZE_PASS_BEGIN(MachineLICM, "machinelicm", 25060786Sps "Machine Loop Invariant Code Motion", false, false) 25160786SpsINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 25260786SpsINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 25360786SpsINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 25460786SpsINITIALIZE_PASS_END(MachineLICM, "machinelicm", 25560786Sps "Machine Loop Invariant Code Motion", false, false) 25660786Sps 25760786SpsFunctionPass *llvm::createMachineLICMPass(bool PreRegAlloc) { 25860786Sps return new MachineLICM(PreRegAlloc); 25960786Sps} 26060786Sps 26160786Sps/// LoopIsOuterMostWithPredecessor - Test if the given loop is the outer-most 26260786Sps/// loop that has a unique predecessor. 26360786Spsstatic bool LoopIsOuterMostWithPredecessor(MachineLoop *CurLoop) { 26460786Sps // Check whether this loop even has a unique predecessor. 26560786Sps if (!CurLoop->getLoopPredecessor()) 26660786Sps return false; 26760786Sps // Ok, now check to see if any of its outer loops do. 26860786Sps for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop()) 26960786Sps if (L->getLoopPredecessor()) 27060786Sps return false; 27160786Sps // None of them did, so this is the outermost with a unique predecessor. 27260786Sps return true; 27360786Sps} 27460786Sps 27560786Spsbool MachineLICM::runOnMachineFunction(MachineFunction &MF) { 27660786Sps if (PreRegAlloc) 27760786Sps DEBUG(dbgs() << "******** Pre-regalloc Machine LICM: "); 27860786Sps else 27960786Sps DEBUG(dbgs() << "******** Post-regalloc Machine LICM: "); 28060786Sps DEBUG(dbgs() << MF.getFunction()->getName() << " ********\n"); 28160786Sps 28260786Sps Changed = FirstInLoop = false; 283128348Stjr TM = &MF.getTarget(); 28460786Sps TII = TM->getInstrInfo(); 28560786Sps TLI = TM->getTargetLowering(); 28660786Sps TRI = TM->getRegisterInfo(); 28760786Sps MFI = MF.getFrameInfo(); 28860786Sps MRI = &MF.getRegInfo(); 28960786Sps InstrItins = TM->getInstrItineraryData(); 29060786Sps AllocatableSet = TRI->getAllocatableSet(MF); 29160786Sps 29260786Sps if (PreRegAlloc) { 29360786Sps // Estimate register pressure during pre-regalloc pass. 29460786Sps unsigned NumRC = TRI->getNumRegClasses(); 29560786Sps RegPressure.resize(NumRC); 29660786Sps std::fill(RegPressure.begin(), RegPressure.end(), 0); 29760786Sps RegLimit.resize(NumRC); 29860786Sps for (TargetRegisterInfo::regclass_iterator I = TRI->regclass_begin(), 29960786Sps E = TRI->regclass_end(); I != E; ++I) 30060786Sps RegLimit[(*I)->getID()] = TRI->getRegPressureLimit(*I, MF); 30160786Sps } 30260786Sps 30360786Sps // Get our Loop information... 30460786Sps MLI = &getAnalysis<MachineLoopInfo>(); 30560786Sps DT = &getAnalysis<MachineDominatorTree>(); 30660786Sps AA = &getAnalysis<AliasAnalysis>(); 30760786Sps 30860786Sps SmallVector<MachineLoop *, 8> Worklist(MLI->begin(), MLI->end()); 30960786Sps while (!Worklist.empty()) { 31060786Sps CurLoop = Worklist.pop_back_val(); 31160786Sps CurPreheader = 0; 31260786Sps 31360786Sps // If this is done before regalloc, only visit outer-most preheader-sporting 31460786Sps // loops. 31560786Sps if (PreRegAlloc && !LoopIsOuterMostWithPredecessor(CurLoop)) { 31660786Sps Worklist.append(CurLoop->begin(), CurLoop->end()); 31760786Sps continue; 318128348Stjr } 31960786Sps 32060786Sps if (!PreRegAlloc) 32160786Sps HoistRegionPostRA(); 32260786Sps else { 32360786Sps // CSEMap is initialized for loop header when the first instruction is 32460786Sps // being hoisted. 32560786Sps MachineDomTreeNode *N = DT->getNode(CurLoop->getHeader()); 32660786Sps FirstInLoop = true; 32760786Sps HoistRegion(N, true); 32860786Sps CSEMap.clear(); 32960786Sps } 33060786Sps } 33160786Sps 33260786Sps return Changed; 33360786Sps} 33460786Sps 33560786Sps/// InstructionStoresToFI - Return true if instruction stores to the 33660786Sps/// specified frame. 33760786Spsstatic bool InstructionStoresToFI(const MachineInstr *MI, int FI) { 33860786Sps for (MachineInstr::mmo_iterator o = MI->memoperands_begin(), 33960786Sps oe = MI->memoperands_end(); o != oe; ++o) { 34060786Sps if (!(*o)->isStore() || !(*o)->getValue()) 34160786Sps continue; 34260786Sps if (const FixedStackPseudoSourceValue *Value = 34360786Sps dyn_cast<const FixedStackPseudoSourceValue>((*o)->getValue())) { 34460786Sps if (Value->getFrameIndex() == FI) 34560786Sps return true; 34660786Sps } 34760786Sps } 34860786Sps return false; 34960786Sps} 35060786Sps 35160786Sps/// ProcessMI - Examine the instruction for potentai LICM candidate. Also 35260786Sps/// gather register def and frame object update information. 35360786Spsvoid MachineLICM::ProcessMI(MachineInstr *MI, 35460786Sps unsigned *PhysRegDefs, 35560786Sps SmallSet<int, 32> &StoredFIs, 35660786Sps SmallVector<CandidateInfo, 32> &Candidates) { 35760786Sps bool RuledOut = false; 35860786Sps bool HasNonInvariantUse = false; 35960786Sps unsigned Def = 0; 36060786Sps for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 36160786Sps const MachineOperand &MO = MI->getOperand(i); 36260786Sps if (MO.isFI()) { 36360786Sps // Remember if the instruction stores to the frame index. 36460786Sps int FI = MO.getIndex(); 36560786Sps if (!StoredFIs.count(FI) && 36660786Sps MFI->isSpillSlotObjectIndex(FI) && 36760786Sps InstructionStoresToFI(MI, FI)) 36860786Sps StoredFIs.insert(FI); 36960786Sps HasNonInvariantUse = true; 37060786Sps continue; 37160786Sps } 37260786Sps 37360786Sps if (!MO.isReg()) 37460786Sps continue; 37560786Sps unsigned Reg = MO.getReg(); 37660786Sps if (!Reg) 37760786Sps continue; 37860786Sps assert(TargetRegisterInfo::isPhysicalRegister(Reg) && 37960786Sps "Not expecting virtual register!"); 38060786Sps 38160786Sps if (!MO.isDef()) { 38260786Sps if (Reg && PhysRegDefs[Reg]) 38360786Sps // If it's using a non-loop-invariant register, then it's obviously not 38460786Sps // safe to hoist. 38560786Sps HasNonInvariantUse = true; 38660786Sps continue; 38760786Sps } 38860786Sps 38960786Sps if (MO.isImplicit()) { 39060786Sps ++PhysRegDefs[Reg]; 39160786Sps for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) 39260786Sps ++PhysRegDefs[*AS]; 39360786Sps if (!MO.isDead()) 39460786Sps // Non-dead implicit def? This cannot be hoisted. 39560786Sps RuledOut = true; 39660786Sps // No need to check if a dead implicit def is also defined by 39760786Sps // another instruction. 39860786Sps continue; 39960786Sps } 40060786Sps 40189022Sps // FIXME: For now, avoid instructions with multiple defs, unless 40289022Sps // it's a dead implicit def. 40389022Sps if (Def) 40460786Sps RuledOut = true; 40560786Sps else 40660786Sps Def = Reg; 407 408 // If we have already seen another instruction that defines the same 409 // register, then this is not safe. 410 if (++PhysRegDefs[Reg] > 1) 411 // MI defined register is seen defined by another instruction in 412 // the loop, it cannot be a LICM candidate. 413 RuledOut = true; 414 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) 415 if (++PhysRegDefs[*AS] > 1) 416 RuledOut = true; 417 } 418 419 // Only consider reloads for now and remats which do not have register 420 // operands. FIXME: Consider unfold load folding instructions. 421 if (Def && !RuledOut) { 422 int FI = INT_MIN; 423 if ((!HasNonInvariantUse && IsLICMCandidate(*MI)) || 424 (TII->isLoadFromStackSlot(MI, FI) && MFI->isSpillSlotObjectIndex(FI))) 425 Candidates.push_back(CandidateInfo(MI, Def, FI)); 426 } 427} 428 429/// HoistRegionPostRA - Walk the specified region of the CFG and hoist loop 430/// invariants out to the preheader. 431void MachineLICM::HoistRegionPostRA() { 432 unsigned NumRegs = TRI->getNumRegs(); 433 unsigned *PhysRegDefs = new unsigned[NumRegs]; 434 std::fill(PhysRegDefs, PhysRegDefs + NumRegs, 0); 435 436 SmallVector<CandidateInfo, 32> Candidates; 437 SmallSet<int, 32> StoredFIs; 438 439 // Walk the entire region, count number of defs for each register, and 440 // collect potential LICM candidates. 441 const std::vector<MachineBasicBlock*> Blocks = CurLoop->getBlocks(); 442 for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 443 MachineBasicBlock *BB = Blocks[i]; 444 // Conservatively treat live-in's as an external def. 445 // FIXME: That means a reload that're reused in successor block(s) will not 446 // be LICM'ed. 447 for (MachineBasicBlock::livein_iterator I = BB->livein_begin(), 448 E = BB->livein_end(); I != E; ++I) { 449 unsigned Reg = *I; 450 ++PhysRegDefs[Reg]; 451 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) 452 ++PhysRegDefs[*AS]; 453 } 454 455 for (MachineBasicBlock::iterator 456 MII = BB->begin(), E = BB->end(); MII != E; ++MII) { 457 MachineInstr *MI = &*MII; 458 ProcessMI(MI, PhysRegDefs, StoredFIs, Candidates); 459 } 460 } 461 462 // Now evaluate whether the potential candidates qualify. 463 // 1. Check if the candidate defined register is defined by another 464 // instruction in the loop. 465 // 2. If the candidate is a load from stack slot (always true for now), 466 // check if the slot is stored anywhere in the loop. 467 for (unsigned i = 0, e = Candidates.size(); i != e; ++i) { 468 if (Candidates[i].FI != INT_MIN && 469 StoredFIs.count(Candidates[i].FI)) 470 continue; 471 472 if (PhysRegDefs[Candidates[i].Def] == 1) { 473 bool Safe = true; 474 MachineInstr *MI = Candidates[i].MI; 475 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 476 const MachineOperand &MO = MI->getOperand(j); 477 if (!MO.isReg() || MO.isDef() || !MO.getReg()) 478 continue; 479 if (PhysRegDefs[MO.getReg()]) { 480 // If it's using a non-loop-invariant register, then it's obviously 481 // not safe to hoist. 482 Safe = false; 483 break; 484 } 485 } 486 if (Safe) 487 HoistPostRA(MI, Candidates[i].Def); 488 } 489 } 490 491 delete[] PhysRegDefs; 492} 493 494/// AddToLiveIns - Add register 'Reg' to the livein sets of BBs in the current 495/// loop, and make sure it is not killed by any instructions in the loop. 496void MachineLICM::AddToLiveIns(unsigned Reg) { 497 const std::vector<MachineBasicBlock*> Blocks = CurLoop->getBlocks(); 498 for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 499 MachineBasicBlock *BB = Blocks[i]; 500 if (!BB->isLiveIn(Reg)) 501 BB->addLiveIn(Reg); 502 for (MachineBasicBlock::iterator 503 MII = BB->begin(), E = BB->end(); MII != E; ++MII) { 504 MachineInstr *MI = &*MII; 505 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 506 MachineOperand &MO = MI->getOperand(i); 507 if (!MO.isReg() || !MO.getReg() || MO.isDef()) continue; 508 if (MO.getReg() == Reg || TRI->isSuperRegister(Reg, MO.getReg())) 509 MO.setIsKill(false); 510 } 511 } 512 } 513} 514 515/// HoistPostRA - When an instruction is found to only use loop invariant 516/// operands that is safe to hoist, this instruction is called to do the 517/// dirty work. 518void MachineLICM::HoistPostRA(MachineInstr *MI, unsigned Def) { 519 MachineBasicBlock *Preheader = getCurPreheader(); 520 if (!Preheader) return; 521 522 // Now move the instructions to the predecessor, inserting it before any 523 // terminator instructions. 524 DEBUG({ 525 dbgs() << "Hoisting " << *MI; 526 if (Preheader->getBasicBlock()) 527 dbgs() << " to MachineBasicBlock " 528 << Preheader->getName(); 529 if (MI->getParent()->getBasicBlock()) 530 dbgs() << " from MachineBasicBlock " 531 << MI->getParent()->getName(); 532 dbgs() << "\n"; 533 }); 534 535 // Splice the instruction to the preheader. 536 MachineBasicBlock *MBB = MI->getParent(); 537 Preheader->splice(Preheader->getFirstTerminator(), MBB, MI); 538 539 // Add register to livein list to all the BBs in the current loop since a 540 // loop invariant must be kept live throughout the whole loop. This is 541 // important to ensure later passes do not scavenge the def register. 542 AddToLiveIns(Def); 543 544 ++NumPostRAHoisted; 545 Changed = true; 546} 547 548/// HoistRegion - Walk the specified region of the CFG (defined by all blocks 549/// dominated by the specified block, and that are in the current loop) in depth 550/// first order w.r.t the DominatorTree. This allows us to visit definitions 551/// before uses, allowing us to hoist a loop body in one pass without iteration. 552/// 553void MachineLICM::HoistRegion(MachineDomTreeNode *N, bool IsHeader) { 554 assert(N != 0 && "Null dominator tree node?"); 555 MachineBasicBlock *BB = N->getBlock(); 556 557 // If this subregion is not in the top level loop at all, exit. 558 if (!CurLoop->contains(BB)) return; 559 560 MachineBasicBlock *Preheader = getCurPreheader(); 561 if (!Preheader) 562 return; 563 564 if (IsHeader) { 565 // Compute registers which are livein into the loop headers. 566 RegSeen.clear(); 567 BackTrace.clear(); 568 InitRegPressure(Preheader); 569 } 570 571 // Remember livein register pressure. 572 BackTrace.push_back(RegPressure); 573 574 for (MachineBasicBlock::iterator 575 MII = BB->begin(), E = BB->end(); MII != E; ) { 576 MachineBasicBlock::iterator NextMII = MII; ++NextMII; 577 MachineInstr *MI = &*MII; 578 if (!Hoist(MI, Preheader)) 579 UpdateRegPressure(MI); 580 MII = NextMII; 581 } 582 583 // Don't hoist things out of a large switch statement. This often causes 584 // code to be hoisted that wasn't going to be executed, and increases 585 // register pressure in a situation where it's likely to matter. 586 if (BB->succ_size() < 25) { 587 const std::vector<MachineDomTreeNode*> &Children = N->getChildren(); 588 for (unsigned I = 0, E = Children.size(); I != E; ++I) 589 HoistRegion(Children[I]); 590 } 591 592 BackTrace.pop_back(); 593} 594 595static bool isOperandKill(const MachineOperand &MO, MachineRegisterInfo *MRI) { 596 return MO.isKill() || MRI->hasOneNonDBGUse(MO.getReg()); 597} 598 599/// InitRegPressure - Find all virtual register references that are liveout of 600/// the preheader to initialize the starting "register pressure". Note this 601/// does not count live through (livein but not used) registers. 602void MachineLICM::InitRegPressure(MachineBasicBlock *BB) { 603 std::fill(RegPressure.begin(), RegPressure.end(), 0); 604 605 // If the preheader has only a single predecessor and it ends with a 606 // fallthrough or an unconditional branch, then scan its predecessor for live 607 // defs as well. This happens whenever the preheader is created by splitting 608 // the critical edge from the loop predecessor to the loop header. 609 if (BB->pred_size() == 1) { 610 MachineBasicBlock *TBB = 0, *FBB = 0; 611 SmallVector<MachineOperand, 4> Cond; 612 if (!TII->AnalyzeBranch(*BB, TBB, FBB, Cond, false) && Cond.empty()) 613 InitRegPressure(*BB->pred_begin()); 614 } 615 616 for (MachineBasicBlock::iterator MII = BB->begin(), E = BB->end(); 617 MII != E; ++MII) { 618 MachineInstr *MI = &*MII; 619 for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) { 620 const MachineOperand &MO = MI->getOperand(i); 621 if (!MO.isReg() || MO.isImplicit()) 622 continue; 623 unsigned Reg = MO.getReg(); 624 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 625 continue; 626 627 bool isNew = RegSeen.insert(Reg); 628 const TargetRegisterClass *RC = MRI->getRegClass(Reg); 629 EVT VT = *RC->vt_begin(); 630 unsigned RCId = TLI->getRepRegClassFor(VT)->getID(); 631 if (MO.isDef()) 632 RegPressure[RCId] += TLI->getRepRegClassCostFor(VT); 633 else { 634 bool isKill = isOperandKill(MO, MRI); 635 if (isNew && !isKill) 636 // Haven't seen this, it must be a livein. 637 RegPressure[RCId] += TLI->getRepRegClassCostFor(VT); 638 else if (!isNew && isKill) 639 RegPressure[RCId] -= TLI->getRepRegClassCostFor(VT); 640 } 641 } 642 } 643} 644 645/// UpdateRegPressure - Update estimate of register pressure after the 646/// specified instruction. 647void MachineLICM::UpdateRegPressure(const MachineInstr *MI) { 648 if (MI->isImplicitDef()) 649 return; 650 651 SmallVector<unsigned, 4> Defs; 652 for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) { 653 const MachineOperand &MO = MI->getOperand(i); 654 if (!MO.isReg() || MO.isImplicit()) 655 continue; 656 unsigned Reg = MO.getReg(); 657 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 658 continue; 659 660 bool isNew = RegSeen.insert(Reg); 661 if (MO.isDef()) 662 Defs.push_back(Reg); 663 else if (!isNew && isOperandKill(MO, MRI)) { 664 const TargetRegisterClass *RC = MRI->getRegClass(Reg); 665 EVT VT = *RC->vt_begin(); 666 unsigned RCId = TLI->getRepRegClassFor(VT)->getID(); 667 unsigned RCCost = TLI->getRepRegClassCostFor(VT); 668 669 if (RCCost > RegPressure[RCId]) 670 RegPressure[RCId] = 0; 671 else 672 RegPressure[RCId] -= RCCost; 673 } 674 } 675 676 while (!Defs.empty()) { 677 unsigned Reg = Defs.pop_back_val(); 678 const TargetRegisterClass *RC = MRI->getRegClass(Reg); 679 EVT VT = *RC->vt_begin(); 680 unsigned RCId = TLI->getRepRegClassFor(VT)->getID(); 681 unsigned RCCost = TLI->getRepRegClassCostFor(VT); 682 RegPressure[RCId] += RCCost; 683 } 684} 685 686/// IsLICMCandidate - Returns true if the instruction may be a suitable 687/// candidate for LICM. e.g. If the instruction is a call, then it's obviously 688/// not safe to hoist it. 689bool MachineLICM::IsLICMCandidate(MachineInstr &I) { 690 // Check if it's safe to move the instruction. 691 bool DontMoveAcrossStore = true; 692 if (!I.isSafeToMove(TII, AA, DontMoveAcrossStore)) 693 return false; 694 695 return true; 696} 697 698/// IsLoopInvariantInst - Returns true if the instruction is loop 699/// invariant. I.e., all virtual register operands are defined outside of the 700/// loop, physical registers aren't accessed explicitly, and there are no side 701/// effects that aren't captured by the operands or other flags. 702/// 703bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) { 704 if (!IsLICMCandidate(I)) 705 return false; 706 707 // The instruction is loop invariant if all of its operands are. 708 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 709 const MachineOperand &MO = I.getOperand(i); 710 711 if (!MO.isReg()) 712 continue; 713 714 unsigned Reg = MO.getReg(); 715 if (Reg == 0) continue; 716 717 // Don't hoist an instruction that uses or defines a physical register. 718 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 719 if (MO.isUse()) { 720 // If the physreg has no defs anywhere, it's just an ambient register 721 // and we can freely move its uses. Alternatively, if it's allocatable, 722 // it could get allocated to something with a def during allocation. 723 if (!MRI->def_empty(Reg)) 724 return false; 725 if (AllocatableSet.test(Reg)) 726 return false; 727 // Check for a def among the register's aliases too. 728 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 729 unsigned AliasReg = *Alias; 730 if (!MRI->def_empty(AliasReg)) 731 return false; 732 if (AllocatableSet.test(AliasReg)) 733 return false; 734 } 735 // Otherwise it's safe to move. 736 continue; 737 } else if (!MO.isDead()) { 738 // A def that isn't dead. We can't move it. 739 return false; 740 } else if (CurLoop->getHeader()->isLiveIn(Reg)) { 741 // If the reg is live into the loop, we can't hoist an instruction 742 // which would clobber it. 743 return false; 744 } 745 } 746 747 if (!MO.isUse()) 748 continue; 749 750 assert(MRI->getVRegDef(Reg) && 751 "Machine instr not mapped for this vreg?!"); 752 753 // If the loop contains the definition of an operand, then the instruction 754 // isn't loop invariant. 755 if (CurLoop->contains(MRI->getVRegDef(Reg))) 756 return false; 757 } 758 759 // If we got this far, the instruction is loop invariant! 760 return true; 761} 762 763 764/// HasAnyPHIUse - Return true if the specified register is used by any 765/// phi node. 766bool MachineLICM::HasAnyPHIUse(unsigned Reg) const { 767 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 768 UE = MRI->use_end(); UI != UE; ++UI) { 769 MachineInstr *UseMI = &*UI; 770 if (UseMI->isPHI()) 771 return true; 772 // Look pass copies as well. 773 if (UseMI->isCopy()) { 774 unsigned Def = UseMI->getOperand(0).getReg(); 775 if (TargetRegisterInfo::isVirtualRegister(Def) && 776 HasAnyPHIUse(Def)) 777 return true; 778 } 779 } 780 return false; 781} 782 783/// HasHighOperandLatency - Compute operand latency between a def of 'Reg' 784/// and an use in the current loop, return true if the target considered 785/// it 'high'. 786bool MachineLICM::HasHighOperandLatency(MachineInstr &MI, 787 unsigned DefIdx, unsigned Reg) const { 788 if (!InstrItins || InstrItins->isEmpty() || MRI->use_nodbg_empty(Reg)) 789 return false; 790 791 for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(Reg), 792 E = MRI->use_nodbg_end(); I != E; ++I) { 793 MachineInstr *UseMI = &*I; 794 if (UseMI->isCopyLike()) 795 continue; 796 if (!CurLoop->contains(UseMI->getParent())) 797 continue; 798 for (unsigned i = 0, e = UseMI->getNumOperands(); i != e; ++i) { 799 const MachineOperand &MO = UseMI->getOperand(i); 800 if (!MO.isReg() || !MO.isUse()) 801 continue; 802 unsigned MOReg = MO.getReg(); 803 if (MOReg != Reg) 804 continue; 805 806 if (TII->hasHighOperandLatency(InstrItins, MRI, &MI, DefIdx, UseMI, i)) 807 return true; 808 } 809 810 // Only look at the first in loop use. 811 break; 812 } 813 814 return false; 815} 816 817/// IsCheapInstruction - Return true if the instruction is marked "cheap" or 818/// the operand latency between its def and a use is one or less. 819bool MachineLICM::IsCheapInstruction(MachineInstr &MI) const { 820 if (MI.getDesc().isAsCheapAsAMove() || MI.isCopyLike()) 821 return true; 822 if (!InstrItins || InstrItins->isEmpty()) 823 return false; 824 825 bool isCheap = false; 826 unsigned NumDefs = MI.getDesc().getNumDefs(); 827 for (unsigned i = 0, e = MI.getNumOperands(); NumDefs && i != e; ++i) { 828 MachineOperand &DefMO = MI.getOperand(i); 829 if (!DefMO.isReg() || !DefMO.isDef()) 830 continue; 831 --NumDefs; 832 unsigned Reg = DefMO.getReg(); 833 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 834 continue; 835 836 if (!TII->hasLowDefLatency(InstrItins, &MI, i)) 837 return false; 838 isCheap = true; 839 } 840 841 return isCheap; 842} 843 844/// CanCauseHighRegPressure - Visit BBs from header to current BB, check 845/// if hoisting an instruction of the given cost matrix can cause high 846/// register pressure. 847bool MachineLICM::CanCauseHighRegPressure(DenseMap<unsigned, int> &Cost) { 848 for (DenseMap<unsigned, int>::iterator CI = Cost.begin(), CE = Cost.end(); 849 CI != CE; ++CI) { 850 if (CI->second <= 0) 851 continue; 852 853 unsigned RCId = CI->first; 854 for (unsigned i = BackTrace.size(); i != 0; --i) { 855 SmallVector<unsigned, 8> &RP = BackTrace[i-1]; 856 if (RP[RCId] + CI->second >= RegLimit[RCId]) 857 return true; 858 } 859 } 860 861 return false; 862} 863 864/// UpdateBackTraceRegPressure - Traverse the back trace from header to the 865/// current block and update their register pressures to reflect the effect 866/// of hoisting MI from the current block to the preheader. 867void MachineLICM::UpdateBackTraceRegPressure(const MachineInstr *MI) { 868 if (MI->isImplicitDef()) 869 return; 870 871 // First compute the 'cost' of the instruction, i.e. its contribution 872 // to register pressure. 873 DenseMap<unsigned, int> Cost; 874 for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) { 875 const MachineOperand &MO = MI->getOperand(i); 876 if (!MO.isReg() || MO.isImplicit()) 877 continue; 878 unsigned Reg = MO.getReg(); 879 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 880 continue; 881 882 const TargetRegisterClass *RC = MRI->getRegClass(Reg); 883 EVT VT = *RC->vt_begin(); 884 unsigned RCId = TLI->getRepRegClassFor(VT)->getID(); 885 unsigned RCCost = TLI->getRepRegClassCostFor(VT); 886 if (MO.isDef()) { 887 DenseMap<unsigned, int>::iterator CI = Cost.find(RCId); 888 if (CI != Cost.end()) 889 CI->second += RCCost; 890 else 891 Cost.insert(std::make_pair(RCId, RCCost)); 892 } else if (isOperandKill(MO, MRI)) { 893 DenseMap<unsigned, int>::iterator CI = Cost.find(RCId); 894 if (CI != Cost.end()) 895 CI->second -= RCCost; 896 else 897 Cost.insert(std::make_pair(RCId, -RCCost)); 898 } 899 } 900 901 // Update register pressure of blocks from loop header to current block. 902 for (unsigned i = 0, e = BackTrace.size(); i != e; ++i) { 903 SmallVector<unsigned, 8> &RP = BackTrace[i]; 904 for (DenseMap<unsigned, int>::iterator CI = Cost.begin(), CE = Cost.end(); 905 CI != CE; ++CI) { 906 unsigned RCId = CI->first; 907 RP[RCId] += CI->second; 908 } 909 } 910} 911 912/// IsProfitableToHoist - Return true if it is potentially profitable to hoist 913/// the given loop invariant. 914bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) { 915 if (MI.isImplicitDef()) 916 return true; 917 918 // If the instruction is cheap, only hoist if it is re-materilizable. LICM 919 // will increase register pressure. It's probably not worth it if the 920 // instruction is cheap. 921 // Also hoist loads from constant memory, e.g. load from stubs, GOT. Hoisting 922 // these tend to help performance in low register pressure situation. The 923 // trade off is it may cause spill in high pressure situation. It will end up 924 // adding a store in the loop preheader. But the reload is no more expensive. 925 // The side benefit is these loads are frequently CSE'ed. 926 if (IsCheapInstruction(MI)) { 927 if (!TII->isTriviallyReMaterializable(&MI, AA)) 928 return false; 929 } else { 930 // Estimate register pressure to determine whether to LICM the instruction. 931 // In low register pressure situation, we can be more aggressive about 932 // hoisting. Also, favors hoisting long latency instructions even in 933 // moderately high pressure situation. 934 // FIXME: If there are long latency loop-invariant instructions inside the 935 // loop at this point, why didn't the optimizer's LICM hoist them? 936 DenseMap<unsigned, int> Cost; 937 for (unsigned i = 0, e = MI.getDesc().getNumOperands(); i != e; ++i) { 938 const MachineOperand &MO = MI.getOperand(i); 939 if (!MO.isReg() || MO.isImplicit()) 940 continue; 941 unsigned Reg = MO.getReg(); 942 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 943 continue; 944 if (MO.isDef()) { 945 if (HasHighOperandLatency(MI, i, Reg)) { 946 ++NumHighLatency; 947 return true; 948 } 949 950 const TargetRegisterClass *RC = MRI->getRegClass(Reg); 951 EVT VT = *RC->vt_begin(); 952 unsigned RCId = TLI->getRepRegClassFor(VT)->getID(); 953 unsigned RCCost = TLI->getRepRegClassCostFor(VT); 954 DenseMap<unsigned, int>::iterator CI = Cost.find(RCId); 955 if (CI != Cost.end()) 956 CI->second += RCCost; 957 else 958 Cost.insert(std::make_pair(RCId, RCCost)); 959 } else if (isOperandKill(MO, MRI)) { 960 // Is a virtual register use is a kill, hoisting it out of the loop 961 // may actually reduce register pressure or be register pressure 962 // neutral. 963 const TargetRegisterClass *RC = MRI->getRegClass(Reg); 964 EVT VT = *RC->vt_begin(); 965 unsigned RCId = TLI->getRepRegClassFor(VT)->getID(); 966 unsigned RCCost = TLI->getRepRegClassCostFor(VT); 967 DenseMap<unsigned, int>::iterator CI = Cost.find(RCId); 968 if (CI != Cost.end()) 969 CI->second -= RCCost; 970 else 971 Cost.insert(std::make_pair(RCId, -RCCost)); 972 } 973 } 974 975 // Visit BBs from header to current BB, if hoisting this doesn't cause 976 // high register pressure, then it's safe to proceed. 977 if (!CanCauseHighRegPressure(Cost)) { 978 ++NumLowRP; 979 return true; 980 } 981 982 // High register pressure situation, only hoist if the instruction is going to 983 // be remat'ed. 984 if (!TII->isTriviallyReMaterializable(&MI, AA) && 985 !MI.isInvariantLoad(AA)) 986 return false; 987 } 988 989 // If result(s) of this instruction is used by PHIs outside of the loop, then 990 // don't hoist it if the instruction because it will introduce an extra copy. 991 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 992 const MachineOperand &MO = MI.getOperand(i); 993 if (!MO.isReg() || !MO.isDef()) 994 continue; 995 if (HasAnyPHIUse(MO.getReg())) 996 return false; 997 } 998 999 return true; 1000} 1001 1002MachineInstr *MachineLICM::ExtractHoistableLoad(MachineInstr *MI) { 1003 // Don't unfold simple loads. 1004 if (MI->getDesc().canFoldAsLoad()) 1005 return 0; 1006 1007 // If not, we may be able to unfold a load and hoist that. 1008 // First test whether the instruction is loading from an amenable 1009 // memory location. 1010 if (!MI->isInvariantLoad(AA)) 1011 return 0; 1012 1013 // Next determine the register class for a temporary register. 1014 unsigned LoadRegIndex; 1015 unsigned NewOpc = 1016 TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(), 1017 /*UnfoldLoad=*/true, 1018 /*UnfoldStore=*/false, 1019 &LoadRegIndex); 1020 if (NewOpc == 0) return 0; 1021 const TargetInstrDesc &TID = TII->get(NewOpc); 1022 if (TID.getNumDefs() != 1) return 0; 1023 const TargetRegisterClass *RC = TID.OpInfo[LoadRegIndex].getRegClass(TRI); 1024 // Ok, we're unfolding. Create a temporary register and do the unfold. 1025 unsigned Reg = MRI->createVirtualRegister(RC); 1026 1027 MachineFunction &MF = *MI->getParent()->getParent(); 1028 SmallVector<MachineInstr *, 2> NewMIs; 1029 bool Success = 1030 TII->unfoldMemoryOperand(MF, MI, Reg, 1031 /*UnfoldLoad=*/true, /*UnfoldStore=*/false, 1032 NewMIs); 1033 (void)Success; 1034 assert(Success && 1035 "unfoldMemoryOperand failed when getOpcodeAfterMemoryUnfold " 1036 "succeeded!"); 1037 assert(NewMIs.size() == 2 && 1038 "Unfolded a load into multiple instructions!"); 1039 MachineBasicBlock *MBB = MI->getParent(); 1040 MBB->insert(MI, NewMIs[0]); 1041 MBB->insert(MI, NewMIs[1]); 1042 // If unfolding produced a load that wasn't loop-invariant or profitable to 1043 // hoist, discard the new instructions and bail. 1044 if (!IsLoopInvariantInst(*NewMIs[0]) || !IsProfitableToHoist(*NewMIs[0])) { 1045 NewMIs[0]->eraseFromParent(); 1046 NewMIs[1]->eraseFromParent(); 1047 return 0; 1048 } 1049 1050 // Update register pressure for the unfolded instruction. 1051 UpdateRegPressure(NewMIs[1]); 1052 1053 // Otherwise we successfully unfolded a load that we can hoist. 1054 MI->eraseFromParent(); 1055 return NewMIs[0]; 1056} 1057 1058void MachineLICM::InitCSEMap(MachineBasicBlock *BB) { 1059 for (MachineBasicBlock::iterator I = BB->begin(),E = BB->end(); I != E; ++I) { 1060 const MachineInstr *MI = &*I; 1061 unsigned Opcode = MI->getOpcode(); 1062 DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator 1063 CI = CSEMap.find(Opcode); 1064 if (CI != CSEMap.end()) 1065 CI->second.push_back(MI); 1066 else { 1067 std::vector<const MachineInstr*> CSEMIs; 1068 CSEMIs.push_back(MI); 1069 CSEMap.insert(std::make_pair(Opcode, CSEMIs)); 1070 } 1071 } 1072} 1073 1074const MachineInstr* 1075MachineLICM::LookForDuplicate(const MachineInstr *MI, 1076 std::vector<const MachineInstr*> &PrevMIs) { 1077 for (unsigned i = 0, e = PrevMIs.size(); i != e; ++i) { 1078 const MachineInstr *PrevMI = PrevMIs[i]; 1079 if (TII->produceSameValue(MI, PrevMI, (PreRegAlloc ? MRI : 0))) 1080 return PrevMI; 1081 } 1082 return 0; 1083} 1084 1085bool MachineLICM::EliminateCSE(MachineInstr *MI, 1086 DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator &CI) { 1087 // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate 1088 // the undef property onto uses. 1089 if (CI == CSEMap.end() || MI->isImplicitDef()) 1090 return false; 1091 1092 if (const MachineInstr *Dup = LookForDuplicate(MI, CI->second)) { 1093 DEBUG(dbgs() << "CSEing " << *MI << " with " << *Dup); 1094 1095 // Replace virtual registers defined by MI by their counterparts defined 1096 // by Dup. 1097 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1098 const MachineOperand &MO = MI->getOperand(i); 1099 1100 // Physical registers may not differ here. 1101 assert((!MO.isReg() || MO.getReg() == 0 || 1102 !TargetRegisterInfo::isPhysicalRegister(MO.getReg()) || 1103 MO.getReg() == Dup->getOperand(i).getReg()) && 1104 "Instructions with different phys regs are not identical!"); 1105 1106 if (MO.isReg() && MO.isDef() && 1107 !TargetRegisterInfo::isPhysicalRegister(MO.getReg())) { 1108 MRI->replaceRegWith(MO.getReg(), Dup->getOperand(i).getReg()); 1109 MRI->clearKillFlags(Dup->getOperand(i).getReg()); 1110 } 1111 } 1112 MI->eraseFromParent(); 1113 ++NumCSEed; 1114 return true; 1115 } 1116 return false; 1117} 1118 1119/// Hoist - When an instruction is found to use only loop invariant operands 1120/// that are safe to hoist, this instruction is called to do the dirty work. 1121/// 1122bool MachineLICM::Hoist(MachineInstr *MI, MachineBasicBlock *Preheader) { 1123 // First check whether we should hoist this instruction. 1124 if (!IsLoopInvariantInst(*MI) || !IsProfitableToHoist(*MI)) { 1125 // If not, try unfolding a hoistable load. 1126 MI = ExtractHoistableLoad(MI); 1127 if (!MI) return false; 1128 } 1129 1130 // Now move the instructions to the predecessor, inserting it before any 1131 // terminator instructions. 1132 DEBUG({ 1133 dbgs() << "Hoisting " << *MI; 1134 if (Preheader->getBasicBlock()) 1135 dbgs() << " to MachineBasicBlock " 1136 << Preheader->getName(); 1137 if (MI->getParent()->getBasicBlock()) 1138 dbgs() << " from MachineBasicBlock " 1139 << MI->getParent()->getName(); 1140 dbgs() << "\n"; 1141 }); 1142 1143 // If this is the first instruction being hoisted to the preheader, 1144 // initialize the CSE map with potential common expressions. 1145 if (FirstInLoop) { 1146 InitCSEMap(Preheader); 1147 FirstInLoop = false; 1148 } 1149 1150 // Look for opportunity to CSE the hoisted instruction. 1151 unsigned Opcode = MI->getOpcode(); 1152 DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator 1153 CI = CSEMap.find(Opcode); 1154 if (!EliminateCSE(MI, CI)) { 1155 // Otherwise, splice the instruction to the preheader. 1156 Preheader->splice(Preheader->getFirstTerminator(),MI->getParent(),MI); 1157 1158 // Update register pressure for BBs from header to this block. 1159 UpdateBackTraceRegPressure(MI); 1160 1161 // Clear the kill flags of any register this instruction defines, 1162 // since they may need to be live throughout the entire loop 1163 // rather than just live for part of it. 1164 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1165 MachineOperand &MO = MI->getOperand(i); 1166 if (MO.isReg() && MO.isDef() && !MO.isDead()) 1167 MRI->clearKillFlags(MO.getReg()); 1168 } 1169 1170 // Add to the CSE map. 1171 if (CI != CSEMap.end()) 1172 CI->second.push_back(MI); 1173 else { 1174 std::vector<const MachineInstr*> CSEMIs; 1175 CSEMIs.push_back(MI); 1176 CSEMap.insert(std::make_pair(Opcode, CSEMIs)); 1177 } 1178 } 1179 1180 ++NumHoisted; 1181 Changed = true; 1182 1183 return true; 1184} 1185 1186MachineBasicBlock *MachineLICM::getCurPreheader() { 1187 // Determine the block to which to hoist instructions. If we can't find a 1188 // suitable loop predecessor, we can't do any hoisting. 1189 1190 // If we've tried to get a preheader and failed, don't try again. 1191 if (CurPreheader == reinterpret_cast<MachineBasicBlock *>(-1)) 1192 return 0; 1193 1194 if (!CurPreheader) { 1195 CurPreheader = CurLoop->getLoopPreheader(); 1196 if (!CurPreheader) { 1197 MachineBasicBlock *Pred = CurLoop->getLoopPredecessor(); 1198 if (!Pred) { 1199 CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1); 1200 return 0; 1201 } 1202 1203 CurPreheader = Pred->SplitCriticalEdge(CurLoop->getHeader(), this); 1204 if (!CurPreheader) { 1205 CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1); 1206 return 0; 1207 } 1208 } 1209 } 1210 return CurPreheader; 1211} 1212