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/BlockFrequencyInfo.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/ProfileSummaryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/CFG.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/IRBuilder.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Module.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include <cmath>

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")
	STATISTIC (NumTREPreventedCold, "Number of tail calls/recursion eliminations prevented due to cold " "calling convention or attribute")
static bool	shouldDisableTailCallsForCold (const CallBase *CB, const Function *Caller, const ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI)
static bool	canTRE (Function &F)
	Scan the specified function for alloca instructions.
static bool	markTails (Function &F, OptimizationRemarkEmitter *ORE, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI)
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.
static bool	isUnaryAccumulatorRecurrence (Instruction *I)
static Constant *	findBaseCaseRetConstant (Function &F, Instruction *AccRecInstr)
static Constant *	canTransformAccumulatorRecursion (Instruction *I, CallInst *CI)
	INITIALIZE_PASS_BEGIN (TailCallElim, "tailcallelim", "Tail Call Elimination", false, false) INITIALIZE_PASS_END(TailCallElim

Variables
static cl::opt< bool >	DisableEntryCountRecompute ("tre-disable-entrycount-recompute", cl::init(false), cl::Hidden, cl::desc("Force disabling recomputing of function entry count, on " "successful tail recursion elimination."))
static cl::opt< bool >	DisableTailCallElimForColdCalls ("disable-tail-call-elim-for-cold-calls", cl::Hidden, cl::init(false), cl::desc("Disable tail call elimination and optimization for cold calls or " "in cold functions"))
	tailcallelim
Tail Call	Elimination
Tail Call	false

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "tailcallelim"

Definition at line 88 of file TailRecursionElimination.cpp.

Function Documentation

canMoveAboveCall()

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 394 of file TailRecursionElimination.cpp.

References DL, llvm::dyn_cast(), llvm::MemoryLocation::get(), I, II, llvm::is_contained(), llvm::isModSet(), llvm::isSafeToLoadUnconditionally(), and llvm::Instruction::mayHaveSideEffects().

canTransformAccumulatorRecursion()

Constant * canTransformAccumulatorRecursion ( Instruction * I, CallInst * CI )

static

Definition at line 501 of file TailRecursionElimination.cpp.

References assert(), findBaseCaseRetConstant(), llvm::Instruction::getFunction(), llvm::ConstantExpr::getIdentity(), I, llvm::isa(), and isUnaryAccumulatorRecurrence().

canTRE()

bool canTRE ( Function & F )

static

Scan the specified function for alloca instructions.

If it contains any dynamic allocas, returns false.

Definition at line 146 of file TailRecursionElimination.cpp.

References llvm::all_of(), llvm::dyn_cast(), F, I, and instructions.

findBaseCaseRetConstant()

Constant * findBaseCaseRetConstant ( Function & F, Instruction * AccRecInstr )

static

Definition at line 465 of file TailRecursionElimination.cpp.

References C(), llvm::dyn_cast(), and F.

Referenced by canTransformAccumulatorRecursion().

INITIALIZE_PASS_BEGIN()

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

References INITIALIZE_PASS_DEPENDENCY.

isUnaryAccumulatorRecurrence()

bool isUnaryAccumulatorRecurrence ( Instruction * I )

static

Definition at line 437 of file TailRecursionElimination.cpp.

References I, and llvm::isa().

Referenced by canTransformAccumulatorRecursion().

markTails()

bool markTails ( Function & F, OptimizationRemarkEmitter * ORE, ProfileSummaryInfo * PSI, BlockFrequencyInfo * BFI )

static

Definition at line 243 of file TailRecursionElimination.cpp.

References A(), llvm::CallBase::args(), llvm::dbgs(), DEBUG_TYPE, llvm::CallBase::doesNotAccessMemory(), llvm::dyn_cast(), llvm::OptimizationRemarkEmitter::emit(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), F, llvm::CallBase::hasOperandBundlesOtherThan(), I, II, llvm::isa(), llvm::CallInst::isNoTailCall(), llvm::CallInst::isTailCall(), LLVM_DEBUG, Modified, llvm::LLVMContext::OB_clang_arc_attachedcall, llvm::LLVMContext::OB_kcfi, llvm::LLVMContext::OB_ptrauth, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::CallInst::setTailCall(), shouldDisableTailCallsForCold(), and llvm::successors().

shouldDisableTailCallsForCold()

bool shouldDisableTailCallsForCold ( const CallBase * CB, const Function * Caller, const ProfileSummaryInfo * PSI, BlockFrequencyInfo * BFI )

static

Definition at line 107 of file TailRecursionElimination.cpp.

References llvm::CallingConv::Cold, DisableTailCallElimForColdCalls, llvm::CallBase::getCallingConv(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::CallBase::hasFnAttr(), llvm::ProfileSummaryInfo::hasProfileSummary(), llvm::ProfileSummaryInfo::isColdBlock(), llvm::ProfileSummaryInfo::isColdCallSite(), llvm::ProfileSummaryInfo::isFunctionEntryCold(), and llvm::CallBase::isMustTailCall().

Referenced by markTails().

STATISTIC() [1/4]

STATISTIC	(	NumAccumAdded	,
		"Number of accumulators introduced"	)

STATISTIC() [2/4]

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

STATISTIC() [3/4]

STATISTIC	(	NumRetDuped	,
		"Number of return duplicated"	)

STATISTIC() [4/4]

STATISTIC	(	NumTREPreventedCold	,
		"Number of tail calls/recursion eliminations prevented due to cold " "calling convention or attribute"	)

Variable Documentation

DisableEntryCountRecompute

cl::opt< bool > DisableEntryCountRecompute("tre-disable-entrycount-recompute", cl::init(false), cl::Hidden, cl::desc("Force disabling recomputing of function entry count, on " "successful tail recursion elimination.")) ( "tre-disable-entrycount-recompute" , cl::init(false) , cl::Hidden , cl::desc("Force disabling recomputing of function entry count, on " "successful tail recursion elimination.")  )

static

DisableTailCallElimForColdCalls

cl::opt< bool > DisableTailCallElimForColdCalls("disable-tail-call-elim-for-cold-calls", cl::Hidden, cl::init(false), cl::desc("Disable tail call elimination and optimization for cold calls or " "in cold functions")) ( "disable-tail-call-elim-for-cold-calls" , cl::Hidden , cl::init(false) , cl::desc("Disable tail call elimination and optimization for cold calls or " "in cold functions")  )

static

Referenced by shouldDisableTailCallsForCold().

Elimination

Tail Call Elimination

Definition at line 1145 of file TailRecursionElimination.cpp.

false

Tail Call false

Definition at line 1146 of file TailRecursionElimination.cpp.

tailcallelim

tailcallelim

Definition at line 1145 of file TailRecursionElimination.cpp.