Optimisation and undefined behaviour in assembly

At -O0, Clang compiles sum_squares in opt.c with two calls of a helper; at -O2 the calls are gone, and a multiply and a multiply-add remain. The same switch turns x + n < x, a test for overflow, into one shift that never reads x, and for x = INT_MAX - 50 and n = 100 the -O2 build answers 0 where the -O0 build answered 1. Reading optimisation and undefined behaviour in assembly means asking what the compiler was allowed to assume.

Optimisation shows as code that is missing, moved or repeated; undefined behaviour, as a test that is not there.

An optimised listing shows four fingerprints

At -O0 each function of opt.c keeps the shape of its source; at -O2 each one changed in a way you can learn to spot:

// opt.c: three small functions whose -O2 listings show what the optimiser did to them

// square is static, so no other file can call it: -O2 is free to copy its body into the caller.
static int square(int x) { return x * x; }
int sum_squares(int a, int b) { return square(a) + square(b); }

// scale is defined elsewhere; calling it is the last thing forward does.
int scale(int x);
int forward(int x) { return scale(x + 1); }

// A loop whose trip count, 3, is known while compiling.
int dot3(const int *a, const int *b) {
    int s = 0;
    for (int i = 0; i < 3; i++)
        s += a[i] * b[i];
    return s;
}

import pathlib
import sys

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

session.run("""
# opt.c at -O0 for AArch64 Linux: the labels and every call (bl) in the listing
clang --target=aarch64-linux-gnu -O0 -S -fno-asynchronous-unwind-tables -o opt_O0.s opt.c
grep -E '^[a-z_0-9]+:|[[:space:]]bl[[:space:]]' opt_O0.s
# The same file at -O2, with directives and comments filtered out
clang --target=aarch64-linux-gnu -O2 -S -fno-asynchronous-unwind-tables -o opt_O2.s opt.c
grep -v -E '^[[:space:]]+[.]|^[.]L|^[[:space:]]*//' opt_O2.s | sed -E 's/[[:space:]]+\\/\\/.*$//'
# sum.c at -O2: the lines of its listing that use vector registers (q0 to q31, v0 to v31)
clang --target=aarch64-linux-gnu -O2 -S -fno-asynchronous-unwind-tables -o sum_O2.s sum.c
grep -E '[[:space:]](q|v)[0-9]+' sum_O2.s
""")

# opt.c at -O0 for AArch64 Linux: the labels and every call (bl) in the listing
$ clang --target=aarch64-linux-gnu -O0 -S -fno-asynchronous-unwind-tables -o opt_O0.s opt.c
$ grep -E '^[a-z_0-9]+:|[[:space:]]bl[[:space:]]' opt_O0.s
sum_squares:                            // @sum_squares
	bl	square
	bl	square
square:                                 // @square
forward:                                // @forward
	bl	scale
dot3:                                   // @dot3
# The same file at -O2, with directives and comments filtered out
$ clang --target=aarch64-linux-gnu -O2 -S -fno-asynchronous-unwind-tables -o opt_O2.s opt.c
$ grep -v -E '^[[:space:]]+[.]|^[.]L|^[[:space:]]*//' opt_O2.s | sed -E 's/[[:space:]]+\/\/.*$//'
sum_squares:
	mul	w8, w0, w0
	madd	w0, w1, w1, w8
	ret
forward:
	add	w0, w0, #1
	b	scale
