The DOI matches its Crossref record; 22 of the 22 references it cites were found in a registry or an index.
Efficiently computing static single assignment form and the control dependence graph
Open accessAbstract
In optimizing compilers, data structure choices directly influence the power and efficiency of practical program optimization.A poor choice of data structure can inhibit optimization or slow compilation to the point that advanced optimization features become undesirable.Recently, static single assignment form and the control dependence graph have been proposed to represent data flow and control flow propertiee of programs.Each of these previously unrelated techniques lends efficiency and power to a useful class of program optimization.Although both of these structures are attractive, the difficulty of their construction and their potential size have discouraged their use.We present new algorithms that efficiently compute these data structures for arbitrary control flow graphs.The algorithms use dominance frontiers, a new concept that may have other applications.We also give analytical and experimental evidence that all of these data structures are usually linear in the size of the original program.This paper thus presents strong evidence that these structures can be of practical use in optimization.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
The program dependence graph and its use in optimization
Ferrante, J., Ottenstein, K. J., & Warren, J. D. (1987) · ACM Transactions on Programming Languages and Systems · doi:10.1145/24039.24041 · Cited by 2,755
Self-citationOptimizing supercompilers for supercomputers
Wolfe, M. (2020) · Proceedings of the 34th ACM International Conference on Supercomputing · doi:10.1145/3392717.3400034 · Cited by 837
Register allocation & spilling via graph coloring
Chaitin, G. J. (1982) · ACM SIGPLAN Notices · doi:10.1145/872726.806984 · Cited by 767
Register allocation via coloring
Chaitin, G. J., Auslander, M. A., Chandra, A. K., Cocke, J., Hopkins, M. E., & Markstein, P. W. (1981) · Computer Languages · doi:10.1016/0096-0551(81)90048-5 · Cited by 737
Register allocation & spilling via graph coloring
Chaitin, G. J. (1982) · Proceedings of the 1982 SIGPLAN symposium on Compiler construction - SIGPLAN '82 · doi:10.1145/800230.806984 · Cited by 666
A fast algorithm for finding dominators in a flowgraph
Lengauer, T., & Tarjan, R. E. (1979) · ACM Transactions on Programming Languages and Systems · doi:10.1145/357062.357071 · Cited by 645
First version of a data flow procedure language
Dennis, J. B. (1974) · Lecture Notes in Computer Science · doi:10.1007/3-540-06859-7_145 · Cited by 644
The Structure of Computers and Computations
Kuck, D. L. (1978) · UCLA - Biblioteca de Ciencias y Tecnologia Felix Morales Bueno · Cited by 492
Analysis of pointers and structures
Chase, D., Wegman, M., & Zadeck, F. K. (2004) · ACM SIGPLAN Notices · doi:10.1145/989393.989429 · Cited by 433
Self-citationIntegrating noninterfering versions of programs
Horwitz, S., Prins, J., & Reps, T. (1989) · ACM Transactions on Programming Languages and Systems · doi:10.1145/65979.65980 · Cited by 417
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
Interprocedural dependence analysis and parallelization
Burke, M. G., & Cytron, R. K. (2004) · ACM SIGPLAN Notices · doi:10.1145/989393.989411 · Cited by 219
Self-citationDetecting conflicts between structure accesses
Larus, J. R., & Hilfinger, P. N. (1988) · ACM SIGPLAN Notices · doi:10.1145/960116.53993 · Cited by 213
A precise inter-procedural data flow algorithm
Myers, E. M. (1981) · Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '81 · doi:10.1145/567532.567556 · Cited by 211
An overview of the PTRAN analysis system for multiprocessing
Allen, F., Burke, M., Charles, P., Cytron, R., & Ferrante, J. (2014) · 25th Anniversary International Conference on Supercomputing Anniversary Volume - · doi:10.1145/2591635.2667156 · Cited by 183
Self-citationDependence analysis for subscripted variables and its application to program transformations
Allen, J. R. (1983) · Rice Research Repository (Rice University) · Cited by 168
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
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
Property extraction in well-founded property sets
Wegbreit, B. (1975) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1975.6312852 · Cited by 91
Code motion of control structures in high-level languages
Cytron, R. K., Lowry, A., & Zadeck, F. K. (1986) · ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL) · doi:10.1145/512644.512651 · Cited by 53
Self-citationData-flow graphs as an intermediate program form.
Ottenstein, K. J. (1978) · Purdue e-Pubs (Purdue University System) · Cited by 34
Cited by
LLVM: A compilation framework for lifelong program analysis & transformation
Lattner, C., & Adve, V. (2004) · International Symposium on Code Generation and Optimization, 2004. CGO 2004. · doi:10.1109/cgo.2004.1281665 · Cited by 2,681
High-Level Synthesis for FPGAs: From Prototyping to Deployment
Cong, J., Liu, B., Neuendorffer, S., Noguera, J., Vissers, K., & Zhang, Z. (2011) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2011.2110592 · Cited by 846
Boogie: A Modular Reusable Verifier for Object-Oriented Programs
Barnett, M., Chang, B.-Y. E., DeLine, R., Jacobs, B., & Leino, K. R. M. (2006) · Lecture Notes in Computer Science · doi:10.1007/11804192_17 · Cited by 799
A survey of symbolic execution techniques
Baldoni, R., Coppa, E., D’elia, D. C., Demetrescu, C., & Finocchi, I. (2019) · ACM Computing Surveys · doi:10.1145/3182657 · Cited by 708
The software model checker Blast: Applications to software engineering
Beyer, D., Henzinger, T. A., Jhala, R., & Majumdar, R. (2007) · International Journal on Software Tools for Technology Transfer · doi:10.1007/s10009-007-0044-z · Cited by 585
Metadata
- Authors
- Cytron, R., Ferrante, J., Rosen, B. K., Wegman, M. N., & Zadeck, F. K.
- Venue
- ACM Transactions on Programming Languages and Systems
- Published
- 1991-10
- Volume
- 13
- Issue
- 4
- Pages
- 451-490
- ISSN
- 0164-0925 (ISSN-L)
- 1558-4593
- OpenAlex
- W1982205631
- Cited by
- 2,267
- References
- 22
- FWCI
- 33.89
- Type
- journal article
- Language
- en
- Open access
- bronze
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.