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