Re: Optimization techniques and undefined behavior

On 03/05/2019 00:48, Bart wrote:
>>> If you have two unknown values A and B, and need to multiply, you won't
>>> know if the result will overflow.
>>   int A := ..., B := ...;
>>   int C := ( A = 0 | 0 |: abs B <= maxint % abs A | A*B | error (...); 0 );
> That sounds unmanageable


Indeed, but it was a proof of concept. Obviously, you can tuck
that line away either using a macro definition or as a function/operator.


> (think about checks here: a*a+b*(c*d), and how
> you might proceed from the error if not aborting) and inefficient if one
> multiply turns into half a dozen operations including a divide.


How quickly do you want your buggy results? If you have to write
code to check, then it takes time, both to write and to execute. Yes, if
you have a complicated expression, it takes lots of time to execute, and
your program will run much more slowly.


> If such overflow checks need to be routinely done, then it really needs
> language support.


If you want to regain efficiency, then it needs not language so
much as hardware support. Yes, you then need a language hook into that
hardware. Early computers/languages typically had statements something
like


      on overflow goto l
      arrayboundcheck off


to give the programmer fine control over the checks and what to do if
the traps were sprung. But it really only works well if the hardware
can generate an interrupt.


> Otherwise it's probably best handled by a guard
> function similar to what someone posted:
>     if multiply_overflow(a,b) then
>          print "Overflow"
>     else
>          c := a * b        # requires that a and b haven't changed
>     end


I would prefer "c := a &* b;" or similar, where "&*" is a "safe
multiply" [which you can write yourself in languages that support user-
defined operators]. So your example above becomes


      a &* a &+ b &* (c &* d)


You can solve the "abort?" problem by having a procedure that is called
when "&*" detects overflow.


> This at least isolates the actual expression we want and leaves it readable.


Yes, but, in the absence of hardware support, it's not going to
be any more efficient than my code [or some near equivalent] above.


>>      Of course, in the old days, compilers used to build in range
>> checks on array indices and overflow checks on all arithmetic.
> Did they? Certainly not any of mine (not really practical on tiny 8-bit
> computers on which both the compiler and the program being developed had
> to run).


You're too young. C on a PDP-11/34 running Unix, in the mid-70s,
was roughly the 10th serious language and the 5th computer/OS I used over
16 years or so, and the first that did not have array-bound checks and
overflow checks compiled in and switched on by default.


>>   A few
>> still do, esp interpreters, but the God of Speed dictates that most
>> languages in most circumstances don't.  We see the results in the huge
>> amount of malware that exploits that failure.
> I don't know how much that would help. And I think that if a program can
> go seriously wrong through unchecked input, then that's a failure in
> proper validation. It's rather sloppy to rely on a runtime check put
> their by a compiler.


Counsel of perfection. The reality is that every week I get
bug fixes to major software on my computer that consists of cures for
buffer over-runs, dereferencing null or dangling pointers, overflow
conditions, race conditions, storage leakage, .... All of those can
be exploited by carefully-crafted malware. All of them, except perhaps
some race conditions, can be detected before the exploit by checks put
there by a compiler. Most of the checks can be optimised away in well-
written code for a decent language.


> During development, yes, but perhaps not after a program is supposed to
> be working.


Dijkstra[?] wrote along the lines of "It's like wearing water
wings to paddle around the swimming pool and discarding them when you
swim out to sea". [I've looked for the exact quote, but can't find it.]


--
Andy Walker,
Nottingham.

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