[RTL] Canonicalize commutative operations more

Hello,

as explained in the PR, the goal of this patch is to have a more canonical 
form for RTL expressions, so it is easier to model them with a small 
number of patterns.

This patch passes bootstrap+testsuite on x86_64-linux-gnu. Using the 
opposite arbitrary order in compare_commutative_operands_precedence 
(exchange x and y in the line with GET_CODE) passes as well. The 
simplify-rtx bit is because I get an infinite recursion otherwise. 
Surprisingly, that infinite recursion occurs only in var-tracking, and 
only for a single file in bootstrap+testsuite (not the same one depending 
on the arbitrary order). I am not sure that is the best place to break the 
recursion, but it seems to work.

I don't really expect the patch to be accepted as is, but it seems good 
enough to start the conversation.

2013-03-19  Marc Glisse  <marc.glisse@inria.fr>

 	PR rtl-optimization/55611
 	* rtl.h (commutative_operand_precedence): Remove.
 	(compare_commutative_operands_precedence): Declare.
 	* optabs.c (swap_commutative_operands_with_target): Use
 	compare_commutative_operands_precedence.
 	* simplify-rtx.c (simplify_associative_operation): Break the
 	recursion cycle.
 	(simplify_plus_minus_op_data_cmp): Use
 	compare_commutative_operands_precedence.
 	* rtlanal.c (commutative_operand_precedence): Make static.
 	(compare_commutative_operands_precedence): New function.
 	(swap_commutative_operands_p): Use it.

> This patch passes bootstrap+testsuite on x86_64-linux-gnu. Using the
> opposite arbitrary order in compare_commutative_operands_precedence
> (exchange x and y in the line with GET_CODE) passes as well. The
> simplify-rtx bit is because I get an infinite recursion otherwise.
> Surprisingly, that infinite recursion occurs only in var-tracking, and
> only for a single file in bootstrap+testsuite (not the same one depending
> on the arbitrary order). I am not sure that is the best place to break the
> recursion, but it seems to work.
> 
> I don't really expect the patch to be accepted as is, but it seems good
> enough to start the conversation.

I'm rather with Jakub here, I think that arbitrary canonicalization as the one 
proposed here will probably be worse than no canonicalization in practice, 
because it will generate much shuffling.  If you need more canonicalization, 
then why not propose new, precise canonicalization rules?

On Wed, 27 Mar 2013, Eric Botcazou wrote:

>> This patch passes bootstrap+testsuite on x86_64-linux-gnu. Using the
>> opposite arbitrary order in compare_commutative_operands_precedence
>> (exchange x and y in the line with GET_CODE) passes as well. The
>> simplify-rtx bit is because I get an infinite recursion otherwise.
>> Surprisingly, that infinite recursion occurs only in var-tracking, and
>> only for a single file in bootstrap+testsuite (not the same one depending
>> on the arbitrary order). I am not sure that is the best place to break the
>> recursion, but it seems to work.
>>
>> I don't really expect the patch to be accepted as is, but it seems good
>> enough to start the conversation.
>
> I'm rather with Jakub here, I think that arbitrary canonicalization as the one
> proposed here will probably be worse than no canonicalization in practice,
> because it will generate much shuffling.  If you need more canonicalization,
> then why not propose new, precise canonicalization rules?

