[Bug tree-optimization/46228] New: code produced for STL container is worse in 4.5.1 than in 4.4.5

[Bug tree-optimization/46228] New: code produced for STL container is worse in 4.5.1 than in 4.4.5

[zeev.tarantov at gmail dot com]

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

           Summary: code produced for STL container is worse in 4.5.1 than
                    in 4.4.5
           Product: gcc
           Version: 4.5.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: zeev.tarantov@gmail.com


First of all, I don't know if this is the right component. If not, I apologize
and ask to please reroute appropriately.

This code:

#include <set>
#include <stdio.h>

int main()
{
  static const int array[] = { 1,2,3,4,5,6,7,8,9,10,6 };
  std::set<int> the_set;
  int count = 0;
  for (unsigned i = 0; i < sizeof(array)/sizeof(*array); i++)
  {
    std::pair<std::set<int>::iterator, bool> result =
      the_set.insert(array[i]);
    if (result.second)
      count++;
  }
  printf("%d unique items in array.\n", count);
  return 0;
}

Compiled with g++ -Os -fno-exceptions using gcc 4.5.1+ rev. 165881 produced
code including this loop in main:

  40076d: mov    %ebx,%eax
  40076f: mov    %r12,%rdi
  400772: lea    0x400a60(,%rax,4),%rsi
  40077a: callq  400930 <std::set<int, std::less<int>, std::allocator<int>
>::insert(int const&)>
  40077f: mov    %rax,(%rsp)
  400783: mov    %edx,0x8(%rsp)
  400787: mov    %rax,0x40(%rsp)
  40078c: mov    0x8(%rsp),%rax
  400791: cmp    $0x1,%al
  400793: mov    %rax,0x48(%rsp)
  400798: sbb    $0xffffffffffffffff,%ebp
  40079b: inc    %ebx
  40079d: cmp    $0xb,%ebx
  4007a0: jne    40076d <main+0x19>

and this function:

<std::set<int, std::less<int>, std::allocator<int> >::insert(int const&)>:
  400930: sub    $0x48,%rsp
  400934: callq  400898 <std::_Rb_tree<int, int, std::_Identity<int>,
std::less<int>, std::allocator<int> >::_M_insert_unique(int const&)>
  400939: mov    %edx,0x18(%rsp)
  40093d: mov    0x18(%rsp),%dl
  400941: mov    %dl,0x28(%rsp)
  400945: mov    0x28(%rsp),%edx
  400949: add    $0x48,%rsp
  40094d: retq

Same source code compiled on clang 2.8 into this:

  4007b3: lea    0x400a20(%r14),%rsi
  4007ba: mov    %r15,%rdi
  4007bd: callq  4007fc <std::_Rb_tree<int, int, std::_Identity<int>,
std::less<int>, std::allocator<int> >::_M_insert_unique(int const&)>
  4007c2: and    $0x1,%dl
  4007c5: movzbl %dl,%eax
  4007c8: add    %eax,%ebx
  4007ca: add    $0x4,%r14
  4007ce: cmp    $0x2c,%r14
  4007d2: jne    4007b3 <main+0x5f>

set::insert has been inlined into nothing, and the pair<iterator, bool> doesn't
get space on the stack.

gcc 4.4.5 didn't produce those shuffles, so this seems like a regression from
4.4.

gcc 4.5.1 also didn't inline _Rb_tree_impl(), ~_Rb_tree (two instructions long)
and the above set::insert that should have been maybe two instructions long.
Could this be fixed?

[Bug tree-optimization/46228] code produced for STL container is worse in 4.5.1 than in 4.4.5

[hjl.tools at gmail dot com]

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

H.J. Lu <hjl.tools at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2010.10.29 19:00:05
                 CC|                            |hubicka at gcc dot gnu.org
   Target Milestone|---                         |4.5.2
     Ever Confirmed|0                           |1

--- Comment #1 from H.J. Lu <hjl.tools at gmail dot com> 2010-10-29 19:00:05 UTC ---
It is caused by revision 151728:

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

[Bug tree-optimization/46228] code produced for STL container is worse in 4.5.1 than in 4.4.5

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |paolo.carlini at oracle dot
                   |                            |com

