[Bug middle-end/42973] New: [4.5 regression] IRA appraently systematically making reload too busy on 2 address instructions with 3 operands

[Bug middle-end/42973] New: [4.5 regression] IRA appraently systematically making reload too busy on 2 address instructions with 3 operands

[hubicka at gcc dot gnu dot org]

Following testcase (derived from pattern appearing in internal loops of NAND
SPEC2k6 benchmark):

double a[1000];
double b[1000];
void t(void)
{
  int i;
  double carried = 0;
  double inv=a[99];
  for (i=0;i<1000;i++)
    {
        carried = inv-carried;
      double tmp = carried *carried;
      carried = a[i];
      b[i]-= tmp;
    }
}

Needs one FP move in internal loop, but with -funroll-instructions we get 16
moves for 8 unrollings:
.L2:
        movapd  %xmm0, %xmm3
        subsd   %xmm2, %xmm3
        movapd  %xmm3, %xmm15
        movsd   a(%rax), %xmm13
        mulsd   %xmm3, %xmm15
        movsd   b(%rax), %xmm14
        subsd   %xmm15, %xmm14
        movsd   %xmm14, b(%rax)
        leaq    8(%rax), %r10
        movapd  %xmm0, %xmm12
        subsd   %xmm13, %xmm12
        movapd  %xmm12, %xmm11
        movsd   a(%r10), %xmm9
        mulsd   %xmm12, %xmm11
        movsd   b(%r10), %xmm10
        subsd   %xmm11, %xmm10
        movsd   %xmm10, b(%r10)
        leaq    16(%rax), %r9
        movapd  %xmm0, %xmm8
        subsd   %xmm9, %xmm8
        movapd  %xmm8, %xmm7

the problem is instruction:
(insn 83 75 84 3 /home/jh/q.c:10 (set (reg/v:DF 109 [ carried ])
        (minus:DF (reg/v:DF 70 [ inv ])
            (reg/v:DF 104 [ carried ]))) 726 {*fop_df_1_sse}
(expr_list:REG_DEAD (reg/v:DF 104 [ carried ])
        (nil)))

This instruction always needs one move (inv is invariant and must be preserved
over loop) IRA allocate both 109 and 104 into same register.  This creates
situation where reload needs to move instructions instead of one:
(insn 156 76 84 3 /home/jh/q.c:10 (set (reg:DF 22 xmm1)
        (reg/v:DF 21 xmm0 [orig:62 inv ] [62])) 103 {*movdf_integer_rex64}
(nil))

(insn 84 156 157 3 /home/jh/q.c:10 (set (reg:DF 22 xmm1)
        (minus:DF (reg:DF 22 xmm1)
            (reg/v:DF 23 xmm2 [orig:89 carried.37 ] [89]))) 733 {*fop_df_1_sse}
(nil))

(insn 157 84 85 3 /home/jh/q.c:10 (set (reg:DF 23 xmm2 [96])
        (reg:DF 22 xmm1)) 103 {*movdf_integer_rex64} (nil))

that cause significant slowdown at NAND benchmark.

I looked why regmove does not fix the instruction into 2 address form.  It is
because:
              if (! (src_note = find_reg_note (insn, REG_DEAD, src)))
                { 
                  /* We used to force the copy here like in other cases, but
                     it produces worse code, as it eliminates no copy
                     instructions and the copy emitted will be produced by
                     reload anyway.  On patterns with multiple alternatives,
                     there may be better solution available.

                     In particular this change produced slower code for numeric
                     i387 programs.  */
continue;
                }


Following patch:
Index: regmove.c
===================================================================
--- regmove.c   (revision 156173)
+++ regmove.c   (working copy)
@@ -1037,6 +1037,11 @@ regmove_backward_pass (void)
                     In particular this change produced slower code for numeric
                     i387 programs.  */

+                 if (!copy_src)
+                   {
+                     copy_src = src;
+                     copy_dst = dst;
+                   }
                  continue;
                }

reverts the ancient change and inserts the move.  This leads to PR42961
with a workaround we get:

