Re: [RFC] Detect most integer overflows.

[OndÅej BÃlka <neleai at seznam dot cz>]

On Tue, Nov 26, 2013 at 12:31:00PM -0500, Geert Bosch wrote:
 
> >> [...]
> >> A few things helped to make the cost small: the biggest one is that
> >> typically on of the operands is known to be negative or positive.
> >> Gigi will use Ada type information, and Natural or Positive integer
> >> variables are very common.  So, if you compute X + C with C positive, 
> >> you can write the conditional expression as:
> > 
> > On x64 efect of this analysis is small, processor does overflow detection for you.
> 
> The problem as always is that of pass ordering. If we would encapsulate
> the overflow check some kind of builtin that we'd directly very late in
> the compilation process to processor-specific instructions, then early 
> optimizers cannot do their work.
>
That is flaw in gcc design, one can make these transparent to analysis by supplying
a equivalent alternative implementation. As one can supply a
implementation for early passes like in following implementation.
static inline uint64_t 
mul_s (uint64_t x, uint64_t y)
{
  if (__builtin_constant_p (x < (1L << 32)) && x < (1L << 32) &&
      __builtin_constant_p (y < (1L << 32)) && y < (1L << 32))
    return x * y;
  if (__builtin_constant_p (x) && __builtin_constant_p (y))
    if (x != 0 && UINT64_MAX / x < y)
      return -1;
    else
      return x * y;
  return builtin_mul_s (x, y);
}
 
> > By just expanding out to regular additions, comparisons and control
> > flow we can avoid this problem.
> > 
> >> (if X < Integer'Last - C then X + C else raise Constraint_Error)
> >> 
> > 
> >> On my x86-64 this generates something like:
> >> 00	cmpl	$0x7fffffff,%de
> >> 06	je	0x0000000c
> >> 08	leal	0x01(%rdi),%eax
> >> 0b	ret
> >> [..]
> > 
> > This has redundant compare instruction that cost a cycle and 6 bytes.
> > You can just write
> > 
> >   0:	83 c7 01             	add    $0x1,%edi
> >   3:	71 03                	jno    0x8
> > [...]
> > When you know that one operand is positive or you deal with unsigned
> > then you could replace jno with jnc which is bit faster on sandy bridge
> > processors and later as add, jnc pair is macro-fused but add jno is not.
> 
> Indeed that is ideal, assuming condition flags are dead, but I think
> that the right way to do that is by late combine-like optimizations
> after instruction selection.
> 
How would do you that for multiplication?

Addition is handled by gcc almost optimally, in following function gcc
does eliminate cmp but uses cmov instead of jump both on -Os and -O3
leading to larger code size.

uint64_t
add_s (uint64_t x, uint64_t y)
{
  if (__builtin_expect(x + y < x, 0))
    return -1;
  return x + y;
}

assembly is following:

  4003c0:	48 89 f8             	mov    %rdi,%rax
  4003c3:	48 c7 c2 ff ff ff ff 	mov    $0xffffffffffffffff,%rdx
  4003ca:	48 01 f0             	add    %rsi,%rax
  4003cd:	48 0f 42 c2          	cmovb  %rdx,%rax
  4003d1:	c3                   	retq

btw also when I replace -1 by x * y then cmov stays which is suboptimal
given a expect hint.

> In looking at generated code in actual programs, most checks are
> optimized away. This is more important than saving a cycle here or
> there in the much smaller number of checks that remain.

That specialization is unwarranted, this holds in general case but
calculating allocation size has different use pattern. A typical
use case is passing a size by argument or reading from io and allocating
apppropriate array.