[Bug tree-optimization/37916] New: [4.0 Regression] SSA names causing register pressure; unnecessarily many simultaneously "live" names.

[Bug tree-optimization/37916] New: [4.0 Regression] SSA names causing register pressure; unnecessarily many simultaneously "live" names.

[hp at gcc dot gnu dot org]

The attached preprocessed code in the first attachment is that of the adler32
function in zlib-1.1.3.  It comes highest in the profile of a zlib-based
performance regression test (the "example" program with no parameters).
I'm attaching the assembly code corresponding to gcc-3.2.1 for cris-axis-elf
with -O2 -march=v10 -fno-gcse -fno-reorder-blocks (the latter options being the
default in our local distribution) as well as the versions for the 4.3 branch
at 141344 and trunk at 141361 with the same options.  Note the larger stack
frames for the newer versions, as well as larger code that uses all available
registers and then some stack slots for the additive sums, where two registers
would have been enough.

While SSA generates lots of "names", IIUC they should have been collapsed
before outof-ssa.  It does to some extent, if the uses and the definitions are
close enough.  Looking at the tree-dumps, it's one pass that moved all the uses
away from the definitions, tree-reassoc, and no pass later that moved them
"back"; in particular TER (part of outof-ssa) did not.  Adding the option
-fno-tree-reassoc gets rid of most of the regression for this code (and
others).

Having TER changed to, or adding a subpass of outof-ssa, that moves each use
back to its definition, would seem like a better solution than shutting off
tree-reassoc.

This is also a good example of missed post-increment opportunities (all
versions); instead of increasing offsets from a base, there should have been a
single post-incremented register.


-- 
           Summary: [4.0 Regression] SSA names causing register pressure;
                    unnecessarily many simultaneously "live" names.
           Product: gcc
           Version: 4.3.3
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: hp at gcc dot gnu dot org
  GCC host triplet: x86_64-unknown-linux-gnu
GCC target triplet: cris-*-* and crisv32-*-*


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

[Bug tree-optimization/37916] [4.0 Regression] SSA names causing register pressure; unnecessarily many simultaneously "live" names.

[hp at gcc dot gnu dot org]

------- Comment #1 from hp at gcc dot gnu dot org  2008-10-25 20:13 -------
Created an attachment (id=16541)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16541&action=view)
Preprocessed adler32.c from zlib-1.1.3, with header gunk pruned.


-- 


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

[Bug tree-optimization/37916] [4.0 Regression] SSA names causing register pressure; unnecessarily many simultaneously "live" names.

[hp at gcc dot gnu dot org]

------- Comment #2 from hp at gcc dot gnu dot org  2008-10-25 20:22 -------
Created an attachment (id=16542)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16542&action=view)
Assembly output corresponding to gcc-3.2.1

For cris-axis-elf, with -O2 -march=v10 -fno-gcse -fno-reorder-blocks
(actually a quite modified local version, but supposedly no effects on this
code.)
Note that this version uses "only" three call-saved registers.


-- 


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

[Bug tree-optimization/37916] [4.0 Regression] SSA names causing register pressure; unnecessarily many simultaneously "live" names.

[hp at gcc dot gnu dot org]

------- Comment #3 from hp at gcc dot gnu dot org  2008-10-25 20:57 -------
Created an attachment (id=16543)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16543&action=view)
Assembly output corresponding to gcc-4.4.0 (trunk at 141361)

For cris-axis-elf, with -O2 -march=v10 -mno-mul-bug-workaround -fno-ivopts
-fno-reorder-blocks -fno-gcse
(Shutting off ivopts has a proven overall positive effect on this port.)


-- 


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

[Bug tree-optimization/37916] [4.0 Regression] SSA names causing register pressure; unnecessarily many simultaneously "live" names.

[hp at gcc dot gnu dot org]

------- Comment #4 from hp at gcc dot gnu dot org  2008-10-25 21:06 -------
Created an attachment (id=16544)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16544&action=view)
Assembly output corresponding to gcc-4.3.3 (gcc-4_3-branch at 141344)

