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