[GlobalISel] Improving InstructionSelect's performance by reducing MatchTable…

Authored by rtereshin on May 21 2018, 3:04 PM.


[GlobalISel] Improving InstructionSelect's performance by reducing MatchTable, mostly NFC, perf patch 1

This patch starts a series of patches that decrease time spent by
GlobalISel in its InstructionSelect pass by roughly 60% for -O0 builds
for large inputs as measured on sqlite3-amalgamation
(http://sqlite.org/download.html) targeting AArch64.

The performance improvements are achieved solely by reducing the
number of matching GIM_* opcodes executed by the MatchTable's
interpreter during the selection by approx. a factor of 30, which also
brings contribution of this particular part of the selection process
to the overall runtime of InstructionSelect pass down from approx.
60-70% to 5-7%, thus making further improvements in this particular
direction not very profitable.

The improvements described above are expected for any target that
doesn't have many complex patterns. The targets that do should
strictly benefit from the changes, but by how much exactly is hard to
estimate beforehand. It's also likely that such target WILL benefit
from further improvements to MatchTable, most likely the ones that
bring it closer to a perfect decision tree.

This commit specifically is rather large mostly NFC commit that does
necessary preparation work and refactoring, there will be a following
series of small patches introducing a specific optimization each
shortly after.

This commit specifically is expected to cause a small compile time
regression (around 2.5% of InstructionSelect pass time), which should
be fixed by the next commit of the series.

Every commit planned shares the same Phabricator Review.

Reviewers: qcolombet, dsanders, bogner, aemerson, javed.absar

Reviewed By: qcolombet

Subscribers: rovka, llvm-commits, kristof.beyls

Differential Revision: https://reviews.llvm.org/D44700

llvm-svn: 332907


rtereshinMay 21 2018, 3:04 PM
Differential Revision
D44700: [GlobalISel] Improving InstructionSelect's performance by reducing MatchTable
rG0322e3cbf515: Fix another make_unique ambiguity.