Optimizer-Friendly Instrumentation for Event Quantification with PRUE Algorithm

To count how often things happen inside a running program — for profiling, fuzzing coverage, or security checks — you insert extra counting instructions, but those instructions write to shared memory, which blocks the compiler's optimizer and makes the program slow; this paper (HKUST — Hao Ling, Yiyuan Guo, Charles Zhang) presents Zircon, which counts into cheap local variables that the optimizer can freely reason about and only occasionally writes the totals out to shared counters, using a static analysis called PRUE to prune the write-outs that are redundant, running up to 149 percent faster than prior tools without losing accuracy.

The argument in one glance

Problem

Counting runtime events is useful but the counters slow everything down

Event quantification means measuring how often things happen while a program runs — how many times a branch is taken, an edge is covered, a function is called. This frequency information is the backbone of many tools: profilers that guide optimization, coverage-guided fuzzers that count which code paths a test exercises, and security and reliability checks that watch for anomalous event rates. The usual way to collect it is instrumentation: the compiler inserts extra instructions into the program that increment counters as events occur. The problem is that this instrumentation is expensive — it adds significant runtime overhead — and, worse, it resists being made cheaper by the compiler. Modern compilers rely on aggressive optimizations (moving computations out of loops, keeping values in registers, deleting redundant work) to make code fast, but those optimizations can barely touch the instrumentation. The reason is side effects: the counting instructions typically update global counters in shared memory, and a write to shared memory is something the optimizer must treat conservatively, because other code — or other threads, or an external observer reading the counts — might depend on exactly when and how it happens. So the optimizer cannot hoist, merge, or eliminate these updates the way it would ordinary arithmetic, and the instrumented program stays slow. The challenge is building instrumentation the optimizer can actually help.
What people did

Count into local variables the optimizer can freely manipulate

There is an intuitive fix: instead of incrementing global counters, count into local counters with transparent lifetimes and scopes. Local variables are things the optimizer fully controls — it can prove nothing outside the current scope observes them, so it can keep them in registers, combine updates, and move them around freely. Optimizations are far more likely to succeed on instructions that manipulate local variables than on ones that touch global memory. So counting locally, at least within a function or loop, should let the optimizer do its job on the instrumentation the way it does on ordinary code.
Why it fell short

Local counters are invisible, and syncing them back reintroduces the problem

Local counters alone do not solve the problem, because the whole point of event quantification is that the counts are observable to external users of the data — a fuzzer, a profiler, a monitoring tool reads them. A local counter that lives and dies inside a scope is invisible to those users, so it is useless on its own. Global counters are therefore still necessary as the observable home of the totals, which means the local counts must be written out to the global counters at some point. And here the difficulty returns: those write-out updates — moving a local total into a global counter — are themselves side-effecting operations on shared memory, exactly the kind that block optimization. So the naive local-counter idea just relocates the problem to the moment of synchronization. Worse, separating the counting from the write-out introduces a new inefficiency: to keep the local counters correct across the program's control flow, updates get executed even along paths where no event actually occurred, so the instrumentation now does redundant work. The real question the design must answer is the update decision problem: when, and along which paths, should the global counters be updated from the locals, so that the counts stay correct and observable while as few side-effecting, optimization-blocking, redundant updates as possible are executed?
This paper's idea

Separate counting from write-out, then statically prune redundant updates

Zircon is presented as the first optimizer-friendly instrumentation for event quantification, and it works in two moves. First, it uses local counters to separate the event occurrence from the quantification: the actual counting happens in local variables, and the side-effecting instructions that update the observable global counters are moved outside the scope where the optimizer applies. This lets the optimizer work freely on the hot code, because the instructions it sees there manipulate local variables rather than global memory — and the compiler's existing optimizations then improve the instrumented code automatically. Second, it confronts the redundancy this separation creates. Because the local counters must be maintained across control flow, the write-out updates would still run even when no event occurred, wasting work. The paper's core algorithm, Partially Redundant Update Elimination (PRUE), addresses this update decision problem: it transforms the program and, using static analysis, prunes away the paths that carry redundant updates, so a global counter is updated only where it actually needs to be. The result is instrumentation that harnesses the compiler instead of fighting it. Evaluated on SPEC CPU 2017, Zircon is up to 149 percent faster than state-of-the-art tools including SanCov and Nisse, and unlike prior work it does not trade accuracy for speed — it keeps exact counts while gaining automatic performance from the optimizer.

Why this problem is worth solving

Counting events cheaply is a shared prerequisite for a whole family of tools, so overhead in instrumentation is a tax paid across profiling, fuzzing, and security.

