llvm/tools/llvm-reduce/deltas/ReduceDistinctMetadata.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-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 "Delta.h"
  16 #include "llvm/ADT/Sequence.h"
  17 #include "llvm/ADT/SetVector.h"
  18 #include "llvm/ADT/SmallVector.h"
  19 #include "llvm/IR/InstIterator.h"
  20 #include <algorithm>
  21 #include <queue>
  22
  23 using namespace llvm;
  24
  25 // Traverse the graph breadth-first and try to remove unnamed metadata nodes
  26 static void
  27 reduceNodes(MDNode *Root,
  28             SetVector<std::pair<unsigned int, MDNode *>> &NodesToDelete,
  29             MDNode *TemporaryNode, Oracle &O, Module &Program) {
  30   std::queue<MDNode *> NodesToTraverse{};
  31   // Keep track of visited nodes not to get into loops
  32   SetVector<MDNode *> VisitedNodes{};
  33   NodesToTraverse.push(Root);
  34
  35   while (!NodesToTraverse.empty()) {
  36     MDNode *CurrentNode = NodesToTraverse.front();
  37     NodesToTraverse.pop();
  38
  39     // Mark the nodes for removal
  40     for (unsigned int I = 0; I < CurrentNode->getNumOperands(); ++I) {
  41       if (MDNode *Operand =
  42               dyn_cast_or_null<MDNode>(CurrentNode->getOperand(I).get())) {
  43         // Check whether node has been visited
  44         if (VisitedNodes.insert(Operand))
  45           NodesToTraverse.push(Operand);
  46         // Delete the node only if it is distinct
  47         if (Operand->isDistinct()) {
  48           // Add to removal list
  49           NodesToDelete.insert(std::make_pair(I, CurrentNode));
  50         }
  51       }
  52     }
  53
  54     // Remove the nodes
  55     for (auto [PositionToReplace, Node] : NodesToDelete) {
  56       if (!O.shouldKeep())
  57         Node->replaceOperandWith(PositionToReplace, TemporaryNode);
  58     }
  59     NodesToDelete.clear();
  60   }
  61 }
  62
  63 // After reducing metadata, we need to remove references to the temporary node,
  64 // this is also done with BFS
  65 static void cleanUpTemporaries(NamedMDNode &NamedNode, MDTuple *TemporaryTuple,
  66                                Module &Program) {
  67   std::queue<MDTuple *> NodesToTraverse{};
  68   SetVector<MDTuple *> VisitedNodes{};
  69
  70   // Push all first level operands of the named node to the queue
  71   for (auto I = NamedNode.op_begin(); I != NamedNode.op_end(); ++I) {
  72     // If the node hasn't been traversed yet, add it to the queue of nodes to
  73     // traverse.
  74     if (MDTuple *TupleI = dyn_cast_or_null<MDTuple>((*I))) {
  75       if (VisitedNodes.insert(TupleI))
  76         NodesToTraverse.push(TupleI);
  77     }
  78   }
  79
  80   while (!NodesToTraverse.empty()) {
  81     MDTuple *CurrentTuple = NodesToTraverse.front();
  82     NodesToTraverse.pop();
  83
  84     // Shift all of the interesting elements to the left, pop remaining
  85     // afterwards
  86     if (CurrentTuple->isDistinct()) {
  87       // Do resizing and cleaning operations only if the node is distinct,
  88       // as resizing is not supported for unique nodes and is redundant.
  89       unsigned int NotToRemove = 0;
  90       for (unsigned int I = 0; I < CurrentTuple->getNumOperands(); ++I) {
  91         Metadata *Operand = CurrentTuple->getOperand(I).get();
  92         // If current operand is not the temporary node, move it to the front
  93         // and increase notToRemove so that it will be saved
  94         if (Operand != TemporaryTuple) {
  95           Metadata *TemporaryMetadata =
  96               CurrentTuple->getOperand(NotToRemove).get();
  97           CurrentTuple->replaceOperandWith(NotToRemove, Operand);
  98           CurrentTuple->replaceOperandWith(I, TemporaryMetadata);
  99           ++NotToRemove;
 100         }
 101       }
 102
 103       // Remove all the uninteresting elements
 104       unsigned int OriginalOperands = CurrentTuple->getNumOperands();
 105       for (unsigned int I = 0; I < OriginalOperands - NotToRemove; ++I)
 106         CurrentTuple->pop_back();
 107     }
 108
 109     // Push the remaining nodes into the queue
 110     for (unsigned int I = 0; I < CurrentTuple->getNumOperands(); ++I) {
 111       MDTuple *Operand =
 112           dyn_cast_or_null<MDTuple>(CurrentTuple->getOperand(I).get());
 113       if (Operand && VisitedNodes.insert(Operand))
 114         // If the node hasn't been traversed yet, add it to the queue of nodes
 115         // to traverse.
 116         NodesToTraverse.push(Operand);
 117     }
 118   }
 119 }
 120
 121 static void extractDistinctMetadataFromModule(Oracle &O,
 122                                               ReducerWorkItem &WorkItem) {
 123   Module &Program = WorkItem.getModule();
 124   MDTuple *TemporaryTuple =
 125       MDTuple::getDistinct(Program.getContext(), SmallVector<Metadata *, 1>{});
 126   SetVector<std::pair<unsigned int, MDNode *>> NodesToDelete{};
 127   for (NamedMDNode &NamedNode :
 128        Program.named_metadata()) { // Iterate over the named nodes
 129     for (unsigned int I = 0; I < NamedNode.getNumOperands();
 130          ++I) { // Iterate over first level unnamed nodes..
 131       if (MDTuple *Operand = dyn_cast_or_null<MDTuple>(NamedNode.getOperand(I)))
 132         reduceNodes(Operand, NodesToDelete, TemporaryTuple, O, Program);
 133     }
 134   }
 135   for (NamedMDNode &NamedNode : Program.named_metadata())
 136     cleanUpTemporaries(NamedNode, TemporaryTuple, Program);
 137 }
 138
 139 void llvm::reduceDistinctMetadataDeltaPass(TestRunner &Test) {
 140   runDeltaPass(Test, extractDistinctMetadataFromModule,
 141                "Reducing Distinct Metadata");
 142 }