//===- TailDuplication.cpp - Simplify CFG through tail duplication --------===//
-//
+//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and 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
#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/Support/ValueHolder.h"
#include "llvm/Transforms/Utils/Local.h"
-#include "Support/Debug.h"
-#include "Support/Statistic.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/ADT/Statistic.h"
using namespace llvm;
namespace {
+ cl::opt<unsigned>
+ Threshold("taildup-threshold", cl::desc("Max block size to tail duplicate"),
+ cl::init(6), cl::Hidden);
Statistic<> NumEliminated("tailduplicate",
"Number of unconditional branches eliminated");
Statistic<> NumPHINodes("tailduplicate", "Number of phi nodes inserted");
}
// Public interface to the Tail Duplication pass
-Pass *llvm::createTailDuplicationPass() { return new TailDup(); }
+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.
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...
+ for (unsigned Size = 0; I != Dest->end(); ++I) {
+ if (Size == Threshold) return false; // The block is too large.
+ // 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.
- if (DTI->getNumSuccessors() > 8)
- if (std::distance(PI, PE) * DTI->getNumSuccessors() > 128)
- return false;
+ 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;
+ }
- return true;
+ 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;
}
DEBUG(std::cerr << "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)) {
+ DEBUG(std::cerr << "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);
+ DEBUG(std::cerr << "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
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;
projects / oota-llvm.git / blobdiff