[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

530

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

533

min(10, size)

549

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

611

shared_ptr

615

Do you need to worry about iterator invalidation here?

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

816

Please add an option to easily disable these passes.

821

insert(end, md_begin, md_end)

831

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

530

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

549

Sure

615

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.

816

Will do.

821

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.)

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"
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 = NamedMDs.size();
+  if (NumPrint > 10)
+    NumPrint = 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;
+  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);
+  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())
+      for (auto op : NamedMD.operands())
+        NamedMDOps.push_back(op);
+    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();