On Fri, Dec 6, 2019 at 9:36 AM Richard Sandiford
<richard.sandif...@arm.com> wrote:
>
> 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.
>
> Tested on aarch64-linux-gnu and x86_64-linux-gnu. OK to install?
OK.
> Richard
>
>
> 2019-12-06 Richard Sandiford <richard.sandif...@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.
>
> Index: gcc/tree-data-ref.c
> ===================================================================
> --- gcc/tree-data-ref.c 2019-11-18 15:36:04.873884873 +0000
> +++ gcc/tree-data-ref.c 2019-12-06 08:35:38.153410087 +0000
> @@ -1535,6 +1535,9 @@ dump_alias_pair (dr_with_seg_len_pair_t
> 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_wi
>
> /* 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_wi
> 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_wi
> 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
