MySmartCoPilot
Ask Passes Your pass 7 days left 1 day left Last day

Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

Assembly (x86-64, AArch64, RISC-V)  Module 6 – Branches, loops and jump tables

Switch statements and jump tables

How a dense switch becomes a bounds check and one indexed jump on x86-64, AArch64 and RISC-V, and why CET, BTI and Zicfilp guard that jump.

  • Intermediate
  • 20 minutes
  • Examples run with Python 3.14.8
  • By MySmartCoPilot
Free: the whole lesson. With a pass: the model answers to its 2 interview questions.

What you will learn

  • Implement a dense switch as a bounds check plus one indexed indirect jump
  • Read a compiler-generated jump table on x86-64, AArch64 and RISC-V
  • Explain why an indirect jump needs landing pads under CET, BTI and Zicfilp
  • Identify a sparse switch the compiler lowered to a tree of compares

Before you start

What you’ll learn · Before you start

What you will learn

  • Implement a dense switch as a bounds check plus one indexed indirect jump
  • Read a compiler-generated jump table on x86-64, AArch64 and RISC-V
  • Explain why an indirect jump needs landing pads under CET, BTI and Zicfilp
  • Identify a sparse switch the compiler lowered to a tree of compares

Before you start

On this page

A switch over sixteen case values that run 0, 1, 2 … 15 does not compare sixteen times. The compiler puts the sixteen landing addresses in a table, checks the value against the table’s length once, and jumps through the entry it reads: on x86-64 that table is 64 bytes, four per case, and on AArch64 the same sixteen cases need 16 bytes, one byte each. A switch this dense lowers this way on all three ISAs.

That makes jump tables worth recognising on sight in a disassembly: a bounds check, a table address, one load, one add, one indirect branch, then a run of short blocks that each end in a return. This lesson compiles one sixteen-case switch for all three ISAs and reads every dispatch, shows what the compiler builds instead when the case values are spread out, names the landing-pad marks that Intel CET, Arm BTI and RISC-V Zicfilp put around the indirect jump, and ends with a four-case table written by hand that assembles and runs.

From a switch to a table of addresses

Here is the switch the whole lesson compiles. Sixteen cases, dense from 0, and each case computes something of its own, so the compiler cannot collapse them into one table of results: every case needs a block of code.

classify.c: sixteen dense cases C · classify.c 
/* classify.c: one dense switch over sixteen kinds.
 *
 * classify(kind, value) applies the rule of one field kind to a raw value, the way a small
 * bytecode interpreter applies one of its opcodes to the accumulator. The case values run
 * 0, 1, 2 ... 15 with no gaps, and each case computes something different, so the compiler
 * cannot fold the switch into a table of constants: every case needs a block of its own.
 * At -O2 that is what makes the lowering a jump table.
 */
int classify(int kind, int value)
{
    switch (kind) {
    case 0:
        return value + 5;
    case 1:
        return value * 3;
    case 2:
        return value - 7;
    case 3:
        return value / 2;
    case 4:
        return value ^ 9;
    case 5:
        return value << 2;
    case 6:
        return value >> 1;
    case 7:
        return value * value;
    case 8:
        return value | 16;
    case 9:
        return value & 31;
    case 10:
        return value % 7;
    case 11:
        return value * 11 + 4;
    case 12:
        return value - value / 3;
    case 13:
        return value + (value >> 2);
    case 14:
        return value * 5 - 1;
    case 15:
        return ~value + 2;
    default:
        return -1;
    }
}

The lowering is the same five parts everywhere. First the bounds check: A compare that proves an index is inside the range of the thing it indexes before the index is used. One unsigned compare covers both ends, because a negative value read as unsigned is larger than any valid index.: one unsigned compare of the switch value against the highest case, which sends anything outside the range to the default block. An unsigned compare is what makes one instruction enough, because a negative value read as unsigned is a very large number and fails the same test. Then the value becomes an index, the index reads one entry of the jump table: A table of addresses, or of 32-bit or smaller offsets, indexed by a value, which turns a dense switch into one indirect jump instead of a chain of compares. Compilers keep it in read-only data., the entry is added to a base address, and one indirect branch goes there.

Interactive · stage by stage The five parts of a table dispatch Step through one dispatch of the sixteen-case switch, from the bounds check to the indirect branch.
The five parts of a table dispatch, step 5 of 5. Showing Bounds check, Value as index, Read one entry, Add the base, Indirect branch (same cost for every case). In focus: Indirect branch.Bounds checkone unsigned compareValue as indexkind 0 to 15Read one entryldrb, movslq or lwAdd the basean entry is a distanceIndirect branchsame cost for every case

The drawing shows the whole scene; its 5 steps are listed below.

Every step as text
  1. Check the range once. One unsigned compare against the highest case value decides whether this call belongs in the table at all. A negative value read as unsigned is huge, so it fails the same test and goes to the default block.
  2. The value is the index. Past the check the value needs no translation, because case 0 is entry 0 and case 15 is entry 15. Nothing is compared again after this point.
  3. Read one entry. One load reads the entry for that index. AArch64 reads a single byte with ldrb, x86-64 a signed 32-bit value with movslq, RISC-V a word with lw after shifting the index left by two.
  4. Add the base back. The entry is a distance, so it means nothing alone. x86-64 and RISC-V add the table's own address back; AArch64 adds the address of the first landing, after multiplying the byte by four.
  5. One branch for any case. The indirect branch goes to the address just computed. Sixteen cases, one branch instruction, and the same work whichever case it was.

Part x86-64 AArch64 RISC-V
Bounds check cmpl $0xf, %edi then ja cmp w0, #15 then b.hi li a2, 15 then bltu
Table address leaq .LJTI0_0(%rip), %rdx adrp/add auipc/addi
Read one entry movslq (%rdx,%rcx,4), %rcx ldrb w11, [x9, x8] slli, add, lw
Add the base addq %rdx, %rcx add x10, x10, x11, lsl #2 add a0, a0, a2
Indirect branch jmpq *%rcx br x10 jr a0

The table itself lives in read-only data, beside string literals: .rodata on ELF, __TEXT,__const on Mach-O. It is plain data that the code indexes, which is why a wrong index is so dangerous and why the bounds check is never optional.

Checkpoint

