Rust Compiler Bug: Control Flow Graph out of control

How a synthetic graph edge in rustc and an unsigned cast in llvm-cov turned 0 executions into 18.4 quintillion.

How it started

Trusty is a secure operating system that provides a Trusted Execution Environment for Pixels. Ages ago, I had some code coverage framework setup for it. That itself was a very interesting problem to solve because of its concurrency issues, runtime limitations such as lack of file system APIs, etc. Anyways, not the point of this blogpost.

Recently, some considerable changes were made, so I had some agents monitor the nightly coverage runs, and they filed some bugs. My triaging agents found the bug, thought it was an issue with the higher-level framework that collects numbers, and tried to add a "clamp" there to make sure the number of times a line was covered stayed in [0, numeric_limits<uint64_t>::max()]. That was pretty sus. Why are the numbers negative in the first place??

And more specifically, why was our LCOV file claiming a single error-handling line in a Trusty TA had executed 18,446,744,073,709,551,599 times (18.4E in llvm-cov) during a 30-second test run?

If you do the math, $2^{64} - 18446744073709551599 = 17$. The line hadn't run 18.4 quintillion times. It had run $-17$ times.

Silly me, thinking coverage counters only go up.

Compressing the CF graph (a primer)

Before we go there, I think some primer on how Rust MIR (Mid-level Intermediate Representation) interacts with code coverage is in order.

When you compile with -Cinstrument-coverage, the naive approach is to stick a physical counter increment (atomicrmw add) in every single basic block of your program. That works, but it bloats the binary's __llvm_prf_cnts section and hammers memory bandwidth on every branch.

Instead, rustc tries to be smart. It compresses the Control Flow Graph (CFG) and uses counter expressions, so the binary only measures a subset of blocks at runtime and the rest get derived with addition and subtraction when the report is generated.

This happens in two main phases inside rustc_mir_transform::coverage.

First, super blocks (Basic Coverage Blocks)

Raw MIR has way too many basic blocks. Every function call, assert!, drop, and borrow-checker false edge splits a block in MIR. For coverage, we don't care about most of those edges. If block A unconditionally flows into block B and B has no other predecessors, they execute the exact same number of times (assuming no panics).

So rustc first condenses the MIR CFG into a CoverageGraph made of Basic Coverage Blocks (BCBs), using two rules:

• Chain linear blocks. If block A has a single coverage-relevant successor B, and A is B's only predecessor, the two get merged into one BCB.
• Ignore unwind edges. Normal function calls (TerminatorKind::Call) and compiler assertions (TerminatorKind::Assert) are assumed to return normally (is_out_summable = true). Their unwind edges are stripped out of the coverage graph, so a sequence of calls can be chained into a single BCB.

That shrinks the graph a lot. Next, rustc wants to apply Kirchhoff's circuit law (flow conservation) to every node:

$$\text{flow}(\text{node}) = \sum \text{in-edges} = \sum \text{out-edges}$$

Real control-flow graphs aren't conserved circuits, though:

• START_BCB (function entry) has out-edges, but no in-edges.
• Return blocks (and diverging calls) have in-edges, but no out-edges (is_out_summable = false).
• Infinite loops (loop {}) trap flow forever without reaching a return.

To force the graph to have "balanced flow", rustc wraps it in a BalancedFlowGraph, which adds a synthetic sink node with:

1. Synthetic in-edges exit -> sink from every Return / Yield / diverging node (and any inescapable loop).
2. One giant synthetic out-edge sink -> START_BCB looping all the way back to the start of the function.

   +-------------------------------------------+
   |            (synthetic edge)               |
   v                                           |
[START_BCB] ---> ... (CFG body) ... ---> [Return BCBs] ---> [sink]

That sink -> START_BCB edge comes back later. It assumes something big: every time a function is entered, it must eventually exit.

$$\text{flow}(\text{START\BCB}) \equiv \sum{e \in \text{exits}} \text{flow}(e)$$

Then Knuth–Stevenson (collapsing spanning-tree edges)

