[M3devel] overshifting?
Jay K
jay.krell at cornell.edu
Thu Mar 4 00:52:54 CET 2010
Tony you aren't understanding me.
I'm not suggesting to optimize away runtime errors.
I understand that part of the spec. It has been referenced multiple times recently.
I'm saying that the front end knows often/always without a doubt if an operation will overflow or not.
If the operation will not overflow, it can do the work itself.
From what you say, it already does.
(I'm going to confuse "overflow" and "subrange error" here briefly.)
If the operation will overflow, it can just generate code to issue the error.
Now, for most operations, it doesn't know how the target responds to overflow, so the second statement isn't quite right.
However, if the operation absolutely will overflow, the frontend should warn. It at least misses some cases, e.g. -FIRST(INTEGER). Granted, on a one's complement system, it won't. But it should warn for the sake of all two's complement systems, which is all of them.
Let's amend the previous:
If the operation absolutely will overflow, the front end should warn, and then just ask CG to generate the usual code, as if the operation wouldn't overflow. I think it misses some warnings currently. I think it's easy to fix and I'll look into it. Basically whenever the TInt operations fail, should warn.
Now, let's somewhat replace "overflow" with "subrange error".
LeftShift(x, 100)
acts the same on all targets. It isn't overflow, it is subrange error.
In this case, I assert, the front end should warn, and it shouldn't bother asking the backend to generate code to the shift.
-Jay
From: hosking at cs.purdue.edu
Date: Wed, 3 Mar 2010 10:54:00 -0500
To: jay.krell at cornell.edu
CC: m3devel at elegosoft.com
Subject: Re: [M3devel] overshifting?
On 3 Mar 2010, at 01:00, Jay K wrote:
Why does Word.LeftShift(x , 100) even get to the backend? It should just generate the code to issue a runtime error? (even if x could be zero? I think so.)
Because the language spec says that a range error (100 does not fit in the range [0..Word.Size-1]) is a run-time error. Note that the code generator's M3CG_Ops don't specify ranges. The range check is in the *interface* for Word. The m3middle and backend M3CG_Ops are intended to be more general. So, M3CG_Ops.shift_left and shift_right are permitted to take an argument that is not range-checked.
Why doesn't front warn for -FIRST(INTEGER)? It should, right?
This is independent of the range check above. This is an expression that may or may not evaluate depending on the run-time defaults (checking for overflow or not). The compiler must be conservative and let the run-time influence whether overflow checking is in place or not.
Overflow checking is a run-time option. The compiler must defer to the run-time.
But still generate code to compute it.
Are these just oversights?
Nope. Intentional.
- Jay
> From: hosking at cs.purdue.edu
> Date: Tue, 2 Mar 2010 23:44:22 -0500
> To: jay.krell at cornell.edu
> CC: m3devel at elegosoft.com
> Subject: Re: [M3devel] overshifting?
>
> The front-end does fold constants where it can prove no overflow will occur. I don't think I understand any of the rest of what you are saying.
>
> On 2 Mar 2010, at 23:21, Jay K wrote:
>
> >
> > The backend can know if there can be a runtime error -- e.g. if the particular target never checks for overflow. Though that could/should also be exposed in Target.i3?
> >
> > I'm slightly leary of this, because currently the absolute norm is no overflow checking, so it seems promising to provide extra value in that case. But maybe the norm will shift and the value will decrease. That is, Target.i3 could advertise that a target never checks for overflow, and then m3front could fold lots of constants for that target. And if Target.i3 indicates a target might/always check for overflow at runtime, then m3front shouldn't fold them. If hypothecal target always checks for overflow, then m3front could omit the code to do the math and just call the runtime error code.
> >
> >
> > m3back historically has always folded constants, and "never" checked for overflow (ok, the LeftShift/RightShift shift count probably).
> >
> >
> > Only with the 64bit longint has overflow started to be detected by m3back, and it has caught some real cases, where the frontend is quiet.
> > Doesn't that seem wrong in some way?
> > front end should warn and then backend can be quiet?
> > Why does the backend know more than frontend?
> >
> >
> > Part of what I mean here is that even if frontend can't always fold the constants, it can know in many cases that overflow absolutely will not occur, and fold those. Like, do the math at compile time, if no overflow, generate the more optimal code. If overflow, generate the slower code and warn?
> >
> >
> >
> > - Jay
> >
> >
> > ----------------------------------------
> >> From: hosking at cs.purdue.edu
> >> Date: Tue, 2 Mar 2010 22:29:47 -0500
> >> To: jay.krell at cornell.edu
> >> CC: m3devel at elegosoft.com
> >> Subject: Re: [M3devel] overshifting?
> >>
> >> The backend should be silent. The warnings should come from the front-end, which has the type information needed. You cannot optimise away operations that may cause a run-time error.
> >>
> >> On 2 Mar 2010, at 18:53, Jay K wrote:
> >>
> >>>
> >>> The front end shouldn't bother asking the backend to shift by overlarge constants, eh?
> >>> Granted, it could be from
> >>> Shift(a, LAST(INTEGER) + ....);
> >>>
> >>> so the frontend can't always know, even if the backend thinks it does.
> >>> I need to try some things there -- code that produces a large shift via overflowing constants.
> >>>
> >>> Which..hm..begets the question. I have the backend error for constant overflows. But shouldn't it actually warn? You know, people code these things to trigger the runtime behavior:
> >>>
> >>> PROCEDURE Crash()
> >>> BEGIN
> >>> EVAL VAL(2, BOOLEAN);
> >>> END Crash.
> >>>
> >>>
> >>> mostly these are warnings at compile, runtime errors.
> >>> But some of these things are now barred by m3back, errors, e.g.
> >>>
> >>> EVAL LAST(INTEGER) + 1;
> >>>
> >>> Maybe I do need that warning callback after all?
> >>>
> >>>
> >>> - Jay
> >>>
> >>>
> >>> ________________________________
> >>>> From: jay.krell at cornell.edu
> >>>> To: hosking at cs.purdue.edu
> >>>> Date: Tue, 2 Mar 2010 21:09:54 +0000
> >>>> CC: m3devel at elegosoft.com
> >>>> Subject: Re: [M3devel] overshifting?
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>> I fixed it. It falls back to generating slower code, which is then not hit because
> >>>>
> >>>> it guaranteeably hits a runtime error ahead of it.
> >>>>
> >>>> Perhaps it should just issue a breakpoint there as the code is not reachable.
> >>>>
> >>>> e.g. in C we have:
> >>>>
> >>>>
> >>>>
> >>>> __declspec(noreturn) abort();
> >>>>
> >>>>
> >>>>
> >>>> void F1()
> >>>>
> >>>> {
> >>>> abort();
> >>>>
> >>>> /* breakpoint here */
> >>>>
> >>>> }
> >>>>
> >>>>
> >>>>
> >>>> Given the guaranteed runtime error, why does the frontend bother asking the backend to do the shift?
> >>>>
> >>>>
> >>>>
> >>>> - Jay
> >>>>
> >>>>
> >>>> ________________________________
> >>>>
> >>>> From: hosking at cs.purdue.edu
> >>>> Date: Tue, 2 Mar 2010 14:50:27 -0500
> >>>> To: hosking at cs.purdue.edu
> >>>> CC: m3devel at elegosoft.com; jay.krell at cornell.edu
> >>>> Subject: Re: [M3devel] overshifting?
> >>>>
> >>>>
> >>>> Oh, yes, of course your backend should not blow up on this.
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>> On 2 Mar 2010, at 14:46, Tony Hosking wrote:
> >>>>
> >>>>
> >>>>
> >>>> P.S. Here are the signatures of Shift, RightShift, and LeftShift.
> >>>>
> >>>>
> >>>>
> >>>> PROCEDURE Shift (x: T; n: INTEGER): T;
> >>>>
> >>>> For all i such that both i and i - n are in the range [0 .. Word.Size - 1], bit i of the result equals bit i - n of x. The other bits of the result are 0. Thus, shifting by n> 0 is like multiplying by 2^(n)
> >>>>
> >>>> PROCEDURE LeftShift (x: T; n: [0..Size-1]): T;
> >>>>
> >>>> = Shift (x, n)
> >>>>
> >>>> PROCEDURE RightShift (x: T; n: [0..Size-1]): T;
> >>>>
> >>>> = Shift (x, -n)
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>> Antony Hosking | Associate Professor | Computer Science | Purdue University
> >>>>
> >>>> 305 N. University Street | West Lafayette | IN 47907 | USA
> >>>>
> >>>> Office +1 765 494 6001 | Mobile +1 765 427 5484
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>> On 2 Mar 2010, at 14:44, Tony Hosking wrote:
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>> Actually, I should have noticed. Word.LeftShift and Word.RightShift both check the range of the shift parameter. It's not the shift that is out of range. It is the shift constant (in this case 630). If you try Shift(FIRST(LONGINT), -630) you get 0 as expected.
> >>>>
> >>>>
> >>>> So, in fact the run-time error is correct! 630 is not in the range [0..63].
> >>>>
> >>>>
> >>>>
> >>>> On 2 Mar 2010, at 13:54, Tony Hosking wrote:
> >>>>
> >>>>
> >>>>
> >>>>
> >>>> I'm trying to understand this. Surely shifting right will never be out of range? Looks like something is broken.
> >>>>
> >>>>
> >>>>
> >>>> On 2 Mar 2010, at 09:04, Jay K wrote:
> >>>>
> >>>>
> >>>>
> >>>> PutLH(Long.RightShift(FIRST(LONGINT), 630)); PutT("\n");
> >>>>
> >>>>
> >>>> I'm guessing the warning is all you're supposed to get here?
> >>>>
> >>>>
> >>>> C:\dev2\cm3.2\m3-sys\m3tests\src\p2\p227>cm3
> >>>> --- building in NT386 ---
> >>>> new source -> compiling Main.m3
> >>>> "..\Main.m3", line 894: warning: value out of range
> >>>>
> >>>> ***
> >>>> *** runtime error:
> >>>> *** An enumeration or subrange value was out of range.
> >>>> *** file "..\src\TWordN.m3", line 129
> >>>> ***
> >>>> Stack trace:
> >>>> FP PC Procedure
> >>>> --------- --------- -------------------------------
> >>>> 0x12f0dc 0x48791a RightShift + 0x35 in ..\src\TWordN.m3
> >>>> 0x12f15c 0x47c62f doshift + 0x2c6 in ..\src\Stackx86.m3
> >>>> 0x12f188 0x4485d2 shift_right + 0x1b2 in ..\src\M3x86.m3
> >>>> 0x12f1ac 0x6414ed shift_right + 0xf5 in ..\src\M3CG_Check.m3
> >>>> 0x12f1d4 0x505a4f Shift_right + 0x87 in ..\src\misc\CG.m3
> >>>> 0x12f1f8 0x570641 CompileR + 0x1da in ..\NT386\LongShift.m3 => ..\src\builti
> >>>> nWord\Shift.mg
> >>>> 0x12f218 0x5cec2f Compile + 0x83 in ..\src\exprs\CallExpr.m3
> >>>> 0x12f234 0x5bfee4 Compile + 0x53 in ..\src\exprs\Expr.m3
> >>>> 0x12f274 0x5d19a7 EmitChecks + 0xdf in ..\src\exprs\CheckExpr.m3
> >>>> 0x12f2b4 0x5c8b15 GenOrdinal + 0xa6 in ..\src\values\Formal.m3
> >>>> ......... ......... ... more frames ...
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20100303/dbd155ac/attachment-0002.html>
More information about the M3devel
mailing list