Simplified BranchProbabilityInfo model

README.md

Simplified BranchProbabilityInfo demo

bpi.cpp reimplements the estimated (loop-aware) heuristic of LLVM's BranchProbabilityInfo — the only heuristic that is a pure function of the CFG + loop structure. See the header comment in bpi.cpp for what is intentionally omitted (instruction-level heuristics, computeUnlikelySuccessors).

Loops come from a nested cycle forest built with Tao Wei's single-pass DFS (the algorithm llvm::CycleInfo uses), visiting successors LIFO to match LLVM's iterative DFS order. This handles reducible and irreducible loops and gives each block its innermost cycle plus containment — so nested loops come out right.

Build & run

g++ -O2 -std=c++17 -o bpi bpi.cpp
./bpi < ex_loop.txt

Input: n m, then m edges u v (node 0 = entry), then optional b K lines giving block b a kind K ∈ {U unreachable, R noreturn, C cold}.

bpi.cpp

// A simplified BranchProbabilityInfo: static branch-probability estimation.
//
// Reproduces the *estimated* heuristic of llvm/lib/Analysis/BranchProbabilityInfo.cpp,
// the only one that is a pure function of the CFG plus loop structure:
//
//   Seed a few blocks with known-bad weights (unreachable=0, noreturn=1, cold=0xffff,
//   against a normal 0xfffff), flow that backward to the branches that gate them, but
//   treat each loop as one unit whose exit edges are divided by the trip count -- so
//   staying in a loop is ~31x likelier than leaving. Normalize per branch.
//
// Loops come from a nested cycle forest built with Tao Wei's single-pass DFS (SAS
// 2007), the algorithm llvm::CycleInfo uses after PR #210301. It handles reducible and
// irreducible loops uniformly and gives each block its innermost cycle plus a
// containment relation, so nested loops stay distinct -- a flat maximal-SCC pass would
// merge them and get the inner loop wrong. BPI never asks whether a cycle is
// reducible, only about membership, enter/exit and containment.
//
// Omitted, all needing instruction-level information a bare CFG lacks:
// calcMetadataWeights, calcPointer/Zero/FloatingPointHeuristics,
// computeUnlikelySuccessors.
//
// The propagation is the real one: propagateEstimatedBlockWeight walks up a Semi-NCA
// dominator tree giving the weight to every dominator the block post-dominates, which
// needs a PostDominatorTree (dominators of the reverse CFG from a virtual exit, with
// LLVM's non-trivial roots for infinite loops). Seeds are applied in RPO and
// predecessors iterated in use-list order; both are observable. Matches post-#210301
// LLVM on every bundled CFG and on LLVM's own BPI lit tests -- see README.
//
// Input (node 0 is the entry):
//   n m
//   u v      (m directed edges u->v)
//   b K      (0+ lines: block b has kind K in {U unreachable, R noreturn, C cold})
//   P ...    (optional: explicit use-list predecessor order, emitted by ll2cfg)
#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

// --- Internal weight scale (llvm::BlockExecWeight). Weights are meaningful only
// relative to each other; at a branch they are normalized to probabilities. ---
static const uint32_t W_UNREACHABLE = 0x0;     // never runs
static const uint32_t W_LOWEST = 0x1;          // noreturn / unwind
static const uint32_t W_COLD = 0xffff;         // block with a cold call
static const uint32_t W_DEFAULT = 0xfffff;     // no information (~16x > cold)
static const uint32_t TC = 124 / 4;            // Loop Branch Heuristic trip count = 31

static int n;
static vector<vector<int>> succ, pred;
static vector<char> kind;                      // 'N','U','R','C'

// --- Nested cycle (loop) forest. ---
static vector<int> cyc;                         // innermost cycle id of a block, or -1
static vector<int> parentCyc;                   // enclosing cycle id, or -1 (top-level)
static vector<vector<int>> entries, exits;      // per-cycle, dedup'd
static vector<char> reducible;                  // per-cycle: exactly one entry?
static int nCyc;

// --- Estimated weights (the sparse "how doomed is this?" maps). -1 = unknown. ---
static vector<long long> estBlock;             // EstimatedBlockWeight
static vector<long long> estLoop;              // EstimatedLoopWeight (per cycle)

