第1页 / 共415页
第2页 / 共415页
第3页 / 共415页
第4页 / 共415页
第5页 / 共415页
第6页 / 共415页
第7页 / 共415页
第8页 / 共415页
Static Single Assignment Book.pdf
Part I Vanilla SSA
1 Introduction — (J. Singer)
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 — (P. Brisk , F. Rastello)
2.1 Preliminaries
2.2 Def-Use and Use-Def Chains
2.3 Minimality
2.4 Strict SSA Form and Dominance Property
2.5 Pruned SSA Form
2.6 Conventional and Transformed SSA Form
2.7 A Stronger Definition of Interference
2.8 Further readings
3 Standard Construction and Destruction Algorithms — (J. Singer , F. Rastello)
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 Additional reading
4 Advanced Construction Algorithms for SSA — (D. Das , U. Ramakrishna , V. Sreedhar)
4.1 Introduction
4.2 Basic Algorithm
4.3 Computation of DF+ (S) using DJ-graphs
4.3.1 Key Observations
4.3.2 Main Algorithm
4.4 Data-flow computation of DF+-graph using DJ-graph
4.4.1 Top Down DF+ Set Computation
4.5 Computing Iterated Dominance Frontier Using Loop Nesting Forests
4.5.1 Loop nesting forest
4.5.2 Main Algorithm
4.6 Concluding Remarks
4.7 Further Reading
5 SSA Reconstruction — (S. Hack)
5.1 Introduction
5.1.1 Live-Range Splitting
5.1.2 Jump Threading
5.2 General Considerations
5.3 Reconstruction based on the Dominance Frontier
5.4 Search-based Reconstruction
5.5 Conclusions
6 Functional representations of SSA — (L. Beringer)
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.3 Nesting, dominance, loop-closure
6.2.4 Destruction of SSA
6.3 Refined block sinking and loop nesting forests
6.4 Pointers to the literature
6.5 Concluding remarks
Part II Analysis
7 Introduction — (M. Schordan and F. Rastello)
7.1 Propagation Engine
7.2 Structural properties
7.3 Sparse Analysis
8 Propagating Information using SSA— (F. Brandner , D. Novillo)
8.1 Overview
8.2 Preliminaries
8.2.1 Solving Data-flow Problems
8.3 Data-flow Propagation under SSA Form
8.3.1 Program Representation
8.3.2 Sparse Data-flow Propagation
8.3.3 Discussion
8.3.4 Limitations
8.4 Example—Copy Propagation
8.5 Further Reading
9 Liveness — (B. Boissinot , F. Rastello)
9.1 Introduction
9.2 Definitions
9.3 Data-Flow Approaches
9.3.1 Liveness Sets On Reducible Graphs
9.3.2 Liveness Sets on Irreducible Flow Graphs
9.3.3 Computing the Outermost Excluding Loop (OLE)
9.4 Liveness Check using Loop Nesting Forest and Forward Reachability
9.4.1 Computing the modified-forward reachability
9.5 Liveness Sets using Path Exploration
9.6 Further readings
10 Loop tree and induction variables — (S. Pop , A. Cohen)
10.1 Part of the CFG and Loop Tree can be exposed from 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— (F. Chow)
11.1 Introduction
11.2 Why partial redundancy elimination and SSA are related
11.3 How SSAPRE Works
11.3.1 The Safety Criterion
11.3.2 The Computational Optimality Criterion
11.3.3 The Lifetime Optimality Criterion
11.4 Speculative PRE
11.5 Register Promotion via PRE
11.5.1 Register Promotion as Placement Optimization
11.5.2 Load Placement Optimization
11.5.3 Store Placement Optimization
11.6 Value-based Redundancy Elimination
11.6.1 Value Numbering
11.7 Advanced Discussions and Further Readings
Part III Extensions
12 Introduction — (V. Sarkar , F. Rastello)
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 — (F. Pereira , F. Rastello)
13.1 Introduction
13.2 Static Single Information
13.2.1 Sparse Analysis
13.2.2 Partitioned Lattice per Variable (PLV) Problems
13.2.3 The Static Single Information Property
13.2.4 Special instructions used to split live-ranges
13.2.5 Propagating Information Forward and Backward
13.2.6 Examples of sparse data-flow analyses
13.3 Construction and Destruction of the Intermediate Program Representation
13.3.1 Splitting strategy
13.3.2 Splitting live-ranges
13.3.3 Variable Renaming
13.3.4 Dead and Undefined Code Elimination
13.3.5 Implementation Details
13.4 Further Reading
14 Graphs and gating functions — (J. Stanier)
14.1 Introduction
14.2 Data-flow Graphs
14.3 The SSA Graph
14.3.1 Finding induction variables with the SSA Graph
14.4 Program Dependence Graph
14.4.1 Detecting parallelism with the PDG
14.5 Gating functions and GSA
14.5.1 Backwards symbolic analysis with GSA
14.6 Value State Dependence Graph
14.6.1 Definition of the VSDG
14.6.2 Nodes
14.6.3 -Nodes
14.6.4 -Nodes
14.6.5 State Nodes
14.6.6 Dead node elimination with the VSDG
14.7 Further readings
15 Psi-SSA Form — (F. de Ferrière)
15.1 Overview
15.2 Definition and Construction
15.3 SSA algorithms
15.4 Psi-SSA algorithms
15.5 Psi-SSA destruction
15.5.1 Psi-normalize
15.5.2 Psi-web
15.6 Additional reading
16 Hashed SSA form: HSSA — (M. Mantione , F. Chow)
16.1 Introduction
16.2 SSA and aliasing: and -functions
16.3 Introducing ``zero versions'' to limit the explosion of the number of variables
16.4 SSA and indirect memory operations: virtual variables
16.5 GVN and indirect memory operations: HSSA
16.6 Building HSSA
16.7 Using HSSA
16.8 Further readings
17 Array SSA Form — (Vivek Sarkar , Kathleen Knobe , Stephen Fink)
17.1 Introduction
17.2 Array SSA Form
17.3 Sparse Constant Propagation of Array Elements
17.3.1 Array Lattice for Sparse Constant Propagation
17.3.2 Beyond Constant Indices
17.4 Extension to Objects: Redundant Load Elimination
17.4.1 Analysis Framework
17.4.2 Definitely-Same and Definitely-Different Analyses for Heap Array Indices
17.4.3 Scalar Replacement Algorithm
17.5 Further Reading
Part IV Machine code generation and optimization
18 SSA form and code generation — (B. Dupont de Dinechin)
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 Classic if-conversion
18.2.2 If-conversion under SSA form
18.2.3 Pre-pass instruction scheduling
18.3 SSA form destruction algorithms
19 Instruction Code Selection — (D. Ebner , A. Krall , B. Scholz)
19.1 Introduction
19.2 Instruction Code Selection for Tree Patterns on SSA-Graphs
19.2.1 Partitioned Boolean Quadratic Problem
19.2.2 Instruction Code Selection with PBQP
19.3 Extensions and Generalizations
19.3.1 Instruction Code Selection for DAG Patterns
19.4 Summary and Further Reading
20 If-Conversion — (C. Bruel)
20.1 Introduction
20.1.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 Conclusion
20.5 Additional reading
21 SSA destruction for machine code — (F. Rastello)
21.1 Introduction
21.2 Correctness
21.3 Code Quality
21.4 Speed and Memory Footprint
21.5 Further Readings
22 Register Allocation— (F. Bouchez , S. Hack)
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 Coloring and coalescing
22.3.1 Greedy coloring 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 Readings
23 Hardware Compilation using SSA— (Pedro C. Diniz , Philip Brisk)
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-planing
23.4 Existing SSA-based hardware compilation efforts
24 Building SSA form in a compiler for PHP — (Paul Biggar and David Gregg, Lero@TCD, Trinity College Dublin)
24.1 Introduction
24.2 SSA form in ``traditional'' languages
24.3 PHP and aliasing
24.4 Our whole-program analysis
24.4.1 The analysis algorithm
24.4.2 Analysis results
24.4.3 Building def-use sets
24.4.4 HSSA
24.5 Other challenging PHP features
24.5.1 Run-time symbol tables
24.5.2 Execution of arbitrary code
24.5.3 Object handlers
24.6 Discussion, implications and conclusion
References
1
Lots of authors
Static Single Assignment Book
Sunday 13th May, 2018
22:27
filled with the actual
book, for instance the start
chapter. To be filled with the ac-
book, for instance the start of the introduc-
filled with the actual beginning of the book,
tion chapter. To be filled
book,
for instance the
the introduc-
the
chapter.
for
in-
2
To
be
beginning of the
of the introduction
tual beginning of the
tion chapter. To be
for instance the start
with the actual be-
start of the introduc-
tual beginning of the
chap-
introduction
ginning of the book,
tion chapter. To be
book, for instance
To be filled with
instance the start
filled with the
stance the start
be filled with
for instance the
To be filled with
for instance the start
be filled with the ac-
stance the start of the
with the actual be-
start of the intro-
the actual begin-
start of the intro-
the actual begin-
start of the introduc-
tual beginning of the
introduction
chap-
ning of the book, for
chapter. To be filled
book, for instance the
To be filled with the
stance the start of the
with the actual begin-
start of the introduc-
tual beginning of the
troduction chapter. To
the book, for instance the
filled with the actual be-
of the introduction chap-
the book, for instance the
with the actual beginning
the
of
ginning of
tion
book,
ter. To be filled
for instance the
filled with the ac-
the start of the in-
the actual begin-
of
the introduc-
actual beginning
of
the introduc-
the actual begin-
start of the intro-
the actual begin-
of
introduc-
tual beginning of
introduction chap-
ginning of the book,
duction
chapter.
ning of the book,
duction
chapter.
ning of the book,
tion chapter. To be
book,
instance
ter. To be filled with
instance the start of
with the actual be-
start of
the intro-
actual beginning of
introduction chap-
ning of the book,
tion chapter. To be
book,
instance
be filled with the ac-
start of the introduc-
ginning of the book,
ter. To be filled with
start of the introduc-
of the book, for instance
for
for
To be filled with the ac-
stance the start of the
with the actual be-
start of the introduc-
tual beginning of the
troduction
chapter.
ning of the book, for
tion chapter. To be
of the book, for in-
tion chapter. To
ning of the book,
duction chapter.
ning of the book,
tion chapter. To
the book, for in-
ter. To be filled
for instance the
To be filled with
for instance the
To be filled with
for
the
filled with the ac-
the start of
the
the actual begin-
the introduction
ginning of
the
duction chapter.
the book, for in-
ter. To be filled
for instance the
filled with the ac-
the start of the in-
instance
tual beginning of
tion chapter. To be
for instance the start
the actual beginning of
tion chapter. To be filled
the start of the introduc-
tion chapter. To be filled with the actual beginning of the book, for instance
the start of the introduction chapter. To be filled with the actual beginning
of the book, for instance the start of the introduction chap-
ter. To be filled with the actual be-
ginning of the book,
for instance the start
of
the introduction
chapter. To be filled
with the actual begin-
ning of the book, for in-
stance the start of the
introduction chapter.
To be filled with the
actual beginning of
the book, for instance
the start of the intro-
duction chapter. To
be filled with the
actual
beginning
of the book, for in-
the
stance
start
of
the
introduc-
tion chapter. To be
filled with the ac-
tual beginning of
the book, for in-
stance the start of
the introduction
chapter.
Springer
Contents
Part I Vanilla SSA
1
2
3
Informal Semantics of SSA
Introduction — (J. Singer) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1 Definition of SSA
1.2
1.3 Comparison with Classical Data-flow Analysis
1.4 SSA in Context
1.5 About the Rest of this Book
5
1.5.1 Benefits of SSA
1.5.2 Fallacies about SSA
Properties and flavours — (P. Brisk, F. Rastello) . . . . . . . . . . . . . . . . . . . . . . . 15
2.1 Preliminaries
2.2 Def-Use and Use-Def Chains
2.3 Minimality
2.4 Strict SSA Form and Dominance Property
2.5 Pruned SSA Form
2.6 Conventional and Transformed SSA Form
2.7 A Stronger Definition of Interference
2.8 Further readings
Standard Construction and Destruction Algorithms — (J. Singer,
F. Rastello) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1 Construction
Join Sets and Dominance Frontiers
3.1.1
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 Additional reading
v
vi
4
5
Contents
Advanced Construction Algorithms for SSA — (D. Das,
U. Ramakrishna, V. Sreedhar) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.1
4.2 Basic Algorithm
4.3 Computation of DF+(S) using DJ-graphs
Introduction
4.3.1 Key Observations
4.3.2 Main Algorithm
4.4 Data-flow computation of DF+-graph using DJ-graph
4.4.1 Top Down DF+ Set Computation
4.5 Computing Iterated Dominance Frontier Using Loop Nesting Forests
4.5.1 Loop nesting forest
4.5.2 Main Algorithm
4.6 Concluding Remarks
4.7 Further Reading
SSA Reconstruction — (S. Hack) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.1
Introduction
5.1.1 Live-Range Splitting
5.1.2
Jump Threading
5.2 General Considerations
5.3 Reconstruction based on the Dominance Frontier
5.4 Search-based Reconstruction
5.5 Conclusions
6
Functional representations of SSA — (L. Beringer) . . . . . . . . . . . . . . . . . . . . 67
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
Initial construction using liveness analysis
6.2.1
6.2.2 λ-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 Pointers to the literature
6.5 Concluding remarks
Part II Analysis
7
Introduction — (M. Schordan and F. Rastello) . . . . . . . . . . . . . . . . . . . . . . . . . 97
7.1 Propagation Engine
7.2 Structural properties
7.3 Sparse Analysis
Contents
vii
8
Propagating Information using SSA— (F. Brandner, D. Novillo) . . . . . . 101
8.1 Overview
8.2 Preliminaries
8.2.1
Solving Data-flow Problems
8.3 Data-flow Propagation under SSA Form
Sparse Data-flow Propagation
8.3.1 Program Representation
8.3.2
8.3.3 Discussion
8.3.4 Limitations
8.4 Example—Copy Propagation
8.5 Further Reading
9
Introduction
Liveness — (B. Boissinot, F. Rastello) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
9.1
9.2 Definitions
9.3 Data-Flow Approaches
9.3.1 Liveness Sets On Reducible Graphs
9.3.2 Liveness Sets on Irreducible Flow Graphs
9.3.3 Computing the Outermost Excluding Loop (OLE)
9.4 Liveness Check using Loop Nesting Forest and Forward Reachability
9.4.1 Computing the modified-forward reachability
9.5 Liveness Sets using Path Exploration
9.6 Further readings
10 Loop tree and induction variables — (S. Pop, A. Cohen) . . . . . . . . . . . . . . . 131
10.1 Part of the CFG and Loop Tree can be exposed from 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— (F. Chow) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
11.1 Introduction
11.2 Why partial redundancy elimination and SSA are related
11.3 How SSAPRE Works
11.3.1 The Safety Criterion
11.3.2 The Computational Optimality Criterion
11.3.3 The Lifetime Optimality Criterion
11.4 Speculative PRE
11.5 Register Promotion via PRE
11.5.1 Register Promotion as Placement Optimization
viii
Contents
11.5.2 Load Placement Optimization
11.5.3 Store Placement Optimization
11.6 Value-based Redundancy Elimination
11.6.1 Value Numbering
11.7 Advanced Discussions and Further Readings
Part III Extensions
12 Introduction — (V. Sarkar, F. Rastello) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
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 — (F. Pereira, F. Rastello) . . . . . . . . . . . . . 173
13.1 Introduction
13.2 Static Single Information
13.2.1 Sparse Analysis
13.2.2 Partitioned Lattice per Variable (PLV) Problems
13.2.3 The Static Single Information Property
13.2.4 Special instructions used to split live-ranges
13.2.5 Propagating Information Forward and Backward
13.2.6 Examples of sparse data-flow analyses
13.3 Construction and Destruction of the Intermediate Program
Representation
13.3.1 Splitting strategy
13.3.2 Splitting live-ranges
13.3.3 Variable Renaming
13.3.4 Dead and Undefined Code Elimination
13.3.5 Implementation Details
13.4 Further Reading
14 Graphs and gating functions — (J. Stanier) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
14.1 Introduction
14.2 Data-flow Graphs
14.3 The SSA Graph
14.3.1 Finding induction variables with the SSA Graph
14.4 Program Dependence Graph
14.4.1 Detecting parallelism with the PDG
14.5 Gating functions and GSA
14.5.1 Backwards symbolic analysis with GSA
14.6 Value State Dependence Graph
14.6.1 Definition of the VSDG
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
