[4/8] Record whether a dr_with_seg_len contains mixed steps

prune_runtime_alias_test_list can merge dr_with_seg_len_pair_ts that
have different steps for the first reference or different steps for the
second reference.  This patch adds a flag to record that.

I don't know whether the change to create_intersect_range_checks_index
fixes anything in practice.  It would have to be a corner case if so,
since at present we only merge two alias pairs if either the first or
the second references are identical and only the other references differ.
And the vectoriser uses VF-based segment lengths only if both references
in a pair have the same step.  Either way, it still seems wrong to use
DR_STEP when it doesn't represent all checks that have been merged into
the pair.


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

gcc/
	* tree-data-ref.h (DR_ALIAS_MIXED_STEPS): New flag.
	* tree-data-ref.c (prune_runtime_alias_test_list): Set it when
	merging data references with different steps.
	(create_intersect_range_checks_index): Take a
	dr_with_seg_len_pair_t instead of two dr_with_seg_lens.
	Bail out if DR_ALIAS_MIXED_STEPS is set.
	(create_intersect_range_checks): Take a dr_with_seg_len_pair_t
	instead of two dr_with_seg_lens.  Update call to
	create_intersect_range_checks_index.
	(create_runtime_alias_checks): Update call accordingly.

On Mon, Nov 11, 2019 at 7:48 PM Richard Sandiford
<richard.sandiford@arm.com> wrote:
>
> prune_runtime_alias_test_list can merge dr_with_seg_len_pair_ts that
> have different steps for the first reference or different steps for the
> second reference.  This patch adds a flag to record that.
>
> I don't know whether the change to create_intersect_range_checks_index
> fixes anything in practice.  It would have to be a corner case if so,
> since at present we only merge two alias pairs if either the first or
> the second references are identical and only the other references differ.
> And the vectoriser uses VF-based segment lengths only if both references
> in a pair have the same step.  Either way, it still seems wrong to use
> DR_STEP when it doesn't represent all checks that have been merged into
> the pair.

OK.

