1//===- ReduceDistinctMetadata.cpp - Specialized Delta Pass ----------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements two functions used by the Generic Delta Debugging
10// Algorithm, which are used to reduce unnamed distinct metadata nodes.
11//
12//===----------------------------------------------------------------------===//
13
14#include "ReduceDistinctMetadata.h"
15#include "llvm/ADT/SetVector.h"
16#include "llvm/ADT/SmallVector.h"
17#include <queue>
18
19using namespace llvm;
20
21// Traverse the graph breadth-first and try to remove unnamed metadata nodes
22static void
23reduceNodes(MDNode *Root,
24 SetVector<std::pair<unsigned int, MDNode *>> &NodesToDelete,
25 MDNode *TemporaryNode, Oracle &O, Module &Program) {
26 std::queue<MDNode *> NodesToTraverse{};
27 // Keep track of visited nodes not to get into loops
28 SetVector<MDNode *> VisitedNodes{};
29 NodesToTraverse.push(x: Root);
30
31 while (!NodesToTraverse.empty()) {
32 MDNode *CurrentNode = NodesToTraverse.front();
33 NodesToTraverse.pop();
34
35 // Mark the nodes for removal
36 for (unsigned int I = 0; I < CurrentNode->getNumOperands(); ++I) {
37 if (MDNode *Operand =
38 dyn_cast_or_null<MDNode>(Val: CurrentNode->getOperand(I).get())) {
39 // Check whether node has been visited
40 if (VisitedNodes.insert(X: Operand))
41 NodesToTraverse.push(x: Operand);
42 // Delete the node only if it is distinct
43 if (Operand->isDistinct()) {
44 // Add to removal list
45 NodesToDelete.insert(X: std::make_pair(x&: I, y&: CurrentNode));
46 }
47 }
48 }
49
50 // Remove the nodes
51 for (auto [PositionToReplace, Node] : NodesToDelete) {
52 if (!O.shouldKeep())
53 Node->replaceOperandWith(I: PositionToReplace, New: TemporaryNode);
54 }
55 NodesToDelete.clear();
56 }
57}
58
59// After reducing metadata, we need to remove references to the temporary node,
60// this is also done with BFS
61static void cleanUpTemporaries(NamedMDNode &NamedNode, MDTuple *TemporaryTuple,
62 Module &Program) {
63 std::queue<MDTuple *> NodesToTraverse{};
64 SetVector<MDTuple *> VisitedNodes{};
65
66 // Push all first level operands of the named node to the queue
67 for (auto I = NamedNode.op_begin(); I != NamedNode.op_end(); ++I) {
68 // If the node hasn't been traversed yet, add it to the queue of nodes to
69 // traverse.
70 if (MDTuple *TupleI = dyn_cast_or_null<MDTuple>(Val: (*I))) {
71 if (VisitedNodes.insert(X: TupleI))
72 NodesToTraverse.push(x: TupleI);
73 }
74 }
75
76 while (!NodesToTraverse.empty()) {
77 MDTuple *CurrentTuple = NodesToTraverse.front();
78 NodesToTraverse.pop();
79
80 // Shift all of the interesting elements to the left, pop remaining
81 // afterwards
82 if (CurrentTuple->isDistinct()) {
83 // Do resizing and cleaning operations only if the node is distinct,
84 // as resizing is not supported for unique nodes and is redundant.
85 unsigned int NotToRemove = 0;
86 for (unsigned int I = 0; I < CurrentTuple->getNumOperands(); ++I) {
87 Metadata *Operand = CurrentTuple->getOperand(I).get();
88 // If current operand is not the temporary node, move it to the front
89 // and increase notToRemove so that it will be saved
90 if (Operand != TemporaryTuple) {
91 Metadata *TemporaryMetadata =
92 CurrentTuple->getOperand(I: NotToRemove).get();
93 CurrentTuple->replaceOperandWith(I: NotToRemove, New: Operand);
94 CurrentTuple->replaceOperandWith(I, New: TemporaryMetadata);
95 ++NotToRemove;
96 }
97 }
98
99 // Remove all the uninteresting elements
100 unsigned int OriginalOperands = CurrentTuple->getNumOperands();
101 for (unsigned int I = 0; I < OriginalOperands - NotToRemove; ++I)
102 CurrentTuple->pop_back();
103 }
104
105 // Push the remaining nodes into the queue
106 for (unsigned int I = 0; I < CurrentTuple->getNumOperands(); ++I) {
107 MDTuple *Operand =
108 dyn_cast_or_null<MDTuple>(Val: CurrentTuple->getOperand(I).get());
109 if (Operand && VisitedNodes.insert(X: Operand))
110 // If the node hasn't been traversed yet, add it to the queue of nodes
111 // to traverse.
112 NodesToTraverse.push(x: Operand);
113 }
114 }
115}
116
117void llvm::reduceDistinctMetadataDeltaPass(Oracle &O,
118 ReducerWorkItem &WorkItem) {
119 Module &Program = WorkItem.getModule();
120 MDTuple *TemporaryTuple =
121 MDTuple::getDistinct(Context&: Program.getContext(), MDs: SmallVector<Metadata *, 1>{});
122 SetVector<std::pair<unsigned int, MDNode *>> NodesToDelete{};
123 for (NamedMDNode &NamedNode :
124 Program.named_metadata()) { // Iterate over the named nodes
125 for (unsigned int I = 0; I < NamedNode.getNumOperands();
126 ++I) { // Iterate over first level unnamed nodes..
127 if (MDTuple *Operand = dyn_cast_or_null<MDTuple>(Val: NamedNode.getOperand(i: I)))
128 reduceNodes(Root: Operand, NodesToDelete, TemporaryNode: TemporaryTuple, O, Program);
129 }
130 }
131 for (NamedMDNode &NamedNode : Program.named_metadata())
132 cleanUpTemporaries(NamedNode, TemporaryTuple, Program);
133}
134