Strength reduction of multiplications by integer constants

ABSTRACT

Replacing a multiplication of an integer constant by a sequence of simple instructions can be beneficial because it reduces the total number of cycles and also provides more opportunity for instruction level parallelism. In this paper we developed an algorithm that selectively replaces multiplications of integer constants with sequences of SUB, ADD, SHIFT, and LEA instructions. The algorithm runs fast and the generated instruction sequences are of high quality. The number of simple instructions generated for a multiplication of an integer constant is about 84.5% of the number of 1-bits in the binary representation of the constant. Also, for several popular processors, the simple instruction sequences significantly reduces the execution time to perform the multiplications.

REFERENCES

• 1: [1] Intel, Pentium Processor User's Manual, Volume 3: Architecture and Programming Manual. 1993.
• 2: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 3: Daniel J. Magenheimer , Liz Peters , Karl Pettis , Dan Zuras, Integer multiplication and division on the HP precision architecture, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.90-99, October 1987, Palo Alto, California, United States
• 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: [5] Preston Briggs, source code for implementing Robert Bernstein's algorithm posted in news group comp.compilers. Oct 20, 1992.
• 6: [6] Habibi, A and P.A. Wintz, "Fast Multipliers," IEEE Trans. on Computers, Vol. C-19, No. 2, pp. 153-157, Feb. 1970.
• 7: Stamatis Vassiliadis , Eric M. Schwarz , Baik M. Sung, Hard-Wired Multipliers with Encoded Partial Products, IEEE Transactions on Computers, v.40 n.11, p.1181-1197, November 1991 [doi>10.1109/12.102823]
• 8: CORPORATE Intel Corp., i486 microprocessor programmer's reference manual, Osborne/McGraw-Hill, Berkeley, CA, 1990

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Computer arithmetic

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

General Terms:
Algorithms, Experimentation, Languages, Performance

Keywords:
code generation, code optimization, instruction-level parallelism, integer multiplication