Abstract
Interprocedural dataflow analysis has a large number of uses for software optimization, maintenance, testing, and verification. For software built with reusable components, the traditional approaches for whole-program analysis cannot be used directly. This paper considers component-level analysis of a main component which is built on top of a pre-existing library component. We propose an approach for computing summary information for the library and for using it to analyze the main component. The approach defines a general theoretical framework for dataflow analysis of programs built with large extensible library components, using pre-computed summary functions for library-local execution paths. Our experimental results indicate that the cost of component-level analysis could be substantially lower than the cost of the corresponding whole-program analysis, without any loss of precision. These results present a promising step towards practical analysis techniques for large-scale software systems built with reusable components.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Callahan, D.: The program summary graph and flow-sensitive interprocedural data flow analysis. In: Conf. Programming Language Design and Implementation, pp. 47–56 (1988)
Chatterjee, R., Ryder, B.G., Landi, W.: Relevant context inference. In: Symp. Principles of Programming Languages, pp. 133–146 (1999)
Cheng, B., Hwu, W.: Modular interprocedural pointer analysis using access paths. In: Conf. Programming Language Design and Implementation (2000)
Choi, J., Gupta, M., Serrano, M., Sreedhar, V., Midkiff, S.: Escape analysis for Java. In: Conf. Object-Oriented Programming Systems, Languages, and Applications, pp. 1–19 (1999)
Codish, M., Debray, S., Giacobazzi, R.: Compositional analysis of modular logic programs. In: Symp. Principles of Programming Languages, pp. 451–464 (1993)
Das, M.: Unification-based pointer analysis with directional assignments. In: Conf. Programming Language Design and Implementation, pp. 35–46 (2000)
Dhamdhere, D., Rosen, B., Zadeck, K.: How to analyze large programs efficiently and informatively. In: Conf. Programming Language Design and Implementation, pp. 212–223 (1992)
Flanagan, C., Felleisen, M.: Componential set-based analysis. ACM Trans. Programming Languages and Systems 21(2), 370–416 (1999)
Grove, D., Chambers, C.: A framework for call graph construction algorithms. ACM Trans. Programming Languages and Systems 23(6), 685–746 (2001)
Grove, D., Torczon, L.: Interprocedural constant propagation: a study of jump function implementation. In: Conf. Programming Language Design and Implementation, pp. 90–99 (1993)
Harrold, M.J., Rothermel, G.: Separate computation of alias information for reuse. IEEE Tran. Software Engineering 22(7), 442–460 (1996)
Heintze, N., Tardieu, O.: Ultra-fast aliasing analysis using CLA. In: Conf. Programming Language Design and Implementation, pp. 254–263 (2001)
Kuck, F.C.: Class analysis for extensible Java software. Master’s thesis, Ohio State University (September 2004)
Lee, Y.-F., Ryder, B.G.: A comprehensive approach to parallel data flow analysis. In: Int. Conf. Supercomputing, pp. 236–247 (1992)
Lhoták, O., Hendren, L.: Scaling Java Points-to Analysis Using SPARK. In: Hedin, G. (ed.) CC 2003. LNCS, vol. 2622, pp. 153–169. Springer, Heidelberg (2003)
Marlowe, T.J., Ryder, B.G.: An efficient hybrid algorithm for incremental data flow analysis. In: Symp. Principles of Programming Languages, pp. 184–196 (1990)
Milanova, A., Rountev, A., Ryder, B.G.: Precise call graphs for C programs with function pointers. Int. J. Automated Software Engineering 11(1), 7–26 (2004)
Reps, T., Horwitz, S., Sagiv, M.: Precise interprocedural dataflow analysis via graph reachability. In: Symp. Principles of Programming Languages, pp. 49–61 (1995)
Reps, T., Sagiv, M., Horwitz, S.: Interprocedural dataflow analysis via graph reachability. Technical Report TR 94-14, Datalogisk Institut, University of Copenhagen (April 1994)
Rountev, A.: Component-Level Dataflow Analysis. In: Heineman, G.T., Crnković, I., Schmidt, H.W., Stafford, J.A., Szyperski, C.A., Wallnau, K. (eds.) CBSE 2005. LNCS, vol. 3489, pp. 82–89. Springer, Heidelberg (2005)
Rountev, A., Connell, B.H.: Object naming analysis for reverse-engineered sequence diagrams. In: Int. Conf. Software Engineering, pp. 254–263 (2005)
Rountev, A., Kagan, S., Marlowe, T.: Interprocedural dataflow analysis in the presence of large libraries. Technical Report OSU-CISRC-1/06-TR01 (January 2006)
Rountev, A., Milanova, A., Ryder, B.G.: Fragment class analysis for testing of polymorphism in Java software. IEEE Tran. Software Engineering 30(6), 372–387 (2004)
Rountev, A., Ryder, B.G.: Points-to and Side-Effect Analyses for Programs Built with Precompiled Libraries. In: Wilhelm, R. (ed.) CC 2001. LNCS, vol. 2027, pp. 20–36. Springer, Heidelberg (2001)
Ruf, E.: Effective synchronization removal for Java. In: Conf. Programming Language Design and Implementation, pp. 208–218 (2000)
Ryder, B.G., Paull, M.C.: Elimination algorithms for data flow analysis. ACM Computing Surveys 18(3), 277–316 (1986)
Sagiv, M., Reps, T., Horwitz, S.: Precise interprocedural dataflow analysis with applications to constant propagation. Theoretical Comp. Sci. 167, 131–170 (1996)
Sharir, M., Pnueli, A.: Two approaches to interprocedural data flow analysis. In: Program Flow Analysis: Theory and Applications, pp. 189–234 (1981)
Tip, F., Sweeney, P., Laffra, C., Eisma, A., Streeter, D.: Practical extraction techniques for Java. ACM Trans. Programming Languages and Systems 24(6), 625–666 (2002)
Vallée-Rai, R., Gagnon, E., Hendren, L., Lam, P., Pominville, P., Sundaresan, V.: Optimizing Java bytecode using the Soot framework: Is it feasible? In: Watt, D.A. (ed.) CC 2000. LNCS, vol. 1781, pp. 18–34. Springer, Heidelberg (2000)
Whaley, J., Rinard, M.: Compositional pointer and escape analysis for Java programs. In: Conf. Object-Oriented Programming Systems, Languages, and Applications, pp. 187–206 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rountev, A., Kagan, S., Marlowe, T. (2006). Interprocedural Dataflow Analysis in the Presence of Large Libraries. In: Mycroft, A., Zeller, A. (eds) Compiler Construction. CC 2006. Lecture Notes in Computer Science, vol 3923. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11688839_2
Download citation
DOI: https://doi.org/10.1007/11688839_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33050-9
Online ISBN: 978-3-540-33051-6
eBook Packages: Computer ScienceComputer Science (R0)