Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//==- BlockFrequencyInfoImpl.h - Block Frequency Implementation --*- C++ -*-==//

//

// 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

//

//===----------------------------------------------------------------------===//

//

// Shared implementation of BlockFrequency for IR and Machine Instructions.

// See the documentation below for BlockFrequencyInfoImpl for details.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_BLOCKFREQUENCYINFOIMPL_H

#define LLVM_ANALYSIS_BLOCKFREQUENCYINFOIMPL_H

#include "llvm/ADT/BitVector.h"

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/DenseSet.h"

#include "llvm/ADT/GraphTraits.h"

#include "llvm/ADT/PostOrderIterator.h"

#include "llvm/ADT/SmallPtrSet.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/ADT/SparseBitVector.h"

#include "llvm/ADT/Twine.h"

#include "llvm/ADT/iterator_range.h"

#include "llvm/IR/BasicBlock.h"

#include "llvm/IR/ValueHandle.h"

#include "llvm/Support/BlockFrequency.h"

#include "llvm/Support/BranchProbability.h"

#include "llvm/Support/CommandLine.h"

#include "llvm/Support/DOTGraphTraits.h"

#include "llvm/Support/Debug.h"

#include "llvm/Support/Format.h"

#include "llvm/Support/ScaledNumber.h"

#include "llvm/Support/raw_ostream.h"

#include <algorithm>

#include <cassert>

#include <cstddef>

#include <cstdint>

#include <deque>

#include <iterator>

#include <limits>

#include <list>

#include <optional>

#include <queue>

#include <string>

#include <utility>

#include <vector>

#define DEBUG_TYPE "block-freq"

namespace llvm {

extern llvm::cl::opt<bool> CheckBFIUnknownBlockQueries;

extern llvm::cl::opt<bool> UseIterativeBFIInference;

extern llvm::cl::opt<unsigned> IterativeBFIMaxIterationsPerBlock;

extern llvm::cl::opt<double> IterativeBFIPrecision;

class BranchProbabilityInfo;

class Function;

class Loop;

class LoopInfo;

class MachineBasicBlock;

class MachineBranchProbabilityInfo;

class MachineFunction;

class MachineLoop;

class MachineLoopInfo;

namespace bfi_detail {

struct IrreducibleGraph;

// This is part of a workaround for a GCC 4.7 crash on lambdas.

template <class BT> struct BlockEdgesAdder;

/// Mass of a block.

///

/// This class implements a sort of fixed-point fraction always between 0.0 and

/// 1.0.  getMass() == std::numeric_limits<uint64_t>::max() indicates a value of

/// 1.0.

///

/// Masses can be added and subtracted.  Simple saturation arithmetic is used,

/// so arithmetic operations never overflow or underflow.

///

/// Masses can be multiplied.  Multiplication treats full mass as 1.0 and uses

/// an inexpensive floating-point algorithm that's off-by-one (almost, but not

/// quite, maximum precision).

///

/// Masses can be scaled by \a BranchProbability at maximum precision.

class BlockMass {

  uint64_t Mass = 0;

public:

  BlockMass() = default;

  explicit BlockMass(uint64_t Mass) : Mass(Mass) {}

  static BlockMass getEmpty() { return BlockMass(); }

  static BlockMass getFull() {

    return BlockMass(std::numeric_limits<uint64_t>::max());

  }

  uint64_t getMass() const { return Mass; }

  bool isFull() const { return Mass == std::numeric_limits<uint64_t>::max(); }

  bool isEmpty() const { return !Mass; }

  bool operator!() const { return isEmpty(); }

  /// Add another mass.

  ///

  /// Adds another mass, saturating at \a isFull() rather than overflowing.

  BlockMass &operator+=(BlockMass X) {

    uint64_t Sum = Mass + X.Mass;

    Mass = Sum < Mass ? std::numeric_limits<uint64_t>::max() : Sum;

    return *this;

  }

