Re: C as intermediate language, signed integer overflow and -ftrapv

["Thomas Mertes" <thomas dot mertes at gmx dot at>]

On Jul 30, 2014, at 16:39 Geert Bosch <boschg@mac.com> wrote:
> On Jul 23, 2014, at 10:56 AM, Thomas Mertes <thomas.mertes@gmx.at> wrote:
> 
> > One such feature is the detection of signed integer overflow. It is
> > not hard, to detect signed integer overflow with a generated C
> > program, but the performance is certainly not optimal. Signed integer
> > overflow is undefined behavior in C and the access to some overflow
> > flag of the CPU is machine dependent.
> 
> Actually, doing proper signed integer overflow checking in a front end 
> can be surprisingly cheap.
> 
> I have some experience with this for the Ada front end, and found the
> following:
>   - In many cases it may be cheapest to widen computations to avoid
>     overflow, and/or check it less frequently.

Do you do a dataflow analysis to avoid some overflow checks?
Seed7 supports only 64-bit signed integers. I am using 128-bit
arithmetic, when multiplying two values that are not known at
compile-time. In this case I multiply with 128-bit and check for
overflow afterwards. The the 128-bit product is checked for an
overflow with:
  (__int128_t) (int64_t) (product) != (product)
But maybe the simple check below is better:
  product < -9223372036854775808 && product > 9223372036854775807
Is it possible to decide that without performance measurements?
Until now I have avoided performance measurements for the target
C compiler.

Not all compilers support 128-bit arithmetic. For this case it is
necessary to do a division to get a bound for the overflow check.
When multiplying two values that are not known at compile-time
and without 128-bit arithmetic I use (a and b are factors,
l = -9223372036854775808, u = 9223372036854775807):

  a<0&&(b<0&&a<u/b||b>0&&a<l/b) || a>0&&(b<0&&b<l/a||b>0&&b>u/a)

Note that for the non-overflow case a division is done at
runtime: Either u/b, l/b, l/a or u/a must be computed.
Maybe you have an idea how to avoid the division.

>   - Even if you need to check, often one side is known to be constant,
>     in which case a simple comparison of the input argument is sufficient

For addition and subtraction I also do just one comparison, when one
argument is constant. When one side of a multiplication is known to
be constant I still have to check, if the other argument is within a
range. My range check for this was (l=lower bound, u=upper bound):
  x<l||x>u
Recently I discoved this (it works only for twos-complement):
  (unsigned)x-l>(unsigned)u-l
A quick measurement did not show a speedup. Maybe you have more
knowledge. Another posibility is:
  x<l|x>u
This would avoid a jump. Until now I have not measured it.
What would you suggest?

>   - In other cases, the sign of one of the operands is known,
>     simplifying the check
>   - Conversions from signed to unsigned types is essentially free and
>     well-defined, so do the overflow check using unsigned types, but use
>     signed integer operations for the actual computation:

Do you do the computation twice, once for the check and again for
the actual computation?

When a and b are not known at compile time I use the following
strategy for a += b. The addition is done with unsigned arithmetic
  c=(int64_t)((uint64_t)a+(uint64_t )b)
and the overflow check is done with
  b>0&&c<a || b<0&&c>a
Finally the result is assigned to a with
  a=c

When a and b are not known at compile time I use the following
strategy for a + b. The check for overflow is done with
  b<0&&a<INT64_MIN-b || b>=0&&a>INT64_MAX-b
Is the unsigned strategy better here? Do you know about a simpler
check? Using 128-bit arithmetic was slower than the check above.

>   - By using a simple comparison to jump to a no_return function, GCC
>     knows the condition is expected to be false and will optimize accordingly

My function to raise an exception is a no_return function.
For the exception conditions I use __builtin_expect to specify
that an exception is unlikely.

> Note that in the second case above, the extra conditional (which will almost
> always be correctly predicted by the CPU and often is free) will, combined with
> the conditional transfer of control to a no_return routine, in effect
> provide range information to the compiler, allowing the elimination of
> redundant checks etc. The positive effects of expanding checks to optimizable
> C-like constructs are far larger than the eventual instruction selection.
> We found the cost of overflow, even without "jo" instructions being generated,
> to be generally in the order of 1 - 2% in execution speed and a bit more in
> growth of executable size (in our case around 10% due to generating exceptions with
> location information).

In the moment I need more than 1 - 2% to do the overflow checking.
Maybe you have ideas how I could improve this.
I expected that a compiler frontend has more possibilities than C.

> If you make overflow checking "special" early by resorting specific builtins,
> -ftrapv or similar, you'll lose out in the general purpose optimization passes and in
> my experience will get far worse code. If your language semantics are: provide the
> numerically correct answer (as if computed with unbounded range) or raise an
> exception, you can probably do better by using wider types and smart expansions
> to avoid overflow while retaining C-level intermediate code.

Since I use 64-bit signed integers the possibility to use
wider types is limited.

> Anyway, the Ada front end is proof that efficient overflow checking is possible
> without any special support in the back end.

Thank you very much.
Hopefully you can help me to do a smarter overflow checking.
See my questions above.

Greetings Thomas Mertes

-- 
Seed7 Homepage:  http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.