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

[proppy]

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:

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:

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)
}