Branchless code: cmov, csel and Zicond

On an Apple silicon Mac, max(a, b) for two signed integers takes three instructions, cmp, csel w0, w0, w1, gt and ret, and the first two are the whole decision: a compare and a one-instruction conditional pick, with no branch between them. The same job written as an if/else puts a conditional branch between the compare and the result, and on random data the predictor guesses that branch wrong about half the time, at about 10 to 20 cycles a miss.

Each instruction set has its own answer for that shape: cmov on x86-64, csel on AArch64, and on RISC-V the Zicond extension, or a mask built from base instructions on chips without it. Branchless codebranchless code: A pattern that computes a result without a conditional branch, using a conditional select, a conditional-zero or a mask built from a comparison, so no path is skipped and the branch predictor is never consulted. The pattern wins on unpredictable data and loses on predictable data because it always pays for both sides. like this runs both sides of the choice on every call, so it beats the branch on some data and loses on other data; a later section gives the rule for telling the two apart.

cmov on x86-64 and the two sides it always pays for

On x86-64, the conditional moveconditional move: An instruction that writes its destination from one of two sources (or a cheap change of one, such as +1 or NOT) under a condition, without a branch. x86-64 cmovcc and AArch64 csel test the flags; RISC-V has no flags, so Zicond's czero pair tests a register, and two of them with an or make the select. is cmovcc dst, src: it copies the source into the destination when the condition codecondition code: A named test of the flags that a conditional branch, set or select instruction uses, such as eq (Z = 1) or the signed lt (N differs from V) on AArch64, and e or l on x86-64. More in “Flags and condition codes” holds and keeps the old value otherwise. The SDM’s description adds two details: the source is loaded on every call, whichever way the condition goes, and a 32-bit cmov clears the upper half of the 64-bit register in both cases. It reads the flags that a previous cmp or test left behind, so one cmp and one cmovcc are a two-register pick with no branch. The companion is setcc: it writes 0 or 1 into a byte register for the same condition, which movzx can widen to a Boolean the way C expects (a > b) to be.

cmovcc arrived with Intel’s P6 family, as the SDM’s CMOVcc entry records, and the x86-64 psABI lists CMOV among the baseline features any x86-64 program may expect, so code built for x86-64 can use cmov without a feature check, and compilers use it for short selects such as a > b ? a : b. Here is the three-instruction body for max(a, b), in GNU as Intel syntax:

# max_int(a, b) on x86-64 in GNU as Intel syntax: three instructions in the body.
# System V AMD64: a is in edi, b in esi and the result goes in eax.
# cmovcc dates from Intel's P6 family and is in the x86-64 baseline, so every x86-64 processor has it.
.intel_syntax noprefix
.text
.globl max_int
max_int:                        # int max_int(int a, int b)
    mov    eax, esi             # eax = b (the pick when b wins or they are equal)
    cmp    edi, esi             # compare a with b, setting the flags
    cmovge eax, edi             # if a >= b (signed), eax = a; else eax keeps b
    ret

The System V AMD64 calling convention passes a in edi and b in esi. The mov loads b as the fallback result, the cmp sets the flags and the cmovge overwrites eax with a when a >= b holds. Both the mov and the cmov run on every call and the branch predictor is never consulted, so no branch mispredictionbranch misprediction: A wrong guess by the branch predictor about which way a conditional branch goes: the core throws away the work done on the guessed path and refetches from the correct target, about 10 to 20 cycles on current cores. Branchless code avoids the cost by removing the branch, at the price of running both sides. can happen here: that is where cmov wins over jcc on data that is hard to predict. The table follows eax through two calls with the first two pairs of the lesson’s driver:

Both calls run all three instructions and both return 7, the same answers the AArch64 run prints below.

Within that constraint, a cmov replaces an if/else whose two sides are values already in registers: no label, no join point and nothing for the predictor to guess.

csel on AArch64 and the family around it