Frequency information about runtime events underpins much of how we make software fast, secure, and reliable. Profile-guided optimization needs accurate counts of how often branches and functions execute to decide what to optimize. Coverage-guided fuzzing — one of the most effective bug-finding techniques in use — instruments programs to count which edges each input exercises, running the target enormous numbers of times, so every bit of per-run overhead multiplies into slower fuzzing and fewer bugs found. Runtime security and reliability monitors watch event rates to catch anomalies. In all of these, the instrumentation overhead is not a side detail; it directly determines how much you can measure and how fast. If counting an event is expensive, you either measure less or run slower. That is why making event quantification cheap is valuable in a broad, reusable way: a technique that cuts the overhead helps every tool built on top of counting. And because the overhead comes specifically from the optimizer being unable to help, the payoff of making instrumentation optimizer-friendly is large — it turns the compiler from a bystander into an ally on exactly the code that was previously stuck being slow.

The crux is a subtle tension between observability and optimizability, and the insight is that you can localize the counting while still exposing the totals.

The reason efficient instrumentation is hard is a genuine conflict. For the optimizer to help, the counting instructions must look like ordinary local computation — values it owns, whose exact timing no one observes — so it can freely rearrange and eliminate them. But for the counts to be useful, they must be observable — living in global state that external tools can read — which forces exactly the shared-memory side effects the optimizer must respect. You seem to need the counters to be both invisible (to the optimizer’s conservatism) and visible (to the data’s consumers) at once. Zircon’s resolution is to split the single act of counting into two: count in the fast, invisible local realm where the optimizer thrives, and only cross into the slow, visible global realm at chosen synchronization points, pushed out of the hot scope. That reframes the whole problem into a decision — where to place the crossings — which is the update decision problem. And once it is a decision, it can be optimized: PRUE’s static analysis proves which of those crossings are redundant and removes them. The elegance is that the design does not compromise accuracy to get speed; it separates the concerns so that both the optimizer’s freedom and the data’s observability are preserved, and then prunes the leftover cost.

What people did before, and where it broke

Instrument with global counters directly. Insert instructions that increment shared global counters as events occur. Where it broke. The shared-memory side effects force the optimizer to be conservative, so it can barely improve the instrumentation, and overhead stays high.
Existing efficient instrumentation (SanCov, Nisse). State-of-the-art tools reduce instrumentation cost with their own techniques. Where it broke. They still leave overhead on the table, and some approaches to efficiency compromise accuracy — accepting approximate counts to go faster.
Count into local variables only. Use local counters with clear lifetimes so the optimizer can freely manipulate them. Where it broke. Local counters are invisible to the external tools that consume the quantification data, so on their own they are useless — the totals must reach observable global state.
Write locals back to globals naively. Keep local counters but synchronize them to global counters as needed. Where it broke. The write-out updates are themselves side-effecting global-memory operations that block optimization, and maintaining locals across control flow makes some updates execute even when no event occurred — redundant work.
The gap. No approach both moved the side-effecting updates out of the optimizer’s way and eliminated the redundant updates that separation creates, so none delivered optimizer-friendly instrumentation without sacrificing accuracy.

How Zircon works

From optimization-blocking global counters to local counting plus pruned write-outs

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Keep the instrumentation from disturbing the program the optimizer sees. Zircon’s first principle is to count where it is cheap and invisible — in local variables — and push the side-effecting, observable work out of the hot scope, so the instrumentation barely disturbs the code the optimizer is trying to improve. Designing instrumentation to observe a program while minimally perturbing its normal execution and the machinery around it is the same goal the work on flexible, non-intrusive dynamic instrumentation for WebAssembly (non-intrusive instrumentation) covered elsewhere on this site pursues, keeping the added observation from getting in the program’s way. Zircon achieves non-intrusiveness specifically toward the compiler’s optimizer, by relocating the intrusive side effects out of the scope where optimization happens.

Turn the leftover cost into redundancy the analysis can remove. Once counting and write-out are separated, the remaining inefficiency is redundant updates — instructions that run even when no event occurred — and Zircon’s PRUE proves, statically, which updates are partially redundant and prunes those paths away. Treating wasted work as redundancy that a static analysis can identify and eliminate, rather than accepting it as inherent, is the same lens the work on finding missed optimizations through the lens of dead-code elimination (dead-code elimination) covered elsewhere on this site applies, using the absence of a needed effect to justify removing the code that produces it. PRUE is a specialized redundancy elimination aimed exactly at the counter-update instructions that separation leaves behind.

Make the frequency data cheap so the tools that consume it run faster. The purpose of all this is efficient event quantification — accurate counts produced with minimal overhead — because those counts feed profilers, fuzzers, and optimizers that act on them. Producing accurate execution-frequency information at low cost so that downstream optimization can use it is the same enterprise the work on a profile-guided relinking optimizer for warehouse-scale applications (Propeller) covered elsewhere on this site is built around, where the value of the counts depends on collecting them cheaply. Zircon strengthens that foundation by making the collection itself optimizer-friendly, so the instrumentation stops being the bottleneck.

