LoopSink.cpp File Reference

#include "llvm/Transforms/Scalar/LoopSink.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/BlockFrequencyInfo.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "loopsink"

Functions
	STATISTIC (NumLoopSunk, "Number of instructions sunk into loop")
	STATISTIC (NumLoopSunkCloned, "Number of cloned instructions sunk into loop")
static BlockFrequency	adjustedSumFreq (SmallPtrSetImpl< BasicBlock * > &BBs, BlockFrequencyInfo &BFI)
	Return adjusted total frequency of BBs.
static SmallPtrSet< BasicBlock *, 2 >	findBBsToSinkInto (const Loop &L, const SmallPtrSetImpl< BasicBlock * > &UseBBs, const SmallVectorImpl< BasicBlock * > &ColdLoopBBs, DominatorTree &DT, BlockFrequencyInfo &BFI)
	Return a set of basic blocks to insert sinked instructions.
static bool	sinkInstruction (Loop &L, Instruction &I, const SmallVectorImpl< BasicBlock * > &ColdLoopBBs, const SmallDenseMap< BasicBlock *, int, 16 > &LoopBlockNumber, LoopInfo &LI, DominatorTree &DT, BlockFrequencyInfo &BFI, MemorySSAUpdater *MSSAU)
static bool	sinkLoopInvariantInstructions (Loop &L, AAResults &AA, LoopInfo &LI, DominatorTree &DT, BlockFrequencyInfo &BFI, MemorySSA &MSSA, ScalarEvolution *SE)
	Sinks instructions from loop's preheader to the loop body if the sum frequency of inserted copy is smaller than preheader's frequency.

Variables
static cl::opt< unsigned >	SinkFrequencyPercentThreshold ("sink-freq-percent-threshold", cl::Hidden, cl::init(90), cl::desc("Do not sink instructions that require cloning unless they " "execute less than this percent of the time."))
static cl::opt< unsigned >	MaxNumberOfUseBBsForSinking ("max-uses-for-sinking", cl::Hidden, cl::init(30), cl::desc("Do not sink instructions that have too many uses."))

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "loopsink"

Definition at line 51 of file LoopSink.cpp.

Function Documentation

adjustedSumFreq()

static BlockFrequency adjustedSumFreq ( SmallPtrSetImpl< BasicBlock * > &  BBs, BlockFrequencyInfo &  BFI  )

static

Return adjusted total frequency of BBs.

• If there is only one BB, sinking instruction will not introduce code size increase. Thus there is no need to adjust the frequency.
• If there are more than one BB, sinking would lead to code size increase. In this case, we add some "tax" to the total frequency to make it harder to sink. E.g. Freq(Preheader) = 100 Freq(BBs) = sum(50, 49) = 99 Even if Freq(BBs) < Freq(Preheader), we will not sink from Preheade to BBs as the difference is too small to justify the code size increase. To model this, The adjusted Freq(BBs) will be: AdjustedFreq(BBs) = 99 / SinkFrequencyPercentThreshold%

Definition at line 78 of file LoopSink.cpp.

References B, SinkFrequencyPercentThreshold, and llvm::SmallPtrSetImplBase::size().

Referenced by findBBsToSinkInto().

findBBsToSinkInto()

static SmallPtrSet< BasicBlock *, 2 > findBBsToSinkInto ( const Loop &  L, const SmallPtrSetImpl< BasicBlock * > &  UseBBs, const SmallVectorImpl< BasicBlock * > &  ColdLoopBBs, DominatorTree &  DT, BlockFrequencyInfo &  BFI  )

static

Return a set of basic blocks to insert sinked instructions.

The returned set of basic blocks (BBsToSinkInto) should satisfy:

• Inside the loop L
• For each UseBB in UseBBs, there is at least one BB in BBsToSinkInto that domintates the UseBB
• Has minimum total frequency that is no greater than preheader frequency

The purpose of the function is to find the optimal sinking points to minimize execution cost, which is defined as "sum of frequency of BBsToSinkInto". As a result, the returned BBsToSinkInto needs to have minimum total frequency. Additionally, if the total frequency of BBsToSinkInto exceeds preheader frequency, the optimal solution is not sinking (return empty set).

ColdLoopBBs is used to help find the optimal sinking locations. It stores a list of BBs that is:

