TailRecursionElimination.cpp File Reference

#include "llvm/Transforms/Scalar/TailRecursionElimination.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/CaptureTracking.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/InlineCost.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#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/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"

Include dependency graph for TailRecursionElimination.cpp:

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "tailcallelim"

Functions
	STATISTIC (NumEliminated, "Number of tail calls removed")
	STATISTIC (NumRetDuped, "Number of return duplicated")
	STATISTIC (NumAccumAdded, "Number of accumulators introduced")
static bool	canTRE (Function &F)
	Scan the specified function for alloca instructions. More...
static bool	markTails (Function &F, bool &AllCallsAreTailCalls, OptimizationRemarkEmitter *ORE)
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, assuming that all instructions between the call and this instruction are movable. More...
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 iteration of the recursive function was executed. More...
static Value *	getCommonReturnValue (ReturnInst *IgnoreRI, CallInst *CI)
	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. More...
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. More...
static Instruction *	firstNonDbg (BasicBlock::iterator I)
static CallInst *	findTRECandidate (Instruction *TI, bool CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *TTI)
static bool	eliminateRecursiveTailCall (CallInst *CI, ReturnInst *Ret, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail, SmallVectorImpl< PHINode *> &ArgumentPHIs, AliasAnalysis *AA, OptimizationRemarkEmitter *ORE, DomTreeUpdater &DTU)
static bool	foldReturnAndProcessPred (BasicBlock *BB, ReturnInst *Ret, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail, SmallVectorImpl< PHINode *> &ArgumentPHIs, bool CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *TTI, AliasAnalysis *AA, OptimizationRemarkEmitter *ORE, DomTreeUpdater &DTU)
static bool	processReturningBlock (ReturnInst *Ret, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail, SmallVectorImpl< PHINode *> &ArgumentPHIs, bool CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *TTI, AliasAnalysis *AA, OptimizationRemarkEmitter *ORE, DomTreeUpdater &DTU)
static bool	eliminateTailRecursion (Function &F, const TargetTransformInfo *TTI, AliasAnalysis *AA, OptimizationRemarkEmitter *ORE, DomTreeUpdater &DTU)
	INITIALIZE_PASS_BEGIN (TailCallElim, "tailcallelim", "Tail Call Elimination", false, false) INITIALIZE_PASS_END(TailCallElim

Variables
	tailcallelim
Tail Call	Elimination
Tail Call	false

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "tailcallelim"

Definition at line 86 of file TailRecursionElimination.cpp.

Referenced by eliminateRecursiveTailCall(), and markTails().

Function Documentation

canMoveAboveCall()

static bool canMoveAboveCall ( Instruction *  I, CallInst *  CI, AliasAnalysis *  AA  )

static

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.

Definition at line 328 of file TailRecursionElimination.cpp.

References llvm::MemoryLocation::get(), llvm::AAResults::getModRefInfo(), llvm::is_contained(), llvm::isModSet(), llvm::isSafeToLoadUnconditionally(), llvm::Instruction::mayHaveSideEffects(), and llvm::User::operands().

Referenced by eliminateRecursiveTailCall().

canTransformAccumulatorRecursion()

static Value* canTransformAccumulatorRecursion ( Instruction *  I, CallInst *  CI  )

static

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.

Definition at line 422 of file TailRecursionElimination.cpp.

References assert(), getCommonReturnValue(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::Value::hasOneUse(), llvm::Instruction::isAssociative(), llvm::Instruction::isCommutative(), and llvm::Instruction::user_back().

Referenced by eliminateRecursiveTailCall().

canTRE()

static bool canTRE ( Function &  F )

static

Scan the specified function for alloca instructions.

If it contains any dynamic allocas, returns false.

Definition at line 94 of file TailRecursionElimination.cpp.

References llvm::all_of(), llvm::MCID::Call, llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, CallBrTy, IterTy >::doesNotCapture(), llvm::dyn_cast(), llvm::SmallVectorBase::empty(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, CallBrTy, IterTy >::getArgumentNo(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, CallBrTy, IterTy >::getDataOperandNo(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, CallBrTy, IterTy >::getInstruction(), llvm::Instruction::getOpcode(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::instructions(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, CallBrTy, IterTy >::isArgOperand(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, CallBrTy, IterTy >::isByValArgument(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, CallBrTy, IterTy >::isDataOperand(), llvm::AllocaInst::isStaticAlloca(), llvm::SPII::Load, llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, CallBrTy, IterTy >::onlyReadsMemory(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::MCID::Select, and llvm::SPII::Store.

Referenced by eliminateTailRecursion().

eliminateRecursiveTailCall()

static bool eliminateRecursiveTailCall ( CallInst *  CI, ReturnInst *  Ret, BasicBlock *&  OldEntry, bool &  TailCallsAreMarkedTail, SmallVectorImpl< PHINode *> &  ArgumentPHIs, AliasAnalysis *  AA, OptimizationRemarkEmitter *  ORE, DomTreeUpdater &  DTU  )

static

Definition at line 499 of file TailRecursionElimination.cpp.

References llvm::PHINode::addIncoming(), llvm::DomTreeUpdater::applyUpdates(), llvm::Function::arg_begin(), llvm::Function::arg_end(), llvm::BasicBlock::begin(), canMoveAboveCall(), canTransformAccumulatorRecursion(), llvm::BasicBlock::Create(), llvm::PHINode::Create(), llvm::BranchInst::Create(), DEBUG_TYPE, E, llvm::OptimizationRemarkEmitter::emit(), llvm::BasicBlock::end(), llvm::iplist_impl< IntrusiveListT, TraitsT >::erase(), F(), llvm::BasicBlock::front(), llvm::CallBase::getArgOperand(), getCommonReturnValue(), llvm::Function::getContext(), llvm::Instruction::getDebugLoc(), llvm::Function::getEntryBlock(), llvm::BasicBlock::getInstList(), llvm::CallBase::getNumArgOperands(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::ReturnInst::getReturnValue(), llvm::Value::getType(), I, llvm::DominatorTreeBase< BasicBlock, false >::Insert, isDynamicConstant(), llvm::CallInst::isTailCall(), P, llvm::pred_begin(), llvm::pred_end(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::DomTreeUpdater::recalculate(), llvm::MipsISD::Ret, llvm::Instruction::setDebugLoc(), llvm::Value::setName(), llvm::User::setOperand(), and llvm::Value::takeName().

Referenced by foldReturnAndProcessPred(), and processReturningBlock().

eliminateTailRecursion()

static bool eliminateTailRecursion ( Function &  F, const TargetTransformInfo *  TTI, AliasAnalysis *  AA, OptimizationRemarkEmitter *  ORE, DomTreeUpdater &  DTU  )

static

Definition at line 748 of file TailRecursionElimination.cpp.

References llvm::AnalysisUsage::addPreserved(), llvm::AnalysisUsage::addRequired(), llvm::Function::begin(), canTRE(), E, llvm::DomTreeUpdater::Eager, llvm::Function::end(), F(), foldReturnAndProcessPred(), llvm::Module::getDataLayout(), llvm::BasicBlock::getFirstNonPHIOrDbg(), llvm::Function::getFnAttribute(), llvm::Function::getFunctionType(), llvm::GlobalValue::getParent(), llvm::PassRegistry::getPassRegistry(), llvm::BasicBlock::getTerminator(), llvm::Attribute::getValueAsString(), INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_DEPENDENCY, llvm::initializeTailCallElimPass(), llvm::FunctionType::isVarArg(), markTails(), processReturningBlock(), llvm::MipsISD::Ret, runOnFunction(), and llvm::SimplifyInstruction().

Referenced by llvm::TailCallElimPass::run().

findTRECandidate()

static CallInst* findTRECandidate ( Instruction *  TI, bool  CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *  TTI  )

static

Definition at line 448 of file TailRecursionElimination.cpp.

References llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, CallBrTy, IterTy >::arg_begin(), llvm::Function::arg_begin(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, CallBrTy, IterTy >::arg_end(), llvm::Function::arg_end(), llvm::BasicBlock::begin(), llvm::dyn_cast(), E, F(), firstNonDbg(), llvm::BasicBlock::front(), llvm::CallBase::getCalledFunction(), llvm::Function::getEntryBlock(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), I, llvm::TargetTransformInfo::isLoweredToCall(), and llvm::CallInst::isTailCall().

Referenced by foldReturnAndProcessPred(), and processReturningBlock().

firstNonDbg()

static Instruction* firstNonDbg ( BasicBlock::iterator  I )

static

Definition at line 442 of file TailRecursionElimination.cpp.

References I.

Referenced by findTRECandidate().

foldReturnAndProcessPred()

static bool foldReturnAndProcessPred ( BasicBlock *  BB, ReturnInst *  Ret, BasicBlock *&  OldEntry, bool &  TailCallsAreMarkedTail, SmallVectorImpl< PHINode *> &  ArgumentPHIs, bool  CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *  TTI, AliasAnalysis *  AA, OptimizationRemarkEmitter *  ORE, DomTreeUpdater &  DTU  )

static

Definition at line 686 of file TailRecursionElimination.cpp.

References assert(), llvm::dbgs(), llvm::DomTreeUpdater::deleteBB(), E, eliminateRecursiveTailCall(), findTRECandidate(), llvm::FoldReturnIntoUncondBranch(), llvm::BasicBlock::getFirstNonPHIOrDbg(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), llvm::BasicBlock::hasAddressTaken(), LLVM_DEBUG, llvm::pred_begin(), and llvm::pred_end().

Referenced by eliminateTailRecursion().

getCommonReturnValue()

static Value* getCommonReturnValue ( ReturnInst *  IgnoreRI, CallInst *  CI  )

static

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.

Definition at line 396 of file TailRecursionElimination.cpp.

References llvm::dyn_cast(), F(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), and isDynamicConstant().

Referenced by canTransformAccumulatorRecursion(), and eliminateRecursiveTailCall().

INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	TailCallElim	,
		"tailcallelim"	,
		"Tail Call Elimination"	,
		false	,
		false
	)

Referenced by eliminateTailRecursion().

isDynamicConstant()

static bool isDynamicConstant ( Value *  V, CallInst *  CI, ReturnInst *  RI  )

static

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.

Definition at line 362 of file TailRecursionElimination.cpp.

References Arg, llvm::Function::arg_begin(), F(), llvm::CallBase::getArgOperand(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::BasicBlock::getUniquePredecessor(), and SI.

Referenced by eliminateRecursiveTailCall(), and getCommonReturnValue().

markTails()

static bool markTails ( Function &  F, bool &  AllCallsAreTailCalls, OptimizationRemarkEmitter *  ORE  )

static

Definition at line 188 of file TailRecursionElimination.cpp.

References Arg, llvm::CallBase::arg_operands(), llvm::Function::args(), llvm::Function::callsFunctionThatReturnsTwice(), llvm::dbgs(), DEBUG_TYPE, llvm::CallBase::doesNotAccessMemory(), llvm::dyn_cast(), llvm::OptimizationRemarkEmitter::emit(), llvm::SmallVectorBase::empty(), llvm::CallBase::hasOperandBundles(), I, llvm::CallInst::isNoTailCall(), llvm::CallInst::isTailCall(), LLVM_DEBUG, llvm::make_range(), Modified, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::CallInst::setTailCall(), llvm::succ_begin(), and llvm::succ_end().

Referenced by eliminateTailRecursion().

processReturningBlock()

static bool processReturningBlock ( ReturnInst *  Ret, BasicBlock *&  OldEntry, bool &  TailCallsAreMarkedTail, SmallVectorImpl< PHINode *> &  ArgumentPHIs, bool  CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *  TTI, AliasAnalysis *  AA, OptimizationRemarkEmitter *  ORE, DomTreeUpdater &  DTU  )

static

Definition at line 735 of file TailRecursionElimination.cpp.

References eliminateRecursiveTailCall(), and findTRECandidate().

Referenced by eliminateTailRecursion().

STATISTIC() [1/3]

STATISTIC	(	NumEliminated	,
		"Number of tail calls removed"
	)

STATISTIC() [2/3]

STATISTIC	(	NumRetDuped	,
		"Number of return duplicated"
	)

STATISTIC() [3/3]

STATISTIC	(	NumAccumAdded	,
		"Number of accumulators introduced"
	)

Variable Documentation

Elimination

Tail Call Elimination

Definition at line 853 of file TailRecursionElimination.cpp.

false

Tail Call false

Definition at line 853 of file TailRecursionElimination.cpp.

tailcallelim

tailcallelim

Definition at line 853 of file TailRecursionElimination.cpp.