TailRecursionElimination.cpp File Reference

#include "llvm/Transforms/Scalar/TailRecursionElimination.h"
#include "ScalarOptions.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/BlockFrequencyInfo.h"
#include "llvm/Analysis/BlockFrequencyInfoImpl.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/MDBuilder.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/ProfDataUtils.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/BlockFrequency.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 ScalarOptions &Opts, 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	returnsCurrentFrameAddress (const IntrinsicInst *II)
	Returns true if II returns an address in the current function's frame.
static bool	markTails (const ScalarOptions &Opts, 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)
	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 92 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 420 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().

canTRE()

bool canTRE ( Function & F )

static

Scan the specified function for alloca instructions.

If it contains any dynamic allocas, returns false.

Definition at line 141 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.

isUnaryAccumulatorRecurrence()

bool isUnaryAccumulatorRecurrence ( Instruction * I )

static

Definition at line 463 of file TailRecursionElimination.cpp.

References I, and llvm::isa().

markTails()

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

static

Definition at line 265 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, instructions, 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(), returnsCurrentFrameAddress(), llvm::CallInst::setTailCall(), shouldDisableTailCallsForCold(), and llvm::successors().

returnsCurrentFrameAddress()

bool returnsCurrentFrameAddress ( const IntrinsicInst * II )

static

Returns true if II returns an address in the current function's frame.

Definition at line 245 of file TailRecursionElimination.cpp.

References llvm::cast(), and II.

Referenced by markTails().

shouldDisableTailCallsForCold()

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

static

Definition at line 101 of file TailRecursionElimination.cpp.

References llvm::CallingConv::Cold, 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

Elimination

Tail Call Elimination

Definition at line 1218 of file TailRecursionElimination.cpp.

false

Tail Call false

Definition at line 1219 of file TailRecursionElimination.cpp.

tailcallelim

tailcallelim

Definition at line 1218 of file TailRecursionElimination.cpp.