Replace long type names in IR with hashes

[sepavloff]

Summary

If a source file extensively uses templates, resulting LLVM IR may have
types with huge names. It may occur if a record type is defined in a class.
In this case its type name contains all declaration contexts and, if a
declaration context is a class specialization, it is specified with
template parameters.

This change implements transformation of long IR type names. If name length
exceeds some limit, it is truncated and SHA1 hash of its full name is
appended to the obtained abbreviated name. Such solution could reduce memory
footprint and still keep names usable for identification.

To implement this algorithm functions PrintTemplateArgumentList were changed.
They try to make their output a valid C++ code. For this purpose they ensure
that digraph '<:' and tokens '>>' are not formed by inserting space between
characters. The implementation prints template arguments into a separate
stream and then put its content into 'uplevel' stream adding space before
and/or after the text if necessary. Such implementation prevents from using
special stream implementations because the intermediate stream is always of
the same type. To cope with this problem, a new flag in PrintingPolicy is
introduced, which turns off checks for undesirable character sequences. In
this case the intermediate stream becomes unneeded and printing occurs into
the same stream.

[rnk]

It's not clear to me that this abbreviation functionality should live in Support. Clang probably wants enough control over this (assuming we're doing it) that the logic should live in clang.

I also think we might want to try solving this a completely different way: just don't bother emitting more than two template arguments for IR type names. We don't really need to worry about type name uniqueness or matching them across TUs.

lib/AST/TypePrinter.cpp

1532–1536

static is nicer than a short anonymous namespace.

1551

Just use SmallString<0> for Buffer. No wasted stack space, no extra unique_ptr. It will allocate memory if it needs it.

1586–1587

It's usually nicer to define free functions in namespaces as void clang::printTemplateArgumentList(.... This ensures that nobody can mess up the namespace scope or forget to include the header that declares the function. It also sometimes turns link errors into compile errors.

[rjmccall]

In Swift's IRGen, we have an option controlling whether to emit meaningful value names. That option can be set directly from the command line, but it defaults to whether we're emitting IR assembly (i.e. .ll, not .bc), which means that the clients most interested in getting meaningful value names — humans, presumably — always get good names, but nobody else pays for them. I have many, many times wished that we'd taken that same approach in Clang instead of basing it on build configuration.

If type names are a significant burden on compile times, should we just start taking that same approach? Just don't use real type names in .bc output unless we're asked to. Maybe we can eventually retroactively use the same option for value names.

I agree with Reid that it's really weird for there to be a raw_ostream that automatically rewrites the string contents to be a hash when some limit is reached; that does not feel like generalizable technology.

include/clang/AST/PrettyPrinter.h

231

This saves, what, a few spaces from a few thousand IR type names? I'm skeptical that this even offsets the code-size impact of adding this option.

include/clang/AST/Type.h

4623 ↗

(On Diff #124413)

I like this refactor, but since it's the majority of your patch, please split it out (it can use post-commit review) and make this patch just about your actual change.

lib/AST/TypePrinter.cpp

1551

Well, it might as well have some stack storage, but otherwise I agree.

[sepavloff]

Updated patch as part of it was committed in rL319178

[sepavloff]

In D40508#936617, @rnk wrote:

It's not clear to me that this abbreviation functionality should live in Support. Clang probably wants enough control over this (assuming we're doing it) that the logic should live in clang.

I also think we might want to try solving this a completely different way: just don't bother emitting more than two template arguments for IR type names. We don't really need to worry about type name uniqueness or matching them across TUs.

Actually the intention is to have unique type names across different TUs.
I will publish the relevant patch a bit latter, but the problem we are solving is in incorrect behavior of llvm-link. If one TU contains opaque type and the other has the type definition, these two types must be merged into one. The merge procedure relies on type names, so it is important to have the same type names for types in different TUs that are equivalent in the sense of C++.

include/clang/AST/PrettyPrinter.h

231

Not these few spaces themselves make the issue. The real evil is that to insert these spaces, printTemplateArgumentList had to print each template parameter into intermediate stream. We could try to use raw_abbrev_ostream to reduce memory consumption, it would not work because these intermediate streams are of type raw_svector_ostream and all these huge parameter texts would be materialized first and only then would go to compacting stream.
If no need to maintain compilable output, intermediate streams are not needed and all input can go directly to raw_abbrev_ostream.

