[PATCH] make find_taken_edge handle case with just default

[PATCH] make find_taken_edge handle case with just default

[Richard Biener]

This refactors things a bit to make CFG cleanup handle switches with
just a default label.  If we make sure to cleanup the CFG after
group_case_labels removes cases with just __builtin_unreachable ()
inside then this fixes the ICE seen in PR81994 as well.

I wonder if find_taken_edge should generally handle successors
with __builtin_unreachable () -- OTOH that would get rid of those
too early I guess.

Bootstrap / regtest running on x86_64-unknown-linux-gnu.

Richard.

2017-06-29  Richard Biener  <rguenther@suse.de>

	* tree-cfg.c (group_case_labels_stmt): Return whether we changed
	anything.
	(group_case_labels): Likewise.
	(find_taken_edge): Push sanity checking on val to workers...
	(find_taken_edge_cond_expr): ... here
	(find_taken_edge_switch_expr): ... and here, handle cases
	with just a default label.
	* tree-cfg.h (group_case_labels_stmt): Adjust prototype.
	(group_case_labels): Likewise.
	* tree-cfgcleanup.c (execute_cleanup_cfg_post_optimizing): When
	group_case_labels does anything cleanup the CFG again.

Index: gcc/tree-cfg.c
===================================================================
--- gcc/tree-cfg.c	(revision 249769)
+++ gcc/tree-cfg.c	(working copy)
@@ -1675,7 +1675,7 @@ cleanup_dead_labels (void)
    the ones jumping to the same label.
    Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
 
-void
+bool
 group_case_labels_stmt (gswitch *stmt)
 {
   int old_size = gimple_switch_num_labels (stmt);
@@ -1759,23 +1759,27 @@ group_case_labels_stmt (gswitch *stmt)
 
   gcc_assert (new_size <= old_size);
   gimple_switch_set_num_labels (stmt, new_size);
+  return new_size < old_size;
 }
 
 /* Look for blocks ending in a multiway branch (a GIMPLE_SWITCH),
    and scan the sorted vector of cases.  Combine the ones jumping to the
    same label.  */
 
-void
+bool
 group_case_labels (void)
 {
   basic_block bb;
+  bool changed = false;
 
   FOR_EACH_BB_FN (bb, cfun)
     {
       gimple *stmt = last_stmt (bb);
       if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
-	group_case_labels_stmt (as_a <gswitch *> (stmt));
+	changed |= group_case_labels_stmt (as_a <gswitch *> (stmt));
     }
+
+  return changed;
 }
 
 /* Checks whether we can merge block B into block A.  */
