Quantitative interprocedural analysis Journal Article


Author(s): Chatterjee, Krishnendu; Pavlogiannis, Andreas; Velner, Yaron
Article Title: Quantitative interprocedural analysis
Affiliation IST Austria
Abstract: We consider the quantitative analysis problem for interprocedural control-flow graphs (ICFGs). The input consists of an ICFG, a positive weight function that assigns every transition a positive integer-valued number, and a labelling of the transitions (events) as good, bad, and neutral events. The weight function assigns to each transition a numerical value that represents ameasure of how good or bad an event is. The quantitative analysis problem asks whether there is a run of the ICFG where the ratio of the sum of the numerical weights of good events versus the sum of weights of bad events in the long-run is at least a given threshold (or equivalently, to compute the maximal ratio among all valid paths in the ICFG). The quantitative analysis problem for ICFGs can be solved in polynomial time, and we present an efficient and practical algorithm for the problem. We show that several problems relevant for static program analysis, such as estimating the worst-case execution time of a program or the average energy consumption of a mobile application, can be modeled in our framework. We have implemented our algorithm as a tool in the Java Soot framework. We demonstrate the effectiveness of our approach with two case studies. First, we show that our framework provides a sound approach (no false positives) for the analysis of inefficiently-used containers. Second, we show that our approach can also be used for static profiling of programs which reasons about methods that are frequently invoked. Our experimental results show that our tool scales to relatively large benchmarks, and discovers relevant and useful information that can be used to optimize performance of the programs.
Keywords: Quantitative objectives; Interprocedural analysis; Mean-payoff and ratio objectives; Memory bloat; Static profiling
Journal Title: ACM SIGPLAN Notices
Volume: 50
Issue 1
ISSN: 1523-2867
Publisher: ACM  
Date Published: 2015-01-01
Start Page: 539
End Page: 551
URL:
DOI: 10.1145/2676726.2676968
Notes: We thank Mooly Sagiv for pointing us to reference, Nimrod Zibil for discussions on C optimizations, and anonymous reviewers for their helpful comments.
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work