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, unsigned &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 < ChunksToKeep.size()) {
33       if (ChunksToKeep[I].contains(SeenNodes.size()))
34         NodesToKeep.insert(MD.second);
35       if (ChunksToKeep[I].end == 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 /// @returns the Module stripped of out-of-chunk MDNodes
55 static void extractMetadataFromModule(const std::vector<Chunk> &ChunksToKeep,
56                                       Module *Program) {
57   std::set<MDNode *> SeenNodes;
58   std::set<MDNode *> NodesToKeep;
59   unsigned I = 0;
60 
61   // Add chunk MDNodes used by GVs, Functions, and Instructions to set
62   for (auto &GV : Program->globals())
63     getChunkMetadataNodes(GV, I, ChunksToKeep, SeenNodes, NodesToKeep);
64 
65   for (auto &F : *Program) {
66     getChunkMetadataNodes(F, I, ChunksToKeep, SeenNodes, NodesToKeep);
67     for (auto &BB : F)
68       for (auto &Inst : BB)
69         getChunkMetadataNodes(Inst, I, ChunksToKeep, SeenNodes, NodesToKeep);
70   }
71 
72   // Once more, go over metadata nodes, but deleting the ones outside chunks
73   for (auto &GV : Program->globals())
74     eraseMetadataIfOutsideChunk(GV, NodesToKeep);
75 
76   for (auto &F : *Program) {
77     eraseMetadataIfOutsideChunk(F, NodesToKeep);
78     for (auto &BB : F)
79       for (auto &Inst : BB)
80         eraseMetadataIfOutsideChunk(Inst, NodesToKeep);
81   }
82 
83 
84   // Get out-of-chunk Named metadata nodes
85   unsigned MetadataCount = SeenNodes.size();
86   std::vector<NamedMDNode *> NamedNodesToDelete;
87   for (auto &MD : Program->named_metadata()) {
88     if (I < ChunksToKeep.size()) {
89       if (!ChunksToKeep[I].contains(++MetadataCount))
90         NamedNodesToDelete.push_back(&MD);
91       if (ChunksToKeep[I].end == SeenNodes.size())
92         ++I;
93     } else
94       NamedNodesToDelete.push_back(&MD);
95   }
96 
97   for (auto *NN : NamedNodesToDelete) {
98     for (int I = 0, E = NN->getNumOperands(); I != E; ++I)
99       NN->setOperand(I, NULL);
100     NN->eraseFromParent();
101   }
102 }
103 
104 // Gets unnamed metadata nodes used by a given instruction/GV/function and adds
105 // them to the set of seen nodes
106 template <class T>
107 static void addMetadataToSet(T &MDUser, std::set<MDNode *> &UnnamedNodes) {
108   SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
109   MDUser.getAllMetadata(MDs);
110   for (auto &MD : MDs)
111     UnnamedNodes.insert(MD.second);
112 }
113 
114 /// Returns the amount of Named and Unnamed Metadata Nodes
115 static unsigned countMetadataTargets(Module *Program) {
116   std::set<MDNode *> UnnamedNodes;
117   int NamedMetadataNodes = Program->named_metadata_size();
118 
119   // Get metadata nodes used by globals
120   for (auto &GV : Program->globals())
121     addMetadataToSet(GV, UnnamedNodes);
122 
123   // Do the same for nodes used by functions & instructions
124   for (auto &F : *Program) {
125     addMetadataToSet(F, UnnamedNodes);
126     for (auto &BB : F)
127       for (auto &I : BB)
128         addMetadataToSet(I, UnnamedNodes);
129   }
130 
131   return UnnamedNodes.size() + NamedMetadataNodes;
132 }
133 
134 void llvm::reduceMetadataDeltaPass(TestRunner &Test) {
135   outs() << "*** Reducing Metadata...\n";
136   unsigned MDCount = countMetadataTargets(Test.getProgram());
137   runDeltaPass(Test, MDCount, extractMetadataFromModule);
138   outs() << "----------------------------\n";
139 }
140