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

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

[Peter Bergner]

This patch is the second attempt to fix PR51513, namely the generation of
wild branches due to switch case statements that only contain calls to
__builtin_unreachable().  With the first attempt:

    https://gcc.gnu.org/ml/gcc-patches/2016-04/msg01915.html

richi said he preferred if we just eliminated the range check for
default case statements that contained __builtin_unreachable().
This patch implements that idea.  It also removes normal case
statement blocks that are marked as unreachable, but in those cases,
we just use a dummy label in the jump table for them.

This passed bootstrap and regtesting with no regressions on powerpc64-linux
and x86_64-linux.  Ok for trunk now or trunk during stage1?

Peter


gcc/
	* tree-cfg.c (gimple_unreachable_bb_p): New function.
	(assert_unreachable_fallthru_edge_p): Use it.
	* 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 and unreachable cases.
	Remove edges to unreachable blocks.
	(expand_case): Test for unreachable default case statement and
	remove its edge.  Set default_label accordingly.
	(emit_case_nodes): Only emit branch to default_label if it
	exists.

gcc/testsuite/
	* gcc.target/powerpc/pr51513.c: New test.

Index: gcc/stmt.c
===================================================================
--- gcc/stmt.c	(revision 246661)
+++ 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"
@@ -989,6 +991,14 @@ emit_case_dispatch_table (tree index_exp
   labelvec = XALLOCAVEC (rtx, ncases);
   memset (labelvec, 0, ncases * sizeof (rtx));
 
+  /* The dispatch table may contain gaps and labels of unreachable case
+     statements.  Gaps can exist at the beginning of the table if we tried
+     to avoid the minval subtraction.  We fill the dispatch table slots
+     associated with the gaps and unreachable case blocks with the default
+     case label.  However, in the event the default case itself is unreachable,
+     we then use any label from one of the reachable case statements.  */
+  rtx gap_label = (default_label) ? default_label : fallback_label;
+
   for (n = case_list; n; n = n->right)
     {
       /* Compute the low and high bounds relative to the minimum
@@ -1000,42 +1010,51 @@ emit_case_dispatch_table (tree index_exp
       HOST_WIDE_INT i_high
 	= tree_to_uhwi (fold_build2 (MINUS_EXPR, index_type,
 				     n->high, minval));
-      HOST_WIDE_INT i;
 
+      basic_block case_bb = label_to_block (n->code_label);
+      rtx case_label;
+      if (gimple_unreachable_bb_p (case_bb))
+	{
+	  /* We have an unreachable case statement, so replace its label
+	     with a dummy label and remove the edge to the unreachable block.
+	     The block itself will be automatically removed later.  */
+	  case_label = gap_label;
+	  remove_edge (find_edge (stmt_bb, case_bb));
+	}
+      else
+	case_label = label_rtx (n->code_label);
+
+      HOST_WIDE_INT i;
       for (i = i_low; i <= i_high; i ++)
-	labelvec[i]
-	  = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
+	labelvec[i] = gen_rtx_LABEL_REF (Pmode, case_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;
+  /* Now fill in the dispatch table gaps.  */
   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)
-    {
-      /* There is at least one entry in the jump table that jumps
-         to default label. The default label can either be reached
-         through the indirect jump or the direct conditional jump
-         before that. Split the probability of reaching the
-         default label among these two jumps.  */
-      new_default_prob = conditional_probability (default_prob/2,
-                                                  base);
-      default_prob /= 2;
-      base -= default_prob;
-    }
-  else
+  if (default_label)
     {
-      base -= default_prob;
-      default_prob = 0;
+      if (has_gaps)
+	{
+	  /* There is at least one entry in the jump table that jumps
+	     to default label. The default label can either be reached
+	     through the indirect jump or the direct conditional jump
+	     before that. Split the probability of reaching the
+	     default label among these two jumps.  */
+	  new_default_prob = conditional_probability (default_prob/2, base);
+	  default_prob /= 2;
+	  base -= default_prob;
+	}
+      else
+	{
+	  base -= default_prob;
+	  default_prob = 0;
+	}
     }
 
   if (default_edge)
@@ -1115,7 +1134,8 @@ 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;
+  int default_prob;
   unsigned int count, uniq;
   int i;
   int ncases = gimple_switch_num_labels (stmt);
@@ -1139,15 +1159,24 @@ expand_case (gswitch *stmt)
   /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
      expressions being INTEGER_CST.  */
   gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
-  
 
   do_pending_stack_adjust ();
 
   /* Find the default case target label.  */
-  default_label = jump_target_rtx
-      (CASE_LABEL (gimple_switch_default_label (stmt)));
-  edge default_edge = EDGE_SUCC (bb, 0);
-  int default_prob = default_edge->probability;
+  tree default_tree = CASE_LABEL (gimple_switch_default_label (stmt));
+  basic_block default_bb = label_to_block (default_tree);
+  if (gimple_unreachable_bb_p (default_bb))
+    {
+      default_label = NULL;
+      default_prob = 0;
+      remove_edge (find_edge (bb, default_bb));
+    }
+  else
+    {
+      default_label = jump_target_rtx (default_tree);
+      edge default_edge = EDGE_SUCC (bb, 0);
+      default_prob = default_edge->probability;
+    }
 
   /* Get upper and lower bounds of case values.  */
   elt = gimple_switch_label (stmt, 1);
@@ -1725,7 +1754,7 @@ emit_case_nodes (rtx index, case_node_pt
 	  if (node->right->right || node->right->left
 	      || !tree_int_cst_equal (node->right->low, node->right->high))
 	    {
-	      if (!node_has_low_bound (node, index_type))
+	      if (default_label && !node_has_low_bound (node, index_type))
 		{
                   probability = conditional_probability (
                       default_prob/2,
@@ -1767,7 +1796,7 @@ emit_case_nodes (rtx index, case_node_pt
 	  if (node->left->left || node->left->right
 	      || !tree_int_cst_equal (node->left->low, node->left->high))
 	    {
-	      if (!node_has_high_bound (node, index_type))
+	      if (default_label && !node_has_high_bound (node, index_type))
 		{
                   probability = conditional_probability (
                       default_prob/2,
@@ -1891,7 +1920,7 @@ emit_case_nodes (rtx index, case_node_pt
 	{
 	  /* Deal with values to the left of this node,
 	     if they are possible.  */
-	  if (!node_has_low_bound (node, index_type))
+	  if (default_label && !node_has_low_bound (node, index_type))
 	    {
               probability = conditional_probability (
                   default_prob/2,
@@ -1928,7 +1957,7 @@ emit_case_nodes (rtx index, case_node_pt
 	{
 	  /* Deal with values to the right of this node,
 	     if they are possible.  */
-	  if (!node_has_high_bound (node, index_type))
+	  if (default_label && !node_has_high_bound (node, index_type))
 	    {
               probability = conditional_probability (
                   default_prob/2,
@@ -1969,7 +1998,7 @@ emit_case_nodes (rtx index, case_node_pt
 	  int high_bound = node_has_high_bound (node, index_type);
 	  int low_bound = node_has_low_bound (node, index_type);
 
-	  if (!high_bound && low_bound)
+	  if (default_label && !high_bound && low_bound)
 	    {
               probability = conditional_probability (
                   default_prob,
@@ -1984,7 +2013,7 @@ emit_case_nodes (rtx index, case_node_pt
                                        probability);
 	    }
 
-	  else if (!low_bound && high_bound)
+	  else if (default_label && !low_bound && high_bound)
 	    {
               probability = conditional_probability (
                   default_prob,
@@ -1998,7 +2027,7 @@ emit_case_nodes (rtx index, case_node_pt
 				       default_label,
                                        probability);
 	    }
-	  else if (!low_bound && !high_bound)
+	  else if (default_label && !low_bound && !high_bound)
 	    {
 	      /* Widen LOW and HIGH to the same width as INDEX.  */
 	      tree type = lang_hooks.types.type_for_mode (mode, unsignedp);
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/tree-cfg.c
===================================================================
--- gcc/tree-cfg.c	(revision 246661)
+++ gcc/tree-cfg.c	(working copy)
@@ -452,6 +452,37 @@ computed_goto_p (gimple *t)
 	  && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL);
 }
 
+/* Returns true if the basic block BB has no successors and only contains
+   a call to __builtin_unreachable ().  */
+
+bool
+gimple_unreachable_bb_p (basic_block bb)
+{
+  gimple_stmt_iterator gsi;
+  gimple_seq stmts = bb_seq (bb);
+  gimple *stmt;
+
+  if (EDGE_COUNT (bb->succs) != 0)
+    return false;
+
+  gsi = gsi_start (stmts);
+  while (!gsi_end_p (gsi) && gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
+    gsi_next (&gsi);
+
+  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);
+}
+
 /* 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:
@@ -475,28 +506,11 @@ assert_unreachable_fallthru_edge_p (edge
       basic_block other_bb = EDGE_SUCC (pred_bb, 0)->dest;
       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_unreachable_bb_p (other_bb);
     }
   return false;
 }
 
-
 /* Initialize GF_CALL_CTRL_ALTERING flag, which indicates the call
    could alter control flow except via eh. We initialize the flag at
    CFG build time and only ever clear it later.  */
Index: gcc/tree-cfg.h
===================================================================
--- gcc/tree-cfg.h	(revision 246661)
+++ 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_unreachable_bb_p (basic_block);
 extern bool assert_unreachable_fallthru_edge_p (edge);
 extern void delete_tree_cfg_annotations (function *);
 extern gphi *get_virtual_phi (basic_block);

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

[Richard Biener]

On Wed, 12 Apr 2017, Peter Bergner wrote:

> This patch is the second attempt to fix PR51513, namely the generation of
> wild branches due to switch case statements that only contain calls to
> __builtin_unreachable().  With the first attempt:
> 
>     https://gcc.gnu.org/ml/gcc-patches/2016-04/msg01915.html
> 
> richi said he preferred if we just eliminated the range check for
> default case statements that contained __builtin_unreachable().
> This patch implements that idea.  It also removes normal case
> statement blocks that are marked as unreachable, but in those cases,
> we just use a dummy label in the jump table for them.
> 
> This passed bootstrap and regtesting with no regressions on powerpc64-linux
> and x86_64-linux.  Ok for trunk now or trunk during stage1?

To recap the situation (from what I can deciper out of the ppc asm
and the expand RTL) we seem to expand to

  if (cond > 2)
    __builtin_unreachable (); // jumps to the jump table data(?)
  goto *tbl[cond];

now I do not remember the reason why we keep __builtin_unreachable ()
at the RTL level -- on GIMPLE we keep it to be able to extract
range information from the controlling condition.

Your patch comments suggest that handling of gaps is similarly
improved but the testcase doesn't contain any gaps.

So I wonder why we don't simply apply the "transform" at the GIMPLE
level, for example in the kitchen-sink pass_fold_builtins.  That is
remove all __builtin_unreachable () labels and if the default label
is amongst them make the first one the new default (or maybe the
last one dependent on which would shrink jump table size most).

I'd apply the same to if conditions but as said I don't remember
why we keep __builtin_unreachable () -- we of course do have to
keep it if stmts preceeding it may have side-effects.

Maybe somebody can chime in on the uselfulness of keeping RTL
for this case?  For trivial cases like

int foo (int i)
{
  if (i < -__INT_MAX__)
    __builtin_unreachable ();
  return i - 2;
}

VRP2 removes the if because we put the range computed by VRP1
on the SSA name used in the test (we have special code handling
unreachable paths there).  For your testcase with the switch
as cond_2 is not used after the switch we do not compute any
range for it, otherwise we'd likely eliminate the default
case as well.  For the small testcase above fold-all-builtins
handles the removal as well if VRP is not run, so extending
that to handle switch stmts sounds reasonable (see
optimize_unreachable).  There's even a TODO in this function.

Richard.

> Peter
> 
> 
> gcc/
> 	* tree-cfg.c (gimple_unreachable_bb_p): New function.
> 	(assert_unreachable_fallthru_edge_p): Use it.
> 	* 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 and unreachable cases.
> 	Remove edges to unreachable blocks.
> 	(expand_case): Test for unreachable default case statement and
> 	remove its edge.  Set default_label accordingly.
> 	(emit_case_nodes): Only emit branch to default_label if it
> 	exists.
> 
> gcc/testsuite/
> 	* gcc.target/powerpc/pr51513.c: New test.
> 
> Index: gcc/stmt.c
> ===================================================================
> --- gcc/stmt.c	(revision 246661)
> +++ 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"
> @@ -989,6 +991,14 @@ emit_case_dispatch_table (tree index_exp
>    labelvec = XALLOCAVEC (rtx, ncases);
>    memset (labelvec, 0, ncases * sizeof (rtx));
>  
> +  /* The dispatch table may contain gaps and labels of unreachable case
> +     statements.  Gaps can exist at the beginning of the table if we tried
> +     to avoid the minval subtraction.  We fill the dispatch table slots
> +     associated with the gaps and unreachable case blocks with the default
> +     case label.  However, in the event the default case itself is unreachable,
> +     we then use any label from one of the reachable case statements.  */
> +  rtx gap_label = (default_label) ? default_label : fallback_label;
> +
>    for (n = case_list; n; n = n->right)
>      {
>        /* Compute the low and high bounds relative to the minimum
> @@ -1000,42 +1010,51 @@ emit_case_dispatch_table (tree index_exp
>        HOST_WIDE_INT i_high
>  	= tree_to_uhwi (fold_build2 (MINUS_EXPR, index_type,
>  				     n->high, minval));
> -      HOST_WIDE_INT i;
>  
> +      basic_block case_bb = label_to_block (n->code_label);
> +      rtx case_label;
> +      if (gimple_unreachable_bb_p (case_bb))
> +	{
> +	  /* We have an unreachable case statement, so replace its label
> +	     with a dummy label and remove the edge to the unreachable block.
> +	     The block itself will be automatically removed later.  */
> +	  case_label = gap_label;
> +	  remove_edge (find_edge (stmt_bb, case_bb));
> +	}
> +      else
> +	case_label = label_rtx (n->code_label);
> +
> +      HOST_WIDE_INT i;
>        for (i = i_low; i <= i_high; i ++)
> -	labelvec[i]
> -	  = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
> +	labelvec[i] = gen_rtx_LABEL_REF (Pmode, case_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;
> +  /* Now fill in the dispatch table gaps.  */
>    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)
> -    {
> -      /* There is at least one entry in the jump table that jumps
> -         to default label. The default label can either be reached
> -         through the indirect jump or the direct conditional jump
> -         before that. Split the probability of reaching the
> -         default label among these two jumps.  */
> -      new_default_prob = conditional_probability (default_prob/2,
> -                                                  base);
> -      default_prob /= 2;
> -      base -= default_prob;
> -    }
> -  else
> +  if (default_label)
>      {
> -      base -= default_prob;
> -      default_prob = 0;
> +      if (has_gaps)
> +	{
> +	  /* There is at least one entry in the jump table that jumps
> +	     to default label. The default label can either be reached
> +	     through the indirect jump or the direct conditional jump
> +	     before that. Split the probability of reaching the
> +	     default label among these two jumps.  */
> +	  new_default_prob = conditional_probability (default_prob/2, base);
> +	  default_prob /= 2;
> +	  base -= default_prob;
> +	}
> +      else
> +	{
> +	  base -= default_prob;
> +	  default_prob = 0;
> +	}
>      }
>  
>    if (default_edge)
> @@ -1115,7 +1134,8 @@ 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;
> +  int default_prob;
>    unsigned int count, uniq;
>    int i;
>    int ncases = gimple_switch_num_labels (stmt);
> @@ -1139,15 +1159,24 @@ expand_case (gswitch *stmt)
>    /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
>       expressions being INTEGER_CST.  */
>    gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
> -  
>  
>    do_pending_stack_adjust ();
>  
>    /* Find the default case target label.  */
> -  default_label = jump_target_rtx
> -      (CASE_LABEL (gimple_switch_default_label (stmt)));
> -  edge default_edge = EDGE_SUCC (bb, 0);
> -  int default_prob = default_edge->probability;
> +  tree default_tree = CASE_LABEL (gimple_switch_default_label (stmt));
> +  basic_block default_bb = label_to_block (default_tree);
> +  if (gimple_unreachable_bb_p (default_bb))
> +    {
> +      default_label = NULL;
> +      default_prob = 0;
> +      remove_edge (find_edge (bb, default_bb));
> +    }
> +  else
> +    {
> +      default_label = jump_target_rtx (default_tree);
> +      edge default_edge = EDGE_SUCC (bb, 0);
> +      default_prob = default_edge->probability;
> +    }
>  
>    /* Get upper and lower bounds of case values.  */
>    elt = gimple_switch_label (stmt, 1);
> @@ -1725,7 +1754,7 @@ emit_case_nodes (rtx index, case_node_pt
>  	  if (node->right->right || node->right->left
>  	      || !tree_int_cst_equal (node->right->low, node->right->high))
>  	    {
> -	      if (!node_has_low_bound (node, index_type))
> +	      if (default_label && !node_has_low_bound (node, index_type))
>  		{
>                    probability = conditional_probability (
>                        default_prob/2,
> @@ -1767,7 +1796,7 @@ emit_case_nodes (rtx index, case_node_pt
>  	  if (node->left->left || node->left->right
>  	      || !tree_int_cst_equal (node->left->low, node->left->high))
>  	    {
> -	      if (!node_has_high_bound (node, index_type))
> +	      if (default_label && !node_has_high_bound (node, index_type))
>  		{
>                    probability = conditional_probability (
>                        default_prob/2,
> @@ -1891,7 +1920,7 @@ emit_case_nodes (rtx index, case_node_pt
>  	{
>  	  /* Deal with values to the left of this node,
>  	     if they are possible.  */
> -	  if (!node_has_low_bound (node, index_type))
> +	  if (default_label && !node_has_low_bound (node, index_type))
>  	    {
>                probability = conditional_probability (
>                    default_prob/2,
> @@ -1928,7 +1957,7 @@ emit_case_nodes (rtx index, case_node_pt
>  	{
>  	  /* Deal with values to the right of this node,
>  	     if they are possible.  */
> -	  if (!node_has_high_bound (node, index_type))
> +	  if (default_label && !node_has_high_bound (node, index_type))
>  	    {
>                probability = conditional_probability (
>                    default_prob/2,
> @@ -1969,7 +1998,7 @@ emit_case_nodes (rtx index, case_node_pt
>  	  int high_bound = node_has_high_bound (node, index_type);
>  	  int low_bound = node_has_low_bound (node, index_type);
>  
> -	  if (!high_bound && low_bound)
> +	  if (default_label && !high_bound && low_bound)
>  	    {
>                probability = conditional_probability (
>                    default_prob,
> @@ -1984,7 +2013,7 @@ emit_case_nodes (rtx index, case_node_pt
>                                         probability);
>  	    }
>  
> -	  else if (!low_bound && high_bound)
> +	  else if (default_label && !low_bound && high_bound)
>  	    {
>                probability = conditional_probability (
>                    default_prob,
> @@ -1998,7 +2027,7 @@ emit_case_nodes (rtx index, case_node_pt
>  				       default_label,
>                                         probability);
>  	    }
> -	  else if (!low_bound && !high_bound)
> +	  else if (default_label && !low_bound && !high_bound)
>  	    {
>  	      /* Widen LOW and HIGH to the same width as INDEX.  */
>  	      tree type = lang_hooks.types.type_for_mode (mode, unsignedp);
> 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/tree-cfg.c
> ===================================================================
> --- gcc/tree-cfg.c	(revision 246661)
> +++ gcc/tree-cfg.c	(working copy)
> @@ -452,6 +452,37 @@ computed_goto_p (gimple *t)
>  	  && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL);
>  }
>  
> +/* Returns true if the basic block BB has no successors and only contains
> +   a call to __builtin_unreachable ().  */
> +
> +bool
> +gimple_unreachable_bb_p (basic_block bb)
> +{
> +  gimple_stmt_iterator gsi;
> +  gimple_seq stmts = bb_seq (bb);
> +  gimple *stmt;
> +
> +  if (EDGE_COUNT (bb->succs) != 0)
> +    return false;
> +
> +  gsi = gsi_start (stmts);
> +  while (!gsi_end_p (gsi) && gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
> +    gsi_next (&gsi);
> +
> +  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);
> +}
> +
>  /* 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:
> @@ -475,28 +506,11 @@ assert_unreachable_fallthru_edge_p (edge
>        basic_block other_bb = EDGE_SUCC (pred_bb, 0)->dest;
>        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_unreachable_bb_p (other_bb);
>      }
>    return false;
>  }
>  
> -
>  /* Initialize GF_CALL_CTRL_ALTERING flag, which indicates the call
>     could alter control flow except via eh. We initialize the flag at
>     CFG build time and only ever clear it later.  */
> Index: gcc/tree-cfg.h
> ===================================================================
> --- gcc/tree-cfg.h	(revision 246661)
> +++ 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_unreachable_bb_p (basic_block);
>  extern bool assert_unreachable_fallthru_edge_p (edge);
>  extern void delete_tree_cfg_annotations (function *);
>  extern gphi *get_virtual_phi (basic_block);
> 
> 

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

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

[Jakub Jelinek]

On Thu, Apr 13, 2017 at 10:14:51AM +0200, Richard Biener wrote:
> now I do not remember the reason why we keep __builtin_unreachable ()
> at the RTL level -- on GIMPLE we keep it to be able to extract

I believe we don't.  In RTL __builtin_unreachable () is represented
as a basic block without successors, followed by a BARRIER.

	Jakub

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

[Peter Bergner]

Bah, fixing up my return address.


On 4/13/17 3:14 AM, Richard Biener wrote:
> To recap the situation (from what I can deciper out of the ppc asm
> and the expand RTL) we seem to expand to
> 
>   if (cond > 2)
>     __builtin_unreachable (); // jumps to the jump table data(?)
>   goto *tbl[cond];
> 
> now I do not remember the reason why we keep __builtin_unreachable ()
> at the RTL level -- on GIMPLE we keep it to be able to extract
> range information from the controlling condition.

As Jakub said, we do remove the blocks.  But we don't remove the branch
to those blocks.  That is true of whether the __builtin_unreachable() is
in the default case statement or in a normal case statement.  That is
what leads to the wild branch issue.


> Your patch comments suggest that handling of gaps is similarly
> improved but the testcase doesn't contain any gaps.

I didn't change the way the jump table gaps are handled.  They have
always been redirected to the "default label"... although the patch
doesn't use default_label anymore, it uses gap_label, as resetting
default_label to fallback_label when default_label is NULL was
what was stopping us from removing the range check.

What is changed, is that now we also handle case labels that point to
blocks with __builtin_unreachable() and those are also redirected to
the new gap_label.

I did not include a test case with an unreachable case statement,
because unlike the unreachable default case test case, there is no
compare/branch I can verify has been removed.  However, looking
closer, it seems the unpatched compiler leaves the unreachable
block as well as it's label in the jump table, so I should be able
to create an executable test case that uses a switch condition
that targets the unreachable case and see if we SEGV/SIGILL or not.
I cannot do that for the unreachable default case, since the range
check we remove is what saves us from accessing the jump table
with an index that is outside of the table.



> So I wonder why we don't simply apply the "transform" at the GIMPLE
> level, for example in the kitchen-sink pass_fold_builtins.  That is
> remove all __builtin_unreachable () labels and if the default label
> is amongst them make the first one the new default (or maybe the
> last one dependent on which would shrink jump table size most).

Well if the default case is unreachable and we compute a "new"
default, then we won't be able to eliminate the range check
(ie, compare/branch to default).  So isn't it performance wise
better to eliminate the range check, rather than choosing a
new default?  If you think we shouldn't care about that, then
I'd vote for choosing the first/last label with the higher
edge probability rather than trying to shrink the table.




> VRP2 removes the if because we put the range computed by VRP1
> on the SSA name used in the test (we have special code handling
> unreachable paths there).  For your testcase with the switch
> as cond_2 is not used after the switch we do not compute any
> range for it, otherwise we'd likely eliminate the default
> case as well.  For the small testcase above fold-all-builtins
> handles the removal as well if VRP is not run, so extending
> that to handle switch stmts sounds reasonable (see
> optimize_unreachable).  There's even a TODO in this function.

If we updated optimize_unreachable() to remove unreachable
default cases, would we still be able to disambiguate between
a switch statement written with no default case and one where
the default case was explicitly shown to be unreachable?
Maybe the default_label would be NULL for the unreachable
case and non-NULL in the other case?  If so, we'd still need
my change that doesn't set default_label to fallback_label
and instead uses the new var gap_label.

Peter

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

[Richard Biener]

On Thu, 13 Apr 2017, Peter Bergner wrote:

> Bah, fixing up my return address.
> 
> 
> On 4/13/17 3:14 AM, Richard Biener wrote:
> > To recap the situation (from what I can deciper out of the ppc asm
> > and the expand RTL) we seem to expand to
> > 
> >   if (cond > 2)
> >     __builtin_unreachable (); // jumps to the jump table data(?)
> >   goto *tbl[cond];
> > 
> > now I do not remember the reason why we keep __builtin_unreachable ()
> > at the RTL level -- on GIMPLE we keep it to be able to extract
> > range information from the controlling condition.
> 
> As Jakub said, we do remove the blocks.  But we don't remove the branch
> to those blocks.  That is true of whether the __builtin_unreachable() is
> in the default case statement or in a normal case statement.  That is
> what leads to the wild branch issue.
> 
> 
> > Your patch comments suggest that handling of gaps is similarly
> > improved but the testcase doesn't contain any gaps.
> 
> I didn't change the way the jump table gaps are handled.  They have
> always been redirected to the "default label"... although the patch
> doesn't use default_label anymore, it uses gap_label, as resetting
> default_label to fallback_label when default_label is NULL was
> what was stopping us from removing the range check.
> 
> What is changed, is that now we also handle case labels that point to
> blocks with __builtin_unreachable() and those are also redirected to
> the new gap_label.
> 
> I did not include a test case with an unreachable case statement,
> because unlike the unreachable default case test case, there is no
> compare/branch I can verify has been removed.  However, looking
> closer, it seems the unpatched compiler leaves the unreachable
> block as well as it's label in the jump table, so I should be able
> to create an executable test case that uses a switch condition
> that targets the unreachable case and see if we SEGV/SIGILL or not.
> I cannot do that for the unreachable default case, since the range
> check we remove is what saves us from accessing the jump table
> with an index that is outside of the table.
> 
> 
> 
> > So I wonder why we don't simply apply the "transform" at the GIMPLE
> > level, for example in the kitchen-sink pass_fold_builtins.  That is
> > remove all __builtin_unreachable () labels and if the default label
> > is amongst them make the first one the new default (or maybe the
> > last one dependent on which would shrink jump table size most).
> 
> Well if the default case is unreachable and we compute a "new"
> default, then we won't be able to eliminate the range check
> (ie, compare/branch to default).  So isn't it performance wise
> better to eliminate the range check, rather than choosing a
> new default?  If you think we shouldn't care about that, then
> I'd vote for choosing the first/last label with the higher
> edge probability rather than trying to shrink the table.

True.

> > VRP2 removes the if because we put the range computed by VRP1
> > on the SSA name used in the test (we have special code handling
> > unreachable paths there).  For your testcase with the switch
> > as cond_2 is not used after the switch we do not compute any
> > range for it, otherwise we'd likely eliminate the default
> > case as well.  For the small testcase above fold-all-builtins
> > handles the removal as well if VRP is not run, so extending
> > that to handle switch stmts sounds reasonable (see
> > optimize_unreachable).  There's even a TODO in this function.
> 
> If we updated optimize_unreachable() to remove unreachable
> default cases, would we still be able to disambiguate between
> a switch statement written with no default case and one where
> the default case was explicitly shown to be unreachable?

No.

> Maybe the default_label would be NULL for the unreachable
> case and non-NULL in the other case?  If so, we'd still need
> my change that doesn't set default_label to fallback_label
> and instead uses the new var gap_label.

That would be possible though we now rely on the default label
to be present IIRC.

Ok, so I think we should ensure that we remove the regular cases
with unreachable destination, like in

switch (i)
{
case 0:
  __builtin_unreachable ();
default:;
}

and handle default with __builtin_unreachable () from switch
expansion by omitting the range check for the jump table
indexing (and choose a non-default case label for gaps).

Richard.

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

[Peter Bergner]

On 4/20/17 2:37 AM, Richard Biener wrote:
> Ok, so I think we should ensure that we remove the regular cases
> with unreachable destination, like in
> 
> switch (i)
> {
> case 0:
>   __builtin_unreachable ();
> default:;
> }
> 
> and handle default with __builtin_unreachable () from switch
> expansion by omitting the range check for the jump table
> indexing (and choose a non-default case label for gaps).

Ok, I'll modify optimize_unreachable() to remove the unreachable
case statements, and leave the unreachable default case statement
for switch expansion so we can eliminate the range check.  Thanks.

Peter

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

[Peter Bergner]

On 4/20/17 8:26 AM, Peter Bergner wrote:
> On 4/20/17 2:37 AM, Richard Biener wrote:
>> Ok, so I think we should ensure that we remove the regular cases
>> with unreachable destination, like in
>>
>> switch (i)
>> {
>> case 0:
>>   __builtin_unreachable ();
>> default:;
>> }
>>
>> and handle default with __builtin_unreachable () from switch
>> expansion by omitting the range check for the jump table
>> indexing (and choose a non-default case label for gaps).
> 
> Ok, I'll modify optimize_unreachable() to remove the unreachable
> case statements, and leave the unreachable default case statement
> for switch expansion so we can eliminate the range check.  Thanks.

Ok, I lied. :-)  It ended up being a fair amount of code to remove
the unreachable case statements within optimize_unreachable().
Instead, I hooked into group_case_labels_stmt() which is much
simpler!  That code eliminates all case statements that have the
same destination as the default case statement.  With the patch,
we also eliminate case statements that are unreachable, thus
treating them like default cases.  This has the added benefit of
being able to reduce the size of the dispatch table, if those cases
were at the end of the dispatch table entries.

One difference from the last patch is that I am no longer setting
default_label to NULL when we emit a decision tree.  I noticed that
the decision tree code seemed to generate slightly better code for
some of my unit tests if I left it alone.  This simplified the
patch somewhat by removing the changes to emit_case_nodes().

This passed bootstrap and regtesting on powerpc64le-linux and
x86_64-linux.  Is this ok for trunk now?  If so, I can hold off
committing it until GCC 7 has been released if that helps.

Peter


gcc/
	* tree-cfg.c (gimple_unreachable_bb_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.
	* gcc/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,37 @@ computed_goto_p (gimple *t)
 	  && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL);
 }
 
+/* Returns true if the basic block BB has no successors and only contains
+   a call to __builtin_unreachable ().  */
+
+bool
+gimple_unreachable_bb_p (basic_block bb)
+{
+  gimple_stmt_iterator gsi;
+  gimple_seq stmts = bb_seq (bb);
+  gimple *stmt;
+
+  if (EDGE_COUNT (bb->succs) != 0)
+    return false;
+
+  gsi = gsi_start (stmts);
+  while (!gsi_end_p (gsi) && gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
+    gsi_next (&gsi);
+
+  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);
+}
+
 /* 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:
@@ -475,23 +506,7 @@ assert_unreachable_fallthru_edge_p (edge
       basic_block other_bb = EDGE_SUCC (pred_bb, 0)->dest;
       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_unreachable_bb_p (other_bb);
     }
   return false;
 }
@@ -1668,9 +1683,10 @@ 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
+	  || gimple_unreachable_bb_p (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_unreachable_bb_p (basic_block);
 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,20 @@ 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 (gimple_unreachable_bb_p (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;

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

[Bernhard Reutner-Fischer]

On Wed, Apr 26, 2017 at 10:39:12PM -0500, Peter Bergner wrote:
> +/* Returns true if the basic block BB has no successors and only contains
> +   a call to __builtin_unreachable ().  */

so
  return EDGE_COUNT (bb->succs) == 0
    && (gsi = gsi_last_nondebug_bb (bb))
    && !gsi_end_p (gsi)
    && gimple_call_builtin_p (gsi_stmt (gsi), BUILT_IN_UNREACHABLE);

or at least
  if (EDGE_COUNT (bb->succs) != 0)
    return false;
  /* there is also a first_non_label_stmt() in tree-cfg.c ?! */
  gsi = gsi_start_nondebug_after_labels_bb (bb);
  if (gsi_end_p (gsi))
    return false;
  while (gimple_clobber_p (gsi_stmt (gsi)))
    {
      gsi_next (&gsi);
      if (gsi_end_p (gsi))
	return false;
    }
  return gimple_call_builtin_p (stmt, BUILT_IN_UNREACHABLE);

which i should better phrase as
  gsi = gsi_start_nondebug_after_labels_bb (bb);
  while (!gsi_end_p (gsi)
    {
      gimple *stmt = gsi_stmt (gsi);
      if (gimple_clobber_p (stmt))
	gsi_next (&gsi);
      else
        return gimple_call_builtin_p (stmt, BUILT_IN_UNREACHABLE);
    }
  return false;

No comment on the patch itself.

cheers,
> +
> +bool
> +gimple_unreachable_bb_p (basic_block bb)
> +{
> +  gimple_stmt_iterator gsi;
> +  gimple_seq stmts = bb_seq (bb);
> +  gimple *stmt;
> +
> +  if (EDGE_COUNT (bb->succs) != 0)
> +    return false;
> +
> +  gsi = gsi_start (stmts);
> +  while (!gsi_end_p (gsi) && gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
> +    gsi_next (&gsi);
> +
> +  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);
> +}
> +
>  /* 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:
> @@ -475,23 +506,7 @@ assert_unreachable_fallthru_edge_p (edge
>        basic_block other_bb = EDGE_SUCC (pred_bb, 0)->dest;
>        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_unreachable_bb_p (other_bb);
>      }
>    return false;
>  }
> @@ -1668,9 +1683,10 @@ 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
> +	  || gimple_unreachable_bb_p (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_unreachable_bb_p (basic_block);
>  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,20 @@ 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 (gimple_unreachable_bb_p (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;
> 
> 

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

[Peter Bergner]

On 4/27/17 6:57 AM, Bernhard Reutner-Fischer wrote:
> On Wed, Apr 26, 2017 at 10:39:12PM -0500, Peter Bergner wrote:
>> +/* Returns true if the basic block BB has no successors and only contains
>> +   a call to __builtin_unreachable ().  */
> 
> so
>   return EDGE_COUNT (bb->succs) == 0
>     && (gsi = gsi_last_nondebug_bb (bb))
>     && !gsi_end_p (gsi)
>     && gimple_call_builtin_p (gsi_stmt (gsi), BUILT_IN_UNREACHABLE);
[snip]
> which i should better phrase as
>   gsi = gsi_start_nondebug_after_labels_bb (bb);
>   while (!gsi_end_p (gsi)
>     {
>       gimple *stmt = gsi_stmt (gsi);
>       if (gimple_clobber_p (stmt))
> 	gsi_next (&gsi);
>       else
>         return gimple_call_builtin_p (stmt, BUILT_IN_UNREACHABLE);
>     }
>   return false;

I didn't try to rewrite the code too much, I basically just outlined
the code as is.  However, one change I did have to make, was to not
use routines like gsi_after_labels(), etc., since those do not work
during expansion to RTL, due to bb->flags == BB_RTL.  Those off limits
routines include gsi_start_nondebug_after_labels_bb(), since it calls
gsi_after_labels().

Peter

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

[Richard Biener]

On Wed, 26 Apr 2017, Peter Bergner wrote:

> On 4/20/17 8:26 AM, Peter Bergner wrote:
> > On 4/20/17 2:37 AM, Richard Biener wrote:
> >> Ok, so I think we should ensure that we remove the regular cases
> >> with unreachable destination, like in
> >>
> >> switch (i)
> >> {
> >> case 0:
> >>   __builtin_unreachable ();
> >> default:;
> >> }
> >>
> >> and handle default with __builtin_unreachable () from switch
> >> expansion by omitting the range check for the jump table
> >> indexing (and choose a non-default case label for gaps).
> > 
> > Ok, I'll modify optimize_unreachable() to remove the unreachable
> > case statements, and leave the unreachable default case statement
> > for switch expansion so we can eliminate the range check.  Thanks.
> 
> Ok, I lied. :-)  It ended up being a fair amount of code to remove
> the unreachable case statements within optimize_unreachable().
> Instead, I hooked into group_case_labels_stmt() which is much
> simpler!  That code eliminates all case statements that have the
> same destination as the default case statement.  With the patch,
> we also eliminate case statements that are unreachable, thus
> treating them like default cases.  This has the added benefit of
> being able to reduce the size of the dispatch table, if those cases
> were at the end of the dispatch table entries.
> 
> One difference from the last patch is that I am no longer setting
> default_label to NULL when we emit a decision tree.  I noticed that
> the decision tree code seemed to generate slightly better code for
> some of my unit tests if I left it alone.  This simplified the
> patch somewhat by removing the changes to emit_case_nodes().
> 
> This passed bootstrap and regtesting on powerpc64le-linux and
> x86_64-linux.  Is this ok for trunk now?  If so, I can hold off
> committing it until GCC 7 has been released if that helps.

Can you do the gimple_unreachable_bb_p check earlier in
expand_case so it covers the emit_case_decision_tree path as well
(and verify that works, of course)?  So basically right at

  /* Find the default case target label.  */
  default_label = jump_target_rtx
      (CASE_LABEL (gimple_switch_default_label (stmt)));
  edge default_edge = EDGE_SUCC (bb, 0);
  int default_prob = default_edge->probability;

handle this case.

As for Bernhards concern I share this -- please intead make the
interface take either a gimple_seq or a gimple_stmt_iterator
instead of a basic-block.  That makes it more obvious you
can't use things like gsi_after_labels.  Also I think it's more
natural to work backwards as the last stmt in the sequence
_has_ to be __builtin_unreachable () and thus checking that first
is the cheapest thing to do given that in most cases it will
not be __builtin_unreachable () (but a noreturn call or an
inifinite loop).

Thus, name it gimple_seq_unreachable_p.

Thanks,
Richard.

> Peter
> 
> 
> gcc/
> 	* tree-cfg.c (gimple_unreachable_bb_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.
> 	* gcc/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,37 @@ computed_goto_p (gimple *t)
>  	  && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL);
>  }
>  
> +/* Returns true if the basic block BB has no successors and only contains
> +   a call to __builtin_unreachable ().  */
> +
> +bool
> +gimple_unreachable_bb_p (basic_block bb)
> +{
> +  gimple_stmt_iterator gsi;
> +  gimple_seq stmts = bb_seq (bb);
> +  gimple *stmt;
> +
> +  if (EDGE_COUNT (bb->succs) != 0)
> +    return false;
> +
> +  gsi = gsi_start (stmts);
> +  while (!gsi_end_p (gsi) && gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
> +    gsi_next (&gsi);
> +
> +  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);
> +}
> +
>  /* 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:
> @@ -475,23 +506,7 @@ assert_unreachable_fallthru_edge_p (edge
>        basic_block other_bb = EDGE_SUCC (pred_bb, 0)->dest;
>        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_unreachable_bb_p (other_bb);
>      }
>    return false;
>  }
> @@ -1668,9 +1683,10 @@ 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
> +	  || gimple_unreachable_bb_p (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_unreachable_bb_p (basic_block);
>  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,20 @@ 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 (gimple_unreachable_bb_p (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)

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

[Peter Bergner]

On 05/03/2017 08:32 AM, Richard Biener wrote:
 > As for Bernhards concern I share this -- please intead make the
 > interface take either a gimple_seq or a gimple_stmt_iterator
 > instead of a basic-block.  That makes it more obvious you
 > can't use things like gsi_after_labels.  Also I think it's more
 > natural to work backwards as the last stmt in the sequence
 > _has_ to be __builtin_unreachable () and thus checking that first
 > is the cheapest thing to do given that in most cases it will
 > not be __builtin_unreachable () (but a noreturn call or an
 > inifinite loop).
 >
 > Thus, name it gimple_seq_unreachable_p.

So you mean something like the following?


/* Returns true if the sequence of statements STMTS only contains
    a call to __builtin_unreachable ().  */

bool
gimple_seq_unreachable_p (gimple_seq stmts)
{
   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;
}



 > On Wed, 26 Apr 2017, Peter Bergner wrote:
 >> One difference from the last patch is that I am no longer setting
 >> default_label to NULL when we emit a decision tree.  I noticed that
 >> the decision tree code seemed to generate slightly better code for
 >> some of my unit tests if I left it alone.  This simplified the
 >> patch somewhat by removing the changes to emit_case_nodes().
[snip]
 >
 > Can you do the gimple_unreachable_bb_p check earlier in
 > expand_case so it covers the emit_case_decision_tree path as well
 > (and verify that works, of course)?  So basically right at
 >
 >   /* Find the default case target label.  */
 >   default_label = jump_target_rtx
 >       (CASE_LABEL (gimple_switch_default_label (stmt)));
 >   edge default_edge = EDGE_SUCC (bb, 0);
 >   int default_prob = default_edge->probability;
 >
 > handle this case.

That is what the previous patch did, but as I mention above,
we generate slightly better code for some test cases (other
tests seemed to generate the same code) if we don't attempt
to handle the decision tree case.  I'll note that the current
unpatched compiler already knows how to remove unreachable
case statement blocks when we expand to a decision tree.

I can add that code back if you think that it will have a
positive benefit for some test case I haven't tried yet.

Peter

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

[Richard Biener]

On May 8, 2017 6:41:01 PM GMT+02:00, Peter Bergner <bergner@vnet.ibm.com> wrote:
>On 05/03/2017 08:32 AM, Richard Biener wrote:
> > As for Bernhards concern I share this -- please intead make the
> > interface take either a gimple_seq or a gimple_stmt_iterator
> > instead of a basic-block.  That makes it more obvious you
> > can't use things like gsi_after_labels.  Also I think it's more
> > natural to work backwards as the last stmt in the sequence
> > _has_ to be __builtin_unreachable () and thus checking that first
> > is the cheapest thing to do given that in most cases it will
> > not be __builtin_unreachable () (but a noreturn call or an
> > inifinite loop).
> >
> > Thus, name it gimple_seq_unreachable_p.
>
>So you mean something like the following?

Yes.

>
>/* Returns true if the sequence of statements STMTS only contains
>    a call to __builtin_unreachable ().  */
>
>bool
>gimple_seq_unreachable_p (gimple_seq stmts)
>{
>   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;
>}
>
>
>
> > On Wed, 26 Apr 2017, Peter Bergner wrote:
> >> One difference from the last patch is that I am no longer setting
> >> default_label to NULL when we emit a decision tree.  I noticed that
> >> the decision tree code seemed to generate slightly better code for
> >> some of my unit tests if I left it alone.  This simplified the
> >> patch somewhat by removing the changes to emit_case_nodes().
>[snip]
> >
> > Can you do the gimple_unreachable_bb_p check earlier in
> > expand_case so it covers the emit_case_decision_tree path as well
> > (and verify that works, of course)?  So basically right at
> >
> >   /* Find the default case target label.  */
> >   default_label = jump_target_rtx
> >       (CASE_LABEL (gimple_switch_default_label (stmt)));
> >   edge default_edge = EDGE_SUCC (bb, 0);
> >   int default_prob = default_edge->probability;
> >
> > handle this case.
>
>That is what the previous patch did, but as I mention above,
>we generate slightly better code for some test cases (other
>tests seemed to generate the same code) if we don't attempt
>to handle the decision tree case.  I'll note that the current
>unpatched compiler already knows how to remove unreachable
>case statement blocks when we expand to a decision tree.
>
>I can add that code back if you think that it will have a
>positive benefit for some test case I haven't tried yet.
>
>Peter

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

[Peter Bergner]

On 05/08/2017 12:44 PM, Richard Biener wrote:

>>> On Wed, 26 Apr 2017, Peter Bergner wrote:
>>>> One difference from the last patch is that I am no longer setting
>>>> default_label to NULL when we emit a decision tree.  I noticed that
>>>> the decision tree code seemed to generate slightly better code for
>>>> some of my unit tests if I left it alone.  This simplified the
>>>> patch somewhat by removing the changes to emit_case_nodes().
>> [snip]
>>> Can you do the gimple_unreachable_bb_p check earlier in
>>> expand_case so it covers the emit_case_decision_tree path as well
>>> (and verify that works, of course)?  So basically right at
>>>
>>>    /* Find the default case target label.  */
>>>    default_label = jump_target_rtx
>>>        (CASE_LABEL (gimple_switch_default_label (stmt)));
>>>    edge default_edge = EDGE_SUCC (bb, 0);
>>>    int default_prob = default_edge->probability;
>>>
>>> handle this case.
>> That is what the previous patch did, but as I mention above,
>> we generate slightly better code for some test cases (other
>> tests seemed to generate the same code) if we don't attempt
>> to handle the decision tree case.  I'll note that the current
>> unpatched compiler already knows how to remove unreachable
>> case statement blocks when we expand to a decision tree.
>>
>> I can add that code back if you think that it will have a
>> positive benefit for some test case I haven't tried yet.

Any comment on the above?

Peter

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

[Peter Bergner]

On 05/08/2017 01:20 PM, Peter Bergner wrote:
 > That is what the previous patch did, but as I mention above,
 > we generate slightly better code for some test cases (other
 > tests seemed to generate the same code) if we don't attempt
 > to handle the decision tree case.  I'll note that the current
 > unpatched compiler already knows how to remove unreachable
 > case statement blocks when we expand to a decision tree.

I should be more careful with my description here.  The patch does
affect both unreachable case statements for both decision trees as
well as jump tables, and that leads to improved code for both
decision trees as well as jump tables.

What I meant to say above, is that the current handling of unreachable
default case statements in the unpatched compiler seems to lead to
slightly better code for some test cases than attempting to handle
default_label == NULL in the decision tree code.  It was for that
reason, I placed the code in expand_case() only in the jump table
path.  The fact it made the patch smaller was a bonus, since I didn't
need to protect emit_case_nodes() from a NULL default_label.

As I said, if you think it will help some test case I haven't tried yet,
I can add that support back.

Peter

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

[Richard Biener]

On Mon, 8 May 2017, Peter Bergner wrote:

> On 05/08/2017 01:20 PM, Peter Bergner wrote:
> > That is what the previous patch did, but as I mention above,
> > we generate slightly better code for some test cases (other
> > tests seemed to generate the same code) if we don't attempt
> > to handle the decision tree case.  I'll note that the current
> > unpatched compiler already knows how to remove unreachable
> > case statement blocks when we expand to a decision tree.
> 
> I should be more careful with my description here.  The patch does
> affect both unreachable case statements for both decision trees as
> well as jump tables, and that leads to improved code for both
> decision trees as well as jump tables.
> 
> What I meant to say above, is that the current handling of unreachable
> default case statements in the unpatched compiler seems to lead to
> slightly better code for some test cases than attempting to handle
> default_label == NULL in the decision tree code.  It was for that
> reason, I placed the code in expand_case() only in the jump table
> path.  The fact it made the patch smaller was a bonus, since I didn't
> need to protect emit_case_nodes() from a NULL default_label.

Ah, ok.

> As I said, if you think it will help some test case I haven't tried yet,
> I can add that support back.

Well, let's to that incremental then, if at all.

Thanks,
Richard.