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

[Richard Biener <rguenther at suse dot de>]

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)