[llvm-reduce] Remove debug metadata elements

[ellis]

Summary

There can be lots of MDTuple debug metadata nodes. For example, globals: !{!1, !2} in !DICompileUnit(). Search through all debug info to find MDTuple's and remove some of their elements.

For D135114 I was able to get a reproducer with 364 lines without manually deleting elements. After this patch I got it down to 67 lines.

[probinson]

+ormris

[dblaikie]

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

15–18

The DILocalVariables don't need {{}} do they?

llvm/test/tools/llvm-reduce/remove-metadata-elements.ll

24

llvm/test/tools/llvm-reduce/remove-named-metadata-elements.ll

7

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

104–106

109–110

117–119

[ellis]

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

15–18

Hmm I originally added this because I didn't want these lines to match themselves. But I guess after the first iteration the comments will be removed and they wont' match themselves anymore.

The tests pass without them so I'll remove them.

[ellis]

Remove extra {{ }} in tests

[dblaikie]

Seems pretty good to me.

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

15–18

oh, fair point - if that's a common stylistic thing done in other llvm-reduce tests, I don't mind it here

[probinson]

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

15–18

It doesn't come up often, but I've seen it done elsewhere.

[aeubanks]

sorry to be late to reviewing this, but I think this is overly aggressive. I see verifier failures like scope must have two or three operands after this patch.

https://reviews.llvm.org/D132077 was in the process of being reviewed and basically does this but more targeted with a specific focus on not creating verifier failures (since that's the direction we'd like to take llvm-reduce, not producing verifier failures since that slows down reduction a lot and dumps a lot of output). could we revert this and use the other patch?

[ellis]

In D135237#3840909, @aeubanks wrote:

sorry to be late to reviewing this, but I think this is overly aggressive. I see verifier failures like scope must have two or three operands after this patch.

https://reviews.llvm.org/D132077 was in the process of being reviewed and basically does this but more targeted with a specific focus on not creating verifier failures (since that's the direction we'd like to take llvm-reduce, not producing verifier failures since that slows down reduction a lot and dumps a lot of output). could we revert this and use the other patch?

Oh sorry I was not aware of D132077. After a quick look at the summary it looks very similar to this diff. Since D132077 is a better direction, I'll revert my diff. Thanks for letting me know!

