[Bug rtl-optimization/55611] New: Operand swapping for commutative operators

[Bug rtl-optimization/55611] New: Operand swapping for commutative operators

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55611

             Bug #: 55611
           Summary: Operand swapping for commutative operators
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: rtl-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: glisse@gcc.gnu.org


Hello,

this PR is here to remember this discussion on IRC. It started because I
noticed that a patch I wrote for bug 55583 failed when the operands of | were
not given in the right order, but is a more general question about how to avoid
a combinatorial explosion of the number of patterns involving commutative
operators. Two promising directions: put a stronger priority order on rtx
(canonicalize more), or when priorities are the same and one order doesn't
match, try the other one.

<MarcG> Hello. It seems that in RTL we don't make a very strong effort to swap
operands of commutative operators, we only swap when one is obviously more
complicated than the other.
<MarcG> For things like an OR of a left shift and a right shift, are we
supposed to have 2 patterns in .md files?
<Richi> there is always a canonical form
<Richi> but I'm not sure that such combine helping pattern is really the
correct approach
<MarcG> if I compile C code (a<<2)|(b>>30) and (b>>30)|(a<<2) I don't get the
same pattern, so it isn't canonical
<Jakub> richi: in this case I believe they have the same operand priority, so
there is no canonical order
<Richi> we could of course change that
<MarcG> I wonder whether an arbitrary order would help?
<Richi> generally not, but for avoiding pattern explosion yes
<Jakub> it can't be done in commutative_operand_precedence (rtx op)
<Jakub> because it doesn't see both operands
<Richi> but we can assign a different precedence for rshift vs lshift?
<Jakub> and there are numerous commutative_operand_precedence callers, so
changing it just in swap_commutative_operands_p might not be enough
<MarcG> can't we just assign a different number to left shift, right shift,
etc? (their enum value?)
<Jakub> marcg: I'm afraid it would penalize code unnecessarily
<Jakub> marcg: the only case you want to treat specially is if one operand is
left shift and one is right shift
<Richi> jakub: I'm not sure - why dont' we want canonical form of say a<<3 | (b
+ 1) as well?
<Jakub> marcg: if you use different priority for <<, >> and the rest of binary
operations, why would you be swapping the operands?
<MarcG> I don't really see how that would penalize code.
<MatZ> Me neither.
<Jakub> marcg: it can increase register pressure or similar (or decrease of
course), it is one further thing where it changes code from what user
originally wrote unnecessarily
<MarcG> Although it might force a lot of trivial reordering in .md files, not
sure.
<MarcG> ah, I see. So maybe find a way to only _try_ it and drop it if it
doesn't help.
<MarcG> seems more complicated already :-(
<Jakub> I think what makes more sense is that the combiner if both operands of
a commutative expression have the same precedence, if the original order
doesn't match, tries also the other order
<MatZ> jakub: That's not pessimization in my book, but shuffling with unclear
effects. The solution to that problem, if it is one, is not to generally avoid
swapping operands, but instead to improve the register allocator for instance.
<Richi> jakub: that sounds reasonable
<Richi> jakub: though in general duplicates work (maybe only if RTX_CODE of the
ops is different)
<MatZ> I think canonicalization as much as possible is better.
<Richi> we can simply have a special combine variant of the precedence
<Jakub> in any case, not a 4.8 thing, if you change canonicalization, it might
take months to catch up in various backends
<Richi> thus make combine select a more canonical variant for matching patterns
<Richi> but not change the IL
<MatZ> I bet the reason it's currently not implemented is not because somebody
conciously decided that it would shuffle too much, but rather simply because
nobody bothered until now, so it seems premature caution to worry about
potential performance effects.
<MatZ> richi: Yes, we could. We could do many thing. The question is, why
should we?
<MarcG> jakub: yes, of course not for 4.8.
<Jakub> marcg: IMHO if you want something for 4.8, just duplicate the pattern,
or write it using some macro where it will match any direction of shift on
either side and in the pattern condition test that the direction is different
<MarcG> I don't want anything for 4.8, I am only interested in long term here
:-)
<MarcG> but that may still be a good idea
<MarcG> except that there is a constraint on the left shift argument being the
same as the output that breaks symmetry and complicates things...
<MarcG> anyway, I never hit that pattern myself, it was more a general question
because I had already wondered about it for other patterns in the past.
<Jakub> or not even a code iterator, you can use match_operator which would
check for logical left/right shift
<MarcG> canonicalizing still has limits. For instance, getting a canonical
order between vec_select x y for different values of y would sometimes be
convenient, but such recursive behavior can't be done by assigning a priority
number.

