[GlobalISel][InstructionSelect] Sorting MatchTable's first level by opcodes and num operands, perf patch 3

This patch continues a series of patches started by r332907 (reapplied as r332917)

In this commit we start sorting the rules by the opcode first, and if
the same, by the number of operands of the root instructions. This
allows better grouping and safe as patterns with different opcodes are
mutually exclusive.

This is expected to decrease time GlobalISel spends in its
InstructionSelect pass by roughly 18% for an -O0 build as measured on
sqlite3-amalgamation (http://sqlite.org/download.html) targeting
AArch64.

I'm also removing RuleMatcher::getFirstConditionAsRootType() function
here and moving it to a later patch within the series as it's not used
yet and was causing a warning on sanitizer-ppc64le-linux bot.

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: 333001

1 files changed, 19 insertions, 11 deletions

diff --git a/llvm/utils/TableGen/GlobalISelEmitter.cpp b/llvm/utils/TableGen/GlobalISelEmitter.cpp
index cdc9df7bf6b..be08165a200 100644
--- a/llvm/utils/TableGen/GlobalISelEmitter.cpp
+++ b/llvm/utils/TableGen/GlobalISelEmitter.cpp
@@ -851,7 +851,6 @@ public:
 
   std::unique_ptr<PredicateMatcher> popFirstCondition() override;
   const PredicateMatcher &getFirstCondition() const override;
-  LLTCodeGen getFirstConditionAsRootType();
   bool hasFirstCondition() const override;
   unsigned getNumOperands() const;
   StringRef getOpcode() const;
@@ -1922,16 +1921,6 @@ unsigned RuleMatcher::getNumOperands() const {
   return Matchers.front()->getNumOperands();
 }
 
-LLTCodeGen RuleMatcher::getFirstConditionAsRootType() {
-  InstructionMatcher &InsnMatcher = *Matchers.front();
-  if (!InsnMatcher.predicates_empty())
-    if (const auto *TM =
-            dyn_cast<LLTOperandMatcher>(&**InsnMatcher.predicates_begin()))
-      if (TM->getInsnVarID() == 0 && TM->getOpIdx() == 0)
-        return TM->getTy();
-  return {};
-}
-
 /// Generates code to check that the operand is a register defined by an
 /// instruction that matches the given instruction matcher.
 ///
@@ -4027,6 +4016,25 @@ GlobalISelEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules,
   if (!Optimize)
     return MatchTable::buildTable(InputRules, WithCoverage);
 
+  unsigned CurrentOrdering = 0;
+  StringMap<unsigned> OpcodeOrder;
+  for (RuleMatcher &Rule : Rules) {
+    const StringRef Opcode = Rule.getOpcode();
+    assert(!Opcode.empty() && "Didn't expect an undefined opcode");
+    if (OpcodeOrder.count(Opcode) == 0)
+      OpcodeOrder[Opcode] = CurrentOrdering++;
+  }
+
+  std::stable_sort(InputRules.begin(), InputRules.end(),
+                   [&OpcodeOrder](const Matcher *A, const Matcher *B) {
+                     auto *L = static_cast<const RuleMatcher *>(A);
+                     auto *R = static_cast<const RuleMatcher *>(B);
+                     return std::make_tuple(OpcodeOrder[L->getOpcode()],
+                                            L->getNumOperands()) <
+                            std::make_tuple(OpcodeOrder[R->getOpcode()],
+                                            R->getNumOperands());
+                   });
+
   for (Matcher *Rule : InputRules)
     Rule->optimize();