[bugpoint] Teach bugpoint to reduce MDNodes

[loladiro]

Summary

This is essentially pretty simple, it first walks through the the contents of
the module starting from instructions/named metadata to find all MDNodes and
then does a standard list reduction in order to cut down the list of which
metadata nodes to keep. To actually implement the MDNode removal, it creates
a temporary Node, inserts it into the VMap, and laters RAUWs that to null.
This works great, except that the verifier really doesn't like null values in
some MDTuples. Thus, we need some extra logic to also fix up any MDTuples,
which would otherwise contain a null.

The one ugly point here is that in order to do the above, we need to allow
temporary metadata during cloning. To make this possible, I had to modify
CloneModule and CloneFunctionInto, in order to allow passing RemapFlags
through. I think this API change is fine, but if there's a different way
to accomplish the same thing, I'd be happy to change that. Naturally, I can
split that part out into a separate review.

There's also a small fix to pass through AllowTemps recursively in
resolveCylces, which was needed to make the above work.

[dexonsmith]

+Pete and Adrian, from whom I've heard ideas about bugpointing metadata
(and debug info specifically) before.

This is great; I'm glad you're working on this.

[loladiro]

Rebased and add switch to disable MD reduction.

[loladiro]

Add two debuginfo specific passes to speed convergence of the reduction:

• Canonicalize all DIFiles into a single node
• Resolve All type references by string into explicit references

These two passes work around the two most commonly encountered verifier
failures when nulling out nodes, significantly speeding up the
convergence of the MD reducer (down to seconds from several minutes
on an LTO build of clang).

[loladiro]

Remove accidentally added second commit

[loladiro]

Recollect all MDNodes to exclude unreachable ones, as we can't be sure they're valid (since the verifier didn't get to them) and won't assert when we look at them.

[slarin]

Sorry to come in cold on the discussion, but let me ask a naive question - Why can't we teach CloneModule to drop unnecessary metadata in the same way we use a selector function for GlobalVariables (ShouldCloneDefinition) - why copy it in the first place?

[loladiro]

Dropping metadata is already implemented in the ValueMaterializer interface. However, I don't think the other things I'm doing are doable with that interface. I suppose we could extend it? @dexonsmith, thoughts on that?

[slarin]

Sorry - I told you I am starting cold :)

Maybe I am talking about a different issue here - I refer to this loop in CloneModule.cpp:

158 // And named metadata....
159 for (Module::const_named_metadata_iterator I = M->named_metadata_begin(),
160 E = M->named_metadata_end(); I != E; ++I) {
161 const NamedMDNode &NMD = *I;
162 NamedMDNode *NewNMD = New->getOrInsertNamedMetadata(NMD.getName());
163 for (unsigned i = 0, e = NMD.getNumOperands(); i != e; ++i)
164 NewNMD->addOperand(MapMetadata(NMD.getOperand(i), VMap));
165 }

It seems to me that it indiscriminately will copy all content of llvm.dbg.cu if one is present - at least this is exactly what it does in my case...

Sorry again if this is unrelated...

---

Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation

[loladiro]

Ah, that's for named metadata. I think it would be reasonable to call isMetadataNeeded there.

[slarin]

Got it. Thanks...

---

Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation

