msabi: Fix exponential mangling time for certain pathological inputs

[thakis]

Summary

Template back references used to be recursively recomputed, add a
memoization cache to cut down on this.

Since there are now two different types of argument maps, rename the
existing TypeBackReferences to FunArgBackReferences, and rename
mangleArgumentType() to mangleFunctionArgumentType().

Fixes PR42091, the input there now takes 50ms instead of 7s to compile.

No intended behavior change.

[rnk]

lgtm

Thanks for this, I remember a user complained about this a long time ago but we never did anything.

clang/lib/AST/MicrosoftMangle.cpp

class MicrosoftCXXNameMangler {
   /// for that specialization.
   const NamedDecl *Structor;
   unsigned StructorType;
 
   typedef llvm::SmallVector<std::string, 10> BackRefVec;
   BackRefVec NameBackReferences;
 
   typedef llvm::DenseMap<const void *, unsigned> ArgBackRefMap;
-  ArgBackRefMap TypeBackReferences;
+  ArgBackRefMap FunArgBackReferences;
+  ArgBackRefMap TemplateArgBackReferences;
 
   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().
private:
   void manglePointerExtQualifiers(Qualifiers Quals, QualType PointeeType);
 
   void mangleUnscopedTemplateName(const TemplateDecl *ND);
   void
   mangleTemplateInstantiationName(const TemplateDecl *TD,
                                   const TemplateArgumentList &TemplateArgs);
   void mangleObjCMethodName(const ObjCMethodDecl *MD);
 
-  void mangleArgumentType(QualType T, SourceRange Range);
+  void mangleFunctionArgumentType(QualType T, SourceRange Range);
   void manglePassObjectSizeArg(const PassObjectSizeAttr *POSA);
 
   bool isArtificialTagType(QualType T) const;
 
   // Declare manglers for every type class.
 #define ABSTRACT_TYPE(CLASS, PARENT)
 #define NON_CANONICAL_TYPE(CLASS, PARENT)
 #define TYPE(CLASS, PARENT) void mangleType(const CLASS##Type *T, \
if (isa<FunctionTemplateDecl>(TD)) {
       return;
     }
 
