evaluation missmatch between JIT and IR interpreter

[proppy]

Description

The XLS fuzzer found a JIT mismatch on optimized IR.
Specifically, evaluated opt IR (JIT) miscompared with evaluated opt IR (interpreter) and unoptimized IR.

Miscompare Details:

args: bits[15]:0x2aaa; bits[2]:0x2 evaluated opt IR (JIT) = (bits[15]:0x2aab, bits[2]:0x2, (bits[14]:0x1555, bits[49]:0x0, bits[39]:0x58_c1d6_b1d9), bits[1]:0x1) evaluated opt IR (interpreter), evaluated unopt IR (JIT), evaluated unopt IR (interpreter), interpreted DSLX, simulated = (bits[15]:0x2aab, bits[2]:0x2, (bits[14]:0x1555, bits[49]:0x1_ffff_ffff_ffff, bits[39]:0x1_0000_0000), bits[1]:0x1)

The differences are in:

• bits[49]: 0x0 (JIT) vs 0x1_ffff_ffff_ffff (Expected)
• bits[39]: 0x58_c1d6_b1d9 (JIT) vs 0x1_0000_0000 (Expected)
  This corresponds to sign_ext.428 and concat.321 in the optimized IR.
  The selector concat.77 for the priority selects in concat.321 seems to have evaluated incorrectly in JIT (selecting case 0 instead of case 1).

Repro steps

Run the regression test (once the CL is submitted or by using the crasher file directly):

blaze test //third_party/xls/fuzzer:crasher_2026-05-21_c47d_test

[proppy]

gemini-3.5-flash came up with this root-cause analysis, @allight @scampanoni does the llvm-fu below look sound?

XLS JIT Fuzzer Failure Analysis

We have investigated the recent fuzzer failure from target //xls/fuzzer:fuzz_integration_test.

1. Executive Summary

• Symptom: Result miscompare in optimized IR JIT vs Interpreter.
• Isolated Repro: We successfully isolated the bug into a small IR file test.ir.
• Trigger: The bug is triggered only at LLVM optimization levels > 0 (--llvm_opt_level=3). At --llvm_opt_level=0, the JIT matches the interpreter (returns correct result).
• Root Cause: An LLVM codegen bug (X86 backend). LLVM incorrectly optimizes a pattern involving or, select, and icmp into an assembly sequence (add + sbb + setb) that uses raw, unmasked i8 register values containing garbage padding bits, instead of the masked (clean) bits[1] value.

---

2. Detailed Isolation & Repro

The original failure reported:

INVALID_ARGUMENT: SampleError: Result miscompare for sample 1:
args: bits[15]:0x2aaa; bits[2]:0x2
evaluated opt IR (JIT) =
   (bits[15]:0x2aab, bits[2]:0x2, (bits[14]:0x1555, bits[49]:0x0, bits[39]:0x58_c1d6_b1d9), bits[1]:0x1)
evaluated opt IR (interpreter) =
   (bits[15]:0x2aab, bits[2]:0x2, (bits[14]:0x1555, bits[49]:0x1_ffff_ffff_ffff, bits[39]:0x1_0000_0000), bits[1]:0x1)

We isolated the failure to this minimal XLS IR test.ir:

package sample

top fn main(x0: bits[15], x1: bits[2]) -> (bits[15], bits[1], bits[1], bits[1]) {
  bit_slice.232: bits[1] = bit_slice(x0, start=0, width=1)
  bit_slice.233: bits[14] = bit_slice(x0, start=1, width=14)
  x13__1: bits[1] = not(bit_slice.232)
  x13: bits[15] = concat(bit_slice.233, x13__1)
  
  literal.43: bits[15] = literal(value=10922)
  ult.45: bits[1] = ult(x13, literal.43)
  
  literal.253: bits[14] = literal(value=5461)
  eq.242: bits[1] = eq(bit_slice.233, literal.253)
  and.245: bits[1] = and(eq.242, bit_slice.232)
  
  or.49: bits[1] = or(ult.45, and.245)
  
  ret tuple.1: (bits[15], bits[1], bits[1], bits[1]) = tuple(x13, ult.45, and.245, or.49)
}

Evaluation Results (x0 = 0x2aaa, x1 = 0x2):

• Expected (Interpreter & JIT Opt 0): (0x2aab, 0, 0, 0)
• Actual (JIT Opt 3): (0x2aab, 0, 0, 1) <-- or.49 is incorrectly evaluated as 1!

---

3. Root Cause Analysis (LLVM Codegen Bug)

By dumping the LLVM IR and generated X86 assembly (using --vmodule=orc_jit=3 --logtostderr), we traced the compilation of or.49.

LLVM IR Level (Correct)

LLVM successfully optimized the or.49 logic:

  ; %3 is bit_slice.233 (5461)
  ; %5 is eq.242 (true)
  ; %6 is ult.45 (false)
  ; %8 is bit_slice.232 (0)
  %7 = zext i1 %6 to i8              ; %7 = 0
  %9 = select i1 %5, i8 %8, i8 0     ; %9 = 0 (since %8 is 0)
  %10 = or i8 %9, %7                 ; %10 = 0

