diff options
| author | Richard Sandiford <richard.sandiford@arm.com> | 2019-12-06 10:31:44 +0000 |
|---|---|---|
| committer | Richard Sandiford <rsandifo@gcc.gnu.org> | 2019-12-06 10:31:44 +0000 |
| commit | ea1ff9e46c7ec5e49ec671616cfcf405ef665054 (patch) | |
| tree | 4a101e644378f764e68b9aeb0c38993ec6c4d243 /gcc/tree-data-ref.c | |
| parent | 28fabd43d9d249134244eb9d7815917c7ae44b64 (diff) | |
| download | gcc-ea1ff9e46c7ec5e49ec671616cfcf405ef665054.zip gcc-ea1ff9e46c7ec5e49ec671616cfcf405ef665054.tar.gz gcc-ea1ff9e46c7ec5e49ec671616cfcf405ef665054.tar.bz2 | |
Avoid quadratic behaviour in prune_runtime_alias_test_list
prune_runtime_alias_test_list used ordered_remove to remove a merged
alias pair, which made the function quadratic when many aliases could
be removed.
I had a testcase in which these memmoves accounted for an impressive
85% of compile time. The fact that we had so many probably shows
a deeper problem, but still, it's easy to remove as we go.
2019-12-06 Richard Sandiford <richard.sandiford@arm.com>
gcc/
* tree-data-ref.c (prune_runtime_alias_test_list): Exit early
for empty vectors. Avoid using ordered_remove and instead
shuffle the vector as we go.
From-SVN: r279038
Diffstat (limited to 'gcc/tree-data-ref.c')
| -rw-r--r-- | gcc/tree-data-ref.c | 17 |
1 files changed, 13 insertions, 4 deletions
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index 117a14b..7ef891d 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -1535,6 +1535,9 @@ void prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *alias_pairs, poly_uint64) { + if (alias_pairs->is_empty ()) + return; + /* Canonicalize each pair so that the base components are ordered wrt data_ref_compare_tree. This allows the loop below to merge more cases. */ @@ -1565,10 +1568,11 @@ prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *alias_pairs, /* Scan the sorted dr pairs and check if we can combine alias checks of two neighboring dr pairs. */ + unsigned int last = 0; 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_pair_t *alias_pair1 = &(*alias_pairs)[i - 1]; + dr_with_seg_len_pair_t *alias_pair1 = &(*alias_pairs)[last]; dr_with_seg_len_pair_t *alias_pair2 = &(*alias_pairs)[i]; dr_with_seg_len *dr_a1 = &alias_pair1->first; @@ -1584,10 +1588,15 @@ prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *alias_pairs, 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; } + /* Assume that we won't be able to merge the pairs, then correct + if we do. */ + last += 1; + if (last != i) + (*alias_pairs)[last] = (*alias_pairs)[i]; + if (*dr_a1 == *dr_a2 || *dr_b1 == *dr_b2) { /* We consider the case that DR_B1 and DR_B2 are same memrefs, @@ -1695,10 +1704,10 @@ prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *alias_pairs, 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--; + last -= 1; } } + alias_pairs->truncate (last + 1); /* 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 |