[TableGen] CodeGenDAGPatterns::GenerateVariants - basic caching of matching predicates

[RKSimon]

Summary

CodeGenDAGPatterns::GenerateVariants is a costly function in many tblgen commands (33.87% of the total runtime of x86 -gen-dag-isel), and due to the O(N^2) nature of the function, there are a lot of repeated comparisons of the pattern's vector<Predicate> (19.9% of the total runtime of x86 -gen-dag-isel).

This initial patch at least avoids repeating these comparisons for every Variant per pattern. I began investigating caching all the matches before entering the loop but hit issues with how best to store the data and how to update the cache as patterns were added - until thats solved, this is at least an improvement.

Also, its not clear to me if the inner loop over PatternsToMatch needs to compare against the extra patterns generated in the function or not - if not it should be possible to split these loops and reduce its quadratic nature. @kparzysz can you confirm please?

Saves around 15secs in debug builds of x86 -gen-dag-isel.

[RKSimon]

ping?

[kparzysz]

It should be possible to move this loop out of the nest and only have it iterate over the preexisting patterns. Could you see if that generates different .inc files (it shouldn't)?

[RKSimon]

In D51035#1214882, @kparzysz wrote:

It should be possible to move this loop out of the nest and only have it iterate over the preexisting patterns. Could you see if that generates different .inc files (it shouldn't)?

Definitely, but to do it properly requires quite a bit of refactoring - the O(N^2) nature of this loop needs addressing properly - I'd prefer to get this initial patch in first please.

llvm/trunk/utils/TableGen/CodeGenDAGPatterns.cpp

 //===- CodeGenDAGPatterns.cpp - Read DAG patterns from .td file -----------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the CodeGenDAGPatterns class, which is used to read and
 // represent the patterns present in a .td file for instructions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "CodeGenDAGPatterns.h"
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Support/Debug.h"
for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) {
 
     assert(!Variants.empty() && "Must create at least original variant!");
     if (Variants.size() == 1)  // No additional variants for this pattern.
       continue;
 
     LLVM_DEBUG(errs() << "FOUND VARIANTS OF: ";
                PatternsToMatch[i].getSrcPattern()->dump(); errs() << "\n");
 
+    // Cache matching predicates.
+    // TODO: Is it performant to pull this out of the loop entirely?
+    BitVector MatchedPredicates(PatternsToMatch.size(), false);
+    for (unsigned p = 0, e = PatternsToMatch.size(); p != e; ++p)
+      MatchedPredicates[p] = (i == p) || (PatternsToMatch[i].getPredicates() ==
+                                          PatternsToMatch[p].getPredicates());
+
+    unsigned NumMatches = MatchedPredicates.count();
+    (void)NumMatches;
+
     for (unsigned v = 0, e = Variants.size(); v != e; ++v) {
       TreePatternNodePtr Variant = Variants[v];
 
       LLVM_DEBUG(errs() << "  VAR#" << v << ": "; Variant->dump();
                  errs() << "\n");
 
       // Scan to see if an instruction or explicit pattern already matches this.
       bool AlreadyExists = false;
       for (unsigned p = 0, e = PatternsToMatch.size(); p != e; ++p) {
         // Skip if the top level predicates do not match.
-        if ((i != p) && (PatternsToMatch[i].getPredicates() !=
-                         PatternsToMatch[p].getPredicates()))
+        if (!MatchedPredicates[p])
           continue;
         // Check to see if this variant already exists.
         if (Variant->isIsomorphicTo(PatternsToMatch[p].getSrcPattern(),
                                     DepVars)) {
           LLVM_DEBUG(errs() << "  *** ALREADY EXISTS, ignoring variant.\n");
           AlreadyExists = true;
           break;
         }
       }
       // If we already have it, ignore the variant.
       if (AlreadyExists) continue;
 
       // Otherwise, add it to the list of patterns we have.
       PatternsToMatch.push_back(PatternToMatch(
           PatternsToMatch[i].getSrcRecord(), PatternsToMatch[i].getPredicates(),
           Variant, PatternsToMatch[i].getDstPatternShared(),
           PatternsToMatch[i].getDstRegs(),
           PatternsToMatch[i].getAddedComplexity(), Record::getNewUID()));
+      MatchedPredicates.resize(PatternsToMatch.size());
+      MatchedPredicates[PatternsToMatch.size() - 1] = true;
     }
 
     LLVM_DEBUG(errs() << "\n");
   }
 }