@@ -2243,15 +2247,8 @@ find_taken_edge (basic_block bb, tree va
 
   stmt = last_stmt (bb);
 
-  gcc_assert (stmt);
   gcc_assert (is_ctrl_stmt (stmt));
 
-  if (val == NULL)
-    return NULL;
-
-  if (!is_gimple_min_invariant (val))
-    return NULL;
-
   if (gimple_code (stmt) == GIMPLE_COND)
     return find_taken_edge_cond_expr (bb, val);
 
@@ -2266,7 +2263,8 @@ find_taken_edge (basic_block bb, tree va
          It may be the case that we only need to allow the LABEL_REF to
          appear inside an ADDR_EXPR, but we also allow the LABEL_REF to
          appear inside a LABEL_EXPR just to be safe.  */
-      if ((TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) == LABEL_EXPR)
+      if (val
+	  && (TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) == LABEL_EXPR)
 	  && TREE_CODE (TREE_OPERAND (val, 0)) == LABEL_DECL)
 	return find_taken_edge_computed_goto (bb, TREE_OPERAND (val, 0));
       return NULL;
@@ -2304,9 +2302,12 @@ find_taken_edge_cond_expr (basic_block b
 {
   edge true_edge, false_edge;
 
+  if (val == NULL
+      || TREE_CODE (val) != INTEGER_CST)
+    return NULL;
+
   extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
 
-  gcc_assert (TREE_CODE (val) == INTEGER_CST);
   return (integer_zerop (val) ? false_edge : true_edge);
 }
 
@@ -2322,7 +2323,12 @@ find_taken_edge_switch_expr (gswitch *sw
   edge e;
   tree taken_case;
 
-  taken_case = find_case_label_for_value (switch_stmt, val);
+  if (gimple_switch_num_labels (switch_stmt) == 1)
+    taken_case = gimple_switch_default_label (switch_stmt);
+  else if (! val || TREE_CODE (val) != INTEGER_CST)
+    return NULL;
+  else
+    taken_case = find_case_label_for_value (switch_stmt, val);
   dest_bb = label_to_block (CASE_LABEL (taken_case));
 
   e = find_edge (bb, dest_bb);
Index: gcc/tree-cfg.h
===================================================================
--- gcc/tree-cfg.h	(revision 249769)
+++ gcc/tree-cfg.h	(working copy)
@@ -36,8 +36,8 @@ extern void end_recording_case_labels (v
 extern basic_block label_to_block_fn (struct function *, tree);
 #define label_to_block(t) (label_to_block_fn (cfun, t))
 extern void cleanup_dead_labels (void);
-extern void group_case_labels_stmt (gswitch *);
-extern void group_case_labels (void);
+extern bool group_case_labels_stmt (gswitch *);
+extern bool group_case_labels (void);
 extern void replace_uses_by (tree, tree);
 extern basic_block single_noncomplex_succ (basic_block bb);
 extern void notice_special_calls (gcall *);
Index: gcc/tree-cfgcleanup.c
===================================================================
--- gcc/tree-cfgcleanup.c	(revision 249769)
+++ gcc/tree-cfgcleanup.c	(working copy)
@@ -1205,7 +1205,8 @@ execute_cleanup_cfg_post_optimizing (voi
     }
   maybe_remove_unreachable_handlers ();
   cleanup_dead_labels ();
-  group_case_labels ();
+  if (group_case_labels ())
+    todo |= TODO_cleanup_cfg;
   if ((flag_compare_debug_opt || flag_compare_debug)
       && flag_dump_final_insns)
     {

Re: [PATCH] make find_taken_edge handle case with just default

[Peter Bergner]

On 6/29/17 4:03 AM, Richard Biener wrote:
> 
> This refactors things a bit to make CFG cleanup handle switches with
> just a default label.  If we make sure to cleanup the CFG after
> group_case_labels removes cases with just __builtin_unreachable ()
> inside then this fixes the ICE seen in PR81994 as well.
> 
> I wonder if find_taken_edge should generally handle successors
> with __builtin_unreachable () -- OTOH that would get rid of those
> too early I guess.

Should we offer an early out of group_case_labels_stmt() for the
fairly common case of new_size == old_size?  There's no reason to
execute the compress labels loop if we didn't combine any of the
labels.

Peter


Index: gcc/tree-cfg.c
===================================================================
--- gcc/tree-cfg.c	(revision 249783)
+++ gcc/tree-cfg.c	(working copy)
@@ -1747,6 +1747,11 @@ group_case_labels_stmt (gswitch *stmt)
 	}
     }

+  gcc_assert (new_size <= old_size);
+
+  if (new_size == old_size)
+    return false;
+
   /* Compress the case labels in the label vector, and adjust the
      length of the vector.  */
   for (i = 0, j = 0; i < new_size; i++)
@@ -1757,9 +1762,8 @@ group_case_labels_stmt (gswitch *stmt)
 			       gimple_switch_label (stmt, j++));
     }

-  gcc_assert (new_size <= old_size);
   gimple_switch_set_num_labels (stmt, new_size);
-  return new_size < old_size;
+  return true;
 }

 /* Look for blocks ending in a multiway branch (a GIMPLE_SWITCH),

Re: [PATCH] make find_taken_edge handle case with just default

[Richard Biener]

On Thu, 29 Jun 2017, Peter Bergner wrote:

> On 6/29/17 4:03 AM, Richard Biener wrote:
> > 
> > This refactors things a bit to make CFG cleanup handle switches with
> > just a default label.  If we make sure to cleanup the CFG after
> > group_case_labels removes cases with just __builtin_unreachable ()
> > inside then this fixes the ICE seen in PR81994 as well.
> > 
> > I wonder if find_taken_edge should generally handle successors
> > with __builtin_unreachable () -- OTOH that would get rid of those
> > too early I guess.
> 
> Should we offer an early out of group_case_labels_stmt() for the
> fairly common case of new_size == old_size?  There's no reason to
> execute the compress labels loop if we didn't combine any of the
> labels.

We can also merge both loops, counting new_size upwards, storing
to label new_size if new_size != i ...

> Peter
> 
> 
> Index: gcc/tree-cfg.c
> ===================================================================
> --- gcc/tree-cfg.c	(revision 249783)
> +++ gcc/tree-cfg.c	(working copy)
> @@ -1747,6 +1747,11 @@ group_case_labels_stmt (gswitch *stmt)
>  	}
>      }
> 
> +  gcc_assert (new_size <= old_size);
> +
> +  if (new_size == old_size)
> +    return false;
> +
>    /* Compress the case labels in the label vector, and adjust the
>       length of the vector.  */
>    for (i = 0, j = 0; i < new_size; i++)
> @@ -1757,9 +1762,8 @@ group_case_labels_stmt (gswitch *stmt)
>  			       gimple_switch_label (stmt, j++));
>      }
> 
> -  gcc_assert (new_size <= old_size);
>    gimple_switch_set_num_labels (stmt, new_size);
> -  return new_size < old_size;
> +  return true;
>  }
> 
>  /* Look for blocks ending in a multiway branch (a GIMPLE_SWITCH),
> 
> 

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

Re: [PATCH] make find_taken_edge handle case with just default

[Peter Bergner]

On 6/29/17 8:58 AM, Richard Biener wrote:
> On Thu, 29 Jun 2017, Peter Bergner wrote:
>> Should we offer an early out of group_case_labels_stmt() for the
>> fairly common case of new_size == old_size?  There's no reason to
>> execute the compress labels loop if we didn't combine any of the
>> labels.
> 
> We can also merge both loops, counting new_size upwards, storing
> to label new_size if new_size != i ...

Yeah.  I can implement that if you like...unless you want to...
or already have. :-)

Peter

Re: [PATCH] make find_taken_edge handle case with just default

[Richard Biener]

On Thu, 29 Jun 2017, Peter Bergner wrote:

> On 6/29/17 8:58 AM, Richard Biener wrote:
> > On Thu, 29 Jun 2017, Peter Bergner wrote:
> >> Should we offer an early out of group_case_labels_stmt() for the
> >> fairly common case of new_size == old_size?  There's no reason to
> >> execute the compress labels loop if we didn't combine any of the
> >> labels.
> > 
> > We can also merge both loops, counting new_size upwards, storing
> > to label new_size if new_size != i ...
> 
> Yeah.  I can implement that if you like...unless you want to...
> or already have. :-)

Go ahead!

Richard.

Re: [PATCH] make find_taken_edge handle case with just default

[Peter Bergner]

On 6/29/17 8:58 AM, Richard Biener wrote:
> On Thu, 29 Jun 2017, Peter Bergner wrote:
> 
>> On 6/29/17 4:03 AM, Richard Biener wrote:
>>>
>>> This refactors things a bit to make CFG cleanup handle switches with
>>> just a default label.  If we make sure to cleanup the CFG after
>>> group_case_labels removes cases with just __builtin_unreachable ()
>>> inside then this fixes the ICE seen in PR81994 as well.
>>>
>>> I wonder if find_taken_edge should generally handle successors
>>> with __builtin_unreachable () -- OTOH that would get rid of those
>>> too early I guess.
>>
>> Should we offer an early out of group_case_labels_stmt() for the
>> fairly common case of new_size == old_size?  There's no reason to
>> execute the compress labels loop if we didn't combine any of the
>> labels.
> 
> We can also merge both loops, counting new_size upwards, storing
> to label new_size if new_size != i ...

Like this.  I'm bootstrapping and regtesting the following patch on
powerpc64le-linux.  Ok if it survives?

Peter

	* tree-cfg.c (group_case_labels_stmt): Merge scanning and compressing
	loops.  Remove now unneeded calls to gimple_switch_set_label() that
	just set removed labels to NULL_TREE.

Index: gcc/tree-cfg.c
===================================================================
--- gcc/tree-cfg.c	(revision 249801)
+++ gcc/tree-cfg.c	(working copy)
@@ -1679,13 +1679,13 @@ bool
 group_case_labels_stmt (gswitch *stmt)
 {
   int old_size = gimple_switch_num_labels (stmt);
-  int i, j, base_index, new_size = old_size;
+  int i, next_index, new_size;
   basic_block default_bb = NULL;

   default_bb = label_to_block (CASE_LABEL (gimple_switch_default_label (stmt)));

   /* Look for possible opportunities to merge cases.  */
