LLVM API Documentation

TailDuplication.cpp

Go to the documentation of this file.
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 }