Enum LutLang 

pub enum LutLang {
    Const(bool),
    Program(u64),
    DC,
    Var(Symbol),
    Nor([Id; 2]),
    Mux([Id; 3]),
    And([Id; 2]),
    Xor([Id; 2]),
    Not([Id; 1]),
    Lut(Box<[Id]>),
    Bus(Box<[Id]>),
    Reg([Id; 4]),
    Arg([Id; 1]),
    Cycle([Id; 1]),
}

Definitions of e-node types. Programs are the only node type that is not a net/signal.

Variants

Const(bool)

Program(u64)

DC

Var(Symbol)

Nor([Id; 2])

Mux([Id; 3])

And([Id; 2])

Xor([Id; 2])

Not([Id; 1])

Lut(Box<[Id]>)

Bus(Box<[Id]>)

Reg([Id; 4])

Arg([Id; 1])

Cycle([Id; 1])

Implementations

impl LutLang

pub const MAX_LUT_SIZE: usize = 6

Maximum size allowed for a LUT. This cannot be made larger due to us using u64 to represent LUTs. FPGAs generally do not support greater than 6-LUTs so this limit should hopefully be sufficient forever.

pub fn verify_rec(&self, expr: &RecExpr<Self>) -> Result<(), String>

Recursively verify the grammar of a LutLang expression expr rooted at self

pub fn get_program(&self, expr: &RecExpr<Self>) -> Result<u64, String>

Extract the program from a LutLang::Lut contained in expression expr

pub fn get_program_in_egraph( &self, egraph: &EGraph<LutLang, LutAnalysis>, ) -> Result<u64, String>

Extract the program from a LutLang::Lut contained in egraph

pub fn get_operand_classes( &self, _egraph: &EGraph<LutLang, LutAnalysis>, ) -> Result<Vec<Id>, String>

Extract the operand class ids from a LutLang::Lut contained in egraph This filters out unwanted leaf nodes, like Programs.

pub fn get_lut_size(&self) -> Result<usize, String>

Returns the fan-in of a LutLang::Lut

pub fn eval( expr: &RecExpr<Self>, inputs: &HashMap<String, bool>, ) -> Result<BitVec, String>

This funcion evaluates the expr as combinational logic under given inputs

pub fn deep_equals(&self, other: &Self, expr: &RecExpr<Self>) -> bool

Since variables/leaves can be duplicated in expressions, we sometimes need to do deep checks for equality. This function returns true if the two nodes with children contained in expr are equal.

pub fn func_equiv(expr: &RecExpr<Self>, other: &RecExpr<Self>) -> Check

Given two expressions and a set of input values, this funcion returns true if they represent the same combinational logic

pub fn get_prim_name(&self) -> Option<String>

Returns the Verilog primitive name for a node type

Trait Implementations

impl Analysis<LutLang> for LutAnalysis

type Data = LutAnalysisData

The per-EClass data for this analysis.

fn merge(&mut self, to: &mut Self::Data, from: Self::Data) -> DidMerge

Defines how to merge two Datas when their containing EClasses merge.

fn make( egraph: &mut EGraph<LutLang, Self>, enode: &LutLang, _id: Id, ) -> Self::Data

Makes a new Analysis data for a given e-node that will go into the given e-class.

fn remake(egraph: &mut EGraph<L, Self>, enode: &L, id: Id) -> Self::Data

Same as Analysis::make, but called during rebuilding.

fn pre_union( egraph: &EGraph<L, Self>, id1: Id, id2: Id, justification: &Option<Justification>, )

An optional hook that allows inspection before a union occurs. When explanations are enabled, it gives two ids that represent the two particular terms being unioned, not the canonical ids for the two eclasses. It also gives a justification for the union when explanations are enabled.

fn modify(egraph: &mut EGraph<L, Self>, id: Id)

A hook that allows the modification of the EGraph.

fn allow_ematching_cycles(&self) -> bool

Whether or not e-matching should allow finding cycles.

impl Applier<LutLang, LutAnalysis> for CombineAlikeInputs

fn apply_one( &self, egraph: &mut EGraph<LutLang, LutAnalysis>, eclass: Id, subst: &Subst, searcher_ast: Option<&PatternAst<LutLang>>, rule_name: Symbol, ) -> Vec<Id>

Apply a single substitution.

