Homework # 6
due November 14

Reading

Read Section 2.5 up to the end of 2.5.2 (page 88)

Book Problems

Do problem 2.10.

Discussion

Consider (but do not do) Problem 2.13. The ``similar result'' in the second half is true for WHILE, but neither is true for Java flow graphs with exceptions.

• Write a simple Java try-catch statement which has ``dead code'': code that cannot be reached.

Since we have this situation, we cannot directly use the proof of Lemma 2.32 on page 78. But it turns out that if we have an additional restriction on the transfer functions, we can preserve the desired result ( ).

• Look at the proof (particular the middle of page 79) and find an additional restriction on the transfer functions that permits the proof to carry forward. Use the terminology from Appendix A 1 (Properties of functions, pages 393-394). Explain this restriction intuitively.

Programming

• Modify the flow-graph so that it has boolean expressions as nodes as well as statements. The graph maker should put ``assume'' boolean expression on each branch from an ``if'' or ``while'' node. (You will need to create exactly one ``not'' boolean expression node for each instance of a ``if'' statement or of a ``while'' statement.)

  You may also need to change your existing GEN-KILL analyses or PerformGenKill to not have problems with these new nodes.

• Define an interface Analysis that defines an instance of an analysis that fits within the monotone framework. This interface should have methods getLattice, isReverse, getInitial and transfer. The latter method should compute the transfer function and should take the node and the input lattice element value. Please be careful to distinguish the lattice from the lattice elements.
• Write a PerformAnalysis class to run any analysis on a WHILE program. The class will be very similar to PerformGenKill.
• Define a wrapper class that enables a GEN-KILL analysis to be used as a general analysis instance. You will find it easier if the GEN-KILL analysis interface is changed first to use a method such as isIntersection instead of a combine method. If you do this, make sure your GEN-KILL analysis framework still works after the change.
• Implement Strongly Live Variable Analysis. Since in WHILE, division expressions can halt program execution, any denominator not known to be non-zero is strongly live.
• Implement Constant Propagation Analysis using VariableLattice. Use conditions intelligently, unlike in the book. You must do at least one of the following checks:
  • If the condition is impossible, propagate the ``bottom'' lattice element value.
  • If the condition requires an equality (e.g. x = 0), then propagate it.
• Run your analysis on examples that demonstrate it working correctly.

Submission

As with all homeworks, please turn in your homework on paper at the beginning of lecture. You may also send the code in an email attachments to boyouen at gmail.com

About this document