From 2c937a13ee04eb37f275b924b38f34306db47eda Mon Sep 17 00:00:00 2001 From: Justin Lebar Date: Fri, 21 Oct 2016 21:45:01 +0000 Subject: [PATCH] Switch SmallSetVector to use DenseSet when it overflows its inline space. Summary: SetVector already used DenseSet, but SmallSetVector used std::set. This leads to surprising performance differences. Moreover, it means that the set of key types accepted by SetVector and SmallSetVector are quite different! In order to make this change, we had to convert some callsites that used SmallSetVector to use SmallSetVector instead. Reviewers: timshen Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D25648 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@284887 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/SetVector.h | 3 ++- utils/TableGen/AsmMatcherEmitter.cpp | 32 ++++++++++++----------- utils/TableGen/FixedLenDecoderEmitter.cpp | 11 ++++---- 3 files changed, 25 insertions(+), 21 deletions(-) diff --git a/include/llvm/ADT/SetVector.h b/include/llvm/ADT/SetVector.h index 455f8a89e10..c6bc9bfb546 100644 --- a/include/llvm/ADT/SetVector.h +++ b/include/llvm/ADT/SetVector.h @@ -282,7 +282,8 @@ private: /// \brief A SetVector that performs no allocations if smaller than /// a certain size. template -class SmallSetVector : public SetVector, SmallSet > { +class SmallSetVector + : public SetVector, SmallDenseSet> { public: SmallSetVector() {} diff --git a/utils/TableGen/AsmMatcherEmitter.cpp b/utils/TableGen/AsmMatcherEmitter.cpp index fb715364b71..5dbd5ec9bb0 100644 --- a/utils/TableGen/AsmMatcherEmitter.cpp +++ b/utils/TableGen/AsmMatcherEmitter.cpp @@ -97,6 +97,7 @@ //===----------------------------------------------------------------------===// #include "CodeGenTarget.h" +#include "llvm/ADT/CachedHashString.h" #include "llvm/ADT/PointerUnion.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" @@ -1822,10 +1823,11 @@ void MatchableInfo::buildAliasResultOperands() { } } -static unsigned getConverterOperandID(const std::string &Name, - SmallSetVector &Table, - bool &IsNew) { - IsNew = Table.insert(Name); +static unsigned +getConverterOperandID(const std::string &Name, + SmallSetVector &Table, + bool &IsNew) { + IsNew = Table.insert(CachedHashString(Name)); unsigned ID = IsNew ? Table.size() - 1 : find(Table, Name) - Table.begin(); @@ -1838,8 +1840,8 @@ static void emitConvertFuncs(CodeGenTarget &Target, StringRef ClassName, std::vector> &Infos, bool HasMnemonicFirst, bool HasOptionalOperands, raw_ostream &OS) { - SmallSetVector OperandConversionKinds; - SmallSetVector InstructionConversionKinds; + SmallSetVector OperandConversionKinds; + SmallSetVector InstructionConversionKinds; std::vector > ConversionTable; size_t MaxRowLength = 2; // minimum is custom converter plus terminator. @@ -1911,9 +1913,9 @@ static void emitConvertFuncs(CodeGenTarget &Target, StringRef ClassName, // Pre-populate the operand conversion kinds with the standard always // available entries. - OperandConversionKinds.insert("CVT_Done"); - OperandConversionKinds.insert("CVT_Reg"); - OperandConversionKinds.insert("CVT_Tied"); + OperandConversionKinds.insert(CachedHashString("CVT_Done")); + OperandConversionKinds.insert(CachedHashString("CVT_Reg")); + OperandConversionKinds.insert(CachedHashString("CVT_Tied")); enum { CVT_Done, CVT_Reg, CVT_Tied }; for (auto &II : Infos) { @@ -1925,13 +1927,13 @@ static void emitConvertFuncs(CodeGenTarget &Target, StringRef ClassName, II->ConversionFnKind = Signature; // Check if we have already generated this signature. - if (!InstructionConversionKinds.insert(Signature)) + if (!InstructionConversionKinds.insert(CachedHashString(Signature))) continue; // Remember this converter for the kind enum. unsigned KindID = OperandConversionKinds.size(); - OperandConversionKinds.insert("CVT_" + - getEnumNameForToken(AsmMatchConverter)); + OperandConversionKinds.insert( + CachedHashString("CVT_" + getEnumNameForToken(AsmMatchConverter))); // Add the converter row for this instruction. ConversionTable.emplace_back(); @@ -2113,7 +2115,7 @@ static void emitConvertFuncs(CodeGenTarget &Target, StringRef ClassName, // Save the signature. If we already have it, don't add a new row // to the table. - if (!InstructionConversionKinds.insert(Signature)) + if (!InstructionConversionKinds.insert(CachedHashString(Signature))) continue; // Add the row to the table. @@ -2130,14 +2132,14 @@ static void emitConvertFuncs(CodeGenTarget &Target, StringRef ClassName, // Output the operand conversion kind enum. OS << "enum OperatorConversionKind {\n"; - for (const std::string &Converter : OperandConversionKinds) + for (const auto &Converter : OperandConversionKinds) OS << " " << Converter << ",\n"; OS << " CVT_NUM_CONVERTERS\n"; OS << "};\n\n"; // Output the instruction conversion kind enum. OS << "enum InstructionConversionKind {\n"; - for (const std::string &Signature : InstructionConversionKinds) + for (const auto &Signature : InstructionConversionKinds) OS << " " << Signature << ",\n"; OS << " CVT_NUM_SIGNATURES\n"; OS << "};\n\n"; diff --git a/utils/TableGen/FixedLenDecoderEmitter.cpp b/utils/TableGen/FixedLenDecoderEmitter.cpp index d0c4e0fd2f9..f2d54e6fe5a 100644 --- a/utils/TableGen/FixedLenDecoderEmitter.cpp +++ b/utils/TableGen/FixedLenDecoderEmitter.cpp @@ -14,6 +14,7 @@ #include "CodeGenTarget.h" #include "llvm/ADT/APInt.h" +#include "llvm/ADT/CachedHashString.h" #include "llvm/ADT/SmallString.h" #include "llvm/ADT/StringExtras.h" #include "llvm/ADT/StringRef.h" @@ -66,8 +67,8 @@ typedef std::vector DecoderTable; typedef uint32_t DecoderFixup; typedef std::vector FixupList; typedef std::vector FixupScopeList; -typedef SmallSetVector PredicateSet; -typedef SmallSetVector DecoderSet; +typedef SmallSetVector PredicateSet; +typedef SmallSetVector DecoderSet; struct DecoderTableInfo { DecoderTable Table; FixupScopeList FixupStack; @@ -1106,7 +1107,7 @@ unsigned FilterChooser::getDecoderIndex(DecoderSet &Decoders, // overkill for now, though. // Make sure the predicate is in the table. - Decoders.insert(StringRef(Decoder)); + Decoders.insert(CachedHashString(Decoder)); // Now figure out the index for when we write out the table. DecoderSet::const_iterator P = find(Decoders, Decoder.str()); return (unsigned)(P - Decoders.begin()); @@ -1179,9 +1180,9 @@ unsigned FilterChooser::getPredicateIndex(DecoderTableInfo &TableInfo, // overkill for now, though. // Make sure the predicate is in the table. - TableInfo.Predicates.insert(Predicate.str()); + TableInfo.Predicates.insert(CachedHashString(Predicate)); // Now figure out the index for when we write out the table. - PredicateSet::const_iterator P = find(TableInfo.Predicates, Predicate.str()); + PredicateSet::const_iterator P = find(TableInfo.Predicates, Predicate); return (unsigned)(P - TableInfo.Predicates.begin()); } -- 2.49.0