Formal Computer Science / Programs & systems

Kenton Labs / Programs & systems

Compiler optimization

A rewrite is correct when source and target agree under the exact language semantics and observable behavior.

The vocabulary.

These definitions state the objects and properties used by the dataset. The complete instance specification remains the authority for each result.

Semantic equivalence
The same observable result for every input in the declared domain.
Modular arithmetic
Arithmetic wraps modulo 2ʷ for width w.
Strength reduction
Replacing an operation with another expression whose performance must be evaluated separately.

How the dataset works.

Three deterministic instances define this family. Each includes its input model, a checked result, evidence, and an acceptance procedure. Download the complete dataset JSON ↘ or the area’s readable source ↘.

Acceptance procedure

  1. Enumerate every value at the chosen bit width.
  2. Evaluate the source expression modulo 2ʷ.
  3. Evaluate the replacement under the same semantics.
  4. Compare outputs, including wraparound inputs.

Cost and scope

Unary width-w equivalence by enumeration checks 2ʷ inputs. This is practical for small widths, not a general large-program optimizer.

A common failure

Correctness is not a speedup claim; duplicating an expression with side effects can be invalid.

Worked records.

Three instances expose concrete claims and the artifacts that establish or refute them. Expand a record for the problem, checker reasoning, formal payload, and verification metadata.

KL-FCS-011
Compiler optimizationStrength reduction under modular arithmeticComplete bit-vector equivalence · 16 inputs

The problem

Check the rewrite x × 2 → x + x for every unsigned four-bit x.

The checked result

Equivalent: yes.

For each possible input, the original and replacement expressions yield the same four-bit result, including values that wrap.

Why the checker accepts it

  1. Enumerate every value at the chosen bit width.
  2. Evaluate the source expression modulo 2ʷ.
  3. Evaluate the replacement under the same semantics.
  4. Compare outputs, including wraparound inputs.

Formal specification

{
  "width": 4,
  "source": "x * 2",
  "semantics": "Pure expressions on four-bit values, with both operators modulo 16 and no observable side effects."
}

Claim and evidence

{
  "claim": {
    "equivalent": true
  },
  "witness": {
    "replacement": "x + x"
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 16 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

Unary width-w equivalence by enumeration checks 2ʷ inputs. This is practical for small widths, not a general large-program optimizer.

This example does not establish a rewrite for language undefined behavior, side effects, overflow flags, other widths, or floating-point arithmetic. No speedup is claimed.

A boundary to investigate

Correctness is not a speedup claim; duplicating an expression with side effects can be invalid. Add expression DAGs, observable-state semantics, and checked equivalence certificates.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-026 ↘Related KL-FCS-027 ↘
KL-FCS-026
Compiler optimizationEliminate an eight-bit neutral additionComplete equivalence · 256 inputs

The problem

Check a pure unsigned modular rewrite at every input.

The checked result

Equivalent: yes.

The checker evaluates both expressions at every representable value. Overflow wraps identically in the two expressions.

Why the checker accepts it

  1. Enumerate every value at the chosen bit width.
  2. Evaluate the source expression modulo 2ʷ.
  3. Evaluate the replacement under the same semantics.
  4. Compare outputs, including wraparound inputs.

Formal specification

{
  "width": 8,
  "source": "x + 0",
  "semantics": "Pure unsigned 8-bit arithmetic modulo 256, with no side effects."
}

Claim and evidence

{
  "claim": {
    "equivalent": true
  },
  "witness": {
    "replacement": "x"
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 256 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

Unary width-w equivalence by enumeration checks 2ʷ inputs. This is practical for small widths, not a general large-program optimizer.

The result does not transfer automatically to signed-overflow undefined behavior or effectful expressions.

A boundary to investigate

Correctness is not a speedup claim; duplicating an expression with side effects can be invalid. Add expression DAGs, observable-state semantics, and checked equivalence certificates.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-011 ↘Related KL-FCS-027 ↘
KL-FCS-027
Compiler optimizationTriple a six-bit value by additionComplete equivalence · 64 inputs

The problem

Check a pure unsigned modular rewrite at every input.

The checked result

Equivalent: yes.

The checker evaluates both expressions at every representable value. Overflow wraps identically in the two expressions.

Why the checker accepts it

  1. Enumerate every value at the chosen bit width.
  2. Evaluate the source expression modulo 2ʷ.
  3. Evaluate the replacement under the same semantics.
  4. Compare outputs, including wraparound inputs.

Formal specification

{
  "width": 6,
  "source": "x * 3",
  "semantics": "Pure unsigned 6-bit arithmetic modulo 64, with no side effects."
}

Claim and evidence

{
  "claim": {
    "equivalent": true
  },
  "witness": {
    "replacement": "(x + x) + x"
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 64 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

Unary width-w equivalence by enumeration checks 2ʷ inputs. This is practical for small widths, not a general large-program optimizer.

The result does not transfer automatically to signed-overflow undefined behavior or effectful expressions.

A boundary to investigate

Correctness is not a speedup claim; duplicating an expression with side effects can be invalid. Add expression DAGs, observable-state semantics, and checked equivalence certificates.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-011 ↘Related KL-FCS-026 ↘

Go further.

Add expression DAGs, observable-state semantics, and checked equivalence certificates.

Questions to investigate

  1. Correctness is not a speedup claim; duplicating an expression with side effects can be invalid.
  2. Which assumption in the specification can be changed to make the current evidence insufficient?
  3. Add expression DAGs, observable-state semantics, and checked equivalence certificates.

Conceptual references

These sources explain the surrounding theory. The linked material was not imported as a dataset, and these records do not claim checking by the source’s software.

Primary conceptual reference ↗

Related areas

Model checkingAbstract interpretationProgram verificationDistributed protocols