[Bug c++/41371] New: compiler hang for C++ code

[Bug c++/41371] New: compiler hang for C++ code

[dcb314 at hotmail dot com]

I just tried to compile the Suse Linux package krename-3.9.3-1.33
with the gcc 4.5 mainline snapshot 20090910
and the compiler appeared to hang for over half an hour on
an otherwise idle machine.

Preprocessed C++ source attached. Flags -O2 -g -m64 required.


-- 
           Summary: compiler hang for C++ code
           Product: gcc
           Version: 4.5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: dcb314 at hotmail dot com
  GCC host triplet: x86_64-suse-linux


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

[Bug c++/41371] compiler hang for C++ code

[dcb314 at hotmail dot com]

------- Comment #1 from dcb314 at hotmail dot com  2009-09-16 09:19 -------
Created an attachment (id=18594)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=18594&action=view)
C++ source code


-- 


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

[Bug rtl-optimization/41371] [4.5 Regression] compiler hang for C++ code

[rguenth at gcc dot gnu dot org]

------- Comment #2 from rguenth at gcc dot gnu dot org  2009-09-16 09:54 -------
it's var-tracking again.  Slowly eating memory and time.  Working very hard
here:

Run till exit from #0  vt_find_locations ()
    at /space/rguenther/src/svn/trunk/gcc/var-tracking.c:5467


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |aoliva at gcc dot gnu dot
                   |                            |org
             Status|UNCONFIRMED                 |NEW
          Component|c++                         |rtl-optimization
     Ever Confirmed|0                           |1
           Keywords|                            |compile-time-hog, memory-hog
   Last reconfirmed|0000-00-00 00:00:00         |2009-09-16 09:54:02
               date|                            |
            Summary|compiler hang for C++ code  |[4.5 Regression] compiler
                   |                            |hang for C++ code
   Target Milestone|---                         |4.5.0


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

[Bug rtl-optimization/41371] [4.5 Regression] compiler hang for C++ code

[rguenth at gcc dot gnu dot org]

-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1


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

[Bug debug/41371] [4.5 Regression] -g causes compiler to hang

[rguenth at gcc dot gnu dot org]

------- Comment #3 from rguenth at gcc dot gnu dot org  2009-10-18 18:00 -------
Reconfirmed.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2009-09-16 09:54:02         |2009-10-18 18:00:22
               date|                            |


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

[Bug debug/41371] [4.5 Regression] -g causes compiler to hang

[jakub at gcc dot gnu dot org]

------- Comment #4 from jakub at gcc dot gnu dot org  2009-11-04 15:34 -------
Created an attachment (id=18964)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=18964&action=view)
qmc2main.ii.bz2

Another testcase where var-tracking takes almost forever on setupUi on
x86_64-linux with -g -O2.


-- 


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

[Bug debug/41371] [4.5 Regression] -g causes compiler to hang

[dcb314 at hotmail dot com]

------- Comment #5 from dcb314 at hotmail dot com  2009-12-05 12:50 -------
(In reply to comment #3)
> Reconfirmed.

It seems to be still broken in snapshot 20091203


-- 


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

[Bug debug/41371] [4.5 Regression] -g causes compiler to hang

[rguenth at gcc dot gnu dot org]

------- Comment #6 from rguenth at gcc dot gnu dot org  2009-12-13 22:18 -------
*** Bug 41264 has been marked as a duplicate of this bug. ***


-- 

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=41371

[Bug debug/41371] [4.5 Regression] -g causes compiler to hang

[rguenth at gcc dot gnu dot org]

------- Comment #7 from rguenth at gcc dot gnu dot org  2009-12-13 22:18 -------
Another testcase is attached to PR41264.


-- 


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

[Bug debug/41371] [4.5 Regression] var-tracking is slow and memory hungry

[jakub at gcc dot gnu dot org]

------- Comment #8 from jakub at gcc dot gnu dot org  2010-01-02 15:05 -------
*** Bug 42565 has been marked as a duplicate of this bug. ***


-- 

jakub at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |aanisimov at inbox dot ru


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

[Bug debug/41371] [4.5 Regression] var-tracking is slow and memory hungry

[jakub at gcc dot gnu dot org]

------- Comment #9 from jakub at gcc dot gnu dot org  2010-01-05 22:30 -------
Created an attachment (id=19478)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=19478&action=view)
vta-limit-on-size.patch

