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