84 #define DEBUG_TYPE "tailcallelim" 86 STATISTIC(NumEliminated,
"Number of tail calls removed");
87 STATISTIC(NumRetDuped,
"Number of return duplicated");
88 STATISTIC(NumAccumAdded,
"Number of accumulators introduced");
101 struct AllocaDerivedValueTracker {
105 void walk(
Value *Root) {
109 auto AddUsesToWorklist = [&](
Value *V) {
110 for (
auto &U : V->uses()) {
111 if (!Visited.
insert(&U).second)
117 AddUsesToWorklist(Root);
119 while (!Worklist.
empty()) {
125 case Instruction::Invoke: {
129 callUsesLocalStack(CS, IsNocapture);
143 if (U->getOperandNo() == 0)
144 EscapePoints.insert(I);
147 case Instruction::BitCast:
148 case Instruction::GetElementPtr:
149 case Instruction::PHI:
151 case Instruction::AddrSpaceCast:
154 EscapePoints.insert(I);
158 AddUsesToWorklist(I);
162 void callUsesLocalStack(
CallSite CS,
bool IsNocapture) {
184 AllCallsAreTailCalls =
true;
187 AllocaDerivedValueTracker Tracker;
189 if (
Arg.hasByValAttr())
225 VisitType Escaped = UNESCAPED;
227 for (
auto &
I : *BB) {
228 if (Tracker.EscapePoints.count(&
I))
232 if (!CI || CI->
isTailCall() || isa<DbgInfoIntrinsic>(&
I))
245 bool SafeToTail =
true;
247 if (isa<Constant>(
Arg.getUser()))
249 if (
Argument *A = dyn_cast<Argument>(
Arg.getUser()))
250 if (!A->hasByValAttr())
259 <<
"marked as tail call candidate (readnone)";
267 if (!IsNoTail && Escaped == UNESCAPED && !Tracker.AllocaUsers.count(CI)) {
270 AllCallsAreTailCalls =
false;
275 auto &State = Visited[SuccBB];
276 if (State < Escaped) {
278 if (State == ESCAPED)
285 if (!WorklistEscaped.
empty()) {
290 while (!WorklistUnescaped.
empty()) {
292 if (Visited[NextBB] == UNESCAPED) {
301 for (
CallInst *CI : DeferredTails) {
302 if (Visited[CI->getParent()] != ESCAPED) {
305 DEBUG(
dbgs() <<
"Marked as tail call candidate: " << *CI <<
"\n");
309 AllCallsAreTailCalls =
false;
326 if (
LoadInst *L = dyn_cast<LoadInst>(I)) {
333 const DataLayout &DL = L->getModule()->getDataLayout();
336 L->getAlignment(), DL, L))
355 if (isa<Constant>(V))
return true;
377 if (
SwitchInst *
SI = dyn_cast<SwitchInst>(UniquePred->getTerminator()))
378 if (
SI->getCondition() == V)
390 Value *ReturnedValue =
nullptr;
394 if (RI ==
nullptr || RI == IgnoreRI)
continue;
404 if (ReturnedValue && RetOp != ReturnedValue)
406 ReturnedValue = RetOp;
408 return ReturnedValue;
417 "Associative/commutative operations should have 2 args!");
435 while (isa<DbgInfoIntrinsic>(I))
441 bool CannotTailCallElimCallsMarkedTail,
446 if (&BB->
front() == TI)
458 if (BBI == BB->
begin())
465 if (CI->
isTailCall() && CannotTailCallElimCallsMarkedTail)
482 for (; I !=
E && FI != FE; ++
I, ++FI)
483 if (*I != &*FI)
break;
484 if (I ==
E && FI == FE)
493 bool &TailCallsAreMarkedTail,
507 Value *AccumulatorRecursionEliminationInitVal =
nullptr;
515 for (++BBI; &*BBI !=
Ret; ++BBI) {
523 if ((AccumulatorRecursionEliminationInitVal =
527 AccumulatorRecursionInstr = &*BBI;
539 AccumulatorRecursionEliminationInitVal ==
nullptr &&
549 if (!AccumulatorRecursionEliminationInitVal)
559 <<
"transforming tail recursion into loop";
568 OldEntry->
setName(
"tailrecurse");
574 if (TailCallsAreMarkedTail)
577 NEBI = NewEntry->
begin(); OEBI !=
E; )
578 if (
AllocaInst *AI = dyn_cast<AllocaInst>(OEBI++))
579 if (isa<ConstantInt>(AI->getArraySize()))
580 AI->moveBefore(&*NEBI);
590 I->getName() +
".tr", InsertPos);
591 I->replaceAllUsesWith(PN);
603 if (TailCallsAreMarkedTail && !CI->
isTailCall())
617 if (AccumulatorRecursionEliminationInitVal) {
618 Instruction *AccRecInstr = AccumulatorRecursionInstr;
622 AccumulatorRecursionEliminationInitVal->
getType(),
623 std::distance(PB, PE) + 1,
"accumulator.tr", &OldEntry->
front());
634 AccPN->
addIncoming(AccumulatorRecursionEliminationInitVal, P);
658 if (
ReturnInst *RI = dyn_cast<ReturnInst>(BBI.getTerminator()))
659 RI->setOperand(0, AccPN);
683 "Trying to fold non-trivial return block");
693 if (
BranchInst *BI = dyn_cast<BranchInst>(PTI))
694 if (BI->isUnconditional())
695 UncondBranchPreds.push_back(BI);
698 while (!UncondBranchPreds.empty()) {
699 BranchInst *BI = UncondBranchPreds.pop_back_val();
703 <<
"INTO UNCOND BRANCH PRED: " << *Pred);
714 ArgumentPHIs, AA, ORE);
724 bool &TailCallsAreMarkedTail,
726 bool CannotTailCallElimCallsMarkedTail,
735 ArgumentPHIs, AA, ORE);
744 bool MadeChange =
false;
745 bool AllCallsAreTailCalls =
false;
746 MadeChange |=
markTails(F, AllCallsAreTailCalls, ORE);
747 if (!AllCallsAreTailCalls)
756 bool TailCallsAreMarkedTail =
false;
762 bool CanTRETailMarkedCall =
canTRE(F);
774 ArgumentPHIs, !CanTRETailMarkedCall,
778 TailCallsAreMarkedTail, ArgumentPHIs,
779 !CanTRETailMarkedCall, TTI, AA, ORE);
780 MadeChange |= Change;
789 for (
PHINode *PN : ArgumentPHIs) {
792 PN->replaceAllUsesWith(PNV);
793 PN->eraseFromParent();
819 F, &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F),
820 &getAnalysis<AAResultsWrapperPass>().getAAResults(),
821 &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE());
836 return new TailCallElim();
Legacy wrapper pass to provide the GlobalsAAResult object.
bool hasOperandBundles() const
Return true if this User has any operand bundles.
Return a value (possibly void), from a function.
User::op_iterator arg_iterator
The type of iterator to use when looping over actual arguments at this call site. ...
void push_back(const T &Elt)
A parsed version of the target data layout string in and methods for querying it. ...
Function * getCalledFunction() const
Return the function called, or null if this is an indirect function invocation.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents an incoming formal argument to a Function.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
iterator erase(iterator where)
Compute iterated dominance frontiers using a linear time algorithm.
This is the interface for a simple mod/ref and alias analysis over globals.
This class represents a function call, abstracting a target machine's calling convention.
Analysis pass providing the TargetTransformInfo.
static bool eliminateRecursiveTailCall(CallInst *CI, ReturnInst *Ret, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail, SmallVectorImpl< PHINode *> &ArgumentPHIs, AliasAnalysis *AA, OptimizationRemarkEmitter *ORE)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
STATISTIC(NumFunctions, "Total number of functions")
An instruction for reading from memory.
bool isSafeToLoadUnconditionally(Value *V, unsigned Align, const DataLayout &DL, Instruction *ScanFrom=nullptr, const DominatorTree *DT=nullptr)
Return true if we know that executing a load from this value cannot trap.
iterator begin()
Instruction iterator methods.
bool onlyReadsMemory() const
Determine if the call does not access or only reads memory.
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
A Use represents the edge between a Value definition and its users.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
InstrTy * getInstruction() const
void setName(const Twine &Name)
Change the name of the value.
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Type * getType() const
All values are typed, get the type of this value.
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
unsigned getDataOperandNo(Value::const_user_iterator UI) const
Given a value use iterator, return the data operand corresponding to it.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
void takeName(Value *V)
Transfer the name from V to this value.
Value * getOperand(unsigned i) const
Interval::succ_iterator succ_end(Interval *I)
bool doesNotAccessMemory() const
Determine if the call does not access memory.
const BasicBlock & getEntryBlock() const
static bool runOnFunction(Function &F, bool PostInlining)
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
Subclasses of this class are all able to terminate a basic block.
A set of analyses that are preserved following a run of a transformation pass.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM Basic Block Representation.
Conditional or Unconditional Branch instruction.
FunctionPass * createTailCallEliminationPass()
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
const Instruction & front() const
static bool isDynamicConstant(Value *V, CallInst *CI, ReturnInst *RI)
Return true if the specified value is the same when the return would exit as it was when the initial ...
static bool processReturningBlock(ReturnInst *Ret, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail, SmallVectorImpl< PHINode *> &ArgumentPHIs, bool CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *TTI, AliasAnalysis *AA, OptimizationRemarkEmitter *ORE)
A manager for alias analyses.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
bool isAssociative() const LLVM_READONLY
Return true if the instruction is associative:
Represent the analysis usage information of a pass.
Analysis pass providing a never-invalidated alias analysis result.
FunctionPass class - This class is used to implement most global optimizations.
Interval::pred_iterator pred_end(Interval *I)
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
self_iterator getIterator()
bool isDataOperand(Value::const_user_iterator UI) const
Determine whether the passed iterator points to a data operand.
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
bool doesNotCapture(unsigned OpNo) const
Determine whether this data operand is not captured.
void setTailCall(bool isTC=true)
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
iterator_range< User::op_iterator > arg_operands()
Iteration adapter for range-for loops.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
static Instruction * firstNonDbg(BasicBlock::iterator I)
static Value * getCommonReturnValue(ReturnInst *IgnoreRI, CallInst *CI)
Check to see if the function containing the specified tail call consistently returns the same runtime...
static CallInst * findTRECandidate(Instruction *TI, bool CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *TTI)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches, switches, etc.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
const InstListType & getInstList() const
Return the underlying instruction list container.
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
Module.h This file contains the declarations for the Module class.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
LLVM_NODISCARD T pop_back_val()
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
bool isCommutative() const
Return true if the instruction is commutative:
void setOperand(unsigned i, Value *Val)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
static bool foldReturnAndProcessPred(BasicBlock *BB, ReturnInst *Ret, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail, SmallVectorImpl< PHINode *> &ArgumentPHIs, bool CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *TTI, AliasAnalysis *AA, OptimizationRemarkEmitter *ORE)
FunctionType * getFunctionType() const
Returns the FunctionType for me.
void initializeTailCallElimPass(PassRegistry &)
ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc)
getModRefInfo (for call sites) - Return information about whether a particular call site modifies or ...
static bool canTRE(Function &F)
Scan the specified function for alloca instructions.
INITIALIZE_PASS_BEGIN(TailCallElim, "tailcallelim", "Tail Call Elimination", false, false) INITIALIZE_PASS_END(TailCallElim
amdgpu Simplify well known AMD library false Value Value * Arg
static bool canMoveAboveCall(Instruction *I, CallInst *CI, AliasAnalysis *AA)
Return true if it is safe to move the specified instruction from after the call to before the call...
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_NODISCARD bool empty() const
unsigned getNumArgOperands() const
Return the number of call arguments.
StringRef getValueAsString() const
Return the attribute's value as a string.
const Function * getParent() const
Return the enclosing method, or null if none.
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink 'this' from the containing function and delete it.
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
ReturnInst * FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, BasicBlock *Pred)
This method duplicates the specified return instruction into a predecessor which ends in an unconditi...
void preserve()
Mark an analysis as preserved.
Value * getReturnValue() const
Convenience accessor. Returns null if there is no return value.
bool callsFunctionThatReturnsTwice() const
callsFunctionThatReturnsTwice - Return true if the function has a call to setjmp or other function th...
static Value * canTransformAccumulatorRecursion(Instruction *I, CallInst *CI)
If the specified instruction can be transformed using accumulator recursion elimination, return the constant which is the start of the accumulator value.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Value * getArgOperand(unsigned i) const
getArgOperand/setArgOperand - Return/set the i-th call argument.
Module * getParent()
Get the module that this global value is contained inside of...
LLVM Value Representation.
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
bool hasOneUse() const
Return true if there is exactly one user of this value.
bool isNoTailCall() const
static bool eliminateTailRecursion(Function &F, const TargetTransformInfo *TTI, AliasAnalysis *AA, OptimizationRemarkEmitter *ORE)
inst_range instructions(Function *F)
A container for analyses that lazily runs them and caches their results.
const Instruction * getFirstNonPHIOrDbg() const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic...
bool isStaticAlloca() const
Return true if this alloca is in the entry block of the function and is a constant size...
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
const TerminatorInst * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
static bool markTails(Function &F, bool &AllCallsAreTailCalls, OptimizationRemarkEmitter *ORE)
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
iterator_range< arg_iterator > args()
const BasicBlock * getParent() const
an instruction to allocate memory on the stack
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.