• Inside the loop L
• Has a frequency no larger than the loop's preheader
• Sorted by BB frequency

The complexity of the function is O(UseBBs.size() * ColdLoopBBs.size()). To avoid expensive computation, we cap the maximum UseBBs.size() in its caller.

Definition at line 116 of file LoopSink.cpp.

References adjustedSumFreq(), llvm::SmallPtrSetImpl< PtrType >::begin(), llvm::SmallPtrSetImplBase::clear(), llvm::DominatorTree::dominates(), llvm::SmallPtrSetImpl< PtrType >::end(), llvm::SmallPtrSetImpl< PtrType >::insert(), and llvm::SmallPtrSetImplBase::size().

Referenced by sinkInstruction().

sinkInstruction()

static bool sinkInstruction ( Loop &  L, Instruction &  I, const SmallVectorImpl< BasicBlock * > &  ColdLoopBBs, const SmallDenseMap< BasicBlock *, int, 16 > &  LoopBlockNumber, LoopInfo &  LI, DominatorTree &  DT, BlockFrequencyInfo &  BFI, MemorySSAUpdater *  MSSAU  )

static

Definition at line 186 of file LoopSink.cpp.

References A, llvm::append_range(), assert(), B, llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::MemorySSA::Beginning, llvm::MemorySSAUpdater::createMemoryAccessInBB(), llvm::dbgs(), llvm::SmallPtrSetImplBase::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), findBBsToSinkInto(), llvm::BasicBlock::getFirstInsertionPt(), llvm::PHINode::getIncomingBlock(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::MemorySSA::getMemoryAccess(), llvm::MemorySSAUpdater::getMemorySSA(), llvm::Value::getName(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::Instruction::insertBefore(), llvm::MemorySSAUpdater::insertDef(), llvm::MemorySSAUpdater::insertUse(), LLVM_DEBUG, MaxNumberOfUseBBsForSinking, llvm::MemorySSAUpdater::moveToPlace(), N, llvm::replaceDominatedUsesWith(), llvm::set_is_subset(), llvm::Value::setName(), llvm::SmallPtrSetImplBase::size(), llvm::SmallVectorBase< Size_T >::size(), and llvm::sort().

Referenced by sinkLoopInvariantInstructions().

sinkLoopInvariantInstructions()

static bool sinkLoopInvariantInstructions ( Loop &  L, AAResults &  AA, LoopInfo &  LI, DominatorTree &  DT, BlockFrequencyInfo &  BFI, MemorySSA &  MSSA, ScalarEvolution *  SE  )

static

Sinks instructions from loop's preheader to the loop body if the sum frequency of inserted copy is smaller than preheader's frequency.

Definition at line 297 of file LoopSink.cpp.

References A, llvm::all_of(), assert(), B, llvm::canSinkOrHoistInst(), llvm::ScalarEvolution::forgetBlockAndLoopDispositions(), llvm::BasicBlock::getParent(), llvm::Function::hasProfileData(), I, llvm::make_early_inc_range(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::reverse(), sinkInstruction(), and llvm::stable_sort().

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

STATISTIC() [1/2]

STATISTIC	(	NumLoopSunk	,
		"Number of instructions sunk into loop"
	)

STATISTIC() [2/2]

STATISTIC	(	NumLoopSunkCloned	,
		"Number of cloned instructions sunk into loop"
	)

Variable Documentation

MaxNumberOfUseBBsForSinking

cl::opt< unsigned > MaxNumberOfUseBBsForSinking("max-uses-for-sinking", cl::Hidden, cl::init(30), cl::desc("Do not sink instructions that have too many uses.")) ( "max-uses-for-sinking"  , cl::Hidden  , cl::init(30)  , cl::desc("Do not sink instructions that have too many uses.")    )

static

Referenced by sinkInstruction().

SinkFrequencyPercentThreshold

cl::opt< unsigned > SinkFrequencyPercentThreshold("sink-freq-percent-threshold", cl::Hidden, cl::init(90), cl::desc("Do not sink instructions that require cloning unless they " "execute less than this percent of the time.")) ( "sink-freq-percent-threshold"  , cl::Hidden  , cl::init(90)  , cl::desc("Do not sink instructions that require cloning unless they " "execute less than this percent of the time.")    )

static

Referenced by adjustedSumFreq().