fn apply_matches( &self, egraph: &mut EGraph<L, N>, matches: &[SearchMatches<'_, L>], rule_name: GlobalSymbol, ) -> Vec<Id>

Apply many substitutions.

fn get_pattern_ast(&self) -> Option<&RecExpr<ENodeOrVar<L>>>

For patterns, get the ast directly as a reference.

fn vars(&self) -> Vec<Var>

Returns a list of variables that this Applier assumes are bound.

impl Applier<LutLang, LutAnalysis> for FuseCut

fn apply_one( &self, egraph: &mut EGraph<LutLang, LutAnalysis>, eclass: Id, subst: &Subst, searcher_ast: Option<&PatternAst<LutLang>>, rule_name: Symbol, ) -> Vec<Id>

Apply a single substitution.

fn apply_matches( &self, egraph: &mut EGraph<L, N>, matches: &[SearchMatches<'_, L>], rule_name: GlobalSymbol, ) -> Vec<Id>

Apply many substitutions.

fn get_pattern_ast(&self) -> Option<&RecExpr<ENodeOrVar<L>>>

For patterns, get the ast directly as a reference.

fn vars(&self) -> Vec<Var>

Returns a list of variables that this Applier assumes are bound.

impl Applier<LutLang, LutAnalysis> for PermuteInput

fn apply_one( &self, egraph: &mut EGraph<LutLang, LutAnalysis>, eclass: Id, subst: &Subst, searcher_ast: Option<&PatternAst<LutLang>>, rule_name: Symbol, ) -> Vec<Id>

Apply a single substitution.

fn apply_matches( &self, egraph: &mut EGraph<L, N>, matches: &[SearchMatches<'_, L>], rule_name: GlobalSymbol, ) -> Vec<Id>

Apply many substitutions.

fn get_pattern_ast(&self) -> Option<&RecExpr<ENodeOrVar<L>>>

For patterns, get the ast directly as a reference.

fn vars(&self) -> Vec<Var>

Returns a list of variables that this Applier assumes are bound.

impl Applier<LutLang, LutAnalysis> for ShannonCondense

fn apply_one( &self, egraph: &mut EGraph<LutLang, LutAnalysis>, eclass: Id, subst: &Subst, searcher_ast: Option<&PatternAst<LutLang>>, rule_name: Symbol, ) -> Vec<Id>

Apply a single substitution.

fn apply_matches( &self, egraph: &mut EGraph<L, N>, matches: &[SearchMatches<'_, L>], rule_name: GlobalSymbol, ) -> Vec<Id>

Apply many substitutions.

fn get_pattern_ast(&self) -> Option<&RecExpr<ENodeOrVar<L>>>

For patterns, get the ast directly as a reference.

fn vars(&self) -> Vec<Var>

Returns a list of variables that this Applier assumes are bound.

impl Applier<LutLang, LutAnalysis> for ShannonExpand

Available on crate feature dyn_decomp only.

fn apply_one( &self, egraph: &mut EGraph<LutLang, LutAnalysis>, eclass: Id, subst: &Subst, searcher_ast: Option<&PatternAst<LutLang>>, rule_name: Symbol, ) -> Vec<Id>

Apply a single substitution.

fn apply_matches( &self, egraph: &mut EGraph<L, N>, matches: &[SearchMatches<'_, L>], rule_name: GlobalSymbol, ) -> Vec<Id>

Apply many substitutions.

fn get_pattern_ast(&self) -> Option<&RecExpr<ENodeOrVar<L>>>

For patterns, get the ast directly as a reference.

fn vars(&self) -> Vec<Var>

Returns a list of variables that this Applier assumes are bound.

impl Canonical for LutLang

fn expr_is_canonical(expr: &RecExpr<Self>) -> bool

Returns true if the expression is canonical.

fn canonicalize_expr(expr: RecExpr<Self>) -> RecExpr<Self>

Returns a canonicalization of the expression.

fn verify_expr(expr: &RecExpr<Self>) -> Result<(), String>

Verify that the expression does not have any extra syntax errors.

impl CircuitLang for LutLang

fn var(sym: Symbol) -> Self

Returns a fresh variable with name sym.

fn bus(ids: impl Iterator<Item = Id>) -> Self

Capture multiple expressions in a single node

fn int(x: u64) -> Option<Self>

Returns a node that stores a constant integer parameter if the Lang supports it

fn is_bus(&self) -> bool

Returns true is the node is a bus

fn is_lut(&self) -> bool

Returns true is the node is a lookup table

fn get_int(&self) -> Option<u64>

Returns an integer if the node stores one

fn get_var(&self) -> Option<Symbol>

Returns the symbol of the node, if is a variable

impl Clone for LutLang

fn clone(&self) -> LutLang

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<A, B> CostFunction<LutLang> for ConjunctiveCostFn<A, B>

where A: CostFunction<LutLang, Cost = i64>, B: CostFunction<LutLang, Cost = i64>,

type Cost = i64

The Cost type. It only requires PartialOrd so you can use floating point types, but failed comparisons (NaNs) will result in a panic.

fn cost<C>(&mut self, enode: &LutLang, costs: C) -> Self::Cost

where C: FnMut(Id) -> Self::Cost,

Calculates the cost of an enode whose children are Costs.

fn cost_rec(&mut self, expr: &RecExpr<L>) -> Self::Cost

Calculates the total cost of a RecExpr.

impl CostFunction<LutLang> for DepthCostFn

type Cost = i64

The Cost type. It only requires PartialOrd so you can use floating point types, but failed comparisons (NaNs) will result in a panic.

fn cost<C>(&mut self, enode: &LutLang, costs: C) -> Self::Cost

where C: FnMut(Id) -> Self::Cost,

Calculates the cost of an enode whose children are Costs.

fn cost_rec(&mut self, expr: &RecExpr<L>) -> Self::Cost

Calculates the total cost of a RecExpr.

impl CostFunction<LutLang> for GateCostFn

type Cost = u64

The Cost type. It only requires PartialOrd so you can use floating point types, but failed comparisons (NaNs) will result in a panic.

fn cost<C>(&mut self, enode: &LutLang, costs: C) -> Self::Cost

where C: FnMut(Id) -> Self::Cost,

Calculates the cost of an enode whose children are Costs.

fn cost_rec(&mut self, expr: &RecExpr<L>) -> Self::Cost

Calculates the total cost of a RecExpr.

impl CostFunction<LutLang> for KLUTCostFn

type Cost = u64

The Cost type. It only requires PartialOrd so you can use floating point types, but failed comparisons (NaNs) will result in a panic.

fn cost<C>(&mut self, enode: &LutLang, costs: C) -> Self::Cost

where C: FnMut(Id) -> Self::Cost,

Calculates the cost of an enode whose children are Costs.

fn cost_rec(&mut self, expr: &RecExpr<L>) -> Self::Cost

Calculates the total cost of a RecExpr.

impl Debug for LutLang

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Display for LutLang

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl EquivCheck for LutLang

fn check_expr(expr: &RecExpr<Self>, other: &RecExpr<Self>) -> Check

Check if expr and other are equivalent.

impl Explanable for LutLang

fn get_explanations<A>( expr: &RecExpr<Self>, other: &RecExpr<Self>, runner: &mut Runner<Self, A>, ) -> Result<Vec<Explanation<Self>>, String>

where A: Analysis<Self>,

Get a list of explanations for the relevant sub-terms in expr and other using the egraph in runnner.

impl Extractable for LutLang

fn depth_cost_fn() -> impl CostFunction<Self, Cost = i64>

Returns the depth cost function for the language.

fn cell_cost_with_reg_weight_fn( cut_size: usize, w: u64, ) -> impl CostFunction<Self>

Returns the area cost function for the language, only selecting cells with fewer than cut_size inputs. Additionally, registers have a parameterized weight w.

fn exact_area_cost_fn() -> impl CostFunction<Self>

Returns the cost function using real cell areas.

fn filter_cost_fn(set: HashSet<String>) -> impl CostFunction<Self>

Returns a cost function used for extracting only certain types nodes.

fn cell_cost_fn(cut_size: usize) -> impl CostFunction<Self>

Returns the area cost function for the language, only selecting cells with fewer than cut_size inputs. In this case, registers have weight 1.

impl FromOp for LutLang

type Error = FromOpError

The error type returned by from_op if its arguments do not represent a valid e-node.

fn from_op(op: &str, children: Vec<Id>) -> Result<Self, Self::Error>

Parse an e-node with operator op and children children.

impl Hash for LutLang

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl Language for LutLang

type Discriminant = Discriminant<LutLang>

Type representing the cases of this language.

fn discriminant(&self) -> Self::Discriminant

Return the Discriminant of this node.

fn matches(&self, other: &Self) -> bool

Returns true if this enode matches another enode. This should only consider the operator and the arity, not the children Ids.

fn children(&self) -> &[Id]

Returns the children of this e-node.

fn children_mut(&mut self) -> &mut [Id]

Returns a mutable slice of the children of this e-node.

fn for_each<F>(&self, f: F)

where F: FnMut(Id),

Runs a given function on each child Id.

fn for_each_mut<F>(&mut self, f: F)

where F: FnMut(&mut Id),

Runs a given function on each child Id, allowing mutation of that Id.

fn try_for_each<E, F>(&self, f: F) -> Result<(), E>

where F: FnMut(Id) -> Result<(), E>,

Runs a falliable function on each child, stopping if the function returns an error.

fn len(&self) -> usize

Returns the number of the children this enode has.

fn is_leaf(&self) -> bool

Returns true if this enode has no children.

fn update_children<F>(&mut self, f: F)

where F: FnMut(Id) -> Id,

Runs a given function to replace the children.

fn map_children<F>(self, f: F) -> Self

where F: FnMut(Id) -> Id,

Creates a new enode with children determined by the given function.

fn fold<F, T>(&self, init: T, f: F) -> T

where F: FnMut(T, Id) -> T,

Folds over the children, given an initial accumulator.

fn all<F>(&self, f: F) -> bool

where F: FnMut(Id) -> bool,

Returns true if the predicate is true on all children. Does not short circuit.

fn any<F>(&self, f: F) -> bool

where F: FnMut(Id) -> bool,

Returns true if the predicate is true on any children. Does not short circuit.

fn join_recexprs<F, Expr>(&self, child_recexpr: F) -> RecExpr<Self>

where F: FnMut(Id) -> Expr, Expr: AsRef<[Self]>,

Make a RecExpr by mapping this enodes children to other RecExprs.

fn build_recexpr<F>(&self, get_node: F) -> RecExpr<Self>

where F: FnMut(Id) -> Self,

Build a RecExpr from an e-node.

fn try_build_recexpr<F, Err>(&self, get_node: F) -> Result<RecExpr<Self>, Err>

where F: FnMut(Id) -> Result<Self, Err>,

Same as Language::build_recexpr, but fallible.

impl LogicCell<PrimitiveCell> for LutLang

fn get_cell(&self, params: &[(Identifier, Parameter)]) -> Option<PrimitiveCell>

Returns the instantiable cell type associated with this logic node

impl LogicFunc<LutLang> for PrimitiveCell

fn get_logic_func(&self, ind: usize, children: &[Id]) -> Option<LutLang>

Get the logic function/variant associated with the output at position ind. The children IDs are set to children.

impl Ord for LutLang

fn cmp(&self, other: &LutLang) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl PartialEq for LutLang

fn eq(&self, other: &LutLang) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl PartialOrd for LutLang

fn partial_cmp(&self, other: &LutLang) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl Report<LutLang> for SynthReport

fn new<A>( input: &RecExpr<LutLang>, output: &RecExpr<LutLang>, extract_time: f64, runner: &Runner<LutLang, A>, ) -> Result<Self, String>

where A: Analysis<LutLang>,

Create a new Report comparing a pre-optimized input and a post-optimized output.

fn with_name(self, name: &str) -> Self

Rewrite the module name of the Report.

impl VerilogEmission for LutLang

fn get_gate_type(&self) -> Option<PrimitiveType>

Returns the primitive type (i.e. the logic) of the language node

fn get_output_ids(expr: &RecExpr<Self>) -> Vec<Id>

Returns all the ids which need to be mapped to Verilog outputs

fn get_var(&self) -> Option<String>

Returns the variable name if the node is an input

fn get_verilog_primitive( &self, lookup: impl Fn(&Id) -> Option<String>, fresh_prim_name: impl Fn() -> String, fresh_signal_name: impl Fn() -> String, ) -> Result<Option<SVPrimitive>, String>

Returns the fully connected SVPrimitive for this node. All the predecessors of this node must be already defined with lookup

fn is_var(&self) -> bool

Returns true if the node is an input/variable

impl VerilogParsing for LutLang

fn get_expr<'a>( signal: &'a str, module: &'a SVModule, expr: &mut RecExpr<LutLang>, map: &mut HashMap<&'a str, Id>, ) -> Result<Id, String>

Compile the Verilog signal signal in module into the expr.

fn map_inputs<'a>( prim: &'a SVPrimitive, module: &'a SVModule, expr: &mut RecExpr<Self>, map: &mut HashMap<&'a str, Id>, ) -> Result<HashMap<&'a str, Id>, String>

Returns a mapping of the inputs to prim while also updating the root map as wel

impl Eq for LutLang

impl StructuralPartialEq for LutLang