LLVM  6.0.0svn
Macros | Functions | Variables
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/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/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/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 "llvm/Transforms/Utils/Local.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 ValuegetCommonReturnValue (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 ValuecanTransformAccumulatorRecursion (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 InstructionfirstNonDbg (BasicBlock::iterator I)
 
static CallInstfindTRECandidate (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)
 
static bool foldReturnAndProcessPred (BasicBlock *BB, ReturnInst *Ret, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail, SmallVectorImpl< PHINode *> &ArgumentPHIs, bool CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *TTI, AliasAnalysis *AA, OptimizationRemarkEmitter *ORE)
 
static bool processReturningBlock (ReturnInst *Ret, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail, SmallVectorImpl< PHINode *> &ArgumentPHIs, bool CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *TTI, AliasAnalysis *AA, OptimizationRemarkEmitter *ORE)
 
static bool eliminateTailRecursion (Function &F, const TargetTransformInfo *TTI, AliasAnalysis *AA, OptimizationRemarkEmitter *ORE)
 
 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 85 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 324 of file TailRecursionElimination.cpp.

References llvm::MemoryLocation::get(), llvm::AAResults::getModRefInfo(), llvm::is_contained(), llvm::isSafeToLoadUnconditionally(), llvm::Instruction::mayHaveSideEffects(), llvm::MRI_Mod, 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 418 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

◆ eliminateRecursiveTailCall()

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

◆ eliminateTailRecursion()

static bool eliminateTailRecursion ( Function F,
const TargetTransformInfo TTI,
AliasAnalysis AA,
OptimizationRemarkEmitter ORE 
)
static

◆ findTRECandidate()

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

◆ firstNonDbg()

static Instruction* firstNonDbg ( BasicBlock::iterator  I)
static

Definition at line 438 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 
)
static

◆ 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 392 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 358 of file TailRecursionElimination.cpp.

References Arg, llvm::Function::arg_begin(), F(), llvm::CallInst::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

◆ processReturningBlock()

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

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

◆ false

Tail Call false

Definition at line 835 of file TailRecursionElimination.cpp.

◆ tailcallelim

tailcallelim

Definition at line 835 of file TailRecursionElimination.cpp.