X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FTailRecursionElimination.cpp;h=9fb8ddc3d2c1c15475efd0cb73cb66e36c70c8cf;hb=6a565e5be6c3daa69a32d2cf879df8699c7e0f88;hp=453f87a29685e79e2bfc9b2b425b9c93bc85550c;hpb=241d1398e0f8267c4dd8bf860e84a2c61739c07f;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/TailRecursionElimination.cpp b/lib/Transforms/Scalar/TailRecursionElimination.cpp index 453f87a2968..9fb8ddc3d2c 100644 --- a/lib/Transforms/Scalar/TailRecursionElimination.cpp +++ b/lib/Transforms/Scalar/TailRecursionElimination.cpp @@ -52,26 +52,28 @@ #define DEBUG_TYPE "tailcallelim" #include "llvm/Transforms/Scalar.h" -#include "llvm/Transforms/Utils/BasicBlockUtils.h" -#include "llvm/Transforms/Utils/Local.h" -#include "llvm/Constants.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Function.h" -#include "llvm/Instructions.h" -#include "llvm/IntrinsicInst.h" -#include "llvm/Module.h" -#include "llvm/Pass.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/Statistic.h" #include "llvm/Analysis/CaptureTracking.h" #include "llvm/Analysis/InlineCost.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/Loads.h" -#include "llvm/Support/CallSite.h" +#include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/DerivedTypes.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/Module.h" +#include "llvm/Pass.h" #include "llvm/Support/CFG.h" +#include "llvm/Support/CallSite.h" #include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" #include "llvm/Support/ValueHandle.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/ADT/STLExtras.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/Local.h" using namespace llvm; STATISTIC(NumEliminated, "Number of tail calls removed"); @@ -80,11 +82,15 @@ 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()); } + virtual void getAnalysisUsage(AnalysisUsage &AU) const; + virtual bool runOnFunction(Function &F); private: @@ -93,16 +99,16 @@ namespace { bool EliminateRecursiveTailCall(CallInst *CI, ReturnInst *Ret, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail, - SmallVector &ArgumentPHIs, + SmallVectorImpl &ArgumentPHIs, bool CannotTailCallElimCallsMarkedTail); bool FoldReturnAndProcessPred(BasicBlock *BB, ReturnInst *Ret, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail, - SmallVector &ArgumentPHIs, + SmallVectorImpl &ArgumentPHIs, bool CannotTailCallElimCallsMarkedTail); bool ProcessReturningBlock(ReturnInst *RI, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail, - SmallVector &ArgumentPHIs, + SmallVectorImpl &ArgumentPHIs, bool CannotTailCallElimCallsMarkedTail); bool CanMoveAboveCall(Instruction *I, CallInst *CI); Value *CanTransformAccumulatorRecursion(Instruction *I, CallInst *CI); @@ -110,14 +116,21 @@ namespace { } char TailCallElim::ID = 0; -INITIALIZE_PASS(TailCallElim, "tailcallelim", - "Tail Call Elimination", false, false) +INITIALIZE_PASS_BEGIN(TailCallElim, "tailcallelim", + "Tail Call Elimination", false, false) +INITIALIZE_AG_DEPENDENCY(TargetTransformInfo) +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(); +} + /// 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. @@ -132,42 +145,41 @@ static bool CanTRE(AllocaInst *AI) { isa(AI->getArraySize()); } +namespace { struct AllocaCaptureTracker : public CaptureTracker { AllocaCaptureTracker() : Captured(false) {} - void tooManyUses() { Captured = true; } + void tooManyUses() LLVM_OVERRIDE { Captured = true; } - bool shouldExplore(Use *U) { - Value *V = U->get(); + bool shouldExplore(Use *U) LLVM_OVERRIDE { + Value *V = U->getUser(); if (isa(V) || isa(V)) - UsesAlloca.push_back(V); - + UsesAlloca.insert(V); return true; } - bool captured(Use *U) { + bool captured(Use *U) LLVM_OVERRIDE { if (isa(U->getUser())) return false; - Captured = true; return true; } - SmallVector UsesAlloca; - bool Captured; + SmallPtrSet UsesAlloca; }; +} // end anonymous namespace bool TailCallElim::runOnFunction(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(); BasicBlock *OldEntry = 0; bool TailCallsAreMarkedTail = false; SmallVector ArgumentPHIs; bool MadeChange = false; - bool FunctionContainsEscapingAllocas = false; // CanTRETailMarkedCall - If false, we cannot perform TRE on tail calls // marked with the 'tail' attribute, because doing so would cause the stack @@ -181,7 +193,8 @@ bool TailCallElim::runOnFunction(Function &F) { for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { if (AllocaInst *AI = dyn_cast(I)) { CanTRETailMarkedCall &= CanTRE(AI); - PointerMayBeCaptured(I, &ACT); + PointerMayBeCaptured(AI, &ACT); + // If any allocas are captured, exit. if (ACT.Captured) return false; } @@ -189,15 +202,22 @@ bool TailCallElim::runOnFunction(Function &F) { } // Second pass, change any tail recursive calls to loops. - 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) - Change = FoldReturnAndProcessPred(BB, Ret, OldEntry, - TailCallsAreMarkedTail, ArgumentPHIs, - !CanTRETailMarkedCall); - MadeChange |= Change; + // + // 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. + if (ACT.UsesAlloca.empty()) { + 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) + Change = FoldReturnAndProcessPred(BB, Ret, OldEntry, + TailCallsAreMarkedTail, ArgumentPHIs, + !CanTRETailMarkedCall); + MadeChange |= Change; + } } } @@ -218,24 +238,29 @@ bool TailCallElim::runOnFunction(Function &F) { } } - // Finally, if this function contains no non-escaping allocas and doesn't - // call setjmp, mark all calls in the function as eligible for tail calls - // (there is no stack memory for them to access). - std::sort(ACT.UsesAlloca.begin(), ACT.UsesAlloca.end()); - - if (!FunctionContainsEscapingAllocas && !F.callsFunctionThatReturnsTwice()) - for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) - for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) - if (CallInst *CI = dyn_cast(I)) - if (!std::binary_search(ACT.UsesAlloca.begin(), ACT.UsesAlloca.end(), - CI)) { + // At this point, we know that the function does not have any captured + // allocas. If additionally the function does not call setjmp, mark all calls + // in the function that do not access stack memory with the tail keyword. This + // implies ensuring that there does not exist any path from a call that takes + // in an alloca but does not capture it and the call which we wish to mark + // with "tail". + if (!F.callsFunctionThatReturnsTwice()) { + for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { + for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { + if (CallInst *CI = dyn_cast(I)) { + if (!ACT.UsesAlloca.count(CI)) { CI->setTailCall(); MadeChange = true; } + } + } + } + } return MadeChange; } + /// CanMoveAboveCall - 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. @@ -402,7 +427,8 @@ TailCallElim::FindTRECandidate(Instruction *TI, if (BB == &F->getEntryBlock() && FirstNonDbg(BB->front()) == CI && FirstNonDbg(llvm::next(BB->begin())) == TI && - callIsSmall(CI)) { + CI->getCalledFunction() && + !TTI->isLoweredToCall(CI->getCalledFunction())) { // A single-block function with just a call and a return. Check that // the arguments match. CallSite::arg_iterator I = CallSite(CI).arg_begin(), @@ -421,7 +447,7 @@ TailCallElim::FindTRECandidate(Instruction *TI, bool TailCallElim::EliminateRecursiveTailCall(CallInst *CI, ReturnInst *Ret, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail, - SmallVector &ArgumentPHIs, + SmallVectorImpl &ArgumentPHIs, bool CannotTailCallElimCallsMarkedTail) { // If we are introducing accumulator recursion to eliminate operations after // the call instruction that are both associative and commutative, the initial @@ -597,7 +623,7 @@ bool TailCallElim::EliminateRecursiveTailCall(CallInst *CI, ReturnInst *Ret, bool TailCallElim::FoldReturnAndProcessPred(BasicBlock *BB, ReturnInst *Ret, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail, - SmallVector &ArgumentPHIs, + SmallVectorImpl &ArgumentPHIs, bool CannotTailCallElimCallsMarkedTail) { bool Change = false; @@ -631,10 +657,11 @@ bool TailCallElim::FoldReturnAndProcessPred(BasicBlock *BB, return Change; } -bool TailCallElim::ProcessReturningBlock(ReturnInst *Ret, BasicBlock *&OldEntry, - bool &TailCallsAreMarkedTail, - SmallVector &ArgumentPHIs, - bool CannotTailCallElimCallsMarkedTail) { +bool +TailCallElim::ProcessReturningBlock(ReturnInst *Ret, BasicBlock *&OldEntry, + bool &TailCallsAreMarkedTail, + SmallVectorImpl &ArgumentPHIs, + bool CannotTailCallElimCallsMarkedTail) { CallInst *CI = FindTRECandidate(Ret, CannotTailCallElimCallsMarkedTail); if (!CI) return false;