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