re PR tree-optimization/79472 (x86-64: Switch table generation fails if default case has different code)

	PR tree-optimization/79472
	* tree-switch-conversion.c (struct switch_conv_info): Add
	contiguous_range and default_case_nonstandard fields.
	(collect_switch_conv_info): Compute contiguous_range and
	default_case_nonstandard fields, don't clear final_bb if
	contiguous_range and only the default case doesn't have the required
	structure.
	(check_all_empty_except_final): Set default_case_nonstandard instead
	of failing if contiguous_range and the default case doesn't have empty
	block.
	(check_final_bb): Add SWTCH argument, don't fail if contiguous_range
	and only the default case doesn't have the required constants.  Skip
	virtual phis.
	(gather_default_values): Skip virtual phis.  Allow non-NULL CASE_LOW
	if default_case_nonstandard.
	(build_constructors): Build constant 1 just once.  Assert that default
	values aren't inserted in between cases if contiguous_range.  Skip
	virtual phis.
	(build_arrays): Skip virtual phis.
	(prune_bbs): Add DEFAULT_BB argument, don't remove that bb.
	(fix_phi_nodes): Don't add e2f phi arg if default_case_nonstandard.
	Handle virtual phis.
	(gen_inbound_check): Handle default_case_nonstandard case.
	(process_switch): Adjust check_final_bb caller.  Call
	gather_default_values with the first non-default case instead of
	default case if default_case_nonstandard.

	* gcc.dg/tree-ssa/vrp40.c: Add -fno-tree-switch-conversion to dg-options.
	* gcc.dg/tree-ssa/vrp113.c: New test.
	* gcc.dg/tree-ssa/cswtch-3.c: New test.
	* gcc.dg/tree-ssa/cswtch-4.c: New test.
	* gcc.dg/tree-ssa/cswtch-5.c: New test.

From-SVN: r247538

