[enhancement] potential combinational cycles should be flagged at the DSLX level
- Dominant language
- C++
- Stars
- 1.9k
- Forks
- 283
- Avg merge
- 2d 10h
- Merged PRs (30d)
- 135
Description
### What's hard to do? (limit 100 words)
Currently combinational cycle detection happens after schedule, during codegen, once the toolchain identifies that the cycle actually materialize in hardware.
This makes sense as the actual materialization of cycle depends on the pipeline configuration: a "lucky" schedule could end up inadvertently breaking a cycle by inserting a pipeline register in the "right" place.
Example, while this proc network, doesn't codegen at `--clock_period_ps=200`:
```
proc Bar {
a: chan in;
b: chan out;
init {
}
config(a: chan in, b: chan out) {
(a, b)
}
next(_: ()) {
let (tok, n) = recv(token(), a);
send(tok, b, n*n + n);
}
}
proc Foo {
a: chan out;
b: chan in;
r: chan out;
init {
u8:0
}
config(r: chan out) {
let (a_s, a_r) = #[channel(depth=1, bypass=true, register_push_outputs=false, register_pop_outputs=false)] chan("a");
let (b_s, b_r) = #[channel(depth=1, bypass=true, register_push_outputs=false, register_pop_outputs=false)] chan("b");
spawn Bar(a_r, b_s);
(a_s, b_r, r)
}
next(state: u8) {
let tok = send(token(), a, state);
let (tok, n) = recv(tok, b);
send(tok, r, n);
n
}
}
```
```
Error: INVALID_ARGUMENT: Cycle detected involving the following components (in flow order):
* FIFO: `fifo_user_module__b`
Combinational path: push_data -> pop_valid
* Proc: `__user_module__Foo_0_next` (instance: `user_module__1 [user_module::user_module__1_inst1->user_module__1]`)
Combinational path: input `user_module__b_valid` -> `p1_stage_done` -> ... -> `__user_module__a_data_valid_and_not_has_been_sent` -> output `user_module__a_valid`
* FIFO: `fifo_user_module__a`
Combinational path: push_valid -> pop_data
* Proc: `__user_module__Foo__Bar_0_next` (instance: `__user_module__Foo__Bar_0_next [user_module::__user_module__Foo__Bar_0_next_inst0->__user_module__Foo__Bar_0_next]`)
Combinational path: input `user_module__a_data` -> `umul.130` -> ... -> `add.132` -> output `user_module__b_data`
```
It does codegen at `--clock_period_ps=150` as a pipeline stage gets inserted between the adder and the multiplier
```
module __user_module__Foo__Bar_0_next(
input wire clk,
input wire reset,
input wire [7:0] user_module__a_data,
input wire user_module__a_valid,
input wire user_module__b_ready,
output wire user_module__a_ready,
output wire [7:0] user_module__b_data,
output wire user_module__b_valid
);
// ri lint_check_off MULTIPLY
function automatic [7:0] umul8b_8b_x_8b (input reg [7:0] lhs, input reg [7:0] rhs);
begin
umul8b_8b_x_8b = lhs * rhs;
end
endfunction
// ri lint_check_on MULTIPLY
reg [7:0] p0_n;
reg [7:0] p0_umul_130;
reg p0_valid;
wire p1_stage_done;
wire p1_not_valid;
wire p0_enable;
wire p0_data_enable;
wire [7:0] add_138;
wire [7:0] umul_130;
assign p1_stage_done = p0_valid & user_module__b_ready;
assign p1_not_valid = ~p0_valid;
assign p0_enable = p1_stage_done | p1_not_valid;
assign p0_data_enable = p0_enable & user_module__a_valid;
assign add_138 = p0_umul_130 + p0_n;
assign umul_130 = umul8b_8b_x_8b(user_module__a_data, user_module__a_data);
always_ff @ (posedge clk) begin
if (reset) begin
p0_n <= 8'h00;
p0_umul_130 <= 8'h00;
p0_valid <= 1'h0;
end else begin
p0_n <= p0_data_enable ? user_module__a_data : p0_n;
p0_umul_130 <= p0_data_enable ? umul_130 : p0_umul_130;
p0_valid <= p0_enable ? user_module__a_valid : p0_valid;
end
end
assign user_module__a_ready = p0_data_enable;
assign user_module__b_data = add_138;
assign user_module__b_valid = p0_valid;
endmodule
```
Given that developers have (by design) little control over where pipeline stage are inserted, this can lead to DevX anti-patterns, like bisecting/tweaking scheduling options until codegen pass, that are inherently fragile (heavily dependent on the complexity of the DSLX code input) and violate the https://en.wikipedia.org/wiki/Principle_of_least_astonishment.
### Current best alternative workaround (limit 100 words)
Worth noting that the error message does attempt to pin-point problematic channels and suggest possible mitigations to the user:
```
* Proc `__user_module__Foo_0_next` (instance: `user_module__1 [user_module::user_module__1_inst1->user_module__1]`): Cut the combinational path from input `user_module__b_valid` -> `p1_stage_done` to `__user_module__a_data_valid_and_not_has_been_sent` -> output `user_module__a_valid` (e.g. by inserting a register or FIFO).
```
Which can translate into DSLX channel's configuration changes, like disabling bypass, adding output/input flopping, and/or changing fifo depth, ex:
```
let (a_s, a_r) = #[channel(depth=1, bypass=false, register_push_outputs=false, register_pop_outputs=false)] chan("a");
```
### Your view of the "best case XLS enhancement" (limit 100 words)
Ideally we could perform a static analysis at the DSLX abstraction-level that flag communication patterns that can potentially results in cycles (i.e: procs communicating back and forth) and instruct the developer to setup reliable channel configurations to consistently avoid them.
Also see https://github.com/google/xls/issues/1509
Contributor guide
Assessment
This issue has not been assessed yet.