BranchProbabilityInfo.cpp | Explore in Territory

//===- BranchProbabilityInfo.cpp - Branch Probability Analysis ------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Loops should be simplified before this analysis.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/ProfDataUtils.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <cstdint>
#include <iterator>
#include <map>
#include <utility>

usingnamespacellvm;

#define DEBUG_TYPE …

static cl::opt<bool> PrintBranchProb(
    "print-bpi", cl::init(false), cl::Hidden,
    cl::desc("Print the branch probability info."));

cl::opt<std::string> PrintBranchProbFuncName(
    "print-bpi-func-name", cl::Hidden,
    cl::desc("The option to specify the name of the function "
             "whose branch probability info is printed."));

INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob",
                      "Branch Probability Analysis", false, true)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass, "branch-prob",
                    "Branch Probability Analysis", false, true)

BranchProbabilityInfoWrapperPass::BranchProbabilityInfoWrapperPass()
    : … { … }

char BranchProbabilityInfoWrapperPass::ID = …;

// Weights are for internal use only. They are used by heuristics to help to
// estimate edges' probability. Example:
//
// Using "Loop Branch Heuristics" we predict weights of edges for the
// block BB2.
//         ...
//          |
//          V
//         BB1<-+
//          |   |
//          |   | (Weight = 124)
//          V   |
//         BB2--+
//          |
//          | (Weight = 4)
//          V
//         BB3
//
// Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875
// Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125
static const uint32_t LBH_TAKEN_WEIGHT = …;
static const uint32_t LBH_NONTAKEN_WEIGHT = …;

/// Unreachable-terminating branch taken probability.
///
/// This is the probability for a branch being taken to a block that terminates
/// (eventually) in unreachable. These are predicted as unlikely as possible.
/// All reachable probability will proportionally share the remaining part.
static const BranchProbability UR_TAKEN_PROB = …;

