Record Details

Efficiency, precision, simplicity, and generality in interprocedural data flow analysis : resurrecting the classical call strings method

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Efficiency, precision, simplicity, and generality in interprocedural data flow analysis : resurrecting the classical call strings method
 
Creator KHEDKER, UP
KARKARE, B
 
Description The full call strings method is the most general, simplest, and most precise method of performing context sensitive interprocedural data flow analysis. It remembers contexts using call strings. For full precision, all call strings up to a prescribed length must be constructed. Two limitations of this method are (a) it cannot be used for frameworks with infinite lattices, and (b) the prescribed length is quadratic in the size of the lattice resulting in an impractically large number of call strings. These limitations have resulted in a proliferation of ad hoc methods which compromise on generality, precision, or simplicity. We propose a variant of the classical full call strings method which reduces the number of call strings, and hence the analysis time, by orders of magnitude as corroborated by our empirical measurements. It reduces the worst case call string length from quadratic in the size of the lattice to linear. Further, unlike the classical method, this worst case length need not be reached. Our approach retains the precision, generality, and simplicity of call strings method without imposing any additional constraints. It can accommodate demand-driven approximations and hence can be used for frameworks with infinite lattices.
 
Publisher SPRINGER-VERLAG BERLIN
 
Date 2011-10-23T23:19:58Z
2011-12-15T09:11:18Z
2011-10-23T23:19:58Z
2011-12-15T09:11:18Z
2008
 
Type Proceedings Paper
 
Identifier COMPILER CONSTRUCTION,4959,213-228
978-3-540-78790-7
0302-9743
http://dspace.library.iitb.ac.in/xmlui/handle/10054/15265
http://hdl.handle.net/100/1985
 
Source 17th International Conference on Compiler Construction,Budapest, HUNGARY,MAR 29-APR 06, 2008
 
Language English