Check: The five parts of a table dispatch

  1. One question The dispatch checks the switch value with one unsigned compare against 15 (cmp w0, #15 then b.hi). How are negative values handled?

    Choose one answer.

    Show the answer

    Answer: They fail the same test, because as an unsigned number a negative value is enormous and larger than 15.

    An unsigned compare is why the bounds check is one instruction. Any value outside 0 to 15, in either direction, is above 15 when read as unsigned, so one conditional branch sends it to the default block.

Reading a compiler-generated table on three ISAs

This session compiles classify.c for AArch64 with Apple’s clang, prints the dispatch, prints the sixteen table entries, then builds the switch with a driver and runs it for kinds -1 to 16. The two kinds outside the range both return -1, through the one bounds check.

AArch64: the dispatch, the table and a run Python · classify_session.py 
"""Compile the sixteen-case switch for AArch64, read its jump table, then build and run it.

Apple clang compiles, assembles, links and runs AArch64 Mach-O code on an Apple silicon Mac,
so the dispatch on the page and the eighteen results below come from the same build.
"""

import pathlib
import sys

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

session.run(
    """
# Compile classify.c to AArch64 assembly at -O2.
clang -O2 -S classify.c -o classify.s
# The dispatch: one bounds check, the table's address, one entry, one indirect branch.
sed -n '/cmp.*w0, #15/,/br.*x10/p' classify.s
# The table: sixteen one-byte entries, each a landing's distance from the first one, in instructions.
sed -n '/lJTI0_0:/,/End function/p' classify.s
# Build the switch with a driver that calls it for kinds -1 to 16, and run it.
clang -O2 -o classify driver.c classify.c
./classify
"""
)

Output

# Compile classify.c to AArch64 assembly at -O2.
$ clang -O2 -S classify.c -o classify.s
# The dispatch: one bounds check, the table's address, one entry, one indirect branch.
$ sed -n '/cmp.*w0, #15/,/br.*x10/p' classify.s
	cmp	w0, #15
	b.hi	LBB0_18
; %bb.1:
	mov	w8, w0
Lloh0:
	adrp	x9, lJTI0_0@PAGE
Lloh1:
	add	x9, x9, lJTI0_0@PAGEOFF
	adr	x10, LBB0_2
	ldrb	w11, [x9, x8]
	add	x10, x10, x11, lsl #2
	br	x10
# The table: sixteen one-byte entries, each a landing's distance from the first one, in instructions.
$ sed -n '/lJTI0_0:/,/End function/p' classify.s
lJTI0_0:
	.byte	(LBB0_2-LBB0_2)>>2
	.byte	(LBB0_12-LBB0_2)>>2
	.byte	(LBB0_8-LBB0_2)>>2
	.byte	(LBB0_10-LBB0_2)>>2
	.byte	(LBB0_5-LBB0_2)>>2
	.byte	(LBB0_13-LBB0_2)>>2
	.byte	(LBB0_15-LBB0_2)>>2
	.byte	(LBB0_11-LBB0_2)>>2
	.byte	(LBB0_17-LBB0_2)>>2
	.byte	(LBB0_7-LBB0_2)>>2
	.byte	(LBB0_16-LBB0_2)>>2
	.byte	(LBB0_4-LBB0_2)>>2
	.byte	(LBB0_6-LBB0_2)>>2
	.byte	(LBB0_14-LBB0_2)>>2
	.byte	(LBB0_3-LBB0_2)>>2
	.byte	(LBB0_9-LBB0_2)>>2
                                        ; -- End function
# Build the switch with a driver that calls it for kinds -1 to 16, and run it.
$ clang -O2 -o classify driver.c classify.c
$ ./classify
value = 12
kind  -1 -> -1
kind   0 -> 17
kind   1 -> 36
kind   2 -> 5
kind   3 -> 6
kind   4 -> 5
kind   5 -> 48
kind   6 -> 6
kind   7 -> 144
kind   8 -> 28
kind   9 -> 12
kind  10 -> 5
kind  11 -> 136
kind  12 -> 8
kind  13 -> 15
kind  14 -> 59
kind  15 -> -11
kind  16 -> -1

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 classify_session.py

Three details in that recording are worth naming. The entries are written as (LBB0_12-LBB0_2)>>2: a landing’s distance from the first landing, in bytes, divided by four. Every AArch64 instruction is four bytes, so the division loses nothing, and sixteen entries fit in sixteen bytes. The ldrb reads one of them, add x10, x10, x11, lsl #2 multiplies by four again and adds the first landing’s address, and br x10 branches. The table’s own address comes from adrp plus add, the position-independent code: Code that reaches its data and other code relative to the program counter rather than by absolute address, so the loader may place it at any base address. Formed with RIP-relative operands on x86-64, adrp/add on AArch64 and auipc/addi on RISC-V. More in “Static data and PC-relative addresses” pair the previous module used for static data.

classify_O2_aarch64.s (clang -O2 -S) S · classify_O2_aarch64.s 
	.build_version macos, 26, 0	sdk_version 27, 0
	.section	__TEXT,__text,regular,pure_instructions
	.globl	_classify                       ; -- Begin function classify
	.p2align	2
_classify:                              ; @classify
	.cfi_startproc
; %bb.0:
	cmp	w0, #15
	b.hi	LBB0_18
; %bb.1:
	mov	w8, w0
Lloh0:
	adrp	x9, lJTI0_0@PAGE
Lloh1:
	add	x9, x9, lJTI0_0@PAGEOFF
	adr	x10, LBB0_2
	ldrb	w11, [x9, x8]
	add	x10, x10, x11, lsl #2
	br	x10
LBB0_2:
	add	w0, w1, #5
	ret
LBB0_3:
	add	w8, w1, w1, lsl #2
	sub	w0, w8, #1
	ret
LBB0_4:
	mov	w8, #11                         ; =0xb
	mov	w9, #4                          ; =0x4
	madd	w0, w1, w8, w9
	ret
LBB0_5:
	mov	w8, #9                          ; =0x9
	eor	w0, w1, w8
	ret
LBB0_6:
	mov	w8, #1431655765                 ; =0x55555555
	smull	x8, w1, w8
	lsr	x8, x8, #32
	sub	w8, w8, w1
	asr	w9, w8, #1
	add	w8, w9, w8, lsr #31
	add	w0, w8, w1
	ret
LBB0_7:
	and	w0, w1, #0x1f
	ret
LBB0_8:
	sub	w0, w1, #7
	ret
LBB0_9:
	mov	w8, #1                          ; =0x1
	sub	w0, w8, w1
	ret
LBB0_10:
	add	w8, w1, w1, lsr #31
	asr	w0, w8, #1
	ret
LBB0_11:
	mul	w0, w1, w1
	ret
LBB0_12:
	add	w0, w1, w1, lsl #1
	ret
LBB0_13:
	lsl	w0, w1, #2
	ret
LBB0_14:
	add	w0, w1, w1, asr #2
	ret
LBB0_15:
	asr	w0, w1, #1
	ret
LBB0_16:
	mov	w8, #9363                       ; =0x2493
	movk	w8, #37449, lsl #16
	smull	x8, w1, w8
	lsr	x8, x8, #32
	add	w8, w8, w1
	asr	w9, w8, #2
	add	w8, w9, w8, lsr #31
	sub	w8, w8, w8, lsl #3
	add	w0, w1, w8
	ret
LBB0_17:
	orr	w0, w1, #0x10
	ret
LBB0_18:
	mov	w0, #-1                         ; =0xffffffff
	ret
	.loh AdrpAdd	Lloh0, Lloh1
	.cfi_endproc
	.section	__TEXT,__const
lJTI0_0:
	.byte	(LBB0_2-LBB0_2)>>2
	.byte	(LBB0_12-LBB0_2)>>2
	.byte	(LBB0_8-LBB0_2)>>2
	.byte	(LBB0_10-LBB0_2)>>2
	.byte	(LBB0_5-LBB0_2)>>2
	.byte	(LBB0_13-LBB0_2)>>2
	.byte	(LBB0_15-LBB0_2)>>2
	.byte	(LBB0_11-LBB0_2)>>2
	.byte	(LBB0_17-LBB0_2)>>2
	.byte	(LBB0_7-LBB0_2)>>2
	.byte	(LBB0_16-LBB0_2)>>2
	.byte	(LBB0_4-LBB0_2)>>2
	.byte	(LBB0_6-LBB0_2)>>2
	.byte	(LBB0_14-LBB0_2)>>2
	.byte	(LBB0_3-LBB0_2)>>2
	.byte	(LBB0_9-LBB0_2)>>2
                                        ; -- End function
.subsections_via_symbols

The same source cross-assembled for Linux shows the other two shapes. x86-64 loads a 32-bit signed entry with movslq and scales the index by four in the addressing mode itself; RISC-V shifts the index left by two, adds the table base and reads the entry with lw. The section: A named region of an object or executable file, such as .text, .rodata, .data or .bss. The linker merges matching sections across objects and the loader groups them into segments at run time. More in “From source to executable: objects and linking” listing in the recording gives the sizes: .rodata is 0x40 bytes for sixteen four-byte entries, and .rela.rodata holds one relocation: An entry beside a section's bytes that says which bytes the linker must patch, with which symbol's address, under which formula. Needed whenever the assembler cannot know a final address yet. More in “From source to executable: objects and linking” per entry.

x86-64 and RISC-V: the same switch, cross-assembled Python · cross_session.py 
"""Cross-assemble the same switch for x86-64 Linux and RISC-V Linux, and read both dispatches.

LLVM's clang compiles the switch for both targets and llvm-objdump disassembles the objects it
writes. The session reads each dispatch and the size the table takes in each object; the ELF
programs themselves are built for Linux.
"""

import pathlib
import sys

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

session.run(
    """
# Assemble the switch for x86-64 Linux and disassemble its dispatch, bytes and all.
/opt/homebrew/opt/llvm/bin/clang -O2 -c -target x86_64-linux-gnu classify.c -o classify_x86_64.o
/opt/homebrew/opt/llvm/bin/llvm-objdump -d --no-leading-addr classify_x86_64.o | sed -n '5,14p'
# The table sits in .rodata: 0x40 bytes, four per entry, with one relocation per entry.
/opt/homebrew/opt/llvm/bin/llvm-objdump -h classify_x86_64.o | sed -n '/Idx/,$p' | sed -n '1,7p'
/opt/homebrew/opt/llvm/bin/llvm-readobj -r classify_x86_64.o | sed -n '/rela.rodata/,/0x10 /p'
# The same source for RISC-V: auipc and addi build the table's address, lw reads one entry.
/opt/homebrew/opt/llvm/bin/clang -O2 -c -target riscv64-linux-gnu classify.c -o classify_riscv64.o
/opt/homebrew/opt/llvm/bin/llvm-objdump -d --no-leading-addr classify_riscv64.o | sed -n '5,17p'
"""
)

Output

# Assemble the switch for x86-64 Linux and disassemble its dispatch, bytes and all.
$ /opt/homebrew/opt/llvm/bin/clang -O2 -c -target x86_64-linux-gnu classify.c -o classify_x86_64.o
$ /opt/homebrew/opt/llvm/bin/llvm-objdump -d --no-leading-addr classify_x86_64.o | sed -n '5,14p'

<classify>:
 83 ff 0f                              	cmpl	$0xf, %edi
 0f 87 aa 00 00 00                     	ja	0xb3 <classify+0xb3>
 89 f0                                 	movl	%esi, %eax
 89 f9                                 	movl	%edi, %ecx
 48 8d 15 00 00 00 00                  	leaq	(%rip), %rdx            # 0x14 <classify+0x14>
 48 63 0c 8a                           	movslq	(%rdx,%rcx,4), %rcx
 48 01 d1                              	addq	%rdx, %rcx
 ff e1                                 	jmpq	*%rcx
# The table sits in .rodata: 0x40 bytes, four per entry, with one relocation per entry.
$ /opt/homebrew/opt/llvm/bin/llvm-objdump -h classify_x86_64.o | sed -n '/Idx/,$p' | sed -n '1,7p'
Idx Name            Size     VMA              Type
  0                 00000000 0000000000000000
  1 .strtab         00000073 0000000000000000
  2 .text           000000b9 0000000000000000 TEXT
  3 .rela.text      00000018 0000000000000000
  4 .rodata         00000040 0000000000000000 DATA
  5 .rela.rodata    00000180 0000000000000000
$ /opt/homebrew/opt/llvm/bin/llvm-readobj -r classify_x86_64.o | sed -n '/rela.rodata/,/0x10 /p'
  Section (5) .rela.rodata {
    0x0 R_X86_64_PC32 .text 0x1D
    0x4 R_X86_64_PC32 .text 0x76
    0x8 R_X86_64_PC32 .text 0x5C
    0xC R_X86_64_PC32 .text 0x6E
    0x10 R_X86_64_PC32 .text 0x41
# The same source for RISC-V: auipc and addi build the table's address, lw reads one entry.
$ /opt/homebrew/opt/llvm/bin/clang -O2 -c -target riscv64-linux-gnu classify.c -o classify_riscv64.o
$ /opt/homebrew/opt/llvm/bin/llvm-objdump -d --no-leading-addr classify_riscv64.o | sed -n '5,17p'

<classify>:
 463d                  	li	a2, 0xf
 00a66063              	bltu	a2, a0, 0x2 <classify+0x2>

<.Lpcrel_hi0>:
 00000617              	auipc	a2, 0x0
 050a                  	slli	a0, a0, 0x2
 00060613              	mv	a2, a2
 9532                  	add	a0, a0, a2
 4108                  	lw	a0, 0x0(a0)
 9532                  	add	a0, a0, a2
 8502                  	jr	a0

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 cross_session.py

classify_x86_64.s (clang -O2 -S for x86-64 Linux) S · classify_x86_64.s 
	.att_syntax
	.file	"classify.c"
	.text
	.globl	classify                        # -- Begin function classify
	.prefalign	4, .Lfunc_end0, nop
	.type	classify,@function
classify:                               # @classify
# %bb.0:
	cmpl	$15, %edi
	ja	.LBB0_20
# %bb.1:
	movl	%esi, %eax
	movl	%edi, %ecx
	leaq	.LJTI0_0(%rip), %rdx
	movslq	(%rdx,%rcx,4), %rcx
	addq	%rdx, %rcx
	jmpq	*%rcx
.LBB0_2:
	addl	$5, %eax
                                        # kill: def $eax killed $eax killed $rax
	retq
.LBB0_3:
	leal	(%rax,%rax,4), %eax
	decl	%eax
                                        # kill: def $eax killed $eax killed $rax
	retq
.LBB0_4:
	leal	(%rax,%rax,4), %ecx
	leal	(%rax,%rcx,2), %eax
	addl	$4, %eax
                                        # kill: def $eax killed $eax killed $rax
	retq
.LBB0_5:
	xorl	$9, %eax
                                        # kill: def $eax killed $eax killed $rax
	retq
.LBB0_6:
	movslq	%eax, %rcx
	imulq	$1431655765, %rcx, %rcx         # imm = 0x55555555
	shrq	$32, %rcx
	subl	%eax, %ecx
	movl	%ecx, %edx
	shrl	$31, %edx
	sarl	%ecx
	addl	%edx, %ecx
	jmp	.LBB0_18
.LBB0_7:
	andl	$31, %eax
                                        # kill: def $eax killed $eax killed $rax
	retq
.LBB0_8:
	addl	$-7, %eax
                                        # kill: def $eax killed $eax killed $rax
	retq
.LBB0_9:
	movl	$1, %ecx
	subl	%eax, %ecx
	movl	%ecx, %eax
                                        # kill: def $eax killed $eax killed $rax
	retq
.LBB0_11:
	movl	%eax, %ecx
	shrl	$31, %ecx
	addl	%eax, %ecx
	sarl	%ecx
	movl	%ecx, %eax
                                        # kill: def $eax killed $eax killed $rax
	retq
.LBB0_12:
	imull	%eax, %eax
                                        # kill: def $eax killed $eax killed $rax
	retq
.LBB0_13:
	leal	(%rax,%rax,2), %eax
                                        # kill: def $eax killed $eax killed $rax
	retq
.LBB0_14:
	shll	$2, %eax
                                        # kill: def $eax killed $eax killed $rax
	retq
.LBB0_15:
	movl	%eax, %ecx
	sarl	$2, %ecx
	addl	%eax, %ecx
	movl	%ecx, %eax
                                        # kill: def $eax killed $eax killed $rax
	retq
.LBB0_16:
	sarl	%eax
                                        # kill: def $eax killed $eax killed $rax
	retq
.LBB0_17:
	movslq	%eax, %rcx
	imulq	$-1840700269, %rcx, %rcx        # imm = 0x92492493
	shrq	$32, %rcx
	addl	%eax, %ecx
	movl	%ecx, %edx
	shrl	$31, %edx
	sarl	$2, %ecx
	addl	%edx, %ecx
	leal	(,%rcx,8), %edx
	subl	%edx, %ecx
.LBB0_18:
	addl	%eax, %ecx
	movl	%ecx, %eax
                                        # kill: def $eax killed $eax killed $rax
	retq
.LBB0_19:
	orl	$16, %eax
                                        # kill: def $eax killed $eax killed $rax
	retq
.LBB0_20:
	movl	$-1, %eax
                                        # kill: def $eax killed $eax killed $rax
	retq
.Lfunc_end0:
	.size	classify, .Lfunc_end0-classify
	.section	.rodata,"a",@progbits
	.p2align	2, 0x0
.LJTI0_0:
	.long	.LBB0_2-.LJTI0_0
	.long	.LBB0_13-.LJTI0_0
	.long	.LBB0_8-.LJTI0_0
	.long	.LBB0_11-.LJTI0_0
	.long	.LBB0_5-.LJTI0_0
	.long	.LBB0_14-.LJTI0_0
	.long	.LBB0_16-.LJTI0_0
	.long	.LBB0_12-.LJTI0_0
	.long	.LBB0_19-.LJTI0_0
	.long	.LBB0_7-.LJTI0_0
	.long	.LBB0_17-.LJTI0_0
	.long	.LBB0_4-.LJTI0_0
	.long	.LBB0_6-.LJTI0_0
	.long	.LBB0_15-.LJTI0_0
	.long	.LBB0_3-.LJTI0_0
	.long	.LBB0_9-.LJTI0_0
                                        # -- End function
	.ident	"Homebrew clang version 23.1.2"
	.section	".note.GNU-stack","",@progbits
	.addrsig
classify_riscv64.s (clang -O2 -S for RISC-V Linux) S · classify_riscv64.s 
	.attribute	4, 16
	.attribute	5, "rv64i2p1_m2p0_a2p1_f2p2_d2p2_c2p0_zicsr2p0_zmmul1p0_zaamo1p0_zalrsc1p0_zca1p0_zcd1p0"
	.file	"classify.c"
	.text
	.globl	classify                        # -- Begin function classify
	.p2align	1
	.type	classify,@function
classify:                               # @classify
# %bb.0:
	li	a2, 15
	bltu	a2, a0, .LBB0_18
# %bb.1:
.Lpcrel_hi0:
	auipc	a2, %pcrel_hi(.LJTI0_0)
	slli	a0, a0, 2
	addi	a2, a2, %pcrel_lo(.Lpcrel_hi0)
	add	a0, a0, a2
	lw	a0, 0(a0)
	add	a0, a0, a2
	jr	a0
.LBB0_2:
	addiw	a0, a1, 5
	ret
.LBB0_3:
	slli	a0, a1, 2
	add	a0, a0, a1
	addiw	a0, a0, -1
	ret
.LBB0_4:
	li	a0, 11
	mul	a0, a1, a0
	addiw	a0, a0, 4
	ret
.LBB0_5:
	xori	a0, a1, 9
	ret
.LBB0_6:
	lui	a0, 349525
	addi	a0, a0, 1365
	mul	a0, a1, a0
	srli	a0, a0, 32
	sub	a0, a0, a1
	srliw	a2, a0, 31
	sraiw	a0, a0, 1
	add	a0, a0, a2
	addw	a0, a0, a1
	ret
.LBB0_7:
	andi	a0, a1, 31
	ret
.LBB0_8:
	addiw	a0, a1, -7
	ret
.LBB0_9:
	li	a0, 1
	subw	a0, a0, a1
	ret
.LBB0_10:
	srliw	a0, a1, 31
	add	a0, a0, a1
	sraiw	a0, a0, 1
	ret
.LBB0_11:
	mulw	a0, a1, a1
	ret
.LBB0_12:
	slli	a0, a1, 1
	addw	a0, a0, a1
	ret
.LBB0_13:
	slliw	a0, a1, 2
	ret
.LBB0_14:
	srli	a0, a1, 2
	addw	a0, a0, a1
	ret
.LBB0_15:
	srai	a0, a1, 1
	ret
.LBB0_16:
	lui	a0, 599186
	addi	a0, a0, 1171
	mul	a0, a1, a0
	srli	a0, a0, 32
	add	a0, a0, a1
	srliw	a2, a0, 31
	sraiw	a0, a0, 2
	add	a0, a0, a2
	slli	a2, a0, 3
	add	a0, a0, a1
	subw	a0, a0, a2
	ret
.LBB0_17:
	ori	a0, a1, 16
	ret
.LBB0_18:
	li	a0, -1
	ret
.Lfunc_end0:
	.size	classify, .Lfunc_end0-classify
	.section	.rodata,"a",@progbits
	.p2align	2, 0x0
.LJTI0_0:
	.word	.LBB0_2-.LJTI0_0
	.word	.LBB0_12-.LJTI0_0
	.word	.LBB0_8-.LJTI0_0
	.word	.LBB0_10-.LJTI0_0
	.word	.LBB0_5-.LJTI0_0
	.word	.LBB0_13-.LJTI0_0
	.word	.LBB0_15-.LJTI0_0
	.word	.LBB0_11-.LJTI0_0
	.word	.LBB0_17-.LJTI0_0
	.word	.LBB0_7-.LJTI0_0
	.word	.LBB0_16-.LJTI0_0
	.word	.LBB0_4-.LJTI0_0
	.word	.LBB0_6-.LJTI0_0
	.word	.LBB0_14-.LJTI0_0
	.word	.LBB0_3-.LJTI0_0
	.word	.LBB0_9-.LJTI0_0
                                        # -- End function
	.ident	"Homebrew clang version 23.1.2"
	.section	".note.GNU-stack","",@progbits
	.addrsig

Key idea

A table entry is a distance, not an address: 32 bits on x86-64 and RISC-V, 8 bits on AArch64 when every landing is close enough, so sixteen cases cost 64, 64 and 16 bytes of data.

Checkpoint

Check: Reading a generated table

  1. One question In the AArch64 recording each table entry is one byte. How many bytes of read-only data does the whole sixteen-case table take?

    Type a number.

    A hint

    Count the entries, not the landings they point at.

    Show the answer

    Answer: 16 bytes

    Sixteen entries of one byte each is 16 bytes, against 64 bytes for the same switch on x86-64 and RISC-V, where an entry is a 32-bit offset.

Why the entries are 32-bit offsets, not addresses

A table of 64-bit addresses would be twice the size and, worse, would hold absolute addresses. An executable that the loader may place anywhere cannot carry absolute addresses in its data without the loader patching every one of them at start-up, so the compiler stores differences instead: each entry is the distance from a fixed point that moves with the code. On x86-64 and RISC-V the fixed point is the table’s own start, which is why the recording shows the base being added back after the load; on AArch64 it is the first landing.

A difference between two places in the same image does not change when the image moves, so the linker computes each entry once and nothing is left for the loader. That is what the relocations in the recording are: sixteen R_X86_64_PC32 entries in .rela.rodata, each asking the linker, not the loader, for one 32-bit difference.

Property A table of addresses A table of 32-bit offsets
Bytes per entry 8 4, or 1 on AArch64
Patched at start-up yes, one relocation each no
Lives in data the loader writes read-only data
Reach anywhere ±2 GB from the base

What offsets cost is reach: a 32-bit signed difference spans about 2 GB in each direction, and AArch64’s entries reach only 255 instructions past the first landing. The compiler knows the sizes of the blocks it just emitted, so it picks the narrowest entry that fits and widens to ldrh or a word when the cases are longer.

Checkpoint

Check: Entries are offsets, not addresses

  1. One question A colleague proposes storing full 64-bit addresses in the table so the dispatch needs no add. What does that cost in a position-independent executable?

    Choose one answer.

    Show the answer

    Answer: The loader has to patch every entry at start-up, and the table moves from read-only data to writable data.

    Offsets from a point inside the same image survive relocation, so the linker resolves all sixteen and the loader does nothing. Absolute addresses would need one load-time relocation each, in writable data.

Dense or sparse: when the compiler picks a compare tree

A table is indexed by the switch value, so its size is set by the range of the case values, not by how many there are. Sixteen cases from 0 to 15 need sixteen entries. Sixteen cases spread from 1 to 60,000 would need 60,000 entries for the same sixteen landings, which is why the compiler drops the table and compares instead. This session measures both, and then the same six dense cases on two targets.

sparse.c: sixteen cases, spread from 1 to 60,000 C · sparse.c 
/* sparse.c: sixteen cases again, but spread out instead of dense.
 *
 * The case values are the same count as classify.c's, yet they run from 1 to 60,000.
 * A table indexed by the switch value would need 60,000 entries for sixteen landings,
 * so the compiler drops the table and compares instead.
 */
int sparse(int kind, int value)
{
    switch (kind) {
    case 1:
        return value + 5;
    case 7:
        return value * 3;
    case 19:
        return value - 7;
    case 42:
        return value / 2;
    case 97:
        return value ^ 9;
    case 203:
        return value << 2;
    case 460:
        return value >> 1;
    case 911:
        return value * value;
    case 1700:
        return value | 16;
    case 3300:
        return value & 31;
    case 6100:
        return value % 7;
    case 9800:
        return value * 11 + 4;
    case 14500:
        return value - value / 3;
    case 23000:
        return value + (value >> 2);
    case 38000:
        return value * 5 - 1;
    case 60000:
        return ~value + 2;
    default:
        return -1;
    }
}
Sparse cases, and a threshold that differs by target Python · density_session.py 
"""Compile a sparse switch and a six-case switch, and count what the compiler chose instead of a table.

Three measurements: sixteen spread-out cases on x86-64 (compares, no table), the same six dense cases
on x86-64 and on AArch64 (a table on one, none on the other), and the AArch64 switch again with the
compiler's table threshold lowered, which brings the table back.
"""

import pathlib
import sys

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

session.run(
    """
# Sixteen cases spread from 1 to 60,000: how many compares, and how many table entries?
/opt/homebrew/opt/llvm/bin/clang -O2 -S -target x86_64-linux-gnu sparse.c -o sparse_x86_64.s
printf 'cmpl: '; grep -cE 'cmpl' sparse_x86_64.s; printf 'table entries: '; grep -cE '[.]long[[:space:]]+[.]LBB' sparse_x86_64.s || true
# Six dense cases, x86-64: a six-entry table of four-byte offsets, 24 bytes in all.
/opt/homebrew/opt/llvm/bin/clang -O2 -S -target x86_64-linux-gnu six.c -o six_x86_64.s
printf 'table entries: '; grep -cE '[.]long[[:space:]]+[.]LBB' six_x86_64.s
# The same six cases for AArch64: the compiler picks conditional selects, with no branch at all.
clang -O2 -S six.c -o six_aarch64.s
printf 'csel: '; grep -cE 'csel' six_aarch64.s; printf 'table entries: '; grep -cE '[.]byte[[:space:]]+[(]LBB' six_aarch64.s || true
# AArch64 again with the table threshold lowered to four entries: the table is back.
clang -O2 -mllvm -aarch64-min-jump-table-entries=4 -S six.c -o six_lowered.s
printf 'table entries: '; grep -cE '[.]byte[[:space:]]+[(]LBB' six_lowered.s
"""
)

Output

# Sixteen cases spread from 1 to 60,000: how many compares, and how many table entries?
$ /opt/homebrew/opt/llvm/bin/clang -O2 -S -target x86_64-linux-gnu sparse.c -o sparse_x86_64.s
$ printf 'cmpl: '; grep -cE 'cmpl' sparse_x86_64.s; printf 'table entries: '; grep -cE '[.]long[[:space:]]+[.]LBB' sparse_x86_64.s || true
cmpl: 23
table entries: 0
# Six dense cases, x86-64: a six-entry table of four-byte offsets, 24 bytes in all.
$ /opt/homebrew/opt/llvm/bin/clang -O2 -S -target x86_64-linux-gnu six.c -o six_x86_64.s
$ printf 'table entries: '; grep -cE '[.]long[[:space:]]+[.]LBB' six_x86_64.s
table entries: 6
# The same six cases for AArch64: the compiler picks conditional selects, with no branch at all.
$ clang -O2 -S six.c -o six_aarch64.s
$ printf 'csel: '; grep -cE 'csel' six_aarch64.s; printf 'table entries: '; grep -cE '[.]byte[[:space:]]+[(]LBB' six_aarch64.s || true
csel: 7
table entries: 0
# AArch64 again with the table threshold lowered to four entries: the table is back.
$ clang -O2 -mllvm -aarch64-min-jump-table-entries=4 -S six.c -o six_lowered.s
$ printf 'table entries: '; grep -cE '[.]byte[[:space:]]+[(]LBB' six_lowered.s
table entries: 6

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 density_session.py

The sparse switch produced 23 cmpl instructions and no table at all: a tree of compares that splits the range, roughly four or five tests to reach a landing. The six-case switch is the interesting one. On x86-64 clang built a six-entry table, 24 bytes. On AArch64 it emitted seven csel instructions and no branch at all, because the compiler used for this lesson keeps a table only from ten cases up on that target, the default that LLVM’s AArch64 back end sets for a build that does not optimise for size; lowering that limit to four with -mllvm -aarch64-min-jump-table-entries=4 brings a six-entry table back from the same source.

GCC exposes the same decision as a tunable parameter, case-values-threshold, documented as the smallest count of distinct values that makes a table better than a tree of conditional branches, with zero meaning the target’s own default. So “dense switch statements become jump tables” is a rule about the compiler’s judgement, not about the language: the same source is a table, a tree or a run of conditional selects depending on the target and the flags.

Interactive · answer and compare Table, tree or selects: what the compiler weighs Answer two questions about your case values to see which lowering the compiler can reach for.
Do your case values run from 0 with no gaps, or are they spread far apart?
Does each case run its own code, or does each one just produce a value?

Answer the questions above: the table then marks what fits your case and says why the rest does not.

Four lowerings of a switch against the shapes of case values this lesson measured.
Lowering Dense values Values spread out Work per call Under CFI
Jump table Reads: one entry of a table Good sixteen dense cases cost 16 bytes of table on AArch64, 64 on x86-64 Poor values 1 to 60,000 would need 60,000 entries for sixteen landings Good one check, one load, one add, one branch, whatever the case Mixed needs a no-track prefix, marked landings or a guarded register
Tree of compares Reads: the value, repeatedly Mixed works, but 23 compares stood where one indexed jump would do Good the only shape that ignores the range of the values Mixed about four or five tests for sixteen cases, each one predicted Good direct branches only, so no landing pad is involved
Conditional selects Reads: the value, branchlessly Mixed the AArch64 build used seven csel for six dense cases Poor every case is computed, so spread-out values multiply the work Mixed every case computed, no branch at all, no misprediction Good no indirect branch, so nothing to guard
Table of results Reads: one entry of a table Good one load and no branch when every case returns a constant Poor indexed by the value, so the same holes as a jump table Good one load; the cheapest shape when it applies Good plain data load, no indirect branch to guard
How the answers decide
  • “Do your case values run from 0 with no gaps, or are they spread far apart?” Spread out: rules out Jump table and Table of results. Both are indexed by the switch value, so the range of the values sets the table's size.
  • “Does each case run its own code, or does each one just produce a value?” A value only: adds a caveat to Jump table. With a value per case the compiler prefers a table of results and skips the indirect branch.
  • “Does each case run its own code, or does each one just produce a value?” Its own code: rules out Table of results. A table of results can only hold values, so cases with their own code need a landing each.
  • “Do your case values run from 0 with no gaps, or are they spread far apart?” Dense, 0 upwards and “Does each case run its own code, or does each one just produce a value?” Its own code: adds a caveat to Conditional selects. Selects compute every case, so they fit a handful of cheap cases, not sixteen blocks.

Counting cases instead of the range

Reading sixteen cases and expecting a table misses the point twice over: the error codes 2, 404 and 60,000 are sixteen cases with a 60,000-wide range, so the table never appears, and renumbering them 0 to 15 can change a hot dispatch from five compares to one indexed jump. Read the case values, not their count.

Checkpoint

Check: Dense values, sparse values

  1. One question A switch has sixteen cases with values 1, 7, 19 … 60,000. The recording shows what the compiler did with it. Which is it?

    Choose one answer.

    Show the answer

    Answer: 23 compare instructions and no table, because a table indexed by the value would need 60,000 entries.

    The recorded build produced 23 cmpl instructions and zero table entries. Density, not case count, decides whether an indexed jump is possible at all.

Control-flow integrity: endbr64, BTI and lpad

An indirect branch is the one place where the processor takes its next address from data. If an attacker can write that data, or can reach the branch with a value of their choosing, the branch goes wherever they like, which is why all three ISAs now have a hardware check for it. control-flow integrity: A defence that limits where a program's control transfers may go: the compiler marks the legal targets of indirect branches, calls and returns, and the processor or the run time faults on a transfer to anything else. marks the legal targets, and the processor faults on a branch to anything else.

The marks are per ISA, and the first session shows the x86-64 one: the same source built with -fcf-protection=none and with -fcf-protection=full. GCC documents those keywords, branch for indirect branches and return for returns, with full as the pair.

x86-64: endbr64 at the entry, and the jump's 3e prefix Python · endbr_session.py 
"""Build the switch for x86-64 Linux twice, with Control-flow Enforcement off and on.

The two disassemblies differ in two bytes' worth of marks: an endbr64 at the function's entry, and a
0x3e prefix on the table's indirect jump. Counting the endbr64 markers shows how many legal landings
for an indirect branch the object declares.
"""

import pathlib
import sys

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

session.run(
    """
# Without CET marks: the function starts straight with its bounds check.
/opt/homebrew/opt/llvm/bin/clang -O2 -c -target x86_64-linux-gnu -fcf-protection=none classify.c -o cet_off.o
/opt/homebrew/opt/llvm/bin/llvm-objdump -d --no-leading-addr cet_off.o | sed -n '6,8p'
# With CET: endbr64 at the entry, and the table's jump carries the 3e no-track prefix.
/opt/homebrew/opt/llvm/bin/clang -O2 -c -target x86_64-linux-gnu -fcf-protection=full classify.c -o cet_on.o
/opt/homebrew/opt/llvm/bin/llvm-objdump -d --no-leading-addr cet_on.o | sed -n '6,15p'
# How many endbr64 markers each object declares, for sixteen landings plus the entry.
for f in cet_off.o cet_on.o; do printf '%s: ' $f; /opt/homebrew/opt/llvm/bin/llvm-objdump -d $f | grep -c endbr64; done
"""
)

Output

# Without CET marks: the function starts straight with its bounds check.
$ /opt/homebrew/opt/llvm/bin/clang -O2 -c -target x86_64-linux-gnu -fcf-protection=none classify.c -o cet_off.o
$ /opt/homebrew/opt/llvm/bin/llvm-objdump -d --no-leading-addr cet_off.o | sed -n '6,8p'
<classify>:
 83 ff 0f                              	cmpl	$0xf, %edi
 0f 87 aa 00 00 00                     	ja	0xb3 <classify+0xb3>
# With CET: endbr64 at the entry, and the table's jump carries the 3e no-track prefix.
$ /opt/homebrew/opt/llvm/bin/clang -O2 -c -target x86_64-linux-gnu -fcf-protection=full classify.c -o cet_on.o
$ /opt/homebrew/opt/llvm/bin/llvm-objdump -d --no-leading-addr cet_on.o | sed -n '6,15p'
<classify>:
 f3 0f 1e fa                           	endbr64
 83 ff 0f                              	cmpl	$0xf, %edi
 0f 87 ab 00 00 00                     	ja	0xb8 <classify+0xb8>
 89 f0                                 	movl	%esi, %eax
 89 f9                                 	movl	%edi, %ecx
 48 8d 15 00 00 00 00                  	leaq	(%rip), %rdx            # 0x18 <classify+0x18>
 48 63 0c 8a                           	movslq	(%rdx,%rcx,4), %rcx
 48 01 d1                              	addq	%rdx, %rcx
 3e ff e1                              	jmpq	*%rcx
# How many endbr64 markers each object declares, for sixteen landings plus the entry.
$ for f in cet_off.o cet_on.o; do printf '%s: ' $f; /opt/homebrew/opt/llvm/bin/llvm-objdump -d $f | grep -c endbr64; done
cet_off.o: 0
cet_on.o: 1

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 endbr_session.py

Count the marks in the recording: one endbr64, not seventeen. The entry of the function gets the landing pad: An instruction that marks a legal target of an indirect branch or call, so a processor enforcing control-flow integrity accepts the transfer: endbr64 on x86-64, bti on AArch64, lpad on RISC-V. because the function can be called indirectly, and the sixteen case blocks get none. What makes that safe is the extra byte on the jump itself, 3e ff e1 instead of ff e1: the 3e prefix tells the processor not to track this branch, so the branch is allowed to land on an instruction that is not a landing pad. The table is read-only and the bounds check is right above it, so the compiler takes that trade.

AArch64 does not have the prefix, so it marks every landing instead. The second session compiles the same switch with -mbranch-protection=bti: bti c guards the function entry and bti j guards all sixteen case blocks, seventeen marks in all. Arm’s System V ABI states the rule the marks satisfy: an indirect branch into a guarded page has to land on a bti instruction whose kind matches the branch, and a loader learns that an image is BTI-ready from a GNU property note.

AArch64 bti c and bti j, then RISC-V lpad Python · cfi_marks_session.py 
"""Compile the same switch with AArch64 branch-target identification, then with RISC-V landing pads.

Both are compiled for Linux targets, so nothing here runs; the marks the compiler puts in the
assembly are the evidence. AArch64 marks every landing of the table; RISC-V marks only the function
entry and changes the dispatch register instead.
"""

import pathlib
import sys

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

session.run(
    """
# AArch64 with BTI: bti c guards the entry, bti j guards each landing of the table.
/opt/homebrew/opt/llvm/bin/clang -O2 -S -target aarch64-linux-gnu -march=armv8.5-a -mbranch-protection=bti classify.c -o bti.s
sed -n '/^classify:/,/^.LBB0_3:/p' bti.s
# One bti c and one bti j per landing: seventeen marks for sixteen cases.
printf 'bti c: '; grep -c 'bti.*c$' bti.s; printf 'bti j: '; grep -c 'bti.*j$' bti.s
# RISC-V with Zicfilp (still an experimental extension in this compiler): lpad marks the entry.
/opt/homebrew/opt/llvm/bin/clang -O2 -S -target riscv64-linux-gnu -menable-experimental-extensions -march=rv64gc_zicfilp1p0 -fcf-protection=branch -mcf-branch-label-scheme=unlabeled classify.c -o lpad.s
sed -n '/^classify:/,/jr/p' lpad.s
printf 'lpad: '; grep -c 'lpad' lpad.s
"""
)

Output

# AArch64 with BTI: bti c guards the entry, bti j guards each landing of the table.
$ /opt/homebrew/opt/llvm/bin/clang -O2 -S -target aarch64-linux-gnu -march=armv8.5-a -mbranch-protection=bti classify.c -o bti.s
$ sed -n '/^classify:/,/^.LBB0_3:/p' bti.s
classify:                               // @classify
	.cfi_startproc
// %bb.0:
	bti	c
	cmp	w0, #15
                                        // kill: def $w1 killed $w1 def $x1
	b.hi	.LBB0_18
// %bb.1:
	mov	w8, w0
	adrp	x9, .LJTI0_0
	add	x9, x9, :lo12:.LJTI0_0
	adr	x10, .LBB0_2
	ldrb	w11, [x9, x8]
	add	x10, x10, x11, lsl #2
	br	x10
.LBB0_2:
	bti	j
	add	w0, w1, #5
	ret
.LBB0_3:
# One bti c and one bti j per landing: seventeen marks for sixteen cases.
$ printf 'bti c: '; grep -c 'bti.*c$' bti.s; printf 'bti j: '; grep -c 'bti.*j$' bti.s
bti c: 1
bti j: 16
# RISC-V with Zicfilp (still an experimental extension in this compiler): lpad marks the entry.
$ /opt/homebrew/opt/llvm/bin/clang -O2 -S -target riscv64-linux-gnu -menable-experimental-extensions -march=rv64gc_zicfilp1p0 -fcf-protection=branch -mcf-branch-label-scheme=unlabeled classify.c -o lpad.s
$ sed -n '/^classify:/,/jr/p' lpad.s
classify:                               # @classify
	.cfi_startproc
# %bb.0:
	lpad	0
	li	a2, 15
	bltu	a2, a0, .LBB0_18
# %bb.1:
.Lpcrel_hi0:
	auipc	a2, %pcrel_hi(.LJTI0_0)
	slli	a0, a0, 2
	addi	a2, a2, %pcrel_lo(.Lpcrel_hi0)
	add	a0, a0, a2
	lw	a0, 0(a0)
	add	t2, a2, a0
	jr	t2
$ printf 'lpad: '; grep -c 'lpad' lpad.s
lpad: 1

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 cfi_marks_session.py

RISC-V takes the third route. In the same recording the Zicfilp build has exactly one lpad, at the entry, and the dispatch changed: the address lands in t2 and the branch is jr t2. The RISC-V manual’s control-flow-integrity chapter calls an indirect branch through x7, which is t2, a software-guarded branch, says such branches need no landing pad, and names compiled switch-cases as a use for them. The compiler changed one register to stay inside the rule.

ISA Mark At the function entry At the table’s landings How the table’s branch is allowed
x86-64 (CET) endbr64 yes no 3e no-track prefix on jmpq
AArch64 (BTI) bti c, bti j bti c bti j on each the landings are marked
RISC-V (Zicfilp) lpad yes no branch through x7 is software-guarded

Key idea

Each ISA lets a compiler’s own jump table through the landing-pad check in its own way: a no-track prefix exempts the jump on x86-64, a bti j on every landing satisfies the check on AArch64, and a branch through x7 is exempt on RISC-V.

Checkpoint

Check: Landing pads for the indirect jump

  1. One question The x86-64 build with Control-flow Enforcement has one endbr64 for sixteen landings. What makes the table's jump legal?

    Choose one answer.

    Show the answer

    Answer: The jump carries the no-track prefix (3e ff e1), so the processor does not require a landing pad for it.

    The recording shows 3e ff e1 where the unprotected build has ff e1. AArch64 took the other route and marked all sixteen landings with bti j.

Writing a jump table by hand

A hand-written table makes the shape concrete. This one dispatches four operations on AArch64 with the same five parts the compiler uses, and the entries are one byte each, measured from the first landing in instructions.

handwritten_table_aarch64.s S · handwritten_table_aarch64.s 
// handwritten_table_aarch64.s: a four-case dispatcher whose jump table is written by hand.
// AArch64, Mach-O; Apple clang assembles and links it, and the session runs it.
//
//   int opcode(int op, int value);
//     op 0 -> value + 1      op 1 -> value * 2
//     op 2 -> value - 3      op 3 -> 0 - value      anything else -> -1
        .section __TEXT,__text,regular,pure_instructions
        .globl  _opcode
        .p2align 2
_opcode:
        cmp     w0, #3                  // the bounds check: is op one of 0..3?
        b.hi    Ldefault                // unsigned compare, so a negative op is above 3 too
        adrp    x9, Ltable@PAGE         // x9 = the table of one-byte entries
        add     x9, x9, Ltable@PAGEOFF
        adr     x10, Lcase0             // x10 = the first landing, which the entries measure from
        ldrb    w11, [x9, w0, uxtw]     // w11 = Ltable[op], the distance in instructions
        add     x10, x10, x11, lsl #2   // every instruction is four bytes wide
        br      x10                     // the indirect jump: one branch for any op
Lcase0:
        add     w0, w1, #1
        ret
Lcase1:
        lsl     w0, w1, #1
        ret
Lcase2:
        sub     w0, w1, #3
        ret
Lcase3:
        neg     w0, w1
        ret
Ldefault:
        mov     w0, #-1
        ret

        .section __TEXT,__const
        .p2align 2
Ltable:
        .byte   (Lcase0-Lcase0)>>2      // 0 instructions past Lcase0
        .byte   (Lcase1-Lcase0)>>2      // 2 instructions past it
        .byte   (Lcase2-Lcase0)>>2      // 4
        .byte   (Lcase3-Lcase0)>>2      // 6
Interactive · step by step One dispatch through the hand-written table Follow op 2 through the four-byte table of the hand-written dispatcher to the block it runs.
One dispatch through the hand-written table, step 5 of 5. Showing op = 2, Ltable, entry = 4, Lcase0, Lcase2. In focus: Lcase2.index4 instructionsop = 2Ltable00 02 04 06entry = 4Lcase0the first landingLcase2sub w0, w1, #3

The drawing shows the whole scene; its 5 steps are listed below.

Every step as text
  1. The op arrives. The caller passes op 2 in w0. The bounds check above has already sent anything outside 0 to 3 to the default block, so this value is safe to use as an index.
  2. Index the table of bytes. Ltable holds four bytes, 00 02 04 06, dumped from the linked binary by the session below. ldrb reads the byte at index 2.
  3. The entry is a distance. The byte read is 4, meaning four instructions past the first landing. It is not an address, so by itself it points nowhere.
  4. Add the first landing. The code holds Lcase0 in x10 from an adr instruction. Adding the entry shifted left by two turns four instructions into sixteen bytes.
  5. Land in the right block. br x10 arrives at Lcase2, which subtracts 3 and returns. The run below shows op 2 with value 20 giving 17.

The session assembles it with a C driver, runs it for ops -1 to 4, disassembles the dispatcher out of the linked binary and dumps the four table bytes. They are 00 02 04 06, because each case block is two instructions long, and the two ops outside the range both return -1.

Running the hand-written dispatcher Python · handwritten_session.py 
"""Assemble, link and run the hand-written AArch64 dispatcher, then read its table out of the binary.

Apple clang assembles the hand-written source and links it with a C driver into one AArch64
program, so the four results and the four table bytes come from the same binary.
"""

import pathlib
import sys

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

session.run(
    """
# Assemble the hand-written dispatcher with a C driver and run it for ops -1 to 4.
clang -O2 -o hand hand_driver.c handwritten_table_aarch64.s
./hand
# The dispatcher as the linker left it: bounds check, table address, one byte, indirect branch.
/opt/homebrew/opt/llvm/bin/llvm-objdump -d --no-leading-addr --disassemble-symbols=_opcode hand | sed -n '5,20p'
# The four table bytes: each landing's distance from the first, in instructions.
/opt/homebrew/opt/llvm/bin/llvm-objdump -s -j __const hand | sed -n '3,5p'
"""
)

Output

# Assemble the hand-written dispatcher with a C driver and run it for ops -1 to 4.
$ clang -O2 -o hand hand_driver.c handwritten_table_aarch64.s
$ ./hand
value = 20
op -1 -> -1
op  0 -> 21
op  1 -> 40
op  2 -> 17
op  3 -> -20
op  4 -> -1
# The dispatcher as the linker left it: bounds check, table address, one byte, indirect branch.
$ /opt/homebrew/opt/llvm/bin/llvm-objdump -d --no-leading-addr --disassemble-symbols=_opcode hand | sed -n '5,20p'

<_opcode>:
 71000c1f              	cmp	w0, #0x3
 540001e8              	b.hi	0x1000005d4 <_opcode+0x40>
 90000009              	adrp	x9, 0x100000000 <_printf+0x100000000>
 91181129              	add	x9, x9, #0x604
 1000008a              	adr	x10, 0x1000005b4 <_opcode+0x20>
 3860492b              	ldrb	w11, [x9, w0, uxtw]
 8b0b094a              	add	x10, x10, x11, lsl #2
 d61f0140              	br	x10
 11000420              	add	w0, w1, #0x1
 d65f03c0              	ret
 531f7820              	lsl	w0, w1, #1
 d65f03c0              	ret
 51000c20              	sub	w0, w1, #0x3
 d65f03c0              	ret
# The four table bytes: each landing's distance from the first, in instructions.
$ /opt/homebrew/opt/llvm/bin/llvm-objdump -s -j __const hand | sed -n '3,5p'
Contents of section __TEXT,__const:
 100000604 00020406                             ....

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 handwritten_session.py

Two details are easy to get wrong by hand. The index must be zero-extended, not sign-extended, which is what uxtw in ldrb w11, [x9, w0, uxtw] says; and the table has to be reached PC-relatively, through adrp plus add, or the object will not link into a position-independent executable. Real code almost always lets the compiler build the table: it sizes the entries, keeps them in step with the blocks it moves around during optimisation, and adds the control-flow-integrity marks the target needs. Hand-written jump tables belong in startup code, interpreters with a measured dispatch loop, and places with no compiler in the way.

Checkpoint

Check: A table written by hand

  1. One question The hand-written dispatcher reads its entry with ldrb w11, [x9, w0, uxtw]. Why uxtw rather than sxtw?

    Choose one answer.

    Show the answer

    Answer: The index must be zero-extended; sign-extending a value that has passed an unsigned bounds check would be pointless and could compute a negative offset.

    The index is an unsigned 0 to 3 by the time the load runs, so it is widened with uxtw. The scaling to bytes happens in the following add, which shifts the entry left by two.

Practise

Two hands-on changes come first, each built and run with the commands its own session shows. The questions after them use the recordings on this page: the entry widths, the counts from the sparse build and the three control-flow-integrity marks.

  1. Copy handwritten_table_aarch64.s and give it a fifth operation, op 4, that returns value >> 2 with asr w0, w1, #2. Three places change: the bounds check, a new case block and a fifth table byte. Predict the five bytes of the table dump and the results for op 4 and op 5, then extend the driver’s loop to op 5 and run it.
  2. Copy sparse.c, renumber its sixteen cases 0 to 15 and leave every case body as it is. Compile it for x86-64 as the density session does and count the cmpl lines and the table entries again. Which count moved, and which part of the dispatch is the one compare that is left?

Practice that adapts to you

Practise this lesson

13 questions about 6 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.

  1. Question 1 of 13 Which sequence matches the dispatch of a dense switch?

    Choose one answer.

    Show the answer

    Answer: Bounds check, index, read one table entry, add the base, indirect branch.

    The order matters: the check comes first so that no out-of-range value is ever used as an index into the table.

  2. Question 2 of 13 You find a hand-written dispatcher that indexes a sixteen-entry table with a value straight from a network message, with no compare. What is the most accurate description?

    Choose one answer.

    Show the answer

    Answer: It reads whatever bytes follow the table for an out-of-range value and branches there, so the caller chooses the branch target.

    This is why every compiler-generated dispatch starts with one unsigned compare, and why a hand-written table must copy that habit.

  3. Question 3 of 13 In the x86-64 dispatch, which instruction reads one entry of the table?

    Choose one answer.

    Show the answer

    Answer: movslq (%rdx,%rcx,4), %rcx

    The scale of 4 in the addressing mode is the entry width, which is how you can read an entry's size straight off the dispatch.

  4. Question 4 of 13 An AArch64 table entry is assembled from (LBB0_12-LBB0_2)>>2. What does the byte hold?

    Choose one answer.

    Show the answer

    Answer: The distance from the first landing to this case's landing, counted in instructions.

    Because the entry counts instructions rather than bytes, one byte reaches 255 instructions past the first landing, which is enough for sixteen short blocks.

  5. Question 5 of 13 How wide is one jump-table entry on x86-64 in the recording?

    Type a number.

    Show the answer

    Answer: 4 bytes

    Four bytes, a 32-bit offset from the table's own address, which is why .rodata is 0x40 bytes for sixteen cases and why the scale in the addressing mode is 4.

  6. Question 6 of 13 What limits a table of 32-bit offsets, and what does the compiler do about it?

    Choose one answer.

    Show the answer

    Answer: Reach, about 2 GB from the base; the compiler picks the narrowest entry width that still reaches every landing.

    The compiler knows the sizes of the blocks it has just emitted, so it can choose a byte, a halfword or a word per entry and still reach every landing.

  7. Question 7 of 13 What decides the size of a jump table?

    Choose one answer.

    Show the answer

    Answer: The range of the case values, because the switch value is the index.

    Sixteen dense cases need sixteen entries; the same sixteen cases spread to 60,000 would need 60,000, which is why the recorded sparse build compares instead.

  8. Question 8 of 13 A hot dispatcher switches on error codes 2, 404, 1001 and 60,000, and the profile blames its branches. Which change is most likely to help, and why?

    Choose one answer.

    Show the answer

    Answer: Renumber the codes 0 to 3 internally and switch on that, so an indexed jump becomes possible.

    Dense switch statements are the ones that become jump tables, so a translation step from sparse codes to a dense index is the usual fix for a hot sparse dispatcher.

  9. Question 9 of 13 Which control-flow-integrity marker belongs to which ISA?

    Choose one answer.

    Show the answer

    Answer: endbr64 on x86-64, bti on AArch64, lpad on RISC-V.

    Intel calls it Control-flow Enforcement, Arm calls it Branch Target Identification and RISC-V calls it Zicfilp, and each marks the legal targets of indirect branches in its own way.

  10. Question 10 of 13 The AArch64 build with branch protection marks the function entry and every landing of the sixteen-case table. How many bti instructions is that?

    Type a number.

    Show the answer

    Answer: 17

    One bti c at the entry plus sixteen bti j, one per landing, which is what the recording counts. x86-64 needed only one marker because its table jump carries the no-track prefix.

  11. Question 11 of 13 You write your own AArch64 dispatcher by hand and the rest of the image is built with branch protection. What must your assembly include?

    Choose one answer.

    Show the answer

    Answer: A bti j at every landing the indirect branch can reach, and a bti c at the entry if the function is called indirectly.

    This is the practical reason to let the compiler build the table: it adds the markers the target needs and keeps them with the blocks as it moves them.

  12. Question 12 of 13 In the hand-written dispatcher, what does adr x10, Lcase0 provide?

    Choose one answer.

    Show the answer

    Answer: The address of the first landing, which every table entry is measured from.

    Two addresses are needed in the dispatch: the table's, for the load, and the first landing's, for the add.

  13. Question 13 of 13 The hand-written table dumps as 00 02 04 06. Why do consecutive entries differ by 2?

    Choose one answer.

    Show the answer

    Answer: Each case block is two instructions long, and the entries count instructions.

    The source writes each entry as a label difference shifted right by two, so a two-instruction block gives a step of 2 and the whole four-case table fits in four bytes.

Interview questions

Warm-up: for a dense set of cases, why is a jump table quicker than a tree of compares, and when does the tree win anyway?

A table costs the same work for every case: one bounds check, one load of an entry, one add and one indirect branch, whatever the value. A tree of compares costs about as many tests as the depth of the tree it builds, four or five conditional branches for sixteen cases, and each one is a chance for the branch predictor to be wrong. The table also keeps the code small, because the decision lives in data rather than in instructions. The tree wins in three situations. When the case values are spread out, a table indexed by the value would be mostly holes, so there is nothing to index. When there are only two or three cases, the compares are shorter than the whole dispatch, and a compiler may go further and remove the branch with conditional selects, as the AArch64 build on this page did for six cases. And when one case is far hotter than the rest, a compare for it first is predicted almost perfectly, while the table’s indirect branch has to be predicted from a history of mixed targets.

Work out your own answer to each of the two questions below, then open its first step and follow-ups on the module’s question page.

Model answers open with any pass: ₹79 for 1 week ($2.99), one payment that never renews.

Choose a pass

  1. Mid to senior

    A service built with control-flow enforcement on x86-64 dies with a control-protection fault, and the faulting address is inside a plugin dispatcher that jumps through a table. What does the hardware's rule tell you about the bug, and how would you narrow it down and fix it?

    First step and follow-ups

  2. Senior to staff

    You have a stripped AArch64 binary of a bytecode interpreter whose main loop switches on 256 opcodes. Walk through how you would find the dispatcher, recover the table, and work out which block belongs to which opcode.

    First step and follow-ups

Flashcards · 6 cards

Recall it, then check

Say the answer to yourself before you look: recalling it is what makes it stick.

  1. What does a dense switch statement compile to?

    One bounds check, one load from a table, one add and one indirect branch. The table lives in read-only data, next to the string literals.

  2. Why are jump-table entries offsets rather than addresses, and how big are they?

    An offset from a fixed point in the same image stays correct wherever the image is loaded, so the linker resolves every entry and the loader patches none. Entries are 4 bytes on x86-64 and RISC-V and can be 1 byte on AArch64, so sixteen cases cost 64, 64 and 16 bytes.

  3. What decides whether a compiler builds a jump table or a tree of compares?

    The range of the case values, not how many there are. Spread-out values would leave a table mostly empty, so the lesson's sparse switch became 23 compares and no table, and a target's own threshold can rule out a table even for six dense cases.

  4. Why is a jump table quicker than a tree of compares for many dense cases?

    The table costs the same few instructions for every value, while a tree costs one conditional branch per level, four or five for sixteen cases, and each of them can be mispredicted.

  5. Which instructions mark legal targets of indirect branches under control-flow integrity?

    endbr64 on x86-64, bti c and bti j on AArch64, and lpad on RISC-V. A processor enforcing the check faults when an indirect branch lands anywhere else.

  6. How does each ISA let a compiler's own jump table get through the landing-pad check?

    On x86-64 a no-track prefix exempts that indirect jump. On AArch64 every landing gets a bti j, which satisfies the check. On RISC-V a jump through register x7 is exempt.

Key takeaways

  • A dense switch lowers to one bounds check, one table read, one add and one indirect branch, and the table lives in read-only data beside the string literals.
  • Entries are distances, not addresses: four bytes on x86-64 and RISC-V, one byte on AArch64 when the landings are close, so the sixteen-case table costs 64, 64 and 16 bytes.
  • Offsets from a fixed point in the same image survive relocation, so the linker resolves every entry and the loader patches none.
  • The range of the case values, not their count, decides whether switch statements get a table: the sparse build in this lesson produced 23 compares and no table, and a target’s own threshold can rule the table out for six dense cases.
  • Control-flow integrity guards the indirect branch with endbr64, bti c and bti j, or lpad, and each ISA lets a compiler’s table jump through in its own way: a no-track prefix on x86-64, a bti j on every landing on AArch64, a branch through x7 on RISC-V.
  • A hand-written table works on AArch64 with adrp, ldrb and br, but the compiler sizes its entries and keeps them correct while it moves blocks around.

Terms in this lesson

bounds check
A compare that proves an index is inside the range of the thing it indexes before the index is used. One unsigned compare covers both ends, because a negative value read as unsigned is larger than any valid index.
control-flow integrity
A defence that limits where a program's control transfers may go: the compiler marks the legal targets of indirect branches, calls and returns, and the processor or the run time faults on a transfer to anything else.
jump table
A table of addresses, or of 32-bit or smaller offsets, indexed by a value, which turns a dense switch into one indirect jump instead of a chain of compares. Compilers keep it in read-only data.
landing pad
An instruction that marks a legal target of an indirect branch or call, so a processor enforcing control-flow integrity accepts the transfer: endbr64 on x86-64, bti on AArch64, lpad on RISC-V.

References

Report a problem with this lesson