Teaching LLVM a trick it already knew

On this page

• The easy part: why it’s always correct
• The hard part: five things that have to hold
• In the source
• The tests are the spec
• Small patch, real lesson

Teaching LLVM a trick it already knew

There are two ways to get the same answer, and one is cheaper. LLVM knew the cheaper one all along, just not in the part of the compiler that decides what's cheap.

26 September 2026 · Rahul Yadav

Here’s the whole trick in one picture. You have two 16-bit numbers and need their `and` as a 32-bit number. Widen both and then combine them, or combine them and widen once:

ab0…0a0…0band0…0a & babanda & b0…0a & bzextzextzextsame bitsWiden first · 2 conversionsCombine first · 1 conversion

One lane shown. A vector does this to every lane at once.

Both paths end with the same bits. Widening fills the top half with zeros on both sides, and zero `and` zero is still zero. The second path gets there with one conversion instead of two, and its `and` works on half the bits.

In LLVM IR, with a vector of four 16-bit lanes, the first path is:

%z1  = zext <4 x i16> %a to <4 x i32>
%z2  = zext <4 x i16> %b to <4 x i32>
%and = and  <4 x i32> %z1, %z2

And the second:

%and.inner = and  <4 x i16> %a, %b
%and       = zext <4 x i16> %and.inner to <4 x i32>

LLVM has made this rewrite since at least 2017. It lives in InstCombine, the general cleanup pass that runs again and again during optimization. But InstCombine has no cost model, so it plays safe with a rule of thumb: rewrite only if at least one of the two casts goes away.

Real vector code often falls outside that rule. In issue #66513, an x86 blend took its mask from comparison results combined with `and` and `xor`, and each mask was used more than once. Both casts had to stay, so InstCombine left the `and` alone, and LLVM couldn’t turn the blend into a plain select.

VectorCombine can say yes in cases like that. Before it rewrites vector code, it asks the target what the old and new versions cost, and a `bitcast` costs nothing even when it has to stay. A `bitcast` version of the fold landed in June 2025 and fixed that blend. My patch, llvm/llvm-project#148350, extended it to `trunc`, `sext` and `zext`, for `and`, `or` and `xor`, so VectorCombine can weigh the rewrite for every cast InstCombine handles. It shipped in LLVM 22, and others have since built on it.

So yes, LLVM learned something it already knew, and that’s normal. Proving a rewrite correct is the easy part. Deciding when it pays off is the hard part, and each pass answers that in its own way.

The easy part: why it’s always correct

Bitwise operations work one bit at a time. Each output bit depends only on the two input bits in the same position. And these four casts only move bits around: they drop some, pad with zeros, pad with copies of the sign bit, or relabel the same bits. So it doesn’t matter whether you combine before or after the cast:

| Cast | What it does to the bits | Why combining first gives the same answer | | ------- | -------------------------------- | ------------------------------------------------------------------------ | | trunc | Drops the high bits | The same high bits get dropped from the result | | zext | Pads with zeros | 0 and 0, 0 or 0 and 0 xor 0 are all 0 | | sext | Pads with copies of the sign bit | The result’s sign bit is the two sign bits combined, so its copies match | | bitcast | Relabels the same bits | Nothing moves at all |

`sext` is the one worth a second look. After `sext`, every padding bit of `%a` equals the sign bit of `%a`, and the same for `%b`. Combine them and every padding bit becomes `sign(a) op sign(b)`, which is exactly the sign bit of `a op b`. So `sext(a op b)` writes the same bits.

The hard part: five things that have to hold

Rewrites like this are easy to get almost right. The patch checks five things before it touches anything.

1. Both sides use the same cast. `zext(a) and sext(b)` doesn’t fold, because the padding bits differ: zeros on one side, sign copies on the other. There’s a test that makes sure it’s left alone.

2. Both sides start from the same type. Combining an `i16` with an `i8` before the cast isn’t even well-formed IR. Left alone, with a test.

3. Vectors with integer lanes only. VectorCombine is about vector code, so scalars are left to InstCombine. There’s a test that makes sure they’re left alone.

4. The new form has to be cheaper. LLVM asks the target what each instruction costs. The old form pays for the logic op on the cast’s result type plus two casts. The new form pays for the logic op on the source type plus one cast. If either original cast has other users, it can’t be deleted, so its cost is added to the new side too. The fold only happens when the new side doesn’t cost more.

That multi-use case has a test of its own. `%z1` is also used by an `add`, so it has to stay:

; before
%z1  = zext <4 x i16> %a to <4 x i32>
%z2  = zext <4 x i16> %b to <4 x i32>
%and = and  <4 x i32> %z1, %z2
%add = add  <4 x i32> %z1, %and
; after
%z1        = zext <4 x i16> %a to <4 x i32>
%and.inner = and  <4 x i16> %a, %b
%and       = zext <4 x i16> %and.inner to <4 x i32>
%add       = add  <4 x i32> %z1, %and

5. Flags have to stay true. Casts can carry promises. `trunc nuw` says the dropped bits were all zero, and `zext nneg` says the input wasn’t negative. The new cast keeps only the flags that both original casts had. That’s safe: if both inputs promise their high bits are zero, `and`, `or` and `xor` keep those bits zero too. So `trunc nuw nsw` on both sides becomes `trunc nuw nsw` on the result, and `zext nneg` stays `zext nneg`.

In the source

The `bitcast` version was a fold called `foldBitOpOfBitcasts`, which turned `bitop(bitcast(x), bitcast(y))` into `bitcast(bitop(x, y))`. The patch generalized it and renamed it `foldBitOpOfCastops` to match. It lives in `llvm/lib/Transforms/Vectorize/VectorCombine.cpp`.

The tests are the spec

The patch adds 20 tests in `llvm/test/Transforms/VectorCombine/X86/bitop-of-castops.ll`:

• every cast with every logic op,
• the cases that must not fold: mismatched casts, mismatched source types and scalars,
• the multi-use case,
• the flag cases.

Reading them top to bottom tells you what the fold does and what it refuses to do, which is the most useful thing a compiler test file can be.

To watch it run, you need LLVM 22 or newer. Save the first snippet above as a function in a `.ll` file and run:

opt -passes=vector-combine -mtriple=x86_64-- -S example.ll

Swap in `-passes=instcombine` and InstCombine makes the same rewrite, even on a much older LLVM.

Small patch, real lesson

The diff is a few dozen lines. The rewrite itself was never the hard part. LLVM has known it since 2017, and the proof fits in a table. The work was everything around it: asking the target whether it pays, keeping the flags honest, and pinning down the cases that must not fold. That’s most of compiler work, and a small fold is a good place to learn it.