LoopLoadElimination.cpp File Reference

#include "llvm/Transforms/Scalar/LoopLoadElimination.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/BlockFrequencyInfo.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/LazyBlockFrequencyInfo.h"
#include "llvm/Analysis/LoopAccessAnalysis.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/ProfileSummaryInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.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.h"
#include "llvm/Transforms/Utils/LoopVersioning.h"
#include "llvm/Transforms/Utils/SizeOpts.h"
#include <algorithm>
#include <cassert>
#include <forward_list>
#include <set>
#include <tuple>
#include <utility>

Include dependency graph for LoopLoadElimination.cpp:

Go to the source code of this file.

Macros
#define	LLE_OPTION   "loop-load-elim"
#define	DEBUG_TYPE   LLE_OPTION

Functions
	STATISTIC (NumLoopLoadEliminted, "Number of loads eliminated by LLE")
static bool	doesStoreDominatesAllLatches (BasicBlock *StoreBlock, Loop *L, DominatorTree *DT)
	Check if the store dominates all latches, so as long as there is no intervening store this value will be loaded in the next iteration. More...
static bool	isLoadConditional (LoadInst *Load, Loop *L)
	Return true if the load is not executed on all paths in the loop. More...
static bool	eliminateLoadsAcrossLoops (Function &F, LoopInfo &LI, DominatorTree &DT, BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, function_ref< const LoopAccessInfo &(Loop &)> GetLAI)

Variables
static cl::opt< unsigned >	CheckPerElim ("runtime-check-per-loop-load-elim", cl::Hidden, cl::desc("Max number of memchecks allowed per eliminated load on average"), cl::init(1))
static cl::opt< unsigned >	LoadElimSCEVCheckThreshold ("loop-load-elimination-scev-check-threshold", cl::init(8), cl::Hidden, cl::desc("The maximum number of SCEV checks allowed for Loop " "Load Elimination"))
static const char	LLE_name [] = "Loop Load Elimination"

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   LLE_OPTION

Definition at line 71 of file LoopLoadElimination.cpp.

LLE_OPTION

#define LLE_OPTION   "loop-load-elim"

Definition at line 70 of file LoopLoadElimination.cpp.

Function Documentation

doesStoreDominatesAllLatches()

static bool doesStoreDominatesAllLatches ( BasicBlock *  StoreBlock, Loop *  L, DominatorTree *  DT  )

static

Check if the store dominates all latches, so as long as there is no intervening store this value will be loaded in the next iteration.

Definition at line 146 of file LoopLoadElimination.cpp.

References llvm::all_of(), llvm::DominatorTree::dominates(), and llvm::LoopBase< BlockT, LoopT >::getLoopLatches().

Referenced by isLoadConditional().

eliminateLoadsAcrossLoops()

static bool eliminateLoadsAcrossLoops ( Function &  F, LoopInfo &  LI, DominatorTree &  DT, BlockFrequencyInfo *  BFI, ProfileSummaryInfo *  PSI, function_ref< const LoopAccessInfo &(Loop &)>  GetLAI  )

static

Definition at line 598 of file LoopLoadElimination.cpp.

References llvm::AnalysisUsage::addPreserved(), llvm::AnalysisUsage::addRequired(), llvm::AnalysisUsage::addRequiredID(), llvm::depth_first(), llvm::LoopBase< BlockT, LoopT >::empty(), llvm::LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(), llvm::PassRegistry::getPassRegistry(), llvm::ProfileSummaryInfo::hasProfileSummary(), llvm::initializeLoopLoadEliminationPass(), llvm::LoopSimplifyID, llvm::SmallVectorTemplateBase< T, bool >::push_back(), and runOnFunction().

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

isLoadConditional()

static bool isLoadConditional ( LoadInst *  Load, Loop *  L  )

static

Return true if the load is not executed on all paths in the loop.

Definition at line 156 of file LoopLoadElimination.cpp.

References llvm::PHINode::addIncoming(), assert(), B, llvm::SmallVectorTemplateCommon< T >::begin(), llvm::AMDGPUISD::BFI, C, Check(), CheckPerElim, llvm::copy_if(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::PHINode::Create(), llvm::dbgs(), doesStoreDominatesAllLatches(), llvm::dyn_cast(), llvm::SmallVectorBase::empty(), llvm::SmallPtrSetImplBase::empty(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::SCEVExpander::expandCodeFor(), F(), for(), llvm::for_each(), llvm::BasicBlock::front(), llvm::MemoryDepChecker::generateInstructionOrderMap(), llvm::RuntimePointerChecking::getChecks(), llvm::SCEVUnionPredicate::getComplexity(), llvm::Module::getDataLayout(), llvm::LoopAccessInfo::getDepChecker(), llvm::MemoryDepChecker::getDependences(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::MemoryDepChecker::getMemoryInstructions(), llvm::BasicBlock::getModule(), llvm::Value::getName(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::RuntimePointerChecking::getPointerInfo(), llvm::LoadInst::getPointerOperandType(), llvm::LoopAccessInfo::getPSE(), llvm::LoopAccessInfo::getRuntimePointerChecking(), llvm::PredicatedScalarEvolution::getSCEV(), llvm::PredicatedScalarEvolution::getSE(), llvm::Value::getType(), llvm::PredicatedScalarEvolution::getUnionPredicate(), llvm::LoopAccessInfo::hasConvergentOp(), I, if(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SCEVUnionPredicate::isAlwaysTrue(), llvm::Loop::isLoopSimplifyForm(), LLVM_DEBUG, LoadElimSCEVCheckThreshold, llvm::RuntimePointerChecking::PointerInfo::PointerValue, llvm::RuntimePointerChecking::printChecks(), llvm::SmallVectorTemplateBase< T >::push_back(), SEE, llvm::LoopVersioning::setAliasChecks(), llvm::shouldOptimizeForSize(), llvm::SmallVectorBase::size(), llvm::Sched::Source, std::swap(), llvm::transform(), and llvm::MemoryDepChecker::Dependence::Unknown.

STATISTIC()

STATISTIC	(	NumLoopLoadEliminted	,
		"Number of loads eliminated by LLE"
	)

Variable Documentation

CheckPerElim

cl::opt<unsigned> CheckPerElim("runtime-check-per-loop-load-elim", cl::Hidden, cl::desc("Max number of memchecks allowed per eliminated load on average"), cl::init(1))

static

Referenced by isLoadConditional().

LLE_name

const char LLE_name[] = "Loop Load Elimination"

static

Definition at line 672 of file LoopLoadElimination.cpp.

LoadElimSCEVCheckThreshold

cl::opt<unsigned> LoadElimSCEVCheckThreshold("loop-load-elimination-scev-check-threshold", cl::init(8), cl::Hidden, cl::desc("The maximum number of SCEV checks allowed for Loop " "Load Elimination"))

static

Referenced by isLoadConditional().