// ---------------------------------------------------------------------------
// Semi-NCA dominators (LLVM's DominatorTree algorithm), generic over the graph
// so the same code serves the CFG and the reverse CFG (post-dominators). Needed
// only by propagateEstimatedBlockWeight below; the cycle forest does not use it.
// ---------------------------------------------------------------------------
static const vector<vector<int>> *sncSucc;
static vector<int> dfn, rdfn, uf, best, sdom, sncIdom, sncPost;
static int tick;
static void sncDfs(int u) {
  best[u] = dfn[u] = tick;
  rdfn[tick++] = u;
  for (int v : (*sncSucc)[u])
    if (dfn[v] < 0) {
      uf[v] = u;
      sncDfs(v);
    }
  sncPost.push_back(u); // same DFS yields the post-order, hence the RPO
}
static int sncEval(int v, int cur) {
  if (dfn[v] <= cur)
    return v;
  int u = uf[v], r = sncEval(u, cur);
  if (best[u] < best[v])
    best[v] = best[u];
  return uf[v] = r;
}
static vector<int> computeIdom(int N, const vector<vector<int>> &gsucc,
                               const vector<vector<int>> &gpred, int root,
                               vector<int> *rpoOut = nullptr) {
  sncSucc = &gsucc;
  dfn.assign(N, -1);
  rdfn.assign(N, -1);
  uf.assign(N, -1);
  best.assign(N, 0);
  sdom.assign(N, 0);
  sncIdom.assign(N, -1); // stays -1 for unreachable vertices
  sncPost.clear();
  tick = 0;
  sncDfs(root);
  for (int i = tick; --i;) { // semidominators, in reverse preorder
    int v = rdfn[i];
    sdom[v] = i;
    for (int u : gpred[v])
      if (dfn[u] >= 0) {
        sncEval(u, i);
        if (best[u] < sdom[v])
          sdom[v] = best[u];
      }
    best[v] = sdom[v];
    sncIdom[v] = uf[v]; // provisional: the DFS parent
  }
  for (int i = 1; i < tick; i++) { // NCA: lift until preorder <= sdom
    int v = rdfn[i];
    while (dfn[sncIdom[v]] > sdom[v])
      sncIdom[v] = sncIdom[sncIdom[v]];
  }
  sncIdom[root] = root;
  if (rpoOut)
    *rpoOut = vector<int>(sncPost.rbegin(), sncPost.rend());
  return sncIdom;
}
static vector<int> idom, rpo, ipdom;
static int VEXIT;
// Post-dominators: dominators of the reverse CFG from a virtual exit pointing at
// every root -- blocks with no successors, plus the "furthest away" block of each
// reverse-unreachable region (infinite loop), mirroring LLVM's FindRoots.
static void computePDT() {
  VEXIT = n;
  vector<char> seen(n, 0);
  vector<int> roots;
  auto markReaching = [&](int s) {
    for (vector<int> stk{s}; !stk.empty();) {
      int b = stk.back();
      stk.pop_back();
      if (seen[b])
        continue;
      seen[b] = 1;
      for (int p : pred[b])
        stk.push_back(p);
    }
  };
  for (int b = 0; b < n; b++)
    if (succ[b].empty())
      roots.push_back(b), markReaching(b);
  for (int b = 0; b < n; b++) {
    if (seen[b])
      continue;
    vector<char> tmp(n, 0); // fresh per region: each search stands alone
    vector<int> order;
    for (vector<int> stk{b}; !stk.empty();) {
      int x = stk.back();
      stk.pop_back();
      if (seen[x] || tmp[x])
        continue;
      tmp[x] = 1;
      order.push_back(x);
      vector<int> ss = succ[x];
      sort(ss.begin(), ss.end()); // LLVM's SuccOrder: stable by block order
      for (int s : ss)
        stk.push_back(s);
    }
    roots.push_back(order.back());
    markReaching(order.back());
  }
  vector<vector<int>> rsucc(n + 1), rpred(n + 1);
  for (int b = 0; b < n; b++)
    rsucc[b] = pred[b], rpred[b] = succ[b];
  for (int r : roots)
    rsucc[VEXIT].push_back(r), rpred[r].push_back(VEXIT);
  ipdom = computeIdom(n + 1, rsucc, rpred, VEXIT);
}
static bool postDominates(int a, int b) {
  for (int x = b; x != -1 && x != VEXIT; x = ipdom[x])
    if (x == a)
      return true;
  return false;
}

// ---------------------------------------------------------------------------
// Step 1: identify loops with Tao Wei's algorithm (see /tmp/t/loop/wei.cpp). A
// single DFS tags every node with its innermost loop header (ilh) and marks
// headers; the loop-nesting forest is (header, ilh).  No dominator tree.
// ---------------------------------------------------------------------------
struct WNode {
  int ilh = -1;           // innermost loop header, -1 = none
  int pos = 0;            // 1-based depth on the current DFS path; 0 once off it
  bool trav = false;      // reached by the DFS?
  bool header = false;    // header of some loop?
};
static vector<WNode> wnd;

static void tagLoopHeader(int b, int h) {
  if (h == -1)
    return;
  while (b != h) {
    int ih = wnd[b].ilh;
    if (ih == -1) {
      wnd[b].ilh = h;
      return;
    }
    if (wnd[ih].pos >= wnd[h].pos)
      b = ih;
    else {
      wnd[b].ilh = h;
      b = h;
      h = ih;
    }
  }
}

static int weiDfs(int b0, int p) {
  wnd[b0].trav = true;
  wnd[b0].pos = p;
  // Visit successors LIFO, matching LLVM's iterative CycleInfo DFS (it pushes
  // successors on a stack and pops in reverse). For irreducible loops the cycle
  // forest is not canonical -- it depends on this order -- so reproducing it is
  // what makes the nesting (and thus the probabilities) match.
  for (auto it = succ[b0].rbegin(); it != succ[b0].rend(); ++it) {
    int b = *it;
    if (!wnd[b].trav) { // tree edge
      tagLoopHeader(b0, weiDfs(b, p + 1));
    } else if (wnd[b].pos > 0) { // back edge: b is a header
      wnd[b].header = true;
      tagLoopHeader(b0, b);
    } else { // forward/cross edge: climb b's header chain to the first open one
      for (int h = wnd[b].ilh; h >= 0; h = wnd[h].ilh)
        if (wnd[h].pos > 0) { // b0 is an interior node of that (still-open) loop
          tagLoopHeader(b0, h);
          break;
        }
      // (closed headers on the chain are irreducible re-entries; the generic
      //  entries computation below recovers them, so we needn't record them.)
    }
  }
  wnd[b0].pos = 0;
  return wnd[b0].ilh;
}

// Non-strict containment over the nesting forest (walking parent chains; real
// LLVM does this as an O(1) interval test over an Euler tour of the forest).
static bool cycHasCyc(int outer, int inner) { // does 'outer' contain 'inner'?
  for (int x = inner; x >= 0; x = parentCyc[x])
    if (x == outer)
      return true;
  return false;
}
static bool cycHasBlock(int c, int b) {
  for (int x = cyc[b]; x >= 0; x = parentCyc[x])
    if (x == c)
      return true;
  return false;
}

