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