Program Specialization (Hardcover)

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