MCS-388 Homework 5 (Spring 2013)

Due: April 23, 2013

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:

Here are your tasks:

  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:
Instructor: Max Hailperin <>