Pointer Provenance

Two pointers can hold the same bit pattern yet not be interchangeable. Provenance is the extra metadata — "which allocation did this pointer come from?" — that makes them distinguishable in a language's memory model. It's what rules out certain compiler optimizations that seem obviously correct at the bit level but break program semantics at the language level.

The nerd-snipe example

If p1 and p2 have the same type, is it valid for a compiler to rewrite if (p1 == p2) { f(p1); } to if (p1 == p2) { f(p2); }?

At the bit level, yes — we just checked they're equal. But with provenance, no: p1 and p2 might be equal numerically yet be derived from different allocations. Passing p2 instead of p1 into f would mean f operates through a different provenance, and any bounds checks, escape analysis, or aliasing reasoning f does would apply to the wrong allocation.

In C and C++, the memory model is ambiguous enough that this question has generated years of committee debate. Ralf Jung's pointer provenance post is a standard reference.

Why compilers care

Modern compilers exploit provenance rules to justify optimizations:

• Alias analysis. Pointers from different allocations can't alias; the compiler can reorder loads and stores around them.
• Escape analysis. A pointer that never escapes its allocation can be kept in registers.
• Dead store elimination. Writes to memory reachable only through one provenance can be removed once that provenance is gone.

Each of these relies on the compiler trusting that equal bit patterns with different provenance don't leak across.

Why fil-c makes it concrete

Most language implementations track provenance abstractly — as a property of the abstract machine the compiler reasons about, erased at runtime. fil-c makes provenance observable at runtime: every pointer is paired with an AllocationRecord* that is the provenance. Two pointers with equal addresses but different records will behave differently because they carry different bounds and different GC-reachability. So the compiler-rewrite question above has a clearly wrong answer in Fil-C: the two pointers aren't interchangeable because their companion records aren't.

This makes Fil-C a useful mental model when thinking about what "provenance" actually means in a concrete system, as distinct from what it means in a committee's abstract machine.

Related

• simplified-model-of-fil-c — where the provenance/capability pairing is described in detail
• fil-c — the project
• no-silver-bullet — provenance is essential complexity in the C/C++ memory model; no optimization trick eliminates it