Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 67 ยท Instruction Set Architecture

Assembly: Branches, Loops and Functions

See how compare-and-jump builds if statements and loops, how call and return use the stack, and what a calling convention is, all run in a small simulator.

A processor runs instructions in order until something changes the program counter. That one idea, "set the PC to somewhere else", is the whole machinery behind if, while, for, and function calls. High-level languages hide it, but every if you have ever written became a compare and a jump.

In this lesson you will write assembly for decisions, loops and recursive functions, run it in a small Python simulator of a teaching machine, and see exactly how the stack holds return addresses and saved values. At the end you will meet real x86-64 and ARM64 listings, which use the same ideas with different spelling. It builds on Assembly Language Basics and the fetch-decode-execute cycle.

The teaching machine

The simulator below runs a small register machine. It has eight registers: r0 to r6 and sp, the stack pointer, which starts at the top of a 64-word memory and moves down as the stack grows. The instructions you need today are these.

Instruction Meaning
LI rd, n rd = n
MOV rd, rs rd = rs
ADD rd, rs, rt / SUB / MUL arithmetic on registers
ADDI rd, rs, n rd = rs + n
CMP ra, rb / CMPI ra, n compare, set the flags, keep nothing else
JMP L always jump to label L
BEQ BNE BLT BGE BGT BLE L jump to L if the last compare satisfied the condition
PUSH r / POP r save or restore a register on the stack
CALL L / RET call a function, return from it
OUT r print a register
HALT stop

Lines ending in : are labels, names for instruction positions. The assembler turns each label into an address, so you can jump by name.

Decisions: compare, then branch

Hardware has no "if". It has two separate steps:

  1. Compare. CMP a, b subtracts b from a, throws the number away, and remembers two facts in flag bits: Z (the result was zero) and N (the result was negative).
  2. Branch. A conditional jump looks at the flags. BEQ jumps when Z is set, BNE when it is clear, BLT when N is set, and so on.

Real processors keep a few more flags (carry, overflow), which matter for unsigned numbers and overflow, as in Binary Arithmetic and Overflow. Our machine keeps only Z and N, which is enough for signed comparisons of small numbers.

Here is if (a > b) m = a; else m = b; in assembly:

TEXT
    CMP  r1, r2        ; flags = r1 - r2
    BGT  a_is_bigger   ; taken if r1 > r2
    MOV  r0, r2        ; else part
    JMP  done
a_is_bigger:
    MOV  r0, r1        ; then part
done:

Notice the shape: the else path must jump over the then code, otherwise execution would fall through into it. An if with two branches always costs one conditional jump and one unconditional jump.

flowchart TD
  C["CMP r1, r2"] --> B{"BGT taken?"}
  B -- "yes" --> T["then: MOV r0, r1"]
  B -- "no" --> E["else: MOV r0, r2"]
  E --> J["JMP done"]
  T --> D["done"]
  J --> D

An if/else is a compare, a conditional jump, and a jump that skips the other branch.

Loops are jumps backward

A loop is a conditional jump whose target is earlier in the program. The pattern for while (i <= n) is: test at the top, exit if false, run the body, jump back to the test.

The first TryIt defines the whole simulator, then runs two programs: a "larger of two" decision and a loop that sums 1 to 10. Read the labels and compare them with the C-like comments.

Python Branches and a loop

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

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the instruction counts. The decision costs 5 or 6 instructions depending on the path taken. The loop runs 10 iterations of a 5-instruction body, plus 2 for setup and 4 for the final test, exit branch, OUT and HALT, which gives the 56 you see. The JMP test at the bottom of the loop is pure overhead: it exists only to get back to the test.

Loop shapes and their cost

Compilers often rewrite the loop so the test sits at the bottom. The body then ends with one conditional branch that jumps backward, and the unconditional JMP disappears:

TEXT
    LI   r0, 0
    LI   r1, 1
body:
    ADD  r0, r0, r1
    ADDI r1, r1, 1
    CMPI r1, 10
    BLE  body          ; one jump per iteration, not two

This saves one instruction every iteration. It is only safe when the loop runs at least once, so compilers add a single guard test before the loop when they cannot prove that. Counting down toward zero is another classic trick on machines whose arithmetic instructions already set the flags: no separate compare is needed. Since CPI and instruction count both set execution time, trimming instructions from the hottest loop is one of the cheapest speedups there is.

Functions: CALL, RET and the stack

A function call needs two things the plain jump cannot do: remember where to come back to, and let the same code be called from many places. The answer is the return address and the stack.

  • CALL f pushes the address of the next instruction onto the stack, then jumps to f.
  • RET pops that address into the PC.

The stack lives in ordinary memory. The stack pointer sp holds the address of the top entry. On our machine (like most) the stack grows toward lower addresses: a push first lowers sp, then writes at sp.

flowchart LR
  subgraph S["Stack after the call to fact"]
    direction TB
    A["higher addresses"]
    R["return address into main"]
    V["saved r1 (argument)"]
    T["sp points here"]
  end
  A --> R --> V --> T

Each call stacks a return address and any saved registers, growing downward in memory.

Because every call pushes its own return address, recursion works with no extra tricks: a function can call itself, and each activation has its own entry on the stack.

A calling convention

