[3/8] Add flags to dr_with_seg_len_pair_t
Richard Sandiford
richard.sandiford@arm.com
Mon Nov 11 18:48:00 GMT 2019
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.
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
More information about the Gcc-patches
mailing list