tree-cfg: Fix ICE with switch stmt to unreachable opt and forced labels [PR95857]

Message ID 20200702090221.GN8462@tucnak
State New
Headers show
Series
  • tree-cfg: Fix ICE with switch stmt to unreachable opt and forced labels [PR95857]
Related show

Commit Message

Jakub Jelinek via Gcc-patches July 2, 2020, 9:02 a.m.
Hi!

The following testcase ICEs, because during the cfg cleanup, we see:
  switch (i$e_11) <default: <L12> [33.33%], case -3: <lab2> [33.33%], case 0: <L10> [33.33%], case 2: <lab2> [33.33%]>
...
lab2:
  __builtin_unreachable ();
where lab2 is FORCED_LABEL.  The way it works, we go through the case labels
and when we reach the first one that points to gimple_seq_unreachable*
basic block, we remove the edge (if any) from the switch bb to the bb
containing the label and bbs reachable only through that edge we've just
removed.  Once we do that, we must throw away all other cases that use
the same label (or some other labels from the same bb we've removed the edge
to and the bb).  To avoid quadratic behavior, this is not done by walking
all remaining cases immediately before removing, but only when processing
them later.
For normal labels this works, fine, if the label is in a deleted bb, it will
have NULL label_to_block and we handle that case, or, if the unreachable bb
has some other edge to it, only the edge will be removed and not the bb,
and again, find_edge will not find the edge and we only remove the case.
And if a label would be to some other block, that other block wouldn't have
been removed earlier because there would be still an edge from the switch
block.
Now, FORCED_LABEL (and I think DECL_NONLOCAL too) break this, because
those labels aren't removed, but instead moved to some surrounding basic
block.  So, when we later process those, when their gimple_seq_unreachable*
basic block is removed, label_to_block will return some unrelated block
(in the testcase the switch bb), so we decide to keep the case which doesn't
seem to be unreachable, but we don't really have an edge from the switch
block to the block the label got moved to.

I thought first about punting in gimple_seq_unreachable* on
FORCED_LABEL/DECL_NONLOCAL labels, but that might penalize even code that
doesn't care, so this instead just makes sure that for
FORCED_LABEL/DECL_NONLOCAL labels that are being removed (and thus moved
randomly) we remember in a hash_set the fact that those labels should be
treated as removed for the purpose of the optimization, and later on
handle those labels that way.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

2020-07-02  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/95857
	* tree-cfg.c (group_case_labels_stmt): When removing an unreachable
	base_bb, remember all forced and non-local labels on it and later
	treat those as if they have NULL label_to_block.  Formatting fix.
	Fix a comment typo.

	* gcc.dg/pr95857.c: New test.


	Jakub

Comments

Jakub Jelinek via Gcc-patches July 2, 2020, 9:24 a.m. | #1
On Thu, Jul 2, 2020 at 11:03 AM Jakub Jelinek via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>

> Hi!

>

> The following testcase ICEs, because during the cfg cleanup, we see:

>   switch (i$e_11) <default: <L12> [33.33%], case -3: <lab2> [33.33%], case 0: <L10> [33.33%], case 2: <lab2> [33.33%]>

> ...

> lab2:

>   __builtin_unreachable ();

> where lab2 is FORCED_LABEL.  The way it works, we go through the case labels

> and when we reach the first one that points to gimple_seq_unreachable*

> basic block, we remove the edge (if any) from the switch bb to the bb

> containing the label and bbs reachable only through that edge we've just

> removed.  Once we do that, we must throw away all other cases that use

> the same label (or some other labels from the same bb we've removed the edge

> to and the bb).  To avoid quadratic behavior, this is not done by walking

> all remaining cases immediately before removing, but only when processing

> them later.

> For normal labels this works, fine, if the label is in a deleted bb, it will

> have NULL label_to_block and we handle that case, or, if the unreachable bb

> has some other edge to it, only the edge will be removed and not the bb,

> and again, find_edge will not find the edge and we only remove the case.

> And if a label would be to some other block, that other block wouldn't have

> been removed earlier because there would be still an edge from the switch

> block.

> Now, FORCED_LABEL (and I think DECL_NONLOCAL too) break this, because

> those labels aren't removed, but instead moved to some surrounding basic

> block.  So, when we later process those, when their gimple_seq_unreachable*

> basic block is removed, label_to_block will return some unrelated block

> (in the testcase the switch bb), so we decide to keep the case which doesn't

> seem to be unreachable, but we don't really have an edge from the switch

> block to the block the label got moved to.

>

> I thought first about punting in gimple_seq_unreachable* on

> FORCED_LABEL/DECL_NONLOCAL labels, but that might penalize even code that

> doesn't care, so this instead just makes sure that for

> FORCED_LABEL/DECL_NONLOCAL labels that are being removed (and thus moved

> randomly) we remember in a hash_set the fact that those labels should be

