Reimplement static-timing pass

[rachitnigam]

Top Down Static Timing

Top down static timing is a reimplementation of the old static-timing pass that generates latency-sensitive FSMs for control sub-programs with an inferred static annotation.

As a first requirement, we need the infer-static-timing pass to run and annotate the control program with @static annotations. Next, we need to define compilation functions for each container operators: seq, par, if, and while because a control sub-program can start with any one of these. enable and invoke are leaf nodes and therefore only make sense in the context of one of these.

Example

Given a program like this:

@static(4) seq {
  @static(3) if lt.out {
    @static(2) one
  } else {
    @static(1) two
  }
  @static(1) three
}

Note: infer-static-timing gives max(tru, fal) + 1 cycles to the latency of an if. This is not necessarily a good choice specially in the case when the branches are unbalanced.

We want to generate an FSM that executes each group for exactly the right number of cycles:

one[go] = fsm.out >= 0 & fsm.out < 2 & lt.out ? 1'd1;
two[go] = fsm.out >= 0 fsm.out < 1 & !lt.out ? 1'd1;
three[go] = fsm.out >= 2 & fsm.out < 3 ? 1'd1;

Like in the TopDownCompileControl pass, we should separate this in two steps:

1. Building a structure that computes which groups need to be activated when.
2. Realizing it into structural assignments.

Handling par

The big difference between TopDownCompileControl and this pass is that statically timed par blocks do not need to create a separate FSM for each child because we know exactly how long they need to run for:

@static(3) par {
  @static(1) one;
  @static(2) two;
  @static(3) seq {
    @static(1) three;
    @static(2) four;
  }
}

Works with the following FSM:

one[go] = fsm.out >= 0 & fsm.out < 1 ? 1'd1;
two[go] = fsm.out >= 0 fsm.out < 2 & ? 1'd1;
three[go] = fsm.out >= 0 & fsm.out < 1 ? 1'd1;
four[go] = fsm.out >= 1 & fsm.out < 3 ? 1'd1;

Note the assignments for three and four which need to basically propagate the par start time into the seq. This kind of nested FSM state generation will show up for all container operators.

Resources

The following methods might be useful:

1. TopDownCompileControl::compute_unique_ids
2. TopDownCompileControl::Schedule::realize_schedule
3. TopDownCompileControl::calculate_states_recur

TODO

• Enable "correctness static" tests
• Add -d static-timing flag to "correctness dynamic" tests
• Add -d static-timing flag to tests/regressions/group-multi-drive.futil
• examples/tutorial/language-tutorial-compute is slower with tdcc which shouldn't be the case.
• Systolic arrays are slower. This is probably because of par compilation.

[rachitnigam]

Blocked on #662