Fix PR81987 (SLSR dominance issue)

Hi,

https://gcc.gnu.org/PR81987 identifies an SSA verification error following
SLSR.  The problem arises when SLSR places an initialization expression at
a point not dominated by the definition of an SSA name it uses.  When there
are multiple conditional candidates for replacement, the initialization
expression must dominate all of these candidates and their phi dependencies,
but the nearest common dominator for these may actually be above the stride
definition in some cases.

In such cases a single initialization point is not possible.  With sufficient
analysis, it would be possible to find multiple initialization points that
would satisfy availability of the stride at the cost of larger code.  This
is too complex for a bug fix, though.  This patch instead refuses to replace
candidates where a single legal initialization point isn't possible.  We
ensure this by setting the cost for the increment associated with this
initialization to effectively infinite.

Bootstrapped and tested on powerpc64le-linux-gnu with no regressions.  Is
this okay for trunk, and backport to all supported releases after a period
of burn-in?

Thanks,
Bill


[gcc]

2017-08-30  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

	PR tree-optimization/81987
	* gimple-ssa-strength-reduction.c (insert_initializers): Don't
	insert an initializer in a location not dominated by the stride
	definition.

[gcc/testsuite]

2017-08-30  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

	PR tree-optimization/81987
	* g++.dg/torture/pr81987.C: New file.

On August 30, 2017 7:22:45 PM GMT+02:00, Bill Schmidt <wschmidt@linux.vnet.ibm.com> wrote:
>Hi,
>
>https://gcc.gnu.org/PR81987 identifies an SSA verification error
>following
>SLSR.  The problem arises when SLSR places an initialization expression
>at
>a point not dominated by the definition of an SSA name it uses.  When
>there
>are multiple conditional candidates for replacement, the initialization
>expression must dominate all of these candidates and their phi
>dependencies,
>but the nearest common dominator for these may actually be above the
>stride
>definition in some cases.
>
>In such cases a single initialization point is not possible.  With
>sufficient
>analysis, it would be possible to find multiple initialization points
>that
>would satisfy availability of the stride at the cost of larger code. 
>This
>is too complex for a bug fix, though.  This patch instead refuses to
>replace
>candidates where a single legal initialization point isn't possible. 
>We
>ensure this by setting the cost for the increment associated with this
>initialization to effectively infinite.
>
>Bootstrapped and tested on powerpc64le-linux-gnu with no regressions. 
>Is
>this okay for trunk, and backport to all supported releases after a
>period
>of burn-in?

Yes. 

Thanks, 
Richard. 

>Thanks,
>Bill
>
>
>[gcc]
>
>2017-08-30  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>
>
>	PR tree-optimization/81987
>	* gimple-ssa-strength-reduction.c (insert_initializers): Don't
>	insert an initializer in a location not dominated by the stride
>	definition.
>
>[gcc/testsuite]
>
>2017-08-30  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>
>
>	PR tree-optimization/81987
>	* g++.dg/torture/pr81987.C: New file.
>
>
>Index: gcc/gimple-ssa-strength-reduction.c
>===================================================================
>--- gcc/gimple-ssa-strength-reduction.c	(revision 251369)
>+++ gcc/gimple-ssa-strength-reduction.c	(working copy)
>@@ -3340,6 +3340,23 @@ insert_initializers (slsr_cand_t c)
> 	 that block, the earliest one will be returned in WHERE.  */
>       bb = nearest_common_dominator_for_cands (c, incr, &where);
> 
>+      /* If the NCD is not dominated by the block containing the
>+	 definition of the stride, we can't legally insert a
>+	 single initializer.  Mark the increment as unprofitable
>+	 so we don't make any replacements.  FIXME: Multiple
>+	 initializers could be placed with more analysis.  */
>+      gimple *stride_def = SSA_NAME_DEF_STMT (c->stride);
>+      basic_block stride_bb = gimple_bb (stride_def);
>+
>+      if (stride_bb && !dominated_by_p (CDI_DOMINATORS, bb,
>stride_bb))
>+	{
>+	  if (dump_file && (dump_flags & TDF_DETAILS))
>+	    fprintf (dump_file,
>+		     "Initializer #%d cannot be legally placed\n", i);
>+	  incr_vec[i].cost = COST_INFINITE;
>+	  continue;
>+	}
>+
>       /* If the nominal stride has a different type than the recorded
> 	 stride type, build a cast from the nominal stride to that type.  */
>       if (!types_compatible_p (TREE_TYPE (c->stride), c->stride_type))
>Index: gcc/testsuite/g++.dg/torture/pr81987.C
>===================================================================
>--- gcc/testsuite/g++.dg/torture/pr81987.C	(nonexistent)
>+++ gcc/testsuite/g++.dg/torture/pr81987.C	(working copy)
>@@ -0,0 +1,61 @@
>+extern short var_1;
>+extern const short var_3;
>+extern unsigned long int var_9;
>+extern short var_13;
>+extern const unsigned long int var_15;
>+extern const unsigned long int var_37;
>+extern unsigned long int var_40;
>+extern long long int var_47;
>+extern short var_48;
>+extern const short var_54;
>+extern long long int var_79;
>+extern long long int var_81;
>+extern long long int var_94;
>+extern long long int var_95;
>+extern long long int var_701;
>+extern unsigned long int var_786;
>+extern short var_788;
>+extern long long int var_844;
>+
>+struct struct_1 {
>+  short member_1_2 : 15;
>+  static long long int member_1_3;
>+};
>+
>+extern struct_1 struct_obj_6;
>+extern struct_1 struct_obj_8;
>+
>+void foo() {
>+  int a = var_3 <= 602154393864UL;
>+  if (var_81 ? 0 : var_3 && var_9)
>+    ;
>+  else {
>+    var_94 = 0;
>+    if (var_3 && var_48 || var_13) {
>+      if (var_48)
>+	var_95 = 0;
>+      short b((2364461588881776511UL + var_3) * (2 ? var_13 : 0) ||
>var_1);
>+      struct_obj_8.member_1_2 = b;
>+      if (var_15) {
>+	if (var_81)
>+	  if (var_47)
>+	    ;
>+	  else if (var_40)
>+	    var_701 = 0;
>+      } else {
>+	if (var_40)
>+	  var_79 = 0;
>+	if (var_54) {
>+	  if (var_37)
>+	    var_786 = 0;
>+	  else
>+	    var_788 = 0;
>+	            struct_obj_6.member_1_3 =
>+		      (2364461588881776511UL + var_3) * (2 ? var_13 : 0);
>+	}
>+      }
>+      if ((2364461588881776511UL + var_3) * (2 ? var_13 : 0))
>+	var_844 = 0;
>+    }
>+  }
>+}