include/llvm/Transforms/Utils/Cloning.h

 std::unique_ptr<Module> CloneModule(const Module *M, ValueToValueMapTy &VMap);
 
 /// Return a copy of the specified module. The ShouldCloneDefinition function
 /// controls whether a specific GlobalValue's definition is cloned. If the
 /// function returns false, the module copy will contain an external reference
 /// in place of the global definition.
 std::unique_ptr<Module>
 CloneModule(const Module *M, ValueToValueMapTy &VMap,
-            std::function<bool(const GlobalValue *)> ShouldCloneDefinition);
+            std::function<bool(const GlobalValue *)> ShouldCloneDefinition,
+            RemapFlags ExtraFlags = RF_None);
 
 /// ClonedCodeInfo - This struct can be used to capture information about code
 /// being cloned, while it is being cloned.
 struct ClonedCodeInfo {
   /// ContainsCalls - This is set to true if the cloned code contains a normal
   /// call instruction.
   bool ContainsCalls;
 
Function *CloneFunction(const Function *F, ValueToValueMapTy &VMap,
                         ClonedCodeInfo *CodeInfo = nullptr);
 
 /// Clone OldFunc into NewFunc, transforming the old arguments into references
 /// to VMap values.  Note that if NewFunc already has basic blocks, the ones
 /// cloned into it will be added to the end of the function.  This function
 /// fills in a list of return instructions, and can optionally remap types
 /// and/or append the specified suffix to all values cloned.
 ///
-/// If ModuleLevelChanges is false, VMap contains no non-identity GlobalValue
-/// mappings.
+/// If Flags contains RF_NoModuleLevelChanges, VMap contains no non-identity
+/// GlobalValue mappings.
 ///
 void CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
-                       ValueToValueMapTy &VMap, bool ModuleLevelChanges,
-                       SmallVectorImpl<ReturnInst*> &Returns,
+                       ValueToValueMapTy &VMap, RemapFlags Flags,
+                       SmallVectorImpl<ReturnInst *> &Returns,
                        const char *NameSuffix = "",
                        ClonedCodeInfo *CodeInfo = nullptr,
                        ValueMapTypeRemapper *TypeMapper = nullptr,
                        ValueMaterializer *Materializer = nullptr);
 
 void CloneAndPruneIntoFromInst(Function *NewFunc, const Function *OldFunc,
                                const Instruction *StartingInst,
                                ValueToValueMapTy &VMap, bool ModuleLevelChanges,

lib/ExecutionEngine/Orc/IndirectionUtils.cpp

void moveFunctionBody(Function &OrigF, ValueToValueMapTy &VMap,
   else
     assert(VMap[&OrigF] == NewF && "Incorrect function mapping in VMap.");
   assert(NewF && "Function mapping missing from VMap.");
   assert(NewF->getParent() != OrigF.getParent() &&
          "moveFunctionBody should only be used to move bodies between "
          "modules.");
 
   SmallVector<ReturnInst *, 8> Returns; // Ignore returns cloned.
-  CloneFunctionInto(NewF, &OrigF, VMap, /*ModuleLevelChanges=*/true, Returns,
-                    "", nullptr, nullptr, Materializer);
+  CloneFunctionInto(NewF, &OrigF, VMap, RF_None, Returns, "", nullptr, nullptr,
+                    Materializer);
   OrigF.deleteBody();
 }
 
 GlobalVariable* cloneGlobalVariableDecl(Module &Dst, const GlobalVariable &GV,
                                         ValueToValueMapTy *VMap) {
   assert(GV.getParent() != &Dst && "Can't copy decl over existing global var.");
   GlobalVariable *NewGV = new GlobalVariable(
       Dst, GV.getType()->getElementType(), GV.isConstant(),

lib/IR/Metadata.cpp

for (const auto &Op : operands()) {
     if (!N)
       continue;
 
     if (N->isTemporary() && AllowTemps)
       continue;
     assert(!N->isTemporary() &&
            "Expected all forward declarations to be resolved");
     if (!N->isResolved())
-      N->resolveCycles();
+      N->resolveRecursivelyImpl(AllowTemps);
   }
 }
 
 static bool hasSelfReference(MDNode *N) {
   for (Metadata *MD : N->operands())
     if (MD == N)
       return true;
   return false;

lib/Target/AMDGPU/AMDGPUOpenCLImageTypeLoweringPass.cpp

for (auto &Arg: F->args()) {
       NewFArgIt->setName(ArgName);
       VMap[&Arg] = &(*NewFArgIt++);
       if (IsImageType(ArgTypeFromMD(KernelMDNode, Arg.getArgNo()))) {
         (NewFArgIt++)->setName(Twine("__size_") + ArgName);
         (NewFArgIt++)->setName(Twine("__format_") + ArgName);
       }
     }
     SmallVector<ReturnInst*, 8> Returns;
-    CloneFunctionInto(NewF, F, VMap, /*ModuleLevelChanges=*/false, Returns);
+    CloneFunctionInto(NewF, F, VMap, RF_NoModuleLevelChanges, Returns);
 
     // Build new MDNode.
     SmallVector<llvm::Metadata *, 6> KernelMDArgs;
     KernelMDArgs.push_back(ConstantAsMetadata::get(NewF));
     for (unsigned i = 0; i < NumKernelArgMDNodes; ++i)
       KernelMDArgs.push_back(MDNode::get(*Context, NewArgMDs.ArgVector[i]));
     MDNode *NewMDNode = MDNode::get(*Context, KernelMDArgs);
 

lib/Transforms/Utils/CloneFunction.cpp

BasicBlock *llvm::CloneBasicBlock(const BasicBlock *BB,
   }
   return NewBB;
 }
 
 // Clone OldFunc into NewFunc, transforming the old arguments into references to
 // VMap values.
 //
 void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
-                             ValueToValueMapTy &VMap,
-                             bool ModuleLevelChanges,
-                             SmallVectorImpl<ReturnInst*> &Returns,
+                             ValueToValueMapTy &VMap, RemapFlags Flags,
+                             SmallVectorImpl<ReturnInst *> &Returns,
                              const char *NameSuffix, ClonedCodeInfo *CodeInfo,
                              ValueMapTypeRemapper *TypeMapper,
                              ValueMaterializer *Materializer) {
   assert(NameSuffix && "NameSuffix cannot be null!");
 
 #ifndef NDEBUG
   for (const Argument &I : OldFunc->args())
     assert(VMap.count(&I) && "No mapping from source argument specified!");
 #endif
 
   // Copy all attributes other than those stored in the AttributeSet.  We need
   // to remap the parameter indices of the AttributeSet.
   AttributeSet NewAttrs = NewFunc->getAttributes();
   NewFunc->copyAttributesFrom(OldFunc);
   NewFunc->setAttributes(NewAttrs);
 
   // Fix up the personality function that got copied over.
   if (OldFunc->hasPersonalityFn())
-    NewFunc->setPersonalityFn(
-        MapValue(OldFunc->getPersonalityFn(), VMap,
-                 ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
+    NewFunc->setPersonalityFn(MapValue(OldFunc->getPersonalityFn(), VMap, Flags,
                                        TypeMapper, Materializer));
 
   AttributeSet OldAttrs = OldFunc->getAttributes();
   // Clone any argument attributes that are present in the VMap.
   for (const Argument &OldArg : OldFunc->args())
     if (Argument *NewArg = dyn_cast<Argument>(VMap[&OldArg])) {
       AttributeSet attrs =
           OldAttrs.getParamAttributes(OldArg.getArgNo() + 1);
       if (attrs.getNumSlots() > 0)
#endif
   // Loop over all of the instructions in the function, fixing up operand
   // references as we go.  This uses VMap to do all the hard work.
   for (Function::iterator BB =
            cast<BasicBlock>(VMap[&OldFunc->front()])->getIterator(),
                           BE = NewFunc->end();
        BB != BE; ++BB)
     // Loop over all instructions, fixing each one as we find it...
     for (Instruction &II : *BB)
-      RemapInstruction(&II, VMap,
-                       ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
-                       TypeMapper, Materializer);
+      RemapInstruction(&II, VMap, Flags, TypeMapper, Materializer);
 }
 
 // Find the MDNode which corresponds to the subprogram data that described F.
 static DISubprogram *FindSubprogram(const Function *F,
                                     DebugInfoFinder &Finder) {
   for (DISubprogram *Subprogram : Finder.subprograms()) {
     if (Subprogram->describes(F))
       return Subprogram;
if (VMap.count(&I) == 0) {     // Is this argument preserved?
       DestI->setName(I.getName()); // Copy the name over...
       VMap[&I] = &*DestI++;        // Add mapping to VMap
     }
 
   if (ModuleLevelChanges)
     CloneDebugInfoMetadata(NewF, F, VMap);
 
   SmallVector<ReturnInst*, 8> Returns;  // Ignore returns cloned.
-  CloneFunctionInto(NewF, F, VMap, ModuleLevelChanges, Returns, "", CodeInfo);
+  CloneFunctionInto(NewF, F, VMap,
+                    ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
+                    Returns, "", CodeInfo);
   return NewF;
 }
 
 
 
 namespace {
   /// This is a private class used to implement CloneAndPruneFunctionInto.
   struct PruningFunctionCloner {

lib/Transforms/Utils/CloneModule.cpp

 
 std::unique_ptr<Module> llvm::CloneModule(const Module *M,
                                           ValueToValueMapTy &VMap) {
   return CloneModule(M, VMap, [](const GlobalValue *GV) { return true; });
 }
 
 std::unique_ptr<Module> llvm::CloneModule(
     const Module *M, ValueToValueMapTy &VMap,
-    std::function<bool(const GlobalValue *)> ShouldCloneDefinition) {
+    std::function<bool(const GlobalValue *)> ShouldCloneDefinition,
+    llvm::RemapFlags ExtraFlags) {
   // First off, we need to create the new module.
   std::unique_ptr<Module> New =
       llvm::make_unique<Module>(M->getModuleIdentifier(), M->getContext());
   New->setDataLayout(M->getDataLayout());
   New->setTargetTriple(M->getTargetTriple());
   New->setModuleInlineAsm(M->getModuleInlineAsm());
    
   // Loop over all of the global variables, making corresponding globals in the
for (Module::const_global_iterator I = M->global_begin(), E = M->global_end();
        I != E; ++I) {
     GlobalVariable *GV = cast<GlobalVariable>(VMap[&*I]);
     if (!ShouldCloneDefinition(&*I)) {
       // Skip after setting the correct linkage for an external reference.
       GV->setLinkage(GlobalValue::ExternalLinkage);
       continue;
     }
     if (I->hasInitializer())
-      GV->setInitializer(MapValue(I->getInitializer(), VMap));
+      GV->setInitializer(MapValue(I->getInitializer(), VMap, ExtraFlags));
   }
 
   // Similarly, copy over function bodies now...
   //
   for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) {
     Function *F = cast<Function>(VMap[&*I]);
     if (!ShouldCloneDefinition(&*I)) {
       // Skip after setting the correct linkage for an external reference.
       F->setLinkage(GlobalValue::ExternalLinkage);
       continue;
     }
     if (!I->isDeclaration()) {
       Function::arg_iterator DestI = F->arg_begin();
       for (Function::const_arg_iterator J = I->arg_begin(); J != I->arg_end();
            ++J) {
         DestI->setName(J->getName());
         VMap[&*J] = &*DestI++;
       }
 
       SmallVector<ReturnInst*, 8> Returns;  // Ignore returns cloned.
-      CloneFunctionInto(F, &*I, VMap, /*ModuleLevelChanges=*/true, Returns);
+      assert(!(ExtraFlags & RF_NoModuleLevelChanges));
+      CloneFunctionInto(F, &*I, VMap, ExtraFlags, Returns);
     }
 
     if (I->hasPersonalityFn())
-      F->setPersonalityFn(MapValue(I->getPersonalityFn(), VMap));
+      F->setPersonalityFn(MapValue(I->getPersonalityFn(), VMap, ExtraFlags));
   }
 
   // And aliases
   for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end();
        I != E; ++I) {
     // We already dealt with undefined aliases above.
     if (!ShouldCloneDefinition(&*I))
       continue;
     GlobalAlias *GA = cast<GlobalAlias>(VMap[&*I]);
     if (const Constant *C = I->getAliasee())
-      GA->setAliasee(MapValue(C, VMap));
+      GA->setAliasee(MapValue(C, VMap, ExtraFlags));
   }
 
   // And named metadata....
   for (Module::const_named_metadata_iterator I = M->named_metadata_begin(),
          E = M->named_metadata_end(); I != E; ++I) {
     const NamedMDNode &NMD = *I;
     NamedMDNode *NewNMD = New->getOrInsertNamedMetadata(NMD.getName());
     for (unsigned i = 0, e = NMD.getNumOperands(); i != e; ++i)
-      NewNMD->addOperand(MapMetadata(NMD.getOperand(i), VMap));
+      NewNMD->addOperand(MapMetadata(NMD.getOperand(i), VMap, ExtraFlags));
   }
 
   return New;
 }
 
 extern "C" {
 
 LLVMModuleRef LLVMCloneModule(LLVMModuleRef M) {
   return wrap(CloneModule(unwrap(M)).release());
 }
 
 }

test/BugPoint/metadata.ll

-; RUN: bugpoint -load %llvmshlibdir/BugpointPasses%shlibext %s -output-prefix %t -bugpoint-crashcalls -silence-passes > /dev/null
+; RUN: bugpoint -load %llvmshlibdir/BugpointPasses%shlibext %s -output-prefix %t -bugpoint-crashcalls -silence-passes -disable-namedmd-remove -disable-md-reduction > /dev/null
 ; RUN: llvm-dis %t-reduced-simplified.bc -o - | FileCheck %s
 ; REQUIRES: loadable_module
 
 ; Bugpoint should keep the call's metadata attached to the call.
 
 ; CHECK: call void @foo(), !dbg ![[LOC:[0-9]+]], !attach ![[CALL:[0-9]+]]
 ; CHECK: ![[LOC]] = !DILocation(line: 104, column: 105, scope: ![[SCOPE:[0-9]+]])
 ; CHECK: ![[SCOPE]] = distinct !DISubprogram(name: "test"

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: bugpoint -load %llvmshlibdir/BugpointPasses%shlibext %s -output-prefix %t -bugpoint-crash-too-many-cus -disable-md-reduction -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]+]]}

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
 /// crashes 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;
   }
   };
 }
 
 char CrashOnDeclFunc::ID = 0;
 static RegisterPass<CrashOnDeclFunc>
   Z("bugpoint-crash-decl-funcs",
     "BugPoint Test Pass - Intentionally crash on declared functions");
 
