1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
//===- 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_or_null<MDNode>(CurrentNode->getOperand(I).get())) {
// Check whether node has been visited
if (VisitedNodes.insert(Operand))
NodesToTraverse.push(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_or_null<MDTuple>((*I))) {
if (VisitedNodes.insert(TupleI))
NodesToTraverse.push(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_or_null<MDTuple>(CurrentTuple->getOperand(I).get());
if (Operand && VisitedNodes.insert(Operand))
// If the node hasn't been traversed yet, add it to the queue of nodes
// to traverse.
NodesToTraverse.push(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_or_null<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");
}
|
