LLVM API Documentation
00001 //===- TailDuplication.cpp - Simplify CFG through tail duplication --------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass performs a limited form of tail duplication, intended to simplify 00011 // CFGs by removing some unconditional branches. This pass is necessary to 00012 // straighten out loops created by the C front-end, but also is capable of 00013 // making other code nicer. After this pass is run, the CFG simplify pass 00014 // should be run to clean up the mess. 00015 // 00016 // This pass could be enhanced in the future to use profile information to be 00017 // more aggressive. 00018 // 00019 //===----------------------------------------------------------------------===// 00020 00021 #define DEBUG_TYPE "tailduplicate" 00022 #include "llvm/Transforms/Scalar.h" 00023 #include "llvm/Constant.h" 00024 #include "llvm/Function.h" 00025 #include "llvm/Instructions.h" 00026 #include "llvm/IntrinsicInst.h" 00027 #include "llvm/Pass.h" 00028 #include "llvm/Type.h" 00029 #include "llvm/Support/CFG.h" 00030 #include "llvm/Analysis/ConstantFolding.h" 00031 #include "llvm/Transforms/Utils/Local.h" 00032 #include "llvm/Support/CommandLine.h" 00033 #include "llvm/Support/Compiler.h" 00034 #include "llvm/Support/Debug.h" 00035 #include "llvm/Support/raw_ostream.h" 00036 #include "llvm/ADT/Statistic.h" 00037 #include "llvm/ADT/SmallPtrSet.h" 00038 #include <map> 00039 using namespace llvm; 00040 00041 STATISTIC(NumEliminated, "Number of unconditional branches eliminated"); 00042 00043 static cl::opt<unsigned> 00044 TailDupThreshold("taildup-threshold", 00045 cl::desc("Max block size to tail duplicate"), 00046 cl::init(1), cl::Hidden); 00047 00048 namespace { 00049 class VISIBILITY_HIDDEN TailDup : public FunctionPass { 00050 bool runOnFunction(Function &F); 00051 public: 00052 static char ID; // Pass identification, replacement for typeid 00053 TailDup() : FunctionPass(&ID) {} 00054 00055 private: 00056 inline bool shouldEliminateUnconditionalBranch(TerminatorInst *, unsigned); 00057 inline void eliminateUnconditionalBranch(BranchInst *BI); 00058 SmallPtrSet<BasicBlock*, 4> CycleDetector; 00059 }; 00060 } 00061 00062 char TailDup::ID = 0; 00063 static RegisterPass<TailDup> X("tailduplicate", "Tail Duplication"); 00064 00065 // Public interface to the Tail Duplication pass 00066 FunctionPass *llvm::createTailDuplicationPass() { return new TailDup(); } 00067 00068 /// runOnFunction - Top level algorithm - Loop over each unconditional branch in 00069 /// the function, eliminating it if it looks attractive enough. CycleDetector 00070 /// prevents infinite loops by checking that we aren't redirecting a branch to 00071 /// a place it already pointed to earlier; see PR 2323. 00072 bool TailDup::runOnFunction(Function &F) { 00073 bool Changed = false; 00074 CycleDetector.clear(); 00075 for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { 00076 if (shouldEliminateUnconditionalBranch(I->getTerminator(), 00077 TailDupThreshold)) { 00078 eliminateUnconditionalBranch(cast<BranchInst>(I->getTerminator())); 00079 Changed = true; 00080 } else { 00081 ++I; 00082 CycleDetector.clear(); 00083 } 00084 } 00085 return Changed; 00086 } 00087 00088 /// shouldEliminateUnconditionalBranch - Return true if this branch looks 00089 /// attractive to eliminate. We eliminate the branch if the destination basic 00090 /// block has <= 5 instructions in it, not counting PHI nodes. In practice, 00091 /// since one of these is a terminator instruction, this means that we will add 00092 /// up to 4 instructions to the new block. 00093 /// 00094 /// We don't count PHI nodes in the count since they will be removed when the 00095 /// contents of the block are copied over. 00096 /// 00097 bool TailDup::shouldEliminateUnconditionalBranch(TerminatorInst *TI, 00098 unsigned Threshold) { 00099 BranchInst *BI = dyn_cast<BranchInst>(TI); 00100 if (!BI || !BI->isUnconditional()) return false; // Not an uncond branch! 00101 00102 BasicBlock *Dest = BI->getSuccessor(0); 00103 if (Dest == BI->getParent()) return false; // Do not loop infinitely! 00104 00105 // Do not inline a block if we will just get another branch to the same block! 00106 TerminatorInst *DTI = Dest->getTerminator(); 00107 if (BranchInst *DBI = dyn_cast<BranchInst>(DTI)) 00108 if (DBI->isUnconditional() && DBI->getSuccessor(0) == Dest) 00109 return false; // Do not loop infinitely! 00110 00111 // FIXME: DemoteRegToStack cannot yet demote invoke instructions to the stack, 00112 // because doing so would require breaking critical edges. This should be 00113 // fixed eventually. 00114 if (!DTI->use_empty()) 00115 return false; 00116 00117 // Do not bother with blocks with only a single predecessor: simplify 00118 // CFG will fold these two blocks together! 00119 pred_iterator PI = pred_begin(Dest), PE = pred_end(Dest); 00120 ++PI; 00121 if (PI == PE) return false; // Exactly one predecessor! 00122 00123 BasicBlock::iterator I = Dest->getFirstNonPHI(); 00124 00125 for (unsigned Size = 0; I != Dest->end(); ++I) { 00126 if (Size == Threshold) return false; // The block is too large. 00127 00128 // Don't tail duplicate call instructions. They are very large compared to 00129 // other instructions. 00130 if (isa<CallInst>(I) || isa<InvokeInst>(I)) return false; 00131 00132 // Allso alloca and malloc. 00133 if (isa<AllocationInst>(I)) return false; 00134 00135 // Some vector instructions can expand into a number of instructions. 00136 if (isa<ShuffleVectorInst>(I) || isa<ExtractElementInst>(I) || 00137 isa<InsertElementInst>(I)) return false; 00138 00139 // Only count instructions that are not debugger intrinsics. 00140 if (!isa<DbgInfoIntrinsic>(I)) ++Size; 00141 } 00142 00143 // Do not tail duplicate a block that has thousands of successors into a block 00144 // with a single successor if the block has many other predecessors. This can 00145 // cause an N^2 explosion in CFG edges (and PHI node entries), as seen in 00146 // cases that have a large number of indirect gotos. 00147 unsigned NumSuccs = DTI->getNumSuccessors(); 00148 if (NumSuccs > 8) { 00149 unsigned TooMany = 128; 00150 if (NumSuccs >= TooMany) return false; 00151 TooMany = TooMany/NumSuccs; 00152 for (; PI != PE; ++PI) 00153 if (TooMany-- == 0) return false; 00154 } 00155 00156 // If this unconditional branch is a fall-through, be careful about 00157 // tail duplicating it. In particular, we don't want to taildup it if the 00158 // original block will still be there after taildup is completed: doing so 00159 // would eliminate the fall-through, requiring unconditional branches. 00160 Function::iterator DestI = Dest; 00161 if (&*--DestI == BI->getParent()) { 00162 // The uncond branch is a fall-through. Tail duplication of the block is 00163 // will eliminate the fall-through-ness and end up cloning the terminator 00164 // at the end of the Dest block. Since the original Dest block will 00165 // continue to exist, this means that one or the other will not be able to 00166 // fall through. One typical example that this helps with is code like: 00167 // if (a) 00168 // foo(); 00169 // if (b) 00170 // foo(); 00171 // Cloning the 'if b' block into the end of the first foo block is messy. 00172 00173 // The messy case is when the fall-through block falls through to other 00174 // blocks. This is what we would be preventing if we cloned the block. 00175 DestI = Dest; 00176 if (++DestI != Dest->getParent()->end()) { 00177 BasicBlock *DestSucc = DestI; 00178 // If any of Dest's successors are fall-throughs, don't do this xform. 00179 for (succ_iterator SI = succ_begin(Dest), SE = succ_end(Dest); 00180 SI != SE; ++SI) 00181 if (*SI == DestSucc) 00182 return false; 00183 } 00184 } 00185 00186 // Finally, check that we haven't redirected to this target block earlier; 00187 // there are cases where we loop forever if we don't check this (PR 2323). 00188 if (!CycleDetector.insert(Dest)) 00189 return false; 00190 00191 return true; 00192 } 00193 00194 /// FindObviousSharedDomOf - We know there is a branch from SrcBlock to 00195 /// DestBlock, and that SrcBlock is not the only predecessor of DstBlock. If we 00196 /// can find a predecessor of SrcBlock that is a dominator of both SrcBlock and 00197 /// DstBlock, return it. 00198 static BasicBlock *FindObviousSharedDomOf(BasicBlock *SrcBlock, 00199 BasicBlock *DstBlock) { 00200 // SrcBlock must have a single predecessor. 00201 pred_iterator PI = pred_begin(SrcBlock), PE = pred_end(SrcBlock); 00202 if (PI == PE || ++PI != PE) return 0; 00203 00204 BasicBlock *SrcPred = *pred_begin(SrcBlock); 00205 00206 // Look at the predecessors of DstBlock. One of them will be SrcBlock. If 00207 // there is only one other pred, get it, otherwise we can't handle it. 00208 PI = pred_begin(DstBlock); PE = pred_end(DstBlock); 00209 BasicBlock *DstOtherPred = 0; 00210 if (*PI == SrcBlock) { 00211 if (++PI == PE) return 0; 00212 DstOtherPred = *PI; 00213 if (++PI != PE) return 0; 00214 } else { 00215 DstOtherPred = *PI; 00216 if (++PI == PE || *PI != SrcBlock || ++PI != PE) return 0; 00217 } 00218 00219 // We can handle two situations here: "if then" and "if then else" blocks. An 00220 // 'if then' situation is just where DstOtherPred == SrcPred. 00221 if (DstOtherPred == SrcPred) 00222 return SrcPred; 00223 00224 // Check to see if we have an "if then else" situation, which means that 00225 // DstOtherPred will have a single predecessor and it will be SrcPred. 00226 PI = pred_begin(DstOtherPred); PE = pred_end(DstOtherPred); 00227 if (PI != PE && *PI == SrcPred) { 00228 if (++PI != PE) return 0; // Not a single pred. 00229 return SrcPred; // Otherwise, it's an "if then" situation. Return the if. 00230 } 00231 00232 // Otherwise, this is something we can't handle. 00233 return 0; 00234 } 00235 00236 00237 /// eliminateUnconditionalBranch - Clone the instructions from the destination 00238 /// block into the source block, eliminating the specified unconditional branch. 00239 /// If the destination block defines values used by successors of the dest 00240 /// block, we may need to insert PHI nodes. 00241 /// 00242 void TailDup::eliminateUnconditionalBranch(BranchInst *Branch) { 00243 BasicBlock *SourceBlock = Branch->getParent(); 00244 BasicBlock *DestBlock = Branch->getSuccessor(0); 00245 assert(SourceBlock != DestBlock && "Our predicate is broken!"); 00246 00247 DEBUG(errs() << "TailDuplication[" << SourceBlock->getParent()->getName() 00248 << "]: Eliminating branch: " << *Branch); 00249 00250 // See if we can avoid duplicating code by moving it up to a dominator of both 00251 // blocks. 00252 if (BasicBlock *DomBlock = FindObviousSharedDomOf(SourceBlock, DestBlock)) { 00253 DEBUG(errs() << "Found shared dominator: " << DomBlock->getName() << "\n"); 00254 00255 // If there are non-phi instructions in DestBlock that have no operands 00256 // defined in DestBlock, and if the instruction has no side effects, we can 00257 // move the instruction to DomBlock instead of duplicating it. 00258 BasicBlock::iterator BBI = DestBlock->getFirstNonPHI(); 00259 while (!isa<TerminatorInst>(BBI)) { 00260 Instruction *I = BBI++; 00261 00262 bool CanHoist = I->isSafeToSpeculativelyExecute() && 00263 !I->mayReadFromMemory(); 00264 if (CanHoist) { 00265 for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) 00266 if (Instruction *OpI = dyn_cast<Instruction>(I->getOperand(op))) 00267 if (OpI->getParent() == DestBlock || 00268 (isa<InvokeInst>(OpI) && OpI->getParent() == DomBlock)) { 00269 CanHoist = false; 00270 break; 00271 } 00272 if (CanHoist) { 00273 // Remove from DestBlock, move right before the term in DomBlock. 00274 DestBlock->getInstList().remove(I); 00275 DomBlock->getInstList().insert(DomBlock->getTerminator(), I); 00276 DOUT << "Hoisted: " << *I; 00277 } 00278 } 00279 } 00280 } 00281 00282 // Tail duplication can not update SSA properties correctly if the values 00283 // defined in the duplicated tail are used outside of the tail itself. For 00284 // this reason, we spill all values that are used outside of the tail to the 00285 // stack. 00286 for (BasicBlock::iterator I = DestBlock->begin(); I != DestBlock->end(); ++I) 00287 if (I->isUsedOutsideOfBlock(DestBlock)) { 00288 // We found a use outside of the tail. Create a new stack slot to 00289 // break this inter-block usage pattern. 00290 DemoteRegToStack(*I); 00291 } 00292 00293 // We are going to have to map operands from the original block B to the new 00294 // copy of the block B'. If there are PHI nodes in the DestBlock, these PHI 00295 // nodes also define part of this mapping. Loop over these PHI nodes, adding 00296 // them to our mapping. 00297 // 00298 std::map<Value*, Value*> ValueMapping; 00299 00300 BasicBlock::iterator BI = DestBlock->begin(); 00301 bool HadPHINodes = isa<PHINode>(BI); 00302 for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI) 00303 ValueMapping[PN] = PN->getIncomingValueForBlock(SourceBlock); 00304 00305 // Clone the non-phi instructions of the dest block into the source block, 00306 // keeping track of the mapping... 00307 // 00308 for (; BI != DestBlock->end(); ++BI) { 00309 Instruction *New = BI->clone(BI->getContext()); 00310 New->setName(BI->getName()); 00311 SourceBlock->getInstList().push_back(New); 00312 ValueMapping[BI] = New; 00313 } 00314 00315 // Now that we have built the mapping information and cloned all of the 00316 // instructions (giving us a new terminator, among other things), walk the new 00317 // instructions, rewriting references of old instructions to use new 00318 // instructions. 00319 // 00320 BI = Branch; ++BI; // Get an iterator to the first new instruction 00321 for (; BI != SourceBlock->end(); ++BI) 00322 for (unsigned i = 0, e = BI->getNumOperands(); i != e; ++i) { 00323 std::map<Value*, Value*>::const_iterator I = 00324 ValueMapping.find(BI->getOperand(i)); 00325 if (I != ValueMapping.end()) 00326 BI->setOperand(i, I->second); 00327 } 00328 00329 // Next we check to see if any of the successors of DestBlock had PHI nodes. 00330 // If so, we need to add entries to the PHI nodes for SourceBlock now. 00331 for (succ_iterator SI = succ_begin(DestBlock), SE = succ_end(DestBlock); 00332 SI != SE; ++SI) { 00333 BasicBlock *Succ = *SI; 00334 for (BasicBlock::iterator PNI = Succ->begin(); isa<PHINode>(PNI); ++PNI) { 00335 PHINode *PN = cast<PHINode>(PNI); 00336 // Ok, we have a PHI node. Figure out what the incoming value was for the 00337 // DestBlock. 00338 Value *IV = PN->getIncomingValueForBlock(DestBlock); 00339 00340 // Remap the value if necessary... 00341 std::map<Value*, Value*>::const_iterator I = ValueMapping.find(IV); 00342 if (I != ValueMapping.end()) 00343 IV = I->second; 00344 PN->addIncoming(IV, SourceBlock); 00345 } 00346 } 00347 00348 // Next, remove the old branch instruction, and any PHI node entries that we 00349 // had. 00350 BI = Branch; ++BI; // Get an iterator to the first new instruction 00351 DestBlock->removePredecessor(SourceBlock); // Remove entries in PHI nodes... 00352 SourceBlock->getInstList().erase(Branch); // Destroy the uncond branch... 00353 00354 // Final step: now that we have finished everything up, walk the cloned 00355 // instructions one last time, constant propagating and DCE'ing them, because 00356 // they may not be needed anymore. 00357 // 00358 if (HadPHINodes) { 00359 while (BI != SourceBlock->end()) { 00360 Instruction *Inst = BI++; 00361 if (isInstructionTriviallyDead(Inst)) 00362 Inst->eraseFromParent(); 00363 else if (Constant *C = ConstantFoldInstruction(Inst, 00364 Inst->getContext())) { 00365 Inst->replaceAllUsesWith(C); 00366 Inst->eraseFromParent(); 00367 } 00368 } 00369 } 00370 00371 ++NumEliminated; // We just killed a branch! 00372 }