static void findCycles() {
  wnd.assign(n, WNode{});
  weiDfs(0, 1); // CycleInfo only covers blocks reachable from the entry

  // Each header becomes a cycle; a block's innermost cycle is its own if it is a
  // header, else its innermost header's. A cycle's parent is its header's.
  vector<int> cycleOf(n, -1);
  nCyc = 0;
  for (int h = 0; h < n; h++)
    if (wnd[h].header)
      cycleOf[h] = nCyc++;
  auto cycOf = [&](int h) { return h < 0 ? -1 : cycleOf[h]; };
  cyc.assign(n, -1);
  parentCyc.assign(nCyc, -1);
  for (int v = 0; v < n; v++) {
    cyc[v] = wnd[v].header ? cycleOf[v] : cycOf(wnd[v].ilh);
    if (wnd[v].header)
      parentCyc[cycleOf[v]] = cycOf(wnd[v].ilh);
  }

  // entries[c] = blocks in c with a predecessor outside c; exits[c] = blocks
  // outside c reached from within it.  "In c" = c is an ancestor-or-self of the
  // block's innermost cycle, so this respects nesting.
  entries.assign(nCyc, {});
  exits.assign(nCyc, {});
  for (int c = 0; c < nCyc; c++) {
    for (int b = 0; b < n; b++) {
      if (!cycHasBlock(c, b))
        continue;
      for (int p : pred[b])
        if (!cycHasBlock(c, p)) {
          entries[c].push_back(b);
          break;
        }
      for (int s : succ[b])
        if (!cycHasBlock(c, s))
          exits[c].push_back(s);
    }
    sort(exits[c].begin(), exits[c].end());
    exits[c].erase(unique(exits[c].begin(), exits[c].end()), exits[c].end());
  }
  reducible.assign(nCyc, 0);
  for (int c = 0; c < nCyc; c++)
    reducible[c] = entries[c].size() == 1;
}

// ---------------------------------------------------------------------------
// Step 2: edge classification, via containment of the endpoints' innermost
// cycles (mirrors isLoopEnteringEdge: entering iff dst is in a cycle that does
// NOT contain the src's cycle).
// ---------------------------------------------------------------------------
static bool entering(int u, int v) {
  if (cyc[v] < 0)
    return false;
  if (cyc[u] < 0)
    return true;
  return !cycHasCyc(cyc[v], cyc[u]); // dst-cycle contains src-cycle?
}
static bool exiting(int u, int v) { return entering(v, u); }

// getEstimatedEdgeWeight: an edge *entering* a loop takes the loop's weight, not
// the target block's; otherwise it takes the target block's weight. -1=unknown.
static long long edgeWeight(int u, int v) {
  return entering(u, v) ? estLoop[cyc[v]] : estBlock[v];
}

// getMaxEstimatedEdgeWeight: max over a set of edges, or -1 (unknown) if ANY is
// unknown -- this "all-or-nothing" rule is what makes a block count as low only
// when every path out of it is low.
static long long maxEdge(int u, const vector<int> &dsts) {
  long long mx = -1;
  for (int v : dsts) {
    long long w = edgeWeight(u, v);
    if (w < 0)
      return -1;
    mx = max(mx, w);
  }
  return mx;
}

// ---------------------------------------------------------------------------
// Step 3: the worklist fixpoint (estimateBlockWeights). Seeds propagate backward
// until stable. Assigning a block re-examines its predecessors; assigning a loop
// re-examines the blocks that enter it.
// ---------------------------------------------------------------------------
static vector<int> blockWL, loopWL;

static long long seedWeight(int b) {
  switch (kind[b]) {
  case 'U': return W_UNREACHABLE;
  case 'R': return W_LOWEST;
  case 'C': return W_COLD;
  default:  return -1;
  }
}

// updateEstimatedBlockWeight: first write wins; enqueue what it affects.
static bool updateBlockWeight(int b, long long w) {
  if (estBlock[b] >= 0)
    return false;
  estBlock[b] = w;
  for (int p : pred[b]) {
    if (exiting(p, b)) {          // p is in a loop that exits to b: try its weight
      if (estLoop[cyc[p]] < 0)
        loopWL.push_back(cyc[p]);
    } else if (estBlock[p] < 0)   // ordinary predecessor: try to derive its weight
      blockWL.push_back(p);
  }
  return true;
}
// propagateEstimatedBlockWeight: give w to bb and to every dominator of bb that
// bb post-dominates -- those run iff bb runs. Stop when post-dominance breaks,
// when a weight is already set, or when the edge crosses a cycle boundary.
static void propagate(int bb, long long w) {
  if (idom[bb] == -1) // unreachable: DT has no node, so LLVM's walk does nothing
    return;
  for (int d = bb;;) {
    if (!postDominates(bb, d))
      break;
    if (!entering(d, bb) && !exiting(d, bb)) {
      if (!updateBlockWeight(d, w))
        break;
    } else if (exiting(d, bb) && cyc[d] >= 0)
      loopWL.push_back(cyc[d]);
    if (d == 0 || idom[d] == -1)
      break;
    d = idom[d];
  }
}

static void estimateWeights() {
  estBlock.assign(n, -1);
  estLoop.assign(nCyc, -1);
  for (int b : rpo) // seed in RPO, as LLVM does
    if (long long w = seedWeight(b); w >= 0)
      propagate(b, w);
  while (!blockWL.empty() || !loopWL.empty()) {
    while (!loopWL.empty()) {
      int c = loopWL.back();
      loopWL.pop_back();
      if (estLoop[c] >= 0)
        continue;
      // Loop weight = how hot the loop is ~ max weight over where it exits to.
      long long lw = maxEdge(entries[c].empty() ? 0 : entries[c][0], exits[c]);
      if (lw < 0)
        continue;
      if (lw <= (long long)W_UNREACHABLE)
        lw = W_LOWEST;            // we enter the loop at least once
      estLoop[c] = lw;
      // Push blocks entering the loop: outside predecessors of every entry.
      for (int e : entries[c])
        for (int p : pred[e])
          if (!cycHasBlock(c, p) && estBlock[p] < 0)
            blockWL.push_back(p);
    }
    while (!blockWL.empty()) {
      int b = blockWL.back();
      blockWL.pop_back();
      if (estBlock[b] >= 0)
        continue;
      if (long long mw = maxEdge(b, succ[b]); mw >= 0)
        propagate(b, mw);
    }
  }
}

