SSA-based Compiler Design

Description

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