--- Comment #2 from Paolo Carlini <paolo.carlini at oracle dot com> 2010-10-29 20:30:25 UTC ---
Would be http://gcc.gnu.org/ml/gcc-cvs/2009-09/msg00475.html

Given that the "offending" patch is that simple, maybe submitter could quickly
try reverting it and see what happens in this and similar snippets. Or, even
simpler, have a look to the man entry about -finline-limit and experiment with
the various available options.

[Bug tree-optimization/46228] code produced for STL container is worse in 4.5.1 than in 4.4.5

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
           Severity|normal                      |enhancement

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> 2010-10-29 20:42:41 UTC ---
Considering std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare,
_Alloc>::~_Rb_tree() [with _Key = int, _Val = int, _KeyOfValue =
std::_Identity<int>, _Compare = std::less<int>, _Alloc = std::allocator<int>]
with 4 size
 to be inlined into int main() in
/home/apinski/local-gcc/lib/gcc/x86_64-unknown-linux-gnu/4.6.0/../../../../include/c++/4.6.0/bits/stl_set.h:87
 Estimated growth after inlined into all callees is +2 insns.
 Estimated badness is 3, frequency 1.00.
 inline_failed:call is unlikely and code size would grow.

...
Considering std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare,
_Alloc>::~_Rb_tree() [with _Key = int, _Val = int, _KeyOfValue =
std::_Identity<int>, _Compare = std::less<int>, _Alloc = std::allocator<int>]
with 4 size
 to be inlined into int main() in
/home/apinski/local-gcc/lib/gcc/x86_64-unknown-linux-gnu/4.6.0/../../../../include/c++/4.6.0/bits/stl_set.h:87
 Estimated growth after inlined into all callees is +2 insns.
 Estimated badness is 118, frequency 0.00.
 inline_failed:call is unlikely and code size would grow.


I bet we don't take into account that the argument to ~_Rb_tree is an
ADDR_EXPR.  First I noticed it saying the call is unlikely which is true but
the thing that is not true is the +2 insns; only because of the arguments being
passed is an ADDR_EXPR of a component_ref of a var_decl.  Maybe we should
record if the only places pointer arguments are used is in
MEM_REF/INDIRECT_REF's and then inline functions based on that fact if we have
those arguments as a ADDR_EXPR of a decl.

[Bug tree-optimization/46228] code produced for STL container is worse in 4.5.1 than in 4.4.5

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.5.2                       |---

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> 2010-10-29 20:44:20 UTC ---
Oh this is not really a regression and inlining heuristics are hard to compare
between compilers especially in a micro benchmark like the one above.