Well, the goal was to have arbitrary canonicalization for all cases where 
precise rules are not already provided. In (a<<8)|(b>>24), there is no 
obvious reason why lshift should have higher or lower priority than 
rshift, but we don't want to have to write patterns with both orders in 
the target .md files. In v[0]+v[1] (v is a V2DF), it is likewise 
preferable if we know in which order the operands will appear, but I don't 
care what that order is (note that ordering this one requires a refinement 
that I didn't include in this first version of the patch). And this way we 
don't have to refine the order all the time, we just check what order this 
arbitrary rule generates and write the pattern accordingly.

I am not sure about adding just a few rules. If I just say that lshift is 
stronger than rshift, the relation is not an order (transitive) anymore. 
And it might already have some of the drawbacks you and Jakub fear (I 
don't have a good understanding of those, I may be wrong).

If there is a nice way to instead try permutations (note that for a 
pattern involving k commutative operations, there are 2^k versions), I am 
just as happy with that.

By the way, even if we don't take the canonicalization (just ignore the 
line comparing GET_CODEs), do we still want the refactoring that this 
patch brings, or is the current interface better?

> Well, the goal was to have arbitrary canonicalization for all cases where
> precise rules are not already provided. In (a<<8)|(b>>24), there is no
> obvious reason why lshift should have higher or lower priority than
> rshift, but we don't want to have to write patterns with both orders in
> the target .md files. In v[0]+v[1] (v is a V2DF), it is likewise
> preferable if we know in which order the operands will appear, but I don't
> care what that order is (note that ordering this one requires a refinement
> that I didn't include in this first version of the patch). And this way we
> don't have to refine the order all the time, we just check what order this
> arbitrary rule generates and write the pattern accordingly.

The question is: do we really need to canonicalize everything?  The more you 
canonicalize, the more internal shuffling you will get in the middle-end for a 
practical benefit that might be elusive in most cases.

> I am not sure about adding just a few rules. If I just say that lshift is
> stronger than rshift, the relation is not an order (transitive) anymore.

Why?  Can't you give them precedences in commutative_operand_precedence that 
preserve the transitivity?

> And it might already have some of the drawbacks you and Jakub fear (I
> don't have a good understanding of those, I may be wrong).

The fear (at least mine) is that, by canonicalizing everything, you will make 
changes behind the back of back-ends that could disable some of their patterns 
silently.  This is also a concern for new canonicalization rules, but at least 
you can reasonably audit the back-ends for every new rule.

> If there is a nice way to instead try permutations (note that for a
> pattern involving k commutative operations, there are 2^k versions), I am
> just as happy with that.

No, of course, canonicalization is desirable.

> By the way, even if we don't take the canonicalization (just ignore the
> line comparing GET_CODEs), do we still want the refactoring that this
> patch brings, or is the current interface better?

I think that the current interface makes it clear that you need to tweak the 
precedence in order to change the canonicalization (thus preserving the 
transitivity).  Btw, there is something to fix in the head comment of 
commutative_operand_precedence because I cannot make sense of it.

On Tue, 2 Apr 2013, Eric Botcazou wrote:

>> I am not sure about adding just a few rules. If I just say that lshift is
>> stronger than rshift, the relation is not an order (transitive) anymore.
>
> Why?  Can't you give them precedences in commutative_operand_precedence that
> preserve the transitivity?

I can, but then I am giving lshift higher priority than every other 
operation, not just rshift. And if I want to give (vec_select x 0) a 
higher precedence than (vec_select x 1) but lower than (vec_select 
(vec_concat a b) 1), the weights may become complicated, whereas the 
comparison function could just recurse. But I understand that it has 
advantages over an arbitrary order, so if I ever feel the need again I 
will try to play with precedence values.

I might also experiment with the new transformation feature of .md files 
to write a pattern once and have it expand to 2 patterns for the 2 orders.

> The fear (at least mine) is that, by canonicalizing everything, you will 
> make changes behind the back of back-ends that could disable some of 
> their patterns silently.

I wonder if those issues might in most cases be bugs in the back-ends 
(optimizations missed depending on the order), that the canonicalization 
would make more noticable (and thus easier to fix).

> I can, but then I am giving lshift higher priority than every other
> operation, not just rshift. And if I want to give (vec_select x 0) a
> higher precedence than (vec_select x 1) but lower than (vec_select
> (vec_concat a b) 1), the weights may become complicated, whereas the
> comparison function could just recurse.

You cannot have both transitivity and fast-tracks in the comparison function.
However it isn't clear (at least to me) if transitivity is really required.

(vec_select x 0) and (vec_select x 1) are the same pattern so they shouldn't 
be distinguished here.

> I wonder if those issues might in most cases be bugs in the back-ends
> (optimizations missed depending on the order), that the canonicalization
> would make more noticable (and thus easier to fix).

There are certainly such issues in the back-ends (and even ??? comments about 
it) so sensible canonicalization is desirable.

On 04/02/2013 04:54 AM, Eric Botcazou wrote:
>> I wonder if those issues might in most cases be bugs in the back-ends
>> (optimizations missed depending on the order), that the canonicalization
>> would make more noticable (and thus easier to fix).
>
> There are certainly such issues in the back-ends (and even ??? comments about
> it) so sensible canonicalization is desirable.
Right.  The choice between canonicalization and code bloat to support 
multiple RTL forms computing the same value is a never-ending problem. 
Where it's clearly made sense we have canonicalized, where it doesn't, 
we haven't.  There's a huge no-mans land in the middle.

Jeff

On Apr 2, 2013, at 1:55 AM, Eric Botcazou <ebotcazou@adacore.com> wrote:
> The question is: do we really need to canonicalize everything?

> The fear (at least mine) is that, by canonicalizing everything, you will make 
> changes behind the back of back-ends that could disable some of their patterns 
> silently.

My take, yes, we really need to.  My take, during construction, the canonicalization code should kick in and build it canonically.  If you had a total ordering predicate, and defined an ordering for any two rtls, then the builder could use it and then there would be no case in which things are not canonicalized.  If one tries to do this after the fact, we'll, let's just say, no good come from that.