[Tablegen] Optimize isSubsetOf() in AsmMatcherEmitter.cpp

[kariddi]

Summary

isSubsetOf() could be very slow if the hierarchy of the RegisterClasses of the target is very complicated.

This is mainly caused by the fact that isSubset() is called multiple times over the same SuperClass of a register class if this ends up being the super class of a register class from multiple paths.

[kariddi]

ping

[greened]

LGTM, with one not-critical comment about comment placement.

utils/TableGen/AsmMatcherEmitter.cpp

278 ↗

(On Diff #154759)

Perhaps this comment should go about the declarations immediate before it.

278 ↗

(On Diff #154759)

s/about/above/

[kariddi]

Thanks David. I'll address your comment in my commit

llvm/trunk/utils/TableGen/AsmMatcherEmitter.cpp

public:
 
   /// isSubsetOf - Test whether this class is a subset of \p RHS.
   bool isSubsetOf(const ClassInfo &RHS) const {
     // This is a subset of RHS if it is the same class...
     if (this == &RHS)
       return true;
 
     // ... or if any of its super classes are a subset of RHS.
-    for (const ClassInfo *CI : SuperClasses)
-      if (CI->isSubsetOf(RHS))
+    SmallVector<const ClassInfo *, 16> Worklist(SuperClasses.begin(),
+                                                SuperClasses.end());
+    SmallPtrSet<const ClassInfo *, 16> Visited;
+    while (!Worklist.empty()) {
+      auto *CI = Worklist.pop_back_val();
+      if (CI == &RHS)
         return true;
+      for (auto *Super : CI->SuperClasses)
+        if (Visited.insert(Super).second)
+          Worklist.push_back(Super);
+    }
 
     return false;
   }
 
   int getTreeDepth() const {
     int Depth = 0;
     const ClassInfo *Root = this;
     while (!Root->SuperClasses.empty()) {