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