ConstraintEliminationPass incorrectly replaces a i256 ne with a constant false.

[allight]

manual_min.ll is a llvm ir program that displays a miscompile.

This reproduces using llvm as of commit: https://github.com/llvm/llvm-project/commit/ff5e2babcb46e7eb3887ee265decb2948da2792c

Unfortunately due to not causing any crash I was unable to minimize it any more than this since whatever I tried bugpoint would either reduce it to nothing or not change anything.

Bug code is generated from an xls program below:

DSLX

``` fn main(x4: u51) -> bool { let x5: u51 = bit_slice_update(x4, x4, x4); let x6: uN[102] = x5 ++ x5; let x9: uN[153] = x6 ++ x5; let gate_src: bool = x6 as uN[153] != x9; gate_src } ```

XLS IR

``` package crasher_manual_min2 file_number 0 "xls/fuzzer/crashers/crasher_manual_min2.x" fn __crasher_manual_min2__main(x4: bits[51]) -> bits[1] { // bit_slice_update(a, b, c) returns 'a' with bits starting at index 'b' replaced with the bits of 'c' x5: bits[51] = bit_slice_update(x4, x4, x4, id=2, pos=[(0,54,38)]) x6: bits[102] = concat(x5, x5, id=3, pos=[(0,55,29)]) zero_ext.5: bits[153] = zero_ext(x6, new_bit_count=153, id=5) x9: bits[153] = concat(x6, x5, id=4, pos=[(0,56,29)]) ret gate_src: bits[1] = ne(zero_ext.5, x9, id=6, pos=[(0,58,43)]) } ```

This is compiled using the xls jit compiler to LLVM. This code is linked with a runner below which simply executes this program on the numbers [0, 256] and prints each result. This should result in a zero byte followed by all 0x1 bytes.

% cat manual_min_runner.bc | lli | hd
00000000  00 01 01 01 01 01 01 01  01 01 01 01 01 01 01 01  |................|
00000010  01 01 01 01 01 01 01 01  01 01 01 01 01 01 01 01  |................|
*
00000100

Runner code

```c #include #include #include extern char __crasher_manual_min2__main(void* inputs, void* outputs, void* buf, void* events, void* user_data, void* rt, long long int cont); typedef int64_t i64; // returns a bool char tryone(i64 v) { void* inp_ptr[1]; i64 bit64 = v; inp_ptr[0] = &bit64; void* out_ptr[1]; char val = 0; out_ptr[0] = &val; void* temp_buf[1]; void* user_data[1]; __crasher_manual_min2__main(inp_ptr, out_ptr, temp_buf, 0, 0, 0, 0); return val; } int main() { // return (tryone(1) << 1) | tryone(0); for (int i = 0; i < 256; ++i) { char r = tryone(i); write(1, &r, sizeof(char)); } return 0; } ```

However in the 349th pass (ConstraintEliminationPass) a miscompile occurs and after that pass the program will always print all 0s.

 % cat manual_min_runner.opt.bc | lli | hd
00000000  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
00000100

This is based on the investigation for https://github.com/google/xls/issues/1146

Repro build process:

% opt manual_min.llvm.ir --O3 -opt-bisect-limit=$current_id > bisect_manual_min.llvm.opt.bc
% clang -S -emit-llvm manual_min_runner.c -o manual_min_runner.ll
% opt manual_min_runner.ll > manual_min_runner_driver.bc
% llvm-link  bisect_manual_min.llvm.opt.bc manual_min_runner_driver.bc > bisect_manual_min_runner.opt.bc

The bitcode can be run by lli or compiled further. It doesn't seem to affect the miscompile.

[ericastor]

I was able to write a script that let bugpoint minimize the example, testing for whether the output differs between -O1 and -O3. This cut it down to a 92 line .ll file.

bugpoint minimized example: bugpoint-reduced-simplified.ll

[allight]

git bisect fingers commit https://github.com/llvm/llvm-project/commit/04f9a8a7d67d as the culprit. I imagine that something about the reassociation, TCO or simplify-cfg passes going before did is what allows the ConstraintEliminationPass to incorrectly optimize the compare away.

Not sure how to continue to bisect from here tbh.

[allight]

@fhahn FYI since you seem to be the owner of ConstraintElimination.

[nikic]

Here is a CE-only test case: https://alive2.llvm.org/ce/z/CYsPCf

[nikic]

Cleaner reduction: https://alive2.llvm.org/ce/z/K6-nPv

define i1 @src(i128 %arg) {
  %mul = mul nuw nsw i128 %arg, 4294967297
  %shl = shl nuw nsw i128 %mul, 32
  %add = add nuw nsw i128 %shl, %arg
  %cmp = icmp eq i128 %add, %mul
  ret i1 %cmp
}

[nikic]

Another variant that makes the root cause more obvious: https://alive2.llvm.org/ce/z/P9veTT

define i1 @src(i128 %arg) {
  %shl1 = shl nuw nsw i128 %arg, 32
  %shl2 = shl nuw nsw i128 %shl1, 32
  %cmp = icmp eq i128 %shl2, 0
  ret i1 %cmp
}

When decomposing, we check that the individual values fit in 63-bits and that everything has the necessary nowrap flags. But we don't account for the possibility that we are working on values wider than 64-bit and might be non-wrapping in the wider bit width while making our 64-bit coefficients wrap.

[nikic]

/cherry-pick 2b74db6c9bff757ce016d62a7086617e2b9e43b3 1d43096e16ff7288c7feac1ae81fd4f745ce10bb

[llvmbot]

Failed to cherry-pick: 1d43096e16ff7288c7feac1ae81fd4f745ce10bb

https://github.com/llvm/llvm-project/actions/runs/6532190811

Please manually backport the fix and push it to your github fork. Once this is done, please add a comment like this:

/branch <user>/<repo>/<branch>

[nikic]

/branch nikic/llvm-project/constraintelim-backport

[llvmbot]

/pull-request llvm/llvm-project-release-prs#734