> treated as removed for the purpose of the optimization, and later on

> handle those labels that way.

>

> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?


OK.

Richard.

> 2020-07-02  Jakub Jelinek  <jakub@redhat.com>

>

>         PR tree-optimization/95857

>         * tree-cfg.c (group_case_labels_stmt): When removing an unreachable

>         base_bb, remember all forced and non-local labels on it and later

>         treat those as if they have NULL label_to_block.  Formatting fix.

>         Fix a comment typo.

>

>         * gcc.dg/pr95857.c: New test.

>

> --- gcc/tree-cfg.c.jj   2020-06-30 11:18:52.981737596 +0200

> +++ gcc/tree-cfg.c      2020-06-30 12:50:22.068246981 +0200

> @@ -1728,6 +1728,7 @@ group_case_labels_stmt (gswitch *stmt)

>    int old_size = gimple_switch_num_labels (stmt);

>    int i, next_index, new_size;

>    basic_block default_bb = NULL;

> +  hash_set<tree> *removed_labels = NULL;

>

>    default_bb = gimple_switch_default_bb (cfun, stmt);

>

> @@ -1744,8 +1745,11 @@ group_case_labels_stmt (gswitch *stmt)

>        base_bb = label_to_block (cfun, CASE_LABEL (base_case));

>

>        /* Discard cases that have the same destination as the default case or

> -        whose destiniation blocks have already been removed as unreachable.  */

> -      if (base_bb == NULL || base_bb == default_bb)

> +        whose destination blocks have already been removed as unreachable.  */

> +      if (base_bb == NULL

> +         || base_bb == default_bb

> +         || (removed_labels

> +             && removed_labels->contains (CASE_LABEL (base_case))))

>         {

>           i++;

>           continue;

> @@ -1768,10 +1772,13 @@ group_case_labels_stmt (gswitch *stmt)

>           /* Merge the cases if they jump to the same place,

>              and their ranges are consecutive.  */

>           if (merge_bb == base_bb

> +             && (removed_labels == NULL

> +                 || !removed_labels->contains (CASE_LABEL (merge_case)))

>               && wi::to_wide (CASE_LOW (merge_case)) == bhp1)

>             {

> -             base_high = CASE_HIGH (merge_case) ?

> -                 CASE_HIGH (merge_case) : CASE_LOW (merge_case);

> +             base_high

> +               = (CASE_HIGH (merge_case)

> +                  ? CASE_HIGH (merge_case) : CASE_LOW (merge_case));

>               CASE_HIGH (base_case) = base_high;

>               next_index++;

>             }

> @@ -1792,7 +1799,29 @@ 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);

> +           {

> +             for (gimple_stmt_iterator gsi = gsi_start_bb (base_bb);

> +                  !gsi_end_p (gsi); gsi_next (&gsi))

> +               if (glabel *stmt = dyn_cast <glabel *> (gsi_stmt (gsi)))

> +                 {

> +                   if (FORCED_LABEL (gimple_label_label (stmt))

> +                       || DECL_NONLOCAL (gimple_label_label (stmt)))

> +                     {

> +                       /* Forced/non-local labels aren't going to be removed,

> +                          but they will be moved to some neighbouring basic

> +                          block. If some later case label refers to one of

> +                          those labels, we should throw that case away rather

> +                          than keeping it around and refering to some random

> +                          other basic block without an edge to it.  */

> +                       if (removed_labels == NULL)

> +                         removed_labels = new hash_set<tree>;

> +                       removed_labels->add (gimple_label_label (stmt));

> +                     }

> +                 }

> +               else

> +                 break;

> +             remove_edge_and_dominated_blocks (base_edge);

> +           }

>           i = next_index;

>           continue;

>         }

> @@ -1809,6 +1838,7 @@ group_case_labels_stmt (gswitch *stmt)

>    if (new_size < old_size)

>      gimple_switch_set_num_labels (stmt, new_size);

>

> +  delete removed_labels;

>    return new_size < old_size;

>  }

>

> --- gcc/testsuite/gcc.dg/pr95857.c.jj   2020-06-30 12:48:53.574511328 +0200

> +++ gcc/testsuite/gcc.dg/pr95857.c      2020-06-30 12:48:53.574511328 +0200

> @@ -0,0 +1,37 @@

> +/* PR tree-optimization/95857 */

> +/* { dg-do compile } */

> +/* { dg-options "-O2" } */

> +

> +struct E { int e; };

> +int bar (void), baz (void);

> +void qux (void *);

> +

> +void

> +foo (int x)

