Struct CellShare

pub struct CellShare { /* private fields */ }

Given a LiveRangeAnalysis that specifies the “share” and “state_share” cells alive at each group, minimizes the cells used for each component.

This works by constructing an interference graph for each alive “state_share” cell. If two cells are ever alive at the same time, then there is an edge between them in the interference graph. Additionally, if two cells are different prototypes, then there is an edge between them.

A greedy graph coloring algorithm on the interference graph is used to assign each cell a name.

By default, this pass will share a given cell as many times as possible. However, by passing a command line argument, we can limit the number of times a given cell is reused. The rationale behind this option is that, in certain cases, if you share a given component too much, the logic to determine when that component should be activated ends up being more expensive than just using a separate component. To pass this command line argument, you give three numbers: The number of times a given combinational component can be shared, the number of times a given register can be shared, and the number of times all other components can be shared. Generally we would want settings such that 1 < 2 < 3, since a given share of a 3) would save more hardware than a share of a 2), and a share of a 2) would save more hardware than a share of a 1). The exact command line syntax to use: if we had a file, “x.futil” and ran: cargo run x.futil -x cell-share:bounds=2,4,8, then we would only share a given combinational component at most twice, a given register at most 4 times, and all other components at most 8 times. If you wanted to do something with fud then run fud e ... -s calyx.flags " -x cell-share:bounds=2,4,8". Finally if you do not want to bound the sharing for a particular cell type, you can pass -1 as a bound. So for example if you passed -x cell-share:bounds=2,-1,3 this means that you will always share registers. Note: The no spaces are important. Also, if you pass the following flag: -x cell-share:print-share-freqs=file-name this pass will write a json to file-name. If want to print into stdout then just set the file-name to be “stdout” (you don’t need the quotes when you actually pass in the argument, so run -x cell-share:print-share-freqs=stdout), and if you want to print to stderr then just set the file-name to be “stderr”. The json will map an integer (say n) to the number of cells in the new design (i.e., the design after sharing has been performed) that were shared exactly n times. So the key n = 2 will be mapped to the number of cells in the new design that are shared exactly twice.

Other flags: print_par_timing: prints the par-timing-map calyx_2020: shares using the Calyx 2020 settings: unlimited sharing of combinational components and registers, but no sharing of anything else

This pass only renames uses of cells. crate::passes::DeadCellRemoval should be run after this to actually remove the definitions.

Trait Implementations

impl ConstructVisitor for CellShare

fn from(ctx: &Context) -> CalyxResult<Self>

Construct the visitor using information from the Context

fn clear_data(&mut self)

Clear the data stored in the visitor. Called before traversing the next component by [ir::traversal::Visitor].

fn get_opts(ctx: &Context) -> LinkedHashMap<&'static str, ParseVal>

where Self: Named,

impl Named for CellShare

fn name() -> &'static str

The name of a pass. Is used for identifying passes.

fn description() -> &'static str

A short description of the pass.

fn opts() -> Vec<PassOpt>

Set of options that can be passed to the pass. The options contains a tuple of the option name and a description.

impl Visitor for CellShare

The algorithm that runs is:

• instantiate conflict graph using all component cells that satisfy cell_filter
• use [ScheduleConflicts] to find groups/invokes that run in parallel with each other
• for each tuple combination of cells that return true on cell_filter(), c1 and c2
• first determine if their live ranges overlap. If so, then insert a conflict between c1 and c2
• if c1 and c2 don’t have overlapping live ranges, check if c1 and c2 are ever live at within the same par block, and they are live at different children of the par block. If the parent par is not static, then add a conflict. If the parent par is static, then we can use the static_par_timing analysis to check whether the cells’ liveness actually overlaps.
• perform graph coloring using self.ordering to define the order of the greedy coloring
• use coloring to rewrite group assignments, continuous assignments, and conditional ports.

fn finish_context(&mut self, _ctx: &mut Context) -> VisResult

If requested, emit share map json after all components are processed

