CSSE4630 Week 8 Lab: Steensgaard¡¯s Pointer Analysis
Mark Utting Version 1.0
1 Introduction
This workshop is focussed on Pointer Analysis. In the second part of this workshop, please also continue working on your assignment and asking questions about it.
2 Implementing Steensgaard¡¯s Algorithm
The TIP system does not fully implement Steensgaard¡¯s pointer analysis algorithm yet. To see this, run the following command and read the exception it generates:
tip -steensgaard examples/ptr7.tip
Implement the five missing cases in the visit method in SteensgaardAnalysis. See page 116
of the textbook for the rules you should implement. Hints:
3
1. The solver is already created for you, so you can just call its unify method.
2. The address-of constructor in the textbook (&X corresponds to PointerRef( ) in the
Scala code (down the bottom of the file).
3. You should use the identifierToTerm method to convert an identifier into an abstract term that represents a set of pointers, and allocToTerm to turn an ¡®alloc¡¯ expression into an abstract term.
4. The first three cases can be implemented with a single line of code, but the last two cases will require about 3 lines of code, as you must allocate a fresh variable (called ¦Á in the textbook) using FreshVariable() and then use it.
Evaluating Pointer Analysis
Use your Steensgaard algorithm to analyse the examples/ptr7.tip program. You should see standard output being printed that includes the following results:
[info] Points-to:
c1:3:25 -> { d1:3:33,d2:3:37 } b1:3:17 -> { c1:3:25,c2:3:29 } a2:3:13 -> { b2:3:21 }
d1:3:33 -> { }
a1:3:9 -> { b1:3:17 }
b2:3:21 -> { c1:3:25,c2:3:29 } d2:3:37 -> { }
c2:3:29 -> { d1:3:33,d2:3:37 }
CSSE4630
Week 8 Lab
Page 1
Here is a nice visualisation of these results, from Slide 18 from the Week 8 lectures. Note how Steensgaard¡¯s analysis merges the c1 and c2 into one set, and therefore must also merge d1 and d2 into one set. It is less precise than the Andersen algorithm, but much faster.
4 Working on your Static Analysis Assignment
Please use the rest of this workshop to work on your assignment, and ask your tutor any questions that you have about it.
CSSE4630 Week 8 Lab Page 2