[Bug middle-end/18499] [4.0 Regression] quadratic behavior in cfgexpand

jh at suse dot cz gcc-bugzilla@gcc.gnu.org
Mon Nov 15 10:37:00 GMT 2004


------- 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



More information about the Gcc-bugs mailing list