On Mon, Nov 11, 2019 at 7:48 PM Richard Sandiford
<richard.sandif...@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.sandif...@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);