8 files changed, 716 insertions, 71 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index e36fdc9..c565697 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,32 @@
+2017-05-03  Jakub Jelinek  <jakub@redhat.com>
+
+	PR tree-optimization/79472
+	* tree-switch-conversion.c (struct switch_conv_info): Add
+	contiguous_range and default_case_nonstandard fields.
+	(collect_switch_conv_info): Compute contiguous_range and
+	default_case_nonstandard fields, don't clear final_bb if
+	contiguous_range and only the default case doesn't have the required
+	structure.
+	(check_all_empty_except_final): Set default_case_nonstandard instead
+	of failing if contiguous_range and the default case doesn't have empty
+	block.
+	(check_final_bb): Add SWTCH argument, don't fail if contiguous_range
+	and only the default case doesn't have the required constants.  Skip
+	virtual phis.
+	(gather_default_values): Skip virtual phis.  Allow non-NULL CASE_LOW
+	if default_case_nonstandard.
+	(build_constructors): Build constant 1 just once.  Assert that default
+	values aren't inserted in between cases if contiguous_range.  Skip
+	virtual phis.
+	(build_arrays): Skip virtual phis.
+	(prune_bbs): Add DEFAULT_BB argument, don't remove that bb.
+	(fix_phi_nodes): Don't add e2f phi arg if default_case_nonstandard.
+	Handle virtual phis.
+	(gen_inbound_check): Handle default_case_nonstandard case.
+	(process_switch): Adjust check_final_bb caller.  Call
+	gather_default_values with the first non-default case instead of
+	default case if default_case_nonstandard.
+
 2017-05-02  Nathan Sidwell  <nathan@acm.org>
 
 	* ggc-page.c (move_ptes_to_front): Replace unsigned >0 with i--
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index e84e045..3f6190bd 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,12 @@
+2017-05-03  Jakub Jelinek  <jakub@redhat.com>
+
+	PR tree-optimization/79472
+	* gcc.dg/tree-ssa/vrp40.c: Add -fno-tree-switch-conversion to dg-options.
+	* gcc.dg/tree-ssa/vrp113.c: New test.
+	* gcc.dg/tree-ssa/cswtch-3.c: New test.
+	* gcc.dg/tree-ssa/cswtch-4.c: New test.
+	* gcc.dg/tree-ssa/cswtch-5.c: New test.
+
 2017-05-03  Tom de Vries  <tom@codesourcery.com>
 
 	PR testsuite/80557
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cswtch-3.c b/gcc/testsuite/gcc.dg/tree-ssa/cswtch-3.c
new file mode 100644
index 0000000..b983c8f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cswtch-3.c
@@ -0,0 +1,330 @@
+/* PR tree-optimization/79472 */
+/* { dg-options "-O2 -fdump-tree-switchconv" } */
+/* { dg-do run } */
+
+int *expected;
+
+void
+foo (int x, int y)
+{
+  if (x != expected[0] || y != expected[1])
+    __builtin_abort ();
+  expected += 2;
+}
+
+__attribute__((noinline, noclone)) void
+f1 (int v, int w)
+{
+  int i, j;
+  if (w)
+    {
+      i = 129;
+      j = i - 1;
+      goto lab;
+    }
+  switch (v)
+    {
+    case 170:
+      j = 7;
+      i = 27;
+      break;
+    case 171:
+      i = 8;
+      j = 122;
+      break;
+    case 172:
+      i = 21;
+      j = -19;
+      break;
+    case 173:
+      i = 18;
+      j = 17;
+      break;
+    case 174:
+      i = 139;
+      j = -5;
+      break;
+    case 175:
+      i = 14;
+      j = -26;
+      break;
+    case 176:
+      j = 5;
+      i = -14;
+      break;
+    case 177:
+      j = 8;
+      i = 12;
+      break;
+    default:
+      __builtin_abort ();
+    }
+
+ lab:
+  foo (i, j);
+}
+
+__attribute__((noinline, noclone)) void
+f2 (int v)
+{
+  int i, j;
+  switch (v)
+    {
+    case 170:
+      j = 7;
+      i = 27;
+      break;
+    case 171:
+      i = 8;
+      j = 122;
+      break;
+    case 172:
+      i = 21;
+      j = -19;
+      break;
+    case 173:
+      i = 18;
+      j = 17;
+      break;
+    case 174:
+      i = 139;
+      j = -5;
+      break;
+    case 175:
+      i = 14;
+      j = -26;
+      break;
+    case 176:
+      j = 5;
+      i = -14;
+      break;
+    case 177:
+      j = 8;
+      i = 12;
+      break;
+    default:
+      foo (5, 12);
+      foo (17, 19);
+      i = 8;
+      j = 19;
+      break;
+    }
+
+  foo (i, j);
+}
+
+__attribute__((noinline, noclone)) void
+f3 (int v)
+{
+  int i;
+  switch (v)
+    {
+    default:
+      i = v;
+      goto lab;
+    case 170:
+      i = 27;
+      break;
+    case 171:
+      i = 8;
+      break;
+    case 172:
+      i = 21;
+      break;
+    case 173:
+      i = 18;
+      break;
+    case 174:
+      i = 139;
+      break;
+    case 175:
+      i = 14;
+      break;
+    case 176:
+      i = -14;
+      break;
+    case 177:
+      i = 12;
+      break;
+    }
+
+ lab:
+  foo (i, -5);
+}
+
+__attribute__((noinline, noclone)) void
+f4 (int v, int w)
+{
+  int i, j, k = 5;
+  if (w)
+    {
+      foo (0, 0);
+      k = 26;
+      goto do_default;
+    }
+  switch (v)
+    {
+    case 170:
+      j = 7;
+      i = 27;
+      break;
+    case 171:
+      i = 8;
+      j = 122;
+      break;
+    case 172:
+      i = 21;
+      j = -19;
+      break;
+    case 173:
+      i = 18;
+      j = 17;
+      break;
+    case 174:
+      i = 139;
+      j = -5;
+      break;
+    case 175:
+      i = 14;
+      j = -26;
+      break;
+    case 176:
+      j = 5;
+      i = -14;
+      break;
+    case 177:
+      j = 8;
+      i = 12;
+      break;
+    default:
+    do_default:
+      foo (5, 12);
+      foo (17, 19);
+      i = 8;
+      j = 19;
+      break;
+    }
+
+  foo (i, j + k);
+}
+
+void
+f5 (int v, int w)
+{
+  int i;
+  if (w)
+    {
+      foo (23, 0);
+      i = 129;
+    }
+  else
+    switch (v)
+      {
+      case 170:
+	i = 27;
+	break;
+      case 171:
+	i = 8;
+	break;
+      case 172:
+	i = 21;
+	break;
+      case 173:
+	i = 18;
+	break;
+      case 174:
+	i = 139;
+	break;
+      case 175:
+	i = 14;
+	break;
+      case 176:
+	i = -14;
+	break;
+      case 177:
+	i = 12;
+	break;
+      default:
+	i = 80;
+	break;
+      }
+
+ lab:
+  foo (i, 0);
+}
+
+int
+main ()
+{
+  int *e;
+#define T(call, cnt, ...) \
+  expected = e = (int []) __VA_ARGS__;		\
+  call;						\
+  if (expected != e + cnt)			\
+    __builtin_abort ()
+  T (f1 (171, 1), 2, { 129, 128 });
+  T (f1 (140, 1), 2, { 129, 128 });
+  T (f1 (170, 0), 2, { 27, 7 });
+  T (f1 (171, 0), 2, { 8, 122 });
+  T (f1 (172, 0), 2, { 21, -19 });
+  T (f1 (173, 0), 2, { 18, 17 });
+  T (f1 (174, 0), 2, { 139, -5 });
+  T (f1 (175, 0), 2, { 14, -26 });
+  T (f1 (176, 0), 2, { -14, 5 });
+  T (f1 (177, 0), 2, { 12, 8 });
+  T (f2 (-31), 6, { 5, 12, 17, 19, 8, 19 });
+  T (f2 (169), 6, { 5, 12, 17, 19, 8, 19 });
+  T (f2 (170), 2, { 27, 7 });
+  T (f2 (171), 2, { 8, 122 });
+  T (f2 (172), 2, { 21, -19 });
+  T (f2 (173), 2, { 18, 17 });
+  T (f2 (174), 2, { 139, -5 });
+  T (f2 (175), 2, { 14, -26 });
+  T (f2 (176), 2, { -14, 5 });
+  T (f2 (177), 2, { 12, 8 });
+  T (f2 (178), 6, { 5, 12, 17, 19, 8, 19 });
+  T (f2 (231), 6, { 5, 12, 17, 19, 8, 19 });
+  T (f3 (-31), 2, { -31, -5 });
+  T (f3 (169), 2, { 169, -5 });
+  T (f3 (170), 2, { 27, -5 });
+  T (f3 (171), 2, { 8, -5 });
+  T (f3 (172), 2, { 21, -5 });
+  T (f3 (173), 2, { 18, -5 });
+  T (f3 (174), 2, { 139, -5 });
+  T (f3 (175), 2, { 14, -5 });
+  T (f3 (176), 2, { -14, -5 });
+  T (f3 (177), 2, { 12, -5 });
+  T (f3 (178), 2, { 178, -5 });
+  T (f3 (231), 2, { 231, -5 });
+  T (f4 (171, 1), 8, { 0, 0, 5, 12, 17, 19, 8, 45 });
+  T (f4 (140, 1), 8, { 0, 0, 5, 12, 17, 19, 8, 45 });
+  T (f4 (-31, 0), 6, { 5, 12, 17, 19, 8, 24 });
+  T (f4 (169, 0), 6, { 5, 12, 17, 19, 8, 24 });
+  T (f4 (170, 0), 2, { 27, 12 });
+  T (f4 (171, 0), 2, { 8, 127 });
+  T (f4 (172, 0), 2, { 21, -14 });
+  T (f4 (173, 0), 2, { 18, 22 });
+  T (f4 (174, 0), 2, { 139, 0 });
+  T (f4 (175, 0), 2, { 14, -21 });
+  T (f4 (176, 0), 2, { -14, 10 });
+  T (f4 (177, 0), 2, { 12, 13 });
+  T (f4 (178, 0), 6, { 5, 12, 17, 19, 8, 24 });
+  T (f4 (231, 0), 6, { 5, 12, 17, 19, 8, 24 });
+  T (f5 (171, 1), 4, { 23, 0, 129, 0 });
+  T (f5 (140, 1), 4, { 23, 0, 129, 0 });
+  T (f5 (-31, 0), 2, { 80, 0 });
+  T (f5 (169, 0), 2, { 80, 0 });
+  T (f5 (170, 0), 2, { 27, 0 });
+  T (f5 (171, 0), 2, { 8, 0 });
+  T (f5 (172, 0), 2, { 21, 0 });
+  T (f5 (173, 0), 2, { 18, 0 });
+  T (f5 (174, 0), 2, { 139, 0 });
+  T (f5 (175, 0), 2, { 14, 0 });
+  T (f5 (176, 0), 2, { -14, 0 });
+  T (f5 (177, 0), 2, { 12, 0 });
+  T (f5 (178, 0), 2, { 80, 0 });
+  T (f5 (231, 0), 2, { 80, 0 });
+}
+
+/* { dg-final { scan-tree-dump-times "Switch converted" 5 "switchconv" } } */
+/* { dg-final { scan-tree-dump-times "= CSWTCH" 8 "switchconv" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cswtch-4.c b/gcc/testsuite/gcc.dg/tree-ssa/cswtch-4.c
new file mode 100644
index 0000000..962690d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cswtch-4.c
@@ -0,0 +1,57 @@
+/* PR tree-optimization/79472 */
+/* { dg-options "-O2 -fdump-tree-switchconv" } */
+/* { dg-do compile } */
+
+void
+frobulate (unsigned int v)
+{
+  const char *s;
+  
+  switch (v)
+    {
+    case 0:
+      s = "foo";
+      break;
+    case 1:
+      s = "bar";
+      break;
+    case 2:
+      s = "spam";
+      break;
+    default:
+      __builtin_abort ();
+      break;
+    }
+
+  __builtin_printf ("%s\n", s);
+}
+
+void
+frobulate_for_gcc (unsigned int v)
+{
+  const char *s;
+  
+  switch (v)
+    {
+    case 0:
+      s = "foo";
+      break;
+    case 1:
+      s = "bar";
+      break;
+    case 2:
+      s = "spam";
+      break;
+    default:
+      s = (const char *) 0;
+      break;
+    }
+  
+  if (!s)
+    __builtin_abort ();
+  
+  __builtin_printf ("%s\n", s);
+}
+
+/* { dg-final { scan-tree-dump-times "Switch converted" 2 "switchconv" } } */
+/* { dg-final { scan-tree-dump-times "= CSWTCH" 2 "switchconv" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cswtch-5.c b/gcc/testsuite/gcc.dg/tree-ssa/cswtch-5.c
new file mode 100644
index 0000000..96a86bb
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cswtch-5.c
@@ -0,0 +1,66 @@
+/* PR tree-optimization/79472 */
+/* { dg-options "-O2 -fdump-tree-switchconv" } */
+/* { dg-do compile } */
+
+void
+foo (unsigned int v)
+{
+  const char *s;
+  
+  switch (v)
+    {
+    case 0:
+      s = "foo";
+      break;
+    case 1:
+      s = "bar";
+      break;
+    case 2:
+      s = "spam";
+      break;
+    default:
+      for (int i = 0; i < v; i++)
+        __builtin_printf ("baz\n");
+      return;
+    }
+
+  __builtin_printf ("%s\n", s);
+}
+
+int
+bar (unsigned int v, int w)
+{
+  const char *s;
+  
+  switch (v)
+    {
+    case 0:
+      s = "foo";
+      break;
+    case 1:
+      s = "bar";
+      break;
+    case 2:
+      s = "spam";
+      break;
+    default:
+      __builtin_printf ("baz\n");
+      if (v > 25)
+	__builtin_printf ("bl1\n");
+      else
+	__builtin_printf ("bl2\n");
+      goto lab;
+    }
+
+  __builtin_printf ("%s\n", s);
+  if (w > 25)
+    __builtin_printf ("cl1\n");
+  else
+    __builtin_printf ("cl2\n");
+ lab:
+  __builtin_printf ("dl\n");
+  return v + w;
+}
+
+/* { dg-final { scan-tree-dump-times "Switch converted" 2 "switchconv" } } */
+/* { dg-final { scan-tree-dump-times "= CSWTCH" 2 "switchconv" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp113.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp113.c
new file mode 100644
index 0000000..5069fdf
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp113.c
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp1" } */
+
+int f(int a) {
+    switch (a & 1) {
+      case 0:
+      case 1: return  3;
+      case 2: return  5;
+      case 3: return  7;
+      case 4: return 11;
+      case 5: return 13;
+      case 6: return 17;
+      case 7: return 19;
+    }
+}
+
+/* { dg-final { scan-tree-dump "return 3;" "vrp1" { xfail *-*-* } } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp40.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp40.c
index de56179..394b5fc 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp40.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp40.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-vrp1" } */
+/* { dg-options "-O2 -fdump-tree-vrp1 -fno-tree-switch-conversion" } */
 
 int f(int a) {
     switch (a & 1) {
diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c
index 1ccb4bd..14e605d 100644
--- a/gcc/tree-switch-conversion.c
+++ b/gcc/tree-switch-conversion.c
@@ -592,6 +592,14 @@ struct switch_conv_info
      dump file, if there is one.  */
   const char *reason;
 
+  /* True if default case is not used for any value between range_min and
+     range_max inclusive.  */
+  bool contiguous_range;
+
+  /* True if default case does not have the required shape for other case
+     labels.  */
+  bool default_case_nonstandard;
+
   /* Parameters for expand_switch_using_bit_tests.  Should be computed
      the same way as in expand_case.  */
   unsigned int uniq;
@@ -606,8 +614,9 @@ collect_switch_conv_info (gswitch *swtch, struct switch_conv_info *info)
   unsigned int branch_num = gimple_switch_num_labels (swtch);
   tree min_case, max_case;
   unsigned int count, i;
-  edge e, e_default;
+  edge e, e_default, e_first;
   edge_iterator ei;
+  basic_block first;
 
   memset (info, 0, sizeof (*info));
 
@@ -616,8 +625,8 @@ collect_switch_conv_info (gswitch *swtch, struct switch_conv_info *info)
      Collect the bits we can deduce from the CFG.  */
   info->index_expr = gimple_switch_index (swtch);
   info->switch_bb = gimple_bb (swtch);
-  info->default_bb =
-    label_to_block (CASE_LABEL (gimple_switch_default_label (swtch)));
+  info->default_bb
+    = label_to_block (CASE_LABEL (gimple_switch_default_label (swtch)));
   e_default = find_edge (info->switch_bb, info->default_bb);
   info->default_prob = e_default->probability;
   info->default_count = e_default->count;
@@ -625,17 +634,54 @@ collect_switch_conv_info (gswitch *swtch, struct switch_conv_info *info)
     if (e != e_default)
       info->other_count += e->count;
 
+  /* Get upper and lower bounds of case values, and the covered range.  */
+  min_case = gimple_switch_label (swtch, 1);
+  max_case = gimple_switch_label (swtch, branch_num - 1);
+
+  info->range_min = CASE_LOW (min_case);
+  if (CASE_HIGH (max_case) != NULL_TREE)
+    info->range_max = CASE_HIGH (max_case);
+  else
+    info->range_max = CASE_LOW (max_case);
+
+  info->contiguous_range = true;
+  tree last = CASE_HIGH (min_case) ? CASE_HIGH (min_case) : info->range_min;
+  for (i = 2; i < branch_num; i++)
+    {
+      tree elt = gimple_switch_label (swtch, i);
+      wide_int w = last;
+      if (w + 1 != CASE_LOW (elt))
+	{
+	  info->contiguous_range = false;
+	  break;
+	}
+      last = CASE_HIGH (elt) ? CASE_HIGH (elt) : CASE_LOW (elt);
+    }
+
+  if (info->contiguous_range)
+    {
+      first = label_to_block (CASE_LABEL (gimple_switch_label (swtch, 1)));
+      e_first = find_edge (info->switch_bb, first);
+    }
+  else
+    {
+      first = info->default_bb;
+      e_first = e_default;
+    }
+
   /* See if there is one common successor block for all branch
      targets.  If it exists, record it in FINAL_BB.
-     Start with the destination of the default case as guess
-     or its destination in case it is a forwarder block.  */
-  if (! single_pred_p (e_default->dest))
-    info->final_bb = e_default->dest;
-  else if (single_succ_p (e_default->dest)
-	   && ! single_pred_p (single_succ (e_default->dest)))
-    info->final_bb = single_succ (e_default->dest);
+     Start with the destination of the first non-default case
+     if the range is contiguous and default case otherwise as
+     guess or its destination in case it is a forwarder block.  */
+  if (! single_pred_p (e_first->dest))
+    info->final_bb = e_first->dest;
+  else if (single_succ_p (e_first->dest)
+	   && ! single_pred_p (single_succ (e_first->dest)))
+    info->final_bb = single_succ (e_first->dest);
   /* Require that all switch destinations are either that common
-     FINAL_BB or a forwarder to it.  */
+     FINAL_BB or a forwarder to it, except for the default
+     case if contiguous range.  */
   if (info->final_bb)
     FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
       {
@@ -647,22 +693,18 @@ collect_switch_conv_info (gswitch *swtch, struct switch_conv_info *info)
 	    && single_succ (e->dest) == info->final_bb)
 	  continue;
 
+	if (e == e_default && info->contiguous_range)
+	  {
+	    info->default_case_nonstandard = true;
+	    continue;
+	  }
+
 	info->final_bb = NULL;
 	break;
       }
 
-  /* Get upper and lower bounds of case values, and the covered range.  */
-  min_case = gimple_switch_label (swtch, 1);
-  max_case = gimple_switch_label (swtch, branch_num - 1);
-
-  info->range_min = CASE_LOW (min_case);
-  if (CASE_HIGH (max_case) != NULL_TREE)
-    info->range_max = CASE_HIGH (max_case);
-  else
-    info->range_max = CASE_LOW (max_case);
-
-  info->range_size =
-    int_const_binop (MINUS_EXPR, info->range_max, info->range_min);
+  info->range_size
+    = int_const_binop (MINUS_EXPR, info->range_max, info->range_min);
 
   /* Get a count of the number of case labels.  Single-valued case labels
      simply count as one, but a case range counts double, since it may
@@ -713,7 +755,7 @@ check_range (struct switch_conv_info *info)
 static bool
 check_all_empty_except_final (struct switch_conv_info *info)
 {
-  edge e;
+  edge e, e_default = find_edge (info->switch_bb, info->default_bb);
   edge_iterator ei;
 
   FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
@@ -723,6 +765,12 @@ check_all_empty_except_final (struct switch_conv_info *info)
 
       if (!empty_block_p (e->dest))
 	{
+	  if (info->contiguous_range && e == e_default)
+	    {
+	      info->default_case_nonstandard = true;
+	      continue;
+	    }
+
 	  info->reason = "bad case - a non-final BB not empty";
 	  return false;
 	}
@@ -737,7 +785,7 @@ check_all_empty_except_final (struct switch_conv_info *info)
    phi nodes are OK, otherwise false.  */
 
 static bool
-check_final_bb (struct switch_conv_info *info)
+check_final_bb (gswitch *swtch, struct switch_conv_info *info)
 {
   gphi_iterator gsi;
 
@@ -747,6 +795,9 @@ check_final_bb (struct switch_conv_info *info)
       gphi *phi = gsi.phi ();
       unsigned int i;
 
+      if (virtual_operand_p (gimple_phi_result (phi)))
+	continue;
+
       info->phi_count++;
 
       for (i = 0; i < gimple_phi_num_args (phi); i++)
@@ -754,27 +805,55 @@ check_final_bb (struct switch_conv_info *info)
 	  basic_block bb = gimple_phi_arg_edge (phi, i)->src;
 
 	  if (bb == info->switch_bb
-	      || (single_pred_p (bb) && single_pred (bb) == info->switch_bb))
+	      || (single_pred_p (bb)
+		  && single_pred (bb) == info->switch_bb
+		  && (!info->default_case_nonstandard
+		      || empty_block_p (bb))))
 	    {
 	      tree reloc, val;
+	      const char *reason = NULL;
 
 	      val = gimple_phi_arg_def (phi, i);
 	      if (!is_gimple_ip_invariant (val))
+		reason = "non-invariant value from a case";
+	      else
 		{
-		  info->reason = "non-invariant value from a case";
-		  return false; /* Non-invariant argument.  */
+		  reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
+		  if ((flag_pic && reloc != null_pointer_node)
+		      || (!flag_pic && reloc == NULL_TREE))
+		    {
+		      if (reloc)
+			reason
+			  = "value from a case would need runtime relocations";
+		      else
+			reason
+			  = "value from a case is not a valid initializer";
+		    }
 		}
-	      reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
-	      if ((flag_pic && reloc != null_pointer_node)
-		  || (!flag_pic && reloc == NULL_TREE))
+	      if (reason)
 		{
-		  if (reloc)
-		    info->reason
-		      = "value from a case would need runtime relocations";
-		  else
-		    info->reason
-		      = "value from a case is not a valid initializer";
-		  return false;
+		  /* For contiguous range, we can allow non-constant
+		     or one that needs relocation, as long as it is
+		     only reachable from the default case.  */
+		  if (bb == info->switch_bb)
+		    bb = info->final_bb;
+		  if (!info->contiguous_range || bb != info->default_bb)
+		    {
+		      info->reason = reason;
+		      return false;
+		    }
+
+		  unsigned int branch_num = gimple_switch_num_labels (swtch);
+		  for (unsigned int i = 1; i < branch_num; i++)
+		    {
+		      tree lab = CASE_LABEL (gimple_switch_label (swtch, i));
+		      if (label_to_block (lab) == bb)
+			{
+			  info->reason = reason;
+			  return false;
+			}
+		    }
+		  info->default_case_nonstandard = true;
 		}
 	    }
 	}