[Bug rtl-optimization/55611] Operand swapping for commutative operators

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55611

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> 2012-12-11 22:12:01 UTC ---
Created attachment 28931
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=28931
Use tree code to determine the canonical order

In this patch, I remove the external calls to commutative_operand_precedence,
and I compare GET_CODEs when the current function would say the arguments are
equivalent. This passes bootstrap+testsuite except for one test:
gfortran.dg/pr43229.f90  -O  (internal compiler error)
that I killed when it was 12GB.

I also tried the reverse order (just swap x and y in the GET_CODE comparison).
It got a crazy process during stage3 compiling tree-ssa-address.c (I killed it
at 40GB). Before that, I had tried parts of the testsuite with a
non-bootstrapped compiler, and it seemed to pass just fine.

[Bug rtl-optimization/55611] Operand swapping for commutative operators

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55611

--- Comment #2 from Marc Glisse <glisse at gcc dot gnu.org> 2013-03-11 14:44:09 UTC ---
The fortran test that fails is equivalent to the following (use -Ofast -g,
surprisingly it only fails in var tracking)

float f(double*a,double*b){
  double x=a[0]*b[0];
  x+=a[1]*b[1];
  x+=a[2]*b[2];
  x+=a[3]*b[3];
  return x;
}

This happens because of an infinite loop between simplify_associative_operation
and simplify_gen_binary (and a few others) which keeps shuffling the additions
around to try and canonicalize the expression. Some well placed tests whether
GET_CODE(*)==code could probably help, although I am a bit surprised that it
fails so seldom, and only in var-tracking.

I didn't investigate the problem with the reverse order, as stage3 failures (in
middle-end code) are hard to debug...

[Bug rtl-optimization/55611] Operand swapping for commutative operators

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55611

--- Comment #3 from Marc Glisse <glisse at gcc dot gnu.org> 2013-03-11 15:14:46 UTC ---
(In reply to comment #1)
> I also tried the reverse order (just swap x and y in the GET_CODE comparison).
> It got a crazy process during stage3 compiling tree-ssa-address.c (I killed it
> at 40GB).

Seems to be the same problem, at least the call stack looks the same, with IOR
instead of PLUS.

[Bug rtl-optimization/55611] Operand swapping for commutative operators

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55611

Marc Glisse <glisse at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #28931|0                           |1
        is obsolete|                            |

--- Comment #4 from Marc Glisse <glisse at gcc dot gnu.org> 2013-03-12 13:04:28 UTC ---
Created attachment 29652
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=29652
Use tree code to determine the canonical order (2)

With this slight tweak to simplify_associative_operation it now passes
bootstrap+testsuite on x86_64-linux-gnu, both in this order and the reverse
order. I am not sure it is the best way to break the infinite recursion, but it
seems to work.

[Bug rtl-optimization/55611] Operand swapping for commutative operators

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55611

--- Comment #5 from Marc Glisse <glisse at gcc dot gnu.org> 2013-04-02 12:11:12 UTC ---
See the discussion at:

http://gcc.gnu.org/ml/gcc-patches/2013-03/msg00692.html

which continues at:

http://gcc.gnu.org/ml/gcc-patches/2013-04/msg00049.html

for why we won't do arbitrary canonicalization.

[Bug rtl-optimization/55611] Operand swapping for commutative operators

[segher at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=55611

Segher Boessenkool <segher at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |segher at gcc dot gnu.org
           Assignee|unassigned at gcc dot gnu.org      |segher at gcc dot gnu.org

--- Comment #6 from Segher Boessenkool <segher at gcc dot gnu.org> ---
Mine.