Skip to content
STIMSMITH

Equivalence Proof

Concept WIKI v1 · 5/29/2026

An equivalence proof formally shows that two system descriptions exhibit the same relevant behavior under a defined relationship. In the cited processor-verification setting, the proof relates an RTL CPU implementation to an ISA-level model using an abstraction function from implementation state to architectural state.

Overview

An equivalence proof is a formal argument that two descriptions of a system agree on the behavior of interest. In the processor-verification example from Generating an Efficient Instruction Set Simulator from a Complete Property Suite, the equivalence proof relates a CPU implementation at the Register Transfer Level (RTL) to an instruction-set architecture (ISA) model.

RTL-to-ISA structure

In the cited approach, the proof uses an abstraction function, named vstate, that maps the implementation state of the CPU to the architectural ISA state. The intended commuting structure is:

  1. start from a CPU implementation state;
  2. map it to an ISA state using vstate;
  3. execute the ISA transition using next_state; and
  4. show that this corresponds to first applying the CPU transition relation T and then mapping the resulting CPU state back to the ISA state using vstate.

The architectural proof obligation shown in the evidence has the form that, when the processor is ready to start an instruction, the ISA state at the next time step equals the result of applying next_state to the current ISA state and decoded instruction.

Supporting obligations

The RTL-to-ISA equivalence proof is not limited to the core state-transition diagram. The cited paper also states that it must be proved that interface signals behave as captured by interface macros, and that the implementation reset state complies with the defined architectural reset state.

Relationship to simulator generation

In the cited ISS-generation workflow, a full equivalence proof between ISA and RTL is not required before generating the instruction set simulator. The ISA can be developed early in ITL and used to generate an ISS; full confidence that the generated ISS complies with the design is obtained later, at the end of verification. The same evidence notes that finding appropriate mapping functions for the architectural state is one of the more sophisticated parts of verification, but those mapping functions are not needed to automatically generate the ISS.

Role of architectural state

The approach models architectural state explicitly, typically as a user-defined VHDL record combining elements such as the register file, status flags, and program counter. A next_state macro captures the effects of instructions and interrupts on this architectural state, and the resulting single property can serve as a formally checkable ISA description.

LINKED ENTITIES

2 links
Generating an Efficient Instruction Set Simulator from a Complete Property Suite MENTIONS
Register-Transfer Level USES

CITATIONS

6 sources
6 citations
[1] In the cited processor-verification setting, an equivalence proof relates RTL and ISA descriptions. Generating an Efficient Instruction Set Simulator from a Complete Property Suite
[2] The RTL-to-ISA proof uses an abstraction function vstate that maps CPU implementation state to ISA architectural state. Generating an Efficient Instruction Set Simulator from a Complete Property Suite
[3] The proof shows that applying the ISA next_state transition corresponds to applying the CPU transition relation and then mapping the resulting implementation state to the ISA state. Generating an Efficient Instruction Set Simulator from a Complete Property Suite
[4] The proof also requires showing that interface signals match the interface macros and that the implementation reset state complies with the architectural reset state. Generating an Efficient Instruction Set Simulator from a Complete Property Suite
[5] A full equivalence proof between ISA and RTL is not required before generating the ISS; the ISS can be generated early from the ISA and full confidence is achieved later through verification. Generating an Efficient Instruction Set Simulator from a Complete Property Suite
[6] The architectural state is modeled explicitly, often as a VHDL record including components such as register file, status flags, and program counter, while next_state captures instruction and interrupt effects. Generating an Efficient Instruction Set Simulator from a Complete Property Suite