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