Infinite Call-String Sensitivity and Object Sensitivity are Incomparable

I just returned from a fantastic week at Dagstuhl, discussing the ins and outs of pointer analysis. I wanted to briefly write up one technical point regarding the comparability of call-string-sensitive and object-sensitive points-to analysis that seemed to not be as widely known as I had thought. For some background on terminology, etc., you can see Milanova et al., Lhoták and Hendren, Smaragdakis et al., or our recent book chapter (not an exhaustive list).

Milanova et al.'s original work on object sensitivity states:

In general, object sensitivity (an instance of the functional approach to context sensitivity [Sharir and Pnueli 1981]) and call chain context sensitivity (an instance of the call string approach) are incomparable in terms of precision.

But, no examples are given to illustrate this point. It's fairly clear how to construct examples showing that k-limited call strings can be more precise than k-limited object sensitivity, and vice versa. But, without k-limiting, i.e., with "infinite" call strings or object sensitivity (ignore recursion for the moment), the question of incomparability becomes a bit murkier. So, here are a couple of examples to show that incomparability holds even without k-limiting.

An example showing call strings to be more precise than object sensitivity isn't too tricky: (The comments name the objects being allocated or indicate the points-to relationships caused by the statement.) A call-string-sensitive analysis analyzes the calls at lines 10 and 11 separately, but an object-sensitive analysis does not, since both have the same receiver object a1. Hence, the object-sensitive analysis computes the imprecise points-to facts z -> o2 and w -> o1. Note that k-limiting plays no role here.

The example showing object sensitivity to be more precise is a bit trickier (and perhaps less widely known): Here, p is a boolean with some unknown value, so z can point to either a1 or a2. With object sensitivity, the call at line 12 is analyzed separately for receiver values a1 and a2, yielding the points-to facts shown. A call-string-sensitive analysis only analyzes the call once, and therefore computes the imprecise facts a1.f -> a2 and a2.f -> a1. Again, k-limiting plays no role. This example shows that object sensitivity is providing a form of path sensitivity that is truly orthogonal to the call-return matching obtained via call strings.

Note that both of these examples are contrived, and it's unclear whether this incomparability has any implications for analysis of real programs, since for the most part, only k-limited variants are used in practice. For an empirical evaluation of call strings vs. object contexts, see Lhoták and Hendren.

Anyway, hopefully this post has been useful in clarifying a small point regarding these analyses.