AArch64 names the same idea csel, conditional select. csel wd, wn, wm, cond writes wn into wd when the condition holds and wm otherwise, with the condition read from the four flags N, Z, C and V. Because it names both sources, it needs no fallback mov: one cmp and one csel are the whole decision.

The family around csel costs the same single instruction and adds a cheap arithmetic step to the second source: csinc writes wn or wm + 1, csinv writes wn or ~wm, and csneg writes wn or -wm. Two aliases round the set out: cset wd, cond writes 1 when the condition holds and 0 otherwise (it is csinc with the zero registerzero register: A register that always reads as zero and discards writes, so that 'set to zero' and 'copy from zero' reuse one move. AArch64 names it xzr/wzr; RISC-V names register x0 'zero'. x86-64 has none, so it uses xor-with-self. More in “Moving values and loading constants” twice, so 0 or 0 + 1), and csetm wd, cond writes all-ones or 0 as a bitwise mask (it is csinv on the same pair, so 0 or ~0).

Here is the AArch64 shape for max(a, b), two instructions in the body plus the return:

// max_int(a, b) on AArch64: one cmp sets the flags and a single csel is the whole decision.
// AAPCS64: a is in w0, b is in w1 and the return value goes back in w0.
.text
.p2align 2
.globl _max_int
_max_int:                       // int max_int(int a, int b)
    cmp  w0, w1                 // compare a with b, setting NZCV
    csel w0, w0, w1, gt         // w0 = (a > b) ? a : b, no branch between them
    ret

// Calls max_int (defined in max_aarch64.s) on four pairs and prints each result on its own line.
#include <limits.h>
#include <stdio.h>

int max_int(int a, int b);

int main(void) {
    int pairs[4][2] = { {3, 7}, {7, 3}, {-1, 1}, {INT_MIN, INT_MAX} };
    for (int i = 0; i < 4; ++i) {
        int a = pairs[i][0], b = pairs[i][1];
        printf("max(%d, %d) = %d\n", a, b, max_int(a, b));
    }
    return 0;
}

import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import session

# Assemble, link and run the AArch64 branchless max natively on an Apple silicon Mac.
# The function body is cmp + csel + ret; csel is the whole decision.
session.run("""
clang -O1 -o max_a64 driver_max.c max_aarch64.s
./max_a64
""")

$ clang -O1 -o max_a64 driver_max.c max_aarch64.s
$ ./max_a64
max(3, 7) = 7
max(7, 3) = 7
max(-1, 1) = 1
max(-2147483648, 2147483647) = 2147483647

The run prints the four pairs the driver asked for, including the boundary of the signed range: INT_MIN against INT_MAX picked INT_MAX, as it should. Every one of those answers came from the same single csel; the last section sets that body beside the other three shapes.

The second AArch64 example turns a comparison into a value with cset. is_positive(x) is one cmp w0, #0 and one cset w0, gt. Because cset writes the whole register, the 0 or 1 is ready to return, with no movzx step as after setcc on x86-64.

// is_positive(x) on AArch64: a cmp with zero, then one cset writes 1 when x > 0 and 0 otherwise.
// AAPCS64: x is in w0, the return value goes back in w0. No branch between the compare and the result.
.text
.p2align 2
.globl _is_positive
_is_positive:                   // int is_positive(int x)
    cmp  w0, #0                 // compare x with 0, setting the flags
    cset w0, gt                 // w0 = 1 if (x > 0), else 0
    ret

// Calls is_positive (defined in cset_aarch64.s) on -3, 0 and 3 and prints each result on its own line.
#include <stdio.h>

int is_positive(int x);

int main(void) {
    int values[3] = { -3, 0, 3 };
    for (int i = 0; i < 3; ++i) {
        int x = values[i];
        printf("is_positive(%d) = %d\n", x, is_positive(x));
    }
    return 0;
}

import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import session

# is_positive(x) is cmp w0, #0 then cset w0, gt. The C driver runs it on -3, 0 and 3.
# The comparison becomes a 0 or 1 value in w0 directly, with no branch in sight.
session.run("""
clang -O1 -o cset_a64 driver_cset.c cset_aarch64.s
./cset_a64
""")