  /// Subtract another mass.

  ///

  /// Subtracts another mass, saturating at \a isEmpty() rather than

  /// undeflowing.

  BlockMass &operator-=(BlockMass X) {

    uint64_t Diff = Mass - X.Mass;

    Mass = Diff > Mass ? 0 : Diff;

    return *this;

  }

  BlockMass &operator*=(BranchProbability P) {

    Mass = P.scale(Mass);

    return *this;

  }

  bool operator==(BlockMass X) const { return Mass == X.Mass; }

  bool operator!=(BlockMass X) const { return Mass != X.Mass; }

  bool operator<=(BlockMass X) const { return Mass <= X.Mass; }

  bool operator>=(BlockMass X) const { return Mass >= X.Mass; }

  bool operator<(BlockMass X) const { return Mass < X.Mass; }

  bool operator>(BlockMass X) const { return Mass > X.Mass; }

  /// Convert to scaled number.

  ///

  /// Convert to \a ScaledNumber.  \a isFull() gives 1.0, while \a isEmpty()

  /// gives slightly above 0.0.

  ScaledNumber<uint64_t> toScaled() const;

  void dump() const;

  raw_ostream &print(raw_ostream &OS) const;

};

inline BlockMass operator+(BlockMass L, BlockMass R) {

  return BlockMass(L) += R;

}

inline BlockMass operator-(BlockMass L, BlockMass R) {

  return BlockMass(L) -= R;

}

inline BlockMass operator*(BlockMass L, BranchProbability R) {

  return BlockMass(L) *= R;

}

inline BlockMass operator*(BranchProbability L, BlockMass R) {

  return BlockMass(R) *= L;

}

inline raw_ostream &operator<<(raw_ostream &OS, BlockMass X) {

  return X.print(OS);

}

} // end namespace bfi_detail

/// Base class for BlockFrequencyInfoImpl

///

/// BlockFrequencyInfoImplBase has supporting data structures and some

/// algorithms for BlockFrequencyInfoImplBase.  Only algorithms that depend on

/// the block type (or that call such algorithms) are skipped here.

///

/// Nevertheless, the majority of the overall algorithm documentation lives with

/// BlockFrequencyInfoImpl.  See there for details.

class BlockFrequencyInfoImplBase {

public:

  using Scaled64 = ScaledNumber<uint64_t>;

  using BlockMass = bfi_detail::BlockMass;

  /// Representative of a block.

  ///

  /// This is a simple wrapper around an index into the reverse-post-order

  /// traversal of the blocks.

  ///

  /// Unlike a block pointer, its order has meaning (location in the

  /// topological sort) and it's class is the same regardless of block type.

  struct BlockNode {

    using IndexType = uint32_t;

    IndexType Index;

    BlockNode() : Index(std::numeric_limits<uint32_t>::max()) {}

    BlockNode(IndexType Index) : Index(Index) {}

    bool operator==(const BlockNode &X) const { return Index == X.Index; }

    bool operator!=(const BlockNode &X) const { return Index != X.Index; }

    bool operator<=(const BlockNode &X) const { return Index <= X.Index; }

    bool operator>=(const BlockNode &X) const { return Index >= X.Index; }

    bool operator<(const BlockNode &X) const { return Index < X.Index; }

    bool operator>(const BlockNode &X) const { return Index > X.Index; }

    bool isValid() const { return Index <= getMaxIndex(); }

    static size_t getMaxIndex() {

       return std::numeric_limits<uint32_t>::max() - 1;

    }

  };

  /// Stats about a block itself.

  struct FrequencyData {

    Scaled64 Scaled;

    uint64_t Integer;

  };

  /// Data about a loop.

  ///

  /// Contains the data necessary to represent a loop as a pseudo-node once it's

  /// packaged.

  struct LoopData {

    using ExitMap = SmallVector<std::pair<BlockNode, BlockMass>, 4>;

