This revision was automatically updated to reflect the committed changes.
Closed by commit rL362560: msabi: Fix exponential mangling time for even more
contrived inputs (authored by nico, committed by ).
Herald added a project: LLVM.
Herald added a subscriber: llvm-commits.
Changed prior to commit:
https://reviews.llvm.org/D62780?vs=202561&id=203044#toc
Repository:
rL LLVM
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D62780/new/
https://reviews.llvm.org/D62780
Files:
cfe/trunk/lib/AST/MicrosoftMangle.cpp
cfe/trunk/test/CodeGenCXX/mangle-ms-back-references-pr13207.cpp
Index: cfe/trunk/test/CodeGenCXX/mangle-ms-back-references-pr13207.cpp
===================================================================
--- cfe/trunk/test/CodeGenCXX/mangle-ms-back-references-pr13207.cpp
+++ cfe/trunk/test/CodeGenCXX/mangle-ms-back-references-pr13207.cpp
@@ -232,3 +232,25 @@
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@"
Index: cfe/trunk/lib/AST/MicrosoftMangle.cpp
===================================================================
--- cfe/trunk/lib/AST/MicrosoftMangle.cpp
+++ cfe/trunk/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);
-
- // Memoize back reference for this type.
- BackRefVec::iterator StringFound =
- llvm::find(NameBackReferences, TemplateMangling);
- if (StringFound != NameBackReferences.end()) {
- TemplateArgBackReferences[ND] =
- StringFound - NameBackReferences.begin();
+
+ 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 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;
}
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
