[7/7] Pool alignment information for common bases

Message ID 87eftyx8mq.fsf@linaro.org
State New
Headers show
Series
  • Untitled series #2694
Related show

Commit Message

Richard Sandiford July 3, 2017, 7:49 a.m.
This patch is a follow-on to the fix for PR81136.  The testcase for that
PR shows that we can (correctly) calculate different base alignments
for two data_references but still tell that their misalignments wrt the
vector size are equal.  This is because we calculate the base alignments
for each dr individually, without looking at the other drs, and in
general the alignment we calculate is only guaranteed if the dr's DR_REF
actually occurs.

This is working as designed, but it does expose a missed opportunity.
We know that if a vectorised loop is reached, all statements in that
loop execute at least once, so it should be safe to pool the alignment
information for all the statements we're vectorising.  The only catch is
that DR_REFs for masked loads and stores only occur if the mask value is
nonzero.  For example, in:

  struct s __attribute__((aligned(32))) {
    int misaligner;
    int array[N];
  };

  int *ptr;
  for (int i = 0; i < n; ++i)
    ptr[i] = c[i] ? ((struct s *) (ptr - 1))->array[i] : 0;

we can only guarantee that ptr points to a "struct s" if at least
one c[i] is true.

This patch adds a DR_IS_CONDITIONAL_IN_STMT flag to record whether
the DR_REF is guaranteed to occur every time that the statement
executes to completion.  It then pools the alignment information
for references that aren't conditional in this sense.

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

Richard


2017-07-03  Richard Sandiford  <richard.sandiford@linaro.org>

gcc/
	* tree-vectorizer.h: Include tree-hash-traits.h.
	(vec_base_alignments): New typedef.
	(vec_info): Add a base_alignments field.
	(vect_record_base_alignments: Declare.
	* tree-data-ref.h (data_reference): Add an is_conditional_in_stmt
	field.
	(DR_IS_CONDITIONAL_IN_STMT): New macro.
	(create_data_ref): Add an is_conditional_in_stmt argument.
	* tree-data-ref.c (create_data_ref): Likewise.  Use it to initialize
	the is_conditional_in_stmt field.
	(data_ref_loc): Add an is_conditional_in_stmt field.
	(get_references_in_stmt): Set the is_conditional_in_stmt field.
	(find_data_references_in_stmt): Update call to create_data_ref.
	(graphite_find_data_references_in_stmt): Likewise.
	* tree-ssa-loop-prefetch.c (determine_loop_nest_reuse): Likewise.
	* tree-vect-data-refs.c (vect_analyze_data_refs): Likewise.
	(vect_record_base_alignment): New function.
	(vect_record_base_alignments): Likewise.
	(vect_compute_data_ref_alignment): Adjust base_addr and aligned_to
	for nested statements even if we fail to compute a misalignment.
	Use pooled base alignments for unconditional references.
	(vect_find_same_alignment_drs): Compare base addresses instead
	of base objects.
	(vect_compute_data_ref_alignment): Call vect_record_base_alignments.
	* tree-vect-slp.c (vect_slp_analyze_bb_1): Likewise.
	(new_bb_vec_info): Initialize base_alignments.
	* tree-vect-loop.c (new_loop_vec_info): Likewise.
	* tree-vectorizer.c (vect_destroy_datarefs): Release base_alignments.

gcc/testsuite/
	* gcc.dg/vect/pr81136.c: Add scan test.

Comments

Richard Biener July 4, 2017, 11:29 a.m. | #1
On Mon, Jul 3, 2017 at 9:49 AM, Richard Sandiford
<richard.sandiford@linaro.org> wrote:
> This patch is a follow-on to the fix for PR81136.  The testcase for that

> PR shows that we can (correctly) calculate different base alignments

> for two data_references but still tell that their misalignments wrt the

> vector size are equal.  This is because we calculate the base alignments

> for each dr individually, without looking at the other drs, and in

> general the alignment we calculate is only guaranteed if the dr's DR_REF

> actually occurs.

>

> This is working as designed, but it does expose a missed opportunity.

> We know that if a vectorised loop is reached, all statements in that

> loop execute at least once, so it should be safe to pool the alignment

> information for all the statements we're vectorising.  The only catch is

> that DR_REFs for masked loads and stores only occur if the mask value is

> nonzero.  For example, in:

>

>   struct s __attribute__((aligned(32))) {

>     int misaligner;

>     int array[N];

>   };

>

>   int *ptr;

>   for (int i = 0; i < n; ++i)

>     ptr[i] = c[i] ? ((struct s *) (ptr - 1))->array[i] : 0;

>

> we can only guarantee that ptr points to a "struct s" if at least

> one c[i] is true.

>

> This patch adds a DR_IS_CONDITIONAL_IN_STMT flag to record whether

> the DR_REF is guaranteed to occur every time that the statement

> executes to completion.  It then pools the alignment information

> for references that aren't conditional in this sense.

>

> Tested on aarch64-linux-gnu and x86_64-linux-gnu.  OK to install?

>

> Richard

>

>

> 2017-07-03  Richard Sandiford  <richard.sandiford@linaro.org>

>

> gcc/

>         * tree-vectorizer.h: Include tree-hash-traits.h.

>         (vec_base_alignments): New typedef.

>         (vec_info): Add a base_alignments field.

>         (vect_record_base_alignments: Declare.

>         * tree-data-ref.h (data_reference): Add an is_conditional_in_stmt

>         field.

>         (DR_IS_CONDITIONAL_IN_STMT): New macro.

>         (create_data_ref): Add an is_conditional_in_stmt argument.

>         * tree-data-ref.c (create_data_ref): Likewise.  Use it to initialize

>         the is_conditional_in_stmt field.

>         (data_ref_loc): Add an is_conditional_in_stmt field.

>         (get_references_in_stmt): Set the is_conditional_in_stmt field.

>         (find_data_references_in_stmt): Update call to create_data_ref.

>         (graphite_find_data_references_in_stmt): Likewise.

>         * tree-ssa-loop-prefetch.c (determine_loop_nest_reuse): Likewise.

>         * tree-vect-data-refs.c (vect_analyze_data_refs): Likewise.

>         (vect_record_base_alignment): New function.

>         (vect_record_base_alignments): Likewise.

>         (vect_compute_data_ref_alignment): Adjust base_addr and aligned_to

>         for nested statements even if we fail to compute a misalignment.

>         Use pooled base alignments for unconditional references.

>         (vect_find_same_alignment_drs): Compare base addresses instead

>         of base objects.

>         (vect_compute_data_ref_alignment): Call vect_record_base_alignments.

>         * tree-vect-slp.c (vect_slp_analyze_bb_1): Likewise.

>         (new_bb_vec_info): Initialize base_alignments.

>         * tree-vect-loop.c (new_loop_vec_info): Likewise.

>         * tree-vectorizer.c (vect_destroy_datarefs): Release base_alignments.

>

> gcc/testsuite/

>         * gcc.dg/vect/pr81136.c: Add scan test.

>

> Index: gcc/tree-vectorizer.h

> ===================================================================

> --- gcc/tree-vectorizer.h       2017-07-03 08:42:50.186422191 +0100

> +++ gcc/tree-vectorizer.h       2017-07-03 08:45:24.571165851 +0100

> @@ -22,6 +22,7 @@ Software Foundation; either version 3, o

>  #define GCC_TREE_VECTORIZER_H

>

>  #include "tree-data-ref.h"

> +#include "tree-hash-traits.h"

>  #include "target.h"

>

>  /* Used for naming of new temporaries.  */

> @@ -84,6 +85,11 @@ struct stmt_info_for_cost {

>

>  typedef vec<stmt_info_for_cost> stmt_vector_for_cost;

>

> +/* Maps base addresses to an innermost_loop_behavior that gives the maximum

> +   known alignment for that base.  */

> +typedef hash_map<tree_operand_hash,

> +                innermost_loop_behavior *> vec_base_alignments;

> +

>  /************************************************************************

>    SLP

>   ************************************************************************/

> @@ -156,6 +162,10 @@ struct vec_info {

>    /* All data references.  */

>    vec<data_reference_p> datarefs;

>

> +  /* Maps base addresses to an innermost_loop_behavior that gives the maximum

> +     known alignment for that base.  */

> +  vec_base_alignments base_alignments;

> +

>    /* All data dependences.  */

>    vec<ddr_p> ddrs;

>

> @@ -1132,6 +1142,7 @@ extern bool vect_prune_runtime_alias_tes

>  extern bool vect_check_gather_scatter (gimple *, loop_vec_info,

>                                        gather_scatter_info *);

>  extern bool vect_analyze_data_refs (vec_info *, int *);

> +extern void vect_record_base_alignments (vec_info *);

>  extern tree vect_create_data_ref_ptr (gimple *, tree, struct loop *, tree,

>                                       tree *, gimple_stmt_iterator *,

>                                       gimple **, bool, bool *,

> Index: gcc/tree-data-ref.h

> ===================================================================

> --- gcc/tree-data-ref.h 2017-07-03 08:42:50.185422235 +0100

> +++ gcc/tree-data-ref.h 2017-07-03 08:42:51.147380631 +0100

> @@ -159,6 +159,11 @@ struct data_reference

>    /* True when the data reference is in RHS of a stmt.  */

>    bool is_read;

>

> +  /* True when the data reference is conditional within STMT,

> +     i.e. if it might not occur even when the statement is executed

> +     and runs to completion.  */

> +  bool is_conditional_in_stmt;

> +

>    /* Behavior of the memory reference in the innermost loop.  */

>    struct innermost_loop_behavior innermost;

>

> @@ -178,6 +183,7 @@ #define DR_ACCESS_FN(DR, I)        DR_AC

>  #define DR_NUM_DIMENSIONS(DR)      DR_ACCESS_FNS (DR).length ()

>  #define DR_IS_READ(DR)             (DR)->is_read

>  #define DR_IS_WRITE(DR)            (!DR_IS_READ (DR))

> +#define DR_IS_CONDITIONAL_IN_STMT(DR) (DR)->is_conditional_in_stmt

>  #define DR_BASE_ADDRESS(DR)        (DR)->innermost.base_address

>  #define DR_OFFSET(DR)              (DR)->innermost.offset

>  #define DR_INIT(DR)                (DR)->innermost.init

> @@ -393,7 +399,8 @@ extern bool graphite_find_data_reference

>                                                    vec<data_reference_p> *);

>  tree find_data_references_in_loop (struct loop *, vec<data_reference_p> *);

>  bool loop_nest_has_data_refs (loop_p loop);

> -struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple *, bool);

> +struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple *, bool,

> +                                       bool);

>  extern bool find_loop_nest (struct loop *, vec<loop_p> *);

>  extern struct data_dependence_relation *initialize_data_dependence_relation

>       (struct data_reference *, struct data_reference *, vec<loop_p>);

> Index: gcc/tree-data-ref.c

> ===================================================================

> --- gcc/tree-data-ref.c 2017-07-03 08:42:50.184422278 +0100

> +++ gcc/tree-data-ref.c 2017-07-03 08:42:51.147380631 +0100

> @@ -1087,15 +1087,19 @@ free_data_ref (data_reference_p dr)

>    free (dr);

>  }

>

> -/* Analyzes memory reference MEMREF accessed in STMT.  The reference

> -   is read if IS_READ is true, write otherwise.  Returns the

> -   data_reference description of MEMREF.  NEST is the outermost loop

> -   in which the reference should be instantiated, LOOP is the loop in

> -   which the data reference should be analyzed.  */

> +/* Analyze memory reference MEMREF, which is accessed in STMT.

> +   The reference is a read if IS_READ is true, otherwise it is a write.

> +   IS_CONDITIONAL_IN_STMT indicates that the reference is conditional

> +   within STMT, i.e. that it might not occur even if STMT is executed

> +   and runs to completion.

> +

> +   Return the data_reference description of MEMREF.  NEST is the outermost

> +   loop in which the reference should be instantiated, LOOP is the loop

> +   in which the data reference should be analyzed.  */

>

>  struct data_reference *

>  create_data_ref (loop_p nest, loop_p loop, tree memref, gimple *stmt,

> -                bool is_read)

> +                bool is_read, bool is_conditional_in_stmt)

