|[5 earlier articles]|
|Re: Multiply by a constant --> shift-and-adds algorithm? email@example.com (1997-11-11)|
|Re: Multiply by a constant --> shift-and-adds algorithm? dube@brachio.IRO.UMontreal.CA (Danny Dube) (1997-11-11)|
|Re: Multiply by a constant --> shift-and-adds algorithm? firstname.lastname@example.org (Christopher Glaeser) (1997-11-13)|
|Re: Multiply by a constant --> shift-and-adds algorithm? email@example.com (Sergey Solyanik) (1997-11-14)|
|Re: Multiply by a constant --> shift-and-adds algorithm? firstname.lastname@example.org (Shankar Unni) (1997-11-15)|
|Multiply by a constant --> shift-and-adds algorithm? email@example.com (1997-11-16)|
|Re: Multiply by a constant --> shift-and-adds algorithm? firstname.lastname@example.org (Christopher Glaeser) (1997-11-18)|
|const_int * (int / const_int) by shift adds? email@example.com (Charles Fiterman) (1997-11-20)|
|From:||Christopher Glaeser <firstname.lastname@example.org>|
|Date:||18 Nov 1997 12:20:09 -0500|
|References:||97-11-038 97-11-078 97-11-086|
|Keywords:||optimize, arithmetic, practice|
Sergey Solyanik wrote:
> Do you have examples? ...
> One hour per constant seems uncomprehensible...
The constants that caused the excessive compilation times had one or
more repeating patterns. Examples include numbers with a binary
pattern such as 10101 repeated two or three times in a 32-bit integer.
I have isolated compile-time problems due to multiply by a constant in
several production compilers (one, as I mentioned, requiring an hour
per constant). The vendors of these compilers are Nullstone
licensees, and the problems have been corrected in current releases.
Since I didn't have access to the compiler source code, I don't know
if the problems were caused during the shift/add expansion, or during
subsequent phases such as register allocation and instruction
While on the topic of integer multiply optimization, I should mention
two other types of problems that I occasionally isolate in production
compilers. The first is unnecessarily limiting the power-of-two
optimization to a power-of-two subrange, even though larger shift
amounts are available in the ISA. An example would be converting
multiply by 2**1 through 2**8 to a shift, but leaving 2**9 through
2**31 as a slower multiply. The second is optimizing signed integer
multiply, but not unsigned integer multiply, or vice versa.
Christopher Glaeser email@example.com
Nullstone Corporation http://www.nullstone.com
Return to the
Search the comp.compilers archives again.