Notes for week 12

Day 1.

Reductions of Change of control productions.

You have a test program you will compile. To see a listing of that program; the trace of the compile; and three address code click here . The following are excerpts from that code that illustrate some of the code generated for conditionals and jumps.

1. Trace the following code

   THIS : INTEGER;
    THAT : REAL;
   
    S1 -> "if" C CondGoToMark "then" S1 GoToMark "else" S1
   
    IF THIS > THAT THEN
    	THIS := THIS
    ELSE
   	THAT := THIS;
   
   6  @temp4 := intoReal(this)
   7  @temp5 := @temp4>that
   8  if not @temp5 then goto 11
   9  this := this
   10  GoTo 13
   11  @temp7 := intoReal(this)
   12  that := @temp6
   13  @temp8 := this+thin
   

   Discuss the CondGoToMark code

   S1 -> "while" Mark C CondGoToMark "do" S1
   
   WHILE THIS <= THAT DO
   	THAT := THIS;
   
   17  @temp10 := intoReal(this)
   18  @temp11 := @temp10<=that
   19  if not @temp11 then goto 23
   20  @temp12 := intoReal(this)
   21  that := @temp12
   22  GoTo 17
   

   Day 2

2. Machine independent optimization
   1. Consider the code generated for X := A + B; Notice the redundant instructions T := A+B X := T
   2. Would like to eliminate this type of problem before tackling the problem to tayloring code for a particular architecture
   3. Optimization takes place over a series of steps, so must make sure that we are not changing the intent of the code when optimizing. Optimizing is a source of errors. (recall VAX Pascal)
   4. Basic Blocks
      1. Set of 3AC instructions always executed in order from beginning to end.
      2. One of the advantages of basic blocks is that if code is changed actual addresses will change. Goto address must be altered. In basic block representation, the address in gotos are changed to the name of the block that contained the original destination. This will always be the beginning of the block.
      3. Computing basic blocks
         1. Blocks begin
            1. At the start of the program
            2. At the target of any branch
            3. Immediately after any branch
         2. Blocks End
            1. Before the next basic block
            2. At the end of the program.
      4. Show the example.

Code Generated

1	i := n
2 	if i < 2 then goto 32
3 	jmax := 1
4	j := 2
5 	if j > i then goto 16
6	T1 := j - 1
7	T2 := T1 * 4
8	T3 := x[T2]
9	T4 := jmax - 1
10	T5 := T4 * 4
11	T6 := x[T5]
12	if T3 <= T6 then goto 14
13	jmax := j
14 	j := j + 1
15	goto 5
16	if i = jmax then goto 30
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
30	i := i -1
31 	goto 2	
32	return

Code Divided Into Blocks