sv_sim_sim/constraints/

func.rs

//! Functions called from constraints (task C13; IEEE 1800-2023 18.5.11).
//!
//! # What is here
//!
//! A constraint may call a function (`length == count_ones(v)`). The LRM calls
//! it *before* the constraints are solved and treats its return value as a
//! state variable, so the solver never has to look inside it: the call is
//! evaluated once its arguments are known and replaced by the constant it
//! returns ([`fold_ground_calls`]). Which arguments are known when is the
//! business of [`super::func_order`] (an argument that is a random variable is
//! solved first).
//!
//! The function itself is a [`Func`]: the builder translates the body of the
//! SystemVerilog function into a small structured statement language over the
//! constraint IR's own expressions, and [`call`] interprets it. The body's
//! expressions are ordinary [`Expr`]s whose `Var(i)` is slot `i` of the call's
//! *frame* (formals, then locals, then the result variable), so the whole
//! operator semantics (widths, signedness, shifts, division) is the one the
//! constraints already use. State variables (a non-`rand` property the body
//! reads) are the program's, read before the solve like any other.
//!
//! # Restrictions (all loud, at build time)
//!
//! The builder refuses what LRM 18.5.11 forbids (`output`/`inout`/non-`const`
//! `ref` formals, `rand_mode`/`constraint_mode`, state kept across calls) and
//! what this interpreter does not model (strings, reals, aggregates, tasks,
//! system calls other than constant ones, timing). A body that reads a random
//! variable of the object other than through an argument is refused: the LRM
//! gives such a read no meaning (the call precedes the solve).
//!
//! Locals are two-state here: a 4-state local starts at 0 rather than `x`
//! (the same 2-state view the constraint solver takes of every value).
//!
//! # Limits
//!
//! A call runs at most [`MAX_STEPS`] statements and nests at most
//! [`MAX_DEPTH`] calls deep; past either, the call fails with a
//! [`FuncError`] instead of hanging the simulation on a runaway loop.

use super::ir::{ArrayNode, Assignment, ConstraintEvalError, Expr, FuncId, Ty, eval, mask};
use num_bigint::BigUint;
use num_traits::Zero;
use std::fmt;

/// The most statements one top-level call may execute.
pub const MAX_STEPS: u64 = 1 << 22;
/// The deepest nesting of calls (a function calling functions).
pub const MAX_DEPTH: usize = 64;

/// One statement of a function body.
#[derive(Clone, Debug, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub enum Stmt {
    /// `slot = expr`; the expression already has the slot's type.
    Assign(u32, Expr),
    /// `if (cond) then else otherwise` (a case statement is built as a chain).
    If(Expr, Vec<Stmt>, Vec<Stmt>),
    /// A loop. With `test_first` the condition is tested before every
    /// iteration (`while`, `for`); without it, after every iteration but not
    /// before the first (`do ... while`). `step` runs after each iteration,
    /// also one ended by `continue` (a `for`'s step expressions). No `cond` is
    /// an endless loop (`forever`, `for (;;)`).
    Loop {
        /// The loop condition.
        cond: Option<Expr>,
        /// The loop body.
        body: Vec<Stmt>,
        /// The step run after the body.
        step: Vec<Stmt>,
        /// Whether the condition guards the first iteration too.
        test_first: bool,
    },
    /// `break`.
    Break,
    /// `continue`.
    Continue,
    /// `return`: the result variable already holds the value.
    Return,
}

/// A function of a [`super::registry::Program`].
#[derive(Clone, Debug, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub struct Func {
    /// Its declared name (diagnostics).
    pub name: String,
    /// The type of every frame slot: the formals (`n_params` of them, in
    /// declaration order), the locals, then the result variable at [`Self::ret`].
    pub slots: Vec<Ty>,
    /// How many leading slots are formals.
    pub n_params: usize,
    /// The slot of the result variable (the function's own name).
    pub ret: u32,
    /// The body.
    pub body: Vec<Stmt>,
}