While Alex is busy working on speeding up var-tracking on these KDE testcases,
here is a temporary workaround, just giving up on -fvar-tracking-assignments
if var-tracking would need too much memory/would take too long, and giving up
on -fvar-tracking altogether if even that didn't help.
5000000 is something I came up from playing with cc1files on x86_64-linux with
-O2 -g or -O3 -g.  There is one generated routine in GCC which needs 10000000
(recog_35 in the cc1files I have), otherwise all of SPEC2K, MICO, FF3D, rest of
GCC, TRAMP3D etc. need always below 5mil (just tramp3d and one routine in ff3d
is approaching it).  Using 10mil is too much for the second testcase in this
PR, had to break the build after 27 minutes.  But with the 5mil limit it was
quite quick.


-- 


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

[Bug debug/41371] [4.5 Regression] var-tracking is slow and memory hungry

[jakub at gcc dot gnu dot org]

------- Comment #10 from jakub at gcc dot gnu dot org  2010-01-11 18:23 -------
I've looked briefly at the #c4 testcase, and the problem seems to be extremely
long loc_chains.  var-tracking e.g. stops for huge amount of time (many
minutes) on one bb, EH pad with 162 incoming EH edges (and no others).  Each of
those 162 incoming EH edges has roughly 1800 vars in its out hash table, with
just one problematic one - which has around 650 items in
var->var_part[0].loc_chain chain.  There are ~ 2 other vars with loc_chain
chain lengths in the 40s and the rest is with chain length below 10.  The CPU
eater is intersect_loc_chains.
For each of the 650 loc_chain entries it calls find_loc_in_1pdv, which, as the
vast majority of the entries in s2var's loc_chain are VALUEs, looks stuff up in
the hash table and recurses.

I wonder whether for large loc_chain lengths we just couldn't use a temporary
hash table.  If we see in intersect_loc_chains that chain length is beyond
certain threshold, populate a temporary hash table by doing what
find_loc_in_1pdv does (except instead of rtx_equal_p and returning early it
seeing a match it would record each loc into the hash table and continue
walking).  Then intersect_loc_chains could just walk this hash table instead of
searching through it again and again, avoiding the O(loc_chain_length^2)
complexity.


-- 


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

[Bug debug/41371] [4.5 Regression] var-tracking is slow and memory hungry

[rguenth at gcc dot gnu dot org]

------- Comment #11 from rguenth at gcc dot gnu dot org  2010-01-12 09:09 -------
(In reply to comment #10)
> I've looked briefly at the #c4 testcase, and the problem seems to be extremely
> long loc_chains.  var-tracking e.g. stops for huge amount of time (many
> minutes) on one bb, EH pad with 162 incoming EH edges (and no others).  Each of
> those 162 incoming EH edges has roughly 1800 vars in its out hash table, with
> just one problematic one - which has around 650 items in
> var->var_part[0].loc_chain chain.  There are ~ 2 other vars with loc_chain
> chain lengths in the 40s and the rest is with chain length below 10.  The CPU
> eater is intersect_loc_chains.
> For each of the 650 loc_chain entries it calls find_loc_in_1pdv, which, as the
> vast majority of the entries in s2var's loc_chain are VALUEs, looks stuff up in
> the hash table and recurses.
> 
> I wonder whether for large loc_chain lengths we just couldn't use a temporary
> hash table.  If we see in intersect_loc_chains that chain length is beyond
> certain threshold, populate a temporary hash table by doing what
> find_loc_in_1pdv does (except instead of rtx_equal_p and returning early it
> seeing a match it would record each loc into the hash table and continue
> walking).  Then intersect_loc_chains could just walk this hash table instead of
> searching through it again and again, avoiding the O(loc_chain_length^2)
> complexity.

That sounds like a good idea.


-- 


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

[Bug debug/41371] [4.5 Regression] var-tracking is slow and memory hungry

[jakub at gcc dot gnu dot org]

------- Comment #12 from jakub at gcc dot gnu dot org  2010-01-12 12:58 -------
It is actually far worse on this testcase, as with all the recursions
find_loc_in_1pdv does we actually must scan many values many times.
I've put a counter and on this bb one outermost find_loc_in_1pdv calls together
rtx_equal_p roughly 880000 times, times 650.
So, perhaps even just not resetting VALUE_RECURSED_INTO back immediately, but
in a second loop afterwards would be enough to make this manageable.


-- 


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

[Bug debug/41371] [4.5 Regression] var-tracking is slow and memory hungry

[jakub at gcc dot gnu dot org]

------- Comment #13 from jakub at gcc dot gnu dot org  2010-01-12 17:00 -------
Created an attachment (id=19564)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=19564&action=view)
gcc45-pr41371.patch

