[M3devel] m3cg shift value/count types

[Rodney M. Bates]

Signed and unsigned integers are inherently confusing and have no easy
linguistic solution that doesn't involve tradeoffs.  Modula-3 and C
have significantly different mechanisms.  Correctly translating the
former into the latter inevitably is going to require generating some
not-so-pretty code.

The C and Modula-2 way is to have distinct signed and unsigned types.
Usually, the unsigned type is full-range.  The builtin operators are
overloaded and in general, have different definitions when applied to
a signed vs. an unsigned type.  Type conversions, implicit or
explicit, must be done for an operator to have mixed signed/unsigned
operands.

The Modula-3 way is to have only a (normally) signed INTEGER type, but
different operators with different names, that apply either a signed
or unsigned interpretation to the bits of this one type.  All the
builtins that syntactically use operator notation ('+', etc.) are
unconditionally signed.  The only unsigned operators are (pseudo-)
functions in Word.i3.  Note that Word.T = INTEGER.

Having on occasions done very careful mixed signed/unsigned code in
both Modula-2 and Modula-3, I like the Modula-3 way a bit better.  It
doesn't really make a lot of difference in how hard you have to think
about the signedness of every operand and operator, but it does at
least greatly simplify the definition of the language's rules and the
difficulty of understanding and remembering them.  Compared to
Modula-2 (where any signedness type conversions must be explicit),
Modula-3 does make it easier to go into denial and ignore the problem.
Since C will apply the conversions implicitly, it makes it just as
easy to deny, while requiring a lot more semantic rules.

So translating Modula-3 to C involves changing the way signed/unsigned
operators are done.  I don't think there is any way to get it right
other than to translate all types into C signed types and explicitly
cast every value to/from the corresponding unsigned type exactly when
the translation of an operation from Word is applied.  (Well, making
everything unsigned would work, but generate far more frequent ugly C
code.)  I suppose a set of macros for the unsigned operators might
make for prettier C code.

C's casts are inconsistent about when they are true type conversions
(defined by a mapping between the abstract values of the two types)
and the equivalent of LOOPHOLE (defined by just reinterpreting the
same bits via a different set of representation rules).  For
translating operators in Word, you need a LOOPHOLE equivalent.
Fortunately, as I read Harbison and Steele, C's casts in this case
can pretty well be depended on to have this meaning.

So then back-end shift operators, since only Word has source language
equivalents for them, really should always treat the to-be-shifted
operand as unsigned, despite the fact that the operand has the back-
end equivalent of a signed type.  This should be true in any back-end,
not just a C-generating one.  I suppose this could require explicit
casts in the M3CG representation, but that is exactly the pedantic way
output from a front-end should be.



On 09/22/2012 01:39 PM, Jay K wrote:
> Correction, I don't think 64bit targets have:
>
> Shift(Word32, Int64);
> ShiftLeft or Right(Word32, Word64);
>
>
> And historically, without LONGINT the differences were smaller, it was:
>
> 32bit:
> Shift(Word32, Int32);
> ShiftLeft or Right(Word32, Word32);
>
> 64bit:
> Shift(Word64, Int64);
> ShiftLeft or Right(Word64, Word64);
>
> The differences were only in signed-ness, not size.
> And, oh, I might have the input-signedness to shift_left/right wrong here.
>
>
> Anyway, I'll likely adjust the comments in M3CG_Ops.i3 and my code in M3C.m3.
> And maybe review the other backends.
> There isn't any sort of runtime stack imbalance implied by these mixed up sizes.
> I'm not sure the sign mixups matter or not.
> I'd have to do some experiments.
>
> Certainly I'm more nervous about signedness mixups now.
> I had this code, which is very wrong:
>
>
> #define m3_shift_T(T) static T m3_shift_##T(T value,INTEGER shift)
> {if((shift>=(sizeof(T)*8))||(shift<=-(sizeof(T)*8)))...
>
>
> shift is signed
> sizeof is unsigned
> shift got treated as unsigned
> small negative numbers got treated as large positive numbers
> shifting by, e.g. -1, resulted in 0, instead of a right shift by 1.
>
>
>   - Jay
>
>
>
> ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 --
> From: jay.krell at cornell.edu
> To: m3devel at elegosoft.com
> Date: Sat, 22 Sep 2012 18:28:14 +0000
> Subject: Re: [M3devel] m3cg shift value/count types
>
> It looks like what I have (shown) is correct.
> The shift count is always an INTEGER.
> 32bit targets have:
>
>
> Shift(Word32, Int32);
> Shift(Word64, Int32);
>
>
> 64bit targets have:
> Shift(Word32, Int64);
> Shift(Word64, Int64);
>
>
> I might have something wrong where I didn't show.
> The M3CG_Ops.i3 comment is wrong.
> The type of the value to shift and the count are never the same.
>
>
> The only place the frontend uses this is builtinWord/Shift.mg.
> Everywhere else, when I looked quickly, is explicit ShiftLeft or ShiftRight.
> For those the count is unsigned.
> Oh. Those look wrong too.
> The front end uses an integer-based subrange for the parameter:
>
> m3front/builtinWord/Shift.mg:
> PROCEDURE Initialize (r: INTEGER) =
> ...
>      sub := SubrangeType.New (TInt.Zero, max, Int.T, FALSE);
>
>
> So it is:
>
>
> 32bit targets:
> ShiftLeft or Right(Word32, Word32);
> ShiftLeft or Right(Word64, Word32);
>
>
> 64bit targets:
> ShiftLeft or Right(Word32, Word64);
> ShiftLeft or Right(Word64, Word64);
>
>
> which also doesn't agree with M3CG_Ops.i3.
>
>
> Possibly "Rep" should abstract out the shift count type and not just the value to shift.
> Perhaps it should be:
>
> 32bit and 64 bit targets:
> ShiftLeft or Right(Word32, Word32);
> ShiftLeft or Right(Word64, Word64);
>
> and perhaps it should be:
>
> 32bit:
> Shift(Word32, Int32);
> Shift(Word64, Int64);
>
>
> 64bit:
> Shift(Word32, Int64);
> Shift(Word64, Int64);
>
>
> there are arguments for various combinations and what we have isn't crazy.
> It just disagrees with comments in M3CG_Ops.i3.
>    The shift count doesn't really need to be widened to match the value.
>     If this were C with its prevalent "int", shift could remain just 32 bits always. (or even 16)
>     But Modula-3 favors INTEGER/ptrdiff_t and widening even when 32bits is plenty.
>
>
>
>   - Jay
>
> ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 --
> From: jay.krell at cornell.edu
> To: m3devel at elegosoft.com
> Date: Sat, 22 Sep 2012 18:00:36 +0000
> Subject: [M3devel] m3cg shift value/count types
>
> M3CG_Ops.i3:
>
> shift        (t: IType);  (* s1.t := Word.Shift  (s1.t, s0.t); pop *)
> rotate       (t: IType);  (* s1.t := Word.Rotate (s1.t, s0.t); pop *)
>
>
> This doesn't seem right to me.
>
> s0 is signed.
> s1 is not
>
> I have it implemented as:
>
> #define m3_shift_T(T) static T m3_shift_##T(T value,INTEGER shift)...
>
> where T is UINT32 or UINT64.
>
> "shift" can vary..I'll look at the frontend...
>
>   - Jay