/// Why a call failed.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum FuncError {
    /// An expression of the body (or an argument) could not be evaluated.
    Eval(ConstraintEvalError),
    /// A call names no function, or passes the wrong number of arguments (a
    /// malformed program).
    Malformed(&'static str),
    /// The nesting of calls exceeded [`MAX_DEPTH`].
    TooDeep {
        /// The function being entered.
        func: String,
    },
    /// The call executed more than [`MAX_STEPS`] statements.
    StepLimit {
        /// The function that was running.
        func: String,
    },
}

impl fmt::Display for FuncError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            FuncError::Eval(e) => write!(f, "a function called from a constraint failed: {e}"),
            FuncError::Malformed(w) => write!(f, "malformed function call in a constraint: {w}"),
            FuncError::TooDeep { func } => write!(
                f,
                "function `{func}` called from a constraint nests calls deeper than {MAX_DEPTH}"
            ),
            FuncError::StepLimit { func } => write!(
                f,
                "function `{func}` called from a constraint ran more than {MAX_STEPS} statements \
                 (a runaway loop?)"
            ),
        }
    }
}

impl std::error::Error for FuncError {}

impl From<ConstraintEvalError> for FuncError {
    fn from(e: ConstraintEvalError) -> Self {
        FuncError::Eval(e)
    }
}

/// How a statement list ended.
#[derive(Clone, Copy, PartialEq, Eq)]
enum Flow {
    Normal,
    Break,
    Continue,
    Return,
}

struct Machine<'a> {
    funcs: &'a [Func],
    /// The state values; `vars` is the frame of the call being run.
    asg: Assignment,
    steps: u64,
}

impl Machine<'_> {
    fn func(&self, id: FuncId) -> Result<&Func, FuncError> {
        self.funcs.get(id as usize).ok_or(FuncError::Malformed(
            "a call of a function outside the table",
        ))
    }

    /// `e` with every nested call evaluated (against the current frame).
    fn resolve(&mut self, e: &Expr, depth: usize) -> Result<Expr, FuncError> {
        if !has_call(e) {
            return Ok(e.clone());
        }
        match e {
            Expr::Array(ArrayNode::Call { func, args, ty }) => {
                let mut vals = Vec::with_capacity(args.len());
                for a in args {
                    vals.push(self.eval_in(a, depth)?);
                }
                let r = self.run(*func, vals, depth + 1)?;
                Ok(Expr::Const(*ty, r))
            }
            other => other.try_map_children(&mut |c| self.resolve(c, depth)),
        }
    }

    fn eval_in(&mut self, e: &Expr, depth: usize) -> Result<BigUint, FuncError> {
        let r = self.resolve(e, depth)?;
        Ok(eval(&r, &self.asg)?)
    }

    fn run(&mut self, id: FuncId, args: Vec<BigUint>, depth: usize) -> Result<BigUint, FuncError> {
        let (n_params, ret, slots, name) = {
            let f = self.func(id)?;
            (f.n_params, f.ret, f.slots.clone(), f.name.clone())
        };
        if depth >= MAX_DEPTH {
            return Err(FuncError::TooDeep { func: name });
        }
        if args.len() != n_params {
            return Err(FuncError::Malformed(
                "a call with the wrong number of arguments",
            ));
        }
        let mut frame: Vec<BigUint> = vec![BigUint::zero(); slots.len()];
        for (k, a) in args.into_iter().enumerate() {
            frame[k] = a & mask(slots[k].width);
        }
        let saved = std::mem::replace(&mut self.asg.vars, frame);
        let body = self.func(id)?.body.clone();
        let flow = self.exec(&body, id, depth);
        let frame = std::mem::replace(&mut self.asg.vars, saved);
        flow?;
        Ok(frame[ret as usize].clone() & mask(slots[ret as usize].width))
    }

    fn tick(&mut self, id: FuncId) -> Result<(), FuncError> {
        self.steps += 1;
        if self.steps > MAX_STEPS {
            return Err(FuncError::StepLimit {
                func: self.func(id)?.name.clone(),
            });
        }
        Ok(())
    }

    fn exec(&mut self, body: &[Stmt], id: FuncId, depth: usize) -> Result<Flow, FuncError> {
        for s in body {
            self.tick(id)?;
            match s {
                Stmt::Assign(slot, e) => {
                    let v = self.eval_in(e, depth)?;
                    let w = self
                        .func(id)?
                        .slots
                        .get(*slot as usize)
                        .ok_or(FuncError::Malformed(
                            "an assignment to a slot outside the frame",
                        ))?
                        .width;
                    self.asg.vars[*slot as usize] = v & mask(w);
                }
                Stmt::If(c, t, e) => {
                    let taken = !self.eval_in(c, depth)?.is_zero();
                    let flow = self.exec(if taken { t } else { e }, id, depth)?;
                    if flow != Flow::Normal {
                        return Ok(flow);
                    }
                }
                Stmt::Loop {
                    cond,
                    body,
                    step,
                    test_first,
                } => {
                    let mut first = true;
                    loop {
                        self.tick(id)?;
                        if (*test_first || !first)
                            && let Some(c) = cond
                            && self.eval_in(c, depth)?.is_zero()
                        {
                            break;
                        }
                        first = false;
                        match self.exec(body, id, depth)? {
                            Flow::Break => break,
                            Flow::Return => return Ok(Flow::Return),
                            Flow::Normal | Flow::Continue => {}
                        }
                        if self.exec(step, id, depth)? == Flow::Return {
                            return Ok(Flow::Return);
                        }
                    }
                }
                Stmt::Break => return Ok(Flow::Break),
                Stmt::Continue => return Ok(Flow::Continue),
                Stmt::Return => return Ok(Flow::Return),
            }
        }
        Ok(Flow::Normal)
    }
}

