Use SCEV information when aligning for vectorisation (PR 84005)

This PR is another regression caused by the removal of the simple_iv
check in dr_analyze_innermost for BB analysis.  Without splitting out
the step, we weren't able to find an underlying object whose alignment
could be increased.

As with PR81635, I think the simple_iv was only handling one special
case of something that ought to be more general.  The more general
thing here is that if the address can be analysed as a scalar
evolution, and if all updates preserve alignment N, it's possible
to align the address to N by increasing the alignment of the base
object to N.  That applies also to outer loops, and to both loop
and BB analysis.

I wasn't sure where the new functions ought to live, but tree-data-ref.c
seemed OK since (a) that already does scev analysis on addresses and
(b) you'd want to use dr_analyze_innermost first if you were analysing
a reference.

2018-03-24  Richard Sandiford  <richard.sandiford@linaro.org>

gcc/
	PR tree-optimization/84005
	* tree-data-ref.h (get_base_for_alignment): Declare.
	* tree-data-ref.c (get_base_for_alignment_1): New function.
	(get_base_for_alignment): Likewise.
	* tree-vect-data-refs.c (vect_compute_data_ref_alignment): Use
	get_base_for_alignment to find a suitable base object, instead
	of always using drb->base_address.

gcc/testsuite/
	PR tree-optimization/84005
	* gcc.dg/vect/bb-slp-1.c: Make sure there is no message about
	failing to force the alignment.

From-SVN: r258833

6 files changed, 98 insertions, 6 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 980768a..9526547 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,13 @@
+2018-03-24  Richard Sandiford  <richard.sandiford@linaro.org>
+
+	PR tree-optimization/84005
+	* tree-data-ref.h (get_base_for_alignment): Declare.
+	* tree-data-ref.c (get_base_for_alignment_1): New function.
+	(get_base_for_alignment): Likewise.
+	* tree-vect-data-refs.c (vect_compute_data_ref_alignment): Use
+	get_base_for_alignment to find a suitable base object, instead
+	of always using drb->base_address.
+
 2018-03-23  Jakub Jelinek  <jakub@redhat.com>
 
 	PR inline-asm/85022
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 0b57b5f..1ea5f0c 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,9 @@
+2018-03-24  Richard Sandiford  <richard.sandiford@linaro.org>
+
+	PR tree-optimization/84005
+	* gcc.dg/vect/bb-slp-1.c: Make sure there is no message about
+	failing to force the alignment.
+
 2018-03-23  Peter Bergner  <bergner@vnet.ibm.com>
 
 	* gcc.target/powerpc/builtins-1-le.c <vclzb>: Rename duplicate test
diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-1.c b/gcc/testsuite/gcc.dg/vect/bb-slp-1.c
index f64514e..e6818cb 100644
--- a/gcc/testsuite/gcc.dg/vect/bb-slp-1.c
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-1.c
@@ -54,5 +54,5 @@ int main (void)
   return 0;
 }
 
+/* { dg-final { scan-tree-dump-not "can't force alignment" "slp1" } } */
 /* { dg-final { scan-tree-dump-times "basic block vectorized" 1 "slp1" } } */
-  
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index af35e41..e2107fe 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -5202,6 +5202,81 @@ dr_alignment (innermost_loop_behavior *drb)
   return alignment;
 }
 