dot3:
	ldp	w8, w11, [x1]
	ldp	w9, w10, [x0]
	ldr	w12, [x1, #8]
	mul	w8, w8, w9
	ldr	w9, [x0, #8]
	madd	w8, w11, w10, w8
	madd	w0, w12, w9, w8
	ret
# sum.c at -O2: the lines of its listing that use vector registers (q0 to q31, v0 to v31)
$ clang --target=aarch64-linux-gnu -O2 -S -fno-asynchronous-unwind-tables -o sum_O2.s sum.c
$ grep -E '[[:space:]](q|v)[0-9]+' sum_O2.s
	movi	v0.2d, #0000000000000000
	movi	v1.2d, #0000000000000000
	movi	v2.2d, #0000000000000000
	movi	v3.2d, #0000000000000000
	ldp	q4, q5, [x8, #-32]
	ldp	q6, q7, [x8], #64
	add	v0.4s, v4.4s, v0.4s
	add	v1.4s, v5.4s, v1.4s
	add	v2.4s, v6.4s, v2.4s
	add	v3.4s, v7.4s, v3.4s
	add	v0.4s, v1.4s, v0.4s
	add	v0.4s, v2.4s, v0.4s
	add	v0.4s, v3.4s, v0.4s
	addv	s0, v0.4s
	movi	v0.2d, #0000000000000000
	mov	v0.s[0], w8
	ldr	q1, [x8], #16
	add	v0.4s, v1.4s, v0.4s
	addv	s0, v0.4s

Inlininginlining: Replacing a call with a copy of the called function's body, so that the call, the return and the passing of arguments disappear and the copy is optimised together with its caller. copied square into sum_squares: mul w8, w0, w0 squares a and madd w0, w1, w1, w8 squares b and adds, so no call is left, and square, being static, keeps no copy of its own. forward ends in b scale because scale’s result is its result: a tail calltail call: A call that is the last thing a function does, compiled as a plain jump (b, jmp or RISC-V's tail) instead of a call and a return. The caller's return address stays in place, so the callee returns straight to the caller's caller. More in “Calls, returns and the link register”, after which scale returns straight to forward’s caller. dot3’s trip count, 3, is known while compiling, so loop unrollingloop unrolling: Writing a loop's body out several times so that each pass does the work of several iterations. A loop whose trip count is known while compiling can be unrolled completely, leaving no counter and no branch back. wrote the body out three times, with no counter and no branch back.

In sum.c at plain -O2, a loop that adds 32-bit integers loads 128-bit q registers and adds with add v0.4s, v4.4s, v0.4s, four additions in one instruction: auto-vectorisationauto-vectorisation: A compiler rewriting a loop written one element at a time so that each pass uses vector instructions on several elements, when it can prove the result is the same and judges that it pays.. A vectorised loop has a wide main body, a step that adds the lanes of a register together, and loops for the leftover elements. Its x86-64 and RISC-V forms differ in width and in how they finish. Whether a vector loop pays is a compiler’s cost-model decision, and two compilers can decide differently.

Four tools change what a hot loop compiles to. restrict promises the compiler that two pointers never reach the same elements. A loop pragma asks the vectoriser for a width or an interleave count. Intrinsics let C name vector instructions directly. Hand-written assembly replaces the compiler’s code for one function.

Undefined behaviour lets the compiler delete a check

add_would_overflow tests for overflow the way the maths reads: adding a non-negative n can only make the sum smaller than x by wrapping round. But C makes signed overflow undefined behaviourundefined behaviour: What the C standard calls an operation for which it sets no requirements at all, such as dividing by zero; a compiler may assume a correct program never performs one. More in “Division: traps, defined results, remainders”: a program whose x + n does not fit in an int has no defined meaning, so the compiler may assume it never happens. Here is the function at -O2 on three ISAs, then run on Apple silicon at -O0 and -O2:

// overflow.c: an overflow test written the way it reads in maths, for a non-negative n: adding such an n can only
// make the sum smaller than x by wrapping round. But signed overflow is undefined behaviour in C.
int add_would_overflow(int x, int n) {
    return x + n < x;
}

import pathlib
import sys

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

session.run("""
# add_would_overflow at -O2 on three ISAs, directives and comments filtered out
clang --target=x86_64-linux-gnu -O2 -masm=intel -S -fno-asynchronous-unwind-tables -o - overflow.c | grep -v -E '^[[:space:]]+[.]|^[.]L|^[[:space:]]*#' | sed -E 's/[[:space:]]+#.*$//'
clang --target=aarch64-linux-gnu -O2 -S -fno-asynchronous-unwind-tables -o - overflow.c | grep -v -E '^[[:space:]]+[.]|^[.]L|^[[:space:]]*//' | sed -E 's/[[:space:]]+\\/\\/.*$//'
clang --target=riscv64-linux-gnu -march=rv64gc -O2 -S -fno-asynchronous-unwind-tables -o - overflow.c | grep -v -E '^[[:space:]]+[.]|^[.]L|^[[:space:]]*#' | sed -E 's/[[:space:]]+#.*$//'
# Built and run on Apple silicon at -O0, then at -O2
clang -O0 -o overflow0 overflow_main.c overflow.c && ./overflow0; echo "exit=$?"
clang -O2 -o overflow2 overflow_main.c overflow.c && ./overflow2; echo "exit=$?"
""")

# add_would_overflow at -O2 on three ISAs, directives and comments filtered out
$ clang --target=x86_64-linux-gnu -O2 -masm=intel -S -fno-asynchronous-unwind-tables -o - overflow.c | grep -v -E '^[[:space:]]+[.]|^[.]L|^[[:space:]]*#' | sed -E 's/[[:space:]]+#.*$//'
add_would_overflow:
	mov	eax, esi
	shr	eax, 31
	ret
$ clang --target=aarch64-linux-gnu -O2 -S -fno-asynchronous-unwind-tables -o - overflow.c | grep -v -E '^[[:space:]]+[.]|^[.]L|^[[:space:]]*//' | sed -E 's/[[:space:]]+\/\/.*$//'
add_would_overflow:
	lsr	w0, w1, #31
	ret
$ clang --target=riscv64-linux-gnu -march=rv64gc -O2 -S -fno-asynchronous-unwind-tables -o - overflow.c | grep -v -E '^[[:space:]]+[.]|^[.]L|^[[:space:]]*#' | sed -E 's/[[:space:]]+#.*$//'
add_would_overflow:
	srliw	a0, a1, 31
	ret
# Built and run on Apple silicon at -O0, then at -O2
$ clang -O0 -o overflow0 overflow_main.c overflow.c && ./overflow0; echo "exit=$?"
add_would_overflow(INT_MAX - 50, 100) = 1
exit=0
$ clang -O2 -o overflow2 overflow_main.c overflow.c && ./overflow2; echo "exit=$?"
add_would_overflow(INT_MAX - 50, 100) = 0
exit=0

All three listings return the sign bit of n and never read x: shr eax, 31, lsr w0, w1, #31 and srliw a0, a1, 31. With overflow ruled out, x + n < x is ordinary algebra, and subtracting x from both sides leaves n < 0.

For x = INT_MAX - 50 and n = 100 the true sum does not fit. The -O0 build compared a wrapped, negative sum and printed 1; the -O2 build tested only n and printed 0. Neither is a compiler bug: C leaves the answer undefined. That is what undefined behaviour in assembly usually looks like, not a strange instruction but a missing one.

-fwrapv defines signed overflow to wrap. A sanitizer reports the overflow while the program runs. C23’s ckd_add asks the question directly and always gets a defined answer. An over-wide shift, and a test of a pointer made after reading through it, go wrong for the same reason.

Practise

Copy opt.c, overflow.c and sum.c first and change only the copies. To see what a change did, paste the old and the new listing into the text diff tool.

1. Remove static from square and compile opt.c at -O2. Is sum_squares still inlined, and what is new in the listing?
2. Make dot3 loop to a parameter n instead of 3, and predict what replaces the mul and the madds before you compile.
3. Rewrite the test as n > 0 && x > __INT_MAX__ - n, which never overflows. Which instructions now read x, and what do the -O0 and -O2 builds print?
4. Compile sum.c with -fno-vectorize and compare its loop with the plain -O2 one.

Vectorised loops read lane by lane on three ISAs Pro: opens with a Pro, Premium or Ultimate pass

Undefined behaviour that removes checks, reproduced and fixed Pro: opens with a Pro, Premium or Ultimate pass

Restrict, pragmas, intrinsics or assembly: choosing for a hot loop Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

A warm-up for freshers: what does -O2 turn on that -O0 leaves off?

-O0 compiles each statement on its own and keeps every variable in memory, so a debugger can follow the source line by line. -O2 turns on the optimisations that almost always pay: values stay in registers, small functions are inlined, calls in tail position become jumps, constants are folded, and loops are unrolled and vectorised when a cost model says it pays, by Clang and by GCC since version 12. It also uses the language’s rules to the full, assuming no signed overflow and no read through a null pointer, so checks that rely on either can vanish. GCC keeps costlier transformations for -O3.

These three go further: an overflow check that fails only at -O2, proof that a loop was vectorised, and intrinsics against the compiler.

Key takeaways

• An optimised listing is read by what is missing or repeated: a vanished call is inlining, a final call turned into a branch is a tail call, a loop written out is unrolling, and vector registers in a scalar loop are vectorisation.
• Signed overflow is undefined behaviour, so -O2 may compile x + n < x to a test of the sign bit of n.
• A test that relies on undefined behaviour can change its answer with the optimisation level, and the listing shows it as a missing check.