CS243 Assignment 4

Redundant Null Check Elimination

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.

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:

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:

What to turn in


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.