+/* If BASE is a pointer-typed SSA name, try to find the object that it
+   is based on.  Return this object X on success and store the alignment
+   in bytes of BASE - &X in *ALIGNMENT_OUT.  */
+
+static tree
+get_base_for_alignment_1 (tree base, unsigned int *alignment_out)
+{
+  if (TREE_CODE (base) != SSA_NAME || !POINTER_TYPE_P (TREE_TYPE (base)))
+    return NULL_TREE;
+
+  gimple *def = SSA_NAME_DEF_STMT (base);
+  base = analyze_scalar_evolution (loop_containing_stmt (def), base);
+
+  /* Peel chrecs and record the minimum alignment preserved by
+     all steps.  */
+  unsigned int alignment = MAX_OFILE_ALIGNMENT / BITS_PER_UNIT;
+  while (TREE_CODE (base) == POLYNOMIAL_CHREC)
+    {
+      unsigned int step_alignment = highest_pow2_factor (CHREC_RIGHT (base));
+      alignment = MIN (alignment, step_alignment);
+      base = CHREC_LEFT (base);
+    }
+
+  /* Punt if the expression is too complicated to handle.  */
+  if (tree_contains_chrecs (base, NULL) || !POINTER_TYPE_P (TREE_TYPE (base)))
+    return NULL_TREE;
+
+  /* The only useful cases are those for which a dereference folds to something
+     other than an INDIRECT_REF.  */
+  tree ref_type = TREE_TYPE (TREE_TYPE (base));
+  tree ref = fold_indirect_ref_1 (UNKNOWN_LOCATION, ref_type, base);
+  if (!ref)
+    return NULL_TREE;
+
+  /* Analyze the base to which the steps we peeled were applied.  */
+  poly_int64 bitsize, bitpos, bytepos;
+  machine_mode mode;
+  int unsignedp, reversep, volatilep;
+  tree offset;
+  base = get_inner_reference (ref, &bitsize, &bitpos, &offset, &mode,
+			      &unsignedp, &reversep, &volatilep);
+  if (!base || !multiple_p (bitpos, BITS_PER_UNIT, &bytepos))
+    return NULL_TREE;
+
+  /* Restrict the alignment to that guaranteed by the offsets.  */
+  unsigned int bytepos_alignment = known_alignment (bytepos);
+  if (bytepos_alignment != 0)
+    alignment = MIN (alignment, bytepos_alignment);
+  if (offset)
+    {
+      unsigned int offset_alignment = highest_pow2_factor (offset);
+      alignment = MIN (alignment, offset_alignment);
+    }
+
+  *alignment_out = alignment;
+  return base;
+}
+
+/* Return the object whose alignment would need to be changed in order
+   to increase the alignment of ADDR.  Store the maximum achievable
+   alignment in *MAX_ALIGNMENT.  */
+
+tree
+get_base_for_alignment (tree addr, unsigned int *max_alignment)
+{
+  tree base = get_base_for_alignment_1 (addr, max_alignment);
+  if (base)
+    return base;
+
+  if (TREE_CODE (addr) == ADDR_EXPR)
+    addr = TREE_OPERAND (addr, 0);
+  *max_alignment = MAX_OFILE_ALIGNMENT / BITS_PER_UNIT;
+  return addr;
+}
+
 /* Recursive helper function.  */
 
 static bool
diff --git a/gcc/tree-data-ref.h b/gcc/tree-data-ref.h
index 63094a7..8739853 100644
--- a/gcc/tree-data-ref.h
+++ b/gcc/tree-data-ref.h
@@ -463,6 +463,7 @@ extern bool compute_all_dependences (vec<data_reference_p> ,
 extern tree find_data_references_in_bb (struct loop *, basic_block,
                                         vec<data_reference_p> *);
 extern unsigned int dr_alignment (innermost_loop_behavior *);
+extern tree get_base_for_alignment (tree, unsigned int *);
 
 /* Return the alignment in bytes that DR is guaranteed to have at all
    times.  */
diff --git a/gcc/tree-vect-data-refs.c b/gcc/tree-vect-data-refs.c
index c009498..ce24387 100644
--- a/gcc/tree-vect-data-refs.c
+++ b/gcc/tree-vect-data-refs.c
@@ -957,11 +957,11 @@ vect_compute_data_ref_alignment (struct data_reference *dr)
 
   if (base_alignment < vector_alignment)
     {
-      tree base = drb->base_address;
-      if (TREE_CODE (base) == ADDR_EXPR)
-	base = TREE_OPERAND (base, 0);
-      if (!vect_can_force_dr_alignment_p (base,
-					  vector_alignment * BITS_PER_UNIT))
+      unsigned int max_alignment;
+      tree base = get_base_for_alignment (drb->base_address, &max_alignment);
+      if (max_alignment < vector_alignment
+	  || !vect_can_force_dr_alignment_p (base,
+					     vector_alignment * BITS_PER_UNIT))
 	{
 	  if (dump_enabled_p ())
 	    {