[3/8] Add flags to dr_with_seg_len_pair_t

This patch adds a bunch of flags to dr_with_seg_len_pair_t,
for use by later patches.  The update to tree-loop-distribution.c
is conservatively correct, but might be tweakable later.


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

gcc/
	* tree-data-ref.h (DR_ALIAS_RAW, DR_ALIAS_WAR, DR_ALIAS_WAW)
	(DR_ALIAS_ARBITRARY, DR_ALIAS_SWAPPED, DR_ALIAS_UNSWAPPED): New flags.
	(dr_with_seg_len_pair_t::sequencing): New enum.
	(dr_with_seg_len_pair_t::flags): New member variable.
	(dr_with_seg_len_pair_t::dr_with_seg_len_pair_t): Take a sequencing
	parameter and initialize the flags member variable.
	* tree-loop-distribution.c (compute_alias_check_pairs): Update
	call accordingly.
	* tree-vect-data-refs.c (vect_prune_runtime_alias_test_list): Likewise.
	Ensure the two data references in an alias pair are in statement
	order, if there is a defined order.
	* tree-data-ref.c (prune_runtime_alias_test_list): Use
	DR_ALIAS_SWAPPED and DR_ALIAS_UNSWAPPED to record whether we've
	swapped the references in a dr_with_seg_len_pair_t.  OR together
	the flags when merging two dr_with_seg_len_pair_ts.  After merging,
	try to restore the original dr_with_seg_len order, updating the
	flags if that fails.

On Mon, Nov 11, 2019 at 7:47 PM Richard Sandiford
<richard.sandiford@arm.com> wrote:
>
> This patch adds a bunch of flags to dr_with_seg_len_pair_t,
> for use by later patches.  The update to tree-loop-distribution.c
> is conservatively correct, but might be tweakable later.

Does this all work with interleaved SLP loads/stores like

  a[i] = b[i];
  tem1 = b[i+1];
  tem2 = b[i+2];
  a[i+2] = tem2;
  a[i+1] = tem1;

where we don't preserve the scalar order but emit code at the
latest stmt of the grouped access?  That is, what does
"preserve scalar oder" actually mean?