/// Whether `e` holds a function call.
pub fn has_call(e: &Expr) -> bool {
    e.any_node(&mut |n| matches!(n, Expr::Array(ArrayNode::Call { .. })))
}

/// Calls function `id` of `funcs` with the argument values `args` (each below
/// `2^width` of its formal) and returns its result, reading the non-`rand`
/// variables the body uses from `states`.
pub fn call(
    funcs: &[Func],
    id: FuncId,
    args: &[BigUint],
    states: &[Option<BigUint>],
) -> Result<BigUint, FuncError> {
    let mut m = Machine {
        funcs,
        asg: Assignment {
            vars: Vec::new(),
            states: states.to_vec(),
        },
        steps: 0,
    };
    m.run(id, args.to_vec(), 0)
}

/// Whether `e` holds neither a random variable nor an array-level node: its
/// value is fixed.
fn is_ground(e: &Expr) -> bool {
    !e.any_node(&mut |n| matches!(n, Expr::Var(..) | Expr::Array(_)))
}

/// `e` with every call whose arguments are already fixed (no random variable,
/// no array-level node left in them) replaced by the constant it returns. A
/// call with a still-unknown argument stays, its own arguments folded as far as
/// they go.
pub fn fold_ground_calls(
    e: &Expr,
    funcs: &[Func],
    states: &[Option<BigUint>],
) -> Result<Expr, FuncError> {
    if !has_call(e) {
        return Ok(e.clone());
    }
    match e {
        Expr::Array(ArrayNode::Call { func, args, ty }) => {
            let args = args
                .iter()
                .map(|a| fold_ground_calls(a, funcs, states))
                .collect::<Result<Vec<_>, _>>()?;
            if args.iter().all(is_ground) {
                let asg = Assignment {
                    vars: Vec::new(),
                    states: states.to_vec(),
                };
                let vals = args
                    .iter()
                    .map(|a| eval(a, &asg))
                    .collect::<Result<Vec<_>, _>>()?;
                let r = call(funcs, *func, &vals, states)?;
                Ok(Expr::Const(*ty, r))
            } else {
                Ok(Expr::Array(ArrayNode::Call {
                    func: *func,
                    args,
                    ty: *ty,
                }))
            }
        }
        // Only the picked element is ever evaluated (a virtual call through a
        // handle holds a call per possible class; the others may read members the
        // object does not have), so the elements wait for the expansion.
        Expr::Array(ArrayNode::Pick {
            index,
            low,
            elems,
            ty,
        }) => Ok(Expr::Array(ArrayNode::Pick {
            index: Box::new(fold_ground_calls(index, funcs, states)?),
            low: *low,
            elems: elems.clone(),
            ty: *ty,
        })),
        other => other.try_map_children(&mut |c| fold_ground_calls(c, funcs, states)),
    }
}

