The DOI matches its Crossref record; 1 of the 1 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
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
Cited by
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) · Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation · doi:10.1145/207110.207111 · Cited by 458
Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C
Ghiya, R., & Hendren, L. J. (1996) · Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '96 · doi:10.1145/237721.237724 · Cited by 287
(2004) · OpenGrey (Institut de l'Information Scientifique et Technique) · Cited by 126
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
- 1
- 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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Interprocedural may-alias analysis for pointers: beyond k -limiting. https://app.cochat.ai/papers/10.1145/178243.178263
- The paper
- Deutsch, A. (1994). Interprocedural may-alias analysis for pointers: beyond k -limiting. Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation. https://doi.org/10.1145/178243.178263
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.