// ---------------------------------------------------------------------------
// Step 4: per-branch probabilities (the loop-relevant half of
// calcEstimatedHeuristics). Exit edges are scaled down by TC; unknown weights
// fall back to DEFAULT.
// ---------------------------------------------------------------------------
static void printProbabilities() {
  for (int b = 0; b < n; b++) {
    if ((int)succ[b].size() < 2)
      continue;
    vector<uint32_t> val(succ[b].size());
    bool found = false;
    for (size_t i = 0; i < succ[b].size(); i++) {
      int s = succ[b][i];
      long long w = edgeWeight(b, s);
      // Loop-exiting edge: scale by trip count (unless it is exactly ZERO).
      if (exiting(b, s) && w != (long long)W_UNREACHABLE) {
        uint32_t base = (w < 0) ? W_DEFAULT : (uint32_t)w;
        w = max(W_LOWEST, base / TC);
      }
      if (w >= 0)
        found = true;
      val[i] = (w < 0) ? W_DEFAULT : (uint32_t)w;
    }
    uint64_t total = 0;
    for (uint32_t v : val)
      total += v;
    // Matches calcEstimatedHeuristics' bail-out: if nothing was estimated, or
    // every successor is weight-0 (all lead to unreachable), the heuristic does
    // not apply and the branch stays uniform. LLVM also walks the blocks in
    // post-order from the entry, so unreachable blocks are never computed.
    bool uniform = idom[b] == -1 || !found || total == 0;

    printf("  block %d ->", b);
    if (uniform)
      printf("  [no estimate: uniform]");
    printf("\n");
    for (size_t i = 0; i < succ[b].size(); i++) {
      int s = succ[b][i];
      const char *tag = entering(b, s) ? " enter" : exiting(b, s) ? " exit " : "      ";
      double p = uniform ? 100.0 / succ[b].size() : 100.0 * val[i] / (double)total;
      printf("      -> %d %s  weight=%-8u  p=%6.2f%%\n", s, tag, val[i], p);
    }
  }
}

int main() {
  int m;
  if (scanf("%d %d", &n, &m) != 2)
    return 0;
  succ.assign(n, {});
  pred.assign(n, {});
  kind.assign(n, 'N');
  for (int i = 0; i < m; i++) {
    int u, v;
    if (scanf("%d %d", &u, &v) != 2)
      return 1;
    succ[u].push_back(v);
    pred[v].push_back(u);
  }
  int b;
  char k;
  while (scanf(" %d %c", &b, &k) == 2)
    if (b >= 0 && b < n)
      kind[b] = k;
  // Optional explicit predecessor order (LLVM's use-list order), emitted by
  // ll2cfg. Absent for hand-written inputs, which keep the derived order.
  char sect;
  if (scanf(" %c", &sect) == 1 && sect == 'P') {
    for (int i = 0; i < n; i++) {
      int v, c;
      if (scanf("%d %d", &v, &c) != 2)
        break;
      pred[v].clear();
      for (int j = 0; j < c; j++) {
        int p;
        if (scanf("%d", &p) == 1)
          pred[v].push_back(p);
      }
    }
  } else {
    // LLVM's predecessors() walks the block's use list, i.e. reverse of
    // construction order. Worklist push order depends on it, and that is
    // observable: a cycle whose exit edge enters another cycle needs that
    // cycle's weight, and is never re-queued once it lands.
    for (auto &v : pred)
      reverse(v.begin(), v.end());
  }

  idom = computeIdom(n, succ, pred, 0, &rpo);
  computePDT();
  findCycles();
  estimateWeights();


  printf("cycles (loops), indented by nesting:\n");
  if (nCyc == 0)
    printf("  (none)\n");
  // Depth-first over the nesting forest so children print under their parent.
  auto printCycle = [&](auto &&self, int c, int depth) -> void {
    printf("%*s cycle %d [%s]  blocks {", 2 + 2 * depth, "", c,
           reducible[c] ? "reducible" : "IRREDUCIBLE");
    // blocks = everything in the cycle, nested sub-cycles included (this is what
    // CycleInfo::getBlocks returns); innermost = the blocks whose innermost
    // cycle this is.
    for (int b = 0; b < n; b++)
      if (cycHasBlock(c, b))
        printf(" %d", b);
    printf(" }  innermost {");
    for (int b = 0; b < n; b++)
      if (cyc[b] == c)
        printf(" %d", b);
    printf(" }  entries {");
    for (int e : entries[c])
      printf(" %d", e);
    printf(" }  exits {");
    for (int x : exits[c])
      printf(" %d", x);
    printf(" }  loopWeight=%lld\n", estLoop[c]);
    for (int k = 0; k < nCyc; k++)
      if (parentCyc[k] == c)
        self(self, k, depth + 1);
  };
  for (int c = 0; c < nCyc; c++)
    if (parentCyc[c] == -1)
      printCycle(printCycle, c, 0);
  printf("estimated block weights (unknown blocks default to %u at a branch):\n",
         W_DEFAULT);
  for (int i = 0; i < n; i++)
    if (estBlock[i] >= 0)
      printf("  block %d = %lld\n", i, estBlock[i]);
  printf("branch probabilities:\n");
  printProbabilities();
  return 0;
}

bpi_prepatch.cpp

// bpi.cpp's twin, using the PRE-#210301 design of LLVM's BranchProbabilityInfo.
// Only the loop model differs -- the weight scale, the propagation, the worklist and
// the per-branch normalization are identical -- so diffing this against bpi.cpp
// isolates exactly what PR #210301 changes.
//
// Instead of one nested cycle forest, BPI used two analyses:
//   LoopInfo -- dominator-based NATURAL loops. Nested, but blind to irreducible
//               loops, which have no single dominating header.
//   SccInfo  -- flat maximal Tarjan SCCs, consulted only for the blocks LoopInfo
//               left unclaimed, i.e. the irreducible ones. "SCCs can't be nested."
// A block routes to its natural loop if it has one, else to its SCC: the old
// LoopBlock = {Loop*, sccNum} pair. Note SccInfo is never consulted for a block
// LoopInfo already claimed, so an irreducible cycle nested inside a natural loop is
// invisible to this model -- every branch in it falls back to uniform.
//
// Input (node 0 is the entry):
//   n m
//   u v      (m directed edges u->v)
//   b K      (0+ lines: block b has kind K in {U unreachable, R noreturn, C cold})
//   P ...    (optional: explicit use-list predecessor order, emitted by ll2cfg)
#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <vector>
using namespace std;

