---
title: "Can a formally-verified C compiler be as performant as gcc -O2?"
slug: can-a-formally-verified-c-compiler-be-as-performant-as-gcc-o2
url: https://listedarticles.com/articles/can-a-formally-verified-c-compiler-be-as-performant-as-gcc-o2
canonical_url: https://ut-infraai.github.io/2026/11/13/trying-to-make-compcert-as-fast-as-gcc-o2/
content_type: research
language: en
published_at: 2026-11-13T06:00:00.000Z
updated_at: 2026-11-17T13:53:19.707Z
author: "Aananth V"
authored_by: human
publisher: "InfraAI Research Blog"
publisher_url: https://ut-infraai.github.io/
topics: ["compilers", "formal-verification", "research"]
license: all-rights-reserved
word_count: 5342
reading_minutes: 23
citation: "Aananth V, InfraAI Research Blog. \"Can a formally-verified C compiler be as performant as gcc -O2?.\" 13 Nov 2026. https://ut-infraai.github.io/2026/11/13/trying-to-make-compcert-as-fast-as-gcc-o2/ (all-rights-reserved)"
# The full text follows. The web page shows an extract and sends readers
# to the source above; quote the citation and link the canonical URL.
---

# Can a formally-verified C compiler be as performant as gcc -O2?

> Aananth V describes writing about 15,000 lines of Rocq, with help from coding agents, to add verified optimization passes to the CompCert C compiler in an attempt to close its 28% performance gap with gcc -O2, and what still blocks parity.

What happens when you write 15,000 lines of Rocq code trying to close the 28% performance gap between a formally verified compiler and the industry-standard GCC.

Aananth V
November 13, 2026

