Efficiently computing static single assignment form and the control dependence graph

1991/10/01 by Ron K. Cytron, Jeanne Ferrante, Barry K. Rosen +2 · 1 voice · 21 citations
Computer Science · #Parallel Computing and Optimization Techniques #Software Engineering Research #Software Testing and Debugging Techniques

paper · pdf · doi:10.1145/115372.115320

openalex publication_date 1991/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

In optimizing compilers, data structure choices directly influence the power and efficiency of practical program optimization.

Citations

• Register allocation & spilling via graph coloring

Cited by

• GPU-Tile-Sim: A Tile-Centric GPU Simulation Framework for LLM Hardware-Software Co-Design
• Constraint-Level Design of zkEVMs: Architectures, Trade-offs, and Evolution
• Retrofitting Control Flow Graphs in LLVM IR for Auto Vectorization
• Don't Unroll Adjoint: Differentiating SSA-Form Programs
• Towards Verified Code Reasoning by LLMs
• Compiling without continuations
• Optimistic Concurrency Control for Real-world Go Programs (Extended Version with Appendix)
• Provably correct peephole optimizations with alive
• Technical Report about Tiramisu: a Three-Layered Abstraction for Hiding Hardware Complexity from DSL Compilers
• Dominator Tree Certification and Independent Spanning Trees
• Compiling PL/SQL Away
• Counter Attack on Byzantine Generals: Parameterized Model Checking of Fault-tolerant Distributed Algorithms
• Towards a Periodic Table of Computer System Design Principles
• How fast can we make interpreted Python?
• Quantifying Program Bias
• Sequent calculus as a compiler intermediate language
• A Multi-Dimensional, Per-Pass Empirical Study of the LLVM Optimization Pipeline
• SSA without Dominance for Higher-Order Programs
• Proving or Disproving likely Invariants with Constraint Reasoning
• Idempotent Slices with Applications to Code-Size Reduction
• Vandal: A Scalable Security Analysis Framework for Smart Contracts

Discussions

• Obviously not an exhaustive answer, but the Control Flow Graph is a common data structure, and reachability (DFS/BFS) and strongly connected components are important topics. For dependency graphs, imp [stackexchange, 6 points]

Related

• Program Composition and Optimization: An Introduction
• Enhancing Compiler Optimization Efficiency through Grammatical Decompositions of Control-Flow Graphs
• Future Directions for Optimizing Compilers
• Optimizing Compiler for Engineering Problems
• RVSDG: An Intermediate Representation for Optimizing Compilers