[PATCH] Fix PR87473 (SLSR ICE on hidden basis)

[Bill Schmidt <wschmidt at linux dot ibm dot com>]

Hi,

This patch addresses SLSR bug PR87473.  The underlying problem here is that
create_add_on_incoming_edge contains code to handle a phi_arg that is equal
to the base expression of the PHI candidate, where the increment assigned to
the incoming arc should be zero minus the index expression of the hidden
basis; but several other places in SLSR processing need to handle the same
case, and fail to do so.  As a result, the code to replace the PHI basis
attempts to use an initializing statement that was never created in the first
place, and we ICE.  This patch adds the necessary logic in four parts of the
code to ensure we handle this consistently throughout.

This error survived this long because the typical case when accessing the
hidden basis is for the index of the hidden basis to be zero.  For such a
case we don't need an initializing statement, and the ICE doesn't trigger.
The test case provided with the PR is a counter-example where the hidden
basis has an index of 2.

For the four functions fixed here, each identified the case of interest,
but just didn't do anything when that case arose.  I've reorganized the
code in each case to always execute the relevant logic, but change what's
done for the specific situation of the "pass-through" PHI argument.  This
makes the diffs a little hard to read, unfortunately.

During the investigation I noticed that we are dealing with a degenerate PHI,
introduced by the loopinit pass, that we would be better off optimizing away
sooner:

 <bb 5> [local count: 14598063]:
  # qz_1 = PHI <qz_3(4)>
  # jl_22 = PHI <jl_6(4)>
  _8 = (unsigned int) jl_22;
  _13 = _8 * _15;
  qz_11 = (int) _13;

The assignment to _8 should just use jl_6 in place of jl_22.  This would
greatly simplify SLSR's job, since PHI-free code is handled much more
straightforwardly than code that involves conditional updates.  We go through
at least 30 passes without having this cleaned up, and I expect other passes
than SLSR would perhaps be hamstrung by this as well.  Any recommendations?

Bootstrapped and tested on powerpc64le-linux-gnu with no regressions.  I've
added the test case from the bugzilla to the torture tests.  Is this okay for
trunk, and after a suitable period, to GCC 7 and 8 also?

Thanks!
Bill


[gcc]

2018-10-12  Bill Schmidt  <wschmidt@linux.ibm.com>

	PR tree-optimization/87473
	* gimple-ssa-strength-reduction.c (record_phi_increments_1): For
	phi arguments identical to the base expression of the phi
	candidate, record a phi-adjust increment of zero minus the index
	expression of the hidden basis.
	(phi_incr_cost_1): For phi arguments identical to the base
	expression of the phi candidate, the difference to compare against
	the increment is zero minus the index expression of the hidden
	basis, and there is no potential savings from replacing the (phi)
	statement.
	(ncd_with_phi): For phi arguments identical to the base expression
	of the phi candidate, the difference to compare against the
	increment is zero minus the index expression of the hidden basis.
	(all_phi_incrs_profitable_1): For phi arguments identical to the
	base expression of the phi candidate, the increment to be checked
	for profitability is zero minus the index expression of the hidden
	basis.

[gcc/testsuite]

2018-10-12  Bill Schmidt  <wschmidt@linux.ibm.com>

	PR tree-optimization/87473
	* gcc.c-torture/compile/pr87473.c: New file.


