BlockFrequencyInfoImpl.cpp | Explore in Territory

//===- BlockFrequencyImplInfo.cpp - Block Frequency Info Implementation ---===//
//
// 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/BlockFrequencyInfoImpl.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/Function.h"
#include "llvm/Support/BlockFrequency.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/ScaledNumber.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <list>
#include <numeric>
#include <optional>
#include <utility>
#include <vector>

usingnamespacellvm;
usingnamespacellvm::bfi_detail;

#define DEBUG_TYPE …

namespace llvm {
cl::opt<bool> CheckBFIUnknownBlockQueries(
    "check-bfi-unknown-block-queries",
    cl::init(false), cl::Hidden,
    cl::desc("Check if block frequency is queried for an unknown block "
             "for debugging missed BFI updates"));

cl::opt<bool> UseIterativeBFIInference(
    "use-iterative-bfi-inference", cl::Hidden,
    cl::desc("Apply an iterative post-processing to infer correct BFI counts"));

cl::opt<unsigned> IterativeBFIMaxIterationsPerBlock(
    "iterative-bfi-max-iterations-per-block", cl::init(1000), cl::Hidden,
    cl::desc("Iterative inference: maximum number of update iterations "
             "per block"));

cl::opt<double> IterativeBFIPrecision(
    "iterative-bfi-precision", cl::init(1e-12), cl::Hidden,
    cl::desc("Iterative inference: delta convergence precision; smaller values "
             "typically lead to better results at the cost of worsen runtime"));
} // namespace llvm

ScaledNumber<uint64_t> BlockMass::toScaled() const { … }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void BlockMass::dump() const { print(dbgs()); }
#endif

static char getHexDigit(int N) { … }

raw_ostream &BlockMass::print(raw_ostream &OS) const { … }

namespace {

BlockNode;
Distribution;
WeightList;
Scaled64;
LoopData;
Weight;
FrequencyData;

/// Dithering mass distributer.
///
/// This class splits up a single mass into portions by weight, dithering to
/// spread out error.  No mass is lost.  The dithering precision depends on the
/// precision of the product of \a BlockMass and \a BranchProbability.
///
/// The distribution algorithm follows.
///
///  1. Initialize by saving the sum of the weights in \a RemWeight and the
///     mass to distribute in \a RemMass.
///
///  2. For each portion:
///
///      1. Construct a branch probability, P, as the portion's weight divided
///         by the current value of \a RemWeight.
///      2. Calculate the portion's mass as \a RemMass times P.
///      3. Update \a RemWeight and \a RemMass at each portion by subtracting
///         the current portion's weight and mass.
struct DitheringDistributer { … };

} // end anonymous namespace

DitheringDistributer::DitheringDistributer(Distribution &Dist,
                                           const BlockMass &Mass) { … }

BlockMass DitheringDistributer::takeMass(uint32_t Weight) { … }

void Distribution::add(const BlockNode &Node, uint64_t Amount,
                       Weight::DistType Type) { … }

static void combineWeight(Weight &W, const Weight &OtherW) { … }

static void combineWeightsBySorting(WeightList &Weights) { … }

static void combineWeightsByHashing(WeightList &Weights) { … }

static void combineWeights(WeightList &Weights) { … }

static uint64_t shiftRightAndRound(uint64_t N, int Shift) { … }

void Distribution::normalize() { … }

void BlockFrequencyInfoImplBase::clear() { … }

/// Clear all memory not needed downstream.
///
/// Releases all memory not used downstream.  In particular, saves Freqs.
static void cleanup(BlockFrequencyInfoImplBase &BFI) { … }

bool BlockFrequencyInfoImplBase::addToDist(Distribution &Dist,
                                           const LoopData *OuterLoop,
                                           const BlockNode &Pred,
                                           const BlockNode &Succ,
                                           uint64_t Weight) { … }

bool BlockFrequencyInfoImplBase::addLoopSuccessorsToDist(
    const LoopData *OuterLoop, LoopData &Loop, Distribution &Dist) { … }

/// Compute the loop scale for a loop.
void BlockFrequencyInfoImplBase::computeLoopScale(LoopData &Loop) { … }