@@ -815,7 +894,9 @@ free_temp_arrays (struct switch_conv_info *info)
 }
 
 /* Populate the array of default values in the order of phi nodes.
-   DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch.  */
+   DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch
+   if the range is non-contiguous or the default case has standard
+   structure, otherwise it is the first non-default case instead.  */
 
 static void
 gather_default_values (tree default_case, struct switch_conv_info *info)
@@ -825,7 +906,8 @@ gather_default_values (tree default_case, struct switch_conv_info *info)
   edge e;
   int i = 0;
 
-  gcc_assert (CASE_LOW (default_case) == NULL_TREE);
+  gcc_assert (CASE_LOW (default_case) == NULL_TREE
+	      || info->default_case_nonstandard);
 
   if (bb == info->final_bb)
     e = find_edge (info->switch_bb, bb);
@@ -835,6 +917,8 @@ gather_default_values (tree default_case, struct switch_conv_info *info)
   for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
     {
       gphi *phi = gsi.phi ();
+      if (virtual_operand_p (gimple_phi_result (phi)))
+	continue;
       tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
       gcc_assert (val);
       info->default_values[i++] = val;
@@ -850,6 +934,7 @@ build_constructors (gswitch *swtch, struct switch_conv_info *info)
 {
   unsigned i, branch_num = gimple_switch_num_labels (swtch);
   tree pos = info->range_min;
+  tree pos_one = build_int_cst (TREE_TYPE (pos), 1);
 
   for (i = 1; i < branch_num; i++)
     {
@@ -869,6 +954,7 @@ build_constructors (gswitch *swtch, struct switch_conv_info *info)
       while (tree_int_cst_lt (pos, CASE_LOW (cs)))
 	{
 	  int k;
+	  gcc_assert (!info->contiguous_range);
 	  for (k = 0; k < info->phi_count; k++)
 	    {
 	      constructor_elt elt;
@@ -879,8 +965,7 @@ build_constructors (gswitch *swtch, struct switch_conv_info *info)
 	      info->constructors[k]->quick_push (elt);
 	    }
 
-	  pos = int_const_binop (PLUS_EXPR, pos,
-				 build_int_cst (TREE_TYPE (pos), 1));
+	  pos = int_const_binop (PLUS_EXPR, pos, pos_one);
 	}
       gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
 
@@ -893,6 +978,8 @@ build_constructors (gswitch *swtch, struct switch_conv_info *info)
 	   !gsi_end_p (gsi); gsi_next (&gsi))
 	{
 	  gphi *phi = gsi.phi ();
+	  if (virtual_operand_p (gimple_phi_result (phi)))
+	    continue;
 	  tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
 	  tree low = CASE_LOW (cs);
 	  pos = CASE_LOW (cs);
@@ -905,8 +992,7 @@ build_constructors (gswitch *swtch, struct switch_conv_info *info)
 	      elt.value = unshare_expr_without_location (val);
 	      info->constructors[j]->quick_push (elt);
 
-	      pos = int_const_binop (PLUS_EXPR, pos,
-				     build_int_cst (TREE_TYPE (pos), 1));
+	      pos = int_const_binop (PLUS_EXPR, pos, pos_one);
 	    } while (!tree_int_cst_lt (high, pos)
 		     && tree_int_cst_lt (low, pos));
 	  j++;
@@ -1125,8 +1211,12 @@ build_arrays (gswitch *swtch, struct switch_conv_info *info)
   info->arr_ref_first = stmt;
 
   for (gpi = gsi_start_phis (info->final_bb), i = 0;
-       !gsi_end_p (gpi); gsi_next (&gpi), i++)
-    build_one_array (swtch, i, arr_index_type, gpi.phi (), tidx, info);
+       !gsi_end_p (gpi); gsi_next (&gpi))
+    {
+      gphi *phi = gpi.phi ();
+      if (!virtual_operand_p (gimple_phi_result (phi)))
+	build_one_array (swtch, i++, arr_index_type, phi, tidx, info);
+    }
 }
 
 /* Generates and appropriately inserts loads of default values at the position
@@ -1155,7 +1245,7 @@ gen_def_assigns (gimple_stmt_iterator *gsi, struct switch_conv_info *info)
    of succession).  */
 
 static void
