LLVM: lib/Transforms/Scalar/LoopSink.cpp File Reference (original) (raw)
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. |
◆ DEBUG_TYPE
#define DEBUG_TYPE "loopsink"
◆ adjustedSumFreq()
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(), llvm::BlockFrequencyInfo::getBlockFreq(), SinkFrequencyPercentThreshold, llvm::SmallPtrSetImplBase::size(), and T.
Referenced by findBBsToSinkInto().
◆ findBBsToSinkInto()
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::SmallPtrSetImplBase::clear(), llvm::DominatorTree::dominates(), llvm::BlockFrequencyInfo::getBlockFreq(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert_range(), and llvm::SmallPtrSetImplBase::size().
Referenced by sinkInstruction().
◆ sinkInstruction()
Definition at line 186 of file LoopSink.cpp.
References A(), llvm::append_range(), llvm::ArrayRef(), assert(), B(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::MemorySSA::Beginning, llvm::cast(), llvm::cast_or_null(), llvm::MemorySSAUpdater::createMemoryAccessInBB(), llvm::dbgs(), llvm::dyn_cast(), 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::isa(), LLVM_DEBUG, MaxNumberOfUseBBsForSinking, llvm::MemorySSAUpdater::moveToPlace(), N, llvm::replaceDominatedUsesWith(), llvm::set_is_subset(), llvm::Value::setName(), llvm::SmallPtrSetImplBase::size(), llvm::SmallVectorTemplateCommon< T, typename >::size(), and llvm::sort().
Referenced by sinkLoopInvariantInstructions().
◆ sinkLoopInvariantInstructions()
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(), Changed, llvm::ScalarEvolution::forgetBlockAndLoopDispositions(), llvm::BlockFrequencyInfo::getBlockFreq(), llvm::BasicBlock::getParent(), llvm::Function::hasProfileData(), I, llvm::isa(), 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" | ) |