Unformatted text preview:

Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science 6.035, Fall 2006 Practice Quiz 2 Saturday, November 04 1. For the basic block: q = 3 r = 10 s = q + r t = 2*r+s t = q u = q + r v = q + t w = 3 + x State for each of the basic b locks on the following page which optimization was p erformed on the above: • Constant Propagation/Folding • Copy Propagation • Common Subexpression Elimination • Dead Code Elimination. 1Name: (a) q = 3 r = 10 s = q + r t1 = s t = 2*r+s t = q u = t1 v = q + t w = 3 + x (b) q = 3 r = 10 s = q + r t = 2*r+s t = q u = q + r v = q + q w = 3 + x (c) q = 3 r = 10 s = 13 t = 33 t = 3 u = 13 v = 36 w = 3 + x (d) q = 3 r = 10 s = q + r t = q u = q + r v = q + t w = 3 + x 2Name: 2. In class we discussed available expression dataflow analysis. Recall that an expression e is available at point p if: • Every path from the initial node to p evaluates e before reaching p, and • There are no assignments to any operand of e after evaluation but before p. In the table below, fill in the final values of IN obtained after performing available expression analysis on the CFG of Figure 1 (next page). A ’1’ should indicate the expression is available on entry to the block. a + b c * d e / f B1 0 0 0 B2 B3 B4 B5 B6 B7 3Name: Entry B1: q = a + b B2: r = e / f B3: B4: e = 2 B5: f = 3 t = c * d w = a + b B6: x = c * d y = e / f a = 1 s = e / f B7: z = e / f Exit Figure 1: CFG for problem 2. 4Name: 3. Recall from lecture that a variable v is live at point p if: • v is used along some path starting at p, and • There is no definition of v along p before its use. In the table below, fill in the final values of OUT obtained after performing liveness analysis on the CFG of Figure 2 (next page). A ’1’ should indicate the variable is live on exit from the block. Assume all variables are visible outside the procedure. a b c B1 B2 B3 B4 B5 B6 B7 1 1 1 5Name: Entry B1: c = 4 B2: a = b + c B3: c = a + b B4: a = 5 a = 1 B5: B6: b = 3 b = 2 B7: c = a + b Exit Figure 2: CFG for problem 3. 6Name: 4. A compiler hacker writes an analysis to compu te values of integer variables in a program. The hacker’s analysis maintains a set for each variable at each program point, the set contains the possible values for that variable. The hacker uses set union to combine values at the control-flow join points. The hacker tests the analysis on several acyclic control flow graphs and it is shipped in the compiler. One of the customers tries to compile a program that contains a loop, and the analysis fails to terminate. What is the problem? Describe the changes that the compiler hacker must make to fix the analysis. 7MIT OpenCourseWarehttp://ocw.mit.edu 6.035 Computer Language Engineering Spring 2010 For information about citing these materials or our Terms of Use, visit:


View Full Document

MIT 6 035 - Study References

Download Study References
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Study References and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Study References 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?