[RFA] Factor conversion out of COND_EXPR using match.pd pattern

[RFA] Factor conversion out of COND_EXPR using match.pd pattern

[Jeff Law]

[-- Attachment #1: Type: text/plain, Size: 1541 bytes --]


I was working on polishing some of Kai's work to eliminate 
shorten_compare and stumbled on this tiny missed optimization.

Basically this change allows us to see something like this:

    n = (short unsigned int) mode_size[(unsigned int) mode] * 8 <= 64 ? 
(int) ((short unsigned int) mode_size[(unsigned int) mode] * 8) : 64;


Note the (int) cast on the true arm of the COND_EXPR.  We factor that 
out and adjust the constant (which is obviously free) into:

    n = (int)((short unsigned int) mode_size[(unsigned int) mode] * 8 <= 
64 ? ((short unsigned int) mode_size[(unsigned int) mode] * 8) : 64);


Seems subtle, but now the existing optimizers can recognize it as:

!   n = (int) MIN_EXPR <(short unsigned int) mode_size[(unsigned int) 
mode] * 8, 64>;


In another case I saw we had the same kind of transformation occur, but 
there was already a type conversation outside the MIN_EXPR.  So we ended 
up with

(T1) (T2) MIN_EXPR < ... >

And we were able to prove the conversion to T2 was redundant resulting 
in just (T) MIN_EXPR < ... >


You could legitimately ask why not apply this when both arguments are 
converted.  That leads to recursion via fold-const.c which wants to 
shove the conversion back into the arms in that case.  Removing that 
code results in testsuite regressions.  I felt it was time to cut that 
thread a bit as the real goal here is to remove the shorten_* bits in 
c-common, not convert all of fold-const.c to match.pd :-)

Bootstrapped and regression tested on x86_64-linux-gnu.  OK for the trunk?


[-- Attachment #2: patch --]
[-- Type: text/plain, Size: 2721 bytes --]

	* match.pd: Add pattern to factor type conversion out of the true/false
	arms of a COND_EXPR.

	* gcc.dg/fold-cond-2.c: New test.

diff --git a/gcc/match.pd b/gcc/match.pd
index abd7851..bf4da61 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1182,3 +1182,41 @@ along with GCC; see the file COPYING3.  If not see
 	(convert (bit_and (op (convert:utype @0) (convert:utype @1))
 			  (convert:utype @4)))))))
 
+/* fold-const has a rich set of optimizations for expressions of the
+   form A op B ? A : B.   However, those optimizations can be easily
+   confused by typecasting, particularly in the true/false arms of the
+   conditional.
+
+   These patterns recognize cases where the typecasting can be moved
+   from the true/false arms to the final result.  This in turn allows
+   fold-const to do a better job.
+
+   Note there is no canonical ordering for the arms of the COND_EXPR,
+   so we have to match both variants. 
+
+   Handling a convert in each arm runs afoul of COND_EXPR folding in
+   fold-const.c which shoves the conversion back into each arm resulting
+   in infinite recursion.  */
+(simplify
+  (cond @0 (convert @1) INTEGER_CST@2)
+  (if (INTEGRAL_TYPE_P (TREE_TYPE (@1))
+       && COMPARISON_CLASS_P (@0)
+       && int_fits_type_p (@2, TREE_TYPE (@1))
+       && ((operand_equal_p (TREE_OPERAND (@0, 0), @2, 0)
+	    && operand_equal_p (TREE_OPERAND (@0, 1), @1, 0))
+	   || (operand_equal_p (TREE_OPERAND (@0, 0), @1, 0)
+	       && operand_equal_p (TREE_OPERAND (@0, 1), @2, 0))))
+    (with { tree itype = TREE_TYPE (@1); tree otype = TREE_TYPE (@2); }
+      (convert:otype (cond:itype @0 @1 (convert:itype @2))))))
+
+(simplify
+  (cond @0 INTEGER_CST@1 (convert @2))
+  (if (INTEGRAL_TYPE_P (TREE_TYPE (@2))
+       && COMPARISON_CLASS_P (@0)
+       && int_fits_type_p (@1, TREE_TYPE (@2))
+       && ((operand_equal_p (TREE_OPERAND (@0, 0), @2, 0)
+	    && operand_equal_p (TREE_OPERAND (@0, 1), @1, 0))
+	   || (operand_equal_p (TREE_OPERAND (@0, 0), @1, 0)
+	       && operand_equal_p (TREE_OPERAND (@0, 1), @2, 0))))
+    (with { tree itype = TREE_TYPE (@2); tree otype = TREE_TYPE (@1); }
+      (convert:otype (cond:itype @0 (convert:itype @1) @2)))))
diff --git a/gcc/testsuite/gcc.dg/fold-cond-2.c b/gcc/testsuite/gcc.dg/fold-cond-2.c
new file mode 100644
index 0000000..2039f6e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-cond-2.c
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-original" } */
+
+
+extern unsigned short mode_size[];
+int
+oof (int mode)
+{
+  return (64 < mode_size[mode] ? 64 : mode_size[mode]);
+}
+
+/* { dg-final { scan-tree-dump-times "MIN_EXPR" 1 "original" } } */
+/* { dg-final { cleanup-tree-dump "original" } } */
+