> 2019-11-11  Richard Sandiford  <richard.sandiford@arm.com>
>
> gcc/
>         * tree-data-ref.h (DR_ALIAS_RAW, DR_ALIAS_WAR, DR_ALIAS_WAW)
>         (DR_ALIAS_ARBITRARY, DR_ALIAS_SWAPPED, DR_ALIAS_UNSWAPPED): New flags.
>         (dr_with_seg_len_pair_t::sequencing): New enum.
>         (dr_with_seg_len_pair_t::flags): New member variable.
>         (dr_with_seg_len_pair_t::dr_with_seg_len_pair_t): Take a sequencing
>         parameter and initialize the flags member variable.
>         * tree-loop-distribution.c (compute_alias_check_pairs): Update
>         call accordingly.
>         * tree-vect-data-refs.c (vect_prune_runtime_alias_test_list): Likewise.
>         Ensure the two data references in an alias pair are in statement
>         order, if there is a defined order.
>         * tree-data-ref.c (prune_runtime_alias_test_list): Use
>         DR_ALIAS_SWAPPED and DR_ALIAS_UNSWAPPED to record whether we've
>         swapped the references in a dr_with_seg_len_pair_t.  OR together
>         the flags when merging two dr_with_seg_len_pair_ts.  After merging,
>         try to restore the original dr_with_seg_len order, updating the
>         flags if that fails.
>
> Index: gcc/tree-data-ref.h
> ===================================================================
> --- gcc/tree-data-ref.h 2019-07-10 19:41:26.383898124 +0100
> +++ gcc/tree-data-ref.h 2019-11-11 18:30:50.527193443 +0000
> @@ -222,20 +222,107 @@ typedef struct data_reference *data_refe
>    unsigned int align;
>  };
>
> +/* Flags that describe a potential alias between two dr_with_seg_lens.
> +   In general, each pair of dr_with_seg_lens represents a composite of
> +   multiple access pairs P, so testing flags like DR_IS_READ on the DRs
> +   does not give meaningful information.
> +
> +   DR_ALIAS_RAW:
> +       There is a pair in P for which the second reference is a read
> +       and the first is a write.
> +
> +   DR_ALIAS_WAR:
> +       There is a pair in P for which the second reference is a write
> +       and the first is a read.
> +
> +   DR_ALIAS_WAW:
> +       There is a pair in P for which both references are writes.
> +
> +   DR_ALIAS_ARBITRARY:
> +       Either
> +       (a) it isn't possible to classify one pair in P as RAW, WAW or WAR; or
> +       (b) there is a pair in P that breaks the ordering assumption below.
> +
> +       This flag overrides the RAW, WAR and WAW flags above.
> +
> +   DR_ALIAS_UNSWAPPED:
> +   DR_ALIAS_SWAPPED:
> +       Temporary flags that indicate whether there is a pair P whose
> +       DRs have or haven't been swapped around.
> +
> +   The ordering assumption mentioned above is that for every pair
> +   (DR_A, DR_B) in P:
> +
> +   (1) The original code accesses n elements for DR_A and n elements for DR_B,
> +       interleaved as follows:
> +
> +        one access of size DR_A.access_size at DR_A.dr
> +        one access of size DR_B.access_size at DR_B.dr
> +        one access of size DR_A.access_size at DR_A.dr + STEP_A
> +        one access of size DR_B.access_size at DR_B.dr + STEP_B
> +        one access of size DR_A.access_size at DR_A.dr + STEP_A * 2
> +        one access of size DR_B.access_size at DR_B.dr + STEP_B * 2
> +        ...
> +
> +   (2) The new code accesses the same data in exactly two chunks:
> +
> +        one group of accesses spanning |DR_A.seg_len| + DR_A.access_size
> +        one group of accesses spanning |DR_B.seg_len| + DR_B.access_size
> +
> +   A pair might break this assumption if the DR_A and DR_B accesses
> +   in the original or the new code are mingled in some way.  For example,
> +   if DR_A.access_size represents the effect of two individual writes
> +   to nearby locations, the pair breaks the assumption if those writes
> +   occur either side of the access for DR_B.
> +
> +   Note that DR_ALIAS_ARBITRARY describes whether the ordering assumption
> +   fails to hold for any individual pair in P.  If the assumption *does*
> +   hold for every pair in P, it doesn't matter whether it holds for the
> +   composite pair or not.  In other words, P should represent the complete
> +   set of pairs that the composite pair is testing, so only the ordering
> +   of two accesses in the same member of P matters.  */
> +const unsigned int DR_ALIAS_RAW = 1U << 0;
> +const unsigned int DR_ALIAS_WAR = 1U << 1;
> +const unsigned int DR_ALIAS_WAW = 1U << 2;
> +const unsigned int DR_ALIAS_ARBITRARY = 1U << 3;
> +const unsigned int DR_ALIAS_SWAPPED = 1U << 4;
> +const unsigned int DR_ALIAS_UNSWAPPED = 1U << 5;
> +
>  /* This struct contains two dr_with_seg_len objects with aliasing data
>     refs.  Two comparisons are generated from them.  */
>
>  class dr_with_seg_len_pair_t
>  {
>  public:
> -  dr_with_seg_len_pair_t (const dr_with_seg_len& d1,
> -                              const dr_with_seg_len& d2)
> -    : first (d1), second (d2) {}
> +  /* WELL_ORDERED indicates that the ordering assumption described above
> +     DR_ALIAS_ARBITRARY holds.  REORDERED indicates that it doesn't.  */
> +  enum sequencing { WELL_ORDERED, REORDERED };
> +
> +  dr_with_seg_len_pair_t (const dr_with_seg_len &,
> +                         const dr_with_seg_len &, sequencing);
>
>    dr_with_seg_len first;
>    dr_with_seg_len second;
> +  unsigned int flags;
>  };
>
> +inline dr_with_seg_len_pair_t::
> +dr_with_seg_len_pair_t (const dr_with_seg_len &d1, const dr_with_seg_len &d2,
> +                       sequencing seq)
> +  : first (d1), second (d2), flags (0)
> +{
> +  if (DR_IS_READ (d1.dr) && DR_IS_WRITE (d2.dr))
> +    flags |= DR_ALIAS_WAR;
> +  else if (DR_IS_WRITE (d1.dr) && DR_IS_READ (d2.dr))
> +    flags |= DR_ALIAS_RAW;
> +  else if (DR_IS_WRITE (d1.dr) && DR_IS_WRITE (d2.dr))
> +    flags |= DR_ALIAS_WAW;
> +  else
> +    gcc_unreachable ();
> +  if (seq == REORDERED)
> +    flags |= DR_ALIAS_ARBITRARY;
> +}
> +
>  enum data_dependence_direction {
>    dir_positive,
>    dir_negative,
> Index: gcc/tree-loop-distribution.c
> ===================================================================
> --- gcc/tree-loop-distribution.c        2019-11-11 18:30:43.207244530 +0000
> +++ gcc/tree-loop-distribution.c        2019-11-11 18:30:50.527193443 +0000
> @@ -2477,7 +2477,9 @@ compute_alias_check_pairs (class loop *l
>
>        dr_with_seg_len_pair_t dr_with_seg_len_pair
>         (dr_with_seg_len (dr_a, seg_length_a, access_size_a, align_a),
> -        dr_with_seg_len (dr_b, seg_length_b, access_size_b, align_b));
> +        dr_with_seg_len (dr_b, seg_length_b, access_size_b, align_b),
> +        /* ??? Would WELL_ORDERED be safe?  */
> +        dr_with_seg_len_pair_t::REORDERED);
>
>        comp_alias_pairs->safe_push (dr_with_seg_len_pair);
>      }
> Index: gcc/tree-vect-data-refs.c
> ===================================================================
> --- gcc/tree-vect-data-refs.c   2019-11-11 18:30:43.207244530 +0000
> +++ gcc/tree-vect-data-refs.c   2019-11-11 18:30:50.531193415 +0000
> @@ -3509,10 +3509,13 @@ vect_prune_runtime_alias_test_list (loop
>        dr_vec_info *dr_info_b = loop_vinfo->lookup_dr (DDR_B (ddr));
>        stmt_vec_info stmt_info_b = dr_info_b->stmt;
>
> +      bool preserves_scalar_order_p
> +       = vect_preserves_scalar_order_p (dr_info_a, dr_info_b);
> +
>        /* Skip the pair if inter-iteration dependencies are irrelevant
>          and intra-iteration dependencies are guaranteed to be honored.  */
>        if (ignore_step_p
> -         && (vect_preserves_scalar_order_p (dr_info_a, dr_info_b)
> +         && (preserves_scalar_order_p
>               || vectorizable_with_step_bound_p (dr_info_a, dr_info_b,
>                                                  &lower_bound)))
>         {
> @@ -3630,11 +3633,21 @@ vect_prune_runtime_alias_test_list (loop
>                                            stmt_info_b->stmt);
>         }
>
> +      dr_with_seg_len dr_a (dr_info_a->dr, segment_length_a,
> +                           access_size_a, align_a);
> +      dr_with_seg_len dr_b (dr_info_b->dr, segment_length_b,
> +                           access_size_b, align_b);
> +      /* Canonicalize the order to be the one that's needed for accurate
> +        RAW, WAR and WAW flags, in cases where the data references are
> +        well-ordered.  The order doesn't really matter otherwise,
> +        but we might as well be consistent.  */
> +      if (get_later_stmt (stmt_info_a, stmt_info_b) == stmt_info_a)
> +       std::swap (dr_a, dr_b);
> +
>        dr_with_seg_len_pair_t dr_with_seg_len_pair
> -       (dr_with_seg_len (dr_info_a->dr, segment_length_a,
> -                         access_size_a, align_a),
> -        dr_with_seg_len (dr_info_b->dr, segment_length_b,
> -                         access_size_b, align_b));
> +       (dr_a, dr_b, (preserves_scalar_order_p
> +                     ? dr_with_seg_len_pair_t::WELL_ORDERED
> +                     : dr_with_seg_len_pair_t::REORDERED));
>
>        comp_alias_ddrs.safe_push (dr_with_seg_len_pair);
>      }
> Index: gcc/tree-data-ref.c
> ===================================================================
> --- gcc/tree-data-ref.c 2019-11-11 18:30:47.199216669 +0000
> +++ gcc/tree-data-ref.c 2019-11-11 18:30:50.527193443 +0000
> @@ -1503,7 +1503,12 @@ prune_runtime_alias_test_list (vec<dr_wi
>        if (comp_res == 0)
>         comp_res = data_ref_compare_tree (DR_INIT (dr_a), DR_INIT (dr_b));
>        if (comp_res > 0)
> -       std::swap (alias_pair->first, alias_pair->second);
> +       {
> +         std::swap (alias_pair->first, alias_pair->second);
> +         alias_pair->flags |= DR_ALIAS_SWAPPED;
> +       }
> +      else
> +       alias_pair->flags |= DR_ALIAS_UNSWAPPED;
>      }
>
>    /* Sort the collected data ref pairs so that we can scan them once to
> @@ -1515,10 +1520,13 @@ prune_runtime_alias_test_list (vec<dr_wi
>    for (i = 1; i < alias_pairs->length (); ++i)
>      {
>        /* Deal with two ddrs (dr_a1, dr_b1) and (dr_a2, dr_b2).  */
> -      dr_with_seg_len *dr_a1 = &(*alias_pairs)[i-1].first,
> -                     *dr_b1 = &(*alias_pairs)[i-1].second,
> -                     *dr_a2 = &(*alias_pairs)[i].first,
> -                     *dr_b2 = &(*alias_pairs)[i].second;
> +      dr_with_seg_len_pair_t *alias_pair1 = &(*alias_pairs)[i - 1];
> +      dr_with_seg_len_pair_t *alias_pair2 = &(*alias_pairs)[i];
> +
> +      dr_with_seg_len *dr_a1 = &alias_pair1->first;
> +      dr_with_seg_len *dr_b1 = &alias_pair1->second;
> +      dr_with_seg_len *dr_a2 = &alias_pair2->first;
> +      dr_with_seg_len *dr_b2 = &alias_pair2->second;
>
>        /* Remove duplicate data ref pairs.  */
>        if (*dr_a1 == *dr_a2 && *dr_b1 == *dr_b2)
> @@ -1527,6 +1535,7 @@ prune_runtime_alias_test_list (vec<dr_wi
>             dump_printf (MSG_NOTE, "found equal ranges %T, %T and %T, %T\n",
>                          DR_REF (dr_a1->dr), DR_REF (dr_b1->dr),
>                          DR_REF (dr_a2->dr), DR_REF (dr_b2->dr));
> +         alias_pair1->flags |= alias_pair2->flags;
>           alias_pairs->ordered_remove (i--);
>           continue;
>         }
> @@ -1632,10 +1641,26 @@ prune_runtime_alias_test_list (vec<dr_wi
>             dump_printf (MSG_NOTE, "merging ranges for %T, %T and %T, %T\n",
>                          DR_REF (dr_a1->dr), DR_REF (dr_b1->dr),
>                          DR_REF (dr_a2->dr), DR_REF (dr_b2->dr));
> +         alias_pair1->flags |= alias_pair2->flags;
>           alias_pairs->ordered_remove (i);
>           i--;
>         }
>      }
> +
> +  /* Try to restore the original dr_with_seg_len order within each
> +     dr_with_seg_len_pair_t.  If we ended up combining swapped and
> +     unswapped pairs into the same check, we have to invalidate any
> +     RAW, WAR and WAW information for it.  */
> +  FOR_EACH_VEC_ELT (*alias_pairs, i, alias_pair)
> +    {
> +      unsigned int swap_mask = (DR_ALIAS_SWAPPED | DR_ALIAS_UNSWAPPED);
> +      unsigned int swapped = (alias_pair->flags & swap_mask);
> +      if (swapped == DR_ALIAS_SWAPPED)
> +       std::swap (alias_pair->first, alias_pair->second);
> +      else if (swapped != DR_ALIAS_UNSWAPPED)
> +       alias_pair->flags |= DR_ALIAS_ARBITRARY;
> +      alias_pair->flags &= ~swap_mask;
> +    }
>  }
>
>  /* Given LOOP's two data references and segment lengths described by DR_A

Richard Biener <richard.guenther@gmail.com> writes:
> On Mon, Nov 11, 2019 at 7:47 PM Richard Sandiford
> <richard.sandiford@arm.com> wrote:
>>
>> This patch adds a bunch of flags to dr_with_seg_len_pair_t,
>> for use by later patches.  The update to tree-loop-distribution.c
>> is conservatively correct, but might be tweakable later.
>
> Does this all work with interleaved SLP loads/stores like
>
>   a[i] = b[i];
>   tem1 = b[i+1];
>   tem2 = b[i+2];
>   a[i+2] = tem2;
>   a[i+1] = tem1;
>
> where we don't preserve the scalar order but emit code at the
> latest stmt of the grouped access?

Yeah.  vect-alias-check-9.c is a less sophisticated example of that.
In both cases vect_preserves_scalar_order_p is false.

> That is, what does "preserve scalar oder" actually mean?

It's supposed to mean that if a memory access A from the first
group and a memory access B from the second group occur within
the same scalar iteration, the order of the accesses in the
vector loop body will be the same as it was in the scalar loop body.
In other words, the order of the vector stmts honours any dependencies
between the accesses that occur within one iteration of the scalar loop.

Thanks,
Richard

On Fri, Nov 15, 2019 at 12:33 PM Richard Sandiford
<richard.sandiford@arm.com> wrote:
>
> Richard Biener <richard.guenther@gmail.com> writes:
> > On Mon, Nov 11, 2019 at 7:47 PM Richard Sandiford
> > <richard.sandiford@arm.com> wrote:
> >>
> >> This patch adds a bunch of flags to dr_with_seg_len_pair_t,
> >> for use by later patches.  The update to tree-loop-distribution.c
> >> is conservatively correct, but might be tweakable later.
> >
> > Does this all work with interleaved SLP loads/stores like
> >
> >   a[i] = b[i];
> >   tem1 = b[i+1];
> >   tem2 = b[i+2];
> >   a[i+2] = tem2;
> >   a[i+1] = tem1;
> >
> > where we don't preserve the scalar order but emit code at the
> > latest stmt of the grouped access?
>
> Yeah.  vect-alias-check-9.c is a less sophisticated example of that.
> In both cases vect_preserves_scalar_order_p is false.
>
> > That is, what does "preserve scalar oder" actually mean?
>
> It's supposed to mean that if a memory access A from the first
> group and a memory access B from the second group occur within
> the same scalar iteration, the order of the accesses in the
> vector loop body will be the same as it was in the scalar loop body.
> In other words, the order of the vector stmts honours any dependencies
> between the accesses that occur within one iteration of the scalar loop.

OK, I see.  The patch is OK then.

Thanks,
Richard.

> Thanks,
> Richard