1//===-- ValueEnumerator.cpp - Number values and types for bitcode writer --===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the ValueEnumerator class.
11//
12//===----------------------------------------------------------------------===//
13
14#include "ValueEnumerator.h"
15#include "llvm/ADT/STLExtras.h"
16#include "llvm/ADT/SmallPtrSet.h"
17#include "llvm/IR/Constants.h"
18#include "llvm/IR/DebugInfoMetadata.h"
19#include "llvm/IR/DerivedTypes.h"
20#include "llvm/IR/Instructions.h"
21#include "llvm/IR/Module.h"
22#include "llvm/IR/UseListOrder.h"
23#include "llvm/IR/ValueSymbolTable.h"
24#include "llvm/Support/Debug.h"
25#include "llvm/Support/raw_ostream.h"
26#include <algorithm>
27using namespace llvm;
28
29namespace {
30struct OrderMap {
31  DenseMap<const Value *, std::pair<unsigned, bool>> IDs;
32  unsigned LastGlobalConstantID;
33  unsigned LastGlobalValueID;
34
35  OrderMap() : LastGlobalConstantID(0), LastGlobalValueID(0) {}
36
37  bool isGlobalConstant(unsigned ID) const {
38    return ID <= LastGlobalConstantID;
39  }
40  bool isGlobalValue(unsigned ID) const {
41    return ID <= LastGlobalValueID && !isGlobalConstant(ID);
42  }
43
44  unsigned size() const { return IDs.size(); }
45  std::pair<unsigned, bool> &operator[](const Value *V) { return IDs[V]; }
46  std::pair<unsigned, bool> lookup(const Value *V) const {
47    return IDs.lookup(V);
48  }
49  void index(const Value *V) {
50    // Explicitly sequence get-size and insert-value operations to avoid UB.
51    unsigned ID = IDs.size() + 1;
52    IDs[V].first = ID;
53  }
54};
55}
56
57static void orderValue(const Value *V, OrderMap &OM) {
58  if (OM.lookup(V).first)
59    return;
60
61  if (const Constant *C = dyn_cast<Constant>(V))
62    if (C->getNumOperands() && !isa<GlobalValue>(C))
63      for (const Value *Op : C->operands())
64        if (!isa<BasicBlock>(Op) && !isa<GlobalValue>(Op))
65          orderValue(Op, OM);
66
67  // Note: we cannot cache this lookup above, since inserting into the map
68  // changes the map's size, and thus affects the other IDs.
69  OM.index(V);
70}
71
72static OrderMap orderModule(const Module &M) {
73  // This needs to match the order used by ValueEnumerator::ValueEnumerator()
74  // and ValueEnumerator::incorporateFunction().
75  OrderMap OM;
76
77  // In the reader, initializers of GlobalValues are set *after* all the
78  // globals have been read.  Rather than awkwardly modeling this behaviour
79  // directly in predictValueUseListOrderImpl(), just assign IDs to
80  // initializers of GlobalValues before GlobalValues themselves to model this
81  // implicitly.
82  for (const GlobalVariable &G : M.globals())
83    if (G.hasInitializer())
84      if (!isa<GlobalValue>(G.getInitializer()))
85        orderValue(G.getInitializer(), OM);
86  for (const GlobalAlias &A : M.aliases())
87    if (!isa<GlobalValue>(A.getAliasee()))
88      orderValue(A.getAliasee(), OM);
89  for (const Function &F : M) {
90    for (const Use &U : F.operands())
91      if (!isa<GlobalValue>(U.get()))
92        orderValue(U.get(), OM);
93  }
94  OM.LastGlobalConstantID = OM.size();
95
96  // Initializers of GlobalValues are processed in
97  // BitcodeReader::ResolveGlobalAndAliasInits().  Match the order there rather
98  // than ValueEnumerator, and match the code in predictValueUseListOrderImpl()
99  // by giving IDs in reverse order.
100  //
101  // Since GlobalValues never reference each other directly (just through
102  // initializers), their relative IDs only matter for determining order of
103  // uses in their initializers.
104  for (const Function &F : M)
105    orderValue(&F, OM);
106  for (const GlobalAlias &A : M.aliases())
107    orderValue(&A, OM);
108  for (const GlobalVariable &G : M.globals())
109    orderValue(&G, OM);
110  OM.LastGlobalValueID = OM.size();
111
112  for (const Function &F : M) {
113    if (F.isDeclaration())
114      continue;
115    // Here we need to match the union of ValueEnumerator::incorporateFunction()
116    // and WriteFunction().  Basic blocks are implicitly declared before
117    // anything else (by declaring their size).
118    for (const BasicBlock &BB : F)
119      orderValue(&BB, OM);
120    for (const Argument &A : F.args())
121      orderValue(&A, OM);
122    for (const BasicBlock &BB : F)
123      for (const Instruction &I : BB)
124        for (const Value *Op : I.operands())
125          if ((isa<Constant>(*Op) && !isa<GlobalValue>(*Op)) ||
126              isa<InlineAsm>(*Op))
127            orderValue(Op, OM);
128    for (const BasicBlock &BB : F)
129      for (const Instruction &I : BB)
130        orderValue(&I, OM);
131  }
132  return OM;
133}
134
135static void predictValueUseListOrderImpl(const Value *V, const Function *F,
136                                         unsigned ID, const OrderMap &OM,
137                                         UseListOrderStack &Stack) {
138  // Predict use-list order for this one.
139  typedef std::pair<const Use *, unsigned> Entry;
140  SmallVector<Entry, 64> List;
141  for (const Use &U : V->uses())
142    // Check if this user will be serialized.
143    if (OM.lookup(U.getUser()).first)
144      List.push_back(std::make_pair(&U, List.size()));
145
146  if (List.size() < 2)
147    // We may have lost some users.
148    return;
149
150  bool IsGlobalValue = OM.isGlobalValue(ID);
151  std::sort(List.begin(), List.end(), [&](const Entry &L, const Entry &R) {
152    const Use *LU = L.first;
153    const Use *RU = R.first;
154    if (LU == RU)
155      return false;
156
157    auto LID = OM.lookup(LU->getUser()).first;
158    auto RID = OM.lookup(RU->getUser()).first;
159
160    // Global values are processed in reverse order.
161    //
162    // Moreover, initializers of GlobalValues are set *after* all the globals
163    // have been read (despite having earlier IDs).  Rather than awkwardly
164    // modeling this behaviour here, orderModule() has assigned IDs to
165    // initializers of GlobalValues before GlobalValues themselves.
166    if (OM.isGlobalValue(LID) && OM.isGlobalValue(RID))
167      return LID < RID;
168
169    // If ID is 4, then expect: 7 6 5 1 2 3.
170    if (LID < RID) {
171      if (RID <= ID)
172        if (!IsGlobalValue) // GlobalValue uses don't get reversed.
173          return true;
174      return false;
175    }
176    if (RID < LID) {
177      if (LID <= ID)
178        if (!IsGlobalValue) // GlobalValue uses don't get reversed.
179          return false;
180      return true;
181    }
182
183    // LID and RID are equal, so we have different operands of the same user.
184    // Assume operands are added in order for all instructions.
185    if (LID <= ID)
186      if (!IsGlobalValue) // GlobalValue uses don't get reversed.
187        return LU->getOperandNo() < RU->getOperandNo();
188    return LU->getOperandNo() > RU->getOperandNo();
189  });
190
191  if (std::is_sorted(
192          List.begin(), List.end(),
193          [](const Entry &L, const Entry &R) { return L.second < R.second; }))
194    // Order is already correct.
195    return;
196
197  // Store the shuffle.
198  Stack.emplace_back(V, F, List.size());
199  assert(List.size() == Stack.back().Shuffle.size() && "Wrong size");
200  for (size_t I = 0, E = List.size(); I != E; ++I)
201    Stack.back().Shuffle[I] = List[I].second;
202}
203
204static void predictValueUseListOrder(const Value *V, const Function *F,
205                                     OrderMap &OM, UseListOrderStack &Stack) {
206  auto &IDPair = OM[V];
207  assert(IDPair.first && "Unmapped value");
208  if (IDPair.second)
209    // Already predicted.
210    return;
211
212  // Do the actual prediction.
213  IDPair.second = true;
214  if (!V->use_empty() && std::next(V->use_begin()) != V->use_end())
215    predictValueUseListOrderImpl(V, F, IDPair.first, OM, Stack);
216
217  // Recursive descent into constants.
218  if (const Constant *C = dyn_cast<Constant>(V))
219    if (C->getNumOperands()) // Visit GlobalValues.
220      for (const Value *Op : C->operands())
221        if (isa<Constant>(Op)) // Visit GlobalValues.
222          predictValueUseListOrder(Op, F, OM, Stack);
223}
224
225static UseListOrderStack predictUseListOrder(const Module &M) {
226  OrderMap OM = orderModule(M);
227
228  // Use-list orders need to be serialized after all the users have been added
229  // to a value, or else the shuffles will be incomplete.  Store them per
230  // function in a stack.
231  //
232  // Aside from function order, the order of values doesn't matter much here.
233  UseListOrderStack Stack;
234
235  // We want to visit the functions backward now so we can list function-local
236  // constants in the last Function they're used in.  Module-level constants
237  // have already been visited above.
238  for (auto I = M.rbegin(), E = M.rend(); I != E; ++I) {
239    const Function &F = *I;
240    if (F.isDeclaration())
241      continue;
242    for (const BasicBlock &BB : F)
243      predictValueUseListOrder(&BB, &F, OM, Stack);
244    for (const Argument &A : F.args())
245      predictValueUseListOrder(&A, &F, OM, Stack);
246    for (const BasicBlock &BB : F)
247      for (const Instruction &I : BB)
248        for (const Value *Op : I.operands())
249          if (isa<Constant>(*Op) || isa<InlineAsm>(*Op)) // Visit GlobalValues.
250            predictValueUseListOrder(Op, &F, OM, Stack);
251    for (const BasicBlock &BB : F)
252      for (const Instruction &I : BB)
253        predictValueUseListOrder(&I, &F, OM, Stack);
254  }
255
256  // Visit globals last, since the module-level use-list block will be seen
257  // before the function bodies are processed.
258  for (const GlobalVariable &G : M.globals())
259    predictValueUseListOrder(&G, nullptr, OM, Stack);
260  for (const Function &F : M)
261    predictValueUseListOrder(&F, nullptr, OM, Stack);
262  for (const GlobalAlias &A : M.aliases())
263    predictValueUseListOrder(&A, nullptr, OM, Stack);
264  for (const GlobalVariable &G : M.globals())
265    if (G.hasInitializer())
266      predictValueUseListOrder(G.getInitializer(), nullptr, OM, Stack);
267  for (const GlobalAlias &A : M.aliases())
268    predictValueUseListOrder(A.getAliasee(), nullptr, OM, Stack);
269  for (const Function &F : M) {
270    for (const Use &U : F.operands())
271      predictValueUseListOrder(U.get(), nullptr, OM, Stack);
272  }
273
274  return Stack;
275}
276
277static bool isIntOrIntVectorValue(const std::pair<const Value*, unsigned> &V) {
278  return V.first->getType()->isIntOrIntVectorTy();
279}
280
281ValueEnumerator::ValueEnumerator(const Module &M,
282                                 bool ShouldPreserveUseListOrder)
283    : HasMDString(false), HasDILocation(false), HasGenericDINode(false),
284      ShouldPreserveUseListOrder(ShouldPreserveUseListOrder) {
285  if (ShouldPreserveUseListOrder)
286    UseListOrders = predictUseListOrder(M);
287
288  // Enumerate the global variables.
289  for (const GlobalVariable &GV : M.globals())
290    EnumerateValue(&GV);
291
292  // Enumerate the functions.
293  for (const Function & F : M) {
294    EnumerateValue(&F);
295    EnumerateAttributes(F.getAttributes());
296  }
297
298  // Enumerate the aliases.
299  for (const GlobalAlias &GA : M.aliases())
300    EnumerateValue(&GA);
301
302  // Remember what is the cutoff between globalvalue's and other constants.
303  unsigned FirstConstant = Values.size();
304
305  // Enumerate the global variable initializers.
306  for (const GlobalVariable &GV : M.globals())
307    if (GV.hasInitializer())
308      EnumerateValue(GV.getInitializer());
309
310  // Enumerate the aliasees.
311  for (const GlobalAlias &GA : M.aliases())
312    EnumerateValue(GA.getAliasee());
313
314  // Enumerate any optional Function data.
315  for (const Function &F : M)
316    for (const Use &U : F.operands())
317      EnumerateValue(U.get());
318
319  // Enumerate the metadata type.
320  //
321  // TODO: Move this to ValueEnumerator::EnumerateOperandType() once bitcode
322  // only encodes the metadata type when it's used as a value.
323  EnumerateType(Type::getMetadataTy(M.getContext()));
324
325  // Insert constants and metadata that are named at module level into the slot
326  // pool so that the module symbol table can refer to them...
327  EnumerateValueSymbolTable(M.getValueSymbolTable());
328  EnumerateNamedMetadata(M);
329
330  SmallVector<std::pair<unsigned, MDNode *>, 8> MDs;
331
332  // Enumerate types used by function bodies and argument lists.
333  for (const Function &F : M) {
334    for (const Argument &A : F.args())
335      EnumerateType(A.getType());
336
337    // Enumerate metadata attached to this function.
338    F.getAllMetadata(MDs);
339    for (const auto &I : MDs)
340      EnumerateMetadata(I.second);
341
342    for (const BasicBlock &BB : F)
343      for (const Instruction &I : BB) {
344        for (const Use &Op : I.operands()) {
345          auto *MD = dyn_cast<MetadataAsValue>(&Op);
346          if (!MD) {
347            EnumerateOperandType(Op);
348            continue;
349          }
350
351          // Local metadata is enumerated during function-incorporation.
352          if (isa<LocalAsMetadata>(MD->getMetadata()))
353            continue;
354
355          EnumerateMetadata(MD->getMetadata());
356        }
357        EnumerateType(I.getType());
358        if (const CallInst *CI = dyn_cast<CallInst>(&I))
359          EnumerateAttributes(CI->getAttributes());
360        else if (const InvokeInst *II = dyn_cast<InvokeInst>(&I))
361          EnumerateAttributes(II->getAttributes());
362
363        // Enumerate metadata attached with this instruction.
364        MDs.clear();
365        I.getAllMetadataOtherThanDebugLoc(MDs);
366        for (unsigned i = 0, e = MDs.size(); i != e; ++i)
367          EnumerateMetadata(MDs[i].second);
368
369        // Don't enumerate the location directly -- it has a special record
370        // type -- but enumerate its operands.
371        if (DILocation *L = I.getDebugLoc())
372          EnumerateMDNodeOperands(L);
373      }
374  }
375
376  // Optimize constant ordering.
377  OptimizeConstants(FirstConstant, Values.size());
378}
379
380unsigned ValueEnumerator::getInstructionID(const Instruction *Inst) const {
381  InstructionMapType::const_iterator I = InstructionMap.find(Inst);
382  assert(I != InstructionMap.end() && "Instruction is not mapped!");
383  return I->second;
384}
385
386unsigned ValueEnumerator::getComdatID(const Comdat *C) const {
387  unsigned ComdatID = Comdats.idFor(C);
388  assert(ComdatID && "Comdat not found!");
389  return ComdatID;
390}
391
392void ValueEnumerator::setInstructionID(const Instruction *I) {
393  InstructionMap[I] = InstructionCount++;
394}
395
396unsigned ValueEnumerator::getValueID(const Value *V) const {
397  if (auto *MD = dyn_cast<MetadataAsValue>(V))
398    return getMetadataID(MD->getMetadata());
399
400  ValueMapType::const_iterator I = ValueMap.find(V);
401  assert(I != ValueMap.end() && "Value not in slotcalculator!");
402  return I->second-1;
403}
404
405void ValueEnumerator::dump() const {
406  print(dbgs(), ValueMap, "Default");
407  dbgs() << '\n';
408  print(dbgs(), MetadataMap, "MetaData");
409  dbgs() << '\n';
410}
411
412void ValueEnumerator::print(raw_ostream &OS, const ValueMapType &Map,
413                            const char *Name) const {
414
415  OS << "Map Name: " << Name << "\n";
416  OS << "Size: " << Map.size() << "\n";
417  for (ValueMapType::const_iterator I = Map.begin(),
418         E = Map.end(); I != E; ++I) {
419
420    const Value *V = I->first;
421    if (V->hasName())
422      OS << "Value: " << V->getName();
423    else
424      OS << "Value: [null]\n";
425    V->dump();
426
427    OS << " Uses(" << std::distance(V->use_begin(),V->use_end()) << "):";
428    for (const Use &U : V->uses()) {
429      if (&U != &*V->use_begin())
430        OS << ",";
431      if(U->hasName())
432        OS << " " << U->getName();
433      else
434        OS << " [null]";
435
436    }
437    OS <<  "\n\n";
438  }
439}
440
441void ValueEnumerator::print(raw_ostream &OS, const MetadataMapType &Map,
442                            const char *Name) const {
443
444  OS << "Map Name: " << Name << "\n";
445  OS << "Size: " << Map.size() << "\n";
446  for (auto I = Map.begin(), E = Map.end(); I != E; ++I) {
447    const Metadata *MD = I->first;
448    OS << "Metadata: slot = " << I->second << "\n";
449    MD->print(OS);
450  }
451}
452
453/// OptimizeConstants - Reorder constant pool for denser encoding.
454void ValueEnumerator::OptimizeConstants(unsigned CstStart, unsigned CstEnd) {
455  if (CstStart == CstEnd || CstStart+1 == CstEnd) return;
456
457  if (ShouldPreserveUseListOrder)
458    // Optimizing constants makes the use-list order difficult to predict.
459    // Disable it for now when trying to preserve the order.
460    return;
461
462  std::stable_sort(Values.begin() + CstStart, Values.begin() + CstEnd,
463                   [this](const std::pair<const Value *, unsigned> &LHS,
464                          const std::pair<const Value *, unsigned> &RHS) {
465    // Sort by plane.
466    if (LHS.first->getType() != RHS.first->getType())
467      return getTypeID(LHS.first->getType()) < getTypeID(RHS.first->getType());
468    // Then by frequency.
469    return LHS.second > RHS.second;
470  });
471
472  // Ensure that integer and vector of integer constants are at the start of the
473  // constant pool.  This is important so that GEP structure indices come before
474  // gep constant exprs.
475  std::partition(Values.begin()+CstStart, Values.begin()+CstEnd,
476                 isIntOrIntVectorValue);
477
478  // Rebuild the modified portion of ValueMap.
479  for (; CstStart != CstEnd; ++CstStart)
480    ValueMap[Values[CstStart].first] = CstStart+1;
481}
482
483
484/// EnumerateValueSymbolTable - Insert all of the values in the specified symbol
485/// table into the values table.
486void ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) {
487  for (ValueSymbolTable::const_iterator VI = VST.begin(), VE = VST.end();
488       VI != VE; ++VI)
489    EnumerateValue(VI->getValue());
490}
491
492/// Insert all of the values referenced by named metadata in the specified
493/// module.
494void ValueEnumerator::EnumerateNamedMetadata(const Module &M) {
495  for (const auto &I : M.named_metadata())
496    EnumerateNamedMDNode(&I);
497}
498
499void ValueEnumerator::EnumerateNamedMDNode(const NamedMDNode *MD) {
500  for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i)
501    EnumerateMetadata(MD->getOperand(i));
502}
503
504/// EnumerateMDNodeOperands - Enumerate all non-function-local values
505/// and types referenced by the given MDNode.
506void ValueEnumerator::EnumerateMDNodeOperands(const MDNode *N) {
507  for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
508    Metadata *MD = N->getOperand(i);
509    if (!MD)
510      continue;
511    assert(!isa<LocalAsMetadata>(MD) && "MDNodes cannot be function-local");
512    EnumerateMetadata(MD);
513  }
514}
515
516void ValueEnumerator::EnumerateMetadata(const Metadata *MD) {
517  assert(
518      (isa<MDNode>(MD) || isa<MDString>(MD) || isa<ConstantAsMetadata>(MD)) &&
519      "Invalid metadata kind");
520
521  // Insert a dummy ID to block the co-recursive call to
522  // EnumerateMDNodeOperands() from re-visiting MD in a cyclic graph.
523  //
524  // Return early if there's already an ID.
525  if (!MetadataMap.insert(std::make_pair(MD, 0)).second)
526    return;
527
528  // Visit operands first to minimize RAUW.
529  if (auto *N = dyn_cast<MDNode>(MD))
530    EnumerateMDNodeOperands(N);
531  else if (auto *C = dyn_cast<ConstantAsMetadata>(MD))
532    EnumerateValue(C->getValue());
533
534  HasMDString |= isa<MDString>(MD);
535  HasDILocation |= isa<DILocation>(MD);
536  HasGenericDINode |= isa<GenericDINode>(MD);
537
538  // Replace the dummy ID inserted above with the correct one.  MetadataMap may
539  // have changed by inserting operands, so we need a fresh lookup here.
540  MDs.push_back(MD);
541  MetadataMap[MD] = MDs.size();
542}
543
544/// EnumerateFunctionLocalMetadataa - Incorporate function-local metadata
545/// information reachable from the metadata.
546void ValueEnumerator::EnumerateFunctionLocalMetadata(
547    const LocalAsMetadata *Local) {
548  // Check to see if it's already in!
549  unsigned &MetadataID = MetadataMap[Local];
550  if (MetadataID)
551    return;
552
553  MDs.push_back(Local);
554  MetadataID = MDs.size();
555
556  EnumerateValue(Local->getValue());
557
558  // Also, collect all function-local metadata for easy access.
559  FunctionLocalMDs.push_back(Local);
560}
561
562void ValueEnumerator::EnumerateValue(const Value *V) {
563  assert(!V->getType()->isVoidTy() && "Can't insert void values!");
564  assert(!isa<MetadataAsValue>(V) && "EnumerateValue doesn't handle Metadata!");
565
566  // Check to see if it's already in!
567  unsigned &ValueID = ValueMap[V];
568  if (ValueID) {
569    // Increment use count.
570    Values[ValueID-1].second++;
571    return;
572  }
573
574  if (auto *GO = dyn_cast<GlobalObject>(V))
575    if (const Comdat *C = GO->getComdat())
576      Comdats.insert(C);
577
578  // Enumerate the type of this value.
579  EnumerateType(V->getType());
580
581  if (const Constant *C = dyn_cast<Constant>(V)) {
582    if (isa<GlobalValue>(C)) {
583      // Initializers for globals are handled explicitly elsewhere.
584    } else if (C->getNumOperands()) {
585      // If a constant has operands, enumerate them.  This makes sure that if a
586      // constant has uses (for example an array of const ints), that they are
587      // inserted also.
588
589      // We prefer to enumerate them with values before we enumerate the user
590      // itself.  This makes it more likely that we can avoid forward references
591      // in the reader.  We know that there can be no cycles in the constants
592      // graph that don't go through a global variable.
593      for (User::const_op_iterator I = C->op_begin(), E = C->op_end();
594           I != E; ++I)
595        if (!isa<BasicBlock>(*I)) // Don't enumerate BB operand to BlockAddress.
596          EnumerateValue(*I);
597
598      // Finally, add the value.  Doing this could make the ValueID reference be
599      // dangling, don't reuse it.
600      Values.push_back(std::make_pair(V, 1U));
601      ValueMap[V] = Values.size();
602      return;
603    }
604  }
605
606  // Add the value.
607  Values.push_back(std::make_pair(V, 1U));
608  ValueID = Values.size();
609}
610
611
612void ValueEnumerator::EnumerateType(Type *Ty) {
613  unsigned *TypeID = &TypeMap[Ty];
614
615  // We've already seen this type.
616  if (*TypeID)
617    return;
618
619  // If it is a non-anonymous struct, mark the type as being visited so that we
620  // don't recursively visit it.  This is safe because we allow forward
621  // references of these in the bitcode reader.
622  if (StructType *STy = dyn_cast<StructType>(Ty))
623    if (!STy->isLiteral())
624      *TypeID = ~0U;
625
626  // Enumerate all of the subtypes before we enumerate this type.  This ensures
627  // that the type will be enumerated in an order that can be directly built.
628  for (Type *SubTy : Ty->subtypes())
629    EnumerateType(SubTy);
630
631  // Refresh the TypeID pointer in case the table rehashed.
632  TypeID = &TypeMap[Ty];
633
634  // Check to see if we got the pointer another way.  This can happen when
635  // enumerating recursive types that hit the base case deeper than they start.
636  //
637  // If this is actually a struct that we are treating as forward ref'able,
638  // then emit the definition now that all of its contents are available.
639  if (*TypeID && *TypeID != ~0U)
640    return;
641
642  // Add this type now that its contents are all happily enumerated.
643  Types.push_back(Ty);
644
645  *TypeID = Types.size();
646}
647
648// Enumerate the types for the specified value.  If the value is a constant,
649// walk through it, enumerating the types of the constant.
650void ValueEnumerator::EnumerateOperandType(const Value *V) {
651  EnumerateType(V->getType());
652
653  if (auto *MD = dyn_cast<MetadataAsValue>(V)) {
654    assert(!isa<LocalAsMetadata>(MD->getMetadata()) &&
655           "Function-local metadata should be left for later");
656
657    EnumerateMetadata(MD->getMetadata());
658    return;
659  }
660
661  const Constant *C = dyn_cast<Constant>(V);
662  if (!C)
663    return;
664
665  // If this constant is already enumerated, ignore it, we know its type must
666  // be enumerated.
667  if (ValueMap.count(C))
668    return;
669
670  // This constant may have operands, make sure to enumerate the types in
671  // them.
672  for (const Value *Op : C->operands()) {
673    // Don't enumerate basic blocks here, this happens as operands to
674    // blockaddress.
675    if (isa<BasicBlock>(Op))
676      continue;
677
678    EnumerateOperandType(Op);
679  }
680}
681
682void ValueEnumerator::EnumerateAttributes(AttributeSet PAL) {
683  if (PAL.isEmpty()) return;  // null is always 0.
684
685  // Do a lookup.
686  unsigned &Entry = AttributeMap[PAL];
687  if (Entry == 0) {
688    // Never saw this before, add it.
689    Attribute.push_back(PAL);
690    Entry = Attribute.size();
691  }
692
693  // Do lookups for all attribute groups.
694  for (unsigned i = 0, e = PAL.getNumSlots(); i != e; ++i) {
695    AttributeSet AS = PAL.getSlotAttributes(i);
696    unsigned &Entry = AttributeGroupMap[AS];
697    if (Entry == 0) {
698      AttributeGroups.push_back(AS);
699      Entry = AttributeGroups.size();
700    }
701  }
702}
703
704void ValueEnumerator::incorporateFunction(const Function &F) {
705  InstructionCount = 0;
706  NumModuleValues = Values.size();
707  NumModuleMDs = MDs.size();
708
709  // Adding function arguments to the value table.
710  for (const auto &I : F.args())
711    EnumerateValue(&I);
712
713  FirstFuncConstantID = Values.size();
714
715  // Add all function-level constants to the value table.
716  for (const BasicBlock &BB : F) {
717    for (const Instruction &I : BB)
718      for (const Use &OI : I.operands()) {
719        if ((isa<Constant>(OI) && !isa<GlobalValue>(OI)) || isa<InlineAsm>(OI))
720          EnumerateValue(OI);
721      }
722    BasicBlocks.push_back(&BB);
723    ValueMap[&BB] = BasicBlocks.size();
724  }
725
726  // Optimize the constant layout.
727  OptimizeConstants(FirstFuncConstantID, Values.size());
728
729  // Add the function's parameter attributes so they are available for use in
730  // the function's instruction.
731  EnumerateAttributes(F.getAttributes());
732
733  FirstInstID = Values.size();
734
735  SmallVector<LocalAsMetadata *, 8> FnLocalMDVector;
736  // Add all of the instructions.
737  for (const BasicBlock &BB : F) {
738    for (const Instruction &I : BB) {
739      for (const Use &OI : I.operands()) {
740        if (auto *MD = dyn_cast<MetadataAsValue>(&OI))
741          if (auto *Local = dyn_cast<LocalAsMetadata>(MD->getMetadata()))
742            // Enumerate metadata after the instructions they might refer to.
743            FnLocalMDVector.push_back(Local);
744      }
745
746      if (!I.getType()->isVoidTy())
747        EnumerateValue(&I);
748    }
749  }
750
751  // Add all of the function-local metadata.
752  for (unsigned i = 0, e = FnLocalMDVector.size(); i != e; ++i)
753    EnumerateFunctionLocalMetadata(FnLocalMDVector[i]);
754}
755
756void ValueEnumerator::purgeFunction() {
757  /// Remove purged values from the ValueMap.
758  for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i)
759    ValueMap.erase(Values[i].first);
760  for (unsigned i = NumModuleMDs, e = MDs.size(); i != e; ++i)
761    MetadataMap.erase(MDs[i]);
762  for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i)
763    ValueMap.erase(BasicBlocks[i]);
764
765  Values.resize(NumModuleValues);
766  MDs.resize(NumModuleMDs);
767  BasicBlocks.clear();
768  FunctionLocalMDs.clear();
769}
770
771static void IncorporateFunctionInfoGlobalBBIDs(const Function *F,
772                                 DenseMap<const BasicBlock*, unsigned> &IDMap) {
773  unsigned Counter = 0;
774  for (const BasicBlock &BB : *F)
775    IDMap[&BB] = ++Counter;
776}
777
778/// getGlobalBasicBlockID - This returns the function-specific ID for the
779/// specified basic block.  This is relatively expensive information, so it
780/// should only be used by rare constructs such as address-of-label.
781unsigned ValueEnumerator::getGlobalBasicBlockID(const BasicBlock *BB) const {
782  unsigned &Idx = GlobalBasicBlockIDs[BB];
783  if (Idx != 0)
784    return Idx-1;
785
786  IncorporateFunctionInfoGlobalBBIDs(BB->getParent(), GlobalBasicBlockIDs);
787  return getGlobalBasicBlockID(BB);
788}
789
790uint64_t ValueEnumerator::computeBitsRequiredForTypeIndicies() const {
791  return Log2_32_Ceil(getTypes().size() + 1);
792}
793