Keith D. Cooper
L. Taylor Simpson
Skip Abstract Section
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.
- ALLEN, F. E. 1969. Program optimization. Annual Review in Automatic Programming 5, 239-308.Google Scholar
- 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.Google Scholar
- ALPERN, B., WEGMAN,M.N.,AND ZADECK, F. K. 1988. Detecting equality of variables in programs. In Conference Record of the Fifteenth Annual ACM Symposium on Principles of Programming Languages. ACM, San Diego, California, 1-11. Google Scholar
- BERNSTEIN, R. 1986. Multiplication by integer constants. Software-Practice and Experience 16,7 (July), 641-652. Google Scholar
- BODIK, R., GUPTA, R., AND SOFFA, M. L. 1998. Complete removal of redundant computations. SIGPLAN Notices 33, 5 (May), 1-14. Proceedings of the ACM SIGPLAN '98 Conference on Programming Language Design and Implementation. Google Scholar
- BRIGGS,P.AND COOPER, K. D. 1994. Effective partial redundancy elimination. SIGPLAN Notices 29, 6 (June), 159-170. Google Scholar
- BRIGGS, P., COOPER,K.D.,HARVEY,T.J.,AND SIMPSON, L. T. 1998. Practical improvements to the construction and destruction of static single assignment form. Software-Practice and Experience 28, 8 (July), 859-881. Google Scholar
- BRIGGS, P., COOPER,K.D.,AND SIMPSON, L. T. 1997. Value numbering. Software-Practice and Experience 27, 6, 710-724. Google Scholar
- BRIGGS, P., COOPER,K.D.,AND TORCZON, L. 1994. Improvements to graph coloring register allocation. ACM Trans. Program. Lang. Syst. 16, 3 (May), 428-455. Google Scholar
- 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.Google Scholar
- CAI,J.AND PAIGE, R. 1991. "Look Ma, no hashing, and no arrays neither". In Conference Record of the Eighteenth Annual ACM Symposium on Principles of Programming Languages. ACM, Orlando, Florida, 143-154. Google Scholar
- 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.Google Scholar
- CHASE, D. R. 1988. Personal communication in the form of an unpublished report.Google Scholar
- CHOI, J.-D., CYTRON, R., AND FERRANTE, J. 1991. Automatic construction of sparse data flow evaluation graphs. In Conference Record of the Eighteenth Annual ACM Symposium on Principles of Programming Languages. ACM, Orlando, Florida, 55-66. Google Scholar
- CLICK,C.AND COOPER, K. D. 1995. Combining analyses, combining optimizations. ACM Trans. Program. Lang. Syst. 17, 2 (Mar.), 181-196. Google Scholar
- COCKE,J.AND KENNEDY, K. 1977. An algorithm for reduction of operator strength. Communications of the ACM 20, 11 (Nov.), 850-856. Google Scholar
- COCKE,J.AND MARKSTEIN, P. 1980a. Measurement of program improvement algorithms. In Proceedings of Information Processing 80. North Holland Publishing Company, Tokyo, Japan.Google Scholar
- 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.Google Scholar
- COCKE,J.AND SCHWARTZ, J. T. 1970. Programming languages and their compilers: Preliminary notes. Tech. rep., Courant Institute of Mathematical Sciences, New York University.Google Scholar
- COOPER,K.D.AND SIMPSON, L. T. 1995. SCC-based value numbering. Tech. Rep. TR95636, Center for Research on Parallel Computation, Rice University. Oct.Google Scholar
- CYTRON, R., FERRANTE, J., ROSEN, B. K., WEGMAN,M.N.,AND ZADECK, F. K. 1991. Efficiently computing static single assignment form and the control dependence graph. ACM Trans. Program. Lang. Syst. 13, 4 (Oct.), 451-490. Google Scholar
- DHAMDHERE, D. M. 1979. On algorithms for operator strength reduction. Communications of the ACM 22, 5 (May), 311-312.Google Scholar
- DHAMDHERE, D. M. 1989. A new algorithm for composite hoisting and strength reduction. Int. J. Comput. Math. 27, 1, 1-14.Google Scholar
- DRECHSLER, K.-H. AND STADEL, M. P. 1993. A variation of Knoop, Ruthing, and Steffen's "lazy code motion". SIGPLAN Notices 28, 5 (May), 29-38. Google Scholar
- 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.Google Scholar
- FONG, A. C. 1979. Automatic improvement of programs in very high level languages. In Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages. ACM, San Antonio, Texas, 21-28. Google Scholar
- FONG,A.C.AND ULLMAN, J. D. 1976. Induction variables in very high level languages. In Conference Record of the Third ACM Symposium on Principles of Programming Languages. ACM, Atlanta, Georgia, 104-112. Google Scholar
- GRANLUND, T. 1995. Private communication with P. Briggs. Discussion of his work in building the routine synth mult for the Gnu C Compiler.Google Scholar
- GRANLUND,T.AND MONTGOMERY, P. L. 1994. Division by invariant integers using multiplication. SIGPLAN Notices 29, 6 (June), 61-72. Google Scholar
- GUPTA, R., BERSON,D.A.,AND FANG, J. Z. 1998. Path profile guided partial redundancy elimination using speculation. In Proceedings of the IEEE 1998 International Conference on Computer Languages. IEEE Computer Society, Chicago, IL., USA, 230-239. Google Scholar
- HAVLAK, P. 1997. Nesting of reducible and irreducible loops. ACM Trans. Program. Lang. Syst. 19, 4 (July), 557-567. Google Scholar
- 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.Google Scholar
- KAM,J.B.AND ULLMAN, J. D. 1976. Global data flow analysis and iterative algorithms. J. ACM 23, 1 (Jan.), 158-171. Google Scholar
- KENNEDY, K. 1973. Reduction in strength using hashed temporaries. SETL Newsletter 102, Courant Institute of Mathematical Sciences, New York University. Mar.Google Scholar
- KENNEDY, K. 1978. Use-definition chains with applications. Computer Languages 3, 163- 179.Google Scholar
- KNOOP, J., RUTHING,O.,AND STEFFEN, B. 1992. Lazy code motion. SIGPLAN Notices 27, 7 (July), 224-234. Google Scholar
- KNOOP, J., RUTHING,O.,AND STEFFEN, B. 1993. Lazy strength reduction. J. Program. Lang. 1,1, 71-91.Google Scholar
- KNOOP, J., RUTHING,O.,AND STEFFEN, B. 1994. Optimal code motion: Theory and practice. ACM Trans. Program. Lang. Syst. 16, 4 (July), 1117-1155. Google Scholar
- LENGAUER,T.AND TARJAN, R. E. 1979. A fast algorithm for finding dominators in a flowgraph. ACM Trans. Program. Lang. Syst. 1, 1 (July), 121-141. Google Scholar
- LIU,Y.A.AND STOLLER, S. D. 1998. Loop optimization for aggregate array computations. In IEEE 1998 International Conference on Computer Languages. IEEE CS Press, Los Alamitos, CA, 262- 271. Google Scholar
- MARKSTEIN,P.W.,MARKSTEIN,V.,AND ZADECK, F. K. 1994. Reassociation and strength reduction. Chapter from an unpublished book, Optimization in Compilers.Google Scholar
- MOREL,E.AND RENVOISE, C. 1979. Global optimization by suppression of partial redundancies. Communications of the ACM 22, 2 (Feb.), 96-103. Google Scholar
- PAIGE,R.AND KOENIG, S. 1982. Finite differencing of computable expressions. ACM Trans. Program. Lang. Syst. 4, 3 (July), 402-454. Google Scholar
- PAIGE,R.AND SCHWARTZ, J. T. 1977. Reduction in strength of high level operations. In Conference Record of the Fourth ACM Symposium on Principles of Programming Languages. ACM, Los Angeles, California, 58-71. Google Scholar
- SANTHANAM, V. 1992. Register reassociation in PA-RISC compilers. Hewlett-Packard Journal 14,6 (June), 33-38.Google Scholar
- SCARBOROUGH,R.G.AND KOLSKY, H. G. 1980. Improved optimization of FORTRAN object programs. IBM J. Res. Dev. 24, 6 (Nov.), 660-676.Google Scholar
- SITES, R. L. 1979. The compilation of loop induction expressions. ACM Trans. Program. Lang. Syst. 1, 1 (July), 50-57. Google Scholar
- TARJAN, R. E. 1972. Depth first search and linear graph algorithms. SIAM J. Comput. 1, 2 (June), 146-160.Google Scholar
- TARJAN, R. E. 1974. Testing flow graph reducibility. J. Comput. Syst. Sci. 9, 355-365.Google Scholar
- VICK, C. A. 1994. SSA based reduction of operator strength. M.S. dissertation, Rice University, Department of Computer Science.Google Scholar
- WEGMAN,M.N.AND ZADECK, F. K. 1991. Constant propagation with conditional branches. ACM Trans. Program. Lang. Syst. 13, 2 (Apr.), 211-236. Google Scholar
- WOLFE, M. 1992. Beyond induction variables. SIGPLAN Notices 27, 7 (July), 162-174. Google Scholar
- WU, Y. 1995. Strength reduction of multiplications by integer constants. SIGPLAN Notices 32,2 (Feb.), 42-48. Google Scholar
Index Terms
- Operator strength reduction
Recommendations
An algorithm for reduction of operator strength
A simple algorithm which uses an indexed temporary table to perform reduction of operator strength in strongly connected regions is presented. Several extensions, including linear function test replacement, are discussed. These algorithms should fit ...
Strength reduction for loop-invariant types
ACSC '04: Proceedings of the 27th Australasian conference on Computer science - Volume 26Types are fundamental for enforcing levels of abstraction in modern high-level programming languages and their lower-level representations. However, some type-related features such as dynamic method calls and dynamic type casts can contribute ...
Comments