11.1 Preparation for Code Generation

11.2 Generation of Directives

11.3 Simple Code Generation from AST's

11.4 Standard Code Generation Strategies

11.5 Code Generator Generators

11.6 Register Allocation

11.7 A Better Code Generation Algorithm from AST's

11.8 Code Generation from DAG's

11.9 Retargetable Code Generation

11.10 Peephole Optimization

11.11 Summary

Web References

Exercises

Exercises

1.
    (a) Using Belady's algorithm from Section 101.5 and the string

    uvwxuxvxw

    show a register use sequence, assuming only two registers are available.

    (b) Change the algorithm to the past tense and remove those variables which have not been used for the longest time.

2.
    (a) Create an abstract syntax tree for

    (a + b) * (a - b) / ((c + d) * (c - d))

    (b) Use the quick 'n dirty code generation algorithm from Example 3 to generate assembly language code.

    (c)Label it using the labeling algorithm of Section 10.4 (assuming at least 1 of the 2 operands is to reside in a register) with the minimal number of registers needed to compute it.

    (d)Using the code generation algorithm from Section 10.4, generate code for your tree

    (i) Assuming there are 10 registers available

    (ii) Assuming there are 2 registers available

3.
    Consider the following intermediate representation for code to multiply two matrices together:

     
    I := 1
    GOTO TestI
    ILoop: J := 1
    GOTO TestJ
    JLoop: C[I,J] := 0
    K := 1
    GOTO TestK
    KLoop: T1 := A[I,K] * B[K,J]
    T2 := C[I,J] + T1
    C[I,J] := T2
    K := K + 1
    TestK: IF K <= N GOTO KLoop
    K := K + 1
    TestJ: IF J <= N GOTO JLoop
    J := J + 1
    TestI: IF I <= N GOTO ILoop

    Translate this into assembly language code:

    (a) Using the templates from Section 10.3.1.

    (b) By extending the algorithms in Section 10.4 (to handle IF's and loops)

4.
    Perform peephole optimization on the code produced in Example 1.

5.
    Perform peephole optimization on the code produced in Example 3.

6.
    Perform peephole optimization on the following, showing each step separately:

    IF 5 &rt; 0 THEN GOTO L1  
    Goto L2
    L1: I := I + 1
    L3: IF I &rt; 5 GOTO L4
    GOTO L5
    L4: T1 := I * 1
    X := X + T1
    I := I + 1
    GOTO L3
    L5: GOTO L6
    L2: X := 0
    L6:

7.
    Consider the following expression (Knuth, 1971):

    A[I * N + J] := ((A + X) * y + 2 * 768 + ((L - M) * (-K)))/Z

    (a)

      Show the AST representation of this label each node with the minimal number of registers needed to compute it, assumming temporary results are kept in registers.

    (b)
      Give the target code which uses the minimal nuber of registers, again assuming temporary results are kept in registers. Use the following instruction forms:

      i. R:=M

      ii. M:=R

      iii. Ri:=Ri op Rj

      iv. Ri:=Ri op M

      plus the operator @ which means "address of" and indirection (Ri) which fetches the value whose address is stored in Ri.

8.

    Section 10.3.1 showed some code generation templates for symbol table entries, assignment statements, expressions, IF-THEN-ELSE's, WHILE loops, and arrays. Write code templates for

    (a) FOR loops

    (b) REPEAT loops

    (c) CASE statements

9.
    Write a greedy algorithm to perform register allocation by coloring.

10.
    (a)
      Draw the interference graph for the program of Example 1.

    (b)
      Find the minimal number of registers which allow variables X, Y, Z, and D to be assigned to registers.

11.
    Repeat Exercise 2 for a machine which performs multiplications and divisions by using (a) a register pair and (b) a register pair which must be consecutively even and odd, that is R2-R3, but not R3-R4.