| 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 |
} |