Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cornell!uw-beaver!rice!titan!preston
From: preston@titan.rice.edu (Preston Briggs)
Newsgroups: comp.arch
Subject: Re: Integer Multiply/Divide
Message-ID: <4057@brazos.Rice.edu>
Date: 30 Dec 89 19:09:00 GMT
References: <84768@linus.UUCP>
Sender: root@rice.edu
Reply-To: preston@titan.rice.edu (Preston Briggs)
Organization: Rice University, Houston
Lines: 31

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