Go to the documentation of this file.
13 #ifndef LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H
14 #define LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H
38 class PostDominatorTree;
39 class TargetLibraryInfo;
126 EstimatedBlockWeight(
std::
move(
Arg.EstimatedBlockWeight)) {}
134 EstimatedBlockWeight =
std::move(
RHS.EstimatedBlockWeight);
152 unsigned IndexInSuccessors)
const;
194 return IsLikely ? LikelyProb : LikelyProb.
getCompl();
225 using SccBlockTypeMaps = std::vector<SccBlockTypeMap>;
228 SccBlockTypeMaps SccBlocks;
240 return getSccBlockType(
BB, SccNum) & Header;
245 return getSccBlockType(
BB, SccNum) & Exiting;
264 void calculateSccBlockType(
const BasicBlock *
BB,
int SccNum);
270 class BasicBlockCallbackVH final :
public CallbackVH {
273 void deleted()
override {
275 BPI->eraseBlock(cast<BasicBlock>(getValPtr()));
280 : CallbackVH(const_cast<
Value *>(V)), BPI(BPI) {}
285 using LoopData = std::pair<Loop *, int>;
289 explicit LoopBlock(
const BasicBlock *
BB,
const LoopInfo &LI,
290 const SccInfo &SccI);
294 LoopData getLoopData()
const {
return LD; }
295 Loop *getLoop()
const {
return LD.first; }
296 int getSccNum()
const {
return LD.second; }
298 bool belongsToLoop()
const {
return getLoop() || getSccNum() != -1; }
299 bool belongsToSameLoop(
const LoopBlock &LB)
const {
300 return (LB.getLoop() && getLoop() == LB.getLoop()) ||
301 (LB.getSccNum() != -1 && getSccNum() == LB.getSccNum());
306 LoopData
LD = {
nullptr, -1};
310 using LoopEdge = std::pair<const LoopBlock &, const LoopBlock &>;
312 DenseSet<BasicBlockCallbackVH, DenseMapInfo<Value*>> Handles;
316 using Edge = std::pair<const BasicBlock *, unsigned>;
318 DenseMap<Edge, BranchProbability> Probs;
323 const LoopInfo *LI =
nullptr;
326 std::unique_ptr<const SccInfo> SccI;
329 SmallDenseMap<const BasicBlock *, uint32_t> EstimatedBlockWeight;
332 SmallDenseMap<LoopData, uint32_t> EstimatedLoopWeight;
336 return LoopBlock(
BB, *LI, *SccI.get());
342 bool isLoopEnteringEdge(
const LoopEdge &Edge)
const;
346 bool isLoopExitingEdge(
const LoopEdge &Edge)
const;
349 bool isLoopEnteringExitingEdge(
const LoopEdge &Edge)
const;
352 bool isLoopBackEdge(
const LoopEdge &Edge)
const;
354 void getLoopEnterBlocks(
const LoopBlock &LB,
355 SmallVectorImpl<BasicBlock *> &Enters)
const;
357 void getLoopExitBlocks(
const LoopBlock &LB,
358 SmallVectorImpl<BasicBlock *> &Exits)
const;
362 std::optional<uint32_t> getEstimatedBlockWeight(
const BasicBlock *
BB)
const;
367 std::optional<uint32_t> getEstimatedLoopWeight(
const LoopData &L)
const;
371 std::optional<uint32_t> getEstimatedEdgeWeight(
const LoopEdge &Edge)
const;
376 template <
class IterT>
377 std::optional<uint32_t>
378 getMaxEstimatedEdgeWeight(
const LoopBlock &SrcBB,
379 iterator_range<IterT> Successors)
const;
385 bool updateEstimatedBlockWeight(LoopBlock &LoopBB,
uint32_t BBWeight,
386 SmallVectorImpl<BasicBlock *> &BlockWorkList,
387 SmallVectorImpl<LoopBlock> &LoopWorkList);
391 void propagateEstimatedBlockWeight(
const LoopBlock &LoopBB, DominatorTree *DT,
392 PostDominatorTree *PDT,
uint32_t BBWeight,
393 SmallVectorImpl<BasicBlock *> &WorkList,
394 SmallVectorImpl<LoopBlock> &LoopWorkList);
397 std::optional<uint32_t> getInitialEstimatedBlockWeight(
const BasicBlock *
BB);
400 void computeEestimateBlockWeight(
const Function &
F, DominatorTree *DT,
401 PostDominatorTree *PDT);
408 bool calcZeroHeuristics(
const BasicBlock *
BB,
const TargetLibraryInfo *TLI);
458 #endif // LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H
A set of analyses that are preserved following a run of a transformation pass.
Printer pass for the BranchProbabilityAnalysis results.
This is an optimization pass for GlobalISel generic memory operations.
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...
A CRTP mix-in to automatically provide informational APIs needed for passes.
BranchProbabilityInfo & operator=(BranchProbabilityInfo &&RHS)
bool isSCCHeader(const BasicBlock *BB, int SccNum) const
Returns true if BB is a 'header' block in SCC with SccNum ID, false otherwise.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
BranchProbabilityInfo(const Function &F, const LoopInfo &LI, const TargetLibraryInfo *TLI=nullptr, DominatorTree *DT=nullptr, PostDominatorTree *PDT=nullptr)
LLVM Basic Block Representation.
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Analysis pass which computes BranchProbabilityInfo.
Legacy analysis pass which computes BranchProbabilityInfo.
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...
BranchProbabilityInfo(BranchProbabilityInfo &&Arg)
bool isSCCExitingBlock(const BasicBlock *BB, int SccNum) const
Returns true if BB is an 'exiting' block in SCC with SccNum ID, false otherwise.
BranchProbabilityInfo & getBPI()
Analysis providing branch probability information.
BranchProbabilityInfo()=default
Represent the analysis usage information of a pass.
BranchProbabilityInfo run(Function &F, FunctionAnalysisManager &AM)
Run the analysis pass over a function and produce BPI.
This class implements an extremely fast bulk output stream that can only output to a stream.
API to communicate dependencies between analyses during invalidation.
BranchProbabilityPrinterPass(raw_ostream &OS)
static BranchProbability getBranchProbStackProtector(bool IsLikely)
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
void copyEdgeProbabilities(BasicBlock *Src, BasicBlock *Dst)
Copy outgoing edge probabilities from Src to Dst.
A special type used by analysis passes to provide an address that identifies that particular analysis...
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
@ BasicBlock
Various leaf nodes.
void eraseBlock(const BasicBlock *BB)
Forget analysis results for the given basic block.
void print(raw_ostream &OS, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
A Module instance is used to store all the information related to an LLVM module.
A CRTP mix-in that provides informational APIs needed for analysis passes.
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
void setEdgeProbability(const BasicBlock *Src, const SmallVectorImpl< BranchProbability > &Probs)
Set the raw probabilities for all edges from the given block.
BranchProbabilityInfoWrapperPass()
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
raw_ostream & printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, const BasicBlock *Dst) const
Print an edge's probability.
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
BranchProbabilityInfo & operator=(const BranchProbabilityInfo &)=delete
Provides information about what library functions are available for the current target.
void calculate(const Function &F, const LoopInfo &LI, const TargetLibraryInfo *TLI, DominatorTree *DT, PostDominatorTree *PDT)
Value handle with callbacks on RAUW and destruction.
BranchProbability getCompl() const
const BranchProbabilityInfo & getBPI() const
bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const
Test if an edge is hot relative to other out-edges of the Src.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
A container for analyses that lazily runs them and caches their results.
bool invalidate(Function &, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
FunctionPass class - This class is used to implement most global optimizations.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
int getSCCNum(const BasicBlock *BB) const
If BB belongs to some SCC then ID of that SCC is returned, otherwise -1 is returned.
SccInfo(const Function &F)