opt_main times out in PartialInfoQueryEngine / IntervalSet::Combine during select_simp
- 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
Assessment
This issue has not been assessed yet.