Notes for week 14

Day 1

DAGs and 3AC

1. DAGs vs 3AC on expressions

   Different than DAGs on expressions since they have to keep track of changes in values of variables

2. Generating a DAG
   1. Two forms

      Two forms a:= b op c or a := op b

   2. Also an array current that contains a pointer to the node that contains the current value of each variable. (May use a numerical value for each variable name so that given a name lookup the number corresponding to that name and use the number as a subscript)
      1. All values in current are nil initially.
      2. Add the statement a:= b op c to the DAG
      3. If current[b] = nil then create a new leaf node labeled b and make current[b] point to the leaf. Do the same for c.
   3. Trace the construction of the DAG on overlay.

      Basic block 9 from week 12

      (17) T7 := i - 1 (18) T8 := T7 * 4 (19) T9 := x[T8] (20) temp := T9 (21) T10 := jmax - 1 (22) T11 := T10 * 4 (23) T12 := x[T11] (24) T13 := i - 1 (25) T14 := T13 * 4 (26) x[T14] := T12 (27) T15 := jmax - 1 (28) T16 := temp

3. Converting DAG to 3AC-Topological sort.

   1.	x[T11]
   2.	x[T8]
   3.	T12
   4.	T11,T16
   5.	T10,T15
   6.	T9, temp
   7.	T8, T14
   8.		T7,T13
   9.		x
   10.	jmax
   11.	(i)
   12.	1
   13.	4	
   

Simple DAG Code

For a simple demonstration of how to build optimizing code for a DAG click here.