MCS-388 Homework 5

Consider the following matrix multiplication program:
  for i := 1 to n do
    for j := 1 to n do
      c[i,j] := 0
  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]
As you complete the numbered tasks found a little ways below, use the following bulleted guidelines. Here are your tasks:
  1. Assuming a, b, and c are allocated static storage and there are four bytes per word in a byte-addressed memory, 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.