UCLID5 Verification Condition (correspondence invariant)

UCLID5 Verification Condition: correspondence invariant

CodeArtifact

The `correspondence` invariant is a UCLID5 verification condition used in the formal verification of pipelined Y86-64 microprocessors. It checks that the state produced by PIPE execution is consistent with the state produced by SEQ execution after the required flushing sequence and under the permitted initial pipeline-state restrictions.

First seen 5/26/2026

Last seen 5/26/2026

Evidence 1 chunks

Wiki v1

WIKI

Overview

The correspondence invariant is the UCLID5 representation of a correctness condition for verifying that a pipelined Y86-64 processor model (PIPE) behaves consistently with a sequential processor model (SEQ). The cited source identifies Figure 14 as a "Verification Condition" and states that the check ensures PIPE operation is consistent with SEQ operation. [C1]

invariant correspondence :
(
 step  > nflush+3
 && pipe_state_ok0
) ==>
 ((S_stat_b0 == SAOK ==> S_pc_a == S_pc_b0)
   &&  S_rf_a == S_rf_b0
   &&  S_cc_a == S_cc_b0
   &&  S_mem_a == S_mem_b0
   &&  S_stat_a == S_stat_b0) ||
 ((S_stat_b0 == SAOK ==> S_pc_a == S_pc_b1)
   &&  S_rf_a == S_rf_b1
   &&  S_cc_a == S_cc_b1
   &&  S_mem_a == S_mem_b1
   &&  S_stat_a == S_stat_b1);

READ FULL ARTICLE →

NEIGHBORHOOD

No graph connections found for this entity yet. It may appear in future ingestion runs.

explore full graph →

RELATIONSHIPS

1 connections

Burch-Dill Correspondence Checking implements → 100% 1e

The UCLID5 verification condition expresses the Burch-Dill correspondence invariant between PIPE and SEQ.

CITATIONS

8 sources

8 citations — click to expand

[1] Figure 14 is a UCLID5 verification condition named `correspondence` that checks PIPE operation for consistency with SEQ operation. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5

[2] The symbolic simulation is expressed as parallel runs of two PIPE copies, `pipe_A` and `pipe_B`, plus one SEQ copy, with both PIPE copies starting from the same symbolic initial state. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5

[3] The verification framework includes control signals for normal or flushing PIPE operation, importing PIPE values into SEQ state elements, and operating SEQ; state-variable values are captured as UCLID5 variables for assertions. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5

[4] Although the condition is expressed as an invariant, `step > nflush+3` means correspondence is required only at steps `n + 4` and beyond; this relates to UCLID5's simultaneous state-update model and flushing-step sequencing. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5

[5] `pipe_state_ok0` describes restrictions that may be imposed on the initial pipeline state. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5

[6] The invariant's consequent compares program counter, register file, condition codes, memory, and status values between `S_*_a` and either the `b0` or `b1` state. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5

[7] The PC consistency condition is imposed only when the processor starts in normal execution, represented in the invariant by the guard `S_stat_b0 == SAOK`. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5

[8] The approach differs from traditional simulation-based testing by operating over all possible states for a short simulation sequence rather than starting from reset and running for many cycles. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5