Reading

H+P Chapter 6, sections 1 and 2; don't bother to study the diagrams in detail.
H+P Chapter 8, sections 1, 3, skim sections 4 and 5.

To do on your own

Look over chapter 3 and see if there's anything you don't understand.

To be turned in

1. H+P exercises 3.29 and 3.30.

2. Recall the five MIPS addressing modes (listed on page 151). Which types of operands might need to be altered by the linker during relocation? Which can always be left alone? Explain your answers. Hint: it may help to look at the examples on pages 160-162.

3. Recursive tree traversal. You have a binary tree. Each node in the tree contains an integer value, the address of the node's left child, and the address of the node's right child. An example tree of this form is shown below:

The child addresses are 0 if the node has no children. Each node has either two children or none.

Here is a MIPS procedure which takes the address of a tree's root node in $a0. What does it return in $v0?

treecomp: subi $sp, $sp, 12
          sw   $s1, 8($sp)
          sw   $ra, 4($sp)
          sw   $a0, 0($sp)
          lw   $t0, 4($a0)
          bne  $t0, $zero, L1
          lw   $v0, 0($a0)
          addi $sp, $sp, 12
          jr   $ra
      L1: lw   $a0, 4($a0)
          jal  treecomp
          add  $s1, $v0, $zero
          lw   $a0, 0($sp)
          lw   $a0, 8($a0)
          jal  treecomp
          add  $v0, $v0, $s1
          lw   $ra, 4($sp)
          lw   $s1, 8($sp)
          addi $sp, $sp, 12
          jr   $ra

Extra credit: Modify treecomp to return the largest value in the tree. Your program should differ from treecomp as little as possible. Comment the lines that you add/change.