$ clang -O1 -o cset_a64 driver_cset.c cset_aarch64.s
$ ./cset_a64
is_positive(-3) = 0
is_positive(0) = 0
is_positive(3) = 1

Three values in, three Booleans out: -3 and 0 are not positive (strict gt), 3 is. The A64 manual lists cset w0, gt as an alias of csinc w0, wzr, wzr, le, with le the inverse of gt: pick 0 when le holds, else 0 + 1. It also names cset as the preferred disassembly of that encoding.

RISC-V: Zicond, and the base-ISA mask when it is not there

RISC-V has no flags register and, until Zicond was ratified, had no standard conditional-move instruction. The ratified Zicond extension (version 1.0.0 in the specifications library) adds two R-type instructions that read a condition register instead of flags: czero.eqz rd, rs, rc writes rs into rd when rc is non-zero and 0 otherwise, and czero.nez rd, rs, rc does the opposite, writing rs into rd when rc is zero. The Zicond chapter calls each one a conditional zero; two of them, joined by one more instruction, make a conditional select.

For max(a, b) the Zicond shape is slt to form the condition, two czero to zero out one half of the pick and an or to combine:

# max_int(a, b) on RV64I with the Zicond extension (version 1.0.0 in the ratified library):
# slt computes the condition, then two czero instructions and an or make the select.
# czero.eqz rd, rs, rc writes rs into rd when rc is non-zero and zero otherwise;
# czero.nez rd, rs, rc does the opposite, writing rs when rc is zero.
.text
.globl max_int
max_int:                        # int max_int(int a, int b)
    slt       t0, a0, a1        # t0 = 1 if a < b, else 0
    czero.nez t1, a0, t0        # t1 = a if a >= b (t0 == 0), else 0
    czero.eqz t2, a1, t0        # t2 = b if a <  b (t0 != 0), else 0
    or        a0, t1, t2        # a0 = max(a, b): one of the two is zero
    ret

The pattern is “one of t1 and t2 is forced to zero, so the or returns the other”: czero.nez t1, a0, t0 writes a into t1 when t0 == 0 (that is, a >= b) and 0 otherwise, while czero.eqz t2, a1, t0 writes b when t0 != 0. The Zicond chapter’s own select joins the two halves with add; or gives the same result, because one of the halves is always 0. The two czero and the or after the compare are the whole decision, with no mask to build.

RV64 chips built before the RVA23 profile made Zicond mandatory may not have it, so the base-ISA shape builds a mask by hand. The same slt sets t0 to 0 or 1; subtracting it from the zero register wraps 1 into all-ones under two’s complement (a 64-bit -1), and 0 stays 0. The mask then selects between a and b with one xor, one and and one more xor:

# max_int(a, b) on RV64I without any extension: five instructions in the body.
# RISC-V System V: a is in a0, b in a1 and the return value goes back in a0.
# No conditional-move instruction here, so a mask built from slt picks between a and b.
.text
.globl max_int
max_int:                        # int max_int(int a, int b)
    slt  t0, a0, a1             # t0 = 1 if a < b, else 0
    sub  t0, zero, t0           # t0 = all-ones mask if a < b, else all-zeros
    xor  t1, a0, a1             # t1 = a XOR b
    and  t1, t1, t0             # t1 = (a XOR b) if a < b, else 0
    xor  a0, a0, t1             # a0 = a XOR t1 = b if a < b, else a
    ret

Five instructions in the body against four for the Zicond shape; both are branchless and both run both sides. When you read them back in the last section, expect sub t0, zero, t0 to print as neg t0, t0: the disassembler shows that encoding under its pseudo-instructionpseudo-instruction: A name an assembler accepts where an instruction goes although the instruction set has no instruction of that name: RISC-V li and la become one or more real instructions. The NASM manual also uses the word for its data lines, such as db, equ and times. More in “Assembler syntax: NASM, GNU as, Intel and AT&T” name. What decides between the two shapes is the target, so answer the table’s two questions about yours:

