From d0d3ccc827de69de3d9f666aa922f5f191219a06 Mon Sep 17 00:00:00 2001 From: Duncan Sands Date: Tue, 13 Jul 2010 15:41:41 +0000 Subject: [PATCH] Handle the case of a tail recursion in which the tail call is followed by a return that returns a constant, while elsewhere in the function another return instruction returns a different constant. This is a special case of accumulator recursion, so just generalize the existing logic a bit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@108241 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/TailRecursionElimination.cpp | 48 ++++++++++++++++------ .../2010-06-26-MultipleReturnValues.ll | 5 ++- 2 files changed, 39 insertions(+), 14 deletions(-) diff --git a/lib/Transforms/Scalar/TailRecursionElimination.cpp b/lib/Transforms/Scalar/TailRecursionElimination.cpp index 7403e3711e7..01c8e5d6fcf 100644 --- a/lib/Transforms/Scalar/TailRecursionElimination.cpp +++ b/lib/Transforms/Scalar/TailRecursionElimination.cpp @@ -373,7 +373,12 @@ bool TailCallElim::ProcessReturningBlock(ReturnInst *Ret, BasicBlock *&OldEntry, // the call instruction that are both associative and commutative, the initial // value for the accumulator is placed in this variable. If this value is set // then we actually perform accumulator recursion elimination instead of - // simple tail recursion elimination. + // simple tail recursion elimination. If the operation is an LLVM instruction + // (eg: "add") then it is recorded in AccumulatorRecursionInstr. If not, then + // we are handling the case when the return instruction returns a constant C + // which is different to the constant returned by other return instructions + // (which is recorded in AccumulatorRecursionEliminationInitVal). This is a + // special case of accumulator recursion, the operation being "return C". Value *AccumulatorRecursionEliminationInitVal = 0; Instruction *AccumulatorRecursionInstr = 0; @@ -404,8 +409,18 @@ bool TailCallElim::ProcessReturningBlock(ReturnInst *Ret, BasicBlock *&OldEntry, if (Ret->getNumOperands() == 1 && Ret->getReturnValue() != CI && !isa(Ret->getReturnValue()) && AccumulatorRecursionEliminationInitVal == 0 && - !getCommonReturnValue(0, CI)) - return false; + !getCommonReturnValue(0, CI)) { + // One case remains that we are able to handle: the current return + // instruction returns a constant, and all other return instructions + // return a different constant. + if (!isDynamicConstant(Ret->getReturnValue(), CI, Ret)) + return false; // Current return instruction does not return a constant. + // Check that all other return instructions return a common constant. If + // so, record it in AccumulatorRecursionEliminationInitVal. + AccumulatorRecursionEliminationInitVal = getCommonReturnValue(Ret, CI); + if (!AccumulatorRecursionEliminationInitVal) + return false; + } // OK! We can transform this tail call. If this is the first one found, // create the new entry block, allowing us to branch back to the old entry. @@ -465,8 +480,9 @@ bool TailCallElim::ProcessReturningBlock(ReturnInst *Ret, BasicBlock *&OldEntry, if (AccumulatorRecursionEliminationInitVal) { Instruction *AccRecInstr = AccumulatorRecursionInstr; // Start by inserting a new PHI node for the accumulator. - PHINode *AccPN = PHINode::Create(AccRecInstr->getType(), "accumulator.tr", - OldEntry->begin()); + PHINode *AccPN = + PHINode::Create(AccumulatorRecursionEliminationInitVal->getType(), + "accumulator.tr", OldEntry->begin()); // Loop over all of the predecessors of the tail recursion block. For the // real entry into the function we seed the PHI with the initial value, @@ -483,14 +499,20 @@ bool TailCallElim::ProcessReturningBlock(ReturnInst *Ret, BasicBlock *&OldEntry, AccPN->addIncoming(AccPN, P); } - // Add an incoming argument for the current block, which is computed by our - // associative and commutative accumulator instruction. - AccPN->addIncoming(AccRecInstr, BB); - - // Next, rewrite the accumulator recursion instruction so that it does not - // use the result of the call anymore, instead, use the PHI node we just - // inserted. - AccRecInstr->setOperand(AccRecInstr->getOperand(0) != CI, AccPN); + if (AccRecInstr) { + // Add an incoming argument for the current block, which is computed by + // our associative and commutative accumulator instruction. + AccPN->addIncoming(AccRecInstr, BB); + + // Next, rewrite the accumulator recursion instruction so that it does not + // use the result of the call anymore, instead, use the PHI node we just + // inserted. + AccRecInstr->setOperand(AccRecInstr->getOperand(0) != CI, AccPN); + } else { + // Add an incoming argument for the current block, which is just the + // constant returned by the current return instruction. + AccPN->addIncoming(Ret->getReturnValue(), BB); + } // Finally, rewrite any return instructions in the program to return the PHI // node instead of the "initval" that they do currently. This loop will diff --git a/test/Transforms/TailCallElim/2010-06-26-MultipleReturnValues.ll b/test/Transforms/TailCallElim/2010-06-26-MultipleReturnValues.ll index f39476f7daf..06265926fa6 100644 --- a/test/Transforms/TailCallElim/2010-06-26-MultipleReturnValues.ll +++ b/test/Transforms/TailCallElim/2010-06-26-MultipleReturnValues.ll @@ -1,7 +1,9 @@ ; RUN: opt < %s -tailcallelim -S | FileCheck %s ; PR7328 +; PR7506 define i32 @foo(i32 %x) { ; CHECK: define i32 @foo +; CHECK: %accumulator.tr = phi i32 [ 1, %entry ], [ 0, %body ] entry: %cond = icmp ugt i32 %x, 0 ; [#uses=1] br i1 %cond, label %return, label %body @@ -9,8 +11,9 @@ entry: body: ; preds = %entry %y = add i32 %x, 1 ; [#uses=1] %tmp = call i32 @foo(i32 %y) ; [#uses=0] +; CHECK-NOT: call ret i32 0 -; CHECK: ret i32 0 +; CHECK: ret i32 %accumulator.tr return: ; preds = %entry ret i32 1 -- 2.11.0