This IR is semantically correct and evaluates %10 (or.49) to 0.

X86 Assembly Level (Incorrect)

LLVM's X86 backend tried to compile the or + select + icmp combination into a clever branchless sequence using sbb (subtract with borrow):

__XLS__main:
	movq	(%rdi), %rax
	movzwl	(%rax), %eax    ; %eax = x0 (0x2aaa = 10922)
	movl	%eax, %ecx
	shrl	%ecx
	andl	$16383, %ecx    ; %ecx = 5461 (bit_slice.233)
	movl	%eax, %edx
	andl	$32767, %edx
	xorl	$1, %edx        ; %edx = 10923 (x13)
	cmpl	$5461, %ecx     ; Compare %ecx (5461) with 5461
	sete	%dil            ; %dil = 1 (eq.242)
	movq	(%rsi), %rsi
	setb	2(%rsi)         ; 2(%rsi) = ult.45 (sets to 0, correct)
	andb	%al, %dil       ; %dil = %dil & %al (and.245, correct because we check LSB of %al later? No...)
	addb	$-1, %al        ; <-- BUG TRIGGER! %al is raw x0 LSB (0xaa = 170).
                            ; 0xaa + 0xff = 0x1a9 -> Sets Carry Flag (CF) = 1.
	sbbw	$5461, %cx      ; %cx = 5461 - 5461 - CF(1) = -1 (0xffff). Sets CF = 1.
	movw	%dx, (%rsi)
	movb	%dil, 3(%rsi)   ; 3(%rsi) = and.245 (stores 0, correct)
	setb	4(%rsi)         ; <-- BUG EFFECT! Stores CF (1) to or.49!
	xorl	%eax, %eax
	retq

Why did LLVM make this mistake?

1. XLS JIT represents bits[1] as i8 in LLVM (because LLVM < 8 bit types can have issues in some backends).
2. LLVM optimized the select by assuming that the input %al was a clean i1 value (only 0 or 1) because it was derived from a bits[1] XLS type.
3. If %al were indeed clean (0 or 1):
   • If %al is 1: addb $-1, 1 -> CF = 1.
   • If %al is 0: addb $-1, 0 -> CF = 0.
     This would make the addb + sbbw + setb sequence correct.
4. However, %al was NOT clean. It contained the raw bits 0-7 of x0 (0xaa = 170). Although XLS JIT cleared the padding bits for the evaluated bit_slice.232 node (stored in %dil), the LLVM optimizer bypassed this and went back to the raw %al register, incorrectly assuming it was clean.
5. Because 0xaa != 0, addb $-1, %al generated a carry (CF=1), which incorrectly propagated to or.49 as 1.

---

4. Next Steps & Recommendations

• File a Bug: We should file a compiler bug against LLVM (or internal toolchain team) with this X86 codegen miscompile repro.
• Workaround in XLS JIT:
  • We could investigate if we can force XLS JIT to use native LLVM i1 for bits[1] instead of i8, which might prevent LLVM from making incorrect assumptions about padding bits in i8 registers.
  • Alternatively, ensure that LLVM is not allowed to see the raw unmasked values when optimizing select operations on narrow bit widths.

[proppy]

result of running dump_llvm_artifacts on the minimal test.ir:

define noundef i1 @____XLS__main_partition_0(ptr readonly captures(none) %input_ptrs, ptr readonly captures(none) %output_ptrs, ptr readnone captures(none) %tmp_buffer, ptr readnone captures(none) %events, ptr readnone captures(none) %instance_context, ptr readnone captures(none) %runtime) local_unnamed_addr #0 {
entry:
  %0 = load ptr, ptr %input_ptrs, align 8
  %.val = load i16, ptr %0, align 2
  %1 = trunc i16 %.val to i8
  %2 = lshr i16 %.val, 1
  %3 = and i16 %2, 16383
  %urem = and i16 %.val, 32767
  %4 = xor i16 %urem, 1
  %5 = icmp eq i16 %3, 5461
  %6 = icmp samesign ult i16 %3, 5461
  %7 = zext i1 %6 to i8
  %8 = and i8 %1, 1
  %9 = select i1 %5, i8 %8, i8 0
  %10 = or i8 %9, %7
  %11 = load ptr, ptr %output_ptrs, align 8
  store i16 %4, ptr %11, align 1
  %12 = getelementptr i8, ptr %11, i64 2
  store i8 %7, ptr %12, align 1
  %13 = getelementptr i8, ptr %11, i64 3
  store i8 %9, ptr %13, align 1
  %14 = getelementptr i8, ptr %11, i64 4
  store i8 %10, ptr %14, align 1
  ret i1 false
}

[allight]

I'm not exactly familiar enough with all the intricacies of x64 instructions to evaluate this fully but this does seem like a reasonable explanation. @scampanoni ?