Sixteen Conditions, Four Bits, and the Inversion That Hides

The condition is four bits, and here are all sixteen

Sixteen conditions in a four-bit field, and the table below is built by assembling one csel per value rather than by quoting a list of names:

$ ./a64dec.py --section=10 | sed -n '/10A\./,/Two names exist/p'
  value  bits    name    word        decoded here
  0      0000    eq      1a820020    csel     w0, w1, w2, eq
  1      0001    ne      1a821020    csel     w0, w1, w2, ne
  2      0010    cs      1a822020    csel     w0, w1, w2, cs
  3      0011    cc      1a823020    csel     w0, w1, w2, cc
  4      0100    mi      1a824020    csel     w0, w1, w2, mi
  5      0101    pl      1a825020    csel     w0, w1, w2, pl
  6      0110    vs      1a826020    csel     w0, w1, w2, vs
  7      0111    vc      1a827020    csel     w0, w1, w2, vc
  8      1000    hi      1a828020    csel     w0, w1, w2, hi
  9      1001    ls      1a829020    csel     w0, w1, w2, ls
  10     1010    ge      1a82a020    csel     w0, w1, w2, ge
  11     1011    lt      1a82b020    csel     w0, w1, w2, lt
  12     1100    gt      1a82c020    csel     w0, w1, w2, gt
  13     1101    le      1a82d020    csel     w0, w1, w2, le
  14     1110    al      1a82e020    csel     w0, w1, w2, al
  15     1111    nv      1a82f020    csel     w0, w1, w2, nv
                

One structural fact is visible in the fourth column and worth stating because it is the cheapest possible way to check the field position: the sixteen words are identical except for the nibble at bits[15:12]. Everything else — the destination at bits[4:0], the first source at bits[9:5], the second at bits[20:16], the whole opcode — is held constant across all sixteen rows. The condition is four bits in the middle of the word and that is the entire claim, and the harness asserts it as a bit pattern rather than as a sentence.

And there is a naming wrinkle that is a fact about the ISA and a nuisance for a cross-check. Values 2 and 3 have two names each. In a select the assembler calls them hs and lo; in a branch it calls them cs and cc. Both were measured: csel w0, w1, w2, cs assembles to 0x1a822020 and the disassembler calls it hs, while b.cs T assembles to 0x54000020 and the disassembler calls it cs. The same four bits, two names, and the printer picks by position. This page uses the select spelling throughout and concept 5 normalises the other one — and says that it does, which is the rule for every normalisation in that section.

The 4x4 table, and why op2 is not the operation

The conditional-select group has more than one field selecting the operation, and getting the relationship wrong is the first thing that goes. Here is the whole table, built as words and then asked about:

$ ./a64dec.py --section=10 | sed -n '/bit30 (invert)/,/SAME/p'
  bit30 (invert)  bits[11:10]  word        the oracle calls it       this decoder calls it
  0              00           1a800022    csel    w2, w1, w0, eq    csel    w2, w1, w0, eq
  0              01           1a800422    csinc   w2, w1, w0, eq    csinc   w2, w1, w0, eq
  0              10           1a800822    (blank)                   (undefined)
  0              11           1a800c22    (blank)                   (undefined)
  1              00           5a800022    csinv   w2, w1, w0, eq    csinv   w2, w1, w0, eq
  1              01           5a800422    csneg   w2, w1, w0, eq    csneg   w2, w1, w0, eq
  1              10           5a800822    (blank)                   (undefined)
  1              11           5a800c22    (blank)                   (undefined)
                

Two facts, and the first one corrects a very natural assumption.

There are four operations, not sixteen and not eight:csel, csinc, csinv and csneg, selected by the pair (bit 30, bits[11:10]) = (0,00), (0,01), (1,00) and (1,01). The first version of this decoder read bits[11:10] as the operation and got csinv and csneg wrong in the corpus — and those two disagreements were in the two instructions the branchless-csel discussion quotes, which is the worst possible place for a bug to land.

The other four cells of the 4x4 are UNDEFINED. The oracle prints <unknown> for all four and this decoder raises on all four. The first draft of the file's own comment called two of them “the SET forms”, which is a plausible-sounding wrong answer that would have taught a reader the group has six operations. (The second version of that table was wrong in a different instructive way: it assembled a line per cell, and since there is no mnemonic for (invert, op2) = (1, 0) the assembler silently produced a csinv for all four of the inv = 1 rows and the table printed csinv eight times. Building the cells as words is the only way a cell with no name can still be measured.)

And the SET forms are not new opcodes

Here is where the trap lives, and the table below is the evidence:

