LICM.cpp revision 79066fa6acce02c97c714a5a6e151ed8a249721c
1e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner//===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source 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" 392741c971044d2165be572749b94398043caccfebChris Lattner#include "llvm/Target/TargetData.h" 40e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include "llvm/Analysis/LoopInfo.h" 41f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner#include "llvm/Analysis/AliasAnalysis.h" 420252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner#include "llvm/Analysis/AliasSetTracker.h" 43952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner#include "llvm/Analysis/Dominators.h" 442e6e741b737960ecd0b68610875050019aac0f07Chris Lattner#include "llvm/Support/CFG.h" 452741c971044d2165be572749b94398043caccfebChris Lattner#include "llvm/Transforms/Utils/PromoteMemToReg.h" 46551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 47551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 48551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 49e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include <algorithm> 5092094b4d928119eceac1484331acffe950f4651cChris Lattnerusing namespace llvm; 51d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 520e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumSunk , "Number of instructions sunk out of loop"); 530e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumHoisted , "Number of instructions hoisted out of loop"); 540e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk"); 550e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk"); 560e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumPromoted , "Number of memory locations promoted to registers"); 570e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattner 58e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattnernamespace { 594a650af59912110a246c0a041bff38c92f0e56a2Chris Lattner cl::opt<bool> 604a650af59912110a246c0a041bff38c92f0e56a2Chris Lattner DisablePromotion("disable-licm-promotion", cl::Hidden, 614a650af59912110a246c0a041bff38c92f0e56a2Chris Lattner cl::desc("Disable memory promotion in LICM pass")); 622e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 63ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner struct LICM : public FunctionPass { 647e70829632f82de15db187845666aaca6e04b792Chris Lattner virtual bool runOnFunction(Function &F); 65e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 6694170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// This transformation requires natural loop information & requires that 6794170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// loop preheaders be inserted into the CFG... 6894170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// 69e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 70cb2610ea037a17115ef3a01a6bdaab4e3cfdca27Chris Lattner AU.setPreservesCFG(); 7198bf436e2e2ab463d79c54a42a46b12028905330Chris Lattner AU.addRequiredID(LoopSimplifyID); 725f0eb8da62308126d5b61e3eee5bee75b9dc5194Chris Lattner AU.addRequired<LoopInfo>(); 73952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner AU.addRequired<DominatorTree>(); 740252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner AU.addRequired<DominanceFrontier>(); // For scalar promotion (mem2reg) 75f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner AU.addRequired<AliasAnalysis>(); 76e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } 77e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 78e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner private: 7992094b4d928119eceac1484331acffe950f4651cChris Lattner // Various analyses that we use... 802e6e741b737960ecd0b68610875050019aac0f07Chris Lattner AliasAnalysis *AA; // Current AliasAnalysis information 8192094b4d928119eceac1484331acffe950f4651cChris Lattner LoopInfo *LI; // Current LoopInfo 8292094b4d928119eceac1484331acffe950f4651cChris Lattner DominatorTree *DT; // Dominator Tree for the current Loop... 8343f820d1f7638656be2158efac7dd8f5b08b8b77Chris Lattner DominanceFrontier *DF; // Current Dominance Frontier 8492094b4d928119eceac1484331acffe950f4651cChris Lattner 8592094b4d928119eceac1484331acffe950f4651cChris Lattner // State that is updated as we process loops 862e6e741b737960ecd0b68610875050019aac0f07Chris Lattner bool Changed; // Set to true when we change anything. 872e6e741b737960ecd0b68610875050019aac0f07Chris Lattner BasicBlock *Preheader; // The preheader block of the current loop... 882e6e741b737960ecd0b68610875050019aac0f07Chris Lattner Loop *CurLoop; // The current loop we are working on... 890252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner AliasSetTracker *CurAST; // AliasSet information for the current loop... 90e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 91fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman /// visitLoop - Hoist expressions out of the specified loop... 9294170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// 930252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner void visitLoop(Loop *L, AliasSetTracker &AST); 94e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 95e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner /// SinkRegion - Walk the specified region of the CFG (defined by all blocks 96e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner /// dominated by the specified block, and that are in the current loop) in 97e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner /// reverse depth first order w.r.t the DominatorTree. This allows us to 98e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner /// visit uses before definitions, allowing us to sink a loop body in one 99e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner /// pass without iteration. 100e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner /// 101e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner void SinkRegion(DominatorTree::Node *N); 102e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 103952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// HoistRegion - Walk the specified region of the CFG (defined by all 104952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// blocks dominated by the specified block, and that are in the current 105952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// loop) in depth first order w.r.t the DominatorTree. This allows us to 106cf00c4ab3ba308d45d98c5ccab87362cf802facbMisha Brukman /// visit definitions before uses, allowing us to hoist a loop body in one 107952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// pass without iteration. 108952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// 109952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner void HoistRegion(DominatorTree::Node *N); 110952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 111b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner /// inSubLoop - Little predicate that returns true if the specified basic 112b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner /// block is in a subloop of the current one, not the current one itself. 11394170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// 114b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner bool inSubLoop(BasicBlock *BB) { 115b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop"); 116329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner for (Loop::iterator I = CurLoop->begin(), E = CurLoop->end(); I != E; ++I) 117329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner if ((*I)->contains(BB)) 118b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner return true; // A subloop actually contains this block! 119b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner return false; 120e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } 121e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 122a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// isExitBlockDominatedByBlockInLoop - This method checks to see if the 123a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// specified exit block of the loop is dominated by the specified block 124a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// that is in the body of the loop. We use these constraints to 125a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// dramatically limit the amount of the dominator tree that needs to be 126a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// searched. 127a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner bool isExitBlockDominatedByBlockInLoop(BasicBlock *ExitBlock, 128a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner BasicBlock *BlockInLoop) const { 129a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // If the block in the loop is the loop header, it must be dominated! 130a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner BasicBlock *LoopHeader = CurLoop->getHeader(); 131a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (BlockInLoop == LoopHeader) 132a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return true; 133fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 134a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner DominatorTree::Node *BlockInLoopNode = DT->getNode(BlockInLoop); 135a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner DominatorTree::Node *IDom = DT->getNode(ExitBlock); 136fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 137a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Because the exit block is not in the loop, we know we have to get _at 1382741c971044d2165be572749b94398043caccfebChris Lattner // least_ its immediate dominator. 139a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner do { 140a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Get next Immediate Dominator. 141a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner IDom = IDom->getIDom(); 142fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 143a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // If we have got to the header of the loop, then the instructions block 144a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // did not dominate the exit node, so we can't hoist it. 145a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (IDom->getBlock() == LoopHeader) 146a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return false; 147fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 148a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } while (IDom != BlockInLoopNode); 149a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 150a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return true; 151a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 152a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 153a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// sink - When an instruction is found to only be used outside of the loop, 154a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// this function moves it to the exit blocks and patches up SSA form as 155a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// needed. 156a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// 157a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner void sink(Instruction &I); 158a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 15994170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// hoist - When an instruction is found to only use loop invariant operands 16094170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// that is safe to hoist, this instruction is called to do the dirty work. 16194170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// 1627e70829632f82de15db187845666aaca6e04b792Chris Lattner void hoist(Instruction &I); 163e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 164a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// isSafeToExecuteUnconditionally - Only sink or hoist an instruction if it 165a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// is not a trapping instruction or if it is a trapping instruction and is 166a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// guaranteed to execute. 1679966c03aad031f738718bed3bc00371e358beb5dTanya Lattner /// 168a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner bool isSafeToExecuteUnconditionally(Instruction &I); 1699966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 17094170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// pointerInvalidatedByLoop - Return true if the body of this loop may 17194170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// store into the memory location pointed to by V. 172fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman /// 173f3e1d6977ee5fb6b66df314d65e28e2c35d6e244Chris Lattner bool pointerInvalidatedByLoop(Value *V, unsigned Size) { 1740252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner // Check to see if any of the basic blocks in CurLoop invalidate *V. 175f3e1d6977ee5fb6b66df314d65e28e2c35d6e244Chris Lattner return CurAST->getAliasSetForPointer(V, Size).isMod(); 1762e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 177f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner 178a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner bool canSinkOrHoistInst(Instruction &I); 179a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner bool isLoopInvariantInst(Instruction &I); 180a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner bool isNotUsedInLoop(Instruction &I); 181e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 1822e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// PromoteValuesInLoop - Look at the stores in the loop and promote as many 1832e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// to scalars as we can. 1842e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// 1852e6e741b737960ecd0b68610875050019aac0f07Chris Lattner void PromoteValuesInLoop(); 1862e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 187fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner /// FindPromotableValuesInLoop - Check the current loop for stores to 188352361b409d16045e703d986aa7fd77295173ef3Misha Brukman /// definite pointers, which are not loaded and stored through may aliases. 1892e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// If these are found, create an alloca for the value, add it to the 1902e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// PromotedValues list, and keep track of the mapping from value to 1912e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// alloca... 1922e6e741b737960ecd0b68610875050019aac0f07Chris Lattner /// 193fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner void FindPromotableValuesInLoop( 1942e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::vector<std::pair<AllocaInst*, Value*> > &PromotedValues, 1952e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::map<Value*, AllocaInst*> &Val2AlMap); 196e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner }; 197f629309f74cf1a64aa7fd1cd5784fd7db9a8f59eChris Lattner 1987f8897f22e88271cfa114998a4d6088e7c8e8e11Chris Lattner RegisterPass<LICM> X("licm", "Loop Invariant Code Motion"); 199e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner} 200e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 20192094b4d928119eceac1484331acffe950f4651cChris LattnerFunctionPass *llvm::createLICMPass() { return new LICM(); } 202e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 20394170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// runOnFunction - For LICM, this simply traverses the loop structure of the 20494170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// function, hoisting expressions out of loops if possible. 20594170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// 20656b7ee20dad7160a117ea0d102fc5432074ce2d0Chris Lattnerbool LICM::runOnFunction(Function &) { 2072e6e741b737960ecd0b68610875050019aac0f07Chris Lattner Changed = false; 208e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 2092e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Get our Loop and Alias Analysis information... 2102e6e741b737960ecd0b68610875050019aac0f07Chris Lattner LI = &getAnalysis<LoopInfo>(); 211f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner AA = &getAnalysis<AliasAnalysis>(); 21243f820d1f7638656be2158efac7dd8f5b08b8b77Chris Lattner DF = &getAnalysis<DominanceFrontier>(); 21311a49a722f657294f38865019af51f82dc31c1c3Tanya Lattner DT = &getAnalysis<DominatorTree>(); 214f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner 2152e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Hoist expressions out of all of the top-level loops. 216329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) { 2170252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner AliasSetTracker AST(*AA); 218ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner visitLoop(*I, AST); 2192e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 220e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner return Changed; 221e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner} 222e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 22394170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner 224fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman/// visitLoop - Hoist expressions out of the specified loop... 22594170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// 2260252e49f6d6973b6f347c8feafc49e28af27163aChris Lattnervoid LICM::visitLoop(Loop *L, AliasSetTracker &AST) { 227e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Recurse through all subloops before we process this loop... 228329c1c6c949d07e3fe9722ec633b4258217fd99dChris Lattner for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) { 2290252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner AliasSetTracker SubAST(*AA); 230ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner visitLoop(*I, SubAST); 2312e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 2322e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Incorporate information about the subloops into this loop... 2330252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner AST.add(SubAST); 2342e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 235e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner CurLoop = L; 2360252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner CurAST = &AST; 237e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 23899a57216a935a512c418032f590a4660bad9d846Chris Lattner // Get the preheader block to move instructions into... 23999a57216a935a512c418032f590a4660bad9d846Chris Lattner Preheader = L->getLoopPreheader(); 24099a57216a935a512c418032f590a4660bad9d846Chris Lattner assert(Preheader&&"Preheader insertion pass guarantees we have a preheader!"); 24199a57216a935a512c418032f590a4660bad9d846Chris Lattner 2422e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Loop over the body of this loop, looking for calls, invokes, and stores. 2430252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner // Because subloops have already been incorporated into AST, we skip blocks in 2442e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // subloops. 2452e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // 246a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner for (std::vector<BasicBlock*>::const_iterator I = L->getBlocks().begin(), 247a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner E = L->getBlocks().end(); I != E; ++I) 2482e6e741b737960ecd0b68610875050019aac0f07Chris Lattner if (LI->getLoopFor(*I) == L) // Ignore blocks in subloops... 2490252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner AST.add(**I); // Incorporate the specified basic block 2502e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 251e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // We want to visit all of the instructions in this loop... that are not parts 252e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // of our subloops (they have already had their invariants hoisted out of 253e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // their loop, into this loop, so there is no need to process the BODIES of 254e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // the subloops). 255e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // 256952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner // Traverse the body of the loop in depth first order on the dominator tree so 257952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner // that we are guaranteed to see definitions before we see uses. This allows 258e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // us to sink instructions in one pass, without iteration. AFter sinking 259e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // instructions, we perform another pass to hoist them out of the loop. 260952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner // 261e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner SinkRegion(DT->getNode(L->getHeader())); 26211a49a722f657294f38865019af51f82dc31c1c3Tanya Lattner HoistRegion(DT->getNode(L->getHeader())); 263e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 2642e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Now that all loop invariants have been removed from the loop, promote any 2652e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // memory references to scalars that we can... 2662e6e741b737960ecd0b68610875050019aac0f07Chris Lattner if (!DisablePromotion) 2672e6e741b737960ecd0b68610875050019aac0f07Chris Lattner PromoteValuesInLoop(); 2682e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 269e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Clear out loops state information for the next iteration 270e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner CurLoop = 0; 27199a57216a935a512c418032f590a4660bad9d846Chris Lattner Preheader = 0; 272e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner} 273e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 274e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner/// SinkRegion - Walk the specified region of the CFG (defined by all blocks 275e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner/// dominated by the specified block, and that are in the current loop) in 276e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner/// reverse depth first order w.r.t the DominatorTree. This allows us to visit 277e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner/// uses before definitions, allowing us to sink a loop body in one pass without 278e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner/// iteration. 279e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner/// 280e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattnervoid LICM::SinkRegion(DominatorTree::Node *N) { 281e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner assert(N != 0 && "Null dominator tree node?"); 282e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner BasicBlock *BB = N->getBlock(); 283e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 284e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // If this subregion is not in the top level loop at all, exit. 285e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner if (!CurLoop->contains(BB)) return; 286e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 287e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // We are processing blocks in reverse dfo, so process children first... 288e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner const std::vector<DominatorTree::Node*> &Children = N->getChildren(); 289e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner for (unsigned i = 0, e = Children.size(); i != e; ++i) 290e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner SinkRegion(Children[i]); 291e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 292e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // Only need to process the contents of this block if it is not part of a 293e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // subloop (which would already have been processed). 294e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner if (inSubLoop(BB)) return; 295e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 296a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner for (BasicBlock::iterator II = BB->end(); II != BB->begin(); ) { 297a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner Instruction &I = *--II; 298fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 299e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // Check to see if we can sink this instruction to the exit blocks 300e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // of the loop. We can do this if the all users of the instruction are 301e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // outside of the loop. In this case, it doesn't even matter if the 302e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // operands of the instruction are loop invariant. 303e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // 30470ac2dcb841dc62f08e16f0b0e2cefbf01baa4c5Chris Lattner if (isNotUsedInLoop(I) && canSinkOrHoistInst(I)) { 305a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner ++II; 306e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner sink(I); 307a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner } 308e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner } 309e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner} 310e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 311e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 312952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner/// HoistRegion - Walk the specified region of the CFG (defined by all blocks 313952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner/// dominated by the specified block, and that are in the current loop) in depth 314cf00c4ab3ba308d45d98c5ccab87362cf802facbMisha Brukman/// first order w.r.t the DominatorTree. This allows us to visit definitions 315952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner/// before uses, allowing us to hoist a loop body in one pass without iteration. 316952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner/// 317952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattnervoid LICM::HoistRegion(DominatorTree::Node *N) { 318952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner assert(N != 0 && "Null dominator tree node?"); 319ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner BasicBlock *BB = N->getBlock(); 320952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 321b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner // If this subregion is not in the top level loop at all, exit. 322ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner if (!CurLoop->contains(BB)) return; 323952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 324a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Only need to process the contents of this block if it is not part of a 325a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // subloop (which would already have been processed). 326ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner if (!inSubLoop(BB)) 327a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) { 328a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner Instruction &I = *II++; 329fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 330e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // Try hoisting the instruction out to the preheader. We can only do this 331e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // if all of the operands of the instruction are loop invariant and if it 332e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // is safe to hoist the instruction. 333e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // 334fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman if (isLoopInvariantInst(I) && canSinkOrHoistInst(I) && 335e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner isSafeToExecuteUnconditionally(I)) 3363c80a51cfd5e7187439ce4c051da77ee46e0ff9aChris Lattner hoist(I); 337a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 338952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 339952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner const std::vector<DominatorTree::Node*> &Children = N->getChildren(); 340952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner for (unsigned i = 0, e = Children.size(); i != e; ++i) 34156b7ee20dad7160a117ea0d102fc5432074ce2d0Chris Lattner HoistRegion(Children[i]); 342952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner} 343952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 344a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// canSinkOrHoistInst - Return true if the hoister and sinker can handle this 345a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// instruction. 346a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// 347a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattnerbool LICM::canSinkOrHoistInst(Instruction &I) { 348ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner // Loads have extra constraints we have to verify before we can hoist them. 349ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(&I)) { 350ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner if (LI->isVolatile()) 351ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner return false; // Don't hoist volatile loads! 352ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner 353ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner // Don't hoist loads which have may-aliased stores in loop. 354f3e1d6977ee5fb6b66df314d65e28e2c35d6e244Chris Lattner unsigned Size = 0; 355f3e1d6977ee5fb6b66df314d65e28e2c35d6e244Chris Lattner if (LI->getType()->isSized()) 356f3e1d6977ee5fb6b66df314d65e28e2c35d6e244Chris Lattner Size = AA->getTargetData().getTypeSize(LI->getType()); 357f3e1d6977ee5fb6b66df314d65e28e2c35d6e244Chris Lattner return !pointerInvalidatedByLoop(LI->getOperand(0), Size); 358118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner } else if (CallInst *CI = dyn_cast<CallInst>(&I)) { 359118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner // Handle obvious cases efficiently. 360118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner if (Function *Callee = CI->getCalledFunction()) { 36168a9d3eb38d78e851cce532ffa307a89373036c6Chris Lattner AliasAnalysis::ModRefBehavior Behavior =AA->getModRefBehavior(Callee, CI); 36268a9d3eb38d78e851cce532ffa307a89373036c6Chris Lattner if (Behavior == AliasAnalysis::DoesNotAccessMemory) 363118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner return true; 36468a9d3eb38d78e851cce532ffa307a89373036c6Chris Lattner else if (Behavior == AliasAnalysis::OnlyReadsMemory) { 365118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner // If this call only reads from memory and there are no writes to memory 366118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner // in the loop, we can hoist or sink the call as appropriate. 367118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner bool FoundMod = false; 368118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); 369118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner I != E; ++I) { 370118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner AliasSet &AS = *I; 371118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner if (!AS.isForwardingAliasSet() && AS.isMod()) { 372118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner FoundMod = true; 373118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner break; 374118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner } 375118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner } 376118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner if (!FoundMod) return true; 377118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner } 378118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner } 379118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner 380118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner // FIXME: This should use mod/ref information to see if we can hoist or sink 381118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner // the call. 382fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 383118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner return false; 384ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner } 385ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner 3863da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer // Otherwise these instructions are hoistable/sinkable 387fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman return isa<BinaryOperator>(I) || isa<ShiftInst>(I) || isa<CastInst>(I) || 388e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer isa<SelectInst>(I) || isa<GetElementPtrInst>(I) || isa<CmpInst>(I); 389a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner} 390a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 391a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// isNotUsedInLoop - Return true if the only users of this instruction are 392a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// outside of the loop. If this is true, we can sink the instruction to the 393a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// exit blocks of the loop. 394a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// 395a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattnerbool LICM::isNotUsedInLoop(Instruction &I) { 396ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); UI != E; ++UI) { 397ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner Instruction *User = cast<Instruction>(*UI); 398ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner if (PHINode *PN = dyn_cast<PHINode>(User)) { 399ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner // PHI node uses occur in predecessor blocks! 400ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 401ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner if (PN->getIncomingValue(i) == &I) 402ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner if (CurLoop->contains(PN->getIncomingBlock(i))) 403ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner return false; 404ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner } else if (CurLoop->contains(User->getParent())) { 405a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return false; 406ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner } 407ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner } 408a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return true; 409a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner} 410a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 411a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 412a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// isLoopInvariantInst - Return true if all operands of this instruction are 413a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// loop invariant. We also filter out non-hoistable instructions here just for 414a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// efficiency. 415a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// 416a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattnerbool LICM::isLoopInvariantInst(Instruction &I) { 417a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // The instruction is loop invariant if all of its operands are loop-invariant 418a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) 4193280f7bd557250a448eb56edbddfc90c94a406e6Chris Lattner if (!CurLoop->isLoopInvariant(I.getOperand(i))) 420a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return false; 421a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 422ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner // If we got this far, the instruction is loop invariant! 423ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner return true; 424ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner} 425ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner 426a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// sink - When an instruction is found to only be used outside of the loop, 427a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner/// this function moves it to the exit blocks and patches up SSA form as needed. 428a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner/// This method is guaranteed to remove the original instruction from its 429a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner/// position, and may either delete it or move it to outside of the loop. 430a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// 431a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattnervoid LICM::sink(Instruction &I) { 432b7427031372337e6d67f9573ec6c722ab5ea913eBill Wendling DOUT << "LICM sinking instruction: " << I; 433a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 4345fa802fe279f10f402e039bc931aa57c0e424bf5Chris Lattner std::vector<BasicBlock*> ExitBlocks; 4355fa802fe279f10f402e039bc931aa57c0e424bf5Chris Lattner CurLoop->getExitBlocks(ExitBlocks); 436df45bd3803ae0965a83cd1f30ee051b9f43e73ddChris Lattner 437df45bd3803ae0965a83cd1f30ee051b9f43e73ddChris Lattner if (isa<LoadInst>(I)) ++NumMovedLoads; 438118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner else if (isa<CallInst>(I)) ++NumMovedCalls; 439df45bd3803ae0965a83cd1f30ee051b9f43e73ddChris Lattner ++NumSunk; 440df45bd3803ae0965a83cd1f30ee051b9f43e73ddChris Lattner Changed = true; 441df45bd3803ae0965a83cd1f30ee051b9f43e73ddChris Lattner 442a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // The case where there is only a single exit node of this loop is common 443a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // enough that we handle it as a special (more efficient) case. It is more 444a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // efficient to handle because there are no PHI nodes that need to be placed. 445a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (ExitBlocks.size() == 1) { 446a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (!isExitBlockDominatedByBlockInLoop(ExitBlocks[0], I.getParent())) { 447a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Instruction is not used, just delete it. 4482741c971044d2165be572749b94398043caccfebChris Lattner CurAST->deleteValue(&I); 44992f7365740e9a116c59a8d33e636ebf6e4699301Chris Lattner if (!I.use_empty()) // If I has users in unreachable blocks, eliminate. 45092f7365740e9a116c59a8d33e636ebf6e4699301Chris Lattner I.replaceAllUsesWith(UndefValue::get(I.getType())); 4513c80a51cfd5e7187439ce4c051da77ee46e0ff9aChris Lattner I.eraseFromParent(); 452a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } else { 453a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Move the instruction to the start of the exit block, after any PHI 454a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // nodes in it. 4553c80a51cfd5e7187439ce4c051da77ee46e0ff9aChris Lattner I.removeFromParent(); 456fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 457a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner BasicBlock::iterator InsertPt = ExitBlocks[0]->begin(); 458a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner while (isa<PHINode>(InsertPt)) ++InsertPt; 459a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner ExitBlocks[0]->getInstList().insert(InsertPt, &I); 460a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 461a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } else if (ExitBlocks.size() == 0) { 462a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // The instruction is actually dead if there ARE NO exit blocks. 4632741c971044d2165be572749b94398043caccfebChris Lattner CurAST->deleteValue(&I); 46492f7365740e9a116c59a8d33e636ebf6e4699301Chris Lattner if (!I.use_empty()) // If I has users in unreachable blocks, eliminate. 46592f7365740e9a116c59a8d33e636ebf6e4699301Chris Lattner I.replaceAllUsesWith(UndefValue::get(I.getType())); 4663c80a51cfd5e7187439ce4c051da77ee46e0ff9aChris Lattner I.eraseFromParent(); 467a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } else { 468a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Otherwise, if we have multiple exits, use the PromoteMem2Reg function to 469a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // do all of the hard work of inserting PHI nodes as necessary. We convert 470a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // the value into a stack object to get it to do this. 471a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 472a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Firstly, we create a stack object to hold the value... 473eaa243039b6a83f8915f4f96ced58fabb520c851Chris Lattner AllocaInst *AI = 0; 474a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 475eaa243039b6a83f8915f4f96ced58fabb520c851Chris Lattner if (I.getType() != Type::VoidTy) 476eaa243039b6a83f8915f4f96ced58fabb520c851Chris Lattner AI = new AllocaInst(I.getType(), 0, I.getName(), 477eaa243039b6a83f8915f4f96ced58fabb520c851Chris Lattner I.getParent()->getParent()->front().begin()); 478fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 479a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Secondly, insert load instructions for each use of the instruction 480a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // outside of the loop. 481a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner while (!I.use_empty()) { 482a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner Instruction *U = cast<Instruction>(I.use_back()); 483a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 484a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // If the user is a PHI Node, we actually have to insert load instructions 485a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // in all predecessor blocks, not in the PHI block itself! 486a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (PHINode *UPN = dyn_cast<PHINode>(U)) { 487a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Only insert into each predecessor once, so that we don't have 488a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // different incoming values from the same block! 489a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner std::map<BasicBlock*, Value*> InsertedBlocks; 490a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner for (unsigned i = 0, e = UPN->getNumIncomingValues(); i != e; ++i) 491a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (UPN->getIncomingValue(i) == &I) { 492a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner BasicBlock *Pred = UPN->getIncomingBlock(i); 493a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner Value *&PredVal = InsertedBlocks[Pred]; 494a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (!PredVal) { 495a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Insert a new load instruction right before the terminator in 496a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // the predecessor block. 497a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner PredVal = new LoadInst(AI, "", Pred->getTerminator()); 498a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 499a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 500a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner UPN->setIncomingValue(i, PredVal); 501a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 502a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 503a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } else { 504a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner LoadInst *L = new LoadInst(AI, "", U); 505a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner U->replaceUsesOfWith(&I, L); 506a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 507a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 508a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 509a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Thirdly, insert a copy of the instruction in each exit block of the loop 510a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // that is dominated by the instruction, storing the result into the memory 511a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // location. Be careful not to insert the instruction into any particular 512a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // basic block more than once. 513a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner std::set<BasicBlock*> InsertedBlocks; 514a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner BasicBlock *InstOrigBB = I.getParent(); 515a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 516a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 517a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner BasicBlock *ExitBlock = ExitBlocks[i]; 518a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 519a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (isExitBlockDominatedByBlockInLoop(ExitBlock, InstOrigBB)) { 520a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // If we haven't already processed this exit block, do so now. 521e3cfe8d563fa06b274587aa38b1359ff707f33deChris Lattner if (InsertedBlocks.insert(ExitBlock).second) { 522a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Insert the code after the last PHI node... 523a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner BasicBlock::iterator InsertPt = ExitBlock->begin(); 524a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner while (isa<PHINode>(InsertPt)) ++InsertPt; 525fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 526a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // If this is the first exit block processed, just move the original 527a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // instruction, otherwise clone the original instruction and insert 528a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // the copy. 529a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner Instruction *New; 5307d3ced934f1bb2c6845676c7333ef879d5219e88Chris Lattner if (InsertedBlocks.size() == 1) { 5313c80a51cfd5e7187439ce4c051da77ee46e0ff9aChris Lattner I.removeFromParent(); 532a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner ExitBlock->getInstList().insert(InsertPt, &I); 533a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner New = &I; 534a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } else { 535a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner New = I.clone(); 53670ac2dcb841dc62f08e16f0b0e2cefbf01baa4c5Chris Lattner CurAST->copyValue(&I, New); 537eaa243039b6a83f8915f4f96ced58fabb520c851Chris Lattner if (!I.getName().empty()) 538eaa243039b6a83f8915f4f96ced58fabb520c851Chris Lattner New->setName(I.getName()+".le"); 539a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner ExitBlock->getInstList().insert(InsertPt, New); 540a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 541fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 542a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Now that we have inserted the instruction, store it into the alloca 543eaa243039b6a83f8915f4f96ced58fabb520c851Chris Lattner if (AI) new StoreInst(New, AI, InsertPt); 544a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 545a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 546a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 547a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner 548a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner // If the instruction doesn't dominate any exit blocks, it must be dead. 549a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner if (InsertedBlocks.empty()) { 5502741c971044d2165be572749b94398043caccfebChris Lattner CurAST->deleteValue(&I); 5513c80a51cfd5e7187439ce4c051da77ee46e0ff9aChris Lattner I.eraseFromParent(); 552a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner } 553fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 554a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Finally, promote the fine value to SSA form. 555eaa243039b6a83f8915f4f96ced58fabb520c851Chris Lattner if (AI) { 556eaa243039b6a83f8915f4f96ced58fabb520c851Chris Lattner std::vector<AllocaInst*> Allocas; 557eaa243039b6a83f8915f4f96ced58fabb520c851Chris Lattner Allocas.push_back(AI); 558fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner PromoteMemToReg(Allocas, *DT, *DF, AA->getTargetData(), CurAST); 559eaa243039b6a83f8915f4f96ced58fabb520c851Chris Lattner } 560a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 561a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner} 562952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 56394170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// hoist - When an instruction is found to only use loop invariant operands 56494170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// that is safe to hoist, this instruction is called to do the dirty work. 56594170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// 566a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattnervoid LICM::hoist(Instruction &I) { 567b7427031372337e6d67f9573ec6c722ab5ea913eBill Wendling DOUT << "LICM hoisting to " << Preheader->getName() << ": " << I; 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. 58892094b4d928119eceac1484331acffe950f4651cChris Lattner if (!Inst.isTrapping()) return true; 589fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 59092094b4d928119eceac1484331acffe950f4651cChris Lattner // Otherwise we have to check to make sure that the instruction dominates all 59192094b4d928119eceac1484331acffe950f4651cChris Lattner // of the exit blocks. If it doesn't, then there is a path out of the loop 59292094b4d928119eceac1484331acffe950f4651cChris Lattner // which does not execute this instruction, so we can't hoist it. 59392094b4d928119eceac1484331acffe950f4651cChris Lattner 59492094b4d928119eceac1484331acffe950f4651cChris Lattner // If the instruction is in the header block for the loop (which is very 59592094b4d928119eceac1484331acffe950f4651cChris Lattner // common), it is always guaranteed to dominate the exit blocks. Since this 59692094b4d928119eceac1484331acffe950f4651cChris Lattner // is a common case, and can save some work, check it now. 597a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (Inst.getParent() == CurLoop->getHeader()) 59892094b4d928119eceac1484331acffe950f4651cChris Lattner return true; 59992094b4d928119eceac1484331acffe950f4651cChris Lattner 6008a9193927a2661293a2afd5d1420faa2b0b8e6bfChris Lattner // It's always safe to load from a global or alloca. 6018a9193927a2661293a2afd5d1420faa2b0b8e6bfChris Lattner if (isa<LoadInst>(Inst)) 6028a9193927a2661293a2afd5d1420faa2b0b8e6bfChris Lattner if (isa<AllocationInst>(Inst.getOperand(0)) || 6038a9193927a2661293a2afd5d1420faa2b0b8e6bfChris Lattner isa<GlobalVariable>(Inst.getOperand(0))) 6048a9193927a2661293a2afd5d1420faa2b0b8e6bfChris Lattner return true; 6058a9193927a2661293a2afd5d1420faa2b0b8e6bfChris Lattner 60692094b4d928119eceac1484331acffe950f4651cChris Lattner // Get the exit blocks for the current loop. 6075fa802fe279f10f402e039bc931aa57c0e424bf5Chris Lattner std::vector<BasicBlock*> ExitBlocks; 6085fa802fe279f10f402e039bc931aa57c0e424bf5Chris Lattner CurLoop->getExitBlocks(ExitBlocks); 6099966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 61092094b4d928119eceac1484331acffe950f4651cChris Lattner // For each exit block, get the DT node and walk up the DT until the 61192094b4d928119eceac1484331acffe950f4651cChris Lattner // instruction's basic block is found or we exit the loop. 612a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 613a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (!isExitBlockDominatedByBlockInLoop(ExitBlocks[i], Inst.getParent())) 614a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return false; 615fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 6169966c03aad031f738718bed3bc00371e358beb5dTanya Lattner return true; 6179966c03aad031f738718bed3bc00371e358beb5dTanya Lattner} 6189966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 619eb53ae4f2dc39e75e725b21b52d77d29cf1c11c9Chris Lattner 6202e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// PromoteValuesInLoop - Try to promote memory values to scalars by sinking 6212e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// stores out of the loop and moving loads to before the loop. We do this by 6222e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// looping over the stores in the loop, looking for stores to Must pointers 6232e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// which are loop invariant. We promote these memory locations to use allocas 6242e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// instead. These allocas can easily be raised to register values by the 6252e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// PromoteMem2Reg functionality. 6262e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// 6272e6e741b737960ecd0b68610875050019aac0f07Chris Lattnervoid LICM::PromoteValuesInLoop() { 6282e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // PromotedValues - List of values that are promoted out of the loop. Each 629065a616adad624152618b1b0084ff074e5b03bbbChris Lattner // value has an alloca instruction for it, and a canonical version of the 6302e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // pointer. 6312e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::vector<std::pair<AllocaInst*, Value*> > PromotedValues; 6322e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::map<Value*, AllocaInst*> ValueToAllocaMap; // Map of ptr to alloca 6332e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 634fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner FindPromotableValuesInLoop(PromotedValues, ValueToAllocaMap); 635fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner if (ValueToAllocaMap.empty()) return; // If there are values to promote. 6362e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 6372e6e741b737960ecd0b68610875050019aac0f07Chris Lattner Changed = true; 6382e6e741b737960ecd0b68610875050019aac0f07Chris Lattner NumPromoted += PromotedValues.size(); 6392e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 640fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner std::vector<Value*> PointerValueNumbers; 641fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner 6422e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Emit a copy from the value into the alloca'd value in the loop preheader 6432e6e741b737960ecd0b68610875050019aac0f07Chris Lattner TerminatorInst *LoopPredInst = Preheader->getTerminator(); 6442e6e741b737960ecd0b68610875050019aac0f07Chris Lattner for (unsigned i = 0, e = PromotedValues.size(); i != e; ++i) { 645fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner Value *Ptr = PromotedValues[i].second; 646fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner 647fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // If we are promoting a pointer value, update alias information for the 648fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // inserted load. 649fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner Value *LoadValue = 0; 650fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner if (isa<PointerType>(cast<PointerType>(Ptr->getType())->getElementType())) { 651fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // Locate a load or store through the pointer, and assign the same value 652fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // to LI as we are loading or storing. Since we know that the value is 653fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // stored in this loop, this will always succeed. 654fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner for (Value::use_iterator UI = Ptr->use_begin(), E = Ptr->use_end(); 655fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner UI != E; ++UI) 656fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { 657fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner LoadValue = LI; 658fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner break; 659fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) { 660bdacd879578943efc98b75639cb8e7b4aab037f9Chris Lattner if (SI->getOperand(1) == Ptr) { 661fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner LoadValue = SI->getOperand(0); 662fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner break; 663fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner } 664fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner } 665fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner assert(LoadValue && "No store through the pointer found!"); 666fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner PointerValueNumbers.push_back(LoadValue); // Remember this for later. 667fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner } 668fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner 669fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // Load from the memory we are promoting. 670fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner LoadInst *LI = new LoadInst(Ptr, Ptr->getName()+".promoted", LoopPredInst); 671fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner 672fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner if (LoadValue) CurAST->copyValue(LoadValue, LI); 673fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner 674fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // Store into the temporary alloca. 6752e6e741b737960ecd0b68610875050019aac0f07Chris Lattner new StoreInst(LI, PromotedValues[i].first, LoopPredInst); 6762e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 677fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 6782e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Scan the basic blocks in the loop, replacing uses of our pointers with 6790ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner // uses of the allocas in question. 6802e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // 6812e6e741b737960ecd0b68610875050019aac0f07Chris Lattner const std::vector<BasicBlock*> &LoopBBs = CurLoop->getBlocks(); 6822e6e741b737960ecd0b68610875050019aac0f07Chris Lattner for (std::vector<BasicBlock*>::const_iterator I = LoopBBs.begin(), 6832e6e741b737960ecd0b68610875050019aac0f07Chris Lattner E = LoopBBs.end(); I != E; ++I) { 6842e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Rewrite all loads and stores in the block of the pointer... 6852e6e741b737960ecd0b68610875050019aac0f07Chris Lattner for (BasicBlock::iterator II = (*I)->begin(), E = (*I)->end(); 6862e6e741b737960ecd0b68610875050019aac0f07Chris Lattner II != E; ++II) { 687e408e25132b8de8c757db1e3ddcd70432dfeb24dChris Lattner if (LoadInst *L = dyn_cast<LoadInst>(II)) { 6882e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::map<Value*, AllocaInst*>::iterator 6892e6e741b737960ecd0b68610875050019aac0f07Chris Lattner I = ValueToAllocaMap.find(L->getOperand(0)); 6902e6e741b737960ecd0b68610875050019aac0f07Chris Lattner if (I != ValueToAllocaMap.end()) 6912e6e741b737960ecd0b68610875050019aac0f07Chris Lattner L->setOperand(0, I->second); // Rewrite load instruction... 692e408e25132b8de8c757db1e3ddcd70432dfeb24dChris Lattner } else if (StoreInst *S = dyn_cast<StoreInst>(II)) { 6932e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::map<Value*, AllocaInst*>::iterator 6942e6e741b737960ecd0b68610875050019aac0f07Chris Lattner I = ValueToAllocaMap.find(S->getOperand(1)); 6952e6e741b737960ecd0b68610875050019aac0f07Chris Lattner if (I != ValueToAllocaMap.end()) 6962e6e741b737960ecd0b68610875050019aac0f07Chris Lattner S->setOperand(1, I->second); // Rewrite store instruction... 6972e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 6982e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 6990ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner } 7002e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 7010ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner // Now that the body of the loop uses the allocas instead of the original 7020ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner // memory locations, insert code to copy the alloca value back into the 7030ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner // original memory location on all exits from the loop. Note that we only 7040ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner // want to insert one copy of the code in each exit block, though the loop may 7050ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner // exit to the same block more than once. 7060ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner // 7070ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner std::set<BasicBlock*> ProcessedBlocks; 7080ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner 7095fa802fe279f10f402e039bc931aa57c0e424bf5Chris Lattner std::vector<BasicBlock*> ExitBlocks; 7105fa802fe279f10f402e039bc931aa57c0e424bf5Chris Lattner CurLoop->getExitBlocks(ExitBlocks); 7110ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 712f594a03197ddd6437ca5eb3c2c61d339528e0da4Chris Lattner if (ProcessedBlocks.insert(ExitBlocks[i]).second) { 713fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // Copy all of the allocas into their memory locations. 7140ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner BasicBlock::iterator BI = ExitBlocks[i]->begin(); 7150ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner while (isa<PHINode>(*BI)) 716fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner ++BI; // Skip over all of the phi nodes in the block. 7170ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner Instruction *InsertPos = BI; 718fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner unsigned PVN = 0; 7190ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner for (unsigned i = 0, e = PromotedValues.size(); i != e; ++i) { 720fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // Load from the alloca. 7210ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner LoadInst *LI = new LoadInst(PromotedValues[i].first, "", InsertPos); 722fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner 723fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // If this is a pointer type, update alias info appropriately. 724fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner if (isa<PointerType>(LI->getType())) 725fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner CurAST->copyValue(PointerValueNumbers[PVN++], LI); 726fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner 727fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // Store into the memory we promoted. 7280ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner new StoreInst(LI, PromotedValues[i].second, InsertPos); 7292e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 7300ed2da9ac733c51ba004c067d3b552c1fa54613dChris Lattner } 7312e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 7322e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Now that we have done the deed, use the mem2reg functionality to promote 733fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // all of the new allocas we just created into real SSA registers. 7342e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // 7352e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::vector<AllocaInst*> PromotedAllocas; 7362e6e741b737960ecd0b68610875050019aac0f07Chris Lattner PromotedAllocas.reserve(PromotedValues.size()); 7372e6e741b737960ecd0b68610875050019aac0f07Chris Lattner for (unsigned i = 0, e = PromotedValues.size(); i != e; ++i) 7382e6e741b737960ecd0b68610875050019aac0f07Chris Lattner PromotedAllocas.push_back(PromotedValues[i].first); 739fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner PromoteMemToReg(PromotedAllocas, *DT, *DF, AA->getTargetData(), CurAST); 7402e6e741b737960ecd0b68610875050019aac0f07Chris Lattner} 7412e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 742fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner/// FindPromotableValuesInLoop - Check the current loop for stores to definite 7432e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// pointers, which are not loaded and stored through may aliases. If these are 7442e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// found, create an alloca for the value, add it to the PromotedValues list, 745fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner/// and keep track of the mapping from value to alloca. 7462e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// 747fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattnervoid LICM::FindPromotableValuesInLoop( 7482e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::vector<std::pair<AllocaInst*, Value*> > &PromotedValues, 7492e6e741b737960ecd0b68610875050019aac0f07Chris Lattner std::map<Value*, AllocaInst*> &ValueToAllocaMap) { 7502e6e741b737960ecd0b68610875050019aac0f07Chris Lattner Instruction *FnStart = CurLoop->getHeader()->getParent()->begin()->begin(); 7512e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 752fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // Loop over all of the alias sets in the tracker object. 7530252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); 7540252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner I != E; ++I) { 7550252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner AliasSet &AS = *I; 7560252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner // We can promote this alias set if it has a store, if it is a "Must" alias 757fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // set, if the pointer is loop invariant, and if we are not eliminating any 758118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner // volatile loads or stores. 7590252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner if (!AS.isForwardingAliasSet() && AS.isMod() && AS.isMustAlias() && 7603280f7bd557250a448eb56edbddfc90c94a406e6Chris Lattner !AS.isVolatile() && CurLoop->isLoopInvariant(AS.begin()->first)) { 7610252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner assert(AS.begin() != AS.end() && 7620252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner "Must alias set should have at least one pointer element in it!"); 7630252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner Value *V = AS.begin()->first; 7640252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner 7650252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner // Check that all of the pointers in the alias set have the same type. We 7660252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner // cannot (yet) promote a memory location that is loaded and stored in 7670252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner // different sizes. 7680252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner bool PointerOk = true; 7690252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I) 7700252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner if (V->getType() != I->first->getType()) { 7710252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner PointerOk = false; 7720252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner break; 7732e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 7740252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner 7750252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner if (PointerOk) { 7760252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner const Type *Ty = cast<PointerType>(V->getType())->getElementType(); 7770252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner AllocaInst *AI = new AllocaInst(Ty, 0, V->getName()+".tmp", FnStart); 7780252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner PromotedValues.push_back(std::make_pair(AI, V)); 779fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner 780fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner // Update the AST and alias analysis. 781fb3ee1930bfd0902f5fa3e6526775e3791e38d3cChris Lattner CurAST->copyValue(V, AI); 782fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 7830252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I) 7840252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner ValueToAllocaMap.insert(std::make_pair(I->first, AI)); 785fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 786b7427031372337e6d67f9573ec6c722ab5ea913eBill Wendling DOUT << "LICM: Promoting value: " << *V << "\n"; 7872e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 7882e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 7892e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 790f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner} 791