static const uint32_t W_UNREACHABLE = 0x0, W_LOWEST = 0x1, W_COLD = 0xffff,
                      W_DEFAULT = 0xfffff, TC = 124 / 4;

static int n;
static vector<vector<int>> succ, pred;
static vector<char> kind;

// ---------------------------------------------------------------------------
// Semi-NCA (Georgiadis), the algorithm LLVM's DominatorTree uses. idom(v) is the
// nearest common ancestor of sdom(v) and parent(v): walk up v's ancestor path
// for the deepest vertex whose preorder number is <= sdom(v)'s. sdom[]/best[]
// hold preorder NUMBERS so they compare directly. Generic over the graph, so it
// serves both the CFG (dominators) and the reverse CFG (post-dominators).
// ---------------------------------------------------------------------------
static const vector<vector<int>> *sncSucc;
static vector<int> dfn, rdfn, uf, best, sdom, sncIdom, sncPost;
static int tick;
static void sncDfs(int u) {
  best[u] = dfn[u] = tick;
  rdfn[tick++] = u;
  for (int v : (*sncSucc)[u])
    if (dfn[v] < 0) {
      uf[v] = u;
      sncDfs(v);
    }
  sncPost.push_back(u); // the same DFS also yields the post-order, hence the RPO
}
static int sncEval(int v, int cur) {
  if (dfn[v] <= cur)
    return v;
  int u = uf[v], r = sncEval(u, cur);
  if (best[u] < best[v])
    best[v] = best[u];
  return uf[v] = r; // path compression
}
static vector<int> computeIdom(int N, const vector<vector<int>> &gsucc,
                               const vector<vector<int>> &gpred, int root,
                               vector<int> *rpoOut = nullptr) {
  sncSucc = &gsucc;
  dfn.assign(N, -1);
  rdfn.assign(N, -1);
  uf.assign(N, -1);
  best.assign(N, 0);
  sdom.assign(N, 0);
  sncIdom.assign(N, -1); // stays -1 for unreachable vertices
  sncPost.clear();
  tick = 0;
  sncDfs(root);
  for (int i = tick; --i;) { // semidominators, in reverse preorder
    int v = rdfn[i];
    sdom[v] = i;
    for (int u : gpred[v])
      if (dfn[u] >= 0) {
        sncEval(u, i);
        if (best[u] < sdom[v])
          sdom[v] = best[u];
      }
    best[v] = sdom[v];
    sncIdom[v] = uf[v]; // provisional: the DFS parent
  }
  for (int i = 1; i < tick; i++) { // NCA: lift until preorder <= sdom
    int v = rdfn[i];
    while (dfn[sncIdom[v]] > sdom[v])
      sncIdom[v] = sncIdom[sncIdom[v]];
  }
  sncIdom[root] = root;
  if (rpoOut)
    *rpoOut = vector<int>(sncPost.rbegin(), sncPost.rend());
  return sncIdom;
}

// Dominator tree of the CFG. Unreachable blocks keep idom == -1.
static vector<int> idom, rpo;
static bool dom(int a, int b) { // idom[root] == root, so that ends the walk
  for (int x = b; x != -1; x = (x == idom[x] ? -1 : idom[x]))
    if (x == a)
      return true;
  return false;
}

// Post-dominator tree: dominators of the reverse CFG from a virtual exit
// pointing at every root. Roots are the blocks with no successors, plus -- per
// reverse-unreachable region (an infinite loop) -- the "furthest away" block a
// forward DFS reaches, mirroring LLVM's FindRoots.
static vector<int> ipdom;
static int VEXIT;
static void computePDT() {
  VEXIT = n;
  vector<char> seen(n, 0);
  vector<int> roots;
  auto markReaching = [&](int s) {
    for (vector<int> stk{s}; !stk.empty();) {
      int b = stk.back();
      stk.pop_back();
      if (seen[b])
        continue;
      seen[b] = 1;
      for (int p : pred[b])
        stk.push_back(p);
    }
  };
  for (int b = 0; b < n; b++)
    if (succ[b].empty())
      roots.push_back(b), markReaching(b);
  for (int b = 0; b < n; b++) {
    if (seen[b])
      continue;
    vector<char> tmp(n, 0); // fresh per region: each search stands alone
    vector<int> order;
    for (vector<int> stk{b}; !stk.empty();) {
      int x = stk.back();
      stk.pop_back();
      if (seen[x] || tmp[x])
        continue;
      tmp[x] = 1;
      order.push_back(x);
      vector<int> ss = succ[x];
      sort(ss.begin(), ss.end()); // LLVM's SuccOrder: stable by block order
      for (int s : ss)
        stk.push_back(s);
    }
    roots.push_back(order.back());
    markReaching(order.back());
  }
  vector<vector<int>> rsucc(n + 1), rpred(n + 1);
  for (int b = 0; b < n; b++)
    rsucc[b] = pred[b], rpred[b] = succ[b];
  for (int r : roots)
    rsucc[VEXIT].push_back(r), rpred[r].push_back(VEXIT);
  ipdom = computeIdom(n + 1, rsucc, rpred, VEXIT);
}
static bool postDominates(int a, int b) {
  for (int x = b; x != -1 && x != VEXIT; x = ipdom[x])
    if (x == a)
      return true;
  return false;
}

