preston@titan.rice.edu (Preston Briggs) (12/31/89)
In article <85204@linus.UUCP> bs@linus.UUCP (Robert D. Silverman) writes: >So far as I know [and I've seen the code] SPICE is not a heavy user >of integer multiply/divides. It does use a fair amount of floating >point. Therefore, trying to get a measure of integer multiply/divide >performance using SPICE is grasping at straws at best. So what's your favorite application that does lots of integer multiplies and divides? Code it up and pass it out for people to run. Lots of people have pointed out that multiplying by a constant can be reduced (during optimization) to a sequence of shifts, adds, and subtracts. People have also pointed out that most multiplies arising from array accesses can be strength reduced to additions. So what's left? Optimizers can eliminate any multiply of any combination of loop-invariant expressions and loop-induction expressions; otherwise, you're on your own. Division is slightly more complex, due to sign handling. For most languages, it isn't safe to replace a divide by 2^N with a shift right (doesn't work for negative numbers). The same problem arises when replacing I % 4 with I & 3. Division and remainder can be strength reduced, but require introduction of a branch. While we're at it, it's also possible to strength reduce exponentiation, most trig functions, etc., though FP precision problems will bite you. Preston Briggs preston@titan.rice.edu
tim@nucleus.amd.com (Tim Olson) (01/01/90)
In article <4057@brazos.Rice.edu> preston@titan.rice.edu (Preston Briggs) writes: | For most languages, it isn't safe to replace a divide by 2^N | with a shift right (doesn't work for negative numbers). | The same problem arises when replacing I % 4 with I & 3. | Division and remainder can be strength reduced, but require introduction | of a branch. Since C (specifically, the proposed ANSI Standard) specifies only that the expression (a/b)*b + a%b == a holds, the sign of a%b and the value for a/b when either operand is negative is implementation defined. Therefore, it is perfectly legal to define that a%b is always positive. If this method is used, then a/b (where b is a positive power-of-2) can be replaced with an arithmetic shift right. For example: Method 1: 5/2 == 2 5%2 == 1 -5/2 == -2 -5%2 == -1 5>>1 == 2 5&1 == 1 -5>>1 == -3 -5&1 == 1 ^ ^ | don't match | Method 2: 5/2 == 2 5%2 == 1 -5/2 == -3 -5%2 == 1 5>>1 == 2 5&1 == 1 -5>>1 == -3 -5&1 == 1 ^ ^ | match | IBM implemented this second form of / and % in their PL.8 compiler for the ROMP chip, just so the above optimization could be performed. However, division or modulo of a signed integer by a positive power-of-2 can be optimized without a branch. The technique is shown below: ; perform a/b, where the sign of a is unknown, ; and b is a positive power-of-2. b == 2**N ; tmp = (a<0) ? b-1 : 0; sra tmp, a, N-1 srl tmp, tmp, 32-N ; tmp = (tmp + a) >> N; add tmp, tmp, a sra tmp, tmp, N ; perform a%b, where the sign of a is unknown, ; and b is a positive power-of-2 ; tmp1 = (a<0) ? b-1 : 0; sra tmp1, a, N-1 srl tmp1, tmp1, 32-N ; tmp2 = ((tmp1 + a) & (b-1)) - tmp1; add tmp2, tmp1, a and tmp2, tmp2, b-1 sub tmp2, tmp2, tmp1 -- Tim Olson Advanced Micro Devices (tim@amd.com)
jesup@cbmvax.commodore.com (Randell Jesup) (01/03/90)
In article <4057@brazos.Rice.edu> preston@titan.rice.edu (Preston Briggs) writes: >Division is slightly more complex, due to sign handling. >For most languages, it isn't safe to replace a divide by 2^N >with a shift right (doesn't work for negative numbers). >The same problem arises when replacing I % 4 with I & 3. Easy solution: x/2^n = (x >> n) + (x & 1 & (bit 31 of x)). Of course, the >> operation must be "arithmetic" and not "logical" (i.e. sign-extending). For a machine with slow divides and a barrel shifter (many risc chips), this may be faster than a divide subroutine/instruction. Also note it avoids any branches. -- Randell Jesup, Keeper of AmigaDos, Commodore Engineering. {uunet|rutgers}!cbmvax!jesup, jesup@cbmvax.cbm.commodore.com BIX: rjesup Common phrase heard at Amiga Devcon '89: "It's in there!"
preston@titan.rice.edu (Preston Briggs) (01/03/90)
In article <9193@cbmvax.commodore.com> jesup@cbmvax.commodore.com (Randell Jesup) writes: >In article <4057@brazos.Rice.edu> preston@titan.rice.edu (Preston Briggs) writes: >>Division is slightly more complex, due to sign handling. >>For most languages, it isn't safe to replace a divide by 2^N >>with a shift right (doesn't work for negative numbers). > Easy solution: x/2^n = (x >> n) + (x & 1 & (bit 31 of x)). Of course, >the >> operation must be "arithmetic" and not "logical" But what about -6/4 ? 6 = 0...0110 -6 = 1...1010 x>>2 = 1...1110 + (1...1010 & 1 & (x >> 31)) = 1...1110 + 0 = 1...1110 = -2 On the other hand, perhaps I've misinterpreted your intent. Preston Briggs
nfs@notecnirp.Princeton.EDU (Norbert Schlenker) (01/03/90)
In article <9193@cbmvax.commodore.com> jesup@cbmvax.commodore.com (Randell Jesup) writes: >In article <4057@brazos.Rice.edu> preston@titan.rice.edu (Preston Briggs) writes: >>Division is slightly more complex, due to sign handling. >>For most languages, it isn't safe to replace a divide by 2^N >>with a shift right (doesn't work for negative numbers). > > Easy solution: x/2^n = (x >> n) + (x & 1 & (bit 31 of x)). Of course, >the >> operation must be "arithmetic" and not "logical" (i.e. sign-extending). This doesn't work. Consider -10/2^3, which results in -2. >Randell Jesup, Keeper of AmigaDos, Commodore Engineering.
jesup@cbmvax.commodore.com (Randell Jesup) (01/06/90)
In article <22705@princeton.Princeton.EDU> nfs@notecnirp.UUCP (Norbert Schlenker) writes: >In article <9193@cbmvax.commodore.com> jesup@cbmvax.commodore.com (Randell Jesup) writes: >> Easy solution: x/2^n = (x >> n) + (x & 1 & (bit 31 of x)). Of course, >>the >> operation must be "arithmetic" and not "logical" (i.e. sign-extending). > >This doesn't work. Consider -10/2^3, which results in -2. Yes, this has been pointed out to me by mail. I grabbed my "divide by 2" algorithm without checking it. The more general form is: if ((x < 0) && (x & "n-ones")) result = (x >> n) + 1; else result = x >> n; "n-ones" means n ones filled in starting at low order working up. Also could be some funky bit-field test instruction; however this would be hard to code in C for a variable n (constant n isn't bad, and may well still be faster than integer divide). The original formula for x/2 has the advantage of not requiring any branches. Hopefully I haven't stuck my foot any further down my throat... :-) -- Randell Jesup, Keeper of AmigaDos, Commodore Engineering. {uunet|rutgers}!cbmvax!jesup, jesup@cbmvax.cbm.commodore.com BIX: rjesup Common phrase heard at Amiga Devcon '89: "It's in there!"