Index: lib/Transforms/Scalar/TailRecursionElimination.cpp =================================================================== --- lib/Transforms/Scalar/TailRecursionElimination.cpp +++ lib/Transforms/Scalar/TailRecursionElimination.cpp @@ -54,27 +54,12 @@ #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" -#include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/CFG.h" -#include "llvm/Analysis/CaptureTracking.h" -#include "llvm/Analysis/InlineCost.h" +#include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/Loads.h" #include "llvm/Analysis/TargetTransformInfo.h" -#include "llvm/IR/CFG.h" -#include "llvm/IR/CallSite.h" -#include "llvm/IR/Constants.h" -#include "llvm/IR/DataLayout.h" -#include "llvm/IR/DerivedTypes.h" #include "llvm/IR/DiagnosticInfo.h" -#include "llvm/IR/Function.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/IntrinsicInst.h" -#include "llvm/IR/Module.h" -#include "llvm/IR/ValueHandle.h" -#include "llvm/Pass.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Local.h" using namespace llvm; @@ -87,39 +72,13 @@ namespace { struct TailCallElim : public FunctionPass { - const TargetTransformInfo *TTI; - static char ID; // Pass identification, replacement for typeid TailCallElim() : FunctionPass(ID) { initializeTailCallElimPass(*PassRegistry::getPassRegistry()); } void getAnalysisUsage(AnalysisUsage &AU) const override; - bool runOnFunction(Function &F) override; - - private: - bool runTRE(Function &F); - bool markTails(Function &F, bool &AllCallsAreTailCalls); - - CallInst *FindTRECandidate(Instruction *I, - bool CannotTailCallElimCallsMarkedTail); - bool EliminateRecursiveTailCall(CallInst *CI, ReturnInst *Ret, - BasicBlock *&OldEntry, - bool &TailCallsAreMarkedTail, - SmallVectorImpl &ArgumentPHIs, - bool CannotTailCallElimCallsMarkedTail); - bool FoldReturnAndProcessPred(BasicBlock *BB, - ReturnInst *Ret, BasicBlock *&OldEntry, - bool &TailCallsAreMarkedTail, - SmallVectorImpl &ArgumentPHIs, - bool CannotTailCallElimCallsMarkedTail); - bool ProcessReturningBlock(ReturnInst *RI, BasicBlock *&OldEntry, - bool &TailCallsAreMarkedTail, - SmallVectorImpl &ArgumentPHIs, - bool CannotTailCallElimCallsMarkedTail); - bool CanMoveAboveCall(Instruction *I, CallInst *CI); - Value *CanTransformAccumulatorRecursion(Instruction *I, CallInst *CI); }; } @@ -142,7 +101,7 @@ /// \brief Scan the specified function for alloca instructions. /// If it contains any dynamic allocas, returns false. -static bool CanTRE(Function &F) { +static bool canTRE(Function &F) { // Because of PR962, we don't TRE dynamic allocas. for (auto &BB : F) { for (auto &I : BB) { @@ -156,20 +115,6 @@ return true; } -bool TailCallElim::runOnFunction(Function &F) { - if (skipFunction(F)) - return false; - - if (F.getFnAttribute("disable-tail-calls").getValueAsString() == "true") - return false; - - bool AllCallsAreTailCalls = false; - bool Modified = markTails(F, AllCallsAreTailCalls); - if (AllCallsAreTailCalls) - Modified |= runTRE(F); - return Modified; -} - namespace { struct AllocaDerivedValueTracker { // Start at a root value and walk its use-def chain to mark calls that use the @@ -250,7 +195,7 @@ }; } -bool TailCallElim::markTails(Function &F, bool &AllCallsAreTailCalls) { +static bool markTails(Function &F, bool &AllCallsAreTailCalls) { if (F.callsFunctionThatReturnsTwice()) return false; AllCallsAreTailCalls = true; @@ -385,63 +330,11 @@ return Modified; } -bool TailCallElim::runTRE(Function &F) { - // If this function is a varargs function, we won't be able to PHI the args - // right, so don't even try to convert it... - if (F.getFunctionType()->isVarArg()) return false; - - TTI = &getAnalysis().getTTI(F); - BasicBlock *OldEntry = nullptr; - bool TailCallsAreMarkedTail = false; - SmallVector ArgumentPHIs; - bool MadeChange = false; - - // If false, we cannot perform TRE on tail calls marked with the 'tail' - // attribute, because doing so would cause the stack size to increase (real - // TRE would deallocate variable sized allocas, TRE doesn't). - bool CanTRETailMarkedCall = CanTRE(F); - - // Change any tail recursive calls to loops. - // - // 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. - for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; /*in loop*/) { - BasicBlock *BB = &*BBI++; // FoldReturnAndProcessPred may delete BB. - if (ReturnInst *Ret = dyn_cast(BB->getTerminator())) { - bool Change = ProcessReturningBlock(Ret, OldEntry, TailCallsAreMarkedTail, - ArgumentPHIs, !CanTRETailMarkedCall); - if (!Change && BB->getFirstNonPHIOrDbg() == Ret) - Change = FoldReturnAndProcessPred(BB, Ret, OldEntry, - TailCallsAreMarkedTail, ArgumentPHIs, - !CanTRETailMarkedCall); - MadeChange |= Change; - } - } - - // If we eliminated any tail recursions, it's possible that we inserted some - // silly PHI nodes which just merge an initial value (the incoming operand) - // with themselves. Check to see if we did and clean up our mess if so. This - // occurs when a function passes an argument straight through to its tail - // call. - for (PHINode *PN : ArgumentPHIs) { - // If the PHI Node is a dynamic constant, replace it with the value it is. - if (Value *PNV = SimplifyInstruction(PN, F.getParent()->getDataLayout())) { - PN->replaceAllUsesWith(PNV); - PN->eraseFromParent(); - } - } - - return MadeChange; -} - - /// Return true if it is safe to move the specified /// instruction from after the call to before the call, assuming that all /// instructions between the call and this instruction are movable. /// -bool TailCallElim::CanMoveAboveCall(Instruction *I, CallInst *CI) { +static bool canMoveAboveCall(Instruction *I, CallInst *CI) { // FIXME: We can move load/store/call/free instructions above the call if the // call does not mod/ref the memory location being processed. if (I->mayHaveSideEffects()) // This also handles volatile loads. @@ -535,8 +428,7 @@ /// If the specified instruction can be transformed using accumulator recursion /// elimination, return the constant which is the start of the accumulator /// value. Otherwise return null. -Value *TailCallElim::CanTransformAccumulatorRecursion(Instruction *I, - CallInst *CI) { +static Value *canTransformAccumulatorRecursion(Instruction *I, CallInst *CI) { if (!I->isAssociative() || !I->isCommutative()) return nullptr; assert(I->getNumOperands() == 2 && "Associative/commutative operations should have 2 args!"); @@ -556,15 +448,15 @@ return getCommonReturnValue(cast(I->user_back()), CI); } -static Instruction *FirstNonDbg(BasicBlock::iterator I) { +static Instruction *firstNonDbg(BasicBlock::iterator I) { while (isa(I)) ++I; return &*I; } -CallInst* -TailCallElim::FindTRECandidate(Instruction *TI, - bool CannotTailCallElimCallsMarkedTail) { +static CallInst *findTRECandidate(Instruction *TI, + bool CannotTailCallElimCallsMarkedTail, + const TargetTransformInfo *TTI) { BasicBlock *BB = TI->getParent(); Function *F = BB->getParent(); @@ -595,8 +487,8 @@ // and disable this xform in this case, because the code generator will // lower the call to fabs into inline code. if (BB == &F->getEntryBlock() && - FirstNonDbg(BB->front().getIterator()) == CI && - FirstNonDbg(std::next(BB->begin())) == TI && CI->getCalledFunction() && + firstNonDbg(BB->front().getIterator()) == CI && + firstNonDbg(std::next(BB->begin())) == TI && CI->getCalledFunction() && !TTI->isLoweredToCall(CI->getCalledFunction())) { // A single-block function with just a call and a return. Check that // the arguments match. @@ -613,7 +505,7 @@ return CI; } -bool TailCallElim::EliminateRecursiveTailCall(CallInst *CI, ReturnInst *Ret, +static bool eliminateRecursiveTailCall(CallInst *CI, ReturnInst *Ret, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail, SmallVectorImpl &ArgumentPHIs, @@ -637,14 +529,14 @@ // Check that this is the case now. BasicBlock::iterator BBI(CI); for (++BBI; &*BBI != Ret; ++BBI) { - if (CanMoveAboveCall(&*BBI, CI)) continue; + if (canMoveAboveCall(&*BBI, CI)) continue; // If we can't move the instruction above the call, it might be because it // is an associative and commutative operation that could be transformed // using accumulator recursion elimination. Check to see if this is the // case, and if so, remember the initial accumulator value for later. if ((AccumulatorRecursionEliminationInitVal = - CanTransformAccumulatorRecursion(&*BBI, CI))) { + canTransformAccumulatorRecursion(&*BBI, CI))) { // Yes, this is accumulator recursion. Remember which instruction // accumulates. AccumulatorRecursionInstr = &*BBI; @@ -791,11 +683,12 @@ return true; } -bool TailCallElim::FoldReturnAndProcessPred(BasicBlock *BB, - ReturnInst *Ret, BasicBlock *&OldEntry, - bool &TailCallsAreMarkedTail, - SmallVectorImpl &ArgumentPHIs, - bool CannotTailCallElimCallsMarkedTail) { +static bool foldReturnAndProcessPred(BasicBlock *BB, ReturnInst *Ret, + BasicBlock *&OldEntry, + bool &TailCallsAreMarkedTail, + SmallVectorImpl &ArgumentPHIs, + bool CannotTailCallElimCallsMarkedTail, + const TargetTransformInfo *TTI) { bool Change = false; // If the return block contains nothing but the return and PHI's, @@ -814,7 +707,7 @@ while (!UncondBranchPreds.empty()) { BranchInst *BI = UncondBranchPreds.pop_back_val(); BasicBlock *Pred = BI->getParent(); - if (CallInst *CI = FindTRECandidate(BI, CannotTailCallElimCallsMarkedTail)){ + if (CallInst *CI = findTRECandidate(BI, CannotTailCallElimCallsMarkedTail, TTI)){ DEBUG(dbgs() << "FOLDING: " << *BB << "INTO UNCOND BRANCH PRED: " << *Pred); ReturnInst *RI = FoldReturnIntoUncondBranch(Ret, BB, Pred); @@ -822,11 +715,11 @@ // Cleanup: if all predecessors of BB have been eliminated by // FoldReturnIntoUncondBranch, delete it. It is important to empty it, // because the ret instruction in there is still using a value which - // EliminateRecursiveTailCall will attempt to remove. + // eliminateRecursiveTailCall will attempt to remove. if (!BB->hasAddressTaken() && pred_begin(BB) == pred_end(BB)) BB->eraseFromParent(); - EliminateRecursiveTailCall(CI, RI, OldEntry, TailCallsAreMarkedTail, + eliminateRecursiveTailCall(CI, RI, OldEntry, TailCallsAreMarkedTail, ArgumentPHIs, CannotTailCallElimCallsMarkedTail); ++NumRetDuped; @@ -837,16 +730,81 @@ return Change; } -bool -TailCallElim::ProcessReturningBlock(ReturnInst *Ret, BasicBlock *&OldEntry, - bool &TailCallsAreMarkedTail, - SmallVectorImpl &ArgumentPHIs, - bool CannotTailCallElimCallsMarkedTail) { - CallInst *CI = FindTRECandidate(Ret, CannotTailCallElimCallsMarkedTail); +static bool processReturningBlock(ReturnInst *Ret, BasicBlock *&OldEntry, + bool &TailCallsAreMarkedTail, + SmallVectorImpl &ArgumentPHIs, + bool CannotTailCallElimCallsMarkedTail, + const TargetTransformInfo *TTI) { + CallInst *CI = findTRECandidate(Ret, CannotTailCallElimCallsMarkedTail, TTI); if (!CI) return false; - return EliminateRecursiveTailCall(CI, Ret, OldEntry, TailCallsAreMarkedTail, + return eliminateRecursiveTailCall(CI, Ret, OldEntry, TailCallsAreMarkedTail, ArgumentPHIs, CannotTailCallElimCallsMarkedTail); } + +static bool runTRE(Function &F, const TargetTransformInfo *TTI) { + // If this function is a varargs function, we won't be able to PHI the args + // right, so don't even try to convert it... + if (F.getFunctionType()->isVarArg()) return false; + + BasicBlock *OldEntry = nullptr; + bool TailCallsAreMarkedTail = false; + SmallVector ArgumentPHIs; + bool MadeChange = false; + + // If false, we cannot perform TRE on tail calls marked with the 'tail' + // attribute, because doing so would cause the stack size to increase (real + // TRE would deallocate variable sized allocas, TRE doesn't). + bool CanTRETailMarkedCall = canTRE(F); + + // Change any tail recursive calls to loops. + // + // 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. + for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; /*in loop*/) { + BasicBlock *BB = &*BBI++; // foldReturnAndProcessPred may delete BB. + if (ReturnInst *Ret = dyn_cast(BB->getTerminator())) { + bool Change = + processReturningBlock(Ret, OldEntry, TailCallsAreMarkedTail, + ArgumentPHIs, !CanTRETailMarkedCall, TTI); + if (!Change && BB->getFirstNonPHIOrDbg() == Ret) + Change = + foldReturnAndProcessPred(BB, Ret, OldEntry, TailCallsAreMarkedTail, + ArgumentPHIs, !CanTRETailMarkedCall, TTI); + MadeChange |= Change; + } + } + + // If we eliminated any tail recursions, it's possible that we inserted some + // silly PHI nodes which just merge an initial value (the incoming operand) + // with themselves. Check to see if we did and clean up our mess if so. This + // occurs when a function passes an argument straight through to its tail + // call. + for (PHINode *PN : ArgumentPHIs) { + // If the PHI Node is a dynamic constant, replace it with the value it is. + if (Value *PNV = SimplifyInstruction(PN, F.getParent()->getDataLayout())) { + PN->replaceAllUsesWith(PNV); + PN->eraseFromParent(); + } + } + + return MadeChange; +} + +bool TailCallElim::runOnFunction(Function &F) { + if (skipFunction(F)) + return false; + + if (F.getFnAttribute("disable-tail-calls").getValueAsString() == "true") + return false; + + bool AllCallsAreTailCalls = false; + bool Modified = markTails(F, AllCallsAreTailCalls); + if (AllCallsAreTailCalls) + Modified |= runTRE(F, &getAnalysis().getTTI(F)); + return Modified; +}