    using NodeList = SmallVector<BlockNode, 4>;

    using HeaderMassList = SmallVector<BlockMass, 1>;

    LoopData *Parent;            ///< The parent loop.

    bool IsPackaged = false;     ///< Whether this has been packaged.

    uint32_t NumHeaders = 1;     ///< Number of headers.

    ExitMap Exits;               ///< Successor edges (and weights).

    NodeList Nodes;              ///< Header and the members of the loop.

    HeaderMassList BackedgeMass; ///< Mass returned to each loop header.

    BlockMass Mass;

    Scaled64 Scale;

    LoopData(LoopData *Parent, const BlockNode &Header)

      : Parent(Parent), Nodes(1, Header), BackedgeMass(1) {}

    template <class It1, class It2>

    LoopData(LoopData *Parent, It1 FirstHeader, It1 LastHeader, It2 FirstOther,

             It2 LastOther)

        : Parent(Parent), Nodes(FirstHeader, LastHeader) {

      NumHeaders = Nodes.size();

      Nodes.insert(Nodes.end(), FirstOther, LastOther);

      BackedgeMass.resize(NumHeaders);

    }

    bool isHeader(const BlockNode &Node) const {

      if (isIrreducible())

        return std::binary_search(Nodes.begin(), Nodes.begin() + NumHeaders,

                                  Node);

      return Node == Nodes[0];

    }

    BlockNode getHeader() const { return Nodes[0]; }

    bool isIrreducible() const { return NumHeaders > 1; }

    HeaderMassList::difference_type getHeaderIndex(const BlockNode &B) {

      assert(isHeader(B) && "this is only valid on loop header blocks");

      if (isIrreducible())

        return std::lower_bound(Nodes.begin(), Nodes.begin() + NumHeaders, B) -

               Nodes.begin();

      return 0;

    }

    NodeList::const_iterator members_begin() const {

      return Nodes.begin() + NumHeaders;

    }

    NodeList::const_iterator members_end() const { return Nodes.end(); }

    iterator_range<NodeList::const_iterator> members() const {

      return make_range(members_begin(), members_end());

    }

  };

  /// Index of loop information.

  struct WorkingData {

    BlockNode Node;           ///< This node.

    LoopData *Loop = nullptr; ///< The loop this block is inside.

    BlockMass Mass;           ///< Mass distribution from the entry block.

    WorkingData(const BlockNode &Node) : Node(Node) {}

    bool isLoopHeader() const { return Loop && Loop->isHeader(Node); }

    bool isDoubleLoopHeader() const {

      return isLoopHeader() && Loop->Parent && Loop->Parent->isIrreducible() &&

             Loop->Parent->isHeader(Node);

    }

    LoopData *getContainingLoop() const {

      if (!isLoopHeader())

        return Loop;

      if (!isDoubleLoopHeader())

        return Loop->Parent;

      return Loop->Parent->Parent;

    }

    /// Resolve a node to its representative.

    ///

    /// Get the node currently representing Node, which could be a containing

    /// loop.

    ///

    /// This function should only be called when distributing mass.  As long as

    /// there are no irreducible edges to Node, then it will have complexity

    /// O(1) in this context.

    ///

    /// In general, the complexity is O(L), where L is the number of loop

    /// headers Node has been packaged into.  Since this method is called in

    /// the context of distributing mass, L will be the number of loop headers

    /// an early exit edge jumps out of.

    BlockNode getResolvedNode() const {

      auto L = getPackagedLoop();

      return L ? L->getHeader() : Node;

    }

    LoopData *getPackagedLoop() const {

      if (!Loop || !Loop->IsPackaged)

        return nullptr;

      auto L = Loop;

      while (L->Parent && L->Parent->IsPackaged)

        L = L->Parent;

      return L;

    }

    /// Get the appropriate mass for a node.

    ///

    /// Get appropriate mass for Node.  If Node is a loop-header (whose loop

