[Bug tree-optimization/43186] New: A loop in tree_unroll_loops_completely never ends

[Bug tree-optimization/43186] New: A loop in tree_unroll_loops_completely never ends

[d dot g dot gorbachev at gmail dot com]

-- 
           Summary: A loop in tree_unroll_loops_completely never ends
           Product: gcc
           Version: 4.5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: d dot g dot gorbachev at gmail dot com
 GCC build triplet: i686-pc-linux-gnu
  GCC host triplet: i686-pc-linux-gnu
GCC target triplet: i686-pc-linux-gnu


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

[Bug tree-optimization/43186] A loop in tree_unroll_loops_completely never ends

[d dot g dot gorbachev at gmail dot com]

------- Comment #1 from d dot g dot gorbachev at gmail dot com  2010-02-26 04:29 -------
Created an attachment (id=19965)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=19965&action=view)
Testcase

gcc -S -O3 -DBUG pr43186.c


-- 


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

[Bug tree-optimization/43186] [4.5 Regression] A loop in tree_unroll_loops_completely never ends

[rguenth at gcc dot gnu dot org]

------- Comment #2 from rguenth at gcc dot gnu dot org  2010-02-26 11:03 -------
Confirmed.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
      Known to work|                            |4.4.2
   Last reconfirmed|0000-00-00 00:00:00         |2010-02-26 11:03:40
               date|                            |
            Summary|A loop in                   |[4.5 Regression] A loop in
                   |tree_unroll_loops_completely|tree_unroll_loops_completely
                   |never ends                  |never ends
   Target Milestone|---                         |4.5.0


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

[Bug tree-optimization/43186] [4.5 Regression] A loop in tree_unroll_loops_completely never ends

[rguenth at gcc dot gnu dot org]

-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rguenth at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2010-02-26 11:03:40         |2010-02-26 11:38:39
               date|                            |


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

[Bug tree-optimization/43186] [4.5 Regression] A loop in tree_unroll_loops_completely never ends

[rguenth at gcc dot gnu dot org]

------- Comment #3 from rguenth at gcc dot gnu dot org  2010-02-26 13:29 -------
For some reason we inline 8 recursive calls of foo resulting in a load of
loops that we all completely unroll.  And in fact this is profitable but
very slow because we estimate induction variable computations to be optimized
(which they are), but we don't do that until we unrolled all loops - so
we generate lots of new SSA names.

Not too bad, but we are left with trivially dead branches from cfgcleanup.

I have a patch.


-- 


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

[Bug tree-optimization/43186] [4.5 Regression] A loop in tree_unroll_loops_completely never ends

[rguenth at gcc dot gnu dot org]

------- Comment #4 from rguenth at gcc dot gnu dot org  2010-02-26 16:02 -------
Subject: Bug 43186

Author: rguenth
Date: Fri Feb 26 16:01:52 2010
New Revision: 157093

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=157093
Log:
2010-02-26  Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/43186
        * gimple.h (gimple_fold): Remove.
        * gimple.c (gimple_fold): Remove.  Inline into single user ...
        * tree-cfgcleanup.c (cleanup_control_expr_graph): ... here.
        Try harder for conditions.

        * gcc.c-torture/compile/pr43186.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.c-torture/compile/pr43186.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/gimple.c
    trunk/gcc/gimple.h
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-cfgcleanup.c


-- 


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

[Bug tree-optimization/43186] [4.5 Regression] A loop in tree_unroll_loops_completely never ends

[rguenth at gcc dot gnu dot org]

------- Comment #5 from rguenth at gcc dot gnu dot org  2010-02-26 16:02 -------
Fixed.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


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

[Bug tree-optimization/43186] [4.5 Regression] A loop in tree_unroll_loops_completely never ends

[d dot g dot gorbachev at gmail dot com]

------- Comment #6 from d dot g dot gorbachev at gmail dot com  2010-02-27 10:17 -------
Thanks! But it still does not work when "a < 3" is replaced by "a < 4". Also,
the original testcase requires much time to compile.


-- 

d dot g dot gorbachev at gmail dot com changed:

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


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

[Bug tree-optimization/43186] [4.5 Regression] A loop in tree_unroll_loops_completely never ends

[rguenth at gcc dot gnu dot org]

------- Comment #7 from rguenth at gcc dot gnu dot org  2010-02-27 19:52 -------
(In reply to comment #6)
> Thanks! But it still does not work when "a < 3" is replaced by "a < 4". Also,
> the original testcase requires much time to compile.

Well, it really only requires much time and memory to compile, it's not
never ending ;)

What you get is in the original testcase 8 times inlining of foo and all
the loop nest completely unrolled (without any intermediate optimization).
The first patch added some intermediate optimization that reduces the amount
of CFG left to further unrollings.

Honza, can we restrict recursive inlining if that increases the loop nest
depth (also for profile guess reasons)?

