X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FTailRecursionElimination.cpp;h=7e1ba2c3c90366ea2f5b87caf14eb8535ec044d2;hb=d8502a20d57dc71e3363abb44812b14cc53bbe0e;hp=65427f261e7f688536d49eac0261ea54c34e26ba;hpb=096d8411b3c093e90e2509bab2fea4f7934e7f91;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/TailRecursionElimination.cpp b/lib/Transforms/Scalar/TailRecursionElimination.cpp index 65427f261e7..7e1ba2c3c90 100644 --- a/lib/Transforms/Scalar/TailRecursionElimination.cpp +++ b/lib/Transforms/Scalar/TailRecursionElimination.cpp @@ -54,8 +54,9 @@ #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" -#include "llvm/Analysis/CaptureTracking.h" +#include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/CFG.h" +#include "llvm/Analysis/CaptureTracking.h" #include "llvm/Analysis/InlineCost.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/Loads.h" @@ -63,7 +64,9 @@ #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" @@ -123,7 +126,7 @@ namespace { char TailCallElim::ID = 0; INITIALIZE_PASS_BEGIN(TailCallElim, "tailcallelim", "Tail Call Elimination", false, false) -INITIALIZE_AG_DEPENDENCY(TargetTransformInfo) +INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) INITIALIZE_PASS_END(TailCallElim, "tailcallelim", "Tail Call Elimination", false, false) @@ -133,27 +136,33 @@ FunctionPass *llvm::createTailCallEliminationPass() { } void TailCallElim::getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(); + AU.addRequired(); + AU.addPreserved(); } -/// CanTRE - Scan the specified basic block for alloca instructions. -/// If it contains any that are variable-sized or not in the entry block, -/// returns false. -static bool CanTRE(AllocaInst *AI) { - // Because of PR962, we don't TRE allocas outside the entry block. - - // If this alloca is in the body of the function, or if it is a variable - // sized allocation, we cannot tail call eliminate calls marked 'tail' - // with this mechanism. - BasicBlock *BB = AI->getParent(); - return BB == &BB->getParent()->getEntryBlock() && - isa(AI->getArraySize()); +/// \brief Scan the specified function for alloca instructions. +/// If it contains any dynamic allocas, returns false. +static bool CanTRE(Function &F) { + // Because of PR962, we don't TRE dynamic allocas. + for (auto &BB : F) { + for (auto &I : BB) { + if (AllocaInst *AI = dyn_cast(&I)) { + if (!AI->isStaticAlloca()) + return false; + } + } + } + + 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) @@ -172,7 +181,7 @@ struct AllocaDerivedValueTracker { auto AddUsesToWorklist = [&](Value *V) { for (auto &U : V->uses()) { - if (!Visited.insert(&U)) + if (!Visited.insert(&U).second) continue; Worklist.push_back(&U); } @@ -224,12 +233,10 @@ struct AllocaDerivedValueTracker { } void callUsesLocalStack(CallSite CS, bool IsNocapture) { - // Add it to the list of alloca users. If it's already there, skip further - // processing. - if (!AllocaUsers.insert(CS.getInstruction())) - return; + // Add it to the list of alloca users. + AllocaUsers.insert(CS.getInstruction()); - // If it's nocapture then it can't capture the alloca. + // If it's nocapture then it can't capture this alloca. if (IsNocapture) return; @@ -297,7 +304,9 @@ bool TailCallElim::markTails(Function &F, bool &AllCallsAreTailCalls) { if (!CI || CI->isTailCall()) continue; - if (CI->doesNotAccessMemory()) { + bool IsNoTail = CI->isNoTailCall(); + + if (!IsNoTail && CI->doesNotAccessMemory()) { // A call to a readnone function whose arguments are all things computed // outside this function can be marked tail. Even if you stored the // alloca address into a global, a readnone function can't load the @@ -316,16 +325,16 @@ bool TailCallElim::markTails(Function &F, bool &AllCallsAreTailCalls) { break; } if (SafeToTail) { - F.getContext().emitOptimizationRemark( - "tailcallelim", F, CI->getDebugLoc(), - "found readnone tail call candidate"); + emitOptimizationRemark( + F.getContext(), "tailcallelim", F, CI->getDebugLoc(), + "marked this readnone call a tail call candidate"); CI->setTailCall(); Modified = true; continue; } } - if (Escaped == UNESCAPED && !Tracker.AllocaUsers.count(CI)) { + if (!IsNoTail && Escaped == UNESCAPED && !Tracker.AllocaUsers.count(CI)) { DeferredTails.push_back(CI); } else { AllCallsAreTailCalls = false; @@ -363,8 +372,9 @@ bool TailCallElim::markTails(Function &F, bool &AllCallsAreTailCalls) { if (Visited[CI->getParent()] != ESCAPED) { // If the escape point was part way through the block, calls after the // escape point wouldn't have been put into DeferredTails. - F.getContext().emitOptimizationRemark( - "tailcallelim", F, CI->getDebugLoc(), "found tail call candidate"); + emitOptimizationRemark(F.getContext(), "tailcallelim", F, + CI->getDebugLoc(), + "marked this call a tail call candidate"); CI->setTailCall(); Modified = true; } else { @@ -380,26 +390,16 @@ bool TailCallElim::runTRE(Function &F) { // right, so don't even try to convert it... if (F.getFunctionType()->isVarArg()) return false; - TTI = &getAnalysis(); + TTI = &getAnalysis().getTTI(F); BasicBlock *OldEntry = nullptr; bool TailCallsAreMarkedTail = false; SmallVector ArgumentPHIs; bool MadeChange = false; - // CanTRETailMarkedCall - 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 = true; - - // Find dynamic allocas. - for (Function::iterator BB = F.begin(), EE = F.end(); BB != EE; ++BB) { - for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { - if (AllocaInst *AI = dyn_cast(I)) { - CanTRETailMarkedCall &= CanTRE(AI); - } - } - } + // 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. // @@ -407,7 +407,8 @@ 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. - for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { + 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); @@ -428,7 +429,7 @@ bool TailCallElim::runTRE(Function &F) { PHINode *PN = ArgumentPHIs[i]; // If the PHI Node is a dynamic constant, replace it with the value it is. - if (Value *PNV = SimplifyInstruction(PN)) { + if (Value *PNV = SimplifyInstruction(PN, F.getParent()->getDataLayout())) { PN->replaceAllUsesWith(PNV); PN->eraseFromParent(); } @@ -438,7 +439,7 @@ bool TailCallElim::runTRE(Function &F) { } -/// CanMoveAboveCall - Return true if it is safe to move the specified +/// 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. /// @@ -473,13 +474,11 @@ bool TailCallElim::CanMoveAboveCall(Instruction *I, CallInst *CI) { return true; } -// isDynamicConstant - Return true if the specified value is the same when the -// return would exit as it was when the initial iteration of the recursive -// function was executed. -// -// We currently handle static constants and arguments that are not modified as -// part of the recursion. -// +/// Return true if the specified value is the same when the return would exit +/// as it was when the initial iteration of the recursive function was executed. +/// +/// We currently handle static constants and arguments that are not modified as +/// part of the recursion. static bool isDynamicConstant(Value *V, CallInst *CI, ReturnInst *RI) { if (isa(V)) return true; // Static constants are always dyn consts @@ -511,10 +510,9 @@ static bool isDynamicConstant(Value *V, CallInst *CI, ReturnInst *RI) { return false; } -// getCommonReturnValue - Check to see if the function containing the specified -// tail call consistently returns the same runtime-constant value at all exit -// points except for IgnoreRI. If so, return the returned value. -// +/// Check to see if the function containing the specified tail call consistently +/// returns the same runtime-constant value at all exit points except for +/// IgnoreRI. If so, return the returned value. static Value *getCommonReturnValue(ReturnInst *IgnoreRI, CallInst *CI) { Function *F = CI->getParent()->getParent(); Value *ReturnedValue = nullptr; @@ -538,10 +536,9 @@ static Value *getCommonReturnValue(ReturnInst *IgnoreRI, CallInst *CI) { return ReturnedValue; } -/// CanTransformAccumulatorRecursion - 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. -/// +/// 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) { if (!I->isAssociative() || !I->isCommutative()) return nullptr; @@ -581,7 +578,7 @@ TailCallElim::FindTRECandidate(Instruction *TI, // Scan backwards from the return, checking to see if there is a tail call in // this block. If so, set CI to it. CallInst *CI = nullptr; - BasicBlock::iterator BBI = TI; + BasicBlock::iterator BBI(TI); while (true) { CI = dyn_cast(BBI); if (CI && CI->getCalledFunction() == F) @@ -602,9 +599,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()) == 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. @@ -643,19 +639,19 @@ bool TailCallElim::EliminateRecursiveTailCall(CallInst *CI, ReturnInst *Ret, // tail call if all of the instructions between the call and the return are // movable to above the call itself, leaving the call next to the return. // Check that this is the case now. - BasicBlock::iterator BBI = CI; + 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; + AccumulatorRecursionInstr = &*BBI; } else { return false; // Otherwise, we cannot eliminate the tail recursion! } @@ -684,9 +680,8 @@ bool TailCallElim::EliminateRecursiveTailCall(CallInst *CI, ReturnInst *Ret, BasicBlock *BB = Ret->getParent(); Function *F = BB->getParent(); - F->getContext().emitOptimizationRemark( - "tailcallelim", *F, CI->getDebugLoc(), - "transforming tail recursion to loop"); + emitOptimizationRemark(F->getContext(), "tailcallelim", *F, CI->getDebugLoc(), + "transforming tail recursion to loop"); // 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. @@ -706,19 +701,19 @@ bool TailCallElim::EliminateRecursiveTailCall(CallInst *CI, ReturnInst *Ret, NEBI = NewEntry->begin(); OEBI != E; ) if (AllocaInst *AI = dyn_cast(OEBI++)) if (isa(AI->getArraySize())) - AI->moveBefore(NEBI); + AI->moveBefore(&*NEBI); // Now that we have created a new block, which jumps to the entry // block, insert a PHI node for each argument of the function. // For now, we initialize each PHI to only have the real arguments // which are passed in. - Instruction *InsertPos = OldEntry->begin(); + Instruction *InsertPos = &OldEntry->front(); for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; ++I) { PHINode *PN = PHINode::Create(I->getType(), 2, I->getName() + ".tr", InsertPos); I->replaceAllUsesWith(PN); // Everyone use the PHI node now! - PN->addIncoming(I, NewEntry); + PN->addIncoming(&*I, NewEntry); ArgumentPHIs.push_back(PN); } } @@ -747,10 +742,9 @@ bool TailCallElim::EliminateRecursiveTailCall(CallInst *CI, ReturnInst *Ret, Instruction *AccRecInstr = AccumulatorRecursionInstr; // Start by inserting a new PHI node for the accumulator. pred_iterator PB = pred_begin(OldEntry), PE = pred_end(OldEntry); - PHINode *AccPN = - PHINode::Create(AccumulatorRecursionEliminationInitVal->getType(), - std::distance(PB, PE) + 1, - "accumulator.tr", OldEntry->begin()); + PHINode *AccPN = PHINode::Create( + AccumulatorRecursionEliminationInitVal->getType(), + std::distance(PB, PE) + 1, "accumulator.tr", &OldEntry->front()); // 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, @@ -827,8 +821,17 @@ 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, 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. + if (!BB->hasAddressTaken() && pred_begin(BB) == pred_end(BB)) + BB->eraseFromParent(); + + EliminateRecursiveTailCall(CI, RI, OldEntry, TailCallsAreMarkedTail, + ArgumentPHIs, CannotTailCallElimCallsMarkedTail); ++NumRetDuped; Change = true;