Re: Optimization techniques

On 2019-05-01, David Brown <david.brown@hesbynett.no> wrote:
> On 01/05/2019 03:24, Gene Wirchenko wrote:
>> On Sun, 28 Apr 2019 23:49:53 +0200, David Brown
>> <david.brown@hesbynett.no> wrote:
>>
>> [snip]
>>
>>> If you are writing your code in a "C with the extra feature of having
>>> defined behaviour on signed integer overflow", and only compile it with
>>> suitable compilers (or compiler flags), then that's okay. But don't
>>> call it correct C code and blame compilers for your own mistakes or
>>> unwarranted assumptions.
>>
>> I would like to see it as part of the language. I *know* that I
>> want to have an error be thrown at run-time if an error can be
>> detected. (It is not an unwarranted assumption.) It is not as if
>> detecting signed integer overflow is a difficult thing on, for
>> example, System/370, which also dates from 1970.
>
> Detecting signed overflow at run-time can be a significant cost. It
> ruins expression manipulation, optimisation, and simplification - much


If we detect signed overflow and treat it as an error condition, then
we can optimize algebraically just as before, on the assumption that
overflow doesn't happen. If it does happen, we have a predictable
handling, rather than "undefined behavior". We just don't constrain the
exact situations when it must happen. I.e. as usual, optimizations are
permitted that can eliminate instances of overflow that would otherwise
happen if the specified arithmetic is followed, optimizations
that can introduce overflow aren't allowed.


> more than making signed overflow be two's complement. Even compared to
> a dumb translation compilation of expressions, it nearly doubles the
> size of the code on many processors as you have to follow each
> arithmetic instruction with a "jump if overflow".


Some can also set a processor flag which can be tested after a batch
of operations, rather than each one. That is reasonably cheap on those
processors because the flag is there anyway; you just have to peek at it
once in a while. Some RISCs can write overflow info into an additional
output register, rather than a global flag word, IIRC.


We often care about whether anything at all overflowed in a complex
expression, without caring about which specific operation on which
operands.


The design issue then is how to indicate the granularity of overflow
detection in the higher level language.


A scoped construct suggests itself, the "owfl" operator:


    owfl(expr, alt)


If anything inside expr overflows, then alt is evaluated, and taken
as the result of the expression. Considerations have to be given to how
this nests with itself, including through functions, and when/how does
the overflow condition get cleared. (We don't want it so that once an
overflow happens, every owfl subsequently executed defaults to its
alt until the program terminates.)


[FWIW the x86 series had an INTO instruction which interrupts if the
overflow flag is on, but they took it out of 64 bit mode. You can
still do a conditional jump or move. -John]

Return to the comp.compilers page.
Search the comp.compilers archives again.