Branching and loops
Changing the program counter to repeat and to choose
Branching and loops let a program repeat and choose by changing the program counter: an unconditional jump (JMP) reloads it with a new address, and a conditional jump (JZ) reloads it only when a flag such as zero is set, turning a straight-line instruction sequence into loops and if-decisions.
Build it in the lab →A straight-line program runs top to bottom exactly once, because the program counter only ever increments. To add ten numbers you would need ten
ADD lines. What the machine is missing is the ability to go somewhere other than the next address, and that is exactly what a jump provides.The jump: loading the program counter
The program counter is a register, and you already gave it a load path: a multiplexer on its input that chooses between
PC + 1 (count) and a new address (jump). JMP a drives that mux to load a instead of incrementing. An unconditional jump always does this, so JMP back to an earlier address makes the machine run those instructions again: a loop.But a loop that always jumps back never stops. To be useful, the machine also needs to jump sometimes. A conditional jump
JZ a (jump if zero) loads the program counter with a only when the zero flag is set, and otherwise falls through to the next instruction. That is an if: the machine takes one path or the other based on a computed condition.A loop that counts down
Put the two together and you get a real loop with an exit. Load a counter, and each time around: do the work, subtract one, and
JZ out when the counter reaches zero, otherwise JMP back to the top. Here is a countdown from five that halts: LOAD n ; ACC = 5 (the counter)
loop: JZ done ; if ACC == 0, jump out of the loop
SUB one ; ACC = ACC - 1
JMP loop ; go back and test again
done: HALT
n: .byte 5
one: .byte 1Trace it:
5, 4, 3, 2, 1, 0. On the pass where the accumulator is 0, JZ sees the zero flag set and jumps to done. Five instructions run many more than five times, because the program counter keeps looping back. This is the moment the little machine stops being a calculator and becomes a computer: with loops and conditional branches it can, given enough memory, compute anything computable.Common mistakes. A loop needs a change that moves it toward its exit condition, forget the
SUB and the counter never reaches zero, so JZ never fires and the program loops forever (an infinite loop). Watch the boundary too: testing for zero before subtracting versus after shifts the count by one (an off-by-one). And a jump's target is an address, not a line number, if you insert an instruction, every later address shifts, which is exactly the bookkeeping labels exist to handle for you.Every control structure you know,
while, for, if, else, function calls, compiles down to jumps. There is no while instruction in the hardware; there is only "load the program counter with this address, maybe conditionally." Loops and decisions are not built into the silicon, they are patterns of jumps, and the whole tower of high-level programming rests on this one ability to change the PC.Try it
In the countdown above, what happens if you delete the
SUB one line? And what if you move JZ done to run AFTER SUB one instead of before it?Answer
Deleting
SUB one gives an infinite loop: the accumulator stays at 5, JZ never fires, and JMP loop runs forever. Moving JZ done to after SUB one changes the count by one: the accumulator is tested at 4, 3, 2, 1, 0, so the work in the loop body runs one fewer time (a classic off-by-one). Where you place the test relative to the update decides exactly how many times the loop runs.Frequently asked
How does a CPU do loops and if-statements?
By changing the program counter with jump instructions. An unconditional jump reloads the PC with an earlier address to repeat instructions (a loop); a conditional jump reloads it only when a flag such as zero is set, choosing one path or another (an if). High-level loops and conditionals all compile down to these jumps.
What is the difference between an unconditional and a conditional jump?
An unconditional jump (JMP) always loads the program counter with its target address. A conditional jump (JZ, and similar) loads the PC only when a condition holds, such as the zero flag being set, and otherwise falls through to the next instruction. Unconditional jumps make loops; conditional jumps make decisions and loop exits.
Why does a computer need conditional branches to be general-purpose?
Without conditional branching a program runs a fixed sequence once and can never react to a computed value, so it cannot loop a variable number of times or choose between paths. Adding a conditional jump (plus enough memory) makes the machine able to compute anything computable, the practical meaning of general-purpose.
You've got the theory. Now build it from scratch and watch it work.
Build it in the lab →Or test yourself: the free placement exam takes 15 minutes →Builds towardWhy multiply is software on small machines