[Bug tree-optimization/46228] code produced for STL container is worse in 4.5.1 than in 4.4.5

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Guenther <rguenth at gcc dot gnu.org> 2010-10-29 23:28:39 UTC ---
Especially since we now predict main as cold (it's called once).

[Bug tree-optimization/46228] code produced for STL container is worse in 4.5.1 than in 4.4.5

[zeev.tarantov at gmail dot com]

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

--- Comment #6 from Zeev Tarantov <zeev.tarantov at gmail dot com> 2010-10-29 23:44:49 UTC ---
Setting -finline-limit high didn't produce different code.

This function:

  4007f8:       48 8b 77 10             mov    0x10(%rdi),%rsi
  4007fc:       e9 c5 ff ff ff          jmpq   4007c6 <std::_Rb_tree<int, int,
std::_Identity<int>, std::less<int>, std::allocator<int>
>::_M_erase(std::_Rb_tree_node<int>*)>
  400801:       90                      nop

is called 100% of the runs of the program. The code is 10 bytes for the
function and 5 bytes to call it, altogether 15 bytes. Inlined it would be 9
bytes. I don't count debug data for extra symbol and potential slowdown of the
call to code that might not be in cache. If this decision is arbitrary and
won't be changed, too bad. But please someone explain the purpose of this code:

  400939:       89 54 24 18             mov    %edx,0x18(%rsp)
  40093d:       8a 54 24 18             mov    0x18(%rsp),%dl
  400941:       88 54 24 28             mov    %dl,0x28(%rsp)
  400945:       8b 54 24 28             mov    0x28(%rsp),%edx
  400949:       48 83 c4 48             add    $0x48,%rsp
  40094d:       c3                      retq   

The writes to stack slots that are about to be wiped. The net result of leaving
"%edx & 0xff" in %edx using 16 bytes of code. The 72 bytes of stack that are
allocated and unused. How is that in any way good? And the pair variable in
main that is also saved to the stack without ever being read later. Why doesn't
the compiler eliminate writes to memory that is never read from, and then
eliminate the stack slot itself?

> Oh this is not really a regression

Is it your opinion that the code produced by gcc 4.5.1 is as good as the code
produced by gcc 4.4.5 (and clang 2.8)?

section          size
.text             952
.text             856

[Bug tree-optimization/46228] code produced for STL container is worse in 4.5.1 than in 4.4.5

[hubicka at gcc dot gnu.org]

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

--- Comment #7 from Jan Hubicka <hubicka at gcc dot gnu.org> 2010-10-30 15:41:11 UTC ---
We predict main() as executed once, not cold, so code inside loop is inlined
for speed at -O1/-O2/-O3, but this testcase is compiled with -Os.

This seems like usual problem with comdat functions being possibly shared with
other compilation units.  I will check how -fwhole-program behaves and if I can
do something with the heruistics here.

[Bug tree-optimization/46228] code produced for STL container is worse in 4.5.1 than in 4.4.5

[hubicka at gcc dot gnu.org]

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

--- Comment #8 from Jan Hubicka <hubicka at gcc dot gnu.org> 2010-10-30 16:00:12 UTC ---
and BTW -Os also reason why -finline-limits has no effect. As long as we
predict code size to grow, we won't inline at -Os.  We tend to regress at -Os
C++ for this reason.

I wonder what can be done about this.  Either
 - we need to improve heuristics to figure out that inlining is smaller than
call sequence (if it really is)
 - we need to teach GCC that comdat functions are not always shared across
units as extensively as we tend to believe now.

I will take more look tomorrow.

Honza

[Bug tree-optimization/46228] code produced for STL container is worse in 4.5.1 than in 4.4.5

[zeev.tarantov at gmail dot com]

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

--- Comment #9 from Zeev Tarantov <zeev.tarantov at gmail dot com> 2010-10-30 20:05:57 UTC ---
Using -fwhole-program I got sane code. But almost all programs that are not
trivial cannot be compiled with -fwhole-program without LTO. At least on 4.5
branch LTO is not quite stable.

"- we need to improve heuristics to figure out that inlining is smaller than
call sequence (if it really is)"

This would be great.

[Bug tree-optimization/46228] code produced for STL container is worse in 4.5.1 than in 4.4.5

[hubicka at gcc dot gnu.org]

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

--- Comment #10 from Jan Hubicka <hubicka at gcc dot gnu.org> 2010-11-04 04:44:30 UTC ---
"- we need to improve heuristics to figure out that inlining is smaller than
call sequence (if it really is)"

Well, we can't do that here.  What I missed is that the function in question is
a wrapper with one parameter calling function with two. 

Inlininig function realy increase code size assuming that the function is not
comdat just out of programmer's stupidity and is really shared across many
units.

All we can do is to introduce some parameter for COMDATs to reduce likelyness
of their sharing across units.  100% as we have now is overly optimistic.  I
will make patch for testing.

[Bug tree-optimization/46228] code produced for STL container is worse in 4.5.1 than in 4.4.5

[hubicka at gcc dot gnu.org]

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

--- Comment #11 from Jan Hubicka <hubicka at gcc dot gnu.org> 2010-11-04 17:32:32 UTC ---
Created attachment 22284
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=22284
Patch I am testing

Hi,
this patch makes size metric more realistic in two ways
 1) We assumed that return statement has size of 0 while it doesn't
 2) We completely ignored the static cost of offline copy of function (i.e.
prologue/epilogue/alignment). Accounting those two should give GCC a little
extra push to inline function whose offline copies disappears.
Many cases where -Os decided to not inline was off-by-one cases in the cost
metric, so this should make it slightly better.

In the case of COMDATs however this still does not help, since the offline copy
of function is supposed to be shared with other unit and thus not really
eliminated by full inlining. Therefore I also added the trick assuming that
there is only 1/8th probability of sharing comdat with someone else.  It is
lousy but only way to reflect reality I think.  Perhaps we can do some
addtional guesswork if the function is instantiation of template or so, but
that would require some cooperation with the C++ FE.