    /// has been packaged), returns the mass of its pseudo-node.  If it's a

    /// node inside a packaged loop, it returns the loop's mass.

    BlockMass &getMass() {

      if (!isAPackage())

        return Mass;

      if (!isADoublePackage())

        return Loop->Mass;

      return Loop->Parent->Mass;

    }

    /// Has ContainingLoop been packaged up?

    bool isPackaged() const { return getResolvedNode() != Node; }

    /// Has Loop been packaged up?

    bool isAPackage() const { return isLoopHeader() && Loop->IsPackaged; }

    /// Has Loop been packaged up twice?

    bool isADoublePackage() const {

      return isDoubleLoopHeader() && Loop->Parent->IsPackaged;

    }

  };

  /// Unscaled probability weight.

  ///

  /// Probability weight for an edge in the graph (including the

  /// successor/target node).

  ///

  /// All edges in the original function are 32-bit.  However, exit edges from

  /// loop packages are taken from 64-bit exit masses, so we need 64-bits of

  /// space in general.

  ///

  /// In addition to the raw weight amount, Weight stores the type of the edge

  /// in the current context (i.e., the context of the loop being processed).

  /// Is this a local edge within the loop, an exit from the loop, or a

  /// backedge to the loop header?

  struct Weight {

    enum DistType { Local, Exit, Backedge };

    DistType Type = Local;

    BlockNode TargetNode;

    uint64_t Amount = 0;

    Weight() = default;

    Weight(DistType Type, BlockNode TargetNode, uint64_t Amount)

        : Type(Type), TargetNode(TargetNode), Amount(Amount) {}

  };

  /// Distribution of unscaled probability weight.

  ///

  /// Distribution of unscaled probability weight to a set of successors.

  ///

  /// This class collates the successor edge weights for later processing.

  ///

  /// \a DidOverflow indicates whether \a Total did overflow while adding to

  /// the distribution.  It should never overflow twice.

  struct Distribution {

    using WeightList = SmallVector<Weight, 4>;

    WeightList Weights;       ///< Individual successor weights.

    uint64_t Total = 0;       ///< Sum of all weights.

    bool DidOverflow = false; ///< Whether \a Total did overflow.

    Distribution() = default;

    void addLocal(const BlockNode &Node, uint64_t Amount) {

      add(Node, Amount, Weight::Local);

    }

    void addExit(const BlockNode &Node, uint64_t Amount) {

      add(Node, Amount, Weight::Exit);

    }

    void addBackedge(const BlockNode &Node, uint64_t Amount) {

      add(Node, Amount, Weight::Backedge);

    }

    /// Normalize the distribution.

    ///

    /// Combines multiple edges to the same \a Weight::TargetNode and scales

    /// down so that \a Total fits into 32-bits.

    ///

    /// This is linear in the size of \a Weights.  For the vast majority of

    /// cases, adjacent edge weights are combined by sorting WeightList and

    /// combining adjacent weights.  However, for very large edge lists an

    /// auxiliary hash table is used.

    void normalize();

  private:

    void add(const BlockNode &Node, uint64_t Amount, Weight::DistType Type);

  };

  /// Data about each block.  This is used downstream.

  std::vector<FrequencyData> Freqs;

  /// Whether each block is an irreducible loop header.

  /// This is used downstream.

  SparseBitVector<> IsIrrLoopHeader;

  /// Loop data: see initializeLoops().

  std::vector<WorkingData> Working;

  /// Indexed information about loops.

  std::list<LoopData> Loops;

  /// Virtual destructor.

  ///

  /// Need a virtual destructor to mask the compiler warning about

  /// getBlockName().

  virtual ~BlockFrequencyInfoImplBase() = default;

  /// Add all edges out of a packaged loop to the distribution.

  ///

  /// Adds all edges from LocalLoopHead to Dist.  Calls addToDist() to add each

  /// successor edge.

  ///

  /// \return \c true unless there's an irreducible backedge.

