[Bug rtl-optimization/19580] New: [3.4/4.0 Regression] poor register allocation

[Bug rtl-optimization/19580] New: [3.4/4.0 Regression] poor register allocation

[belyshev at depni dot sinp dot msu dot ru]

------------------------------------------------------------------------------
int r[6];

void f (int n)
{
  while (-- n)
    {
      r [0] += r [5];
      r [1] += r [0];
      r [2] += r [1];
      r [3] += r [2];
      r [4] += r [3];
      r [5] += r [4];
    }
}
------------------------------------------------------------------------------

On i386 with -O2 -fomit-frame-pointer we get:

.L4:
	movl	20(%esp), %ebp
	movl	8(%esp), %eax
	movl	16(%esp), %ebx
	incl	24(%esp)
	addl	%edi, %ebp
	leal	(%ebp,%eax), %esi
	movl	12(%esp), %eax
	movl	%ebp, 20(%esp)
	leal	(%esi,%ebx), %ecx
	movl	4(%esp), %ebx
	movl	%esi, 8(%esp)
	leal	(%ecx,%eax), %edx
	movl	%ecx, 16(%esp)
	leal	(%edx,%ebx), %eax
	movl	24(%esp), %ebx
	cmpl	%ebx, 28(%esp)
	movl	%edx, 12(%esp)
	leal	(%eax,%edi), %edi
	movl	%eax, 4(%esp)
	movl	%edi, (%esp)
	jne	.L4

workaround: -fno-gcse

-- 
           Summary: [3.4/4.0 Regression] poor register allocation
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Keywords: missed-optimization, ra
          Severity: normal
          Priority: P2
         Component: rtl-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: belyshev at depni dot sinp dot msu dot ru
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug rtl-optimization/19580] [3.4/4.0 Regression] poor register allocation

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-23 01:36 -------
Confirmed, only a regression from 3.3.3 which gave the following good code:
.L5:
        addl    %edi, %ebp
        addl    %ebp, %esi
        addl    %esi, %ecx
        addl    %ecx, %edx
        addl    %edx, %eax
        addl    %eax, %edi
        decl    %ebx
        jne     .L5

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
      Known to fail|                            |3.4.0 4.0.0
      Known to work|                            |3.3.3
   Last reconfirmed|0000-00-00 00:00:00         |2005-01-23 01:36:57
               date|                            |
   Target Milestone|---                         |3.4.4


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

[Bug middle-end/19580] [3.4/4.0 Regression] poor register allocation

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-01-23 01:49 -------
This is a tree-optimization bug for 4.0 and later.  I think the problem 
is that we don't catch the store motion opportunity at the tree level 
because to the tree alias analyses arrays are opaque objects.  On RTL 
we can distinguish the array members. 
 
If this is the problem, then Dan's sa-branch work should fix it... 
Dan? 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dberlin at gcc dot gnu dot
                   |                            |org
          Component|rtl-optimization            |middle-end
           Keywords|ra                          |alias


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

