Abstract
Large programs are typically built from separate modules. Traditional whole-program analysis cannot be used in the context of such modular development. In this paper we consider analysis for programs that combine client modules with precompiled library modules.We define separate analyses that allow library modules and client modules to be analyzed separately from each other. Our target analyses are Andersen’s points-to analysis for C [1] and a side-effect analysis based on it. We perform separate points-to and side-effect analyses of a library module by using worst-case assumptions about the rest of the program. We also show how to construct summary information about a library module and how to use it for separate analysis of client modules. Our empirical results show that the separate points-to analyses are practical even for large modules, and that the cost of constructing and storing library summaries is low. This work is a step toward incorporating practical points-to and side-effect analyses in realistic compilers and software productivity tools.
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
L. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen, 1994.
R. Chatterjee, B. G. Ryder, and W. Landi. Relevant context inference. In Symposium on Principles of Programming Languages, pages 133–146, 1999.
B. Cheng and W. Hwu. Modular interprocedural pointer analysis using access paths. In Conference on Programming Language Design and Implementation, pages 57–69, 2000.
J. Choi, M. Gupta, M. Serrano, V. Sreedhar, and S. Midkiff. Escape analysis for Java. In Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 1–19, 1999.
M. Das. Unification-based pointer analysis with directional assignments. In Conference on Programming Language Design and Implementation, pages 35–46, 2000.
M. Fahndrich, J. Foster, Z. Su, and A. Aiken. Partial online cycle elimination in inclusion constraint graphs. In Conference on Programming Language Design and Implementation, pages 85–96, 1998.
C. Flanagan and M. Felleisen. Componential set-based analysis. ACM Trans. Programming Languages and Systems, 21(2):370–416, Mar. 1999.
S. Guyer and C. Lin. Optimizing the use of high performance software libraries. In Workshop on Languages and Compilers for Parallel Computing, 2000.
M. J. Harrold and G. Rothermel. Separate computation of alias information for reuse. IEEE Trans. Software Engineering, 22(7):442–460, July 1996.
M. Hind and A. Pioli. Which pointer analysis should I use? In International Symposium on Software Testing and Analysis, pages 113–123, 2000.
A. Rountev and S. Chandra. Off-line variable substitution for scaling points-to analysis. In Conference on Programming Language Design and Implementation, pages 47–56, 2000.
A. Rountev and B. G. Ryder. Points-to and side-effect analyses for programs built with precompiled libraries. Technical Report 423, Rutgers University, Oct. 2000.
A. Rountev and B. G. Ryder. Practical points-to analysis for programs built with libraries. Technical Report 410, Rutgers University, Feb. 2000.
A. Rountev, B. G. Ryder, and W. Landi. Data-flow analysis of program fragments. In Symposium on the Foundations of Software Engineering, LNCS 1687, 1999.
B. G. Ryder, W. Landi, P. Stocks, S. Zhang, and R. Altucher. A schema for interprocedural side effect analysis with pointer aliasing. Technical Report 336, Rutgers University, May 1998. To appear in ACM TOPLAS.
M. Shapiro and S. Horwitz. The effects of the precision of pointer analysis. In Static Analysis Symposium, LNCS 1302, pages 16–34, 1997.
M. Shapiro and S. Horwitz. Fast and accurate flow-insensitive points-to analysis. In Symposium on Principles of Programming Languages, pages 1–14, 1997.
B. Steensgaard. Points-to analysis in almost linear time. In Symposium on Principles of Programming Languages, pages 32–41, 1996.
P. Sweeney and F. Tip. Extracting library-based object-oriented applications. In Symposium on the Foundations of Software Engineering, pages 98–107, 2000.
J. Whaley and M. Rinard. Compositional pointer and escape analysis for Java programs. In Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 187–206, 1999.
S. Zhang, B. G. Ryder, and W. Landi. Program decomposition for pointer aliasing: A step towards practical analyses. In Symposium on the Foundations of Software Engineering, pages 81–92, 1996.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rountev, A., Ryder, B.G. (2001). Points-to and Side-Effect Analyses for Programs Built with Precompiled Libraries. In: Wilhelm, R. (eds) Compiler Construction. CC 2001. Lecture Notes in Computer Science, vol 2027. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45306-7_3
Download citation
DOI: https://doi.org/10.1007/3-540-45306-7_3
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41861-0
Online ISBN: 978-3-540-45306-2
eBook Packages: Springer Book Archive