Prof. Dr. Eric Bodden

Authors: Eric Bodden, Patrick Lam and Laurie Hendren
Date: September 2007
Abstract
Pointer analyses enable many subsequent program analyses and transformations, since they enable compilers to statically disambiguate references to the heap. Extra precision enables pointer analysis clients to draw stronger conclusions about programs. Flow-sensitive pointer analyses are typically quite precise. Unfortunately, flow-sensitive pointer analyses are also often too expensive to run on whole programs. This paper therefore describes a technique which sharpens results from a whole-program flow-insensitive points-to analysis using two flow-sensitive intraprocedural analyses: a must-not-alias analysis and a must-alias analysis. The main technical idea is the notion of instance keys, which enable client analyses to disambiguate object references. We distinguish two kinds of keys: weak and strong. Strong instance keys guarantee that different keys represent different runtime objects, allowing instance keys to almost transparently substitute for runtime objects in static analyses. Weak instance keys may represent multiple runtime objects, but still enable disambiguation of compile-time values. We assign instance keys based on the results of our analyses. We found that the use of instance keys greatly simplified the design and implementation of subsequent analysis phases.

available here for download

It’s done. OOPSLA is over. I have to say, first I was skeptical about this year’s OOPSLA edition because there were so many tracks going on at the same time. However, one has to admit that in general there was a lot of interesting and funky stuff going on (and the research track was not always the most interesting one). So maybe it’s a good thing to have that variety after all. It’s hard to say, but anyway I had a good week with lots of fruitful discussions. As I understand, some videos of the most important keynotes and other stuff will be available on the OOPSLA or R.P. Gabriel’s website shortly.

Michael Bond presented an interesting approach to tracking the origin of unusable values such as null today at OOPSLA. His team uses a piggybacking approach, which makes this task very efficient. Instead of storing null when null is assigned, they store some special data structure encoding the location at which this assignment occurs. If then a nullpointer exception happens later on, they are able to report that location. Runtime overheads for their java-based approach (based on modifications to the Jikes RVM) was about 4% in average only.