Re: [PATCH] Teach VRP to register assertions along default switch labels (PR 18046)

[Patrick Palka <patrick at parcs dot ath dot cx>]

On Fri, 22 Jul 2016, Patrick Palka wrote:

> On Fri, 22 Jul 2016, Patrick Palka wrote:
> 
> > This patch teaches VRP to register along a default switch label
> > assertions that corresponds to the anti range of each case label.
> > 
> > Does this look OK to commit after bootstrap + regtest on
> > x86_64-pc-linux-gnu?
> 
> Forgot the changelog:
> 
> gcc/ChangeLog:
> 
> 	PR tree-optimization/18046
> 	* tree-vrp.c (find_switch_asserts): Register edge assertions
> 	for the default label which correspond to the anti-ranges
> 	of each non-case label.
> 
> gcc/testsuite/ChangeLog:
> 
> 	PR tree-optimization/18046
> 	* gcc.dg/tree-ssa/ssa-dom-thread-6.c: Bump FSM count to 5.
> 	* gcc.dg/tree-ssa/vrp103.c: New test.
> 	* gcc.dg/tree-ssa/vrp104.c: New test.
> 

The patch failed to bootstrap due to a number -Warray-bounds warnings
getting emitted for the autogenerated header file insn-modes.h:

In file included from /home/patrick/code/gcc/gcc/machmode.h:24:0,
                 from /home/patrick/code/gcc/gcc/coretypes.h:391,
                 from /home/patrick/code/gcc/gcc/lto-streamer-out.c:25:
./insn-modes.h: In function ʽvoid produce_asm_for_decls()ʼ:
./insn-modes.h:638:36: warning: array subscript is outside array bounds [-Warray-bounds]
     default: return mode_inner[mode];
                     ~~~~~~~~~~~~~~~^

These new warnings seem legitimate.  From what I can tell, this array
access along the default switch label will always be out of bounds.  The
code it's warning about basically looks like this:

  enum A { a, b, c };
  int foo (A i)
  {
    int array[3];
    switch (i)
    {
      case a: return x;
      case b: return y;
      case c: return z;
      default: return array[i];
    }
  }

and while the switch does exhaust every possible enumeration value of A,
there's nothing stopping the user from passing an arbitrary int to
foo() thus triggering the default case.  So this patch suppresses these
warnings by making genemit emit an assertion that verifies that mode is
within the bounds of the array.  This assertion won't affect performance
because the mode_*_inline functions are always called with constant
arguments.

This version of the patch has the following changes:

1. Fixes the bootstrap failure as mentioned above.
2. Checks if the switch operand is live along the default edge before
registering assertions.
3. Combines contiguous case ranges to reduce the number of assert
expressions to insert.

Bootstrap + regtesting in progress on x86_64-pc-linux-gnu.

gcc/ChangeLog:

	PR tree-optimization/18046
	* genmodes.c (emit_mode_size_inline): Emit an assert that
	verifies that mode is a valid array index.
	(emit_mode_nuinits_inline): Likewise.
	(emit_mode_inner_inline): Likewise.
	(emit_mode_unit_size_inline): Likewise.
	(emit_mode_unit_precision_inline): Likewise.
	* tree-vrp.c (compare_case_label_values): New qsort callback.
	(find_switch_asserts): Register edge assertions for
	the default label, which correspond to the anti-range of each
	non-case label.

gcc/testsuite/ChangeLog:

	PR tree-optimization/18046
	* gcc.dg/tree-ssa/ssa-dom-thread-6.c: Bump FSM count to 5.
	* gcc.dg/tree-ssa/vrp103.c: New test.
	* gcc.dg/tree-ssa/vrp104.c: New test.
---
 gcc/genmodes.c                                   |  5 ++
 gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c |  2 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp103.c           | 30 +++++++++
 gcc/testsuite/gcc.dg/tree-ssa/vrp104.c           | 32 +++++++++
 gcc/tree-vrp.c                                   | 85 +++++++++++++++++++++++-
 5 files changed, 151 insertions(+), 3 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp103.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp104.c

