Skip to content
STIMSMITH

ALU Abstraction Modeling

Concept WIKI v1 · 5/26/2026

ALU abstraction modeling is the choice of how precisely to represent arithmetic-logic-unit behavior in a formal processor model. In the cited UCLID5 verification work on pipelined Y86-64 processors, ALU behavior ranges from a fully uninterpreted function to partially interpreted addition-specific models and a more precise arithmetic/bit-vector model, with the required precision depending on the pipeline variant being verified.

Overview

ALU abstraction modeling is the selection of a precision level for modeling arithmetic-logic-unit behavior in a formal processor model. In the UCLID5 verification study of pipelined Y86-64 microprocessors, ALU operations were modeled at several abstraction levels, from an uninterpreted function to precise arithmetic and bit-vector operations. These ALU choices were combined with different word representations: uninterpreted terms, integers, or bit vectors. [C1]

The abstraction choices form a partial order: a model is more abstract when it permits a wider range of behaviors. Uninterpreted data types are more abstract than concrete data types, and uninterpreted functions are more abstract than precise mathematical functions. The evidence also treats integer and bit-vector word models as incomparable: some arithmetic behavior can be related by modulo mapping, but equality, ordering, and bit-wise logical operations are not preserved in the same way. [C2]

ALU abstraction levels

The cited work considered the following ALU models. [C3]

Uninterpreted ALU

The most abstract ALU model defines the ALU as an uninterpreted function of an operation code and two word operands. In UCLID5-style pseudocode, the result is delegated to a base uninterpreted ALU function:

val = common.base_alufun(op, valA, valB);

This level was sufficient for verifying the STD, FULL, STALL, and LF pipeline variants. [C4]

ALU Add zero

The ALU Add zero model partially interprets addition only for the identity case x + 0 = x; otherwise, ALU behavior remains uninterpreted. The model is expressed by returning valA when the operation is ALUADD and the second operand is zero, and otherwise calling the uninterpreted base ALU function. [C5]

This abstraction was required for the NT and BTFNT pipeline variants, where the ALU is used to pass the branch target through the execute stage when a branch is taken. [C5]

ALU Increment/Decrement

The ALU Increment/Decrement model attempts to capture the multi-application property (x + 8) + -8 = x. Because this property concerns multiple applications of the ALU function, the cited work expresses it as a UCLID5 axiom over the otherwise uninterpreted ALU function rather than as a direct procedure definition. [C6]

This property was required for the SW pipeline variant because of how that variant manipulates the stack pointer for the popq instruction. However, the SMT solver could not make effective use of the axiom, and verification at this abstraction level was unsuccessful. [C6]

ALU Add

The ALU Add model fully interprets ALU behavior for addition and leaves other operations uninterpreted. It can be used only when words are modeled as integers or bit vectors. This abstraction sufficed for verifying all pipeline variants in the cited study. [C7]

Precise ALU

The Precise model represents the ALU as precisely as UCLID5 permits. Addition and subtraction are modeled precisely; bit-wise logical operations are modeled precisely when bit-vector words are used. The model also precisely represents program-counter incrementing and the comparison operation used in the BTFNT variant to compare the branch target with the current program counter. [C8]

The precise model was used to test UCLID5 behavior when supplied with more precision than was required for the verification task. [C8]

Interaction with data representation

The ALU abstraction is combined with the representation of data words. The cited work considers three word representations:

  • U: uninterpreted terms;
  • I: integers;
  • B: bit vectors. [C1]

In the abstraction diagram described by the evidence, each vertical chain corresponds to ALU precision, ranging from uninterpreted functions at the most abstract level to precise ALU modeling at the least abstract level. The two most precise ALU models apply only to integer and bit-vector data. [C9]

Although uninterpreted data was theoretically sufficient for all variants, the SW variant required integer or bit-vector data with precise addition in practice, because the SMT solver could not effectively use the increment/decrement axiom. [C10]

Role in the execute stage

In the pipeline model, the execute-stage procedure computes ALU operands and the ALU function, calls alu_operate, and then conditionally updates condition codes using cc_fun. The cited UCLID5 execute-stage sketch includes:

aluA  = gen_aluA();
aluB  = gen_aluB();
alufun = gen_alufun();
call (e_valE) = alu_operate(alufun, aluA, aluB);
set_cc = gen_set_cc();
if (set_cc) {
  cc = common.cc_fun(alufun, aluA, aluB);
}

This shows that the chosen ALU abstraction directly affects the modeled execute-stage result e_valE, and, when condition codes are set, the inputs to condition-code computation. [C11]

Modeling implication

The central modeling tradeoff is between abstraction and required semantic precision. More abstract ALU models can simplify verification by allowing fewer concrete arithmetic commitments, but some pipeline behaviors require specific arithmetic facts such as addition identity, stack-pointer increment/decrement cancellation, or fully interpreted addition. When solver support for an axiom is ineffective, a less abstract model using integer or bit-vector arithmetic may be necessary. [C2] [C6] [C10]

CITATIONS

11 sources
11 citations
[1] ALU abstraction modeling in the cited work combines choices of ALU precision with word representations such as uninterpreted terms, integers, and bit vectors. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[2] The abstraction levels form a partial order in which uninterpreted data and functions are more abstract than concrete data types and precise mathematical functions; integer and bit-vector models are treated as incomparable. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[3] The cited work defines multiple ALU abstraction alternatives, including uninterpreted, Add zero, Increment/Decrement, Add, and Precise models. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[4] The uninterpreted ALU model defines ALU behavior through an uninterpreted function and sufficed for pipeline variants STD, FULL, STALL, and LF. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[5] The ALU Add zero model captures x + 0 = x while otherwise leaving behavior uninterpreted, and it was required for NT and BTFNT because the ALU passes the branch target through the execute stage when a branch is taken. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[6] The ALU Increment/Decrement abstraction captures (x + 8) + -8 = x as an axiom; it was needed for SW stack-pointer manipulation in popq, but the SMT solver could not use the axiom effectively and verification at that level was unsuccessful. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[7] The ALU Add model fully interprets addition, leaves other operations uninterpreted, applies only to integer or bit-vector word models, and sufficed for all pipeline variants. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[8] The Precise ALU model includes precise addition and subtraction, bit-wise logical operations for bit-vector data, precise program-counter incrementing, and the comparison used by BTFNT. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[9] The abstraction diagram has vertical chains from uninterpreted ALU functions to precise ALU modeling, and the two most precise ALU models apply only to integer and bit-vector data. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[10] Although uninterpreted data should suffice in principle, the SW variant required integer or bit-vector data with precise addition because the solver could not effectively use the increment/decrement axiom. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[11] The execute-stage UCLID5 procedure computes ALU operands and operation code, calls alu_operate, and conditionally computes condition codes using cc_fun. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5