Patch that speeds up the qmc2main.ii testcase to bearable compile time (2m20s
on my box with -g -O2).  With -g0 -O2 it compiles in 45s, so var-tracking still
dominates the time, but it is no longer so slow.
I'll bootstrap/regtest it now.


-- 

jakub at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |jakub at gcc dot gnu dot org
                   |dot org                     |
             Status|NEW                         |ASSIGNED


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

[Bug debug/41371] [4.5 Regression] var-tracking is slow and memory hungry

[jakub at gcc dot gnu dot org]

------- Comment #14 from jakub at gcc dot gnu dot org  2010-01-13 13:27 -------
Subject: Bug 41371

Author: jakub
Date: Wed Jan 13 13:26:47 2010
New Revision: 155858

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=155858
Log:
        PR debug/41371
        * var-tracking.c (values_to_unmark): New variable.
        (find_loc_in_1pdv): Clear VALUE_RECURSED_INTO of values in
        values_to_unmark vector.  Moved body to...
        (find_loc_in_1pdv_1): ... this.  Don't clear VALUE_RECURSED_INTO,
        instead queue it into values_to_unmark vector.
        (vt_find_locations): Free values_to_unmark vector.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/var-tracking.c


-- 


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

[Bug debug/41371] [4.5 Regression] var-tracking is slow and memory hungry

[jakub at gcc dot gnu dot org]

------- Comment #15 from jakub at gcc dot gnu dot org  2010-01-19 09:03 -------
This patch seems to fix issues with (most of) KDE testcases, but there are
still some testcases where gcc spends very long time in var-tracking (usually
generated huge routines where simply too many VALUEs are tracked through).
E.g. https://bugzilla.redhat.com/show_bug.cgi?id=548826 and
https://bugzilla.redhat.com/show_bug.cgi?id=531218
These can be worked around by the #c9 patch, even with much bigger default
(50mil).

Not sure if we should track this all in this bug, or just split into separate
bugs.


-- 

jakub at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|jakub at gcc dot gnu dot org|unassigned at gcc dot gnu
                   |                            |dot org
             Status|ASSIGNED                    |NEW


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

[Bug debug/41371] [4.5 Regression] var-tracking is slow and memory hungry

[l dot lunak at suse dot cz]

------- Comment #16 from l dot lunak at suse dot cz  2010-02-16 12:47 -------
Created an attachment (id=19887)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=19887&action=view)
testcase from kdesdk/umbrello

If it helps, here's another testcase where 2G RAM is not enough. This is "g++
(SUSE Linux) 4.5.0 20100212 (experimental) [trunk revision 156733]" on x86_64
with -g -O2.


-- 


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

[Bug debug/41371] [4.5 Regression] var-tracking is slow and memory hungry

[jakub at gcc dot gnu dot org]

------- Comment #17 from jakub at gcc dot gnu dot org  2010-02-16 13:06 -------
You should retry with r156794 or newer.


-- 


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

[Bug debug/41371] [4.5 Regression] var-tracking is slow and memory hungry

[aoliva at gcc dot gnu dot org]

------- Comment #18 from aoliva at gcc dot gnu dot org  2010-03-06 20:26 -------
Subject: Bug 41371

Author: aoliva
Date: Sat Mar  6 20:26:15 2010
New Revision: 157257

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=157257
Log:
* var-tracking.c (dataflow_set_merge): Swap src and src2.
Reverted:
2010-01-13  Jakub Jelinek  <jakub@redhat.com>
PR debug/41371
* var-tracking.c (values_to_unmark): New variable.
(find_loc_in_1pdv): Clear VALUE_RECURSED_INTO of values in
values_to_unmark vector.  Moved body to...
(find_loc_in_1pdv_1): ... this.  Don't clear VALUE_RECURSED_INTO,
instead queue it into values_to_unmark vector.
(vt_find_locations): Free values_to_unmark vector.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/var-tracking.c


-- 


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

[Bug debug/41371] [4.5 Regression] var-tracking is slow and memory hungry

[jakub at gcc dot gnu dot org]

------- Comment #19 from jakub at gcc dot gnu dot org  2010-03-15 15:12 -------
A variant of the #c9 patch is checked in for many days, do you still have
something where VTA is really so big compile time or memory hog (besides
PR43058)?


-- 

jakub at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |WAITING


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

[Bug debug/41371] [4.5 Regression] var-tracking is slow and memory hungry

[rguenth at gcc dot gnu dot org]

------- Comment #20 from rguenth at gcc dot gnu dot org  2010-03-15 15:20 -------
*** Bug 42911 has been marked as a duplicate of this bug. ***


-- 


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

[Bug debug/41371] [4.5 Regression] var-tracking is slow and memory hungry

[jakub at gcc dot gnu dot org]

------- Comment #21 from jakub at gcc dot gnu dot org  2010-03-18 20:36 -------
Assuming this is fixed.  If you have a new testcase, please file a new PR.


-- 

jakub at gcc dot gnu dot org changed:

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


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

[Bug debug/41371] [4.5 Regression] var-tracking is slow and memory hungry

[dcb314 at hotmail dot com]

------- Comment #22 from dcb314 at hotmail dot com  2010-05-16 10:21 -------
(In reply to comment #21)
> Assuming this is fixed.  If you have a new testcase, please file a new PR.

I am not sure that my original bug report is fixed.

I tried 4.6 snapshot 20100515 and it couldn't compile it in ten minutes
(ulimit -t 600) on a 2.7GHz Athlon.


-- 

dcb314 at hotmail dot com changed:

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


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

[Bug debug/41371] [4.5/4.6 Regression] var-tracking is slow and memory hungry

[rguenth at gcc dot gnu dot org]

------- Comment #23 from rguenth at gcc dot gnu dot org  2010-05-16 10:49 -------
I see

 variable tracking     : 734.06 (99%) usr   0.33 (35%) sys 735.29 (99%) wall  
11548 kB ( 8%) ggc
...

743.18user 1.00system 12:25.12elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+10440outputs (0major+116553minor)pagefaults 0swaps

for bug90.cc at -O2 -g with 4.5 branch r158342.

Which is a 6800% regression over 4.4.3:

10.88user 0.62system 0:12.64elapsed 90%CPU (0avgtext+0avgdata 0maxresident)k
18664inputs+5096outputs (106major+55648minor)pagefaults 0swaps


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P1                          |P2
   Last reconfirmed|2009-10-18 18:00:22         |2010-05-16 10:49:29
               date|                            |
            Summary|[4.5 Regression] var-       |[4.5/4.6 Regression] var-
                   |tracking is slow and memory |tracking is slow and memory
                   |hungry                      |hungry
   Target Milestone|4.5.0                       |4.5.1


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

[Bug debug/41371] [4.5/4.6 Regression] var-tracking is slow and memory hungry

[pluto at agmk dot net]

------- Comment #24 from pluto at agmk dot net  2010-05-16 12:22 -------
*** Bug 43776 has been marked as a duplicate of this bug. ***


-- 

pluto at agmk dot net changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pluto at agmk dot net


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

[Bug debug/41371] [4.5/4.6 Regression] var-tracking is slow and memory hungry

[pluto at agmk dot net]

------- Comment #25 from pluto at agmk dot net  2010-05-16 12:26 -------
PR43776 constains another thestcase:

results for top of 4.5/4.6:

$ time g++45 -Wall -c 1.ii -O1 -g2
1.ii: In member function 'void es::ClockAnalyzer::initPrimitives()':
1.ii:38722:7: note: variable tracking size limit exceeded with
-fvar-tracking-assignments, retrying without
g++45 -Wall -c 1.ii -O1 -g2  32,72s user 0,35s system 99% cpu 33,096 total

$ time g++46 -Wall -c 1.ii -O1 -g2
1.ii: In member function 'void es::ClockAnalyzer::initPrimitives()':
1.ii:38722:7: note: variable tracking size limit exceeded with
-fvar-tracking-assignments, retrying without
g++46 -Wall -c 1.ii -O1 -g2  23,68s user 0,40s system 99% cpu 24,099 total

btw. the '-O1 -fno-inline -g2' has worse results.


-- 


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

[Bug debug/41371] [4.5/4.6 Regression] var-tracking is slow and memory hungry

[rguenth at gcc dot gnu dot org]

------- Comment #26 from rguenth at gcc dot gnu dot org  2010-05-17 14:28 -------
The problem from comment #12 seems to be back.


-- 


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

[Bug debug/41371] [4.5/4.6 Regression] var-tracking is slow and memory hungry

[jakub at gcc dot gnu dot org]

------- Comment #27 from jakub at gcc dot gnu dot org  2010-05-18 09:36 -------
Subject: Bug 41371

Author: jakub
Date: Tue May 18 09:35:52 2010
New Revision: 159528

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=159528
Log:
        PR debug/41371
        * var-tracking.c (find_loc_in_1pdv): Add a few checks from
        rtx_equal_p inline.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/var-tracking.c


-- 


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

[Bug debug/41371] [4.5/4.6 Regression] var-tracking is slow and memory hungry

[jakub at gcc dot gnu dot org]

------- Comment #28 from jakub at gcc dot gnu dot org  2010-05-25 10:39 -------
Created an attachment (id=20741)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=20741&action=view)
gcc46-pr41371.patch

Another small optimization.  At least on this testcase in 80% the s1node and
s2var->var_part[0].loc_chain chains contain the same locations in the same
order.  So, if we avoid calling find_loc_in_1pdv in that case and only start
calling it when they differ, the testcase can be speeded up slightly.
With --enable-checking=release cc1plus the difference is:
real    4m52.484s
user    4m51.991s
sys     0m0.446s

to:

real    3m38.218s
user    3m37.641s
sys     0m0.383s

I'm going to bootstrap/regtest it now with additional statistics gathering on
how many find_loc_in_1pdv calls it can avoid.


-- 


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

[Bug debug/41371] [4.5/4.6 Regression] var-tracking is slow and memory hungry

[jakub at gcc dot gnu dot org]

------- Comment #29 from jakub at gcc dot gnu dot org  2010-05-25 16:27 -------
Subject: Bug 41371

Author: jakub
Date: Tue May 25 16:27:03 2010
New Revision: 159829

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=159829
Log:
        PR debug/41371
        * var-tracking.c (find_loc_in_1pdv): Guard asserts with
        ENABLE_CHECKING.
        (intersect_loc_chains): Walk the s2var's loc_chain together
        with s1node chain as long as the locations are equal, don't
        call find_loc_in_1pdv in that case.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/var-tracking.c


-- 


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

[Bug debug/41371] [4.5/4.6 Regression] var-tracking is slow and memory hungry

[jakub at gcc dot gnu dot org]

------- Comment #30 from jakub at gcc dot gnu dot org  2010-06-04 09:02 -------
Created an attachment (id=20833)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=20833&action=view)
rh598310.i.bz2

Another testcase from wine,
./cc1 -m32 -fPIC -fno-strict-aliasing -g -O2 rh598310.i -quiet
takes here over 7 minutes, again most of the time spent in find_loc_in_1pdv
called from intersect_loc_chains.


-- 


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

[Bug debug/41371] [4.5/4.6 Regression] var-tracking is slow and memory hungry

