Initialize much of AssemblyWriter lazily.

[jlebar]

Summary

The AssemblyWriter constructor is in the critical path of
Value::operator<<, which in turn is in the critical path of most debug
messages. It currently scans the entire module multiple times, even
though most of that work is usually unnecessary. This change makes us
lazier.

With this change, I can compile a big Thrust file with
-debug-only=inline in a few minutes. Before, I gave up after 30m.

[• rafael]

lib/IR/AsmWriter.cpp

426

Why the fancy decltype? Can this be just

TypeFinder getNamedTypes() {....

?

[jlebar]

Nix unnecessary trailing return + decltype.

lib/IR/AsmWriter.cpp

426

I have no idea why I did that. If I should use the fancy thing anywhere, it should be on the function below, which at least has an ugly return type.

Anyway, fixed, thank you.

[timshen]

lib/IR/AsmWriter.cpp

416

Do you think it's better to create a Lazy<T> template type, which has an Optional<T>, but automatically checks & value-initializes the underlying T on operator->()/operator*() ? It seems able to reduce the users' mind burden compared to using raw Optional.

[timshen]

Obviously if I add an inline comment without a non-inline comment, I'm still shown as "review requested". Add this comment to make Phabricator happy.

[jlebar]

Use Lazy<T> in AssemblyWriter patch.

lib/IR/AsmWriter.cpp

416

Hm. If we go this route, I think we don't just want to value-initialize T -- that opens us up to a bug where you accidentally use one of these containers before it's been filled with data.

Now, a Lazy<T> that takes an std::function and uses *that* to initialize T...that's interesting. I did it, but I am not sure it's clearer.

Have a look, see what you think? I saved my state so we can go back no problem.

[timshen]

inline comments.

lib/IR/AsmWriter.cpp

82

Man, by last time I looked at libstdc++, it's like 48 bytes on 64-bit machines...

Even if Lazy keeps track of the raw lambda, the lambda may still capture stuff and have memory footprint.

Now I think it's a bad idea. It's as bad as that dtor doesn't have parameters so each container, which may be in a parent container, needs to keep its allocator.

Sorry, I think the Optional version is better. :(

BTW, how hard is it to make the user side lazy, rather the library side?

[jlebar]

lib/IR/AsmWriter.cpp

82

Man, by last time I looked at libstdc++, it's like 48 bytes on 64-bit machines...

Eh, I don't think this is a big deal, compared to all the other work we're doing here. :)

Even if Lazy keeps track of the raw lambda, the lambda may still capture stuff and have memory footprint.

Indeed, but these lambdas don't, so we're ok in that respect!

It's as bad as that dtor doesn't have parameters so each container, which may be in a parent container, needs to keep its allocator.

:) Here I'm much more concerned about readability. Like, we're making this *way* faster in any case; the extra few bytes or whatever isn't a big deal.

BTW, how hard is it to make the user side lazy, rather the library side?

I'm not sure what you mean; can you give me an example?

[timshen]

lib/IR/AsmWriter.cpp

82

:) Here I'm much more concerned about readability. Like, we're making this *way* faster in any case; the extra few bytes or whatever isn't a big deal.

If you don't think extra is a big deal, go for it :). But still be aware that the moment when the underlying object T gets initialized is relatively hard to track down (that's the whole point, isn't it ;).

I'm not sure what you mean; can you give me an example?

By saying "user" I mean "Value::operator<<", and library is "AssemblyWriter". Is there a way to keep an AssemblyWriter instance in Value::operator<<'s context (Module?), so that you don't have to change AssemblyWriter?

[jlebar]

Roll back to previous version.

[jlebar]

Is there a way to keep an AssemblyWriter instance in Value::operator<<'s context (Module?), so that you don't have to change AssemblyWriter?

Ah. That would be nice. But I think it's hard because AssemblyWriter assumes the module doesn't change.

[timshen]

I don't have more comments. Should I just stamp this patch?

lib/IR/AsmWriter.cpp

461

Optional:

LazyNamedTypes.erase(
  std::remove_if(LazyNamedTypes.begin(), LazyNamedTypes.end(),
    [&](...) { ... }),
  LazyNamedTypes.end());

?

I don't know if you like this half-functional style or pure imperative style.

[jlebar]

Should I just stamp this patch?

If you're comfortable doing so!

lib/IR/AsmWriter.cpp

461

Normally I like that, but here we're doing so much other stuff (building up LazyNumberedTypes), I think it's probably clearer as-is.

[timshen]

Actually I don't feel comfortable to stamp it - I've never seen this code before; but LGTM. :)

