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