-prune_bbs (basic_block bbd, basic_block final)
+prune_bbs (basic_block bbd, basic_block final, basic_block default_bb)
 {
   edge_iterator ei;
   edge e;
@@ -1165,7 +1255,7 @@ prune_bbs (basic_block bbd, basic_block final)
       basic_block bb;
       bb = e->dest;
       remove_edge (e);
-      if (bb != final)
+      if (bb != final && bb != default_bb)
 	delete_basic_block (bb);
     }
   delete_basic_block (bbd);
@@ -1184,11 +1274,20 @@ fix_phi_nodes (edge e1f, edge e2f, basic_block bbf,
   int i;
 
   for (gsi = gsi_start_phis (bbf), i = 0;
-       !gsi_end_p (gsi); gsi_next (&gsi), i++)
+       !gsi_end_p (gsi); gsi_next (&gsi))
     {
       gphi *phi = gsi.phi ();
-      add_phi_arg (phi, info->target_inbound_names[i], e1f, UNKNOWN_LOCATION);
-      add_phi_arg (phi, info->target_outbound_names[i], e2f, UNKNOWN_LOCATION);
+      tree inbound, outbound;
+      if (virtual_operand_p (gimple_phi_result (phi)))
+	inbound = outbound = gimple_vop (cfun);
+      else
+	{
+	  inbound = info->target_inbound_names[i];
+	  outbound = info->target_outbound_names[i++];
+	}
+      add_phi_arg (phi, inbound, e1f, UNKNOWN_LOCATION);
+      if (!info->default_case_nonstandard)
+	add_phi_arg (phi, outbound, e2f, UNKNOWN_LOCATION);
     }
 }
 