lib/IR/AsmWriter.cpp

 static void orderValue(const Value *V, OrderMap &OM) {
   if (OM.lookup(V).first)
     return;
 
   if (const Constant *C = dyn_cast<Constant>(V))
     if (C->getNumOperands() && !isa<GlobalValue>(C))
       for (const Value *Op : C->operands())
         if (!isa<BasicBlock>(Op) && !isa<GlobalValue>(Op))
           orderValue(Op, OM);
 
   // Note: we cannot cache this lookup above, since inserting into the map
   // changes the map's size, and thus affects the other IDs.
   OM.index(V);
 }
 
 static OrderMap orderModule(const Module *M) {
   // This needs to match the order used by ValueEnumerator::ValueEnumerator()

 /// (if it has special chars in it). Print it out.
 static void PrintLLVMName(raw_ostream &OS, const Value *V) {
   PrintLLVMName(OS, V->getName(),
                 isa<GlobalValue>(V) ? GlobalPrefix : LocalPrefix);
 }
 
 
 namespace {
+// Instances of this class are sometimes created very frequently -- e.g. on
+// every call to Instruction::operator<< -- so we lazily initialize our
+// expensive data structures, in the hopes we won't need them.
 class TypePrinting {
   TypePrinting(const TypePrinting &) = delete;
   void operator=(const TypePrinting&) = delete;
-public:
 
-  /// NamedTypes - The named types that are used by the current module.
-  TypeFinder NamedTypes;
+  void EnsureTypesInitialized();
+
+  const Module *TheModule; // May be null.
+  Optional<TypeFinder> LazyNamedTypes;
+  Optional<DenseMap<StructType *, unsigned>> LazyNumberedTypes;
 
-  /// NumberedTypes - The numbered types, along with their value.
-  DenseMap<StructType*, unsigned> NumberedTypes;
+public:
+  explicit TypePrinting(const Module *M = nullptr) : TheModule(M) {}
 
-  TypePrinting() = default;
+  /// The named types that are used by the current module.
+  const TypeFinder &GetNamedTypes() {
+    EnsureTypesInitialized();
+    return *LazyNamedTypes;
+  }
 
-  void incorporateTypes(const Module &M);
+  /// The numbered types, along with their value.
+  const DenseMap<StructType *, unsigned> &GetNumberedTypes() {
+    EnsureTypesInitialized();
+    return *LazyNumberedTypes;
+  }
 
   void print(Type *Ty, raw_ostream &OS);
 
   void printStructBody(StructType *Ty, raw_ostream &OS);
 };
 } // namespace
 
-void TypePrinting::incorporateTypes(const Module &M) {
-  NamedTypes.run(M, false);
+void TypePrinting::EnsureTypesInitialized() {
+  if (LazyNamedTypes) {
+    assert(LazyNumberedTypes &&
+           "Named and numbered types are initialized together.");
+    return;
+  }
+  LazyNamedTypes.emplace();
+  LazyNumberedTypes.emplace();
+  if (!TheModule)
+    return;
+
+  LazyNamedTypes->run(*TheModule, false);
 
   // The list of struct types we got back includes all the struct types, split
   // the unnamed ones out to a numbering and remove the anonymous structs.
   unsigned NextNumber = 0;
 
-  std::vector<StructType*>::iterator NextToUse = NamedTypes.begin(), I, E;
-  for (I = NamedTypes.begin(), E = NamedTypes.end(); I != E; ++I) {
+  auto NextToUse = LazyNamedTypes->begin();
+  for (auto I = LazyNamedTypes->begin(), E = LazyNamedTypes->end(); I != E;
+       ++I) {
     StructType *STy = *I;
 
     // Ignore anonymous types.
     if (STy->isLiteral())
       continue;
 
     if (STy->getName().empty())
-      NumberedTypes[STy] = NextNumber++;
+      (*LazyNumberedTypes)[STy] = NextNumber++;
     else
       *NextToUse++ = STy;
   }
 
-  NamedTypes.erase(NextToUse, NamedTypes.end());
+  LazyNamedTypes->erase(NextToUse, LazyNamedTypes->end());
 }
 
-
 /// CalcTypeName - Write the specified type to the specified raw_ostream, making
 /// use of type names or up references to shorten the type name where possible.
 void TypePrinting::print(Type *Ty, raw_ostream &OS) {
   switch (Ty->getTypeID()) {
   case Type::VoidTyID:      OS << "void"; return;
   case Type::HalfTyID:      OS << "half"; return;
   case Type::FloatTyID:     OS << "float"; return;
   case Type::DoubleTyID:    OS << "double"; return;
case Type::StructTyID: {
     StructType *STy = cast<StructType>(Ty);
 
     if (STy->isLiteral())
       return printStructBody(STy, OS);
 
     if (!STy->getName().empty())
       return PrintLLVMName(OS, STy->getName(), LocalPrefix);
 
-    DenseMap<StructType*, unsigned>::iterator I = NumberedTypes.find(STy);
-    if (I != NumberedTypes.end())
+    auto I = GetNumberedTypes().find(STy);
+    if (I != GetNumberedTypes().end())
       OS << '%' << I->second;
     else  // Not enumerated, print the hex address.
       OS << "%\"type " << STy << '\"';
     return;
   }
   case Type::PointerTyID: {
     PointerType *PTy = cast<PointerType>(Ty);
     print(PTy->getElementType(), OS);
assert((FromValue || !isa<LocalAsMetadata>(V)) &&
          "Unexpected function-local metadata outside of value argument");
 
   TypePrinter->print(V->getValue()->getType(), Out);
   Out << ' ';
   WriteAsOperandInternal(Out, V->getValue(), TypePrinter, Machine, Context);
 }
 
 namespace {
+// New instances of this class are created frequently -- e.g. we get a new one
+// every time we run Instruction::operator<<.  So we do as much lazy
+// initialization as is reasonable.
 class AssemblyWriter {
   formatted_raw_ostream &Out;
   const Module *TheModule;
   std::unique_ptr<SlotTracker> SlotTrackerStorage;
   SlotTracker &Machine;
   TypePrinting TypePrinter;
   AssemblyAnnotationWriter *AnnotationWriter;
-  SetVector<const Comdat *> Comdats;
   bool IsForDebug;
   bool ShouldPreserveUseListOrder;
   UseListOrderStack UseListOrders;
   SmallVector<StringRef, 8> MDNames;
 
+  // Lazily initialized.  Don't access directly; call GetComdats().
+  Optional<SetVector<const Comdat *>> LazyComdats;
+
+  const SetVector<const Comdat *> &GetComdats();
+
 public:
   /// Construct an AssemblyWriter with an external SlotTracker
   AssemblyWriter(formatted_raw_ostream &o, SlotTracker &Mac, const Module *M,
                  AssemblyAnnotationWriter *AAW, bool IsForDebug,
                  bool ShouldPreserveUseListOrder = false);
 
   void printMDNodeBody(const MDNode *MD);
   void printNamedMDNode(const NamedMDNode *NMD);
private:
   // intrinsic indicating base and derived pointer names.
   void printGCRelocateComment(const GCRelocateInst &Relocate);
 };
 } // namespace
 
 AssemblyWriter::AssemblyWriter(formatted_raw_ostream &o, SlotTracker &Mac,
                                const Module *M, AssemblyAnnotationWriter *AAW,
                                bool IsForDebug, bool ShouldPreserveUseListOrder)
-    : Out(o), TheModule(M), Machine(Mac), AnnotationWriter(AAW),
+    : Out(o), TheModule(M), Machine(Mac), TypePrinter(M), AnnotationWriter(AAW),
       IsForDebug(IsForDebug),
-      ShouldPreserveUseListOrder(ShouldPreserveUseListOrder) {
-  if (!TheModule)
-    return;
-  TypePrinter.incorporateTypes(*TheModule);
+      ShouldPreserveUseListOrder(ShouldPreserveUseListOrder) {}
+
+const SetVector<const Comdat *> &AssemblyWriter::GetComdats() {
+  if (!LazyComdats) {
+    LazyComdats.emplace();
     for (const Function &F : *TheModule)
       if (const Comdat *C = F.getComdat())
-      Comdats.insert(C);
+        LazyComdats->insert(C);
     for (const GlobalVariable &GV : TheModule->globals())
       if (const Comdat *C = GV.getComdat())
-      Comdats.insert(C);
+        LazyComdats->insert(C);
+  }
+  return *LazyComdats;
 }
 
 void AssemblyWriter::writeOperand(const Value *Operand, bool PrintType) {
   if (!Operand) {
     Out << "<null operand!>";
     return;
   }
   if (PrintType) {
do {
       PrintEscapedString(Front, Out);
       Out << "\"\n";
     } while (!Asm.empty());
   }
 
   printTypeIdentities();
 
   // Output all comdats.
+  const auto &Comdats = GetComdats();
   if (!Comdats.empty())
     Out << '\n';
   for (const Comdat *C : Comdats) {
     printComdat(C);
     if (C != Comdats.back())
       Out << '\n';
   }
 
void AssemblyWriter::printAlias(const GlobalAlias *GA) {
   Out << '\n';
 }
 
 void AssemblyWriter::printComdat(const Comdat *C) {
   C->print(Out);
 }
 
 void AssemblyWriter::printTypeIdentities() {
-  if (TypePrinter.NumberedTypes.empty() &&
-      TypePrinter.NamedTypes.empty())
+  const auto &NumberedTypes = TypePrinter.GetNumberedTypes();
+  const auto &NamedTypes = TypePrinter.GetNamedTypes();
+  if (NumberedTypes.empty() && NamedTypes.empty())
     return;
 
   Out << '\n';
 
   // We know all the numbers that each type is used and we know that it is a
   // dense assignment.  Convert the map to an index table.
-  std::vector<StructType*> NumberedTypes(TypePrinter.NumberedTypes.size());
-  for (DenseMap<StructType*, unsigned>::iterator I =
-       TypePrinter.NumberedTypes.begin(), E = TypePrinter.NumberedTypes.end();
-       I != E; ++I) {
-    assert(I->second < NumberedTypes.size() && "Didn't get a dense numbering?");
-    NumberedTypes[I->second] = I->first;
+  std::vector<StructType *> NumberedTypesVec(NumberedTypes.size());
+  for (const auto &KV : NumberedTypes) {
+    assert(KV.second < NumberedTypes.size() && "Didn't get a dense numbering?");
+    NumberedTypesVec[KV.second] = KV.first;
   }
 
   // Emit all numbered types.
-  for (unsigned i = 0, e = NumberedTypes.size(); i != e; ++i) {
+  for (unsigned i = 0, e = NumberedTypesVec.size(); i != e; ++i) {
     Out << '%' << i << " = type ";
 
     // Make sure we print out at least one level of the type structure, so
     // that we do not get %2 = type %2
-    TypePrinter.printStructBody(NumberedTypes[i], Out);
+    TypePrinter.printStructBody(NumberedTypesVec[i], Out);
     Out << '\n';
   }
 
-  for (unsigned i = 0, e = TypePrinter.NamedTypes.size(); i != e; ++i) {
-    PrintLLVMName(Out, TypePrinter.NamedTypes[i]->getName(), LocalPrefix);
+  for (StructType *STy : NamedTypes) {
+    PrintLLVMName(Out, STy->getName(), LocalPrefix);
     Out << " = type ";
 
     // Make sure we print out at least one level of the type structure, so
     // that we do not get %FILE = type %FILE
-    TypePrinter.printStructBody(TypePrinter.NamedTypes[i], Out);
+    TypePrinter.printStructBody(STy, Out);
     Out << '\n';
   }
 }
 
 /// printFunction - Print all aspects of a function.
 ///
 void AssemblyWriter::printFunction(const Function *F) {
   // Print out the return type and name.
if (V.hasName() || isa<GlobalValue>(V) ||
     WriteAsOperandInternal(O, &V, nullptr, Machine, M);
     return true;
   }
   return false;
 }
 
 static void printAsOperandImpl(const Value &V, raw_ostream &O, bool PrintType,
                                ModuleSlotTracker &MST) {
-  TypePrinting TypePrinter;
-  if (const Module *M = MST.getModule())
-    TypePrinter.incorporateTypes(*M);
+  TypePrinting TypePrinter(MST.getModule());
   if (PrintType) {
     TypePrinter.print(V.getType(), O);
     O << ' ';
   }
 
   WriteAsOperandInternal(O, &V, &TypePrinter, MST.getMachine(),
                          MST.getModule());
 }
void Value::printAsOperand(raw_ostream &O, bool PrintType,
   printAsOperandImpl(*this, O, PrintType, MST);
 }
 
 static void printMetadataImpl(raw_ostream &ROS, const Metadata &MD,
                               ModuleSlotTracker &MST, const Module *M,
                               bool OnlyAsOperand) {
   formatted_raw_ostream OS(ROS);
 
-  TypePrinting TypePrinter;
-  if (M)
-    TypePrinter.incorporateTypes(*M);
-
+  TypePrinting TypePrinter(M);
   WriteAsOperandInternal(OS, &MD, &TypePrinter, MST.getMachine(), M,
                          /* FromValue */ true);
 
   auto *N = dyn_cast<MDNode>(&MD);
   if (OnlyAsOperand || !N)
     return;
 
   OS << " = ";