Struct TopDownCompileControl

pub struct TopDownCompileControl { /* private fields */ }

Core lowering pass. Compiles away the control programs in components into purely structural code using an finite-state machine (FSM).

Lowering operates in two steps:

1. Compile all ir::Par control sub-programs into a single ir::Enable of a group that runs all children to completion.
2. Compile the top-level control program into a single ir::Enable.

Compiling non-par programs

At very high-level, the pass assigns an FSM state to each ir::Enable in the program and generates transitions to the state to activate the groups contained within the ir::Enable.

The compilation process calculates all predeccesors of the ir::Enable while walking over the control program. A predeccesor is any enable statement that can directly “jump” to the current ir::Enable. The compilation process computes all such predeccesors and the guards that need to be true for the predeccesor to jump into this enable statement.

cond0;
while lt.out {
  if gt.out { true } else { false }
}
next;

The predeccesor sets are:

cond0 -> []
true -> [(cond0, lt.out & gt.out); (true; lt.out & gt.out); (false, lt.out & !gt.out)]
false -> [(cond0, lt.out & !gt.out); (true; lt.out & gt.out); (false, lt.out & !gt.out)]
next -> [(cond0, !lt.out); (true, !lt.out); (false, !lt.out)]

Compiling ir::Enable

The process first takes all edges from predeccesors and transitions to the state for this enable and enables the group in this state:

let cur_state; // state of this enable
for (state, guard) in predeccesors:
  transitions.insert(state, cur_state, guard)
enables.insert(cur_state, group)

While this process will generate a functioning FSM, the FSM takes unnecessary cycles for FSM transitions.

For example:

seq { one; two; }

The FSM generated will look like this (where f is the FSM register):

f.in = one[done] ? 1;
f.in = two[done] ? 2;
one[go] = !one[done] & f.out == 0;
two[go] = !two[done] & f.out == 1;

The cycle-level timing for this FSM will look like: - cycle 0: (f.out == 0), enable one - cycle t: (f.out == 0), (one[done] == 1), disable one - cycle t+1: (f.out == 1), enable two - cycle t+l: (f.out == 1), (two[done] == 1), disable two - cycle t+l+1: finish

The transition t -> t+1 represents one where group one is done but group two hasn’t started executing.

To address this specific problem, there is an additional enable added to run all groups within an enable while the FSM is transitioning. The final transition will look like this:

f.in = one[done] ? 1;
f.in = two[done] ? 2;
one[go] = !one[done] & f.out == 0;
two[go] = (!two[done] & f.out == 1) || (one[done] & f.out == 0);

Note that !two[done] isn’t present in the second disjunct because all groups are guaranteed to run for at least one cycle and the second disjunct will only be true for one cycle before the first disjunct becomes true.

Compiling par programs

We have to generate new FSM-based controller for each child of a par node so that each child can indepdendently make progress. If we tie the children to one top-level FSM, their transitions would become interdependent and reduce available concurrency.

Compilation guarantee

At the end of this pass, the control program will have no more than one group enable in it.

Trait Implementations

impl ConstructVisitor for TopDownCompileControl

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

where Self: Sized + Named,

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 TopDownCompileControl

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 TopDownCompileControl

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

Compile each child in par block separately so each child can make progress indepdendently.

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

If requested, emit FSM json after all components are processed

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

Executed before the traversal begins.

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 finish_if( &mut self, i: &mut If, comp: &mut Component, sigs: &LibrarySignatures, _comps: &[Component], ) -> VisResult

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

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

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

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 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 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 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 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 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 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 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.