[jakub at gcc dot gnu dot org]

------- Comment #31 from jakub at gcc dot gnu dot org  2010-06-04 09:24 -------
Created an attachment (id=20834)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=20834&action=view)
limit-depth.patch

Quick patch that brings the time down to 1 minute 15 sec.

>From the callgrind dump on this testcase, intersect_loc_chains in 5159260x
cases calls insert_into_intersection in the first loop (i.e. where the recent
patch from this PR helps), then calls 320611x find_loc_in_1pdv.  Out of these
calls, 75537x it returns NULL and the rest of time it returns non-NULL.  When
it returns non-NULL, it is possible to return non-NULL without recursion
244863x, with one level of find_loc_in_1pdv recursion 205x and with two level
recursion 6x.  No successful call in this testcase needs deeper recursion.
When not limiting the recursion depth, instead just monitoring it, for all
cases where find_loc_in_1pdv returned non-NULL the depth at which return node;
is used
is at most 2 (0 is just find_loc_in_1pdv call with no recursion) and maximum
depth ever recursed for the successful calls is 3.  I believe the problem of
this testcase is not the cases where find_loc_in_1pdv returns non-NULL.


-- 


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

[Bug debug/41371] [4.5/4.6 Regression] var-tracking is slow and memory hungry

[jakub at gcc dot gnu dot org]

------- Comment #32 from jakub at gcc dot gnu dot org  2010-06-04 09:30 -------
Created an attachment (id=20835)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=20835&action=view)
hack

Hack that shows that the maximum depth is 3 even for the found == NULL cases.
Alex tells me on IRC he has the right fix for this.


-- 


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

[Bug debug/41371] [4.5/4.6 Regression] var-tracking is slow and memory hungry

[aoliva at gcc dot gnu dot org]

------- Comment #33 from aoliva at gcc dot gnu dot org  2010-06-04 09:51 -------
Mine


-- 

aoliva at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |aoliva at gcc dot gnu dot
                   |dot org                     |org
             Status|REOPENED                    |ASSIGNED


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

[Bug debug/41371] [4.5/4.6 Regression] var-tracking is slow and memory hungry

[aoliva at gcc dot gnu dot org]

------- Comment #34 from aoliva at gcc dot gnu dot org  2010-06-04 10:03 -------
Created an attachment (id=20836)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=20836&action=view)
Patch that fixes the bug and verifies recursion is bounded as expected

This patch (except for comments and ChangeLog) completed stage1 libs, more
testing needed.


-- 


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

[Bug debug/41371] [4.5/4.6 Regression] var-tracking is slow and memory hungry

[rguenth at gcc dot gnu dot org]

------- Comment #35 from rguenth at gcc dot gnu dot org  2010-06-04 11:03 -------
Created an attachment (id=20837)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=20837&action=view)
bnc611650

Another testcase from open-office this time, on i?86-linux only.

$> time  g++ -c -g -Os -fomit-frame-pointer analysis.ii

real    103m46.642s
user    96m21.093s
sys     0m1.196s

$> time g++ -c -g -Os analysis.ii

real    0m19.345s
user    0m19.177s
sys     0m0.168s

$> time  g++ -c -Os -fomit-frame-pointer analysis.ii

real    0m3.747s
user    0m3.640s
sys     0m0.104s

numbers above are from the 4.5 branch rev. 159866.  trunk is also very slow,
but the compile didn't yet finish.


-- 


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

[Bug debug/41371] [4.5/4.6 Regression] var-tracking is slow and memory hungry

[jakub at gcc dot gnu dot org]

------- Comment #36 from jakub at gcc dot gnu dot org  2010-06-04 11:15 -------
With Alex' patch with checking guarded with #ifdef ENABLE_CHECKING (currently
bootstrapping/regtesting that) I see on x86_64 on the trunk:
time ./cc1plus -m32 -quiet -g -Os -fomit-frame-pointer bug-611650_analysis.ii 

real    2m16.789s
user    2m16.333s
sys     0m0.276s

Of course not ideal, but much better than those 103 minutes.


-- 


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

[Bug debug/41371] [4.5/4.6 Regression] var-tracking is slow and memory hungry

