Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 1 | //===- TailDuplication.cpp - Simplify CFG through tail duplication --------===// |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 2 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 7 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 9 | // |
| 10 | // This pass performs a limited form of tail duplication, intended to simplify |
| 11 | // CFGs by removing some unconditional branches. This pass is necessary to |
| 12 | // straighten out loops created by the C front-end, but also is capable of |
| 13 | // making other code nicer. After this pass is run, the CFG simplify pass |
| 14 | // should be run to clean up the mess. |
| 15 | // |
| 16 | // This pass could be enhanced in the future to use profile information to be |
| 17 | // more aggressive. |
| 18 | // |
| 19 | //===----------------------------------------------------------------------===// |
| 20 | |
Chris Lattner | 7514437 | 2006-09-27 04:58:23 +0000 | [diff] [blame] | 21 | #define DEBUG_TYPE "tailduplicate" |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 22 | #include "llvm/Transforms/Scalar.h" |
Chris Lattner | 3186d27 | 2003-08-31 21:17:44 +0000 | [diff] [blame] | 23 | #include "llvm/Constant.h" |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 24 | #include "llvm/Function.h" |
Misha Brukman | d8e1eea | 2004-07-29 17:05:13 +0000 | [diff] [blame] | 25 | #include "llvm/Instructions.h" |
Chris Lattner | b9df9b4 | 2004-11-22 17:23:57 +0000 | [diff] [blame] | 26 | #include "llvm/IntrinsicInst.h" |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 27 | #include "llvm/Pass.h" |
| 28 | #include "llvm/Type.h" |
| 29 | #include "llvm/Support/CFG.h" |
| 30 | #include "llvm/Transforms/Utils/Local.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 31 | #include "llvm/Support/CommandLine.h" |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 32 | #include "llvm/Support/Compiler.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 33 | #include "llvm/Support/Debug.h" |
| 34 | #include "llvm/ADT/Statistic.h" |
Dan Gohman | c9235d2 | 2008-03-21 23:51:57 +0000 | [diff] [blame] | 35 | #include <map> |
Chris Lattner | d745602 | 2004-01-09 06:02:20 +0000 | [diff] [blame] | 36 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 37 | |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 38 | STATISTIC(NumEliminated, "Number of unconditional branches eliminated"); |
| 39 | |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 40 | namespace { |
Chris Lattner | 3c85eef | 2004-04-18 00:52:43 +0000 | [diff] [blame] | 41 | cl::opt<unsigned> |
| 42 | Threshold("taildup-threshold", cl::desc("Max block size to tail duplicate"), |
| 43 | cl::init(6), cl::Hidden); |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 44 | class VISIBILITY_HIDDEN TailDup : public FunctionPass { |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 45 | bool runOnFunction(Function &F); |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 46 | public: |
Nick Lewycky | ecd94c8 | 2007-05-06 13:37:16 +0000 | [diff] [blame] | 47 | static char ID; // Pass identification, replacement for typeid |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 48 | TailDup() : FunctionPass((intptr_t)&ID) {} |
| 49 | |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 50 | private: |
| 51 | inline bool shouldEliminateUnconditionalBranch(TerminatorInst *TI); |
| 52 | inline void eliminateUnconditionalBranch(BranchInst *BI); |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 53 | }; |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 54 | char TailDup::ID = 0; |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 55 | RegisterPass<TailDup> X("tailduplicate", "Tail Duplication"); |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 56 | } |
| 57 | |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 58 | // Public interface to the Tail Duplication pass |
Chris Lattner | 4b50156 | 2004-09-20 04:43:15 +0000 | [diff] [blame] | 59 | FunctionPass *llvm::createTailDuplicationPass() { return new TailDup(); } |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 60 | |
| 61 | /// runOnFunction - Top level algorithm - Loop over each unconditional branch in |
| 62 | /// the function, eliminating it if it looks attractive enough. |
| 63 | /// |
| 64 | bool TailDup::runOnFunction(Function &F) { |
| 65 | bool Changed = false; |
| 66 | for (Function::iterator I = F.begin(), E = F.end(); I != E; ) |
Chris Lattner | 24ad00d | 2004-03-16 23:29:09 +0000 | [diff] [blame] | 67 | if (shouldEliminateUnconditionalBranch(I->getTerminator())) { |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 68 | eliminateUnconditionalBranch(cast<BranchInst>(I->getTerminator())); |
| 69 | Changed = true; |
| 70 | } else { |
| 71 | ++I; |
| 72 | } |
| 73 | return Changed; |
| 74 | } |
| 75 | |
| 76 | /// shouldEliminateUnconditionalBranch - Return true if this branch looks |
| 77 | /// attractive to eliminate. We eliminate the branch if the destination basic |
| 78 | /// block has <= 5 instructions in it, not counting PHI nodes. In practice, |
| 79 | /// since one of these is a terminator instruction, this means that we will add |
| 80 | /// up to 4 instructions to the new block. |
| 81 | /// |
| 82 | /// We don't count PHI nodes in the count since they will be removed when the |
| 83 | /// contents of the block are copied over. |
| 84 | /// |
| 85 | bool TailDup::shouldEliminateUnconditionalBranch(TerminatorInst *TI) { |
| 86 | BranchInst *BI = dyn_cast<BranchInst>(TI); |
| 87 | if (!BI || !BI->isUnconditional()) return false; // Not an uncond branch! |
| 88 | |
| 89 | BasicBlock *Dest = BI->getSuccessor(0); |
| 90 | if (Dest == BI->getParent()) return false; // Do not loop infinitely! |
| 91 | |
Chris Lattner | 00f185f | 2003-07-23 03:32:41 +0000 | [diff] [blame] | 92 | // Do not inline a block if we will just get another branch to the same block! |
Chris Lattner | 4bebf08 | 2004-03-16 19:45:22 +0000 | [diff] [blame] | 93 | TerminatorInst *DTI = Dest->getTerminator(); |
| 94 | if (BranchInst *DBI = dyn_cast<BranchInst>(DTI)) |
Chris Lattner | 00f185f | 2003-07-23 03:32:41 +0000 | [diff] [blame] | 95 | if (DBI->isUnconditional() && DBI->getSuccessor(0) == Dest) |
| 96 | return false; // Do not loop infinitely! |
| 97 | |
Chris Lattner | 24ad00d | 2004-03-16 23:29:09 +0000 | [diff] [blame] | 98 | // FIXME: DemoteRegToStack cannot yet demote invoke instructions to the stack, |
| 99 | // because doing so would require breaking critical edges. This should be |
| 100 | // fixed eventually. |
| 101 | if (!DTI->use_empty()) |
| 102 | return false; |
| 103 | |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 104 | // Do not bother working on dead blocks... |
| 105 | pred_iterator PI = pred_begin(Dest), PE = pred_end(Dest); |
| 106 | if (PI == PE && Dest != Dest->getParent()->begin()) |
| 107 | return false; // It's just a dead block, ignore it... |
| 108 | |
| 109 | // Also, do not bother with blocks with only a single predecessor: simplify |
| 110 | // CFG will fold these two blocks together! |
| 111 | ++PI; |
| 112 | if (PI == PE) return false; // Exactly one predecessor! |
| 113 | |
| 114 | BasicBlock::iterator I = Dest->begin(); |
| 115 | while (isa<PHINode>(*I)) ++I; |
| 116 | |
Chris Lattner | b9df9b4 | 2004-11-22 17:23:57 +0000 | [diff] [blame] | 117 | for (unsigned Size = 0; I != Dest->end(); ++I) { |
| 118 | if (Size == Threshold) return false; // The block is too large. |
Chris Lattner | 0647ebf | 2007-11-04 06:37:55 +0000 | [diff] [blame] | 119 | |
| 120 | // Don't tail duplicate call instructions. They are very large compared to |
| 121 | // other instructions. |
| 122 | if (isa<CallInst>(I) || isa<InvokeInst>(I)) return false; |
| 123 | |
Chris Lattner | b9df9b4 | 2004-11-22 17:23:57 +0000 | [diff] [blame] | 124 | // Only count instructions that are not debugger intrinsics. |
| 125 | if (!isa<DbgInfoIntrinsic>(I)) ++Size; |
| 126 | } |
Chris Lattner | 4bebf08 | 2004-03-16 19:45:22 +0000 | [diff] [blame] | 127 | |
| 128 | // Do not tail duplicate a block that has thousands of successors into a block |
| 129 | // with a single successor if the block has many other predecessors. This can |
| 130 | // cause an N^2 explosion in CFG edges (and PHI node entries), as seen in |
| 131 | // cases that have a large number of indirect gotos. |
Chris Lattner | 7e54a01 | 2004-11-01 07:05:07 +0000 | [diff] [blame] | 132 | unsigned NumSuccs = DTI->getNumSuccessors(); |
| 133 | if (NumSuccs > 8) { |
| 134 | unsigned TooMany = 128; |
| 135 | if (NumSuccs >= TooMany) return false; |
| 136 | TooMany = TooMany/NumSuccs; |
| 137 | for (; PI != PE; ++PI) |
| 138 | if (TooMany-- == 0) return false; |
| 139 | } |
Chris Lattner | e99c623 | 2006-09-07 21:30:15 +0000 | [diff] [blame] | 140 | |
| 141 | // Finally, if this unconditional branch is a fall-through, be careful about |
| 142 | // tail duplicating it. In particular, we don't want to taildup it if the |
| 143 | // original block will still be there after taildup is completed: doing so |
| 144 | // would eliminate the fall-through, requiring unconditional branches. |
| 145 | Function::iterator DestI = Dest; |
| 146 | if (&*--DestI == BI->getParent()) { |
| 147 | // The uncond branch is a fall-through. Tail duplication of the block is |
| 148 | // will eliminate the fall-through-ness and end up cloning the terminator |
| 149 | // at the end of the Dest block. Since the original Dest block will |
| 150 | // continue to exist, this means that one or the other will not be able to |
| 151 | // fall through. One typical example that this helps with is code like: |
| 152 | // if (a) |
| 153 | // foo(); |
| 154 | // if (b) |
| 155 | // foo(); |
| 156 | // Cloning the 'if b' block into the end of the first foo block is messy. |
Chris Lattner | dfa1af0 | 2006-09-10 18:17:58 +0000 | [diff] [blame] | 157 | |
| 158 | // The messy case is when the fall-through block falls through to other |
| 159 | // blocks. This is what we would be preventing if we cloned the block. |
| 160 | DestI = Dest; |
| 161 | if (++DestI != Dest->getParent()->end()) { |
| 162 | BasicBlock *DestSucc = DestI; |
| 163 | // If any of Dest's successors are fall-throughs, don't do this xform. |
| 164 | for (succ_iterator SI = succ_begin(Dest), SE = succ_end(Dest); |
| 165 | SI != SE; ++SI) |
| 166 | if (*SI == DestSucc) |
| 167 | return false; |
| 168 | } |
Chris Lattner | e99c623 | 2006-09-07 21:30:15 +0000 | [diff] [blame] | 169 | } |
Chris Lattner | 4bebf08 | 2004-03-16 19:45:22 +0000 | [diff] [blame] | 170 | |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 171 | return true; |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 172 | } |
| 173 | |
Chris Lattner | c3e903f | 2004-10-06 03:27:37 +0000 | [diff] [blame] | 174 | /// FindObviousSharedDomOf - We know there is a branch from SrcBlock to |
| 175 | /// DestBlock, and that SrcBlock is not the only predecessor of DstBlock. If we |
| 176 | /// can find a predecessor of SrcBlock that is a dominator of both SrcBlock and |
| 177 | /// DstBlock, return it. |
| 178 | static BasicBlock *FindObviousSharedDomOf(BasicBlock *SrcBlock, |
| 179 | BasicBlock *DstBlock) { |
| 180 | // SrcBlock must have a single predecessor. |
| 181 | pred_iterator PI = pred_begin(SrcBlock), PE = pred_end(SrcBlock); |
| 182 | if (PI == PE || ++PI != PE) return 0; |
| 183 | |
| 184 | BasicBlock *SrcPred = *pred_begin(SrcBlock); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 185 | |
Chris Lattner | c3e903f | 2004-10-06 03:27:37 +0000 | [diff] [blame] | 186 | // Look at the predecessors of DstBlock. One of them will be SrcBlock. If |
| 187 | // there is only one other pred, get it, otherwise we can't handle it. |
| 188 | PI = pred_begin(DstBlock); PE = pred_end(DstBlock); |
| 189 | BasicBlock *DstOtherPred = 0; |
| 190 | if (*PI == SrcBlock) { |
| 191 | if (++PI == PE) return 0; |
| 192 | DstOtherPred = *PI; |
| 193 | if (++PI != PE) return 0; |
| 194 | } else { |
| 195 | DstOtherPred = *PI; |
| 196 | if (++PI == PE || *PI != SrcBlock || ++PI != PE) return 0; |
| 197 | } |
| 198 | |
| 199 | // We can handle two situations here: "if then" and "if then else" blocks. An |
| 200 | // 'if then' situation is just where DstOtherPred == SrcPred. |
| 201 | if (DstOtherPred == SrcPred) |
| 202 | return SrcPred; |
| 203 | |
| 204 | // Check to see if we have an "if then else" situation, which means that |
| 205 | // DstOtherPred will have a single predecessor and it will be SrcPred. |
| 206 | PI = pred_begin(DstOtherPred); PE = pred_end(DstOtherPred); |
| 207 | if (PI != PE && *PI == SrcPred) { |
| 208 | if (++PI != PE) return 0; // Not a single pred. |
| 209 | return SrcPred; // Otherwise, it's an "if then" situation. Return the if. |
| 210 | } |
| 211 | |
| 212 | // Otherwise, this is something we can't handle. |
| 213 | return 0; |
| 214 | } |
| 215 | |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 216 | |
| 217 | /// eliminateUnconditionalBranch - Clone the instructions from the destination |
| 218 | /// block into the source block, eliminating the specified unconditional branch. |
| 219 | /// If the destination block defines values used by successors of the dest |
| 220 | /// block, we may need to insert PHI nodes. |
| 221 | /// |
| 222 | void TailDup::eliminateUnconditionalBranch(BranchInst *Branch) { |
| 223 | BasicBlock *SourceBlock = Branch->getParent(); |
| 224 | BasicBlock *DestBlock = Branch->getSuccessor(0); |
| 225 | assert(SourceBlock != DestBlock && "Our predicate is broken!"); |
| 226 | |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 227 | DOUT << "TailDuplication[" << SourceBlock->getParent()->getName() |
| 228 | << "]: Eliminating branch: " << *Branch; |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 229 | |
Chris Lattner | c3e903f | 2004-10-06 03:27:37 +0000 | [diff] [blame] | 230 | // See if we can avoid duplicating code by moving it up to a dominator of both |
| 231 | // blocks. |
| 232 | if (BasicBlock *DomBlock = FindObviousSharedDomOf(SourceBlock, DestBlock)) { |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 233 | DOUT << "Found shared dominator: " << DomBlock->getName() << "\n"; |
Chris Lattner | c3e903f | 2004-10-06 03:27:37 +0000 | [diff] [blame] | 234 | |
| 235 | // If there are non-phi instructions in DestBlock that have no operands |
| 236 | // defined in DestBlock, and if the instruction has no side effects, we can |
| 237 | // move the instruction to DomBlock instead of duplicating it. |
| 238 | BasicBlock::iterator BBI = DestBlock->begin(); |
| 239 | while (isa<PHINode>(BBI)) ++BBI; |
| 240 | while (!isa<TerminatorInst>(BBI)) { |
| 241 | Instruction *I = BBI++; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 242 | |
Chris Lattner | c3e903f | 2004-10-06 03:27:37 +0000 | [diff] [blame] | 243 | bool CanHoist = !I->isTrapping() && !I->mayWriteToMemory(); |
| 244 | if (CanHoist) { |
| 245 | for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) |
| 246 | if (Instruction *OpI = dyn_cast<Instruction>(I->getOperand(op))) |
| 247 | if (OpI->getParent() == DestBlock || |
| 248 | (isa<InvokeInst>(OpI) && OpI->getParent() == DomBlock)) { |
| 249 | CanHoist = false; |
| 250 | break; |
| 251 | } |
| 252 | if (CanHoist) { |
| 253 | // Remove from DestBlock, move right before the term in DomBlock. |
| 254 | DestBlock->getInstList().remove(I); |
| 255 | DomBlock->getInstList().insert(DomBlock->getTerminator(), I); |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 256 | DOUT << "Hoisted: " << *I; |
Chris Lattner | c3e903f | 2004-10-06 03:27:37 +0000 | [diff] [blame] | 257 | } |
| 258 | } |
| 259 | } |
| 260 | } |
| 261 | |
Chris Lattner | 24ad00d | 2004-03-16 23:29:09 +0000 | [diff] [blame] | 262 | // Tail duplication can not update SSA properties correctly if the values |
| 263 | // defined in the duplicated tail are used outside of the tail itself. For |
| 264 | // this reason, we spill all values that are used outside of the tail to the |
| 265 | // stack. |
| 266 | for (BasicBlock::iterator I = DestBlock->begin(); I != DestBlock->end(); ++I) |
| 267 | for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; |
| 268 | ++UI) { |
| 269 | bool ShouldDemote = false; |
| 270 | if (cast<Instruction>(*UI)->getParent() != DestBlock) { |
| 271 | // We must allow our successors to use tail values in their PHI nodes |
| 272 | // (if the incoming value corresponds to the tail block). |
| 273 | if (PHINode *PN = dyn_cast<PHINode>(*UI)) { |
| 274 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) |
| 275 | if (PN->getIncomingValue(i) == I && |
| 276 | PN->getIncomingBlock(i) != DestBlock) { |
| 277 | ShouldDemote = true; |
| 278 | break; |
| 279 | } |
| 280 | |
| 281 | } else { |
| 282 | ShouldDemote = true; |
| 283 | } |
| 284 | } else if (PHINode *PN = dyn_cast<PHINode>(cast<Instruction>(*UI))) { |
| 285 | // If the user of this instruction is a PHI node in the current block, |
Chris Lattner | 50eafbc | 2004-03-16 23:36:49 +0000 | [diff] [blame] | 286 | // which has an entry from another block using the value, spill it. |
| 287 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) |
| 288 | if (PN->getIncomingValue(i) == I && |
| 289 | PN->getIncomingBlock(i) != DestBlock) { |
| 290 | ShouldDemote = true; |
| 291 | break; |
| 292 | } |
Chris Lattner | 24ad00d | 2004-03-16 23:29:09 +0000 | [diff] [blame] | 293 | } |
| 294 | |
| 295 | if (ShouldDemote) { |
| 296 | // We found a use outside of the tail. Create a new stack slot to |
| 297 | // break this inter-block usage pattern. |
| 298 | DemoteRegToStack(*I); |
| 299 | break; |
| 300 | } |
| 301 | } |
| 302 | |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 303 | // We are going to have to map operands from the original block B to the new |
| 304 | // copy of the block B'. If there are PHI nodes in the DestBlock, these PHI |
| 305 | // nodes also define part of this mapping. Loop over these PHI nodes, adding |
| 306 | // them to our mapping. |
Chris Lattner | ea635cd | 2003-06-22 20:25:27 +0000 | [diff] [blame] | 307 | // |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 308 | std::map<Value*, Value*> ValueMapping; |
| 309 | |
| 310 | BasicBlock::iterator BI = DestBlock->begin(); |
| 311 | bool HadPHINodes = isa<PHINode>(BI); |
| 312 | for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI) |
| 313 | ValueMapping[PN] = PN->getIncomingValueForBlock(SourceBlock); |
| 314 | |
| 315 | // Clone the non-phi instructions of the dest block into the source block, |
| 316 | // keeping track of the mapping... |
| 317 | // |
| 318 | for (; BI != DestBlock->end(); ++BI) { |
| 319 | Instruction *New = BI->clone(); |
Owen Anderson | 6bc41e8 | 2008-04-14 17:38:21 +0000 | [diff] [blame^] | 320 | New->setName(BI->getName()); |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 321 | SourceBlock->getInstList().push_back(New); |
| 322 | ValueMapping[BI] = New; |
| 323 | } |
| 324 | |
| 325 | // Now that we have built the mapping information and cloned all of the |
| 326 | // instructions (giving us a new terminator, among other things), walk the new |
| 327 | // instructions, rewriting references of old instructions to use new |
| 328 | // instructions. |
| 329 | // |
| 330 | BI = Branch; ++BI; // Get an iterator to the first new instruction |
| 331 | for (; BI != SourceBlock->end(); ++BI) |
| 332 | for (unsigned i = 0, e = BI->getNumOperands(); i != e; ++i) |
| 333 | if (Value *Remapped = ValueMapping[BI->getOperand(i)]) |
| 334 | BI->setOperand(i, Remapped); |
| 335 | |
| 336 | // Next we check to see if any of the successors of DestBlock had PHI nodes. |
| 337 | // If so, we need to add entries to the PHI nodes for SourceBlock now. |
| 338 | for (succ_iterator SI = succ_begin(DestBlock), SE = succ_end(DestBlock); |
| 339 | SI != SE; ++SI) { |
| 340 | BasicBlock *Succ = *SI; |
Reid Spencer | 2da5c3d | 2004-09-15 17:06:42 +0000 | [diff] [blame] | 341 | for (BasicBlock::iterator PNI = Succ->begin(); isa<PHINode>(PNI); ++PNI) { |
| 342 | PHINode *PN = cast<PHINode>(PNI); |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 343 | // Ok, we have a PHI node. Figure out what the incoming value was for the |
| 344 | // DestBlock. |
| 345 | Value *IV = PN->getIncomingValueForBlock(DestBlock); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 346 | |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 347 | // Remap the value if necessary... |
| 348 | if (Value *MappedIV = ValueMapping[IV]) |
| 349 | IV = MappedIV; |
| 350 | PN->addIncoming(IV, SourceBlock); |
| 351 | } |
| 352 | } |
Chris Lattner | 24ad00d | 2004-03-16 23:29:09 +0000 | [diff] [blame] | 353 | |
| 354 | // Next, remove the old branch instruction, and any PHI node entries that we |
| 355 | // had. |
| 356 | BI = Branch; ++BI; // Get an iterator to the first new instruction |
| 357 | DestBlock->removePredecessor(SourceBlock); // Remove entries in PHI nodes... |
| 358 | SourceBlock->getInstList().erase(Branch); // Destroy the uncond branch... |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 359 | |
| 360 | // Final step: now that we have finished everything up, walk the cloned |
| 361 | // instructions one last time, constant propagating and DCE'ing them, because |
| 362 | // they may not be needed anymore. |
| 363 | // |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 364 | if (HadPHINodes) |
| 365 | while (BI != SourceBlock->end()) |
| 366 | if (!dceInstruction(BI) && !doConstantPropagation(BI)) |
| 367 | ++BI; |
| 368 | |
Chris Lattner | 7a7bef4 | 2003-06-22 20:10:28 +0000 | [diff] [blame] | 369 | ++NumEliminated; // We just killed a branch! |
| 370 | } |