From: Richard Sandiford <richard.sandiford@arm.com>
To: gcc-patches@gcc.gnu.org
Subject: [4/8] Record whether a dr_with_seg_len contains mixed steps
Date: Mon, 11 Nov 2019 18:49:00 -0000 [thread overview]
Message-ID: <mptlfsmgsga.fsf@arm.com> (raw)
In-Reply-To: <mpt36eui76b.fsf@arm.com> (Richard Sandiford's message of "Mon, 11 Nov 2019 18:45:00 +0000")
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.
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);
next prev parent reply other threads:[~2019-11-11 18:48 UTC|newest]
Thread overview: 19+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-11-11 18:46 [0/8] Improve vector alias checks for WAR and WAW dependencies Richard Sandiford
2019-11-11 18:47 ` [1/8] Move canonicalisation of dr_with_seg_len_pair_ts Richard Sandiford
2019-11-15 11:01 ` Richard Biener
2019-11-11 18:47 ` [2/8] Delay swapping data refs in prune_runtime_alias_test_list Richard Sandiford
2019-11-15 11:06 ` Richard Biener
2019-11-11 18:48 ` [3/8] Add flags to dr_with_seg_len_pair_t Richard Sandiford
2019-11-15 11:07 ` Richard Biener
2019-11-15 11:37 ` Richard Sandiford
2019-11-15 12:00 ` Richard Biener
2019-11-11 18:49 ` Richard Sandiford [this message]
2019-11-15 11:08 ` [4/8] Record whether a dr_with_seg_len contains mixed steps Richard Biener
2019-11-11 18:50 ` [5/8] Dump the list of merged alias pairs Richard Sandiford
2019-11-15 11:08 ` Richard Biener
2019-11-11 18:51 ` [6/8] Print the type of alias check in a dump message Richard Sandiford
2019-11-15 11:09 ` Richard Biener
2019-11-11 18:52 ` [7/8] Use a single comparison for index-based alias checks Richard Sandiford
2019-11-15 11:12 ` Richard Biener
2019-11-11 19:02 ` [8/8] Optimise WAR and WAW " Richard Sandiford
2019-11-18 11:05 ` Richard Biener
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=mptlfsmgsga.fsf@arm.com \
--to=richard.sandiford@arm.com \
--cc=gcc-patches@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).