]> CyberLeo.Net >> Repos - FreeBSD/FreeBSD.git/blob - contrib/llvm/lib/Bitcode/Writer/ValueEnumerator.cpp
MFV r316083,316094:
[FreeBSD/FreeBSD.git] / contrib / llvm / lib / Bitcode / Writer / ValueEnumerator.cpp
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>
27 using namespace llvm;
28
29 namespace {
30 struct 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
57 static 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
72 static 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 GlobalIFunc &I : M.ifuncs())
90     if (!isa<GlobalValue>(I.getResolver()))
91       orderValue(I.getResolver(), OM);
92   for (const Function &F : M) {
93     for (const Use &U : F.operands())
94       if (!isa<GlobalValue>(U.get()))
95         orderValue(U.get(), OM);
96   }
97   OM.LastGlobalConstantID = OM.size();
98
99   // Initializers of GlobalValues are processed in
100   // BitcodeReader::ResolveGlobalAndAliasInits().  Match the order there rather
101   // than ValueEnumerator, and match the code in predictValueUseListOrderImpl()
102   // by giving IDs in reverse order.
103   //
104   // Since GlobalValues never reference each other directly (just through
105   // initializers), their relative IDs only matter for determining order of
106   // uses in their initializers.
107   for (const Function &F : M)
108     orderValue(&F, OM);
109   for (const GlobalAlias &A : M.aliases())
110     orderValue(&A, OM);
111   for (const GlobalIFunc &I : M.ifuncs())
112     orderValue(&I, OM);
113   for (const GlobalVariable &G : M.globals())
114     orderValue(&G, OM);
115   OM.LastGlobalValueID = OM.size();
116
117   for (const Function &F : M) {
118     if (F.isDeclaration())
119       continue;
120     // Here we need to match the union of ValueEnumerator::incorporateFunction()
121     // and WriteFunction().  Basic blocks are implicitly declared before
122     // anything else (by declaring their size).
123     for (const BasicBlock &BB : F)
124       orderValue(&BB, OM);
125     for (const Argument &A : F.args())
126       orderValue(&A, OM);
127     for (const BasicBlock &BB : F)
128       for (const Instruction &I : BB)
129         for (const Value *Op : I.operands())
130           if ((isa<Constant>(*Op) && !isa<GlobalValue>(*Op)) ||
131               isa<InlineAsm>(*Op))
132             orderValue(Op, OM);
133     for (const BasicBlock &BB : F)
134       for (const Instruction &I : BB)
135         orderValue(&I, OM);
136   }
137   return OM;
138 }
139
140 static void predictValueUseListOrderImpl(const Value *V, const Function *F,
141                                          unsigned ID, const OrderMap &OM,
142                                          UseListOrderStack &Stack) {
143   // Predict use-list order for this one.
144   typedef std::pair<const Use *, unsigned> Entry;
145   SmallVector<Entry, 64> List;
146   for (const Use &U : V->uses())
147     // Check if this user will be serialized.
148     if (OM.lookup(U.getUser()).first)
149       List.push_back(std::make_pair(&U, List.size()));
150
151   if (List.size() < 2)
152     // We may have lost some users.
153     return;
154
155   bool IsGlobalValue = OM.isGlobalValue(ID);
156   std::sort(List.begin(), List.end(), [&](const Entry &L, const Entry &R) {
157     const Use *LU = L.first;
158     const Use *RU = R.first;
159     if (LU == RU)
160       return false;
161
162     auto LID = OM.lookup(LU->getUser()).first;
163     auto RID = OM.lookup(RU->getUser()).first;
164
165     // Global values are processed in reverse order.
166     //
167     // Moreover, initializers of GlobalValues are set *after* all the globals
168     // have been read (despite having earlier IDs).  Rather than awkwardly
169     // modeling this behaviour here, orderModule() has assigned IDs to
170     // initializers of GlobalValues before GlobalValues themselves.
171     if (OM.isGlobalValue(LID) && OM.isGlobalValue(RID))
172       return LID < RID;
173
174     // If ID is 4, then expect: 7 6 5 1 2 3.
175     if (LID < RID) {
176       if (RID <= ID)
177         if (!IsGlobalValue) // GlobalValue uses don't get reversed.
178           return true;
179       return false;
180     }
181     if (RID < LID) {
182       if (LID <= ID)
183         if (!IsGlobalValue) // GlobalValue uses don't get reversed.
184           return false;
185       return true;
186     }
187
188     // LID and RID are equal, so we have different operands of the same user.
189     // Assume operands are added in order for all instructions.
190     if (LID <= ID)
191       if (!IsGlobalValue) // GlobalValue uses don't get reversed.
192         return LU->getOperandNo() < RU->getOperandNo();
193     return LU->getOperandNo() > RU->getOperandNo();
194   });
195
196   if (std::is_sorted(
197           List.begin(), List.end(),
198           [](const Entry &L, const Entry &R) { return L.second < R.second; }))
199     // Order is already correct.
200     return;
201
202   // Store the shuffle.
203   Stack.emplace_back(V, F, List.size());
204   assert(List.size() == Stack.back().Shuffle.size() && "Wrong size");
205   for (size_t I = 0, E = List.size(); I != E; ++I)
206     Stack.back().Shuffle[I] = List[I].second;
207 }
208
209 static void predictValueUseListOrder(const Value *V, const Function *F,
210                                      OrderMap &OM, UseListOrderStack &Stack) {
211   auto &IDPair = OM[V];
212   assert(IDPair.first && "Unmapped value");
213   if (IDPair.second)
214     // Already predicted.
215     return;
216
217   // Do the actual prediction.
218   IDPair.second = true;
219   if (!V->use_empty() && std::next(V->use_begin()) != V->use_end())
220     predictValueUseListOrderImpl(V, F, IDPair.first, OM, Stack);
221
222   // Recursive descent into constants.
223   if (const Constant *C = dyn_cast<Constant>(V))
224     if (C->getNumOperands()) // Visit GlobalValues.
225       for (const Value *Op : C->operands())
226         if (isa<Constant>(Op)) // Visit GlobalValues.
227           predictValueUseListOrder(Op, F, OM, Stack);
228 }
229
230 static UseListOrderStack predictUseListOrder(const Module &M) {
231   OrderMap OM = orderModule(M);
232
233   // Use-list orders need to be serialized after all the users have been added
234   // to a value, or else the shuffles will be incomplete.  Store them per
235   // function in a stack.
236   //
237   // Aside from function order, the order of values doesn't matter much here.
238   UseListOrderStack Stack;
239
240   // We want to visit the functions backward now so we can list function-local
241   // constants in the last Function they're used in.  Module-level constants
242   // have already been visited above.
243   for (auto I = M.rbegin(), E = M.rend(); I != E; ++I) {
244     const Function &F = *I;
245     if (F.isDeclaration())
246       continue;
247     for (const BasicBlock &BB : F)
248       predictValueUseListOrder(&BB, &F, OM, Stack);
249     for (const Argument &A : F.args())
250       predictValueUseListOrder(&A, &F, OM, Stack);
251     for (const BasicBlock &BB : F)
252       for (const Instruction &I : BB)
253         for (const Value *Op : I.operands())
254           if (isa<Constant>(*Op) || isa<InlineAsm>(*Op)) // Visit GlobalValues.
255             predictValueUseListOrder(Op, &F, OM, Stack);
256     for (const BasicBlock &BB : F)
257       for (const Instruction &I : BB)
258         predictValueUseListOrder(&I, &F, OM, Stack);
259   }
260
261   // Visit globals last, since the module-level use-list block will be seen
262   // before the function bodies are processed.
263   for (const GlobalVariable &G : M.globals())
264     predictValueUseListOrder(&G, nullptr, OM, Stack);
265   for (const Function &F : M)
266     predictValueUseListOrder(&F, nullptr, OM, Stack);
267   for (const GlobalAlias &A : M.aliases())
268     predictValueUseListOrder(&A, nullptr, OM, Stack);
269   for (const GlobalIFunc &I : M.ifuncs())
270     predictValueUseListOrder(&I, nullptr, OM, Stack);
271   for (const GlobalVariable &G : M.globals())
272     if (G.hasInitializer())
273       predictValueUseListOrder(G.getInitializer(), nullptr, OM, Stack);
274   for (const GlobalAlias &A : M.aliases())
275     predictValueUseListOrder(A.getAliasee(), nullptr, OM, Stack);
276   for (const GlobalIFunc &I : M.ifuncs())
277     predictValueUseListOrder(I.getResolver(), nullptr, OM, Stack);
278   for (const Function &F : M) {
279     for (const Use &U : F.operands())
280       predictValueUseListOrder(U.get(), nullptr, OM, Stack);
281   }
282
283   return Stack;
284 }
285
286 static bool isIntOrIntVectorValue(const std::pair<const Value*, unsigned> &V) {
287   return V.first->getType()->isIntOrIntVectorTy();
288 }
289
290 ValueEnumerator::ValueEnumerator(const Module &M,
291                                  bool ShouldPreserveUseListOrder)
292     : ShouldPreserveUseListOrder(ShouldPreserveUseListOrder) {
293   if (ShouldPreserveUseListOrder)
294     UseListOrders = predictUseListOrder(M);
295
296   // Enumerate the global variables.
297   for (const GlobalVariable &GV : M.globals())
298     EnumerateValue(&GV);
299
300   // Enumerate the functions.
301   for (const Function & F : M) {
302     EnumerateValue(&F);
303     EnumerateAttributes(F.getAttributes());
304   }
305
306   // Enumerate the aliases.
307   for (const GlobalAlias &GA : M.aliases())
308     EnumerateValue(&GA);
309
310   // Enumerate the ifuncs.
311   for (const GlobalIFunc &GIF : M.ifuncs())
312     EnumerateValue(&GIF);
313
314   // Remember what is the cutoff between globalvalue's and other constants.
315   unsigned FirstConstant = Values.size();
316
317   // Enumerate the global variable initializers.
318   for (const GlobalVariable &GV : M.globals())
319     if (GV.hasInitializer())
320       EnumerateValue(GV.getInitializer());
321
322   // Enumerate the aliasees.
323   for (const GlobalAlias &GA : M.aliases())
324     EnumerateValue(GA.getAliasee());
325
326   // Enumerate the ifunc resolvers.
327   for (const GlobalIFunc &GIF : M.ifuncs())
328     EnumerateValue(GIF.getResolver());
329
330   // Enumerate any optional Function data.
331   for (const Function &F : M)
332     for (const Use &U : F.operands())
333       EnumerateValue(U.get());
334
335   // Enumerate the metadata type.
336   //
337   // TODO: Move this to ValueEnumerator::EnumerateOperandType() once bitcode
338   // only encodes the metadata type when it's used as a value.
339   EnumerateType(Type::getMetadataTy(M.getContext()));
340
341   // Insert constants and metadata that are named at module level into the slot
342   // pool so that the module symbol table can refer to them...
343   EnumerateValueSymbolTable(M.getValueSymbolTable());
344   EnumerateNamedMetadata(M);
345
346   SmallVector<std::pair<unsigned, MDNode *>, 8> MDs;
347   for (const GlobalVariable &GV : M.globals()) {
348     MDs.clear();
349     GV.getAllMetadata(MDs);
350     for (const auto &I : MDs)
351       // FIXME: Pass GV to EnumerateMetadata and arrange for the bitcode writer
352       // to write metadata to the global variable's own metadata block
353       // (PR28134).
354       EnumerateMetadata(nullptr, I.second);
355   }
356
357   // Enumerate types used by function bodies and argument lists.
358   for (const Function &F : M) {
359     for (const Argument &A : F.args())
360       EnumerateType(A.getType());
361
362     // Enumerate metadata attached to this function.
363     MDs.clear();
364     F.getAllMetadata(MDs);
365     for (const auto &I : MDs)
366       EnumerateMetadata(F.isDeclaration() ? nullptr : &F, I.second);
367
368     for (const BasicBlock &BB : F)
369       for (const Instruction &I : BB) {
370         for (const Use &Op : I.operands()) {
371           auto *MD = dyn_cast<MetadataAsValue>(&Op);
372           if (!MD) {
373             EnumerateOperandType(Op);
374             continue;
375           }
376
377           // Local metadata is enumerated during function-incorporation.
378           if (isa<LocalAsMetadata>(MD->getMetadata()))
379             continue;
380
381           EnumerateMetadata(&F, MD->getMetadata());
382         }
383         EnumerateType(I.getType());
384         if (const CallInst *CI = dyn_cast<CallInst>(&I))
385           EnumerateAttributes(CI->getAttributes());
386         else if (const InvokeInst *II = dyn_cast<InvokeInst>(&I))
387           EnumerateAttributes(II->getAttributes());
388
389         // Enumerate metadata attached with this instruction.
390         MDs.clear();
391         I.getAllMetadataOtherThanDebugLoc(MDs);
392         for (unsigned i = 0, e = MDs.size(); i != e; ++i)
393           EnumerateMetadata(&F, MDs[i].second);
394
395         // Don't enumerate the location directly -- it has a special record
396         // type -- but enumerate its operands.
397         if (DILocation *L = I.getDebugLoc())
398           for (const Metadata *Op : L->operands())
399             EnumerateMetadata(&F, Op);
400       }
401   }
402
403   // Optimize constant ordering.
404   OptimizeConstants(FirstConstant, Values.size());
405
406   // Organize metadata ordering.
407   organizeMetadata();
408 }
409
410 unsigned ValueEnumerator::getInstructionID(const Instruction *Inst) const {
411   InstructionMapType::const_iterator I = InstructionMap.find(Inst);
412   assert(I != InstructionMap.end() && "Instruction is not mapped!");
413   return I->second;
414 }
415
416 unsigned ValueEnumerator::getComdatID(const Comdat *C) const {
417   unsigned ComdatID = Comdats.idFor(C);
418   assert(ComdatID && "Comdat not found!");
419   return ComdatID;
420 }
421
422 void ValueEnumerator::setInstructionID(const Instruction *I) {
423   InstructionMap[I] = InstructionCount++;
424 }
425
426 unsigned ValueEnumerator::getValueID(const Value *V) const {
427   if (auto *MD = dyn_cast<MetadataAsValue>(V))
428     return getMetadataID(MD->getMetadata());
429
430   ValueMapType::const_iterator I = ValueMap.find(V);
431   assert(I != ValueMap.end() && "Value not in slotcalculator!");
432   return I->second-1;
433 }
434
435 LLVM_DUMP_METHOD void ValueEnumerator::dump() const {
436   print(dbgs(), ValueMap, "Default");
437   dbgs() << '\n';
438   print(dbgs(), MetadataMap, "MetaData");
439   dbgs() << '\n';
440 }
441
442 void ValueEnumerator::print(raw_ostream &OS, const ValueMapType &Map,
443                             const char *Name) const {
444
445   OS << "Map Name: " << Name << "\n";
446   OS << "Size: " << Map.size() << "\n";
447   for (ValueMapType::const_iterator I = Map.begin(),
448          E = Map.end(); I != E; ++I) {
449
450     const Value *V = I->first;
451     if (V->hasName())
452       OS << "Value: " << V->getName();
453     else
454       OS << "Value: [null]\n";
455     V->dump();
456
457     OS << " Uses(" << std::distance(V->use_begin(),V->use_end()) << "):";
458     for (const Use &U : V->uses()) {
459       if (&U != &*V->use_begin())
460         OS << ",";
461       if(U->hasName())
462         OS << " " << U->getName();
463       else
464         OS << " [null]";
465
466     }
467     OS <<  "\n\n";
468   }
469 }
470
471 void ValueEnumerator::print(raw_ostream &OS, const MetadataMapType &Map,
472                             const char *Name) const {
473
474   OS << "Map Name: " << Name << "\n";
475   OS << "Size: " << Map.size() << "\n";
476   for (auto I = Map.begin(), E = Map.end(); I != E; ++I) {
477     const Metadata *MD = I->first;
478     OS << "Metadata: slot = " << I->second.ID << "\n";
479     OS << "Metadata: function = " << I->second.F << "\n";
480     MD->print(OS);
481     OS << "\n";
482   }
483 }
484
485 /// OptimizeConstants - Reorder constant pool for denser encoding.
486 void ValueEnumerator::OptimizeConstants(unsigned CstStart, unsigned CstEnd) {
487   if (CstStart == CstEnd || CstStart+1 == CstEnd) return;
488
489   if (ShouldPreserveUseListOrder)
490     // Optimizing constants makes the use-list order difficult to predict.
491     // Disable it for now when trying to preserve the order.
492     return;
493
494   std::stable_sort(Values.begin() + CstStart, Values.begin() + CstEnd,
495                    [this](const std::pair<const Value *, unsigned> &LHS,
496                           const std::pair<const Value *, unsigned> &RHS) {
497     // Sort by plane.
498     if (LHS.first->getType() != RHS.first->getType())
499       return getTypeID(LHS.first->getType()) < getTypeID(RHS.first->getType());
500     // Then by frequency.
501     return LHS.second > RHS.second;
502   });
503
504   // Ensure that integer and vector of integer constants are at the start of the
505   // constant pool.  This is important so that GEP structure indices come before
506   // gep constant exprs.
507   std::stable_partition(Values.begin() + CstStart, Values.begin() + CstEnd,
508                         isIntOrIntVectorValue);
509
510   // Rebuild the modified portion of ValueMap.
511   for (; CstStart != CstEnd; ++CstStart)
512     ValueMap[Values[CstStart].first] = CstStart+1;
513 }
514
515
516 /// EnumerateValueSymbolTable - Insert all of the values in the specified symbol
517 /// table into the values table.
518 void ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) {
519   for (ValueSymbolTable::const_iterator VI = VST.begin(), VE = VST.end();
520        VI != VE; ++VI)
521     EnumerateValue(VI->getValue());
522 }
523
524 /// Insert all of the values referenced by named metadata in the specified
525 /// module.
526 void ValueEnumerator::EnumerateNamedMetadata(const Module &M) {
527   for (const auto &I : M.named_metadata())
528     EnumerateNamedMDNode(&I);
529 }
530
531 void ValueEnumerator::EnumerateNamedMDNode(const NamedMDNode *MD) {
532   for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i)
533     EnumerateMetadata(nullptr, MD->getOperand(i));
534 }
535
536 unsigned ValueEnumerator::getMetadataFunctionID(const Function *F) const {
537   return F ? getValueID(F) + 1 : 0;
538 }
539
540 void ValueEnumerator::EnumerateMetadata(const Function *F, const Metadata *MD) {
541   EnumerateMetadata(getMetadataFunctionID(F), MD);
542 }
543
544 void ValueEnumerator::EnumerateFunctionLocalMetadata(
545     const Function &F, const LocalAsMetadata *Local) {
546   EnumerateFunctionLocalMetadata(getMetadataFunctionID(&F), Local);
547 }
548
549 void ValueEnumerator::dropFunctionFromMetadata(
550     MetadataMapType::value_type &FirstMD) {
551   SmallVector<const MDNode *, 64> Worklist;
552   auto push = [this, &Worklist](MetadataMapType::value_type &MD) {
553     auto &Entry = MD.second;
554
555     // Nothing to do if this metadata isn't tagged.
556     if (!Entry.F)
557       return;
558
559     // Drop the function tag.
560     Entry.F = 0;
561
562     // If this is has an ID and is an MDNode, then its operands have entries as
563     // well.  We need to drop the function from them too.
564     if (Entry.ID)
565       if (auto *N = dyn_cast<MDNode>(MD.first))
566         Worklist.push_back(N);
567   };
568   push(FirstMD);
569   while (!Worklist.empty())
570     for (const Metadata *Op : Worklist.pop_back_val()->operands()) {
571       if (!Op)
572         continue;
573       auto MD = MetadataMap.find(Op);
574       if (MD != MetadataMap.end())
575         push(*MD);
576     }
577 }
578
579 void ValueEnumerator::EnumerateMetadata(unsigned F, const Metadata *MD) {
580   // It's vital for reader efficiency that uniqued subgraphs are done in
581   // post-order; it's expensive when their operands have forward references.
582   // If a distinct node is referenced from a uniqued node, it'll be delayed
583   // until the uniqued subgraph has been completely traversed.
584   SmallVector<const MDNode *, 32> DelayedDistinctNodes;
585
586   // Start by enumerating MD, and then work through its transitive operands in
587   // post-order.  This requires a depth-first search.
588   SmallVector<std::pair<const MDNode *, MDNode::op_iterator>, 32> Worklist;
589   if (const MDNode *N = enumerateMetadataImpl(F, MD))
590     Worklist.push_back(std::make_pair(N, N->op_begin()));
591
592   while (!Worklist.empty()) {
593     const MDNode *N = Worklist.back().first;
594
595     // Enumerate operands until we hit a new node.  We need to traverse these
596     // nodes' operands before visiting the rest of N's operands.
597     MDNode::op_iterator I = std::find_if(
598         Worklist.back().second, N->op_end(),
599         [&](const Metadata *MD) { return enumerateMetadataImpl(F, MD); });
600     if (I != N->op_end()) {
601       auto *Op = cast<MDNode>(*I);
602       Worklist.back().second = ++I;
603
604       // Delay traversing Op if it's a distinct node and N is uniqued.
605       if (Op->isDistinct() && !N->isDistinct())
606         DelayedDistinctNodes.push_back(Op);
607       else
608         Worklist.push_back(std::make_pair(Op, Op->op_begin()));
609       continue;
610     }
611
612     // All the operands have been visited.  Now assign an ID.
613     Worklist.pop_back();
614     MDs.push_back(N);
615     MetadataMap[N].ID = MDs.size();
616
617     // Flush out any delayed distinct nodes; these are all the distinct nodes
618     // that are leaves in last uniqued subgraph.
619     if (Worklist.empty() || Worklist.back().first->isDistinct()) {
620       for (const MDNode *N : DelayedDistinctNodes)
621         Worklist.push_back(std::make_pair(N, N->op_begin()));
622       DelayedDistinctNodes.clear();
623     }
624   }
625 }
626
627 const MDNode *ValueEnumerator::enumerateMetadataImpl(unsigned F, const Metadata *MD) {
628   if (!MD)
629     return nullptr;
630
631   assert(
632       (isa<MDNode>(MD) || isa<MDString>(MD) || isa<ConstantAsMetadata>(MD)) &&
633       "Invalid metadata kind");
634
635   auto Insertion = MetadataMap.insert(std::make_pair(MD, MDIndex(F)));
636   MDIndex &Entry = Insertion.first->second;
637   if (!Insertion.second) {
638     // Already mapped.  If F doesn't match the function tag, drop it.
639     if (Entry.hasDifferentFunction(F))
640       dropFunctionFromMetadata(*Insertion.first);
641     return nullptr;
642   }
643
644   // Don't assign IDs to metadata nodes.
645   if (auto *N = dyn_cast<MDNode>(MD))
646     return N;
647
648   // Save the metadata.
649   MDs.push_back(MD);
650   Entry.ID = MDs.size();
651
652   // Enumerate the constant, if any.
653   if (auto *C = dyn_cast<ConstantAsMetadata>(MD))
654     EnumerateValue(C->getValue());
655
656   return nullptr;
657 }
658
659 /// EnumerateFunctionLocalMetadataa - Incorporate function-local metadata
660 /// information reachable from the metadata.
661 void ValueEnumerator::EnumerateFunctionLocalMetadata(
662     unsigned F, const LocalAsMetadata *Local) {
663   assert(F && "Expected a function");
664
665   // Check to see if it's already in!
666   MDIndex &Index = MetadataMap[Local];
667   if (Index.ID) {
668     assert(Index.F == F && "Expected the same function");
669     return;
670   }
671
672   MDs.push_back(Local);
673   Index.F = F;
674   Index.ID = MDs.size();
675
676   EnumerateValue(Local->getValue());
677 }
678
679 static unsigned getMetadataTypeOrder(const Metadata *MD) {
680   // Strings are emitted in bulk and must come first.
681   if (isa<MDString>(MD))
682     return 0;
683
684   // ConstantAsMetadata doesn't reference anything.  We may as well shuffle it
685   // to the front since we can detect it.
686   auto *N = dyn_cast<MDNode>(MD);
687   if (!N)
688     return 1;
689
690   // The reader is fast forward references for distinct node operands, but slow
691   // when uniqued operands are unresolved.
692   return N->isDistinct() ? 2 : 3;
693 }
694
695 void ValueEnumerator::organizeMetadata() {
696   assert(MetadataMap.size() == MDs.size() &&
697          "Metadata map and vector out of sync");
698
699   if (MDs.empty())
700     return;
701
702   // Copy out the index information from MetadataMap in order to choose a new
703   // order.
704   SmallVector<MDIndex, 64> Order;
705   Order.reserve(MetadataMap.size());
706   for (const Metadata *MD : MDs)
707     Order.push_back(MetadataMap.lookup(MD));
708
709   // Partition:
710   //   - by function, then
711   //   - by isa<MDString>
712   // and then sort by the original/current ID.  Since the IDs are guaranteed to
713   // be unique, the result of std::sort will be deterministic.  There's no need
714   // for std::stable_sort.
715   std::sort(Order.begin(), Order.end(), [this](MDIndex LHS, MDIndex RHS) {
716     return std::make_tuple(LHS.F, getMetadataTypeOrder(LHS.get(MDs)), LHS.ID) <
717            std::make_tuple(RHS.F, getMetadataTypeOrder(RHS.get(MDs)), RHS.ID);
718   });
719
720   // Rebuild MDs, index the metadata ranges for each function in FunctionMDs,
721   // and fix up MetadataMap.
722   std::vector<const Metadata *> OldMDs = std::move(MDs);
723   MDs.reserve(OldMDs.size());
724   for (unsigned I = 0, E = Order.size(); I != E && !Order[I].F; ++I) {
725     auto *MD = Order[I].get(OldMDs);
726     MDs.push_back(MD);
727     MetadataMap[MD].ID = I + 1;
728     if (isa<MDString>(MD))
729       ++NumMDStrings;
730   }
731
732   // Return early if there's nothing for the functions.
733   if (MDs.size() == Order.size())
734     return;
735
736   // Build the function metadata ranges.
737   MDRange R;
738   FunctionMDs.reserve(OldMDs.size());
739   unsigned PrevF = 0;
740   for (unsigned I = MDs.size(), E = Order.size(), ID = MDs.size(); I != E;
741        ++I) {
742     unsigned F = Order[I].F;
743     if (!PrevF) {
744       PrevF = F;
745     } else if (PrevF != F) {
746       R.Last = FunctionMDs.size();
747       std::swap(R, FunctionMDInfo[PrevF]);
748       R.First = FunctionMDs.size();
749
750       ID = MDs.size();
751       PrevF = F;
752     }
753
754     auto *MD = Order[I].get(OldMDs);
755     FunctionMDs.push_back(MD);
756     MetadataMap[MD].ID = ++ID;
757     if (isa<MDString>(MD))
758       ++R.NumStrings;
759   }
760   R.Last = FunctionMDs.size();
761   FunctionMDInfo[PrevF] = R;
762 }
763
764 void ValueEnumerator::incorporateFunctionMetadata(const Function &F) {
765   NumModuleMDs = MDs.size();
766
767   auto R = FunctionMDInfo.lookup(getValueID(&F) + 1);
768   NumMDStrings = R.NumStrings;
769   MDs.insert(MDs.end(), FunctionMDs.begin() + R.First,
770              FunctionMDs.begin() + R.Last);
771 }
772
773 void ValueEnumerator::EnumerateValue(const Value *V) {
774   assert(!V->getType()->isVoidTy() && "Can't insert void values!");
775   assert(!isa<MetadataAsValue>(V) && "EnumerateValue doesn't handle Metadata!");
776
777   // Check to see if it's already in!
778   unsigned &ValueID = ValueMap[V];
779   if (ValueID) {
780     // Increment use count.
781     Values[ValueID-1].second++;
782     return;
783   }
784
785   if (auto *GO = dyn_cast<GlobalObject>(V))
786     if (const Comdat *C = GO->getComdat())
787       Comdats.insert(C);
788
789   // Enumerate the type of this value.
790   EnumerateType(V->getType());
791
792   if (const Constant *C = dyn_cast<Constant>(V)) {
793     if (isa<GlobalValue>(C)) {
794       // Initializers for globals are handled explicitly elsewhere.
795     } else if (C->getNumOperands()) {
796       // If a constant has operands, enumerate them.  This makes sure that if a
797       // constant has uses (for example an array of const ints), that they are
798       // inserted also.
799
800       // We prefer to enumerate them with values before we enumerate the user
801       // itself.  This makes it more likely that we can avoid forward references
802       // in the reader.  We know that there can be no cycles in the constants
803       // graph that don't go through a global variable.
804       for (User::const_op_iterator I = C->op_begin(), E = C->op_end();
805            I != E; ++I)
806         if (!isa<BasicBlock>(*I)) // Don't enumerate BB operand to BlockAddress.
807           EnumerateValue(*I);
808
809       // Finally, add the value.  Doing this could make the ValueID reference be
810       // dangling, don't reuse it.
811       Values.push_back(std::make_pair(V, 1U));
812       ValueMap[V] = Values.size();
813       return;
814     }
815   }
816
817   // Add the value.
818   Values.push_back(std::make_pair(V, 1U));
819   ValueID = Values.size();
820 }
821
822
823 void ValueEnumerator::EnumerateType(Type *Ty) {
824   unsigned *TypeID = &TypeMap[Ty];
825
826   // We've already seen this type.
827   if (*TypeID)
828     return;
829
830   // If it is a non-anonymous struct, mark the type as being visited so that we
831   // don't recursively visit it.  This is safe because we allow forward
832   // references of these in the bitcode reader.
833   if (StructType *STy = dyn_cast<StructType>(Ty))
834     if (!STy->isLiteral())
835       *TypeID = ~0U;
836
837   // Enumerate all of the subtypes before we enumerate this type.  This ensures
838   // that the type will be enumerated in an order that can be directly built.
839   for (Type *SubTy : Ty->subtypes())
840     EnumerateType(SubTy);
841
842   // Refresh the TypeID pointer in case the table rehashed.
843   TypeID = &TypeMap[Ty];
844
845   // Check to see if we got the pointer another way.  This can happen when
846   // enumerating recursive types that hit the base case deeper than they start.
847   //
848   // If this is actually a struct that we are treating as forward ref'able,
849   // then emit the definition now that all of its contents are available.
850   if (*TypeID && *TypeID != ~0U)
851     return;
852
853   // Add this type now that its contents are all happily enumerated.
854   Types.push_back(Ty);
855
856   *TypeID = Types.size();
857 }
858
859 // Enumerate the types for the specified value.  If the value is a constant,
860 // walk through it, enumerating the types of the constant.
861 void ValueEnumerator::EnumerateOperandType(const Value *V) {
862   EnumerateType(V->getType());
863
864   assert(!isa<MetadataAsValue>(V) && "Unexpected metadata operand");
865
866   const Constant *C = dyn_cast<Constant>(V);
867   if (!C)
868     return;
869
870   // If this constant is already enumerated, ignore it, we know its type must
871   // be enumerated.
872   if (ValueMap.count(C))
873     return;
874
875   // This constant may have operands, make sure to enumerate the types in
876   // them.
877   for (const Value *Op : C->operands()) {
878     // Don't enumerate basic blocks here, this happens as operands to
879     // blockaddress.
880     if (isa<BasicBlock>(Op))
881       continue;
882
883     EnumerateOperandType(Op);
884   }
885 }
886
887 void ValueEnumerator::EnumerateAttributes(AttributeSet PAL) {
888   if (PAL.isEmpty()) return;  // null is always 0.
889
890   // Do a lookup.
891   unsigned &Entry = AttributeMap[PAL];
892   if (Entry == 0) {
893     // Never saw this before, add it.
894     Attribute.push_back(PAL);
895     Entry = Attribute.size();
896   }
897
898   // Do lookups for all attribute groups.
899   for (unsigned i = 0, e = PAL.getNumSlots(); i != e; ++i) {
900     AttributeSet AS = PAL.getSlotAttributes(i);
901     unsigned &Entry = AttributeGroupMap[AS];
902     if (Entry == 0) {
903       AttributeGroups.push_back(AS);
904       Entry = AttributeGroups.size();
905     }
906   }
907 }
908
909 void ValueEnumerator::incorporateFunction(const Function &F) {
910   InstructionCount = 0;
911   NumModuleValues = Values.size();
912
913   // Add global metadata to the function block.  This doesn't include
914   // LocalAsMetadata.
915   incorporateFunctionMetadata(F);
916
917   // Adding function arguments to the value table.
918   for (const auto &I : F.args())
919     EnumerateValue(&I);
920
921   FirstFuncConstantID = Values.size();
922
923   // Add all function-level constants to the value table.
924   for (const BasicBlock &BB : F) {
925     for (const Instruction &I : BB)
926       for (const Use &OI : I.operands()) {
927         if ((isa<Constant>(OI) && !isa<GlobalValue>(OI)) || isa<InlineAsm>(OI))
928           EnumerateValue(OI);
929       }
930     BasicBlocks.push_back(&BB);
931     ValueMap[&BB] = BasicBlocks.size();
932   }
933
934   // Optimize the constant layout.
935   OptimizeConstants(FirstFuncConstantID, Values.size());
936
937   // Add the function's parameter attributes so they are available for use in
938   // the function's instruction.
939   EnumerateAttributes(F.getAttributes());
940
941   FirstInstID = Values.size();
942
943   SmallVector<LocalAsMetadata *, 8> FnLocalMDVector;
944   // Add all of the instructions.
945   for (const BasicBlock &BB : F) {
946     for (const Instruction &I : BB) {
947       for (const Use &OI : I.operands()) {
948         if (auto *MD = dyn_cast<MetadataAsValue>(&OI))
949           if (auto *Local = dyn_cast<LocalAsMetadata>(MD->getMetadata()))
950             // Enumerate metadata after the instructions they might refer to.
951             FnLocalMDVector.push_back(Local);
952       }
953
954       if (!I.getType()->isVoidTy())
955         EnumerateValue(&I);
956     }
957   }
958
959   // Add all of the function-local metadata.
960   for (unsigned i = 0, e = FnLocalMDVector.size(); i != e; ++i) {
961     // At this point, every local values have been incorporated, we shouldn't
962     // have a metadata operand that references a value that hasn't been seen.
963     assert(ValueMap.count(FnLocalMDVector[i]->getValue()) &&
964            "Missing value for metadata operand");
965     EnumerateFunctionLocalMetadata(F, FnLocalMDVector[i]);
966   }
967 }
968
969 void ValueEnumerator::purgeFunction() {
970   /// Remove purged values from the ValueMap.
971   for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i)
972     ValueMap.erase(Values[i].first);
973   for (unsigned i = NumModuleMDs, e = MDs.size(); i != e; ++i)
974     MetadataMap.erase(MDs[i]);
975   for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i)
976     ValueMap.erase(BasicBlocks[i]);
977
978   Values.resize(NumModuleValues);
979   MDs.resize(NumModuleMDs);
980   BasicBlocks.clear();
981   NumMDStrings = 0;
982 }
983
984 static void IncorporateFunctionInfoGlobalBBIDs(const Function *F,
985                                  DenseMap<const BasicBlock*, unsigned> &IDMap) {
986   unsigned Counter = 0;
987   for (const BasicBlock &BB : *F)
988     IDMap[&BB] = ++Counter;
989 }
990
991 /// getGlobalBasicBlockID - This returns the function-specific ID for the
992 /// specified basic block.  This is relatively expensive information, so it
993 /// should only be used by rare constructs such as address-of-label.
994 unsigned ValueEnumerator::getGlobalBasicBlockID(const BasicBlock *BB) const {
995   unsigned &Idx = GlobalBasicBlockIDs[BB];
996   if (Idx != 0)
997     return Idx-1;
998
999   IncorporateFunctionInfoGlobalBBIDs(BB->getParent(), GlobalBasicBlockIDs);
1000   return getGlobalBasicBlockID(BB);
1001 }
1002
1003 uint64_t ValueEnumerator::computeBitsRequiredForTypeIndicies() const {
1004   return Log2_32_Ceil(getTypes().size() + 1);
1005 }