lib/AST/TypePrinter.cpp

1532–1536

Yes, but this is function template. It won't create symbol in object file. Actually anonymous namespace has no effect here, it is only a documentation hint.

[sepavloff]

In D40508#937212, @rjmccall wrote:

In Swift's IRGen, we have an option controlling whether to emit meaningful value names. That option can be set directly from the command line, but it defaults to whether we're emitting IR assembly (i.e. .ll, not .bc), which means that the clients most interested in getting meaningful value names — humans, presumably — always get good names, but nobody else pays for them. I have many, many times wished that we'd taken that same approach in Clang instead of basing it on build configuration.

If type names are a significant burden on compile times, should we just start taking that same approach? Just don't use real type names in .bc output unless we're asked to. Maybe we can eventually retroactively use the same option for value names.

This is indeed reasonable approach, I will implement it the subsequent patch. Actually we could vary name length to achieve better readability or same memory, as the hash is calculated for entire type name and remains the same.

I agree with Reid that it's really weird for there to be a raw_ostream that automatically rewrites the string contents to be a hash when some limit is reached; that does not feel like generalizable technology.

It reduces type names and at the same time keeps type uniqueness across TUs. It also does not require massive changes in printing methods. Probably the intent will be more clear when I publish the next patch of this set.

[sepavloff]

D40567 presents a patch that adds template argument names to class template specializations. It also describes the use case in which type names are used to identify type across different TUs.
Adding template parameters obviously increase memory consumption. This patch provides a way to reduce it.
Note that this issue arises only if source is compiled to bitcode (.ll or .bc). If compilation is made to machine representation (.s or .o), IR type name are not needed.

[rjmccall]

My skepticism about the raw_ostream is not about the design of having a custom raw_ostream subclass, it's that that subclass could conceivably be re-used by some other client. It feels like it belongs as an internal hack in Clang absent some real evidence that someone else would use it.

lib/AST/TypePrinter.cpp

1532–1536

Nonetheless, we generally prefer to use 'static' on internal functions, even function templates, instead of putting them in anonymous namespaces.

[sepavloff]

In D40508#938040, @rjmccall wrote:

My skepticism about the raw_ostream is not about the design of having a custom raw_ostream subclass, it's that that subclass could conceivably be re-used by some other client. It feels like it belongs as an internal hack in Clang absent some real evidence that someone else would use it.

This class can be helpful in various cases where string identifier must persistently identify an object and memory consumption must be low. It may be:

• Name mangling,
• Symbol obfuscation,
• More convenient replacement for raw_sha1_ostream (the latter produces binary result, while raw_abbrev_ostream produces text),
• If we introduce an option that allows a user to specify how many symbols of full type name are kept in abbreviated name, then llvm-link may see types named as foo<int> and 2544896211ff669ed44dccd265f4c9163b340190, if they come from modules compiled with different options. To find out that these are the same type, it must have access to the same machinery.

lib/AST/TypePrinter.cpp

1532–1536

OK, fixed in rL319290.

[rjmccall]

In D40508#938675, @sepavloff wrote:

In D40508#938040, @rjmccall wrote:

My skepticism about the raw_ostream is not about the design of having a custom raw_ostream subclass, it's that that subclass could conceivably be re-used by some other client. It feels like it belongs as an internal hack in Clang absent some real evidence that someone else would use it.

This class can be helpful in various cases where string identifier must persistently identify an object and memory consumption must be low. It may be:

• Name mangling,
• Symbol obfuscation,
• More convenient replacement for raw_sha1_ostream (the latter produces binary result, while raw_abbrev_ostream produces text),

There's no requirement to persistently identify an object here.

• If we introduce an option that allows a user to specify how many symbols of full type name are kept in abbreviated name, then llvm-link may see types named as foo<int> and 2544896211ff669ed44dccd265f4c9163b340190, if they come from modules compiled with different options. To find out that these are the same type, it must have access to the same machinery.

The LLVM linking model does not actually depend on struct type names matching. My understanding is that, at best, it uses that as a heuristic for deciding whether to make an effort to unify two types, but it's not something that's ultimately supposed to impact IR semantics.

If we needed IR type names to match reliably, we would use a mangled name, not a pretty-print.

[sepavloff]

In D40508#938686, @rjmccall wrote:

In D40508#938675, @sepavloff wrote:

In D40508#938040, @rjmccall wrote:

My skepticism about the raw_ostream is not about the design of having a custom raw_ostream subclass, it's that that subclass could conceivably be re-used by some other client. It feels like it belongs as an internal hack in Clang absent some real evidence that someone else would use it.

This class can be helpful in various cases where string identifier must persistently identify an object and memory consumption must be low. It may be:

• If we introduce an option that allows a user to specify how many symbols of full type name are kept in abbreviated name, then llvm-link may see types named as foo<int> and 2544896211ff669ed44dccd265f4c9163b340190, if they come from modules compiled with different options. To find out that these are the same type, it must have access to the same machinery.

The LLVM linking model does not actually depend on struct type names matching. My understanding is that, at best, it uses that as a heuristic for deciding whether to make an effort to unify two types, but it's not something that's ultimately supposed to impact IR semantics.

It is mainly true with an exception, when llvm-link resolves opaque types it relies on type name only. And this behavior creates the issue that D40567 tries to resolve.

If we needed IR type names to match reliably, we would use a mangled name, not a pretty-print.

There is no requirement for IR type name to be an identifier, so pretty-print fits the need of type identification.

[rjmccall]

In D40508#938854, @sepavloff wrote:

In D40508#938686, @rjmccall wrote:

In D40508#938675, @sepavloff wrote:

In D40508#938040, @rjmccall wrote:

My skepticism about the raw_ostream is not about the design of having a custom raw_ostream subclass, it's that that subclass could conceivably be re-used by some other client. It feels like it belongs as an internal hack in Clang absent some real evidence that someone else would use it.

This class can be helpful in various cases where string identifier must persistently identify an object and memory consumption must be low. It may be:

• If we introduce an option that allows a user to specify how many symbols of full type name are kept in abbreviated name, then llvm-link may see types named as foo<int> and 2544896211ff669ed44dccd265f4c9163b340190, if they come from modules compiled with different options. To find out that these are the same type, it must have access to the same machinery.

The LLVM linking model does not actually depend on struct type names matching. My understanding is that, at best, it uses that as a heuristic for deciding whether to make an effort to unify two types, but it's not something that's ultimately supposed to impact IR semantics.

It is mainly true with an exception, when llvm-link resolves opaque types it relies on type name only. And this behavior creates the issue that D40567 tries to resolve.

It is not clear from that report what the actual problem is. Two incomplete types get merged by the linker? So what?

If we needed IR type names to match reliably, we would use a mangled name, not a pretty-print.

There is no requirement for IR type name to be an identifier, so pretty-print fits the need of type identification.

Not really; pretty-printing drops a lot of information that is pertinent in a stable identifier, like scopes and so on, and makes arbitrary decisions about other things, like where to insert spaces, namespace qualifiers, etc.

[sepavloff]

In D40508#939513, @rjmccall wrote:

In D40508#938854, @sepavloff wrote:

In D40508#938686, @rjmccall wrote:

The LLVM linking model does not actually depend on struct type names matching. My understanding is that, at best, it uses that as a heuristic for deciding whether to make an effort to unify two types, but it's not something that's ultimately supposed to impact IR semantics.

It is mainly true with an exception, when llvm-link resolves opaque types it relies on type name only. And this behavior creates the issue that D40567 tries to resolve.

It is not clear from that report what the actual problem is. Two incomplete types get merged by the linker? So what?

llvm-link is expected to produce IR that is semantically consistent with the program initially represented by a set of TUs. In this case it is not true. A function defined in source as foo(ABC<int>&) is converted by linking to foo<int*> &) and this breaks initial semantics.

If we needed IR type names to match reliably, we would use a mangled name, not a pretty-print.

There is no requirement for IR type name to be an identifier, so pretty-print fits the need of type identification.

Not really; pretty-printing drops a lot of information that is pertinent in a stable identifier, like scopes and so on, and makes arbitrary decisions about other things, like where to insert spaces, namespace qualifiers, etc.

Type name mangling indeed is attractive solution. It has at least the advantages:

• It is reversible (in theory).
• It can be more compact. For instance, there is no need to spell type name that is encountered already, a some kind of reference is sufficient.

And there are arguments against it:

• It make working with IR harder for developers as readability is broken,
• Type name in IR is mostly a decoration, with the exception of rare case of opaque type resolution, so type name mangling may be considered as an overkill.

