Program Specialization

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.

Auteur

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.

Résumé
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.

Contenu
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...