13#ifndef LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H
14#define LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H
38class PostDominatorTree;
39class TargetLibraryInfo;
127 EstimatedBlockWeight(
std::
move(Arg.EstimatedBlockWeight)) {
128 for (
auto &Handle : Handles)
137 Handles = std::move(
RHS.Handles);
138 Probs = std::move(
RHS.Probs);
139 EstimatedBlockWeight = std::move(
RHS.EstimatedBlockWeight);
140 for (
auto &Handle : Handles)
159 unsigned IndexInSuccessors)
const;
204 return IsLikely ? LikelyProb : LikelyProb.
getCompl();
235 using SccBlockTypeMaps = std::vector<SccBlockTypeMap>;
238 SccBlockTypeMaps SccBlocks;
250 return getSccBlockType(BB, SccNum) & Header;
255 return getSccBlockType(BB, SccNum) & Exiting;
274 void calculateSccBlockType(
const BasicBlock *BB,
int SccNum);
280 class BasicBlockCallbackVH final :
public CallbackVH {
283 void deleted()
override {
285 BPI->eraseBlock(cast<BasicBlock>(
getValPtr()));
297 using LoopData = std::pair<Loop *, int>;
301 explicit LoopBlock(
const BasicBlock *BB,
const LoopInfo &LI,
302 const SccInfo &SccI);
304 const BasicBlock *getBlock()
const {
return BB; }
306 LoopData getLoopData()
const {
return LD; }
307 Loop *getLoop()
const {
return LD.first; }
308 int getSccNum()
const {
return LD.second; }
310 bool belongsToLoop()
const {
return getLoop() || getSccNum() != -1; }
311 bool belongsToSameLoop(
const LoopBlock &LB)
const {
312 return (LB.getLoop() && getLoop() == LB.getLoop()) ||
313 (LB.getSccNum() != -1 && getSccNum() == LB.getSccNum());
318 LoopData
LD = {
nullptr, -1};
322 using LoopEdge = std::pair<const LoopBlock &, const LoopBlock &>;
324 DenseSet<BasicBlockCallbackVH, DenseMapInfo<Value*>> Handles;
328 using Edge = std::pair<const BasicBlock *, unsigned>;
330 DenseMap<Edge, BranchProbability> Probs;
335 const LoopInfo *LI =
nullptr;
338 std::unique_ptr<const SccInfo> SccI;
341 SmallDenseMap<const BasicBlock *, uint32_t> EstimatedBlockWeight;
344 SmallDenseMap<LoopData, uint32_t> EstimatedLoopWeight;
347 LoopBlock getLoopBlock(
const BasicBlock *BB)
const {
348 return LoopBlock(BB, *LI, *SccI);
354 bool isLoopEnteringEdge(
const LoopEdge &Edge)
const;
358 bool isLoopExitingEdge(
const LoopEdge &Edge)
const;
361 bool isLoopEnteringExitingEdge(
const LoopEdge &Edge)
const;
364 bool isLoopBackEdge(
const LoopEdge &Edge)
const;
366 void getLoopEnterBlocks(
const LoopBlock &LB,
367 SmallVectorImpl<BasicBlock *> &Enters)
const;
369 void getLoopExitBlocks(
const LoopBlock &LB,
370 SmallVectorImpl<BasicBlock *> &Exits)
const;
374 std::optional<uint32_t> getEstimatedBlockWeight(
const BasicBlock *BB)
const;
379 std::optional<uint32_t> getEstimatedLoopWeight(
const LoopData &L)
const;
383 std::optional<uint32_t> getEstimatedEdgeWeight(
const LoopEdge &Edge)
const;
388 template <
class IterT>
389 std::optional<uint32_t>
390 getMaxEstimatedEdgeWeight(
const LoopBlock &SrcBB,
391 iterator_range<IterT> Successors)
const;
397 bool updateEstimatedBlockWeight(LoopBlock &LoopBB,
uint32_t BBWeight,
398 SmallVectorImpl<BasicBlock *> &BlockWorkList,
399 SmallVectorImpl<LoopBlock> &LoopWorkList);
403 void propagateEstimatedBlockWeight(
const LoopBlock &LoopBB, DominatorTree *DT,
404 PostDominatorTree *PDT,
uint32_t BBWeight,
405 SmallVectorImpl<BasicBlock *> &WorkList,
406 SmallVectorImpl<LoopBlock> &LoopWorkList);
409 std::optional<uint32_t> getInitialEstimatedBlockWeight(
const BasicBlock *BB);
412 void computeEestimateBlockWeight(
const Function &
F, DominatorTree *DT,
413 PostDominatorTree *PDT);
417 bool calcEstimatedHeuristics(
const BasicBlock *BB);
418 bool calcMetadataWeights(
const BasicBlock *BB);
419 bool calcPointerHeuristics(
const BasicBlock *BB);
420 bool calcZeroHeuristics(
const BasicBlock *BB,
const TargetLibraryInfo *TLI);
421 bool calcFloatingPointHeuristics(
const BasicBlock *BB);
This file defines DenseMapInfo traits for DenseMap.
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This header defines various interfaces for pass management in LLVM.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
API to communicate dependencies between analyses during invalidation.
A container for analyses that lazily runs them and caches their results.
Represent the analysis usage information of a pass.
LLVM Basic Block Representation.
Analysis pass which computes BranchProbabilityInfo.
BranchProbabilityInfo run(Function &F, FunctionAnalysisManager &AM)
Run the analysis pass over a function and produce BPI.
Legacy analysis pass which computes BranchProbabilityInfo.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
const BranchProbabilityInfo & getBPI() const
BranchProbabilityInfoWrapperPass()
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void print(raw_ostream &OS, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
BranchProbabilityInfo & getBPI()
bool isSCCHeader(const BasicBlock *BB, int SccNum) const
Returns true if BB is a 'header' block in SCC with SccNum ID, false otherwise.
void getSccEnterBlocks(int SccNum, SmallVectorImpl< BasicBlock * > &Enters) const
Fills in Enters vector with all such blocks that don't belong to SCC with SccNum ID but there is an e...
bool isSCCExitingBlock(const BasicBlock *BB, int SccNum) const
Returns true if BB is an 'exiting' block in SCC with SccNum ID, false otherwise.
void getSccExitBlocks(int SccNum, SmallVectorImpl< BasicBlock * > &Exits) const
Fills in Exits vector with all such blocks that don't belong to SCC with SccNum ID but there is an ed...
int getSCCNum(const BasicBlock *BB) const
If BB belongs to some SCC then ID of that SCC is returned, otherwise -1 is returned.
Analysis providing branch probability information.
void eraseBlock(const BasicBlock *BB)
Forget analysis results for the given basic block.
void setEdgeProbability(const BasicBlock *Src, const SmallVectorImpl< BranchProbability > &Probs)
Set the raw probabilities for all edges from the given block.
BranchProbabilityInfo(const BranchProbabilityInfo &)=delete
bool invalidate(Function &, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
static BranchProbability getBranchProbStackProtector(bool IsLikely)
void calculate(const Function &F, const LoopInfo &LI, const TargetLibraryInfo *TLI, DominatorTree *DT, PostDominatorTree *PDT)
BranchProbabilityInfo & operator=(BranchProbabilityInfo &&RHS)
BranchProbabilityInfo()=default
bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const
Test if an edge is hot relative to other out-edges of the Src.
void swapSuccEdgesProbabilities(const BasicBlock *Src)
Swap outgoing edges probabilities for Src with branch terminator.
BranchProbabilityInfo(BranchProbabilityInfo &&Arg)
void print(raw_ostream &OS) const
BranchProbabilityInfo(const Function &F, const LoopInfo &LI, const TargetLibraryInfo *TLI=nullptr, DominatorTree *DT=nullptr, PostDominatorTree *PDT=nullptr)
BranchProbabilityInfo & operator=(const BranchProbabilityInfo &)=delete
raw_ostream & printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, const BasicBlock *Dst) const
Print an edge's probability.
void copyEdgeProbabilities(BasicBlock *Src, BasicBlock *Dst)
Copy outgoing edge probabilities from Src to Dst.
Printer pass for the BranchProbabilityAnalysis results.
BranchProbabilityPrinterPass(raw_ostream &OS)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
BranchProbability getCompl() const
Value handle with callbacks on RAUW and destruction.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
FunctionPass class - This class is used to implement most global optimizations.
A Module instance is used to store all the information related to an LLVM module.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
A set of analyses that are preserved following a run of a transformation pass.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Provides information about what library functions are available for the current target.
Value * getValPtr() const
This class implements an extremely fast bulk output stream that can only output to a stream.
@ BasicBlock
Various leaf nodes.
This is an optimization pass for GlobalISel generic memory operations.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Implement std::hash so that hash_code can be used in STL containers.
A CRTP mix-in that provides informational APIs needed for analysis passes.
A special type used by analysis passes to provide an address that identifies that particular analysis...
A CRTP mix-in to automatically provide informational APIs needed for passes.