Re: [RFA] Factor conversion out of COND_EXPR using match.pd pattern

[Bernhard Reutner-Fischer]

On May 30, 2015 6:22:59 AM GMT+02:00, Jeff Law <law@redhat.com> wrote:

+/* { dg-final { cleanup-tree-dump "original" } } */

Please drop this cleanup dg-final, trunk now does this automatically.

Thanks,

Re: [RFA] Factor conversion out of COND_EXPR using match.pd pattern

[Jeff Law]

On 05/30/2015 02:33 AM, Bernhard Reutner-Fischer wrote:
> On May 30, 2015 6:22:59 AM GMT+02:00, Jeff Law <law@redhat.com> wrote:
>
> +/* { dg-final { cleanup-tree-dump "original" } } */
>
> Please drop this cleanup dg-final, trunk now does this automatically.
Yea, figured that'd need to be fixed up after your cleanups.

Thanks,
jeff

Re: [RFA] Factor conversion out of COND_EXPR using match.pd pattern

[Marc Glisse]

(only commenting on the technique, not on the transformation itself)

>+(simplify
>+  (cond @0 (convert @1) INTEGER_CST@2)
>+  (if (INTEGRAL_TYPE_P (TREE_TYPE (@1))
>+       && COMPARISON_CLASS_P (@0)

If you add COMPARISON_CLASS_P to define_predicates, you could write:
(cond COMPARISON_CLASS_P@0 (convert @1) INTEGER_CST@2)
or maybe use a for loop on comparisons, which would give names to 
TREE_OPERAND (@0, *). This should even handle the operand_equal_p 
alternative:

(cond (cmp:c@0 @1 @2) (convert @1) INTEGER_CST@2)

>+       && int_fits_type_p (@2, TREE_TYPE (@1))
>+       && ((operand_equal_p (TREE_OPERAND (@0, 0), @2, 0)
>+           && operand_equal_p (TREE_OPERAND (@0, 1), @1, 0))
>+          || (operand_equal_p (TREE_OPERAND (@0, 0), @1, 0)
>+              && operand_equal_p (TREE_OPERAND (@0, 1), @2, 0))))
>+    (with { tree itype = TREE_TYPE (@1); tree otype = TREE_TYPE (@2); }
>+      (convert:otype (cond:itype @0 @1 (convert:itype @2))))))

This should be enough, no need to specify the outer type
(convert (cond:itype @0 @1 (convert:itype @2))))))

I believe we should not have to write cond:itype here, cond should be made 
to use the type of its second argument instead of the first one, by 
default (expr::gen_transform already has a few special cases).

-- 
Marc Glisse

Re: [RFA] Factor conversion out of COND_EXPR using match.pd pattern

[Richard Biener]

On Sat, May 30, 2015 at 11:11 AM, Marc Glisse <marc.glisse@inria.fr> wrote:
> (only commenting on the technique, not on the transformation itself)
>
>> +(simplify
>> +  (cond @0 (convert @1) INTEGER_CST@2)
>> +  (if (INTEGRAL_TYPE_P (TREE_TYPE (@1))
>> +       && COMPARISON_CLASS_P (@0)
>
>
> If you add COMPARISON_CLASS_P to define_predicates, you could write:
> (cond COMPARISON_CLASS_P@0 (convert @1) INTEGER_CST@2)

But that would fail to match on GIMPLE, so I don't like either variant
as Jeffs relies on the awkward fact that on GIMPLE cond expr conditions
are GENERIC and yours wouldn't work.

That said - for this kind of patterns testcases that exercise the patterns
on GIMPLE would be very appreciated.

> or maybe use a for loop on comparisons, which would give names to
> TREE_OPERAND (@0, *). This should even handle the operand_equal_p
> alternative:
>
> (cond (cmp:c@0 @1 @2) (convert @1) INTEGER_CST@2)

Yes, that would be my reference.

>> +       && int_fits_type_p (@2, TREE_TYPE (@1))
>> +       && ((operand_equal_p (TREE_OPERAND (@0, 0), @2, 0)
>> +           && operand_equal_p (TREE_OPERAND (@0, 1), @1, 0))
>> +          || (operand_equal_p (TREE_OPERAND (@0, 0), @1, 0)
>> +              && operand_equal_p (TREE_OPERAND (@0, 1), @2, 0))))
>> +    (with { tree itype = TREE_TYPE (@1); tree otype = TREE_TYPE (@2); }
>> +      (convert:otype (cond:itype @0 @1 (convert:itype @2))))))
>
>
> This should be enough, no need to specify the outer type
> (convert (cond:itype @0 @1 (convert:itype @2))))))

Yes.

> I believe we should not have to write cond:itype here, cond should be made
> to use the type of its second argument instead of the first one, by default
> (expr::gen_transform already has a few special cases).