Following an event count through Zircon

Counting an event without blocking the optimizer

An illustration, drawn from the paper's abstract, of how Zircon separates counting from write-out and prunes redundant updates. Internal mechanism details are the paper's.

Step 1 of 5

An event happens inside a hot loop

The program executes a branch or edge that should be counted, inside a frequently-run region. Conventionally this would increment a global counter in shared memory right here, blocking optimization of the loop.

The shared-memory write is the side effect the optimizer must respect.

Why it works

Local counters restore the optimizer’s freedom. Global-counter writes force conservative, un-optimizable code → but counting into locals the optimizer fully controls → so ordinary optimizations (registers, merging, motion) apply to the instrumentation.
Moving write-outs out of scope keeps the hot path clean. The observable global updates are the side effects that block optimization → but relocating them outside the optimized scope → so the frequently-run code the optimizer cares about stays free of them.
Separation is what creates the redundancy PRUE targets. Splitting counting from write-out makes some updates run without an event → but recognizing these as partially redundant updates → so a dedicated analysis has a well-defined thing to eliminate.
Static analysis prunes updates without losing counts. Redundant write-outs waste work but cannot simply be deleted blindly → but PRUE proves which paths’ updates are unnecessary → so it removes them while keeping the global counts exact.
Accuracy is preserved, so speed is a pure gain. Prior efficiency sometimes came from approximating the counts → but Zircon separates concerns instead of dropping precision → so it gets automatic compiler speedups with no accuracy compromise.

What it costs (trade-offs and scope)

It requires compiler-level program transformation and static analysis. Zircon restructures counting into locals, relocates write-outs, and runs the PRUE analysis to prune updates; this is machinery built into the instrumentation and compilation pipeline, not a runtime-only tweak.
Local counters add state and lifetime management. Introducing local counters with controlled lifetimes and scopes is what enables the optimization, but managing them across control flow is exactly what creates the redundant updates PRUE must then clean up.
PRUE removes partial redundancy, not all overhead. The analysis prunes paths with redundant updates, but the remaining necessary write-outs to global counters still carry their inherent cost; the win is eliminating the avoidable part.
Gains depend on how much the optimizer can now do. The speedup comes from letting existing optimizations apply to the instrumentation, so the benefit is largest where the counting sits in hot, optimizable code and smaller where it does not.
Reported figures are on specific benchmarks and baselines. The up-to-149-percent speedup is measured on SPEC CPU 2017 against SanCov and Nisse; the exact improvement depends on the programs, the events being quantified, and the compiler configuration.

The comparison

Instrumenting a program to quantify runtime events

Property	Global counters (typical)	Local counters only	Zircon (with PRUE)
Where counting happens
Optimizer can help
Counts observable to tools
Redundant updates
Accuracy vs speed

A comparison of ways to instrument a program for event quantification. Global counters are observable but block optimization; local-only counters optimize well but are invisible to the tools that need the data. Zircon counts into local counters the optimizer can freely manipulate, moves the observable write-outs outside the optimized scope, and uses the PRUE static analysis to prune redundant updates — so the compiler improves the instrumentation automatically without sacrificing accuracy, running up to 149 percent faster than SanCov and Nisse on SPEC CPU 2017. Exact figures should be read from the paper.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is based on the paper’s abstract and public metadata, not its full text, which was not available at the time of writing. The high-level claims are the authors’: Zircon is presented as the first optimizer-friendly instrumentation for event quantification. It uses local counters with transparent lifetimes and scopes to separate event occurrence from quantification, moving the side-effecting instructions that update observable global counters outside the scope where compiler optimizers apply, so ordinary optimizations can improve the instrumented code. This separation introduces redundant updates (executed even when no event occurred), and the paper’s core algorithm, Partially Redundant Update Elimination (PRUE), transforms the program and prunes paths with redundant updates based on static analysis, addressing the “update decision problem” of when to update the global counters from the locals. The reported results are from an evaluation on SPEC CPU 2017: Zircon is up to 149 percent faster than state-of-the-art work including SanCov and Nisse, without compromising accuracy for efficiency. The background above on instrumentation, global-versus-local counters, compiler side effects, and coverage-guided fuzzing and profiling as consumers of event counts is standard context provided to make the approach intuitive. The Flow, the step-by-step walkthrough, and the “Why it works” reasoning are illustrations built from the abstract’s description, not detailed accounts from the paper — how PRUE’s static analysis is formulated, exactly how and where write-outs are placed, and the full evaluation should be read from the paper. Do not treat specific procedural details here as established beyond what the abstract states.

Background

