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	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 385 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()

bool canTransformAccumulatorRecursion ( Instruction * I, CallInst * CI )

static

Definition at line 418 of file TailRecursionElimination.cpp.

References assert(), llvm::dyn_cast(), llvm::ConstantExpr::getIntrinsicIdentity(), I, II, and llvm::isa().

canTRE()

bool canTRE ( Function & F )

static

Scan the specified function for alloca instructions.

If it contains any dynamic allocas, returns false.

Definition at line 137 of file TailRecursionElimination.cpp.

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

INITIALIZE_PASS_BEGIN()

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

References INITIALIZE_PASS_DEPENDENCY.

markTails()

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

static

Definition at line 234 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(), 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 1025 of file TailRecursionElimination.cpp.

false

Tail Call false

Definition at line 1026 of file TailRecursionElimination.cpp.

tailcallelim

tailcallelim

Definition at line 1025 of file TailRecursionElimination.cpp.