[PATCH] Expand switch statements with a single (or none) non-default case.

[Martin Liška <mliska at suse dot cz>]

Hi.

Simple transformation of switch statements where degenerated switch can be interpreted
as gimple condition (or removed if having any non-default case). I originally though
that we don't have switch statements without non-default cases, but PR82032 shows we
can see it.

Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.

Ready to be installed?
Martin

gcc/ChangeLog:

2017-08-25  Martin Liska  <mliska@suse.cz>

	PR tree-optimization/82032
	* tree-switch-conversion.c (generate_high_low_equality): New
	function.
	(expand_degenerated_switch): Likewise.
	(process_switch): Call expand_degenerated_switch.
	(try_switch_expansion): Likewise.
	(emit_case_nodes): Use generate_high_low_equality.

gcc/testsuite/ChangeLog:

2017-08-25  Martin Liska  <mliska@suse.cz>

	PR tree-optimization/82032
	* gcc.dg/tree-ssa/pr68198.c: Update jump threading expectations.
	* gcc.dg/tree-ssa/switch-expansion.c: New test.
	* gcc.dg/tree-ssa/vrp34.c: Update scanned pattern.
	* g++.dg/other/pr82032.C: New test.
---
 gcc/testsuite/g++.dg/other/pr82032.C             |  36 +++++++
 gcc/testsuite/gcc.dg/tree-ssa/pr68198.c          |   6 +-
 gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c |  14 +++
 gcc/testsuite/gcc.dg/tree-ssa/vrp34.c            |   5 +-
 gcc/tree-switch-conversion.c                     | 123 ++++++++++++++++++-----
 5 files changed, 152 insertions(+), 32 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/other/pr82032.C
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c


diff --git a/gcc/testsuite/g++.dg/other/pr82032.C b/gcc/testsuite/g++.dg/other/pr82032.C
new file mode 100644
index 00000000000..607bf85c8e1
--- /dev/null
+++ b/gcc/testsuite/g++.dg/other/pr82032.C
@@ -0,0 +1,36 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -Wno-return-type" } */
+
+template <typename a> class b
+{
+public:
+  typename a::aa operator[] (typename a::c) { }
+};
+class d
+{
+public:
+  typedef long c;
+  typedef int aa;
+};
+struct e
+{
+  int af[4];
+  int ag;
+};
+b<d> f;
+bool
+g (e &i)
+{
+  for (int h; h; ++h)
+    switch (f[h])
+      {
+      case 'x':
+      case 'a':
+	i.af[h] = 3;
+	break;
+      default:
+	return false;
+      }
+
+  return true;
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr68198.c b/gcc/testsuite/gcc.dg/tree-ssa/pr68198.c
index 16097d7e2bc..59d562e156c 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr68198.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr68198.c
@@ -37,7 +37,5 @@ c_finish_omp_clauses (tree clauses)
     }
 }
 
-/* There are 3 FSM jump threading opportunities, two of which will
-  get filtered out.  */
-/* { dg-final { scan-tree-dump-times "Registering FSM" 1 "thread1"} } */
-/* { dg-final { scan-tree-dump-times "FSM Thread through multiway branch without threading a multiway branch" 2 "thread1"} } */
+/* There are 3 FSM jump threading opportunities.  */
+/* { dg-final { scan-tree-dump-times "Registering FSM" 3 "thread1"} } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c b/gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c
new file mode 100644
index 00000000000..306253f3f9c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c
@@ -0,0 +1,14 @@
+/* { dg-options "-O2 -fdump-tree-switchconv" } */
+
+int check(int param)
+{
+  switch (param) 
+    {
+    case -2:
+      return 1;
+    default:
+      return 0;
+    }
+}
+
+/* { dg-final { scan-tree-dump "Expanding GIMPLE switch as condition" "switchconv" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp34.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp34.c
index 142e56c1641..d2a36a706f2 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp34.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp34.c
@@ -15,5 +15,6 @@ foo (int a)
     }
 }
 
-/* Both ifs should be optimized.  */
-/* { dg-final { scan-tree-dump-times "if \\\(" 0 "vrp1" } } */
+/* Both ifs should be optimized (and switch statement will be the only if
+   in the function).  */
+/* { dg-final { scan-tree-dump-times "if \\\(" 1 "vrp1" } } */
diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c
index 5a827a6f1f9..b1cc203aba2 100644
--- a/gcc/tree-switch-conversion.c
+++ b/gcc/tree-switch-conversion.c
@@ -1486,6 +1486,88 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info)
     }
 }
 