Why observing a program without disturbing it is a recurring systems problem

It helps to see Zircon within a broad and recurring tension in systems: to make software fast, secure, and reliable we constantly need to observe it — count its events, check its memory, trace its behavior — and yet every observation risks disturbing the very thing being observed, most often by adding overhead. Instrumentation is the classic instance, and its central difficulty is that the added bookkeeping fights the machinery that would otherwise make the program fast, whether that machinery is the CPU pipeline, the memory system, or, as here, the compiler’s optimizer. Much of the progress in this area comes from cleverly restructuring the observation so it interferes as little as possible with the fast path — batching, moving work off the hot path, and eliminating the parts that turn out to be unnecessary. Zircon is a clean instance aimed squarely at the optimizer: it keeps the hot code optimizable by counting locally and pushing the observable side effects out of scope, then statically prunes the redundant remainder. This drive to slash the overhead of pervasive program instrumentation so that measurement stops being prohibitively expensive is the same terrain the work on efficient memory sanitization with segment folding (GiantSan) covered elsewhere on this site occupies, making a heavyweight checking mechanism cheap enough to use widely. Zircon’s particular contribution is to show that, for event quantification, separating counting from observable write-out and eliminating the resulting redundant updates lets the compiler’s own optimizations do the work — delivering large speedups while keeping the counts exact.

If you remember only three things

1. Event quantification — counting how often runtime events occur — powers profilers, coverage-guided fuzzers, and security and reliability monitors, and it is collected by instrumentation that inserts counting instructions into a program. The trouble is that these counters normally live in shared global memory, and writes to shared memory are side effects the compiler's optimizer must treat conservatively: it cannot hoist, merge, or delete them, so the instrumented program stays slow. In other words, the instrumentation can barely benefit from the very optimizations that make ordinary code fast. The intuitive fix of counting into local variables (which the optimizer can freely manipulate) fails on its own, because local counters are invisible to the external tools that need the counts.
2. Zircon, presented as the first optimizer-friendly instrumentation for event quantification, resolves this by separating counting from observability. It counts events into local counters with transparent lifetimes and scopes — which the optimizer fully controls — and moves the side-effecting instructions that write totals out to the observable global counters outside the scope where optimization applies, so the hot code the optimizer cares about stays free of optimization-blocking side effects. But maintaining the local counters across control flow makes some write-out updates run even when no event occurred (redundant work), so Zircon's core algorithm, Partially Redundant Update Elimination (PRUE), transforms the program and uses static analysis to prune the paths carrying those redundant updates — solving the update decision problem of when the globals must actually change.
3. The payoff is instrumentation that harnesses the compiler instead of fighting it: on SPEC CPU 2017, Zircon runs up to 149 percent faster than state-of-the-art tools including SanCov and Nisse, and crucially it does not trade accuracy for speed — the counts stay exact while the optimizer delivers automatic performance gains. The trade-offs and scope: Zircon requires compiler-level transformation and the PRUE static analysis, introduces local-counter state whose lifetime management is what creates the redundancy PRUE must clean up, removes the avoidable redundancy rather than all overhead, and yields its largest gains where counting sits in hot, optimizable code. This explainer is based on the paper's abstract; the formulation of PRUE and the full evaluation should be confirmed in the paper.

Check yourself

Check your understanding

1. Why does normal event-quantification instrumentation resist compiler optimization?
2. Why is simply switching to local counters not enough by itself?
3. What are Zircon's two key moves, and what does PRUE do?
4. What does Zircon achieve, and what are the limits of the approach?

Sources

The paper is “Optimizer-Friendly Instrumentation for Event Quantification with PRUE Algorithm” by Hao Ling, Yiyuan Guo, and Charles Zhang (The Hong Kong University of Science and Technology), published at ASPLOS 2026, DOI 10.1145/3779212.3790196.

This explainer is written from the paper’s abstract and public metadata; the full text was not available at the time of writing, so the page is marked a draft. As reported there, the paper presents Zircon, described as the first optimizer-friendly instrumentation for event quantification. Zircon uses local counters with transparent lifetimes and scopes to separate event occurrence from quantification, moving the side-effecting instructions that update observable global counters outside the scope where compiler optimizers apply. Because this separation introduces redundant updates, the paper’s core algorithm, Partially Redundant Update Elimination (PRUE), transforms the program and prunes paths with redundant updates using static analysis, solving the update decision problem of when to update the global counters from the locals. On SPEC CPU 2017, Zircon is reported up to 149 percent faster than state-of-the-art work including SanCov and Nisse, without compromising accuracy. Background on instrumentation, global-versus-local counters, compiler side effects, and the tools that consume event counts is standard context. The specific numbers are the paper’s own; the formulation of PRUE and the full evaluation should be confirmed in the paper.