Improve tail call elimination to handle the switch statement.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86403 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/lib/Target/README.txt b/lib/Target/README.txt
index 7018b61f68f4229da27c7e47c48d59fff435fafa..dce29b82755ac631c507f4421090b6ec354a4fd3 100644 (file)
--- a/lib/Target/README.txt
+++ b/lib/Target/README.txt
@@ -406,22 +406,6 @@ return:            ; preds = %then.1, %else.0, %then.0
 
 //===---------------------------------------------------------------------===//
 
-Tail recursion elimination is not transforming this function, because it is
-returning n, which fails the isDynamicConstant check in the accumulator 
-recursion checks.
-
-long long fib(const long long n) {
-  switch(n) {
-    case 0:
-    case 1:
-      return n;
-    default:
-      return fib(n-1) + fib(n-2);
-  }
-}
-
-//===---------------------------------------------------------------------===//
-
 Tail recursion elimination should handle:
 
 int pow2m1(int n) {

diff --git a/lib/Transforms/Scalar/TailRecursionElimination.cpp b/lib/Transforms/Scalar/TailRecursionElimination.cpp
index e05991373a8df6484a736dd9dde7c7121502859b..4119cb9db41c5279b34529469f1aee232df7b56c 100644 (file)
--- a/lib/Transforms/Scalar/TailRecursionElimination.cpp
+++ b/lib/Transforms/Scalar/TailRecursionElimination.cpp
@@ -234,7 +234,7 @@ bool TailCallElim::CanMoveAboveCall(Instruction *I, CallInst *CI) {
 // We currently handle static constants and arguments that are not modified as
 // part of the recursion.
 //
-static bool isDynamicConstant(Value *V, CallInst *CI) {
+static bool isDynamicConstant(Value *V, CallInst *CI, ReturnInst *RI) {
   if (isa<Constant>(V)) return true; // Static constants are always dyn consts
 
   // Check to see if this is an immutable argument, if so, the value
@@ -252,6 +252,15 @@ static bool isDynamicConstant(Value *V, CallInst *CI) {
     if (CI->getOperand(ArgNo+1) == Arg)
       return true;
   }
+
+  // Switch cases are always constant integers. If the value is being switched
+  // on and the return is only reachable from one of its cases, it's
+  // effectively constant.
+  if (BasicBlock *UniquePred = RI->getParent()->getUniquePredecessor())
+    if (SwitchInst *SI = dyn_cast<SwitchInst>(UniquePred->getTerminator()))
+      if (SI->getCondition() == V)
+        return SI->getDefaultDest() != RI->getParent();
+
   // Not a constant or immutable argument, we can't safely transform.
   return false;
 }
@@ -273,7 +282,7 @@ static Value *getCommonReturnValue(ReturnInst *TheRI, CallInst *CI) {
         // evaluatable at the start of the initial invocation of the function,
         // instead of at the end of the evaluation.
         //
-        if (!isDynamicConstant(RetOp, CI))
+        if (!isDynamicConstant(RetOp, CI, RI))
           return 0;
 
         if (ReturnedValue && RetOp != ReturnedValue)

diff --git a/test/Transforms/TailCallElim/switch.ll b/test/Transforms/TailCallElim/switch.ll
new file mode 100644 (file)
index 0000000..3388431
--- /dev/null
+++ b/test/Transforms/TailCallElim/switch.ll
@@ -0,0 +1,34 @@
+; RUN: opt %s -tailcallelim -S | FileCheck %s
+
+define i64 @fib(i64 %n) nounwind readnone {
+; CHECK: @fib
+entry:
+; CHECK: tailrecurse:
+; CHECK: %accumulator.tr = phi i64 [ %n, %entry ], [ %3, %bb1 ]
+; CHECK: %n.tr = phi i64 [ %n, %entry ], [ %2, %bb1 ]
+  switch i64 %n, label %bb1 [
+; CHECK: switch i64 %n.tr, label %bb1 [
+    i64 0, label %bb2
+    i64 1, label %bb2
+  ]
+
+bb1:
+; CHECK: bb1:
+  %0 = add i64 %n, -1
+; CHECK: %0 = add i64 %n.tr, -1
+  %1 = tail call i64 @fib(i64 %0) nounwind
+; CHECK: %1 = tail call i64 @fib(i64 %0)
+  %2 = add i64 %n, -2
+; CHECK: %2 = add i64 %n.tr, -2
+  %3 = tail call i64 @fib(i64 %2) nounwind
+; CHECK-NOT: tail call i64 @fib
+  %4 = add nsw i64 %3, %1
+; CHECK: add nsw i64 %accumulator.tr, %1
+  ret i64 %4
+; CHECK: br label %tailrecurse
+
+bb2:
+; CHECK: bb2:
+  ret i64 %n
+; CHECK: ret i64 %accumulator.tr
+}