# MCS-388 Homework 5 (Spring 2009)

## Due: April 27, 2009

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

1. Produce three-address statements for the program.

2. Construct a flow graph from the three-address statements.

3. Eliminate the common subexpressions from each basic block.

4. Move the loop-invariant computations out of the loops.

5. Find the induction variables of each loop and eliminate them where possible.

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

Course web site: http://www.gac.edu/~max/courses/S2009/MCS-388/
Instructor: Max Hailperin <max@gustavus.edu>