  bool addLoopSuccessorsToDist(const LoopData *OuterLoop, LoopData &Loop,

                               Distribution &Dist);

  /// Add an edge to the distribution.

  ///

  /// Adds an edge to Succ to Dist.  If \c LoopHead.isValid(), then whether the

  /// edge is local/exit/backedge is in the context of LoopHead.  Otherwise,

  /// every edge should be a local edge (since all the loops are packaged up).

  ///

  /// \return \c true unless aborted due to an irreducible backedge.

  bool addToDist(Distribution &Dist, const LoopData *OuterLoop,

                 const BlockNode &Pred, const BlockNode &Succ, uint64_t Weight);

  /// Analyze irreducible SCCs.

  ///

  /// Separate irreducible SCCs from \c G, which is an explicit graph of \c

  /// OuterLoop (or the top-level function, if \c OuterLoop is \c nullptr).

  /// Insert them into \a Loops before \c Insert.

  ///

  /// \return the \c LoopData nodes representing the irreducible SCCs.

  iterator_range<std::list<LoopData>::iterator>

  analyzeIrreducible(const bfi_detail::IrreducibleGraph &G, LoopData *OuterLoop,

                     std::list<LoopData>::iterator Insert);

  /// Update a loop after packaging irreducible SCCs inside of it.

  ///

  /// Update \c OuterLoop.  Before finding irreducible control flow, it was

  /// partway through \a computeMassInLoop(), so \a LoopData::Exits and \a

  /// LoopData::BackedgeMass need to be reset.  Also, nodes that were packaged

  /// up need to be removed from \a OuterLoop::Nodes.

  void updateLoopWithIrreducible(LoopData &OuterLoop);

  /// Distribute mass according to a distribution.

  ///

  /// Distributes the mass in Source according to Dist.  If LoopHead.isValid(),

  /// backedges and exits are stored in its entry in Loops.

  ///

  /// Mass is distributed in parallel from two copies of the source mass.

  void distributeMass(const BlockNode &Source, LoopData *OuterLoop,

                      Distribution &Dist);

  /// Compute the loop scale for a loop.

  void computeLoopScale(LoopData &Loop);

  /// Adjust the mass of all headers in an irreducible loop.

  ///

  /// Initially, irreducible loops are assumed to distribute their mass

  /// equally among its headers. This can lead to wrong frequency estimates

  /// since some headers may be executed more frequently than others.

  ///

  /// This adjusts header mass distribution so it matches the weights of

  /// the backedges going into each of the loop headers.

  void adjustLoopHeaderMass(LoopData &Loop);

  void distributeIrrLoopHeaderMass(Distribution &Dist);

  /// Package up a loop.

  void packageLoop(LoopData &Loop);

  /// Unwrap loops.

  void unwrapLoops();

  /// Finalize frequency metrics.

  ///

  /// Calculates final frequencies and cleans up no-longer-needed data

  /// structures.

  void finalizeMetrics();

  /// Clear all memory.

  void clear();

  virtual std::string getBlockName(const BlockNode &Node) const;

  std::string getLoopName(const LoopData &Loop) const;

  virtual raw_ostream &print(raw_ostream &OS) const { return OS; }

  void dump() const { print(dbgs()); }

  Scaled64 getFloatingBlockFreq(const BlockNode &Node) const;

  BlockFrequency getBlockFreq(const BlockNode &Node) const;

  std::optional<uint64_t>

  getBlockProfileCount(const Function &F, const BlockNode &Node,

                       bool AllowSynthetic = false) const;

  std::optional<uint64_t>

  getProfileCountFromFreq(const Function &F, uint64_t Freq,

                          bool AllowSynthetic = false) const;

  bool isIrrLoopHeader(const BlockNode &Node);

  void setBlockFreq(const BlockNode &Node, uint64_t Freq);

  raw_ostream &printBlockFreq(raw_ostream &OS, const BlockNode &Node) const;

