google / google/xls

Codegen 1.5 fails to detect hierarchical combinational cycles

Open
#4,556 1 comment 0 reactions 0 assignees View on GitHub
codegen
Dominant language
C++
Stars
1.9k
Forks
283
Avg merge
2d 10h
Merged PRs (30d)
135

Description

**Describe the bug**
XLS fails to detect hierarchical combinational ready/valid loops (cycles that cross instantiation boundaries) when using Codegen 1.5. This allows XLS to compile the design successfully and output Verilog, which subsequently fails synthesis in downstream EDA tools (like Yosys) due to logic loops.

The cycle is correctly detected by Codegen 1.0, but is missed in Codegen 1.5 because the Codegen 1.5 entry point (`codegen::Codegen` in `xls/codegen_v_1_5/codegen.cc`) does not execute `VerifyPackage` or any invariant checkers on the final block hierarchy. **Note it's possible other checkers that aren't being run through `VerifyPackage` may manifest as other issues but they are not analyzed here.**

**To Reproduce**
Steps to reproduce the behavior:

1. Create a DSLX file `hierarchical_cycle.x` with the following content:
```dslx
// Toy example to reproduce cross-proc combinational ready/valid cycles.

proc B {
x_in: chan in;
y_out: chan out;

config(x_in: chan in, y_out: chan out) { (x_in, y_out) }

init { }

next(_: ()) {
let (tok, x) = recv(join(), x_in);
send(tok, y_out, x);
}
}

proc A {
x_in: chan in;
x_out: chan out;
y_in: chan in;
y_out: chan out;

config(x_in: chan in, y_out: chan out) {
let (x_s, x_r) = chan("x_internal");
let (y_s, y_r) = chan("y_internal");

spawn B(x_r, y_s);
(x_in, x_s, y_r, y_out)
}

init { }

next(_: ()) {
let (tok_in, x) = recv(join(), x_in);
send(tok_in, x_out, x);

let (tok_out, y) = recv(join(), y_in); // Independent token to bypass SendThenRecvConstraint
send(tok_out, y_out, y);
}
}
```

2. Configure the Bazel targets in your `BUILD` file. Note that `lower_to_proc_scoped_channels` is set to `false` to use package-scoped channels to factor it out of the equation but the same issue is present with PSC. `fifo_module` is set to `""` to materialize the FIFO logic inline but you can also replace it with a handwritten FIFO wrapper:
```python
load(
"//xls/build_rules:xls_build_defs.bzl",
"xls_dslx_library",
"xls_dslx_verilog",
)
load("@rules_hdl//verilog:providers.bzl", "verilog_library")
load("@rules_hdl//synthesis:build_defs.bzl", "synthesize_rtl")

xls_dslx_library(
name = "hierarchical_cycle_dslx",
srcs = ["hierarchical_cycle.x"],
)

# Buggy configuration (Codegen 1.5 + package-scoped channels)
xls_dslx_verilog(
name = "hierarchical_cycle_codegen",
codegen_args = {
"clock_period_ps": "100000",
"module_name": "hierarchical_cycle",
"generator": "pipeline",
"delay_model": "sky130",
"use_system_verilog": "false", # Standard Verilog for Yosys parser compatibility
"reset": "rst",
"reset_data_path": "true",
"reset_active_low": "false",
"reset_asynchronous": "true",
"flop_inputs": "false",
"flop_single_value_channels": "false",
"flop_outputs": "false",
"add_idle_output": "false",
"multi_proc": "true",
"codegen_version": "1.5",
"pipeline_stages": "1",
"fifo_module": "", # Materialize FIFO logic inline
},
dslx_top = "A",
ir_conv_args = {
"default_fifo_config": "depth: 0, bypass: true, register_push_outputs: false, register_pop_outputs: false",
"lower_to_proc_scoped_channels": "false", # Disable proc-scoped channels
},
library = ":hierarchical_cycle_dslx",
verilog_file = "hierarchical_cycle.v",
)

verilog_library(
name = "hierarchical_cycle_verilog",
srcs = [":hierarchical_cycle.v"],
)

synthesize_rtl(
name = "hierarchical_cycle_synth",
top_module = "hierarchical_cycle",
deps = [
":hierarchical_cycle_verilog",
],
)
```

3. Run the codegen build with Codegen 1.5. Note that it succeeds without warnings:
```bash
bazel build //xls/examples:hierarchical_cycle_codegen
```

