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