LICM.cpp revision 9966c03aad031f738718bed3bc00371e358beb5d
1e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner//===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===// 2e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner// 32e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// This pass is a simple loop invariant code motion pass. An interesting aspect 42e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// of this pass is that it uses alias analysis for two purposes: 52e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// 62e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// 1. Moving loop invariant loads out of loops. If we can determine that a 72e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// load inside of a loop never aliases anything stored to, we can hoist it 82e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// like any other instruction. 92e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// 2. Scalar Promotion of Memory - If there is a store instruction inside of 102e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// the loop, we try to move the store to happen AFTER the loop instead of 112e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// inside of the loop. This can only happen if a few conditions are true: 122e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// A. The pointer stored through is loop invariant 132e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// B. There are no stores or loads in the loop which _may_ alias the 142e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// pointer. There are no calls in the loop which mod/ref the pointer. 152e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// If these conditions are true, we can promote the loads and stores in the 162e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// loop of the pointer to use a temporary alloca'd variable. We then use 172e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// the mem2reg functionality to construct the appropriate SSA form for the 182e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// variable. 19e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner// 20e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner//===----------------------------------------------------------------------===// 21e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 22e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include "llvm/Transforms/Scalar.h" 232e6e741b737960ecd0b68610875050019aac0f07Chris Lattner#include "llvm/Transforms/Utils/PromoteMemToReg.h" 24e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include "llvm/Transforms/Utils/Local.h" 25e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include "llvm/Analysis/LoopInfo.h" 26f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner#include "llvm/Analysis/AliasAnalysis.h" 270252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner#include "llvm/Analysis/AliasSetTracker.h" 28952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner#include "llvm/Analysis/Dominators.h" 292e6e741b737960ecd0b68610875050019aac0f07Chris Lattner#include "llvm/Instructions.h" 302e6e741b737960ecd0b68610875050019aac0f07Chris Lattner#include "llvm/DerivedTypes.h" 31fb743a937f6856e3ab1f8ed599677038750a550eChris Lattner#include "llvm/Target/TargetData.h" 32e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include "llvm/Support/InstVisitor.h" 332e6e741b737960ecd0b68610875050019aac0f07Chris Lattner#include "llvm/Support/CFG.h" 342e6e741b737960ecd0b68610875050019aac0f07Chris Lattner#include "Support/CommandLine.h" 356806f5614d2ec260fda954c951d33f58e77ed610Chris Lattner#include "Support/Debug.h" 366806f5614d2ec260fda954c951d33f58e77ed610Chris Lattner#include "Support/Statistic.h" 37b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner#include "llvm/Assembly/Writer.h" 38e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include <algorithm> 39e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 40e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattnernamespace { 412e6e741b737960ecd0b68610875050019aac0f07Chris Lattner cl::opt<bool> DisablePromotion("disable-licm-promotion", cl::Hidden, 422e6e741b737960ecd0b68610875050019aac0f07Chris Lattner cl::desc("Disable memory promotion in LICM pass")); 432e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 44a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner Statistic<> NumHoisted("licm", "Number of instructions hoisted out of loop"); 45a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner Statistic<> NumHoistedLoads("licm", "Number of load insts hoisted"); 462e6e741b737960ecd0b68610875050019aac0f07Chris Lattner Statistic<> NumPromoted("licm", "Number of memory locations promoted to registers"); 472e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 48e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner struct LICM : public FunctionPass, public InstVisitor<LICM> { 497e70829632f82de15db187845666aaca6e04b792Chris Lattner virtual bool runOnFunction(Function &F); 50e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 5194170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// This transformation requires natural loop information & requires that 5294170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// loop preheaders be inserted into the CFG... 5394170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// 54e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 55cb2610ea037a17115ef3a01a6bdaab4e3cfdca27Chris Lattner AU.setPreservesCFG(); 56eb53ae4f2dc39e75e725b21b52d77d29cf1c11c9Chris Lattner AU.addRequiredID(LoopPreheadersID); 575f0eb8da62308126d5b61e3eee5bee75b9dc5194Chris Lattner AU.addRequired<LoopInfo>(); 58952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner AU.addRequired<DominatorTree>(); 590252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner AU.addRequired<DominanceFrontier>(); // For scalar promotion (mem2reg) 60f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner AU.addRequired<AliasAnalysis>(); 61e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } 62e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 63e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner private: 642e6e741b737960ecd0b68610875050019aac0f07Chris Lattner LoopInfo *LI; // Current LoopInfo 652e6e741b737960ecd0b68610875050019aac0f07Chris Lattner AliasAnalysis *AA; // Current AliasAnalysis information 662e6e741b737960ecd0b68610875050019aac0f07Chris Lattner bool Changed; // Set to true when we change anything. 672e6e741b737960ecd0b68610875050019aac0f07Chris Lattner BasicBlock *Preheader; // The preheader block of the current loop... 682e6e741b737960ecd0b68610875050019aac0f07Chris Lattner Loop *CurLoop; // The current loop we are working on... 690252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner AliasSetTracker *CurAST; // AliasSet information for the current loop... 709966c03aad031f738718bed3bc00371e358beb5dTanya Lattner DominatorTree *CurDT; // Dominator Tree for the current Loop... 71e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 7294170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// visitLoop - Hoist expressions out of the specified loop... 7394170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// 740252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner void visitLoop(Loop *L, AliasSetTracker &AST); 75e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 76952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// HoistRegion - Walk the specified region of the CFG (defined by all 77952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// blocks dominated by the specified block, and that are in the current 78952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// loop) in depth first order w.r.t the DominatorTree. This allows us to 79952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// visit defintions before uses, allowing us to hoist a loop body in one 80952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// pass without iteration. 81952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// 82952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner void HoistRegion(DominatorTree::Node *N); 83952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 84b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner /// inSubLoop - Little predicate that returns true if the specified basic 85b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner /// block is in a subloop of the current one, not the current one itself. 8694170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// 87b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner bool inSubLoop(BasicBlock *BB) { 88b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop"); 89e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner for (unsigned i = 0, e = CurLoop->getSubLoops().size(); i != e; ++i) 90e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner if (CurLoop->getSubLoops()[i]->contains(BB)) 91b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner return true; // A subloop actually contains this block! 92b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner return false; 93e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } 94e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 9594170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// hoist - When an instruction is found to only use loop invariant operands 9694170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// that is safe to hoist, this instruction is called to do the dirty work. 9794170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// 987e70829632f82de15db187845666aaca6e04b792Chris Lattner void hoist(Instruction &I); 99e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 1009966c03aad031f738718bed3bc00371e358beb5dTanya Lattner /// SafeToHoist - Only hoist an instruction if it is not a trapping instruction 1019966c03aad031f738718bed3bc00371e358beb5dTanya Lattner /// or if it is a trapping instruction and is guaranteed to execute 1029966c03aad031f738718bed3bc00371e358beb5dTanya Lattner /// 1039966c03aad031f738718bed3bc00371e358beb5dTanya Lattner bool SafeToHoist(Instruction &I); 1049966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 10594170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// pointerInvalidatedByLoop - Return true if the body of this loop may 10694170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// store into the memory location pointed to by V. 10794170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// 1082e6e741b737960ecd0b68610875050019aac0f07Chris Lattner bool pointerInvalidatedByLoop(Value *V) { 1090252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner // Check to see if any of the basic blocks in CurLoop invalidate *V. 1100252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner return CurAST->getAliasSetForPointer(V, 0).isMod(); 1112e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 112f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner 11394170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// isLoopInvariant - Return true if the specified value is loop invariant 11494170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// 115e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner inline bool isLoopInvariant(Value *V) { 116e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 117e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner return !CurLoop->contains(I->getParent()); 118e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner return true; // All non-instructions are loop invariant 119e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } 120e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 1212e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// PromoteValuesInLoop - Look at the stores in the loop and promote as many 1222e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// to scalars as we can. 1232e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// 1242e6e741b737960ecd0b68610875050019aac0f07Chris Lattner void PromoteValuesInLoop(); 1252e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 1262e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// findPromotableValuesInLoop - Check the current loop for stores to 1272e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// definate pointers, which are not loaded and stored through may aliases. 1282e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// If these are found, create an alloca for the value, add it to the 1292e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// PromotedValues list, and keep track of the mapping from value to 1302e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// alloca... 1312e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// 1322e6e741b737960ecd0b68610875050019aac0f07Chris Lattner void findPromotableValuesInLoop( 1332e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::vector<std::pair<AllocaInst*, Value*> > &PromotedValues, 1342e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::map<Value*, AllocaInst*> &Val2AlMap); 1352e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 1362e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 13794170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// Instruction visitation handlers... these basically control whether or 13894170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// not the specified instruction types are hoisted. 13994170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// 140e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner friend class InstVisitor<LICM>; 1417e70829632f82de15db187845666aaca6e04b792Chris Lattner void visitBinaryOperator(Instruction &I) { 1429966c03aad031f738718bed3bc00371e358beb5dTanya Lattner if (isLoopInvariant(I.getOperand(0)) && isLoopInvariant(I.getOperand(1)) && SafeToHoist(I)) 143e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner hoist(I); 144e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } 1459b2b80fd48b10396be85a71735ffda0c155e5f72Chris Lattner void visitCastInst(CastInst &CI) { 1469b2b80fd48b10396be85a71735ffda0c155e5f72Chris Lattner Instruction &I = (Instruction&)CI; 1479966c03aad031f738718bed3bc00371e358beb5dTanya Lattner if (isLoopInvariant(I.getOperand(0)) && SafeToHoist(CI)) hoist(I); 1480513e9fe03f6e3c7d0272b8f4f82359e8d1a2e44Chris Lattner } 1497e70829632f82de15db187845666aaca6e04b792Chris Lattner void visitShiftInst(ShiftInst &I) { visitBinaryOperator((Instruction&)I); } 150e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 151eb53ae4f2dc39e75e725b21b52d77d29cf1c11c9Chris Lattner void visitLoadInst(LoadInst &LI); 152f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner 1537e70829632f82de15db187845666aaca6e04b792Chris Lattner void visitGetElementPtrInst(GetElementPtrInst &GEPI) { 1547e70829632f82de15db187845666aaca6e04b792Chris Lattner Instruction &I = (Instruction&)GEPI; 1557e70829632f82de15db187845666aaca6e04b792Chris Lattner for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) 1567e70829632f82de15db187845666aaca6e04b792Chris Lattner if (!isLoopInvariant(I.getOperand(i))) return; 1579966c03aad031f738718bed3bc00371e358beb5dTanya Lattner if(SafeToHoist(GEPI)) 1589966c03aad031f738718bed3bc00371e358beb5dTanya Lattner hoist(I); 159e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } 160e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner }; 161f629309f74cf1a64aa7fd1cd5784fd7db9a8f59eChris Lattner 162a6275ccdf5e1aa208afde56c498e2b13e16442f0Chris Lattner RegisterOpt<LICM> X("licm", "Loop Invariant Code Motion"); 163e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner} 164e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 165e0e734eea052a4e8372e6f430ef41149128ba0a6Chris LattnerPass *createLICMPass() { return new LICM(); } 166e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 16794170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// runOnFunction - For LICM, this simply traverses the loop structure of the 16894170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// function, hoisting expressions out of loops if possible. 16994170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// 1707e70829632f82de15db187845666aaca6e04b792Chris Lattnerbool LICM::runOnFunction(Function &) { 1712e6e741b737960ecd0b68610875050019aac0f07Chris Lattner Changed = false; 172e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 1732e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Get our Loop and Alias Analysis information... 1742e6e741b737960ecd0b68610875050019aac0f07Chris Lattner LI = &getAnalysis<LoopInfo>(); 175f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner AA = &getAnalysis<AliasAnalysis>(); 176f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner 1772e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Hoist expressions out of all of the top-level loops. 1782e6e741b737960ecd0b68610875050019aac0f07Chris Lattner const std::vector<Loop*> &TopLevelLoops = LI->getTopLevelLoops(); 1792e6e741b737960ecd0b68610875050019aac0f07Chris Lattner for (std::vector<Loop*>::const_iterator I = TopLevelLoops.begin(), 1802e6e741b737960ecd0b68610875050019aac0f07Chris Lattner E = TopLevelLoops.end(); I != E; ++I) { 1810252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner AliasSetTracker AST(*AA); 1820252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner LICM::visitLoop(*I, AST); 1832e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 184e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner return Changed; 185e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner} 186e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 18794170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner 18894170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// visitLoop - Hoist expressions out of the specified loop... 18994170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// 1900252e49f6d6973b6f347c8feafc49e28af27163aChris Lattnervoid LICM::visitLoop(Loop *L, AliasSetTracker &AST) { 191e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Recurse through all subloops before we process this loop... 1922e6e741b737960ecd0b68610875050019aac0f07Chris Lattner for (std::vector<Loop*>::const_iterator I = L->getSubLoops().begin(), 1932e6e741b737960ecd0b68610875050019aac0f07Chris Lattner E = L->getSubLoops().end(); I != E; ++I) { 1940252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner AliasSetTracker SubAST(*AA); 1950252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner LICM::visitLoop(*I, SubAST); 1962e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 1972e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Incorporate information about the subloops into this loop... 1980252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner AST.add(SubAST); 1992e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 200e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner CurLoop = L; 2010252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner CurAST = &AST; 202e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 20399a57216a935a512c418032f590a4660bad9d846Chris Lattner // Get the preheader block to move instructions into... 20499a57216a935a512c418032f590a4660bad9d846Chris Lattner Preheader = L->getLoopPreheader(); 20599a57216a935a512c418032f590a4660bad9d846Chris Lattner assert(Preheader&&"Preheader insertion pass guarantees we have a preheader!"); 20699a57216a935a512c418032f590a4660bad9d846Chris Lattner 2072e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Loop over the body of this loop, looking for calls, invokes, and stores. 2080252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner // Because subloops have already been incorporated into AST, we skip blocks in 2092e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // subloops. 2102e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // 2112e6e741b737960ecd0b68610875050019aac0f07Chris Lattner const std::vector<BasicBlock*> &LoopBBs = L->getBlocks(); 2122e6e741b737960ecd0b68610875050019aac0f07Chris Lattner for (std::vector<BasicBlock*>::const_iterator I = LoopBBs.begin(), 2132e6e741b737960ecd0b68610875050019aac0f07Chris Lattner E = LoopBBs.end(); I != E; ++I) 2142e6e741b737960ecd0b68610875050019aac0f07Chris Lattner if (LI->getLoopFor(*I) == L) // Ignore blocks in subloops... 2150252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner AST.add(**I); // Incorporate the specified basic block 2162e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 217e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // We want to visit all of the instructions in this loop... that are not parts 218e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // of our subloops (they have already had their invariants hoisted out of 219e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // their loop, into this loop, so there is no need to process the BODIES of 220e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // the subloops). 221e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // 222952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner // Traverse the body of the loop in depth first order on the dominator tree so 223952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner // that we are guaranteed to see definitions before we see uses. This allows 224952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner // us to perform the LICM transformation in one pass, without iteration. 225952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner // 2269966c03aad031f738718bed3bc00371e358beb5dTanya Lattner CurDT = &getAnalysis<DominatorTree>(); 2279966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 2289966c03aad031f738718bed3bc00371e358beb5dTanya Lattner HoistRegion(CurDT->getNode(L->getHeader())); 229e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 2302e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Now that all loop invariants have been removed from the loop, promote any 2312e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // memory references to scalars that we can... 2322e6e741b737960ecd0b68610875050019aac0f07Chris Lattner if (!DisablePromotion) 2332e6e741b737960ecd0b68610875050019aac0f07Chris Lattner PromoteValuesInLoop(); 2342e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 235e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Clear out loops state information for the next iteration 236e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner CurLoop = 0; 23799a57216a935a512c418032f590a4660bad9d846Chris Lattner Preheader = 0; 238e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner} 239e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 240952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner/// HoistRegion - Walk the specified region of the CFG (defined by all blocks 241952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner/// dominated by the specified block, and that are in the current loop) in depth 242952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner/// first order w.r.t the DominatorTree. This allows us to visit defintions 243952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner/// before uses, allowing us to hoist a loop body in one pass without iteration. 244952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner/// 245952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattnervoid LICM::HoistRegion(DominatorTree::Node *N) { 246952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner assert(N != 0 && "Null dominator tree node?"); 247952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 248b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner // If this subregion is not in the top level loop at all, exit. 249b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner if (!CurLoop->contains(N->getNode())) return; 250952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 251b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner // Only need to hoist the contents of this block if it is not part of a 252b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner // subloop (which would already have been hoisted) 253b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner if (!inSubLoop(N->getNode())) 254b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner visit(*N->getNode()); 255952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 256952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner const std::vector<DominatorTree::Node*> &Children = N->getChildren(); 257952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner for (unsigned i = 0, e = Children.size(); i != e; ++i) 258952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner HoistRegion(Children[i]); 259952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner} 260952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 261952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 26294170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// hoist - When an instruction is found to only use loop invariant operands 26394170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// that is safe to hoist, this instruction is called to do the dirty work. 26494170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// 2657e70829632f82de15db187845666aaca6e04b792Chris Lattnervoid LICM::hoist(Instruction &Inst) { 266b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner DEBUG(std::cerr << "LICM hoisting to"; 267b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner WriteAsOperand(std::cerr, Preheader, false); 268b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner std::cerr << ": " << Inst); 269e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 27099a57216a935a512c418032f590a4660bad9d846Chris Lattner // Remove the instruction from its current basic block... but don't delete the 27199a57216a935a512c418032f590a4660bad9d846Chris Lattner // instruction. 27299a57216a935a512c418032f590a4660bad9d846Chris Lattner Inst.getParent()->getInstList().remove(&Inst); 273e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 2749646e6b6af1f924f9366a2bffc6dde102f84d231Chris Lattner // Insert the new node in Preheader, before the terminator. 27599a57216a935a512c418032f590a4660bad9d846Chris Lattner Preheader->getInstList().insert(Preheader->getTerminator(), &Inst); 2769646e6b6af1f924f9366a2bffc6dde102f84d231Chris Lattner 2779646e6b6af1f924f9366a2bffc6dde102f84d231Chris Lattner ++NumHoisted; 278e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner Changed = true; 279e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner} 280e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 2819966c03aad031f738718bed3bc00371e358beb5dTanya Lattner/// SafeToHoist - Only hoist an instruction if it is not a trapping instruction 2829966c03aad031f738718bed3bc00371e358beb5dTanya Lattner/// or if it is a trapping instruction and is guaranteed to execute 2839966c03aad031f738718bed3bc00371e358beb5dTanya Lattner/// 2849966c03aad031f738718bed3bc00371e358beb5dTanya Lattnerbool LICM::SafeToHoist(Instruction &Inst) { 2859966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 2869966c03aad031f738718bed3bc00371e358beb5dTanya Lattner //If it is a trapping instruction, then check if its guaranteed to execute. 2879966c03aad031f738718bed3bc00371e358beb5dTanya Lattner if(Inst.isTrapping()) { 2889966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 2899966c03aad031f738718bed3bc00371e358beb5dTanya Lattner //Get the instruction's basic block. 2909966c03aad031f738718bed3bc00371e358beb5dTanya Lattner BasicBlock *InstBB = Inst.getParent(); 2919966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 2929966c03aad031f738718bed3bc00371e358beb5dTanya Lattner //Get the Dominator Tree Node for the instruction's basic block/ 2939966c03aad031f738718bed3bc00371e358beb5dTanya Lattner DominatorTree::Node *InstDTNode = CurDT->getNode(InstBB); 2949966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 2959966c03aad031f738718bed3bc00371e358beb5dTanya Lattner //Get the exit blocks for the current loop. 2969966c03aad031f738718bed3bc00371e358beb5dTanya Lattner const std::vector<BasicBlock* > ExitBlocks = CurLoop->getExitBlocks(); 2979966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 2989966c03aad031f738718bed3bc00371e358beb5dTanya Lattner //For each exit block, get the DT node and walk up the DT until 2999966c03aad031f738718bed3bc00371e358beb5dTanya Lattner //the instruction's basic block is found or we exit the loop. 3009966c03aad031f738718bed3bc00371e358beb5dTanya Lattner for(unsigned i=0; i < ExitBlocks.size(); ++i) { 3019966c03aad031f738718bed3bc00371e358beb5dTanya Lattner DominatorTree::Node *IDom = CurDT->getNode(ExitBlocks[i]); 3029966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 3039966c03aad031f738718bed3bc00371e358beb5dTanya Lattner //Using boolean variable because exit nodes are not "contained" 3049966c03aad031f738718bed3bc00371e358beb5dTanya Lattner //in the loop, so can not use that as the while test condition 3059966c03aad031f738718bed3bc00371e358beb5dTanya Lattner //for first pass. 3069966c03aad031f738718bed3bc00371e358beb5dTanya Lattner bool inLoop = true; 3079966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 3089966c03aad031f738718bed3bc00371e358beb5dTanya Lattner while(inLoop) { 3099966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 3109966c03aad031f738718bed3bc00371e358beb5dTanya Lattner //compare Instruction DT node to Current DT Node 3119966c03aad031f738718bed3bc00371e358beb5dTanya Lattner if(IDom == InstDTNode) 3129966c03aad031f738718bed3bc00371e358beb5dTanya Lattner return true; 3139966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 3149966c03aad031f738718bed3bc00371e358beb5dTanya Lattner //Get next Immediate Dominator. 3159966c03aad031f738718bed3bc00371e358beb5dTanya Lattner IDom = IDom->getIDom(); 3169966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 3179966c03aad031f738718bed3bc00371e358beb5dTanya Lattner //See if we exited the loop. 3189966c03aad031f738718bed3bc00371e358beb5dTanya Lattner inLoop = CurLoop->contains(IDom->getNode()); 3199966c03aad031f738718bed3bc00371e358beb5dTanya Lattner } 3209966c03aad031f738718bed3bc00371e358beb5dTanya Lattner return false; 3219966c03aad031f738718bed3bc00371e358beb5dTanya Lattner } 3229966c03aad031f738718bed3bc00371e358beb5dTanya Lattner } 3239966c03aad031f738718bed3bc00371e358beb5dTanya Lattner return true; 3249966c03aad031f738718bed3bc00371e358beb5dTanya Lattner} 3259966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 326eb53ae4f2dc39e75e725b21b52d77d29cf1c11c9Chris Lattner 327eb53ae4f2dc39e75e725b21b52d77d29cf1c11c9Chris Lattnervoid LICM::visitLoadInst(LoadInst &LI) { 328eb53ae4f2dc39e75e725b21b52d77d29cf1c11c9Chris Lattner if (isLoopInvariant(LI.getOperand(0)) && 3299966c03aad031f738718bed3bc00371e358beb5dTanya Lattner !pointerInvalidatedByLoop(LI.getOperand(0)) && SafeToHoist(LI)) { 330eb53ae4f2dc39e75e725b21b52d77d29cf1c11c9Chris Lattner hoist(LI); 33199a57216a935a512c418032f590a4660bad9d846Chris Lattner ++NumHoistedLoads; 33299a57216a935a512c418032f590a4660bad9d846Chris Lattner } 333eb53ae4f2dc39e75e725b21b52d77d29cf1c11c9Chris Lattner} 334eb53ae4f2dc39e75e725b21b52d77d29cf1c11c9Chris Lattner 3352e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// PromoteValuesInLoop - Try to promote memory values to scalars by sinking 3362e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// stores out of the loop and moving loads to before the loop. We do this by 3372e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// looping over the stores in the loop, looking for stores to Must pointers 3382e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// which are loop invariant. We promote these memory locations to use allocas 3392e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// instead. These allocas can easily be raised to register values by the 3402e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// PromoteMem2Reg functionality. 3412e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// 3422e6e741b737960ecd0b68610875050019aac0f07Chris Lattnervoid LICM::PromoteValuesInLoop() { 3432e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // PromotedValues - List of values that are promoted out of the loop. Each 3442e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // value has an alloca instruction for it, and a cannonical version of the 3452e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // pointer. 3462e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::vector<std::pair<AllocaInst*, Value*> > PromotedValues; 3472e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::map<Value*, AllocaInst*> ValueToAllocaMap; // Map of ptr to alloca 3482e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 3492e6e741b737960ecd0b68610875050019aac0f07Chris Lattner findPromotableValuesInLoop(PromotedValues, ValueToAllocaMap); 3502e6e741b737960ecd0b68610875050019aac0f07Chris Lattner if (ValueToAllocaMap.empty()) return; // If there are values to promote... 3512e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 3522e6e741b737960ecd0b68610875050019aac0f07Chris Lattner Changed = true; 3532e6e741b737960ecd0b68610875050019aac0f07Chris Lattner NumPromoted += PromotedValues.size(); 3542e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 3552e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Emit a copy from the value into the alloca'd value in the loop preheader 3562e6e741b737960ecd0b68610875050019aac0f07Chris Lattner TerminatorInst *LoopPredInst = Preheader->getTerminator(); 3572e6e741b737960ecd0b68610875050019aac0f07Chris Lattner for (unsigned i = 0, e = PromotedValues.size(); i != e; ++i) { 3582e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Load from the memory we are promoting... 3592e6e741b737960ecd0b68610875050019aac0f07Chris Lattner LoadInst *LI = new LoadInst(PromotedValues[i].second, 3602e6e741b737960ecd0b68610875050019aac0f07Chris Lattner PromotedValues[i].second->getName()+".promoted", 3612e6e741b737960ecd0b68610875050019aac0f07Chris Lattner LoopPredInst); 3622e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Store into the temporary alloca... 3632e6e741b737960ecd0b68610875050019aac0f07Chris Lattner new StoreInst(LI, PromotedValues[i].first, LoopPredInst); 3642e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 3652e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 3662e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Scan the basic blocks in the loop, replacing uses of our pointers with 3672e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // uses of the allocas in question. If we find a branch that exits the 3682e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // loop, make sure to put reload code into all of the successors of the 3692e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // loop. 3702e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // 3712e6e741b737960ecd0b68610875050019aac0f07Chris Lattner const std::vector<BasicBlock*> &LoopBBs = CurLoop->getBlocks(); 3722e6e741b737960ecd0b68610875050019aac0f07Chris Lattner for (std::vector<BasicBlock*>::const_iterator I = LoopBBs.begin(), 3732e6e741b737960ecd0b68610875050019aac0f07Chris Lattner E = LoopBBs.end(); I != E; ++I) { 3742e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Rewrite all loads and stores in the block of the pointer... 3752e6e741b737960ecd0b68610875050019aac0f07Chris Lattner for (BasicBlock::iterator II = (*I)->begin(), E = (*I)->end(); 3762e6e741b737960ecd0b68610875050019aac0f07Chris Lattner II != E; ++II) { 377e408e25132b8de8c757db1e3ddcd70432dfeb24dChris Lattner if (LoadInst *L = dyn_cast<LoadInst>(II)) { 3782e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::map<Value*, AllocaInst*>::iterator 3792e6e741b737960ecd0b68610875050019aac0f07Chris Lattner I = ValueToAllocaMap.find(L->getOperand(0)); 3802e6e741b737960ecd0b68610875050019aac0f07Chris Lattner if (I != ValueToAllocaMap.end()) 3812e6e741b737960ecd0b68610875050019aac0f07Chris Lattner L->setOperand(0, I->second); // Rewrite load instruction... 382e408e25132b8de8c757db1e3ddcd70432dfeb24dChris Lattner } else if (StoreInst *S = dyn_cast<StoreInst>(II)) { 3832e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::map<Value*, AllocaInst*>::iterator 3842e6e741b737960ecd0b68610875050019aac0f07Chris Lattner I = ValueToAllocaMap.find(S->getOperand(1)); 3852e6e741b737960ecd0b68610875050019aac0f07Chris Lattner if (I != ValueToAllocaMap.end()) 3862e6e741b737960ecd0b68610875050019aac0f07Chris Lattner S->setOperand(1, I->second); // Rewrite store instruction... 3872e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 3882e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 3892e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 3902e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Check to see if any successors of this block are outside of the loop. 3912e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // If so, we need to copy the value from the alloca back into the memory 3922e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // location... 3932e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // 3942e6e741b737960ecd0b68610875050019aac0f07Chris Lattner for (succ_iterator SI = succ_begin(*I), SE = succ_end(*I); SI != SE; ++SI) 3952e6e741b737960ecd0b68610875050019aac0f07Chris Lattner if (!CurLoop->contains(*SI)) { 3962e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Copy all of the allocas into their memory locations... 3978601a9bf54049389e0e0b6a907dc51069dcadc60Chris Lattner BasicBlock::iterator BI = (*SI)->begin(); 3988601a9bf54049389e0e0b6a907dc51069dcadc60Chris Lattner while (isa<PHINode>(*BI)) 3998601a9bf54049389e0e0b6a907dc51069dcadc60Chris Lattner ++BI; // Skip over all of the phi nodes in the block... 4008601a9bf54049389e0e0b6a907dc51069dcadc60Chris Lattner Instruction *InsertPos = BI; 4012e6e741b737960ecd0b68610875050019aac0f07Chris Lattner for (unsigned i = 0, e = PromotedValues.size(); i != e; ++i) { 4022e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Load from the alloca... 4032e6e741b737960ecd0b68610875050019aac0f07Chris Lattner LoadInst *LI = new LoadInst(PromotedValues[i].first, "", InsertPos); 4042e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Store into the memory we promoted... 4052e6e741b737960ecd0b68610875050019aac0f07Chris Lattner new StoreInst(LI, PromotedValues[i].second, InsertPos); 4062e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 4072e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 4082e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 4092e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 4102e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Now that we have done the deed, use the mem2reg functionality to promote 4112e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // all of the new allocas we just created into real SSA registers... 4122e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // 4132e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::vector<AllocaInst*> PromotedAllocas; 4142e6e741b737960ecd0b68610875050019aac0f07Chris Lattner PromotedAllocas.reserve(PromotedValues.size()); 4152e6e741b737960ecd0b68610875050019aac0f07Chris Lattner for (unsigned i = 0, e = PromotedValues.size(); i != e; ++i) 4162e6e741b737960ecd0b68610875050019aac0f07Chris Lattner PromotedAllocas.push_back(PromotedValues[i].first); 417fb743a937f6856e3ab1f8ed599677038750a550eChris Lattner PromoteMemToReg(PromotedAllocas, getAnalysis<DominanceFrontier>(), 418fb743a937f6856e3ab1f8ed599677038750a550eChris Lattner AA->getTargetData()); 4192e6e741b737960ecd0b68610875050019aac0f07Chris Lattner} 4202e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 4212e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// findPromotableValuesInLoop - Check the current loop for stores to definate 4222e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// pointers, which are not loaded and stored through may aliases. If these are 4232e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// found, create an alloca for the value, add it to the PromotedValues list, 4242e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// and keep track of the mapping from value to alloca... 4252e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// 4262e6e741b737960ecd0b68610875050019aac0f07Chris Lattnervoid LICM::findPromotableValuesInLoop( 4272e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::vector<std::pair<AllocaInst*, Value*> > &PromotedValues, 4282e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::map<Value*, AllocaInst*> &ValueToAllocaMap) { 4292e6e741b737960ecd0b68610875050019aac0f07Chris Lattner Instruction *FnStart = CurLoop->getHeader()->getParent()->begin()->begin(); 4302e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 4310252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner // Loop over all of the alias sets in the tracker object... 4320252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); 4330252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner I != E; ++I) { 4340252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner AliasSet &AS = *I; 4350252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner // We can promote this alias set if it has a store, if it is a "Must" alias 4360252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner // set, and if the pointer is loop invariant. 4370252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner if (!AS.isForwardingAliasSet() && AS.isMod() && AS.isMustAlias() && 4380252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner isLoopInvariant(AS.begin()->first)) { 4390252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner assert(AS.begin() != AS.end() && 4400252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner "Must alias set should have at least one pointer element in it!"); 4410252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner Value *V = AS.begin()->first; 4420252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner 4430252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner // Check that all of the pointers in the alias set have the same type. We 4440252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner // cannot (yet) promote a memory location that is loaded and stored in 4450252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner // different sizes. 4460252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner bool PointerOk = true; 4470252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I) 4480252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner if (V->getType() != I->first->getType()) { 4490252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner PointerOk = false; 4500252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner break; 4512e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 4520252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner 4530252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner if (PointerOk) { 4540252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner const Type *Ty = cast<PointerType>(V->getType())->getElementType(); 4550252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner AllocaInst *AI = new AllocaInst(Ty, 0, V->getName()+".tmp", FnStart); 4560252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner PromotedValues.push_back(std::make_pair(AI, V)); 4570252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner 4580252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I) 4590252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner ValueToAllocaMap.insert(std::make_pair(I->first, AI)); 4600252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner 4610252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner DEBUG(std::cerr << "LICM: Promoting value: " << *V << "\n"); 4622e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 4632e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 4642e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 465f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner} 466