Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-2645
Full metadata record
DC FieldValueLanguage
dc.contributor.authorStaiger-Stöhr, Stefande
dc.date.accessioned2009-04-23de
dc.date.accessioned2016-03-31T07:58:50Z-
dc.date.available2009-04-23de
dc.date.available2016-03-31T07:58:50Z-
dc.date.issued2009de
dc.identifier.other31409699Xde
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:bsz:93-opus-39604de
dc.identifier.urihttp://elib.uni-stuttgart.de/handle/11682/2662-
dc.identifier.urihttp://dx.doi.org/10.18419/opus-2645-
dc.description.abstractAndersen'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.en
dc.language.isoende
dc.relation.ispartofseriesTechnischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;2009,3de
dc.rightsinfo:eu-repo/semantics/openAccessde
dc.subject.classificationDatenflussde
dc.subject.ddc004de
dc.subject.otherpointer analysisen
dc.titleImplementing sparse flow-sensitive Andersen analysisen
dc.typeworkingPaperde
dc.date.updated2013-07-15de
ubs.fakultaetFakultät Informatik, Elektrotechnik und Informationstechnikde
ubs.institutInstitut für Softwaretechnologiede
ubs.opusid3960de
ubs.publikation.typArbeitspapierde
ubs.schriftenreihe.nameTechnischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnikde
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.