[PATCH] Improve forward jump threading of switch statements (PR18046)

[PATCH] Improve forward jump threading of switch statements (PR18046)

[Patrick Palka]

This patch improves the forward jump threader's ability to thread
GIMPLE_SWITCHes by making the VRP simplification callback attempt to
determine which case label will be taken.

For example, if the index operand of a switch has a value range ~[5,6]
along some edge and the switch statement has no "case 5" or "case 6"
label then this patch recognizes such a scenario as an opportunity for
threading through the switch and to the switch's default bb.

This improvement is necessary for the code in comment #1 of PR18046 to
get threaded.  There we have (in the VRP2 dump):

    bar ()
    {
      int i.0_1;
      int i.0_2;
      int pretmp_8;
      int prephitmp_9;
      int i.0_10;

      <bb 2>:
      i.0_1 = i;
      switch (i.0_1) <default: <L12>, case 0: <L0>>

    <L12>:
      i.0_10 = ASSERT_EXPR <i.0_1, i.0_1 != 0>;
      goto <bb 4> (<L2>);  // <-- this can be threaded to <L6>

    <L0>:
      i.0_2 = ASSERT_EXPR <i.0_1, i.0_1 == 0>;
      foo ();
      pretmp_8 = i;

      # prephitmp_9 = PHI <i.0_10(7), pretmp_8(3)>
    <L2>:
      switch (prephitmp_9) <default: <L6>, case 0: <L4>>

    <L4>:
      foo ();

    <L6>:
      return;

    }

The FSM threader can't thread the default edge of the 1st switch through
to the default edge of the 2nd switch because i.0_1 doesn't have a known
constant value along that path -- it could have any non-zero value.  For
this scenario and others like it, it is necessary to consider value
ranges.

During bootstrap this simplification triggered about 1000 times in
total.  It's not an impressive amount but the simplification itself is
cheap.

Bootstrap + regtest in progress on x86_64-pc-linux-gnu.  Does this look
OK to commit if there are no new regressions?

gcc/ChangeLog:

	PR tree-optimization/18046
	* tree-ssa-threadedge.c: Include cfganal.h.
	(simplify_control_statement_condition): If simplifying a
	GIMPLE_SWITCH, replace the index operand of the GIMPLE_SWITCH
	with the dominating ASSERT_EXPR before handing it off to VRP.
	Mention that a CASE_LABEL_EXPR may be returned.
	(thread_around_empty_blocks): Adjust to handle
	simplify_control_statement_condition() returning a
	CASE_LABEL_EXPR.
	(thread_through_normal_block): Likewise.
	* tree-vrp.c (simplify_stmt_for_jump_threading): Simplify
	a switch statement by trying to determine which case label
	will be taken.

gcc/testsuite/ChangeLog:

	PR tree-optimization/18046
	* gcc.dg/tree-ssa/vrp105.c: New test.
	* gcc.dg/tree-ssa/vrp106.c: New test.
---
 gcc/testsuite/gcc.dg/tree-ssa/vrp105.c | 37 +++++++++++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/vrp106.c | 27 +++++++++++++++
 gcc/tree-ssa-threadedge.c              | 40 ++++++++++++++++++----
 gcc/tree-vrp.c                         | 61 ++++++++++++++++++++++++++++++++++
 4 files changed, 159 insertions(+), 6 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp105.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp106.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp105.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp105.c
