calyx 0.7.1

Compiler Infrastructure for Hardware Accelerator Generation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174

# Debugging Compilation Bugs

These tips are directed towards *compilation bugs*. Before trying these, make sure your program
produces the correct values with the [Calyx Interpreter](../interpreter.md)

## Disabling Optimizations

The first step is disabling optimization passes and running the bare bones compilation pipeline.

To disable the passes, add the flag `-p no-opt` to compiler invocation:
1. For the compiler: `futil <filename> -p no-opt`.
2. For `fud`: `fud ... -s calyx.flags " -p no-opt"`.

If the output is still incorrect then one of the core compilation passes is incorrect.
Our best bet at this point is to reduce the test file such that the output from the
interpreter and the Calyx compiler still disagree and [report the
bug](https://github.com/calyxir/calyx/issues/new). We can use the [waveform
debugging](#waveform-debugging) to figure out which part of the compilation pipeline generates the
incorrect result.

If the execution generates the right result, then one of the optimizations
passes is incorrect.
To identify which optimization pass is wrong, add back individual passes and see
when the execution fails.
The `calyx/src/default_passes.rs` file defines the compilation pipeline. Start by incrementally
adding passes to this flag invocation:
```
-p validate -p simplify-with-control -p <PASS 1> ... -p <PASS N> -p compile -p lower
```


## Reducing Test Files

It is often possible to reduce the size of the example program that is
generating incorrect results.
In order to perform a reduction, we need to run the program twice, once with
a "golden workflow" that we trust to generate the right result and once with
the buggy workflow.

### Inlining (Optional)
It is useful to inline all the code into the `main` component so that we can focus our energy on reducing one control program. This can be done by passing the following flags to the compiler:
```
-p well-formed -p inline -x inline:always -p post-opt
```
The `-x inline:always` flag tells the inlining pass to attempt to inline all components into one. If this command fails, we can just work with the original program and reduce control programs for each component.

### Reducing
At a high-level, we want to do the following:
1. Delete some part of the control program
2. See if the error still occurs
3. If it doesn't, delete a smaller part of the control program
4. Otherwise, continue deleting more parts of the control program

> When deleting parts of the control program, the compiler may complain that certain groups are no longer being used. In this case, run the `-p dead-group-removal` pass before any other pass runs.

Next, if we've identified the problem to be in one of the Calyx passes,
the "golden workflow" is running the program without the pass while the buggy
workflow is running the program with the pass enabled.
This case is so common that we've written [a script][flag-cmp] that can run
programs with different set of flags to the Calyx compiler and show the
difference in the outputs after simulation.

The script is invoked as:
```
tools/flag-compare.sh <calyx program> <data>
```

By default, the script will try to run the programs by simulating them through
Verilator by providing `fud` with the target `--to dat`.
If you'd like to use the Calyx Interpreter instead, run the following command:
```
tools/flag-compare.sh <calyx program> <data> interpreter-out
```

### Reducing Calyx Programs

The best way to reduce Calyx program deleting group enables from the control
program and seeing if the generated program still generates the wrong output.
While doing this, make sure that you're not deleting an update to a loop
variable which might cause infinite loops.

By default, the compiler will complain if the program contains a `group` that
is not used in the control program which can get in the way of minimizing
programs.
To get around this, run the [`dead-group-removal`][dgr] pass before the validation
passes:
```
futil -p dead-group-removal -p validate ...
```

### Reducing Dahlia Programs

If you're working with Dahlia programs, it is also possible to reduce the
program with the script since it simply uses `fud` to run the program with the
simulator.
As with Calyx reduction, try deleting parts of the program and seeing if the
flag configurations for the Calyx program still generate different outputs.


## Waveform Debugging

Waveform debugging is the final way of debugging Calyx programs.
A waveform captures the value of every port at every clock cycle and can be
viewed using a wave viewer program like [GTKWave][gtkwave] or
[WaveTrace][wavetrace] to look at the wave form.
Because of this level of granularity, it generates a lot of information.
To make the information a little more digestible, we can use information
generated by Calyx during compilation.

For waveform debugging, we recommend disabling the optimization passes and
static timing compilation (unless you're debugging these passes).
In this debugging strategy, we'll do the following:
1. Dump out the control FSM for the program we're debugging.
2. Find the FSM states that enable the particular groups that might be misbehaving.
3. Open the waveform viewer and find clock cycles where the FSM takes the corresponding
values and identify other signals that we care about.

Consider the control section from [examples/futil/dot-product.futil](https://github.com/calyxir/calyx/blob/master/examples/futil/dot-product.futil):
```
{{#include ../../examples/futil/dot-product.futil:control}}
```
Suppose that we want to make sure that `let0` is correctly performing its
computation.
We can generate the control FSM for the program using:

      futil <filename> -p top-down-cc

This generates a Calyx program with several new groups.
We want to look for groups with the prefix `tdcc` which look something like
this:
```
group tdcc {
  let0[go] = !let0[done] & fsm.out == 4'd0 ? 1'd1;
  cs_wh.in = fsm.out == 4'd1 ? le0.out;
  cs_wh.write_en = fsm.out == 4'd1 ? 1'd1;
  cond0[go] = fsm.out == 4'd1 ? 1'd1;
  par[go] = !par[done] & cs_wh.out & fsm.out == 4'd2 ? 1'd1;
  let1[go] = !let1[done] & cs_wh.out & fsm.out == 4'd3 ? 1'd1;
  let2[go] = !let2[done] & cs_wh.out & fsm.out == 4'd4 ? 1'd1;
  upd2[go] = !upd2[done] & cs_wh.out & fsm.out == 4'd5 ? 1'd1;
  upd3[go] = !upd3[done] & cs_wh.out & fsm.out == 4'd6 ? 1'd1;
  ...
}
```

The assignments to `let0[go]` indicate what conditions make the `let0` group
execute.
In this program, we have:

    let0[go] = !let0[done] & fsm.out == 4'd0 ? 1'd1;

Which states that `let0` will be active when the state of the `fsm` register
is `0` along with some other conditions.
The remainder of the group defines how the state in the `fsm` variable changes:
```
  ...
  fsm.in = fsm.out == 4'd0 & let0[done] ? 4'd1;
  fsm.write_en = fsm.out == 4'd0 & let0[done] ? 1'd1;
  fsm.in = fsm.out == 4'd1 & cond0[done] ? 4'd2;
  fsm.write_en = fsm.out == 4'd1 & cond0[done] ? 1'd1;
  ...
```
For example, we can see that when the value of the FSM is 0 and `let0[done]`
becomes high, the FSM will take the value 1.

Once we have this information, we can open the VCD file and look at points when
the `fsm` register has the value 1 and check to see if the assignments in
`let0` activated in the way we expected.


[gtkwave]: http://gtkwave.sourceforge.net/
[wavetrace]: https://marketplace.visualstudio.com/items?itemName=wavetrace.wavetrace
[flag-cmp]: https://github.com/calyxir/calyx/blob/master/tools/flag-compare.sh
[dgr]: https://docs.rs/calyx-opt/latest/calyx_opt/passes/struct.DeadGroupRemoval.html