-  i = 1;
+  new_size = i = 1;
   while (i < old_size)
     {
       tree base_case, base_high;
@@ -1699,23 +1699,21 @@ group_case_labels_stmt (gswitch *stmt)
       /* Discard cases that have the same destination as the default case.  */
       if (base_bb == default_bb)
	{
-	  gimple_switch_set_label (stmt, i, NULL_TREE);
	  i++;
-	  new_size--;
	  continue;
	}

       base_high = CASE_HIGH (base_case)
	  ? CASE_HIGH (base_case)
	  : CASE_LOW (base_case);
-      base_index = i++;
+      next_index = i + 1;

       /* Try to merge case labels.  Break out when we reach the end
	 of the label vector or when we cannot merge the next case
	 label with the current one.  */
-      while (i < old_size)
+      while (next_index < old_size)
	{
-	  tree merge_case = gimple_switch_label (stmt, i);
+	  tree merge_case = gimple_switch_label (stmt, next_index);
	  basic_block merge_bb = label_to_block (CASE_LABEL (merge_case));
	  wide_int bhp1 = wi::add (base_high, 1);

@@ -1727,9 +1725,7 @@ group_case_labels_stmt (gswitch *stmt)
	      base_high = CASE_HIGH (merge_case) ?
		  CASE_HIGH (merge_case) : CASE_LOW (merge_case);
	      CASE_HIGH (base_case) = base_high;
-	      gimple_switch_set_label (stmt, i, NULL_TREE);
-	      new_size--;
-	      i++;
+	      next_index++;
	    }
	  else
	    break;
@@ -1742,23 +1738,22 @@ group_case_labels_stmt (gswitch *stmt)
	  edge base_edge = find_edge (gimple_bb (stmt), base_bb);
	  if (base_edge != NULL)
	    remove_edge_and_dominated_blocks (base_edge);
-	  gimple_switch_set_label (stmt, base_index, NULL_TREE);
-	  new_size--;
+	  i = next_index;
+	  continue;
	}
