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

[Richard Biener <rguenther@suse.de>]

On Wed, 21 Jun 2017, Marc Glisse wrote:

> 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?

I guess try to fix the negation and see if that magically fixes things...

> > 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.

Yep :/  This is the issue with all the non-pointer integer folding
fixes as well -- as soon as we introduce unsigned ops for the fear
of introducing undefined overflow we lose on followup optimization
opportunities.

> 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...

I repeatedly thought of POINTER_DIFF_EXPR but adding such a basic tree
code is quite a big job.  So we'd have POINTER_DIFF_EXPR take two
pointer typed args and produce ptrdiff_t.  What's the advantage of
having this?  And yes, I agree that POINTER_PLUS_EXPR should take
ptrdiff_t rather than sizetype offset -- changing one without the
other will lead to awkwardness in required patterns involving
both like (p - q) + q.

As said, it's a big job with likely all sorts of (testsuite) fallout.

> > 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.

Not sure where the unsigned multiply comes from -- I guess we fold
it inside the cast ...

> 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 :-(

It's always the question whether the above testsuite regressions have any
real-world impact of course.

I don't like the idea of not doing foldings condidional on sanitization
too much.

Richard.