Loops: while, for and counting down

strlen("hello") is a loop of four instructions that runs five times: load a byte, test it for zero, count it, jump back. On the sixth pass the byte is the terminator, the test is taken and the loop ends with 5. Whether the source says while, for or do-while, the machine code has the same parts: a label to come back to, a conditional branch that decides when to stop and a jump that closes the circle.

Each loop here comes in its x86-64, AArch64 and RISC-V form. Along the way you count down so that the decrement sets the flag the branch needs, write the loop’s invariant before its body to avoid off-by-one errors, and read the shape a compiler gives a loop at -O2.

A while loop is a test, a body and a jump back

A while loop tests before every pass, do-while tests after, and for is a while with a start value and a step folded in. In assembly the simplest form keeps the test at the top: load or compute what the condition needs, branch out of the loop if it fails, run the body, then jump back to the top. strlen in that shape, with the null terminatornull terminator: A single byte of value 0 appended to a string to mark its end. The C library's strlen, puts and printf all walk forward until they meet one; a length-prefixed call like write(2) uses a separate length instead. More in “Endianness, strings and text in memory” as the stopping condition:

// strlen_aarch64.s — count bytes before the NUL terminator (AArch64 Mac)
// Loop invariant: every byte in [str, str+len) is non-zero.
// Post-condition: byte at str+len is zero; len is the string length.

.global _my_strlen
.align 4

// _my_strlen: count bytes until the NUL terminator
// Input:  x0 = pointer to a NUL-terminated string
// Output: x0 = length (bytes before the terminator)
_my_strlen:
    mov     x1, #0              // len = 0
.Lloop:
    ldrb    w2, [x0, x1]        // load byte at str[len]
    cbz     w2, .Ldone          // if byte == 0, done
    add     x1, x1, #1          // len += 1
    b       .Lloop              // repeat
.Ldone:
    mov     x0, x1              // return len
    ret

The C equivalent is while (str[len] != 0) len++;. ldrb w2, [x0, x1] loads the byte at str + len, cbz leaves the loop when it is zero, add counts it, and b .Lloop goes back to the load. .Lloop has no .global, so it is local to its file: no other object file can refer to it. On ELF targets such as Linux the .L prefix also keeps it out of the symbol tablesymbol table: The list of labels an object file defines or references, with each label's name, the section it belongs to and the offset within that section. The linker reads it to match references between objects. More in “From source to executable: objects and linking”; Mach-O uses a plain L for that, so the macOS build still lists .Lloop as a non-external symbol. Step through the call on "hello":

The driver calls it on "hello" and on the empty string:

// strlen_driver.c — call my_strlen and print the results
#include <stdio.h>
extern long my_strlen(const char *s);

int main(void) {
    printf("%ld\n", my_strlen("hello"));
    printf("%ld\n", my_strlen(""));
    return 0;
}

import pathlib
import sys

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

# Assemble strlen_aarch64.s, link with C driver, run it.
# The driver calls my_strlen twice and prints "5" and "0".
session.run(r"""
clang -o strlen_prog strlen_aarch64.s strlen_driver.c
./strlen_prog
""")

$ clang -o strlen_prog strlen_aarch64.s strlen_driver.c
$ ./strlen_prog
5
0

It printed 5 and 0. The empty string never enters the body: the first cbz is taken at once. Each pass through the body, though, runs two branches, the cbz that falls through and the b that is always taken; the last section of this lesson shows how a compiler gets rid of one of them.

Count down to zero, and let the subtraction set the flag

A loop that counts up from 0 to n needs a compare before its branch: nothing about i + 1 says whether i has reached n. Counting down from n to zero removes the compare, because the decrement itself can report the zero. That is the count-down idiomcount-down idiom: A loop pattern that counts from n down to zero instead of from 0 up to n. The decrement sets the zero flag directly (subs on AArch64, dec on x86), saving a separate compare instruction..

AArch64’s subs subtracts and sets the condition flagscondition flags: Single bits that an instruction sets to describe its result: zero, negative, carry and signed overflow. x86-64 keeps them in RFLAGS as ZF, SF, CF and OF, AArch64 in NZCV; RISC-V has none. More in “Flags and condition codes”; plain sub sets none. On x86-64, dec and sub both set the zero flag, so dec ecx and jnz close a loop. RISC-V has no flags: addi a0, a0, -1 and then bnez a0 branch on the register itself. x86-64 also has a loop instruction that decrements rcx and branches while it is not zero, but its offset is 8 bits, so its target must be within 128 bytes. sum_1_to_n adds n, n − 1 and so on down to 1:

// sum_1_to_n_aarch64.s — sum from 1 to n using a count-down loop (AArch64 Mac)
// Loop invariant: acc holds sum of all integers from (counter+1) to n.
// Post-condition: counter == 0, acc == n*(n+1)/2.

.global _sum_1_to_n
.align 4

// _sum_1_to_n: compute 1 + 2 + ... + n
// Input:  x0 = n (unsigned 64-bit)
// Output: x0 = sum (unsigned 64-bit)
// Uses count-down with subs to set the zero flag in one instruction.
_sum_1_to_n:
    mov     x1, #0              // acc = 0
    cbz     x0, .Lsum_done      // if n == 0, skip loop
.Lsum_loop:
    add     x1, x1, x0          // acc += counter
    subs    x0, x0, #1          // counter -= 1 and set flags
    b.ne    .Lsum_loop          // repeat if counter != 0
.Lsum_done:
    mov     x0, x1              // return acc
    ret

The loop is three instructions: add accumulates, subs decrements and sets the flags, b.ne repeats while the counter is not zero. The cbz x0, .Lsum_done above it handles n = 0, which must not run the body at all: with n = 0, subs would wrap the counter to the largest 64-bit value and the loop would run about 1.8 × 10¹⁹ times. Step through n = 3:

// sum_driver.c — call sum_1_to_n and compare to formula
#include <stdio.h>
extern unsigned long sum_1_to_n(unsigned long n);

int main(void) {
    unsigned long tests[] = {0, 1, 100000};
    for (int i = 0; i < 3; i++) {
        unsigned long n = tests[i];
        unsigned long computed = sum_1_to_n(n);
        unsigned long expected = n * (n + 1) / 2;
        printf("n=%lu: sum=%lu, expected=%lu\n", n, computed, expected);
    }
    return 0;
}

import pathlib
import sys

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

# Assemble sum_1_to_n_aarch64.s, link with C driver, run it.
# The driver tests n=0, n=1, n=100000 and compares to formula.
session.run(r"""
clang -o sum_prog sum_1_to_n_aarch64.s sum_driver.c
./sum_prog
""")

$ clang -o sum_prog sum_1_to_n_aarch64.s sum_driver.c
$ ./sum_prog
n=0: sum=0, expected=0
n=1: sum=1, expected=1
n=100000: sum=5000050000, expected=5000050000

All three rows match the formula, including 5,000,050,000 for n = 100000, a sum too large for 32 bits.

The loop invariant you write before you code

A loop invariantloop invariant: A statement about a loop's variables that is true at the start of every iteration. Writing it down first helps avoid off-by-one errors by making the meaning of each variable explicit. is a claim about the loop’s variables that holds whenever control reaches the loop test. Writing it down before the body forces two decisions: what each variable means at the top of a pass, and what is true when the loop ends. Most off-by-one errors are a loop whose author never made them.

For strlen the invariant is: every byte in str[0] to str[len - 1] is non-zero, the half-open range [0, len). At the start len is 0 and the range is empty, so it holds. The next byte not yet covered is str[len], so that is the byte the body must load. If it is non-zero, len + 1 keeps the invariant true; if it is zero, the loop stops, and the invariant plus the zero byte say exactly that len is the length. The same reasoning fixes the count-down loop: at the top of each pass, acc holds the sum of every number above the counter, up to n.

The table follows the invariant through the six tests of strlen("hello"), the call the strlen session ran:

Loop rotation moves the test to the bottom

The strlen loop runs two branches per pass. A compiler removes one with loop rotationloop rotation: A compiler transformation that moves the loop test from the top to the bottom, with a one-time entry test that skips the loop if it should not run. This saves one branch per iteration when the loop runs at least once.: it turns the loop into a do-while, with the test after the body, so the jump back and the test become one conditional branch. LLVM’s documentation notes the catch: a do-while runs its body at least once, so unless the compiler can prove that n is at least 1 it adds a guard in front that skips the loop. loop_rotation.c sums an array, and clang compiled it at -O2:

// loop_rotation.c — a sum loop to show loop rotation
// This version takes a pointer to prevent the closed-form optimization.
long sum_array(long *arr, long n) {
    long acc = 0;
    for (long i = 0; i < n; i++) {
        acc += arr[i];
    }
    return acc;
}

"""Compiles loop_rotation.c at -O2 and prints the function clang wrote, to see where the loop test went."""

import pathlib
import sys

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

session.run(r"""
# -fno-vectorize keeps one element per iteration, as in the C source, so the loop stays easy to read
clang -O2 -fno-vectorize -S -o loop_rotation.s loop_rotation.c
# Print the function only, from its label to the end of its code
sed -n '/^_sum_array:/,/cfi_endproc/p' loop_rotation.s
""")

# -fno-vectorize keeps one element per iteration, as in the C source, so the loop stays easy to read
$ clang -O2 -fno-vectorize -S -o loop_rotation.s loop_rotation.c
# Print the function only, from its label to the end of its code
$ sed -n '/^_sum_array:/,/cfi_endproc/p' loop_rotation.s
_sum_array:                             ; @sum_array
	.cfi_startproc
; %bb.0:
	cmp	x1, #1
	b.lt	LBB0_4
; %bb.1:
	mov	x8, #0                          ; =0x0
LBB0_2:                                 ; =>This Inner Loop Header: Depth=1
	ldr	x9, [x0], #8
	add	x8, x9, x8
	subs	x1, x1, #1
	b.ne	LBB0_2
; %bb.3:
	mov	x0, x8
	ret
LBB0_4:
	mov	x8, #0                          ; =0x0
	mov	x0, x8
	ret
	.cfi_endproc

The guard is cmp x1, #1 and b.lt LBB0_4, which returns 0 for an empty array. Past it, the loop starting at LBB0_2 has the body first, ldr x9, [x0], #8 and add x8, x9, x8, and the test last: subs x1, x1, #1 and b.ne LBB0_2. clang also turned the count up of the C source into a count down of x1, the idiom of the previous section. Step through it for two elements, then for none:

For an array of 1,000 elements the top-tested shape runs 2,000 branches in the loop plus the final exit test; the rotated one runs 1,000 and the guard once.

The same byte loop on x86-64 and RISC-V

strlen on the other two ISAs has the same four parts. x86-64 can compare a byte in memory with zero in one instruction; RISC-V, a load-store ISA, loads it first and needs an add to form the address. The x86-64 file is in AT&T syntax, where the source operand comes first:

# strlen_x86_64.s: count bytes before the NUL terminator (x86-64 Linux, GNU as syntax).
# Loop invariant: every byte in [rdi, rdi+rcx) is non-zero.
# Post-condition: byte at rdi+rcx is zero; rcx is the string length.
        .text
        .globl  strlen
strlen:
        xorl    %ecx, %ecx          # len = 0
.Lloop:
        cmpb    $0, (%rdi, %rcx)    # compare byte at str[len] with 0
        je      .Ldone              # if zero, done
        incq    %rcx                # len += 1
        jmp     .Lloop              # repeat
.Ldone:
        movq    %rcx, %rax          # return len in rax
        ret

# strlen_riscv64.s: count bytes before the NUL terminator (RISC-V 64, GNU as syntax).
# Loop invariant: every byte in [a0, a0+a1) is non-zero.
# Post-condition: byte at a0+a1 is zero; a1 is the string length.
        .text
        .globl  strlen
strlen:
        li      a1, 0               # len = 0
.Lloop:
        add     a2, a0, a1          # compute address str + len
        lbu     a3, 0(a2)           # load byte at str[len]
        beqz    a3, .Ldone          # if zero, done
        addi    a1, a1, 1           # len += 1
        j       .Lloop              # repeat
.Ldone:
        mv      a0, a1              # return len in a0
        ret

import pathlib
import sys

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

# Assemble strlen for x86-64 Linux and RISC-V Linux with LLVM, then list the machine code of each object:
# the instruction encodings of the same byte loop on two more ISAs.
session.run(r"""
# x86-64: LLVM clang cross-assembles to ELF object
/opt/homebrew/opt/llvm/bin/clang -target x86_64-linux-gnu -c -o strlen_x86_64.o strlen_x86_64.s
/opt/homebrew/opt/llvm/bin/llvm-objdump -d --no-leading-addr strlen_x86_64.o
""")

