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