spade_mir/
lib.rs

Help
1mod aliasing;
2mod assertion_codegen;
3pub mod codegen;
4pub mod diff;
5pub mod diff_printing;
6mod enum_util;
7pub mod eval;
8pub mod macros;
9pub mod passes;
10pub mod renaming;
11mod type_list;
12pub mod types;
13pub mod unit_name;
14pub mod verilator_wrapper;
15mod verilog;
16mod wal;
17
18use derive_where::derive_where;
19use itertools::Itertools;
20use num::{BigInt, BigUint};
21use renaming::VerilogNameSource;
22use serde::{Deserialize, Serialize};
23use spade_common::id_tracker::ExprID;
24use types::Type;
25
26use spade_common::location_info::{Loc, WithLocation};
27use spade_common::name::NameID;
28use spade_common::num_ext::InfallibleToBigInt;
29
30pub use unit_name::UnitName;
31
32#[derive(Clone, PartialEq, Debug, Eq, Hash)]
33pub enum ConstantValue {
34    Int(BigInt),
35    Bool(bool),
36    HighImp,
37}
38
39impl ConstantValue {
40    pub fn int(val: i32) -> Self {
41        Self::Int(val.to_bigint())
42    }
43}
44
45impl std::fmt::Display for ConstantValue {
46    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
47        match self {
48            ConstantValue::Int(val) => write!(f, "{val}"),
49            ConstantValue::Bool(val) => write!(f, "{val}"),
50            ConstantValue::HighImp => write!(f, "HIGHIMP"),
51        }
52    }
53}
54
55#[derive(Clone, PartialEq, Debug, Hash, Eq, serde::Serialize, serde::Deserialize)]
56pub enum ValueNameSource {
57    Name(NameID),
58    Expr(ExprID),
59}
60
61impl From<NameID> for ValueNameSource {
62    fn from(value: NameID) -> Self {
63        (&value).into()
64    }
65}
66
67impl From<&NameID> for ValueNameSource {
68    fn from(value: &NameID) -> Self {
69        Self::Name(value.clone())
70    }
71}
72
73impl From<&ValueName> for ValueNameSource {
74    fn from(value: &ValueName) -> Self {
75        match value {
76            ValueName::Named(_, _, source) => source.clone(),
77            ValueName::Expr(id) => Self::Expr(*id),
78        }
79    }
80}
81
82/// A name of a value. Can either come from the NameID of the underlying
83/// variable, or the id of the underlying expression
84#[derive(Clone, Debug, Serialize, Deserialize)]
85#[derive_where(Hash, Eq, PartialEq)]
86pub enum ValueName {
87    /// A named value in the code with with an index to make that name locally unique
88    Named(
89        // ID of the name in the generated verilog
90        u64,
91        // Human readable name in the generated verilog. If this is not unique
92        // to the current module, the id will be appended
93        String,
94        // The original name ID from which this name originates
95        // NOTE: Not checked by MIR diff because it is only a metadata field
96        #[derive_where(skip)] ValueNameSource,
97    ),
98    // FIXME: Consider renaming this since it's now used for both patterns and expressions
99    /// An un-named expression. In the resulting verilog, this is called _e_$id
100    Expr(ExprID),
101}
102
103impl WithLocation for ValueName {}
104
105impl ValueName {
106    pub fn verilog_name_source_fwd(&self) -> VerilogNameSource {
107        match self {
108            ValueName::Named(_, _, ValueNameSource::Name(name_id)) => {
109                VerilogNameSource::ForwardName(name_id.clone())
110            }
111            ValueName::Named(_, _, ValueNameSource::Expr(id)) | ValueName::Expr(id) => {
112                VerilogNameSource::ForwardExpr(*id)
113            }
114        }
115    }
116
117    pub fn verilog_name_source_back(&self) -> VerilogNameSource {
118        match self {
119            ValueName::Named(_, _, ValueNameSource::Name(name_id)) => {
120                VerilogNameSource::BackwardName(name_id.clone())
121            }
122            ValueName::Named(_, _, ValueNameSource::Expr(id)) | ValueName::Expr(id) => {
123                VerilogNameSource::BackwardExpr(*id)
124            }
125        }
126    }
127
128    pub fn _test_named(id: u64, name: String) -> Self {
129        use spade_common::name::Path;
130
131        Self::Named(
132            id,
133            name.clone(),
134            NameID(id, Path::from_strs(&[name.as_str()])).into(),
135        )
136    }
137}
138
139impl std::fmt::Display for ValueName {
140    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
141        match self {
142            ValueName::Named(id, s, _) => {
143                // The first identifier of each name has the exact same name as the underlying
144                // spade variable.
145                // However, Vivado has a bug where it treats an escaped `new` as the `new` keyword
146                // from `SystemVerilog`, so we need to special case new here
147                if *id == 0 && s != "new" {
148                    write!(f, "{s}")
149                } else {
150                    write!(f, "{s}_n{id}")
151                }
152            }
153            ValueName::Expr(id) => write!(f, "e{}", id.0),
154        }
155    }
156}
157
158#[derive(Clone, PartialEq, Eq, Hash, Debug)]
159pub struct ParamName {
160    pub name: String,
161    pub no_mangle: Option<Loc<()>>,
162}
163
164#[derive_where(PartialEq, Eq, Hash)]
165#[derive(Clone, Debug)]
166pub enum Operator {
167    // Binary arithmetic operators
168    Add,
169    UnsignedAdd,
170    Sub,
171    UnsignedSub,
172    Mul,
173    UnsignedMul,
174    Div,
175    UnsignedDiv,
176    Mod,
177    UnsignedMod,
178    Eq,
179    NotEq,
180    Gt,
181    UnsignedGt,
182    Lt,
183    UnsignedLt,
184    Ge,
185    UnsignedGe,
186    Le,
187    UnsignedLe,
188    LeftShift,
189    RightShift,
190    ArithmeticRightShift,
191    LogicalAnd,
192    LogicalOr,
193    LogicalXor,
194    LogicalNot,
195    BitwiseAnd,
196    BitwiseOr,
197    BitwiseXor,
198    ReduceAnd,
199    ReduceOr,
200    ReduceXor,
201    USub,
202    Not,
203    ReadPort,
204    BitwiseNot,
205    // Divide op[0] by 2**op[1] rounding towards 0
206    DivPow2,
207    /// Sign extend the first operand with the provided amount of extra bits
208    SignExtend {
209        extra_bits: BigUint,
210        operand_size: BigUint,
211    },
212    ZeroExtend {
213        extra_bits: BigUint,
214    },
215    /// Truncate the first operand to fit the size of the target operand.
216    /// Should not be used on operands which are smaller than the target
217    Truncate,
218    /// Concatenate the bits of all input operands
219    Concat,
220    /// Select [1] if [0] else [2]
221    Select,
222    /// Corresponds to a match statement. If value [0] is true, select [1], if [2] holds, select
223    /// [3] and so on. Values are priorotized in order, i.e. if both [0] and [2] hold, [1] is
224    /// selected
225    // NOTE: We may want to add a MatchUnique for cases where we can guarantee uniqueness,
226    // typically match statements with no wildcards
227    Match,
228    /// Construct an array from the operand expressions
229    ConstructArray,
230    /// Create a mutable array which is modified on the rising edge of the first argument.
231    /// the second argument is an array of (write enable, write address, write data) tuples
232    /// which update the array.
233    DeclClockedMemory {
234        write_ports: BigUint,
235        /// Width of the write address
236        addr_w: BigUint,
237        /// Number of elements in the array
238        inner_w: BigUint,
239        /// Number of elements in the array
240        elems: BigUint,
241        /// Initial values for the memory. Must be const evaluatable
242        initial: Option<Vec<Vec<Statement>>>,
243    },
244    /// Index an array with elements of the specified size
245    IndexArray {
246        array_size: BigUint,
247    },
248    IndexMemory,
249    /// Indexes an array to extract a range of elements
250    RangeIndexArray {
251        start: BigUint,
252        end_exclusive: BigUint,
253        in_array_size: BigUint,
254    },
255    /// Compiles to verilog [end_exclusive:start]. Supports single bit indexing, (when
256    /// end_exclusive == start + 1, in which case it compiles to [start]
257    RangeIndexBits {
258        start: BigUint,
259        end_exclusive: BigUint,
260    },
261    /// Construct a tuple from all the operand expressions
262    ConstructTuple,
263    /// Construct the nth enum variant with the operand expressions as the payload
264    ConstructEnum {
265        variant: usize,
266        variant_count: usize,
267    },
268    /// 1 if the input is the specified enum variant
269    IsEnumVariant {
270        variant: usize,
271        enum_type: Type,
272    },
273    /// Get the `member_index`th member of the `variant`th variant.
274    EnumMember {
275        enum_type: Type,
276        variant: usize,
277        member_index: usize,
278    },
279    /// Get the `.0`th element of a tuple or a type of the same representation as a tuple, for
280    /// example a Struct. The types of the elements are specified
281    /// in the second argument
282    IndexTuple(u64, Vec<Type>),
283
284    /// Inverts the direction of all bits of a port. I.e. the forward ports
285    /// become backward ports. This is only valid when converting from T to ~T
286    FlipPort,
287
288    /// Given a struct or tuple consisting of mut and non-mut wires, create a new
289    /// struct or tuple with the non-mut copies of the mut wires
290    ///
291    /// As an example `(&mut T1, T2, &mut T3)` becomes `(T1, T3)`
292    // NOTE: For now this variant is a bit of a hack used during wal_trace_lowering
293    // A saner implementation that also solves #252 would be nice
294    // In particular, a dedicated `ReadMutTuple` might be useful
295    // lifeguard spade#252
296    ReadMutWires,
297
298    /// Instantiation of another module with the specified name. The operands are passed
299    /// by name to the entity. The operand name mapping is decided by the `argument_names` field of
300    /// this variant. The first operand gets mapped to the first argument name, and so on.
301    /// The target module can only have a single output which must be the last argument.
302    /// The location of the instantiation is optional but can be passed to improve
303    /// critical path report readability
304    Instance {
305        name: UnitName,
306        params: Vec<(String, BigUint)>,
307        /// The names of the arguments in the same order as the operands.
308        /// For instance, if the `i`th argument name is "foo" and the `i`th [`Binding`] is
309        /// `my_port`, the verilog module will be instantiated with `.foo(my_port)`.
310        argument_names: Vec<ParamName>,
311        #[derive_where(skip)]
312        loc: Option<Loc<()>>,
313    },
314    /// Alias another named value
315    Alias,
316    /// Define a variable for the value but don't do anything with it. Useful for creating ports
317    Nop,
318}
319
320impl Operator {
321    pub fn simple_instance(name: UnitName, argument_names: Vec<&str>) -> Self {
322        Self::Instance {
323            name,
324            params: Vec::default(),
325            argument_names: argument_names
326                .iter()
327                .map(|p| ParamName {
328                    name: p.to_string(),
329                    no_mangle: None,
330                })
331                .collect(),
332            loc: None,
333        }
334    }
335}
336
337impl std::fmt::Display for Operator {
338    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
339        match self {
340            Operator::Add => write!(f, "Add"),
341            Operator::UnsignedAdd => write!(f, "UnsignedAdd"),
342            Operator::Sub => write!(f, "Sub"),
343            Operator::UnsignedSub => write!(f, "UnsignedSub"),
344            Operator::Mul => write!(f, "Mul"),
345            Operator::UnsignedMul => write!(f, "UnsignedMul"),
346            Operator::Div => write!(f, "Div"),
347            Operator::UnsignedDiv => write!(f, "UnsignedDiv"),
348            Operator::Mod => write!(f, "Mod"),
349            Operator::UnsignedMod => write!(f, "UnsignedMod"),
350            Operator::Eq => write!(f, "Eq"),
351            Operator::NotEq => write!(f, "NotEq"),
352            Operator::Gt => write!(f, "Gt"),
353            Operator::UnsignedGt => write!(f, "UnsignedGt"),
354            Operator::Lt => write!(f, "Lt"),
355            Operator::UnsignedLt => write!(f, "UnsignedLt"),
356            Operator::Ge => write!(f, "Ge"),
357            Operator::UnsignedGe => write!(f, "UnsignedGe"),
358            Operator::Le => write!(f, "Le"),
359            Operator::UnsignedLe => write!(f, "UnsignedLe"),
360            Operator::RightShift => write!(f, "RightShift"),
361            Operator::ArithmeticRightShift => write!(f, "ArithmeticRightShift"),
362            Operator::LogicalAnd => write!(f, "LogicalAnd"),
363            Operator::LogicalOr => write!(f, "LogicalOr"),
364            Operator::LogicalXor => write!(f, "LogicalXor"),
365            Operator::LogicalNot => write!(f, "LogicalNot"),
366            Operator::BitwiseAnd => write!(f, "BitwiseAnd"),
367            Operator::BitwiseOr => write!(f, "BitwiseOr"),
368            Operator::BitwiseNot => write!(f, "BitwiseNot"),
369            Operator::BitwiseXor => write!(f, "BitwiseXor"),
370            Operator::ReduceAnd => write!(f, "ReduceAnd"),
371            Operator::ReduceOr => write!(f, "ReduceOr"),
372            Operator::ReduceXor => write!(f, "ReduceXor"),
373            Operator::USub => write!(f, "USub"),
374            Operator::Not => write!(f, "Not"),
375            Operator::Select => write!(f, "Select"),
376            Operator::Match => write!(f, "Match"),
377            Operator::LeftShift => write!(f, "LeftShift"),
378            Operator::DivPow2 => write!(f, "DivPow2"),
379            Operator::SignExtend {
380                extra_bits,
381                operand_size,
382            } => write!(f, "SignExtend({extra_bits}, {operand_size})"),
383            Operator::ZeroExtend { extra_bits } => write!(f, "ZeroExtend({extra_bits})"),
384            Operator::Truncate => write!(f, "Truncate"),
385            Operator::Concat => write!(f, "Concat"),
386            Operator::ConstructEnum {
387                variant,
388                variant_count,
389            } => write!(f, "ConstructEnum({}, {})", variant, variant_count),
390            Operator::IsEnumVariant {
391                variant,
392                enum_type: _,
393            } => write!(f, "IsEnumVariant({})", variant),
394            Operator::EnumMember {
395                variant,
396                member_index,
397                enum_type: _,
398            } => write!(f, "EnumMember({} {})", variant, member_index),
399            Operator::ConstructTuple => write!(f, "ConstructTuple"),
400            Operator::ConstructArray => write!(f, "ConstructArray"),
401            Operator::DeclClockedMemory {
402                write_ports,
403                addr_w,
404                inner_w,
405                elems,
406                initial,
407            } => write!(
408                f,
409                "DeclClockedMemory({write_ports}, {addr_w}, {inner_w}, {elems}{})",
410                if let Some(values) = initial {
411                    format!(
412                        ", [{}]",
413                        values
414                            .iter()
415                            .map(|v| format!("[{}]", v.iter().map(|v| format!("{v}")).join(", ")))
416                            .join(", ")
417                    )
418                } else {
419                    String::new()
420                }
421            ),
422            Operator::IndexArray { array_size } => write!(f, "IndexArray({array_size})"),
423            Operator::IndexTuple(idx, ty) => write!(f, "IndexTuple({}, {ty:?})", idx),
424            Operator::RangeIndexArray {
425                start,
426                end_exclusive: end,
427                in_array_size: _,
428            } => write!(f, "RangeIndexArray({start}, {end})"),
429            Operator::RangeIndexBits {
430                start,
431                end_exclusive: end,
432            } => write!(f, "RangeIndexBits({start}, {end})"),
433            Operator::IndexMemory => write!(f, "IndexMemory"),
434            Operator::Instance { name, .. } => write!(f, "Instance({})", name.as_verilog()),
435            Operator::Alias => write!(f, "Alias"),
436            Operator::FlipPort => write!(f, "FlipPort"),
437            Operator::ReadMutWires => write!(f, "ReadMutWires"),
438            Operator::Nop => write!(f, "Nop"),
439            Operator::ReadPort => write!(f, "ReadPort"),
440        }
441    }
442}
443
444#[derive(Clone, PartialEq, Eq, Hash, Debug)]
445pub struct Binding {
446    pub name: ValueName,
447    pub operator: Operator,
448    pub operands: Vec<ValueName>,
449    pub ty: Type,
450    pub loc: Option<Loc<()>>,
451}
452
453impl std::fmt::Display for Binding {
454    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
455        let Binding {
456            name,
457            operator,
458            operands,
459            ty,
460            loc: _,
461        } = self;
462        write!(
463            f,
464            "let {name}: {ty} = {operator}({})",
465            operands.iter().map(|op| format!("{op}")).join(", ")
466        )
467    }
468}
469
470#[derive(Clone, PartialEq, Eq, Hash, Debug)]
471pub struct Register {
472    pub name: ValueName,
473    pub ty: Type,
474    pub clock: ValueName,
475    pub reset: Option<(ValueName, ValueName)>,
476    pub initial: Option<Vec<Statement>>,
477    pub value: ValueName,
478    pub loc: Option<Loc<()>>,
479    /// True if this register corresponds to an fsm with the specified ValueName
480    /// as the actual state
481    pub traced: Option<ValueName>,
482}
483
484impl std::fmt::Display for Register {
485    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
486        let Register {
487            name,
488            ty,
489            clock,
490            reset,
491            initial,
492            value,
493            loc: _,
494            traced: _,
495        } = self;
496
497        let reset = reset
498            .as_ref()
499            .map(|(trig, val)| format!("({trig}, {val})"))
500            .unwrap_or_else(String::new);
501
502        let initial = initial
503            .as_ref()
504            .map(|i| format!("initial({})", i.iter().map(|s| format!("{s}")).join("; ")))
505            .unwrap_or_else(String::new);
506
507        write!(f, "reg({clock}) {name}: {ty}{reset}{initial} = {value}")
508    }
509}
510
511#[derive(Clone, PartialEq, Eq, Hash, Debug)]
512pub enum Statement {
513    Binding(Binding),
514    Register(Register),
515    /// A constant expression with the specified ID and value
516    Constant(ExprID, Type, ConstantValue),
517    Assert(Loc<ValueName>),
518    Set {
519        target: Loc<ValueName>,
520        value: Loc<ValueName>,
521    },
522    /// This is a tracing signal as part of the value `name`. It is used for
523    /// both individual fields if `#[wal_traceable]` and `#[wal_trace]` is used,
524    /// and whole signals if `#[wal_suffix]` is used
525    /// I.e. the result of
526    /// ```
527    /// #[wal_traceable(suffix) struct T {a: A, b: B}
528    ///
529    /// let x: T = ...`
530    /// ```
531    ///
532    /// Will be
533    /// (e(0); IndexStruct(0); x)
534    /// (wal_trace {name: x, val: e(0), suffix: _a_suffix, ty: A}
535    /// (e(1); IndexStruct(1); x)
536    /// (wal_trace {name: x, val: e(0), suffix: _a_suffix, ty: A}
537    WalTrace {
538        name: ValueName,
539        val: ValueName,
540        suffix: String,
541        ty: Type,
542    },
543}
544
545impl std::fmt::Display for Statement {
546    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
547        match self {
548            Statement::Binding(b) => write!(f, "{b}"),
549            Statement::Register(r) => write!(f, "{r}"),
550            Statement::Constant(id, ty, val) => write!(f, "const e{id}: {ty} = {val}", id = id.0),
551            Statement::Assert(val) => write!(f, "assert {val}"),
552            Statement::Set { target, value } => write!(f, "set {target} = {value}"),
553            Statement::WalTrace {
554                name,
555                val,
556                suffix,
557                ty: _,
558            } => write!(f, "wal_trace({name}, {val}, {suffix})"),
559        }
560    }
561}
562
563#[derive(Clone, PartialEq, Debug)]
564pub struct MirInput {
565    pub name: String,
566    pub val_name: ValueName,
567    pub ty: Type,
568    pub no_mangle: Option<Loc<()>>,
569}
570#[derive(Clone, PartialEq, Debug)]
571pub struct Entity {
572    /// The name of the module
573    pub name: UnitName,
574    /// A module input which is called `.1` externally and `.2` internally in the module
575    pub inputs: Vec<MirInput>,
576    pub output: ValueName,
577    pub output_type: Type,
578    pub statements: Vec<Statement>,
579}
580
581impl std::fmt::Display for Entity {
582    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
583        let Entity {
584            name,
585            inputs,
586            output,
587            output_type,
588            statements,
589        } = self;
590
591        let inputs = inputs
592            .iter()
593            .map(
594                |MirInput {
595                     name,
596                     val_name,
597                     ty,
598                     no_mangle,
599                 }| {
600                    format!(
601                        "({}{name}, {val_name}, {ty})",
602                        no_mangle.map(|_| "#[no_mangle]").unwrap_or("")
603                    )
604                },
605            )
606            .join(", ");
607
608        let statements = statements.iter().map(|s| format!("\t{s}\n")).join("");
609
610        writeln!(
611            f,
612            "entity {name}({inputs}) -> {output_type} {{",
613            name = name.as_verilog()
614        )?;
615        write!(f, "{statements}")?;
616        write!(f, "}} => {output}")
617    }
618}
spade_mir/lib.rs

spade_mir/
lib.rs
