commit 487077698cf3c2b50de55de59729ddc9cd6bf95e
author Nico Weber <nicolasweber@gmx.de> Tue Jun 04 23:27:40 2019 +0000
committer Nico Weber <nicolasweber@gmx.de> Tue Jun 04 23:27:40 2019 +0000
tree ff112951a2113ee02843b21d9957bd4158547371
parent 5e312be0fa8442958fab31f08ec877cc4f6f31a2

msabi: Fix exponential mangling time for even more contrived inputs

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.

Differential Revision: https://reviews.llvm.org/D62780

llvm-svn: 362560

clang/lib/AST/MicrosoftMangle.cpp

diff --git a/clang/lib/AST/MicrosoftMangle.cpp b/clang/lib/AST/MicrosoftMangle.cpp
index ddc6e12..5e9358e 100644
--- a/clang/lib/AST/MicrosoftMangle.cpp
+++ b/clang/lib/AST/MicrosoftMangle.cpp
@@ -31,6 +31,7 @@
 #include "llvm/Support/xxhash.h"
 #include "llvm/Support/MD5.h"
 #include "llvm/Support/MathExtras.h"
+#include "llvm/Support/StringSaver.h"
 
 using namespace clang;
 
@@ -268,6 +269,11 @@
   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;
 
@@ -282,18 +288,21 @@
 
   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) {}
 
@@ -809,24 +818,34 @@
     // 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);
+      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);
 
-      // Memoize back reference for this type.
-      BackRefVec::iterator StringFound =
-          llvm::find(NameBackReferences, TemplateMangling);
-      if (StringFound != NameBackReferences.end()) {
-        TemplateArgBackReferences[ND] =
-            StringFound - NameBackReferences.begin();
+        // Use the string backref vector to possibly get a back reference.
+        mangleSourceName(TemplateMangling);
+
+        // 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; // Outputs a StringRef.
       }
     } else {
-      Out << Found->second;
+      Out << Found->second; // Outputs a back reference (an int).
     }
     return;
   }