     // Here comes the tricky thing: if we need to mangle something like
     //   void foo(A::X<Y>, B::X<Y>),
     // the X<Y> part is aliased. However, if you need to mangle
     //   void foo(A::X<A::Y>, A::X<B::Y>),
     // the A::X<> part is not aliased.
-    // That said, from the mangler's perspective we have a structure like this:
+    // That is, from the mangler's perspective we have a structure like this:
     //   namespace[s] -> type[ -> template-parameters]
     // but from the Clang perspective we have
     //   type [ -> template-parameters]
     //      \-> namespace[s]
     // 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()) {
+      // 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.
+      BackRefVec::iterator StringFound =
+          llvm::find(NameBackReferences, TemplateMangling);
+      if (StringFound != NameBackReferences.end()) {
+        TemplateArgBackReferences[ND] =
+            StringFound - NameBackReferences.begin();
+      }
+    } else {
+      Out << Found->second;
+    }
     return;
   }
 
   switch (Name.getNameKind()) {
     case DeclarationName::Identifier: {
       if (const IdentifierInfo *II = Name.getAsIdentifierInfo()) {
         mangleSourceName(II->getName());
         break;

 
 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;
+  ArgBackRefMap OuterFunArgsContext;
+  ArgBackRefMap OuterTemplateArgsContext;
   BackRefVec OuterTemplateContext;
   PassObjectSizeArgsSet OuterPassObjectSizeArgs;
   NameBackReferences.swap(OuterTemplateContext);
-  TypeBackReferences.swap(OuterArgsContext);
+  FunArgBackReferences.swap(OuterFunArgsContext);
+  TemplateArgBackReferences.swap(OuterTemplateArgsContext);
   PassObjectSizeArgs.swap(OuterPassObjectSizeArgs);
 
   mangleUnscopedTemplateName(TD);
   mangleTemplateArgs(TD, TemplateArgs);
 
   // Restore the previous back reference contexts.
   NameBackReferences.swap(OuterTemplateContext);
-  TypeBackReferences.swap(OuterArgsContext);
+  FunArgBackReferences.swap(OuterFunArgsContext);
+  TemplateArgBackReferences.swap(OuterTemplateArgsContext);
   PassObjectSizeArgs.swap(OuterPassObjectSizeArgs);
 }
 
 void
 MicrosoftCXXNameMangler::mangleUnscopedTemplateName(const TemplateDecl *TD) {
   // <unscoped-template-name> ::= ?$ <unqualified-name>
   Out << "?$";
   mangleUnqualifiedName(TD);
if (HasConst && HasVolatile) {
     Out << 'R';
   } else if (HasConst) {
     Out << 'Q';
   } else {
     Out << 'P';
   }
 }
 
-void MicrosoftCXXNameMangler::mangleArgumentType(QualType T,
+void MicrosoftCXXNameMangler::mangleFunctionArgumentType(QualType T,
                                                          SourceRange Range) {
   // MSVC will backreference two canonically equivalent types that have slightly
   // different manglings when mangled alone.
 
   // Decayed types do not match up with non-decayed versions of the same type.
   //
   // e.g.
   // void (*x)(void) will not form a backreference with void x(void)
   void *TypePtr;
if (const auto *DT = T->getAs<DecayedType>()) {
     // e.g.
     // int [] -> int * const
     if (OriginalType->isArrayType())
       T = T.withConst();
   } else {
     TypePtr = T.getCanonicalType().getAsOpaquePtr();
   }
 
-  ArgBackRefMap::iterator Found = TypeBackReferences.find(TypePtr);
+  ArgBackRefMap::iterator Found = FunArgBackReferences.find(TypePtr);
 
-  if (Found == TypeBackReferences.end()) {
+  if (Found == FunArgBackReferences.end()) {
     size_t OutSizeBefore = Out.tell();
 
     mangleType(T, Range, QMM_Drop);
 
     // See if it's worth creating a back reference.
     // Only types longer than 1 character are considered
     // and only 10 back references slots are available:
     bool LongerThanOneChar = (Out.tell() - OutSizeBefore > 1);
-    if (LongerThanOneChar && TypeBackReferences.size() < 10) {
-      size_t Size = TypeBackReferences.size();
-      TypeBackReferences[TypePtr] = Size;
+    if (LongerThanOneChar && FunArgBackReferences.size() < 10) {
+      size_t Size = FunArgBackReferences.size();
+      FunArgBackReferences[TypePtr] = Size;
     }
   } else {
     Out << Found->second;
   }
 }
 
 void MicrosoftCXXNameMangler::manglePassObjectSizeArg(
     const PassObjectSizeAttr *POSA) {
   int Type = POSA->getType();
   bool Dynamic = POSA->isDynamic();
 
   auto Iter = PassObjectSizeArgs.insert({Type, Dynamic}).first;
   auto *TypePtr = (const void *)&*Iter;
-  ArgBackRefMap::iterator Found = TypeBackReferences.find(TypePtr);
+  ArgBackRefMap::iterator Found = FunArgBackReferences.find(TypePtr);
 
-  if (Found == TypeBackReferences.end()) {
+  if (Found == FunArgBackReferences.end()) {
     std::string Name =
         Dynamic ? "__pass_dynamic_object_size" : "__pass_object_size";
     mangleArtificialTagType(TTK_Enum, Name + llvm::utostr(Type), {"__clang"});
 
-    if (TypeBackReferences.size() < 10) {
-      size_t Size = TypeBackReferences.size();
-      TypeBackReferences[TypePtr] = Size;
+    if (FunArgBackReferences.size() < 10) {
+      size_t Size = FunArgBackReferences.size();
+      FunArgBackReferences[TypePtr] = Size;
     }
   } else {
     Out << Found->second;
   }
 }
 
 void MicrosoftCXXNameMangler::mangleAddressSpaceType(QualType T,
                                                      Qualifiers Quals,
if (IsCtorClosure) {
       // void.
       Out << 'X';
 
       if (StructorType == Ctor_DefaultClosure) {
         // Default constructor closure always has no arguments.
         Out << 'X';
       } else if (StructorType == Ctor_CopyingClosure) {
         // Copy constructor closure always takes an unqualified reference.
-        mangleArgumentType(getASTContext().getLValueReferenceType(
+        mangleFunctionArgumentType(getASTContext().getLValueReferenceType(
                                        Proto->getParamType(0)
                                            ->getAs<LValueReferenceType>()
                                            ->getPointeeType(),
                                        /*SpelledAsLValue=*/true),
                                    Range);
         Out << '@';
       } else {
         llvm_unreachable("unexpected constructor closure!");
       }
       Out << 'Z';
       return;
     }
     Out << '@';
if (!Proto) {
     // within an overloadable function in C. We mangle these as the absence of
     // any parameter types (not even an empty parameter list).
     Out << '@';
   } else if (Proto->getNumParams() == 0 && !Proto->isVariadic()) {
     Out << 'X';
   } else {
     // Happens for function pointer type arguments for example.
     for (unsigned I = 0, E = Proto->getNumParams(); I != E; ++I) {
-      mangleArgumentType(Proto->getParamType(I), Range);
+      mangleFunctionArgumentType(Proto->getParamType(I), Range);
       // Mangle each pass_object_size parameter as if it's a parameter of enum
       // type passed directly after the parameter with the pass_object_size
       // attribute. The aforementioned enum's name is __pass_object_size, and we
       // pretend it resides in a top-level namespace called __clang.
       //
       // FIXME: Is there a defined extension notation for the MS ABI, or is it
       // necessary to just cross our fingers and hope this type+namespace
       // combination doesn't conflict with anything?

 void MicrosoftCXXNameMangler::mangleType(const ObjCObjectType *T,
                                          Qualifiers Quals, SourceRange Range) {
   if (T->isKindOfType())
     return mangleObjCKindOfType(T, Quals, Range);
 
   if (T->qual_empty() && !T->isSpecialized())
     return mangleType(T->getBaseType(), Range, QMM_Drop);
 
-  ArgBackRefMap OuterArgsContext;
+  ArgBackRefMap OuterFunArgsContext;
+  ArgBackRefMap OuterTemplateArgsContext;
   BackRefVec OuterTemplateContext;
 
-  TypeBackReferences.swap(OuterArgsContext);
+  FunArgBackReferences.swap(OuterFunArgsContext);
+  TemplateArgBackReferences.swap(OuterTemplateArgsContext);
   NameBackReferences.swap(OuterTemplateContext);
 
   mangleTagTypeKind(TTK_Struct);
 
   Out << "?$";
   if (T->isObjCId())
     mangleSourceName("objc_object");
   else if (T->isObjCClass())
     mangleSourceName("objc_class");
   else
     mangleSourceName(T->getInterface()->getName());
 
   for (const auto &Q : T->quals())
     mangleObjCProtocol(Q);
 
   if (T->isSpecialized())
     for (const auto &TA : T->getTypeArgs())
       mangleType(TA, Range, QMM_Drop);
 
   Out << '@';
 
   Out << '@';
 
-  TypeBackReferences.swap(OuterArgsContext);
+  FunArgBackReferences.swap(OuterFunArgsContext);
+  TemplateArgBackReferences.swap(OuterTemplateArgsContext);
   NameBackReferences.swap(OuterTemplateContext);
 }
 
 void MicrosoftCXXNameMangler::mangleType(const BlockPointerType *T,
                                          Qualifiers Quals, SourceRange Range) {
   QualType PointeeType = T->getPointeeType();
   manglePointerCVQualifiers(Quals);
   manglePointerExtQualifiers(Quals, PointeeType);

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

 }
 RetVal ident(int x) { return RetVal(); }
 void fun_instantiate2() {
   fun_tmpl_recurse<int, fun_tmpl_recurse<int, ident> >(10);
 }
 // CHECK: "??$fun_tmpl_recurse@H$1??$fun_tmpl_recurse@H$1?ident@fn_space@@YA?AURetVal@2@H@Z@fn_space@@YA?AURetVal@1@H@Z@fn_space@@YA?AURetVal@0@H@Z"
 // CHECK: "??$fun_tmpl_recurse@H$1?ident@fn_space@@YA?AURetVal@2@H@Z@fn_space@@YA?AURetVal@0@H@Z"
 }
+
+
+template <class T1, class T2, class T3, class T4, class T5, class T6, class T7,
+          class T8, class T9, class T10>
+struct Fooob {};
+
+using A0 = Fooob<int, int, int, int, int, int, int, int, int, int>;
+using A1 = Fooob<A0, A0, A0, A0, A0, A0, A0, A0, A0, A0>;
+using A2 = Fooob<A1, A1, A1, A1, A1, A1, A1, A1, A1, A1>;
+using A3 = Fooob<A2, A2, A2, A2, A2, A2, A2, A2, A2, A2>;
+using A4 = Fooob<A3, A3, A3, A3, A3, A3, A3, A3, A3, A3>;
+using A5 = Fooob<A4, A4, A4, A4, A4, A4, A4, A4, A4, A4>;
+using A6 = Fooob<A5, A5, A5, A5, A5, A5, A5, A5, A5, A5>;
+using A7 = Fooob<A6, A6, A6, A6, A6, A6, A6, A6, A6, A6>;
+using A8 = Fooob<A7, A7, A7, A7, A7, A7, A7, A7, A7, A7>;
+using A9 = Fooob<A8, A8, A8, A8, A8, A8, A8, A8, A8, A8>;
+using A10 = Fooob<A9, A9, A9, A9, A9, A9, A9, A9, A9, A9>;
+
+// This should take milliseconds, not minutes.
+void f(A9 a) {}
+// CHECK: "?f@@YAXU?$Fooob@U?$Fooob@U?$Fooob@U?$Fooob@U?$Fooob@U?$Fooob@U?$Fooob@U?$Fooob@U?$Fooob@U?$Fooob@HHHHHHHHHH@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@U1@U1@U1@U1@U1@U1@U1@U1@U1@@@@Z"
+
+
+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 Food {};
+
+using B0 = Food<int, int, int, int, int, int, int, int, int, int,  int, int, int, int, int, int, int, int, int, int>;
+using B1 = Food<B0, B0, B0, B0, B0, B0, B0, B0, B0, B0,  B0, B0, B0, B0, B0, B0, B0, B0, B0, B0>;
+using B2 = Food<B1, B0, B0, B0, B0, B0, B0, B0, B0, B0,  B1, B1, B1, B1, B1, B1, B1, B1, B1, B1>;
+using B3 = Food<B2, B1, B0, B0, B0, B0, B0, B0, B0, B0,  B2, B2, B2, B2, B2, B2, B2, B2, B2, B2>;
+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"