Fuzzer opt timeout on strength reduction pass

[angelomatni1]

Repro:

bazel test -c opt //xls/fuzzer:run_crasher_test_2026-05-11_d422

Error:

E0511 11:32:20.018260    5964 sample_runner.cc:832] Exception when running sample: DEADLINE_EXCEEDED: Subprocess call timed out after 1500 seconds: /build/work/d87a9529c3b742bfc9ddf24115f2d83a017c/google3/runfiles/google3/third_party/xls/tools/opt_main /tmp/temp_directory_7OCcP8/sample.ir --logtostderr

[angelomatni1]

While working on getting the crashing sample DSLX merged, I will reference it here to explain where my investigation is currently at:

fn x21(x22: uN[118], x23: uN[118], x24: bool, x25: s3, x26: bool) -> (uN[118],) {
    {
        let x27: uN[118] = rev(x22);
        (x27,)
    }
}
fn main(x0: (s2, s29), x1: (xN[bool:0x1][1938], s57)) -> (uN[119], xN[bool:0x0][885], uN[301], bool, u45, uN[236]) {
    {
        let x2: u59 = match x0 {
            (s2:0x1, .., s29:0x1fff_ffff) | (s2:0x1, s29:0xaaa_aaaa) => u59:0x3ff_ffff_ffff_ffff,
            (s2:0x2, s29:0x2_0000) | (s2:0x1, s29:0b1100_1100_1101_1100_0000_0101) => u59:0x1000,
            (_, s29:0x2000) => u59:0x0,
            (s2:0b1, _) | (s2:0x3, _) => u59:0x100_0000,
            _ => u59:0x2aa_aaaa_aaaa_aaaa,
        };
        let x3: u59 = -x2;
        let x4: uN[236] = x3 ++ x3 ++ x3 ++ x2;
        let x5: u59 = -x2;
        let x6: xN[bool:0x0][885] = x4 ++ x5 ++ x4 ++ x4 ++ x5 ++ x5;
        let x7: s3 = s3:0x7;
        let x8: uN[118] = x3 ++ x5;
        let x9: bool = or_reduce(x5);
        let x10: s29 = x0.1;
        let x11: xN[bool:0x0][885] = x9 as xN[bool:0x0][885] | x6;
        let x12: bool = x9 ^ x9;
        let x13: u59 = -x2;
        let x14: u23 = u23:0x3f_ffff;
        let x15: u59 = one_hot_sel(x12, [x3]);
        let x16: bool = x9[0+:bool];
        let x17: uN[118] = x8 | x9 as uN[118];
        let x18: u59 = x13 << 22;
        let x19: u5 = (x10 as u29)[24+:u5];
        let x20: uN[119] = x13 ++ x3 ++ x12;
        let x28: (uN[118],) = x21(x17, x8, x9, x7, x16);
        let (_) = x21(x17, x8, x9, x7, x16);
        let x29: u23 = x14 >> x17;
        let x30: bool = xor_reduce(x11);
        let x31: uN[301] = x8 ++ x15 ++ x19 ++ x20;
        let x32: bool = x16 + x31 as bool;
        let x33: u45 = match x30 {
            bool:false => u45:0xaaa_aaaa_aaaa,
            bool:true => u45:0xaaa_aaaa_aaaa,
            bool:0x0 => u45:0xfff_ffff_ffff,
            _ => u45:0x1fff_ffff_ffff,
        };
        let x34: u2 = (x7 as u3)[1+:u2];
        (x20, x11, x31, x12, x33, x4)
    }
}

The strength reduction pass uses the partial info query engine which seems to hang on trying to compute known values for the node x11.

[angelomatni1]

This proves insufficient to prevent an explosion of combinations of possible interval sets for each operand of the concatenate resulting in timeout in ir/interval_ops.cc:PerformVariadicOp

      // TODO(allight): We might want to distribute the intervals more evenly
      // then just giving the first 12 operands 5 segments and the rest 1.
      // Limit exponential growth after 12 parameters. 5^12 = 244 million
      interval_set = MinimizeIntervals(interval_set, (i < 12) ? 5 : 1);