[llvm-reduce] Reduce metadata references.

[Meinersbur]

Summary

The ReduceMetadata pass before this patch removed metadata on a per-MDNode (or NamedMDNode) basis. Either all references to an MDNode are kept, or all of them are removed. However, MDNodes are uniqued, meaning that references to MDNodes with the same data become references to the same MDNodes. As a consequence, e.g. tbaa references to the same type will all have the same MDNode reference and hence make it impossible to reduce only keeping metadata on those memory access for which they are interesting.
Moreover, MDNodes can also be referenced by some intrinsics or other MDNodes. These references were not considered for removal leading to the possibility that MDNodes are not actually removed even if selected to be removed by the oracle.

This patch changes ReduceMetadata to reduces based on removable metadata references instead. MDNodes without references implicitly dropped anyway. References by intrinsic calls should be removed by ReduceOperands or ReduceInstructions. References in other MDNodes cannot be removed as it would violate the immutability of MDNodes.

Additionally, ReduceMetadata pass before this patch used setMetadata(I, NULL) to remove references, where I is the index in the array returned by getAllMetadata. However, setMetadata expects a MDKind (such as MD_tbaa) as first argument. getAllMetadata does not return those in consecutive order (otherwise it would not need to be a std::pair with first representing the MDKind).

[aeubanks]

thanks!

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

12

should add a couple things to check for just to make sure we didn't accidentally reduce everything

[jeroen.dobbelaere]

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

14

Just wondering: given the spaces around the matcher, will this have the wanted effect ? Aka, if you give the checker the original input, will it fail ?

[Meinersbur]

Test case refinement

• Add --delta-passes=metadata
• Remove required necessary space after/before "Boring"
• Add RUN lines for test self-consistency

[aeubanks]

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

14

llvm-reduce should automatically check that the input is interesting and fail out if it isn't, so I don't think we need the extra RUN lines. We just need to check if the output is correct.

[nickdesaulniers]

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

85

should this be auto &I rather than auto &&I?

[Meinersbur]

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

12

The RUN at line 2 tests this by checking the existence of all the "EXCITING" lines. I started using --check-prefixes=EXCITING,REDUCED but then I would add NOT lines between all the INTERESTING lines. Would something like REDUCED-DAG-NOT or REDUCED-NOT-DAG work?

14

The NOT expressions would match the NOT lines themselves. To appropriately test the test itself, I ran it through opt (see lines 4 and 5) to remove comments.

Turns out you were right with your suspicion. Boring {{.*}} requires a space after Boring, which e.g. is not the case for @BoringGlobal. I had the concern with spaces as well, but only considered the !md !0 which indeed is always followed/proceeded with a space.

I left line 4 and 5 in the patch for illustration. I could remove them again before committing.

[Meinersbur]

• Replace auto with concrete types.

[Meinersbur]

• Remove self-consistency RUN lines

[aeubanks]

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

12

Actually I changed my mind, I think this is good enough. If the output isn't passing the interestingness test there's something seriously wrong

And the RUN at line 2 is redundant with the internal llvm-reduce check that the input is interesting
Generally I think just the llvm-reduce RUN and the FileCheck for the reduced file RUN are good enough

[Meinersbur]

• Remove llvm-reduce final output interestingness check

[nickdesaulniers]

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

61

I was curious if we should switch the order of the for/if on !O.shouldKeep(), but if I'm reading this correctly, it seems that if O.shouldKeep() == true, then we do no work in this function and should just return early? Then we can remove all of the conditional checks on !O.shouldKeep()?

[aeubanks]

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

61

O.shouldKeep() is not constant, the whole point of llvm-reduce is that it returns true/false for different calls so we can try reducing various subsets of whatever we're trying to reduce since we may not be able to remove everything all at once, or even one at a time, things may need to be reduced in batches.

[Meinersbur]

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

61

To add to @aeubanks explanation, Oracle::shouldKeep() is comparable to Google Benchmark's State::KeepRunning() or LLVM's OptBisect::shouldRunPass(). It controls loop behaviour depending on when/how often it has been called already without explicitly passing which loop iteration we are in.

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

