Conference item
A correspondence between two approaches to interprocedural analysis in the presence of join
- Abstract:
- Many interprocedural static analyses perform a lossy join for reasons of termination or efficiency. We study the relationship between two predominant approaches to interprocedural analysis, the summary- based (or functional) approach and the call-strings (or k-CFA) approach, in the presence of a lossy join. Despite the use of radically different ways to distinguish procedure contexts by these two approaches, we prove that post-processing their results using a form of garbage collection ren- ders them equivalent. Our result extends the classic result by Sharir and Pnueli that showed the equivalence between these two approaches in the setting of distributive analysis, wherein the join is lossless. We also empirically compare these two approaches by applying them to a pointer analysis that performs a lossy join. Our experiments on ten Java programs of size 400K{900K bytecodes show that the summary-based approach outperforms an optimized implementation of the k-CFA approach: the k-CFA implementation does not scale beyond k=2, while the summary-based approach proves up to 46% more pointer analysis client queries than 2-CFA. The summary-based approach thus enables, via our equivalence result, to measure the precision of k-CFA with unbounded k, for the class of interprocedural analyses that perform a lossy join.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 478.1KB, Terms of use)
-
- Publisher copy:
- 10.1007/978-3-642-54833-8_27
Authors
- Publisher:
- Springer
- Host title:
- Programming Languages and Systems: 23rd European Symposium on Programming, ESOP 2014, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2014, Grenoble, France, April 5-13, 2014, Proceedings. Editor: Zhong Shao
- Volume:
- Lecture Notes in Computer Science: 8410
- Pages:
- 513-533
- Publication date:
- 2014-01-01
- DOI:
- ISSN:
-
0302-9743
- ISBN:
- 9783642548338
- Keywords:
- Pubs id:
-
pubs:581047
- UUID:
-
uuid:e91ec8d6-31f5-4c98-a4c0-01752c504df3
- Local pid:
-
pubs:581047
- Source identifiers:
-
581047
- Deposit date:
-
2016-01-03
- ARK identifier:
Terms of use
- Copyright holder:
- Springer
- Copyright date:
- 2014
- Notes:
- © Springer-Verlag Berlin Heidelberg 2014. This is the author accepted manuscript following peer review version of the article. The final version is available online from Springer at: dx.doi.org/10.1007/978-3-642-54833-8_27
If you are the owner of this record, you can report an update to it here: Report update to this record