Exercise 9        Name __________________        Score __/18

1. (9) For each of the following expressions, draw the tree and generate Jouette-machine instructions using maximal munch. Cicrle the tiles (as in Figure 9.2) but number them in the order they are munched and show sequence of Jouette instructions that result.

    

   1. MOVE(MEM(TEMP x), MEM(+ (TEMP fp, CONST 1)))

      ADDI t5 <- tfp+1 MOVEM M[tx] <- M[t5]

   2. MOVE(MEM( + ( + (CONST 1000, MEM(TEMP x)), TEMP fp)), CONST 0)

       

      LOAD t3 <- M[tx] ADDI t2 <- t3+1000 ADD t1 <- t2+tfp ADDI t4 <- 0 STORE M[t1] <- t4

      

       

2. (9) The Jouette machine has control-flow instructions as follows:
   1. BRANCHGE    if r_i >= 0 goto LABEL
   2. BRANCHLT     if r_i < 0 goto LABEL
   3. BRANCHEQ    if r_i == 0 goto LABEL
   4. BRANCHNE    if r_i != 0 goto LABEL
   5. JUMP            goto r_i

   _{where the JUMP instruction goes to an address contained in a register.}

   _{Use these instructions to implement the following tree patterns:}

       _{JUMP            JUMP                      CJUMP  
          |                  |                       /  |  |   |  \ 
                           NAME                EQ        T   F}

   _{Assume that a CJUMP is always followed by its false label and the T and F label basic blocks. Show the best way to implement each pattern; in some cases you may need to use more than one instruction or make up a new temporary.}

   JUMP                 goto ri	JUMP    |
   JUMP                 ADDI ri <- r0 + NAME                         JUMP goto ri	JUMP    | NAME
   BRANCHEQ        SUB ri <- rj - rk                         if ri == 0 goto T	CJUMP       /  |  |  |  \    EQ        T  F