From 7b9dc28060d71b024b6823df6064be2ee8bddef3 Mon Sep 17 00:00:00 2001 From: "Arnaud A. de Grandmaison" Date: Wed, 19 Nov 2014 13:32:51 +0000 Subject: Fix tail recursion elimination When the BasicBlock containing the return instrution has a PHI with 2 incoming values, FoldReturnIntoUncondBranch will remove the no longer used incoming value and remove the no longer needed phi as well. This leaves us with a BB that no longer has a PHI, but the subsequent call to FoldReturnIntoUncondBranch from FoldReturnAndProcessPred will not remove the return instruction (which still uses the result of the call instruction). This prevents EliminateRecursiveTailCall to remove the value, as it is still being used in a basicblock which has no predecessors. The basicblock can not be erased on the spot, because its iterator is still being used in runTRE. This issue was exposed when removing the threshold on size for lifetime marker insertion for named temporaries in clang. The testcase is a much reduced version of peelOffOuterExpr(const Expr*, const ExplodedNode *) from clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp. llvm-svn: 222354 --- .../Transforms/Scalar/TailRecursionElimination.cpp | 28 +++++++++++++++++++--- 1 file changed, 25 insertions(+), 3 deletions(-) (limited to 'llvm/lib/Transforms') diff --git a/llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp b/llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp index 65b1f142821..f3c3e3054b6 100644 --- a/llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp +++ b/llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp @@ -404,18 +404,28 @@ bool TailCallElim::runTRE(Function &F) { // 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. + SmallVector BBToErase; for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { if (ReturnInst *Ret = dyn_cast(BB->getTerminator())) { bool Change = ProcessReturningBlock(Ret, OldEntry, TailCallsAreMarkedTail, ArgumentPHIs, !CanTRETailMarkedCall); - if (!Change && BB->getFirstNonPHIOrDbg() == Ret) + if (!Change && BB->getFirstNonPHIOrDbg() == Ret) { Change = FoldReturnAndProcessPred(BB, Ret, OldEntry, TailCallsAreMarkedTail, ArgumentPHIs, !CanTRETailMarkedCall); + // FoldReturnAndProcessPred may have emptied some BB. Remember to + // erase them. + if (Change && BB->empty()) + BBToErase.push_back(BB); + + } MadeChange |= Change; } } + for (auto BB: BBToErase) + BB->eraseFromParent(); + // 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 @@ -823,8 +833,20 @@ bool TailCallElim::FoldReturnAndProcessPred(BasicBlock *BB, if (CallInst *CI = FindTRECandidate(BI, CannotTailCallElimCallsMarkedTail)){ DEBUG(dbgs() << "FOLDING: " << *BB << "INTO UNCOND BRANCH PRED: " << *Pred); - EliminateRecursiveTailCall(CI, FoldReturnIntoUncondBranch(Ret, BB, Pred), - OldEntry, TailCallsAreMarkedTail, ArgumentPHIs, + ReturnInst *RI = FoldReturnIntoUncondBranch(Ret, BB, Pred); + + // Cleanup: if all predecessors of BB have been eliminated by + // FoldReturnIntoUncondBranch, we would like to delete it, but we + // can not just nuke it as it is being used as an iterator by our caller. + // Just empty it, and the caller will erase it when it is safe to do so. + // It is important to empty it, because the ret instruction in there is + // still using a value which EliminateRecursiveTailCall will attempt + // to remove. + if (!BB->hasAddressTaken() && pred_begin(BB) == pred_end(BB)) + BB->getInstList().clear(); + + EliminateRecursiveTailCall(CI, RI, OldEntry, TailCallsAreMarkedTail, + ArgumentPHIs, CannotTailCallElimCallsMarkedTail); ++NumRetDuped; Change = true; -- cgit v1.2.3