CS612 Problem Set #4

Due date: Tuesday, April 10, 2001 - In class

Problem 1. Transforming imperfectly nested codes

Consider the following program,

arrays L(n,n), B(n,m) // column-major

do k = 1, m
    do i = 1, n
        do j = 1, i-1
            S1: B(i,k) = B(i,k) - L(i,j) * B(j,k)
        enddo
        S2: B(i,k) = B(i,k) / L(i,i)
    enddo
enddo
  1. What are the statement iteration spaces?
  2. What is the product space and the embedding functions for each statement?
  3. Show what the code for the product space would look like. Hint: your code: will be perfectly nested and have guards.Your code will look something like, 
    do t1 = ...
    do t2 = ...
        ...
            do tn = ...
                if ... then S1(t1,t2,...,tn)
                if ... then S2(t1,t2,...,tn)
            enddo
        ...
    enddo
enddo
  4. Is tiling of this code legal? If so, why? There are two approaches to answering this question. The first is to make a high-level argument. The second approach is to use Omega to calculate the dependence vectors and prove it empirically. Either is acceptable.

Problem 2. Scalar Optimizations

A copy assignment is an assignment of the form "x := y". Copy propagation is an analysis which identifies all points in the program to which the effect of the assignment reaches. That is, it identifiers all points in the program in which copy assignments are have been executed without intervening definitions of either "x" or "y". Uses of "x" at this points can safely be replaced by "y".

  1. What are the lattice and dataflow equations for copy propagation?
  2. Consider the program below. Show a bit-vector evaluation of the analysis.

  1. Show the def-use chains for this program. Describe how copy propagation can be computed using def-use chains, and show the results for this program. How and why do these results differ from the bit-vector results?

Problem 3. Control Dependence and Roman Chariots

Consider the following control flow graph,

  1. What is the post-dominance tree for this program?
  2. Suppose that a=1. Show the zones that are constructed using the greedy algorithm given in class.
  3. Annotate your post-dominance tree with the information that would be cached for the CONDS relation (i.e., the information about where chariot routes end). Don't forget that interior and boundary nodes are handled differently.
  4. Answer the following queries,