+; RUN: llvm-reduce %s -o %t --delta-passes=metadata --test FileCheck --test-arg %s --test-arg --check-prefix=EXCITING --test-arg --input-file
+; RUN: FileCheck %s --input-file %t --check-prefix=REDUCED
+
+; All exciting stuff must remain in the reduced file.
+; EXCITING-DAG: ExcitingGlobal = global i32 0, !md !0
+; EXCITING-DAG: define void @ExcitingFunc() !md !0
+; EXCITING-DAG: store i32 0, i32* @ExcitingGlobal, align 4, !md !0
+; EXCITING-DAG: !ExcitingNamedMD = !{!0}
+
+; Boring stuff's metadata must have been removed.
+; REDUCED-NOT: Boring{{.*}} !md !0
+; REDUCED-NOT: !md !0 {{.*}}Boring
+
+
+@ExcitingGlobal = global i32 0, !md !0
+@BoringGlobal = global i32 0, !md !0
+
+define void @ExcitingFunc() !md !0 {
+   store i32 0, i32* @ExcitingGlobal, align 4, !md !0
+   store i32 0, i32* @BoringGlobal, align 4, !md !0
+   ret void
+}
+
+declare !md !0 void @BoringFunc()
+
+!ExcitingNamedMD = !{!0}
+!BoringNamedMD = !{!0}
+
+!0 = !{!"my metadata"}

llvm/tools/llvm-reduce/deltas/ReduceMetadata.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 "ReduceMetadata.h"
 #include "Delta.h"
+#include "llvm/ADT/Sequence.h"
 #include "llvm/ADT/SmallVector.h"
-#include <set>
+#include "llvm/IR/InstIterator.h"
 #include <vector>
 
 using namespace llvm;
 