// ---------------------------------------------------------------------------
// LoopInfo: natural loops. A back-edge is a->h with dom(h,a); the loop body is
// h plus everything reaching a latch without passing h (so it includes nested
// sub-loops). Loops sharing a header are one loop.
// ---------------------------------------------------------------------------
static int nLoops;
static vector<int> loopHeader, loopSize, loopOf;
static vector<vector<char>> loopBody;
static void buildNaturalLoops() {
  vector<vector<int>> latches(n);
  for (int a = 0; a < n; a++) {
    if (idom[a] == -1) // unreachable: dominated by everything, LoopInfo skips it
      continue;
    for (int h : succ[a])
      if (dom(h, a))
        latches[h].push_back(a);
  }
  loopHeader.clear();
  for (int h = 0; h < n; h++)
    if (!latches[h].empty())
      loopHeader.push_back(h);
  nLoops = loopHeader.size();
  loopBody.assign(nLoops, vector<char>(n, 0));
  loopSize.assign(nLoops, 0);
  for (int l = 0; l < nLoops; l++) {
    auto &body = loopBody[l];
    body[loopHeader[l]] = 1;
    loopSize[l] = 1;
    vector<int> stk;
    for (int a : latches[loopHeader[l]])
      if (!body[a])
        body[a] = 1, ++loopSize[l], stk.push_back(a);
    while (!stk.empty()) {
      int x = stk.back();
      stk.pop_back();
      for (int p : pred[x])
        if (idom[p] != -1 && !body[p]) // LoopInfo skips unreachable predecessors
          body[p] = 1, ++loopSize[l], stk.push_back(p);
    }
  }
  loopOf.assign(n, -1); // innermost = smallest body containing the block
  for (int b = 0; b < n; b++)
    for (int l = 0, sm = 1 << 30; l < nLoops; l++)
      if (loopBody[l][b] && loopSize[l] < sm)
        sm = loopSize[l], loopOf[b] = l;
}
static bool loopContains(int outer, int inner) {
  return inner != -1 && loopBody[outer][loopHeader[inner]];
}

// ---------------------------------------------------------------------------
// SccInfo: flat Tarjan SCCs, kept only for blocks with no natural loop.
// ---------------------------------------------------------------------------
static int tIdx, nComp;
static vector<int> tnum, comp, tstk;
static vector<char> multi; // per component: does it actually cycle?
// An unnumbered comp[] entry already means "still on the stack", so no onStk[];
// the low-link rides the return value, so no low[]; and whether a component is
// a real cycle falls out of the pop count plus a self-edge check, so no size[].
static int tarjan(int v) {
  int low = tIdx, self = 0;
  tnum[v] = tIdx++;
  tstk.push_back(v);
  for (int u : succ[v]) {
    self |= u == v;
    if (tnum[u] < 0)
      low = min(low, tarjan(u));
    else if (comp[u] < 0)
      low = min(low, tnum[u]);
  }
  if (low == tnum[v]) {
    int u, cnt = 0;
    do
      comp[u = tstk.back()] = nComp, tstk.pop_back(), ++cnt;
    while (u != v);
    multi.push_back(cnt > 1 || self); // a lone block cycles only via a self-edge
    ++nComp;
  }
  return low;
}
static void buildSCC() {
  tnum.assign(n, -1);
  comp.assign(n, -1);
  tstk.clear();
  multi.clear();
  tIdx = nComp = 0;
  if (n)
    tarjan(0); // scc_begin(&F) walks from the entry only
}
// SccInfo::getSCCNum -- the component, but only for blocks LoopInfo did not
// already claim. A derived view of comp[], not a second array.
static int sccOf(int b) {
  return loopOf[b] == -1 && comp[b] >= 0 && multi[comp[b]] ? comp[b] : -1;
}

// ---------------------------------------------------------------------------
// Units: the loop-like nodes the weight engine keys on -- one per natural loop
// (id 0..nLoops-1), one per SCC (id nLoops+comp).
// ---------------------------------------------------------------------------
static int nUnits;
static vector<int> unitOf, unitRep;
static vector<vector<int>> enterBlocks, exitBlocks;
static bool inUnit(int u, int b) {
  return u < nLoops ? (bool)loopBody[u][b] : comp[b] == u - nLoops;
}
static void buildUnits() {
  nUnits = nLoops + nComp;
  unitOf.assign(n, -1);
  for (int b = 0; b < n; b++)
    unitOf[b] = loopOf[b] >= 0   ? loopOf[b]
                : sccOf(b) >= 0  ? nLoops + comp[b]
                                 : -1;
  unitRep.assign(nUnits, -1);
  enterBlocks.assign(nUnits, {});
  exitBlocks.assign(nUnits, {});
  for (int u = 0; u < nUnits; u++) {
    bool isLoop = u < nLoops;
    if (!isLoop && !multi[u - nLoops])
      continue;
    // Exits are the same idea for both: successors that leave the unit.
    for (int b = 0; b < n; b++)
      if (inUnit(u, b)) {
        if (unitRep[u] == -1)
          unitRep[u] = b;
        for (int s : succ[b])
          if (!inUnit(u, s))
            exitBlocks[u].push_back(s);
      }
    // Enters are where pre-patch BPI is asymmetric: a natural loop takes the
    // header's predecessors, an SCC takes the in-SCC block itself, once per
    // incoming edge from outside.
    if (isLoop) {
      unitRep[u] = loopHeader[u];
      enterBlocks[u] = pred[loopHeader[u]];
    } else {
      for (int b = 0; b < n; b++)
        if (inUnit(u, b))
          for (int p : pred[b])
            if (!inUnit(u, p))
              enterBlocks[u].push_back(b);
    }
  }
}

// isLoopEnteringEdge: a block sits in a natural loop or an SCC, never both, so
// whichever it is decides. Loops nest (containment); SCCs don't (equality).
static bool entering(int u, int v) {
  if (loopOf[v] != -1)
    return !loopContains(loopOf[v], loopOf[u]);
  if (sccOf(v) != -1)
    return sccOf(u) != sccOf(v);
  return false;
}
static bool exiting(int u, int v) { return entering(v, u); }

