Exercise 10        Name __________________        Score __/18

  1. (5) The IR at left translates into the Mips instructions at right. Give the def, use and succ sets.
    MOVE(a,CONST(0))
    LABEL(WHILE)
    CJUMP(Tree.CJUMP.NE, a, b, T, ENDWHILE)
    LABEL(T)
    MOVE(b,a)
    MOVE(c,BINOP(BINOP.PLUS,c,b))
    JUMP(WHILE)
    LABEL(ENDWHILE)
    MOVE(c,c)    		 0.  MOVE [ move `d0 `s0] [t1] [t0]
    1.  LABEL [WHILE:][WHILE]
    2.  OPER  [ bne `s0 `s1 T] [] [t1 t2 ] [T ENDWHILE]
    3.  LABEL [T:][T]
    4.  MOVE [ move `d0 `s0] [t2] [t1]
    5.  OPER [add `d0 `s0 `s1] [t33 ] [t3 t2 ] []
    6.  MOVE [ move `d0 `s0] [t3] [t33]
    7.  OPER [ b WHILE] [] [] [WHILE]
    8.  LABEL [ENDWHILE:] [ENDWHILE]
    9.  MOVE [ move `d0 `s0] [t3] [t3]
  2. (3) Give the flow graph.
  3. (5) Give the first complete pass in computing live in and out sets.
  4. (5) From the given final def and out sets determine the interference graph.
    in
    0:{ t0 t2 t3 }
    1:{ t1 t2 t3 }
    2:{ t1 t2 t3 }
    3:{ t1 t3 }
    4:{ t1 t3 }
    5:{ t1 t2 t3 }
    6:{ t33 t1 t2 }
    7:{ t1 t2 t3 }
    8:{ t3 }
    9:{ t3 }    		 out
    0:{ t1 t2 t3 }
    1:{ t1 t2 t3 }
    2:{ t1 t3 }
    3:{ t1 t3 }
    4:{ t1 t2 t3 }
    5:{ t33 t1 t2 }
    6:{ t1 t2 t3 }
    7:{ t1 t2 t3 }
    8:{ t3 }
    9:{ }