.L2:
        movapd  %xmm0, %xmm8
        subsd   %xmm3, %xmm8
        movsd   a(%rax), %xmm6
        mulsd   %xmm8, %xmm8
        movsd   b(%rax), %xmm7
        subsd   %xmm8, %xmm7
        movsd   %xmm7, b(%rax)
        leaq    8(%rax), %r10
        movapd  %xmm0, %xmm5
        subsd   %xmm6, %xmm5
        movsd   a(%r10), %xmm3
        mulsd   %xmm5, %xmm5
        movsd   b(%r10), %xmm4
        subsd   %xmm5, %xmm4
        movsd   %xmm4, b(%r10)
        leaq    16(%rax), %r9
        movapd  %xmm0, %xmm1
        subsd   %xmm3, %xmm1
        movsd   a(%r9), %xmm15
        mulsd   %xmm1, %xmm1
        movsd   b(%r9), %xmm2
        subsd   %xmm1, %xmm2
        movsd   %xmm2, b(%r9)
        leaq    24(%rax), %r8

i.e. problem is gone and we also get for % speedup at NAMD itself.

Martin pointed out that http://gcc.gnu.org/ml/gcc/2010-02/msg00055.html
seems related. I also see suffle copies here:
  cp0:a0(r60)<->a35(r68)@15:shuffle
  cp1:a32(r78)<->a33(r74)@15:shuffle
  cp2:a28(r84)<->a29(r77)@15:shuffle
  cp3:a24(r90)<->a25(r83)@15:shuffle
  cp4:a20(r96)<->a21(r89)@15:shuffle
  cp5:a16(r102)<->a17(r95)@15:shuffle
  cp6:a12(r108)<->a13(r101)@15:shuffle
  cp7:a8(r113)<->a9(r107)@15:shuffle

So it seems that IRA makes this pattern by design.  Can't we instead of
the regmove patch above just make IRA to record conflict in between destination
and second operand of 2 address instruction (They can't sit in same register
anyway) instead of recording the copy?

Honza


-- 
           Summary: [4.5 regression] IRA appraently systematically making
                    reload too busy on 2 address instructions with 3
                    operands
           Product: gcc
           Version: 4.5.0
            Status: UNCONFIRMED
          Keywords: missed-optimization, ra
          Severity: normal
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: hubicka at gcc dot gnu dot org
GCC target triplet: x86_64-linux


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

[Bug middle-end/42973] [4.5 regression] IRA appraently systematically making reload too busy on 2 address instructions with 3 operands

[hubicka at gcc dot gnu dot org]

------- Comment #1 from hubicka at gcc dot gnu dot org  2010-02-05 13:11 -------
-funroll-instructions is shortcut for -O2 -funroll-loops -fno-schedule-insns2
(last one is there just to make asm prettier)


-- 


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

[Bug middle-end/42973] [4.5 regression] IRA appraently systematically making reload too busy on 2 address instructions with 3 operands

[rguenth at gcc dot gnu dot org]

-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.5.0


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

[Bug middle-end/42973] [4.5 regression] IRA apparently systematically making reload too busy on 2 address instructions with 3 operands

[law at redhat dot com]

------- Comment #2 from law at redhat dot com  2010-02-05 16:20 -------
The argument for using conflicts is that the vast majority of the time if the
constraints force us to tie a specific source to the destination, then the
other source must not use the same hard reg as the destination.  There might be
oddball cases where all the operands could share the same hard reg, but I
suspect those would be extremely rare.

The argument against using conflicts is the conflict code works on liveness so
we have to process the constraints and cause certain input operands to become
live earlier than normal.  However, we already do that for earlyclobbers, so it
might not be too ugly.

Using the costing models may be marginally simpler, but I doubt they'll be
nearly as effective.  In fact, for the example in my message, using the
ira-reload code, costing models is insufficient to solve the problem because
the only available register for the untied input reg is the hard register used
by the output.  So even with a high cost, we still allocate the output and
untied input to the same hard reg triggering reload insanity.  We're actually
better off leaving the untied input unallocated.


-- 


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

[Bug middle-end/42973] [4.5 regression] IRA apparently systematically making reload too busy on 2 address instructions with 3 operands

[hubicka at ucw dot cz]

------- Comment #3 from hubicka at ucw dot cz  2010-02-06 00:51 -------
Subject: Re:  [4.5 regression] IRA apparently
        systematically making reload too busy on 2 address instructions
        with 3 operands

> The argument for using conflicts is that the vast majority of the time if the
> constraints force us to tie a specific source to the destination, then the
> other source must not use the same hard reg as the destination.  There might be
> oddball cases where all the operands could share the same hard reg, but I
> suspect those would be extremely rare.

