Debian Codegraph @

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

raw
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(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>(CurrentNode->getOperand(I).get())) {
39 // Check whether node has been visited
40 if (VisitedNodes.insert(Operand))
41 NodesToTraverse.push(Operand);
42 // Delete the node only if it is distinct
43 if (Operand->isDistinct()) {
44 // Add to removal list
45 NodesToDelete.insert(std::make_pair(I, CurrentNode));
46 }
47 }
48 }
49
50 // Remove the nodes
51 for (auto [PositionToReplace, Node] : NodesToDelete) {
52 if (!O.shouldKeep())
53 Node->replaceOperandWith(PositionToReplace, 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>((*I))) {
71 if (VisitedNodes.insert(TupleI))
72 NodesToTraverse.push(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(NotToRemove).get();
93 CurrentTuple->replaceOperandWith(NotToRemove, Operand);
94 CurrentTuple->replaceOperandWith(I, 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>(CurrentTuple->getOperand(I).get());
109 if (Operand && VisitedNodes.insert(Operand))
110 // If the node hasn't been traversed yet, add it to the queue of nodes
111 // to traverse.
112 NodesToTraverse.push(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(Program.getContext(), 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>(NamedNode.getOperand(I)))
128 reduceNodes(Operand, NodesToDelete, TemporaryTuple, O, Program);
129 }
130 }
131 for (NamedMDNode &NamedNode : Program.named_metadata())
132 cleanUpTemporaries(NamedNode, TemporaryTuple, Program);
133 }