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>
getChunkMetadataNodes(T & MDUser,Oracle & O,std::set<MDNode * > & SeenNodes,std::set<MDNode * > & NodesToKeep)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>
eraseMetadataIfOutsideChunk(T & MDUser,const std::set<MDNode * > & NodesToKeep)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.
extractMetadataFromModule(const std::vector<Chunk> & ChunksToKeep,Module * Program)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>
addMetadataToSet(T & MDUser,std::set<MDNode * > & UnnamedNodes)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
countMetadataTargets(Module * Program)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
reduceMetadataDeltaPass(TestRunner & Test)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