Claw back some of the code size regression in 548.exchange2_r

[Richard Sandiford <richard.sandiford@arm.com>]

This patch tries harder to detect cases in which the inner dimension
of an array access is invariant, such as:

     x(i, :) = 100

It fixes some of the code size regression in 548.exchange2_r, with
size improving by 5% compared to before the patch.  Of the two other
SPEC 2017 tests affected by loop versioning, 554.roms_r improved by a
trivial amount (0.3%) and 549.fotonik3d_r didn't change.  All three
results are with -Ofast -flto.

Tested on aarch64-linux-gnu, aarch64_be-elf and x86_64-linux-gnu.
OK to install?

Richard


2019-01-18  Richard Sandiford  <richard.sandiford@arm.com>

gcc/
	* gimple-loop-versioning.cc (loop_versioning::dump_inner_likelihood):
	New function, split out from...
	(loop_versioning::analyze_stride): ...here.
	(loop_versioning::find_per_loop_multiplication): Use gassign.
	(loop_versioning::analyze_term_using_scevs): Return a success code.
	(loop_versioning::analyze_arbitrary_term): New function.
	(loop_versioning::analyze_address_fragment): Use
	analyze_arbitrary_term if all else fails.

gcc/testsuite/
	* gfortran.dg/loop_versioning_1.f90: Bump the number of identified
	inner strides.
	* gfortran.dg/loop_versioning_9.f90: New test.
	* gfortran.dg/loop_versioning_10.f90: Likewise.

Index: gcc/gimple-loop-versioning.cc
===================================================================
--- gcc/gimple-loop-versioning.cc	2019-01-04 11:39:25.918257505 +0000
+++ gcc/gimple-loop-versioning.cc	2019-01-18 16:36:13.172064883 +0000
@@ -294,10 +294,12 @@ private:
   bool acceptable_type_p (tree, unsigned HOST_WIDE_INT *);
   bool multiply_term_by (address_term_info &, tree);
   inner_likelihood get_inner_likelihood (tree, unsigned HOST_WIDE_INT);
+  void dump_inner_likelihood (address_info &, address_term_info &);
   void analyze_stride (address_info &, address_term_info &,
 		       tree, struct loop *);
   bool find_per_loop_multiplication (address_info &, address_term_info &);
-  void analyze_term_using_scevs (address_info &, address_term_info &);
+  bool analyze_term_using_scevs (address_info &, address_term_info &);
+  void analyze_arbitrary_term (address_info &, address_term_info &);
   void analyze_address_fragment (address_info &);
   void record_address_fragment (gimple *, unsigned HOST_WIDE_INT,
 				tree, unsigned HOST_WIDE_INT, HOST_WIDE_INT);
@@ -803,6 +805,24 @@ loop_versioning::get_inner_likelihood (t
   return unlikely_p ? INNER_UNLIKELY : INNER_DONT_KNOW;
 }
 