-/// Adds all Unnamed Metadata Nodes that are inside desired Chunks to set
-template <class T>
-static void getChunkMetadataNodes(T &MDUser, Oracle &O,
-                                  std::set<MDNode *> &SeenNodes,
-                                  std::set<MDNode *> &NodesToKeep) {
-  SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
-  MDUser.getAllMetadata(MDs);
-  for (auto &MD : MDs) {
-    SeenNodes.insert(MD.second);
-    if (O.shouldKeep())
-      NodesToKeep.insert(MD.second);
-  }
-}
-
-/// Erases out-of-chunk unnamed metadata nodes from its user
-template <class T>
-static void eraseMetadataIfOutsideChunk(T &MDUser,
-                                        const std::set<MDNode *> &NodesToKeep) {
-  SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
-  MDUser.getAllMetadata(MDs);
-  for (int I = 0, E = MDs.size(); I != E; ++I)
-    if (!NodesToKeep.count(MDs[I].second))
-      MDUser.setMetadata(I, NULL);
-}
-
 /// Removes all the Named and Unnamed Metadata Nodes, as well as any debug
 /// functions that aren't inside the desired Chunks.
 static void extractMetadataFromModule(const std::vector<Chunk> &ChunksToKeep,
                                       Module *Program) {
   Oracle O(ChunksToKeep);
 
-  std::set<MDNode *> SeenNodes;
-  std::set<MDNode *> NodesToKeep;
-
-  // Add chunk MDNodes used by GVs, Functions, and Instructions to set
-  for (auto &GV : Program->globals())
-    getChunkMetadataNodes(GV, O, SeenNodes, NodesToKeep);
-
-  for (auto &F : *Program) {
-    getChunkMetadataNodes(F, O, SeenNodes, NodesToKeep);
-    for (auto &BB : F)
-      for (auto &Inst : BB)
-        getChunkMetadataNodes(Inst, O, SeenNodes, NodesToKeep);
-  }
-
-  // Once more, go over metadata nodes, but deleting the ones outside chunks
-  for (auto &GV : Program->globals())
-    eraseMetadataIfOutsideChunk(GV, NodesToKeep);
-
-  for (auto &F : *Program) {
-    eraseMetadataIfOutsideChunk(F, NodesToKeep);
-    for (auto &BB : F)
-      for (auto &Inst : BB)
-        eraseMetadataIfOutsideChunk(Inst, NodesToKeep);
-  }
-
-
   // Get out-of-chunk Named metadata nodes
-  std::vector<NamedMDNode *> NamedNodesToDelete;
-  for (auto &MD : Program->named_metadata())
+  SmallVector<NamedMDNode *> NamedNodesToDelete;
+  for (NamedMDNode &MD : Program->named_metadata())
     if (!O.shouldKeep())
       NamedNodesToDelete.push_back(&MD);
 
-  for (auto *NN : NamedNodesToDelete) {
-    for (int I = 0, E = NN->getNumOperands(); I != E; ++I)
+  for (NamedMDNode *NN : NamedNodesToDelete) {
+    for (auto I : seq<unsigned>(0, NN->getNumOperands()))
       NN->setOperand(I, NULL);
     NN->eraseFromParent();
   }
+
+  // Delete out-of-chunk metadata attached to globals.
+  SmallVector<std::pair<unsigned, MDNode *>> MDs;
+  for (GlobalVariable &GV : Program->globals()) {
+    GV.getAllMetadata(MDs);
+    for (std::pair<unsigned, MDNode *> &MD : MDs)
+      if (!O.shouldKeep())
+        GV.setMetadata(MD.first, NULL);
   }
 
-// Gets unnamed metadata nodes used by a given instruction/GV/function and adds
-// them to the set of seen nodes
-template <class T>
-static void addMetadataToSet(T &MDUser, std::set<MDNode *> &UnnamedNodes) {
-  SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
-  MDUser.getAllMetadata(MDs);
-  for (auto &MD : MDs)
-    UnnamedNodes.insert(MD.second);
+  for (Function &F : *Program) {
+    // Delete out-of-chunk metadata attached to functions.
+    F.getAllMetadata(MDs);
+    for (std::pair<unsigned, MDNode *> &MD : MDs)
+      if (!O.shouldKeep())
+        F.setMetadata(MD.first, NULL);
+
+    // Delete out-of-chunk metadata attached to instructions.
+    for (Instruction &I : instructions(F)) {
+      I.getAllMetadata(MDs);
+      for (std::pair<unsigned, MDNode *> &MD : MDs)
+        if (!O.shouldKeep())
+          I.setMetadata(MD.first, NULL);
+    }
+  }
 }
 
-/// Returns the amount of Named and Unnamed Metadata Nodes
 static int countMetadataTargets(Module *Program) {
-  std::set<MDNode *> UnnamedNodes;
   int NamedMetadataNodes = Program->named_metadata_size();
 
-  // Get metadata nodes used by globals
-  for (auto &GV : Program->globals())
-    addMetadataToSet(GV, UnnamedNodes);
-
-  // Do the same for nodes used by functions & instructions
-  for (auto &F : *Program) {
-    addMetadataToSet(F, UnnamedNodes);
-    for (auto &BB : F)
-      for (auto &I : BB)
-        addMetadataToSet(I, UnnamedNodes);
+  // Get metadata attached to globals.
+  int GlobalMetadataArgs = 0;
+  SmallVector<std::pair<unsigned, MDNode *>> MDs;
+  for (GlobalVariable &GV : Program->globals()) {
+    GV.getAllMetadata(MDs);
+    GlobalMetadataArgs += MDs.size();
+  }
+
+  // Get metadata attached to functions & instructions.
+  int FunctionMetadataArgs = 0;
+  int InstructionMetadataArgs = 0;
+  for (Function &F : *Program) {
+    F.getAllMetadata(MDs);
+    FunctionMetadataArgs += MDs.size();
+
+    for (Instruction &I : instructions(F)) {
+      I.getAllMetadata(MDs);
+      InstructionMetadataArgs += MDs.size();
+    }
   }
 
-  return UnnamedNodes.size() + NamedMetadataNodes;
+  return NamedMetadataNodes + GlobalMetadataArgs + FunctionMetadataArgs +
+         InstructionMetadataArgs;
 }
 
 void llvm::reduceMetadataDeltaPass(TestRunner &Test) {
   outs() << "*** Reducing Metadata...\n";
   int MDCount = countMetadataTargets(Test.getProgram());
   runDeltaPass(Test, MDCount, extractMetadataFromModule);
   outs() << "----------------------------\n";
 }