#[cfg(test)]
pub(crate) mod tests {
    use super::*;
    use crate::constraints::ir::{BinOp, UnOp};

    fn u(w: u32) -> Ty {
        Ty::unsigned(w)
    }
    fn s32() -> Ty {
        Ty::signed(32)
    }
    fn var(i: u32, t: Ty) -> Expr {
        Expr::Var(i, t)
    }
    fn k(t: Ty, v: u64) -> Expr {
        Expr::constant(t, v)
    }
    fn bin(op: BinOp, a: Expr, b: Expr, t: Ty) -> Expr {
        Expr::Binary(op, Box::new(a), Box::new(b), t)
    }
    fn n(v: u64) -> BigUint {
        BigUint::from(v)
    }

    /// LRM 18.5.11's `count_ones`:
    /// `for (count_ones = 0; w != 0; w = w >> 1) count_ones += w & 1'b1;`
    pub(crate) fn count_ones() -> Func {
        // slots: 0 = w (10 bits), 1 = count_ones (32 bits)
        let w = var(0, u(10));
        let c = var(1, s32());
        Func {
            name: "count_ones".into(),
            slots: vec![u(10), s32()],
            n_params: 1,
            ret: 1,
            body: vec![
                Stmt::Assign(1, k(s32(), 0)),
                Stmt::Loop {
                    cond: Some(bin(BinOp::Ne, w.clone(), k(u(10), 0), Ty::BIT)),
                    body: vec![Stmt::Assign(
                        1,
                        bin(
                            BinOp::Add,
                            c.clone(),
                            Expr::Resize(
                                Box::new(bin(BinOp::And, w.clone(), k(u(10), 1), u(10))),
                                s32(),
                            ),
                            s32(),
                        ),
                    )],
                    step: vec![Stmt::Assign(
                        0,
                        bin(BinOp::Shr, w.clone(), k(u(32), 1), u(10)),
                    )],
                    test_first: true,
                },
            ],
        }
    }

    #[test]
    fn count_ones_counts_the_set_bits() {
        let f = [count_ones()];
        for v in [0u64, 1, 0b1011, 0x3ff, 0b10_0000_0001] {
            let r = call(&f, 0, &[n(v)], &[]).unwrap();
            assert_eq!(r, n(u64::from(v.count_ones())), "count_ones({v:#b})");
        }
    }

    #[test]
    fn a_runaway_loop_is_a_loud_error_not_a_hang() {
        let f = [Func {
            name: "spin".into(),
            slots: vec![s32()],
            n_params: 0,
            ret: 0,
            body: vec![Stmt::Loop {
                cond: None,
                body: Vec::new(),
                step: Vec::new(),
                test_first: true,
            }],
        }];
        assert!(matches!(
            call(&f, 0, &[], &[]),
            Err(FuncError::StepLimit { .. })
        ));
    }

    #[test]
    fn recursion_works_and_unbounded_recursion_is_an_error() {
        // fact(n) = n <= 1 ? 1 : n * fact(n - 1); slots: 0 = n, 1 = fact
        let rec = Expr::Array(ArrayNode::Call {
            func: 0,
            args: vec![bin(BinOp::Sub, var(0, s32()), k(s32(), 1), s32())],
            ty: s32(),
        });
        let fact = Func {
            name: "fact".into(),
            slots: vec![s32(), s32()],
            n_params: 1,
            ret: 1,
            body: vec![Stmt::If(
                bin(BinOp::Le, var(0, s32()), k(s32(), 1), Ty::BIT),
                vec![Stmt::Assign(1, k(s32(), 1)), Stmt::Return],
                vec![Stmt::Assign(1, bin(BinOp::Mul, var(0, s32()), rec, s32()))],
            )],
        };
        assert_eq!(
            call(std::slice::from_ref(&fact), 0, &[n(5)], &[]).unwrap(),
            n(120)
        );
        let endless = Func {
            body: vec![Stmt::Assign(
                1,
                Expr::Array(ArrayNode::Call {
                    func: 0,
                    args: vec![var(0, s32())],
                    ty: s32(),
                }),
            )],
            ..fact
        };
        assert!(matches!(
            call(&[endless], 0, &[n(1)], &[]),
            Err(FuncError::TooDeep { .. })
        ));
    }

