Cranelift x86_64 Fix: bitselect Not Implemented for Scalars

The crash happens because Cranelift can represent bitselect on scalar values in its IR, but the x86_64 backend historically focused on vector-friendly lowering patterns for this operation. When fuzzing generates a scalar bitselect such as an i12, instruction selection reaches a backend path with no legal scalar lowering rule, so codegen fails even though the IR itself is valid.

Understanding the Root Cause

At a bit level, bitselect(c, x, y) means: choose bits from x where the mask c has 1s, otherwise choose bits from y. The canonical identity is:

(x & c) | (y & ~c)

or equivalently:

y ^ ((x ^ y) & c)

The issue on x86_64 appears when the legalizer or lowering pipeline does not rewrite scalar bitselect into one of these primitive forms before instruction selection. Unlike some vector cases, there is no single generic scalar machine instruction named bitselect that the backend can emit directly across all CPUs. As a result, the backend needs either:

• a dedicated lowering rule for scalar bitselect, or
• a legalization step that expands it into supported scalar operations like and, or, xor, and not.

This bug is especially visible with narrow integer types like i12, because non-power-of-two widths often pass through additional legalization and register-class handling. If the scalar form survives too long in the pipeline, backend matching fails.

In short, the root cause is a missing scalar lowering path in the x86_64 ISA backend for an IR instruction that is semantically valid but not directly encodable.

Step-by-Step Solution

The most robust fix is to lower scalar bitselect into standard integer operations before final x86_64 emission. This keeps semantics correct and works on all x86_64 CPUs without requiring specialized instructions.

1. Reproduce the failure

Start with the failing .clif test generated by fuzzing. The issue description indicates a case similar to:

test interpret
test run
set enable_llvm_abi_extensions=true
target x86_64

function %a(i12, i12, i12) -> i12 {
block0(v0: i12, v1: i12, v2: i12):
    v3 = bitselect v0, v1, v2
    return v3
}

Run it through the Cranelift test harness and confirm that interpretation succeeds while native x86_64 codegen fails.

2. Choose a scalar expansion strategy

Use one of the standard identities. A good backend-friendly form is:

result = (x & c) | (y & ~c)

This maps naturally to scalar integer instructions and is easy to legalize for unusual widths.

3. Add legalization or lowering for scalar bitselect

Depending on the Cranelift version and backend structure, implement the fix in the legalization layer or in x86_64 lowering. The preferred approach is usually to expand earlier so all backends benefit consistently.

A conceptual legalization rewrite looks like this:

fn expand_bitselect_scalar(mask, x, y):
    let not_mask = bnot(mask)
    let lhs = band(x, mask)
    let rhs = band(y, not_mask)
    return bor(lhs, rhs)

If your legalization framework distinguishes vectors from scalars, make the rule explicit:

if opcode == bitselect && ty.is_int() && ty.is_scalar() {
    replace bitselect(mask, x, y)
    with bor(band(x, mask), band(y, bnot(mask)))
}

4. Preserve narrow integer semantics

For widths like i12, make sure the transformation respects the type’s lane width and does not accidentally widen without truncation. If your backend legalizes narrow integers through a larger container type such as i16 or i32, insert truncation or rely on existing narrow-int rules consistently.

tmp0 = band(x, mask)
tmp1 = bnot(mask)
tmp2 = band(y, tmp1)
tmp3 = bor(tmp0, tmp2)
result = ireduce.i12 tmp3

Whether ireduce is necessary depends on where in the pipeline the rewrite occurs. If the IR nodes already enforce i12 semantics, an extra reduction may be redundant. The key is to avoid leaking high bits after widening.

5. Add or update backend tests

Create focused regression coverage for scalar widths, especially the fuzzed case. Include both interpreter and run tests where possible.

test interpret
test run
set enable_llvm_abi_extensions=true
target x86_64

function %bitselect_scalar_i12(i12, i12, i12) -> i12 {
block0(v0: i12, v1: i12, v2: i12):
    v3 = bitselect v0, v1, v2
    return v3
}

Also add a few neighboring widths to prevent future regressions:

i8, i16, i32, i64, i128

6. Verify generated code

On x86_64, the lowered form should become combinations of AND, OR, XOR, and possibly NOT-equivalent patterns. Depending on register allocation and optimization, you might see variants such as:

tmp = x ^ y
tmp = tmp & mask
result = tmp ^ y

This form is also correct and sometimes more efficient. What matters is that there is no remaining raw scalar bitselect at the point where x86_64 instruction selection runs.

7. Submit the patch cleanly

Your final change set should usually include:

• a legalization or lowering implementation for scalar bitselect,
• a regression test for the original fuzzed case,
• optional additional width coverage to protect narrow integer handling.

A concise patch summary might read: implement scalar bitselect expansion on x86_64 by rewriting to and/or/not primitives during legalization.

Common Edge Cases

Non-standard integer widths

Types like i12, i24, or i1 may be represented in larger physical registers. If high bits are not masked or reduced correctly, the expanded sequence can produce wrong results.

Sign-related confusion

bitselect is a bitwise operation, not a signed comparison. Do not use arithmetic sign logic when lowering it. The implementation must preserve raw bit patterns only.

Vector versus scalar paths

If vectors already work, avoid accidentally changing vector lowering behavior while fixing scalars. Keep the condition explicit so only scalar integer types take the new expansion path.

Optimization reordering

Later optimization passes may rewrite (x & c) | (y & ~c) into an xor/and/xor sequence or something equivalent. That is fine as long as type-width semantics remain intact.

Backend-specific assumptions

If the expansion is added only in the x86_64 backend, other architectures may still fail on scalar bitselect. If possible, place the rewrite in a shared legalization layer so the fix is architecture-agnostic.

FAQ

Why does the interpreter pass but x86_64 codegen fail?

The interpreter executes Cranelift IR semantics directly, so bitselect is understood as a valid IR instruction. The x86_64 backend must translate that IR into real machine instructions, and that translation path for scalar bitselect was missing.

Why is i12 specifically useful for exposing this bug?

Narrow, unusual widths stress legalization paths that common widths like i32 and i64 may not. Fuzzers often find backend gaps by generating legal but uncommon types that bypass typical hand-written test coverage.

Should this be fixed in legalization or instruction lowering?

Usually legalization is the better place because bitselect can be expanded into universally supported primitive operations. That reduces backend complexity and helps all targets, not just x86_64.

By rewriting scalar bitselect into primitive bitwise operations and validating narrow-width behavior, you eliminate the x86_64 backend crash and make Cranelift substantially more robust against future fuzz-generated IR.