//===- TailDuplication.cpp - Simplify CFG through tail duplication --------===//
//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
// This pass performs a limited form of tail duplication, intended to simplify
// CFGs by removing some unconditional branches. This pass is necessary to
// straighten out loops created by the C front-end, but also is capable of
//
//===----------------------------------------------------------------------===//
+#define DEBUG_TYPE "tailduplicate"
#include "llvm/Transforms/Scalar.h"
+#include "llvm/Constant.h"
#include "llvm/Function.h"
-#include "llvm/iPHINode.h"
-#include "llvm/iTerminators.h"
+#include "llvm/Instructions.h"
+#include "llvm/IntrinsicInst.h"
#include "llvm/Pass.h"
#include "llvm/Type.h"
#include "llvm/Support/CFG.h"
#include "llvm/Transforms/Utils/Local.h"
-#include "Support/Statistic.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Compiler.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include <map>
+using namespace llvm;
-namespace {
- Statistic<> NumEliminated("tailduplicate",
- "Number of unconditional branches eliminated");
- Statistic<> NumPHINodes("tailduplicate", "Number of phi nodes inserted");
+STATISTIC(NumEliminated, "Number of unconditional branches eliminated");
- class TailDup : public FunctionPass {
+static cl::opt<unsigned>
+Threshold("taildup-threshold", cl::desc("Max block size to tail duplicate"),
+ cl::init(6), cl::Hidden);
+
+namespace {
+ class VISIBILITY_HIDDEN TailDup : public FunctionPass {
bool runOnFunction(Function &F);
+ public:
+ static char ID; // Pass identification, replacement for typeid
+ TailDup() : FunctionPass((intptr_t)&ID) {}
+
private:
inline bool shouldEliminateUnconditionalBranch(TerminatorInst *TI);
inline void eliminateUnconditionalBranch(BranchInst *BI);
- inline void InsertPHINodesIfNecessary(Instruction *OrigInst, Value *NewInst,
- BasicBlock *NewBlock);
- inline Value *GetValueInBlock(BasicBlock *BB, Value *OrigVal,
- std::map<BasicBlock*, Value*> &ValueMap,
- std::map<BasicBlock*, Value*> &OutValueMap);
- inline Value *GetValueOutBlock(BasicBlock *BB, Value *OrigVal,
- std::map<BasicBlock*, Value*> &ValueMap,
- std::map<BasicBlock*, Value*> &OutValueMap);
+ SmallPtrSet<BasicBlock*, 4> CycleDetector;
};
- RegisterOpt<TailDup> X("tailduplicate", "Tail Duplication");
}
-Pass *createTailDuplicationPass() { return new TailDup(); }
+char TailDup::ID = 0;
+static RegisterPass<TailDup> X("tailduplicate", "Tail Duplication");
+
+// Public interface to the Tail Duplication pass
+FunctionPass *llvm::createTailDuplicationPass() { return new TailDup(); }
/// runOnFunction - Top level algorithm - Loop over each unconditional branch in
-/// the function, eliminating it if it looks attractive enough.
-///
+/// the function, eliminating it if it looks attractive enough. CycleDetector
+/// prevents infinite loops by checking that we aren't redirecting a branch to
+/// a place it already pointed to earlier; see PR 2323.
bool TailDup::runOnFunction(Function &F) {
bool Changed = false;
- for (Function::iterator I = F.begin(), E = F.end(); I != E; )
+ CycleDetector.clear();
+ for (Function::iterator I = F.begin(), E = F.end(); I != E; ) {
if (shouldEliminateUnconditionalBranch(I->getTerminator())) {
eliminateUnconditionalBranch(cast<BranchInst>(I->getTerminator()));
Changed = true;
} else {
++I;
+ CycleDetector.clear();
}
+ }
return Changed;
}
BasicBlock *Dest = BI->getSuccessor(0);
if (Dest == BI->getParent()) return false; // Do not loop infinitely!
- // Do not bother working on dead blocks...
- pred_iterator PI = pred_begin(Dest), PE = pred_end(Dest);
- if (PI == PE && Dest != Dest->getParent()->begin())
- return false; // It's just a dead block, ignore it...
+ // Do not inline a block if we will just get another branch to the same block!
+ TerminatorInst *DTI = Dest->getTerminator();
+ if (BranchInst *DBI = dyn_cast<BranchInst>(DTI))
+ if (DBI->isUnconditional() && DBI->getSuccessor(0) == Dest)
+ return false; // Do not loop infinitely!
- // Also, do not bother with blocks with only a single predecessor: simplify
+ // FIXME: DemoteRegToStack cannot yet demote invoke instructions to the stack,
+ // because doing so would require breaking critical edges. This should be
+ // fixed eventually.
+ if (!DTI->use_empty())
+ return false;
+
+ // Do not bother with blocks with only a single predecessor: simplify
// CFG will fold these two blocks together!
+ pred_iterator PI = pred_begin(Dest), PE = pred_end(Dest);
++PI;
if (PI == PE) return false; // Exactly one predecessor!
BasicBlock::iterator I = Dest->begin();
while (isa<PHINode>(*I)) ++I;
- for (unsigned Size = 0; I != Dest->end(); ++Size, ++I)
- if (Size == 6) return false; // The block is too large...
- return true;
+ for (unsigned Size = 0; I != Dest->end(); ++I) {
+ if (Size == Threshold) return false; // The block is too large.
+
+ // Don't tail duplicate call instructions. They are very large compared to
+ // other instructions.
+ if (isa<CallInst>(I) || isa<InvokeInst>(I)) return false;
+
+ // Only count instructions that are not debugger intrinsics.
+ if (!isa<DbgInfoIntrinsic>(I)) ++Size;
+ }
+
+ // Do not tail duplicate a block that has thousands of successors into a block
+ // with a single successor if the block has many other predecessors. This can
+ // cause an N^2 explosion in CFG edges (and PHI node entries), as seen in
+ // cases that have a large number of indirect gotos.
+ unsigned NumSuccs = DTI->getNumSuccessors();
+ if (NumSuccs > 8) {
+ unsigned TooMany = 128;
+ if (NumSuccs >= TooMany) return false;
+ TooMany = TooMany/NumSuccs;
+ for (; PI != PE; ++PI)
+ if (TooMany-- == 0) return false;
+ }
+
+ // If this unconditional branch is a fall-through, be careful about
+ // tail duplicating it. In particular, we don't want to taildup it if the
+ // original block will still be there after taildup is completed: doing so
+ // would eliminate the fall-through, requiring unconditional branches.
+ Function::iterator DestI = Dest;
+ if (&*--DestI == BI->getParent()) {
+ // The uncond branch is a fall-through. Tail duplication of the block is
+ // will eliminate the fall-through-ness and end up cloning the terminator
+ // at the end of the Dest block. Since the original Dest block will
+ // continue to exist, this means that one or the other will not be able to
+ // fall through. One typical example that this helps with is code like:
+ // if (a)
+ // foo();
+ // if (b)
+ // foo();
+ // Cloning the 'if b' block into the end of the first foo block is messy.
+
+ // The messy case is when the fall-through block falls through to other
+ // blocks. This is what we would be preventing if we cloned the block.
+ DestI = Dest;
+ if (++DestI != Dest->getParent()->end()) {
+ BasicBlock *DestSucc = DestI;
+ // If any of Dest's successors are fall-throughs, don't do this xform.
+ for (succ_iterator SI = succ_begin(Dest), SE = succ_end(Dest);
+ SI != SE; ++SI)
+ if (*SI == DestSucc)
+ return false;
+ }
+ }
+
+ // Finally, check that we haven't redirected to this target block earlier;
+ // there are cases where we loop forever if we don't check this (PR 2323).
+ if (!CycleDetector.insert(Dest))
+ return false;
+
+ return true;
+}
+
+/// FindObviousSharedDomOf - We know there is a branch from SrcBlock to
+/// DestBlock, and that SrcBlock is not the only predecessor of DstBlock. If we
+/// can find a predecessor of SrcBlock that is a dominator of both SrcBlock and
+/// DstBlock, return it.
+static BasicBlock *FindObviousSharedDomOf(BasicBlock *SrcBlock,
+ BasicBlock *DstBlock) {
+ // SrcBlock must have a single predecessor.
+ pred_iterator PI = pred_begin(SrcBlock), PE = pred_end(SrcBlock);
+ if (PI == PE || ++PI != PE) return 0;
+
+ BasicBlock *SrcPred = *pred_begin(SrcBlock);
+
+ // Look at the predecessors of DstBlock. One of them will be SrcBlock. If
+ // there is only one other pred, get it, otherwise we can't handle it.
+ PI = pred_begin(DstBlock); PE = pred_end(DstBlock);
+ BasicBlock *DstOtherPred = 0;
+ if (*PI == SrcBlock) {
+ if (++PI == PE) return 0;
+ DstOtherPred = *PI;
+ if (++PI != PE) return 0;
+ } else {
+ DstOtherPred = *PI;
+ if (++PI == PE || *PI != SrcBlock || ++PI != PE) return 0;
+ }
+
+ // We can handle two situations here: "if then" and "if then else" blocks. An
+ // 'if then' situation is just where DstOtherPred == SrcPred.
+ if (DstOtherPred == SrcPred)
+ return SrcPred;
+
+ // Check to see if we have an "if then else" situation, which means that
+ // DstOtherPred will have a single predecessor and it will be SrcPred.
+ PI = pred_begin(DstOtherPred); PE = pred_end(DstOtherPred);
+ if (PI != PE && *PI == SrcPred) {
+ if (++PI != PE) return 0; // Not a single pred.
+ return SrcPred; // Otherwise, it's an "if then" situation. Return the if.
+ }
+
+ // Otherwise, this is something we can't handle.
+ return 0;
}
BasicBlock *DestBlock = Branch->getSuccessor(0);
assert(SourceBlock != DestBlock && "Our predicate is broken!");
- DEBUG(std::cerr << "TailDuplication[" << SourceBlock->getParent()->getName()
- << "]: Eliminating branch: " << *Branch);
+ DOUT << "TailDuplication[" << SourceBlock->getParent()->getName()
+ << "]: Eliminating branch: " << *Branch;
+
+ // See if we can avoid duplicating code by moving it up to a dominator of both
+ // blocks.
+ if (BasicBlock *DomBlock = FindObviousSharedDomOf(SourceBlock, DestBlock)) {
+ DOUT << "Found shared dominator: " << DomBlock->getName() << "\n";
+
+ // If there are non-phi instructions in DestBlock that have no operands
+ // defined in DestBlock, and if the instruction has no side effects, we can
+ // move the instruction to DomBlock instead of duplicating it.
+ BasicBlock::iterator BBI = DestBlock->begin();
+ while (isa<PHINode>(BBI)) ++BBI;
+ while (!isa<TerminatorInst>(BBI)) {
+ Instruction *I = BBI++;
+
+ bool CanHoist = !I->isTrapping() && !I->mayWriteToMemory();
+ if (CanHoist) {
+ for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op)
+ if (Instruction *OpI = dyn_cast<Instruction>(I->getOperand(op)))
+ if (OpI->getParent() == DestBlock ||
+ (isa<InvokeInst>(OpI) && OpI->getParent() == DomBlock)) {
+ CanHoist = false;
+ break;
+ }
+ if (CanHoist) {
+ // Remove from DestBlock, move right before the term in DomBlock.
+ DestBlock->getInstList().remove(I);
+ DomBlock->getInstList().insert(DomBlock->getTerminator(), I);
+ DOUT << "Hoisted: " << *I;
+ }
+ }
+ }
+ }
+
+ // Tail duplication can not update SSA properties correctly if the values
+ // defined in the duplicated tail are used outside of the tail itself. For
+ // this reason, we spill all values that are used outside of the tail to the
+ // stack.
+ for (BasicBlock::iterator I = DestBlock->begin(); I != DestBlock->end(); ++I)
+ if (I->isUsedOutsideOfBlock(DestBlock)) {
+ // We found a use outside of the tail. Create a new stack slot to
+ // break this inter-block usage pattern.
+ DemoteRegToStack(*I);
+ }
// We are going to have to map operands from the original block B to the new
// copy of the block B'. If there are PHI nodes in the DestBlock, these PHI
for (succ_iterator SI = succ_begin(DestBlock), SE = succ_end(DestBlock);
SI != SE; ++SI) {
BasicBlock *Succ = *SI;
- for (BasicBlock::iterator PNI = Succ->begin();
- PHINode *PN = dyn_cast<PHINode>(PNI); ++PNI) {
+ for (BasicBlock::iterator PNI = Succ->begin(); isa<PHINode>(PNI); ++PNI) {
+ PHINode *PN = cast<PHINode>(PNI);
// Ok, we have a PHI node. Figure out what the incoming value was for the
// DestBlock.
Value *IV = PN->getIncomingValueForBlock(DestBlock);
-
+
// Remap the value if necessary...
if (Value *MappedIV = ValueMapping[IV])
IV = MappedIV;
PN->addIncoming(IV, SourceBlock);
}
}
-
- // Now that all of the instructions are correctly copied into the SourceBlock,
- // we have one more minor problem: the successors of the original DestBB may
- // use the values computed in DestBB either directly (if DestBB dominated the
- // block), or through a PHI node. In either case, we need to insert PHI nodes
- // into any successors of DestBB (which are now our successors) for each value
- // that is computed in DestBB, but is used outside of it. All of these uses
- // we have to rewrite with the new PHI node.
- //
- if (succ_begin(SourceBlock) != succ_end(SourceBlock)) // Avoid wasting time...
- for (BI = DestBlock->begin(); BI != DestBlock->end(); ++BI)
- if (BI->getType() != Type::VoidTy)
- InsertPHINodesIfNecessary(BI, ValueMapping[BI], SourceBlock);
+
+ // Next, remove the old branch instruction, and any PHI node entries that we
+ // had.
+ BI = Branch; ++BI; // Get an iterator to the first new instruction
+ DestBlock->removePredecessor(SourceBlock); // Remove entries in PHI nodes...
+ SourceBlock->getInstList().erase(Branch); // Destroy the uncond branch...
// Final step: now that we have finished everything up, walk the cloned
// instructions one last time, constant propagating and DCE'ing them, because
// they may not be needed anymore.
//
- BI = Branch; ++BI; // Get an iterator to the first new instruction
if (HadPHINodes)
while (BI != SourceBlock->end())
if (!dceInstruction(BI) && !doConstantPropagation(BI))
++BI;
- DestBlock->removePredecessor(SourceBlock); // Remove entries in PHI nodes...
- SourceBlock->getInstList().erase(Branch); // Destroy the uncond branch...
-
++NumEliminated; // We just killed a branch!
}
-
-/// InsertPHINodesIfNecessary - So at this point, we cloned the OrigInst
-/// instruction into the NewBlock with the value of NewInst. If OrigInst was
-/// used outside of its defining basic block, we need to insert a PHI nodes into
-/// the successors.
-///
-void TailDup::InsertPHINodesIfNecessary(Instruction *OrigInst, Value *NewInst,
- BasicBlock *NewBlock) {
- // Loop over all of the uses of OrigInst, rewriting them to be newly inserted
- // PHI nodes, unless they are in the same basic block as OrigInst.
- BasicBlock *OrigBlock = OrigInst->getParent();
- std::vector<Instruction*> Users;
- Users.reserve(OrigInst->use_size());
- for (Value::use_iterator I = OrigInst->use_begin(), E = OrigInst->use_end();
- I != E; ++I) {
- Instruction *In = cast<Instruction>(*I);
- if (In->getParent() != OrigBlock) // Don't modify uses in the orig block!
- Users.push_back(In);
- }
-
- // The common case is that the instruction is only used within the block that
- // defines it. If we have this case, quick exit.
- //
- if (Users.empty()) return;
-
- // Otherwise, we have a more complex case, handle it now. This requires the
- // construction of a mapping between a basic block and the value to use when
- // in the scope of that basic block. This map will map to the original and
- // new values when in the original or new block, but will map to inserted PHI
- // nodes when in other blocks.
- //
- std::map<BasicBlock*, Value*> ValueMap;
- std::map<BasicBlock*, Value*> OutValueMap; // The outgoing value map
- OutValueMap[OrigBlock] = OrigInst;
- OutValueMap[NewBlock ] = NewInst; // Seed the initial values...
-
- DEBUG(std::cerr << " ** Inserting PHI nodes for " << OrigInst);
- while (!Users.empty()) {
- Instruction *User = Users.back(); Users.pop_back();
-
- if (PHINode *PN = dyn_cast<PHINode>(User)) {
- // PHI nodes must be handled specially here, because their operands are
- // actually defined in predecessor basic blocks, NOT in the block that the
- // PHI node lives in. Note that we have already added entries to PHI nods
- // which are in blocks that are immediate successors of OrigBlock, so
- // don't modify them again.
- for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
- if (PN->getIncomingValue(i) == OrigInst &&
- PN->getIncomingBlock(i) != OrigBlock) {
- Value *V = GetValueOutBlock(PN->getIncomingBlock(i), OrigInst,
- ValueMap, OutValueMap);
- PN->setIncomingValue(i, V);
- }
-
- } else {
- // Any other user of the instruction can just replace any uses with the
- // new value defined in the block it resides in.
- Value *V = GetValueInBlock(User->getParent(), OrigInst, ValueMap,
- OutValueMap);
- User->replaceUsesOfWith(OrigInst, V);
- }
- }
-}
-
-/// GetValueInBlock - This is a recursive method which inserts PHI nodes into
-/// the function until there is a value available in basic block BB.
-///
-Value *TailDup::GetValueInBlock(BasicBlock *BB, Value *OrigVal,
- std::map<BasicBlock*, Value*> &ValueMap,
- std::map<BasicBlock*, Value*> &OutValueMap) {
- Value*& BBVal = ValueMap[BB];
- if (BBVal) return BBVal; // Value already computed for this block?
-
- assert(pred_begin(BB) != pred_end(BB) &&
- "Propagating PHI nodes to unreachable blocks?");
-
- // If there is no value already available in this basic block, we need to
- // either reuse a value from an incoming, dominating, basic block, or we need
- // to create a new PHI node to merge in different incoming values. Because we
- // don't know if we're part of a loop at this point or not, we create a PHI
- // node, even if we will ultimately eliminate it.
- PHINode *PN = new PHINode(OrigVal->getType(), OrigVal->getName()+".pn",
- BB->begin());
- BBVal = PN; // Insert this into the BBVal slot in case of cycles...
-
- Value*& BBOutVal = OutValueMap[BB];
- if (BBOutVal == 0) BBOutVal = PN;
-
- // Now that we have created the PHI node, loop over all of the predecessors of
- // this block, computing an incoming value for the predecessor.
- std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB));
- for (unsigned i = 0, e = Preds.size(); i != e; ++i)
- PN->addIncoming(GetValueOutBlock(Preds[i], OrigVal, ValueMap, OutValueMap),
- Preds[i]);
-
- // The PHI node is complete. In many cases, however the PHI node was
- // ultimately unnecessary: we could have just reused a dominating incoming
- // value. If this is the case, nuke the PHI node and replace the map entry
- // with the dominating value.
- //
- assert(PN->getNumIncomingValues() > 0 && "No predecessors?");
-
- // Check to see if all of the elements in the PHI node are either the PHI node
- // itself or ONE particular value.
- unsigned i = 0;
- Value *ReplVal = PN->getIncomingValue(i);
- for (; ReplVal == PN && i != PN->getNumIncomingValues(); ++i)
- ReplVal = PN->getIncomingValue(i); // Skip values equal to the PN
-
- for (; i != PN->getNumIncomingValues(); ++i)
- if (PN->getIncomingValue(i) != PN && PN->getIncomingValue(i) != ReplVal) {
- ReplVal = 0;
- break;
- }
-
- // Found a value to replace the PHI node with?
- if (ReplVal && ReplVal != PN) {
- PN->replaceAllUsesWith(ReplVal);
- BBVal = ReplVal;
- if (BBOutVal == PN) BBOutVal = ReplVal;
- BB->getInstList().erase(PN); // Erase the PHI node...
- } else {
- ++NumPHINodes;
- }
-
- return BBVal;
-}
-
-Value *TailDup::GetValueOutBlock(BasicBlock *BB, Value *OrigVal,
- std::map<BasicBlock*, Value*> &ValueMap,
- std::map<BasicBlock*, Value*> &OutValueMap) {
- Value*& BBVal = OutValueMap[BB];
- if (BBVal) return BBVal; // Value already computed for this block?
-
- return BBVal = GetValueInBlock(BB, OrigVal, ValueMap, OutValueMap);
-}
projects / oota-llvm.git / blobdiff