I realize that manually doing the 8-fold inlining still would leave us with
a slow complete unrolling.  We could restrict us to unroll say a maximum
loop nest depth of 3.  Or what we really would need is constant propagation
and dead code elimination for the unrolled BBs after each iteration.

I'm adding the restriction on unrolling.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |hubicka at gcc dot gnu dot
                   |                            |org
             Status|REOPENED                    |ASSIGNED
           Keywords|                            |compile-time-hog, memory-hog
   Last reconfirmed|2010-02-26 11:38:39         |2010-02-27 19:52:12
               date|                            |


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

[Bug tree-optimization/43186] [4.5 Regression] A loop in tree_unroll_loops_completely never ends

[d dot g dot gorbachev at gmail dot com]

------- Comment #8 from d dot g dot gorbachev at gmail dot com  2010-02-27 22:11 -------
> Well, it really only requires much time and memory to compile,
> it's not never ending ;)

Ah, it means that machine is old.

Also, the generated code is larger then what gcc 4.3 does (4.4 is affected,
too). Should I file a bug report?


-- 


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

[Bug tree-optimization/43186] [4.5 Regression] A loop in tree_unroll_loops_completely never ends

[rguenth at gcc dot gnu dot org]

------- Comment #9 from rguenth at gcc dot gnu dot org  2010-02-27 22:20 -------
(In reply to comment #8)
> > Well, it really only requires much time and memory to compile,
> > it's not never ending ;)
> 
> Ah, it means that machine is old.
> 
> Also, the generated code is larger then what gcc 4.3 does (4.4 is affected,
> too). Should I file a bug report?

GCC 4.3 did only unroll the very innermost loops.  GCC 4.4 does have the same
code (so I wondered why your initial testcase didn't trigger) - I can backport
the parm change there.

As for the size of the code - you can file a bugreport but what the loop
optimizer analyzes looks reasonable.  So I guess the inliner with its
improved size/time estimates inlines more (you might want to verify this).


-- 


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

[Bug tree-optimization/43186] [4.4 Regression] A loop in tree_unroll_loops_completely never ends

[rguenth at gcc dot gnu dot org]

------- Comment #11 from rguenth at gcc dot gnu dot org  2010-02-27 23:29 -------
Fixed for 4.5.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |4.4.3
      Known to work|4.4.2                       |4.3.4 4.5.0
            Summary|[4.5 Regression] A loop in  |[4.4 Regression] A loop in
                   |tree_unroll_loops_completely|tree_unroll_loops_completely
                   |never ends                  |never ends
   Target Milestone|4.5.0                       |4.4.4


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

[Bug tree-optimization/43186] [4.5 Regression] A loop in tree_unroll_loops_completely never ends

[rguenth at gcc dot gnu dot org]

------- Comment #10 from rguenth at gcc dot gnu dot org  2010-02-27 23:29 -------
Subject: Bug 43186

Author: rguenth
Date: Sat Feb 27 23:28:46 2010
New Revision: 157114

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=157114
Log:
2010-02-27  Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/43186
        * params.def (PARAM_MAX_UNROLL_ITERATIONS): New param.
        * doc/invoke.texi (max-completely-peel-loop-nest-depth): Document.
        * tree-ssa-loop-ivcanon.c (tree_unroll_loops_completely): Limit
        unroller iterations.

        * gcc.c-torture/compile/pr43186.c: Adjust testcase.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/doc/invoke.texi
    trunk/gcc/params.def
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.c-torture/compile/pr43186.c
    trunk/gcc/tree-ssa-loop-ivcanon.c


-- 


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

[Bug tree-optimization/43186] [4.4 Regression] A loop in tree_unroll_loops_completely never ends

[rguenth at gcc dot gnu dot org]

------- Comment #12 from rguenth at gcc dot gnu dot org  2010-04-08 10:47 -------
Fixed.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


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

[Bug tree-optimization/43186] [4.4 Regression] A loop in tree_unroll_loops_completely never ends

[rguenth at gcc dot gnu dot org]

------- Comment #13 from rguenth at gcc dot gnu dot org  2010-04-08 10:47 -------
Subject: Bug 43186

Author: rguenth
Date: Thu Apr  8 10:46:46 2010
New Revision: 158114

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=158114
Log:
2010-04-08  Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/43186
        * params.def (PARAM_MAX_UNROLL_ITERATIONS): New param.
        * doc/invoke.texi (max-completely-peel-loop-nest-depth): Document.
        * tree-ssa-loop-ivcanon.c (tree_unroll_loops_completely): Limit
        unroller iterations.

        * gcc.c-torture/compile/pr43186.c: New testcase.

Added:
    branches/gcc-4_4-branch/gcc/testsuite/gcc.c-torture/compile/pr43186.c
Modified:
    branches/gcc-4_4-branch/gcc/ChangeLog
    branches/gcc-4_4-branch/gcc/doc/invoke.texi
    branches/gcc-4_4-branch/gcc/params.def
    branches/gcc-4_4-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_4-branch/gcc/tree-ssa-loop-ivcanon.c


-- 


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

[Bug tree-optimization/43186] [4.4 Regression] A loop in tree_unroll_loops_completely never ends

[hubicka at gcc dot gnu dot org]

------- Comment #14 from hubicka at gcc dot gnu dot org  2010-04-08 13:14 -------
Adding a simple limit on number of loop nests in recursive inlining is easy
thing to do, but I am not quite sure how useful it is (well, overall recursive
inlining tends to help only few very special benchmrks).
So the problem is that function body after inlinng is resonable but with
unrolling it explodes?


-- 


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

[Bug tree-optimization/43186] [4.4 Regression] A loop in tree_unroll_loops_completely never ends

[rguenth at gcc dot gnu dot org]

------- Comment #15 from rguenth at gcc dot gnu dot org  2010-04-08 13:19 -------
(In reply to comment #14)
> Adding a simple limit on number of loop nests in recursive inlining is easy
> thing to do, but I am not quite sure how useful it is (well, overall recursive
> inlining tends to help only few very special benchmrks).
> So the problem is that function body after inlinng is resonable but with
> unrolling it explodes?

The main issue is that we are doing a very poor job in limiting the work
we do during complete unrolling (as well as leaving as little work for
subsequent passes as possible).


-- 

rguenth at gcc dot gnu dot org changed:

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


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

[Bug tree-optimization/43186] [4.4 Regression] A loop in tree_unroll_loops_completely never ends

[hubicka at ucw dot cz]

------- Comment #16 from hubicka at ucw dot cz  2010-04-08 13:26 -------
Subject: Re:  [4.4 Regression] A loop in
        tree_unroll_loops_completely never ends

> The main issue is that we are doing a very poor job in limiting the work
> we do during complete unrolling (as well as leaving as little work for
> subsequent passes as possible).

Well, I guess in addition to number of instructions after optimizing we can
also estimate number of instruction we actually produce by unrolling and have
some cutoff (a lot bigger than for code size estimate growth) on those as
well...

Honza


-- 


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

[Bug tree-optimization/43186] [4.4 Regression] A loop in tree_unroll_loops_completely never ends

[rguenther at suse dot de]

------- Comment #17 from rguenther at suse dot de  2010-04-08 13:29 -------
Subject: Re:  [4.4 Regression] A loop in
 tree_unroll_loops_completely never ends

On Thu, 8 Apr 2010, hubicka at ucw dot cz wrote:

> ------- Comment #16 from hubicka at ucw dot cz  2010-04-08 13:26 -------
> Subject: Re:  [4.4 Regression] A loop in
>         tree_unroll_loops_completely never ends
> 
> > The main issue is that we are doing a very poor job in limiting the work
> > we do during complete unrolling (as well as leaving as little work for
> > subsequent passes as possible).
> 
> Well, I guess in addition to number of instructions after optimizing we can
> also estimate number of instruction we actually produce by unrolling and have
> some cutoff (a lot bigger than for code size estimate growth) on those as
> well...

We do.  But it all get's just smaller - but only after optimizing.

Richard.


-- 


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

[Bug tree-optimization/43186] [4.4 Regression] A loop in tree_unroll_loops_completely never ends

[hubicka at ucw dot cz]

------- Comment #18 from hubicka at ucw dot cz  2010-04-08 14:41 -------
Subject: Re:  [4.4 Regression] A loop in
        tree_unroll_loops_completely never ends

> > Well, I guess in addition to number of instructions after optimizing we can
> > also estimate number of instruction we actually produce by unrolling and have
> > some cutoff (a lot bigger than for code size estimate growth) on those as
> > well...
> 
> We do.  But it all get's just smaller - but only after optimizing.

Yep, we compute what will get optimized out as constant expression after full
unrolling.  I guess we need to compute both values - one with taking these into
account (i.e. estimating effect on the generated code) and one without (i.e.
estimating effect on memory and time we will blow on this) and limit both...

At least this is my "backup plan" for inliner if we ever run into case that the
heuristic will blow up out of time and space by giving something that optimizes
very well subsequently.

I can play with this if this seems sane. (as I guess my unrolling estimate
improvements are source of this issue)

Honza


-- 


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

[Bug tree-optimization/43186] [4.4 Regression] A loop in tree_unroll_loops_completely never ends

[matz at gcc dot gnu dot org]

------- Comment #19 from matz at gcc dot gnu dot org  2010-04-08 14:50 -------
This seems rather like a hack for our not-so-capable loop unroller.  The
estimator already correctly knows that much of it will be optimized away,
hence it would make more sense for the code emitter to also not emit
useless things that the estimator already knows will be optimized away.

It seems backward to have an additional limit on "compile time/memory need"
for a transformation that we know will succeed.


-- 


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