[Vm-dev] Is bytecodePrimMultiply correct?

[David T. Lewis]

On Tue, Oct 04, 2011 at 10:11:33AM -0700, Eliot Miranda wrote:
>  
> Hi Stefan,
> 
>     so the VMMaker source is probably easier to read.  First, thanks for the
> optimization; clearly
> 
> (arg = 0 or: [(result // arg) = rcvr and: [self isIntegerValue: result]])
> 
> 
> is better than the original
> 
> ((arg = 0 or: [(result // arg) = rcvr]) and: [self isIntegerValue: result])
> 
> 
> I'd suspect the definition of isIntegerValue:, which is:
> 
> ObjectMemory methods for interpreter access
> isIntegerValue: intValue
> "Return true if the given value can be represented as a Smalltalk integer
> value."
> "Use a shift and XOR to set the sign bit if and only if the top two bits of
> the given value are the same, then test the sign bit. Note that the top two
> bits are equal for exactly those integers in the range that can be
> represented in 31-bits or 63-bits."
> 
> ^ (intValue bitXor: (intValue << 1)) >= 0
> 
> The comment makes sense but there is perhaps nothing to guarantee that a C
> compiler must consider the type of signed ^ signed as signed, in which case
> the compiler would assume it is always >= 0, and the overflow detection
> would fail.
> 
> If you change the method to
> 
> ObjectMemory methods for interpreter access
> isIntegerValue: intValue
> "Return true if the given value can be represented as a Smalltalk integer
> value."
> "Use a shift and XOR to set the sign bit if and only if the top two bits of
> the given value are the same, then test the sign bit. Note that the top two
> bits are equal for exactly those integers in the range that can be
> represented in 31-bits or 63-bits."
> 
> ^(intValue bitXor: (intValue << 1)) asInteger >= 0
> 
> which should force a cast to sqInt, does that fix things?
> 
> i.e. it should produce
> 
>       if (((arg == 0)
>        || ((result / arg) == rcvr))
>         && ((sqInt)((result ^ (result << 1))) >= 0)) {

The current implementation of isIntegerValue does this type declaration properly.

Background: http://bugs.squeak.org/view.php?id=5238

The implementation of ObjectMemory>>isIntegerValue: in VMMaker trunk is as follows:

isIntegerValue: intValue
	"Return true if the given value can be represented as a Smalltalk integer value."
	"Use a shift and XOR to set the sign bit if and only if the top two bits of the given
	value are the same, then test the sign bit. Note that the top two bits are equal for
	exactly those integers in the range that can be represented in 31-bits or 63-bits.

	Operands are coerced to machine integer size so the test will work with 64 bit
	images on 32 bit hosts. When running on a 32 bit host, the cast to int has little
	or no performance impact for either 32 bit or 64 bit images.

	On a 64 bit host, the shift and XOR test is replaced by an explicit range check,
	which provides the best performance for both 32 bit and 64 bit images.

	If the range of small integers is enlarged for 64 bit images, this method must
	be updated accordingly."

	^ self isDefined: 'SQ_HOST32'
		inSmalltalk: [true]
		comment: 'cast to int for 64 bit image on 32 bit host'
		ifTrue: ((self cCoerce: intValue to: 'int')
					bitXor: ((self cCoerce: intValue to: 'int') << 1)) >= 0
		ifFalse: (intValue >= 16r-40000000 and: [intValue <= 16r3FFFFFFF])
		

When translated to C this becomes:

sqInt isIntegerValue(sqInt intValue) {
	return 
# ifdef SQ_HOST32  // cast to int for 64 bit image on 32 bit host
		(((((int) intValue)) ^ ((((int) intValue)) << 1)) >= 0)
# else
		((intValue >= -1073741824) && (intValue <= 1073741823))
# endif  // SQ_HOST32
	;
}

So on a 32-bit platform this ensures that the check will use the following
signed comparison:

sqInt isIntegerValue(sqInt intValue) {
	return (((((int) intValue)) ^ ((((int) intValue)) << 1)) >= 0);
}

Dave



> 
> On Mon, Oct 3, 2011 at 5:46 PM, Stefan Marr <squeak at stefan-marr.de> wrote:
> 
> >
> > Dear all:
> >
> > With the RoarVM, I was hitting a problem with Clang 3.0
> > (tags/Apple/clang-211.9).
> >
> > It turned out that Clang does not like the current implementation of
> > bytecodePrimMultiply.
> >
> > From what I can tell, it should be identical with what I found in the
> > SqueakVM sources.
> >
> > RoarVM src:
> > https://github.com/smarr/RoarVM/blob/master/vm/src/interpreter/interpreter_bytecodes.cpp#L316
> >
> >    oop_int_t ri = rcvr.integerValue();
> >    oop_int_t ai = arg.integerValue();
> >    oop_int_t r  = ri * ai;
> >    if (ai == 0  ||  (r / ai  ==  ri    &&    Oop::isIntegerValue(r))) {
> >      internalPopThenPush(2, Oop::from_int(r));
> >      fetchNextBytecode();
> >      return;
> >    }
> >
> > Squeak src:
> >
> > http://squeakvm.org/cgi-bin/viewcvs.cgi/branches/Cog/src/vm/cointerp.c?rev=2497&view=auto
> >
> >        rcvr = (rcvr >> 1);
> >        arg = (arg >> 1);
> >        result = rcvr * arg;
> >        if (((arg == 0)
> >        || ((result / arg) == rcvr))
> >         && ((result ^ (result << 1)) >= 0)) {
> >                /* begin internalPop:thenPush: */
> >                longAtPointerput((localSP += (2 - 1) * BytesPerWord),
> > ((result << 1) | 1));
> >                /* begin fetchNextBytecode */
> >                currentBytecode = byteAtPointer(++localIP);
> >                goto l69;
> >        }
> >
> >
> > The problematic example is rcvr: 40453, arg: 864001.
> >
> > In that case, the current implementation does not detect the overflow
> > correctly when Clang is used with >= O1 optimization.
> >
> > The big question for me now is, whether we got here a Clang compiler bug,
> > or unspecified C behavior.
> >
> >
> > My quick fix is:
> >
> >    oop_int_t ri = rcvr.integerValue();
> >    oop_int_t ai = arg.integerValue();
> >    long long result_with_overflow = (long long)ri * ai;
> >    if (ai == 0  ||  ((result_with_overflow >= -1073741824) &&
> > (result_with_overflow <= 1073741823)))
> >    {
> >      internalPopThenPush(2, Oop::from_int(result_with_overflow));
> >      fetchNextBytecode();
> >      return;
> >    }
> >
> > This works obviously, but I assume that the original code is a well
> > considered speed optimizations.
> >
> > Any thoughts?
> >
> > Thanks
> > Stefan
> >
> > --
> > Stefan Marr
> > Software Languages Lab
> > Vrije Universiteit Brussel
> > Pleinlaan 2 / B-1050 Brussels / Belgium
> > http://soft.vub.ac.be/~smarr
> > Phone: +32 2 629 2974
> > Fax:   +32 2 629 3525
> >
> >
> 
> 
> -- 
> best,
> Eliot