The Compilation of Loop Induction Expressions

ABSTRACT

In an optimizing compiler, it is often desirable to compile subscript expressions such as Abase-2 + I*2 so that the value of the expression is available in a register and is simply incremented whenever I is incremented, thus avoiding the multiplication inside the loop. This change is effected by a standard optimization called strength reduction. Program loops often contain several such expressions stemming perhaps from references to operands A(I), A(I+1), B(I), and C(K,J,I,L). Under what circumstances can we do better than keeping four addresses in four separate registers or temporaries? A general technique is presented which minimizes the number of registers needed to hold such values, while simultaneously minimizing the amount of computation inside the loop. In the above collection, it is possible to use as few as two registers for the four I-dependent values.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 2: ALLEN, F.E. Program optimization. In Annual Review in Automatic Programming, Vol. 5. Pergamon Press, New York, 1969, pp. 239-307.
• 3: ALLEN, F.E., A~D COCKE, J. A catalogue of optimizing transformations. In Design and Optimization of Compilers, R. Rustin, Ed., Prentice-Hall, Englewood Cliffs, N.J., 1972, pp. 1-30.
• 4: COCKE, J., AND SCHWARTZ, J.T. Programming languages and their compilers. Courant Inst., New York, 1971.
• 5: FTN 4.6 internal maintenance specifications, section 64--global register assignment. Control Data Corp., Minneapolis, Minn.
• 6: Edward S. Lowry , C. W. Medlock, Object code optimization, Communications of the ACM, v.12 n.1, p.13-22, Jan. 1969 [doi>10.1145/362835.362838]
• 7: J ASZK, S. Private communication.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

General Terms:
Design, Languages, Performance, Theory