Encoding vcmpps and vcmppd

The x86 / x86-64 instruction sets have many instructions for comparing IEEE754 floating-point numbers. Casey Muratori recently asked about two of them:

It would be great if someone from Intel would share the rationale behind the immediate bit pattern of the AVX CMP instructions (eg., vcmppd, vcmpps). I've stared at it many times and it just seems "pure banacakes", as Jeff would say.

I can attempt to explain the immediate bit pattern of vcmpps and vcmppd, but it makes most sense to start somewhere else: the comiss and ucomiss instructions. These instructions compare two floats (say A and B) and then set flags based on the result. IEE754 floats have the convenient property that exactly one of these four statements is true:

1. A > B
2. A == B
3. A < B
4. A is unordered with respect to B (i.e. at least one of them is a NaN)

That fourth case is a bit of a mouthful, so I'll write it as A unord B from here on. When comparing A and B, the comiss and ucomiss instructions determine which case applies, and set the CF and ZF flags accordingly:

	A > B	A == B	A < B	A unord B
CF set to:	0	0	1	1
ZF set to:	0	1	0	1

(These instructions also set PF, but always as PF = CF & ZF, so for our purposes it suffices to look at just CF and ZF.)

The difference between comiss and ucomiss is how "loud" they are with respect to quiet NaNs, where comiss is "signalling" and ucomiss is "quiet". Most people consider loudness to be an obscure corner of IEEE754, but it is a corner which most pieces of hardware implement, and it amounts to running this flow chart before the comparison instruction:

                                       ↓
                               ╔════════════════╗
                           Yes ║ Is any operand ║ No
            ┌───────────────── ║    an sNaN?    ║ ───┐
            │                  ╚════════════════╝    │
            │                                        ↓
            │                             ╔════════════════╗
            │                         Yes ║ Is any operand ║ No
            │                       ┌──── ║    a qNaN?     ║ ───┐
            │                       │     ╚════════════════╝    │
            │                       ↓                           │
            │                ╔══════════════════╗               │
            │     Signalling ║ What loudness is ║ Quiet         │
            │   ┌─────────── ║ the instruction? ║ ──────┐       │
            │   │            ╚══════════════════╝       │       │
            ↓   ↓                                       │       │
          ╔══════════════╗      ╔══════════════╗        │       │
      Yes ║ Is mxcsr.IM  ║ No   ║ Set mxcsr.IE ║        │       │
    ┌──── ║ set to zero? ║ ───→ ║    to one    ║ ─┐     │       │
    │     ╚══════════════╝      ╚══════════════╝  │     │       │
    ↓                                             ↓     ↓       ↓
╔═══════════╗                               ╔══════════════════════╗
║ Raise an  ║                               ║     Execute the      ║
║ exception ║                               ║ instruction normally ║
╚═══════════╝                               ╚══════════════════════╝

---

That's enough context about comiss and ucomiss, so onward to vcmpps and vcmppd. These instructions operate on multiple SIMD lanes, and hence they can't set flags. Instead they compute a one-bit result per SIMD lane (and then replicate that bit to all 32 or 64 positions within the lane), with a five-bit field within the instruction configuring how to reach that result. If b0 through b4 represent those five bits, a de-novo design might be something like:

0. The loudness is "signalling" if b0 is set, and "quiet" otherwise.
1. If A > B, the one-bit result is b1.
2. If A == B, the one-bit result is b2.
3. If A < B, the one-bit result is b3.
4. If A unord B, the one-bit result is b4.

The actual encoding of vcmpps and vcmppd is ... nothing like that. The reality is:

0. The loudness is "signalling" if b4 ^ b1 ^ b0, and "quiet" otherwise.
1. If A > B, the one-bit result is b2.
2. If A == B, the one-bit result is b2 ^ !b0.
3. If A < B, the one-bit result is b2 ^ b1 ^ b0.
4. If A unord B, the one-bit result is b3 ^ b2 ^ (b1 & b0).

If it isn't immediately obvious that this encoding scheme covers every possibility exactly once, the entire five bits can be determined by:

1. Decide what result you want when A > B, set b2 to this.
2. Set b0 such that b2 ^ !b0 is the result you want when A == B.
3. Set b1 such that b2 ^ b1 ^ b0 is the result you want when A < B.
4. Set b3 such that b3 ^ b2 ^ (b1 & b0) is the result you want when A unord B.
5. Set b4 such that b4 ^ b1 ^ b0 is the desired loudness.

In practice, nobody follows that process to determine the five bits. Instead, they just look up the combination they want from the table of cases:

b4,⋯,0	Name	A > B	A == B	A < B	A unord B	Loudness
0b00000	vcmpeqps	0	1	0	0	Quiet
0b00001	vcmpltps	0	0	1	0	Signalling
0b00010	vcmpleps	0	1	1	0	Signalling
0b00011	vcmpunordps	0	0	0	1	Quiet
0b00100	vcmpneqps	1	0	1	1	Quiet
0b00101	vcmpnltps	1	1	0	1	Signalling
0b00110	vcmpnleps	1	0	0	1	Signalling
0b00111	vcmpordps	1	1	1	0	Quiet
0b01000	vcmpeq_uqps	0	1	0	1	Quiet
0b01001	vcmpngeps	0	0	1	1	Signalling
0b01010	vcmpngtps	0	1	1	1	Signalling
0b01011	vcmpfalseps	0	0	0	0	Quiet
0b01100	vcmpneq_oqps	1	0	1	0	Quiet
0b01101	vcmpgeps	1	1	0	0	Signalling
0b01110	vcmpgtps	1	0	0	0	Signalling
0b01111	vcmptrueps	1	1	1	1	Quiet
0b10000	vcmpeq_osps	0	1	0	0	Signalling
0b10001	vcmplt_oqps	0	0	1	0	Quiet
0b10010	vcmple_oqps	0	1	1	0	Quiet
0b10011	vcmpunord_sps	0	0	0	1	Signalling
0b10100	vcmpneq_usps	1	0	1	1	Signalling
0b10101	vcmpnlt_uqps	1	1	0	1	Quiet
0b10110	vcmpnle_uqps	1	0	0	1	Quiet
0b10111	vcmpord_sps	1	1	1	0	Signalling
0b11000	vcmpeq_usps	0	1	0	1	Signalling
0b11001	vcmpnge_uqps	0	0	1	1	Quiet
0b11010	vcmpngt_uqps	0	1	1	1	Quiet
0b11011	vcmpfalse_osps	0	0	0	0	Signalling
0b11100	vcmpneq_osps	1	0	1	0	Signalling
0b11101	vcmpge_oqps	1	1	0	0	Quiet
0b11110	vcmpgt_oqps	1	0	0	0	Quiet
0b11111	vcmptrue_usps	1	1	1	1	Signalling

If this table and the exposition thus far looks like a convoluted mess (a.k.a. "pure banacakes"), it implies that we might be looking at the world from the wrong place. As with many x86 things, part of the perspective is history. In this case, the applicable question is: what if we didn't have five bits to play with, but instead only had two bits? Two bits allows four different cases, so the question can be re-framed as deciding which four cases you consider the most important. You can debate this, but the x86 designers made their choice, and it is the first four rows of the table:

b4,⋯,0	Name	A > B	A == B	A < B	A unord B	Loudness
0b00000	vcmpeqps	0	1	0	0	Quiet
0b00001	vcmpltps	0	0	1	0	Signalling
0b00010	vcmpleps	0	1	1	0	Signalling
0b00011	vcmpunordps	0	0	0	1	Quiet

It might look like A > B can't be computed using one of these four, but > and < are symmetric: A > B is the same as B < A, and < can be computed (albeit I'm ignoring that x86 often re-uses the left operand as the result register, and often allows the right operand to come from memory, both of which defeat symmetry).

Orthogonality is a desirable property in instruction sets, and in the context of comparisons it means that whenever you can test for X you should also be able to test for not X. This justifies adding a third bit (b2) which inverts all the results, thus giving us the first eight rows:

b4,⋯,0	Name	A > B	A == B	A < B	A unord B	Loudness
0b00000	vcmpeqps	0	1	0	0	Quiet
0b00001	vcmpltps	0	0	1	0	Signalling
0b00010	vcmpleps	0	1	1	0	Signalling
0b00011	vcmpunordps	0	0	0	1	Quiet
0b00100	vcmpneqps	1	0	1	1	Quiet
0b00101	vcmpnltps	1	1	0	1	Signalling
0b00110	vcmpnleps	1	0	0	1	Signalling
0b00111	vcmpordps	1	1	1	0	Quiet

This is where pre-AVX CPUs stopped, and for compatibility, cmpps (NB: no v) still stops here on post-AVX CPUs (I did say history was relevant). AVX came along and expanded three bits to five, but obviously the old and new behaviours should coincide when the new bits (b3 and b4) are both zero, as that's how you make the migration as easy as possible for software (i.e. for compilers, disassemblers, etc).

How do you plug in those two extra bits to get from these first eight cases to all 32 cases being covered? Perhaps you wire up one of them (b3) to flip the outcome of A unord B (and nothing else), and wire up the other (b4) to flip between Quiet ↔ Signalling. Doing so gets you exactly the full 32-entry table from earlier (ta da!).

That feels like a reasonable explanation of how vcmpps and vcmppd got to where they are, but how might a CPU actually implement them? Determining loudness from b4 ^ b1 ^ b0 feels reasonable enough, so the interesting question is how to compute the one-bit result. Given the presence of comiss and ucomiss, there could plausibly be a circuit which takes two floats and computes CF and ZF. In the case of comiss and ucomiss, those CF and ZF bits get wired into the flags register, whereas in the case of vcmpps there could be a circuit which takes those two bits along with b3 through b0 and computes the one-bit result. On a modern FPGA, this trivially maps to a single 6:1 LUT. On an ASIC, one cheap trick would be a 4:1 mux whose two control inputs are ZF and CF and four data inputs are b2, b2 ^ !b0, b2 ^ b1 ^ b0, and b3 ^ b2 ^ (b1 & b0). An alternative would be to rotate the mux to make b0 and b1 be the control inputs. If doing that, and ignoring b2 and b3 for a minute, this would require that the four data inputs be:

Mux control bits (b1,0)	Name	Formulas for mux data inputs
0b00	vcmpeqps	ZF & !CF
0b01	vcmpltps	CF & !ZF
0b10	vcmpleps	(CF & !ZF) | (ZF & !CF)
0b11	vcmpunordps	CF & ZF

An equivalent formulation is:

Mux control bits (b1,0)	Name	Formulas for mux data inputs
0b00	vcmpeqps	ZF & (ZF ^ CF)
0b01	vcmpltps	CF & (ZF ^ CF)
0b10	vcmpleps	(CF | ZF) & (ZF ^ CF)
0b11	vcmpunordps	CF & !(ZF ^ CF)

This equivalent formulation feels less intuitive, but the common (ZF ^ CF) term is neat. It also makes it easy to add in b3: in all four cases, the (ZF ^ CF) term just needs to be replaced by ((ZF ^ CF) | b3). Adding in b2 is also easy: conditionally negate the whole lot by having a ^ with b2 after the mux. Finally, if a mux feels like cheating, it can be expanded out to two-input logic gates to give:

tmp1 = (CF & (b0 | b1)) | (ZF & !b0)
tmp2 = ((ZF ^ CF) | b3) ^ (b0 & b1)
result = (tmp1 & tmp2) ^ b2

Are these forumulas elegant? No. Do they reveal some deep insight? Also no. But that's the life story of x86: it's a bit of a mess, justified by decades of history, and it gets the job done regardless.