Re: [RFC PATCH] Fix pointer diff (was: -fsanitize=pointer-overflow support (PR sanitizer/80998))

[Marc Glisse <marc dot glisse at inria dot fr>]

On Wed, 21 Jun 2017, Jakub Jelinek wrote:

> So, I wrote following patch to do the subtraction in unsigned
> type.  It passes bootstrap, but on both x86_64-linux and i686-linux
> regresses:
> +FAIL: gcc.dg/torture/pr66178.c   -O*  (test for excess errors)
> +FAIL: gcc.dg/tree-ssa/cmpexactdiv-2.c scan-tree-dump-not optimized "minus_expr"
> +FAIL: g++.dg/tree-ssa/pr21082.C  -std=gnu++* (test for excess errors)
>
> E.g. in the first testcase we have in the test:
> static uintptr_t a =  ((char *)&&l2-(char *)&&l3)+((char *)&&l1-(char *)&&l2);
> Without the patch, we ended up with:
> static uintptr_t a = (uintptr_t) (((long int) &l2 - (long int) &l3) + ((long int) &l1 - (long int) &l2));
> but with the patch with (the negation in signed type sounds like a folding
> bug), which is too difficult for the initializer_constant_valid_p* handling:
> (uintptr_t) (((long unsigned int) -(long int) &l3 - (long unsigned int) &l2) + ((long unsigned int) &l2 + (long unsigned int) &l1));
> Shall we just xfail that test, or make sure we don't reassociate such
> subtractions, something different?

Adding to match.pd a few more simple reassoc transformations (like
(c-b)+(b-a) for instance) that work for both signed and unsigned is on
my TODO-list, though that may not be enough. Maybe together with fixing
whatever produced the negation would suffice?

> The second failure is on:
> int f (long *a, long *b, long *c) {
>    __PTRDIFF_TYPE__ l1 = b - a;
>    __PTRDIFF_TYPE__ l2 = c - a;
>    return l1 < l2;
> }
> where without the patch during forwprop2 we optimize it
> using match.pd:
> /* X - Z < Y - Z is the same as X < Y when there is no overflow.  */
> because we had:
>  b.0_1 = (long int) b_8(D);
>  a.1_2 = (long int) a_9(D);
>  _3 = b.0_1 - a.1_2;
>  c.2_4 = (long int) c_11(D);
>  a.3_5 = (long int) a_9(D);
>  _6 = c.2_4 - a.3_5;
>  _7 = _3 < _6;
> But with the patch we have:
>  b.0_1 = (long unsigned int) b_9(D);
>  a.1_2 = (long unsigned int) a_10(D);
>  _3 = b.0_1 - a.1_2;
>  _4 = (long int) _3;
>  c.2_5 = (long unsigned int) c_11(D);
>  _6 = c.2_5 - a.1_2;
>  _7 = (long int) _6;
>  _8 = _4 < _7;
> instead.  But that is something we can't generally optimize.
> So do we need to introduce POINTER_DIFF (where we could still
> optimize this) or remove the test?  If we rely on largest possible
> array to be half of the VA size - 1 (i.e. where for x > y both being
> pointers into the same array x - y > 0), then it is a valid optimization
> of the 2 pointer subtractions, but it is not a valid optimization on
> comparison of unsigned subtractions cast to signed type.

(this testcase was meant as a simpler version of
vector.size() < vector.capacity() )

It does indeed seem impossible to do this optimization with the unsigned
pointer subtraction.

If we consider pointers as unsigned, with a subtraction that has a signed 
result with the constraint that overflow is undefined, we cannot model 
that optimally with just the usual signed/unsigned operations, so I am in 
favor of POINTER_DIFF, at least in the long run (together with having a 
signed second argument for POINTER_PLUS, etc). For 64-bit platforms it 
might have been easier to declare that the upper half (3/4 ?) of the 
address space doesn't exist...

> The third one is
>        if (&a[b] - &a[c] != b - c)
>                link_error();
> where fold already during generic folding used to be able to cope with it,
> but now we have:
> (long int) (((long unsigned int) b - (long unsigned int) c) * 4) /[ex] 4 != b - c
> which we don't fold.

Once we have this last expression, we have lost, we need to know that the 
multiplication cannot overflow for this. When the size multiplications are 
done in a signed type in the future (?), it might help.

On the other hand, is this an important optimization? I am surprised we 
are only doing this transformation in generic (so some hack in the 
front-end could still work), it shouldn't be hard to implement some subset 
of fold_addr_of_array_ref_difference in match.pd (it is recursive so a 
complete move may be harder). But that would make your patch break even 
more stuff :-(

--
Marc Glisse