From ded7c4a4c0f0df94bd7abfc98a6e0123c5849efe Mon Sep 17 00:00:00 2001
From: Nick Lewycky <nicholas@mxc.ca>
Date: Sat, 7 Nov 2009 21:10:15 +0000
Subject: [PATCH] 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
---
 lib/Target/README.txt                              | 16 ----------
 lib/Transforms/Scalar/TailRecursionElimination.cpp | 13 +++++++--
 test/Transforms/TailCallElim/switch.ll             | 34 ++++++++++++++++++++++
 3 files changed, 45 insertions(+), 18 deletions(-)
 create mode 100644 test/Transforms/TailCallElim/switch.ll

diff --git a/lib/Target/README.txt b/lib/Target/README.txt
index 7018b61f68..dce29b8275 100644
--- 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 e05991373a..4119cb9db4 100644
--- 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
index 0000000000..33884318b0
--- /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
+}
-- 
2.11.4.GIT