[bugpoint] Add a named metadata (+their operands) reducer

[loladiro]

Summary

We frequently run bugpoint on a linked-together module of all modules we jit while compiling the julia standard library. As a result, this module has a very large number of compile units (10000+) in llvm.dbg.cu, which didn't get reduced at all, requiring manual post processing. This is an attempt to
have bugpoint go through and attempt to reduce the number of global named metadata nodes as well as their operands, to cut down the number of roots for such metadata.

[loladiro]

Forgot to clang-format (now fixed!)

[reames]

Test cases?

tools/bugpoint/CrashDebugger.cpp

534

Please use a shared_ptr or something. Raw pointers should be avoided.

537

min(10, size)

553

Possibly: ToDelete.reserve(NamedMD.size())?

615

shared_ptr

619

Do you need to worry about iterator invalidation here?

Would it be easier to just remove the operands or set them to undef?

814

Please add an option to easily disable these passes.

819

insert(end, md_begin, md_end)

829

insert(end, op_begin, op_end)

[dexonsmith]

This sounds awesome. I won't have a chance to look until at least tomorrow, but I know Adrian and Pete both had ideas around bugpoint and debug info so I'm CCing them.

• dpnes

[loladiro]

tools/bugpoint/CrashDebugger.cpp

534

I copied that from above. Happy to change the API throughout, but that should be a separate change.

553

Sure

619

No, the iterators are in the original module, but the ones we're dropping are in the new one. I didn't see an obvious way to just remove operands. I agree that would be preferable.

814

Will do.

819

Needs to convert from named md to its name

[loladiro]

Address review comments and add test case.

[reames]

LGTM

[pete]

Philip has been doing most of the reviewing, so I'll defer to him for a final LGTM. But FWIW, this LGTM given the work to address his feedback.

BTW, my approach was a little different. You are reducing the number of CU's which is great. I should have tried that first.

My approach was to reduce the number of types, global variables, imported entities, and subprograms in an individual CU. Given that these tend to also be referenced from llvm.dbg.* intrinsics, many dbg info entries would remain in the metadata, even after being removed from the CU. From there, I would then strip dbg info from instructions and see if there was a reduced set which would still crash. Eventually I'd get the smallest possible CU in terms of types, subprograms, etc, which demonstrate the bug.

Unfortunately, this didn't seem to be 100% reliable. I kept encountering crashes in llc when it tried to emit the debug info as it thought entries were missing, or weren't in states it wanted them to be in. So I may have actually found real bugs, i'm not sure, but those bugs made it impossible to run llc in bug point and know that the crashes were the original bug and not what i was causing with reduced debug info.

Anyway, i still have the patch lying around if its ever of interest. Its about 6 months old though so likely needs fixed to work on ToT.

[loladiro]

Yes, I think that would be a great step further. As I mentioned, this patch arose from the very specific situation of having tons of otherwise unreferenced CUs left over, but there is certainly room for more.

[dexonsmith]

(Just in case you're waiting for me: I still haven't looked, but if I find anything I can review post-commit.)

test/BugPoint/named-md.ll