Indeed.  Patch welcome (I'd have expected it already works...)

Richard.

> --
> Marc Glisse

Re: [RFA] Factor conversion out of COND_EXPR using match.pd pattern

[Jeff Law]

On 06/01/2015 04:55 AM, Richard Biener wrote:
> On Sat, May 30, 2015 at 11:11 AM, Marc Glisse <marc.glisse@inria.fr> wrote:
>> (only commenting on the technique, not on the transformation itself)
>>
>>> +(simplify
>>> +  (cond @0 (convert @1) INTEGER_CST@2)
>>> +  (if (INTEGRAL_TYPE_P (TREE_TYPE (@1))
>>> +       && COMPARISON_CLASS_P (@0)
>>
>>
>> If you add COMPARISON_CLASS_P to define_predicates, you could write:
>> (cond COMPARISON_CLASS_P@0 (convert @1) INTEGER_CST@2)
>
> But that would fail to match on GIMPLE, so I don't like either variant
> as Jeffs relies on the awkward fact that on GIMPLE cond expr conditions
> are GENERIC and yours wouldn't work.
>
> That said - for this kind of patterns testcases that exercise the patterns
> on GIMPLE would be very appreciated.
OK.  I'll see if I can build a testcase to exercise this in gimple.  If 
that's not possible would you prefer the pattern be restricted to 
generic just to be safe?

>
>> or maybe use a for loop on comparisons, which would give names to
>> TREE_OPERAND (@0, *). This should even handle the operand_equal_p
>> alternative:
>>
>> (cond (cmp:c@0 @1 @2) (convert @1) INTEGER_CST@2)
>
> Yes, that would be my reference.
OK.  easily done.

>
>>> +       && int_fits_type_p (@2, TREE_TYPE (@1))
>>> +       && ((operand_equal_p (TREE_OPERAND (@0, 0), @2, 0)
>>> +           && operand_equal_p (TREE_OPERAND (@0, 1), @1, 0))
>>> +          || (operand_equal_p (TREE_OPERAND (@0, 0), @1, 0)
>>> +              && operand_equal_p (TREE_OPERAND (@0, 1), @2, 0))))
>>> +    (with { tree itype = TREE_TYPE (@1); tree otype = TREE_TYPE (@2); }
>>> +      (convert:otype (cond:itype @0 @1 (convert:itype @2))))))
>>
>>
>> This should be enough, no need to specify the outer type
>> (convert (cond:itype @0 @1 (convert:itype @2))))))
>
> Yes.
>
>> I believe we should not have to write cond:itype here, cond should be made
>> to use the type of its second argument instead of the first one, by default
>> (expr::gen_transform already has a few special cases).
>
> Indeed.  Patch welcome (I'd have expected it already works...)
One of them is needed, but I can't recall which :-)  I'll pull them to 
generate the failure I'd run into and simplify appropriately and explain 
whichever is remaining.

jeff

Re: [RFA] Factor conversion out of COND_EXPR using match.pd pattern

[Jeff Law]

On 06/01/2015 04:55 AM, Richard Biener wrote:
> On Sat, May 30, 2015 at 11:11 AM, Marc Glisse <marc.glisse@inria.fr> wrote:
>> (only commenting on the technique, not on the transformation itself)
>>
>>> +(simplify
>>> +  (cond @0 (convert @1) INTEGER_CST@2)
>>> +  (if (INTEGRAL_TYPE_P (TREE_TYPE (@1))
>>> +       && COMPARISON_CLASS_P (@0)
>>
>>
>> If you add COMPARISON_CLASS_P to define_predicates, you could write:
>> (cond COMPARISON_CLASS_P@0 (convert @1) INTEGER_CST@2)
>
> But that would fail to match on GIMPLE, so I don't like either variant
> as Jeffs relies on the awkward fact that on GIMPLE cond expr conditions
> are GENERIC and yours wouldn't work.
>
> That said - for this kind of patterns testcases that exercise the patterns
> on GIMPLE would be very appreciated.
It may be the case that these patterns don't make a lot of sense on 
gimple and should be restricted to generic, at least with our current 
infrastructure.

The problem is when we lower from generic to gimple, we end up with 
branchy code, not straight line code and there's no good way I see to 
write a match.pd pattern which encompasses flow control.

So to discover the MIN/MAX with typecast, we're probably stuck hacking 
minmax_replacement to know when it can ignore the typecast.

That may in fact be a good thing -- I haven't looked closely yet, but 
45397 may be of a similar nature (no good chance to see straight line 
code for match.pd, thus we're forced to handle it in phiopt).


So do we want to restrict the new pattern on GENERIC, then rely on 
phiopt to get smarter and catch this stuff for GIMPLE?  Or drop the 
pattern totally and do everything in phiopt on GIMPLE?



>
>> or maybe use a for loop on comparisons, which would give names to
>> TREE_OPERAND (@0, *). This should even handle the operand_equal_p
>> alternative:
>>
>> (cond (cmp:c@0 @1 @2) (convert @1) INTEGER_CST@2)
>
> Yes, that would be my reference.
But won't this require pointer equivalence?  Are INTEGER_CST nodes fully 
shared?  What if @1 is something more complex than a _DECL node 
(remember, we're working with GENERIC).  So something like
(cond (cmp:c@0 @1 @2) (convert @3) INTEGER_CST@4))

And using operand_equal_p seems more appropriate to me (and is still 
better than the original (cond @0 ...) and grubbing around inside @0 to 
look at operands.


>
>>> +       && int_fits_type_p (@2, TREE_TYPE (@1))
>>> +       && ((operand_equal_p (TREE_OPERAND (@0, 0), @2, 0)
>>> +           && operand_equal_p (TREE_OPERAND (@0, 1), @1, 0))
>>> +          || (operand_equal_p (TREE_OPERAND (@0, 0), @1, 0)
>>> +              && operand_equal_p (TREE_OPERAND (@0, 1), @2, 0))))
>>> +    (with { tree itype = TREE_TYPE (@1); tree otype = TREE_TYPE (@2); }
>>> +      (convert:otype (cond:itype @0 @1 (convert:itype @2))))))
>>
>>
>> This should be enough, no need to specify the outer type
>> (convert (cond:itype @0 @1 (convert:itype @2))))))
>
> Yes.
>
>> I believe we should not have to write cond:itype here, cond should be made
>> to use the type of its second argument instead of the first one, by default
>> (expr::gen_transform already has a few special cases).
>
> Indeed.  Patch welcome (I'd have expected it already works...)
With Marc's fix, those explicit types are no longer needed.

Jeff

Re: [RFA] Factor conversion out of COND_EXPR using match.pd pattern

[Marc Glisse]

On Mon, 29 Jun 2015, Jeff Law wrote:

>> That said - for this kind of patterns testcases that exercise the patterns
>> on GIMPLE would be very appreciated.
> It may be the case that these patterns don't make a lot of sense on gimple 
> and should be restricted to generic, at least with our current 
> infrastructure.
>
> The problem is when we lower from generic to gimple, we end up with branchy 
> code, not straight line code and there's no good way I see to write a 
> match.pd pattern which encompasses flow control.

Andrew was working on a way to generate phiopt code automatically from 
match.pd patterns involving cond_expr, I don't know what the status is.

>>> or maybe use a for loop on comparisons, which would give names to
>>> TREE_OPERAND (@0, *). This should even handle the operand_equal_p
>>> alternative:
>>> 
>>> (cond (cmp:c@0 @1 @2) (convert @1) INTEGER_CST@2)

Hmm, looks like I wrote INTEGER_CST before the second occurence of @2 
instead of the first, so it is probably ignored :-(

>> Yes, that would be my reference.
> But won't this require pointer equivalence?  Are INTEGER_CST nodes fully 
> shared?  What if @1 is something more complex than a _DECL node (remember, 
> we're working with GENERIC).  So something like
> (cond (cmp:c@0 @1 @2) (convert @3) INTEGER_CST@4))
>
> And using operand_equal_p seems more appropriate to me (and is still better 
> than the original (cond @0 ...) and grubbing around inside @0 to look at 
> operands.

I don't understand this comment. When you write @1 twice, genmatch emits a 
call to operand_equal_p to check that they are "the same".

-- 
Marc Glisse

Re: [RFA] Factor conversion out of COND_EXPR using match.pd pattern

[Andrew Pinski]

On Mon, Jun 29, 2015 at 3:12 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Mon, 29 Jun 2015, Jeff Law wrote:
>
>>> That said - for this kind of patterns testcases that exercise the
>>> patterns
>>> on GIMPLE would be very appreciated.
>>
>> It may be the case that these patterns don't make a lot of sense on gimple
>> and should be restricted to generic, at least with our current
>> infrastructure.
>>
>> The problem is when we lower from generic to gimple, we end up with
>> branchy code, not straight line code and there's no good way I see to write
>> a match.pd pattern which encompasses flow control.
>
>
> Andrew was working on a way to generate phiopt code automatically from
> match.pd patterns involving cond_expr, I don't know what the status is.


I stopped due to many different things.  One was match.pd was too
immature for conditional expressions.  The other reason was because I
had other things to do internally.  I might pick up but it won't be
for another three months.

Thanks,
Andrew

>
>>>> or maybe use a for loop on comparisons, which would give names to
>>>> TREE_OPERAND (@0, *). This should even handle the operand_equal_p
>>>> alternative:
>>>>
>>>> (cond (cmp:c@0 @1 @2) (convert @1) INTEGER_CST@2)
>
>
> Hmm, looks like I wrote INTEGER_CST before the second occurence of @2
> instead of the first, so it is probably ignored :-(
>
>>> Yes, that would be my reference.
>>
>> But won't this require pointer equivalence?  Are INTEGER_CST nodes fully
>> shared?  What if @1 is something more complex than a _DECL node (remember,
>> we're working with GENERIC).  So something like
>> (cond (cmp:c@0 @1 @2) (convert @3) INTEGER_CST@4))
>>
>> And using operand_equal_p seems more appropriate to me (and is still
>> better than the original (cond @0 ...) and grubbing around inside @0 to look
>> at operands.
>
>
> I don't understand this comment. When you write @1 twice, genmatch emits a
> call to operand_equal_p to check that they are "the same".
>
> --
> Marc Glisse

Re: [RFA] Factor conversion out of COND_EXPR using match.pd pattern

[Richard Biener]

On Mon, Jun 29, 2015 at 7:51 PM, Jeff Law <law@redhat.com> wrote:
> On 06/01/2015 04:55 AM, Richard Biener wrote:
>>
>> On Sat, May 30, 2015 at 11:11 AM, Marc Glisse <marc.glisse@inria.fr>
>> wrote:
>>>
>>> (only commenting on the technique, not on the transformation itself)
>>>
>>>> +(simplify
>>>> +  (cond @0 (convert @1) INTEGER_CST@2)
>>>> +  (if (INTEGRAL_TYPE_P (TREE_TYPE (@1))
>>>> +       && COMPARISON_CLASS_P (@0)
>>>
>>>
>>>
>>> If you add COMPARISON_CLASS_P to define_predicates, you could write:
>>> (cond COMPARISON_CLASS_P@0 (convert @1) INTEGER_CST@2)
>>
>>
>> But that would fail to match on GIMPLE, so I don't like either variant
>> as Jeffs relies on the awkward fact that on GIMPLE cond expr conditions
>> are GENERIC and yours wouldn't work.
>>
>> That said - for this kind of patterns testcases that exercise the patterns
>> on GIMPLE would be very appreciated.
>
> It may be the case that these patterns don't make a lot of sense on gimple
> and should be restricted to generic, at least with our current
> infrastructure.
>
> The problem is when we lower from generic to gimple, we end up with branchy
> code, not straight line code and there's no good way I see to write a
> match.pd pattern which encompasses flow control.
>
> So to discover the MIN/MAX with typecast, we're probably stuck hacking
> minmax_replacement to know when it can ignore the typecast.
>
> That may in fact be a good thing -- I haven't looked closely yet, but 45397
> may be of a similar nature (no good chance to see straight line code for
> match.pd, thus we're forced to handle it in phiopt).
>
>
> So do we want to restrict the new pattern on GENERIC, then rely on phiopt to
> get smarter and catch this stuff for GIMPLE?  Or drop the pattern totally
> and do everything in phiopt on GIMPLE?

Note that IMHO it doesn't make a lot of sense to add match.pd patterns
restricted
to GENERIC - those should simply go to / stay in fold-const.c.  For patterns
restricted to GIMPLE match.pd is still the proper place.

As for matching control flow it's actually not that difficult to get
it working at
least for toplevel COND_EXPRs.  The trick is to match on the PHI nodes
(like phiopt does), thus for

  if (cond)
...
  _3 = PHI <_4, _5>

ask the match-and-simplify machinery

  if (gimple_simplify (COND_EXPR, TREE_TYPE (_3), cond, _4, _5, ...))

which will then for example match

(simplify
 (cond (gt @0 @1) @0 @1)
 (max @0 @1))

for non-toplevel COND_EXPRs we'd need to adjust the matching code itself
to handle PHI defs.

Of course with this there are several complications arising.  One is cost
as the conditional might not go away (other code may be control dependet
on it).  One is SSA form - if you get complicated enough patterns you
might end up substituting a value into the result that is computed in a place
that does not dominate the PHI result (so you'd need to insert a PHI node
for it and figure out a value for the other edges ... which might mean such
patterns would be invalid anyway?).

So it's indeed not clear if re-writing phiopt to match.pd patterns is possible
or desirable.

>>
>>> or maybe use a for loop on comparisons, which would give names to
>>> TREE_OPERAND (@0, *). This should even handle the operand_equal_p
>>> alternative:
>>>
>>> (cond (cmp:c@0 @1 @2) (convert @1) INTEGER_CST@2)
>>
>>
>> Yes, that would be my reference.
>
> But won't this require pointer equivalence?  Are INTEGER_CST nodes fully
> shared?  What if @1 is something more complex than a _DECL node (remember,
> we're working with GENERIC).  So something like
> (cond (cmp:c@0 @1 @2) (convert @3) INTEGER_CST@4))
>
> And using operand_equal_p seems more appropriate to me (and is still better
> than the original (cond @0 ...) and grubbing around inside @0 to look at
> operands.

We do use operand_equal_p to query whether @0 and @0 are equal.

>>
>>>> +       && int_fits_type_p (@2, TREE_TYPE (@1))
>>>> +       && ((operand_equal_p (TREE_OPERAND (@0, 0), @2, 0)
>>>> +           && operand_equal_p (TREE_OPERAND (@0, 1), @1, 0))
>>>> +          || (operand_equal_p (TREE_OPERAND (@0, 0), @1, 0)
>>>> +              && operand_equal_p (TREE_OPERAND (@0, 1), @2, 0))))
>>>> +    (with { tree itype = TREE_TYPE (@1); tree otype = TREE_TYPE (@2); }
>>>> +      (convert:otype (cond:itype @0 @1 (convert:itype @2))))))
>>>
>>>
>>>
>>> This should be enough, no need to specify the outer type
>>> (convert (cond:itype @0 @1 (convert:itype @2))))))
>>
>>
>> Yes.
>>
>>> I believe we should not have to write cond:itype here, cond should be
>>> made
>>> to use the type of its second argument instead of the first one, by
>>> default
>>> (expr::gen_transform already has a few special cases).
>>
>>
>> Indeed.  Patch welcome (I'd have expected it already works...)
>
> With Marc's fix, those explicit types are no longer needed.

Good.

Richard.

> Jeff

Re: [RFA] Factor conversion out of COND_EXPR using match.pd pattern

[Jeff Law]

On 06/30/2015 01:45 AM, Richard Biener wrote:
> On Mon, Jun 29, 2015 at 7:51 PM, Jeff Law <law@redhat.com> wrote:
>>
>> So do we want to restrict the new pattern on GENERIC, then rely on
>> phiopt to get smarter and catch this stuff for GIMPLE?  Or drop the
>> pattern totally and do everything in phiopt on GIMPLE?
>
> Note that IMHO it doesn't make a lot of sense to add match.pd
> patterns restricted to GENERIC - those should simply go to / stay in
> fold-const.c.  For patterns restricted to GIMPLE match.pd is still
> the proper place.

[ snip ]
>
> So it's indeed not clear if re-writing phiopt to match.pd patterns is
> possible or desirable.
Probably the thing to do is drop this match.pd change from consideration 
and instead look into improving phi-opt.

I'll open a BZ to capture the missed optimization and include a link 
back to this discussion.


>> And using operand_equal_p seems more appropriate to me (and is
>> still better than the original (cond @0 ...) and grubbing around
>> inside @0 to look at operands.
>
> We do use operand_equal_p to query whether @0 and @0 are equal.
Ah.  I had no idea.  I assumed that for multiple @N references we'd just 
use pointer equality.  My bad.

Jeff

Re: [RFA] Factor conversion out of COND_EXPR using match.pd pattern

[Richard Biener]

On Sat, May 30, 2015 at 6:22 AM, Jeff Law <law@redhat.com> wrote:
>
> I was working on polishing some of Kai's work to eliminate shorten_compare
> and stumbled on this tiny missed optimization.
>
> Basically this change allows us to see something like this:
>
>    n = (short unsigned int) mode_size[(unsigned int) mode] * 8 <= 64 ? (int)
> ((short unsigned int) mode_size[(unsigned int) mode] * 8) : 64;
>
>
> Note the (int) cast on the true arm of the COND_EXPR.  We factor that out
> and adjust the constant (which is obviously free) into:
>
>    n = (int)((short unsigned int) mode_size[(unsigned int) mode] * 8 <= 64 ?
> ((short unsigned int) mode_size[(unsigned int) mode] * 8) : 64);
>
>
> Seems subtle, but now the existing optimizers can recognize it as:
>
> !   n = (int) MIN_EXPR <(short unsigned int) mode_size[(unsigned int) mode]
> * 8, 64>;
>
>
> In another case I saw we had the same kind of transformation occur, but
> there was already a type conversation outside the MIN_EXPR.  So we ended up
> with
>
> (T1) (T2) MIN_EXPR < ... >
>
> And we were able to prove the conversion to T2 was redundant resulting in
> just (T) MIN_EXPR < ... >
>
>
> You could legitimately ask why not apply this when both arguments are
> converted.  That leads to recursion via fold-const.c which wants to shove
> the conversion back into the arms in that case.  Removing that code results
> in testsuite regressions.  I felt it was time to cut that thread a bit as
> the real goal here is to remove the shorten_* bits in c-common, not convert
> all of fold-const.c to match.pd :-)
>
> Bootstrapped and regression tested on x86_64-linux-gnu.  OK for the trunk?
>
>
>         * match.pd: Add pattern to factor type conversion out of the
> true/false
>         arms of a COND_EXPR.
>
>         * gcc.dg/fold-cond-2.c: New test.
>
> diff --git a/gcc/match.pd b/gcc/match.pd
> index abd7851..bf4da61 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -1182,3 +1182,41 @@ along with GCC; see the file COPYING3.  If not see
>         (convert (bit_and (op (convert:utype @0) (convert:utype @1))
>                           (convert:utype @4)))))))
>
> +/* fold-const has a rich set of optimizations for expressions of the
> +   form A op B ? A : B.   However, those optimizations can be easily
> +   confused by typecasting, particularly in the true/false arms of the
> +   conditional.
> +
> +   These patterns recognize cases where the typecasting can be moved
> +   from the true/false arms to the final result.  This in turn allows
> +   fold-const to do a better job.
> +
> +   Note there is no canonical ordering for the arms of the COND_EXPR,
> +   so we have to match both variants.
> +
> +   Handling a convert in each arm runs afoul of COND_EXPR folding in
> +   fold-const.c which shoves the conversion back into each arm resulting
> +   in infinite recursion.  */
> +(simplify
> +  (cond @0 (convert @1) INTEGER_CST@2)
> +  (if (INTEGRAL_TYPE_P (TREE_TYPE (@1))
> +       && COMPARISON_CLASS_P (@0)
> +       && int_fits_type_p (@2, TREE_TYPE (@1))
> +       && ((operand_equal_p (TREE_OPERAND (@0, 0), @2, 0)
> +           && operand_equal_p (TREE_OPERAND (@0, 1), @1, 0))
> +          || (operand_equal_p (TREE_OPERAND (@0, 0), @1, 0)
> +              && operand_equal_p (TREE_OPERAND (@0, 1), @2, 0))))
> +    (with { tree itype = TREE_TYPE (@1); tree otype = TREE_TYPE (@2); }
> +      (convert:otype (cond:itype @0 @1 (convert:itype @2))))))
> +
> +(simplify
> +  (cond @0 INTEGER_CST@1 (convert @2))
> +  (if (INTEGRAL_TYPE_P (TREE_TYPE (@2))
> +       && COMPARISON_CLASS_P (@0)
> +       && int_fits_type_p (@1, TREE_TYPE (@2))
> +       && ((operand_equal_p (TREE_OPERAND (@0, 0), @2, 0)
> +           && operand_equal_p (TREE_OPERAND (@0, 1), @1, 0))
> +          || (operand_equal_p (TREE_OPERAND (@0, 0), @1, 0)
> +              && operand_equal_p (TREE_OPERAND (@0, 1), @2, 0))))
> +    (with { tree itype = TREE_TYPE (@2); tree otype = TREE_TYPE (@1); }
> +      (convert:otype (cond:itype @0 (convert:itype @1) @2)))))

Now this is a case where :c support on cond would make sense...  in
theory the preprocessor would also be your friend here.  Or we could
enhance the syntax to support multiple match patterns for the same
result, thus

 (simplify
   (cond @0 (convert @1) INTEGER_CST@2)
   (cond @0 INTEGER_CST@2 (convert @1))
   (if ...

though that would require some extra markup to see where the list of matches
ends.  user-defined predicates can be used for this already though

(match (widening_cond @0 @1 @2)
  (cond @0 (convert @1) INTEGER_CST@2))
(match (widening_cond @0 @1 @2)
  (cond @0 INTEGER_CST@2 (convert @1)))
(simplify
  (widening_cond @0 @1 @2)
  (if (...

but the comments from Marc still holds in that you shouldn't rely
on @0 being GENERIC - you want a GIMPLE testcase as well for this,
sth like

_Bool cond = 64 < mode_size[mode];
return cond ? 64 : mode_size[mode];

so to use an iterator for the comparison you'd end up with sth like

(match (widening_cond @0 @1 @2 @3)
  (cond (tcc_comparison @0 @1) (convert @2) INTEGER_CST@3))
(match (widening_cond @0 @1 @2 @3)
  (cond (tcc_comparison @0 @1) INTEGER_CST@3 (convert @2)))
(simplify
  (widening_cond @0 @1 @2 @3)
  (if ...

bah, the (match ...) syntax should allow for multiple matches without
needing repetition of (match (...) at least.

Richard.

> diff --git a/gcc/testsuite/gcc.dg/fold-cond-2.c
> b/gcc/testsuite/gcc.dg/fold-cond-2.c
> new file mode 100644
> index 0000000..2039f6e
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/fold-cond-2.c
> @@ -0,0 +1,14 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-original" } */
> +
> +
> +extern unsigned short mode_size[];
> +int
> +oof (int mode)
> +{
> +  return (64 < mode_size[mode] ? 64 : mode_size[mode]);
> +}
> +
> +/* { dg-final { scan-tree-dump-times "MIN_EXPR" 1 "original" } } */
> +/* { dg-final { cleanup-tree-dump "original" } } */
> +
>

Re: [RFA] Factor conversion out of COND_EXPR using match.pd pattern

[Jeff Law]

On 06/01/2015 05:07 AM, Richard Biener wrote:
>> +(simplify
>> +  (cond @0 (convert @1) INTEGER_CST@2)
>> +  (if (INTEGRAL_TYPE_P (TREE_TYPE (@1))
>> +       && COMPARISON_CLASS_P (@0)
>> +       && int_fits_type_p (@2, TREE_TYPE (@1))
>> +       && ((operand_equal_p (TREE_OPERAND (@0, 0), @2, 0)
>> +           && operand_equal_p (TREE_OPERAND (@0, 1), @1, 0))
>> +          || (operand_equal_p (TREE_OPERAND (@0, 0), @1, 0)
>> +              && operand_equal_p (TREE_OPERAND (@0, 1), @2, 0))))
>> +    (with { tree itype = TREE_TYPE (@1); tree otype = TREE_TYPE (@2); }
>> +      (convert:otype (cond:itype @0 @1 (convert:itype @2))))))
>> +
>> +(simplify
>> +  (cond @0 INTEGER_CST@1 (convert @2))
>> +  (if (INTEGRAL_TYPE_P (TREE_TYPE (@2))
>> +       && COMPARISON_CLASS_P (@0)
>> +       && int_fits_type_p (@1, TREE_TYPE (@2))
>> +       && ((operand_equal_p (TREE_OPERAND (@0, 0), @2, 0)
>> +           && operand_equal_p (TREE_OPERAND (@0, 1), @1, 0))
>> +          || (operand_equal_p (TREE_OPERAND (@0, 0), @1, 0)
>> +              && operand_equal_p (TREE_OPERAND (@0, 1), @2, 0))))
>> +    (with { tree itype = TREE_TYPE (@2); tree otype = TREE_TYPE (@1); }
>> +      (convert:otype (cond:itype @0 (convert:itype @1) @2)))))
>
> Now this is a case where :c support on cond would make sense...
Yea.  The trick would be describing which operands can commute since 
COND_EXPR has 3 operands.  I guess we could just define it in the 
obvious way for COND_EXPR and special case it wherever we need.




  in
> theory the preprocessor would also be your friend here.  Or we could
> enhance the syntax to support multiple match patterns for the same
> result, thus
>
>   (simplify
>     (cond @0 (convert @1) INTEGER_CST@2)
>     (cond @0 INTEGER_CST@2 (convert @1))
>     (if ...
>
> though that would require some extra markup to see where the list of matches
> ends.  user-defined predicates can be used for this already though
>
> (match (widening_cond @0 @1 @2)
>    (cond @0 (convert @1) INTEGER_CST@2))
> (match (widening_cond @0 @1 @2)
>    (cond @0 INTEGER_CST@2 (convert @1)))
> (simplify
>    (widening_cond @0 @1 @2)
>    (if (...
If you'd prefer this syntax, I'm happy to switch to it and simplify 
later if we gain :c support on the COND_EXPR.

>
> but the comments from Marc still holds in that you shouldn't rely
> on @0 being GENERIC - you want a GIMPLE testcase as well for this,
> sth like
>
> _Bool cond = 64 < mode_size[mode];
> return cond ? 64 : mode_size[mode];
Yea, I'll poke at that to generate some gimple tests.


Not sure if I'll get another iteration out before heading on PTO or not.

Thanks for the feedback,


Jeff

Re: [RFA] Factor conversion out of COND_EXPR using match.pd pattern

[Richard Biener]

On Tue, Jun 2, 2015 at 7:33 PM, Jeff Law <law@redhat.com> wrote:
> On 06/01/2015 05:07 AM, Richard Biener wrote:
>>>
>>> +(simplify
>>> +  (cond @0 (convert @1) INTEGER_CST@2)
>>> +  (if (INTEGRAL_TYPE_P (TREE_TYPE (@1))
>>> +       && COMPARISON_CLASS_P (@0)
>>> +       && int_fits_type_p (@2, TREE_TYPE (@1))
>>> +       && ((operand_equal_p (TREE_OPERAND (@0, 0), @2, 0)
>>> +           && operand_equal_p (TREE_OPERAND (@0, 1), @1, 0))
>>> +          || (operand_equal_p (TREE_OPERAND (@0, 0), @1, 0)
>>> +              && operand_equal_p (TREE_OPERAND (@0, 1), @2, 0))))
>>> +    (with { tree itype = TREE_TYPE (@1); tree otype = TREE_TYPE (@2); }
>>> +      (convert:otype (cond:itype @0 @1 (convert:itype @2))))))
>>> +
>>> +(simplify
>>> +  (cond @0 INTEGER_CST@1 (convert @2))
>>> +  (if (INTEGRAL_TYPE_P (TREE_TYPE (@2))
>>> +       && COMPARISON_CLASS_P (@0)
>>> +       && int_fits_type_p (@1, TREE_TYPE (@2))
>>> +       && ((operand_equal_p (TREE_OPERAND (@0, 0), @2, 0)
>>> +           && operand_equal_p (TREE_OPERAND (@0, 1), @1, 0))
>>> +          || (operand_equal_p (TREE_OPERAND (@0, 0), @1, 0)
>>> +              && operand_equal_p (TREE_OPERAND (@0, 1), @2, 0))))
>>> +    (with { tree itype = TREE_TYPE (@2); tree otype = TREE_TYPE (@1); }
>>> +      (convert:otype (cond:itype @0 (convert:itype @1) @2)))))
>>
>>
>> Now this is a case where :c support on cond would make sense...
>
> Yea.  The trick would be describing which operands can commute since
> COND_EXPR has 3 operands.  I guess we could just define it in the obvious
> way for COND_EXPR and special case it wherever we need.
>
>
>
>
>  in
>>
>> theory the preprocessor would also be your friend here.  Or we could
>> enhance the syntax to support multiple match patterns for the same
>> result, thus
>>
>>   (simplify
>>     (cond @0 (convert @1) INTEGER_CST@2)
>>     (cond @0 INTEGER_CST@2 (convert @1))
>>     (if ...
>>
>> though that would require some extra markup to see where the list of
>> matches
>> ends.  user-defined predicates can be used for this already though
>>
>> (match (widening_cond @0 @1 @2)
>>    (cond @0 (convert @1) INTEGER_CST@2))
>> (match (widening_cond @0 @1 @2)
>>    (cond @0 INTEGER_CST@2 (convert @1)))
>> (simplify
>>    (widening_cond @0 @1 @2)
>>    (if (...
>
> If you'd prefer this syntax, I'm happy to switch to it and simplify later if
> we gain :c support on the COND_EXPR.

Yes, I'd prefer the above.

I'll note down the syntax improvements and hope to get to them during
stage1.

Thanks,
Richard.

>>
>> but the comments from Marc still holds in that you shouldn't rely
>> on @0 being GENERIC - you want a GIMPLE testcase as well for this,
>> sth like
>>
>> _Bool cond = 64 < mode_size[mode];
>> return cond ? 64 : mode_size[mode];
>
> Yea, I'll poke at that to generate some gimple tests.
>
>
> Not sure if I'll get another iteration out before heading on PTO or not.
>
> Thanks for the feedback,
>
>
> Jeff