LICM.cpp revision e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0
1e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner//===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner// 1092094b4d928119eceac1484331acffe950f4651cChris Lattner// This pass performs loop invariant code motion, attempting to remove as much 1192094b4d928119eceac1484331acffe950f4651cChris Lattner// code from the body of a loop as possible. It does this by either hoisting 1292094b4d928119eceac1484331acffe950f4651cChris Lattner// code into the preheader block, or by sinking code to the exit blocks if it is 1392094b4d928119eceac1484331acffe950f4651cChris Lattner// safe. This pass also promotes must-aliased memory locations in the loop to 14e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner// live in registers, thus hoisting and sinking "invariant" loads and stores. 1592094b4d928119eceac1484331acffe950f4651cChris Lattner// 1692094b4d928119eceac1484331acffe950f4651cChris Lattner// This pass uses alias analysis for two purposes: 172e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// 182741c971044d2165be572749b94398043caccfebChris Lattner// 1. Moving loop invariant loads and calls out of loops. If we can determine 192741c971044d2165be572749b94398043caccfebChris Lattner// that a load or call inside of a loop never aliases anything stored to, 202741c971044d2165be572749b94398043caccfebChris Lattner// we can hoist it or sink it like any other instruction. 212e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// 2. Scalar Promotion of Memory - If there is a store instruction inside of 222e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// the loop, we try to move the store to happen AFTER the loop instead of 232e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// inside of the loop. This can only happen if a few conditions are true: 242e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// A. The pointer stored through is loop invariant 252e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// B. There are no stores or loads in the loop which _may_ alias the 262e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// pointer. There are no calls in the loop which mod/ref the pointer. 272e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// If these conditions are true, we can promote the loads and stores in the 282e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// loop of the pointer to use a temporary alloca'd variable. We then use 29e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner// the SSAUpdater to construct the appropriate SSA form for the value. 30e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner// 31e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner//===----------------------------------------------------------------------===// 32e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 331f309c1a4e8068a64627c612a895d9b403dbcb26Chris Lattner#define DEBUG_TYPE "licm" 34e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include "llvm/Transforms/Scalar.h" 3579066fa6acce02c97c714a5a6e151ed8a249721cChris Lattner#include "llvm/Constants.h" 362741c971044d2165be572749b94398043caccfebChris Lattner#include "llvm/DerivedTypes.h" 379289ae85b41eef62ae1fadb93e99d33f723fb682Torok Edwin#include "llvm/IntrinsicInst.h" 382741c971044d2165be572749b94398043caccfebChris Lattner#include "llvm/Instructions.h" 392741c971044d2165be572749b94398043caccfebChris Lattner#include "llvm/Target/TargetData.h" 40e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include "llvm/Analysis/LoopInfo.h" 4154959d6cf68a9b575c98c074babe9867682a7271Devang Patel#include "llvm/Analysis/LoopPass.h" 42f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner#include "llvm/Analysis/AliasAnalysis.h" 430252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner#include "llvm/Analysis/AliasSetTracker.h" 44952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner#include "llvm/Analysis/Dominators.h" 4596b651c627160e1ea0f1bb86d352d697e6c1972dDevang Patel#include "llvm/Analysis/ScalarEvolution.h" 46a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner#include "llvm/Transforms/Utils/SSAUpdater.h" 479133fe28954d498fc4de13064c7d65bd811de02cReid Spencer#include "llvm/Support/CFG.h" 48551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 49ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar#include "llvm/Support/raw_ostream.h" 50551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 51551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 52e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include <algorithm> 5392094b4d928119eceac1484331acffe950f4651cChris Lattnerusing namespace llvm; 54d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 550e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumSunk , "Number of instructions sunk out of loop"); 560e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumHoisted , "Number of instructions hoisted out of loop"); 570e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk"); 580e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk"); 590e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumPromoted , "Number of memory locations promoted to registers"); 600e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattner 61844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> 62844731a7f1909f55935e3514c9e713a62d67662eDan GohmanDisablePromotion("disable-licm-promotion", cl::Hidden, 63844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::desc("Disable memory promotion in LICM pass")); 642e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 65844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 663e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner struct LICM : public LoopPass { 67ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 6890c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson LICM() : LoopPass(ID) {} 69794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 7054959d6cf68a9b575c98c074babe9867682a7271Devang Patel virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 71e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 7294170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// This transformation requires natural loop information & requires that 7394170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// loop preheaders be inserted into the CFG... 7494170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// 75e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 76cb2610ea037a17115ef3a01a6bdaab4e3cfdca27Chris Lattner AU.setPreservesCFG(); 773a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson AU.addRequired<DominatorTree>(); 780252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner AU.addRequired<DominanceFrontier>(); // For scalar promotion (mem2reg) 791e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman AU.addRequired<LoopInfo>(); 801e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman AU.addRequiredID(LoopSimplifyID); 81f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner AU.addRequired<AliasAnalysis>(); 8296b651c627160e1ea0f1bb86d352d697e6c1972dDevang Patel AU.addPreserved<ScalarEvolution>(); 8396b651c627160e1ea0f1bb86d352d697e6c1972dDevang Patel AU.addPreserved<DominanceFrontier>(); 845c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman AU.addPreservedID(LoopSimplifyID); 85e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } 86e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 87747603e39ea3f29add9ba6c07bbefcc5c2432612Dan Gohman bool doFinalization() { 88fd94dd58ffef1be3597ef8cb64f3b1d476d7d5ecAnton Korobeynikov // Free the values stored in the map 89fd94dd58ffef1be3597ef8cb64f3b1d476d7d5ecAnton Korobeynikov for (std::map<Loop *, AliasSetTracker *>::iterator 90fd94dd58ffef1be3597ef8cb64f3b1d476d7d5ecAnton Korobeynikov I = LoopToAliasMap.begin(), E = LoopToAliasMap.end(); I != E; ++I) 91fd94dd58ffef1be3597ef8cb64f3b1d476d7d5ecAnton Korobeynikov delete I->second; 92fd94dd58ffef1be3597ef8cb64f3b1d476d7d5ecAnton Korobeynikov 9354959d6cf68a9b575c98c074babe9867682a7271Devang Patel LoopToAliasMap.clear(); 9454959d6cf68a9b575c98c074babe9867682a7271Devang Patel return false; 9554959d6cf68a9b575c98c074babe9867682a7271Devang Patel } 9654959d6cf68a9b575c98c074babe9867682a7271Devang Patel 97e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner private: 9892094b4d928119eceac1484331acffe950f4651cChris Lattner // Various analyses that we use... 992e6e741b737960ecd0b68610875050019aac0f07Chris Lattner AliasAnalysis *AA; // Current AliasAnalysis information 10092094b4d928119eceac1484331acffe950f4651cChris Lattner LoopInfo *LI; // Current LoopInfo 1013a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson DominatorTree *DT; // Dominator Tree for the current Loop... 10243f820d1f7638656be2158efac7dd8f5b08b8b77Chris Lattner DominanceFrontier *DF; // Current Dominance Frontier 10392094b4d928119eceac1484331acffe950f4651cChris Lattner 10492094b4d928119eceac1484331acffe950f4651cChris Lattner // State that is updated as we process loops 1052e6e741b737960ecd0b68610875050019aac0f07Chris Lattner bool Changed; // Set to true when we change anything. 1062e6e741b737960ecd0b68610875050019aac0f07Chris Lattner BasicBlock *Preheader; // The preheader block of the current loop... 1072e6e741b737960ecd0b68610875050019aac0f07Chris Lattner Loop *CurLoop; // The current loop we are working on... 1080252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner AliasSetTracker *CurAST; // AliasSet information for the current loop... 10954959d6cf68a9b575c98c074babe9867682a7271Devang Patel std::map<Loop *, AliasSetTracker *> LoopToAliasMap; 110e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 11191d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info. 11291d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel void cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L); 11391d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel 11491d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel /// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias 11591d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel /// set. 11691d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel void deleteAnalysisValue(Value *V, Loop *L); 11791d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel 118e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner /// SinkRegion - Walk the specified region of the CFG (defined by all blocks 119e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner /// dominated by the specified block, and that are in the current loop) in 1203a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson /// reverse depth first order w.r.t the DominatorTree. This allows us to 121e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner /// visit uses before definitions, allowing us to sink a loop body in one 122e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner /// pass without iteration. 123e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner /// 12426042420d642e810f5cdfb2da6156b74aaf80945Devang Patel void SinkRegion(DomTreeNode *N); 125e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 126952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// HoistRegion - Walk the specified region of the CFG (defined by all 127952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// blocks dominated by the specified block, and that are in the current 1283a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson /// loop) in depth first order w.r.t the DominatorTree. This allows us to 129cf00c4ab3ba308d45d98c5ccab87362cf802facbMisha Brukman /// visit definitions before uses, allowing us to hoist a loop body in one 130952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// pass without iteration. 131952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// 13226042420d642e810f5cdfb2da6156b74aaf80945Devang Patel void HoistRegion(DomTreeNode *N); 133952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 134b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner /// inSubLoop - Little predicate that returns true if the specified basic 135b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner /// block is in a subloop of the current one, not the current one itself. 13694170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// 137b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner bool inSubLoop(BasicBlock *BB) { 138b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop"); 139329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner for (Loop::iterator I = CurLoop->begin(), E = CurLoop->end(); I != E; ++I) 140329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner if ((*I)->contains(BB)) 141b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner return true; // A subloop actually contains this block! 142b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner return false; 143e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } 144e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 145a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// isExitBlockDominatedByBlockInLoop - This method checks to see if the 146a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// specified exit block of the loop is dominated by the specified block 147a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// that is in the body of the loop. We use these constraints to 148a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// dramatically limit the amount of the dominator tree that needs to be 149a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// searched. 150a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner bool isExitBlockDominatedByBlockInLoop(BasicBlock *ExitBlock, 151a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner BasicBlock *BlockInLoop) const { 152a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // If the block in the loop is the loop header, it must be dominated! 153a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner BasicBlock *LoopHeader = CurLoop->getHeader(); 154a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (BlockInLoop == LoopHeader) 155a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return true; 156fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 15726042420d642e810f5cdfb2da6156b74aaf80945Devang Patel DomTreeNode *BlockInLoopNode = DT->getNode(BlockInLoop); 15826042420d642e810f5cdfb2da6156b74aaf80945Devang Patel DomTreeNode *IDom = DT->getNode(ExitBlock); 159fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 160a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Because the exit block is not in the loop, we know we have to get _at 1612741c971044d2165be572749b94398043caccfebChris Lattner // least_ its immediate dominator. 1623472ae1e7b0f38c4ac0802ffc2900f71a5470c3bEric Christopher IDom = IDom->getIDom(); 1633472ae1e7b0f38c4ac0802ffc2900f71a5470c3bEric Christopher 1643472ae1e7b0f38c4ac0802ffc2900f71a5470c3bEric Christopher while (IDom && IDom != BlockInLoopNode) { 165a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // If we have got to the header of the loop, then the instructions block 166a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // did not dominate the exit node, so we can't hoist it. 1673a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson if (IDom->getBlock() == LoopHeader) 168a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return false; 169fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1703472ae1e7b0f38c4ac0802ffc2900f71a5470c3bEric Christopher // Get next Immediate Dominator. 1713472ae1e7b0f38c4ac0802ffc2900f71a5470c3bEric Christopher IDom = IDom->getIDom(); 1723472ae1e7b0f38c4ac0802ffc2900f71a5470c3bEric Christopher }; 173a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 174a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return true; 175a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 176a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 177a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// sink - When an instruction is found to only be used outside of the loop, 178a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// this function moves it to the exit blocks and patches up SSA form as 179a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// needed. 180a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// 181a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner void sink(Instruction &I); 182a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 18394170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// hoist - When an instruction is found to only use loop invariant operands 18494170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// that is safe to hoist, this instruction is called to do the dirty work. 18594170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// 1867e70829632f82de15db187845666aaca6e04b792Chris Lattner void hoist(Instruction &I); 187e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 188a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// isSafeToExecuteUnconditionally - Only sink or hoist an instruction if it 189a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// is not a trapping instruction or if it is a trapping instruction and is 190a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// guaranteed to execute. 1919966c03aad031f738718bed3bc00371e358beb5dTanya Lattner /// 192a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner bool isSafeToExecuteUnconditionally(Instruction &I); 1939966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 19494170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// pointerInvalidatedByLoop - Return true if the body of this loop may 19594170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// store into the memory location pointed to by V. 196fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman /// 197f3e1d6977ee5fb6b66df314d65e28e2c35d6e244Chris Lattner bool pointerInvalidatedByLoop(Value *V, unsigned Size) { 1980252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner // Check to see if any of the basic blocks in CurLoop invalidate *V. 199f3e1d6977ee5fb6b66df314d65e28e2c35d6e244Chris Lattner return CurAST->getAliasSetForPointer(V, Size).isMod(); 2002e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 201f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner 202a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner bool canSinkOrHoistInst(Instruction &I); 203a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner bool isLoopInvariantInst(Instruction &I); 204a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner bool isNotUsedInLoop(Instruction &I); 205e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 206e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner void PromoteAliasSet(AliasSet &AS); 207e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner }; 208e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner} 209e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 210844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar LICM::ID = 0; 211d13db2c59cc94162d6cf0a04187d408bfef6d4a7Owen AndersonINITIALIZE_PASS(LICM, "licm", "Loop Invariant Code Motion", false, false); 212844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 213394f0441e06dafca29f0752cf400990a5b8fe4b1Daniel DunbarPass *llvm::createLICMPass() { return new LICM(); } 214e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 2158d246f09cb46fe38aa71d2a4edcd84f30c4bf80eDevang Patel/// Hoist expressions out of the specified loop. Note, alias info for inner 2168d246f09cb46fe38aa71d2a4edcd84f30c4bf80eDevang Patel/// loop is not preserved so it is not a good idea to run LICM multiple 2178d246f09cb46fe38aa71d2a4edcd84f30c4bf80eDevang Patel/// times on one loop. 21894170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// 21954959d6cf68a9b575c98c074babe9867682a7271Devang Patelbool LICM::runOnLoop(Loop *L, LPPassManager &LPM) { 2202e6e741b737960ecd0b68610875050019aac0f07Chris Lattner Changed = false; 221e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 2222e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Get our Loop and Alias Analysis information... 2232e6e741b737960ecd0b68610875050019aac0f07Chris Lattner LI = &getAnalysis<LoopInfo>(); 224f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner AA = &getAnalysis<AliasAnalysis>(); 22543f820d1f7638656be2158efac7dd8f5b08b8b77Chris Lattner DF = &getAnalysis<DominanceFrontier>(); 2263a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson DT = &getAnalysis<DominatorTree>(); 227f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner 22854959d6cf68a9b575c98c074babe9867682a7271Devang Patel CurAST = new AliasSetTracker(*AA); 229f38ac5dd390ca583b6e6d1b40b378d07e49e5097Devang Patel // Collect Alias info from subloops 23054959d6cf68a9b575c98c074babe9867682a7271Devang Patel for (Loop::iterator LoopItr = L->begin(), LoopItrE = L->end(); 23154959d6cf68a9b575c98c074babe9867682a7271Devang Patel LoopItr != LoopItrE; ++LoopItr) { 23254959d6cf68a9b575c98c074babe9867682a7271Devang Patel Loop *InnerL = *LoopItr; 23354959d6cf68a9b575c98c074babe9867682a7271Devang Patel AliasSetTracker *InnerAST = LoopToAliasMap[InnerL]; 23454959d6cf68a9b575c98c074babe9867682a7271Devang Patel assert (InnerAST && "Where is my AST?"); 23594170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner 23654959d6cf68a9b575c98c074babe9867682a7271Devang Patel // What if InnerLoop was modified by other passes ? 23754959d6cf68a9b575c98c074babe9867682a7271Devang Patel CurAST->add(*InnerAST); 2382e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 23954959d6cf68a9b575c98c074babe9867682a7271Devang Patel 240e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner CurLoop = L; 241e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 24299a57216a935a512c418032f590a4660bad9d846Chris Lattner // Get the preheader block to move instructions into... 24399a57216a935a512c418032f590a4660bad9d846Chris Lattner Preheader = L->getLoopPreheader(); 24499a57216a935a512c418032f590a4660bad9d846Chris Lattner 2452e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Loop over the body of this loop, looking for calls, invokes, and stores. 2460252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner // Because subloops have already been incorporated into AST, we skip blocks in 2472e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // subloops. 2482e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // 2499b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 2509b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman I != E; ++I) { 2519b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman BasicBlock *BB = *I; 2529b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman if (LI->getLoopFor(BB) == L) // Ignore blocks in subloops... 2539b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman CurAST->add(*BB); // Incorporate the specified basic block 2549b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman } 2552e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 256e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // We want to visit all of the instructions in this loop... that are not parts 257e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // of our subloops (they have already had their invariants hoisted out of 258e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // their loop, into this loop, so there is no need to process the BODIES of 259e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // the subloops). 260e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // 261952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner // Traverse the body of the loop in depth first order on the dominator tree so 262952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner // that we are guaranteed to see definitions before we see uses. This allows 263af5cbc82bb6410129425c98bbfc1ffc4c3d0f411Nick Lewycky // us to sink instructions in one pass, without iteration. After sinking 264e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // instructions, we perform another pass to hoist them out of the loop. 265952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner // 26603e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman if (L->hasDedicatedExits()) 26703e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman SinkRegion(DT->getNode(L->getHeader())); 26803e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman if (Preheader) 26903e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman HoistRegion(DT->getNode(L->getHeader())); 270e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 2712e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Now that all loop invariants have been removed from the loop, promote any 272e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // memory references to scalars that we can. 273e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner if (!DisablePromotion && Preheader && L->hasDedicatedExits()) { 274e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // Loop over all of the alias sets in the tracker object. 275e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); 276e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner I != E; ++I) 277e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner PromoteAliasSet(*I); 278e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner } 279e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 280e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Clear out loops state information for the next iteration 281e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner CurLoop = 0; 28299a57216a935a512c418032f590a4660bad9d846Chris Lattner Preheader = 0; 28354959d6cf68a9b575c98c074babe9867682a7271Devang Patel 28454959d6cf68a9b575c98c074babe9867682a7271Devang Patel LoopToAliasMap[L] = CurAST; 28554959d6cf68a9b575c98c074babe9867682a7271Devang Patel return Changed; 286e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner} 287e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 288e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner/// SinkRegion - Walk the specified region of the CFG (defined by all blocks 289e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner/// dominated by the specified block, and that are in the current loop) in 2903a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson/// reverse depth first order w.r.t the DominatorTree. This allows us to visit 291e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner/// uses before definitions, allowing us to sink a loop body in one pass without 292e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner/// iteration. 293e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner/// 29426042420d642e810f5cdfb2da6156b74aaf80945Devang Patelvoid LICM::SinkRegion(DomTreeNode *N) { 2953a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson assert(N != 0 && "Null dominator tree node?"); 2963a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson BasicBlock *BB = N->getBlock(); 297e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 298e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // If this subregion is not in the top level loop at all, exit. 299e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner if (!CurLoop->contains(BB)) return; 300e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 301e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // We are processing blocks in reverse dfo, so process children first... 30226042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const std::vector<DomTreeNode*> &Children = N->getChildren(); 303e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner for (unsigned i = 0, e = Children.size(); i != e; ++i) 304e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner SinkRegion(Children[i]); 305e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 306e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // Only need to process the contents of this block if it is not part of a 307e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // subloop (which would already have been processed). 308e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner if (inSubLoop(BB)) return; 309e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 310a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner for (BasicBlock::iterator II = BB->end(); II != BB->begin(); ) { 311a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner Instruction &I = *--II; 312fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 313e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // Check to see if we can sink this instruction to the exit blocks 314e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // of the loop. We can do this if the all users of the instruction are 315e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // outside of the loop. In this case, it doesn't even matter if the 316e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // operands of the instruction are loop invariant. 317e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // 31870ac2dcb841dc62f08e16f0b0e2cefbf01baa4c5Chris Lattner if (isNotUsedInLoop(I) && canSinkOrHoistInst(I)) { 319a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner ++II; 320e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner sink(I); 321a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner } 322e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner } 323e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner} 324e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 325952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner/// HoistRegion - Walk the specified region of the CFG (defined by all blocks 326952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner/// dominated by the specified block, and that are in the current loop) in depth 3273a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson/// first order w.r.t the DominatorTree. This allows us to visit definitions 328952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner/// before uses, allowing us to hoist a loop body in one pass without iteration. 329952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner/// 33026042420d642e810f5cdfb2da6156b74aaf80945Devang Patelvoid LICM::HoistRegion(DomTreeNode *N) { 3313a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson assert(N != 0 && "Null dominator tree node?"); 3323a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson BasicBlock *BB = N->getBlock(); 333952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 334b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner // If this subregion is not in the top level loop at all, exit. 335ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner if (!CurLoop->contains(BB)) return; 336952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 337a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Only need to process the contents of this block if it is not part of a 338a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // subloop (which would already have been processed). 339ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner if (!inSubLoop(BB)) 340a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) { 341a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner Instruction &I = *II++; 342fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 343e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // Try hoisting the instruction out to the preheader. We can only do this 344e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // if all of the operands of the instruction are loop invariant and if it 345e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // is safe to hoist the instruction. 346e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // 347fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman if (isLoopInvariantInst(I) && canSinkOrHoistInst(I) && 348e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner isSafeToExecuteUnconditionally(I)) 3493c80a51cfd5e7187439ce4c051da77ee46e0ff9aChris Lattner hoist(I); 350a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 351952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 35226042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const std::vector<DomTreeNode*> &Children = N->getChildren(); 353952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner for (unsigned i = 0, e = Children.size(); i != e; ++i) 35456b7ee20dad7160a117ea0d102fc5432074ce2d0Chris Lattner HoistRegion(Children[i]); 355952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner} 356952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 357a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// canSinkOrHoistInst - Return true if the hoister and sinker can handle this 358a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// instruction. 359a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// 360a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattnerbool LICM::canSinkOrHoistInst(Instruction &I) { 361ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner // Loads have extra constraints we have to verify before we can hoist them. 362ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(&I)) { 363ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner if (LI->isVolatile()) 364ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner return false; // Don't hoist volatile loads! 365ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner 366967948b4e25cae3de68f38fddaa75d838e676decChris Lattner // Loads from constant memory are always safe to move, even if they end up 367967948b4e25cae3de68f38fddaa75d838e676decChris Lattner // in the same alias set as something that ends up being modified. 368dab249b3b762cff0ff16069b3233e4c885e75347Dan Gohman if (AA->pointsToConstantMemory(LI->getOperand(0))) 369967948b4e25cae3de68f38fddaa75d838e676decChris Lattner return true; 370967948b4e25cae3de68f38fddaa75d838e676decChris Lattner 371ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner // Don't hoist loads which have may-aliased stores in loop. 372f3e1d6977ee5fb6b66df314d65e28e2c35d6e244Chris Lattner unsigned Size = 0; 373f3e1d6977ee5fb6b66df314d65e28e2c35d6e244Chris Lattner if (LI->getType()->isSized()) 374fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman Size = AA->getTypeStoreSize(LI->getType()); 375f3e1d6977ee5fb6b66df314d65e28e2c35d6e244Chris Lattner return !pointerInvalidatedByLoop(LI->getOperand(0), Size); 376118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner } else if (CallInst *CI = dyn_cast<CallInst>(&I)) { 377118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner // Handle obvious cases efficiently. 378dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands AliasAnalysis::ModRefBehavior Behavior = AA->getModRefBehavior(CI); 379dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands if (Behavior == AliasAnalysis::DoesNotAccessMemory) 380dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands return true; 381dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands else if (Behavior == AliasAnalysis::OnlyReadsMemory) { 382dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands // If this call only reads from memory and there are no writes to memory 383dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands // in the loop, we can hoist or sink the call as appropriate. 384dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands bool FoundMod = false; 385dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); 386dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands I != E; ++I) { 387dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands AliasSet &AS = *I; 388dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands if (!AS.isForwardingAliasSet() && AS.isMod()) { 389dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands FoundMod = true; 390dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands break; 391118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner } 392118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner } 393dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands if (!FoundMod) return true; 394118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner } 395118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner 396118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner // FIXME: This should use mod/ref information to see if we can hoist or sink 397118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner // the call. 398fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 399118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner return false; 400ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner } 401ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner 4023da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer // Otherwise these instructions are hoistable/sinkable 403832254e1c2387c0cbeb0a820b8315fbe85cb003aReid Spencer return isa<BinaryOperator>(I) || isa<CastInst>(I) || 404d8af90c1da64b81a7aa167b5adcc1e81b0741252Dan Gohman isa<SelectInst>(I) || isa<GetElementPtrInst>(I) || isa<CmpInst>(I) || 405d8af90c1da64b81a7aa167b5adcc1e81b0741252Dan Gohman isa<InsertElementInst>(I) || isa<ExtractElementInst>(I) || 406d8af90c1da64b81a7aa167b5adcc1e81b0741252Dan Gohman isa<ShuffleVectorInst>(I); 407a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner} 408a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 409a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// isNotUsedInLoop - Return true if the only users of this instruction are 410a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// outside of the loop. If this is true, we can sink the instruction to the 411a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// exit blocks of the loop. 412a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// 413a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattnerbool LICM::isNotUsedInLoop(Instruction &I) { 414ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); UI != E; ++UI) { 415ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner Instruction *User = cast<Instruction>(*UI); 416ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner if (PHINode *PN = dyn_cast<PHINode>(User)) { 417ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner // PHI node uses occur in predecessor blocks! 418ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 419ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner if (PN->getIncomingValue(i) == &I) 420ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner if (CurLoop->contains(PN->getIncomingBlock(i))) 421ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner return false; 42292329c7fbe572892c17aa2d2542a10e3ea16132fDan Gohman } else if (CurLoop->contains(User)) { 423a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return false; 424ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner } 425ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner } 426a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return true; 427a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner} 428a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 429a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 430a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// isLoopInvariantInst - Return true if all operands of this instruction are 431a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// loop invariant. We also filter out non-hoistable instructions here just for 432a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// efficiency. 433a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// 434a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattnerbool LICM::isLoopInvariantInst(Instruction &I) { 435a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // The instruction is loop invariant if all of its operands are loop-invariant 436a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) 4373280f7bd557250a448eb56edbddfc90c94a406e6Chris Lattner if (!CurLoop->isLoopInvariant(I.getOperand(i))) 438a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return false; 439a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 440ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner // If we got this far, the instruction is loop invariant! 441ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner return true; 442ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner} 443ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner 444a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// sink - When an instruction is found to only be used outside of the loop, 445a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner/// this function moves it to the exit blocks and patches up SSA form as needed. 446a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner/// This method is guaranteed to remove the original instruction from its 447a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner/// position, and may either delete it or move it to outside of the loop. 448a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// 449a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattnervoid LICM::sink(Instruction &I) { 45039a383124b70dda1fea18288235114029ede76cfNick Lewycky DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n"); 451a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 452b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel SmallVector<BasicBlock*, 8> ExitBlocks; 453d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner CurLoop->getUniqueExitBlocks(ExitBlocks); 454df45bd3803ae0965a83cd1f30ee051b9f43e73ddChris Lattner 455df45bd3803ae0965a83cd1f30ee051b9f43e73ddChris Lattner if (isa<LoadInst>(I)) ++NumMovedLoads; 456118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner else if (isa<CallInst>(I)) ++NumMovedCalls; 457df45bd3803ae0965a83cd1f30ee051b9f43e73ddChris Lattner ++NumSunk; 458df45bd3803ae0965a83cd1f30ee051b9f43e73ddChris Lattner Changed = true; 459df45bd3803ae0965a83cd1f30ee051b9f43e73ddChris Lattner 460a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // The case where there is only a single exit node of this loop is common 461a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // enough that we handle it as a special (more efficient) case. It is more 462a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // efficient to handle because there are no PHI nodes that need to be placed. 463a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (ExitBlocks.size() == 1) { 464a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (!isExitBlockDominatedByBlockInLoop(ExitBlocks[0], I.getParent())) { 465a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Instruction is not used, just delete it. 4662741c971044d2165be572749b94398043caccfebChris Lattner CurAST->deleteValue(&I); 4671bf5ebc7be0d5b05e4175c7adb767b38896adef1Devang Patel // If I has users in unreachable blocks, eliminate. 468228ebd0f4cf9207d32d61ef4b11b81736895dc09Devang Patel // If I is not void type then replaceAllUsesWith undef. 469228ebd0f4cf9207d32d61ef4b11b81736895dc09Devang Patel // This allows ValueHandlers and custom metadata to adjust itself. 470a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner if (!I.use_empty()) 471228ebd0f4cf9207d32d61ef4b11b81736895dc09Devang Patel I.replaceAllUsesWith(UndefValue::get(I.getType())); 4723c80a51cfd5e7187439ce4c051da77ee46e0ff9aChris Lattner I.eraseFromParent(); 473a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } else { 474a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Move the instruction to the start of the exit block, after any PHI 475a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // nodes in it. 4763c80a51cfd5e7187439ce4c051da77ee46e0ff9aChris Lattner I.removeFromParent(); 47702dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = ExitBlocks[0]->getFirstNonPHI(); 478a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner ExitBlocks[0]->getInstList().insert(InsertPt, &I); 479a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 480d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner return; 481d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner } 482d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner 483d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner if (ExitBlocks.empty()) { 484a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // The instruction is actually dead if there ARE NO exit blocks. 4852741c971044d2165be572749b94398043caccfebChris Lattner CurAST->deleteValue(&I); 4861bf5ebc7be0d5b05e4175c7adb767b38896adef1Devang Patel // If I has users in unreachable blocks, eliminate. 487228ebd0f4cf9207d32d61ef4b11b81736895dc09Devang Patel // If I is not void type then replaceAllUsesWith undef. 488228ebd0f4cf9207d32d61ef4b11b81736895dc09Devang Patel // This allows ValueHandlers and custom metadata to adjust itself. 489a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner if (!I.use_empty()) 490228ebd0f4cf9207d32d61ef4b11b81736895dc09Devang Patel I.replaceAllUsesWith(UndefValue::get(I.getType())); 4913c80a51cfd5e7187439ce4c051da77ee46e0ff9aChris Lattner I.eraseFromParent(); 492d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner return; 493d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner } 494d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner 495a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner // Otherwise, if we have multiple exits, use the SSAUpdater to do all of the 496a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner // hard work of inserting PHI nodes as necessary. 497a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner SmallVector<PHINode*, 8> NewPHIs; 498a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner SSAUpdater SSA(&NewPHIs); 499a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner 500a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner if (!I.use_empty()) 501a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner SSA.Initialize(&I); 502d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner 503a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner // Insert a copy of the instruction in each exit block of the loop that is 504a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner // dominated by the instruction. Each exit block is known to only be in the 505a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner // ExitBlocks list once. 506a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner BasicBlock *InstOrigBB = I.getParent(); 507d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner unsigned NumInserted = 0; 508a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner 509d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 510d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner BasicBlock *ExitBlock = ExitBlocks[i]; 511a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner 512d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner if (!isExitBlockDominatedByBlockInLoop(ExitBlock, InstOrigBB)) 513d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner continue; 514d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner 515a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner // Insert the code after the last PHI node. 516d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner BasicBlock::iterator InsertPt = ExitBlock->getFirstNonPHI(); 517a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner 518d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner // If this is the first exit block processed, just move the original 519d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner // instruction, otherwise clone the original instruction and insert 520d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner // the copy. 521d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner Instruction *New; 522a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner if (NumInserted++ == 0) { 523a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner I.moveBefore(InsertPt); 524d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner New = &I; 525d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner } else { 526d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner New = I.clone(); 527d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner CurAST->copyValue(&I, New); 528d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner if (!I.getName().empty()) 529d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner New->setName(I.getName()+".le"); 530d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner ExitBlock->getInstList().insert(InsertPt, New); 531a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 532d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner 533a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner // Now that we have inserted the instruction, inform SSAUpdater. 534a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner if (!I.use_empty()) 535a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner SSA.AddAvailableValue(ExitBlock, New); 536d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner } 537a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner 538d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner // If the instruction doesn't dominate any exit blocks, it must be dead. 539d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner if (NumInserted == 0) { 540d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner CurAST->deleteValue(&I); 541a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner if (!I.use_empty()) 542a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner I.replaceAllUsesWith(UndefValue::get(I.getType())); 543d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner I.eraseFromParent(); 544a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner return; 545d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner } 546a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner 547a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner // Next, rewrite uses of the instruction, inserting PHI nodes as needed. 548a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner for (Value::use_iterator UI = I.use_begin(), UE = I.use_end(); UI != UE; ) { 549a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner // Grab the use before incrementing the iterator. 550a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner Use &U = UI.getUse(); 551a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner // Increment the iterator before removing the use from the list. 552a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner ++UI; 553a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner SSA.RewriteUseAfterInsertions(U); 554a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 555a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner 556a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner // Update CurAST for NewPHIs if I had pointer type. 557a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner if (I.getType()->isPointerTy()) 558a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner for (unsigned i = 0, e = NewPHIs.size(); i != e; ++i) 559a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner CurAST->copyValue(NewPHIs[i], &I); 560a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner} 561952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 56294170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// hoist - When an instruction is found to only use loop invariant operands 56394170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// that is safe to hoist, this instruction is called to do the dirty work. 56494170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// 565a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattnervoid LICM::hoist(Instruction &I) { 566f15826999bc560ee6f67cff5ecd71bf9cce7a7aaDavid Greene DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " 56767d1d1f8322bdc460158888cd233be8d1cb1d4abEvan Cheng << I << "\n"); 568ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner 56999a57216a935a512c418032f590a4660bad9d846Chris Lattner // Remove the instruction from its current basic block... but don't delete the 57099a57216a935a512c418032f590a4660bad9d846Chris Lattner // instruction. 5713c80a51cfd5e7187439ce4c051da77ee46e0ff9aChris Lattner I.removeFromParent(); 572e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 5739646e6b6af1f924f9366a2bffc6dde102f84d231Chris Lattner // Insert the new node in Preheader, before the terminator. 574a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner Preheader->getInstList().insert(Preheader->getTerminator(), &I); 575fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 576a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (isa<LoadInst>(I)) ++NumMovedLoads; 577118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner else if (isa<CallInst>(I)) ++NumMovedCalls; 5789646e6b6af1f924f9366a2bffc6dde102f84d231Chris Lattner ++NumHoisted; 579e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner Changed = true; 580e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner} 581e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 582a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// isSafeToExecuteUnconditionally - Only sink or hoist an instruction if it is 583a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// not a trapping instruction or if it is a trapping instruction and is 584a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// guaranteed to execute. 5859966c03aad031f738718bed3bc00371e358beb5dTanya Lattner/// 586a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattnerbool LICM::isSafeToExecuteUnconditionally(Instruction &Inst) { 58792094b4d928119eceac1484331acffe950f4651cChris Lattner // If it is not a trapping instruction, it is always safe to hoist. 5880b79a7727d68a507837e827803859424cf3d997bEli Friedman if (Inst.isSafeToSpeculativelyExecute()) 5890b79a7727d68a507837e827803859424cf3d997bEli Friedman return true; 590fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 59192094b4d928119eceac1484331acffe950f4651cChris Lattner // Otherwise we have to check to make sure that the instruction dominates all 59292094b4d928119eceac1484331acffe950f4651cChris Lattner // of the exit blocks. If it doesn't, then there is a path out of the loop 59392094b4d928119eceac1484331acffe950f4651cChris Lattner // which does not execute this instruction, so we can't hoist it. 59492094b4d928119eceac1484331acffe950f4651cChris Lattner 59592094b4d928119eceac1484331acffe950f4651cChris Lattner // If the instruction is in the header block for the loop (which is very 59692094b4d928119eceac1484331acffe950f4651cChris Lattner // common), it is always guaranteed to dominate the exit blocks. Since this 59792094b4d928119eceac1484331acffe950f4651cChris Lattner // is a common case, and can save some work, check it now. 598a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (Inst.getParent() == CurLoop->getHeader()) 59992094b4d928119eceac1484331acffe950f4651cChris Lattner return true; 60092094b4d928119eceac1484331acffe950f4651cChris Lattner 60192094b4d928119eceac1484331acffe950f4651cChris Lattner // Get the exit blocks for the current loop. 602b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel SmallVector<BasicBlock*, 8> ExitBlocks; 6035fa802fe279f10f402e039bc931aa57c0e424bf5Chris Lattner CurLoop->getExitBlocks(ExitBlocks); 6049966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 6053a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson // For each exit block, get the DT node and walk up the DT until the 60692094b4d928119eceac1484331acffe950f4651cChris Lattner // instruction's basic block is found or we exit the loop. 607a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 608a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (!isExitBlockDominatedByBlockInLoop(ExitBlocks[i], Inst.getParent())) 609a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return false; 610fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 6119966c03aad031f738718bed3bc00371e358beb5dTanya Lattner return true; 6129966c03aad031f738718bed3bc00371e358beb5dTanya Lattner} 6139966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 614e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner/// PromoteAliasSet - Try to promote memory values to scalars by sinking 6152e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// stores out of the loop and moving loads to before the loop. We do this by 6162e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// looping over the stores in the loop, looking for stores to Must pointers 617e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner/// which are loop invariant. 6182e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// 619e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattnervoid LICM::PromoteAliasSet(AliasSet &AS) { 620e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // We can promote this alias set if it has a store, if it is a "Must" alias 621e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // set, if the pointer is loop invariant, and if we are not eliminating any 622e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // volatile loads or stores. 623e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() || 624e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner AS.isVolatile() || !CurLoop->isLoopInvariant(AS.begin()->getValue())) 625e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner return; 626e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 627e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner assert(!AS.empty() && 628e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner "Must alias set should have at least one pointer element in it!"); 629e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner Value *SomePtr = AS.begin()->getValue(); 630fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 631e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // It isn't safe to promote a load/store from the loop if the load/store is 632e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // conditional. For example, turning: 6332e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // 634e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // for () { if (c) *P += 1; } 6352e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // 636e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // into: 637e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // 638e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // tmp = *P; for () { if (c) tmp +=1; } *P = tmp; 639e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // 640e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // is not safe, because *P may only be valid to access if 'c' is true. 641e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // 642e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // It is safe to promote P if all uses are direct load/stores and if at 643e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // least one is guaranteed to be executed. 644e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner bool GuaranteedToExecute = false; 645e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 646e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner SmallVector<Instruction*, 64> LoopUses; 647e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner SmallPtrSet<Value*, 4> PointerMustAliases; 648e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 649e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // Check that all of the pointers in the alias set have the same type. We 650e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // cannot (yet) promote a memory location that is loaded and stored in 651e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // different sizes. 652e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) { 653e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner Value *ASIV = ASI->getValue(); 654e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner PointerMustAliases.insert(ASIV); 65529d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner 65629d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner // Check that all of the pointers in the alias set have the same type. We 65729d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner // cannot (yet) promote a memory location that is loaded and stored in 65829d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner // different sizes. 659e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner if (SomePtr->getType() != ASIV->getType()) 660e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner return; 661e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 662e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner for (Value::use_iterator UI = ASIV->use_begin(), UE = ASIV->use_end(); 66319d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner UI != UE; ++UI) { 664e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // Ignore instructions that are outside the loop. 66529d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner Instruction *Use = dyn_cast<Instruction>(*UI); 66692329c7fbe572892c17aa2d2542a10e3ea16132fDan Gohman if (!Use || !CurLoop->contains(Use)) 66729d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner continue; 668e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 669e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // If there is an non-load/store instruction in the loop, we can't promote 670e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // it. 671e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner if (isa<LoadInst>(Use)) 672e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner assert(!cast<LoadInst>(Use)->isVolatile() && "AST broken"); 673e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner else if (isa<StoreInst>(Use)) 674e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner assert(!cast<StoreInst>(Use)->isVolatile() && 675e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner Use->getOperand(0) != ASIV && "AST broken"); 676e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner else 677e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner return; // Not a load or store. 67819d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner 67919d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner if (!GuaranteedToExecute) 68019d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner GuaranteedToExecute = isSafeToExecuteUnconditionally(*Use); 681e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 682e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner LoopUses.push_back(Use); 68329d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner } 684e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner } 685e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 686e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // If there isn't a guaranteed-to-execute instruction, we can't promote. 687e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner if (!GuaranteedToExecute) 688e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner return; 689e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 690e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // Otherwise, this is safe to promote, lets do it! 691e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " <<*SomePtr<<'\n'); 692e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner Changed = true; 693e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner ++NumPromoted; 694bc2265abe1d1b830995bb2f6322409bc7d7c5740Devang Patel 695e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // We use the SSAUpdater interface to insert phi nodes as required. 696e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner SmallVector<PHINode*, 16> NewPHIs; 697e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner SSAUpdater SSA(&NewPHIs); 698e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 699e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // It wants to know some value of the same type as what we'll be inserting. 700e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner Value *SomeValue; 701e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner if (isa<LoadInst>(LoopUses[0])) 702e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner SomeValue = LoopUses[0]; 703e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner else 704e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner SomeValue = cast<StoreInst>(LoopUses[0])->getOperand(0); 705e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner SSA.Initialize(SomeValue); 706e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 707e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // First step: bucket up uses of the pointers by the block they occur in. 708e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // This is important because we have to handle multiple defs/uses in a block 709e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // ourselves: SSAUpdater is purely for cross-block references. 710e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // FIXME: Want a TinyVector<Instruction*> since there is usually 0/1 element. 711e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner DenseMap<BasicBlock*, std::vector<Instruction*> > UsesByBlock; 712e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner for (unsigned i = 0, e = LoopUses.size(); i != e; ++i) { 713e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner Instruction *User = LoopUses[i]; 714e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner UsesByBlock[User->getParent()].push_back(User); 715e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner } 716e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 717e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // Okay, now we can iterate over all the blocks in the loop with uses, 718e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // processing them. Keep track of which loads are loading a live-in value. 719e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner SmallVector<LoadInst*, 32> LiveInLoads; 720e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 721e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner for (unsigned LoopUse = 0, e = LoopUses.size(); LoopUse != e; ++LoopUse) { 722e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner Instruction *User = LoopUses[LoopUse]; 723e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner std::vector<Instruction*> &BlockUses = UsesByBlock[User->getParent()]; 724e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 725e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // If this block has already been processed, ignore this repeat use. 726e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner if (BlockUses.empty()) continue; 727e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 728e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // Okay, this is the first use in the block. If this block just has a 729e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // single user in it, we can rewrite it trivially. 730e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner if (BlockUses.size() == 1) { 731e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // If it is a store, it is a trivial def of the value in the block. 732e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner if (isa<StoreInst>(User)) { 733e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner SSA.AddAvailableValue(User->getParent(), 734e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner cast<StoreInst>(User)->getOperand(0)); 735e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner } else { 736e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // Otherwise it is a load, queue it to rewrite as a live-in load. 737e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner LiveInLoads.push_back(cast<LoadInst>(User)); 738e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner } 739e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner BlockUses.clear(); 74029d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner continue; 741e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner } 742e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 743e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // Otherwise, check to see if this block is all loads. If so, we can queue 744e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // them all as live in loads. 745e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner bool HasStore = false; 746e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner for (unsigned i = 0, e = BlockUses.size(); i != e; ++i) { 747e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner if (isa<StoreInst>(BlockUses[i])) { 748e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner HasStore = true; 749e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner break; 750e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner } 751e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner } 75229d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner 753e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner if (!HasStore) { 754e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner for (unsigned i = 0, e = BlockUses.size(); i != e; ++i) 755e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner LiveInLoads.push_back(cast<LoadInst>(BlockUses[i])); 756e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner BlockUses.clear(); 757e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner continue; 758e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner } 759e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 760e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // Otherwise, we have mixed loads and stores (or just a bunch of stores). 761e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // Since SSAUpdater is purely for cross-block values, we need to determine 762e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // the order of these instructions in the block. If the first use in the 763e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // block is a load, then it uses the live in value. The last store defines 764e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // the live out value. We handle this by doing a linear scan of the block. 765e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner BasicBlock *BB = User->getParent(); 766e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner Value *StoredValue = 0; 767e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ++II) { 768e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner if (LoadInst *L = dyn_cast<LoadInst>(II)) { 769e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // If this is a load to an unrelated pointer, ignore it. 770e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner if (!PointerMustAliases.count(L->getOperand(0))) continue; 771e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 772e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // If we haven't seen a store yet, this is a live in use, otherwise 773e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // use the stored value. 774e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner if (StoredValue) 775e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner L->replaceAllUsesWith(StoredValue); 776e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner else 777e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner LiveInLoads.push_back(L); 778e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner continue; 779e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner } 780e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 781e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner if (StoreInst *S = dyn_cast<StoreInst>(II)) { 782e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // If this is a load to an unrelated pointer, ignore it. 783e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner if (!PointerMustAliases.count(S->getOperand(1))) continue; 784fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner 785e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // Remember that this is the active value in the block. 786e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner StoredValue = S->getOperand(0); 787e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner } 788e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner } 789e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 790e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // The last stored value that happened is the live-out for the block. 791e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner assert(StoredValue && "Already checked that there is a store in block"); 792e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner SSA.AddAvailableValue(BB, StoredValue); 793e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner BlockUses.clear(); 794e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner } 795e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 796e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // Now that all the intra-loop values are classified, set up the preheader. 797e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // It gets a load of the pointer we're promoting, and it is the live-out value 798e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // from the preheader. 799e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner LoadInst *PreheaderLoad = new LoadInst(SomePtr,SomePtr->getName()+".promoted", 800e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner Preheader->getTerminator()); 801e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner SSA.AddAvailableValue(Preheader, PreheaderLoad); 802e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 803e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // Now that the preheader is good to go, set up the exit blocks. Each exit 804e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // block gets a store of the live-out values that feed them. Since we've 805e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // already told the SSA updater about the defs in the loop and the preheader 806e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // definition, it is all set and we can start using it. 807e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner SmallVector<BasicBlock*, 8> ExitBlocks; 808e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner CurLoop->getUniqueExitBlocks(ExitBlocks); 809e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 810e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner BasicBlock *ExitBlock = ExitBlocks[i]; 811e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock); 812e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner Instruction *InsertPos = ExitBlock->getFirstNonPHI(); 813e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner new StoreInst(LiveInValue, SomePtr, InsertPos); 814e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner } 815fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 816e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // Okay, now we rewrite all loads that use live-in values in the loop, 817e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // inserting PHI nodes as necessary. 818e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner for (unsigned i = 0, e = LiveInLoads.size(); i != e; ++i) { 819e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner LoadInst *ALoad = LiveInLoads[i]; 820e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner ALoad->replaceAllUsesWith(SSA.GetValueInMiddleOfBlock(ALoad->getParent())); 821e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner } 822e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 823e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // Now that everything is rewritten, delete the old instructions from the body 824e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // of the loop. They should all be dead now. 825e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner for (unsigned i = 0, e = LoopUses.size(); i != e; ++i) { 826e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner Instruction *User = LoopUses[i]; 827e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner CurAST->deleteValue(User); 828e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner User->eraseFromParent(); 829e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner } 830e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 831e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // If the preheader load is itself a pointer, we need to tell alias analysis 832e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // about the new pointer we created in the preheader block and about any PHI 833e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // nodes that just got inserted. 834e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner if (PreheaderLoad->getType()->isPointerTy()) { 835e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // Copy any value stored to or loaded from a must-alias of the pointer. 836e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner CurAST->copyValue(SomeValue, PreheaderLoad); 837fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 838e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner for (unsigned i = 0, e = NewPHIs.size(); i != e; ++i) 839e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner CurAST->copyValue(SomeValue, NewPHIs[i]); 8402e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 841e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 842e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // fwew, we're done! 843f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner} 84491d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel 845e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 84691d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel/// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info. 84791d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patelvoid LICM::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L) { 84891d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel AliasSetTracker *AST = LoopToAliasMap[L]; 84991d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel if (!AST) 85091d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel return; 85191d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel 85291d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel AST->copyValue(From, To); 85391d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel} 85491d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel 85591d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel/// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias 85691d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel/// set. 85791d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patelvoid LICM::deleteAnalysisValue(Value *V, Loop *L) { 85891d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel AliasSetTracker *AST = LoopToAliasMap[L]; 85991d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel if (!AST) 86091d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel return; 86191d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel 86291d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel AST->deleteValue(V); 86391d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel} 864