[TableGen] Some simple optimizations to TableGen execution time

[zturner]

Summary

I got sufficiently annoyed with sitting around waiting forever for TableGen to complete during a build, so I profiled it. While there's quite a bit more that can be done, this is the really easy stuff. Tons of string allocations and re-allocations, STL stringstream usage, and STL set container usage.

With this patch, X86GenDAGISel is reduced from ~45 seconds to ~33 seconds on my machine, which is a ~1.3x speedup.

The next biggest bottleneck is the class that indents and formats the output. Given that tablegen output is really only intended to be consumed by a machine, it makes sense to question whether or not it's worth the performance cost. I removed the formatting and my speedup jumps to a 2x speedup (44s -> 22s).

After I get the single-threaded execution time sufficiently fast, I might even try to parallelize it. It seems like a terribly obvious and easy candidate for parallelization given that we now have simple parallel algorithms in Support.

Feel free to add other reviewers if there's someone better.

[zturner]

To be clear, this patch is intended to be NFC. So the formatting changes aren't here. Just throwing it out there for potential commentary. I really have no idea how any of this black magic works, so if there's some obvious reason why people need the output to be formatted I'm happy to be wrong (well not happy necessarily, happy would be an extra 11s of my life back every time I type ninja)

[craig.topper]

llvm/utils/TableGen/CodeGenDAGPatterns.h

230–231

I don't see any usage of the return value of this. Did I miss it?

If I didn't miss it, should this just be a void method called print? I think that would be consistent with other classes in LLVM.

Is the llvm:: namespace qualifier needed on raw_ostream?

[craig.topper]

llvm/utils/TableGen/CodeGenDAGPatterns.cpp

3129

llvm:: shouldn't be necessary here.

3819

Shouldn't need llvm::

[craig.topper]

llvm/utils/TableGen/CodeGenDAGPatterns.cpp

186

Why do you need a reserve here? Isn't the vector already have S.size() elements in it after the constructor?

[zturner]

Updated from suggestions.

Craig, do you have thoughts about the formatting? How important is it that the output be formatted?

[asb]

In my view, disabling formatting is unhelpful when you have to debug a compilation error is generated from tablegen'ed code or when auditing its output. If the build-time improvement is meaningful, I'd suggest disabling formatting only when building LLVM in release mode.

[Note: I haven't reviewed unformatted vs formatted tablegen output, it's plausible that in practice the more correct formatting adds relatively little].

[zturner]

Changed another std::set to a DenseSet, and changed a couple of sets to vectors. This shaves off another couple of seconds, I'm now down from 45s (no patch) -> 26s (with patch), for a 1.73x combined speedup.

[RKSimon]

Thank you for working on this!

llvm/include/llvm/CodeGen/MachineValueType.h

203

Is this supposed to equal Metadata?

237

Please revert these whitespace changes - if nothing else it pollutes this patch.

[craig.topper]

llvm/utils/TableGen/CodeGenDAGPatterns.h

242

I wonder if we could use std::bitset. The MVT enum only contains 255 values.

[craig.topper]

Is it the PadToColumn calls that are slowing down the formatting?

[zturner]

In D37957#873349, @craig.topper wrote:

Is it the PadToColumn calls that are slowing down the formatting?

I think it's the fact that every character of every write must be examined in order to find newlines.

One potential optimization that might still work with formatting is to provide a method on the stream called writeLine, where you don't specify the newline but it puts one for you, and assumes that there are no other newlines in the input. This would allow us to get rid of the character scan.

[kparzysz]

Could you rebase this patch?

[zturner]

Rebased on top of changes.

Original baseline (before any performance regression): 11s
After regression: 38s
+Krzysztof's improvements: 26s
+These additional optimizations: 16s

I think this is close enough to the original baseline that it's within the realm of being tolerable. I do get an assertion failure when I run with my patch in debug build, because it's trying to insert an empty StringRef into a StringSet, which is not allowed. Can you apply this patch Krzysztof and see if you can figure out what the right thing to do is with the empty StringRef?

[kparzysz]

In D37957#875513, @zturner wrote:

Can you apply this patch Krzysztof and see if you can figure out what the right thing to do is with the empty StringRef?

It's because of this pattern that doesn't have any named variables (i.e. all names of leaf values are empty):
(intrinsic_void 5755:{ *:[iPTR] }, ECX:{ *:[i32] }, EAX:{ *:[i32] }, EBX:{ *:[i32] })

It corresponds to this pattern in .td, in case anyone's interested:

let Uses = [ ECX, EAX, EBX ] in {
  def MWAITXrrr : I<0x01, MRM_FB, (outs), (ins), "mwaitx",
                  [(int_x86_mwaitx ECX, EAX, EBX)], IIC_SSE_MWAITX>,
                  TB, Requires<[ HasMWAITX ]>;
}

[kparzysz]

