MachineLICM.cpp revision 45094e34bcbb133aa0bbe55710e25369df0e02ed
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" 31af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng#include "llvm/ADT/DenseMap.h" 32ac69582664714c2656a28ed6cb70627bb85ee673Chris Lattner#include "llvm/ADT/Statistic.h" 33ac69582664714c2656a28ed6cb70627bb85ee673Chris Lattner#include "llvm/Support/Compiler.h" 34ac69582664714c2656a28ed6cb70627bb85ee673Chris Lattner#include "llvm/Support/Debug.h" 35ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar#include "llvm/Support/raw_ostream.h" 360f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 370f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendlingusing namespace llvm; 380f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 39041b3f835682588cb63df7e609d726369dd6b7d3Bill WendlingSTATISTIC(NumHoisted, "Number of machine instructions hoisted out of loops"); 40af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan ChengSTATISTIC(NumCSEed, "Number of hoisted machine instructions CSEed"); 41b48519cbadbb2b91a811f6fc189f40bd67c007f4Bill Wendling 420f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendlingnamespace { 430f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling class VISIBILITY_HIDDEN MachineLICM : public MachineFunctionPass { 449258cd3994e54aaec66f69a321032e071391dc90Bill Wendling const TargetMachine *TM; 45efe2be797699d77dc3387969aa566c26d5c36d9dBill Wendling const TargetInstrInfo *TII; 46a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman const TargetRegisterInfo *TRI; 4745094e34bcbb133aa0bbe55710e25369df0e02edDan Gohman BitVector AllocatableSet; 4812ebf14048f4a6489033f8468ba36424442140acBill Wendling 490f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // Various analyses that we use... 50e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling MachineLoopInfo *LI; // Current MachineLoopInfo 51e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling MachineDominatorTree *DT; // Machine dominator tree for the cur loop 529258cd3994e54aaec66f69a321032e071391dc90Bill Wendling MachineRegisterInfo *RegInfo; // Machine register information 530f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 540f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // State that is updated as we process loops 55e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling bool Changed; // True if a loop is changed. 56e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling MachineLoop *CurLoop; // The current loop we are working on. 57c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman MachineBasicBlock *CurPreheader; // The preheader for CurLoop. 58af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng 59af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng // For each BB and opcode pair, keep a list of hoisted instructions. 60af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng DenseMap<std::pair<unsigned, unsigned>, 61af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng std::vector<const MachineInstr*> > CSEMap; 620f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling public: 630f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling static char ID; // Pass identification, replacement for typeid 64ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman MachineLICM() : MachineFunctionPass(&ID) {} 650f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 660f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling virtual bool runOnMachineFunction(MachineFunction &MF); 670f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 687224170f6a5b8a3c76f4adc5f84d650d142a27c4Dan Gohman const char *getPassName() const { return "Machine Instruction LICM"; } 697224170f6a5b8a3c76f4adc5f84d650d142a27c4Dan Gohman 70074223a124e945ee67cacedb99e777265a0c6cb6Bill Wendling // FIXME: Loop preheaders? 710f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling virtual void getAnalysisUsage(AnalysisUsage &AU) const { 720f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling AU.setPreservesCFG(); 730f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling AU.addRequired<MachineLoopInfo>(); 740f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling AU.addRequired<MachineDominatorTree>(); 75d5da7048c297deb6137ad10cac217c5d9d702065Bill Wendling AU.addPreserved<MachineLoopInfo>(); 76d5da7048c297deb6137ad10cac217c5d9d702065Bill Wendling AU.addPreserved<MachineDominatorTree>(); 77d5da7048c297deb6137ad10cac217c5d9d702065Bill Wendling MachineFunctionPass::getAnalysisUsage(AU); 780f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling } 79af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng 80af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng virtual void releaseMemory() { 81af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng CSEMap.clear(); 82af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng } 83af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng 840f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling private: 85041b3f835682588cb63df7e609d726369dd6b7d3Bill Wendling /// IsLoopInvariantInst - Returns true if the instruction is loop 860f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// invariant. I.e., all virtual register operands are defined outside of 870f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// the loop, physical registers aren't accessed (explicitly or implicitly), 880f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// and the instruction is hoistable. 890f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// 90041b3f835682588cb63df7e609d726369dd6b7d3Bill Wendling bool IsLoopInvariantInst(MachineInstr &I); 910f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 9245e94d68d7c99235cf4decc72812445b214df40eEvan Cheng /// IsProfitableToHoist - Return true if it is potentially profitable to 9345e94d68d7c99235cf4decc72812445b214df40eEvan Cheng /// hoist the given loop invariant. 9445e94d68d7c99235cf4decc72812445b214df40eEvan Cheng bool IsProfitableToHoist(MachineInstr &MI); 9545e94d68d7c99235cf4decc72812445b214df40eEvan Cheng 960f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// HoistRegion - Walk the specified region of the CFG (defined by all 970f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// blocks dominated by the specified block, and that are in the current 980f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// loop) in depth first order w.r.t the DominatorTree. This allows us to 990f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// visit definitions before uses, allowing us to hoist a loop body in one 1000f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// pass without iteration. 1010f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// 1020f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling void HoistRegion(MachineDomTreeNode *N); 1030f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1040f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// Hoist - When an instruction is found to only use loop invariant operands 1050f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// that is safe to hoist, this instruction is called to do the dirty work. 1060f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling /// 107b48519cbadbb2b91a811f6fc189f40bd67c007f4Bill Wendling void Hoist(MachineInstr &MI); 1080f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling }; 1090f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling} // end anonymous namespace 1100f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 111844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar MachineLICM::ID = 0; 112844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<MachineLICM> 1138870ce951d3f545edc8a5ce89ce3e7cdbf38eb25Bill WendlingX("machinelicm", "Machine Loop Invariant Code Motion"); 114844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 1150f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill WendlingFunctionPass *llvm::createMachineLICMPass() { return new MachineLICM(); } 1160f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 117c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman/// LoopIsOuterMostWithPreheader - Test if the given loop is the outer-most 118c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman/// loop that has a preheader. 119c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohmanstatic bool LoopIsOuterMostWithPreheader(MachineLoop *CurLoop) { 120c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop()) 121c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman if (L->getLoopPreheader()) 122c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman return false; 123c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman return true; 124c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman} 125c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman 1260f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// Hoist expressions out of the specified loop. Note, alias info for inner loop 1270f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// is not preserved so it is not a good idea to run LICM multiple times on one 1280f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// loop. 1290f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// 1300f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendlingbool MachineLICM::runOnMachineFunction(MachineFunction &MF) { 131740854bb1974642af77bec5e7f835e15115ad639Evan Cheng const Function *F = MF.getFunction(); 132740854bb1974642af77bec5e7f835e15115ad639Evan Cheng if (F->hasFnAttr(Attribute::OptimizeForSize)) 133740854bb1974642af77bec5e7f835e15115ad639Evan Cheng return false; 134740854bb1974642af77bec5e7f835e15115ad639Evan Cheng 135b7a89928f495da21e77bae788e3d6b1c57ecc192Bill Wendling DEBUG(errs() << "******** Machine LICM ********\n"); 136a17ad59e13f5caafe33738bafc75af00ca354c9fBill Wendling 1370f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling Changed = false; 138acb04ec4273516242fe87cb0a57a43136805deddBill Wendling TM = &MF.getTarget(); 1399258cd3994e54aaec66f69a321032e071391dc90Bill Wendling TII = TM->getInstrInfo(); 140a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman TRI = TM->getRegisterInfo(); 141acb04ec4273516242fe87cb0a57a43136805deddBill Wendling RegInfo = &MF.getRegInfo(); 14245094e34bcbb133aa0bbe55710e25369df0e02edDan Gohman AllocatableSet = TRI->getAllocatableSet(MF); 1430f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1440f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // Get our Loop information... 1450f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling LI = &getAnalysis<MachineLoopInfo>(); 1460f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling DT = &getAnalysis<MachineDominatorTree>(); 1470f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1480f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling for (MachineLoopInfo::iterator 1490f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling I = LI->begin(), E = LI->end(); I != E; ++I) { 150a17ad59e13f5caafe33738bafc75af00ca354c9fBill Wendling CurLoop = *I; 1510f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 152c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // Only visit outer-most preheader-sporting loops. 153c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman if (!LoopIsOuterMostWithPreheader(CurLoop)) 154c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman continue; 155c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman 156c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // Determine the block to which to hoist instructions. If we can't find a 157c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // suitable loop preheader, we can't do any hoisting. 158c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // 159c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // FIXME: We are only hoisting if the basic block coming into this loop 160c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // has only one successor. This isn't the case in general because we haven't 161c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // broken critical edges or added preheaders. 162c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman CurPreheader = CurLoop->getLoopPreheader(); 163c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman if (!CurPreheader) 164c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman continue; 165c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman 166c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman HoistRegion(DT->getNode(CurLoop->getHeader())); 1670f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling } 1680f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1690f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling return Changed; 1700f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling} 1710f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1720f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// HoistRegion - Walk the specified region of the CFG (defined by all blocks 1730f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// dominated by the specified block, and that are in the current loop) in depth 1740f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// first order w.r.t the DominatorTree. This allows us to visit definitions 1750f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// before uses, allowing us to hoist a loop body in one pass without iteration. 1760f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// 1770f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendlingvoid MachineLICM::HoistRegion(MachineDomTreeNode *N) { 1780f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling assert(N != 0 && "Null dominator tree node?"); 1790f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling MachineBasicBlock *BB = N->getBlock(); 1800f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1810f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // If this subregion is not in the top level loop at all, exit. 1820f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling if (!CurLoop->contains(BB)) return; 1830f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 184c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman for (MachineBasicBlock::iterator 185af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng MII = BB->begin(), E = BB->end(); MII != E; ) { 186af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng MachineBasicBlock::iterator NextMII = MII; ++NextMII; 187af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng MachineInstr &MI = *MII; 188c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman 189c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman Hoist(MI); 190af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng 191af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng MII = NextMII; 192c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman } 1930f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1940f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling const std::vector<MachineDomTreeNode*> &Children = N->getChildren(); 1950f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 1960f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling for (unsigned I = 0, E = Children.size(); I != E; ++I) 1970f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling HoistRegion(Children[I]); 1980f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling} 1990f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 200041b3f835682588cb63df7e609d726369dd6b7d3Bill Wendling/// IsLoopInvariantInst - Returns true if the instruction is loop 2010f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// invariant. I.e., all virtual register operands are defined outside of the 20260ff1a300523d931bc297905a7238219e789028dBill Wendling/// loop, physical registers aren't accessed explicitly, and there are no side 20360ff1a300523d931bc297905a7238219e789028dBill Wendling/// effects that aren't captured by the operands or other flags. 2040f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// 205041b3f835682588cb63df7e609d726369dd6b7d3Bill Wendlingbool MachineLICM::IsLoopInvariantInst(MachineInstr &I) { 206a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner const TargetInstrDesc &TID = I.getDesc(); 207a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner 208a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner // Ignore stuff that we obviously can't hoist. 209237dee125997dcaf16e391878465162cc680c0faDan Gohman if (TID.mayStore() || TID.isCall() || TID.isTerminator() || 210a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner TID.hasUnmodeledSideEffects()) 211a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner return false; 2129b61f33351a92f6a87065adae713c02497780887Evan Cheng 213a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner if (TID.mayLoad()) { 214e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling // Okay, this instruction does a load. As a refinement, we allow the target 215e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling // to decide whether the loaded value is actually a constant. If so, we can 216e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling // actually use it as a load. 21745e94d68d7c99235cf4decc72812445b214df40eEvan Cheng if (!TII->isInvariantLoad(&I)) 218a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner // FIXME: we should be able to sink loads with no other side effects if 219a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner // there is nothing that can change memory from here until the end of 220e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling // block. This is a trivial form of alias analysis. 221a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner return false; 222a22edc82cab86be4cb8876da1e6e78f82bb47a3eChris Lattner } 223074223a124e945ee67cacedb99e777265a0c6cb6Bill Wendling 224280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling DEBUG({ 225b7a89928f495da21e77bae788e3d6b1c57ecc192Bill Wendling errs() << "--- Checking if we can hoist " << I; 226749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner if (I.getDesc().getImplicitUses()) { 227b7a89928f495da21e77bae788e3d6b1c57ecc192Bill Wendling errs() << " * Instruction has implicit uses:\n"; 228280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling 2296f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman const TargetRegisterInfo *TRI = TM->getRegisterInfo(); 230749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner for (const unsigned *ImpUses = I.getDesc().getImplicitUses(); 23169244300b8a0112efb44b6273ecea4ca6264b8cfChris Lattner *ImpUses; ++ImpUses) 232b7a89928f495da21e77bae788e3d6b1c57ecc192Bill Wendling errs() << " -> " << TRI->getName(*ImpUses) << "\n"; 233280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling } 234280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling 235749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner if (I.getDesc().getImplicitDefs()) { 236b7a89928f495da21e77bae788e3d6b1c57ecc192Bill Wendling errs() << " * Instruction has implicit defines:\n"; 237280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling 2386f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman const TargetRegisterInfo *TRI = TM->getRegisterInfo(); 239749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner for (const unsigned *ImpDefs = I.getDesc().getImplicitDefs(); 24069244300b8a0112efb44b6273ecea4ca6264b8cfChris Lattner *ImpDefs; ++ImpDefs) 241b7a89928f495da21e77bae788e3d6b1c57ecc192Bill Wendling errs() << " -> " << TRI->getName(*ImpDefs) << "\n"; 242280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling } 243280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling }); 244280f4565eb599ce424c204b9ea07130d772af7e3Bill Wendling 245d3361e996b272084d8ebe5bae8a0d420206c8e37Bill Wendling if (I.getDesc().getImplicitDefs() || I.getDesc().getImplicitUses()) { 246b7a89928f495da21e77bae788e3d6b1c57ecc192Bill Wendling DEBUG(errs() << "Cannot hoist with implicit defines or uses\n"); 247d3361e996b272084d8ebe5bae8a0d420206c8e37Bill Wendling return false; 248d3361e996b272084d8ebe5bae8a0d420206c8e37Bill Wendling } 249d3361e996b272084d8ebe5bae8a0d420206c8e37Bill Wendling 250e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling // The instruction is loop invariant if all of its operands are. 2510f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 2520f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling const MachineOperand &MO = I.getOperand(i); 2530f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 254d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg()) 255fb018d0433f7b52c3f1235e675276adb1f92d597Bill Wendling continue; 256fb018d0433f7b52c3f1235e675276adb1f92d597Bill Wendling 2570f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling unsigned Reg = MO.getReg(); 258074223a124e945ee67cacedb99e777265a0c6cb6Bill Wendling if (Reg == 0) continue; 2590f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 260c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // Don't hoist an instruction that uses or defines a physical register. 261a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 262a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman // If this is a physical register use, we can't move it. If it is a def, 263a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman // we can move it, but only if the def is dead. 264a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman if (MO.isUse()) { 265a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman // If the physreg has no defs anywhere, it's just an ambient register 26645094e34bcbb133aa0bbe55710e25369df0e02edDan Gohman // and we can freely move its uses. Alternatively, if it's allocatable, 26745094e34bcbb133aa0bbe55710e25369df0e02edDan Gohman // it could get allocated to something with a def during allocation. 268a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman if (!RegInfo->def_empty(Reg)) 269a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman return false; 27045094e34bcbb133aa0bbe55710e25369df0e02edDan Gohman if (AllocatableSet.test(Reg)) 27145094e34bcbb133aa0bbe55710e25369df0e02edDan Gohman return false; 272a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman // Check for a def among the register's aliases too. 27345094e34bcbb133aa0bbe55710e25369df0e02edDan Gohman for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 27445094e34bcbb133aa0bbe55710e25369df0e02edDan Gohman unsigned AliasReg = *Alias; 27545094e34bcbb133aa0bbe55710e25369df0e02edDan Gohman if (!RegInfo->def_empty(AliasReg)) 27645094e34bcbb133aa0bbe55710e25369df0e02edDan Gohman return false; 27745094e34bcbb133aa0bbe55710e25369df0e02edDan Gohman if (AllocatableSet.test(AliasReg)) 278a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman return false; 27945094e34bcbb133aa0bbe55710e25369df0e02edDan Gohman } 280a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman // Otherwise it's safe to move. 281a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman continue; 282a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman } else if (!MO.isDead()) { 283a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman // A def that isn't dead. We can't move it. 284a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman return false; 285a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman } 286a8fb336c2e7b8beb00d96a0992c41d38f0310a8fDan Gohman } 2870f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 288c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman if (!MO.isUse()) 289c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman continue; 290c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman 291e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling assert(RegInfo->getVRegDef(Reg) && 292e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling "Machine instr not mapped for this vreg?!"); 2930f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 2940f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // If the loop contains the definition of an operand, then the instruction 2950f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // isn't loop invariant. 2969258cd3994e54aaec66f69a321032e071391dc90Bill Wendling if (CurLoop->contains(RegInfo->getVRegDef(Reg)->getParent())) 2970f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling return false; 2980f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling } 2990f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 3000f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling // If we got this far, the instruction is loop invariant! 3010f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling return true; 3020f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling} 3030f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 304af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng 305af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng/// HasPHIUses - Return true if the specified register has any PHI use. 306af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Chengstatic bool HasPHIUses(unsigned Reg, MachineRegisterInfo *RegInfo) { 30745e94d68d7c99235cf4decc72812445b214df40eEvan Cheng for (MachineRegisterInfo::use_iterator UI = RegInfo->use_begin(Reg), 30845e94d68d7c99235cf4decc72812445b214df40eEvan Cheng UE = RegInfo->use_end(); UI != UE; ++UI) { 30945e94d68d7c99235cf4decc72812445b214df40eEvan Cheng MachineInstr *UseMI = &*UI; 310af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng if (UseMI->getOpcode() == TargetInstrInfo::PHI) 311af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng return true; 31245e94d68d7c99235cf4decc72812445b214df40eEvan Cheng } 313af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng return false; 31445e94d68d7c99235cf4decc72812445b214df40eEvan Cheng} 31545e94d68d7c99235cf4decc72812445b214df40eEvan Cheng 31645e94d68d7c99235cf4decc72812445b214df40eEvan Cheng/// IsProfitableToHoist - Return true if it is potentially profitable to hoist 31745e94d68d7c99235cf4decc72812445b214df40eEvan Cheng/// the given loop invariant. 31845e94d68d7c99235cf4decc72812445b214df40eEvan Chengbool MachineLICM::IsProfitableToHoist(MachineInstr &MI) { 319efc783951c0ab801601aeaeae07ef2a7305d37b0Evan Cheng if (MI.getOpcode() == TargetInstrInfo::IMPLICIT_DEF) 320efc783951c0ab801601aeaeae07ef2a7305d37b0Evan Cheng return false; 321efc783951c0ab801601aeaeae07ef2a7305d37b0Evan Cheng 32245e94d68d7c99235cf4decc72812445b214df40eEvan Cheng const TargetInstrDesc &TID = MI.getDesc(); 32345e94d68d7c99235cf4decc72812445b214df40eEvan Cheng 32445e94d68d7c99235cf4decc72812445b214df40eEvan Cheng // FIXME: For now, only hoist re-materilizable instructions. LICM will 32545e94d68d7c99235cf4decc72812445b214df40eEvan Cheng // increase register pressure. We want to make sure it doesn't increase 32645e94d68d7c99235cf4decc72812445b214df40eEvan Cheng // spilling. 3275caa883afc2c768c293757d4ca30d85b9094e876Evan Cheng if (!TID.mayLoad() && (!TID.isRematerializable() || 3285caa883afc2c768c293757d4ca30d85b9094e876Evan Cheng !TII->isTriviallyReMaterializable(&MI))) 32945e94d68d7c99235cf4decc72812445b214df40eEvan Cheng return false; 33045e94d68d7c99235cf4decc72812445b214df40eEvan Cheng 331af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng // If result(s) of this instruction is used by PHIs, then don't hoist it. 332af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng // The presence of joins makes it difficult for current register allocator 333af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng // implementation to perform remat. 33445e94d68d7c99235cf4decc72812445b214df40eEvan Cheng for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 33545e94d68d7c99235cf4decc72812445b214df40eEvan Cheng const MachineOperand &MO = MI.getOperand(i); 33645e94d68d7c99235cf4decc72812445b214df40eEvan Cheng if (!MO.isReg() || !MO.isDef()) 33745e94d68d7c99235cf4decc72812445b214df40eEvan Cheng continue; 338af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng if (HasPHIUses(MO.getReg(), RegInfo)) 339af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng return false; 34045e94d68d7c99235cf4decc72812445b214df40eEvan Cheng } 341af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng 342af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng return true; 343af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng} 344af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng 345af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Chengstatic const MachineInstr *LookForDuplicate(const MachineInstr *MI, 346efc783951c0ab801601aeaeae07ef2a7305d37b0Evan Cheng std::vector<const MachineInstr*> &PrevMIs, 347efc783951c0ab801601aeaeae07ef2a7305d37b0Evan Cheng MachineRegisterInfo *RegInfo) { 348af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng unsigned NumOps = MI->getNumOperands(); 349af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng for (unsigned i = 0, e = PrevMIs.size(); i != e; ++i) { 350af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng const MachineInstr *PrevMI = PrevMIs[i]; 351af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng unsigned NumOps2 = PrevMI->getNumOperands(); 352af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng if (NumOps != NumOps2) 353af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng continue; 354af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng bool IsSame = true; 355af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng for (unsigned j = 0; j != NumOps; ++j) { 356af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng const MachineOperand &MO = MI->getOperand(j); 357efc783951c0ab801601aeaeae07ef2a7305d37b0Evan Cheng if (MO.isReg() && MO.isDef()) { 358efc783951c0ab801601aeaeae07ef2a7305d37b0Evan Cheng if (RegInfo->getRegClass(MO.getReg()) != 359efc783951c0ab801601aeaeae07ef2a7305d37b0Evan Cheng RegInfo->getRegClass(PrevMI->getOperand(j).getReg())) { 360efc783951c0ab801601aeaeae07ef2a7305d37b0Evan Cheng IsSame = false; 361efc783951c0ab801601aeaeae07ef2a7305d37b0Evan Cheng break; 362efc783951c0ab801601aeaeae07ef2a7305d37b0Evan Cheng } 363af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng continue; 364efc783951c0ab801601aeaeae07ef2a7305d37b0Evan Cheng } 365af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng if (!MO.isIdenticalTo(PrevMI->getOperand(j))) { 366af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng IsSame = false; 367af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng break; 368af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng } 369af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng } 370af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng if (IsSame) 371af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng return PrevMI; 372af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng } 373af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng return 0; 37445e94d68d7c99235cf4decc72812445b214df40eEvan Cheng} 37545e94d68d7c99235cf4decc72812445b214df40eEvan Cheng 376e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling/// Hoist - When an instruction is found to use only loop invariant operands 377e4fc1ccd4dd66a7421e911528c1af5337c20167bBill Wendling/// that are safe to hoist, this instruction is called to do the dirty work. 3780f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling/// 379b48519cbadbb2b91a811f6fc189f40bd67c007f4Bill Wendlingvoid MachineLICM::Hoist(MachineInstr &MI) { 380041b3f835682588cb63df7e609d726369dd6b7d3Bill Wendling if (!IsLoopInvariantInst(MI)) return; 38145e94d68d7c99235cf4decc72812445b214df40eEvan Cheng if (!IsProfitableToHoist(MI)) return; 3820f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling 383c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // Now move the instructions to the predecessor, inserting it before any 384c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman // terminator instructions. 385c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman DEBUG({ 386ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar errs() << "Hoisting " << MI; 387c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman if (CurPreheader->getBasicBlock()) 388ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar errs() << " to MachineBasicBlock " 389ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar << CurPreheader->getBasicBlock()->getName(); 390c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman if (MI.getParent()->getBasicBlock()) 391ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar errs() << " from MachineBasicBlock " 392ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar << MI.getParent()->getBasicBlock()->getName(); 393ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar errs() << "\n"; 394c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman }); 395b48519cbadbb2b91a811f6fc189f40bd67c007f4Bill Wendling 396af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng // Look for opportunity to CSE the hoisted instruction. 397af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng std::pair<unsigned, unsigned> BBOpcPair = 398af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng std::make_pair(CurPreheader->getNumber(), MI.getOpcode()); 399af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng DenseMap<std::pair<unsigned, unsigned>, 400af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng std::vector<const MachineInstr*> >::iterator CI = CSEMap.find(BBOpcPair); 401af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng bool DoneCSE = false; 402af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng if (CI != CSEMap.end()) { 403efc783951c0ab801601aeaeae07ef2a7305d37b0Evan Cheng const MachineInstr *Dup = LookForDuplicate(&MI, CI->second, RegInfo); 404af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng if (Dup) { 405b7a89928f495da21e77bae788e3d6b1c57ecc192Bill Wendling DEBUG(errs() << "CSEing " << MI << " with " << *Dup); 406af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 407af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng const MachineOperand &MO = MI.getOperand(i); 408af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng if (MO.isReg() && MO.isDef()) 409af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng RegInfo->replaceRegWith(MO.getReg(), Dup->getOperand(i).getReg()); 410af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng } 411af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng MI.eraseFromParent(); 412af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng DoneCSE = true; 413af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng ++NumCSEed; 414af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng } 415af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng } 416af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng 417af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng // Otherwise, splice the instruction to the preheader. 418af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng if (!DoneCSE) { 419af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng CurPreheader->splice(CurPreheader->getFirstTerminator(), 420af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng MI.getParent(), &MI); 421af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng // Add to the CSE map. 422af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng if (CI != CSEMap.end()) 423af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng CI->second.push_back(&MI); 424af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng else { 425af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng std::vector<const MachineInstr*> CSEMIs; 426af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng CSEMIs.push_back(&MI); 427af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng CSEMap.insert(std::make_pair(BBOpcPair, CSEMIs)); 428af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng } 429af6949d0b1e1545dff21c5e492fbf1760aa74b59Evan Cheng } 430b48519cbadbb2b91a811f6fc189f40bd67c007f4Bill Wendling 431c475c3608a5f0fc0c6bd43da04ae786649690070Dan Gohman ++NumHoisted; 4320f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling Changed = true; 4330f940c95d4506f8d04fa2aeda8a79cadb3105fe3Bill Wendling} 434