-#include <iostream>
+namespace {
+/// CrashOnVar - This pass is used to test bugpoint. It intentionally
+/// crashes if the module has an a global variable. Checking for the CU
+/// is necessary because otherwise it will realize that it can drop the debug
+/// info version.
+class CrashOnVarAndCU : public ModulePass {
+public:
+  static char ID; // Pass ID, replacement for typeid
+  CrashOnVarAndCU() : ModulePass(ID) {}
+
+private:
+  bool runOnModule(Module &M) override {
+    for (auto &GV : M.globals()) {
+      (void)GV;
+      if (M.getNamedMetadata("llvm.dbg.cu"))
+        abort();
+    }
+    return false;
+  }
+};
+}
+
+char CrashOnVarAndCU::ID = 0;
+static RegisterPass<CrashOnVarAndCU>
+    A("bugpoint-crash-var-and-cu",
+      "BugPoint Test Pass - Intentionally crash on global variables as long as "
+      "the module has at least one CU");
+
+namespace {
+/// CrashOnVar - This pass is used to test bugpoint.  It intentionally
+/// crashes if the module has an a global variable.
+class DropUnsedVar : public ModulePass {
+public:
+  static char ID; // Pass ID, replacement for typeid
+  DropUnsedVar() : ModulePass(ID) {}
+
+private:
+  bool runOnModule(Module &M) override {
+    std::vector<GlobalVariable *> ToDelete;
+    for (auto &GV : M.globals())
+      if (GV.use_empty() && !GV.isUsedByMetadata())
+        ToDelete.push_back(&GV);
+    if (ToDelete.empty())
+      return false;
+    for (auto *GV : ToDelete)
+      GV->eraseFromParent();
+    return true;
+  }
+};
+}
+
+char DropUnsedVar::ID = 0;
+static RegisterPass<DropUnsedVar>
+    B("bugpoint-drop-unref-var",
+      "BugPoint Test Pass - Drop unreferenced Global Variables");
+
 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",
