Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 40 ยท Control Flow

Writing Loops

Build loops in assembly with a compare and a backward jump: counting loops, while vs do-while shapes, the LOOP instruction, nested loops, factorial and gcd.

There is no loop instruction family in a CPU that corresponds to for or while. A loop is just a jump backwards: run a block of code, then jump to its start again as long as some condition holds. Once you can write that by hand, every loop a compiler produces becomes readable, and you also understand why some loop shapes are cheaper than others.

This lesson builds on Compare and Jump. We write counting loops in three shapes, look at the special loop instruction, nest loops inside each other, and then solve three classic problems (sum, factorial and greatest common divisor). All programs run on the toy CPU, whose interpreter sits at the bottom of each TryIt.

The anatomy of a loop

Every loop has the same four parts:

  1. Initialise a counter (and any accumulators).
  2. Test whether to continue.
  3. Body: the work for one iteration.
  4. Update the counter, then jump back.

The only question is where the test goes. That choice gives two shapes, the same two you know from while and do { } while.

Test at the top (while). The test runs before the body, so the body can run zero times:

NASM
        mov   rbx, 1          ; i = 1
top:    cmp   rbx, 10
        jg    end             ; leave if i > 10
        ; ... body ...
        inc   rbx
        jmp   top
end:

Test at the bottom (do-while). The body always runs at least once, and each iteration needs only one jump instead of two:

NASM
        mov   rcx, 10
top:    ; ... body ...
        dec   rcx
        jnz   top             ; repeat while rcx != 0

Counting down to zero is a favorite trick. dec already sets ZF, so no separate cmp is needed: the update instruction doubles as the test. That saves an instruction per iteration, which is why hand-written and compiler-written loops so often count backwards.

flowchart TD
  A["init counter"] --> B{"test at top<br/>(while)"}
  B -- "continue" --> C["body"]
  C --> D["update"]
  D --> B
  B -- "stop" --> E["after loop"]

A while loop: the test runs first, so the body may never run. Moving the test to the bottom gives a do-while.

Three ways to sum 1 to 10

Run all three forms below. They compute the same sum, but the number of executed instructions differs, which you can read from steps.

JS While, do-while and loop: same sum, different cost

Press Run (or Ctrl + Enter) to see the console output here.

No output.

For n = 10 all three print 55. The while form needs 54 steps, the do-while 32 and the loop form 22, because every instruction in the loop body costs a step.

For n = 0 something instructive happens. The while loop correctly returns 0 after four steps. The other two enter the body first, so rcx goes from 0 to "minus one", the counter wraps around to its maximum value and the loop would run billions of times; the toy CPU stops after 1,000 steps. A do-while shape is only correct when the loop is guaranteed to run at least once. Compilers that use it for a for loop therefore add a guard: a single test before the loop that skips it when the count is zero.

The loop instruction

x86 has a one-instruction version of "decrement rcx and jump back unless it became zero": loop label. It does not touch the flags. A closely related instruction, jrcxz, jumps when rcx is zero, which you use as the guard.

NASM
        mov   rcx, 10
top:    ; body
        loop  top             ; rcx = rcx - 1; if rcx != 0, jump to top

It looks ideal, yet compilers almost never emit it. On many Intel and AMD processors loop is slower than the pair dec plus jnz, which the CPU can even fuse into one internal operation. Treat loop as a historical convenience that you will meet in old code and tutorials, and prefer dec/jnz (or sub/jnz) in your own work. ARM64 has no loop at all; the usual pattern is subs x0, x0, #1 followed by b.ne top, or cbnz x0, top, which jumps when a register is non-zero without touching flags.

The toy CPU implements loop on rcx only because it is short to explain. Real programs should rely on dec/jnz.

Factorial and wraparound

A loop that multiplies as it counts down computes factorials. The toy registers are 32 bits wide (like eax on a real CPU), so large results wrap around. Here is the same program for 5, 12 and 13.

