Reasoning About Program Transformations

✍ Scribed by Jean-Francois Collard

• Publisher: Springer
• Year: 2002
• Tongue: English
• Leaves: 256
• Edition: 1
• Category: Library

✦ Synopsis

The text contains a detailed and current presentation of the program analyses and transformations that extract the flow of data in computer memory systems. The emphasis is on a framework for the optimization of code for imperative programs and greater computer systems efficiency. In addition, the author shows that correctness of program transformations is guaranteed by the conservation of data flow. Professionals and researchers in software engineering, computer engineering, program design analysis, and compiler design will benefit from its presentation of data-flow methods and memory optimization of compilers.

✦ Table of Contents

Cover......Page 1
Reasoning About Program
Transformations......Page 4
ISBN 9780387953915......Page 5
Preface......Page 8
Contents......Page 12
1 Introduction......Page 20
1.1 Computers Have Memory......Page 21
1.2 Programs Update Memory......Page 23
1.3 What Is a Program Transformation? When Is It Correct?......Page 24
1.4 Parallelism and Parallel Languages......Page 25
1.5 Transforming a Program Into a Parallel One......Page 27
1.6 Another Typical Transformation: Expansion......Page 28
1.8 Dealing with Statement Instances......Page 30
1.9 Parameters......Page 32
1.11 What This Book Is Not About......Page 33
I Basic Concepts......Page 36
2 Describing Program Executions......Page 38
2.1 Language and Statements......Page 39
2.2 Program States, Computations, and Paths......Page 41
2.3 Statement Instances......Page 47
2.4 Memory......Page 48
2.5 Execution Order......Page 51
2.6 Relations......Page 52
2.7 Scheduling......Page 53
2.8 From Math to Compilers......Page 54
3.1 The Case of Loop Nests......Page 56
3.2 Changing the Execution Order......Page 64
3.3 The Case of Recursive Programs......Page 66
3.5 Conclusion......Page 74
II Analyses and Transformations......Page 76
4.1 Alias Analysis......Page 78
4.2 Reaching Definition Analysis......Page 80
4.3 Reaching Definition Analysis and Program Transformations......Page 83
4.4 Dominance......Page 84
4.5 Initialized, Live, and Dead Variables......Page 90
4.6 Conclusion......Page 94
5 Reaching Definition Analysis......Page 96
5.1 Iterative Reaching Definitions Analyses......Page 100
5.2 Direct Reaching Definition Analyses......Page 105
5.3 Recursive Programs......Page 131
5.4 Further Reading......Page 140
5.5 Conclusion......Page 141
6.1 Value Sharing......Page 142
6.2 Successive Reaching Definition Analyses......Page 146
6.3 Reaching Definition Analyses and Verification......Page 150
6.4 Conclusion......Page 161
7.1 Dependence Analysis......Page 162
7.2 Previous References......Page 167
7.4 Iteration-based Slicing......Page 174
7.5 Conclusion......Page 180
III Data Flow and Expansion......Page 182
8.1 Single-Assignment Form......Page 184
8.2 Static Single Assignment......Page 207
8.3 Further Reading......Page 211
8.4 Conclusion......Page 212
9 Maximal Static Expansion......Page 214
9.1 Motivating Examples......Page 215
9.2 Problem Statement......Page 219
9.3 Constructing the Maximal Static Expansion......Page 221
9.4 Back to the Examples......Page 222
9.5 Conclusion......Page 229
10.1 Parallel Languages......Page 230
10.2 Execution Order......Page 233
10.3 Reaching Definition Analysis......Page 236
10.4 (S)SA Forms for Explicitly Parallel Programs......Page 238
10.5 Further Reading......Page 240
10.6 Conclusion......Page 241
11 Conclusion: Toward Algorithm Recognition......Page 242
References......Page 248
L......Page 255
Z......Page 256