>  {

>    struct data_reference *dr;

>

> @@ -1110,6 +1114,7 @@ create_data_ref (loop_p nest, loop_p loo

>    DR_STMT (dr) = stmt;

>    DR_REF (dr) = memref;

>    DR_IS_READ (dr) = is_read;

> +  DR_IS_CONDITIONAL_IN_STMT (dr) = is_conditional_in_stmt;

>

>    dr_analyze_innermost (dr, nest != NULL ? loop : NULL);

>    dr_analyze_indices (dr, nest, loop);

> @@ -4484,6 +4489,11 @@ struct data_ref_loc

>

>    /* True if the memory reference is read.  */

>    bool is_read;

> +

> +  /* True if the data reference is conditional within the containing

> +     statement, i.e. if it might not occur even when the statement

> +     is executed and runs to completion.  */

> +  bool is_conditional_in_stmt;

>  };

>

>

> @@ -4550,6 +4560,7 @@ get_references_in_stmt (gimple *stmt, ve

>         {

>           ref.ref = op1;

>           ref.is_read = true;

> +         ref.is_conditional_in_stmt = false;

>           references->safe_push (ref);

>         }

>      }

> @@ -4577,6 +4588,7 @@ get_references_in_stmt (gimple *stmt, ve

>               type = TREE_TYPE (gimple_call_arg (stmt, 3));

>             if (TYPE_ALIGN (type) != align)

>               type = build_aligned_type (type, align);

> +           ref.is_conditional_in_stmt = true;

>             ref.ref = fold_build2 (MEM_REF, type, gimple_call_arg (stmt, 0),

>                                    ptr);

>             references->safe_push (ref);

> @@ -4596,6 +4608,7 @@ get_references_in_stmt (gimple *stmt, ve

>             {

>               ref.ref = op1;

>               ref.is_read = true;

> +             ref.is_conditional_in_stmt = false;

>               references->safe_push (ref);

>             }

>         }

> @@ -4609,6 +4622,7 @@ get_references_in_stmt (gimple *stmt, ve

>      {

>        ref.ref = op0;

>        ref.is_read = false;

> +      ref.is_conditional_in_stmt = false;

>        references->safe_push (ref);

>      }

>    return clobbers_memory;

> @@ -4673,8 +4687,8 @@ find_data_references_in_stmt (struct loo

>

>    FOR_EACH_VEC_ELT (references, i, ref)

>      {

> -      dr = create_data_ref (nest, loop_containing_stmt (stmt),

> -                           ref->ref, stmt, ref->is_read);

> +      dr = create_data_ref (nest, loop_containing_stmt (stmt), ref->ref,

> +                           stmt, ref->is_read, ref->is_conditional_in_stmt);

>        gcc_assert (dr != NULL);

>        datarefs->safe_push (dr);

>      }

> @@ -4703,7 +4717,8 @@ graphite_find_data_references_in_stmt (l

>

>    FOR_EACH_VEC_ELT (references, i, ref)

>      {

> -      dr = create_data_ref (nest, loop, ref->ref, stmt, ref->is_read);

> +      dr = create_data_ref (nest, loop, ref->ref, stmt, ref->is_read,

> +                           ref->is_conditional_in_stmt);

>        gcc_assert (dr != NULL);

>        datarefs->safe_push (dr);

>      }

> Index: gcc/tree-ssa-loop-prefetch.c

> ===================================================================

> --- gcc/tree-ssa-loop-prefetch.c        2017-07-03 08:20:56.404763323 +0100

> +++ gcc/tree-ssa-loop-prefetch.c        2017-07-03 08:42:51.147380631 +0100

> @@ -1633,7 +1633,7 @@ determine_loop_nest_reuse (struct loop *

>      for (ref = gr->refs; ref; ref = ref->next)

>        {

>         dr = create_data_ref (nest, loop_containing_stmt (ref->stmt),

> -                             ref->mem, ref->stmt, !ref->write_p);

> +                             ref->mem, ref->stmt, !ref->write_p, false);

>

>         if (dr)

>           {

> Index: gcc/tree-vect-data-refs.c

> ===================================================================

> --- gcc/tree-vect-data-refs.c   2017-07-03 08:42:50.185422235 +0100

> +++ gcc/tree-vect-data-refs.c   2017-07-03 08:47:16.424712986 +0100

> @@ -647,6 +647,69 @@ vect_slp_analyze_instance_dependence (sl

>    return res;

>  }

>

> +/* Record in VINFO the base alignment guarantee given by DRB.  STMT is

> +   the statement that contains DRB, which is useful for recording in the

> +   dump file.  */

> +

> +static void

> +vect_record_base_alignment (vec_info *vinfo, gimple *stmt,

> +                           innermost_loop_behavior *drb)

> +{

> +  bool existed;

> +  innermost_loop_behavior *&entry

> +    = vinfo->base_alignments.get_or_insert (drb->base_address, &existed);

> +  if (!existed || entry->base_alignment < drb->base_alignment)

> +    {

> +      entry = drb;

> +      if (dump_enabled_p ())

> +       {

> +         dump_printf_loc (MSG_NOTE, vect_location,

> +                          "recording new base alignment for ");

> +         dump_generic_expr (MSG_NOTE, TDF_SLIM, drb->base_address);

> +         dump_printf (MSG_NOTE, "\n");

> +         dump_printf_loc (MSG_NOTE, vect_location,

> +                          "  alignment:    %d\n", drb->base_alignment);

> +         dump_printf_loc (MSG_NOTE, vect_location,

> +                          "  misalignment: %d\n", drb->base_misalignment);

> +         dump_printf_loc (MSG_NOTE, vect_location,

> +                          "  based on:     ");

> +         dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);

> +       }

> +    }

> +}

> +

> +/* If the region we're going to vectorize is reached, all unconditional

> +   data references occur at least once.  We can therefore pool the base

> +   alignment guarantees from each unconditional reference.  Do this by

> +   going through all the data references in VINFO and checking whether

> +   the containing statement makes the reference unconditionally.  If so,

> +   record the alignment of the base address in VINFO so that it can be

> +   used for all other references with the same base.  */

> +

> +void

> +vect_record_base_alignments (vec_info *vinfo)

> +{

> +  loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo);

> +  struct loop *loop = loop_vinfo ? LOOP_VINFO_LOOP (loop_vinfo) : NULL;

> +  data_reference *dr;

> +  unsigned int i;

> +  FOR_EACH_VEC_ELT (vinfo->datarefs, i, dr)

> +    if (!DR_IS_CONDITIONAL_IN_STMT (dr))

> +      {

> +       gimple *stmt = DR_STMT (dr);

> +       vect_record_base_alignment (vinfo, stmt, &DR_INNERMOST (dr));

> +

> +       /* If DR is nested in the loop that is being vectorized, we can also

> +          record the alignment of the base wrt the outer loop.  */

> +       if (loop && nested_in_vect_loop_p (loop, stmt))

> +         {

> +           stmt_vec_info stmt_info = vinfo_for_stmt (stmt);

> +           vect_record_base_alignment

> +             (vinfo, stmt, &STMT_VINFO_DR_WRT_VEC_LOOP (stmt_info));

> +         }

> +      }

> +}

> +

>  /* Function vect_compute_data_ref_alignment

>

>     Compute the misalignment of the data reference DR.

> @@ -664,6 +727,7 @@ vect_compute_data_ref_alignment (struct

>  {

>    gimple *stmt = DR_STMT (dr);

>    stmt_vec_info stmt_info = vinfo_for_stmt (stmt);

> +  vec_base_alignments *base_alignments = &stmt_info->vinfo->base_alignments;

>    loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);

>    struct loop *loop = NULL;

>    tree ref = DR_REF (dr);

> @@ -732,6 +796,15 @@ vect_compute_data_ref_alignment (struct

>    unsigned int base_misalignment = drb->base_misalignment;

>    unsigned HOST_WIDE_INT vector_alignment = TYPE_ALIGN_UNIT (vectype);

>

> +  /* Calculate the maximum of the pooled base address alignment and the

> +     alignment that we can compute for DR itself.  */

> +  innermost_loop_behavior **entry = base_alignments->get (drb->base_address);

> +  if (entry && base_alignment < (*entry)->base_alignment)

> +    {

> +      base_alignment = (*entry)->base_alignment;

> +      base_misalignment = (*entry)->base_misalignment;

> +    }

> +

>    if (drb->offset_alignment < vector_alignment

>        || !step_preserves_misalignment_p

>        /* We need to know whether the step wrt the vectorized loop is

> @@ -2070,8 +2143,7 @@ vect_find_same_alignment_drs (struct dat

>    if (dra == drb)

>      return;

>

> -  if (!operand_equal_p (DR_BASE_OBJECT (dra), DR_BASE_OBJECT (drb),

> -                       OEP_ADDRESS_OF)

> +  if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)


Why this change?  It's semantically weaker after your change.

>        || !operand_equal_p (DR_OFFSET (dra), DR_OFFSET (drb), 0)

>        || !operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))

>      return;

> @@ -2129,6 +2201,7 @@ vect_analyze_data_refs_alignment (loop_v

>    vec<data_reference_p> datarefs = vinfo->datarefs;

>    struct data_reference *dr;

>

> +  vect_record_base_alignments (vinfo);

>    FOR_EACH_VEC_ELT (datarefs, i, dr)

>      {

>        stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr));

> @@ -3327,7 +3400,8 @@ vect_analyze_data_refs (vec_info *vinfo,

>             {

>               struct data_reference *newdr

>                 = create_data_ref (NULL, loop_containing_stmt (stmt),

> -                                  DR_REF (dr), stmt, maybe_scatter ? false : true);

> +                                  DR_REF (dr), stmt, !maybe_scatter,

> +                                  DR_IS_CONDITIONAL_IN_STMT (dr));

>               gcc_assert (newdr != NULL && DR_REF (newdr));

>               if (DR_BASE_ADDRESS (newdr)

>                   && DR_OFFSET (newdr)

> Index: gcc/tree-vect-slp.c

> ===================================================================

> --- gcc/tree-vect-slp.c 2017-07-03 08:20:56.404763323 +0100

> +++ gcc/tree-vect-slp.c 2017-07-03 08:42:51.149380545 +0100

> @@ -2358,6 +2358,7 @@ new_bb_vec_info (gimple_stmt_iterator re

>    gimple_stmt_iterator gsi;

>

>    res = (bb_vec_info) xcalloc (1, sizeof (struct _bb_vec_info));

> +  new (&res->base_alignments) vec_base_alignments ();


Ick.  I'd rather make this proper C++ and do

   res = new _bb_vec_info;

and add a constructor to the vec_info base initializing the hashtable.
The above smells fishy.

Looks like vec<> are happy with .create () being called on a zeroed struct.

Alternatively add .create () to hashtable/map.

Otherwise looks ok to me.

Thanks,
Richard.

>    res->kind = vec_info::bb;

>    BB_VINFO_BB (res) = bb;

>    res->region_begin = region_begin;

> @@ -2773,6 +2774,8 @@ vect_slp_analyze_bb_1 (gimple_stmt_itera

>        return NULL;

>      }

>

> +  vect_record_base_alignments (bb_vinfo);

> +

>    /* Analyze and verify the alignment of data references and the

>       dependence in the SLP instances.  */

>    for (i = 0; BB_VINFO_SLP_INSTANCES (bb_vinfo).iterate (i, &instance); )

> Index: gcc/tree-vect-loop.c

> ===================================================================

> --- gcc/tree-vect-loop.c        2017-07-03 08:20:56.404763323 +0100

> +++ gcc/tree-vect-loop.c        2017-07-03 08:42:51.149380545 +0100

> @@ -1159,6 +1159,7 @@ new_loop_vec_info (struct loop *loop)

>    LOOP_VINFO_VECT_FACTOR (res) = 0;

>    LOOP_VINFO_LOOP_NEST (res) = vNULL;

>    LOOP_VINFO_DATAREFS (res) = vNULL;

> +  new (&res->base_alignments) vec_base_alignments ();

>    LOOP_VINFO_DDRS (res) = vNULL;

>    LOOP_VINFO_UNALIGNED_DR (res) = NULL;

>    LOOP_VINFO_MAY_MISALIGN_STMTS (res) = vNULL;

> Index: gcc/tree-vectorizer.c

> ===================================================================

> --- gcc/tree-vectorizer.c       2017-07-03 08:20:56.404763323 +0100

> +++ gcc/tree-vectorizer.c       2017-07-03 08:42:51.149380545 +0100

> @@ -370,6 +370,8 @@ vect_destroy_datarefs (vec_info *vinfo)

>        }

>

>    free_data_refs (vinfo->datarefs);

> +

> +  vinfo->base_alignments.~vec_base_alignments ();

>  }

>

>  /* A helper function to free scev and LOOP niter information, as well as

> Index: gcc/testsuite/gcc.dg/vect/pr81136.c

> ===================================================================

> --- gcc/testsuite/gcc.dg/vect/pr81136.c 2017-07-03 08:20:56.404763323 +0100

> +++ gcc/testsuite/gcc.dg/vect/pr81136.c 2017-07-03 08:42:51.144380761 +0100

> @@ -14,3 +14,5 @@ fn1 (int n)

>    for (int i = 0; i < n; i++)

>      a->bar[i] = b[i];

>  }

> +

> +/* { dg-final { scan-tree-dump-not "Unknown misalignment" "vect" } } */
Richard Sandiford July 4, 2017, 12:01 p.m. | #2
Richard Biener <richard.guenther@gmail.com> writes:
> On Mon, Jul 3, 2017 at 9:49 AM, Richard Sandiford

> <richard.sandiford@linaro.org> wrote:

>> @@ -2070,8 +2143,7 @@ vect_find_same_alignment_drs (struct dat

>>    if (dra == drb)

>>      return;

>>

>> -  if (!operand_equal_p (DR_BASE_OBJECT (dra), DR_BASE_OBJECT (drb),

>> -                       OEP_ADDRESS_OF)

>> +  if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)

>

> Why this change?  It's semantically weaker after your change.


It's because the DR_BASE_OBJECT comes from the access_fn analysis
while the DR_BASE_ADDRESS comes from the innermost_loop_behavior.
I hadn't realised when adding the original code how different the
two were, and since all the other parts are based on the
innermost_loop_behavior, I think this check should be too.
E.g. it doesn't really make sense to compare DR_INITs based
on DR_BASE_OBJECT.

I guess it should have been a separate patch though.

>>        || !operand_equal_p (DR_OFFSET (dra), DR_OFFSET (drb), 0)

>>        || !operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))

>>      return;

>> @@ -2129,6 +2201,7 @@ vect_analyze_data_refs_alignment (loop_v

>>    vec<data_reference_p> datarefs = vinfo->datarefs;

>>    struct data_reference *dr;

>>

>> +  vect_record_base_alignments (vinfo);

>>    FOR_EACH_VEC_ELT (datarefs, i, dr)

>>      {

>>        stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr));

>> @@ -3327,7 +3400,8 @@ vect_analyze_data_refs (vec_info *vinfo,

>>             {

>>               struct data_reference *newdr

>>                 = create_data_ref (NULL, loop_containing_stmt (stmt),

>> - DR_REF (dr), stmt, maybe_scatter ? false : true);

>> +                                  DR_REF (dr), stmt, !maybe_scatter,

>> +                                  DR_IS_CONDITIONAL_IN_STMT (dr));

>>               gcc_assert (newdr != NULL && DR_REF (newdr));

>>               if (DR_BASE_ADDRESS (newdr)

>>                   && DR_OFFSET (newdr)

>> Index: gcc/tree-vect-slp.c

>> ===================================================================

>> --- gcc/tree-vect-slp.c 2017-07-03 08:20:56.404763323 +0100

>> +++ gcc/tree-vect-slp.c 2017-07-03 08:42:51.149380545 +0100

>> @@ -2358,6 +2358,7 @@ new_bb_vec_info (gimple_stmt_iterator re

>>    gimple_stmt_iterator gsi;

>>

>>    res = (bb_vec_info) xcalloc (1, sizeof (struct _bb_vec_info));

>> +  new (&res->base_alignments) vec_base_alignments ();

>

> Ick.  I'd rather make this proper C++ and do

>

>    res = new _bb_vec_info;

>

> and add a constructor to the vec_info base initializing the hashtable.

> The above smells fishy.


I knew I pushing my luck with that one.  I just didn't want to have to
convert the current xcalloc of loop_vec_info into a long list of explicit
zero initializers.  (OK, we have a lot of explicit zero assignments already,
but certainly some fields rely on the calloc zeroing.)

> Looks like vec<> are happy with .create () being called on a zeroed struct.

>

> Alternatively add .create () to hashtable/map.


The difference is that vec<> is explicitly meant to be POD, whereas
hash_map isn't (and I don't think we want it to be).

Ah well.  I'll do a separate pre-patch to C++-ify the structures.

Thanks,
Richard
Richard Biener July 4, 2017, 12:25 p.m. | #3
On Tue, Jul 4, 2017 at 2:01 PM, Richard Sandiford
<richard.sandiford@linaro.org> wrote:
> Richard Biener <richard.guenther@gmail.com> writes:

>> On Mon, Jul 3, 2017 at 9:49 AM, Richard Sandiford

>> <richard.sandiford@linaro.org> wrote:

>>> @@ -2070,8 +2143,7 @@ vect_find_same_alignment_drs (struct dat

>>>    if (dra == drb)

>>>      return;

>>>

>>> -  if (!operand_equal_p (DR_BASE_OBJECT (dra), DR_BASE_OBJECT (drb),

>>> -                       OEP_ADDRESS_OF)

>>> +  if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)

>>

>> Why this change?  It's semantically weaker after your change.

>

> It's because the DR_BASE_OBJECT comes from the access_fn analysis

> while the DR_BASE_ADDRESS comes from the innermost_loop_behavior.

> I hadn't realised when adding the original code how different the

> two were, and since all the other parts are based on the

> innermost_loop_behavior, I think this check should be too.

> E.g. it doesn't really make sense to compare DR_INITs based

> on DR_BASE_OBJECT.


Ah ok, makes sense now.

> I guess it should have been a separate patch though.


No need.

>>>        || !operand_equal_p (DR_OFFSET (dra), DR_OFFSET (drb), 0)

>>>        || !operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))

>>>      return;

>>> @@ -2129,6 +2201,7 @@ vect_analyze_data_refs_alignment (loop_v

>>>    vec<data_reference_p> datarefs = vinfo->datarefs;

>>>    struct data_reference *dr;

>>>

>>> +  vect_record_base_alignments (vinfo);

>>>    FOR_EACH_VEC_ELT (datarefs, i, dr)

>>>      {

>>>        stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr));

>>> @@ -3327,7 +3400,8 @@ vect_analyze_data_refs (vec_info *vinfo,

>>>             {

>>>               struct data_reference *newdr

>>>                 = create_data_ref (NULL, loop_containing_stmt (stmt),

>>> - DR_REF (dr), stmt, maybe_scatter ? false : true);

>>> +                                  DR_REF (dr), stmt, !maybe_scatter,

>>> +                                  DR_IS_CONDITIONAL_IN_STMT (dr));

>>>               gcc_assert (newdr != NULL && DR_REF (newdr));

>>>               if (DR_BASE_ADDRESS (newdr)

>>>                   && DR_OFFSET (newdr)

>>> Index: gcc/tree-vect-slp.c

>>> ===================================================================

>>> --- gcc/tree-vect-slp.c 2017-07-03 08:20:56.404763323 +0100

>>> +++ gcc/tree-vect-slp.c 2017-07-03 08:42:51.149380545 +0100

>>> @@ -2358,6 +2358,7 @@ new_bb_vec_info (gimple_stmt_iterator re

>>>    gimple_stmt_iterator gsi;

>>>

>>>    res = (bb_vec_info) xcalloc (1, sizeof (struct _bb_vec_info));

>>> +  new (&res->base_alignments) vec_base_alignments ();

>>

>> Ick.  I'd rather make this proper C++ and do

>>

>>    res = new _bb_vec_info;

>>

>> and add a constructor to the vec_info base initializing the hashtable.

>> The above smells fishy.

>

> I knew I pushing my luck with that one.  I just didn't want to have to

> convert the current xcalloc of loop_vec_info into a long list of explicit

> zero initializers.  (OK, we have a lot of explicit zero assignments already,

> but certainly some fields rely on the calloc zeroing.)

>

>> Looks like vec<> are happy with .create () being called on a zeroed struct.

>>

>> Alternatively add .create () to hashtable/map.

>

> The difference is that vec<> is explicitly meant to be POD, whereas

> hash_map isn't (and I don't think we want it to be).


Ah, indeed.  So your patch makes *vec_info no longer POD (no problem
but then use new/delete and constructors).

> Ah well.  I'll do a separate pre-patch to C++-ify the structures.


Thanks.
Richard.

> Thanks,

> Richard
Richard Sandiford July 27, 2017, 12:50 p.m. | #4
Richard Biener <richard.guenther@gmail.com> writes:
> On Tue, Jul 4, 2017 at 2:01 PM, Richard Sandiford

> <richard.sandiford@linaro.org> wrote:

>> Richard Biener <richard.guenther@gmail.com> writes:

>>> On Mon, Jul 3, 2017 at 9:49 AM, Richard Sandiford

>>> <richard.sandiford@linaro.org> wrote:

>>>> @@ -2070,8 +2143,7 @@ vect_find_same_alignment_drs (struct dat

>>>>    if (dra == drb)

>>>>      return;

>>>>

>>>> -  if (!operand_equal_p (DR_BASE_OBJECT (dra), DR_BASE_OBJECT (drb),

>>>> -                       OEP_ADDRESS_OF)

>>>> +  if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)

>>>

>>> Why this change?  It's semantically weaker after your change.

>>

>> It's because the DR_BASE_OBJECT comes from the access_fn analysis

>> while the DR_BASE_ADDRESS comes from the innermost_loop_behavior.

>> I hadn't realised when adding the original code how different the

>> two were, and since all the other parts are based on the

>> innermost_loop_behavior, I think this check should be too.

>> E.g. it doesn't really make sense to compare DR_INITs based

>> on DR_BASE_OBJECT.

>

> Ah ok, makes sense now.

>

>> I guess it should have been a separate patch though.

>

> No need.

>

>>>>        || !operand_equal_p (DR_OFFSET (dra), DR_OFFSET (drb), 0)

>>>>        || !operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))

>>>>      return;

>>>> @@ -2129,6 +2201,7 @@ vect_analyze_data_refs_alignment (loop_v

>>>>    vec<data_reference_p> datarefs = vinfo->datarefs;

>>>>    struct data_reference *dr;

>>>>

>>>> +  vect_record_base_alignments (vinfo);

>>>>    FOR_EACH_VEC_ELT (datarefs, i, dr)

>>>>      {

>>>>        stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr));

>>>> @@ -3327,7 +3400,8 @@ vect_analyze_data_refs (vec_info *vinfo,

>>>>             {

>>>>               struct data_reference *newdr

>>>>                 = create_data_ref (NULL, loop_containing_stmt (stmt),

>>>> - DR_REF (dr), stmt, maybe_scatter ? false : true);

>>>> +                                  DR_REF (dr), stmt, !maybe_scatter,

>>>> +                                  DR_IS_CONDITIONAL_IN_STMT (dr));

>>>>               gcc_assert (newdr != NULL && DR_REF (newdr));

>>>>               if (DR_BASE_ADDRESS (newdr)

>>>>                   && DR_OFFSET (newdr)

>>>> Index: gcc/tree-vect-slp.c

>>>> ===================================================================

>>>> --- gcc/tree-vect-slp.c 2017-07-03 08:20:56.404763323 +0100

>>>> +++ gcc/tree-vect-slp.c 2017-07-03 08:42:51.149380545 +0100

>>>> @@ -2358,6 +2358,7 @@ new_bb_vec_info (gimple_stmt_iterator re

>>>>    gimple_stmt_iterator gsi;

>>>>

>>>>    res = (bb_vec_info) xcalloc (1, sizeof (struct _bb_vec_info));

>>>> +  new (&res->base_alignments) vec_base_alignments ();

>>>

>>> Ick.  I'd rather make this proper C++ and do

>>>

>>>    res = new _bb_vec_info;

>>>

>>> and add a constructor to the vec_info base initializing the hashtable.

>>> The above smells fishy.

>>

>> I knew I pushing my luck with that one.  I just didn't want to have to

>> convert the current xcalloc of loop_vec_info into a long list of explicit

>> zero initializers.  (OK, we have a lot of explicit zero assignments already,

>> but certainly some fields rely on the calloc zeroing.)

>>

>>> Looks like vec<> are happy with .create () being called on a zeroed struct.

>>>

>>> Alternatively add .create () to hashtable/map.

>>

>> The difference is that vec<> is explicitly meant to be POD, whereas

>> hash_map isn't (and I don't think we want it to be).

>

> Ah, indeed.  So your patch makes *vec_info no longer POD (no problem

> but then use new/delete and constructors).

>

>> Ah well.  I'll do a separate pre-patch to C++-ify the structures.


Here's an update that applies on top of the vec_info c++-ification patch
I just posted [ https://gcc.gnu.org/ml/gcc-patches/2017-07/msg01807.html ]

Tested as before.  OK to install?

Thanks,
Richard


2017-07-27  Richard Sandiford  <richard.sandiford@linaro.org>

gcc/
	PR tree-optimization/81136
	* tree-vectorizer.h: Include tree-hash-traits.h.
	(vec_base_alignments): New typedef.
	(vec_info): Add a base_alignments field.
	(vect_record_base_alignments): Declare.
	* tree-data-ref.h (data_reference): Add an is_conditional_in_stmt
	field.
	(DR_IS_CONDITIONAL_IN_STMT): New macro.
	(create_data_ref): Add an is_conditional_in_stmt argument.
	* tree-data-ref.c (create_data_ref): Likewise.  Use it to initialize
	the is_conditional_in_stmt field.
	(data_ref_loc): Add an is_conditional_in_stmt field.
	(get_references_in_stmt): Set the is_conditional_in_stmt field.
	(find_data_references_in_stmt): Update call to create_data_ref.
	(graphite_find_data_references_in_stmt): Likewise.
	* tree-ssa-loop-prefetch.c (determine_loop_nest_reuse): Likewise.
	* tree-vect-data-refs.c (vect_analyze_data_refs): Likewise.
	(vect_record_base_alignment): New function.
	(vect_record_base_alignments): Likewise.
	(vect_compute_data_ref_alignment): Adjust base_addr and aligned_to
	for nested statements even if we fail to compute a misalignment.
	Use pooled base alignments for unconditional references.
	(vect_find_same_alignment_drs): Compare base addresses instead
	of base objects.
	(vect_analyze_data_refs_alignment): Call vect_record_base_alignments.
	* tree-vect-slp.c (vect_slp_analyze_bb_1): Likewise.

gcc/testsuite/
	PR tree-optimization/81136
	* gcc.dg/vect/pr81136.c: Add scan test.Index: gcc/tree-vectorizer.h
===================================================================
--- gcc/tree-vectorizer.h	2017-07-27 13:46:58.376642483 +0100
+++ gcc/tree-vectorizer.h	2017-07-27 13:46:58.579633332 +0100
@@ -22,6 +22,7 @@ Software Foundation; either version 3, o
 #define GCC_TREE_VECTORIZER_H
 
 #include "tree-data-ref.h"
+#include "tree-hash-traits.h"
 #include "target.h"
 
 /* Used for naming of new temporaries.  */
@@ -84,6 +85,11 @@ struct stmt_info_for_cost {
 
 typedef vec<stmt_info_for_cost> stmt_vector_for_cost;
 
+/* Maps base addresses to an innermost_loop_behavior that gives the maximum
+   known alignment for that base.  */
+typedef hash_map<tree_operand_hash,
+		 innermost_loop_behavior *> vec_base_alignments;
+
 /************************************************************************
   SLP
  ************************************************************************/
@@ -169,6 +175,10 @@ struct vec_info {
   /* All data references.  Freed by free_data_refs, so not an auto_vec.  */
   vec<data_reference_p> datarefs;
 
+  /* Maps base addresses to an innermost_loop_behavior that gives the maximum
+     known alignment for that base.  */
+  vec_base_alignments base_alignments;
+
   /* All data dependences.  Freed by free_dependence_relations, so not
      an auto_vec.  */
   vec<ddr_p> ddrs;
@@ -1162,6 +1172,7 @@ extern bool vect_prune_runtime_alias_tes
 extern bool vect_check_gather_scatter (gimple *, loop_vec_info,
 				       gather_scatter_info *);
 extern bool vect_analyze_data_refs (vec_info *, int *);
+extern void vect_record_base_alignments (vec_info *);
 extern tree vect_create_data_ref_ptr (gimple *, tree, struct loop *, tree,
 				      tree *, gimple_stmt_iterator *,
 				      gimple **, bool, bool *,
Index: gcc/tree-data-ref.h
===================================================================
--- gcc/tree-data-ref.h	2017-07-27 13:46:58.376642483 +0100
+++ gcc/tree-data-ref.h	2017-07-27 13:46:58.578633377 +0100
@@ -159,6 +159,11 @@ struct data_reference
   /* True when the data reference is in RHS of a stmt.  */
   bool is_read;
 
+  /* True when the data reference is conditional within STMT,
+     i.e. if it might not occur even when the statement is executed
+     and runs to completion.  */
+  bool is_conditional_in_stmt;
+
   /* Behavior of the memory reference in the innermost loop.  */
   struct innermost_loop_behavior innermost;
 
@@ -178,6 +183,7 @@ #define DR_ACCESS_FN(DR, I)        DR_AC
 #define DR_NUM_DIMENSIONS(DR)      DR_ACCESS_FNS (DR).length ()
 #define DR_IS_READ(DR)             (DR)->is_read
 #define DR_IS_WRITE(DR)            (!DR_IS_READ (DR))
+#define DR_IS_CONDITIONAL_IN_STMT(DR) (DR)->is_conditional_in_stmt
 #define DR_BASE_ADDRESS(DR)        (DR)->innermost.base_address
 #define DR_OFFSET(DR)              (DR)->innermost.offset
 #define DR_INIT(DR)                (DR)->innermost.init
@@ -434,7 +440,8 @@ extern bool graphite_find_data_reference
 						   vec<data_reference_p> *);
 tree find_data_references_in_loop (struct loop *, vec<data_reference_p> *);
 bool loop_nest_has_data_refs (loop_p loop);
-struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple *, bool);
+struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple *, bool,
+					bool);
 extern bool find_loop_nest (struct loop *, vec<loop_p> *);
 extern struct data_dependence_relation *initialize_data_dependence_relation
      (struct data_reference *, struct data_reference *, vec<loop_p>);
Index: gcc/tree-data-ref.c
===================================================================
--- gcc/tree-data-ref.c	2017-07-27 13:46:58.376642483 +0100
+++ gcc/tree-data-ref.c	2017-07-27 13:46:58.577633422 +0100
@@ -1125,15 +1125,19 @@ free_data_ref (data_reference_p dr)
   free (dr);
 }
 
-/* Analyzes memory reference MEMREF accessed in STMT.  The reference
-   is read if IS_READ is true, write otherwise.  Returns the
-   data_reference description of MEMREF.  NEST is the outermost loop
-   in which the reference should be instantiated, LOOP is the loop in
-   which the data reference should be analyzed.  */
+/* Analyze memory reference MEMREF, which is accessed in STMT.
+   The reference is a read if IS_READ is true, otherwise it is a write.
+   IS_CONDITIONAL_IN_STMT indicates that the reference is conditional
+   within STMT, i.e. that it might not occur even if STMT is executed
+   and runs to completion.
+
+   Return the data_reference description of MEMREF.  NEST is the outermost
+   loop in which the reference should be instantiated, LOOP is the loop
+   in which the data reference should be analyzed.  */
 
 struct data_reference *
 create_data_ref (loop_p nest, loop_p loop, tree memref, gimple *stmt,
-		 bool is_read)
+		 bool is_read, bool is_conditional_in_stmt)
 {
   struct data_reference *dr;
 
@@ -1148,6 +1152,7 @@ create_data_ref (loop_p nest, loop_p loo
   DR_STMT (dr) = stmt;
   DR_REF (dr) = memref;
   DR_IS_READ (dr) = is_read;
+  DR_IS_CONDITIONAL_IN_STMT (dr) = is_conditional_in_stmt;
 
   dr_analyze_innermost (&DR_INNERMOST (dr), memref,
 			nest != NULL ? loop : NULL);
@@ -4774,6 +4779,11 @@ struct data_ref_loc
 
   /* True if the memory reference is read.  */
   bool is_read;
+
+  /* True if the data reference is conditional within the containing
+     statement, i.e. if it might not occur even when the statement
+     is executed and runs to completion.  */
+  bool is_conditional_in_stmt;
 };
 
 
@@ -4840,6 +4850,7 @@ get_references_in_stmt (gimple *stmt, ve
 	{
 	  ref.ref = op1;
 	  ref.is_read = true;
+	  ref.is_conditional_in_stmt = false;
 	  references->safe_push (ref);
 	}
     }
@@ -4867,6 +4878,7 @@ get_references_in_stmt (gimple *stmt, ve
 	      type = TREE_TYPE (gimple_call_arg (stmt, 3));
 	    if (TYPE_ALIGN (type) != align)
 	      type = build_aligned_type (type, align);
+	    ref.is_conditional_in_stmt = true;
 	    ref.ref = fold_build2 (MEM_REF, type, gimple_call_arg (stmt, 0),
 				   ptr);
 	    references->safe_push (ref);
@@ -4886,6 +4898,7 @@ get_references_in_stmt (gimple *stmt, ve
 	    {
 	      ref.ref = op1;
 	      ref.is_read = true;
+	      ref.is_conditional_in_stmt = false;
 	      references->safe_push (ref);
 	    }
 	}
@@ -4899,6 +4912,7 @@ get_references_in_stmt (gimple *stmt, ve
     {
       ref.ref = op0;
       ref.is_read = false;
+      ref.is_conditional_in_stmt = false;
       references->safe_push (ref);
     }
   return clobbers_memory;
@@ -4963,8 +4977,8 @@ find_data_references_in_stmt (struct loo
 
   FOR_EACH_VEC_ELT (references, i, ref)
     {
-      dr = create_data_ref (nest, loop_containing_stmt (stmt),
-			    ref->ref, stmt, ref->is_read);
+      dr = create_data_ref (nest, loop_containing_stmt (stmt), ref->ref,
+			    stmt, ref->is_read, ref->is_conditional_in_stmt);
       gcc_assert (dr != NULL);
       datarefs->safe_push (dr);
     }
@@ -4993,7 +5007,8 @@ graphite_find_data_references_in_stmt (l
 
   FOR_EACH_VEC_ELT (references, i, ref)
     {
-      dr = create_data_ref (nest, loop, ref->ref, stmt, ref->is_read);
+      dr = create_data_ref (nest, loop, ref->ref, stmt, ref->is_read,
+			    ref->is_conditional_in_stmt);
       gcc_assert (dr != NULL);
       datarefs->safe_push (dr);
     }
Index: gcc/tree-ssa-loop-prefetch.c
===================================================================
--- gcc/tree-ssa-loop-prefetch.c	2017-07-27 13:46:58.376642483 +0100
+++ gcc/tree-ssa-loop-prefetch.c	2017-07-27 13:46:58.578633377 +0100
@@ -1633,7 +1633,7 @@ determine_loop_nest_reuse (struct loop *
     for (ref = gr->refs; ref; ref = ref->next)
       {
 	dr = create_data_ref (nest, loop_containing_stmt (ref->stmt),
-			      ref->mem, ref->stmt, !ref->write_p);
+			      ref->mem, ref->stmt, !ref->write_p, false);
 
 	if (dr)
 	  {
Index: gcc/tree-vect-data-refs.c
===================================================================
--- gcc/tree-vect-data-refs.c	2017-07-27 13:46:58.376642483 +0100
+++ gcc/tree-vect-data-refs.c	2017-07-27 13:46:58.579633332 +0100
@@ -708,6 +708,69 @@ vect_slp_analyze_instance_dependence (sl
   return res;
 }
 
+/* Record in VINFO the base alignment guarantee given by DRB.  STMT is
+   the statement that contains DRB, which is useful for recording in the
+   dump file.  */
+
+static void
+vect_record_base_alignment (vec_info *vinfo, gimple *stmt,
+			    innermost_loop_behavior *drb)
+{
+  bool existed;
+  innermost_loop_behavior *&entry
+    = vinfo->base_alignments.get_or_insert (drb->base_address, &existed);
+  if (!existed || entry->base_alignment < drb->base_alignment)
+    {
+      entry = drb;
+      if (dump_enabled_p ())
+	{
+	  dump_printf_loc (MSG_NOTE, vect_location,
+			   "recording new base alignment for ");
+	  dump_generic_expr (MSG_NOTE, TDF_SLIM, drb->base_address);
+	  dump_printf (MSG_NOTE, "\n");
+	  dump_printf_loc (MSG_NOTE, vect_location,
+			   "  alignment:    %d\n", drb->base_alignment);
+	  dump_printf_loc (MSG_NOTE, vect_location,
+			   "  misalignment: %d\n", drb->base_misalignment);
+	  dump_printf_loc (MSG_NOTE, vect_location,
+			   "  based on:     ");
+	  dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
+	}
+    }
+}
+
+/* If the region we're going to vectorize is reached, all unconditional
+   data references occur at least once.  We can therefore pool the base
+   alignment guarantees from each unconditional reference.  Do this by
+   going through all the data references in VINFO and checking whether
+   the containing statement makes the reference unconditionally.  If so,
+   record the alignment of the base address in VINFO so that it can be
+   used for all other references with the same base.  */
+
+void
+vect_record_base_alignments (vec_info *vinfo)
+{
+  loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo);
+  struct loop *loop = loop_vinfo ? LOOP_VINFO_LOOP (loop_vinfo) : NULL;
+  data_reference *dr;
+  unsigned int i;
+  FOR_EACH_VEC_ELT (vinfo->datarefs, i, dr)
+    if (!DR_IS_CONDITIONAL_IN_STMT (dr))
+      {
+	gimple *stmt = DR_STMT (dr);
+	vect_record_base_alignment (vinfo, stmt, &DR_INNERMOST (dr));
+
+	/* If DR is nested in the loop that is being vectorized, we can also
+	   record the alignment of the base wrt the outer loop.  */
+	if (loop && nested_in_vect_loop_p (loop, stmt))
+	  {
+	    stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
+	    vect_record_base_alignment
+	      (vinfo, stmt, &STMT_VINFO_DR_WRT_VEC_LOOP (stmt_info));
+	  }
+      }
+}
+
 /* Function vect_compute_data_ref_alignment
 
    Compute the misalignment of the data reference DR.
@@ -725,6 +788,7 @@ vect_compute_data_ref_alignment (struct
 {
   gimple *stmt = DR_STMT (dr);
   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
+  vec_base_alignments *base_alignments = &stmt_info->vinfo->base_alignments;
   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
   struct loop *loop = NULL;
   tree ref = DR_REF (dr);
@@ -793,6 +857,15 @@ vect_compute_data_ref_alignment (struct
   unsigned int base_misalignment = drb->base_misalignment;
   unsigned HOST_WIDE_INT vector_alignment = TYPE_ALIGN_UNIT (vectype);
 
+  /* Calculate the maximum of the pooled base address alignment and the
+     alignment that we can compute for DR itself.  */
+  innermost_loop_behavior **entry = base_alignments->get (drb->base_address);
+  if (entry && base_alignment < (*entry)->base_alignment)
+    {
+      base_alignment = (*entry)->base_alignment;
+      base_misalignment = (*entry)->base_misalignment;
+    }
+
   if (drb->offset_alignment < vector_alignment
       || !step_preserves_misalignment_p
       /* We need to know whether the step wrt the vectorized loop is
@@ -2113,8 +2186,7 @@ vect_find_same_alignment_drs (struct dat
   if (dra == drb)
     return;
 
-  if (!operand_equal_p (DR_BASE_OBJECT (dra), DR_BASE_OBJECT (drb),
-			OEP_ADDRESS_OF)
+  if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)
       || !operand_equal_p (DR_OFFSET (dra), DR_OFFSET (drb), 0)
       || !operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))
     return;
@@ -2172,6 +2244,7 @@ vect_analyze_data_refs_alignment (loop_v
   vec<data_reference_p> datarefs = vinfo->datarefs;
   struct data_reference *dr;
 
+  vect_record_base_alignments (vinfo);
   FOR_EACH_VEC_ELT (datarefs, i, dr)
     {
       stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr));
@@ -3437,7 +3510,8 @@ vect_analyze_data_refs (vec_info *vinfo,
 	    {
 	      struct data_reference *newdr
 		= create_data_ref (NULL, loop_containing_stmt (stmt),
-				   DR_REF (dr), stmt, maybe_scatter ? false : true);
+				   DR_REF (dr), stmt, !maybe_scatter,
+				   DR_IS_CONDITIONAL_IN_STMT (dr));
 	      gcc_assert (newdr != NULL && DR_REF (newdr));
 	      if (DR_BASE_ADDRESS (newdr)
 		  && DR_OFFSET (newdr)
Index: gcc/tree-vect-slp.c
===================================================================
--- gcc/tree-vect-slp.c	2017-07-27 13:46:58.376642483 +0100
+++ gcc/tree-vect-slp.c	2017-07-27 13:46:58.579633332 +0100
@@ -2764,6 +2764,8 @@ vect_slp_analyze_bb_1 (gimple_stmt_itera
       return NULL;
     }
 
+  vect_record_base_alignments (bb_vinfo);
+
   /* Analyze and verify the alignment of data references and the
      dependence in the SLP instances.  */
   for (i = 0; BB_VINFO_SLP_INSTANCES (bb_vinfo).iterate (i, &instance); )
Index: gcc/testsuite/gcc.dg/vect/pr81136.c
===================================================================
--- gcc/testsuite/gcc.dg/vect/pr81136.c	2017-07-27 13:46:58.376642483 +0100
+++ gcc/testsuite/gcc.dg/vect/pr81136.c	2017-07-27 13:46:58.577633422 +0100
@@ -14,3 +14,5 @@ fn1 (int n)
   for (int i = 0; i < n; i++)
     a->bar[i] = b[i];
 }
+
+/* { dg-final { scan-tree-dump-not "Unknown misalignment" "vect" } } */

Richard Biener July 28, 2017, 8:21 a.m. | #5
On Thu, Jul 27, 2017 at 2:50 PM, Richard Sandiford
<richard.sandiford@linaro.org> wrote:
> Richard Biener <richard.guenther@gmail.com> writes:

>> On Tue, Jul 4, 2017 at 2:01 PM, Richard Sandiford

>> <richard.sandiford@linaro.org> wrote:

>>> Richard Biener <richard.guenther@gmail.com> writes:

>>>> On Mon, Jul 3, 2017 at 9:49 AM, Richard Sandiford

>>>> <richard.sandiford@linaro.org> wrote:

>>>>> @@ -2070,8 +2143,7 @@ vect_find_same_alignment_drs (struct dat

>>>>>    if (dra == drb)

>>>>>      return;

>>>>>

>>>>> -  if (!operand_equal_p (DR_BASE_OBJECT (dra), DR_BASE_OBJECT (drb),

>>>>> -                       OEP_ADDRESS_OF)

>>>>> +  if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)

>>>>

>>>> Why this change?  It's semantically weaker after your change.

>>>

>>> It's because the DR_BASE_OBJECT comes from the access_fn analysis

>>> while the DR_BASE_ADDRESS comes from the innermost_loop_behavior.

>>> I hadn't realised when adding the original code how different the

>>> two were, and since all the other parts are based on the

>>> innermost_loop_behavior, I think this check should be too.

>>> E.g. it doesn't really make sense to compare DR_INITs based

>>> on DR_BASE_OBJECT.

>>

>> Ah ok, makes sense now.

>>

>>> I guess it should have been a separate patch though.

>>

>> No need.

>>

>>>>>        || !operand_equal_p (DR_OFFSET (dra), DR_OFFSET (drb), 0)

>>>>>        || !operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))

>>>>>      return;

>>>>> @@ -2129,6 +2201,7 @@ vect_analyze_data_refs_alignment (loop_v

>>>>>    vec<data_reference_p> datarefs = vinfo->datarefs;

>>>>>    struct data_reference *dr;

>>>>>

>>>>> +  vect_record_base_alignments (vinfo);

>>>>>    FOR_EACH_VEC_ELT (datarefs, i, dr)

>>>>>      {

>>>>>        stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr));

>>>>> @@ -3327,7 +3400,8 @@ vect_analyze_data_refs (vec_info *vinfo,

>>>>>             {

>>>>>               struct data_reference *newdr

>>>>>                 = create_data_ref (NULL, loop_containing_stmt (stmt),

>>>>> - DR_REF (dr), stmt, maybe_scatter ? false : true);

>>>>> +                                  DR_REF (dr), stmt, !maybe_scatter,

>>>>> +                                  DR_IS_CONDITIONAL_IN_STMT (dr));

>>>>>               gcc_assert (newdr != NULL && DR_REF (newdr));

>>>>>               if (DR_BASE_ADDRESS (newdr)

>>>>>                   && DR_OFFSET (newdr)

>>>>> Index: gcc/tree-vect-slp.c

>>>>> ===================================================================

>>>>> --- gcc/tree-vect-slp.c 2017-07-03 08:20:56.404763323 +0100

>>>>> +++ gcc/tree-vect-slp.c 2017-07-03 08:42:51.149380545 +0100

>>>>> @@ -2358,6 +2358,7 @@ new_bb_vec_info (gimple_stmt_iterator re

>>>>>    gimple_stmt_iterator gsi;

>>>>>

>>>>>    res = (bb_vec_info) xcalloc (1, sizeof (struct _bb_vec_info));

>>>>> +  new (&res->base_alignments) vec_base_alignments ();

>>>>

>>>> Ick.  I'd rather make this proper C++ and do

>>>>

>>>>    res = new _bb_vec_info;

>>>>

>>>> and add a constructor to the vec_info base initializing the hashtable.

>>>> The above smells fishy.

>>>

>>> I knew I pushing my luck with that one.  I just didn't want to have to

>>> convert the current xcalloc of loop_vec_info into a long list of explicit

>>> zero initializers.  (OK, we have a lot of explicit zero assignments already,

>>> but certainly some fields rely on the calloc zeroing.)

>>>

>>>> Looks like vec<> are happy with .create () being called on a zeroed struct.

>>>>

>>>> Alternatively add .create () to hashtable/map.

>>>

>>> The difference is that vec<> is explicitly meant to be POD, whereas

>>> hash_map isn't (and I don't think we want it to be).

>>

>> Ah, indeed.  So your patch makes *vec_info no longer POD (no problem

>> but then use new/delete and constructors).

>>

>>> Ah well.  I'll do a separate pre-patch to C++-ify the structures.

>

> Here's an update that applies on top of the vec_info c++-ification patch

> I just posted [ https://gcc.gnu.org/ml/gcc-patches/2017-07/msg01807.html ]

>

> Tested as before.  OK to install?


Ok.

Thanks,
Richard.

> Thanks,

> Richard

>

>

> 2017-07-27  Richard Sandiford  <richard.sandiford@linaro.org>

>

> gcc/

>         PR tree-optimization/81136

>         * tree-vectorizer.h: Include tree-hash-traits.h.

>         (vec_base_alignments): New typedef.

>         (vec_info): Add a base_alignments field.

>         (vect_record_base_alignments): Declare.

>         * tree-data-ref.h (data_reference): Add an is_conditional_in_stmt

>         field.

>         (DR_IS_CONDITIONAL_IN_STMT): New macro.

>         (create_data_ref): Add an is_conditional_in_stmt argument.

>         * tree-data-ref.c (create_data_ref): Likewise.  Use it to initialize

>         the is_conditional_in_stmt field.

>         (data_ref_loc): Add an is_conditional_in_stmt field.

>         (get_references_in_stmt): Set the is_conditional_in_stmt field.

>         (find_data_references_in_stmt): Update call to create_data_ref.

>         (graphite_find_data_references_in_stmt): Likewise.

>         * tree-ssa-loop-prefetch.c (determine_loop_nest_reuse): Likewise.

>         * tree-vect-data-refs.c (vect_analyze_data_refs): Likewise.

>         (vect_record_base_alignment): New function.

>         (vect_record_base_alignments): Likewise.

>         (vect_compute_data_ref_alignment): Adjust base_addr and aligned_to

>         for nested statements even if we fail to compute a misalignment.

>         Use pooled base alignments for unconditional references.

>         (vect_find_same_alignment_drs): Compare base addresses instead

>         of base objects.

>         (vect_analyze_data_refs_alignment): Call vect_record_base_alignments.

>         * tree-vect-slp.c (vect_slp_analyze_bb_1): Likewise.

>

> gcc/testsuite/

>         PR tree-optimization/81136

>         * gcc.dg/vect/pr81136.c: Add scan test.

>

> Index: gcc/tree-vectorizer.h

> ===================================================================

> --- gcc/tree-vectorizer.h       2017-07-27 13:46:58.376642483 +0100

> +++ gcc/tree-vectorizer.h       2017-07-27 13:46:58.579633332 +0100

> @@ -22,6 +22,7 @@ Software Foundation; either version 3, o

>  #define GCC_TREE_VECTORIZER_H

>

>  #include "tree-data-ref.h"

> +#include "tree-hash-traits.h"

>  #include "target.h"

>

>  /* Used for naming of new temporaries.  */

> @@ -84,6 +85,11 @@ struct stmt_info_for_cost {

>

>  typedef vec<stmt_info_for_cost> stmt_vector_for_cost;

>

> +/* Maps base addresses to an innermost_loop_behavior that gives the maximum

> +   known alignment for that base.  */

> +typedef hash_map<tree_operand_hash,

> +                innermost_loop_behavior *> vec_base_alignments;

> +

>  /************************************************************************

>    SLP

>   ************************************************************************/

> @@ -169,6 +175,10 @@ struct vec_info {

>    /* All data references.  Freed by free_data_refs, so not an auto_vec.  */

>    vec<data_reference_p> datarefs;

>

> +  /* Maps base addresses to an innermost_loop_behavior that gives the maximum

> +     known alignment for that base.  */

> +  vec_base_alignments base_alignments;

> +

>    /* All data dependences.  Freed by free_dependence_relations, so not

>       an auto_vec.  */

>    vec<ddr_p> ddrs;

> @@ -1162,6 +1172,7 @@ extern bool vect_prune_runtime_alias_tes

>  extern bool vect_check_gather_scatter (gimple *, loop_vec_info,

>                                        gather_scatter_info *);

>  extern bool vect_analyze_data_refs (vec_info *, int *);

> +extern void vect_record_base_alignments (vec_info *);

>  extern tree vect_create_data_ref_ptr (gimple *, tree, struct loop *, tree,

>                                       tree *, gimple_stmt_iterator *,

>                                       gimple **, bool, bool *,

> Index: gcc/tree-data-ref.h

> ===================================================================

> --- gcc/tree-data-ref.h 2017-07-27 13:46:58.376642483 +0100

> +++ gcc/tree-data-ref.h 2017-07-27 13:46:58.578633377 +0100

> @@ -159,6 +159,11 @@ struct data_reference

>    /* True when the data reference is in RHS of a stmt.  */

>    bool is_read;

>

> +  /* True when the data reference is conditional within STMT,

> +     i.e. if it might not occur even when the statement is executed

> +     and runs to completion.  */

> +  bool is_conditional_in_stmt;

> +

>    /* Behavior of the memory reference in the innermost loop.  */

>    struct innermost_loop_behavior innermost;

>

> @@ -178,6 +183,7 @@ #define DR_ACCESS_FN(DR, I)        DR_AC

>  #define DR_NUM_DIMENSIONS(DR)      DR_ACCESS_FNS (DR).length ()

>  #define DR_IS_READ(DR)             (DR)->is_read

>  #define DR_IS_WRITE(DR)            (!DR_IS_READ (DR))

> +#define DR_IS_CONDITIONAL_IN_STMT(DR) (DR)->is_conditional_in_stmt

>  #define DR_BASE_ADDRESS(DR)        (DR)->innermost.base_address

>  #define DR_OFFSET(DR)              (DR)->innermost.offset

>  #define DR_INIT(DR)                (DR)->innermost.init

> @@ -434,7 +440,8 @@ extern bool graphite_find_data_reference

>                                                    vec<data_reference_p> *);

>  tree find_data_references_in_loop (struct loop *, vec<data_reference_p> *);

>  bool loop_nest_has_data_refs (loop_p loop);

> -struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple *, bool);

> +struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple *, bool,

> +                                       bool);

>  extern bool find_loop_nest (struct loop *, vec<loop_p> *);

>  extern struct data_dependence_relation *initialize_data_dependence_relation

>       (struct data_reference *, struct data_reference *, vec<loop_p>);

> Index: gcc/tree-data-ref.c

> ===================================================================

> --- gcc/tree-data-ref.c 2017-07-27 13:46:58.376642483 +0100

> +++ gcc/tree-data-ref.c 2017-07-27 13:46:58.577633422 +0100

> @@ -1125,15 +1125,19 @@ free_data_ref (data_reference_p dr)

>    free (dr);

>  }

>

> -/* Analyzes memory reference MEMREF accessed in STMT.  The reference

> -   is read if IS_READ is true, write otherwise.  Returns the

> -   data_reference description of MEMREF.  NEST is the outermost loop

> -   in which the reference should be instantiated, LOOP is the loop in

> -   which the data reference should be analyzed.  */

> +/* Analyze memory reference MEMREF, which is accessed in STMT.

> +   The reference is a read if IS_READ is true, otherwise it is a write.

> +   IS_CONDITIONAL_IN_STMT indicates that the reference is conditional

> +   within STMT, i.e. that it might not occur even if STMT is executed

> +   and runs to completion.

> +

> +   Return the data_reference description of MEMREF.  NEST is the outermost

> +   loop in which the reference should be instantiated, LOOP is the loop

> +   in which the data reference should be analyzed.  */

>

>  struct data_reference *

>  create_data_ref (loop_p nest, loop_p loop, tree memref, gimple *stmt,

> -                bool is_read)

> +                bool is_read, bool is_conditional_in_stmt)

>  {

>    struct data_reference *dr;

>

> @@ -1148,6 +1152,7 @@ create_data_ref (loop_p nest, loop_p loo

>    DR_STMT (dr) = stmt;

>    DR_REF (dr) = memref;

>    DR_IS_READ (dr) = is_read;

> +  DR_IS_CONDITIONAL_IN_STMT (dr) = is_conditional_in_stmt;

>

>    dr_analyze_innermost (&DR_INNERMOST (dr), memref,

>                         nest != NULL ? loop : NULL);

> @@ -4774,6 +4779,11 @@ struct data_ref_loc

>

>    /* True if the memory reference is read.  */

>    bool is_read;

> +

> +  /* True if the data reference is conditional within the containing

> +     statement, i.e. if it might not occur even when the statement

> +     is executed and runs to completion.  */

> +  bool is_conditional_in_stmt;

>  };

>

>

> @@ -4840,6 +4850,7 @@ get_references_in_stmt (gimple *stmt, ve

>         {

>           ref.ref = op1;

>           ref.is_read = true;

> +         ref.is_conditional_in_stmt = false;

>           references->safe_push (ref);

>         }

>      }

> @@ -4867,6 +4878,7 @@ get_references_in_stmt (gimple *stmt, ve

>               type = TREE_TYPE (gimple_call_arg (stmt, 3));

>             if (TYPE_ALIGN (type) != align)

>               type = build_aligned_type (type, align);

> +           ref.is_conditional_in_stmt = true;

>             ref.ref = fold_build2 (MEM_REF, type, gimple_call_arg (stmt, 0),

>                                    ptr);

>             references->safe_push (ref);

> @@ -4886,6 +4898,7 @@ get_references_in_stmt (gimple *stmt, ve

>             {

>               ref.ref = op1;

>               ref.is_read = true;

> +             ref.is_conditional_in_stmt = false;

>               references->safe_push (ref);

>             }

>         }

> @@ -4899,6 +4912,7 @@ get_references_in_stmt (gimple *stmt, ve

>      {

>        ref.ref = op0;

>        ref.is_read = false;

> +      ref.is_conditional_in_stmt = false;

>        references->safe_push (ref);

>      }

>    return clobbers_memory;

> @@ -4963,8 +4977,8 @@ find_data_references_in_stmt (struct loo

>

>    FOR_EACH_VEC_ELT (references, i, ref)

>      {

> -      dr = create_data_ref (nest, loop_containing_stmt (stmt),

> -                           ref->ref, stmt, ref->is_read);

> +      dr = create_data_ref (nest, loop_containing_stmt (stmt), ref->ref,

> +                           stmt, ref->is_read, ref->is_conditional_in_stmt);

>        gcc_assert (dr != NULL);

>        datarefs->safe_push (dr);

>      }

> @@ -4993,7 +5007,8 @@ graphite_find_data_references_in_stmt (l

>

>    FOR_EACH_VEC_ELT (references, i, ref)

>      {

> -      dr = create_data_ref (nest, loop, ref->ref, stmt, ref->is_read);

> +      dr = create_data_ref (nest, loop, ref->ref, stmt, ref->is_read,

> +                           ref->is_conditional_in_stmt);

>        gcc_assert (dr != NULL);

>        datarefs->safe_push (dr);

>      }

> Index: gcc/tree-ssa-loop-prefetch.c

> ===================================================================

> --- gcc/tree-ssa-loop-prefetch.c        2017-07-27 13:46:58.376642483 +0100

> +++ gcc/tree-ssa-loop-prefetch.c        2017-07-27 13:46:58.578633377 +0100

> @@ -1633,7 +1633,7 @@ determine_loop_nest_reuse (struct loop *

>      for (ref = gr->refs; ref; ref = ref->next)

>        {

>         dr = create_data_ref (nest, loop_containing_stmt (ref->stmt),

> -                             ref->mem, ref->stmt, !ref->write_p);

> +                             ref->mem, ref->stmt, !ref->write_p, false);

>

>         if (dr)

>           {

> Index: gcc/tree-vect-data-refs.c

> ===================================================================

> --- gcc/tree-vect-data-refs.c   2017-07-27 13:46:58.376642483 +0100

> +++ gcc/tree-vect-data-refs.c   2017-07-27 13:46:58.579633332 +0100

> @@ -708,6 +708,69 @@ vect_slp_analyze_instance_dependence (sl

>    return res;

>  }

>

> +/* Record in VINFO the base alignment guarantee given by DRB.  STMT is

> +   the statement that contains DRB, which is useful for recording in the

> +   dump file.  */

> +

> +static void

> +vect_record_base_alignment (vec_info *vinfo, gimple *stmt,

> +                           innermost_loop_behavior *drb)

> +{

> +  bool existed;

> +  innermost_loop_behavior *&entry

> +    = vinfo->base_alignments.get_or_insert (drb->base_address, &existed);

> +  if (!existed || entry->base_alignment < drb->base_alignment)

> +    {

> +      entry = drb;

> +      if (dump_enabled_p ())

> +       {

> +         dump_printf_loc (MSG_NOTE, vect_location,

> +                          "recording new base alignment for ");

> +         dump_generic_expr (MSG_NOTE, TDF_SLIM, drb->base_address);

> +         dump_printf (MSG_NOTE, "\n");

> +         dump_printf_loc (MSG_NOTE, vect_location,

> +                          "  alignment:    %d\n", drb->base_alignment);

> +         dump_printf_loc (MSG_NOTE, vect_location,

> +                          "  misalignment: %d\n", drb->base_misalignment);

> +         dump_printf_loc (MSG_NOTE, vect_location,

> +                          "  based on:     ");

> +         dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);

> +       }

> +    }

> +}

> +

> +/* If the region we're going to vectorize is reached, all unconditional

> +   data references occur at least once.  We can therefore pool the base

> +   alignment guarantees from each unconditional reference.  Do this by

> +   going through all the data references in VINFO and checking whether

> +   the containing statement makes the reference unconditionally.  If so,

> +   record the alignment of the base address in VINFO so that it can be

> +   used for all other references with the same base.  */

> +

> +void

> +vect_record_base_alignments (vec_info *vinfo)

> +{

> +  loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo);

> +  struct loop *loop = loop_vinfo ? LOOP_VINFO_LOOP (loop_vinfo) : NULL;

> +  data_reference *dr;

> +  unsigned int i;

> +  FOR_EACH_VEC_ELT (vinfo->datarefs, i, dr)

> +    if (!DR_IS_CONDITIONAL_IN_STMT (dr))

> +      {

> +       gimple *stmt = DR_STMT (dr);

> +       vect_record_base_alignment (vinfo, stmt, &DR_INNERMOST (dr));

> +

> +       /* If DR is nested in the loop that is being vectorized, we can also

> +          record the alignment of the base wrt the outer loop.  */

> +       if (loop && nested_in_vect_loop_p (loop, stmt))

> +         {

> +           stmt_vec_info stmt_info = vinfo_for_stmt (stmt);

> +           vect_record_base_alignment

> +             (vinfo, stmt, &STMT_VINFO_DR_WRT_VEC_LOOP (stmt_info));

> +         }

> +      }

> +}

> +

>  /* Function vect_compute_data_ref_alignment

>

>     Compute the misalignment of the data reference DR.

> @@ -725,6 +788,7 @@ vect_compute_data_ref_alignment (struct

>  {

>    gimple *stmt = DR_STMT (dr);

>    stmt_vec_info stmt_info = vinfo_for_stmt (stmt);

> +  vec_base_alignments *base_alignments = &stmt_info->vinfo->base_alignments;

>    loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);

>    struct loop *loop = NULL;

>    tree ref = DR_REF (dr);

> @@ -793,6 +857,15 @@ vect_compute_data_ref_alignment (struct

>    unsigned int base_misalignment = drb->base_misalignment;

>    unsigned HOST_WIDE_INT vector_alignment = TYPE_ALIGN_UNIT (vectype);

>

> +  /* Calculate the maximum of the pooled base address alignment and the

> +     alignment that we can compute for DR itself.  */

> +  innermost_loop_behavior **entry = base_alignments->get (drb->base_address);

> +  if (entry && base_alignment < (*entry)->base_alignment)

> +    {

> +      base_alignment = (*entry)->base_alignment;

> +      base_misalignment = (*entry)->base_misalignment;

> +    }

> +

>    if (drb->offset_alignment < vector_alignment

>        || !step_preserves_misalignment_p

>        /* We need to know whether the step wrt the vectorized loop is

> @@ -2113,8 +2186,7 @@ vect_find_same_alignment_drs (struct dat

>    if (dra == drb)

>      return;

>

> -  if (!operand_equal_p (DR_BASE_OBJECT (dra), DR_BASE_OBJECT (drb),

> -                       OEP_ADDRESS_OF)

> +  if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)

>        || !operand_equal_p (DR_OFFSET (dra), DR_OFFSET (drb), 0)

>        || !operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))

>      return;

> @@ -2172,6 +2244,7 @@ vect_analyze_data_refs_alignment (loop_v

>    vec<data_reference_p> datarefs = vinfo->datarefs;

>    struct data_reference *dr;

>

> +  vect_record_base_alignments (vinfo);

>    FOR_EACH_VEC_ELT (datarefs, i, dr)

>      {

>        stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr));

> @@ -3437,7 +3510,8 @@ vect_analyze_data_refs (vec_info *vinfo,

>             {

>               struct data_reference *newdr

>                 = create_data_ref (NULL, loop_containing_stmt (stmt),

> -                                  DR_REF (dr), stmt, maybe_scatter ? false : true);

> +                                  DR_REF (dr), stmt, !maybe_scatter,

> +                                  DR_IS_CONDITIONAL_IN_STMT (dr));

>               gcc_assert (newdr != NULL && DR_REF (newdr));

>               if (DR_BASE_ADDRESS (newdr)

>                   && DR_OFFSET (newdr)

> Index: gcc/tree-vect-slp.c

> ===================================================================

> --- gcc/tree-vect-slp.c 2017-07-27 13:46:58.376642483 +0100

> +++ gcc/tree-vect-slp.c 2017-07-27 13:46:58.579633332 +0100

> @@ -2764,6 +2764,8 @@ vect_slp_analyze_bb_1 (gimple_stmt_itera

>        return NULL;

>      }

>

> +  vect_record_base_alignments (bb_vinfo);

> +

>    /* Analyze and verify the alignment of data references and the

>       dependence in the SLP instances.  */

>    for (i = 0; BB_VINFO_SLP_INSTANCES (bb_vinfo).iterate (i, &instance); )

> Index: gcc/testsuite/gcc.dg/vect/pr81136.c

> ===================================================================

> --- gcc/testsuite/gcc.dg/vect/pr81136.c 2017-07-27 13:46:58.376642483 +0100

> +++ gcc/testsuite/gcc.dg/vect/pr81136.c 2017-07-27 13:46:58.577633422 +0100

> @@ -14,3 +14,5 @@ fn1 (int n)

>    for (int i = 0; i < n; i++)

>      a->bar[i] = b[i];

>  }

> +

> +/* { dg-final { scan-tree-dump-not "Unknown misalignment" "vect" } } */

Patch

Index: gcc/tree-vectorizer.h
===================================================================
--- gcc/tree-vectorizer.h	2017-07-03 08:42:50.186422191 +0100
+++ gcc/tree-vectorizer.h	2017-07-03 08:45:24.571165851 +0100
@@ -22,6 +22,7 @@  Software Foundation; either version 3, o
 #define GCC_TREE_VECTORIZER_H
 
 #include "tree-data-ref.h"
+#include "tree-hash-traits.h"
 #include "target.h"
 
 /* Used for naming of new temporaries.  */
@@ -84,6 +85,11 @@  struct stmt_info_for_cost {
 
 typedef vec<stmt_info_for_cost> stmt_vector_for_cost;
 
+/* Maps base addresses to an innermost_loop_behavior that gives the maximum
+   known alignment for that base.  */
+typedef hash_map<tree_operand_hash,
+		 innermost_loop_behavior *> vec_base_alignments;
+
 /************************************************************************
   SLP
  ************************************************************************/
@@ -156,6 +162,10 @@  struct vec_info {
   /* All data references.  */
   vec<data_reference_p> datarefs;
 
+  /* Maps base addresses to an innermost_loop_behavior that gives the maximum
+     known alignment for that base.  */
+  vec_base_alignments base_alignments;
+
   /* All data dependences.  */
   vec<ddr_p> ddrs;
 
@@ -1132,6 +1142,7 @@  extern bool vect_prune_runtime_alias_tes
 extern bool vect_check_gather_scatter (gimple *, loop_vec_info,
 				       gather_scatter_info *);
 extern bool vect_analyze_data_refs (vec_info *, int *);
+extern void vect_record_base_alignments (vec_info *);
 extern tree vect_create_data_ref_ptr (gimple *, tree, struct loop *, tree,
 				      tree *, gimple_stmt_iterator *,
 				      gimple **, bool, bool *,
Index: gcc/tree-data-ref.h
===================================================================
--- gcc/tree-data-ref.h	2017-07-03 08:42:50.185422235 +0100
+++ gcc/tree-data-ref.h	2017-07-03 08:42:51.147380631 +0100
@@ -159,6 +159,11 @@  struct data_reference
   /* True when the data reference is in RHS of a stmt.  */
   bool is_read;
 
+  /* True when the data reference is conditional within STMT,
+     i.e. if it might not occur even when the statement is executed
+     and runs to completion.  */
+  bool is_conditional_in_stmt;
+
   /* Behavior of the memory reference in the innermost loop.  */
   struct innermost_loop_behavior innermost;
 
@@ -178,6 +183,7 @@  #define DR_ACCESS_FN(DR, I)        DR_AC
 #define DR_NUM_DIMENSIONS(DR)      DR_ACCESS_FNS (DR).length ()
 #define DR_IS_READ(DR)             (DR)->is_read
 #define DR_IS_WRITE(DR)            (!DR_IS_READ (DR))
+#define DR_IS_CONDITIONAL_IN_STMT(DR) (DR)->is_conditional_in_stmt
 #define DR_BASE_ADDRESS(DR)        (DR)->innermost.base_address
 #define DR_OFFSET(DR)              (DR)->innermost.offset
 #define DR_INIT(DR)                (DR)->innermost.init
@@ -393,7 +399,8 @@  extern bool graphite_find_data_reference
 						   vec<data_reference_p> *);
 tree find_data_references_in_loop (struct loop *, vec<data_reference_p> *);
 bool loop_nest_has_data_refs (loop_p loop);
-struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple *, bool);
+struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple *, bool,
+					bool);
 extern bool find_loop_nest (struct loop *, vec<loop_p> *);
 extern struct data_dependence_relation *initialize_data_dependence_relation
      (struct data_reference *, struct data_reference *, vec<loop_p>);
Index: gcc/tree-data-ref.c
===================================================================
--- gcc/tree-data-ref.c	2017-07-03 08:42:50.184422278 +0100
+++ gcc/tree-data-ref.c	2017-07-03 08:42:51.147380631 +0100
@@ -1087,15 +1087,19 @@  free_data_ref (data_reference_p dr)
   free (dr);
 }
 
-/* Analyzes memory reference MEMREF accessed in STMT.  The reference
-   is read if IS_READ is true, write otherwise.  Returns the
-   data_reference description of MEMREF.  NEST is the outermost loop
-   in which the reference should be instantiated, LOOP is the loop in
-   which the data reference should be analyzed.  */
+/* Analyze memory reference MEMREF, which is accessed in STMT.
+   The reference is a read if IS_READ is true, otherwise it is a write.
+   IS_CONDITIONAL_IN_STMT indicates that the reference is conditional
+   within STMT, i.e. that it might not occur even if STMT is executed
+   and runs to completion.
+
+   Return the data_reference description of MEMREF.  NEST is the outermost
+   loop in which the reference should be instantiated, LOOP is the loop
+   in which the data reference should be analyzed.  */
 
 struct data_reference *
 create_data_ref (loop_p nest, loop_p loop, tree memref, gimple *stmt,
-		 bool is_read)
+		 bool is_read, bool is_conditional_in_stmt)
 {
   struct data_reference *dr;
 
@@ -1110,6 +1114,7 @@  create_data_ref (loop_p nest, loop_p loo
   DR_STMT (dr) = stmt;
   DR_REF (dr) = memref;
   DR_IS_READ (dr) = is_read;
+  DR_IS_CONDITIONAL_IN_STMT (dr) = is_conditional_in_stmt;
 
   dr_analyze_innermost (dr, nest != NULL ? loop : NULL);
   dr_analyze_indices (dr, nest, loop);
@@ -4484,6 +4489,11 @@  struct data_ref_loc
 
   /* True if the memory reference is read.  */
   bool is_read;
+
+  /* True if the data reference is conditional within the containing
+     statement, i.e. if it might not occur even when the statement
+     is executed and runs to completion.  */
+  bool is_conditional_in_stmt;
 };
 
 
@@ -4550,6 +4560,7 @@  get_references_in_stmt (gimple *stmt, ve
 	{
 	  ref.ref = op1;
 	  ref.is_read = true;
+	  ref.is_conditional_in_stmt = false;
 	  references->safe_push (ref);
 	}
     }
@@ -4577,6 +4588,7 @@  get_references_in_stmt (gimple *stmt, ve
 	      type = TREE_TYPE (gimple_call_arg (stmt, 3));
 	    if (TYPE_ALIGN (type) != align)
 	      type = build_aligned_type (type, align);
+	    ref.is_conditional_in_stmt = true;
 	    ref.ref = fold_build2 (MEM_REF, type, gimple_call_arg (stmt, 0),
 				   ptr);
 	    references->safe_push (ref);
@@ -4596,6 +4608,7 @@  get_references_in_stmt (gimple *stmt, ve
 	    {
 	      ref.ref = op1;
 	      ref.is_read = true;
+	      ref.is_conditional_in_stmt = false;
 	      references->safe_push (ref);
 	    }
 	}
@@ -4609,6 +4622,7 @@  get_references_in_stmt (gimple *stmt, ve
     {
       ref.ref = op0;
       ref.is_read = false;
+      ref.is_conditional_in_stmt = false;
       references->safe_push (ref);
     }
   return clobbers_memory;
@@ -4673,8 +4687,8 @@  find_data_references_in_stmt (struct loo
 
   FOR_EACH_VEC_ELT (references, i, ref)
     {
-      dr = create_data_ref (nest, loop_containing_stmt (stmt),
-			    ref->ref, stmt, ref->is_read);
+      dr = create_data_ref (nest, loop_containing_stmt (stmt), ref->ref,
+			    stmt, ref->is_read, ref->is_conditional_in_stmt);
       gcc_assert (dr != NULL);
       datarefs->safe_push (dr);
     }
@@ -4703,7 +4717,8 @@  graphite_find_data_references_in_stmt (l
 
   FOR_EACH_VEC_ELT (references, i, ref)
     {
-      dr = create_data_ref (nest, loop, ref->ref, stmt, ref->is_read);
+      dr = create_data_ref (nest, loop, ref->ref, stmt, ref->is_read,
+			    ref->is_conditional_in_stmt);
       gcc_assert (dr != NULL);
       datarefs->safe_push (dr);
     }
Index: gcc/tree-ssa-loop-prefetch.c
===================================================================
--- gcc/tree-ssa-loop-prefetch.c	2017-07-03 08:20:56.404763323 +0100
+++ gcc/tree-ssa-loop-prefetch.c	2017-07-03 08:42:51.147380631 +0100
@@ -1633,7 +1633,7 @@  determine_loop_nest_reuse (struct loop *
     for (ref = gr->refs; ref; ref = ref->next)
       {
 	dr = create_data_ref (nest, loop_containing_stmt (ref->stmt),
-			      ref->mem, ref->stmt, !ref->write_p);
+			      ref->mem, ref->stmt, !ref->write_p, false);
 
 	if (dr)
 	  {
Index: gcc/tree-vect-data-refs.c
===================================================================
--- gcc/tree-vect-data-refs.c	2017-07-03 08:42:50.185422235 +0100
+++ gcc/tree-vect-data-refs.c	2017-07-03 08:47:16.424712986 +0100
@@ -647,6 +647,69 @@  vect_slp_analyze_instance_dependence (sl
   return res;
 }
 
+/* Record in VINFO the base alignment guarantee given by DRB.  STMT is
+   the statement that contains DRB, which is useful for recording in the
+   dump file.  */
+
+static void
+vect_record_base_alignment (vec_info *vinfo, gimple *stmt,
+			    innermost_loop_behavior *drb)
+{
+  bool existed;
+  innermost_loop_behavior *&entry
+    = vinfo->base_alignments.get_or_insert (drb->base_address, &existed);
+  if (!existed || entry->base_alignment < drb->base_alignment)
+    {
+      entry = drb;
+      if (dump_enabled_p ())
+	{
+	  dump_printf_loc (MSG_NOTE, vect_location,
+			   "recording new base alignment for ");
+	  dump_generic_expr (MSG_NOTE, TDF_SLIM, drb->base_address);
+	  dump_printf (MSG_NOTE, "\n");
+	  dump_printf_loc (MSG_NOTE, vect_location,
+			   "  alignment:    %d\n", drb->base_alignment);
+	  dump_printf_loc (MSG_NOTE, vect_location,
+			   "  misalignment: %d\n", drb->base_misalignment);
+	  dump_printf_loc (MSG_NOTE, vect_location,
+			   "  based on:     ");
+	  dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
+	}
+    }
+}
+
+/* If the region we're going to vectorize is reached, all unconditional
+   data references occur at least once.  We can therefore pool the base
+   alignment guarantees from each unconditional reference.  Do this by
+   going through all the data references in VINFO and checking whether
+   the containing statement makes the reference unconditionally.  If so,
+   record the alignment of the base address in VINFO so that it can be
+   used for all other references with the same base.  */
+
+void
+vect_record_base_alignments (vec_info *vinfo)
+{
+  loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo);
+  struct loop *loop = loop_vinfo ? LOOP_VINFO_LOOP (loop_vinfo) : NULL;
+  data_reference *dr;
+  unsigned int i;
+  FOR_EACH_VEC_ELT (vinfo->datarefs, i, dr)
+    if (!DR_IS_CONDITIONAL_IN_STMT (dr))
+      {
+	gimple *stmt = DR_STMT (dr);
+	vect_record_base_alignment (vinfo, stmt, &DR_INNERMOST (dr));
+
+	/* If DR is nested in the loop that is being vectorized, we can also
+	   record the alignment of the base wrt the outer loop.  */
+	if (loop && nested_in_vect_loop_p (loop, stmt))
+	  {
+	    stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
+	    vect_record_base_alignment
+	      (vinfo, stmt, &STMT_VINFO_DR_WRT_VEC_LOOP (stmt_info));
+	  }
+      }
+}
+
 /* Function vect_compute_data_ref_alignment
 
    Compute the misalignment of the data reference DR.
@@ -664,6 +727,7 @@  vect_compute_data_ref_alignment (struct
 {
   gimple *stmt = DR_STMT (dr);
   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
+  vec_base_alignments *base_alignments = &stmt_info->vinfo->base_alignments;
   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
   struct loop *loop = NULL;
   tree ref = DR_REF (dr);
@@ -732,6 +796,15 @@  vect_compute_data_ref_alignment (struct
   unsigned int base_misalignment = drb->base_misalignment;
   unsigned HOST_WIDE_INT vector_alignment = TYPE_ALIGN_UNIT (vectype);
 
+  /* Calculate the maximum of the pooled base address alignment and the
+     alignment that we can compute for DR itself.  */
+  innermost_loop_behavior **entry = base_alignments->get (drb->base_address);
+  if (entry && base_alignment < (*entry)->base_alignment)
+    {
+      base_alignment = (*entry)->base_alignment;
+      base_misalignment = (*entry)->base_misalignment;
+    }
+
   if (drb->offset_alignment < vector_alignment
       || !step_preserves_misalignment_p
       /* We need to know whether the step wrt the vectorized loop is
@@ -2070,8 +2143,7 @@  vect_find_same_alignment_drs (struct dat
   if (dra == drb)
     return;
 
-  if (!operand_equal_p (DR_BASE_OBJECT (dra), DR_BASE_OBJECT (drb),
-			OEP_ADDRESS_OF)
+  if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)
       || !operand_equal_p (DR_OFFSET (dra), DR_OFFSET (drb), 0)
       || !operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))
     return;
@@ -2129,6 +2201,7 @@  vect_analyze_data_refs_alignment (loop_v
   vec<data_reference_p> datarefs = vinfo->datarefs;
   struct data_reference *dr;
 
+  vect_record_base_alignments (vinfo);
   FOR_EACH_VEC_ELT (datarefs, i, dr)
     {
       stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr));
@@ -3327,7 +3400,8 @@  vect_analyze_data_refs (vec_info *vinfo,
 	    {
 	      struct data_reference *newdr
 		= create_data_ref (NULL, loop_containing_stmt (stmt),
-				   DR_REF (dr), stmt, maybe_scatter ? false : true);
+				   DR_REF (dr), stmt, !maybe_scatter,
+				   DR_IS_CONDITIONAL_IN_STMT (dr));
 	      gcc_assert (newdr != NULL && DR_REF (newdr));
 	      if (DR_BASE_ADDRESS (newdr)
 		  && DR_OFFSET (newdr)
Index: gcc/tree-vect-slp.c
===================================================================
--- gcc/tree-vect-slp.c	2017-07-03 08:20:56.404763323 +0100
+++ gcc/tree-vect-slp.c	2017-07-03 08:42:51.149380545 +0100
@@ -2358,6 +2358,7 @@  new_bb_vec_info (gimple_stmt_iterator re
   gimple_stmt_iterator gsi;
 
   res = (bb_vec_info) xcalloc (1, sizeof (struct _bb_vec_info));
+  new (&res->base_alignments) vec_base_alignments ();
   res->kind = vec_info::bb;
   BB_VINFO_BB (res) = bb;
   res->region_begin = region_begin;
@@ -2773,6 +2774,8 @@  vect_slp_analyze_bb_1 (gimple_stmt_itera
       return NULL;
     }
 
+  vect_record_base_alignments (bb_vinfo);
+
   /* Analyze and verify the alignment of data references and the
      dependence in the SLP instances.  */
   for (i = 0; BB_VINFO_SLP_INSTANCES (bb_vinfo).iterate (i, &instance); )
Index: gcc/tree-vect-loop.c
===================================================================
--- gcc/tree-vect-loop.c	2017-07-03 08:20:56.404763323 +0100
+++ gcc/tree-vect-loop.c	2017-07-03 08:42:51.149380545 +0100
@@ -1159,6 +1159,7 @@  new_loop_vec_info (struct loop *loop)
   LOOP_VINFO_VECT_FACTOR (res) = 0;
   LOOP_VINFO_LOOP_NEST (res) = vNULL;
   LOOP_VINFO_DATAREFS (res) = vNULL;
+  new (&res->base_alignments) vec_base_alignments ();
   LOOP_VINFO_DDRS (res) = vNULL;
   LOOP_VINFO_UNALIGNED_DR (res) = NULL;
   LOOP_VINFO_MAY_MISALIGN_STMTS (res) = vNULL;
Index: gcc/tree-vectorizer.c
===================================================================
--- gcc/tree-vectorizer.c	2017-07-03 08:20:56.404763323 +0100
+++ gcc/tree-vectorizer.c	2017-07-03 08:42:51.149380545 +0100
@@ -370,6 +370,8 @@  vect_destroy_datarefs (vec_info *vinfo)
       }
 
   free_data_refs (vinfo->datarefs);
+
+  vinfo->base_alignments.~vec_base_alignments ();
 }
 
 /* A helper function to free scev and LOOP niter information, as well as
Index: gcc/testsuite/gcc.dg/vect/pr81136.c
===================================================================
--- gcc/testsuite/gcc.dg/vect/pr81136.c	2017-07-03 08:20:56.404763323 +0100
+++ gcc/testsuite/gcc.dg/vect/pr81136.c	2017-07-03 08:42:51.144380761 +0100
@@ -14,3 +14,5 @@  fn1 (int n)
   for (int i = 0; i < n; i++)
     a->bar[i] = b[i];
 }
+
+/* { dg-final { scan-tree-dump-not "Unknown misalignment" "vect" } } */