Universität Stuttgart

Permanent URI for this communityhttps://elib.uni-stuttgart.de/handle/11682/1

Browse

Filters

2007 - 20092

Settings

Institute: search.filters.UBSInstitut.Institut für SoftwaretechnologiePublication Type: search.filters.UBSTyp.Arbeitspapier

Search Results

Now showing 1 - 2 of 2
  • Thumbnail Image
    ItemOpen Access
    Interprocedural static single assignment form in Bauhaus
    (2007) Staiger, Stefan; Vogel, Gunther; Keul, Steffen; Wiebe, Eduard
    In this paper we describe interprocedural static single assignment form (ISSA) with optimizations as implemented in the Bauhaus project. We explain our framework which uses an abstract program representation enabling us to use different pointer analyses ranging from fast but imprecise to slow but precise ones. Our implementation includes the computation of (may and must) side effects and optimizations like pruning definitions with simple linear-time algorithms. This paper also provides comprehensive test results and statistics for a large test suite.
  • Thumbnail Image
    ItemOpen Access
    Implementing sparse flow-sensitive Andersen analysis
    (2009) Staiger-Stöhr, Stefan
    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.