diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/Target/README.txt | 16 | ||||
| -rw-r--r-- | lib/Transforms/Scalar/TailRecursionElimination.cpp | 13 |
2 files changed, 11 insertions, 18 deletions
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) |