JIT compile hang in LLVM ConstraintEliminationPass for large array comparisons

[proppy]

Summary

XLS JIT compilation hangs when compiling comparisons of large multidimensional arrays. Specifically, comparing two arrays of type bits[1][18][7][10][10] (12,600 elements of 1-bit) using ne triggers a hang in LLVM's optimization passes.

Root Cause

LLVM's ConstraintEliminationPass hangs during optimization of the generated LLVM IR. The stack trace of the hung process shows it is stuck in ConstraintInfo::addFactImpl called from eliminateConstraints.

Minimized DSLX

const W32_V10 = u32:10;
const W32_V18 = u32:18;
const W32_V7 = u32:7;
type x0 = u1;
type x1 = x0[W32_V18];
type x2 = x1[W32_V7];
type x3 = x2[W32_V10];

fn main(x: x3[W32_V10], y: x3[W32_V10]) -> bool {
    x != y
}

Reproduction Steps

1. Convert the DSLX to IR:

   ir_converter_main minimized.x > minimized.ir

2. Run eval_ir_main with JIT enabled:

   eval_ir_main --test_llvm_jit --random_inputs=1 --top=__minimized__main minimized.ir

   This command will hang.

Stack Trace

*** SIGTERM received by PID 35063 (TID 35063) on cpu 1, si_code=0, from PID 35062; stack trace: ***
PC: @     0x55f70a0b6ce0  (unknown)  FailureSignalHandler()
    @     0x55f70a0b7088       1904  FailureSignalHandler()
    @     0x7f544cd67c60  202195888  (unknown)
    @     0x55f706c17432        640  (anonymous namespace)::ConstraintInfo::addFactImpl()
    @     0x55f706c0927d       7200  eliminateConstraints()
    @     0x55f706c04e4f        112  llvm::ConstraintEliminationPass::run()
    @     0x55f7079a10d9        208  llvm::PassManager<>::run()
    ...
    @     0x55f70508505f       2992  xls::LlvmCompiler::PerformStandardOptimization()
    @     0x55f704fd7d9b        240  xls::OrcJit::Optimizer()