14#ifndef LLVM_TRANSFORMS_UTILS_SAMPLEPROFILEINFERENCE_H
15#define LLVM_TRANSFORMS_UTILS_SAMPLEPROFILEINFERENCE_H
28class MachineBasicBlock;
31namespace afdo_detail {
145 using Edge = std::pair<const BasicBlockT *, const BasicBlockT *>;
153 :
F(
F), Successors(Successors), SampleBlockWeights(SampleBlockWeights) {}
161 const std::vector<const BasicBlockT *> &BasicBlocks,
167 void findUnlikelyJumps(
const std::vector<const BasicBlockT *> &BasicBlocks,
183template <
typename BT>
195 for (
const auto &BB :
F) {
205 std::vector<const BasicBlockT *> BasicBlocks;
207 BasicBlocks.reserve(Reachable.
size());
208 for (
const auto &BB :
F) {
209 if (Reachable.
count(&BB) && InverseReachable.
count(&BB)) {
210 BlockIndex[&BB] = BasicBlocks.
size();
211 BasicBlocks.push_back(&BB);
215 BlockWeights.
clear();
217 bool HasSamples =
false;
218 for (
const auto *BB : BasicBlocks) {
219 auto It = SampleBlockWeights.find(BB);
220 if (It != SampleBlockWeights.end() && It->second > 0) {
222 BlockWeights[BB] = It->second;
226 if (BasicBlocks.size() <= 1 || !HasSamples) {
232 initFunction(Func, BasicBlocks, BlockIndex);
240 for (
const auto *BB : BasicBlocks) {
241 BlockWeights[BB] = Func.Blocks[BlockIndex[BB]].Flow;
243 for (
auto &Jump : Func.Jumps) {
244 Edge E = std::make_pair(BasicBlocks[Jump.Source], BasicBlocks[Jump.Target]);
245 EdgeWeights[
E] = Jump.Flow;
250 for (
auto &
I : BlockWeights) {
254 for (
auto &
I : EdgeWeights) {
258 InverseReachable.
contains(
I.first.second));
263template <
typename BT>
265 FlowFunction &Func,
const std::vector<const BasicBlockT *> &BasicBlocks,
267 Func.Blocks.reserve(BasicBlocks.size());
269 for (
const auto *BB : BasicBlocks) {
271 if (SampleBlockWeights.find(BB) != SampleBlockWeights.end()) {
272 Block.HasUnknownWeight =
false;
273 Block.Weight = SampleBlockWeights[BB];
275 Block.HasUnknownWeight =
true;
282 for (
const auto *BB : BasicBlocks) {
283 for (
auto *Succ : Successors[BB]) {
284 if (!BlockIndex.
count(Succ))
287 Jump.Source = BlockIndex[BB];
288 Jump.Target = BlockIndex[Succ];
289 Func.Jumps.push_back(Jump);
292 for (
auto &Jump :
Func.Jumps) {
295 Func.Blocks[Src].SuccJumps.push_back(&Jump);
296 Func.Blocks[Dst].PredJumps.push_back(&Jump);
300 findUnlikelyJumps(BasicBlocks, Successors, Func);
303 for (
size_t I = 0;
I <
Func.Blocks.size();
I++) {
304 if (
Func.Blocks[
I].isEntry()) {
309 assert(
Func.Entry == 0 &&
"incorrect index of the entry block");
312 auto &EntryBlock =
Func.Blocks[
Func.Entry];
313 if (EntryBlock.Weight == 0 && !EntryBlock.HasUnknownWeight) {
314 EntryBlock.Weight = 1;
315 EntryBlock.HasUnknownWeight =
false;
319template <
typename BT>
320inline void SampleProfileInference<BT>::findUnlikelyJumps(
321 const std::vector<const BasicBlockT *> &BasicBlocks,
322 BlockEdgeMap &Successors, FlowFunction &Func) {}
325inline void SampleProfileInference<BasicBlock>::findUnlikelyJumps(
326 const std::vector<const BasicBlockT *> &BasicBlocks,
327 BlockEdgeMap &Successors, FlowFunction &Func) {
328 for (
auto &Jump :
Func.Jumps) {
329 const auto *BB = BasicBlocks[Jump.Source];
330 const auto *Succ = BasicBlocks[Jump.Target];
331 const Instruction *TI = BB->getTerminator();
334 if (Successors[BB].
size() == 2 && Successors[BB].back() == Succ) {
335 if (isa<InvokeInst>(TI)) {
336 Jump.IsUnlikely =
true;
339 const Instruction *SuccTI = Succ->getTerminator();
341 if (SuccTI->getNumSuccessors() == 0) {
342 if (isa<UnreachableInst>(SuccTI)) {
343 Jump.IsUnlikely =
true;
349template <
typename BT>
350inline bool SampleProfileInference<BT>::isExit(
const BasicBlockT *BB) {
351 return BB->succ_empty();
355inline bool SampleProfileInference<BasicBlock>::isExit(
const BasicBlock *BB) {
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
LLVM Basic Block Representation.
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
Sample profile inference pass.
DenseMap< const BasicBlockT *, SmallVector< const BasicBlockT *, 8 > > BlockEdgeMap
typename afdo_detail::TypeMap< BT >::FunctionT FunctionT
SampleProfileInference(FunctionT &F, BlockEdgeMap &Successors, BlockWeightMap &SampleBlockWeights)
typename afdo_detail::TypeMap< BT >::BasicBlockT BasicBlockT
DenseMap< const BasicBlockT *, uint64_t > BlockWeightMap
void apply(BlockWeightMap &BlockWeights, EdgeWeightMap &EdgeWeights)
Apply the profile inference algorithm for a given function.
std::pair< const BasicBlockT *, const BasicBlockT * > Edge
DenseMap< Edge, uint64_t > EdgeWeightMap
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
bool contains(ConstPtrType Ptr) const
This is an optimization pass for GlobalISel generic memory operations.
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
bool succ_empty(const Instruction *I)
iterator_range< idf_ext_iterator< T, SetTy > > inverse_depth_first_ext(const T &G, SetTy &S)
void applyFlowInference(const ProfiParams &Params, FlowFunction &Func)
Apply the profile inference algorithm for a given function and provided profi options.
A wrapper of a binary basic block.
bool isEntry() const
Check if it is the entry block in the function.
bool isExit() const
Check if it is an exit block in the function.
std::vector< FlowJump * > PredJumps
std::vector< FlowJump * > SuccJumps
A wrapper of binary function with basic blocks and jumps.
std::vector< FlowJump > Jumps
Jumps between the basic blocks.
std::vector< FlowBlock > Blocks
Basic blocks in the function.
uint64_t Entry
The index of the entry block.
A wrapper of a jump between two basic blocks.
Various thresholds and options controlling the behavior of the profile inference algorithm.
unsigned CostJumpUnknownFTInc
The cost of increasing an unknown fall-through jump's count by one.
unsigned CostBlockInc
The cost of increasing a block's count by one.
unsigned CostJumpFTInc
The cost of increasing a fall-through jump's count by one.
bool RebalanceUnknown
Evenly re-distribute flow among unknown subgraphs.
const int64_t CostUnlikely
The cost of taking an unlikely block/jump.
unsigned CostJumpDec
The cost of decreasing a jump's count by one.
bool JoinIslands
Join isolated components having positive flow.
unsigned CostBlockZeroInc
The cost of increasing a count of zero-weight block by one.
unsigned CostBlockEntryDec
The cost of decreasing the entry block's count by one.
unsigned CostJumpInc
The cost of increasing a jump's count by one.
unsigned CostJumpUnknownInc
The cost of increasing an unknown jump's count by one.
unsigned CostBlockUnknownInc
The cost of increasing an unknown block's count by one.
unsigned CostJumpFTDec
The cost of decreasing a fall-through jump's count by one.
unsigned CostBlockDec
The cost of decreasing a block's count by one.
unsigned CostBlockEntryInc
The cost of increasing the entry block's count by one.
bool EvenFlowDistribution
Evenly distribute flow when there are multiple equally likely options.