The short version: the mask when the binary must run on every RV64 core, the Zicond select when every core it targets is known to have the extension.

When branchless helps and when it hurts

A cmov or a csel avoids one specific cost, a branch misprediction, and pays one specific cost: both sides of the choice run on every call. The right shape depends on how predictable the branch is on the data the program actually sees, as a short rule-of-thumb table makes clear:

The 10 to 20 cycles are what LLVM, the compiler framework clang is built on, assumes when it weighs this choice: its scheduling models charge a mispredicted branch 14 cycles on Intel’s Skylake and Alder Lake P cores, 13 on AMD’s Zen 4 and 10 on Arm’s Neoverse N2 and V2.

Branchless code also matters when a choice depends on a secret, such as a key byte or a password: a branch on secret data makes the run time and the instructions fetched depend on that data, which constant-time code must avoid, while a select between two registers runs the same instructions whichever value wins. A C if or ?: can still compile to a branch, which is one more reason for the rule below.

The exact threshold between the two shapes on today’s cores is a measurement, not a formula; the performance module later in this track takes it up. The rule for now: measure on your own data, and read the disassembly to make sure the compiler kept the shape you asked for.

Side-by-side: max on three ISAs

The four sources above become four object files here, and each is read back as instructions. Apple clang assembles the AArch64 source as a macOS object, which otool -tV lists; Homebrew’s LLVM cross-assembles the x86-64 source and the two RISC-V sources as Linux ELF objects, which llvm-objdump lists:

import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import session

# Cross-assemble each ISA's object file with Homebrew LLVM 23.1.2 and read the bytes back as instructions.
# Apple clang assembles AArch64 natively; the x86-64 and RISC-V objects are built as Linux ELF for the disassembly.
# -c stops after the assembler, so the object has one function and no addresses the linker would patch.
session.run("""
clang -c -o max_a64.o max_aarch64.s
otool -tV max_a64.o | cat
/opt/homebrew/opt/llvm/bin/clang --target=x86_64-linux-gnu -c -o max_x64.o max_x86_64.s
llvm-objdump -d --no-show-raw-insn --no-leading-addr max_x64.o
/opt/homebrew/opt/llvm/bin/clang --target=riscv64-linux-gnu -march=rv64gc -c -o max_rv.o max_riscv64.s
llvm-objdump -d --no-show-raw-insn --no-leading-addr max_rv.o
/opt/homebrew/opt/llvm/bin/clang --target=riscv64-linux-gnu -march=rv64gc_zicond -c -o max_rv_z.o max_riscv64_zicond.s
llvm-objdump -d --no-show-raw-insn --no-leading-addr max_rv_z.o
""")

$ clang -c -o max_a64.o max_aarch64.s
$ otool -tV max_a64.o | cat
max_a64.o:
(__TEXT,__text) section
_max_int:
0000000000000000	cmp	w0, w1
0000000000000004	csel	w0, w0, w1, gt
0000000000000008	ret
$ /opt/homebrew/opt/llvm/bin/clang --target=x86_64-linux-gnu -c -o max_x64.o max_x86_64.s
$ llvm-objdump -d --no-show-raw-insn --no-leading-addr max_x64.o

max_x64.o:	file format elf64-x86-64

Disassembly of section .text:

<max_int>:
               	movl	%esi, %eax
               	cmpl	%esi, %edi
               	cmovgel	%edi, %eax
               	retq
$ /opt/homebrew/opt/llvm/bin/clang --target=riscv64-linux-gnu -march=rv64gc -c -o max_rv.o max_riscv64.s
$ llvm-objdump -d --no-show-raw-insn --no-leading-addr max_rv.o

max_rv.o:	file format elf64-littleriscv

Disassembly of section .text:

<max_int>:
               	slt	t0, a0, a1
               	neg	t0, t0
               	xor	t1, a0, a1
               	and	t1, t1, t0
               	xor	a0, a0, t1
               	ret
