CS243 Assignment 4

In this assignment, you will develop and use a dataflow analysis that will actually speed up Java programs. There are two components to this assignment, only one of which is mandatory.

The problem

When generating Quads out of Java bytecodes, safety checks are explicitly added at all possible points; everything is NULL_CHECKed before it is ever dereferenced. This is wasteful. Often we perform many actions on the same pointer, and we really ought to only be checking it once.

Your task

Write a program to identify all NULL_CHECKs that are redundant with respect to NULL_CHECK. For this version, if, at the IN point of a NULL_CHECK statement, all paths leading to that point have had a successful NULL_CHECK on that variable's value, the check should be removed.

The output format here is stylized to make the code easier to autograde. See "What to turn in," below.

Extra credit

Our null-check analysis is simple, but it can be used to speed up code. If you want some bonus points (and these are REAL bonus points; they are applied after all grades are curved), strengthen this analysis, or perform other optimizations. This is as open-ended as you want it to be; some sample code to optimize will be made available over the next couple of days. Options for this include:

• Strengthen the NULL_CHECK removal. There are several ways one could go about doing this.
• Remove redundant array bounds checking.
• Remove redundant type checking.
• Perform copy propagation, or adapt the constant-propagation code we gave you in homework 2 to transform uses of an unneeded variable with the 'simpler' value. When combined with a dead-code-elimination pass, this could dramatically tighten the code.

We will award between 0 and 20% extra credit for this assignment. However, all optimizations must be sound! If you remove even one necessary null or bounds check, or falsely copy a constant, we will award no extra credit.

Where to start

Copy the basics from /usr/class/cs243/optimize/ or download them from here. We provide:

• A basic dataflow solver, in Flow.java and ReferenceSolver.java. Note that the Flow.Analysis interface has changed a little bit, to include the result of test quads (e.g. IFCMP).
• A submission script, submit.sh.
• A copy script, copy_assignment.sh.
• Two skeleton programs, FindChecks.java and Optimize.java.
• NullTests.java, an annotated source file for FindChecks to optimize. Includes some truly ridiculous corner cases for the ambitious.

What to turn in

• FindChecks.java, which takes a class as an argument on the command line and prints out, for each method in the class, a name, and then a sorted set of integers corresponding to the quad IDs of redundant NullChecks, like so:
  main: [4, 17, 19]
sample: [5]
<init>: []
• Optimize.java, which performs all the optimizations on the control flow graph. It should print out the fullDump() of the optimized ControlFlowGraph. (Since these by their nature will have to be hand-evaluated, the requirements are less strict.)
• README, which includes your names, logins, name of one person in the group that you are sharing test cases with (if you share test cases), and a description of your design. Explain the dataflow analysis used in FindChecks, and the optimizations you applied in Optimize.
• Any supporting classes you define for the project.

Submitting

• A submit.sh script is available in the usr/class/cs243/optimize/submit.sh
• Run the script from the directory containing all your files.
• If you are working with a partner, then only one of you need to submit the assignment and put your partner Sunet ID as an argument to the submit script.
  For example : usr/class/cs243/optimize/submit.sh foo where foo is the Sunet ID of your partner.

Transforming the code

Joeq provides a limited capability to modify the code that it analyzes. The two easiest transforms are the removal of quads or the addition of new ones; the QuadIterator's remove() and add(Object o) commands allow one to remove the most recently returns quad or insert quads after it, respectively.

To change the values of Operands, there are static methods in each Operator class to set the appropriate argument. For example, Move has methods setDest and setSrc to complement getDest and getSrc.

Actually modifying the ControlFlowGraph is trickier. You'll need to use ControlFlowGraph.createBasicBlock to construct the Basic Blocks, and the addFoo routines in BasicBlock itself to modify the lists of quads. Consult the joeq javadocs for full details on these points.