Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-2645
Authors: Staiger-Stöhr, Stefan
Title: Implementing sparse flow-sensitive Andersen analysis
Issue Date: 2009
metadata.ubs.publikation.typ: Arbeitspapier
Series/Report no.: Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;2009,3
URI: http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-39604
http://elib.uni-stuttgart.de/handle/11682/2662
http://dx.doi.org/10.18419/opus-2645
Abstract: Andersen's analysis is the most influential pointer analysis known so far. This paper, which contains parts of the author's upcoming PhD thesis, for the first time presents a flow-sensitive version of that analysis. We prove that the flow-sensitive version still has the same cubic complexity. Thus, the higher precision comes without loss of asymptotic scalability. This contradicts common wisdom of flow-sensitivity being substantially more expensive. Compared to other flow-sensitive pointer analyses, we have no expensive data-flow problem on the CFG. Instead, we simply propagate pointer targets along data-flow relations which we determine during the analysis. Our analysis in fact combines the computation of the interprocedural SSA data-flow representation and the uncovering of pointer targets. It also integrates the computation of control-flow relations. The analysis thus presents a new, sparse approach for the flow-sensitive solution of the central problems for data-flow based program analyses. This paper also presents two extensions for higher precision. The first extension shows how the analysis can detect strong updates without increasing the complexity. The second extension describes a context-sensitive version which excludes unrealizable paths. Together this yields the first analysis of that precision which only has a complexity of n^4. This is a substantial improvement over the previous n^6 bound found by Landi. Thus, in summary this report describes several theoretical advances in the field of flow-sensitive pointer analysis. It also provides details on the algorithms used for incremental SSA construction and context-sensitive pointer propagation.
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
TR_2009_03.pdf282,61 kBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.