llvm/test/tools/llvm-reduce/Inputs/remove-metadata.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: 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-INTERESTINGNESS-DAG: !{{DIGlobalVariable}}(
+; CHECK-INTERESTINGNESS-DAG: !{{DILocalVariable}}(name: "A"
+; CHECK-INTERESTINGNESS-DAG: !{{DILocalVariable}}(name: "B"
+; CHECK-INTERESTINGNESS-DAG: !{{DILocalVariable}}(name: "C"
 
 
 
 ; CHECK: define void @test() !dbg [[SUBPROG:![0-9]+]]
 ; CHECK: !llvm.module.flags = !{
 
 ; CHECK: !llvm.dbg.cu = !{[[CU:.+]]}
 

llvm/test/tools/llvm-reduce/remove-metadata-elements.ll

+; RUN: llvm-reduce %s -o %t --delta-passes=metadata --test FileCheck --test-arg %s --test-arg --input-file
+; RUN: FileCheck %s < %t --implicit-check-not="boring"
+
+; Test that debug metadata lists can be reduced by making sure debug info for
+; "boring" globals are removed.
+
+; $ cat a.c
+; int boringA, interesting, boringB;
+; $ clang a.c -g -S -emit-llvm -o -
+
+@A = dso_local global i32 0, align 4, !dbg !0
+@B = dso_local global i32 0, align 4, !dbg !5
+@C = dso_local global i32 0, align 4, !dbg !8
+
+!llvm.dbg.cu = !{!2}
+!llvm.module.flags = !{!10, !11, !12, !13, !14, !15, !16}
+
+!0 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression())
+!1 = distinct !DIGlobalVariable(name: "boringA", scope: !2, file: !3, line: 1, type: !7, isLocal: false, isDefinition: true)
+!2 = distinct !DICompileUnit(language: DW_LANG_C99, file: !3, isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, globals: !4, splitDebugInlining: false, nameTableKind: None)
+!3 = !DIFile(filename: "a.c", directory: "")
+!4 = !{!0, !5, !8}
+!5 = !DIGlobalVariableExpression(var: !6, expr: !DIExpression())
+; CHECK: !{{DIGlobalVariable}}(name: "interesting"
+!6 = distinct !DIGlobalVariable(name: "interesting", scope: !2, file: !3, line: 1, type: !7, isLocal: false, isDefinition: true)
+!7 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!8 = !DIGlobalVariableExpression(var: !9, expr: !DIExpression())
+!9 = distinct !DIGlobalVariable(name: "boringB", scope: !2, file: !3, line: 1, type: !7, isLocal: false, isDefinition: true)
+!10 = !{i32 7, !"Dwarf Version", i32 5}
+!11 = !{i32 2, !"Debug Info Version", i32 3}
+!12 = !{i32 1, !"wchar_size", i32 4}
+!13 = !{i32 8, !"PIC Level", i32 2}
+!14 = !{i32 7, !"PIE Level", i32 2}
+!15 = !{i32 7, !"uwtable", i32 2}
+!16 = !{i32 7, !"frame-pointer", i32 2}

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

 ; Test that llvm-reduce can remove uninteresting metadata from an IR file.
 ; The Metadata pass erases named & unnamed metadata nodes.
 ;
-; RUN: llvm-reduce --test %python --test-arg %p/Inputs/remove-metadata.py %s -o %t
-; RUN: cat %t | FileCheck -implicit-check-not=! %s
+; RUN: llvm-reduce %s -o %t --delta-passes=metadata --test FileCheck --test-arg %s --test-arg --input-file
+; RUN: FileCheck %s < %t
 
 @global = global i32 0, !dbg !0
 
 define void @main() !dbg !0 {
    ret void, !dbg !0
 }
 
 !uninteresting = !{!0}
-; CHECK: !interesting = !{!0}
+; CHECK: !interesting = !{![[I:[0-9]+]]}
 !interesting = !{!1}
 
 !0 = !{!"uninteresting"}
-; CHECK: !0 = !{!"interesting"}
+; CHECK: ![[I]] = !{!"interesting"}
 !1 = !{!"interesting"}

llvm/test/tools/llvm-reduce/remove-named-metadata-elements.ll

+; RUN: llvm-reduce %s -o %t --delta-passes=metadata --test FileCheck --test-arg %s --test-arg --input-file
+; RUN: FileCheck %s < %t --implicit-check-not="boring" --check-prefixes=CHECK,REDUCED
+
+; Test that we can remove elements from named metadata.
+
+!llvm.dbg.cu = !{!0, !1}
+; CHECK: !{{llvm.module.flags}} =
+; REDUCED-SAME: !{}
+!llvm.module.flags = !{!10, !11, !12, !13, !14, !15, !16}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !2, isOptimized: false, runtimeVersion: 0, emissionKind: NoDebug)
+!1 = distinct !DICompileUnit(language: DW_LANG_C99, file: !3, isOptimized: false, runtimeVersion: 0, emissionKind: NoDebug)
+; CHECK: !{{DIFile}}(filename: "interesting.c"
+!2 = !DIFile(filename: "interesting.c", directory: "")
+!3 = !DIFile(filename: "boring.c", directory: "")
+
+!10 = !{i32 7, !"Dwarf Version", i32 5}
+!11 = !{i32 2, !"Debug Info Version", i32 3}
+!12 = !{i32 1, !"wchar_size", i32 4}
+!13 = !{i32 8, !"PIC Level", i32 2}
+!14 = !{i32 7, !"PIE Level", i32 2}
+!15 = !{i32 7, !"uwtable", i32 2}
+!16 = !{i32 7, !"frame-pointer", i32 2}

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

 #include "llvm/IR/InstIterator.h"
 #include <vector>
 
 using namespace llvm;
 
 /// Removes all the Named and Unnamed Metadata Nodes, as well as any debug
 /// functions that aren't inside the desired Chunks.
 static void extractMetadataFromModule(Oracle &O, Module &Program) {
+  SmallSetVector<MDNode *, 8> NodesToVisit;
+
   // Get out-of-chunk Named metadata nodes
   SmallVector<NamedMDNode *> NamedNodesToDelete;
-  for (NamedMDNode &MD : Program.named_metadata())
-    if (!O.shouldKeep())
+  for (NamedMDNode &MD : Program.named_metadata()) {
+    if (O.shouldKeep()) {
+      for (auto *Op : MD.operands())
+        NodesToVisit.insert(Op);
+    } else {
       NamedNodesToDelete.push_back(&MD);
+    }
+  }
 
   for (NamedMDNode *NN : NamedNodesToDelete) {
     for (auto I : seq<unsigned>(0, NN->getNumOperands()))
       NN->setOperand(I, nullptr);
     NN->eraseFromParent();
   }
 
+  // Delete elements from named metadata lists
+  for (auto &NamedList : Program.named_metadata()) {
+    SmallVector<MDNode *> NewOperands;
+    for (auto *Op : NamedList.operands())
+      if (O.shouldKeep())
+        NewOperands.push_back(Op);
+    if (NewOperands.size() == NamedList.getNumOperands())
+      continue;
+    NamedList.clearOperands();
+    for (auto *Op : NewOperands)
+      NamedList.addOperand(Op);
+  }
+
   // Delete out-of-chunk metadata attached to globals.
   for (GlobalVariable &GV : Program.globals()) {
     SmallVector<std::pair<unsigned, MDNode *>> MDs;
     GV.getAllMetadata(MDs);
-    for (std::pair<unsigned, MDNode *> &MD : MDs)
-      if (!O.shouldKeep())
+    for (std::pair<unsigned, MDNode *> &MD : MDs) {
+      if (O.shouldKeep()) {
+        NodesToVisit.insert(MD.second);
+      } else {
         GV.setMetadata(MD.first, nullptr);
       }
+    }
+  }
 
   for (Function &F : Program) {
     {
       SmallVector<std::pair<unsigned, MDNode *>> MDs;
       // Delete out-of-chunk metadata attached to functions.
       F.getAllMetadata(MDs);
-      for (std::pair<unsigned, MDNode *> &MD : MDs)
-        if (!O.shouldKeep())
+      for (std::pair<unsigned, MDNode *> &MD : MDs) {
+        if (O.shouldKeep()) {
+          NodesToVisit.insert(MD.second);
+        } else {
           F.setMetadata(MD.first, nullptr);
         }
+      }
+    }
 
     // Delete out-of-chunk metadata attached to instructions.
     for (Instruction &I : instructions(F)) {
       SmallVector<std::pair<unsigned, MDNode *>> MDs;
       I.getAllMetadata(MDs);
-      for (std::pair<unsigned, MDNode *> &MD : MDs)
-        if (!O.shouldKeep())
+      for (std::pair<unsigned, MDNode *> &MD : MDs) {
+        if (O.shouldKeep()) {
+          NodesToVisit.insert(MD.second);
+        } else {
           I.setMetadata(MD.first, nullptr);
         }
       }
     }
+  }
+
+  // Gather all metadata tuples and their parents
+  SmallVector<std::pair<MDNode *, unsigned>> OperandsOfTuples;
+  SmallSet<Metadata *, 8> VisitedNodes;
+  while (!NodesToVisit.empty()) {
+    auto *Node = NodesToVisit.pop_back_val();
+    if (VisitedNodes.contains(Node))
+      continue;
+    VisitedNodes.insert(Node);
+    for (auto I : seq<unsigned>(0, Node->getNumOperands())) {
+      auto *Op = Node->getOperand(I).get();
+      if (isa_and_nonnull<MDNode>(Op))
+        NodesToVisit.insert(cast<MDNode>(Op));
+      if (isa_and_nonnull<MDTuple>(Op))
+        OperandsOfTuples.push_back(std::make_pair(Node, I));
+    }
+  }
+
+  // Delete elements from metadata tuples
+  for (auto Pair : OperandsOfTuples) {
+    auto *Node = Pair.first;
+    unsigned NodeOpID = Pair.second;
+    auto *Tuple = dyn_cast<MDTuple>(Node->getOperand(NodeOpID));
+    SmallVector<Metadata *> NewOperands;
+    for (auto &Op : Tuple->operands())
+      if (O.shouldKeep())
+        NewOperands.push_back(Op.get());
+    if (NewOperands.size() == Tuple->getNumOperands())
+      continue;
+    Node->replaceOperandWith(
+        NodeOpID, MDTuple::get(Tuple->getContext(), makeArrayRef(NewOperands)));
+  }
+}
 
 void llvm::reduceMetadataDeltaPass(TestRunner &Test) {
   outs() << "*** Reducing Metadata...\n";
   runDeltaPass(Test, extractMetadataFromModule);
   outs() << "----------------------------\n";
 }