文档介绍：A Loop Optimization Technique Based on Quasi-
Invariance
Litong Song1, Yoshihiko Futamura1, Robert Glück1, Zhenjiang Hu2
1 Dept. of Information puter Science, Graduate School of Science and Engineering, Waseda
University, Okubo 3-4-1, Shinjuku-ku, Tokyo 169-0072, Japan,
E-mail: {slt, futamura}***@, glueck@
2 Dept. of Information Engineering, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113, Japan,
E-mail: ******@-
Techniques for code motion are basically limited
Abstract to loop-putations, this can be a problem
Loop optimization plays an important role in in automatically produced programs. Consider the
compiler optimization and program transformation. digital circuit in Fig. 1, which is simulated by the
Many sophisticated techniques such as loop- program in Fig. 2, where the simulation is carried out
invariance code motion, loop restructuring and loop for T steps. We use f, g and gi to denote functions
fusion have been developed. This paper introduces a simulating blocks.
novel technique called loop quasi-invariance code y
motion. It is a generalization of standard loop-
invariance code motion, but based on loop quasi- f
invariance analysis. Loop quasi-invariance is similar
to standard loop-invariance but allows for a finite
g
number of iterations putations in a loop
e invariant. In this paper we define the notion x1 x2 x3
of loop quasi-invariance, present an algorithm for
puting the optimal unfolding length in g1 g2 g3
While-programs and give a transformation method.
Our method can increase the accuracy of program
analyses and improve the efficiency of programs by c1 c2 c3
making loops smaller and faster. Our technique is Fig. 1. A sequential digital circuit.
well-suited as supporting transformation pilers,
partial evaluators, and other program transformers. while t<T do
x3:=g3(x2,c3);
x2:=g2(x1,c2);
1. Introduction x1:=g1(c1);
Loop-invariance code motion is a well-known loo