-    }

-  /* Compress the case labels in the label vector, and adjust the
-     length of the vector.  */
-  for (i = 0, j = 0; i < new_size; i++)
-    {
-      while (! gimple_switch_label (stmt, j))
-	j++;
-      gimple_switch_set_label (stmt, i,
-			       gimple_switch_label (stmt, j++));
+      if (new_size < i)
+	gimple_switch_set_label (stmt, new_size,
+				 gimple_switch_label (stmt, i));
+      i = next_index;
+      new_size++;
     }

   gcc_assert (new_size <= old_size);
-  gimple_switch_set_num_labels (stmt, new_size);
+
+  if (new_size < old_size)
+    gimple_switch_set_num_labels (stmt, new_size);
+
   return new_size < old_size;
 }

Re: [PATCH] make find_taken_edge handle case with just default

[Richard Biener]

On Thu, 29 Jun 2017, Peter Bergner wrote:

> On 6/29/17 8:58 AM, Richard Biener wrote:
> > On Thu, 29 Jun 2017, Peter Bergner wrote:
> > 
> >> On 6/29/17 4:03 AM, Richard Biener wrote:
> >>>
> >>> This refactors things a bit to make CFG cleanup handle switches with
> >>> just a default label.  If we make sure to cleanup the CFG after
> >>> group_case_labels removes cases with just __builtin_unreachable ()
> >>> inside then this fixes the ICE seen in PR81994 as well.
> >>>
> >>> I wonder if find_taken_edge should generally handle successors
> >>> with __builtin_unreachable () -- OTOH that would get rid of those
> >>> too early I guess.
> >>
> >> Should we offer an early out of group_case_labels_stmt() for the
> >> fairly common case of new_size == old_size?  There's no reason to
> >> execute the compress labels loop if we didn't combine any of the
> >> labels.
> > 
> > We can also merge both loops, counting new_size upwards, storing
> > to label new_size if new_size != i ...
> 
> Like this.  I'm bootstrapping and regtesting the following patch on
> powerpc64le-linux.  Ok if it survives?

Looks good to me.

Thanks,
Richard.

