Decisions

So far, we have only covered sequential execution. In other words, the instructions are executed in program order from top to bottom. Unfortunately, this is not enough to perform general computing tasks¹. For general computing tasks, we need two additional constructs:

1. Selection (i.e., making decision): if and switch-case.
2. Repetition (i.e., iterations): while, do-while and for.

In MIPS, both selection and repetition are combined into a single construct similar to if statement followed by a goto. Note that C has a goto statement but it is highly discouraged².

What these "decision making" instructions do is to alter the control flow of the program as well as change the next instruction to be executed. For instance, it allows a certain sequence to be executed only if a certain condition occurs (i.e., selection via goto downward) or a certain sequence to be executed multiple times until a certain condition is no longer valid (i.e., repetition via goto upwards).

Label

There are two types of decision making statements in MIPS:

1. Conditional (a.k.a., branch)
   • bne $t0, $t1, label
   • beq $t0, $t1, label
2. Unconditional (a.k.a., jump)
   • j label

A label is an "anchor" in the assembly code to indicate a point of interest. This is usually a branch target but can also be used to indicate a logical grouping for the programmer. It is important to note that labels are NOT instructions.

You have seen one instance of label in the previous section:

1
2
3
4
5
6
7

swap:
  sll  $2, $5, 2   #  $v0    = k * 4     -- for word alignment
  add  $2, $4, $2  #  $v0    = (k*4)+v   -- computing the actual address
  lw   $15, 0($2)  #  temp   = v[k]
  lw   $16, 4($2)  #  $t8    = v[k+1]
  sw   $16, 0($2)  #  v[k]   = $t8
  sw   $15, 4($2)  #  v[k+1] = temp

Here, the name swap is a label. It indicates that the code below it belongs to the same logical grouping for swapping. The labels can be any name and will be removed from the code during assembly. As such, its use is only for us programmers to understand the code better.

Conditional Branch

Branch indicates that there are at least two possible choices for the path to take. In this case, the processor follows the branch only when the condition is satisfied (i.e., true). There are two conditional branch instructions in MIPS depending on whether the condition should be based on equality or non-equality.

1

beq $rs, $rt, label

1
2
3

if($rs == $rt) {
  // label lands here
}

1

bne $rs, $rt, label

1
2
3

if($rs != $rt) {
  // label lands here
}

Although we show the possible MipC equivalent code, it is not exactly correct. In this case, there is an implicit assumption that label is after the current instruction. Furthermore, there is a common trick to slightly optimise the code for selection. More importantly, the conversion should be the other way around (i.e., MipC to MIPS).

Unconditional Jump

A jump indicates no choice. In this case, the processor always follows the branch.

1

j label

1

beq $reg, $reg, label

Inequalities

We have beq and bne, but what about if want to branch on inequalities? For example, what if we want to branch when $rs is less than $rt? There is no real blt (i.e., branch on less than) instruction but there are several pseudo-instructions.

In the end, it will still be translated into real instructions. What are the real instructions used in this case? Suprisingly, only one additional real instruction is needed to be able to translate all of the pseudo-instructions.

1

slt $rd, $rs, $rt

1
2
3
4
5

if (rs < rt) {
  rd = 1;
} else {
  rd = 0;
}

Given this additional instruction, we can now build the pseudo-instructions as follows:

1
2

slt $t0, $rs, $rt
bne $t0, $zero, L

1
2

slt $t0, $rt, $rs
bne $t0, $zero, L

1
2

slt $t0, $rt, $rs
beq $t0, $zero, L

1
2

slt $t0, $rs, $rt
beq $t0, $zero, L

Take a moment to understand the translation. If you are having problem understanding the translation, do click on the explanation below.

1
2

$rs > $rt
≡ $rt < $rs

1
2
3
4

$rs <= $rt
≡ !($rs > $rt)
≡ !($rt < $rs)
≡ ($rt < $rs) == 0

1
2
3
4
5

$rs >= $rt
≡ $rt <= $rs
≡ !($rt > $rs)
≡ !($rs < $rt)
≡ ($rs < $rt) == 0

Examples

Selection Statement

1
2
3

if (i == j) {
  f = g + h;
}

1
2
3

if ($s3 == $s4) {
  $s1 = $s1 + $s2;
}

1
2
3
4

      beq $s3, $s4, L1
      j   Exit
L1:     add $s0, $s1, $s2
Exit:

1
2
3

      bne $s3, $s4, Exit
      add $s0, $s1, $s2
Exit:

1
2
3
4
5

if (i == j) {
  f = g + h;
} else {
  f = g - h;
}

1
2
3
4
5

if ($s3 == $s4) {
  $s1 = $s1 + $s2;
} else {
  $s1 = $s1 - $s2;
}

1
2
3
4
5

      bne $s3, $s4, Else # invert then goto else branch
      add $s0, $s1, $s2
      j   Exit
Else: sub $s0, $s1, $s2
Exit:

Repetition Statement

For the repetition statement, the MipC intermediate is not exactly useful as we designed the MipC to be quite close to C for these high-level constructs. As such, in the examples below, we will simply show the MIPS instructions instead with explanation in a C with goto.

1
2
3

while (j == k) {
  i = i + 1;      // ignore for a moment that this is infinite loop
}

1
2
3
4

Loop: if (j != k) goto Exit;  // Inversion: exit when false
      i = i + 1;
      goto Loop;              // Jump back to start of loop
Exit:

1
2
3
4

Loop: bne  $s4, $s5, Exit  # Inversion: exit when false
      addi $s3, $s3, 1
      j    Loop            # Jump back to start of loop
Exit:

1
2
3

for (i=0; i<10; i++) {
  a = a + 5;
}

1
2
3
4
5
6

i = 0;
$s1 = 10;
while (i != $s1) {
  a = a + 5;
  i++;
}

1
2
3
4
5
6
7

      add  $s0, $zero, $zero #       i   = 0;
      addi $s1, $zero, 10    #       $s1 = 10;
Loop: beq  $s0, $s1, Exit    # Loop: if (i == $s1) goto Exit;
      addi $s2, $s2, 5       #       a   = a + 5;
      addi $s0, $s0, 1       #       i++;
      j    Loop              #       goto Loop;
Exit:                        # Exit:

Array and Loop

A typical example of accessing array elements in a loop can be summarised with the diagram below:

1
2
3
4
5
6
7
8

result = 0;
i = 0;
while (i < 40) {   // How to compare correctly?
  if (A[i] == 0) { // How to translate A[i] correctly?
    result++;
  }
  i++;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

      addi $t8, $zero, 0
      addi $t1, $zero, 0
      addi $t2, $zero, 40    # end point
loop: bge  $t1, $t2, end     # pseudo-instruction, can you use beq?
      sll  $t3, $t1, 2       # $t3 = i*4     (for offset computation)
      add  $t4, $t0, $t3     # $t4 = &A[$t3] (after offset computation)
      lw   $t5, 0($t4)       # $t5 = A[$t3]  (deferencing using *$t4)
      bne  $t5, $zero, skip
      addi $t8, $t8, 1       # result++
skip: addi $t1, $t1, 1       # i++
      j loop
end:

1
2
3
4
5
6
7
8
9

result = 0;
curr = &A[0];
last = &A[40];
while (curr < last) { // How to compare correctly?
  if (*curr == 0) {   // How to translate curr correctly?
    result++;
  }
  curr++;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

      addi $t8, $zero, 0
      addi $t1, $t0, 0      # curr = &A[0];
      addi $t2, $t0, 160    # last = &A[40];
loop: bge  $t1, $t2, end    # address comparison! can you use beq?
      lw   $t3, 0($t1)      # $t3 = *curr  (simple load)
      bne  $t3, $zero, skip
      addi $t8, $t8, 1      # result++
skip: addi $t1, $t1, 4      # curr++ (move to next item, but add 4 to address)
      j loop
end:

1
2
3
4
5
6

       addi $t1, $zero, 10
       add  $t1, $t1, $t1
       addi $t2, $zero, 10
Loop:  addi $t2, $t2, 10
       addi $t1, $t1, -1
       beq  $t1, $zero, Loop

1
2
3
4
5
6

       add  $t0, $zero, $zero
       add  $t1, $t0, $t0
       addi $t2, $t1, 4
Again: add  $t1, $t1, $t0
       addi $t0, $t0, 1
       bne  $t2, $t0, Again

1
2
3
4
5
6

       addi $t1, $t0, 10
       add  $t2, $zero, $zero
Loop:  ulw  $t3, 0($t1) # ulw: unaligned lw
       add  $t2, $t2, $t3
       addi $t1, $t1, -1
       bne  $t1, $t0, Loop