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: ff5e2ba

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

#include <stdio.h>
#include <unistd.h>
#include <stdint.h>

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 google/xls#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 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.