[Bug tree-optimization/14703] Inadequate optimization of inline templated functions

[Bug tree-optimization/14703] Inadequate optimization of inline templated functions

[eric-gcc at omnifarious dot org]

------- Comment #6 from eric-gcc at omnifarious dot org  2006-03-02 20:25 -------
I'm pleased that I came up with such a difficult test case for the optimizer. 
I never thought it'd be that hard.  :-)

I don't know anything about the internals, but...

The compiler has to generate everything down to the fibconst<0> and fibconst<1>
specializations anyway.  So why can't it memoize and filter the optimization
up?  Say it generates fibconst<1> and fibconst<2> in order to generate
fibconst<3>, then it discovers that fibconst<3> can be optimized to return
plain old '3'.  It can save that, and then when it comes down again needing
fibconst<2> and fibconst<3> in order to generate fibconst<4>, it can see the
already optimized version of fibconst<3> and generate an optimized version of
fibconst<4> that just returns plain old '5'.

Maybe I have things totally wrong and there's no way to do anything like that
with the code.  Or maybe it would turn out that that way of doing things is so
special case that it's not worth bothering with.

But, I just wonder if memoizing some sort of optimized version of a function
would help with a lot of things.


-- 


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

[Bug tree-optimization/14703] Inadequate optimization of inline templated functions

[rguenth at gcc dot gnu dot org]

------- Comment #7 from rguenth at gcc dot gnu dot org  2006-03-03 10:29 -------
Note that using functions as in fibconst is not really an efficient way to do
this.  Still, with gcc 4.1.0 you now have the ability to use

template<unsigned long long L> inline __attribute__((flatten)) unsigned long
long fibconst()
{
   return fibconst<L - 1>() + fibconst<L - 2>();
}

which will result in one call in main and a fibconst that returns the constant
requested.  Of course for big numbers you'll hit interesting quadraticness in
time and memory required to build the program - so the limits in place actually
prevent you from running into this issue.  It's like

rguenther@g148:/tmp> ~/bin/maxmem2.sh
/space/rguenther/install/gcc-4.1.0/bin/gcc -O2 -S t.C -DVAL=23
total: 149886 kB
rguenther@g148:/tmp> ~/bin/maxmem2.sh
/space/rguenther/install/gcc-4.1.0/bin/gcc -O2 -S t.C -DVAL=24
total: 238102 kB
rguenther@g148:/tmp> ~/bin/maxmem2.sh
/space/rguenther/install/gcc-4.1.0/bin/gcc -O2 -S t.C -DVAL=25
total: 385738 kB
rguenther@g148:/tmp> ~/bin/maxmem2.sh
/space/rguenther/install/gcc-4.1.0/bin/gcc -O2 -S t.C -DVAL=26
total: 623094 kB

so, an exponential growth in memory usage due to the way we're doing the
inlining.


-- 


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

[Bug tree-optimization/14703] [4.4 regression] Inadequate optimization of inline templated functions, infinite loop in ipa-reference and memory hog

[hubicka at gcc dot gnu dot org]

------- Comment #8 from hubicka at gcc dot gnu dot org  2008-09-06 12:37 -------
Hi,
the following patch fixes inlining problem:
Index: passes.c
===================================================================
--- passes.c    (revision 139985)
+++ passes.c    (working copy)
@@ -565,6 +565,7 @@ init_optimization_passes (void)
        }
       NEXT_PASS (pass_release_ssa_names);
       NEXT_PASS (pass_rebuild_cgraph_edges);
+      NEXT_PASS (pass_inline_parameters);
     }
   NEXT_PASS (pass_ipa_increase_alignment);
   NEXT_PASS (pass_ipa_matrix_reorg);
Early inliner does not recompute body size after optimization.  This call got
lost in some cleanups.

With this we inline well, but we leak so much memory so compiler explode.  I am
just looking into it.

