MS ABI: Avoid hashing back reference keys in mangler

[K-ballo]

Summary

This patch replaces the back reference StringMap from the MS mangler with a SmallVector of strings. My previous patches reduced the number of hashes involved in back reference lookups, this one removes them completely. The back reference map contains at most 10 entries, which are likely to be of varying sizes and different initial subsequences, and which can easily became huge (due to templates and namespaces).

The solution presented is the simplest possible one. Nevertheless, it's enough to reduce compilation times for a particular test case from 11.1s to 9s, versus 8.58s for the Itanium ABI. Possible further improvements include using a sorted vector (carefully to not introduce an extra comparison), storing the string contents in a common arena, and/or keep the string storage in the context for reuse.

[majnemer]

lib/AST/MicrosoftMangle.cpp

192–194

It's not really a map anymore, perhaps BackRefVec ?

[timurrrr]

Funny.

Agreed to David's comment, otherwise LGTM.

lib/AST/MicrosoftMangle.cpp

999

nit: {} not needed anymore?

[K-ballo]

Addressed review comments

[majnemer]

LGTM

[K-ballo]

Landed in rL218461

lib/AST/MicrosoftMangle.cpp

 #include "clang/AST/DeclTemplate.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/VTableBuilder.h"
 #include "clang/Basic/ABI.h"
 #include "clang/Basic/DiagnosticOptions.h"
 #include "clang/Basic/TargetInfo.h"
 #include "llvm/ADT/StringExtras.h"
-#include "llvm/ADT/StringMap.h"
 #include "llvm/Support/MathExtras.h"
 
 using namespace clang;
 
 namespace {
 
 /// \brief Retrieve the declaration context that should be used when mangling
 /// the given declaration.
class MicrosoftCXXNameMangler {
   MicrosoftMangleContextImpl &Context;
   raw_ostream &Out;
 
   /// The "structor" is the top-level declaration being mangled, if
   /// that's not a template specialization; otherwise it's the pattern
   /// for that specialization.
   const NamedDecl *Structor;
   unsigned StructorType;
 
-  typedef llvm::StringMap<unsigned> BackRefMap;
-  BackRefMap NameBackReferences;
+  typedef llvm::SmallVector<std::string, 10> BackRefVec;
+  BackRefVec NameBackReferences;
 
   typedef llvm::DenseMap<void *, unsigned> ArgBackRefMap;
   ArgBackRefMap TypeBackReferences;
 
   ASTContext &getASTContext() const { return Context.getASTContext(); }
 
   // FIXME: If we add support for __ptr32/64 qualifiers, then we should push
   // this check into mangleQualifiers().
void MicrosoftCXXNameMangler::mangleOperatorName(OverloadedOperatorKind OO,
   case OO_None:
   case NUM_OVERLOADED_OPERATORS:
     llvm_unreachable("Not an overloaded operator");
   }
 }
 
 void MicrosoftCXXNameMangler::mangleSourceName(StringRef Name) {
   // <source name> ::= <identifier> @
-  BackRefMap::iterator Found;
-  if (NameBackReferences.size() < 10) {
-    size_t Size = NameBackReferences.size();
-    bool Inserted;
-    std::tie(Found, Inserted) =
-        NameBackReferences.insert(std::make_pair(Name, Size));
-    if (Inserted)
-      Found = NameBackReferences.end();
-  } else {
-    Found = NameBackReferences.find(Name);
-  }
-
+  BackRefVec::iterator Found =
+      std::find(NameBackReferences.begin(), NameBackReferences.end(), Name);
   if (Found == NameBackReferences.end()) {
+    if (NameBackReferences.size() < 10)
+      NameBackReferences.push_back(Name);
     Out << Name << '@';
   } else {
-    Out << Found->second;
+    Out << (Found - NameBackReferences.begin());
   }
 }
 
 void MicrosoftCXXNameMangler::mangleObjCMethodName(const ObjCMethodDecl *MD) {
   Context.mangleObjCMethodName(MD, Out);
 }
 
 void MicrosoftCXXNameMangler::mangleTemplateInstantiationName(
     const TemplateDecl *TD, const TemplateArgumentList &TemplateArgs) {
   // <template-name> ::= <unscoped-template-name> <template-args>
   //                 ::= <substitution>
   // Always start with the unqualified name.
 
   // Templates have their own context for back references.
   ArgBackRefMap OuterArgsContext;
-  BackRefMap OuterTemplateContext;
+  BackRefVec OuterTemplateContext;
   NameBackReferences.swap(OuterTemplateContext);
   TypeBackReferences.swap(OuterArgsContext);
 
   mangleUnscopedTemplateName(TD);
   mangleTemplateArgs(TD, TemplateArgs);
 
   // Restore the previous back reference contexts.
   NameBackReferences.swap(OuterTemplateContext);