@@ -1225,10 +1324,10 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info)
 
   gcond *cond_stmt;
 
-  gassign *last_assign;
+  gassign *last_assign = NULL;
   gimple_stmt_iterator gsi;
   basic_block bb0, bb1, bb2, bbf, bbd;
-  edge e01, e02, e21, e1d, e1f, e2f;
+  edge e01 = NULL, e02, e21, e1d, e1f, e2f;
   location_t loc = gimple_location (swtch);
 
   gcc_assert (info->default_values);
@@ -1248,9 +1347,12 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info)
   update_stmt (cond_stmt);
 
   /* block 2 */
-  label2 = gimple_build_label (label_decl2);
-  gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
-  last_assign = gen_def_assigns (&gsi, info);
+  if (!info->default_case_nonstandard)
+    {
+      label2 = gimple_build_label (label_decl2);
+      gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
+      last_assign = gen_def_assigns (&gsi, info);
+    }
 
   /* block 1 */
   label1 = gimple_build_label (label_decl1);
@@ -1265,16 +1367,40 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info)
   e02 = split_block (bb0, cond_stmt);
   bb2 = e02->dest;
 
-  e21 = split_block (bb2, last_assign);
-  bb1 = e21->dest;
-  remove_edge (e21);
+  if (info->default_case_nonstandard)
+    {
+      bb1 = bb2;
+      bb2 = info->default_bb;
+      e01 = e02;
+      e01->flags = EDGE_TRUE_VALUE;
+      e02 = make_edge (bb0, bb2, EDGE_FALSE_VALUE);
+      edge e_default = find_edge (bb1, bb2);
+      for (gphi_iterator gsi = gsi_start_phis (bb2);
+	   !gsi_end_p (gsi); gsi_next (&gsi))
+	{
+	  gphi *phi = gsi.phi ();
+	  tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e_default);
+	  add_phi_arg (phi, arg, e02,
+		       gimple_phi_arg_location_from_edge (phi, e_default));
+	}
+      /* Partially fix the dominator tree, if it is available.  */
+      if (dom_info_available_p (CDI_DOMINATORS))
+	redirect_immediate_dominators (CDI_DOMINATORS, bb1, bb0);
+    }
+  else
+    {
+      e21 = split_block (bb2, last_assign);
+      bb1 = e21->dest;
+      remove_edge (e21);
+    }
 
   e1d = split_block (bb1, info->arr_ref_last);
   bbd = e1d->dest;
   remove_edge (e1d);
 
   /* flags and profiles of the edge for in-range values */