+/* Dump the likelihood that TERM's stride is for the innermost dimension.
+   ADDRESS is the address that contains TERM.  */
+
+void
+loop_versioning::dump_inner_likelihood (address_info &address,
+					address_term_info &term)
+{
+  if (term.inner_likelihood == INNER_LIKELY)
+    dump_printf_loc (MSG_NOTE, address.stmt, "%T is likely to be the"
+		     " innermost dimension\n", term.stride);
+  else if (term.inner_likelihood == INNER_UNLIKELY)
+    dump_printf_loc (MSG_NOTE, address.stmt, "%T is probably not the"
+		     " innermost dimension\n", term.stride);
+  else
+    dump_printf_loc (MSG_NOTE, address.stmt, "cannot tell whether %T"
+		     " is the innermost dimension\n", term.stride);
+}
+
 /* The caller has identified that STRIDE is the stride of interest
    in TERM, and that the stride is applied in OP_LOOP.  Record this
    information in TERM, deciding whether STRIDE is likely to be for
@@ -818,17 +838,7 @@ loop_versioning::analyze_stride (address
 
   term.inner_likelihood = get_inner_likelihood (stride, term.multiplier);
   if (dump_enabled_p ())
-    {
-      if (term.inner_likelihood == INNER_LIKELY)
-	dump_printf_loc (MSG_NOTE, address.stmt, "%T is likely to be the"
-			 " innermost dimension\n", stride);
-      else if (term.inner_likelihood == INNER_UNLIKELY)
-	dump_printf_loc (MSG_NOTE, address.stmt, "%T is probably not the"
-			 " innermost dimension\n", stride);
-      else
-	dump_printf_loc (MSG_NOTE, address.stmt, "cannot tell whether %T"
-			 " is the innermost dimension\n", stride);
-    }
+    dump_inner_likelihood (address, term);
 
   /* To be a versioning opportunity we require:
 
@@ -879,7 +889,7 @@ bool
 loop_versioning::find_per_loop_multiplication (address_info &address,
 					       address_term_info &term)
 {
-  gimple *mult = maybe_get_assign (term.expr);
+  gassign *mult = maybe_get_assign (term.expr);
   if (!mult || gimple_assign_rhs_code (mult) != MULT_EXPR)
     return false;
 
@@ -909,7 +919,7 @@ loop_versioning::find_per_loop_multiplic
 }
 
 /* Try to use scalar evolutions to find an address stride for TERM,
-   which belongs to ADDRESS.
+   which belongs to ADDRESS.  Return true and update TERM if so.
 
    Here we are interested in any evolution information we can find,
    not just evolutions wrt ADDRESS->LOOP.  For example, if we find that
@@ -917,17 +927,17 @@ loop_versioning::find_per_loop_multiplic
    that information can help us eliminate worthless versioning opportunities
    in inner loops.  */
 
-void
+bool
 loop_versioning::analyze_term_using_scevs (address_info &address,
 					   address_term_info &term)
 {
   gimple *setter = maybe_get_stmt (term.expr);
   if (!setter)
-    return;
+    return false;
 
   struct loop *wrt_loop = loop_containing_stmt (setter);
   if (!loop_outer (wrt_loop))
-    return;
+    return false;
 
   tree chrec = strip_casts (analyze_scalar_evolution (wrt_loop, term.expr));
   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
@@ -955,7 +965,53 @@ loop_versioning::analyze_term_using_scev
 	}
 
       analyze_stride (address, term, stride, get_chrec_loop (chrec));
+      return true;
+    }
+
+  return false;
+}
+
+/* Address term TERM is an arbitrary term that provides no versioning
+   opportunities.  Analyze it to see whether it contains any likely
+   inner strides, so that we don't mistakenly version for other
+   (less likely) candidates.
+
+   This copes with invariant innermost indices such as:
+
+     x(i, :) = 100
+
+   where the "i" component of the address is invariant in the loop
+   but provides the real inner stride.
+
+   ADDRESS is the address that contains TERM.  */
+
+void
+loop_versioning::analyze_arbitrary_term (address_info &address,
+					 address_term_info &term)
+
+{
+  /* A multiplication offers two potential strides.  Pick the one that
+     is most likely to be an innermost stride.  */
+  tree expr = term.expr, alt = NULL_TREE;
+  gassign *mult = maybe_get_assign (expr);
+  if (mult && gimple_assign_rhs_code (mult) == MULT_EXPR)
+    {
+      expr = strip_casts (gimple_assign_rhs1 (mult));
+      alt = strip_casts (gimple_assign_rhs2 (mult));
+    }
+  term.stride = expr;
+  term.inner_likelihood = get_inner_likelihood (expr, term.multiplier);
+  if (alt)
+    {
+      inner_likelihood alt_l = get_inner_likelihood (alt, term.multiplier);
+      if (alt_l > term.inner_likelihood)
+	{
+	  term.stride = alt;
+	  term.inner_likelihood = alt_l;
+	}
     }
+  if (dump_enabled_p ())
+    dump_inner_likelihood (address, term);
 }
 
 /* Try to identify loop strides in ADDRESS and try to choose realistic
@@ -1038,8 +1094,10 @@ loop_versioning::analyze_address_fragmen
      find_per_loop_multiplication and analyze_term_using_scevs can handle,
      but the former is much cheaper than SCEV analysis, so try it first.  */
   for (unsigned int i = 0; i < address.terms.length (); ++i)
