[MIR] Making MIR Printing, opt -dot-cfg, and -debug printing faster

[rtereshin]

Summary

Value::printAsOperand has been scanning the entire module just to
print a single value as an operand, regardless being asked to print a
type or not at all, and regardless really needing to scan the module
to print a type.

It made some of the users of the method exceptionally slow on large
IR-modules (or large MIR-files with large IR-modules embedded).

This patch defers scanning a module looking for struct types, mostly
numbered struct types, as much as possible, speeding up those users
w/o changing any APIs at all.

See speedup examples below:

Release Build:

# 83 seconds -> 5.5 seconds
time ./bin/llc -start-before=irtranslator -stop-after=irtranslator \
  -global-isel -global-isel-abort=2 -simplify-mir sqlite3.O0.ll -o \
  sqlite3.O0.mir

# 133 seconds -> 6.2 seconds
time ./bin/opt sqlite3.O0.ll -dot-cfg -disable-output

Release + Asserts Build:

# 1096 seconds -> 553 seconds
time ./bin/llc -debug-only=isel -fast-isel=false -stop-after=isel \
  sqlite3.O0.ll -o /dev/null 2> err

# 95 seconds -> 5.5 seconds
time ./bin/llc -start-before=irtranslator -stop-after=irtranslator \
  -global-isel -global-isel-abort=2 -simplify-mir sqlite3.O0.ll -o \
  sqlite3.O0.mir

# 146 seconds -> 6.2 seconds
time ./bin/opt sqlite3.O0.ll -dot-cfg -disable-output

