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.
Autorentext
Renaud Marlet is senior researcher at école des Ponts ParisTech (ENPC), head of the IMAGINE research group, and delegate director by interim of the Laboratoire d'Informatique Gaspard Monge (LIGM) for the école des Ponts ParisTech, France.
Zusammenfassung
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.
Inhalt
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 unr...