// ---------------------------------------------------------------------------
// Estimated weights.
// ---------------------------------------------------------------------------
static vector<long long> estBlock, estLoop;
static vector<int> blockWL, loopWL;
static long long seedWeight(int b) {
  switch (kind[b]) {
  case 'U': return W_UNREACHABLE;
  case 'R': return W_LOWEST;
  case 'C': return W_COLD;
  default:  return -1;
  }
}
static long long edgeWeight(int u, int v) {
  return entering(u, v) ? estLoop[unitOf[v]] : estBlock[v];
}
static long long maxEdge(int u, const vector<int> &dsts) {
  long long mx = -1;
  for (int v : dsts) {
    long long w = edgeWeight(u, v);
    if (w < 0)
      return -1;
    mx = max(mx, w);
  }
  return mx;
}
// updateEstimatedBlockWeight: first write wins; enqueue what it affects.
static bool updateBlockWeight(int b, long long w) {
  if (estBlock[b] >= 0)
    return false;
  estBlock[b] = w;
  for (int p : pred[b]) {
    if (exiting(p, b)) {
      if (unitOf[p] >= 0 && estLoop[unitOf[p]] < 0)
        loopWL.push_back(unitOf[p]);
    } else if (estBlock[p] < 0)
      blockWL.push_back(p);
  }
  return true;
}
// propagateEstimatedBlockWeight: give w to bb and to every dominator of bb that
// bb post-dominates -- those run iff bb runs. Stop when post-dominance breaks,
// when a weight is already set, or when the edge crosses a loop boundary.
static void propagate(int bb, long long w) {
  if (idom[bb] == -1) // unreachable: DT has no node, so LLVM's walk does nothing
    return;
  for (int d = bb;;) {
    if (!postDominates(bb, d))
      break;
    if (!entering(d, bb) && !exiting(d, bb)) {
      if (!updateBlockWeight(d, w))
        break;
    } else if (exiting(d, bb) && unitOf[d] >= 0)
      loopWL.push_back(unitOf[d]);
    if (d == 0 || idom[d] == -1)
      break;
    d = idom[d];
  }
}
static void estimateWeights() {
  estBlock.assign(n, -1);
  estLoop.assign(nUnits, -1);
  for (int b : rpo) // seed in RPO, as LLVM does
    if (long long w = seedWeight(b); w >= 0)
      propagate(b, w);
  while (!blockWL.empty() || !loopWL.empty()) {
    while (!loopWL.empty()) {
      int c = loopWL.back();
      loopWL.pop_back();
      if (estLoop[c] >= 0)
        continue;
      long long lw = maxEdge(unitRep[c], exitBlocks[c]);
      if (lw < 0)
        continue;
      estLoop[c] = lw <= (long long)W_UNREACHABLE ? W_LOWEST : lw;
      for (int p : enterBlocks[c])
        if (estBlock[p] < 0)
          blockWL.push_back(p);
    }
    while (!blockWL.empty()) {
      int b = blockWL.back();
      blockWL.pop_back();
      if (estBlock[b] >= 0)
        continue;
      if (long long mw = maxEdge(b, succ[b]); mw >= 0)
        propagate(b, mw);
    }
  }
}

static void printProbabilities() {
  for (int b = 0; b < n; b++) {
    if ((int)succ[b].size() < 2)
      continue;
    vector<uint32_t> val(succ[b].size());
    bool found = false;
    for (size_t i = 0; i < succ[b].size(); i++) {
      long long w = edgeWeight(b, succ[b][i]);
      if (exiting(b, succ[b][i]) && w != (long long)W_UNREACHABLE)
        w = max(W_LOWEST, (w < 0 ? W_DEFAULT : (uint32_t)w) / TC);
      if (w >= 0)
        found = true;
      val[i] = (w < 0) ? W_DEFAULT : (uint32_t)w;
    }
    uint64_t total = 0;
    for (uint32_t v : val)
      total += v;
    // LLVM also walks the blocks in post-order from the entry, so unreachable
    // blocks are never computed and keep uniform probabilities.
    bool uniform = idom[b] == -1 || !found || total == 0;
    printf("  block %d ->%s\n", b, uniform ? "  [no estimate: uniform]" : "");
    for (size_t i = 0; i < succ[b].size(); i++) {
      int s = succ[b][i];
      const char *tag = entering(b, s) ? " enter" : exiting(b, s) ? " exit " : "      ";
      double p = uniform ? 100.0 / succ[b].size() : 100.0 * val[i] / (double)total;
      printf("      -> %d %s  weight=%-8u  p=%6.2f%%\n", s, tag, val[i], p);
    }
  }
}

int main() {
  int m;
  if (scanf("%d %d", &n, &m) != 2)
    return 0;
  succ.assign(n, {});
  pred.assign(n, {});
  kind.assign(n, 'N');
  for (int i = 0; i < m; i++) {
    int u, v;
    if (scanf("%d %d", &u, &v) != 2)
      return 1;
    succ[u].push_back(v);
    pred[v].push_back(u);
  }
  int b;
  char k;
  while (scanf(" %d %c", &b, &k) == 2)
    if (b >= 0 && b < n)
      kind[b] = k;
  // Optional explicit predecessor order (LLVM's use-list order, which an edge
  // list cannot encode). Without it, fall back to reversing the derived order.
  char sect;
  if (scanf(" %c", &sect) == 1 && sect == 'P') {
    for (int i = 0; i < n; i++) {
      int v, c;
      if (scanf("%d %d", &v, &c) != 2)
        break;
      pred[v].clear();
      for (int j = 0; j < c; j++) {
        int p;
        if (scanf("%d", &p) == 1)
          pred[v].push_back(p);
      }
    }
  } else {
    for (auto &v : pred)
      reverse(v.begin(), v.end());
  }

  idom = computeIdom(n, succ, pred, 0, &rpo);
  computePDT();
  buildNaturalLoops();
  buildSCC();
  buildUnits();
  estimateWeights();

  printf("units (loop = natural/reducible, SCC = irreducible fallback), "
         "indented by nesting:\n");
  // Natural loops nest; SCCs never do ("SCCs can't be nested"), so every SCC sits
  // at the top level. A loop's parent is the smallest loop strictly containing it.
  vector<int> loopParent(nLoops, -1);
  for (int l = 0; l < nLoops; l++)
    for (int m = 0; m < nLoops; m++)
      if (m != l && loopSize[m] > loopSize[l] && loopBody[m][loopHeader[l]] &&
          (loopParent[l] == -1 || loopSize[m] < loopSize[loopParent[l]]))
        loopParent[l] = m;

  bool anyUnit = false;
  auto printUnit = [&](int u, int depth) {
    anyUnit = true;
    bool isLoop = u < nLoops;
    // blocks = the whole body, nested sub-loops included (what contains() means)
    // innermost = the blocks this unit is the innermost one for. An SCC with no
    // innermost blocks was computed but is never consulted, because LoopInfo
    // claimed every one of its blocks first.
    printf("%*s unit %d [%s]  blocks {", 2 + 2 * depth, "", u,
           isLoop ? "loop" : "SCC ");
    for (int b = 0; b < n; b++)
      if (inUnit(u, b))
        printf(" %d", b);
    printf(" }  innermost {");
    int nInner = 0;
    for (int b = 0; b < n; b++)
      if (unitOf[b] == u)
        printf(" %d", b), ++nInner;
    printf(" }  %s=%d  weight=%lld%s\n", isLoop ? "header" : "rep",
           isLoop ? loopHeader[u] : unitRep[u], estLoop[u],
           nInner ? "" : "  [never consulted]");
  };
  auto printLoopTree = [&](auto &&self, int l, int depth) -> void {
    printUnit(l, depth);
    for (int k = 0; k < nLoops; k++)
      if (loopParent[k] == l)
        self(self, k, depth + 1);
  };
  for (int l = 0; l < nLoops; l++)
    if (loopParent[l] == -1)
      printLoopTree(printLoopTree, l, 0);
  for (int u = nLoops; u < nUnits; u++) {
    if (!multi[u - nLoops])
      continue; // SccInfo ignores single-block SCCs
    bool any = false;
    for (int b = 0; b < n && !any; b++)
      any = inUnit(u, b);
    if (any)
      printUnit(u, 0);
  }
  if (!anyUnit)
    printf("  (none)\n");
  printf("estimated block weights (unknown blocks default to %u at a branch):\n",
         W_DEFAULT);
  for (int i = 0; i < n; i++)
    if (estBlock[i] >= 0)
      printf("  block %d = %lld\n", i, estBlock[i]);
  printf("branch probabilities:\n");
  printProbabilities();
  return 0;
}