  raw_ostream &printBlockFreq(raw_ostream &OS,

                              const BlockFrequency &Freq) const;

  uint64_t getEntryFreq() const {

    assert(!Freqs.empty());

    return Freqs[0].Integer;

  }

};

namespace bfi_detail {

template <class BlockT> struct TypeMap {};

template <> struct TypeMap<BasicBlock> {

  using BlockT = BasicBlock;

  using BlockKeyT = AssertingVH<const BasicBlock>;

  using FunctionT = Function;

  using BranchProbabilityInfoT = BranchProbabilityInfo;

  using LoopT = Loop;

  using LoopInfoT = LoopInfo;

};

template <> struct TypeMap<MachineBasicBlock> {

  using BlockT = MachineBasicBlock;

  using BlockKeyT = const MachineBasicBlock *;

  using FunctionT = MachineFunction;

  using BranchProbabilityInfoT = MachineBranchProbabilityInfo;

  using LoopT = MachineLoop;

  using LoopInfoT = MachineLoopInfo;

};

template <class BlockT, class BFIImplT>

class BFICallbackVH;

/// Get the name of a MachineBasicBlock.

///

/// Get the name of a MachineBasicBlock.  It's templated so that including from

/// CodeGen is unnecessary (that would be a layering issue).

///

/// This is used mainly for debug output.  The name is similar to

/// MachineBasicBlock::getFullName(), but skips the name of the function.

template <class BlockT> std::string getBlockName(const BlockT *BB) {

  assert(BB && "Unexpected nullptr");

  auto MachineName = "BB" + Twine(BB->getNumber());

  if (BB->getBasicBlock())

    return (MachineName + "[" + BB->getName() + "]").str();

  return MachineName.str();

}

/// Get the name of a BasicBlock.

template <> inline std::string getBlockName(const BasicBlock *BB) {

  assert(BB && "Unexpected nullptr");

  return BB->getName().str();

}

/// Graph of irreducible control flow.

///

/// This graph is used for determining the SCCs in a loop (or top-level

/// function) that has irreducible control flow.

///

/// During the block frequency algorithm, the local graphs are defined in a

/// light-weight way, deferring to the \a BasicBlock or \a MachineBasicBlock

/// graphs for most edges, but getting others from \a LoopData::ExitMap.  The

/// latter only has successor information.

///

/// \a IrreducibleGraph makes this graph explicit.  It's in a form that can use

/// \a GraphTraits (so that \a analyzeIrreducible() can use \a scc_iterator),

/// and it explicitly lists predecessors and successors.  The initialization

/// that relies on \c MachineBasicBlock is defined in the header.

struct IrreducibleGraph {

  using BFIBase = BlockFrequencyInfoImplBase;

  BFIBase &BFI;

  using BlockNode = BFIBase::BlockNode;

  struct IrrNode {

    BlockNode Node;

    unsigned NumIn = 0;

    std::deque<const IrrNode *> Edges;

    IrrNode(const BlockNode &Node) : Node(Node) {}

    using iterator = std::deque<const IrrNode *>::const_iterator;

    iterator pred_begin() const { return Edges.begin(); }

    iterator succ_begin() const { return Edges.begin() + NumIn; }

    iterator pred_end() const { return succ_begin(); }

    iterator succ_end() const { return Edges.end(); }

  };

  BlockNode Start;

  const IrrNode *StartIrr = nullptr;

  std::vector<IrrNode> Nodes;

  SmallDenseMap<uint32_t, IrrNode *, 4> Lookup;

  /// Construct an explicit graph containing irreducible control flow.

  ///

  /// Construct an explicit graph of the control flow in \c OuterLoop (or the

  /// top-level function, if \c OuterLoop is \c nullptr).  Uses \c

  /// addBlockEdges to add block successors that have not been packaged into

  /// loops.

  ///

  /// \a BlockFrequencyInfoImpl::computeIrreducibleMass() is the only expected