[Bug rtl-optimization/19580] [3.4/4.0 Regression] missed load/store monition

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-23 01:53 -------
(In reply to comment #2)
> This is a tree-optimization bug for 4.0 and later.  I think the problem 
> is that we don't catch the store motion opportunity at the tree level 
> because to the tree alias analyses arrays are opaque objects.  On RTL 
> we can distinguish the array members. 
Then why don't we optimize in 3.4.0 while we did in 3.3.3.

> If this is the problem, then Dan's sa-branch work should fix it... 
> Dan? 

I already filed PR  19581 for that because on PPC even in 3.3.3 we don't get optimial code.  But 
someone should look into what happened to changed the behavor in 3.4.0.

I am willing to bet it was the rewritten of the load/store monition.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|middle-end                  |rtl-optimization
            Summary|[3.4/4.0 Regression] poor   |[3.4/4.0 Regression] missed
                   |register allocation         |load/store monition


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

[Bug rtl-optimization/19580] [3.4/4.0 Regression] missed load/store monition

[dberlin at dberlin dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2005-01-23 02:08 -------
Subject: Re:  [3.4/4.0 Regression] poor register
 allocation



On Sat, 23 Jan 2005, steven at gcc dot gnu dot org wrote:

>
> ------- Additional Comments From steven at gcc dot gnu dot org  2005-01-23 01:49 -------
> This is a tree-optimization bug for 4.0 and later.  I think the problem
> is that we don't catch the store motion opportunity at the tree level
> because to the tree alias analyses arrays are opaque objects.  On RTL
> we can distinguish the array members.
>
> If this is the problem, then Dan's sa-branch work should fix it...
> Dan?

It will once i handle constant index array refs (It currently punts on 
array refs entirely).



-- 


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

[Bug rtl-optimization/19580] [3.4/4.0 Regression] missed load/store monition

[belyshev at depni dot sinp dot msu dot ru]

------- Additional Comments From belyshev at depni dot sinp dot msu dot ru  2005-01-23 04:34 -------
Caused by this patch:

2003-04-01  Zdenek Dvorak  <rakdver@atrey.karlin.mff.cuni.cz>

	* gcse.c (struct ls_expr): Added pattern_regs field.
	(ldst_entry): Initialize it.
	(extract_mentioned_regs, extract_mentioned_regs_helper): New.
	(store_ops_ok): Use regs precomputed by them.
	(find_loads, store_killed_in_insn, load_kills_store): Change return
	type to bool.
	(store_killed_before, store_killed_after): Take position of register
	set in account.
	(reg_set_info): Store position of the setter.
	(gcse_main): Enable store motion.
	(mems_conflict_for_gcse_p): Enable load motion of non-symbol mems.
	(pre_insert_copy_insn, update_ld_motion_stores, insert_store): Prevent rtl
	sharing.
	(simple_mem): Enable store motion of non-symbol mems.
	(regvec): Type changed.
	(LAST_AVAIL_CHECK_FAILURE): New.
	(compute_store_table_current_insn): New.
	(build_store_vectors): Computation of availability and anticipatability
	moved ...
	(compute_store_table, find_moveable_store): ... here.
	(delete_store): Remove senseless comment.
	(store_motion): Reorganize.


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |ra


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

[Bug rtl-optimization/19580] [3.4/4.0 Regression] missed load/store motion

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-23 04:38 -------
(In reply to comment #5)
> Caused by this patch:
And I was right this was caused by the store motion rewrite.
http://gcc.gnu.org/ml/gcc-patches/2003-02/msg02090.html

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|ra                          |
            Summary|[3.4/4.0 Regression] missed |[3.4/4.0 Regression] missed
                   |load/store monition         |load/store motion


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

[Bug rtl-optimization/19580] [3.4/4.0 Regression] missed load/store motion

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-23 04:39 -------
Note this is not a register allocator problem any more but a missed optimization.

-- 


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

[Bug rtl-optimization/19580] [3.4/4.0 Regression] missed load/store motion

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-01-23 11:13 -------
The patch you identified makes RTL store motion work.  Before the patch 
gcse-sm just did almost nothing at all. 
 
You can't blame a patch for fixing a pass. 
 
Closing this as won't fix.  Lets focus on PR19581 instead. 
 
 
 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |WONTFIX


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

[Bug rtl-optimization/19580] [3.4/4.0 Regression] missed load/store motion

[belyshev at depni dot sinp dot msu dot ru]

------- Additional Comments From belyshev at depni dot sinp dot msu dot ru  2005-01-23 14:36 -------
(In reply to comment #8)
> Closing this as won't fix.  Lets focus on PR19581 instead. 

Two notes:

1) tree-outof-ssa does not coalesce variables in this case:

g.c:                             g.c.t65.optimized:
------------------------------------------------------------------------
void g ()                       |
{                               |       <bb 0>:
  r [0] += r [2];               |         D.1129 = r[0] + r[2];
  r [1] += r [0];               |         r[0] = D.1129;
  r [2] += r [1];               |         D.1131 = D.1129 + r[1];
}                               |         r[1] = D.1131;
                                |         r[2] = D.1131 + r[2];
                                |         return;
                                |
------------------------------------------------------------------------

... while it does in this:
f.c:                             f.c.t65.optimized:
------------------------------------------------------------------------
void f ()                       |
{                               |       <bb 0>:
  r [0] += r [1];               |         r[0] = r[0] + r[1];
  r [1] += r [2];               |         r[1] = r[1] + r[2];
  r [2] += r [0];               |         r[2] = r[2] + r[0];
}                               |         return;
                                |
------------------------------------------------------------------------

2) and disabling -fgcse-lm *fixes* original problem for 3.4 and 4.0.

I cannot believe this bug is WONTFIX for 4.0 just because it will be fixed in
4.1 at tree level.


-- 


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

[Bug rtl-optimization/19580] [3.4/4.0 Regression] missed load/store motion

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-23 15:24 -------
Well since this is more than just a 4.0.0 regressions lets reopen it.  Basically lsm was rewritten for 3.4.0 
and it causes this regression which means lsm is not good at all.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
         Resolution|WONTFIX                     |


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

[Bug rtl-optimization/19580] [3.4/4.0 Regression] missed load/store motion

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-01-23 15:41 -------
This is *not* a gcc 4.0 regression.  The 4.0 problem is PR19581. 
 
But Andrew prefers keeping multiple bugs open for the same regression, 
apparently. 
 

-- 


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

[Bug rtl-optimization/19580] [3.4/4.0 Regression] missed load/store motion

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-23 15:43 -------
(In reply to comment #11)
> This is *not* a gcc 4.0 regression.  The 4.0 problem is PR19581. 
What about 3.4.0?

-- 


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

[Bug rtl-optimization/19580] [3.4/4.0 Regression] missed load/store motion

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-01-23 15:51 -------
 
g.c:                             g.c.t65.optimized: 
------------------------------------------------------------------------ 
void g ()                       | 
{                               |       <bb 0>: 
  r [0] += r [2];               |         D.1129 = r[0] + r[2]; 
  r [1] += r [0];               |         r[0] = D.1129; 
  r [2] += r [1];               |         D.1131 = D.1129 + r[1]; 
}                               |         r[1] = D.1131; 
                                |         r[2] = D.1131 + r[2]; 
                                |         return; 
 
What exactly are you expecting to be coalesced in this case, if I may ask? 
 
 
 

-- 


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

[Bug rtl-optimization/19580] [3.4/4.0 Regression] missed load/store motion

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-01-23 15:56 -------
Clearly it *is* a 3.4 regression. 
But the subject also includes 4.0.  And that's not right because we have 
disabled gcse store motion for gcc 4.0.  The bug for 4.0 is PR19581 and 
that is just a different issue. 
 
 

-- 


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

[Bug rtl-optimization/19580] [3.4/4.0 Regression] missed load/store motion

[belyshev at depni dot sinp dot msu dot ru]

------- Additional Comments From belyshev at depni dot sinp dot msu dot ru  2005-01-23 18:31 -------
(In reply to comment #13)
> What exactly are you expecting to be coalesced in this case, if I may ask? 

I am expecting all of D.1129 and D.1131 to be coalesced so this:

    D.1129 = r[0] + r[2]; 
    r[0] = D.1129; 
    D.1131 = D.1129 + r[1]; 
    r[1] = D.1131; 
    r[2] = D.1131 + r[2]; 

...is turned into what it was (like in second example):

    r[0] = r[0] + r[2];
    r[1] = r[0] + r[1];
    r[2] = r[1] + r[2];


-- 


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

[Bug rtl-optimization/19580] [3.4/4.0 Regression] missed load/store motion

[dberlin at dberlin dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2005-01-23 19:07 -------
Subject: Re:  [3.4/4.0 Regression] missed load/store
 motion



On Sun, 23 Jan 2005, belyshev at depni dot sinp dot msu dot ru wrote:

>
> ------- Additional Comments From belyshev at depni dot sinp dot msu dot ru  2005-01-23 18:31 -------
> (In reply to comment #13)
>> What exactly are you expecting to be coalesced in this case, if I may ask?
>
> I am expecting all of D.1129 and D.1131 to be coalesced so this:
>
>    D.1129 = r[0] + r[2];
>    r[0] = D.1129;
>    D.1131 = D.1129 + r[1];
>    r[1] = D.1131;
>    r[2] = D.1131 + r[2];
>
> ...is turned into what it was (like in second example):
>
>    r[0] = r[0] + r[2];
>    r[1] = r[0] + r[1];
>    r[2] = r[1] + r[2];

It can't.
It believes they conflict right now.
.


-- 


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

[Bug rtl-optimization/19580] [3.4/4.0 Regression] missed load/store motion

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-01-23 19:11 -------
Ehm, does it really think they conflict now, or is it simply not replacing 
a reg with a load? 
 

-- 


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

[Bug rtl-optimization/19580] [3.4/4.0 Regression] missed load/store motion

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-01-23 19:23 -------
For x86 I get this: 
g: 
        movl    r+8, %edx 
        movl    r, %eax 
        addl    %edx, %eax 
        movl    %eax, r 
        addl    r+4, %eax 
        movl    %eax, r+4 
        addl    %edx, %eax 
        movl    %eax, r+8 
        ret 
 
That is pretty much the best you can get, as far as I can tell. 
 
For AMD64 it's similar: 
 
g: 
.LFB2: 
        movl    r+8(%rip), %edx 
        movl    r(%rip), %eax 
        addl    %edx, %eax 
        movl    %eax, r(%rip) 
        addl    r+4(%rip), %eax 
        movl    %eax, r+4(%rip) 
        addl    %edx, %eax 
        movl    %eax, r+8(%rip) 
        ret 
.LFE2: 
 
I'm not sure what you think the missed optimization is here.  You will have 
to show what you want at the assembly level, and explain why you think this 
is a coalescing problem.  So far, I don't see a missed optimization. 
 
What is worse is that we fail to do store motion when you put such blocks 
inside a loop, e.g. 
 
int r[6]; 
void g (int n) 
{ 
  while (--n) 
    { 
      r [0] += r [1]; 
      r [1] += r [2]; 
      r [2] += r [0]; 
    } 
} 
 
which is the issue discussed in PR19581. 

-- 


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

[Bug rtl-optimization/19580] [3.4/4.0 Regression] missed load/store motion

[belyshev at depni dot sinp dot msu dot ru]

------- Additional Comments From belyshev at depni dot sinp dot msu dot ru  2005-01-23 19:51 -------
(In reply to comment #18)
> I'm not sure what you think the missed optimization is here.  You will have 
> to show what you want at the assembly level, and explain why you think this 
> is a coalescing problem.  So far, I don't see a missed optimization. 

Short examples in comment #9 I used only to show that there is problem with
variable coalescing at tree level, of course they all optimized at rtl level.

To see *the* problem, compare i386 assembly and .optimized dumps for these two
functions on mainline with patch to bug 19464 applied:

int r[6];

void f (int n)
{
  while (-- n)
    {
      r [0] += r [5];
      r [1] += r [0];
      r [2] += r [1];
      r [3] += r [2];
      r [4] += r [3];
      r [5] += r [4];
    }
}

void g (int n)
{
  while (-- n)
    {
      r [0] += r [1];
      r [1] += r [2];
      r [2] += r [3];
      r [3] += r [4];
      r [4] += r [5];
      r [5] += r [0];
    }
}


-- 


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

[Bug rtl-optimization/19580] [3.4/4.0 Regression] missed load/store motion

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|REOPENED                    |NEW


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

[Bug rtl-optimization/19580] [3.4/4.0/4.1 Regression] missed load/store motion

[mmitchel at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|3.4.4                       |3.4.5


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

[Bug rtl-optimization/19580] [3.4/4.0/4.1 Regression] missed load/store motion

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-07-22 21:13 -------
Moving to 4.0.2 pre Mark.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|3.4.5                       |4.0.2


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

[Bug rtl-optimization/19580] [3.4/4.0/4.1 Regression] missed load/store motion

[mmitchel at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.0.2                       |4.0.3


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