Abstract
This paper presents a new worklist algorithm that significantly speeds up a large class of flow-sensitive data-flow analyses, including typestate error checking and pointer analysis. Our algorithm works particularly well for interprocedural analyses. By contrast, traditional algorithms work well for individual procedures but do not scale well to interprocedural analysis because they spend too much time unnecessarily re-analyzing large parts of the program. Our algorithm solves this problem by exploiting the sparse nature of many analyses. The key to our approach is the use of interprocedural def-use chains, which allows our algorithm to re-analyze only those parts of the program that are affected by changes in the flow values. Unlike other techniques for sparse analysis, our algorithm does not rely on precomputed def-use chains, since this computation can itself require costly analysis, particularly in the presence of pointers. Instead, we compute def-use chains on the fly during the analysis, along with precise pointer information. When applied to large programs such as nn, our techniques improve analysis time by up to 90%—from 1974s to 190s—over a state of the art algorithm.
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
Aho, A.V., Ullman, J.D.: Node listings for reducible flow graphs. In: Proc. 7th Annual ACM Symp. on Theory of Computing, pp. 177–185 (1975)
Atkinson, D.C., Griswold, W.G.: Implementation techniques for efficient data-flow analysis of large programs. In: Proc. IEEE Int’l Conf. on Software Maintenance (ICSM 2001), November 2001, pp. 52–61 (2001)
Choi, J., Burke, M., Carini, P.: Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In: POPL, pp. 232–245 (1993)
Choi, J., Cytron, R., Ferrante, J.: Automatic construction of sparse data flow evaluation graphs. In: POPL, pp. 55–66 (1991)
Cobleigh, J.M., Clarke, L.A., Osterweil, L.J.: The right algorithm at the right time: comparing data flow analysis algorithms for finite state verification. In: Int’l Conf. on Software Engineering, pp. 37–46 (May 2001)
Foster, J.S., Terauchi, T., Aiken, A.: Flow-sensitive type qualifiers. In: ACM SIGPLAN 2002 Proc. 2002 PLDI, pp. 1–12 (June 2002)
Guyer, S.Z., Lin, C.: Client driven pointer analysis. In: Cousot, R. (ed.) SAS 2003. LNCS, vol. 2694, pp. 214–236. Springer, Heidelberg (2003)
Guyer, S.Z., Lin, C.: An annotation language for optimizing software libraries. In: 2nd Conf. on Domain Specific Languages, pp. 39–53 (October 1999)
Hind, M., Pioli, A.: Which pointer analysis should I use? In: ACM SIGSOFT Int’l Symp. on Software Testing and Analysis (ISSTA 2000), pp. 113–123 (August 2000)
Hind, M., Pioli, A.: Assessing the Effects of Flow-Sensitivity on Pointer Alias Analyses. In: Levi, G. (ed.) SAS 1998. LNCS, vol. 1503, pp. 57–81. Springer, Heidelberg (1998)
Horwitz, S., Reps, T., Sagiv, M.: Demand interprocedural dataflow analysis. In: ACM 3rd Symp. on the Foundations of Software Engineering, pp. 104–115 (1995)
Hecht, M.S., Ullman, J.D.: Analysis of a simple algorithm for global data flow problems. In: POPL, pp. 207–217 (1973)
Kennedy, K.W.: Node listings applied to data flow analysis. In: Proc. 2th ACM Symp. on Principles of Programming Languages, pp. 10–21 (1975)
Kam, J.B., Ullman, J.D.: Global Data Flow Analysis and Iterative Algorithms. Journal of ACM 23(1), 158–171 (1976)
Moon, S., et al.: SYZYGY — a framework for scalable cross-module IPO. In: 2004 Int’l Symp. on Code Generation and Optimization with Special Emphasis on Feedback-Directed and Runtime Optimization, pp. 65–74 (March 2004)
Myers, E.M.: A precise inter-procedural data flow algorithm. In: Proc. 8th ACM Symp. on Principles of Programming Languages, January 1981, pp. 219–230 (1981)
Ramalingam, G.: On sparse evaluation representations. Research Report RC 21245(94831), IBM Research (July 1998)
Ryder, B.G., Landi, W.A., Stocks, P.A., Zhang, S., Altucher, R.: A schema for interprocedural modification side-effect analysis with pointer aliasing. ACM Transactions on Programming Languages and Systems 23(1), 105–186 (2001)
Rountev, A., Ryder, B.G., Landi, W.A.: Data-flow Analysis of Program Fragments. In: Proc. 7th Symposium on the Foundations of Software Engineering, pp. 235–253 (September 1999)
Ruf, E.: Partitioning dataflow analyses using types. In: Proc. 24th ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, pp. 15–26 (January 1997)
Ryder, B.G., Paull, M.C.: Elimination algorithms for data flow analysis. ACM Computing Surveys (CSUR) 18(3), 277–316 (1986)
Tip, F.: A survey of program slicing techniques. Journal of Programming Languages 3 (1995)
Wegman, M.N., Zadeck, F.K.: Constant propagation with conditional branches. ACM Transactions on Programming Languages and Systems 13(2), 181–210 (1991)
Whaley, J., Lam, M.S.: Cloning-Based Context-Sensitive Pointer Alias Analyses Using Binary Decision Diagrams. In: ACM SIGPLAN 2004 Proc. 2004 PLDI, pp. 131–144 (June 2004)
Zhu, J., Calman, S.: Symbolic Pointer Analysis Revisited. In: ACM SIGPLAN 2004 Proc. 2004 PLDI, pp. 145–157 (June 2004)
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
Tok, T.B., Guyer, S.Z., Lin, C. (2006). Efficient Flow-Sensitive Interprocedural Data-Flow Analysis in the Presence of Pointers. 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_3
Download citation
DOI: https://doi.org/10.1007/11688839_3
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)