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