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

   1 //===- ReduceMetadata.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 Metadata nodes.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "ReduceMetadata.h"
  15 #include "Delta.h"
  16 #include "llvm/ADT/SmallVector.h"
  17 #include <set>
  18 #include <vector>
  19
  20 using namespace llvm;
  21
  22 /// Adds all Unnamed Metadata Nodes that are inside desired Chunks to set
  23 template <class T>
  24 static void getChunkMetadataNodes(T &MDUser, int &I,
  25                                   const std::vector<Chunk> &ChunksToKeep,
  26                                   std::set<MDNode *> &SeenNodes,
  27                                   std::set<MDNode *> &NodesToKeep) {
  28   SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
  29   MDUser.getAllMetadata(MDs);
  30   for (auto &MD : MDs) {
  31     SeenNodes.insert(MD.second);
  32     if (I < (int)ChunksToKeep.size()) {
  33       if (ChunksToKeep[I].contains(SeenNodes.size()))
  34         NodesToKeep.insert(MD.second);
  35       if (ChunksToKeep[I].end == (int)SeenNodes.size())
  36         ++I;
  37     }
  38   }
  39 }
  40
  41 /// Erases out-of-chunk unnamed metadata nodes from its user
  42 template <class T>
  43 static void eraseMetadataIfOutsideChunk(T &MDUser,
  44                                         const std::set<MDNode *> &NodesToKeep) {
  45   SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
  46   MDUser.getAllMetadata(MDs);
  47   for (int I = 0, E = MDs.size(); I != E; ++I)
  48     if (!NodesToKeep.count(MDs[I].second))
  49       MDUser.setMetadata(I, NULL);
  50 }
  51
  52 /// Removes all the Named and Unnamed Metadata Nodes, as well as any debug
  53 /// functions that aren't inside the desired Chunks.
  54 static void extractMetadataFromModule(const std::vector<Chunk> &ChunksToKeep,
  55                                       Module *Program) {
  56   std::set<MDNode *> SeenNodes;
  57   std::set<MDNode *> NodesToKeep;
  58   int I = 0;
  59
  60   // Add chunk MDNodes used by GVs, Functions, and Instructions to set
  61   for (auto &GV : Program->globals())
  62     getChunkMetadataNodes(GV, I, ChunksToKeep, SeenNodes, NodesToKeep);
  63
  64   for (auto &F : *Program) {
  65     getChunkMetadataNodes(F, I, ChunksToKeep, SeenNodes, NodesToKeep);
  66     for (auto &BB : F)
  67       for (auto &Inst : BB)
  68         getChunkMetadataNodes(Inst, I, ChunksToKeep, SeenNodes, NodesToKeep);
  69   }
  70
  71   // Once more, go over metadata nodes, but deleting the ones outside chunks
  72   for (auto &GV : Program->globals())
  73     eraseMetadataIfOutsideChunk(GV, NodesToKeep);
  74
  75   for (auto &F : *Program) {
  76     eraseMetadataIfOutsideChunk(F, NodesToKeep);
  77     for (auto &BB : F)
  78       for (auto &Inst : BB)
  79         eraseMetadataIfOutsideChunk(Inst, NodesToKeep);
  80   }
  81
  82
  83   // Get out-of-chunk Named metadata nodes
  84   unsigned MetadataCount = SeenNodes.size();
  85   std::vector<NamedMDNode *> NamedNodesToDelete;
  86   for (auto &MD : Program->named_metadata()) {
  87     if (I < (int)ChunksToKeep.size()) {
  88       if (!ChunksToKeep[I].contains(++MetadataCount))
  89         NamedNodesToDelete.push_back(&MD);
  90       if (ChunksToKeep[I].end == (int)SeenNodes.size())
  91         ++I;
  92     } else
  93       NamedNodesToDelete.push_back(&MD);
  94   }
  95
  96   for (auto *NN : NamedNodesToDelete) {
  97     for (int I = 0, E = NN->getNumOperands(); I != E; ++I)
  98       NN->setOperand(I, NULL);
  99     NN->eraseFromParent();
 100   }
 101 }
 102
 103 // Gets unnamed metadata nodes used by a given instruction/GV/function and adds
 104 // them to the set of seen nodes
 105 template <class T>
 106 static void addMetadataToSet(T &MDUser, std::set<MDNode *> &UnnamedNodes) {
 107   SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
 108   MDUser.getAllMetadata(MDs);
 109   for (auto &MD : MDs)
 110     UnnamedNodes.insert(MD.second);
 111 }
 112
 113 /// Returns the amount of Named and Unnamed Metadata Nodes
 114 static int countMetadataTargets(Module *Program) {
 115   std::set<MDNode *> UnnamedNodes;
 116   int NamedMetadataNodes = Program->named_metadata_size();
 117
 118   // Get metadata nodes used by globals
 119   for (auto &GV : Program->globals())
 120     addMetadataToSet(GV, UnnamedNodes);
 121
 122   // Do the same for nodes used by functions & instructions
 123   for (auto &F : *Program) {
 124     addMetadataToSet(F, UnnamedNodes);
 125     for (auto &BB : F)
 126       for (auto &I : BB)
 127         addMetadataToSet(I, UnnamedNodes);
 128   }
 129
 130   return UnnamedNodes.size() + NamedMetadataNodes;
 131 }
 132
 133 void llvm::reduceMetadataDeltaPass(TestRunner &Test) {
 134   outs() << "*** Reducing Metadata...\n";
 135   int MDCount = countMetadataTargets(Test.getProgram());
 136   runDeltaPass(Test, MDCount, extractMetadataFromModule);
 137   outs() << "----------------------------\n";
 138 }