where sqlite3.O0.ll is non-optimized IR produced from
sqlite-amalgamation (http://sqlite.org/download.html), which is entire
SQLite3 implementation in a single C-file.

Benchmarked on 4-cores / 8 threads PCI-E SSD iMac running macOS

[rtereshin]

Ping

[bogner]

Nice improvement! I have a couple of minor style/clarity comments, but LGTM with those addressed.

lib/IR/AsmWriter.cpp

502–506

Maybe move this comment up so it's a bit clearer that the sizes matching imply we've already built the index table?

508

range-for would be a bit more concise.

512–513

AFAICT this assert and the one inside the loop are checking the same thing. Do we need them both?

527

It's a bit surprising to null out the module to mark that we already ran this, but I suppose it's simpler than keeping an extra bool around just for that. Maybe add comments to point out what's happening with M, both here and by the member declaration?

[rtereshin]

lib/IR/AsmWriter.cpp

502–506

Sure, will improve comments around here!

508

will do

512–513

Not quite, but I'm checking the uniqueness one totally wrong, I will fix it, good catch!

527

Sure, will do, thanks!

[rtereshin]

Addressing the review comments

[bogner]

Still looks good - two very nitpicky style comments below for when you commit.

lib/IR/AsmWriter.cpp

509

Better to spell this "const auto &P"

511

I think you can avoid default constructing the item by using NumberedTypes.count(P.second) instead of operator[]. Of course, it really doesn't matter much in this case since the value's just an unsigned.

[rtereshin]

lib/IR/AsmWriter.cpp

511

NumberedTypes is a vector

lib/IR/AsmWriter.cpp

static void PrintLLVMName(raw_ostream &OS, const Value *V) {
   PrintLLVMName(OS, V->getName(),
                 isa<GlobalValue>(V) ? GlobalPrefix : LocalPrefix);
 }
 
 namespace {
 
 class TypePrinting {
 public:
-  /// NamedTypes - The named types that are used by the current module.
-  TypeFinder NamedTypes;
-
-  /// NumberedTypes - The numbered types, along with their value.
-  DenseMap<StructType*, unsigned> NumberedTypes;
+  TypePrinting(const Module *M = nullptr) : DeferredM(M) {}
 
-  TypePrinting() = default;
   TypePrinting(const TypePrinting &) = delete;
   TypePrinting &operator=(const TypePrinting &) = delete;
 
-  void incorporateTypes(const Module &M);
+  /// The named types that are used by the current module.
+  TypeFinder &getNamedTypes();
+
+  /// The numbered types, number to type mapping.
+  std::vector<StructType *> &getNumberedTypes();
+
+  bool empty();
 
   void print(Type *Ty, raw_ostream &OS);
 
   void printStructBody(StructType *Ty, raw_ostream &OS);
+
+private:
+  void incorporateTypes();
+
+  /// A module to process lazily when needed. Set to nullptr as soon as used.
+  const Module *DeferredM;
+
+  TypeFinder NamedTypes;
+
+  // The numbered types, along with their value.
+  DenseMap<StructType *, unsigned> Type2Number;
+
+  std::vector<StructType *> NumberedTypes;
 };
 
 } // end anonymous namespace
 
-void TypePrinting::incorporateTypes(const Module &M) {
-  NamedTypes.run(M, false);
+TypeFinder &TypePrinting::getNamedTypes() {
+  incorporateTypes();
+  return NamedTypes;
+}
+
+std::vector<StructType *> &TypePrinting::getNumberedTypes() {
+  incorporateTypes();
+
+  // 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, if it's not done
+  // already (judging from the sizes):
+  if (NumberedTypes.size() == Type2Number.size())
+    return NumberedTypes;
+
+  NumberedTypes.resize(Type2Number.size());
+  for (const auto P : Type2Number) {
+    assert(P.second < NumberedTypes.size() && "Didn't get a dense numbering?");
+    assert(!NumberedTypes[P.second] && "Didn't get a unique numbering?");
+    NumberedTypes[P.second] = P.first;
+  }
+  return NumberedTypes;
+}
+
+bool TypePrinting::empty() {
+  incorporateTypes();
+  return NamedTypes.empty() && Type2Number.empty();
+}
+
+void TypePrinting::incorporateTypes() {
+  if (!DeferredM)
+    return;
+
+  NamedTypes.run(*DeferredM, false);
+  DeferredM = nullptr;
 
   // 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) {
     StructType *STy = *I;
 
     // Ignore anonymous types.
     if (STy->isLiteral())
       continue;
 
     if (STy->getName().empty())
-      NumberedTypes[STy] = NextNumber++;
+      Type2Number[STy] = NextNumber++;
     else
       *NextToUse++ = STy;
   }
 
   NamedTypes.erase(NextToUse, NamedTypes.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.
+/// 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::X86_FP80TyID:  OS << "x86_fp80"; return;
   case Type::FP128TyID:     OS << "fp128"; 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())
+    incorporateTypes();
+    const auto I = Type2Number.find(STy);
+    if (I != Type2Number.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);
private:
   void printGCRelocateComment(const GCRelocateInst &Relocate);
 };
 
 } // end anonymous 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);
   for (const GlobalObject &GO : TheModule->global_objects())
     if (const Comdat *C = GO.getComdat())
       Comdats.insert(C);
 }
 
 void AssemblyWriter::writeOperand(const Value *Operand, bool PrintType) {
   if (!Operand) {
     Out << "<null operand!>";
void AssemblyWriter::printIndirectSymbol(const GlobalIndirectSymbol *GIS) {
   Out << '\n';
 }
 
 void AssemblyWriter::printComdat(const Comdat *C) {
   C->print(Out);
 }
 
 void AssemblyWriter::printTypeIdentities() {
-  if (TypePrinter.NumberedTypes.empty() &&
-      TypePrinter.NamedTypes.empty())
+  if (TypePrinter.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;
-  }
-
   // Emit all numbered types.
-  for (unsigned i = 0, e = NumberedTypes.size(); i != e; ++i) {
-    Out << '%' << i << " = type ";
+  auto &NumberedTypes = TypePrinter.getNumberedTypes();
+  for (unsigned I = 0, E = NumberedTypes.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(NumberedTypes[I], Out);
     Out << '\n';
   }
 
-  for (unsigned i = 0, e = TypePrinter.NamedTypes.size(); i != e; ++i) {
-    PrintLLVMName(Out, TypePrinter.NamedTypes[i]->getName(), LocalPrefix);
+  auto &NamedTypes = TypePrinter.getNamedTypes();
+  for (unsigned I = 0, E = NamedTypes.size(); I != E; ++I) {
+    PrintLLVMName(Out, NamedTypes[I]->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(NamedTypes[I], Out);
     Out << '\n';
   }
 }
 
 /// printFunction - Print all aspects of a function.
 void AssemblyWriter::printFunction(const Function *F) {
   // Print out the return type and name.
   Out << '\n';
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 || isa<DIExpression>(MD))
     return;
 

unittests/IR/ValueTest.cpp

 #endif
 #endif
 
 TEST(ValueTest, printSlots) {
   // Check that Value::print() and Value::printAsOperand() work with and
   // without a slot tracker.
   LLVMContext C;
 
-  const char *ModuleString = "define void @f(i32 %x, i32 %y) {\n"
+  const char *ModuleString = "@g0 = external global %500\n"
+                             "@g1 = external global %900\n"
+                             "\n"
+                             "%900 = type { i32, i32 }\n"
+                             "%500 = type { i32 }\n"
+                             "\n"
+                             "define void @f(i32 %x, i32 %y) {\n"
                              "entry:\n"
                              "  %0 = add i32 %y, 1\n"
                              "  %1 = add i32 %y, 1\n"
                              "  ret void\n"
                              "}\n";
   SMDiagnostic Err;
   std::unique_ptr<Module> M = parseAssemblyString(ModuleString, Err, C);
 
   Function *F = M->getFunction("f");
   ASSERT_TRUE(F);
   ASSERT_FALSE(F->empty());
   BasicBlock &BB = F->getEntryBlock();
   ASSERT_EQ(3u, BB.size());
 
   Instruction *I0 = &*BB.begin();
   ASSERT_TRUE(I0);
   Instruction *I1 = &*++BB.begin();
   ASSERT_TRUE(I1);
 
+  GlobalVariable *G0 = M->getGlobalVariable("g0");
+  ASSERT_TRUE(G0);
+  GlobalVariable *G1 = M->getGlobalVariable("g1");
+  ASSERT_TRUE(G1);
+
   ModuleSlotTracker MST(M.get());
 
 #define CHECK_PRINT(INST, STR)                                                 \
   do {                                                                         \
     {                                                                          \
       std::string S;                                                           \
       raw_string_ostream OS(S);                                                \
       INST->print(OS);                                                         \
do {                                                                         \
       INST->printAsOperand(OS, TYPE, MST);                                     \
       EXPECT_EQ(StringRef(STR), StringRef(OS.str()));                          \
     }                                                                          \
   } while (false)
   CHECK_PRINT_AS_OPERAND(I0, false, "%0");
   CHECK_PRINT_AS_OPERAND(I1, false, "%1");
   CHECK_PRINT_AS_OPERAND(I0, true, "i32 %0");
   CHECK_PRINT_AS_OPERAND(I1, true, "i32 %1");
+  CHECK_PRINT_AS_OPERAND(G0, true, "%0* @g0");
+  CHECK_PRINT_AS_OPERAND(G1, true, "%1* @g1");
 #undef CHECK_PRINT_AS_OPERAND
 }
 
 TEST(ValueTest, getLocalSlots) {
   // Verify that the getLocalSlot method returns the correct slot numbers.
   LLVMContext C;
   const char *ModuleString = "define void @f(i32 %x, i32 %y) {\n"
                              "entry:\n"