If any function could use any register in any way, callers could never trust their own values after a call. A calling convention is the agreement that prevents this. Ours is simple, and real ones (System V on Linux, AAPCS on ARM) follow the same pattern with more registers:

  • The first argument goes in r1, and the return value comes back in r0.
  • r0 to r3 are caller-saved: a function may overwrite them, so a caller that needs them must save them first.
  • r4 to r6 are callee-saved: a function that wants to use one must restore it before returning, usually with a PUSH at the start and a POP at the end.

The second TryIt computes fact(5) recursively. To see the stack, the simulator remembers the lowest value sp reached, and after the run prints the memory cells from there up to the top, which still hold what the deepest calls wrote.

Python Recursive factorial and its stack

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

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The program prints fact(5) = 120 after 40 instructions. The stack reaches a depth of 9 words: the return address into main (the value 2 at address 63), then two words for each of the four levels that recurse, the saved n from PUSH (5, 4, 3, 2) and the return address from CALL (11, the instruction after the recursive call inside fact). The base case, fact(1), pushes only its return address, at address 55.

A group of stack entries belonging to one call (saved registers, local variables, the return address) is a stack frame. Real compilers allocate frames by subtracting from sp once at function entry and use a frame pointer register to address locals with fixed offsets. Our PUSH/POP style is the simplest version of the same thing.

When the convention is broken

A calling convention only works if both sides keep their promises. The third TryIt shows two functions that double r1 into r0. The bad one uses callee-saved r4 as scratch space and never restores it. The caller, trusting the convention, kept a running total in r4 and gets a wrong answer. The good one saves and restores r4. It then ends with a runaway recursion to show what stack overflow looks like when the stack collides with the bottom of memory.

Python Callee-saved registers and stack overflow

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

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The bad version prints 42 because the caller's 100 was overwritten, and the good version prints 142. Bugs of this kind are painful in real code because the broken function works fine in isolation. Compilers and assemblers cannot check the convention for you; it is a contract. The last example ends in a stack overflow once the 64-word stack is full, because each call pushes a return address and none ever returns.

Real listings: x86-64 and ARM64

The same C function in two real instruction sets shows how little the ideas change. Both listings below are read-only illustrations of what a compiler might produce for int sum(int n) that adds 1 through n; exact output varies with compiler and options.

C
int sum(int n) {
    int s = 0;
    for (int i = 1; i <= n; i++) s += i;
    return s;
}

x86-64, Intel syntax, System V calling convention (first argument in edi, result in eax):

TEXT
sum:
    xor   eax, eax        ; s = 0
    mov   ecx, 1          ; i = 1
.loop:
    cmp   ecx, edi        ; flags = i - n
    jg    .done           ; leave when i > n
    add   eax, ecx        ; s += i
    inc   ecx             ; i++
    jmp   .loop
.done:
    ret

ARM64 (AArch64), where the first argument arrives in w0 and the result goes back in w0:

TEXT
sum:
    mov   w1, #0          // s = 0
    mov   w2, #1          // i = 1
.loop:
    cmp   w2, w0          // flags = i - n
    b.gt  .done           // leave when i > n
    add   w1, w1, w2      // s += i
    add   w2, w2, #1      // i++
    b     .loop
.done:
    mov   w0, w1          // result in w0
    ret

Compare them with our total program. All three have flags, a compare, a conditional jump out, and an unconditional jump back. The differences are in the details:

  • Call mechanics. x86 call pushes the return address on the stack, like our CALL. ARM64's bl instead puts it in a link register (x30), so a leaf function can return with no memory traffic, and only functions that call others need to save it.
  • Register count. x86-64 has 16 general registers, ARM64 has 31, and more arguments travel in registers (six on System V x86-64, eight on ARM64) before spilling to the stack.
  • Spelling. Operand order, comment characters and register names differ, but the operations are the same.

When you read compiler output on a site such as Compiler Explorer, look for the compare, the conditional jump and the labels first. Once you find the loop's backward jump, the rest of the function is easy to place.

Optimizing compilers go further: at -O2 the loop above is typically replaced by a closed-form formula with no loop at all. That is a good reminder that assembly describes what the machine does, not what your source looked like.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a CMP instruction do on our teaching machine?

    CMP computes a - b only to set the Z and N flags. A later conditional branch reads those flags.
  2. 2. Why does an if/else usually need an unconditional JMP after the 'else' code?

    Instructions run in order, so without the JMP the else path would continue straight into the then path.
  3. 3. What does RET do?

    CALL pushes the return address and RET pops it, so the callee goes back to just after the call.
  4. 4. A function uses a callee-saved register as scratch space. What must it do?

    Callee-saved means the callee promises to hand the register back unchanged, typically with a PUSH at the start and a POP at the end.
  5. 5. What usually causes a stack overflow?

    Each call consumes stack space. Unbounded recursion eventually runs the stack pointer past the memory reserved for the stack.

Summary

  • Control flow is the program counter being overwritten: a CMP sets flags, a conditional branch reads them, and JMP always jumps.
  • An if/else needs a conditional jump plus a jump over the other branch; a loop is a conditional jump to an earlier label.
  • Putting the loop test at the bottom saves one jump per iteration.
  • CALL pushes the return address and jumps; RET pops it. This is why recursion works.
  • A calling convention fixes where arguments and results live and which registers survive a call. Breaking it causes bugs that are hard to see.
  • x86-64 and ARM64 use the same building blocks; ARM64's bl keeps the return address in a link register instead of on the stack.

Next, move inside the processor with The CPU Datapath.