Remove incomplete cost analysis.

[oota-llvm.git] / lib / Transforms / Scalar / TailDuplication.cpp

diff --git a/lib/Transforms/Scalar/TailDuplication.cpp b/lib/Transforms/Scalar/TailDuplication.cpp
index f78ce91d6ee0bfea0c6b09dc388d558763470c13..22d8157fc085319fc8be9593cc49cd64d662bd30 100644 (file)
--- a/lib/Transforms/Scalar/TailDuplication.cpp
+++ b/lib/Transforms/Scalar/TailDuplication.cpp
@@ -18,6 +18,7 @@
 //
 //===----------------------------------------------------------------------===//
 
+#define DEBUG_TYPE "tailduplicate"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Constant.h"
 #include "llvm/Function.h"
@@ -28,25 +29,29 @@
 #include "llvm/Support/CFG.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/ADT/Statistic.h"
 using namespace llvm;
 
+STATISTIC(NumEliminated, "Number of unconditional branches eliminated");
+
 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");
-
-  class TailDup : public FunctionPass {
+  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);
   };
-  RegisterOpt<TailDup> X("tailduplicate", "Tail Duplication");
+  char TailDup::ID = 0;
+  RegisterPass<TailDup> X("tailduplicate", "Tail Duplication");
 }
 
 // Public interface to the Tail Duplication pass
@@ -126,6 +131,36 @@ bool TailDup::shouldEliminateUnconditionalBranch(TerminatorInst *TI) {
     for (; PI != PE; ++PI)
       if (TooMany-- == 0) return false;
   }
+  
+  // Finally, 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;
+    }
+  }
 
   return true;
 }
@@ -183,14 +218,13 @@ void TailDup::eliminateUnconditionalBranch(BranchInst *Branch) {
   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)) {
-    DEBUG(std::cerr << "Found shared dominator: " << DomBlock->getName()
-                    << "\n");
+    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
@@ -213,7 +247,7 @@ void TailDup::eliminateUnconditionalBranch(BranchInst *Branch) {
           // 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);
+          DOUT << "Hoisted: " << *I;
         }
       }
     }