New publication: Object representatives: a uniform abstraction for pointer information

Eric | August 5, 2008

And yes, we have yet another publication. This one has been accepted at BCS 2008. The conference promises to be an interesting event, as the British Computer Society managed to line up seven Turing Award winners to give keynote talks. Laurie Hendren, my supervisor, will be an invited speaker. Very unfortunately, I don’t think that I will be able to attend. So in case you go there, good for you and please try to speak with Patrick Lam instead, who will presenting the paper.

Anyway, so what are Object Representatives all about? Object Representatives are a sometimes very useful, uniform static abstraction of runtime objects that we came up with when evaluating tracematches ahead-of-time. At compile time, an Object Representative (OR) is just a plain old Java object that implements the interface below.

public interface ObjectRepresentative {
  public boolean mustAlias(ObjectRepresentative other);
  public boolean mustNotAlias(ObjectRepresentative other);
  public int hashCode();
  public boolean equals(Object obj);

As you can see, you can ask the question whether an OR must alias another OR (i.e. they both represent the same runtime object) or whether these ORs cannot alias (i.e. they definitely represent different objects). The cool and really useful thing is however the implementation of equals and hashCode. Both methods are implemented in such a way that two ORs are equal if and only if they represent the same runtime objects.

This crucial property allows programmers to substitute runtime objects directly with their respective Object Representatives at compile time. You can store ORs in indexing data structures like hash sets and maps and will automatically be guaranteed a sensible semantics.

When talking about must-aliasing we found out that it’s not at all obvious what must-aliasing actually means. Importantly, must-aliasing has a temporal component. Consider the following code…

void foo( Iterator i ) {
Collection c; Iterator j ; Object o;
while( i .hasNext()) {
  c = i .next ();
  j = c. iterator ();
  while ( j .hasNext()) {
    o = j .next ();
    /* use o somehow */
  } } }

As you can see, the variable j is redefined in the outer loop but not in the inner loop. Therefore, we can say that j must-aliases itself at line 7 when only taking the inner loop into account (in other words, j will always point to the same object in this case, regardless of the loop iteration). However when taking the execution of the entire method into account, then certainly j does not have to alias itself at line 7: in different iterations of the outer loop j will point to different objects. The definition of Object Representatives therefore includes a scope. This scope can be anything from a block of straight-line code over a loop, method, thread up to the entire program (that’s all we could think of; there may be other useful scopes). Must-aliasing is then always defined with respect to this scope.

Soot currently supports a prototype of ORs under the name of InstanceKey. We are currently in the process of refactoring the interface and making it available to the wide public.