diff --git a/gcc/genmodes.c b/gcc/genmodes.c
index 097cc80..1170d4f 100644
--- a/gcc/genmodes.c
+++ b/gcc/genmodes.c
@@ -976,6 +976,7 @@ unsigned char\n\
 mode_size_inline (machine_mode mode)\n\
 {\n\
   extern %sunsigned char mode_size[NUM_MACHINE_MODES];\n\
+  gcc_assert (mode >= 0 && mode < NUM_MACHINE_MODES);\n\
   switch (mode)\n\
     {\n", adj_bytesize ? "" : "const ");
 
@@ -1006,6 +1007,7 @@ unsigned char\n\
 mode_nunits_inline (machine_mode mode)\n\
 {\n\
   extern const unsigned char mode_nunits[NUM_MACHINE_MODES];\n\
+  gcc_assert (mode >= 0 && mode < NUM_MACHINE_MODES);\n\
   switch (mode)\n\
     {");
 
@@ -1035,6 +1037,7 @@ unsigned char\n\
 mode_inner_inline (machine_mode mode)\n\
 {\n\
   extern const unsigned char mode_inner[NUM_MACHINE_MODES];\n\
+  gcc_assert (mode >= 0 && mode < NUM_MACHINE_MODES);\n\
   switch (mode)\n\
     {");
 
@@ -1067,6 +1070,7 @@ mode_unit_size_inline (machine_mode mode)\n\
 {\n\
   extern CONST_MODE_UNIT_SIZE unsigned char mode_unit_size[NUM_MACHINE_MODES];\
 \n\
+  gcc_assert (mode >= 0 && mode < NUM_MACHINE_MODES);\n\
   switch (mode)\n\
     {");
 
@@ -1103,6 +1107,7 @@ unsigned short\n\
 mode_unit_precision_inline (machine_mode mode)\n\
 {\n\
   extern const unsigned short mode_unit_precision[NUM_MACHINE_MODES];\n\
+  gcc_assert (mode >= 0 && mode < NUM_MACHINE_MODES);\n\
   switch (mode)\n\
     {");
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c
index 5ec4687..551fbac 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c
@@ -1,7 +1,7 @@
 /* { dg-do compile } */
 /* { dg-options "-O2 -fdump-tree-thread1-details -fdump-tree-thread2-details" } */
 /* { dg-final { scan-tree-dump-times "FSM" 3 "thread1" } } */
-/* { dg-final { scan-tree-dump-times "FSM" 4 "thread2" } } */
+/* { dg-final { scan-tree-dump-times "FSM" 5 "thread2" } } */
 
 int sum0, sum1, sum2, sum3;
 int foo (char *s, char **ret)
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp103.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp103.c
new file mode 100644
index 0000000..eea98bb
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp103.c
@@ -0,0 +1,30 @@
+/* PR tree-optimization/18046  */
+/* { dg-options "-O2 -fdump-tree-vrp" }  */
+/* { dg-final { scan-tree-dump-times "baz \\(0\\);" 4 "vrp1" } }  */
+
+void foo ();
+void bar ();
+void baz (int);
+
+void
+test (int i)
+{
+  switch (i)
+    {
+    case 1:
+    case 2:
+    case 3:
+      foo ();
+      break;
+    case 5:
+      bar ();
+      break;
+    default:
+      /* These tests should be folded to 0, resulting in 4 calls to bar (0).  */
+      baz (i == 1);
+      baz (i == 2);
+      baz (i == 3);
+      baz (i == 5);
+      break;
+    }
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c
new file mode 100644
index 0000000..6410847
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c
@@ -0,0 +1,32 @@
+/* PR tree-optimization/18046  */
+/* { dg-options "-O2 -fdump-tree-optimized" }  */
+/* { dg-final { scan-tree-dump-times "switch" 1 "optimized" } }  */
+
+void foo ();
+void bar ();
+
+void
+test (int i)
+{
+  switch (i)
+    {
+    case 1:
+      foo ();
+      break;
+    case 2:
+      bar ();
+      break;
+    default:
+      break;
+    }
+
+  /* This switch should be gone after threading/VRP.  */
+  switch (i)
+    {
+    case 1:
+      foo ();
+      break;
+    default:
+      break;
+    }
+}
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 06364b7..a3068ec 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -5882,6 +5882,24 @@ compare_case_labels (const void *p1, const void *p2)
     return 1;
 }
 
+/* Compare two case labels sorting only by the case value.  */
+
+static int
+compare_case_label_values (const void *p1, const void *p2)
+{
+  const struct case_info *ci1 = (const struct case_info *) p1;
+  const struct case_info *ci2 = (const struct case_info *) p2;
+
+  /* Make sure the default label is first.  */
+  if (!CASE_LOW (ci1->expr))
+    return -1;
+  else if (!CASE_LOW (ci2->expr))
+    return 1;
+  else
+    return tree_int_cst_compare (CASE_LOW (ci1->expr),
+				 CASE_LOW (ci2->expr));
+}
+
 /* Determine whether the outgoing edges of BB should receive an
    ASSERT_EXPR for each of the operands of BB's LAST statement.
    The last statement of BB must be a SWITCH_EXPR.
@@ -5917,6 +5935,7 @@ find_switch_asserts (basic_block bb, gswitch *last)
       ci[idx].expr = gimple_switch_label (last, idx);
       ci[idx].bb = label_to_block (CASE_LABEL (ci[idx].expr));
     }
+  edge default_edge = find_edge (bb, ci[0].bb);
   qsort (ci, n, sizeof (struct case_info), compare_case_labels);
 
   for (idx = 0; idx < n; ++idx)
@@ -5945,8 +5964,8 @@ find_switch_asserts (basic_block bb, gswitch *last)
 	    max = CASE_LOW (ci[idx].expr);
 	}
 
-      /* Nothing to do if the range includes the default label until we
-	 can register anti-ranges.  */
+      /* Can't extract a useful assertion out of a range that includes the
+	 default label.  */
       if (min == NULL_TREE)
 	continue;
 
@@ -5963,6 +5982,68 @@ find_switch_asserts (basic_block bb, gswitch *last)
 				  fold_convert (TREE_TYPE (op), max));
     }
 
+  if (live_on_edge (default_edge, op))
+    {
+      /* Re-sort the vector by just the case values so that we can easily
+	 combine contiguous case ranges below.  */
+      qsort (ci, n, sizeof (struct case_info), compare_case_label_values);
+      gcc_assert (CASE_LOW (ci[0].expr) == NULL_TREE);
+
+      /* Register along the default label assertions that correspond to the
+	 anti-range of each label.  */
+      for (idx = 1; idx < n; idx++)
+	{
+	  tree min, max;
+	  tree cl = ci[idx].expr;
+
+	  min = CASE_LOW (cl);
+	  max = CASE_HIGH (cl);
+
+	  /* Combine contiguous case range to reduce the number of assertions
+	     to insert.  */
+	  for (idx = idx + 1; idx < n; idx++)
+	    {
+	      tree next_min, next_max;
+	      tree next_cl = ci[idx].expr;
+
+	      next_min = CASE_LOW (next_cl);
+	      next_max = CASE_HIGH (next_cl);
+
+	      tree difference
+		= int_const_binop (MINUS_EXPR, next_min, max ? max : min);
+	      if (integer_onep (difference))
+		max = next_max ? next_max : next_min;
+	      else
+		{
+		  gcc_assert (tree_int_cst_sgn (difference) > 0);
+		  break;
+		}
+	    }
+	  idx--;
+
+	  if (max == NULL_TREE)
+	    {
+	      /* Register the assertion OP != MIN.  */
+	      min = fold_convert (TREE_TYPE (op), min);
+	      register_edge_assert_for (op, default_edge, bsi,
+					NE_EXPR, op, min);
+	    }
+	  else
+	    {
+	      /* Register the assertion (unsigned)OP - MIN > (MAX - MIN),
+		 which will give OP the anti-range ~[MIN,MAX].  */
+	      tree uop = fold_convert (unsigned_type_for (TREE_TYPE (op)), op);
+	      min = fold_convert (TREE_TYPE (uop), min);
+	      max = fold_convert (TREE_TYPE (uop), max);
+
+	      tree lhs = fold_build2 (MINUS_EXPR, TREE_TYPE (uop), uop, min);
+	      tree rhs = int_const_binop (MINUS_EXPR, max, min);
+	      register_new_assert_for (op, lhs, GT_EXPR, rhs,
+				       NULL, default_edge, bsi);
+	    }
+	}
+    }
+
   XDELETEVEC (ci);
 }
 
-- 
2.9.2.413.g76d2a70