Abstract
This paper considers the complexity of interprocedural function pointer may-alias analysis, i.e., determining the set of functions that a function pointer (in a language such as C) can point to at a point in a program. This information is necessary, for example, in order to construct the control flow graphs of programs that use function pointers, which in turn is fundamental for most dataflow analyses and optimizations. We show that the general problem is complete for deterministic exponential time. We then consider two natural simplifications to the basic (precise) analysis and examine their complexity. The approach described can be used to readily obtain similar complexity results for related analyses such as reachability and recursiveness.
This work was supported in part by NSF grant number CCR-9502826.
Chapter PDF
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
A. Aho, R. Sethi, and J. Ullman. Compilers. principles, techniques, and tools. Addison-Wesley, 1986.
D. Callahan, A. Carle, M. Hall, and K. Kennedy. Constructing the procedure call multigraph. IEEE Trans. on Softw. Eng., 16(4):483, April 1990.
J. Choi, M. Burke, and P. Carini. Efficient Flow-Sensitive Interprocedural Computation of Pointer-Induced Aliases and Side Effects. Proc. 20th. ACM Symp. on Principles of Programming Languages, Jan. 1993, pp. 232–245.
P. Hudak and J. Young. Higher-order strictness analysis in untyped lambda calculus. In Proc. 13th ACM Symp. on Principles of Programming Languages, pages 97–109, St. Petersburg Beach, Florida, January 1986.
N. Jones and S. Muchnick. Complexity of flow analysis, inductive assertion synthesis, and a language due to Dijkstra. In Steven S Muchnick and Neil D Jones, editors, Program Flow Analysis: Theory and Applications, chapter 12, pages 380–393. Prentice-Hall, 1981.
N. Jones and A. Mycroft. Data flow analysis of applicative programs using minimal function graphs: abridged version. In Proc. 13th ACM Symp. on Principles of Programming Languages, pages 296–306, St. Petersburg, FL, January 1986.
A. Lakhotia. Constructing call multigraphs using dependence graphs. In Proc. 20th ACM Symp. on Principles of Programming Languages, pages 273–284, Charleston, South Carolina, January 1993.
W. Landi and B. Ryder. A safe approximate algorithm for interprocedural pointer aliasing. SIGPLAN Notices, 27(7):235–248, July 1992. Proc. of the ACM SIGPLAN '92 Conf. on Programming Language Design and Implementation.
W. Landi, B. Ryder, and S. Zhang. Interprocedural side effect analysis with pointer aliasing. SIGPLAN Notices, 28(6):56–67, June 1993. Proc. of the ACM SIGPLAN '93 Conf. on Programming Language Design and Implementation.
R. Muth and S. Debray. On the complexity of function pointer may-alias analysis. Technical Report 96-18, Dept. of Computer Science, The University of Arizona, Tucson, USA. October 1996.
B. Ryder. Constructing the call graph of a program. IEEE Transaction of Software Engineering, SE-5(3):216–226, 1979.
O. Shivers. Control-Flow Analysis of Higher-Order Languages or Taming Lambda. PhD thesis, Carnige-Mellon Univeristy, May 1991. Also available as CMU-CS-91-145.
R. Wilson and M. Lam, Efficient Context-Sensitive Pointer Analysis for C Programs. Proc. SIGPLAN '95 Conference on Programming Language Design and Implementation, June 1995, pp. 1–12.
S. Zhang and B. Ryder. Complexity of single level function pointer aliasing analysis. Technical Report LCSR-TR-233, Laboratory of Computer Science Research, Rutgers University, October 1994.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Muth, R., Debray, S. (1997). On the complexity of function pointer may-alias analysis. In: Bidoit, M., Dauchet, M. (eds) TAPSOFT '97: Theory and Practice of Software Development. CAAP 1997. Lecture Notes in Computer Science, vol 1214. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0030612
Download citation
DOI: https://doi.org/10.1007/BFb0030612
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62781-4
Online ISBN: 978-3-540-68517-3
eBook Packages: Springer Book Archive