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