However this testcase send ipa-reference to infinite loop on unpatched
compiler.
Kenny, I can not make much sense of merge_callee_local_info.
If you want to produce combined summary of the function after inlining, you
need to produce duplicate copy of the local properties and recusively walk the
inlined edges of the inline clones (not masters) merging in the original infos
from masters.
But I don't see why you want to do this at first place and you can't just run
propagation on the expanded tree?

Honza


-- 

hubicka at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |zadeck at naturalbridge dot
                   |                            |com
           Severity|enhancement                 |normal
   Last reconfirmed|2006-03-01 02:48:47         |2008-09-06 12:37:51
               date|                            |
            Summary|Inadequate optimization of  |[4.4 regression] Inadequate
                   |inline templated functions  |optimization of inline
                   |                            |templated functions,
                   |                            |infinite loop in ipa-
                   |                            |reference and memory hog


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

[Bug tree-optimization/14703] [4.4 regression] Inadequate optimization of inline templated functions, infinite loop in ipa-reference and memory hog

[hubicka at gcc dot gnu dot org]

------- Comment #9 from hubicka at gcc dot gnu dot org  2008-09-06 12:56 -------
cp/lex.c:590 (copy_decl)                              10176: 0.0%          0:
0.0%     578168: 0.0%      66200: 0.0%       2257
cp/lex.c:510 (build_lang_decl)                       161064: 0.1%      73304:
0.0%     928504: 0.0%     103928: 0.1%       4891
ggc-common.c:187 (ggc_calloc)                     128717192:50.5%       9936:
0.0%   84083632: 3.5%      11048: 0.0%        651
tree-dfa.c:150 (create_var_ann)                           0: 0.0% 
383385552:98.7%  212651472: 8.9%   54185184:28.3%    6773148
tree-inline.c:484 (remap_block)                   117369096:46.1%          0:
0.0%  939210480:39.4%   81275352:42.5%   10159419
tree-inline.c:4088 (copy_decl_no_change)              36328: 0.0%          0:
0.0% 1137856064:47.7%   54184584:28.3%    6773199

This patch solves it:
Index: tree-ssa-live.c
===================================================================
--- tree-ssa-live.c     (revision 139985)
+++ tree-ssa-live.c     (working copy)
@@ -489,6 +489,13 @@ remove_unused_scope_block_p (tree scope)
       if (TREE_CODE (*t) == FUNCTION_DECL)
        unused = false;

