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-citation
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
The design of the TAO real-time object request broker
Schmidt, D. C., Levine, D. L., & Mungee, S. (1998) · Computer Communications · doi:10.1016/s0140-3664(97)00165-5 · Cited by 543
MLIR: Scaling Compiler Infrastructure for Domain Specific Computation
Lattner, C., Amini, M., Bondhugula, U., Cohen, A., Davis, A., Pienaar, J., Riddle, R., Shpeisman, T., Vasilache, N., & Zinenko, O. (2021) · 2021 IEEE/ACM International Symposium on Code Generation and Optimization (CGO) · doi:10.1109/cgo51591.2021.9370308 · Cited by 541
Henzinger, T. A., Jhala, R., Majumdar, R., & McMillan, K. L. (2014) · ACM SIGPLAN Notices · doi:10.1145/2641638.2641655 · Cited by 475
An empirical study of cryptographic misuse in android applications
Egele, M., Brumley, D., Fratantonio, Y., & Kruegel, C. (2013) · Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security - CCS '13 · doi:10.1145/2508859.2516693 · Cited by 435
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-citationStatic detection of cross-site scripting vulnerabilities
Wassermann, G., & Su, Z. (2008) · Proceedings of the 13th international conference on Software engineering - ICSE '08 · doi:10.1145/1368088.1368112 · Cited by 382
A brief survey of program slicing
Xu, B., Qian, J., Zhang, X., Wu, Z., & Chen, L. (2005) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/1050849.1050865 · Cited by 313
TAJ: effective taint analysis of web applications
Tripp, O., Pistoia, M., Fink, S. J., Sridharan, M., & Weisman, O. (2009) · Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/1542476.1542486 · Cited by 308
Henzinger, T. A., Jhala, R., Majumdar, R., & McMillan, K. L. (2004) · Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/964001.964021 · Cited by 307
Tracing the meta-level: PyPy's tracing JIT compiler
Bolz, C. F., Cuni, A., Fijalkowski, M., & Rigo, A. (2009) · Proceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems · doi:10.1145/1565824.1565827 · Cited by 282
Toward an engineering discipline for grammarware
Klint, P., Lämmel, R., & Verhoef, C. (2005) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/1072997.1073000 · Cited by 271
Execute This! Analyzing Unsafe and Malicious Dynamic Code Loading in Android Applications
Poeplau, S., Fratantonio, Y., Bianchi, A., Kruegel, C., & Vigna, G. (2014) · Proceedings 2014 Network and Distributed System Security Symposium · doi:10.14722/ndss.2014.23328 · Cited by 265
Adaptive optimization in the Jalapeño JVM
Arnold, M., Fink, S., Grove, D., Hind, M., & Sweeney, P. F. (2000) · Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications · doi:10.1145/353171.353175 · Cited by 257
FairSquare: probabilistic verification of program fairness
Albarghouthi, A., D'Antoni, L., Drews, S., & Nori, A. V. (2017) · Proceedings of the ACM on Programming Languages · doi:10.1145/3133904 · Cited by 94
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.