LICM.cpp revision 261304248f4f2cd0d9f0f85f91d400bcedeb0f45
1e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner//===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner// 1092094b4d928119eceac1484331acffe950f4651cChris Lattner// This pass performs loop invariant code motion, attempting to remove as much 1192094b4d928119eceac1484331acffe950f4651cChris Lattner// code from the body of a loop as possible. It does this by either hoisting 1292094b4d928119eceac1484331acffe950f4651cChris Lattner// code into the preheader block, or by sinking code to the exit blocks if it is 1392094b4d928119eceac1484331acffe950f4651cChris Lattner// safe. This pass also promotes must-aliased memory locations in the loop to 14e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner// live in registers, thus hoisting and sinking "invariant" loads and stores. 1592094b4d928119eceac1484331acffe950f4651cChris Lattner// 1692094b4d928119eceac1484331acffe950f4651cChris Lattner// This pass uses alias analysis for two purposes: 172e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// 182741c971044d2165be572749b94398043caccfebChris Lattner// 1. Moving loop invariant loads and calls out of loops. If we can determine 192741c971044d2165be572749b94398043caccfebChris Lattner// that a load or call inside of a loop never aliases anything stored to, 202741c971044d2165be572749b94398043caccfebChris Lattner// we can hoist it or sink it like any other instruction. 212e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// 2. Scalar Promotion of Memory - If there is a store instruction inside of 222e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// the loop, we try to move the store to happen AFTER the loop instead of 232e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// inside of the loop. This can only happen if a few conditions are true: 242e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// A. The pointer stored through is loop invariant 252e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// B. There are no stores or loads in the loop which _may_ alias the 262e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// pointer. There are no calls in the loop which mod/ref the pointer. 272e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// If these conditions are true, we can promote the loads and stores in the 282e6e741b737960ecd0b68610875050019aac0f07Chris Lattner// loop of the pointer to use a temporary alloca'd variable. We then use 29e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner// the SSAUpdater to construct the appropriate SSA form for the value. 30e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner// 31e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner//===----------------------------------------------------------------------===// 32e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 331f309c1a4e8068a64627c612a895d9b403dbcb26Chris Lattner#define DEBUG_TYPE "licm" 34e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include "llvm/Transforms/Scalar.h" 35d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 36f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner#include "llvm/Analysis/AliasAnalysis.h" 370252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner#include "llvm/Analysis/AliasSetTracker.h" 382ac6e2354ac9961b00fa351635ed04baf7fdd234Chris Lattner#include "llvm/Analysis/ConstantFolding.h" 39d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/Dominators.h" 402ac6e2354ac9961b00fa351635ed04baf7fdd234Chris Lattner#include "llvm/Analysis/LoopInfo.h" 412ac6e2354ac9961b00fa351635ed04baf7fdd234Chris Lattner#include "llvm/Analysis/LoopPass.h" 42f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman#include "llvm/Analysis/ValueTracking.h" 430b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 440b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 450b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DerivedTypes.h" 460b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 470b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 480b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/LLVMContext.h" 49261304248f4f2cd0d9f0f85f91d400bcedeb0f45Chris Lattner#include "llvm/IR/Metadata.h" 509133fe28954d498fc4de13064c7d65bd811de02cReid Spencer#include "llvm/Support/CFG.h" 51551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 52551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 53d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Support/raw_ostream.h" 54d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetLibraryInfo.h" 55d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/Local.h" 56d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/SSAUpdater.h" 57e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner#include <algorithm> 5892094b4d928119eceac1484331acffe950f4651cChris Lattnerusing namespace llvm; 59d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 600e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumSunk , "Number of instructions sunk out of loop"); 610e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumHoisted , "Number of instructions hoisted out of loop"); 620e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk"); 630e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk"); 640e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumPromoted , "Number of memory locations promoted to registers"); 650e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattner 66844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> 67844731a7f1909f55935e3514c9e713a62d67662eDan GohmanDisablePromotion("disable-licm-promotion", cl::Hidden, 68844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::desc("Disable memory promotion in LICM pass")); 692e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 70844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 713e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner struct LICM : public LoopPass { 72ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 73081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson LICM() : LoopPass(ID) { 74081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeLICMPass(*PassRegistry::getPassRegistry()); 75081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 76794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 7754959d6cf68a9b575c98c074babe9867682a7271Devang Patel virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 78e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 7994170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// This transformation requires natural loop information & requires that 8094170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// loop preheaders be inserted into the CFG... 8194170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// 82e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 83cb2610ea037a17115ef3a01a6bdaab4e3cfdca27Chris Lattner AU.setPreservesCFG(); 843a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson AU.addRequired<DominatorTree>(); 851e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman AU.addRequired<LoopInfo>(); 861e381fcd553a3955a10338fd305efc023d7d22e1Dan Gohman AU.addRequiredID(LoopSimplifyID); 87f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner AU.addRequired<AliasAnalysis>(); 88e418ac832c1a2813736c44f6ec5c646b4c89c339Chris Lattner AU.addPreserved<AliasAnalysis>(); 89a9b61e7f7b1ab3a7344bbdc31c3e254c189fafccDan Gohman AU.addPreserved("scalar-evolution"); 905c89b5240c90eb8171f999e5f06f815502d0321cDan Gohman AU.addPreservedID(LoopSimplifyID); 91aab8e28d5e470711d80276bbf717408c3ab966fdChad Rosier AU.addRequired<TargetLibraryInfo>(); 92e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } 93e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 94ee721156701ec3afb198d4cfede00095b228eeacMatt Beaumont-Gay using llvm::Pass::doFinalization; 95ee721156701ec3afb198d4cfede00095b228eeacMatt Beaumont-Gay 96747603e39ea3f29add9ba6c07bbefcc5c2432612Dan Gohman bool doFinalization() { 974282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner assert(LoopToAliasSetMap.empty() && "Didn't free loop alias sets"); 9854959d6cf68a9b575c98c074babe9867682a7271Devang Patel return false; 9954959d6cf68a9b575c98c074babe9867682a7271Devang Patel } 10054959d6cf68a9b575c98c074babe9867682a7271Devang Patel 101e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner private: 1022e6e741b737960ecd0b68610875050019aac0f07Chris Lattner AliasAnalysis *AA; // Current AliasAnalysis information 10392094b4d928119eceac1484331acffe950f4651cChris Lattner LoopInfo *LI; // Current LoopInfo 10444e2bd31f13da68bca451e4210560db3644b8208Chris Lattner DominatorTree *DT; // Dominator Tree for the current Loop. 10592094b4d928119eceac1484331acffe950f4651cChris Lattner 1063574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow DataLayout *TD; // DataLayout for constant folding. 107aab8e28d5e470711d80276bbf717408c3ab966fdChad Rosier TargetLibraryInfo *TLI; // TargetLibraryInfo for constant folding. 108aab8e28d5e470711d80276bbf717408c3ab966fdChad Rosier 1094282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner // State that is updated as we process loops. 1102e6e741b737960ecd0b68610875050019aac0f07Chris Lattner bool Changed; // Set to true when we change anything. 1112e6e741b737960ecd0b68610875050019aac0f07Chris Lattner BasicBlock *Preheader; // The preheader block of the current loop... 1122e6e741b737960ecd0b68610875050019aac0f07Chris Lattner Loop *CurLoop; // The current loop we are working on... 1130252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner AliasSetTracker *CurAST; // AliasSet information for the current loop... 1147765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem bool MayThrow; // The current loop contains an instruction which 1157765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem // may throw, thus preventing code motion of 1167765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem // instructions with side effects. 1174282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner DenseMap<Loop*, AliasSetTracker*> LoopToAliasSetMap; 118e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 11991d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info. 12091d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel void cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L); 12191d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel 12291d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel /// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias 12391d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel /// set. 12491d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel void deleteAnalysisValue(Value *V, Loop *L); 12591d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel 126e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner /// SinkRegion - Walk the specified region of the CFG (defined by all blocks 127e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner /// dominated by the specified block, and that are in the current loop) in 1283a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson /// reverse depth first order w.r.t the DominatorTree. This allows us to 129e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner /// visit uses before definitions, allowing us to sink a loop body in one 130e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner /// pass without iteration. 131e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner /// 13226042420d642e810f5cdfb2da6156b74aaf80945Devang Patel void SinkRegion(DomTreeNode *N); 133e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 134952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// HoistRegion - Walk the specified region of the CFG (defined by all 135952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// blocks dominated by the specified block, and that are in the current 1363a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson /// loop) in depth first order w.r.t the DominatorTree. This allows us to 137cf00c4ab3ba308d45d98c5ccab87362cf802facbMisha Brukman /// visit definitions before uses, allowing us to hoist a loop body in one 138952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// pass without iteration. 139952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner /// 14026042420d642e810f5cdfb2da6156b74aaf80945Devang Patel void HoistRegion(DomTreeNode *N); 141952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 142b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner /// inSubLoop - Little predicate that returns true if the specified basic 143b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner /// block is in a subloop of the current one, not the current one itself. 14494170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// 145b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner bool inSubLoop(BasicBlock *BB) { 146b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop"); 14781a866d615d6e4ee8dcbd49268d2cfb174f5155bChris Lattner return LI->getLoopFor(BB) != CurLoop; 148e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner } 149e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 150a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// sink - When an instruction is found to only be used outside of the loop, 151a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// this function moves it to the exit blocks and patches up SSA form as 152a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// needed. 153a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// 154a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner void sink(Instruction &I); 155a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 15694170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// hoist - When an instruction is found to only use loop invariant operands 15794170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// that is safe to hoist, this instruction is called to do the dirty work. 15894170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// 1597e70829632f82de15db187845666aaca6e04b792Chris Lattner void hoist(Instruction &I); 160e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 161a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// isSafeToExecuteUnconditionally - Only sink or hoist an instruction if it 162a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// is not a trapping instruction or if it is a trapping instruction and is 163a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner /// guaranteed to execute. 1649966c03aad031f738718bed3bc00371e358beb5dTanya Lattner /// 165a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner bool isSafeToExecuteUnconditionally(Instruction &I); 1669966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 16773bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman /// isGuaranteedToExecute - Check that the instruction is guaranteed to 16873bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman /// execute. 16973bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman /// 17073bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman bool isGuaranteedToExecute(Instruction &I); 17173bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman 17294170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// pointerInvalidatedByLoop - Return true if the body of this loop may 17394170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner /// store into the memory location pointed to by V. 174fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman /// 1753da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman bool pointerInvalidatedByLoop(Value *V, uint64_t Size, 176a8702eaf78e70e1eef8a63882ce97ae6d60edf5bDan Gohman const MDNode *TBAAInfo) { 1770252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner // Check to see if any of the basic blocks in CurLoop invalidate *V. 178a8702eaf78e70e1eef8a63882ce97ae6d60edf5bDan Gohman return CurAST->getAliasSetForPointer(V, Size, TBAAInfo).isMod(); 1792e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 180f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner 181a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner bool canSinkOrHoistInst(Instruction &I); 182a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner bool isNotUsedInLoop(Instruction &I); 183e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 1849d1747c3cd709cd5bbc1a07074550862d188527eDan Gohman void PromoteAliasSet(AliasSet &AS, 1859d1747c3cd709cd5bbc1a07074550862d188527eDan Gohman SmallVectorImpl<BasicBlock*> &ExitBlocks, 1869d1747c3cd709cd5bbc1a07074550862d188527eDan Gohman SmallVectorImpl<Instruction*> &InsertPts); 187e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner }; 188e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner} 189e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 190844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar LICM::ID = 0; 1912ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(LICM, "licm", "Loop Invariant Code Motion", false, false) 1922ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominatorTree) 1932ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LoopInfo) 1942ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LoopSimplify) 195aab8e28d5e470711d80276bbf717408c3ab966fdChad RosierINITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 1962ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 1972ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(LICM, "licm", "Loop Invariant Code Motion", false, false) 198844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 199394f0441e06dafca29f0752cf400990a5b8fe4b1Daniel DunbarPass *llvm::createLICMPass() { return new LICM(); } 200e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 2018d246f09cb46fe38aa71d2a4edcd84f30c4bf80eDevang Patel/// Hoist expressions out of the specified loop. Note, alias info for inner 202a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser/// loop is not preserved so it is not a good idea to run LICM multiple 2038d246f09cb46fe38aa71d2a4edcd84f30c4bf80eDevang Patel/// times on one loop. 20494170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// 20554959d6cf68a9b575c98c074babe9867682a7271Devang Patelbool LICM::runOnLoop(Loop *L, LPPassManager &LPM) { 2062e6e741b737960ecd0b68610875050019aac0f07Chris Lattner Changed = false; 207e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 2082e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Get our Loop and Alias Analysis information... 2092e6e741b737960ecd0b68610875050019aac0f07Chris Lattner LI = &getAnalysis<LoopInfo>(); 210f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner AA = &getAnalysis<AliasAnalysis>(); 2113a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson DT = &getAnalysis<DominatorTree>(); 212f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner 2133574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow TD = getAnalysisIfAvailable<DataLayout>(); 214aab8e28d5e470711d80276bbf717408c3ab966fdChad Rosier TLI = &getAnalysis<TargetLibraryInfo>(); 215aab8e28d5e470711d80276bbf717408c3ab966fdChad Rosier 21654959d6cf68a9b575c98c074babe9867682a7271Devang Patel CurAST = new AliasSetTracker(*AA); 2174282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner // Collect Alias info from subloops. 21854959d6cf68a9b575c98c074babe9867682a7271Devang Patel for (Loop::iterator LoopItr = L->begin(), LoopItrE = L->end(); 21954959d6cf68a9b575c98c074babe9867682a7271Devang Patel LoopItr != LoopItrE; ++LoopItr) { 22054959d6cf68a9b575c98c074babe9867682a7271Devang Patel Loop *InnerL = *LoopItr; 2214282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner AliasSetTracker *InnerAST = LoopToAliasSetMap[InnerL]; 2224282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner assert(InnerAST && "Where is my AST?"); 22394170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner 22454959d6cf68a9b575c98c074babe9867682a7271Devang Patel // What if InnerLoop was modified by other passes ? 22554959d6cf68a9b575c98c074babe9867682a7271Devang Patel CurAST->add(*InnerAST); 226a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 2274282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner // Once we've incorporated the inner loop's AST into ours, we don't need the 2284282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner // subloop's anymore. 2294282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner delete InnerAST; 2304282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner LoopToAliasSetMap.erase(InnerL); 2312e6e741b737960ecd0b68610875050019aac0f07Chris Lattner } 232a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 233e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner CurLoop = L; 234e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 23599a57216a935a512c418032f590a4660bad9d846Chris Lattner // Get the preheader block to move instructions into... 23699a57216a935a512c418032f590a4660bad9d846Chris Lattner Preheader = L->getLoopPreheader(); 23799a57216a935a512c418032f590a4660bad9d846Chris Lattner 2382e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Loop over the body of this loop, looking for calls, invokes, and stores. 2390252e49f6d6973b6f347c8feafc49e28af27163aChris Lattner // Because subloops have already been incorporated into AST, we skip blocks in 2402e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // subloops. 2412e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // 2429b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 2439b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman I != E; ++I) { 2449b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman BasicBlock *BB = *I; 2454282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner if (LI->getLoopFor(BB) == L) // Ignore blocks in subloops. 2469b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman CurAST->add(*BB); // Incorporate the specified basic block 2479b78763fce4cb418e7a2e672efb84bac25559b79Dan Gohman } 2482e6e741b737960ecd0b68610875050019aac0f07Chris Lattner 2497765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem MayThrow = false; 2507765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem // TODO: We've already searched for instructions which may throw in subloops. 2517765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem // We may want to reuse this information. 2527765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem for (Loop::block_iterator BB = L->block_begin(), BBE = L->block_end(); 2537765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem (BB != BBE) && !MayThrow ; ++BB) 2547765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); 2557765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem (I != E) && !MayThrow; ++I) 2567765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem MayThrow |= I->mayThrow(); 2577765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem 258e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // We want to visit all of the instructions in this loop... that are not parts 259e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // of our subloops (they have already had their invariants hoisted out of 260e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // their loop, into this loop, so there is no need to process the BODIES of 261e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // the subloops). 262e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // 263952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner // Traverse the body of the loop in depth first order on the dominator tree so 264952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner // that we are guaranteed to see definitions before we see uses. This allows 265af5cbc82bb6410129425c98bbfc1ffc4c3d0f411Nick Lewycky // us to sink instructions in one pass, without iteration. After sinking 266e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // instructions, we perform another pass to hoist them out of the loop. 267952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner // 26803e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman if (L->hasDedicatedExits()) 26903e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman SinkRegion(DT->getNode(L->getHeader())); 27003e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman if (Preheader) 27103e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman HoistRegion(DT->getNode(L->getHeader())); 272e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 2732e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // Now that all loop invariants have been removed from the loop, promote any 274e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // memory references to scalars that we can. 275e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner if (!DisablePromotion && Preheader && L->hasDedicatedExits()) { 2769d1747c3cd709cd5bbc1a07074550862d188527eDan Gohman SmallVector<BasicBlock *, 8> ExitBlocks; 2779d1747c3cd709cd5bbc1a07074550862d188527eDan Gohman SmallVector<Instruction *, 8> InsertPts; 2789d1747c3cd709cd5bbc1a07074550862d188527eDan Gohman 279e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // Loop over all of the alias sets in the tracker object. 280e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); 281e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner I != E; ++I) 2829d1747c3cd709cd5bbc1a07074550862d188527eDan Gohman PromoteAliasSet(*I, ExitBlocks, InsertPts); 283e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner } 284a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 285e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner // Clear out loops state information for the next iteration 286e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner CurLoop = 0; 28799a57216a935a512c418032f590a4660bad9d846Chris Lattner Preheader = 0; 28854959d6cf68a9b575c98c074babe9867682a7271Devang Patel 2894282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner // If this loop is nested inside of another one, save the alias information 2904282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner // for when we process the outer loop. 2914282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner if (L->getParentLoop()) 2924282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner LoopToAliasSetMap[L] = CurAST; 2934282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner else 2944282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner delete CurAST; 29554959d6cf68a9b575c98c074babe9867682a7271Devang Patel return Changed; 296e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner} 297e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 298e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner/// SinkRegion - Walk the specified region of the CFG (defined by all blocks 299e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner/// dominated by the specified block, and that are in the current loop) in 3003a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson/// reverse depth first order w.r.t the DominatorTree. This allows us to visit 301e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner/// uses before definitions, allowing us to sink a loop body in one pass without 302e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner/// iteration. 303e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner/// 30426042420d642e810f5cdfb2da6156b74aaf80945Devang Patelvoid LICM::SinkRegion(DomTreeNode *N) { 3053a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson assert(N != 0 && "Null dominator tree node?"); 3063a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson BasicBlock *BB = N->getBlock(); 307e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 308e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // If this subregion is not in the top level loop at all, exit. 309e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner if (!CurLoop->contains(BB)) return; 310e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 3110de5cad74d8d2987b92b8d76af3f1eab988b3c7bChris Lattner // We are processing blocks in reverse dfo, so process children first. 31226042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const std::vector<DomTreeNode*> &Children = N->getChildren(); 313e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner for (unsigned i = 0, e = Children.size(); i != e; ++i) 314e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner SinkRegion(Children[i]); 315e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 316e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // Only need to process the contents of this block if it is not part of a 317e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // subloop (which would already have been processed). 318e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner if (inSubLoop(BB)) return; 319e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 320a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner for (BasicBlock::iterator II = BB->end(); II != BB->begin(); ) { 321a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner Instruction &I = *--II; 322a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 3230de5cad74d8d2987b92b8d76af3f1eab988b3c7bChris Lattner // If the instruction is dead, we would try to sink it because it isn't used 3240de5cad74d8d2987b92b8d76af3f1eab988b3c7bChris Lattner // in the loop, instead, just delete it. 3258e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (isInstructionTriviallyDead(&I, TLI)) { 326cb7f65342291caa3636cb50c0ee04b383cd79f8dChris Lattner DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n'); 3270de5cad74d8d2987b92b8d76af3f1eab988b3c7bChris Lattner ++II; 3280de5cad74d8d2987b92b8d76af3f1eab988b3c7bChris Lattner CurAST->deleteValue(&I); 3290de5cad74d8d2987b92b8d76af3f1eab988b3c7bChris Lattner I.eraseFromParent(); 3300de5cad74d8d2987b92b8d76af3f1eab988b3c7bChris Lattner Changed = true; 3310de5cad74d8d2987b92b8d76af3f1eab988b3c7bChris Lattner continue; 3320de5cad74d8d2987b92b8d76af3f1eab988b3c7bChris Lattner } 333fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 334e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // Check to see if we can sink this instruction to the exit blocks 335e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // of the loop. We can do this if the all users of the instruction are 336e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // outside of the loop. In this case, it doesn't even matter if the 337e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // operands of the instruction are loop invariant. 338e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // 33970ac2dcb841dc62f08e16f0b0e2cefbf01baa4c5Chris Lattner if (isNotUsedInLoop(I) && canSinkOrHoistInst(I)) { 340a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner ++II; 341e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner sink(I); 342a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner } 343e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner } 344e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner} 345e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner 346952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner/// HoistRegion - Walk the specified region of the CFG (defined by all blocks 347952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner/// dominated by the specified block, and that are in the current loop) in depth 3483a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson/// first order w.r.t the DominatorTree. This allows us to visit definitions 349952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner/// before uses, allowing us to hoist a loop body in one pass without iteration. 350952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner/// 35126042420d642e810f5cdfb2da6156b74aaf80945Devang Patelvoid LICM::HoistRegion(DomTreeNode *N) { 3523a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson assert(N != 0 && "Null dominator tree node?"); 3533a2b58f3adc5e9f9bffac7ce193f0570aa5a721fOwen Anderson BasicBlock *BB = N->getBlock(); 354952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 355b461373fbcdc5909cc7331fa64791cd039de4bc8Chris Lattner // If this subregion is not in the top level loop at all, exit. 356ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner if (!CurLoop->contains(BB)) return; 357952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 358a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Only need to process the contents of this block if it is not part of a 359a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // subloop (which would already have been processed). 360ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner if (!inSubLoop(BB)) 361a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) { 362a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner Instruction &I = *II++; 363fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 3642ac6e2354ac9961b00fa351635ed04baf7fdd234Chris Lattner // Try constant folding this instruction. If all the operands are 3652ac6e2354ac9961b00fa351635ed04baf7fdd234Chris Lattner // constants, it is technically hoistable, but it would be better to just 3662ac6e2354ac9961b00fa351635ed04baf7fdd234Chris Lattner // fold it. 367aab8e28d5e470711d80276bbf717408c3ab966fdChad Rosier if (Constant *C = ConstantFoldInstruction(&I, TD, TLI)) { 3682ac6e2354ac9961b00fa351635ed04baf7fdd234Chris Lattner DEBUG(dbgs() << "LICM folding inst: " << I << " --> " << *C << '\n'); 3692ac6e2354ac9961b00fa351635ed04baf7fdd234Chris Lattner CurAST->copyValue(&I, C); 3702ac6e2354ac9961b00fa351635ed04baf7fdd234Chris Lattner CurAST->deleteValue(&I); 3712ac6e2354ac9961b00fa351635ed04baf7fdd234Chris Lattner I.replaceAllUsesWith(C); 3722ac6e2354ac9961b00fa351635ed04baf7fdd234Chris Lattner I.eraseFromParent(); 3732ac6e2354ac9961b00fa351635ed04baf7fdd234Chris Lattner continue; 3742ac6e2354ac9961b00fa351635ed04baf7fdd234Chris Lattner } 375a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 376e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // Try hoisting the instruction out to the preheader. We can only do this 377e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // if all of the operands of the instruction are loop invariant and if it 378e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // is safe to hoist the instruction. 379e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner // 380adc799112dc180b3cd099038c05101b85d217716Chris Lattner if (CurLoop->hasLoopInvariantOperands(&I) && canSinkOrHoistInst(I) && 381e4365b2e8c79f9b2d564f31fdcc0568da8e5d60fChris Lattner isSafeToExecuteUnconditionally(I)) 3823c80a51cfd5e7187439ce4c051da77ee46e0ff9aChris Lattner hoist(I); 3832ac6e2354ac9961b00fa351635ed04baf7fdd234Chris Lattner } 384952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 38526042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const std::vector<DomTreeNode*> &Children = N->getChildren(); 386952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner for (unsigned i = 0, e = Children.size(); i != e; ++i) 38756b7ee20dad7160a117ea0d102fc5432074ce2d0Chris Lattner HoistRegion(Children[i]); 388952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner} 389952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 390a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// canSinkOrHoistInst - Return true if the hoister and sinker can handle this 391a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// instruction. 392a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// 393a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattnerbool LICM::canSinkOrHoistInst(Instruction &I) { 394ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner // Loads have extra constraints we have to verify before we can hoist them. 395ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(&I)) { 39697671565ffd341d1d3291243f9f51edc6b64b065Eli Friedman if (!LI->isUnordered()) 39797671565ffd341d1d3291243f9f51edc6b64b065Eli Friedman return false; // Don't hoist volatile/atomic loads! 398ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner 399967948b4e25cae3de68f38fddaa75d838e676decChris Lattner // Loads from constant memory are always safe to move, even if they end up 400967948b4e25cae3de68f38fddaa75d838e676decChris Lattner // in the same alias set as something that ends up being modified. 401dab249b3b762cff0ff16069b3233e4c885e75347Dan Gohman if (AA->pointsToConstantMemory(LI->getOperand(0))) 402967948b4e25cae3de68f38fddaa75d838e676decChris Lattner return true; 40385dadecbd664f60f0c7e4fbb44f083d43d01cfb7Benjamin Kramer if (LI->getMetadata("invariant.load")) 4042d76a7846200fcbe518e6f73291a6cbda8864ea0Pete Cooper return true; 405a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 406ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner // Don't hoist loads which have may-aliased stores in loop. 4073da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman uint64_t Size = 0; 408f3e1d6977ee5fb6b66df314d65e28e2c35d6e244Chris Lattner if (LI->getType()->isSized()) 409fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman Size = AA->getTypeStoreSize(LI->getType()); 410a8702eaf78e70e1eef8a63882ce97ae6d60edf5bDan Gohman return !pointerInvalidatedByLoop(LI->getOperand(0), Size, 411a8702eaf78e70e1eef8a63882ce97ae6d60edf5bDan Gohman LI->getMetadata(LLVMContext::MD_tbaa)); 412118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner } else if (CallInst *CI = dyn_cast<CallInst>(&I)) { 41330a121b4e83c2bed062cc2d89f4b8fc354ac370eEli Friedman // Don't sink or hoist dbg info; it's legal, but not useful. 41430a121b4e83c2bed062cc2d89f4b8fc354ac370eEli Friedman if (isa<DbgInfoIntrinsic>(I)) 41530a121b4e83c2bed062cc2d89f4b8fc354ac370eEli Friedman return false; 41630a121b4e83c2bed062cc2d89f4b8fc354ac370eEli Friedman 41730a121b4e83c2bed062cc2d89f4b8fc354ac370eEli Friedman // Handle simple cases by querying alias analysis. 418dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands AliasAnalysis::ModRefBehavior Behavior = AA->getModRefBehavior(CI); 419dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands if (Behavior == AliasAnalysis::DoesNotAccessMemory) 420dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands return true; 421cd93f3bbb9cf209aff3ffdff9d7c7d05d935b292Dan Gohman if (AliasAnalysis::onlyReadsMemory(Behavior)) { 422dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands // If this call only reads from memory and there are no writes to memory 423dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands // in the loop, we can hoist or sink the call as appropriate. 424dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands bool FoundMod = false; 425dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); 426dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands I != E; ++I) { 427dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands AliasSet &AS = *I; 428dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands if (!AS.isForwardingAliasSet() && AS.isMod()) { 429dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands FoundMod = true; 430dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands break; 431118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner } 432118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner } 433dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands if (!FoundMod) return true; 434118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner } 435118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner 4367765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem // FIXME: This should use mod/ref information to see if we can hoist or 4377765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem // sink the call. 438fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 439118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner return false; 440ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner } 441ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner 4427765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem // Only these instructions are hoistable/sinkable. 4437765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem bool HoistableKind = (isa<BinaryOperator>(I) || isa<CastInst>(I) || 4447765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem isa<SelectInst>(I) || isa<GetElementPtrInst>(I) || 4457765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem isa<CmpInst>(I) || isa<InsertElementInst>(I) || 4467765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem isa<ExtractElementInst>(I) || 4477765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem isa<ShuffleVectorInst>(I)); 4487765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem if (!HoistableKind) 4497765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem return false; 4507765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem 4517765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem return isSafeToExecuteUnconditionally(I); 452a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner} 453a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 454a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// isNotUsedInLoop - Return true if the only users of this instruction are 455a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// outside of the loop. If this is true, we can sink the instruction to the 456a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// exit blocks of the loop. 457a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// 458a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattnerbool LICM::isNotUsedInLoop(Instruction &I) { 459ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); UI != E; ++UI) { 460ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner Instruction *User = cast<Instruction>(*UI); 461ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner if (PHINode *PN = dyn_cast<PHINode>(User)) { 462ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner // PHI node uses occur in predecessor blocks! 463ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 464ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner if (PN->getIncomingValue(i) == &I) 465ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner if (CurLoop->contains(PN->getIncomingBlock(i))) 466ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner return false; 46792329c7fbe572892c17aa2d2542a10e3ea16132fDan Gohman } else if (CurLoop->contains(User)) { 468a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return false; 469ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner } 470ea9403f2aa078e840a49792d906390395f0cd2f6Chris Lattner } 471a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return true; 472a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner} 473a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 474a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 475a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// sink - When an instruction is found to only be used outside of the loop, 476a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner/// this function moves it to the exit blocks and patches up SSA form as needed. 477a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner/// This method is guaranteed to remove the original instruction from its 478a3df8a964aa9d0d171fd4f6e491c7d1cf9dee500Chris Lattner/// position, and may either delete it or move it to outside of the loop. 479a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// 480a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattnervoid LICM::sink(Instruction &I) { 48139a383124b70dda1fea18288235114029ede76cfNick Lewycky DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n"); 482a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner 483b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel SmallVector<BasicBlock*, 8> ExitBlocks; 484d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner CurLoop->getUniqueExitBlocks(ExitBlocks); 485df45bd3803ae0965a83cd1f30ee051b9f43e73ddChris Lattner 486df45bd3803ae0965a83cd1f30ee051b9f43e73ddChris Lattner if (isa<LoadInst>(I)) ++NumMovedLoads; 487118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner else if (isa<CallInst>(I)) ++NumMovedCalls; 488df45bd3803ae0965a83cd1f30ee051b9f43e73ddChris Lattner ++NumSunk; 489df45bd3803ae0965a83cd1f30ee051b9f43e73ddChris Lattner Changed = true; 490df45bd3803ae0965a83cd1f30ee051b9f43e73ddChris Lattner 491a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // The case where there is only a single exit node of this loop is common 492a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // enough that we handle it as a special (more efficient) case. It is more 493a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // efficient to handle because there are no PHI nodes that need to be placed. 494a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (ExitBlocks.size() == 1) { 49530a121b4e83c2bed062cc2d89f4b8fc354ac370eEli Friedman if (!DT->dominates(I.getParent(), ExitBlocks[0])) { 496a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Instruction is not used, just delete it. 4972741c971044d2165be572749b94398043caccfebChris Lattner CurAST->deleteValue(&I); 4981bf5ebc7be0d5b05e4175c7adb767b38896adef1Devang Patel // If I has users in unreachable blocks, eliminate. 499228ebd0f4cf9207d32d61ef4b11b81736895dc09Devang Patel // If I is not void type then replaceAllUsesWith undef. 500228ebd0f4cf9207d32d61ef4b11b81736895dc09Devang Patel // This allows ValueHandlers and custom metadata to adjust itself. 501a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner if (!I.use_empty()) 502228ebd0f4cf9207d32d61ef4b11b81736895dc09Devang Patel I.replaceAllUsesWith(UndefValue::get(I.getType())); 5033c80a51cfd5e7187439ce4c051da77ee46e0ff9aChris Lattner I.eraseFromParent(); 504a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } else { 505a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // Move the instruction to the start of the exit block, after any PHI 506a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // nodes in it. 50726665de4f7ab03d651f626bddb925724a2816a18Bill Wendling I.moveBefore(ExitBlocks[0]->getFirstInsertionPt()); 5084282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner 5094282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner // This instruction is no longer in the AST for the current loop, because 5104282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner // we just sunk it out of the loop. If we just sunk it into an outer 5114282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner // loop, we will rediscover the operation when we process it. 5124282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner CurAST->deleteValue(&I); 513a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 514d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner return; 515d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner } 516a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 517d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner if (ExitBlocks.empty()) { 518a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner // The instruction is actually dead if there ARE NO exit blocks. 5192741c971044d2165be572749b94398043caccfebChris Lattner CurAST->deleteValue(&I); 5201bf5ebc7be0d5b05e4175c7adb767b38896adef1Devang Patel // If I has users in unreachable blocks, eliminate. 521228ebd0f4cf9207d32d61ef4b11b81736895dc09Devang Patel // If I is not void type then replaceAllUsesWith undef. 522228ebd0f4cf9207d32d61ef4b11b81736895dc09Devang Patel // This allows ValueHandlers and custom metadata to adjust itself. 523a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner if (!I.use_empty()) 524228ebd0f4cf9207d32d61ef4b11b81736895dc09Devang Patel I.replaceAllUsesWith(UndefValue::get(I.getType())); 5253c80a51cfd5e7187439ce4c051da77ee46e0ff9aChris Lattner I.eraseFromParent(); 526d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner return; 527d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner } 528a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 529a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner // Otherwise, if we have multiple exits, use the SSAUpdater to do all of the 530a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner // hard work of inserting PHI nodes as necessary. 531a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner SmallVector<PHINode*, 8> NewPHIs; 532a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner SSAUpdater SSA(&NewPHIs); 533a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 534a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner if (!I.use_empty()) 535fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sands SSA.Initialize(I.getType(), I.getName()); 536a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 537a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner // Insert a copy of the instruction in each exit block of the loop that is 538a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner // dominated by the instruction. Each exit block is known to only be in the 539a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner // ExitBlocks list once. 540a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner BasicBlock *InstOrigBB = I.getParent(); 541d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner unsigned NumInserted = 0; 542a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 543d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 544d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner BasicBlock *ExitBlock = ExitBlocks[i]; 545a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 54683fc584ea811aca780d965258c49db72a3ee8b1dChris Lattner if (!DT->dominates(InstOrigBB, ExitBlock)) 547d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner continue; 548a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 549a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner // Insert the code after the last PHI node. 55026665de4f7ab03d651f626bddb925724a2816a18Bill Wendling BasicBlock::iterator InsertPt = ExitBlock->getFirstInsertionPt(); 551a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 552d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner // If this is the first exit block processed, just move the original 553d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner // instruction, otherwise clone the original instruction and insert 554d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner // the copy. 555d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner Instruction *New; 556a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner if (NumInserted++ == 0) { 557a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner I.moveBefore(InsertPt); 558d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner New = &I; 559d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner } else { 560d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner New = I.clone(); 561d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner if (!I.getName().empty()) 562d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner New->setName(I.getName()+".le"); 563d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner ExitBlock->getInstList().insert(InsertPt, New); 564a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 565a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 566a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner // Now that we have inserted the instruction, inform SSAUpdater. 567a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner if (!I.use_empty()) 568a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner SSA.AddAvailableValue(ExitBlock, New); 569d7bc19dfee3f2ce8e9c8b9193bdfb93a67008a39Chris Lattner } 570a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 571c955d212a8c060d7082fe975fd65fcbc9263853aEli Friedman // If the instruction doesn't dominate any exit blocks, it must be dead. 572c955d212a8c060d7082fe975fd65fcbc9263853aEli Friedman if (NumInserted == 0) { 573c955d212a8c060d7082fe975fd65fcbc9263853aEli Friedman CurAST->deleteValue(&I); 574c955d212a8c060d7082fe975fd65fcbc9263853aEli Friedman if (!I.use_empty()) 575c955d212a8c060d7082fe975fd65fcbc9263853aEli Friedman I.replaceAllUsesWith(UndefValue::get(I.getType())); 576c955d212a8c060d7082fe975fd65fcbc9263853aEli Friedman I.eraseFromParent(); 577c955d212a8c060d7082fe975fd65fcbc9263853aEli Friedman return; 578c955d212a8c060d7082fe975fd65fcbc9263853aEli Friedman } 579a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 580a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner // Next, rewrite uses of the instruction, inserting PHI nodes as needed. 581a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner for (Value::use_iterator UI = I.use_begin(), UE = I.use_end(); UI != UE; ) { 582a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner // Grab the use before incrementing the iterator. 583a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner Use &U = UI.getUse(); 584a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner // Increment the iterator before removing the use from the list. 585a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner ++UI; 586a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner SSA.RewriteUseAfterInsertions(U); 587a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner } 588a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 589a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner // Update CurAST for NewPHIs if I had pointer type. 590a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner if (I.getType()->isPointerTy()) 591a6a36f59b42703c5da0f68e0db37605c2e1633bfChris Lattner for (unsigned i = 0, e = NewPHIs.size(); i != e; ++i) 5929c282011e6b7a6e23a3a163ec9c865890449e8dcChris Lattner CurAST->copyValue(&I, NewPHIs[i]); 593a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 59498917503c702e16f35ccdec3f6b4c48e5c4759acChris Lattner // Finally, remove the instruction from CurAST. It is no longer in the loop. 59598917503c702e16f35ccdec3f6b4c48e5c4759acChris Lattner CurAST->deleteValue(&I); 596a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner} 597952eaee239d6c38f5121ed68277555344c2d6bf0Chris Lattner 59894170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// hoist - When an instruction is found to only use loop invariant operands 59994170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// that is safe to hoist, this instruction is called to do the dirty work. 60094170596b715928794a55bc5a1671e3992fd2dc9Chris Lattner/// 601a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattnervoid LICM::hoist(Instruction &I) { 602f15826999bc560ee6f67cff5ecd71bf9cce7a7aaDavid Greene DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " 60367d1d1f8322bdc460158888cd233be8d1cb1d4abEvan Cheng << I << "\n"); 604ed6dfc2856cd44a8aa608a9074eabbf42dd6cadcChris Lattner 605d9a5daeb7719c83136c0dc43d6ef732402d1a1b5Chris Lattner // Move the new node to the Preheader, before its terminator. 606d9a5daeb7719c83136c0dc43d6ef732402d1a1b5Chris Lattner I.moveBefore(Preheader->getTerminator()); 607fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 608a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (isa<LoadInst>(I)) ++NumMovedLoads; 609118dd0ce3d8e4b0a945afc95c9538d5005abacdeChris Lattner else if (isa<CallInst>(I)) ++NumMovedCalls; 6109646e6b6af1f924f9366a2bffc6dde102f84d231Chris Lattner ++NumHoisted; 611e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner Changed = true; 612e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner} 613e0e734eea052a4e8372e6f430ef41149128ba0a6Chris Lattner 614a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// isSafeToExecuteUnconditionally - Only sink or hoist an instruction if it is 615a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// not a trapping instruction or if it is a trapping instruction and is 616a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner/// guaranteed to execute. 6179966c03aad031f738718bed3bc00371e358beb5dTanya Lattner/// 618a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattnerbool LICM::isSafeToExecuteUnconditionally(Instruction &Inst) { 61992094b4d928119eceac1484331acffe950f4651cChris Lattner // If it is not a trapping instruction, it is always safe to hoist. 620f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman if (isSafeToSpeculativelyExecute(&Inst)) 6210b79a7727d68a507837e827803859424cf3d997bEli Friedman return true; 622fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 62373bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman return isGuaranteedToExecute(Inst); 62473bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman} 62573bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman 62673bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedmanbool LICM::isGuaranteedToExecute(Instruction &Inst) { 6277765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem 6287765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem // Somewhere in this loop there is an instruction which may throw and make us 6297765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem // exit the loop. 6307765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem if (MayThrow) 6317765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem return false; 6327765492a7a7e6eab36bc43558ea7c1f91e57cfecNadav Rotem 63392094b4d928119eceac1484331acffe950f4651cChris Lattner // Otherwise we have to check to make sure that the instruction dominates all 63492094b4d928119eceac1484331acffe950f4651cChris Lattner // of the exit blocks. If it doesn't, then there is a path out of the loop 63592094b4d928119eceac1484331acffe950f4651cChris Lattner // which does not execute this instruction, so we can't hoist it. 63692094b4d928119eceac1484331acffe950f4651cChris Lattner 63792094b4d928119eceac1484331acffe950f4651cChris Lattner // If the instruction is in the header block for the loop (which is very 63892094b4d928119eceac1484331acffe950f4651cChris Lattner // common), it is always guaranteed to dominate the exit blocks. Since this 63992094b4d928119eceac1484331acffe950f4651cChris Lattner // is a common case, and can save some work, check it now. 640a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner if (Inst.getParent() == CurLoop->getHeader()) 64192094b4d928119eceac1484331acffe950f4651cChris Lattner return true; 64292094b4d928119eceac1484331acffe950f4651cChris Lattner 64392094b4d928119eceac1484331acffe950f4651cChris Lattner // Get the exit blocks for the current loop. 644b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel SmallVector<BasicBlock*, 8> ExitBlocks; 6455fa802fe279f10f402e039bc931aa57c0e424bf5Chris Lattner CurLoop->getExitBlocks(ExitBlocks); 6469966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 64783fc584ea811aca780d965258c49db72a3ee8b1dChris Lattner // Verify that the block dominates each of the exit blocks of the loop. 648a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 64983fc584ea811aca780d965258c49db72a3ee8b1dChris Lattner if (!DT->dominates(Inst.getParent(), ExitBlocks[i])) 650a2706518f9cc34358cba1072f78235aa091d6d93Chris Lattner return false; 651fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 6524056a73638d3019cbd153679361411d5595f50c9Nick Lewycky // As a degenerate case, if the loop is statically infinite then we haven't 6534056a73638d3019cbd153679361411d5595f50c9Nick Lewycky // proven anything since there are no exit blocks. 6544056a73638d3019cbd153679361411d5595f50c9Nick Lewycky if (ExitBlocks.empty()) 6554056a73638d3019cbd153679361411d5595f50c9Nick Lewycky return false; 6564056a73638d3019cbd153679361411d5595f50c9Nick Lewycky 6579966c03aad031f738718bed3bc00371e358beb5dTanya Lattner return true; 6589966c03aad031f738718bed3bc00371e358beb5dTanya Lattner} 6599966c03aad031f738718bed3bc00371e358beb5dTanya Lattner 660deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattnernamespace { 661deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner class LoopPromoter : public LoadAndStorePromoter { 662deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner Value *SomePtr; // Designated pointer to store to. 663deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner SmallPtrSet<Value*, 4> &PointerMustAliases; 664deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner SmallVectorImpl<BasicBlock*> &LoopExitBlocks; 6659d1747c3cd709cd5bbc1a07074550862d188527eDan Gohman SmallVectorImpl<Instruction*> &LoopInsertPts; 666deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner AliasSetTracker &AST; 667dda266d4ce34bafed3b213ef0370cd9209159ba5Eli Friedman DebugLoc DL; 668df7102b7d6d472c58d5f0fcc16e0ebf07c8deb55Tobias Grosser int Alignment; 669503fc1c488f6c67cabe565bdc979dcd4d889ebd3Chris Lattner MDNode *TBAATag; 670deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner public: 671deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner LoopPromoter(Value *SP, 672deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner const SmallVectorImpl<Instruction*> &Insts, SSAUpdater &S, 673deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner SmallPtrSet<Value*, 4> &PMA, 6749d1747c3cd709cd5bbc1a07074550862d188527eDan Gohman SmallVectorImpl<BasicBlock*> &LEB, 6759d1747c3cd709cd5bbc1a07074550862d188527eDan Gohman SmallVectorImpl<Instruction*> &LIP, 676503fc1c488f6c67cabe565bdc979dcd4d889ebd3Chris Lattner AliasSetTracker &ast, DebugLoc dl, int alignment, 677503fc1c488f6c67cabe565bdc979dcd4d889ebd3Chris Lattner MDNode *TBAATag) 678231a5ab746ca12000aa57208869a98f78781aa6bDevang Patel : LoadAndStorePromoter(Insts, S), SomePtr(SP), 6799d1747c3cd709cd5bbc1a07074550862d188527eDan Gohman PointerMustAliases(PMA), LoopExitBlocks(LEB), LoopInsertPts(LIP), 680503fc1c488f6c67cabe565bdc979dcd4d889ebd3Chris Lattner AST(ast), DL(dl), Alignment(alignment), TBAATag(TBAATag) {} 681a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 682deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner virtual bool isInstInList(Instruction *I, 683deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner const SmallVectorImpl<Instruction*> &) const { 684deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner Value *Ptr; 685deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(I)) 686deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner Ptr = LI->getOperand(0); 687deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner else 688deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner Ptr = cast<StoreInst>(I)->getPointerOperand(); 689deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner return PointerMustAliases.count(Ptr); 690deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner } 691a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 692deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner virtual void doExtraRewritesBeforeFinalDeletion() const { 693deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner // Insert stores after in the loop exit blocks. Each exit block gets a 694deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner // store of the live-out values that feed them. Since we've already told 695deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner // the SSA updater about the defs in the loop and the preheader 696deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner // definition, it is all set and we can start using it. 697deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) { 698deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner BasicBlock *ExitBlock = LoopExitBlocks[i]; 699deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock); 7009d1747c3cd709cd5bbc1a07074550862d188527eDan Gohman Instruction *InsertPos = LoopInsertPts[i]; 701dda266d4ce34bafed3b213ef0370cd9209159ba5Eli Friedman StoreInst *NewSI = new StoreInst(LiveInValue, SomePtr, InsertPos); 702df7102b7d6d472c58d5f0fcc16e0ebf07c8deb55Tobias Grosser NewSI->setAlignment(Alignment); 703dda266d4ce34bafed3b213ef0370cd9209159ba5Eli Friedman NewSI->setDebugLoc(DL); 704503fc1c488f6c67cabe565bdc979dcd4d889ebd3Chris Lattner if (TBAATag) NewSI->setMetadata(LLVMContext::MD_tbaa, TBAATag); 705deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner } 706deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner } 707deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner 708deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner virtual void replaceLoadWithValue(LoadInst *LI, Value *V) const { 709deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner // Update alias analysis. 710deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner AST.copyValue(LI, V); 711deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner } 712deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner virtual void instructionDeleted(Instruction *I) const { 713deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner AST.deleteValue(I); 714deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner } 715deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner }; 716deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner} // end anon namespace 717deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner 718e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner/// PromoteAliasSet - Try to promote memory values to scalars by sinking 7192e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// stores out of the loop and moving loads to before the loop. We do this by 7202e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// looping over the stores in the loop, looking for stores to Must pointers 721e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner/// which are loop invariant. 7222e6e741b737960ecd0b68610875050019aac0f07Chris Lattner/// 7239d1747c3cd709cd5bbc1a07074550862d188527eDan Gohmanvoid LICM::PromoteAliasSet(AliasSet &AS, 7249d1747c3cd709cd5bbc1a07074550862d188527eDan Gohman SmallVectorImpl<BasicBlock*> &ExitBlocks, 7259d1747c3cd709cd5bbc1a07074550862d188527eDan Gohman SmallVectorImpl<Instruction*> &InsertPts) { 726e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // We can promote this alias set if it has a store, if it is a "Must" alias 727e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // set, if the pointer is loop invariant, and if we are not eliminating any 728e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // volatile loads or stores. 729e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() || 730e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner AS.isVolatile() || !CurLoop->isLoopInvariant(AS.begin()->getValue())) 731e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner return; 732a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 733e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner assert(!AS.empty() && 734e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner "Must alias set should have at least one pointer element in it!"); 735e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner Value *SomePtr = AS.begin()->getValue(); 736fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 737e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // It isn't safe to promote a load/store from the loop if the load/store is 738e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // conditional. For example, turning: 7392e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // 740e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // for () { if (c) *P += 1; } 7412e6e741b737960ecd0b68610875050019aac0f07Chris Lattner // 742e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // into: 743e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // 744e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // tmp = *P; for () { if (c) tmp +=1; } *P = tmp; 745e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // 746e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // is not safe, because *P may only be valid to access if 'c' is true. 747a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser // 748e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // It is safe to promote P if all uses are direct load/stores and if at 749e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // least one is guaranteed to be executed. 750e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner bool GuaranteedToExecute = false; 751df7102b7d6d472c58d5f0fcc16e0ebf07c8deb55Tobias Grosser 752e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner SmallVector<Instruction*, 64> LoopUses; 753e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner SmallPtrSet<Value*, 4> PointerMustAliases; 754e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 755df7102b7d6d472c58d5f0fcc16e0ebf07c8deb55Tobias Grosser // We start with an alignment of one and try to find instructions that allow 756df7102b7d6d472c58d5f0fcc16e0ebf07c8deb55Tobias Grosser // us to prove better alignment. 757df7102b7d6d472c58d5f0fcc16e0ebf07c8deb55Tobias Grosser unsigned Alignment = 1; 758503fc1c488f6c67cabe565bdc979dcd4d889ebd3Chris Lattner MDNode *TBAATag = 0; 759df7102b7d6d472c58d5f0fcc16e0ebf07c8deb55Tobias Grosser 760e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // Check that all of the pointers in the alias set have the same type. We 761e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // cannot (yet) promote a memory location that is loaded and stored in 762503fc1c488f6c67cabe565bdc979dcd4d889ebd3Chris Lattner // different sizes. While we are at it, collect alignment and TBAA info. 763e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) { 764e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner Value *ASIV = ASI->getValue(); 765e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner PointerMustAliases.insert(ASIV); 766a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 76729d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner // Check that all of the pointers in the alias set have the same type. We 76829d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner // cannot (yet) promote a memory location that is loaded and stored in 76929d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner // different sizes. 770e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner if (SomePtr->getType() != ASIV->getType()) 771e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner return; 772a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 773e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner for (Value::use_iterator UI = ASIV->use_begin(), UE = ASIV->use_end(); 77419d9d4364e514f316f8757b577bb8bb33c22dbfcChris Lattner UI != UE; ++UI) { 775e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // Ignore instructions that are outside the loop. 77629d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner Instruction *Use = dyn_cast<Instruction>(*UI); 77792329c7fbe572892c17aa2d2542a10e3ea16132fDan Gohman if (!Use || !CurLoop->contains(Use)) 77829d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner continue; 779a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 780e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // If there is an non-load/store instruction in the loop, we can't promote 781e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // it. 78297671565ffd341d1d3291243f9f51edc6b64b065Eli Friedman if (LoadInst *load = dyn_cast<LoadInst>(Use)) { 78397671565ffd341d1d3291243f9f51edc6b64b065Eli Friedman assert(!load->isVolatile() && "AST broken"); 78497671565ffd341d1d3291243f9f51edc6b64b065Eli Friedman if (!load->isSimple()) 78597671565ffd341d1d3291243f9f51edc6b64b065Eli Friedman return; 786df7102b7d6d472c58d5f0fcc16e0ebf07c8deb55Tobias Grosser } else if (StoreInst *store = dyn_cast<StoreInst>(Use)) { 7871dec0d27048725cf73f73ce4f0bb97ca78255f97Chris Lattner // Stores *of* the pointer are not interesting, only stores *to* the 7881dec0d27048725cf73f73ce4f0bb97ca78255f97Chris Lattner // pointer. 7891dec0d27048725cf73f73ce4f0bb97ca78255f97Chris Lattner if (Use->getOperand(1) != ASIV) 7901dec0d27048725cf73f73ce4f0bb97ca78255f97Chris Lattner continue; 79197671565ffd341d1d3291243f9f51edc6b64b065Eli Friedman assert(!store->isVolatile() && "AST broken"); 79297671565ffd341d1d3291243f9f51edc6b64b065Eli Friedman if (!store->isSimple()) 79397671565ffd341d1d3291243f9f51edc6b64b065Eli Friedman return; 794df7102b7d6d472c58d5f0fcc16e0ebf07c8deb55Tobias Grosser 79573bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman // Note that we only check GuaranteedToExecute inside the store case 79673bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman // so that we do not introduce stores where they did not exist before 79773bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman // (which would break the LLVM concurrency model). 79873bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman 79973bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman // If the alignment of this instruction allows us to specify a more 80073bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman // restrictive (and performant) alignment and if we are sure this 80173bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman // instruction will be executed, update the alignment. 80273bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman // Larger is better, with the exception of 0 being the best alignment. 80397671565ffd341d1d3291243f9f51edc6b64b065Eli Friedman unsigned InstAlignment = store->getAlignment(); 804503fc1c488f6c67cabe565bdc979dcd4d889ebd3Chris Lattner if ((InstAlignment > Alignment || InstAlignment == 0) && Alignment != 0) 80573bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman if (isGuaranteedToExecute(*Use)) { 80673bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman GuaranteedToExecute = true; 80773bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman Alignment = InstAlignment; 80873bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman } 80973bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman 81073bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman if (!GuaranteedToExecute) 81173bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman GuaranteedToExecute = isGuaranteedToExecute(*Use); 812df7102b7d6d472c58d5f0fcc16e0ebf07c8deb55Tobias Grosser 81373bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman } else 81473bfa4aecf25da5d37261c9ad608ba88b20e0860Eli Friedman return; // Not a load or store. 815a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 816503fc1c488f6c67cabe565bdc979dcd4d889ebd3Chris Lattner // Merge the TBAA tags. 817503fc1c488f6c67cabe565bdc979dcd4d889ebd3Chris Lattner if (LoopUses.empty()) { 818503fc1c488f6c67cabe565bdc979dcd4d889ebd3Chris Lattner // On the first load/store, just take its TBAA tag. 819503fc1c488f6c67cabe565bdc979dcd4d889ebd3Chris Lattner TBAATag = Use->getMetadata(LLVMContext::MD_tbaa); 820261304248f4f2cd0d9f0f85f91d400bcedeb0f45Chris Lattner } else if (TBAATag) { 821261304248f4f2cd0d9f0f85f91d400bcedeb0f45Chris Lattner TBAATag = MDNode::getMostGenericTBAA(TBAATag, 822261304248f4f2cd0d9f0f85f91d400bcedeb0f45Chris Lattner Use->getMetadata(LLVMContext::MD_tbaa)); 823503fc1c488f6c67cabe565bdc979dcd4d889ebd3Chris Lattner } 824261304248f4f2cd0d9f0f85f91d400bcedeb0f45Chris Lattner 825e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner LoopUses.push_back(Use); 82629d929363d9b8a2c0d40c5d50fec022c736cb654Chris Lattner } 827e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner } 828df7102b7d6d472c58d5f0fcc16e0ebf07c8deb55Tobias Grosser 829e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // If there isn't a guaranteed-to-execute instruction, we can't promote. 830e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner if (!GuaranteedToExecute) 831e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner return; 832a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 833e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // Otherwise, this is safe to promote, lets do it! 834a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " <<*SomePtr<<'\n'); 835e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner Changed = true; 836e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner ++NumPromoted; 837bc2265abe1d1b830995bb2f6322409bc7d7c5740Devang Patel 838dda266d4ce34bafed3b213ef0370cd9209159ba5Eli Friedman // Grab a debug location for the inserted loads/stores; given that the 839dda266d4ce34bafed3b213ef0370cd9209159ba5Eli Friedman // inserted loads/stores have little relation to the original loads/stores, 840dda266d4ce34bafed3b213ef0370cd9209159ba5Eli Friedman // this code just arbitrarily picks a location from one, since any debug 841dda266d4ce34bafed3b213ef0370cd9209159ba5Eli Friedman // location is better than none. 842dda266d4ce34bafed3b213ef0370cd9209159ba5Eli Friedman DebugLoc DL = LoopUses[0]->getDebugLoc(); 843dda266d4ce34bafed3b213ef0370cd9209159ba5Eli Friedman 8449d1747c3cd709cd5bbc1a07074550862d188527eDan Gohman // Figure out the loop exits and their insertion points, if this is the 8459d1747c3cd709cd5bbc1a07074550862d188527eDan Gohman // first promotion. 8469d1747c3cd709cd5bbc1a07074550862d188527eDan Gohman if (ExitBlocks.empty()) { 8479d1747c3cd709cd5bbc1a07074550862d188527eDan Gohman CurLoop->getUniqueExitBlocks(ExitBlocks); 8489d1747c3cd709cd5bbc1a07074550862d188527eDan Gohman InsertPts.resize(ExitBlocks.size()); 8499d1747c3cd709cd5bbc1a07074550862d188527eDan Gohman for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 8509d1747c3cd709cd5bbc1a07074550862d188527eDan Gohman InsertPts[i] = ExitBlocks[i]->getFirstInsertionPt(); 8519d1747c3cd709cd5bbc1a07074550862d188527eDan Gohman } 852a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 853e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner // We use the SSAUpdater interface to insert phi nodes as required. 854e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner SmallVector<PHINode*, 16> NewPHIs; 855e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner SSAUpdater SSA(&NewPHIs); 856deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner LoopPromoter Promoter(SomePtr, LoopUses, SSA, PointerMustAliases, ExitBlocks, 857503fc1c488f6c67cabe565bdc979dcd4d889ebd3Chris Lattner InsertPts, *CurAST, DL, Alignment, TBAATag); 858a3574fb7e5b7b4517eb81c8c76f05e5be05eec1bTobias Grosser 859deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner // Set up the preheader to have a definition of the value. It is the live-out 860deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner // value from the preheader that uses in the loop will use. 861deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner LoadInst *PreheaderLoad = 862deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner new LoadInst(SomePtr, SomePtr->getName()+".promoted", 863deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner Preheader->getTerminator()); 864df7102b7d6d472c58d5f0fcc16e0ebf07c8deb55Tobias Grosser PreheaderLoad->setAlignment(Alignment); 865dda266d4ce34bafed3b213ef0370cd9209159ba5Eli Friedman PreheaderLoad->setDebugLoc(DL); 866503fc1c488f6c67cabe565bdc979dcd4d889ebd3Chris Lattner if (TBAATag) PreheaderLoad->setMetadata(LLVMContext::MD_tbaa, TBAATag); 867e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner SSA.AddAvailableValue(Preheader, PreheaderLoad); 868e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 869deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner // Rewrite all the loads in the loop and remember all the definitions from 870deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner // stores in the loop. 871deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner Promoter.run(LoopUses); 8720e382192c1a7750a157e470f749645ac2266d317Eli Friedman 8730e382192c1a7750a157e470f749645ac2266d317Eli Friedman // If the SSAUpdater didn't use the load in the preheader, just zap it now. 8740e382192c1a7750a157e470f749645ac2266d317Eli Friedman if (PreheaderLoad->use_empty()) 8750e382192c1a7750a157e470f749645ac2266d317Eli Friedman PreheaderLoad->eraseFromParent(); 876f5e84aa0887d3fcd752d4a4fa1bb0e526be49f20Chris Lattner} 87791d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel 878e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0Chris Lattner 87991d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel/// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info. 88091d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patelvoid LICM::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L) { 8814282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner AliasSetTracker *AST = LoopToAliasSetMap.lookup(L); 88291d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel if (!AST) 88391d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel return; 88491d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel 88591d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel AST->copyValue(From, To); 88691d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel} 88791d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel 88891d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel/// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias 88991d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel/// set. 89091d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patelvoid LICM::deleteAnalysisValue(Value *V, Loop *L) { 8914282e32712da220fd97177772e22ec1ee7e50af2Chris Lattner AliasSetTracker *AST = LoopToAliasSetMap.lookup(L); 89291d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel if (!AST) 89391d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel return; 89491d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel 89591d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel AST->deleteValue(V); 89691d22c8b1ec2ad8f2f29804b729473ccf720fb3eDevang Patel} 897