Improve TableGen performance of -gen-dag-isel (motivated by X86 backend)

The introduction of parameterized register classes in r313271 caused the
matcher generation code in TableGen to run much slower, particularly so
in the unoptimized (debug) build. This patch recovers some of the lost
performance.

Summary of changes:
- Cache the set of legal types in TypeInfer::getLegalTypes. The contents
  of this set do not change.
- Add LLVM_ATTRIBUTE_ALWAYS_INLINE to several small functions. Normally
  this would not be necessary, but in the debug build TableGen is not
  optimized, so this helps a little bit.
- Add an early exit from TypeSetByHwMode::operator== for the case when
  one or both arguments are "simple", i.e. only have one mode. This
  saves some time in GenerateVariants.
- Finally, replace the underlying storage type in TypeSetByHwMode::SetType
  with MachineValueTypeSet based on std::array instead of std::set.
  This significantly reduces the number of memory allocation calls.

I've done a number of experiments with the underlying type of InfoByHwMode.
The type is a map, and for targets that do not use the parameterization,
this map has only one entry. The best (unoptimized) performance, somewhat
surprisingly came from std::map, followed closely by std::unordered_map.
DenseMap was the slowest by a large margin.
Various hand-crafted solutions (emulating enough of the map interface
not to make sweeping changes to the users) did not yield any observable
improvements.

llvm-svn: 313647

1 files changed, 52 insertions, 28 deletions

diff --git a/llvm/utils/TableGen/CodeGenDAGPatterns.cpp b/llvm/utils/TableGen/CodeGenDAGPatterns.cpp
index 86238b6c..633b5b3 100644
--- a/llvm/utils/TableGen/CodeGenDAGPatterns.cpp
+++ b/llvm/utils/TableGen/CodeGenDAGPatterns.cpp
@@ -43,15 +43,16 @@ static inline bool isScalar(MVT VT) {
   return !VT.isVector();
 }
 