new file mode 100644
index 0000000..7cdd4dd
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp105.c
@@ -0,0 +1,37 @@
+/* PR tree-optimization/18046  */
+/* { dg-options "-O2 -fdump-tree-vrp2-details" }  */
+/* { dg-final { scan-tree-dump-times "Threaded jump" 1 "vrp2" } }  */
+/* In the 2nd VRP pass (after PRE) we expect to thread the default label of the
+   1st switch straight to that of the 2nd switch.  */
+
+extern void foo (void);
+extern void bar (void);
+
+extern int i;
+void
+test (void)
+{
+  switch (i)
+    {
+    case 0:
+      foo ();
+      break;
+    case 1:
+      bar ();
+      break;
+    default:
+      break;
+    }
+
+  switch (i)
+    {
+    case 0:
+      foo ();
+      break;
+    case 1:
+      bar ();
+      break;
+    default:
+      break;
+    }
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp106.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp106.c
new file mode 100644
index 0000000..e2e48d8
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp106.c
@@ -0,0 +1,27 @@
+/* PR tree-optimization/18046  */
+/* { dg-options "-O2 -fdump-tree-vrp1-details" }  */
+/* { dg-final { scan-tree-dump-times "Threaded jump" 1 "vrp1" } }  */
+/* During VRP we expect to thread the true arm of the conditional through the switch
+   and to the BB that corresponds to the 7 ... 9 case label.  */
+extern void foo (void);
+extern void bar (void);
+extern void baz (void);
+
+void
+test (int i)
+{
+  if (i >= 7 && i <= 8)
+    foo ();
+
+  switch (i)
+  {
+    case 1:
+      bar ();
+      break;
+    case 7:
+    case 8:
+    case 9:
+      baz ();
+      break;
+  }
+}
diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index de671b9..170e456 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -36,6 +36,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-ssa-threadedge.h"
 #include "tree-ssa-dom.h"
 #include "gimple-fold.h"
+#include "cfganal.h"
 
 /* To avoid code explosion due to jump threading, we limit the
    number of statements we are going to copy.  This variable
@@ -390,7 +391,8 @@ static tree simplify_control_stmt_condition_1 (edge, gimple *,
    a condition using pass specific information.
 
    Return the simplified condition or NULL if simplification could
-   not be performed.
+   not be performed.  When simplifying a GIMPLE_SWITCH, we may return
+   the CASE_LABEL_EXPR that will be taken.
 
    The available expression table is referenced via AVAIL_EXPRS_STACK.  */
 
@@ -513,7 +515,21 @@ simplify_control_stmt_condition (edge e,
       /* If we haven't simplified to an invariant yet, then use the
 	 pass specific callback to try and simplify it further.  */
       if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
-        cached_lhs = (*simplify) (stmt, stmt, avail_exprs_stack);
+	{
+	  if (handle_dominating_asserts && code == GIMPLE_SWITCH)
+	    {
+	      /* Replace the index operand of the GIMPLE_SWITCH with the
+		 dominating ASSERT_EXPR before handing it off to VRP.  If
+		 simplification is possible, the simplified value will be a
+		 CASE_LABEL_EXPR of the label that is proven to be taken.  */
+	      gswitch *dummy_switch = as_a<gswitch *> (gimple_copy (stmt));
+	      gimple_switch_set_index (dummy_switch, cached_lhs);
+	      cached_lhs = (*simplify) (dummy_switch, stmt, avail_exprs_stack);
+	      ggc_free (dummy_switch);
+	    }
+	  else
+	    cached_lhs = (*simplify) (stmt, stmt, avail_exprs_stack);
+	}
 
       /* We couldn't find an invariant.  But, callers of this
 	 function may be able to do something useful with the
@@ -938,9 +954,14 @@ thread_around_empty_blocks (edge taken_edge,
   /* If the condition can be statically computed and we have not already
      visited the destination edge, then add the taken edge to our thread
      path.  */
-  if (cond && is_gimple_min_invariant (cond))
+  if (cond != NULL_TREE
+      && (is_gimple_min_invariant (cond)
+	  || TREE_CODE (cond) == CASE_LABEL_EXPR))
     {
-      taken_edge = find_taken_edge (bb, cond);
+      if (TREE_CODE (cond) == CASE_LABEL_EXPR)
+	taken_edge = find_edge (bb, label_to_block (CASE_LABEL (cond)));
+      else
+	taken_edge = find_taken_edge (bb, cond);
 
       if ((taken_edge->flags & EDGE_DFS_BACK) != 0)
 	return false;
@@ -1069,9 +1090,16 @@ thread_through_normal_block (edge e,
       if (!cond)
 	return 0;
 
-      if (is_gimple_min_invariant (cond))
+      if (is_gimple_min_invariant (cond)
+	  || TREE_CODE (cond) == CASE_LABEL_EXPR)
 	{
-	  edge taken_edge = find_taken_edge (e->dest, cond);
+	  edge taken_edge;
+	  if (TREE_CODE (cond) == CASE_LABEL_EXPR)
+	    taken_edge = find_edge (e->dest,
+				    label_to_block (CASE_LABEL (cond)));
+	  else
+	    taken_edge = find_taken_edge (e->dest, cond);
+
 	  basic_block dest = (taken_edge ? taken_edge->dest : NULL);
 
 	  /* DEST could be NULL for a computed jump to an absolute
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 41c870f..cb316b0 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -10092,6 +10092,67 @@ simplify_stmt_for_jump_threading (gimple *stmt, gimple *within_stmt,
 				     gimple_cond_rhs (cond_stmt),
 				     within_stmt);
 
+  /* We simplify a switch statement by trying to determine which case label
+     will be taken.  If we are successful then we return the corresponding
+     CASE_LABEL_EXPR.  */
+  if (gswitch *switch_stmt = dyn_cast <gswitch *> (stmt))
+    {
+      tree op = gimple_switch_index (switch_stmt);
+      if (TREE_CODE (op) != SSA_NAME)
+	return NULL_TREE;
+
+      value_range *vr = get_value_range (op);
+      if ((vr->type != VR_RANGE && vr->type != VR_ANTI_RANGE)
+	  || symbolic_range_p (vr))
+	return NULL_TREE;
+
+      if (vr->type == VR_RANGE)
+	{
+	  size_t i, j;
+	  /* Get the range of labels that contain a part of the operand's
+	     value range.  */
+	  find_case_label_range (switch_stmt, vr->min, vr->max, &i, &j);
+
+	  /* Is there only one such label?  */
+	  if (i == j)
+	    {
+	      tree label = gimple_switch_label (switch_stmt, i);
+
+	      /* The i'th label will be taken only if the value range of the
+		 operand is entirely within the bounds of this label.  */
+	      if (CASE_HIGH (label) != NULL_TREE
+		  ? (tree_int_cst_compare (CASE_LOW (label), vr->min) <= 0
+		     && tree_int_cst_compare (CASE_HIGH (label), vr->max) >= 0)
+		  : (tree_int_cst_equal (CASE_LOW (label), vr->min)
+		     && tree_int_cst_equal (vr->min, vr->max)))
+		return label;
+	    }
+
+	  /* If there are no such labels then the default label will be
+	     taken.  */
+	  if (i > j)
+	    return gimple_switch_label (switch_stmt, 0);
+	}
+
+      if (vr->type == VR_ANTI_RANGE)
+	{
+	  unsigned n = gimple_switch_num_labels (switch_stmt);
+	  tree min_label = gimple_switch_label (switch_stmt, 1);
+	  tree max_label = gimple_switch_label (switch_stmt, n - 1);
+
+	  /* The default label will be taken only if the anti-range of the
+	     operand is entirely outside the bounds of all the (non-default)
+	     case labels.  */
+	  if (tree_int_cst_compare (vr->min, CASE_LOW (min_label)) <= 0
+	      && (CASE_HIGH (max_label) != NULL_TREE
+		  ? tree_int_cst_compare (vr->max, CASE_HIGH (max_label)) >= 0
+		  : tree_int_cst_compare (vr->max, CASE_LOW (max_label)) >= 0))
+	  return gimple_switch_label (switch_stmt, 0);
+	}
+
+      return NULL_TREE;
+    }
+
   if (gassign *assign_stmt = dyn_cast <gassign *> (stmt))
     {
       value_range new_vr = VR_INITIALIZER;
-- 
2.9.2.512.gd7cab81

Re: [PATCH] Improve forward jump threading of switch statements (PR18046)

[Patrick Palka]

On Thu, Jul 28, 2016 at 11:46 PM, Patrick Palka <patrick@parcs.ath.cx> wrote:
> This patch improves the forward jump threader's ability to thread
> GIMPLE_SWITCHes by making the VRP simplification callback attempt to
> determine which case label will be taken.
>
> For example, if the index operand of a switch has a value range ~[5,6]
> along some edge and the switch statement has no "case 5" or "case 6"
> label then this patch recognizes such a scenario as an opportunity for
> threading through the switch and to the switch's default bb.

Uh, sorry, this example I gave is completely bogus... Given a value
range of ~[5,6],  "case 5" and "case 6" would have to be the only
non-default labels in the switch for threading to occur, which is how
the patch behaves.

Re: [PATCH] Improve forward jump threading of switch statements (PR18046)

[Patrick Palka]

On Thu, Jul 28, 2016 at 11:46 PM, Patrick Palka <patrick@parcs.ath.cx> wrote:
> This patch improves the forward jump threader's ability to thread
> GIMPLE_SWITCHes by making the VRP simplification callback attempt to
> determine which case label will be taken.
>
> For example, if the index operand of a switch has a value range ~[5,6]
> along some edge and the switch statement has no "case 5" or "case 6"
> label then this patch recognizes such a scenario as an opportunity for
> threading through the switch and to the switch's default bb.
>
> This improvement is necessary for the code in comment #1 of PR18046 to
> get threaded.  There we have (in the VRP2 dump):
>
>     bar ()
>     {
>       int i.0_1;
>       int i.0_2;
>       int pretmp_8;
>       int prephitmp_9;
>       int i.0_10;
>
>       <bb 2>:
>       i.0_1 = i;
>       switch (i.0_1) <default: <L12>, case 0: <L0>>
>
>     <L12>:
>       i.0_10 = ASSERT_EXPR <i.0_1, i.0_1 != 0>;
>       goto <bb 4> (<L2>);  // <-- this can be threaded to <L6>
>
>     <L0>:
>       i.0_2 = ASSERT_EXPR <i.0_1, i.0_1 == 0>;
>       foo ();
>       pretmp_8 = i;
>
>       # prephitmp_9 = PHI <i.0_10(7), pretmp_8(3)>
>     <L2>:
>       switch (prephitmp_9) <default: <L6>, case 0: <L4>>
>
>     <L4>:
>       foo ();
>
>     <L6>:
>       return;
>
>     }
>
> The FSM threader can't thread the default edge of the 1st switch through
> to the default edge of the 2nd switch because i.0_1 doesn't have a known
> constant value along that path -- it could have any non-zero value.  For
> this scenario and others like it, it is necessary to consider value
> ranges.
>
> During bootstrap this simplification triggered about 1000 times in
> total.  It's not an impressive amount but the simplification itself is
> cheap.
>
> Bootstrap + regtest in progress on x86_64-pc-linux-gnu.  Does this look
> OK to commit if there are no new regressions?
>
> gcc/ChangeLog:
>
>         PR tree-optimization/18046
>         * tree-ssa-threadedge.c: Include cfganal.h.
>         (simplify_control_statement_condition): If simplifying a
>         GIMPLE_SWITCH, replace the index operand of the GIMPLE_SWITCH
>         with the dominating ASSERT_EXPR before handing it off to VRP.
>         Mention that a CASE_LABEL_EXPR may be returned.
>         (thread_around_empty_blocks): Adjust to handle
>         simplify_control_statement_condition() returning a
>         CASE_LABEL_EXPR.
>         (thread_through_normal_block): Likewise.
>         * tree-vrp.c (simplify_stmt_for_jump_threading): Simplify
>         a switch statement by trying to determine which case label
>         will be taken.
>
> gcc/testsuite/ChangeLog:
>
>         PR tree-optimization/18046
>         * gcc.dg/tree-ssa/vrp105.c: New test.
>         * gcc.dg/tree-ssa/vrp106.c: New test.
> ---
>  gcc/testsuite/gcc.dg/tree-ssa/vrp105.c | 37 +++++++++++++++++++++
>  gcc/testsuite/gcc.dg/tree-ssa/vrp106.c | 27 +++++++++++++++
>  gcc/tree-ssa-threadedge.c              | 40 ++++++++++++++++++----
>  gcc/tree-vrp.c                         | 61 ++++++++++++++++++++++++++++++++++
>  4 files changed, 159 insertions(+), 6 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp105.c
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp106.c
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp105.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp105.c
> new file mode 100644
> index 0000000..7cdd4dd
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp105.c
> @@ -0,0 +1,37 @@
> +/* PR tree-optimization/18046  */
> +/* { dg-options "-O2 -fdump-tree-vrp2-details" }  */
> +/* { dg-final { scan-tree-dump-times "Threaded jump" 1 "vrp2" } }  */
> +/* In the 2nd VRP pass (after PRE) we expect to thread the default label of the
> +   1st switch straight to that of the 2nd switch.  */
> +
> +extern void foo (void);
> +extern void bar (void);
> +
> +extern int i;
> +void
> +test (void)
> +{
> +  switch (i)
> +    {
> +    case 0:
> +      foo ();
> +      break;
> +    case 1:
> +      bar ();
> +      break;
> +    default:
> +      break;
> +    }
> +
> +  switch (i)
> +    {
> +    case 0:
> +      foo ();
> +      break;
> +    case 1:
> +      bar ();
> +      break;
> +    default:
> +      break;
> +    }
> +}
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp106.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp106.c
> new file mode 100644
> index 0000000..e2e48d8
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp106.c
> @@ -0,0 +1,27 @@
> +/* PR tree-optimization/18046  */
> +/* { dg-options "-O2 -fdump-tree-vrp1-details" }  */
> +/* { dg-final { scan-tree-dump-times "Threaded jump" 1 "vrp1" } }  */
> +/* During VRP we expect to thread the true arm of the conditional through the switch
> +   and to the BB that corresponds to the 7 ... 9 case label.  */
> +extern void foo (void);
> +extern void bar (void);
> +extern void baz (void);
> +
> +void
> +test (int i)
> +{
> +  if (i >= 7 && i <= 8)
> +    foo ();
> +
> +  switch (i)
> +  {
> +    case 1:
> +      bar ();
> +      break;
> +    case 7:
> +    case 8:
> +    case 9:
> +      baz ();
> +      break;
> +  }
> +}
> diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
> index de671b9..170e456 100644
> --- a/gcc/tree-ssa-threadedge.c
> +++ b/gcc/tree-ssa-threadedge.c
> @@ -36,6 +36,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include "tree-ssa-threadedge.h"
>  #include "tree-ssa-dom.h"
>  #include "gimple-fold.h"
> +#include "cfganal.h"
>
>  /* To avoid code explosion due to jump threading, we limit the
>     number of statements we are going to copy.  This variable
> @@ -390,7 +391,8 @@ static tree simplify_control_stmt_condition_1 (edge, gimple *,
>     a condition using pass specific information.
>
>     Return the simplified condition or NULL if simplification could
> -   not be performed.
> +   not be performed.  When simplifying a GIMPLE_SWITCH, we may return
> +   the CASE_LABEL_EXPR that will be taken.
>
>     The available expression table is referenced via AVAIL_EXPRS_STACK.  */
>
> @@ -513,7 +515,21 @@ simplify_control_stmt_condition (edge e,
>        /* If we haven't simplified to an invariant yet, then use the
>          pass specific callback to try and simplify it further.  */
>        if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
> -        cached_lhs = (*simplify) (stmt, stmt, avail_exprs_stack);
> +       {
> +         if (handle_dominating_asserts && code == GIMPLE_SWITCH)
> +           {
> +             /* Replace the index operand of the GIMPLE_SWITCH with the
> +                dominating ASSERT_EXPR before handing it off to VRP.  If
> +                simplification is possible, the simplified value will be a
> +                CASE_LABEL_EXPR of the label that is proven to be taken.  */
> +             gswitch *dummy_switch = as_a<gswitch *> (gimple_copy (stmt));
> +             gimple_switch_set_index (dummy_switch, cached_lhs);
> +             cached_lhs = (*simplify) (dummy_switch, stmt, avail_exprs_stack);
> +             ggc_free (dummy_switch);
> +           }
> +         else
> +           cached_lhs = (*simplify) (stmt, stmt, avail_exprs_stack);
> +       }
>
>        /* We couldn't find an invariant.  But, callers of this
>          function may be able to do something useful with the
> @@ -938,9 +954,14 @@ thread_around_empty_blocks (edge taken_edge,
>    /* If the condition can be statically computed and we have not already
>       visited the destination edge, then add the taken edge to our thread
>       path.  */
> -  if (cond && is_gimple_min_invariant (cond))
> +  if (cond != NULL_TREE
> +      && (is_gimple_min_invariant (cond)
> +         || TREE_CODE (cond) == CASE_LABEL_EXPR))
>      {
> -      taken_edge = find_taken_edge (bb, cond);
> +      if (TREE_CODE (cond) == CASE_LABEL_EXPR)
> +       taken_edge = find_edge (bb, label_to_block (CASE_LABEL (cond)));
> +      else
> +       taken_edge = find_taken_edge (bb, cond);
>
>        if ((taken_edge->flags & EDGE_DFS_BACK) != 0)
>         return false;
> @@ -1069,9 +1090,16 @@ thread_through_normal_block (edge e,
>        if (!cond)
>         return 0;
>
> -      if (is_gimple_min_invariant (cond))
> +      if (is_gimple_min_invariant (cond)
> +         || TREE_CODE (cond) == CASE_LABEL_EXPR)
>         {
> -         edge taken_edge = find_taken_edge (e->dest, cond);
> +         edge taken_edge;
> +         if (TREE_CODE (cond) == CASE_LABEL_EXPR)
> +           taken_edge = find_edge (e->dest,
> +                                   label_to_block (CASE_LABEL (cond)));
> +         else
> +           taken_edge = find_taken_edge (e->dest, cond);
> +
>           basic_block dest = (taken_edge ? taken_edge->dest : NULL);
>
>           /* DEST could be NULL for a computed jump to an absolute
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index 41c870f..cb316b0 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -10092,6 +10092,67 @@ simplify_stmt_for_jump_threading (gimple *stmt, gimple *within_stmt,
>                                      gimple_cond_rhs (cond_stmt),
>                                      within_stmt);
>
> +  /* We simplify a switch statement by trying to determine which case label
> +     will be taken.  If we are successful then we return the corresponding
> +     CASE_LABEL_EXPR.  */
> +  if (gswitch *switch_stmt = dyn_cast <gswitch *> (stmt))
> +    {
> +      tree op = gimple_switch_index (switch_stmt);
> +      if (TREE_CODE (op) != SSA_NAME)
> +       return NULL_TREE;
> +
> +      value_range *vr = get_value_range (op);
> +      if ((vr->type != VR_RANGE && vr->type != VR_ANTI_RANGE)
> +         || symbolic_range_p (vr))
> +       return NULL_TREE;
> +
> +      if (vr->type == VR_RANGE)
> +       {
> +         size_t i, j;
> +         /* Get the range of labels that contain a part of the operand's
> +            value range.  */
> +         find_case_label_range (switch_stmt, vr->min, vr->max, &i, &j);
> +
> +         /* Is there only one such label?  */
> +         if (i == j)
> +           {
> +             tree label = gimple_switch_label (switch_stmt, i);
> +
> +             /* The i'th label will be taken only if the value range of the
> +                operand is entirely within the bounds of this label.  */
> +             if (CASE_HIGH (label) != NULL_TREE
> +                 ? (tree_int_cst_compare (CASE_LOW (label), vr->min) <= 0
> +                    && tree_int_cst_compare (CASE_HIGH (label), vr->max) >= 0)
> +                 : (tree_int_cst_equal (CASE_LOW (label), vr->min)
> +                    && tree_int_cst_equal (vr->min, vr->max)))
> +               return label;
> +           }
> +
> +         /* If there are no such labels then the default label will be
> +            taken.  */
> +         if (i > j)
> +           return gimple_switch_label (switch_stmt, 0);
> +       }
> +
> +      if (vr->type == VR_ANTI_RANGE)
> +       {
> +         unsigned n = gimple_switch_num_labels (switch_stmt);
> +         tree min_label = gimple_switch_label (switch_stmt, 1);
> +         tree max_label = gimple_switch_label (switch_stmt, n - 1);
> +
> +         /* The default label will be taken only if the anti-range of the
> +            operand is entirely outside the bounds of all the (non-default)
> +            case labels.  */
> +         if (tree_int_cst_compare (vr->min, CASE_LOW (min_label)) <= 0
> +             && (CASE_HIGH (max_label) != NULL_TREE
> +                 ? tree_int_cst_compare (vr->max, CASE_HIGH (max_label)) >= 0
> +                 : tree_int_cst_compare (vr->max, CASE_LOW (max_label)) >= 0))
> +         return gimple_switch_label (switch_stmt, 0);
> +       }
> +
> +      return NULL_TREE;
> +    }
> +
>    if (gassign *assign_stmt = dyn_cast <gassign *> (stmt))
>      {
>        value_range new_vr = VR_INITIALIZER;
> --
> 2.9.2.512.gd7cab81
>

Ping.

Re: [PATCH] Improve forward jump threading of switch statements (PR18046)

[Jeff Law]

On 07/28/2016 09:46 PM, Patrick Palka wrote:
> This patch improves the forward jump threader's ability to thread
> GIMPLE_SWITCHes by making the VRP simplification callback attempt to
> determine which case label will be taken.
>
> For example, if the index operand of a switch has a value range ~[5,6]
> along some edge and the switch statement has no "case 5" or "case 6"
> label then this patch recognizes such a scenario as an opportunity for
> threading through the switch and to the switch's default bb.
>
> This improvement is necessary for the code in comment #1 of PR18046 to
> get threaded.  There we have (in the VRP2 dump):
>
>     bar ()
>     {
>       int i.0_1;
>       int i.0_2;
>       int pretmp_8;
>       int prephitmp_9;
>       int i.0_10;
>
>       <bb 2>:
>       i.0_1 = i;
>       switch (i.0_1) <default: <L12>, case 0: <L0>>
>
>     <L12>:
>       i.0_10 = ASSERT_EXPR <i.0_1, i.0_1 != 0>;
>       goto <bb 4> (<L2>);  // <-- this can be threaded to <L6>
>
>     <L0>:
>       i.0_2 = ASSERT_EXPR <i.0_1, i.0_1 == 0>;
>       foo ();
>       pretmp_8 = i;
>
>       # prephitmp_9 = PHI <i.0_10(7), pretmp_8(3)>
>     <L2>:
>       switch (prephitmp_9) <default: <L6>, case 0: <L4>>
>
>     <L4>:
>       foo ();
>
>     <L6>:
>       return;
>
>     }
>
> The FSM threader can't thread the default edge of the 1st switch through
> to the default edge of the 2nd switch because i.0_1 doesn't have a known
> constant value along that path -- it could have any non-zero value.  For
> this scenario and others like it, it is necessary to consider value
> ranges.
>
> During bootstrap this simplification triggered about 1000 times in
> total.  It's not an impressive amount but the simplification itself is
> cheap.
>
> Bootstrap + regtest in progress on x86_64-pc-linux-gnu.  Does this look
> OK to commit if there are no new regressions?
>
> gcc/ChangeLog:
>
> 	PR tree-optimization/18046
> 	* tree-ssa-threadedge.c: Include cfganal.h.
> 	(simplify_control_statement_condition): If simplifying a
> 	GIMPLE_SWITCH, replace the index operand of the GIMPLE_SWITCH
> 	with the dominating ASSERT_EXPR before handing it off to VRP.
> 	Mention that a CASE_LABEL_EXPR may be returned.
> 	(thread_around_empty_blocks): Adjust to handle
> 	simplify_control_statement_condition() returning a
> 	CASE_LABEL_EXPR.
> 	(thread_through_normal_block): Likewise.
> 	* tree-vrp.c (simplify_stmt_for_jump_threading): Simplify
> 	a switch statement by trying to determine which case label
> 	will be taken.
>
> gcc/testsuite/ChangeLog:
>
> 	PR tree-optimization/18046
> 	* gcc.dg/tree-ssa/vrp105.c: New test.
> 	* gcc.dg/tree-ssa/vrp106.c: New test.
OK.

Thanks for your patience,
jeff