>
> 2019-11-11  Richard Sandiford  <richard.sandiford@arm.com>
>
> gcc/
>         * tree-data-ref.h (DR_ALIAS_MIXED_STEPS): New flag.
>         * tree-data-ref.c (prune_runtime_alias_test_list): Set it when
>         merging data references with different steps.
>         (create_intersect_range_checks_index): Take a
>         dr_with_seg_len_pair_t instead of two dr_with_seg_lens.
>         Bail out if DR_ALIAS_MIXED_STEPS is set.
>         (create_intersect_range_checks): Take a dr_with_seg_len_pair_t
>         instead of two dr_with_seg_lens.  Update call to
>         create_intersect_range_checks_index.
>         (create_runtime_alias_checks): Update call accordingly.
>
> Index: gcc/tree-data-ref.h
> ===================================================================
> --- gcc/tree-data-ref.h 2019-11-11 18:30:50.527193443 +0000
> +++ gcc/tree-data-ref.h 2019-11-11 18:30:53.863170161 +0000
> @@ -250,6 +250,12 @@ typedef struct data_reference *data_refe
>         Temporary flags that indicate whether there is a pair P whose
>         DRs have or haven't been swapped around.
>
> +   DR_ALIAS_MIXED_STEPS:
> +       The DR_STEP for one of the data references in the pair does not
> +       accurately describe that reference for all members of P.  (Note
> +       that the flag does not say anything about whether the DR_STEPs
> +       of the two references in the pair are the same.)
> +
>     The ordering assumption mentioned above is that for every pair
>     (DR_A, DR_B) in P:
>
> @@ -287,6 +293,7 @@ const unsigned int DR_ALIAS_WAW = 1U <<
>  const unsigned int DR_ALIAS_ARBITRARY = 1U << 3;
>  const unsigned int DR_ALIAS_SWAPPED = 1U << 4;
>  const unsigned int DR_ALIAS_UNSWAPPED = 1U << 5;
> +const unsigned int DR_ALIAS_MIXED_STEPS = 1U << 6;
>
>  /* This struct contains two dr_with_seg_len objects with aliasing data
>     refs.  Two comparisons are generated from them.  */
> Index: gcc/tree-data-ref.c
> ===================================================================
> --- gcc/tree-data-ref.c 2019-11-11 18:30:50.527193443 +0000
> +++ gcc/tree-data-ref.c 2019-11-11 18:30:53.863170161 +0000
> @@ -1618,6 +1618,11 @@ prune_runtime_alias_test_list (vec<dr_wi
>               std::swap (init_a1, init_a2);
>             }
>
> +         /* The DR_Bs are equal, so only the DR_As can introduce
> +            mixed steps.  */
> +         if (!operand_equal_p (DR_STEP (dr_a1->dr), DR_STEP (dr_a2->dr), 0))
> +           alias_pair1->flags |= DR_ALIAS_MIXED_STEPS;
> +
>           if (new_seg_len_p)
>             {
>               dr_a1->seg_len = build_int_cst (TREE_TYPE (dr_a1->seg_len),
> @@ -1663,11 +1668,14 @@ prune_runtime_alias_test_list (vec<dr_wi
>      }
>  }
>
> -/* Given LOOP's two data references and segment lengths described by DR_A
> -   and DR_B, create expression checking if the two addresses ranges intersect
> -   with each other based on index of the two addresses.  This can only be
> -   done if DR_A and DR_B referring to the same (array) object and the index
> -   is the only difference.  For example:
> +/* Try to generate a runtime condition that is true if ALIAS_PAIR is
> +   free of aliases, using a condition based on index values instead
> +   of a condition based on addresses.  Return true on success,
> +   storing the condition in *COND_EXPR.
> +
> +   This can only be done if the two data references in ALIAS_PAIR access
> +   the same array object and the index is the only difference.  For example,
> +   if the two data references are DR_A and DR_B:
>
>                         DR_A                           DR_B
>        data-ref         arr[i]                         arr[j]
> @@ -1690,10 +1698,12 @@ prune_runtime_alias_test_list (vec<dr_wi
>
>  static bool
>  create_intersect_range_checks_index (class loop *loop, tree *cond_expr,
> -                                    const dr_with_seg_len& dr_a,
> -                                    const dr_with_seg_len& dr_b)
> +                                    const dr_with_seg_len_pair_t &alias_pair)
>  {
> -  if (integer_zerop (DR_STEP (dr_a.dr))
> +  const dr_with_seg_len &dr_a = alias_pair.first;
> +  const dr_with_seg_len &dr_b = alias_pair.second;
> +  if ((alias_pair.flags & DR_ALIAS_MIXED_STEPS)
> +      || integer_zerop (DR_STEP (dr_a.dr))
>        || integer_zerop (DR_STEP (dr_b.dr))
>        || DR_NUM_DIMENSIONS (dr_a.dr) != DR_NUM_DIMENSIONS (dr_b.dr))
>      return false;
> @@ -1915,24 +1925,26 @@ get_segment_min_max (const dr_with_seg_l
>    *seg_max_out = fold_build_pointer_plus (addr_base, max_reach);
>  }
>
> -/* Given two data references and segment lengths described by DR_A and DR_B,
> -   create expression checking if the two addresses ranges intersect with
> -   each other:
> +/* Generate a runtime condition that is true if ALIAS_PAIR is free of aliases,
> +   storing the condition in *COND_EXPR.  The fallback is to generate a
> +   a test that the two accesses do not overlap:
>
> -     ((DR_A_addr_0 + DR_A_segment_length_0) <= DR_B_addr_0)
> -     || (DR_B_addr_0 + DER_B_segment_length_0) <= DR_A_addr_0))  */
> +     end_a <= start_b || end_b <= start_a.  */
>
>  static void
>  create_intersect_range_checks (class loop *loop, tree *cond_expr,
> -                              const dr_with_seg_len& dr_a,
> -                              const dr_with_seg_len& dr_b)
> +                              const dr_with_seg_len_pair_t &alias_pair)
>  {
> +  const dr_with_seg_len& dr_a = alias_pair.first;
> +  const dr_with_seg_len& dr_b = alias_pair.second;
>    *cond_expr = NULL_TREE;
> -  if (create_intersect_range_checks_index (loop, cond_expr, dr_a, dr_b))
> +  if (create_intersect_range_checks_index (loop, cond_expr, alias_pair))
>      return;
>
>    unsigned HOST_WIDE_INT min_align;
>    tree_code cmp_code;
> +  /* We don't have to check DR_ALIAS_MIXED_STEPS here, since both versions
> +     are equivalent.  This is just an optimization heuristic.  */
>    if (TREE_CODE (DR_STEP (dr_a.dr)) == INTEGER_CST
>        && TREE_CODE (DR_STEP (dr_b.dr)) == INTEGER_CST)
>      {
> @@ -1989,18 +2001,19 @@ create_runtime_alias_checks (class loop
>    tree part_cond_expr;
>
>    fold_defer_overflow_warnings ();
> -  for (size_t i = 0, s = alias_pairs->length (); i < s; ++i)
> +  dr_with_seg_len_pair_t *alias_pair;
> +  unsigned int i;
> +  FOR_EACH_VEC_ELT (*alias_pairs, i, alias_pair)
>      {
> -      const dr_with_seg_len& dr_a = (*alias_pairs)[i].first;
> -      const dr_with_seg_len& dr_b = (*alias_pairs)[i].second;
> -
> +      gcc_assert (alias_pair->flags);
>        if (dump_enabled_p ())
>         dump_printf (MSG_NOTE,
>                      "create runtime check for data references %T and %T\n",
> -                    DR_REF (dr_a.dr), DR_REF (dr_b.dr));
> +                    DR_REF (alias_pair->first.dr),
> +                    DR_REF (alias_pair->second.dr));
>
>        /* Create condition expression for each pair data references.  */
> -      create_intersect_range_checks (loop, &part_cond_expr, dr_a, dr_b);
> +      create_intersect_range_checks (loop, &part_cond_expr, *alias_pair);
>        if (*cond_expr)
>         *cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
>                                   *cond_expr, part_cond_expr);