* [PATCH] Move X - (X / Y) * Y folding to match.pd
@ 2015-06-26 16:39 Marek Polacek
2015-06-27 14:53 ` Marc Glisse
0 siblings, 1 reply; 7+ messages in thread
From: Marek Polacek @ 2015-06-26 16:39 UTC (permalink / raw)
To: GCC Patches, Richard Biener
This is an attempt to move one pattern from fold-const.c to match.pd.
It ought to be 1:1, but is not, e.g. with this patch we won't fold e.g.
int
f (int a, int b)
{
return a - (unsigned) ((a / b) * b)
}
anymore, but we're able to fold
int
ff (int a, unsigned int b)
{
return a - ((a / b) * b);
}
and fold-const.c is not. I played around with converts, but didn't find
anything that would work well. Any suggestions how to make this pattern
better?
More to come...
Bootstrapped/regtested on x86_64-linux, ok for trunk?
2015-06-26 Marek Polacek <polacek@redhat.com>
* fold-const.c (fold_binary_loc): Move X - (X / Y) * Y -> X % Y to ...
* match.pd: ... pattern here.
diff --git gcc/fold-const.c gcc/fold-const.c
index 6f12dd0..01e3983 100644
--- gcc/fold-const.c
+++ gcc/fold-const.c
@@ -10509,19 +10509,6 @@ fold_binary_loc (location_t loc,
fold_convert_loc (loc, type,
TREE_OPERAND (arg0, 0)));
- /* X - (X / Y) * Y is X % Y. */
- if ((INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
- && TREE_CODE (arg1) == MULT_EXPR
- && TREE_CODE (TREE_OPERAND (arg1, 0)) == TRUNC_DIV_EXPR
- && operand_equal_p (arg0,
- TREE_OPERAND (TREE_OPERAND (arg1, 0), 0), 0)
- && operand_equal_p (TREE_OPERAND (TREE_OPERAND (arg1, 0), 1),
- TREE_OPERAND (arg1, 1), 0))
- return
- fold_convert_loc (loc, type,
- fold_build2_loc (loc, TRUNC_MOD_EXPR, TREE_TYPE (arg0),
- arg0, TREE_OPERAND (arg1, 1)));
-
if (! FLOAT_TYPE_P (type))
{
/* Fold A - (A & B) into ~B & A. */
diff --git gcc/match.pd gcc/match.pd
index b2f8429..2bc158b 100644
--- gcc/match.pd
+++ gcc/match.pd
@@ -238,6 +238,12 @@ along with GCC; see the file COPYING3. If not see
&& tree_nop_conversion_p (type, TREE_TYPE (@1)))
(trunc_mod @0 (convert @1))))
+/* X - (X / Y) * Y is the same as X % Y. */
+(simplify
+ (minus @0 (mult (trunc_div @0 @1) @1))
+ (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
+ (trunc_mod @0 @1)))
+
/* Optimize TRUNC_MOD_EXPR by a power of two into a BIT_AND_EXPR,
i.e. "X % C" into "X & (C - 1)", if X and C are positive.
Also optimize A % (C << N) where C is a power of 2,
Marek
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] Move X - (X / Y) * Y folding to match.pd
2015-06-26 16:39 [PATCH] Move X - (X / Y) * Y folding to match.pd Marek Polacek
@ 2015-06-27 14:53 ` Marc Glisse
2015-06-29 7:58 ` Richard Biener
0 siblings, 1 reply; 7+ messages in thread
From: Marc Glisse @ 2015-06-27 14:53 UTC (permalink / raw)
To: Marek Polacek; +Cc: GCC Patches, Richard Biener
On Fri, 26 Jun 2015, Marek Polacek wrote:
> This is an attempt to move one pattern from fold-const.c to match.pd.
> It ought to be 1:1, but is not, e.g. with this patch we won't fold e.g.
>
> int
> f (int a, int b)
> {
> return a - (unsigned) ((a / b) * b)
> }
>
> anymore, but we're able to fold
>
> int
> ff (int a, unsigned int b)
> {
> return a - ((a / b) * b);
> }
>
> and fold-const.c is not. I played around with converts, but didn't find
> anything that would work well. Any suggestions how to make this pattern
> better?
Anything wrong with this?
+/* X - (X / Y) * Y is the same as X % Y. */
+(simplify
+ (minus (convert? @0) (convert? (mult (trunc_div @0 @1) @1)))
+ (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
+ (convert (trunc_mod @0 @1))))
(the other div/mod pairs could benefit from the same transformation as
long as there are no conversions, but the conversion seems easier to
handle with trunc_)
> diff --git gcc/match.pd gcc/match.pd
> index b2f8429..2bc158b 100644
> --- gcc/match.pd
> +++ gcc/match.pd
> @@ -238,6 +238,12 @@ along with GCC; see the file COPYING3. If not see
> && tree_nop_conversion_p (type, TREE_TYPE (@1)))
> (trunc_mod @0 (convert @1))))
>
> +/* X - (X / Y) * Y is the same as X % Y. */
> +(simplify
> + (minus @0 (mult (trunc_div @0 @1) @1))
> + (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
> + (trunc_mod @0 @1)))
> +
> /* Optimize TRUNC_MOD_EXPR by a power of two into a BIT_AND_EXPR,
> i.e. "X % C" into "X & (C - 1)", if X and C are positive.
> Also optimize A % (C << N) where C is a power of 2,
>
> Marek
>
--
Marc Glisse
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] Move X - (X / Y) * Y folding to match.pd
2015-06-27 14:53 ` Marc Glisse
@ 2015-06-29 7:58 ` Richard Biener
2015-06-29 14:04 ` Marek Polacek
0 siblings, 1 reply; 7+ messages in thread
From: Richard Biener @ 2015-06-29 7:58 UTC (permalink / raw)
To: GCC Patches; +Cc: Marek Polacek
On Sat, 27 Jun 2015, Marc Glisse wrote:
> On Fri, 26 Jun 2015, Marek Polacek wrote:
>
> > This is an attempt to move one pattern from fold-const.c to match.pd.
> > It ought to be 1:1, but is not, e.g. with this patch we won't fold e.g.
> >
> > int
> > f (int a, int b)
> > {
> > return a - (unsigned) ((a / b) * b)
> > }
> >
> > anymore, but we're able to fold
> >
> > int
> > ff (int a, unsigned int b)
> > {
> > return a - ((a / b) * b);
> > }
> >
> > and fold-const.c is not.
Interesting.
> > I played around with converts, but didn't find
> > anything that would work well. Any suggestions how to make this pattern
> > better?
>
> Anything wrong with this?
>
> +/* X - (X / Y) * Y is the same as X % Y. */
> +(simplify
> + (minus (convert? @0) (convert? (mult (trunc_div @0 @1) @1)))
> + (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
> + (convert (trunc_mod @0 @1))))
Yes. Eventually even (convert? (mult (convert1? (trunc_div ...)?
Of course with matching @0 between the two operands of the minus
you constrain types quite a bit.
I'd say just single-step through fold and see what types it get
present when folding a - (unsigned) ((a / b) * b).
Thanks,
Richard.
> (the other div/mod pairs could benefit from the same transformation as long as
> there are no conversions, but the conversion seems easier to handle with
> trunc_)
>
> > diff --git gcc/match.pd gcc/match.pd
> > index b2f8429..2bc158b 100644
> > --- gcc/match.pd
> > +++ gcc/match.pd
> > @@ -238,6 +238,12 @@ along with GCC; see the file COPYING3. If not see
> > && tree_nop_conversion_p (type, TREE_TYPE (@1)))
> > (trunc_mod @0 (convert @1))))
> >
> > +/* X - (X / Y) * Y is the same as X % Y. */
> > +(simplify
> > + (minus @0 (mult (trunc_div @0 @1) @1))
> > + (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
> > + (trunc_mod @0 @1)))
> > +
> > /* Optimize TRUNC_MOD_EXPR by a power of two into a BIT_AND_EXPR,
> > i.e. "X % C" into "X & (C - 1)", if X and C are positive.
> > Also optimize A % (C << N) where C is a power of 2,
> >
> > Marek
> >
>
>
--
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Dilip Upmanyu, Graham Norton, HRB 21284 (AG Nuernberg)
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] Move X - (X / Y) * Y folding to match.pd
2015-06-29 7:58 ` Richard Biener
@ 2015-06-29 14:04 ` Marek Polacek
2015-06-29 14:09 ` Richard Biener
2015-06-29 22:26 ` Marc Glisse
0 siblings, 2 replies; 7+ messages in thread
From: Marek Polacek @ 2015-06-29 14:04 UTC (permalink / raw)
To: Richard Biener; +Cc: GCC Patches
On Mon, Jun 29, 2015 at 09:36:59AM +0200, Richard Biener wrote:
> > Anything wrong with this?
> >
> > +/* X - (X / Y) * Y is the same as X % Y. */
> > +(simplify
> > + (minus (convert? @0) (convert? (mult (trunc_div @0 @1) @1)))
> > + (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
> > + (convert (trunc_mod @0 @1))))
That looks awfully similar to a variant I also tried (but I remember
having convert1? and convert2? in it). Not sure what was wrong with
that one; certainly yours seems to work fine.
Not sure whether we need some tree_nop_conversion_p in it. Perhaps not.
> Yes. Eventually even (convert? (mult (convert1? (trunc_div ...)?
> Of course with matching @0 between the two operands of the minus
> you constrain types quite a bit.
I'm starting to dislike this whole convert business ;).
> I'd say just single-step through fold and see what types it get
> present when folding a - (unsigned) ((a / b) * b).
I did that. The whole expression has type "unsigned int", arg0
is "a" of type int and arg1 is "(a / b) * b" of type int.
The following version is what Marc suggests.
Bootstrapped/regtested on x86_64-linux, ok for trunk?
2015-06-29 Marek Polacek <polacek@redhat.com>
Marc Glisse <marc.glisse@inria.fr>
* fold-const.c (fold_binary_loc): Move X - (X / Y) * Y -> X % Y to ...
* match.pd: ... pattern here.
diff --git gcc/fold-const.c gcc/fold-const.c
index 6f12dd0..01e3983 100644
--- gcc/fold-const.c
+++ gcc/fold-const.c
@@ -10509,19 +10509,6 @@ fold_binary_loc (location_t loc,
fold_convert_loc (loc, type,
TREE_OPERAND (arg0, 0)));
- /* X - (X / Y) * Y is X % Y. */
- if ((INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
- && TREE_CODE (arg1) == MULT_EXPR
- && TREE_CODE (TREE_OPERAND (arg1, 0)) == TRUNC_DIV_EXPR
- && operand_equal_p (arg0,
- TREE_OPERAND (TREE_OPERAND (arg1, 0), 0), 0)
- && operand_equal_p (TREE_OPERAND (TREE_OPERAND (arg1, 0), 1),
- TREE_OPERAND (arg1, 1), 0))
- return
- fold_convert_loc (loc, type,
- fold_build2_loc (loc, TRUNC_MOD_EXPR, TREE_TYPE (arg0),
- arg0, TREE_OPERAND (arg1, 1)));
-
if (! FLOAT_TYPE_P (type))
{
/* Fold A - (A & B) into ~B & A. */
diff --git gcc/match.pd gcc/match.pd
index b2f8429..2bc158b 100644
--- gcc/match.pd
+++ gcc/match.pd
@@ -238,6 +238,12 @@ along with GCC; see the file COPYING3. If not see
&& tree_nop_conversion_p (type, TREE_TYPE (@1)))
(trunc_mod @0 (convert @1))))
+/* X - (X / Y) * Y is the same as X % Y. */
+(simplify
+ (minus (convert? @0) (convert? (mult (trunc_div @0 @1) @1)))
+ (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
+ (convert (trunc_mod @0 @1))))
+
/* Optimize TRUNC_MOD_EXPR by a power of two into a BIT_AND_EXPR,
i.e. "X % C" into "X & (C - 1)", if X and C are positive.
Also optimize A % (C << N) where C is a power of 2,
Marek
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] Move X - (X / Y) * Y folding to match.pd
2015-06-29 14:04 ` Marek Polacek
@ 2015-06-29 14:09 ` Richard Biener
2015-06-29 22:26 ` Marc Glisse
1 sibling, 0 replies; 7+ messages in thread
From: Richard Biener @ 2015-06-29 14:09 UTC (permalink / raw)
To: Marek Polacek; +Cc: GCC Patches
On Mon, 29 Jun 2015, Marek Polacek wrote:
> On Mon, Jun 29, 2015 at 09:36:59AM +0200, Richard Biener wrote:
> > > Anything wrong with this?
> > >
> > > +/* X - (X / Y) * Y is the same as X % Y. */
> > > +(simplify
> > > + (minus (convert? @0) (convert? (mult (trunc_div @0 @1) @1)))
> > > + (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
> > > + (convert (trunc_mod @0 @1))))
>
> That looks awfully similar to a variant I also tried (but I remember
> having convert1? and convert2? in it). Not sure what was wrong with
> that one; certainly yours seems to work fine.
>
> Not sure whether we need some tree_nop_conversion_p in it. Perhaps not.
>
> > Yes. Eventually even (convert? (mult (convert1? (trunc_div ...)?
> > Of course with matching @0 between the two operands of the minus
> > you constrain types quite a bit.
>
> I'm starting to dislike this whole convert business ;).
;) fold-const.c STRIP_NOPS certainly was both convenient and
error-prone at the same time.
> > I'd say just single-step through fold and see what types it get
> > present when folding a - (unsigned) ((a / b) * b).
>
> I did that. The whole expression has type "unsigned int", arg0
> is "a" of type int and arg1 is "(a / b) * b" of type int.
>
> The following version is what Marc suggests.
>
> Bootstrapped/regtested on x86_64-linux, ok for trunk?
Ok.
Thanks,
Richard.
> 2015-06-29 Marek Polacek <polacek@redhat.com>
> Marc Glisse <marc.glisse@inria.fr>
>
> * fold-const.c (fold_binary_loc): Move X - (X / Y) * Y -> X % Y to ...
> * match.pd: ... pattern here.
>
> diff --git gcc/fold-const.c gcc/fold-const.c
> index 6f12dd0..01e3983 100644
> --- gcc/fold-const.c
> +++ gcc/fold-const.c
> @@ -10509,19 +10509,6 @@ fold_binary_loc (location_t loc,
> fold_convert_loc (loc, type,
> TREE_OPERAND (arg0, 0)));
>
> - /* X - (X / Y) * Y is X % Y. */
> - if ((INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
> - && TREE_CODE (arg1) == MULT_EXPR
> - && TREE_CODE (TREE_OPERAND (arg1, 0)) == TRUNC_DIV_EXPR
> - && operand_equal_p (arg0,
> - TREE_OPERAND (TREE_OPERAND (arg1, 0), 0), 0)
> - && operand_equal_p (TREE_OPERAND (TREE_OPERAND (arg1, 0), 1),
> - TREE_OPERAND (arg1, 1), 0))
> - return
> - fold_convert_loc (loc, type,
> - fold_build2_loc (loc, TRUNC_MOD_EXPR, TREE_TYPE (arg0),
> - arg0, TREE_OPERAND (arg1, 1)));
> -
> if (! FLOAT_TYPE_P (type))
> {
> /* Fold A - (A & B) into ~B & A. */
> diff --git gcc/match.pd gcc/match.pd
> index b2f8429..2bc158b 100644
> --- gcc/match.pd
> +++ gcc/match.pd
> @@ -238,6 +238,12 @@ along with GCC; see the file COPYING3. If not see
> && tree_nop_conversion_p (type, TREE_TYPE (@1)))
> (trunc_mod @0 (convert @1))))
>
> +/* X - (X / Y) * Y is the same as X % Y. */
> +(simplify
> + (minus (convert? @0) (convert? (mult (trunc_div @0 @1) @1)))
> + (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
> + (convert (trunc_mod @0 @1))))
> +
> /* Optimize TRUNC_MOD_EXPR by a power of two into a BIT_AND_EXPR,
> i.e. "X % C" into "X & (C - 1)", if X and C are positive.
> Also optimize A % (C << N) where C is a power of 2,
>
> Marek
>
>
--
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Dilip Upmanyu, Graham Norton, HRB 21284 (AG Nuernberg)
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] Move X - (X / Y) * Y folding to match.pd
2015-06-29 14:04 ` Marek Polacek
2015-06-29 14:09 ` Richard Biener
@ 2015-06-29 22:26 ` Marc Glisse
2015-06-30 7:45 ` Richard Biener
1 sibling, 1 reply; 7+ messages in thread
From: Marc Glisse @ 2015-06-29 22:26 UTC (permalink / raw)
To: Marek Polacek; +Cc: Richard Biener, GCC Patches
On Mon, 29 Jun 2015, Marek Polacek wrote:
> On Mon, Jun 29, 2015 at 09:36:59AM +0200, Richard Biener wrote:
>>> Anything wrong with this?
>>>
>>> +/* X - (X / Y) * Y is the same as X % Y. */
>>> +(simplify
>>> + (minus (convert? @0) (convert? (mult (trunc_div @0 @1) @1)))
>>> + (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
>>> + (convert (trunc_mod @0 @1))))
>
> That looks awfully similar to a variant I also tried (but I remember
> having convert1? and convert2? in it). Not sure what was wrong with
> that one; certainly yours seems to work fine.
Afterwards I thought of a limitation. Nothing bad, but it highlights a
trap I regularly fall into: several @0 in the same pattern may have
different types (for INTEGER_CST, operand_equal_p mostly ignores the
type). So for an int x, 42L-42/x*x should fail to match, while using
convert1? and convert2? should match.
--
Marc Glisse
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] Move X - (X / Y) * Y folding to match.pd
2015-06-29 22:26 ` Marc Glisse
@ 2015-06-30 7:45 ` Richard Biener
0 siblings, 0 replies; 7+ messages in thread
From: Richard Biener @ 2015-06-30 7:45 UTC (permalink / raw)
To: GCC Patches; +Cc: Marek Polacek
On Tue, 30 Jun 2015, Marc Glisse wrote:
> On Mon, 29 Jun 2015, Marek Polacek wrote:
>
> > On Mon, Jun 29, 2015 at 09:36:59AM +0200, Richard Biener wrote:
> > > > Anything wrong with this?
> > > >
> > > > +/* X - (X / Y) * Y is the same as X % Y. */
> > > > +(simplify
> > > > + (minus (convert? @0) (convert? (mult (trunc_div @0 @1) @1)))
> > > > + (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
> > > > + (convert (trunc_mod @0 @1))))
> >
> > That looks awfully similar to a variant I also tried (but I remember
> > having convert1? and convert2? in it). Not sure what was wrong with
> > that one; certainly yours seems to work fine.
>
> Afterwards I thought of a limitation. Nothing bad, but it highlights a trap I
> regularly fall into: several @0 in the same pattern may have different types
> (for INTEGER_CST, operand_equal_p mostly ignores the type). So for an int x,
> 42L-42/x*x should fail to match, while using convert1? and convert2? should
> match.
Indeed that's a subtle issue with using operand_equal_p for matching
operands. Note that 42L-42/x*x will appear as
42L-(long)(42/x*x) in the IL just in case that wasn't obvious.
Thus ok to adjust the pattern to convert1? / convert2? if you add such
a testcase (maybe also add the one that the variants you tried on
originally failed to match).
Richard.
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2015-06-30 7:35 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-06-26 16:39 [PATCH] Move X - (X / Y) * Y folding to match.pd Marek Polacek
2015-06-27 14:53 ` Marc Glisse
2015-06-29 7:58 ` Richard Biener
2015-06-29 14:04 ` Marek Polacek
2015-06-29 14:09 ` Richard Biener
2015-06-29 22:26 ` Marc Glisse
2015-06-30 7:45 ` Richard Biener
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).