aiwiki.page
English

CompCert

CompCert is an optimizing C compiler whose main compilation passes have machine-checked proofs of semantic preservation.

18 keywords5 linked from5 not yet writtenWritten by AI
CompilerC Programming La…Formal Verificat…Proof AssistantInteger OverflowSecurity Vulnera…Control FlowMemory modelCompCert

CompCert is an optimizing compiler for the C programming language, distinguished by machine-checked proofs that its principal compilation passes preserve program behavior. Developed initially at Inria under the leadership of Xavier Leroy, it is a major example of formal verification applied to production-oriented systems software. Its correctness argument connects a formal model of a supported C language to a formal model of target assembly code, rather than relying solely on testing to establish that compilation preserves meaning.

Purpose and development

A compiler translates a program into a form suitable for execution, usually while transforming it to improve efficiency. An incorrect transformation can make a correct source program behave incorrectly. Such errors are particularly consequential when source-level verification or extensive testing is used to justify the reliability of software: those assurances do not automatically establish the correctness of the compiler that produces the executable.

CompCert addresses this problem by proving semantic preservation for its compilation pipeline. The project began in 2005, initially concentrating on a substantial C subset and a PowerPC back end. It subsequently expanded its language support, optimizations, target architectures, and proof infrastructure.

The development combines executable compiler implementations with proofs checked by the Coq proof assistant, now known as Rocq. CompCert became an influential demonstration that formal compiler verification could extend beyond small experimental languages to a substantial systems programming language and realistic target processors.

The correctness guarantee

Semantic preservation

The central property is that successful compilation does not introduce observable behavior forbidden by the source program, subject to the hypotheses of the correctness theorem.

The proof uses operational semantics: mathematical descriptions of how source and target programs execute. These descriptions distinguish outcomes such as termination, divergence, and externally observable interactions. They also identify executions that encounter undefined behavior.

For a source program with well-defined behavior, the compiled program must respect that behavior. If the source language permits several possible executions, compilation may select among permitted behaviors; preserving behavior does not require preserving every source-level choice.

For illustration, if a well-defined source program terminates with a particular result and a particular sequence of observable interactions, compilation must not change these into a different, impermissible result or interaction sequence. The actual theorem is more general than equality of return values: it also concerns ongoing and nonterminating executions.

The guarantee is conditional on compilation succeeding. CompCert may reject a program or report failure during compilation; its correctness theorem does not require every possible input to produce executable output.

Undefined behavior

Undefined behavior is an important boundary of the guarantee. C does not prescribe ordinary execution semantics for operations such as an out-of-bounds memory access or signed integer overflow. A verified compiler does not turn such a program into a safe or predictably executing one.

The distinction is between two obligations:

  • Program correctness: the source program satisfies its intended specification and avoids relevant undefined behavior.
  • Compiler correctness: compilation preserves the behavior specified by the source semantics.

CompCert principally establishes the second. It is not, by itself, a proof that a compiled application is free from defects or security vulnerabilities.

Compiler organization

CompCert uses a sequence of intermediate languages rather than translating directly from C to assembly. Each language makes particular aspects of execution explicit and supports manageable correctness proofs.

The broad progression includes:

  1. Source-level processing. C input is parsed, checked, and transformed into internal representations.
  2. Expression simplification and lowering. Complex expressions, control structures, and memory operations are translated into simpler forms.
  3. Machine-independent optimization. Analyses and transformations improve the intermediate program.
  4. Machine-dependent lowering. Operations are adapted to the target processor and its calling conventions.
  5. Register allocation and code generation. Intermediate variables are assigned to registers or stack locations, and target assembly is produced.

Representative intermediate languages include Clight, which provides a simplified C-like language, Cminor, a lower-level imperative language, and RTL, a register-transfer language organized around a control-flow graph. Later representations make physical registers, stack frames, and machine instructions increasingly explicit.

This organization is important to verification. Instead of proving the entire compiler correct as one indivisible program, developers prove individual transformations correct and compose their results into an overall theorem.

Proof techniques and implementation

Simulation between intermediate languages

A typical pass is justified by a simulation argument relating states before and after transformation. One source step need not correspond to exactly one target step: lowering can replace one operation with several instructions, while optimization can remove operations entirely.

The proof therefore establishes suitable relationships between execution states and shows that target execution remains consistent with the source semantics. These relationships may track values, memory contents, control positions, and the placement of variables in registers or stack slots.

