[llvm-reduce] Add pass that reduces DebugInfo metadata

[ormris]

Summary

This new pass for llvm-reduce attempts to reduce DebugInfo metadata. The strategy is as follows:

1. Scan every MD node, keeping track of nodes already visited.
2. Look for DebugInfo nodes, then record any operands that are lists.
   • Ignore empty lists.
3. Bisect though all the elements of the collected lists.
   • Ignore any elements that are not references to other DebugInfo MD.
4. If all elements of the list are null, replace with an empty list.

This process can dramatically simplify the module. Without going into exactly what is removed, the difference in the final file size show how large the difference is. This uses a large internal bitcode test case.

Reduction strategy	Size
No reduction	22M
Current	49K
With Patch	5.6K

I've taken more measurements of the runtime impact and it's not too bad. It's negligible when only 1 thread is used, but increases with multiple threads.

Threads:	Current (s)	With Patch (s)
-j 1	203.33	203.67
-j 8	201.33	203.33

[aeubanks]

thanks for the patch, I've really wanted something like this for a while (actually my simpler idea was to just run the strip pass at the beginning to see if we could remove all debug info, but this is probably better).

I'm a bit busy right now, but will try to find time to review this unless somebody else gets to it before me

llvm/tools/llvm-reduce/DeltaManager.cpp

71

I wonder if we should move the metadata passes later where we should already have removed as many potential metadata havers, e.g. after instructions or ir-passes

[ormris]

llvm/tools/llvm-reduce/DeltaManager.cpp

71

Good point. I've run some tests locally and it seems like moving it after the instructions pass saves a few seconds. I'll change the patch.

Position	Time (s)
Current	85.3
Last	81.8
After instructions	80.96

[ormris]

Change pass pipeline slightly to improve performance.

[ormris]

Gentle ping

[ormris]

ping ping

[aeubanks]

sorry for the slow review