This should happen only when all operands are already same pseudo, and at that
time there won't be conflict to add, right?

Honza


-- 


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

[Bug middle-end/42973] [4.5 regression] IRA apparently systematically making reload too busy on 2 address instructions with 3 operands

[vmakarov at redhat dot com]

------- Comment #4 from vmakarov at redhat dot com  2010-02-06 00:57 -------
I have a patch which solves the problem and analogous problem that Jeff
recently sent me.

I just need a time to do some benchmarking.  If everything is all right, I'll
submit the patch probably on Monday.


-- 


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

[Bug middle-end/42973] [4.4/4.5 regression] IRA apparently systematically making reload too busy on 2 address instructions with 3 operands

[rguenth at gcc dot gnu dot org]

------- Comment #5 from rguenth at gcc dot gnu dot org  2010-02-07 15:03 -------
Confirmed.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
      Known to fail|                            |4.4.3 4.5.0
      Known to work|                            |4.3.4
           Priority|P3                          |P2
   Last reconfirmed|0000-00-00 00:00:00         |2010-02-07 15:03:02
               date|                            |
            Summary|[4.5 regression] IRA        |[4.4/4.5 regression] IRA
                   |apparently systematically   |apparently systematically
                   |making reload too busy on 2 |making reload too busy on 2
                   |address instructions with 3 |address instructions with 3
                   |operands                    |operands


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

[Bug middle-end/42973] [4.4/4.5 regression] IRA apparently systematically making reload too busy on 2 address instructions with 3 operands

[vmakarov at redhat dot com]

------- Comment #6 from vmakarov at redhat dot com  2010-02-09 19:56 -------
  The patch which I'll send in a few minutes solves the problem.  The patch
avoids the creation of shuffle copies if an involved operand should be bound to
some other operand in the current insn.  The test code generated with the patch
looks like

.L2:
        movapd  %xmm0, %xmm8
        subsd   %xmm3, %xmm8
        movsd   a(%rax), %xmm6
        mulsd   %xmm8, %xmm8
        movsd   b(%rax), %xmm7
        subsd   %xmm8, %xmm7
        movsd   %xmm7, b(%rax)
        leaq    8(%rax), %r10
        movapd  %xmm0, %xmm5
        subsd   %xmm6, %xmm5
        movsd   a(%r10), %xmm3
        mulsd   %xmm5, %xmm5
        movsd   b(%r10), %xmm4
        subsd   %xmm5, %xmm4
        movsd   %xmm4, b(%r10)
        leaq    16(%rax), %r9
        movapd  %xmm0, %xmm1
        subsd   %xmm3, %xmm1
        movsd   a(%r9), %xmm15
        mulsd   %xmm1, %xmm1
        movsd   b(%r9), %xmm2
        subsd   %xmm1, %xmm2
        movsd   %xmm2, b(%r9)
        leaq    24(%rax), %r8


SPEC2000 benchmarking on x86/x86_64 (Core i7) shows that the patch usage
results in a bit better code.

 x86: The code is different on gzip, vpr, gcc, crafty, perlbmk, gap,
vortex, bzip2, twolf and mesa.  The patch results in always not bigger
code (in average about 0.02% smaller).  The rate is a bit better with
patch but practically the same (the biggest improvement is on crafty
and perlbmk about 1%).

  x86_64: The code is different on gzip, vpr, gcc, crafty, parser, perlbmk,
gap,
vortex, bzip2, twolf and mesa, art, ammp.  The patch results in
average about 0.01% smaller code.  The rate is a bit better with patch
but practically the same (the biggest improvement is on vortex 1.3%
and on crafty and bzip2 0.7%).


-- 


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

[Bug middle-end/42973] [4.4/4.5 regression] IRA apparently systematically making reload too busy on 2 address instructions with 3 operands

[vmakarov at gcc dot gnu dot org]

------- Comment #7 from vmakarov at gcc dot gnu dot org  2010-02-10 02:07 -------
Subject: Bug 42973

Author: vmakarov
Date: Wed Feb 10 02:07:22 2010
New Revision: 156641

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=156641
Log:
2010-02-09  Vladimir Makarov  <vmakarov@redhat.com>

        PR middle-end/42973
        * ira-conflicts.c (get_dup): Remove.
        (process_reg_shuffles): Add new parameter.  Use it as an
        additional guard for copy generation.
        (add_insn_allocno_copies): Rewrite.


Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/ira-conflicts.c


