LICM.cpp revision bdff548e4dd577a72094d57b282de4e765643b96
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 292e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// the mem2reg functionality to construct the appropriate SSA form for the 302e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// variable. 31e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner// 32e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner//===----------------------------------------------------------------------===// 33e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 341f309c1a4e8068a64627c612a895d9b403dbcb26Chris Lattner#define DEBUG_TYPE "licm" 35e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include "llvm/Transforms/Scalar.h" 3679066fa6acce02c97c714a5a6e151ed8a249721cChris Lattner#include "llvm/Constants.h" 372741c971044d2165be572749b94398043caccfebChris Lattner#include "llvm/DerivedTypes.h" 382741c971044d2165be572749b94398043caccfebChris Lattner#include "llvm/Instructions.h" 391ff50b380e6f5549f5ddd9e6c390dcb00332e3e9Owen Anderson#include "llvm/LLVMContext.h" 402741c971044d2165be572749b94398043caccfebChris Lattner#include "llvm/Target/TargetData.h" 41e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include "llvm/Analysis/LoopInfo.h" 4254959d6cf68a9b575c98c074babe9867682a7271Devang Patel#include "llvm/Analysis/LoopPass.h" 43f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner#include "llvm/Analysis/AliasAnalysis.h" 440252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner#include "llvm/Analysis/AliasSetTracker.h" 45952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner#include "llvm/Analysis/Dominators.h" 4696b651c627160e1ea0f1bb86d352d697e6c1972dDevang Patel#include "llvm/Analysis/ScalarEvolution.h" 472741c971044d2165be572749b94398043caccfebChris Lattner#include "llvm/Transforms/Utils/PromoteMemToReg.h" 489133fe28954d498fc4de13064c7d65bd811de02cReid Spencer#include "llvm/Support/CFG.h" 499133fe28954d498fc4de13064c7d65bd811de02cReid Spencer#include "llvm/Support/Compiler.h" 50551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 51ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar#include "llvm/Support/raw_ostream.h" 52551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 53551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 54e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include <algorithm> 5592094b4d928119eceac1484331acffe950f4651cChris Lattnerusing namespace llvm; 56d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 570e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumSunk , "Number of instructions sunk out of loop"); 580e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumHoisted , "Number of instructions hoisted out of loop"); 590e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk"); 600e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk"); 610e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumPromoted , "Number of memory locations promoted to registers"); 620e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattner 63844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> 64844731a7f1909f55935e3514c9e713a62d67662eDan GohmanDisablePromotion("disable-licm-promotion", cl::Hidden, 65844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::desc("Disable memory promotion in LICM pass")); 662e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 67d7168ddb116c2e9aa1f8325ae887eb63d6003037Chris Lattner// This feature is currently disabled by default because CodeGen is not yet 68d7168ddb116c2e9aa1f8325ae887eb63d6003037Chris Lattner// capable of rematerializing these constants in PIC mode, so it can lead to 69d7168ddb116c2e9aa1f8325ae887eb63d6003037Chris Lattner// degraded performance. Compile test/CodeGen/X86/remat-constant.ll with 703eee6542f5c65dce299361fa5435340513cf3fe4Dan Gohman// -relocation-model=pic to see an example of this. 713eee6542f5c65dce299361fa5435340513cf3fe4Dan Gohmanstatic cl::opt<bool> 723eee6542f5c65dce299361fa5435340513cf3fe4Dan GohmanEnableLICMConstantMotion("enable-licm-constant-variables", cl::Hidden, 733eee6542f5c65dce299361fa5435340513cf3fe4Dan Gohman cl::desc("Enable hoisting/sinking of constant " 743eee6542f5c65dce299361fa5435340513cf3fe4Dan Gohman "global variables")); 753eee6542f5c65dce299361fa5435340513cf3fe4Dan Gohman 76844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 7754959d6cf68a9b575c98c074babe9867682a7271Devang Patel struct VISIBILITY_HIDDEN LICM : public LoopPass { 78ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 79ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman LICM() : LoopPass(&ID) {} 80794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 8154959d6cf68a9b575c98c074babe9867682a7271Devang Patel virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 82e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 8394170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// This transformation requires natural loop information & requires that 8494170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// loop preheaders be inserted into the CFG... 8594170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// 86e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 87cb2610ea037a17115ef3a01a6bdaab4e3cfdca27Chris Lattner AU.setPreservesCFG(); 8898bf436e2e2ab463d79c54a42a46b12028905330Chris Lattner AU.addRequiredID(LoopSimplifyID); 895f0eb8da62308126d5b61e3eee5bee75b9dc5194Chris Lattner AU.addRequired<LoopInfo>(); 903a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson AU.addRequired<DominatorTree>(); 910252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner AU.addRequired<DominanceFrontier>(); // For scalar promotion (mem2reg) 92f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner AU.addRequired<AliasAnalysis>(); 9396b651c627160e1ea0f1bb86d352d697e6c1972dDevang Patel AU.addPreserved<ScalarEvolution>(); 9496b651c627160e1ea0f1bb86d352d697e6c1972dDevang Patel AU.addPreserved<DominanceFrontier>(); 95e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } 96e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 97747603e39ea3f29add9ba6c07bbefcc5c2432612Dan Gohman bool doFinalization() { 98fd94dd58ffef1be3597ef8cb64f3b1d476d7d5ecAnton Korobeynikov // Free the values stored in the map 99fd94dd58ffef1be3597ef8cb64f3b1d476d7d5ecAnton Korobeynikov for (std::map<Loop *, AliasSetTracker *>::iterator 100fd94dd58ffef1be3597ef8cb64f3b1d476d7d5ecAnton Korobeynikov I = LoopToAliasMap.begin(), E = LoopToAliasMap.end(); I != E; ++I) 101fd94dd58ffef1be3597ef8cb64f3b1d476d7d5ecAnton Korobeynikov delete I->second; 102fd94dd58ffef1be3597ef8cb64f3b1d476d7d5ecAnton Korobeynikov 10354959d6cf68a9b575c98c074babe9867682a7271Devang Patel LoopToAliasMap.clear(); 10454959d6cf68a9b575c98c074babe9867682a7271Devang Patel return false; 10554959d6cf68a9b575c98c074babe9867682a7271Devang Patel } 10654959d6cf68a9b575c98c074babe9867682a7271Devang Patel 107e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner private: 10892094b4d928119eceac1484331acffe950f4651cChris Lattner // Various analyses that we use... 1092e6e741b737960ecd0b68610875050019aac0f07Chris Lattner AliasAnalysis *AA; // Current AliasAnalysis information 11092094b4d928119eceac1484331acffe950f4651cChris Lattner LoopInfo *LI; // Current LoopInfo 1113a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson DominatorTree *DT; // Dominator Tree for the current Loop... 11243f820d1f7638656be2158efac7dd8f5b08b8b77Chris Lattner DominanceFrontier *DF; // Current Dominance Frontier 11392094b4d928119eceac1484331acffe950f4651cChris Lattner 11492094b4d928119eceac1484331acffe950f4651cChris Lattner // State that is updated as we process loops 1152e6e741b737960ecd0b68610875050019aac0f07Chris Lattner bool Changed; // Set to true when we change anything. 1162e6e741b737960ecd0b68610875050019aac0f07Chris Lattner BasicBlock *Preheader; // The preheader block of the current loop... 1172e6e741b737960ecd0b68610875050019aac0f07Chris Lattner Loop *CurLoop; // The current loop we are working on... 1180252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner AliasSetTracker *CurAST; // AliasSet information for the current loop... 11954959d6cf68a9b575c98c074babe9867682a7271Devang Patel std::map<Loop *, AliasSetTracker *> LoopToAliasMap; 120e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 12191d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info. 12291d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel void cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L); 12391d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel 12491d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel /// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias 12591d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel /// set. 12691d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel void deleteAnalysisValue(Value *V, Loop *L); 12791d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel 128e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner /// SinkRegion - Walk the specified region of the CFG (defined by all blocks 129e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner /// dominated by the specified block, and that are in the current loop) in 1303a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson /// reverse depth first order w.r.t the DominatorTree. This allows us to 131e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner /// visit uses before definitions, allowing us to sink a loop body in one 132e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner /// pass without iteration. 133e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner /// 13426042420d642e810f5cdfb2da6156b74aaf80945Devang Patel void SinkRegion(DomTreeNode *N); 135e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 136952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// HoistRegion - Walk the specified region of the CFG (defined by all 137952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// blocks dominated by the specified block, and that are in the current 1383a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson /// loop) in depth first order w.r.t the DominatorTree. This allows us to 139cf00c4ab3ba308d45d98c5ccab87362cf802facbMisha Brukman /// visit definitions before uses, allowing us to hoist a loop body in one 140952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// pass without iteration. 141952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// 14226042420d642e810f5cdfb2da6156b74aaf80945Devang Patel void HoistRegion(DomTreeNode *N); 143952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 144b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner /// inSubLoop - Little predicate that returns true if the specified basic 145b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner /// block is in a subloop of the current one, not the current one itself. 14694170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// 147b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner bool inSubLoop(BasicBlock *BB) { 148b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop"); 149329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner for (Loop::iterator I = CurLoop->begin(), E = CurLoop->end(); I != E; ++I) 150329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner if ((*I)->contains(BB)) 151b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner return true; // A subloop actually contains this block! 152b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner return false; 153e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } 154e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 155a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// isExitBlockDominatedByBlockInLoop - This method checks to see if the 156a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// specified exit block of the loop is dominated by the specified block 157a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// that is in the body of the loop. We use these constraints to 158a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// dramatically limit the amount of the dominator tree that needs to be 159a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// searched. 160a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner bool isExitBlockDominatedByBlockInLoop(BasicBlock *ExitBlock, 161a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner BasicBlock *BlockInLoop) const { 162a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // If the block in the loop is the loop header, it must be dominated! 163a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner BasicBlock *LoopHeader = CurLoop->getHeader(); 164a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (BlockInLoop == LoopHeader) 165a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return true; 166fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 16726042420d642e810f5cdfb2da6156b74aaf80945Devang Patel DomTreeNode *BlockInLoopNode = DT->getNode(BlockInLoop); 16826042420d642e810f5cdfb2da6156b74aaf80945Devang Patel DomTreeNode *IDom = DT->getNode(ExitBlock); 169fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 170a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Because the exit block is not in the loop, we know we have to get _at 1712741c971044d2165be572749b94398043caccfebChris Lattner // least_ its immediate dominator. 172a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner do { 173a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Get next Immediate Dominator. 1743a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson IDom = IDom->getIDom(); 175fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 176a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // If we have got to the header of the loop, then the instructions block 177a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // did not dominate the exit node, so we can't hoist it. 1783a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson if (IDom->getBlock() == LoopHeader) 179a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return false; 180fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1813a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson } while (IDom != BlockInLoopNode); 182a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 183a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return true; 184a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 185a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 186a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// sink - When an instruction is found to only be used outside of the loop, 187a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// this function moves it to the exit blocks and patches up SSA form as 188a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// needed. 189a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// 190a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner void sink(Instruction &I); 191a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 19294170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// hoist - When an instruction is found to only use loop invariant operands 19394170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// that is safe to hoist, this instruction is called to do the dirty work. 19494170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// 1957e70829632f82de15db187845666aaca6e04b792Chris Lattner void hoist(Instruction &I); 196e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 197a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// isSafeToExecuteUnconditionally - Only sink or hoist an instruction if it 198a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// is not a trapping instruction or if it is a trapping instruction and is 199a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// guaranteed to execute. 2009966c03aad031f738718bed3bc00371e358beb5dTanya Lattner /// 201a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner bool isSafeToExecuteUnconditionally(Instruction &I); 2029966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 20394170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// pointerInvalidatedByLoop - Return true if the body of this loop may 20494170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// store into the memory location pointed to by V. 205fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman /// 206f3e1d6977ee5fb6b66df314d65e28e2c35d6e244Chris Lattner bool pointerInvalidatedByLoop(Value *V, unsigned Size) { 2070252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner // Check to see if any of the basic blocks in CurLoop invalidate *V. 208f3e1d6977ee5fb6b66df314d65e28e2c35d6e244Chris Lattner return CurAST->getAliasSetForPointer(V, Size).isMod(); 2092e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 210f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner 211a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner bool canSinkOrHoistInst(Instruction &I); 212a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner bool isLoopInvariantInst(Instruction &I); 213a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner bool isNotUsedInLoop(Instruction &I); 214e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 2152e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// PromoteValuesInLoop - Look at the stores in the loop and promote as many 2162e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// to scalars as we can. 2172e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// 2182e6e741b737960ecd0b68610875050019aac0f07Chris Lattner void PromoteValuesInLoop(); 2192e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 220fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner /// FindPromotableValuesInLoop - Check the current loop for stores to 221352361b409d16045e703d986aa7fd77295173ef3Misha Brukman /// definite pointers, which are not loaded and stored through may aliases. 2222e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// If these are found, create an alloca for the value, add it to the 2232e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// PromotedValues list, and keep track of the mapping from value to 2242e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// alloca... 2252e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// 226fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner void FindPromotableValuesInLoop( 2272e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::vector<std::pair<AllocaInst*, Value*> > &PromotedValues, 2282e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::map<Value*, AllocaInst*> &Val2AlMap); 229e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner }; 230e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner} 231e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 232844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar LICM::ID = 0; 233844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<LICM> X("licm", "Loop Invariant Code Motion"); 234844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 235394f0441e06dafca29f0752cf400990a5b8fe4b1Daniel DunbarPass *llvm::createLICMPass() { return new LICM(); } 236e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 2378d246f09cb46fe38aa71d2a4edcd84f30c4bf80eDevang Patel/// Hoist expressions out of the specified loop. Note, alias info for inner 2388d246f09cb46fe38aa71d2a4edcd84f30c4bf80eDevang Patel/// loop is not preserved so it is not a good idea to run LICM multiple 2398d246f09cb46fe38aa71d2a4edcd84f30c4bf80eDevang Patel/// times on one loop. 24094170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// 24154959d6cf68a9b575c98c074babe9867682a7271Devang Patelbool LICM::runOnLoop(Loop *L, LPPassManager &LPM) { 2422e6e741b737960ecd0b68610875050019aac0f07Chris Lattner Changed = false; 243e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 2442e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Get our Loop and Alias Analysis information... 2452e6e741b737960ecd0b68610875050019aac0f07Chris Lattner LI = &getAnalysis<LoopInfo>(); 246f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner AA = &getAnalysis<AliasAnalysis>(); 24743f820d1f7638656be2158efac7dd8f5b08b8b77Chris Lattner DF = &getAnalysis<DominanceFrontier>(); 2483a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson DT = &getAnalysis<DominatorTree>(); 249f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner 25054959d6cf68a9b575c98c074babe9867682a7271Devang Patel CurAST = new AliasSetTracker(*AA); 251f38ac5dd390ca583b6e6d1b40b378d07e49e5097Devang Patel // Collect Alias info from subloops 25254959d6cf68a9b575c98c074babe9867682a7271Devang Patel for (Loop::iterator LoopItr = L->begin(), LoopItrE = L->end(); 25354959d6cf68a9b575c98c074babe9867682a7271Devang Patel LoopItr != LoopItrE; ++LoopItr) { 25454959d6cf68a9b575c98c074babe9867682a7271Devang Patel Loop *InnerL = *LoopItr; 25554959d6cf68a9b575c98c074babe9867682a7271Devang Patel AliasSetTracker *InnerAST = LoopToAliasMap[InnerL]; 25654959d6cf68a9b575c98c074babe9867682a7271Devang Patel assert (InnerAST && "Where is my AST?"); 25794170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner 25854959d6cf68a9b575c98c074babe9867682a7271Devang Patel // What if InnerLoop was modified by other passes ? 25954959d6cf68a9b575c98c074babe9867682a7271Devang Patel CurAST->add(*InnerAST); 2602e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 26154959d6cf68a9b575c98c074babe9867682a7271Devang Patel 262e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner CurLoop = L; 263e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 26499a57216a935a512c418032f590a4660bad9d846Chris Lattner // Get the preheader block to move instructions into... 26599a57216a935a512c418032f590a4660bad9d846Chris Lattner Preheader = L->getLoopPreheader(); 26699a57216a935a512c418032f590a4660bad9d846Chris Lattner assert(Preheader&&"Preheader insertion pass guarantees we have a preheader!"); 26799a57216a935a512c418032f590a4660bad9d846Chris Lattner 2682e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Loop over the body of this loop, looking for calls, invokes, and stores. 2690252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner // Because subloops have already been incorporated into AST, we skip blocks in 2702e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // subloops. 2712e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // 2729b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 2739b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman I != E; ++I) { 2749b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman BasicBlock *BB = *I; 2759b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman if (LI->getLoopFor(BB) == L) // Ignore blocks in subloops... 2769b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman CurAST->add(*BB); // Incorporate the specified basic block 2779b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman } 2782e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 279e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // We want to visit all of the instructions in this loop... that are not parts 280e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // of our subloops (they have already had their invariants hoisted out of 281e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // their loop, into this loop, so there is no need to process the BODIES of 282e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // the subloops). 283e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // 284952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner // Traverse the body of the loop in depth first order on the dominator tree so 285952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner // that we are guaranteed to see definitions before we see uses. This allows 286af5cbc82bb6410129425c98bbfc1ffc4c3d0f411Nick Lewycky // us to sink instructions in one pass, without iteration. After sinking 287e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // instructions, we perform another pass to hoist them out of the loop. 288952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner // 2893a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson SinkRegion(DT->getNode(L->getHeader())); 2903a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson HoistRegion(DT->getNode(L->getHeader())); 291e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 2922e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Now that all loop invariants have been removed from the loop, promote any 2932e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // memory references to scalars that we can... 2942e6e741b737960ecd0b68610875050019aac0f07Chris Lattner if (!DisablePromotion) 2952e6e741b737960ecd0b68610875050019aac0f07Chris Lattner PromoteValuesInLoop(); 2962e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 297e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Clear out loops state information for the next iteration 298e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner CurLoop = 0; 29999a57216a935a512c418032f590a4660bad9d846Chris Lattner Preheader = 0; 30054959d6cf68a9b575c98c074babe9867682a7271Devang Patel 30154959d6cf68a9b575c98c074babe9867682a7271Devang Patel LoopToAliasMap[L] = CurAST; 30254959d6cf68a9b575c98c074babe9867682a7271Devang Patel return Changed; 303e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner} 304e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 305e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner/// SinkRegion - Walk the specified region of the CFG (defined by all blocks 306e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner/// dominated by the specified block, and that are in the current loop) in 3073a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson/// reverse depth first order w.r.t the DominatorTree. This allows us to visit 308e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner/// uses before definitions, allowing us to sink a loop body in one pass without 309e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner/// iteration. 310e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner/// 31126042420d642e810f5cdfb2da6156b74aaf80945Devang Patelvoid LICM::SinkRegion(DomTreeNode *N) { 3123a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson assert(N != 0 && "Null dominator tree node?"); 3133a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson BasicBlock *BB = N->getBlock(); 314e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 315e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // If this subregion is not in the top level loop at all, exit. 316e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner if (!CurLoop->contains(BB)) return; 317e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 318e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // We are processing blocks in reverse dfo, so process children first... 31926042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const std::vector<DomTreeNode*> &Children = N->getChildren(); 320e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner for (unsigned i = 0, e = Children.size(); i != e; ++i) 321e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner SinkRegion(Children[i]); 322e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 323e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // Only need to process the contents of this block if it is not part of a 324e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // subloop (which would already have been processed). 325e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner if (inSubLoop(BB)) return; 326e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 327a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner for (BasicBlock::iterator II = BB->end(); II != BB->begin(); ) { 328a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner Instruction &I = *--II; 329fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 330e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // Check to see if we can sink this instruction to the exit blocks 331e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // of the loop. We can do this if the all users of the instruction are 332e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // outside of the loop. In this case, it doesn't even matter if the 333e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // operands of the instruction are loop invariant. 334e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // 33570ac2dcb841dc62f08e16f0b0e2cefbf01baa4c5Chris Lattner if (isNotUsedInLoop(I) && canSinkOrHoistInst(I)) { 336a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner ++II; 337e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner sink(I); 338a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner } 339e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner } 340e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner} 341e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 342e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 343952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner/// HoistRegion - Walk the specified region of the CFG (defined by all blocks 344952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner/// dominated by the specified block, and that are in the current loop) in depth 3453a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson/// first order w.r.t the DominatorTree. This allows us to visit definitions 346952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner/// before uses, allowing us to hoist a loop body in one pass without iteration. 347952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner/// 34826042420d642e810f5cdfb2da6156b74aaf80945Devang Patelvoid LICM::HoistRegion(DomTreeNode *N) { 3493a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson assert(N != 0 && "Null dominator tree node?"); 3503a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson BasicBlock *BB = N->getBlock(); 351952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 352b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner // If this subregion is not in the top level loop at all, exit. 353ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner if (!CurLoop->contains(BB)) return; 354952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 355a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Only need to process the contents of this block if it is not part of a 356a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // subloop (which would already have been processed). 357ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner if (!inSubLoop(BB)) 358a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) { 359a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner Instruction &I = *II++; 360fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 361e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // Try hoisting the instruction out to the preheader. We can only do this 362e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // if all of the operands of the instruction are loop invariant and if it 363e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // is safe to hoist the instruction. 364e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // 365fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman if (isLoopInvariantInst(I) && canSinkOrHoistInst(I) && 366e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner isSafeToExecuteUnconditionally(I)) 3673c80a51cfd5e7187439ce4c051da77ee46e0ff9aChris Lattner hoist(I); 368a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 369952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 37026042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const std::vector<DomTreeNode*> &Children = N->getChildren(); 371952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner for (unsigned i = 0, e = Children.size(); i != e; ++i) 37256b7ee20dad7160a117ea0d102fc5432074ce2d0Chris Lattner HoistRegion(Children[i]); 373952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner} 374952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 375a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// canSinkOrHoistInst - Return true if the hoister and sinker can handle this 376a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// instruction. 377a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// 378a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattnerbool LICM::canSinkOrHoistInst(Instruction &I) { 379ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner // Loads have extra constraints we have to verify before we can hoist them. 380ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(&I)) { 381ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner if (LI->isVolatile()) 382ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner return false; // Don't hoist volatile loads! 383ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner 384967948b4e25cae3de68f38fddaa75d838e676decChris Lattner // Loads from constant memory are always safe to move, even if they end up 385967948b4e25cae3de68f38fddaa75d838e676decChris Lattner // in the same alias set as something that ends up being modified. 3863eee6542f5c65dce299361fa5435340513cf3fe4Dan Gohman if (EnableLICMConstantMotion && 3873eee6542f5c65dce299361fa5435340513cf3fe4Dan Gohman AA->pointsToConstantMemory(LI->getOperand(0))) 388967948b4e25cae3de68f38fddaa75d838e676decChris Lattner return true; 389967948b4e25cae3de68f38fddaa75d838e676decChris Lattner 390ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner // Don't hoist loads which have may-aliased stores in loop. 391f3e1d6977ee5fb6b66df314d65e28e2c35d6e244Chris Lattner unsigned Size = 0; 392f3e1d6977ee5fb6b66df314d65e28e2c35d6e244Chris Lattner if (LI->getType()->isSized()) 393fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman Size = AA->getTypeStoreSize(LI->getType()); 394f3e1d6977ee5fb6b66df314d65e28e2c35d6e244Chris Lattner return !pointerInvalidatedByLoop(LI->getOperand(0), Size); 395118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner } else if (CallInst *CI = dyn_cast<CallInst>(&I)) { 396118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner // Handle obvious cases efficiently. 397dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands AliasAnalysis::ModRefBehavior Behavior = AA->getModRefBehavior(CI); 398dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands if (Behavior == AliasAnalysis::DoesNotAccessMemory) 399dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands return true; 400dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands else if (Behavior == AliasAnalysis::OnlyReadsMemory) { 401dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands // If this call only reads from memory and there are no writes to memory 402dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands // in the loop, we can hoist or sink the call as appropriate. 403dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands bool FoundMod = false; 404dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); 405dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands I != E; ++I) { 406dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands AliasSet &AS = *I; 407dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands if (!AS.isForwardingAliasSet() && AS.isMod()) { 408dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands FoundMod = true; 409dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands break; 410118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner } 411118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner } 412dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands if (!FoundMod) return true; 413118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner } 414118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner 415118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner // FIXME: This should use mod/ref information to see if we can hoist or sink 416118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner // the call. 417fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 418118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner return false; 419ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner } 420ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner 4213da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer // Otherwise these instructions are hoistable/sinkable 422832254e1c2387c0cbeb0a820b8315fbe85cb003aReid Spencer return isa<BinaryOperator>(I) || isa<CastInst>(I) || 423d8af90c1da64b81a7aa167b5adcc1e81b0741252Dan Gohman isa<SelectInst>(I) || isa<GetElementPtrInst>(I) || isa<CmpInst>(I) || 424d8af90c1da64b81a7aa167b5adcc1e81b0741252Dan Gohman isa<InsertElementInst>(I) || isa<ExtractElementInst>(I) || 425d8af90c1da64b81a7aa167b5adcc1e81b0741252Dan Gohman isa<ShuffleVectorInst>(I); 426a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner} 427a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 428a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// isNotUsedInLoop - Return true if the only users of this instruction are 429a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// outside of the loop. If this is true, we can sink the instruction to the 430a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// exit blocks of the loop. 431a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// 432a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattnerbool LICM::isNotUsedInLoop(Instruction &I) { 433ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); UI != E; ++UI) { 434ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner Instruction *User = cast<Instruction>(*UI); 435ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner if (PHINode *PN = dyn_cast<PHINode>(User)) { 436ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner // PHI node uses occur in predecessor blocks! 437ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 438ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner if (PN->getIncomingValue(i) == &I) 439ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner if (CurLoop->contains(PN->getIncomingBlock(i))) 440ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner return false; 441ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner } else if (CurLoop->contains(User->getParent())) { 442a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return false; 443ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner } 444ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner } 445a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return true; 446a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner} 447a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 448a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 449a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// isLoopInvariantInst - Return true if all operands of this instruction are 450a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// loop invariant. We also filter out non-hoistable instructions here just for 451a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// efficiency. 452a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// 453a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattnerbool LICM::isLoopInvariantInst(Instruction &I) { 454a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // The instruction is loop invariant if all of its operands are loop-invariant 455a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) 4563280f7bd557250a448eb56edbddfc90c94a406e6Chris Lattner if (!CurLoop->isLoopInvariant(I.getOperand(i))) 457a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return false; 458a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 459ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner // If we got this far, the instruction is loop invariant! 460ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner return true; 461ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner} 462ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner 463a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// sink - When an instruction is found to only be used outside of the loop, 464a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner/// this function moves it to the exit blocks and patches up SSA form as needed. 465a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner/// This method is guaranteed to remove the original instruction from its 466a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner/// position, and may either delete it or move it to outside of the loop. 467a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// 468a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattnervoid LICM::sink(Instruction &I) { 469bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner DEBUG(errs() << "LICM sinking instruction: " << I); 470a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 471b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel SmallVector<BasicBlock*, 8> ExitBlocks; 4725fa802fe279f10f402e039bc931aa57c0e424bf5Chris Lattner CurLoop->getExitBlocks(ExitBlocks); 473df45bd3803ae0965a83cd1f30ee051b9f43e73ddChris Lattner 474df45bd3803ae0965a83cd1f30ee051b9f43e73ddChris Lattner if (isa<LoadInst>(I)) ++NumMovedLoads; 475118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner else if (isa<CallInst>(I)) ++NumMovedCalls; 476df45bd3803ae0965a83cd1f30ee051b9f43e73ddChris Lattner ++NumSunk; 477df45bd3803ae0965a83cd1f30ee051b9f43e73ddChris Lattner Changed = true; 478df45bd3803ae0965a83cd1f30ee051b9f43e73ddChris Lattner 479e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson LLVMContext &Context = I.getContext(); 480e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson 481a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // The case where there is only a single exit node of this loop is common 482a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // enough that we handle it as a special (more efficient) case. It is more 483a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // efficient to handle because there are no PHI nodes that need to be placed. 484a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (ExitBlocks.size() == 1) { 485a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (!isExitBlockDominatedByBlockInLoop(ExitBlocks[0], I.getParent())) { 486a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Instruction is not used, just delete it. 4872741c971044d2165be572749b94398043caccfebChris Lattner CurAST->deleteValue(&I); 48892f7365740e9a116c59a8d33e636ebf6e4699301Chris Lattner if (!I.use_empty()) // If I has users in unreachable blocks, eliminate. 4899e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson I.replaceAllUsesWith(UndefValue::get(I.getType())); 4903c80a51cfd5e7187439ce4c051da77ee46e0ff9aChris Lattner I.eraseFromParent(); 491a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } else { 492a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Move the instruction to the start of the exit block, after any PHI 493a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // nodes in it. 4943c80a51cfd5e7187439ce4c051da77ee46e0ff9aChris Lattner I.removeFromParent(); 495fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 49602dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = ExitBlocks[0]->getFirstNonPHI(); 497a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner ExitBlocks[0]->getInstList().insert(InsertPt, &I); 498a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 499303595942502f17c087fa28874c2b89117148c45Dan Gohman } else if (ExitBlocks.empty()) { 500a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // The instruction is actually dead if there ARE NO exit blocks. 5012741c971044d2165be572749b94398043caccfebChris Lattner CurAST->deleteValue(&I); 50292f7365740e9a116c59a8d33e636ebf6e4699301Chris Lattner if (!I.use_empty()) // If I has users in unreachable blocks, eliminate. 5039e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson I.replaceAllUsesWith(UndefValue::get(I.getType())); 5043c80a51cfd5e7187439ce4c051da77ee46e0ff9aChris Lattner I.eraseFromParent(); 505a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } else { 506a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Otherwise, if we have multiple exits, use the PromoteMem2Reg function to 507a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // do all of the hard work of inserting PHI nodes as necessary. We convert 508a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // the value into a stack object to get it to do this. 509a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 510a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Firstly, we create a stack object to hold the value... 511eaa243039b6a83f8915f4f96ced58fabb520c851Chris Lattner AllocaInst *AI = 0; 512a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 5131d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson if (I.getType() != Type::getVoidTy(I.getContext())) { 51450dead06ffc107edb7e84857baaeeb09039c631cOwen Anderson AI = new AllocaInst(I.getType(), 0, I.getName(), 515ecb7a77885b174cf4d001a9b48533b3979e7810dDan Gohman I.getParent()->getParent()->getEntryBlock().begin()); 516e7ae1a9dee1b023dbd5f7d6d1fbdb165fbbcb26cDevang Patel CurAST->add(AI); 517e7ae1a9dee1b023dbd5f7d6d1fbdb165fbbcb26cDevang Patel } 518fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 519a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Secondly, insert load instructions for each use of the instruction 520a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // outside of the loop. 521a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner while (!I.use_empty()) { 522a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner Instruction *U = cast<Instruction>(I.use_back()); 523a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 524a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // If the user is a PHI Node, we actually have to insert load instructions 525a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // in all predecessor blocks, not in the PHI block itself! 526a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (PHINode *UPN = dyn_cast<PHINode>(U)) { 527a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Only insert into each predecessor once, so that we don't have 528a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // different incoming values from the same block! 529a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner std::map<BasicBlock*, Value*> InsertedBlocks; 530a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner for (unsigned i = 0, e = UPN->getNumIncomingValues(); i != e; ++i) 531a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (UPN->getIncomingValue(i) == &I) { 532a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner BasicBlock *Pred = UPN->getIncomingBlock(i); 533a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner Value *&PredVal = InsertedBlocks[Pred]; 534a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (!PredVal) { 535a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Insert a new load instruction right before the terminator in 536a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // the predecessor block. 537a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner PredVal = new LoadInst(AI, "", Pred->getTerminator()); 538e7ae1a9dee1b023dbd5f7d6d1fbdb165fbbcb26cDevang Patel CurAST->add(cast<LoadInst>(PredVal)); 539a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 540a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 541a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner UPN->setIncomingValue(i, PredVal); 542a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 543a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 544a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } else { 545a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner LoadInst *L = new LoadInst(AI, "", U); 546a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner U->replaceUsesOfWith(&I, L); 547e7ae1a9dee1b023dbd5f7d6d1fbdb165fbbcb26cDevang Patel CurAST->add(L); 548a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 549a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 550a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 551a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Thirdly, insert a copy of the instruction in each exit block of the loop 552a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // that is dominated by the instruction, storing the result into the memory 553a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // location. Be careful not to insert the instruction into any particular 554a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // basic block more than once. 555a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner std::set<BasicBlock*> InsertedBlocks; 556a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner BasicBlock *InstOrigBB = I.getParent(); 557a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 558a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 559a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner BasicBlock *ExitBlock = ExitBlocks[i]; 560a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 561a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (isExitBlockDominatedByBlockInLoop(ExitBlock, InstOrigBB)) { 562a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // If we haven't already processed this exit block, do so now. 563e3cfe8d563fa06b274587aa38b1359ff707f33deChris Lattner if (InsertedBlocks.insert(ExitBlock).second) { 564a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Insert the code after the last PHI node... 56502dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = ExitBlock->getFirstNonPHI(); 566fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 567a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // If this is the first exit block processed, just move the original 568a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // instruction, otherwise clone the original instruction and insert 569a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // the copy. 570a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner Instruction *New; 5717d3ced934f1bb2c6845676c7333ef879d5219e88Chris Lattner if (InsertedBlocks.size() == 1) { 5723c80a51cfd5e7187439ce4c051da77ee46e0ff9aChris Lattner I.removeFromParent(); 573a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner ExitBlock->getInstList().insert(InsertPt, &I); 574a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner New = &I; 575a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } else { 576e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson New = I.clone(Context); 57770ac2dcb841dc62f08e16f0b0e2cefbf01baa4c5Chris Lattner CurAST->copyValue(&I, New); 578eaa243039b6a83f8915f4f96ced58fabb520c851Chris Lattner if (!I.getName().empty()) 579eaa243039b6a83f8915f4f96ced58fabb520c851Chris Lattner New->setName(I.getName()+".le"); 580a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner ExitBlock->getInstList().insert(InsertPt, New); 581a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 582fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 583a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Now that we have inserted the instruction, store it into the alloca 584eaa243039b6a83f8915f4f96ced58fabb520c851Chris Lattner if (AI) new StoreInst(New, AI, InsertPt); 585a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 586a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 587a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 588a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner 589a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner // If the instruction doesn't dominate any exit blocks, it must be dead. 590a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner if (InsertedBlocks.empty()) { 5912741c971044d2165be572749b94398043caccfebChris Lattner CurAST->deleteValue(&I); 5923c80a51cfd5e7187439ce4c051da77ee46e0ff9aChris Lattner I.eraseFromParent(); 593a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner } 594fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 595a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Finally, promote the fine value to SSA form. 596eaa243039b6a83f8915f4f96ced58fabb520c851Chris Lattner if (AI) { 597eaa243039b6a83f8915f4f96ced58fabb520c851Chris Lattner std::vector<AllocaInst*> Allocas; 598eaa243039b6a83f8915f4f96ced58fabb520c851Chris Lattner Allocas.push_back(AI); 5990a205a459884ec745df1c529396dd921f029dafdOwen Anderson PromoteMemToReg(Allocas, *DT, *DF, Context, CurAST); 600eaa243039b6a83f8915f4f96ced58fabb520c851Chris Lattner } 601a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 602a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner} 603952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 60494170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// hoist - When an instruction is found to only use loop invariant operands 60594170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// that is safe to hoist, this instruction is called to do the dirty work. 60694170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// 607a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattnervoid LICM::hoist(Instruction &I) { 608ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar DEBUG(errs() << "LICM hoisting to " << Preheader->getName() << ": " << I); 609ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner 61099a57216a935a512c418032f590a4660bad9d846Chris Lattner // Remove the instruction from its current basic block... but don't delete the 61199a57216a935a512c418032f590a4660bad9d846Chris Lattner // instruction. 6123c80a51cfd5e7187439ce4c051da77ee46e0ff9aChris Lattner I.removeFromParent(); 613e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 6149646e6b6af1f924f9366a2bffc6dde102f84d231Chris Lattner // Insert the new node in Preheader, before the terminator. 615a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner Preheader->getInstList().insert(Preheader->getTerminator(), &I); 616fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 617a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (isa<LoadInst>(I)) ++NumMovedLoads; 618118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner else if (isa<CallInst>(I)) ++NumMovedCalls; 6199646e6b6af1f924f9366a2bffc6dde102f84d231Chris Lattner ++NumHoisted; 620e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner Changed = true; 621e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner} 622e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 623a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// isSafeToExecuteUnconditionally - Only sink or hoist an instruction if it is 624a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// not a trapping instruction or if it is a trapping instruction and is 625a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// guaranteed to execute. 6269966c03aad031f738718bed3bc00371e358beb5dTanya Lattner/// 627a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattnerbool LICM::isSafeToExecuteUnconditionally(Instruction &Inst) { 62892094b4d928119eceac1484331acffe950f4651cChris Lattner // If it is not a trapping instruction, it is always safe to hoist. 6290b79a7727d68a507837e827803859424cf3d997bEli Friedman if (Inst.isSafeToSpeculativelyExecute()) 6300b79a7727d68a507837e827803859424cf3d997bEli Friedman return true; 631fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 63292094b4d928119eceac1484331acffe950f4651cChris Lattner // Otherwise we have to check to make sure that the instruction dominates all 63392094b4d928119eceac1484331acffe950f4651cChris Lattner // of the exit blocks. If it doesn't, then there is a path out of the loop 63492094b4d928119eceac1484331acffe950f4651cChris Lattner // which does not execute this instruction, so we can't hoist it. 63592094b4d928119eceac1484331acffe950f4651cChris Lattner 63692094b4d928119eceac1484331acffe950f4651cChris Lattner // If the instruction is in the header block for the loop (which is very 63792094b4d928119eceac1484331acffe950f4651cChris Lattner // common), it is always guaranteed to dominate the exit blocks. Since this 63892094b4d928119eceac1484331acffe950f4651cChris Lattner // is a common case, and can save some work, check it now. 639a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (Inst.getParent() == CurLoop->getHeader()) 64092094b4d928119eceac1484331acffe950f4651cChris Lattner return true; 64192094b4d928119eceac1484331acffe950f4651cChris Lattner 64292094b4d928119eceac1484331acffe950f4651cChris Lattner // Get the exit blocks for the current loop. 643b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel SmallVector<BasicBlock*, 8> ExitBlocks; 6445fa802fe279f10f402e039bc931aa57c0e424bf5Chris Lattner CurLoop->getExitBlocks(ExitBlocks); 6459966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 6463a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson // For each exit block, get the DT node and walk up the DT until the 64792094b4d928119eceac1484331acffe950f4651cChris Lattner // instruction's basic block is found or we exit the loop. 648a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 649a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (!isExitBlockDominatedByBlockInLoop(ExitBlocks[i], Inst.getParent())) 650a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return false; 651fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 6529966c03aad031f738718bed3bc00371e358beb5dTanya Lattner return true; 6539966c03aad031f738718bed3bc00371e358beb5dTanya Lattner} 6549966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 655eb53ae4f2dc39e75e725b21b52d77d29cf1c11c9Chris Lattner 6562e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// PromoteValuesInLoop - Try to promote memory values to scalars by sinking 6572e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// stores out of the loop and moving loads to before the loop. We do this by 6582e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// looping over the stores in the loop, looking for stores to Must pointers 6592e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// which are loop invariant. We promote these memory locations to use allocas 6602e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// instead. These allocas can easily be raised to register values by the 6612e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// PromoteMem2Reg functionality. 6622e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// 6632e6e741b737960ecd0b68610875050019aac0f07Chris Lattnervoid LICM::PromoteValuesInLoop() { 6642e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // PromotedValues - List of values that are promoted out of the loop. Each 665065a616adad624152618b1b0084ff074e5b03bbbChris Lattner // value has an alloca instruction for it, and a canonical version of the 6662e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // pointer. 6672e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::vector<std::pair<AllocaInst*, Value*> > PromotedValues; 6682e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::map<Value*, AllocaInst*> ValueToAllocaMap; // Map of ptr to alloca 6692e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 670fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner FindPromotableValuesInLoop(PromotedValues, ValueToAllocaMap); 671fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner if (ValueToAllocaMap.empty()) return; // If there are values to promote. 6722e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 6732e6e741b737960ecd0b68610875050019aac0f07Chris Lattner Changed = true; 6742e6e741b737960ecd0b68610875050019aac0f07Chris Lattner NumPromoted += PromotedValues.size(); 6752e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 676fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner std::vector<Value*> PointerValueNumbers; 677fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner 6782e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Emit a copy from the value into the alloca'd value in the loop preheader 6792e6e741b737960ecd0b68610875050019aac0f07Chris Lattner TerminatorInst *LoopPredInst = Preheader->getTerminator(); 6802e6e741b737960ecd0b68610875050019aac0f07Chris Lattner for (unsigned i = 0, e = PromotedValues.size(); i != e; ++i) { 681fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner Value *Ptr = PromotedValues[i].second; 682fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner 683fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // If we are promoting a pointer value, update alias information for the 684fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // inserted load. 685fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner Value *LoadValue = 0; 686fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner if (isa<PointerType>(cast<PointerType>(Ptr->getType())->getElementType())) { 687fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // Locate a load or store through the pointer, and assign the same value 688fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // to LI as we are loading or storing. Since we know that the value is 689fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // stored in this loop, this will always succeed. 690fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner for (Value::use_iterator UI = Ptr->use_begin(), E = Ptr->use_end(); 691fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner UI != E; ++UI) 692fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { 693fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner LoadValue = LI; 694fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner break; 695fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) { 696bdacd879578943efc98b75639cb8e7b4aab037f9Chris Lattner if (SI->getOperand(1) == Ptr) { 697fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner LoadValue = SI->getOperand(0); 698fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner break; 699fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner } 700fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner } 701fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner assert(LoadValue && "No store through the pointer found!"); 702fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner PointerValueNumbers.push_back(LoadValue); // Remember this for later. 703fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner } 704fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner 705fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // Load from the memory we are promoting. 706fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner LoadInst *LI = new LoadInst(Ptr, Ptr->getName()+".promoted", LoopPredInst); 707fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner 708fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner if (LoadValue) CurAST->copyValue(LoadValue, LI); 709fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner 710fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // Store into the temporary alloca. 7112e6e741b737960ecd0b68610875050019aac0f07Chris Lattner new StoreInst(LI, PromotedValues[i].first, LoopPredInst); 7122e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 713fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 7142e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Scan the basic blocks in the loop, replacing uses of our pointers with 7150ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner // uses of the allocas in question. 7162e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // 7179b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman for (Loop::block_iterator I = CurLoop->block_begin(), 7189b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman E = CurLoop->block_end(); I != E; ++I) { 7199b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman BasicBlock *BB = *I; 7202e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Rewrite all loads and stores in the block of the pointer... 7219b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ++II) { 722e408e25132b8de8c757db1e3ddcd70432dfeb24dChris Lattner if (LoadInst *L = dyn_cast<LoadInst>(II)) { 7232e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::map<Value*, AllocaInst*>::iterator 7242e6e741b737960ecd0b68610875050019aac0f07Chris Lattner I = ValueToAllocaMap.find(L->getOperand(0)); 7252e6e741b737960ecd0b68610875050019aac0f07Chris Lattner if (I != ValueToAllocaMap.end()) 7262e6e741b737960ecd0b68610875050019aac0f07Chris Lattner L->setOperand(0, I->second); // Rewrite load instruction... 727e408e25132b8de8c757db1e3ddcd70432dfeb24dChris Lattner } else if (StoreInst *S = dyn_cast<StoreInst>(II)) { 7282e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::map<Value*, AllocaInst*>::iterator 7292e6e741b737960ecd0b68610875050019aac0f07Chris Lattner I = ValueToAllocaMap.find(S->getOperand(1)); 7302e6e741b737960ecd0b68610875050019aac0f07Chris Lattner if (I != ValueToAllocaMap.end()) 7312e6e741b737960ecd0b68610875050019aac0f07Chris Lattner S->setOperand(1, I->second); // Rewrite store instruction... 7322e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 7332e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 7340ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner } 7352e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 7360ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner // Now that the body of the loop uses the allocas instead of the original 7370ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner // memory locations, insert code to copy the alloca value back into the 7380ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner // original memory location on all exits from the loop. Note that we only 7390ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner // want to insert one copy of the code in each exit block, though the loop may 7400ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner // exit to the same block more than once. 7410ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner // 74219d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner SmallPtrSet<BasicBlock*, 16> ProcessedBlocks; 7430ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner 744b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel SmallVector<BasicBlock*, 8> ExitBlocks; 7455fa802fe279f10f402e039bc931aa57c0e424bf5Chris Lattner CurLoop->getExitBlocks(ExitBlocks); 74619d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 74719d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner if (!ProcessedBlocks.insert(ExitBlocks[i])) 74819d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner continue; 74919d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner 75019d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner // Copy all of the allocas into their memory locations. 75102dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator BI = ExitBlocks[i]->getFirstNonPHI(); 75219d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner Instruction *InsertPos = BI; 75319d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner unsigned PVN = 0; 75419d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner for (unsigned i = 0, e = PromotedValues.size(); i != e; ++i) { 75519d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner // Load from the alloca. 75619d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner LoadInst *LI = new LoadInst(PromotedValues[i].first, "", InsertPos); 75719d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner 75819d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner // If this is a pointer type, update alias info appropriately. 75919d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner if (isa<PointerType>(LI->getType())) 76019d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner CurAST->copyValue(PointerValueNumbers[PVN++], LI); 76119d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner 76219d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner // Store into the memory we promoted. 76319d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner new StoreInst(LI, PromotedValues[i].second, InsertPos); 7640ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner } 76519d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner } 7662e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 7672e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Now that we have done the deed, use the mem2reg functionality to promote 768fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // all of the new allocas we just created into real SSA registers. 7692e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // 7702e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::vector<AllocaInst*> PromotedAllocas; 7712e6e741b737960ecd0b68610875050019aac0f07Chris Lattner PromotedAllocas.reserve(PromotedValues.size()); 7722e6e741b737960ecd0b68610875050019aac0f07Chris Lattner for (unsigned i = 0, e = PromotedValues.size(); i != e; ++i) 7732e6e741b737960ecd0b68610875050019aac0f07Chris Lattner PromotedAllocas.push_back(PromotedValues[i].first); 774e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson PromoteMemToReg(PromotedAllocas, *DT, *DF, Preheader->getContext(), CurAST); 7752e6e741b737960ecd0b68610875050019aac0f07Chris Lattner} 7762e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 777fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner/// FindPromotableValuesInLoop - Check the current loop for stores to definite 778f2038b1d9325b23e73a20b57fcb3508f4dda1817Devang Patel/// pointers, which are not loaded and stored through may aliases and are safe 779f2038b1d9325b23e73a20b57fcb3508f4dda1817Devang Patel/// for promotion. If these are found, create an alloca for the value, add it 780f2038b1d9325b23e73a20b57fcb3508f4dda1817Devang Patel/// to the PromotedValues list, and keep track of the mapping from value to 781f2038b1d9325b23e73a20b57fcb3508f4dda1817Devang Patel/// alloca. 782fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattnervoid LICM::FindPromotableValuesInLoop( 7832e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::vector<std::pair<AllocaInst*, Value*> > &PromotedValues, 7842e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::map<Value*, AllocaInst*> &ValueToAllocaMap) { 7852e6e741b737960ecd0b68610875050019aac0f07Chris Lattner Instruction *FnStart = CurLoop->getHeader()->getParent()->begin()->begin(); 7862e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 787fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // Loop over all of the alias sets in the tracker object. 7880252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); 7890252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner I != E; ++I) { 7900252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner AliasSet &AS = *I; 7910252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner // We can promote this alias set if it has a store, if it is a "Must" alias 792fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // set, if the pointer is loop invariant, and if we are not eliminating any 793118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner // volatile loads or stores. 79429d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() || 795d7168ddb116c2e9aa1f8325ae887eb63d6003037Chris Lattner AS.isVolatile() || !CurLoop->isLoopInvariant(AS.begin()->getValue())) 79629d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner continue; 79729d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner 79829d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner assert(!AS.empty() && 79929d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner "Must alias set should have at least one pointer element in it!"); 800d7168ddb116c2e9aa1f8325ae887eb63d6003037Chris Lattner Value *V = AS.begin()->getValue(); 80129d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner 80229d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner // Check that all of the pointers in the alias set have the same type. We 80329d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner // cannot (yet) promote a memory location that is loaded and stored in 80429d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner // different sizes. 80529d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner { 8060252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner bool PointerOk = true; 8070252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I) 808d7168ddb116c2e9aa1f8325ae887eb63d6003037Chris Lattner if (V->getType() != I->getValue()->getType()) { 8090252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner PointerOk = false; 8100252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner break; 8112e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 81229d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner if (!PointerOk) 81329d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner continue; 81429d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner } 8150252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner 81619d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner // It isn't safe to promote a load/store from the loop if the load/store is 81719d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner // conditional. For example, turning: 81819d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner // 81919d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner // for () { if (c) *P += 1; } 82019d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner // 82119d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner // into: 82219d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner // 82319d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner // tmp = *P; for () { if (c) tmp +=1; } *P = tmp; 82419d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner // 82519d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner // is not safe, because *P may only be valid to access if 'c' is true. 82619d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner // 82719d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner // It is safe to promote P if all uses are direct load/stores and if at 82819d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner // least one is guaranteed to be executed. 82919d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner bool GuaranteedToExecute = false; 83019d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner bool InvalidInst = false; 83119d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); 83219d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner UI != UE; ++UI) { 83319d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner // Ignore instructions not in this loop. 83429d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner Instruction *Use = dyn_cast<Instruction>(*UI); 83529d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner if (!Use || !CurLoop->contains(Use->getParent())) 83629d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner continue; 837bc2265abe1d1b830995bb2f6322409bc7d7c5740Devang Patel 83819d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner if (!isa<LoadInst>(Use) && !isa<StoreInst>(Use)) { 83919d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner InvalidInst = true; 84029d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner break; 84119d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner } 84219d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner 84319d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner if (!GuaranteedToExecute) 84419d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner GuaranteedToExecute = isSafeToExecuteUnconditionally(*Use); 84529d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner } 846bc2265abe1d1b830995bb2f6322409bc7d7c5740Devang Patel 84719d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner // If there is an non-load/store instruction in the loop, we can't promote 84819d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner // it. If there isn't a guaranteed-to-execute instruction, we can't 84919d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner // promote. 85019d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner if (InvalidInst || !GuaranteedToExecute) 85129d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner continue; 85229d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner 85329d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner const Type *Ty = cast<PointerType>(V->getType())->getElementType(); 85450dead06ffc107edb7e84857baaeeb09039c631cOwen Anderson AllocaInst *AI = new AllocaInst(Ty, 0, V->getName()+".tmp", FnStart); 85529d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner PromotedValues.push_back(std::make_pair(AI, V)); 856fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner 85729d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner // Update the AST and alias analysis. 85829d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner CurAST->copyValue(V, AI); 859fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 86029d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I) 861d7168ddb116c2e9aa1f8325ae887eb63d6003037Chris Lattner ValueToAllocaMap.insert(std::make_pair(I->getValue(), AI)); 862fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 863bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner DEBUG(errs() << "LICM: Promoting value: " << *V << "\n"); 8642e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 865f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner} 86691d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel 86791d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel/// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info. 86891d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patelvoid LICM::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L) { 86991d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel AliasSetTracker *AST = LoopToAliasMap[L]; 87091d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel if (!AST) 87191d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel return; 87291d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel 87391d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel AST->copyValue(From, To); 87491d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel} 87591d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel 87691d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel/// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias 87791d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel/// set. 87891d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patelvoid LICM::deleteAnalysisValue(Value *V, Loop *L) { 87991d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel AliasSetTracker *AST = LoopToAliasMap[L]; 88091d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel if (!AST) 88191d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel return; 88291d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel 88391d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel AST->deleteValue(V); 88491d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel} 885