Avoid quadratic behaviour in prune_runtime_alias_test_list
authorRichard Sandiford <richard.sandiford@arm.com>
Fri, 6 Dec 2019 10:31:44 +0000 (10:31 +0000)
committerRichard Sandiford <rsandifo@gcc.gnu.org>
Fri, 6 Dec 2019 10:31:44 +0000 (10:31 +0000)
commitea1ff9e46c7ec5e49ec671616cfcf405ef665054
tree4a101e644378f764e68b9aeb0c38993ec6c4d243
parent28fabd43d9d249134244eb9d7815917c7ae44b64
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
gcc/ChangeLog
gcc/tree-data-ref.c