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