This assignment is a variant of Exercises 8.4.1 and 9.1.3(a), but please use my instructions rather than those in the textbook.
This entire assignment concerns the matrix multiplication algorithm in Figure 8.10 on page 532.
As you complete the numbered tasks in this assignment, use the following bulleted guidelines:
Assume that the arrays a, b, and
c are indexed from 0 to n-1 in each dimension.
Assume that you know at compile time that n is 300 and
that the arrays a, b, and c
start at addresses 10000, 4000000, and 6000000, respectively. Each
element in these arrays occupies four bytes. Memory addresses are
expressed in units of bytes.
Because you know that n≥1, you know that each loop
will execute at least once. Take advantage of this fact by having
each loop execute its test only after it has made it through the loop
body.
Create a new temporary for each value, rather than trying to be frugal and re-use temporaries. That is, do something like
t1 := i * n
t2 := t1 + j
not
t1 := i * n
t1 := t1 + j
However, don't bother with SSA form for the variables
i, j, and k.
In your three address code, do not use the bracket notation, but rather do the address addition explicitly. For example, a one-dimensional array reference would look like
t1 := i * 4
t2 := d + t1
t3 := *t2
rather than
t1 := i * 4
t3 := d[t1]
Similarly, storing into that array element would look like
t1 := i * 4
t2 := d + t1
*t2 := t3
rather than
t1 := i * 4
d[t1] := t3
Here are your tasks:
Produce three-address statements for the program.
Construct a flow graph from the three-address statements.
Eliminate the common subexpressions from each basic block.
Move the loop-invariant computations out of the loops.
Find the induction variables of each loop and eliminate them where possible.
Briefly describe any major opportunities for optimizing this routine that are not covered by the exercise. Keep in mind that on contemporary machines, it is memory accesses that are generally the most time consuming operations.