Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!rice!titan!preston From: preston@titan.rice.edu (Preston Briggs) Newsgroups: comp.arch Subject: Re: Integer Multiply/Divide on Sparc Message-ID: <4270@brazos.Rice.edu> Date: 15 Jan 90 18:53:50 GMT References: <8840005@hpfcso.HP.COM> <1249@otc.otca.oz> <1255@otc.otca.oz> Sender: root@rice.edu Reply-To: preston@titan.rice.edu (Preston Briggs) Organization: Rice University, Houston Lines: 54 In article <1255@otc.otca.oz> gregw@otc.UUCP (Greg Wilkins) writes: >But what about multiplies by constants, the compiler will have turned these >into wonderful sequences of shifts and adds. If a mul instruction became >available, these should be replaced by a load with constant followed by a >multiply. But then I guess nothing can solve this one (without greatly >slowing the performance of all machines without a multiply instruction). Converting I x C into a sequence of shifts, adds, and subtracts is really a machine-dependent optimization -- it's not always profitable. In a short paper Multiplication by Integer Constants Robert Bernstein Software -- Practice and Experience, July 1986 Bernstein describes the method used by the PL.8 compiler to handle 32x32 signed multiplies. The cost of a multiply, on an 801, using multiply-step instructions is 19 cycles. The cost, using his scheme, is summarized below constant # instructions --------------------------------------- 2 1 3 2 6 3 11 4 22 5 43 6 86 7 171 8 342 9 683 10 1366 11 2731 12 5462 13 ... that is, multiplications by 2731 require 12 instructions. Multiplications by C < 2731 require 11 or fewer instructions. So, if you've got a multiplier that's quicker than 10 cycles, you'd rather not convert some constants >= 683. On the other hand, if you have lots of multiplies by strange integer constants, converting them all might expose opportunities for common subexpression elimination. Note that the above numbers are misleading for some machines. If you don't have a barrel shifter or 3-address instructions or adequate registers, the cost will be higher. Preston Briggs preston@titan.rice.edu