JS Factorial with imul and dec/jnz

Press Run (or Ctrl + Enter) to see the console output here.

No output.

You see 120 and 479,001,600 (the largest factorial that fits in a signed 32-bit integer). For 13 the true answer is 6,227,020,800, which needs 33 bits, so the printed value is the low 32 bits, 1,932,053,504. Nothing crashes; the CPU just keeps the bits that fit. This silent wrap is exactly what happens to a C int in a long multiplication chain.

Greatest common divisor

Euclid's algorithm, in its subtraction form, is a loop with an exit in the middle and two branches inside. While the numbers differ, subtract the smaller from the larger. When they become equal, that value is the gcd.

JS gcd(48, 18) by repeated subtraction

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Read the trace: 48 and 18 become 30 and 18, then 12 and 18, then 12 and 6, then 6 and 6, and the program prints 6. Try mov rax, 17 and mov rbx, 5 to see a gcd of 1. Division-based versions are faster, but they need div, which comes in Arithmetic: ADD, SUB, MUL, DIV.

Nested loops

A loop inside a loop simply needs two counters and two labels. The inner loop runs completely for every step of the outer loop. This program adds up i * j for i from 1 to N and j from 1 to M, and prints how many steps that costs.

JS Nested loops: the cost multiplies

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The totals are 60 and 381,300, and the work grows from 86 to 7,322 steps. The body executes N times M times, so doubling both counts quadruples the cost; this is the root of "O(n squared)". Remember that the inner counter must be re-initialised inside the outer loop, otherwise the inner loop only runs once.

What a compiler really emits

Compilers like the test-at-the-bottom layout. Here is the typical shape of an unoptimised (-O0) C loop for (i = 0; i < 10; i++), read-only:

NASM
        mov   DWORD PTR [rbp-4], 0     ; i = 0
        jmp   .Lcond                   ; jump straight to the test
.Lbody:
        ; ... loop body ...
        add   DWORD PTR [rbp-4], 1     ; i++
.Lcond:
        cmp   DWORD PTR [rbp-4], 9
        jle   .Lbody                   ; i <= 9 ? repeat

It enters the loop by jumping to the condition, which keeps a single conditional jump per iteration. With optimisation turned on, the counter lives in a register and the code often becomes a guard plus a do-while. You will practise reading such output in Reading Real Assembly from a C Compiler.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which loop shape guarantees that the body runs at least once?

    With the test at the bottom, the body executes before the first test. A while loop tests first and can skip the body entirely.
  2. 2. Why do many hand-written loops count down to zero with dec and jnz?

    The update instruction doubles as the test: when dec produces zero, ZF is 1 and jnz falls through. That removes one instruction per iteration.
  3. 3. What happens in the toy CPU when a do-while loop built with mov rcx, 0 ... loop top starts?

    The body runs once, then loop decrements rcx from 0 to 0xFFFFFFFF in the toy (all ones), which is not zero, so it keeps jumping back. A guard test before the loop avoids this.
  4. 4. A nested loop has N outer and M inner iterations. How many times does the inner body run in total?

    The inner loop runs completely, M times, for each of the N outer iterations. That gives N times M body executions.

Summary

  • A loop is a backward jump guarded by a condition: initialise, test, body, update.
  • Test at the top gives a while loop that may run zero times; test at the bottom gives a do-while that runs at least once and needs only one jump per iteration.
  • Counting down to zero lets dec followed by jnz serve as update and test together.
  • The loop instruction decrements rcx and jumps, but it is usually slower than dec/jnz and compilers avoid it; ARM64 uses subs/b.ne or cbnz.
  • Results wrap around silently at the register width, as the 13 factorial run showed.
  • Nested loops multiply their costs, and the inner counter must be reset on every outer iteration.

Next: see how compilers turn if, switch and the ternary operator into jumps in How if, switch and Ternaries Compile.