-  e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
+  if (!info->default_case_nonstandard)
+    e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
   e01->probability = REG_BR_PROB_BASE - info->default_prob;
   e01->count = info->other_count;
 
@@ -1290,17 +1416,24 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info)
   e1f->probability = REG_BR_PROB_BASE;
   e1f->count = info->other_count;
 
-  e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
-  e2f->probability = REG_BR_PROB_BASE;
-  e2f->count = info->default_count;
+  if (info->default_case_nonstandard)
+    e2f = NULL;
+  else
+    {
+      e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
+      e2f->probability = REG_BR_PROB_BASE;
+      e2f->count = info->default_count;
+    }
 
   /* frequencies of the new BBs */
   bb1->frequency = EDGE_FREQUENCY (e01);
   bb2->frequency = EDGE_FREQUENCY (e02);
-  bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f);
+  if (!info->default_case_nonstandard)
+    bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f);
 
   /* Tidy blocks that have become unreachable.  */
-  prune_bbs (bbd, info->final_bb);
+  prune_bbs (bbd, info->final_bb,
+	     info->default_case_nonstandard ? info->default_bb : NULL);
 
   /* Fixup the PHI nodes in bbF.  */
   fix_phi_nodes (e1f, e2f, bbf, info);
@@ -1311,15 +1444,17 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info)
       vec<basic_block> bbs_to_fix_dom;
 
       set_immediate_dominator (CDI_DOMINATORS, bb1, bb0);
