This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Fold pointer range checks with equal spans

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

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

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

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]