1//===- Metadata.cpp - Implement Metadata classes --------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the Metadata classes.
10//
11//===----------------------------------------------------------------------===//
12
13#include "LLVMContextImpl.h"
14#include "MetadataImpl.h"
15#include "SymbolTableListTraitsImpl.h"
16#include "llvm/ADT/APFloat.h"
17#include "llvm/ADT/APInt.h"
18#include "llvm/ADT/ArrayRef.h"
19#include "llvm/ADT/DenseSet.h"
20#include "llvm/ADT/None.h"
21#include "llvm/ADT/STLExtras.h"
22#include "llvm/ADT/SetVector.h"
23#include "llvm/ADT/SmallPtrSet.h"
24#include "llvm/ADT/SmallSet.h"
25#include "llvm/ADT/SmallVector.h"
26#include "llvm/ADT/StringMap.h"
27#include "llvm/ADT/StringRef.h"
28#include "llvm/ADT/Twine.h"
29#include "llvm/IR/Argument.h"
30#include "llvm/IR/BasicBlock.h"
31#include "llvm/IR/Constant.h"
32#include "llvm/IR/ConstantRange.h"
33#include "llvm/IR/Constants.h"
34#include "llvm/IR/DebugInfoMetadata.h"
35#include "llvm/IR/DebugLoc.h"
36#include "llvm/IR/Function.h"
37#include "llvm/IR/GlobalObject.h"
38#include "llvm/IR/GlobalVariable.h"
39#include "llvm/IR/Instruction.h"
40#include "llvm/IR/LLVMContext.h"
41#include "llvm/IR/Metadata.h"
42#include "llvm/IR/Module.h"
43#include "llvm/IR/TrackingMDRef.h"
44#include "llvm/IR/Type.h"
45#include "llvm/IR/Value.h"
46#include "llvm/IR/ValueHandle.h"
47#include "llvm/Support/Casting.h"
48#include "llvm/Support/ErrorHandling.h"
49#include "llvm/Support/MathExtras.h"
50#include <algorithm>
51#include <cassert>
52#include <cstddef>
53#include <cstdint>
54#include <iterator>
55#include <tuple>
56#include <type_traits>
57#include <utility>
58#include <vector>
59
60using namespace llvm;
61
62MetadataAsValue::MetadataAsValue(Type *Ty, Metadata *MD)
63    : Value(Ty, MetadataAsValueVal), MD(MD) {
64  track();
65}
66
67MetadataAsValue::~MetadataAsValue() {
68  getType()->getContext().pImpl->MetadataAsValues.erase(MD);
69  untrack();
70}
71
72/// Canonicalize metadata arguments to intrinsics.
73///
74/// To support bitcode upgrades (and assembly semantic sugar) for \a
75/// MetadataAsValue, we need to canonicalize certain metadata.
76///
77///   - nullptr is replaced by an empty MDNode.
78///   - An MDNode with a single null operand is replaced by an empty MDNode.
79///   - An MDNode whose only operand is a \a ConstantAsMetadata gets skipped.
80///
81/// This maintains readability of bitcode from when metadata was a type of
82/// value, and these bridges were unnecessary.
83static Metadata *canonicalizeMetadataForValue(LLVMContext &Context,
84                                              Metadata *MD) {
85  if (!MD)
86    // !{}
87    return MDNode::get(Context, None);
88
89  // Return early if this isn't a single-operand MDNode.
90  auto *N = dyn_cast<MDNode>(MD);
91  if (!N || N->getNumOperands() != 1)
92    return MD;
93
94  if (!N->getOperand(0))
95    // !{}
96    return MDNode::get(Context, None);
97
98  if (auto *C = dyn_cast<ConstantAsMetadata>(N->getOperand(0)))
99    // Look through the MDNode.
100    return C;
101
102  return MD;
103}
104
105MetadataAsValue *MetadataAsValue::get(LLVMContext &Context, Metadata *MD) {
106  MD = canonicalizeMetadataForValue(Context, MD);
107  auto *&Entry = Context.pImpl->MetadataAsValues[MD];
108  if (!Entry)
109    Entry = new MetadataAsValue(Type::getMetadataTy(Context), MD);
110  return Entry;
111}
112
113MetadataAsValue *MetadataAsValue::getIfExists(LLVMContext &Context,
114                                              Metadata *MD) {
115  MD = canonicalizeMetadataForValue(Context, MD);
116  auto &Store = Context.pImpl->MetadataAsValues;
117  return Store.lookup(MD);
118}
119
120void MetadataAsValue::handleChangedMetadata(Metadata *MD) {
121  LLVMContext &Context = getContext();
122  MD = canonicalizeMetadataForValue(Context, MD);
123  auto &Store = Context.pImpl->MetadataAsValues;
124
125  // Stop tracking the old metadata.
126  Store.erase(this->MD);
127  untrack();
128  this->MD = nullptr;
129
130  // Start tracking MD, or RAUW if necessary.
131  auto *&Entry = Store[MD];
132  if (Entry) {
133    replaceAllUsesWith(Entry);
134    delete this;
135    return;
136  }
137
138  this->MD = MD;
139  track();
140  Entry = this;
141}
142
143void MetadataAsValue::track() {
144  if (MD)
145    MetadataTracking::track(&MD, *MD, *this);
146}
147
148void MetadataAsValue::untrack() {
149  if (MD)
150    MetadataTracking::untrack(MD);
151}
152
153bool MetadataTracking::track(void *Ref, Metadata &MD, OwnerTy Owner) {
154  assert(Ref && "Expected live reference");
155  assert((Owner || *static_cast<Metadata **>(Ref) == &MD) &&
156         "Reference without owner must be direct");
157  if (auto *R = ReplaceableMetadataImpl::getOrCreate(MD)) {
158    R->addRef(Ref, Owner);
159    return true;
160  }
161  if (auto *PH = dyn_cast<DistinctMDOperandPlaceholder>(&MD)) {
162    assert(!PH->Use && "Placeholders can only be used once");
163    assert(!Owner && "Unexpected callback to owner");
164    PH->Use = static_cast<Metadata **>(Ref);
165    return true;
166  }
167  return false;
168}
169
170void MetadataTracking::untrack(void *Ref, Metadata &MD) {
171  assert(Ref && "Expected live reference");
172  if (auto *R = ReplaceableMetadataImpl::getIfExists(MD))
173    R->dropRef(Ref);
174  else if (auto *PH = dyn_cast<DistinctMDOperandPlaceholder>(&MD))
175    PH->Use = nullptr;
176}
177
178bool MetadataTracking::retrack(void *Ref, Metadata &MD, void *New) {
179  assert(Ref && "Expected live reference");
180  assert(New && "Expected live reference");
181  assert(Ref != New && "Expected change");
182  if (auto *R = ReplaceableMetadataImpl::getIfExists(MD)) {
183    R->moveRef(Ref, New, MD);
184    return true;
185  }
186  assert(!isa<DistinctMDOperandPlaceholder>(MD) &&
187         "Unexpected move of an MDOperand");
188  assert(!isReplaceable(MD) &&
189         "Expected un-replaceable metadata, since we didn't move a reference");
190  return false;
191}
192
193bool MetadataTracking::isReplaceable(const Metadata &MD) {
194  return ReplaceableMetadataImpl::isReplaceable(MD);
195}
196
197void ReplaceableMetadataImpl::addRef(void *Ref, OwnerTy Owner) {
198  bool WasInserted =
199      UseMap.insert(std::make_pair(Ref, std::make_pair(Owner, NextIndex)))
200          .second;
201  (void)WasInserted;
202  assert(WasInserted && "Expected to add a reference");
203
204  ++NextIndex;
205  assert(NextIndex != 0 && "Unexpected overflow");
206}
207
208void ReplaceableMetadataImpl::dropRef(void *Ref) {
209  bool WasErased = UseMap.erase(Ref);
210  (void)WasErased;
211  assert(WasErased && "Expected to drop a reference");
212}
213
214void ReplaceableMetadataImpl::moveRef(void *Ref, void *New,
215                                      const Metadata &MD) {
216  auto I = UseMap.find(Ref);
217  assert(I != UseMap.end() && "Expected to move a reference");
218  auto OwnerAndIndex = I->second;
219  UseMap.erase(I);
220  bool WasInserted = UseMap.insert(std::make_pair(New, OwnerAndIndex)).second;
221  (void)WasInserted;
222  assert(WasInserted && "Expected to add a reference");
223
224  // Check that the references are direct if there's no owner.
225  (void)MD;
226  assert((OwnerAndIndex.first || *static_cast<Metadata **>(Ref) == &MD) &&
227         "Reference without owner must be direct");
228  assert((OwnerAndIndex.first || *static_cast<Metadata **>(New) == &MD) &&
229         "Reference without owner must be direct");
230}
231
232void ReplaceableMetadataImpl::replaceAllUsesWith(Metadata *MD) {
233  if (UseMap.empty())
234    return;
235
236  // Copy out uses since UseMap will get touched below.
237  using UseTy = std::pair<void *, std::pair<OwnerTy, uint64_t>>;
238  SmallVector<UseTy, 8> Uses(UseMap.begin(), UseMap.end());
239  llvm::sort(Uses, [](const UseTy &L, const UseTy &R) {
240    return L.second.second < R.second.second;
241  });
242  for (const auto &Pair : Uses) {
243    // Check that this Ref hasn't disappeared after RAUW (when updating a
244    // previous Ref).
245    if (!UseMap.count(Pair.first))
246      continue;
247
248    OwnerTy Owner = Pair.second.first;
249    if (!Owner) {
250      // Update unowned tracking references directly.
251      Metadata *&Ref = *static_cast<Metadata **>(Pair.first);
252      Ref = MD;
253      if (MD)
254        MetadataTracking::track(Ref);
255      UseMap.erase(Pair.first);
256      continue;
257    }
258
259    // Check for MetadataAsValue.
260    if (Owner.is<MetadataAsValue *>()) {
261      Owner.get<MetadataAsValue *>()->handleChangedMetadata(MD);
262      continue;
263    }
264
265    // There's a Metadata owner -- dispatch.
266    Metadata *OwnerMD = Owner.get<Metadata *>();
267    switch (OwnerMD->getMetadataID()) {
268#define HANDLE_METADATA_LEAF(CLASS)                                            \
269  case Metadata::CLASS##Kind:                                                  \
270    cast<CLASS>(OwnerMD)->handleChangedOperand(Pair.first, MD);                \
271    continue;
272#include "llvm/IR/Metadata.def"
273    default:
274      llvm_unreachable("Invalid metadata subclass");
275    }
276  }
277  assert(UseMap.empty() && "Expected all uses to be replaced");
278}
279
280void ReplaceableMetadataImpl::resolveAllUses(bool ResolveUsers) {
281  if (UseMap.empty())
282    return;
283
284  if (!ResolveUsers) {
285    UseMap.clear();
286    return;
287  }
288
289  // Copy out uses since UseMap could get touched below.
290  using UseTy = std::pair<void *, std::pair<OwnerTy, uint64_t>>;
291  SmallVector<UseTy, 8> Uses(UseMap.begin(), UseMap.end());
292  llvm::sort(Uses, [](const UseTy &L, const UseTy &R) {
293    return L.second.second < R.second.second;
294  });
295  UseMap.clear();
296  for (const auto &Pair : Uses) {
297    auto Owner = Pair.second.first;
298    if (!Owner)
299      continue;
300    if (Owner.is<MetadataAsValue *>())
301      continue;
302
303    // Resolve MDNodes that point at this.
304    auto *OwnerMD = dyn_cast<MDNode>(Owner.get<Metadata *>());
305    if (!OwnerMD)
306      continue;
307    if (OwnerMD->isResolved())
308      continue;
309    OwnerMD->decrementUnresolvedOperandCount();
310  }
311}
312
313ReplaceableMetadataImpl *ReplaceableMetadataImpl::getOrCreate(Metadata &MD) {
314  if (auto *N = dyn_cast<MDNode>(&MD))
315    return N->isResolved() ? nullptr : N->Context.getOrCreateReplaceableUses();
316  return dyn_cast<ValueAsMetadata>(&MD);
317}
318
319ReplaceableMetadataImpl *ReplaceableMetadataImpl::getIfExists(Metadata &MD) {
320  if (auto *N = dyn_cast<MDNode>(&MD))
321    return N->isResolved() ? nullptr : N->Context.getReplaceableUses();
322  return dyn_cast<ValueAsMetadata>(&MD);
323}
324
325bool ReplaceableMetadataImpl::isReplaceable(const Metadata &MD) {
326  if (auto *N = dyn_cast<MDNode>(&MD))
327    return !N->isResolved();
328  return dyn_cast<ValueAsMetadata>(&MD);
329}
330
331static DISubprogram *getLocalFunctionMetadata(Value *V) {
332  assert(V && "Expected value");
333  if (auto *A = dyn_cast<Argument>(V)) {
334    if (auto *Fn = A->getParent())
335      return Fn->getSubprogram();
336    return nullptr;
337  }
338
339  if (BasicBlock *BB = cast<Instruction>(V)->getParent()) {
340    if (auto *Fn = BB->getParent())
341      return Fn->getSubprogram();
342    return nullptr;
343  }
344
345  return nullptr;
346}
347
348ValueAsMetadata *ValueAsMetadata::get(Value *V) {
349  assert(V && "Unexpected null Value");
350
351  auto &Context = V->getContext();
352  auto *&Entry = Context.pImpl->ValuesAsMetadata[V];
353  if (!Entry) {
354    assert((isa<Constant>(V) || isa<Argument>(V) || isa<Instruction>(V)) &&
355           "Expected constant or function-local value");
356    assert(!V->IsUsedByMD && "Expected this to be the only metadata use");
357    V->IsUsedByMD = true;
358    if (auto *C = dyn_cast<Constant>(V))
359      Entry = new ConstantAsMetadata(C);
360    else
361      Entry = new LocalAsMetadata(V);
362  }
363
364  return Entry;
365}
366
367ValueAsMetadata *ValueAsMetadata::getIfExists(Value *V) {
368  assert(V && "Unexpected null Value");
369  return V->getContext().pImpl->ValuesAsMetadata.lookup(V);
370}
371
372void ValueAsMetadata::handleDeletion(Value *V) {
373  assert(V && "Expected valid value");
374
375  auto &Store = V->getType()->getContext().pImpl->ValuesAsMetadata;
376  auto I = Store.find(V);
377  if (I == Store.end())
378    return;
379
380  // Remove old entry from the map.
381  ValueAsMetadata *MD = I->second;
382  assert(MD && "Expected valid metadata");
383  assert(MD->getValue() == V && "Expected valid mapping");
384  Store.erase(I);
385
386  // Delete the metadata.
387  MD->replaceAllUsesWith(nullptr);
388  delete MD;
389}
390
391void ValueAsMetadata::handleRAUW(Value *From, Value *To) {
392  assert(From && "Expected valid value");
393  assert(To && "Expected valid value");
394  assert(From != To && "Expected changed value");
395  assert(From->getType() == To->getType() && "Unexpected type change");
396
397  LLVMContext &Context = From->getType()->getContext();
398  auto &Store = Context.pImpl->ValuesAsMetadata;
399  auto I = Store.find(From);
400  if (I == Store.end()) {
401    assert(!From->IsUsedByMD && "Expected From not to be used by metadata");
402    return;
403  }
404
405  // Remove old entry from the map.
406  assert(From->IsUsedByMD && "Expected From to be used by metadata");
407  From->IsUsedByMD = false;
408  ValueAsMetadata *MD = I->second;
409  assert(MD && "Expected valid metadata");
410  assert(MD->getValue() == From && "Expected valid mapping");
411  Store.erase(I);
412
413  if (isa<LocalAsMetadata>(MD)) {
414    if (auto *C = dyn_cast<Constant>(To)) {
415      // Local became a constant.
416      MD->replaceAllUsesWith(ConstantAsMetadata::get(C));
417      delete MD;
418      return;
419    }
420    if (getLocalFunctionMetadata(From) && getLocalFunctionMetadata(To) &&
421        getLocalFunctionMetadata(From) != getLocalFunctionMetadata(To)) {
422      // DISubprogram changed.
423      MD->replaceAllUsesWith(nullptr);
424      delete MD;
425      return;
426    }
427  } else if (!isa<Constant>(To)) {
428    // Changed to function-local value.
429    MD->replaceAllUsesWith(nullptr);
430    delete MD;
431    return;
432  }
433
434  auto *&Entry = Store[To];
435  if (Entry) {
436    // The target already exists.
437    MD->replaceAllUsesWith(Entry);
438    delete MD;
439    return;
440  }
441
442  // Update MD in place (and update the map entry).
443  assert(!To->IsUsedByMD && "Expected this to be the only metadata use");
444  To->IsUsedByMD = true;
445  MD->V = To;
446  Entry = MD;
447}
448
449//===----------------------------------------------------------------------===//
450// MDString implementation.
451//
452
453MDString *MDString::get(LLVMContext &Context, StringRef Str) {
454  auto &Store = Context.pImpl->MDStringCache;
455  auto I = Store.try_emplace(Str);
456  auto &MapEntry = I.first->getValue();
457  if (!I.second)
458    return &MapEntry;
459  MapEntry.Entry = &*I.first;
460  return &MapEntry;
461}
462
463StringRef MDString::getString() const {
464  assert(Entry && "Expected to find string map entry");
465  return Entry->first();
466}
467
468//===----------------------------------------------------------------------===//
469// MDNode implementation.
470//
471
472// Assert that the MDNode types will not be unaligned by the objects
473// prepended to them.
474#define HANDLE_MDNODE_LEAF(CLASS)                                              \
475  static_assert(                                                               \
476      alignof(uint64_t) >= alignof(CLASS),                                     \
477      "Alignment is insufficient after objects prepended to " #CLASS);
478#include "llvm/IR/Metadata.def"
479
480void *MDNode::operator new(size_t Size, unsigned NumOps) {
481  size_t OpSize = NumOps * sizeof(MDOperand);
482  // uint64_t is the most aligned type we need support (ensured by static_assert
483  // above)
484  OpSize = alignTo(OpSize, alignof(uint64_t));
485  void *Ptr = reinterpret_cast<char *>(::operator new(OpSize + Size)) + OpSize;
486  MDOperand *O = static_cast<MDOperand *>(Ptr);
487  for (MDOperand *E = O - NumOps; O != E; --O)
488    (void)new (O - 1) MDOperand;
489  return Ptr;
490}
491
492// Repress memory sanitization, due to use-after-destroy by operator
493// delete. Bug report 24578 identifies this issue.
494LLVM_NO_SANITIZE_MEMORY_ATTRIBUTE void MDNode::operator delete(void *Mem) {
495  MDNode *N = static_cast<MDNode *>(Mem);
496  size_t OpSize = N->NumOperands * sizeof(MDOperand);
497  OpSize = alignTo(OpSize, alignof(uint64_t));
498
499  MDOperand *O = static_cast<MDOperand *>(Mem);
500  for (MDOperand *E = O - N->NumOperands; O != E; --O)
501    (O - 1)->~MDOperand();
502  ::operator delete(reinterpret_cast<char *>(Mem) - OpSize);
503}
504
505MDNode::MDNode(LLVMContext &Context, unsigned ID, StorageType Storage,
506               ArrayRef<Metadata *> Ops1, ArrayRef<Metadata *> Ops2)
507    : Metadata(ID, Storage), NumOperands(Ops1.size() + Ops2.size()),
508      NumUnresolved(0), Context(Context) {
509  unsigned Op = 0;
510  for (Metadata *MD : Ops1)
511    setOperand(Op++, MD);
512  for (Metadata *MD : Ops2)
513    setOperand(Op++, MD);
514
515  if (!isUniqued())
516    return;
517
518  // Count the unresolved operands.  If there are any, RAUW support will be
519  // added lazily on first reference.
520  countUnresolvedOperands();
521}
522
523TempMDNode MDNode::clone() const {
524  switch (getMetadataID()) {
525  default:
526    llvm_unreachable("Invalid MDNode subclass");
527#define HANDLE_MDNODE_LEAF(CLASS)                                              \
528  case CLASS##Kind:                                                            \
529    return cast<CLASS>(this)->cloneImpl();
530#include "llvm/IR/Metadata.def"
531  }
532}
533
534static bool isOperandUnresolved(Metadata *Op) {
535  if (auto *N = dyn_cast_or_null<MDNode>(Op))
536    return !N->isResolved();
537  return false;
538}
539
540void MDNode::countUnresolvedOperands() {
541  assert(NumUnresolved == 0 && "Expected unresolved ops to be uncounted");
542  assert(isUniqued() && "Expected this to be uniqued");
543  NumUnresolved = count_if(operands(), isOperandUnresolved);
544}
545
546void MDNode::makeUniqued() {
547  assert(isTemporary() && "Expected this to be temporary");
548  assert(!isResolved() && "Expected this to be unresolved");
549
550  // Enable uniquing callbacks.
551  for (auto &Op : mutable_operands())
552    Op.reset(Op.get(), this);
553
554  // Make this 'uniqued'.
555  Storage = Uniqued;
556  countUnresolvedOperands();
557  if (!NumUnresolved) {
558    dropReplaceableUses();
559    assert(isResolved() && "Expected this to be resolved");
560  }
561
562  assert(isUniqued() && "Expected this to be uniqued");
563}
564
565void MDNode::makeDistinct() {
566  assert(isTemporary() && "Expected this to be temporary");
567  assert(!isResolved() && "Expected this to be unresolved");
568
569  // Drop RAUW support and store as a distinct node.
570  dropReplaceableUses();
571  storeDistinctInContext();
572
573  assert(isDistinct() && "Expected this to be distinct");
574  assert(isResolved() && "Expected this to be resolved");
575}
576
577void MDNode::resolve() {
578  assert(isUniqued() && "Expected this to be uniqued");
579  assert(!isResolved() && "Expected this to be unresolved");
580
581  NumUnresolved = 0;
582  dropReplaceableUses();
583
584  assert(isResolved() && "Expected this to be resolved");
585}
586
587void MDNode::dropReplaceableUses() {
588  assert(!NumUnresolved && "Unexpected unresolved operand");
589
590  // Drop any RAUW support.
591  if (Context.hasReplaceableUses())
592    Context.takeReplaceableUses()->resolveAllUses();
593}
594
595void MDNode::resolveAfterOperandChange(Metadata *Old, Metadata *New) {
596  assert(isUniqued() && "Expected this to be uniqued");
597  assert(NumUnresolved != 0 && "Expected unresolved operands");
598
599  // Check if an operand was resolved.
600  if (!isOperandUnresolved(Old)) {
601    if (isOperandUnresolved(New))
602      // An operand was un-resolved!
603      ++NumUnresolved;
604  } else if (!isOperandUnresolved(New))
605    decrementUnresolvedOperandCount();
606}
607
608void MDNode::decrementUnresolvedOperandCount() {
609  assert(!isResolved() && "Expected this to be unresolved");
610  if (isTemporary())
611    return;
612
613  assert(isUniqued() && "Expected this to be uniqued");
614  if (--NumUnresolved)
615    return;
616
617  // Last unresolved operand has just been resolved.
618  dropReplaceableUses();
619  assert(isResolved() && "Expected this to become resolved");
620}
621
622void MDNode::resolveCycles() {
623  if (isResolved())
624    return;
625
626  // Resolve this node immediately.
627  resolve();
628
629  // Resolve all operands.
630  for (const auto &Op : operands()) {
631    auto *N = dyn_cast_or_null<MDNode>(Op);
632    if (!N)
633      continue;
634
635    assert(!N->isTemporary() &&
636           "Expected all forward declarations to be resolved");
637    if (!N->isResolved())
638      N->resolveCycles();
639  }
640}
641
642static bool hasSelfReference(MDNode *N) {
643  for (Metadata *MD : N->operands())
644    if (MD == N)
645      return true;
646  return false;
647}
648
649MDNode *MDNode::replaceWithPermanentImpl() {
650  switch (getMetadataID()) {
651  default:
652    // If this type isn't uniquable, replace with a distinct node.
653    return replaceWithDistinctImpl();
654
655#define HANDLE_MDNODE_LEAF_UNIQUABLE(CLASS)                                    \
656  case CLASS##Kind:                                                            \
657    break;
658#include "llvm/IR/Metadata.def"
659  }
660
661  // Even if this type is uniquable, self-references have to be distinct.
662  if (hasSelfReference(this))
663    return replaceWithDistinctImpl();
664  return replaceWithUniquedImpl();
665}
666
667MDNode *MDNode::replaceWithUniquedImpl() {
668  // Try to uniquify in place.
669  MDNode *UniquedNode = uniquify();
670
671  if (UniquedNode == this) {
672    makeUniqued();
673    return this;
674  }
675
676  // Collision, so RAUW instead.
677  replaceAllUsesWith(UniquedNode);
678  deleteAsSubclass();
679  return UniquedNode;
680}
681
682MDNode *MDNode::replaceWithDistinctImpl() {
683  makeDistinct();
684  return this;
685}
686
687void MDTuple::recalculateHash() {
688  setHash(MDTupleInfo::KeyTy::calculateHash(this));
689}
690
691void MDNode::dropAllReferences() {
692  for (unsigned I = 0, E = NumOperands; I != E; ++I)
693    setOperand(I, nullptr);
694  if (Context.hasReplaceableUses()) {
695    Context.getReplaceableUses()->resolveAllUses(/* ResolveUsers */ false);
696    (void)Context.takeReplaceableUses();
697  }
698}
699
700void MDNode::handleChangedOperand(void *Ref, Metadata *New) {
701  unsigned Op = static_cast<MDOperand *>(Ref) - op_begin();
702  assert(Op < getNumOperands() && "Expected valid operand");
703
704  if (!isUniqued()) {
705    // This node is not uniqued.  Just set the operand and be done with it.
706    setOperand(Op, New);
707    return;
708  }
709
710  // This node is uniqued.
711  eraseFromStore();
712
713  Metadata *Old = getOperand(Op);
714  setOperand(Op, New);
715
716  // Drop uniquing for self-reference cycles and deleted constants.
717  if (New == this || (!New && Old && isa<ConstantAsMetadata>(Old))) {
718    if (!isResolved())
719      resolve();
720    storeDistinctInContext();
721    return;
722  }
723
724  // Re-unique the node.
725  auto *Uniqued = uniquify();
726  if (Uniqued == this) {
727    if (!isResolved())
728      resolveAfterOperandChange(Old, New);
729    return;
730  }
731
732  // Collision.
733  if (!isResolved()) {
734    // Still unresolved, so RAUW.
735    //
736    // First, clear out all operands to prevent any recursion (similar to
737    // dropAllReferences(), but we still need the use-list).
738    for (unsigned O = 0, E = getNumOperands(); O != E; ++O)
739      setOperand(O, nullptr);
740    if (Context.hasReplaceableUses())
741      Context.getReplaceableUses()->replaceAllUsesWith(Uniqued);
742    deleteAsSubclass();
743    return;
744  }
745
746  // Store in non-uniqued form if RAUW isn't possible.
747  storeDistinctInContext();
748}
749
750void MDNode::deleteAsSubclass() {
751  switch (getMetadataID()) {
752  default:
753    llvm_unreachable("Invalid subclass of MDNode");
754#define HANDLE_MDNODE_LEAF(CLASS)                                              \
755  case CLASS##Kind:                                                            \
756    delete cast<CLASS>(this);                                                  \
757    break;
758#include "llvm/IR/Metadata.def"
759  }
760}
761
762template <class T, class InfoT>
763static T *uniquifyImpl(T *N, DenseSet<T *, InfoT> &Store) {
764  if (T *U = getUniqued(Store, N))
765    return U;
766
767  Store.insert(N);
768  return N;
769}
770
771template <class NodeTy> struct MDNode::HasCachedHash {
772  using Yes = char[1];
773  using No = char[2];
774  template <class U, U Val> struct SFINAE {};
775
776  template <class U>
777  static Yes &check(SFINAE<void (U::*)(unsigned), &U::setHash> *);
778  template <class U> static No &check(...);
779
780  static const bool value = sizeof(check<NodeTy>(nullptr)) == sizeof(Yes);
781};
782
783MDNode *MDNode::uniquify() {
784  assert(!hasSelfReference(this) && "Cannot uniquify a self-referencing node");
785
786  // Try to insert into uniquing store.
787  switch (getMetadataID()) {
788  default:
789    llvm_unreachable("Invalid or non-uniquable subclass of MDNode");
790#define HANDLE_MDNODE_LEAF_UNIQUABLE(CLASS)                                    \
791  case CLASS##Kind: {                                                          \
792    CLASS *SubclassThis = cast<CLASS>(this);                                   \
793    std::integral_constant<bool, HasCachedHash<CLASS>::value>                  \
794        ShouldRecalculateHash;                                                 \
795    dispatchRecalculateHash(SubclassThis, ShouldRecalculateHash);              \
796    return uniquifyImpl(SubclassThis, getContext().pImpl->CLASS##s);           \
797  }
798#include "llvm/IR/Metadata.def"
799  }
800}
801
802void MDNode::eraseFromStore() {
803  switch (getMetadataID()) {
804  default:
805    llvm_unreachable("Invalid or non-uniquable subclass of MDNode");
806#define HANDLE_MDNODE_LEAF_UNIQUABLE(CLASS)                                    \
807  case CLASS##Kind:                                                            \
808    getContext().pImpl->CLASS##s.erase(cast<CLASS>(this));                     \
809    break;
810#include "llvm/IR/Metadata.def"
811  }
812}
813
814MDTuple *MDTuple::getImpl(LLVMContext &Context, ArrayRef<Metadata *> MDs,
815                          StorageType Storage, bool ShouldCreate) {
816  unsigned Hash = 0;
817  if (Storage == Uniqued) {
818    MDTupleInfo::KeyTy Key(MDs);
819    if (auto *N = getUniqued(Context.pImpl->MDTuples, Key))
820      return N;
821    if (!ShouldCreate)
822      return nullptr;
823    Hash = Key.getHash();
824  } else {
825    assert(ShouldCreate && "Expected non-uniqued nodes to always be created");
826  }
827
828  return storeImpl(new (MDs.size()) MDTuple(Context, Storage, Hash, MDs),
829                   Storage, Context.pImpl->MDTuples);
830}
831
832void MDNode::deleteTemporary(MDNode *N) {
833  assert(N->isTemporary() && "Expected temporary node");
834  N->replaceAllUsesWith(nullptr);
835  N->deleteAsSubclass();
836}
837
838void MDNode::storeDistinctInContext() {
839  assert(!Context.hasReplaceableUses() && "Unexpected replaceable uses");
840  assert(!NumUnresolved && "Unexpected unresolved nodes");
841  Storage = Distinct;
842  assert(isResolved() && "Expected this to be resolved");
843
844  // Reset the hash.
845  switch (getMetadataID()) {
846  default:
847    llvm_unreachable("Invalid subclass of MDNode");
848#define HANDLE_MDNODE_LEAF(CLASS)                                              \
849  case CLASS##Kind: {                                                          \
850    std::integral_constant<bool, HasCachedHash<CLASS>::value> ShouldResetHash; \
851    dispatchResetHash(cast<CLASS>(this), ShouldResetHash);                     \
852    break;                                                                     \
853  }
854#include "llvm/IR/Metadata.def"
855  }
856
857  getContext().pImpl->DistinctMDNodes.push_back(this);
858}
859
860void MDNode::replaceOperandWith(unsigned I, Metadata *New) {
861  if (getOperand(I) == New)
862    return;
863
864  if (!isUniqued()) {
865    setOperand(I, New);
866    return;
867  }
868
869  handleChangedOperand(mutable_begin() + I, New);
870}
871
872void MDNode::setOperand(unsigned I, Metadata *New) {
873  assert(I < NumOperands);
874  mutable_begin()[I].reset(New, isUniqued() ? this : nullptr);
875}
876
877/// Get a node or a self-reference that looks like it.
878///
879/// Special handling for finding self-references, for use by \a
880/// MDNode::concatenate() and \a MDNode::intersect() to maintain behaviour from
881/// when self-referencing nodes were still uniqued.  If the first operand has
882/// the same operands as \c Ops, return the first operand instead.
883static MDNode *getOrSelfReference(LLVMContext &Context,
884                                  ArrayRef<Metadata *> Ops) {
885  if (!Ops.empty())
886    if (MDNode *N = dyn_cast_or_null<MDNode>(Ops[0]))
887      if (N->getNumOperands() == Ops.size() && N == N->getOperand(0)) {
888        for (unsigned I = 1, E = Ops.size(); I != E; ++I)
889          if (Ops[I] != N->getOperand(I))
890            return MDNode::get(Context, Ops);
891        return N;
892      }
893
894  return MDNode::get(Context, Ops);
895}
896
897MDNode *MDNode::concatenate(MDNode *A, MDNode *B) {
898  if (!A)
899    return B;
900  if (!B)
901    return A;
902
903  SmallSetVector<Metadata *, 4> MDs(A->op_begin(), A->op_end());
904  MDs.insert(B->op_begin(), B->op_end());
905
906  // FIXME: This preserves long-standing behaviour, but is it really the right
907  // behaviour?  Or was that an unintended side-effect of node uniquing?
908  return getOrSelfReference(A->getContext(), MDs.getArrayRef());
909}
910
911MDNode *MDNode::intersect(MDNode *A, MDNode *B) {
912  if (!A || !B)
913    return nullptr;
914
915  SmallSetVector<Metadata *, 4> MDs(A->op_begin(), A->op_end());
916  SmallPtrSet<Metadata *, 4> BSet(B->op_begin(), B->op_end());
917  MDs.remove_if([&](Metadata *MD) { return !BSet.count(MD); });
918
919  // FIXME: This preserves long-standing behaviour, but is it really the right
920  // behaviour?  Or was that an unintended side-effect of node uniquing?
921  return getOrSelfReference(A->getContext(), MDs.getArrayRef());
922}
923
924MDNode *MDNode::getMostGenericAliasScope(MDNode *A, MDNode *B) {
925  if (!A || !B)
926    return nullptr;
927
928  return concatenate(A, B);
929}
930
931MDNode *MDNode::getMostGenericFPMath(MDNode *A, MDNode *B) {
932  if (!A || !B)
933    return nullptr;
934
935  APFloat AVal = mdconst::extract<ConstantFP>(A->getOperand(0))->getValueAPF();
936  APFloat BVal = mdconst::extract<ConstantFP>(B->getOperand(0))->getValueAPF();
937  if (AVal < BVal)
938    return A;
939  return B;
940}
941
942static bool isContiguous(const ConstantRange &A, const ConstantRange &B) {
943  return A.getUpper() == B.getLower() || A.getLower() == B.getUpper();
944}
945
946static bool canBeMerged(const ConstantRange &A, const ConstantRange &B) {
947  return !A.intersectWith(B).isEmptySet() || isContiguous(A, B);
948}
949
950static bool tryMergeRange(SmallVectorImpl<ConstantInt *> &EndPoints,
951                          ConstantInt *Low, ConstantInt *High) {
952  ConstantRange NewRange(Low->getValue(), High->getValue());
953  unsigned Size = EndPoints.size();
954  APInt LB = EndPoints[Size - 2]->getValue();
955  APInt LE = EndPoints[Size - 1]->getValue();
956  ConstantRange LastRange(LB, LE);
957  if (canBeMerged(NewRange, LastRange)) {
958    ConstantRange Union = LastRange.unionWith(NewRange);
959    Type *Ty = High->getType();
960    EndPoints[Size - 2] =
961        cast<ConstantInt>(ConstantInt::get(Ty, Union.getLower()));
962    EndPoints[Size - 1] =
963        cast<ConstantInt>(ConstantInt::get(Ty, Union.getUpper()));
964    return true;
965  }
966  return false;
967}
968
969static void addRange(SmallVectorImpl<ConstantInt *> &EndPoints,
970                     ConstantInt *Low, ConstantInt *High) {
971  if (!EndPoints.empty())
972    if (tryMergeRange(EndPoints, Low, High))
973      return;
974
975  EndPoints.push_back(Low);
976  EndPoints.push_back(High);
977}
978
979MDNode *MDNode::getMostGenericRange(MDNode *A, MDNode *B) {
980  // Given two ranges, we want to compute the union of the ranges. This
981  // is slightly complicated by having to combine the intervals and merge
982  // the ones that overlap.
983
984  if (!A || !B)
985    return nullptr;
986
987  if (A == B)
988    return A;
989
990  // First, walk both lists in order of the lower boundary of each interval.
991  // At each step, try to merge the new interval to the last one we adedd.
992  SmallVector<ConstantInt *, 4> EndPoints;
993  int AI = 0;
994  int BI = 0;
995  int AN = A->getNumOperands() / 2;
996  int BN = B->getNumOperands() / 2;
997  while (AI < AN && BI < BN) {
998    ConstantInt *ALow = mdconst::extract<ConstantInt>(A->getOperand(2 * AI));
999    ConstantInt *BLow = mdconst::extract<ConstantInt>(B->getOperand(2 * BI));
1000
1001    if (ALow->getValue().slt(BLow->getValue())) {
1002      addRange(EndPoints, ALow,
1003               mdconst::extract<ConstantInt>(A->getOperand(2 * AI + 1)));
1004      ++AI;
1005    } else {
1006      addRange(EndPoints, BLow,
1007               mdconst::extract<ConstantInt>(B->getOperand(2 * BI + 1)));
1008      ++BI;
1009    }
1010  }
1011  while (AI < AN) {
1012    addRange(EndPoints, mdconst::extract<ConstantInt>(A->getOperand(2 * AI)),
1013             mdconst::extract<ConstantInt>(A->getOperand(2 * AI + 1)));
1014    ++AI;
1015  }
1016  while (BI < BN) {
1017    addRange(EndPoints, mdconst::extract<ConstantInt>(B->getOperand(2 * BI)),
1018             mdconst::extract<ConstantInt>(B->getOperand(2 * BI + 1)));
1019    ++BI;
1020  }
1021
1022  // If we have more than 2 ranges (4 endpoints) we have to try to merge
1023  // the last and first ones.
1024  unsigned Size = EndPoints.size();
1025  if (Size > 4) {
1026    ConstantInt *FB = EndPoints[0];
1027    ConstantInt *FE = EndPoints[1];
1028    if (tryMergeRange(EndPoints, FB, FE)) {
1029      for (unsigned i = 0; i < Size - 2; ++i) {
1030        EndPoints[i] = EndPoints[i + 2];
1031      }
1032      EndPoints.resize(Size - 2);
1033    }
1034  }
1035
1036  // If in the end we have a single range, it is possible that it is now the
1037  // full range. Just drop the metadata in that case.
1038  if (EndPoints.size() == 2) {
1039    ConstantRange Range(EndPoints[0]->getValue(), EndPoints[1]->getValue());
1040    if (Range.isFullSet())
1041      return nullptr;
1042  }
1043
1044  SmallVector<Metadata *, 4> MDs;
1045  MDs.reserve(EndPoints.size());
1046  for (auto *I : EndPoints)
1047    MDs.push_back(ConstantAsMetadata::get(I));
1048  return MDNode::get(A->getContext(), MDs);
1049}
1050
1051MDNode *MDNode::getMostGenericAlignmentOrDereferenceable(MDNode *A, MDNode *B) {
1052  if (!A || !B)
1053    return nullptr;
1054
1055  ConstantInt *AVal = mdconst::extract<ConstantInt>(A->getOperand(0));
1056  ConstantInt *BVal = mdconst::extract<ConstantInt>(B->getOperand(0));
1057  if (AVal->getZExtValue() < BVal->getZExtValue())
1058    return A;
1059  return B;
1060}
1061
1062//===----------------------------------------------------------------------===//
1063// NamedMDNode implementation.
1064//
1065
1066static SmallVector<TrackingMDRef, 4> &getNMDOps(void *Operands) {
1067  return *(SmallVector<TrackingMDRef, 4> *)Operands;
1068}
1069
1070NamedMDNode::NamedMDNode(const Twine &N)
1071    : Name(N.str()), Operands(new SmallVector<TrackingMDRef, 4>()) {}
1072
1073NamedMDNode::~NamedMDNode() {
1074  dropAllReferences();
1075  delete &getNMDOps(Operands);
1076}
1077
1078unsigned NamedMDNode::getNumOperands() const {
1079  return (unsigned)getNMDOps(Operands).size();
1080}
1081
1082MDNode *NamedMDNode::getOperand(unsigned i) const {
1083  assert(i < getNumOperands() && "Invalid Operand number!");
1084  auto *N = getNMDOps(Operands)[i].get();
1085  return cast_or_null<MDNode>(N);
1086}
1087
1088void NamedMDNode::addOperand(MDNode *M) { getNMDOps(Operands).emplace_back(M); }
1089
1090void NamedMDNode::setOperand(unsigned I, MDNode *New) {
1091  assert(I < getNumOperands() && "Invalid operand number");
1092  getNMDOps(Operands)[I].reset(New);
1093}
1094
1095void NamedMDNode::eraseFromParent() { getParent()->eraseNamedMetadata(this); }
1096
1097void NamedMDNode::clearOperands() { getNMDOps(Operands).clear(); }
1098
1099StringRef NamedMDNode::getName() const { return StringRef(Name); }
1100
1101//===----------------------------------------------------------------------===//
1102// Instruction Metadata method implementations.
1103//
1104void MDAttachmentMap::set(unsigned ID, MDNode &MD) {
1105  for (auto &I : Attachments)
1106    if (I.first == ID) {
1107      I.second.reset(&MD);
1108      return;
1109    }
1110  Attachments.emplace_back(std::piecewise_construct, std::make_tuple(ID),
1111                           std::make_tuple(&MD));
1112}
1113
1114bool MDAttachmentMap::erase(unsigned ID) {
1115  if (empty())
1116    return false;
1117
1118  // Common case is one/last value.
1119  if (Attachments.back().first == ID) {
1120    Attachments.pop_back();
1121    return true;
1122  }
1123
1124  for (auto I = Attachments.begin(), E = std::prev(Attachments.end()); I != E;
1125       ++I)
1126    if (I->first == ID) {
1127      *I = std::move(Attachments.back());
1128      Attachments.pop_back();
1129      return true;
1130    }
1131
1132  return false;
1133}
1134
1135MDNode *MDAttachmentMap::lookup(unsigned ID) const {
1136  for (const auto &I : Attachments)
1137    if (I.first == ID)
1138      return I.second;
1139  return nullptr;
1140}
1141
1142void MDAttachmentMap::getAll(
1143    SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
1144  Result.append(Attachments.begin(), Attachments.end());
1145
1146  // Sort the resulting array so it is stable.
1147  if (Result.size() > 1)
1148    array_pod_sort(Result.begin(), Result.end());
1149}
1150
1151void MDGlobalAttachmentMap::insert(unsigned ID, MDNode &MD) {
1152  Attachments.push_back({ID, TrackingMDNodeRef(&MD)});
1153}
1154
1155MDNode *MDGlobalAttachmentMap::lookup(unsigned ID) const {
1156  for (const auto &A : Attachments)
1157    if (A.MDKind == ID)
1158      return A.Node;
1159  return nullptr;
1160}
1161
1162void MDGlobalAttachmentMap::get(unsigned ID,
1163                                SmallVectorImpl<MDNode *> &Result) const {
1164  for (const auto &A : Attachments)
1165    if (A.MDKind == ID)
1166      Result.push_back(A.Node);
1167}
1168
1169bool MDGlobalAttachmentMap::erase(unsigned ID) {
1170  auto I = std::remove_if(Attachments.begin(), Attachments.end(),
1171                          [ID](const Attachment &A) { return A.MDKind == ID; });
1172  bool Changed = I != Attachments.end();
1173  Attachments.erase(I, Attachments.end());
1174  return Changed;
1175}
1176
1177void MDGlobalAttachmentMap::getAll(
1178    SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
1179  for (const auto &A : Attachments)
1180    Result.emplace_back(A.MDKind, A.Node);
1181
1182  // Sort the resulting array so it is stable with respect to metadata IDs. We
1183  // need to preserve the original insertion order though.
1184  llvm::stable_sort(Result, less_first());
1185}
1186
1187void Instruction::setMetadata(StringRef Kind, MDNode *Node) {
1188  if (!Node && !hasMetadata())
1189    return;
1190  setMetadata(getContext().getMDKindID(Kind), Node);
1191}
1192
1193MDNode *Instruction::getMetadataImpl(StringRef Kind) const {
1194  return getMetadataImpl(getContext().getMDKindID(Kind));
1195}
1196
1197void Instruction::dropUnknownNonDebugMetadata(ArrayRef<unsigned> KnownIDs) {
1198  if (!hasMetadataHashEntry())
1199    return; // Nothing to remove!
1200
1201  auto &InstructionMetadata = getContext().pImpl->InstructionMetadata;
1202
1203  SmallSet<unsigned, 4> KnownSet;
1204  KnownSet.insert(KnownIDs.begin(), KnownIDs.end());
1205  if (KnownSet.empty()) {
1206    // Just drop our entry at the store.
1207    InstructionMetadata.erase(this);
1208    setHasMetadataHashEntry(false);
1209    return;
1210  }
1211
1212  auto &Info = InstructionMetadata[this];
1213  Info.remove_if([&KnownSet](const std::pair<unsigned, TrackingMDNodeRef> &I) {
1214    return !KnownSet.count(I.first);
1215  });
1216
1217  if (Info.empty()) {
1218    // Drop our entry at the store.
1219    InstructionMetadata.erase(this);
1220    setHasMetadataHashEntry(false);
1221  }
1222}
1223
1224void Instruction::setMetadata(unsigned KindID, MDNode *Node) {
1225  if (!Node && !hasMetadata())
1226    return;
1227
1228  // Handle 'dbg' as a special case since it is not stored in the hash table.
1229  if (KindID == LLVMContext::MD_dbg) {
1230    DbgLoc = DebugLoc(Node);
1231    return;
1232  }
1233
1234  // Handle the case when we're adding/updating metadata on an instruction.
1235  if (Node) {
1236    auto &Info = getContext().pImpl->InstructionMetadata[this];
1237    assert(!Info.empty() == hasMetadataHashEntry() &&
1238           "HasMetadata bit is wonked");
1239    if (Info.empty())
1240      setHasMetadataHashEntry(true);
1241    Info.set(KindID, *Node);
1242    return;
1243  }
1244
1245  // Otherwise, we're removing metadata from an instruction.
1246  assert((hasMetadataHashEntry() ==
1247          (getContext().pImpl->InstructionMetadata.count(this) > 0)) &&
1248         "HasMetadata bit out of date!");
1249  if (!hasMetadataHashEntry())
1250    return; // Nothing to remove!
1251  auto &Info = getContext().pImpl->InstructionMetadata[this];
1252
1253  // Handle removal of an existing value.
1254  Info.erase(KindID);
1255
1256  if (!Info.empty())
1257    return;
1258
1259  getContext().pImpl->InstructionMetadata.erase(this);
1260  setHasMetadataHashEntry(false);
1261}
1262
1263void Instruction::setAAMetadata(const AAMDNodes &N) {
1264  setMetadata(LLVMContext::MD_tbaa, N.TBAA);
1265  setMetadata(LLVMContext::MD_tbaa_struct, N.TBAAStruct);
1266  setMetadata(LLVMContext::MD_alias_scope, N.Scope);
1267  setMetadata(LLVMContext::MD_noalias, N.NoAlias);
1268}
1269
1270MDNode *Instruction::getMetadataImpl(unsigned KindID) const {
1271  // Handle 'dbg' as a special case since it is not stored in the hash table.
1272  if (KindID == LLVMContext::MD_dbg)
1273    return DbgLoc.getAsMDNode();
1274
1275  if (!hasMetadataHashEntry())
1276    return nullptr;
1277  auto &Info = getContext().pImpl->InstructionMetadata[this];
1278  assert(!Info.empty() && "bit out of sync with hash table");
1279
1280  return Info.lookup(KindID);
1281}
1282
1283void Instruction::getAllMetadataImpl(
1284    SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
1285  Result.clear();
1286
1287  // Handle 'dbg' as a special case since it is not stored in the hash table.
1288  if (DbgLoc) {
1289    Result.push_back(
1290        std::make_pair((unsigned)LLVMContext::MD_dbg, DbgLoc.getAsMDNode()));
1291    if (!hasMetadataHashEntry())
1292      return;
1293  }
1294
1295  assert(hasMetadataHashEntry() &&
1296         getContext().pImpl->InstructionMetadata.count(this) &&
1297         "Shouldn't have called this");
1298  const auto &Info = getContext().pImpl->InstructionMetadata.find(this)->second;
1299  assert(!Info.empty() && "Shouldn't have called this");
1300  Info.getAll(Result);
1301}
1302
1303void Instruction::getAllMetadataOtherThanDebugLocImpl(
1304    SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
1305  Result.clear();
1306  assert(hasMetadataHashEntry() &&
1307         getContext().pImpl->InstructionMetadata.count(this) &&
1308         "Shouldn't have called this");
1309  const auto &Info = getContext().pImpl->InstructionMetadata.find(this)->second;
1310  assert(!Info.empty() && "Shouldn't have called this");
1311  Info.getAll(Result);
1312}
1313
1314bool Instruction::extractProfMetadata(uint64_t &TrueVal,
1315                                      uint64_t &FalseVal) const {
1316  assert(
1317      (getOpcode() == Instruction::Br || getOpcode() == Instruction::Select) &&
1318      "Looking for branch weights on something besides branch or select");
1319
1320  auto *ProfileData = getMetadata(LLVMContext::MD_prof);
1321  if (!ProfileData || ProfileData->getNumOperands() != 3)
1322    return false;
1323
1324  auto *ProfDataName = dyn_cast<MDString>(ProfileData->getOperand(0));
1325  if (!ProfDataName || !ProfDataName->getString().equals("branch_weights"))
1326    return false;
1327
1328  auto *CITrue = mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(1));
1329  auto *CIFalse = mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(2));
1330  if (!CITrue || !CIFalse)
1331    return false;
1332
1333  TrueVal = CITrue->getValue().getZExtValue();
1334  FalseVal = CIFalse->getValue().getZExtValue();
1335
1336  return true;
1337}
1338
1339bool Instruction::extractProfTotalWeight(uint64_t &TotalVal) const {
1340  assert((getOpcode() == Instruction::Br ||
1341          getOpcode() == Instruction::Select ||
1342          getOpcode() == Instruction::Call ||
1343          getOpcode() == Instruction::Invoke ||
1344          getOpcode() == Instruction::Switch) &&
1345         "Looking for branch weights on something besides branch");
1346
1347  TotalVal = 0;
1348  auto *ProfileData = getMetadata(LLVMContext::MD_prof);
1349  if (!ProfileData)
1350    return false;
1351
1352  auto *ProfDataName = dyn_cast<MDString>(ProfileData->getOperand(0));
1353  if (!ProfDataName)
1354    return false;
1355
1356  if (ProfDataName->getString().equals("branch_weights")) {
1357    TotalVal = 0;
1358    for (unsigned i = 1; i < ProfileData->getNumOperands(); i++) {
1359      auto *V = mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(i));
1360      if (!V)
1361        return false;
1362      TotalVal += V->getValue().getZExtValue();
1363    }
1364    return true;
1365  } else if (ProfDataName->getString().equals("VP") &&
1366             ProfileData->getNumOperands() > 3) {
1367    TotalVal = mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(2))
1368                   ->getValue()
1369                   .getZExtValue();
1370    return true;
1371  }
1372  return false;
1373}
1374
1375void Instruction::clearMetadataHashEntries() {
1376  assert(hasMetadataHashEntry() && "Caller should check");
1377  getContext().pImpl->InstructionMetadata.erase(this);
1378  setHasMetadataHashEntry(false);
1379}
1380
1381void GlobalObject::getMetadata(unsigned KindID,
1382                               SmallVectorImpl<MDNode *> &MDs) const {
1383  if (hasMetadata())
1384    getContext().pImpl->GlobalObjectMetadata[this].get(KindID, MDs);
1385}
1386
1387void GlobalObject::getMetadata(StringRef Kind,
1388                               SmallVectorImpl<MDNode *> &MDs) const {
1389  if (hasMetadata())
1390    getMetadata(getContext().getMDKindID(Kind), MDs);
1391}
1392
1393void GlobalObject::addMetadata(unsigned KindID, MDNode &MD) {
1394  if (!hasMetadata())
1395    setHasMetadataHashEntry(true);
1396
1397  getContext().pImpl->GlobalObjectMetadata[this].insert(KindID, MD);
1398}
1399
1400void GlobalObject::addMetadata(StringRef Kind, MDNode &MD) {
1401  addMetadata(getContext().getMDKindID(Kind), MD);
1402}
1403
1404bool GlobalObject::eraseMetadata(unsigned KindID) {
1405  // Nothing to unset.
1406  if (!hasMetadata())
1407    return false;
1408
1409  auto &Store = getContext().pImpl->GlobalObjectMetadata[this];
1410  bool Changed = Store.erase(KindID);
1411  if (Store.empty())
1412    clearMetadata();
1413  return Changed;
1414}
1415
1416void GlobalObject::getAllMetadata(
1417    SmallVectorImpl<std::pair<unsigned, MDNode *>> &MDs) const {
1418  MDs.clear();
1419
1420  if (!hasMetadata())
1421    return;
1422
1423  getContext().pImpl->GlobalObjectMetadata[this].getAll(MDs);
1424}
1425
1426void GlobalObject::clearMetadata() {
1427  if (!hasMetadata())
1428    return;
1429  getContext().pImpl->GlobalObjectMetadata.erase(this);
1430  setHasMetadataHashEntry(false);
1431}
1432
1433void GlobalObject::setMetadata(unsigned KindID, MDNode *N) {
1434  eraseMetadata(KindID);
1435  if (N)
1436    addMetadata(KindID, *N);
1437}
1438
1439void GlobalObject::setMetadata(StringRef Kind, MDNode *N) {
1440  setMetadata(getContext().getMDKindID(Kind), N);
1441}
1442
1443MDNode *GlobalObject::getMetadata(unsigned KindID) const {
1444  if (hasMetadata())
1445    return getContext().pImpl->GlobalObjectMetadata[this].lookup(KindID);
1446  return nullptr;
1447}
1448
1449MDNode *GlobalObject::getMetadata(StringRef Kind) const {
1450  return getMetadata(getContext().getMDKindID(Kind));
1451}
1452
1453void GlobalObject::copyMetadata(const GlobalObject *Other, unsigned Offset) {
1454  SmallVector<std::pair<unsigned, MDNode *>, 8> MDs;
1455  Other->getAllMetadata(MDs);
1456  for (auto &MD : MDs) {
1457    // We need to adjust the type metadata offset.
1458    if (Offset != 0 && MD.first == LLVMContext::MD_type) {
1459      auto *OffsetConst = cast<ConstantInt>(
1460          cast<ConstantAsMetadata>(MD.second->getOperand(0))->getValue());
1461      Metadata *TypeId = MD.second->getOperand(1);
1462      auto *NewOffsetMD = ConstantAsMetadata::get(ConstantInt::get(
1463          OffsetConst->getType(), OffsetConst->getValue() + Offset));
1464      addMetadata(LLVMContext::MD_type,
1465                  *MDNode::get(getContext(), {NewOffsetMD, TypeId}));
1466      continue;
1467    }
1468    // If an offset adjustment was specified we need to modify the DIExpression
1469    // to prepend the adjustment:
1470    // !DIExpression(DW_OP_plus, Offset, [original expr])
1471    auto *Attachment = MD.second;
1472    if (Offset != 0 && MD.first == LLVMContext::MD_dbg) {
1473      DIGlobalVariable *GV = dyn_cast<DIGlobalVariable>(Attachment);
1474      DIExpression *E = nullptr;
1475      if (!GV) {
1476        auto *GVE = cast<DIGlobalVariableExpression>(Attachment);
1477        GV = GVE->getVariable();
1478        E = GVE->getExpression();
1479      }
1480      ArrayRef<uint64_t> OrigElements;
1481      if (E)
1482        OrigElements = E->getElements();
1483      std::vector<uint64_t> Elements(OrigElements.size() + 2);
1484      Elements[0] = dwarf::DW_OP_plus_uconst;
1485      Elements[1] = Offset;
1486      llvm::copy(OrigElements, Elements.begin() + 2);
1487      E = DIExpression::get(getContext(), Elements);
1488      Attachment = DIGlobalVariableExpression::get(getContext(), GV, E);
1489    }
1490    addMetadata(MD.first, *Attachment);
1491  }
1492}
1493
1494void GlobalObject::addTypeMetadata(unsigned Offset, Metadata *TypeID) {
1495  addMetadata(
1496      LLVMContext::MD_type,
1497      *MDTuple::get(getContext(),
1498                    {ConstantAsMetadata::get(ConstantInt::get(
1499                         Type::getInt64Ty(getContext()), Offset)),
1500                     TypeID}));
1501}
1502
1503void GlobalObject::setVCallVisibilityMetadata(VCallVisibility Visibility) {
1504  // Remove any existing vcall visibility metadata first in case we are
1505  // updating.
1506  eraseMetadata(LLVMContext::MD_vcall_visibility);
1507  addMetadata(LLVMContext::MD_vcall_visibility,
1508              *MDNode::get(getContext(),
1509                           {ConstantAsMetadata::get(ConstantInt::get(
1510                               Type::getInt64Ty(getContext()), Visibility))}));
1511}
1512
1513GlobalObject::VCallVisibility GlobalObject::getVCallVisibility() const {
1514  if (MDNode *MD = getMetadata(LLVMContext::MD_vcall_visibility)) {
1515    uint64_t Val = cast<ConstantInt>(
1516                       cast<ConstantAsMetadata>(MD->getOperand(0))->getValue())
1517                       ->getZExtValue();
1518    assert(Val <= 2 && "unknown vcall visibility!");
1519    return (VCallVisibility)Val;
1520  }
1521  return VCallVisibility::VCallVisibilityPublic;
1522}
1523
1524void Function::setSubprogram(DISubprogram *SP) {
1525  setMetadata(LLVMContext::MD_dbg, SP);
1526}
1527
1528DISubprogram *Function::getSubprogram() const {
1529  return cast_or_null<DISubprogram>(getMetadata(LLVMContext::MD_dbg));
1530}
1531
1532bool Function::isDebugInfoForProfiling() const {
1533  if (DISubprogram *SP = getSubprogram()) {
1534    if (DICompileUnit *CU = SP->getUnit()) {
1535      return CU->getDebugInfoForProfiling();
1536    }
1537  }
1538  return false;
1539}
1540
1541void GlobalVariable::addDebugInfo(DIGlobalVariableExpression *GV) {
1542  addMetadata(LLVMContext::MD_dbg, *GV);
1543}
1544
1545void GlobalVariable::getDebugInfo(
1546    SmallVectorImpl<DIGlobalVariableExpression *> &GVs) const {
1547  SmallVector<MDNode *, 1> MDs;
1548  getMetadata(LLVMContext::MD_dbg, MDs);
1549  for (MDNode *MD : MDs)
1550    GVs.push_back(cast<DIGlobalVariableExpression>(MD));
1551}
1552