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