On the other hand pretty-printing can be finely tuned so that all necessary information appears in its result. As there is no requirements on compatibility of type names in bitcode files, things like number of spaces look not so important, it is enough that the same version of clang was used to compile bc files that are linked by llvm-link. After all it is readable.

[rjmccall]

Are you trying to use LLVM struct type identity to infer information about the source program? That is not and has never been a guarantee.

[sepavloff]

Using llvm type names is considered a wrong direction.

include/clang/AST/PrettyPrinter.h

: Indentation(2), SuppressSpecifiers(false),
       SuppressTemplateArgsInCXXConstructors(false),
       Bool(LO.Bool), Restrict(LO.C99),
       Alignof(LO.CPlusPlus11), UnderscoreAlignof(LO.C11),
       UseVoidForZeroParams(!LO.CPlusPlus),
       TerseOutput(false), PolishForDeclaration(false),
       Half(LO.Half), MSWChar(LO.MicrosoftExt && !LO.WChar),
       IncludeNewlines(true), MSVCFormatting(false),
       ConstantsAsWritten(false), SuppressImplicitBase(false),
-      FullyQualifiedName(false) { }
+      FullyQualifiedName(false), NotForCompilation(false) { }
 
   /// Adjust this printing policy for cases where it's known that we're
   /// printing C++ code (for instance, if AST dumping reaches a C++-only
   /// construct). This should not be used if a real LangOptions object is
   /// available.
   void adjustForCPlusPlus() {
     SuppressTagKeyword = true;
     Bool = true;
struct PrintingPolicy {
   bool ConstantsAsWritten : 1;
 
   /// When true, don't print the implicit 'self' or 'this' expressions.
   bool SuppressImplicitBase : 1;
 
   /// When true, print the fully qualified name of function declarations.
   /// This is the opposite of SuppressScope and thus overrules it.
   bool FullyQualifiedName : 1;
+
+  /// When true, the print result will not be used as compiler input, so do not
+  /// make things like breaking digraphs and '>>' in template parameters.
+  bool NotForCompilation : 1;
 };
 
 } // end namespace clang
 
 #endif

