Fix PR42963: redundant switch label cleanup

[Richard Guenther]

On Wed, Apr 14, 2010 at 3:03 PM, Michael Matz <matz@suse.de> wrote:
> Hello,
>
> so, it needed some prodding from Steven, but here it is.  Due to various
> circumstances we don't cleanup redundant switch labels anymore until very
> late in the compiler (we currently clean them up at two points, one very
> early where we meanwhile didn't cleanup some jumps anymore, and one very
> late).  This patch implements cleaning them up as soon as cfg-cleanup
> redirected any jump out of GIMPLE_SWITCH stmts.  To avoid quadratic
> complexity in case we redirect many jump targets I simply remember all BBs
> that need investigation, and clean them up later.
>
> The patch is noisy because it breaks out the actual cleaning per stmt from
> group_case_labels() into it's own routine.  Hence I include only the
> patch ignoring white-space changes for easier review.
>
> Regstrapping on x86_64-linux in progress, okay for trunk?

Ok.

Thanks,
Richard.

>
> Ciao,
> Michael.
> --
>        PR tree-optimization/42963
>        * tree-cfg.c (touched_switch_bbs): New static variable.
>        (group_case_labels_stmt): New function broken out from ...
>        (group_case_labels): ... here, use the above.
>        (start_recording_case_labels): Allocate touched_switch_bbs.
>        (end_recording_case_labels): Deallocate it, call
>        group_case_labels_stmt.
>        (gimple_redirect_edge_and_branch): Remember index of affected BB.
>
> testsuite/
>        * testsuite/gcc.dg/pr42963.c: New testcase.
>
> Index: tree-cfg.c
> ===================================================================
> *** tree-cfg.c  (revision 158263)
> --- tree-cfg.c  (working copy)
> *************** static const int initial_cfg_capacity =
> *** 71,76 ****
> --- 71,82 ----
>
>  static struct pointer_map_t *edge_to_cases;
>
> + /* If we record edge_to_cases, this bitmap will hold indexes
> +    of basic blocks that end in a GIMPLE_SWITCH which we touched
> +    due to edge manipulations.  */
> +
> + static bitmap touched_switch_bbs;
> +
>  /* CFG statistics.  */
>  struct cfg_stats_d
>  {
> *************** static edge find_taken_edge_computed_got
> *** 122,127 ****
> --- 128,134 ----
>  static edge find_taken_edge_cond_expr (basic_block, tree);
>  static edge find_taken_edge_switch_expr (basic_block, tree);
>  static tree find_case_label_for_value (gimple, tree);
> + static void group_case_labels_stmt (gimple);
>
>  void
>  init_empty_tree_cfg_for_function (struct function *fn)
> *************** start_recording_case_labels (void)
> *** 848,853 ****
> --- 855,861 ----
>  {
>    gcc_assert (edge_to_cases == NULL);
>    edge_to_cases = pointer_map_create ();
> +   touched_switch_bbs = BITMAP_ALLOC (NULL);
>  }
>
>  /* Return nonzero if we are recording information for case labels.  */
> *************** recording_case_labels_p (void)
> *** 863,871 ****
> --- 871,892 ----
>  void
>  end_recording_case_labels (void)
>  {
> +   bitmap_iterator bi;
> +   unsigned i;
>    pointer_map_traverse (edge_to_cases, edge_to_cases_cleanup, NULL);
>    pointer_map_destroy (edge_to_cases);
>    edge_to_cases = NULL;
> +   EXECUTE_IF_SET_IN_BITMAP (touched_switch_bbs, 0, i, bi)
> +     {
> +       basic_block bb = BASIC_BLOCK (i);
> +       if (bb)
> +       {
> +         gimple stmt = last_stmt (bb);
> +         if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
> +           group_case_labels_stmt (stmt);
> +       }
> +     }
> +   BITMAP_FREE (touched_switch_bbs);
>  }
>
>  /* If we are inside a {start,end}_recording_cases block, then return
> *************** cleanup_dead_labels (void)
> *** 1278,1297 ****
>    free (label_for_bb);
>  }
>
> ! /* Look for blocks ending in a multiway branch (a SWITCH_EXPR in GIMPLE),
> !    and scan the sorted vector of cases.  Combine the ones jumping to the
> !    same label.
>     Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
>
> ! void
> ! group_case_labels (void)
> ! {
> !   basic_block bb;
> !
> !   FOR_EACH_BB (bb)
> !     {
> !       gimple stmt = last_stmt (bb);
> !       if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
>        {
>          int old_size = gimple_switch_num_labels (stmt);
>          int i, j, new_size = old_size;
> --- 1299,1310 ----
>    free (label_for_bb);
>  }
>
> ! /* Scan the sorted vector of cases in STMT (a GIMPLE_SWITCH) and combine
> !    the ones jumping to the same label.
>     Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
>
> ! static void
> ! group_case_labels_stmt (gimple stmt)
>  {
>    int old_size = gimple_switch_num_labels (stmt);
>    int i, j, new_size = old_size;
> *************** group_case_labels (void)
> *** 1380,1385 ****
> --- 1393,1413 ----
>    gcc_assert (new_size <= old_size);
>    gimple_switch_set_num_labels (stmt, new_size);
>  }
> +
> + /* Look for blocks ending in a multiway branch (a SWITCH_EXPR in GIMPLE),
> +    and scan the sorted vector of cases.  Combine the ones jumping to the
> +    same label.  */
> +
> + void
> + group_case_labels (void)
> + {
> +   basic_block bb;
> +
> +   FOR_EACH_BB (bb)
> +     {
> +       gimple stmt = last_stmt (bb);
> +       if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
> +       group_case_labels_stmt (stmt);
>      }
>  }
>
> *************** gimple_redirect_edge_and_branch (edge e,
> *** 4689,4694 ****
> --- 4738,4744 ----
>                TREE_CHAIN (last) = TREE_CHAIN (cases2);
>                TREE_CHAIN (cases2) = first;
>              }
> +           bitmap_set_bit (touched_switch_bbs, gimple_bb (stmt)->index);
>          }
>        else
>          {
> Index: testsuite/gcc.dg/pr42963.c
> ===================================================================
> --- testsuite/gcc.dg/pr42963.c  (revision 0)
> +++ testsuite/gcc.dg/pr42963.c  (revision 0)
> @@ -0,0 +1,28 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-cfg" } */
> +extern void foo (void);
> +extern int i;
> +void
> +bar (void)
> +{
> +  switch (i)
> +    {
> +    case 0:
> +      foo ();
> +      break;
> +    case 1:
> +      break;
> +    }
> +
> +
> +  switch (i)
> +    {
> +    case 0:
> +      foo ();
> +      break;
> +    case 1:
> +      break;
> +    }
> +}
> +/* { dg-final { scan-tree-dump-times "case 1:" 0 "cfg" } } */
> +/* { dg-final { cleanup-tree-dump "cfg" } } */
>