LLVM  15.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"
15 #include "DXILPointerType.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"
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/Use.h"
36 #include "llvm/IR/User.h"
37 #include "llvm/IR/Value.h"
39 #include "llvm/Support/Casting.h"
40 #include "llvm/Support/Compiler.h"
41 #include "llvm/Support/Debug.h"
44 #include <algorithm>
45 #include <cstddef>
46 #include <iterator>
47 #include <tuple>
48 
49 using namespace llvm;
50 using namespace llvm::dxil;
51 
52 namespace {
53 
54 struct 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 
85 static 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 
105 static 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 
204 static 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 
263  if (llvm::is_sorted(List, [](const Entry &L, const Entry &R) {
264  return L.second < R.second;
265  }))
266  // Order is already correct.
267  return;
268 
269  // Store the shuffle.
270  Stack.emplace_back(V, F, List.size());
271  assert(List.size() == Stack.back().Shuffle.size() && "Wrong size");
272  for (size_t I = 0, E = List.size(); I != E; ++I)
273  Stack.back().Shuffle[I] = List[I].second;
274 }
275 
276 static void predictValueUseListOrder(const Value *V, const Function *F,
277  OrderMap &OM, UseListOrderStack &Stack) {
278  auto &IDPair = OM[V];
279  assert(IDPair.first && "Unmapped value");
280  if (IDPair.second)
281  // Already predicted.
282  return;
283 
284  // Do the actual prediction.
285  IDPair.second = true;
286  if (!V->use_empty() && std::next(V->use_begin()) != V->use_end())
287  predictValueUseListOrderImpl(V, F, IDPair.first, OM, Stack);
288 
289  // Recursive descent into constants.
290  if (const Constant *C = dyn_cast<Constant>(V)) {
291  if (C->getNumOperands()) { // Visit GlobalValues.
292  for (const Value *Op : C->operands())
293  if (isa<Constant>(Op)) // Visit GlobalValues.
294  predictValueUseListOrder(Op, F, OM, Stack);
295  if (auto *CE = dyn_cast<ConstantExpr>(C))
296  if (CE->getOpcode() == Instruction::ShuffleVector)
297  predictValueUseListOrder(CE->getShuffleMaskForBitcode(), F, OM,
298  Stack);
299  }
300  }
301 }
302 
304  OrderMap OM = orderModule(M);
305 
306  // Use-list orders need to be serialized after all the users have been added
307  // to a value, or else the shuffles will be incomplete. Store them per
308  // function in a stack.
309  //
310  // Aside from function order, the order of values doesn't matter much here.
311  UseListOrderStack Stack;
312 
313  // We want to visit the functions backward now so we can list function-local
314  // constants in the last Function they're used in. Module-level constants
315  // have already been visited above.
316  for (const Function &F : llvm::reverse(M)) {
317  if (F.isDeclaration())
318  continue;
319  for (const BasicBlock &BB : F)
320  predictValueUseListOrder(&BB, &F, OM, Stack);
321  for (const Argument &A : F.args())
322  predictValueUseListOrder(&A, &F, OM, Stack);
323  for (const BasicBlock &BB : F)
324  for (const Instruction &I : BB) {
325  for (const Value *Op : I.operands())
326  if (isa<Constant>(*Op) || isa<InlineAsm>(*Op)) // Visit GlobalValues.
327  predictValueUseListOrder(Op, &F, OM, Stack);
328  if (auto *SVI = dyn_cast<ShuffleVectorInst>(&I))
329  predictValueUseListOrder(SVI->getShuffleMaskForBitcode(), &F, OM,
330  Stack);
331  }
332  for (const BasicBlock &BB : F)
333  for (const Instruction &I : BB)
334  predictValueUseListOrder(&I, &F, OM, Stack);
335  }
336 
337  // Visit globals last, since the module-level use-list block will be seen
338  // before the function bodies are processed.
339  for (const GlobalVariable &G : M.globals())
340  predictValueUseListOrder(&G, nullptr, OM, Stack);
341  for (const Function &F : M)
342  predictValueUseListOrder(&F, nullptr, OM, Stack);
343  for (const GlobalAlias &A : M.aliases())
344  predictValueUseListOrder(&A, nullptr, OM, Stack);
345  for (const GlobalIFunc &I : M.ifuncs())
346  predictValueUseListOrder(&I, nullptr, OM, Stack);
347  for (const GlobalVariable &G : M.globals())
348  if (G.hasInitializer())
349  predictValueUseListOrder(G.getInitializer(), nullptr, OM, Stack);
350  for (const GlobalAlias &A : M.aliases())
351  predictValueUseListOrder(A.getAliasee(), nullptr, OM, Stack);
352  for (const GlobalIFunc &I : M.ifuncs())
353  predictValueUseListOrder(I.getResolver(), nullptr, OM, Stack);
354  for (const Function &F : M) {
355  for (const Use &U : F.operands())
356  predictValueUseListOrder(U.get(), nullptr, OM, Stack);
357  }
358 
359  return Stack;
360 }
361 
364 
366 
367  // Enumerate the global variables.
368  for (const GlobalVariable &GV : M.globals()) {
369  EnumerateValue(&GV);
370  EnumerateType(GV.getValueType());
371  }
372 
373  // Enumerate the functions.
374  for (const Function &F : M) {
375  EnumerateValue(&F);
376  EnumerateType(F.getValueType());
378  dxil::TypedPointerType::get(F.getFunctionType(), F.getAddressSpace()));
379  EnumerateAttributes(F.getAttributes());
380  }
381 
382  // Enumerate the aliases.
383  for (const GlobalAlias &GA : M.aliases()) {
384  EnumerateValue(&GA);
385  EnumerateType(GA.getValueType());
386  }
387 
388  // Enumerate the ifuncs.
389  for (const GlobalIFunc &GIF : M.ifuncs()) {
390  EnumerateValue(&GIF);
391  EnumerateType(GIF.getValueType());
392  }
393 
394  // Enumerate the global variable initializers and attributes.
395  for (const GlobalVariable &GV : M.globals()) {
396  if (GV.hasInitializer())
397  EnumerateValue(GV.getInitializer());
399  dxil::TypedPointerType::get(GV.getValueType(), GV.getAddressSpace()));
400  if (GV.hasAttributes())
401  EnumerateAttributes(GV.getAttributesAsList(AttributeList::FunctionIndex));
402  }
403 
404  // Enumerate the aliasees.
405  for (const GlobalAlias &GA : M.aliases())
406  EnumerateValue(GA.getAliasee());
407 
408  // Enumerate the ifunc resolvers.
409  for (const GlobalIFunc &GIF : M.ifuncs())
410  EnumerateValue(GIF.getResolver());
411 
412  // Enumerate any optional Function data.
413  for (const Function &F : M)
414  for (const Use &U : F.operands())
415  EnumerateValue(U.get());
416 
417  // Enumerate the metadata type.
418  //
419  // TODO: Move this to ValueEnumerator::EnumerateOperandType() once bitcode
420  // only encodes the metadata type when it's used as a value.
421  EnumerateType(Type::getMetadataTy(M.getContext()));
422 
423  // Insert constants and metadata that are named at module level into the slot
424  // pool so that the module symbol table can refer to them...
425  EnumerateValueSymbolTable(M.getValueSymbolTable());
426  EnumerateNamedMetadata(M);
427 
429  for (const GlobalVariable &GV : M.globals()) {
430  MDs.clear();
431  GV.getAllMetadata(MDs);
432  for (const auto &I : MDs)
433  // FIXME: Pass GV to EnumerateMetadata and arrange for the bitcode writer
434  // to write metadata to the global variable's own metadata block
435  // (PR28134).
436  EnumerateMetadata(nullptr, I.second);
437  }
438 
439  // Enumerate types used by function bodies and argument lists.
440  for (const Function &F : M) {
441  for (const Argument &A : F.args())
442  EnumerateType(A.getType());
443 
444  // Enumerate metadata attached to this function.
445  MDs.clear();
446  F.getAllMetadata(MDs);
447  for (const auto &I : MDs)
448  EnumerateMetadata(F.isDeclaration() ? nullptr : &F, I.second);
449 
450  for (const BasicBlock &BB : F)
451  for (const Instruction &I : BB) {
452  for (const Use &Op : I.operands()) {
453  auto *MD = dyn_cast<MetadataAsValue>(&Op);
454  if (!MD) {
455  EnumerateOperandType(Op);
456  continue;
457  }
458 
459  // Local metadata is enumerated during function-incorporation, but
460  // any ConstantAsMetadata arguments in a DIArgList should be examined
461  // now.
462  if (isa<LocalAsMetadata>(MD->getMetadata()))
463  continue;
464  if (auto *AL = dyn_cast<DIArgList>(MD->getMetadata())) {
465  for (auto *VAM : AL->getArgs())
466  if (isa<ConstantAsMetadata>(VAM))
467  EnumerateMetadata(&F, VAM);
468  continue;
469  }
470 
471  EnumerateMetadata(&F, MD->getMetadata());
472  }
473  if (auto *SVI = dyn_cast<ShuffleVectorInst>(&I))
474  EnumerateType(SVI->getShuffleMaskForBitcode()->getType());
475  if (auto *GEP = dyn_cast<GetElementPtrInst>(&I))
476  EnumerateType(GEP->getSourceElementType());
477  if (auto *AI = dyn_cast<AllocaInst>(&I))
478  EnumerateType(AI->getAllocatedType());
479  EnumerateType(I.getType());
480  if (const auto *Call = dyn_cast<CallBase>(&I)) {
481  EnumerateAttributes(Call->getAttributes());
482  EnumerateType(Call->getFunctionType());
483  }
484 
485  // Enumerate metadata attached with this instruction.
486  MDs.clear();
487  I.getAllMetadataOtherThanDebugLoc(MDs);
488  for (unsigned i = 0, e = MDs.size(); i != e; ++i)
489  EnumerateMetadata(&F, MDs[i].second);
490 
491  // Don't enumerate the location directly -- it has a special record
492  // type -- but enumerate its operands.
493  if (DILocation *L = I.getDebugLoc())
494  for (const Metadata *Op : L->operands())
495  EnumerateMetadata(&F, Op);
496  }
497  }
498 
499  // Organize metadata ordering.
500  organizeMetadata();
501 }
502 
503 unsigned ValueEnumerator::getInstructionID(const Instruction *Inst) const {
504  InstructionMapType::const_iterator I = InstructionMap.find(Inst);
505  assert(I != InstructionMap.end() && "Instruction is not mapped!");
506  return I->second;
507 }
508 
509 unsigned ValueEnumerator::getComdatID(const Comdat *C) const {
510  unsigned ComdatID = Comdats.idFor(C);
511  assert(ComdatID && "Comdat not found!");
512  return ComdatID;
513 }
514 
516  InstructionMap[I] = InstructionCount++;
517 }
518 
519 unsigned ValueEnumerator::getValueID(const Value *V) const {
520  if (auto *MD = dyn_cast<MetadataAsValue>(V))
521  return getMetadataID(MD->getMetadata());
522 
524  assert(I != ValueMap.end() && "Value not in slotcalculator!");
525  return I->second - 1;
526 }
527 
528 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
530  print(dbgs(), ValueMap, "Default");
531  dbgs() << '\n';
532  print(dbgs(), MetadataMap, "MetaData");
533  dbgs() << '\n';
534 }
535 #endif
536 
537 void 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(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  OS << "\n\n";
560  }
561 }
562 
563 void ValueEnumerator::print(raw_ostream &OS, const MetadataMapType &Map,
564  const char *Name) const {
565  OS << "Map Name: " << Name << "\n";
566  OS << "Size: " << Map.size() << "\n";
567  for (const auto &I : Map) {
568  const Metadata *MD = I.first;
569  OS << "Metadata: slot = " << I.second.ID << "\n";
570  OS << "Metadata: function = " << I.second.F << "\n";
571  MD->print(OS);
572  OS << "\n";
573  }
574 }
575 
576 /// EnumerateValueSymbolTable - Insert all of the values in the specified symbol
577 /// table into the values table.
578 void ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) {
579  for (ValueSymbolTable::const_iterator VI = VST.begin(), VE = VST.end();
580  VI != VE; ++VI)
581  EnumerateValue(VI->getValue());
582 }
583 
584 /// Insert all of the values referenced by named metadata in the specified
585 /// module.
586 void ValueEnumerator::EnumerateNamedMetadata(const Module &M) {
587  for (const auto &I : M.named_metadata())
588  EnumerateNamedMDNode(&I);
589 }
590 
591 void ValueEnumerator::EnumerateNamedMDNode(const NamedMDNode *MD) {
592  for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i)
593  EnumerateMetadata(nullptr, MD->getOperand(i));
594 }
595 
596 unsigned ValueEnumerator::getMetadataFunctionID(const Function *F) const {
597  return F ? getValueID(F) + 1 : 0;
598 }
599 
600 void ValueEnumerator::EnumerateMetadata(const Function *F, const Metadata *MD) {
601  EnumerateMetadata(getMetadataFunctionID(F), MD);
602 }
603 
604 void ValueEnumerator::EnumerateFunctionLocalMetadata(
605  const Function &F, const LocalAsMetadata *Local) {
606  EnumerateFunctionLocalMetadata(getMetadataFunctionID(&F), Local);
607 }
608 
609 void ValueEnumerator::EnumerateFunctionLocalListMetadata(
610  const Function &F, const DIArgList *ArgList) {
611  EnumerateFunctionLocalListMetadata(getMetadataFunctionID(&F), ArgList);
612 }
613 
614 void ValueEnumerator::dropFunctionFromMetadata(
615  MetadataMapType::value_type &FirstMD) {
617  auto push = [&Worklist](MetadataMapType::value_type &MD) {
618  auto &Entry = MD.second;
619 
620  // Nothing to do if this metadata isn't tagged.
621  if (!Entry.F)
622  return;
623 
624  // Drop the function tag.
625  Entry.F = 0;
626 
627  // If this is has an ID and is an MDNode, then its operands have entries as
628  // well. We need to drop the function from them too.
629  if (Entry.ID)
630  if (auto *N = dyn_cast<MDNode>(MD.first))
631  Worklist.push_back(N);
632  };
633  push(FirstMD);
634  while (!Worklist.empty())
635  for (const Metadata *Op : Worklist.pop_back_val()->operands()) {
636  if (!Op)
637  continue;
638  auto MD = MetadataMap.find(Op);
639  if (MD != MetadataMap.end())
640  push(*MD);
641  }
642 }
643 
644 void ValueEnumerator::EnumerateMetadata(unsigned F, const Metadata *MD) {
645  // It's vital for reader efficiency that uniqued subgraphs are done in
646  // post-order; it's expensive when their operands have forward references.
647  // If a distinct node is referenced from a uniqued node, it'll be delayed
648  // until the uniqued subgraph has been completely traversed.
649  SmallVector<const MDNode *, 32> DelayedDistinctNodes;
650 
651  // Start by enumerating MD, and then work through its transitive operands in
652  // post-order. This requires a depth-first search.
654  if (const MDNode *N = enumerateMetadataImpl(F, MD))
655  Worklist.push_back(std::make_pair(N, N->op_begin()));
656 
657  while (!Worklist.empty()) {
658  const MDNode *N = Worklist.back().first;
659 
660  // Enumerate operands until we hit a new node. We need to traverse these
661  // nodes' operands before visiting the rest of N's operands.
663  Worklist.back().second, N->op_end(),
664  [&](const Metadata *MD) { return enumerateMetadataImpl(F, MD); });
665  if (I != N->op_end()) {
666  auto *Op = cast<MDNode>(*I);
667  Worklist.back().second = ++I;
668 
669  // Delay traversing Op if it's a distinct node and N is uniqued.
670  if (Op->isDistinct() && !N->isDistinct())
671  DelayedDistinctNodes.push_back(Op);
672  else
673  Worklist.push_back(std::make_pair(Op, Op->op_begin()));
674  continue;
675  }
676 
677  // All the operands have been visited. Now assign an ID.
678  Worklist.pop_back();
679  MDs.push_back(N);
680  MetadataMap[N].ID = MDs.size();
681 
682  // Flush out any delayed distinct nodes; these are all the distinct nodes
683  // that are leaves in last uniqued subgraph.
684  if (Worklist.empty() || Worklist.back().first->isDistinct()) {
685  for (const MDNode *N : DelayedDistinctNodes)
686  Worklist.push_back(std::make_pair(N, N->op_begin()));
687  DelayedDistinctNodes.clear();
688  }
689  }
690 }
691 
692 const MDNode *ValueEnumerator::enumerateMetadataImpl(unsigned F,
693  const Metadata *MD) {
694  if (!MD)
695  return nullptr;
696 
697  assert(
698  (isa<MDNode>(MD) || isa<MDString>(MD) || isa<ConstantAsMetadata>(MD)) &&
699  "Invalid metadata kind");
700 
701  auto Insertion = MetadataMap.insert(std::make_pair(MD, MDIndex(F)));
702  MDIndex &Entry = Insertion.first->second;
703  if (!Insertion.second) {
704  // Already mapped. If F doesn't match the function tag, drop it.
705  if (Entry.hasDifferentFunction(F))
706  dropFunctionFromMetadata(*Insertion.first);
707  return nullptr;
708  }
709 
710  // Don't assign IDs to metadata nodes.
711  if (auto *N = dyn_cast<MDNode>(MD))
712  return N;
713 
714  // Save the metadata.
715  MDs.push_back(MD);
716  Entry.ID = MDs.size();
717 
718  // Enumerate the constant, if any.
719  if (auto *C = dyn_cast<ConstantAsMetadata>(MD))
720  EnumerateValue(C->getValue());
721 
722  return nullptr;
723 }
724 
725 /// EnumerateFunctionLocalMetadata - Incorporate function-local metadata
726 /// information reachable from the metadata.
727 void ValueEnumerator::EnumerateFunctionLocalMetadata(
728  unsigned F, const LocalAsMetadata *Local) {
729  assert(F && "Expected a function");
730 
731  // Check to see if it's already in!
732  MDIndex &Index = MetadataMap[Local];
733  if (Index.ID) {
734  assert(Index.F == F && "Expected the same function");
735  return;
736  }
737 
738  MDs.push_back(Local);
739  Index.F = F;
740  Index.ID = MDs.size();
741 
742  EnumerateValue(Local->getValue());
743 }
744 
745 /// EnumerateFunctionLocalListMetadata - Incorporate function-local metadata
746 /// information reachable from the metadata.
747 void ValueEnumerator::EnumerateFunctionLocalListMetadata(
748  unsigned F, const DIArgList *ArgList) {
749  assert(F && "Expected a function");
750 
751  // Check to see if it's already in!
752  MDIndex &Index = MetadataMap[ArgList];
753  if (Index.ID) {
754  assert(Index.F == F && "Expected the same function");
755  return;
756  }
757 
758  for (ValueAsMetadata *VAM : ArgList->getArgs()) {
759  if (isa<LocalAsMetadata>(VAM)) {
760  assert(MetadataMap.count(VAM) &&
761  "LocalAsMetadata should be enumerated before DIArgList");
762  assert(MetadataMap[VAM].F == F &&
763  "Expected LocalAsMetadata in the same function");
764  } else {
765  assert(isa<ConstantAsMetadata>(VAM) &&
766  "Expected LocalAsMetadata or ConstantAsMetadata");
767  assert(ValueMap.count(VAM->getValue()) &&
768  "Constant should be enumerated beforeDIArgList");
769  EnumerateMetadata(F, VAM);
770  }
771  }
772 
773  MDs.push_back(ArgList);
774  Index.F = F;
775  Index.ID = MDs.size();
776 }
777 
778 static unsigned getMetadataTypeOrder(const Metadata *MD) {
779  // Strings are emitted in bulk and must come first.
780  if (isa<MDString>(MD))
781  return 0;
782 
783  // ConstantAsMetadata doesn't reference anything. We may as well shuffle it
784  // to the front since we can detect it.
785  auto *N = dyn_cast<MDNode>(MD);
786  if (!N)
787  return 1;
788 
789  // The reader is fast forward references for distinct node operands, but slow
790  // when uniqued operands are unresolved.
791  return N->isDistinct() ? 2 : 3;
792 }
793 
794 void ValueEnumerator::organizeMetadata() {
795  assert(MetadataMap.size() == MDs.size() &&
796  "Metadata map and vector out of sync");
797 
798  if (MDs.empty())
799  return;
800 
801  // Copy out the index information from MetadataMap in order to choose a new
802  // order.
804  Order.reserve(MetadataMap.size());
805  for (const Metadata *MD : MDs)
806  Order.push_back(MetadataMap.lookup(MD));
807 
808  // Partition:
809  // - by function, then
810  // - by isa<MDString>
811  // and then sort by the original/current ID. Since the IDs are guaranteed to
812  // be unique, the result of std::sort will be deterministic. There's no need
813  // for std::stable_sort.
814  llvm::sort(Order, [this](MDIndex LHS, MDIndex RHS) {
815  return std::make_tuple(LHS.F, getMetadataTypeOrder(LHS.get(MDs)), LHS.ID) <
816  std::make_tuple(RHS.F, getMetadataTypeOrder(RHS.get(MDs)), RHS.ID);
817  });
818 
819  // Rebuild MDs, index the metadata ranges for each function in FunctionMDs,
820  // and fix up MetadataMap.
821  std::vector<const Metadata *> OldMDs;
822  MDs.swap(OldMDs);
823  MDs.reserve(OldMDs.size());
824  for (unsigned I = 0, E = Order.size(); I != E && !Order[I].F; ++I) {
825  auto *MD = Order[I].get(OldMDs);
826  MDs.push_back(MD);
827  MetadataMap[MD].ID = I + 1;
828  if (isa<MDString>(MD))
829  ++NumMDStrings;
830  }
831 
832  // Return early if there's nothing for the functions.
833  if (MDs.size() == Order.size())
834  return;
835 
836  // Build the function metadata ranges.
837  MDRange R;
838  FunctionMDs.reserve(OldMDs.size());
839  unsigned PrevF = 0;
840  for (unsigned I = MDs.size(), E = Order.size(), ID = MDs.size(); I != E;
841  ++I) {
842  unsigned F = Order[I].F;
843  if (!PrevF) {
844  PrevF = F;
845  } else if (PrevF != F) {
846  R.Last = FunctionMDs.size();
847  std::swap(R, FunctionMDInfo[PrevF]);
848  R.First = FunctionMDs.size();
849 
850  ID = MDs.size();
851  PrevF = F;
852  }
853 
854  auto *MD = Order[I].get(OldMDs);
855  FunctionMDs.push_back(MD);
856  MetadataMap[MD].ID = ++ID;
857  if (isa<MDString>(MD))
858  ++R.NumStrings;
859  }
860  R.Last = FunctionMDs.size();
861  FunctionMDInfo[PrevF] = R;
862 }
863 
864 void ValueEnumerator::incorporateFunctionMetadata(const Function &F) {
865  NumModuleMDs = MDs.size();
866 
867  auto R = FunctionMDInfo.lookup(getValueID(&F) + 1);
868  NumMDStrings = R.NumStrings;
869  MDs.insert(MDs.end(), FunctionMDs.begin() + R.First,
870  FunctionMDs.begin() + R.Last);
871 }
872 
873 void ValueEnumerator::EnumerateValue(const Value *V) {
874  assert(!V->getType()->isVoidTy() && "Can't insert void values!");
875  assert(!isa<MetadataAsValue>(V) && "EnumerateValue doesn't handle Metadata!");
876 
877  // Check to see if it's already in!
878  unsigned &ValueID = ValueMap[V];
879  if (ValueID) {
880  // Increment use count.
881  Values[ValueID - 1].second++;
882  return;
883  }
884 
885  if (auto *GO = dyn_cast<GlobalObject>(V))
886  if (const Comdat *C = GO->getComdat())
887  Comdats.insert(C);
888 
889  // Enumerate the type of this value.
890  EnumerateType(V->getType());
891 
892  if (const Constant *C = dyn_cast<Constant>(V)) {
893  if (isa<GlobalValue>(C)) {
894  // Initializers for globals are handled explicitly elsewhere.
895  } else if (C->getNumOperands()) {
896  // If a constant has operands, enumerate them. This makes sure that if a
897  // constant has uses (for example an array of const ints), that they are
898  // inserted also.
899 
900  // We prefer to enumerate them with values before we enumerate the user
901  // itself. This makes it more likely that we can avoid forward references
902  // in the reader. We know that there can be no cycles in the constants
903  // graph that don't go through a global variable.
904  for (User::const_op_iterator I = C->op_begin(), E = C->op_end(); I != E;
905  ++I)
906  if (!isa<BasicBlock>(*I)) // Don't enumerate BB operand to BlockAddress.
907  EnumerateValue(*I);
908  if (auto *CE = dyn_cast<ConstantExpr>(C)) {
909  if (CE->getOpcode() == Instruction::ShuffleVector)
910  EnumerateValue(CE->getShuffleMaskForBitcode());
911  if (auto *GEP = dyn_cast<GEPOperator>(CE))
912  EnumerateType(GEP->getSourceElementType());
913  }
914 
915  // Finally, add the value. Doing this could make the ValueID reference be
916  // dangling, don't reuse it.
917  Values.push_back(std::make_pair(V, 1U));
918  ValueMap[V] = Values.size();
919  return;
920  }
921  }
922 
923  // Add the value.
924  Values.push_back(std::make_pair(V, 1U));
925  ValueID = Values.size();
926 }
927 
929  unsigned *TypeID = &TypeMap[Ty];
930 
931  // We've already seen this type.
932  if (*TypeID)
933  return;
934 
935  // If it is a non-anonymous struct, mark the type as being visited so that we
936  // don't recursively visit it. This is safe because we allow forward
937  // references of these in the bitcode reader.
938  if (StructType *STy = dyn_cast<StructType>(Ty))
939  if (!STy->isLiteral())
940  *TypeID = ~0U;
941 
942  // Enumerate all of the subtypes before we enumerate this type. This ensures
943  // that the type will be enumerated in an order that can be directly built.
944  for (Type *SubTy : Ty->subtypes())
945  EnumerateType(SubTy);
946 
947  // Refresh the TypeID pointer in case the table rehashed.
948  TypeID = &TypeMap[Ty];
949 
950  // Check to see if we got the pointer another way. This can happen when
951  // enumerating recursive types that hit the base case deeper than they start.
952  //
953  // If this is actually a struct that we are treating as forward ref'able,
954  // then emit the definition now that all of its contents are available.
955  if (*TypeID && *TypeID != ~0U)
956  return;
957 
958  // Add this type now that its contents are all happily enumerated.
959  Types.push_back(Ty);
960 
961  *TypeID = Types.size();
962 }
963 
964 // Enumerate the types for the specified value. If the value is a constant,
965 // walk through it, enumerating the types of the constant.
966 void ValueEnumerator::EnumerateOperandType(const Value *V) {
967  EnumerateType(V->getType());
968 
969  assert(!isa<MetadataAsValue>(V) && "Unexpected metadata operand");
970 
971  const Constant *C = dyn_cast<Constant>(V);
972  if (!C)
973  return;
974 
975  // If this constant is already enumerated, ignore it, we know its type must
976  // be enumerated.
977  if (ValueMap.count(C))
978  return;
979 
980  // This constant may have operands, make sure to enumerate the types in
981  // them.
982  for (const Value *Op : C->operands()) {
983  // Don't enumerate basic blocks here, this happens as operands to
984  // blockaddress.
985  if (isa<BasicBlock>(Op))
986  continue;
987 
988  EnumerateOperandType(Op);
989  }
990  if (auto *CE = dyn_cast<ConstantExpr>(C)) {
991  if (CE->getOpcode() == Instruction::ShuffleVector)
992  EnumerateOperandType(CE->getShuffleMaskForBitcode());
993  if (CE->getOpcode() == Instruction::GetElementPtr)
994  EnumerateType(cast<GEPOperator>(CE)->getSourceElementType());
995  }
996 }
997 
998 void ValueEnumerator::EnumerateAttributes(AttributeList PAL) {
999  if (PAL.isEmpty())
1000  return; // null is always 0.
1001 
1002  // Do a lookup.
1003  unsigned &Entry = AttributeListMap[PAL];
1004  if (Entry == 0) {
1005  // Never saw this before, add it.
1006  AttributeLists.push_back(PAL);
1007  Entry = AttributeLists.size();
1008  }
1009 
1010  // Do lookups for all attribute groups.
1011  for (unsigned i : PAL.indexes()) {
1012  AttributeSet AS = PAL.getAttributes(i);
1013  if (!AS.hasAttributes())
1014  continue;
1015  IndexAndAttrSet Pair = {i, AS};
1016  unsigned &Entry = AttributeGroupMap[Pair];
1017  if (Entry == 0) {
1018  AttributeGroups.push_back(Pair);
1019  Entry = AttributeGroups.size();
1020 
1021  for (Attribute Attr : AS) {
1022  if (Attr.isTypeAttribute())
1023  EnumerateType(Attr.getValueAsType());
1024  }
1025  }
1026  }
1027 }
1028 
1030  InstructionCount = 0;
1031  NumModuleValues = Values.size();
1032 
1033  // Add global metadata to the function block. This doesn't include
1034  // LocalAsMetadata.
1035  incorporateFunctionMetadata(F);
1036 
1037  // Adding function arguments to the value table.
1038  for (const auto &I : F.args()) {
1039  EnumerateValue(&I);
1040  if (I.hasAttribute(Attribute::ByVal))
1041  EnumerateType(I.getParamByValType());
1042  else if (I.hasAttribute(Attribute::StructRet))
1043  EnumerateType(I.getParamStructRetType());
1044  else if (I.hasAttribute(Attribute::ByRef))
1045  EnumerateType(I.getParamByRefType());
1046  }
1047  FirstFuncConstantID = Values.size();
1048 
1049  // Add all function-level constants to the value table.
1050  for (const BasicBlock &BB : F) {
1051  for (const Instruction &I : BB) {
1052  for (const Use &OI : I.operands()) {
1053  if ((isa<Constant>(OI) && !isa<GlobalValue>(OI)) || isa<InlineAsm>(OI))
1054  EnumerateValue(OI);
1055  }
1056  if (auto *SVI = dyn_cast<ShuffleVectorInst>(&I))
1057  EnumerateValue(SVI->getShuffleMaskForBitcode());
1058  }
1059  BasicBlocks.push_back(&BB);
1060  ValueMap[&BB] = BasicBlocks.size();
1061  }
1062 
1063  // Add the function's parameter attributes so they are available for use in
1064  // the function's instruction.
1065  EnumerateAttributes(F.getAttributes());
1066 
1067  FirstInstID = Values.size();
1068 
1069  SmallVector<LocalAsMetadata *, 8> FnLocalMDVector;
1070  SmallVector<DIArgList *, 8> ArgListMDVector;
1071  // Add all of the instructions.
1072  for (const BasicBlock &BB : F) {
1073  for (const Instruction &I : BB) {
1074  for (const Use &OI : I.operands()) {
1075  if (auto *MD = dyn_cast<MetadataAsValue>(&OI)) {
1076  if (auto *Local = dyn_cast<LocalAsMetadata>(MD->getMetadata())) {
1077  // Enumerate metadata after the instructions they might refer to.
1078  FnLocalMDVector.push_back(Local);
1079  } else if (auto *ArgList = dyn_cast<DIArgList>(MD->getMetadata())) {
1080  ArgListMDVector.push_back(ArgList);
1081  for (ValueAsMetadata *VMD : ArgList->getArgs()) {
1082  if (auto *Local = dyn_cast<LocalAsMetadata>(VMD)) {
1083  // Enumerate metadata after the instructions they might refer
1084  // to.
1085  FnLocalMDVector.push_back(Local);
1086  }
1087  }
1088  }
1089  }
1090  }
1091 
1092  if (!I.getType()->isVoidTy())
1093  EnumerateValue(&I);
1094  }
1095  }
1096 
1097  // Add all of the function-local metadata.
1098  for (unsigned i = 0, e = FnLocalMDVector.size(); i != e; ++i) {
1099  // At this point, every local values have been incorporated, we shouldn't
1100  // have a metadata operand that references a value that hasn't been seen.
1101  assert(ValueMap.count(FnLocalMDVector[i]->getValue()) &&
1102  "Missing value for metadata operand");
1103  EnumerateFunctionLocalMetadata(F, FnLocalMDVector[i]);
1104  }
1105  // DIArgList entries must come after function-local metadata, as it is not
1106  // possible to forward-reference them.
1107  for (const DIArgList *ArgList : ArgListMDVector)
1108  EnumerateFunctionLocalListMetadata(F, ArgList);
1109 }
1110 
1112  /// Remove purged values from the ValueMap.
1113  for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i)
1114  ValueMap.erase(Values[i].first);
1115  for (unsigned i = NumModuleMDs, e = MDs.size(); i != e; ++i)
1116  MetadataMap.erase(MDs[i]);
1117  for (const BasicBlock *BB : BasicBlocks)
1118  ValueMap.erase(BB);
1119 
1120  Values.resize(NumModuleValues);
1121  MDs.resize(NumModuleMDs);
1122  BasicBlocks.clear();
1123  NumMDStrings = 0;
1124 }
1125 
1128  unsigned Counter = 0;
1129  for (const BasicBlock &BB : *F)
1130  IDMap[&BB] = ++Counter;
1131 }
1132 
1133 /// getGlobalBasicBlockID - This returns the function-specific ID for the
1134 /// specified basic block. This is relatively expensive information, so it
1135 /// should only be used by rare constructs such as address-of-label.
1136 unsigned ValueEnumerator::getGlobalBasicBlockID(const BasicBlock *BB) const {
1137  unsigned &Idx = GlobalBasicBlockIDs[BB];
1138  if (Idx != 0)
1139  return Idx - 1;
1140 
1141  IncorporateFunctionInfoGlobalBBIDs(BB->getParent(), GlobalBasicBlockIDs);
1142  return getGlobalBasicBlockID(BB);
1143 }
1144 
1146  return Log2_32_Ceil(getTypes().size() + 1);
1147 }
i
i
Definition: README.txt:29
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
llvm::DIArgList
List of ValueAsMetadata, to be used as an argument to a dbg.value intrinsic.
Definition: DebugInfoMetadata.h:3565
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:494
MathExtras.h
GlobalIFunc.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::AttributeSet::hasAttributes
bool hasAttributes() const
Return true if attributes exists in this set.
Definition: Attributes.h:350
llvm::AArch64CC::AL
@ AL
Definition: AArch64BaseInfo.h:269
llvm::dxil::ValueEnumerator::ValueEnumerator
ValueEnumerator(const Module &M, Type *PrefixType)
Definition: DXILValueEnumerator.cpp:362
llvm::NamedMDNode
A tuple of MDNodes.
Definition: Metadata.h:1588
Metadata.h
llvm::NamedMDNode::getNumOperands
unsigned getNumOperands() const
Definition: Metadata.cpp:1211
DebugInfoMetadata.h
llvm::ValueMap::end
iterator end()
Definition: ValueMap.h:136
llvm::Function
Definition: Function.h:60
llvm::Attribute
Definition: Attributes.h:65
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::lookup
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:199
llvm::dxil::ValueEnumerator::purgeFunction
void purgeFunction()
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::ValueSymbolTable::begin
iterator begin()
Get an iterator that from the beginning of the symbol table.
Definition: ValueSymbolTable.h:98
llvm::Value::hasName
bool hasName() const
Definition: Value.h:261
DXILValueEnumerator.h
llvm::GlobalVariable
Definition: GlobalVariable.h:39
llvm::GlobalAlias
Definition: GlobalAlias.h:28
push
static void push(SmallVectorImpl< uint64_t > &R, StringRef Str)
Definition: BitstreamRemarkSerializer.cpp:24
llvm::DenseMapBase::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:304
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1557
llvm::dxil::ValueEnumerator::getInstructionID
unsigned getInstructionID(const Instruction *I) const
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
Module.h
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
llvm::AttributeList
Definition: Attributes.h:425
llvm::dxil::ValueEnumerator::dump
void dump() const
llvm::DenseMapBase::count
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:147
GlobalObject.h
Operator.h
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:893
llvm::LocalAsMetadata
Definition: Metadata.h:437
llvm::dxil::ValueEnumerator::UseListOrders
UseListOrderStack UseListOrders
Definition: DXILValueEnumerator.h:57
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
DXILPointerType.h
llvm::dxil::ValueEnumerator::setInstructionID
void setInstructionID(const Instruction *I)
Use.h
llvm::UniqueVector::idFor
unsigned idFor(const T &Entry) const
idFor - return the ID for an existing entry.
Definition: UniqueVector.h:57
getMetadataTypeOrder
static unsigned getMetadataTypeOrder(const Metadata *MD)
Definition: DXILValueEnumerator.cpp:778
llvm::dxil::ValueEnumerator::getValueID
unsigned getValueID(const Value *V) const
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:241
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::dxil::ValueEnumerator::print
void print(raw_ostream &OS, const ValueMapType &Map, const char *Name) const
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::DenseMapBase< DenseMap< const Instruction *, unsigned, DenseMapInfo< const Instruction * >, llvm::detail::DenseMapPair< const Instruction *, unsigned > >, const Instruction *, unsigned, DenseMapInfo< const Instruction * >, llvm::detail::DenseMapPair< const Instruction *, unsigned > >::const_iterator
DenseMapIterator< const Instruction *, unsigned, DenseMapInfo< const Instruction * >, llvm::detail::DenseMapPair< const Instruction *, unsigned >, true > const_iterator
Definition: DenseMap.h:73
Instruction.h
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::Type::getMetadataTy
static Type * getMetadataTy(LLVMContext &C)
Definition: Type.cpp:228
IncorporateFunctionInfoGlobalBBIDs
static void IncorporateFunctionInfoGlobalBBIDs(const Function *F, DenseMap< const BasicBlock *, unsigned > &IDMap)
Definition: DXILValueEnumerator.cpp:1126
llvm::ValueSymbolTable::end
iterator end()
Get an iterator to the end of the symbol table.
Definition: ValueSymbolTable.h:104
GlobalValue.h
llvm::msgpack::Type::Map
@ Map
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::StringMapConstIterator
Definition: StringMap.h:26
llvm::MDNode::operands
ArrayRef< MDOperand > operands() const
Definition: Metadata.h:1290
llvm::dxil::ValueEnumerator::getComdatID
unsigned getComdatID(const Comdat *C) const
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:376
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
llvm::Instruction
Definition: Instruction.h:42
llvm::AttributeList::getAttributes
AttributeSet getAttributes(unsigned Index) const
The attributes for the specified index are returned.
Definition: Attributes.cpp:1501
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::Comdat
Definition: Comdat.h:33
llvm::Metadata
Root of the metadata hierarchy.
Definition: Metadata.h:62
llvm::ValueMap::count
size_type count(const KeyT &Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: ValueMap.h:152
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:344
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Type.h
llvm::Log2_32_Ceil
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:636
llvm::dxil::ValueEnumerator::IndexAndAttrSet
std::pair< unsigned, AttributeSet > IndexAndAttrSet
Attribute groups as encoded in bitcode are almost AttributeSets, but they include the AttributeList i...
Definition: DXILValueEnumerator.h:55
ValueSymbolTable.h
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:200
llvm::Type::subtypes
ArrayRef< Type * > subtypes() const
Definition: Type.h:322
BasicBlock.h
orderModule
static OrderMap orderModule(const Module &M)
Definition: DXILValueEnumerator.cpp:105
VI
@ VI
Definition: SIInstrInfo.cpp:7861
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::dxil
Definition: DXILPointerType.h:18
llvm::dxil::ValueEnumerator::computeBitsRequiredForTypeIndicies
uint64_t computeBitsRequiredForTypeIndicies() const
llvm::dxil::ValueEnumerator::getTypes
const TypeList & getTypes() const
Definition: DXILValueEnumerator.h:212
index
splat index
Definition: README_ALTIVEC.txt:181
uint64_t
llvm::DenseMapBase< DenseMap< const Metadata *, MDIndex, DenseMapInfo< const Metadata * >, llvm::detail::DenseMapPair< const Metadata *, MDIndex > >, const Metadata *, MDIndex, DenseMapInfo< const Metadata * >, llvm::detail::DenseMapPair< const Metadata *, MDIndex > >::value_type
llvm::detail::DenseMapPair< const Metadata *, MDIndex > value_type
Definition: DenseMap.h:69
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:716
llvm::ValueMap::erase
bool erase(const KeyT &Val)
Definition: ValueMap.h:191
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::Value::print
void print(raw_ostream &O, bool IsForDebug=false) const
Implement operator<< on Value.
Definition: AsmWriter.cpp:4586
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:152
llvm::NamedMDNode::getOperand
MDNode * getOperand(unsigned i) const
Definition: Metadata.cpp:1215
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
predictValueUseListOrderImpl
static void predictValueUseListOrderImpl(const Value *V, const Function *F, unsigned ID, const OrderMap &OM, UseListOrderStack &Stack)
Definition: DXILValueEnumerator.cpp:204
llvm::DIArgList::getArgs
ArrayRef< ValueAsMetadata * > getArgs() const
Definition: DebugInfoMetadata.h:3597
llvm::Value::use_begin
use_iterator use_begin()
Definition: Value.h:360
llvm::Type::isVoidTy
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:139
llvm::WinEH::EncodingType::CE
@ CE
Windows NT (Windows on ARM)
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::MDNode
Metadata node.
Definition: Metadata.h:944
llvm::Metadata::print
void print(raw_ostream &OS, const Module *M=nullptr, bool IsForDebug=false) const
Print.
Definition: AsmWriter.cpp:4785
llvm::size
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:1598
llvm::dxil::ValueEnumerator::getMetadataID
unsigned getMetadataID(const Metadata *MD) const
Definition: DXILValueEnumerator.h:153
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::Value::getNumUses
unsigned getNumUses() const
This method computes the number of uses of this Value.
Definition: Value.cpp:251
if
if(llvm_vc STREQUAL "") set(fake_version_inc "$
Definition: CMakeLists.txt:14
Compiler.h
llvm::Value::use_end
use_iterator use_end()
Definition: Value.h:368
llvm::dxil::ValueEnumerator::getGlobalBasicBlockID
unsigned getGlobalBasicBlockID(const BasicBlock *BB) const
getGlobalBasicBlockID - This returns the function-specific ID for the specified basic block.
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:305
llvm::ValueMap
See the file comment.
Definition: ValueMap.h:85
llvm::DenseMapBase::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:209
Argument.h
llvm::find_if
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1644
llvm::pdb::PDB_DataKind::Local
@ Local
llvm::UseListOrderStack
std::vector< UseListOrder > UseListOrderStack
Definition: UseListOrder.h:39
Constant.h
llvm::dxil::ValueEnumerator::EnumerateType
void EnumerateType(Type *T)
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:50
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:84
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
GlobalVariable.h
Casting.h
Function.h
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::size
unsigned size() const
Definition: DenseMap.h:101
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1562
llvm::is_sorted
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:1697
llvm::ValueMap::find
iterator find(const KeyT &Val)
Definition: ValueMap.h:156
predictUseListOrder
static UseListOrderStack predictUseListOrder(const Module &M)
Definition: DXILValueEnumerator.cpp:303
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
orderValue
static void orderValue(const Value *V, OrderMap &OM)
Definition: DXILValueEnumerator.cpp:85
GlobalAlias.h
llvm::AttributeList::FunctionIndex
@ FunctionIndex
Definition: Attributes.h:429
Instructions.h
llvm::AttributeSet
Definition: Attributes.h:290
PrefixType
PrefixType
Definition: AsmWriter.cpp:340
SmallVector.h
llvm::ValueSymbolTable
This class provides a symbol table of name/value pairs.
Definition: ValueSymbolTable.h:37
lookup
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:108
User.h
List
const NodeList & List
Definition: RDFGraph.cpp:199
N
#define N
llvm::AttributeList::indexes
index_iterator indexes() const
Use this to iterate over the valid attribute indexes.
Definition: Attributes.h:914
predictValueUseListOrder
static void predictValueUseListOrder(const Value *V, const Function *F, OrderMap &OM, UseListOrderStack &Stack)
Definition: DXILValueEnumerator.cpp:276
llvm::ValueAsMetadata
Value wrapper in the Metadata hierarchy.
Definition: Metadata.h:345
DerivedTypes.h
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:171
llvm::Type::TypeID
TypeID
Definitions of all of the base types for the Type system.
Definition: Type.h:54
raw_ostream.h
llvm::dxil::ValueEnumerator::incorporateFunction
void incorporateFunction(const Function &F)
incorporateFunction/purgeFunction - If you'd like to deal with a function, use these two methods to g...
OrderMap
MapVector< const Value *, unsigned > OrderMap
Definition: AsmWriter.cpp:98
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:644
Value.h
llvm::GlobalIFunc
Definition: GlobalIFunc.h:34
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::UniqueVector::insert
unsigned insert(const T &Entry)
insert - Append entry to the vector if it doesn't already exist.
Definition: UniqueVector.h:40
Debug.h
llvm::AttributeList::isEmpty
bool isEmpty() const
Return true if there are no attributes.
Definition: Attributes.h:926
llvm::MDOperand
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:773
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::dxil::TypedPointerType::get
static TypedPointerType * get(Type *ElementType, unsigned AddressSpace)
This constructs a pointer to an object of the specified type in a numbered address space.
Definition: DXILPointerType.cpp:29