google / google/xls

opt_main times out in PartialInfoQueryEngine / IntervalSet::Combine during select_simp

Open
#4,425 0 comments 0 reactions 0 assignees View on GitHub
bug fuzz optimizer
Dominant language
C++
Stars
1.9k
Forks
283
Avg merge
2d 10h
Merged PRs (30d)
135

Description

### Summary
The fuzzer crasher in cl/933798665 (`crasher_2026-06-17_771c.x`) fails due to a subprocess timeout after 1500 seconds during IR optimization (`opt_main`).

### Reproduction Steps
Run `opt_main` on the unoptimized converted IR from `crasher_2026-06-17_771c.x`:
```bash
opt_main sample.ir --logtostderr
```

### Root Cause Analysis
When running `opt_main`, the optimization pipeline successfully executes 628+ passes and then hangs indefinitely inside the **Select Simplification** (`select_simp`) pass.

Specifically, during `select_simp`:
1. `PartialInfoQueryEngine::ComputeInfo()` visits `sel` / `priority_sel` nodes.
2. `PartialInfoQueryEngine::JoinElements()` computes abstract information across candidate branches by calling `PartialInformation::MeetWith()`.
3. `MeetWith()` invokes `IntervalSet::Combine(*range_, *other.range_)` to compute the union of possible interval bounds across branches.
4. `IntervalSet::Combine()` calls `CombineAndAdvance()` in a loop. On fragmented interval sets derived from large array update operations (e.g., array updates on `u8[1194]`), `IntervalSet::Combine()` exhibits catastrophic time complexity / hanging.

### Call Stack at Hang
```
xls::IntervalSet::Combine()
xls::PartialInformation::MeetWith()
xls::(anonymous namespace)::PartialInfoVisitor::JoinElements()
xls::leaf_type_tree::ZipIndex<>()
xls::DataflowVisitor<>::HandleSel()
xls::Node::VisitSingleNode()
xls::PartialInfoQueryEngine::ComputeInfo()
```

### Minimized Test Case
Using `ir_minimizer_main`, the crashing IR was minimized from 1877 nodes down to 19 nodes:
```ir
package sample

top fn __sample__main(x0: bits[48] id=27, x1: bits[14] id=28) -> bits[8][3] {
bit_slice.551: bits[1] = bit_slice(x0, start=0, width=1, id=551)
literal.541: bits[2] = literal(value=0, id=541)
concat.542: bits[4] = concat(bit_slice.551, bit_slice.551, literal.541, id=542)
literal.51: bits[1] = literal(value=1, id=51)
literal.45: bits[1] = literal(value=0, id=45)
x23__2: bits[1] = priority_sel(concat.542, cases=[literal.45, literal.45, literal.51, literal.45], default=literal.45, id=535)
x27__1: bits[8] = literal(value=0, id=331)
x27__2: bits[8] = literal(value=107, id=268)
x3: bits[8][1194] = literal(value=[0, ...])
x27: bits[8] = sel(x23__2, cases=[x27__1, x27__2], id=249)
x28: bits[8][1194] = array_update(x3, x27, indices=[x27], assumed_in_bounds=true, id=316)
literal.26047: bits[64] = literal(value=0, id=26047)
literal.782: bits[64] = literal(value=107, id=782)
x28_arr98: bits[8] = array_index(x28, indices=[literal.26047], assumed_in_bounds=true, id=1799)
x28_arr107: bits[8] = array_index(x28, indices=[literal.782], assumed_in_bounds=true, id=1817)
ret array.26087: bits[8][3] = array(x28_arr98, x27__1, x28_arr107, id=26087)
}
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.