$ /opt/homebrew/opt/llvm/bin/clang --target=riscv64-linux-gnu -march=rv64gc_zicond -c -o max_rv_z.o max_riscv64_zicond.s
$ llvm-objdump -d --no-show-raw-insn --no-leading-addr max_rv_z.o

max_rv_z.o:	file format elf64-littleriscv

Disassembly of section .text:

<max_int>:
               	slt	t0, a0, a1
               	czero.nez	t1, a0, t0
               	czero.eqz	t2, a1, t0
               	or	a0, t1, t2
               	ret

Reading the four blocks top to bottom: the AArch64 body is cmp w0, w1, csel w0, w0, w1, gt, ret; the x86-64 body is movl %esi, %eax, cmpl %esi, %edi, cmovgel %edi, %eax, retq; the RISC-V base-ISA body is slt, neg (the pseudo for sub t0, zero, t0), xor, and, xor, ret; the RISC-V Zicond body is slt, czero.nez, czero.eqz, or, ret. Without the ret, the bodies are two instructions on AArch64, three on x86-64 and four or five on RV64 depending on the extension, and every shape is branchless.

The x86-64 block looks reversed because llvm-objdump prints x86-64 in AT&T syntax, not the Intel syntax of the source: the destination comes last, every register carries a % and the l suffix marks a 32-bit operation, so cmovgel %edi, %eax is the source’s cmovge eax, edi. Step through the four bodies one at a time:

Two, three, four and five instructions for one max: the count follows what each instruction set offers, and none of the four bodies needs a branch.

Practise

Build the sources of this page yourself, on an Apple silicon Mac or with the tools from setting up the toolchain:

1. Add a fifth pair, (0, 0), to driver_max.c (the array size and the loop bound both say 4) and run the AArch64 build again. With equal inputs gt is false, so which register does csel copy, and why does the printed line not tell you?
2. Rewrite is_positive on AArch64 so it uses ge instead of gt. Which inputs change their answer, and why?
3. Assemble max_riscv64.s with -march=rv64gc and max_riscv64_zicond.s with -march=rv64gc_zicond, as the recorded session does, and count the instructions in each listing. Then assemble the Zicond file with plain -march=rv64gc and read why the assembler refuses czero.

Interview questions

A warm-up for freshers: how does cmov differ from jcc in what it costs the pipeline?

A jcc is a conditional branch: the processor guesses which way it goes, runs ahead on the guess and throws that work away when the guess was wrong. A right guess costs almost nothing; a wrong one costs about 10 to 20 cycles on current cores, because every instruction fetched after the branch is discarded. A cmov has nothing to guess: it reads the flags the compare left and writes its destination from one of two sources, so the instruction stream never forks. The price is that both sides of the choice are ready every call, while a jcc can skip the work of the side not taken. On data the predictor can learn (sorted input, a flag that is rarely set) the branchy shape wins; on data it cannot (shuffled, random, near half-and-half) cmov wins by the misprediction penalty it never pays.

Two harder questions continue from here: whether to swap a branchy max in a hot loop for csel or cmov, and how to keep a password comparison constant-time on three instruction sets. Note the first thing you would measure or check for each, then follow its link to the first step and follow-ups:

Key takeaways

• A conditional select (cmov on x86-64, csel on AArch64, two Zicond czero joined by an or on RISC-V) picks one of two registers under a condition, with no branch between the compare and the result.
• setcc, cset and slt turn a comparison into a 0 or 1 value, which lets code treat a condition as a number without a branch.
• Branchless code avoids the misprediction penalty but always pays for both sides of the choice every call; the shape wins on unpredictable data and loses on predictable data.
• RISC-V has two shapes: a four-instruction select with the Zicond extension (slt, two czero and an or) and a five-instruction base-ISA mask (slt, sub-from-zero, xor, and, xor).
• Reading the shape back from the disassembly is how to be sure the compiler kept it: the select appears under its own name (cmovge, csel, czero.nez), and a conditional branch in its place means the compiler chose a branch.