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