+    C("bugpoint-crash-too-many-cus",
       "BugPoint Test Pass - Intentionally crash on too many CUs");

tools/bugpoint/CrashDebugger.cpp

 
 #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/DebugInfoMetadata.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"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
namespace {
   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));
+
+  cl::opt<bool> NoMDReduction("disable-md-reduction",
+                              cl::desc("Do not attempt to reduce md nodes"),
+                              cl::init(false));
+
+  cl::opt<bool>
+      NoTupleSquashing("disable-mdtuple-squashing",
+                       cl::desc("Do not suqash nulls out of MDTuples"),
+                       cl::init(false));
 }
 
 namespace llvm {
   class ReducePassList : public ListReducer<std::string> {
     BugDriver &BD;
   public:
     ReducePassList(BugDriver &bd) : BD(bd) {}
 
for (auto &NamedMD : BD.getProgram()->named_metadata()) {
     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);
+  // If the result is invalid, try something else
+  if (verifyModule(*M)) {
+    delete M;
+    return false;
+  }
 
   // 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;
 }
 
+namespace {
+// Reduce the number of MDNodes
+class ReduceCrashingMDs : public ListReducer<const MDNode *> {
+  BugDriver &BD;
+  std::vector<const MDNode *> AllMDNodes;
+  bool (*TestFn)(const BugDriver &, Module *);
+  bool DoTupleSquashing;
+  MDNode *(*NodeReplacer)(Module *);
+
+public:
+  ReduceCrashingMDs(BugDriver &bd, std::vector<const MDNode *> All,
+                    bool (*testFn)(const BugDriver &, Module *),
+                    bool NeedsTupleSquashing, MDNode *(*NodeReplacer)(Module *))
+      : BD(bd), AllMDNodes(All), TestFn(testFn),
+        DoTupleSquashing(NeedsTupleSquashing & !NoTupleSquashing),
+        NodeReplacer(NodeReplacer) {}
+
+  TestResult doTest(std::vector<const MDNode *> &Prefix,
+                    std::vector<const MDNode *> &Kept,
+                    std::string &Error) override {
+    if (!Kept.empty() && TestMDNodes(Kept))
+      return KeepSuffix;
+    if (!Prefix.empty() && TestMDNodes(Prefix))
+      return KeepPrefix;
+    return NoFailure;
+  }
+
+  bool TestMDNodes(std::vector<const MDNode *> &MDNodes);
+};
+}
+
+static void CollectMDNodeOps(const MDNode *Node,
+                             std::set<const MDNode *> &MDs) {
+  MDs.insert(Node);
+  for (const MDOperand &Op : Node->operands()) {
+    const Metadata *MD = Op.get();
+    if (!MD || !isa<MDNode>(MD))
+      continue;
+    if (MDs.count(cast<MDNode>(MD)))
+      continue;
+    CollectMDNodeOps(cast<MDNode>(MD), MDs);
+  }
+}
+
+static std::set<const MDNode *> CollectMDNodeSet(llvm::Module *M) {
+  // Collect all roots (instruction attachments and named metadata)
+  std::set<const MDNode *> Roots;
+  for (auto &NamedMD : M->named_metadata())
+    for (auto op : NamedMD.operands())
+      Roots.insert(op);
+
+  for (Module::iterator MI = M->begin(), ME = M->end(); MI != ME; ++MI)
+    for (Function::iterator FI = MI->begin(), FE = MI->end(); FI != FE; ++FI)
+      for (BasicBlock::iterator I = FI->begin(), E = FI->end(); I != E;) {
+        Instruction *Inst = &*I++;
+        SmallVector<std::pair<unsigned, MDNode *>, 1> MDs;
+        Inst->getAllMetadata(MDs);
+        for (auto p : MDs)
+          Roots.insert(p.second);
+      }
+
+  // Collect all Metadata reachable from the roots
+  std::set<const MDNode *> AllNodes;
+  for (const MDNode *Node : Roots)
+    CollectMDNodeOps(Node, AllNodes);
+
+  return AllNodes;
+}
+
+bool ReduceCrashingMDs::TestMDNodes(std::vector<const MDNode *> &MDNodes) {
+  // Convert list to set for fast lookup...
+  SmallPtrSet<const MDNode *, 64> OldMDNodes;
+  for (unsigned i = 0, e = MDNodes.size(); i != e; ++i) {
+    OldMDNodes.insert(MDNodes[i]);
+  }
+
+  outs() << "Checking for crash with only " << OldMDNodes.size();
+  if (OldMDNodes.size() == 1)
+    outs() << " metadata node: ";
+  else
+    outs() << " metadata nodes: ";
+
+  // Named Metadata Nodes cannnot have null operands, so always
+  // preserve those MD nodes (plus we already reduced them before)
+  SmallPtrSet<const MDNode *, 64> NMDRoots;
+  for (auto &NamedMD : BD.getProgram()->named_metadata())
+    for (MDNode *op : NamedMD.operands())
+      NMDRoots.insert(op);
+
+  ValueToValueMapTy VMap;
+  LLVMContext &Context = BD.getProgram()->getContext();
+  // Insert everything we want to remove as a temporary mapping in
+  // the Value map
+  TempMDTuple Temp = MDNode::getTemporary(Context, {});
+  for (const MDNode *MD : AllMDNodes) {
+    if (!OldMDNodes.count(MD) && !NMDRoots.count(MD))
+      VMap.MD()[MD].reset(Temp.get());
+  }
+
+  // However, we need to make sure to squash tuples, since the verifier checks
+  // that some tuples don't have null operands. However, we also can't just
+  // map the operands over yet, because they may depend on global values that
+  // only get created in CloneModule. Thus, create temporaries for them now and
+  // keep a list of everything we need to resolve later.
+  // TODO: This isn't great, there could very well be tuples where nulls have
+  // semantic meaning. However, without this, the verifier will prevent us from
+  // getting a meaningful reduction. For now, just add a switch to disable this
+  // behavior. If it becomes a problem, we could do something smarter, (e.g.
+  // only do it for references from Debug Info nodes or making the Verifier more
+  // permissive)
+  std::vector<const MDTuple *> Tuples;
+  if (!NoTupleSquashing) {
+    for (const MDNode *Node : AllMDNodes) {
+      if (Node && OldMDNodes.count(Node) && Node->getNumOperands() != 0 &&
+          isa<MDTuple>(Node)) {
+        if (std::any_of(Node->op_begin(), Node->op_end(),
+                        [&](const Metadata *Operand) {
+                          return VMap.MD()[Operand].get() == Temp.get();
+                        })) {
+          auto TempTuple = MDNode::getTemporary(Context, {});
+          VMap.MD()[Node].reset(TempTuple.release());
+          Tuples.push_back(cast<MDTuple>(Node));
+        }
+      }
+    }
+  }
+
+  auto M = CloneModule(BD.getProgram(), VMap,
+                       [](const GlobalValue *) { return true; },
+                       RF_HaveUnmaterializedMetadata);
+
+  if (!NoTupleSquashing) {
+    for (const MDTuple *Tuple : Tuples) {
+      SmallVector<Metadata *, 1> Operands;
+      MDTuple *TempTuple = cast<MDTuple>(VMap.MD()[Tuple].get());
+      // Already mapped this tuple before (this can happen because the list of
+      // MD nodes is not necessarily deduplicated if two tuples map to the same
+      // tuple when an operand is dropped - rather than paying the cost to
+      // dedup,
+      // we just handle it here).
+      if (!TempTuple->isTemporary())
+        continue;
+      for (Metadata *Operand : Tuple->operands())
+        if (Operand &&
+            (!isa<MDNode>(Operand) || OldMDNodes.count(cast<MDNode>(Operand))))
+          Operands.push_back(Operand);
+      Metadata *SquashedNode = Tuple->isDistinct()
+                                   ? MDNode::getDistinct(Context, Operands)
+                                   : MDNode::get(Context, Operands);
+      // We could be in the following situation:
+      // !1 = {!4, !5, !6}
+      // !2 = {!4, !5}
+      // If !2 and !6 get selected for removal, the SquashedNode for !1 would be
+      // !2 by uniquing, but the VMap already has our guard entry. To avoid that
+      // situation, clear the VMap for the squashed node here.
+      VMap.MD()[SquashedNode].reset();
+      Metadata *Replacement =
+          MapMetadata(SquashedNode, VMap, RF_HaveUnmaterializedMetadata);
+      TempTuple->replaceAllUsesWith(Replacement);
+      MDNode::deleteTemporary(TempTuple);
+    }
+  }
+
+  Temp->replaceAllUsesWith(NodeReplacer(&*M));
+  if (verifyModule(*M, &outs())) {
+    outs() << "Replacement invalidated module...\n";
+    return false;
+  }
+
+  // Try running on the hacked up program...
+  if (TestFn(BD, M.get())) {
+    // We need to recollect all MDNodes, because we don't really have any other
+    // way of knowing whether a node is actually referenced in the module and
+    // the unreferenced nodes could be invalid and trigger asserts later when
+    // we look at them (the referenced nodes are guaranteed to be ok by the
+    // Verifier).
+    std::set<const MDNode *> ReferencedMDNodes(CollectMDNodeSet(M.get()));
+
+    // Make sure to use pointers that point into the now-current module.
+    std::vector<const MDNode *> NewMDNodes;
+    for (const MDNode *Node : MDNodes) {
+      // Even if something was in the preserve list, it is possible that it
+      // is null if all it's parents got dropped. Do still keep in the list
+      // however, because otherwise the list reducer gets confused.
+      MDNode *MD = cast_or_null<MDNode>(VMap.MD()[Node].get());
+      if (!MD || !ReferencedMDNodes.count(MD))
+        NewMDNodes.push_back(nullptr);
+      else
+        NewMDNodes.push_back(MD);
+    }
+    MDNodes.swap(NewMDNodes);
+
+    std::vector<const MDNode *> AllNewMDNodes;
+    for (const MDNode *Node : AllMDNodes) {
+      MDNode *MD = cast_or_null<MDNode>(VMap.MD()[Node].get());
+      if (MD)
+        AllNewMDNodes.push_back(MD);
+    }
+    AllMDNodes = std::move(AllNewMDNodes);
+
+    BD.setNewProgram(M.release()); // It crashed, keep the trimmed version...
+    return true;
+  }
+  return false;
+}
+
+static std::vector<const MDNode *> CollectMDNodes(llvm::Module *M) {
+  std::set<const MDNode *> AllNodes(CollectMDNodeSet(M));
+
+  // Convert to list suitable for reducing
+  std::vector<const MDNode *> AllNodeList(AllNodes.begin(), AllNodes.end());
+
+  return AllNodeList;
+}
+
 /// 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...
if (!BugpointIsInterrupted) {
       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);
     }
   }
 