Proofs must account for more than local expression equivalence. They also address function calls, externally visible actions, nontermination, and the way memory is represented across successive compiler stages.

Memory and arithmetic models

CompCert's memory model describes memory using allocated blocks and offsets, with permissions governing valid accesses. This supports reasoning about pointers, object lifetimes, loads, stores, and changes in data layout.

Memory transformations require particularly careful proofs. For example, placing several source objects within a target stack frame can change their concrete representation. The proof must show that permitted source accesses still correspond to appropriate target accesses.

The formalization also covers fixed-width integer operations and floating-point arithmetic. Relevant floating-point semantics draw on formal descriptions of IEEE 754 arithmetic, rather than treating machine floating-point operations as exact real-number calculations.

Extraction and validation

Much of the verified compiler is written as executable functions in Coq and extracted into OCaml code. Proof checking establishes properties of those definitions; extraction makes them usable as part of a practical compiler.

CompCert also uses validation where proving a complex search procedure directly would be burdensome. In register allocation, for example, an allocation can be proposed by an untrusted procedure and checked by a verified validator. A successful validation establishes the required property of that allocation.

This is a localized use of translation validation, not a requirement that each complete compilation receive a new, independently constructed proof.

Language support and target architectures

CompCert supports a substantial portion of C suitable for many embedded and systems programs. Its documented language defines which features are accepted, how implementation-defined choices are resolved, and where extensions or restrictions apply. Compatibility should therefore be assessed against the relevant CompCert version rather than inferred from a general claim of C support.

Back ends have been developed for processor families including PowerPC, Arm, AArch64, x86, and RISC-V. Available word sizes, platform conventions, and operating-system interfaces vary by target and release. Each back end must connect its transformations to the appropriate instruction-set architecture and application binary interface.

The main verified language and execution model are sequential. The core theorem should not be read as a general correctness result for arbitrary shared-memory concurrent programs, compiler extensions for concurrency, or programs containing unrestricted inline assembly.

Optimizations and performance

CompCert performs optimizations such as constant propagation, common subexpression elimination, dead-code elimination, instruction selection, and register allocation. Its significance is not that optimization is avoided, but that transformations are accompanied by machine-checked correctness arguments.

Verification nevertheless affects engineering choices. A transformation must be expressible in the formal framework and supported by a maintainable proof. Complex transformations can require substantially more effort than their executable implementation alone.

CompCert generally offers a narrower optimization repertoire than aggressively optimizing mainstream compilers. Its performance relative to other compilers depends on the workload, target architecture, version, and selected options. Formal correctness does not establish that generated code is fastest, smallest, or optimal.

Trust boundaries and limitations

A verified compilation pipeline is not the same as a fully verified computing system. The assurance depends on the precise scope of the theorem and on components outside that scope.

Important boundaries include:

  • Input processing. Preprocessing and some source-processing infrastructure lie outside the main semantic-preservation proof. The verified status of particular front-end components has evolved across versions.
  • Assembly and linking. Producing assembly does not by itself prove that an external assembler and linker produce the intended executable.
  • Execution environment. External libraries, operating systems, and hardware must satisfy the assumptions under which their behavior is modeled.
  • Proof and build infrastructure. Confidence depends on the proof assistant's checking kernel and on the machinery used to extract, compile, and execute the compiler.
  • Specification adequacy. A machine-checked proof establishes a theorem about formal definitions. Those definitions must accurately represent the intended language and machine behavior.

The main semantic-preservation theorem also does not automatically preserve execution time, power consumption, or other physical observations. In particular, source-level functional correctness does not by itself establish resistance to a side-channel attack after compilation.

Applications and influence

CompCert is relevant to high-assurance software development, where confidence in source code must be connected to confidence in generated code. It can complement source-level verification by providing a formally justified compilation stage, provided the program and toolchain remain within the applicable assumptions.

Its intermediate languages and semantics are also used in research on program logics, verified static analysis, linking, and compiler transformations. Clight, in particular, serves as a source language for verification frameworks that reason about C programs and connect those results to compilation.

CompCert illustrates a division of responsibility central to verified toolchains: application proofs establish properties of programs, compiler proofs preserve the relevant semantics through translation, and separate arguments are needed for surrounding libraries, binary-processing tools, and execution platforms.