[RFC] Improve switchconv optimization (PR tree-optimization/79472)

Hi!

The following patch is an attempt to fix a regression where we no longer
switch convert one switch because earlier optimizations turn it into
unsupported shape.

The patch contains two important changes (that can perhaps be split off
separately):
1) handle virtual PHIs; while because we require all the switch bbs
   to be empty, all the edges from the switch to final_bb should have the
   same virtual op SSA_NAME, if the final_bb is reachable through other
   edges from other code, it might have virtual PHI and switchconv would
   unnecessarily give up
2) if the switch cases form contiguous range, there is no need to require
   anything about the default case, it can be abort, or arbitrary code
   that can or might not fall through into final_bb, or it can e.g. be
   empty bb and just the values from default bb might not be appropriate
   constants; we emit an if (val is in range) vals = CSWTCH[...]; else
   anyway and the else can be anything; we still have to require standard
   default case if the range is non-contiguous, because then the default
   is used also for some values in the tables.

Bootstrapped/regtested on x86_64-linux and i686-linux.  It causes a single
regression, vrp40.c, which looks like this:
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; }
}
and expects to be optimized into return 3 by vrp1.  As switchconv is earlier
than that, vrp1 sees:
  _1 = a_3(D) & 1;
  _4 = (unsigned int) _1;
  _5 = CSWTCH.1[_4];
  return _5;
and doesn't optimize it.  If the testcase had say case 7: replaced with
default:, it wouldn't pass already before.  If the patch is ok, what should
we do with vrp40.c?  Change it in some way (e.g. return variable in one
case) so that switchconv doesn't trigger, or add an optimization in vrp
if we see a load from constant array with known initializer and the range
is small enough and contains the same value for all those values, replace
it with the value?  It would help also with say:
const int a[] = { 7, 8, 9, 1, 1, 1, 1, 2, 3, 4, 5, 6 };
int foo (int x)
{
  if (x <= 2 || x >= 7) return 3;
  return a[x];
}
turn it into
int foo (int x)
{
  if (x <= 2 || x >= 7) return 3;
  return 1;
}

2017-02-14  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.

	* 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.


	Jakub

On February 14, 2017 9:04:45 PM GMT+01:00, Jakub Jelinek <jakub@redhat.com> wrote:
>Hi!
>
>The following patch is an attempt to fix a regression where we no
>longer
>switch convert one switch because earlier optimizations turn it into
>unsupported shape.

Is that because of early threading?

>The patch contains two important changes (that can perhaps be split off
>separately):
>1) handle virtual PHIs; while because we require all the switch bbs
> to be empty, all the edges from the switch to final_bb should have the
>   same virtual op SSA_NAME, if the final_bb is reachable through other
>  edges from other code, it might have virtual PHI and switchconv would
>   unnecessarily give up
>2) if the switch cases form contiguous range, there is no need to
>require
>   anything about the default case, it can be abort, or arbitrary code
>   that can or might not fall through into final_bb, or it can e.g. be
>  empty bb and just the values from default bb might not be appropriate
>   constants; we emit an if (val is in range) vals = CSWTCH[...]; else
> anyway and the else can be anything; we still have to require standard
>  default case if the range is non-contiguous, because then the default
>   is used also for some values in the tables.
>
>Bootstrapped/regtested on x86_64-linux and i686-linux.  It causes a
>single
>regression, vrp40.c, which looks like this:
>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; }
>}
>and expects to be optimized into return 3 by vrp1.  As switchconv is
>earlier
>than that, vrp1 sees:
>  _1 = a_3(D) & 1;
>  _4 = (unsigned int) _1;
>  _5 = CSWTCH.1[_4];
>  return _5;
>and doesn't optimize it.  If the testcase had say case 7: replaced with
>default:, it wouldn't pass already before.

That looks odd...

  If the patch is ok, what
>should
>we do with vrp40.c?  Change it in some way (e.g. return variable in one
>case) so that switchconv doesn't trigger, or add an optimization in vrp
>if we see a load from constant array with known initializer and the
>range
>is small enough and contains the same value for all those values,
>replace
>it with the value? 

Possibly, but for GCC 8.

can we teach EVRP about this?  It runs before switch conversion.

Richard.


 It would help also with say:
