Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 1 | //===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===// |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 2 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 7 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 9 | // |
Chris Lattner | 92094b4 | 2003-12-09 17:18:00 +0000 | [diff] [blame] | 10 | // This pass performs loop invariant code motion, attempting to remove as much |
| 11 | // code from the body of a loop as possible. It does this by either hoisting |
| 12 | // code into the preheader block, or by sinking code to the exit blocks if it is |
| 13 | // safe. This pass also promotes must-aliased memory locations in the loop to |
Chris Lattner | e4365b2 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 14 | // live in registers, thus hoisting and sinking "invariant" loads and stores. |
Chris Lattner | 92094b4 | 2003-12-09 17:18:00 +0000 | [diff] [blame] | 15 | // |
| 16 | // This pass uses alias analysis for two purposes: |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 17 | // |
Chris Lattner | 2741c97 | 2004-05-23 21:20:19 +0000 | [diff] [blame] | 18 | // 1. Moving loop invariant loads and calls out of loops. If we can determine |
| 19 | // that a load or call inside of a loop never aliases anything stored to, |
| 20 | // we can hoist it or sink it like any other instruction. |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 21 | // 2. Scalar Promotion of Memory - If there is a store instruction inside of |
| 22 | // the loop, we try to move the store to happen AFTER the loop instead of |
| 23 | // inside of the loop. This can only happen if a few conditions are true: |
| 24 | // A. The pointer stored through is loop invariant |
| 25 | // B. There are no stores or loads in the loop which _may_ alias the |
| 26 | // pointer. There are no calls in the loop which mod/ref the pointer. |
| 27 | // If these conditions are true, we can promote the loads and stores in the |
| 28 | // loop of the pointer to use a temporary alloca'd variable. We then use |
| 29 | // the mem2reg functionality to construct the appropriate SSA form for the |
| 30 | // variable. |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 31 | // |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 32 | //===----------------------------------------------------------------------===// |
| 33 | |
Chris Lattner | 1f309c1 | 2005-03-23 21:00:12 +0000 | [diff] [blame] | 34 | #define DEBUG_TYPE "licm" |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 35 | #include "llvm/Transforms/Scalar.h" |
Chris Lattner | 79066fa | 2007-01-30 23:46:24 +0000 | [diff] [blame] | 36 | #include "llvm/Constants.h" |
Chris Lattner | 2741c97 | 2004-05-23 21:20:19 +0000 | [diff] [blame] | 37 | #include "llvm/DerivedTypes.h" |
| 38 | #include "llvm/Instructions.h" |
Owen Anderson | 1ff50b3 | 2009-07-03 00:54:20 +0000 | [diff] [blame] | 39 | #include "llvm/LLVMContext.h" |
Chris Lattner | 2741c97 | 2004-05-23 21:20:19 +0000 | [diff] [blame] | 40 | #include "llvm/Target/TargetData.h" |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 41 | #include "llvm/Analysis/LoopInfo.h" |
Devang Patel | 54959d6 | 2007-03-07 04:41:30 +0000 | [diff] [blame] | 42 | #include "llvm/Analysis/LoopPass.h" |
Chris Lattner | f5e84aa | 2002-08-22 21:39:55 +0000 | [diff] [blame] | 43 | #include "llvm/Analysis/AliasAnalysis.h" |
Chris Lattner | 0252e49 | 2003-03-03 23:32:45 +0000 | [diff] [blame] | 44 | #include "llvm/Analysis/AliasSetTracker.h" |
Chris Lattner | 952eaee | 2002-09-29 21:46:09 +0000 | [diff] [blame] | 45 | #include "llvm/Analysis/Dominators.h" |
Devang Patel | 96b651c | 2007-07-30 20:19:59 +0000 | [diff] [blame] | 46 | #include "llvm/Analysis/ScalarEvolution.h" |
Chris Lattner | 2741c97 | 2004-05-23 21:20:19 +0000 | [diff] [blame] | 47 | #include "llvm/Transforms/Utils/PromoteMemToReg.h" |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 48 | #include "llvm/Support/CFG.h" |
| 49 | #include "llvm/Support/Compiler.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 50 | #include "llvm/Support/CommandLine.h" |
| 51 | #include "llvm/Support/Debug.h" |
| 52 | #include "llvm/ADT/Statistic.h" |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 53 | #include <algorithm> |
Chris Lattner | 92094b4 | 2003-12-09 17:18:00 +0000 | [diff] [blame] | 54 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 55 | |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 56 | STATISTIC(NumSunk , "Number of instructions sunk out of loop"); |
| 57 | STATISTIC(NumHoisted , "Number of instructions hoisted out of loop"); |
| 58 | STATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk"); |
| 59 | STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk"); |
| 60 | STATISTIC(NumPromoted , "Number of memory locations promoted to registers"); |
| 61 | |
Dan Gohman | 844731a | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 62 | static cl::opt<bool> |
| 63 | DisablePromotion("disable-licm-promotion", cl::Hidden, |
| 64 | cl::desc("Disable memory promotion in LICM pass")); |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 65 | |
Chris Lattner | d7168dd | 2009-03-09 05:11:09 +0000 | [diff] [blame] | 66 | // This feature is currently disabled by default because CodeGen is not yet |
| 67 | // capable of rematerializing these constants in PIC mode, so it can lead to |
| 68 | // degraded performance. Compile test/CodeGen/X86/remat-constant.ll with |
Dan Gohman | 3eee654 | 2008-07-24 23:57:25 +0000 | [diff] [blame] | 69 | // -relocation-model=pic to see an example of this. |
| 70 | static cl::opt<bool> |
| 71 | EnableLICMConstantMotion("enable-licm-constant-variables", cl::Hidden, |
| 72 | cl::desc("Enable hoisting/sinking of constant " |
| 73 | "global variables")); |
| 74 | |
Dan Gohman | 844731a | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 75 | namespace { |
Devang Patel | 54959d6 | 2007-03-07 04:41:30 +0000 | [diff] [blame] | 76 | struct VISIBILITY_HIDDEN LICM : public LoopPass { |
Nick Lewycky | ecd94c8 | 2007-05-06 13:37:16 +0000 | [diff] [blame] | 77 | static char ID; // Pass identification, replacement for typeid |
Dan Gohman | ae73dc1 | 2008-09-04 17:05:41 +0000 | [diff] [blame] | 78 | LICM() : LoopPass(&ID) {} |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 79 | |
Devang Patel | 54959d6 | 2007-03-07 04:41:30 +0000 | [diff] [blame] | 80 | virtual bool runOnLoop(Loop *L, LPPassManager &LPM); |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 81 | |
Chris Lattner | 9417059 | 2002-09-26 16:52:07 +0000 | [diff] [blame] | 82 | /// This transformation requires natural loop information & requires that |
| 83 | /// loop preheaders be inserted into the CFG... |
| 84 | /// |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 85 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
Chris Lattner | cb2610e | 2002-10-21 20:00:28 +0000 | [diff] [blame] | 86 | AU.setPreservesCFG(); |
Chris Lattner | 98bf436 | 2003-10-12 21:52:28 +0000 | [diff] [blame] | 87 | AU.addRequiredID(LoopSimplifyID); |
Chris Lattner | 5f0eb8d | 2002-08-08 19:01:30 +0000 | [diff] [blame] | 88 | AU.addRequired<LoopInfo>(); |
Owen Anderson | 3a2b58f | 2007-04-24 06:40:39 +0000 | [diff] [blame] | 89 | AU.addRequired<DominatorTree>(); |
Chris Lattner | 0252e49 | 2003-03-03 23:32:45 +0000 | [diff] [blame] | 90 | AU.addRequired<DominanceFrontier>(); // For scalar promotion (mem2reg) |
Chris Lattner | f5e84aa | 2002-08-22 21:39:55 +0000 | [diff] [blame] | 91 | AU.addRequired<AliasAnalysis>(); |
Devang Patel | 96b651c | 2007-07-30 20:19:59 +0000 | [diff] [blame] | 92 | AU.addPreserved<ScalarEvolution>(); |
| 93 | AU.addPreserved<DominanceFrontier>(); |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 94 | } |
| 95 | |
Dan Gohman | 747603e | 2007-04-17 18:21:36 +0000 | [diff] [blame] | 96 | bool doFinalization() { |
Anton Korobeynikov | fd94dd5 | 2007-11-25 23:52:02 +0000 | [diff] [blame] | 97 | // Free the values stored in the map |
| 98 | for (std::map<Loop *, AliasSetTracker *>::iterator |
| 99 | I = LoopToAliasMap.begin(), E = LoopToAliasMap.end(); I != E; ++I) |
| 100 | delete I->second; |
| 101 | |
Devang Patel | 54959d6 | 2007-03-07 04:41:30 +0000 | [diff] [blame] | 102 | LoopToAliasMap.clear(); |
| 103 | return false; |
| 104 | } |
| 105 | |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 106 | private: |
Chris Lattner | 92094b4 | 2003-12-09 17:18:00 +0000 | [diff] [blame] | 107 | // Various analyses that we use... |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 108 | AliasAnalysis *AA; // Current AliasAnalysis information |
Chris Lattner | 92094b4 | 2003-12-09 17:18:00 +0000 | [diff] [blame] | 109 | LoopInfo *LI; // Current LoopInfo |
Owen Anderson | 3a2b58f | 2007-04-24 06:40:39 +0000 | [diff] [blame] | 110 | DominatorTree *DT; // Dominator Tree for the current Loop... |
Chris Lattner | 43f820d | 2003-10-05 21:20:13 +0000 | [diff] [blame] | 111 | DominanceFrontier *DF; // Current Dominance Frontier |
Chris Lattner | 92094b4 | 2003-12-09 17:18:00 +0000 | [diff] [blame] | 112 | |
| 113 | // State that is updated as we process loops |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 114 | bool Changed; // Set to true when we change anything. |
| 115 | BasicBlock *Preheader; // The preheader block of the current loop... |
| 116 | Loop *CurLoop; // The current loop we are working on... |
Chris Lattner | 0252e49 | 2003-03-03 23:32:45 +0000 | [diff] [blame] | 117 | AliasSetTracker *CurAST; // AliasSet information for the current loop... |
Devang Patel | 54959d6 | 2007-03-07 04:41:30 +0000 | [diff] [blame] | 118 | std::map<Loop *, AliasSetTracker *> LoopToAliasMap; |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 119 | |
Devang Patel | 91d22c8 | 2007-07-31 08:01:41 +0000 | [diff] [blame] | 120 | /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info. |
| 121 | void cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L); |
| 122 | |
| 123 | /// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias |
| 124 | /// set. |
| 125 | void deleteAnalysisValue(Value *V, Loop *L); |
| 126 | |
Chris Lattner | e4365b2 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 127 | /// SinkRegion - Walk the specified region of the CFG (defined by all blocks |
| 128 | /// dominated by the specified block, and that are in the current loop) in |
Owen Anderson | 3a2b58f | 2007-04-24 06:40:39 +0000 | [diff] [blame] | 129 | /// reverse depth first order w.r.t the DominatorTree. This allows us to |
Chris Lattner | e4365b2 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 130 | /// visit uses before definitions, allowing us to sink a loop body in one |
| 131 | /// pass without iteration. |
| 132 | /// |
Devang Patel | 2604242 | 2007-06-04 00:32:22 +0000 | [diff] [blame] | 133 | void SinkRegion(DomTreeNode *N); |
Chris Lattner | e4365b2 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 134 | |
Chris Lattner | 952eaee | 2002-09-29 21:46:09 +0000 | [diff] [blame] | 135 | /// HoistRegion - Walk the specified region of the CFG (defined by all |
| 136 | /// blocks dominated by the specified block, and that are in the current |
Owen Anderson | 3a2b58f | 2007-04-24 06:40:39 +0000 | [diff] [blame] | 137 | /// loop) in depth first order w.r.t the DominatorTree. This allows us to |
Misha Brukman | cf00c4a | 2003-10-10 17:57:28 +0000 | [diff] [blame] | 138 | /// visit definitions before uses, allowing us to hoist a loop body in one |
Chris Lattner | 952eaee | 2002-09-29 21:46:09 +0000 | [diff] [blame] | 139 | /// pass without iteration. |
| 140 | /// |
Devang Patel | 2604242 | 2007-06-04 00:32:22 +0000 | [diff] [blame] | 141 | void HoistRegion(DomTreeNode *N); |
Chris Lattner | 952eaee | 2002-09-29 21:46:09 +0000 | [diff] [blame] | 142 | |
Chris Lattner | b461373 | 2002-09-29 22:26:07 +0000 | [diff] [blame] | 143 | /// inSubLoop - Little predicate that returns true if the specified basic |
| 144 | /// block is in a subloop of the current one, not the current one itself. |
Chris Lattner | 9417059 | 2002-09-26 16:52:07 +0000 | [diff] [blame] | 145 | /// |
Chris Lattner | b461373 | 2002-09-29 22:26:07 +0000 | [diff] [blame] | 146 | bool inSubLoop(BasicBlock *BB) { |
| 147 | assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop"); |
Chris Lattner | 329c1c6 | 2004-01-08 00:09:44 +0000 | [diff] [blame] | 148 | for (Loop::iterator I = CurLoop->begin(), E = CurLoop->end(); I != E; ++I) |
| 149 | if ((*I)->contains(BB)) |
Chris Lattner | b461373 | 2002-09-29 22:26:07 +0000 | [diff] [blame] | 150 | return true; // A subloop actually contains this block! |
| 151 | return false; |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 152 | } |
| 153 | |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 154 | /// isExitBlockDominatedByBlockInLoop - This method checks to see if the |
| 155 | /// specified exit block of the loop is dominated by the specified block |
| 156 | /// that is in the body of the loop. We use these constraints to |
| 157 | /// dramatically limit the amount of the dominator tree that needs to be |
| 158 | /// searched. |
| 159 | bool isExitBlockDominatedByBlockInLoop(BasicBlock *ExitBlock, |
| 160 | BasicBlock *BlockInLoop) const { |
| 161 | // If the block in the loop is the loop header, it must be dominated! |
| 162 | BasicBlock *LoopHeader = CurLoop->getHeader(); |
| 163 | if (BlockInLoop == LoopHeader) |
| 164 | return true; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 165 | |
Devang Patel | 2604242 | 2007-06-04 00:32:22 +0000 | [diff] [blame] | 166 | DomTreeNode *BlockInLoopNode = DT->getNode(BlockInLoop); |
| 167 | DomTreeNode *IDom = DT->getNode(ExitBlock); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 168 | |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 169 | // Because the exit block is not in the loop, we know we have to get _at |
Chris Lattner | 2741c97 | 2004-05-23 21:20:19 +0000 | [diff] [blame] | 170 | // least_ its immediate dominator. |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 171 | do { |
| 172 | // Get next Immediate Dominator. |
Owen Anderson | 3a2b58f | 2007-04-24 06:40:39 +0000 | [diff] [blame] | 173 | IDom = IDom->getIDom(); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 174 | |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 175 | // If we have got to the header of the loop, then the instructions block |
| 176 | // did not dominate the exit node, so we can't hoist it. |
Owen Anderson | 3a2b58f | 2007-04-24 06:40:39 +0000 | [diff] [blame] | 177 | if (IDom->getBlock() == LoopHeader) |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 178 | return false; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 179 | |
Owen Anderson | 3a2b58f | 2007-04-24 06:40:39 +0000 | [diff] [blame] | 180 | } while (IDom != BlockInLoopNode); |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 181 | |
| 182 | return true; |
| 183 | } |
| 184 | |
| 185 | /// sink - When an instruction is found to only be used outside of the loop, |
| 186 | /// this function moves it to the exit blocks and patches up SSA form as |
| 187 | /// needed. |
| 188 | /// |
| 189 | void sink(Instruction &I); |
| 190 | |
Chris Lattner | 9417059 | 2002-09-26 16:52:07 +0000 | [diff] [blame] | 191 | /// hoist - When an instruction is found to only use loop invariant operands |
| 192 | /// that is safe to hoist, this instruction is called to do the dirty work. |
| 193 | /// |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 194 | void hoist(Instruction &I); |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 195 | |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 196 | /// isSafeToExecuteUnconditionally - Only sink or hoist an instruction if it |
| 197 | /// is not a trapping instruction or if it is a trapping instruction and is |
| 198 | /// guaranteed to execute. |
Tanya Lattner | 9966c03 | 2003-08-05 18:45:46 +0000 | [diff] [blame] | 199 | /// |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 200 | bool isSafeToExecuteUnconditionally(Instruction &I); |
Tanya Lattner | 9966c03 | 2003-08-05 18:45:46 +0000 | [diff] [blame] | 201 | |
Chris Lattner | 9417059 | 2002-09-26 16:52:07 +0000 | [diff] [blame] | 202 | /// pointerInvalidatedByLoop - Return true if the body of this loop may |
| 203 | /// store into the memory location pointed to by V. |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 204 | /// |
Chris Lattner | f3e1d69 | 2004-11-26 21:20:09 +0000 | [diff] [blame] | 205 | bool pointerInvalidatedByLoop(Value *V, unsigned Size) { |
Chris Lattner | 0252e49 | 2003-03-03 23:32:45 +0000 | [diff] [blame] | 206 | // Check to see if any of the basic blocks in CurLoop invalidate *V. |
Chris Lattner | f3e1d69 | 2004-11-26 21:20:09 +0000 | [diff] [blame] | 207 | return CurAST->getAliasSetForPointer(V, Size).isMod(); |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 208 | } |
Chris Lattner | f5e84aa | 2002-08-22 21:39:55 +0000 | [diff] [blame] | 209 | |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 210 | bool canSinkOrHoistInst(Instruction &I); |
| 211 | bool isLoopInvariantInst(Instruction &I); |
| 212 | bool isNotUsedInLoop(Instruction &I); |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 213 | |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 214 | /// PromoteValuesInLoop - Look at the stores in the loop and promote as many |
| 215 | /// to scalars as we can. |
| 216 | /// |
| 217 | void PromoteValuesInLoop(); |
| 218 | |
Chris Lattner | fb3ee19 | 2004-09-15 01:04:07 +0000 | [diff] [blame] | 219 | /// FindPromotableValuesInLoop - Check the current loop for stores to |
Misha Brukman | 352361b | 2003-09-11 15:32:37 +0000 | [diff] [blame] | 220 | /// definite pointers, which are not loaded and stored through may aliases. |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 221 | /// If these are found, create an alloca for the value, add it to the |
| 222 | /// PromotedValues list, and keep track of the mapping from value to |
| 223 | /// alloca... |
| 224 | /// |
Chris Lattner | fb3ee19 | 2004-09-15 01:04:07 +0000 | [diff] [blame] | 225 | void FindPromotableValuesInLoop( |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 226 | std::vector<std::pair<AllocaInst*, Value*> > &PromotedValues, |
| 227 | std::map<Value*, AllocaInst*> &Val2AlMap); |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 228 | }; |
| 229 | } |
| 230 | |
Dan Gohman | 844731a | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 231 | char LICM::ID = 0; |
| 232 | static RegisterPass<LICM> X("licm", "Loop Invariant Code Motion"); |
| 233 | |
Daniel Dunbar | 394f044 | 2008-10-22 23:32:42 +0000 | [diff] [blame] | 234 | Pass *llvm::createLICMPass() { return new LICM(); } |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 235 | |
Devang Patel | 8d246f0 | 2007-07-31 16:52:25 +0000 | [diff] [blame] | 236 | /// Hoist expressions out of the specified loop. Note, alias info for inner |
| 237 | /// loop is not preserved so it is not a good idea to run LICM multiple |
| 238 | /// times on one loop. |
Chris Lattner | 9417059 | 2002-09-26 16:52:07 +0000 | [diff] [blame] | 239 | /// |
Devang Patel | 54959d6 | 2007-03-07 04:41:30 +0000 | [diff] [blame] | 240 | bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) { |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 241 | Changed = false; |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 242 | |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 243 | // Get our Loop and Alias Analysis information... |
| 244 | LI = &getAnalysis<LoopInfo>(); |
Chris Lattner | f5e84aa | 2002-08-22 21:39:55 +0000 | [diff] [blame] | 245 | AA = &getAnalysis<AliasAnalysis>(); |
Chris Lattner | 43f820d | 2003-10-05 21:20:13 +0000 | [diff] [blame] | 246 | DF = &getAnalysis<DominanceFrontier>(); |
Owen Anderson | 3a2b58f | 2007-04-24 06:40:39 +0000 | [diff] [blame] | 247 | DT = &getAnalysis<DominatorTree>(); |
Chris Lattner | f5e84aa | 2002-08-22 21:39:55 +0000 | [diff] [blame] | 248 | |
Devang Patel | 54959d6 | 2007-03-07 04:41:30 +0000 | [diff] [blame] | 249 | CurAST = new AliasSetTracker(*AA); |
Devang Patel | f38ac5d | 2007-05-30 15:29:37 +0000 | [diff] [blame] | 250 | // Collect Alias info from subloops |
Devang Patel | 54959d6 | 2007-03-07 04:41:30 +0000 | [diff] [blame] | 251 | for (Loop::iterator LoopItr = L->begin(), LoopItrE = L->end(); |
| 252 | LoopItr != LoopItrE; ++LoopItr) { |
| 253 | Loop *InnerL = *LoopItr; |
| 254 | AliasSetTracker *InnerAST = LoopToAliasMap[InnerL]; |
| 255 | assert (InnerAST && "Where is my AST?"); |
| 256 | |
| 257 | // What if InnerLoop was modified by other passes ? |
| 258 | CurAST->add(*InnerAST); |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 259 | } |
Devang Patel | 54959d6 | 2007-03-07 04:41:30 +0000 | [diff] [blame] | 260 | |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 261 | CurLoop = L; |
| 262 | |
Chris Lattner | 99a5721 | 2002-09-26 19:40:25 +0000 | [diff] [blame] | 263 | // Get the preheader block to move instructions into... |
| 264 | Preheader = L->getLoopPreheader(); |
| 265 | assert(Preheader&&"Preheader insertion pass guarantees we have a preheader!"); |
| 266 | |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 267 | // Loop over the body of this loop, looking for calls, invokes, and stores. |
Chris Lattner | 0252e49 | 2003-03-03 23:32:45 +0000 | [diff] [blame] | 268 | // Because subloops have already been incorporated into AST, we skip blocks in |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 269 | // subloops. |
| 270 | // |
Dan Gohman | 9b78763 | 2008-06-22 20:18:58 +0000 | [diff] [blame] | 271 | for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); |
| 272 | I != E; ++I) { |
| 273 | BasicBlock *BB = *I; |
| 274 | if (LI->getLoopFor(BB) == L) // Ignore blocks in subloops... |
| 275 | CurAST->add(*BB); // Incorporate the specified basic block |
| 276 | } |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 277 | |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 278 | // We want to visit all of the instructions in this loop... that are not parts |
| 279 | // of our subloops (they have already had their invariants hoisted out of |
| 280 | // their loop, into this loop, so there is no need to process the BODIES of |
| 281 | // the subloops). |
| 282 | // |
Chris Lattner | 952eaee | 2002-09-29 21:46:09 +0000 | [diff] [blame] | 283 | // Traverse the body of the loop in depth first order on the dominator tree so |
| 284 | // that we are guaranteed to see definitions before we see uses. This allows |
Nick Lewycky | af5cbc8 | 2007-08-18 15:08:56 +0000 | [diff] [blame] | 285 | // us to sink instructions in one pass, without iteration. After sinking |
Chris Lattner | e4365b2 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 286 | // instructions, we perform another pass to hoist them out of the loop. |
Chris Lattner | 952eaee | 2002-09-29 21:46:09 +0000 | [diff] [blame] | 287 | // |
Owen Anderson | 3a2b58f | 2007-04-24 06:40:39 +0000 | [diff] [blame] | 288 | SinkRegion(DT->getNode(L->getHeader())); |
| 289 | HoistRegion(DT->getNode(L->getHeader())); |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 290 | |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 291 | // Now that all loop invariants have been removed from the loop, promote any |
| 292 | // memory references to scalars that we can... |
| 293 | if (!DisablePromotion) |
| 294 | PromoteValuesInLoop(); |
| 295 | |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 296 | // Clear out loops state information for the next iteration |
| 297 | CurLoop = 0; |
Chris Lattner | 99a5721 | 2002-09-26 19:40:25 +0000 | [diff] [blame] | 298 | Preheader = 0; |
Devang Patel | 54959d6 | 2007-03-07 04:41:30 +0000 | [diff] [blame] | 299 | |
| 300 | LoopToAliasMap[L] = CurAST; |
| 301 | return Changed; |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 302 | } |
| 303 | |
Chris Lattner | e4365b2 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 304 | /// SinkRegion - Walk the specified region of the CFG (defined by all blocks |
| 305 | /// dominated by the specified block, and that are in the current loop) in |
Owen Anderson | 3a2b58f | 2007-04-24 06:40:39 +0000 | [diff] [blame] | 306 | /// reverse depth first order w.r.t the DominatorTree. This allows us to visit |
Chris Lattner | e4365b2 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 307 | /// uses before definitions, allowing us to sink a loop body in one pass without |
| 308 | /// iteration. |
| 309 | /// |
Devang Patel | 2604242 | 2007-06-04 00:32:22 +0000 | [diff] [blame] | 310 | void LICM::SinkRegion(DomTreeNode *N) { |
Owen Anderson | 3a2b58f | 2007-04-24 06:40:39 +0000 | [diff] [blame] | 311 | assert(N != 0 && "Null dominator tree node?"); |
| 312 | BasicBlock *BB = N->getBlock(); |
Chris Lattner | e4365b2 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 313 | |
| 314 | // If this subregion is not in the top level loop at all, exit. |
| 315 | if (!CurLoop->contains(BB)) return; |
| 316 | |
| 317 | // We are processing blocks in reverse dfo, so process children first... |
Devang Patel | 2604242 | 2007-06-04 00:32:22 +0000 | [diff] [blame] | 318 | const std::vector<DomTreeNode*> &Children = N->getChildren(); |
Chris Lattner | e4365b2 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 319 | for (unsigned i = 0, e = Children.size(); i != e; ++i) |
| 320 | SinkRegion(Children[i]); |
| 321 | |
| 322 | // Only need to process the contents of this block if it is not part of a |
| 323 | // subloop (which would already have been processed). |
| 324 | if (inSubLoop(BB)) return; |
| 325 | |
Chris Lattner | a3df8a9 | 2003-12-19 08:18:16 +0000 | [diff] [blame] | 326 | for (BasicBlock::iterator II = BB->end(); II != BB->begin(); ) { |
| 327 | Instruction &I = *--II; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 328 | |
Chris Lattner | e4365b2 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 329 | // Check to see if we can sink this instruction to the exit blocks |
| 330 | // of the loop. We can do this if the all users of the instruction are |
| 331 | // outside of the loop. In this case, it doesn't even matter if the |
| 332 | // operands of the instruction are loop invariant. |
| 333 | // |
Chris Lattner | 70ac2dc | 2005-03-25 00:22:36 +0000 | [diff] [blame] | 334 | if (isNotUsedInLoop(I) && canSinkOrHoistInst(I)) { |
Chris Lattner | a3df8a9 | 2003-12-19 08:18:16 +0000 | [diff] [blame] | 335 | ++II; |
Chris Lattner | e4365b2 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 336 | sink(I); |
Chris Lattner | a3df8a9 | 2003-12-19 08:18:16 +0000 | [diff] [blame] | 337 | } |
Chris Lattner | e4365b2 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 338 | } |
| 339 | } |
| 340 | |
| 341 | |
Chris Lattner | 952eaee | 2002-09-29 21:46:09 +0000 | [diff] [blame] | 342 | /// HoistRegion - Walk the specified region of the CFG (defined by all blocks |
| 343 | /// dominated by the specified block, and that are in the current loop) in depth |
Owen Anderson | 3a2b58f | 2007-04-24 06:40:39 +0000 | [diff] [blame] | 344 | /// first order w.r.t the DominatorTree. This allows us to visit definitions |
Chris Lattner | 952eaee | 2002-09-29 21:46:09 +0000 | [diff] [blame] | 345 | /// before uses, allowing us to hoist a loop body in one pass without iteration. |
| 346 | /// |
Devang Patel | 2604242 | 2007-06-04 00:32:22 +0000 | [diff] [blame] | 347 | void LICM::HoistRegion(DomTreeNode *N) { |
Owen Anderson | 3a2b58f | 2007-04-24 06:40:39 +0000 | [diff] [blame] | 348 | assert(N != 0 && "Null dominator tree node?"); |
| 349 | BasicBlock *BB = N->getBlock(); |
Chris Lattner | 952eaee | 2002-09-29 21:46:09 +0000 | [diff] [blame] | 350 | |
Chris Lattner | b461373 | 2002-09-29 22:26:07 +0000 | [diff] [blame] | 351 | // If this subregion is not in the top level loop at all, exit. |
Chris Lattner | ed6dfc2 | 2003-12-09 19:32:44 +0000 | [diff] [blame] | 352 | if (!CurLoop->contains(BB)) return; |
Chris Lattner | 952eaee | 2002-09-29 21:46:09 +0000 | [diff] [blame] | 353 | |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 354 | // Only need to process the contents of this block if it is not part of a |
| 355 | // subloop (which would already have been processed). |
Chris Lattner | ed6dfc2 | 2003-12-09 19:32:44 +0000 | [diff] [blame] | 356 | if (!inSubLoop(BB)) |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 357 | for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) { |
| 358 | Instruction &I = *II++; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 359 | |
Chris Lattner | e4365b2 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 360 | // Try hoisting the instruction out to the preheader. We can only do this |
| 361 | // if all of the operands of the instruction are loop invariant and if it |
| 362 | // is safe to hoist the instruction. |
| 363 | // |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 364 | if (isLoopInvariantInst(I) && canSinkOrHoistInst(I) && |
Chris Lattner | e4365b2 | 2003-12-19 07:22:45 +0000 | [diff] [blame] | 365 | isSafeToExecuteUnconditionally(I)) |
Chris Lattner | 3c80a51 | 2006-06-26 19:10:05 +0000 | [diff] [blame] | 366 | hoist(I); |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 367 | } |
Chris Lattner | 952eaee | 2002-09-29 21:46:09 +0000 | [diff] [blame] | 368 | |
Devang Patel | 2604242 | 2007-06-04 00:32:22 +0000 | [diff] [blame] | 369 | const std::vector<DomTreeNode*> &Children = N->getChildren(); |
Chris Lattner | 952eaee | 2002-09-29 21:46:09 +0000 | [diff] [blame] | 370 | for (unsigned i = 0, e = Children.size(); i != e; ++i) |
Chris Lattner | 56b7ee2 | 2004-06-19 20:23:35 +0000 | [diff] [blame] | 371 | HoistRegion(Children[i]); |
Chris Lattner | 952eaee | 2002-09-29 21:46:09 +0000 | [diff] [blame] | 372 | } |
| 373 | |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 374 | /// canSinkOrHoistInst - Return true if the hoister and sinker can handle this |
| 375 | /// instruction. |
| 376 | /// |
| 377 | bool LICM::canSinkOrHoistInst(Instruction &I) { |
Chris Lattner | ed6dfc2 | 2003-12-09 19:32:44 +0000 | [diff] [blame] | 378 | // Loads have extra constraints we have to verify before we can hoist them. |
| 379 | if (LoadInst *LI = dyn_cast<LoadInst>(&I)) { |
| 380 | if (LI->isVolatile()) |
| 381 | return false; // Don't hoist volatile loads! |
| 382 | |
Chris Lattner | 967948b | 2008-07-23 05:06:28 +0000 | [diff] [blame] | 383 | // Loads from constant memory are always safe to move, even if they end up |
| 384 | // in the same alias set as something that ends up being modified. |
Dan Gohman | 3eee654 | 2008-07-24 23:57:25 +0000 | [diff] [blame] | 385 | if (EnableLICMConstantMotion && |
| 386 | AA->pointsToConstantMemory(LI->getOperand(0))) |
Chris Lattner | 967948b | 2008-07-23 05:06:28 +0000 | [diff] [blame] | 387 | return true; |
| 388 | |
Chris Lattner | ed6dfc2 | 2003-12-09 19:32:44 +0000 | [diff] [blame] | 389 | // Don't hoist loads which have may-aliased stores in loop. |
Chris Lattner | f3e1d69 | 2004-11-26 21:20:09 +0000 | [diff] [blame] | 390 | unsigned Size = 0; |
| 391 | if (LI->getType()->isSized()) |
Duncan Sands | 514ab34 | 2007-11-01 20:53:16 +0000 | [diff] [blame] | 392 | Size = AA->getTargetData().getTypeStoreSize(LI->getType()); |
Chris Lattner | f3e1d69 | 2004-11-26 21:20:09 +0000 | [diff] [blame] | 393 | return !pointerInvalidatedByLoop(LI->getOperand(0), Size); |
Chris Lattner | 118dd0c | 2004-03-15 04:11:30 +0000 | [diff] [blame] | 394 | } else if (CallInst *CI = dyn_cast<CallInst>(&I)) { |
| 395 | // Handle obvious cases efficiently. |
Duncan Sands | dff6710 | 2007-12-01 07:51:45 +0000 | [diff] [blame] | 396 | AliasAnalysis::ModRefBehavior Behavior = AA->getModRefBehavior(CI); |
| 397 | if (Behavior == AliasAnalysis::DoesNotAccessMemory) |
| 398 | return true; |
| 399 | else if (Behavior == AliasAnalysis::OnlyReadsMemory) { |
| 400 | // If this call only reads from memory and there are no writes to memory |
| 401 | // in the loop, we can hoist or sink the call as appropriate. |
| 402 | bool FoundMod = false; |
| 403 | for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); |
| 404 | I != E; ++I) { |
| 405 | AliasSet &AS = *I; |
| 406 | if (!AS.isForwardingAliasSet() && AS.isMod()) { |
| 407 | FoundMod = true; |
| 408 | break; |
Chris Lattner | 118dd0c | 2004-03-15 04:11:30 +0000 | [diff] [blame] | 409 | } |
Chris Lattner | 118dd0c | 2004-03-15 04:11:30 +0000 | [diff] [blame] | 410 | } |
Duncan Sands | dff6710 | 2007-12-01 07:51:45 +0000 | [diff] [blame] | 411 | if (!FoundMod) return true; |
Chris Lattner | 118dd0c | 2004-03-15 04:11:30 +0000 | [diff] [blame] | 412 | } |
| 413 | |
| 414 | // FIXME: This should use mod/ref information to see if we can hoist or sink |
| 415 | // the call. |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 416 | |
Chris Lattner | 118dd0c | 2004-03-15 04:11:30 +0000 | [diff] [blame] | 417 | return false; |
Chris Lattner | ed6dfc2 | 2003-12-09 19:32:44 +0000 | [diff] [blame] | 418 | } |
| 419 | |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame] | 420 | // Otherwise these instructions are hoistable/sinkable |
Reid Spencer | 832254e | 2007-02-02 02:16:23 +0000 | [diff] [blame] | 421 | return isa<BinaryOperator>(I) || isa<CastInst>(I) || |
Dan Gohman | d8af90c | 2007-06-05 16:05:55 +0000 | [diff] [blame] | 422 | isa<SelectInst>(I) || isa<GetElementPtrInst>(I) || isa<CmpInst>(I) || |
| 423 | isa<InsertElementInst>(I) || isa<ExtractElementInst>(I) || |
| 424 | isa<ShuffleVectorInst>(I); |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 425 | } |
| 426 | |
| 427 | /// isNotUsedInLoop - Return true if the only users of this instruction are |
| 428 | /// outside of the loop. If this is true, we can sink the instruction to the |
| 429 | /// exit blocks of the loop. |
| 430 | /// |
| 431 | bool LICM::isNotUsedInLoop(Instruction &I) { |
Chris Lattner | ea9403f | 2003-12-11 22:23:32 +0000 | [diff] [blame] | 432 | for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); UI != E; ++UI) { |
| 433 | Instruction *User = cast<Instruction>(*UI); |
| 434 | if (PHINode *PN = dyn_cast<PHINode>(User)) { |
| 435 | // PHI node uses occur in predecessor blocks! |
| 436 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) |
| 437 | if (PN->getIncomingValue(i) == &I) |
| 438 | if (CurLoop->contains(PN->getIncomingBlock(i))) |
| 439 | return false; |
| 440 | } else if (CurLoop->contains(User->getParent())) { |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 441 | return false; |
Chris Lattner | ea9403f | 2003-12-11 22:23:32 +0000 | [diff] [blame] | 442 | } |
| 443 | } |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 444 | return true; |
| 445 | } |
| 446 | |
| 447 | |
| 448 | /// isLoopInvariantInst - Return true if all operands of this instruction are |
| 449 | /// loop invariant. We also filter out non-hoistable instructions here just for |
| 450 | /// efficiency. |
| 451 | /// |
| 452 | bool LICM::isLoopInvariantInst(Instruction &I) { |
| 453 | // The instruction is loop invariant if all of its operands are loop-invariant |
| 454 | for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) |
Chris Lattner | 3280f7b | 2004-04-18 22:46:08 +0000 | [diff] [blame] | 455 | if (!CurLoop->isLoopInvariant(I.getOperand(i))) |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 456 | return false; |
| 457 | |
Chris Lattner | ed6dfc2 | 2003-12-09 19:32:44 +0000 | [diff] [blame] | 458 | // If we got this far, the instruction is loop invariant! |
| 459 | return true; |
| 460 | } |
| 461 | |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 462 | /// sink - When an instruction is found to only be used outside of the loop, |
Chris Lattner | a3df8a9 | 2003-12-19 08:18:16 +0000 | [diff] [blame] | 463 | /// this function moves it to the exit blocks and patches up SSA form as needed. |
| 464 | /// This method is guaranteed to remove the original instruction from its |
| 465 | /// position, and may either delete it or move it to outside of the loop. |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 466 | /// |
| 467 | void LICM::sink(Instruction &I) { |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 468 | DOUT << "LICM sinking instruction: " << I; |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 469 | |
Devang Patel | b7211a2 | 2007-08-21 00:31:24 +0000 | [diff] [blame] | 470 | SmallVector<BasicBlock*, 8> ExitBlocks; |
Chris Lattner | 5fa802f | 2004-04-18 22:15:13 +0000 | [diff] [blame] | 471 | CurLoop->getExitBlocks(ExitBlocks); |
Chris Lattner | df45bd3 | 2003-12-10 20:43:29 +0000 | [diff] [blame] | 472 | |
| 473 | if (isa<LoadInst>(I)) ++NumMovedLoads; |
Chris Lattner | 118dd0c | 2004-03-15 04:11:30 +0000 | [diff] [blame] | 474 | else if (isa<CallInst>(I)) ++NumMovedCalls; |
Chris Lattner | df45bd3 | 2003-12-10 20:43:29 +0000 | [diff] [blame] | 475 | ++NumSunk; |
| 476 | Changed = true; |
| 477 | |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 478 | // The case where there is only a single exit node of this loop is common |
| 479 | // enough that we handle it as a special (more efficient) case. It is more |
| 480 | // efficient to handle because there are no PHI nodes that need to be placed. |
| 481 | if (ExitBlocks.size() == 1) { |
| 482 | if (!isExitBlockDominatedByBlockInLoop(ExitBlocks[0], I.getParent())) { |
| 483 | // Instruction is not used, just delete it. |
Chris Lattner | 2741c97 | 2004-05-23 21:20:19 +0000 | [diff] [blame] | 484 | CurAST->deleteValue(&I); |
Chris Lattner | 92f7365 | 2006-09-12 19:17:09 +0000 | [diff] [blame] | 485 | if (!I.use_empty()) // If I has users in unreachable blocks, eliminate. |
Owen Anderson | 1ff50b3 | 2009-07-03 00:54:20 +0000 | [diff] [blame] | 486 | I.replaceAllUsesWith(Context->getUndef(I.getType())); |
Chris Lattner | 3c80a51 | 2006-06-26 19:10:05 +0000 | [diff] [blame] | 487 | I.eraseFromParent(); |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 488 | } else { |
| 489 | // Move the instruction to the start of the exit block, after any PHI |
| 490 | // nodes in it. |
Chris Lattner | 3c80a51 | 2006-06-26 19:10:05 +0000 | [diff] [blame] | 491 | I.removeFromParent(); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 492 | |
Dan Gohman | 02dea8b | 2008-05-23 21:05:58 +0000 | [diff] [blame] | 493 | BasicBlock::iterator InsertPt = ExitBlocks[0]->getFirstNonPHI(); |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 494 | ExitBlocks[0]->getInstList().insert(InsertPt, &I); |
| 495 | } |
Dan Gohman | 3035959 | 2008-01-29 13:02:09 +0000 | [diff] [blame] | 496 | } else if (ExitBlocks.empty()) { |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 497 | // The instruction is actually dead if there ARE NO exit blocks. |
Chris Lattner | 2741c97 | 2004-05-23 21:20:19 +0000 | [diff] [blame] | 498 | CurAST->deleteValue(&I); |
Chris Lattner | 92f7365 | 2006-09-12 19:17:09 +0000 | [diff] [blame] | 499 | if (!I.use_empty()) // If I has users in unreachable blocks, eliminate. |
Owen Anderson | 1ff50b3 | 2009-07-03 00:54:20 +0000 | [diff] [blame] | 500 | I.replaceAllUsesWith(Context->getUndef(I.getType())); |
Chris Lattner | 3c80a51 | 2006-06-26 19:10:05 +0000 | [diff] [blame] | 501 | I.eraseFromParent(); |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 502 | } else { |
| 503 | // Otherwise, if we have multiple exits, use the PromoteMem2Reg function to |
| 504 | // do all of the hard work of inserting PHI nodes as necessary. We convert |
| 505 | // the value into a stack object to get it to do this. |
| 506 | |
| 507 | // Firstly, we create a stack object to hold the value... |
Chris Lattner | eaa2430 | 2004-07-27 07:38:32 +0000 | [diff] [blame] | 508 | AllocaInst *AI = 0; |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 509 | |
Devang Patel | e7ae1a9 | 2007-06-01 22:15:31 +0000 | [diff] [blame] | 510 | if (I.getType() != Type::VoidTy) { |
Owen Anderson | 50dead0 | 2009-07-15 23:53:25 +0000 | [diff] [blame] | 511 | AI = new AllocaInst(I.getType(), 0, I.getName(), |
Dan Gohman | ecb7a77 | 2007-03-22 16:38:57 +0000 | [diff] [blame] | 512 | I.getParent()->getParent()->getEntryBlock().begin()); |
Devang Patel | e7ae1a9 | 2007-06-01 22:15:31 +0000 | [diff] [blame] | 513 | CurAST->add(AI); |
| 514 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 515 | |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 516 | // Secondly, insert load instructions for each use of the instruction |
| 517 | // outside of the loop. |
| 518 | while (!I.use_empty()) { |
| 519 | Instruction *U = cast<Instruction>(I.use_back()); |
| 520 | |
| 521 | // If the user is a PHI Node, we actually have to insert load instructions |
| 522 | // in all predecessor blocks, not in the PHI block itself! |
| 523 | if (PHINode *UPN = dyn_cast<PHINode>(U)) { |
| 524 | // Only insert into each predecessor once, so that we don't have |
| 525 | // different incoming values from the same block! |
| 526 | std::map<BasicBlock*, Value*> InsertedBlocks; |
| 527 | for (unsigned i = 0, e = UPN->getNumIncomingValues(); i != e; ++i) |
| 528 | if (UPN->getIncomingValue(i) == &I) { |
| 529 | BasicBlock *Pred = UPN->getIncomingBlock(i); |
| 530 | Value *&PredVal = InsertedBlocks[Pred]; |
| 531 | if (!PredVal) { |
| 532 | // Insert a new load instruction right before the terminator in |
| 533 | // the predecessor block. |
| 534 | PredVal = new LoadInst(AI, "", Pred->getTerminator()); |
Devang Patel | e7ae1a9 | 2007-06-01 22:15:31 +0000 | [diff] [blame] | 535 | CurAST->add(cast<LoadInst>(PredVal)); |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 536 | } |
| 537 | |
| 538 | UPN->setIncomingValue(i, PredVal); |
| 539 | } |
| 540 | |
| 541 | } else { |
| 542 | LoadInst *L = new LoadInst(AI, "", U); |
| 543 | U->replaceUsesOfWith(&I, L); |
Devang Patel | e7ae1a9 | 2007-06-01 22:15:31 +0000 | [diff] [blame] | 544 | CurAST->add(L); |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 545 | } |
| 546 | } |
| 547 | |
| 548 | // Thirdly, insert a copy of the instruction in each exit block of the loop |
| 549 | // that is dominated by the instruction, storing the result into the memory |
| 550 | // location. Be careful not to insert the instruction into any particular |
| 551 | // basic block more than once. |
| 552 | std::set<BasicBlock*> InsertedBlocks; |
| 553 | BasicBlock *InstOrigBB = I.getParent(); |
| 554 | |
| 555 | for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { |
| 556 | BasicBlock *ExitBlock = ExitBlocks[i]; |
| 557 | |
| 558 | if (isExitBlockDominatedByBlockInLoop(ExitBlock, InstOrigBB)) { |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 559 | // If we haven't already processed this exit block, do so now. |
Chris Lattner | e3cfe8d | 2003-12-10 16:58:24 +0000 | [diff] [blame] | 560 | if (InsertedBlocks.insert(ExitBlock).second) { |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 561 | // Insert the code after the last PHI node... |
Dan Gohman | 02dea8b | 2008-05-23 21:05:58 +0000 | [diff] [blame] | 562 | BasicBlock::iterator InsertPt = ExitBlock->getFirstNonPHI(); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 563 | |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 564 | // If this is the first exit block processed, just move the original |
| 565 | // instruction, otherwise clone the original instruction and insert |
| 566 | // the copy. |
| 567 | Instruction *New; |
Chris Lattner | 7d3ced9 | 2003-12-10 22:35:56 +0000 | [diff] [blame] | 568 | if (InsertedBlocks.size() == 1) { |
Chris Lattner | 3c80a51 | 2006-06-26 19:10:05 +0000 | [diff] [blame] | 569 | I.removeFromParent(); |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 570 | ExitBlock->getInstList().insert(InsertPt, &I); |
| 571 | New = &I; |
| 572 | } else { |
Owen Anderson | 333c400 | 2009-07-09 23:48:35 +0000 | [diff] [blame] | 573 | New = I.clone(*Context); |
Chris Lattner | 70ac2dc | 2005-03-25 00:22:36 +0000 | [diff] [blame] | 574 | CurAST->copyValue(&I, New); |
Chris Lattner | eaa2430 | 2004-07-27 07:38:32 +0000 | [diff] [blame] | 575 | if (!I.getName().empty()) |
| 576 | New->setName(I.getName()+".le"); |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 577 | ExitBlock->getInstList().insert(InsertPt, New); |
| 578 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 579 | |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 580 | // Now that we have inserted the instruction, store it into the alloca |
Chris Lattner | eaa2430 | 2004-07-27 07:38:32 +0000 | [diff] [blame] | 581 | if (AI) new StoreInst(New, AI, InsertPt); |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 582 | } |
| 583 | } |
| 584 | } |
Chris Lattner | a3df8a9 | 2003-12-19 08:18:16 +0000 | [diff] [blame] | 585 | |
| 586 | // If the instruction doesn't dominate any exit blocks, it must be dead. |
| 587 | if (InsertedBlocks.empty()) { |
Chris Lattner | 2741c97 | 2004-05-23 21:20:19 +0000 | [diff] [blame] | 588 | CurAST->deleteValue(&I); |
Chris Lattner | 3c80a51 | 2006-06-26 19:10:05 +0000 | [diff] [blame] | 589 | I.eraseFromParent(); |
Chris Lattner | a3df8a9 | 2003-12-19 08:18:16 +0000 | [diff] [blame] | 590 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 591 | |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 592 | // Finally, promote the fine value to SSA form. |
Chris Lattner | eaa2430 | 2004-07-27 07:38:32 +0000 | [diff] [blame] | 593 | if (AI) { |
| 594 | std::vector<AllocaInst*> Allocas; |
| 595 | Allocas.push_back(AI); |
Owen Anderson | 0a205a4 | 2009-07-05 22:41:43 +0000 | [diff] [blame] | 596 | PromoteMemToReg(Allocas, *DT, *DF, Context, CurAST); |
Chris Lattner | eaa2430 | 2004-07-27 07:38:32 +0000 | [diff] [blame] | 597 | } |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 598 | } |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 599 | } |
Chris Lattner | 952eaee | 2002-09-29 21:46:09 +0000 | [diff] [blame] | 600 | |
Chris Lattner | 9417059 | 2002-09-26 16:52:07 +0000 | [diff] [blame] | 601 | /// hoist - When an instruction is found to only use loop invariant operands |
| 602 | /// that is safe to hoist, this instruction is called to do the dirty work. |
| 603 | /// |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 604 | void LICM::hoist(Instruction &I) { |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 605 | DOUT << "LICM hoisting to " << Preheader->getName() << ": " << I; |
Chris Lattner | ed6dfc2 | 2003-12-09 19:32:44 +0000 | [diff] [blame] | 606 | |
Chris Lattner | 99a5721 | 2002-09-26 19:40:25 +0000 | [diff] [blame] | 607 | // Remove the instruction from its current basic block... but don't delete the |
| 608 | // instruction. |
Chris Lattner | 3c80a51 | 2006-06-26 19:10:05 +0000 | [diff] [blame] | 609 | I.removeFromParent(); |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 610 | |
Chris Lattner | 9646e6b | 2002-09-26 16:38:03 +0000 | [diff] [blame] | 611 | // Insert the new node in Preheader, before the terminator. |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 612 | Preheader->getInstList().insert(Preheader->getTerminator(), &I); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 613 | |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 614 | if (isa<LoadInst>(I)) ++NumMovedLoads; |
Chris Lattner | 118dd0c | 2004-03-15 04:11:30 +0000 | [diff] [blame] | 615 | else if (isa<CallInst>(I)) ++NumMovedCalls; |
Chris Lattner | 9646e6b | 2002-09-26 16:38:03 +0000 | [diff] [blame] | 616 | ++NumHoisted; |
Chris Lattner | e0e734e | 2002-05-10 22:44:58 +0000 | [diff] [blame] | 617 | Changed = true; |
| 618 | } |
| 619 | |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 620 | /// isSafeToExecuteUnconditionally - Only sink or hoist an instruction if it is |
| 621 | /// not a trapping instruction or if it is a trapping instruction and is |
| 622 | /// guaranteed to execute. |
Tanya Lattner | 9966c03 | 2003-08-05 18:45:46 +0000 | [diff] [blame] | 623 | /// |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 624 | bool LICM::isSafeToExecuteUnconditionally(Instruction &Inst) { |
Chris Lattner | 92094b4 | 2003-12-09 17:18:00 +0000 | [diff] [blame] | 625 | // If it is not a trapping instruction, it is always safe to hoist. |
Eli Friedman | 0b79a77 | 2009-07-17 04:28:42 +0000 | [diff] [blame^] | 626 | if (Inst.isSafeToSpeculativelyExecute()) |
| 627 | return true; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 628 | |
Chris Lattner | 92094b4 | 2003-12-09 17:18:00 +0000 | [diff] [blame] | 629 | // Otherwise we have to check to make sure that the instruction dominates all |
| 630 | // of the exit blocks. If it doesn't, then there is a path out of the loop |
| 631 | // which does not execute this instruction, so we can't hoist it. |
Tanya Lattner | 9966c03 | 2003-08-05 18:45:46 +0000 | [diff] [blame] | 632 | |
Chris Lattner | 92094b4 | 2003-12-09 17:18:00 +0000 | [diff] [blame] | 633 | // If the instruction is in the header block for the loop (which is very |
| 634 | // common), it is always guaranteed to dominate the exit blocks. Since this |
| 635 | // is a common case, and can save some work, check it now. |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 636 | if (Inst.getParent() == CurLoop->getHeader()) |
Chris Lattner | 92094b4 | 2003-12-09 17:18:00 +0000 | [diff] [blame] | 637 | return true; |
Tanya Lattner | 9966c03 | 2003-08-05 18:45:46 +0000 | [diff] [blame] | 638 | |
Chris Lattner | 92094b4 | 2003-12-09 17:18:00 +0000 | [diff] [blame] | 639 | // Get the exit blocks for the current loop. |
Devang Patel | b7211a2 | 2007-08-21 00:31:24 +0000 | [diff] [blame] | 640 | SmallVector<BasicBlock*, 8> ExitBlocks; |
Chris Lattner | 5fa802f | 2004-04-18 22:15:13 +0000 | [diff] [blame] | 641 | CurLoop->getExitBlocks(ExitBlocks); |
Chris Lattner | 92094b4 | 2003-12-09 17:18:00 +0000 | [diff] [blame] | 642 | |
Owen Anderson | 3a2b58f | 2007-04-24 06:40:39 +0000 | [diff] [blame] | 643 | // For each exit block, get the DT node and walk up the DT until the |
Chris Lattner | 92094b4 | 2003-12-09 17:18:00 +0000 | [diff] [blame] | 644 | // instruction's basic block is found or we exit the loop. |
Chris Lattner | a270651 | 2003-12-10 06:41:05 +0000 | [diff] [blame] | 645 | for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) |
| 646 | if (!isExitBlockDominatedByBlockInLoop(ExitBlocks[i], Inst.getParent())) |
| 647 | return false; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 648 | |
Tanya Lattner | 9966c03 | 2003-08-05 18:45:46 +0000 | [diff] [blame] | 649 | return true; |
| 650 | } |
| 651 | |
Chris Lattner | eb53ae4 | 2002-09-26 16:19:31 +0000 | [diff] [blame] | 652 | |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 653 | /// PromoteValuesInLoop - Try to promote memory values to scalars by sinking |
| 654 | /// stores out of the loop and moving loads to before the loop. We do this by |
| 655 | /// looping over the stores in the loop, looking for stores to Must pointers |
| 656 | /// which are loop invariant. We promote these memory locations to use allocas |
| 657 | /// instead. These allocas can easily be raised to register values by the |
| 658 | /// PromoteMem2Reg functionality. |
| 659 | /// |
| 660 | void LICM::PromoteValuesInLoop() { |
| 661 | // PromotedValues - List of values that are promoted out of the loop. Each |
Chris Lattner | 065a616 | 2003-09-10 05:29:43 +0000 | [diff] [blame] | 662 | // value has an alloca instruction for it, and a canonical version of the |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 663 | // pointer. |
| 664 | std::vector<std::pair<AllocaInst*, Value*> > PromotedValues; |
| 665 | std::map<Value*, AllocaInst*> ValueToAllocaMap; // Map of ptr to alloca |
| 666 | |
Chris Lattner | fb3ee19 | 2004-09-15 01:04:07 +0000 | [diff] [blame] | 667 | FindPromotableValuesInLoop(PromotedValues, ValueToAllocaMap); |
| 668 | if (ValueToAllocaMap.empty()) return; // If there are values to promote. |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 669 | |
| 670 | Changed = true; |
| 671 | NumPromoted += PromotedValues.size(); |
| 672 | |
Chris Lattner | fb3ee19 | 2004-09-15 01:04:07 +0000 | [diff] [blame] | 673 | std::vector<Value*> PointerValueNumbers; |
| 674 | |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 675 | // Emit a copy from the value into the alloca'd value in the loop preheader |
| 676 | TerminatorInst *LoopPredInst = Preheader->getTerminator(); |
| 677 | for (unsigned i = 0, e = PromotedValues.size(); i != e; ++i) { |
Chris Lattner | fb3ee19 | 2004-09-15 01:04:07 +0000 | [diff] [blame] | 678 | Value *Ptr = PromotedValues[i].second; |
| 679 | |
| 680 | // If we are promoting a pointer value, update alias information for the |
| 681 | // inserted load. |
| 682 | Value *LoadValue = 0; |
| 683 | if (isa<PointerType>(cast<PointerType>(Ptr->getType())->getElementType())) { |
| 684 | // Locate a load or store through the pointer, and assign the same value |
| 685 | // to LI as we are loading or storing. Since we know that the value is |
| 686 | // stored in this loop, this will always succeed. |
| 687 | for (Value::use_iterator UI = Ptr->use_begin(), E = Ptr->use_end(); |
| 688 | UI != E; ++UI) |
| 689 | if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { |
| 690 | LoadValue = LI; |
| 691 | break; |
| 692 | } else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) { |
Chris Lattner | bdacd87 | 2004-09-15 02:34:40 +0000 | [diff] [blame] | 693 | if (SI->getOperand(1) == Ptr) { |
Chris Lattner | fb3ee19 | 2004-09-15 01:04:07 +0000 | [diff] [blame] | 694 | LoadValue = SI->getOperand(0); |
| 695 | break; |
| 696 | } |
| 697 | } |
| 698 | assert(LoadValue && "No store through the pointer found!"); |
| 699 | PointerValueNumbers.push_back(LoadValue); // Remember this for later. |
| 700 | } |
| 701 | |
| 702 | // Load from the memory we are promoting. |
| 703 | LoadInst *LI = new LoadInst(Ptr, Ptr->getName()+".promoted", LoopPredInst); |
| 704 | |
| 705 | if (LoadValue) CurAST->copyValue(LoadValue, LI); |
| 706 | |
| 707 | // Store into the temporary alloca. |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 708 | new StoreInst(LI, PromotedValues[i].first, LoopPredInst); |
| 709 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 710 | |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 711 | // Scan the basic blocks in the loop, replacing uses of our pointers with |
Chris Lattner | 0ed2da9 | 2003-12-10 15:56:24 +0000 | [diff] [blame] | 712 | // uses of the allocas in question. |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 713 | // |
Dan Gohman | 9b78763 | 2008-06-22 20:18:58 +0000 | [diff] [blame] | 714 | for (Loop::block_iterator I = CurLoop->block_begin(), |
| 715 | E = CurLoop->block_end(); I != E; ++I) { |
| 716 | BasicBlock *BB = *I; |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 717 | // Rewrite all loads and stores in the block of the pointer... |
Dan Gohman | 9b78763 | 2008-06-22 20:18:58 +0000 | [diff] [blame] | 718 | for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ++II) { |
Chris Lattner | e408e25 | 2003-04-23 16:37:45 +0000 | [diff] [blame] | 719 | if (LoadInst *L = dyn_cast<LoadInst>(II)) { |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 720 | std::map<Value*, AllocaInst*>::iterator |
| 721 | I = ValueToAllocaMap.find(L->getOperand(0)); |
| 722 | if (I != ValueToAllocaMap.end()) |
| 723 | L->setOperand(0, I->second); // Rewrite load instruction... |
Chris Lattner | e408e25 | 2003-04-23 16:37:45 +0000 | [diff] [blame] | 724 | } else if (StoreInst *S = dyn_cast<StoreInst>(II)) { |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 725 | std::map<Value*, AllocaInst*>::iterator |
| 726 | I = ValueToAllocaMap.find(S->getOperand(1)); |
| 727 | if (I != ValueToAllocaMap.end()) |
| 728 | S->setOperand(1, I->second); // Rewrite store instruction... |
| 729 | } |
| 730 | } |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 731 | } |
| 732 | |
Chris Lattner | 0ed2da9 | 2003-12-10 15:56:24 +0000 | [diff] [blame] | 733 | // Now that the body of the loop uses the allocas instead of the original |
| 734 | // memory locations, insert code to copy the alloca value back into the |
| 735 | // original memory location on all exits from the loop. Note that we only |
| 736 | // want to insert one copy of the code in each exit block, though the loop may |
| 737 | // exit to the same block more than once. |
| 738 | // |
Chris Lattner | 19d9d43 | 2008-05-22 03:22:42 +0000 | [diff] [blame] | 739 | SmallPtrSet<BasicBlock*, 16> ProcessedBlocks; |
Chris Lattner | 0ed2da9 | 2003-12-10 15:56:24 +0000 | [diff] [blame] | 740 | |
Devang Patel | b7211a2 | 2007-08-21 00:31:24 +0000 | [diff] [blame] | 741 | SmallVector<BasicBlock*, 8> ExitBlocks; |
Chris Lattner | 5fa802f | 2004-04-18 22:15:13 +0000 | [diff] [blame] | 742 | CurLoop->getExitBlocks(ExitBlocks); |
Chris Lattner | 19d9d43 | 2008-05-22 03:22:42 +0000 | [diff] [blame] | 743 | for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { |
| 744 | if (!ProcessedBlocks.insert(ExitBlocks[i])) |
| 745 | continue; |
| 746 | |
| 747 | // Copy all of the allocas into their memory locations. |
Dan Gohman | 02dea8b | 2008-05-23 21:05:58 +0000 | [diff] [blame] | 748 | BasicBlock::iterator BI = ExitBlocks[i]->getFirstNonPHI(); |
Chris Lattner | 19d9d43 | 2008-05-22 03:22:42 +0000 | [diff] [blame] | 749 | Instruction *InsertPos = BI; |
| 750 | unsigned PVN = 0; |
| 751 | for (unsigned i = 0, e = PromotedValues.size(); i != e; ++i) { |
| 752 | // Load from the alloca. |
| 753 | LoadInst *LI = new LoadInst(PromotedValues[i].first, "", InsertPos); |
Chris Lattner | fb3ee19 | 2004-09-15 01:04:07 +0000 | [diff] [blame] | 754 | |
Chris Lattner | 19d9d43 | 2008-05-22 03:22:42 +0000 | [diff] [blame] | 755 | // If this is a pointer type, update alias info appropriately. |
| 756 | if (isa<PointerType>(LI->getType())) |
| 757 | CurAST->copyValue(PointerValueNumbers[PVN++], LI); |
Chris Lattner | fb3ee19 | 2004-09-15 01:04:07 +0000 | [diff] [blame] | 758 | |
Chris Lattner | 19d9d43 | 2008-05-22 03:22:42 +0000 | [diff] [blame] | 759 | // Store into the memory we promoted. |
| 760 | new StoreInst(LI, PromotedValues[i].second, InsertPos); |
Chris Lattner | 0ed2da9 | 2003-12-10 15:56:24 +0000 | [diff] [blame] | 761 | } |
Chris Lattner | 19d9d43 | 2008-05-22 03:22:42 +0000 | [diff] [blame] | 762 | } |
Chris Lattner | 0ed2da9 | 2003-12-10 15:56:24 +0000 | [diff] [blame] | 763 | |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 764 | // Now that we have done the deed, use the mem2reg functionality to promote |
Chris Lattner | fb3ee19 | 2004-09-15 01:04:07 +0000 | [diff] [blame] | 765 | // all of the new allocas we just created into real SSA registers. |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 766 | // |
| 767 | std::vector<AllocaInst*> PromotedAllocas; |
| 768 | PromotedAllocas.reserve(PromotedValues.size()); |
| 769 | for (unsigned i = 0, e = PromotedValues.size(); i != e; ++i) |
| 770 | PromotedAllocas.push_back(PromotedValues[i].first); |
Owen Anderson | 0a205a4 | 2009-07-05 22:41:43 +0000 | [diff] [blame] | 771 | PromoteMemToReg(PromotedAllocas, *DT, *DF, Context, CurAST); |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 772 | } |
| 773 | |
Chris Lattner | fb3ee19 | 2004-09-15 01:04:07 +0000 | [diff] [blame] | 774 | /// FindPromotableValuesInLoop - Check the current loop for stores to definite |
Devang Patel | f2038b1 | 2007-09-19 20:18:51 +0000 | [diff] [blame] | 775 | /// pointers, which are not loaded and stored through may aliases and are safe |
| 776 | /// for promotion. If these are found, create an alloca for the value, add it |
| 777 | /// to the PromotedValues list, and keep track of the mapping from value to |
| 778 | /// alloca. |
Chris Lattner | fb3ee19 | 2004-09-15 01:04:07 +0000 | [diff] [blame] | 779 | void LICM::FindPromotableValuesInLoop( |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 780 | std::vector<std::pair<AllocaInst*, Value*> > &PromotedValues, |
| 781 | std::map<Value*, AllocaInst*> &ValueToAllocaMap) { |
| 782 | Instruction *FnStart = CurLoop->getHeader()->getParent()->begin()->begin(); |
| 783 | |
Chris Lattner | fb3ee19 | 2004-09-15 01:04:07 +0000 | [diff] [blame] | 784 | // Loop over all of the alias sets in the tracker object. |
Chris Lattner | 0252e49 | 2003-03-03 23:32:45 +0000 | [diff] [blame] | 785 | for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); |
| 786 | I != E; ++I) { |
| 787 | AliasSet &AS = *I; |
| 788 | // We can promote this alias set if it has a store, if it is a "Must" alias |
Chris Lattner | fb3ee19 | 2004-09-15 01:04:07 +0000 | [diff] [blame] | 789 | // set, if the pointer is loop invariant, and if we are not eliminating any |
Chris Lattner | 118dd0c | 2004-03-15 04:11:30 +0000 | [diff] [blame] | 790 | // volatile loads or stores. |
Chris Lattner | 29d9293 | 2008-05-22 00:53:38 +0000 | [diff] [blame] | 791 | if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() || |
Chris Lattner | d7168dd | 2009-03-09 05:11:09 +0000 | [diff] [blame] | 792 | AS.isVolatile() || !CurLoop->isLoopInvariant(AS.begin()->getValue())) |
Chris Lattner | 29d9293 | 2008-05-22 00:53:38 +0000 | [diff] [blame] | 793 | continue; |
| 794 | |
| 795 | assert(!AS.empty() && |
| 796 | "Must alias set should have at least one pointer element in it!"); |
Chris Lattner | d7168dd | 2009-03-09 05:11:09 +0000 | [diff] [blame] | 797 | Value *V = AS.begin()->getValue(); |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 798 | |
Chris Lattner | 29d9293 | 2008-05-22 00:53:38 +0000 | [diff] [blame] | 799 | // Check that all of the pointers in the alias set have the same type. We |
| 800 | // cannot (yet) promote a memory location that is loaded and stored in |
| 801 | // different sizes. |
| 802 | { |
Chris Lattner | 0252e49 | 2003-03-03 23:32:45 +0000 | [diff] [blame] | 803 | bool PointerOk = true; |
| 804 | for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I) |
Chris Lattner | d7168dd | 2009-03-09 05:11:09 +0000 | [diff] [blame] | 805 | if (V->getType() != I->getValue()->getType()) { |
Chris Lattner | 0252e49 | 2003-03-03 23:32:45 +0000 | [diff] [blame] | 806 | PointerOk = false; |
| 807 | break; |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 808 | } |
Chris Lattner | 29d9293 | 2008-05-22 00:53:38 +0000 | [diff] [blame] | 809 | if (!PointerOk) |
| 810 | continue; |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 811 | } |
Chris Lattner | 29d9293 | 2008-05-22 00:53:38 +0000 | [diff] [blame] | 812 | |
Chris Lattner | 19d9d43 | 2008-05-22 03:22:42 +0000 | [diff] [blame] | 813 | // It isn't safe to promote a load/store from the loop if the load/store is |
| 814 | // conditional. For example, turning: |
| 815 | // |
| 816 | // for () { if (c) *P += 1; } |
| 817 | // |
| 818 | // into: |
| 819 | // |
| 820 | // tmp = *P; for () { if (c) tmp +=1; } *P = tmp; |
| 821 | // |
| 822 | // is not safe, because *P may only be valid to access if 'c' is true. |
| 823 | // |
| 824 | // It is safe to promote P if all uses are direct load/stores and if at |
| 825 | // least one is guaranteed to be executed. |
| 826 | bool GuaranteedToExecute = false; |
| 827 | bool InvalidInst = false; |
| 828 | for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); |
| 829 | UI != UE; ++UI) { |
| 830 | // Ignore instructions not in this loop. |
Chris Lattner | 29d9293 | 2008-05-22 00:53:38 +0000 | [diff] [blame] | 831 | Instruction *Use = dyn_cast<Instruction>(*UI); |
| 832 | if (!Use || !CurLoop->contains(Use->getParent())) |
| 833 | continue; |
Chris Lattner | 29d9293 | 2008-05-22 00:53:38 +0000 | [diff] [blame] | 834 | |
Chris Lattner | 19d9d43 | 2008-05-22 03:22:42 +0000 | [diff] [blame] | 835 | if (!isa<LoadInst>(Use) && !isa<StoreInst>(Use)) { |
| 836 | InvalidInst = true; |
Chris Lattner | 29d9293 | 2008-05-22 00:53:38 +0000 | [diff] [blame] | 837 | break; |
Chris Lattner | 19d9d43 | 2008-05-22 03:22:42 +0000 | [diff] [blame] | 838 | } |
| 839 | |
| 840 | if (!GuaranteedToExecute) |
| 841 | GuaranteedToExecute = isSafeToExecuteUnconditionally(*Use); |
Chris Lattner | 29d9293 | 2008-05-22 00:53:38 +0000 | [diff] [blame] | 842 | } |
| 843 | |
Chris Lattner | 19d9d43 | 2008-05-22 03:22:42 +0000 | [diff] [blame] | 844 | // If there is an non-load/store instruction in the loop, we can't promote |
| 845 | // it. If there isn't a guaranteed-to-execute instruction, we can't |
| 846 | // promote. |
| 847 | if (InvalidInst || !GuaranteedToExecute) |
Chris Lattner | 29d9293 | 2008-05-22 00:53:38 +0000 | [diff] [blame] | 848 | continue; |
| 849 | |
| 850 | const Type *Ty = cast<PointerType>(V->getType())->getElementType(); |
Owen Anderson | 50dead0 | 2009-07-15 23:53:25 +0000 | [diff] [blame] | 851 | AllocaInst *AI = new AllocaInst(Ty, 0, V->getName()+".tmp", FnStart); |
Chris Lattner | 29d9293 | 2008-05-22 00:53:38 +0000 | [diff] [blame] | 852 | PromotedValues.push_back(std::make_pair(AI, V)); |
| 853 | |
| 854 | // Update the AST and alias analysis. |
| 855 | CurAST->copyValue(V, AI); |
| 856 | |
| 857 | for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I) |
Chris Lattner | d7168dd | 2009-03-09 05:11:09 +0000 | [diff] [blame] | 858 | ValueToAllocaMap.insert(std::make_pair(I->getValue(), AI)); |
Chris Lattner | 29d9293 | 2008-05-22 00:53:38 +0000 | [diff] [blame] | 859 | |
| 860 | DOUT << "LICM: Promoting value: " << *V << "\n"; |
Chris Lattner | 2e6e741 | 2003-02-24 03:52:32 +0000 | [diff] [blame] | 861 | } |
Chris Lattner | f5e84aa | 2002-08-22 21:39:55 +0000 | [diff] [blame] | 862 | } |
Devang Patel | 91d22c8 | 2007-07-31 08:01:41 +0000 | [diff] [blame] | 863 | |
| 864 | /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info. |
| 865 | void LICM::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L) { |
| 866 | AliasSetTracker *AST = LoopToAliasMap[L]; |
| 867 | if (!AST) |
| 868 | return; |
| 869 | |
| 870 | AST->copyValue(From, To); |
| 871 | } |
| 872 | |
| 873 | /// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias |
| 874 | /// set. |
| 875 | void LICM::deleteAnalysisValue(Value *V, Loop *L) { |
| 876 | AliasSetTracker *AST = LoopToAliasMap[L]; |
| 877 | if (!AST) |
| 878 | return; |
| 879 | |
| 880 | AST->deleteValue(V); |
| 881 | } |