Quantitative Interprocedural Analysis

Chatterjee, Krishnendu and Pavlogiannis, Andreas and Velner, Yaron (2016) Quantitative Interprocedural Analysis. Technical Report. IST Austria.

[img] Text
main.pdf - Published Version
Available under License All rights reserved.
[IST-2016-523-v1+1]
Download (881Kb)

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.

Item Type: Monograph (Technical Report)
Additional Information: A short version of this technical report is available at http://dx.doi.org/10.1145/2676726.2676968
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems
000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 005 Computer programming, programs & data
Research Group: Chatterjee Group
Depositing User: Andreas Pavlogiannis
Date Deposited: 01 Apr 2016 06:31
Last Modified: 17 Jun 2019 14:41
URI: https://repository.ist.ac.at/id/eprint/523

Actions (login required)

View Item View Item