|
121
|
1 //===- ValueEnumerator.cpp - Number values and types for bitcode writer ---===//
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
3 // The LLVM Compiler Infrastructure
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
4 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5 // This file is distributed under the University of Illinois Open Source
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
6 // License. See LICENSE.TXT for details.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
7 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
8 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
9 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
10 // This file implements the ValueEnumerator class.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
11 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
12 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
13
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
14 #include "ValueEnumerator.h"
|
|
121
|
15 #include "llvm/ADT/DenseMap.h"
|
|
|
16 #include "llvm/ADT/SmallVector.h"
|
|
|
17 #include "llvm/IR/Argument.h"
|
|
|
18 #include "llvm/IR/Attributes.h"
|
|
|
19 #include "llvm/IR/BasicBlock.h"
|
|
|
20 #include "llvm/IR/Constant.h"
|
|
83
|
21 #include "llvm/IR/DebugInfoMetadata.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
22 #include "llvm/IR/DerivedTypes.h"
|
|
121
|
23 #include "llvm/IR/Function.h"
|
|
|
24 #include "llvm/IR/GlobalAlias.h"
|
|
|
25 #include "llvm/IR/GlobalIFunc.h"
|
|
|
26 #include "llvm/IR/GlobalObject.h"
|
|
|
27 #include "llvm/IR/GlobalValue.h"
|
|
|
28 #include "llvm/IR/GlobalVariable.h"
|
|
|
29 #include "llvm/IR/Instruction.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
30 #include "llvm/IR/Instructions.h"
|
|
121
|
31 #include "llvm/IR/Metadata.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
32 #include "llvm/IR/Module.h"
|
|
121
|
33 #include "llvm/IR/Type.h"
|
|
|
34 #include "llvm/IR/Use.h"
|
|
77
|
35 #include "llvm/IR/UseListOrder.h"
|
|
121
|
36 #include "llvm/IR/User.h"
|
|
|
37 #include "llvm/IR/Value.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
38 #include "llvm/IR/ValueSymbolTable.h"
|
|
121
|
39 #include "llvm/Support/Casting.h"
|
|
|
40 #include "llvm/Support/Compiler.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
41 #include "llvm/Support/Debug.h"
|
|
121
|
42 #include "llvm/Support/MathExtras.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
43 #include "llvm/Support/raw_ostream.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
44 #include <algorithm>
|
|
121
|
45 #include <cassert>
|
|
|
46 #include <cstddef>
|
|
|
47 #include <iterator>
|
|
|
48 #include <tuple>
|
|
|
49 #include <utility>
|
|
|
50 #include <vector>
|
|
|
51
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
52 using namespace llvm;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
53
|
|
77
|
54 namespace {
|
|
121
|
55
|
|
77
|
56 struct OrderMap {
|
|
|
57 DenseMap<const Value *, std::pair<unsigned, bool>> IDs;
|
|
121
|
58 unsigned LastGlobalConstantID = 0;
|
|
|
59 unsigned LastGlobalValueID = 0;
|
|
77
|
60
|
|
121
|
61 OrderMap() = default;
|
|
77
|
62
|
|
|
63 bool isGlobalConstant(unsigned ID) const {
|
|
|
64 return ID <= LastGlobalConstantID;
|
|
|
65 }
|
|
121
|
66
|
|
77
|
67 bool isGlobalValue(unsigned ID) const {
|
|
|
68 return ID <= LastGlobalValueID && !isGlobalConstant(ID);
|
|
|
69 }
|
|
|
70
|
|
|
71 unsigned size() const { return IDs.size(); }
|
|
|
72 std::pair<unsigned, bool> &operator[](const Value *V) { return IDs[V]; }
|
|
121
|
73
|
|
77
|
74 std::pair<unsigned, bool> lookup(const Value *V) const {
|
|
|
75 return IDs.lookup(V);
|
|
|
76 }
|
|
121
|
77
|
|
77
|
78 void index(const Value *V) {
|
|
|
79 // Explicitly sequence get-size and insert-value operations to avoid UB.
|
|
|
80 unsigned ID = IDs.size() + 1;
|
|
|
81 IDs[V].first = ID;
|
|
|
82 }
|
|
|
83 };
|
|
121
|
84
|
|
|
85 } // end anonymous namespace
|
|
77
|
86
|
|
|
87 static void orderValue(const Value *V, OrderMap &OM) {
|
|
|
88 if (OM.lookup(V).first)
|
|
|
89 return;
|
|
|
90
|
|
|
91 if (const Constant *C = dyn_cast<Constant>(V))
|
|
|
92 if (C->getNumOperands() && !isa<GlobalValue>(C))
|
|
|
93 for (const Value *Op : C->operands())
|
|
|
94 if (!isa<BasicBlock>(Op) && !isa<GlobalValue>(Op))
|
|
|
95 orderValue(Op, OM);
|
|
|
96
|
|
|
97 // Note: we cannot cache this lookup above, since inserting into the map
|
|
|
98 // changes the map's size, and thus affects the other IDs.
|
|
|
99 OM.index(V);
|
|
|
100 }
|
|
|
101
|
|
83
|
102 static OrderMap orderModule(const Module &M) {
|
|
77
|
103 // This needs to match the order used by ValueEnumerator::ValueEnumerator()
|
|
|
104 // and ValueEnumerator::incorporateFunction().
|
|
|
105 OrderMap OM;
|
|
|
106
|
|
|
107 // In the reader, initializers of GlobalValues are set *after* all the
|
|
|
108 // globals have been read. Rather than awkwardly modeling this behaviour
|
|
|
109 // directly in predictValueUseListOrderImpl(), just assign IDs to
|
|
|
110 // initializers of GlobalValues before GlobalValues themselves to model this
|
|
|
111 // implicitly.
|
|
83
|
112 for (const GlobalVariable &G : M.globals())
|
|
77
|
113 if (G.hasInitializer())
|
|
|
114 if (!isa<GlobalValue>(G.getInitializer()))
|
|
|
115 orderValue(G.getInitializer(), OM);
|
|
83
|
116 for (const GlobalAlias &A : M.aliases())
|
|
77
|
117 if (!isa<GlobalValue>(A.getAliasee()))
|
|
|
118 orderValue(A.getAliasee(), OM);
|
|
120
|
119 for (const GlobalIFunc &I : M.ifuncs())
|
|
|
120 if (!isa<GlobalValue>(I.getResolver()))
|
|
|
121 orderValue(I.getResolver(), OM);
|
|
83
|
122 for (const Function &F : M) {
|
|
100
|
123 for (const Use &U : F.operands())
|
|
|
124 if (!isa<GlobalValue>(U.get()))
|
|
|
125 orderValue(U.get(), OM);
|
|
83
|
126 }
|
|
77
|
127 OM.LastGlobalConstantID = OM.size();
|
|
|
128
|
|
|
129 // Initializers of GlobalValues are processed in
|
|
|
130 // BitcodeReader::ResolveGlobalAndAliasInits(). Match the order there rather
|
|
|
131 // than ValueEnumerator, and match the code in predictValueUseListOrderImpl()
|
|
|
132 // by giving IDs in reverse order.
|
|
|
133 //
|
|
|
134 // Since GlobalValues never reference each other directly (just through
|
|
|
135 // initializers), their relative IDs only matter for determining order of
|
|
|
136 // uses in their initializers.
|
|
83
|
137 for (const Function &F : M)
|
|
77
|
138 orderValue(&F, OM);
|
|
83
|
139 for (const GlobalAlias &A : M.aliases())
|
|
77
|
140 orderValue(&A, OM);
|
|
120
|
141 for (const GlobalIFunc &I : M.ifuncs())
|
|
|
142 orderValue(&I, OM);
|
|
83
|
143 for (const GlobalVariable &G : M.globals())
|
|
77
|
144 orderValue(&G, OM);
|
|
|
145 OM.LastGlobalValueID = OM.size();
|
|
|
146
|
|
83
|
147 for (const Function &F : M) {
|
|
77
|
148 if (F.isDeclaration())
|
|
|
149 continue;
|
|
|
150 // Here we need to match the union of ValueEnumerator::incorporateFunction()
|
|
|
151 // and WriteFunction(). Basic blocks are implicitly declared before
|
|
|
152 // anything else (by declaring their size).
|
|
|
153 for (const BasicBlock &BB : F)
|
|
|
154 orderValue(&BB, OM);
|
|
|
155 for (const Argument &A : F.args())
|
|
|
156 orderValue(&A, OM);
|
|
|
157 for (const BasicBlock &BB : F)
|
|
|
158 for (const Instruction &I : BB)
|
|
|
159 for (const Value *Op : I.operands())
|
|
|
160 if ((isa<Constant>(*Op) && !isa<GlobalValue>(*Op)) ||
|
|
|
161 isa<InlineAsm>(*Op))
|
|
|
162 orderValue(Op, OM);
|
|
|
163 for (const BasicBlock &BB : F)
|
|
|
164 for (const Instruction &I : BB)
|
|
|
165 orderValue(&I, OM);
|
|
|
166 }
|
|
|
167 return OM;
|
|
|
168 }
|
|
|
169
|
|
|
170 static void predictValueUseListOrderImpl(const Value *V, const Function *F,
|
|
|
171 unsigned ID, const OrderMap &OM,
|
|
|
172 UseListOrderStack &Stack) {
|
|
|
173 // Predict use-list order for this one.
|
|
121
|
174 using Entry = std::pair<const Use *, unsigned>;
|
|
77
|
175 SmallVector<Entry, 64> List;
|
|
|
176 for (const Use &U : V->uses())
|
|
|
177 // Check if this user will be serialized.
|
|
|
178 if (OM.lookup(U.getUser()).first)
|
|
|
179 List.push_back(std::make_pair(&U, List.size()));
|
|
|
180
|
|
|
181 if (List.size() < 2)
|
|
|
182 // We may have lost some users.
|
|
|
183 return;
|
|
|
184
|
|
|
185 bool IsGlobalValue = OM.isGlobalValue(ID);
|
|
|
186 std::sort(List.begin(), List.end(), [&](const Entry &L, const Entry &R) {
|
|
|
187 const Use *LU = L.first;
|
|
|
188 const Use *RU = R.first;
|
|
|
189 if (LU == RU)
|
|
|
190 return false;
|
|
|
191
|
|
|
192 auto LID = OM.lookup(LU->getUser()).first;
|
|
|
193 auto RID = OM.lookup(RU->getUser()).first;
|
|
|
194
|
|
|
195 // Global values are processed in reverse order.
|
|
|
196 //
|
|
|
197 // Moreover, initializers of GlobalValues are set *after* all the globals
|
|
|
198 // have been read (despite having earlier IDs). Rather than awkwardly
|
|
|
199 // modeling this behaviour here, orderModule() has assigned IDs to
|
|
|
200 // initializers of GlobalValues before GlobalValues themselves.
|
|
|
201 if (OM.isGlobalValue(LID) && OM.isGlobalValue(RID))
|
|
|
202 return LID < RID;
|
|
|
203
|
|
|
204 // If ID is 4, then expect: 7 6 5 1 2 3.
|
|
|
205 if (LID < RID) {
|
|
|
206 if (RID <= ID)
|
|
|
207 if (!IsGlobalValue) // GlobalValue uses don't get reversed.
|
|
|
208 return true;
|
|
|
209 return false;
|
|
|
210 }
|
|
|
211 if (RID < LID) {
|
|
|
212 if (LID <= ID)
|
|
|
213 if (!IsGlobalValue) // GlobalValue uses don't get reversed.
|
|
|
214 return false;
|
|
|
215 return true;
|
|
|
216 }
|
|
|
217
|
|
|
218 // LID and RID are equal, so we have different operands of the same user.
|
|
|
219 // Assume operands are added in order for all instructions.
|
|
|
220 if (LID <= ID)
|
|
|
221 if (!IsGlobalValue) // GlobalValue uses don't get reversed.
|
|
|
222 return LU->getOperandNo() < RU->getOperandNo();
|
|
|
223 return LU->getOperandNo() > RU->getOperandNo();
|
|
|
224 });
|
|
|
225
|
|
|
226 if (std::is_sorted(
|
|
|
227 List.begin(), List.end(),
|
|
|
228 [](const Entry &L, const Entry &R) { return L.second < R.second; }))
|
|
|
229 // Order is already correct.
|
|
|
230 return;
|
|
|
231
|
|
|
232 // Store the shuffle.
|
|
|
233 Stack.emplace_back(V, F, List.size());
|
|
|
234 assert(List.size() == Stack.back().Shuffle.size() && "Wrong size");
|
|
|
235 for (size_t I = 0, E = List.size(); I != E; ++I)
|
|
|
236 Stack.back().Shuffle[I] = List[I].second;
|
|
|
237 }
|
|
|
238
|
|
|
239 static void predictValueUseListOrder(const Value *V, const Function *F,
|
|
|
240 OrderMap &OM, UseListOrderStack &Stack) {
|
|
|
241 auto &IDPair = OM[V];
|
|
|
242 assert(IDPair.first && "Unmapped value");
|
|
|
243 if (IDPair.second)
|
|
|
244 // Already predicted.
|
|
|
245 return;
|
|
|
246
|
|
|
247 // Do the actual prediction.
|
|
|
248 IDPair.second = true;
|
|
|
249 if (!V->use_empty() && std::next(V->use_begin()) != V->use_end())
|
|
|
250 predictValueUseListOrderImpl(V, F, IDPair.first, OM, Stack);
|
|
|
251
|
|
|
252 // Recursive descent into constants.
|
|
|
253 if (const Constant *C = dyn_cast<Constant>(V))
|
|
|
254 if (C->getNumOperands()) // Visit GlobalValues.
|
|
|
255 for (const Value *Op : C->operands())
|
|
|
256 if (isa<Constant>(Op)) // Visit GlobalValues.
|
|
|
257 predictValueUseListOrder(Op, F, OM, Stack);
|
|
|
258 }
|
|
|
259
|
|
83
|
260 static UseListOrderStack predictUseListOrder(const Module &M) {
|
|
77
|
261 OrderMap OM = orderModule(M);
|
|
|
262
|
|
|
263 // Use-list orders need to be serialized after all the users have been added
|
|
|
264 // to a value, or else the shuffles will be incomplete. Store them per
|
|
|
265 // function in a stack.
|
|
|
266 //
|
|
|
267 // Aside from function order, the order of values doesn't matter much here.
|
|
|
268 UseListOrderStack Stack;
|
|
|
269
|
|
|
270 // We want to visit the functions backward now so we can list function-local
|
|
|
271 // constants in the last Function they're used in. Module-level constants
|
|
|
272 // have already been visited above.
|
|
83
|
273 for (auto I = M.rbegin(), E = M.rend(); I != E; ++I) {
|
|
77
|
274 const Function &F = *I;
|
|
|
275 if (F.isDeclaration())
|
|
|
276 continue;
|
|
|
277 for (const BasicBlock &BB : F)
|
|
|
278 predictValueUseListOrder(&BB, &F, OM, Stack);
|
|
|
279 for (const Argument &A : F.args())
|
|
|
280 predictValueUseListOrder(&A, &F, OM, Stack);
|
|
|
281 for (const BasicBlock &BB : F)
|
|
|
282 for (const Instruction &I : BB)
|
|
|
283 for (const Value *Op : I.operands())
|
|
|
284 if (isa<Constant>(*Op) || isa<InlineAsm>(*Op)) // Visit GlobalValues.
|
|
|
285 predictValueUseListOrder(Op, &F, OM, Stack);
|
|
|
286 for (const BasicBlock &BB : F)
|
|
|
287 for (const Instruction &I : BB)
|
|
|
288 predictValueUseListOrder(&I, &F, OM, Stack);
|
|
|
289 }
|
|
|
290
|
|
|
291 // Visit globals last, since the module-level use-list block will be seen
|
|
|
292 // before the function bodies are processed.
|
|
83
|
293 for (const GlobalVariable &G : M.globals())
|
|
77
|
294 predictValueUseListOrder(&G, nullptr, OM, Stack);
|
|
83
|
295 for (const Function &F : M)
|
|
77
|
296 predictValueUseListOrder(&F, nullptr, OM, Stack);
|
|
83
|
297 for (const GlobalAlias &A : M.aliases())
|
|
77
|
298 predictValueUseListOrder(&A, nullptr, OM, Stack);
|
|
120
|
299 for (const GlobalIFunc &I : M.ifuncs())
|
|
|
300 predictValueUseListOrder(&I, nullptr, OM, Stack);
|
|
83
|
301 for (const GlobalVariable &G : M.globals())
|
|
77
|
302 if (G.hasInitializer())
|
|
|
303 predictValueUseListOrder(G.getInitializer(), nullptr, OM, Stack);
|
|
83
|
304 for (const GlobalAlias &A : M.aliases())
|
|
77
|
305 predictValueUseListOrder(A.getAliasee(), nullptr, OM, Stack);
|
|
120
|
306 for (const GlobalIFunc &I : M.ifuncs())
|
|
|
307 predictValueUseListOrder(I.getResolver(), nullptr, OM, Stack);
|
|
83
|
308 for (const Function &F : M) {
|
|
100
|
309 for (const Use &U : F.operands())
|
|
|
310 predictValueUseListOrder(U.get(), nullptr, OM, Stack);
|
|
83
|
311 }
|
|
77
|
312
|
|
|
313 return Stack;
|
|
|
314 }
|
|
|
315
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
316 static bool isIntOrIntVectorValue(const std::pair<const Value*, unsigned> &V) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
317 return V.first->getType()->isIntOrIntVectorTy();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
318 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
319
|
|
95
|
320 ValueEnumerator::ValueEnumerator(const Module &M,
|
|
|
321 bool ShouldPreserveUseListOrder)
|
|
120
|
322 : ShouldPreserveUseListOrder(ShouldPreserveUseListOrder) {
|
|
95
|
323 if (ShouldPreserveUseListOrder)
|
|
77
|
324 UseListOrders = predictUseListOrder(M);
|
|
|
325
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
326 // Enumerate the global variables.
|
|
95
|
327 for (const GlobalVariable &GV : M.globals())
|
|
|
328 EnumerateValue(&GV);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
329
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
330 // Enumerate the functions.
|
|
95
|
331 for (const Function & F : M) {
|
|
|
332 EnumerateValue(&F);
|
|
|
333 EnumerateAttributes(F.getAttributes());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
334 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
335
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
336 // Enumerate the aliases.
|
|
95
|
337 for (const GlobalAlias &GA : M.aliases())
|
|
|
338 EnumerateValue(&GA);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
339
|
|
120
|
340 // Enumerate the ifuncs.
|
|
|
341 for (const GlobalIFunc &GIF : M.ifuncs())
|
|
|
342 EnumerateValue(&GIF);
|
|
|
343
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
344 // Remember what is the cutoff between globalvalue's and other constants.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
345 unsigned FirstConstant = Values.size();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
346
|
|
121
|
347 // Enumerate the global variable initializers and attributes.
|
|
|
348 for (const GlobalVariable &GV : M.globals()) {
|
|
95
|
349 if (GV.hasInitializer())
|
|
|
350 EnumerateValue(GV.getInitializer());
|
|
121
|
351 if (GV.hasAttributes())
|
|
|
352 EnumerateAttributes(GV.getAttributesAsList(AttributeList::FunctionIndex));
|
|
|
353 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
354
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
355 // Enumerate the aliasees.
|
|
95
|
356 for (const GlobalAlias &GA : M.aliases())
|
|
|
357 EnumerateValue(GA.getAliasee());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
358
|
|
120
|
359 // Enumerate the ifunc resolvers.
|
|
|
360 for (const GlobalIFunc &GIF : M.ifuncs())
|
|
|
361 EnumerateValue(GIF.getResolver());
|
|
|
362
|
|
100
|
363 // Enumerate any optional Function data.
|
|
95
|
364 for (const Function &F : M)
|
|
100
|
365 for (const Use &U : F.operands())
|
|
|
366 EnumerateValue(U.get());
|
|
83
|
367
|
|
|
368 // Enumerate the metadata type.
|
|
|
369 //
|
|
|
370 // TODO: Move this to ValueEnumerator::EnumerateOperandType() once bitcode
|
|
|
371 // only encodes the metadata type when it's used as a value.
|
|
|
372 EnumerateType(Type::getMetadataTy(M.getContext()));
|
|
|
373
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
374 // Insert constants and metadata that are named at module level into the slot
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
375 // pool so that the module symbol table can refer to them...
|
|
83
|
376 EnumerateValueSymbolTable(M.getValueSymbolTable());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
377 EnumerateNamedMetadata(M);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
378
|
|
83
|
379 SmallVector<std::pair<unsigned, MDNode *>, 8> MDs;
|
|
120
|
380 for (const GlobalVariable &GV : M.globals()) {
|
|
|
381 MDs.clear();
|
|
|
382 GV.getAllMetadata(MDs);
|
|
|
383 for (const auto &I : MDs)
|
|
|
384 // FIXME: Pass GV to EnumerateMetadata and arrange for the bitcode writer
|
|
|
385 // to write metadata to the global variable's own metadata block
|
|
|
386 // (PR28134).
|
|
|
387 EnumerateMetadata(nullptr, I.second);
|
|
|
388 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
389
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
390 // Enumerate types used by function bodies and argument lists.
|
|
83
|
391 for (const Function &F : M) {
|
|
77
|
392 for (const Argument &A : F.args())
|
|
|
393 EnumerateType(A.getType());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
394
|
|
95
|
395 // Enumerate metadata attached to this function.
|
|
120
|
396 MDs.clear();
|
|
95
|
397 F.getAllMetadata(MDs);
|
|
|
398 for (const auto &I : MDs)
|
|
120
|
399 EnumerateMetadata(F.isDeclaration() ? nullptr : &F, I.second);
|
|
95
|
400
|
|
77
|
401 for (const BasicBlock &BB : F)
|
|
|
402 for (const Instruction &I : BB) {
|
|
|
403 for (const Use &Op : I.operands()) {
|
|
83
|
404 auto *MD = dyn_cast<MetadataAsValue>(&Op);
|
|
|
405 if (!MD) {
|
|
|
406 EnumerateOperandType(Op);
|
|
|
407 continue;
|
|
|
408 }
|
|
|
409
|
|
|
410 // Local metadata is enumerated during function-incorporation.
|
|
|
411 if (isa<LocalAsMetadata>(MD->getMetadata()))
|
|
|
412 continue;
|
|
|
413
|
|
120
|
414 EnumerateMetadata(&F, MD->getMetadata());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
415 }
|
|
77
|
416 EnumerateType(I.getType());
|
|
|
417 if (const CallInst *CI = dyn_cast<CallInst>(&I))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
418 EnumerateAttributes(CI->getAttributes());
|
|
77
|
419 else if (const InvokeInst *II = dyn_cast<InvokeInst>(&I))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
420 EnumerateAttributes(II->getAttributes());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
421
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
422 // Enumerate metadata attached with this instruction.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
423 MDs.clear();
|
|
77
|
424 I.getAllMetadataOtherThanDebugLoc(MDs);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
425 for (unsigned i = 0, e = MDs.size(); i != e; ++i)
|
|
120
|
426 EnumerateMetadata(&F, MDs[i].second);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
427
|
|
95
|
428 // Don't enumerate the location directly -- it has a special record
|
|
|
429 // type -- but enumerate its operands.
|
|
|
430 if (DILocation *L = I.getDebugLoc())
|
|
120
|
431 for (const Metadata *Op : L->operands())
|
|
|
432 EnumerateMetadata(&F, Op);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
433 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
434 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
435
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
436 // Optimize constant ordering.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
437 OptimizeConstants(FirstConstant, Values.size());
|
|
120
|
438
|
|
|
439 // Organize metadata ordering.
|
|
|
440 organizeMetadata();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
441 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
442
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
443 unsigned ValueEnumerator::getInstructionID(const Instruction *Inst) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
444 InstructionMapType::const_iterator I = InstructionMap.find(Inst);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
445 assert(I != InstructionMap.end() && "Instruction is not mapped!");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
446 return I->second;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
447 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
448
|
|
77
|
449 unsigned ValueEnumerator::getComdatID(const Comdat *C) const {
|
|
|
450 unsigned ComdatID = Comdats.idFor(C);
|
|
|
451 assert(ComdatID && "Comdat not found!");
|
|
|
452 return ComdatID;
|
|
|
453 }
|
|
|
454
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
455 void ValueEnumerator::setInstructionID(const Instruction *I) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
456 InstructionMap[I] = InstructionCount++;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
457 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
458
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
459 unsigned ValueEnumerator::getValueID(const Value *V) const {
|
|
83
|
460 if (auto *MD = dyn_cast<MetadataAsValue>(V))
|
|
|
461 return getMetadataID(MD->getMetadata());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
462
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
463 ValueMapType::const_iterator I = ValueMap.find(V);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
464 assert(I != ValueMap.end() && "Value not in slotcalculator!");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
465 return I->second-1;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
466 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
467
|
|
121
|
468 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
|
|
120
|
469 LLVM_DUMP_METHOD void ValueEnumerator::dump() const {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
470 print(dbgs(), ValueMap, "Default");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
471 dbgs() << '\n';
|
|
100
|
472 print(dbgs(), MetadataMap, "MetaData");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
473 dbgs() << '\n';
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
474 }
|
|
121
|
475 #endif
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
476
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
477 void ValueEnumerator::print(raw_ostream &OS, const ValueMapType &Map,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
478 const char *Name) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
479 OS << "Map Name: " << Name << "\n";
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
480 OS << "Size: " << Map.size() << "\n";
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
481 for (ValueMapType::const_iterator I = Map.begin(),
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
482 E = Map.end(); I != E; ++I) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
483 const Value *V = I->first;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
484 if (V->hasName())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
485 OS << "Value: " << V->getName();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
486 else
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
487 OS << "Value: [null]\n";
|
|
121
|
488 V->print(errs());
|
|
|
489 errs() << '\n';
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
490
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
491 OS << " Uses(" << std::distance(V->use_begin(),V->use_end()) << "):";
|
|
77
|
492 for (const Use &U : V->uses()) {
|
|
|
493 if (&U != &*V->use_begin())
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
494 OS << ",";
|
|
77
|
495 if(U->hasName())
|
|
|
496 OS << " " << U->getName();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
497 else
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
498 OS << " [null]";
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
499
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
500 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
501 OS << "\n\n";
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
502 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
503 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
504
|
|
83
|
505 void ValueEnumerator::print(raw_ostream &OS, const MetadataMapType &Map,
|
|
|
506 const char *Name) const {
|
|
|
507 OS << "Map Name: " << Name << "\n";
|
|
|
508 OS << "Size: " << Map.size() << "\n";
|
|
|
509 for (auto I = Map.begin(), E = Map.end(); I != E; ++I) {
|
|
|
510 const Metadata *MD = I->first;
|
|
120
|
511 OS << "Metadata: slot = " << I->second.ID << "\n";
|
|
|
512 OS << "Metadata: function = " << I->second.F << "\n";
|
|
83
|
513 MD->print(OS);
|
|
120
|
514 OS << "\n";
|
|
83
|
515 }
|
|
|
516 }
|
|
|
517
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
518 /// OptimizeConstants - Reorder constant pool for denser encoding.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
519 void ValueEnumerator::OptimizeConstants(unsigned CstStart, unsigned CstEnd) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
520 if (CstStart == CstEnd || CstStart+1 == CstEnd) return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
521
|
|
95
|
522 if (ShouldPreserveUseListOrder)
|
|
77
|
523 // Optimizing constants makes the use-list order difficult to predict.
|
|
|
524 // Disable it for now when trying to preserve the order.
|
|
|
525 return;
|
|
|
526
|
|
|
527 std::stable_sort(Values.begin() + CstStart, Values.begin() + CstEnd,
|
|
|
528 [this](const std::pair<const Value *, unsigned> &LHS,
|
|
|
529 const std::pair<const Value *, unsigned> &RHS) {
|
|
|
530 // Sort by plane.
|
|
|
531 if (LHS.first->getType() != RHS.first->getType())
|
|
|
532 return getTypeID(LHS.first->getType()) < getTypeID(RHS.first->getType());
|
|
|
533 // Then by frequency.
|
|
|
534 return LHS.second > RHS.second;
|
|
|
535 });
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
536
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
537 // Ensure that integer and vector of integer constants are at the start of the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
538 // constant pool. This is important so that GEP structure indices come before
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
539 // gep constant exprs.
|
|
120
|
540 std::stable_partition(Values.begin() + CstStart, Values.begin() + CstEnd,
|
|
|
541 isIntOrIntVectorValue);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
542
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
543 // Rebuild the modified portion of ValueMap.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
544 for (; CstStart != CstEnd; ++CstStart)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
545 ValueMap[Values[CstStart].first] = CstStart+1;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
546 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
547
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
548 /// EnumerateValueSymbolTable - Insert all of the values in the specified symbol
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
549 /// table into the values table.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
550 void ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
551 for (ValueSymbolTable::const_iterator VI = VST.begin(), VE = VST.end();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
552 VI != VE; ++VI)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
553 EnumerateValue(VI->getValue());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
554 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
555
|
|
83
|
556 /// Insert all of the values referenced by named metadata in the specified
|
|
|
557 /// module.
|
|
|
558 void ValueEnumerator::EnumerateNamedMetadata(const Module &M) {
|
|
95
|
559 for (const auto &I : M.named_metadata())
|
|
|
560 EnumerateNamedMDNode(&I);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
561 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
562
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
563 void ValueEnumerator::EnumerateNamedMDNode(const NamedMDNode *MD) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
564 for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i)
|
|
120
|
565 EnumerateMetadata(nullptr, MD->getOperand(i));
|
|
|
566 }
|
|
|
567
|
|
|
568 unsigned ValueEnumerator::getMetadataFunctionID(const Function *F) const {
|
|
|
569 return F ? getValueID(F) + 1 : 0;
|
|
|
570 }
|
|
|
571
|
|
|
572 void ValueEnumerator::EnumerateMetadata(const Function *F, const Metadata *MD) {
|
|
|
573 EnumerateMetadata(getMetadataFunctionID(F), MD);
|
|
|
574 }
|
|
|
575
|
|
|
576 void ValueEnumerator::EnumerateFunctionLocalMetadata(
|
|
|
577 const Function &F, const LocalAsMetadata *Local) {
|
|
|
578 EnumerateFunctionLocalMetadata(getMetadataFunctionID(&F), Local);
|
|
|
579 }
|
|
|
580
|
|
|
581 void ValueEnumerator::dropFunctionFromMetadata(
|
|
|
582 MetadataMapType::value_type &FirstMD) {
|
|
|
583 SmallVector<const MDNode *, 64> Worklist;
|
|
121
|
584 auto push = [&Worklist](MetadataMapType::value_type &MD) {
|
|
120
|
585 auto &Entry = MD.second;
|
|
|
586
|
|
|
587 // Nothing to do if this metadata isn't tagged.
|
|
|
588 if (!Entry.F)
|
|
|
589 return;
|
|
|
590
|
|
|
591 // Drop the function tag.
|
|
|
592 Entry.F = 0;
|
|
|
593
|
|
|
594 // If this is has an ID and is an MDNode, then its operands have entries as
|
|
|
595 // well. We need to drop the function from them too.
|
|
|
596 if (Entry.ID)
|
|
|
597 if (auto *N = dyn_cast<MDNode>(MD.first))
|
|
|
598 Worklist.push_back(N);
|
|
|
599 };
|
|
|
600 push(FirstMD);
|
|
|
601 while (!Worklist.empty())
|
|
|
602 for (const Metadata *Op : Worklist.pop_back_val()->operands()) {
|
|
|
603 if (!Op)
|
|
|
604 continue;
|
|
|
605 auto MD = MetadataMap.find(Op);
|
|
|
606 if (MD != MetadataMap.end())
|
|
|
607 push(*MD);
|
|
|
608 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
609 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
610
|
|
120
|
611 void ValueEnumerator::EnumerateMetadata(unsigned F, const Metadata *MD) {
|
|
|
612 // It's vital for reader efficiency that uniqued subgraphs are done in
|
|
|
613 // post-order; it's expensive when their operands have forward references.
|
|
|
614 // If a distinct node is referenced from a uniqued node, it'll be delayed
|
|
|
615 // until the uniqued subgraph has been completely traversed.
|
|
|
616 SmallVector<const MDNode *, 32> DelayedDistinctNodes;
|
|
|
617
|
|
|
618 // Start by enumerating MD, and then work through its transitive operands in
|
|
|
619 // post-order. This requires a depth-first search.
|
|
|
620 SmallVector<std::pair<const MDNode *, MDNode::op_iterator>, 32> Worklist;
|
|
|
621 if (const MDNode *N = enumerateMetadataImpl(F, MD))
|
|
|
622 Worklist.push_back(std::make_pair(N, N->op_begin()));
|
|
|
623
|
|
|
624 while (!Worklist.empty()) {
|
|
|
625 const MDNode *N = Worklist.back().first;
|
|
|
626
|
|
|
627 // Enumerate operands until we hit a new node. We need to traverse these
|
|
|
628 // nodes' operands before visiting the rest of N's operands.
|
|
|
629 MDNode::op_iterator I = std::find_if(
|
|
|
630 Worklist.back().second, N->op_end(),
|
|
|
631 [&](const Metadata *MD) { return enumerateMetadataImpl(F, MD); });
|
|
|
632 if (I != N->op_end()) {
|
|
|
633 auto *Op = cast<MDNode>(*I);
|
|
|
634 Worklist.back().second = ++I;
|
|
|
635
|
|
|
636 // Delay traversing Op if it's a distinct node and N is uniqued.
|
|
|
637 if (Op->isDistinct() && !N->isDistinct())
|
|
|
638 DelayedDistinctNodes.push_back(Op);
|
|
|
639 else
|
|
|
640 Worklist.push_back(std::make_pair(Op, Op->op_begin()));
|
|
83
|
641 continue;
|
|
120
|
642 }
|
|
|
643
|
|
|
644 // All the operands have been visited. Now assign an ID.
|
|
|
645 Worklist.pop_back();
|
|
|
646 MDs.push_back(N);
|
|
|
647 MetadataMap[N].ID = MDs.size();
|
|
|
648
|
|
|
649 // Flush out any delayed distinct nodes; these are all the distinct nodes
|
|
|
650 // that are leaves in last uniqued subgraph.
|
|
|
651 if (Worklist.empty() || Worklist.back().first->isDistinct()) {
|
|
|
652 for (const MDNode *N : DelayedDistinctNodes)
|
|
|
653 Worklist.push_back(std::make_pair(N, N->op_begin()));
|
|
|
654 DelayedDistinctNodes.clear();
|
|
|
655 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
656 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
657 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
658
|
|
120
|
659 const MDNode *ValueEnumerator::enumerateMetadataImpl(unsigned F, const Metadata *MD) {
|
|
|
660 if (!MD)
|
|
|
661 return nullptr;
|
|
|
662
|
|
83
|
663 assert(
|
|
|
664 (isa<MDNode>(MD) || isa<MDString>(MD) || isa<ConstantAsMetadata>(MD)) &&
|
|
|
665 "Invalid metadata kind");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
666
|
|
120
|
667 auto Insertion = MetadataMap.insert(std::make_pair(MD, MDIndex(F)));
|
|
|
668 MDIndex &Entry = Insertion.first->second;
|
|
|
669 if (!Insertion.second) {
|
|
|
670 // Already mapped. If F doesn't match the function tag, drop it.
|
|
|
671 if (Entry.hasDifferentFunction(F))
|
|
|
672 dropFunctionFromMetadata(*Insertion.first);
|
|
|
673 return nullptr;
|
|
|
674 }
|
|
83
|
675
|
|
120
|
676 // Don't assign IDs to metadata nodes.
|
|
83
|
677 if (auto *N = dyn_cast<MDNode>(MD))
|
|
120
|
678 return N;
|
|
|
679
|
|
|
680 // Save the metadata.
|
|
|
681 MDs.push_back(MD);
|
|
|
682 Entry.ID = MDs.size();
|
|
|
683
|
|
|
684 // Enumerate the constant, if any.
|
|
|
685 if (auto *C = dyn_cast<ConstantAsMetadata>(MD))
|
|
83
|
686 EnumerateValue(C->getValue());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
687
|
|
120
|
688 return nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
689 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
690
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
691 /// EnumerateFunctionLocalMetadataa - Incorporate function-local metadata
|
|
83
|
692 /// information reachable from the metadata.
|
|
|
693 void ValueEnumerator::EnumerateFunctionLocalMetadata(
|
|
120
|
694 unsigned F, const LocalAsMetadata *Local) {
|
|
|
695 assert(F && "Expected a function");
|
|
|
696
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
697 // Check to see if it's already in!
|
|
120
|
698 MDIndex &Index = MetadataMap[Local];
|
|
|
699 if (Index.ID) {
|
|
|
700 assert(Index.F == F && "Expected the same function");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
701 return;
|
|
120
|
702 }
|
|
83
|
703
|
|
|
704 MDs.push_back(Local);
|
|
120
|
705 Index.F = F;
|
|
|
706 Index.ID = MDs.size();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
707
|
|
83
|
708 EnumerateValue(Local->getValue());
|
|
120
|
709 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
710
|
|
120
|
711 static unsigned getMetadataTypeOrder(const Metadata *MD) {
|
|
|
712 // Strings are emitted in bulk and must come first.
|
|
|
713 if (isa<MDString>(MD))
|
|
|
714 return 0;
|
|
|
715
|
|
|
716 // ConstantAsMetadata doesn't reference anything. We may as well shuffle it
|
|
|
717 // to the front since we can detect it.
|
|
|
718 auto *N = dyn_cast<MDNode>(MD);
|
|
|
719 if (!N)
|
|
|
720 return 1;
|
|
|
721
|
|
|
722 // The reader is fast forward references for distinct node operands, but slow
|
|
|
723 // when uniqued operands are unresolved.
|
|
|
724 return N->isDistinct() ? 2 : 3;
|
|
|
725 }
|
|
|
726
|
|
|
727 void ValueEnumerator::organizeMetadata() {
|
|
|
728 assert(MetadataMap.size() == MDs.size() &&
|
|
|
729 "Metadata map and vector out of sync");
|
|
|
730
|
|
|
731 if (MDs.empty())
|
|
|
732 return;
|
|
|
733
|
|
|
734 // Copy out the index information from MetadataMap in order to choose a new
|
|
|
735 // order.
|
|
|
736 SmallVector<MDIndex, 64> Order;
|
|
|
737 Order.reserve(MetadataMap.size());
|
|
|
738 for (const Metadata *MD : MDs)
|
|
|
739 Order.push_back(MetadataMap.lookup(MD));
|
|
|
740
|
|
|
741 // Partition:
|
|
|
742 // - by function, then
|
|
|
743 // - by isa<MDString>
|
|
|
744 // and then sort by the original/current ID. Since the IDs are guaranteed to
|
|
|
745 // be unique, the result of std::sort will be deterministic. There's no need
|
|
|
746 // for std::stable_sort.
|
|
|
747 std::sort(Order.begin(), Order.end(), [this](MDIndex LHS, MDIndex RHS) {
|
|
|
748 return std::make_tuple(LHS.F, getMetadataTypeOrder(LHS.get(MDs)), LHS.ID) <
|
|
|
749 std::make_tuple(RHS.F, getMetadataTypeOrder(RHS.get(MDs)), RHS.ID);
|
|
|
750 });
|
|
|
751
|
|
|
752 // Rebuild MDs, index the metadata ranges for each function in FunctionMDs,
|
|
|
753 // and fix up MetadataMap.
|
|
|
754 std::vector<const Metadata *> OldMDs = std::move(MDs);
|
|
|
755 MDs.reserve(OldMDs.size());
|
|
|
756 for (unsigned I = 0, E = Order.size(); I != E && !Order[I].F; ++I) {
|
|
|
757 auto *MD = Order[I].get(OldMDs);
|
|
|
758 MDs.push_back(MD);
|
|
|
759 MetadataMap[MD].ID = I + 1;
|
|
|
760 if (isa<MDString>(MD))
|
|
|
761 ++NumMDStrings;
|
|
|
762 }
|
|
|
763
|
|
|
764 // Return early if there's nothing for the functions.
|
|
|
765 if (MDs.size() == Order.size())
|
|
|
766 return;
|
|
|
767
|
|
|
768 // Build the function metadata ranges.
|
|
|
769 MDRange R;
|
|
|
770 FunctionMDs.reserve(OldMDs.size());
|
|
|
771 unsigned PrevF = 0;
|
|
|
772 for (unsigned I = MDs.size(), E = Order.size(), ID = MDs.size(); I != E;
|
|
|
773 ++I) {
|
|
|
774 unsigned F = Order[I].F;
|
|
|
775 if (!PrevF) {
|
|
|
776 PrevF = F;
|
|
|
777 } else if (PrevF != F) {
|
|
|
778 R.Last = FunctionMDs.size();
|
|
|
779 std::swap(R, FunctionMDInfo[PrevF]);
|
|
|
780 R.First = FunctionMDs.size();
|
|
|
781
|
|
|
782 ID = MDs.size();
|
|
|
783 PrevF = F;
|
|
|
784 }
|
|
|
785
|
|
|
786 auto *MD = Order[I].get(OldMDs);
|
|
|
787 FunctionMDs.push_back(MD);
|
|
|
788 MetadataMap[MD].ID = ++ID;
|
|
|
789 if (isa<MDString>(MD))
|
|
|
790 ++R.NumStrings;
|
|
|
791 }
|
|
|
792 R.Last = FunctionMDs.size();
|
|
|
793 FunctionMDInfo[PrevF] = R;
|
|
|
794 }
|
|
|
795
|
|
|
796 void ValueEnumerator::incorporateFunctionMetadata(const Function &F) {
|
|
|
797 NumModuleMDs = MDs.size();
|
|
|
798
|
|
|
799 auto R = FunctionMDInfo.lookup(getValueID(&F) + 1);
|
|
|
800 NumMDStrings = R.NumStrings;
|
|
|
801 MDs.insert(MDs.end(), FunctionMDs.begin() + R.First,
|
|
|
802 FunctionMDs.begin() + R.Last);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
803 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
804
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
805 void ValueEnumerator::EnumerateValue(const Value *V) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
806 assert(!V->getType()->isVoidTy() && "Can't insert void values!");
|
|
83
|
807 assert(!isa<MetadataAsValue>(V) && "EnumerateValue doesn't handle Metadata!");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
808
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
809 // Check to see if it's already in!
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
810 unsigned &ValueID = ValueMap[V];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
811 if (ValueID) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
812 // Increment use count.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
813 Values[ValueID-1].second++;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
814 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
815 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
816
|
|
77
|
817 if (auto *GO = dyn_cast<GlobalObject>(V))
|
|
|
818 if (const Comdat *C = GO->getComdat())
|
|
|
819 Comdats.insert(C);
|
|
|
820
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
821 // Enumerate the type of this value.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
822 EnumerateType(V->getType());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
823
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
824 if (const Constant *C = dyn_cast<Constant>(V)) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
825 if (isa<GlobalValue>(C)) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
826 // Initializers for globals are handled explicitly elsewhere.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
827 } else if (C->getNumOperands()) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
828 // If a constant has operands, enumerate them. This makes sure that if a
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
829 // constant has uses (for example an array of const ints), that they are
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
830 // inserted also.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
831
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
832 // We prefer to enumerate them with values before we enumerate the user
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
833 // itself. This makes it more likely that we can avoid forward references
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
834 // in the reader. We know that there can be no cycles in the constants
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
835 // graph that don't go through a global variable.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
836 for (User::const_op_iterator I = C->op_begin(), E = C->op_end();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
837 I != E; ++I)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
838 if (!isa<BasicBlock>(*I)) // Don't enumerate BB operand to BlockAddress.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
839 EnumerateValue(*I);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
840
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
841 // Finally, add the value. Doing this could make the ValueID reference be
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
842 // dangling, don't reuse it.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
843 Values.push_back(std::make_pair(V, 1U));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
844 ValueMap[V] = Values.size();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
845 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
846 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
847 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
848
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
849 // Add the value.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
850 Values.push_back(std::make_pair(V, 1U));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
851 ValueID = Values.size();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
852 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
853
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
854
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
855 void ValueEnumerator::EnumerateType(Type *Ty) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
856 unsigned *TypeID = &TypeMap[Ty];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
857
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
858 // We've already seen this type.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
859 if (*TypeID)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
860 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
861
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
862 // If it is a non-anonymous struct, mark the type as being visited so that we
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
863 // don't recursively visit it. This is safe because we allow forward
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
864 // references of these in the bitcode reader.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
865 if (StructType *STy = dyn_cast<StructType>(Ty))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
866 if (!STy->isLiteral())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
867 *TypeID = ~0U;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
868
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
869 // Enumerate all of the subtypes before we enumerate this type. This ensures
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
870 // that the type will be enumerated in an order that can be directly built.
|
|
83
|
871 for (Type *SubTy : Ty->subtypes())
|
|
|
872 EnumerateType(SubTy);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
873
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
874 // Refresh the TypeID pointer in case the table rehashed.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
875 TypeID = &TypeMap[Ty];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
876
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
877 // Check to see if we got the pointer another way. This can happen when
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
878 // enumerating recursive types that hit the base case deeper than they start.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
879 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
880 // If this is actually a struct that we are treating as forward ref'able,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
881 // then emit the definition now that all of its contents are available.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
882 if (*TypeID && *TypeID != ~0U)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
883 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
884
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
885 // Add this type now that its contents are all happily enumerated.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
886 Types.push_back(Ty);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
887
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
888 *TypeID = Types.size();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
889 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
890
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
891 // Enumerate the types for the specified value. If the value is a constant,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
892 // walk through it, enumerating the types of the constant.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
893 void ValueEnumerator::EnumerateOperandType(const Value *V) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
894 EnumerateType(V->getType());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
895
|
|
120
|
896 assert(!isa<MetadataAsValue>(V) && "Unexpected metadata operand");
|
|
83
|
897
|
|
|
898 const Constant *C = dyn_cast<Constant>(V);
|
|
|
899 if (!C)
|
|
|
900 return;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
901
|
|
83
|
902 // If this constant is already enumerated, ignore it, we know its type must
|
|
|
903 // be enumerated.
|
|
|
904 if (ValueMap.count(C))
|
|
|
905 return;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
906
|
|
83
|
907 // This constant may have operands, make sure to enumerate the types in
|
|
|
908 // them.
|
|
95
|
909 for (const Value *Op : C->operands()) {
|
|
83
|
910 // Don't enumerate basic blocks here, this happens as operands to
|
|
|
911 // blockaddress.
|
|
|
912 if (isa<BasicBlock>(Op))
|
|
|
913 continue;
|
|
|
914
|
|
|
915 EnumerateOperandType(Op);
|
|
|
916 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
917 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
918
|
|
121
|
919 void ValueEnumerator::EnumerateAttributes(AttributeList PAL) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
920 if (PAL.isEmpty()) return; // null is always 0.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
921
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
922 // Do a lookup.
|
|
121
|
923 unsigned &Entry = AttributeListMap[PAL];
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
924 if (Entry == 0) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
925 // Never saw this before, add it.
|
|
121
|
926 AttributeLists.push_back(PAL);
|
|
|
927 Entry = AttributeLists.size();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
928 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
929
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
930 // Do lookups for all attribute groups.
|
|
121
|
931 for (unsigned i = PAL.index_begin(), e = PAL.index_end(); i != e; ++i) {
|
|
|
932 AttributeSet AS = PAL.getAttributes(i);
|
|
|
933 if (!AS.hasAttributes())
|
|
|
934 continue;
|
|
|
935 IndexAndAttrSet Pair = {i, AS};
|
|
|
936 unsigned &Entry = AttributeGroupMap[Pair];
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
937 if (Entry == 0) {
|
|
121
|
938 AttributeGroups.push_back(Pair);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
939 Entry = AttributeGroups.size();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
940 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
941 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
942 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
943
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
944 void ValueEnumerator::incorporateFunction(const Function &F) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
945 InstructionCount = 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
946 NumModuleValues = Values.size();
|
|
120
|
947
|
|
|
948 // Add global metadata to the function block. This doesn't include
|
|
|
949 // LocalAsMetadata.
|
|
|
950 incorporateFunctionMetadata(F);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
951
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
952 // Adding function arguments to the value table.
|
|
95
|
953 for (const auto &I : F.args())
|
|
|
954 EnumerateValue(&I);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
955
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
956 FirstFuncConstantID = Values.size();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
957
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
958 // Add all function-level constants to the value table.
|
|
95
|
959 for (const BasicBlock &BB : F) {
|
|
|
960 for (const Instruction &I : BB)
|
|
|
961 for (const Use &OI : I.operands()) {
|
|
|
962 if ((isa<Constant>(OI) && !isa<GlobalValue>(OI)) || isa<InlineAsm>(OI))
|
|
|
963 EnumerateValue(OI);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
964 }
|
|
95
|
965 BasicBlocks.push_back(&BB);
|
|
|
966 ValueMap[&BB] = BasicBlocks.size();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
967 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
968
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
969 // Optimize the constant layout.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
970 OptimizeConstants(FirstFuncConstantID, Values.size());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
971
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
972 // Add the function's parameter attributes so they are available for use in
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
973 // the function's instruction.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
974 EnumerateAttributes(F.getAttributes());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
975
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
976 FirstInstID = Values.size();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
977
|
|
83
|
978 SmallVector<LocalAsMetadata *, 8> FnLocalMDVector;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
979 // Add all of the instructions.
|
|
95
|
980 for (const BasicBlock &BB : F) {
|
|
|
981 for (const Instruction &I : BB) {
|
|
|
982 for (const Use &OI : I.operands()) {
|
|
|
983 if (auto *MD = dyn_cast<MetadataAsValue>(&OI))
|
|
83
|
984 if (auto *Local = dyn_cast<LocalAsMetadata>(MD->getMetadata()))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
985 // Enumerate metadata after the instructions they might refer to.
|
|
83
|
986 FnLocalMDVector.push_back(Local);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
987 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
988
|
|
95
|
989 if (!I.getType()->isVoidTy())
|
|
|
990 EnumerateValue(&I);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
991 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
992 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
993
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
994 // Add all of the function-local metadata.
|
|
120
|
995 for (unsigned i = 0, e = FnLocalMDVector.size(); i != e; ++i) {
|
|
|
996 // At this point, every local values have been incorporated, we shouldn't
|
|
|
997 // have a metadata operand that references a value that hasn't been seen.
|
|
|
998 assert(ValueMap.count(FnLocalMDVector[i]->getValue()) &&
|
|
|
999 "Missing value for metadata operand");
|
|
|
1000 EnumerateFunctionLocalMetadata(F, FnLocalMDVector[i]);
|
|
|
1001 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1002 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1003
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1004 void ValueEnumerator::purgeFunction() {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1005 /// Remove purged values from the ValueMap.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1006 for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1007 ValueMap.erase(Values[i].first);
|
|
83
|
1008 for (unsigned i = NumModuleMDs, e = MDs.size(); i != e; ++i)
|
|
100
|
1009 MetadataMap.erase(MDs[i]);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1010 for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1011 ValueMap.erase(BasicBlocks[i]);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1012
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1013 Values.resize(NumModuleValues);
|
|
83
|
1014 MDs.resize(NumModuleMDs);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1015 BasicBlocks.clear();
|
|
120
|
1016 NumMDStrings = 0;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1017 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1018
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1019 static void IncorporateFunctionInfoGlobalBBIDs(const Function *F,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1020 DenseMap<const BasicBlock*, unsigned> &IDMap) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1021 unsigned Counter = 0;
|
|
95
|
1022 for (const BasicBlock &BB : *F)
|
|
|
1023 IDMap[&BB] = ++Counter;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1024 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1025
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1026 /// getGlobalBasicBlockID - This returns the function-specific ID for the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1027 /// specified basic block. This is relatively expensive information, so it
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1028 /// should only be used by rare constructs such as address-of-label.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1029 unsigned ValueEnumerator::getGlobalBasicBlockID(const BasicBlock *BB) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1030 unsigned &Idx = GlobalBasicBlockIDs[BB];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1031 if (Idx != 0)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1032 return Idx-1;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1033
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1034 IncorporateFunctionInfoGlobalBBIDs(BB->getParent(), GlobalBasicBlockIDs);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1035 return getGlobalBasicBlockID(BB);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1036 }
|
|
95
|
1037
|
|
|
1038 uint64_t ValueEnumerator::computeBitsRequiredForTypeIndicies() const {
|
|
|
1039 return Log2_32_Ceil(getTypes().size() + 1);
|
|
|
1040 }
|