> +{

> +  struct E a = { 0 };

> +  struct E i = { 0 };

> +  qux (&&lab2);

> +  if (baz ())

> +    i.e = 1;

> +  else

> +    a.e = -2;

> +  switch (a.e)

> +    {

> +    case -2:

> +    lab1:

> +      switch (i.e)

> +       {

> +       case -3:

> +       case 2:

> +         if (i.e-- != 2)

> +           __builtin_unreachable ();

> +       lab2:

> +         baz ();

> +         goto lab1;

> +       case 0:

> +         bar ();

> +       }

> +      break;

> +    }

> +}

>

>         Jakub

>

Patch

--- gcc/tree-cfg.c.jj	2020-06-30 11:18:52.981737596 +0200
+++ gcc/tree-cfg.c	2020-06-30 12:50:22.068246981 +0200
@@ -1728,6 +1728,7 @@  group_case_labels_stmt (gswitch *stmt)
   int old_size = gimple_switch_num_labels (stmt);
   int i, next_index, new_size;
   basic_block default_bb = NULL;
+  hash_set<tree> *removed_labels = NULL;
 
   default_bb = gimple_switch_default_bb (cfun, stmt);
 
@@ -1744,8 +1745,11 @@  group_case_labels_stmt (gswitch *stmt)
       base_bb = label_to_block (cfun, CASE_LABEL (base_case));
 
       /* Discard cases that have the same destination as the default case or
-	 whose destiniation blocks have already been removed as unreachable.  */
-      if (base_bb == NULL || base_bb == default_bb)
+	 whose destination blocks have already been removed as unreachable.  */
+      if (base_bb == NULL
+	  || base_bb == default_bb
+	  || (removed_labels
+	      && removed_labels->contains (CASE_LABEL (base_case))))
 	{
 	  i++;
 	  continue;
@@ -1768,10 +1772,13 @@  group_case_labels_stmt (gswitch *stmt)
 	  /* Merge the cases if they jump to the same place,
 	     and their ranges are consecutive.  */
 	  if (merge_bb == base_bb
+	      && (removed_labels == NULL
+		  || !removed_labels->contains (CASE_LABEL (merge_case)))
 	      && wi::to_wide (CASE_LOW (merge_case)) == bhp1)
 	    {
-	      base_high = CASE_HIGH (merge_case) ?
-		  CASE_HIGH (merge_case) : CASE_LOW (merge_case);
+	      base_high
+		= (CASE_HIGH (merge_case)
+		   ? CASE_HIGH (merge_case) : CASE_LOW (merge_case));
 	      CASE_HIGH (base_case) = base_high;
 	      next_index++;
 	    }
@@ -1792,7 +1799,29 @@  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);
+	    {
+	      for (gimple_stmt_iterator gsi = gsi_start_bb (base_bb);
+		   !gsi_end_p (gsi); gsi_next (&gsi))
+		if (glabel *stmt = dyn_cast <glabel *> (gsi_stmt (gsi)))
+		  {
+		    if (FORCED_LABEL (gimple_label_label (stmt))
+			|| DECL_NONLOCAL (gimple_label_label (stmt)))
+		      {
+			/* Forced/non-local labels aren't going to be removed,
+			   but they will be moved to some neighbouring basic
+			   block. If some later case label refers to one of
+			   those labels, we should throw that case away rather
+			   than keeping it around and refering to some random
+			   other basic block without an edge to it.  */
+			if (removed_labels == NULL)
+			  removed_labels = new hash_set<tree>;
+			removed_labels->add (gimple_label_label (stmt));
+		      }
+		  }
+		else
+		  break;
+	      remove_edge_and_dominated_blocks (base_edge);
+	    }
 	  i = next_index;
 	  continue;
 	}
@@ -1809,6 +1838,7 @@  group_case_labels_stmt (gswitch *stmt)
   if (new_size < old_size)
     gimple_switch_set_num_labels (stmt, new_size);
 
+  delete removed_labels;
   return new_size < old_size;
 }
 
--- gcc/testsuite/gcc.dg/pr95857.c.jj	2020-06-30 12:48:53.574511328 +0200
+++ gcc/testsuite/gcc.dg/pr95857.c	2020-06-30 12:48:53.574511328 +0200
@@ -0,0 +1,37 @@ 
+/* PR tree-optimization/95857 */
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+
+struct E { int e; };
+int bar (void), baz (void);
+void qux (void *);
+
+void
+foo (int x)
+{
+  struct E a = { 0 };
+  struct E i = { 0 };
+  qux (&&lab2);
+  if (baz ())
+    i.e = 1;
+  else
+    a.e = -2;
+  switch (a.e)
+    {
+    case -2:
+    lab1:
+      switch (i.e)
+	{
+	case -3:
+	case 2:
+	  if (i.e-- != 2)
+	    __builtin_unreachable ();
+	lab2:
+	  baz ();
+	  goto lab1;
+	case 0:
+	  bar ();
+	}
+      break;
+    }
+}