The test case for 17340 exposes quadratic behavior caused by
abnormal edges in the CFG:
% cumulative self self total
time seconds seconds calls s/call s/call name
13.83 36.60 37.60 272892 0.00 0.00 remove_edge
4.90 50.92 13.32 17634463 0.00 0.00 replace_goto_queue_1
2.18 56.84 5.92 443335 0.00 0.00 find_reloads
1.93 62.08 5.24 1110938 0.00 0.00 gt_ggc_mx_lang_tree_node
1.76 66.87 4.79 375356 0.00 0.00 record_reg_classes
1.39 70.65 3.78 13455581 0.00 0.00 ggc_set_mark
1.37 74.37 3.72 8683135 0.00 0.00 ggc_alloc_stat
1.26 77.81 3.44 3448355 0.00 0.00 comptypes
1.21 81.09 3.28 1336950 0.00 0.00 walk_tree
-----------------------------------------------
0.11 0.00 919/272892 purge_dead_edges [270]
0.37 0.00 3133/272892 delete_basic_block [160]
1.08 0.00 9094/272892
remove_phi_nodes_and_edges_for_unreachable_block [234]
1.10 0.00 9303/272892 remove_fake_predecessors
[229]
2.06 0.01 17341/272892 merge_blocks [139]
2.61 0.01 21999/272892 find_bb_boundaries [100]
3.84 0.02 32405/272892 connect_post_landing_pads
[78]
9.66 0.04 81428/272892 finish_eh_generation [31]
16.77 0.00 97270/272892 expand_gimple_basic_block
[17]
[30] 13.9 37.60 0.08 272892 remove_edge [30]
0.08 0.00 272892/523547 ggc_free [613]
0.00 0.00 272892/341925 free_edge [2842]
-----------------------------------------------
This comes from this loop:
for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
{
/* Clear EDGE_EXECUTABLE. This flag is never used in the backend. */
e->flags &= ~EDGE_EXECUTABLE;
/* At the moment not all abnormal edges match the RTL representation.
It is safe to remove them here as find_sub_basic_blocks will
rediscover them. In the future we should get this fixed properly.
*/
if (e->flags & EDGE_ABNORMAL)
remove_edge (ei);
else
ei_next (&ei);
}
We walk all edges here, and we walk all of them again for remove_edge.
--
Summary: [4.0 Regression] quadratic behavior in cfgexpand
Product: gcc
Version: 4.0.0
Status: UNCONFIRMED
Keywords: compile-time-hog
Severity: normal
Priority: P2
Component: middle-end
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: steven at gcc dot gnu dot org
CC: gcc-bugs at gcc dot gnu dot org,jh at suse dot cz
BugsThisDependsOn: 17340
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18499
