A Loop Optimization Technique Based on Quasi- Invariance
Litong Song, Yoshihiko Futamura, Robert Glück, Zhenjiang Hu · 2000
This paper introduces a novel technique called loop quasi-invariance code motion. It is a generalization of standard loopinvariance code motion, but based on loop quasiinvariance analysis. Loop quasi-invariance is similar to standard loop-invariance but allows for a finite number of iterations before computations in a loop become invariant. In this paper we define the notion of loop quasi-invariance, present an algorithm for statically computing the optimal unfolding length in While-programs and give a transformation method. Our method can increase the accuracy of program analyses and improve the efficiency of programs by making loops smaller and faster. Our technique is well-suited as supporting transformation in compilers, partial evaluators, and other program transformers