Bug Summary

File:include/llvm/IR/Metadata.h
Warning:line 824, column 3
Potential leak of memory pointed to by 'ReplaceableUses._M_t._M_head_impl'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name Metadata.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-9/lib/clang/9.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/lib/IR -I /build/llvm-toolchain-snapshot-9~svn362543/lib/IR -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/include -I /build/llvm-toolchain-snapshot-9~svn362543/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/9.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-9/lib/clang/9.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/lib/IR -fdebug-prefix-map=/build/llvm-toolchain-snapshot-9~svn362543=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2019-06-05-060531-1271-1 -x c++ /build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp -faddrsig

/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp

→
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")((Ref && "Expected live reference") ? static_cast<
void> (0) : __assert_fail ("Ref && \"Expected live reference\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 154, __PRETTY_FUNCTION__));
1
Assuming 'Ref' is non-null
→
2
←
'?' condition is true
→
155 assert((Owner || *static_cast<Metadata **>(Ref) == &MD) &&(((Owner || *static_cast<Metadata **>(Ref) == &MD) &&
"Reference without owner must be direct") ? static_cast<void
> (0) : __assert_fail ("(Owner || *static_cast<Metadata **>(Ref) == &MD) && \"Reference without owner must be direct\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 156, __PRETTY_FUNCTION__))
3
←
'?' condition is true
→
156 "Reference without owner must be direct")(((Owner || *static_cast<Metadata **>(Ref) == &MD) &&
"Reference without owner must be direct") ? static_cast<void
> (0) : __assert_fail ("(Owner || *static_cast<Metadata **>(Ref) == &MD) && \"Reference without owner must be direct\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 156, __PRETTY_FUNCTION__));
157 if (auto *R = ReplaceableMetadataImpl::getOrCreate(MD)) {
4
←
Calling 'ReplaceableMetadataImpl::getOrCreate'
→
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")((!PH->Use && "Placeholders can only be used once"
) ? static_cast<void> (0) : __assert_fail ("!PH->Use && \"Placeholders can only be used once\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 162, __PRETTY_FUNCTION__));
163 assert(!Owner && "Unexpected callback to owner")((!Owner && "Unexpected callback to owner") ? static_cast
<void> (0) : __assert_fail ("!Owner && \"Unexpected callback to owner\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 163, __PRETTY_FUNCTION__));
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")((Ref && "Expected live reference") ? static_cast<
void> (0) : __assert_fail ("Ref && \"Expected live reference\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 171, __PRETTY_FUNCTION__));
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")((Ref && "Expected live reference") ? static_cast<
void> (0) : __assert_fail ("Ref && \"Expected live reference\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 179, __PRETTY_FUNCTION__));
180 assert(New && "Expected live reference")((New && "Expected live reference") ? static_cast<
void> (0) : __assert_fail ("New && \"Expected live reference\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 180, __PRETTY_FUNCTION__));
181 assert(Ref != New && "Expected change")((Ref != New && "Expected change") ? static_cast<void
> (0) : __assert_fail ("Ref != New && \"Expected change\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 181, __PRETTY_FUNCTION__));
182 if (auto *R = ReplaceableMetadataImpl::getIfExists(MD)) {
183 R->moveRef(Ref, New, MD);
184 return true;
185 }
186 assert(!isa<DistinctMDOperandPlaceholder>(MD) &&((!isa<DistinctMDOperandPlaceholder>(MD) && "Unexpected move of an MDOperand"
) ? static_cast<void> (0) : __assert_fail ("!isa<DistinctMDOperandPlaceholder>(MD) && \"Unexpected move of an MDOperand\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 187, __PRETTY_FUNCTION__))
187 "Unexpected move of an MDOperand")((!isa<DistinctMDOperandPlaceholder>(MD) && "Unexpected move of an MDOperand"
) ? static_cast<void> (0) : __assert_fail ("!isa<DistinctMDOperandPlaceholder>(MD) && \"Unexpected move of an MDOperand\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 187, __PRETTY_FUNCTION__));
188 assert(!isReplaceable(MD) &&((!isReplaceable(MD) && "Expected un-replaceable metadata, since we didn't move a reference"
) ? static_cast<void> (0) : __assert_fail ("!isReplaceable(MD) && \"Expected un-replaceable metadata, since we didn't move a reference\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 189, __PRETTY_FUNCTION__))
189 "Expected un-replaceable metadata, since we didn't move a reference")((!isReplaceable(MD) && "Expected un-replaceable metadata, since we didn't move a reference"
) ? static_cast<void> (0) : __assert_fail ("!isReplaceable(MD) && \"Expected un-replaceable metadata, since we didn't move a reference\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 189, __PRETTY_FUNCTION__));
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")((WasInserted && "Expected to add a reference") ? static_cast
<void> (0) : __assert_fail ("WasInserted && \"Expected to add a reference\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 202, __PRETTY_FUNCTION__));
203
204 ++NextIndex;
205 assert(NextIndex != 0 && "Unexpected overflow")((NextIndex != 0 && "Unexpected overflow") ? static_cast
<void> (0) : __assert_fail ("NextIndex != 0 && \"Unexpected overflow\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 205, __PRETTY_FUNCTION__));
206}
207
208void ReplaceableMetadataImpl::dropRef(void *Ref) {
209 bool WasErased = UseMap.erase(Ref);
210 (void)WasErased;
211 assert(WasErased && "Expected to drop a reference")((WasErased && "Expected to drop a reference") ? static_cast
<void> (0) : __assert_fail ("WasErased && \"Expected to drop a reference\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 211, __PRETTY_FUNCTION__));
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")((I != UseMap.end() && "Expected to move a reference"
) ? static_cast<void> (0) : __assert_fail ("I != UseMap.end() && \"Expected to move a reference\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 217, __PRETTY_FUNCTION__));
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")((WasInserted && "Expected to add a reference") ? static_cast
<void> (0) : __assert_fail ("WasInserted && \"Expected to add a reference\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 222, __PRETTY_FUNCTION__));
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) &&(((OwnerAndIndex.first || *static_cast<Metadata **>(Ref
) == &MD) && "Reference without owner must be direct"
) ? static_cast<void> (0) : __assert_fail ("(OwnerAndIndex.first || *static_cast<Metadata **>(Ref) == &MD) && \"Reference without owner must be direct\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 227, __PRETTY_FUNCTION__))
227 "Reference without owner must be direct")(((OwnerAndIndex.first || *static_cast<Metadata **>(Ref
) == &MD) && "Reference without owner must be direct"
) ? static_cast<void> (0) : __assert_fail ("(OwnerAndIndex.first || *static_cast<Metadata **>(Ref) == &MD) && \"Reference without owner must be direct\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 227, __PRETTY_FUNCTION__));
228 assert((OwnerAndIndex.first || *static_cast<Metadata **>(New) == &MD) &&(((OwnerAndIndex.first || *static_cast<Metadata **>(New
) == &MD) && "Reference without owner must be direct"
) ? static_cast<void> (0) : __assert_fail ("(OwnerAndIndex.first || *static_cast<Metadata **>(New) == &MD) && \"Reference without owner must be direct\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 229, __PRETTY_FUNCTION__))
229 "Reference without owner must be direct")(((OwnerAndIndex.first || *static_cast<Metadata **>(New
) == &MD) && "Reference without owner must be direct"
) ? static_cast<void> (0) : __assert_fail ("(OwnerAndIndex.first || *static_cast<Metadata **>(New) == &MD) && \"Reference without owner must be direct\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 229, __PRETTY_FUNCTION__));
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")::llvm::llvm_unreachable_internal("Invalid metadata subclass"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 274);
275 }
276 }
277 assert(UseMap.empty() && "Expected all uses to be replaced")((UseMap.empty() && "Expected all uses to be replaced"
) ? static_cast<void> (0) : __assert_fail ("UseMap.empty() && \"Expected all uses to be replaced\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 277, __PRETTY_FUNCTION__));
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))
5
←
Taking true branch
→
315 return N->isResolved() ? nullptr : N->Context.getOrCreateReplaceableUses();
6
←
'?' condition is false
→
7
←
Calling 'ContextAndReplaceableUses::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")((V && "Expected value") ? static_cast<void> (0
) : __assert_fail ("V && \"Expected value\"", "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 332, __PRETTY_FUNCTION__));
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")((V && "Unexpected null Value") ? static_cast<void
> (0) : __assert_fail ("V && \"Unexpected null Value\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 349, __PRETTY_FUNCTION__));
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)) &&(((isa<Constant>(V) || isa<Argument>(V) || isa<
Instruction>(V)) && "Expected constant or function-local value"
) ? static_cast<void> (0) : __assert_fail ("(isa<Constant>(V) || isa<Argument>(V) || isa<Instruction>(V)) && \"Expected constant or function-local value\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 355, __PRETTY_FUNCTION__))
355 "Expected constant or function-local value")(((isa<Constant>(V) || isa<Argument>(V) || isa<
Instruction>(V)) && "Expected constant or function-local value"
) ? static_cast<void> (0) : __assert_fail ("(isa<Constant>(V) || isa<Argument>(V) || isa<Instruction>(V)) && \"Expected constant or function-local value\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 355, __PRETTY_FUNCTION__));
356 assert(!V->IsUsedByMD && "Expected this to be the only metadata use")((!V->IsUsedByMD && "Expected this to be the only metadata use"
) ? static_cast<void> (0) : __assert_fail ("!V->IsUsedByMD && \"Expected this to be the only metadata use\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 356, __PRETTY_FUNCTION__));
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")((V && "Unexpected null Value") ? static_cast<void
> (0) : __assert_fail ("V && \"Unexpected null Value\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 368, __PRETTY_FUNCTION__));
369 return V->getContext().pImpl->ValuesAsMetadata.lookup(V);
370}
371
372void ValueAsMetadata::handleDeletion(Value *V) {
373 assert(V && "Expected valid value")((V && "Expected valid value") ? static_cast<void>
(0) : __assert_fail ("V && \"Expected valid value\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 373, __PRETTY_FUNCTION__));
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")((MD && "Expected valid metadata") ? static_cast<void
> (0) : __assert_fail ("MD && \"Expected valid metadata\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 382, __PRETTY_FUNCTION__));
383 assert(MD->getValue() == V && "Expected valid mapping")((MD->getValue() == V && "Expected valid mapping")
? static_cast<void> (0) : __assert_fail ("MD->getValue() == V && \"Expected valid mapping\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 383, __PRETTY_FUNCTION__));
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")((From && "Expected valid value") ? static_cast<void
> (0) : __assert_fail ("From && \"Expected valid value\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 392, __PRETTY_FUNCTION__));
393 assert(To && "Expected valid value")((To && "Expected valid value") ? static_cast<void
> (0) : __assert_fail ("To && \"Expected valid value\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 393, __PRETTY_FUNCTION__));
394 assert(From != To && "Expected changed value")((From != To && "Expected changed value") ? static_cast
<void> (0) : __assert_fail ("From != To && \"Expected changed value\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 394, __PRETTY_FUNCTION__));
395 assert(From->getType() == To->getType() && "Unexpected type change")((From->getType() == To->getType() && "Unexpected type change"
) ? static_cast<void> (0) : __assert_fail ("From->getType() == To->getType() && \"Unexpected type change\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 395, __PRETTY_FUNCTION__));
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")((!From->IsUsedByMD && "Expected From not to be used by metadata"
) ? static_cast<void> (0) : __assert_fail ("!From->IsUsedByMD && \"Expected From not to be used by metadata\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 401, __PRETTY_FUNCTION__));
402 return;
403 }
404
405 // Remove old entry from the map.
406 assert(From->IsUsedByMD && "Expected From to be used by metadata")((From->IsUsedByMD && "Expected From to be used by metadata"
) ? static_cast<void> (0) : __assert_fail ("From->IsUsedByMD && \"Expected From to be used by metadata\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 406, __PRETTY_FUNCTION__));
407 From->IsUsedByMD = false;
408 ValueAsMetadata *MD = I->second;
409 assert(MD && "Expected valid metadata")((MD && "Expected valid metadata") ? static_cast<void
> (0) : __assert_fail ("MD && \"Expected valid metadata\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 409, __PRETTY_FUNCTION__));
410 assert(MD->getValue() == From && "Expected valid mapping")((MD->getValue() == From && "Expected valid mapping"
) ? static_cast<void> (0) : __assert_fail ("MD->getValue() == From && \"Expected valid mapping\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 410, __PRETTY_FUNCTION__));
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")((!To->IsUsedByMD && "Expected this to be the only metadata use"
) ? static_cast<void> (0) : __assert_fail ("!To->IsUsedByMD && \"Expected this to be the only metadata use\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 443, __PRETTY_FUNCTION__));
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")((Entry && "Expected to find string map entry") ? static_cast
<void> (0) : __assert_fail ("Entry && \"Expected to find string map entry\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 464, __PRETTY_FUNCTION__));
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
492void MDNode::operator delete(void *Mem) {
493 MDNode *N = static_cast<MDNode *>(Mem);
494 size_t OpSize = N->NumOperands * sizeof(MDOperand);
495 OpSize = alignTo(OpSize, alignof(uint64_t));
496
497 MDOperand *O = static_cast<MDOperand *>(Mem);
498 for (MDOperand *E = O - N->NumOperands; O != E; --O)
499 (O - 1)->~MDOperand();
500 ::operator delete(reinterpret_cast<char *>(Mem) - OpSize);
501}
502
503MDNode::MDNode(LLVMContext &Context, unsigned ID, StorageType Storage,
504 ArrayRef<Metadata *> Ops1, ArrayRef<Metadata *> Ops2)
505 : Metadata(ID, Storage), NumOperands(Ops1.size() + Ops2.size()),
506 NumUnresolved(0), Context(Context) {
507 unsigned Op = 0;
508 for (Metadata *MD : Ops1)
509 setOperand(Op++, MD);
510 for (Metadata *MD : Ops2)
511 setOperand(Op++, MD);
512
513 if (!isUniqued())
514 return;
515
516 // Count the unresolved operands. If there are any, RAUW support will be
517 // added lazily on first reference.
518 countUnresolvedOperands();
519}
520
521TempMDNode MDNode::clone() const {
522 switch (getMetadataID()) {
523 default:
524 llvm_unreachable("Invalid MDNode subclass")::llvm::llvm_unreachable_internal("Invalid MDNode subclass", "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 524);
525#define HANDLE_MDNODE_LEAF(CLASS) \
526 case CLASS##Kind: \
527 return cast<CLASS>(this)->cloneImpl();
528#include "llvm/IR/Metadata.def"
529 }
530}
531
532static bool isOperandUnresolved(Metadata *Op) {
533 if (auto *N = dyn_cast_or_null<MDNode>(Op))
534 return !N->isResolved();
535 return false;
536}
537
538void MDNode::countUnresolvedOperands() {
539 assert(NumUnresolved == 0 && "Expected unresolved ops to be uncounted")((NumUnresolved == 0 && "Expected unresolved ops to be uncounted"
) ? static_cast<void> (0) : __assert_fail ("NumUnresolved == 0 && \"Expected unresolved ops to be uncounted\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 539, __PRETTY_FUNCTION__));
540 assert(isUniqued() && "Expected this to be uniqued")((isUniqued() && "Expected this to be uniqued") ? static_cast
<void> (0) : __assert_fail ("isUniqued() && \"Expected this to be uniqued\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 540, __PRETTY_FUNCTION__));
541 NumUnresolved = count_if(operands(), isOperandUnresolved);
542}
543
544void MDNode::makeUniqued() {
545 assert(isTemporary() && "Expected this to be temporary")((isTemporary() && "Expected this to be temporary") ?
static_cast<void> (0) : __assert_fail ("isTemporary() && \"Expected this to be temporary\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 545, __PRETTY_FUNCTION__));
546 assert(!isResolved() && "Expected this to be unresolved")((!isResolved() && "Expected this to be unresolved") ?
static_cast<void> (0) : __assert_fail ("!isResolved() && \"Expected this to be unresolved\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 546, __PRETTY_FUNCTION__));
547
548 // Enable uniquing callbacks.
549 for (auto &Op : mutable_operands())
550 Op.reset(Op.get(), this);
551
552 // Make this 'uniqued'.
553 Storage = Uniqued;
554 countUnresolvedOperands();
555 if (!NumUnresolved) {
556 dropReplaceableUses();
557 assert(isResolved() && "Expected this to be resolved")((isResolved() && "Expected this to be resolved") ? static_cast
<void> (0) : __assert_fail ("isResolved() && \"Expected this to be resolved\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 557, __PRETTY_FUNCTION__));
558 }
559
560 assert(isUniqued() && "Expected this to be uniqued")((isUniqued() && "Expected this to be uniqued") ? static_cast
<void> (0) : __assert_fail ("isUniqued() && \"Expected this to be uniqued\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 560, __PRETTY_FUNCTION__));
561}
562
563void MDNode::makeDistinct() {
564 assert(isTemporary() && "Expected this to be temporary")((isTemporary() && "Expected this to be temporary") ?
static_cast<void> (0) : __assert_fail ("isTemporary() && \"Expected this to be temporary\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 564, __PRETTY_FUNCTION__));
565 assert(!isResolved() && "Expected this to be unresolved")((!isResolved() && "Expected this to be unresolved") ?
static_cast<void> (0) : __assert_fail ("!isResolved() && \"Expected this to be unresolved\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 565, __PRETTY_FUNCTION__));
566
567 // Drop RAUW support and store as a distinct node.
568 dropReplaceableUses();
569 storeDistinctInContext();
570
571 assert(isDistinct() && "Expected this to be distinct")((isDistinct() && "Expected this to be distinct") ? static_cast
<void> (0) : __assert_fail ("isDistinct() && \"Expected this to be distinct\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 571, __PRETTY_FUNCTION__));
572 assert(isResolved() && "Expected this to be resolved")((isResolved() && "Expected this to be resolved") ? static_cast
<void> (0) : __assert_fail ("isResolved() && \"Expected this to be resolved\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 572, __PRETTY_FUNCTION__));
573}
574
575void MDNode::resolve() {
576 assert(isUniqued() && "Expected this to be uniqued")((isUniqued() && "Expected this to be uniqued") ? static_cast
<void> (0) : __assert_fail ("isUniqued() && \"Expected this to be uniqued\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 576, __PRETTY_FUNCTION__));
577 assert(!isResolved() && "Expected this to be unresolved")((!isResolved() && "Expected this to be unresolved") ?
static_cast<void> (0) : __assert_fail ("!isResolved() && \"Expected this to be unresolved\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 577, __PRETTY_FUNCTION__));
578
579 NumUnresolved = 0;
580 dropReplaceableUses();
581
582 assert(isResolved() && "Expected this to be resolved")((isResolved() && "Expected this to be resolved") ? static_cast
<void> (0) : __assert_fail ("isResolved() && \"Expected this to be resolved\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 582, __PRETTY_FUNCTION__));
583}
584
585void MDNode::dropReplaceableUses() {
586 assert(!NumUnresolved && "Unexpected unresolved operand")((!NumUnresolved && "Unexpected unresolved operand") ?
static_cast<void> (0) : __assert_fail ("!NumUnresolved && \"Unexpected unresolved operand\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 586, __PRETTY_FUNCTION__));
587
588 // Drop any RAUW support.
589 if (Context.hasReplaceableUses())
590 Context.takeReplaceableUses()->resolveAllUses();
591}
592
593void MDNode::resolveAfterOperandChange(Metadata *Old, Metadata *New) {
594 assert(isUniqued() && "Expected this to be uniqued")((isUniqued() && "Expected this to be uniqued") ? static_cast
<void> (0) : __assert_fail ("isUniqued() && \"Expected this to be uniqued\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 594, __PRETTY_FUNCTION__));
595 assert(NumUnresolved != 0 && "Expected unresolved operands")((NumUnresolved != 0 && "Expected unresolved operands"
) ? static_cast<void> (0) : __assert_fail ("NumUnresolved != 0 && \"Expected unresolved operands\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 595, __PRETTY_FUNCTION__));
596
597 // Check if an operand was resolved.
598 if (!isOperandUnresolved(Old)) {
599 if (isOperandUnresolved(New))
600 // An operand was un-resolved!
601 ++NumUnresolved;
602 } else if (!isOperandUnresolved(New))
603 decrementUnresolvedOperandCount();
604}
605
606void MDNode::decrementUnresolvedOperandCount() {
607 assert(!isResolved() && "Expected this to be unresolved")((!isResolved() && "Expected this to be unresolved") ?
static_cast<void> (0) : __assert_fail ("!isResolved() && \"Expected this to be unresolved\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 607, __PRETTY_FUNCTION__));
608 if (isTemporary())
609 return;
610
611 assert(isUniqued() && "Expected this to be uniqued")((isUniqued() && "Expected this to be uniqued") ? static_cast
<void> (0) : __assert_fail ("isUniqued() && \"Expected this to be uniqued\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 611, __PRETTY_FUNCTION__));
612 if (--NumUnresolved)
613 return;
614
615 // Last unresolved operand has just been resolved.
616 dropReplaceableUses();
617 assert(isResolved() && "Expected this to become resolved")((isResolved() && "Expected this to become resolved")
? static_cast<void> (0) : __assert_fail ("isResolved() && \"Expected this to become resolved\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 617, __PRETTY_FUNCTION__));
618}
619
620void MDNode::resolveCycles() {
621 if (isResolved())
622 return;
623
624 // Resolve this node immediately.
625 resolve();
626
627 // Resolve all operands.
628 for (const auto &Op : operands()) {
629 auto *N = dyn_cast_or_null<MDNode>(Op);
630 if (!N)
631 continue;
632
633 assert(!N->isTemporary() &&((!N->isTemporary() && "Expected all forward declarations to be resolved"
) ? static_cast<void> (0) : __assert_fail ("!N->isTemporary() && \"Expected all forward declarations to be resolved\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 634, __PRETTY_FUNCTION__))
634 "Expected all forward declarations to be resolved")((!N->isTemporary() && "Expected all forward declarations to be resolved"
) ? static_cast<void> (0) : __assert_fail ("!N->isTemporary() && \"Expected all forward declarations to be resolved\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 634, __PRETTY_FUNCTION__));
635 if (!N->isResolved())
636 N->resolveCycles();
637 }
638}
639
640static bool hasSelfReference(MDNode *N) {
641 for (Metadata *MD : N->operands())
642 if (MD == N)
643 return true;
644 return false;
645}
646
647MDNode *MDNode::replaceWithPermanentImpl() {
648 switch (getMetadataID()) {
649 default:
650 // If this type isn't uniquable, replace with a distinct node.
651 return replaceWithDistinctImpl();
652
653#define HANDLE_MDNODE_LEAF_UNIQUABLE(CLASS) \
654 case CLASS##Kind: \
655 break;
656#include "llvm/IR/Metadata.def"
657 }
658
659 // Even if this type is uniquable, self-references have to be distinct.
660 if (hasSelfReference(this))
661 return replaceWithDistinctImpl();
662 return replaceWithUniquedImpl();
663}
664
665MDNode *MDNode::replaceWithUniquedImpl() {
666 // Try to uniquify in place.
667 MDNode *UniquedNode = uniquify();
668
669 if (UniquedNode == this) {
670 makeUniqued();
671 return this;
672 }
673
674 // Collision, so RAUW instead.
675 replaceAllUsesWith(UniquedNode);
676 deleteAsSubclass();
677 return UniquedNode;
678}
679
680MDNode *MDNode::replaceWithDistinctImpl() {
681 makeDistinct();
682 return this;
683}
684
685void MDTuple::recalculateHash() {
686 setHash(MDTupleInfo::KeyTy::calculateHash(this));
687}
688
689void MDNode::dropAllReferences() {
690 for (unsigned I = 0, E = NumOperands; I != E; ++I)
691 setOperand(I, nullptr);
692 if (Context.hasReplaceableUses()) {
693 Context.getReplaceableUses()->resolveAllUses(/* ResolveUsers */ false);
694 (void)Context.takeReplaceableUses();
695 }
696}
697
698void MDNode::handleChangedOperand(void *Ref, Metadata *New) {
699 unsigned Op = static_cast<MDOperand *>(Ref) - op_begin();
700 assert(Op < getNumOperands() && "Expected valid operand")((Op < getNumOperands() && "Expected valid operand"
) ? static_cast<void> (0) : __assert_fail ("Op < getNumOperands() && \"Expected valid operand\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 700, __PRETTY_FUNCTION__));
701
702 if (!isUniqued()) {
703 // This node is not uniqued. Just set the operand and be done with it.
704 setOperand(Op, New);
705 return;
706 }
707
708 // This node is uniqued.
709 eraseFromStore();
710
711 Metadata *Old = getOperand(Op);
712 setOperand(Op, New);
713
714 // Drop uniquing for self-reference cycles and deleted constants.
715 if (New == this || (!New && Old && isa<ConstantAsMetadata>(Old))) {
716 if (!isResolved())
717 resolve();
718 storeDistinctInContext();
719 return;
720 }
721
722 // Re-unique the node.
723 auto *Uniqued = uniquify();
724 if (Uniqued == this) {
725 if (!isResolved())
726 resolveAfterOperandChange(Old, New);
727 return;
728 }
729
730 // Collision.
731 if (!isResolved()) {
732 // Still unresolved, so RAUW.
733 //
734 // First, clear out all operands to prevent any recursion (similar to
735 // dropAllReferences(), but we still need the use-list).
736 for (unsigned O = 0, E = getNumOperands(); O != E; ++O)
737 setOperand(O, nullptr);
738 if (Context.hasReplaceableUses())
739 Context.getReplaceableUses()->replaceAllUsesWith(Uniqued);
740 deleteAsSubclass();
741 return;
742 }
743
744 // Store in non-uniqued form if RAUW isn't possible.
745 storeDistinctInContext();
746}
747
748void MDNode::deleteAsSubclass() {
749 switch (getMetadataID()) {
750 default:
751 llvm_unreachable("Invalid subclass of MDNode")::llvm::llvm_unreachable_internal("Invalid subclass of MDNode"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 751);
752#define HANDLE_MDNODE_LEAF(CLASS) \
753 case CLASS##Kind: \
754 delete cast<CLASS>(this); \
755 break;
756#include "llvm/IR/Metadata.def"
757 }
758}
759
760template <class T, class InfoT>
761static T *uniquifyImpl(T *N, DenseSet<T *, InfoT> &Store) {
762 if (T *U = getUniqued(Store, N))
763 return U;
764
765 Store.insert(N);
766 return N;
767}
768
769template <class NodeTy> struct MDNode::HasCachedHash {
770 using Yes = char[1];
771 using No = char[2];
772 template <class U, U Val> struct SFINAE {};
773
774 template <class U>
775 static Yes &check(SFINAE<void (U::*)(unsigned), &U::setHash> *);
776 template <class U> static No &check(...);
777
778 static const bool value = sizeof(check<NodeTy>(nullptr)) == sizeof(Yes);
779};
780
781MDNode *MDNode::uniquify() {
782 assert(!hasSelfReference(this) && "Cannot uniquify a self-referencing node")((!hasSelfReference(this) && "Cannot uniquify a self-referencing node"
) ? static_cast<void> (0) : __assert_fail ("!hasSelfReference(this) && \"Cannot uniquify a self-referencing node\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 782, __PRETTY_FUNCTION__));
783
784 // Try to insert into uniquing store.
785 switch (getMetadataID()) {
786 default:
787 llvm_unreachable("Invalid or non-uniquable subclass of MDNode")::llvm::llvm_unreachable_internal("Invalid or non-uniquable subclass of MDNode"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 787);
788#define HANDLE_MDNODE_LEAF_UNIQUABLE(CLASS) \
789 case CLASS##Kind: { \
790 CLASS *SubclassThis = cast<CLASS>(this); \
791 std::integral_constant<bool, HasCachedHash<CLASS>::value> \
792 ShouldRecalculateHash; \
793 dispatchRecalculateHash(SubclassThis, ShouldRecalculateHash); \
794 return uniquifyImpl(SubclassThis, getContext().pImpl->CLASS##s); \
795 }
796#include "llvm/IR/Metadata.def"
797 }
798}
799
800void MDNode::eraseFromStore() {
801 switch (getMetadataID()) {
802 default:
803 llvm_unreachable("Invalid or non-uniquable subclass of MDNode")::llvm::llvm_unreachable_internal("Invalid or non-uniquable subclass of MDNode"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 803);
804#define HANDLE_MDNODE_LEAF_UNIQUABLE(CLASS) \
805 case CLASS##Kind: \
806 getContext().pImpl->CLASS##s.erase(cast<CLASS>(this)); \
807 break;
808#include "llvm/IR/Metadata.def"
809 }
810}
811
812MDTuple *MDTuple::getImpl(LLVMContext &Context, ArrayRef<Metadata *> MDs,
813 StorageType Storage, bool ShouldCreate) {
814 unsigned Hash = 0;
815 if (Storage == Uniqued) {
816 MDTupleInfo::KeyTy Key(MDs);
817 if (auto *N = getUniqued(Context.pImpl->MDTuples, Key))
818 return N;
819 if (!ShouldCreate)
820 return nullptr;
821 Hash = Key.getHash();
822 } else {
823 assert(ShouldCreate && "Expected non-uniqued nodes to always be created")((ShouldCreate && "Expected non-uniqued nodes to always be created"
) ? static_cast<void> (0) : __assert_fail ("ShouldCreate && \"Expected non-uniqued nodes to always be created\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 823, __PRETTY_FUNCTION__));
824 }
825
826 return storeImpl(new (MDs.size()) MDTuple(Context, Storage, Hash, MDs),
827 Storage, Context.pImpl->MDTuples);
828}
829
830void MDNode::deleteTemporary(MDNode *N) {
831 assert(N->isTemporary() && "Expected temporary node")((N->isTemporary() && "Expected temporary node") ?
static_cast<void> (0) : __assert_fail ("N->isTemporary() && \"Expected temporary node\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 831, __PRETTY_FUNCTION__));
832 N->replaceAllUsesWith(nullptr);
833 N->deleteAsSubclass();
834}
835
836void MDNode::storeDistinctInContext() {
837 assert(!Context.hasReplaceableUses() && "Unexpected replaceable uses")((!Context.hasReplaceableUses() && "Unexpected replaceable uses"
) ? static_cast<void> (0) : __assert_fail ("!Context.hasReplaceableUses() && \"Unexpected replaceable uses\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 837, __PRETTY_FUNCTION__));
838 assert(!NumUnresolved && "Unexpected unresolved nodes")((!NumUnresolved && "Unexpected unresolved nodes") ? static_cast
<void> (0) : __assert_fail ("!NumUnresolved && \"Unexpected unresolved nodes\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 838, __PRETTY_FUNCTION__));
839 Storage = Distinct;
840 assert(isResolved() && "Expected this to be resolved")((isResolved() && "Expected this to be resolved") ? static_cast
<void> (0) : __assert_fail ("isResolved() && \"Expected this to be resolved\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 840, __PRETTY_FUNCTION__));
841
842 // Reset the hash.
843 switch (getMetadataID()) {
844 default:
845 llvm_unreachable("Invalid subclass of MDNode")::llvm::llvm_unreachable_internal("Invalid subclass of MDNode"
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 845);
846#define HANDLE_MDNODE_LEAF(CLASS) \
847 case CLASS##Kind: { \
848 std::integral_constant<bool, HasCachedHash<CLASS>::value> ShouldResetHash; \
849 dispatchResetHash(cast<CLASS>(this), ShouldResetHash); \
850 break; \
851 }
852#include "llvm/IR/Metadata.def"
853 }
854
855 getContext().pImpl->DistinctMDNodes.push_back(this);
856}
857
858void MDNode::replaceOperandWith(unsigned I, Metadata *New) {
859 if (getOperand(I) == New)
860 return;
861
862 if (!isUniqued()) {
863 setOperand(I, New);
864 return;
865 }
866
867 handleChangedOperand(mutable_begin() + I, New);
868}
869
870void MDNode::setOperand(unsigned I, Metadata *New) {
871 assert(I < NumOperands)((I < NumOperands) ? static_cast<void> (0) : __assert_fail
("I < NumOperands", "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 871, __PRETTY_FUNCTION__));
872 mutable_begin()[I].reset(New, isUniqued() ? this : nullptr);
873}
874
875/// Get a node or a self-reference that looks like it.
876///
877/// Special handling for finding self-references, for use by \a
878/// MDNode::concatenate() and \a MDNode::intersect() to maintain behaviour from
879/// when self-referencing nodes were still uniqued. If the first operand has
880/// the same operands as \c Ops, return the first operand instead.
881static MDNode *getOrSelfReference(LLVMContext &Context,
882 ArrayRef<Metadata *> Ops) {
883 if (!Ops.empty())
884 if (MDNode *N = dyn_cast_or_null<MDNode>(Ops[0]))
885 if (N->getNumOperands() == Ops.size() && N == N->getOperand(0)) {
886 for (unsigned I = 1, E = Ops.size(); I != E; ++I)
887 if (Ops[I] != N->getOperand(I))
888 return MDNode::get(Context, Ops);
889 return N;
890 }
891
892 return MDNode::get(Context, Ops);
893}
894
895MDNode *MDNode::concatenate(MDNode *A, MDNode *B) {
896 if (!A)
897 return B;
898 if (!B)
899 return A;
900
901 SmallSetVector<Metadata *, 4> MDs(A->op_begin(), A->op_end());
902 MDs.insert(B->op_begin(), B->op_end());
903
904 // FIXME: This preserves long-standing behaviour, but is it really the right
905 // behaviour? Or was that an unintended side-effect of node uniquing?
906 return getOrSelfReference(A->getContext(), MDs.getArrayRef());
907}
908
909MDNode *MDNode::intersect(MDNode *A, MDNode *B) {
910 if (!A || !B)
911 return nullptr;
912
913 SmallSetVector<Metadata *, 4> MDs(A->op_begin(), A->op_end());
914 SmallPtrSet<Metadata *, 4> BSet(B->op_begin(), B->op_end());
915 MDs.remove_if([&](Metadata *MD) { return !is_contained(BSet, MD); });
916
917 // FIXME: This preserves long-standing behaviour, but is it really the right
918 // behaviour? Or was that an unintended side-effect of node uniquing?
919 return getOrSelfReference(A->getContext(), MDs.getArrayRef());
920}
921
922MDNode *MDNode::getMostGenericAliasScope(MDNode *A, MDNode *B) {
923 if (!A || !B)
924 return nullptr;
925
926 return concatenate(A, B);
927}
928
929MDNode *MDNode::getMostGenericFPMath(MDNode *A, MDNode *B) {
930 if (!A || !B)
931 return nullptr;
932
933 APFloat AVal = mdconst::extract<ConstantFP>(A->getOperand(0))->getValueAPF();
934 APFloat BVal = mdconst::extract<ConstantFP>(B->getOperand(0))->getValueAPF();
935 if (AVal.compare(BVal) == APFloat::cmpLessThan)
936 return A;
937 return B;
938}
939
940static bool isContiguous(const ConstantRange &A, const ConstantRange &B) {
941 return A.getUpper() == B.getLower() || A.getLower() == B.getUpper();
942}
943
944static bool canBeMerged(const ConstantRange &A, const ConstantRange &B) {
945 return !A.intersectWith(B).isEmptySet() || isContiguous(A, B);
946}
947
948static bool tryMergeRange(SmallVectorImpl<ConstantInt *> &EndPoints,
949 ConstantInt *Low, ConstantInt *High) {
950 ConstantRange NewRange(Low->getValue(), High->getValue());
951 unsigned Size = EndPoints.size();
952 APInt LB = EndPoints[Size - 2]->getValue();
953 APInt LE = EndPoints[Size - 1]->getValue();
954 ConstantRange LastRange(LB, LE);
955 if (canBeMerged(NewRange, LastRange)) {
956 ConstantRange Union = LastRange.unionWith(NewRange);
957 Type *Ty = High->getType();
958 EndPoints[Size - 2] =
959 cast<ConstantInt>(ConstantInt::get(Ty, Union.getLower()));
960 EndPoints[Size - 1] =
961 cast<ConstantInt>(ConstantInt::get(Ty, Union.getUpper()));
962 return true;
963 }
964 return false;
965}
966
967static void addRange(SmallVectorImpl<ConstantInt *> &EndPoints,
968 ConstantInt *Low, ConstantInt *High) {
969 if (!EndPoints.empty())
970 if (tryMergeRange(EndPoints, Low, High))
971 return;
972
973 EndPoints.push_back(Low);
974 EndPoints.push_back(High);
975}
976
977MDNode *MDNode::getMostGenericRange(MDNode *A, MDNode *B) {
978 // Given two ranges, we want to compute the union of the ranges. This
979 // is slightly complicated by having to combine the intervals and merge
980 // the ones that overlap.
981
982 if (!A || !B)
983 return nullptr;
984
985 if (A == B)
986 return A;
987
988 // First, walk both lists in order of the lower boundary of each interval.
989 // At each step, try to merge the new interval to the last one we adedd.
990 SmallVector<ConstantInt *, 4> EndPoints;
991 int AI = 0;
992 int BI = 0;
993 int AN = A->getNumOperands() / 2;
994 int BN = B->getNumOperands() / 2;
995 while (AI < AN && BI < BN) {
996 ConstantInt *ALow = mdconst::extract<ConstantInt>(A->getOperand(2 * AI));
997 ConstantInt *BLow = mdconst::extract<ConstantInt>(B->getOperand(2 * BI));
998
999 if (ALow->getValue().slt(BLow->getValue())) {
1000 addRange(EndPoints, ALow,
1001 mdconst::extract<ConstantInt>(A->getOperand(2 * AI + 1)));
1002 ++AI;
1003 } else {
1004 addRange(EndPoints, BLow,
1005 mdconst::extract<ConstantInt>(B->getOperand(2 * BI + 1)));
1006 ++BI;
1007 }
1008 }
1009 while (AI < AN) {
1010 addRange(EndPoints, mdconst::extract<ConstantInt>(A->getOperand(2 * AI)),
1011 mdconst::extract<ConstantInt>(A->getOperand(2 * AI + 1)));
1012 ++AI;
1013 }
1014 while (BI < BN) {
1015 addRange(EndPoints, mdconst::extract<ConstantInt>(B->getOperand(2 * BI)),
1016 mdconst::extract<ConstantInt>(B->getOperand(2 * BI + 1)));
1017 ++BI;
1018 }
1019
1020 // If we have more than 2 ranges (4 endpoints) we have to try to merge
1021 // the last and first ones.
1022 unsigned Size = EndPoints.size();
1023 if (Size > 4) {
1024 ConstantInt *FB = EndPoints[0];
1025 ConstantInt *FE = EndPoints[1];
1026 if (tryMergeRange(EndPoints, FB, FE)) {
1027 for (unsigned i = 0; i < Size - 2; ++i) {
1028 EndPoints[i] = EndPoints[i + 2];
1029 }
1030 EndPoints.resize(Size - 2);
1031 }
1032 }
1033
1034 // If in the end we have a single range, it is possible that it is now the
1035 // full range. Just drop the metadata in that case.
1036 if (EndPoints.size() == 2) {
1037 ConstantRange Range(EndPoints[0]->getValue(), EndPoints[1]->getValue());
1038 if (Range.isFullSet())
1039 return nullptr;
1040 }
1041
1042 SmallVector<Metadata *, 4> MDs;
1043 MDs.reserve(EndPoints.size());
1044 for (auto *I : EndPoints)
1045 MDs.push_back(ConstantAsMetadata::get(I));
1046 return MDNode::get(A->getContext(), MDs);
1047}
1048
1049MDNode *MDNode::getMostGenericAlignmentOrDereferenceable(MDNode *A, MDNode *B) {
1050 if (!A || !B)
1051 return nullptr;
1052
1053 ConstantInt *AVal = mdconst::extract<ConstantInt>(A->getOperand(0));
1054 ConstantInt *BVal = mdconst::extract<ConstantInt>(B->getOperand(0));
1055 if (AVal->getZExtValue() < BVal->getZExtValue())
1056 return A;
1057 return B;
1058}
1059
1060//===----------------------------------------------------------------------===//
1061// NamedMDNode implementation.
1062//
1063
1064static SmallVector<TrackingMDRef, 4> &getNMDOps(void *Operands) {
1065 return *(SmallVector<TrackingMDRef, 4> *)Operands;
1066}
1067
1068NamedMDNode::NamedMDNode(const Twine &N)
1069 : Name(N.str()), Operands(new SmallVector<TrackingMDRef, 4>()) {}
1070
1071NamedMDNode::~NamedMDNode() {
1072 dropAllReferences();
1073 delete &getNMDOps(Operands);
1074}
1075
1076unsigned NamedMDNode::getNumOperands() const {
1077 return (unsigned)getNMDOps(Operands).size();
1078}
1079
1080MDNode *NamedMDNode::getOperand(unsigned i) const {
1081 assert(i < getNumOperands() && "Invalid Operand number!")((i < getNumOperands() && "Invalid Operand number!"
) ? static_cast<void> (0) : __assert_fail ("i < getNumOperands() && \"Invalid Operand number!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1081, __PRETTY_FUNCTION__));
1082 auto *N = getNMDOps(Operands)[i].get();
1083 return cast_or_null<MDNode>(N);
1084}
1085
1086void NamedMDNode::addOperand(MDNode *M) { getNMDOps(Operands).emplace_back(M); }
1087
1088void NamedMDNode::setOperand(unsigned I, MDNode *New) {
1089 assert(I < getNumOperands() && "Invalid operand number")((I < getNumOperands() && "Invalid operand number"
) ? static_cast<void> (0) : __assert_fail ("I < getNumOperands() && \"Invalid operand number\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1089, __PRETTY_FUNCTION__));
1090 getNMDOps(Operands)[I].reset(New);
1091}
1092
1093void NamedMDNode::eraseFromParent() { getParent()->eraseNamedMetadata(this); }
1094
1095void NamedMDNode::clearOperands() { getNMDOps(Operands).clear(); }
1096
1097StringRef NamedMDNode::getName() const { return StringRef(Name); }
1098
1099//===----------------------------------------------------------------------===//
1100// Instruction Metadata method implementations.
1101//
1102void MDAttachmentMap::set(unsigned ID, MDNode &MD) {
1103 for (auto &I : Attachments)
1104 if (I.first == ID) {
1105 I.second.reset(&MD);
1106 return;
1107 }
1108 Attachments.emplace_back(std::piecewise_construct, std::make_tuple(ID),
1109 std::make_tuple(&MD));
1110}
1111
1112bool MDAttachmentMap::erase(unsigned ID) {
1113 if (empty())
1114 return false;
1115
1116 // Common case is one/last value.
1117 if (Attachments.back().first == ID) {
1118 Attachments.pop_back();
1119 return true;
1120 }
1121
1122 for (auto I = Attachments.begin(), E = std::prev(Attachments.end()); I != E;
1123 ++I)
1124 if (I->first == ID) {
1125 *I = std::move(Attachments.back());
1126 Attachments.pop_back();
1127 return true;
1128 }
1129
1130 return false;
1131}
1132
1133MDNode *MDAttachmentMap::lookup(unsigned ID) const {
1134 for (const auto &I : Attachments)
1135 if (I.first == ID)
1136 return I.second;
1137 return nullptr;
1138}
1139
1140void MDAttachmentMap::getAll(
1141 SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
1142 Result.append(Attachments.begin(), Attachments.end());
1143
1144 // Sort the resulting array so it is stable.
1145 if (Result.size() > 1)
1146 array_pod_sort(Result.begin(), Result.end());
1147}
1148
1149void MDGlobalAttachmentMap::insert(unsigned ID, MDNode &MD) {
1150 Attachments.push_back({ID, TrackingMDNodeRef(&MD)});
1151}
1152
1153MDNode *MDGlobalAttachmentMap::lookup(unsigned ID) const {
1154 for (const auto &A : Attachments)
1155 if (A.MDKind == ID)
1156 return A.Node;
1157 return nullptr;
1158}
1159
1160void MDGlobalAttachmentMap::get(unsigned ID,
1161 SmallVectorImpl<MDNode *> &Result) const {
1162 for (const auto &A : Attachments)
1163 if (A.MDKind == ID)
1164 Result.push_back(A.Node);
1165}
1166
1167bool MDGlobalAttachmentMap::erase(unsigned ID) {
1168 auto I = std::remove_if(Attachments.begin(), Attachments.end(),
1169 [ID](const Attachment &A) { return A.MDKind == ID; });
1170 bool Changed = I != Attachments.end();
1171 Attachments.erase(I, Attachments.end());
1172 return Changed;
1173}
1174
1175void MDGlobalAttachmentMap::getAll(
1176 SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
1177 for (const auto &A : Attachments)
1178 Result.emplace_back(A.MDKind, A.Node);
1179
1180 // Sort the resulting array so it is stable with respect to metadata IDs. We
1181 // need to preserve the original insertion order though.
1182 llvm::stable_sort(Result, less_first());
1183}
1184
1185void Instruction::setMetadata(StringRef Kind, MDNode *Node) {
1186 if (!Node && !hasMetadata())
1187 return;
1188 setMetadata(getContext().getMDKindID(Kind), Node);
1189}
1190
1191MDNode *Instruction::getMetadataImpl(StringRef Kind) const {
1192 return getMetadataImpl(getContext().getMDKindID(Kind));
1193}
1194
1195void Instruction::dropUnknownNonDebugMetadata(ArrayRef<unsigned> KnownIDs) {
1196 if (!hasMetadataHashEntry())
1197 return; // Nothing to remove!
1198
1199 auto &InstructionMetadata = getContext().pImpl->InstructionMetadata;
1200
1201 SmallSet<unsigned, 4> KnownSet;
1202 KnownSet.insert(KnownIDs.begin(), KnownIDs.end());
1203 if (KnownSet.empty()) {
1204 // Just drop our entry at the store.
1205 InstructionMetadata.erase(this);
1206 setHasMetadataHashEntry(false);
1207 return;
1208 }
1209
1210 auto &Info = InstructionMetadata[this];
1211 Info.remove_if([&KnownSet](const std::pair<unsigned, TrackingMDNodeRef> &I) {
1212 return !KnownSet.count(I.first);
1213 });
1214
1215 if (Info.empty()) {
1216 // Drop our entry at the store.
1217 InstructionMetadata.erase(this);
1218 setHasMetadataHashEntry(false);
1219 }
1220}
1221
1222void Instruction::setMetadata(unsigned KindID, MDNode *Node) {
1223 if (!Node && !hasMetadata())
1224 return;
1225
1226 // Handle 'dbg' as a special case since it is not stored in the hash table.
1227 if (KindID == LLVMContext::MD_dbg) {
1228 DbgLoc = DebugLoc(Node);
1229 return;
1230 }
1231
1232 // Handle the case when we're adding/updating metadata on an instruction.
1233 if (Node) {
1234 auto &Info = getContext().pImpl->InstructionMetadata[this];
1235 assert(!Info.empty() == hasMetadataHashEntry() &&((!Info.empty() == hasMetadataHashEntry() && "HasMetadata bit is wonked"
) ? static_cast<void> (0) : __assert_fail ("!Info.empty() == hasMetadataHashEntry() && \"HasMetadata bit is wonked\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1236, __PRETTY_FUNCTION__))
1236 "HasMetadata bit is wonked")((!Info.empty() == hasMetadataHashEntry() && "HasMetadata bit is wonked"
) ? static_cast<void> (0) : __assert_fail ("!Info.empty() == hasMetadataHashEntry() && \"HasMetadata bit is wonked\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1236, __PRETTY_FUNCTION__));
1237 if (Info.empty())
1238 setHasMetadataHashEntry(true);
1239 Info.set(KindID, *Node);
1240 return;
1241 }
1242
1243 // Otherwise, we're removing metadata from an instruction.
1244 assert((hasMetadataHashEntry() ==(((hasMetadataHashEntry() == (getContext().pImpl->InstructionMetadata
.count(this) > 0)) && "HasMetadata bit out of date!"
) ? static_cast<void> (0) : __assert_fail ("(hasMetadataHashEntry() == (getContext().pImpl->InstructionMetadata.count(this) > 0)) && \"HasMetadata bit out of date!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1246, __PRETTY_FUNCTION__))
1245 (getContext().pImpl->InstructionMetadata.count(this) > 0)) &&(((hasMetadataHashEntry() == (getContext().pImpl->InstructionMetadata
.count(this) > 0)) && "HasMetadata bit out of date!"
) ? static_cast<void> (0) : __assert_fail ("(hasMetadataHashEntry() == (getContext().pImpl->InstructionMetadata.count(this) > 0)) && \"HasMetadata bit out of date!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1246, __PRETTY_FUNCTION__))
1246 "HasMetadata bit out of date!")(((hasMetadataHashEntry() == (getContext().pImpl->InstructionMetadata
.count(this) > 0)) && "HasMetadata bit out of date!"
) ? static_cast<void> (0) : __assert_fail ("(hasMetadataHashEntry() == (getContext().pImpl->InstructionMetadata.count(this) > 0)) && \"HasMetadata bit out of date!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1246, __PRETTY_FUNCTION__));
1247 if (!hasMetadataHashEntry())
1248 return; // Nothing to remove!
1249 auto &Info = getContext().pImpl->InstructionMetadata[this];
1250
1251 // Handle removal of an existing value.
1252 Info.erase(KindID);
1253
1254 if (!Info.empty())
1255 return;
1256
1257 getContext().pImpl->InstructionMetadata.erase(this);
1258 setHasMetadataHashEntry(false);
1259}
1260
1261void Instruction::setAAMetadata(const AAMDNodes &N) {
1262 setMetadata(LLVMContext::MD_tbaa, N.TBAA);
1263 setMetadata(LLVMContext::MD_alias_scope, N.Scope);
1264 setMetadata(LLVMContext::MD_noalias, N.NoAlias);
1265}
1266
1267MDNode *Instruction::getMetadataImpl(unsigned KindID) const {
1268 // Handle 'dbg' as a special case since it is not stored in the hash table.
1269 if (KindID == LLVMContext::MD_dbg)
1270 return DbgLoc.getAsMDNode();
1271
1272 if (!hasMetadataHashEntry())
1273 return nullptr;
1274 auto &Info = getContext().pImpl->InstructionMetadata[this];
1275 assert(!Info.empty() && "bit out of sync with hash table")((!Info.empty() && "bit out of sync with hash table")
? static_cast<void> (0) : __assert_fail ("!Info.empty() && \"bit out of sync with hash table\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1275, __PRETTY_FUNCTION__));
1276
1277 return Info.lookup(KindID);
1278}
1279
1280void Instruction::getAllMetadataImpl(
1281 SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
1282 Result.clear();
1283
1284 // Handle 'dbg' as a special case since it is not stored in the hash table.
1285 if (DbgLoc) {
1286 Result.push_back(
1287 std::make_pair((unsigned)LLVMContext::MD_dbg, DbgLoc.getAsMDNode()));
1288 if (!hasMetadataHashEntry())
1289 return;
1290 }
1291
1292 assert(hasMetadataHashEntry() &&((hasMetadataHashEntry() && getContext().pImpl->InstructionMetadata
.count(this) && "Shouldn't have called this") ? static_cast
<void> (0) : __assert_fail ("hasMetadataHashEntry() && getContext().pImpl->InstructionMetadata.count(this) && \"Shouldn't have called this\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1294, __PRETTY_FUNCTION__))
1293 getContext().pImpl->InstructionMetadata.count(this) &&((hasMetadataHashEntry() && getContext().pImpl->InstructionMetadata
.count(this) && "Shouldn't have called this") ? static_cast
<void> (0) : __assert_fail ("hasMetadataHashEntry() && getContext().pImpl->InstructionMetadata.count(this) && \"Shouldn't have called this\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1294, __PRETTY_FUNCTION__))
1294 "Shouldn't have called this")((hasMetadataHashEntry() && getContext().pImpl->InstructionMetadata
.count(this) && "Shouldn't have called this") ? static_cast
<void> (0) : __assert_fail ("hasMetadataHashEntry() && getContext().pImpl->InstructionMetadata.count(this) && \"Shouldn't have called this\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1294, __PRETTY_FUNCTION__));
1295 const auto &Info = getContext().pImpl->InstructionMetadata.find(this)->second;
1296 assert(!Info.empty() && "Shouldn't have called this")((!Info.empty() && "Shouldn't have called this") ? static_cast
<void> (0) : __assert_fail ("!Info.empty() && \"Shouldn't have called this\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1296, __PRETTY_FUNCTION__));
1297 Info.getAll(Result);
1298}
1299
1300void Instruction::getAllMetadataOtherThanDebugLocImpl(
1301 SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
1302 Result.clear();
1303 assert(hasMetadataHashEntry() &&((hasMetadataHashEntry() && getContext().pImpl->InstructionMetadata
.count(this) && "Shouldn't have called this") ? static_cast
<void> (0) : __assert_fail ("hasMetadataHashEntry() && getContext().pImpl->InstructionMetadata.count(this) && \"Shouldn't have called this\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1305, __PRETTY_FUNCTION__))
1304 getContext().pImpl->InstructionMetadata.count(this) &&((hasMetadataHashEntry() && getContext().pImpl->InstructionMetadata
.count(this) && "Shouldn't have called this") ? static_cast
<void> (0) : __assert_fail ("hasMetadataHashEntry() && getContext().pImpl->InstructionMetadata.count(this) && \"Shouldn't have called this\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1305, __PRETTY_FUNCTION__))
1305 "Shouldn't have called this")((hasMetadataHashEntry() && getContext().pImpl->InstructionMetadata
.count(this) && "Shouldn't have called this") ? static_cast
<void> (0) : __assert_fail ("hasMetadataHashEntry() && getContext().pImpl->InstructionMetadata.count(this) && \"Shouldn't have called this\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1305, __PRETTY_FUNCTION__));
1306 const auto &Info = getContext().pImpl->InstructionMetadata.find(this)->second;
1307 assert(!Info.empty() && "Shouldn't have called this")((!Info.empty() && "Shouldn't have called this") ? static_cast
<void> (0) : __assert_fail ("!Info.empty() && \"Shouldn't have called this\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1307, __PRETTY_FUNCTION__));
1308 Info.getAll(Result);
1309}
1310
1311bool Instruction::extractProfMetadata(uint64_t &TrueVal,
1312 uint64_t &FalseVal) const {
1313 assert((((getOpcode() == Instruction::Br || getOpcode() == Instruction
::Select) && "Looking for branch weights on something besides branch or select"
) ? static_cast<void> (0) : __assert_fail ("(getOpcode() == Instruction::Br || getOpcode() == Instruction::Select) && \"Looking for branch weights on something besides branch or select\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1315, __PRETTY_FUNCTION__))
1314 (getOpcode() == Instruction::Br || getOpcode() == Instruction::Select) &&(((getOpcode() == Instruction::Br || getOpcode() == Instruction
::Select) && "Looking for branch weights on something besides branch or select"
) ? static_cast<void> (0) : __assert_fail ("(getOpcode() == Instruction::Br || getOpcode() == Instruction::Select) && \"Looking for branch weights on something besides branch or select\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1315, __PRETTY_FUNCTION__))
1315 "Looking for branch weights on something besides branch or select")(((getOpcode() == Instruction::Br || getOpcode() == Instruction
::Select) && "Looking for branch weights on something besides branch or select"
) ? static_cast<void> (0) : __assert_fail ("(getOpcode() == Instruction::Br || getOpcode() == Instruction::Select) && \"Looking for branch weights on something besides branch or select\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1315, __PRETTY_FUNCTION__));
1316
1317 auto *ProfileData = getMetadata(LLVMContext::MD_prof);
1318 if (!ProfileData || ProfileData->getNumOperands() != 3)
1319 return false;
1320
1321 auto *ProfDataName = dyn_cast<MDString>(ProfileData->getOperand(0));
1322 if (!ProfDataName || !ProfDataName->getString().equals("branch_weights"))
1323 return false;
1324
1325 auto *CITrue = mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(1));
1326 auto *CIFalse = mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(2));
1327 if (!CITrue || !CIFalse)
1328 return false;
1329
1330 TrueVal = CITrue->getValue().getZExtValue();
1331 FalseVal = CIFalse->getValue().getZExtValue();
1332
1333 return true;
1334}
1335
1336bool Instruction::extractProfTotalWeight(uint64_t &TotalVal) const {
1337 assert((getOpcode() == Instruction::Br ||(((getOpcode() == Instruction::Br || getOpcode() == Instruction
::Select || getOpcode() == Instruction::Call || getOpcode() ==
Instruction::Invoke || getOpcode() == Instruction::Switch) &&
"Looking for branch weights on something besides branch") ? static_cast
<void> (0) : __assert_fail ("(getOpcode() == Instruction::Br || getOpcode() == Instruction::Select || getOpcode() == Instruction::Call || getOpcode() == Instruction::Invoke || getOpcode() == Instruction::Switch) && \"Looking for branch weights on something besides branch\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1342, __PRETTY_FUNCTION__))
1338 getOpcode() == Instruction::Select ||(((getOpcode() == Instruction::Br || getOpcode() == Instruction
::Select || getOpcode() == Instruction::Call || getOpcode() ==
Instruction::Invoke || getOpcode() == Instruction::Switch) &&
"Looking for branch weights on something besides branch") ? static_cast
<void> (0) : __assert_fail ("(getOpcode() == Instruction::Br || getOpcode() == Instruction::Select || getOpcode() == Instruction::Call || getOpcode() == Instruction::Invoke || getOpcode() == Instruction::Switch) && \"Looking for branch weights on something besides branch\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1342, __PRETTY_FUNCTION__))
1339 getOpcode() == Instruction::Call ||(((getOpcode() == Instruction::Br || getOpcode() == Instruction
::Select || getOpcode() == Instruction::Call || getOpcode() ==
Instruction::Invoke || getOpcode() == Instruction::Switch) &&
"Looking for branch weights on something besides branch") ? static_cast
<void> (0) : __assert_fail ("(getOpcode() == Instruction::Br || getOpcode() == Instruction::Select || getOpcode() == Instruction::Call || getOpcode() == Instruction::Invoke || getOpcode() == Instruction::Switch) && \"Looking for branch weights on something besides branch\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1342, __PRETTY_FUNCTION__))
1340 getOpcode() == Instruction::Invoke ||(((getOpcode() == Instruction::Br || getOpcode() == Instruction
::Select || getOpcode() == Instruction::Call || getOpcode() ==
Instruction::Invoke || getOpcode() == Instruction::Switch) &&
"Looking for branch weights on something besides branch") ? static_cast
<void> (0) : __assert_fail ("(getOpcode() == Instruction::Br || getOpcode() == Instruction::Select || getOpcode() == Instruction::Call || getOpcode() == Instruction::Invoke || getOpcode() == Instruction::Switch) && \"Looking for branch weights on something besides branch\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1342, __PRETTY_FUNCTION__))
1341 getOpcode() == Instruction::Switch) &&(((getOpcode() == Instruction::Br || getOpcode() == Instruction
::Select || getOpcode() == Instruction::Call || getOpcode() ==
Instruction::Invoke || getOpcode() == Instruction::Switch) &&
"Looking for branch weights on something besides branch") ? static_cast
<void> (0) : __assert_fail ("(getOpcode() == Instruction::Br || getOpcode() == Instruction::Select || getOpcode() == Instruction::Call || getOpcode() == Instruction::Invoke || getOpcode() == Instruction::Switch) && \"Looking for branch weights on something besides branch\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1342, __PRETTY_FUNCTION__))
1342 "Looking for branch weights on something besides branch")(((getOpcode() == Instruction::Br || getOpcode() == Instruction
::Select || getOpcode() == Instruction::Call || getOpcode() ==
Instruction::Invoke || getOpcode() == Instruction::Switch) &&
"Looking for branch weights on something besides branch") ? static_cast
<void> (0) : __assert_fail ("(getOpcode() == Instruction::Br || getOpcode() == Instruction::Select || getOpcode() == Instruction::Call || getOpcode() == Instruction::Invoke || getOpcode() == Instruction::Switch) && \"Looking for branch weights on something besides branch\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1342, __PRETTY_FUNCTION__));
1343
1344 TotalVal = 0;
1345 auto *ProfileData = getMetadata(LLVMContext::MD_prof);
1346 if (!ProfileData)
1347 return false;
1348
1349 auto *ProfDataName = dyn_cast<MDString>(ProfileData->getOperand(0));
1350 if (!ProfDataName)
1351 return false;
1352
1353 if (ProfDataName->getString().equals("branch_weights")) {
1354 TotalVal = 0;
1355 for (unsigned i = 1; i < ProfileData->getNumOperands(); i++) {
1356 auto *V = mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(i));
1357 if (!V)
1358 return false;
1359 TotalVal += V->getValue().getZExtValue();
1360 }
1361 return true;
1362 } else if (ProfDataName->getString().equals("VP") &&
1363 ProfileData->getNumOperands() > 3) {
1364 TotalVal = mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(2))
1365 ->getValue()
1366 .getZExtValue();
1367 return true;
1368 }
1369 return false;
1370}
1371
1372void Instruction::clearMetadataHashEntries() {
1373 assert(hasMetadataHashEntry() && "Caller should check")((hasMetadataHashEntry() && "Caller should check") ? static_cast
<void> (0) : __assert_fail ("hasMetadataHashEntry() && \"Caller should check\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/IR/Metadata.cpp"
, 1373, __PRETTY_FUNCTION__));
1374 getContext().pImpl->InstructionMetadata.erase(this);
1375 setHasMetadataHashEntry(false);
1376}
1377
1378void GlobalObject::getMetadata(unsigned KindID,
1379 SmallVectorImpl<MDNode *> &MDs) const {
1380 if (hasMetadata())
1381 getContext().pImpl->GlobalObjectMetadata[this].get(KindID, MDs);
1382}
1383
1384void GlobalObject::getMetadata(StringRef Kind,
1385 SmallVectorImpl<MDNode *> &MDs) const {
1386 if (hasMetadata())
1387 getMetadata(getContext().getMDKindID(Kind), MDs);
1388}
1389
1390void GlobalObject::addMetadata(unsigned KindID, MDNode &MD) {
1391 if (!hasMetadata())
1392 setHasMetadataHashEntry(true);
1393
1394 getContext().pImpl->GlobalObjectMetadata[this].insert(KindID, MD);
1395}
1396
1397void GlobalObject::addMetadata(StringRef Kind, MDNode &MD) {
1398 addMetadata(getContext().getMDKindID(Kind), MD);
1399}
1400
1401bool GlobalObject::eraseMetadata(unsigned KindID) {
1402 // Nothing to unset.
1403 if (!hasMetadata())
1404 return false;
1405
1406 auto &Store = getContext().pImpl->GlobalObjectMetadata[this];
1407 bool Changed = Store.erase(KindID);
1408 if (Store.empty())
1409 clearMetadata();
1410 return Changed;
1411}
1412
1413void GlobalObject::getAllMetadata(
1414 SmallVectorImpl<std::pair<unsigned, MDNode *>> &MDs) const {
1415 MDs.clear();
1416
1417 if (!hasMetadata())
1418 return;
1419
1420 getContext().pImpl->GlobalObjectMetadata[this].getAll(MDs);
1421}
1422
1423void GlobalObject::clearMetadata() {
1424 if (!hasMetadata())
1425 return;
1426 getContext().pImpl->GlobalObjectMetadata.erase(this);
1427 setHasMetadataHashEntry(false);
1428}
1429
1430void GlobalObject::setMetadata(unsigned KindID, MDNode *N) {
1431 eraseMetadata(KindID);
1432 if (N)
1433 addMetadata(KindID, *N);
1434}
1435
1436void GlobalObject::setMetadata(StringRef Kind, MDNode *N) {
1437 setMetadata(getContext().getMDKindID(Kind), N);
1438}
1439
1440MDNode *GlobalObject::getMetadata(unsigned KindID) const {
1441 if (hasMetadata())
1442 return getContext().pImpl->GlobalObjectMetadata[this].lookup(KindID);
1443 return nullptr;
1444}
1445
1446MDNode *GlobalObject::getMetadata(StringRef Kind) const {
1447 return getMetadata(getContext().getMDKindID(Kind));
1448}
1449
1450void GlobalObject::copyMetadata(const GlobalObject *Other, unsigned Offset) {
1451 SmallVector<std::pair<unsigned, MDNode *>, 8> MDs;
1452 Other->getAllMetadata(MDs);
1453 for (auto &MD : MDs) {
1454 // We need to adjust the type metadata offset.
1455 if (Offset != 0 && MD.first == LLVMContext::MD_type) {
1456 auto *OffsetConst = cast<ConstantInt>(
1457 cast<ConstantAsMetadata>(MD.second->getOperand(0))->getValue());
1458 Metadata *TypeId = MD.second->getOperand(1);
1459 auto *NewOffsetMD = ConstantAsMetadata::get(ConstantInt::get(
1460 OffsetConst->getType(), OffsetConst->getValue() + Offset));
1461 addMetadata(LLVMContext::MD_type,
1462 *MDNode::get(getContext(), {NewOffsetMD, TypeId}));
1463 continue;
1464 }
1465 // If an offset adjustment was specified we need to modify the DIExpression
1466 // to prepend the adjustment:
1467 // !DIExpression(DW_OP_plus, Offset, [original expr])
1468 auto *Attachment = MD.second;
1469 if (Offset != 0 && MD.first == LLVMContext::MD_dbg) {
1470 DIGlobalVariable *GV = dyn_cast<DIGlobalVariable>(Attachment);
1471 DIExpression *E = nullptr;
1472 if (!GV) {
1473 auto *GVE = cast<DIGlobalVariableExpression>(Attachment);
1474 GV = GVE->getVariable();
1475 E = GVE->getExpression();
1476 }
1477 ArrayRef<uint64_t> OrigElements;
1478 if (E)
1479 OrigElements = E->getElements();
1480 std::vector<uint64_t> Elements(OrigElements.size() + 2);
1481 Elements[0] = dwarf::DW_OP_plus_uconst;
1482 Elements[1] = Offset;
1483 llvm::copy(OrigElements, Elements.begin() + 2);
1484 E = DIExpression::get(getContext(), Elements);
1485 Attachment = DIGlobalVariableExpression::get(getContext(), GV, E);
1486 }
1487 addMetadata(MD.first, *Attachment);
1488 }
1489}
1490
1491void GlobalObject::addTypeMetadata(unsigned Offset, Metadata *TypeID) {
1492 addMetadata(
1493 LLVMContext::MD_type,
1494 *MDTuple::get(getContext(),
1495 {ConstantAsMetadata::get(ConstantInt::get(
1496 Type::getInt64Ty(getContext()), Offset)),
1497 TypeID}));
1498}
1499
1500void Function::setSubprogram(DISubprogram *SP) {
1501 setMetadata(LLVMContext::MD_dbg, SP);
1502}
1503
1504DISubprogram *Function::getSubprogram() const {
1505 return cast_or_null<DISubprogram>(getMetadata(LLVMContext::MD_dbg));
1506}
1507
1508bool Function::isDebugInfoForProfiling() const {
1509 if (DISubprogram *SP = getSubprogram()) {
1510 if (DICompileUnit *CU = SP->getUnit()) {
1511 return CU->getDebugInfoForProfiling();
1512 }
1513 }
1514 return false;
1515}
1516
1517void GlobalVariable::addDebugInfo(DIGlobalVariableExpression *GV) {
1518 addMetadata(LLVMContext::MD_dbg, *GV);
1519}
1520
1521void GlobalVariable::getDebugInfo(
1522 SmallVectorImpl<DIGlobalVariableExpression *> &GVs) const {
1523 SmallVector<MDNode *, 1> MDs;
1524 getMetadata(LLVMContext::MD_dbg, MDs);
1525 for (MDNode *MD : MDs)
1526 GVs.push_back(cast<DIGlobalVariableExpression>(MD));
1527}
←

/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/IR/Metadata.h

→
1//===- llvm/IR/Metadata.h - Metadata definitions ----------------*- C++ -*-===//
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/// @file
10/// This file contains the declarations for metadata subclasses.
11/// They represent the different flavors of metadata that live in LLVM.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_IR_METADATA_H
16#define LLVM_IR_METADATA_H
17
18#include "llvm/ADT/ArrayRef.h"
19#include "llvm/ADT/DenseMap.h"
20#include "llvm/ADT/DenseMapInfo.h"
21#include "llvm/ADT/None.h"
22#include "llvm/ADT/PointerUnion.h"
23#include "llvm/ADT/STLExtras.h"
24#include "llvm/ADT/SmallVector.h"
25#include "llvm/ADT/StringRef.h"
26#include "llvm/ADT/ilist_node.h"
27#include "llvm/ADT/iterator_range.h"
28#include "llvm/IR/Constant.h"
29#include "llvm/IR/LLVMContext.h"
30#include "llvm/IR/Value.h"
31#include "llvm/Support/CBindingWrapping.h"
32#include "llvm/Support/Casting.h"
33#include "llvm/Support/ErrorHandling.h"
34#include <cassert>
35#include <cstddef>
36#include <cstdint>
37#include <iterator>
38#include <memory>
39#include <string>
40#include <type_traits>
41#include <utility>
42
43namespace llvm {
44
45class Module;
46class ModuleSlotTracker;
47class raw_ostream;
48class Type;
49
50enum LLVMConstants : uint32_t {
51 DEBUG_METADATA_VERSION = 3 // Current debug info version number.
52};
53
54/// Root of the metadata hierarchy.
55///
56/// This is a root class for typeless data in the IR.
57class Metadata {
58 friend class ReplaceableMetadataImpl;
59
60 /// RTTI.
61 const unsigned char SubclassID;
62
63protected:
64 /// Active type of storage.
65 enum StorageType { Uniqued, Distinct, Temporary };
66
67 /// Storage flag for non-uniqued, otherwise unowned, metadata.
68 unsigned char Storage : 7;
69 // TODO: expose remaining bits to subclasses.
70
71 unsigned char ImplicitCode : 1;
72
73 unsigned short SubclassData16 = 0;
74 unsigned SubclassData32 = 0;
75
76public:
77 enum MetadataKind {
78#define HANDLE_METADATA_LEAF(CLASS) CLASS##Kind,
79#include "llvm/IR/Metadata.def"
80 };
81
82protected:
83 Metadata(unsigned ID, StorageType Storage)
84 : SubclassID(ID), Storage(Storage), ImplicitCode(false) {
85 static_assert(sizeof(*this) == 8, "Metadata fields poorly packed");
86 }
87
88 ~Metadata() = default;
89
90 /// Default handling of a changed operand, which asserts.
91 ///
92 /// If subclasses pass themselves in as owners to a tracking node reference,
93 /// they must provide an implementation of this method.
94 void handleChangedOperand(void *, Metadata *) {
95 llvm_unreachable("Unimplemented in Metadata subclass")::llvm::llvm_unreachable_internal("Unimplemented in Metadata subclass"
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/IR/Metadata.h"
, 95);
96 }
97
98public:
99 unsigned getMetadataID() const { return SubclassID; }
100
101 /// User-friendly dump.
102 ///
103 /// If \c M is provided, metadata nodes will be numbered canonically;
104 /// otherwise, pointer addresses are substituted.
105 ///
106 /// Note: this uses an explicit overload instead of default arguments so that
107 /// the nullptr version is easy to call from a debugger.
108 ///
109 /// @{
110 void dump() const;
111 void dump(const Module *M) const;
112 /// @}
113
114 /// Print.
115 ///
116 /// Prints definition of \c this.
117 ///
118 /// If \c M is provided, metadata nodes will be numbered canonically;
119 /// otherwise, pointer addresses are substituted.
120 /// @{
121 void print(raw_ostream &OS, const Module *M = nullptr,
122 bool IsForDebug = false) const;
123 void print(raw_ostream &OS, ModuleSlotTracker &MST, const Module *M = nullptr,
124 bool IsForDebug = false) const;
125 /// @}
126
127 /// Print as operand.
128 ///
129 /// Prints reference of \c this.
130 ///
131 /// If \c M is provided, metadata nodes will be numbered canonically;
132 /// otherwise, pointer addresses are substituted.
133 /// @{
134 void printAsOperand(raw_ostream &OS, const Module *M = nullptr) const;
135 void printAsOperand(raw_ostream &OS, ModuleSlotTracker &MST,
136 const Module *M = nullptr) const;
137 /// @}
138};
139
140// Create wrappers for C Binding types (see CBindingWrapping.h).
141DEFINE_ISA_CONVERSION_FUNCTIONS(Metadata, LLVMMetadataRef)inline Metadata *unwrap(LLVMMetadataRef P) { return reinterpret_cast
<Metadata*>(P); } inline LLVMMetadataRef wrap(const Metadata
*P) { return reinterpret_cast<LLVMMetadataRef>(const_cast
<Metadata*>(P)); } template<typename T> inline T *
unwrap(LLVMMetadataRef P) { return cast<T>(unwrap(P)); }
142
143// Specialized opaque metadata conversions.
144inline Metadata **unwrap(LLVMMetadataRef *MDs) {
145 return reinterpret_cast<Metadata**>(MDs);
146}
147
148#define HANDLE_METADATA(CLASS) class CLASS;
149#include "llvm/IR/Metadata.def"
150
151// Provide specializations of isa so that we don't need definitions of
152// subclasses to see if the metadata is a subclass.
153#define HANDLE_METADATA_LEAF(CLASS) \
154 template <> struct isa_impl<CLASS, Metadata> { \
155 static inline bool doit(const Metadata &MD) { \
156 return MD.getMetadataID() == Metadata::CLASS##Kind; \
157 } \
158 };
159#include "llvm/IR/Metadata.def"
160
161inline raw_ostream &operator<<(raw_ostream &OS, const Metadata &MD) {
162 MD.print(OS);
163 return OS;
164}
165
166/// Metadata wrapper in the Value hierarchy.
167///
168/// A member of the \a Value hierarchy to represent a reference to metadata.
169/// This allows, e.g., instrinsics to have metadata as operands.
170///
171/// Notably, this is the only thing in either hierarchy that is allowed to
172/// reference \a LocalAsMetadata.
173class MetadataAsValue : public Value {
174 friend class ReplaceableMetadataImpl;
175 friend class LLVMContextImpl;
176
177 Metadata *MD;
178
179 MetadataAsValue(Type *Ty, Metadata *MD);
180
181 /// Drop use of metadata (during teardown).
182 void dropUse() { MD = nullptr; }
183
184public:
185 ~MetadataAsValue();
186
187 static MetadataAsValue *get(LLVMContext &Context, Metadata *MD);
188 static MetadataAsValue *getIfExists(LLVMContext &Context, Metadata *MD);
189
190 Metadata *getMetadata() const { return MD; }
191
192 static bool classof(const Value *V) {
193 return V->getValueID() == MetadataAsValueVal;
194 }
195
196private:
197 void handleChangedMetadata(Metadata *MD);
198 void track();
199 void untrack();
200};
201
202/// API for tracking metadata references through RAUW and deletion.
203///
204/// Shared API for updating \a Metadata pointers in subclasses that support
205/// RAUW.
206///
207/// This API is not meant to be used directly. See \a TrackingMDRef for a
208/// user-friendly tracking reference.
209class MetadataTracking {
210public:
211 /// Track the reference to metadata.
212 ///
213 /// Register \c MD with \c *MD, if the subclass supports tracking. If \c *MD
214 /// gets RAUW'ed, \c MD will be updated to the new address. If \c *MD gets
215 /// deleted, \c MD will be set to \c nullptr.
216 ///
217 /// If tracking isn't supported, \c *MD will not change.
218 ///
219 /// \return true iff tracking is supported by \c MD.
220 static bool track(Metadata *&MD) {
221 return track(&MD, *MD, static_cast<Metadata *>(nullptr));
222 }
223
224 /// Track the reference to metadata for \a Metadata.
225 ///
226 /// As \a track(Metadata*&), but with support for calling back to \c Owner to
227 /// tell it that its operand changed. This could trigger \c Owner being
228 /// re-uniqued.
229 static bool track(void *Ref, Metadata &MD, Metadata &Owner) {
230 return track(Ref, MD, &Owner);
231 }
232
233 /// Track the reference to metadata for \a MetadataAsValue.
234 ///
235 /// As \a track(Metadata*&), but with support for calling back to \c Owner to
236 /// tell it that its operand changed. This could trigger \c Owner being
237 /// re-uniqued.
238 static bool track(void *Ref, Metadata &MD, MetadataAsValue &Owner) {
239 return track(Ref, MD, &Owner);
240 }
241
242 /// Stop tracking a reference to metadata.
243 ///
244 /// Stops \c *MD from tracking \c MD.
245 static void untrack(Metadata *&MD) { untrack(&MD, *MD); }
246 static void untrack(void *Ref, Metadata &MD);
247
248 /// Move tracking from one reference to another.
249 ///
250 /// Semantically equivalent to \c untrack(MD) followed by \c track(New),
251 /// except that ownership callbacks are maintained.
252 ///
253 /// Note: it is an error if \c *MD does not equal \c New.
254 ///
255 /// \return true iff tracking is supported by \c MD.
256 static bool retrack(Metadata *&MD, Metadata *&New) {
257 return retrack(&MD, *MD, &New);
258 }
259 static bool retrack(void *Ref, Metadata &MD, void *New);
260
261 /// Check whether metadata is replaceable.
262 static bool isReplaceable(const Metadata &MD);
263
264 using OwnerTy = PointerUnion<MetadataAsValue *, Metadata *>;
265
266private:
267 /// Track a reference to metadata for an owner.
268 ///
269 /// Generalized version of tracking.
270 static bool track(void *Ref, Metadata &MD, OwnerTy Owner);
271};
272
273/// Shared implementation of use-lists for replaceable metadata.
274///
275/// Most metadata cannot be RAUW'ed. This is a shared implementation of
276/// use-lists and associated API for the two that support it (\a ValueAsMetadata
277/// and \a TempMDNode).
278class ReplaceableMetadataImpl {
279 friend class MetadataTracking;
280
281public:
282 using OwnerTy = MetadataTracking::OwnerTy;
283
284private:
285 LLVMContext &Context;
286 uint64_t NextIndex = 0;
287 SmallDenseMap<void *, std::pair<OwnerTy, uint64_t>, 4> UseMap;
288
289public:
290 ReplaceableMetadataImpl(LLVMContext &Context) : Context(Context) {}
291
292 ~ReplaceableMetadataImpl() {
293 assert(UseMap.empty() && "Cannot destroy in-use replaceable metadata")((UseMap.empty() && "Cannot destroy in-use replaceable metadata"
) ? static_cast<void> (0) : __assert_fail ("UseMap.empty() && \"Cannot destroy in-use replaceable metadata\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/IR/Metadata.h"
, 293, __PRETTY_FUNCTION__));
294 }
295
296 LLVMContext &getContext() const { return Context; }
297
298 /// Replace all uses of this with MD.
299 ///
300 /// Replace all uses of this with \c MD, which is allowed to be null.
301 void replaceAllUsesWith(Metadata *MD);
302
303 /// Resolve all uses of this.
304 ///
305 /// Resolve all uses of this, turning off RAUW permanently. If \c
306 /// ResolveUsers, call \a MDNode::resolve() on any users whose last operand
307 /// is resolved.
308 void resolveAllUses(bool ResolveUsers = true);
309
310private:
311 void addRef(void *Ref, OwnerTy Owner);
312 void dropRef(void *Ref);
313 void moveRef(void *Ref, void *New, const Metadata &MD);
314
315 /// Lazily construct RAUW support on MD.
316 ///
317 /// If this is an unresolved MDNode, RAUW support will be created on-demand.
318 /// ValueAsMetadata always has RAUW support.
319 static ReplaceableMetadataImpl *getOrCreate(Metadata &MD);
320
321 /// Get RAUW support on MD, if it exists.
322 static ReplaceableMetadataImpl *getIfExists(Metadata &MD);
323
324 /// Check whether this node will support RAUW.
325 ///
326 /// Returns \c true unless getOrCreate() would return null.
327 static bool isReplaceable(const Metadata &MD);
328};
329
330/// Value wrapper in the Metadata hierarchy.
331///
332/// This is a custom value handle that allows other metadata to refer to
333/// classes in the Value hierarchy.
334///
335/// Because of full uniquing support, each value is only wrapped by a single \a
336/// ValueAsMetadata object, so the lookup maps are far more efficient than
337/// those using ValueHandleBase.
338class ValueAsMetadata : public Metadata, ReplaceableMetadataImpl {
339 friend class ReplaceableMetadataImpl;
340 friend class LLVMContextImpl;
341
342 Value *V;
343
344 /// Drop users without RAUW (during teardown).
345 void dropUsers() {
346 ReplaceableMetadataImpl::resolveAllUses(/* ResolveUsers */ false);
347 }
348
349protected:
350 ValueAsMetadata(unsigned ID, Value *V)
351 : Metadata(ID, Uniqued), ReplaceableMetadataImpl(V->getContext()), V(V) {
352 assert(V && "Expected valid value")((V && "Expected valid value") ? static_cast<void>
(0) : __assert_fail ("V && \"Expected valid value\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/IR/Metadata.h"
, 352, __PRETTY_FUNCTION__));
353 }
354
355 ~ValueAsMetadata() = default;
356
357public:
358 static ValueAsMetadata *get(Value *V);
359
360 static ConstantAsMetadata *getConstant(Value *C) {
361 return cast<ConstantAsMetadata>(get(C));
362 }
363
364 static LocalAsMetadata *getLocal(Value *Local) {
365 return cast<LocalAsMetadata>(get(Local));
366 }
367
368 static ValueAsMetadata *getIfExists(Value *V);
369
370 static ConstantAsMetadata *getConstantIfExists(Value *C) {
371 return cast_or_null<ConstantAsMetadata>(getIfExists(C));
372 }
373
374 static LocalAsMetadata *getLocalIfExists(Value *Local) {
375 return cast_or_null<LocalAsMetadata>(getIfExists(Local));
376 }
377
378 Value *getValue() const { return V; }
379 Type *getType() const { return V->getType(); }
380 LLVMContext &getContext() const { return V->getContext(); }
381
382 static void handleDeletion(Value *V);
383 static void handleRAUW(Value *From, Value *To);
384
385protected:
386 /// Handle collisions after \a Value::replaceAllUsesWith().
387 ///
388 /// RAUW isn't supported directly for \a ValueAsMetadata, but if the wrapped
389 /// \a Value gets RAUW'ed and the target already exists, this is used to
390 /// merge the two metadata nodes.
391 void replaceAllUsesWith(Metadata *MD) {
392 ReplaceableMetadataImpl::replaceAllUsesWith(MD);
393 }
394
395public:
396 static bool classof(const Metadata *MD) {
397 return MD->getMetadataID() == LocalAsMetadataKind ||
398 MD->getMetadataID() == ConstantAsMetadataKind;
399 }
400};
401
402class ConstantAsMetadata : public ValueAsMetadata {
403 friend class ValueAsMetadata;
404
405 ConstantAsMetadata(Constant *C)
406 : ValueAsMetadata(ConstantAsMetadataKind, C) {}
407
408public:
409 static ConstantAsMetadata *get(Constant *C) {
410 return ValueAsMetadata::getConstant(C);
411 }
412
413 static ConstantAsMetadata *getIfExists(Constant *C) {
414 return ValueAsMetadata::getConstantIfExists(C);
415 }
416
417 Constant *getValue() const {
418 return cast<Constant>(ValueAsMetadata::getValue());
419 }
420
421 static bool classof(const Metadata *MD) {
422 return MD->getMetadataID() == ConstantAsMetadataKind;
423 }
424};
425
426class LocalAsMetadata : public ValueAsMetadata {
427 friend class ValueAsMetadata;
428
429 LocalAsMetadata(Value *Local)
430 : ValueAsMetadata(LocalAsMetadataKind, Local) {
431 assert(!isa<Constant>(Local) && "Expected local value")((!isa<Constant>(Local) && "Expected local value"
) ? static_cast<void> (0) : __assert_fail ("!isa<Constant>(Local) && \"Expected local value\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/IR/Metadata.h"
, 431, __PRETTY_FUNCTION__));
432 }
433
434public:
435 static LocalAsMetadata *get(Value *Local) {
436 return ValueAsMetadata::getLocal(Local);
437 }
438
439 static LocalAsMetadata *getIfExists(Value *Local) {
440 return ValueAsMetadata::getLocalIfExists(Local);
441 }
442
443 static bool classof(const Metadata *MD) {
444 return MD->getMetadataID() == LocalAsMetadataKind;
445 }
446};
447
448/// Transitional API for extracting constants from Metadata.
449///
450/// This namespace contains transitional functions for metadata that points to
451/// \a Constants.
452///
453/// In prehistory -- when metadata was a subclass of \a Value -- \a MDNode
454/// operands could refer to any \a Value. There's was a lot of code like this:
455///
456/// \code
457/// MDNode *N = ...;
458/// auto *CI = dyn_cast<ConstantInt>(N->getOperand(2));
459/// \endcode
460///
461/// Now that \a Value and \a Metadata are in separate hierarchies, maintaining
462/// the semantics for \a isa(), \a cast(), \a dyn_cast() (etc.) requires three
463/// steps: cast in the \a Metadata hierarchy, extraction of the \a Value, and
464/// cast in the \a Value hierarchy. Besides creating boiler-plate, this
465/// requires subtle control flow changes.
466///
467/// The end-goal is to create a new type of metadata, called (e.g.) \a MDInt,
468/// so that metadata can refer to numbers without traversing a bridge to the \a
469/// Value hierarchy. In this final state, the code above would look like this:
470///
471/// \code
472/// MDNode *N = ...;
473/// auto *MI = dyn_cast<MDInt>(N->getOperand(2));
474/// \endcode
475///
476/// The API in this namespace supports the transition. \a MDInt doesn't exist
477/// yet, and even once it does, changing each metadata schema to use it is its
478/// own mini-project. In the meantime this API prevents us from introducing
479/// complex and bug-prone control flow that will disappear in the end. In
480/// particular, the above code looks like this:
481///
482/// \code
483/// MDNode *N = ...;
484/// auto *CI = mdconst::dyn_extract<ConstantInt>(N->getOperand(2));
485/// \endcode
486///
487/// The full set of provided functions includes:
488///
489/// mdconst::hasa <=> isa
490/// mdconst::extract <=> cast
491/// mdconst::extract_or_null <=> cast_or_null
492/// mdconst::dyn_extract <=> dyn_cast
493/// mdconst::dyn_extract_or_null <=> dyn_cast_or_null
494///
495/// The target of the cast must be a subclass of \a Constant.
496namespace mdconst {
497
498namespace detail {
499
500template <class T> T &make();
501template <class T, class Result> struct HasDereference {
502 using Yes = char[1];
503 using No = char[2];
504 template <size_t N> struct SFINAE {};
505
506 template <class U, class V>
507 static Yes &hasDereference(SFINAE<sizeof(static_cast<V>(*make<U>()))> * = 0);
508 template <class U, class V> static No &hasDereference(...);
509
510 static const bool value =
511 sizeof(hasDereference<T, Result>(nullptr)) == sizeof(Yes);
512};
513template <class V, class M> struct IsValidPointer {
514 static const bool value = std::is_base_of<Constant, V>::value &&
515 HasDereference<M, const Metadata &>::value;
516};
517template <class V, class M> struct IsValidReference {
518 static const bool value = std::is_base_of<Constant, V>::value &&
519 std::is_convertible<M, const Metadata &>::value;
520};
521
522} // end namespace detail
523
524/// Check whether Metadata has a Value.
525///
526/// As an analogue to \a isa(), check whether \c MD has an \a Value inside of
527/// type \c X.
528template <class X, class Y>
529inline typename std::enable_if<detail::IsValidPointer<X, Y>::value, bool>::type
530hasa(Y &&MD) {
531 assert(MD && "Null pointer sent into hasa")((MD && "Null pointer sent into hasa") ? static_cast<
void> (0) : __assert_fail ("MD && \"Null pointer sent into hasa\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/IR/Metadata.h"
, 531, __PRETTY_FUNCTION__));
532 if (auto *V = dyn_cast<ConstantAsMetadata>(MD))
533 return isa<X>(V->getValue());
534 return false;
535}
536template <class X, class Y>
537inline
538 typename std::enable_if<detail::IsValidReference<X, Y &>::value, bool>::type
539 hasa(Y &MD) {
540 return hasa(&MD);
541}
542
543/// Extract a Value from Metadata.
544///
545/// As an analogue to \a cast(), extract the \a Value subclass \c X from \c MD.
546template <class X, class Y>
547inline typename std::enable_if<detail::IsValidPointer<X, Y>::value, X *>::type
548extract(Y &&MD) {
549 return cast<X>(cast<ConstantAsMetadata>(MD)->getValue());
550}
551template <class X, class Y>
552inline
553 typename std::enable_if<detail::IsValidReference<X, Y &>::value, X *>::type
554 extract(Y &MD) {
555 return extract(&MD);
556}
557
558/// Extract a Value from Metadata, allowing null.
559///
560/// As an analogue to \a cast_or_null(), extract the \a Value subclass \c X
561/// from \c MD, allowing \c MD to be null.
562template <class X, class Y>
563inline typename std::enable_if<detail::IsValidPointer<X, Y>::value, X *>::type
564extract_or_null(Y &&MD) {
565 if (auto *V = cast_or_null<ConstantAsMetadata>(MD))
566 return cast<X>(V->getValue());
567 return nullptr;
568}
569
570/// Extract a Value from Metadata, if any.
571///
572/// As an analogue to \a dyn_cast_or_null(), extract the \a Value subclass \c X
573/// from \c MD, return null if \c MD doesn't contain a \a Value or if the \a
574/// Value it does contain is of the wrong subclass.
575template <class X, class Y>
576inline typename std::enable_if<detail::IsValidPointer<X, Y>::value, X *>::type
577dyn_extract(Y &&MD) {
578 if (auto *V = dyn_cast<ConstantAsMetadata>(MD))
579 return dyn_cast<X>(V->getValue());
580 return nullptr;
581}
582
583/// Extract a Value from Metadata, if any, allowing null.
584///
585/// As an analogue to \a dyn_cast_or_null(), extract the \a Value subclass \c X
586/// from \c MD, return null if \c MD doesn't contain a \a Value or if the \a
587/// Value it does contain is of the wrong subclass, allowing \c MD to be null.
588template <class X, class Y>
589inline typename std::enable_if<detail::IsValidPointer<X, Y>::value, X *>::type
590dyn_extract_or_null(Y &&MD) {
591 if (auto *V = dyn_cast_or_null<ConstantAsMetadata>(MD))
592 return dyn_cast<X>(V->getValue());
593 return nullptr;
594}
595
596} // end namespace mdconst
597
598//===----------------------------------------------------------------------===//
599/// A single uniqued string.
600///
601/// These are used to efficiently contain a byte sequence for metadata.
602/// MDString is always unnamed.
603class MDString : public Metadata {
604 friend class StringMapEntry<MDString>;
605
606 StringMapEntry<MDString> *Entry = nullptr;
607
608 MDString() : Metadata(MDStringKind, Uniqued) {}
609
610public:
611 MDString(const MDString &) = delete;
612 MDString &operator=(MDString &&) = delete;
613 MDString &operator=(const MDString &) = delete;
614
615 static MDString *get(LLVMContext &Context, StringRef Str);
616 static MDString *get(LLVMContext &Context, const char *Str) {
617 return get(Context, Str ? StringRef(Str) : StringRef());
618 }
619
620 StringRef getString() const;
621
622 unsigned getLength() const { return (unsigned)getString().size(); }
623
624 using iterator = StringRef::iterator;
625
626 /// Pointer to the first byte of the string.
627 iterator begin() const { return getString().begin(); }
628
629 /// Pointer to one byte past the end of the string.
630 iterator end() const { return getString().end(); }
631
632 const unsigned char *bytes_begin() const { return getString().bytes_begin(); }
633 const unsigned char *bytes_end() const { return getString().bytes_end(); }
634
635 /// Methods for support type inquiry through isa, cast, and dyn_cast.
636 static bool classof(const Metadata *MD) {
637 return MD->getMetadataID() == MDStringKind;
638 }
639};
640
641/// A collection of metadata nodes that might be associated with a
642/// memory access used by the alias-analysis infrastructure.
643struct AAMDNodes {
644 explicit AAMDNodes(MDNode *T = nullptr, MDNode *S = nullptr,
645 MDNode *N = nullptr)
646 : TBAA(T), Scope(S), NoAlias(N) {}
647
648 bool operator==(const AAMDNodes &A) const {
649 return TBAA == A.TBAA && Scope == A.Scope && NoAlias == A.NoAlias;
650 }
651
652 bool operator!=(const AAMDNodes &A) const { return !(*this == A); }
653
654 explicit operator bool() const { return TBAA || Scope || NoAlias; }
655
656 /// The tag for type-based alias analysis.
657 MDNode *TBAA;
658
659 /// The tag for alias scope specification (used with noalias).
660 MDNode *Scope;
661
662 /// The tag specifying the noalias scope.
663 MDNode *NoAlias;
664
665 /// Given two sets of AAMDNodes that apply to the same pointer,
666 /// give the best AAMDNodes that are compatible with both (i.e. a set of
667 /// nodes whose allowable aliasing conclusions are a subset of those
668 /// allowable by both of the inputs). However, for efficiency
669 /// reasons, do not create any new MDNodes.
670 AAMDNodes intersect(const AAMDNodes &Other) {
671 AAMDNodes Result;
672 Result.TBAA = Other.TBAA == TBAA ? TBAA : nullptr;
673 Result.Scope = Other.Scope == Scope ? Scope : nullptr;
674 Result.NoAlias = Other.NoAlias == NoAlias ? NoAlias : nullptr;
675 return Result;
676 }
677};
678
679// Specialize DenseMapInfo for AAMDNodes.
680template<>
681struct DenseMapInfo<AAMDNodes> {
682 static inline AAMDNodes getEmptyKey() {
683 return AAMDNodes(DenseMapInfo<MDNode *>::getEmptyKey(),
684 nullptr, nullptr);
685 }
686
687 static inline AAMDNodes getTombstoneKey() {
688 return AAMDNodes(DenseMapInfo<MDNode *>::getTombstoneKey(),
689 nullptr, nullptr);
690 }
691
692 static unsigned getHashValue(const AAMDNodes &Val) {
693 return DenseMapInfo<MDNode *>::getHashValue(Val.TBAA) ^
694 DenseMapInfo<MDNode *>::getHashValue(Val.Scope) ^
695 DenseMapInfo<MDNode *>::getHashValue(Val.NoAlias);
696 }
697
698 static bool isEqual(const AAMDNodes &LHS, const AAMDNodes &RHS) {
699 return LHS == RHS;
700 }
701};
702
703/// Tracking metadata reference owned by Metadata.
704///
705/// Similar to \a TrackingMDRef, but it's expected to be owned by an instance
706/// of \a Metadata, which has the option of registering itself for callbacks to
707/// re-unique itself.
708///
709/// In particular, this is used by \a MDNode.
710class MDOperand {
711 Metadata *MD = nullptr;
712
713public:
714 MDOperand() = default;
715 MDOperand(MDOperand &&) = delete;
716 MDOperand(const MDOperand &) = delete;
717 MDOperand &operator=(MDOperand &&) = delete;
718 MDOperand &operator=(const MDOperand &) = delete;
719 ~MDOperand() { untrack(); }
720
721 Metadata *get() const { return MD; }
722 operator Metadata *() const { return get(); }
723 Metadata *operator->() const { return get(); }
724 Metadata &operator*() const { return *get(); }
725
726 void reset() {
727 untrack();
728 MD = nullptr;
729 }
730 void reset(Metadata *MD, Metadata *Owner) {
731 untrack();
732 this->MD = MD;
733 track(Owner);
734 }
735
736private:
737 void track(Metadata *Owner) {
738 if (MD) {
739 if (Owner)
740 MetadataTracking::track(this, *MD, *Owner);
741 else
742 MetadataTracking::track(MD);
743 }
744 }
745
746 void untrack() {
747 assert(static_cast<void *>(this) == &MD && "Expected same address")((static_cast<void *>(this) == &MD && "Expected same address"
) ? static_cast<void> (0) : __assert_fail ("static_cast<void *>(this) == &MD && \"Expected same address\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/IR/Metadata.h"
, 747, __PRETTY_FUNCTION__));
748 if (MD)
749 MetadataTracking::untrack(MD);
750 }
751};
752
753template <> struct simplify_type<MDOperand> {
754 using SimpleType = Metadata *;
755
756 static SimpleType getSimplifiedValue(MDOperand &MD) { return MD.get(); }
757};
758
759template <> struct simplify_type<const MDOperand> {
760 using SimpleType = Metadata *;
761
762 static SimpleType getSimplifiedValue(const MDOperand &MD) { return MD.get(); }
763};
764
765/// Pointer to the context, with optional RAUW support.
766///
767/// Either a raw (non-null) pointer to the \a LLVMContext, or an owned pointer
768/// to \a ReplaceableMetadataImpl (which has a reference to \a LLVMContext).
769class ContextAndReplaceableUses {
770 PointerUnion<LLVMContext *, ReplaceableMetadataImpl *> Ptr;
771
772public:
773 ContextAndReplaceableUses(LLVMContext &Context) : Ptr(&Context) {}
774 ContextAndReplaceableUses(
775 std::unique_ptr<ReplaceableMetadataImpl> ReplaceableUses)
776 : Ptr(ReplaceableUses.release()) {
777 assert(getReplaceableUses() && "Expected non-null replaceable uses")((getReplaceableUses() && "Expected non-null replaceable uses"
) ? static_cast<void> (0) : __assert_fail ("getReplaceableUses() && \"Expected non-null replaceable uses\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/IR/Metadata.h"
, 777, __PRETTY_FUNCTION__));
778 }
779 ContextAndReplaceableUses() = delete;
780 ContextAndReplaceableUses(ContextAndReplaceableUses &&) = delete;
781 ContextAndReplaceableUses(const ContextAndReplaceableUses &) = delete;
782 ContextAndReplaceableUses &operator=(ContextAndReplaceableUses &&) = delete;
783 ContextAndReplaceableUses &
784 operator=(const ContextAndReplaceableUses &) = delete;
785 ~ContextAndReplaceableUses() { delete getReplaceableUses(); }
786
787 operator LLVMContext &() { return getContext(); }
788
789 /// Whether this contains RAUW support.
790 bool hasReplaceableUses() const {
791 return Ptr.is<ReplaceableMetadataImpl *>();
792 }
793
794 LLVMContext &getContext() const {
795 if (hasReplaceableUses())
796 return getReplaceableUses()->getContext();
797 return *Ptr.get<LLVMContext *>();
798 }
799
800 ReplaceableMetadataImpl *getReplaceableUses() const {
801 if (hasReplaceableUses())
802 return Ptr.get<ReplaceableMetadataImpl *>();
803 return nullptr;
804 }
805
806 /// Ensure that this has RAUW support, and then return it.
807 ReplaceableMetadataImpl *getOrCreateReplaceableUses() {
808 if (!hasReplaceableUses())
8
←
Taking true branch
→
809 makeReplaceable(llvm::make_unique<ReplaceableMetadataImpl>(getContext()));
9
←
Calling 'make_unique<llvm::ReplaceableMetadataImpl, llvm::LLVMContext &>'
→
11
←
Returned allocated memory
→
12
←
Calling 'ContextAndReplaceableUses::makeReplaceable'
→
810 return getReplaceableUses();
811 }
812
813 /// Assign RAUW support to this.
814 ///
815 /// Make this replaceable, taking ownership of \c ReplaceableUses (which must
816 /// not be null).
817 void
818 makeReplaceable(std::unique_ptr<ReplaceableMetadataImpl> ReplaceableUses) {
819 assert(ReplaceableUses && "Expected non-null replaceable uses")((ReplaceableUses && "Expected non-null replaceable uses"
) ? static_cast<void> (0) : __assert_fail ("ReplaceableUses && \"Expected non-null replaceable uses\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/IR/Metadata.h"
, 819, __PRETTY_FUNCTION__));
13
←
'?' condition is true
→
820 assert(&ReplaceableUses->getContext() == &getContext() &&((&ReplaceableUses->getContext() == &getContext() &&
"Expected same context") ? static_cast<void> (0) : __assert_fail
("&ReplaceableUses->getContext() == &getContext() && \"Expected same context\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/IR/Metadata.h"
, 821, __PRETTY_FUNCTION__))
14
←
Assuming the condition is true
→
15
←
'?' condition is true
→
821 "Expected same context")((&ReplaceableUses->getContext() == &getContext() &&
"Expected same context") ? static_cast<void> (0) : __assert_fail
("&ReplaceableUses->getContext() == &getContext() && \"Expected same context\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/IR/Metadata.h"
, 821, __PRETTY_FUNCTION__));
822 delete getReplaceableUses();
823 Ptr = ReplaceableUses.release();
824 }
16
←
Potential leak of memory pointed to by 'ReplaceableUses._M_t._M_head_impl'
825
826 /// Drop RAUW support.
827 ///
828 /// Cede ownership of RAUW support, returning it.
829 std::unique_ptr<ReplaceableMetadataImpl> takeReplaceableUses() {
830 assert(hasReplaceableUses() && "Expected to own replaceable uses")((hasReplaceableUses() && "Expected to own replaceable uses"
) ? static_cast<void> (0) : __assert_fail ("hasReplaceableUses() && \"Expected to own replaceable uses\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/IR/Metadata.h"
, 830, __PRETTY_FUNCTION__));
831 std::unique_ptr<ReplaceableMetadataImpl> ReplaceableUses(
832 getReplaceableUses());
833 Ptr = &ReplaceableUses->getContext();
834 return ReplaceableUses;
835 }
836};
837
838struct TempMDNodeDeleter {
839 inline void operator()(MDNode *Node) const;
840};
841
842#define HANDLE_MDNODE_LEAF(CLASS) \
843 using Temp##CLASS = std::unique_ptr<CLASS, TempMDNodeDeleter>;
844#define HANDLE_MDNODE_BRANCH(CLASS) HANDLE_MDNODE_LEAF(CLASS)
845#include "llvm/IR/Metadata.def"
846
847/// Metadata node.
848///
849/// Metadata nodes can be uniqued, like constants, or distinct. Temporary
850/// metadata nodes (with full support for RAUW) can be used to delay uniquing
851/// until forward references are known. The basic metadata node is an \a
852/// MDTuple.
853///
854/// There is limited support for RAUW at construction time. At construction
855/// time, if any operand is a temporary node (or an unresolved uniqued node,
856/// which indicates a transitive temporary operand), the node itself will be
857/// unresolved. As soon as all operands become resolved, it will drop RAUW
858/// support permanently.
859///
860/// If an unresolved node is part of a cycle, \a resolveCycles() needs
861/// to be called on some member of the cycle once all temporary nodes have been
862/// replaced.
863class MDNode : public Metadata {
864 friend class ReplaceableMetadataImpl;
865 friend class LLVMContextImpl;
866
867 unsigned NumOperands;
868 unsigned NumUnresolved;
869
870 ContextAndReplaceableUses Context;
871
872protected:
873 MDNode(LLVMContext &Context, unsigned ID, StorageType Storage,
874 ArrayRef<Metadata *> Ops1, ArrayRef<Metadata *> Ops2 = None);
875 ~MDNode() = default;
876
877 void *operator new(size_t Size, unsigned NumOps);
878 void operator delete(void *Mem);
879
880 /// Required by std, but never called.
881 void operator delete(void *, unsigned) {
882 llvm_unreachable("Constructor throws?")::llvm::llvm_unreachable_internal("Constructor throws?", "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/IR/Metadata.h"
, 882);
883 }
884
885 /// Required by std, but never called.
886 void operator delete(void *, unsigned, bool) {
887 llvm_unreachable("Constructor throws?")::llvm::llvm_unreachable_internal("Constructor throws?", "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/IR/Metadata.h"
, 887);
888 }
889
890 void dropAllReferences();
891
892 MDOperand *mutable_begin() { return mutable_end() - NumOperands; }
893 MDOperand *mutable_end() { return reinterpret_cast<MDOperand *>(this); }
894
895 using mutable_op_range = iterator_range<MDOperand *>;
896
897 mutable_op_range mutable_operands() {
898 return mutable_op_range(mutable_begin(), mutable_end());
899 }
900
901public:
902 MDNode(const MDNode &) = delete;
903 void operator=(const MDNode &) = delete;
904 void *operator new(size_t) = delete;
905
906 static inline MDTuple *get(LLVMContext &Context, ArrayRef<Metadata *> MDs);
907 static inline MDTuple *getIfExists(LLVMContext &Context,
908 ArrayRef<Metadata *> MDs);
909 static inline MDTuple *getDistinct(LLVMContext &Context,
910 ArrayRef<Metadata *> MDs);
911 static inline TempMDTuple getTemporary(LLVMContext &Context,
912 ArrayRef<Metadata *> MDs);
913
914 /// Create a (temporary) clone of this.
915 TempMDNode clone() const;
916
917 /// Deallocate a node created by getTemporary.
918 ///
919 /// Calls \c replaceAllUsesWith(nullptr) before deleting, so any remaining
920 /// references will be reset.
921 static void deleteTemporary(MDNode *N);
922
923 LLVMContext &getContext() const { return Context.getContext(); }
924
925 /// Replace a specific operand.
926 void replaceOperandWith(unsigned I, Metadata *New);
927
928 /// Check if node is fully resolved.
929 ///
930 /// If \a isTemporary(), this always returns \c false; if \a isDistinct(),
931 /// this always returns \c true.
932 ///
933 /// If \a isUniqued(), returns \c true if this has already dropped RAUW
934 /// support (because all operands are resolved).
935 ///
936 /// As forward declarations are resolved, their containers should get
937 /// resolved automatically. However, if this (or one of its operands) is
938 /// involved in a cycle, \a resolveCycles() needs to be called explicitly.
939 bool isResolved() const { return !isTemporary() && !NumUnresolved; }
940
941 bool isUniqued() const { return Storage == Uniqued; }
942 bool isDistinct() const { return Storage == Distinct; }
943 bool isTemporary() const { return Storage == Temporary; }
944
945 /// RAUW a temporary.
946 ///
947 /// \pre \a isTemporary() must be \c true.
948 void replaceAllUsesWith(Metadata *MD) {
949 assert(isTemporary() && "Expected temporary node")((isTemporary() && "Expected temporary node") ? static_cast
<void> (0) : __assert_fail ("isTemporary() && \"Expected temporary node\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/IR/Metadata.h"
, 949, __PRETTY_FUNCTION__));
950 if (Context.hasReplaceableUses())
951 Context.getReplaceableUses()->replaceAllUsesWith(MD);
952 }
953
954 /// Resolve cycles.
955 ///
956 /// Once all forward declarations have been resolved, force cycles to be
957 /// resolved.
958 ///
959 /// \pre No operands (or operands' operands, etc.) have \a isTemporary().
960 void resolveCycles();
961
962 /// Resolve a unique, unresolved node.
963 void resolve();
964
965 /// Replace a temporary node with a permanent one.
966 ///
967 /// Try to create a uniqued version of \c N -- in place, if possible -- and
968 /// return it. If \c N cannot be uniqued, return a distinct node instead.
969 template <class T>
970 static typename std::enable_if<std::is_base_of<MDNode, T>::value, T *>::type
971 replaceWithPermanent(std::unique_ptr<T, TempMDNodeDeleter> N) {
972 return cast<T>(N.release()->replaceWithPermanentImpl());
973 }
974
975 /// Replace a temporary node with a uniqued one.
976 ///
977 /// Create a uniqued version of \c N -- in place, if possible -- and return
978 /// it. Takes ownership of the temporary node.
979 ///
980 /// \pre N does not self-reference.
981 template <class T>
982 static typename std::enable_if<std::is_base_of<MDNode, T>::value, T *>::type
983 replaceWithUniqued(std::unique_ptr<T, TempMDNodeDeleter> N) {
984 return cast<T>(N.release()->replaceWithUniquedImpl());
985 }
986
987 /// Replace a temporary node with a distinct one.
988 ///
989 /// Create a distinct version of \c N -- in place, if possible -- and return
990 /// it. Takes ownership of the temporary node.
991 template <class T>
992 static typename std::enable_if<std::is_base_of<MDNode, T>::value, T *>::type
993 replaceWithDistinct(std::unique_ptr<T, TempMDNodeDeleter> N) {
994 return cast<T>(N.release()->replaceWithDistinctImpl());
995 }
996
997private:
998 MDNode *replaceWithPermanentImpl();
999 MDNode *replaceWithUniquedImpl();
1000 MDNode *replaceWithDistinctImpl();
1001
1002protected:
1003 /// Set an operand.
1004 ///
1005 /// Sets the operand directly, without worrying about uniquing.
1006 void setOperand(unsigned I, Metadata *New);
1007
1008 void storeDistinctInContext();
1009 template <class T, class StoreT>
1010 static T *storeImpl(T *N, StorageType Storage, StoreT &Store);
1011 template <class T> static T *storeImpl(T *N, StorageType Storage);
1012
1013private:
1014 void handleChangedOperand(void *Ref, Metadata *New);
1015
1016 /// Drop RAUW support, if any.
1017 void dropReplaceableUses();
1018
1019 void resolveAfterOperandChange(Metadata *Old, Metadata *New);
1020 void decrementUnresolvedOperandCount();
1021 void countUnresolvedOperands();
1022
1023 /// Mutate this to be "uniqued".
1024 ///
1025 /// Mutate this so that \a isUniqued().
1026 /// \pre \a isTemporary().
1027 /// \pre already added to uniquing set.
1028 void makeUniqued();
1029
1030 /// Mutate this to be "distinct".
1031 ///
1032 /// Mutate this so that \a isDistinct().
1033 /// \pre \a isTemporary().
1034 void makeDistinct();
1035
1036 void deleteAsSubclass();
1037 MDNode *uniquify();
1038 void eraseFromStore();
1039
1040 template <class NodeTy> struct HasCachedHash;
1041 template <class NodeTy>
1042 static void dispatchRecalculateHash(NodeTy *N, std::true_type) {
1043 N->recalculateHash();
1044 }
1045 template <class NodeTy>
1046 static void dispatchRecalculateHash(NodeTy *, std::false_type) {}
1047 template <class NodeTy>
1048 static void dispatchResetHash(NodeTy *N, std::true_type) {
1049 N->setHash(0);
1050 }
1051 template <class NodeTy>
1052 static void dispatchResetHash(NodeTy *, std::false_type) {}
1053
1054public:
1055 using op_iterator = const MDOperand *;
1056 using op_range = iterator_range<op_iterator>;
1057
1058 op_iterator op_begin() const {
1059 return const_cast<MDNode *>(this)->mutable_begin();
1060 }
1061
1062 op_iterator op_end() const {
1063 return const_cast<MDNode *>(this)->mutable_end();
1064 }
1065
1066 op_range operands() const { return op_range(op_begin(), op_end()); }
1067
1068 const MDOperand &getOperand(unsigned I) const {
1069 assert(I < NumOperands && "Out of range")((I < NumOperands && "Out of range") ? static_cast
<void> (0) : __assert_fail ("I < NumOperands && \"Out of range\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/IR/Metadata.h"
, 1069, __PRETTY_FUNCTION__));
1070 return op_begin()[I];
1071 }
1072
1073 /// Return number of MDNode operands.
1074 unsigned getNumOperands() const { return NumOperands; }
1075
1076 /// Methods for support type inquiry through isa, cast, and dyn_cast:
1077 static bool classof(const Metadata *MD) {
1078 switch (MD->getMetadataID()) {
1079 default:
1080 return false;
1081#define HANDLE_MDNODE_LEAF(CLASS) \
1082 case CLASS##Kind: \
1083 return true;
1084#include "llvm/IR/Metadata.def"
1085 }
1086 }
1087
1088 /// Check whether MDNode is a vtable access.
1089 bool isTBAAVtableAccess() const;
1090
1091 /// Methods for metadata merging.
1092 static MDNode *concatenate(MDNode *A, MDNode *B);
1093 static MDNode *intersect(MDNode *A, MDNode *B);
1094 static MDNode *getMostGenericTBAA(MDNode *A, MDNode *B);
1095 static MDNode *getMostGenericFPMath(MDNode *A, MDNode *B);
1096 static MDNode *getMostGenericRange(MDNode *A, MDNode *B);
1097 static MDNode *getMostGenericAliasScope(MDNode *A, MDNode *B);
1098 static MDNode *getMostGenericAlignmentOrDereferenceable(MDNode *A, MDNode *B);
1099};
1100
1101/// Tuple of metadata.
1102///
1103/// This is the simple \a MDNode arbitrary tuple. Nodes are uniqued by
1104/// default based on their operands.
1105class MDTuple : public MDNode {
1106 friend class LLVMContextImpl;
1107 friend class MDNode;
1108
1109 MDTuple(LLVMContext &C, StorageType Storage, unsigned Hash,
1110 ArrayRef<Metadata *> Vals)
1111 : MDNode(C, MDTupleKind, Storage, Vals) {
1112 setHash(Hash);
1113 }
1114
1115 ~MDTuple() { dropAllReferences(); }
1116
1117 void setHash(unsigned Hash) { SubclassData32 = Hash; }
1118 void recalculateHash();
1119
1120 static MDTuple *getImpl(LLVMContext &Context, ArrayRef<Metadata *> MDs,
1121 StorageType Storage, bool ShouldCreate = true);
1122
1123 TempMDTuple cloneImpl() const {
1124 return getTemporary(getContext(),
1125 SmallVector<Metadata *, 4>(op_begin(), op_end()));
1126 }
1127
1128public:
1129 /// Get the hash, if any.
1130 unsigned getHash() const { return SubclassData32; }
1131
1132 static MDTuple *get(LLVMContext &Context, ArrayRef<Metadata *> MDs) {
1133 return getImpl(Context, MDs, Uniqued);
1134 }
1135
1136 static MDTuple *getIfExists(LLVMContext &Context, ArrayRef<Metadata *> MDs) {
1137 return getImpl(Context, MDs, Uniqued, /* ShouldCreate */ false);
1138 }
1139
1140 /// Return a distinct node.
1141 ///
1142 /// Return a distinct node -- i.e., a node that is not uniqued.
1143 static MDTuple *getDistinct(LLVMContext &Context, ArrayRef<Metadata *> MDs) {
1144 return getImpl(Context, MDs, Distinct);
1145 }
1146
1147 /// Return a temporary node.
1148 ///
1149 /// For use in constructing cyclic MDNode structures. A temporary MDNode is
1150 /// not uniqued, may be RAUW'd, and must be manually deleted with
1151 /// deleteTemporary.
1152 static TempMDTuple getTemporary(LLVMContext &Context,
1153 ArrayRef<Metadata *> MDs) {
1154 return TempMDTuple(getImpl(Context, MDs, Temporary));
1155 }
1156
1157 /// Return a (temporary) clone of this.
1158 TempMDTuple clone() const { return cloneImpl(); }
1159
1160 static bool classof(const Metadata *MD) {
1161 return MD->getMetadataID() == MDTupleKind;
1162 }
1163};
1164
1165MDTuple *MDNode::get(LLVMContext &Context, ArrayRef<Metadata *> MDs) {
1166 return MDTuple::get(Context, MDs);
1167}
1168
1169MDTuple *MDNode::getIfExists(LLVMContext &Context, ArrayRef<Metadata *> MDs) {
1170 return MDTuple::getIfExists(Context, MDs);
1171}
1172
1173MDTuple *MDNode::getDistinct(LLVMContext &Context, ArrayRef<Metadata *> MDs) {
1174 return MDTuple::getDistinct(Context, MDs);
1175}
1176
1177TempMDTuple MDNode::getTemporary(LLVMContext &Context,
1178 ArrayRef<Metadata *> MDs) {
1179 return MDTuple::getTemporary(Context, MDs);
1180}
1181
1182void TempMDNodeDeleter::operator()(MDNode *Node) const {
1183 MDNode::deleteTemporary(Node);
1184}
1185
1186/// Typed iterator through MDNode operands.
1187///
1188/// An iterator that transforms an \a MDNode::iterator into an iterator over a
1189/// particular Metadata subclass.
1190template <class T>
1191class TypedMDOperandIterator
1192 : public std::iterator<std::input_iterator_tag, T *, std::ptrdiff_t, void,
1193 T *> {
1194 MDNode::op_iterator I = nullptr;
1195
1196public:
1197 TypedMDOperandIterator() = default;
1198 explicit TypedMDOperandIterator(MDNode::op_iterator I) : I(I) {}
1199
1200 T *operator*() const { return cast_or_null<T>(*I); }
1201
1202 TypedMDOperandIterator &operator++() {
1203 ++I;
1204 return *this;
1205 }
1206
1207 TypedMDOperandIterator operator++(int) {
1208 TypedMDOperandIterator Temp(*this);
1209 ++I;
1210 return Temp;
1211 }
1212
1213 bool operator==(const TypedMDOperandIterator &X) const { return I == X.I; }
1214 bool operator!=(const TypedMDOperandIterator &X) const { return I != X.I; }
1215};
1216
1217/// Typed, array-like tuple of metadata.
1218///
1219/// This is a wrapper for \a MDTuple that makes it act like an array holding a
1220/// particular type of metadata.
1221template <class T> class MDTupleTypedArrayWrapper {
1222 const MDTuple *N = nullptr;
1223
1224public:
1225 MDTupleTypedArrayWrapper() = default;
1226 MDTupleTypedArrayWrapper(const MDTuple *N) : N(N) {}
1227
1228 template <class U>
1229 MDTupleTypedArrayWrapper(
1230 const MDTupleTypedArrayWrapper<U> &Other,
1231 typename std::enable_if<std::is_convertible<U *, T *>::value>::type * =
1232 nullptr)
1233 : N(Other.get()) {}
1234
1235 template <class U>
1236 explicit MDTupleTypedArrayWrapper(
1237 const MDTupleTypedArrayWrapper<U> &Other,
1238 typename std::enable_if<!std::is_convertible<U *, T *>::value>::type * =
1239 nullptr)
1240 : N(Other.get()) {}
1241
1242 explicit operator bool() const { return get(); }
1243 explicit operator MDTuple *() const { return get(); }
1244
1245 MDTuple *get() const { return const_cast<MDTuple *>(N); }
1246 MDTuple *operator->() const { return get(); }
1247 MDTuple &operator*() const { return *get(); }
1248
1249 // FIXME: Fix callers and remove condition on N.
1250 unsigned size() const { return N ? N->getNumOperands() : 0u; }
1251 bool empty() const { return N ? N->getNumOperands() == 0 : true; }
1252 T *operator[](unsigned I) const { return cast_or_null<T>(N->getOperand(I)); }
1253
1254 // FIXME: Fix callers and remove condition on N.
1255 using iterator = TypedMDOperandIterator<T>;
1256
1257 iterator begin() const { return N ? iterator(N->op_begin()) : iterator(); }
1258 iterator end() const { return N ? iterator(N->op_end()) : iterator(); }
1259};
1260
1261#define HANDLE_METADATA(CLASS) \
1262 using CLASS##Array = MDTupleTypedArrayWrapper<CLASS>;
1263#include "llvm/IR/Metadata.def"
1264
1265/// Placeholder metadata for operands of distinct MDNodes.
1266///
1267/// This is a lightweight placeholder for an operand of a distinct node. It's
1268/// purpose is to help track forward references when creating a distinct node.
1269/// This allows distinct nodes involved in a cycle to be constructed before
1270/// their operands without requiring a heavyweight temporary node with
1271/// full-blown RAUW support.
1272///
1273/// Each placeholder supports only a single MDNode user. Clients should pass
1274/// an ID, retrieved via \a getID(), to indicate the "real" operand that this
1275/// should be replaced with.
1276///
1277/// While it would be possible to implement move operators, they would be
1278/// fairly expensive. Leave them unimplemented to discourage their use
1279/// (clients can use std::deque, std::list, BumpPtrAllocator, etc.).
1280class DistinctMDOperandPlaceholder : public Metadata {
1281 friend class MetadataTracking;
1282
1283 Metadata **Use = nullptr;
1284
1285public:
1286 explicit DistinctMDOperandPlaceholder(unsigned ID)
1287 : Metadata(DistinctMDOperandPlaceholderKind, Distinct) {
1288 SubclassData32 = ID;
1289 }
1290
1291 DistinctMDOperandPlaceholder() = delete;
1292 DistinctMDOperandPlaceholder(DistinctMDOperandPlaceholder &&) = delete;
1293 DistinctMDOperandPlaceholder(const DistinctMDOperandPlaceholder &) = delete;
1294
1295 ~DistinctMDOperandPlaceholder() {
1296 if (Use)
1297 *Use = nullptr;
1298 }
1299
1300 unsigned getID() const { return SubclassData32; }
1301
1302 /// Replace the use of this with MD.
1303 void replaceUseWith(Metadata *MD) {
1304 if (!Use)
1305 return;
1306 *Use = MD;
1307
1308 if (*Use)
1309 MetadataTracking::track(*Use);
1310
1311 Metadata *T = cast<Metadata>(this);
1312 MetadataTracking::untrack(T);
1313 assert(!Use && "Use is still being tracked despite being untracked!")((!Use && "Use is still being tracked despite being untracked!"
) ? static_cast<void> (0) : __assert_fail ("!Use && \"Use is still being tracked despite being untracked!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/IR/Metadata.h"
, 1313, __PRETTY_FUNCTION__));
1314 }
1315};
1316
1317//===----------------------------------------------------------------------===//
1318/// A tuple of MDNodes.
1319///
1320/// Despite its name, a NamedMDNode isn't itself an MDNode.
1321///
1322/// NamedMDNodes are named module-level entities that contain lists of MDNodes.
1323///
1324/// It is illegal for a NamedMDNode to appear as an operand of an MDNode.
1325class NamedMDNode : public ilist_node<NamedMDNode> {
1326 friend class LLVMContextImpl;
1327 friend class Module;
1328
1329 std::string Name;
1330 Module *Parent = nullptr;
1331 void *Operands; // SmallVector<TrackingMDRef, 4>
1332
1333 void setParent(Module *M) { Parent = M; }
1334
1335 explicit NamedMDNode(const Twine &N);
1336
1337 template<class T1, class T2>
1338 class op_iterator_impl :
1339 public std::iterator<std::bidirectional_iterator_tag, T2> {
1340 friend class NamedMDNode;
1341
1342 const NamedMDNode *Node = nullptr;
1343 unsigned Idx = 0;
1344
1345 op_iterator_impl(const NamedMDNode *N, unsigned i) : Node(N), Idx(i) {}
1346
1347 public:
1348 op_iterator_impl() = default;
1349
1350 bool operator==(const op_iterator_impl &o) const { return Idx == o.Idx; }
1351 bool operator!=(const op_iterator_impl &o) const { return Idx != o.Idx; }
1352
1353 op_iterator_impl &operator++() {
1354 ++Idx;
1355 return *this;
1356 }
1357
1358 op_iterator_impl operator++(int) {
1359 op_iterator_impl tmp(*this);
1360 operator++();
1361 return tmp;
1362 }
1363
1364 op_iterator_impl &operator--() {
1365 --Idx;
1366 return *this;
1367 }
1368
1369 op_iterator_impl operator--(int) {
1370 op_iterator_impl tmp(*this);
1371 operator--();
1372 return tmp;
1373 }
1374
1375 T1 operator*() const { return Node->getOperand(Idx); }
1376 };
1377
1378public:
1379 NamedMDNode(const NamedMDNode &) = delete;
1380 ~NamedMDNode();
1381
1382 /// Drop all references and remove the node from parent module.
1383 void eraseFromParent();
1384
1385 /// Remove all uses and clear node vector.
1386 void dropAllReferences() { clearOperands(); }
1387 /// Drop all references to this node's operands.
1388 void clearOperands();
1389
1390 /// Get the module that holds this named metadata collection.
1391 inline Module *getParent() { return Parent; }
1392 inline const Module *getParent() const { return Parent; }
1393
1394 MDNode *getOperand(unsigned i) const;
1395 unsigned getNumOperands() const;
1396 void addOperand(MDNode *M);
1397 void setOperand(unsigned I, MDNode *New);
1398 StringRef getName() const;
1399 void print(raw_ostream &ROS, bool IsForDebug = false) const;
1400 void print(raw_ostream &ROS, ModuleSlotTracker &MST,
1401 bool IsForDebug = false) const;
1402 void dump() const;
1403
1404 // ---------------------------------------------------------------------------
1405 // Operand Iterator interface...
1406 //
1407 using op_iterator = op_iterator_impl<MDNode *, MDNode>;
1408
1409 op_iterator op_begin() { return op_iterator(this, 0); }
1410 op_iterator op_end() { return op_iterator(this, getNumOperands()); }
1411
1412 using const_op_iterator = op_iterator_impl<const MDNode *, MDNode>;
1413
1414 const_op_iterator op_begin() const { return const_op_iterator(this, 0); }
1415 const_op_iterator op_end() const { return const_op_iterator(this, getNumOperands()); }
1416
1417 inline iterator_range<op_iterator> operands() {
1418 return make_range(op_begin(), op_end());
1419 }
1420 inline iterator_range<const_op_iterator> operands() const {
1421 return make_range(op_begin(), op_end());
1422 }
1423};
1424
1425// Create wrappers for C Binding types (see CBindingWrapping.h).
1426DEFINE_ISA_CONVERSION_FUNCTIONS(NamedMDNode, LLVMNamedMDNodeRef)inline NamedMDNode *unwrap(LLVMNamedMDNodeRef P) { return reinterpret_cast
<NamedMDNode*>(P); } inline LLVMNamedMDNodeRef wrap(const
NamedMDNode *P) { return reinterpret_cast<LLVMNamedMDNodeRef
>(const_cast<NamedMDNode*>(P)); } template<typename
T> inline T *unwrap(LLVMNamedMDNodeRef P) { return cast<
T>(unwrap(P)); }
1427
1428} // end namespace llvm
1429
1430#endif // LLVM_IR_METADATA_H
←

/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/STLExtras.h

1//===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===//
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 contains some templates that are useful if you are working with the
10// STL at all.
11//
12// No library is required when using these functions.
13//
14//===----------------------------------------------------------------------===//
15
16#ifndef LLVM_ADT_STLEXTRAS_H
17#define LLVM_ADT_STLEXTRAS_H
18
19#include "llvm/ADT/Optional.h"
20#include "llvm/ADT/SmallVector.h"
21#include "llvm/ADT/iterator.h"
22#include "llvm/ADT/iterator_range.h"
23#include "llvm/Config/abi-breaking.h"
24#include "llvm/Support/ErrorHandling.h"
25#include <algorithm>
26#include <cassert>
27#include <cstddef>
28#include <cstdint>
29#include <cstdlib>
30#include <functional>
31#include <initializer_list>
32#include <iterator>
33#include <limits>
34#include <memory>
35#include <tuple>
36#include <type_traits>
37#include <utility>
38
39#ifdef EXPENSIVE_CHECKS
40#include <random> // for std::mt19937
41#endif
42
43namespace llvm {
44
45// Only used by compiler if both template types are the same. Useful when
46// using SFINAE to test for the existence of member functions.
47template <typename T, T> struct SameType;
48
49namespace detail {
50
51template <typename RangeT>
52using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
53
54template <typename RangeT>
55using ValueOfRange = typename std::remove_reference<decltype(
56 *std::begin(std::declval<RangeT &>()))>::type;
57
58} // end namespace detail
59
60//===----------------------------------------------------------------------===//
61// Extra additions to <type_traits>
62//===----------------------------------------------------------------------===//
63
64template <typename T>
65struct negation : std::integral_constant<bool, !bool(T::value)> {};
66
67template <typename...> struct conjunction : std::true_type {};
68template <typename B1> struct conjunction<B1> : B1 {};
69template <typename B1, typename... Bn>
70struct conjunction<B1, Bn...>
71 : std::conditional<bool(B1::value), conjunction<Bn...>, B1>::type {};
72
73template <typename T> struct make_const_ptr {
74 using type =
75 typename std::add_pointer<typename std::add_const<T>::type>::type;
76};
77
78template <typename T> struct make_const_ref {
79 using type = typename std::add_lvalue_reference<
80 typename std::add_const<T>::type>::type;
81};
82
83//===----------------------------------------------------------------------===//
84// Extra additions to <functional>
85//===----------------------------------------------------------------------===//
86
87template <class Ty> struct identity {
88 using argument_type = Ty;
89
90 Ty &operator()(Ty &self) const {
91 return self;
92 }
93 const Ty &operator()(const Ty &self) const {
94 return self;
95 }
96};
97
98template <class Ty> struct less_ptr {
99 bool operator()(const Ty* left, const Ty* right) const {
100 return *left < *right;
101 }
102};
103
104template <class Ty> struct greater_ptr {
105 bool operator()(const Ty* left, const Ty* right) const {
106 return *right < *left;
107 }
108};
109
110/// An efficient, type-erasing, non-owning reference to a callable. This is
111/// intended for use as the type of a function parameter that is not used
112/// after the function in question returns.
113///
114/// This class does not own the callable, so it is not in general safe to store
115/// a function_ref.
116template<typename Fn> class function_ref;
117
118template<typename Ret, typename ...Params>
119class function_ref<Ret(Params...)> {
120 Ret (*callback)(intptr_t callable, Params ...params) = nullptr;
121 intptr_t callable;
122
123 template<typename Callable>
124 static Ret callback_fn(intptr_t callable, Params ...params) {
125 return (*reinterpret_cast<Callable*>(callable))(
126 std::forward<Params>(params)...);
127 }
128
129public:
130 function_ref() = default;
131 function_ref(std::nullptr_t) {}
132
133 template <typename Callable>
134 function_ref(Callable &&callable,
135 typename std::enable_if<
136 !std::is_same<typename std::remove_reference<Callable>::type,
137 function_ref>::value>::type * = nullptr)
138 : callback(callback_fn<typename std::remove_reference<Callable>::type>),
139 callable(reinterpret_cast<intptr_t>(&callable)) {}
140
141 Ret operator()(Params ...params) const {
142 return callback(callable, std::forward<Params>(params)...);
143 }
144
145 operator bool() const { return callback; }
146};
147
148// deleter - Very very very simple method that is used to invoke operator
149// delete on something. It is used like this:
150//
151// for_each(V.begin(), B.end(), deleter<Interval>);
152template <class T>
153inline void deleter(T *Ptr) {
154 delete Ptr;
155}
156
157//===----------------------------------------------------------------------===//
158// Extra additions to <iterator>
159//===----------------------------------------------------------------------===//
160
161namespace adl_detail {
162
163using std::begin;
164
165template <typename ContainerTy>
166auto adl_begin(ContainerTy &&container)
167 -> decltype(begin(std::forward<ContainerTy>(container))) {
168 return begin(std::forward<ContainerTy>(container));
169}
170
171using std::end;
172
173template <typename ContainerTy>
174auto adl_end(ContainerTy &&container)
175 -> decltype(end(std::forward<ContainerTy>(container))) {
176 return end(std::forward<ContainerTy>(container));
177}
178
179using std::swap;
180
181template <typename T>
182void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
183 std::declval<T>()))) {
184 swap(std::forward<T>(lhs), std::forward<T>(rhs));
185}
186
187} // end namespace adl_detail
188
189template <typename ContainerTy>
190auto adl_begin(ContainerTy &&container)
191 -> decltype(adl_detail::adl_begin(std::forward<ContainerTy>(container))) {
192 return adl_detail::adl_begin(std::forward<ContainerTy>(container));
193}
194
195template <typename ContainerTy>
196auto adl_end(ContainerTy &&container)
197 -> decltype(adl_detail::adl_end(std::forward<ContainerTy>(container))) {
198 return adl_detail::adl_end(std::forward<ContainerTy>(container));
199}
200
201template <typename T>
202void adl_swap(T &&lhs, T &&rhs) noexcept(
203 noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {
204 adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));
205}
206
207/// Test whether \p RangeOrContainer is empty. Similar to C++17 std::empty.
208template <typename T>
209constexpr bool empty(const T &RangeOrContainer) {
210 return adl_begin(RangeOrContainer) == adl_end(RangeOrContainer);
211}
212
213// mapped_iterator - This is a simple iterator adapter that causes a function to
214// be applied whenever operator* is invoked on the iterator.
215
216template <typename ItTy, typename FuncTy,
217 typename FuncReturnTy =
218 decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
219class mapped_iterator
220 : public iterator_adaptor_base<
221 mapped_iterator<ItTy, FuncTy>, ItTy,
222 typename std::iterator_traits<ItTy>::iterator_category,
223 typename std::remove_reference<FuncReturnTy>::type> {
224public:
225 mapped_iterator(ItTy U, FuncTy F)
226 : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {}
227
228 ItTy getCurrent() { return this->I; }
229
230 FuncReturnTy operator*() { return F(*this->I); }
231
232private:
233 FuncTy F;
234};
235
236// map_iterator - Provide a convenient way to create mapped_iterators, just like
237// make_pair is useful for creating pairs...
238template <class ItTy, class FuncTy>
239inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) {
240 return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
241}
242
243/// Helper to determine if type T has a member called rbegin().
244template <typename Ty> class has_rbegin_impl {
245 using yes = char[1];
246 using no = char[2];
247
248 template <typename Inner>
249 static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);
250
251 template <typename>
252 static no& test(...);
253
254public:
255 static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
256};
257
258/// Metafunction to determine if T& or T has a member called rbegin().
259template <typename Ty>
260struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> {
261};
262
263// Returns an iterator_range over the given container which iterates in reverse.
264// Note that the container must have rbegin()/rend() methods for this to work.
265template <typename ContainerTy>
266auto reverse(ContainerTy &&C,
267 typename std::enable_if<has_rbegin<ContainerTy>::value>::type * =
268 nullptr) -> decltype(make_range(C.rbegin(), C.rend())) {
269 return make_range(C.rbegin(), C.rend());
270}
271
272// Returns a std::reverse_iterator wrapped around the given iterator.
273template <typename IteratorTy>
274std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
275 return std::reverse_iterator<IteratorTy>(It);
276}
277
278// Returns an iterator_range over the given container which iterates in reverse.
279// Note that the container must have begin()/end() methods which return
280// bidirectional iterators for this to work.
281template <typename ContainerTy>
282auto reverse(
283 ContainerTy &&C,
284 typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
285 -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
286 llvm::make_reverse_iterator(std::begin(C)))) {
287 return make_range(llvm::make_reverse_iterator(std::end(C)),
288 llvm::make_reverse_iterator(std::begin(C)));
289}
290
291/// An iterator adaptor that filters the elements of given inner iterators.
292///
293/// The predicate parameter should be a callable object that accepts the wrapped
294/// iterator's reference type and returns a bool. When incrementing or
295/// decrementing the iterator, it will call the predicate on each element and
296/// skip any where it returns false.
297///
298/// \code
299/// int A[] = { 1, 2, 3, 4 };
300/// auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
301/// // R contains { 1, 3 }.
302/// \endcode
303///
304/// Note: filter_iterator_base implements support for forward iteration.
305/// filter_iterator_impl exists to provide support for bidirectional iteration,
306/// conditional on whether the wrapped iterator supports it.
307template <typename WrappedIteratorT, typename PredicateT, typename IterTag>
308class filter_iterator_base
309 : public iterator_adaptor_base<
310 filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
311 WrappedIteratorT,
312 typename std::common_type<
313 IterTag, typename std::iterator_traits<
314 WrappedIteratorT>::iterator_category>::type> {
315 using BaseT = iterator_adaptor_base<
316 filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
317 WrappedIteratorT,
318 typename std::common_type<
319 IterTag, typename std::iterator_traits<
320 WrappedIteratorT>::iterator_category>::type>;
321
322protected:
323 WrappedIteratorT End;
324 PredicateT Pred;
325
326 void findNextValid() {
327 while (this->I != End && !Pred(*this->I))
328 BaseT::operator++();
329 }
330
331 // Construct the iterator. The begin iterator needs to know where the end
332 // is, so that it can properly stop when it gets there. The end iterator only
333 // needs the predicate to support bidirectional iteration.
334 filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End,
335 PredicateT Pred)
336 : BaseT(Begin), End(End), Pred(Pred) {
337 findNextValid();
338 }
339
340public:
341 using BaseT::operator++;
342
343 filter_iterator_base &operator++() {
344 BaseT::operator++();
345 findNextValid();
346 return *this;
347 }
348};
349
350/// Specialization of filter_iterator_base for forward iteration only.
351template <typename WrappedIteratorT, typename PredicateT,
352 typename IterTag = std::forward_iterator_tag>
353class filter_iterator_impl
354 : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> {
355 using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>;
356
357public:
358 filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
359 PredicateT Pred)
360 : BaseT(Begin, End, Pred) {}
361};
362
363/// Specialization of filter_iterator_base for bidirectional iteration.
364template <typename WrappedIteratorT, typename PredicateT>
365class filter_iterator_impl<WrappedIteratorT, PredicateT,
366 std::bidirectional_iterator_tag>
367 : public filter_iterator_base<WrappedIteratorT, PredicateT,
368 std::bidirectional_iterator_tag> {
369 using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT,
370 std::bidirectional_iterator_tag>;
371 void findPrevValid() {
372 while (!this->Pred(*this->I))
373 BaseT::operator--();
374 }
375
376public:
377 using BaseT::operator--;
378
379 filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
380 PredicateT Pred)
381 : BaseT(Begin, End, Pred) {}
382
383 filter_iterator_impl &operator--() {
384 BaseT::operator--();
385 findPrevValid();
386 return *this;
387 }
388};
389
390namespace detail {
391
392template <bool is_bidirectional> struct fwd_or_bidi_tag_impl {
393 using type = std::forward_iterator_tag;
394};
395
396template <> struct fwd_or_bidi_tag_impl<true> {
397 using type = std::bidirectional_iterator_tag;
398};
399
400/// Helper which sets its type member to forward_iterator_tag if the category
401/// of \p IterT does not derive from bidirectional_iterator_tag, and to
402/// bidirectional_iterator_tag otherwise.
403template <typename IterT> struct fwd_or_bidi_tag {
404 using type = typename fwd_or_bidi_tag_impl<std::is_base_of<
405 std::bidirectional_iterator_tag,
406 typename std::iterator_traits<IterT>::iterator_category>::value>::type;
407};
408
409} // namespace detail
410
411/// Defines filter_iterator to a suitable specialization of
412/// filter_iterator_impl, based on the underlying iterator's category.
413template <typename WrappedIteratorT, typename PredicateT>
414using filter_iterator = filter_iterator_impl<
415 WrappedIteratorT, PredicateT,
416 typename detail::fwd_or_bidi_tag<WrappedIteratorT>::type>;
417
418/// Convenience function that takes a range of elements and a predicate,
419/// and return a new filter_iterator range.
420///
421/// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the
422/// lifetime of that temporary is not kept by the returned range object, and the
423/// temporary is going to be dropped on the floor after the make_iterator_range
424/// full expression that contains this function call.
425template <typename RangeT, typename PredicateT>
426iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>>
427make_filter_range(RangeT &&Range, PredicateT Pred) {
428 using FilterIteratorT =
429 filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
430 return make_range(
431 FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
432 std::end(std::forward<RangeT>(Range)), Pred),
433 FilterIteratorT(std::end(std::forward<RangeT>(Range)),
434 std::end(std::forward<RangeT>(Range)), Pred));
435}
436
437/// A pseudo-iterator adaptor that is designed to implement "early increment"
438/// style loops.
439///
440/// This is *not a normal iterator* and should almost never be used directly. It
441/// is intended primarily to be used with range based for loops and some range
442/// algorithms.
443///
444/// The iterator isn't quite an `OutputIterator` or an `InputIterator` but
445/// somewhere between them. The constraints of these iterators are:
446///
447/// - On construction or after being incremented, it is comparable and
448/// dereferencable. It is *not* incrementable.
449/// - After being dereferenced, it is neither comparable nor dereferencable, it
450/// is only incrementable.
451///
452/// This means you can only dereference the iterator once, and you can only
453/// increment it once between dereferences.
454template <typename WrappedIteratorT>
455class early_inc_iterator_impl
456 : public iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
457 WrappedIteratorT, std::input_iterator_tag> {
458 using BaseT =
459 iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
460 WrappedIteratorT, std::input_iterator_tag>;
461
462 using PointerT = typename std::iterator_traits<WrappedIteratorT>::pointer;
463
464protected:
465#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
466 bool IsEarlyIncremented = false;
467#endif
468
469public:
470 early_inc_iterator_impl(WrappedIteratorT I) : BaseT(I) {}
471
472 using BaseT::operator*;
473 typename BaseT::reference operator*() {
474#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
475 assert(!IsEarlyIncremented && "Cannot dereference twice!")((!IsEarlyIncremented && "Cannot dereference twice!")
? static_cast<void> (0) : __assert_fail ("!IsEarlyIncremented && \"Cannot dereference twice!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/STLExtras.h"
, 475, __PRETTY_FUNCTION__));
476 IsEarlyIncremented = true;
477#endif
478 return *(this->I)++;
479 }
480
481 using BaseT::operator++;
482 early_inc_iterator_impl &operator++() {
483#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
484 assert(IsEarlyIncremented && "Cannot increment before dereferencing!")((IsEarlyIncremented && "Cannot increment before dereferencing!"
) ? static_cast<void> (0) : __assert_fail ("IsEarlyIncremented && \"Cannot increment before dereferencing!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/STLExtras.h"
, 484, __PRETTY_FUNCTION__));
485 IsEarlyIncremented = false;
486#endif
487 return *this;
488 }
489
490 using BaseT::operator==;
491 bool operator==(const early_inc_iterator_impl &RHS) const {
492#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
493 assert(!IsEarlyIncremented && "Cannot compare after dereferencing!")((!IsEarlyIncremented && "Cannot compare after dereferencing!"
) ? static_cast<void> (0) : __assert_fail ("!IsEarlyIncremented && \"Cannot compare after dereferencing!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/STLExtras.h"
, 493, __PRETTY_FUNCTION__));
494#endif
495 return BaseT::operator==(RHS);
496 }
497};
498
499/// Make a range that does early increment to allow mutation of the underlying
500/// range without disrupting iteration.
501///
502/// The underlying iterator will be incremented immediately after it is
503/// dereferenced, allowing deletion of the current node or insertion of nodes to
504/// not disrupt iteration provided they do not invalidate the *next* iterator --
505/// the current iterator can be invalidated.
506///
507/// This requires a very exact pattern of use that is only really suitable to
508/// range based for loops and other range algorithms that explicitly guarantee
509/// to dereference exactly once each element, and to increment exactly once each
510/// element.
511template <typename RangeT>
512iterator_range<early_inc_iterator_impl<detail::IterOfRange<RangeT>>>
513make_early_inc_range(RangeT &&Range) {
514 using EarlyIncIteratorT =
515 early_inc_iterator_impl<detail::IterOfRange<RangeT>>;
516 return make_range(EarlyIncIteratorT(std::begin(std::forward<RangeT>(Range))),
517 EarlyIncIteratorT(std::end(std::forward<RangeT>(Range))));
518}
519
520// forward declarations required by zip_shortest/zip_first/zip_longest
521template <typename R, typename UnaryPredicate>
522bool all_of(R &&range, UnaryPredicate P);
523template <typename R, typename UnaryPredicate>
524bool any_of(R &&range, UnaryPredicate P);
525
526template <size_t... I> struct index_sequence;
527
528template <class... Ts> struct index_sequence_for;
529
530namespace detail {
531
532using std::declval;
533
534// We have to alias this since inlining the actual type at the usage site
535// in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.
536template<typename... Iters> struct ZipTupleType {
537 using type = std::tuple<decltype(*declval<Iters>())...>;
538};
539
540template <typename ZipType, typename... Iters>
541using zip_traits = iterator_facade_base<
542 ZipType, typename std::common_type<std::bidirectional_iterator_tag,
543 typename std::iterator_traits<
544 Iters>::iterator_category...>::type,
545 // ^ TODO: Implement random access methods.
546 typename ZipTupleType<Iters...>::type,
547 typename std::iterator_traits<typename std::tuple_element<
548 0, std::tuple<Iters...>>::type>::difference_type,
549 // ^ FIXME: This follows boost::make_zip_iterator's assumption that all
550 // inner iterators have the same difference_type. It would fail if, for
551 // instance, the second field's difference_type were non-numeric while the
552 // first is.
553 typename ZipTupleType<Iters...>::type *,
554 typename ZipTupleType<Iters...>::type>;
555
556template <typename ZipType, typename... Iters>
557struct zip_common : public zip_traits<ZipType, Iters...> {
558 using Base = zip_traits<ZipType, Iters...>;
559 using value_type = typename Base::value_type;
560
561 std::tuple<Iters...> iterators;
562
563protected:
564 template <size_t... Ns> value_type deref(index_sequence<Ns...>) const {
565 return value_type(*std::get<Ns>(iterators)...);
566 }
567
568 template <size_t... Ns>
569 decltype(iterators) tup_inc(index_sequence<Ns...>) const {
570 return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
571 }
572
573 template <size_t... Ns>
574 decltype(iterators) tup_dec(index_sequence<Ns...>) const {
575 return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
576 }
577
578public:
579 zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
580
581 value_type operator*() { return deref(index_sequence_for<Iters...>{}); }
582
583 const value_type operator*() const {
584 return deref(index_sequence_for<Iters...>{});
585 }
586
587 ZipType &operator++() {
588 iterators = tup_inc(index_sequence_for<Iters...>{});
589 return *reinterpret_cast<ZipType *>(this);
590 }
591
592 ZipType &operator--() {
593 static_assert(Base::IsBidirectional,
594 "All inner iterators must be at least bidirectional.");
595 iterators = tup_dec(index_sequence_for<Iters...>{});
596 return *reinterpret_cast<ZipType *>(this);
597 }
598};
599
600template <typename... Iters>
601struct zip_first : public zip_common<zip_first<Iters...>, Iters...> {
602 using Base = zip_common<zip_first<Iters...>, Iters...>;
603
604 bool operator==(const zip_first<Iters...> &other) const {
605 return std::get<0>(this->iterators) == std::get<0>(other.iterators);
606 }
607
608 zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
609};
610
611template <typename... Iters>
612class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> {
613 template <size_t... Ns>
614 bool test(const zip_shortest<Iters...> &other, index_sequence<Ns...>) const {
615 return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
616 std::get<Ns>(other.iterators)...},
617 identity<bool>{});
618 }
619
620public:
621 using Base = zip_common<zip_shortest<Iters...>, Iters...>;
622
623 zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
624
625 bool operator==(const zip_shortest<Iters...> &other) const {
626 return !test(other, index_sequence_for<Iters...>{});
627 }
628};
629
630template <template <typename...> class ItType, typename... Args> class zippy {
631public:
632 using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>;
633 using iterator_category = typename iterator::iterator_category;
634 using value_type = typename iterator::value_type;
635 using difference_type = typename iterator::difference_type;
636 using pointer = typename iterator::pointer;
637 using reference = typename iterator::reference;
638
639private:
640 std::tuple<Args...> ts;
641
642 template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const {
643 return iterator(std::begin(std::get<Ns>(ts))...);
644 }
645 template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const {
646 return iterator(std::end(std::get<Ns>(ts))...);
647 }
648
649public:
650 zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
651
652 iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); }
653 iterator end() const { return end_impl(index_sequence_for<Args...>{}); }
654};
655
656} // end namespace detail
657
658/// zip iterator for two or more iteratable types.
659template <typename T, typename U, typename... Args>
660detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u,
661 Args &&... args) {
662 return detail::zippy<detail::zip_shortest, T, U, Args...>(
663 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
664}
665
666/// zip iterator that, for the sake of efficiency, assumes the first iteratee to
667/// be the shortest.
668template <typename T, typename U, typename... Args>
669detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u,
670 Args &&... args) {
671 return detail::zippy<detail::zip_first, T, U, Args...>(
672 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
673}
674
675namespace detail {
676template <typename Iter>
677static Iter next_or_end(const Iter &I, const Iter &End) {
678 if (I == End)
679 return End;
680 return std::next(I);
681}
682
683template <typename Iter>
684static auto deref_or_none(const Iter &I, const Iter &End)
685 -> llvm::Optional<typename std::remove_const<
686 typename std::remove_reference<decltype(*I)>::type>::type> {
687 if (I == End)
688 return None;
689 return *I;
690}
691
692template <typename Iter> struct ZipLongestItemType {
693 using type =
694 llvm::Optional<typename std::remove_const<typename std::remove_reference<
695 decltype(*std::declval<Iter>())>::type>::type>;
696};
697
698template <typename... Iters> struct ZipLongestTupleType {
699 using type = std::tuple<typename ZipLongestItemType<Iters>::type...>;
700};
701
702template <typename... Iters>
703class zip_longest_iterator
704 : public iterator_facade_base<
705 zip_longest_iterator<Iters...>,
706 typename std::common_type<
707 std::forward_iterator_tag,
708 typename std::iterator_traits<Iters>::iterator_category...>::type,
709 typename ZipLongestTupleType<Iters...>::type,
710 typename std::iterator_traits<typename std::tuple_element<
711 0, std::tuple<Iters...>>::type>::difference_type,
712 typename ZipLongestTupleType<Iters...>::type *,
713 typename ZipLongestTupleType<Iters...>::type> {
714public:
715 using value_type = typename ZipLongestTupleType<Iters...>::type;
716
717private:
718 std::tuple<Iters...> iterators;
719 std::tuple<Iters...> end_iterators;
720
721 template <size_t... Ns>
722 bool test(const zip_longest_iterator<Iters...> &other,
723 index_sequence<Ns...>) const {
724 return llvm::any_of(
725 std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
726 std::get<Ns>(other.iterators)...},
727 identity<bool>{});
728 }
729
730 template <size_t... Ns> value_type deref(index_sequence<Ns...>) const {
731 return value_type(
732 deref_or_none(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
733 }
734
735 template <size_t... Ns>
736 decltype(iterators) tup_inc(index_sequence<Ns...>) const {
737 return std::tuple<Iters...>(
738 next_or_end(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
739 }
740
741public:
742 zip_longest_iterator(std::pair<Iters &&, Iters &&>... ts)
743 : iterators(std::forward<Iters>(ts.first)...),
744 end_iterators(std::forward<Iters>(ts.second)...) {}
745
746 value_type operator*() { return deref(index_sequence_for<Iters...>{}); }
747
748 value_type operator*() const { return deref(index_sequence_for<Iters...>{}); }
749
750 zip_longest_iterator<Iters...> &operator++() {
751 iterators = tup_inc(index_sequence_for<Iters...>{});
752 return *this;
753 }
754
755 bool operator==(const zip_longest_iterator<Iters...> &other) const {
756 return !test(other, index_sequence_for<Iters...>{});
757 }
758};
759
760template <typename... Args> class zip_longest_range {
761public:
762 using iterator =
763 zip_longest_iterator<decltype(adl_begin(std::declval<Args>()))...>;
764 using iterator_category = typename iterator::iterator_category;
765 using value_type = typename iterator::value_type;
766 using difference_type = typename iterator::difference_type;
767 using pointer = typename iterator::pointer;
768 using reference = typename iterator::reference;
769
770private:
771 std::tuple<Args...> ts;
772
773 template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const {
774 return iterator(std::make_pair(adl_begin(std::get<Ns>(ts)),
775 adl_end(std::get<Ns>(ts)))...);
776 }
777
778 template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const {
779 return iterator(std::make_pair(adl_end(std::get<Ns>(ts)),
780 adl_end(std::get<Ns>(ts)))...);
781 }
782
783public:
784 zip_longest_range(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
785
786 iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); }
787 iterator end() const { return end_impl(index_sequence_for<Args...>{}); }
788};
789} // namespace detail
790
791/// Iterate over two or more iterators at the same time. Iteration continues
792/// until all iterators reach the end. The llvm::Optional only contains a value
793/// if the iterator has not reached the end.
794template <typename T, typename U, typename... Args>
795detail::zip_longest_range<T, U, Args...> zip_longest(T &&t, U &&u,
796 Args &&... args) {
797 return detail::zip_longest_range<T, U, Args...>(
798 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
799}
800
801/// Iterator wrapper that concatenates sequences together.
802///
803/// This can concatenate different iterators, even with different types, into
804/// a single iterator provided the value types of all the concatenated
805/// iterators expose `reference` and `pointer` types that can be converted to
806/// `ValueT &` and `ValueT *` respectively. It doesn't support more
807/// interesting/customized pointer or reference types.
808///
809/// Currently this only supports forward or higher iterator categories as
810/// inputs and always exposes a forward iterator interface.
811template <typename ValueT, typename... IterTs>
812class concat_iterator
813 : public iterator_facade_base<concat_iterator<ValueT, IterTs...>,
814 std::forward_iterator_tag, ValueT> {
815 using BaseT = typename concat_iterator::iterator_facade_base;
816
817 /// We store both the current and end iterators for each concatenated
818 /// sequence in a tuple of pairs.
819 ///
820 /// Note that something like iterator_range seems nice at first here, but the
821 /// range properties are of little benefit and end up getting in the way
822 /// because we need to do mutation on the current iterators.
823 std::tuple<IterTs...> Begins;
824 std::tuple<IterTs...> Ends;
825
826 /// Attempts to increment a specific iterator.
827 ///
828 /// Returns true if it was able to increment the iterator. Returns false if
829 /// the iterator is already at the end iterator.
830 template <size_t Index> bool incrementHelper() {
831 auto &Begin = std::get<Index>(Begins);
832 auto &End = std::get<Index>(Ends);
833 if (Begin == End)
834 return false;
835
836 ++Begin;
837 return true;
838 }
839
840 /// Increments the first non-end iterator.
841 ///
842 /// It is an error to call this with all iterators at the end.
843 template <size_t... Ns> void increment(index_sequence<Ns...>) {
844 // Build a sequence of functions to increment each iterator if possible.
845 bool (concat_iterator::*IncrementHelperFns[])() = {
846 &concat_iterator::incrementHelper<Ns>...};
847
848 // Loop over them, and stop as soon as we succeed at incrementing one.
849 for (auto &IncrementHelperFn : IncrementHelperFns)
850 if ((this->*IncrementHelperFn)())
851 return;
852
853 llvm_unreachable("Attempted to increment an end concat iterator!")::llvm::llvm_unreachable_internal("Attempted to increment an end concat iterator!"
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/STLExtras.h"
, 853);
854 }
855
856 /// Returns null if the specified iterator is at the end. Otherwise,
857 /// dereferences the iterator and returns the address of the resulting
858 /// reference.
859 template <size_t Index> ValueT *getHelper() const {
860 auto &Begin = std::get<Index>(Begins);
861 auto &End = std::get<Index>(Ends);
862 if (Begin == End)
863 return nullptr;
864
865 return &*Begin;
866 }
867
868 /// Finds the first non-end iterator, dereferences, and returns the resulting
869 /// reference.
870 ///
871 /// It is an error to call this with all iterators at the end.
872 template <size_t... Ns> ValueT &get(index_sequence<Ns...>) const {
873 // Build a sequence of functions to get from iterator if possible.
874 ValueT *(concat_iterator::*GetHelperFns[])() const = {
875 &concat_iterator::getHelper<Ns>...};
876
877 // Loop over them, and return the first result we find.
878 for (auto &GetHelperFn : GetHelperFns)
879 if (ValueT *P = (this->*GetHelperFn)())
880 return *P;
881
882 llvm_unreachable("Attempted to get a pointer from an end concat iterator!")::llvm::llvm_unreachable_internal("Attempted to get a pointer from an end concat iterator!"
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/STLExtras.h"
, 882);
883 }
884
885public:
886 /// Constructs an iterator from a squence of ranges.
887 ///
888 /// We need the full range to know how to switch between each of the
889 /// iterators.
890 template <typename... RangeTs>
891 explicit concat_iterator(RangeTs &&... Ranges)
892 : Begins(std::begin(Ranges)...), Ends(std::end(Ranges)...) {}
893
894 using BaseT::operator++;
895
896 concat_iterator &operator++() {
897 increment(index_sequence_for<IterTs...>());
898 return *this;
899 }
900
901 ValueT &operator*() const { return get(index_sequence_for<IterTs...>()); }
902
903 bool operator==(const concat_iterator &RHS) const {
904 return Begins == RHS.Begins && Ends == RHS.Ends;
905 }
906};
907
908namespace detail {
909
910/// Helper to store a sequence of ranges being concatenated and access them.
911///
912/// This is designed to facilitate providing actual storage when temporaries
913/// are passed into the constructor such that we can use it as part of range
914/// based for loops.
915template <typename ValueT, typename... RangeTs> class concat_range {
916public:
917 using iterator =
918 concat_iterator<ValueT,
919 decltype(std::begin(std::declval<RangeTs &>()))...>;
920
921private:
922 std::tuple<RangeTs...> Ranges;
923
924 template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) {
925 return iterator(std::get<Ns>(Ranges)...);
926 }
927 template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) {
928 return iterator(make_range(std::end(std::get<Ns>(Ranges)),
929 std::end(std::get<Ns>(Ranges)))...);
930 }
931
932public:
933 concat_range(RangeTs &&... Ranges)
934 : Ranges(std::forward<RangeTs>(Ranges)...) {}
935
936 iterator begin() { return begin_impl(index_sequence_for<RangeTs...>{}); }
937 iterator end() { return end_impl(index_sequence_for<RangeTs...>{}); }
938};
939
940} // end namespace detail
941
942/// Concatenated range across two or more ranges.
943///
944/// The desired value type must be explicitly specified.
945template <typename ValueT, typename... RangeTs>
946detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
947 static_assert(sizeof...(RangeTs) > 1,
948 "Need more than one range to concatenate!");
949 return detail::concat_range<ValueT, RangeTs...>(
950 std::forward<RangeTs>(Ranges)...);
951}
952
953//===----------------------------------------------------------------------===//
954// Extra additions to <utility>
955//===----------------------------------------------------------------------===//
956
957/// Function object to check whether the first component of a std::pair
958/// compares less than the first component of another std::pair.
959struct less_first {
960 template <typename T> bool operator()(const T &lhs, const T &rhs) const {
961 return lhs.first < rhs.first;
962 }
963};
964
965/// Function object to check whether the second component of a std::pair
966/// compares less than the second component of another std::pair.
967struct less_second {
968 template <typename T> bool operator()(const T &lhs, const T &rhs) const {
969 return lhs.second < rhs.second;
970 }
971};
972
973/// \brief Function object to apply a binary function to the first component of
974/// a std::pair.
975template<typename FuncTy>
976struct on_first {
977 FuncTy func;
978
979 template <typename T>
980 auto operator()(const T &lhs, const T &rhs) const
981 -> decltype(func(lhs.first, rhs.first)) {
982 return func(lhs.first, rhs.first);
983 }
984};
985
986// A subset of N3658. More stuff can be added as-needed.
987
988/// Represents a compile-time sequence of integers.
989template <class T, T... I> struct integer_sequence {
990 using value_type = T;
991
992 static constexpr size_t size() { return sizeof...(I); }
993};
994
995/// Alias for the common case of a sequence of size_ts.
996template <size_t... I>
997struct index_sequence : integer_sequence<std::size_t, I...> {};
998
999template <std::size_t N, std::size_t... I>
1000struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {};
1001template <std::size_t... I>
1002struct build_index_impl<0, I...> : index_sequence<I...> {};
1003
1004/// Creates a compile-time integer sequence for a parameter pack.
1005template <class... Ts>
1006struct index_sequence_for : build_index_impl<sizeof...(Ts)> {};
1007
1008/// Utility type to build an inheritance chain that makes it easy to rank
1009/// overload candidates.
1010template <int N> struct rank : rank<N - 1> {};
1011template <> struct rank<0> {};
1012
1013/// traits class for checking whether type T is one of any of the given
1014/// types in the variadic list.
1015template <typename T, typename... Ts> struct is_one_of {
1016 static const bool value = false;
1017};
1018
1019template <typename T, typename U, typename... Ts>
1020struct is_one_of<T, U, Ts...> {
1021 static const bool value =
1022 std::is_same<T, U>::value || is_one_of<T, Ts...>::value;
1023};
1024
1025/// traits class for checking whether type T is a base class for all
1026/// the given types in the variadic list.
1027template <typename T, typename... Ts> struct are_base_of {
1028 static const bool value = true;
1029};
1030
1031template <typename T, typename U, typename... Ts>
1032struct are_base_of<T, U, Ts...> {
1033 static const bool value =
1034 std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value;
1035};
1036
1037//===----------------------------------------------------------------------===//
1038// Extra additions for arrays
1039//===----------------------------------------------------------------------===//
1040
1041/// Find the length of an array.
1042template <class T, std::size_t N>
1043constexpr inline size_t array_lengthof(T (&)[N]) {
1044 return N;
1045}
1046
1047/// Adapt std::less<T> for array_pod_sort.
1048template<typename T>
1049inline int array_pod_sort_comparator(const void *P1, const void *P2) {
1050 if (std::less<T>()(*reinterpret_cast<const T*>(P1),
1051 *reinterpret_cast<const T*>(P2)))
1052 return -1;
1053 if (std::less<T>()(*reinterpret_cast<const T*>(P2),
1054 *reinterpret_cast<const T*>(P1)))
1055 return 1;
1056 return 0;
1057}
1058
1059/// get_array_pod_sort_comparator - This is an internal helper function used to
1060/// get type deduction of T right.
1061template<typename T>
1062inline int (*get_array_pod_sort_comparator(const T &))
1063 (const void*, const void*) {
1064 return array_pod_sort_comparator<T>;
1065}
1066
1067/// array_pod_sort - This sorts an array with the specified start and end
1068/// extent. This is just like std::sort, except that it calls qsort instead of
1069/// using an inlined template. qsort is slightly slower than std::sort, but
1070/// most sorts are not performance critical in LLVM and std::sort has to be
1071/// template instantiated for each type, leading to significant measured code
1072/// bloat. This function should generally be used instead of std::sort where
1073/// possible.
1074///
1075/// This function assumes that you have simple POD-like types that can be
1076/// compared with std::less and can be moved with memcpy. If this isn't true,
1077/// you should use std::sort.
1078///
1079/// NOTE: If qsort_r were portable, we could allow a custom comparator and
1080/// default to std::less.
1081template<class IteratorTy>
1082inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
1083 // Don't inefficiently call qsort with one element or trigger undefined
1084 // behavior with an empty sequence.
1085 auto NElts = End - Start;
1086 if (NElts <= 1) return;
1087#ifdef EXPENSIVE_CHECKS
1088 std::mt19937 Generator(std::random_device{}());
1089 std::shuffle(Start, End, Generator);
1090#endif
1091 qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
1092}
1093
1094template <class IteratorTy>
1095inline void array_pod_sort(
1096 IteratorTy Start, IteratorTy End,
1097 int (*Compare)(
1098 const typename std::iterator_traits<IteratorTy>::value_type *,
1099 const typename std::iterator_traits<IteratorTy>::value_type *)) {
1100 // Don't inefficiently call qsort with one element or trigger undefined
1101 // behavior with an empty sequence.
1102 auto NElts = End - Start;
1103 if (NElts <= 1) return;
1104#ifdef EXPENSIVE_CHECKS
1105 std::mt19937 Generator(std::random_device{}());
1106 std::shuffle(Start, End, Generator);
1107#endif
1108 qsort(&*Start, NElts, sizeof(*Start),
1109 reinterpret_cast<int (*)(const void *, const void *)>(Compare));
1110}
1111
1112// Provide wrappers to std::sort which shuffle the elements before sorting
1113// to help uncover non-deterministic behavior (PR35135).
1114template <typename IteratorTy>
1115inline void sort(IteratorTy Start, IteratorTy End) {
1116#ifdef EXPENSIVE_CHECKS
1117 std::mt19937 Generator(std::random_device{}());
1118 std::shuffle(Start, End, Generator);
1119#endif
1120 std::sort(Start, End);
1121}
1122
1123template <typename Container> inline void sort(Container &&C) {
1124 llvm::sort(adl_begin(C), adl_end(C));
1125}
1126
1127template <typename IteratorTy, typename Compare>
1128inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) {
1129#ifdef EXPENSIVE_CHECKS
1130 std::mt19937 Generator(std::random_device{}());
1131 std::shuffle(Start, End, Generator);
1132#endif
1133 std::sort(Start, End, Comp);
1134}
1135
1136template <typename Container, typename Compare>
1137inline void sort(Container &&C, Compare Comp) {
1138 llvm::sort(adl_begin(C), adl_end(C), Comp);
1139}
1140
1141//===----------------------------------------------------------------------===//
1142// Extra additions to <algorithm>
1143//===----------------------------------------------------------------------===//
1144
1145/// For a container of pointers, deletes the pointers and then clears the
1146/// container.
1147template<typename Container>
1148void DeleteContainerPointers(Container &C) {
1149 for (auto V : C)
1150 delete V;
1151 C.clear();
1152}
1153
1154/// In a container of pairs (usually a map) whose second element is a pointer,
1155/// deletes the second elements and then clears the container.
1156template<typename Container>
1157void DeleteContainerSeconds(Container &C) {
1158 for (auto &V : C)
1159 delete V.second;
1160 C.clear();
1161}
1162
1163/// Get the size of a range. This is a wrapper function around std::distance
1164/// which is only enabled when the operation is O(1).
1165template <typename R>
1166auto size(R &&Range, typename std::enable_if<
1167 std::is_same<typename std::iterator_traits<decltype(
1168 Range.begin())>::iterator_category,
1169 std::random_access_iterator_tag>::value,
1170 void>::type * = nullptr)
1171 -> decltype(std::distance(Range.begin(), Range.end())) {
1172 return std::distance(Range.begin(), Range.end());
1173}
1174
1175/// Provide wrappers to std::for_each which take ranges instead of having to
1176/// pass begin/end explicitly.
1177template <typename R, typename UnaryPredicate>
1178UnaryPredicate for_each(R &&Range, UnaryPredicate P) {
1179 return std::for_each(adl_begin(Range), adl_end(Range), P);
1180}
1181
1182/// Provide wrappers to std::all_of which take ranges instead of having to pass
1183/// begin/end explicitly.
1184template <typename R, typename UnaryPredicate>
1185bool all_of(R &&Range, UnaryPredicate P) {
1186 return std::all_of(adl_begin(Range), adl_end(Range), P);
1187}
1188
1189/// Provide wrappers to std::any_of which take ranges instead of having to pass
1190/// begin/end explicitly.
1191template <typename R, typename UnaryPredicate>
1192bool any_of(R &&Range, UnaryPredicate P) {
1193 return std::any_of(adl_begin(Range), adl_end(Range), P);
1194}
1195
1196/// Provide wrappers to std::none_of which take ranges instead of having to pass
1197/// begin/end explicitly.
1198template <typename R, typename UnaryPredicate>
1199bool none_of(R &&Range, UnaryPredicate P) {
1200 return std::none_of(adl_begin(Range), adl_end(Range), P);
1201}
1202
1203/// Provide wrappers to std::find which take ranges instead of having to pass
1204/// begin/end explicitly.
1205template <typename R, typename T>
1206auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range)) {
1207 return std::find(adl_begin(Range), adl_end(Range), Val);
1208}
1209
1210/// Provide wrappers to std::find_if which take ranges instead of having to pass
1211/// begin/end explicitly.
1212template <typename R, typename UnaryPredicate>
1213auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1214 return std::find_if(adl_begin(Range), adl_end(Range), P);
1215}
1216
1217template <typename R, typename UnaryPredicate>
1218auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1219 return std::find_if_not(adl_begin(Range), adl_end(Range), P);
1220}
1221
1222/// Provide wrappers to std::remove_if which take ranges instead of having to
1223/// pass begin/end explicitly.
1224template <typename R, typename UnaryPredicate>
1225auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1226 return std::remove_if(adl_begin(Range), adl_end(Range), P);
1227}
1228
1229/// Provide wrappers to std::copy_if which take ranges instead of having to
1230/// pass begin/end explicitly.
1231template <typename R, typename OutputIt, typename UnaryPredicate>
1232OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
1233 return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
1234}
1235
1236template <typename R, typename OutputIt>
1237OutputIt copy(R &&Range, OutputIt Out) {
1238 return std::copy(adl_begin(Range), adl_end(Range), Out);
1239}
1240
1241/// Wrapper function around std::find to detect if an element exists
1242/// in a container.
1243template <typename R, typename E>
1244bool is_contained(R &&Range, const E &Element) {
1245 return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
1246}
1247
1248/// Wrapper function around std::count to count the number of times an element
1249/// \p Element occurs in the given range \p Range.
1250template <typename R, typename E>
1251auto count(R &&Range, const E &Element) ->
1252 typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
1253 return std::count(adl_begin(Range), adl_end(Range), Element);
1254}
1255
1256/// Wrapper function around std::count_if to count the number of times an
1257/// element satisfying a given predicate occurs in a range.
1258template <typename R, typename UnaryPredicate>
1259auto count_if(R &&Range, UnaryPredicate P) ->
1260 typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
1261 return std::count_if(adl_begin(Range), adl_end(Range), P);
1262}
1263
1264/// Wrapper function around std::transform to apply a function to a range and
1265/// store the result elsewhere.
1266template <typename R, typename OutputIt, typename UnaryPredicate>
1267OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) {
1268 return std::transform(adl_begin(Range), adl_end(Range), d_first, P);
1269}
1270
1271/// Provide wrappers to std::partition which take ranges instead of having to
1272/// pass begin/end explicitly.
1273template <typename R, typename UnaryPredicate>
1274auto partition(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1275 return std::partition(adl_begin(Range), adl_end(Range), P);
1276}
1277
1278/// Provide wrappers to std::lower_bound which take ranges instead of having to
1279/// pass begin/end explicitly.
1280template <typename R, typename T>
1281auto lower_bound(R &&Range, T &&Value) -> decltype(adl_begin(Range)) {
1282 return std::lower_bound(adl_begin(Range), adl_end(Range),
1283 std::forward<T>(Value));
1284}
1285
1286template <typename R, typename T, typename Compare>
1287auto lower_bound(R &&Range, T &&Value, Compare C)
1288 -> decltype(adl_begin(Range)) {
1289 return std::lower_bound(adl_begin(Range), adl_end(Range),
1290 std::forward<T>(Value), C);
1291}
1292
1293/// Provide wrappers to std::upper_bound which take ranges instead of having to
1294/// pass begin/end explicitly.
1295template <typename R, typename T>
1296auto upper_bound(R &&Range, T &&Value) -> decltype(adl_begin(Range)) {
1297 return std::upper_bound(adl_begin(Range), adl_end(Range),
1298 std::forward<T>(Value));
1299}
1300
1301template <typename R, typename T, typename Compare>
1302auto upper_bound(R &&Range, T &&Value, Compare C)
1303 -> decltype(adl_begin(Range)) {
1304 return std::upper_bound(adl_begin(Range), adl_end(Range),
1305 std::forward<T>(Value), C);
1306}
1307
1308template <typename R>
1309void stable_sort(R &&Range) {
1310 std::stable_sort(adl_begin(Range), adl_end(Range));
1311}
1312
1313template <typename R, typename Compare>
1314void stable_sort(R &&Range, Compare C) {
1315 std::stable_sort(adl_begin(Range), adl_end(Range), C);
1316}
1317
1318/// Binary search for the first index where a predicate is true.
1319/// Returns the first I in [Lo, Hi) where C(I) is true, or Hi if it never is.
1320/// Requires that C is always false below some limit, and always true above it.
1321///
1322/// Example:
1323/// size_t DawnModernEra = bsearch(1776, 2050, [](size_t Year){
1324/// return Presidents.for(Year).twitterHandle() != None;
1325/// });
1326///
1327/// Note the return value differs from std::binary_search!
1328template <typename Predicate>
1329size_t bsearch(size_t Lo, size_t Hi, Predicate P) {
1330 while (Lo != Hi) {
1331 assert(Hi > Lo)((Hi > Lo) ? static_cast<void> (0) : __assert_fail (
"Hi > Lo", "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/STLExtras.h"
, 1331, __PRETTY_FUNCTION__));
1332 size_t Mid = Lo + (Hi - Lo) / 2;
1333 if (P(Mid))
1334 Hi = Mid;
1335 else
1336 Lo = Mid + 1;
1337 }
1338 return Hi;
1339}
1340
1341/// Binary search for the first iterator where a predicate is true.
1342/// Returns the first I in [Lo, Hi) where C(*I) is true, or Hi if it never is.
1343/// Requires that C is always false below some limit, and always true above it.
1344template <typename It, typename Predicate,
1345 typename Val = decltype(*std::declval<It>())>
1346It bsearch(It Lo, It Hi, Predicate P) {
1347 return std::lower_bound(Lo, Hi, 0u,
1348 [&](const Val &V, unsigned) { return !P(V); });
1349}
1350
1351/// Binary search for the first iterator in a range where a predicate is true.
1352/// Requires that C is always false below some limit, and always true above it.
1353template <typename R, typename Predicate>
1354auto bsearch(R &&Range, Predicate P) -> decltype(adl_begin(Range)) {
1355 return bsearch(adl_begin(Range), adl_end(Range), P);
1356}
1357
1358/// Wrapper function around std::equal to detect if all elements
1359/// in a container are same.
1360template <typename R>
1361bool is_splat(R &&Range) {
1362 size_t range_size = size(Range);
1363 return range_size != 0 && (range_size == 1 ||
1364 std::equal(adl_begin(Range) + 1, adl_end(Range), adl_begin(Range)));
1365}
1366
1367/// Given a range of type R, iterate the entire range and return a
1368/// SmallVector with elements of the vector. This is useful, for example,
1369/// when you want to iterate a range and then sort the results.
1370template <unsigned Size, typename R>
1371SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size>
1372to_vector(R &&Range) {
1373 return {adl_begin(Range), adl_end(Range)};
1374}
1375
1376/// Provide a container algorithm similar to C++ Library Fundamentals v2's
1377/// `erase_if` which is equivalent to:
1378///
1379/// C.erase(remove_if(C, pred), C.end());
1380///
1381/// This version works for any container with an erase method call accepting
1382/// two iterators.
1383template <typename Container, typename UnaryPredicate>
1384void erase_if(Container &C, UnaryPredicate P) {
1385 C.erase(remove_if(C, P), C.end());
1386}
1387
1388//===----------------------------------------------------------------------===//
1389// Extra additions to <memory>
1390//===----------------------------------------------------------------------===//
1391
1392// Implement make_unique according to N3656.
1393
1394/// Constructs a `new T()` with the given args and returns a
1395/// `unique_ptr<T>` which owns the object.
1396///
1397/// Example:
1398///
1399/// auto p = make_unique<int>();
1400/// auto p = make_unique<std::tuple<int, int>>(0, 1);
1401template <class T, class... Args>
1402typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
1403make_unique(Args &&... args) {
1404 return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
10
←
Memory is allocated
→
1405}
1406
1407/// Constructs a `new T[n]` with the given args and returns a
1408/// `unique_ptr<T[]>` which owns the object.
1409///
1410/// \param n size of the new array.
1411///
1412/// Example:
1413///
1414/// auto p = make_unique<int[]>(2); // value-initializes the array with 0's.
1415template <class T>
1416typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
1417 std::unique_ptr<T>>::type
1418make_unique(size_t n) {
1419 return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
1420}
1421
1422/// This function isn't used and is only here to provide better compile errors.
1423template <class T, class... Args>
1424typename std::enable_if<std::extent<T>::value != 0>::type
1425make_unique(Args &&...) = delete;
1426
1427struct FreeDeleter {
1428 void operator()(void* v) {
1429 ::free(v);
1430 }
1431};
1432
1433template<typename First, typename Second>
1434struct pair_hash {
1435 size_t operator()(const std::pair<First, Second> &P) const {
1436 return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
1437 }
1438};
1439
1440/// A functor like C++14's std::less<void> in its absence.
1441struct less {
1442 template <typename A, typename B> bool operator()(A &&a, B &&b) const {
1443 return std::forward<A>(a) < std::forward<B>(b);
1444 }
1445};
1446
1447/// A functor like C++14's std::equal<void> in its absence.
1448struct equal {
1449 template <typename A, typename B> bool operator()(A &&a, B &&b) const {
1450 return std::forward<A>(a) == std::forward<B>(b);
1451 }
1452};
1453
1454/// Binary functor that adapts to any other binary functor after dereferencing
1455/// operands.
1456template <typename T> struct deref {
1457 T func;
1458
1459 // Could be further improved to cope with non-derivable functors and
1460 // non-binary functors (should be a variadic template member function
1461 // operator()).
1462 template <typename A, typename B>
1463 auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) {
1464 assert(lhs)((lhs) ? static_cast<void> (0) : __assert_fail ("lhs", "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/STLExtras.h"
, 1464, __PRETTY_FUNCTION__));
1465 assert(rhs)((rhs) ? static_cast<void> (0) : __assert_fail ("rhs", "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/STLExtras.h"
, 1465, __PRETTY_FUNCTION__));
1466 return func(*lhs, *rhs);
1467 }
1468};
1469
1470namespace detail {
1471
1472template <typename R> class enumerator_iter;
1473
1474template <typename R> struct result_pair {
1475 friend class enumerator_iter<R>;
1476
1477 result_pair() = default;
1478 result_pair(std::size_t Index, IterOfRange<R> Iter)
1479 : Index(Index), Iter(Iter) {}
1480
1481 result_pair<R> &operator=(const result_pair<R> &Other) {
1482 Index = Other.Index;
1483 Iter = Other.Iter;
1484 return *this;
1485 }
1486
1487 std::size_t index() const { return Index; }
1488 const ValueOfRange<R> &value() const { return *Iter; }
1489 ValueOfRange<R> &value() { return *Iter; }
1490
1491private:
1492 std::size_t Index = std::numeric_limits<std::size_t>::max();
1493 IterOfRange<R> Iter;
1494};
1495
1496template <typename R>
1497class enumerator_iter
1498 : public iterator_facade_base<
1499 enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>,
1500 typename std::iterator_traits<IterOfRange<R>>::difference_type,
1501 typename std::iterator_traits<IterOfRange<R>>::pointer,
1502 typename std::iterator_traits<IterOfRange<R>>::reference> {
1503 using result_type = result_pair<R>;
1504
1505public:
1506 explicit enumerator_iter(IterOfRange<R> EndIter)
1507 : Result(std::numeric_limits<size_t>::max(), EndIter) {}
1508
1509 enumerator_iter(std::size_t Index, IterOfRange<R> Iter)
1510 : Result(Index, Iter) {}
1511
1512 result_type &operator*() { return Result; }
1513 const result_type &operator*() const { return Result; }
1514
1515 enumerator_iter<R> &operator++() {
1516 assert(Result.Index != std::numeric_limits<size_t>::max())((Result.Index != std::numeric_limits<size_t>::max()) ?
static_cast<void> (0) : __assert_fail ("Result.Index != std::numeric_limits<size_t>::max()"
, "/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/STLExtras.h"
, 1516, __PRETTY_FUNCTION__));
1517 ++Result.Iter;
1518 ++Result.Index;
1519 return *this;
1520 }
1521
1522 bool operator==(const enumerator_iter<R> &RHS) const {
1523 // Don't compare indices here, only iterators. It's possible for an end
1524 // iterator to have different indices depending on whether it was created
1525 // by calling std::end() versus incrementing a valid iterator.
1526 return Result.Iter == RHS.Result.Iter;
1527 }
1528
1529 enumerator_iter<R> &operator=(const enumerator_iter<R> &Other) {
1530 Result = Other.Result;
1531 return *this;
1532 }
1533
1534private:
1535 result_type Result;
1536};
1537
1538template <typename R> class enumerator {
1539public:
1540 explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
1541
1542 enumerator_iter<R> begin() {
1543 return enumerator_iter<R>(0, std::begin(TheRange));
1544 }
1545
1546 enumerator_iter<R> end() {
1547 return enumerator_iter<R>(std::end(TheRange));
1548 }
1549
1550private:
1551 R TheRange;
1552};
1553
1554} // end namespace detail
1555
1556/// Given an input range, returns a new range whose values are are pair (A,B)
1557/// such that A is the 0-based index of the item in the sequence, and B is
1558/// the value from the original sequence. Example:
1559///
1560/// std::vector<char> Items = {'A', 'B', 'C', 'D'};
1561/// for (auto X : enumerate(Items)) {
1562/// printf("Item %d - %c\n", X.index(), X.value());
1563/// }
1564///
1565/// Output:
1566/// Item 0 - A
1567/// Item 1 - B
1568/// Item 2 - C
1569/// Item 3 - D
1570///
1571template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
1572 return detail::enumerator<R>(std::forward<R>(TheRange));
1573}
1574
1575namespace detail {
1576
1577template <typename F, typename Tuple, std::size_t... I>
1578auto apply_tuple_impl(F &&f, Tuple &&t, index_sequence<I...>)
1579 -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)) {
1580 return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...);
1581}
1582
1583} // end namespace detail
1584
1585/// Given an input tuple (a1, a2, ..., an), pass the arguments of the
1586/// tuple variadically to f as if by calling f(a1, a2, ..., an) and
1587/// return the result.
1588template <typename F, typename Tuple>
1589auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl(
1590 std::forward<F>(f), std::forward<Tuple>(t),
1591 build_index_impl<
1592 std::tuple_size<typename std::decay<Tuple>::type>::value>{})) {
1593 using Indices = build_index_impl<
1594 std::tuple_size<typename std::decay<Tuple>::type>::value>;
1595
1596 return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t),
1597 Indices{});
1598}
1599
1600/// Return true if the sequence [Begin, End) has exactly N items. Runs in O(N)
1601/// time. Not meant for use with random-access iterators.
1602template <typename IterTy>
1603bool hasNItems(
1604 IterTy &&Begin, IterTy &&End, unsigned N,
1605 typename std::enable_if<
1606 !std::is_same<
1607 typename std::iterator_traits<typename std::remove_reference<
1608 decltype(Begin)>::type>::iterator_category,
1609 std::random_access_iterator_tag>::value,
1610 void>::type * = nullptr) {
1611 for (; N; --N, ++Begin)
1612 if (Begin == End)
1613 return false; // Too few.
1614 return Begin == End;
1615}
1616
1617/// Return true if the sequence [Begin, End) has N or more items. Runs in O(N)
1618/// time. Not meant for use with random-access iterators.
1619template <typename IterTy>
1620bool hasNItemsOrMore(
1621 IterTy &&Begin, IterTy &&End, unsigned N,
1622 typename std::enable_if<
1623 !std::is_same<
1624 typename std::iterator_traits<typename std::remove_reference<
1625 decltype(Begin)>::type>::iterator_category,
1626 std::random_access_iterator_tag>::value,
1627 void>::type * = nullptr) {
1628 for (; N; --N, ++Begin)
1629 if (Begin == End)
1630 return false; // Too few.
1631 return true;
1632}
1633
1634/// Returns a raw pointer that represents the same address as the argument.
1635///
1636/// The late bound return should be removed once we move to C++14 to better
1637/// align with the C++20 declaration. Also, this implementation can be removed
1638/// once we move to C++20 where it's defined as std::to_addres()
1639///
1640/// The std::pointer_traits<>::to_address(p) variations of these overloads has
1641/// not been implemented.
1642template <class Ptr> auto to_address(const Ptr &P) -> decltype(P.operator->()) {
1643 return P.operator->();
1644}
1645template <class T> constexpr T *to_address(T *P) { return P; }
1646
1647} // end namespace llvm
1648
1649#endif // LLVM_ADT_STLEXTRAS_H