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).

- Page 761-2, Section 8.6, Problems 1, 2
- Page 763, Section 8.7, Problem 1.
- [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;

end;

end;

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];

end;

end;

end

- Assume
**a**,**b**and**c**are allocated in static memory, produce MiniJava IL code for this program. - Generate x86 target machine code from the IL.
- Construct a control flow graph (CFG) from the IL.
- Eliminate common subexpressions from each basic block.
- Find the loops in the CFG.
- Move loop-invariant computations out of the loops.
- Find and eliminate, if possible, induction variables for each loop.
- Generate x86 target machine code from the new IL produced using c-g.
- Compare the code from (b) and (h).

- Assume
- 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.)
- 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.
- Page 767-8, Section 10.3, Problem 5a.
- Pages 768-9, Section 10.4, Problem 1.
- Page 768-9, Section 10.4, Problems 2a, 2c.