+      /* Remove everything we don't generate debug info for.  */
+      else if (DECL_IGNORED_P (*t))
+       {
+         *t = TREE_CHAIN (*t);
+         next = t;
+       }
+
       /* When we are outputting debug info, we usually want to output
         info about optimized-out variables in the scope blocks.
         Exception are the scope blocks not containing any instructions

The combined patch masks ipa-reference issue, but it needs to be solved too.


-- 

hubicka at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2008-09-06 12:37:51         |2008-09-06 12:56:26
               date|                            |


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

[Bug tree-optimization/14703] [4.4 regression] Inadequate optimization of inline templated functions, infinite loop in ipa-reference and memory hog

[hubicka at gcc dot gnu dot org]

------- Comment #10 from hubicka at gcc dot gnu dot org  2008-09-06 17:11 -------
Subject: Bug 14703

Author: hubicka
Date: Sat Sep  6 17:10:00 2008
New Revision: 140068

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=140068
Log:
        PR tree-optimization/14703
        * tree-ssa-live.c (remove_unused_scope_block_p): Remove ignored
declarations.
        * passes.c (init_optimization_passes): Recompute inline parameters.
        * g++.dg/tree-ssa-pr14703.C: New testcase.

Added:
    trunk/gcc/testsuite/g++.dg/tree-ssa/pr14703.C
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/passes.c
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-live.c


-- 


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

[Bug tree-optimization/14703] [4.4 regression] Inadequate optimization of inline templated functions, infinite loop in ipa-reference and memory hog

[hubicka at gcc dot gnu dot org]

------- Comment #11 from hubicka at gcc dot gnu dot org  2008-09-06 20:23 -------
The code quality problems are solved.  Not closing the bug until IPA-reference
is fixed.

Honza


-- 


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

[Bug tree-optimization/14703] [4.4 regression] Inadequate optimization of inline templated functions, infinite loop in ipa-reference and memory hog

[luisgpm at linux dot vnet dot ibm dot com]

------- Comment #12 from luisgpm at linux dot vnet dot ibm dot com  2008-09-11 05:18 -------
This patch (revision 140068) breaks SPEC2000's 200.sixtrack benchmark for
POWER6 due to miscompares.  Reverting this patch solves the problem. Not sure
what specific problem was introduced. I can isolate a testcase if needed be.


-- 


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

[Bug tree-optimization/14703] [4.4 regression] Inadequate optimization of inline templated functions, infinite loop in ipa-reference and memory hog

[hubicka at gcc dot gnu dot org]

------- Comment #13 from hubicka at gcc dot gnu dot org  2008-09-12 08:33 -------
Having testcase would be great.  In theory removing unused things from debug
info should not make any difference.  Perhaps it is related to stack frame
packing, that is only other place walking blocks.
could you please try adding && is_gimple_reg (*t)?

Honza


-- 


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

[Bug tree-optimization/14703] [4.4 regression] Inadequate optimization of inline templated functions, infinite loop in ipa-reference and memory hog

[hubicka at gcc dot gnu dot org]

------- Comment #14 from hubicka at gcc dot gnu dot org  2008-09-12 08:39 -------
Created an attachment (id=16301)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16301&action=view)
patch that should fix the sixtrack problem.

This patch should solve the sixtrack problem.  Can you please test for me?

Honza


-- 


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

[Bug tree-optimization/14703] [4.4 regression] Inadequate optimization of inline templated functions, infinite loop in ipa-reference and memory hog

[hubicka at gcc dot gnu dot org]

------- Comment #15 from hubicka at gcc dot gnu dot org  2008-09-19 06:22 -------
The infinite loop in ipa-reference is solved now.  Is the sixtrack problem
remaining and if so, would be possible to test the proposed patch?
We probably could track it as independent PR and close this one.

Honza


-- 


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

[Bug tree-optimization/14703] Inadequate optimization of inline templated functions, infinite loop in ipa-reference and memory hog

[rguenth at gcc dot gnu dot org]

------- Comment #16 from rguenth at gcc dot gnu dot org  2008-11-01 11:51 -------
How is this a regression?  In fact this seems to be fixed on the trunk and
instead the 4.3 branch and earlier releases suffer from memory/compile-time
explosion during inlining.

Marked as fixed.  If the problem from comment #12 still occurs it should go
to a separate PR.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
           Priority|P2                          |P3
         Resolution|                            |FIXED
            Summary|[4.4 regression] Inadequate |Inadequate optimization of
                   |optimization of inline      |inline templated functions,
                   |templated functions,        |infinite loop in ipa-
                   |infinite loop in ipa-       |reference and memory hog
                   |reference and memory hog    |
   Target Milestone|---                         |4.4.0


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

[Bug tree-optimization/14703] Inadequate optimization of inline templated functions

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-05-27 00:15 -------
What we need for this testcase is the following:
inline, optimize, inline, ...

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2004-12-25 01:27:52         |2005-05-27 00:15:50
               date|                            |


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

[Bug tree-optimization/14703] Inadequate optimization of inline templated functions

[rguenth at gcc dot gnu dot org]

------- Additional Comments From rguenth at gcc dot gnu dot org  2005-02-25 16:53 -------
http://gcc.gnu.org/ml/gcc-patches/2005-02/msg01571.html

improves this to the extent that the inliner now estimates the size of
fibconst to
   n    size
 0,1,2  0
   3    1
   4    2
   5    4
   6    7

etc., i.e. to the number of additions required.

Inlining all of fibconst<90> now only requires the appropriate limits, or,
of course folding during inlining.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at tat dot physik
                   |                            |dot uni-tuebingen dot de


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