/// Heuristics and lookup tables for non-loop branches:
/// Pointer Heuristics (PH)
static const uint32_t PH_TAKEN_WEIGHT = …;
static const uint32_t PH_NONTAKEN_WEIGHT = …;
static const BranchProbability
    PtrTakenProb(PH_TAKEN_WEIGHT, PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
static const BranchProbability
    PtrUntakenProb(PH_NONTAKEN_WEIGHT, PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);

ProbabilityList;
ProbabilityTable;

/// Pointer comparisons:
static const ProbabilityTable PointerTable{ … };

/// Zero Heuristics (ZH)
static const uint32_t ZH_TAKEN_WEIGHT = …;
static const uint32_t ZH_NONTAKEN_WEIGHT = …;
static const BranchProbability
    ZeroTakenProb(ZH_TAKEN_WEIGHT, ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
static const BranchProbability
    ZeroUntakenProb(ZH_NONTAKEN_WEIGHT, ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);

/// Integer compares with 0:
static const ProbabilityTable ICmpWithZeroTable{ … };

/// Integer compares with -1:
static const ProbabilityTable ICmpWithMinusOneTable{ … };

/// Integer compares with 1:
static const ProbabilityTable ICmpWithOneTable{ … };

/// strcmp and similar functions return zero, negative, or positive, if the
/// first string is equal, less, or greater than the second. We consider it
/// likely that the strings are not equal, so a comparison with zero is
/// probably false, but also a comparison with any other number is also
/// probably false given that what exactly is returned for nonzero values is
/// not specified. Any kind of comparison other than equality we know
/// nothing about.
static const ProbabilityTable ICmpWithLibCallTable{ … };

// Floating-Point Heuristics (FPH)
static const uint32_t FPH_TAKEN_WEIGHT = …;
static const uint32_t FPH_NONTAKEN_WEIGHT = …;

/// This is the probability for an ordered floating point comparison.
static const uint32_t FPH_ORD_WEIGHT = …;
/// This is the probability for an unordered floating point comparison, it means
/// one or two of the operands are NaN. Usually it is used to test for an
/// exceptional case, so the result is unlikely.
static const uint32_t FPH_UNO_WEIGHT = …;

static const BranchProbability FPOrdTakenProb(FPH_ORD_WEIGHT,
                                              FPH_ORD_WEIGHT + FPH_UNO_WEIGHT);
static const BranchProbability
    FPOrdUntakenProb(FPH_UNO_WEIGHT, FPH_ORD_WEIGHT + FPH_UNO_WEIGHT);
static const BranchProbability
    FPTakenProb(FPH_TAKEN_WEIGHT, FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT);
static const BranchProbability
    FPUntakenProb(FPH_NONTAKEN_WEIGHT, FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT);

/// Floating-Point compares:
static const ProbabilityTable FCmpTable{ … };

/// Set of dedicated "absolute" execution weights for a block. These weights are
/// meaningful relative to each other and their derivatives only.
enum class BlockExecWeight : std::uint32_t { … };

BranchProbabilityInfo::SccInfo::SccInfo(const Function &F) { … }

int BranchProbabilityInfo::SccInfo::getSCCNum(const BasicBlock *BB) const { … }

void BranchProbabilityInfo::SccInfo::getSccEnterBlocks(
    int SccNum, SmallVectorImpl<BasicBlock *> &Enters) const { … }

void BranchProbabilityInfo::SccInfo::getSccExitBlocks(
    int SccNum, SmallVectorImpl<BasicBlock *> &Exits) const { … }

uint32_t BranchProbabilityInfo::SccInfo::getSccBlockType(const BasicBlock *BB,
                                                         int SccNum) const { … }

void BranchProbabilityInfo::SccInfo::calculateSccBlockType(const BasicBlock *BB,
                                                           int SccNum) { … }

BranchProbabilityInfo::LoopBlock::LoopBlock(const BasicBlock *BB,
                                            const LoopInfo &LI,
                                            const SccInfo &SccI)
    : … { … }

bool BranchProbabilityInfo::isLoopEnteringEdge(const LoopEdge &Edge) const { … }

bool BranchProbabilityInfo::isLoopExitingEdge(const LoopEdge &Edge) const { … }

bool BranchProbabilityInfo::isLoopEnteringExitingEdge(
    const LoopEdge &Edge) const { … }

bool BranchProbabilityInfo::isLoopBackEdge(const LoopEdge &Edge) const { … }

void BranchProbabilityInfo::getLoopEnterBlocks(
    const LoopBlock &LB, SmallVectorImpl<BasicBlock *> &Enters) const { … }

void BranchProbabilityInfo::getLoopExitBlocks(
    const LoopBlock &LB, SmallVectorImpl<BasicBlock *> &Exits) const { … }

// Propagate existing explicit probabilities from either profile data or
// 'expect' intrinsic processing. Examine metadata against unreachable
// heuristic. The probability of the edge coming to unreachable block is
// set to min of metadata and unreachable heuristic.
bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) { … }

// Calculate Edge Weights using "Pointer Heuristics". Predict a comparison
// between two pointer or pointer and NULL will fail.
bool BranchProbabilityInfo::calcPointerHeuristics(const BasicBlock *BB) { … }

// Compute the unlikely successors to the block BB in the loop L, specifically
// those that are unlikely because this is a loop, and add them to the
// UnlikelyBlocks set.
static void
computeUnlikelySuccessors(const BasicBlock *BB, Loop *L,
                          SmallPtrSetImpl<const BasicBlock*> &UnlikelyBlocks) { … }

std::optional<uint32_t>
BranchProbabilityInfo::getEstimatedBlockWeight(const BasicBlock *BB) const { … }

std::optional<uint32_t>
BranchProbabilityInfo::getEstimatedLoopWeight(const LoopData &L) const { … }

std::optional<uint32_t>
BranchProbabilityInfo::getEstimatedEdgeWeight(const LoopEdge &Edge) const { … }

template <class IterT>
std::optional<uint32_t> BranchProbabilityInfo::getMaxEstimatedEdgeWeight(
    const LoopBlock &SrcLoopBB, iterator_range<IterT> Successors) const { … }

// Updates \p LoopBB's weight and returns true. If \p LoopBB has already
// an associated weight it is unchanged and false is returned.
//
// Please note by the algorithm the weight is not expected to change once set
// thus 'false' status is used to track visited blocks.
bool BranchProbabilityInfo::updateEstimatedBlockWeight(
    LoopBlock &LoopBB, uint32_t BBWeight,
    SmallVectorImpl<BasicBlock *> &BlockWorkList,
    SmallVectorImpl<LoopBlock> &LoopWorkList) { … }

// Starting from \p BB traverse through dominator blocks and assign \p BBWeight
// to all such blocks that are post dominated by \BB. In other words to all
// blocks that the one is executed if and only if another one is executed.
// Importantly, we skip loops here for two reasons. First weights of blocks in
// a loop should be scaled by trip count (yet possibly unknown). Second there is
// no any value in doing that because that doesn't give any additional
// information regarding distribution of probabilities inside the loop.
// Exception is loop 'enter' and 'exit' edges that are handled in a special way
// at calcEstimatedHeuristics.
//
// In addition, \p WorkList is populated with basic blocks if at leas one
// successor has updated estimated weight.
void BranchProbabilityInfo::propagateEstimatedBlockWeight(
    const LoopBlock &LoopBB, DominatorTree *DT, PostDominatorTree *PDT,
    uint32_t BBWeight, SmallVectorImpl<BasicBlock *> &BlockWorkList,
    SmallVectorImpl<LoopBlock> &LoopWorkList) { … }

std::optional<uint32_t>
BranchProbabilityInfo::getInitialEstimatedBlockWeight(const BasicBlock *BB) { … }

// Does RPO traversal over all blocks in \p F and assigns weights to
// 'unreachable', 'noreturn', 'cold', 'unwind' blocks. In addition it does its
// best to propagate the weight to up/down the IR.
void BranchProbabilityInfo::computeEestimateBlockWeight(
    const Function &F, DominatorTree *DT, PostDominatorTree *PDT) { … }

// Calculate edge probabilities based on block's estimated weight.
// Note that gathered weights were not scaled for loops. Thus edges entering
// and exiting loops requires special processing.
bool BranchProbabilityInfo::calcEstimatedHeuristics(const BasicBlock *BB) { … }

bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB,
                                               const TargetLibraryInfo *TLI) { … }

bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) { … }

void BranchProbabilityInfo::releaseMemory() { … }

bool BranchProbabilityInfo::invalidate(Function &, const PreservedAnalyses &PA,
                                       FunctionAnalysisManager::Invalidator &) { … }

void BranchProbabilityInfo::print(raw_ostream &OS) const { … }

bool BranchProbabilityInfo::
isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const { … }

/// Get the raw edge probability for the edge. If can't find it, return a
/// default probability 1/N where N is the number of successors. Here an edge is
/// specified using PredBlock and an
/// index to the successors.
BranchProbability
BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
                                          unsigned IndexInSuccessors) const { … }

BranchProbability
BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
                                          const_succ_iterator Dst) const { … }

/// Get the raw edge probability calculated for the block pair. This returns the
/// sum of all raw edge probabilities from Src to Dst.
BranchProbability
BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
                                          const BasicBlock *Dst) const { … }

/// Set the edge probability for all edges at once.
void BranchProbabilityInfo::setEdgeProbability(
    const BasicBlock *Src, const SmallVectorImpl<BranchProbability> &Probs) { … }

void BranchProbabilityInfo::copyEdgeProbabilities(BasicBlock *Src,
                                                  BasicBlock *Dst) { … }

void BranchProbabilityInfo::swapSuccEdgesProbabilities(const BasicBlock *Src) { … }

raw_ostream &
BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
                                            const BasicBlock *Src,
                                            const BasicBlock *Dst) const { … }

void BranchProbabilityInfo::eraseBlock(const BasicBlock *BB) { … }

void BranchProbabilityInfo::calculate(const Function &F, const LoopInfo &LoopI,
                                      const TargetLibraryInfo *TLI,
                                      DominatorTree *DT,
                                      PostDominatorTree *PDT) { … }

void BranchProbabilityInfoWrapperPass::getAnalysisUsage(
    AnalysisUsage &AU) const { … }

bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) { … }

void BranchProbabilityInfoWrapperPass::releaseMemory() { … }

void BranchProbabilityInfoWrapperPass::print(raw_ostream &OS,
                                             const Module *) const { … }

AnalysisKey BranchProbabilityAnalysis::Key;
BranchProbabilityInfo
BranchProbabilityAnalysis::run(Function &F, FunctionAnalysisManager &AM) { … }

PreservedAnalyses
BranchProbabilityPrinterPass::run(Function &F, FunctionAnalysisManager &AM) { … }
llvm/llvm/lib/Analysis/BranchProbabilityInfo.cpp