    #[test]
    fn break_continue_and_do_while_follow_the_loop_rules() {
        // r = 0; do { i++; if (i == 2) continue; if (i == 5) break; r += i; } while (i < 100);
        // slots: 0 = i, 1 = r
        let i = var(0, s32());
        let r = var(1, s32());
        let inc = Stmt::Assign(0, bin(BinOp::Add, i.clone(), k(s32(), 1), s32()));
        let f = Func {
            name: "dw".into(),
            slots: vec![s32(), s32()],
            n_params: 0,
            ret: 1,
            body: vec![Stmt::Loop {
                cond: Some(bin(BinOp::Lt, i.clone(), k(s32(), 100), Ty::BIT)),
                body: vec![
                    inc,
                    Stmt::If(
                        bin(BinOp::Eq, i.clone(), k(s32(), 2), Ty::BIT),
                        vec![Stmt::Continue],
                        Vec::new(),
                    ),
                    Stmt::If(
                        bin(BinOp::Eq, i.clone(), k(s32(), 5), Ty::BIT),
                        vec![Stmt::Break],
                        Vec::new(),
                    ),
                    Stmt::Assign(1, bin(BinOp::Add, r.clone(), i.clone(), s32())),
                ],
                step: Vec::new(),
                test_first: false,
            }],
        };
        // i = 1 (r = 1), 2 (skipped), 3 (r = 4), 4 (r = 8), 5 (break).
        assert_eq!(call(&[f], 0, &[], &[]).unwrap(), n(8));
    }

    #[test]
    fn a_function_reads_state_and_an_unreadable_state_is_an_error() {
        // f(a) = a + state0
        let f = Func {
            name: "f".into(),
            slots: vec![s32(), s32()],
            n_params: 1,
            ret: 1,
            body: vec![Stmt::Assign(
                1,
                bin(BinOp::Add, var(0, s32()), Expr::State(0, s32()), s32()),
            )],
        };
        assert_eq!(
            call(std::slice::from_ref(&f), 0, &[n(2)], &[Some(n(40))]).unwrap(),
            n(42)
        );
        assert_eq!(
            call(&[f], 0, &[n(2)], &[None]),
            Err(FuncError::Eval(ConstraintEvalError::StateUnknown(0)))
        );
    }

    #[test]
    fn division_by_zero_inside_a_function_is_an_error() {
        let f = Func {
            name: "d".into(),
            slots: vec![s32(), s32()],
            n_params: 1,
            ret: 1,
            body: vec![Stmt::Assign(
                1,
                bin(BinOp::Div, k(s32(), 1), var(0, s32()), s32()),
            )],
        };
        assert_eq!(
            call(&[f], 0, &[n(0)], &[]),
            Err(FuncError::Eval(ConstraintEvalError::DivideByZero))
        );
    }

    #[test]
    fn only_calls_with_fixed_arguments_are_folded() {
        let f = [count_ones()];
        let ground = Expr::Array(ArrayNode::Call {
            func: 0,
            args: vec![k(u(10), 0b111)],
            ty: s32(),
        });
        let open = Expr::Array(ArrayNode::Call {
            func: 0,
            args: vec![var(0, u(10))],
            ty: s32(),
        });
        let e = bin(BinOp::Add, ground, open.clone(), s32());
        let folded = fold_ground_calls(&e, &f, &[]).unwrap();
        assert_eq!(folded, bin(BinOp::Add, k(s32(), 3), open, s32()));
        // A negation of a ground call folds under it too.
        let neg = Expr::Unary(
            UnOp::Neg,
            Box::new(Expr::Array(ArrayNode::Call {
                func: 0,
                args: vec![k(u(10), 1)],
                ty: s32(),
            })),
            s32(),
        );
        assert_eq!(
            fold_ground_calls(&neg, &f, &[]).unwrap(),
            Expr::Unary(UnOp::Neg, Box::new(k(s32(), 1)), s32())
        );
    }
}