Re: Fold pointer range checks with equal spans

[Marc Glisse <marc.glisse@inria.fr>]

On Wed, 1 Aug 2018, Richard Sandiford wrote:

> +/* For pointers @0 and @2 and nonnegative constant offset @1, look for
> +   expressions like:
> +
> +   A: (@0 + @1 < @2) | (@2 + @1 < @0)
> +   B: (@0 + @1 <= @2) | (@2 + @1 <= @0)

Once this is in, we may want to consider the opposite:

(@0 + @1 > @2) & (@2 + @1 > @0)

> +     /* Always fails for negative values.  */
> +     (if (wi::min_precision (rhs, UNSIGNED) <= TYPE_PRECISION (sizetype))

I guess we could simplify to 'true' in the 'else' case but that's less
interesting.

>> Turning multiple comparisons of the form P + cst CMP Q + cst into a
>> range check on P - Q sounds good (we don't really have to restrict to
>> the case where the range is symmetric). Actually, just turning P + cst
>> CMP Q + cst into P - Q CMP cst should do it, we should already have code
>> to handle range checking on integers (modulo the issue of CSE P-Q and
>> Q-P). But I don't know if a couple :s is sufficient to make this
>> transformation a good canonicalization.
>
> Yeah.  Like you say, in the cases being handled by the patch, folding the
> two comparisons separately and then folding the IOR would require either
>
> (a) folding:
>       P + cst < Q
>    to the rather unnatural-looking:
>       Q - P > -cst
>    when tree_swap_operands_p (P, Q) or

Is it unnatural? If it helps other optimizations, it doesn't look that
bad to me ;-)

One issue is if we start mixing forms because only one is single_use:
@0 + @1 < @2 | @1 < @0 - @2

> (b) making the range fold handle reversed pointer_diffs (which I guess
>    makes more sense).

It would be interesting to have a way to write:

(plus @0 (opposite@1 @0))

which would match if @0 is a-b and @1 is b-a or anything similar (I
don't want to repeat all the cases of negate, minus, pointer_diff, etc
in each transformation), but

(match (opposite (minus @0 @1)) (minus @1 @0))

is not a valid syntax. More likely we would write

(plus @0 @1) (if (opposite_p (@0, @1))

with opposite_p defined outside of match.pd :-(

Maybe there is a way to simulate binary predicates on @0 @1 using unary
predicates on (artificial @0 @1).

(looks like I forgot to add pointer_diff to negate_expr_p)

>> If we start from a comparison of pointer_plus, I think it would make
>> sense to use pointer_diff.
>>
>> I believe currently we try to use pointer operations (pointer_plus,
>> pointer_diff, lt) only for related pointers and we cast to some integer
>> type for wilder cases (implementation of std::less in C++ for instance).
>> On the other hand, in an alias check, the 2 pointers are possibly
>> unrelated, so maybe the code emitted for an alias check should be
>> changed.
>
> If we can prove that the pointers are to different objects, it would
> be valid to fold the check to "no alias", regardless of the constant
> (although in practice we should have weeded out those cases before
> generating the check).  In that sense, relying on the UBness of
> comparing pointers to different objects would be fine.  If there's a
> risk of the check being folded to "alias" when the pointers are known
> to point to different objects then that would be more of a problem
> (as a missed optimisation).

Assuming they are related, we are also assuming that pointer_diff will
not overflow. But for unrelated objects, in particular on 32bit targets,
pointer differences cannot all be represented by a 32 bit ptrdiff_t (the
differences live in a range twice that size), and doing comparisons on
it can have strange effects. In this particular case, I don't really see
a way things could break (you would somehow need one pointer close to 0
and the other close to 2^32 so they end up close modulo 2^32, but that
would require @2+@1 to overflow which means the loop will never run that
far anyway).

But we are still lying and taking a risk that some other optimization
will trust us. (I am ok with keeping the current alias code, just saying
that it involves a small, possibly negligible risk)

-- 
Marc Glisse