msabi: Fix exponential mangling time for even more contrived inputs

[thakis]

Summary

This is a follow-up to r362293 which fixed exponential time needed
for mangling certain templates. This fixes the same issue if that
template pattern happens in template arguments > 10: The first
ten template arguments can use back references, and r362293 added
caching for back references. For latter arguments, we have to add
a cache for the mangling itself instead.

Fixes PR42091 even more.

[rnk]

clang/lib/AST/MicrosoftMangle.cpp

819–823

Here's a thought: could we get by with one map? I think we can be certain that nothing mangles to integer literals between 0 and 9, since otherwise the demangler couldn't distinguish those from back references. So, can we keep the string map, and insert the string "0", "1", etc for back referenced things?

[thakis]

clang/lib/AST/MicrosoftMangle.cpp

819–823

I had wondered too. In the end, I figured the int map needs less memory and is almost always enough, so I went with this approach.

[rnk]

lgtm

clang/lib/AST/MicrosoftMangle.cpp

819–823

I think I'm coming at this more from the perspective of less code complexity, fewer ifs, fewer data structures to name and have to understand. We could get the memory wins by storing numbers in the map, and then having a side vector of numbered strings, indexed by BackrefId-10. Then that data structure would be seldom used. Anyway, it's all code golf, not really important.

clang/lib/AST/MicrosoftMangle.cpp

 #include "clang/Basic/ABI.h"
 #include "clang/Basic/DiagnosticOptions.h"
 #include "clang/Basic/TargetInfo.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/JamCRC.h"
 #include "llvm/Support/xxhash.h"
 #include "llvm/Support/MD5.h"
 #include "llvm/Support/MathExtras.h"
