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

[RKSimon]

Summary

Further extension to D51035, this patch avoids all repeated predicates[] matching by caching as it collects the patterns that have multiple variants.

Saves around 25secs in debug builds of x86 -gen-dag-isel (and finally gets its runtime below 7mins!).

[RKSimon]

ping?

[RKSimon]

ping

[andreadb]

LGTM.

utils/TableGen/CodeGenDAGPatterns.cpp

void CodeGenDAGPatterns::GenerateVariants() {
   // generate variants of the instruction, through the exploitation of
   // identities.  This permits the target to provide aggressive matching without
   // the .td file having to contain tons of variants of instructions.
   //
   // Note that this loop adds new patterns to the PatternsToMatch list, but we
   // intentionally do not reconsider these.  Any variants of added patterns have
   // already been added.
   //
-  for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) {
-    MultipleUseVarSet             DepVars;
+  const unsigned NumOriginalPatterns = PatternsToMatch.size();
+  BitVector MatchedPatterns(NumOriginalPatterns);
+  std::vector<BitVector> MatchedPredicates(NumOriginalPatterns,
+                                           BitVector(NumOriginalPatterns));
+
+  typedef std::pair<MultipleUseVarSet, std::vector<TreePatternNodePtr>>
+      DepsAndVariants;
+  std::map<unsigned, DepsAndVariants> PatternsWithVariants;
+
+  // Collect patterns with more than one variant.
+  for (unsigned i = 0; i != NumOriginalPatterns; ++i) {
+    MultipleUseVarSet DepVars;
     std::vector<TreePatternNodePtr> Variants;
     FindDepVars(PatternsToMatch[i].getSrcPattern(), DepVars);
     LLVM_DEBUG(errs() << "Dependent/multiply used variables: ");
     LLVM_DEBUG(DumpDepVars(DepVars));
     LLVM_DEBUG(errs() << "\n");
     GenerateVariantsOf(PatternsToMatch[i].getSrcPatternShared(), Variants,
                        *this, DepVars);
 
     assert(!Variants.empty() && "Must create at least original variant!");
-    if (Variants.size() == 1)  // No additional variants for this pattern.
+    if (Variants.size() == 1) // No additional variants for this pattern.
       continue;
 
     LLVM_DEBUG(errs() << "FOUND VARIANTS OF: ";
                PatternsToMatch[i].getSrcPattern()->dump(); errs() << "\n");
 
+    PatternsWithVariants[i] = std::make_pair(DepVars, Variants);
+
     // 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());
+    if (MatchedPatterns[i])
+      continue;
+
+    const std::vector<Predicate> &Predicates =
+        PatternsToMatch[i].getPredicates();
+
+    BitVector &Matches = MatchedPredicates[i];
+    MatchedPatterns[i] = true;
+    Matches[i] = true;
+
+    // Don't test patterns that have already been cached - it won't match.
+    for (unsigned p = 0; p != NumOriginalPatterns; ++p)
+      if (!MatchedPatterns[p])
+        Matches[p] = (Predicates == PatternsToMatch[p].getPredicates());
+
+    // Copy this to all the matching patterns.
+    for (int p = Matches.find_first(); p != -1; p = Matches.find_next(p))
+      if (p != i) {
+        MatchedPatterns[p] = true;
+        MatchedPredicates[p] = Matches;
+      }
+  }
+
+  for (auto it : PatternsWithVariants) {
+    unsigned i = it.first;
+    const MultipleUseVarSet &DepVars = it.second.first;
+    const std::vector<TreePatternNodePtr> &Variants = it.second.second;
 
     for (unsigned v = 0, e = Variants.size(); v != e; ++v) {
       TreePatternNodePtr Variant = Variants[v];
+      BitVector &Matches = MatchedPredicates[i];
 
       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 (!MatchedPredicates[p])
+        if (!Matches[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;
+      MatchedPredicates.push_back(Matches);
+
+      unsigned NumPatterns = PatternsToMatch.size();
+      for (unsigned p = 0; p != NumPatterns; ++p)
+        MatchedPredicates[p].resize(NumPatterns, MatchedPredicates[p][i]);
     }
 
     LLVM_DEBUG(errs() << "\n");
   }
 }