MachineLICM.cpp revision 207618
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 does not attempt to throttle itself to limit register pressure. 14193323Sed// The register allocation phases are expected to perform rematerialization 15193323Sed// to recover when register pressure is high. 16193323Sed// 17193323Sed// This pass is not intended to be a replacement or a complete alternative 18193323Sed// for the LLVM-IR-level LICM pass. It is only designed to hoist simple 19193323Sed// constructs that are not exposed before lowering and instruction selection. 20193323Sed// 21193323Sed//===----------------------------------------------------------------------===// 22193323Sed 23193323Sed#define DEBUG_TYPE "machine-licm" 24193323Sed#include "llvm/CodeGen/Passes.h" 25193323Sed#include "llvm/CodeGen/MachineDominators.h" 26207618Srdivacky#include "llvm/CodeGen/MachineFrameInfo.h" 27193323Sed#include "llvm/CodeGen/MachineLoopInfo.h" 28198892Srdivacky#include "llvm/CodeGen/MachineMemOperand.h" 29193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 30198892Srdivacky#include "llvm/CodeGen/PseudoSourceValue.h" 31193323Sed#include "llvm/Target/TargetRegisterInfo.h" 32193323Sed#include "llvm/Target/TargetInstrInfo.h" 33193323Sed#include "llvm/Target/TargetMachine.h" 34198090Srdivacky#include "llvm/Analysis/AliasAnalysis.h" 35193323Sed#include "llvm/ADT/DenseMap.h" 36207618Srdivacky#include "llvm/ADT/SmallSet.h" 37193323Sed#include "llvm/ADT/Statistic.h" 38193323Sed#include "llvm/Support/Debug.h" 39198090Srdivacky#include "llvm/Support/raw_ostream.h" 40193323Sed 41193323Sedusing namespace llvm; 42193323Sed 43193323SedSTATISTIC(NumHoisted, "Number of machine instructions hoisted out of loops"); 44193323SedSTATISTIC(NumCSEed, "Number of hoisted machine instructions CSEed"); 45207618SrdivackySTATISTIC(NumPostRAHoisted, 46207618Srdivacky "Number of machine instructions hoisted out of loops post regalloc"); 47193323Sed 48193323Sednamespace { 49198892Srdivacky class MachineLICM : public MachineFunctionPass { 50207618Srdivacky bool PreRegAlloc; 51207618Srdivacky 52193323Sed const TargetMachine *TM; 53193323Sed const TargetInstrInfo *TII; 54198090Srdivacky const TargetRegisterInfo *TRI; 55207618Srdivacky const MachineFrameInfo *MFI; 56207618Srdivacky MachineRegisterInfo *RegInfo; 57193323Sed 58193323Sed // Various analyses that we use... 59198090Srdivacky AliasAnalysis *AA; // Alias analysis info. 60207618Srdivacky MachineLoopInfo *MLI; // Current MachineLoopInfo 61193323Sed MachineDominatorTree *DT; // Machine dominator tree for the cur loop 62193323Sed 63193323Sed // State that is updated as we process loops 64193323Sed bool Changed; // True if a loop is changed. 65193323Sed MachineLoop *CurLoop; // The current loop we are working on. 66193323Sed MachineBasicBlock *CurPreheader; // The preheader for CurLoop. 67193323Sed 68207618Srdivacky BitVector AllocatableSet; 69207618Srdivacky 70198892Srdivacky // For each opcode, keep a list of potentail CSE instructions. 71198892Srdivacky DenseMap<unsigned, std::vector<const MachineInstr*> > CSEMap; 72207618Srdivacky 73193323Sed public: 74193323Sed static char ID; // Pass identification, replacement for typeid 75207618Srdivacky MachineLICM() : 76207618Srdivacky MachineFunctionPass(&ID), PreRegAlloc(true) {} 77193323Sed 78207618Srdivacky explicit MachineLICM(bool PreRA) : 79207618Srdivacky MachineFunctionPass(&ID), PreRegAlloc(PreRA) {} 80207618Srdivacky 81193323Sed virtual bool runOnMachineFunction(MachineFunction &MF); 82193323Sed 83193323Sed const char *getPassName() const { return "Machine Instruction LICM"; } 84193323Sed 85193323Sed // FIXME: Loop preheaders? 86193323Sed virtual void getAnalysisUsage(AnalysisUsage &AU) const { 87193323Sed AU.setPreservesCFG(); 88193323Sed AU.addRequired<MachineLoopInfo>(); 89193323Sed AU.addRequired<MachineDominatorTree>(); 90198090Srdivacky AU.addRequired<AliasAnalysis>(); 91193323Sed AU.addPreserved<MachineLoopInfo>(); 92193323Sed AU.addPreserved<MachineDominatorTree>(); 93193323Sed MachineFunctionPass::getAnalysisUsage(AU); 94193323Sed } 95193323Sed 96193323Sed virtual void releaseMemory() { 97193323Sed CSEMap.clear(); 98193323Sed } 99193323Sed 100193323Sed private: 101207618Srdivacky /// CandidateInfo - Keep track of information about hoisting candidates. 102207618Srdivacky struct CandidateInfo { 103207618Srdivacky MachineInstr *MI; 104207618Srdivacky unsigned Def; 105207618Srdivacky int FI; 106207618Srdivacky CandidateInfo(MachineInstr *mi, unsigned def, int fi) 107207618Srdivacky : MI(mi), Def(def), FI(fi) {} 108207618Srdivacky }; 109207618Srdivacky 110207618Srdivacky /// HoistRegionPostRA - Walk the specified region of the CFG and hoist loop 111207618Srdivacky /// invariants out to the preheader. 112207618Srdivacky void HoistRegionPostRA(); 113207618Srdivacky 114207618Srdivacky /// HoistPostRA - When an instruction is found to only use loop invariant 115207618Srdivacky /// operands that is safe to hoist, this instruction is called to do the 116207618Srdivacky /// dirty work. 117207618Srdivacky void HoistPostRA(MachineInstr *MI, unsigned Def); 118207618Srdivacky 119207618Srdivacky /// ProcessMI - Examine the instruction for potentai LICM candidate. Also 120207618Srdivacky /// gather register def and frame object update information. 121207618Srdivacky void ProcessMI(MachineInstr *MI, unsigned *PhysRegDefs, 122207618Srdivacky SmallSet<int, 32> &StoredFIs, 123207618Srdivacky SmallVector<CandidateInfo, 32> &Candidates); 124207618Srdivacky 125207618Srdivacky /// AddToLiveIns - Add register 'Reg' to the livein sets of BBs in the 126207618Srdivacky /// current loop. 127207618Srdivacky void AddToLiveIns(unsigned Reg); 128207618Srdivacky 129207618Srdivacky /// IsLICMCandidate - Returns true if the instruction may be a suitable 130207618Srdivacky /// candidate for LICM. e.g. If the instruction is a call, then it's obviously 131207618Srdivacky /// not safe to hoist it. 132207618Srdivacky bool IsLICMCandidate(MachineInstr &I); 133207618Srdivacky 134193323Sed /// IsLoopInvariantInst - Returns true if the instruction is loop 135193323Sed /// invariant. I.e., all virtual register operands are defined outside of 136193323Sed /// the loop, physical registers aren't accessed (explicitly or implicitly), 137193323Sed /// and the instruction is hoistable. 138193323Sed /// 139193323Sed bool IsLoopInvariantInst(MachineInstr &I); 140193323Sed 141193323Sed /// IsProfitableToHoist - Return true if it is potentially profitable to 142193323Sed /// hoist the given loop invariant. 143193323Sed bool IsProfitableToHoist(MachineInstr &MI); 144193323Sed 145193323Sed /// HoistRegion - Walk the specified region of the CFG (defined by all 146193323Sed /// blocks dominated by the specified block, and that are in the current 147193323Sed /// loop) in depth first order w.r.t the DominatorTree. This allows us to 148193323Sed /// visit definitions before uses, allowing us to hoist a loop body in one 149193323Sed /// pass without iteration. 150193323Sed /// 151193323Sed void HoistRegion(MachineDomTreeNode *N); 152193323Sed 153199989Srdivacky /// isLoadFromConstantMemory - Return true if the given instruction is a 154199989Srdivacky /// load from constant memory. 155199989Srdivacky bool isLoadFromConstantMemory(MachineInstr *MI); 156199989Srdivacky 157198892Srdivacky /// ExtractHoistableLoad - Unfold a load from the given machineinstr if 158198892Srdivacky /// the load itself could be hoisted. Return the unfolded and hoistable 159198892Srdivacky /// load, or null if the load couldn't be unfolded or if it wouldn't 160198892Srdivacky /// be hoistable. 161198892Srdivacky MachineInstr *ExtractHoistableLoad(MachineInstr *MI); 162198892Srdivacky 163199481Srdivacky /// LookForDuplicate - Find an instruction amount PrevMIs that is a 164199481Srdivacky /// duplicate of MI. Return this instruction if it's found. 165199481Srdivacky const MachineInstr *LookForDuplicate(const MachineInstr *MI, 166199481Srdivacky std::vector<const MachineInstr*> &PrevMIs); 167199481Srdivacky 168198953Srdivacky /// EliminateCSE - Given a LICM'ed instruction, look for an instruction on 169198953Srdivacky /// the preheader that compute the same value. If it's found, do a RAU on 170198953Srdivacky /// with the definition of the existing instruction rather than hoisting 171198953Srdivacky /// the instruction to the preheader. 172198953Srdivacky bool EliminateCSE(MachineInstr *MI, 173198953Srdivacky DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator &CI); 174198953Srdivacky 175193323Sed /// Hoist - When an instruction is found to only use loop invariant operands 176193323Sed /// that is safe to hoist, this instruction is called to do the dirty work. 177193323Sed /// 178198892Srdivacky void Hoist(MachineInstr *MI); 179198892Srdivacky 180198892Srdivacky /// InitCSEMap - Initialize the CSE map with instructions that are in the 181198892Srdivacky /// current loop preheader that may become duplicates of instructions that 182198892Srdivacky /// are hoisted out of the loop. 183198892Srdivacky void InitCSEMap(MachineBasicBlock *BB); 184193323Sed }; 185193323Sed} // end anonymous namespace 186193323Sed 187193323Sedchar MachineLICM::ID = 0; 188193323Sedstatic RegisterPass<MachineLICM> 189193323SedX("machinelicm", "Machine Loop Invariant Code Motion"); 190193323Sed 191207618SrdivackyFunctionPass *llvm::createMachineLICMPass(bool PreRegAlloc) { 192207618Srdivacky return new MachineLICM(PreRegAlloc); 193207618Srdivacky} 194193323Sed 195193323Sed/// LoopIsOuterMostWithPreheader - Test if the given loop is the outer-most 196193323Sed/// loop that has a preheader. 197193323Sedstatic bool LoopIsOuterMostWithPreheader(MachineLoop *CurLoop) { 198193323Sed for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop()) 199193323Sed if (L->getLoopPreheader()) 200193323Sed return false; 201193323Sed return true; 202193323Sed} 203193323Sed 204193323Sedbool MachineLICM::runOnMachineFunction(MachineFunction &MF) { 205207618Srdivacky if (PreRegAlloc) 206207618Srdivacky DEBUG(dbgs() << "******** Pre-regalloc Machine LICM ********\n"); 207207618Srdivacky else 208207618Srdivacky DEBUG(dbgs() << "******** Post-regalloc Machine LICM ********\n"); 209193323Sed 210207618Srdivacky Changed = false; 211193323Sed TM = &MF.getTarget(); 212193323Sed TII = TM->getInstrInfo(); 213198090Srdivacky TRI = TM->getRegisterInfo(); 214207618Srdivacky MFI = MF.getFrameInfo(); 215193323Sed RegInfo = &MF.getRegInfo(); 216198090Srdivacky AllocatableSet = TRI->getAllocatableSet(MF); 217193323Sed 218193323Sed // Get our Loop information... 219207618Srdivacky MLI = &getAnalysis<MachineLoopInfo>(); 220207618Srdivacky DT = &getAnalysis<MachineDominatorTree>(); 221207618Srdivacky AA = &getAnalysis<AliasAnalysis>(); 222193323Sed 223207618Srdivacky for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); I != E; ++I){ 224193323Sed CurLoop = *I; 225193323Sed 226207618Srdivacky // If this is done before regalloc, only visit outer-most preheader-sporting 227207618Srdivacky // loops. 228207618Srdivacky if (PreRegAlloc && !LoopIsOuterMostWithPreheader(CurLoop)) 229193323Sed continue; 230193323Sed 231193323Sed // Determine the block to which to hoist instructions. If we can't find a 232193323Sed // suitable loop preheader, we can't do any hoisting. 233193323Sed // 234193323Sed // FIXME: We are only hoisting if the basic block coming into this loop 235193323Sed // has only one successor. This isn't the case in general because we haven't 236193323Sed // broken critical edges or added preheaders. 237193323Sed CurPreheader = CurLoop->getLoopPreheader(); 238193323Sed if (!CurPreheader) 239193323Sed continue; 240193323Sed 241207618Srdivacky if (!PreRegAlloc) 242207618Srdivacky HoistRegionPostRA(); 243207618Srdivacky else { 244207618Srdivacky // CSEMap is initialized for loop header when the first instruction is 245207618Srdivacky // being hoisted. 246207618Srdivacky MachineDomTreeNode *N = DT->getNode(CurLoop->getHeader()); 247207618Srdivacky HoistRegion(N); 248207618Srdivacky CSEMap.clear(); 249207618Srdivacky } 250193323Sed } 251193323Sed 252193323Sed return Changed; 253193323Sed} 254193323Sed 255207618Srdivacky/// InstructionStoresToFI - Return true if instruction stores to the 256207618Srdivacky/// specified frame. 257207618Srdivackystatic bool InstructionStoresToFI(const MachineInstr *MI, int FI) { 258207618Srdivacky for (MachineInstr::mmo_iterator o = MI->memoperands_begin(), 259207618Srdivacky oe = MI->memoperands_end(); o != oe; ++o) { 260207618Srdivacky if (!(*o)->isStore() || !(*o)->getValue()) 261207618Srdivacky continue; 262207618Srdivacky if (const FixedStackPseudoSourceValue *Value = 263207618Srdivacky dyn_cast<const FixedStackPseudoSourceValue>((*o)->getValue())) { 264207618Srdivacky if (Value->getFrameIndex() == FI) 265207618Srdivacky return true; 266207618Srdivacky } 267207618Srdivacky } 268207618Srdivacky return false; 269207618Srdivacky} 270207618Srdivacky 271207618Srdivacky/// ProcessMI - Examine the instruction for potentai LICM candidate. Also 272207618Srdivacky/// gather register def and frame object update information. 273207618Srdivackyvoid MachineLICM::ProcessMI(MachineInstr *MI, 274207618Srdivacky unsigned *PhysRegDefs, 275207618Srdivacky SmallSet<int, 32> &StoredFIs, 276207618Srdivacky SmallVector<CandidateInfo, 32> &Candidates) { 277207618Srdivacky bool RuledOut = false; 278207618Srdivacky bool HasNonInvariantUse = false; 279207618Srdivacky unsigned Def = 0; 280207618Srdivacky for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 281207618Srdivacky const MachineOperand &MO = MI->getOperand(i); 282207618Srdivacky if (MO.isFI()) { 283207618Srdivacky // Remember if the instruction stores to the frame index. 284207618Srdivacky int FI = MO.getIndex(); 285207618Srdivacky if (!StoredFIs.count(FI) && 286207618Srdivacky MFI->isSpillSlotObjectIndex(FI) && 287207618Srdivacky InstructionStoresToFI(MI, FI)) 288207618Srdivacky StoredFIs.insert(FI); 289207618Srdivacky HasNonInvariantUse = true; 290207618Srdivacky continue; 291207618Srdivacky } 292207618Srdivacky 293207618Srdivacky if (!MO.isReg()) 294207618Srdivacky continue; 295207618Srdivacky unsigned Reg = MO.getReg(); 296207618Srdivacky if (!Reg) 297207618Srdivacky continue; 298207618Srdivacky assert(TargetRegisterInfo::isPhysicalRegister(Reg) && 299207618Srdivacky "Not expecting virtual register!"); 300207618Srdivacky 301207618Srdivacky if (!MO.isDef()) { 302207618Srdivacky if (Reg && PhysRegDefs[Reg]) 303207618Srdivacky // If it's using a non-loop-invariant register, then it's obviously not 304207618Srdivacky // safe to hoist. 305207618Srdivacky HasNonInvariantUse = true; 306207618Srdivacky continue; 307207618Srdivacky } 308207618Srdivacky 309207618Srdivacky if (MO.isImplicit()) { 310207618Srdivacky ++PhysRegDefs[Reg]; 311207618Srdivacky for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) 312207618Srdivacky ++PhysRegDefs[*AS]; 313207618Srdivacky if (!MO.isDead()) 314207618Srdivacky // Non-dead implicit def? This cannot be hoisted. 315207618Srdivacky RuledOut = true; 316207618Srdivacky // No need to check if a dead implicit def is also defined by 317207618Srdivacky // another instruction. 318207618Srdivacky continue; 319207618Srdivacky } 320207618Srdivacky 321207618Srdivacky // FIXME: For now, avoid instructions with multiple defs, unless 322207618Srdivacky // it's a dead implicit def. 323207618Srdivacky if (Def) 324207618Srdivacky RuledOut = true; 325207618Srdivacky else 326207618Srdivacky Def = Reg; 327207618Srdivacky 328207618Srdivacky // If we have already seen another instruction that defines the same 329207618Srdivacky // register, then this is not safe. 330207618Srdivacky if (++PhysRegDefs[Reg] > 1) 331207618Srdivacky // MI defined register is seen defined by another instruction in 332207618Srdivacky // the loop, it cannot be a LICM candidate. 333207618Srdivacky RuledOut = true; 334207618Srdivacky for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) 335207618Srdivacky if (++PhysRegDefs[*AS] > 1) 336207618Srdivacky RuledOut = true; 337207618Srdivacky } 338207618Srdivacky 339207618Srdivacky // Only consider reloads for now and remats which do not have register 340207618Srdivacky // operands. FIXME: Consider unfold load folding instructions. 341207618Srdivacky if (Def && !RuledOut) { 342207618Srdivacky int FI = INT_MIN; 343207618Srdivacky if ((!HasNonInvariantUse && IsLICMCandidate(*MI)) || 344207618Srdivacky (TII->isLoadFromStackSlot(MI, FI) && MFI->isSpillSlotObjectIndex(FI))) 345207618Srdivacky Candidates.push_back(CandidateInfo(MI, Def, FI)); 346207618Srdivacky } 347207618Srdivacky} 348207618Srdivacky 349207618Srdivacky/// HoistRegionPostRA - Walk the specified region of the CFG and hoist loop 350207618Srdivacky/// invariants out to the preheader. 351207618Srdivackyvoid MachineLICM::HoistRegionPostRA() { 352207618Srdivacky unsigned NumRegs = TRI->getNumRegs(); 353207618Srdivacky unsigned *PhysRegDefs = new unsigned[NumRegs]; 354207618Srdivacky std::fill(PhysRegDefs, PhysRegDefs + NumRegs, 0); 355207618Srdivacky 356207618Srdivacky SmallVector<CandidateInfo, 32> Candidates; 357207618Srdivacky SmallSet<int, 32> StoredFIs; 358207618Srdivacky 359207618Srdivacky // Walk the entire region, count number of defs for each register, and 360207618Srdivacky // collect potential LICM candidates. 361207618Srdivacky const std::vector<MachineBasicBlock*> Blocks = CurLoop->getBlocks(); 362207618Srdivacky for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 363207618Srdivacky MachineBasicBlock *BB = Blocks[i]; 364207618Srdivacky // Conservatively treat live-in's as an external def. 365207618Srdivacky // FIXME: That means a reload that're reused in successor block(s) will not 366207618Srdivacky // be LICM'ed. 367207618Srdivacky for (MachineBasicBlock::livein_iterator I = BB->livein_begin(), 368207618Srdivacky E = BB->livein_end(); I != E; ++I) { 369207618Srdivacky unsigned Reg = *I; 370207618Srdivacky ++PhysRegDefs[Reg]; 371207618Srdivacky for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) 372207618Srdivacky ++PhysRegDefs[*AS]; 373207618Srdivacky } 374207618Srdivacky 375207618Srdivacky for (MachineBasicBlock::iterator 376207618Srdivacky MII = BB->begin(), E = BB->end(); MII != E; ++MII) { 377207618Srdivacky MachineInstr *MI = &*MII; 378207618Srdivacky ProcessMI(MI, PhysRegDefs, StoredFIs, Candidates); 379207618Srdivacky } 380207618Srdivacky } 381207618Srdivacky 382207618Srdivacky // Now evaluate whether the potential candidates qualify. 383207618Srdivacky // 1. Check if the candidate defined register is defined by another 384207618Srdivacky // instruction in the loop. 385207618Srdivacky // 2. If the candidate is a load from stack slot (always true for now), 386207618Srdivacky // check if the slot is stored anywhere in the loop. 387207618Srdivacky for (unsigned i = 0, e = Candidates.size(); i != e; ++i) { 388207618Srdivacky if (Candidates[i].FI != INT_MIN && 389207618Srdivacky StoredFIs.count(Candidates[i].FI)) 390207618Srdivacky continue; 391207618Srdivacky 392207618Srdivacky if (PhysRegDefs[Candidates[i].Def] == 1) { 393207618Srdivacky bool Safe = true; 394207618Srdivacky MachineInstr *MI = Candidates[i].MI; 395207618Srdivacky for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 396207618Srdivacky const MachineOperand &MO = MI->getOperand(j); 397207618Srdivacky if (!MO.isReg() || MO.isDef() || !MO.getReg()) 398207618Srdivacky continue; 399207618Srdivacky if (PhysRegDefs[MO.getReg()]) { 400207618Srdivacky // If it's using a non-loop-invariant register, then it's obviously 401207618Srdivacky // not safe to hoist. 402207618Srdivacky Safe = false; 403207618Srdivacky break; 404207618Srdivacky } 405207618Srdivacky } 406207618Srdivacky if (Safe) 407207618Srdivacky HoistPostRA(MI, Candidates[i].Def); 408207618Srdivacky } 409207618Srdivacky } 410207618Srdivacky 411207618Srdivacky delete[] PhysRegDefs; 412207618Srdivacky} 413207618Srdivacky 414207618Srdivacky/// AddToLiveIns - Add register 'Reg' to the livein sets of BBs in the current 415207618Srdivacky/// loop, and make sure it is not killed by any instructions in the loop. 416207618Srdivackyvoid MachineLICM::AddToLiveIns(unsigned Reg) { 417207618Srdivacky const std::vector<MachineBasicBlock*> Blocks = CurLoop->getBlocks(); 418207618Srdivacky for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { 419207618Srdivacky MachineBasicBlock *BB = Blocks[i]; 420207618Srdivacky if (!BB->isLiveIn(Reg)) 421207618Srdivacky BB->addLiveIn(Reg); 422207618Srdivacky for (MachineBasicBlock::iterator 423207618Srdivacky MII = BB->begin(), E = BB->end(); MII != E; ++MII) { 424207618Srdivacky MachineInstr *MI = &*MII; 425207618Srdivacky for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 426207618Srdivacky MachineOperand &MO = MI->getOperand(i); 427207618Srdivacky if (!MO.isReg() || !MO.getReg() || MO.isDef()) continue; 428207618Srdivacky if (MO.getReg() == Reg || TRI->isSuperRegister(Reg, MO.getReg())) 429207618Srdivacky MO.setIsKill(false); 430207618Srdivacky } 431207618Srdivacky } 432207618Srdivacky } 433207618Srdivacky} 434207618Srdivacky 435207618Srdivacky/// HoistPostRA - When an instruction is found to only use loop invariant 436207618Srdivacky/// operands that is safe to hoist, this instruction is called to do the 437207618Srdivacky/// dirty work. 438207618Srdivackyvoid MachineLICM::HoistPostRA(MachineInstr *MI, unsigned Def) { 439207618Srdivacky // Now move the instructions to the predecessor, inserting it before any 440207618Srdivacky // terminator instructions. 441207618Srdivacky DEBUG({ 442207618Srdivacky dbgs() << "Hoisting " << *MI; 443207618Srdivacky if (CurPreheader->getBasicBlock()) 444207618Srdivacky dbgs() << " to MachineBasicBlock " 445207618Srdivacky << CurPreheader->getName(); 446207618Srdivacky if (MI->getParent()->getBasicBlock()) 447207618Srdivacky dbgs() << " from MachineBasicBlock " 448207618Srdivacky << MI->getParent()->getName(); 449207618Srdivacky dbgs() << "\n"; 450207618Srdivacky }); 451207618Srdivacky 452207618Srdivacky // Splice the instruction to the preheader. 453207618Srdivacky MachineBasicBlock *MBB = MI->getParent(); 454207618Srdivacky CurPreheader->splice(CurPreheader->getFirstTerminator(), MBB, MI); 455207618Srdivacky 456207618Srdivacky // Add register to livein list to all the BBs in the current loop since a 457207618Srdivacky // loop invariant must be kept live throughout the whole loop. This is 458207618Srdivacky // important to ensure later passes do not scavenge the def register. 459207618Srdivacky AddToLiveIns(Def); 460207618Srdivacky 461207618Srdivacky ++NumPostRAHoisted; 462207618Srdivacky Changed = true; 463207618Srdivacky} 464207618Srdivacky 465193323Sed/// HoistRegion - Walk the specified region of the CFG (defined by all blocks 466193323Sed/// dominated by the specified block, and that are in the current loop) in depth 467193323Sed/// first order w.r.t the DominatorTree. This allows us to visit definitions 468193323Sed/// before uses, allowing us to hoist a loop body in one pass without iteration. 469193323Sed/// 470193323Sedvoid MachineLICM::HoistRegion(MachineDomTreeNode *N) { 471193323Sed assert(N != 0 && "Null dominator tree node?"); 472193323Sed MachineBasicBlock *BB = N->getBlock(); 473193323Sed 474193323Sed // If this subregion is not in the top level loop at all, exit. 475193323Sed if (!CurLoop->contains(BB)) return; 476193323Sed 477193323Sed for (MachineBasicBlock::iterator 478193323Sed MII = BB->begin(), E = BB->end(); MII != E; ) { 479193323Sed MachineBasicBlock::iterator NextMII = MII; ++NextMII; 480198892Srdivacky Hoist(&*MII); 481193323Sed MII = NextMII; 482193323Sed } 483193323Sed 484193323Sed const std::vector<MachineDomTreeNode*> &Children = N->getChildren(); 485193323Sed for (unsigned I = 0, E = Children.size(); I != E; ++I) 486193323Sed HoistRegion(Children[I]); 487193323Sed} 488193323Sed 489207618Srdivacky/// IsLICMCandidate - Returns true if the instruction may be a suitable 490207618Srdivacky/// candidate for LICM. e.g. If the instruction is a call, then it's obviously 491207618Srdivacky/// not safe to hoist it. 492207618Srdivackybool MachineLICM::IsLICMCandidate(MachineInstr &I) { 493207618Srdivacky if (I.isImplicitDef()) 494207618Srdivacky return false; 495207618Srdivacky 496193323Sed const TargetInstrDesc &TID = I.getDesc(); 497193323Sed 498193323Sed // Ignore stuff that we obviously can't hoist. 499193323Sed if (TID.mayStore() || TID.isCall() || TID.isTerminator() || 500193323Sed TID.hasUnmodeledSideEffects()) 501193323Sed return false; 502193323Sed 503193323Sed if (TID.mayLoad()) { 504193323Sed // Okay, this instruction does a load. As a refinement, we allow the target 505193323Sed // to decide whether the loaded value is actually a constant. If so, we can 506193323Sed // actually use it as a load. 507198090Srdivacky if (!I.isInvariantLoad(AA)) 508199481Srdivacky // FIXME: we should be able to hoist loads with no other side effects if 509199481Srdivacky // there are no other instructions which can change memory in this loop. 510199481Srdivacky // This is a trivial form of alias analysis. 511193323Sed return false; 512193323Sed } 513207618Srdivacky return true; 514207618Srdivacky} 515193323Sed 516207618Srdivacky/// IsLoopInvariantInst - Returns true if the instruction is loop 517207618Srdivacky/// invariant. I.e., all virtual register operands are defined outside of the 518207618Srdivacky/// loop, physical registers aren't accessed explicitly, and there are no side 519207618Srdivacky/// effects that aren't captured by the operands or other flags. 520207618Srdivacky/// 521207618Srdivackybool MachineLICM::IsLoopInvariantInst(MachineInstr &I) { 522207618Srdivacky if (!IsLICMCandidate(I)) 523207618Srdivacky return false; 524207618Srdivacky 525193323Sed // The instruction is loop invariant if all of its operands are. 526193323Sed for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 527193323Sed const MachineOperand &MO = I.getOperand(i); 528193323Sed 529193323Sed if (!MO.isReg()) 530193323Sed continue; 531193323Sed 532193323Sed unsigned Reg = MO.getReg(); 533193323Sed if (Reg == 0) continue; 534193323Sed 535193323Sed // Don't hoist an instruction that uses or defines a physical register. 536198090Srdivacky if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 537198090Srdivacky if (MO.isUse()) { 538198090Srdivacky // If the physreg has no defs anywhere, it's just an ambient register 539198090Srdivacky // and we can freely move its uses. Alternatively, if it's allocatable, 540198090Srdivacky // it could get allocated to something with a def during allocation. 541198090Srdivacky if (!RegInfo->def_empty(Reg)) 542198090Srdivacky return false; 543198090Srdivacky if (AllocatableSet.test(Reg)) 544198090Srdivacky return false; 545198090Srdivacky // Check for a def among the register's aliases too. 546198090Srdivacky for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 547198090Srdivacky unsigned AliasReg = *Alias; 548198090Srdivacky if (!RegInfo->def_empty(AliasReg)) 549198090Srdivacky return false; 550198090Srdivacky if (AllocatableSet.test(AliasReg)) 551198090Srdivacky return false; 552198090Srdivacky } 553198090Srdivacky // Otherwise it's safe to move. 554198090Srdivacky continue; 555198090Srdivacky } else if (!MO.isDead()) { 556198090Srdivacky // A def that isn't dead. We can't move it. 557198090Srdivacky return false; 558204642Srdivacky } else if (CurLoop->getHeader()->isLiveIn(Reg)) { 559204642Srdivacky // If the reg is live into the loop, we can't hoist an instruction 560204642Srdivacky // which would clobber it. 561204642Srdivacky return false; 562198090Srdivacky } 563198090Srdivacky } 564193323Sed 565193323Sed if (!MO.isUse()) 566193323Sed continue; 567193323Sed 568193323Sed assert(RegInfo->getVRegDef(Reg) && 569193323Sed "Machine instr not mapped for this vreg?!"); 570193323Sed 571193323Sed // If the loop contains the definition of an operand, then the instruction 572193323Sed // isn't loop invariant. 573201360Srdivacky if (CurLoop->contains(RegInfo->getVRegDef(Reg))) 574193323Sed return false; 575193323Sed } 576193323Sed 577193323Sed // If we got this far, the instruction is loop invariant! 578193323Sed return true; 579193323Sed} 580193323Sed 581193323Sed 582193323Sed/// HasPHIUses - Return true if the specified register has any PHI use. 583193323Sedstatic bool HasPHIUses(unsigned Reg, MachineRegisterInfo *RegInfo) { 584193323Sed for (MachineRegisterInfo::use_iterator UI = RegInfo->use_begin(Reg), 585193323Sed UE = RegInfo->use_end(); UI != UE; ++UI) { 586193323Sed MachineInstr *UseMI = &*UI; 587203954Srdivacky if (UseMI->isPHI()) 588193323Sed return true; 589193323Sed } 590193323Sed return false; 591193323Sed} 592193323Sed 593199989Srdivacky/// isLoadFromConstantMemory - Return true if the given instruction is a 594199989Srdivacky/// load from constant memory. Machine LICM will hoist these even if they are 595199989Srdivacky/// not re-materializable. 596199989Srdivackybool MachineLICM::isLoadFromConstantMemory(MachineInstr *MI) { 597199989Srdivacky if (!MI->getDesc().mayLoad()) return false; 598199989Srdivacky if (!MI->hasOneMemOperand()) return false; 599199989Srdivacky MachineMemOperand *MMO = *MI->memoperands_begin(); 600199989Srdivacky if (MMO->isVolatile()) return false; 601199989Srdivacky if (!MMO->getValue()) return false; 602199989Srdivacky const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(MMO->getValue()); 603199989Srdivacky if (PSV) { 604199989Srdivacky MachineFunction &MF = *MI->getParent()->getParent(); 605199989Srdivacky return PSV->isConstant(MF.getFrameInfo()); 606199989Srdivacky } else { 607199989Srdivacky return AA->pointsToConstantMemory(MMO->getValue()); 608199989Srdivacky } 609199989Srdivacky} 610199989Srdivacky 611193323Sed/// IsProfitableToHoist - Return true if it is potentially profitable to hoist 612193323Sed/// the given loop invariant. 613193323Sedbool MachineLICM::IsProfitableToHoist(MachineInstr &MI) { 614193323Sed // FIXME: For now, only hoist re-materilizable instructions. LICM will 615193323Sed // increase register pressure. We want to make sure it doesn't increase 616193323Sed // spilling. 617199989Srdivacky // Also hoist loads from constant memory, e.g. load from stubs, GOT. Hoisting 618199989Srdivacky // these tend to help performance in low register pressure situation. The 619199989Srdivacky // trade off is it may cause spill in high pressure situation. It will end up 620199989Srdivacky // adding a store in the loop preheader. But the reload is no more expensive. 621199989Srdivacky // The side benefit is these loads are frequently CSE'ed. 622199989Srdivacky if (!TII->isTriviallyReMaterializable(&MI, AA)) { 623199989Srdivacky if (!isLoadFromConstantMemory(&MI)) 624199989Srdivacky return false; 625199989Srdivacky } 626193323Sed 627193323Sed // If result(s) of this instruction is used by PHIs, then don't hoist it. 628193323Sed // The presence of joins makes it difficult for current register allocator 629193323Sed // implementation to perform remat. 630193323Sed for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 631193323Sed const MachineOperand &MO = MI.getOperand(i); 632193323Sed if (!MO.isReg() || !MO.isDef()) 633193323Sed continue; 634193323Sed if (HasPHIUses(MO.getReg(), RegInfo)) 635193323Sed return false; 636193323Sed } 637193323Sed 638193323Sed return true; 639193323Sed} 640193323Sed 641198892SrdivackyMachineInstr *MachineLICM::ExtractHoistableLoad(MachineInstr *MI) { 642198892Srdivacky // If not, we may be able to unfold a load and hoist that. 643198892Srdivacky // First test whether the instruction is loading from an amenable 644198892Srdivacky // memory location. 645199989Srdivacky if (!isLoadFromConstantMemory(MI)) 646199989Srdivacky return 0; 647199989Srdivacky 648198892Srdivacky // Next determine the register class for a temporary register. 649198892Srdivacky unsigned LoadRegIndex; 650198892Srdivacky unsigned NewOpc = 651198892Srdivacky TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(), 652198892Srdivacky /*UnfoldLoad=*/true, 653198892Srdivacky /*UnfoldStore=*/false, 654198892Srdivacky &LoadRegIndex); 655198892Srdivacky if (NewOpc == 0) return 0; 656198892Srdivacky const TargetInstrDesc &TID = TII->get(NewOpc); 657198892Srdivacky if (TID.getNumDefs() != 1) return 0; 658198892Srdivacky const TargetRegisterClass *RC = TID.OpInfo[LoadRegIndex].getRegClass(TRI); 659198892Srdivacky // Ok, we're unfolding. Create a temporary register and do the unfold. 660198892Srdivacky unsigned Reg = RegInfo->createVirtualRegister(RC); 661199989Srdivacky 662199989Srdivacky MachineFunction &MF = *MI->getParent()->getParent(); 663198892Srdivacky SmallVector<MachineInstr *, 2> NewMIs; 664198892Srdivacky bool Success = 665198892Srdivacky TII->unfoldMemoryOperand(MF, MI, Reg, 666198892Srdivacky /*UnfoldLoad=*/true, /*UnfoldStore=*/false, 667198892Srdivacky NewMIs); 668198892Srdivacky (void)Success; 669198892Srdivacky assert(Success && 670198892Srdivacky "unfoldMemoryOperand failed when getOpcodeAfterMemoryUnfold " 671198892Srdivacky "succeeded!"); 672198892Srdivacky assert(NewMIs.size() == 2 && 673198892Srdivacky "Unfolded a load into multiple instructions!"); 674198892Srdivacky MachineBasicBlock *MBB = MI->getParent(); 675198892Srdivacky MBB->insert(MI, NewMIs[0]); 676198892Srdivacky MBB->insert(MI, NewMIs[1]); 677198892Srdivacky // If unfolding produced a load that wasn't loop-invariant or profitable to 678198892Srdivacky // hoist, discard the new instructions and bail. 679198892Srdivacky if (!IsLoopInvariantInst(*NewMIs[0]) || !IsProfitableToHoist(*NewMIs[0])) { 680198892Srdivacky NewMIs[0]->eraseFromParent(); 681198892Srdivacky NewMIs[1]->eraseFromParent(); 682198892Srdivacky return 0; 683198892Srdivacky } 684198892Srdivacky // Otherwise we successfully unfolded a load that we can hoist. 685198892Srdivacky MI->eraseFromParent(); 686198892Srdivacky return NewMIs[0]; 687198892Srdivacky} 688198892Srdivacky 689198892Srdivackyvoid MachineLICM::InitCSEMap(MachineBasicBlock *BB) { 690198892Srdivacky for (MachineBasicBlock::iterator I = BB->begin(),E = BB->end(); I != E; ++I) { 691198892Srdivacky const MachineInstr *MI = &*I; 692198892Srdivacky // FIXME: For now, only hoist re-materilizable instructions. LICM will 693198892Srdivacky // increase register pressure. We want to make sure it doesn't increase 694198892Srdivacky // spilling. 695198892Srdivacky if (TII->isTriviallyReMaterializable(MI, AA)) { 696198892Srdivacky unsigned Opcode = MI->getOpcode(); 697198892Srdivacky DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator 698198892Srdivacky CI = CSEMap.find(Opcode); 699198892Srdivacky if (CI != CSEMap.end()) 700198892Srdivacky CI->second.push_back(MI); 701198892Srdivacky else { 702198892Srdivacky std::vector<const MachineInstr*> CSEMIs; 703198892Srdivacky CSEMIs.push_back(MI); 704198892Srdivacky CSEMap.insert(std::make_pair(Opcode, CSEMIs)); 705198892Srdivacky } 706198892Srdivacky } 707198892Srdivacky } 708198892Srdivacky} 709198892Srdivacky 710199481Srdivackyconst MachineInstr* 711199481SrdivackyMachineLICM::LookForDuplicate(const MachineInstr *MI, 712199481Srdivacky std::vector<const MachineInstr*> &PrevMIs) { 713198953Srdivacky for (unsigned i = 0, e = PrevMIs.size(); i != e; ++i) { 714198953Srdivacky const MachineInstr *PrevMI = PrevMIs[i]; 715204642Srdivacky if (TII->produceSameValue(MI, PrevMI)) 716198953Srdivacky return PrevMI; 717198953Srdivacky } 718198953Srdivacky return 0; 719198953Srdivacky} 720198953Srdivacky 721198953Srdivackybool MachineLICM::EliminateCSE(MachineInstr *MI, 722198953Srdivacky DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator &CI) { 723199481Srdivacky if (CI == CSEMap.end()) 724199481Srdivacky return false; 725199481Srdivacky 726199481Srdivacky if (const MachineInstr *Dup = LookForDuplicate(MI, CI->second)) { 727202375Srdivacky DEBUG(dbgs() << "CSEing " << *MI << " with " << *Dup); 728204642Srdivacky 729204642Srdivacky // Replace virtual registers defined by MI by their counterparts defined 730204642Srdivacky // by Dup. 731199481Srdivacky for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 732199481Srdivacky const MachineOperand &MO = MI->getOperand(i); 733204642Srdivacky 734204642Srdivacky // Physical registers may not differ here. 735204642Srdivacky assert((!MO.isReg() || MO.getReg() == 0 || 736204642Srdivacky !TargetRegisterInfo::isPhysicalRegister(MO.getReg()) || 737204642Srdivacky MO.getReg() == Dup->getOperand(i).getReg()) && 738204642Srdivacky "Instructions with different phys regs are not identical!"); 739204642Srdivacky 740204642Srdivacky if (MO.isReg() && MO.isDef() && 741204642Srdivacky !TargetRegisterInfo::isPhysicalRegister(MO.getReg())) 742199481Srdivacky RegInfo->replaceRegWith(MO.getReg(), Dup->getOperand(i).getReg()); 743198953Srdivacky } 744199481Srdivacky MI->eraseFromParent(); 745199481Srdivacky ++NumCSEed; 746199481Srdivacky return true; 747198953Srdivacky } 748198953Srdivacky return false; 749198953Srdivacky} 750198953Srdivacky 751193323Sed/// Hoist - When an instruction is found to use only loop invariant operands 752193323Sed/// that are safe to hoist, this instruction is called to do the dirty work. 753193323Sed/// 754198892Srdivackyvoid MachineLICM::Hoist(MachineInstr *MI) { 755198892Srdivacky // First check whether we should hoist this instruction. 756198892Srdivacky if (!IsLoopInvariantInst(*MI) || !IsProfitableToHoist(*MI)) { 757198892Srdivacky // If not, try unfolding a hoistable load. 758198892Srdivacky MI = ExtractHoistableLoad(MI); 759198892Srdivacky if (!MI) return; 760198892Srdivacky } 761193323Sed 762193323Sed // Now move the instructions to the predecessor, inserting it before any 763193323Sed // terminator instructions. 764193323Sed DEBUG({ 765202375Srdivacky dbgs() << "Hoisting " << *MI; 766193323Sed if (CurPreheader->getBasicBlock()) 767202375Srdivacky dbgs() << " to MachineBasicBlock " 768199989Srdivacky << CurPreheader->getName(); 769198892Srdivacky if (MI->getParent()->getBasicBlock()) 770202375Srdivacky dbgs() << " from MachineBasicBlock " 771199989Srdivacky << MI->getParent()->getName(); 772202375Srdivacky dbgs() << "\n"; 773193323Sed }); 774193323Sed 775198892Srdivacky // If this is the first instruction being hoisted to the preheader, 776198892Srdivacky // initialize the CSE map with potential common expressions. 777198892Srdivacky InitCSEMap(CurPreheader); 778198892Srdivacky 779193323Sed // Look for opportunity to CSE the hoisted instruction. 780198892Srdivacky unsigned Opcode = MI->getOpcode(); 781198892Srdivacky DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator 782198892Srdivacky CI = CSEMap.find(Opcode); 783198953Srdivacky if (!EliminateCSE(MI, CI)) { 784198953Srdivacky // Otherwise, splice the instruction to the preheader. 785198892Srdivacky CurPreheader->splice(CurPreheader->getFirstTerminator(),MI->getParent(),MI); 786198892Srdivacky 787193323Sed // Add to the CSE map. 788193323Sed if (CI != CSEMap.end()) 789198892Srdivacky CI->second.push_back(MI); 790193323Sed else { 791193323Sed std::vector<const MachineInstr*> CSEMIs; 792198892Srdivacky CSEMIs.push_back(MI); 793198892Srdivacky CSEMap.insert(std::make_pair(Opcode, CSEMIs)); 794193323Sed } 795193323Sed } 796193323Sed 797193323Sed ++NumHoisted; 798193323Sed Changed = true; 799193323Sed} 800