google / google/xls

Timeout due to infinite optimization loop between Strength Reduction and Array Simplification Pass (crasher_2026-07-04_500f)

Open
#4,545 1 comment 0 reactions 0 assignees View on GitHub
bug fuzz
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.