[LLVM-Reduce] - Distinct Metadata Reduction (#104624)

5 files changed, 191 insertions, 9 deletions

diff --git a/llvm/tools/llvm-reduce/CMakeLists.txt b/llvm/tools/llvm-reduce/CMakeLists.txt
index a4c605f..b8ad6f7 100644
--- a/llvm/tools/llvm-reduce/CMakeLists.txt
+++ b/llvm/tools/llvm-reduce/CMakeLists.txt
@@ -31,6 +31,7 @@ add_llvm_tool(llvm-reduce
   deltas/ReduceAttributes.cpp
   deltas/ReduceBasicBlocks.cpp
   deltas/ReduceDIMetadata.cpp
+  deltas/ReduceDistinctMetadata.cpp
   deltas/ReduceDbgRecords.cpp
   deltas/ReduceFunctionBodies.cpp
   deltas/ReduceFunctions.cpp
diff --git a/llvm/tools/llvm-reduce/DeltaManager.cpp b/llvm/tools/llvm-reduce/DeltaManager.cpp
index 67fbc2f..624b530 100644
--- a/llvm/tools/llvm-reduce/DeltaManager.cpp
+++ b/llvm/tools/llvm-reduce/DeltaManager.cpp
@@ -21,6 +21,7 @@
 #include "deltas/ReduceBasicBlocks.h"
 #include "deltas/ReduceDIMetadata.h"
 #include "deltas/ReduceDbgRecords.h"
+#include "deltas/ReduceDistinctMetadata.h"
 #include "deltas/ReduceFunctionBodies.h"
 #include "deltas/ReduceFunctions.h"
 #include "deltas/ReduceGlobalObjects.h"
@@ -93,6 +94,7 @@ static cl::list<std::string>
     DELTA_PASS("global-variables", reduceGlobalsDeltaPass)                     \
     DELTA_PASS("di-metadata", reduceDIMetadataDeltaPass)                       \
     DELTA_PASS("dbg-records", reduceDbgRecordDeltaPass)                        \
+    DELTA_PASS("distinct-metadata", reduceDistinctMetadataDeltaPass)           \
     DELTA_PASS("metadata", reduceMetadataDeltaPass)                            \
     DELTA_PASS("named-metadata", reduceNamedMetadataDeltaPass)                 \
     DELTA_PASS("arguments", reduceArgumentsDeltaPass)                          \
@@ -112,7 +114,7 @@ static cl::list<std::string>
     DELTA_PASS("atomic-ordering", reduceAtomicOrderingDeltaPass)               \
     DELTA_PASS("syncscopes", reduceAtomicSyncScopesDeltaPass)                  \
     DELTA_PASS("instruction-flags", reduceInstructionFlagsDeltaPass)           \
-} while (false)
+  } while (false)
 
 #define DELTA_PASSES_MIR                                                       \
   do {                                                                         \
diff --git a/llvm/tools/llvm-reduce/deltas/ReduceDistinctMetadata.cpp b/llvm/tools/llvm-reduce/deltas/ReduceDistinctMetadata.cpp
new file mode 100644
index 0000000..32fca80
--- /dev/null
+++ b/llvm/tools/llvm-reduce/deltas/ReduceDistinctMetadata.cpp
@@ -0,0 +1,147 @@
+//===- ReduceDistinctMetadata.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 unnamed distinct metadata nodes.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ReduceDistinctMetadata.h"
+#include "Delta.h"
+#include "llvm/ADT/Sequence.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/InstIterator.h"
+#include <algorithm>
+#include <queue>
+
+using namespace llvm;
+
+// Traverse the graph breadth-first and try to remove unnamed metadata nodes
+static void
+reduceNodes(MDNode *Root,
+            SetVector<std::pair<unsigned int, MDNode *>> &NodesToDelete,
+            MDNode *TemporaryNode, Oracle &O, Module &Program) {
+  std::queue<MDNode *> NodesToTraverse{};
+  // Keep track of visited nodes not to get into loops
+  SetVector<MDNode *> VisitedNodes{};
+  NodesToTraverse.push(Root);
+
+  while (!NodesToTraverse.empty()) {
+    MDNode *CurrentNode = NodesToTraverse.front();
+    NodesToTraverse.pop();
+
+    // Mark the nodes for removal
+    for (unsigned int I = 0; I < CurrentNode->getNumOperands(); ++I) {
+      if (MDNode *Operand =
+              dyn_cast<MDNode>(CurrentNode->getOperand(I).get())) {
+        // Check whether node has been visited
+        if (!VisitedNodes.contains(Operand)) {
+          NodesToTraverse.push(Operand);
+          VisitedNodes.insert(Operand);
+        }
+        // Delete the node only if it is distinct
+        if (Operand->isDistinct()) {
+          // Add to removal list
+          NodesToDelete.insert(std::make_pair(I, CurrentNode));
+        }
+      }
+    }
+
+    // Remove the nodes
+    for (auto [PositionToReplace, Node] : NodesToDelete) {
+      if (!O.shouldKeep())
+        Node->replaceOperandWith(PositionToReplace, TemporaryNode);
+    }
+    NodesToDelete.clear();
+  }
+}
+
+// After reducing metadata, we need to remove references to the temporary node,
+// this is also done with BFS
+static void cleanUpTemporaries(NamedMDNode &NamedNode, MDTuple *TemporaryTuple,
+                               Module &Program) {
+  std::queue<MDTuple *> NodesToTraverse{};
+  SetVector<MDTuple *> VisitedNodes{};
+
+  // Push all first level operands of the named node to the queue
+  for (auto I = NamedNode.op_begin(); I != NamedNode.op_end(); ++I) {
+    // If the node hasn't been traversed yet, add it to the queue of nodes to
+    // traverse.
+    if (MDTuple *TupleI = dyn_cast<MDTuple>((*I))) {
+      if (!VisitedNodes.contains(TupleI)) {
+        NodesToTraverse.push(TupleI);
+        VisitedNodes.insert(TupleI);
+      }
+    }
+  }
+
+  while (!NodesToTraverse.empty()) {
+    MDTuple *CurrentTuple = NodesToTraverse.front();
+    NodesToTraverse.pop();
+
+    // Shift all of the interesting elements to the left, pop remaining
+    // afterwards
+    if (CurrentTuple->isDistinct()) {
+      // Do resizing and cleaning operations only if the node is distinct,
+      // as resizing is not supported for unique nodes and is redundant.
+      unsigned int NotToRemove = 0;
+      for (unsigned int I = 0; I < CurrentTuple->getNumOperands(); ++I) {
+        Metadata *Operand = CurrentTuple->getOperand(I).get();
+        // If current operand is not the temporary node, move it to the front
+        // and increase notToRemove so that it will be saved
+        if (Operand != TemporaryTuple) {
+          Metadata *TemporaryMetadata =
+              CurrentTuple->getOperand(NotToRemove).get();
+          CurrentTuple->replaceOperandWith(NotToRemove, Operand);
+          CurrentTuple->replaceOperandWith(I, TemporaryMetadata);
+          ++NotToRemove;
+        }
+      }
+
+      // Remove all the uninteresting elements
+      unsigned int OriginalOperands = CurrentTuple->getNumOperands();
+      for (unsigned int I = 0; I < OriginalOperands - NotToRemove; ++I)
+        CurrentTuple->pop_back();
+    }
+
+    // Push the remaining nodes into the queue
+    for (unsigned int I = 0; I < CurrentTuple->getNumOperands(); ++I) {
+      MDTuple *Operand = dyn_cast<MDTuple>(CurrentTuple->getOperand(I).get());
+      if (Operand && !VisitedNodes.contains(Operand)) {
+        NodesToTraverse.push(Operand);
+        // If the node hasn't been traversed yet, add it to the queue of nodes
+        // to traverse.
+        VisitedNodes.insert(Operand);
+      }
+    }
+  }
+}
+
+static void extractDistinctMetadataFromModule(Oracle &O,
+                                              ReducerWorkItem &WorkItem) {
+  Module &Program = WorkItem.getModule();
+  MDTuple *TemporaryTuple =
+      MDTuple::getDistinct(Program.getContext(), SmallVector<Metadata *, 1>{});
+  SetVector<std::pair<unsigned int, MDNode *>> NodesToDelete{};
+  for (NamedMDNode &NamedNode :
+       Program.named_metadata()) { // Iterate over the named nodes
+    for (unsigned int I = 0; I < NamedNode.getNumOperands();
+         ++I) { // Iterate over first level unnamed nodes..
+      if (MDTuple *Operand = dyn_cast<MDTuple>(NamedNode.getOperand(I)))
+        reduceNodes(Operand, NodesToDelete, TemporaryTuple, O, Program);
+    }
+  }
+  for (NamedMDNode &NamedNode : Program.named_metadata())
+    cleanUpTemporaries(NamedNode, TemporaryTuple, Program);
+}
+
+void llvm::reduceDistinctMetadataDeltaPass(TestRunner &Test) {
+  runDeltaPass(Test, extractDistinctMetadataFromModule,
+               "Reducing Distinct Metadata");
+}
diff --git a/llvm/tools/llvm-reduce/deltas/ReduceDistinctMetadata.h b/llvm/tools/llvm-reduce/deltas/ReduceDistinctMetadata.h
new file mode 100644
index 0000000..d02e8e6
--- /dev/null
+++ b/llvm/tools/llvm-reduce/deltas/ReduceDistinctMetadata.h
@@ -0,0 +1,23 @@
+//===- ReduceDistinctMetadata.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_REDUCEDISTINCTMETADATA_H
+#define LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEDISTINCTMETADATA_H
+
+#include "TestRunner.h"
+
+namespace llvm {
+void reduceDistinctMetadataDeltaPass(TestRunner &Test);
+} // namespace llvm
+
+#endif
diff --git a/llvm/tools/llvm-reduce/deltas/ReduceMetadata.cpp b/llvm/tools/llvm-reduce/deltas/ReduceMetadata.cpp
index 30bf612..316c748 100644
--- a/llvm/tools/llvm-reduce/deltas/ReduceMetadata.cpp
+++ b/llvm/tools/llvm-reduce/deltas/ReduceMetadata.cpp
@@ -20,6 +20,13 @@
 
 using namespace llvm;
 
+extern cl::OptionCategory LLVMReduceOptions;
+
+static cl::opt<bool> AggressiveMetadataReduction(
+    "aggressive-named-md-reduction",
+    cl::desc("Reduce named metadata without taking its type into account"),
+    cl::cat(LLVMReduceOptions));
+
 static bool shouldKeepDebugIntrinsicMetadata(Instruction &I, MDNode &MD) {
   return isa<DILocation>(MD) && isa<DbgInfoIntrinsic>(I);
 }
@@ -44,24 +51,26 @@ static constexpr StringLiteral ListNamedMetadata[] = {
 static void reduceNamedMetadataOperands(Oracle &O, ReducerWorkItem &WorkItem) {
   Module &M = WorkItem.getModule();
 
-  for (StringRef MDName : ListNamedMetadata) {
-    NamedMDNode *NamedNode = M.getNamedMetadata(MDName);
-    if (!NamedNode)
+  for (NamedMDNode &I : M.named_metadata()) {
+    // If we don't want to reduce mindlessly, check if our node is part of
+    // ListNamedMetadata before reducing it
+    if (!AggressiveMetadataReduction &&
+        !is_contained(ListNamedMetadata, I.getName()))
       continue;
 
     bool MadeChange = false;
-    SmallVector<MDNode *, 16> KeptOperands;
-    for (auto I : seq<unsigned>(0, NamedNode->getNumOperands())) {
+    SmallVector<MDNode *> KeptOperands;
+    for (auto J : seq<unsigned>(0, I.getNumOperands())) {
       if (O.shouldKeep())
-        KeptOperands.push_back(NamedNode->getOperand(I));
+        KeptOperands.push_back(I.getOperand(J));
       else
         MadeChange = true;
     }
 
     if (MadeChange) {
-      NamedNode->clearOperands();
+      I.clearOperands();
       for (MDNode *KeptOperand : KeptOperands)
-        NamedNode->addOperand(KeptOperand);
+        I.addOperand(KeptOperand);
     }
   }
 }