llvm/utils/TableGen/CodeGenDAGPatterns.cpp

180

You still need to print the contents of the type set. Something like:

for (unsigned M : Modes) {
  OS << ' ' << getModeName() << ':';
  writeToStream(get(M), OS);
}

3823

Make it if (N->hasName() && isa<DefInit>(N->getLeafValue())). This will avoid the assertion.

[zturner]

Fixed suggestions.

[kparzysz]

LGTM with a few nitpicks (inline comments). Also, could you commit the DenseSet/tombstone changes in a separate patch?

llvm/utils/TableGen/CodeGenDAGPatterns.cpp

101

Same here---the llvm:: seems unnecessary.

167

Same here.

llvm/utils/TableGen/CodeGenDAGPatterns.h

21

This should go in the .cpp file (I don't see any uses of DenseSet in the header).

338

Is the llvm:: needed here?

[zturner]

llvm/utils/TableGen/CodeGenDAGPatterns.h

21

It's needed here in order to specialize the DenseMapInfo

[rnk]

lgtm, just nits

llvm/include/llvm/ADT/DenseSet.h

192

What made us need this?

196

Is this simpler as:

if (!Other.count(I))
  return false;

llvm/utils/TableGen/CodeGenDAGPatterns.cpp

20

You only use StringMap, not StringSet, so include that header.

llvm/utils/TableGen/CodeGenDAGPatterns.h

21

Include DenseMapInfo.h directly, then.

[zturner]

llvm/include/llvm/ADT/DenseSet.h

192

It was no longer needed after Krzysztof's other changes. I removed this in the version that I committted.

llvm/include/llvm/ADT/DenseSet.h

public:
   void erase(Iterator I) { return TheMap.erase(I.I); }
   void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
 
   std::pair<iterator, bool> insert(const ValueT &V) {
     detail::DenseSetEmpty Empty;
     return TheMap.try_emplace(V, Empty);
   }
 
+  bool operator==(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &Other) const {
+    if (size() != Other.size())
+      return false;
+    for (const auto &I : *this)
+      if (Other.find(I) == Other.end())
+        return false;
+    return true;
+  }
+
+  bool operator!=(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &Other) const {
+    return !(*this == Other);
+  }
+
   std::pair<iterator, bool> insert(ValueT &&V) {
     detail::DenseSetEmpty Empty;
     return TheMap.try_emplace(std::move(V), Empty);
   }
 
   /// Alternative version of insert that uses a different (and possibly less
   /// expensive) key type.
   template <typename LookupKeyT>

llvm/include/llvm/CodeGen/MachineValueType.h

 // This file defines the set of machine-level target independent types which
 // legal values in the code generator use.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_MACHINEVALUETYPE_H
 #define LLVM_CODEGEN_MACHINEVALUETYPE_H
 
+#include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MathExtras.h"
 #include <cassert>
 
 namespace llvm {
 
   class Type;
 
   /// Machine Value Type. Every type that is supported natively by some
   /// processor targeted by LLVM occurs here. This means that any legal value
   /// type can be represented by an MVT.
   class MVT {
   public:
     enum SimpleValueType : uint8_t {
       // Simple value types that aren't explicitly part of this enumeration
       // are considered extended value types.
       INVALID_SIMPLE_VALUE_TYPE = 0,
 
       // If you change this numbering, you must change the values in
       // ValueTypes.td as well!
-      Other          =   1,   // This is a non-standard value
-      i1             =   2,   // This is a 1 bit integer value
-      i8             =   3,   // This is an 8 bit integer value
-      i16            =   4,   // This is a 16 bit integer value
-      i32            =   5,   // This is a 32 bit integer value
-      i64            =   6,   // This is a 64 bit integer value
-      i128           =   7,   // This is a 128 bit integer value
+      Other = 1, // This is a non-standard value
+      i1 = 2,    // This is a 1 bit integer value
+      i8 = 3,    // This is an 8 bit integer value
+      i16 = 4,   // This is a 16 bit integer value
+      i32 = 5,   // This is a 32 bit integer value
+      i64 = 6,   // This is a 64 bit integer value
+      i128 = 7,  // This is a 128 bit integer value
 
       FIRST_INTEGER_VALUETYPE = i1,
-      LAST_INTEGER_VALUETYPE  = i128,
+      LAST_INTEGER_VALUETYPE = i128,
 
-      f16            =   8,   // This is a 16 bit floating point value
-      f32            =   9,   // This is a 32 bit floating point value
-      f64            =  10,   // This is a 64 bit floating point value
-      f80            =  11,   // This is a 80 bit floating point value
-      f128           =  12,   // This is a 128 bit floating point value
-      ppcf128        =  13,   // This is a PPC 128-bit floating point value
+      f16 = 8,      // This is a 16 bit floating point value
+      f32 = 9,      // This is a 32 bit floating point value
+      f64 = 10,     // This is a 64 bit floating point value
+      f80 = 11,     // This is a 80 bit floating point value
+      f128 = 12,    // This is a 128 bit floating point value
+      ppcf128 = 13, // This is a PPC 128-bit floating point value
 
       FIRST_FP_VALUETYPE = f16,
-      LAST_FP_VALUETYPE  = ppcf128,
+      LAST_FP_VALUETYPE = ppcf128,
 
-      v1i1           =  14,   //    1 x i1
-      v2i1           =  15,   //    2 x i1
-      v4i1           =  16,   //    4 x i1
-      v8i1           =  17,   //    8 x i1
-      v16i1          =  18,   //   16 x i1
-      v32i1          =  19,   //   32 x i1
-      v64i1          =  20,   //   64 x i1
-      v512i1         =  21,   //  512 x i1
-      v1024i1        =  22,   // 1024 x i1
+      v1i1 = 14,    //    1 x i1
+      v2i1 = 15,    //    2 x i1
+      v4i1 = 16,    //    4 x i1
+      v8i1 = 17,    //    8 x i1
+      v16i1 = 18,   //   16 x i1
+      v32i1 = 19,   //   32 x i1
+      v64i1 = 20,   //   64 x i1
+      v512i1 = 21,  //  512 x i1
+      v1024i1 = 22, // 1024 x i1
 
-      v1i8           =  23,   //  1 x i8
-      v2i8           =  24,   //  2 x i8
-      v4i8           =  25,   //  4 x i8
-      v8i8           =  26,   //  8 x i8
-      v16i8          =  27,   // 16 x i8
-      v32i8          =  28,   // 32 x i8
-      v64i8          =  29,   // 64 x i8
-      v128i8         =  30,   //128 x i8
-      v256i8         =  31,   //256 x i8
+      v1i8 = 23,   //  1 x i8
+      v2i8 = 24,   //  2 x i8
+      v4i8 = 25,   //  4 x i8
+      v8i8 = 26,   //  8 x i8
+      v16i8 = 27,  // 16 x i8
+      v32i8 = 28,  // 32 x i8
+      v64i8 = 29,  // 64 x i8
+      v128i8 = 30, // 128 x i8
+      v256i8 = 31, // 256 x i8
 
-      v1i16          =  32,   //  1 x i16
-      v2i16          =  33,   //  2 x i16
-      v4i16          =  34,   //  4 x i16
-      v8i16          =  35,   //  8 x i16
-      v16i16         =  36,   // 16 x i16
-      v32i16         =  37,   // 32 x i16
-      v64i16         =  38,   // 64 x i16
-      v128i16        =  39,   //128 x i16
+      v1i16 = 32,   //  1 x i16
+      v2i16 = 33,   //  2 x i16
+      v4i16 = 34,   //  4 x i16
+      v8i16 = 35,   //  8 x i16
+      v16i16 = 36,  // 16 x i16
+      v32i16 = 37,  // 32 x i16
+      v64i16 = 38,  // 64 x i16
+      v128i16 = 39, // 128 x i16
 
-      v1i32          =  40,   //  1 x i32
-      v2i32          =  41,   //  2 x i32
-      v4i32          =  42,   //  4 x i32
-      v8i32          =  43,   //  8 x i32
-      v16i32         =  44,   // 16 x i32
-      v32i32         =  45,   // 32 x i32
-      v64i32         =  46,   // 64 x i32
+      v1i32 = 40,  //  1 x i32
+      v2i32 = 41,  //  2 x i32
+      v4i32 = 42,  //  4 x i32
+      v8i32 = 43,  //  8 x i32
+      v16i32 = 44, // 16 x i32
+      v32i32 = 45, // 32 x i32
+      v64i32 = 46, // 64 x i32
 
-      v1i64          =  47,   //  1 x i64
-      v2i64          =  48,   //  2 x i64
-      v4i64          =  49,   //  4 x i64
-      v8i64          =  50,   //  8 x i64
-      v16i64         =  51,   // 16 x i64
-      v32i64         =  52,   // 32 x i64
+      v1i64 = 47,  //  1 x i64
+      v2i64 = 48,  //  2 x i64
+      v4i64 = 49,  //  4 x i64
+      v8i64 = 50,  //  8 x i64
+      v16i64 = 51, // 16 x i64
+      v32i64 = 52, // 32 x i64
 
-      v1i128         =  53,   //  1 x i128
+      v1i128 = 53, //  1 x i128
 
       // Scalable integer types
-      nxv1i1         =  54,   // n x  1 x i1
-      nxv2i1         =  55,   // n x  2 x i1
-      nxv4i1         =  56,   // n x  4 x i1
-      nxv8i1         =  57,   // n x  8 x i1
-      nxv16i1        =  58,   // n x 16 x i1
-      nxv32i1        =  59,   // n x 32 x i1
+      nxv1i1 = 54,  // n x  1 x i1
+      nxv2i1 = 55,  // n x  2 x i1
+      nxv4i1 = 56,  // n x  4 x i1
+      nxv8i1 = 57,  // n x  8 x i1
+      nxv16i1 = 58, // n x 16 x i1
+      nxv32i1 = 59, // n x 32 x i1
 
-      nxv1i8         =  60,   // n x  1 x i8
-      nxv2i8         =  61,   // n x  2 x i8
-      nxv4i8         =  62,   // n x  4 x i8
-      nxv8i8         =  63,   // n x  8 x i8
-      nxv16i8        =  64,   // n x 16 x i8
-      nxv32i8        =  65,   // n x 32 x i8
+      nxv1i8 = 60,  // n x  1 x i8
+      nxv2i8 = 61,  // n x  2 x i8
+      nxv4i8 = 62,  // n x  4 x i8
+      nxv8i8 = 63,  // n x  8 x i8
+      nxv16i8 = 64, // n x 16 x i8
+      nxv32i8 = 65, // n x 32 x i8
 
-      nxv1i16        =  66,   // n x  1 x i16
-      nxv2i16        =  67,   // n x  2 x i16
-      nxv4i16        =  68,   // n x  4 x i16
-      nxv8i16        =  69,   // n x  8 x i16
-      nxv16i16       =  70,   // n x 16 x i16
-      nxv32i16       =  71,   // n x 32 x i16
+      nxv1i16 = 66,  // n x  1 x i16
+      nxv2i16 = 67,  // n x  2 x i16
+      nxv4i16 = 68,  // n x  4 x i16
+      nxv8i16 = 69,  // n x  8 x i16
+      nxv16i16 = 70, // n x 16 x i16
+      nxv32i16 = 71, // n x 32 x i16
 
-      nxv1i32        =  72,   // n x  1 x i32
-      nxv2i32        =  73,   // n x  2 x i32
-      nxv4i32        =  74,   // n x  4 x i32
-      nxv8i32        =  75,   // n x  8 x i32
-      nxv16i32       =  76,   // n x 16 x i32
-      nxv32i32       =  77,   // n x 32 x i32
+      nxv1i32 = 72,  // n x  1 x i32
+      nxv2i32 = 73,  // n x  2 x i32
+      nxv4i32 = 74,  // n x  4 x i32
+      nxv8i32 = 75,  // n x  8 x i32
+      nxv16i32 = 76, // n x 16 x i32
+      nxv32i32 = 77, // n x 32 x i32
 
-      nxv1i64        =  78,   // n x  1 x i64
-      nxv2i64        =  79,   // n x  2 x i64
-      nxv4i64        =  80,   // n x  4 x i64
-      nxv8i64        =  81,   // n x  8 x i64
-      nxv16i64       =  82,   // n x 16 x i64
-      nxv32i64       =  83,   // n x 32 x i64
+      nxv1i64 = 78,  // n x  1 x i64
+      nxv2i64 = 79,  // n x  2 x i64
+      nxv4i64 = 80,  // n x  4 x i64
+      nxv8i64 = 81,  // n x  8 x i64
+      nxv16i64 = 82, // n x 16 x i64
+      nxv32i64 = 83, // n x 32 x i64
 
       FIRST_INTEGER_VECTOR_VALUETYPE = v1i1,
       LAST_INTEGER_VECTOR_VALUETYPE = nxv32i64,
 
       FIRST_INTEGER_SCALABLE_VALUETYPE = nxv1i1,
       LAST_INTEGER_SCALABLE_VALUETYPE = nxv32i64,
 
-      v2f16          =  84,   //  2 x f16
-      v4f16          =  85,   //  4 x f16
-      v8f16          =  86,   //  8 x f16
-      v1f32          =  87,   //  1 x f32
-      v2f32          =  88,   //  2 x f32
-      v4f32          =  89,   //  4 x f32
-      v8f32          =  90,   //  8 x f32
-      v16f32         =  91,   // 16 x f32
-      v1f64          =  92,   //  1 x f64
-      v2f64          =  93,   //  2 x f64
-      v4f64          =  94,   //  4 x f64
-      v8f64          =  95,   //  8 x f64
+      v2f16 = 84,  //  2 x f16
+      v4f16 = 85,  //  4 x f16
+      v8f16 = 86,  //  8 x f16
+      v1f32 = 87,  //  1 x f32
+      v2f32 = 88,  //  2 x f32
+      v4f32 = 89,  //  4 x f32
+      v8f32 = 90,  //  8 x f32
+      v16f32 = 91, // 16 x f32
+      v1f64 = 92,  //  1 x f64
+      v2f64 = 93,  //  2 x f64
+      v4f64 = 94,  //  4 x f64
+      v8f64 = 95,  //  8 x f64
 
-      nxv2f16        =  96,   // n x  2 x f16
-      nxv4f16        =  97,   // n x  4 x f16
-      nxv8f16        =  98,   // n x  8 x f16
-      nxv1f32        =  99,   // n x  1 x f32
-      nxv2f32        = 100,   // n x  2 x f32
-      nxv4f32        = 101,   // n x  4 x f32
-      nxv8f32        = 102,   // n x  8 x f32
-      nxv16f32       = 103,   // n x 16 x f32
-      nxv1f64        = 104,   // n x  1 x f64
-      nxv2f64        = 105,   // n x  2 x f64
-      nxv4f64        = 106,   // n x  4 x f64
-      nxv8f64        = 107,   // n x  8 x f64
+      nxv2f16 = 96,   // n x  2 x f16
+      nxv4f16 = 97,   // n x  4 x f16
+      nxv8f16 = 98,   // n x  8 x f16
+      nxv1f32 = 99,   // n x  1 x f32
+      nxv2f32 = 100,  // n x  2 x f32
+      nxv4f32 = 101,  // n x  4 x f32
+      nxv8f32 = 102,  // n x  8 x f32
+      nxv16f32 = 103, // n x 16 x f32
+      nxv1f64 = 104,  // n x  1 x f64
+      nxv2f64 = 105,  // n x  2 x f64
+      nxv4f64 = 106,  // n x  4 x f64
+      nxv8f64 = 107,  // n x  8 x f64
 
       FIRST_FP_VECTOR_VALUETYPE = v2f16,
       LAST_FP_VECTOR_VALUETYPE = nxv8f64,
 
       FIRST_FP_SCALABLE_VALUETYPE = nxv2f16,
       LAST_FP_SCALABLE_VALUETYPE = nxv8f64,
 
       FIRST_VECTOR_VALUETYPE = v1i1,
-      LAST_VECTOR_VALUETYPE  = nxv8f64,
+      LAST_VECTOR_VALUETYPE = nxv8f64,
 
-      x86mmx         =  108,   // This is an X86 MMX value
+      x86mmx = 108, // This is an X86 MMX value
 
-      Glue           =  109,   // This glues nodes together during pre-RA sched
+      Glue = 109, // This glues nodes together during pre-RA sched
 
-      isVoid         =  110,   // This has no value
+      isVoid = 110, // This has no value
 
-      Untyped        =  111,   // This value takes a register, but has
-                               // unspecified type.  The register class
-                               // will be determined by the opcode.
+      Untyped = 111, // This value takes a register, but has
 
-      FIRST_VALUETYPE = 1,     // This is always the beginning of the list.
-      LAST_VALUETYPE =  112,   // This always remains at the end of the list.
+      FIRST_VALUETYPE = 1,  // This is always the beginning of the list.
+      LAST_VALUETYPE = 112, // This always remains at the end of the list.
 
       // This is the current maximum for LAST_VALUETYPE.
       // MVT::MAX_ALLOWED_VALUETYPE is used for asserts and to size bit vectors
       // This value must be a multiple of 32.
       MAX_ALLOWED_VALUETYPE = 128,
 
+      // Tombstone value used for DenseMapInfo
+      tombstone = 247,
+
       // A value of type llvm::TokenTy
-      token          = 248,
+      token = 248,
 
       // This is MDNode or MDString.
-      Metadata       = 249,
+      Metadata = 249,
 
       // An int value the size of the pointer of the current
       // target to any address space. This must only be used internal to
       // tblgen. Other than for overloading, we treat iPTRAny the same as iPTR.
-      iPTRAny        = 250,
+      iPTRAny = 250,
 
       // A vector with any length and element size. This is used
       // for intrinsics that have overloadings based on vector types.
       // This is only for tblgen's consumption!
-      vAny           = 251,
+      vAny = 251,
 
       // Any floating-point or vector floating-point value. This is used
       // for intrinsics that have overloadings based on floating-point types.
       // This is only for tblgen's consumption!
-      fAny           = 252,
+      fAny = 252,
 
       // An integer or vector integer value of any bit width. This is
       // used for intrinsics that have overloadings based on integer bit widths.
       // This is only for tblgen's consumption!
-      iAny           = 253,
+      iAny = 253,
 
       // An int value the size of the pointer of the current
       // target.  This should only be used internal to tblgen!
-      iPTR           = 254,
+      iPTR = 254,
 
       // Any type. This is used for intrinsics that have overloadings.
       // This is only for tblgen's consumption!
-      Any            = 255
+      Any = 255
     };
 
     SimpleValueType SimpleTy = INVALID_SIMPLE_VALUE_TYPE;
 
     // A class to represent the number of elements in a vector
     //
     // For fixed-length vectors, the total number of elements is equal to 'Min'
     // For scalable vectors, the total number of elements is a multiple of 'Min'
public:
 
     static mvt_range fp_scalable_vector_valuetypes() {
       return mvt_range(MVT::FIRST_FP_SCALABLE_VALUETYPE,
                    (MVT::SimpleValueType)(MVT::LAST_FP_SCALABLE_VALUETYPE + 1));
     }
     /// @}
   };
 
+  template <> struct DenseMapInfo<MVT> {
+    static inline MVT getEmptyKey() {
+      return MVT(MVT::INVALID_SIMPLE_VALUE_TYPE);
+    }
+    static inline MVT getTombstoneKey() { return MVT(MVT::tombstone); }
+    static unsigned getHashValue(const MVT &Val) {
+      return unsigned(Val.SimpleTy);
+    }
+    static bool isEqual(const MVT &LHS, const MVT &RHS) { return LHS == RHS; }
+  };
+
 } // end namespace llvm
 
 #endif // LLVM_CODEGEN_MACHINEVALUETYPE_H

llvm/utils/TableGen/CodeGenDAGPatterns.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_UTILS_TABLEGEN_CODEGENDAGPATTERNS_H
 #define LLVM_UTILS_TABLEGEN_CODEGENDAGPATTERNS_H
 
 #include "CodeGenHwModes.h"
 #include "CodeGenIntrinsics.h"
 #include "CodeGenTarget.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringSet.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MathExtras.h"
 #include <algorithm>
 #include <array>
 #include <map>
 #include <set>
 #include <vector>
 
struct TypeSetByHwMode : public InfoByHwMode<MachineValueTypeSet> {
   LLVM_ATTRIBUTE_ALWAYS_INLINE
   bool isDefaultOnly() const {
     return Map.size() == 1 && Map.begin()->first == DefaultMode;
   }
 
   bool insert(const ValueTypeByHwMode &VVT);
   bool constrain(const TypeSetByHwMode &VTS);
   template <typename Predicate> bool constrain(Predicate P);
-  template <typename Predicate> bool assign_if(const TypeSetByHwMode &VTS,
-                                               Predicate P);
+  template <typename Predicate>
+  bool assign_if(const TypeSetByHwMode &VTS, Predicate P);
 
-  std::string getAsString() const;
-  static std::string getAsString(const SetType &S);
+  void writeToStream(raw_ostream &OS) const;
+  static void writeToStream(const SetType &S, raw_ostream &OS);
 
   bool operator==(const TypeSetByHwMode &VTS) const;
   bool operator!=(const TypeSetByHwMode &VTS) const { return !(*this == VTS); }
 
   void dump() const;
   void validate() const;
 
 private:
   /// Intersect two sets. Return true if anything has changed.
   bool intersect(SetType &Out, const SetType &In);
 };
 
 struct TypeInfer {
   TypeInfer(TreePattern &T) : TP(T), ForceMode(0) {}
 
   bool isConcrete(const TypeSetByHwMode &VTS, bool AllowEmpty) const {
     return VTS.isValueTypeByHwMode(AllowEmpty);
   }
   ValueTypeByHwMode getConcrete(const TypeSetByHwMode &VTS,
private:
   TypeSetByHwMode getLegalTypes();
 
   /// Cached legal types.
   bool LegalTypesCached = false;
   TypeSetByHwMode::SetType LegalCache = {};
 };
 
 /// Set type used to track multiply used variables in patterns
-typedef std::set<std::string> MultipleUseVarSet;
+typedef llvm::StringSet<> MultipleUseVarSet;
 
 /// SDTypeConstraint - This is a discriminated union of constraints,
 /// corresponding to the SDTypeConstraint tablegen class in Target.td.
 struct SDTypeConstraint {
   SDTypeConstraint(Record *R, const CodeGenHwModes &CGH);
 
   unsigned OperandNo;   // The operand # this constraint applies to.
   enum {

llvm/utils/TableGen/CodeGenDAGPatterns.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "CodeGenDAGPatterns.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringExtras.h"
+#include "llvm/ADT/StringSet.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/TableGen/Error.h"
 #include "llvm/TableGen/Record.h"
 #include <algorithm>
 #include <cstdio>
 #include <set>
-#include <sstream>
 using namespace llvm;
 
 #define DEBUG_TYPE "dag-patterns"
 
 static inline bool isIntegerOrPtr(MVT VT) {
   return VT.isInteger() || VT == MVT::iPTR;
 }
 static inline bool isFloatingPoint(MVT VT) {
bool TypeSetByHwMode::isPossible() const {
   for (const auto &I : *this)
     if (!I.second.empty())
       return true;
   return false;
 }
 
 bool TypeSetByHwMode::insert(const ValueTypeByHwMode &VVT) {
   bool Changed = false;
-  std::set<unsigned> Modes;
+  llvm::SmallDenseSet<unsigned, 4> Modes;
   for (const auto &P : VVT) {
     unsigned M = P.first;
     Modes.insert(M);
     // Make sure there exists a set for each specific mode from VVT.
     Changed |= getOrCreate(M).insert(P.second).second;
   }
 
   // If VVT has a default mode, add the corresponding type to all
   // modes in "this" that do not exist in VVT.
   if (Modes.count(DefaultMode)) {
     MVT DT = VVT.getType(DefaultMode);
     for (auto &I : *this)
       if (!Modes.count(I.first))
         Changed |= I.second.insert(DT).second;
   }
-
   return Changed;
 }
 
 // Constrain the type set to be the intersection with VTS.
 bool TypeSetByHwMode::constrain(const TypeSetByHwMode &VTS) {
   bool Changed = false;
   if (hasDefault()) {
     for (const auto &I : VTS) {
for (const auto &I : VTS) {
     SetType &S = getOrCreate(I.first);
     for (auto J : I.second)
       if (P(J))
         S.insert(J);
   }
   return !empty();
 }
 
-std::string TypeSetByHwMode::getAsString() const {
-  std::stringstream str;
-  std::vector<unsigned> Modes;
+void TypeSetByHwMode::writeToStream(raw_ostream &OS) const {
+  llvm::SmallVector<unsigned, 4> Modes;
+  Modes.reserve(Map.size());
 
   for (const auto &I : *this)
     Modes.push_back(I.first);
-  if (Modes.empty())
-    return "{}";
+  if (Modes.empty()) {
+    OS << "{}";
+    return;
+  }
   array_pod_sort(Modes.begin(), Modes.end());
 
-  str << '{';
-  for (unsigned M : Modes) {
-    const SetType &S = get(M);
-    str << ' ' << getModeName(M) << ':' << getAsString(S);
-  }
-  str << " }";
-  return str.str();
+  OS << '{';
+  for (unsigned M : Modes)
+    OS << ' ' << getModeName(M) << ':';
+  OS << " }";
 }
 
-std::string TypeSetByHwMode::getAsString(const SetType &S) {
-  std::vector<MVT> Types;
-  for (MVT T : S)
-    Types.push_back(T);
+void TypeSetByHwMode::writeToStream(const SetType &S, raw_ostream &OS) {
+  SmallVector<MVT, 4> Types(S.begin(), S.end());
   array_pod_sort(Types.begin(), Types.end());
 
-  std::stringstream str;
-  str << '[';
+  OS << '[';
   for (unsigned i = 0, e = Types.size(); i != e; ++i) {
-    str << ValueTypeByHwMode::getMVTName(Types[i]);
+    OS << ValueTypeByHwMode::getMVTName(Types[i]);
     if (i != e-1)
-      str << ' ';
+      OS << ' ';
   }
-  str << ']';
-  return str.str();
+  OS << ']';
 }
 
 bool TypeSetByHwMode::operator==(const TypeSetByHwMode &VTS) const {
   bool HaveDefault = hasDefault();
   if (HaveDefault != VTS.hasDefault())
     return false;
 
   if (isSimple()) {
     if (VTS.isSimple())
       return *begin() == *VTS.begin();
     return false;
   }
 
-  std::set<unsigned> Modes;
+  SmallDenseSet<unsigned, 4> Modes;
   for (auto &I : *this)
     Modes.insert(I.first);
   for (const auto &I : VTS)
     Modes.insert(I.first);
 
   if (HaveDefault) {
     // Both sets have default mode.
     for (unsigned M : Modes) {
if (HaveDefault) {
     }
   }
 
   return true;
 }
 
 LLVM_DUMP_METHOD
 void TypeSetByHwMode::dump() const {
-  dbgs() << getAsString() << '\n';
+  writeToStream(dbgs());
+  dbgs() << '\n';
 }
 
 bool TypeSetByHwMode::intersect(SetType &Out, const SetType &In) {
   bool OutP = Out.count(MVT::iPTR), InP = In.count(MVT::iPTR);
   auto Int = [&In](MVT T) -> bool { return !In.count(T); };
 
   if (OutP == InP)
     return berase_if(Out, Int);

 }
 
 void TypeInfer::expandOverloads(TypeSetByHwMode::SetType &Out,
                                 const TypeSetByHwMode::SetType &Legal) {
   std::set<MVT> Ovs;
   for (MVT T : Out) {
     if (!T.isOverloaded())
       continue;
+
     Ovs.insert(T);
     // MachineValueTypeSet allows iteration and erasing.
     Out.erase(T);
   }
 
   for (MVT Ov : Ovs) {
     switch (Ov.SimpleTy) {
       case MVT::iPTRAny:

 }
 
 void TreePatternNode::print(raw_ostream &OS) const {
   if (isLeaf())
     OS << *getLeafValue();
   else
     OS << '(' << getOperator()->getName();
 
-  for (unsigned i = 0, e = Types.size(); i != e; ++i)
-    OS << ':' << getExtType(i).getAsString();
+  for (unsigned i = 0, e = Types.size(); i != e; ++i) {
+    OS << ':';
+    getExtType(i).writeToStream(OS);
+  }
 
   if (!isLeaf()) {
     if (getNumChildren() != 0) {
       OS << " ";
       getChild(0)->print(OS);
       for (unsigned i = 1, e = getNumChildren(); i != e; ++i) {
         OS << ", ";
         getChild(i)->print(OS);
for (Record *Frag : Fragments) {
     DagInit *Tree = Frag->getValueAsDag("Fragment");
     TreePattern *P =
         (PatternFragments[Frag] = llvm::make_unique<TreePattern>(
              Frag, Tree, !Frag->isSubClassOf("OutPatFrag"),
              *this)).get();
 
     // Validate the argument list, converting it to set, to discard duplicates.
     std::vector<std::string> &Args = P->getArgList();
-    std::set<std::string> OperandsSet(Args.begin(), Args.end());
+    // Copy the args so we can take StringRefs to them.
+    auto ArgsCopy = Args;
+    SmallDenseSet<StringRef, 4> OperandsSet;
+    OperandsSet.insert(ArgsCopy.begin(), ArgsCopy.end());
 
     if (OperandsSet.count(""))
       P->error("Cannot have unnamed 'node' values in pattern fragment!");
 
     // Parse the operands list.
     DagInit *OpsList = Frag->getValueAsDag("Operands");
     DefInit *OpsOp = dyn_cast<DefInit>(OpsList->getOperator());
     // Special cases: ops == outs == ins. Different names are used to
const DAGInstruction &CodeGenDAGPatterns::parseInstructionPattern(
   // InstResults - Keep track of all the virtual registers that are 'set'
   // in the instruction, including what reg class they are.
   std::map<std::string, TreePatternNode*> InstResults;
 
   std::vector<Record*> InstImpResults;
 
   // Verify that the top-level forms in the instruction are of void type, and
   // fill in the InstResults map.
+  SmallString<32> TypesString;
   for (unsigned j = 0, e = I->getNumTrees(); j != e; ++j) {
+    TypesString.clear();
     TreePatternNode *Pat = I->getTree(j);
     if (Pat->getNumTypes() != 0) {
-      std::string Types;
+      raw_svector_ostream OS(TypesString);
       for (unsigned k = 0, ke = Pat->getNumTypes(); k != ke; ++k) {
         if (k > 0)
-          Types += ", ";
-        Types += Pat->getExtType(k).getAsString();
+          OS << ", ";
+        Pat->getExtType(k).writeToStream(OS);
       }
       I->error("Top-level forms in instruction pattern should have"
-               " void types, has types " + Types);
+               " void types, has types " +
+               OS.str());
     }
 
     // Find inputs and outputs, and verify the structure of the uses/defs.
     FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults,
                                 InstImpResults);
   }
 
   // Now that we have inputs and outputs of the pattern, inspect the operands
for (PatternToMatch &P : Copy) {
 
     bool HasDefault = Modes.count(DefaultMode);
     if (HasDefault)
       AppendPattern(P, DefaultMode);
   }
 }
 
 /// Dependent variable map for CodeGenDAGPattern variant generation
-typedef std::map<std::string, int> DepVarMap;
+typedef StringMap<int> DepVarMap;
 
 static void FindDepVarsOf(TreePatternNode *N, DepVarMap &DepMap) {
   if (N->isLeaf()) {
     if (isa<DefInit>(N->getLeafValue()))
       DepMap[N->getName()]++;
   } else {
     for (size_t i = 0, e = N->getNumChildren(); i != e; ++i)
       FindDepVarsOf(N->getChild(i), DepMap);
   }
 }
 
 /// Find dependent variables within child patterns
 static void FindDepVars(TreePatternNode *N, MultipleUseVarSet &DepVars) {
   DepVarMap depcounts;
   FindDepVarsOf(N, depcounts);
-  for (const std::pair<std::string, int> &Pair : depcounts) {
-    if (Pair.second > 1)
-      DepVars.insert(Pair.first);
+  for (const auto &Pair : depcounts) {
+    if (Pair.getValue() > 1)
+      DepVars.insert(Pair.getKey());
   }
 }
 
 #ifndef NDEBUG
 /// Dump the dependent variable set:
 static void DumpDepVars(MultipleUseVarSet &DepVars) {
   if (DepVars.empty()) {
     DEBUG(errs() << "<empty set>");
   } else {
     DEBUG(errs() << "[ ");
-    for (const std::string &DepVar : DepVars) {
-      DEBUG(errs() << DepVar << " ");
+    for (const auto &DepVar : DepVars) {
+      DEBUG(errs() << DepVar.getKey() << " ");
     }
     DEBUG(errs() << "]");
   }
 }
 #endif
 
 
 /// CombineChildVariants - Given a bunch of permutations of each child of the