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

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

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