I added it for overnight testing for SPEC/CSiBE/C++ benchmarks on Vangelis and
will give it a try building Mozilla.

Tramp3d gets 50% code size reduction at -Os (and -Os is now actually smaller
than -O2 and executes about 3 times slower) and I would expect improvements on
C benchmarks, too. The COMDAT trick should not kick in at C code and the
prologue/epilogue/return trick should just do good job.
At -O2 I get 6% code size savings at tramp3d.

Honza

P.S. LTO can now build Mozilla, so -fwhole-program should be more useful than
before ;)

[Bug tree-optimization/46228] code produced for STL container is worse in 4.5.1 than in 4.4.5

[hubicka at gcc dot gnu.org]

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

--- Comment #13 from Jan Hubicka <hubicka at gcc dot gnu.org> 2010-11-10 20:10:51 UTC ---
Author: hubicka
Date: Wed Nov 10 20:10:46 2010
New Revision: 166553

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=166553
Log:
    PR tree-optimize/46228
    * cgraph.c (cgraph_propagate_frequency): Fix typo.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/cgraph.c

[Bug tree-optimization/46228] code produced for STL container is worse in 4.5.1 than in 4.4.5

[hubicka at gcc dot gnu.org]

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

--- Comment #14 from Jan Hubicka <hubicka at gcc dot gnu.org> 2010-11-10 20:23:12 UTC ---
Author: hubicka
Date: Wed Nov 10 20:23:09 2010
New Revision: 166555

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=166555
Log:
    PR tree-optimize/46228
    * doc/invoke.texi (comdat-sharing-probability): Document.
    * ipa-inline.c (cgraph_estimate_growth): Handle COMDATs
    * params.def (PARAM_COMDAT_SHARING_PROBABILITY): New param.
    * g++.dg/tree-ssa/pr46228.C: New testcase.

Added:
    trunk/gcc/testsuite/g++.dg/tree-ssa/pr46228.C
Modified:
    trunk/gcc/doc/invoke.texi
    trunk/gcc/ipa-inline.c
    trunk/gcc/params.def
    trunk/gcc/testsuite/ChangeLog

[Bug tree-optimization/46228] code produced for STL container is worse in 4.5.1 than in 4.4.5

[hubicka at gcc dot gnu.org]

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

--- Comment #15 from Jan Hubicka <hubicka at gcc dot gnu.org> 2010-11-10 20:26:39 UTC ---
Author: hubicka
Date: Wed Nov 10 20:26:36 2010
New Revision: 166556

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=166556
Log:

    PR tree-optimize/46228
    * doc/invoke.texi (comdat-sharing-probability): Document.
    * ipa-inline.c (cgraph_estimate_growth): Handle COMDATs
    * params.def (PARAM_COMDAT_SHARING_PROBABILITY): New param.

Modified:
    trunk/gcc/ChangeLog

[Bug tree-optimization/46228] code produced for STL container is worse in 4.5.1 than in 4.4.5

[zeev.tarantov at gmail dot com]

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

--- Comment #16 from Zeev Tarantov <zeev.tarantov at gmail dot com> 2010-11-11 00:42:57 UTC ---
In
http://gcc.gnu.org/viewcvs/trunk/gcc/doc/invoke.texi?r1=166555&r2=166554&pathrev=166555:

+will be shared acroess multiple compilation units.  The default value is 20.

s/acroess/across/

In
http://gcc.gnu.org/viewcvs/trunk/gcc/params.def?r1=166555&r2=166554&pathrev=166555:

+      "Probability that COMDAT function will be shared with different
compilatoin unit",

s/compilatoin/compilation/
s/unit/units

[Bug ipa/46228] code produced for STL container is worse in 4.5.1 than in 4.4.5

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |marxin at gcc dot gnu.org
          Component|tree-optimization           |ipa
   Target Milestone|---                         |4.8.0
         Resolution|---                         |FIXED

--- Comment #17 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Fixed in GCC 4.8.0.
There has been many many inlining changes since then even and it looks like it
stayed fixed too.