Cranelift bug: why uextend.i128 collapses into iconst.i128 under egraphs, and how to fix it safely

This issue is a classic rewrite unsoundness: a zero-extension from a smaller integer type to i128 is being treated as if it were equivalent to a plain constant materialization in the larger type. When the egraph optimizer folds that transform too aggressively, it can erase the semantic distinction between “extend this value” and “create this exact 128-bit constant,” producing an invalid optimization.

In Cranelift IR, uextend preserves the numeric value of the source operand while changing its bit width by inserting zeroes in the upper bits. That is only equivalent to an iconst.i128 when the source is already proven to be a compile-time constant and the extension is performed with the correct source-width semantics. If the egraph rewrite skips that proof or reconstructs the constant from the wrong type domain, the result is semantically incorrect.

Understanding the Root Cause

The bug appears because the egraphs optimization pipeline is likely applying a rewrite that assumes:

uextend.i128(x)  ==  iconst.i128(K)

under conditions that are too broad. The valid version of this rewrite is much narrower:

uextend.i128(iconst.iN K)  ==  iconst.i128(zext_N_to_128(K))

where N is the source type width and zext_N_to_128 means zero-extending from exactly that width to 128 bits.

There are several ways this can go wrong in a compiler optimizer:

• The rewrite matches uextend without checking that the operand is a literal constant.
• The rewrite constant-folds using the destination type only, ignoring the source lane width.
• The rewrite reuses a generic integer-constant canonicalization rule that is sound for smaller types but not for i128.
• The egraph extractor chooses a cheaper iconst.i128 node even though equivalence was established incorrectly.

For the reported fuzz case, the suspicious pattern starts from a small constant like:

v0 = iconst.i64 0
v1 = uextend.i128 v0

In this exact example, folding to iconst.i128 0 is actually fine. The issue is that the rewrite machinery appears to generalize that equivalence in a way that later affects non-trivial inputs. Fuzzers often expose these bugs by first finding a harmless-looking reduction that points to an unsound rule in the optimizer.

So the true root cause is not “constant folding is bad,” but that the egraph equivalence class is being populated with an invalid identity. Once that happens, extraction can legally pick the wrong form because the optimizer has already been told the nodes are equivalent.

Step-by-Step Solution

The safest fix is to tighten the egraph rewrite so that it only fires when the operand is a known constant and the zero-extension is computed from the source type width. In practice, you should also add regression tests that cover both valid folds and invalid generalizations.

1. Locate the egraph rewrite for integer extension

Search the Cranelift source for rewrite rules related to uextend, iconst, or integer constant folding in the egraph pass.

git grep -n "uextend"
git grep -n "iconst"
git grep -n "egraph"

You are looking for code that effectively turns an extension of a value into a constant in the destination type.

2. Restrict the fold to literal constants only

If the current rule matches any expression node, change it so it only fires when the operand is an iconst with a known source bit width.

// Pseudocode: only fold when the input is literally a constant.
match inst {
    Inst::UExtend { val, dst_ty } => {
        if let Some((src_ty, k)) = get_iconst(val) {
            let folded = zero_extend_from_width(k, src_ty.bits(), dst_ty.bits());
            return Some(iconst(dst_ty, folded));
        }
        None
    }
    _ => None,
}

The important detail is that the fold must use src_ty.bits(), not just “reinterpret the constant as 128-bit.”

3. Encode the width-aware zero-extension correctly

For i128, avoid accidental sign propagation or host-language truncation. Compute the result with explicit masking before extension if needed.

// Pseudocode for width-safe zero extension.
fn zero_extend_from_width(k: u128, src_bits: u8, dst_bits: u8) -> u128 {
    debug_assert!(src_bits <= dst_bits);
    let mask = if src_bits == 128 {
        u128::MAX
    } else {
        (1u128 << src_bits) - 1
    };
    k & mask
}

If the source constant is stored in a signed representation internally, normalize it before masking so that the semantic value reflects the source bit width.

4. Prevent unsound equivalence insertion in the egraph

If the bug comes from a declarative rewrite rule rather than a local folder, refine the rule condition. For example, do not express a general equivalence like this:

(uextend x)  =>  (iconst C)

Instead, require a constant predicate and a computed replacement:

if is_iconst(x) and src_width_known(x):
    replace (uextend.i128 x)
    with    (iconst.i128 zext(value(x), width(x)))

In an egraph system, conditional rewrites are critical because an unsound equality pollutes the whole equivalence class.

5. Add a targeted regression test

Create a test that covers both the valid fold case and a case where folding must not happen unless the operand is proven constant.

test compile
set opt_level=speed
target x86_64

function %valid_fold() -> i128 system_v {
block0:
    v0 = iconst.i64 0
    v1 = uextend.i128 v0
    return v1
}

function %must_not_generalize(v0: i64) -> i128 system_v {
block0(v0: i64):
    v1 = uextend.i128 v0
    return v1
}

Then verify the generated IR or optimization output does not replace the second function with a fixed iconst.i128.

6. Add a negative fuzz-style test for non-zero values

Zero often hides bugs because many wrong transforms still produce zero. Include values that exercise upper-bit behavior.

test compile
set opt_level=speed
target x86_64

function %check_values() -> i128 system_v {
block0:
    v0 = iconst.i8 255
    v1 = uextend.i128 v0
    return v1
}

This should produce 255 in i128, not a sign-extended value and not an incorrectly reconstructed constant based on a mismatched width.

7. Run the relevant test suites

cargo test -p cranelift-codegen
cargo test -p cranelift-filetests

If you have a dedicated command for filetests or egraph-specific optimization tests in your checkout, run that as well before opening the patch.

Common Edge Cases

• Zero hides the bug: uextend.i128(iconst.i64 0) and iconst.i128 0 are equivalent, so a test using only zero may not prove the rewrite is sound.
• Sign-extension confusion: do not accidentally use logic appropriate for sextend. For example, 0xFF from i8 zero-extends to 255, while sign-extending would produce -1 in two’s complement semantics.
• Source-width mismatch: folding from i8, i16, i32, and i64 must all respect the original width. The same numeric storage value can mean different things depending on the source type.
• Host integer overflow: if folding code uses native integer types carelessly, shifts like 1 << 128 or intermediate casts can overflow or panic. Special-case 128-bit masks.
• Egraph extraction bias: even if the local fold looks harmless, an unsound equality inside the egraph can lead the extractor to pick a constant because it appears cheaper. Fix the equality source, not just the final selected node.
• Vector or lane-based extension rules: if similar patterns exist for vector lanes, verify the scalar fix does not leave equivalent bugs in lane-wise extension rewrites.

FAQ

Why is replacing uextend.i128 with iconst.i128 sometimes valid?

It is valid only when the operand is a proven compile-time constant and the replacement constant is computed using the source type’s bit width. In that narrow case, the extension result is itself a constant, so folding is correct.

Why does this show up specifically with egraphs?

Egraph optimizers work by building equivalence classes of expressions and then extracting the cheapest form. If a rewrite adds an unsound equivalence, the system may later choose a wrong-but-cheap node like iconst.i128. The visible failure happens at extraction time, but the actual bug is usually in the rewrite rule or analysis condition.

What is the best regression test for this issue?

Use at least three cases: a foldable constant zero case, a foldable non-zero constant case such as i8 255, and a non-constant input case where uextend.i128 must remain value-dependent. That combination catches both accidental generalization and width-handling mistakes.

Once patched, this issue becomes a good example of a broader compiler engineering lesson: constant folding must preserve typed semantics, and in an egraph pipeline, every rewrite must be stronger on correctness than on profitability.