Index: gcc/gimple-ssa-strength-reduction.c
===================================================================
--- gcc/gimple-ssa-strength-reduction.c	(revision 265112)
+++ gcc/gimple-ssa-strength-reduction.c	(working copy)
@@ -2779,17 +2779,23 @@ record_phi_increments_1 (slsr_cand_t basis, gimple
   for (i = 0; i < gimple_phi_num_args (phi); i++)
     {
       tree arg = gimple_phi_arg_def (phi, i);
+      gimple *arg_def = SSA_NAME_DEF_STMT (arg);
 
-      if (!operand_equal_p (arg, phi_cand->base_expr, 0))
+      if (gimple_code (arg_def) == GIMPLE_PHI)
+	record_phi_increments_1 (basis, arg_def);
+      else
 	{
-	  gimple *arg_def = SSA_NAME_DEF_STMT (arg);
+	  widest_int diff;
 
-	  if (gimple_code (arg_def) == GIMPLE_PHI)
-	    record_phi_increments_1 (basis, arg_def);
+	  if (operand_equal_p (arg, phi_cand->base_expr, 0))
+	    {
+	      diff = -basis->index;
+	      record_increment (phi_cand, diff, PHI_ADJUST);
+	    }
 	  else
 	    {
 	      slsr_cand_t arg_cand = base_cand_from_table (arg);
-	      widest_int diff = arg_cand->index - basis->index;
+	      diff = arg_cand->index - basis->index;
 	      record_increment (arg_cand, diff, PHI_ADJUST);
 	    }
 	}
@@ -2864,29 +2870,43 @@ phi_incr_cost_1 (slsr_cand_t c, const widest_int &
   for (i = 0; i < gimple_phi_num_args (phi); i++)
     {
       tree arg = gimple_phi_arg_def (phi, i);
+      gimple *arg_def = SSA_NAME_DEF_STMT (arg);
 
-      if (!operand_equal_p (arg, phi_cand->base_expr, 0))
+      if (gimple_code (arg_def) == GIMPLE_PHI)
 	{
-	  gimple *arg_def = SSA_NAME_DEF_STMT (arg);
-      
-	  if (gimple_code (arg_def) == GIMPLE_PHI)
+	  int feeding_savings = 0;
+	  tree feeding_var = gimple_phi_result (arg_def);
+	  cost += phi_incr_cost_1 (c, incr, arg_def, &feeding_savings);
+	  if (uses_consumed_by_stmt (feeding_var, phi))
+	    *savings += feeding_savings;
+	}
+      else
+	{
+	  widest_int diff;
+	  slsr_cand_t arg_cand;
+
+	  /* When the PHI argument is just a pass-through to the base
+	     expression of the hidden basis, the difference is zero minus
+	     the index of the basis.  There is no potential savings by
+	     eliminating a statement in this case.  */
+	  if (operand_equal_p (arg, phi_cand->base_expr, 0))
 	    {
-	      int feeding_savings = 0;
-	      tree feeding_var = gimple_phi_result (arg_def);
-	      cost += phi_incr_cost_1 (c, incr, arg_def, &feeding_savings);
-	      if (uses_consumed_by_stmt (feeding_var, phi))
-		*savings += feeding_savings;
+	      arg_cand = (slsr_cand_t)NULL;
+	      diff = -basis->index;
 	    }
 	  else
 	    {
-	      slsr_cand_t arg_cand = base_cand_from_table (arg);
-	      widest_int diff = arg_cand->index - basis->index;
-
-	      if (incr == diff)
+	      arg_cand = base_cand_from_table (arg);
+	      diff = arg_cand->index - basis->index;
+	    }
+	  
+	  if (incr == diff)
+	    {
+	      tree basis_lhs = gimple_assign_lhs (basis->cand_stmt);
+	      cost += add_cost (true, TYPE_MODE (TREE_TYPE (basis_lhs)));
+	      if (arg_cand)
 		{
-		  tree basis_lhs = gimple_assign_lhs (basis->cand_stmt);
 		  tree lhs = gimple_assign_lhs (arg_cand->cand_stmt);
-		  cost += add_cost (true, TYPE_MODE (TREE_TYPE (basis_lhs)));
 		  if (uses_consumed_by_stmt (lhs, phi))
 		    *savings += stmt_cost (arg_cand->cand_stmt, true);
 		}
@@ -3228,23 +3248,26 @@ ncd_with_phi (slsr_cand_t c, const widest_int &inc
   for (i = 0; i < gimple_phi_num_args (phi); i++)
     {
       tree arg = gimple_phi_arg_def (phi, i);
+      gimple *arg_def = SSA_NAME_DEF_STMT (arg);
 
-      if (!operand_equal_p (arg, phi_cand->base_expr, 0))
+      if (gimple_code (arg_def) == GIMPLE_PHI)
+	ncd = ncd_with_phi (c, incr, as_a <gphi *> (arg_def), ncd, where);
+      else 
 	{
-	  gimple *arg_def = SSA_NAME_DEF_STMT (arg);
+	  widest_int diff;
 
-	  if (gimple_code (arg_def) == GIMPLE_PHI)
-	    ncd = ncd_with_phi (c, incr, as_a <gphi *> (arg_def), ncd,
-				where);
-	  else 
+	  if (operand_equal_p (arg, phi_cand->base_expr, 0))
+	    diff = -basis->index;
+	  else
 	    {
 	      slsr_cand_t arg_cand = base_cand_from_table (arg);
-	      widest_int diff = arg_cand->index - basis->index;
-	      basic_block pred = gimple_phi_arg_edge (phi, i)->src;
-
-	      if ((incr == diff) || (!address_arithmetic_p && incr == -diff))
-		ncd = ncd_for_two_cands (ncd, pred, *where, NULL, where);
+	      diff = arg_cand->index - basis->index;
 	    }
+	  
+	  basic_block pred = gimple_phi_arg_edge (phi, i)->src;
+	  
+	  if ((incr == diff) || (!address_arithmetic_p && incr == -diff))
+	    ncd = ncd_for_two_cands (ncd, pred, *where, NULL, where);
 	}
     }
 
@@ -3515,51 +3538,53 @@ all_phi_incrs_profitable_1 (slsr_cand_t c, gphi *p
 	return false;
 
       tree arg = gimple_phi_arg_def (phi, i);
+      gimple *arg_def = SSA_NAME_DEF_STMT (arg);
 
-      if (!operand_equal_p (arg, phi_cand->base_expr, 0))
+      if (gimple_code (arg_def) == GIMPLE_PHI)
 	{
-	  gimple *arg_def = SSA_NAME_DEF_STMT (arg);
+	  if (!all_phi_incrs_profitable_1 (c, as_a <gphi *> (arg_def), spread)
+	      || *spread > MAX_SPREAD)
+	    return false;
+	}
+      else
+	{
+	  int j;
+	  widest_int increment;
 
-	  if (gimple_code (arg_def) == GIMPLE_PHI)
-	    {
-	      if (!all_phi_incrs_profitable_1 (c, as_a <gphi *> (arg_def),
-					       spread)
-		  || *spread > MAX_SPREAD)
-		return false;
-	    }
+	  if (operand_equal_p (arg, phi_cand->base_expr, 0))
+	    increment = -basis->index;
 	  else
 	    {
-	      int j;
 	      slsr_cand_t arg_cand = base_cand_from_table (arg);
-	      widest_int increment = arg_cand->index - basis->index;
+	      increment = arg_cand->index - basis->index;
+	    }
 
-	      if (!address_arithmetic_p && wi::neg_p (increment))
-		increment = -increment;
+	  if (!address_arithmetic_p && wi::neg_p (increment))
+	    increment = -increment;
 
-	      j = incr_vec_index (increment);
+	  j = incr_vec_index (increment);
 
-	      if (dump_file && (dump_flags & TDF_DETAILS))
-		{
-		  fprintf (dump_file, "  Conditional candidate %d, phi: ",
-			   c->cand_num);
-		  print_gimple_stmt (dump_file, phi, 0);
-		  fputs ("    increment: ", dump_file);
-		  print_decs (increment, dump_file);
-		  if (j < 0)
-		    fprintf (dump_file,
-			     "\n  Not replaced; incr_vec overflow.\n");
-		  else {
-		    fprintf (dump_file, "\n    cost: %d\n", incr_vec[j].cost);
-		    if (profitable_increment_p (j))
-		      fputs ("  Replacing...\n", dump_file);
-		    else
-		      fputs ("  Not replaced.\n", dump_file);
-		  }
-		}
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "  Conditional candidate %d, phi: ",
+		       c->cand_num);
+	      print_gimple_stmt (dump_file, phi, 0);
+	      fputs ("    increment: ", dump_file);
+	      print_decs (increment, dump_file);
+	      if (j < 0)
+		fprintf (dump_file,
+			 "\n  Not replaced; incr_vec overflow.\n");
+	      else {
+		fprintf (dump_file, "\n    cost: %d\n", incr_vec[j].cost);
+		if (profitable_increment_p (j))
+		  fputs ("  Replacing...\n", dump_file);
+		else
+		  fputs ("  Not replaced.\n", dump_file);
+	      }
+	    }
 
-	      if (j < 0 || !profitable_increment_p (j))
-		return false;
-	    }
+	  if (j < 0 || !profitable_increment_p (j))
+	    return false;
 	}
     }
 
Index: gcc/testsuite/gcc.c-torture/compile/pr87473.c
===================================================================
--- gcc/testsuite/gcc.c-torture/compile/pr87473.c	(nonexistent)
+++ gcc/testsuite/gcc.c-torture/compile/pr87473.c	(working copy)
@@ -0,0 +1,19 @@
+/* PR87473: SLSR ICE on hidden basis with |increment| > 1.  */
+/* { dg-additional-options "-fno-tree-ch" } */
+
+void
+t6 (int qz, int wh)
+{
+  int jl = wh;
+
+  while (1.0 / 0 < 1)
+    {
+      qz = wh * (wh + 2);
+
+      while (wh < 1)
+        jl = 0;
+    }
+
+  while (qz < 1)
+    qz = jl * wh;
+}