This book presents the principles and techniques of program specialization — a general method to make programs faster (and possibly smaller) when some inputs can be known in advance. As an illustration, it describes the architecture of Tempo, an offline program specializer for C that can also specialize code at runtime, and provides figures for concrete applications in various domains. Technical details address issues related to program analysis precision, value reification, incomplete program specialization, strategies to exploit specialized program, incremental specialization, and data specialization. The book, that targets both researchers and software engineers, also opens scientific and industrial perspectives.
Table of Contents:
Chapter 1. Main Principles of Program Specialization 1
1.1. Specialized program 2
1.2. Specializing to improve performance 16
1.3. Automatic specialization 22
1.4. Main applications of specialization 27
1.5. Specialization times 33
1.6. Financial viability of specialization 37
Chapter 2. Specialization Techniques 43
2.1. Transforming specialization programs 44
2.2. Termination of specialization 57
2.3. Correctness of specialization 60
2.4. Other forms of specialization 65
Chapter 3. Offline Specialization 71
3.1. Main principles of offline specialization 72
3.2. Compared advantages of offline specialization 92
3.3. Main components of binding-time analysis 99
3.4. When static inputs become dynamic 109
Chapter 4. A Specializer for C: Tempo 117
4.1. History 118
4.2. Disruptive technologies 121
4.3. Architecture 123
4.4. Engineering economics 132
4.5. Beyond Tempo 139
4.6. Other specializers for the C language 142
Chapter 5. Applications of Specialization 145
5.1. Applications in operating systems and networks 146
5.2. Applications to numerical computation 159
5.3. Applications to compilation using an interpreter 160
5.4. Applications to the optimization of software architectures 164
5.5. Specialization as a software engineering tool 180
Chapter 6. Precision of Program Analysis 185
6.1. Choosing the precision of an analysis 186
6.2. Sensitivity to (control) flow 189
6.3. Sensitivity to speculative evaluation 193
6.4. Sensitivity to data structure components 194
6.5. Sensitivity to data structure instances 196
6.6. Sensitivity to use (of memory locations) 201
6.7. Sensitivity to use of literal constants 208
6.8. Intraprocedural versus interprocedural analysis 211
6.9. Sensitivity to the context (of function call) 213
6.10. Sensitivity to the return value 214
6.11. Other precision forms 216
6.12. Precision of the existing C specializers 217
Chapter 7. Reification: From a Value to a Term 221
7.1. Different types of reification 222
7.2. Constraints of lifting 226
7.3. Lifting of immutable data 231
7.4. Lifting of a non-shared mutable piece of data 234
7.5. Reification of a shared mutable piece of data 237
7.6. Reification of a reference 238
7.7. Physical data sharing between execution times 243
7.8. Reification and binding time 245
Chapter 8. Specialization of Incomplete Programs 249
8.1. Constraints on the code to be specialized 250
8.2. Specialization module and language module 254
8.3. Revision of the expression of specialization 256
8.4. Calling context of a function to be specialized 264
8.5. Effect of external function calls 266
8.6. Abstract modeling languages 269
8.7. Concrete modeling 272
Chapter 9. Exploitation of Specialization 283
9.1. Means of exploiting specialization 284
9.2. Invariant execution context 286
9.3. Optimistic specialization 288
9.4. Selection by necessity of a specialized function 294
9.5. Selection by anticipation of a specialized function 298
Chapter 10. Incremental Runtime Specialization 309
10.1. Data availability staging 310
10.2. Models for incremental specialization 313
10.3. Binding-time analyses for incremental specialization 322
10.4. Implementation 323
10.5. Compared advantages of iterated specialization 335
10.6. Related works 339
10.7. Improving incremental runtime specialization 341
Chapter 11. Data Specialization 343
11.1. Program specialization and loop unrolling 344
11.2. General concept of data specialization 350
11.3. Caching and binding time 360
11.4. Structuring the cache 365
11.5. The question of control in data specialization 371
11.6. Reconstructions of control 375
11.7. Program specialization versus data specialization 382
11.8. Experimental results 387
Chapter 12. Scientific Perspectives 393
12.1. Improving the specialized code 394
12.2. Complexity of the process of specialization 404
12.3. Simplifying the process of specialization 408
12.4. Integration into a software engineering process 418
Chapter 13. Conclusion: From Prototype to Product 421
13.1. The race for performance 422
13.2. A different viewpoint 423
13.3. Difficulties for investing in software engineering 425
13.4. Niche uses 429
13.5. Developing a specialization platform 432
Appendix. Basic Facts about Languages and Programs 435
Bibliography 487
Index 523
