[Openmcl-devel] Bug in integer arithmetic (AMD64)

[Gary Byers]

This was fixed this morning (in the trunk in r14893, and that should go into
the 1.7 release as well.)  It was introduced into the x86 backend in r14822
and had been in the ARM backend for a few weeks longer; I don't know why
Leo's not seeing it but I don't know what his init file looks like either
(and that or the optimization settings in effect might explain the behavior.)

[The rest of this may be more than most people would want to know.]

If anyone's curious (and if you are, you're a sick, twisted individual ...),
there were actually two bugs there.  The first (which is less severe) is
that the call to * should really have been fully constant-folded but
wasn't.  The compiler had gotten as far as seeing:

(* -144115188075855873 1)       ; once it's clear that the value of A is 1

and missed the opportunity to constant-fold that.

If X and Y are integers and one of them is a constant equal to (EXPT 2 N)
for some positive integer N, then the multiplication can be reduced to
a shift of the other operand by N; the shift is probably at least a little
cheaper (and on some architectures it's significantly cheaper.)  LOGCOUNT
of such a positive power of 2 will be 1; the code that tried to recognize
such a constant checked for that but neglected to check that the constant
was positive:

? (logcount -144115188075855873)
1
? (logcount -33554433) ; (* -1 <the constant from Ron's example>)
1

Oops.

If the constant is positive, then (* such-a-constant another-integer)
can be treated as (ash another-integer (1- (integer-length such-a-constant))):
(* 4 (THE FIXNUM X)) = (ASH (THE FIXNUM X) 2)

In the examples, the compiler incorrectly turned

(* -144115188075855873 1)

into

(ash 1 57)      ; (1- (integer-length -144115188075855873)) = 57

which is the incorrect result that was observed (and for obscure reasons that
call to ASH did constant-fold into the wrong answer.)

So: at some (default) optimization settings, some calls to * involving negative
integer (FIXNUM, actually) constants whose LOGCOUNT is 1 were incorrectly
transformed into shifts.

Aside from the fact that someone caught it (thanks), the good news here is that
the bug didn't involve either the compilation of instructions to perform 
multiplication or runtime support for that.  (Maybe that's just barely good news,
but if those things were failing on certain arguments it might have been harder
to determine why.)  The compiler was convinced that it was dealing with a constant
here; it was right about that, but was confused about the value of that constant.

On Thu, 21 Jul 2011, Leo wrote:

> On 2011-07-20 18:52 +0800, Eric Marsden wrote:
>> Surprising!
>>
>> ,----
>> | ? (lisp-implementation-version)
>> | "Version 1.7-dev-r14890M  (LinuxX8664)"
>> | ? (let ((a 1)) (* 144115188075855873 a -1))
>> | 144115188075855872
>> `----
>
> Welcome to Clozure Common Lisp Version 1.7-dev-r14882M-trunk  (DarwinX8664)!
> ? (let ((a 1)) (* 144115188075855873 a -1))
> -144115188075855873
>
> Leo
> _______________________________________________
> Openmcl-devel mailing list
> Openmcl-devel at clozure.com
> http://clozure.com/mailman/listinfo/openmcl-devel
>
>