>const int a[] = { 7, 8, 9, 1, 1, 1, 1, 2, 3, 4, 5, 6 };
>int foo (int x)
>{
>  if (x <= 2 || x >= 7) return 3;
>  return a[x];
>}
>turn it into
>int foo (int x)
>{
>  if (x <= 2 || x >= 7) return 3;
>  return 1;
>}
>
>2017-02-14  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.
>
>	* 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.
>
>--- gcc/tree-switch-conversion.c.jj	2017-02-14 14:54:08.020975500 +0100
>+++ gcc/tree-switch-conversion.c	2017-02-14 17:09:01.162826954 +0100
>@@ -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
>   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
>      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
>     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
> 	    && 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 *in
> 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 swi
> 
>       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 swi
>    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
>       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
> 	  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_inf
> }
> 
> /* 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
>   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
>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, stru
> {
>   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, stru
>       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, stru
> 	      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, stru
> 	   !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, stru
> 	      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++;
>@@ -1118,8 +1204,12 @@ build_arrays (gswitch *swtch, struct swi
>   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
>@@ -1148,7 +1238,7 @@ gen_def_assigns (gimple_stmt_iterator *g
>    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;
>@@ -1158,7 +1248,7 @@ prune_bbs (basic_block bbd, basic_block
>       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);
>@@ -1177,11 +1267,20 @@ fix_phi_nodes (edge e1f, edge e2f, basic
>   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);
>     }
> }
> 
>@@ -1218,10 +1317,10 @@ gen_inbound_check (gswitch *swtch, struc
> 
>   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);
>@@ -1241,9 +1340,12 @@ gen_inbound_check (gswitch *swtch, struc
>   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);
>@@ -1258,16 +1360,40 @@ gen_inbound_check (gswitch *swtch, struc
>   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;
> 
>@@ -1283,17 +1409,24 @@ gen_inbound_check (gswitch *swtch, struc
>   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);
>@@ -1304,15 +1437,17 @@ gen_inbound_check (gswitch *swtch, struc
>       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);
>@@ -1387,7 +1522,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;
>@@ -1397,7 +1532,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.   */
>--- gcc/testsuite/gcc.dg/tree-ssa/cswtch-3.c.jj	2017-02-14
>15:46:55.002417399 +0100
>+++ gcc/testsuite/gcc.dg/tree-ssa/cswtch-3.c	2017-02-14
>15:46:55.002417399 +0100
>@@ -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" } } */
>--- gcc/testsuite/gcc.dg/tree-ssa/cswtch-4.c.jj	2017-02-14
>15:46:55.003417386 +0100
>+++ gcc/testsuite/gcc.dg/tree-ssa/cswtch-4.c	2017-02-14
>15:46:55.003417386 +0100
>@@ -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" } } */
>--- gcc/testsuite/gcc.dg/tree-ssa/cswtch-5.c.jj	2017-02-14
>17:11:40.802710606 +0100
>+++ gcc/testsuite/gcc.dg/tree-ssa/cswtch-5.c	2017-02-14
>17:13:59.424872889 +0100
>@@ -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" } } */
>
>	Jakub

On Wed, Feb 15, 2017 at 08:06:16AM +0100, Richard Biener wrote:
> On February 14, 2017 9:04:45 PM GMT+01:00, Jakub Jelinek <jakub@redhat.com> wrote:
> >Hi!
> >
> >The following patch is an attempt to fix a regression where we no
> >longer
> >switch convert one switch because earlier optimizations turn it into
> >unsupported shape.
> 
> Is that because of early threading?

Yes.

> >and expects to be optimized into return 3 by vrp1.  As switchconv is
> >earlier
> >than that, vrp1 sees:
> >  _1 = a_3(D) & 1;
> >  _4 = (unsigned int) _1;
> >  _5 = CSWTCH.1[_4];
> >  return _5;
> >and doesn't optimize it.  If the testcase had say case 7: replaced with
> >default:, it wouldn't pass already before.
> 
> That looks odd...

Just a pass ordering issue.

>   If the patch is ok, what
> >should
> >we do with vrp40.c?  Change it in some way (e.g. return variable in one
> >case) so that switchconv doesn't trigger, or add an optimization in vrp
> >if we see a load from constant array with known initializer and the
> >range
> >is small enough and contains the same value for all those values,
> >replace
> >it with the value? 
> 
> Possibly, but for GCC 8.

