[Bugpoint redesign] Added pass to reduce Metadata

[diegotf]

Summary

This pass tries to reduce named & unnamed metadata nodes from an IR file, as well as any declared debug functions (as well as their calls).

[diegotf]

Re-worded file header comment and added newline to ReduceMetadata.cpp

[dblaikie]

llvm/tools/llvm-reduce/DeltaManager.h

19–40 ↗

(On Diff #210919)

Anonymous namespaces and static variables aren't suitable for header files (they can lead to ODR violations, etc) You can inline these things inside runDeltaPasses (using lambdas for local functions, etc) or take the runDeltaPasses definition out of line into a .cc file and move these static variables/anonymous namespace content to there.

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

15 ↗

(On Diff #210919)

Might've been a bit easier to do some of these renames as separate patches - super easy to review (or commit without review) & keeps the "interesting" reviews uncluttered.

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

20 ↗

(On Diff #210919)

Is this intentionally passed by value for some reason? (usually a non-trivial data structure like a std::vector would be passed by const ref if a copy isn't needed, etc)

[diegotf]

Made ChunksToKeep a const ref in function params & moved DeltaPasses cl option to main cpp file

[diegotf]

llvm/tools/llvm-reduce/DeltaManager.h

19–40 ↗

(On Diff #210919)

I don't know why I keep forgetting this, I swear I'll tattoo it on my arm next time I forget haha.

Thanks for the comment, David.

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

15 ↗

(On Diff #210919)

My bad, I'll do that from now on :)

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

20 ↗

(On Diff #210919)

Good catch, I forgot to pass it as const ref.

I'll make another patch later with the same fix on other Delta Passes to reduce the clutter on this diff

[dblaikie]

The goal of this pass is to be able to remove as many intrinsic calls and metadata (debug info and non-debug info metadata alike) while still preserving the "interestingness". I would figure maybe some more testing would be appropriate - since this currently only tests (if I understand the test) that it can remove all of these things - not that it preserves any of them at any time? Perhaps some tests for certain interesting metadata and intrinsics to ensure some are preserved?

(also, if the goal is to make a more streamlined reduction tool - maybe it'd be good to avoid adding a new command line argument/tweakable knob? & have more targeted tests/interestingness test? (to make tests more legible, I wonder if it'd be handy to keep the interestingness test inside the test - in the form of catting it out to a file from the .ll test file?))

llvm/tools/llvm-reduce/llvm-reduce.cpp

56–76 ↗

(On Diff #211219)

Is this idiomatic? (are there other uses of cl options that use a similar structure (indirecting through cl::location, then storing to another variable?) - I just haven't seen it done that way & wonder if there's some other cl::opt usage that would be more suitable/common)

[diegotf]

In D65026#1596697, @dblaikie wrote:

The goal of this pass is to be able to remove as many intrinsic calls and metadata (debug info and non-debug info metadata alike) while still preserving the "interestingness". I would figure maybe some more testing would be appropriate - since this currently only tests (if I understand the test) that it can remove all of these things - not that it preserves any of them at any time? Perhaps some tests for certain interesting metadata and intrinsics to ensure some are preserved?

That's very good insight, I'll modify the test so it verifies interesting metadata is preserved.

(also, if the goal is to make a more streamlined reduction tool - maybe it'd be good to avoid adding a new command line argument/tweakable knob? & have more targeted tests/interestingness test? (to make tests more legible, I wonder if it'd be handy to keep the interestingness test inside the test - in the form of catting it out to a file from the .ll test file?))

I thought about the complexity the run-only might add, but since this tool will probably be integrated into the bugpoint tool itself, the option will mainly be used for testing purposes. Although I agree that tests need to be more targeted, and tackling this might solve the need for the former.

llvm/tools/llvm-reduce/llvm-reduce.cpp

56–76 ↗

(On Diff #211219)

I found it quite odd as well, and I took it straight from llc.cpp (line 163).

But now that you mention it, I think I'll move the struct's behaviour to a helper function, since it adds unnecessary complexity

[diegotf]

Added more targeted tests & fixed off-by-one variable init. on ReduceFunctions.cpp and ReduceGlobalVars.cpp

[diegotf]

Changed pass to reflect changes in base diff, moved interesting-ness test to python & changed test so it only reduces certain metadata (previously it just stripped everything)

[diegotf]

Added missing check in test

[diegotf]

Removed some stale changes that have since been integrated into base

[dblaikie]

llvm/test/Reduce/remove-metadata.ll

1 ↗

(On Diff #214259)

Would it be possible to test this without specifically debug info metadata? If the feature is general over all metadata it might be clearer to demonstrate with less IR (fewer metadata nodes, if they don't have to form a complete debug info metadata graph, etc).

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

10–11 ↗

(On Diff #214259)

Any reason debug functions would need to be a special case here, rather than handled as a consequence of a general pass that removes any functions?

[diegotf]

llvm/test/Reduce/remove-metadata.ll

1 ↗

(On Diff #214259)

Agreed, I'll modify the test so it only contains fewer unnamed metadata nodes (and no !dbg metadata)

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

10–11 ↗

(On Diff #214259)

Yeah, since ReduceFunctions.cpp only considers defined functions, they would be ignored. Though I've been thinking about changing that lately...

I'll cook up a quick diff so this pass doesn't have to consider debug functions.

[diegotf]

Pass doesn't consider debug functions anymore since D66257 takes care of them.

Simplified test so there's less IR noise

[dblaikie]

llvm/test/Reduce/remove-metadata.ll

8–24 ↗

(On Diff #215269)

Could you change all of this metadata (both named and unnamed) to be more "arbitrary" rather than special llvm things - use some metasyntactic variable names (foo/bar/baz, etc) and only include as much as is needed to test the code? (so I guess only two named (one that's kept, one that's dropped) and two unnamed nodes)?

Probably actively test /for/ the presence of the things that remain (and a CHECK-NOT: ! after it, just to be "and no other nodes after this" rather than having to explain why 3 is the right number)

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

60 ↗

(On Diff #215269)

This is for removing metadata from functions, right? But there's no testing for metadata on functions anymore - does that testing need to be added?

[diegotf]

Simplified test & Added check to verify pass removes metadata from globals, functions & instructions.

llvm/test/Reduce/remove-metadata.ll

8–24 ↗

(On Diff #215269)

done!

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

60 ↗

(On Diff #215269)

Yes, let me add a little function to the test

[diegotf]

Updated test to output to STDOUT, instead of reduced.ll

[dblaikie]

From the discussion on https://reviews.llvm.org/D66110 - would it be possible/good to rewrite the "correctness" script to be a one-size-fits-all - diffing against a golden file of expected output (& maybe somehow deriving the golden file name from the original file name - which might be best achieved by copying both files to a temp directory)?

Like I said on that other review, I'm understanding of hesitance around golden files - and in this case it means another file to do IR upgrades on when LLVM textual IR changes (but most of those are done en-mass, so I don't think having twice the number of files for these tests is particularly problematic - there are already lots of other .ll files in Inputs directories around LLVM's tests, so anyone doing mass migration would already be scanning/patching them).

By doing it this way, it'll be easier to read in some ways - comparing one IR file to another (diffing, for instance). No need to complicate the interestingness test with novel ways to preserve features that aren't under test but are needed for the test (like preserving certain functions when you're trying to test that the metadata is removed from within the function).

[xbolva00]

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

54

this method returns nothing

[thakis]

The test added in this change has a file leak that causes all possible temp file patterns to be created, at which point it starts failing, see https://bugs.llvm.org/show_bug.cgi?id=43278 (Diego, I tried to cc you, but bugzilla didn't know your email address.) Can you please take a look, and revert if it takes a while to investigate? (remove-funcs seems to have the same problem.)

[dblaikie]

In D65026#1666176, @thakis wrote:

The test added in this change has a file leak that causes all possible temp file patterns to be created, at which point it starts failing, see https://bugs.llvm.org/show_bug.cgi?id=43278 (Diego, I tried to cc you, but bugzilla didn't know your email address.) Can you please take a look, and revert if it takes a while to investigate? (remove-funcs seems to have the same problem.)

All the tests work roughly the same way, so I expect they're all broken in roughly the same way.

I'll look into it/them. Might disable the tests in the short term to keep the buildbots happy.

[w2yehia]

Just FYI, that our (IBM's) internal bots are also breaking because the following tests are not cleaning the build/test/Reduce/tmp folder:

LLVM :: Reduce/remove-funcs.ll
LLVM :: Reduce/remove-metadata.ll

And we're forced to sometimes do a clean build.

[dblaikie]

In D65026#1666621, @w2yehia wrote:

Just FYI, that our (IBM's) internal bots are also breaking because the following tests are not cleaning the build/test/Reduce/tmp folder:

LLVM :: Reduce/remove-funcs.ll
LLVM :: Reduce/remove-metadata.ll

And we're forced to sometimes do a clean build.

In D65026#1666176, @thakis wrote:

The test added in this change has a file leak that causes all possible temp file patterns to be created, at which point it starts failing, see https://bugs.llvm.org/show_bug.cgi?id=43278 (Diego, I tried to cc you, but bugzilla didn't know your email address.) Can you please take a look, and revert if it takes a while to investigate? (remove-funcs seems to have the same problem.)

Fixed in r371696 - thanks for the reports/identifying the issue!

llvm/trunk/test/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/trunk/test/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: rm -rf %t
+; RUN: mkdir %t
+; copy the test file to preserve executable bit
+; RUN: cp %p/Inputs/remove-metadata.py %t/test.py
+; get the python path from lit
+; RUN: echo "#!" %python > %t/test.py
+; then include the rest of the test script
+; RUN: cat %p/Inputs/remove-metadata.py >> %t/test.py
+
+; RUN: llvm-reduce --test %t/test.py %s -o %t/out.ll
+; RUN: cat %t/out.ll | FileCheck -implicit-check-not=! %s
+; REQUIRES: plugins
+
+@global = global i32 0, !dbg !0
+
+define void @main() !dbg !0 {
+   ret void, !dbg !0
+}
+
+!uninteresting = !{!0}
+; CHECK: !interesting = !{!0}
+!interesting = !{!1}
+
+!0 = !{!"uninteresting"}
+; CHECK: !0 = !{!"interesting"}
+!1 = !{!"interesting"}

llvm/trunk/tools/llvm-reduce/CMakeLists.txt

 set(LLVM_NO_DEAD_STRIP 1)
 
 add_llvm_tool(llvm-reduce
   llvm-reduce.cpp
   TestRunner.cpp
   deltas/Delta.cpp
   deltas/ReduceFunctions.cpp
   deltas/ReduceGlobalVars.cpp
+  deltas/ReduceMetadata.cpp
 
   DEPENDS
   intrinsics_gen
   )
 export_executable_symbols(llvm-reduce)

llvm/trunk/tools/llvm-reduce/DeltaManager.h

 // file.
 //
 //===----------------------------------------------------------------------===//
 
 #include "TestRunner.h"
 #include "deltas/Delta.h"
 #include "deltas/ReduceFunctions.h"
 #include "deltas/ReduceGlobalVars.h"
+#include "deltas/ReduceMetadata.h"
 
 namespace llvm {
 
 // TODO: Add CLI option to run only specified Passes (for unit tests)
 inline void runDeltaPasses(TestRunner &Tester) {
-  outs() << "Reducing functions...\n";
   reduceFunctionsDeltaPass(Tester);
-  outs() << "Reducing GVs...\n";
   reduceGlobalsDeltaPass(Tester);
+  reduceMetadataDeltaPass(Tester);
   // TODO: Implement the remaining Delta Passes
 }
 
 } // namespace llvm

llvm/trunk/tools/llvm-reduce/deltas/ReduceMetadata.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.
+//
+//===----------------------------------------------------------------------===//
+
+#include "TestRunner.h"
+
+namespace llvm {
+void reduceMetadataDeltaPass(TestRunner &Test);
+} // namespace llvm

llvm/trunk/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/SmallVector.h"
+#include <set>
+#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, unsigned &I,
+                                  const std::vector<Chunk> &ChunksToKeep,
+                                  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 (I < ChunksToKeep.size()) {
+      if (ChunksToKeep[I].contains(SeenNodes.size()))
+        NodesToKeep.insert(MD.second);
+      if (ChunksToKeep[I].end == SeenNodes.size())
+        ++I;
+    }
+  }
+}
+
+/// 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.
+/// @returns the Module stripped of out-of-chunk MDNodes
+static void extractMetadataFromModule(const std::vector<Chunk> &ChunksToKeep,
+                                      Module *Program) {
+  std::set<MDNode *> SeenNodes;
+  std::set<MDNode *> NodesToKeep;
+  unsigned I = 0;
+
+  // Add chunk MDNodes used by GVs, Functions, and Instructions to set
+  for (auto &GV : Program->globals())
+    getChunkMetadataNodes(GV, I, ChunksToKeep, SeenNodes, NodesToKeep);
+
+  for (auto &F : *Program) {
+    getChunkMetadataNodes(F, I, ChunksToKeep, SeenNodes, NodesToKeep);
+    for (auto &BB : F)
+      for (auto &Inst : BB)
+        getChunkMetadataNodes(Inst, I, ChunksToKeep, 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
+  unsigned MetadataCount = SeenNodes.size();
+  std::vector<NamedMDNode *> NamedNodesToDelete;
+  for (auto &MD : Program->named_metadata()) {
+    if (I < ChunksToKeep.size()) {
+      if (!ChunksToKeep[I].contains(++MetadataCount))
+        NamedNodesToDelete.push_back(&MD);
+      if (ChunksToKeep[I].end == SeenNodes.size())
+        ++I;
+    } else
+      NamedNodesToDelete.push_back(&MD);
+  }
+
+  for (auto *NN : NamedNodesToDelete) {
+    for (int I = 0, E = NN->getNumOperands(); I != E; ++I)
+      NN->setOperand(I, NULL);
+    NN->eraseFromParent();
+  }
+}
+
+// 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);
+}
+
+/// Returns the amount of Named and Unnamed Metadata Nodes
+static unsigned 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);
+  }
+
+  return UnnamedNodes.size() + NamedMetadataNodes;
+}
+
+void llvm::reduceMetadataDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing Metadata...\n";
+  unsigned MDCount = countMetadataTargets(Test.getProgram());
+  runDeltaPass(Test, MDCount, extractMetadataFromModule);
+  outs() << "----------------------------\n";
+}