[rguenth at gcc dot gnu dot org]

------- Comment #37 from rguenth at gcc dot gnu dot org  2010-06-04 12:45 -------
Subject: Bug 41371

Author: rguenth
Date: Fri Jun  4 12:44:41 2010
New Revision: 160261

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

        Backport from mainline:
        2010-05-18  Jakub Jelinek  <jakub@redhat.com>

        PR debug/41371
        * var-tracking.c (find_loc_in_1pdv): Add a few checks from
        rtx_equal_p inline.

        2010-05-25  Jakub Jelinek  <jakub@redhat.com>

        PR debug/41371
        * var-tracking.c (find_loc_in_1pdv): Guard asserts with
        ENABLE_CHECKING.
        (intersect_loc_chains): Walk the s2var's loc_chain together
        with s1node chain as long as the locations are equal, don't
        call find_loc_in_1pdv in that case.

Modified:
    branches/gcc-4_5-branch/gcc/ChangeLog
    branches/gcc-4_5-branch/gcc/var-tracking.c


-- 


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

[Bug debug/41371] [4.5/4.6 Regression] var-tracking is slow and memory hungry

[jakub at gcc dot gnu dot org]

------- Comment #38 from jakub at gcc dot gnu dot org  2010-06-04 16:42 -------
Subject: Bug 41371

Author: jakub
Date: Fri Jun  4 16:42:27 2010
New Revision: 160280

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=160280
Log:
        PR debug/41371
        * var-tracking.c (find_loc_in_1pdv): Mark initial value before
        recursing.  Check that recursion is bounded.  Rename inner var
        to avoid hiding incoming argument.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/var-tracking.c


-- 


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

[Bug debug/41371] [4.5/4.6 Regression] var-tracking is slow and memory hungry

[jakub at gcc dot gnu dot org]

------- Comment #39 from jakub at gcc dot gnu dot org  2010-06-04 16:48 -------
Subject: Bug 41371

Author: jakub
Date: Fri Jun  4 16:47:41 2010
New Revision: 160282

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=160282
Log:
        PR debug/41371
        * var-tracking.c (find_loc_in_1pdv): Mark initial value before
        recursing.  Check that recursion is bounded.  Rename inner var
        to avoid hiding incoming argument.

Modified:
    branches/gcc-4_5-branch/gcc/ChangeLog
    branches/gcc-4_5-branch/gcc/var-tracking.c


-- 


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

[Bug debug/41371] [4.5/4.6 Regression] var-tracking is slow and memory hungry

[aoliva at gcc dot gnu dot org]

------- Comment #40 from aoliva at gcc dot gnu dot org  2010-06-09 04:56 -------
Fixed


-- 

aoliva at gcc dot gnu dot org changed:

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


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

[Bug debug/41371] [4.5/4.6 Regression] var-tracking is slow and memory hungry

[aoliva at gcc dot gnu dot org]

------- Comment #41 from aoliva at gcc dot gnu dot org  2010-06-10 16:44 -------
Subject: Bug 41371

Author: aoliva
Date: Thu Jun 10 16:43:46 2010
New Revision: 160559

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=160559
Log:
PR debug/41371
* var-tracking.c (find_loc_in_1pdv): Remove recursion, only
tail-recurse into canonical node.  Fast-forward over
non-canonical VALUEs.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/var-tracking.c


-- 


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

[Bug debug/41371] [4.5/4.6 Regression] var-tracking is slow and memory hungry

[aoliva at gcc dot gnu dot org]

------- Comment #42 from aoliva at gcc dot gnu dot org  2010-06-10 17:01 -------
Subject: Bug 41371

Author: aoliva
Date: Thu Jun 10 17:01:32 2010
New Revision: 160563

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=160563
Log:
PR debug/41371
* var-tracking.c (find_loc_in_1pdv): Remove recursion, only
tail-recurse into canonical node.  Fast-forward over
non-canonical VALUEs.

Modified:
    branches/gcc-4_5-branch/gcc/ChangeLog
    branches/gcc-4_5-branch/gcc/var-tracking.c


-- 


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