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.