[Bug debug/59992] New: [4.9 Regression] Compilation of insn-recog.c too slow due to var-tracking

[Bug debug/59992] New: [4.9 Regression] Compilation of insn-recog.c too slow due to var-tracking

[jakub at gcc dot gnu.org]

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

            Bug ID: 59992
           Summary: [4.9 Regression] Compilation of insn-recog.c too slow
                    due to var-tracking
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: debug
          Assignee: unassigned at gcc dot gnu.org
          Reporter: jakub at gcc dot gnu.org
                CC: aoliva at gcc dot gnu.org

#define A(n) if (p[n]) { extern void foo##n (int, int, double, int, int); \
foo##n (p[n], 5, 8.0, p[n] + p[n + 1], 9); return; }
#define B(n) A(n##0) A(n##1) A(n##2) A(n##3) A(n##4) \
A(n##5) A(n##6) A(n##7) A(n##8) A(n##9)
#define C(n) B(n##0) B(n##1) B(n##2) B(n##3) B(n##4) \
B(n##5) B(n##6) B(n##7) B(n##8) B(n##9)
#define D(n) C(n##0) C(n##1) C(n##2) C(n##3) C(n##4) \
C(n##5) C(n##6) C(n##7) C(n##8) C(n##9)
#define E(n) D(n##0) D(n##1) D(n##2) D(n##3) D(n##4) \
D(n##5) D(n##6) D(n##7) D(n##8) D(n##9)

void
foo (int *p)
{
  E(1) E(2)
}

with -O2 -m32 -g on x86_64-linux takes just a few seconds to compile with 4.8,
but on trunk 13 minutes (--enable-checking=release).  This testcase is roughly
modelled after what insn-recog.c contains when built in
--enable-checking=yes,rtl compiler, and the important change has been the
switch to -mno-accumulate-outgoing-args.  Almost all time is spent in
vt_initialize -> 
cselib_preserve_only_values -> remove_useless_values.

[Bug debug/59992] [4.9 Regression] Compilation of insn-recog.c too slow due to var-tracking

[jakub at gcc dot gnu.org]

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

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 31990
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=31990&action=edit
gcc49-pr59992.patch

Untested fix.  On the E(1) E(2) testcase in -O0 built --enable-checking=yes
cc1 it improves:
 variable tracking       :1099.23 (91%) usr   0.10 ( 3%) sys1102.71 (91%) wall 
102786 kB (13%) ggc
 var-tracking dataflow   :   2.04 ( 0%) usr   0.05 ( 2%) sys   2.09 ( 0%) wall 
     0 kB ( 0%) ggc
 var-tracking emit       :   0.23 ( 0%) usr   0.00 ( 0%) sys   0.22 ( 0%) wall 
  4999 kB ( 1%) ggc
to:
 variable tracking       :   2.84 ( 2%) usr   0.03 ( 1%) sys   2.88 ( 2%) wall 
109819 kB (13%) ggc
 var-tracking dataflow   :   2.08 ( 2%) usr   0.05 ( 2%) sys   2.13 ( 2%) wall 
     0 kB ( 0%) ggc
 var-tracking emit       :   0.22 ( 0%) usr   0.00 ( 0%) sys   0.22 ( 0%) wall 
  4999 kB ( 1%) ggc
and on the slightly reduced testcase in the patch (just E(1), i.e. half the
number of basic blocks):
 variable tracking       : 265.96 (85%) usr   0.16 (14%) sys 267.11 (84%) wall 
 51380 kB (12%) ggc
 var-tracking dataflow   :   1.93 ( 1%) usr   0.03 ( 3%) sys   1.98 ( 1%) wall 
     0 kB ( 0%) ggc
 var-tracking emit       :   0.11 ( 0%) usr   0.00 ( 0%) sys   0.11 ( 0%) wall 
  2499 kB ( 1%) ggc
to:
 variable tracking       :   1.55 ( 3%) usr   0.02 ( 2%) sys   1.56 ( 3%) wall 
 54897 kB (13%) ggc
 var-tracking dataflow   :   2.00 ( 4%) usr   0.05 ( 5%) sys   2.05 ( 4%) wall 
     0 kB ( 0%) ggc
 var-tracking emit       :   0.11 ( 0%) usr   0.00 ( 0%) sys   0.12 ( 0%) wall 
  2499 kB ( 1%) ggc

[Bug debug/59992] [4.9 Regression] Compilation of insn-recog.c too slow due to var-tracking

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-01-30
   Target Milestone|---                         |4.9.0
     Ever confirmed|0                           |1

[Bug debug/59992] [4.9 Regression] Compilation of insn-recog.c too slow due to var-tracking

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

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

[Bug debug/59992] [4.9 Regression] Compilation of insn-recog.c too slow due to var-tracking

[jakub at gcc dot gnu.org]

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

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Author: jakub
Date: Thu Feb  6 15:47:12 2014
New Revision: 207562

URL: http://gcc.gnu.org/viewcvs?rev=207562&root=gcc&view=rev
Log:
    PR debug/59992
    * var-tracking.c (adjust_mems): Before adding a SET
    to amd->side_effects, adjust it's SET_SRC using
    simplify_replace_fn_rtx.

    * gcc.dg/pr59992.c: New test.

Added:
    trunk/gcc/testsuite/gcc.dg/pr59992.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/var-tracking.c

[Bug debug/59992] [4.9 Regression] Compilation of insn-recog.c too slow due to var-tracking

[jakub at gcc dot gnu.org]

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

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The testcase has been fixed, but unfortunately --enable-checking=yes,rtl
insn-recog.c still takes about an hour to var-track.

[Bug debug/59992] [4.9 Regression] Compilation of insn-recog.c too slow due to var-tracking

[jakub at gcc dot gnu.org]

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

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Untested hack to generate somewhat smaller recog_* functions by dynamically
lowering the threshold if we'd see too big functions.  With this patch we get
149 recog_* functions instead of 122, and largest number of lines in one
function decreases from more than 20000 to about 9000.

--- genrecog.c.jj    2014-01-03 11:40:29.000000000 +0100
+++ genrecog.c    2014-02-10 12:21:32.547199720 +0100
@@ -1504,15 +1504,26 @@ simplify_tests (struct decision_head *he
    that is generated.  */

 static int
-break_out_subroutines (struct decision_head *head, int initial)
+break_out_subroutines (struct decision_head *head, int initial, int threshold)
 {
-  int size = 0;
+  int size = 0, t;
   struct decision *sub;

-  for (sub = head->first; sub; sub = sub->next)
-    size += 1 + break_out_subroutines (&sub->success, 0);
+  if (head->first && head->first->subroutine_number)
+    return 1;
+
+  for (t = SUBROUTINE_THRESHOLD;
+       t > SUBROUTINE_THRESHOLD / 2;
+       t -= SUBROUTINE_THRESHOLD / 10)
+    {
+      size = 0;
+      for (sub = head->first; sub; sub = sub->next)
+    size += 1 + break_out_subroutines (&sub->success, 0, t);
+      if (size < SUBROUTINE_THRESHOLD * 5)
+    break;
+    }

-  if (size > SUBROUTINE_THRESHOLD && ! initial)
+  if (size > threshold && ! initial)
     {
       head->first->subroutine_number = ++next_subroutine_number;
       size = 1;
@@ -2486,7 +2497,7 @@ process_tree (struct decision_head *head
       factor_tests (head);

       next_subroutine_number = 0;
-      break_out_subroutines (head, 1);
+      break_out_subroutines (head, 1, SUBROUTINE_THRESHOLD);
       find_afterward (head, NULL);

       /* We run this after find_afterward, because find_afterward needs

[Bug debug/59992] [4.9 Regression] Compilation of insn-recog.c too slow due to var-tracking

[jakub at gcc dot gnu.org]

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 32096
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32096&action=edit
insn-recog.ii.bz2

Preprocessed source for
-fpreprocessed insn-recog.ii -m32 -mtune=generic -march=pentiumpro -O2
-fno-exceptions -fno-rtti -fasynchronous-unwind-tables -fno-common
With --enable-checking=yes,rtl x86_64 compiler without -g it still takes 10
minutes to compile.

[Bug debug/59992] [4.9 Regression] Compilation of insn-recog.c too slow due to var-tracking

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
I think the issue for that is probably

> ./cc1plus -quiet t.ii -O2 -ftime-report -m32 -Wdisabled-optimization
../../gcc/config/i386/sync.md: In function ‘int recog_102(rtx, rtx, int*)’:
../../gcc/config/i386/sync.md:518:1: warning: const/copy propagation disabled:
34779 basic blocks and 85328 registers [-Wdisabled-optimization]
../../gcc/config/i386/sync.md:518:1: warning: PRE disabled: 34779 basic blocks
and 85328 registers [-Wdisabled-optimization]
../../gcc/config/i386/sync.md:518:1: warning: const/copy propagation disabled:
34779 basic blocks and 85328 registers [-Wdisabled-optimization]
../../gcc/config/i386/sync.md:518:1: warning: const/copy propagation disabled:
34536 basic blocks and 85329 registers [-Wdisabled-optimization]
...

so we hit the self-imposed limits in cprop/gcse which then likely makes
the compiler (the insn-recog part) very slow?

As other parts of the compiler don't turn themselves off because of DF
memory use at least the comment before this limit seems odd to me.
(the compile still uses 1.7GB of ram for me).

One issue is definitely the explicitely represented maximum set in lcm.c
compute_available (and others - but that's used by both gcse and cprop).
>From gcc-bugs-return-443202-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Mon Feb 10 12:56:00 2014
Return-Path: <gcc-bugs-return-443202-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 27062 invoked by alias); 10 Feb 2014 12:55:59 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 26996 invoked by uid 48); 10 Feb 2014 12:55:56 -0000
From: "rguenth at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug debug/59992] [4.9 Regression] Compilation of insn-recog.c too slow due to var-tracking
Date: Mon, 10 Feb 2014 12:55:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: debug
X-Bugzilla-Version: 4.9.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: rguenth at gcc dot gnu.org
X-Bugzilla-Status: NEW
X-Bugzilla-Priority: P1
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: 4.9.0
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields:
Message-ID: <bug-59992-4-yBmCP1Zi9l@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-59992-4@http.gcc.gnu.org/bugzilla/>
References: <bug-59992-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2014-02/txt/msg00959.txt.bz2
Content-length: 536

http://gcc.gnu.org/bugzilla/show_bug.cgi?idY992

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Bumping to --param max-gcse-memory@0 * 1024 * 1024 "fixes" that and we get
(as expected from non-RTL checking -ftime-report)

 CPROP                   :   4.82 ( 3%) usr   0.57 ( 8%) sys   5.61 ( 3%) wall
112174 kB ( 4%) ggc
 PRE                     :  26.88 (16%) usr   0.78 (10%) sys  27.69 (16%) wall
  4241 kB ( 0%) ggc
 TOTAL                 : 169.50             7.48           177.36
3130446 kB

[Bug debug/59992] [4.9 Regression] Compilation of insn-recog.c too slow due to var-tracking

[aoliva at gcc dot gnu.org]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset="UTF-8", Size: 2997 bytes --]

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

Alexandre Oliva <aoliva at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |aoliva at gcc dot gnu.org

--- Comment #8 from Alexandre Oliva <aoliva at gcc dot gnu.org> ---
Mine.  There are horrible quadratic inefficiencies in vt_initialize().  I've
managed to cut the “variable tracking” time down from 1700+ to 5 seconds with a
couple of patches I'm testing now, that I'll attach momentarily.
>From gcc-bugs-return-444803-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Wed Feb 26 01:12:08 2014
Return-Path: <gcc-bugs-return-444803-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 26593 invoked by alias); 26 Feb 2014 01:12:07 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 26538 invoked by uid 48); 26 Feb 2014 01:12:04 -0000
From: "aoliva at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug debug/59992] [4.9 Regression] Compilation of insn-recog.c too slow due to var-tracking
Date: Wed, 26 Feb 2014 01:12:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: debug
X-Bugzilla-Version: 4.9.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: aoliva at gcc dot gnu.org
X-Bugzilla-Status: NEW
X-Bugzilla-Priority: P1
X-Bugzilla-Assigned-To: aoliva at gcc dot gnu.org
X-Bugzilla-Target-Milestone: 4.9.0
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: attachments.created
Message-ID: <bug-59992-4-0i8j2yFPzc@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-59992-4@http.gcc.gnu.org/bugzilla/>
References: <bug-59992-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2014-02/txt/msg02560.txt.bz2
Content-length: 564

http://gcc.gnu.org/bugzilla/show_bug.cgi?idY992

--- Comment #9 from Alexandre Oliva <aoliva at gcc dot gnu.org> ---
Created attachment 32213
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id2213&actioníit
avoid quadratic behavior for the removal of useless values

This is the first of the two patches; it extends the condition that protects
from quadratic behavior in dropping useless values to the second path that
calls this function.  This is enough to cut down the vt_initialize time from
over 1700 to about 500 seconds for the insn-recog testcase.

[Bug debug/59992] [4.9 Regression] Compilation of insn-recog.c too slow due to var-tracking

[aoliva at gcc dot gnu.org]

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

--- Comment #10 from Alexandre Oliva <aoliva at gcc dot gnu.org> ---
Created attachment 32214
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32214&action=edit
preserve permanent values in a separate table

vt_initialize still took way too long in the insn-recog testcase, going over
the entire table so as to preserve constants and equivalences over and over and
over.  That's silly.  Moving to a separate table everything that is permanent
avoids this complexity without significant drawbacks.  With this patch,
vt_initialize time goes down from the improved 500 seconds to 5 seconds. 
Wheee!

[Bug debug/59992] [4.9 Regression] Compilation of insn-recog.c too slow due to var-tracking

[aoliva at gcc dot gnu.org]

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

--- Comment #11 from Alexandre Oliva <aoliva at gcc dot gnu.org> ---
Author: aoliva
Date: Fri Feb 28 12:57:06 2014
New Revision: 208220

URL: http://gcc.gnu.org/viewcvs?rev=208220&root=gcc&view=rev
Log:
PR debug/59992
* cselib.c (remove_useless_values): Skip to avoid quadratic
behavior if the condition moved from...
(cselib_process_insn): ... here holds.

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

[Bug debug/59992] [4.9 Regression] Compilation of insn-recog.c too slow due to var-tracking

[aoliva at gcc dot gnu.org]

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

--- Comment #12 from Alexandre Oliva <aoliva at gcc dot gnu.org> ---
Author: aoliva
Date: Fri Feb 28 12:57:40 2014
New Revision: 208221

URL: http://gcc.gnu.org/viewcvs?rev=208221&root=gcc&view=rev
Log:
PR debug/59992
* cselib.c (cselib_hasher::equal): Special-case VALUE lookup.
(cselib_preserved_hash_table): New.
(preserve_constants_and_equivs): Move preserved vals to it.
(cselib_find_slot): Look it up first.
(cselib_init): Initialize it.
(cselib_finish): Release it.
(dump_cselib_table): Dump it.

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

[Bug debug/59992] [4.9 Regression] Compilation of insn-recog.c too slow due to var-tracking

[aoliva at gcc dot gnu.org]

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

Alexandre Oliva <aoliva at gcc dot gnu.org> changed:

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

--- Comment #13 from Alexandre Oliva <aoliva at gcc dot gnu.org> ---
Fixed

[Bug debug/59992] [4.9 Regression] Compilation of insn-recog.c too slow due to var-tracking

[aoliva at gcc dot gnu.org]

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

--- Comment #14 from Alexandre Oliva <aoliva at gcc dot gnu.org> ---
Author: aoliva
Date: Thu Mar  6 07:04:47 2014
New Revision: 208361

URL: http://gcc.gnu.org/viewcvs?rev=208361&root=gcc&view=rev
Log:
PR debug/60381
Revert:
2014-02-28  Alexandre Oliva <aoliva@redhat.com>
PR debug/59992
* cselib.c (remove_useless_values): Skip to avoid quadratic
behavior if the condition moved from...
(cselib_process_insn): ... here holds.

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