------- Additional Comments From jh at suse dot cz 2004-11-15 10:37 ------- Subject: Re: New: [4.0 Regression] quadratic behavior in cfgexpand
> 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. Hmm, this was introduced by the edge vectors change. What is the canonical way to walk the edges and remove some? Honza > > -- > 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 > > ------- You are receiving this mail because: ------- > You are on the CC list for the bug, or are watching someone who is. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18499