session.run(r"""
# RISC-V 64: LLVM clang cross-assembles to ELF object
/opt/homebrew/opt/llvm/bin/clang -target riscv64-linux-gnu -c -o strlen_riscv64.o strlen_riscv64.s
/opt/homebrew/opt/llvm/bin/llvm-objdump -d --no-leading-addr strlen_riscv64.o
""")

# x86-64: LLVM clang cross-assembles to ELF object
$ /opt/homebrew/opt/llvm/bin/clang -target x86_64-linux-gnu -c -o strlen_x86_64.o strlen_x86_64.s
$ /opt/homebrew/opt/llvm/bin/llvm-objdump -d --no-leading-addr strlen_x86_64.o

strlen_x86_64.o:	file format elf64-x86-64

Disassembly of section .text:

<strlen>:
 31 c9                                 	xorl	%ecx, %ecx
 80 3c 0f 00                           	cmpb	$0x0, (%rdi,%rcx)
 74 05                                 	je	0xd <strlen+0xd>
 48 ff c1                              	incq	%rcx
 eb f5                                 	jmp	0x2 <strlen+0x2>
 48 89 c8                              	movq	%rcx, %rax
 c3                                    	retq
# RISC-V 64: LLVM clang cross-assembles to ELF object
$ /opt/homebrew/opt/llvm/bin/clang -target riscv64-linux-gnu -c -o strlen_riscv64.o strlen_riscv64.s
$ /opt/homebrew/opt/llvm/bin/llvm-objdump -d --no-leading-addr strlen_riscv64.o

strlen_riscv64.o:	file format elf64-littleriscv

Disassembly of section .text:

<strlen>:
 4581                  	li	a1, 0x0

<.Lloop>:
 00b50633              	add	a2, a0, a1
 00064683              	lbu	a3, 0x0(a2)
 c281                  	beqz	a3, 0xa <.Lloop+0x8>
 0585                  	addi	a1, a1, 0x1
 a001                  	j	0xe <.Lloop+0xc>

<.Ldone>:
 852e                  	mv	a0, a1
 8082                  	ret

On x86-64 the loop is cmpb $0x0, (%rdi,%rcx), je, incq and jmp: compare, leave if zero, count, jump back. On RISC-V it is add, lbu, beqz, addi and j. LLVM’s assembler chose 2-byte compressed encodings for most of them, such as c281 for the beqz, because the target it assembled for includes the C extension; the add and the lbu kept their 4-byte forms. The structure is the same on all three; only the instructions that do each part differ.

Practise

1. Copy strlen_aarch64.s and rotate it by hand: test once before the loop, put the body first, and end the loop with a cbnz back to the load. Run it on "hello" and "" with the commands of the strlen session and check that it still prints 5 and 0.
2. Copy sum_1_to_n_aarch64.s and delete the cbz x0, .Lsum_done line. Predict what the program does for n = 0 before you run it. If it has not finished after a few seconds, stop it with Ctrl+C and explain from subs why.

Interview questions

What is a loop invariant, and how does writing it down before you code change the first line of the loop body?

It is a claim that holds whenever control reaches the loop test, and it pins down what each variable means. For strlen, “every byte of [0, len) is non-zero” says that len counts checked bytes, so the first line of the body must load str[len], the first byte outside the range. Counting first, or loading str[len - 1], breaks the statement on the very first pass, which is why the off-by-one never gets written. When the loop stops, the invariant and the failed test together give the result: the bytes before len are non-zero and str[len] is zero.

Two harder questions on loops follow, one about a hot loop that lost its vector code and one about a count-down loop that broke on an empty buffer:

Key takeaways

• Every loop compiles to a label, a test, a body and a branch back, whichever of while, do-while or for the source used.
• Counting down lets the decrement set the zero flag, so subs and b.ne on AArch64 or dec and jnz on x86-64 close the loop without a compare, while RISC-V branches on the counter register with bnez.
• A count-down loop needs a guard for n = 0, because a decrement from 0 wraps around instead of stopping.
• Writing the loop invariant first decides what the counter means and which element the body touches first, which removes most off-by-one errors.
• At -O2 the compiler rotates a loop so that the test is at the bottom and each pass runs one branch, with a guard in front for the case of no passes at all.