SSA-based Compiler Design

Foreword
Preface
Contents
About the Editors
Part I Vanilla SSA
1 Introduction
1.1 Definition of SSA
1.2 Informal Semantics of SSA
1.3 Comparison with Classical Data-Flow Analysis
1.4 SSA in Context
1.5 About the Rest of This Book
1.5.1 Benefits of SSA
1.5.2 Fallacies About SSA
2 Properties and Flavours
2.1 Def-Use and Use-Def Chains
2.2 Minimality
2.3 Strict SSA Form and Dominance Property
2.4 Pruned SSA Form
2.5 Conventional and Transformed SSA Form
2.6 A Stronger Definition of Interference
2.7 Further Reading
3 Standard Construction and Destruction Algorithms
3.1 Construction
3.1.1 Join Sets and Dominance Frontiers
3.1.2 ϕ-Function Insertion
3.1.3 Variable Renaming
3.1.4 Summary
3.2 Destruction
3.3 SSA Property Transformations
3.3.1 Pessimistic ϕ-Function Insertion
3.4 Further Reading
4 Advanced Construction Algorithms for SSA
4.1 Basic Algorithm
4.2 Computation of DF+ (S) Using DJ-Graphs
4.2.1 Key Observations
4.2.2 Main Algorithm
4.3 Data-Flow Computation of DF+-Graph Using DJ-Graph
4.3.1 Top-Down DF+ Set Computation
4.4 Computing Iterated Dominance Frontier Using Loop Nesting Forests
4.4.1 Loop Nesting Forest
4.4.2 Main Algorithm
4.5 Concluding Remarks and Further Reading
5 SSA Reconstruction
5.1 General Considerations
5.2 Reconstruction Based on the Dominance Frontier
5.3 Search-Based Reconstruction
5.4 Further Reading
6 Functional Representations of SSA
6.1 Low-Level Functional Program Representations
6.1.1 Variable Assignment Versus Binding
6.1.2 Control Flow: Continuations
6.1.3 Control Flow: Direct Style
6.1.4 Let-Normal Form
6.2 Functional Construction and Destruction of SSA
6.2.1 Initial Construction Using Liveness Analysis
6.2.2 λ-Dropping
6.2.2.1 Block Sinking
6.2.2.2 Parameter Dropping
6.2.3 Nesting, Dominance, Loop-Closure
6.2.4 Destruction of SSA
6.3 Refined Block Sinking and Loop Nesting Forests
6.4 Further Reading and Concluding Remarks
Part II Analysis
7 Introduction
8 Propagating Information Using SSA
8.1 Preliminaries
8.1.1 Solving Data-Flow Problems
8.2 Data-Flow Propagation Under SSA Form
8.2.1 Program Representation
8.2.2 Sparse Data-Flow Propagation
8.2.3 Discussion
8.3 Example—Copy Propagation
8.4 Further Reading
9 Liveness
9.1 Definitions
9.2 Data-Flow Approaches
9.2.1 Liveness Sets on Reducible Graphs
9.2.1.1 Correctness
9.2.2 Liveness Sets on Irreducible Flow Graphs
9.2.3 Computing the Outermost Excluding Loop (OLE)
9.3 Liveness Check Using Loop Nesting Forest and Forward Reachability
9.3.1 Computing Modified-Forward Reachability
9.4 Liveness Sets Using Path Exploration
9.5 Further Reading
10 Loop Tree and Induction Variables
10.1 Part of the CFG and Loop Tree Can Be Exposed Through the SSA
10.1.1 An SSA Representation Without the CFG
10.1.2 Natural Loop Structures on the SSA
10.1.3 Improving the SSA Pretty Printer for Loops
10.2 Analysis of Induction Variables
10.2.1 Stride Detection
10.2.2 Translation to Chains of Recurrences
10.2.3 Instantiation of Symbols and Region Parameters
10.2.4 Number of Iterations and Computation of the End-of-Loop Value
10.3 Further Reading
11 Redundancy Elimination
11.1 Why Partial Redundancy Elimination and SSA Are Related
11.2 How SSAPRE Works
11.2.1 The Safety Criterion
11.2.2 The Computational Optimality Criterion
11.2.3 The Lifetime Optimality Criterion
11.3 Speculative PRE
11.4 Register Promotion via PRE
11.4.1 Register Promotion as Placement Optimization
11.4.2 Load Placement Optimization
11.4.3 Store Placement Optimization
11.5 Value-Based Redundancy Elimination
11.5.1 Value Numbering
11.5.2 Redundancy Elimination Under Value Numbering
11.6 Further Reading
Part III Extensions
12 Introduction
12.1 Static Single Information Form
12.2 Control Dependencies
12.3 Gated SSA Forms
12.4 Psi-SSA Form
12.5 Hashed SSA Form
12.6 Array SSA Form
12.7 Memory-Based Data Flow
13 Static Single Information Form
13.1 Static Single Information
13.1.1 Sparse Analysis
13.1.2 Partitioned Lattice per Variable (PLV) Problems
13.1.3 The Static Single Information Property
13.1.4 Special Instructions Used to Split Live Ranges
13.1.5 Propagating Information Forward and Backward
13.1.6 Examples of Sparse Data-Flow Analyses
13.2 Construction and Destruction of the Intermediate Program Representation
13.2.1 Splitting Strategy
13.2.2 Splitting Live Ranges
13.2.3 Variable Renaming
13.2.4 Dead and Undefined Code Elimination
13.2.5 Implementation Details
13.3 Further Reading
14 Graphs and Gating Functions
14.1 Data-Flow Graphs
14.2 The SSA Graph
14.2.1 Finding Induction Variables with the SSA Graph
14.3 Program Dependence Graph
14.3.1 Detecting Parallelism with the PDG
14.4 Gating Functions and GSA
14.4.1 Backward Symbolic Analysis with GSA
14.5 Value State Dependence Graph
14.5.1 Definition of the VSDG
14.5.2 Dead Node Elimination with the VSDG
14.6 Further Reading
15 Psi-SSA Form
15.1 Definition and Construction
15.2 SSA Algorithms
15.3 Psi-SSA Algorithms
15.4 Psi-SSA Destruction
15.4.1 Psi-Normalize
15.4.2 Psi-web
15.5 Further Reading
16 Hashed SSA Form: HSSA
16.1 SSA and Aliasing: μ- and χ-Functions
16.2 Introducing ``Zero Versions'' to Limit Version Explosion
16.3 SSA for Indirect Memory Operations: Virtual Variables
16.4 Using GVN to Form HSSA
16.5 Building HSSA
16.6 Further Reading
17 Array SSA Form
17.1 Array SSA Form
17.2 Sparse Constant Propagation of Array Elements
17.2.1 Array Lattice for Sparse Constant Propagation
17.2.2 Beyond Constant Indices
17.3 Extension to Objects: Redundant Load Elimination
17.3.1 Analysis Framework
17.3.2 Definitely Same and Definitely Different Analyses for Heap Array Indices
17.3.3 Scalar Promotion Algorithm
17.4 Further Reading
Part IV Machine Code Generation and Optimization
18 SSA Form and Code Generation
18.1 SSA Form Engineering Issues
18.1.1 Instructions, Operands, Operations, and Operators
18.1.2 Representation of Instruction Semantics
18.1.3 Operand Naming Constraints
18.1.4 Non-kill Target Operands
18.1.5 Program Representation Invariants
18.2 Code Generation Phases and the SSA Form
18.2.1 If-Conversion
18.2.2 Prepass Instruction Scheduling
18.3 SSA Form Destruction Algorithms
19 Instruction Code Selection
19.1 Instruction Code Selection for Tree Patterns on SSA Graphs
19.1.1 Partitioned Boolean Quadratic Problem
19.1.2 Instruction Code Selection with PBQP
19.2 Extensions and Generalizations
19.2.1 Instruction Code Selection for DAG Patterns
19.3 Concluding Remarks and Further Reading
20 If-Conversion
20.1 Architectural Requirements
20.2 Basic Transformations
20.2.1 SSA Operations on Basic Blocks
20.2.2 Handling of Predicated Execution Model
20.3 Global Analysis and Transformations
20.3.1 SSA Incremental If-Conversion Algorithm
20.3.2 Tail Duplication
20.3.3 Profitability
20.4 Concluding Remarks and Further Reading
21 SSA Destruction for Machine Code
21.1 Correctness
21.2 Code Quality
21.3 Speed and Memory Footprint
21.4 Further Reading
22 Register Allocation
22.1 Introduction
22.1.1 Questions for Register Allocators
22.1.2 Maxlive and Variable Splitting
22.1.3 The Spill Test Under SSA
22.2 Spilling
22.2.1 Graph-Based Approach
22.2.2 Scan-Based Approach
22.3 Colouring and Coalescing
22.3.1 Greedy Colouring Scheme
22.3.2 Coalescing Under SSA Form
22.3.3 Graph-Based Approach
22.3.4 Scan-Based Approach
22.4 Practical Discussions and Further Reading
23 Hardware Compilation Using SSA
23.1 Brief History and Overview
23.2 Why Use SSA for Hardware Compilation?
23.3 Mapping a Control-Flow Graph to Hardware
23.3.1 Basic Block Mapping
23.3.2 Basic Control-Flow Graph Mapping
23.3.3 Control-Flow Graph Mapping Using SSA
23.3.4 ϕ-Function and Multiplexer Optimizations
23.3.5 Implications of Using SSA Form in Floor Planning
23.4 Existing SSA-Based Hardware Compilation Efforts
24 Building SSA in a Compiler for PHP
24.1 SSA Form in Statically Typed Languages
24.2 PHP and Aliasing
24.3 Our Whole-Program Analysis
24.3.1 The Analysis Algorithm
24.3.2 Analysis Results
24.3.3 Building Def-Use Sets
24.3.4 HSSA
24.4 Other Challenging PHP Features
24.4.1 Runtime Symbol Tables
24.4.2 Execution of Arbitrary Code
24.4.3 Object Handlers
24.5 Concluding Remarks and Further Reading
References
Index