[7/7] Pool alignment information for common bases
Richard Biener
richard.guenther@gmail.com
Tue Jul 4 11:30:00 GMT 2017
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" } } */
More information about the Gcc-patches
mailing list