[Bug pch/53880] [4.8 Regression] compile time regression when generating precompiled headers for boost

["steven at gcc dot gnu.org" <gcc-bugzilla at gcc dot gnu dot org>]

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

--- Comment #27 from Steven Bosscher <steven at gcc dot gnu.org> 2012-07-30 13:51:58 UTC ---
The problem is the quadratic behavior invoked by the loop in
gt_pch_nx_line_maps:
      {
        size_t l2 = (size_t)(((*x).info_macro).used);
        if ((*x).info_macro.maps != NULL) {
          size_t i2;
          for (i2 = 0; i2 != (size_t)(l2); i2++) {
            switch (((*x).info_macro.maps[i2]).reason == LC_ENTER_MACRO)
              {
              case 0:
                gt_pch_n_S ((*x).info_macro.maps[i2].d.ordinary.to_file);
                break;
              case 1:
                {
                  union tree_node * const x3 =
                    ((*x).info_macro.maps[i2].d.macro.macro) ?
HT_IDENT_TO_GCC_IDENT (HT_NODE (((*x).info_macro.maps[i2].d.macro.macro))) :
NULL;
                  gt_pch_n_9tree_node (x3);
                }
                if ((*x).info_macro.maps[i2].d.macro.macro_locations != NULL) {
                  gt_pch_note_object
((*x).info_macro.maps[i2].d.macro.macro_locations, x, gt_pch_p_9line_maps,
gt_types_enum_last);
                }
                break;
              default:
                break;
              }
          }

and the loop in gt_pch_p_9line_maps:

    size_t l2 = (size_t)(((*x).info_macro).used);
    if ((*x).info_macro.maps != NULL) {
      size_t i2;
      for (i2 = 0; i2 != (size_t)(l2); i2++) {
        switch (((*x).info_macro.maps[i2]).reason == LC_ENTER_MACRO)
          {
          case 0:
            if ((void *)((*x).info_macro.maps) == this_obj)
              op (&((*x).info_macro.maps[i2].d.ordinary.to_file), cookie);
            break;
          case 1:
            {
              union tree_node * x3 =
                ((*x).info_macro.maps[i2].d.macro.macro) ?
HT_IDENT_TO_GCC_IDENT (HT_NODE (((*x).info_macro.maps[i2].d.macro.macro))) :
NULL;
              if ((void *)((*x).info_macro.maps) == this_obj)
                op (&(x3), cookie);
              (*x).info_macro.maps[i2].d.macro.macro = (x3) ? CPP_HASHNODE
(GCC_IDENT_TO_HT_IDENT ((x3))) : NULL;
            }
            if ((*x).info_macro.maps[i2].d.macro.macro_locations != NULL) {
              if ((void *)((*x).info_macro.maps) == this_obj)
                op (&((*x).info_macro.maps[i2].d.macro.macro_locations),
cookie);
            }
            break;
          default:
            break;
          }
      }


The first loop registers every line map entry to be visited for pointer
rewriting later by gt_pch_p_9line_maps:

gt_pch_note_object ((*x).info_macro.maps[i2].d.macro.macro_locations, x,
gt_pch_p_9line_maps, gt_types_enum_last);

where x==input.c:line_table, and
(*x).info_macro.maps[i2].d.macro.macro_locations is the "i2"'th entry.

The second loop is called from the loop in gt_pch_save via note_ptr_fn, which
is gt_pch_p_9line_maps:

      state.ptrs[i]->note_ptr_fn (state.ptrs[i]->obj,
                                  state.ptrs[i]->note_ptr_cookie,
                                  relocate_ptrs, &state);
==
       gt_pch_p_9line_maps((*x).info_macro.maps[i2].d.macro.macro_locations,
                           &line_table, relocate_ptrs, &state);

and gt_pch_p_9line_maps loops over all map elements until:
  (void *)((*x).info_macro.maps) == this_obj

This causes (((*x).info_macro).used)**2 visits.