/// Package up a loop.
void BlockFrequencyInfoImplBase::packageLoop(LoopData &Loop) { … }

#ifndef NDEBUG
static void debugAssign(const BlockFrequencyInfoImplBase &BFI,
                        const DitheringDistributer &D, const BlockNode &T,
                        const BlockMass &M, const char *Desc) {
  dbgs() << "  => assign " << M << " (" << D.RemMass << ")";
  if (Desc)
    dbgs() << " [" << Desc << "]";
  if (T.isValid())
    dbgs() << " to " << BFI.getBlockName(T);
  dbgs() << "\n";
}
#endif

void BlockFrequencyInfoImplBase::distributeMass(const BlockNode &Source,
                                                LoopData *OuterLoop,
                                                Distribution &Dist) { … }

static void convertFloatingToInteger(BlockFrequencyInfoImplBase &BFI,
                                     const Scaled64 &Min, const Scaled64 &Max) { … }

/// Unwrap a loop package.
///
/// Visits all the members of a loop, adjusting their BlockData according to
/// the loop's pseudo-node.
static void unwrapLoop(BlockFrequencyInfoImplBase &BFI, LoopData &Loop) { … }

void BlockFrequencyInfoImplBase::unwrapLoops() { … }

void BlockFrequencyInfoImplBase::finalizeMetrics() { … }

BlockFrequency
BlockFrequencyInfoImplBase::getBlockFreq(const BlockNode &Node) const { … }

std::optional<uint64_t>
BlockFrequencyInfoImplBase::getBlockProfileCount(const Function &F,
                                                 const BlockNode &Node,
                                                 bool AllowSynthetic) const { … }

std::optional<uint64_t> BlockFrequencyInfoImplBase::getProfileCountFromFreq(
    const Function &F, BlockFrequency Freq, bool AllowSynthetic) const { … }

bool
BlockFrequencyInfoImplBase::isIrrLoopHeader(const BlockNode &Node) { … }

Scaled64
BlockFrequencyInfoImplBase::getFloatingBlockFreq(const BlockNode &Node) const { … }

void BlockFrequencyInfoImplBase::setBlockFreq(const BlockNode &Node,
                                              BlockFrequency Freq) { … }

std::string
BlockFrequencyInfoImplBase::getBlockName(const BlockNode &Node) const { … }

std::string
BlockFrequencyInfoImplBase::getLoopName(const LoopData &Loop) const { … }

void IrreducibleGraph::addNodesInLoop(const BFIBase::LoopData &OuterLoop) { … }

void IrreducibleGraph::addNodesInFunction() { … }

void IrreducibleGraph::indexNodes() { … }

void IrreducibleGraph::addEdge(IrrNode &Irr, const BlockNode &Succ,
                               const BFIBase::LoopData *OuterLoop) { … }

namespace llvm {

template <> struct GraphTraits<IrreducibleGraph> { … };

} // end namespace llvm

/// Find extra irreducible headers.
///
/// Find entry blocks and other blocks with backedges, which exist when \c G
/// contains irreducible sub-SCCs.
static void findIrreducibleHeaders(
    const BlockFrequencyInfoImplBase &BFI,
    const IrreducibleGraph &G,
    const std::vector<const IrreducibleGraph::IrrNode *> &SCC,
    LoopData::NodeList &Headers, LoopData::NodeList &Others) { … }

static void createIrreducibleLoop(
    BlockFrequencyInfoImplBase &BFI, const IrreducibleGraph &G,
    LoopData *OuterLoop, std::list<LoopData>::iterator Insert,
    const std::vector<const IrreducibleGraph::IrrNode *> &SCC) { … }

iterator_range<std::list<LoopData>::iterator>
BlockFrequencyInfoImplBase::analyzeIrreducible(
    const IrreducibleGraph &G, LoopData *OuterLoop,
    std::list<LoopData>::iterator Insert) { … }

void
BlockFrequencyInfoImplBase::updateLoopWithIrreducible(LoopData &OuterLoop) { … }

void BlockFrequencyInfoImplBase::adjustLoopHeaderMass(LoopData &Loop) { … }

void BlockFrequencyInfoImplBase::distributeIrrLoopHeaderMass(Distribution &Dist) { … }
llvm/llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp
