CS 553 Compiler Construction — Fall 2006 Homework #2Dominators, Loops, SSA, and Value Numbering Due October 16, 2005Write your answers on another sheet of paper. Homework assignments are to be completedindividually. Hand written submissions are fine, but they must be readable. Due at the beginningof class. Total points: 100, 5% of course grade1. [30 Points] Here is an example program.y = ...t = ...a = 3 + tb = ac = ax = 40if (y<x) goto L1z = y + cx = b + 30goto L2L1:z = y + 30L2:t = z + x(a) Draw a control-flow graph for the given program.(b) Show the dominance frontiers.(c) Show the SSA representation for the given program.12. [20 Points] Below is the MPI-CFG for a parallel version of matrix-vector multiplication. AnMPI-CFG is a control-flow graph extended with communication edges to indicate possiblepairings betwee n message passing sends and receives. The nodes labeled with just numbersinclude more code that has been removed since the code is not immediately relevant. If thecommunication edges are not treated any differently than the control-flow edges, then is thegraph reducible? Explain why it is reducible or not.Entry2myid .eq. master1Broadcasti=1i<min(numprocs-1,rows)3Sendnumsent = numsent + 1i = i+1i<rowsReceive4i = i+1if (numsent .lt. rows)5numsent=numsent+1SendSendi=1Broadcastif (rank .gt. rows)ExitReceiveif (status(MPI_TAG) .eq. 0)6 (comp)Send23. [50 Points] Consider the following code (assume that read is a function that reads input fromstdin):a = read()b = read()z = read()w = read()x = a + by = b + aj = 0loop:z = b * aif (z > j) goto L1w = a * bgoto L2L1:w = b * aL2:x = a + by = xj = j + 1if (j<10) goto loopprint w,x,y,z(a) Compute the dominators for the given program.(b) What statements are involved in loop(s)?(c) Perform pessimistic global value numbering.(d) Perform optimistic global value
View Full Document
Unlocking...