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 | |
19 | using namespace llvm; |
20 | |
21 | // Traverse the graph breadth-first and try to remove unnamed metadata nodes |
22 | static void |
23 | reduceNodes(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 |
61 | static 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 | |
117 | void 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 | |