Programming Assignment 5
A5: Context-Insensitive Pointer Analysis
1 Assignment Objectives
- Implement a context-insensitive pointer analysis for Java.
- Implement on-the-fly call graph construction as part of pointer analysis.
In this programming assignment, you will implement a context-insensitive pointer analysis for Java on top of Tai-e. This pointer analysis builds a call graph on the fly. If your implementation is correct, you can observe that pointer analysis can build more precise call graphs than class hierarchy analysis (CHA) as described later.
In this assignment, we will teach you how to handle the Java features that are not covered in the lectures, i.e., static field, array, and static method, so that you will implement a pointer analysis that can handle all kinds of pointers in Java.
2 Implementing Pointer Analysis
You will implement the context-insensitive pointer analysis algorithm introduced in Lectures 9 and 10, in which the algorithm handles two kinds of pointers, i.e., local variables and instance fields, as well as instance method calls. To achieve a more practical pointer analysis, you will handle the other two kinds of pointers, i.e., static fields and array indexes, as well as static method calls in this assignment. We will introduce the analysis rules to handle these features in Section 2.2. These rules are very similar to (or even simpler than) the rules you have learnt in lectures, and you need to figure out how to implement them based on the pointer analysis algorithm.
2.2 New Rules
In this section, we introduce new pointer analysis rules to handle static fields, array indexes, and static method calls.
Static Fields. The handling of static fields is simple, i.e., we just need to pass values between the static field and the variable. We use
T.f, and then define the rules to handle static field stores and loads as follows:
Array Indexes. As explained in page 86 of the slides for Lecture 8, regular pointer analysis does not distinguish between loads and stores to different array indexes (locations). Suppose that
Static Methods. The handing of static methods is the same as that of instance methods, except that 1) we do not need to dispatch on the receiver object to resolve the callee, and 2) we do not need to pass the receiver object. Since static method calls do not require receiver object, its treatment is simpler than that of instance method calls as shown below:
2.3 Tai-e Classes You Need to Know
In this section, we first introduce the IR-related classes (
pascal.taie.ir.*) and then the pointer-analysis-related classes (
pascal.taie.analysis.pta.*) that you need to know to finish this assignment.
You have seen this class in previous assignments. It represents all definition statements in the program, e.g.,
x = yand
x = m(…). All pointer-affecting statements that you need to handle in this assignment are subclasses of this class, as shown in the figure below (you will handle the classes in red boxes).
These classes are simple, and you could get familiar with them by reading the source code and comments. Note that
Invokerepresents both instance method calls and static method calls as you have seen in Assignment 4, and you can use its
isStatic()method to check if the
Invokestatement is a static or instance call. Similarly,
StoreFieldrepresent loads and stores of both instance and static fields. These two classes also provide
isStatic()method to check if a
LoadField/StoreFieldstatement loads/stores a static or instance field.
You have seen this class before, which represents the variables in Tai-e’s IR. If a variable is the base variable of any instance field loads/stores, array loads/stores, or instance calls, then this class provides convenient APIs to find the relevant statements. For example, suppose we are analyzing the following code snippet:
x = y; x.h = a; x.g = z; a = x.f; b = y.f; c = x.m(); d[i] = c; e = d[i];
var.getStoreFields()returns the field store statements at lines 2 and 3,
var.getLoadFields()returns the field load statement at line 4, and
var.getInvokes()returns the instance call at line 6; if
var.getStoreArrays()returns the array store statement at line 7, and
var.getLoadArrays()returns the array load statement at line 8.
These APIs ease the implementation of pointer analysis, and we strongly recommend you to use them in this assignment. You could read the source code and comments in class
Varfor more information.
This class represents fields in the program.
Below we introduce pointer-analysis-related classes. These classes are generally simple, and you should read their source code and comments to decide how to use them.
This class represents abstract objects in pointer analysis, i.e., the objects in points-to sets.
This class represents heap models (i.e., heap abstraction) for heap objects. You can use its
getObj(New)method to obtain the abstract object (i.e.,
Obj) for given
Newstatement (i.e., allocation site). We adopt allocation-site abstraction as introduced in page 44 of the slides for Lecture 8, thus this method returns a unique abstract object for each
This class represents points-to sets, i.e., sets of
Objin pointer analysis. It is iterable, i.e., you could iterate the objects in a points-to set via a for loop:
PointsToSet pts = ...; for (Obj obj : pts) ...
This class represents the pointers in the analysis, i.e., the nodes in the PFG (pointer flow graph). Each
Pointeris associated with a
PointsToSet, which can be obtained by calling
getPointsToSet(). This class has four subclasses:
which corresponds to the four kinds of pointers in Java as introduced in page 82 of slides for Lecture 8.
This class represents a pointer flow graph of the program. It also maintains the mappings from variables / static fields / instance fields / array indexes to corresponding pointers (i.e., PFG nodes), and thus you can obtain various
Pointersfrom APIs of this class.
This class represents the worklist in pointer analysis algorithm. It has an inner record class Entry which represents the entries in the worklist.
This class implements a context-insensitive pointer analysis solver. It is incomplete, and you need to finish it as explained in Section 2.4.
In addition to the above classes, you also need to know classes
Edge. Since these classes have been introduced in the previous assignment, we do not detail them here.
2.4 Your Task [Important!]
Your task is to finish class
Solver. We have initialized work list, pointer flow graph, and call graph in
Solver.initialize(), and stored them in
callGraph, so that you can manipulate them. When you build call graph, you can use the APIs of
DefaultCallGraph introduced in the previous assignment to modify the call graph. You need to finish the main part of the pointer analysis algorithm. Specifically, you will finish the following five APIs:
This method implements the
AddReachablefunction given in page 119 of the slides for Lecture 10.
This method implements the
AddEdgefunction given in page 43 of the slides for Lecture 9.
This method implements the main part, i.e., the while loop, of the
Solvefunction given in page 125 of the slides for Lecture 10.
This method merges two steps of the algorithm. It first computes the difference set (
), then propagates into as described by the
Propagatefunction in page 43 of the slides for Lecture 9. It returns
as the result of the call.
This method implements the
ProcessCallfunction given in page 124 of the slides for Lecture 10.
We have provided code skeletons for the above APIs, and your task is to fill in the part with comment "
TODO – finish me".
3 Run and Test Your Implementation
You can run the analysis as described in Set Up Tai-e Assignments. In this assignment, Tai-e performs context-insensitive pointer analysis for the program, and outputs the points-to sets of all kinds of pointers and the resulting call graph:
The points-to sets and call graph are empty as you have not finished the analysis yet. After you implement the analysis, the output should look like:
In addition, Tai-e outputs the IRs for the classes of the program it analyzes to folder
output/. The IRs are stored as
.tir files which can be opened by general text editors.
We provide test driver
pascal.taie.analysis.pta.CIPTATest for this assignment, and you could use it to test your implementation.
We encourage you to use your implementation of Assignment 4, i.e., CHA-based call graph builder, to analyze the test cases in this assignment (e.g.,
Example.java), and observe the precision differences on the resulting call graphs constructed by CHA and pointer analysis.
4 General Requirements
In this assignment, your only goal is correctness. Efficiency is not your concern.
DO NOT distribute the assignment package to any others.
Last but not least, DO NOT plagiarize. The work must be all your own!
5 Submission of Assignment
Your submission should be a zip file, which contains your implementation of
You can refer to Grade Your Programming Assignments to use our online judge to grade your completed assignments.
The points will be allocated for correctness. We will use your submission to analyze the given test files from the
src/test/resources/ directory, as well as other tests of our own, and compare your output to that of our solution.