MachineLICM.cpp revision 5caa883afc2c768c293757d4ca30d85b9094e876
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 7945e94d68d7c99235cf4decc72812445b214df40eEvan Cheng /// IsProfitableToHoist - Return true if it is potentially profitable to 8045e94d68d7c99235cf4decc72812445b214df40eEvan Cheng /// hoist the given loop invariant. 8145e94d68d7c99235cf4decc72812445b214df40eEvan Cheng bool IsProfitableToHoist(MachineInstr &MI); 8245e94d68d7c99235cf4decc72812445b214df40eEvan Cheng 830f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// HoistRegion - Walk the specified region of the CFG (defined by all 840f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// blocks dominated by the specified block, and that are in the current 850f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// loop) in depth first order w.r.t the DominatorTree. This allows us to 860f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// visit definitions before uses, allowing us to hoist a loop body in one 870f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// pass without iteration. 880f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// 890f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling void HoistRegion(MachineDomTreeNode *N); 900f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 910f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// Hoist - When an instruction is found to only use loop invariant operands 920f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// that is safe to hoist, this instruction is called to do the dirty work. 930f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// 94b48519cbadbb2b91a811f6fc189f40bd67c007f4Bill Wendling void Hoist(MachineInstr &MI); 950f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling }; 960f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling} // end anonymous namespace 970f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 98844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar MachineLICM::ID = 0; 99844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<MachineLICM> 1008870ce951d3f545edc8a5ce89ce3e7cdbf38eb25Bill WendlingX("machinelicm", "Machine Loop Invariant Code Motion"); 101844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 1020f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill WendlingFunctionPass *llvm::createMachineLICMPass() { return new MachineLICM(); } 1030f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 104c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman/// LoopIsOuterMostWithPreheader - Test if the given loop is the outer-most 105c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman/// loop that has a preheader. 106c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohmanstatic bool LoopIsOuterMostWithPreheader(MachineLoop *CurLoop) { 107c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop()) 108c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman if (L->getLoopPreheader()) 109c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman return false; 110c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman return true; 111c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman} 112c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman 1130f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// Hoist expressions out of the specified loop. Note, alias info for inner loop 1140f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// is not preserved so it is not a good idea to run LICM multiple times on one 1150f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// loop. 1160f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// 1170f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendlingbool MachineLICM::runOnMachineFunction(MachineFunction &MF) { 118a17ad59e13f5caafe33738bafc75af00ca354c9fBill Wendling DOUT << "******** Machine LICM ********\n"; 119a17ad59e13f5caafe33738bafc75af00ca354c9fBill Wendling 1200f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling Changed = false; 121acb04ec4273516242fe87cb0a57a43136805deddBill Wendling TM = &MF.getTarget(); 1229258cd3994e54aaec66f69a321032e071391dc90Bill Wendling TII = TM->getInstrInfo(); 123acb04ec4273516242fe87cb0a57a43136805deddBill Wendling RegInfo = &MF.getRegInfo(); 1240f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1250f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // Get our Loop information... 1260f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling LI = &getAnalysis<MachineLoopInfo>(); 1270f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling DT = &getAnalysis<MachineDominatorTree>(); 1280f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1290f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling for (MachineLoopInfo::iterator 1300f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling I = LI->begin(), E = LI->end(); I != E; ++I) { 131a17ad59e13f5caafe33738bafc75af00ca354c9fBill Wendling CurLoop = *I; 1320f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 133c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // Only visit outer-most preheader-sporting loops. 134c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman if (!LoopIsOuterMostWithPreheader(CurLoop)) 135c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman continue; 136c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman 137c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // Determine the block to which to hoist instructions. If we can't find a 138c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // suitable loop preheader, we can't do any hoisting. 139c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // 140c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // FIXME: We are only hoisting if the basic block coming into this loop 141c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // has only one successor. This isn't the case in general because we haven't 142c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // broken critical edges or added preheaders. 143c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman CurPreheader = CurLoop->getLoopPreheader(); 144c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman if (!CurPreheader) 145c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman continue; 146c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman 147c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman HoistRegion(DT->getNode(CurLoop->getHeader())); 1480f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling } 1490f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1500f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling return Changed; 1510f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling} 1520f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1530f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// HoistRegion - Walk the specified region of the CFG (defined by all blocks 1540f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// dominated by the specified block, and that are in the current loop) in depth 1550f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// first order w.r.t the DominatorTree. This allows us to visit definitions 1560f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// before uses, allowing us to hoist a loop body in one pass without iteration. 1570f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// 1580f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendlingvoid MachineLICM::HoistRegion(MachineDomTreeNode *N) { 1590f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling assert(N != 0 && "Null dominator tree node?"); 1600f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling MachineBasicBlock *BB = N->getBlock(); 1610f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1620f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // If this subregion is not in the top level loop at all, exit. 1630f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling if (!CurLoop->contains(BB)) return; 1640f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 165c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman for (MachineBasicBlock::iterator 166c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman I = BB->begin(), E = BB->end(); I != E; ) { 167c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman MachineInstr &MI = *I++; 168c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman 169c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // Try hoisting the instruction out of the loop. We can only do this if 170c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // all of the operands of the instruction are loop invariant and if it is 171c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // safe to hoist the instruction. 172c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman Hoist(MI); 173c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman } 1740f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1750f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling const std::vector<MachineDomTreeNode*> &Children = N->getChildren(); 1760f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1770f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling for (unsigned I = 0, E = Children.size(); I != E; ++I) 1780f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling HoistRegion(Children[I]); 1790f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling} 1800f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 181041b3f835682588cb63df7e609d726369dd6b7d3Bill Wendling/// IsLoopInvariantInst - Returns true if the instruction is loop 1820f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// invariant. I.e., all virtual register operands are defined outside of the 18360ff1a300523d931bc297905a7238219e789028dBill Wendling/// loop, physical registers aren't accessed explicitly, and there are no side 18460ff1a300523d931bc297905a7238219e789028dBill Wendling/// effects that aren't captured by the operands or other flags. 1850f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// 186041b3f835682588cb63df7e609d726369dd6b7d3Bill Wendlingbool MachineLICM::IsLoopInvariantInst(MachineInstr &I) { 187a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner const TargetInstrDesc &TID = I.getDesc(); 188a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner 189a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner // Ignore stuff that we obviously can't hoist. 190237dee125997dcaf16e391878465162cc680c0faDan Gohman if (TID.mayStore() || TID.isCall() || TID.isTerminator() || 191a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner TID.hasUnmodeledSideEffects()) 192a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner return false; 1939b61f33351a92f6a87065adae713c02497780887Evan Cheng 194a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner if (TID.mayLoad()) { 195e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling // Okay, this instruction does a load. As a refinement, we allow the target 196e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling // to decide whether the loaded value is actually a constant. If so, we can 197e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling // actually use it as a load. 19845e94d68d7c99235cf4decc72812445b214df40eEvan Cheng if (!TII->isInvariantLoad(&I)) 199a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner // FIXME: we should be able to sink loads with no other side effects if 200a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner // there is nothing that can change memory from here until the end of 201e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling // block. This is a trivial form of alias analysis. 202a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner return false; 203a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner } 204074223a124e945ee67cacedb99e777265a0c6cb6Bill Wendling 205280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling DEBUG({ 206280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling DOUT << "--- Checking if we can hoist " << I; 207749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner if (I.getDesc().getImplicitUses()) { 208280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling DOUT << " * Instruction has implicit uses:\n"; 209280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling 2106f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman const TargetRegisterInfo *TRI = TM->getRegisterInfo(); 211749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner for (const unsigned *ImpUses = I.getDesc().getImplicitUses(); 21269244300b8a0112efb44b6273ecea4ca6264b8cfChris Lattner *ImpUses; ++ImpUses) 213e6d088acc90e422451e098555d383d4d65b6ce6bBill Wendling DOUT << " -> " << TRI->getName(*ImpUses) << "\n"; 214280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling } 215280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling 216749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner if (I.getDesc().getImplicitDefs()) { 217280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling DOUT << " * Instruction has implicit defines:\n"; 218280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling 2196f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman const TargetRegisterInfo *TRI = TM->getRegisterInfo(); 220749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner for (const unsigned *ImpDefs = I.getDesc().getImplicitDefs(); 22169244300b8a0112efb44b6273ecea4ca6264b8cfChris Lattner *ImpDefs; ++ImpDefs) 222e6d088acc90e422451e098555d383d4d65b6ce6bBill Wendling DOUT << " -> " << TRI->getName(*ImpDefs) << "\n"; 223280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling } 224280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling }); 225280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling 226d3361e996b272084d8ebe5bae8a0d420206c8e37Bill Wendling if (I.getDesc().getImplicitDefs() || I.getDesc().getImplicitUses()) { 227d3361e996b272084d8ebe5bae8a0d420206c8e37Bill Wendling DOUT << "Cannot hoist with implicit defines or uses\n"; 228d3361e996b272084d8ebe5bae8a0d420206c8e37Bill Wendling return false; 229d3361e996b272084d8ebe5bae8a0d420206c8e37Bill Wendling } 230d3361e996b272084d8ebe5bae8a0d420206c8e37Bill Wendling 231e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling // The instruction is loop invariant if all of its operands are. 2320f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 2330f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling const MachineOperand &MO = I.getOperand(i); 2340f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 235d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg()) 236fb018d0433f7b52c3f1235e675276adb1f92d597Bill Wendling continue; 237fb018d0433f7b52c3f1235e675276adb1f92d597Bill Wendling 2380f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling unsigned Reg = MO.getReg(); 239074223a124e945ee67cacedb99e777265a0c6cb6Bill Wendling if (Reg == 0) continue; 2400f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 241c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // Don't hoist an instruction that uses or defines a physical register. 242074223a124e945ee67cacedb99e777265a0c6cb6Bill Wendling if (TargetRegisterInfo::isPhysicalRegister(Reg)) 2430f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling return false; 2440f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 245c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman if (!MO.isUse()) 246c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman continue; 247c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman 248e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling assert(RegInfo->getVRegDef(Reg) && 249e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling "Machine instr not mapped for this vreg?!"); 2500f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 2510f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // If the loop contains the definition of an operand, then the instruction 2520f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // isn't loop invariant. 2539258cd3994e54aaec66f69a321032e071391dc90Bill Wendling if (CurLoop->contains(RegInfo->getVRegDef(Reg)->getParent())) 2540f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling return false; 2550f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling } 2560f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 2570f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // If we got this far, the instruction is loop invariant! 2580f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling return true; 2590f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling} 2600f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 26145e94d68d7c99235cf4decc72812445b214df40eEvan Cheng/// HasOnlyPHIUses - Return true if the only uses of Reg are PHIs. 26245e94d68d7c99235cf4decc72812445b214df40eEvan Chengstatic bool HasOnlyPHIUses(unsigned Reg, MachineRegisterInfo *RegInfo) { 26345e94d68d7c99235cf4decc72812445b214df40eEvan Cheng bool OnlyPHIUse = false; 26445e94d68d7c99235cf4decc72812445b214df40eEvan Cheng for (MachineRegisterInfo::use_iterator UI = RegInfo->use_begin(Reg), 26545e94d68d7c99235cf4decc72812445b214df40eEvan Cheng UE = RegInfo->use_end(); UI != UE; ++UI) { 26645e94d68d7c99235cf4decc72812445b214df40eEvan Cheng MachineInstr *UseMI = &*UI; 26745e94d68d7c99235cf4decc72812445b214df40eEvan Cheng if (UseMI->getOpcode() != TargetInstrInfo::PHI) 26845e94d68d7c99235cf4decc72812445b214df40eEvan Cheng return false; 26945e94d68d7c99235cf4decc72812445b214df40eEvan Cheng OnlyPHIUse = true; 27045e94d68d7c99235cf4decc72812445b214df40eEvan Cheng } 27145e94d68d7c99235cf4decc72812445b214df40eEvan Cheng return OnlyPHIUse; 27245e94d68d7c99235cf4decc72812445b214df40eEvan Cheng} 27345e94d68d7c99235cf4decc72812445b214df40eEvan Cheng 27445e94d68d7c99235cf4decc72812445b214df40eEvan Cheng/// IsProfitableToHoist - Return true if it is potentially profitable to hoist 27545e94d68d7c99235cf4decc72812445b214df40eEvan Cheng/// the given loop invariant. 27645e94d68d7c99235cf4decc72812445b214df40eEvan Chengbool MachineLICM::IsProfitableToHoist(MachineInstr &MI) { 27745e94d68d7c99235cf4decc72812445b214df40eEvan Cheng const TargetInstrDesc &TID = MI.getDesc(); 27845e94d68d7c99235cf4decc72812445b214df40eEvan Cheng 27945e94d68d7c99235cf4decc72812445b214df40eEvan Cheng // FIXME: For now, only hoist re-materilizable instructions. LICM will 28045e94d68d7c99235cf4decc72812445b214df40eEvan Cheng // increase register pressure. We want to make sure it doesn't increase 28145e94d68d7c99235cf4decc72812445b214df40eEvan Cheng // spilling. 2825caa883afc2c768c293757d4ca30d85b9094e876Evan Cheng if (!TID.mayLoad() && (!TID.isRematerializable() || 2835caa883afc2c768c293757d4ca30d85b9094e876Evan Cheng !TII->isTriviallyReMaterializable(&MI))) 28445e94d68d7c99235cf4decc72812445b214df40eEvan Cheng return false; 28545e94d68d7c99235cf4decc72812445b214df40eEvan Cheng 28645e94d68d7c99235cf4decc72812445b214df40eEvan Cheng if (!TID.isAsCheapAsAMove()) 28745e94d68d7c99235cf4decc72812445b214df40eEvan Cheng return true; 28845e94d68d7c99235cf4decc72812445b214df40eEvan Cheng 28945e94d68d7c99235cf4decc72812445b214df40eEvan Cheng // If the instruction is "cheap" and the only uses of the register(s) defined 29045e94d68d7c99235cf4decc72812445b214df40eEvan Cheng // by this MI are PHIs, then don't hoist it. Otherwise we just end up with a 29145e94d68d7c99235cf4decc72812445b214df40eEvan Cheng // cheap instruction (e.g. constant) with long live interval feeeding into 29245e94d68d7c99235cf4decc72812445b214df40eEvan Cheng // copies that are not always coalesced away. 29345e94d68d7c99235cf4decc72812445b214df40eEvan Cheng bool OnlyPHIUses = false; 29445e94d68d7c99235cf4decc72812445b214df40eEvan Cheng for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 29545e94d68d7c99235cf4decc72812445b214df40eEvan Cheng const MachineOperand &MO = MI.getOperand(i); 29645e94d68d7c99235cf4decc72812445b214df40eEvan Cheng if (!MO.isReg() || !MO.isDef()) 29745e94d68d7c99235cf4decc72812445b214df40eEvan Cheng continue; 29845e94d68d7c99235cf4decc72812445b214df40eEvan Cheng OnlyPHIUses |= HasOnlyPHIUses(MO.getReg(), RegInfo); 29945e94d68d7c99235cf4decc72812445b214df40eEvan Cheng } 30045e94d68d7c99235cf4decc72812445b214df40eEvan Cheng return !OnlyPHIUses; 30145e94d68d7c99235cf4decc72812445b214df40eEvan Cheng} 30245e94d68d7c99235cf4decc72812445b214df40eEvan Cheng 303e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling/// Hoist - When an instruction is found to use only loop invariant operands 304e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling/// that are safe to hoist, this instruction is called to do the dirty work. 3050f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// 306b48519cbadbb2b91a811f6fc189f40bd67c007f4Bill Wendlingvoid MachineLICM::Hoist(MachineInstr &MI) { 307041b3f835682588cb63df7e609d726369dd6b7d3Bill Wendling if (!IsLoopInvariantInst(MI)) return; 30845e94d68d7c99235cf4decc72812445b214df40eEvan Cheng if (!IsProfitableToHoist(MI)) return; 3090f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 310c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // Now move the instructions to the predecessor, inserting it before any 311c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // terminator instructions. 312c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman DEBUG({ 313c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman DOUT << "Hoisting " << MI; 314c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman if (CurPreheader->getBasicBlock()) 315c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman DOUT << " to MachineBasicBlock " 316c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman << CurPreheader->getBasicBlock()->getName(); 317c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman if (MI.getParent()->getBasicBlock()) 318c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman DOUT << " from MachineBasicBlock " 319c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman << MI.getParent()->getBasicBlock()->getName(); 320c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman DOUT << "\n"; 321c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman }); 322b48519cbadbb2b91a811f6fc189f40bd67c007f4Bill Wendling 323c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman CurPreheader->splice(CurPreheader->getFirstTerminator(), MI.getParent(), &MI); 324b48519cbadbb2b91a811f6fc189f40bd67c007f4Bill Wendling 325c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman ++NumHoisted; 3260f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling Changed = true; 3270f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling} 328