Similar: for cris-axis-elf, with -O2 -march=v10 -mno-mul-bug-workaround
-fno-ivopts -fno-reorder-blocks -fno-gcse


-- 


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

[Bug tree-optimization/37916] [4.0 Regression] SSA names causing register pressure; unnecessarily many simultaneously "live" names.

[hp at gcc dot gnu dot org]

------- Comment #5 from hp at gcc dot gnu dot org  2008-10-25 21:09 -------
Created an attachment (id=16545)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16545&action=view)
As 4.4.0 above but with -fno-tree-reassoc

As attachment id=16543, but adding -fno-tree-reassoc.


-- 


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

[Bug tree-optimization/37916] [4.0 Regression] SSA names causing register pressure; unnecessarily many simultaneously "live" names.

[hp at gcc dot gnu dot org]

------- Comment #6 from hp at gcc dot gnu dot org  2008-10-25 21:20 -------
Created an attachment (id=16546)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16546&action=view)
As 4.3.3 above but with -fno-tree-reassoc

As attachment id=16544, but adding -fno-tree-reassoc.
Note that it now "only" uses 6 of the 9 available call-saved registers,
still quite a regression since 3.2.1 (three registers).

FWIW, I don't think only using call-clobbered registers (5 plus 2 special
registers suitable only for moves) should be unpossible for this code.


-- 


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

[Bug tree-optimization/37916] [4.0 Regression] SSA names causing register pressure; unnecessarily many simultaneously "live" names.

[hp at gcc dot gnu dot org]

-- 

hp at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2008-10-25 21:24:13
               date|                            |


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

[Bug tree-optimization/37916] [4.0 Regression] SSA names causing register pressure; unnecessarily many simultaneously "live" names.

[rguenth at gcc dot gnu dot org]

------- Comment #7 from rguenth at gcc dot gnu dot org  2008-10-27 10:45 -------
Please update the know-to-work and known-to-fail fields and adjust the
regression marker from '4.0' which is bogus.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org


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

[Bug tree-optimization/37916] [Regression] SSA names causing register pressure; unnecessarily many simultaneously "live" names.

[hp at gcc dot gnu dot org]

------- Comment #8 from hp at gcc dot gnu dot org  2008-10-27 11:53 -------
Hey, it's not bogus, it's when SSA was introduced!  But, I removed it, as it's
obviously confusing.


-- 

hp at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |4.3.1
      Known to work|                            |3.2.1
            Summary|[4.0 Regression] SSA names  |[Regression] SSA names
                   |causing register pressure;  |causing register pressure;
                   |unnecessarily many          |unnecessarily many
                   |simultaneously "live" names.|simultaneously "live" names.


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

[Bug tree-optimization/37916] [4.2/4.3/4.4 Regression] SSA names causing register pressure; unnecessarily many simultaneously "live" names.

[rguenth at gcc dot gnu dot org]

------- Comment #9 from rguenth at gcc dot gnu dot org  2008-10-27 12:32 -------
This is not how the regression marking works ;)  Fixing...


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[Regression] SSA names      |[4.2/4.3/4.4 Regression] SSA
                   |causing register pressure;  |names causing register
                   |unnecessarily many          |pressure; unnecessarily many
                   |simultaneously "live" names.|simultaneously "live" names.
   Target Milestone|---                         |4.2.5


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

[Bug tree-optimization/37916] [4.2/4.3/4.4 Regression] SSA names causing register pressure; unnecessarily many simultaneously "live" names.

[jakub at gcc dot gnu dot org]

-- 

jakub at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P5


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

[Bug tree-optimization/37916] [4.2/4.3/4.4 Regression] SSA names causing register pressure; unnecessarily many simultaneously "live" names.

[rguenth at gcc dot gnu dot org]

------- Comment #10 from rguenth at gcc dot gnu dot org  2008-10-27 12:46 -------
Is scheduling before reload enabled for your target?  If not can you try
-fschedule-insns1?


-- 


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