+#include "llvm/Support/StringSaver.h"
 
 using namespace clang;
 
 namespace {
 
 struct msvc_hashing_ostream : public llvm::raw_svector_ostream {
   raw_ostream &OS;
   llvm::SmallString<64> Buffer;
class MicrosoftCXXNameMangler {
 
   typedef llvm::SmallVector<std::string, 10> BackRefVec;
   BackRefVec NameBackReferences;
 
   typedef llvm::DenseMap<const void *, unsigned> ArgBackRefMap;
   ArgBackRefMap FunArgBackReferences;
   ArgBackRefMap TemplateArgBackReferences;
 
+  typedef llvm::DenseMap<const void *, StringRef> TemplateArgStringMap;
+  TemplateArgStringMap TemplateArgStrings;
+  llvm::StringSaver TemplateArgStringStorage;
+  llvm::BumpPtrAllocator TemplateArgStringStorageAlloc;
+
   typedef std::set<std::pair<int, bool>> PassObjectSizeArgsSet;
   PassObjectSizeArgsSet PassObjectSizeArgs;
 
   ASTContext &getASTContext() const { return Context.getASTContext(); }
 
   // FIXME: If we add support for __ptr32/64 qualifiers, then we should push
   // this check into mangleQualifiers().
   const bool PointersAre64Bit;
 
 public:
   enum QualifierMangleMode { QMM_Drop, QMM_Mangle, QMM_Escape, QMM_Result };
 
   MicrosoftCXXNameMangler(MicrosoftMangleContextImpl &C, raw_ostream &Out_)
       : Context(C), Out(Out_), Structor(nullptr), StructorType(-1),
+        TemplateArgStringStorage(TemplateArgStringStorageAlloc),
         PointersAre64Bit(C.getASTContext().getTargetInfo().getPointerWidth(0) ==
                          64) {}
 
   MicrosoftCXXNameMangler(MicrosoftMangleContextImpl &C, raw_ostream &Out_,
                           const CXXConstructorDecl *D, CXXCtorType Type)
       : Context(C), Out(Out_), Structor(getStructor(D)), StructorType(Type),
+        TemplateArgStringStorage(TemplateArgStringStorageAlloc),
         PointersAre64Bit(C.getASTContext().getTargetInfo().getPointerWidth(0) ==
                          64) {}
 
   MicrosoftCXXNameMangler(MicrosoftMangleContextImpl &C, raw_ostream &Out_,
                           const CXXDestructorDecl *D, CXXDtorType Type)
       : Context(C), Out(Out_), Structor(getStructor(D)), StructorType(Type),
+        TemplateArgStringStorage(TemplateArgStringStorageAlloc),
         PointersAre64Bit(C.getASTContext().getTargetInfo().getPointerWidth(0) ==
                          64) {}
 
   raw_ostream &getStream() const { return Out; }
 
   void mangle(const NamedDecl *D, StringRef Prefix = "?");
   void mangleName(const NamedDecl *ND);
   void mangleFunctionEncoding(const FunctionDecl *FD, bool ShouldMangle);
if (const TemplateDecl *TD = isTemplate(ND, TemplateArgs)) {
     // What we do is we create a new mangler, mangle the same type (without
     // a namespace suffix) to a string using the extra mangler and then use
     // the mangled type name as a key to check the mangling of different types
     // for aliasing.
 
     // It's important to key cache reads off ND, not TD -- the same TD can
     // be used with different TemplateArgs, but ND uniquely identifies
     // TD / TemplateArg pairs.
     ArgBackRefMap::iterator Found = TemplateArgBackReferences.find(ND);
     if (Found == TemplateArgBackReferences.end()) {
+
+      TemplateArgStringMap::iterator Found = TemplateArgStrings.find(ND);
+      if (Found == TemplateArgStrings.end()) {
         // Mangle full template name into temporary buffer.
         llvm::SmallString<64> TemplateMangling;
         llvm::raw_svector_ostream Stream(TemplateMangling);
         MicrosoftCXXNameMangler Extra(Context, Stream);
         Extra.mangleTemplateInstantiationName(TD, *TemplateArgs);
 
         // Use the string backref vector to possibly get a back reference.
         mangleSourceName(TemplateMangling);
 
-      // Memoize back reference for this type.
+        // Memoize back reference for this type if one exist, else memoize
+        // the mangling itself.
         BackRefVec::iterator StringFound =
             llvm::find(NameBackReferences, TemplateMangling);
         if (StringFound != NameBackReferences.end()) {
           TemplateArgBackReferences[ND] =
               StringFound - NameBackReferences.begin();
+        } else {
+          TemplateArgStrings[ND] =
+              TemplateArgStringStorage.save(TemplateMangling.str());
         }
       } else {
-      Out << Found->second;
+        Out << Found->second; // Outputs a StringRef.
+      }
+    } else {
+      Out << Found->second; // Outputs a back reference (an int).
     }
     return;
   }
 
   switch (Name.getNameKind()) {
     case DeclarationName::Identifier: {
       if (const IdentifierInfo *II = Name.getAsIdentifierInfo()) {
         mangleSourceName(II->getName());

clang/test/CodeGenCXX/mangle-ms-back-references-pr13207.cpp

 using B4 = Food<B3, B2, B1, B0, B0, B0, B0, B0, B0, B0,  B3, B3, B3, B3, B3, B3, B3, B3, B3, B3>;
 using B5 = Food<B4, B3, B2, B1, B0, B0, B0, B0, B0, B0,  B4, B4, B4, B4, B4, B4, B4, B4, B4, B4>;
 using B6 = Food<B5, B4, B3, B2, B1, B0, B0, B0, B0, B0,  B5, B5, B5, B5, B5, B5, B5, B5, B5, B5>;
 
 // This too should take milliseconds, not minutes.
 void f(B6 a) {}
 
 // CHECK: "?f@@YAXU?$Food@U?$Food@U?$Food@U?$Food@U?$Food@U?$Food@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U2@U2@U2@U2@U2@U2@U2@U2@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U3@U3@U3@U3@U3@U3@U3@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@U?$Food@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U2@U2@U2@U2@U2@U2@U2@U2@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U4@U4@U4@U4@U4@U4@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@U?$Food@U?$Food@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U2@U2@U2@U2@U2@U2@U2@U2@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U3@U3@U3@U3@U3@U3@U3@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@U?$Food@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U2@U2@U2@U2@U2@U2@U2@U2@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U5@U5@U5@U5@U5@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@U?$Food@U?$Food@U?$Food@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U2@U2@U2@U2@U2@U2@U2@U2@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U3@U3@U3@U3@U3@U3@U3@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@U?$Food@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U2@U2@U2@U2@U2@U2@U2@U2@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U4@U4@U4@U4@U4@U4@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@U?$Food@U?$Food@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U2@U2@U2@U2@U2@U2@U2@U2@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U3@U3@U3@U3@U3@U3@U3@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@U?$Food@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U2@U2@U2@U2@U2@U2@U2@U2@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U?$Food@HHHHHHHHHHHHHHHHHHHH@@U6@U6@U6@U6@U1@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@@Z"
+
+
+// Similar to the previous case, except that the later arguments aren't
+// present in the earlier ones and hence aren't in the backref cache.
+template <class T1, class T2, class T3, class T4, class T5, class T6, class T7,
+          class T8, class T9, class T10, class T11, class T12, class T13,
+          class T14, class T15, class T16, class T17, class T18, class T19,
+          class T20>
+struct Fooe {};
+
+using C0 = Fooe<int, int, int, int, int, int, int, int, int, int,  int, int, int, int, int, int, int, int, int, int>;
+using C1 = Fooe<C0, C0, C0, C0, C0, C0, C0, C0, C0, C0,  C0, C0, C0, C0, C0, C0, C0, C0, C0, C0>;
+using C2 = Fooe<C0, C0, C0, C0, C0, C0, C0, C0, C0, C0,  C1, C1, C1, C1, C1, C1, C1, C1, C1, C1>;
+using C3 = Fooe<C1, C1, C0, C0, C0, C0, C0, C0, C0, C0,  C2, C2, C2, C2, C2, C2, C2, C2, C2, C2>;
+using C4 = Fooe<C2, C2, C1, C0, C0, C0, C0, C0, C0, C0,  C3, C3, C3, C3, C3, C3, C3, C3, C3, C3>;
+using C5 = Fooe<C3, C3, C2, C1, C0, C0, C0, C0, C0, C0,  C4, C4, C4, C4, C4, C4, C4, C4, C4, C4>;
+using C6 = Fooe<C4, C4, C3, C2, C1, C0, C0, C0, C0, C0,  C5, C5, C5, C5, C5, C5, C5, C5, C5, C5>;
+using C7 = Fooe<C5, C4, C3, C2, C1, C0, C0, C0, C0, C0,  C6, C6, C6, C6, C6, C6, C6, C6, C6, C6>;
+
+// This too should take milliseconds, not minutes.
+void f(C7 a) {}
+// CHECK: "??@f23afdfb44276eaa53a5575352cf0ebc@"