LLVM  14.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 (auto I = M.rbegin(), E = M.rend(); I != E; ++I) {
314  const Function &F = *I;
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 
360 static bool isIntOrIntVectorValue(const std::pair<const Value*, unsigned> &V) {
361  return V.first->getType()->isIntOrIntVectorTy();
362 }
363 
365  bool ShouldPreserveUseListOrder)
366  : ShouldPreserveUseListOrder(ShouldPreserveUseListOrder) {
367  if (ShouldPreserveUseListOrder)
369 
370  // Enumerate the global variables.
371  for (const GlobalVariable &GV : M.globals()) {
372  EnumerateValue(&GV);
373  EnumerateType(GV.getValueType());
374  }
375 
376  // Enumerate the functions.
377  for (const Function & F : M) {
378  EnumerateValue(&F);
379  EnumerateType(F.getValueType());
380  EnumerateAttributes(F.getAttributes());
381  }
382 
383  // Enumerate the aliases.
384  for (const GlobalAlias &GA : M.aliases()) {
385  EnumerateValue(&GA);
386  EnumerateType(GA.getValueType());
387  }
388 
389  // Enumerate the ifuncs.
390  for (const GlobalIFunc &GIF : M.ifuncs())
391  EnumerateValue(&GIF);
392 
393  // Remember what is the cutoff between globalvalue's and other constants.
394  unsigned FirstConstant = Values.size();
395 
396  // Enumerate the global variable initializers and attributes.
397  for (const GlobalVariable &GV : M.globals()) {
398  if (GV.hasInitializer())
399  EnumerateValue(GV.getInitializer());
400  if (GV.hasAttributes())
401  EnumerateAttributes(GV.getAttributesAsList(AttributeList::FunctionIndex));
402  }
403 
404  // Enumerate the aliasees.
405  for (const GlobalAlias &GA : M.aliases())
406  EnumerateValue(GA.getAliasee());
407 
408  // Enumerate the ifunc resolvers.
409  for (const GlobalIFunc &GIF : M.ifuncs())
410  EnumerateValue(GIF.getResolver());
411 
412  // Enumerate any optional Function data.
413  for (const Function &F : M)
414  for (const Use &U : F.operands())
415  EnumerateValue(U.get());
416 
417  // Enumerate the metadata type.
418  //
419  // TODO: Move this to ValueEnumerator::EnumerateOperandType() once bitcode
420  // only encodes the metadata type when it's used as a value.
421  EnumerateType(Type::getMetadataTy(M.getContext()));
422 
423  // Insert constants and metadata that are named at module level into the slot
424  // pool so that the module symbol table can refer to them...
425  EnumerateValueSymbolTable(M.getValueSymbolTable());
426  EnumerateNamedMetadata(M);
427 
429  for (const GlobalVariable &GV : M.globals()) {
430  MDs.clear();
431  GV.getAllMetadata(MDs);
432  for (const auto &I : MDs)
433  // FIXME: Pass GV to EnumerateMetadata and arrange for the bitcode writer
434  // to write metadata to the global variable's own metadata block
435  // (PR28134).
436  EnumerateMetadata(nullptr, I.second);
437  }
438 
439  // Enumerate types used by function bodies and argument lists.
440  for (const Function &F : M) {
441  for (const Argument &A : F.args())
442  EnumerateType(A.getType());
443 
444  // Enumerate metadata attached to this function.
445  MDs.clear();
446  F.getAllMetadata(MDs);
447  for (const auto &I : MDs)
448  EnumerateMetadata(F.isDeclaration() ? nullptr : &F, I.second);
449 
450  for (const BasicBlock &BB : F)
451  for (const Instruction &I : BB) {
452  for (const Use &Op : I.operands()) {
453  auto *MD = dyn_cast<MetadataAsValue>(&Op);
454  if (!MD) {
455  EnumerateOperandType(Op);
456  continue;
457  }
458 
459  // Local metadata is enumerated during function-incorporation, but
460  // any ConstantAsMetadata arguments in a DIArgList should be examined
461  // now.
462  if (isa<LocalAsMetadata>(MD->getMetadata()))
463  continue;
464  if (auto *AL = dyn_cast<DIArgList>(MD->getMetadata())) {
465  for (auto *VAM : AL->getArgs())
466  if (isa<ConstantAsMetadata>(VAM))
467  EnumerateMetadata(&F, VAM);
468  continue;
469  }
470 
471  EnumerateMetadata(&F, MD->getMetadata());
472  }
473  if (auto *SVI = dyn_cast<ShuffleVectorInst>(&I))
474  EnumerateType(SVI->getShuffleMaskForBitcode()->getType());
475  if (auto *GEP = dyn_cast<GetElementPtrInst>(&I))
476  EnumerateType(GEP->getSourceElementType());
477  if (auto *AI = dyn_cast<AllocaInst>(&I))
478  EnumerateType(AI->getAllocatedType());
479  EnumerateType(I.getType());
480  if (const auto *Call = dyn_cast<CallBase>(&I)) {
481  EnumerateAttributes(Call->getAttributes());
482  EnumerateType(Call->getFunctionType());
483  }
484 
485  // Enumerate metadata attached with this instruction.
486  MDs.clear();
487  I.getAllMetadataOtherThanDebugLoc(MDs);
488  for (unsigned i = 0, e = MDs.size(); i != e; ++i)
489  EnumerateMetadata(&F, MDs[i].second);
490 
491  // Don't enumerate the location directly -- it has a special record
492  // type -- but enumerate its operands.
493  if (DILocation *L = I.getDebugLoc())
494  for (const Metadata *Op : L->operands())
495  EnumerateMetadata(&F, Op);
496  }
497  }
498 
499  // Optimize constant ordering.
500  OptimizeConstants(FirstConstant, Values.size());
501 
502  // Organize metadata ordering.
503  organizeMetadata();
504 }
505 
506 unsigned ValueEnumerator::getInstructionID(const Instruction *Inst) const {
507  InstructionMapType::const_iterator I = InstructionMap.find(Inst);
508  assert(I != InstructionMap.end() && "Instruction is not mapped!");
509  return I->second;
510 }
511 
512 unsigned ValueEnumerator::getComdatID(const Comdat *C) const {
513  unsigned ComdatID = Comdats.idFor(C);
514  assert(ComdatID && "Comdat not found!");
515  return ComdatID;
516 }
517 
519  InstructionMap[I] = InstructionCount++;
520 }
521 
522 unsigned ValueEnumerator::getValueID(const Value *V) const {
523  if (auto *MD = dyn_cast<MetadataAsValue>(V))
524  return getMetadataID(MD->getMetadata());
525 
527  assert(I != ValueMap.end() && "Value not in slotcalculator!");
528  return I->second-1;
529 }
530 
531 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
533  print(dbgs(), ValueMap, "Default");
534  dbgs() << '\n';
535  print(dbgs(), MetadataMap, "MetaData");
536  dbgs() << '\n';
537 }
538 #endif
539 
541  const char *Name) const {
542  OS << "Map Name: " << Name << "\n";
543  OS << "Size: " << Map.size() << "\n";
544  for (ValueMapType::const_iterator I = Map.begin(),
545  E = Map.end(); I != E; ++I) {
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 (auto I = Map.begin(), E = Map.end(); I != E; ++I) {
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 
946  // Finally, add the value. Doing this could make the ValueID reference be
947  // dangling, don't reuse it.
948  Values.push_back(std::make_pair(V, 1U));
949  ValueMap[V] = Values.size();
950  return;
951  }
952  }
953 
954  // Add the value.
955  Values.push_back(std::make_pair(V, 1U));
956  ValueID = Values.size();
957 }
958 
959 
960 void ValueEnumerator::EnumerateType(Type *Ty) {
961  unsigned *TypeID = &TypeMap[Ty];
962 
963  // We've already seen this type.
964  if (*TypeID)
965  return;
966 
967  // If it is a non-anonymous struct, mark the type as being visited so that we
968  // don't recursively visit it. This is safe because we allow forward
969  // references of these in the bitcode reader.
970  if (StructType *STy = dyn_cast<StructType>(Ty))
971  if (!STy->isLiteral())
972  *TypeID = ~0U;
973 
974  // Enumerate all of the subtypes before we enumerate this type. This ensures
975  // that the type will be enumerated in an order that can be directly built.
976  for (Type *SubTy : Ty->subtypes())
977  EnumerateType(SubTy);
978 
979  // Refresh the TypeID pointer in case the table rehashed.
980  TypeID = &TypeMap[Ty];
981 
982  // Check to see if we got the pointer another way. This can happen when
983  // enumerating recursive types that hit the base case deeper than they start.
984  //
985  // If this is actually a struct that we are treating as forward ref'able,
986  // then emit the definition now that all of its contents are available.
987  if (*TypeID && *TypeID != ~0U)
988  return;
989 
990  // Add this type now that its contents are all happily enumerated.
991  Types.push_back(Ty);
992 
993  *TypeID = Types.size();
994 }
995 
996 // Enumerate the types for the specified value. If the value is a constant,
997 // walk through it, enumerating the types of the constant.
998 void ValueEnumerator::EnumerateOperandType(const Value *V) {
999  EnumerateType(V->getType());
1000 
1001  assert(!isa<MetadataAsValue>(V) && "Unexpected metadata operand");
1002 
1003  const Constant *C = dyn_cast<Constant>(V);
1004  if (!C)
1005  return;
1006 
1007  // If this constant is already enumerated, ignore it, we know its type must
1008  // be enumerated.
1009  if (ValueMap.count(C))
1010  return;
1011 
1012  // This constant may have operands, make sure to enumerate the types in
1013  // them.
1014  for (const Value *Op : C->operands()) {
1015  // Don't enumerate basic blocks here, this happens as operands to
1016  // blockaddress.
1017  if (isa<BasicBlock>(Op))
1018  continue;
1019 
1020  EnumerateOperandType(Op);
1021  }
1022  if (auto *CE = dyn_cast<ConstantExpr>(C)) {
1023  if (CE->getOpcode() == Instruction::ShuffleVector)
1024  EnumerateOperandType(CE->getShuffleMaskForBitcode());
1025  if (CE->getOpcode() == Instruction::GetElementPtr)
1026  EnumerateType(cast<GEPOperator>(CE)->getSourceElementType());
1027  }
1028 }
1029 
1030 void ValueEnumerator::EnumerateAttributes(AttributeList PAL) {
1031  if (PAL.isEmpty()) return; // null is always 0.
1032 
1033  // Do a lookup.
1034  unsigned &Entry = AttributeListMap[PAL];
1035  if (Entry == 0) {
1036  // Never saw this before, add it.
1037  AttributeLists.push_back(PAL);
1038  Entry = AttributeLists.size();
1039  }
1040 
1041  // Do lookups for all attribute groups.
1042  for (unsigned i = PAL.index_begin(), e = PAL.index_end(); i != e; ++i) {
1043  AttributeSet AS = PAL.getAttributes(i);
1044  if (!AS.hasAttributes())
1045  continue;
1046  IndexAndAttrSet Pair = {i, AS};
1047  unsigned &Entry = AttributeGroupMap[Pair];
1048  if (Entry == 0) {
1049  AttributeGroups.push_back(Pair);
1050  Entry = AttributeGroups.size();
1051 
1052  for (Attribute Attr : AS) {
1053  if (Attr.isTypeAttribute())
1054  EnumerateType(Attr.getValueAsType());
1055  }
1056  }
1057  }
1058 }
1059 
1061  InstructionCount = 0;
1062  NumModuleValues = Values.size();
1063 
1064  // Add global metadata to the function block. This doesn't include
1065  // LocalAsMetadata.
1066  incorporateFunctionMetadata(F);
1067 
1068  // Adding function arguments to the value table.
1069  for (const auto &I : F.args()) {
1070  EnumerateValue(&I);
1071  if (I.hasAttribute(Attribute::ByVal))
1072  EnumerateType(I.getParamByValType());
1073  else if (I.hasAttribute(Attribute::StructRet))
1074  EnumerateType(I.getParamStructRetType());
1075  else if (I.hasAttribute(Attribute::ByRef))
1076  EnumerateType(I.getParamByRefType());
1077  }
1078  FirstFuncConstantID = Values.size();
1079 
1080  // Add all function-level constants to the value table.
1081  for (const BasicBlock &BB : F) {
1082  for (const Instruction &I : BB) {
1083  for (const Use &OI : I.operands()) {
1084  if ((isa<Constant>(OI) && !isa<GlobalValue>(OI)) || isa<InlineAsm>(OI))
1085  EnumerateValue(OI);
1086  }
1087  if (auto *SVI = dyn_cast<ShuffleVectorInst>(&I))
1088  EnumerateValue(SVI->getShuffleMaskForBitcode());
1089  }
1090  BasicBlocks.push_back(&BB);
1091  ValueMap[&BB] = BasicBlocks.size();
1092  }
1093 
1094  // Optimize the constant layout.
1095  OptimizeConstants(FirstFuncConstantID, Values.size());
1096 
1097  // Add the function's parameter attributes so they are available for use in
1098  // the function's instruction.
1099  EnumerateAttributes(F.getAttributes());
1100 
1101  FirstInstID = Values.size();
1102 
1103  SmallVector<LocalAsMetadata *, 8> FnLocalMDVector;
1104  SmallVector<DIArgList *, 8> ArgListMDVector;
1105  // Add all of the instructions.
1106  for (const BasicBlock &BB : F) {
1107  for (const Instruction &I : BB) {
1108  for (const Use &OI : I.operands()) {
1109  if (auto *MD = dyn_cast<MetadataAsValue>(&OI)) {
1110  if (auto *Local = dyn_cast<LocalAsMetadata>(MD->getMetadata())) {
1111  // Enumerate metadata after the instructions they might refer to.
1112  FnLocalMDVector.push_back(Local);
1113  } else if (auto *ArgList = dyn_cast<DIArgList>(MD->getMetadata())) {
1114  ArgListMDVector.push_back(ArgList);
1115  for (ValueAsMetadata *VMD : ArgList->getArgs()) {
1116  if (auto *Local = dyn_cast<LocalAsMetadata>(VMD)) {
1117  // Enumerate metadata after the instructions they might refer
1118  // to.
1119  FnLocalMDVector.push_back(Local);
1120  }
1121  }
1122  }
1123  }
1124  }
1125 
1126  if (!I.getType()->isVoidTy())
1127  EnumerateValue(&I);
1128  }
1129  }
1130 
1131  // Add all of the function-local metadata.
1132  for (unsigned i = 0, e = FnLocalMDVector.size(); i != e; ++i) {
1133  // At this point, every local values have been incorporated, we shouldn't
1134  // have a metadata operand that references a value that hasn't been seen.
1135  assert(ValueMap.count(FnLocalMDVector[i]->getValue()) &&
1136  "Missing value for metadata operand");
1137  EnumerateFunctionLocalMetadata(F, FnLocalMDVector[i]);
1138  }
1139  // DIArgList entries must come after function-local metadata, as it is not
1140  // possible to forward-reference them.
1141  for (const DIArgList *ArgList : ArgListMDVector)
1142  EnumerateFunctionLocalListMetadata(F, ArgList);
1143 }
1144 
1146  /// Remove purged values from the ValueMap.
1147  for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i)
1148  ValueMap.erase(Values[i].first);
1149  for (unsigned i = NumModuleMDs, e = MDs.size(); i != e; ++i)
1150  MetadataMap.erase(MDs[i]);
1151  for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i)
1152  ValueMap.erase(BasicBlocks[i]);
1153 
1154  Values.resize(NumModuleValues);
1155  MDs.resize(NumModuleMDs);
1156  BasicBlocks.clear();
1157  NumMDStrings = 0;
1158 }
1159 
1162  unsigned Counter = 0;
1163  for (const BasicBlock &BB : *F)
1164  IDMap[&BB] = ++Counter;
1165 }
1166 
1167 /// getGlobalBasicBlockID - This returns the function-specific ID for the
1168 /// specified basic block. This is relatively expensive information, so it
1169 /// should only be used by rare constructs such as address-of-label.
1171  unsigned &Idx = GlobalBasicBlockIDs[BB];
1172  if (Idx != 0)
1173  return Idx-1;
1174 
1175  IncorporateFunctionInfoGlobalBBIDs(BB->getParent(), GlobalBasicBlockIDs);
1176  return getGlobalBasicBlockID(BB);
1177 }
1178 
1180  return Log2_32_Ceil(getTypes().size() + 1);
1181 }
i
i
Definition: README.txt:29
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
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:3604
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:491
MathExtras.h
GlobalIFunc.h
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
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:326
llvm::AArch64CC::AL
@ AL
Definition: AArch64BaseInfo.h:269
llvm::NamedMDNode
A tuple of MDNodes.
Definition: Metadata.h:1391
Metadata.h
llvm::NamedMDNode::getNumOperands
unsigned getNumOperands() const
Definition: Metadata.cpp:1120
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:61
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:197
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
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:262
llvm::GlobalVariable
Definition: GlobalVariable.h:40
llvm::GlobalAlias
Definition: GlobalAlias.h:27
push
static void push(SmallVectorImpl< uint64_t > &R, StringRef Str)
Definition: BitstreamRemarkSerializer.cpp:23
llvm::DenseMapBase::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:302
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1580
llvm::DenseMapIterator
Definition: DenseMap.h:56
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::AttributeList
Definition: Attributes.h:398
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:145
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:892
llvm::LocalAsMetadata
Definition: Metadata.h:436
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
Use.h
llvm::AttributeList::index_end
unsigned index_end() const
Definition: Attributes.h:856
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:56
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:193
llvm::MDNode::operands
op_range operands() const
Definition: Metadata.h:1105
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Instruction.h
llvm::Type::getMetadataTy
static Type * getMetadataTy(LLVMContext &C)
Definition: Type.cpp:192
llvm::ValueEnumerator::getInstructionID
unsigned getInstructionID(const Instruction *I) const
Definition: ValueEnumerator.cpp:506
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
llvm::AttributeList::index_begin
unsigned index_begin() const
Use these to iterate over the valid attribute indices.
Definition: Attributes.h:855
orderValue
static void orderValue(const Value *V, OrderMap &OM)
Definition: ValueEnumerator.cpp:82
llvm::ValueEnumerator::computeBitsRequiredForTypeIndicies
uint64_t computeBitsRequiredForTypeIndicies() const
Definition: ValueEnumerator.cpp:1179
llvm::StringMapConstIterator
Definition: StringMap.h:24
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:377
IncorporateFunctionInfoGlobalBBIDs
static void IncorporateFunctionInfoGlobalBBIDs(const Function *F, DenseMap< const BasicBlock *, unsigned > &IDMap)
Definition: ValueEnumerator.cpp:1160
llvm::Instruction
Definition: Instruction.h:45
llvm::AttributeList::getAttributes
AttributeSet getAttributes(unsigned Index) const
The attributes for the specified index are returned.
Definition: Attributes.cpp:1496
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::Comdat
Definition: Comdat.h:31
llvm::Metadata
Root of the metadata hierarchy.
Definition: Metadata.h:62
llvm::ValueEnumerator::getValueID
unsigned getValueID(const Value *V) const
Definition: ValueEnumerator.cpp:522
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:540
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:345
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:609
ValueSymbolTable.h
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
llvm::Type::subtypes
ArrayRef< Type * > subtypes() const
Definition: Type.h:332
BasicBlock.h
VI
@ VI
Definition: SIInstrInfo.cpp:7679
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
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:68
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
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:59
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:4598
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:1124
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:840
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:1060
llvm::DIArgList::getArgs
ArrayRef< ValueAsMetadata * > getArgs() const
Definition: DebugInfoMetadata.h:3636
llvm::Value::use_begin
use_iterator use_begin()
Definition: Value.h:361
llvm::Type::isVoidTy
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:138
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:67
llvm::MDNode
Metadata node.
Definition: Metadata.h:901
llvm::ValueEnumerator::dump
void dump() const
Definition: ValueEnumerator.cpp:532
llvm::Metadata::print
void print(raw_ostream &OS, const Module *M=nullptr, bool IsForDebug=false) const
Print.
Definition: AsmWriter.cpp:4727
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:1528
llvm::ValueEnumerator::setInstructionID
void setInstructionID(const Instruction *I)
Definition: ValueEnumerator.cpp:518
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:256
llvm::Value::getNumUses
unsigned getNumUses() const
This method computes the number of uses of this Value.
Definition: Value.cpp:243
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:369
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:297
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
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:1574
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:1682
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:83
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
GlobalVariable.h
Casting.h
isIntOrIntVectorValue
static bool isIntOrIntVectorValue(const std::pair< const Value *, unsigned > &V)
Definition: ValueEnumerator.cpp:360
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:100
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1488
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:1618
llvm::ValueMap::find
iterator find(const KeyT &Val)
Definition: ValueMap.h:156
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
GlobalAlias.h
llvm::ValueEnumerator::getComdatID
unsigned getComdatID(const Comdat *C) const
Definition: ValueEnumerator.cpp:512
llvm::ValueEnumerator::getGlobalBasicBlockID
unsigned getGlobalBasicBlockID(const BasicBlock *BB) const
getGlobalBasicBlockID - This returns the function-specific ID for the specified basic block.
Definition: ValueEnumerator.cpp:1170
llvm::AttributeList::FunctionIndex
@ FunctionIndex
Definition: Attributes.h:402
Instructions.h
llvm::AttributeSet
Definition: Attributes.h:266
llvm::ValueEnumerator::ValueEnumerator
ValueEnumerator(const Module &M, bool ShouldPreserveUseListOrder)
Definition: ValueEnumerator.cpp:364
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:201
N
#define N
llvm::ValueAsMetadata
Value wrapper in the Metadata hierarchy.
Definition: Metadata.h:344
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:97
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:624
llvm::ValueEnumerator::purgeFunction
void purgeFunction()
Definition: ValueEnumerator.cpp:1145
Value.h
llvm::GlobalIFunc
Definition: GlobalIFunc.h:32
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
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:868
llvm::MDOperand
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:748
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37