LLVM  6.0.0svn
Macros | Functions | Variables
LoopSink.cpp File Reference
#include "llvm/Transforms/Scalar/LoopSink.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AliasSetTracker.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/BlockFrequencyInfo.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Scalar/LoopPassManager.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
Include dependency graph for LoopSink.cpp:

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. More...
 
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. More...
 
static bool sinkInstruction (Loop &L, Instruction &I, const SmallVectorImpl< BasicBlock *> &ColdLoopBBs, const SmallDenseMap< BasicBlock *, int, 16 > &LoopBlockNumber, LoopInfo &LI, DominatorTree &DT, BlockFrequencyInfo &BFI)
 
static bool sinkLoopInvariantInstructions (Loop &L, AAResults &AA, LoopInfo &LI, DominatorTree &DT, BlockFrequencyInfo &BFI, 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. More...
 
 INITIALIZE_PASS_BEGIN (LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false) Pass *llvm
 

Variables

static cl::opt< unsignedSinkFrequencyPercentThreshold ("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< unsignedMaxNumberOfUseBBsForSinking ("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 56 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 83 of file LoopSink.cpp.

References B, llvm::BlockFrequencyInfo::getBlockFreq(), SinkFrequencyPercentThreshold, and T.

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 121 of file LoopSink.cpp.

References adjustedSumFreq(), llvm::SmallPtrSetImpl< PtrType >::begin(), llvm::SmallPtrSetImplBase::clear(), llvm::DominatorTree::dominates(), llvm::SmallPtrSetImpl< PtrType >::end(), llvm::BlockFrequencyInfo::getBlockFreq(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::SmallPtrSetImpl< PtrType >::insert(), and llvm::SmallPtrSetImplBase::size().

Referenced by sinkInstruction().

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN ( LegacyLoopSinkPass  ,
"loop-sink ,
"Loop Sink"  ,
false  ,
false   
)

Definition at line 367 of file LoopSink.cpp.

◆ sinkInstruction()

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

◆ sinkLoopInvariantInstructions()

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

◆ 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."))
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."))
static

Referenced by adjustedSumFreq().