Interprocedural Data Flow Analysis: Resurrecting the Classical Call Strings Method

Add to your list(s) Download to your calendar using vCal

• Uday Khedker ( IIT Bombay)
• Tuesday 17 May 2011, 14:30-15:30
• GS15, Computer Laboratory.

If you have a question about this talk, please contact Alan Mycroft.

Another unusual date/time...

Context sensitive interprocedural data flow analysis requires incorporating the effect of all possible calling contexts on the data flow information at a program point. The call strings approach, which represents context information in the form of a call string, bounds the contexts by terminating the call string construction using precomputed length bounds. These bounds are large enough to guarantee a safe and precise solution, but usually result in a large number of call strings, thereby rendering the method impractical.

We propose a simple change in the classical call strings method. Unlike the traditional approach in which call string construction is orthogonal to the computation of data flow values, our variant uses the equivalence of data flow values for termination of call string construction. This allows us to discard call strings where they are redundant and regenerate them when required. For the cyclic call strings, regeneration facilitates iterative computation of data flow values without explicitly constructing most of the call strings. This reduces the number of call strings, and hence the analysis time, by orders of magnitude as corroborated by our empirical measurements.

On the theoretical side, our method reduces the worst case call string length from quadratic in the size of lattice to linear. Further, unlike the classical method, this worst case length need not be reached since termination does not depend on constructing all call strings up to this length. Our approach retains the precision, generality, and simplicity of the call strings method and simultaneously reduces the complexity and increases efficiency significantly without imposing any additional constraints.

Reference: Uday P. Khedker and Bageshri Karkare. Efficiency, Precision, Simplicity, and Generality in Interprocedural Data Flow Analysis: Resurrecting the Classical Call Strings Method. International Conference on Compiler Construction (CC 2008), Hungary.

This talk is part of the Computer Laboratory Programming Research Group Seminar series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory Programming Research Group Seminar
• Department of Computer Science and Technology talks and seminars
• GS15, Computer Laboratory
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.