To both this switchconv patch and the potential improvement for loading
from const arrays (can create an enhancement PR for that), or just the
latter?

> can we teach EVRP about this?  It runs before switch conversion.

I guess so.  It is a matter of calling simplify_switch_using_ranges
and then doing some cleanup (you wrote that optimization)
- to_update_switch_stmts handling.

	Jakub

On 15/02/17 08:17, Jakub Jelinek wrote:
> On Wed, Feb 15, 2017 at 08:06:16AM +0100, Richard Biener wrote:
>> On February 14, 2017 9:04:45 PM GMT+01:00, Jakub Jelinek <jakub@redhat.com> wrote:
>>> Hi!
>>>
>>> The following patch is an attempt to fix a regression where we no
>>> longer
>>> switch convert one switch because earlier optimizations turn it into
>>> unsupported shape.
>>
>> Is that because of early threading?
> 
> Yes.
> 
>>> and expects to be optimized into return 3 by vrp1.  As switchconv is
>>> earlier
>>> than that, vrp1 sees:
>>>  _1 = a_3(D) & 1;
>>>  _4 = (unsigned int) _1;
>>>  _5 = CSWTCH.1[_4];
>>>  return _5;
>>> and doesn't optimize it.  If the testcase had say case 7: replaced with
>>> default:, it wouldn't pass already before.
>>
>> That looks odd...
> 
> Just a pass ordering issue.
> 
>>   If the patch is ok, what
>>> should
>>> we do with vrp40.c?  Change it in some way (e.g. return variable in one
>>> case) so that switchconv doesn't trigger, or add an optimization in vrp
>>> if we see a load from constant array with known initializer and the
>>> range
>>> is small enough and contains the same value for all those values,
>>> replace
>>> it with the value? 
>>
>> Possibly, but for GCC 8.
> 
> To both this switchconv patch and the potential improvement for loading
> from const arrays (can create an enhancement PR for that), or just the
> latter?

Both I think - the patch is pretty big.  Maybe we can instead make early
threading not mess this up?

>> can we teach EVRP about this?  It runs before switch conversion.
> 
> I guess so.  It is a matter of calling simplify_switch_using_ranges
> and then doing some cleanup (you wrote that optimization)
> - to_update_switch_stmts handling.

Sounds like a good thing to do (for GCC 8 as well).

Thanks,
Richard.

> 
> 	Jakub
>

On Wed, Feb 15, 2017 at 12:46:44PM +0100, Richard Biener wrote:
> >> Possibly, but for GCC 8.
> > 
> > To both this switchconv patch and the potential improvement for loading
> > from const arrays (can create an enhancement PR for that), or just the
> > latter?
> 
> Both I think - the patch is pretty big.

Ok, I'll queue the patch for GCC8 then.

>  Maybe we can instead make early
> threading not mess this up?

Maybe, but not planning to do that myself, my knowledge about jump threading
is too limited.

> >> can we teach EVRP about this?  It runs before switch conversion.
> > 
> > I guess so.  It is a matter of calling simplify_switch_using_ranges
> > and then doing some cleanup (you wrote that optimization)
> > - to_update_switch_stmts handling.
> 
> Sounds like a good thing to do (for GCC 8 as well).

Ok, will file enhancement PRs.

	Jakub

On 02/15/2017 04:51 AM, Jakub Jelinek wrote:
> On Wed, Feb 15, 2017 at 12:46:44PM +0100, Richard Biener wrote:
>>>> Possibly, but for GCC 8.
>>>
>>> To both this switchconv patch and the potential improvement for loading
>>> from const arrays (can create an enhancement PR for that), or just the
>>> latter?
>>
>> Both I think - the patch is pretty big.
>
> Ok, I'll queue the patch for GCC8 then.
>
>>  Maybe we can instead make early
>> threading not mess this up?
>
> Maybe, but not planning to do that myself, my knowledge about jump threading
> is too limited.
The problem is at the point where we thread all we see is this:

   # s_1 = PHI <"foo"(2), "bar"(3), "spam"(4), 0B(5)>
<L7>:
   if (s_1 == 0B)
     goto <bb 7>;
   else
     goto <bb 8>;

Nothing more is needed for jump threading to do its job.  This doesn't 
look any different to the threader than any other simple jump threading 
opportunity.

I guess we could look to see if the PHI is the join point for a switch, 
but that seems rather hacky.

jeff