In January 2025 (PR #135481, shipped in Rust 1.86), rustc overhauled its counter assignment to use the classic algorithm from Knuth & Stevenson (1973), "Optimal measurement points for program frequency counts".

On the BalancedFlowGraph, it runs in two steps:

1. Merge sibling targets into supernodes (UnionFind). For every node $u$, all of its outgoing successors are unified into a single equivalence class (a supernode). Because u's flow equals the sum of flows into its successors, each BCB $u$ now acts as a directed edge $\text{super}(u) \to \text{succ\_super}(u)$ in a compressed supernode graph.
2. Build a spanning tree. rustc walks the BCBs in a deliberately chosen priority_list order:
   • If a BCB's edge connects two supernodes that aren't connected yet, it claims a spanning-tree edge. Tree edges get counter expressions, which cost nothing at runtime.
   • If a BCB's edge would form a cycle in the spanning tree, it gets a physical counter (c0, c1, ...), and pushes +c or -c onto every tree edge along that cycle.

Because earlier nodes in priority_list get expressions and later nodes get physical counters, the sort order in counters.rs decides what gets measured vs. derived:

// First node is ALWAYS the synthetic sink (must never get a physical counter).
assert_eq!(nodes[0], balanced_graph.sink);

// Sort real nodes: earlier (lesser) = expression, later (greater) = physical counter.
nodes[1..].sort_by(|&a, &b| {
    Ordering::Equal
        // Prefer a physical counter for return/yield nodes.
        .then_with(|| Ord::cmp(&graph[a].is_out_summable, &graph[b].is_out_summable))
        // Prefer an expression for reloop nodes.
        .then_with(|| Ord::cmp(&is_reloop_node[a], &is_reloop_node[b]).reverse())
        // Otherwise, prefer a physical counter for dominating nodes.
        .then_with(|| graph.cmp_in_dominator_order(a, b).reverse())
});

The bug is in the first comparator (counters.rs:68-69):

// Prefer a physical counter for return/yield nodes.
.then_with(|| Ord::cmp(&graph[a].is_out_summable, &graph[b].is_out_summable))

The other two comparators have .reverse(). This one doesn't.

In Rust, false < true, and for a Return node is_out_summable is false. So sorting without .reverse() puts Return nodes (false) at the very front of priority_list, which gives them counter expressions. That's the exact opposite of what the comment above it says.

The issue

Say we have a long-running worker loop in a service that polls for requests and handles errors:

fn run_worker() -> Result<(), Error> {
    loop {
        let err = match poll_next() {
            Ok(()) => continue,
            Err(err) => err,
        };

        match err {
            Error::Retry => {
                // Transient error: keep looping
            }
            Error::Backoff => {
                // Log and keep looping
            }
            Error::Fatal => {
                // Unrecoverable: exit the worker loop
                return Err(err);
            }
        }
    }
}

What our compressed CFG looks like

When rustc lowers run_worker into Basic Coverage Blocks, we get 8 BCBs (bcb0 through bcb7) plus the synthetic sink:

       [bcb0: entry] <------------------------------------+
             |                                            |
             v                                            |
     +-> [bcb1: loop header / poll_next()]                |
     |       |                    |                       |
     |  Ok   |                    | Err                   | (synthetic
     |       v                    v                       |  sink edge)
     +-- [bcb7: continue]   [bcb2: match err]             |
     |                      /       |        \            |
     |               Retry / Backoff|         \ Fatal     |
     |                    v         v          v          |
     |               [bcb6]      [bcb4]    [bcb3: return] |
     |                    \         /             |       |
     |                     v       v              v       |
     +------------------ [bcb5: join]          [sink] ----+

Knuth–Stevenson then walks this graph in the following order:

1. sink goes first. It claims the tree edge sink -> bcb0, which locks in flow(sink) == flow(bcb0) for good.
2. bcb3 (return Err) goes second. Because of the missing .reverse(), bcb3 (is_out_summable == false) gets sorted right after sink. And since bcb3 is the only exit from the function into sink, its counter expression is simply: $$\text{flow}(\text{bcb3: return Err}) = c_0 \text{ (entry)}$$
3. Then come the sibling arms of match err (bcb2). bcb2 branches three ways into {bcb6, bcb4, bcb3}. Since bcb3 already claimed an expression (= c0), rustc gives physical counters to bcb2 (c2), bcb4 (c4), bcb0 (c0), and bcb1 (c1). That leaves bcb6 (Retry) to be derived by subtracting its two siblings from their parent bcb2: $$\text{flow}(\text{bcb6: retry}) = c_2 - (c_0 + c_4)$$

bcb2, bcb6, and bcb4 all live inside the Err branch of the loop. But the formula for bcb6 subtracts c0, the function entry counter.

How it became negative

In a desktop CLI tool, main() runs, functions return, and the program exits cleanly. Every function entered $N$ times also returns $N$ times.

Background services and event loops don't work like that. Suppose 17 worker instances enter run_worker(). They sit in that loop for the entire lifetime of the test, servicing thousands of Ok(()) requests and blocking in poll_next(). When the test suite finishes and dumps coverage profiles, all 17 frames are still live inside the loop, and none of them has ever returned.

At profile-dump time, the physical counters in memory are:

• c0 (bcb0: entry) = 17 (17 workers entered run_worker)
• c1 (bcb1: loop header) = 17017 (17,000 Ok iterations + 17 currently blocked in poll_next())
• c2 (bcb2: Err match) = 0 (no errors occurred)
• c4 (bcb4: Backoff arm) = 0 (no backoffs occurred)

Plugging those counters into rustc's expressions gives:

• Fatal arm, Error::Fatal => return Err(err) (bcb3): $$\text{count} = c_0 = \mathbf{17}$$ So a fatal error path that executed 0 times gets reported as covered 17 times.
• Retry arm (bcb6): $$\text{count} = c_2 - (c_0 + c_4) = 0 - (17 + 0) = \mathbf{-17}$$

The obvious thing to try was adding the missing .reverse() in counters.rs:69, so that bcb3 (return Err) gets a physical counter instead.

I built a stage1 rustc to test that exact one-liner. It broke function coverage in the opposite direction.

In the CFG diagram, if sink and bcb0 are connected on one side, and the loop (bcb1..bcb7) is on the other side, there are only two edges crossing the cut between them: bcb0 (entry) going in, and bcb3 (return) coming out.

In any spanning tree of a connected graph, at least one edge across a 2-edge cut has to be a tree edge (an expression). For a long-running service loop, that means one of the two always ends up wrong:

• Without .reverse(), bcb3 (return) is the expression (= c(bcb0) = 17), so the never-executed return lies and says 17.
• With .reverse(), bcb3 (return) gets the physical counter (= 0), which forces bcb0 (entry) to become the expression (= c(bcb3) = 0). Now llvm-cov reports that run_worker(), the hottest function in the binary, was executed 0 times (FNDA:0).

Once I knew what to look for, it turned out rustc's own test suite already showed this regression. When PR #135481 landed, it re-blessed tests/coverage/panic_unwind.coverage, where main() loops from countdown = 10 down to 1 and panics on the last iteration before reaching Ok(()) at the end of main:

    LL|      1|fn main() -> Result<(), u8> {
    LL|      1|    let mut countdown = 10;
-   LL|     11|    while countdown > 0 {
-   LL|     11|        if countdown == 1 {
+   LL|     10|    while countdown > 0 {
+   LL|      9|        if countdown == 1 {
    LL|      1|            might_panic(true);
-   LL|     10|        } else if countdown < 5 {
+   LL|      8|        } else if countdown < 5 {
    LL|      3|            might_panic(false);
-   LL|      6|        }
-   LL|     10|        countdown -= 1;
+   LL|      5|        }
+   LL|      9|        countdown -= 1;
    LL|       |    }
-   LL|      0|    Ok(())
-   LL|      0|}
+   LL|      1|    Ok(())
+   LL|      1|}

At the bottom of that diff, Ok(()) at the end of main() changed from 0 (the truth, since main panicked) to 1 (aliased to c0 at function entry). And inside the loop, else if countdown < 5 was given the expression c1 - (c0 + c2). The only reason panic_unwind.rs didn't underflow in rustc's test suite was that countdown started at 10 (10 - 2 = 8). Change let mut countdown = 10; to let mut countdown = 1;, and panic_unwind.rs immediately underflows to $-1$.

How LLVM made it worse

rustc only got us to $-17$. Turning $-17$ into 18446744073709551599 happens in llvm-cov.

In llvm/lib/ProfileData/Coverage/CoverageMapping.cpp, CounterMappingContext::evaluate evaluates counter expressions using signed 64-bit integers (int64_t):

int64_t LHS = Current.LHS;
int64_t RHS = LastPoppedValue;
LastPoppedValue =
    E.Kind == CounterExpression::Subtract ? LHS - RHS : LHS + RHS;

So Ctx.evaluate(C) returns Expected<int64_t>(-17).

Right below that, CountedRegionEmitter::evaluateAndCacheCounter caches the result into CounterValues, which is declared as std::map<Counter, uint64_t>:

auto ValueOrErr = Ctx.evaluate(C);
if (!ValueOrErr)
  return ValueOrErr.takeError();
CounterValues[C] = *ValueOrErr; //int64_t(-17) -> uint64_t(18446744073709551599)!

Nothing clamps it to zero or checks for underflow. C++ silently converts the signed value to unsigned, which wraps $-17$ into 18446744073709551599 (UINT64_MAX - 16).

From there, llvm-cov show sees a 20-digit unsigned number and helpfully formats it with an exa-suffix as 18.4E, while llvm-cov export --format=lcov dumps raw DA:14,18446744073709551599 lines that blow up downstream parsers.

What's next

The real fix has to break the false equivalence flow(START_BCB) == sum(flow(exits)) whenever a function can be caught mid-execution:

1. In rustc, decouple START_BCB and exit nodes across the synthetic sink edge so function entry and function exits are never derived from each other (at the cost of at most +1 physical counter in multi-block functions), and fix the inverted is_out_summable sort comparator in counters.rs.
2. In llvm-cov, clamp negative int64_t expression results to 0 before casting to uint64_t in CoverageMapping.cpp, because even valid region-based counters can transiently go negative if a process calls exit(0) or longjmp mid-block.
3. And never let an agent silently clamp away a uint64_t underflow. Sometimes that "harmless parser glitch" is actually a compiler bug nobody has found yet ;)

Until next time, happy debugging! 🦀