CSE 401 - Homework Assignment #3

Due: Wednesday December 10, 5PM.

This is required only of the students doing the reduced project (MiniJava--).

Produce a hard-copy of your answers and turn them in under Notkin's door (or submitted by email).

  1. Page 761-2, Section 8.6, Problems 1, 2
  2. Page 763, Section 8.7, Problem 1.
  3. [Due to Aho and colleagues] Consider the matrix multiplication program:

    for i = 1 to n do
        for j = 1 to n do
            c[i,j] = 0;
    for i = 1 to n do
        for j = 1 to n do
            for k = 1 to n do
                c[i,j] = c[i,j] + a[i,k]*b[k,j];

    1. Assume a, b and c are allocated in static memory, produce MiniJava IL code for this program.
    2. Generate x86 target machine code from the IL.
    3. Construct a control flow graph (CFG) from the IL.
    4. Eliminate common subexpressions from each basic block.
    5. Find the loops in the CFG.
    6. Move loop-invariant computations out of the loops.
    7. Find and eliminate, if possible, induction variables for each loop.
    8. Generate x86 target machine code from the new IL produced using c-g.
    9. Compare the code from (b) and (h).
  4. Using the graph coloring register allocation heuristic shown in lecture and considering a machine with only three registers, produce an example IL program for which the heuristic produces a non-optimal register assignment.. (Or show that in this case, the heuristic always produces an optimal allocation.)
  5. Briefly explain how a dataflow analysis to compute "available expressions" would have to change to accommodate a programming language that had pointers.  A sketch of the issues is needed, not a detailed recasting of the dataflow equations.
  6. Page 767-8, Section 10.3, Problem 5a.
  7. Pages 768-9, Section 10.4, Problem 1.
  8. Page 768-9, Section 10.4, Problems 2a, 2c.