IR: Allow temporary nodes to become uniqued or distinct
[oota-llvm.git] / lib / IR / Metadata.cpp
1 //===-- Metadata.cpp - Implement Metadata classes -------------------------===//
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 Metadata classes.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "llvm/IR/Metadata.h"
15 #include "LLVMContextImpl.h"
16 #include "SymbolTableListTraitsImpl.h"
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallSet.h"
20 #include "llvm/ADT/SmallString.h"
21 #include "llvm/ADT/StringMap.h"
22 #include "llvm/IR/ConstantRange.h"
23 #include "llvm/IR/Instruction.h"
24 #include "llvm/IR/LLVMContext.h"
25 #include "llvm/IR/Module.h"
26 #include "llvm/IR/ValueHandle.h"
27
28 using namespace llvm;
29
30 MetadataAsValue::MetadataAsValue(Type *Ty, Metadata *MD)
31     : Value(Ty, MetadataAsValueVal), MD(MD) {
32   track();
33 }
34
35 MetadataAsValue::~MetadataAsValue() {
36   getType()->getContext().pImpl->MetadataAsValues.erase(MD);
37   untrack();
38 }
39
40 /// \brief Canonicalize metadata arguments to intrinsics.
41 ///
42 /// To support bitcode upgrades (and assembly semantic sugar) for \a
43 /// MetadataAsValue, we need to canonicalize certain metadata.
44 ///
45 ///   - nullptr is replaced by an empty MDNode.
46 ///   - An MDNode with a single null operand is replaced by an empty MDNode.
47 ///   - An MDNode whose only operand is a \a ConstantAsMetadata gets skipped.
48 ///
49 /// This maintains readability of bitcode from when metadata was a type of
50 /// value, and these bridges were unnecessary.
51 static Metadata *canonicalizeMetadataForValue(LLVMContext &Context,
52                                               Metadata *MD) {
53   if (!MD)
54     // !{}
55     return MDNode::get(Context, None);
56
57   // Return early if this isn't a single-operand MDNode.
58   auto *N = dyn_cast<MDNode>(MD);
59   if (!N || N->getNumOperands() != 1)
60     return MD;
61
62   if (!N->getOperand(0))
63     // !{}
64     return MDNode::get(Context, None);
65
66   if (auto *C = dyn_cast<ConstantAsMetadata>(N->getOperand(0)))
67     // Look through the MDNode.
68     return C;
69
70   return MD;
71 }
72
73 MetadataAsValue *MetadataAsValue::get(LLVMContext &Context, Metadata *MD) {
74   MD = canonicalizeMetadataForValue(Context, MD);
75   auto *&Entry = Context.pImpl->MetadataAsValues[MD];
76   if (!Entry)
77     Entry = new MetadataAsValue(Type::getMetadataTy(Context), MD);
78   return Entry;
79 }
80
81 MetadataAsValue *MetadataAsValue::getIfExists(LLVMContext &Context,
82                                               Metadata *MD) {
83   MD = canonicalizeMetadataForValue(Context, MD);
84   auto &Store = Context.pImpl->MetadataAsValues;
85   auto I = Store.find(MD);
86   return I == Store.end() ? nullptr : I->second;
87 }
88
89 void MetadataAsValue::handleChangedMetadata(Metadata *MD) {
90   LLVMContext &Context = getContext();
91   MD = canonicalizeMetadataForValue(Context, MD);
92   auto &Store = Context.pImpl->MetadataAsValues;
93
94   // Stop tracking the old metadata.
95   Store.erase(this->MD);
96   untrack();
97   this->MD = nullptr;
98
99   // Start tracking MD, or RAUW if necessary.
100   auto *&Entry = Store[MD];
101   if (Entry) {
102     replaceAllUsesWith(Entry);
103     delete this;
104     return;
105   }
106
107   this->MD = MD;
108   track();
109   Entry = this;
110 }
111
112 void MetadataAsValue::track() {
113   if (MD)
114     MetadataTracking::track(&MD, *MD, *this);
115 }
116
117 void MetadataAsValue::untrack() {
118   if (MD)
119     MetadataTracking::untrack(MD);
120 }
121
122 void ReplaceableMetadataImpl::addRef(void *Ref, OwnerTy Owner) {
123   bool WasInserted =
124       UseMap.insert(std::make_pair(Ref, std::make_pair(Owner, NextIndex)))
125           .second;
126   (void)WasInserted;
127   assert(WasInserted && "Expected to add a reference");
128
129   ++NextIndex;
130   assert(NextIndex != 0 && "Unexpected overflow");
131 }
132
133 void ReplaceableMetadataImpl::dropRef(void *Ref) {
134   bool WasErased = UseMap.erase(Ref);
135   (void)WasErased;
136   assert(WasErased && "Expected to drop a reference");
137 }
138
139 void ReplaceableMetadataImpl::moveRef(void *Ref, void *New,
140                                       const Metadata &MD) {
141   auto I = UseMap.find(Ref);
142   assert(I != UseMap.end() && "Expected to move a reference");
143   auto OwnerAndIndex = I->second;
144   UseMap.erase(I);
145   bool WasInserted = UseMap.insert(std::make_pair(New, OwnerAndIndex)).second;
146   (void)WasInserted;
147   assert(WasInserted && "Expected to add a reference");
148
149   // Check that the references are direct if there's no owner.
150   (void)MD;
151   assert((OwnerAndIndex.first || *static_cast<Metadata **>(Ref) == &MD) &&
152          "Reference without owner must be direct");
153   assert((OwnerAndIndex.first || *static_cast<Metadata **>(New) == &MD) &&
154          "Reference without owner must be direct");
155 }
156
157 void ReplaceableMetadataImpl::replaceAllUsesWith(Metadata *MD) {
158   assert(!(MD && isa<MDNode>(MD) && cast<MDNode>(MD)->isTemporary()) &&
159          "Expected non-temp node");
160
161   if (UseMap.empty())
162     return;
163
164   // Copy out uses since UseMap will get touched below.
165   typedef std::pair<void *, std::pair<OwnerTy, uint64_t>> UseTy;
166   SmallVector<UseTy, 8> Uses(UseMap.begin(), UseMap.end());
167   std::sort(Uses.begin(), Uses.end(), [](const UseTy &L, const UseTy &R) {
168     return L.second.second < R.second.second;
169   });
170   for (const auto &Pair : Uses) {
171     // Check that this Ref hasn't disappeared after RAUW (when updating a
172     // previous Ref).
173     if (!UseMap.count(Pair.first))
174       continue;
175
176     OwnerTy Owner = Pair.second.first;
177     if (!Owner) {
178       // Update unowned tracking references directly.
179       Metadata *&Ref = *static_cast<Metadata **>(Pair.first);
180       Ref = MD;
181       if (MD)
182         MetadataTracking::track(Ref);
183       UseMap.erase(Pair.first);
184       continue;
185     }
186
187     // Check for MetadataAsValue.
188     if (Owner.is<MetadataAsValue *>()) {
189       Owner.get<MetadataAsValue *>()->handleChangedMetadata(MD);
190       continue;
191     }
192
193     // There's a Metadata owner -- dispatch.
194     Metadata *OwnerMD = Owner.get<Metadata *>();
195     switch (OwnerMD->getMetadataID()) {
196 #define HANDLE_METADATA_LEAF(CLASS)                                            \
197   case Metadata::CLASS##Kind:                                                  \
198     cast<CLASS>(OwnerMD)->handleChangedOperand(Pair.first, MD);                \
199     continue;
200 #include "llvm/IR/Metadata.def"
201     default:
202       llvm_unreachable("Invalid metadata subclass");
203     }
204   }
205   assert(UseMap.empty() && "Expected all uses to be replaced");
206 }
207
208 void ReplaceableMetadataImpl::resolveAllUses(bool ResolveUsers) {
209   if (UseMap.empty())
210     return;
211
212   if (!ResolveUsers) {
213     UseMap.clear();
214     return;
215   }
216
217   // Copy out uses since UseMap could get touched below.
218   typedef std::pair<void *, std::pair<OwnerTy, uint64_t>> UseTy;
219   SmallVector<UseTy, 8> Uses(UseMap.begin(), UseMap.end());
220   std::sort(Uses.begin(), Uses.end(), [](const UseTy &L, const UseTy &R) {
221     return L.second.second < R.second.second;
222   });
223   UseMap.clear();
224   for (const auto &Pair : Uses) {
225     auto Owner = Pair.second.first;
226     if (!Owner)
227       continue;
228     if (Owner.is<MetadataAsValue *>())
229       continue;
230
231     // Resolve UniquableMDNodes that point at this.
232     auto *OwnerMD = dyn_cast<UniquableMDNode>(Owner.get<Metadata *>());
233     if (!OwnerMD)
234       continue;
235     if (OwnerMD->isResolved())
236       continue;
237     OwnerMD->decrementUnresolvedOperandCount();
238   }
239 }
240
241 static Function *getLocalFunction(Value *V) {
242   assert(V && "Expected value");
243   if (auto *A = dyn_cast<Argument>(V))
244     return A->getParent();
245   if (BasicBlock *BB = cast<Instruction>(V)->getParent())
246     return BB->getParent();
247   return nullptr;
248 }
249
250 ValueAsMetadata *ValueAsMetadata::get(Value *V) {
251   assert(V && "Unexpected null Value");
252
253   auto &Context = V->getContext();
254   auto *&Entry = Context.pImpl->ValuesAsMetadata[V];
255   if (!Entry) {
256     assert((isa<Constant>(V) || isa<Argument>(V) || isa<Instruction>(V)) &&
257            "Expected constant or function-local value");
258     assert(!V->NameAndIsUsedByMD.getInt() &&
259            "Expected this to be the only metadata use");
260     V->NameAndIsUsedByMD.setInt(true);
261     if (auto *C = dyn_cast<Constant>(V))
262       Entry = new ConstantAsMetadata(C);
263     else
264       Entry = new LocalAsMetadata(V);
265   }
266
267   return Entry;
268 }
269
270 ValueAsMetadata *ValueAsMetadata::getIfExists(Value *V) {
271   assert(V && "Unexpected null Value");
272   return V->getContext().pImpl->ValuesAsMetadata.lookup(V);
273 }
274
275 void ValueAsMetadata::handleDeletion(Value *V) {
276   assert(V && "Expected valid value");
277
278   auto &Store = V->getType()->getContext().pImpl->ValuesAsMetadata;
279   auto I = Store.find(V);
280   if (I == Store.end())
281     return;
282
283   // Remove old entry from the map.
284   ValueAsMetadata *MD = I->second;
285   assert(MD && "Expected valid metadata");
286   assert(MD->getValue() == V && "Expected valid mapping");
287   Store.erase(I);
288
289   // Delete the metadata.
290   MD->replaceAllUsesWith(nullptr);
291   delete MD;
292 }
293
294 void ValueAsMetadata::handleRAUW(Value *From, Value *To) {
295   assert(From && "Expected valid value");
296   assert(To && "Expected valid value");
297   assert(From != To && "Expected changed value");
298   assert(From->getType() == To->getType() && "Unexpected type change");
299
300   LLVMContext &Context = From->getType()->getContext();
301   auto &Store = Context.pImpl->ValuesAsMetadata;
302   auto I = Store.find(From);
303   if (I == Store.end()) {
304     assert(!From->NameAndIsUsedByMD.getInt() &&
305            "Expected From not to be used by metadata");
306     return;
307   }
308
309   // Remove old entry from the map.
310   assert(From->NameAndIsUsedByMD.getInt() &&
311          "Expected From to be used by metadata");
312   From->NameAndIsUsedByMD.setInt(false);
313   ValueAsMetadata *MD = I->second;
314   assert(MD && "Expected valid metadata");
315   assert(MD->getValue() == From && "Expected valid mapping");
316   Store.erase(I);
317
318   if (isa<LocalAsMetadata>(MD)) {
319     if (auto *C = dyn_cast<Constant>(To)) {
320       // Local became a constant.
321       MD->replaceAllUsesWith(ConstantAsMetadata::get(C));
322       delete MD;
323       return;
324     }
325     if (getLocalFunction(From) && getLocalFunction(To) &&
326         getLocalFunction(From) != getLocalFunction(To)) {
327       // Function changed.
328       MD->replaceAllUsesWith(nullptr);
329       delete MD;
330       return;
331     }
332   } else if (!isa<Constant>(To)) {
333     // Changed to function-local value.
334     MD->replaceAllUsesWith(nullptr);
335     delete MD;
336     return;
337   }
338
339   auto *&Entry = Store[To];
340   if (Entry) {
341     // The target already exists.
342     MD->replaceAllUsesWith(Entry);
343     delete MD;
344     return;
345   }
346
347   // Update MD in place (and update the map entry).
348   assert(!To->NameAndIsUsedByMD.getInt() &&
349          "Expected this to be the only metadata use");
350   To->NameAndIsUsedByMD.setInt(true);
351   MD->V = To;
352   Entry = MD;
353 }
354
355 //===----------------------------------------------------------------------===//
356 // MDString implementation.
357 //
358
359 MDString *MDString::get(LLVMContext &Context, StringRef Str) {
360   auto &Store = Context.pImpl->MDStringCache;
361   auto I = Store.find(Str);
362   if (I != Store.end())
363     return &I->second;
364
365   auto *Entry =
366       StringMapEntry<MDString>::Create(Str, Store.getAllocator(), MDString());
367   bool WasInserted = Store.insert(Entry);
368   (void)WasInserted;
369   assert(WasInserted && "Expected entry to be inserted");
370   Entry->second.Entry = Entry;
371   return &Entry->second;
372 }
373
374 StringRef MDString::getString() const {
375   assert(Entry && "Expected to find string map entry");
376   return Entry->first();
377 }
378
379 //===----------------------------------------------------------------------===//
380 // MDNode implementation.
381 //
382
383 void *MDNode::operator new(size_t Size, unsigned NumOps) {
384   void *Ptr = ::operator new(Size + NumOps * sizeof(MDOperand));
385   MDOperand *O = static_cast<MDOperand *>(Ptr);
386   for (MDOperand *E = O + NumOps; O != E; ++O)
387     (void)new (O) MDOperand;
388   return O;
389 }
390
391 void MDNode::operator delete(void *Mem) {
392   MDNode *N = static_cast<MDNode *>(Mem);
393   MDOperand *O = static_cast<MDOperand *>(Mem);
394   for (MDOperand *E = O - N->NumOperands; O != E; --O)
395     (O - 1)->~MDOperand();
396   ::operator delete(O);
397 }
398
399 MDNode::MDNode(LLVMContext &Context, unsigned ID, StorageType Storage,
400                ArrayRef<Metadata *> MDs)
401     : Metadata(ID, Storage), Context(Context), NumOperands(MDs.size()),
402       MDNodeSubclassData(0) {
403   for (unsigned I = 0, E = MDs.size(); I != E; ++I)
404     setOperand(I, MDs[I]);
405
406   if (isTemporary())
407     this->Context.makeReplaceable(
408         make_unique<ReplaceableMetadataImpl>(Context));
409 }
410
411 static bool isOperandUnresolved(Metadata *Op) {
412   if (auto *N = dyn_cast_or_null<MDNode>(Op))
413     return !N->isResolved();
414   return false;
415 }
416
417 UniquableMDNode::UniquableMDNode(LLVMContext &C, unsigned ID,
418                                  StorageType Storage, ArrayRef<Metadata *> Vals)
419     : MDNode(C, ID, Storage, Vals) {
420   if (!isUniqued())
421     return;
422
423   // Check whether any operands are unresolved, requiring re-uniquing.
424   unsigned NumUnresolved = countUnresolvedOperands();
425   if (!NumUnresolved)
426     return;
427
428   this->Context.makeReplaceable(make_unique<ReplaceableMetadataImpl>(C));
429   SubclassData32 = NumUnresolved;
430 }
431
432 unsigned UniquableMDNode::countUnresolvedOperands() const {
433   unsigned NumUnresolved = 0;
434   for (const auto &Op : operands())
435     NumUnresolved += unsigned(isOperandUnresolved(Op));
436   return NumUnresolved;
437 }
438
439 void UniquableMDNode::makeUniqued() {
440   assert(isTemporary() && "Expected this to be temporary");
441   assert(!isResolved() && "Expected this to be unresolved");
442
443   // Make this 'uniqued'.
444   Storage = Uniqued;
445   if (unsigned NumUnresolved = countUnresolvedOperands())
446     SubclassData32 = NumUnresolved;
447   else
448     resolve();
449
450   assert(isUniqued() && "Expected this to be uniqued");
451 }
452
453 void UniquableMDNode::makeDistinct() {
454   assert(isTemporary() && "Expected this to be temporary");
455   assert(!isResolved() && "Expected this to be unresolved");
456
457   // Pretend to be uniqued, resolve the node, and then store in distinct table.
458   Storage = Uniqued;
459   resolve();
460   storeDistinctInContext();
461
462   assert(isDistinct() && "Expected this to be distinct");
463   assert(isResolved() && "Expected this to be resolved");
464 }
465
466 void UniquableMDNode::resolve() {
467   assert(isUniqued() && "Expected this to be uniqued");
468   assert(!isResolved() && "Expected this to be unresolved");
469
470   // Move the map, so that this immediately looks resolved.
471   auto Uses = Context.takeReplaceableUses();
472   SubclassData32 = 0;
473   assert(isResolved() && "Expected this to be resolved");
474
475   // Drop RAUW support.
476   Uses->resolveAllUses();
477 }
478
479 void UniquableMDNode::resolveAfterOperandChange(Metadata *Old, Metadata *New) {
480   assert(SubclassData32 != 0 && "Expected unresolved operands");
481
482   // Check if an operand was resolved.
483   if (!isOperandUnresolved(Old)) {
484     if (isOperandUnresolved(New))
485       // An operand was un-resolved!
486       ++SubclassData32;
487   } else if (!isOperandUnresolved(New))
488     decrementUnresolvedOperandCount();
489 }
490
491 void UniquableMDNode::decrementUnresolvedOperandCount() {
492   if (!--SubclassData32)
493     // Last unresolved operand has just been resolved.
494     resolve();
495 }
496
497 void UniquableMDNode::resolveCycles() {
498   if (isResolved())
499     return;
500
501   // Resolve this node immediately.
502   resolve();
503
504   // Resolve all operands.
505   for (const auto &Op : operands()) {
506     auto *N = dyn_cast_or_null<UniquableMDNode>(Op);
507     if (!N)
508       continue;
509
510     assert(!N->isTemporary() &&
511            "Expected all forward declarations to be resolved");
512     if (!N->isResolved())
513       N->resolveCycles();
514   }
515 }
516
517 void MDTuple::recalculateHash() {
518   setHash(hash_combine_range(op_begin(), op_end()));
519 #ifndef NDEBUG
520   {
521     SmallVector<Metadata *, 8> MDs(op_begin(), op_end());
522     unsigned RawHash = hash_combine_range(MDs.begin(), MDs.end());
523     assert(getHash() == RawHash &&
524            "Expected hash of MDOperand to equal hash of Metadata*");
525   }
526 #endif
527 }
528
529 void MDNode::dropAllReferences() {
530   for (unsigned I = 0, E = NumOperands; I != E; ++I)
531     setOperand(I, nullptr);
532   if (auto *N = dyn_cast<UniquableMDNode>(this))
533     if (!N->isResolved()) {
534       N->Context.getReplaceableUses()->resolveAllUses(/* ResolveUsers */ false);
535       (void)N->Context.takeReplaceableUses();
536     }
537 }
538
539 namespace llvm {
540 /// \brief Make MDOperand transparent for hashing.
541 ///
542 /// This overload of an implementation detail of the hashing library makes
543 /// MDOperand hash to the same value as a \a Metadata pointer.
544 ///
545 /// Note that overloading \a hash_value() as follows:
546 ///
547 /// \code
548 ///     size_t hash_value(const MDOperand &X) { return hash_value(X.get()); }
549 /// \endcode
550 ///
551 /// does not cause MDOperand to be transparent.  In particular, a bare pointer
552 /// doesn't get hashed before it's combined, whereas \a MDOperand would.
553 static const Metadata *get_hashable_data(const MDOperand &X) { return X.get(); }
554 }
555
556 void UniquableMDNode::handleChangedOperand(void *Ref, Metadata *New) {
557   unsigned Op = static_cast<MDOperand *>(Ref) - op_begin();
558   assert(Op < getNumOperands() && "Expected valid operand");
559
560   if (!isUniqued()) {
561     // This node is not uniqued.  Just set the operand and be done with it.
562     setOperand(Op, New);
563     return;
564   }
565
566   // This node is uniqued.
567   eraseFromStore();
568
569   Metadata *Old = getOperand(Op);
570   setOperand(Op, New);
571
572   // Drop uniquing for self-reference cycles.
573   if (New == this) {
574     if (!isResolved())
575       resolve();
576     storeDistinctInContext();
577     return;
578   }
579
580   // Re-unique the node.
581   auto *Uniqued = uniquify();
582   if (Uniqued == this) {
583     if (!isResolved())
584       resolveAfterOperandChange(Old, New);
585     return;
586   }
587
588   // Collision.
589   if (!isResolved()) {
590     // Still unresolved, so RAUW.
591     //
592     // First, clear out all operands to prevent any recursion (similar to
593     // dropAllReferences(), but we still need the use-list).
594     for (unsigned O = 0, E = getNumOperands(); O != E; ++O)
595       setOperand(O, nullptr);
596     Context.getReplaceableUses()->replaceAllUsesWith(Uniqued);
597     deleteAsSubclass();
598     return;
599   }
600
601   // Store in non-uniqued form if RAUW isn't possible.
602   storeDistinctInContext();
603 }
604
605 void UniquableMDNode::deleteAsSubclass() {
606   switch (getMetadataID()) {
607   default:
608     llvm_unreachable("Invalid subclass of UniquableMDNode");
609 #define HANDLE_UNIQUABLE_LEAF(CLASS)                                           \
610   case CLASS##Kind:                                                            \
611     delete cast<CLASS>(this);                                                  \
612     break;
613 #include "llvm/IR/Metadata.def"
614   }
615 }
616
617 UniquableMDNode *UniquableMDNode::uniquify() {
618   switch (getMetadataID()) {
619   default:
620     llvm_unreachable("Invalid subclass of UniquableMDNode");
621 #define HANDLE_UNIQUABLE_LEAF(CLASS)                                           \
622   case CLASS##Kind:                                                            \
623     return cast<CLASS>(this)->uniquifyImpl();
624 #include "llvm/IR/Metadata.def"
625   }
626 }
627
628 void UniquableMDNode::eraseFromStore() {
629   switch (getMetadataID()) {
630   default:
631     llvm_unreachable("Invalid subclass of UniquableMDNode");
632 #define HANDLE_UNIQUABLE_LEAF(CLASS)                                           \
633   case CLASS##Kind:                                                            \
634     cast<CLASS>(this)->eraseFromStoreImpl();                                   \
635     break;
636 #include "llvm/IR/Metadata.def"
637   }
638 }
639
640 template <class T, class InfoT>
641 static T *getUniqued(DenseSet<T *, InfoT> &Store,
642                      const typename InfoT::KeyTy &Key) {
643   auto I = Store.find_as(Key);
644   return I == Store.end() ? nullptr : *I;
645 }
646
647 template <class T, class StoreT>
648 T *UniquableMDNode::storeImpl(T *N, StorageType Storage, StoreT &Store) {
649   switch (Storage) {
650   case Uniqued:
651     Store.insert(N);
652     break;
653   case Distinct:
654     N->storeDistinctInContext();
655     break;
656   case Temporary:
657     break;
658   }
659   return N;
660 }
661
662 MDTuple *MDTuple::getImpl(LLVMContext &Context, ArrayRef<Metadata *> MDs,
663                           StorageType Storage, bool ShouldCreate) {
664   unsigned Hash = 0;
665   if (Storage == Uniqued) {
666     MDTupleInfo::KeyTy Key(MDs);
667     if (auto *N = getUniqued(Context.pImpl->MDTuples, Key))
668       return N;
669     if (!ShouldCreate)
670       return nullptr;
671     Hash = Key.Hash;
672   } else {
673     assert(ShouldCreate && "Expected non-uniqued nodes to always be created");
674   }
675
676   return storeImpl(new (MDs.size()) MDTuple(Context, Storage, Hash, MDs),
677                    Storage, Context.pImpl->MDTuples);
678 }
679
680 MDTuple *MDTuple::uniquifyImpl() {
681   recalculateHash();
682   auto &Store = getContext().pImpl->MDTuples;
683   if (MDTuple *N = getUniqued(Store, this))
684     return N;
685
686   Store.insert(this);
687   return this;
688 }
689
690 void MDTuple::eraseFromStoreImpl() { getContext().pImpl->MDTuples.erase(this); }
691
692 MDLocation::MDLocation(LLVMContext &C, StorageType Storage, unsigned Line,
693                        unsigned Column, ArrayRef<Metadata *> MDs)
694     : UniquableMDNode(C, MDLocationKind, Storage, MDs) {
695   assert((MDs.size() == 1 || MDs.size() == 2) &&
696          "Expected a scope and optional inlined-at");
697
698   // Set line and column.
699   assert(Line < (1u << 24) && "Expected 24-bit line");
700   assert(Column < (1u << 16) && "Expected 16-bit column");
701
702   MDNodeSubclassData = Line;
703   SubclassData16 = Column;
704 }
705
706 static void adjustLine(unsigned &Line) {
707   // Set to unknown on overflow.  Still use 24 bits for now.
708   if (Line >= (1u << 24))
709     Line = 0;
710 }
711
712 static void adjustColumn(unsigned &Column) {
713   // Set to unknown on overflow.  We only have 16 bits to play with here.
714   if (Column >= (1u << 16))
715     Column = 0;
716 }
717
718 MDLocation *MDLocation::getImpl(LLVMContext &Context, unsigned Line,
719                                 unsigned Column, Metadata *Scope,
720                                 Metadata *InlinedAt, StorageType Storage,
721                                 bool ShouldCreate) {
722   // Fixup line/column.
723   adjustLine(Line);
724   adjustColumn(Column);
725
726   if (Storage == Uniqued) {
727     if (auto *N = getUniqued(
728             Context.pImpl->MDLocations,
729             MDLocationInfo::KeyTy(Line, Column, Scope, InlinedAt)))
730       return N;
731     if (!ShouldCreate)
732       return nullptr;
733   } else {
734     assert(ShouldCreate && "Expected non-uniqued nodes to always be created");
735   }
736
737   SmallVector<Metadata *, 2> Ops;
738   Ops.push_back(Scope);
739   if (InlinedAt)
740     Ops.push_back(InlinedAt);
741   return storeImpl(new (Ops.size())
742                        MDLocation(Context, Storage, Line, Column, Ops),
743                    Storage, Context.pImpl->MDLocations);
744 }
745
746 MDLocation *MDLocation::uniquifyImpl() {
747   auto &Store = getContext().pImpl->MDLocations;
748   if (MDLocation *N = getUniqued(Store, this))
749     return N;
750
751   Store.insert(this);
752   return this;
753 }
754
755 void MDLocation::eraseFromStoreImpl() {
756   getContext().pImpl->MDLocations.erase(this);
757 }
758
759 void MDNode::deleteTemporary(MDNode *N) {
760   assert(N->isTemporary() && "Expected temporary node");
761   cast<UniquableMDNode>(N)->deleteAsSubclass();
762 }
763
764 void UniquableMDNode::storeDistinctInContext() {
765   assert(isResolved() && "Expected resolved nodes");
766   Storage = Distinct;
767   if (auto *T = dyn_cast<MDTuple>(this))
768     T->setHash(0);
769   getContext().pImpl->DistinctMDNodes.insert(this);
770 }
771
772 void MDNode::replaceOperandWith(unsigned I, Metadata *New) {
773   if (getOperand(I) == New)
774     return;
775
776   if (!isUniqued()) {
777     setOperand(I, New);
778     return;
779   }
780
781   cast<UniquableMDNode>(this)->handleChangedOperand(mutable_begin() + I, New);
782 }
783
784 void MDNode::setOperand(unsigned I, Metadata *New) {
785   assert(I < NumOperands);
786   mutable_begin()[I].reset(New, isUniqued() ? this : nullptr);
787 }
788
789 /// \brief Get a node, or a self-reference that looks like it.
790 ///
791 /// Special handling for finding self-references, for use by \a
792 /// MDNode::concatenate() and \a MDNode::intersect() to maintain behaviour from
793 /// when self-referencing nodes were still uniqued.  If the first operand has
794 /// the same operands as \c Ops, return the first operand instead.
795 static MDNode *getOrSelfReference(LLVMContext &Context,
796                                   ArrayRef<Metadata *> Ops) {
797   if (!Ops.empty())
798     if (MDNode *N = dyn_cast_or_null<MDNode>(Ops[0]))
799       if (N->getNumOperands() == Ops.size() && N == N->getOperand(0)) {
800         for (unsigned I = 1, E = Ops.size(); I != E; ++I)
801           if (Ops[I] != N->getOperand(I))
802             return MDNode::get(Context, Ops);
803         return N;
804       }
805
806   return MDNode::get(Context, Ops);
807 }
808
809 MDNode *MDNode::concatenate(MDNode *A, MDNode *B) {
810   if (!A)
811     return B;
812   if (!B)
813     return A;
814
815   SmallVector<Metadata *, 4> MDs(A->getNumOperands() + B->getNumOperands());
816
817   unsigned j = 0;
818   for (unsigned i = 0, ie = A->getNumOperands(); i != ie; ++i)
819     MDs[j++] = A->getOperand(i);
820   for (unsigned i = 0, ie = B->getNumOperands(); i != ie; ++i)
821     MDs[j++] = B->getOperand(i);
822
823   // FIXME: This preserves long-standing behaviour, but is it really the right
824   // behaviour?  Or was that an unintended side-effect of node uniquing?
825   return getOrSelfReference(A->getContext(), MDs);
826 }
827
828 MDNode *MDNode::intersect(MDNode *A, MDNode *B) {
829   if (!A || !B)
830     return nullptr;
831
832   SmallVector<Metadata *, 4> MDs;
833   for (unsigned i = 0, ie = A->getNumOperands(); i != ie; ++i) {
834     Metadata *MD = A->getOperand(i);
835     for (unsigned j = 0, je = B->getNumOperands(); j != je; ++j)
836       if (MD == B->getOperand(j)) {
837         MDs.push_back(MD);
838         break;
839       }
840   }
841
842   // FIXME: This preserves long-standing behaviour, but is it really the right
843   // behaviour?  Or was that an unintended side-effect of node uniquing?
844   return getOrSelfReference(A->getContext(), MDs);
845 }
846
847 MDNode *MDNode::getMostGenericFPMath(MDNode *A, MDNode *B) {
848   if (!A || !B)
849     return nullptr;
850
851   APFloat AVal = mdconst::extract<ConstantFP>(A->getOperand(0))->getValueAPF();
852   APFloat BVal = mdconst::extract<ConstantFP>(B->getOperand(0))->getValueAPF();
853   if (AVal.compare(BVal) == APFloat::cmpLessThan)
854     return A;
855   return B;
856 }
857
858 static bool isContiguous(const ConstantRange &A, const ConstantRange &B) {
859   return A.getUpper() == B.getLower() || A.getLower() == B.getUpper();
860 }
861
862 static bool canBeMerged(const ConstantRange &A, const ConstantRange &B) {
863   return !A.intersectWith(B).isEmptySet() || isContiguous(A, B);
864 }
865
866 static bool tryMergeRange(SmallVectorImpl<ConstantInt *> &EndPoints,
867                           ConstantInt *Low, ConstantInt *High) {
868   ConstantRange NewRange(Low->getValue(), High->getValue());
869   unsigned Size = EndPoints.size();
870   APInt LB = EndPoints[Size - 2]->getValue();
871   APInt LE = EndPoints[Size - 1]->getValue();
872   ConstantRange LastRange(LB, LE);
873   if (canBeMerged(NewRange, LastRange)) {
874     ConstantRange Union = LastRange.unionWith(NewRange);
875     Type *Ty = High->getType();
876     EndPoints[Size - 2] =
877         cast<ConstantInt>(ConstantInt::get(Ty, Union.getLower()));
878     EndPoints[Size - 1] =
879         cast<ConstantInt>(ConstantInt::get(Ty, Union.getUpper()));
880     return true;
881   }
882   return false;
883 }
884
885 static void addRange(SmallVectorImpl<ConstantInt *> &EndPoints,
886                      ConstantInt *Low, ConstantInt *High) {
887   if (!EndPoints.empty())
888     if (tryMergeRange(EndPoints, Low, High))
889       return;
890
891   EndPoints.push_back(Low);
892   EndPoints.push_back(High);
893 }
894
895 MDNode *MDNode::getMostGenericRange(MDNode *A, MDNode *B) {
896   // Given two ranges, we want to compute the union of the ranges. This
897   // is slightly complitade by having to combine the intervals and merge
898   // the ones that overlap.
899
900   if (!A || !B)
901     return nullptr;
902
903   if (A == B)
904     return A;
905
906   // First, walk both lists in older of the lower boundary of each interval.
907   // At each step, try to merge the new interval to the last one we adedd.
908   SmallVector<ConstantInt *, 4> EndPoints;
909   int AI = 0;
910   int BI = 0;
911   int AN = A->getNumOperands() / 2;
912   int BN = B->getNumOperands() / 2;
913   while (AI < AN && BI < BN) {
914     ConstantInt *ALow = mdconst::extract<ConstantInt>(A->getOperand(2 * AI));
915     ConstantInt *BLow = mdconst::extract<ConstantInt>(B->getOperand(2 * BI));
916
917     if (ALow->getValue().slt(BLow->getValue())) {
918       addRange(EndPoints, ALow,
919                mdconst::extract<ConstantInt>(A->getOperand(2 * AI + 1)));
920       ++AI;
921     } else {
922       addRange(EndPoints, BLow,
923                mdconst::extract<ConstantInt>(B->getOperand(2 * BI + 1)));
924       ++BI;
925     }
926   }
927   while (AI < AN) {
928     addRange(EndPoints, mdconst::extract<ConstantInt>(A->getOperand(2 * AI)),
929              mdconst::extract<ConstantInt>(A->getOperand(2 * AI + 1)));
930     ++AI;
931   }
932   while (BI < BN) {
933     addRange(EndPoints, mdconst::extract<ConstantInt>(B->getOperand(2 * BI)),
934              mdconst::extract<ConstantInt>(B->getOperand(2 * BI + 1)));
935     ++BI;
936   }
937
938   // If we have more than 2 ranges (4 endpoints) we have to try to merge
939   // the last and first ones.
940   unsigned Size = EndPoints.size();
941   if (Size > 4) {
942     ConstantInt *FB = EndPoints[0];
943     ConstantInt *FE = EndPoints[1];
944     if (tryMergeRange(EndPoints, FB, FE)) {
945       for (unsigned i = 0; i < Size - 2; ++i) {
946         EndPoints[i] = EndPoints[i + 2];
947       }
948       EndPoints.resize(Size - 2);
949     }
950   }
951
952   // If in the end we have a single range, it is possible that it is now the
953   // full range. Just drop the metadata in that case.
954   if (EndPoints.size() == 2) {
955     ConstantRange Range(EndPoints[0]->getValue(), EndPoints[1]->getValue());
956     if (Range.isFullSet())
957       return nullptr;
958   }
959
960   SmallVector<Metadata *, 4> MDs;
961   MDs.reserve(EndPoints.size());
962   for (auto *I : EndPoints)
963     MDs.push_back(ConstantAsMetadata::get(I));
964   return MDNode::get(A->getContext(), MDs);
965 }
966
967 //===----------------------------------------------------------------------===//
968 // NamedMDNode implementation.
969 //
970
971 static SmallVector<TrackingMDRef, 4> &getNMDOps(void *Operands) {
972   return *(SmallVector<TrackingMDRef, 4> *)Operands;
973 }
974
975 NamedMDNode::NamedMDNode(const Twine &N)
976     : Name(N.str()), Parent(nullptr),
977       Operands(new SmallVector<TrackingMDRef, 4>()) {}
978
979 NamedMDNode::~NamedMDNode() {
980   dropAllReferences();
981   delete &getNMDOps(Operands);
982 }
983
984 unsigned NamedMDNode::getNumOperands() const {
985   return (unsigned)getNMDOps(Operands).size();
986 }
987
988 MDNode *NamedMDNode::getOperand(unsigned i) const {
989   assert(i < getNumOperands() && "Invalid Operand number!");
990   auto *N = getNMDOps(Operands)[i].get();
991   return cast_or_null<MDNode>(N);
992 }
993
994 void NamedMDNode::addOperand(MDNode *M) { getNMDOps(Operands).emplace_back(M); }
995
996 void NamedMDNode::setOperand(unsigned I, MDNode *New) {
997   assert(I < getNumOperands() && "Invalid operand number");
998   getNMDOps(Operands)[I].reset(New);
999 }
1000
1001 void NamedMDNode::eraseFromParent() {
1002   getParent()->eraseNamedMetadata(this);
1003 }
1004
1005 void NamedMDNode::dropAllReferences() {
1006   getNMDOps(Operands).clear();
1007 }
1008
1009 StringRef NamedMDNode::getName() const {
1010   return StringRef(Name);
1011 }
1012
1013 //===----------------------------------------------------------------------===//
1014 // Instruction Metadata method implementations.
1015 //
1016
1017 void Instruction::setMetadata(StringRef Kind, MDNode *Node) {
1018   if (!Node && !hasMetadata())
1019     return;
1020   setMetadata(getContext().getMDKindID(Kind), Node);
1021 }
1022
1023 MDNode *Instruction::getMetadataImpl(StringRef Kind) const {
1024   return getMetadataImpl(getContext().getMDKindID(Kind));
1025 }
1026
1027 void Instruction::dropUnknownMetadata(ArrayRef<unsigned> KnownIDs) {
1028   SmallSet<unsigned, 5> KnownSet;
1029   KnownSet.insert(KnownIDs.begin(), KnownIDs.end());
1030
1031   // Drop debug if needed
1032   if (KnownSet.erase(LLVMContext::MD_dbg))
1033     DbgLoc = DebugLoc();
1034
1035   if (!hasMetadataHashEntry())
1036     return; // Nothing to remove!
1037
1038   DenseMap<const Instruction *, LLVMContextImpl::MDMapTy> &MetadataStore =
1039       getContext().pImpl->MetadataStore;
1040
1041   if (KnownSet.empty()) {
1042     // Just drop our entry at the store.
1043     MetadataStore.erase(this);
1044     setHasMetadataHashEntry(false);
1045     return;
1046   }
1047
1048   LLVMContextImpl::MDMapTy &Info = MetadataStore[this];
1049   unsigned I;
1050   unsigned E;
1051   // Walk the array and drop any metadata we don't know.
1052   for (I = 0, E = Info.size(); I != E;) {
1053     if (KnownSet.count(Info[I].first)) {
1054       ++I;
1055       continue;
1056     }
1057
1058     Info[I] = std::move(Info.back());
1059     Info.pop_back();
1060     --E;
1061   }
1062   assert(E == Info.size());
1063
1064   if (E == 0) {
1065     // Drop our entry at the store.
1066     MetadataStore.erase(this);
1067     setHasMetadataHashEntry(false);
1068   }
1069 }
1070
1071 /// setMetadata - Set the metadata of of the specified kind to the specified
1072 /// node.  This updates/replaces metadata if already present, or removes it if
1073 /// Node is null.
1074 void Instruction::setMetadata(unsigned KindID, MDNode *Node) {
1075   if (!Node && !hasMetadata())
1076     return;
1077
1078   // Handle 'dbg' as a special case since it is not stored in the hash table.
1079   if (KindID == LLVMContext::MD_dbg) {
1080     DbgLoc = DebugLoc::getFromDILocation(Node);
1081     return;
1082   }
1083   
1084   // Handle the case when we're adding/updating metadata on an instruction.
1085   if (Node) {
1086     LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this];
1087     assert(!Info.empty() == hasMetadataHashEntry() &&
1088            "HasMetadata bit is wonked");
1089     if (Info.empty()) {
1090       setHasMetadataHashEntry(true);
1091     } else {
1092       // Handle replacement of an existing value.
1093       for (auto &P : Info)
1094         if (P.first == KindID) {
1095           P.second.reset(Node);
1096           return;
1097         }
1098     }
1099
1100     // No replacement, just add it to the list.
1101     Info.emplace_back(std::piecewise_construct, std::make_tuple(KindID),
1102                       std::make_tuple(Node));
1103     return;
1104   }
1105
1106   // Otherwise, we're removing metadata from an instruction.
1107   assert((hasMetadataHashEntry() ==
1108           (getContext().pImpl->MetadataStore.count(this) > 0)) &&
1109          "HasMetadata bit out of date!");
1110   if (!hasMetadataHashEntry())
1111     return;  // Nothing to remove!
1112   LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this];
1113
1114   // Common case is removing the only entry.
1115   if (Info.size() == 1 && Info[0].first == KindID) {
1116     getContext().pImpl->MetadataStore.erase(this);
1117     setHasMetadataHashEntry(false);
1118     return;
1119   }
1120
1121   // Handle removal of an existing value.
1122   for (unsigned i = 0, e = Info.size(); i != e; ++i)
1123     if (Info[i].first == KindID) {
1124       Info[i] = std::move(Info.back());
1125       Info.pop_back();
1126       assert(!Info.empty() && "Removing last entry should be handled above");
1127       return;
1128     }
1129   // Otherwise, removing an entry that doesn't exist on the instruction.
1130 }
1131
1132 void Instruction::setAAMetadata(const AAMDNodes &N) {
1133   setMetadata(LLVMContext::MD_tbaa, N.TBAA);
1134   setMetadata(LLVMContext::MD_alias_scope, N.Scope);
1135   setMetadata(LLVMContext::MD_noalias, N.NoAlias);
1136 }
1137
1138 MDNode *Instruction::getMetadataImpl(unsigned KindID) const {
1139   // Handle 'dbg' as a special case since it is not stored in the hash table.
1140   if (KindID == LLVMContext::MD_dbg)
1141     return DbgLoc.getAsMDNode();
1142
1143   if (!hasMetadataHashEntry()) return nullptr;
1144   
1145   LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this];
1146   assert(!Info.empty() && "bit out of sync with hash table");
1147
1148   for (const auto &I : Info)
1149     if (I.first == KindID)
1150       return I.second;
1151   return nullptr;
1152 }
1153
1154 void Instruction::getAllMetadataImpl(
1155     SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
1156   Result.clear();
1157   
1158   // Handle 'dbg' as a special case since it is not stored in the hash table.
1159   if (!DbgLoc.isUnknown()) {
1160     Result.push_back(
1161         std::make_pair((unsigned)LLVMContext::MD_dbg, DbgLoc.getAsMDNode()));
1162     if (!hasMetadataHashEntry()) return;
1163   }
1164   
1165   assert(hasMetadataHashEntry() &&
1166          getContext().pImpl->MetadataStore.count(this) &&
1167          "Shouldn't have called this");
1168   const LLVMContextImpl::MDMapTy &Info =
1169     getContext().pImpl->MetadataStore.find(this)->second;
1170   assert(!Info.empty() && "Shouldn't have called this");
1171
1172   Result.reserve(Result.size() + Info.size());
1173   for (auto &I : Info)
1174     Result.push_back(std::make_pair(I.first, cast<MDNode>(I.second.get())));
1175
1176   // Sort the resulting array so it is stable.
1177   if (Result.size() > 1)
1178     array_pod_sort(Result.begin(), Result.end());
1179 }
1180
1181 void Instruction::getAllMetadataOtherThanDebugLocImpl(
1182     SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
1183   Result.clear();
1184   assert(hasMetadataHashEntry() &&
1185          getContext().pImpl->MetadataStore.count(this) &&
1186          "Shouldn't have called this");
1187   const LLVMContextImpl::MDMapTy &Info =
1188     getContext().pImpl->MetadataStore.find(this)->second;
1189   assert(!Info.empty() && "Shouldn't have called this");
1190   Result.reserve(Result.size() + Info.size());
1191   for (auto &I : Info)
1192     Result.push_back(std::make_pair(I.first, cast<MDNode>(I.second.get())));
1193
1194   // Sort the resulting array so it is stable.
1195   if (Result.size() > 1)
1196     array_pod_sort(Result.begin(), Result.end());
1197 }
1198
1199 /// clearMetadataHashEntries - Clear all hashtable-based metadata from
1200 /// this instruction.
1201 void Instruction::clearMetadataHashEntries() {
1202   assert(hasMetadataHashEntry() && "Caller should check");
1203   getContext().pImpl->MetadataStore.erase(this);
1204   setHasMetadataHashEntry(false);
1205 }