Milestone 2: Points-To Analysis

Due: start of class on Wednesday Feb. 22

Task 1: Understand Java WIL (To be done individually)

Explain in your own words how Java objects are represented in WIL. To learn how Java is translated into WIL, take a look at the simple Java example in $VORTEX_HOME/Java/src/example/src. The WIL files generated for this example by the Java-to-WIL front-end are in $VORTEX_HOME/Java/src/example/wil (just take a look at the *.wil files in this directory).

Task 2: Implement points-to analysis and scalar replacement in Whirlwind (To be done in groups)

Requirements

You will implement a may-points-to analysis for Whirlwind. Your analysis should track, with reasonable precision, the set of pointers between local and non-local variables, dynamically allocated memory, members of records and objects, and array elements.  Your analysis should also replace a pointer dereference *p on the left- or right-hand-side of an assignment (i.e., in a TargetStoreNode or a TargetDerefNode) with a variable x (i.e., to a TargetVarAssnNode or a TargetIDExprNode)  whenever it is known that p definitely points to x.

Your analysis should compute at each program point a map from locations to sets of locations. A location represents one or more run-time memory locations. A mapping [l -> {l1, l2, l3}] says that the run-time memory location(s) represented by l may contain a pointer to l1, l2, or l3. There are several kinds of locations:

• Var(x) represents the unique memory location of variable x. (Each variable should be identified by its ValDeclNode.)
• AllocSummary(s) is a summary node: it represents all the heap memory blocks that have been allocated at allocation site s. (Each allocation site should be identified by its TargetAllocNode.
• Field(loc, name) represents the memory location for the member named name of the record(s) or object(s) represented by location loc. So, for example, Field(Var(x), n) represents the location of member n of variable x, which should hold a record or object. As another example, Field(AllocSummary(s), f) summarizes all the members named f of records or objects allocated at allocation site s.
• ArrayElemSummary(l) is another summary node, representing the memory locations of all elements of the array(s) represented by location l. So for example, ArrayElemSummary(Var(x)) represents the elements of the array variable x. As another example, Field(ArrayElemSummary(Var(x)), f) represents all the fields f of the array elements of x (this assumes that x is an array of records or objects that contain a field named f).

An example

The following example shows a simple program and the information your analysis should compute. Before looking at the example, there are a few things that you need to keep in mind about WIL:

• In WIL, the record selection operator (the dot operator) operates on pointers to records, not on records: given a pointer p to a record, p.f returns a pointer to the member f of the record pointed to by p. Thus, if x is a record (a struct in C) what in C you would write as x.f, in WIL you would write as *((&x).f). What in C you would write p->f, in WIL you would write *(p.f). Notice how in the example below pf3 points to member f3 of gs.
• In WIL, the array selection operator (the bracket operator) operates on pointers to arrays: given a pointer p to an array, p[i] returns a pointer to the ith array element of the array pointed to by p. Thus, if a is an array, what in C you would write as a[i], in WIL you would write as *((&a)[i]). Notice how in the example below, ppint points to the 5th element of array a.

Skeleton code

The $VORTEX_HOME/Diesel/src/whirlwind/optimizations/pts-to.diesel file contains an initial skeleton implementation of this points-to analysis.  You should define concrete subclasses of the abstract Location class for representing various kinds of locations, concrete subclasses of the abstract LocationSet class for representing a set of locations and supporting appropriate operations on sets of locations (perhaps along with named objects representing the top and/or bottom location sets), and concrete subclasses of the PtsTo abstract class for representing the points-to sets, i.e., mappings from locations to sets of locations (perhaps along with named objects representing the top and/or bottom points-to sets).  You also should fill in the implementations of the various functions and methods with "implement me" in their bodies.

The definitions of the TargetIRNodes manipulated in this analysis is in $VORTEX_HOME/Diesel/src/whirlwind/internal-rep/nodes/ir-node.diesel and ir-node-target.diesel.

By default, points-to analysis is disabled (since it's not implemented!).  You can enable it by default by changing the pts_to field's initial value to true, or by doing pts_to on at the Whirlwind> prompt, and then compiling with optimization on (e.g. using makeo1). You can also set the pts_to_msgs flag to a given level, e.g. pts_to_msgs 5, at the Whirlwind> prompt, to print out debugging information about points-to analysis. See the calls to cond_msg on options.pts_to_msgs to see the current debugging output, and feel free to add your own calls to help you monitor your analysis and transformation.

When running the compiler, you can call print_string on an object to see its "nice" string representation, and basic_print_string to see its low-level details. So, for example, if you have a TargetIDExprNode that represents a reference to variable y, then if you call print_string on it, you will get "y", and if you call basic_print_string, you will get the some string that tells you, among other things, that you're looking at a TargetIDExprNode.

Testing

Your points-to analysis should run successfully when compiling the existing WIL regression test file, test.wil.

You also should be able to run your optimization on the Java Towers-of-Hanoi benchmark.  You can do that by adding its location to Whirlwind's source paths (expand $VORTEX_HOME to its real value in the commands below) and then compiling towers.wil with optimization on:

Whirlwind> append source_paths $VORTEX_HOME/Java/src/example/wil $VORTEX_HOME/Java/wil-stdlib
...
Whirlwind> makeo1 towers.wil
...

You also should construct your own points-to test code, pts-to-test.wil, which exercises your analysis and optimization and shows off what it can do, and also that it doesn't do anything wrong in tricky situations.  Use comments in the test file to describe what should happen and not happen.

Deliverables

• Your explanation of Java WIL.
• Your modified pts-to.diesel file.
• Your pts-to-test.wil file.