134 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements two functions used by the Generic Delta Debugging10// 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 nodes22static void23reduceNodes(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 loops28 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 removal36 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 visited40 if (VisitedNodes.insert(Operand))41 NodesToTraverse.push(Operand);42 // Delete the node only if it is distinct43 if (Operand->isDistinct()) {44 // Add to removal list45 NodesToDelete.insert(std::make_pair(I, CurrentNode));46 }47 }48 }49 50 // Remove the nodes51 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 BFS61static 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 queue67 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 to69 // 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 remaining81 // afterwards82 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 front89 // and increase notToRemove so that it will be saved90 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 elements100 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 queue106 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 nodes111 // to traverse.112 NodesToTraverse.push(Operand);113 }114 }115}116 117void 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 nodes125 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}134