Lazy code motion
- 1 July 1992
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 27 (7), 224-234
- https://doi.org/10.1145/143103.143136
Abstract
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.Keywords
This publication has 18 references indexed in Scilit:
- Practical adaption of the global optimization algorithm of Morel and RenvoiseACM Transactions on Programming Languages and Systems, 1991
- Some comments on “A solution to a problem with Morel and Renvoise's 'Global optimization by suppression of partial redundancies'”ACM Transactions on Programming Languages and Systems, 1989
- A fast algorithm for code movement optimisationACM SIGPLAN Notices, 1988
- A solution to a problem with Morel and Renvoise's “Global optimization by suppression of partial redundancies”ACM Transactions on Programming Languages and Systems, 1988
- Fast Algorithms for Solving Path ProblemsJournal of the ACM, 1981
- A Unified Approach to Path ProblemsJournal of the ACM, 1981
- Applications of Path Compression on Balanced TreesJournal of the ACM, 1979
- Global optimization by suppression of partial redundanciesCommunications of the ACM, 1979
- Global Data Flow Analysis and Iterative AlgorithmsJournal of the ACM, 1976
- A Fast and Usually Linear Algorithm for Global Flow AnalysisJournal of the ACM, 1976