From f185b903488b020ae3bb2dc21a5a2b8f7ed861cc Mon Sep 17 00:00:00 2001 From: Marcello Maggioni Date: Fri, 13 Jul 2018 16:36:14 +0000 Subject: [PATCH] [Tablegen] Optimize isSubsetOf() in AsmMatcherEmitter.cpp. NFC 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. Differential Revision: https://reviews.llvm.org/D49124 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@337020 91177308-0d34-0410-b5e6-96231b3b80d8 --- utils/TableGen/AsmMatcherEmitter.cpp | 12 ++++++++++-- 1 file changed, 10 insertions(+), 2 deletions(-) diff --git a/utils/TableGen/AsmMatcherEmitter.cpp b/utils/TableGen/AsmMatcherEmitter.cpp index 7318c6d109e..e808661b7a5 100644 --- a/utils/TableGen/AsmMatcherEmitter.cpp +++ b/utils/TableGen/AsmMatcherEmitter.cpp @@ -273,9 +273,17 @@ public: return true; // ... or if any of its super classes are a subset of RHS. - for (const ClassInfo *CI : SuperClasses) - if (CI->isSubsetOf(RHS)) + SmallVector Worklist(SuperClasses.begin(), + SuperClasses.end()); + SmallPtrSet 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; } -- 2.11.0