IR: Remove MDNodeFwdDecl
[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 = 0;
425   for (const auto &Op : operands())
426     NumUnresolved += unsigned(isOperandUnresolved(Op));
427
428   if (!NumUnresolved)
429     return;
430
431   this->Context.makeReplaceable(make_unique<ReplaceableMetadataImpl>(C));
432   SubclassData32 = NumUnresolved;
433 }
434
435 void UniquableMDNode::resolve() {
436   assert(isUniqued() && "Expected this to be uniqued");
437   assert(!isResolved() && "Expected this to be unresolved");
438
439   // Move the map, so that this immediately looks resolved.
440   auto Uses = Context.takeReplaceableUses();
441   SubclassData32 = 0;
442   assert(isResolved() && "Expected this to be resolved");
443
444   // Drop RAUW support.
445   Uses->resolveAllUses();
446 }
447
448 void UniquableMDNode::resolveAfterOperandChange(Metadata *Old, Metadata *New) {
449   assert(SubclassData32 != 0 && "Expected unresolved operands");
450
451   // Check if an operand was resolved.
452   if (!isOperandUnresolved(Old)) {
453     if (isOperandUnresolved(New))
454       // An operand was un-resolved!
455       ++SubclassData32;
456   } else if (!isOperandUnresolved(New))
457     decrementUnresolvedOperandCount();
458 }
459
460 void UniquableMDNode::decrementUnresolvedOperandCount() {
461   if (!--SubclassData32)
462     // Last unresolved operand has just been resolved.
463     resolve();
464 }
465
466 void UniquableMDNode::resolveCycles() {
467   if (isResolved())
468     return;
469
470   // Resolve this node immediately.
471   resolve();
472
473   // Resolve all operands.
474   for (const auto &Op : operands()) {
475     auto *N = dyn_cast_or_null<UniquableMDNode>(Op);
476     if (!N)
477       continue;
478
479     assert(!N->isTemporary() &&
480            "Expected all forward declarations to be resolved");
481     if (!N->isResolved())
482       N->resolveCycles();
483   }
484 }
485
486 void MDTuple::recalculateHash() {
487   setHash(hash_combine_range(op_begin(), op_end()));
488 #ifndef NDEBUG
489   {
490     SmallVector<Metadata *, 8> MDs(op_begin(), op_end());
491     unsigned RawHash = hash_combine_range(MDs.begin(), MDs.end());
492     assert(getHash() == RawHash &&
493            "Expected hash of MDOperand to equal hash of Metadata*");
494   }
495 #endif
496 }
497
498 void MDNode::dropAllReferences() {
499   for (unsigned I = 0, E = NumOperands; I != E; ++I)
500     setOperand(I, nullptr);
501   if (auto *N = dyn_cast<UniquableMDNode>(this))
502     if (!N->isResolved()) {
503       N->Context.getReplaceableUses()->resolveAllUses(/* ResolveUsers */ false);
504       (void)N->Context.takeReplaceableUses();
505     }
506 }
507
508 namespace llvm {
509 /// \brief Make MDOperand transparent for hashing.
510 ///
511 /// This overload of an implementation detail of the hashing library makes
512 /// MDOperand hash to the same value as a \a Metadata pointer.
513 ///
514 /// Note that overloading \a hash_value() as follows:
515 ///
516 /// \code
517 ///     size_t hash_value(const MDOperand &X) { return hash_value(X.get()); }
518 /// \endcode
519 ///
520 /// does not cause MDOperand to be transparent.  In particular, a bare pointer
521 /// doesn't get hashed before it's combined, whereas \a MDOperand would.
522 static const Metadata *get_hashable_data(const MDOperand &X) { return X.get(); }
523 }
524
525 void UniquableMDNode::handleChangedOperand(void *Ref, Metadata *New) {
526   unsigned Op = static_cast<MDOperand *>(Ref) - op_begin();
527   assert(Op < getNumOperands() && "Expected valid operand");
528
529   if (!isUniqued()) {
530     // This node is not uniqued.  Just set the operand and be done with it.
531     setOperand(Op, New);
532     return;
533   }
534
535   // This node is uniqued.
536   eraseFromStore();
537
538   Metadata *Old = getOperand(Op);
539   setOperand(Op, New);
540
541   // Drop uniquing for self-reference cycles.
542   if (New == this) {
543     if (!isResolved())
544       resolve();
545     storeDistinctInContext();
546     return;
547   }
548
549   // Re-unique the node.
550   auto *Uniqued = uniquify();
551   if (Uniqued == this) {
552     if (!isResolved())
553       resolveAfterOperandChange(Old, New);
554     return;
555   }
556
557   // Collision.
558   if (!isResolved()) {
559     // Still unresolved, so RAUW.
560     //
561     // First, clear out all operands to prevent any recursion (similar to
562     // dropAllReferences(), but we still need the use-list).
563     for (unsigned O = 0, E = getNumOperands(); O != E; ++O)
564       setOperand(O, nullptr);
565     Context.getReplaceableUses()->replaceAllUsesWith(Uniqued);
566     deleteAsSubclass();
567     return;
568   }
569
570   // Store in non-uniqued form if RAUW isn't possible.
571   storeDistinctInContext();
572 }
573
574 void UniquableMDNode::deleteAsSubclass() {
575   switch (getMetadataID()) {
576   default:
577     llvm_unreachable("Invalid subclass of UniquableMDNode");
578 #define HANDLE_UNIQUABLE_LEAF(CLASS)                                           \
579   case CLASS##Kind:                                                            \
580     delete cast<CLASS>(this);                                                  \
581     break;
582 #include "llvm/IR/Metadata.def"
583   }
584 }
585
586 UniquableMDNode *UniquableMDNode::uniquify() {
587   switch (getMetadataID()) {
588   default:
589     llvm_unreachable("Invalid subclass of UniquableMDNode");
590 #define HANDLE_UNIQUABLE_LEAF(CLASS)                                           \
591   case CLASS##Kind:                                                            \
592     return cast<CLASS>(this)->uniquifyImpl();
593 #include "llvm/IR/Metadata.def"
594   }
595 }
596
597 void UniquableMDNode::eraseFromStore() {
598   switch (getMetadataID()) {
599   default:
600     llvm_unreachable("Invalid subclass of UniquableMDNode");
601 #define HANDLE_UNIQUABLE_LEAF(CLASS)                                           \
602   case CLASS##Kind:                                                            \
603     cast<CLASS>(this)->eraseFromStoreImpl();                                   \
604     break;
605 #include "llvm/IR/Metadata.def"
606   }
607 }
608
609 template <class T, class InfoT>
610 static T *getUniqued(DenseSet<T *, InfoT> &Store,
611                      const typename InfoT::KeyTy &Key) {
612   auto I = Store.find_as(Key);
613   return I == Store.end() ? nullptr : *I;
614 }
615
616 template <class T, class StoreT>
617 T *UniquableMDNode::storeImpl(T *N, StorageType Storage, StoreT &Store) {
618   switch (Storage) {
619   case Uniqued:
620     Store.insert(N);
621     break;
622   case Distinct:
623     N->storeDistinctInContext();
624     break;
625   case Temporary:
626     break;
627   }
628   return N;
629 }
630
631 MDTuple *MDTuple::getImpl(LLVMContext &Context, ArrayRef<Metadata *> MDs,
632                           StorageType Storage, bool ShouldCreate) {
633   unsigned Hash = 0;
634   if (Storage == Uniqued) {
635     MDTupleInfo::KeyTy Key(MDs);
636     if (auto *N = getUniqued(Context.pImpl->MDTuples, Key))
637       return N;
638     if (!ShouldCreate)
639       return nullptr;
640     Hash = Key.Hash;
641   } else {
642     assert(ShouldCreate && "Expected non-uniqued nodes to always be created");
643   }
644
645   return storeImpl(new (MDs.size()) MDTuple(Context, Storage, Hash, MDs),
646                    Storage, Context.pImpl->MDTuples);
647 }
648
649 MDTuple *MDTuple::uniquifyImpl() {
650   recalculateHash();
651   auto &Store = getContext().pImpl->MDTuples;
652   if (MDTuple *N = getUniqued(Store, this))
653     return N;
654
655   Store.insert(this);
656   return this;
657 }
658
659 void MDTuple::eraseFromStoreImpl() { getContext().pImpl->MDTuples.erase(this); }
660
661 MDLocation::MDLocation(LLVMContext &C, StorageType Storage, unsigned Line,
662                        unsigned Column, ArrayRef<Metadata *> MDs)
663     : UniquableMDNode(C, MDLocationKind, Storage, MDs) {
664   assert((MDs.size() == 1 || MDs.size() == 2) &&
665          "Expected a scope and optional inlined-at");
666
667   // Set line and column.
668   assert(Line < (1u << 24) && "Expected 24-bit line");
669   assert(Column < (1u << 16) && "Expected 16-bit column");
670
671   MDNodeSubclassData = Line;
672   SubclassData16 = Column;
673 }
674
675 static void adjustLine(unsigned &Line) {
676   // Set to unknown on overflow.  Still use 24 bits for now.
677   if (Line >= (1u << 24))
678     Line = 0;
679 }
680
681 static void adjustColumn(unsigned &Column) {
682   // Set to unknown on overflow.  We only have 16 bits to play with here.
683   if (Column >= (1u << 16))
684     Column = 0;
685 }
686
687 MDLocation *MDLocation::getImpl(LLVMContext &Context, unsigned Line,
688                                 unsigned Column, Metadata *Scope,
689                                 Metadata *InlinedAt, StorageType Storage,
690                                 bool ShouldCreate) {
691   // Fixup line/column.
692   adjustLine(Line);
693   adjustColumn(Column);
694
695   if (Storage == Uniqued) {
696     if (auto *N = getUniqued(
697             Context.pImpl->MDLocations,
698             MDLocationInfo::KeyTy(Line, Column, Scope, InlinedAt)))
699       return N;
700     if (!ShouldCreate)
701       return nullptr;
702   } else {
703     assert(ShouldCreate && "Expected non-uniqued nodes to always be created");
704   }
705
706   SmallVector<Metadata *, 2> Ops;
707   Ops.push_back(Scope);
708   if (InlinedAt)
709     Ops.push_back(InlinedAt);
710   return storeImpl(new (Ops.size())
711                        MDLocation(Context, Storage, Line, Column, Ops),
712                    Storage, Context.pImpl->MDLocations);
713 }
714
715 MDLocation *MDLocation::uniquifyImpl() {
716   auto &Store = getContext().pImpl->MDLocations;
717   if (MDLocation *N = getUniqued(Store, this))
718     return N;
719
720   Store.insert(this);
721   return this;
722 }
723
724 void MDLocation::eraseFromStoreImpl() {
725   getContext().pImpl->MDLocations.erase(this);
726 }
727
728 void MDNode::deleteTemporary(MDNode *N) {
729   assert(N->isTemporary() && "Expected temporary node");
730   cast<UniquableMDNode>(N)->deleteAsSubclass();
731 }
732
733 void UniquableMDNode::storeDistinctInContext() {
734   assert(isResolved() && "Expected resolved nodes");
735   Storage = Distinct;
736   if (auto *T = dyn_cast<MDTuple>(this))
737     T->setHash(0);
738   getContext().pImpl->DistinctMDNodes.insert(this);
739 }
740
741 void MDNode::replaceOperandWith(unsigned I, Metadata *New) {
742   if (getOperand(I) == New)
743     return;
744
745   if (!isUniqued()) {
746     setOperand(I, New);
747     return;
748   }
749
750   cast<UniquableMDNode>(this)->handleChangedOperand(mutable_begin() + I, New);
751 }
752
753 void MDNode::setOperand(unsigned I, Metadata *New) {
754   assert(I < NumOperands);
755   mutable_begin()[I].reset(New, isUniqued() ? this : nullptr);
756 }
757
758 /// \brief Get a node, or a self-reference that looks like it.
759 ///
760 /// Special handling for finding self-references, for use by \a
761 /// MDNode::concatenate() and \a MDNode::intersect() to maintain behaviour from
762 /// when self-referencing nodes were still uniqued.  If the first operand has
763 /// the same operands as \c Ops, return the first operand instead.
764 static MDNode *getOrSelfReference(LLVMContext &Context,
765                                   ArrayRef<Metadata *> Ops) {
766   if (!Ops.empty())
767     if (MDNode *N = dyn_cast_or_null<MDNode>(Ops[0]))
768       if (N->getNumOperands() == Ops.size() && N == N->getOperand(0)) {
769         for (unsigned I = 1, E = Ops.size(); I != E; ++I)
770           if (Ops[I] != N->getOperand(I))
771             return MDNode::get(Context, Ops);
772         return N;
773       }
774
775   return MDNode::get(Context, Ops);
776 }
777
778 MDNode *MDNode::concatenate(MDNode *A, MDNode *B) {
779   if (!A)
780     return B;
781   if (!B)
782     return A;
783
784   SmallVector<Metadata *, 4> MDs(A->getNumOperands() + B->getNumOperands());
785
786   unsigned j = 0;
787   for (unsigned i = 0, ie = A->getNumOperands(); i != ie; ++i)
788     MDs[j++] = A->getOperand(i);
789   for (unsigned i = 0, ie = B->getNumOperands(); i != ie; ++i)
790     MDs[j++] = B->getOperand(i);
791
792   // FIXME: This preserves long-standing behaviour, but is it really the right
793   // behaviour?  Or was that an unintended side-effect of node uniquing?
794   return getOrSelfReference(A->getContext(), MDs);
795 }
796
797 MDNode *MDNode::intersect(MDNode *A, MDNode *B) {
798   if (!A || !B)
799     return nullptr;
800
801   SmallVector<Metadata *, 4> MDs;
802   for (unsigned i = 0, ie = A->getNumOperands(); i != ie; ++i) {
803     Metadata *MD = A->getOperand(i);
804     for (unsigned j = 0, je = B->getNumOperands(); j != je; ++j)
805       if (MD == B->getOperand(j)) {
806         MDs.push_back(MD);
807         break;
808       }
809   }
810
811   // FIXME: This preserves long-standing behaviour, but is it really the right
812   // behaviour?  Or was that an unintended side-effect of node uniquing?
813   return getOrSelfReference(A->getContext(), MDs);
814 }
815
816 MDNode *MDNode::getMostGenericFPMath(MDNode *A, MDNode *B) {
817   if (!A || !B)
818     return nullptr;
819
820   APFloat AVal = mdconst::extract<ConstantFP>(A->getOperand(0))->getValueAPF();
821   APFloat BVal = mdconst::extract<ConstantFP>(B->getOperand(0))->getValueAPF();
822   if (AVal.compare(BVal) == APFloat::cmpLessThan)
823     return A;
824   return B;
825 }
826
827 static bool isContiguous(const ConstantRange &A, const ConstantRange &B) {
828   return A.getUpper() == B.getLower() || A.getLower() == B.getUpper();
829 }
830
831 static bool canBeMerged(const ConstantRange &A, const ConstantRange &B) {
832   return !A.intersectWith(B).isEmptySet() || isContiguous(A, B);
833 }
834
835 static bool tryMergeRange(SmallVectorImpl<ConstantInt *> &EndPoints,
836                           ConstantInt *Low, ConstantInt *High) {
837   ConstantRange NewRange(Low->getValue(), High->getValue());
838   unsigned Size = EndPoints.size();
839   APInt LB = EndPoints[Size - 2]->getValue();
840   APInt LE = EndPoints[Size - 1]->getValue();
841   ConstantRange LastRange(LB, LE);
842   if (canBeMerged(NewRange, LastRange)) {
843     ConstantRange Union = LastRange.unionWith(NewRange);
844     Type *Ty = High->getType();
845     EndPoints[Size - 2] =
846         cast<ConstantInt>(ConstantInt::get(Ty, Union.getLower()));
847     EndPoints[Size - 1] =
848         cast<ConstantInt>(ConstantInt::get(Ty, Union.getUpper()));
849     return true;
850   }
851   return false;
852 }
853
854 static void addRange(SmallVectorImpl<ConstantInt *> &EndPoints,
855                      ConstantInt *Low, ConstantInt *High) {
856   if (!EndPoints.empty())
857     if (tryMergeRange(EndPoints, Low, High))
858       return;
859
860   EndPoints.push_back(Low);
861   EndPoints.push_back(High);
862 }
863
864 MDNode *MDNode::getMostGenericRange(MDNode *A, MDNode *B) {
865   // Given two ranges, we want to compute the union of the ranges. This
866   // is slightly complitade by having to combine the intervals and merge
867   // the ones that overlap.
868
869   if (!A || !B)
870     return nullptr;
871
872   if (A == B)
873     return A;
874
875   // First, walk both lists in older of the lower boundary of each interval.
876   // At each step, try to merge the new interval to the last one we adedd.
877   SmallVector<ConstantInt *, 4> EndPoints;
878   int AI = 0;
879   int BI = 0;
880   int AN = A->getNumOperands() / 2;
881   int BN = B->getNumOperands() / 2;
882   while (AI < AN && BI < BN) {
883     ConstantInt *ALow = mdconst::extract<ConstantInt>(A->getOperand(2 * AI));
884     ConstantInt *BLow = mdconst::extract<ConstantInt>(B->getOperand(2 * BI));
885
886     if (ALow->getValue().slt(BLow->getValue())) {
887       addRange(EndPoints, ALow,
888                mdconst::extract<ConstantInt>(A->getOperand(2 * AI + 1)));
889       ++AI;
890     } else {
891       addRange(EndPoints, BLow,
892                mdconst::extract<ConstantInt>(B->getOperand(2 * BI + 1)));
893       ++BI;
894     }
895   }
896   while (AI < AN) {
897     addRange(EndPoints, mdconst::extract<ConstantInt>(A->getOperand(2 * AI)),
898              mdconst::extract<ConstantInt>(A->getOperand(2 * AI + 1)));
899     ++AI;
900   }
901   while (BI < BN) {
902     addRange(EndPoints, mdconst::extract<ConstantInt>(B->getOperand(2 * BI)),
903              mdconst::extract<ConstantInt>(B->getOperand(2 * BI + 1)));
904     ++BI;
905   }
906
907   // If we have more than 2 ranges (4 endpoints) we have to try to merge
908   // the last and first ones.
909   unsigned Size = EndPoints.size();
910   if (Size > 4) {
911     ConstantInt *FB = EndPoints[0];
912     ConstantInt *FE = EndPoints[1];
913     if (tryMergeRange(EndPoints, FB, FE)) {
914       for (unsigned i = 0; i < Size - 2; ++i) {
915         EndPoints[i] = EndPoints[i + 2];
916       }
917       EndPoints.resize(Size - 2);
918     }
919   }
920
921   // If in the end we have a single range, it is possible that it is now the
922   // full range. Just drop the metadata in that case.
923   if (EndPoints.size() == 2) {
924     ConstantRange Range(EndPoints[0]->getValue(), EndPoints[1]->getValue());
925     if (Range.isFullSet())
926       return nullptr;
927   }
928
929   SmallVector<Metadata *, 4> MDs;
930   MDs.reserve(EndPoints.size());
931   for (auto *I : EndPoints)
932     MDs.push_back(ConstantAsMetadata::get(I));
933   return MDNode::get(A->getContext(), MDs);
934 }
935
936 //===----------------------------------------------------------------------===//
937 // NamedMDNode implementation.
938 //
939
940 static SmallVector<TrackingMDRef, 4> &getNMDOps(void *Operands) {
941   return *(SmallVector<TrackingMDRef, 4> *)Operands;
942 }
943
944 NamedMDNode::NamedMDNode(const Twine &N)
945     : Name(N.str()), Parent(nullptr),
946       Operands(new SmallVector<TrackingMDRef, 4>()) {}
947
948 NamedMDNode::~NamedMDNode() {
949   dropAllReferences();
950   delete &getNMDOps(Operands);
951 }
952
953 unsigned NamedMDNode::getNumOperands() const {
954   return (unsigned)getNMDOps(Operands).size();
955 }
956
957 MDNode *NamedMDNode::getOperand(unsigned i) const {
958   assert(i < getNumOperands() && "Invalid Operand number!");
959   auto *N = getNMDOps(Operands)[i].get();
960   return cast_or_null<MDNode>(N);
961 }
962
963 void NamedMDNode::addOperand(MDNode *M) { getNMDOps(Operands).emplace_back(M); }
964
965 void NamedMDNode::setOperand(unsigned I, MDNode *New) {
966   assert(I < getNumOperands() && "Invalid operand number");
967   getNMDOps(Operands)[I].reset(New);
968 }
969
970 void NamedMDNode::eraseFromParent() {
971   getParent()->eraseNamedMetadata(this);
972 }
973
974 void NamedMDNode::dropAllReferences() {
975   getNMDOps(Operands).clear();
976 }
977
978 StringRef NamedMDNode::getName() const {
979   return StringRef(Name);
980 }
981
982 //===----------------------------------------------------------------------===//
983 // Instruction Metadata method implementations.
984 //
985
986 void Instruction::setMetadata(StringRef Kind, MDNode *Node) {
987   if (!Node && !hasMetadata())
988     return;
989   setMetadata(getContext().getMDKindID(Kind), Node);
990 }
991
992 MDNode *Instruction::getMetadataImpl(StringRef Kind) const {
993   return getMetadataImpl(getContext().getMDKindID(Kind));
994 }
995
996 void Instruction::dropUnknownMetadata(ArrayRef<unsigned> KnownIDs) {
997   SmallSet<unsigned, 5> KnownSet;
998   KnownSet.insert(KnownIDs.begin(), KnownIDs.end());
999
1000   // Drop debug if needed
1001   if (KnownSet.erase(LLVMContext::MD_dbg))
1002     DbgLoc = DebugLoc();
1003
1004   if (!hasMetadataHashEntry())
1005     return; // Nothing to remove!
1006
1007   DenseMap<const Instruction *, LLVMContextImpl::MDMapTy> &MetadataStore =
1008       getContext().pImpl->MetadataStore;
1009
1010   if (KnownSet.empty()) {
1011     // Just drop our entry at the store.
1012     MetadataStore.erase(this);
1013     setHasMetadataHashEntry(false);
1014     return;
1015   }
1016
1017   LLVMContextImpl::MDMapTy &Info = MetadataStore[this];
1018   unsigned I;
1019   unsigned E;
1020   // Walk the array and drop any metadata we don't know.
1021   for (I = 0, E = Info.size(); I != E;) {
1022     if (KnownSet.count(Info[I].first)) {
1023       ++I;
1024       continue;
1025     }
1026
1027     Info[I] = std::move(Info.back());
1028     Info.pop_back();
1029     --E;
1030   }
1031   assert(E == Info.size());
1032
1033   if (E == 0) {
1034     // Drop our entry at the store.
1035     MetadataStore.erase(this);
1036     setHasMetadataHashEntry(false);
1037   }
1038 }
1039
1040 /// setMetadata - Set the metadata of of the specified kind to the specified
1041 /// node.  This updates/replaces metadata if already present, or removes it if
1042 /// Node is null.
1043 void Instruction::setMetadata(unsigned KindID, MDNode *Node) {
1044   if (!Node && !hasMetadata())
1045     return;
1046
1047   // Handle 'dbg' as a special case since it is not stored in the hash table.
1048   if (KindID == LLVMContext::MD_dbg) {
1049     DbgLoc = DebugLoc::getFromDILocation(Node);
1050     return;
1051   }
1052   
1053   // Handle the case when we're adding/updating metadata on an instruction.
1054   if (Node) {
1055     LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this];
1056     assert(!Info.empty() == hasMetadataHashEntry() &&
1057            "HasMetadata bit is wonked");
1058     if (Info.empty()) {
1059       setHasMetadataHashEntry(true);
1060     } else {
1061       // Handle replacement of an existing value.
1062       for (auto &P : Info)
1063         if (P.first == KindID) {
1064           P.second.reset(Node);
1065           return;
1066         }
1067     }
1068
1069     // No replacement, just add it to the list.
1070     Info.emplace_back(std::piecewise_construct, std::make_tuple(KindID),
1071                       std::make_tuple(Node));
1072     return;
1073   }
1074
1075   // Otherwise, we're removing metadata from an instruction.
1076   assert((hasMetadataHashEntry() ==
1077           (getContext().pImpl->MetadataStore.count(this) > 0)) &&
1078          "HasMetadata bit out of date!");
1079   if (!hasMetadataHashEntry())
1080     return;  // Nothing to remove!
1081   LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this];
1082
1083   // Common case is removing the only entry.
1084   if (Info.size() == 1 && Info[0].first == KindID) {
1085     getContext().pImpl->MetadataStore.erase(this);
1086     setHasMetadataHashEntry(false);
1087     return;
1088   }
1089
1090   // Handle removal of an existing value.
1091   for (unsigned i = 0, e = Info.size(); i != e; ++i)
1092     if (Info[i].first == KindID) {
1093       Info[i] = std::move(Info.back());
1094       Info.pop_back();
1095       assert(!Info.empty() && "Removing last entry should be handled above");
1096       return;
1097     }
1098   // Otherwise, removing an entry that doesn't exist on the instruction.
1099 }
1100
1101 void Instruction::setAAMetadata(const AAMDNodes &N) {
1102   setMetadata(LLVMContext::MD_tbaa, N.TBAA);
1103   setMetadata(LLVMContext::MD_alias_scope, N.Scope);
1104   setMetadata(LLVMContext::MD_noalias, N.NoAlias);
1105 }
1106
1107 MDNode *Instruction::getMetadataImpl(unsigned KindID) const {
1108   // Handle 'dbg' as a special case since it is not stored in the hash table.
1109   if (KindID == LLVMContext::MD_dbg)
1110     return DbgLoc.getAsMDNode();
1111
1112   if (!hasMetadataHashEntry()) return nullptr;
1113   
1114   LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this];
1115   assert(!Info.empty() && "bit out of sync with hash table");
1116
1117   for (const auto &I : Info)
1118     if (I.first == KindID)
1119       return I.second;
1120   return nullptr;
1121 }
1122
1123 void Instruction::getAllMetadataImpl(
1124     SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
1125   Result.clear();
1126   
1127   // Handle 'dbg' as a special case since it is not stored in the hash table.
1128   if (!DbgLoc.isUnknown()) {
1129     Result.push_back(
1130         std::make_pair((unsigned)LLVMContext::MD_dbg, DbgLoc.getAsMDNode()));
1131     if (!hasMetadataHashEntry()) return;
1132   }
1133   
1134   assert(hasMetadataHashEntry() &&
1135          getContext().pImpl->MetadataStore.count(this) &&
1136          "Shouldn't have called this");
1137   const LLVMContextImpl::MDMapTy &Info =
1138     getContext().pImpl->MetadataStore.find(this)->second;
1139   assert(!Info.empty() && "Shouldn't have called this");
1140
1141   Result.reserve(Result.size() + Info.size());
1142   for (auto &I : Info)
1143     Result.push_back(std::make_pair(I.first, cast<MDNode>(I.second.get())));
1144
1145   // Sort the resulting array so it is stable.
1146   if (Result.size() > 1)
1147     array_pod_sort(Result.begin(), Result.end());
1148 }
1149
1150 void Instruction::getAllMetadataOtherThanDebugLocImpl(
1151     SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
1152   Result.clear();
1153   assert(hasMetadataHashEntry() &&
1154          getContext().pImpl->MetadataStore.count(this) &&
1155          "Shouldn't have called this");
1156   const LLVMContextImpl::MDMapTy &Info =
1157     getContext().pImpl->MetadataStore.find(this)->second;
1158   assert(!Info.empty() && "Shouldn't have called this");
1159   Result.reserve(Result.size() + Info.size());
1160   for (auto &I : Info)
1161     Result.push_back(std::make_pair(I.first, cast<MDNode>(I.second.get())));
1162
1163   // Sort the resulting array so it is stable.
1164   if (Result.size() > 1)
1165     array_pod_sort(Result.begin(), Result.end());
1166 }
1167
1168 /// clearMetadataHashEntries - Clear all hashtable-based metadata from
1169 /// this instruction.
1170 void Instruction::clearMetadataHashEntries() {
1171   assert(hasMetadataHashEntry() && "Caller should check");
1172   getContext().pImpl->MetadataStore.erase(this);
1173   setHasMetadataHashEntry(false);
1174 }