Computation of alias sets from shape graphs for comparison of shape analysis precision

Various shape analyses have been introduced, but their precision often cannot be compared because they use different representations of analysis results. The aim of the authors work was to compare the precision of two well-known graph-based shape analyses, those presented by Sagiv, Reps and Wilhem (SRW); and by Nielson, Nielson and Hankin (NNH). Rather than comparing the shape graphs directly, their comparison uses alias information extracted from the graphs: for every pair (e₁, e₂) of pointer expressions in a programme, and for every programme point pt the authors determine the aliasing between e₁ and e₂. In their experiments, they use a new algorithm for extracting this alias information called the `common tails´ algorithm that is strictly more precise than the technique introduced by Reps, Sagiv and Wilhem (RSW). They present two interesting results: (i) they show that using their common tails algorithm, they are able to reduce the number of conservative results (strict may-aliases) by a factor of up to 5 (compared with the original RSW algorithm) while incurring an overhead of no more than 10% of analysis run-time. (ii) They show that NNH is more precise than SRW by a factor of 1.62 on average for their set of benchmarks.