Struct calyx_opt::passes::TopDownCompileControl
source · [−]pub struct TopDownCompileControl { /* private fields */ }
Expand description
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:
- Compile all ir::Par control sub-programs into a single ir::Enable of a group that runs all children to completion.
- 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
sourceimpl ConstructVisitor for TopDownCompileControl
impl ConstructVisitor for TopDownCompileControl
sourcefn from(ctx: &Context) -> CalyxResult<Self>where
Self: Sized + Named,
fn from(ctx: &Context) -> CalyxResult<Self>where
Self: Sized + Named,
sourcefn clear_data(&mut self)
fn clear_data(&mut self)
fn get_opts(ctx: &Context) -> LinkedHashMap<&'static str, ParseVal>where
Self: Named,
sourceimpl Named for TopDownCompileControl
impl Named for TopDownCompileControl
sourcefn description() -> &'static str
fn description() -> &'static str
sourceimpl Visitor for TopDownCompileControl
impl Visitor for TopDownCompileControl
sourcefn finish_par(
&mut self,
s: &mut Par,
comp: &mut Component,
sigs: &LibrarySignatures,
_comps: &[Component]
) -> VisResult
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.
sourcefn start(
&mut self,
comp: &mut Component,
_sigs: &LibrarySignatures,
_comps: &[Component]
) -> VisResult
fn start(
&mut self,
comp: &mut Component,
_sigs: &LibrarySignatures,
_comps: &[Component]
) -> VisResult
sourcefn finish_seq(
&mut self,
s: &mut Seq,
comp: &mut Component,
sigs: &LibrarySignatures,
_comps: &[Component]
) -> VisResult
fn finish_seq(
&mut self,
s: &mut Seq,
comp: &mut Component,
sigs: &LibrarySignatures,
_comps: &[Component]
) -> VisResult
sourcefn finish_if(
&mut self,
i: &mut If,
comp: &mut Component,
sigs: &LibrarySignatures,
_comps: &[Component]
) -> VisResult
fn finish_if(
&mut self,
i: &mut If,
comp: &mut Component,
sigs: &LibrarySignatures,
_comps: &[Component]
) -> VisResult
sourcefn finish_while(
&mut self,
w: &mut While,
comp: &mut Component,
sigs: &LibrarySignatures,
_comps: &[Component]
) -> VisResult
fn finish_while(
&mut self,
w: &mut While,
comp: &mut Component,
sigs: &LibrarySignatures,
_comps: &[Component]
) -> VisResult
sourcefn finish(
&mut self,
comp: &mut Component,
sigs: &LibrarySignatures,
_comps: &[Component]
) -> VisResult
fn finish(
&mut self,
comp: &mut Component,
sigs: &LibrarySignatures,
_comps: &[Component]
) -> VisResult
sourcefn precondition(_ctx: &Context) -> Option<String>where
Self: Sized,
fn precondition(_ctx: &Context) -> Option<String>where
Self: Sized,
sourcefn start_context(&mut self, _ctx: &mut Context) -> VisResult
fn start_context(&mut self, _ctx: &mut Context) -> VisResult
ir::Context
before visiting the components.sourcefn finish_context(&mut self, _ctx: &mut Context) -> VisResult
fn finish_context(&mut self, _ctx: &mut Context) -> VisResult
ir::Context
after visiting the components.sourcefn iteration_order() -> Orderwhere
Self: Sized,
fn iteration_order() -> Orderwhere
Self: Sized,
sourcefn traverse_component(
&mut self,
comp: &mut Component,
signatures: &LibrarySignatures,
components: &[Component]
) -> CalyxResult<()>where
Self: Sized,
fn traverse_component(
&mut self,
comp: &mut Component,
signatures: &LibrarySignatures,
components: &[Component]
) -> CalyxResult<()>where
Self: Sized,
sourcefn do_pass(&mut self, context: &mut Context) -> CalyxResult<()>where
Self: Sized + ConstructVisitor + Named,
fn do_pass(&mut self, context: &mut Context) -> CalyxResult<()>where
Self: Sized + ConstructVisitor + Named,
ir::Context
.
The function mutably borrows the control
program in each component and
traverses it. Read more