The DOI matches its Crossref record; 34 of the 34 references it cites were found in a registry or an index.
Interprocedural may-alias analysis for pointers: beyond k -limiting
Abstract
Existing methods for alias analysis of recursive pointer data structures are based on two approximation techniques: k-limiting, and store-based (or equivalently location or region-based) approximations, which blur distinction between elements of recursive data structures. Although notable progress in inter-procedural alias analysis has been recently accomplished, very little progress in the precision of analysis of recursive pointer data structures has been seen since the inception of these approximation techniques by Jones and Muchnick a decade ago. As a result, optimizing, verifying and parallelizing programs with pointers has remained difficult.We present a new parametric framework for analyzing recursive pointer data structures which can express a new natural class of alias information not accessible to existing methods. The key idea is to represent alias information by pairs of symbolic access paths which are qualified by symbolic descriptions of the positions for which the alias pair holds.Based on this result, we present an algorithm for interprocedural may-alias analysis with pointers which on numerous examples that occur in practice is much more precise than recently published algorithms [CWZ90, He90, LR92, CBC93].
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Compilers: Principles, Techniques, and Tools
Aho, A. V., Sethi, R., & Ullman, J. D. (1986) · Cited by 8,448
Cousot, P., & Cousot, R. (1977) · Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '77 · doi:10.1145/512950.512973 · Cited by 6,279
Automata, Languages, and Machines
(1974) · Pure and applied mathematics · doi:10.1016/s0079-8169(08)x6055-6 · Cited by 1,897
Systematic design of program analysis frameworks
Cousot, P., & Cousot, R. (1979) · Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '79 · doi:10.1145/567752.567778 · Cited by 1,621
Automatic discovery of linear restraints among variables of a program
Cousot, P., & Halbwachs, N. (1978) · Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '78 · doi:10.1145/512760.512770 · Cited by 1,614
Derivatives of Regular Expressions
Brzozowski, J. A. (1964) · Journal of the ACM · doi:10.1145/321239.321249 · Cited by 923
A unified approach to global program optimization
Kildall, G. A. (1973) · Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '73 · doi:10.1145/512927.512945 · Cited by 916
Parikh, R. (1966) · Journal of the ACM · doi:10.1145/321356.321364 · Cited by 808
Affine relationships among variables of a program
Karr, M. (1976) · Acta Informatica · doi:10.1007/bf00268497 · Cited by 439
Analysis of pointers and structures
Chase, D., Wegman, M., & Zadeck, F. K. (2004) · ACM SIGPLAN Notices · doi:10.1145/989393.989429 · Cited by 433
Comparing the Galois connection and widening/narrowing approaches to abstract interpretation
Cousot, P., & Cousot, R. (2006) · Lecture Notes in Computer Science · doi:10.1007/3-540-55844-6_142 · Cited by 423
Undecidability of static analysis
Landi, W. A. (1992) · ACM Letters on Programming Languages and Systems · doi:10.1145/161494.161501 · Cited by 407
Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects
Choi, J.-D., Burke, M., & Carini, P. R. (1993) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/158511.158639 · Cited by 362
A safe approximate algorithm for interprocedural pointer aliasing
Landi, W. A., & Ryder, B. G. (2004) · ACM SIGPLAN Notices · doi:10.1145/989393.989440 · Cited by 276
Dependence analysis for pointer variables
Horwitz, S., Pfeiffer, P., & Reps, T. (1989) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/73141.74821 · Cited by 233
Parallelizing programs with recursive data structures
Hendren, L. J., & Nicolau, A. (1990) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/71.80123 · Cited by 219
Detecting conflicts between structure accesses
Larus, J. R., & Hilfinger, P. N. (1988) · ACM SIGPLAN Notices · doi:10.1145/960116.53993 · Cited by 213
Jones, N. D., & Muchnick, S. S. (1982) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/582153.582161 · Cited by 213
Semantic foundations of program analysis
Cousot, P. M. (1981) · Cited by 203
Static determination of dynamic properties of recursive procedures
Cousot, P. M., & Cousot, R. (1977) · Cited by 175
Static analysis of arithmetical congruences
Granger, P. (1989) · International Journal of Computer Mathematics · doi:10.1080/00207168908803778 · Cited by 162
Detecting conflicts between structure accesses
Larus, J. R., & Hilfinger, P. N. (1988) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/53990.53993 · Cited by 156
Static analysis of linear congruence equalities among variables of a program
Granger, P. (1991) · Lecture notes in computer science · doi:10.1007/3-540-53982-4_10 · Cited by 146
A semantic model of reference counting and its abstraction (detailed summary)
Hudak, P. (1986) · ACM Conference on LISP and Functional Programming (LFP) · doi:10.1145/319838.319876 · Cited by 141
The interprocedural analysis and automatic parallelization of Scheme programs
Harrison, W. L. (1989) · LISP and Symbolic Computation · doi:10.1007/bf01808954 · Cited by 134
A technique for summarizing data access and its use in parallelism enhancing transformations
Balasundaram, V., & Kennedy, K. (1989) · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/73141.74822 · Cited by 125
Lifetime analysis of dynamically allocated objects
Ruggieri, C., & Murtagh, T. (1988) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/73560.73585 · Cited by 113
Deutsch, A. (2003) · International Conference on Computer Languages (ICCL) · doi:10.1109/iccl.1992.185463 · Cited by 113
Self-citationDeutsch, A. (1990) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/96709.96725 · Cited by 107
Self-citationFlow analysis of lambda expressions: Preliminary version
Jones, N. D. (1981) · Lecture notes in computer science · doi:10.1007/3-540-10843-2_10 · Cited by 96
Granger, P. (1992) · Lecture notes in computer science · doi:10.1007/3-540-56287-7_95 · Cited by 79
Static determination of dynamic properties of generalized type unions
Cousot, P. M., & Cousot, R. (1977) · ACM SIGPLAN Notices · doi:10.1145/390017.808314 · Cited by 63
Dependence analysis for pointer variables
Horwitz, S., Pfeiffer, P., & Reps, T. (1989) · ACM SIGPLAN Notices · doi:10.1145/74818.74821 · Cited by 59
Restructuring Lisp programs for concurrent execution
Larus, J. R., & Hilfinger, P. N. (1988) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/62115.62126 · Cited by 37
Cited by
Points-to analysis in almost linear time
Steensgaard, B. (1996) · Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '96 · doi:10.1145/237721.237727 · Cited by 1,088
Watermarking, tamper-proofing, and obfuscation - tools for software protection
Collberg, C. S., & Thomborson, C. (2002) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2002.1027797 · Cited by 735
Miné, A. (2006) · Higher-Order and Symbolic Computation · doi:10.1007/s10990-006-8609-1 · Cited by 720
Ownership types for flexible alias protection
Clarke, D. G., Potter, J. M., & Noble, J. (1998) · Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications · doi:10.1145/286936.286947 · Cited by 580
Efficient context-sensitive pointer analysis for C programs
Wilson, R. P., & Lam, M. S. (1995) · ACM SIGPLAN Notices · doi:10.1145/223428.207111 · Cited by 539
Metadata
- Authors
- Deutsch, A.
- Venue
- Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation
- Publisher
- ACM
- Published
- 1994-06
- Pages
- 230-241
- ISSN
- 1531-7102 (ISSN-L)
- OpenAlex
- W2102440514
- Cited by
- 328
- References
- 34
- FWCI
- 18.32
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.