+/* Generate GIMPLE IL to basic block BB which compares whether INDEX
+   value is within range LOW ... HIGH.  We create a LHS and RHS that
+   can be then compared in order to hit the interval or not.  */
+
+static void
+generate_high_low_equality (basic_block bb, tree index, tree low, tree high,
+			    tree *lhs, tree *rhs)
+{
+  tree type = TREE_TYPE (index);
+  tree utype = unsigned_type_for (type);
+
+  low = fold_convert (type, low);
+  high = fold_convert (type, high);
+
+  tree tmp = make_ssa_name (type);
+  gassign *sub1
+    = gimple_build_assign (tmp, MINUS_EXPR, index, low);
+
+  *lhs = make_ssa_name (utype);
+  gassign *a = gimple_build_assign (*lhs, NOP_EXPR, tmp);
+
+  *rhs = fold_build2 (MINUS_EXPR, utype, high, low);
+  gimple_stmt_iterator gsi = gsi_last_bb (bb);
+  gsi_insert_before (&gsi, sub1, GSI_SAME_STMT);
+  gsi_insert_before (&gsi, a, GSI_SAME_STMT);
+}
+
+/* Expand SWTCH with at maximum a single non-default edge to simple gimple
+   condition.  */
+
+static void
+expand_degenerated_switch (gswitch *swtch)
+{
+  tree index = gimple_switch_index (swtch);
+  gimple_stmt_iterator gsi = gsi_for_stmt (swtch);
+
+  if (gimple_switch_num_labels (swtch) == 1)
+    {
+      gsi_remove (&gsi, true);
+
+      if (dump_file)
+	fprintf (dump_file, ";; Removing GIMPLE switch:\n");
+    }
+  else
+    {
+      tree default_label = CASE_LABEL (gimple_switch_default_label (swtch));
+      tree label = gimple_switch_label (swtch, 1);
+      tree low = CASE_LOW (label);
+      tree high = CASE_HIGH (label);
+
+      basic_block default_bb = label_to_block_fn (cfun, default_label);
+      basic_block case_bb = label_to_block_fn (cfun, CASE_LABEL (label));
+
+      basic_block bb = gimple_bb (swtch);
+      gcond *cond;
+
+      /* Replace switch statement with condition statement.  */
+      if (high)
+	{
+	  tree lhs, rhs;
+	  generate_high_low_equality (bb, index, low, high, &lhs, &rhs);
+	  cond = gimple_build_cond (LE_EXPR, lhs, rhs, NULL_TREE, NULL_TREE);
+	}
+      else
+	cond = gimple_build_cond (EQ_EXPR, index,
+				  fold_convert (TREE_TYPE (index), low),
+				  NULL_TREE, NULL_TREE);
+
+      gsi_replace (&gsi, cond, true);
+
+      /* Update edges.  */
+      edge case_edge = find_edge (bb, case_bb);
+      edge default_edge = find_edge (bb, default_bb);
+
+      case_edge->flags |= EDGE_TRUE_VALUE;
+      default_edge->flags |= EDGE_FALSE_VALUE;
+
+      if (dump_file)
+	fprintf (dump_file, ";; Expanding GIMPLE switch as condition:\n");
+    }
+}
+
 /* The following function is invoked on every switch statement (the current one
    is given in SWTCH) and runs the individual phases of switch conversion on it
    one after another until one fails or the conversion is completed.
@@ -1501,10 +1583,11 @@ process_switch (gswitch *swtch)
      that decide on the code generation approach for this switch.  */
   group_case_labels_stmt (swtch);
 
-  /* If this switch is now a degenerate case with only a default label,
-     there is nothing left for us to do.   */
-  if (gimple_switch_num_labels (swtch) < 2)
-    return "switch is a degenerate case";
+  if (gimple_switch_num_labels (swtch) <= 2)
+    {
+      expand_degenerated_switch (swtch);
+      return NULL;
+    }
 
   collect_switch_conv_info (swtch, &info);
 
@@ -2047,6 +2130,12 @@ try_switch_expansion (gswitch *stmt)
   hash_map<tree, tree> phi_mapping;
   auto_vec<basic_block> case_bbs;
 
+  if (gimple_switch_num_labels (stmt) <= 2)
+    {
+      expand_degenerated_switch (stmt);
+      return true;
+    }
+
   /* A list of case labels; it is first built as a list and it may then
      be rearranged into a nearly balanced binary tree.  */
   case_node *case_list = 0;
@@ -2058,10 +2147,6 @@ try_switch_expansion (gswitch *stmt)
      expressions being INTEGER_CST.  */
   gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
 
-  /* Optimization of switch statements with only one label has already
-     occurred, so we should never see them at this point.  */
-  gcc_assert (ncases > 1);
-
   /* Find the default case target label.  */
   tree default_label = CASE_LABEL (gimple_switch_default_label (stmt));
   default_bb = label_to_block_fn (cfun, default_label);
@@ -2702,27 +2787,13 @@ emit_case_nodes (basic_block bb, tree index, case_node_ptr node,
 	    }
 	  else if (!low_bound && !high_bound)
 	    {
-	      tree type = TREE_TYPE (index);
-	      tree utype = unsigned_type_for (type);
-
-	      tree lhs = make_ssa_name (type);
-	      gassign *sub1
-		= gimple_build_assign (lhs, MINUS_EXPR, index, node->low);
-
-	      tree converted = make_ssa_name (utype);
-	      gassign *a = gimple_build_assign (converted, NOP_EXPR, lhs);
-
-	      tree rhs = fold_build2 (MINUS_EXPR, utype,
-				      fold_convert (type, node->high),
-				      fold_convert (type, node->low));
-	      gimple_stmt_iterator gsi = gsi_last_bb (bb);
-	      gsi_insert_before (&gsi, sub1, GSI_SAME_STMT);
-	      gsi_insert_before (&gsi, a, GSI_SAME_STMT);
-
+	      tree lhs, rhs;
+	      generate_high_low_equality (bb, index, node->low, node->high,
+					  &lhs, &rhs);
 	      probability
 		= conditional_probability (default_prob,
 					   subtree_prob + default_prob);
-	      bb = emit_cmp_and_jump_insns (bb, converted, rhs, GT_EXPR,
+	      bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR,
 					    default_bb, probability,
 					    phi_mapping);
 	    }