This is the mail archive of the
`gcc-patches@gcc.gnu.org`
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] |

*From*: Richard Biener <richard dot guenther at gmail dot com>*To*: Marc Glisse <marc dot glisse at inria dot fr>, GCC Patches <gcc-patches at gcc dot gnu dot org>, richard dot sandiford at arm dot com*Date*: Wed, 1 Aug 2018 13:58:49 +0200*Subject*: Re: Fold pointer range checks with equal spans*References*: <87in5a2odu.fsf@arm.com> <alpine.DEB.2.21.1807201401500.24375@stedding.saclay.inria.fr> <87tvoq0z8t.fsf@arm.com> <CAFiYyc2tYG_ng7tCzwUn5NsmZx0Wf2g-J0MHEg9+LE1d=OmcfA@mail.gmail.com> <87d0v4d3aa.fsf@arm.com> <CAFiYyc3ev_7WgA-sYukkH18rNoW5V=Vekt0tOifRrGkm169TWw@mail.gmail.com> <87tvoe9yen.fsf@arm.com>

On Wed, Aug 1, 2018 at 12:25 PM Richard Sandiford <richard.sandiford@arm.com> wrote: > > Richard Biener <richard.guenther@gmail.com> writes: > > On Mon, Jul 30, 2018 at 7:47 PM Richard Sandiford > > <richard.sandiford@arm.com> wrote: > >> > >> [Sorry, somehow missed this till now] > >> > >> Richard Biener <richard.guenther@gmail.com> writes: > >> > On Mon, Jul 23, 2018 at 5:05 PM Richard Sandiford > >> > <richard.sandiford@arm.com> wrote: > >> >> > >> >> Marc Glisse <marc.glisse@inria.fr> writes: > >> >> > On Fri, 20 Jul 2018, Richard Sandiford wrote: > >> >> > > >> >> >> --- gcc/match.pd 2018-07-18 18:44:22.565914281 +0100 > >> >> >> +++ gcc/match.pd 2018-07-20 11:24:33.692045585 +0100 > >> >> >> @@ -4924,3 +4924,37 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) > >> >> >> (if (inverse_conditions_p (@0, @2) > >> >> >> && element_precision (type) == element_precision (op_type)) > >> >> >> (view_convert (cond_op @2 @3 @4 @5 (view_convert:op_type @1))))))) > >> >> >> + > >> >> >> +/* For pointers @0 and @2 and unsigned constant offset @1, look for > >> >> >> + expressions like: > >> >> >> + > >> >> >> + A: (@0 + @1 < @2) | (@2 + @1 < @0) > >> >> >> + B: (@0 + @1 <= @2) | (@2 + @1 <= @0) > >> >> >> + > >> >> >> + If pointers are known not to wrap, B checks whether @1 bytes starting at > >> >> >> + @0 and @2 do not overlap, while A tests the same thing for @1 + 1 bytes. > >> >> >> + A is more efficiently tested as: > >> >> >> + > >> >> >> + ((sizetype) @0 - (sizetype) @2 + @1) > (@1 * 2) > >> >> >> + > >> >> >> + as long as @1 * 2 doesn't overflow. B is the same with @1 replaced > >> >> >> + with @1 - 1. */ > >> >> >> +(for ior (truth_orif truth_or bit_ior) > >> >> >> + (for cmp (le lt) > >> >> >> + (simplify > >> >> >> + (ior (cmp (pointer_plus:s @0 INTEGER_CST@1) @2) > >> >> >> + (cmp (pointer_plus:s @2 @1) @0)) > >> >> > > >> >> > Do you want :c on cmp, in case it appears as @2 > @0 + @1 ? (may > >> >> > need some > >> >> > care with "cmp == LE_EXPR" below) > >> >> > Do you want :s on cmp as well? > >> >> > > >> >> >> + (if (!flag_trapv && !TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0))) > >> >> > > >> >> > Don't you want TYPE_OVERFLOW_UNDEFINED? > >> >> > >> >> Thanks, fixed below. Think the cmp == LE_EXPR stuff is still ok with :c, > >> >> since the generated code sets cmp to LE_EXPR when matching GE_EXPR. > >> >> > >> >> Tested as before. OK to install? > >> >> > >> >> Richard > >> >> > >> >> > >> >> 2018-07-23 Richard Sandiford <richard.sandiford@arm.com> > >> >> > >> >> gcc/ > >> >> * match.pd: Optimise pointer range checks. > >> >> > >> >> gcc/testsuite/ > >> >> * gcc.dg/pointer-range-check-1.c: New test. > >> >> * gcc.dg/pointer-range-check-2.c: Likewise. > >> >> > >> >> Index: gcc/match.pd > >> >> =================================================================== > >> >> --- gcc/match.pd 2018-07-23 15:56:47.000000000 +0100 > >> >> +++ gcc/match.pd 2018-07-23 15:58:33.480269844 +0100 > >> >> @@ -4924,3 +4924,37 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) > >> >> (if (inverse_conditions_p (@0, @2) > >> >> && element_precision (type) == element_precision (op_type)) > >> >> (view_convert (cond_op @2 @3 @4 @5 (view_convert:op_type @1))))))) > >> >> + > >> >> +/* For pointers @0 and @2 and unsigned constant offset @1, look for > >> >> + expressions like: > >> >> + > >> >> + A: (@0 + @1 < @2) | (@2 + @1 < @0) > >> >> + B: (@0 + @1 <= @2) | (@2 + @1 <= @0) > >> >> + > >> >> + If pointers are known not to wrap, B checks whether @1 bytes starting at > >> >> + @0 and @2 do not overlap, while A tests the same thing for @1 + 1 bytes. > >> >> + A is more efficiently tested as: > >> >> + > >> >> + ((sizetype) @0 - (sizetype) @2 + @1) > (@1 * 2) > >> >> + > >> >> + as long as @1 * 2 doesn't overflow. B is the same with @1 replaced > >> >> + with @1 - 1. */ > >> >> +(for ior (truth_orif truth_or bit_ior) > >> >> + (for cmp (le lt) > >> >> + (simplify > >> >> + (ior (cmp:cs (pointer_plus:s @0 INTEGER_CST@1) @2) > >> >> + (cmp:cs (pointer_plus:s @2 @1) @0)) > >> >> + (if (!flag_trapv && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0))) > >> > > >> > no need to check flag_trapv, pointer arithmetic is not covered by -ftrapv. > >> > >> This was there because we're converting pointer arithmetic into integer > >> arithmetic, and -ftrapv could cause that new integer code to trap. > >> TYPE_OVERFLOW_UNDEFINED says that pointer overflow is undefined, > >> but it seemed bad form to make it actually trap, especially when the > >> above does some reassociation too. > > > > Ok, but then maybe check TYPE_OVERFLOW_WRAPS () on the type > > you are doing the arithmetic on (sizetype) instead? > > OK, done below. > > >> >> + /* Convert the B form to the A form. */ > >> >> + (with { offset_int off = wi::to_offset (@1) - (cmp == LE_EXPR ? 1 : > >> >> 0); } > >> >> + /* Always fails for negative values. */ > >> >> + (if (wi::min_precision (off, UNSIGNED) * 2 <= TYPE_PRECISION > >> >> (sizetype)) > >> >> + /* It doesn't matter whether we use @2 - @0 or @0 - @2, so let > >> >> + tree_swap_operands_p pick a canonical order. */ > >> > > >> > gimple_resimplify takes care of that - well, it doesn't since minus isn't > >> > commutative... I guess you get better CSE later when doing this thus ok, > >> > but it does look a bit off here ;) > >> > > >> > I think you shouldn't use 'sizetype' without guarding this whole thing > >> > with TYPE_PRECISION (sizetype) == TYPE_PRECISION (TREE_TYPE (@0)). > >> > >> OK, hadn't realised that could be false. Would building the appropriate > >> unsigned type be OK without the condition, or does it need to be sizetype? > > > > That would probably work but it might be dead slow on those targets that choose > > to have a lower-precision sizetype (ISTR some have 24bit pointers but 16bit > > sizetype because there's no arithmetic for 24bit but in offsetted addressing). > > So the transform is likely not a win for those. > > Ah, yeah. The version below adds the == test. > > >> > Since the original IL performs an ordered compare of two eventually > >> > unrelated > >> > pointers (or pointers adjusted in a way that crosses object > >> > boundaries) (uh... ;)) > >> > I wonder if you can use POINTER_DIFF_EXPR here to avoid the sizetype > >> > conversion? Since POINTER_PLUS_EXPR offsets are supposed to be > >> > interpreted "signed" that should also handle negative offsets > >> > correctly then? > >> > >> The transform isn't valid when @1 is negative though, so I think we > >> need that check either way. > > > > + /* Always fails for negative values. */ > > + (if (wi::min_precision (off, UNSIGNED) * 2 <= TYPE_PRECISION (sizetype)) > > > > shouldn't that be wi::min_precision (off * 2, UNSIGNED) <= > > TYPE_PRECISION (sizetype)? > > Gah, yes :-( > > >> I could use POINTER_DIFF_EXPR and convert to unsigned though, if that > >> seems better. That might also allow us to CSE the retained > >> POINTER_PLUS_EXPRs. > > > > Yeah, that sounds better then. > > And the CSEing did happen, so we now get the "ideal" sequence for the > original alias checks: > > add x0, x0, 15 > sub x6, x0, x1 > sub x5, x0, x2 > cmp x6, 30 > ccmp x5, 30, 0, hi > > whereas the original patch had an extra add. > > >> > Also, when @2 == @0 + (@1+1) then the original condition is true but > >> > ((sizetype) @0 - (sizetype) @2 + @1) > (@1 * 2) is not? > >> > (sizetype) @0 - (sizetype) (@0 + @1 + 1) + @1 > @1 * 2 > >> > -> -1 > @1 * 2 > >> > > >> > which is false. So I can't really see how you can apply this transform in > >> > general (it would be fine for generating alias checks but a bit more > >> > pessimistic). > >> > > >> > But maybe I am missing something? > >> > >> It relies on sizetype being unsigned: (sizetype)-1 > @1 * 2 is true. > > > > Hmm, so mathematically this is > > > > (@0 - @2) % modreduce + @1 > @1 * 2 > > Probably not % if you operating over Z, since if @0 - @2 = -@1 * 2 > (and -@1 * 2 % modreduce == -@1 * 2), the condition above will be false > while we want it to be true. But... > > > then, but I don't want to think too much about this since Marc didn't > > object here ;) > > ...we start out converting the range check for A to: > > !(-@1 <= @0 - @2 <= @1) > > i.e. @1 + 1 bytes at @0 and @2 are free from overlap. Then we just > apply the usual trick: > > A <= X <= B -> (unsigned) (X - A) <= (unsigned) (B - A) when A <= B > > Substituting @0 - @2 for X, -@1 for A and @1 for B gives: > > !((unsigned) (@0 - @2 + @1) <= (unsigned) (@1 * 2)) > -> (unsigned) (@0 - @2 + @1) > (unsigned) (@1 * 2) > > Then the B case is just an off-by-one variant. > > Patch tested as before. OK. Thanks, Richard. > Thanks, > Richard > > > 2018-08-01 Richard Sandiford <richard.sandiford@arm.com> > > gcc/ > * match.pd: Optimise pointer range checks. > > gcc/testsuite/ > * gcc.dg/pointer-range-check-1.c: New test. > * gcc.dg/pointer-range-check-2.c: Likewise. > > Index: gcc/match.pd > =================================================================== > --- gcc/match.pd 2018-07-24 19:04:14.985363724 +0100 > +++ gcc/match.pd 2018-08-01 10:55:10.695766411 +0100 > @@ -4937,3 +4937,63 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) > (if (inverse_conditions_p (@0, @2) > && element_precision (type) == element_precision (op_type)) > (view_convert (cond_op @2 @3 @4 @5 (view_convert:op_type @1))))))) > + > +/* 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) > + > + If pointers are known not to wrap, B checks whether @1 bytes starting > + at @0 and @2 do not overlap, while A tests the same thing for @1 + 1 > + bytes. A is more efficiently tested as: > + > + A: (sizetype) (@0 + @1 - @2) > @1 * 2 > + > + The equivalent expression for B is given by replacing @1 with @1 - 1: > + > + B: (sizetype) (@0 + (@1 - 1) - @2) > (@1 - 1) * 2 > + > + @0 and @2 can be swapped in both expressions without changing the result. > + > + The folds rely on sizetype's being unsigned (which is always true) > + and on its being the same width as the pointer (which we have to check). > + > + The fold replaces two pointer_plus expressions, two comparisons and > + an IOR with a pointer_plus, a pointer_diff, and a comparison, so in > + the best case it's a saving of two operations. The A fold retains one > + of the original pointer_pluses, so is a win even if both pointer_pluses > + are used elsewhere. The B fold is a wash if both pointer_pluses are > + used elsewhere, since all we end up doing is replacing a comparison with > + a pointer_plus. We do still apply the fold under those circumstances > + though, in case applying it to other conditions eventually makes one of the > + pointer_pluses dead. */ > +(for ior (truth_orif truth_or bit_ior) > + (for cmp (le lt) > + (simplify > + (ior (cmp:cs (pointer_plus@3 @0 INTEGER_CST@1) @2) > + (cmp:cs (pointer_plus@4 @2 @1) @0)) > + (if (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0)) > + && TYPE_OVERFLOW_WRAPS (sizetype) > + && TYPE_PRECISION (TREE_TYPE (@0)) == TYPE_PRECISION (sizetype)) > + /* Calculate the rhs constant. */ > + (with { offset_int off = wi::to_offset (@1) - (cmp == LE_EXPR ? 1 : 0); > + offset_int rhs = off * 2; } > + /* Always fails for negative values. */ > + (if (wi::min_precision (rhs, UNSIGNED) <= TYPE_PRECISION (sizetype)) > + /* Since the order of @0 and @2 doesn't matter, let tree_swap_operands_p > + pick a canonical order. This increases the chances of using the > + same pointer_plus in multiple checks. */ > + (with { bool swap_p = tree_swap_operands_p (@0, @2); > + tree rhs_tree = wide_int_to_tree (sizetype, rhs); } > + (if (cmp == LT_EXPR) > + (gt (convert:sizetype > + (pointer_diff:ssizetype { swap_p ? @4 : @3; } > + { swap_p ? @0 : @2; })) > + { rhs_tree; }) > + (gt (convert:sizetype > + (pointer_diff:ssizetype > + (pointer_plus { swap_p ? @2 : @0; } > + { wide_int_to_tree (sizetype, off); }) > + { swap_p ? @0 : @2; })) > + { rhs_tree; }))))))))) > Index: gcc/testsuite/gcc.dg/pointer-range-check-1.c > =================================================================== > --- /dev/null 2018-07-26 10:26:13.137955424 +0100 > +++ gcc/testsuite/gcc.dg/pointer-range-check-1.c 2018-08-01 10:55:10.695766411 +0100 > @@ -0,0 +1,37 @@ > +/* { dg-do compile { target { ilp32 || lp64 } } } */ > +/* { dg-options "-O2 -fno-ipa-icf -fdump-tree-optimized" } */ > + > +/* All four functions should be folded to: > + > + (sizetype) (a + 15 - b) < 30. */ > + > +_Bool > +f1 (char *a, char *b) > +{ > + return (a + 16 <= b) || (b + 16 <= a); > +} > + > +_Bool > +f2 (char *a, char *b) > +{ > + return (a + 15 < b) || (b + 15 < a); > +} > + > +_Bool > +f3 (char *a, char *b) > +{ > + return (a + 16 <= b) | (b + 16 <= a); > +} > + > +_Bool > +f4 (char *a, char *b) > +{ > + return (a + 15 < b) | (b + 15 < a); > +} > + > +/* { dg-final { scan-tree-dump-times { = [^\n]* - [^\n]*;} 4 "optimized" } } */ > +/* { dg-final { scan-tree-dump-times { = [^\n]* \+ [^\n]*;} 4 "optimized" } } */ > +/* { dg-final { scan-tree-dump-times { = [^\n]*\ > [^\n]*;} 4 "optimized" } } */ > +/* { dg-final { scan-tree-dump-not {=[^\n]*\ < [^\n]*;} "optimized" } } */ > +/* { dg-final { scan-tree-dump-times { \+ 15} 4 "optimized" } } */ > +/* { dg-final { scan-tree-dump-times { > 30} 4 "optimized" } } */ > Index: gcc/testsuite/gcc.dg/pointer-range-check-2.c > =================================================================== > --- /dev/null 2018-07-26 10:26:13.137955424 +0100 > +++ gcc/testsuite/gcc.dg/pointer-range-check-2.c 2018-08-01 10:55:10.695766411 +0100 > @@ -0,0 +1,31 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fno-ipa-icf -fwrapv-pointer -fdump-tree-optimized" } */ > + > +_Bool > +f1 (char *a, char *b) > +{ > + return (a + 16 <= b) || (b + 16 <= a); > +} > + > +_Bool > +f2 (char *a, char *b) > +{ > + return (a + 15 < b) || (b + 15 < a); > +} > + > +_Bool > +f3 (char *a, char *b) > +{ > + return (a + 16 <= b) | (b + 16 <= a); > +} > + > +_Bool > +f4 (char *a, char *b) > +{ > + return (a + 15 < b) | (b + 15 < a); > +} > + > +/* { dg-final { scan-tree-dump-not { = [^\n]* - [^\n]*;} "optimized" } } */ > +/* { dg-final { scan-tree-dump-times { = [^\n]* \+ [^\n]*;} 8 "optimized" } } */ > +/* { dg-final { scan-tree-dump-times { \+ 15} 4 "optimized" } } */ > +/* { dg-final { scan-tree-dump-times { \+ 16} 4 "optimized" } } */

**References**:**Re: Fold pointer range checks with equal spans***From:*Richard Sandiford

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |