[Back]

V. Pavlu, M Schordan, A. Krall:
"Computation of Alias Sets from Shape Graphs for Comparison of Shape Analysis Precision";
Talk: Eleventh IEEE International Workshop on Source Code Analysis and Manipulation (SCAM), Williamsburg, Virginia, USA; 2011-09-25 - 2011-09-26; in: "Proceedings of the Eleventh IEEE International Workshop on Source Code Analysis and Manipulation", IEEE, (2011), ISBN: 978-1-4577-0932-6; 25 - 34.

Shape analysis is a static pointer analysis technique that models heap-allocated data structures in greater detail than the typical pointer analysis does. To a compiler, this information is crucial for deciding wether two expressions refer to the same memory location, as a great number of analyses depend on this aliasing information.
Various shape analyses have been introduced but their relation in terms of precision often remains unclear as analyses cannot be compared directly due to different representations of analysis results.
The aim of this work is to make the precision of shape analysis results comparable. Our solution is based on extracting alias information from shape analysis results. We also propose a significant improvement in precision over an existing 3-valued logic based algorithm to compute alias sets from shape graphs.
Using this method we are able to compare the precision of graph-based shape analyses. We demonstrate our algorithm by comparing the precision of two classic examples of graph-based shape analyses, proposed by Sagiv, Reps & Wilhelm (SRW) and Nielson, Nielson & Hankin (NNH) which were implemented for C++ in the SATIrE program analysis framework. Comparison of the computed alias sets gives a measure of quality by which NNH is more precise than SRW shape analysis for each of our benchmarks.

pointer aliasing; shape analysis; pointer analysis; shape graph; alias set; precision;

http://publik.tuwien.ac.at/files/PubDat_203416.pdf

Project Head Andreas Krall:
Optimale Code Erzeugung für explizit parallele Prozessoren