[Bug tree-optimization/37916] [4.2/4.3/4.4 Regression] SSA names causing register pressure; unnecessarily many simultaneously "live" names.

[hp at gcc dot gnu dot org]

------- Comment #11 from hp at gcc dot gnu dot org  2008-10-27 15:22 -------
(In reply to comment #10)
> Is scheduling before reload enabled for your target?  If not can you try
> -fschedule-insns1?

No such option, I presume you mean -fschedule-insns.  But, as there's no
scheduler description defined for the architecture, all I get is of course:
warning: instruction scheduling not supported on this target machine
with no difference in the output with -O2 -march=v10 -mno-mul-bug-workaround
-fno-ivopts -fno-reorder-blocks -fno-gcse.

Besides, scheduling would move uses away from definitions, not closer to them.
:)  Also, if this is meant as a permanent solution, that pass seems a bit late.


-- 


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

[Bug tree-optimization/37916] [4.2/4.3/4.4 Regression] SSA names causing register pressure; unnecessarily many simultaneously "live" names.

[hp at gcc dot gnu dot org]

------- Comment #12 from hp at gcc dot gnu dot org  2008-10-27 16:09 -------
I had an "old" native x86_64-unknown-linux-gnu tree around from
[trunk revision 139963], and I see the corresponding effect there.

Of all four combinations of {,-fno-tree-reassoc} {,-fschedule-insns
-fschedule-insns2}, together with -fno-ivopts -fno-reorder-blocks -fno-gcse, it
was plain  -fno-tree-reassoc (no scheduling) that produces the smallest
stack-frame and *at a glance* smaller, faster code.  (FWIW, I'm a bit surprised
to see that -fschedule-insns -fschedule-insns2 is not the default for this
arch.)


-- 


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

[Bug tree-optimization/37916] [4.2/4.3/4.4 Regression] SSA names causing register pressure; unnecessarily many simultaneously "live" names.

[rguenther at suse dot de]

------- Comment #13 from rguenther at suse dot de  2008-10-27 16:21 -------
Subject: Re:  [4.2/4.3/4.4 Regression] SSA names
 causing register pressure; unnecessarily many simultaneously "live" names.

On Mon, 27 Oct 2008, hp at gcc dot gnu dot org wrote:

> ------- Comment #12 from hp at gcc dot gnu dot org  2008-10-27 16:09 -------
> I had an "old" native x86_64-unknown-linux-gnu tree around from
> [trunk revision 139963], and I see the corresponding effect there.
> 
> Of all four combinations of {,-fno-tree-reassoc} {,-fschedule-insns
> -fschedule-insns2}, together with -fno-ivopts -fno-reorder-blocks -fno-gcse, it
> was plain  -fno-tree-reassoc (no scheduling) that produces the smallest
> stack-frame and *at a glance* smaller, faster code.  (FWIW, I'm a bit surprised
> to see that -fschedule-insns -fschedule-insns2 is not the default for this
> arch.)

Because scheduling before register allocation tends to increase register
pressure.  Of course this is not a necessary thing - in fact scheduling
could reduce register pressure, just this would probably be called
re-materialization during register allocation.

tree reassociation is not aware of register pressure as a simple matter
of fact.  TER usually reduces the effect somewhat, but of course in
the end we want to get rid of TER ...

Richard.


-- 


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

[Bug tree-optimization/37916] [4.2/4.3/4.4 Regression] SSA names causing register pressure; unnecessarily many simultaneously "live" names.

[amacleod at redhat dot com]

------- Comment #14 from amacleod at redhat dot com  2008-10-27 16:21 -------
TER's job is to create larger expressions for the expander so that we get
better instruction selection during the initial expansion from trees/tuples to
RTL.

It does this by simply expanding the definition of an ssa-name into its use
location.  This is only done if the definition has a single use, otherwise you
would be executing the definition code more than once, which is generally
undesirable.

