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;
361 Optional<uint32_t> getEstimatedBlockWeight(
const BasicBlock *
BB)
const;
366 Optional<uint32_t> getEstimatedLoopWeight(
const LoopData &L)
const;
370 Optional<uint32_t> getEstimatedEdgeWeight(
const LoopEdge &Edge)
const;
375 template <
class IterT>
377 getMaxEstimatedEdgeWeight(
const LoopBlock &SrcBB,
378 iterator_range<IterT> Successors)
const;
384 bool updateEstimatedBlockWeight(LoopBlock &LoopBB,
uint32_t BBWeight,
385 SmallVectorImpl<BasicBlock *> &BlockWorkList,
386 SmallVectorImpl<LoopBlock> &LoopWorkList);
390 void propagateEstimatedBlockWeight(
const LoopBlock &LoopBB, DominatorTree *DT,
391 PostDominatorTree *PDT,
uint32_t BBWeight,
392 SmallVectorImpl<BasicBlock *> &WorkList,
393 SmallVectorImpl<LoopBlock> &LoopWorkList);
396 Optional<uint32_t> getInitialEstimatedBlockWeight(
const BasicBlock *
BB);
399 void computeEestimateBlockWeight(
const Function &
F, DominatorTree *DT,
400 PostDominatorTree *PDT);
407 bool calcZeroHeuristics(
const BasicBlock *
BB,
const TargetLibraryInfo *TLI);
457 #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)