Lazy code motion
Jens Knoop, Oliver Rüthing, Bernhard Steffen · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · 1992
We present a bit-vector algorithm for the optimal and economical placement of computations within flow graphs, which is as efficient as standard uni-directional analyses. The point of our algorithm is the decomposition of the bi-directional structure of the known placement algorithms into a sequence of a backward and a forward analysis, which directly implies the efficiency result. Moreover, the new compositional structure opens the algorithm for modification: two further uni-directional analysis components exclude any unnecessary code motion. This laziness of our algorithm minimizes the register pressure, which has drastic effects on the run-time behaviour of the optimized programs in practice, where an economical use of registers is essential.
Cited by 259 works. doi:10.1145/143095.143136 Open-access PDF
Authors
References
- Flow Analysis of Computer Programs
- Programming languages and their compilers: Preliminary notes
- A Fast and Usually Linear Algorithm for Global Flow Analysis
- Applications of Path Compression on Balanced Trees
- Global Data Flow Analysis and Iterative Algorithms
- Fast algorithms for the elimination of common subexpressions
- A Simple Algorithm for Global Data Flow Analysis Problems
- Global optimization by suppression of partial redundancies
- Monotone data flow analysis frameworks
- Analysis of a simple algorithm global data flow problems