[llvm-reduce] Fix di-metadata pass test failures

[ormris]

Summary

We're seeing intermittent failures in upstream bots. See:

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

This appears to be due to the unstable iteration order of DenseSet. Since we're trying to reduce a tree, it makes sense to attempt reductions from the top down.

This also addresses post-review comments from @MatzeB.

[ormris]

Thanks for the review @aeubanks!

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=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
+; RUN: FileCheck <%t --enable-var-scope %s
 
-; CHECK-INTERESTINGNESS: define void @test() !dbg
+; CHECK-INTERESTINGNESS: define void @test() !dbg [[SUBPROG:![0-9]+]]
 ; 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: [[SUBPROG]] = distinct !DISubprogram(name: "test",
 
 
 
 ; CHECK: define void @test() !dbg [[SUBPROG:![0-9]+]]
 ; CHECK: !llvm.module.flags = !{
 
 ; CHECK: !llvm.dbg.cu = !{[[CU:.+]]}
 

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: llvm-reduce --abort-on-invalid-reduction --delta-passes=di-metadata --test=FileCheck --test-arg=--check-prefix=CHECK-INTERESTINGNESS --test-arg=%s --test-arg=--input-file %s -o %t
 ; RUN: FileCheck <%t %s
 
 @global = global i32 0
 
 define void @main() !dbg !5 {
    ret void
 }
 

 !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: elements: [[EL:![0-9]+]])
 ; CHECK: [[EL]] = !{!{{[0-9]+}}}
+; CHECK-INTERESTINGNESS: interesting
 !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/deltas/ReduceDIMetadata.cpp

 #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;
+  SetVector<std::tuple<MDNode *, size_t, MDNode *>> Tuples;
   std::vector<MDNode *> ToLook;
-  DenseSet<MDNode *> Visited;
+  SetVector<MDNode *> Visited;
 
   // Start by looking at the attachments we collected
   for (const auto &NMD : MDs)
-    if (NMD && !Visited.count(NMD))
+    if (NMD)
       ToLook.push_back(NMD);
 
   while (!ToLook.empty()) {
     MDNode *MD = ToLook.back();
     ToLook.pop_back();
 
     if (Visited.count(MD))
       continue;