LLVM  16.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 "llvm/ADT/SmallVector.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"
21 #include "llvm/IR/DerivedTypes.h"
22 #include "llvm/IR/Function.h"
23 #include "llvm/IR/GlobalAlias.h"
24 #include "llvm/IR/GlobalIFunc.h"
25 #include "llvm/IR/GlobalObject.h"
26 #include "llvm/IR/GlobalValue.h"
27 #include "llvm/IR/GlobalVariable.h"
28 #include "llvm/IR/Instruction.h"
29 #include "llvm/IR/Instructions.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"
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 
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 
274 static 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 
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());
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());
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 
501 unsigned 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 
507 unsigned 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 
517 unsigned 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 
535 void 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 
561 void 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.
576 void 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.
584 void ValueEnumerator::EnumerateNamedMetadata(const Module &M) {
585  for (const auto &I : M.named_metadata())
586  EnumerateNamedMDNode(&I);
587 }
588 
589 void ValueEnumerator::EnumerateNamedMDNode(const NamedMDNode *MD) {
590  for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i)
591  EnumerateMetadata(nullptr, MD->getOperand(i));
592 }
593 
594 unsigned ValueEnumerator::getMetadataFunctionID(const Function *F) const {
595  return F ? getValueID(F) + 1 : 0;
596 }
597 
598 void ValueEnumerator::EnumerateMetadata(const Function *F, const Metadata *MD) {
599  EnumerateMetadata(getMetadataFunctionID(F), MD);
600 }
601 
602 void ValueEnumerator::EnumerateFunctionLocalMetadata(
603  const Function &F, const LocalAsMetadata *Local) {
604  EnumerateFunctionLocalMetadata(getMetadataFunctionID(&F), Local);
605 }
606 
607 void ValueEnumerator::EnumerateFunctionLocalListMetadata(
608  const Function &F, const DIArgList *ArgList) {
609  EnumerateFunctionLocalListMetadata(getMetadataFunctionID(&F), ArgList);
610 }
611 
612 void 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 
642 void 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.
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 
690 const 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.
725 void 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.
745 void 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 
776 static 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 
792 void 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 
862 void 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 
871 void 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 
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.
964 void 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 
996 void 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.
1134 unsigned 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 }
i
i
Definition: README.txt:29
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
llvm::less_second
Function object to check whether the second component of a std::pair compares less than the second co...
Definition: STLExtras.h:1363
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:484
MathExtras.h
GlobalIFunc.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:360
llvm::NamedMDNode
A tuple of MDNodes.
Definition: Metadata.h:1588
Metadata.h
llvm::NamedMDNode::getNumOperands
unsigned getNumOperands() const
Definition: Metadata.cpp:1212
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:197
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:1183
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:302
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:381
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:145
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
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
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:776
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:1124
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:52
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:623
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:327
BasicBlock.h
orderModule
static OrderMap orderModule(const Module &M)
Definition: DXILValueEnumerator.cpp:105
VI
@ VI
Definition: SIInstrInfo.cpp:7858
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::dxil
Definition: DXILBitcodeWriter.cpp:55
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:53
llvm::DenseMap
Definition: DenseMap.h:714
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:4588
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
llvm::NamedMDNode::getOperand
MDNode * getOperand(unsigned i) const
Definition: Metadata.cpp:1216
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:4787
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:1599
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:254
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:308
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:207
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:1645
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:99
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1563
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:1698
llvm::ValueMap::find
iterator find(const KeyT &Val)
Definition: ValueMap.h:156
predictUseListOrder
static UseListOrderStack predictUseListOrder(const Module &M)
Definition: DXILValueEnumerator.cpp:301
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:598
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:341
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::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:661
llvm::AttributeList::indexes
index_iterator indexes() const
Use this to iterate over the valid attribute indexes.
Definition: Attributes.h:920
predictValueUseListOrder
static void predictValueUseListOrder(const Value *V, const Function *F, OrderMap &OM, UseListOrderStack &Stack)
Definition: DXILValueEnumerator.cpp:274
llvm::ValueAsMetadata
Value wrapper in the Metadata hierarchy.
Definition: Metadata.h:345
DerivedTypes.h
llvm::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: TypedPointerType.cpp:17
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:99
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:651
Value.h
llvm::GlobalIFunc
Definition: GlobalIFunc.h:34
TypedPointerType.h
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:932
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