google / google/xls

JIT compile hang in LLVM ConstraintEliminationPass for large array comparisons

Open
#4,508 0 comments 0 reactions 0 assignees View on GitHub
bug fuzz jit
Dominant language
C++
Stars
1.9k
Forks
283
Avg merge
2d 10h
Merged PRs (30d)
135

Description

### 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
```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:
```bash
ir_converter_main minimized.x > minimized.ir
```
2. Run `eval_ir_main` with JIT enabled:
```bash
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()
```

Contributor guide

Open the contributing guide

Research direction

Start by reproducing the hang by converting minimized.x with ir_converter_main and running eval_ir_main --test_llvm_jit --random_inputs=1 --top=__minimized__main. Trace xls::LlvmCompiler::PerformStandardOptimization and xls::OrcJit::Optimizer to confirm the generated LLVM IR reaches ConstraintEliminationPass; done means the minimized large-array comparison no longer hangs under LLVM JIT.

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.