+  if (!NoMDReduction) {
+    if (!BugpointIsInterrupted) {
+      // Finally go through all metadata nodes and try to delete them
+      std::vector<const MDNode *> AllNodeList(CollectMDNodes(BD.getProgram()));
+
+      // Before getting to the generic fallback reducer below, perform some
+      // reductions specific to certain kinds of debug info in order to speed up
+      // convergence.
+
+      // Replace all DIFile nodes by a single new one. The contents of a DIFile
+      // is unlikely to matter, but just in case, we still do a list reduction.
+      std::vector<const MDNode *> AllDIFileNodes;
+      std::copy_if(AllNodeList.begin(), AllNodeList.end(),
+                   std::back_inserter(AllDIFileNodes),
+                   [](const MDNode *Node) { return isa<DIFile>(Node); });
+      ReduceCrashingMDs(BD, AllDIFileNodes, TestFn, false,
+                        [](Module *M) -> MDNode * {
+                          return DIFile::get(M->getContext(), "none", ".");
+                        })
+          .reduceList(AllNodeList, Error);
+
+      // Resolve all indirect type references into direct ones such that the
+      // generic reducer can null out the references effectively.
+      {
+        outs() << "Attempting to resolve indirect references...";
+        AllNodeList = CollectMDNodes(BD.getProgram());
+        std::map<const MDString *, const Metadata *> TypeRefs;
+        // Collect the mapping from identifier to typeref
+        for (const MDNode *Node : AllNodeList) {
+          auto *Ty = dyn_cast<DICompositeType>(Node);
+          if (!Ty)
+            continue;
+          if (MDString *TypeId = Ty->getRawIdentifier()) {
+            auto P = TypeRefs.insert(std::make_pair(TypeId, Ty));
+            if (!P.second && !Ty->isForwardDecl())
+              P.first->second = Ty;
+          }
+        }
+
+        std::vector<const MDNode *> ToReplace;
+        ValueToValueMapTy VMap;
+        for (const MDNode *Node : AllNodeList) {
+          if (!isa<DINode>(Node))
+            continue;
+
+          if (auto *SRT = dyn_cast<DISubroutineType>(Node)) {
+            if (!SRT->getRawTypeArray())
+              continue;
+            Node = cast<MDTuple>(SRT->getRawTypeArray());
+          }
+
+          // Look to see if any of the operands are MDStrings that are in our
+          // type ref map.
+          for (const Metadata *Op : Node->operands()) {
+            if (!Op || !isa<MDString>(Op))
+              continue;
+            auto T = TypeRefs.find(cast<MDString>(Op));
+            if (T != TypeRefs.end() && T->second != Node) {
+              VMap.MD()[Node].reset(
+                  MDNode::getTemporary(BD.getProgram()->getContext(), {})
+                      .release());
+              assert(VMap.MD()[Node].get());
+              ToReplace.push_back(Node);
+              break;
+            }
+          }
+        }
+
+        auto M = CloneModule(BD.getProgram(), VMap,
+                             [](const GlobalValue *) { return true; },
+                             RF_HaveUnmaterializedMetadata);
+
+        for (const MDNode *Node : ToReplace) {
+          MDNode *Temp = cast<MDNode>(VMap.MD()[Node].get());
+          if (!Temp->isTemporary())
+            continue;
+          auto Replacement = Node->clone();
+          for (unsigned i = 0; i < Node->getNumOperands(); ++i) {
+            const MDString *Ref =
+                dyn_cast_or_null<MDString>(Node->getOperand(i));
+            if (!Ref)
+              continue;
+            auto T = TypeRefs.find(Ref);
+            if (T == TypeRefs.end() || T->second == Node)
+              continue;
+            Replacement->replaceOperandWith(i,
+                                            const_cast<Metadata *>(T->second));
+          }
+          Temp->replaceAllUsesWith(MapMetadata(
+              Node->isDistinct()
+                  ? MDNode::replaceWithDistinct(std::move(Replacement))
+                  : MDNode::replaceWithPermanent(std::move(Replacement)),
+              VMap, RF_HaveUnmaterializedMetadata));
+          MDNode::deleteTemporary(Temp);
+        }
+
+        // Try running on the hacked up program...
+        if (!verifyModule(*M, &outs()) && TestFn(BD, M.get())) {
+          BD.setNewProgram(M.release());
+        }
+      }
+
+      // Generic reducer - we do this in two stages. First, we exclude all nodes
+      // that the debug special case reducers left in, as it is likely that
+      // removing will hide the bug, thus slowing convergence. Afterwards, we
+      // do the same reduction with all nodes (of which there are hopefully few
+      // at that point), in order to make sure we really get down the number of
+      // nodes as far as possible.
+      AllNodeList = CollectMDNodes(BD.getProgram());
+      AllNodeList.erase(
+          remove_if(AllNodeList.begin(), AllNodeList.end(),
+                    [](const MDNode *Node) { return isa<DIFile>(Node); }),
+          AllNodeList.end());
+      ReduceCrashingMDs(BD, AllNodeList, TestFn, true,
+                        [](Module *M) -> MDNode * { return nullptr; })
+          .reduceList(AllNodeList, Error);
+
+      // Second Pass
+      AllNodeList = CollectMDNodes(BD.getProgram());
+      ReduceCrashingMDs(BD, AllNodeList, TestFn, true,
+                        [](Module *M) -> MDNode * { return nullptr; })
+          .reduceList(AllNodeList, 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()).release();
     M = BD.performFinalCleanups(M, true).release();
 

tools/bugpoint/ListReducer.h

if (TheList.size() > 2) {
         
         // If the binary split reduction loop made an unfortunate sequence of
         // splits, the trimming loop might be left off with a huge number of
         // remaining elements (large search space). Backjumping out of that
         // search space and attempting a different split can significantly 
         // improve the convergence speed.
         if (std::rand() % 100 < BackjumpProbability)
           goto Backjump;
-        
-        for (unsigned i = 1; i < TheList.size()-1; ++i) { // Check interior elts
+        for (unsigned i = 1; i < TheList.size(); ++i) { // Check interior elts
           if (BugpointIsInterrupted) {
             errs() << "\n\n*** Reduction Interrupted, cleaning up...\n\n";
             return true;
           }
           
           std::vector<ElTy> TestList(TheList);
           TestList.erase(TestList.begin()+i);
 

unittests/Transforms/Utils/Cloning.cpp

TEST_F(CloneInstruction, Attributes) {
   AttributeSet AS = AttributeSet::get(context, 0, AK);
   Argument *A = &*F1->arg_begin();
   A->addAttr(AS);
 
   SmallVector<ReturnInst*, 4> Returns;
   ValueToValueMapTy VMap;
   VMap[A] = UndefValue::get(A->getType());
 
-  CloneFunctionInto(F2, F1, VMap, false, Returns);
+  CloneFunctionInto(F2, F1, VMap, RF_NoModuleLevelChanges, Returns);
   EXPECT_FALSE(F2->arg_begin()->hasNoCaptureAttr());
 
   delete F1;
   delete F2;
 }
 
 TEST_F(CloneInstruction, CallingConvention) {
   Type *ArgTy1[] = { Type::getInt32PtrTy(context) };
   FunctionType *FT1 =  FunctionType::get(Type::getVoidTy(context), ArgTy1, false);
 
   Function *F1 = Function::Create(FT1, Function::ExternalLinkage);
   F1->setCallingConv(CallingConv::Cold);
   BasicBlock *BB = BasicBlock::Create(context, "", F1);
   IRBuilder<> Builder(BB);
   Builder.CreateRetVoid();
 
   Function *F2 = Function::Create(FT1, Function::ExternalLinkage);
 
   SmallVector<ReturnInst*, 4> Returns;
   ValueToValueMapTy VMap;
   VMap[&*F1->arg_begin()] = &*F2->arg_begin();
 
-  CloneFunctionInto(F2, F1, VMap, false, Returns);
+  CloneFunctionInto(F2, F1, VMap, RF_NoModuleLevelChanges, Returns);
   EXPECT_EQ(CallingConv::Cold, F2->getCallingConv());
 
   delete F1;
   delete F2;
 }
 
 class CloneFunc : public ::testing::Test {
 protected: