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