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]
    use
    0:{ t0 }
    1:{ }
    2:{ t1 t2 }
    3:{ }
    4:{ t1 }
    5:{ t2 t3 }
    6:{ t33 }
    7:{ }
    8:{ }
    9:{ t3 }    		 def
    0:{ t1 }
    1:{ }
    2:{ }
    3:{ }
    4:{ t2 }
    5:{ t33 }
    6:{ t3 }
    7:{ }
    8:{ }
    9:{ t3 }    		 succ
    0:{1}
    1:{2}
    2:{3,8}
    3:{4}
    4:{5}
    5:{6}
    6:{7}
    7:{1}
    8:{9}
    9:{}
  2. (3) Give the flow graph.
    0: t1 <= t0 ; goto 1
    1: <- ; goto 2
    2: <- t1 t2 ; goto 8 3
    3: <- ; goto 4
    4: t2 <= t1 ; goto 5
    5: t33 <- t3 t2 ; goto 6
    6: t3 <= t33 ; goto 7
    7: <- ; goto 1
    8: <- ; goto 9
    9: t3 <= t3 ; goto
  3. (5) Give the first complete pass in computing live in and out sets.
    in
    0:{ t0 }
    1:{ }
    2:{ t1 t2 }
    3:{ }
    4:{ t1 }
    5:{ t2 t3 }
    6:{ t33 }
    7:{ }
    8:{ }
    9:{ t3 }    		 out
    0:{ }
    1:{ }
    2:{ }
    3:{ }
    4:{ }
    5:{ }
    6:{ }
    7:{ }
    8:{ }
    9:{ }
    use
    0:{ t0 }
    1:{ }
    2:{ t1 t2 }
    3:{ }
    4:{ t1 }
    5:{ t2 t3 }
    6:{ t33 }
    7:{ }
    8:{ }
    9:{ t3 }    		 def
    0:{ t1 }
    1:{ }
    2:{ }
    3:{ }
    4:{ t2 }
    5:{ t33 }
    6:{ t3 }
    7:{ }
    8:{ }
    9:{ t3 }    		 succ
    0:{1}
    1:{2}
    2:{3,8}
    3:{4}
    4:{5}
    5:{6}
    6:{7}
    7:{1}
    8:{9}
    9:{}

     

    Iterating 9..0 gives:

    in
    0:{ t0 }
    1:{ }
    2:{ t1 t2 }
    3:{ }
    4:{ t1 }
    5:{ t2 t3 }
    6:{ t33 }
    7:{ }
    8:{ }
    9:{ t3 }    		 out
    0:{ }
    1:{ t1 t2 }
    2:{ }
    3:{ t1 }
    4:{ t2 t3 }
    5:{ t33 }
    6:{ }
    7:{ }
    8:{ t3 }
    9:{ }

     

  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:{ }    		 def
    0:{ t1 }
    1:{ }
    2:{ }
    3:{ }
    4:{ t2 }
    5:{ t33 }
    6:{ t3 }
    7:{ }
    8:{ }
    9:{ t3 }
    for each node in the flow graph
      for each def temporary at that node
         for each live out temporary at that node
             addEdge(def, out);
             addEdge(out, def);
    Live Interval
    t33 [5,5]
    t1 [0,7]
    t2 [0,7]
    t3 [0,8]    		 Interference Graph
    t1: t33 t3 t2 t1
    t2: t33 t3 t2 t1
    t3: t3 t2 t1
    t33: t2 t1 t33