03. MIPS Control

MIPS Control#

Control Flow#

So far, our programs execute linearly: one instruction after another. That is insufficient for if, while, or for, all of which need to choose the next instruction based on a condition.

MIPS implements this using branches, jumps, and labels. A conditional branch says: if this comparison is true, continue execution at the given label.

	bge	$t0, $t1, out_of_range	# if (x >= limit) goto out_of_range;

An unconditional branch always jumps:

	b	loop__cond		# goto loop__cond;

Simplified C#

Directly translating structured C can feel like a leap. The course's most useful technique is to first rewrite the program into simplified C, where each statement has an obvious assembly counterpart.

flowchart TD
    C["Normal C"] --> S["Simplified C<br/>labels + goto"]
    S --> M["MIPS<br/>labels + branches"]

This is not a recommendation to use goto in ordinary C. It exposes the control flow already hidden inside loops and conditionals.

1. Split complex expressions into temporary values.
2. Rewrite structured control flow using labels and goto.
3. Test the simplified C if practical.
4. Allocate registers for every live value.
5. Translate one line at a time.

Branch Instructions#

Many friendly comparison branches are pseudo-instructions. Signed and unsigned comparisons are not interchangeable, so consult the course instruction reference when the bit patterns represent unsigned values.

Translating an if#

Suppose we begin with:

if (n % 2 == 0) {
	print_even();
}

To skip the body when the condition is false, simplified C uses the opposite comparison:

int remainder = n % 2;
if (remainder != 0) goto if_even__end;
print_even();
if_even__end:

If n is in $t0:

	rem	$t1, $t0, 2		# int remainder = n % 2;
	bne	$t1, 0, if_even__end	# if (remainder != 0) goto if_even__end;

	# print the even message

if_even__end:

The common trap is branching on the original condition. Ask: what condition means the body should be skipped?

Translating if / else#

if (temperature < 18) {
	state = COLD;
} else {
	state = WARM;
}

becomes:

if (temperature >= 18) goto if_cold__else;
state = COLD;
goto if_cold__end;
if_cold__else:
state = WARM;
if_cold__end:

and then:

	bge	$t0, 18, if_cold__else
	li	$t1, COLD
	b	if_cold__end

if_cold__else:
	li	$t1, WARM

if_cold__end:

The first branch skips the true body. The unconditional branch after that body prevents execution from falling through into the else body.

else if#

An else if chain is a sequence of tests whose successful bodies jump to one shared end:

	blt	$t0, 85, grade__check_b
	li	$t1, 'A'
	b	grade__end

grade__check_b:
	blt	$t0, 75, grade__check_c
	li	$t1, 'B'
	b	grade__end

grade__check_c:
	blt	$t0, 65, grade__else
	li	$t1, 'C'
	b	grade__end

grade__else:
	li	$t1, 'F'

grade__end:

Here the letters are simply four example bands: A, B, C, and F. Test order matters. A mark of 90 also satisfies >= 75, so the highest threshold must be checked first.

Boolean Expressions#

C uses short-circuit evaluation. In A && B, B is evaluated only if A is true. In A || B, B is evaluated only if A is false. This can affect correctness when the second expression performs work or would be unsafe to evaluate.

Logical AND#

if (x >= 0 && x <= 100) {
	in_bounds();
} else {
	out_of_bounds();
}

Every part of an && must succeed, so any failure can jump directly to the false path:

	blt	$t0, 0, bounds__else
	bgt	$t0, 100, bounds__else

	# in bounds
	b	bounds__end

bounds__else:
	# out of bounds

bounds__end:

Logical OR#

if (age >= 30 || level < 10) {
	replace_milk();
} else {
	keep_milk();
}

Any successful part of an || can jump directly to the true path:

	bge	$t0, 30, milk__replace
	blt	$t1, 10, milk__replace

	# keep milk
	b	milk__end

milk__replace:
	# replace milk

milk__end:

Nested Expressions#

For y < 10 || (z > 50 && w < 5), reason in paths:

	blt	$t0, 10, condition__true
	ble	$t1, 50, condition__end
	bge	$t2, 5, condition__end

condition__true:
	# condition met

condition__end:

If y < 10, the entire expression is already true. Otherwise, both right-hand comparisons must pass.

Loops#

A loop contains four conceptual regions:

flowchart TD
    I["initialisation"] --> C{"another iteration?"}
    C -->|yes| B["body"]
    B --> S["step"]
    S --> C
    C -->|no| E["end"]

Use consistent labels:

loop_name__init
loop_name__cond
loop_name__body
loop_name__step
loop_name__end

Translating a while Loop#

int i = 0;
while (i < 10) {
	print_int(i);
	i++;
}

Simplified C:

int i;
loop_i__init:
i = 0;
loop_i__cond:
if (i >= 10) goto loop_i__end;
loop_i__body:
print_int(i);
loop_i__step:
i++;
goto loop_i__cond;
loop_i__end:

MIPS:

loop_i__init:
	li	$t0, 0			# int i = 0;
loop_i__cond:
	bge	$t0, 10, loop_i__end
loop_i__body:
	li	$v0, 1
	move	$a0, $t0
	syscall				# print_int(i);
loop_i__step:
	addi	$t0, $t0, 1		# i++;
	b	loop_i__cond
loop_i__end:

Translating a for Loop#

First rewrite the for as a while, then use the same regions:

int sum = 0;
for (int i = 1; i <= 100; i++) {
	sum += i * i;
}

	li	$t0, 0			# int sum = 0;
loop_i__init:
	li	$t1, 1			# int i = 1;
loop_i__cond:
	bgt	$t1, 100, loop_i__end
loop_i__body:
	mul	$t2, $t1, $t1		# int square = i * i;
	add	$t0, $t0, $t2		# sum += square;
loop_i__step:
	addi	$t1, $t1, 1		# i++;
	b	loop_i__cond
loop_i__end:

break and continue#

break exits the current loop, so it becomes a branch to loop__end.

continue begins the next iteration. In a translated for loop, it must branch to loop__step, not directly to loop__cond, or the update is skipped.

	rem	$t1, $t0, 2
	bne	$t1, 0, loop_i__step	# continue when i is odd

Nested Loops#

Give every loop a distinct prefix:

loop_row__cond:
	# ...
loop_col__cond:
	# ...
loop_col__end:
	# ...
loop_row__end:

When these loops access a two-dimensional array, the control-flow structure remains unchanged; only the element-address calculation differs. See MIPS Data and Memory.

Common Mistakes#

• Branching on the original if condition when the intended branch should skip a false body.
• Forgetting the branch that skips an else body.
• Reversing operands in a comparison.
• Forgetting to return from the loop body to __cond.
• Omitting the loop step and creating an accidental infinite loop.
• Sending continue to __cond in a for-shaped loop.
• Evaluating both sides of && or || despite C's short-circuit behaviour.
• Reusing a register while its previous value is still needed.

Checking a Translation#

Trace a tiny case by hand. For a loop which should process i = 0, 1, 2:

This exposes off-by-one errors and backwards conditions quickly. Running MIPS explains how to perform the same trace interactively.

Sources and Further Reading#

• COMP1521 MIPS control notes
• COMP1521 course material
• COMP1521 MIPS instruction reference