LICM.cpp revision 5f0eb8da62308126d5b61e3eee5bee75b9dc5194
1e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner//===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===// 2e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner// 3e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner// This pass is a simple loop invariant code motion pass. 4e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner// 5e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner// Note that this pass does NOT require pre-headers to exist on loops in the 6e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner// CFG, but if there is not distinct preheader for a loop, the hoisted code will 7e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner// be *DUPLICATED* in every basic block, outside of the loop, that preceeds the 8e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner// loop header. Additionally, any use of one of these hoisted expressions 9e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner// cannot be loop invariant itself, because the expression hoisted gets a PHI 10e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner// node that is loop variant. 11e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner// 12e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner// For these reasons, and many more, it makes sense to run a pass before this 13e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner// that ensures that there are preheaders on all loops. That said, we don't 14e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner// REQUIRE it. :) 15e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner// 16e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner//===----------------------------------------------------------------------===// 17e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 18e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include "llvm/Transforms/Scalar.h" 19e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include "llvm/Transforms/Utils/Local.h" 20e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include "llvm/Analysis/LoopInfo.h" 21e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include "llvm/iOperators.h" 22e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include "llvm/iPHINode.h" 23e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include "llvm/Support/InstVisitor.h" 24e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include "llvm/Support/CFG.h" 25e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include "Support/STLExtras.h" 26e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include "Support/StatisticReporter.h" 27e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include <algorithm> 285ba99bd124dc18302f527d6e2b0efd0fa866bc9eAnand Shuklausing std::string; 29e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 30e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattnerstatic Statistic<> NumHoistedNPH("licm\t\t- Number of insts hoisted to multiple" 31e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner " loop preds (bad, no loop pre-header)"); 32e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattnerstatic Statistic<> NumHoistedPH("licm\t\t- Number of insts hoisted to a loop " 33e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner "pre-header"); 34e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 35e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattnernamespace { 36e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner struct LICM : public FunctionPass, public InstVisitor<LICM> { 377e70829632f82de15db187845666aaca6e04b792Chris Lattner virtual bool runOnFunction(Function &F); 38e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 39e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // This transformation requires natural loop information... 40e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 41e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner AU.preservesCFG(); 425f0eb8da62308126d5b61e3eee5bee75b9dc5194Chris Lattner AU.addRequired<LoopInfo>(); 43e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } 44e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 45e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner private: 46e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // List of predecessor blocks for the current loop - These blocks are where 47e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // we hoist loop invariants to for the current loop. 48e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // 49e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner std::vector<BasicBlock*> LoopPreds, LoopBackEdges; 50e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 51e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner Loop *CurLoop; // The current loop we are working on... 52e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner bool Changed; // Set to true when we change anything. 53e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 54e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // visitLoop - Hoist expressions out of the specified loop... 55e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner void visitLoop(Loop *L); 56e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 57e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // notInCurrentLoop - Little predicate that returns true if the specified 58e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // basic block is in a subloop of the current one, not the current one 59e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // itself. 60e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // 61e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner bool notInCurrentLoop(BasicBlock *BB) { 62e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner for (unsigned i = 0, e = CurLoop->getSubLoops().size(); i != e; ++i) 63e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner if (CurLoop->getSubLoops()[i]->contains(BB)) 64e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner return true; // A subloop actually contains this block! 65e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner return false; 66e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } 67e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 68e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // hoist - When an instruction is found to only use loop invariant operands 69e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // that is safe to hoist, this instruction is called to do the dirty work. 70e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // 717e70829632f82de15db187845666aaca6e04b792Chris Lattner void hoist(Instruction &I); 72e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 73e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // isLoopInvariant - Return true if the specified value is loop invariant 74e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner inline bool isLoopInvariant(Value *V) { 75e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 76e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner return !CurLoop->contains(I->getParent()); 77e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner return true; // All non-instructions are loop invariant 78e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } 79e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 80e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // visitBasicBlock - Run LICM on a particular block. 81e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner void visitBasicBlock(BasicBlock *BB); 82e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 83e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Instruction visitation handlers... these basically control whether or not 84e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // the specified instruction types are hoisted. 85e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // 86e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner friend class InstVisitor<LICM>; 877e70829632f82de15db187845666aaca6e04b792Chris Lattner void visitUnaryOperator(Instruction &I) { 887e70829632f82de15db187845666aaca6e04b792Chris Lattner if (isLoopInvariant(I.getOperand(0))) hoist(I); 89e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } 907e70829632f82de15db187845666aaca6e04b792Chris Lattner void visitBinaryOperator(Instruction &I) { 917e70829632f82de15db187845666aaca6e04b792Chris Lattner if (isLoopInvariant(I.getOperand(0)) && isLoopInvariant(I.getOperand(1))) 92e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner hoist(I); 93e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } 94e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 957e70829632f82de15db187845666aaca6e04b792Chris Lattner void visitCastInst(CastInst &I) { visitUnaryOperator((Instruction&)I); } 967e70829632f82de15db187845666aaca6e04b792Chris Lattner void visitShiftInst(ShiftInst &I) { visitBinaryOperator((Instruction&)I); } 97e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 987e70829632f82de15db187845666aaca6e04b792Chris Lattner void visitGetElementPtrInst(GetElementPtrInst &GEPI) { 997e70829632f82de15db187845666aaca6e04b792Chris Lattner Instruction &I = (Instruction&)GEPI; 1007e70829632f82de15db187845666aaca6e04b792Chris Lattner for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) 1017e70829632f82de15db187845666aaca6e04b792Chris Lattner if (!isLoopInvariant(I.getOperand(i))) return; 102e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner hoist(I); 103e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } 104e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner }; 105f629309f74cf1a64aa7fd1cd5784fd7db9a8f59eChris Lattner 106a6275ccdf5e1aa208afde56c498e2b13e16442f0Chris Lattner RegisterOpt<LICM> X("licm", "Loop Invariant Code Motion"); 107e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner} 108e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 109e0e734eea052a4e8372e6f430ef41149128ba0a6Chris LattnerPass *createLICMPass() { return new LICM(); } 110e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 1117e70829632f82de15db187845666aaca6e04b792Chris Lattnerbool LICM::runOnFunction(Function &) { 112e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // get our loop information... 113e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner const std::vector<Loop*> &TopLevelLoops = 114e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner getAnalysis<LoopInfo>().getTopLevelLoops(); 115e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 116e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Traverse loops in postorder, hoisting expressions out of the deepest loops 117e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // first. 118e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // 119e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner Changed = false; 120e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner std::for_each(TopLevelLoops.begin(), TopLevelLoops.end(), 121e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner bind_obj(this, &LICM::visitLoop)); 122e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner return Changed; 123e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner} 124e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 125e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattnervoid LICM::visitLoop(Loop *L) { 126e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Recurse through all subloops before we process this loop... 127e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner std::for_each(L->getSubLoops().begin(), L->getSubLoops().end(), 128e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner bind_obj(this, &LICM::visitLoop)); 129e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner CurLoop = L; 130e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 131e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Calculate the set of predecessors for this loop. The predecessors for this 132e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // loop are equal to the predecessors for the header node of the loop that are 133e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // not themselves in the loop. 134e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // 135e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner BasicBlock *Header = L->getHeader(); 136e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 137e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Calculate the sets of predecessors and backedges of the loop... 138e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner LoopBackEdges.insert(LoopBackEdges.end(),pred_begin(Header),pred_end(Header)); 139e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 140e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner std::vector<BasicBlock*>::iterator LPI = 141e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner std::partition(LoopBackEdges.begin(), LoopBackEdges.end(), 142e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner bind_obj(CurLoop, &Loop::contains)); 143e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 144e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Move all predecessors to the LoopPreds vector... 145e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner LoopPreds.insert(LoopPreds.end(), LPI, LoopBackEdges.end()); 146e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 147e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Remove predecessors from backedges list... 148e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner LoopBackEdges.erase(LPI, LoopBackEdges.end()); 149e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 150e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 151e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // The only way that there could be no predecessors to a loop is if the loop 152e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // is not reachable. Since we don't care about optimizing dead loops, 153e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // summarily ignore them. 154e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // 155e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner if (LoopPreds.empty()) return; 156e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 157e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // We want to visit all of the instructions in this loop... that are not parts 158e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // of our subloops (they have already had their invariants hoisted out of 159e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // their loop, into this loop, so there is no need to process the BODIES of 160e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // the subloops). 161e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // 162e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner std::vector<BasicBlock*> BBs(L->getBlocks().begin(), L->getBlocks().end()); 163e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 164e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Remove blocks that are actually in subloops... 165e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner BBs.erase(std::remove_if(BBs.begin(), BBs.end(), 166e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner bind_obj(this, &LICM::notInCurrentLoop)), BBs.end()); 167e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 168e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Visit all of the basic blocks we have chosen, hoisting out the instructions 169e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // as neccesary. This leaves dead copies of the instruction in the loop 170e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // unfortunately... 171e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // 172e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner for_each(BBs.begin(), BBs.end(), bind_obj(this, &LICM::visitBasicBlock)); 173e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 174e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Clear out loops state information for the next iteration 175e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner CurLoop = 0; 176e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner LoopPreds.clear(); 177e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner LoopBackEdges.clear(); 178e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner} 179e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 180e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattnervoid LICM::visitBasicBlock(BasicBlock *BB) { 1817e70829632f82de15db187845666aaca6e04b792Chris Lattner for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { 1827e70829632f82de15db187845666aaca6e04b792Chris Lattner visit(*I); 183e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 1847e70829632f82de15db187845666aaca6e04b792Chris Lattner if (dceInstruction(I)) 185e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner Changed = true; 186e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner else 1877e70829632f82de15db187845666aaca6e04b792Chris Lattner ++I; 188e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } 189e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner} 190e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 191e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 1927e70829632f82de15db187845666aaca6e04b792Chris Lattnervoid LICM::hoist(Instruction &Inst) { 1937e70829632f82de15db187845666aaca6e04b792Chris Lattner if (Inst.use_empty()) return; // Don't (re) hoist dead instructions! 194e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner //cerr << "Hoisting " << Inst; 195e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 196e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner BasicBlock *Header = CurLoop->getHeader(); 197e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 198e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Old instruction will be removed, so take it's name... 1997e70829632f82de15db187845666aaca6e04b792Chris Lattner string InstName = Inst.getName(); 2007e70829632f82de15db187845666aaca6e04b792Chris Lattner Inst.setName(""); 201e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 202e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // The common case is that we have a pre-header. Generate special case code 203e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // that is faster if that is the case. 204e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // 205e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner if (LoopPreds.size() == 1) { 206e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner BasicBlock *Pred = LoopPreds[0]; 207e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 208e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Create a new copy of the instruction, for insertion into Pred. 2097e70829632f82de15db187845666aaca6e04b792Chris Lattner Instruction *New = Inst.clone(); 210e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner New->setName(InstName); 211e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 212e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Insert the new node in Pred, before the terminator. 2137e70829632f82de15db187845666aaca6e04b792Chris Lattner Pred->getInstList().insert(--Pred->end(), New); 214e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 2157e70829632f82de15db187845666aaca6e04b792Chris Lattner // Kill the old instruction... 2167e70829632f82de15db187845666aaca6e04b792Chris Lattner Inst.replaceAllUsesWith(New); 217e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner ++NumHoistedPH; 218e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 219e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } else { 220e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // No loop pre-header, insert a PHI node into header to capture all of the 221e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // incoming versions of the value. 222e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // 2237e70829632f82de15db187845666aaca6e04b792Chris Lattner PHINode *LoopVal = new PHINode(Inst.getType(), InstName+".phi"); 224e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 225e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Insert the new PHI node into the loop header... 226e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner Header->getInstList().push_front(LoopVal); 227e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 228e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Insert cloned versions of the instruction into all of the loop preds. 229e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner for (unsigned i = 0, e = LoopPreds.size(); i != e; ++i) { 230e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner BasicBlock *Pred = LoopPreds[i]; 231e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 232e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Create a new copy of the instruction, for insertion into Pred. 2337e70829632f82de15db187845666aaca6e04b792Chris Lattner Instruction *New = Inst.clone(); 234e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner New->setName(InstName); 235e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 236e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Insert the new node in Pred, before the terminator. 2377e70829632f82de15db187845666aaca6e04b792Chris Lattner Pred->getInstList().insert(--Pred->end(), New); 238e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 239e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Add the incoming value to the PHI node. 240e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner LoopVal->addIncoming(New, Pred); 241e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } 242e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 243e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Add incoming values to the PHI node for all backedges in the loop... 244e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner for (unsigned i = 0, e = LoopBackEdges.size(); i != e; ++i) 245e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner LoopVal->addIncoming(LoopVal, LoopBackEdges[i]); 246e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 247e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Replace all uses of the old version of the instruction in the loop with 248e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // the new version that is out of the loop. We know that this is ok, 249e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // because the new definition is in the loop header, which dominates the 250e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // entire loop body. The old definition was defined _inside_ of the loop, 251e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // so the scope cannot extend outside of the loop, so we're ok. 252e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // 2537e70829632f82de15db187845666aaca6e04b792Chris Lattner Inst.replaceAllUsesWith(LoopVal); 254e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner ++NumHoistedNPH; 255e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } 256e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 257e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner Changed = true; 258e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner} 259e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 260