-      set_immediate_dominator (CDI_DOMINATORS, bb2, bb0);
+      if (!info->default_case_nonstandard)
+	set_immediate_dominator (CDI_DOMINATORS, bb2, bb0);
       if (! get_immediate_dominator (CDI_DOMINATORS, bbf))
 	/* If bbD was the immediate dominator ...  */
 	set_immediate_dominator (CDI_DOMINATORS, bbf, bb0);
 
-      bbs_to_fix_dom.create (4);
+      bbs_to_fix_dom.create (3 + (bb2 != bbf));
       bbs_to_fix_dom.quick_push (bb0);
       bbs_to_fix_dom.quick_push (bb1);
-      bbs_to_fix_dom.quick_push (bb2);
+      if (bb2 != bbf)
+	bbs_to_fix_dom.quick_push (bb2);
       bbs_to_fix_dom.quick_push (bbf);
 
       iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
@@ -1394,7 +1529,7 @@ process_switch (gswitch *swtch)
       gcc_assert (info.reason);
       return info.reason;
     }
-  if (!check_final_bb (&info))
+  if (!check_final_bb (swtch, &info))
     {
       gcc_assert (info.reason);
       return info.reason;
@@ -1404,7 +1539,9 @@ process_switch (gswitch *swtch)
      transformation.  */
 
   create_temp_arrays (&info);
-  gather_default_values (gimple_switch_default_label (swtch), &info);
+  gather_default_values (info.default_case_nonstandard
+			 ? gimple_switch_label (swtch, 1)
+			 : gimple_switch_default_label (swtch), &info);
   build_constructors (swtch, &info);
 
   build_arrays (swtch, &info); /* Build the static arrays and assignments.   */