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