CS274: Computer Architecture - MIPS Iteration
Activity Goals
The goals of this activity are:- To implement iterative algorithms using the MIPS assembly language
The Activity
Directions
Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity, and compare with your group to prepare for our whole-class discussion. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.Model 1: An iterative MIPS program
Questions
- What kind of loop do you see depicted in this program?
Model 2: Implementing Loops in MIPS
Questions
- Translate each of the above C code listings into a MIPS assembly program
Model 3: Key Formulas and Concepts Recap
A one-page summary of loops in MIPS.
The three loop skeletons:
while (cond) { body } do { body } while (cond); for (init; cond; update) { body }
-------------------- ------------------------ ---------------------------------
loop: loop: # init, e.g. li $t0, 0
# test cond; # body loop:
# branch to done # test cond; # test cond; branch to done
# when it FAILS # branch to loop # body
# body # when it HOLDS # update, e.g. addi $t0, $t0, 1
j loop j loop
done: done:
Notice: a while/for loop tests at the top (branching away on the opposite of the condition), and a do-while tests at the bottom (branching back when the condition holds), so its body always runs at least once.
A concrete counted loop (sum 0 + 1 + ... + 9), with every micro-step:
- Initialize:
li $t0, 0(i) andli $s0, 0(sum). - Test:
slti $at, $t0, 10sets$at= 1 while i < 10;beq $at, $zero, doneexits when i reaches 10. - Body:
add $s0, $s0, $t0. - Update:
addi $t0, $t0, 1. - Repeat:
j loop. The loop body runs exactly 10 times (i = 0 through 9).
Key rules:
| Rule | Micro-example |
|---|---|
| Branch away on the opposite of the loop condition to exit; jump back to repeat. | C's while (i < 10) becomes "exit when i >= 10" |
| Every loop needs an initialization, a test, and an update -- forget the update and you loop forever. | Without addi $t0, $t0, 1, i stays 0 and the test never fails |
Compound conditions (||, &&) become chains of branches. |
while (n < 1 || n > 10): branch back to the prompt from either test |
| When looping over an array by index, scale the index by 4 each iteration (or add 4 to a running pointer). | sll $t4, $t2, 2 then add $t3, $t0, $t4 |
| Backward branch offsets are negative two's complement word counts. | A branch 5 instructions back stores immediate 0xFFFB (-5) |
Glossary:
| Term | One-line definition |
|---|---|
| Loop body | The instructions repeated on every iteration. |
| Loop counter (induction variable) | A register (often a $t) that counts iterations, e.g. i. |
| Pre-test loop | Tests before the body (while, for); may run zero times. |
| Post-test loop | Tests after the body (do-while); always runs at least once. |
| Infinite loop | A loop whose exit test can never fail -- often a missing update instruction. |
| Sentinel | A special value (like a correct guess, or a string's null terminator) that ends a loop. |
| Backward branch | A branch or jump to an earlier address; the telltale sign of a loop in machine code. |