Abstract
The subject of this article is flow- and context-insensitive pointer analysis. We present a novel approach for precisely modelling struct variables and indirect function calls. Our method emphasises efficiency and simplicity and is based on a simple language of set constraints. We obtain an O(v4) bound on the time needed to solve a set of constraints from this language, where v is the number of constraint variables. This gives, for the first time, some insight into the hardness of performing field-sensitive pointer analysis of C. Furthermore, we experimentally evaluate the time versus precision trade-off for our method by comparing against the field-insensitive equivalent. Our benchmark suite consists of 11 common C programs ranging in size from 15,000 to 200,000 lines of code. Our results indicate the field-sensitive analysis is more expensive to compute, but yields significantly better precision. In addition, our technique has been integrated into the latest release (version 4.1) of the GNU Compiler GCC. Finally, we identify several previously unknown issues with an alternative and less precise approach to modelling struct variables, known as field-based analysis.
- Aiken, A. 1994. Set constraints: Results, applications, and future directions. In Proceedings of the Workshop on Principles and Practice of Constraint Programming (PPCP). Lecture Notes in Computer Science, vol. 874. Springer-Verlag, New York, 326--335. Google ScholarDigital Library
- Aiken, A. 1999. Introduction to set constraint-based program analysis. Sci. Comput. Prog. 35, 2--3, 79--111. Google ScholarDigital Library
- Aiken, A., and Wimmers, E. L. 1992. Solving systems of set constraints. In Proceedings of the IEEE Symposium on Logic in Computer Science (LICS). IEEE Computer Society Press, Los Alamitos, CA, 329--340.Google Scholar
- Aiken, A. and Wimmers, E. L. 1993. Type inclusion constraints and type inference. In Proceedings of the ACM Conference on Functional Programming Languages and Computer Architecture (FPCA). ACM, New York, 31--41. Google ScholarDigital Library
- Alur, R., Henzinger, T. A., Mang, F. Y. C., Qadeer, S., Rajamani, S. K., and Tasiran, S. 1998. MOCHA: Modularity in model checking. In Proceedings of the Conference on Computer Aided Verification (CAV). Lecture Notes in Computer Science, vol. 1427. Springer-Verlag, New York, 521--525. Google ScholarDigital Library
- Andersen, L. O. 1994. Program analysis and specialization for the C programming language. Ph.D. dissertation. DIKU, University of Copenhagen.Google Scholar
- Ball, T. and Horwitz, S. 1993. Slicing programs with arbitrary control-flow. In Proceedings of the Workshop on Automated and Algorithmic Debugging (AADEBUG). Lecture Notes in Computer Science, vol. 749. Springer-Verlag, New York, 206--222. Google ScholarDigital Library
- Berlin, D. 2005. Structure aliasing in GCC. In Proceedings of the GCC Developers Summit. 25--36.Google Scholar
- Berndl, M., Lhoták, O., Qian, F., Hendren, L. J., and Umanee, N. 2003. Points-to analysis using BDDs. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI). ACM, New York, 196--207. Google ScholarDigital Library
- Binkley, D. 1998. The application of program slicing to regression testing. Inf. Softw. Tech. 40, 11--12, 583--594.Google ScholarCross Ref
- Blanchet, B., Cousot, P., Cousot, R., Feret, J., Mauborgne, L., Miné, A., Monniaux, D., and Rival, X. 2002. Design and implementation of a special-purpose static program analyzer for safety-critical real-time embedded software. In The Essence of Computation: Complexity, Analysis, Transformation. Lecture Notes in Computer Science, vol. 2566. Springer-Verlag, New York, 85--108. Google ScholarDigital Library
- Blanchet, B., Cousot, P., Cousot, R., Feret, J., Mauborgne, L., Miné, A., Monniaux, D., and Rival, X. 2003. A static analyzer for large safety-critical software. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI). ACM, New York, 196--207. Google ScholarDigital Library
- Bourdoncle, F. 1993a. Abstract debugging of higher-order imperative languages. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI). ACM, New York, 46--55. Google ScholarDigital Library
- Bourdoncle, F. 1993b. Efficient chaotic iteration strategies with widenings. In Proceedings of the Conference on Formal Methods in Programming and Their Applications. Lecture Notes in Computer Science, vol. 735. Springer-Verlag, New York, 128--141.Google Scholar
- Burke, M. 1990. An interval-based approach to exhaustive and incremental interprocedural data-flow analysis. ACM Trans. Prog. Lang. Syst. (TOPLAS) 12, 3, 341--395. Google ScholarDigital Library
- Chandra, S., and Reps, T. 1999a. Physical type checking for C. In Proceedings of the ACM Workshop on Program Analysis for Software Tools and Engineering (PASTE). ACM, New York, 66--75. Google ScholarDigital Library
- Chandra, S. and Reps, T. 1999b. Physical type checking for C. Technical Report BL0113590-990302-04, Lucent Technologies, Bell Laboratories.Google Scholar
- Chatterjee, R., Ryder, B. G., and Landi, W. A. 1999. Relevant context inference. In Proceedings of the ACM Symposium on Principles of Programming Languages (POPL). ACM, New York, 133--146. Google ScholarDigital Library
- Chen, L.-L. and Harrison, W. L. 1994. An efficient approach to computing fixpoints for complex program analysis. In Proceedings of the ACM Supercomputing Conference (SC). ACM, New York, 98--106. Google ScholarDigital Library
- Cheng, B.-C. and Hwu, W.-M. W. 2000. Modular interprocedural pointer analysis using access paths: design, implementation, and evaluation. In Proceedings of the ACM conference on Programming Language Design and Implementation (PLDI). ACM, New York, 57--69. Google ScholarDigital Library
- Das, M. 2000. Unification-based pointer analysis with directional assignments. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI). ACM, New York, 35--46. Google ScholarDigital Library
- Das, M., Liblit, B., Fähndrich, M., and Rehof, J. 2001. Estimating the impact of scalable pointer analysis on optimization. In Proceedings of the Static Analysis Symposium (SAS). Lecture Notes in Computer Science, vol. 2126. Springer-Verlag, New York, 260--278. Google ScholarDigital Library
- Diwan, A., McKinley, K. S., and Moss, J. E. B. 1998. Type-based alias analysis. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI). ACM, New York, 106--117. Google ScholarDigital Library
- Dor, N., Rodeh, M., and Sagiv, M. 2003. CSSV: Towards a realistic tool for statically detecting all buffer overflows in C. In Proceedings of the ACM conference on Programming Language Design and Implementation (PLDI). ACM, New York, 155--167. Google ScholarDigital Library
- Eichin, M. W. and Rochlis, J. A. 1989. With microscope and tweezers: An analysis of the internet virus of November 1988. In Proceedings of the IEEE Symposium on Research in Security and Privacy. IEEE Computer Society Press, Los Alamitos, CA, 326--343.Google Scholar
- Emami, M., Ghiya, R., and Hendren, L. J. 1994. Context-sensitive interprocedural points-to analysis in the presence of function pointers. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI). ACM, New York, 242--256. Google ScholarDigital Library
- Fähndrich, M., Foster, J. S., Su, Z., and Aiken, A. 1998. Partial online cycle elimination in inclusion constraint graphs. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI). ACM, New York, 85--96. Google ScholarDigital Library
- Fähndrich, M., Rehof, J., and Das, M. 2000. Scalable context-sensitive flow analysis using instantiation constraints. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI). ACM, New York, 253--263. Google ScholarDigital Library
- Fecht, C. and Seidl, H. 1996. An even faster solver for general systems of equations. In Proceedings of the Static Analysis Symposium (SAS). Lecture Notes in Computer Science, vol. 1145. Springer-Verlag, New York, 189--204. Google ScholarDigital Library
- Fecht, C. and Seidl, H. 1998. Propagating differences: An efficient new fixpoint algorithm for distributive constraint systems. In Proceedings of the European Symposium on Programming (ESOP). Lecture Notes in Computer Science, vol. 1381. Springer-Verlag, New York, 90--104. Google ScholarDigital Library
- Flanagan, C. 1997. Effective static debugging via componential set-based analysis. Ph.D. dissertation. Rice University.Google Scholar
- Flanagan, C., Leino, K. R. M., Lillibridge, M., Nelson, G., Saxe, J. B., and Stata, R. 2002. Extended static checking for Java. In Proceedings of the ACM conference on Programming Language Design and Implementation (PLDI). ACM, New York, 234--245. Google ScholarDigital Library
- Foster, J. S., Fähndrich, M., and Aiken, A. 1997. Flow-insensitive points-to analysis with term and set constraints. Technical Report CSD-97-964, University of California, Berkeley, CA. Google ScholarDigital Library
- Foster, J. S., Fähndrich, M., and Aiken, A. 1999. A theory of type qualifiers. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI). ACM, New York, 192--203. Google ScholarDigital Library
- Foster, J. S., Fähndrich, M., and Aiken, A. 2000. Polymorphic versus monomorphic flow-insensitive points-to analysis for C. In Proceedings of the Static Analysis Symposium (SAS). Lecture Notes in Computer Science, vol. 1824. Springer-Verlag, New York, 175--198. Google ScholarDigital Library
- Gabow, H. N. 2000. Path-based depth-first search for strong and biconnected components. Inf. Proc. Lett. 74, 3--4 (May), 107--114. Google ScholarDigital Library
- Ghiya, R., Lavery, D., and Sehr, D. 2001. On the importance of points-to analysis and other memory disambiguation methods for C programs. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI). ACM, New York, 47--58. Google ScholarDigital Library
- Godefroid, P. 1997. VeriSoft: A tool for the automatic analysis of concurrent reactive software. In Proceedings of the Conference on Computer Aided Verification (CAV). Lecture Notes in Computer Science, vol. 1254. Springer-Verlag, New York, 476--479. Google ScholarDigital Library
- Harman, M., Binkley, D., and Danicic, S. 2003. Amorphous program slicing. J. Syst. Softw. (JSS) 68, 1, 45--64. Google ScholarDigital Library
- Hasti, R. and Horwitz, S. 1998. Using static single assignment form to improve flow-insensitive pointer analysis. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI). ACM, New York, 97--105. Google ScholarDigital Library
- Heintze, N. 1994. Set-based analysis of ML programs. In Proceedings of the ACM Conference on Lisp and Functional Programming (LFP). ACM, New York, 306--317. Google ScholarDigital Library
- Heintze, N. and McAllester, D. 1997a. Linear-time subtransitive control flow analysis. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI). ACM, New York, 261--272. Google ScholarDigital Library
- Heintze, N. and McAllester, D. A. 1997b. On the cubic bottleneck in subtyping and flow analysis. In Proceedings of the IEEE Symposium on Logic in Computer Science (LICS). IEEE Computer Society Press, Los Alamitos, CA, 342--351. Google ScholarDigital Library
- Heintze, N. and Tardieu, O. 2001a. Demand-driven pointer analysis. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI). ACM, New York, 24--34. Google ScholarDigital Library
- Heintze, N. and Tardieu, O. 2001b. Ultra-fast aliasing analysis using CLA: A million lines of C code in a second. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI). ACM, New York, 254--263. Google ScholarDigital Library
- Henzinger, T. A., Jhala, R., Majumdar, R., and Sutre, G. 2003. Software verification with Blast. In Proceedings of the Workshop on Model Checking Software. Lecture Notes in Computer Science, vol. 2648. Springer-Verlag, New York, 235--239.Google Scholar
- Hind, M. 2001. Pointer analysis: Haven't we solved this problem yet? In Proceedings of the 2001 ACM workshop on Program Analysis for Software Tools and Engineering (PASTE). ACM, New York, 54--61. Google ScholarDigital Library
- Hind, M., Burke, M., Carini, P., and Choi, J.-D. 1999. Interprocedural pointer alias analysis. ACM Trans. Prog. Lang. Syst. (TOPLAS) 21, 4, 848--894. Google ScholarDigital Library
- Hind, M. and Pioli, A. 1998. Assessing the effects of flow-sensitivity on pointer alias analyses. In Proceedings of the Static Analysis Symposium (SAS). Lecture Notes in Computer Science, vol. 1503. Springer-Verlag, New York, 57--81. Google ScholarDigital Library
- Hind, M. and Pioli, A. 2000. Which pointer analysis should I use? In Proceedings of the ACM International Symposium on Software Testing and Analysis (ISSTA). ACM, New York, 113--123. Google ScholarDigital Library
- Holzmann, G. J. 1997. The Spin model checker. IEEE Trans. Softw. Engin. 23, 5, 279--95. Google ScholarDigital Library
- Horwitz, S., Demers, A. J., and Teitelbaum, T. 1987. An efficient general iterative algorithm for dataflow analysis. Acta Inf. 24, 6, 679--694. Google ScholarDigital Library
- ISO90 1990. ISO/IEC. international standard ISO/IEC 9899, programming languages - C.Google Scholar
- Johnson, R. and Wagner, D. 2004. Finding user/kernel pointer bugs with type inference. In Proceedings of the USENIX Security Symposium. USENIX, 119--134. Google ScholarDigital Library
- Jones, J. A., Harrold, M. J., and Stasko, J. 2002. Visualization of test information to assist fault localization. In Proceedings of the International Conference on Software Engineering (ICSE). ACM, New York, 467--477. Google ScholarDigital Library
- Jones, N. D. and Muchnick, S. S. 1981. Flow analysis and optimization of lisp-like structures. In Program Flow Analysis: Theory and Applications, S. S. Muchnick and N. D. Jones, Eds. Prentice-Hall, Englewood Cliff, 102--131.Google Scholar
- Kodumal, J. and Aiken, A. 2005. Banshee: A scalable constraint-based analysis toolkit. In Proceedings of the Static Analysis Symposium, SAS. Lecture Notes in Computer Science, vol. 3672. Springer-Verlag, New York, 218--234. Google ScholarDigital Library
- Landi, W. 1992a. Interprocedural aliasing in the presence of pointers. Ph.D. dissertation, Rutgers University, NJ. Google ScholarDigital Library
- Landi, W. 1992b. Undecidability of static analysis. ACM Lett. Prog. Lang. Syst. 1, 4, 323--337. Google ScholarDigital Library
- Lhotak, O. and Hendren, L. J. 2003. Scaling Java points-to analysis using SPARK. In Proceedings of the Conference on Compiler Construction (CC). Lecture Notes in Computer Science, vol. 2622. Springer-Verlag, New York, 153--169.Google Scholar
- Liang, D. and Harrold, M. J. 1999. Efficient points-to analysis for whole-program analysis. In Proceedings of the European Software Engineering Confrence (ESEC) and ACM Foundations of Software Engineering (FSE). Lecture Notes in Computer Science, vol. 1687. Springer-Verlag/ACM, New York, 199--215. Google ScholarDigital Library
- Liang, D., Pennings, M., and Harrold, M. J. 2001. Extending and evaluating flow-insensitive and context-insensitive points-to analyses for Java. In Proceedings of the ACM Workshop on Program Analyses for Software Tools and Engineering (PASTE). ACM, New York, 73--79. Google ScholarDigital Library
- McKinley, K. S. 1994. Evaluating automatic parallelization for efficient execution on shared-memory multiprocessors. In Proceedings of the IEEE/ACM Supercomputing Conference (SC). ACM, New York, 54--63. Google ScholarDigital Library
- Melski, D. and Reps, T. 1997. Interconvertibility of set constraints and context-free language reachability. In Proceedings of the ACM Workshop on Partial Evaluation and Program Manipulation (PEPM). ACM, New York, 74--88. Google ScholarDigital Library
- Milanova, A., Rountev, A., and Ryder, B. 2002. Parameterized object sensitivity for points-to and side-effect analyses for Java. In Proceedings of the ACM International Symposium on Software Testing and Analysis (ISSTA). ACM, New York, 1--11. Google ScholarDigital Library
- Myers, B. A. 1986. Visual programming, programming by example, and program visualization; A taxonomy. In Proceedings of the ACM Conference on Human Factors in Computing Systems (CHI). ACM, New York, 59--66. Google ScholarDigital Library
- Nielson, F., Nielson, H. R., and Hankin, C. L. 1999. Principles of Program Analysis. Springer-Verlag, New York. Google ScholarDigital Library
- Nuutila, E. and Soisalon-Soininen, E. 1994. On finding the strongly connected components in a directed graph. Inf. Proc. Lett. 49, 1 (Jan.), 9--14. Google ScholarDigital Library
- Nystrom, E. M., Kim, H.-S., and Hwu, W.-M. W. 2004a. Bottom-up and top-down context-sensitive summary-based pointer analysis. In Proceedings of the Static Analysis Symposium (SAS). Lecture Notes in Computer Science, vol. 3148. Springer-Verlag, New York, 165--180.Google Scholar
- Nystrom, E. M., Kim, H.-S., and Hwu, W.-M. W. 2004b. Importance of heap specialization in pointer analysis. In Proceedings of the ACM Workshop on Program Analysis for Software Tools and Engineering (PASTE). ACM, New York, 43--48. Google ScholarDigital Library
- Padua, D. A., Kuck, D. J., and Lawrie, D. H. 1980. High-speed multiprocessors and compilation techniques. IEEE Trans. Comput. C-29, 9 (Sept.), 763--776. Google ScholarDigital Library
- Padua, D. A. and Wolfe, M. J. 1986. Advanced compiler optimizations for supercomputers. Commun. ACM 29, 12, 1184--1201. Google ScholarDigital Library
- Pearce, D. J. 2005. Some directed graph algorithms and their application to pointer analysis (online version available at http://www.mcs.vuw.ac.nz/djp). Ph.D. dissertation, Imperial College, London, United Kingdom.Google Scholar
- Pearce, D. J. and Kelly, P. H. J. 2004. A dynamic algorithm for topologically sorting directed acyclic graphs. In Proceedings of the Workshop on Efficient and Experimental Algorithms (WEA). Lecture Notes in Computer Science, vol. 3059. Springer-Verlag, New York, 383--398.Google Scholar
- Pearce, D. J. and Kelly, P. H. J. 2006. A dynamic topological sort algorithm for directed acyclic graphs. ACM J. Experim. Alg. 11, 1.7. Google ScholarDigital Library
- Pearce, D. J., Kelly, P. H. J., and Hankin, C. 2003. Online cycle detection and difference propagation for pointer analysis. In Proceedings of the IEEE Workshop on Source Code Analysis and Manipulation (SCAM). IEEE Computer Society Press, Los Alamitos, CA, 3--12.Google Scholar
- Pearce, D. J., Kelly, P. H. J., and Hankin, C. 2004a. Efficient field-sensitive pointer analysis for C. In Proceedings of the ACM Workshop on Program Analysis for Software Tools and Engineering (PASTE). ACM, New York, 37--42. Google ScholarDigital Library
- Pearce, D. J., Kelly, P. H. J., and Hankin, C. 2004b. Online cycle detection and difference propagation: Applications to pointer analysis. Softw. Qual. J. 12, 4, 309--335. Google ScholarDigital Library
- Ramalingam, G. 1994. The undecidability of aliasing. ACM Trans. Prog. Lang. Syst. (TOPLAS) 16, 5, 1467--1471. Google ScholarDigital Library
- Reiss, S. P. 1997. Cacti: A front end for program visualization. In Proceedings of the IEEE symposium on Information Visualization (InfoVis). IEEE Computer Society Press, Los Alamitos, CA, 46--50. Google ScholarDigital Library
- Reps, T. and Turnidge, T. 1996. Program specialization via program slicing. In Selected Papers from the International Seminar on Partial Evaluation. Lecture Notes in Computer Science, vol. 1110. Springer-Verlag, New York, 409--429. Google ScholarDigital Library
- Reynolds, J. C. 1969. Automatic computation of data set definitions. In Proceedings of the Information Processing Congress (IFIP). Vol. 1. North-Holland, Amsterdam, The Netherlands, 456--461.Google Scholar
- Rountev, A. and Chandra, S. 2000. Off-line variable substitution for scaling points-to analysis. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI). ACM, New York, 47--56. Google ScholarDigital Library
- Rountev, A., Milanova, A., and Ryder, B. G. 2001. Points-to analysis for Java using annotated constraints. In Proceedings of the ACM Conference on Object Oriented Programming Systems, Languages and Applications (OOPSLA). ACM, New York, 43--55. Google ScholarDigital Library
- Saha, D. and Ramakrishnan, C. R. 2005. Incremental and demand-driven points-to analysis using logic programming. In Proceedings of the ACM Conference on Principles and Practice of Declarative Programming (PPDP). ACM, New York, 117--128. Google ScholarDigital Library
- Schon, E. 1995. On the computation of fixpoints in static program analysis with an application to AKL. Technical Report R95-06, Swedish Institute of Computer Science. Nov. Google ScholarDigital Library
- Shapiro, M. and Horwitz, S. 1997. Fast and accurate flow-insensitive points-to analysis. In Proceedings of the Symposium on Principles of Programming Languages (POPL). ACM, New York, 1--14. Google ScholarDigital Library
- Shmueli, O. 1983. Dynamic cycle detection. Inf. Proc. Lett. 17, 4 (Nov.), 185--188.Google ScholarCross Ref
- So, B., Moon, S., and Hall, M. W. 1998. Measuring the effectiveness of automatic parallelization in SUIF. In Proceedings of the ACM/IEEE Supercomputing Conference (SC). ACM, New York, 212--219. Google ScholarDigital Library
- Sridharan, M., Gopan, D., Shan, L., and Bodik, R. 2005. Demand-driven points-to analysis for Java. In Proceedings of the ACM Conference on Object Oriented Programming, Systems, Languages, and Applications (OOPSLA). ACM, New York, 59--76. Google ScholarDigital Library
- Steensgaard, B. 1996. Points-to analysis in almost linear time. In Proceedings of the ACM Symposium on Principles of Programming Languages (POPL). ACM, New York, 32--41. Google ScholarDigital Library
- Su, Z., Fähndrich, M., and Aiken, A. 2000. Projection merging: Reducing redundancies in inclusion constraint graphs. In Proceedings of the Symposium on Principles of Programming Languages (POPL). ACM, New York, 81--95. Google ScholarDigital Library
- SUIF2. The SUIF 2 research compiler Stanford University, Stanford, CA, http://suif.stanford.edu.Google Scholar
- Systa, T., Yu, P., and Müller, H. 2000. Analyzing Java software by combining metrics and program visualization. In Proceedings of the IEEE Conference on Software Maintenance and Reengineering (CSMR). IEEE Computer Society Press, Los Alamitos, CA, 199--208. Google ScholarDigital Library
- Tarjan, R. E. 1972. Depth-first search and linear graph algorithms. SIAM J. Comput. 1, 2, 146--160.Google ScholarDigital Library
- The VIS Group. 1996. VIS: A system for verification and synthesis. In Proceedings of the Conference on Computer Aided Verification (CAV). Lecture Notes in Computer Science, vol. 1102. Springer-Verlag, New York, 428--432. Google ScholarDigital Library
- Vivien, F. and Rinard, M. 2001. Incrementalized pointer and escape analysis. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI). ACM, New York, 35--46. Google ScholarDigital Library
- Wagner, D., Foster, J. S., Brewer, E. A., and Aiken, A. 2000. A first step towards automated detection of buffer overrun vulnerabilities. In Proceedings of the Network and Distributed System Security Symposium (NDSS). The Internet Society, 3--17.Google Scholar
- Whaley, J. and Lam, M. S. 2002. An efficient inclusion-based points-to analysis for strictly-typed languages. In Proceedings of the Symposium on Static Analysis (SAS). Lecture Notes in Computer Science, vol. 2477. Springer-Verlag, New York, 180--195. Google ScholarDigital Library
- Whaley, J. and Lam, M. S. 2004. Cloning-based context-sensitive pointer alias analysis using Binary Decision Diagrams. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI). ACM, New York, 131--144. Google ScholarDigital Library
- Wilson, R. P. 1997. Efficient context-sensitive pointer analysis for C programs. Ph.D. dissertation. Stanford University, Stanford, CA. Google ScholarDigital Library
- Wilson, R. P. and Lam, M. S. 1995. Efficient context-sensitive pointer analysis for C programs. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI). ACM, New York, 1--12. Google ScholarDigital Library
- Wolfe, M. J. 1982. Optimizing supercompilers for supercomputers. Ph.D. dissertation. Deptartment of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL. Google ScholarDigital Library
- Yong, S. H., Horwitz, S., and Reps, T. 1999. Pointer analysis for programs with structures and casting. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI). ACM, New York, 91--103. Google ScholarDigital Library
Index Terms
- Efficient field-sensitive pointer analysis of C
Recommendations
Efficient field-sensitive pointer analysis for C
PASTE '04: Proceedings of the 5th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineeringThe subject of this paper is flow- and context-insensitive pointer analysis. We present a novel approach for precisely modelling struct variables and indirect function calls. Our method emphasises efficiency and simplicity and extends the language of ...
Semi-sparse flow-sensitive pointer analysis
POPL '09Pointer analysis is a prerequisite for many program analyses, and the effectiveness of these analyses depends on the precision of the pointer information they receive. Two major axes of pointer analysis precision are flow-sensitivity and context-...
Semi-sparse flow-sensitive pointer analysis
POPL '09: Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languagesPointer analysis is a prerequisite for many program analyses, and the effectiveness of these analyses depends on the precision of the pointer information they receive. Two major axes of pointer analysis precision are flow-sensitivity and context-...
Comments