4. Run the synthesis build. Yosys will fail and report logic loops:
```bash
bazel build //xls/examples:hierarchical_cycle_synth
```
Output:
```
Warning: found logic loop in module hierarchical_cycle:
cell $flatten\__hierarchical_cycle__A__B_0_next_inst0.$and$bazel-out/k8-fastbuild/bin/xls/examples/hierarchical_cycle.v:12$143 ($and)
cell $flatten\hierarchical_cycle__1_inst1.$and$bazel-out/k8-fastbuild/bin/xls/examples/hierarchical_cycle.v:49$127 ($and)
cell $flatten\hierarchical_cycle__1_inst1.$and$bazel-out/k8-fastbuild/bin/xls/examples/hierarchical_cycle.v:49$129 ($and)
cell $flatten\hierarchical_cycle__1_inst1.$or$bazel-out/k8-fastbuild/bin/xls/examples/hierarchical_cycle.v:49$126 ($or)
cell $flatten\materialized_fifo_fifo_hierarchical_cycle__x_internal_.$or$bazel-out/k8-fastbuild/bin/xls/examples/hierarchical_cycle.v:121$71 ($or)
cell $flatten\materialized_fifo_fifo_hierarchical_cycle__x_internal_.$or$bazel-out/k8-fastbuild/bin/xls/examples/hierarchical_cycle.v:129$78 ($or)
cell $flatten\materialized_fifo_fifo_hierarchical_cycle__y_internal_.$or$bazel-out/k8-fastbuild/bin/xls/examples/hierarchical_cycle.v:217$18 ($or)
wire $flatten\hierarchical_cycle__1_inst1.$and$bazel-out/k8-fastbuild/bin/xls/examples/hierarchical_cycle.v:49$127_Y
wire $flatten\hierarchical_cycle__1_inst1.$or$bazel-out/k8-fastbuild/bin/xls/examples/hierarchical_cycle.v:49$126_Y
wire \__hierarchical_cycle__A__B_0_next_inst0.hierarchical_cycle__y_internal_rdy
wire \hierarchical_cycle__1_inst1.hierarchical_cycle__x_internal_rdy
wire \hierarchical_cycle__1_inst1.stage_outputs_valid_0
wire \materialized_fifo_fifo_hierarchical_cycle__x_internal_.can_do_push
wire \materialized_fifo_fifo_hierarchical_cycle__x_internal_.pop_ready
```

5. To verify it is caught by Codegen 1.0:
Update the `hierarchical_cycle_codegen` target in `BUILD` to use Codegen 1.0:
* Set `codegen_version` to `"1.0"`

Then run codegen again:
```bash
bazel build //xls/examples:hierarchical_cycle_codegen
```
This correctly **fails during XLS compilation** with the expected cycle error:
```
Error: INVALID_ARGUMENT: Cycle detected involving the following components (in flow order):
* Proc: `__hierarchical_cycle__A_0_next` (instance: `hierarchical_cycle__1 [hierarchical_cycle::hierarchical_cycle__1_inst1->hierarchical_cycle__1]`)
Combinational path: `p0_all_active_inputs_valid` -> ... -> `__hierarchical_cycle__x_internal_valid_and_not_has_been_sent` -> output `hierarchical_cycle__x_internal_vld`
...
```

**Expected behavior**
XLS should fail compilation during codegen when a combinational loop is present in the design, regardless of the codegen version. Codegen 1.5 should execute `VerifyPackage(..., codegen=true)` to catch hierarchical cycles before generating Verilog.

**Additional Context**
- **SystemVerilog vs Verilog**: The reproduction targets use `"use_system_verilog": "false"` and output `.v` files. This is to ensure the generated materialized FIFO logic uses standard Verilog-2001 (element-by-element array assignment) instead of SystemVerilog array patterns (`'{...}`), allowing the open-source Yosys parser to parse the file without syntax errors. The bug itself is present regardless of this setting (Codegen 1.5 misses the cycle in both SV and non-SV modes). The materialized FIFOs work in SystemVerilog with the Verific parser.
- **Proc-Scoped Channels**: The reproduction has proc-scoped channels disabled (`lower_to_proc_scoped_channels = "false"`) to simplify the reproduction because PSC implicitly forces codegen 1.5 (#4554) . The bug occurs in both configurations.

Contributor guide

Open the contributing guide

Research direction

Start in xls/codegen_v_1_5/codegen.cc at the codegen::Codegen entry point and compare its final block-hierarchy checks with Codegen 1.0. Reproduce the issue with the hierarchical_cycle.x example and the BUILD configuration, then run bazel build //xls/examples:hierarchical_cycle_codegen with Codegen 1.5. Done means the build rejects the hierarchical cycle during XLS compilation rather than emitting Verilog that only fails during synthesis.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
52/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.