MachineLICM.cpp revision 9b61f33351a92f6a87065adae713c02497780887
10f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling//===-- MachineLICM.cpp - Machine Loop Invariant Code Motion Pass ---------===// 20f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling// 30f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling// The LLVM Compiler Infrastructure 40f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 70f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling// 80f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling//===----------------------------------------------------------------------===// 90f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling// 100f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling// This pass performs loop invariant code motion on machine instructions. We 110f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling// attempt to remove as much code from the body of a loop as possible. 120f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling// 13c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman// This pass does not attempt to throttle itself to limit register pressure. 14c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman// The register allocation phases are expected to perform rematerialization 15c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman// to recover when register pressure is high. 16c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman// 17c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman// This pass is not intended to be a replacement or a complete alternative 18c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman// for the LLVM-IR-level LICM pass. It is only designed to hoist simple 19c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman// constructs that are not exposed before lowering and instruction selection. 20c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman// 210f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling//===----------------------------------------------------------------------===// 220f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 230f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling#define DEBUG_TYPE "machine-licm" 24ac69582664714c2656a28ed6cb70627bb85ee673Chris Lattner#include "llvm/CodeGen/Passes.h" 250f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling#include "llvm/CodeGen/MachineDominators.h" 260f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling#include "llvm/CodeGen/MachineLoopInfo.h" 279258cd3994e54aaec66f69a321032e071391dc90Bill Wendling#include "llvm/CodeGen/MachineRegisterInfo.h" 286f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 29efe2be797699d77dc3387969aa566c26d5c36d9dBill Wendling#include "llvm/Target/TargetInstrInfo.h" 300f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling#include "llvm/Target/TargetMachine.h" 31ac69582664714c2656a28ed6cb70627bb85ee673Chris Lattner#include "llvm/ADT/Statistic.h" 32ac69582664714c2656a28ed6cb70627bb85ee673Chris Lattner#include "llvm/Support/CommandLine.h" 33ac69582664714c2656a28ed6cb70627bb85ee673Chris Lattner#include "llvm/Support/Compiler.h" 34ac69582664714c2656a28ed6cb70627bb85ee673Chris Lattner#include "llvm/Support/Debug.h" 350f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 360f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendlingusing namespace llvm; 370f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 38041b3f835682588cb63df7e609d726369dd6b7d3Bill WendlingSTATISTIC(NumHoisted, "Number of machine instructions hoisted out of loops"); 39b48519cbadbb2b91a811f6fc189f40bd67c007f4Bill Wendling 400f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendlingnamespace { 410f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling class VISIBILITY_HIDDEN MachineLICM : public MachineFunctionPass { 429258cd3994e54aaec66f69a321032e071391dc90Bill Wendling const TargetMachine *TM; 43efe2be797699d77dc3387969aa566c26d5c36d9dBill Wendling const TargetInstrInfo *TII; 4412ebf14048f4a6489033f8468ba36424442140acBill Wendling 450f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // Various analyses that we use... 46e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling MachineLoopInfo *LI; // Current MachineLoopInfo 47e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling MachineDominatorTree *DT; // Machine dominator tree for the cur loop 489258cd3994e54aaec66f69a321032e071391dc90Bill Wendling MachineRegisterInfo *RegInfo; // Machine register information 490f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 500f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // State that is updated as we process loops 51e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling bool Changed; // True if a loop is changed. 52e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling MachineLoop *CurLoop; // The current loop we are working on. 53c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman MachineBasicBlock *CurPreheader; // The preheader for CurLoop. 540f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling public: 550f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling static char ID; // Pass identification, replacement for typeid 56ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman MachineLICM() : MachineFunctionPass(&ID) {} 570f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 580f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling virtual bool runOnMachineFunction(MachineFunction &MF); 590f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 607224170f6a5b8a3c76f4adc5f84d650d142a27c4Dan Gohman const char *getPassName() const { return "Machine Instruction LICM"; } 617224170f6a5b8a3c76f4adc5f84d650d142a27c4Dan Gohman 62074223a124e945ee67cacedb99e777265a0c6cb6Bill Wendling // FIXME: Loop preheaders? 630f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling virtual void getAnalysisUsage(AnalysisUsage &AU) const { 640f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling AU.setPreservesCFG(); 650f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling AU.addRequired<MachineLoopInfo>(); 660f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling AU.addRequired<MachineDominatorTree>(); 67d5da7048c297deb6137ad10cac217c5d9d702065Bill Wendling AU.addPreserved<MachineLoopInfo>(); 68d5da7048c297deb6137ad10cac217c5d9d702065Bill Wendling AU.addPreserved<MachineDominatorTree>(); 69d5da7048c297deb6137ad10cac217c5d9d702065Bill Wendling MachineFunctionPass::getAnalysisUsage(AU); 700f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling } 710f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling private: 72041b3f835682588cb63df7e609d726369dd6b7d3Bill Wendling /// IsLoopInvariantInst - Returns true if the instruction is loop 730f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// invariant. I.e., all virtual register operands are defined outside of 740f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// the loop, physical registers aren't accessed (explicitly or implicitly), 750f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// and the instruction is hoistable. 760f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// 77041b3f835682588cb63df7e609d726369dd6b7d3Bill Wendling bool IsLoopInvariantInst(MachineInstr &I); 780f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 790f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// HoistRegion - Walk the specified region of the CFG (defined by all 800f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// blocks dominated by the specified block, and that are in the current 810f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// loop) in depth first order w.r.t the DominatorTree. This allows us to 820f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// visit definitions before uses, allowing us to hoist a loop body in one 830f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// pass without iteration. 840f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// 850f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling void HoistRegion(MachineDomTreeNode *N); 860f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 870f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// Hoist - When an instruction is found to only use loop invariant operands 880f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// that is safe to hoist, this instruction is called to do the dirty work. 890f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// 90b48519cbadbb2b91a811f6fc189f40bd67c007f4Bill Wendling void Hoist(MachineInstr &MI); 910f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling }; 920f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling} // end anonymous namespace 930f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 94844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar MachineLICM::ID = 0; 95844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<MachineLICM> 968870ce951d3f545edc8a5ce89ce3e7cdbf38eb25Bill WendlingX("machinelicm", "Machine Loop Invariant Code Motion"); 97844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 980f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill WendlingFunctionPass *llvm::createMachineLICMPass() { return new MachineLICM(); } 990f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 100c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman/// LoopIsOuterMostWithPreheader - Test if the given loop is the outer-most 101c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman/// loop that has a preheader. 102c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohmanstatic bool LoopIsOuterMostWithPreheader(MachineLoop *CurLoop) { 103c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop()) 104c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman if (L->getLoopPreheader()) 105c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman return false; 106c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman return true; 107c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman} 108c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman 1090f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// Hoist expressions out of the specified loop. Note, alias info for inner loop 1100f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// is not preserved so it is not a good idea to run LICM multiple times on one 1110f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// loop. 1120f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// 1130f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendlingbool MachineLICM::runOnMachineFunction(MachineFunction &MF) { 114a17ad59e13f5caafe33738bafc75af00ca354c9fBill Wendling DOUT << "******** Machine LICM ********\n"; 115a17ad59e13f5caafe33738bafc75af00ca354c9fBill Wendling 1160f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling Changed = false; 117acb04ec4273516242fe87cb0a57a43136805deddBill Wendling TM = &MF.getTarget(); 1189258cd3994e54aaec66f69a321032e071391dc90Bill Wendling TII = TM->getInstrInfo(); 119acb04ec4273516242fe87cb0a57a43136805deddBill Wendling RegInfo = &MF.getRegInfo(); 1200f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1210f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // Get our Loop information... 1220f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling LI = &getAnalysis<MachineLoopInfo>(); 1230f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling DT = &getAnalysis<MachineDominatorTree>(); 1240f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1250f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling for (MachineLoopInfo::iterator 1260f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling I = LI->begin(), E = LI->end(); I != E; ++I) { 127a17ad59e13f5caafe33738bafc75af00ca354c9fBill Wendling CurLoop = *I; 1280f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 129c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // Only visit outer-most preheader-sporting loops. 130c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman if (!LoopIsOuterMostWithPreheader(CurLoop)) 131c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman continue; 132c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman 133c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // Determine the block to which to hoist instructions. If we can't find a 134c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // suitable loop preheader, we can't do any hoisting. 135c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // 136c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // FIXME: We are only hoisting if the basic block coming into this loop 137c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // has only one successor. This isn't the case in general because we haven't 138c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // broken critical edges or added preheaders. 139c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman CurPreheader = CurLoop->getLoopPreheader(); 140c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman if (!CurPreheader) 141c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman continue; 142c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman 143c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman HoistRegion(DT->getNode(CurLoop->getHeader())); 1440f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling } 1450f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1460f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling return Changed; 1470f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling} 1480f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1490f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// HoistRegion - Walk the specified region of the CFG (defined by all blocks 1500f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// dominated by the specified block, and that are in the current loop) in depth 1510f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// first order w.r.t the DominatorTree. This allows us to visit definitions 1520f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// before uses, allowing us to hoist a loop body in one pass without iteration. 1530f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// 1540f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendlingvoid MachineLICM::HoistRegion(MachineDomTreeNode *N) { 1550f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling assert(N != 0 && "Null dominator tree node?"); 1560f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling MachineBasicBlock *BB = N->getBlock(); 1570f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1580f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // If this subregion is not in the top level loop at all, exit. 1590f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling if (!CurLoop->contains(BB)) return; 1600f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 161c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman for (MachineBasicBlock::iterator 162c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman I = BB->begin(), E = BB->end(); I != E; ) { 163c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman MachineInstr &MI = *I++; 164c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman 165c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // Try hoisting the instruction out of the loop. We can only do this if 166c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // all of the operands of the instruction are loop invariant and if it is 167c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // safe to hoist the instruction. 168c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman Hoist(MI); 169c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman } 1700f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1710f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling const std::vector<MachineDomTreeNode*> &Children = N->getChildren(); 1720f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1730f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling for (unsigned I = 0, E = Children.size(); I != E; ++I) 1740f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling HoistRegion(Children[I]); 1750f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling} 1760f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 177041b3f835682588cb63df7e609d726369dd6b7d3Bill Wendling/// IsLoopInvariantInst - Returns true if the instruction is loop 1780f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// invariant. I.e., all virtual register operands are defined outside of the 17960ff1a300523d931bc297905a7238219e789028dBill Wendling/// loop, physical registers aren't accessed explicitly, and there are no side 18060ff1a300523d931bc297905a7238219e789028dBill Wendling/// effects that aren't captured by the operands or other flags. 1810f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// 182041b3f835682588cb63df7e609d726369dd6b7d3Bill Wendlingbool MachineLICM::IsLoopInvariantInst(MachineInstr &I) { 183a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner const TargetInstrDesc &TID = I.getDesc(); 184a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner 185a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner // Ignore stuff that we obviously can't hoist. 186237dee125997dcaf16e391878465162cc680c0faDan Gohman if (TID.mayStore() || TID.isCall() || TID.isTerminator() || 187a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner TID.hasUnmodeledSideEffects()) 188a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner return false; 1899b61f33351a92f6a87065adae713c02497780887Evan Cheng 1909b61f33351a92f6a87065adae713c02497780887Evan Cheng bool isInvLoad = false; 191a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner if (TID.mayLoad()) { 192e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling // Okay, this instruction does a load. As a refinement, we allow the target 193e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling // to decide whether the loaded value is actually a constant. If so, we can 194e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling // actually use it as a load. 1959b61f33351a92f6a87065adae713c02497780887Evan Cheng isInvLoad = TII->isInvariantLoad(&I); 1969b61f33351a92f6a87065adae713c02497780887Evan Cheng if (!isInvLoad) 197a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner // FIXME: we should be able to sink loads with no other side effects if 198a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner // there is nothing that can change memory from here until the end of 199e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling // block. This is a trivial form of alias analysis. 200a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner return false; 201a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner } 202074223a124e945ee67cacedb99e777265a0c6cb6Bill Wendling 2039b61f33351a92f6a87065adae713c02497780887Evan Cheng // FIXME: For now, only hoist re-materilizable instructions. LICM will 2049b61f33351a92f6a87065adae713c02497780887Evan Cheng // increase register pressure. We want to make sure it doesn't increase 2059b61f33351a92f6a87065adae713c02497780887Evan Cheng // spilling. 2069b61f33351a92f6a87065adae713c02497780887Evan Cheng if (!isInvLoad && (!TID.isRematerializable() || 2079b61f33351a92f6a87065adae713c02497780887Evan Cheng !TII->isTriviallyReMaterializable(&I))) 2089b61f33351a92f6a87065adae713c02497780887Evan Cheng return false; 2099b61f33351a92f6a87065adae713c02497780887Evan Cheng 210280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling DEBUG({ 211280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling DOUT << "--- Checking if we can hoist " << I; 212749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner if (I.getDesc().getImplicitUses()) { 213280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling DOUT << " * Instruction has implicit uses:\n"; 214280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling 2156f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman const TargetRegisterInfo *TRI = TM->getRegisterInfo(); 216749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner for (const unsigned *ImpUses = I.getDesc().getImplicitUses(); 21769244300b8a0112efb44b6273ecea4ca6264b8cfChris Lattner *ImpUses; ++ImpUses) 218e6d088acc90e422451e098555d383d4d65b6ce6bBill Wendling DOUT << " -> " << TRI->getName(*ImpUses) << "\n"; 219280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling } 220280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling 221749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner if (I.getDesc().getImplicitDefs()) { 222280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling DOUT << " * Instruction has implicit defines:\n"; 223280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling 2246f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman const TargetRegisterInfo *TRI = TM->getRegisterInfo(); 225749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner for (const unsigned *ImpDefs = I.getDesc().getImplicitDefs(); 22669244300b8a0112efb44b6273ecea4ca6264b8cfChris Lattner *ImpDefs; ++ImpDefs) 227e6d088acc90e422451e098555d383d4d65b6ce6bBill Wendling DOUT << " -> " << TRI->getName(*ImpDefs) << "\n"; 228280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling } 229280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling }); 230280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling 231d3361e996b272084d8ebe5bae8a0d420206c8e37Bill Wendling if (I.getDesc().getImplicitDefs() || I.getDesc().getImplicitUses()) { 232d3361e996b272084d8ebe5bae8a0d420206c8e37Bill Wendling DOUT << "Cannot hoist with implicit defines or uses\n"; 233d3361e996b272084d8ebe5bae8a0d420206c8e37Bill Wendling return false; 234d3361e996b272084d8ebe5bae8a0d420206c8e37Bill Wendling } 235d3361e996b272084d8ebe5bae8a0d420206c8e37Bill Wendling 236e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling // The instruction is loop invariant if all of its operands are. 2370f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 2380f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling const MachineOperand &MO = I.getOperand(i); 2390f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 240d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg()) 241fb018d0433f7b52c3f1235e675276adb1f92d597Bill Wendling continue; 242fb018d0433f7b52c3f1235e675276adb1f92d597Bill Wendling 2430f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling unsigned Reg = MO.getReg(); 244074223a124e945ee67cacedb99e777265a0c6cb6Bill Wendling if (Reg == 0) continue; 2450f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 246c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // Don't hoist an instruction that uses or defines a physical register. 247074223a124e945ee67cacedb99e777265a0c6cb6Bill Wendling if (TargetRegisterInfo::isPhysicalRegister(Reg)) 2480f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling return false; 2490f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 250c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman if (!MO.isUse()) 251c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman continue; 252c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman 253e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling assert(RegInfo->getVRegDef(Reg) && 254e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling "Machine instr not mapped for this vreg?!"); 2550f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 2560f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // If the loop contains the definition of an operand, then the instruction 2570f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // isn't loop invariant. 2589258cd3994e54aaec66f69a321032e071391dc90Bill Wendling if (CurLoop->contains(RegInfo->getVRegDef(Reg)->getParent())) 2590f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling return false; 2600f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling } 2610f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 2620f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // If we got this far, the instruction is loop invariant! 2630f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling return true; 2640f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling} 2650f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 266e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling/// Hoist - When an instruction is found to use only loop invariant operands 267e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling/// that are safe to hoist, this instruction is called to do the dirty work. 2680f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// 269b48519cbadbb2b91a811f6fc189f40bd67c007f4Bill Wendlingvoid MachineLICM::Hoist(MachineInstr &MI) { 270041b3f835682588cb63df7e609d726369dd6b7d3Bill Wendling if (!IsLoopInvariantInst(MI)) return; 2710f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 272c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // Now move the instructions to the predecessor, inserting it before any 273c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // terminator instructions. 274c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman DEBUG({ 275c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman DOUT << "Hoisting " << MI; 276c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman if (CurPreheader->getBasicBlock()) 277c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman DOUT << " to MachineBasicBlock " 278c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman << CurPreheader->getBasicBlock()->getName(); 279c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman if (MI.getParent()->getBasicBlock()) 280c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman DOUT << " from MachineBasicBlock " 281c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman << MI.getParent()->getBasicBlock()->getName(); 282c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman DOUT << "\n"; 283c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman }); 284b48519cbadbb2b91a811f6fc189f40bd67c007f4Bill Wendling 285c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman CurPreheader->splice(CurPreheader->getFirstTerminator(), MI.getParent(), &MI); 286b48519cbadbb2b91a811f6fc189f40bd67c007f4Bill Wendling 287c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman ++NumHoisted; 2880f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling Changed = true; 2890f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling} 290