Remove attribution from file headers, per discussion on llvmdev.

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

diff --git a/lib/Transforms/Scalar/TailRecursionElimination.cpp b/lib/Transforms/Scalar/TailRecursionElimination.cpp
index 2b67b439cb323d21176b39e75925f3e6d1bc5639..5849254374d2ec39ed14bfeea7693d534c5eda2f 100644 (file)
--- a/lib/Transforms/Scalar/TailRecursionElimination.cpp
+++ b/lib/Transforms/Scalar/TailRecursionElimination.cpp
@@ -2,8 +2,8 @@
 //
 //                     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 file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
@@ -50,6 +50,7 @@
 //
 //===----------------------------------------------------------------------===//
 
+#define DEBUG_TYPE "tailcallelim"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Constants.h"
 #include "llvm/DerivedTypes.h"
@@ -58,13 +59,17 @@
 #include "llvm/Pass.h"
 #include "llvm/Support/CFG.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Support/Compiler.h"
 using namespace llvm;
 
+STATISTIC(NumEliminated, "Number of tail calls removed");
+STATISTIC(NumAccumAdded, "Number of accumulators introduced");
+
 namespace {
-  Statistic<> NumEliminated("tailcallelim", "Number of tail calls removed");
-  Statistic<> NumAccumAdded("tailcallelim","Number of accumulators introduced");
+  struct VISIBILITY_HIDDEN TailCallElim : public FunctionPass {
+    static char ID; // Pass identification, replacement for typeid
+    TailCallElim() : FunctionPass((intptr_t)&ID) {}
 
-  struct TailCallElim : public FunctionPass {
     virtual bool runOnFunction(Function &F);
 
   private:
@@ -75,7 +80,8 @@ namespace {
     bool CanMoveAboveCall(Instruction *I, CallInst *CI);
     Value *CanTransformAccumulatorRecursion(Instruction *I, CallInst *CI);
   };
-  RegisterOpt<TailCallElim> X("tailcallelim", "Tail Call Elimination");
+  char TailCallElim::ID = 0;
+  RegisterPass<TailCallElim> X("tailcallelim", "Tail Call Elimination");
 }
 
 // Public interface to the TailCallElimination pass
@@ -106,7 +112,7 @@ static bool CheckForEscapingAllocas(BasicBlock *BB,
       // If this alloca is in the body of the function, or if it is a variable
       // sized allocation, we cannot tail call eliminate calls marked 'tail'
       // with this mechanism.
-      if (BB != &BB->getParent()->front() ||
+      if (BB != &BB->getParent()->getEntryBlock() ||
           !isa<ConstantInt>(AI->getArraySize()))
         CannotTCETailMarkedCall = true;
     }
@@ -140,6 +146,14 @@ bool TailCallElim::runOnFunction(Function &F) {
     FunctionContainsEscapingAllocas |=
       CheckForEscapingAllocas(BB, CannotTCETailMarkedCall);
   }
+  
+  /// FIXME: The code generator produces really bad code when an 'escaping
+  /// alloca' is changed from being a static alloca to being a dynamic alloca.
+  /// Until this is resolved, disable this transformation if that would ever
+  /// happen.  This bug is PR962.
+  if (FunctionContainsEscapingAllocas)
+    return false;
+  
 
   // Second pass, change any tail calls to loops.
   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
@@ -153,7 +167,6 @@ bool TailCallElim::runOnFunction(Function &F) {
   // occurs when a function passes an argument straight through to its tail
   // call.
   if (!ArgumentPHIs.empty()) {
-    unsigned NumIncoming = ArgumentPHIs[0]->getNumIncomingValues();
     for (unsigned i = 0, e = ArgumentPHIs.size(); i != e; ++i) {
       PHINode *PN = ArgumentPHIs[i];
 
@@ -289,6 +302,15 @@ bool TailCallElim::ProcessReturningBlock(ReturnInst *Ret, BasicBlock *&OldEntry,
 
   if (&BB->front() == Ret) // Make sure there is something before the ret...
     return false;
+  
+  // If the return is in the entry block, then making this transformation would
+  // turn infinite recursion into an infinite loop.  This transformation is ok
+  // in theory, but breaks some code like:
+  //   double fabs(double f) { return __builtin_fabs(f); } // a 'fabs' call
+  // disable this xform in this case, because the code generator will lower the
+  // call to fabs into inline code.
+  if (BB == &F->getEntryBlock())
+    return false;
 
   // Scan backwards from the return, checking to see if there is a tail call in
   // this block.  If so, set CI to it.
@@ -342,6 +364,7 @@ bool TailCallElim::ProcessReturningBlock(ReturnInst *Ret, BasicBlock *&OldEntry,
   // constant, return the value returned by the tail call, or that are being
   // accumulator recursion variable eliminated.
   if (Ret->getNumOperands() != 0 && Ret->getReturnValue() != CI &&
+      !isa<UndefValue>(Ret->getReturnValue()) &&
       AccumulatorRecursionEliminationInitVal == 0 &&
       !getCommonReturnValue(Ret, CI))
     return false;
@@ -350,8 +373,9 @@ bool TailCallElim::ProcessReturningBlock(ReturnInst *Ret, BasicBlock *&OldEntry,
   // create the new entry block, allowing us to branch back to the old entry.
   if (OldEntry == 0) {
     OldEntry = &F->getEntryBlock();
-    std::string OldName = OldEntry->getName(); OldEntry->setName("tailrecurse");
-    BasicBlock *NewEntry = new BasicBlock(OldName, F, OldEntry);
+    BasicBlock *NewEntry = new BasicBlock("", F, OldEntry);
+    NewEntry->takeName(OldEntry);
+    OldEntry->setName("tailrecurse");
     new BranchInst(OldEntry, NewEntry);
 
     // If this tail call is marked 'tail' and if there are any allocas in the
@@ -363,7 +387,7 @@ bool TailCallElim::ProcessReturningBlock(ReturnInst *Ret, BasicBlock *&OldEntry,
              NEBI = NewEntry->begin(); OEBI != E; )
         if (AllocaInst *AI = dyn_cast<AllocaInst>(OEBI++))
           if (isa<ConstantInt>(AI->getArraySize()))
-            NewEntry->getInstList().splice(NEBI, OldEntry->getInstList(), AI);
+            AI->moveBefore(NEBI);
 
     // Now that we have created a new block, which jumps to the entry
     // block, insert a PHI node for each argument of the function.