[Vm-dev] how the h**l do I generate a signed shift?

Eliot Miranda eliot.miranda at gmail.com
Mon Jun 30 19:24:12 UTC 2014

Hi All,

    I recently eliminated the optimization in Slang that replaces a
division by a power of two with a shift, because the code cast the argument
to signed, and hence broke unsigned division.  That's what used to be
controlled by the UseRightShiftForDivide class var of CCodeGenerator.

Yesterday I found out that that optimization is the only thing that's
keeping the LargeIntegers plugin afloat.  To whit:

LargeIntegersPlugin>>cDigitSub: pByteSmall
len: smallLen
with: pByteLarge
len: largeLen
into: pByteRes
| z limit |
<var: #pByteSmall type: 'unsigned char * '>
<var: #pByteLarge type: 'unsigned char * '>
<var: #pByteRes type: 'unsigned char * '>

z := 0.
"Loop invariant is -1<=z<=1"
limit := smallLen - 1.
0 to: limit do:
[:i |
z := z + (pByteLarge at: i) - (pByteSmall at: i).
pByteRes at: i put: z - (z // 256 * 256).
"sign-tolerant form of (z bitAnd: 255)"
z := z // 256].
limit := largeLen - 1.
smallLen to: limit do:
[:i |
z := z + (pByteLarge at: i) .
pByteRes at: i put: z - (z // 256 * 256).
"sign-tolerant form of (z bitAnd: 255)"
z := z // 256].

The "z := z // 256"'s at the end of the loops were being generated as
        z = ((sqInt) z) >> 8;
 which is essential for the signed arithmetic implicit in "z := z +
(pByteLarge at: i) - (pByteSmall at: i)" to work.

So what's the right thing to do?

In C -1 // 256 = 0, but in Smalltalk -1 // 256 = -1 (// rounds towards -
infinity), whereas  (-1 quo: 256) = 0 (quo: rounds towards 0).

I could modify the code generator to generate Smalltalk semantics for //,
but its not pretty (one has to check signedness, check if there's a
remainder, etc).

What I'd like is to have a signed bitShift:.  Wait you say, bitShift: is
signed.  Ah, but the code generator generates unsigned shifts for all
bitShift:'s !!!!.

So some ideas:

1. change bitShift: to obey the type of the receiver (Slang allows one to
type variables, defaulting to a singed long). This is my preference, but it
risks breaking a good handful of negative bitShift: uses in plugins (which
is where I'm worried about regressions).

2. change bitShift: to obey explicit casts, generating a signed shift for
   foo asInteger bitShift: expr
   (self cCoerceSimple: #foo to: #sqInt) bitShift: expr
Seriously?!?! this stinks.

3. write
z := self cCode: [z >>= 8] inSmalltalk: [z // 256]

Seriously?!?! this stinks too.

Anything else that makes any sense?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20140630/71afae34/attachment-0001.htm

More information about the Vm-dev mailing list