Operator strength reduction

ABSTRACT

Operator strength reduction is a technique that improves compiler-generated code by reformulating certain costly computations in terms of less expensive ones. A common case arises in array addressing expressions used in loops. The compiler can replace the sequence of multiplies generated by a direct translation of the address expression with an equivalent sequence of additions. When combined with linear function test replacement, strength reduction can speed up the execution of loops containing array references. The improvement comes from two sources: a reduction in the number of operations needed to implement the loop and the use of less costly operations.This paper presents a new algorithm for operator strength reduction, called OSR. OSR improves upon an earlier algorithm of Allen, Cocke, and Kennedy [Allen et al. 1981]. OSR operates on the static single assignment (SSA) form of a procedure [Cytron et al. 1991]. By taking advantage of the properties of SSA form, we have derived an algorithm that is simple to understand, quick to implement, and, in practice, fast to run. Its asymptotic complexity is, in the worst case, the same as the Allen, Cocke,and Kennedy algorithm (ACK). OSR achieves optimization results that are equivalent to those obtained with the ACK algorithm. OSR has been implemented in several research and production compilers.

REFERENCES

• 1: ALLEN, F. E. 1969. Program optimization. Annual Review in Automatic Programming 5, 239-308.
• 2: ALLEN, F. E., COCKE,J.,AND KENNEDY, K. 1981. Reduction of operator strength. In Program Flow Analysis: Theory and Applications, S. S. Muchnick and N. D. Jones, Eds. Prentice-Hall, Englewood Cliffs, NJ, USA.
• 3: B. Alpern , M. N. Wegman , F. K. Zadeck, Detecting equality of variables in programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73561]
• 4: R Bernstein, Multiplication by Integer constants, Software—Practice & Experience, v.16 n.7, p.641-652, July. 1986 [doi>10.1002/spe.4380160704]
• 5: Rastislav Bodík , Rajiv Gupta , Mary Lou Soffa, Complete removal of redundant expressions, ACM SIGPLAN Notices, v.33 n.5, p.1-14, May 1998
• 6: Preston Briggs , Keith D. Cooper, Effective partial redundancy elimination, ACM SIGPLAN Notices, v.29 n.6, p.159-170, June 1994
• 7: Preston Briggs , Keith D. Cooper , Timothy J. Harvey , L. Taylor Simpson, Practical improvements to the construction and destruction of static single assignment form, Software—Practice & Experience, v.28 n.8, p.859-881, July 10, 1998 [doi>10.1002/(SICI)1097-024X(19980710)28:8<859::AID-SPE188>3.0.CO;2-8]
• 8: Preston Briggs , Keith D. Cooper , L. Taylor Simpson, Value numbering, Software—Practice & Experience, v.27 n.6, p.701-724, June 1997 [doi>10.1002/(SICI)1097-024X(199706)27:6<701::AID-SPE104>3.3.CO;2-S]
• 9: Preston Briggs , Keith D. Cooper , Linda Torczon, Improvements to graph coloring register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.428-455, May 1994 [doi>10.1145/177492.177575]
• 10: BRIGGS,P.AND HARVEY, T. J. 1994. Multiplication by integer constants. This is a "web", a literate programming document. See http://softlib.rice.edu/MSCP.
• 11: Jiazhen Cai , Robert A. Paige, Look ma, no hashing, and no arrays neither, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.143-154, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99605]
• 12: CHAITIN,G.J.,AUSLANDER, M. A., CHANDRA, A. K., COCKE, J., HOPKINS,M.E.,AND MARKSTEIN,P.W. 1981. Register allocation via coloring. Computer Languages 6, 47-57.
• 13: CHASE, D. R. 1988. Personal communication in the form of an unpublished report.
• 14: Jong-Deok Choi , Ron Cytron , Jeanne Ferrante, Automatic construction of sparse data flow evaluation graphs, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.55-66, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99594]
• 15: Cliff Click , Keith D. Cooper, Combining analyses, combining optimizations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.181-196, March 1995 [doi>10.1145/201059.201061]
• 16: John Cocke , Ken Kennedy, An algorithm for reduction of operator strength, Communications of the ACM, v.20 n.11, p.850-856, Nov. 1977 [doi>10.1145/359863.359888]
• 17: COCKE,J.AND MARKSTEIN, P. 1980a. Measurement of program improvement algorithms. In Proceedings of Information Processing 80. North Holland Publishing Company, Tokyo, Japan.
• 18: COCKE,J.AND MARKSTEIN, P. 1980b. Strength reduction for division and modulo with application to a multilevel store. IBM J. Res. Dev. 24, 6, 692-694.
• 19: COCKE,J.AND SCHWARTZ, J. T. 1970. Programming languages and their compilers: Preliminary notes. Tech. rep., Courant Institute of Mathematical Sciences, New York University.
• 20: COOPER,K.D.AND SIMPSON, L. T. 1995. SCC-based value numbering. Tech. Rep. TR95636, Center for Research on Parallel Computation, Rice University. Oct.
• 21: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 22: DHAMDHERE, D. M. 1979. On algorithms for operator strength reduction. Communications of the ACM 22, 5 (May), 311-312.
• 23: DHAMDHERE, D. M. 1989. A new algorithm for composite hoisting and strength reduction. Int. J. Comput. Math. 27, 1, 1-14.
• 24: Karl-Heinz Drechsler , Manfred P. Stadel, A variation of Knoop, Rüthing, and Steffen's Lazy Code Motion, ACM SIGPLAN Notices, v.28 n.5, p.29-38, May 1993 [doi>10.1145/152819.152823]
• 25: EARLY, J. 1974. High level iterators and a method of automatically designing data structure representation. Tech. Rep. ERL-M416, Computer Science Division, University of California, Berkeley. Feb.
• 26: Amelia C. Fong, Inductively computable constructs in very high level languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.21-28, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567755]
• 27: Amelia C. Fong , Jeffrey D. Ullman, Induction variables in very high level languages, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.104-112, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811544]
• 28: GRANLUND, T. 1995. Private communication with P. Briggs. Discussion of his work in building the routine synth mult for the Gnu C Compiler.
• 29: Torbjörn Granlund , Peter L. Montgomery, Division by invariant integers using multiplication, ACM SIGPLAN Notices, v.29 n.6, p.61-72, June 1994
• 30: Rajiv Gupta , David A. Berson , Jesse Z. Fang, Path Profile Guided Partial Redundancy Elimination Using Speculation, Proceedings of the 1998 International Conference on Computer Languages, p.230, May 14-16, 1998
• 31: Paul Havlak, Nesting of reducible and irreducible loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.4, p.557-567, July 1997 [doi>10.1145/262004.262005]
• 32: ISSAC,J.AND DHAMDHERE, D. M. 1980. A composite algorithm for strength reduction and code movement. Int. J. Comput. Info. Sci. 9, 3, 243-273.
• 33: John B. Kam , Jeffrey D. Ullman, Global Data Flow Analysis and Iterative Algorithms, Journal of the ACM (JACM), v.23 n.1, p.158-171, Jan. 1976 [doi>10.1145/321921.321938]
• 34: KENNEDY, K. 1973. Reduction in strength using hashed temporaries. SETL Newsletter 102, Courant Institute of Mathematical Sciences, New York University. Mar.
• 35: KENNEDY, K. 1978. Use-definition chains with applications. Computer Languages 3, 163- 179.
• 36: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Lazy code motion, ACM SIGPLAN Notices, v.27 n.7, p.224-234, July 1992
• 37: KNOOP, J., RUTHING,O.,AND STEFFEN, B. 1993. Lazy strength reduction. J. Program. Lang. 1,1, 71-91.
• 38: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Optimal code motion: theory and practice, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1117-1155, July 1994 [doi>10.1145/183432.183443]
• 39: Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979 [doi>10.1145/357062.357071]
• 40: Yanhong A. Liu , Scott D. Stoller, Loop optimization for aggregate array computations, Proceedings of the 1998 International Conference on Computer Languages, p.262, May 14-16, 1998
• 41: MARKSTEIN,P.W.,MARKSTEIN,V.,AND ZADECK, F. K. 1994. Reassociation and strength reduction. Chapter from an unpublished book, Optimization in Compilers.
• 42: E. Morel , C. Renvoise, Global optimization by suppression of partial redundancies, Communications of the ACM, v.22 n.2, p.96-103, Feb. 1979 [doi>10.1145/359060.359069]
• 43: Robert Paige , Shaye Koenig, Finite Differencing of Computable Expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.402-454, July 1982 [doi>10.1145/357172.357177]
• 44: Bob Paige , J. T. Schwartz, Expression continuity and the formal differentiation of algorithms, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.58-71, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512957]
• 45: SANTHANAM, V. 1992. Register reassociation in PA-RISC compilers. Hewlett-Packard Journal 14,6 (June), 33-38.
• 46: SCARBOROUGH,R.G.AND KOLSKY, H. G. 1980. Improved optimization of FORTRAN object programs. IBM J. Res. Dev. 24, 6 (Nov.), 660-676.
• 47: Richard L. Sites, The Compilation of Loop Induction Expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.50-57, July 1979 [doi>10.1145/357062.357065]
• 48: TARJAN, R. E. 1972. Depth first search and linear graph algorithms. SIAM J. Comput. 1, 2 (June), 146-160.
• 49: TARJAN, R. E. 1974. Testing flow graph reducibility. J. Comput. Syst. Sci. 9, 355-365.
• 50: VICK, C. A. 1994. SSA based reduction of operator strength. M.S. dissertation, Rice University, Department of Computer Science.
• 51: Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991 [doi>10.1145/103135.103136]
• 52: Michael Wolfe, Beyond induction variables, ACM SIGPLAN Notices, v.27 n.7, p.162-174, July 1992
• 53: Youfeng Wu, Strength reduction of multiplications by integer constants, ACM SIGPLAN Notices, v.30 n.2, p.42-48, Feb. 1995 [doi>10.1145/199873.199880]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Algorithms, Languages

Keywords:
loops, static single assignment form, strength reduction