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/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")
static bool	canTRE (Function &F)
	Scan the specified function for alloca instructions.
static bool	markTails (Function &F, 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.
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 >	ForceDisableBFI ("tre-disable-entrycount-recompute", cl::init(false), cl::Hidden, cl::desc("Force disabling recomputing of function entry count, on " "successful tail recursion elimination."))
	tailcallelim
Tail Call	Elimination
Tail Call	false

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "tailcallelim"

Definition at line 87 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 344 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 377 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 100 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 )

static

Definition at line 197 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(), and llvm::successors().

STATISTIC() [1/3]

STATISTIC	(	NumAccumAdded	,
		"Number of accumulators introduced"	)

STATISTIC() [2/3]

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

STATISTIC() [3/3]

STATISTIC	(	NumRetDuped	,
		"Number of return duplicated"	)

Variable Documentation

Elimination

Tail Call Elimination

Definition at line 977 of file TailRecursionElimination.cpp.

false

Tail Call false

Definition at line 978 of file TailRecursionElimination.cpp.

ForceDisableBFI

cl::opt< bool > ForceDisableBFI("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

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

tailcallelim

tailcallelim

Definition at line 977 of file TailRecursionElimination.cpp.