Re: Multiply by a constant --> shift-and-adds algorithm?

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
scheduling.


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.


Best regards,
Christopher Glaeser cdg@nullstone.com
Nullstone Corporation http://www.nullstone.com
--

Return to the comp.compilers page.
Search the comp.compilers archives again.