+; RUN: bugpoint -load %llvmshlibdir/BugpointPasses%shlibext %s -output-prefix %t -bugpoint-crash-too-many-cus -silence-passes > /dev/null
+; RUN: llvm-dis %t-reduced-simplified.bc -o - | FileCheck %s
+; RUN-DISABLE: bugpoint -disable-namedmd-remove -load %llvmshlibdir/BugpointPasses%shlibext %s -output-prefix %t -bugpoint-crash-too-many-cus -silence-passes > /dev/null
+; RUN-DISABLE: llvm-dis %t-reduced-simplified.bc -o - | FileCheck %s
+; REQUIRES: loadable_module
+
+; CHECK: !llvm.dbg.cu = !{![[FIRST:[0-9]+]], ![[SECOND:[0-9]+]]}
+; CHECK-DISABLE:      !llvm.dbg.cu = !{![[FIRST:[0-9]+]], ![[SECOND:[0-9]+]],
+; CHECK-DISABLE-SAME: ![[THIRD:[0-9]+]], ![[FOURTH:[0-9]+]], ![[FIFTH:[0-9]+]]}
+!llvm.dbg.cu = !{!0, !1, !2, !3, !4, !5}
+; CHECK-NOT: !named
+; CHECK-DISABLE: !named
+!named = !{!0, !1, !2, !3, !4, !5}
+; CHECK: !llvm.module.flags = !{![[DIVERSION:[0-9]+]]}
+!llvm.module.flags = !{!6, !7}
+
+; CHECK-DAG: ![[FIRST]] = distinct !DICompileUnit(language: DW_LANG_Julia,
+; CHECK-DAG: ![[SECOND]] = distinct !DICompileUnit(language: DW_LANG_Julia,
+; CHECK-DAG: ![[DIVERSION]] = !{i32 2, !"Debug Info Version", i32 3}
+; CHECK-DAG: !DIFile(filename: "a", directory: "b")
+
+; 4 nodes survive. Due to renumbering !4 should not exist
+; CHECK-NOT: !4
+
+!0 = distinct !DICompileUnit(language: DW_LANG_Julia,
+                             file: !8)
+!1 = distinct !DICompileUnit(language: DW_LANG_Julia,
+                             file: !8)
+!2 = distinct !DICompileUnit(language: DW_LANG_Julia,
+                             file: !8)
+!3 = distinct !DICompileUnit(language: DW_LANG_Julia,
+                             file: !8)
+!4 = distinct !DICompileUnit(language: DW_LANG_Julia,
+                             file: !8)
+!5 = distinct !DICompileUnit(language: DW_LANG_Julia,
+                             file: !8)
+!6 = !{i32 2, !"Dwarf Version", i32 2}
+!7 = !{i32 2, !"Debug Info Version", i32 3}
+!8 = !DIFile(filename: "a", directory: "b")

tools/bugpoint-passes/TestPasses.cpp

 
 char DeleteCalls::ID = 0;
 static RegisterPass<DeleteCalls>
   Y("bugpoint-deletecalls",
     "BugPoint Test Pass - Intentionally 'misoptimize' CallInsts");
 
 namespace {
   /// CrashOnDeclFunc - This pass is used to test bugpoint.  It intentionally
-  /// crash if the module has an undefined function (ie a function that is
-  /// defined in an external module).
-  class CrashOnDeclFunc : public ModulePass {
-  public:
-    static char ID; // Pass ID, replacement for typeid
-    CrashOnDeclFunc() : ModulePass(ID) {}
-  private:
-    bool runOnModule(Module &M) override {
-      for (auto &F : M.functions()) {
-        if (F.isDeclaration())
-          abort();
-      }
-      return false;
-    }
+/// crashes if the module has an undefined function (ie a function that is
+
   };
 }
 
 char CrashOnDeclFunc::ID = 0;
 static RegisterPass<CrashOnDeclFunc>
   Z("bugpoint-crash-decl-funcs",
     "BugPoint Test Pass - Intentionally crash on declared functions");
+
+#include <iostream>
+namespace {
+/// CrashOnOneCU - This pass is used to test bugpoint. It intentionally
+/// crashes if the Module has two or more compile units
+class CrashOnTooManyCUs : public ModulePass {
+public:
+  static char ID;
+  CrashOnTooManyCUs() : ModulePass(ID) {}
+
+private:
+  bool runOnModule(Module &M) override {
+    NamedMDNode *CU_Nodes = M.getNamedMetadata("llvm.dbg.cu");
+    if (!CU_Nodes)
+      return false;
+    if (CU_Nodes->getNumOperands() >= 2)
+      abort();
+    return false;
+  }
+};
+}
+
+char CrashOnTooManyCUs::ID = 0;
+static RegisterPass<CrashOnTooManyCUs>
+    A("bugpoint-crash-too-many-cus",
+      "BugPoint Test Pass - Intentionally crash on too many CUs");

tools/bugpoint/CrashDebugger.cpp

 // This file defines the bugpoint internals that narrow down compilation crashes
 //
 //===----------------------------------------------------------------------===//
 
 #include "BugDriver.h"
 #include "ListReducer.h"
 #include "ToolRunner.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/StringSet.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/ValueSymbolTable.h"
 #include "llvm/IR/Verifier.h"
namespace {
   cl::opt<bool>
   ReplaceFuncsWithNull("replace-funcs-with-null",
          cl::desc("When stubbing functions, replace all uses will null"),
          cl::init(false));
   cl::opt<bool>
   DontReducePassList("disable-pass-list-reduction",
                      cl::desc("Skip pass list reduction steps"),
                      cl::init(false));
+
+  cl::opt<bool> NoNamedMDRM("disable-namedmd-remove",
+                            cl::desc("Do not remove global named metadata"),
+                            cl::init(false));
 }
 
 namespace llvm {
   class ReducePassList : public ListReducer<std::string> {
     BugDriver &BD;
   public:
     ReducePassList(BugDriver &bd) : BD(bd) {}
 
if (TestFn(BD, M)) {
     for (Instruction *Inst : Instructions)
       Insts.push_back(Inst);
     return true;
   }
   delete M;  // It didn't crash, try something else.
   return false;
 }
 
+namespace {
+// Reduce the list of Named Metadata nodes. We keep this as a list of
+// names to avoid having to convert back and forth every time.
+class ReduceCrashingNamedMD : public ListReducer<std::string> {
+  BugDriver &BD;
+  bool (*TestFn)(const BugDriver &, Module *);
+
+public:
+  ReduceCrashingNamedMD(BugDriver &bd,
+                        bool (*testFn)(const BugDriver &, Module *))
+      : BD(bd), TestFn(testFn) {}
+
+  TestResult doTest(std::vector<std::string> &Prefix,
+                    std::vector<std::string> &Kept,
+                    std::string &Error) override {
+    if (!Kept.empty() && TestNamedMDs(Kept))
+      return KeepSuffix;
+    if (!Prefix.empty() && TestNamedMDs(Prefix))
+      return KeepPrefix;
+    return NoFailure;
+  }
+
+  bool TestNamedMDs(std::vector<std::string> &NamedMDs);
+};
+}
+
+bool ReduceCrashingNamedMD::TestNamedMDs(std::vector<std::string> &NamedMDs) {
+
+  ValueToValueMapTy VMap;
+  Module *M = CloneModule(BD.getProgram(), VMap);
+
+  outs() << "Checking for crash with only these named metadata nodes:";
+  unsigned NumPrint = std::min<size_t>(NamedMDs.size(), 10);
+  for (unsigned i = 0, e = NumPrint; i != e; ++i)
+    outs() << " " << NamedMDs[i];
+  if (NumPrint < NamedMDs.size())
+    outs() << "... <" << NamedMDs.size() << " total>";
+  outs() << ": ";
+
+  // Make a StringMap for faster lookup
+  StringSet<> Names;
+  for (const std::string &Name : NamedMDs)
+    Names.insert(Name);
+
+  // First collect all the metadata to delete in a vector, then
+  // delete them all at once to avoid invalidating the iterator
+  std::vector<NamedMDNode *> ToDelete;
+  ToDelete.reserve(M->named_metadata_size() - Names.size());
+  for (auto &NamedMD : M->named_metadata())
+    if (!Names.count(NamedMD.getName()))
+      ToDelete.push_back(&NamedMD);
+
+  for (auto *NamedMD : ToDelete)
+    NamedMD->eraseFromParent();
+
+  // Verify that this is still valid.
+  legacy::PassManager Passes;
+  Passes.add(createVerifierPass());
+  Passes.run(*M);
+
+  // Try running on the hacked up program...
+  if (TestFn(BD, M)) {
+    BD.setNewProgram(M); // It crashed, keep the trimmed version...
+    return true;
+  }
+  delete M; // It didn't crash, try something else.
+  return false;
+}
+
+namespace {
+// Reduce the list of operands to named metadata nodes
+class ReduceCrashingNamedMDOps : public ListReducer<const MDNode *> {
+  BugDriver &BD;
+  bool (*TestFn)(const BugDriver &, Module *);
+
+public:
+  ReduceCrashingNamedMDOps(BugDriver &bd,
+                           bool (*testFn)(const BugDriver &, Module *))
+      : BD(bd), TestFn(testFn) {}
+
+  TestResult doTest(std::vector<const MDNode *> &Prefix,
+                    std::vector<const MDNode *> &Kept,
+                    std::string &Error) override {
+    if (!Kept.empty() && TestNamedMDOps(Kept))
+      return KeepSuffix;
+    if (!Prefix.empty() && TestNamedMDOps(Prefix))
+      return KeepPrefix;
+    return NoFailure;
+  }
+
+  bool TestNamedMDOps(std::vector<const MDNode *> &NamedMDOps);
+};
+}
+
+bool ReduceCrashingNamedMDOps::TestNamedMDOps(
+    std::vector<const MDNode *> &NamedMDOps) {
+  // Convert list to set for fast lookup...
+  SmallPtrSet<const MDNode *, 64> OldMDNodeOps;
+  for (unsigned i = 0, e = NamedMDOps.size(); i != e; ++i) {
+    OldMDNodeOps.insert(NamedMDOps[i]);
+  }
+
+  outs() << "Checking for crash with only " << OldMDNodeOps.size();
+  if (OldMDNodeOps.size() == 1)
+    outs() << " named metadata operand: ";
+  else
+    outs() << " named metadata operands: ";
+
+  ValueToValueMapTy VMap;
+  Module *M = CloneModule(BD.getProgram(), VMap);
+
+  // This is a little wasteful. In the future it might be good if we could have
+  // these dropped during cloning.
+  for (auto &NamedMD : BD.getProgram()->named_metadata()) {
+    // Drop the old one and create a new one
+    M->eraseNamedMetadata(M->getNamedMetadata(NamedMD.getName()));
+    NamedMDNode *NewNamedMDNode =
+        M->getOrInsertNamedMetadata(NamedMD.getName());
+    for (MDNode *op : NamedMD.operands())
+      if (OldMDNodeOps.count(op))
+        NewNamedMDNode->addOperand(cast<MDNode>(MapMetadata(op, VMap)));
+  }
+
+  // Verify that this is still valid.
+  legacy::PassManager Passes;
+  Passes.add(createVerifierPass());
+  Passes.run(*M);
+
+  // Try running on the hacked up program...
+  if (TestFn(BD, M)) {
+    // Make sure to use instruction pointers that point into the now-current
+    // module, and that they don't include any deleted blocks.
+    NamedMDOps.clear();
+    for (const MDNode *Node : OldMDNodeOps)
+      NamedMDOps.push_back(cast<MDNode>(VMap.MD()[Node].get()));
+
+    BD.setNewProgram(M); // It crashed, keep the trimmed version...
+    return true;
+  }
+  delete M; // It didn't crash, try something else.
+  return false;
+}
+
 /// DebugACrash - Given a predicate that determines whether a component crashes
 /// on a program, try to destructively reduce the program while still keeping
 /// the predicate true.
 static bool DebugACrash(BugDriver &BD,
                         bool (*TestFn)(const BugDriver &, Module *),
                         std::string &Error) {
   // See if we can get away with nuking some of the global variable initializers
   // in the program...
for (Module::const_iterator FI = BD.getProgram()->begin(),
           }
 
     if (InstructionsToSkipBeforeDeleting) {
       InstructionsToSkipBeforeDeleting = 0;
       goto TryAgain;
     }
 
   } while (Simplification);
+
+  if (!NoNamedMDRM) {
+    BD.EmitProgressBitcode(BD.getProgram(), "reduced-instructions");
+
+    if (!BugpointIsInterrupted) {
+      // Try to reduce the amount of global metadata (particularly debug info),
+      // by dropping global named metadata that anchors them
+      outs() << "\n*** Attempting to remove named metadata: ";
+      std::vector<std::string> NamedMDNames;
+      for (auto &NamedMD : BD.getProgram()->named_metadata())
+        NamedMDNames.push_back(NamedMD.getName().str());
+      ReduceCrashingNamedMD(BD, TestFn).reduceList(NamedMDNames, Error);
+    }
+
+    if (!BugpointIsInterrupted) {
+      // Now that we quickly dropped all the named metadata that doesn't
+      // contribute to the crash, bisect the operands of the remaining ones
+      std::vector<const MDNode *> NamedMDOps;
+      for (auto &NamedMD : BD.getProgram()->named_metadata())
+        NamedMDOps.insert(NamedMDOps.end(), NamedMD.op_begin(),
+                          NamedMD.op_end());
+      ReduceCrashingNamedMDOps(BD, TestFn).reduceList(NamedMDOps, Error);
+    }
+  }
+
 ExitLoops:
 
   // Try to clean up the testcase by running funcresolve and globaldce...
   if (!BugpointIsInterrupted) {
     outs() << "\n*** Attempting to perform final cleanups: ";
     Module *M = CloneModule(BD.getProgram());
     M = BD.performFinalCleanups(M, true).release();