diff options
Diffstat (limited to 'lib/Transforms/Scalar/TailRecursionElimination.cpp')
| -rw-r--r-- | lib/Transforms/Scalar/TailRecursionElimination.cpp | 301 |
1 files changed, 145 insertions, 156 deletions
diff --git a/lib/Transforms/Scalar/TailRecursionElimination.cpp b/lib/Transforms/Scalar/TailRecursionElimination.cpp index 4e84d72ae7bd..d5ff99750370 100644 --- a/lib/Transforms/Scalar/TailRecursionElimination.cpp +++ b/lib/Transforms/Scalar/TailRecursionElimination.cpp @@ -50,6 +50,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/Transforms/Scalar/TailRecursionElimination.h" #include "llvm/Transforms/Scalar.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" @@ -85,64 +86,9 @@ STATISTIC(NumEliminated, "Number of tail calls removed"); STATISTIC(NumRetDuped, "Number of return duplicated"); STATISTIC(NumAccumAdded, "Number of accumulators introduced"); -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<PHINode *> &ArgumentPHIs, - bool CannotTailCallElimCallsMarkedTail); - bool FoldReturnAndProcessPred(BasicBlock *BB, - ReturnInst *Ret, BasicBlock *&OldEntry, - bool &TailCallsAreMarkedTail, - SmallVectorImpl<PHINode *> &ArgumentPHIs, - bool CannotTailCallElimCallsMarkedTail); - bool ProcessReturningBlock(ReturnInst *RI, BasicBlock *&OldEntry, - bool &TailCallsAreMarkedTail, - SmallVectorImpl<PHINode *> &ArgumentPHIs, - bool CannotTailCallElimCallsMarkedTail); - bool CanMoveAboveCall(Instruction *I, CallInst *CI); - Value *CanTransformAccumulatorRecursion(Instruction *I, CallInst *CI); - }; -} - -char TailCallElim::ID = 0; -INITIALIZE_PASS_BEGIN(TailCallElim, "tailcallelim", - "Tail Call Elimination", false, false) -INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) -INITIALIZE_PASS_END(TailCallElim, "tailcallelim", - "Tail Call Elimination", false, false) - -// Public interface to the TailCallElimination pass -FunctionPass *llvm::createTailCallEliminationPass() { - return new TailCallElim(); -} - -void TailCallElim::getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired<TargetTransformInfoWrapperPass>(); - AU.addPreserved<GlobalsAAWrapperPass>(); -} - /// \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 +102,6 @@ static bool CanTRE(Function &F) { return true; } -bool TailCallElim::runOnFunction(Function &F) { - if (skipOptnoneFunction(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 +182,7 @@ struct AllocaDerivedValueTracker { }; } -bool TailCallElim::markTails(Function &F, bool &AllCallsAreTailCalls) { +static bool markTails(Function &F, bool &AllCallsAreTailCalls) { if (F.callsFunctionThatReturnsTwice()) return false; AllCallsAreTailCalls = true; @@ -385,63 +317,11 @@ bool TailCallElim::markTails(Function &F, bool &AllCallsAreTailCalls) { 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<TargetTransformInfoWrapperPass>().getTTI(F); - BasicBlock *OldEntry = nullptr; - bool TailCallsAreMarkedTail = false; - SmallVector<PHINode*, 8> 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<ReturnInst>(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. @@ -454,9 +334,10 @@ bool TailCallElim::CanMoveAboveCall(Instruction *I, CallInst *CI) { // does not write to memory and the load provably won't trap. // FIXME: Writes to memory only matter if they may alias the pointer // being loaded from. + const DataLayout &DL = L->getModule()->getDataLayout(); if (CI->mayWriteToMemory() || - !isSafeToLoadUnconditionally(L->getPointerOperand(), L, - L->getAlignment())) + !isSafeToLoadUnconditionally(L->getPointerOperand(), + L->getAlignment(), DL, L)) return false; } } @@ -512,8 +393,8 @@ static Value *getCommonReturnValue(ReturnInst *IgnoreRI, CallInst *CI) { Function *F = CI->getParent()->getParent(); Value *ReturnedValue = nullptr; - for (Function::iterator BBI = F->begin(), E = F->end(); BBI != E; ++BBI) { - ReturnInst *RI = dyn_cast<ReturnInst>(BBI->getTerminator()); + for (BasicBlock &BBI : *F) { + ReturnInst *RI = dyn_cast<ReturnInst>(BBI.getTerminator()); if (RI == nullptr || RI == IgnoreRI) continue; // We can only perform this transformation if the value returned is @@ -534,8 +415,7 @@ static Value *getCommonReturnValue(ReturnInst *IgnoreRI, CallInst *CI) { /// 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!"); @@ -555,15 +435,15 @@ Value *TailCallElim::CanTransformAccumulatorRecursion(Instruction *I, return getCommonReturnValue(cast<ReturnInst>(I->user_back()), CI); } -static Instruction *FirstNonDbg(BasicBlock::iterator I) { +static Instruction *firstNonDbg(BasicBlock::iterator I) { while (isa<DbgInfoIntrinsic>(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(); @@ -594,8 +474,8 @@ TailCallElim::FindTRECandidate(Instruction *TI, // 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. @@ -612,7 +492,7 @@ TailCallElim::FindTRECandidate(Instruction *TI, return CI; } -bool TailCallElim::EliminateRecursiveTailCall(CallInst *CI, ReturnInst *Ret, +static bool eliminateRecursiveTailCall(CallInst *CI, ReturnInst *Ret, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail, SmallVectorImpl<PHINode *> &ArgumentPHIs, @@ -636,14 +516,14 @@ bool TailCallElim::EliminateRecursiveTailCall(CallInst *CI, ReturnInst *Ret, // 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; @@ -773,8 +653,8 @@ bool TailCallElim::EliminateRecursiveTailCall(CallInst *CI, ReturnInst *Ret, // Finally, rewrite any return instructions in the program to return the PHI // node instead of the "initval" that they do currently. This loop will // actually rewrite the return value we are destroying, but that's ok. - for (Function::iterator BBI = F->begin(), E = F->end(); BBI != E; ++BBI) - if (ReturnInst *RI = dyn_cast<ReturnInst>(BBI->getTerminator())) + for (BasicBlock &BBI : *F) + if (ReturnInst *RI = dyn_cast<ReturnInst>(BBI.getTerminator())) RI->setOperand(0, AccPN); ++NumAccumAdded; } @@ -790,11 +670,12 @@ bool TailCallElim::EliminateRecursiveTailCall(CallInst *CI, ReturnInst *Ret, return true; } -bool TailCallElim::FoldReturnAndProcessPred(BasicBlock *BB, - ReturnInst *Ret, BasicBlock *&OldEntry, - bool &TailCallsAreMarkedTail, - SmallVectorImpl<PHINode *> &ArgumentPHIs, - bool CannotTailCallElimCallsMarkedTail) { +static bool foldReturnAndProcessPred(BasicBlock *BB, ReturnInst *Ret, + BasicBlock *&OldEntry, + bool &TailCallsAreMarkedTail, + SmallVectorImpl<PHINode *> &ArgumentPHIs, + bool CannotTailCallElimCallsMarkedTail, + const TargetTransformInfo *TTI) { bool Change = false; // If the return block contains nothing but the return and PHI's, @@ -813,7 +694,7 @@ bool TailCallElim::FoldReturnAndProcessPred(BasicBlock *BB, 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); @@ -821,11 +702,11 @@ bool TailCallElim::FoldReturnAndProcessPred(BasicBlock *BB, // 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; @@ -836,16 +717,124 @@ bool TailCallElim::FoldReturnAndProcessPred(BasicBlock *BB, return Change; } -bool -TailCallElim::ProcessReturningBlock(ReturnInst *Ret, BasicBlock *&OldEntry, - bool &TailCallsAreMarkedTail, - SmallVectorImpl<PHINode *> &ArgumentPHIs, - bool CannotTailCallElimCallsMarkedTail) { - CallInst *CI = FindTRECandidate(Ret, CannotTailCallElimCallsMarkedTail); +static bool processReturningBlock(ReturnInst *Ret, BasicBlock *&OldEntry, + bool &TailCallsAreMarkedTail, + SmallVectorImpl<PHINode *> &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 eliminateTailRecursion(Function &F, const TargetTransformInfo *TTI) { + if (F.getFnAttribute("disable-tail-calls").getValueAsString() == "true") + return false; + + bool MadeChange = false; + bool AllCallsAreTailCalls = false; + MadeChange |= markTails(F, AllCallsAreTailCalls); + if (!AllCallsAreTailCalls) + return MadeChange; + + // 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<PHINode*, 8> ArgumentPHIs; + + // 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<ReturnInst>(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; +} + +namespace { +struct TailCallElim : public FunctionPass { + static char ID; // Pass identification, replacement for typeid + TailCallElim() : FunctionPass(ID) { + initializeTailCallElimPass(*PassRegistry::getPassRegistry()); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired<TargetTransformInfoWrapperPass>(); + AU.addPreserved<GlobalsAAWrapperPass>(); + } + + bool runOnFunction(Function &F) override { + if (skipFunction(F)) + return false; + + return eliminateTailRecursion( + F, &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F)); + } +}; +} + +char TailCallElim::ID = 0; +INITIALIZE_PASS_BEGIN(TailCallElim, "tailcallelim", "Tail Call Elimination", + false, false) +INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) +INITIALIZE_PASS_END(TailCallElim, "tailcallelim", "Tail Call Elimination", + false, false) + +// Public interface to the TailCallElimination pass +FunctionPass *llvm::createTailCallEliminationPass() { + return new TailCallElim(); +} + +PreservedAnalyses TailCallElimPass::run(Function &F, + FunctionAnalysisManager &AM) { + + TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(F); + + bool Changed = eliminateTailRecursion(F, &TTI); + + if (!Changed) + return PreservedAnalyses::all(); + PreservedAnalyses PA; + PA.preserve<GlobalsAA>(); + return PA; +} |