Interacting Code Motion Transformations: Their Impact and Their Complexity

✍ Scribed by O Rüthing (auth.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 1998
• Tongue: English
• Leaves: 223
• Series: Lecture Notes in Computer Science 1539
• Edition: 1
• Category: Library

✦ Synopsis

Code motion techniques are integrated in many optimizing production and research compilers. They are still a major topic of ongoing research in program optimization, but traditional methods are restricted by a narrow focus on their immediate effects. A more ambitious approach is to investigate the interdependencies between distinct component transformations.
This monograph provides a comprehensive account of the methods most accepted in practice for program analysis and program transformation for imperative languages. It also develops a scenario, systematically and step by step, which overcomes the structural restrictions that had previously long resisted attack. The author presents formal proofs for all the steps leading to this breakthrough, though the reader may skip the proofs and consult the technical details as needed yet still enjoy a smooth introduction to the central principles of code motion.

✦ Table of Contents

Introduction....Pages 1-8
Basic Formalisms and Definitions....Pages 9-15
Front Matter....Pages 19-20
Optimal Expression Motion: The Single-Expression View....Pages 21-35
Optimal Expression Motion: The Multiple-Expression View....Pages 37-112
Expression Motion in the Presence of Critical Edges....Pages 113-131
Front Matter....Pages 135-136
Program Transformations Based on Assignment Motion....Pages 137-151
A Framework for Assignment Motion Based Program Transformations....Pages 153-197
Assignment Motion in the Presence of Critical Edges....Pages 199-210
Conclusions and Perspectives....Pages 211-213

✦ Subjects

Logics and Meanings of Programs; Programming Languages, Compilers, Interpreters; Software Engineering