Owen Anderson | 2480737 | 2006-05-26 21:11:53 +0000 | [diff] [blame] | 1 | //===-- LCSSA.cpp - Convert loops into loop-closed SSA form ---------------===// |
Owen Anderson | 11f510b | 2006-05-26 13:58:26 +0000 | [diff] [blame] | 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame^] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Owen Anderson | 11f510b | 2006-05-26 13:58:26 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This pass transforms loops by placing phi nodes at the end of the loops for |
| 11 | // all values that are live across the loop boundary. For example, it turns |
| 12 | // the left into the right code: |
| 13 | // |
| 14 | // for (...) for (...) |
Dan Gohman | 23d9d27 | 2007-05-11 21:10:54 +0000 | [diff] [blame] | 15 | // if (c) if (c) |
Owen Anderson | 11f510b | 2006-05-26 13:58:26 +0000 | [diff] [blame] | 16 | // X1 = ... X1 = ... |
| 17 | // else else |
| 18 | // X2 = ... X2 = ... |
| 19 | // X3 = phi(X1, X2) X3 = phi(X1, X2) |
| 20 | // ... = X3 + 4 X4 = phi(X3) |
| 21 | // ... = X4 + 4 |
| 22 | // |
| 23 | // This is still valid LLVM; the extra phi nodes are purely redundant, and will |
| 24 | // be trivially eliminated by InstCombine. The major benefit of this |
| 25 | // transformation is that it makes many other loop optimizations, such as |
| 26 | // LoopUnswitching, simpler. |
| 27 | // |
| 28 | //===----------------------------------------------------------------------===// |
| 29 | |
Chris Lattner | d216e8b | 2006-12-19 22:17:40 +0000 | [diff] [blame] | 30 | #define DEBUG_TYPE "lcssa" |
Owen Anderson | 2480737 | 2006-05-26 21:11:53 +0000 | [diff] [blame] | 31 | #include "llvm/Transforms/Scalar.h" |
Owen Anderson | e4e1ecd | 2006-07-09 08:14:06 +0000 | [diff] [blame] | 32 | #include "llvm/Constants.h" |
Owen Anderson | 11f510b | 2006-05-26 13:58:26 +0000 | [diff] [blame] | 33 | #include "llvm/Pass.h" |
| 34 | #include "llvm/Function.h" |
| 35 | #include "llvm/Instructions.h" |
Owen Anderson | 9e1c1dd | 2006-06-04 00:02:23 +0000 | [diff] [blame] | 36 | #include "llvm/ADT/SetVector.h" |
Owen Anderson | a90b2c7 | 2006-05-27 00:31:37 +0000 | [diff] [blame] | 37 | #include "llvm/ADT/Statistic.h" |
Owen Anderson | 2480737 | 2006-05-26 21:11:53 +0000 | [diff] [blame] | 38 | #include "llvm/Analysis/Dominators.h" |
Devang Patel | b4559a2 | 2007-07-13 23:57:11 +0000 | [diff] [blame] | 39 | #include "llvm/Analysis/LoopPass.h" |
| 40 | #include "llvm/Analysis/ScalarEvolution.h" |
Owen Anderson | 11f510b | 2006-05-26 13:58:26 +0000 | [diff] [blame] | 41 | #include "llvm/Support/CFG.h" |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 42 | #include "llvm/Support/Compiler.h" |
Owen Anderson | 2480737 | 2006-05-26 21:11:53 +0000 | [diff] [blame] | 43 | #include <algorithm> |
Reid Spencer | 0974ea0 | 2007-02-05 05:23:32 +0000 | [diff] [blame] | 44 | #include <map> |
Owen Anderson | 11f510b | 2006-05-26 13:58:26 +0000 | [diff] [blame] | 45 | using namespace llvm; |
| 46 | |
Chris Lattner | d216e8b | 2006-12-19 22:17:40 +0000 | [diff] [blame] | 47 | STATISTIC(NumLCSSA, "Number of live out of a loop variables"); |
| 48 | |
Owen Anderson | 11f510b | 2006-05-26 13:58:26 +0000 | [diff] [blame] | 49 | namespace { |
Devang Patel | b4559a2 | 2007-07-13 23:57:11 +0000 | [diff] [blame] | 50 | struct VISIBILITY_HIDDEN LCSSA : public LoopPass { |
Nick Lewycky | ecd94c8 | 2007-05-06 13:37:16 +0000 | [diff] [blame] | 51 | static char ID; // Pass identification, replacement for typeid |
Devang Patel | b4559a2 | 2007-07-13 23:57:11 +0000 | [diff] [blame] | 52 | LCSSA() : LoopPass((intptr_t)&ID) {} |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 53 | |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 54 | // Cached analysis information for the current function. |
| 55 | LoopInfo *LI; |
Evan Cheng | cc045d5 | 2007-04-18 22:39:00 +0000 | [diff] [blame] | 56 | DominatorTree *DT; |
Owen Anderson | 92deacf | 2006-06-06 04:28:30 +0000 | [diff] [blame] | 57 | std::vector<BasicBlock*> LoopBlocks; |
Owen Anderson | 11f510b | 2006-05-26 13:58:26 +0000 | [diff] [blame] | 58 | |
Devang Patel | b4559a2 | 2007-07-13 23:57:11 +0000 | [diff] [blame] | 59 | virtual bool runOnLoop(Loop *L, LPPassManager &LPM); |
| 60 | |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 61 | void ProcessInstruction(Instruction* Instr, |
Devang Patel | b7211a2 | 2007-08-21 00:31:24 +0000 | [diff] [blame] | 62 | const SmallVector<BasicBlock*, 8>& exitBlocks); |
Owen Anderson | 11f510b | 2006-05-26 13:58:26 +0000 | [diff] [blame] | 63 | |
| 64 | /// This transformation requires natural loop information & requires that |
Owen Anderson | a90b2c7 | 2006-05-27 00:31:37 +0000 | [diff] [blame] | 65 | /// loop preheaders be inserted into the CFG. It maintains both of these, |
| 66 | /// as well as the CFG. It also requires dominator information. |
Owen Anderson | 11f510b | 2006-05-26 13:58:26 +0000 | [diff] [blame] | 67 | /// |
| 68 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
Owen Anderson | 2480737 | 2006-05-26 21:11:53 +0000 | [diff] [blame] | 69 | AU.setPreservesCFG(); |
Owen Anderson | 11f510b | 2006-05-26 13:58:26 +0000 | [diff] [blame] | 70 | AU.addRequiredID(LoopSimplifyID); |
| 71 | AU.addPreservedID(LoopSimplifyID); |
| 72 | AU.addRequired<LoopInfo>(); |
Devang Patel | b4559a2 | 2007-07-13 23:57:11 +0000 | [diff] [blame] | 73 | AU.addPreserved<LoopInfo>(); |
Evan Cheng | cc045d5 | 2007-04-18 22:39:00 +0000 | [diff] [blame] | 74 | AU.addRequired<DominatorTree>(); |
Devang Patel | b4559a2 | 2007-07-13 23:57:11 +0000 | [diff] [blame] | 75 | AU.addPreserved<ScalarEvolution>(); |
Devang Patel | 81a129c | 2007-07-30 20:23:45 +0000 | [diff] [blame] | 76 | AU.addPreserved<DominatorTree>(); |
| 77 | |
| 78 | // Request DominanceFrontier now, even though LCSSA does |
| 79 | // not use it. This allows Pass Manager to schedule Dominance |
| 80 | // Frontier early enough such that one LPPassManager can handle |
| 81 | // multiple loop transformation passes. |
| 82 | AU.addRequired<DominanceFrontier>(); |
| 83 | AU.addPreserved<DominanceFrontier>(); |
Owen Anderson | 11f510b | 2006-05-26 13:58:26 +0000 | [diff] [blame] | 84 | } |
| 85 | private: |
Chris Lattner | d6b7a16 | 2007-04-14 22:10:17 +0000 | [diff] [blame] | 86 | void getLoopValuesUsedOutsideLoop(Loop *L, |
| 87 | SetVector<Instruction*> &AffectedValues); |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 88 | |
Devang Patel | 2604242 | 2007-06-04 00:32:22 +0000 | [diff] [blame] | 89 | Value *GetValueForBlock(DomTreeNode *BB, Instruction *OrigInst, |
| 90 | std::map<DomTreeNode*, Value*> &Phis); |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 91 | |
Owen Anderson | 92deacf | 2006-06-06 04:28:30 +0000 | [diff] [blame] | 92 | /// inLoop - returns true if the given block is within the current loop |
| 93 | const bool inLoop(BasicBlock* B) { |
Owen Anderson | e9d93d5 | 2006-06-06 04:36:36 +0000 | [diff] [blame] | 94 | return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B); |
| 95 | } |
Owen Anderson | 11f510b | 2006-05-26 13:58:26 +0000 | [diff] [blame] | 96 | }; |
| 97 | |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 98 | char LCSSA::ID = 0; |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 99 | RegisterPass<LCSSA> X("lcssa", "Loop-Closed SSA Form Pass"); |
Owen Anderson | 11f510b | 2006-05-26 13:58:26 +0000 | [diff] [blame] | 100 | } |
| 101 | |
Devang Patel | b4559a2 | 2007-07-13 23:57:11 +0000 | [diff] [blame] | 102 | LoopPass *llvm::createLCSSAPass() { return new LCSSA(); } |
Owen Anderson | a452932 | 2006-06-08 20:02:53 +0000 | [diff] [blame] | 103 | const PassInfo *llvm::LCSSAID = X.getPassInfo(); |
Owen Anderson | 11f510b | 2006-05-26 13:58:26 +0000 | [diff] [blame] | 104 | |
Owen Anderson | a452932 | 2006-06-08 20:02:53 +0000 | [diff] [blame] | 105 | /// runOnFunction - Process all loops in the function, inner-most out. |
Devang Patel | b4559a2 | 2007-07-13 23:57:11 +0000 | [diff] [blame] | 106 | bool LCSSA::runOnLoop(Loop *L, LPPassManager &LPM) { |
Owen Anderson | 7be3f1e | 2006-06-13 19:37:18 +0000 | [diff] [blame] | 107 | |
Devang Patel | b4559a2 | 2007-07-13 23:57:11 +0000 | [diff] [blame] | 108 | LI = &LPM.getAnalysis<LoopInfo>(); |
Evan Cheng | cc045d5 | 2007-04-18 22:39:00 +0000 | [diff] [blame] | 109 | DT = &getAnalysis<DominatorTree>(); |
Devang Patel | 96bf524 | 2007-08-17 21:59:16 +0000 | [diff] [blame] | 110 | |
Owen Anderson | 2480737 | 2006-05-26 21:11:53 +0000 | [diff] [blame] | 111 | // Speed up queries by creating a sorted list of blocks |
Owen Anderson | 92deacf | 2006-06-06 04:28:30 +0000 | [diff] [blame] | 112 | LoopBlocks.clear(); |
| 113 | LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end()); |
| 114 | std::sort(LoopBlocks.begin(), LoopBlocks.end()); |
Owen Anderson | 2480737 | 2006-05-26 21:11:53 +0000 | [diff] [blame] | 115 | |
Chris Lattner | d6b7a16 | 2007-04-14 22:10:17 +0000 | [diff] [blame] | 116 | SetVector<Instruction*> AffectedValues; |
| 117 | getLoopValuesUsedOutsideLoop(L, AffectedValues); |
Owen Anderson | 11f510b | 2006-05-26 13:58:26 +0000 | [diff] [blame] | 118 | |
Owen Anderson | 408a406 | 2006-05-31 20:55:06 +0000 | [diff] [blame] | 119 | // If no values are affected, we can save a lot of work, since we know that |
| 120 | // nothing will be changed. |
| 121 | if (AffectedValues.empty()) |
| 122 | return false; |
| 123 | |
Devang Patel | b7211a2 | 2007-08-21 00:31:24 +0000 | [diff] [blame] | 124 | SmallVector<BasicBlock*, 8> exitBlocks; |
| 125 | L->getExitBlocks(exitBlocks); |
Owen Anderson | 2f21e07 | 2006-05-27 18:47:11 +0000 | [diff] [blame] | 126 | |
| 127 | // Iterate over all affected values for this loop and insert Phi nodes |
| 128 | // for them in the appropriate exit blocks |
Owen Anderson | 408a406 | 2006-05-31 20:55:06 +0000 | [diff] [blame] | 129 | |
Owen Anderson | 9e1c1dd | 2006-06-04 00:02:23 +0000 | [diff] [blame] | 130 | for (SetVector<Instruction*>::iterator I = AffectedValues.begin(), |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 131 | E = AffectedValues.end(); I != E; ++I) |
| 132 | ProcessInstruction(*I, exitBlocks); |
Owen Anderson | 00ea74c | 2006-05-29 01:00:00 +0000 | [diff] [blame] | 133 | |
Owen Anderson | c2cc15c | 2006-06-11 19:22:28 +0000 | [diff] [blame] | 134 | assert(L->isLCSSAForm()); |
| 135 | |
Owen Anderson | 92deacf | 2006-06-06 04:28:30 +0000 | [diff] [blame] | 136 | return true; |
Owen Anderson | 11f510b | 2006-05-26 13:58:26 +0000 | [diff] [blame] | 137 | } |
| 138 | |
Owen Anderson | a452932 | 2006-06-08 20:02:53 +0000 | [diff] [blame] | 139 | /// processInstruction - Given a live-out instruction, insert LCSSA Phi nodes, |
| 140 | /// eliminate all out-of-loop uses. |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 141 | void LCSSA::ProcessInstruction(Instruction *Instr, |
Devang Patel | b7211a2 | 2007-08-21 00:31:24 +0000 | [diff] [blame] | 142 | const SmallVector<BasicBlock*, 8>& exitBlocks) { |
Owen Anderson | 408a406 | 2006-05-31 20:55:06 +0000 | [diff] [blame] | 143 | ++NumLCSSA; // We are applying the transformation |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 144 | |
| 145 | // Keep track of the blocks that have the value available already. |
Devang Patel | 2604242 | 2007-06-04 00:32:22 +0000 | [diff] [blame] | 146 | std::map<DomTreeNode*, Value*> Phis; |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 147 | |
Devang Patel | 2604242 | 2007-06-04 00:32:22 +0000 | [diff] [blame] | 148 | DomTreeNode *InstrNode = DT->getNode(Instr->getParent()); |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 149 | |
| 150 | // Insert the LCSSA phi's into the exit blocks (dominated by the value), and |
| 151 | // add them to the Phi's map. |
Devang Patel | b7211a2 | 2007-08-21 00:31:24 +0000 | [diff] [blame] | 152 | for (SmallVector<BasicBlock*, 8>::const_iterator BBI = exitBlocks.begin(), |
Owen Anderson | 3d2aa47 | 2006-06-12 07:10:16 +0000 | [diff] [blame] | 153 | BBE = exitBlocks.end(); BBI != BBE; ++BBI) { |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 154 | BasicBlock *BB = *BBI; |
Devang Patel | 2604242 | 2007-06-04 00:32:22 +0000 | [diff] [blame] | 155 | DomTreeNode *ExitBBNode = DT->getNode(BB); |
Evan Cheng | cc045d5 | 2007-04-18 22:39:00 +0000 | [diff] [blame] | 156 | Value *&Phi = Phis[ExitBBNode]; |
Devang Patel | 9a51157 | 2007-06-07 17:47:21 +0000 | [diff] [blame] | 157 | if (!Phi && DT->dominates(InstrNode, ExitBBNode)) { |
Chris Lattner | cbea67f | 2006-10-31 18:56:48 +0000 | [diff] [blame] | 158 | PHINode *PN = new PHINode(Instr->getType(), Instr->getName()+".lcssa", |
| 159 | BB->begin()); |
| 160 | PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB))); |
| 161 | |
| 162 | // Remember that this phi makes the value alive in this block. |
| 163 | Phi = PN; |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 164 | |
| 165 | // Add inputs from inside the loop for this PHI. |
| 166 | for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) |
Chris Lattner | cbea67f | 2006-10-31 18:56:48 +0000 | [diff] [blame] | 167 | PN->addIncoming(Instr, *PI); |
Owen Anderson | 2824da4 | 2006-06-01 06:05:47 +0000 | [diff] [blame] | 168 | } |
Owen Anderson | 3d2aa47 | 2006-06-12 07:10:16 +0000 | [diff] [blame] | 169 | } |
Owen Anderson | 408a406 | 2006-05-31 20:55:06 +0000 | [diff] [blame] | 170 | |
Owen Anderson | 30019c8 | 2006-06-03 23:22:50 +0000 | [diff] [blame] | 171 | |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 172 | // Record all uses of Instr outside the loop. We need to rewrite these. The |
| 173 | // LCSSA phis won't be included because they use the value in the loop. |
| 174 | for (Value::use_iterator UI = Instr->use_begin(), E = Instr->use_end(); |
| 175 | UI != E;) { |
| 176 | BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); |
| 177 | if (PHINode *P = dyn_cast<PHINode>(*UI)) { |
Owen Anderson | 8b92d0c | 2006-06-13 20:50:09 +0000 | [diff] [blame] | 178 | unsigned OperandNo = UI.getOperandNo(); |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 179 | UserBB = P->getIncomingBlock(OperandNo/2); |
Owen Anderson | 8b92d0c | 2006-06-13 20:50:09 +0000 | [diff] [blame] | 180 | } |
| 181 | |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 182 | // If the user is in the loop, don't rewrite it! |
Chris Lattner | f9ba401 | 2006-08-02 00:16:47 +0000 | [diff] [blame] | 183 | if (UserBB == Instr->getParent() || inLoop(UserBB)) { |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 184 | ++UI; |
| 185 | continue; |
Owen Anderson | 2824da4 | 2006-06-01 06:05:47 +0000 | [diff] [blame] | 186 | } |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 187 | |
| 188 | // Otherwise, patch up uses of the value with the appropriate LCSSA Phi, |
| 189 | // inserting PHI nodes into join points where needed. |
Evan Cheng | cc045d5 | 2007-04-18 22:39:00 +0000 | [diff] [blame] | 190 | Value *Val = GetValueForBlock(DT->getNode(UserBB), Instr, Phis); |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 191 | |
| 192 | // Preincrement the iterator to avoid invalidating it when we change the |
| 193 | // value. |
| 194 | Use &U = UI.getUse(); |
| 195 | ++UI; |
| 196 | U.set(Val); |
Owen Anderson | 408a406 | 2006-05-31 20:55:06 +0000 | [diff] [blame] | 197 | } |
| 198 | } |
| 199 | |
Owen Anderson | 2480737 | 2006-05-26 21:11:53 +0000 | [diff] [blame] | 200 | /// getLoopValuesUsedOutsideLoop - Return any values defined in the loop that |
| 201 | /// are used by instructions outside of it. |
Chris Lattner | d6b7a16 | 2007-04-14 22:10:17 +0000 | [diff] [blame] | 202 | void LCSSA::getLoopValuesUsedOutsideLoop(Loop *L, |
| 203 | SetVector<Instruction*> &AffectedValues) { |
Owen Anderson | 408a406 | 2006-05-31 20:55:06 +0000 | [diff] [blame] | 204 | // FIXME: For large loops, we may be able to avoid a lot of use-scanning |
| 205 | // by using dominance information. In particular, if a block does not |
| 206 | // dominate any of the loop exits, then none of the values defined in the |
| 207 | // block could be used outside the loop. |
Owen Anderson | 11f510b | 2006-05-26 13:58:26 +0000 | [diff] [blame] | 208 | for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); |
| 209 | BB != E; ++BB) { |
| 210 | for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ++I) |
| 211 | for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; |
| 212 | ++UI) { |
| 213 | BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); |
Owen Anderson | 7be3f1e | 2006-06-13 19:37:18 +0000 | [diff] [blame] | 214 | if (PHINode* p = dyn_cast<PHINode>(*UI)) { |
| 215 | unsigned OperandNo = UI.getOperandNo(); |
| 216 | UserBB = p->getIncomingBlock(OperandNo/2); |
| 217 | } |
| 218 | |
Chris Lattner | f9ba401 | 2006-08-02 00:16:47 +0000 | [diff] [blame] | 219 | if (*BB != UserBB && !inLoop(UserBB)) { |
Owen Anderson | 11f510b | 2006-05-26 13:58:26 +0000 | [diff] [blame] | 220 | AffectedValues.insert(I); |
Owen Anderson | 408a406 | 2006-05-31 20:55:06 +0000 | [diff] [blame] | 221 | break; |
| 222 | } |
Owen Anderson | 11f510b | 2006-05-26 13:58:26 +0000 | [diff] [blame] | 223 | } |
| 224 | } |
Owen Anderson | 2480737 | 2006-05-26 21:11:53 +0000 | [diff] [blame] | 225 | } |
Owen Anderson | 408a406 | 2006-05-31 20:55:06 +0000 | [diff] [blame] | 226 | |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 227 | /// GetValueForBlock - Get the value to use within the specified basic block. |
| 228 | /// available values are in Phis. |
Devang Patel | 2604242 | 2007-06-04 00:32:22 +0000 | [diff] [blame] | 229 | Value *LCSSA::GetValueForBlock(DomTreeNode *BB, Instruction *OrigInst, |
| 230 | std::map<DomTreeNode*, Value*> &Phis) { |
Chris Lattner | cbea67f | 2006-10-31 18:56:48 +0000 | [diff] [blame] | 231 | // If there is no dominator info for this BB, it is unreachable. |
| 232 | if (BB == 0) |
| 233 | return UndefValue::get(OrigInst->getType()); |
| 234 | |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 235 | // If we have already computed this value, return the previously computed val. |
Chris Lattner | cbea67f | 2006-10-31 18:56:48 +0000 | [diff] [blame] | 236 | Value *&V = Phis[BB]; |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 237 | if (V) return V; |
| 238 | |
Devang Patel | 2604242 | 2007-06-04 00:32:22 +0000 | [diff] [blame] | 239 | DomTreeNode *IDom = BB->getIDom(); |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 240 | |
| 241 | // Otherwise, there are two cases: we either have to insert a PHI node or we |
| 242 | // don't. We need to insert a PHI node if this block is not dominated by one |
| 243 | // of the exit nodes from the loop (the loop could have multiple exits, and |
| 244 | // though the value defined *inside* the loop dominated all its uses, each |
| 245 | // exit by itself may not dominate all the uses). |
| 246 | // |
| 247 | // The simplest way to check for this condition is by checking to see if the |
| 248 | // idom is in the loop. If so, we *know* that none of the exit blocks |
| 249 | // dominate this block. Note that we *know* that the block defining the |
| 250 | // original instruction is in the idom chain, because if it weren't, then the |
| 251 | // original value didn't dominate this use. |
Evan Cheng | cc045d5 | 2007-04-18 22:39:00 +0000 | [diff] [blame] | 252 | if (!inLoop(IDom->getBlock())) { |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 253 | // Idom is not in the loop, we must still be "below" the exit block and must |
| 254 | // be fully dominated by the value live in the idom. |
| 255 | return V = GetValueForBlock(IDom, OrigInst, Phis); |
| 256 | } |
Owen Anderson | e4e1ecd | 2006-07-09 08:14:06 +0000 | [diff] [blame] | 257 | |
Evan Cheng | cc045d5 | 2007-04-18 22:39:00 +0000 | [diff] [blame] | 258 | BasicBlock *BBN = BB->getBlock(); |
| 259 | |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 260 | // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so |
| 261 | // now, then get values to fill in the incoming values for the PHI. |
Chris Lattner | cbea67f | 2006-10-31 18:56:48 +0000 | [diff] [blame] | 262 | PHINode *PN = new PHINode(OrigInst->getType(), OrigInst->getName()+".lcssa", |
Evan Cheng | cc045d5 | 2007-04-18 22:39:00 +0000 | [diff] [blame] | 263 | BBN->begin()); |
| 264 | PN->reserveOperandSpace(std::distance(pred_begin(BBN), pred_end(BBN))); |
Chris Lattner | cbea67f | 2006-10-31 18:56:48 +0000 | [diff] [blame] | 265 | V = PN; |
| 266 | |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 267 | // Fill in the incoming values for the block. |
Evan Cheng | cc045d5 | 2007-04-18 22:39:00 +0000 | [diff] [blame] | 268 | for (pred_iterator PI = pred_begin(BBN), E = pred_end(BBN); PI != E; ++PI) |
| 269 | PN->addIncoming(GetValueForBlock(DT->getNode(*PI), OrigInst, Phis), *PI); |
Chris Lattner | cbea67f | 2006-10-31 18:56:48 +0000 | [diff] [blame] | 270 | return PN; |
Owen Anderson | 408a406 | 2006-05-31 20:55:06 +0000 | [diff] [blame] | 271 | } |
Chris Lattner | d41ae8b | 2006-08-02 00:06:09 +0000 | [diff] [blame] | 272 | |