Due: Friday March 3rd, 5PM
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.
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.
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.
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:
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.
Copy the basics from
/usr/class/cs243/optimize/ or download them
from here. We provide:
ReferenceSolver.java. Note that the
Flow.Analysisinterface has changed a little bit, to include the result of test quads (e.g.
NullTests.java, an annotated source file for
FindChecksto optimize. Includes some truly ridiculous corner cases for the ambitious.
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]
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.
submit.shscript is available in the usr/class/cs243/optimize/submit.sh
usr/class/cs243/optimize/submit.sh foowhere foo is the Sunet ID of your partner.
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
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,
setSrc to complement
Actually modifying the ControlFlowGraph is trickier. You'll need to use
to construct the Basic Blocks, and the
addFoo routines in
itself to modify the lists of quads. Consult the joeq javadocs for full details
on these points.