1193323Sed//===-- MachineLICM.cpp - Machine Loop Invariant Code Motion Pass ---------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This pass performs loop invariant code motion on machine instructions. We 11193323Sed// attempt to remove as much code from the body of a loop as possible. 12193323Sed// 13193323Sed// This pass is not intended to be a replacement or a complete alternative 14193323Sed// for the LLVM-IR-level LICM pass. It is only designed to hoist simple 15193323Sed// constructs that are not exposed before lowering and instruction selection. 16193323Sed// 17193323Sed//===----------------------------------------------------------------------===// 18193323Sed 19193323Sed#include "llvm/CodeGen/Passes.h" 20249423Sdim#include "llvm/ADT/DenseMap.h" 21249423Sdim#include "llvm/ADT/SmallSet.h" 22249423Sdim#include "llvm/ADT/Statistic.h" 23249423Sdim#include "llvm/Analysis/AliasAnalysis.h" 24193323Sed#include "llvm/CodeGen/MachineDominators.h" 25207618Srdivacky#include "llvm/CodeGen/MachineFrameInfo.h" 26193323Sed#include "llvm/CodeGen/MachineLoopInfo.h" 27198892Srdivacky#include "llvm/CodeGen/MachineMemOperand.h" 28193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 29198892Srdivacky#include "llvm/CodeGen/PseudoSourceValue.h" 30288943Sdim#include "llvm/CodeGen/TargetSchedule.h" 31226633Sdim#include "llvm/Support/CommandLine.h" 32193323Sed#include "llvm/Support/Debug.h" 33198090Srdivacky#include "llvm/Support/raw_ostream.h" 34249423Sdim#include "llvm/Target/TargetInstrInfo.h" 35249423Sdim#include "llvm/Target/TargetLowering.h" 36249423Sdim#include "llvm/Target/TargetMachine.h" 37249423Sdim#include "llvm/Target/TargetRegisterInfo.h" 38280031Sdim#include "llvm/Target/TargetSubtargetInfo.h" 39193323Sedusing namespace llvm; 40193323Sed 41276479Sdim#define DEBUG_TYPE "machine-licm" 42276479Sdim 43226633Sdimstatic cl::opt<bool> 44226633SdimAvoidSpeculation("avoid-speculation", 45226633Sdim cl::desc("MachineLICM should avoid speculation"), 46234353Sdim cl::init(true), cl::Hidden); 47226633Sdim 48280031Sdimstatic cl::opt<bool> 49280031SdimHoistCheapInsts("hoist-cheap-insts", 50280031Sdim cl::desc("MachineLICM should hoist even cheap instructions"), 51280031Sdim cl::init(false), cl::Hidden); 52280031Sdim 53288943Sdimstatic cl::opt<bool> 54288943SdimSinkInstsToAvoidSpills("sink-insts-to-avoid-spills", 55288943Sdim cl::desc("MachineLICM should sink instructions into " 56288943Sdim "loops to avoid register spills"), 57288943Sdim cl::init(false), cl::Hidden); 58288943Sdim 59218893SdimSTATISTIC(NumHoisted, 60218893Sdim "Number of machine instructions hoisted out of loops"); 61218893SdimSTATISTIC(NumLowRP, 62218893Sdim "Number of instructions hoisted in low reg pressure situation"); 63218893SdimSTATISTIC(NumHighLatency, 64218893Sdim "Number of high latency instructions hoisted"); 65218893SdimSTATISTIC(NumCSEed, 66218893Sdim "Number of hoisted machine instructions CSEed"); 67207618SrdivackySTATISTIC(NumPostRAHoisted, 68207618Srdivacky "Number of machine instructions hoisted out of loops post regalloc"); 69193323Sed 70193323Sednamespace { 71198892Srdivacky class MachineLICM : public MachineFunctionPass { 72193323Sed const TargetInstrInfo *TII; 73249423Sdim const TargetLoweringBase *TLI; 74198090Srdivacky const TargetRegisterInfo *TRI; 75207618Srdivacky const MachineFrameInfo *MFI; 76218893Sdim MachineRegisterInfo *MRI; 77288943Sdim TargetSchedModel SchedModel; 78234353Sdim bool PreRegAlloc; 79193323Sed 80193323Sed // Various analyses that we use... 81198090Srdivacky AliasAnalysis *AA; // Alias analysis info. 82207618Srdivacky MachineLoopInfo *MLI; // Current MachineLoopInfo 83193323Sed MachineDominatorTree *DT; // Machine dominator tree for the cur loop 84193323Sed 85193323Sed // State that is updated as we process loops 86193323Sed bool Changed; // True if a loop is changed. 87210299Sed bool FirstInLoop; // True if it's the first LICM in the loop. 88193323Sed MachineLoop *CurLoop; // The current loop we are working on. 89193323Sed MachineBasicBlock *CurPreheader; // The preheader for CurLoop. 90193323Sed 91234353Sdim // Exit blocks for CurLoop. 92234353Sdim SmallVector<MachineBasicBlock*, 8> ExitBlocks; 93207618Srdivacky 94234353Sdim bool isExitBlock(const MachineBasicBlock *MBB) const { 95234353Sdim return std::find(ExitBlocks.begin(), ExitBlocks.end(), MBB) != 96234353Sdim ExitBlocks.end(); 97234353Sdim } 98234353Sdim 99218893Sdim // Track 'estimated' register pressure. 100218893Sdim SmallSet<unsigned, 32> RegSeen; 101218893Sdim SmallVector<unsigned, 8> RegPressure; 102218893Sdim 103288943Sdim // Register pressure "limit" per register pressure set. If the pressure 104218893Sdim // is higher than the limit, then it's considered high. 105218893Sdim SmallVector<unsigned, 8> RegLimit; 106218893Sdim 107218893Sdim // Register pressure on path leading from loop preheader to current BB. 108218893Sdim SmallVector<SmallVector<unsigned, 8>, 16> BackTrace; 109218893Sdim 110212904Sdim // For each opcode, keep a list of potential CSE instructions. 111198892Srdivacky DenseMap<unsigned, std::vector<const MachineInstr*> > CSEMap; 112207618Srdivacky 113226633Sdim enum { 114226633Sdim SpeculateFalse = 0, 115226633Sdim SpeculateTrue = 1, 116226633Sdim SpeculateUnknown = 2 117226633Sdim }; 118226633Sdim 119226633Sdim // If a MBB does not dominate loop exiting blocks then it may not safe 120226633Sdim // to hoist loads from this block. 121226633Sdim // Tri-state: 0 - false, 1 - true, 2 - unknown 122226633Sdim unsigned SpeculationState; 123226633Sdim 124193323Sed public: 125193323Sed static char ID; // Pass identification, replacement for typeid 126207618Srdivacky MachineLICM() : 127218893Sdim MachineFunctionPass(ID), PreRegAlloc(true) { 128218893Sdim initializeMachineLICMPass(*PassRegistry::getPassRegistry()); 129218893Sdim } 130193323Sed 131207618Srdivacky explicit MachineLICM(bool PreRA) : 132218893Sdim MachineFunctionPass(ID), PreRegAlloc(PreRA) { 133218893Sdim initializeMachineLICMPass(*PassRegistry::getPassRegistry()); 134218893Sdim } 135207618Srdivacky 136276479Sdim bool runOnMachineFunction(MachineFunction &MF) override; 137193323Sed 138276479Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 139193323Sed AU.addRequired<MachineLoopInfo>(); 140193323Sed AU.addRequired<MachineDominatorTree>(); 141296417Sdim AU.addRequired<AAResultsWrapperPass>(); 142193323Sed AU.addPreserved<MachineLoopInfo>(); 143193323Sed AU.addPreserved<MachineDominatorTree>(); 144193323Sed MachineFunctionPass::getAnalysisUsage(AU); 145193323Sed } 146193323Sed 147276479Sdim void releaseMemory() override { 148218893Sdim RegSeen.clear(); 149218893Sdim RegPressure.clear(); 150218893Sdim RegLimit.clear(); 151218893Sdim BackTrace.clear(); 152193323Sed CSEMap.clear(); 153193323Sed } 154193323Sed 155193323Sed private: 156296417Sdim /// Keep track of information about hoisting candidates. 157207618Srdivacky struct CandidateInfo { 158207618Srdivacky MachineInstr *MI; 159207618Srdivacky unsigned Def; 160207618Srdivacky int FI; 161207618Srdivacky CandidateInfo(MachineInstr *mi, unsigned def, int fi) 162207618Srdivacky : MI(mi), Def(def), FI(fi) {} 163207618Srdivacky }; 164207618Srdivacky 165207618Srdivacky void HoistRegionPostRA(); 166207618Srdivacky 167207618Srdivacky void HoistPostRA(MachineInstr *MI, unsigned Def); 168207618Srdivacky 169296417Sdim void ProcessMI(MachineInstr *MI, BitVector &PhysRegDefs, 170296417Sdim BitVector &PhysRegClobbers, SmallSet<int, 32> &StoredFIs, 171261991Sdim SmallVectorImpl<CandidateInfo> &Candidates); 172207618Srdivacky 173207618Srdivacky void AddToLiveIns(unsigned Reg); 174207618Srdivacky 175207618Srdivacky bool IsLICMCandidate(MachineInstr &I); 176207618Srdivacky 177193323Sed bool IsLoopInvariantInst(MachineInstr &I); 178193323Sed 179234353Sdim bool HasLoopPHIUse(const MachineInstr *MI) const; 180221345Sdim 181218893Sdim bool HasHighOperandLatency(MachineInstr &MI, unsigned DefIdx, 182218893Sdim unsigned Reg) const; 183218893Sdim 184218893Sdim bool IsCheapInstruction(MachineInstr &MI) const; 185218893Sdim 186288943Sdim bool CanCauseHighRegPressure(const DenseMap<unsigned, int> &Cost, 187288943Sdim bool Cheap); 188218893Sdim 189218893Sdim void UpdateBackTraceRegPressure(const MachineInstr *MI); 190218893Sdim 191193323Sed bool IsProfitableToHoist(MachineInstr &MI); 192193323Sed 193226633Sdim bool IsGuaranteedToExecute(MachineBasicBlock *BB); 194226633Sdim 195234353Sdim void EnterScope(MachineBasicBlock *MBB); 196234353Sdim 197234353Sdim void ExitScope(MachineBasicBlock *MBB); 198234353Sdim 199296417Sdim void ExitScopeIfDone( 200296417Sdim MachineDomTreeNode *Node, 201296417Sdim DenseMap<MachineDomTreeNode *, unsigned> &OpenChildren, 202296417Sdim DenseMap<MachineDomTreeNode *, MachineDomTreeNode *> &ParentMap); 203234353Sdim 204234353Sdim void HoistOutOfLoop(MachineDomTreeNode *LoopHeaderNode); 205296417Sdim 206234353Sdim void HoistRegion(MachineDomTreeNode *N, bool IsHeader); 207193323Sed 208288943Sdim void SinkIntoLoop(); 209226633Sdim 210218893Sdim void InitRegPressure(MachineBasicBlock *BB); 211199989Srdivacky 212288943Sdim DenseMap<unsigned, int> calcRegisterCost(const MachineInstr *MI, 213288943Sdim bool ConsiderSeen, 214288943Sdim bool ConsiderUnseenAsDef); 215288943Sdim 216288943Sdim void UpdateRegPressure(const MachineInstr *MI, 217288943Sdim bool ConsiderUnseenAsDef = false); 218218893Sdim 219198892Srdivacky MachineInstr *ExtractHoistableLoad(MachineInstr *MI); 220198892Srdivacky 221296417Sdim const MachineInstr * 222296417Sdim LookForDuplicate(const MachineInstr *MI, 223296417Sdim std::vector<const MachineInstr *> &PrevMIs); 224199481Srdivacky 225296417Sdim bool EliminateCSE( 226296417Sdim MachineInstr *MI, 227296417Sdim DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator &CI); 228198953Srdivacky 229226633Sdim bool MayCSE(MachineInstr *MI); 230226633Sdim 231218893Sdim bool Hoist(MachineInstr *MI, MachineBasicBlock *Preheader); 232198892Srdivacky 233198892Srdivacky void InitCSEMap(MachineBasicBlock *BB); 234210299Sed 235210299Sed MachineBasicBlock *getCurPreheader(); 236193323Sed }; 237193323Sed} // end anonymous namespace 238193323Sed 239193323Sedchar MachineLICM::ID = 0; 240234353Sdimchar &llvm::MachineLICMID = MachineLICM::ID; 241218893SdimINITIALIZE_PASS_BEGIN(MachineLICM, "machinelicm", 242218893Sdim "Machine Loop Invariant Code Motion", false, false) 243218893SdimINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 244218893SdimINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 245296417SdimINITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 246218893SdimINITIALIZE_PASS_END(MachineLICM, "machinelicm", 247218893Sdim "Machine Loop Invariant Code Motion", false, false) 248193323Sed 249296417Sdim/// Test if the given loop is the outer-most loop that has a unique predecessor. 250210299Sedstatic bool LoopIsOuterMostWithPredecessor(MachineLoop *CurLoop) { 251210299Sed // Check whether this loop even has a unique predecessor. 252210299Sed if (!CurLoop->getLoopPredecessor()) 253210299Sed return false; 254210299Sed // Ok, now check to see if any of its outer loops do. 255193323Sed for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop()) 256210299Sed if (L->getLoopPredecessor()) 257193323Sed return false; 258210299Sed // None of them did, so this is the outermost with a unique predecessor. 259193323Sed return true; 260193323Sed} 261193323Sed 262193323Sedbool MachineLICM::runOnMachineFunction(MachineFunction &MF) { 263276479Sdim if (skipOptnoneFunction(*MF.getFunction())) 264276479Sdim return false; 265276479Sdim 266210299Sed Changed = FirstInLoop = false; 267288943Sdim const TargetSubtargetInfo &ST = MF.getSubtarget(); 268288943Sdim TII = ST.getInstrInfo(); 269288943Sdim TLI = ST.getTargetLowering(); 270288943Sdim TRI = ST.getRegisterInfo(); 271207618Srdivacky MFI = MF.getFrameInfo(); 272218893Sdim MRI = &MF.getRegInfo(); 273288943Sdim SchedModel.init(ST.getSchedModel(), &ST, TII); 274193323Sed 275234353Sdim PreRegAlloc = MRI->isSSA(); 276234353Sdim 277234353Sdim if (PreRegAlloc) 278234353Sdim DEBUG(dbgs() << "******** Pre-regalloc Machine LICM: "); 279234353Sdim else 280234353Sdim DEBUG(dbgs() << "******** Post-regalloc Machine LICM: "); 281243830Sdim DEBUG(dbgs() << MF.getName() << " ********\n"); 282234353Sdim 283218893Sdim if (PreRegAlloc) { 284218893Sdim // Estimate register pressure during pre-regalloc pass. 285288943Sdim unsigned NumRPS = TRI->getNumRegPressureSets(); 286288943Sdim RegPressure.resize(NumRPS); 287218893Sdim std::fill(RegPressure.begin(), RegPressure.end(), 0); 288288943Sdim RegLimit.resize(NumRPS); 289288943Sdim for (unsigned i = 0, e = NumRPS; i != e; ++i) 290288943Sdim RegLimit[i] = TRI->getRegPressureSetLimit(MF, i); 291218893Sdim } 292218893Sdim 293193323Sed // Get our Loop information... 294207618Srdivacky MLI = &getAnalysis<MachineLoopInfo>(); 295207618Srdivacky DT = &getAnalysis<MachineDominatorTree>(); 296296417Sdim AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); 297193323Sed 298210299Sed SmallVector<MachineLoop *, 8> Worklist(MLI->begin(), MLI->end()); 299210299Sed while (!Worklist.empty()) { 300210299Sed CurLoop = Worklist.pop_back_val(); 301276479Sdim CurPreheader = nullptr; 302234353Sdim ExitBlocks.clear(); 303193323Sed 304207618Srdivacky // If this is done before regalloc, only visit outer-most preheader-sporting 305207618Srdivacky // loops. 306210299Sed if (PreRegAlloc && !LoopIsOuterMostWithPredecessor(CurLoop)) { 307210299Sed Worklist.append(CurLoop->begin(), CurLoop->end()); 308193323Sed continue; 309210299Sed } 310193323Sed 311234353Sdim CurLoop->getExitBlocks(ExitBlocks); 312234353Sdim 313207618Srdivacky if (!PreRegAlloc) 314207618Srdivacky HoistRegionPostRA(); 315207618Srdivacky else { 316207618Srdivacky // CSEMap is initialized for loop header when the first instruction is 317207618Srdivacky // being hoisted. 318207618Srdivacky MachineDomTreeNode *N = DT->getNode(CurLoop->getHeader()); 319210299Sed FirstInLoop = true; 320234353Sdim HoistOutOfLoop(N); 321207618Srdivacky CSEMap.clear(); 322288943Sdim 323288943Sdim if (SinkInstsToAvoidSpills) 324288943Sdim SinkIntoLoop(); 325207618Srdivacky } 326193323Sed } 327193323Sed 328193323Sed return Changed; 329193323Sed} 330193323Sed 331296417Sdim/// Return true if instruction stores to the specified frame. 332207618Srdivackystatic bool InstructionStoresToFI(const MachineInstr *MI, int FI) { 333296417Sdim // If we lost memory operands, conservatively assume that the instruction 334296417Sdim // writes to all slots. 335296417Sdim if (MI->memoperands_empty()) 336296417Sdim return true; 337296417Sdim for (const MachineMemOperand *MemOp : MI->memoperands()) { 338296417Sdim if (!MemOp->isStore() || !MemOp->getPseudoValue()) 339207618Srdivacky continue; 340207618Srdivacky if (const FixedStackPseudoSourceValue *Value = 341296417Sdim dyn_cast<FixedStackPseudoSourceValue>(MemOp->getPseudoValue())) { 342207618Srdivacky if (Value->getFrameIndex() == FI) 343207618Srdivacky return true; 344207618Srdivacky } 345207618Srdivacky } 346207618Srdivacky return false; 347207618Srdivacky} 348207618Srdivacky 349296417Sdim/// Examine the instruction for potentai LICM candidate. Also 350207618Srdivacky/// gather register def and frame object update information. 351207618Srdivackyvoid MachineLICM::ProcessMI(MachineInstr *MI, 352234353Sdim BitVector &PhysRegDefs, 353234353Sdim BitVector &PhysRegClobbers, 354207618Srdivacky SmallSet<int, 32> &StoredFIs, 355261991Sdim SmallVectorImpl<CandidateInfo> &Candidates) { 356207618Srdivacky bool RuledOut = false; 357207618Srdivacky bool HasNonInvariantUse = false; 358207618Srdivacky unsigned Def = 0; 359296417Sdim for (const MachineOperand &MO : MI->operands()) { 360207618Srdivacky if (MO.isFI()) { 361207618Srdivacky // Remember if the instruction stores to the frame index. 362207618Srdivacky int FI = MO.getIndex(); 363207618Srdivacky if (!StoredFIs.count(FI) && 364207618Srdivacky MFI->isSpillSlotObjectIndex(FI) && 365207618Srdivacky InstructionStoresToFI(MI, FI)) 366207618Srdivacky StoredFIs.insert(FI); 367207618Srdivacky HasNonInvariantUse = true; 368207618Srdivacky continue; 369207618Srdivacky } 370207618Srdivacky 371234353Sdim // We can't hoist an instruction defining a physreg that is clobbered in 372234353Sdim // the loop. 373234353Sdim if (MO.isRegMask()) { 374234353Sdim PhysRegClobbers.setBitsNotInMask(MO.getRegMask()); 375234353Sdim continue; 376234353Sdim } 377234353Sdim 378207618Srdivacky if (!MO.isReg()) 379207618Srdivacky continue; 380207618Srdivacky unsigned Reg = MO.getReg(); 381207618Srdivacky if (!Reg) 382207618Srdivacky continue; 383207618Srdivacky assert(TargetRegisterInfo::isPhysicalRegister(Reg) && 384207618Srdivacky "Not expecting virtual register!"); 385207618Srdivacky 386207618Srdivacky if (!MO.isDef()) { 387234353Sdim if (Reg && (PhysRegDefs.test(Reg) || PhysRegClobbers.test(Reg))) 388207618Srdivacky // If it's using a non-loop-invariant register, then it's obviously not 389207618Srdivacky // safe to hoist. 390207618Srdivacky HasNonInvariantUse = true; 391207618Srdivacky continue; 392207618Srdivacky } 393207618Srdivacky 394207618Srdivacky if (MO.isImplicit()) { 395239462Sdim for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 396239462Sdim PhysRegClobbers.set(*AI); 397207618Srdivacky if (!MO.isDead()) 398207618Srdivacky // Non-dead implicit def? This cannot be hoisted. 399207618Srdivacky RuledOut = true; 400207618Srdivacky // No need to check if a dead implicit def is also defined by 401207618Srdivacky // another instruction. 402207618Srdivacky continue; 403207618Srdivacky } 404207618Srdivacky 405207618Srdivacky // FIXME: For now, avoid instructions with multiple defs, unless 406207618Srdivacky // it's a dead implicit def. 407207618Srdivacky if (Def) 408207618Srdivacky RuledOut = true; 409207618Srdivacky else 410207618Srdivacky Def = Reg; 411207618Srdivacky 412207618Srdivacky // If we have already seen another instruction that defines the same 413234353Sdim // register, then this is not safe. Two defs is indicated by setting a 414234353Sdim // PhysRegClobbers bit. 415239462Sdim for (MCRegAliasIterator AS(Reg, TRI, true); AS.isValid(); ++AS) { 416234353Sdim if (PhysRegDefs.test(*AS)) 417234353Sdim PhysRegClobbers.set(*AS); 418234353Sdim PhysRegDefs.set(*AS); 419234353Sdim } 420261991Sdim if (PhysRegClobbers.test(Reg)) 421261991Sdim // MI defined register is seen defined by another instruction in 422261991Sdim // the loop, it cannot be a LICM candidate. 423261991Sdim RuledOut = true; 424207618Srdivacky } 425207618Srdivacky 426207618Srdivacky // Only consider reloads for now and remats which do not have register 427207618Srdivacky // operands. FIXME: Consider unfold load folding instructions. 428207618Srdivacky if (Def && !RuledOut) { 429207618Srdivacky int FI = INT_MIN; 430207618Srdivacky if ((!HasNonInvariantUse && IsLICMCandidate(*MI)) || 431207618Srdivacky (TII->isLoadFromStackSlot(MI, FI) && MFI->isSpillSlotObjectIndex(FI))) 432207618Srdivacky Candidates.push_back(CandidateInfo(MI, Def, FI)); 433207618Srdivacky } 434207618Srdivacky} 435207618Srdivacky 436296417Sdim/// Walk the specified region of the CFG and hoist loop invariants out to the 437296417Sdim/// preheader. 438207618Srdivackyvoid MachineLICM::HoistRegionPostRA() { 439234353Sdim MachineBasicBlock *Preheader = getCurPreheader(); 440234353Sdim if (!Preheader) 441234353Sdim return; 442234353Sdim 443207618Srdivacky unsigned NumRegs = TRI->getNumRegs(); 444234353Sdim BitVector PhysRegDefs(NumRegs); // Regs defined once in the loop. 445234353Sdim BitVector PhysRegClobbers(NumRegs); // Regs defined more than once. 446207618Srdivacky 447207618Srdivacky SmallVector<CandidateInfo, 32> Candidates; 448207618Srdivacky SmallSet<int, 32> StoredFIs; 449207618Srdivacky 450207618Srdivacky // Walk the entire region, count number of defs for each register, and 451207618Srdivacky // collect potential LICM candidates. 452261991Sdim const std::vector<MachineBasicBlock *> &Blocks = CurLoop->getBlocks(); 453296417Sdim for (MachineBasicBlock *BB : Blocks) { 454226633Sdim // If the header of the loop containing this basic block is a landing pad, 455226633Sdim // then don't try to hoist instructions out of this loop. 456226633Sdim const MachineLoop *ML = MLI->getLoopFor(BB); 457296417Sdim if (ML && ML->getHeader()->isEHPad()) continue; 458226633Sdim 459207618Srdivacky // Conservatively treat live-in's as an external def. 460207618Srdivacky // FIXME: That means a reload that're reused in successor block(s) will not 461207618Srdivacky // be LICM'ed. 462296417Sdim for (const auto &LI : BB->liveins()) { 463296417Sdim for (MCRegAliasIterator AI(LI.PhysReg, TRI, true); AI.isValid(); ++AI) 464239462Sdim PhysRegDefs.set(*AI); 465207618Srdivacky } 466207618Srdivacky 467226633Sdim SpeculationState = SpeculateUnknown; 468296417Sdim for (MachineInstr &MI : *BB) 469296417Sdim ProcessMI(&MI, PhysRegDefs, PhysRegClobbers, StoredFIs, Candidates); 470207618Srdivacky } 471207618Srdivacky 472234353Sdim // Gather the registers read / clobbered by the terminator. 473234353Sdim BitVector TermRegs(NumRegs); 474234353Sdim MachineBasicBlock::iterator TI = Preheader->getFirstTerminator(); 475234353Sdim if (TI != Preheader->end()) { 476296417Sdim for (const MachineOperand &MO : TI->operands()) { 477234353Sdim if (!MO.isReg()) 478234353Sdim continue; 479234353Sdim unsigned Reg = MO.getReg(); 480234353Sdim if (!Reg) 481234353Sdim continue; 482239462Sdim for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 483239462Sdim TermRegs.set(*AI); 484234353Sdim } 485234353Sdim } 486234353Sdim 487207618Srdivacky // Now evaluate whether the potential candidates qualify. 488207618Srdivacky // 1. Check if the candidate defined register is defined by another 489207618Srdivacky // instruction in the loop. 490207618Srdivacky // 2. If the candidate is a load from stack slot (always true for now), 491207618Srdivacky // check if the slot is stored anywhere in the loop. 492234353Sdim // 3. Make sure candidate def should not clobber 493234353Sdim // registers read by the terminator. Similarly its def should not be 494234353Sdim // clobbered by the terminator. 495296417Sdim for (CandidateInfo &Candidate : Candidates) { 496296417Sdim if (Candidate.FI != INT_MIN && 497296417Sdim StoredFIs.count(Candidate.FI)) 498207618Srdivacky continue; 499207618Srdivacky 500296417Sdim unsigned Def = Candidate.Def; 501234353Sdim if (!PhysRegClobbers.test(Def) && !TermRegs.test(Def)) { 502207618Srdivacky bool Safe = true; 503296417Sdim MachineInstr *MI = Candidate.MI; 504296417Sdim for (const MachineOperand &MO : MI->operands()) { 505207618Srdivacky if (!MO.isReg() || MO.isDef() || !MO.getReg()) 506207618Srdivacky continue; 507234353Sdim unsigned Reg = MO.getReg(); 508234353Sdim if (PhysRegDefs.test(Reg) || 509234353Sdim PhysRegClobbers.test(Reg)) { 510207618Srdivacky // If it's using a non-loop-invariant register, then it's obviously 511207618Srdivacky // not safe to hoist. 512207618Srdivacky Safe = false; 513207618Srdivacky break; 514207618Srdivacky } 515207618Srdivacky } 516207618Srdivacky if (Safe) 517296417Sdim HoistPostRA(MI, Candidate.Def); 518207618Srdivacky } 519207618Srdivacky } 520207618Srdivacky} 521207618Srdivacky 522296417Sdim/// Add register 'Reg' to the livein sets of BBs in the current loop, and make 523296417Sdim/// sure it is not killed by any instructions in the loop. 524207618Srdivackyvoid MachineLICM::AddToLiveIns(unsigned Reg) { 525261991Sdim const std::vector<MachineBasicBlock *> &Blocks = CurLoop->getBlocks(); 526296417Sdim for (MachineBasicBlock *BB : Blocks) { 527207618Srdivacky if (!BB->isLiveIn(Reg)) 528207618Srdivacky BB->addLiveIn(Reg); 529296417Sdim for (MachineInstr &MI : *BB) { 530296417Sdim for (MachineOperand &MO : MI.operands()) { 531207618Srdivacky if (!MO.isReg() || !MO.getReg() || MO.isDef()) continue; 532207618Srdivacky if (MO.getReg() == Reg || TRI->isSuperRegister(Reg, MO.getReg())) 533207618Srdivacky MO.setIsKill(false); 534207618Srdivacky } 535207618Srdivacky } 536207618Srdivacky } 537207618Srdivacky} 538207618Srdivacky 539296417Sdim/// When an instruction is found to only use loop invariant operands that is 540296417Sdim/// safe to hoist, this instruction is called to do the dirty work. 541207618Srdivackyvoid MachineLICM::HoistPostRA(MachineInstr *MI, unsigned Def) { 542210299Sed MachineBasicBlock *Preheader = getCurPreheader(); 543210299Sed 544207618Srdivacky // Now move the instructions to the predecessor, inserting it before any 545207618Srdivacky // terminator instructions. 546234353Sdim DEBUG(dbgs() << "Hoisting to BB#" << Preheader->getNumber() << " from BB#" 547234353Sdim << MI->getParent()->getNumber() << ": " << *MI); 548207618Srdivacky 549207618Srdivacky // Splice the instruction to the preheader. 550207618Srdivacky MachineBasicBlock *MBB = MI->getParent(); 551210299Sed Preheader->splice(Preheader->getFirstTerminator(), MBB, MI); 552207618Srdivacky 553234353Sdim // Add register to livein list to all the BBs in the current loop since a 554207618Srdivacky // loop invariant must be kept live throughout the whole loop. This is 555207618Srdivacky // important to ensure later passes do not scavenge the def register. 556207618Srdivacky AddToLiveIns(Def); 557207618Srdivacky 558207618Srdivacky ++NumPostRAHoisted; 559207618Srdivacky Changed = true; 560207618Srdivacky} 561207618Srdivacky 562296417Sdim/// Check if this mbb is guaranteed to execute. If not then a load from this mbb 563296417Sdim/// may not be safe to hoist. 564226633Sdimbool MachineLICM::IsGuaranteedToExecute(MachineBasicBlock *BB) { 565226633Sdim if (SpeculationState != SpeculateUnknown) 566226633Sdim return SpeculationState == SpeculateFalse; 567234353Sdim 568226633Sdim if (BB != CurLoop->getHeader()) { 569226633Sdim // Check loop exiting blocks. 570226633Sdim SmallVector<MachineBasicBlock*, 8> CurrentLoopExitingBlocks; 571226633Sdim CurLoop->getExitingBlocks(CurrentLoopExitingBlocks); 572296417Sdim for (MachineBasicBlock *CurrentLoopExitingBlock : CurrentLoopExitingBlocks) 573296417Sdim if (!DT->dominates(BB, CurrentLoopExitingBlock)) { 574226633Sdim SpeculationState = SpeculateTrue; 575226633Sdim return false; 576226633Sdim } 577226633Sdim } 578226633Sdim 579226633Sdim SpeculationState = SpeculateFalse; 580226633Sdim return true; 581226633Sdim} 582226633Sdim 583234353Sdimvoid MachineLICM::EnterScope(MachineBasicBlock *MBB) { 584234353Sdim DEBUG(dbgs() << "Entering: " << MBB->getName() << '\n'); 585193323Sed 586234353Sdim // Remember livein register pressure. 587234353Sdim BackTrace.push_back(RegPressure); 588234353Sdim} 589226633Sdim 590234353Sdimvoid MachineLICM::ExitScope(MachineBasicBlock *MBB) { 591234353Sdim DEBUG(dbgs() << "Exiting: " << MBB->getName() << '\n'); 592234353Sdim BackTrace.pop_back(); 593234353Sdim} 594193323Sed 595296417Sdim/// Destroy scope for the MBB that corresponds to the given dominator tree node 596296417Sdim/// if its a leaf or all of its children are done. Walk up the dominator tree to 597296417Sdim/// destroy ancestors which are now done. 598234353Sdimvoid MachineLICM::ExitScopeIfDone(MachineDomTreeNode *Node, 599234353Sdim DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren, 600234353Sdim DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> &ParentMap) { 601234353Sdim if (OpenChildren[Node]) 602218893Sdim return; 603218893Sdim 604234353Sdim // Pop scope. 605234353Sdim ExitScope(Node->getBlock()); 606234353Sdim 607234353Sdim // Now traverse upwards to pop ancestors whose offsprings are all done. 608234353Sdim while (MachineDomTreeNode *Parent = ParentMap[Node]) { 609234353Sdim unsigned Left = --OpenChildren[Parent]; 610234353Sdim if (Left != 0) 611234353Sdim break; 612234353Sdim ExitScope(Parent->getBlock()); 613234353Sdim Node = Parent; 614234353Sdim } 615234353Sdim} 616234353Sdim 617296417Sdim/// Walk the specified loop in the CFG (defined by all blocks dominated by the 618296417Sdim/// specified header block, and that are in the current loop) in depth first 619296417Sdim/// order w.r.t the DominatorTree. This allows us to visit definitions before 620296417Sdim/// uses, allowing us to hoist a loop body in one pass without iteration. 621234353Sdim/// 622234353Sdimvoid MachineLICM::HoistOutOfLoop(MachineDomTreeNode *HeaderN) { 623288943Sdim MachineBasicBlock *Preheader = getCurPreheader(); 624288943Sdim if (!Preheader) 625288943Sdim return; 626288943Sdim 627234353Sdim SmallVector<MachineDomTreeNode*, 32> Scopes; 628234353Sdim SmallVector<MachineDomTreeNode*, 8> WorkList; 629234353Sdim DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> ParentMap; 630234353Sdim DenseMap<MachineDomTreeNode*, unsigned> OpenChildren; 631234353Sdim 632234353Sdim // Perform a DFS walk to determine the order of visit. 633234353Sdim WorkList.push_back(HeaderN); 634288943Sdim while (!WorkList.empty()) { 635234353Sdim MachineDomTreeNode *Node = WorkList.pop_back_val(); 636276479Sdim assert(Node && "Null dominator tree node?"); 637234353Sdim MachineBasicBlock *BB = Node->getBlock(); 638234353Sdim 639234353Sdim // If the header of the loop containing this basic block is a landing pad, 640234353Sdim // then don't try to hoist instructions out of this loop. 641234353Sdim const MachineLoop *ML = MLI->getLoopFor(BB); 642296417Sdim if (ML && ML->getHeader()->isEHPad()) 643234353Sdim continue; 644234353Sdim 645234353Sdim // If this subregion is not in the top level loop at all, exit. 646234353Sdim if (!CurLoop->contains(BB)) 647234353Sdim continue; 648234353Sdim 649234353Sdim Scopes.push_back(Node); 650234353Sdim const std::vector<MachineDomTreeNode*> &Children = Node->getChildren(); 651234353Sdim unsigned NumChildren = Children.size(); 652234353Sdim 653234353Sdim // Don't hoist things out of a large switch statement. This often causes 654234353Sdim // code to be hoisted that wasn't going to be executed, and increases 655234353Sdim // register pressure in a situation where it's likely to matter. 656234353Sdim if (BB->succ_size() >= 25) 657234353Sdim NumChildren = 0; 658234353Sdim 659234353Sdim OpenChildren[Node] = NumChildren; 660234353Sdim // Add children in reverse order as then the next popped worklist node is 661234353Sdim // the first child of this node. This means we ultimately traverse the 662234353Sdim // DOM tree in exactly the same order as if we'd recursed. 663234353Sdim for (int i = (int)NumChildren-1; i >= 0; --i) { 664234353Sdim MachineDomTreeNode *Child = Children[i]; 665234353Sdim ParentMap[Child] = Node; 666234353Sdim WorkList.push_back(Child); 667234353Sdim } 668288943Sdim } 669234353Sdim 670288943Sdim if (Scopes.size() == 0) 671288943Sdim return; 672234353Sdim 673288943Sdim // Compute registers which are livein into the loop headers. 674288943Sdim RegSeen.clear(); 675288943Sdim BackTrace.clear(); 676288943Sdim InitRegPressure(Preheader); 677218893Sdim 678234353Sdim // Now perform LICM. 679296417Sdim for (MachineDomTreeNode *Node : Scopes) { 680234353Sdim MachineBasicBlock *MBB = Node->getBlock(); 681218893Sdim 682234353Sdim EnterScope(MBB); 683234353Sdim 684234353Sdim // Process the block 685234353Sdim SpeculationState = SpeculateUnknown; 686234353Sdim for (MachineBasicBlock::iterator 687234353Sdim MII = MBB->begin(), E = MBB->end(); MII != E; ) { 688234353Sdim MachineBasicBlock::iterator NextMII = MII; ++NextMII; 689234353Sdim MachineInstr *MI = &*MII; 690234353Sdim if (!Hoist(MI, Preheader)) 691234353Sdim UpdateRegPressure(MI); 692234353Sdim MII = NextMII; 693234353Sdim } 694234353Sdim 695234353Sdim // If it's a leaf node, it's done. Traverse upwards to pop ancestors. 696234353Sdim ExitScopeIfDone(Node, OpenChildren, ParentMap); 697212904Sdim } 698193323Sed} 699193323Sed 700296417Sdim/// Sink instructions into loops if profitable. This especially tries to prevent 701296417Sdim/// register spills caused by register pressure if there is little to no 702296417Sdim/// overhead moving instructions into loops. 703288943Sdimvoid MachineLICM::SinkIntoLoop() { 704288943Sdim MachineBasicBlock *Preheader = getCurPreheader(); 705288943Sdim if (!Preheader) 706288943Sdim return; 707288943Sdim 708288943Sdim SmallVector<MachineInstr *, 8> Candidates; 709288943Sdim for (MachineBasicBlock::instr_iterator I = Preheader->instr_begin(); 710288943Sdim I != Preheader->instr_end(); ++I) { 711288943Sdim // We need to ensure that we can safely move this instruction into the loop. 712288943Sdim // As such, it must not have side-effects, e.g. such as a call has. 713296417Sdim if (IsLoopInvariantInst(*I) && !HasLoopPHIUse(&*I)) 714296417Sdim Candidates.push_back(&*I); 715288943Sdim } 716288943Sdim 717288943Sdim for (MachineInstr *I : Candidates) { 718288943Sdim const MachineOperand &MO = I->getOperand(0); 719288943Sdim if (!MO.isDef() || !MO.isReg() || !MO.getReg()) 720288943Sdim continue; 721288943Sdim if (!MRI->hasOneDef(MO.getReg())) 722288943Sdim continue; 723288943Sdim bool CanSink = true; 724288943Sdim MachineBasicBlock *B = nullptr; 725288943Sdim for (MachineInstr &MI : MRI->use_instructions(MO.getReg())) { 726288943Sdim // FIXME: Come up with a proper cost model that estimates whether sinking 727288943Sdim // the instruction (and thus possibly executing it on every loop 728288943Sdim // iteration) is more expensive than a register. 729288943Sdim // For now assumes that copies are cheap and thus almost always worth it. 730288943Sdim if (!MI.isCopy()) { 731288943Sdim CanSink = false; 732288943Sdim break; 733288943Sdim } 734288943Sdim if (!B) { 735288943Sdim B = MI.getParent(); 736288943Sdim continue; 737288943Sdim } 738288943Sdim B = DT->findNearestCommonDominator(B, MI.getParent()); 739288943Sdim if (!B) { 740288943Sdim CanSink = false; 741288943Sdim break; 742288943Sdim } 743288943Sdim } 744288943Sdim if (!CanSink || !B || B == Preheader) 745288943Sdim continue; 746288943Sdim B->splice(B->getFirstNonPHI(), Preheader, I); 747288943Sdim } 748288943Sdim} 749288943Sdim 750218893Sdimstatic bool isOperandKill(const MachineOperand &MO, MachineRegisterInfo *MRI) { 751218893Sdim return MO.isKill() || MRI->hasOneNonDBGUse(MO.getReg()); 752218893Sdim} 753218893Sdim 754296417Sdim/// Find all virtual register references that are liveout of the preheader to 755296417Sdim/// initialize the starting "register pressure". Note this does not count live 756296417Sdim/// through (livein but not used) registers. 757218893Sdimvoid MachineLICM::InitRegPressure(MachineBasicBlock *BB) { 758218893Sdim std::fill(RegPressure.begin(), RegPressure.end(), 0); 759218893Sdim 760218893Sdim // If the preheader has only a single predecessor and it ends with a 761218893Sdim // fallthrough or an unconditional branch, then scan its predecessor for live 762218893Sdim // defs as well. This happens whenever the preheader is created by splitting 763218893Sdim // the critical edge from the loop predecessor to the loop header. 764218893Sdim if (BB->pred_size() == 1) { 765276479Sdim MachineBasicBlock *TBB = nullptr, *FBB = nullptr; 766218893Sdim SmallVector<MachineOperand, 4> Cond; 767218893Sdim if (!TII->AnalyzeBranch(*BB, TBB, FBB, Cond, false) && Cond.empty()) 768218893Sdim InitRegPressure(*BB->pred_begin()); 769218893Sdim } 770218893Sdim 771288943Sdim for (const MachineInstr &MI : *BB) 772288943Sdim UpdateRegPressure(&MI, /*ConsiderUnseenAsDef=*/true); 773288943Sdim} 774218893Sdim 775296417Sdim/// Update estimate of register pressure after the specified instruction. 776288943Sdimvoid MachineLICM::UpdateRegPressure(const MachineInstr *MI, 777288943Sdim bool ConsiderUnseenAsDef) { 778288943Sdim auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/true, ConsiderUnseenAsDef); 779288943Sdim for (const auto &RPIdAndCost : Cost) { 780288943Sdim unsigned Class = RPIdAndCost.first; 781288943Sdim if (static_cast<int>(RegPressure[Class]) < -RPIdAndCost.second) 782288943Sdim RegPressure[Class] = 0; 783288943Sdim else 784288943Sdim RegPressure[Class] += RPIdAndCost.second; 785218893Sdim } 786218893Sdim} 787218893Sdim 788296417Sdim/// Calculate the additional register pressure that the registers used in MI 789296417Sdim/// cause. 790296417Sdim/// 791296417Sdim/// If 'ConsiderSeen' is true, updates 'RegSeen' and uses the information to 792296417Sdim/// figure out which usages are live-ins. 793296417Sdim/// FIXME: Figure out a way to consider 'RegSeen' from all code paths. 794288943SdimDenseMap<unsigned, int> 795288943SdimMachineLICM::calcRegisterCost(const MachineInstr *MI, bool ConsiderSeen, 796288943Sdim bool ConsiderUnseenAsDef) { 797288943Sdim DenseMap<unsigned, int> Cost; 798218893Sdim if (MI->isImplicitDef()) 799288943Sdim return Cost; 800218893Sdim for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) { 801218893Sdim const MachineOperand &MO = MI->getOperand(i); 802218893Sdim if (!MO.isReg() || MO.isImplicit()) 803218893Sdim continue; 804218893Sdim unsigned Reg = MO.getReg(); 805218893Sdim if (!TargetRegisterInfo::isVirtualRegister(Reg)) 806218893Sdim continue; 807218893Sdim 808288943Sdim // FIXME: It seems bad to use RegSeen only for some of these calculations. 809288943Sdim bool isNew = ConsiderSeen ? RegSeen.insert(Reg).second : false; 810288943Sdim const TargetRegisterClass *RC = MRI->getRegClass(Reg); 811288943Sdim 812288943Sdim RegClassWeight W = TRI->getRegClassWeight(RC); 813288943Sdim int RCCost = 0; 814218893Sdim if (MO.isDef()) 815288943Sdim RCCost = W.RegWeight; 816288943Sdim else { 817288943Sdim bool isKill = isOperandKill(MO, MRI); 818288943Sdim if (isNew && !isKill && ConsiderUnseenAsDef) 819288943Sdim // Haven't seen this, it must be a livein. 820288943Sdim RCCost = W.RegWeight; 821288943Sdim else if (!isNew && isKill) 822288943Sdim RCCost = -W.RegWeight; 823288943Sdim } 824288943Sdim if (RCCost == 0) 825288943Sdim continue; 826288943Sdim const int *PS = TRI->getRegClassPressureSets(RC); 827288943Sdim for (; *PS != -1; ++PS) { 828288943Sdim if (Cost.find(*PS) == Cost.end()) 829288943Sdim Cost[*PS] = RCCost; 830218893Sdim else 831288943Sdim Cost[*PS] += RCCost; 832218893Sdim } 833218893Sdim } 834288943Sdim return Cost; 835218893Sdim} 836218893Sdim 837296417Sdim/// Return true if this machine instruction loads from global offset table or 838296417Sdim/// constant pool. 839296417Sdimstatic bool mayLoadFromGOTOrConstantPool(MachineInstr &MI) { 840234353Sdim assert (MI.mayLoad() && "Expected MI that loads!"); 841296417Sdim 842296417Sdim // If we lost memory operands, conservatively assume that the instruction 843296417Sdim // reads from everything.. 844296417Sdim if (MI.memoperands_empty()) 845296417Sdim return true; 846296417Sdim 847296417Sdim for (MachineMemOperand *MemOp : MI.memoperands()) 848296417Sdim if (const PseudoSourceValue *PSV = MemOp->getPseudoValue()) 849296417Sdim if (PSV->isGOT() || PSV->isConstantPool()) 850276479Sdim return true; 851296417Sdim 852234353Sdim return false; 853234353Sdim} 854234353Sdim 855296417Sdim/// Returns true if the instruction may be a suitable candidate for LICM. 856296417Sdim/// e.g. If the instruction is a call, then it's obviously not safe to hoist it. 857207618Srdivackybool MachineLICM::IsLICMCandidate(MachineInstr &I) { 858210299Sed // Check if it's safe to move the instruction. 859210299Sed bool DontMoveAcrossStore = true; 860288943Sdim if (!I.isSafeToMove(AA, DontMoveAcrossStore)) 861207618Srdivacky return false; 862226633Sdim 863226633Sdim // If it is load then check if it is guaranteed to execute by making sure that 864226633Sdim // it dominates all exiting blocks. If it doesn't, then there is a path out of 865234353Sdim // the loop which does not execute this load, so we can't hoist it. Loads 866234353Sdim // from constant memory are not safe to speculate all the time, for example 867234353Sdim // indexed load from a jump table. 868226633Sdim // Stores and side effects are already checked by isSafeToMove. 869296417Sdim if (I.mayLoad() && !mayLoadFromGOTOrConstantPool(I) && 870234353Sdim !IsGuaranteedToExecute(I.getParent())) 871226633Sdim return false; 872226633Sdim 873207618Srdivacky return true; 874207618Srdivacky} 875193323Sed 876296417Sdim/// Returns true if the instruction is loop invariant. 877296417Sdim/// I.e., all virtual register operands are defined outside of the loop, 878296417Sdim/// physical registers aren't accessed explicitly, and there are no side 879207618Srdivacky/// effects that aren't captured by the operands or other flags. 880234353Sdim/// 881207618Srdivackybool MachineLICM::IsLoopInvariantInst(MachineInstr &I) { 882207618Srdivacky if (!IsLICMCandidate(I)) 883207618Srdivacky return false; 884207618Srdivacky 885193323Sed // The instruction is loop invariant if all of its operands are. 886296417Sdim for (const MachineOperand &MO : I.operands()) { 887193323Sed if (!MO.isReg()) 888193323Sed continue; 889193323Sed 890193323Sed unsigned Reg = MO.getReg(); 891193323Sed if (Reg == 0) continue; 892193323Sed 893193323Sed // Don't hoist an instruction that uses or defines a physical register. 894198090Srdivacky if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 895198090Srdivacky if (MO.isUse()) { 896198090Srdivacky // If the physreg has no defs anywhere, it's just an ambient register 897198090Srdivacky // and we can freely move its uses. Alternatively, if it's allocatable, 898198090Srdivacky // it could get allocated to something with a def during allocation. 899234353Sdim if (!MRI->isConstantPhysReg(Reg, *I.getParent()->getParent())) 900198090Srdivacky return false; 901198090Srdivacky // Otherwise it's safe to move. 902198090Srdivacky continue; 903198090Srdivacky } else if (!MO.isDead()) { 904198090Srdivacky // A def that isn't dead. We can't move it. 905198090Srdivacky return false; 906204642Srdivacky } else if (CurLoop->getHeader()->isLiveIn(Reg)) { 907204642Srdivacky // If the reg is live into the loop, we can't hoist an instruction 908204642Srdivacky // which would clobber it. 909204642Srdivacky return false; 910198090Srdivacky } 911198090Srdivacky } 912193323Sed 913193323Sed if (!MO.isUse()) 914193323Sed continue; 915193323Sed 916218893Sdim assert(MRI->getVRegDef(Reg) && 917193323Sed "Machine instr not mapped for this vreg?!"); 918193323Sed 919193323Sed // If the loop contains the definition of an operand, then the instruction 920193323Sed // isn't loop invariant. 921218893Sdim if (CurLoop->contains(MRI->getVRegDef(Reg))) 922193323Sed return false; 923193323Sed } 924193323Sed 925193323Sed // If we got this far, the instruction is loop invariant! 926193323Sed return true; 927193323Sed} 928193323Sed 929193323Sed 930296417Sdim/// Return true if the specified instruction is used by a phi node and hoisting 931296417Sdim/// it could cause a copy to be inserted. 932234353Sdimbool MachineLICM::HasLoopPHIUse(const MachineInstr *MI) const { 933234353Sdim SmallVector<const MachineInstr*, 8> Work(1, MI); 934234353Sdim do { 935234353Sdim MI = Work.pop_back_val(); 936288943Sdim for (const MachineOperand &MO : MI->operands()) { 937288943Sdim if (!MO.isReg() || !MO.isDef()) 938234353Sdim continue; 939288943Sdim unsigned Reg = MO.getReg(); 940234353Sdim if (!TargetRegisterInfo::isVirtualRegister(Reg)) 941234353Sdim continue; 942276479Sdim for (MachineInstr &UseMI : MRI->use_instructions(Reg)) { 943234353Sdim // A PHI may cause a copy to be inserted. 944276479Sdim if (UseMI.isPHI()) { 945234353Sdim // A PHI inside the loop causes a copy because the live range of Reg is 946234353Sdim // extended across the PHI. 947276479Sdim if (CurLoop->contains(&UseMI)) 948234353Sdim return true; 949234353Sdim // A PHI in an exit block can cause a copy to be inserted if the PHI 950234353Sdim // has multiple predecessors in the loop with different values. 951234353Sdim // For now, approximate by rejecting all exit blocks. 952276479Sdim if (isExitBlock(UseMI.getParent())) 953234353Sdim return true; 954234353Sdim continue; 955234353Sdim } 956234353Sdim // Look past copies as well. 957276479Sdim if (UseMI.isCopy() && CurLoop->contains(&UseMI)) 958276479Sdim Work.push_back(&UseMI); 959234353Sdim } 960221345Sdim } 961234353Sdim } while (!Work.empty()); 962193323Sed return false; 963193323Sed} 964193323Sed 965296417Sdim/// Compute operand latency between a def of 'Reg' and an use in the current 966296417Sdim/// loop, return true if the target considered it high. 967218893Sdimbool MachineLICM::HasHighOperandLatency(MachineInstr &MI, 968218893Sdim unsigned DefIdx, unsigned Reg) const { 969288943Sdim if (MRI->use_nodbg_empty(Reg)) 970218893Sdim return false; 971218893Sdim 972276479Sdim for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg)) { 973276479Sdim if (UseMI.isCopyLike()) 974218893Sdim continue; 975276479Sdim if (!CurLoop->contains(UseMI.getParent())) 976218893Sdim continue; 977276479Sdim for (unsigned i = 0, e = UseMI.getNumOperands(); i != e; ++i) { 978276479Sdim const MachineOperand &MO = UseMI.getOperand(i); 979218893Sdim if (!MO.isReg() || !MO.isUse()) 980218893Sdim continue; 981218893Sdim unsigned MOReg = MO.getReg(); 982218893Sdim if (MOReg != Reg) 983218893Sdim continue; 984218893Sdim 985288943Sdim if (TII->hasHighOperandLatency(SchedModel, MRI, &MI, DefIdx, &UseMI, i)) 986218893Sdim return true; 987218893Sdim } 988218893Sdim 989218893Sdim // Only look at the first in loop use. 990218893Sdim break; 991199989Srdivacky } 992218893Sdim 993218893Sdim return false; 994199989Srdivacky} 995199989Srdivacky 996296417Sdim/// Return true if the instruction is marked "cheap" or the operand latency 997296417Sdim/// between its def and a use is one or less. 998218893Sdimbool MachineLICM::IsCheapInstruction(MachineInstr &MI) const { 999280031Sdim if (TII->isAsCheapAsAMove(&MI) || MI.isCopyLike()) 1000218893Sdim return true; 1001218893Sdim 1002218893Sdim bool isCheap = false; 1003218893Sdim unsigned NumDefs = MI.getDesc().getNumDefs(); 1004218893Sdim for (unsigned i = 0, e = MI.getNumOperands(); NumDefs && i != e; ++i) { 1005218893Sdim MachineOperand &DefMO = MI.getOperand(i); 1006218893Sdim if (!DefMO.isReg() || !DefMO.isDef()) 1007218893Sdim continue; 1008218893Sdim --NumDefs; 1009218893Sdim unsigned Reg = DefMO.getReg(); 1010218893Sdim if (TargetRegisterInfo::isPhysicalRegister(Reg)) 1011218893Sdim continue; 1012218893Sdim 1013288943Sdim if (!TII->hasLowDefLatency(SchedModel, &MI, i)) 1014218893Sdim return false; 1015218893Sdim isCheap = true; 1016218893Sdim } 1017218893Sdim 1018218893Sdim return isCheap; 1019218893Sdim} 1020218893Sdim 1021296417Sdim/// Visit BBs from header to current BB, check if hoisting an instruction of the 1022296417Sdim/// given cost matrix can cause high register pressure. 1023288943Sdimbool MachineLICM::CanCauseHighRegPressure(const DenseMap<unsigned, int>& Cost, 1024234353Sdim bool CheapInstr) { 1025288943Sdim for (const auto &RPIdAndCost : Cost) { 1026288943Sdim if (RPIdAndCost.second <= 0) 1027218893Sdim continue; 1028218893Sdim 1029288943Sdim unsigned Class = RPIdAndCost.first; 1030288943Sdim int Limit = RegLimit[Class]; 1031234353Sdim 1032234353Sdim // Don't hoist cheap instructions if they would increase register pressure, 1033234353Sdim // even if we're under the limit. 1034280031Sdim if (CheapInstr && !HoistCheapInsts) 1035234353Sdim return true; 1036234353Sdim 1037288943Sdim for (const auto &RP : BackTrace) 1038288943Sdim if (static_cast<int>(RP[Class]) + RPIdAndCost.second >= Limit) 1039218893Sdim return true; 1040218893Sdim } 1041218893Sdim 1042218893Sdim return false; 1043218893Sdim} 1044218893Sdim 1045296417Sdim/// Traverse the back trace from header to the current block and update their 1046296417Sdim/// register pressures to reflect the effect of hoisting MI from the current 1047296417Sdim/// block to the preheader. 1048218893Sdimvoid MachineLICM::UpdateBackTraceRegPressure(const MachineInstr *MI) { 1049218893Sdim // First compute the 'cost' of the instruction, i.e. its contribution 1050218893Sdim // to register pressure. 1051288943Sdim auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/false, 1052288943Sdim /*ConsiderUnseenAsDef=*/false); 1053218893Sdim 1054218893Sdim // Update register pressure of blocks from loop header to current block. 1055288943Sdim for (auto &RP : BackTrace) 1056288943Sdim for (const auto &RPIdAndCost : Cost) 1057288943Sdim RP[RPIdAndCost.first] += RPIdAndCost.second; 1058218893Sdim} 1059218893Sdim 1060296417Sdim/// Return true if it is potentially profitable to hoist the given loop 1061296417Sdim/// invariant. 1062193323Sedbool MachineLICM::IsProfitableToHoist(MachineInstr &MI) { 1063218893Sdim if (MI.isImplicitDef()) 1064218893Sdim return true; 1065218893Sdim 1066234353Sdim // Besides removing computation from the loop, hoisting an instruction has 1067234353Sdim // these effects: 1068234353Sdim // 1069234353Sdim // - The value defined by the instruction becomes live across the entire 1070234353Sdim // loop. This increases register pressure in the loop. 1071234353Sdim // 1072234353Sdim // - If the value is used by a PHI in the loop, a copy will be required for 1073234353Sdim // lowering the PHI after extending the live range. 1074234353Sdim // 1075234353Sdim // - When hoisting the last use of a value in the loop, that value no longer 1076234353Sdim // needs to be live in the loop. This lowers register pressure in the loop. 1077226633Sdim 1078234353Sdim bool CheapInstr = IsCheapInstruction(MI); 1079234353Sdim bool CreatesCopy = HasLoopPHIUse(&MI); 1080218893Sdim 1081234353Sdim // Don't hoist a cheap instruction if it would create a copy in the loop. 1082234353Sdim if (CheapInstr && CreatesCopy) { 1083234353Sdim DEBUG(dbgs() << "Won't hoist cheap instr with loop PHI use: " << MI); 1084234353Sdim return false; 1085234353Sdim } 1086234353Sdim 1087234353Sdim // Rematerializable instructions should always be hoisted since the register 1088234353Sdim // allocator can just pull them down again when needed. 1089234353Sdim if (TII->isTriviallyReMaterializable(&MI, AA)) 1090234353Sdim return true; 1091234353Sdim 1092234353Sdim // FIXME: If there are long latency loop-invariant instructions inside the 1093234353Sdim // loop at this point, why didn't the optimizer's LICM hoist them? 1094234353Sdim for (unsigned i = 0, e = MI.getDesc().getNumOperands(); i != e; ++i) { 1095234353Sdim const MachineOperand &MO = MI.getOperand(i); 1096234353Sdim if (!MO.isReg() || MO.isImplicit()) 1097234353Sdim continue; 1098234353Sdim unsigned Reg = MO.getReg(); 1099234353Sdim if (!TargetRegisterInfo::isVirtualRegister(Reg)) 1100234353Sdim continue; 1101288943Sdim if (MO.isDef() && HasHighOperandLatency(MI, i, Reg)) { 1102288943Sdim DEBUG(dbgs() << "Hoist High Latency: " << MI); 1103288943Sdim ++NumHighLatency; 1104288943Sdim return true; 1105218893Sdim } 1106234353Sdim } 1107218893Sdim 1108288943Sdim // Estimate register pressure to determine whether to LICM the instruction. 1109288943Sdim // In low register pressure situation, we can be more aggressive about 1110288943Sdim // hoisting. Also, favors hoisting long latency instructions even in 1111288943Sdim // moderately high pressure situation. 1112288943Sdim // Cheap instructions will only be hoisted if they don't increase register 1113288943Sdim // pressure at all. 1114288943Sdim auto Cost = calcRegisterCost(&MI, /*ConsiderSeen=*/false, 1115288943Sdim /*ConsiderUnseenAsDef=*/false); 1116288943Sdim 1117234353Sdim // Visit BBs from header to current BB, if hoisting this doesn't cause 1118234353Sdim // high register pressure, then it's safe to proceed. 1119234353Sdim if (!CanCauseHighRegPressure(Cost, CheapInstr)) { 1120234353Sdim DEBUG(dbgs() << "Hoist non-reg-pressure: " << MI); 1121234353Sdim ++NumLowRP; 1122234353Sdim return true; 1123234353Sdim } 1124218893Sdim 1125234353Sdim // Don't risk increasing register pressure if it would create copies. 1126234353Sdim if (CreatesCopy) { 1127234353Sdim DEBUG(dbgs() << "Won't hoist instr with loop PHI use: " << MI); 1128234353Sdim return false; 1129234353Sdim } 1130226633Sdim 1131234353Sdim // Do not "speculate" in high register pressure situation. If an 1132234353Sdim // instruction is not guaranteed to be executed in the loop, it's best to be 1133234353Sdim // conservative. 1134234353Sdim if (AvoidSpeculation && 1135234353Sdim (!IsGuaranteedToExecute(MI.getParent()) && !MayCSE(&MI))) { 1136234353Sdim DEBUG(dbgs() << "Won't speculate: " << MI); 1137234353Sdim return false; 1138199989Srdivacky } 1139193323Sed 1140234353Sdim // High register pressure situation, only hoist if the instruction is going 1141234353Sdim // to be remat'ed. 1142234353Sdim if (!TII->isTriviallyReMaterializable(&MI, AA) && 1143234353Sdim !MI.isInvariantLoad(AA)) { 1144234353Sdim DEBUG(dbgs() << "Can't remat / high reg-pressure: " << MI); 1145234353Sdim return false; 1146193323Sed } 1147193323Sed 1148193323Sed return true; 1149193323Sed} 1150193323Sed 1151296417Sdim/// Unfold a load from the given machineinstr if the load itself could be 1152296417Sdim/// hoisted. Return the unfolded and hoistable load, or null if the load 1153296417Sdim/// couldn't be unfolded or if it wouldn't be hoistable. 1154198892SrdivackyMachineInstr *MachineLICM::ExtractHoistableLoad(MachineInstr *MI) { 1155218893Sdim // Don't unfold simple loads. 1156234353Sdim if (MI->canFoldAsLoad()) 1157276479Sdim return nullptr; 1158218893Sdim 1159198892Srdivacky // If not, we may be able to unfold a load and hoist that. 1160198892Srdivacky // First test whether the instruction is loading from an amenable 1161198892Srdivacky // memory location. 1162218893Sdim if (!MI->isInvariantLoad(AA)) 1163276479Sdim return nullptr; 1164199989Srdivacky 1165198892Srdivacky // Next determine the register class for a temporary register. 1166198892Srdivacky unsigned LoadRegIndex; 1167198892Srdivacky unsigned NewOpc = 1168198892Srdivacky TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(), 1169198892Srdivacky /*UnfoldLoad=*/true, 1170198892Srdivacky /*UnfoldStore=*/false, 1171198892Srdivacky &LoadRegIndex); 1172276479Sdim if (NewOpc == 0) return nullptr; 1173224145Sdim const MCInstrDesc &MID = TII->get(NewOpc); 1174276479Sdim if (MID.getNumDefs() != 1) return nullptr; 1175239462Sdim MachineFunction &MF = *MI->getParent()->getParent(); 1176239462Sdim const TargetRegisterClass *RC = TII->getRegClass(MID, LoadRegIndex, TRI, MF); 1177198892Srdivacky // Ok, we're unfolding. Create a temporary register and do the unfold. 1178218893Sdim unsigned Reg = MRI->createVirtualRegister(RC); 1179199989Srdivacky 1180198892Srdivacky SmallVector<MachineInstr *, 2> NewMIs; 1181198892Srdivacky bool Success = 1182198892Srdivacky TII->unfoldMemoryOperand(MF, MI, Reg, 1183198892Srdivacky /*UnfoldLoad=*/true, /*UnfoldStore=*/false, 1184198892Srdivacky NewMIs); 1185198892Srdivacky (void)Success; 1186198892Srdivacky assert(Success && 1187198892Srdivacky "unfoldMemoryOperand failed when getOpcodeAfterMemoryUnfold " 1188198892Srdivacky "succeeded!"); 1189198892Srdivacky assert(NewMIs.size() == 2 && 1190198892Srdivacky "Unfolded a load into multiple instructions!"); 1191198892Srdivacky MachineBasicBlock *MBB = MI->getParent(); 1192234353Sdim MachineBasicBlock::iterator Pos = MI; 1193234353Sdim MBB->insert(Pos, NewMIs[0]); 1194234353Sdim MBB->insert(Pos, NewMIs[1]); 1195198892Srdivacky // If unfolding produced a load that wasn't loop-invariant or profitable to 1196198892Srdivacky // hoist, discard the new instructions and bail. 1197198892Srdivacky if (!IsLoopInvariantInst(*NewMIs[0]) || !IsProfitableToHoist(*NewMIs[0])) { 1198198892Srdivacky NewMIs[0]->eraseFromParent(); 1199198892Srdivacky NewMIs[1]->eraseFromParent(); 1200276479Sdim return nullptr; 1201198892Srdivacky } 1202218893Sdim 1203218893Sdim // Update register pressure for the unfolded instruction. 1204218893Sdim UpdateRegPressure(NewMIs[1]); 1205218893Sdim 1206198892Srdivacky // Otherwise we successfully unfolded a load that we can hoist. 1207198892Srdivacky MI->eraseFromParent(); 1208198892Srdivacky return NewMIs[0]; 1209198892Srdivacky} 1210198892Srdivacky 1211296417Sdim/// Initialize the CSE map with instructions that are in the current loop 1212296417Sdim/// preheader that may become duplicates of instructions that are hoisted 1213296417Sdim/// out of the loop. 1214198892Srdivackyvoid MachineLICM::InitCSEMap(MachineBasicBlock *BB) { 1215296417Sdim for (MachineInstr &MI : *BB) 1216296417Sdim CSEMap[MI.getOpcode()].push_back(&MI); 1217198892Srdivacky} 1218198892Srdivacky 1219296417Sdim/// Find an instruction amount PrevMIs that is a duplicate of MI. 1220296417Sdim/// Return this instruction if it's found. 1221199481Srdivackyconst MachineInstr* 1222199481SrdivackyMachineLICM::LookForDuplicate(const MachineInstr *MI, 1223199481Srdivacky std::vector<const MachineInstr*> &PrevMIs) { 1224296417Sdim for (const MachineInstr *PrevMI : PrevMIs) 1225276479Sdim if (TII->produceSameValue(MI, PrevMI, (PreRegAlloc ? MRI : nullptr))) 1226198953Srdivacky return PrevMI; 1227296417Sdim 1228276479Sdim return nullptr; 1229198953Srdivacky} 1230198953Srdivacky 1231296417Sdim/// Given a LICM'ed instruction, look for an instruction on the preheader that 1232296417Sdim/// computes the same value. If it's found, do a RAU on with the definition of 1233296417Sdim/// the existing instruction rather than hoisting the instruction to the 1234296417Sdim/// preheader. 1235198953Srdivackybool MachineLICM::EliminateCSE(MachineInstr *MI, 1236198953Srdivacky DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator &CI) { 1237210299Sed // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate 1238210299Sed // the undef property onto uses. 1239210299Sed if (CI == CSEMap.end() || MI->isImplicitDef()) 1240199481Srdivacky return false; 1241199481Srdivacky 1242199481Srdivacky if (const MachineInstr *Dup = LookForDuplicate(MI, CI->second)) { 1243202375Srdivacky DEBUG(dbgs() << "CSEing " << *MI << " with " << *Dup); 1244204642Srdivacky 1245204642Srdivacky // Replace virtual registers defined by MI by their counterparts defined 1246204642Srdivacky // by Dup. 1247234353Sdim SmallVector<unsigned, 2> Defs; 1248199481Srdivacky for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1249199481Srdivacky const MachineOperand &MO = MI->getOperand(i); 1250204642Srdivacky 1251204642Srdivacky // Physical registers may not differ here. 1252204642Srdivacky assert((!MO.isReg() || MO.getReg() == 0 || 1253204642Srdivacky !TargetRegisterInfo::isPhysicalRegister(MO.getReg()) || 1254204642Srdivacky MO.getReg() == Dup->getOperand(i).getReg()) && 1255204642Srdivacky "Instructions with different phys regs are not identical!"); 1256204642Srdivacky 1257204642Srdivacky if (MO.isReg() && MO.isDef() && 1258234353Sdim !TargetRegisterInfo::isPhysicalRegister(MO.getReg())) 1259234353Sdim Defs.push_back(i); 1260234353Sdim } 1261234353Sdim 1262234353Sdim SmallVector<const TargetRegisterClass*, 2> OrigRCs; 1263234353Sdim for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 1264234353Sdim unsigned Idx = Defs[i]; 1265234353Sdim unsigned Reg = MI->getOperand(Idx).getReg(); 1266234353Sdim unsigned DupReg = Dup->getOperand(Idx).getReg(); 1267234353Sdim OrigRCs.push_back(MRI->getRegClass(DupReg)); 1268234353Sdim 1269234353Sdim if (!MRI->constrainRegClass(DupReg, MRI->getRegClass(Reg))) { 1270234353Sdim // Restore old RCs if more than one defs. 1271234353Sdim for (unsigned j = 0; j != i; ++j) 1272234353Sdim MRI->setRegClass(Dup->getOperand(Defs[j]).getReg(), OrigRCs[j]); 1273234353Sdim return false; 1274208599Srdivacky } 1275198953Srdivacky } 1276234353Sdim 1277296417Sdim for (unsigned Idx : Defs) { 1278234353Sdim unsigned Reg = MI->getOperand(Idx).getReg(); 1279234353Sdim unsigned DupReg = Dup->getOperand(Idx).getReg(); 1280234353Sdim MRI->replaceRegWith(Reg, DupReg); 1281234353Sdim MRI->clearKillFlags(DupReg); 1282234353Sdim } 1283234353Sdim 1284199481Srdivacky MI->eraseFromParent(); 1285199481Srdivacky ++NumCSEed; 1286199481Srdivacky return true; 1287198953Srdivacky } 1288198953Srdivacky return false; 1289198953Srdivacky} 1290198953Srdivacky 1291296417Sdim/// Return true if the given instruction will be CSE'd if it's hoisted out of 1292296417Sdim/// the loop. 1293226633Sdimbool MachineLICM::MayCSE(MachineInstr *MI) { 1294226633Sdim unsigned Opcode = MI->getOpcode(); 1295226633Sdim DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator 1296226633Sdim CI = CSEMap.find(Opcode); 1297226633Sdim // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate 1298226633Sdim // the undef property onto uses. 1299226633Sdim if (CI == CSEMap.end() || MI->isImplicitDef()) 1300226633Sdim return false; 1301226633Sdim 1302276479Sdim return LookForDuplicate(MI, CI->second) != nullptr; 1303226633Sdim} 1304226633Sdim 1305296417Sdim/// When an instruction is found to use only loop invariant operands 1306193323Sed/// that are safe to hoist, this instruction is called to do the dirty work. 1307296417Sdim/// It returns true if the instruction is hoisted. 1308218893Sdimbool MachineLICM::Hoist(MachineInstr *MI, MachineBasicBlock *Preheader) { 1309198892Srdivacky // First check whether we should hoist this instruction. 1310198892Srdivacky if (!IsLoopInvariantInst(*MI) || !IsProfitableToHoist(*MI)) { 1311198892Srdivacky // If not, try unfolding a hoistable load. 1312198892Srdivacky MI = ExtractHoistableLoad(MI); 1313218893Sdim if (!MI) return false; 1314198892Srdivacky } 1315193323Sed 1316193323Sed // Now move the instructions to the predecessor, inserting it before any 1317193323Sed // terminator instructions. 1318193323Sed DEBUG({ 1319202375Srdivacky dbgs() << "Hoisting " << *MI; 1320210299Sed if (Preheader->getBasicBlock()) 1321202375Srdivacky dbgs() << " to MachineBasicBlock " 1322210299Sed << Preheader->getName(); 1323198892Srdivacky if (MI->getParent()->getBasicBlock()) 1324202375Srdivacky dbgs() << " from MachineBasicBlock " 1325199989Srdivacky << MI->getParent()->getName(); 1326202375Srdivacky dbgs() << "\n"; 1327193323Sed }); 1328193323Sed 1329198892Srdivacky // If this is the first instruction being hoisted to the preheader, 1330198892Srdivacky // initialize the CSE map with potential common expressions. 1331210299Sed if (FirstInLoop) { 1332210299Sed InitCSEMap(Preheader); 1333210299Sed FirstInLoop = false; 1334210299Sed } 1335198892Srdivacky 1336193323Sed // Look for opportunity to CSE the hoisted instruction. 1337198892Srdivacky unsigned Opcode = MI->getOpcode(); 1338198892Srdivacky DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator 1339198892Srdivacky CI = CSEMap.find(Opcode); 1340198953Srdivacky if (!EliminateCSE(MI, CI)) { 1341198953Srdivacky // Otherwise, splice the instruction to the preheader. 1342210299Sed Preheader->splice(Preheader->getFirstTerminator(),MI->getParent(),MI); 1343198892Srdivacky 1344218893Sdim // Update register pressure for BBs from header to this block. 1345218893Sdim UpdateBackTraceRegPressure(MI); 1346218893Sdim 1347208599Srdivacky // Clear the kill flags of any register this instruction defines, 1348208599Srdivacky // since they may need to be live throughout the entire loop 1349208599Srdivacky // rather than just live for part of it. 1350296417Sdim for (MachineOperand &MO : MI->operands()) 1351208599Srdivacky if (MO.isReg() && MO.isDef() && !MO.isDead()) 1352218893Sdim MRI->clearKillFlags(MO.getReg()); 1353208599Srdivacky 1354193323Sed // Add to the CSE map. 1355193323Sed if (CI != CSEMap.end()) 1356198892Srdivacky CI->second.push_back(MI); 1357280031Sdim else 1358280031Sdim CSEMap[Opcode].push_back(MI); 1359193323Sed } 1360193323Sed 1361193323Sed ++NumHoisted; 1362193323Sed Changed = true; 1363218893Sdim 1364218893Sdim return true; 1365193323Sed} 1366210299Sed 1367296417Sdim/// Get the preheader for the current loop, splitting a critical edge if needed. 1368210299SedMachineBasicBlock *MachineLICM::getCurPreheader() { 1369210299Sed // Determine the block to which to hoist instructions. If we can't find a 1370210299Sed // suitable loop predecessor, we can't do any hoisting. 1371210299Sed 1372210299Sed // If we've tried to get a preheader and failed, don't try again. 1373210299Sed if (CurPreheader == reinterpret_cast<MachineBasicBlock *>(-1)) 1374276479Sdim return nullptr; 1375210299Sed 1376210299Sed if (!CurPreheader) { 1377210299Sed CurPreheader = CurLoop->getLoopPreheader(); 1378210299Sed if (!CurPreheader) { 1379210299Sed MachineBasicBlock *Pred = CurLoop->getLoopPredecessor(); 1380210299Sed if (!Pred) { 1381210299Sed CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1); 1382276479Sdim return nullptr; 1383210299Sed } 1384210299Sed 1385210299Sed CurPreheader = Pred->SplitCriticalEdge(CurLoop->getHeader(), this); 1386210299Sed if (!CurPreheader) { 1387210299Sed CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1); 1388276479Sdim return nullptr; 1389210299Sed } 1390210299Sed } 1391210299Sed } 1392210299Sed return CurPreheader; 1393210299Sed} 1394