LLVM  14.0.0git
Macros | Functions | Variables
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/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/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.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/InitializePasses.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, MemorySSAUpdater *MSSAU)
 
static bool sinkLoopInvariantInstructions (Loop &L, AAResults &AA, LoopInfo &LI, DominatorTree &DT, BlockFrequencyInfo &BFI, ScalarEvolution *SE, AliasSetTracker *CurAST, MemorySSA *MSSA)
 Sinks instructions from loop's preheader to the loop body if the sum frequency of inserted copy is smaller than preheader's frequency. More...
 
static void computeAliasSet (Loop &L, BasicBlock &Preheader, AliasSetTracker &CurAST)
 
 INITIALIZE_PASS_BEGIN (LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false) Pass *llvm
 

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."))
 
static cl::opt< bool > EnableMSSAInLoopSink ("enable-mssa-in-loop-sink", cl::Hidden, cl::init(true), cl::desc("Enable MemorySSA for LoopSink in new pass manager"))
 
static cl::opt< bool > EnableMSSAInLegacyLoopSink ("enable-mssa-in-legacy-loop-sink", cl::Hidden, cl::init(false), cl::desc("Enable MemorySSA for LoopSink in legacy pass manager"))
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "loopsink"

Definition at line 59 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 94 of file LoopSink.cpp.

References B, llvm::AMDGPUISD::BFI, and SinkFrequencyPercentThreshold.

Referenced by findBBsToSinkInto().

◆ computeAliasSet()

static void computeAliasSet ( Loop L,
BasicBlock Preheader,
AliasSetTracker CurAST 
)
static

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

References adjustedSumFreq(), BB, llvm::SmallPtrSetImpl< PtrType >::begin(), llvm::AMDGPUISD::BFI, llvm::SmallPtrSetImplBase::clear(), llvm::DominatorTree::dominates(), llvm::SmallPtrSetImpl< PtrType >::end(), 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 470 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,
MemorySSAUpdater MSSAU 
)
static

◆ sinkLoopInvariantInstructions()

static bool sinkLoopInvariantInstructions ( Loop L,
AAResults AA,
LoopInfo LI,
DominatorTree DT,
BlockFrequencyInfo BFI,
ScalarEvolution SE,
AliasSetTracker CurAST,
MemorySSA MSSA 
)
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

◆ EnableMSSAInLegacyLoopSink

cl::opt<bool> EnableMSSAInLegacyLoopSink("enable-mssa-in-legacy-loop-sink", cl::Hidden, cl::init(false), cl::desc("Enable MemorySSA for LoopSink in legacy pass manager"))
static

◆ EnableMSSAInLoopSink

cl::opt<bool> EnableMSSAInLoopSink("enable-mssa-in-loop-sink", cl::Hidden, cl::init(true), cl::desc("Enable MemorySSA for LoopSink in new pass manager"))
static

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

◆ 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().