fn start( &mut self, comp: &mut Component, sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed before the traversal begins.

fn precondition(_ctx: &Context) -> Option<String>

where Self: Sized,

Precondition for this pass to run on the program. If this function returns None, the pass triggers. Otherwise it aborts and logs the string as the reason.

fn start_context(&mut self, _ctx: &mut Context) -> VisResult

Transform the ir::Context before visiting the components.

fn iteration_order() -> Order

where Self: Sized,

Define the iteration order in which components should be visited

fn traverse_component( &mut self, comp: &mut Component, signatures: &LibrarySignatures, components: &[Component], ) -> CalyxResult<()>

where Self: Sized,

Define the traversal over a component. Calls Visitor::start, visits each control node, and finally calls Visitor::finish.

fn do_pass(&mut self, context: &mut Context) -> CalyxResult<()>

where Self: Sized + ConstructVisitor + Named,

Run the visitor on a given program ir::Context. The function mutably borrows the control program in each component and traverses it.

fn do_pass_default(context: &mut Context) -> CalyxResult<Self>

where Self: ConstructVisitor + Sized + Named,

Build a Default implementation of this pass and call Visitor::do_pass using it.

fn finish( &mut self, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed after the traversal ends. This method is always invoked regardless of the Action returned from the children.

fn start_seq( &mut self, _s: &mut Seq, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed before visiting the children of a ir::Seq node.

fn finish_seq( &mut self, _s: &mut Seq, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed after visiting the children of a ir::Seq node.

fn start_par( &mut self, _s: &mut Par, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed before visiting the children of a ir::Par node.

fn finish_par( &mut self, _s: &mut Par, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed after visiting the children of a ir::Par node.

fn start_if( &mut self, _s: &mut If, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed before visiting the children of a ir::If node.

fn finish_if( &mut self, _s: &mut If, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed after visiting the children of a ir::If node.

fn start_while( &mut self, _s: &mut While, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed before visiting the children of a ir::While node.

fn finish_while( &mut self, _s: &mut While, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed after visiting the children of a ir::While node.

fn start_repeat( &mut self, _s: &mut Repeat, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed before visiting the children of a ir::Repeat node.

fn finish_repeat( &mut self, _s: &mut Repeat, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed after visiting the children of a ir::Repeat node.

fn start_static_control( &mut self, _s: &mut StaticControl, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed before visiting the contents of an ir::StaticControl node.

fn finish_static_control( &mut self, _s: &mut StaticControl, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed after visiting the conetnts of an ir::StaticControl node.

fn enable( &mut self, _s: &mut Enable, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed at an ir::Enable node.

fn fsm_enable( &mut self, _s: &mut FSMEnable, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed at an ir::FSMEnable node.

fn static_enable( &mut self, _s: &mut StaticEnable, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed at an ir::StaticEnable node.

fn start_static_if( &mut self, _s: &mut StaticIf, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed before visiting the children of a ir::StaticIf node.

fn finish_static_if( &mut self, _s: &mut StaticIf, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed after visiting the children of a ir::StaticIf node.

fn start_static_repeat( &mut self, _s: &mut StaticRepeat, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed before visiting the children of a ir::StaticRepeat node.

fn finish_static_repeat( &mut self, _s: &mut StaticRepeat, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed after visiting the children of a ir::StaticRepeat node.

fn start_static_seq( &mut self, _s: &mut StaticSeq, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

fn finish_static_seq( &mut self, _s: &mut StaticSeq, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

fn start_static_par( &mut self, _s: &mut StaticPar, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

fn finish_static_par( &mut self, _s: &mut StaticPar, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

fn invoke( &mut self, _s: &mut Invoke, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed at an ir::Invoke node.

fn static_invoke( &mut self, _s: &mut StaticInvoke, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed at a ir::StaticInvoke node.

fn empty( &mut self, _s: &mut Empty, _comp: &mut Component, _sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

Executed at an ir::Empty node.