Re: [PATCH, v4] Fix PR51513, switch statement with default case containing __builtin_unreachable leads to wild branch

[Richard Biener <rguenther at suse dot de>]

On Tue, 9 May 2017, Peter Bergner wrote:

> Here is the updated patch to use gimple_seq_unreachable_p() which scans the
> sequence backwards so it bails out earlier in the common case (ie, no call
> to __builtin_unreachable).  As discussed in the previous thread, we remove
> case statement labels from the jump table that lead to unreachable blocks,
> which leads to fewer compare/branches in the decision tree case and
> possibly a smaller jump table in the jump table case.  Unreachable default
> case statements are only handled here when generating a jump table, since
> the current code for decision trees seems to prefer the status quo.  We can
> revisit this later if someone finds a test case that would benefit from
> handling it for decision trees too.
> 
> This passes bootstrap and regtesting on powerpc64le-linux and x86_64-linux
> with no regressions.  Ok for trunk now?

Ok.

Thanks,
Richard.

> Peter
> 
> gcc/
> 	* tree-cfg.c (gimple_seq_unreachable_p): New function.
> 	(assert_unreachable_fallthru_edge_p): Use it.
> 	(group_case_labels_stmt): Likewise.
> 	* tree-cfg.h: Prototype it.
> 	* stmt.c: Include cfghooks.h and tree-cfg.h.
> 	(emit_case_dispatch_table) <gap_label>: New local variable.
> 	Use it to fill dispatch table gaps.
> 	Test for default_label before updating probabilities.
> 	(expand_case) <default_label>: Remove unneeded initialization.
> 	Test for unreachable default case statement and remove its edge.
> 	Set default_label accordingly.
> 	* tree-ssa-ccp.c (optimize_unreachable): Update comment.
> 
> gcc/testsuite/
> 	* gcc.target/powerpc/pr51513.c: New test.
> 	* gcc.dg/predict-13.c: Replace __builtin_unreachable() with
> 	__builtin_abort().
> 	* gcc.dg/predict-14.c: Likewise.
> 
> Index: gcc/tree-cfg.c
> ===================================================================
> --- gcc/tree-cfg.c	(revision 247291)
> +++ gcc/tree-cfg.c	(working copy)
> @@ -452,6 +452,31 @@ computed_goto_p (gimple *t)
>  	  && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL);
>  }
>  
> +/* Returns true if the sequence of statements STMTS only contains
> +   a call to __builtin_unreachable ().  */
> +
> +bool
> +gimple_seq_unreachable_p (gimple_seq stmts)
> +{
> +  if (stmts == NULL)
> +    return false;
> +
> +  gimple_stmt_iterator gsi = gsi_last (stmts);
> +
> +  if (!gimple_call_builtin_p (gsi_stmt (gsi), BUILT_IN_UNREACHABLE))
> +    return false;
> +
> +  for (gsi_prev (&gsi); !gsi_end_p (gsi); gsi_prev (&gsi))
> +    {
> +      gimple *stmt = gsi_stmt (gsi);
> +      if (gimple_code (stmt) != GIMPLE_LABEL
> +	  && !is_gimple_debug (stmt)
> +	  && !gimple_clobber_p (stmt))
> +      return false;
> +    }
> +  return true;
> +}
> +
>  /* Returns true for edge E where e->src ends with a GIMPLE_COND and
>     the other edge points to a bb with just __builtin_unreachable ().
>     I.e. return true for C->M edge in:
> @@ -476,22 +501,7 @@ assert_unreachable_fallthru_edge_p (edge
>        if (other_bb == e->dest)
>  	other_bb = EDGE_SUCC (pred_bb, 1)->dest;
>        if (EDGE_COUNT (other_bb->succs) == 0)
> -	{
> -	  gimple_stmt_iterator gsi = gsi_after_labels (other_bb);
> -	  gimple *stmt;
> -
> -	  if (gsi_end_p (gsi))
> -	    return false;
> -	  stmt = gsi_stmt (gsi);
> -	  while (is_gimple_debug (stmt) || gimple_clobber_p (stmt))
> -	    {
> -	      gsi_next (&gsi);
> -	      if (gsi_end_p (gsi))
> -		return false;
> -	      stmt = gsi_stmt (gsi);
> -	    }
> -	  return gimple_call_builtin_p (stmt, BUILT_IN_UNREACHABLE);
> -	}
> +	return gimple_seq_unreachable_p (bb_seq (other_bb));
>      }
>    return false;
>  }
> @@ -1668,9 +1678,11 @@ group_case_labels_stmt (gswitch *stmt)
>        gcc_assert (base_case);
>        base_bb = label_to_block (CASE_LABEL (base_case));
>  
> -      /* Discard cases that have the same destination as the
> -	 default case.  */
> -      if (base_bb == default_bb)
> +      /* Discard cases that have the same destination as the default case
> +	 or if their destination block is unreachable.  */
> +      if (base_bb == default_bb
> +	  || (EDGE_COUNT (base_bb->succs) == 0
> +	      && gimple_seq_unreachable_p (bb_seq (base_bb))))
>  	{
>  	  gimple_switch_set_label (stmt, i, NULL_TREE);
>  	  i++;
> Index: gcc/tree-cfg.h
> ===================================================================
> --- gcc/tree-cfg.h	(revision 247291)
> +++ gcc/tree-cfg.h	(working copy)
> @@ -56,6 +56,7 @@ extern bool is_ctrl_stmt (gimple *);
>  extern bool is_ctrl_altering_stmt (gimple *);
>  extern bool simple_goto_p (gimple *);
>  extern bool stmt_ends_bb_p (gimple *);
> +extern bool gimple_seq_unreachable_p (gimple_seq);
>  extern bool assert_unreachable_fallthru_edge_p (edge);
>  extern void delete_tree_cfg_annotations (function *);
>  extern gphi *get_virtual_phi (basic_block);
> Index: gcc/stmt.c
> ===================================================================
> --- gcc/stmt.c	(revision 247291)
> +++ gcc/stmt.c	(working copy)
> @@ -30,6 +30,7 @@ along with GCC; see the file COPYING3.
>  #include "rtl.h"
>  #include "tree.h"
>  #include "gimple.h"
> +#include "cfghooks.h"
>  #include "predict.h"
>  #include "alloc-pool.h"
>  #include "memmodel.h"
> @@ -49,6 +50,7 @@ along with GCC; see the file COPYING3.
>  #include "expr.h"
>  #include "langhooks.h"
>  #include "cfganal.h"
> +#include "tree-cfg.h"
>  #include "params.h"
>  #include "dumpfile.h"
>  #include "builtins.h"
> @@ -1007,20 +1009,21 @@ emit_case_dispatch_table (tree index_exp
>  	  = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
>      }
>  
> -  /* Fill in the gaps with the default.  We may have gaps at
> -     the beginning if we tried to avoid the minval subtraction,
> -     so substitute some label even if the default label was
> -     deemed unreachable.  */
> -  if (!default_label)
> -    default_label = fallback_label;
> +  /* The dispatch table may contain gaps, including at the beginning of
> +     the table if we tried to avoid the minval subtraction.  We fill the
> +     dispatch table slots associated with the gaps with the default case label.
> +     However, in the event the default case is unreachable, we then use
> +     any label from one of the case statements.  */
> +  rtx gap_label = (default_label) ? default_label : fallback_label;
> +
>    for (i = 0; i < ncases; i++)
>      if (labelvec[i] == 0)
>        {
> -        has_gaps = true;
> -        labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
> +	has_gaps = true;
> +	labelvec[i] = gen_rtx_LABEL_REF (Pmode, gap_label);
>        }
>  
> -  if (has_gaps)
> +  if (has_gaps && default_label)
>      {
>        /* There is at least one entry in the jump table that jumps
>           to default label. The default label can either be reached
> @@ -1115,7 +1118,7 @@ void
>  expand_case (gswitch *stmt)
>  {
>    tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
> -  rtx_code_label *default_label = NULL;
> +  rtx_code_label *default_label;
>    unsigned int count, uniq;
>    int i;
>    int ncases = gimple_switch_num_labels (stmt);
> @@ -1232,9 +1235,21 @@ expand_case (gswitch *stmt)
>                               case_list, default_label,
>                               default_prob);
>    else
> -    emit_case_dispatch_table (index_expr, index_type,
> -			      case_list, default_label,
> -			      minval, maxval, range, bb);
> +    {
> +      /* If the default case is unreachable, then set default_label to NULL
> +	 so that we omit the range check when generating the dispatch table.
> +	 We also remove the edge to the unreachable default case.  The block
> +	 itself will be automatically removed later.  */
> +      if (EDGE_COUNT (default_edge->dest->succs) == 0
> +	  && gimple_seq_unreachable_p (bb_seq (default_edge->dest)))
> +	{
> +	  default_label = NULL;
> +	  remove_edge (default_edge);
> +	}
> +      emit_case_dispatch_table (index_expr, index_type,
> +				case_list, default_label,
> +				minval, maxval, range, bb);
> +    }
>  
>    reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case);
>  
> Index: gcc/tree-ssa-ccp.c
> ===================================================================
> --- gcc/tree-ssa-ccp.c	(revision 247291)
> +++ gcc/tree-ssa-ccp.c	(working copy)
> @@ -2715,7 +2715,8 @@ optimize_unreachable (gimple_stmt_iterat
>  	}
>        else
>  	{
> -	  /* Todo: handle other cases, f.i. switch statement.  */
> +	  /* Todo: handle other cases.  Note that unreachable switch case
> +	     statements have already been removed.  */
>  	  continue;
>  	}
>  
> Index: gcc/testsuite/gcc.target/powerpc/pr51513.c
> ===================================================================
> --- gcc/testsuite/gcc.target/powerpc/pr51513.c	(nonexistent)
> +++ gcc/testsuite/gcc.target/powerpc/pr51513.c	(working copy)
> @@ -0,0 +1,25 @@
> +/* { dg-do compile { target { powerpc*-*-linux* } } } */
> +/* { dg-options "-O2 -fjump-tables --param case-values-threshold=1" } */
> +/* Verify we created a jump table.  */
> +/* { dg-final { scan-assembler-times "mtctr "  1 } } */
> +/* { dg-final { scan-assembler-times "bctr" 1 } } */
> +/* Verify we eliminated the range check.  */
> +/* { dg-final { scan-assembler-not "cmpldi" } } */
> +/* { dg-final { scan-assembler-not "cmplwi" } } */
> +
> +long
> +bug (long cond, long v0, long v1, long v2)
> +{
> +  switch (cond)
> +    {
> +      case 0:
> +	return v0;
> +      case 1:
> +	return v1;
> +      case 2:
> +	return v2;
> +      default:
> +	__builtin_unreachable ();
> +    }
> +  __builtin_abort ();
> +}
> Index: gcc/testsuite/gcc.dg/predict-13.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/predict-13.c	(revision 247291)
> +++ gcc/testsuite/gcc.dg/predict-13.c	(working copy)
> @@ -10,9 +10,9 @@ int main(int argc, char **argv)
>      case 2:
>        return 2;
>      case 3:
> -      __builtin_unreachable();
> +      __builtin_abort();
>      case 4:
> -      __builtin_unreachable();
> +      __builtin_abort();
>      default:
>        return 5;
>      }
> Index: gcc/testsuite/gcc.dg/predict-14.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/predict-14.c	(revision 247291)
> +++ gcc/testsuite/gcc.dg/predict-14.c	(working copy)
> @@ -6,11 +6,11 @@ int main(int argc, char **argv)
>    switch (argc)
>      {
>      case 1:
> -      __builtin_unreachable();
> +      __builtin_abort();
>      case 4:
> -      __builtin_unreachable();
> +      __builtin_abort();
>      default:
> -      __builtin_unreachable();
> +      __builtin_abort();
>      }
>  
>    return 10;
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)