Timeout due to infinite optimization loop between Strength Reduction and Array Simplification Pass (crasher_2026-07-04_500f)
- Dominant language
- C++
- Stars
- 1.9k
- Forks
- 283
- Avg merge
- 2d 10h
- Merged PRs (30d)
- 135
Description
### Summary
The crasher causes `opt_main` to time out after 1500 seconds due to an infinite optimization loop between Strength Reduction (`strength_reduction_pass.cc`) and Array Simplification (`array_simplification_pass.cc`).
### Root Cause
1. Strength Reduction (`SinkSingleUserSelect` in `strength_reduction_pass.cc`) sees `array_update(array_literal, sel_val, indices=[sel_val])` where `sel_val`'s cases are known constants and the array is constant. It sinks `array_update` into `sel_val`, creating `sel(cases=[array_update(const0), array_update(const1)])`.
2. Array Simplification (`array_simplification_pass.cc`) detects a select whose cases are all `array_update` on the same array/index and hoists the select back out, producing `array_update(sel(...))`.
3. The two passes endlessly undo each other in a loop until timeout.
### Reproduction Steps
Run opt_main on the unoptimized converted IR from crasher_2026-07-04_500fx:
### Minimized IR Reproduction
```
package test_package
top fn main(s: bits[1]) -> bits[8][2] {
a: bits[8][2] = literal(value=[1, 2])
c0: bits[8] = literal(value=0)
c1: bits[8] = literal(value=1)
sel_val: bits[8] = sel(s, cases=[c0, c1])
ret array_update.1: bits[8][2] = array_update(a, sel_val, indices=[sel_val])
}
```
Contributor guide
Research direction
Start by running opt_main on the minimized IR and the unoptimized converted IR from crasher_2026-07-04_500fx. Read SinkSingleUserSelect in strength_reduction_pass.cc alongside array_simplification_pass.cc to trace how each pass transforms array_update and sel. Done means the reproducer no longer times out after 1500 seconds because the two passes no longer undo each other indefinitely.
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
- Mostly clear
- Newbie friendliness
- 48/100