-    if (!find_per_loop_multiplication (address, address.terms[i]))
-      analyze_term_using_scevs (address, address.terms[i]);
+    if (!find_per_loop_multiplication (address, address.terms[i])
+	&& !analyze_term_using_scevs (address, address.terms[i])
+	&& !POINTER_TYPE_P (TREE_TYPE (address.terms[i].expr)))
+      analyze_arbitrary_term (address, address.terms[i]);
 
   /* Check for strides that are likely to be for the innermost dimension.
 
Index: gcc/testsuite/gfortran.dg/loop_versioning_1.f90
===================================================================
--- gcc/testsuite/gfortran.dg/loop_versioning_1.f90	2018-12-17 10:05:18.091771024 +0000
+++ gcc/testsuite/gfortran.dg/loop_versioning_1.f90	2019-01-18 16:36:13.172064883 +0000
@@ -23,6 +23,6 @@ subroutine f3(x, limit, step)
   end do
 end subroutine f3
 
-! { dg-final { scan-tree-dump-times {likely to be the innermost dimension} 1 "lversion" } }
+! { dg-final { scan-tree-dump-times {likely to be the innermost dimension} 2 "lversion" } }
 ! { dg-final { scan-tree-dump-times {want to version containing loop} 3 "lversion" } }
 ! { dg-final { scan-tree-dump-times {versioned this loop} 3 "lversion" } }
Index: gcc/testsuite/gfortran.dg/loop_versioning_9.f90
===================================================================
--- /dev/null	2018-12-31 11:20:29.178325188 +0000
+++ gcc/testsuite/gfortran.dg/loop_versioning_9.f90	2019-01-18 16:36:13.172064883 +0000
@@ -0,0 +1,31 @@
+! { dg-options "-O3 -fdump-tree-lversion-details" }
+
+subroutine f1(x)
+  real :: x(:, :)
+  x(1, :) = 100
+end subroutine f1
+
+subroutine f2(x, i)
+  real :: x(:, :)
+  integer :: i
+  x(i, :) = 100
+end subroutine f2
+
+subroutine f3(x)
+  real :: x(:, :)
+  do j = lbound(x, 2), ubound(x, 2)
+     x(1, j) = 100
+  end do
+end subroutine f3
+
+subroutine f4(x, i)
+  real :: x(:, :)
+  integer :: i
+  do j = lbound(x, 2), ubound(x, 2)
+     x(i, j) = 100
+  end do
+end subroutine f4
+
+! { dg-final { scan-tree-dump-times {likely to be the innermost dimension} 4 "lversion" } }
+! { dg-final { scan-tree-dump-not {want to version} "lversion" } }
+! { dg-final { scan-tree-dump-not {versioned} "lversion" } }
Index: gcc/testsuite/gfortran.dg/loop_versioning_10.f90
===================================================================
--- /dev/null	2018-12-31 11:20:29.178325188 +0000
+++ gcc/testsuite/gfortran.dg/loop_versioning_10.f90	2019-01-18 16:36:13.172064883 +0000
@@ -0,0 +1,31 @@
+! { dg-options "-O3 -fdump-tree-lversion-details" }
+
+subroutine f1(x)
+  real :: x(:, :)
+  x(:, 1) = 100
+end subroutine f1
+
+subroutine f2(x, i)
+  real :: x(:, :)
+  integer :: i
+  x(:, i) = 100
+end subroutine f2
+
+subroutine f3(x)
+  real :: x(:, :)
+  do j = lbound(x, 1), ubound(x, 1)
+     x(j, 1) = 100
+  end do
+end subroutine f3
+
+subroutine f4(x, i)
+  real :: x(:, :)
+  integer :: i
+  do j = lbound(x, 1), ubound(x, 1)
+     x(j, i) = 100
+  end do
+end subroutine f4
+
+! { dg-final { scan-tree-dump-times {likely to be the innermost dimension} 6 "lversion" } }
+! { dg-final { scan-tree-dump-times {want to version} 4 "lversion" } }
+! { dg-final { scan-tree-dump-times {versioned} 4 "lversion" } }