-- 


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

[Bug middle-end/42973] [4.4/4.5 regression] IRA apparently systematically making reload too busy on 2 address instructions with 3 operands

[hubicka at ucw dot cz]

------- Comment #8 from hubicka at ucw dot cz  2010-02-10 09:22 -------
Subject: Re:  [4.4/4.5 regression] IRA apparently
        systematically making reload too busy on 2 address instructions
        with 3 operands

Thanks, we should see if this solves the AMMP problem in a day or two.
Are you going to look at the related PR42961?  Without the regmove hunk
it does not happen at AMMP but it likely happens elsewhere.  I did some
work on this years back on old RA so I can play with it too.
(Simple fix would be to add ? penalizers to integer variant of FP moves,
but I would like to see some solution where RA actually can use integers
for mem->mem copies)

Honza


-- 


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

[Bug middle-end/42973] [4.4/4.5 regression] IRA apparently systematically making reload too busy on 2 address instructions with 3 operands

[steven at gcc dot gnu dot org]

------- Comment #9 from steven at gcc dot gnu dot org  2010-02-10 09:46 -------
What is the purpose of regmove these days, anyway? Isn't it all useless code
thanks to IRA?


-- 


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

[Bug middle-end/42973] [4.4/4.5 regression] IRA apparently systematically making reload too busy on 2 address instructions with 3 operands

[vmakarov at redhat dot com]

------- Comment #10 from vmakarov at redhat dot com  2010-02-10 17:02 -------
  The big chunk of regmove which did the same what IRA is capable to do was
removed when IRA was merged.

  There are still a lot of important transformations (like dealing with
increments, sign/zero extensions etc) which IRA can not do.

  As I remember I benchmarked IRA with regmove and without it on x86/x86_64
some time ago and I got a clear impression that regmove is still important.

  It would be nice to see what regmove transformations are important, try to
rewrite it or move some its functionality to IRA but unfortunately I have no
time for this.


-- 


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

[Bug middle-end/42973] [4.4/4.5 regression] IRA apparently systematically making reload too busy on 2 address instructions with 3 operands

[vmakarov at redhat dot com]

------- Comment #11 from vmakarov at redhat dot com  2010-02-10 17:15 -------

