This commit makes Savi depart from the bit shifting semantics
that were inherited from the Pony language in order to reach
semantics that are (in my opinion) more consistent to reason about.
To a certain extent both of these changes were already implied
by the existing documentation comments in Savi for these operations,
so they were somewhat bugs already in that the documentation didn't
match how it was working under the hood. But in any case, the
documentation comments have been updated to be more clear on these
points, which are also elaborated below:
Right shifting now uses "logical" shift instead of "arithmetic"
shift for both signed and unsigned integers.
Prior to this, signed integers used "arithmetic" shifting,
so that the right shifting was always isomorphic with
the arithmetic operation of dividing by 2.
However, that behavior made it hard to write generic code
that relied on the "logical" semantics of bit shifting,
as signed integers were a special case to need to deal with.
This new change stops the use of arithmetic shifting,
under the reasoning that if one needs to reliably divide
negative integers by multiples of 2, then one can explicitly
use the division operator to do so, and rely on the compiler
(specifically, LLVM optimizations) to convert division into
arithmetic bit shifting when/if it is appropriate.
Bit shifting by more than the bit_width of the type now
always results in all zero bits (zero).
Prior to this, the number of bits to be shifted by was
being clamped to a maximum of one less the bit_width,
meaning that one bit from the original bit set would remain
in the window of visible bits after the shift operation.
This was surprising behavior in several ways, not the least
of which being that shifting by N bits twice wouldn't
necessarily give you the same result as shifting by 2N bits once,
in the case that 2N >= T.bit_width && N < T.bit_width.
This new change fixes that distributive property and ensures
consistent behavior by making the case behave in such away
that all of the original bits are shifted away out of sight
and only zero bits are left in their wake.
The reason this needs to be a special case at the LLVM IR
level is that the LLVM shl and lshr instructions
define that shifting by greater than or equal to the bit_width
results in a "poison" value that will break downstream code.
Pony (and the Savi semantics inherited from Pony) was treating
the special case by reducing the bit shift amount but Savi
instead treats it by just returning zero in that case.
This commit makes Savi depart from the bit shifting semantics that were inherited from the Pony language in order to reach semantics that are (in my opinion) more consistent to reason about.
To a certain extent both of these changes were already implied by the existing documentation comments in Savi for these operations, so they were somewhat bugs already in that the documentation didn't match how it was working under the hood. But in any case, the documentation comments have been updated to be more clear on these points, which are also elaborated below:
Right shifting now uses "logical" shift instead of "arithmetic" shift for both signed and unsigned integers.
Bit shifting by more than the
bit_width
of the type now always results in all zero bits (zero).bit_width
, meaning that one bit from the original bit set would remain in the window of visible bits after the shift operation.2N >= T.bit_width && N < T.bit_width
.shl
andlshr
instructions define that shifting by greater than or equal to thebit_width
results in a "poison" value that will break downstream code.