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, 158 insertions, 14 deletions

diff --git a/llvm/utils/TableGen/CodeGenDAGPatterns.h b/llvm/utils/TableGen/CodeGenDAGPatterns.h
index bc25419e556..310fbfcc790 100644
--- a/llvm/utils/TableGen/CodeGenDAGPatterns.h
+++ b/llvm/utils/TableGen/CodeGenDAGPatterns.h
@@ -21,24 +21,160 @@
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/MathExtras.h"
 #include <algorithm>
+#include <array>
 #include <map>
 #include <set>
 #include <vector>
 
 namespace llvm {
-  class Record;
-  class Init;
-  class ListInit;
-  class DagInit;
-  class SDNodeInfo;
-  class TreePattern;
-  class TreePatternNode;
-  class CodeGenDAGPatterns;
-  class ComplexPattern;
-
-struct TypeSetByHwMode : public InfoByHwMode<std::set<MVT>> {
-  typedef std::set<MVT> SetType;
+
+class Record;
+class Init;
+class ListInit;
+class DagInit;
+class SDNodeInfo;
+class TreePattern;
+class TreePatternNode;
+class CodeGenDAGPatterns;
+class ComplexPattern;
+
+/// This represents a set of MVTs. Since the underlying type for the MVT
+/// is uint8_t, there are at most 256 values. To reduce the number of memory
+/// allocations and deallocations, represent the set as a sequence of bits.
+/// To reduce the allocations even further, make MachineValueTypeSet own
+/// the storage and use std::array as the bit container.
+struct MachineValueTypeSet {
+  static_assert(std::is_same<std::underlying_type<MVT::SimpleValueType>::type,
+                             uint8_t>::value,
+                "Change uint8_t here to the SimpleValueType's type");
+  static unsigned constexpr Capacity = std::numeric_limits<uint8_t>::max()+1;
+  using WordType = uint64_t;
+  static unsigned constexpr WordWidth = 8*sizeof(WordType);
+  static unsigned constexpr NumWords = Capacity/WordWidth;
+  static_assert(NumWords*WordWidth == Capacity,
+                "Capacity should be a multiple of WordWidth");
+
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  MachineValueTypeSet() {
+    clear();
+  }
+
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  unsigned size() const {
+    unsigned Count = 0;
+    for (WordType W : Words)
+      Count += countPopulation(W);
+    return Count;
+  }
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  void clear() {
+    std::memset(Words.data(), 0, NumWords*sizeof(WordType));
+  }
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  bool empty() const {
+    for (WordType W : Words)
+      if (W != 0)
+        return false;
+    return true;
+  }
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  unsigned count(MVT T) const {
+    return (Words[T.SimpleTy / WordWidth] >> (T.SimpleTy % WordWidth)) & 1;
+  }
+  std::pair<MachineValueTypeSet&,bool> insert(MVT T) {
+    bool V = count(T.SimpleTy);
+    Words[T.SimpleTy / WordWidth] |= WordType(1) << (T.SimpleTy % WordWidth);
+    return {*this, V};
+  }
+  MachineValueTypeSet &insert(const MachineValueTypeSet &S) {
+    for (unsigned i = 0; i != NumWords; ++i)
+      Words[i] |= S.Words[i];
+    return *this;
+  }
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  void erase(MVT T) {
+    Words[T.SimpleTy / WordWidth] &= ~(WordType(1) << (T.SimpleTy % WordWidth));
+  }
+
+  struct const_iterator {
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
+    MVT operator*() const {
+      assert(Pos != Capacity);
+      return MVT::SimpleValueType(Pos);
+    }
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
+    const_iterator(const MachineValueTypeSet *S, bool End) : Set(S) {
+      Pos = End ? Capacity : find_from_pos(0);
+    }
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
+    const_iterator &operator++() {
+      assert(Pos != Capacity);
+      Pos = find_from_pos(Pos+1);
+      return *this;
+    }
+
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
+    bool operator==(const const_iterator &It) const {
+      return Set == It.Set && Pos == It.Pos;
+    }
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
+    bool operator!=(const const_iterator &It) const {
+      return !operator==(It);
+    }
+
+  private:
+    unsigned find_from_pos(unsigned P) const {
+      unsigned SkipWords = P / WordWidth;
+      unsigned SkipBits = P % WordWidth;
+      unsigned Count = SkipWords * WordWidth;
+
+      // If P is in the middle of a word, process it manually here, because
+      // the trailing bits need to be masked off to use findFirstSet.
+      if (SkipBits != 0) {
+        WordType W = Set->Words[SkipWords];
+        W &= maskLeadingOnes<WordType>(WordWidth-SkipBits);
+        if (W != 0)
+          return Count + findFirstSet(W);
+        Count += WordWidth;
+        SkipWords++;
+      }
+
+      for (unsigned i = SkipWords; i != NumWords; ++i) {
+        WordType W = Set->Words[i];
+        if (W != 0)
+          return Count + findFirstSet(W);
+        Count += WordWidth;
+      }
+      return Capacity;
+    }
+
+    const MachineValueTypeSet *Set;
+    unsigned Pos;
+  };
+
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  const_iterator begin() const { return const_iterator(this, false); }
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  const_iterator end()   const { return const_iterator(this, true); }
+
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  bool operator==(const MachineValueTypeSet &S) const {
+    return Words == S.Words;
+  }
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  bool operator!=(const MachineValueTypeSet &S) const {
+    return !operator==(S);
+  }
+
+private:
+  friend struct const_iterator;
+  std::array<WordType,NumWords> Words;
+};
+
+struct TypeSetByHwMode : public InfoByHwMode<MachineValueTypeSet> {
+  using SetType = MachineValueTypeSet;
 
   TypeSetByHwMode() = default;
   TypeSetByHwMode(const TypeSetByHwMode &VTS) = default;
@@ -56,19 +192,23 @@ struct TypeSetByHwMode : public InfoByHwMode<std::set<MVT>> {
 
   bool isValueTypeByHwMode(bool AllowEmpty) const;
   ValueTypeByHwMode getValueTypeByHwMode() const;
+
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
   bool isMachineValueType() const {
     return isDefaultOnly() && Map.begin()->second.size() == 1;
   }
 
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
   MVT getMachineValueType() const {
     assert(isMachineValueType());
     return *Map.begin()->second.begin();
   }
 
   bool isPossible() const;
+
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
   bool isDefaultOnly() const {
-    return Map.size() == 1 &&
-           Map.begin()->first == DefaultMode;
+    return Map.size() == 1 && Map.begin()->first == DefaultMode;
   }
 
   bool insert(const ValueTypeByHwMode &VVT);
@@ -178,6 +318,10 @@ struct TypeInfer {
 
 private:
   TypeSetByHwMode getLegalTypes();
+
+  /// Cached legal types.
+  bool LegalTypesCached = false;
+  TypeSetByHwMode::SetType LegalCache = {};
 };
 
 /// Set type used to track multiply used variables in patterns