Open AccessComputation of alias sets from shape graphs for comparison of shape analysis precision
Author(s) -
Pavlu Viktor,
Schordan Markus,
Krall Andreas
Publication year - 2014
Publication title -
iet software
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.305
H-Index - 43
eISSN - 1751-8814
pISSN - 1751-8806
DOI - 10.1049/iet-sen.2012.0049
Subject(s) - alias , aliasing , computer science , algorithm , computation , overhead (engineering) , graph , set (abstract data type) , pointer (user interface) , spurious relationship , theoretical computer science , data mining , artificial intelligence , programming language , machine learning , undersampling
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 1 , e 2 ) of pointer expressions in a programme, and for every programme point pt the authors determine the aliasing between e 1 and e 2 . 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.