-template <typename T, typename Predicate>
-static bool berase_if(std::set<T> &S, Predicate P) {
+template <typename Predicate>
+static bool berase_if(MachineValueTypeSet &S, Predicate P) {
   bool Erased = false;
-  for (auto I = S.begin(); I != S.end(); ) {
-    if (P(*I)) {
-      Erased = true;
-      I = S.erase(I);
-    } else
-      ++I;
+  // It is ok to iterate over MachineValueTypeSet and remove elements from it
+  // at the same time.
+  for (MVT T : S) {
+    if (!P(T))
+      continue;
+    Erased = true;
+    S.erase(T);
   }
   return Erased;
 }
@@ -125,7 +126,7 @@ bool TypeSetByHwMode::constrain(const TypeSetByHwMode &VTS) {
       unsigned M = I.first;
       if (M == DefaultMode || hasMode(M))
         continue;
-      Map[M] = Map[DefaultMode];
+      Map.insert({M, Map.at(DefaultMode)});
       Changed = true;
     }
   }
@@ -183,7 +184,9 @@ std::string TypeSetByHwMode::getAsString() const {
 }
 
 std::string TypeSetByHwMode::getAsString(const SetType &S) {
-  std::vector<MVT> Types(S.begin(), S.end());
+  std::vector<MVT> Types;
+  for (MVT T : S)
+    Types.push_back(T);
   array_pod_sort(Types.begin(), Types.end());
 
   std::stringstream str;
@@ -202,6 +205,12 @@ bool TypeSetByHwMode::operator==(const TypeSetByHwMode &VTS) const {
   if (HaveDefault != VTS.hasDefault())
     return false;
 
+  if (isSimple()) {
+    if (VTS.isSimple())
+      return *begin() == *VTS.begin();
+    return false;
+  }
+
   std::set<unsigned> Modes;
   for (auto &I : *this)
     Modes.insert(I.first);
@@ -253,18 +262,31 @@ bool TypeSetByHwMode::intersect(SetType &Out, const SetType &In) {
   // For example
   // { iPTR } * { i32 }     -> { i32 }
   // { iPTR } * { i32 i64 } -> { iPTR }
-
+  // and
+  // { iPTR i32 } * { i32 }          -> { i32 }
+  // { iPTR i32 } * { i32 i64 }      -> { i32 i64 }
+  // { iPTR i32 } * { i32 i64 i128 } -> { iPTR i32 }
+
+  // Compute the difference between the two sets in such a way that the
+  // iPTR is in the set that is being subtracted. This is to see if there
+  // are any extra scalars in the set without iPTR that are not in the
+  // set containing iPTR. Then the iPTR could be considered a "wildcard"
+  // matching these scalars. If there is only one such scalar, it would
+  // replace the iPTR, if there are more, the iPTR would be retained.
   SetType Diff;
   if (InP) {
-    std::copy_if(Out.begin(), Out.end(), std::inserter(Diff, Diff.end()),
-                [&In](MVT T) { return !In.count(T); });
+    Diff = Out;
+    berase_if(Diff, [&In](MVT T) { return In.count(T); });
+    // Pre-remove these elements and rely only on InP/OutP to determine
+    // whether a change has been made.
     berase_if(Out, [&Diff](MVT T) { return Diff.count(T); });
   } else {
-    std::copy_if(In.begin(), In.end(), std::inserter(Diff, Diff.end()),
-                [&Out](MVT T) { return !Out.count(T); });
+    Diff = In;
+    berase_if(Diff, [&Out](MVT T) { return Out.count(T); });
     Out.erase(MVT::iPTR);
   }
 
+  // The actual intersection.
   bool Changed = berase_if(Out, Int);
   unsigned NumD = Diff.size();
   if (NumD == 0)
@@ -276,8 +298,9 @@ bool TypeSetByHwMode::intersect(SetType &Out, const SetType &In) {
     // being replaced).
     Changed |= OutP;
   } else {
+    // Multiple elements from Out are now replaced with iPTR.
     Out.insert(MVT::iPTR);
-    Changed |= InP;
+    Changed |= !OutP;
   }
   return Changed;
 }
@@ -758,13 +781,12 @@ void TypeInfer::expandOverloads(TypeSetByHwMode &VTS) {
 void TypeInfer::expandOverloads(TypeSetByHwMode::SetType &Out,
                                 const TypeSetByHwMode::SetType &Legal) {
   std::set<MVT> Ovs;
-  for (auto I = Out.begin(); I != Out.end(); ) {
-    if (I->isOverloaded()) {
-      Ovs.insert(*I);
-      I = Out.erase(I);
+  for (MVT T : Out) {
+    if (!T.isOverloaded())
       continue;
-    }
-    ++I;
+    Ovs.insert(T);
+    // MachineValueTypeSet allows iteration and erasing.
+    Out.erase(T);
   }
 
   for (MVT Ov : Ovs) {
@@ -805,13 +827,15 @@ void TypeInfer::expandOverloads(TypeSetByHwMode::SetType &Out,
 }
 
 TypeSetByHwMode TypeInfer::getLegalTypes() {
+  if (!LegalTypesCached) {
+    // Stuff all types from all modes into the default mode.
+    const TypeSetByHwMode &LTS = TP.getDAGPatterns().getLegalTypes();
+    for (const auto &I : LTS)
+      LegalCache.insert(I.second);
+    LegalTypesCached = true;
+  }
   TypeSetByHwMode VTS;
-  TypeSetByHwMode::SetType &DS = VTS.getOrCreate(DefaultMode);
-  const TypeSetByHwMode &LTS = TP.getDAGPatterns().getLegalTypes();
-
-  // Stuff all types from all modes into the default mode.
-  for (const auto &I : LTS)
-    DS.insert(I.second.begin(), I.second.end());
+  VTS.getOrCreate(DefaultMode) = LegalCache;
   return VTS;
 }