lib/AST/TypePrinter.cpp

 
 static
 const TemplateArgument &getArgument(const TemplateArgument &A) { return A; }
 
 static const TemplateArgument &getArgument(const TemplateArgumentLoc &A) {
   return A.getArgument();
 }
 
 namespace {
 template<typename TA>
 void printTo(raw_ostream &OS, ArrayRef<TA> Args, const PrintingPolicy &Policy,
              bool SkipBrackets) {
   const char *Comma = Policy.MSVCFormatting ? "," : ", ";
   if (!SkipBrackets)
     OS << '<';
 
   bool NeedSpace = false;
   bool FirstArg = true;
   for (const auto &Arg : Args) {
+    SmallString<0> Buffer;
+    std::unique_ptr<llvm::raw_svector_ostream> BufOS;
+    if (!Policy.NotForCompilation) {
       // Print the argument into a string.
-    SmallString<128> Buf;
-    llvm::raw_svector_ostream ArgOS(Buf);
+      BufOS.reset(new llvm::raw_svector_ostream(Buffer));
+    }
+    llvm::raw_ostream &ArgOS = Policy.NotForCompilation ? OS : *BufOS;
     const TemplateArgument &Argument = getArgument(Arg);
     if (Argument.getKind() == TemplateArgument::Pack) {
       if (Argument.pack_size() && !FirstArg)
         OS << Comma;
       printTo(ArgOS, Argument.getPackAsArray(), Policy, true);
     } else {
       if (!FirstArg)
         OS << Comma;
       Argument.print(Policy, ArgOS);
     }
-    StringRef ArgString = ArgOS.str();
+    if (!Policy.NotForCompilation) {
+      StringRef ArgString = BufOS->str();
 
       // If this is the first argument and its string representation
       // begins with the global scope specifier ('::foo'), add a space
       // to avoid printing the diagraph '<:'.
       if (FirstArg && !ArgString.empty() && ArgString[0] == ':')
         OS << ' ';
 
       OS << ArgString;
 
       NeedSpace = (!ArgString.empty() && ArgString.back() == '>');
+    }
     FirstArg = false;
   }
 
   // If the last character of our string is '>', add another space to
   // keep the two '>''s separate tokens. We don't *have* to do this in
   // C++0x, but it's still good hygiene.
   if (NeedSpace)
     OS << ' ';
 
   if (!SkipBrackets)
     OS << '>';
 }
 }
 
 void clang::printTemplateArgumentList(raw_ostream &OS,
                                       const TemplateArgumentListInfo &Args,
                                       const PrintingPolicy &Policy) {
   return printTo(OS, Args.arguments(), Policy, false);
 }
 
 void clang::printTemplateArgumentList(raw_ostream &OS,
                                       ArrayRef<TemplateArgument> Args,
                                       const PrintingPolicy &Policy) {

lib/CodeGen/CodeGenTypes.cpp

 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclObjC.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/RecordLayout.h"
 #include "clang/CodeGen/CGFunctionInfo.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Module.h"
+#include "llvm/Support/raw_abbrev_ostream.h"
 using namespace clang;
 using namespace CodeGen;
 
 CodeGenTypes::CodeGenTypes(CodeGenModule &cgm)
   : CGM(cgm), Context(cgm.getContext()), TheModule(cgm.getModule()),
     Target(cgm.getTarget()), TheCXXABI(cgm.getCXXABI()),
     TheABIInfo(cgm.getTargetCodeGenInfo().getABIInfo()) {
   SkippedLayout = false;

 
 const CodeGenOptions &CodeGenTypes::getCodeGenOpts() const {
   return CGM.getCodeGenOpts();
 }
 
 void CodeGenTypes::addRecordTypeName(const RecordDecl *RD,
                                      llvm::StructType *Ty,
                                      StringRef suffix) {
-  SmallString<256> TypeName;
-  llvm::raw_svector_ostream OS(TypeName);
+  PrintingPolicy Policy = RD->getASTContext().getPrintingPolicy();
+  Policy.NotForCompilation = true;
+  llvm::raw_abbrev_ostream OS;
+  OS.setHash().setTrunc().setBeginMarker("...");
+
+  // Set truncation limit. Long value helps in debugging but can result in
+  // higher memory consumption.
+  OS.setLimit(400);
+
   OS << RD->getKindName() << '.';
-  
   // Name the codegen type after the typedef name
   // if there is no tag type name available
   if (RD->getIdentifier()) {
+    OS.startAbbrev();
     // FIXME: We should not have to check for a null decl context here.
     // Right now we do it because the implicit Obj-C decls don't have one.
     if (RD->getDeclContext())
-      RD->printQualifiedName(OS);
+      RD->printQualifiedName(OS, Policy);
     else
       RD->printName(OS);
   } else if (const TypedefNameDecl *TDD = RD->getTypedefNameForAnonDecl()) {
+    OS.startAbbrev();
     // FIXME: We should not have to check for a null decl context here.
     // Right now we do it because the implicit Obj-C decls don't have one.
     if (TDD->getDeclContext())
-      TDD->printQualifiedName(OS);
+      TDD->printQualifiedName(OS, Policy);
     else
       TDD->printName(OS);
   } else
     OS << "anon";
+  OS.stopAbbrev();
 
   if (!suffix.empty())
     OS << suffix;
 
   Ty->setName(OS.str());
 }
 
 /// ConvertTypeForMem - Convert type T into a llvm::Type.  This differs from

test/CodeGenCXX/template-types.cpp

+// RUN: %clang_cc1 -std=c++11 -triple i686-linux-gnu -S -emit-llvm %s -o - | FileCheck %s
+
+// Taken from the test pr29160.cpp
+template <typename... Ts>
+struct Foo {
+  template <typename... T>
+  static void ignore() {}
+  Foo() { ignore<Ts...>(); }
+  struct Inner {};
+};
+
+struct Base {
+  Base();
+  ~Base();
+};
+
+#define STAMP(thiz, prev) using thiz = Foo< \
+  prev, prev, prev, prev, prev, prev, prev, prev, prev, prev, prev, prev, \
+  prev, prev, prev, prev, prev, prev, prev, prev, prev, prev, prev, prev, \
+  prev, prev, prev, prev, prev, prev, prev, prev, prev, prev, prev, prev \
+  >;
+STAMP(A, Base);
+STAMP(B, A);
+STAMP(C, B);
+
+int main() {
+  C::Inner val_1;
+}
+
+// CHECK: %"struct.Foo<Foo<Foo<Base, Base, {{.*}}, Base, Base,...616A5BC91324C3B62589C85C57D927D7C6CE3CA9" = type { i8 }