File: | lib/Bitcode/Writer/ValueEnumerator.cpp |
Warning: | line 753, column 3 Method called on moved-from object 'MDs' of type 'std::vector' |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- ValueEnumerator.cpp - Number values and types for bitcode writer ---===// | |||
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 the ValueEnumerator class. | |||
10 | // | |||
11 | //===----------------------------------------------------------------------===// | |||
12 | ||||
13 | #include "ValueEnumerator.h" | |||
14 | #include "llvm/ADT/DenseMap.h" | |||
15 | #include "llvm/ADT/SmallVector.h" | |||
16 | #include "llvm/Config/llvm-config.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" | |||
21 | #include "llvm/IR/DebugInfoMetadata.h" | |||
22 | #include "llvm/IR/DerivedTypes.h" | |||
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" | |||
30 | #include "llvm/IR/Instructions.h" | |||
31 | #include "llvm/IR/Metadata.h" | |||
32 | #include "llvm/IR/Module.h" | |||
33 | #include "llvm/IR/Type.h" | |||
34 | #include "llvm/IR/Use.h" | |||
35 | #include "llvm/IR/UseListOrder.h" | |||
36 | #include "llvm/IR/User.h" | |||
37 | #include "llvm/IR/Value.h" | |||
38 | #include "llvm/IR/ValueSymbolTable.h" | |||
39 | #include "llvm/Support/Casting.h" | |||
40 | #include "llvm/Support/Compiler.h" | |||
41 | #include "llvm/Support/Debug.h" | |||
42 | #include "llvm/Support/MathExtras.h" | |||
43 | #include "llvm/Support/raw_ostream.h" | |||
44 | #include <algorithm> | |||
45 | #include <cassert> | |||
46 | #include <cstddef> | |||
47 | #include <iterator> | |||
48 | #include <tuple> | |||
49 | #include <utility> | |||
50 | #include <vector> | |||
51 | ||||
52 | using namespace llvm; | |||
53 | ||||
54 | namespace { | |||
55 | ||||
56 | struct OrderMap { | |||
57 | DenseMap<const Value *, std::pair<unsigned, bool>> IDs; | |||
58 | unsigned LastGlobalConstantID = 0; | |||
59 | unsigned LastGlobalValueID = 0; | |||
60 | ||||
61 | OrderMap() = default; | |||
62 | ||||
63 | bool isGlobalConstant(unsigned ID) const { | |||
64 | return ID <= LastGlobalConstantID; | |||
65 | } | |||
66 | ||||
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]; } | |||
73 | ||||
74 | std::pair<unsigned, bool> lookup(const Value *V) const { | |||
75 | return IDs.lookup(V); | |||
76 | } | |||
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 | }; | |||
84 | ||||
85 | } // end anonymous namespace | |||
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 | ||||
102 | static OrderMap orderModule(const Module &M) { | |||
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. | |||
112 | for (const GlobalVariable &G : M.globals()) | |||
113 | if (G.hasInitializer()) | |||
114 | if (!isa<GlobalValue>(G.getInitializer())) | |||
115 | orderValue(G.getInitializer(), OM); | |||
116 | for (const GlobalAlias &A : M.aliases()) | |||
117 | if (!isa<GlobalValue>(A.getAliasee())) | |||
118 | orderValue(A.getAliasee(), OM); | |||
119 | for (const GlobalIFunc &I : M.ifuncs()) | |||
120 | if (!isa<GlobalValue>(I.getResolver())) | |||
121 | orderValue(I.getResolver(), OM); | |||
122 | for (const Function &F : M) { | |||
123 | for (const Use &U : F.operands()) | |||
124 | if (!isa<GlobalValue>(U.get())) | |||
125 | orderValue(U.get(), OM); | |||
126 | } | |||
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. | |||
137 | for (const Function &F : M) | |||
138 | orderValue(&F, OM); | |||
139 | for (const GlobalAlias &A : M.aliases()) | |||
140 | orderValue(&A, OM); | |||
141 | for (const GlobalIFunc &I : M.ifuncs()) | |||
142 | orderValue(&I, OM); | |||
143 | for (const GlobalVariable &G : M.globals()) | |||
144 | orderValue(&G, OM); | |||
145 | OM.LastGlobalValueID = OM.size(); | |||
146 | ||||
147 | for (const Function &F : M) { | |||
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. | |||
174 | using Entry = std::pair<const Use *, unsigned>; | |||
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 | llvm::sort(List, [&](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")((List.size() == Stack.back().Shuffle.size() && "Wrong size" ) ? static_cast<void> (0) : __assert_fail ("List.size() == Stack.back().Shuffle.size() && \"Wrong size\"" , "/build/llvm-toolchain-snapshot-9~svn359999/lib/Bitcode/Writer/ValueEnumerator.cpp" , 234, __PRETTY_FUNCTION__)); | |||
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")((IDPair.first && "Unmapped value") ? static_cast< void> (0) : __assert_fail ("IDPair.first && \"Unmapped value\"" , "/build/llvm-toolchain-snapshot-9~svn359999/lib/Bitcode/Writer/ValueEnumerator.cpp" , 242, __PRETTY_FUNCTION__)); | |||
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 | ||||
260 | static UseListOrderStack predictUseListOrder(const Module &M) { | |||
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. | |||
273 | for (auto I = M.rbegin(), E = M.rend(); I != E; ++I) { | |||
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. | |||
293 | for (const GlobalVariable &G : M.globals()) | |||
294 | predictValueUseListOrder(&G, nullptr, OM, Stack); | |||
295 | for (const Function &F : M) | |||
296 | predictValueUseListOrder(&F, nullptr, OM, Stack); | |||
297 | for (const GlobalAlias &A : M.aliases()) | |||
298 | predictValueUseListOrder(&A, nullptr, OM, Stack); | |||
299 | for (const GlobalIFunc &I : M.ifuncs()) | |||
300 | predictValueUseListOrder(&I, nullptr, OM, Stack); | |||
301 | for (const GlobalVariable &G : M.globals()) | |||
302 | if (G.hasInitializer()) | |||
303 | predictValueUseListOrder(G.getInitializer(), nullptr, OM, Stack); | |||
304 | for (const GlobalAlias &A : M.aliases()) | |||
305 | predictValueUseListOrder(A.getAliasee(), nullptr, OM, Stack); | |||
306 | for (const GlobalIFunc &I : M.ifuncs()) | |||
307 | predictValueUseListOrder(I.getResolver(), nullptr, OM, Stack); | |||
308 | for (const Function &F : M) { | |||
309 | for (const Use &U : F.operands()) | |||
310 | predictValueUseListOrder(U.get(), nullptr, OM, Stack); | |||
311 | } | |||
312 | ||||
313 | return Stack; | |||
314 | } | |||
315 | ||||
316 | static bool isIntOrIntVectorValue(const std::pair<const Value*, unsigned> &V) { | |||
317 | return V.first->getType()->isIntOrIntVectorTy(); | |||
318 | } | |||
319 | ||||
320 | ValueEnumerator::ValueEnumerator(const Module &M, | |||
321 | bool ShouldPreserveUseListOrder) | |||
322 | : ShouldPreserveUseListOrder(ShouldPreserveUseListOrder) { | |||
323 | if (ShouldPreserveUseListOrder) | |||
| ||||
324 | UseListOrders = predictUseListOrder(M); | |||
325 | ||||
326 | // Enumerate the global variables. | |||
327 | for (const GlobalVariable &GV : M.globals()) | |||
328 | EnumerateValue(&GV); | |||
329 | ||||
330 | // Enumerate the functions. | |||
331 | for (const Function & F : M) { | |||
332 | EnumerateValue(&F); | |||
333 | EnumerateAttributes(F.getAttributes()); | |||
334 | } | |||
335 | ||||
336 | // Enumerate the aliases. | |||
337 | for (const GlobalAlias &GA : M.aliases()) | |||
338 | EnumerateValue(&GA); | |||
339 | ||||
340 | // Enumerate the ifuncs. | |||
341 | for (const GlobalIFunc &GIF : M.ifuncs()) | |||
342 | EnumerateValue(&GIF); | |||
343 | ||||
344 | // Remember what is the cutoff between globalvalue's and other constants. | |||
345 | unsigned FirstConstant = Values.size(); | |||
346 | ||||
347 | // Enumerate the global variable initializers and attributes. | |||
348 | for (const GlobalVariable &GV : M.globals()) { | |||
349 | if (GV.hasInitializer()) | |||
350 | EnumerateValue(GV.getInitializer()); | |||
351 | if (GV.hasAttributes()) | |||
352 | EnumerateAttributes(GV.getAttributesAsList(AttributeList::FunctionIndex)); | |||
353 | } | |||
354 | ||||
355 | // Enumerate the aliasees. | |||
356 | for (const GlobalAlias &GA : M.aliases()) | |||
357 | EnumerateValue(GA.getAliasee()); | |||
358 | ||||
359 | // Enumerate the ifunc resolvers. | |||
360 | for (const GlobalIFunc &GIF : M.ifuncs()) | |||
361 | EnumerateValue(GIF.getResolver()); | |||
362 | ||||
363 | // Enumerate any optional Function data. | |||
364 | for (const Function &F : M) | |||
365 | for (const Use &U : F.operands()) | |||
366 | EnumerateValue(U.get()); | |||
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 | ||||
374 | // Insert constants and metadata that are named at module level into the slot | |||
375 | // pool so that the module symbol table can refer to them... | |||
376 | EnumerateValueSymbolTable(M.getValueSymbolTable()); | |||
377 | EnumerateNamedMetadata(M); | |||
378 | ||||
379 | SmallVector<std::pair<unsigned, MDNode *>, 8> MDs; | |||
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 | } | |||
389 | ||||
390 | // Enumerate types used by function bodies and argument lists. | |||
391 | for (const Function &F : M) { | |||
392 | for (const Argument &A : F.args()) | |||
393 | EnumerateType(A.getType()); | |||
394 | ||||
395 | // Enumerate metadata attached to this function. | |||
396 | MDs.clear(); | |||
397 | F.getAllMetadata(MDs); | |||
398 | for (const auto &I : MDs) | |||
399 | EnumerateMetadata(F.isDeclaration() ? nullptr : &F, I.second); | |||
400 | ||||
401 | for (const BasicBlock &BB : F) | |||
402 | for (const Instruction &I : BB) { | |||
403 | for (const Use &Op : I.operands()) { | |||
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 | ||||
414 | EnumerateMetadata(&F, MD->getMetadata()); | |||
415 | } | |||
416 | EnumerateType(I.getType()); | |||
417 | if (const auto *Call = dyn_cast<CallBase>(&I)) | |||
418 | EnumerateAttributes(Call->getAttributes()); | |||
419 | ||||
420 | // Enumerate metadata attached with this instruction. | |||
421 | MDs.clear(); | |||
422 | I.getAllMetadataOtherThanDebugLoc(MDs); | |||
423 | for (unsigned i = 0, e = MDs.size(); i != e; ++i) | |||
424 | EnumerateMetadata(&F, MDs[i].second); | |||
425 | ||||
426 | // Don't enumerate the location directly -- it has a special record | |||
427 | // type -- but enumerate its operands. | |||
428 | if (DILocation *L = I.getDebugLoc()) | |||
429 | for (const Metadata *Op : L->operands()) | |||
430 | EnumerateMetadata(&F, Op); | |||
431 | } | |||
432 | } | |||
433 | ||||
434 | // Optimize constant ordering. | |||
435 | OptimizeConstants(FirstConstant, Values.size()); | |||
436 | ||||
437 | // Organize metadata ordering. | |||
438 | organizeMetadata(); | |||
439 | } | |||
440 | ||||
441 | unsigned ValueEnumerator::getInstructionID(const Instruction *Inst) const { | |||
442 | InstructionMapType::const_iterator I = InstructionMap.find(Inst); | |||
443 | assert(I != InstructionMap.end() && "Instruction is not mapped!")((I != InstructionMap.end() && "Instruction is not mapped!" ) ? static_cast<void> (0) : __assert_fail ("I != InstructionMap.end() && \"Instruction is not mapped!\"" , "/build/llvm-toolchain-snapshot-9~svn359999/lib/Bitcode/Writer/ValueEnumerator.cpp" , 443, __PRETTY_FUNCTION__)); | |||
444 | return I->second; | |||
445 | } | |||
446 | ||||
447 | unsigned ValueEnumerator::getComdatID(const Comdat *C) const { | |||
448 | unsigned ComdatID = Comdats.idFor(C); | |||
449 | assert(ComdatID && "Comdat not found!")((ComdatID && "Comdat not found!") ? static_cast<void > (0) : __assert_fail ("ComdatID && \"Comdat not found!\"" , "/build/llvm-toolchain-snapshot-9~svn359999/lib/Bitcode/Writer/ValueEnumerator.cpp" , 449, __PRETTY_FUNCTION__)); | |||
450 | return ComdatID; | |||
451 | } | |||
452 | ||||
453 | void ValueEnumerator::setInstructionID(const Instruction *I) { | |||
454 | InstructionMap[I] = InstructionCount++; | |||
455 | } | |||
456 | ||||
457 | unsigned ValueEnumerator::getValueID(const Value *V) const { | |||
458 | if (auto *MD = dyn_cast<MetadataAsValue>(V)) | |||
459 | return getMetadataID(MD->getMetadata()); | |||
460 | ||||
461 | ValueMapType::const_iterator I = ValueMap.find(V); | |||
462 | assert(I != ValueMap.end() && "Value not in slotcalculator!")((I != ValueMap.end() && "Value not in slotcalculator!" ) ? static_cast<void> (0) : __assert_fail ("I != ValueMap.end() && \"Value not in slotcalculator!\"" , "/build/llvm-toolchain-snapshot-9~svn359999/lib/Bitcode/Writer/ValueEnumerator.cpp" , 462, __PRETTY_FUNCTION__)); | |||
463 | return I->second-1; | |||
464 | } | |||
465 | ||||
466 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) | |||
467 | LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void ValueEnumerator::dump() const { | |||
468 | print(dbgs(), ValueMap, "Default"); | |||
469 | dbgs() << '\n'; | |||
470 | print(dbgs(), MetadataMap, "MetaData"); | |||
471 | dbgs() << '\n'; | |||
472 | } | |||
473 | #endif | |||
474 | ||||
475 | void ValueEnumerator::print(raw_ostream &OS, const ValueMapType &Map, | |||
476 | const char *Name) const { | |||
477 | OS << "Map Name: " << Name << "\n"; | |||
478 | OS << "Size: " << Map.size() << "\n"; | |||
479 | for (ValueMapType::const_iterator I = Map.begin(), | |||
480 | E = Map.end(); I != E; ++I) { | |||
481 | const Value *V = I->first; | |||
482 | if (V->hasName()) | |||
483 | OS << "Value: " << V->getName(); | |||
484 | else | |||
485 | OS << "Value: [null]\n"; | |||
486 | V->print(errs()); | |||
487 | errs() << '\n'; | |||
488 | ||||
489 | OS << " Uses(" << V->getNumUses() << "):"; | |||
490 | for (const Use &U : V->uses()) { | |||
491 | if (&U != &*V->use_begin()) | |||
492 | OS << ","; | |||
493 | if(U->hasName()) | |||
494 | OS << " " << U->getName(); | |||
495 | else | |||
496 | OS << " [null]"; | |||
497 | ||||
498 | } | |||
499 | OS << "\n\n"; | |||
500 | } | |||
501 | } | |||
502 | ||||
503 | void ValueEnumerator::print(raw_ostream &OS, const MetadataMapType &Map, | |||
504 | const char *Name) const { | |||
505 | OS << "Map Name: " << Name << "\n"; | |||
506 | OS << "Size: " << Map.size() << "\n"; | |||
507 | for (auto I = Map.begin(), E = Map.end(); I != E; ++I) { | |||
508 | const Metadata *MD = I->first; | |||
509 | OS << "Metadata: slot = " << I->second.ID << "\n"; | |||
510 | OS << "Metadata: function = " << I->second.F << "\n"; | |||
511 | MD->print(OS); | |||
512 | OS << "\n"; | |||
513 | } | |||
514 | } | |||
515 | ||||
516 | /// OptimizeConstants - Reorder constant pool for denser encoding. | |||
517 | void ValueEnumerator::OptimizeConstants(unsigned CstStart, unsigned CstEnd) { | |||
518 | if (CstStart == CstEnd || CstStart+1 == CstEnd) return; | |||
519 | ||||
520 | if (ShouldPreserveUseListOrder) | |||
521 | // Optimizing constants makes the use-list order difficult to predict. | |||
522 | // Disable it for now when trying to preserve the order. | |||
523 | return; | |||
524 | ||||
525 | std::stable_sort(Values.begin() + CstStart, Values.begin() + CstEnd, | |||
526 | [this](const std::pair<const Value *, unsigned> &LHS, | |||
527 | const std::pair<const Value *, unsigned> &RHS) { | |||
528 | // Sort by plane. | |||
529 | if (LHS.first->getType() != RHS.first->getType()) | |||
530 | return getTypeID(LHS.first->getType()) < getTypeID(RHS.first->getType()); | |||
531 | // Then by frequency. | |||
532 | return LHS.second > RHS.second; | |||
533 | }); | |||
534 | ||||
535 | // Ensure that integer and vector of integer constants are at the start of the | |||
536 | // constant pool. This is important so that GEP structure indices come before | |||
537 | // gep constant exprs. | |||
538 | std::stable_partition(Values.begin() + CstStart, Values.begin() + CstEnd, | |||
539 | isIntOrIntVectorValue); | |||
540 | ||||
541 | // Rebuild the modified portion of ValueMap. | |||
542 | for (; CstStart != CstEnd; ++CstStart) | |||
543 | ValueMap[Values[CstStart].first] = CstStart+1; | |||
544 | } | |||
545 | ||||
546 | /// EnumerateValueSymbolTable - Insert all of the values in the specified symbol | |||
547 | /// table into the values table. | |||
548 | void ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) { | |||
549 | for (ValueSymbolTable::const_iterator VI = VST.begin(), VE = VST.end(); | |||
550 | VI != VE; ++VI) | |||
551 | EnumerateValue(VI->getValue()); | |||
552 | } | |||
553 | ||||
554 | /// Insert all of the values referenced by named metadata in the specified | |||
555 | /// module. | |||
556 | void ValueEnumerator::EnumerateNamedMetadata(const Module &M) { | |||
557 | for (const auto &I : M.named_metadata()) | |||
558 | EnumerateNamedMDNode(&I); | |||
559 | } | |||
560 | ||||
561 | void ValueEnumerator::EnumerateNamedMDNode(const NamedMDNode *MD) { | |||
562 | for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i) | |||
563 | EnumerateMetadata(nullptr, MD->getOperand(i)); | |||
564 | } | |||
565 | ||||
566 | unsigned ValueEnumerator::getMetadataFunctionID(const Function *F) const { | |||
567 | return F ? getValueID(F) + 1 : 0; | |||
568 | } | |||
569 | ||||
570 | void ValueEnumerator::EnumerateMetadata(const Function *F, const Metadata *MD) { | |||
571 | EnumerateMetadata(getMetadataFunctionID(F), MD); | |||
572 | } | |||
573 | ||||
574 | void ValueEnumerator::EnumerateFunctionLocalMetadata( | |||
575 | const Function &F, const LocalAsMetadata *Local) { | |||
576 | EnumerateFunctionLocalMetadata(getMetadataFunctionID(&F), Local); | |||
577 | } | |||
578 | ||||
579 | void ValueEnumerator::dropFunctionFromMetadata( | |||
580 | MetadataMapType::value_type &FirstMD) { | |||
581 | SmallVector<const MDNode *, 64> Worklist; | |||
582 | auto push = [&Worklist](MetadataMapType::value_type &MD) { | |||
583 | auto &Entry = MD.second; | |||
584 | ||||
585 | // Nothing to do if this metadata isn't tagged. | |||
586 | if (!Entry.F) | |||
587 | return; | |||
588 | ||||
589 | // Drop the function tag. | |||
590 | Entry.F = 0; | |||
591 | ||||
592 | // If this is has an ID and is an MDNode, then its operands have entries as | |||
593 | // well. We need to drop the function from them too. | |||
594 | if (Entry.ID) | |||
595 | if (auto *N = dyn_cast<MDNode>(MD.first)) | |||
596 | Worklist.push_back(N); | |||
597 | }; | |||
598 | push(FirstMD); | |||
599 | while (!Worklist.empty()) | |||
600 | for (const Metadata *Op : Worklist.pop_back_val()->operands()) { | |||
601 | if (!Op) | |||
602 | continue; | |||
603 | auto MD = MetadataMap.find(Op); | |||
604 | if (MD != MetadataMap.end()) | |||
605 | push(*MD); | |||
606 | } | |||
607 | } | |||
608 | ||||
609 | void ValueEnumerator::EnumerateMetadata(unsigned F, const Metadata *MD) { | |||
610 | // It's vital for reader efficiency that uniqued subgraphs are done in | |||
611 | // post-order; it's expensive when their operands have forward references. | |||
612 | // If a distinct node is referenced from a uniqued node, it'll be delayed | |||
613 | // until the uniqued subgraph has been completely traversed. | |||
614 | SmallVector<const MDNode *, 32> DelayedDistinctNodes; | |||
615 | ||||
616 | // Start by enumerating MD, and then work through its transitive operands in | |||
617 | // post-order. This requires a depth-first search. | |||
618 | SmallVector<std::pair<const MDNode *, MDNode::op_iterator>, 32> Worklist; | |||
619 | if (const MDNode *N = enumerateMetadataImpl(F, MD)) | |||
620 | Worklist.push_back(std::make_pair(N, N->op_begin())); | |||
621 | ||||
622 | while (!Worklist.empty()) { | |||
623 | const MDNode *N = Worklist.back().first; | |||
624 | ||||
625 | // Enumerate operands until we hit a new node. We need to traverse these | |||
626 | // nodes' operands before visiting the rest of N's operands. | |||
627 | MDNode::op_iterator I = std::find_if( | |||
628 | Worklist.back().second, N->op_end(), | |||
629 | [&](const Metadata *MD) { return enumerateMetadataImpl(F, MD); }); | |||
630 | if (I != N->op_end()) { | |||
631 | auto *Op = cast<MDNode>(*I); | |||
632 | Worklist.back().second = ++I; | |||
633 | ||||
634 | // Delay traversing Op if it's a distinct node and N is uniqued. | |||
635 | if (Op->isDistinct() && !N->isDistinct()) | |||
636 | DelayedDistinctNodes.push_back(Op); | |||
637 | else | |||
638 | Worklist.push_back(std::make_pair(Op, Op->op_begin())); | |||
639 | continue; | |||
640 | } | |||
641 | ||||
642 | // All the operands have been visited. Now assign an ID. | |||
643 | Worklist.pop_back(); | |||
644 | MDs.push_back(N); | |||
645 | MetadataMap[N].ID = MDs.size(); | |||
646 | ||||
647 | // Flush out any delayed distinct nodes; these are all the distinct nodes | |||
648 | // that are leaves in last uniqued subgraph. | |||
649 | if (Worklist.empty() || Worklist.back().first->isDistinct()) { | |||
650 | for (const MDNode *N : DelayedDistinctNodes) | |||
651 | Worklist.push_back(std::make_pair(N, N->op_begin())); | |||
652 | DelayedDistinctNodes.clear(); | |||
653 | } | |||
654 | } | |||
655 | } | |||
656 | ||||
657 | const MDNode *ValueEnumerator::enumerateMetadataImpl(unsigned F, const Metadata *MD) { | |||
658 | if (!MD) | |||
659 | return nullptr; | |||
660 | ||||
661 | assert((((isa<MDNode>(MD) || isa<MDString>(MD) || isa< ConstantAsMetadata>(MD)) && "Invalid metadata kind" ) ? static_cast<void> (0) : __assert_fail ("(isa<MDNode>(MD) || isa<MDString>(MD) || isa<ConstantAsMetadata>(MD)) && \"Invalid metadata kind\"" , "/build/llvm-toolchain-snapshot-9~svn359999/lib/Bitcode/Writer/ValueEnumerator.cpp" , 663, __PRETTY_FUNCTION__)) | |||
662 | (isa<MDNode>(MD) || isa<MDString>(MD) || isa<ConstantAsMetadata>(MD)) &&(((isa<MDNode>(MD) || isa<MDString>(MD) || isa< ConstantAsMetadata>(MD)) && "Invalid metadata kind" ) ? static_cast<void> (0) : __assert_fail ("(isa<MDNode>(MD) || isa<MDString>(MD) || isa<ConstantAsMetadata>(MD)) && \"Invalid metadata kind\"" , "/build/llvm-toolchain-snapshot-9~svn359999/lib/Bitcode/Writer/ValueEnumerator.cpp" , 663, __PRETTY_FUNCTION__)) | |||
663 | "Invalid metadata kind")(((isa<MDNode>(MD) || isa<MDString>(MD) || isa< ConstantAsMetadata>(MD)) && "Invalid metadata kind" ) ? static_cast<void> (0) : __assert_fail ("(isa<MDNode>(MD) || isa<MDString>(MD) || isa<ConstantAsMetadata>(MD)) && \"Invalid metadata kind\"" , "/build/llvm-toolchain-snapshot-9~svn359999/lib/Bitcode/Writer/ValueEnumerator.cpp" , 663, __PRETTY_FUNCTION__)); | |||
664 | ||||
665 | auto Insertion = MetadataMap.insert(std::make_pair(MD, MDIndex(F))); | |||
666 | MDIndex &Entry = Insertion.first->second; | |||
667 | if (!Insertion.second) { | |||
668 | // Already mapped. If F doesn't match the function tag, drop it. | |||
669 | if (Entry.hasDifferentFunction(F)) | |||
670 | dropFunctionFromMetadata(*Insertion.first); | |||
671 | return nullptr; | |||
672 | } | |||
673 | ||||
674 | // Don't assign IDs to metadata nodes. | |||
675 | if (auto *N = dyn_cast<MDNode>(MD)) | |||
676 | return N; | |||
677 | ||||
678 | // Save the metadata. | |||
679 | MDs.push_back(MD); | |||
680 | Entry.ID = MDs.size(); | |||
681 | ||||
682 | // Enumerate the constant, if any. | |||
683 | if (auto *C = dyn_cast<ConstantAsMetadata>(MD)) | |||
684 | EnumerateValue(C->getValue()); | |||
685 | ||||
686 | return nullptr; | |||
687 | } | |||
688 | ||||
689 | /// EnumerateFunctionLocalMetadataa - Incorporate function-local metadata | |||
690 | /// information reachable from the metadata. | |||
691 | void ValueEnumerator::EnumerateFunctionLocalMetadata( | |||
692 | unsigned F, const LocalAsMetadata *Local) { | |||
693 | assert(F && "Expected a function")((F && "Expected a function") ? static_cast<void> (0) : __assert_fail ("F && \"Expected a function\"", "/build/llvm-toolchain-snapshot-9~svn359999/lib/Bitcode/Writer/ValueEnumerator.cpp" , 693, __PRETTY_FUNCTION__)); | |||
694 | ||||
695 | // Check to see if it's already in! | |||
696 | MDIndex &Index = MetadataMap[Local]; | |||
697 | if (Index.ID) { | |||
698 | assert(Index.F == F && "Expected the same function")((Index.F == F && "Expected the same function") ? static_cast <void> (0) : __assert_fail ("Index.F == F && \"Expected the same function\"" , "/build/llvm-toolchain-snapshot-9~svn359999/lib/Bitcode/Writer/ValueEnumerator.cpp" , 698, __PRETTY_FUNCTION__)); | |||
699 | return; | |||
700 | } | |||
701 | ||||
702 | MDs.push_back(Local); | |||
703 | Index.F = F; | |||
704 | Index.ID = MDs.size(); | |||
705 | ||||
706 | EnumerateValue(Local->getValue()); | |||
707 | } | |||
708 | ||||
709 | static unsigned getMetadataTypeOrder(const Metadata *MD) { | |||
710 | // Strings are emitted in bulk and must come first. | |||
711 | if (isa<MDString>(MD)) | |||
712 | return 0; | |||
713 | ||||
714 | // ConstantAsMetadata doesn't reference anything. We may as well shuffle it | |||
715 | // to the front since we can detect it. | |||
716 | auto *N = dyn_cast<MDNode>(MD); | |||
717 | if (!N) | |||
718 | return 1; | |||
719 | ||||
720 | // The reader is fast forward references for distinct node operands, but slow | |||
721 | // when uniqued operands are unresolved. | |||
722 | return N->isDistinct() ? 2 : 3; | |||
723 | } | |||
724 | ||||
725 | void ValueEnumerator::organizeMetadata() { | |||
726 | assert(MetadataMap.size() == MDs.size() &&((MetadataMap.size() == MDs.size() && "Metadata map and vector out of sync" ) ? static_cast<void> (0) : __assert_fail ("MetadataMap.size() == MDs.size() && \"Metadata map and vector out of sync\"" , "/build/llvm-toolchain-snapshot-9~svn359999/lib/Bitcode/Writer/ValueEnumerator.cpp" , 727, __PRETTY_FUNCTION__)) | |||
727 | "Metadata map and vector out of sync")((MetadataMap.size() == MDs.size() && "Metadata map and vector out of sync" ) ? static_cast<void> (0) : __assert_fail ("MetadataMap.size() == MDs.size() && \"Metadata map and vector out of sync\"" , "/build/llvm-toolchain-snapshot-9~svn359999/lib/Bitcode/Writer/ValueEnumerator.cpp" , 727, __PRETTY_FUNCTION__)); | |||
728 | ||||
729 | if (MDs.empty()) | |||
730 | return; | |||
731 | ||||
732 | // Copy out the index information from MetadataMap in order to choose a new | |||
733 | // order. | |||
734 | SmallVector<MDIndex, 64> Order; | |||
735 | Order.reserve(MetadataMap.size()); | |||
736 | for (const Metadata *MD : MDs) | |||
737 | Order.push_back(MetadataMap.lookup(MD)); | |||
738 | ||||
739 | // Partition: | |||
740 | // - by function, then | |||
741 | // - by isa<MDString> | |||
742 | // and then sort by the original/current ID. Since the IDs are guaranteed to | |||
743 | // be unique, the result of std::sort will be deterministic. There's no need | |||
744 | // for std::stable_sort. | |||
745 | llvm::sort(Order, [this](MDIndex LHS, MDIndex RHS) { | |||
746 | return std::make_tuple(LHS.F, getMetadataTypeOrder(LHS.get(MDs)), LHS.ID) < | |||
747 | std::make_tuple(RHS.F, getMetadataTypeOrder(RHS.get(MDs)), RHS.ID); | |||
748 | }); | |||
749 | ||||
750 | // Rebuild MDs, index the metadata ranges for each function in FunctionMDs, | |||
751 | // and fix up MetadataMap. | |||
752 | std::vector<const Metadata *> OldMDs = std::move(MDs); | |||
753 | MDs.reserve(OldMDs.size()); | |||
| ||||
754 | for (unsigned I = 0, E = Order.size(); I != E && !Order[I].F; ++I) { | |||
755 | auto *MD = Order[I].get(OldMDs); | |||
756 | MDs.push_back(MD); | |||
757 | MetadataMap[MD].ID = I + 1; | |||
758 | if (isa<MDString>(MD)) | |||
759 | ++NumMDStrings; | |||
760 | } | |||
761 | ||||
762 | // Return early if there's nothing for the functions. | |||
763 | if (MDs.size() == Order.size()) | |||
764 | return; | |||
765 | ||||
766 | // Build the function metadata ranges. | |||
767 | MDRange R; | |||
768 | FunctionMDs.reserve(OldMDs.size()); | |||
769 | unsigned PrevF = 0; | |||
770 | for (unsigned I = MDs.size(), E = Order.size(), ID = MDs.size(); I != E; | |||
771 | ++I) { | |||
772 | unsigned F = Order[I].F; | |||
773 | if (!PrevF) { | |||
774 | PrevF = F; | |||
775 | } else if (PrevF != F) { | |||
776 | R.Last = FunctionMDs.size(); | |||
777 | std::swap(R, FunctionMDInfo[PrevF]); | |||
778 | R.First = FunctionMDs.size(); | |||
779 | ||||
780 | ID = MDs.size(); | |||
781 | PrevF = F; | |||
782 | } | |||
783 | ||||
784 | auto *MD = Order[I].get(OldMDs); | |||
785 | FunctionMDs.push_back(MD); | |||
786 | MetadataMap[MD].ID = ++ID; | |||
787 | if (isa<MDString>(MD)) | |||
788 | ++R.NumStrings; | |||
789 | } | |||
790 | R.Last = FunctionMDs.size(); | |||
791 | FunctionMDInfo[PrevF] = R; | |||
792 | } | |||
793 | ||||
794 | void ValueEnumerator::incorporateFunctionMetadata(const Function &F) { | |||
795 | NumModuleMDs = MDs.size(); | |||
796 | ||||
797 | auto R = FunctionMDInfo.lookup(getValueID(&F) + 1); | |||
798 | NumMDStrings = R.NumStrings; | |||
799 | MDs.insert(MDs.end(), FunctionMDs.begin() + R.First, | |||
800 | FunctionMDs.begin() + R.Last); | |||
801 | } | |||
802 | ||||
803 | void ValueEnumerator::EnumerateValue(const Value *V) { | |||
804 | assert(!V->getType()->isVoidTy() && "Can't insert void values!")((!V->getType()->isVoidTy() && "Can't insert void values!" ) ? static_cast<void> (0) : __assert_fail ("!V->getType()->isVoidTy() && \"Can't insert void values!\"" , "/build/llvm-toolchain-snapshot-9~svn359999/lib/Bitcode/Writer/ValueEnumerator.cpp" , 804, __PRETTY_FUNCTION__)); | |||
805 | assert(!isa<MetadataAsValue>(V) && "EnumerateValue doesn't handle Metadata!")((!isa<MetadataAsValue>(V) && "EnumerateValue doesn't handle Metadata!" ) ? static_cast<void> (0) : __assert_fail ("!isa<MetadataAsValue>(V) && \"EnumerateValue doesn't handle Metadata!\"" , "/build/llvm-toolchain-snapshot-9~svn359999/lib/Bitcode/Writer/ValueEnumerator.cpp" , 805, __PRETTY_FUNCTION__)); | |||
806 | ||||
807 | // Check to see if it's already in! | |||
808 | unsigned &ValueID = ValueMap[V]; | |||
809 | if (ValueID) { | |||
810 | // Increment use count. | |||
811 | Values[ValueID-1].second++; | |||
812 | return; | |||
813 | } | |||
814 | ||||
815 | if (auto *GO = dyn_cast<GlobalObject>(V)) | |||
816 | if (const Comdat *C = GO->getComdat()) | |||
817 | Comdats.insert(C); | |||
818 | ||||
819 | // Enumerate the type of this value. | |||
820 | EnumerateType(V->getType()); | |||
821 | ||||
822 | if (const Constant *C = dyn_cast<Constant>(V)) { | |||
823 | if (isa<GlobalValue>(C)) { | |||
824 | // Initializers for globals are handled explicitly elsewhere. | |||
825 | } else if (C->getNumOperands()) { | |||
826 | // If a constant has operands, enumerate them. This makes sure that if a | |||
827 | // constant has uses (for example an array of const ints), that they are | |||
828 | // inserted also. | |||
829 | ||||
830 | // We prefer to enumerate them with values before we enumerate the user | |||
831 | // itself. This makes it more likely that we can avoid forward references | |||
832 | // in the reader. We know that there can be no cycles in the constants | |||
833 | // graph that don't go through a global variable. | |||
834 | for (User::const_op_iterator I = C->op_begin(), E = C->op_end(); | |||
835 | I != E; ++I) | |||
836 | if (!isa<BasicBlock>(*I)) // Don't enumerate BB operand to BlockAddress. | |||
837 | EnumerateValue(*I); | |||
838 | ||||
839 | // Finally, add the value. Doing this could make the ValueID reference be | |||
840 | // dangling, don't reuse it. | |||
841 | Values.push_back(std::make_pair(V, 1U)); | |||
842 | ValueMap[V] = Values.size(); | |||
843 | return; | |||
844 | } | |||
845 | } | |||
846 | ||||
847 | // Add the value. | |||
848 | Values.push_back(std::make_pair(V, 1U)); | |||
849 | ValueID = Values.size(); | |||
850 | } | |||
851 | ||||
852 | ||||
853 | void ValueEnumerator::EnumerateType(Type *Ty) { | |||
854 | unsigned *TypeID = &TypeMap[Ty]; | |||
855 | ||||
856 | // We've already seen this type. | |||
857 | if (*TypeID) | |||
858 | return; | |||
859 | ||||
860 | // If it is a non-anonymous struct, mark the type as being visited so that we | |||
861 | // don't recursively visit it. This is safe because we allow forward | |||
862 | // references of these in the bitcode reader. | |||
863 | if (StructType *STy = dyn_cast<StructType>(Ty)) | |||
864 | if (!STy->isLiteral()) | |||
865 | *TypeID = ~0U; | |||
866 | ||||
867 | // Enumerate all of the subtypes before we enumerate this type. This ensures | |||
868 | // that the type will be enumerated in an order that can be directly built. | |||
869 | for (Type *SubTy : Ty->subtypes()) | |||
870 | EnumerateType(SubTy); | |||
871 | ||||
872 | // Refresh the TypeID pointer in case the table rehashed. | |||
873 | TypeID = &TypeMap[Ty]; | |||
874 | ||||
875 | // Check to see if we got the pointer another way. This can happen when | |||
876 | // enumerating recursive types that hit the base case deeper than they start. | |||
877 | // | |||
878 | // If this is actually a struct that we are treating as forward ref'able, | |||
879 | // then emit the definition now that all of its contents are available. | |||
880 | if (*TypeID && *TypeID != ~0U) | |||
881 | return; | |||
882 | ||||
883 | // Add this type now that its contents are all happily enumerated. | |||
884 | Types.push_back(Ty); | |||
885 | ||||
886 | *TypeID = Types.size(); | |||
887 | } | |||
888 | ||||
889 | // Enumerate the types for the specified value. If the value is a constant, | |||
890 | // walk through it, enumerating the types of the constant. | |||
891 | void ValueEnumerator::EnumerateOperandType(const Value *V) { | |||
892 | EnumerateType(V->getType()); | |||
893 | ||||
894 | assert(!isa<MetadataAsValue>(V) && "Unexpected metadata operand")((!isa<MetadataAsValue>(V) && "Unexpected metadata operand" ) ? static_cast<void> (0) : __assert_fail ("!isa<MetadataAsValue>(V) && \"Unexpected metadata operand\"" , "/build/llvm-toolchain-snapshot-9~svn359999/lib/Bitcode/Writer/ValueEnumerator.cpp" , 894, __PRETTY_FUNCTION__)); | |||
895 | ||||
896 | const Constant *C = dyn_cast<Constant>(V); | |||
897 | if (!C) | |||
898 | return; | |||
899 | ||||
900 | // If this constant is already enumerated, ignore it, we know its type must | |||
901 | // be enumerated. | |||
902 | if (ValueMap.count(C)) | |||
903 | return; | |||
904 | ||||
905 | // This constant may have operands, make sure to enumerate the types in | |||
906 | // them. | |||
907 | for (const Value *Op : C->operands()) { | |||
908 | // Don't enumerate basic blocks here, this happens as operands to | |||
909 | // blockaddress. | |||
910 | if (isa<BasicBlock>(Op)) | |||
911 | continue; | |||
912 | ||||
913 | EnumerateOperandType(Op); | |||
914 | } | |||
915 | } | |||
916 | ||||
917 | void ValueEnumerator::EnumerateAttributes(AttributeList PAL) { | |||
918 | if (PAL.isEmpty()) return; // null is always 0. | |||
919 | ||||
920 | // Do a lookup. | |||
921 | unsigned &Entry = AttributeListMap[PAL]; | |||
922 | if (Entry == 0) { | |||
923 | // Never saw this before, add it. | |||
924 | AttributeLists.push_back(PAL); | |||
925 | Entry = AttributeLists.size(); | |||
926 | } | |||
927 | ||||
928 | // Do lookups for all attribute groups. | |||
929 | for (unsigned i = PAL.index_begin(), e = PAL.index_end(); i != e; ++i) { | |||
930 | AttributeSet AS = PAL.getAttributes(i); | |||
931 | if (!AS.hasAttributes()) | |||
932 | continue; | |||
933 | IndexAndAttrSet Pair = {i, AS}; | |||
934 | unsigned &Entry = AttributeGroupMap[Pair]; | |||
935 | if (Entry == 0) { | |||
936 | AttributeGroups.push_back(Pair); | |||
937 | Entry = AttributeGroups.size(); | |||
938 | } | |||
939 | } | |||
940 | } | |||
941 | ||||
942 | void ValueEnumerator::incorporateFunction(const Function &F) { | |||
943 | InstructionCount = 0; | |||
944 | NumModuleValues = Values.size(); | |||
945 | ||||
946 | // Add global metadata to the function block. This doesn't include | |||
947 | // LocalAsMetadata. | |||
948 | incorporateFunctionMetadata(F); | |||
949 | ||||
950 | // Adding function arguments to the value table. | |||
951 | for (const auto &I : F.args()) | |||
952 | EnumerateValue(&I); | |||
953 | ||||
954 | FirstFuncConstantID = Values.size(); | |||
955 | ||||
956 | // Add all function-level constants to the value table. | |||
957 | for (const BasicBlock &BB : F) { | |||
958 | for (const Instruction &I : BB) | |||
959 | for (const Use &OI : I.operands()) { | |||
960 | if ((isa<Constant>(OI) && !isa<GlobalValue>(OI)) || isa<InlineAsm>(OI)) | |||
961 | EnumerateValue(OI); | |||
962 | } | |||
963 | BasicBlocks.push_back(&BB); | |||
964 | ValueMap[&BB] = BasicBlocks.size(); | |||
965 | } | |||
966 | ||||
967 | // Optimize the constant layout. | |||
968 | OptimizeConstants(FirstFuncConstantID, Values.size()); | |||
969 | ||||
970 | // Add the function's parameter attributes so they are available for use in | |||
971 | // the function's instruction. | |||
972 | EnumerateAttributes(F.getAttributes()); | |||
973 | ||||
974 | FirstInstID = Values.size(); | |||
975 | ||||
976 | SmallVector<LocalAsMetadata *, 8> FnLocalMDVector; | |||
977 | // Add all of the instructions. | |||
978 | for (const BasicBlock &BB : F) { | |||
979 | for (const Instruction &I : BB) { | |||
980 | for (const Use &OI : I.operands()) { | |||
981 | if (auto *MD = dyn_cast<MetadataAsValue>(&OI)) | |||
982 | if (auto *Local = dyn_cast<LocalAsMetadata>(MD->getMetadata())) | |||
983 | // Enumerate metadata after the instructions they might refer to. | |||
984 | FnLocalMDVector.push_back(Local); | |||
985 | } | |||
986 | ||||
987 | if (!I.getType()->isVoidTy()) | |||
988 | EnumerateValue(&I); | |||
989 | } | |||
990 | } | |||
991 | ||||
992 | // Add all of the function-local metadata. | |||
993 | for (unsigned i = 0, e = FnLocalMDVector.size(); i != e; ++i) { | |||
994 | // At this point, every local values have been incorporated, we shouldn't | |||
995 | // have a metadata operand that references a value that hasn't been seen. | |||
996 | assert(ValueMap.count(FnLocalMDVector[i]->getValue()) &&((ValueMap.count(FnLocalMDVector[i]->getValue()) && "Missing value for metadata operand") ? static_cast<void> (0) : __assert_fail ("ValueMap.count(FnLocalMDVector[i]->getValue()) && \"Missing value for metadata operand\"" , "/build/llvm-toolchain-snapshot-9~svn359999/lib/Bitcode/Writer/ValueEnumerator.cpp" , 997, __PRETTY_FUNCTION__)) | |||
997 | "Missing value for metadata operand")((ValueMap.count(FnLocalMDVector[i]->getValue()) && "Missing value for metadata operand") ? static_cast<void> (0) : __assert_fail ("ValueMap.count(FnLocalMDVector[i]->getValue()) && \"Missing value for metadata operand\"" , "/build/llvm-toolchain-snapshot-9~svn359999/lib/Bitcode/Writer/ValueEnumerator.cpp" , 997, __PRETTY_FUNCTION__)); | |||
998 | EnumerateFunctionLocalMetadata(F, FnLocalMDVector[i]); | |||
999 | } | |||
1000 | } | |||
1001 | ||||
1002 | void ValueEnumerator::purgeFunction() { | |||
1003 | /// Remove purged values from the ValueMap. | |||
1004 | for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i) | |||
1005 | ValueMap.erase(Values[i].first); | |||
1006 | for (unsigned i = NumModuleMDs, e = MDs.size(); i != e; ++i) | |||
1007 | MetadataMap.erase(MDs[i]); | |||
1008 | for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i) | |||
1009 | ValueMap.erase(BasicBlocks[i]); | |||
1010 | ||||
1011 | Values.resize(NumModuleValues); | |||
1012 | MDs.resize(NumModuleMDs); | |||
1013 | BasicBlocks.clear(); | |||
1014 | NumMDStrings = 0; | |||
1015 | } | |||
1016 | ||||
1017 | static void IncorporateFunctionInfoGlobalBBIDs(const Function *F, | |||
1018 | DenseMap<const BasicBlock*, unsigned> &IDMap) { | |||
1019 | unsigned Counter = 0; | |||
1020 | for (const BasicBlock &BB : *F) | |||
1021 | IDMap[&BB] = ++Counter; | |||
1022 | } | |||
1023 | ||||
1024 | /// getGlobalBasicBlockID - This returns the function-specific ID for the | |||
1025 | /// specified basic block. This is relatively expensive information, so it | |||
1026 | /// should only be used by rare constructs such as address-of-label. | |||
1027 | unsigned ValueEnumerator::getGlobalBasicBlockID(const BasicBlock *BB) const { | |||
1028 | unsigned &Idx = GlobalBasicBlockIDs[BB]; | |||
1029 | if (Idx != 0) | |||
1030 | return Idx-1; | |||
1031 | ||||
1032 | IncorporateFunctionInfoGlobalBBIDs(BB->getParent(), GlobalBasicBlockIDs); | |||
1033 | return getGlobalBasicBlockID(BB); | |||
1034 | } | |||
1035 | ||||
1036 | uint64_t ValueEnumerator::computeBitsRequiredForTypeIndicies() const { | |||
1037 | return Log2_32_Ceil(getTypes().size() + 1); | |||
1038 | } |