(In reply to comment #8)
> 
> Thanks, we should see if this solves the AMMP problem in a day or two.
> Are you going to look at the related PR42961?  Without the regmove hunk
> it does not happen at AMMP but it likely happens elsewhere.  I did some
> work on this years back on old RA so I can play with it too.
> (Simple fix would be to add ? penalizers to integer variant of FP moves,
> but I would like to see some solution where RA actually can use integers
> for mem->mem copies)

  I am working on IRA without usage of cover classes.  For example, IRA could
assign integer or floating point register for mem->mem copies whatever is
possible and whatever is more profitable.  This code is big and not ready yet. 
There are a lot of performance issues (besides IRA speed issues which is a
consequence of dealing with more classes).  I am trying to solve the issues. 
But if the code is ok, it probably will solve the problem.


-- 


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

[Bug middle-end/42973] [4.4/4.5 regression] IRA apparently systematically making reload too busy on 2 address instructions with 3 operands

[law at redhat dot com]

------- Comment #12 from law at redhat dot com  2010-02-11 04:49 -------
Subject: Re:  [4.4/4.5 regression] IRA apparently systematically
 making reload too busy on 2 address instructions with 3 operands

On 02/10/10 02:46, steven at gcc dot gnu dot org wrote:
> ------- Comment #9 from steven at gcc dot gnu dot org  2010-02-10 09:46 -------
> What is the purpose of regmove these days, anyway? Isn't it all useless code
> thanks to IRA?
>    
Not quite.  There were some hunks that were removed shortly after IRA 
was integrated.  The majority of what's left are things not handled by 
IRA.    The code most likely to be useless right now is 
optimize_reg_copy_2.    With some IRA work, optimize_reg_copy_1 might 
disappear.

optimize_reg_copy_3 optimizes zero & sign extensions.  One could argue 
this should be handled elsewhere.

fixup_match_2 optimizes constants in arithmetic insns -- the net result 
is some lifetimes may be shortened and autoinc opportunities may be 
exposed.  This could be handled by more modern techniques, but certainly 
isn't something IRA should be doing.
Jeff


-- 


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

[Bug middle-end/42973] [4.4/4.5 regression] IRA apparently systematically making reload too busy on 2 address instructions with 3 operands

[hubicka at ucw dot cz]

------- Comment #13 from hubicka at ucw dot cz  2010-02-11 16:56 -------
Subject: Re:  [4.4/4.5 regression] IRA apparently
        systematically making reload too busy on 2 address instructions
        with 3 operands

Hi,
it seems that the NAMD improved as expected tonight (by about 3%)
http://gcc.opensuse.org/SPEC/CFP/sb-barbella.suse.de-head-64-2006/index.html

Honza


-- 


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

[Bug middle-end/42973] [4.4 regression] IRA apparently systematically making reload too busy on 2 address instructions with 3 operands

[hubicka at gcc dot gnu dot org]

------- Comment #14 from hubicka at gcc dot gnu dot org  2010-02-11 16:57 -------
Fixed on trunk.


-- 

hubicka at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|4.4.3 4.5.0                 |4.4.3
            Summary|[4.4/4.5 regression] IRA    |[4.4 regression] IRA
                   |apparently systematically   |apparently systematically
                   |making reload too busy on 2 |making reload too busy on 2
                   |address instructions with 3 |address instructions with 3
                   |operands                    |operands


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

[Bug middle-end/42973] [4.4 regression] IRA apparently systematically making reload too busy on 2 address instructions with 3 operands

[rguenth at gcc dot gnu dot org]

------- Comment #15 from rguenth at gcc dot gnu dot org  2010-04-06 11:20 -------
GCC 4.5.0 is being released.  Deferring to 4.5.1.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.5.0                       |4.5.1


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

[Bug middle-end/42973] [4.4 regression] IRA apparently systematically making reload too busy on 2 address instructions with 3 operands

[hubicka at ucw dot cz]

------- Comment #16 from hubicka at ucw dot cz  2010-04-06 11:38 -------
Subject: Re:  [4.4 regression] IRA apparently
        systematically making reload too busy on 2 address instructions
        with 3 operands

I believe Vladimir fixed this bug (comment #13)

Honza


-- 


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

[Bug middle-end/42973] [4.4 regression] IRA apparently systematically making reload too busy on 2 address instructions with 3 operands

[law at redhat dot com]

------- Comment #17 from law at redhat dot com  2010-04-06 15:20 -------
Subject: Re:  [4.4 regression] IRA apparently systematically
 making reload too busy on 2 address instructions with 3 operands

On 04/06/10 05:38, hubicka at ucw dot cz wrote:
> ------- Comment #16 from hubicka at ucw dot cz  2010-04-06 11:38 -------
> Subject: Re:  [4.4 regression] IRA apparently
>          systematically making reload too busy on 2 address instructions
>          with 3 operands
>
> I believe Vladimir fixed this bug (comment #13)
>    
Correct.

jeff


-- 


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

[Bug middle-end/42973] [4.4 regression] IRA apparently systematically making reload too busy on 2 address instructions with 3 operands

[rguenth at gcc dot gnu dot org]

------- Comment #18 from rguenth at gcc dot gnu dot org  2010-04-06 15:38 -------
Adjusting target milestone and known-to-work then.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|4.3.4                       |4.3.4 4.5.0
   Target Milestone|4.5.1                       |4.4.4


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

[Bug middle-end/42973] [4.4 regression] IRA apparently systematically making reload too busy on 2 address instructions with 3 operands

[jakub at gcc dot gnu dot org]

-- 

jakub at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.4.4                       |4.4.5


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

[Bug middle-end/42973] [4.4 regression] IRA apparently systematically making reload too busy on 2 address instructions with 3 operands

[law at redhat dot com]

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

Jeffrey A. Law <law at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |law at redhat dot com
         Resolution|                            |FIXED

--- Comment #19 from Jeffrey A. Law <law at redhat dot com> 2011-02-21 23:46:07 UTC ---
Fixed long ago.

[Bug middle-end/42973] [4.4 regression] IRA apparently systematically making reload too busy on 2 address instructions with 3 operands

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.4.5                       |4.4.6