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.

Tested on aarch64-linux-gnu and x86_64-linux-gnu.  OK to install?

Richard


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.

On Fri, Dec 6, 2019 at 9:36 AM Richard Sandiford
<richard.sandiford@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.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.
>
> 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