  /// user of this.

  template <class BlockEdgesAdder>

  IrreducibleGraph(BFIBase &BFI, const BFIBase::LoopData *OuterLoop,

                   BlockEdgesAdder addBlockEdges) : BFI(BFI) {

    initialize(OuterLoop, addBlockEdges);

  }

  template <class BlockEdgesAdder>

  void initialize(const BFIBase::LoopData *OuterLoop,

                  BlockEdgesAdder addBlockEdges);

  void addNodesInLoop(const BFIBase::LoopData &OuterLoop);

  void addNodesInFunction();

  void addNode(const BlockNode &Node) {

    Nodes.emplace_back(Node);

    BFI.Working[Node.Index].getMass() = BlockMass::getEmpty();

  }

  void indexNodes();

  template <class BlockEdgesAdder>

  void addEdges(const BlockNode &Node, const BFIBase::LoopData *OuterLoop,

                BlockEdgesAdder addBlockEdges);

  void addEdge(IrrNode &Irr, const BlockNode &Succ,

               const BFIBase::LoopData *OuterLoop);

};

template <class BlockEdgesAdder>

void IrreducibleGraph::initialize(const BFIBase::LoopData *OuterLoop,

                                  BlockEdgesAdder addBlockEdges) {

  if (OuterLoop) {

    addNodesInLoop(*OuterLoop);

    for (auto N : OuterLoop->Nodes)

      addEdges(N, OuterLoop, addBlockEdges);

  } else {

    addNodesInFunction();

    for (uint32_t Index = 0; Index < BFI.Working.size(); ++Index)

      addEdges(Index, OuterLoop, addBlockEdges);

  }

  StartIrr = Lookup[Start.Index];

}

template <class BlockEdgesAdder>

void IrreducibleGraph::addEdges(const BlockNode &Node,

                                const BFIBase::LoopData *OuterLoop,

                                BlockEdgesAdder addBlockEdges) {

  auto L = Lookup.find(Node.Index);

  if (L == Lookup.end())

    return;

  IrrNode &Irr = *L->second;

  const auto &Working = BFI.Working[Node.Index];

  if (Working.isAPackage())

    for (const auto &I : Working.Loop->Exits)

      addEdge(Irr, I.first, OuterLoop);

  else

    addBlockEdges(*this, Irr, OuterLoop);

}

} // end namespace bfi_detail

/// Shared implementation for block frequency analysis.

///

/// This is a shared implementation of BlockFrequencyInfo and

/// MachineBlockFrequencyInfo, and calculates the relative frequencies of

/// blocks.

///

/// LoopInfo defines a loop as a "non-trivial" SCC dominated by a single block,

/// which is called the header.  A given loop, L, can have sub-loops, which are

/// loops within the subgraph of L that exclude its header.  (A "trivial" SCC

/// consists of a single block that does not have a self-edge.)

///

/// In addition to loops, this algorithm has limited support for irreducible

/// SCCs, which are SCCs with multiple entry blocks.  Irreducible SCCs are

/// discovered on the fly, and modelled as loops with multiple headers.

///

/// The headers of irreducible sub-SCCs consist of its entry blocks and all

/// nodes that are targets of a backedge within it (excluding backedges within

/// true sub-loops).  Block frequency calculations act as if a block is

/// inserted that intercepts all the edges to the headers.  All backedges and

/// entries point to this block.  Its successors are the headers, which split

/// the frequency evenly.

///

/// This algorithm leverages BlockMass and ScaledNumber to maintain precision,

/// separates mass distribution from loop scaling, and dithers to eliminate

/// probability mass loss.

///

/// The implementation is split between BlockFrequencyInfoImpl, which knows the

/// type of graph being modelled (BasicBlock vs. MachineBasicBlock), and

/// BlockFrequencyInfoImplBase, which doesn't.  The base class uses \a

/// BlockNode, a wrapper around a uint32_t.  BlockNode is numbered from 0 in

/// reverse-post order.  This gives two advantages:  it's easy to compare the

/// relative ordering of two nodes, and maps keyed on BlockT can be represented

/// by vectors.

///

/// This algorithm is O(V+E), unless there is irreducible control flow, in

/// which case it's O(V*E) in the worst case.

///

/// These are the main stages:

///

///  0. Reverse post-order traversal (\a initializeRPOT()).

///

///     Run a single post-order traversal and save it (in reverse) in RPOT.

///     All other stages make use of this ordering.  Save a lookup from BlockT

///     to BlockNode (the index into RPOT) in Nodes.

///

///  1. Loop initialization (\a initializeLoops()).

///

///     Translate LoopInfo/MachineLoopInfo into a form suitable for the rest of

///     the algorithm.  In particular, store the immediate members of each loop

///     in reverse post-order.

///

///  2. Calculate mass and scale in loops (\a computeMassInLoops()).

///

///     For each loop (bottom-up), distribute mass through the DAG resulting

///     from ignoring backedges and treating sub-loops as a single pseudo-node.

///     Track the backedge mass distributed to the loop header, and use it to

///     calculate the loop scale (number of loop iterations).  Immediate

///     members that represent sub-loops will already have been visited and

///     packaged into a pseudo-node.

///

///     Distributing mass in a loop is a reverse-post-order traversal through

///     the loop.  Start by assigning full mass to the Loop header.  For each

///     node in the loop:

///

///         - Fetch and categorize the weight distribution for its successors.

///           If this is a packaged-subloop, the weight distribution is stored

///           in \a LoopData::Exits.  Otherwise, fetch it from

///           BranchProbabilityInfo.

///

///         - Each successor is categorized as \a Weight::Local, a local edge

///           within the current loop, \a Weight::Backedge, a backedge to the

///           loop header, or \a Weight::Exit, any successor outside the loop.

///           The weight, the successor, and its category are stored in \a

///           Distribution.  There can be multiple edges to each successor.

///

///         - If there's a backedge to a non-header, there's an irreducible SCC.

///           The usual flow is temporarily aborted.  \a

///           computeIrreducibleMass() finds the irreducible SCCs within the

///           loop, packages them up, and restarts the flow.

///

///         - Normalize the distribution:  scale weights down so that their sum

///           is 32-bits, and coalesce multiple edges to the same node.

///

///         - Distribute the mass accordingly, dithering to minimize mass loss,

///           as described in \a distributeMass().

///

///     In the case of irreducible loops, instead of a single loop header,

///     there will be several. The computation of backedge masses is similar

///     but instead of having a single backedge mass, there will be one

///     backedge per loop header. In these cases, each backedge will carry

///     a mass proportional to the edge weights along the corresponding

///     path.

///

///     At the end of propagation, the full mass assigned to the loop will be

///     distributed among the loop headers proportionally according to the

///     mass flowing through their backedges.

///

///     Finally, calculate the loop scale from the accumulated backedge mass.

///

///  3. Distribute mass in the function (\a computeMassInFunction()).

///

///     Finally, distribute mass through the DAG resulting from packaging all

///     loops in the function.  This uses the same algorithm as distributing

///     mass in a loop, except that there are no exit or backedge edges.

///

///  4. Unpackage loops (\a unwrapLoops()).

///

///     Initialize each block's frequency to a floating point representation of

///     its mass.

///

///     Visit loops top-down, scaling the frequencies of its immediate members

///     by the loop's pseudo-node's frequency.

///

///  5. Convert frequencies to a 64-bit range (\a finalizeMetrics()).

///

///     Using the min and max frequencies as a guide, translate floating point

///     frequencies to an appropriate range in uint64_t.

///

/// It has some known flaws.

///

///   - The model of irreducible control flow is a rough approximation.

///

///     Modelling irreducible control flow exactly involves setting up and