do you have cases where stripping the debug info e.g. passing the IR through opt -passes=strip` makes the IR uninteresting, but this significantly helps over just the metadata pass?

llvm/test/tools/llvm-reduce/remove-dimetadata.ll

2–3

looks copy/pasted

5

could you add --abort-on-invalid-reduction?

llvm/tools/llvm-reduce/DeltaManager.cpp

71

running dimetadata before metadata seems better since dimetadata can make metadata do less work, but not vice versa

74

can this be di-metadata? dimetadata is too squished for me

llvm/tools/llvm-reduce/deltas/ReduceDIMetadata.cpp

46–47

making ToLook a vector and using pop_back here seems nicer

51

nit: formatting
I see some other unformatted code, did you run clang-format?

54

check if MDT is null?

65

should this be at the top of the loop?

71

with C++17 we should be able to use auto [a, b, c] = foo;

97

check if this is null?

[aeubanks]

llvm/tools/llvm-reduce/deltas/ReduceDIMetadata.cpp

75

use brackets for bodies with more than one line

84–85

is it possible for multiple DINodes to refer to a tuple?

[aeubanks]

actually I just happened to run across a case where this would be useful, but I'm getting tons of verifier errors in reduction to do with invalid template parameter

[ormris]

Changelog:

• clang-format
• Rename "dimetadata" to "di-metadata"
• Code and data structure clean-up
• Add "--abort-on-invalid-reduction" to test
• Fix header comments

[ormris]

Everything should be addressed. Sorry for the delay. Things have been busy over here.

In D132077#3765732, @aeubanks wrote:

actually I just happened to run across a case where this would be useful, but I'm getting tons of verifier errors in reduction to do with invalid template parameter

Yes, this does lean on the verifier. It's fairly blind to the structure of DI Metadata. Did it provide a useful reduction?

llvm/test/tools/llvm-reduce/remove-dimetadata.ll

2–3

Fixed

5

Fixed

llvm/tools/llvm-reduce/DeltaManager.cpp

71

Fixed

74

Fixed

llvm/tools/llvm-reduce/deltas/ReduceDIMetadata.cpp

46–47

FIxed

51

I did not. Should be fixed.

54

Fixed

65

No, that messes with checks in the body of the loop. There are two places where if check if the node is visited.

71

Fixed.

75

Fixed.

84–85

Yes. In my example IR files, multiple nodes refer to the same empty tuple.

97

Fixed

[fhahn]

Thanks for working on this. I was also looking into improving the situation, but this patch is more complete. I pushed an additional test case in 5be203ec4db5 which also covers the DICompileUnit case. It would need updating to use the di-metadata pass here.

llvm/tools/llvm-reduce/DeltaManager.cpp

64

Should this be split off as a separate patch? It seems independent of adding a new DI-metadata reduction pass.

llvm/tools/llvm-reduce/deltas/ReduceDIMetadata.cpp

94

I think you should also include DICompileUnit nodes: Program.debug_compile_units()

[arsenm]

llvm/tools/llvm-reduce/deltas/ReduceDIMetadata.cpp

31

DenseSet?

33

DenseSet?

[aeubanks]

In D132077#3801049, @ormris wrote:

Everything should be addressed. Sorry for the delay. Things have been busy over here.

In D132077#3765732, @aeubanks wrote:

actually I just happened to run across a case where this would be useful, but I'm getting tons of verifier errors in reduction to do with invalid template parameter

Yes, this does lean on the verifier. It's fairly blind to the structure of DI Metadata. Did it provide a useful reduction?

IIRC I eventually gave up because it kept failing the verifier.
In its current state I think this patch can't run in the default llvm-reduce pipeline because of this. In cases with certain types of debug info (e.g. templates) it'll significantly slow down the reduce. I'm ok with adding it as a pass that isn't run by default. Or if you can somehow get the pass to not fail the verifier with templated code (i.e. llvm-reduce --abort-on-invalid-reduction -delta-passes=di-metadata doesn't fail on some IR with template debug info).

[ormris]

llvm/tools/llvm-reduce/DeltaManager.cpp

64

Actually, this is an incorrect merge. Sorry for the confusion.

[ormris]

Updating this patch to address verifier issues. From my reading of the verifier, and some internal tests, it looks like removing all elements of the tuple is valid for tuples attached to nodes like DISubprogram and DICompositeType. This also allows the pass to reduce those node types more fully. DICompileUnit nodes are now added to the queue. I've also updated fhahn's test to reflect the changes.

[aeubanks]

even with the latest patch I'm seeing verifier errors

!6249 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "BindUnwrapTraits<base::internal::UnretainedWrapper<v8::JobTask> >", scope: !22, file: !1379, line: 1456, size: 8, flags: DIFlagTypePassByValue, elements: !7, templateParams: !2223, identifier: ".?AU?$BindUnwrapTraits@V?$UnretainedWrapper@VJobTask@v8@@@internal@base@@@base@@")
!2223 = distinct !{null}
invalid template parameter

is it possible to not replace the metadata with null but rather create a new metadata node with just the remaining operands?

here's what I've been testing with

b.ll5 MBDownload

$ cat /tmp/reduce.sh 
#!/bin/bash
set -eu
[[ $(rg --count DILocation $@ ) -gt 2000 ]]
$ ./build/rel/bin/llvm-reduce --test /tmp/reduce.sh /tmp/b.ll -o /tmp/c.ll --delta-passes=di-metadata

[ormris]

Thanks for the example and suggestion, that was really helpful. I've changed the pass to use that strategy. I don't get any verification errors when using my internal test case or the test case you provided, and the code is overall cleaner, I think.

[arsenm]

llvm/test/tools/llvm-reduce/remove-debug-info-nodes.ll

4

Can you add -abort-on-invalid-reduction here?

[ormris]

Add --abort-on-invalid-reduction to test

[aeubanks]

some nits, but thanks for going this direction, looks much better

llvm/test/tools/llvm-reduce/remove-dimetadata.ll

22

can we be more explicit about this CHECK and the one below?
e.g.

; CHECK: DISubroutineType(types: [[CHILD:![0-9]+]])
; CHECK: [[CHILD]] = !{}

(I might have the exact syntax wrong)

llvm/tools/llvm-reduce/deltas/ReduceDIMetadata.cpp

36

when would this be false/null?

45

some indentation weirdness, git clang-format?

48

the outer if just checked that this isn't false/null

55

ditto

62

could you give these more descriptive names?

[ormris]

llvm/tools/llvm-reduce/deltas/ReduceDIMetadata.cpp

36

NMD could be null if debug metadata attachment was null. I believe it's legal to say !dbg !null, but I could be misremembering. The second condition could be false if multiple nodes had the same debug metadata attachment.

45

This is what clang-format outputs. Happy to make it look cleaner, but I couldn't see a way to improve it.

[arsenm]

llvm/test/tools/llvm-reduce/remove-dimetadata.ll

4

Don't need cat, FileCheck %s < %t

[aeubanks]

uh looks like https://reviews.llvm.org/D135237 was submitted, I'll need to see what's going on between this patch and that patch

[aeubanks]

lg with comments addressed, but we need to figure out what to do with https://reviews.llvm.org/D135237. I think that one is overly aggressive, I'll ask if we can use this patch instead

llvm/tools/llvm-reduce/deltas/ReduceDIMetadata.cpp

2

headers need updating

45

if you delete one of the leading spaces before the comment, the whole block will be properly formatted by clang-format

59

typically we check visited at the top of the loop, rather than when adding, because we may add something to the queue multiple times before visiting it, and we end up processing something multiple times

[ormris]

Agreed. I just tested it using your test case and it crashed.

[ormris]

Fix header comment and check for visited nodes.

llvm/tools/llvm-reduce/deltas/ReduceDIMetadata.cpp

59

typically we check visited at the top of the loop, rather than when adding, because we may add something to the queue multiple times before visiting it, and we end up processing something multiple times

[ormris]

llvm/tools/llvm-reduce/deltas/ReduceDIMetadata.cpp

59

Sorry, pressed reply rather than "Done". Ignore the comment above. This should be fixed.

[aeubanks]

lg, and the other patch has been reverted. thanks for pushing this through!

[ormris]

Thanks for the review, @aeubanks and @arsenm! I'll committing this shortly.

[ellis]

llvm/tools/llvm-reduce/deltas/ReduceDIMetadata.cpp

84

In D135237 I searched through Program.named_metadata() which includes things like !llvm.module.flags and !llvm.dbg.cu (I assume this is the same as Program.debug_compile_units()). Do we also want to reduce these? My guess is this patch won't remove unnecessary module flags. Is that the case?

[aeubanks]

llvm/tools/llvm-reduce/deltas/ReduceDIMetadata.cpp

84

At least in regards to !llvm.dbg.cu, I've seen DICompileUnit not listed in llvm.dbg.cu verifier errors, so we need to take care there. !llvm.module.flags should be reducable (and I do that manually a lot, so it'd be nice to get that working)

[MatzeB]

llvm/tools/llvm-reduce/DeltaManager.cpp

71

running dimetadata before metadata seems better since dimetadata can make metadata do less work, but not vice versa

Is that true? I think I typically see metadata drop references to DICompileUnit nodes and with it all the debug info disappears, reducing the work for dimetadata...

llvm/tools/llvm-reduce/deltas/ReduceDIMetadata.cpp

36–38

Isn't Visited empty in this loop and !Visited() will just always be true? So this loop in effect just copies from MDs to ToLook but filtering out nullptr. The next loop then seems to use Visited to ensure every node is only checked once even if it appears multiple times in the ToLook list.

Unless I miss something here, wouldn't it be a lot easier to:

1. Turn MDs into a std::set<MDNode*> or similar so duplicates get eliminated immediately?
2. Don't add nullptrs in the first place (or alternative just skip the 1 unique nullptr in the later loop)
3. No need for ToLook or pop_back anymore, just do for (MDNode *MD : MDs) for the loop in line 39?

[MatzeB]

llvm/test/tools/llvm-reduce/Inputs/remove-dimetadata.py

2–9

This checks whether there is at least 1 line in the input with the word "interesting" in it.

But you can get that with somethign like FileCheck --prefix=INTERESTING %s < xxx INTERESTING: interesting instead with the need for a custom python script, can't you?

[MatzeB]

llvm/tools/llvm-reduce/deltas/ReduceDIMetadata.cpp

36–38

Oh I guess this a worklist like algorithm to traverse MDNodes recursively. So you can ignore most of that my comment. Though the Visited use in line 36 still seems unnecessary.

[MatzeB]

Also just realized this already landed, I guess I'm also fine not having my nitpicks addressed then.

[chapuni]

I have seen flaky behavior.
(excuse me, in internal builders)

llvm/tools/llvm-reduce/deltas/ReduceDIMetadata.cpp

64

'Tuples' is DenseMap. Would it be safe for loop?

[aeubanks]

In D132077#3842375, @chapuni wrote:

I have seen flaky behavior.
(excuse me, in internal builders)

you mean a failing test? do you have example output?

[ormris]

We're seeing a test fail intermittently as well. See below. I have a fix and am about to post a review for it.

https://lab.llvm.org/buildbot/#/builders/139/builds/29185

[aeubanks]

if it's not a trivial fix, I'd revert this patch and reupload it for review with the fix

[ormris]

It's pretty trivial, but I also wanted to address @MatzeB's post commit feedback. https://reviews.llvm.org/D135473

llvm/test/tools/llvm-reduce/Inputs/remove-dimetadata.py

+import sys
+
+input = open(sys.argv[1], "r")
+for line in input:
+  if "interesting" in line:
+    sys.exit(0)
+
+sys.exit(1)

llvm/test/tools/llvm-reduce/remove-debug-info-nodes.ll

 ; Test that llvm-reduce can drop unneeded debug metadata nodes referenced by
 ; DICompileUnit and DISuprogram.
 ;
-; RUN: llvm-reduce --delta-passes=metadata --test FileCheck --test-arg --check-prefixes=CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
+; RUN: llvm-reduce --delta-passes=di-metadata --abort-on-invalid-reduction --test FileCheck --test-arg --check-prefixes=CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
 ; RUN: cat %t | FileCheck %s
 
 ; CHECK-INTERESTINGNESS: define void @test() !dbg
 ; CHECK-INTERESTINGNESS: !llvm.module.flags = !{
 
 ; CHECK-INTERESTINGNESS: !llvm.dbg.cu = !{[[CU:.+]]}
 
 ; CHECK-INTERESTINGNESS-DAG: [[CU]] = distinct !DICompileUnit(language: DW_LANG_C99,{{.*}}, retainedTypes: [[TYPES:![0-9]+]]
 ; CHECK-INTERESTINGNESS-DAG: [[TYPES]] = !{[[T0:![0-9]+]]
 ; CHECK-INTERESTINGNESS-DAG: [[T0]] = !DIBasicType(name: "unsigned int",
 
 
 
 ; CHECK: define void @test() !dbg [[SUBPROG:![0-9]+]]
 ; CHECK: !llvm.module.flags = !{
 
 ; CHECK: !llvm.dbg.cu = !{[[CU:.+]]}
 
 ; CHECK-DAG: [[CU]] = distinct !DICompileUnit(language: DW_LANG_C99,{{.*}}, retainedTypes: [[TYPES:![0-9]+]], globals: [[GLOBALS:![0-9]+]]
+; CHECK-DAG: [[EMPTY:![0-9]+]] = !{}
 ; CHECK-DAG: [[TYPES]] = !{[[T0:![0-9]+]]
 ; CHECK-DAG: [[T0]] = !DIBasicType(name: "unsigned int",
-; CHECK-DAG: [[GLOBALS]] = !{!{{.+}}
+; CHECK-DAG: [[GLOBALS]] = !{{{![0-9]+}}
 
-
-; CHECK-DAG: [[SUBPROG]] = distinct !DISubprogram(name: "test", {{.*}}retainedNodes: [[RETAINED_NODES:.+]])
-; CHECK-DAG: [[RETAINED_NODES]] = !{!{{.+}},
+; CHECK-DAG: [[SUBPROG]] = distinct !DISubprogram(name: "test", {{.*}}retainedNodes: [[EMPTY]])
 
 define void @test() !dbg !17 {
   ret void
 }
 
 !llvm.module.flags = !{!0, !1}
 !llvm.dbg.cu = !{!2}
 

llvm/test/tools/llvm-reduce/remove-dimetadata.ll

+; Test that llvm-reduce can remove uninteresting DI metadata from an IR file.
+;
+; RUN: llvm-reduce --abort-on-invalid-reduction --delta-passes=di-metadata --test %python --test-arg %p/Inputs/remove-dimetadata.py %s -o %t
+; RUN: cat %t | FileCheck %s
+
+@global = global i32 0
+
+define void @main() !dbg !5 {
+   ret void
+}
+
+!llvm.module.flags = !{!0}
+!llvm.dbg.cu = !{!4}
+
+!0 = !{i32 2, !"Debug Info Version", i32 3}
+!1 = !DIFile(filename: "test.c", directory: "test")
+!2 = !{!10}
+!4 = distinct !DICompileUnit(language: DW_LANG_C, file: !1, producer: "clang", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !9)
+!5 = distinct !DISubprogram(name: "main", scope: !1, file: !1, line: 498, type: !6, scopeLine: 0, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !4, retainedNodes: !2)
+!6 = !DISubroutineType(types: !7)
+!7 = !{!13}
+; CHECK: !{}
+!8 = distinct !DICompileUnit(language: DW_LANG_C, file: !1, producer: "clang", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !9)
+!9 = !{}
+!10 = !DILocalVariable(name: "one", scope: !14, file: !1, line: 0, type: !15)
+!13 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!14 = distinct !DILexicalBlock(scope: !5, file: !1, line: 3)
+!15 = !DICompositeType(tag: DW_TAG_structure_type, name: "test", file: !1, size: 64, align: 32, flags: DIFlagPublic, elements: !16)
+!16 = !{!17, !18}
+; CHECK: !{!{{[0-9]+}}}
+!17 = !DIDerivedType(tag: DW_TAG_member, name: "interesting", scope: !14, file: !1, baseType: !13, size: 32, align: 32, flags: DIFlagPublic)
+!18 = !DIDerivedType(tag: DW_TAG_member, name: "uninteresting", scope: !14, file: !1, baseType: !13, size: 32, align: 32, offset: 32, flags: DIFlagPublic)

llvm/tools/llvm-reduce/CMakeLists.txt

add_llvm_tool(llvm-reduce
   ReducerWorkItem.cpp
   TestRunner.cpp
   deltas/Delta.cpp
   deltas/Utils.cpp
   deltas/ReduceAliases.cpp
   deltas/ReduceArguments.cpp
   deltas/ReduceAttributes.cpp
   deltas/ReduceBasicBlocks.cpp
+  deltas/ReduceDIMetadata.cpp
   deltas/ReduceFunctionBodies.cpp
   deltas/ReduceFunctions.cpp
   deltas/ReduceGlobalObjects.cpp
   deltas/ReduceGlobalValues.cpp
   deltas/ReduceGlobalVarInitializers.cpp
   deltas/ReduceGlobalVars.cpp
   deltas/ReduceInstructions.cpp
   deltas/ReduceMetadata.cpp

llvm/tools/llvm-reduce/DeltaManager.cpp

 #include "DeltaManager.h"
 #include "ReducerWorkItem.h"
 #include "TestRunner.h"
 #include "deltas/Delta.h"
 #include "deltas/ReduceAliases.h"
 #include "deltas/ReduceArguments.h"
 #include "deltas/ReduceAttributes.h"
 #include "deltas/ReduceBasicBlocks.h"
+#include "deltas/ReduceDIMetadata.h"
 #include "deltas/ReduceFunctionBodies.h"
 #include "deltas/ReduceFunctions.h"
 #include "deltas/ReduceGlobalObjects.h"
 #include "deltas/ReduceGlobalValues.h"
 #include "deltas/ReduceGlobalVarInitializers.h"
 #include "deltas/ReduceGlobalVars.h"
 #include "deltas/ReduceIRReferences.h"
 #include "deltas/ReduceInstructionFlagsMIR.h"
DeltaPasses("delta-passes",
                 cl::cat(LLVMReduceOptions));
 
 #define DELTA_PASSES                                                           \
   do {                                                                         \
     DELTA_PASS("functions", reduceFunctionsDeltaPass)                          \
     DELTA_PASS("function-bodies", reduceFunctionBodiesDeltaPass)               \
     DELTA_PASS("special-globals", reduceSpecialGlobalsDeltaPass)               \
     DELTA_PASS("aliases", reduceAliasesDeltaPass)                              \
     DELTA_PASS("basic-blocks", reduceBasicBlocksDeltaPass)                     \
     DELTA_PASS("global-values", reduceGlobalValuesDeltaPass)                   \
     DELTA_PASS("global-objects", reduceGlobalObjectsDeltaPass)                 \
     DELTA_PASS("global-initializers", reduceGlobalsInitializersDeltaPass)      \
     DELTA_PASS("global-variables", reduceGlobalsDeltaPass)                     \
+    DELTA_PASS("di-metadata", reduceDIMetadataDeltaPass)                       \
     DELTA_PASS("metadata", reduceMetadataDeltaPass)                            \
     DELTA_PASS("arguments", reduceArgumentsDeltaPass)                          \
     DELTA_PASS("instructions", reduceInstructionsDeltaPass)                    \
     DELTA_PASS("simplify-instructions", simplifyInstructionsDeltaPass)         \
     DELTA_PASS("ir-passes", runIRPassesDeltaPass)                              \
     DELTA_PASS("operands-zero", reduceOperandsZeroDeltaPass)                   \
     DELTA_PASS("operands-one", reduceOperandsOneDeltaPass)                     \
     DELTA_PASS("operands-nan", reduceOperandsNaNDeltaPass)                     \
     DELTA_PASS("operands-to-args", reduceOperandsToArgsDeltaPass)              \
     DELTA_PASS("operands-skip", reduceOperandsSkipDeltaPass)                   \
     DELTA_PASS("operand-bundles", reduceOperandBundesDeltaPass)                \
     DELTA_PASS("simplify-cfg", reduceUsingSimplifyCFGDeltaPass)                \
     DELTA_PASS("attributes", reduceAttributesDeltaPass)                        \

llvm/tools/llvm-reduce/deltas/ReduceDIMetadata.h

+//===- ReduceMetadata.h - Specialized Delta Pass --------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements two functions used by the Generic Delta Debugging
+// Algorithm, which are used to reduce Metadata nodes.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEDIMETADATA_H
+#define LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEDIMETADATA_H
+
+#include "TestRunner.h"
+
+namespace llvm {
+void reduceDIMetadataDeltaPass(TestRunner &Test);
+} // namespace llvm
+
+#endif

llvm/tools/llvm-reduce/deltas/ReduceDIMetadata.cpp

+//===- ReduceMetadata.cpp - Specialized Delta Pass ------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements two functions used by the Generic Delta Debugging
+// Algorithm, which are used to reduce Metadata nodes.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ReduceDIMetadata.h"
+#include "Delta.h"
+#include "llvm/ADT/Sequence.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/DebugInfoMetadata.h"
+#include "llvm/IR/InstIterator.h"
+#include <set>
+#include <stack>
+#include <tuple>
+#include <vector>
+
+using namespace llvm;
+
+using MDNodeList = SmallVector<MDNode *>;
+
+void identifyUninterestingMDNodes(Oracle &O, MDNodeList &MDs) {
+  DenseSet<std::tuple<MDNode *, size_t, MDNode *>> Tuples;
+  std::vector<MDNode *> ToLook;
+  DenseSet<MDNode *> Visited;
+
+  // Start by looking at the attachments we collected
+  for (const auto &NMD : MDs)
+    if (NMD && !Visited.count(NMD))
+      ToLook.push_back(NMD);
+
+  while (!ToLook.empty()) {
+    MDNode *MD = ToLook.back();
+    ToLook.pop_back();
+
+    // Determine if the current MDNode is DebugInfo
+    if (DINode *DIM = dyn_cast_or_null<DINode>(MD)) {
+        // Scan operands and record attached tuples
+        for (size_t I = 0; I < DIM->getNumOperands(); ++I)
+          if (MDTuple *MDT = dyn_cast_or_null<MDTuple>(DIM->getOperand(I)))
+            if (MDT && !Visited.count(MDT) && MDT->getNumOperands())
+              Tuples.insert({DIM, I, MDT});
+    }
+
+    // Add all of the operands of the current node to the loop's todo list.
+    for (Metadata *Op : MD->operands())
+      if (MDNode *OMD = dyn_cast_or_null<MDNode>(Op))
+        if (OMD && !Visited.count(OMD))
+          ToLook.push_back(OMD);
+
+    Visited.insert(MD);
+  }
+
+  for (auto &T : Tuples) {
+    auto [MO, J, MT] = T;
+    // Remove the operands of the tuple that are not in the desired chunks.
+    SmallVector<Metadata *, 16> TN;
+    for (size_t I = 0; I < MT->getNumOperands(); ++I) {
+      // Ignore any operands that are not DebugInfo metadata nodes.
+      if (MDNode *OMD = dyn_cast_or_null<DINode>(MT->getOperand(I)))
+        // Don't add uninteresting operands to the tuple.
+        if (!O.shouldKeep())
+          continue;
+
+      TN.push_back(MT->getOperand(I));
+    }
+    if (TN.size() != MT->getNumOperands())
+      MO->replaceOperandWith(J, MO->get(MO->getContext(), TN));
+  }
+}
+
+static void extractDIMetadataFromModule(Oracle &O, Module &Program) {
+  MDNodeList MDs;
+  // Collect all !dbg metadata attachments.
+  for (const auto &DC : Program.debug_compile_units())
+    if (DC)
+      MDs.push_back(DC);
+  for (GlobalVariable &GV : Program.globals())
+    GV.getMetadata(llvm::LLVMContext::MD_dbg, MDs);
+  for (Function &F : Program.functions()) {
+    F.getMetadata(llvm::LLVMContext::MD_dbg, MDs);
+    for (Instruction &I : instructions(F))
+      if (auto *DI = I.getMetadata(llvm::LLVMContext::MD_dbg))
+        MDs.push_back(DI);
+  }
+  identifyUninterestingMDNodes(O, MDs);
+}
+
+void llvm::reduceDIMetadataDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing DIMetadata...\n";
+  runDeltaPass(Test, extractDIMetadataFromModule);
+  outs() << "----------------------------\n";
+}