$ ./a64dec.py --section=10 | sed -n '/cset w0, eq  /,/cneg w0, w1, ge/p'
    cset w0, eq              1a9f17e0   csinc w0, wzr, wzr, ne   1a9f17e0   SAME
    cset w0, ne              1a9f07e0   csinc w0, wzr, wzr, eq   1a9f07e0   SAME
    csetm w0, eq             5a9f13e0   csinv w0, wzr, wzr, ne   5a9f13e0   SAME
    csetm x0, ne             da9f03e0   csinv x0, xzr, xzr, eq   da9f03e0   SAME
    cinc w0, w1, eq          1a811420   csinc w0, w1, w1, ne     1a811420   SAME
    cinc w1, w2, eq          1a821441   csinc w1, w2, w2, ne     1a821441   SAME
    cneg w0, w1, ge          5a81b420   csneg w0, w1, w1, lt     5a81b420   SAME
    csinc w0, wzr, wzr, al   1a9fe7e0   cset w0, eq              1a9f17e0   DIFFERENT
    csinc w0, wzr, wzr, ne   1a9f17e0   cset w0, eq              1a9f17e0   SAME
    csinc w0, wzr, wzr, nv   1a9ff7e0   cset w0, eq              1a9f17e0   DIFFERENT
    csinv w0, wzr, wzr, al   5a9fe3e0   csetm w0, eq             5a9f13e0   DIFFERENT
                

Read the first row and then the eighth. cset w0, eq is csinc w0, wzr, wzr, ne — the condition is inverted, and the two are different 32 bits that differ in the condition field and nowhere else. And the assembly text of csinc w0, wzr, wzr, al, which is the ninth row, is cset w0, ne: a different word again.

Why the inversion, in one sentence: “1 if the condition holds, else 0” is “0 + 0 if it does not hold, else 0 + 1”. Both sources are the zero register, so the sum is the constant, and the constant is 1 in the case where the condition is false. The assembler prints the user's condition and the encoding holds its negation, and both are right about what the instruction does.

So the shape of the bug is worth stating exactly, because it is the general form:

• A decoder that models cset as “a csinc with Rn = Rm = 31” reports every condition in the program inverted.
• The output is 0 or 1 either way, so nothing about it looks wrong.
• No cross-check against yourself finds it, because you would make the same assumption twice. Concept 5 exists because of this shape specifically.

And note what a field map cannot show you. CSET reuses the same two field values as CSINC; what is different is that Rn and Rm are 31, and 31 means the zero register in this group. Four opcodes plus two register values give a sixth and a seventh instruction, and there is no bit anywhere that says “this is a set”. That is why the 4x4 table has no cset row and why the model in the artifact has to read the registers to name it.

The same four bits, five of them, in a branch

And a B.cond is bits[31:24] = 0b01010100, imm19 at bits[23:5], and the condition at bits[4:0]:

$ ./a64dec.py --section=10 | sed -n '/10C\./,/A B.cond is/p'
  value  bits    name    word        decoded here
  0      0000    eq      54ffffc0    b.eq     -8
  14     1110    al      54ffffce    b.al     -8
  15     1111    nv      54ffffcf    b.nv     -8
                

The same four bits are at position 4 here and at position 12 in a csel, and the two fields do not overlap. A decoder that finds one cond field and uses it for both gets every conditional instruction in the program wrong, in the same direction — and in this case the error is visible in the output, because b.eq and b.ne are different branches and a program that takes the wrong one misbehaves. That is the good case. The cset case above is the bad one, and it is the one that got its own concept's warning.

AArch64 does not have a single condition field. That is a cost of the encoding rather than an accident: two different places, two different widths, one meaning. Concept 2's field table shows both positions side by side, and this is what the two non-contiguous rows in it are about.

How often the compiler reaches for a select

$ ./a64dec.py --section=10 | sed -n '/conditional selects:/,/half of/p'
  conditional selects: 56   conditional branches: 49
  and the 45-looking number is not a typo: 23 of the 56 selects are
  the INVERTED forms -- cset, csetm, cinc, cinv, cneg -- which are
  the ones whose condition field is the negation of the one the
  mnemonic names.  A decoder that misses the inversion decodes 23
  instructions in this corpus with the condition backwards, and
  every one of them still produces a correct boolean for half of
  its inputs.
                

Both are real and both are used, and 23 of the 56 selects are the inverted forms this page is about. A decoder that missed the inversion would decode 23 of these with the condition backwards, and every one would still produce a correct boolean for half its inputs.

The family has nine names and the artifact's first version counted them with a startswith test — which misses csinc, csinv and csneg, because “csinc” starts with “csi” and not with “cse”. That printed 45 where the answer is 56, and the eleven missing instructions were three of the four operations in the group: the section's own count of its own family was short by exactly the operations whose selection depends on the bit-30/op2 pair. The list is now spelled out and the count printed as a sum of the numbers above it.

Which one a compiler reaches for is a decision about whether the two sides of the branch are equally likely — a property of the program, not of the architecture. So that number is a fact about this corpus and a fact about clang, and concept 5 measures what the choice costs in bytes rather than arguing about it.