The code in this example has a string of about 14 serial adds, followed by 14
related adds.

 s1.155 = s1.153 + (long unsigned int) MEM[base: buf.183, offset: 1]{*D.1237};
 s1.157 = s1.155 + (long unsigned int) MEM[base: buf.183, offset: 2]{*D.1240};
 s1.159 = s1.157 + (long unsigned int) MEM[base: buf.183, offset: 3]{*D.1243};
 s1.161 = s1.159 + (long unsigned int) MEM[base: buf.183, offset: 4]{*D.1246};
<...>
 s2.156 = s2.154 + s1.155;
 s2.158 = s2.156 + s1.157;
 s2.160 = s2.158 + s1.159;
 s2.162 = s2.160 + s1.161;

Since s1.155 is used in 2 different places, it eliminates TER from doing
anything with it.

A register pressure reduction pass could alleviate this problem, either early
near RTL expansion time or as part of the register allocator spilling
subsystem. Both have been talked about, but I don't believe either has been
worked on to any great degree.

Scheduling could help as well if it would see fit to start interleaving some of
those adds:

Since the addition of s1.157 has to wait for s1.155 to finish, and then s1.159
has to wait for s1.157, s2.156 is ready to execute and could be interleaved
between s1.157 and s1.159 while waiting for s1.157 to finish (which since it
has to go to memory one would expect might be delayed).
ie:
 s1.155 = s1.153 + (long unsigned int) MEM[base: buf.183, offset: 1]{*D.1237};
 s1.157 = s1.155 + (long unsigned int) MEM[base: buf.183, offset: 2]{*D.1240};
 s2.156 = s2.154 + s1.155;
 s1.159 = s1.157 + (long unsigned int) MEM[base: buf.183, offset: 3]{*D.1243};
 s2.158 = s2.156 + s1.157;
 s1.161 = s1.159 + (long unsigned int) MEM[base: buf.183, offset: 4]{*D.1246};
 s2.160 = s2.158 + s1.159;

which would, as a convenient side effect, solve the problem.


-- 

amacleod at redhat dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |amacleod at redhat dot com


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

[Bug tree-optimization/37916] [4.2/4.3/4.4 Regression] SSA names causing register pressure; unnecessarily many simultaneously "live" names.

[hp at gcc dot gnu dot org]

------- Comment #15 from hp at gcc dot gnu dot org  2008-10-27 16:36 -------
(In reply to comment #14)
Ok, I was misinformed about TER's purpose.  Ignore TER references in the
description.  The suggestion of a new pass remains and seems agreed on.


-- 

hp at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |hp at gcc dot gnu dot org
                   |dot org                     |
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2008-10-25 21:24:13         |2008-10-27 16:36:09
               date|                            |


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

[Bug tree-optimization/37916] [4.3/4.4/4.5 Regression] SSA names causing register pressure; unnecessarily many simultaneously "live" names.

[jsm28 at gcc dot gnu dot org]

------- Comment #16 from jsm28 at gcc dot gnu dot org  2009-03-31 21:00 -------
Closing 4.2 branch.


-- 

jsm28 at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[4.2/4.3/4.4/4.5 Regression]|[4.3/4.4/4.5 Regression] SSA
                   |SSA names causing register  |names causing register
                   |pressure; unnecessarily many|pressure; unnecessarily many
                   |simultaneously "live" names.|simultaneously "live" names.
   Target Milestone|4.2.5                       |4.3.4


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

[Bug tree-optimization/37916] [4.3/4.4/4.5 Regression] SSA names causing register pressure; unnecessarily many simultaneously "live" names.

[rguenth at gcc dot gnu dot org]

------- Comment #17 from rguenth at gcc dot gnu dot org  2009-08-04 12:29 -------
GCC 4.3.4 is being released, adjusting target milestone.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.3.4                       |4.3.5


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

[Bug tree-optimization/37916] [4.3/4.4/4.5/4.6 Regression] SSA names causing register pressure; unnecessarily many simultaneously "live" names.

[rguenth at gcc dot gnu dot org]

------- Comment #18 from rguenth at gcc dot gnu dot org  2010-05-22 18:12 -------
GCC 4.3.5 is being released, adjusting target milestone.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.3.5                       |4.3.6


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