Teach VRP to truncate the case ranges of a switch

gcc/ChangeLog:

	* tree-vrp.c (simplify_switch_using_ranges): Try to truncate
	the case label ranges that partially overlap with OP's value
	range.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/vrp107.c: New test.
	* gcc.dg/tree-ssa/vrp108.c: New test.
	* gcc.dg/tree-ssa/vrp109.c: New test.

From-SVN: r239157

6 files changed, 206 insertions, 1 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index fd6fa78..83bdb1a 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,9 @@
+2016-08-04  Patrick Palka  <ppalka@gcc.gnu.org>
+
+	* tree-vrp.c (simplify_switch_using_ranges): Try to truncate
+	the case label ranges that partially overlap with OP's value
+	range.
+
 2016-08-04  Uros Bizjak  <ubizjak@gmail.com>
 
 	PR target/72805
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 52e8f2e..6f057a4 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,9 @@
+2016-08-04  Patrick Palka  <ppalka@gcc.gnu.org>
+
+	* gcc.dg/tree-ssa/vrp107.c: New test.
+	* gcc.dg/tree-ssa/vrp108.c: New test.
+	* gcc.dg/tree-ssa/vrp109.c: New test.
+
 2016-08-04  Prathamesh Kulkarni  <prathamesh.kulkarni@linaro.org>
 
 	* gcc.dg/pr70920-4.c: Move dg-require-effective-target before
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp107.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp107.c
new file mode 100644
index 0000000..b74f031
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp107.c
@@ -0,0 +1,25 @@
+/* { dg-options "-O2 -fdump-tree-vrp1" }  */
+/* { dg-final { scan-tree-dump "case 2:" "vrp1" } }  */
+/* { dg-final { scan-tree-dump "case 7 ... 8:" "vrp1" } }  */
+
+extern void foo (void);
+extern void bar (void);
+extern void baz (void);
+
+void
+test (int i)
+{
+  if (i >= 2 && i <= 8)
+  switch (i)
+    {
+    case 1: /* Redundant label.  */
+    case 2:
+      bar ();
+      break;
+    case 7:
+    case 8:
+    case 9: /* Redundant label.  */
+      baz ();
+      break;
+    }
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp108.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp108.c
new file mode 100644
index 0000000..49dbfb5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp108.c
@@ -0,0 +1,25 @@
+/* { dg-options "-O2 -fdump-tree-vrp1" }  */
+/* { dg-final { scan-tree-dump "case 1:" "vrp1" } }  */
+/* { dg-final { scan-tree-dump "case 9:" "vrp1" } }  */
+
+extern void foo (void);
+extern void bar (void);
+extern void baz (void);
+
+void
+test (int i)
+{
+  if (i < 2 || i > 8)
+  switch (i)
+    {
+    case 1:
+    case 2: /* Redundant label.  */
+      bar ();
+      break;
+    case 7: /* Redundant label.  */
+    case 8: /* Redundant label.  */
+    case 9:
+      baz ();
+      break;
+    }
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp109.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp109.c
new file mode 100644
index 0000000..86299a9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp109.c
@@ -0,0 +1,65 @@
+/* { dg-options "-O2 -fdump-tree-vrp1" }  */
+/* { dg-final { scan-tree-dump "case 9 ... 10:" "vrp1" } }  */
+/* { dg-final { scan-tree-dump "case 17 ... 18:" "vrp1" } }  */
+/* { dg-final { scan-tree-dump "case 27 ... 30:" "vrp1" } }  */
+
+extern void foo (void);
+extern void bar (void);
+
+void
+test1 (int i)
+{
+  if (i != 7 && i != 8)
+    switch (i)
+      {
+      case 1:
+      case 2:
+        foo ();
+        break;
+      case 7: /* Redundant label.  */
+      case 8: /* Redundant label.  */
+      case 9:
+      case 10:
+        bar ();
+        break;
+      }
+}
+
+void
+test3 (int i)
+{
+  if (i != 19 && i != 20)
+    switch (i)
+      {
+      case 1:
+      case 2:
+        foo ();
+        break;
+      case 17:
+      case 18:
+      case 19: /* Redundant label.  */
+      case 20: /* Redundant label.  */
+        bar ();
+        break;
+      }
+}
+
+void
+test2 (int i)
+{
+  if (i != 28 && i != 29)
+    switch (i)
+      {
+      case 1:
+      case 2:
+        foo ();
+        break;
+      /* No redundancy.  */
+      case 27:
+      case 28:
+      case 29:
+      case 30:
+        bar ();
+        break;
+      }
+}
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index c0e25cf..cee6424 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -9593,7 +9593,7 @@ static bool
 simplify_switch_using_ranges (gswitch *stmt)
 {
   tree op = gimple_switch_index (stmt);
-  value_range *vr;
+  value_range *vr = NULL;
   bool take_default;
   edge e;
   edge_iterator ei;
@@ -9633,6 +9633,84 @@ simplify_switch_using_ranges (gswitch *stmt)
 
   n = gimple_switch_num_labels (stmt);
 
+  /* We can truncate the case label ranges that partially overlap with OP's
+     value range.  */
+  size_t min_idx = 1, max_idx = 0;
+  if (vr != NULL)
+    find_case_label_range (stmt, vr->min, vr->max, &min_idx, &max_idx);
+  if (min_idx <= max_idx)
+    {
+      tree min_label = gimple_switch_label (stmt, min_idx);
+      tree max_label = gimple_switch_label (stmt, max_idx);
+
+      if (vr->type == VR_RANGE)
+	{
+	  /* If OP's value range is [2,8] and the low label range is
+	     0 ... 3, truncate the label's range to 2 .. 3.  */
+	  if (tree_int_cst_compare (CASE_LOW (min_label), vr->min) < 0
+	      && CASE_HIGH (min_label) != NULL_TREE
+	      && tree_int_cst_compare (CASE_HIGH (min_label), vr->min) >= 0)
+	    CASE_LOW (min_label) = vr->min;
+
+	  /* If OP's value range is [2,8] and the high label range is
+	     7 ... 10, truncate the label's range to 7 .. 8.  */
+	  if (tree_int_cst_compare (CASE_LOW (max_label), vr->max) <= 0
+	      && CASE_HIGH (max_label) != NULL_TREE
+	      && tree_int_cst_compare (CASE_HIGH (max_label), vr->max) > 0)
+	    CASE_HIGH (max_label) = vr->max;
+	}
+      else if (vr->type == VR_ANTI_RANGE)
+	{
+	  tree one_cst = build_one_cst (TREE_TYPE (op));
+
+	  if (min_label == max_label)
+	    {
+	      /* If OP's value range is ~[7,8] and the label's range is
+		 7 ... 10, truncate the label's range to 9 ... 10.  */
+	      if (tree_int_cst_compare (CASE_LOW (min_label), vr->min) == 0
+		  && CASE_HIGH (min_label) != NULL_TREE
+		  && tree_int_cst_compare (CASE_HIGH (min_label), vr->max) > 0)
+		CASE_LOW (min_label)
+		  = int_const_binop (PLUS_EXPR, vr->max, one_cst);
+
+	      /* If OP's value range is ~[7,8] and the label's range is
+		 5 ... 8, truncate the label's range to 5 ... 6.  */
+	      if (tree_int_cst_compare (CASE_LOW (min_label), vr->min) < 0
+		  && CASE_HIGH (min_label) != NULL_TREE
+		  && tree_int_cst_compare (CASE_HIGH (min_label), vr->max) == 0)
+		CASE_HIGH (min_label)
+		  = int_const_binop (MINUS_EXPR, vr->min, one_cst);
+	    }
+	  else
+	    {
+	      /* If OP's value range is ~[2,8] and the low label range is
+		 0 ... 3, truncate the label's range to 0 ... 1.  */
+	      if (tree_int_cst_compare (CASE_LOW (min_label), vr->min) < 0
+		  && CASE_HIGH (min_label) != NULL_TREE
+		  && tree_int_cst_compare (CASE_HIGH (min_label), vr->min) >= 0)
+		CASE_HIGH (min_label)
+		  = int_const_binop (MINUS_EXPR, vr->min, one_cst);
+
+	      /* If OP's value range is ~[2,8] and the high label range is
+		 7 ... 10, truncate the label's range to 9 ... 10.  */
+	      if (tree_int_cst_compare (CASE_LOW (max_label), vr->max) <= 0
+		  && CASE_HIGH (max_label) != NULL_TREE
+		  && tree_int_cst_compare (CASE_HIGH (max_label), vr->max) > 0)
+		CASE_LOW (max_label)
+		  = int_const_binop (PLUS_EXPR, vr->max, one_cst);
+	    }
+	}
+
+      /* Canonicalize singleton case ranges.  */
+      if (tree_int_cst_equal (CASE_LOW (min_label), CASE_HIGH (min_label)))
+	CASE_HIGH (min_label) = NULL_TREE;
+      if (tree_int_cst_equal (CASE_LOW (max_label), CASE_HIGH (max_label)))
+	CASE_HIGH (max_label) = NULL_TREE;
+    }
+
+  /* We can also eliminate case labels that lie completely outside OP's value
+     range.  */
+
   /* Bail out if this is just all edges taken.  */
   if (i == 1
       && j == n - 1