ll2cfg.cpp

// Convert a .ll file into the numeric CFG format bpi.cpp / bpi_prepatch.cpp
// read, one file per function, using LLVM's own parser so block order,
// successor order and predecessor order are exactly what BPI sees.
//
//   ll2cfg in.ll outdir stem
//
// Writes, per function:
//   outdir/<stem>__<fn>.txt   n m / m "u v" edges / "b K" kinds / "P" + pred lists
//   outdir/<stem>__<fn>.meta  "func <name>", "name <idx> %<bbname>",
//                             "prof <idx>" for terminators carrying !prof
#include "llvm/ADT/STLExtras.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IRReader/IRReader.h"
#include "llvm/Support/SourceMgr.h"
#include "llvm/Support/raw_ostream.h"
#include <map>
#include <string>
using namespace llvm;

// Mirrors BPIConstruction::getInitialEstimatedBlockWeight's ordering exactly.
static char kindOf(const BasicBlock &BB) {
  auto hasNoReturn = [&] {
    for (const Instruction &I : reverse(BB))
      if (const auto *CI = dyn_cast<CallInst>(&I))
        if (CI->hasFnAttr(Attribute::NoReturn))
          return true;
    return false;
  };
  if (isa<UnreachableInst>(BB.getTerminator()) || BB.getTerminatingDeoptimizeCall())
    return hasNoReturn() ? 'R' : 'U'; // NORETURN(1) : UNREACHABLE(0)
  if (BB.isEHPad())
    return 'R'; // UNWIND shares LOWEST_NON_ZERO with NORETURN
  for (const Instruction &I : BB)
    if (const auto *CI = dyn_cast<CallInst>(&I))
      if (CI->hasFnAttr(Attribute::Cold))
        return 'C';
  return 'N';
}

static std::string bbName(const BasicBlock &BB) {
  std::string s;
  raw_string_ostream os(s);
  BB.printAsOperand(os, false); // same form BPI's printer emits
  return os.str();
}

int main(int argc, char **argv) {
  if (argc != 4) {
    errs() << "usage: ll2cfg in.ll outdir stem\n";
    return 1;
  }
  LLVMContext Ctx;
  SMDiagnostic Err;
  auto M = parseIRFile(argv[1], Err, Ctx);
  if (!M) {
    Err.print("ll2cfg", errs());
    return 1;
  }
  for (const Function &F : *M) {
    if (F.isDeclaration())
      continue;
    std::map<const BasicBlock *, int> idx;
    int n = 0;
    for (const BasicBlock &BB : F)
      idx[&BB] = n++;

    std::string base = std::string(argv[2]) + "/" + argv[3] + "__" + F.getName().str();
    std::error_code EC;
    raw_fd_ostream cfg(base + ".txt", EC);
    raw_fd_ostream meta(base + ".meta", EC);
    if (EC) {
      errs() << "cannot write " << base << ": " << EC.message() << "\n";
      return 1;
    }

    int m = 0;
    for (const BasicBlock &BB : F)
      m += BB.getTerminator()->getNumSuccessors();
    cfg << n << " " << m << "\n";
    for (const BasicBlock &BB : F)
      for (const BasicBlock *S : successors(&BB))
        cfg << idx[&BB] << " " << idx[S] << "\n";
    for (const BasicBlock &BB : F)
      if (char k = kindOf(BB); k != 'N')
        cfg << idx[&BB] << " " << k << "\n";
    // Explicit predecessor order: use-list order, which an edge list cannot
    // encode (it is not derivable from successor order).
    cfg << "P\n";
    for (const BasicBlock &BB : F) {
      int c = 0;
      for (const BasicBlock *P : predecessors(&BB))
        (void)P, ++c;
      cfg << idx[&BB] << " " << c;
      for (const BasicBlock *P : predecessors(&BB))
        cfg << " " << idx[P];
      cfg << "\n";
    }

    meta << "func " << F.getName() << "\n";
    for (const BasicBlock &BB : F)
      meta << "name " << idx[&BB] << " " << bbName(BB) << "\n";
    for (const BasicBlock &BB : F)
      if (BB.getTerminator()->getMetadata(LLVMContext::MD_prof))
        meta << "prof " << idx[&BB] << "\n";
  }
  return 0;
}