[Bug middle-end/54704] New: three-fold increase in compile-time between r191483 and r191569

[Bug middle-end/54704] New: three-fold increase in compile-time between r191483 and r191569

[rguenth at gcc dot gnu.org]

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

             Bug #: 54704
           Summary: three-fold increase in compile-time between r191483
                    and r191569
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Keywords: compile-time-hog
          Severity: normal
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: rguenth@gcc.gnu.org
                CC: bernds@gcc.gnu.org, dehao@gcc.gnu.org


http://gcc.opensuse.org/c++bench-frescobaldi/tramp3d/ shows a three-fold
compile-time increase for tramp3d between r191483 (good) and r191569 (bad).

Pretty bad I'd say.

Suspicious are:

+2012-09-19  Dehao Chen  <dehao@google.com>
+
+       * toplev.c (general_init): Init block_locations.
+       * tree.c (tree_set_block): New.
+       (tree_block): Change to use LOCATION_BLOCK.
+       * tree.h (TREE_SET_BLOCK): New.
...

and

+2012-09-19  Bernd Schmidt  <bernds@codesourcery.com>
+
+       * dbgcnt.def (sched_breakdep): New counter.
+       * haifa-sched.c (update_insn_after_change): New static function,
+       broken out of haifa_change_pattern.
+       (haifa_change_pattern): Call it.
+       (dep_t heap vecs): Declare.
+       (INSN_COST): Define earlier.
...

[Bug middle-end/54704] three-fold increase in compile-time between r191483 and r191569

[rguenth at gcc dot gnu.org]

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

--- Comment #1 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-09-25 14:07:33 UTC ---
Created attachment 28268
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=28268
testcase

Testcase.  Needs -fpermissive, for example with -O2 -funroll-loops -ffast-math.

[Bug middle-end/54704] [4.8 Regression] three-fold increase in compile-time between r191483 and r191569

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|bernds at gcc dot gnu.org   |
   Target Milestone|---                         |4.8.0
            Summary|three-fold increase in      |[4.8 Regression] three-fold
                   |compile-time between        |increase in compile-time
                   |r191483 and r191569         |between r191483 and r191569

--- Comment #2 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-09-25 14:09:37 UTC ---
 integration             :  40.95 (45%) usr   0.20 ( 6%) sys  41.31 (43%) wall 
 79770 kB ( 7%) ggc

thus the inliner (and here probably allocating new locations for the blocks)
is responsible.  With tramp3d you have around 1000 calls per assembler
instruction emitted.

[Bug middle-end/54704] [4.8 Regression] three-fold increase in compile-time between r191483 and r191569

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-09-25
     Ever Confirmed|0                           |1

--- Comment #3 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-09-25 14:37:55 UTC ---
hashtable collisions are an issue (-O1 -fpermissive, break on htab expand).
The last expansion shows:

Breakpoint 1, get_combined_adhoc_loc (set=0x7ffff7ff9000, 
    locus=<optimized out>, data=<optimized out>)
    at /space/rguenther/tramp3d/trunk/libcpp/line-map.c:139
139                                location_adhoc_data_update, &offset);
(gdb) p *set->location_adhoc_data_map.htab
$16 = {hash_f = 0xef2a50 <location_adhoc_data_hash(void const*)>, 
  eq_f = 0xef2a60 <location_adhoc_data_eq(void const*, void const*)>, 
  del_f = 0x0, entries = 0x221b650, size = 262139, n_elements = 131073, 
  n_deleted = 0, searches = 211955, collisions = 160177370, 
  alloc_f = 0xf1d320 <xcalloc>, free_f = 0x4e0570 <free@plt>, alloc_arg = 0x0, 
  alloc_with_arg_f = 0x0, free_with_arg_f = 0x0, size_prime_index = 15}

[Bug middle-end/54704] [4.8 Regression] three-fold increase in compile-time between r191483 and r191569

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-09-25 14:41:17 UTC ---
static hashval_t
location_adhoc_data_hash (const void *l)
{
  const struct location_adhoc_data *lb =
      (const struct location_adhoc_data *) l;
  return (hashval_t) lb->locus + (size_t) &lb->data;
}

should probably use something better, and not &lb->data but lb->data?
(breaks location_adhoc_data_update probably).

Deaho?

[Bug middle-end/54704] [4.8 Regression] three-fold increase in compile-time between r191483 and r191569

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-09-25 14:57:58 UTC ---
With the hash function fixed

Index: libcpp/line-map.c
===================================================================
--- libcpp/line-map.c   (revision 191706)
+++ libcpp/line-map.c   (working copy)
@@ -58,7 +58,7 @@ location_adhoc_data_hash (const void *l)
 {
   const struct location_adhoc_data *lb =
       (const struct location_adhoc_data *) l;
-  return (hashval_t) lb->locus + (size_t) &lb->data;
+  return (hashval_t) lb->locus + (size_t) lb->data;
 }

 /* Compare function for location_adhoc_data hashtable.  */

compile-time looks way better.  Needs proper testing of course.

Breakpoint 1, get_combined_adhoc_loc (set=0x7ffff7ff9000, 
    locus=<optimized out>, data=<optimized out>)
    at /space/rguenther/tramp3d/trunk/libcpp/line-map.c:139
139                                location_adhoc_data_update, &offset);
(gdb) p *set->location_adhoc_data_map.htab
$11 = {hash_f = 0xef2a50 <location_adhoc_data_hash(void const*)>, 
  eq_f = 0xef2a60 <location_adhoc_data_eq(void const*, void const*)>, 
  del_f = 0x0, entries = 0x2243410, size = 262139, n_elements = 131073, 
  n_deleted = 0, searches = 278216, collisions = 365860, 
  alloc_f = 0xf1d320 <xcalloc>, free_f = 0x4e0570 <free@plt>, alloc_arg = 0x0, 
  alloc_with_arg_f = 0x0, free_with_arg_f = 0x0, size_prime_index = 15}

and

 integration             :   0.90 ( 2%) usr   0.15 ( 4%) sys   0.99 ( 2%) wall 
 86042 kB ( 8%) ggc

[Bug middle-end/54704] [4.8 Regression] three-fold increase in compile-time between r191483 and r191569

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #6 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-09-25 15:01:47 UTC ---
Well.  Mine.

[Bug middle-end/54704] [4.8 Regression] three-fold increase in compile-time between r191483 and r191569

[dehao at google dot com]

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

Dehao Chen <dehao at google dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dehao at google dot com

--- Comment #7 from Dehao Chen <dehao at google dot com> 2012-09-25 19:34:33 UTC ---
Yes, this is bug in the hash function. Your fix should be correct, as can be
inferred from the location_adhoc_data_eq function. I'll test the patch now.

Thanks,
Dehao

[Bug middle-end/54704] [4.8 Regression] three-fold increase in compile-time between r191483 and r191569

[dehao at gcc dot gnu.org]

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

--- Comment #8 from dehao at gcc dot gnu.org 2012-09-25 21:32:39 UTC ---
Author: dehao
Date: Tue Sep 25 21:32:29 2012
New Revision: 191747

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=191747
Log:
libcpp:
    2012-09-25  Dehao Chen  <dehao@google.com>

    PR middle-end/54704
    * line-map.c (location_adhoc_data_hash): Fix the hash function.


Modified:
    trunk/libcpp/ChangeLog
    trunk/libcpp/line-map.c

[Bug middle-end/54704] [4.8 Regression] three-fold increase in compile-time between r191483 and r191569

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #9 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-09-26 09:03:31 UTC ---
Fixed.