![A C program passes through CompCert to become x86-64 assembly, with machine-checked proofs.](https://ut-infraai.github.io/assets/posts/compcert-gcc-o2/cover.png)

CompCert ([GitHub](https://github.com/AbsInt/CompCert)) is a *formally verified* C compiler written in Rocq and OCaml. Like `gcc` or `clang`, it compiles C to assembly and optimizes the program to be faster along the way; the difference is that CompCert *proves* that those optimizations preserve the program’s behavior under its formal semantics. You feed a C program into the front end, and it transforms the program through a sequence of optimizations and intermediate representations all the way down to x86-64 assembly code. Each of these transformations in the verified pipeline, also called passes in compiler jargon, is implemented in Rocq or checked by a verified validator, and proved to preserve the program’s behavior under CompCert’s *formal semantics* of C and x86-64: precise mathematical definitions of what a C program means and what each x86-64 instruction does. At the end, a machine-checked theorem ensures that the generated assembly preserves an allowed behavior of the source C program, provided the source has no undefined behavior under these semantics.[1](#fn:scope) This makes CompCert particularly suitable for safety-critical software where correctness is just as important as performance, since mainstream compilers such as GCC and LLVM have been shown to silently generate wrong code.[2](#fn:csmith)[3](#fn:emi)[4](#fn:sun)

However, formal verification currently comes with a steep runtime tax. For example, the CompCert benchmarks, a suite of test programs that ships with CompCert, run roughly 28% slower than when compiled by `gcc -O2`, and the PolyBench loop-nest benchmarks run about 55% slower.[5](#fn:bench)

One common theory for this gap is CompCert’s strict and fairly simple semantic models of C and x86-64, which rule out several assumptions that GCC uses to optimize:

- **Signed integer overflow.** The C standard leaves it undefined, so GCC assumes it never happens; for example, it can treat `i + 1 > i` as always true and simplify loop counters. CompCert’s semantics defines overflow to wrap around, so it can’t make that assumption.
- **Type-based aliasing.** C’s aliasing rules let GCC assume that an `int *` and a `float *` never point to the same memory, so it can keep a value in a register across a store through the other pointer. CompCert’s memory model doesn’t include these rules.
- **Fused multiply-add.** GCC may combine `a * b + c` into a single FMA instruction, which is faster and rounds only once. CompCert rounds every floating-point operation separately.
- **SIMD.** GCC vectorizes loops to process several elements per instruction. CompCert’s x86-64 model has no vector instructions.

I wanted to know whether these semantic restrictions actually explain why CompCert is slow, or whether CompCert is simply missing many standard compiler optimizations and backend code generation polish. And if the gap is mostly missing passes,

1. Is proof generation the bottleneck? (CompCert was first released in 2008…)
2. Could AI agents find, implement, and *prove* those transformations in Rocq without any human intervention? (Recent progress in math suggests yes…)

All of our passes, proofs, and benchmarking scripts are available at [github.com/UT-InfraAI/CompCert](https://github.com/UT-InfraAI/CompCert/tree/v3.18).

---

## 1. Testing the Folk Theory: Is It the Semantic Model?

Before touching CompCert, we tested the semantic-model hypothesis on GCC. Every major restriction in CompCert’s semantics has a matching flag in GCC that disables the corresponding optimizations:

| Restriction | In CompCert | GCC flag |
| --- | --- | --- |
| Signed integer overflow | Defined to wrap around | `-fwrapv` |
| Type-based aliasing | Rules not in the memory model | `-fno-strict-aliasing` |
| Fused multiply-add | Every operation rounded separately | `-ffp-contract=off` |
| SIMD | No vector instructions in the x86-64 model | `-fno-tree-vectorize` |

If CompCert’s formal semantics were the main bottleneck, disabling these four features in GCC would wipe out most of GCC’s lead.

However, this is not what we see. Even after restricting these flags in `gcc -O2`, CompCert is still 26% slower on the CompCert benchmarks and 54% slower on the PolyBench suite. This means that the semantic models are not the main bottleneck. Most of the gap comes from optimizations that CompCert’s rules already allow, but that CompCert never performs.

Figure 1: Geometric Mean Runtime Across Compiler Configurations

Normalized to CompCert = 1.000 (lower is faster). Interleaved round-robin timing.

---

## 2. Assembly Surgery: So where does the time actually go?

We first needed to know which missing transformations actually contribute to the performance gap on real hardware. The idea is simple: we take CompCert’s `.s` assembly output for a slow benchmark and manually edit it to apply one missing optimization at a time. Then we re-assemble the binary, check its output against the reference results, and time it. Once we know which optimizations actually help, we can prove and implement them in CompCert. Thanks to coding agents, this was not as painful as it sounds.

The following are some of the missing optimizations we found this way:

### Loop-Carried Reloads in `spectral`

One of the CompCert benchmarks, [`spectral`](https://github.com/AbsInt/CompCert-small-tests/blob/main/c/spectral.c), spends most of its time in an inner loop that accumulates products into an array element `Au[i]`:

```
/* spectral.c: inner product loop */
for (j = 0; j < n; j++)
  Au[i] += u[j] / (double)((i + j) * (i + j + 1) / 2 + i + 1);
```

Normally, CompCert’s common subexpression elimination (CSE) pass ([`backend/CSE.v`](https://github.com/UT-InfraAI/CompCert/blob/v3.18/backend/CSE.v)) would avoid reloading a value the program already has. But CSE only remembers values within a stretch of code that has a single way in, and the top of a loop has two: from the code before the loop, and from the end of the previous iteration. So CSE forgets everything it knew at the start of every iteration. As a result, CompCert reloads `Au[i]` from memory, adds to it, and stores it back on every single inner-loop iteration:

```
# CompCert (126 ms): reload and store on every iteration; excerpt
.L102:  movsd   0(%rdx,%rax,8), %xmm1   # reload Au[i] from memory
        mulsd   %xmm4, %xmm0            # multiply matrix term by u[j]
        addsd   %xmm0, %xmm1            # add product to accumulator
        movsd   %xmm1, 0(%rdx,%rax,8)   # store Au[i] back to memory
        # ... remaining loop arithmetic and control omitted ...
```

Simply using a temporary register to accumulate the sum across loop iterations cuts `spectral` runtime nearly in half, from 126 ms down to 73 ms:

```
# Hand-edited (73 ms, -42%): Au[i] kept in %xmm1 across iterations
.L103:  mulsd   %xmm4, %xmm0            # multiply matrix term by u[j]
        addsd   %xmm0, %xmm1            # accumulate directly into %xmm1
        jl      .L103                   # loop back with %xmm1 live (no reload or store)
        movsd   %xmm1, 0(%rdx,%r9,8)    # store Au[i] once after the loop finishes
```

This transformation could be realized with two standard loop optimizations that GCC and LLVM already perform but CompCert lacks: *loop-invariant code motion* (LICM) and *loop rotation*. Together, they load `Au[i]` once before the loop and store it once after it.

### Over-Conservative Stack Aliasing in `sha3`

Another CompCert benchmark, [`sha3`](https://github.com/AbsInt/CompCert-small-tests/blob/main/c/sha3.c), spends most of its time in `keccakf`, the function that scrambles SHA-3’s internal state over 24 rounds. It writes temporary values into a local array `bc[5]` on the stack:

```
/* sha3.c: temporary slice buffer in keccakf */
uint64_t bc[5];
for (i = 0; i < 5; i++)
  bc[i] = st[i] ^ st[i + 5] ^ st[i + 10] ^ st[i + 15] ^ st[i + 20];
```

By the end of each round, 34 stores to `bc[]` are dead because those slots are overwritten before they are ever read again.

CompCert’s dead-code elimination pass ([`backend/Deadcode.v`](https://github.com/UT-InfraAI/CompCert/blob/v3.18/backend/Deadcode.v)) should remove them, but it didn’t. `keccakf` reads its state through a pointer `st` passed in by the caller. CompCert’s analysis ([`backend/NeedDomain.v`](https://github.com/UT-InfraAI/CompCert/blob/v3.18/backend/NeedDomain.v)) already knows that `st` cannot point into `keccakf`’s own stack frame, yet it treated every load through `st` as if it might read anything on that stack frame, including `bc`. So every store to `bc` looked like it might be needed later:

```
# CompCert: stores to bc[] that are never read
movq    %rax, 0(%rsp)           # store bc[0] to the stack
movq    %rbx, 8(%rsp)           # store bc[1] to the stack
movq    %rcx, 16(%rsp)          # store bc[2] to the stack
# ... 31 more like these per round; each is overwritten before it is read ...
# CompCert keeps them all: it assumes later loads through st might read them
```

Removing these dead stores eliminated 80% of the stack stores per round and cut `sha3` runtime by 18%.

### Redundant Zero-Extensions and False Register Dependencies

When we inspected [`aes`](https://github.com/AbsInt/CompCert-small-tests/blob/main/c/aes.c) and [`nbody`](https://github.com/AbsInt/CompCert-small-tests/blob/main/c/nbody.c) we found two issues in CompCert’s x86-64 backend model and code emission.

First, on x86-64, writing a 32-bit register automatically zeroes the upper 32 bits of the 64-bit register. CompCert’s instruction selector did not model this hardware rule for shifts and bitwise masks. When [`aes`](https://github.com/AbsInt/CompCert-small-tests/blob/main/c/aes.c) indexed a lookup table using `(u64)(x >> 24)`, CompCert emitted an explicit zero-extension:

```
# CompCert: redundant movl zero-extension
shrl    $24, %edx               # logical right shift table index by 24 bits
movl    %edx, %edx              # redundant! 32-bit shift already zeroes upper 32 bits
movl    0(%r9,%rdx,4), %r10d    # load 32-bit word from lookup table Te0
```

That added 23 useless instructions to every encryption round. Just removing these instructions cut `aes` runtime from 85.2 ms down to 77.6 ms (a 9% runtime reduction). Along with LICM, we were able to reach ~67 ms (about a 20% runtime reduction from the ~84 ms baseline). This was slightly faster than `gcc -O2`.

Second, we found a suboptimal lowering in CompCert’s emission of scalar SSE instructions like `cvtsi2sd` and `sqrtsd`. While these instructions write only the lower 64 bits, the hardware considers the full 128 bits of the `%xmm` register when executing and must keep the upper bits intact. These upper bits are never used in scalar code (no SIMD). This creates a false read-after-write dependency where the CPU waits for the previous write to that register to complete, stalling the instruction pipeline.

Both GCC and Clang fix this by emitting `xorpd %xmm, %xmm` first (see LLVM’s [`BreakFalseDeps.cpp`](https://github.com/llvm/llvm-project/blob/main/llvm/lib/CodeGen/BreakFalseDeps.cpp) and this [Stack Overflow breakdown](https://stackoverflow.com/questions/60688348/why-does-adding-an-xorps-instruction-make-this-function-using-cvtsi2ss-and-addss) for more details). Modern x86 processors recognize xor-with-self as a zero-execution-cycle instruction in the register renamer and break the false dependency at no additional cost:

```
# CompCert (184 ms): false dependency on old %xmm3 contents
cvtsi2sd %r11d, %xmm3           # writes low 64 bits, stalls waiting for old %xmm3 pipeline
sqrtsd  %xmm3, %xmm3            # computes sqrt with false dependency chain intact

# Hand-edited (112 ms, -40%): zero-cost xorpd breaks the dependency chain
xorpd   %xmm3, %xmm3            # renamer allocates fresh register at zero latency
cvtsi2sd %r11d, %xmm3           # writes low 64 bits immediately with no pipeline stall
sqrtsd  %xmm3, %xmm3            # computes sqrt at full hardware throughput
```

This results in a 40% speedup for [`nbody`](https://github.com/AbsInt/CompCert-small-tests/blob/main/c/nbody.c) when `sqrt` is compiled to CompCert’s `__builtin_sqrt`. (With the false dependency, that version was even slower than stock CompCert’s 132 ms libm call.)

---

## 3. How CompCert Proves Compiler Passes

Before asking AI agents to write new transformations, let’s try to understand how CompCert proves that the transformations are correct. Every pass in CompCert comes with a mathematical proof written in Rocq that proves that the transformed code behaves identically to the original program. There are two fundamentally different approaches that CompCert uses, and each comes with distinct engineering trade-offs.

### Approach 1: Direct Verified Dataflow

In direct verification, the optimization passes are directly written in Rocq’s purely functional language (Gallina) and extracted to OCaml to build the compiler binary. A pass proves a global simulation theorem: for every program \(P\), executing the transformed program \(P'\) matches the exact observable behavior of \(P\). Since the optimization pass is the formal object under proof, the algorithm and the proof are fused together. CompCert uses this design for its core passes like constant propagation (`Constprop.v`), common subexpression elimination (`CSE.v`), and dead code elimination (`Deadcode.v`).

Most passes in this category are dataflow analyses. To optimize code, the compiler tracks what facts are true at every point in the function:

1. **Define what the compiler knows**: You define a set of facts about variables and memory. A variable might hold a known number (`r1 = 42`) or an unknown runtime value. These facts propagate through the control flow graph of the function.
2. **Update facts across each instruction**: You write a function that updates these facts for every operation. An assignment like `r1 = 5` adds a known constant to the current state. A pointer store like `*p = r3` updates the state and wipes out any cached load that might share memory with `p`.
3. **Loop until facts stop changing**: When two blocks merge after an `if-else` or when iterating over a loop, the compiler combines their facts. For example, if one branch says `r1 = 42` and the other says `r1 = 10`, the compiler drops the specific number and marks `r1` as unknown. CompCert runs a solver (Kildall’s algorithm) that walks the control flow graph repeatedly until the facts stabilize.

Direct verification works well for textbook passes with clean, predictable rules. However, many optimizations rely on complex heuristics and edge cases. Since the optimization algorithm and its mathematical proof are inseparable, you cannot simply tweak how a pass behaves without also re-proving its underlying theorems. A change to a single analysis rule can invalidate proof chains across hundreds of lines of Rocq. This tight coupling makes iterating on complex optimizations slow.

### Approach 2: Translation Validation

While direct verification proves the transformation algorithm itself, translation validation proves a checker.

Think of it like solving a Sudoku puzzle versus checking one. Writing a solver that never makes a wrong guess is difficult to verify. Writing a checker that inspects a completed grid to confirm numbers 1 through 9 appear without duplicates is much simpler.

Instead of proving that an optimization algorithm produces the correct output for every conceivable input program, translation validation splits the pass into two halves:

1. An **untrusted oracle** (written in standard OCaml) that runs the complicated heuristics and performs the transformation.
2. A **verified validator** (written and proved in Rocq, and then extracted to OCaml) that checks whether the transformation is correct for that specific function.

CompCert already uses this design for passes with complex graph algorithms:

- **Register Allocation (`Allocation.v`):** An untrusted OCaml solver runs iterated register coalescing graph coloring, and a compact Rocq validator checks that every variable’s value is still in the register or stack slot where the allocated code reads it.
- **Basic Block Layout (`Linearize.v`):** An untrusted OCaml heuristic orders blocks to minimize jumps, and a verified Rocq validator checks that all control flow paths remain intact.

This architecture does not weaken the mathematical guarantee. The pass retains its verification guarantee under the same trusted assumptions. You prove a single theorem for the validator once when building the compiler:

\[\begin{gathered}\forall f \, f', \quad \texttt{check\_function}(f, f') = \texttt{OK}\\ \implies f' \text{ preserves the semantics of } f.\end{gathered}\]

When you compile a C program, CompCert runs the validator to guarantee that the transformation is correct for that specific program. Since the validator is mathematically proven never to return `OK` on an invalid rewrite, an untrusted oracle cannot compromise correctness. If the oracle is buggy and suggests a broken transformation, the validator is guaranteed to reject it, and the compiler either falls back to the original code or reports a compilation error. Most of the passes we implemented in this project used this architecture.

---

## 4. Scaling Verified Passes with Coding Agents

Once we identified which passes we needed to implement ([Section 2](#2-assembly-surgery-so-where-does-the-time-actually-go)), we used coding agents to scale the generation and verification of optimization passes. Each optimization was assigned to an agent in an isolated git worktree. Every change made by the agent had to compile cleanly across all target architectures and pass CompCert’s regression test suite. The proofs also had to introduce zero `Admitted` proofs or unapproved `Axiom` declarations.

While Rocq verifies that the transformations themselves are mathematically sound, it cannot verify changes to the hardware model. If an agent incorrectly alters the definition of an x86 instruction, Rocq will still accept the proof, but the compiler will emit broken machine code. Due to this, agents were barred from modifying the **trusted computing base** (C semantics, x86 assembly instructions, and the memory model) without explicit human approval. Unfortunately, the monkey in the loop (me) also approved incorrect changes to the hardware model, but we’ll go over that in [Section 6](#6-the-human-gate-when-proofs-cannot-save-you).

We implemented 5 new passes as well as improvements to existing passes:

| Pass & Intermediate Layer | Transformation | Runtime change |
| --- | --- | --- |
| **[IVwiden](https://github.com/UT-InfraAI/CompCert/blob/v3.18/backend/IVwiden.v)** (RTL, new) | Widens 32-bit IVs to 64 bits; folds affine array offsets | [`gemm`](https://github.com/MatthiasJReisinger/PolyBenchC-4.2.1/blob/master/linear-algebra/blas/gemm/gemm.c) -26%, [`sha1`](https://github.com/AbsInt/CompCert-small-tests/blob/main/c/sha1.c) -13% |
| **[LICM](https://github.com/UT-InfraAI/CompCert/blob/v3.18/backend/LICM.v) + [Looprot](https://github.com/UT-InfraAI/CompCert/blob/v3.18/backend/Looprot.v)** (RTL, new) | Hoists invariant chains (row strides and base addresses) | [`gemm`](https://github.com/MatthiasJReisinger/PolyBenchC-4.2.1/blob/master/linear-algebra/blas/gemm/gemm.c) -28%, [`syrk`](https://github.com/MatthiasJReisinger/PolyBenchC-4.2.1/blob/master/linear-algebra/blas/syrk/syrk.c) -27% |
| **[Loadfwd](https://github.com/UT-InfraAI/CompCert/blob/v3.18/backend/Loadfwd.v)** (RTL, new) | Forwards loads across join points and loop back-edges | [`spectral`](https://github.com/AbsInt/CompCert-small-tests/blob/main/c/spectral.c) -40%, [`3mm`](https://github.com/MatthiasJReisinger/PolyBenchC-4.2.1/blob/master/linear-algebra/kernels/3mm/3mm.c) -47% |
| **[Tailacc](https://github.com/UT-InfraAI/CompCert/blob/v3.18/backend/Tailacc.v) + [Inlining(2)](https://github.com/UT-InfraAI/CompCert/blob/v3.18/backend/Inlining.v)** (RTL) | Rewrites tail recursion to loops; second inlining round | [`integr`](https://github.com/AbsInt/CompCert-small-tests/blob/main/c/integr.c) -54%, [`fib`](https://github.com/AbsInt/CompCert-small-tests/blob/main/c/fib.c) -46% |
| **[CSE](https://github.com/UT-InfraAI/CompCert/blob/v3.18/backend/CSE.v) + [Deadcode](https://github.com/UT-InfraAI/CompCert/blob/v3.18/backend/Deadcode.v)** (RTL, refined) | Disjoint alias analysis; byte-load merging (`Mint64u`) | [`siphash24`](https://github.com/AbsInt/CompCert-small-tests/blob/main/c/siphash24.c) -21%, [`sha3`](https://github.com/AbsInt/CompCert-small-tests/blob/main/c/sha3.c) -18% |
| **[Loadop](https://github.com/UT-InfraAI/CompCert/blob/v3.18/backend/Loadop.v) + [x86 Asm](https://github.com/UT-InfraAI/CompCert/blob/v3.18/x86/Asm.v)** (Linear/Asm) | Fuses loads into memory operands; zero-extending shifts | [`gemm`](https://github.com/MatthiasJReisinger/PolyBenchC-4.2.1/blob/master/linear-algebra/blas/gemm/gemm.c) -9%, [`nsievebits`](https://github.com/AbsInt/CompCert-small-tests/blob/main/c/nsievebits.c) -6% |
| **[Pure libm Builtins](https://github.com/UT-InfraAI/CompCert/blob/v3.18/common/Builtins0.v)** (C/common) | Rewrites `sqrt`/`fabs`; treats 50 math calls as pure for CSE | [`nbody`](https://github.com/AbsInt/CompCert-small-tests/blob/main/c/nbody.c) -17%, [`perlin`](https://github.com/AbsInt/CompCert-small-tests/blob/main/c/perlin.c) -15% |

---

## 5. From Isolated Wins to a Full Pipeline

Writing Rocq proofs was usually straightforward. Using Opus 5.5 in Claude Code, most passes took a few hours and about 10 to 40 compile-and-fix iterations to complete. However, the work didn’t stop there and some real challenges showed up after the proofs were done, with held-out code, with passes interacting with each other, and with real hardware.

### 5.1 Pass Interactions and the Case for Autotuning

Every single pass we implemented made benchmarks faster in isolation. However, merging all of them into a single *static* pipeline revealed subtle interactions across passes. On some programs, combining all optimizations even made them slower than applying a small subset. We used `-fno-*` flags to pinpoint bad interactions, for example:

- In `sha3`, `Loadfwd` inserted shadow copies after memory operations. While `Deadcode` normally eliminated them, `CSE` used those shadow registers as canonical replacements, merging 27 distinct values and increasing register pressure until `keccakf` spilled to the stack.
- In `nsieve`, rotating a loop copied the exit test to the bottom, turning an unconditional jump into a conditional branch. That disqualified the block from CompCert’s latch-placement heuristic in `Linearizeaux.ml`, adding extra jumps on the hot path.

While we were able to resolve both cases by refining local heuristics, this pattern points to a broader reality: no single fixed pass order or heuristic is optimal across all codebases. Pass interactions like these make a strong case for **profile-driven autotuning** and/or **agentic optimization**. This is especially true for *verified compilers* since each optimization pass is guaranteed to be correct (or no-op) — so we only need to worry about the interactions! This is very different from traditional compilers where the wrong order of passes might not only be suboptimal but could also introduce bugs.

### 5.2 Evaluating Beyond the CompCert Benchmarks: PolyBench and Larger Programs

After addressing these interactions, the initial version of our modified compiler, `faster-compcert` (v0), was able to beat `gcc -O1` and achieve `0.871x` the baseline CompCert runtime on the CompCert benchmarks. This closed 60% of the gap to `gcc -O2` (restricted) (`0.794x`).

To test whether these speedups generalized beyond the CompCert benchmarks, we evaluated the compiler on two initially held-out suites: `big` (five larger programs: `raytracer`, `spass`, `arcode`, `lzw`, and `lzss`) and `polybench` (all 30 loop-nest kernels from PolyBench/C 4.2.1). The results were modest and both lagged behind `gcc -O1`.

- On `big`, the compiler reached `0.982x` of baseline (vs `0.949x` for `gcc -O1`).
- On `polybench`, the compiler reached `0.845x` of baseline (vs `0.739x` for `gcc -O1`).[6](#fn:drift)

Inspecting the assembly of [`gemm`](https://github.com/MatthiasJReisinger/PolyBenchC-4.2.1/blob/master/linear-algebra/blas/gemm/gemm.c) (`C[i][j] += alpha * A[i][k] * B[k][j]`) showed immediately why PolyBench was still slow. Our compiler executed 22 instructions in the inner loop, while `gcc -O1` executed 8:

**Before (`faster-compcert` v0: 22 instructions in inner loop):**

```
.L114:  movq    %rsi, %r8
        imulq   $8800, %r8              # C[i] row base recomputed every j!
        leaq    0(%rbp,%r8,1), %r8
        movslq  %edx, %r11              # 32-to-64 sign extension of j
        movq    %r11, %rcx
        movsd   0(%r8,%rcx,8), %xmm0
        movq    %rsi, %r10
        imulq   $9600, %r10             # A[i] row base recomputed every j!
        leaq    0(%r12,%r10,1), %r10
        movslq  %r9d, %rax
        movsd   0(%r10,%rax,8), %xmm6   # A[i][k]
        movapd  %xmm2, %xmm3
        mulsd   %xmm6, %xmm3
        imulq   $8800, %rax             # B[k] row base recomputed every j!
        leaq    0(%rbx,%rax,1), %r10
        movsd   0(%r10,%rcx,8), %xmm4
        mulsd   %xmm4, %xmm3
        addsd   %xmm3, %xmm0
        movsd   %xmm0, 0(%r8,%r11,8)
        leal    1(%edx), %edx
        cmpl    $1100, %edx
        jl      .L114
```

**After (`faster-compcert` v1, with dependent-chain LICM + IVwiden: 11 instructions in inner loop):**

```
.L114:  movsd   0(%rdi,%rcx,8), %xmm6   # C[i][j]: row base hoisted, 64-bit index
        movsd   0(%rdx,%r11,8), %xmm7   # A[i][k]: row base hoisted
        movapd  %xmm3, %xmm4
        mulsd   %xmm7, %xmm4
        movsd   0(%rsi,%rcx,8), %xmm8   # B[k][j]: row base hoisted
        mulsd   %xmm8, %xmm4
        addsd   %xmm4, %xmm6
        movsd   %xmm6, 0(%rdi,%rcx,8)
        leaq    1(%rcx), %rcx           # 64-bit induction variable, no movslq
        cmpq    $1100, %rcx
        jl      .L114
```

Why did `LICM` initially fail to hoist the row base addresses `C[i]`, `A[i]`, and `B[k]`? In 2D arrays, computing a row base takes a chain of three dependent instructions: sign-extend the outer index (`movslq %esi, %r8`), multiply by the row stride (`imulq $8800, %r8`), and add the array base (`leaq 0(%rbp,%r8,1), %r8`). Our first `LICM` pass only hoisted single operations whose arguments were already defined outside the loop.

For v1, we extended `LICM.v` to hoist dependent chains of invariant operations, and we built `IVwiden.v` to widen 32-bit loop indices into 64-bit induction variables. Together, those two passes cut `gemm` runtime by nearly half (from `1.96 s` down to `1.05 s`) and dropped our PolyBench geomean from `0.845x` to `0.738x`.

---

## 6. The Human Gate: When Proofs Cannot Save You

In CompCert, the transformations are formally verified using Rocq. If an agent makes a mistake in the transformations, say `Loadfwd` or `LICM`, `make proof` will reject it. However, that safety net vanishes the moment we touch the **trusted base**: the C semantics, the memory model, the x86 assembly semantics, or the code that prints the final assembly. A wrong assumption in the trusted base invalidates the correctness guarantee while Rocq happily reports `Qed`.

Even with our rule requiring human sign-off on trusted files, **twice I approved a trusted-base proposal that turned out to be mathematically false**.

In one of those instances, an agent was trying to improve the performance of `siphash24`, one of the CompCert benchmarks. `siphash24` reads little-endian 64-bit words from an unaligned `uint8_t *` pointer. In C, each word is built from eight byte loads shifted and ORed together:

```
#define U8TO64_LE(p) \
  (((uint64_t)((p)[0]))       | ((uint64_t)((p)[1]) <<  8) | \
   ((uint64_t)((p)[2]) << 16) | ((uint64_t)((p)[3]) << 24) | \
   ((uint64_t)((p)[4]) << 32) | ((uint64_t)((p)[5]) << 40) | \
   ((uint64_t)((p)[6]) << 48) | ((uint64_t)((p)[7]) << 56))
```

GCC folds those eight byte loads into a single unaligned `movq (%rdi), %rax`. CompCert could not do this because its 64-bit memory chunk (`Mint64`) requires 8-byte alignment in the memory model.

To fix this, an agent suggested adding an unaligned 8-byte chunk (`Mint64u`) to the memory model, and claimed a simple lemma: *if 8 consecutive `Mint8unsigned` loads at `ptr + 0 .. ptr + 7` all succeed, then a single `Mint64u` load at `ptr` also succeeds and returns the combined 64-bit word.*

That sounded obviously true to me. I approved it.

Then the implementing agent sat down to prove the lemma in Rocq, and **proved a counterexample instead.**

In CompCert’s memory model, pointer offsets are 64-bit modular integers (`Ptrofs.int`), which `Mem.loadv` interprets as unsigned integers in \([0, 2^{64})\). In particular, `Mem.load` requires the entire contiguous byte range \([\text{ofs}, \text{ofs} + \text{size})\) to be valid without wrapping around \(2^{64}\). Suppose a memory block has valid permissions at both the very top of the 64-bit address space (\(2^{64} - 4\) through \(2^{64} - 1\)) and the very bottom (\(0\) through \(3\)), and `ptr` sits at offset \(2^{64} - 4\):

1. All eight individual byte loads `ptr + 0` through `ptr + 7` succeed because pointer addition `Ptrofs.add` wraps modulo \(2^{64}\) before each 1-byte check.
2. The merged 8-byte load at `ptr` fails (`None`) because \([2^{64} - 4, 2^{64} + 4)\) crosses the \(2^{64}\) boundary!

Had this claim gone into the trusted base as an assumption rather than a lemma to be proved, every proof would still have passed, and the compiler would have been unsound. Because the agent was instructed to halt rather than improvise around a trusted-base flaw, we caught the error immediately. We replaced the flawed proposal with a change to the memory model itself (`common/Memtype.v` and `common/Memory.v`). Specifically, we added a global invariant `access_bounded` stating that no memory block ever has permissions at offsets \(\ge 2^{64} - 8\) (`perm_limit := Ptrofs.modulus - 8`). No real x86-64 user-space object can have size \(\ge 2^{64} - 8\) anyway. With `access_bounded` in place, 8 consecutive byte loads cannot wrap around \(2^{64}\). The merge lemma went through cleanly, and `siphash24` runtime dropped by 21% (`86.2 ms` down to `68.4 ms`).

> **Lesson from the Human Gate:** Human sign-off on formal specifications is necessary, but human intuition alone is not reliable enough. After this, we changed our process: every trusted-base proposal had to be mechanically prototyped in a scratch branch (with the key soundness lemma proved and zero admits) *and* differentially tested against the real CPU or glibc before coming to me for approval.

---

## 7. Where Performance Stands Today

Here is where `faster-compcert` stands on a quiet machine, expressed as geometric mean runtime relative to CompCert (lower is faster):

| Compiler configuration | CompCert benchmarks (24 progs, tuned) | `big` (5 progs, held out) | `PolyBench` (30 kernels, used in development) |
| --- | --- | --- | --- |
| CompCert (baseline) | 1.000 | 1.000 | 1.000 |
| `gcc -O1` | 0.893 | 0.950 | 0.756 |
| **faster-compcert (defaults)** | **0.831** | **0.967** | **0.738** |
| **faster-compcert (all opt-in flags)** | **0.815** | **0.961** | **0.733** |
| `gcc -O2` (restricted) | 0.795 | 0.887 | 0.648 |
| `gcc -O2` (full) | 0.784 | 0.886 | 0.646 |
| `gcc -O3` | 0.790 | 0.913 | 0.583 |

*(Note: “defaults” includes all verified middle-end passes plus `-fshift-mask`, `-fzext-load`, and `-fmerge-bytes`. “All opt-in flags” adds `-fload-op` and `-ftrust-libm`.)*

If we view the same data relative to full `gcc -O2` (`1.00x` = `gcc -O2`), the picture is clear:

1. On the CompCert benchmarks, CompCert started **28% behind** `gcc -O2`. It is now within **4.0% to 6.1%** (closing 81% to 89% of the gap to `gcc -O2` (restricted)).[7](#fn:gap)
2. On `PolyBench` loop nests, CompCert started **55% behind** `gcc -O2`. It is now within **13.5% to 14.2%** (closing 70% to 72% of the gap) and beats `gcc -O1`.
3. On the held-out `big` programs (`spass`, `raytracer`, `arcode`, `lzw`, `lzss`), CompCert started **13% behind** `gcc -O2` and is now **8.5% to 9.1% behind** (closing 28% to 33% of the gap).

Figure 2: Full Per-Benchmark Explorer (All 59 Programs)

All faster-compcert values use all opt-in flags, including -ftrust-libm. Values < 1.00x mean faster than CompCert. Select a suite tab to inspect raw execution times and runtime reductions.

| Benchmark | CompCert | faster-compcert (all opt-in flags) | gcc -O2 | Runtime reduction vs CompCert | Runtime vs gcc -O2 |
| --- | --- | --- | --- | --- | --- |

Positive percentages mean less runtime than CompCert; negative values indicate regressions. Ratios to gcc -O2 describe measured minima, not statistical significance.

---

## 8. What Still Blocks Us from Matching GCC -O2

While we have made significant progress in closing the performance gap in this pilot, there is still a long way to go. The gap between the CompCert benchmarks and the held-out `big` programs reflects where we focused our optimization effort (and token spend). We focused on low-hanging fruit like loop-level optimizations inside individual functions. That strategy works well for small numerical kernels. But in larger programs like `spass` and `raytracer`, runtime was driven by function call overhead, pointer indirection, and memory layout. These are things we haven’t even begun to address.

Closing the remaining gap to `gcc -O2` requires moving beyond single-function scalar passes. The following are some examples of optimizations that we identified but did not implement.

### 1. Coarse Alias Analysis and Loop-Invariant Loads

On PolyBench loop nests, `faster-compcert` still trails `gcc -O2` by 13%, partly due to missing loop-invariant load hoisting. Take `gemm` (`C[i][j] += alpha * A[i][k] * B[k][j]`): in the inner `j` loop, the value `A[i][k]` never changes. GCC hoists it once into a register before the loop starts. But CompCert currently lacks heap points-to analysis, so it cannot prove that storing into `C[i][j]` leaves `A[i][k]` untouched. Consequently, CompCert reloads `A[i][k]` from memory on every single iteration.

**What it will take:** Either a verified points-to analysis for the heap, or translation validation for C99 `restrict` annotations so the compiler can prove the arrays do not overlap.

### 2. Interprocedural Register Allocation (IPA-RA)

In call-heavy code like `spass` and `arcode`, functions call other functions constantly. CompCert compiles one function at a time. When a function executes a `call` instruction, it assumes all caller-saved registers are wiped out. Even if a small callee function touches only two registers, the caller still saves its own live variables to stack memory beforehand and reloads them afterward.

**What it will take:** Whole-program analysis across the compilation unit, letting the compiler customize calling conventions so callers only save registers the callee actually touches.

### 3. Stack Frame Back-Links

On x86-64, an optimized function prologue simply subtracts a constant offset from the stack pointer (`subq $sz, %rsp`).

CompCert’s formal model instead tears down each stack frame (`Pfreeframe`) by reading a stored back-link from memory, so every prologue (`Pallocframe`) must also write that back-link (an extra `leaq` and `movq`). Small, non-inlined functions that could otherwise run entirely in CPU registers are forced to store a stack pointer to memory on every call.

**What it will take:** Either more aggressive inlining to remove the frame altogether, or refactoring `Mach` and `Asm` frame semantics so `Pfreeframe` no longer reads the back-link and the store can be dropped.

---

## 9. Takeaways

We started with two questions: why is CompCert slower than `gcc -O2`, and can LLM agents close the gap?

First, CompCert’s formal models are not the primary reason for it being slow. Almost all of the gap between CompCert and `gcc -O2` comes from missing optimization passes and suboptimal instruction selection.

Second, LLM agents can write and prove serious compiler optimizations at scale with minimal human supervision. Writing nearly 15,000 lines of Rocq code, including implementations and proofs, was fast and reliable. Classical performance engineering (catching negative pass interactions, preventing quadratic compile-time blow-ups, checking for overfitting with held-out suites, and fixing shared-machine timing noise) involved more human input than proof engineering.

Finally, formal verification works only when the model of the real system is accurate. Agents automate traditionally difficult parts of the job like pass-building and proof generation, but human guardrails are still needed for defining the scope of the system and verifying that the model is accurate. Methods like differential testing can help bridge this gap in the future to further reduce the human effort required.

*Written by [Aananth V](https://www.linkedin.com/in/aananthv), a first-year master’s student working with InfraAI on AI for systems and formal verification. Edited by [Rohit Dwivedula](https://dwivedula.dev). This work was supported by AWS credits from Amazon.*

1. The theorem covers the verified pipeline from CompCert C abstract syntax to assembly abstract syntax. Front-end elaboration, assembly printing, assembling, and linking remain trusted. See the [CompCert manual](https://compcert.org/man/manual001.html). [↩](#fnref:scope)
2. Xuejun Yang, Yang Chen, Eric Eide, and John Regehr. [Finding and Understanding Bugs in C Compilers](https://doi.org/10.1145/1993498.1993532). PLDI 2011. [↩](#fnref:csmith)
3. Vu Le, Mehrdad Afshari, and Zhendong Su. [Compiler Validation via Equivalence Modulo Inputs](https://doi.org/10.1145/2594291.2594334). PLDI 2014. [↩](#fnref:emi)
4. Chengnian Sun, Vu Le, Qirun Zhang, and Zhendong Su. [Toward Understanding Compiler Bugs in GCC and LLVM](https://doi.org/10.1145/2931037.2931074). ISSTA 2016. [↩](#fnref:sun)
5. CompCert benchmarks: the programs in CompCert 3.18’s `test/c` directory ([CompCert-small-tests](https://github.com/AbsInt/CompCert-small-tests)). PolyBench: the 30 loop-nest kernels of [PolyBench/C 4.2.1](https://sourceforge.net/projects/polybench/). All measurements in this post were taken on an Intel Xeon Silver 4314; the benchmarking harness is in [`faster-compcert/`](https://github.com/UT-InfraAI/CompCert/tree/v3.18/faster-compcert) in our fork. [↩](#fnref:bench)
6. The v0 numbers in this section come from an earlier measurement session. In the final runs in Section 7, `gcc -O1` measured `0.950x` on `big` and `0.756x` on PolyBench because of run-to-run machine drift. [↩](#fnref:drift)
7. “Gap closed” is measured on a log scale against `gcc -O2` (restricted): `ln(faster-compcert) / ln(gcc -O2 restricted)`, using the geomeans in the table above. [↩](#fnref:gap)
