robertwessel2@yahoo.com
7/10/2011 3:48:00 PM
On Sun, 10 Jul 2011 01:47:25 -0700 (PDT), tm <thomas.mertes@gmx.at>
wrote:
>On 8 Jul., 05:04, Patricia Shanahan <p...@acm.org> wrote:
>> On 7/7/2011 5:51 PM, Peter Duniho wrote:
>> ...
>>
>> > I would not worry about the "simple" or "efficient" criteria. IMHO, if
>> > one is deciding to apply overflow checking to every computation, one has
>> > already abandoned the hope of efficiency.
>>
>> Not necessarily. I assumed a couple of decades ago that array index
>> checking would be impossibly inefficient, but it seems to work fine in
>> Java.
>
>And in other languages, like Pascal, Ada and Seed7, as well.
A good compiler can often limit the number of time array bounds checks
to much less than every access. For example, a sequence of uses of
the same index value obvious only needs the index checked once, or a
loop with bounds that don't change during the loop can often move the
check ahead of the loop.
>> I suspect that having integer range types would be a major help.
>> When I'm working out whether an int can overflow, I often think in terms
>> of the ranges of inputs to calculations. A compiler would be able to
>> tell that adding a digit to a digit always fits in the range [0,18].
>
>I think there are two things:
>
> 1. range checks (like value fits in [0,18]).
> 2. check if an 32-bit (or 8-bit, 16-bit, 64-bit, ...)
> computation overflows.
>
>In the 1. case a compiler could generate code that does
>the computation and checks the range afterwards.
>In the 2. case a computation could result in wrong data,
>because the overflow was silently ignored. In this case
>either some checks must be done before the computation or
>the overfow condition is recognized during or after the
>computation. In an ideal world the hardware would do this.
>
>A CPU could (in theory) easily recognize the overflow
>and generate an interrupt. This way normal computations
>(without overflow) would have no extra cost. AFAIK
>commonly used CPUs do not have this possibility. They
>have some FLAG, which is set when an overflow occurred.
>But there is no possibility to cause an interrupt, when
>the overflow FLAG is set. So code, which checks for
>overflow, must check this flag after every computation.
>Needless to say: Normal computations (without overflow)
>are slowed down by this checks.
>
>Because of this slow down most compilers and virtual
>machines (AFAIK inluding the JVM) have no overflow
>checking.
>
>In other words: A missing hardware feature:
>
> Trigger interupt when overflow flag is set.
>
>Causes compilers and JVMs to omit overflow checks.
S/360 and its descendents have such a feature (for both binary and
decimal arithmetic), which can be enabled by applications by setting a
bit in the PSW. Nobody uses it. It doesn't do quite everything (for
example, the multiply instruction produces double width results, and
doesn't ever overflow, but you obviously have an issue if you're going
to store that result back in a single width variable). It also messes
up enough code, that what you'd really want is a separate set of
instruction that did or didn't trap on overflow (S/360 already has a
number of separate signed and unsigned binary arithmetic instructions,
the unsigned ones don't trap on "overflow").
In a similar vein, SNaNs are only rarely actually set to trap, even
though a lot of hardware that support IEEE math does support doing
that.