> Peter
> 
> 	* tree-cfg.c (group_case_labels_stmt): Merge scanning and compressing
> 	loops.  Remove now unneeded calls to gimple_switch_set_label() that
> 	just set removed labels to NULL_TREE.
> 
> Index: gcc/tree-cfg.c
> ===================================================================
> --- gcc/tree-cfg.c	(revision 249801)
> +++ gcc/tree-cfg.c	(working copy)
> @@ -1679,13 +1679,13 @@ bool
>  group_case_labels_stmt (gswitch *stmt)
>  {
>    int old_size = gimple_switch_num_labels (stmt);
> -  int i, j, base_index, new_size = old_size;
> +  int i, next_index, new_size;
>    basic_block default_bb = NULL;
> 
>    default_bb = label_to_block (CASE_LABEL (gimple_switch_default_label (stmt)));
> 
>    /* Look for possible opportunities to merge cases.  */
> -  i = 1;
> +  new_size = i = 1;
>    while (i < old_size)
>      {
>        tree base_case, base_high;
> @@ -1699,23 +1699,21 @@ group_case_labels_stmt (gswitch *stmt)
>        /* Discard cases that have the same destination as the default case.  */
>        if (base_bb == default_bb)
> 	{
> -	  gimple_switch_set_label (stmt, i, NULL_TREE);
> 	  i++;
> -	  new_size--;
> 	  continue;
> 	}
> 
>        base_high = CASE_HIGH (base_case)
> 	  ? CASE_HIGH (base_case)
> 	  : CASE_LOW (base_case);
> -      base_index = i++;
> +      next_index = i + 1;
> 
>        /* Try to merge case labels.  Break out when we reach the end
> 	 of the label vector or when we cannot merge the next case
> 	 label with the current one.  */
> -      while (i < old_size)
> +      while (next_index < old_size)
> 	{
> -	  tree merge_case = gimple_switch_label (stmt, i);
> +	  tree merge_case = gimple_switch_label (stmt, next_index);
> 	  basic_block merge_bb = label_to_block (CASE_LABEL (merge_case));
> 	  wide_int bhp1 = wi::add (base_high, 1);
> 
> @@ -1727,9 +1725,7 @@ group_case_labels_stmt (gswitch *stmt)
> 	      base_high = CASE_HIGH (merge_case) ?
> 		  CASE_HIGH (merge_case) : CASE_LOW (merge_case);
> 	      CASE_HIGH (base_case) = base_high;
> -	      gimple_switch_set_label (stmt, i, NULL_TREE);
> -	      new_size--;
> -	      i++;
> +	      next_index++;
> 	    }
> 	  else
> 	    break;
> @@ -1742,23 +1738,22 @@ group_case_labels_stmt (gswitch *stmt)
> 	  edge base_edge = find_edge (gimple_bb (stmt), base_bb);
> 	  if (base_edge != NULL)
> 	    remove_edge_and_dominated_blocks (base_edge);
> -	  gimple_switch_set_label (stmt, base_index, NULL_TREE);
> -	  new_size--;
> +	  i = next_index;
> +	  continue;
> 	}
> -    }
> 
> -  /* Compress the case labels in the label vector, and adjust the
> -     length of the vector.  */
> -  for (i = 0, j = 0; i < new_size; i++)
> -    {
> -      while (! gimple_switch_label (stmt, j))
> -	j++;
> -      gimple_switch_set_label (stmt, i,
> -			       gimple_switch_label (stmt, j++));
> +      if (new_size < i)
> +	gimple_switch_set_label (stmt, new_size,
> +				 gimple_switch_label (stmt, i));
> +      i = next_index;
> +      new_size++;
>      }
> 
>    gcc_assert (new_size <= old_size);
> -  gimple_switch_set_num_labels (stmt, new_size);
> +
> +  if (new_size < old_size)
> +    gimple_switch_set_num_labels (stmt, new_size);
> +
>    return new_size < old_size;
>  }
> 
> 
> 

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

Re: [PATCH] make find_taken_edge handle case with just default

[Peter Bergner]

On 6/30/17 3:27 AM, Richard Biener wrote:
> On Thu, 29 Jun 2017, Peter Bergner wrote:
>> On 6/29/17 8:58 AM, Richard Biener wrote:
>>> We can also merge both loops, counting new_size upwards, storing
>>> to label new_size if new_size != i ...
>>
>> Like this.  I'm bootstrapping and regtesting the following patch on
>> powerpc64le-linux.  Ok if it survives?
> 
> Looks good to me.

Bootstrap / regtest was clean on both powerpc64le-linux and x86_64-linux.
Committed as revision 249847.  Thanks!

Peter