]> git.ipfire.org Git - thirdparty/gcc.git/commit
combine: Optimise distribute_links search [PR116398]
authorRichard Sandiford <richard.sandiford@arm.com>
Mon, 7 Apr 2025 07:03:48 +0000 (08:03 +0100)
committerRichard Sandiford <richard.sandiford@arm.com>
Mon, 7 Apr 2025 07:03:48 +0000 (08:03 +0100)
commit107a1b2126ceb42a79edbc388863c868bd4fbc2e
tree2718c3a408398fad385c6a1d7b76b3f615a1afd6
parent30a4eedfdbfeb1caaadd43738cbb0b49d7fa120b
combine: Optimise distribute_links search [PR116398]

Another problem in PR101523 was that, after each successful 2->2
combination attempt, distribute_links would search further and further
for the next combinable use of the i2 destination.  Each search would
start at i2 itself, making the search quadratic in the worst case.

In a 2->2 combination, if i2 is unchanged, the search can start at i3
instead of i2.  The same thing applies to i2 when distributing i2's
links, since the only changes to earlier instructions are the deletion
of i0 and i1.

This change, combined with the previous split_i2i3 patch, gives a
34.6% speedup in combine for the testcase in PR101523.  Combine
goes from being 41% to 34% of compile time.

gcc/
PR testsuite/116398
* combine.cc (distribute_links): Take an optional start point.
(try_combine): If only i3 has changed, only distribute i3's links,
not i2's.  Start the search for the new use from i3 rather than
from the definition instruction.  Likewise start the search for
the new use from i2 when distributing i2's links.
gcc/combine.cc