Bug Summary

File:lib/IR/Value.cpp
Warning:line 176, column 41
Called C++ object pointer is null

Annotated Source Code

/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp

1//===-- Value.cpp - Implement the Value class -----------------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the Value, ValueHandle, and User classes.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/IR/Value.h"
15#include "LLVMContextImpl.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/SmallString.h"
18#include "llvm/IR/CallSite.h"
19#include "llvm/IR/Constant.h"
20#include "llvm/IR/Constants.h"
21#include "llvm/IR/DataLayout.h"
22#include "llvm/IR/DerivedTypes.h"
23#include "llvm/IR/DerivedUser.h"
24#include "llvm/IR/GetElementPtrTypeIterator.h"
25#include "llvm/IR/InstrTypes.h"
26#include "llvm/IR/Instructions.h"
27#include "llvm/IR/IntrinsicInst.h"
28#include "llvm/IR/Module.h"
29#include "llvm/IR/Operator.h"
30#include "llvm/IR/Statepoint.h"
31#include "llvm/IR/ValueHandle.h"
32#include "llvm/IR/ValueSymbolTable.h"
33#include "llvm/Support/Debug.h"
34#include "llvm/Support/ErrorHandling.h"
35#include "llvm/Support/ManagedStatic.h"
36#include "llvm/Support/raw_ostream.h"
37#include <algorithm>
38
39using namespace llvm;
40
41//===----------------------------------------------------------------------===//
42// Value Class
43//===----------------------------------------------------------------------===//
44static inline Type *checkType(Type *Ty) {
45 assert(Ty && "Value defined with a null type: Error!")((Ty && "Value defined with a null type: Error!") ? static_cast
<void> (0) : __assert_fail ("Ty && \"Value defined with a null type: Error!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 45, __PRETTY_FUNCTION__))
;
46 return Ty;
47}
48
49Value::Value(Type *ty, unsigned scid)
50 : VTy(checkType(ty)), UseList(nullptr), SubclassID(scid),
51 HasValueHandle(0), SubclassOptionalData(0), SubclassData(0),
52 NumUserOperands(0), IsUsedByMD(false), HasName(false) {
53 static_assert(ConstantFirstVal == 0, "!(SubclassID < ConstantFirstVal)");
54 // FIXME: Why isn't this in the subclass gunk??
55 // Note, we cannot call isa<CallInst> before the CallInst has been
56 // constructed.
57 if (SubclassID == Instruction::Call || SubclassID == Instruction::Invoke)
58 assert((VTy->isFirstClassType() || VTy->isVoidTy() || VTy->isStructTy()) &&(((VTy->isFirstClassType() || VTy->isVoidTy() || VTy->
isStructTy()) && "invalid CallInst type!") ? static_cast
<void> (0) : __assert_fail ("(VTy->isFirstClassType() || VTy->isVoidTy() || VTy->isStructTy()) && \"invalid CallInst type!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 59, __PRETTY_FUNCTION__))
59 "invalid CallInst type!")(((VTy->isFirstClassType() || VTy->isVoidTy() || VTy->
isStructTy()) && "invalid CallInst type!") ? static_cast
<void> (0) : __assert_fail ("(VTy->isFirstClassType() || VTy->isVoidTy() || VTy->isStructTy()) && \"invalid CallInst type!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 59, __PRETTY_FUNCTION__))
;
60 else if (SubclassID != BasicBlockVal &&
61 (/*SubclassID < ConstantFirstVal ||*/ SubclassID > ConstantLastVal))
62 assert((VTy->isFirstClassType() || VTy->isVoidTy()) &&(((VTy->isFirstClassType() || VTy->isVoidTy()) &&
"Cannot create non-first-class values except for constants!"
) ? static_cast<void> (0) : __assert_fail ("(VTy->isFirstClassType() || VTy->isVoidTy()) && \"Cannot create non-first-class values except for constants!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 63, __PRETTY_FUNCTION__))
63 "Cannot create non-first-class values except for constants!")(((VTy->isFirstClassType() || VTy->isVoidTy()) &&
"Cannot create non-first-class values except for constants!"
) ? static_cast<void> (0) : __assert_fail ("(VTy->isFirstClassType() || VTy->isVoidTy()) && \"Cannot create non-first-class values except for constants!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 63, __PRETTY_FUNCTION__))
;
64 static_assert(sizeof(Value) == 2 * sizeof(void *) + 2 * sizeof(unsigned),
65 "Value too big");
66}
67
68Value::~Value() {
69 // Notify all ValueHandles (if present) that this value is going away.
70 if (HasValueHandle)
71 ValueHandleBase::ValueIsDeleted(this);
72 if (isUsedByMetadata())
73 ValueAsMetadata::handleDeletion(this);
74
75#ifndef NDEBUG // Only in -g mode...
76 // Check to make sure that there are no uses of this value that are still
77 // around when the value is destroyed. If there are, then we have a dangling
78 // reference and something is wrong. This code is here to print out where
79 // the value is still being referenced.
80 //
81 if (!use_empty()) {
82 dbgs() << "While deleting: " << *VTy << " %" << getName() << "\n";
83 for (auto *U : users())
84 dbgs() << "Use still stuck around after Def is destroyed:" << *U << "\n";
85 }
86#endif
87 assert(use_empty() && "Uses remain when a value is destroyed!")((use_empty() && "Uses remain when a value is destroyed!"
) ? static_cast<void> (0) : __assert_fail ("use_empty() && \"Uses remain when a value is destroyed!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 87, __PRETTY_FUNCTION__))
;
88
89 // If this value is named, destroy the name. This should not be in a symtab
90 // at this point.
91 destroyValueName();
92}
93
94void Value::deleteValue() {
95 switch (getValueID()) {
96#define HANDLE_VALUE(Name) \
97 case Value::Name##Val: \
98 delete static_cast<Name *>(this); \
99 break;
100#define HANDLE_MEMORY_VALUE(Name) \
101 case Value::Name##Val: \
102 static_cast<DerivedUser *>(this)->DeleteValue( \
103 static_cast<DerivedUser *>(this)); \
104 break;
105#define HANDLE_INSTRUCTION(Name) /* nothing */
106#include "llvm/IR/Value.def"
107
108#define HANDLE_INST(N, OPC, CLASS) \
109 case Value::InstructionVal + Instruction::OPC: \
110 delete static_cast<CLASS *>(this); \
111 break;
112#define HANDLE_USER_INST(N, OPC, CLASS)
113#include "llvm/IR/Instruction.def"
114
115 default:
116 llvm_unreachable("attempting to delete unknown value kind")::llvm::llvm_unreachable_internal("attempting to delete unknown value kind"
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 116)
;
117 }
118}
119
120void Value::destroyValueName() {
121 ValueName *Name = getValueName();
122 if (Name)
123 Name->Destroy();
124 setValueName(nullptr);
125}
126
127bool Value::hasNUses(unsigned N) const {
128 const_use_iterator UI = use_begin(), E = use_end();
129
130 for (; N; --N, ++UI)
131 if (UI == E) return false; // Too few.
132 return UI == E;
133}
134
135bool Value::hasNUsesOrMore(unsigned N) const {
136 const_use_iterator UI = use_begin(), E = use_end();
137
138 for (; N; --N, ++UI)
139 if (UI == E) return false; // Too few.
140
141 return true;
142}
143
144bool Value::isUsedInBasicBlock(const BasicBlock *BB) const {
145 // This can be computed either by scanning the instructions in BB, or by
146 // scanning the use list of this Value. Both lists can be very long, but
147 // usually one is quite short.
148 //
149 // Scan both lists simultaneously until one is exhausted. This limits the
150 // search to the shorter list.
151 BasicBlock::const_iterator BI = BB->begin(), BE = BB->end();
152 const_user_iterator UI = user_begin(), UE = user_end();
153 for (; BI != BE && UI != UE; ++BI, ++UI) {
154 // Scan basic block: Check if this Value is used by the instruction at BI.
155 if (is_contained(BI->operands(), this))
156 return true;
157 // Scan use list: Check if the use at UI is in BB.
158 const auto *User = dyn_cast<Instruction>(*UI);
159 if (User && User->getParent() == BB)
160 return true;
161 }
162 return false;
163}
164
165unsigned Value::getNumUses() const {
166 return (unsigned)std::distance(use_begin(), use_end());
167}
168
169static bool getSymTab(Value *V, ValueSymbolTable *&ST) {
170 ST = nullptr;
171 if (Instruction *I = dyn_cast<Instruction>(V)) {
172 if (BasicBlock *P = I->getParent())
173 if (Function *PP = P->getParent())
174 ST = PP->getValueSymbolTable();
175 } else if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
176 if (Function *P = BB->getParent())
177 ST = P->getValueSymbolTable();
178 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
179 if (Module *P = GV->getParent())
180 ST = &P->getValueSymbolTable();
181 } else if (Argument *A = dyn_cast<Argument>(V)) {
182 if (Function *P = A->getParent())
183 ST = P->getValueSymbolTable();
184 } else {
185 assert(isa<Constant>(V) && "Unknown value type!")((isa<Constant>(V) && "Unknown value type!") ? static_cast
<void> (0) : __assert_fail ("isa<Constant>(V) && \"Unknown value type!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 185, __PRETTY_FUNCTION__))
;
186 return true; // no name is setable for this.
187 }
188 return false;
189}
190
191ValueName *Value::getValueName() const {
192 if (!HasName) return nullptr;
193
194 LLVMContext &Ctx = getContext();
195 auto I = Ctx.pImpl->ValueNames.find(this);
196 assert(I != Ctx.pImpl->ValueNames.end() &&((I != Ctx.pImpl->ValueNames.end() && "No name entry found!"
) ? static_cast<void> (0) : __assert_fail ("I != Ctx.pImpl->ValueNames.end() && \"No name entry found!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 197, __PRETTY_FUNCTION__))
197 "No name entry found!")((I != Ctx.pImpl->ValueNames.end() && "No name entry found!"
) ? static_cast<void> (0) : __assert_fail ("I != Ctx.pImpl->ValueNames.end() && \"No name entry found!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 197, __PRETTY_FUNCTION__))
;
198
199 return I->second;
200}
201
202void Value::setValueName(ValueName *VN) {
203 LLVMContext &Ctx = getContext();
204
205 assert(HasName == Ctx.pImpl->ValueNames.count(this) &&((HasName == Ctx.pImpl->ValueNames.count(this) && "HasName bit out of sync!"
) ? static_cast<void> (0) : __assert_fail ("HasName == Ctx.pImpl->ValueNames.count(this) && \"HasName bit out of sync!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 206, __PRETTY_FUNCTION__))
206 "HasName bit out of sync!")((HasName == Ctx.pImpl->ValueNames.count(this) && "HasName bit out of sync!"
) ? static_cast<void> (0) : __assert_fail ("HasName == Ctx.pImpl->ValueNames.count(this) && \"HasName bit out of sync!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 206, __PRETTY_FUNCTION__))
;
207
208 if (!VN) {
209 if (HasName)
210 Ctx.pImpl->ValueNames.erase(this);
211 HasName = false;
212 return;
213 }
214
215 HasName = true;
216 Ctx.pImpl->ValueNames[this] = VN;
217}
218
219StringRef Value::getName() const {
220 // Make sure the empty string is still a C string. For historical reasons,
221 // some clients want to call .data() on the result and expect it to be null
222 // terminated.
223 if (!hasName())
224 return StringRef("", 0);
225 return getValueName()->getKey();
226}
227
228void Value::setNameImpl(const Twine &NewName) {
229 // Fast-path: LLVMContext can be set to strip out non-GlobalValue names
230 if (getContext().shouldDiscardValueNames() && !isa<GlobalValue>(this))
9
Assuming the condition is false
10
Taking false branch
231 return;
232
233 // Fast path for common IRBuilder case of setName("") when there is no name.
234 if (NewName.isTriviallyEmpty() && !hasName())
11
Taking false branch
235 return;
236
237 SmallString<256> NameData;
238 StringRef NameRef = NewName.toStringRef(NameData);
239 assert(NameRef.find_first_of(0) == StringRef::npos &&((NameRef.find_first_of(0) == StringRef::npos && "Null bytes are not allowed in names"
) ? static_cast<void> (0) : __assert_fail ("NameRef.find_first_of(0) == StringRef::npos && \"Null bytes are not allowed in names\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 240, __PRETTY_FUNCTION__))
240 "Null bytes are not allowed in names")((NameRef.find_first_of(0) == StringRef::npos && "Null bytes are not allowed in names"
) ? static_cast<void> (0) : __assert_fail ("NameRef.find_first_of(0) == StringRef::npos && \"Null bytes are not allowed in names\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 240, __PRETTY_FUNCTION__))
;
241
242 // Name isn't changing?
243 if (getName() == NameRef)
12
Assuming the condition is false
13
Taking false branch
244 return;
245
246 assert(!getType()->isVoidTy() && "Cannot assign a name to void values!")((!getType()->isVoidTy() && "Cannot assign a name to void values!"
) ? static_cast<void> (0) : __assert_fail ("!getType()->isVoidTy() && \"Cannot assign a name to void values!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 246, __PRETTY_FUNCTION__))
;
247
248 // Get the symbol table to update for this object.
249 ValueSymbolTable *ST;
250 if (getSymTab(this, ST))
14
Taking false branch
251 return; // Cannot set a name on this value (e.g. constant).
252
253 if (!ST) { // No symbol table to update? Just do the change.
15
Taking true branch
254 if (NameRef.empty()) {
16
Assuming the condition is false
17
Taking false branch
255 // Free the name for this value.
256 destroyValueName();
257 return;
258 }
259
260 // NOTE: Could optimize for the case the name is shrinking to not deallocate
261 // then reallocated.
262 destroyValueName();
263
264 // Create the new name.
265 setValueName(ValueName::Create(NameRef));
18
Calling 'StringMapEntry::Create'
266 getValueName()->setValue(this);
267 return;
268 }
269
270 // NOTE: Could optimize for the case the name is shrinking to not deallocate
271 // then reallocated.
272 if (hasName()) {
273 // Remove old name.
274 ST->removeValueName(getValueName());
275 destroyValueName();
276
277 if (NameRef.empty())
278 return;
279 }
280
281 // Name is changing to something new.
282 setValueName(ST->createValueName(NameRef, this));
283}
284
285void Value::setName(const Twine &NewName) {
286 setNameImpl(NewName);
8
Calling 'Value::setNameImpl'
287 if (Function *F = dyn_cast<Function>(this))
288 F->recalculateIntrinsicID();
289}
290
291void Value::takeName(Value *V) {
292 ValueSymbolTable *ST = nullptr;
293 // If this value has a name, drop it.
294 if (hasName()) {
1
Assuming the condition is false
2
Taking false branch
295 // Get the symtab this is in.
296 if (getSymTab(this, ST)) {
297 // We can't set a name on this value, but we need to clear V's name if
298 // it has one.
299 if (V->hasName()) V->setName("");
300 return; // Cannot set a name on this value (e.g. constant).
301 }
302
303 // Remove old name.
304 if (ST)
305 ST->removeValueName(getValueName());
306 destroyValueName();
307 }
308
309 // Now we know that this has no name.
310
311 // If V has no name either, we're done.
312 if (!V->hasName()) return;
3
Assuming the condition is false
4
Taking false branch
313
314 // Get this's symtab if we didn't before.
315 if (!ST) {
5
Taking true branch
316 if (getSymTab(this, ST)) {
6
Taking true branch
317 // Clear V's name.
318 V->setName("");
7
Calling 'Value::setName'
319 return; // Cannot set a name on this value (e.g. constant).
320 }
321 }
322
323 // Get V's ST, this should always succed, because V has a name.
324 ValueSymbolTable *VST;
325 bool Failure = getSymTab(V, VST);
326 assert(!Failure && "V has a name, so it should have a ST!")((!Failure && "V has a name, so it should have a ST!"
) ? static_cast<void> (0) : __assert_fail ("!Failure && \"V has a name, so it should have a ST!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 326, __PRETTY_FUNCTION__))
; (void)Failure;
327
328 // If these values are both in the same symtab, we can do this very fast.
329 // This works even if both values have no symtab yet.
330 if (ST == VST) {
331 // Take the name!
332 setValueName(V->getValueName());
333 V->setValueName(nullptr);
334 getValueName()->setValue(this);
335 return;
336 }
337
338 // Otherwise, things are slightly more complex. Remove V's name from VST and
339 // then reinsert it into ST.
340
341 if (VST)
342 VST->removeValueName(V->getValueName());
343 setValueName(V->getValueName());
344 V->setValueName(nullptr);
345 getValueName()->setValue(this);
346
347 if (ST)
348 ST->reinsertValue(this);
349}
350
351void Value::assertModuleIsMaterializedImpl() const {
352#ifndef NDEBUG
353 const GlobalValue *GV = dyn_cast<GlobalValue>(this);
354 if (!GV)
355 return;
356 const Module *M = GV->getParent();
357 if (!M)
358 return;
359 assert(M->isMaterialized())((M->isMaterialized()) ? static_cast<void> (0) : __assert_fail
("M->isMaterialized()", "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 359, __PRETTY_FUNCTION__))
;
360#endif
361}
362
363#ifndef NDEBUG
364static bool contains(SmallPtrSetImpl<ConstantExpr *> &Cache, ConstantExpr *Expr,
365 Constant *C) {
366 if (!Cache.insert(Expr).second)
367 return false;
368
369 for (auto &O : Expr->operands()) {
370 if (O == C)
371 return true;
372 auto *CE = dyn_cast<ConstantExpr>(O);
373 if (!CE)
374 continue;
375 if (contains(Cache, CE, C))
376 return true;
377 }
378 return false;
379}
380
381static bool contains(Value *Expr, Value *V) {
382 if (Expr == V)
383 return true;
384
385 auto *C = dyn_cast<Constant>(V);
386 if (!C)
387 return false;
388
389 auto *CE = dyn_cast<ConstantExpr>(Expr);
390 if (!CE)
391 return false;
392
393 SmallPtrSet<ConstantExpr *, 4> Cache;
394 return contains(Cache, CE, C);
395}
396#endif // NDEBUG
397
398void Value::doRAUW(Value *New, bool NoMetadata) {
399 assert(New && "Value::replaceAllUsesWith(<null>) is invalid!")((New && "Value::replaceAllUsesWith(<null>) is invalid!"
) ? static_cast<void> (0) : __assert_fail ("New && \"Value::replaceAllUsesWith(<null>) is invalid!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 399, __PRETTY_FUNCTION__))
;
400 assert(!contains(New, this) &&((!contains(New, this) && "this->replaceAllUsesWith(expr(this)) is NOT valid!"
) ? static_cast<void> (0) : __assert_fail ("!contains(New, this) && \"this->replaceAllUsesWith(expr(this)) is NOT valid!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 401, __PRETTY_FUNCTION__))
401 "this->replaceAllUsesWith(expr(this)) is NOT valid!")((!contains(New, this) && "this->replaceAllUsesWith(expr(this)) is NOT valid!"
) ? static_cast<void> (0) : __assert_fail ("!contains(New, this) && \"this->replaceAllUsesWith(expr(this)) is NOT valid!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 401, __PRETTY_FUNCTION__))
;
402 assert(New->getType() == getType() &&((New->getType() == getType() && "replaceAllUses of value with new value of different type!"
) ? static_cast<void> (0) : __assert_fail ("New->getType() == getType() && \"replaceAllUses of value with new value of different type!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 403, __PRETTY_FUNCTION__))
403 "replaceAllUses of value with new value of different type!")((New->getType() == getType() && "replaceAllUses of value with new value of different type!"
) ? static_cast<void> (0) : __assert_fail ("New->getType() == getType() && \"replaceAllUses of value with new value of different type!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 403, __PRETTY_FUNCTION__))
;
404
405 // Notify all ValueHandles (if present) that this value is going away.
406 if (HasValueHandle)
407 ValueHandleBase::ValueIsRAUWd(this, New);
408 if (!NoMetadata && isUsedByMetadata())
409 ValueAsMetadata::handleRAUW(this, New);
410
411 while (!use_empty()) {
412 Use &U = *UseList;
413 // Must handle Constants specially, we cannot call replaceUsesOfWith on a
414 // constant because they are uniqued.
415 if (auto *C = dyn_cast<Constant>(U.getUser())) {
416 if (!isa<GlobalValue>(C)) {
417 C->handleOperandChange(this, New);
418 continue;
419 }
420 }
421
422 U.set(New);
423 }
424
425 if (BasicBlock *BB = dyn_cast<BasicBlock>(this))
426 BB->replaceSuccessorsPhiUsesWith(cast<BasicBlock>(New));
427}
428
429void Value::replaceAllUsesWith(Value *New) {
430 doRAUW(New, false /* NoMetadata */);
431}
432
433void Value::replaceNonMetadataUsesWith(Value *New) {
434 doRAUW(New, true /* NoMetadata */);
435}
436
437// Like replaceAllUsesWith except it does not handle constants or basic blocks.
438// This routine leaves uses within BB.
439void Value::replaceUsesOutsideBlock(Value *New, BasicBlock *BB) {
440 assert(New && "Value::replaceUsesOutsideBlock(<null>, BB) is invalid!")((New && "Value::replaceUsesOutsideBlock(<null>, BB) is invalid!"
) ? static_cast<void> (0) : __assert_fail ("New && \"Value::replaceUsesOutsideBlock(<null>, BB) is invalid!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 440, __PRETTY_FUNCTION__))
;
441 assert(!contains(New, this) &&((!contains(New, this) && "this->replaceUsesOutsideBlock(expr(this), BB) is NOT valid!"
) ? static_cast<void> (0) : __assert_fail ("!contains(New, this) && \"this->replaceUsesOutsideBlock(expr(this), BB) is NOT valid!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 442, __PRETTY_FUNCTION__))
442 "this->replaceUsesOutsideBlock(expr(this), BB) is NOT valid!")((!contains(New, this) && "this->replaceUsesOutsideBlock(expr(this), BB) is NOT valid!"
) ? static_cast<void> (0) : __assert_fail ("!contains(New, this) && \"this->replaceUsesOutsideBlock(expr(this), BB) is NOT valid!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 442, __PRETTY_FUNCTION__))
;
443 assert(New->getType() == getType() &&((New->getType() == getType() && "replaceUses of value with new value of different type!"
) ? static_cast<void> (0) : __assert_fail ("New->getType() == getType() && \"replaceUses of value with new value of different type!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 444, __PRETTY_FUNCTION__))
444 "replaceUses of value with new value of different type!")((New->getType() == getType() && "replaceUses of value with new value of different type!"
) ? static_cast<void> (0) : __assert_fail ("New->getType() == getType() && \"replaceUses of value with new value of different type!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 444, __PRETTY_FUNCTION__))
;
445 assert(BB && "Basic block that may contain a use of 'New' must be defined\n")((BB && "Basic block that may contain a use of 'New' must be defined\n"
) ? static_cast<void> (0) : __assert_fail ("BB && \"Basic block that may contain a use of 'New' must be defined\\n\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 445, __PRETTY_FUNCTION__))
;
446
447 use_iterator UI = use_begin(), E = use_end();
448 for (; UI != E;) {
449 Use &U = *UI;
450 ++UI;
451 auto *Usr = dyn_cast<Instruction>(U.getUser());
452 if (Usr && Usr->getParent() == BB)
453 continue;
454 U.set(New);
455 }
456}
457
458void Value::replaceUsesExceptBlockAddr(Value *New) {
459 use_iterator UI = use_begin(), E = use_end();
460 for (; UI != E;) {
461 Use &U = *UI;
462 ++UI;
463
464 if (isa<BlockAddress>(U.getUser()))
465 continue;
466
467 // Must handle Constants specially, we cannot call replaceUsesOfWith on a
468 // constant because they are uniqued.
469 if (auto *C = dyn_cast<Constant>(U.getUser())) {
470 if (!isa<GlobalValue>(C)) {
471 C->handleOperandChange(this, New);
472 continue;
473 }
474 }
475
476 U.set(New);
477 }
478}
479
480namespace {
481// Various metrics for how much to strip off of pointers.
482enum PointerStripKind {
483 PSK_ZeroIndices,
484 PSK_ZeroIndicesAndAliases,
485 PSK_ZeroIndicesAndAliasesAndBarriers,
486 PSK_InBoundsConstantIndices,
487 PSK_InBounds
488};
489
490template <PointerStripKind StripKind>
491static const Value *stripPointerCastsAndOffsets(const Value *V) {
492 if (!V->getType()->isPointerTy())
493 return V;
494
495 // Even though we don't look through PHI nodes, we could be called on an
496 // instruction in an unreachable block, which may be on a cycle.
497 SmallPtrSet<const Value *, 4> Visited;
498
499 Visited.insert(V);
500 do {
501 if (auto *GEP = dyn_cast<GEPOperator>(V)) {
502 switch (StripKind) {
503 case PSK_ZeroIndicesAndAliases:
504 case PSK_ZeroIndicesAndAliasesAndBarriers:
505 case PSK_ZeroIndices:
506 if (!GEP->hasAllZeroIndices())
507 return V;
508 break;
509 case PSK_InBoundsConstantIndices:
510 if (!GEP->hasAllConstantIndices())
511 return V;
512 LLVM_FALLTHROUGH[[clang::fallthrough]];
513 case PSK_InBounds:
514 if (!GEP->isInBounds())
515 return V;
516 break;
517 }
518 V = GEP->getPointerOperand();
519 } else if (Operator::getOpcode(V) == Instruction::BitCast ||
520 Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
521 V = cast<Operator>(V)->getOperand(0);
522 } else if (auto *GA = dyn_cast<GlobalAlias>(V)) {
523 if (StripKind == PSK_ZeroIndices || GA->isInterposable())
524 return V;
525 V = GA->getAliasee();
526 } else {
527 if (auto CS = ImmutableCallSite(V)) {
528 if (const Value *RV = CS.getReturnedArgOperand()) {
529 V = RV;
530 continue;
531 }
532 // The result of invariant.group.barrier must alias it's argument,
533 // but it can't be marked with returned attribute, that's why it needs
534 // special case.
535 if (StripKind == PSK_ZeroIndicesAndAliasesAndBarriers &&
536 CS.getIntrinsicID() == Intrinsic::invariant_group_barrier) {
537 V = CS.getArgOperand(0);
538 continue;
539 }
540 }
541 return V;
542 }
543 assert(V->getType()->isPointerTy() && "Unexpected operand type!")((V->getType()->isPointerTy() && "Unexpected operand type!"
) ? static_cast<void> (0) : __assert_fail ("V->getType()->isPointerTy() && \"Unexpected operand type!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 543, __PRETTY_FUNCTION__))
;
544 } while (Visited.insert(V).second);
545
546 return V;
547}
548} // end anonymous namespace
549
550const Value *Value::stripPointerCasts() const {
551 return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndAliases>(this);
552}
553
554const Value *Value::stripPointerCastsNoFollowAliases() const {
555 return stripPointerCastsAndOffsets<PSK_ZeroIndices>(this);
556}
557
558const Value *Value::stripInBoundsConstantOffsets() const {
559 return stripPointerCastsAndOffsets<PSK_InBoundsConstantIndices>(this);
560}
561
562const Value *Value::stripPointerCastsAndBarriers() const {
563 return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndAliasesAndBarriers>(
564 this);
565}
566
567const Value *
568Value::stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL,
569 APInt &Offset) const {
570 if (!getType()->isPointerTy())
571 return this;
572
573 assert(Offset.getBitWidth() == DL.getPointerSizeInBits(cast<PointerType>(((Offset.getBitWidth() == DL.getPointerSizeInBits(cast<PointerType
>( getType())->getAddressSpace()) && "The offset must have exactly as many bits as our pointer."
) ? static_cast<void> (0) : __assert_fail ("Offset.getBitWidth() == DL.getPointerSizeInBits(cast<PointerType>( getType())->getAddressSpace()) && \"The offset must have exactly as many bits as our pointer.\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 575, __PRETTY_FUNCTION__))
574 getType())->getAddressSpace()) &&((Offset.getBitWidth() == DL.getPointerSizeInBits(cast<PointerType
>( getType())->getAddressSpace()) && "The offset must have exactly as many bits as our pointer."
) ? static_cast<void> (0) : __assert_fail ("Offset.getBitWidth() == DL.getPointerSizeInBits(cast<PointerType>( getType())->getAddressSpace()) && \"The offset must have exactly as many bits as our pointer.\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 575, __PRETTY_FUNCTION__))
575 "The offset must have exactly as many bits as our pointer.")((Offset.getBitWidth() == DL.getPointerSizeInBits(cast<PointerType
>( getType())->getAddressSpace()) && "The offset must have exactly as many bits as our pointer."
) ? static_cast<void> (0) : __assert_fail ("Offset.getBitWidth() == DL.getPointerSizeInBits(cast<PointerType>( getType())->getAddressSpace()) && \"The offset must have exactly as many bits as our pointer.\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 575, __PRETTY_FUNCTION__))
;
576
577 // Even though we don't look through PHI nodes, we could be called on an
578 // instruction in an unreachable block, which may be on a cycle.
579 SmallPtrSet<const Value *, 4> Visited;
580 Visited.insert(this);
581 const Value *V = this;
582 do {
583 if (auto *GEP = dyn_cast<GEPOperator>(V)) {
584 if (!GEP->isInBounds())
585 return V;
586 APInt GEPOffset(Offset);
587 if (!GEP->accumulateConstantOffset(DL, GEPOffset))
588 return V;
589 Offset = GEPOffset;
590 V = GEP->getPointerOperand();
591 } else if (Operator::getOpcode(V) == Instruction::BitCast) {
592 V = cast<Operator>(V)->getOperand(0);
593 } else if (auto *GA = dyn_cast<GlobalAlias>(V)) {
594 V = GA->getAliasee();
595 } else {
596 if (auto CS = ImmutableCallSite(V))
597 if (const Value *RV = CS.getReturnedArgOperand()) {
598 V = RV;
599 continue;
600 }
601
602 return V;
603 }
604 assert(V->getType()->isPointerTy() && "Unexpected operand type!")((V->getType()->isPointerTy() && "Unexpected operand type!"
) ? static_cast<void> (0) : __assert_fail ("V->getType()->isPointerTy() && \"Unexpected operand type!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 604, __PRETTY_FUNCTION__))
;
605 } while (Visited.insert(V).second);
606
607 return V;
608}
609
610const Value *Value::stripInBoundsOffsets() const {
611 return stripPointerCastsAndOffsets<PSK_InBounds>(this);
612}
613
614unsigned Value::getPointerDereferenceableBytes(const DataLayout &DL,
615 bool &CanBeNull) const {
616 assert(getType()->isPointerTy() && "must be pointer")((getType()->isPointerTy() && "must be pointer") ?
static_cast<void> (0) : __assert_fail ("getType()->isPointerTy() && \"must be pointer\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 616, __PRETTY_FUNCTION__))
;
617
618 unsigned DerefBytes = 0;
619 CanBeNull = false;
620 if (const Argument *A = dyn_cast<Argument>(this)) {
621 DerefBytes = A->getDereferenceableBytes();
622 if (DerefBytes == 0 && A->hasByValAttr() && A->getType()->isSized()) {
623 DerefBytes = DL.getTypeStoreSize(A->getType());
624 CanBeNull = false;
625 }
626 if (DerefBytes == 0) {
627 DerefBytes = A->getDereferenceableOrNullBytes();
628 CanBeNull = true;
629 }
630 } else if (auto CS = ImmutableCallSite(this)) {
631 DerefBytes = CS.getDereferenceableBytes(AttributeList::ReturnIndex);
632 if (DerefBytes == 0) {
633 DerefBytes = CS.getDereferenceableOrNullBytes(AttributeList::ReturnIndex);
634 CanBeNull = true;
635 }
636 } else if (const LoadInst *LI = dyn_cast<LoadInst>(this)) {
637 if (MDNode *MD = LI->getMetadata(LLVMContext::MD_dereferenceable)) {
638 ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
639 DerefBytes = CI->getLimitedValue();
640 }
641 if (DerefBytes == 0) {
642 if (MDNode *MD =
643 LI->getMetadata(LLVMContext::MD_dereferenceable_or_null)) {
644 ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
645 DerefBytes = CI->getLimitedValue();
646 }
647 CanBeNull = true;
648 }
649 } else if (auto *AI = dyn_cast<AllocaInst>(this)) {
650 if (AI->getAllocatedType()->isSized()) {
651 DerefBytes = DL.getTypeStoreSize(AI->getAllocatedType());
652 CanBeNull = false;
653 }
654 } else if (auto *GV = dyn_cast<GlobalVariable>(this)) {
655 if (GV->getValueType()->isSized() && !GV->hasExternalWeakLinkage()) {
656 // TODO: Don't outright reject hasExternalWeakLinkage but set the
657 // CanBeNull flag.
658 DerefBytes = DL.getTypeStoreSize(GV->getValueType());
659 CanBeNull = false;
660 }
661 }
662 return DerefBytes;
663}
664
665unsigned Value::getPointerAlignment(const DataLayout &DL) const {
666 assert(getType()->isPointerTy() && "must be pointer")((getType()->isPointerTy() && "must be pointer") ?
static_cast<void> (0) : __assert_fail ("getType()->isPointerTy() && \"must be pointer\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 666, __PRETTY_FUNCTION__))
;
667
668 unsigned Align = 0;
669 if (auto *GO = dyn_cast<GlobalObject>(this)) {
670 Align = GO->getAlignment();
671 if (Align == 0) {
672 if (auto *GVar = dyn_cast<GlobalVariable>(GO)) {
673 Type *ObjectType = GVar->getValueType();
674 if (ObjectType->isSized()) {
675 // If the object is defined in the current Module, we'll be giving
676 // it the preferred alignment. Otherwise, we have to assume that it
677 // may only have the minimum ABI alignment.
678 if (GVar->isStrongDefinitionForLinker())
679 Align = DL.getPreferredAlignment(GVar);
680 else
681 Align = DL.getABITypeAlignment(ObjectType);
682 }
683 }
684 }
685 } else if (const Argument *A = dyn_cast<Argument>(this)) {
686 Align = A->getParamAlignment();
687
688 if (!Align && A->hasStructRetAttr()) {
689 // An sret parameter has at least the ABI alignment of the return type.
690 Type *EltTy = cast<PointerType>(A->getType())->getElementType();
691 if (EltTy->isSized())
692 Align = DL.getABITypeAlignment(EltTy);
693 }
694 } else if (const AllocaInst *AI = dyn_cast<AllocaInst>(this)) {
695 Align = AI->getAlignment();
696 if (Align == 0) {
697 Type *AllocatedType = AI->getAllocatedType();
698 if (AllocatedType->isSized())
699 Align = DL.getPrefTypeAlignment(AllocatedType);
700 }
701 } else if (auto CS = ImmutableCallSite(this))
702 Align = CS.getAttributes().getRetAlignment();
703 else if (const LoadInst *LI = dyn_cast<LoadInst>(this))
704 if (MDNode *MD = LI->getMetadata(LLVMContext::MD_align)) {
705 ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
706 Align = CI->getLimitedValue();
707 }
708
709 return Align;
710}
711
712const Value *Value::DoPHITranslation(const BasicBlock *CurBB,
713 const BasicBlock *PredBB) const {
714 auto *PN = dyn_cast<PHINode>(this);
715 if (PN && PN->getParent() == CurBB)
716 return PN->getIncomingValueForBlock(PredBB);
717 return this;
718}
719
720LLVMContext &Value::getContext() const { return VTy->getContext(); }
721
722void Value::reverseUseList() {
723 if (!UseList || !UseList->Next)
724 // No need to reverse 0 or 1 uses.
725 return;
726
727 Use *Head = UseList;
728 Use *Current = UseList->Next;
729 Head->Next = nullptr;
730 while (Current) {
731 Use *Next = Current->Next;
732 Current->Next = Head;
733 Head->setPrev(&Current->Next);
734 Head = Current;
735 Current = Next;
736 }
737 UseList = Head;
738 Head->setPrev(&UseList);
739}
740
741bool Value::isSwiftError() const {
742 auto *Arg = dyn_cast<Argument>(this);
743 if (Arg)
744 return Arg->hasSwiftErrorAttr();
745 auto *Alloca = dyn_cast<AllocaInst>(this);
746 if (!Alloca)
747 return false;
748 return Alloca->isSwiftError();
749}
750
751//===----------------------------------------------------------------------===//
752// ValueHandleBase Class
753//===----------------------------------------------------------------------===//
754
755void ValueHandleBase::AddToExistingUseList(ValueHandleBase **List) {
756 assert(List && "Handle list is null?")((List && "Handle list is null?") ? static_cast<void
> (0) : __assert_fail ("List && \"Handle list is null?\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 756, __PRETTY_FUNCTION__))
;
757
758 // Splice ourselves into the list.
759 Next = *List;
760 *List = this;
761 setPrevPtr(List);
762 if (Next) {
763 Next->setPrevPtr(&Next);
764 assert(getValPtr() == Next->getValPtr() && "Added to wrong list?")((getValPtr() == Next->getValPtr() && "Added to wrong list?"
) ? static_cast<void> (0) : __assert_fail ("getValPtr() == Next->getValPtr() && \"Added to wrong list?\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 764, __PRETTY_FUNCTION__))
;
765 }
766}
767
768void ValueHandleBase::AddToExistingUseListAfter(ValueHandleBase *List) {
769 assert(List && "Must insert after existing node")((List && "Must insert after existing node") ? static_cast
<void> (0) : __assert_fail ("List && \"Must insert after existing node\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 769, __PRETTY_FUNCTION__))
;
770
771 Next = List->Next;
772 setPrevPtr(&List->Next);
773 List->Next = this;
774 if (Next)
775 Next->setPrevPtr(&Next);
776}
777
778void ValueHandleBase::AddToUseList() {
779 assert(getValPtr() && "Null pointer doesn't have a use list!")((getValPtr() && "Null pointer doesn't have a use list!"
) ? static_cast<void> (0) : __assert_fail ("getValPtr() && \"Null pointer doesn't have a use list!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 779, __PRETTY_FUNCTION__))
;
780
781 LLVMContextImpl *pImpl = getValPtr()->getContext().pImpl;
782
783 if (getValPtr()->HasValueHandle) {
784 // If this value already has a ValueHandle, then it must be in the
785 // ValueHandles map already.
786 ValueHandleBase *&Entry = pImpl->ValueHandles[getValPtr()];
787 assert(Entry && "Value doesn't have any handles?")((Entry && "Value doesn't have any handles?") ? static_cast
<void> (0) : __assert_fail ("Entry && \"Value doesn't have any handles?\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 787, __PRETTY_FUNCTION__))
;
788 AddToExistingUseList(&Entry);
789 return;
790 }
791
792 // Ok, it doesn't have any handles yet, so we must insert it into the
793 // DenseMap. However, doing this insertion could cause the DenseMap to
794 // reallocate itself, which would invalidate all of the PrevP pointers that
795 // point into the old table. Handle this by checking for reallocation and
796 // updating the stale pointers only if needed.
797 DenseMap<Value*, ValueHandleBase*> &Handles = pImpl->ValueHandles;
798 const void *OldBucketPtr = Handles.getPointerIntoBucketsArray();
799
800 ValueHandleBase *&Entry = Handles[getValPtr()];
801 assert(!Entry && "Value really did already have handles?")((!Entry && "Value really did already have handles?")
? static_cast<void> (0) : __assert_fail ("!Entry && \"Value really did already have handles?\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 801, __PRETTY_FUNCTION__))
;
802 AddToExistingUseList(&Entry);
803 getValPtr()->HasValueHandle = true;
804
805 // If reallocation didn't happen or if this was the first insertion, don't
806 // walk the table.
807 if (Handles.isPointerIntoBucketsArray(OldBucketPtr) ||
808 Handles.size() == 1) {
809 return;
810 }
811
812 // Okay, reallocation did happen. Fix the Prev Pointers.
813 for (DenseMap<Value*, ValueHandleBase*>::iterator I = Handles.begin(),
814 E = Handles.end(); I != E; ++I) {
815 assert(I->second && I->first == I->second->getValPtr() &&((I->second && I->first == I->second->getValPtr
() && "List invariant broken!") ? static_cast<void
> (0) : __assert_fail ("I->second && I->first == I->second->getValPtr() && \"List invariant broken!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 816, __PRETTY_FUNCTION__))
816 "List invariant broken!")((I->second && I->first == I->second->getValPtr
() && "List invariant broken!") ? static_cast<void
> (0) : __assert_fail ("I->second && I->first == I->second->getValPtr() && \"List invariant broken!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 816, __PRETTY_FUNCTION__))
;
817 I->second->setPrevPtr(&I->second);
818 }
819}
820
821void ValueHandleBase::RemoveFromUseList() {
822 assert(getValPtr() && getValPtr()->HasValueHandle &&((getValPtr() && getValPtr()->HasValueHandle &&
"Pointer doesn't have a use list!") ? static_cast<void>
(0) : __assert_fail ("getValPtr() && getValPtr()->HasValueHandle && \"Pointer doesn't have a use list!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 823, __PRETTY_FUNCTION__))
823 "Pointer doesn't have a use list!")((getValPtr() && getValPtr()->HasValueHandle &&
"Pointer doesn't have a use list!") ? static_cast<void>
(0) : __assert_fail ("getValPtr() && getValPtr()->HasValueHandle && \"Pointer doesn't have a use list!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 823, __PRETTY_FUNCTION__))
;
824
825 // Unlink this from its use list.
826 ValueHandleBase **PrevPtr = getPrevPtr();
827 assert(*PrevPtr == this && "List invariant broken")((*PrevPtr == this && "List invariant broken") ? static_cast
<void> (0) : __assert_fail ("*PrevPtr == this && \"List invariant broken\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 827, __PRETTY_FUNCTION__))
;
828
829 *PrevPtr = Next;
830 if (Next) {
831 assert(Next->getPrevPtr() == &Next && "List invariant broken")((Next->getPrevPtr() == &Next && "List invariant broken"
) ? static_cast<void> (0) : __assert_fail ("Next->getPrevPtr() == &Next && \"List invariant broken\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 831, __PRETTY_FUNCTION__))
;
832 Next->setPrevPtr(PrevPtr);
833 return;
834 }
835
836 // If the Next pointer was null, then it is possible that this was the last
837 // ValueHandle watching VP. If so, delete its entry from the ValueHandles
838 // map.
839 LLVMContextImpl *pImpl = getValPtr()->getContext().pImpl;
840 DenseMap<Value*, ValueHandleBase*> &Handles = pImpl->ValueHandles;
841 if (Handles.isPointerIntoBucketsArray(PrevPtr)) {
842 Handles.erase(getValPtr());
843 getValPtr()->HasValueHandle = false;
844 }
845}
846
847void ValueHandleBase::ValueIsDeleted(Value *V) {
848 assert(V->HasValueHandle && "Should only be called if ValueHandles present")((V->HasValueHandle && "Should only be called if ValueHandles present"
) ? static_cast<void> (0) : __assert_fail ("V->HasValueHandle && \"Should only be called if ValueHandles present\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 848, __PRETTY_FUNCTION__))
;
849
850 // Get the linked list base, which is guaranteed to exist since the
851 // HasValueHandle flag is set.
852 LLVMContextImpl *pImpl = V->getContext().pImpl;
853 ValueHandleBase *Entry = pImpl->ValueHandles[V];
854 assert(Entry && "Value bit set but no entries exist")((Entry && "Value bit set but no entries exist") ? static_cast
<void> (0) : __assert_fail ("Entry && \"Value bit set but no entries exist\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 854, __PRETTY_FUNCTION__))
;
855
856 // We use a local ValueHandleBase as an iterator so that ValueHandles can add
857 // and remove themselves from the list without breaking our iteration. This
858 // is not really an AssertingVH; we just have to give ValueHandleBase a kind.
859 // Note that we deliberately do not the support the case when dropping a value
860 // handle results in a new value handle being permanently added to the list
861 // (as might occur in theory for CallbackVH's): the new value handle will not
862 // be processed and the checking code will mete out righteous punishment if
863 // the handle is still present once we have finished processing all the other
864 // value handles (it is fine to momentarily add then remove a value handle).
865 for (ValueHandleBase Iterator(Assert, *Entry); Entry; Entry = Iterator.Next) {
866 Iterator.RemoveFromUseList();
867 Iterator.AddToExistingUseListAfter(Entry);
868 assert(Entry->Next == &Iterator && "Loop invariant broken.")((Entry->Next == &Iterator && "Loop invariant broken."
) ? static_cast<void> (0) : __assert_fail ("Entry->Next == &Iterator && \"Loop invariant broken.\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 868, __PRETTY_FUNCTION__))
;
869
870 switch (Entry->getKind()) {
871 case Assert:
872 break;
873 case Weak:
874 case WeakTracking:
875 // WeakTracking and Weak just go to null, which unlinks them
876 // from the list.
877 Entry->operator=(nullptr);
878 break;
879 case Callback:
880 // Forward to the subclass's implementation.
881 static_cast<CallbackVH*>(Entry)->deleted();
882 break;
883 }
884 }
885
886 // All callbacks, weak references, and assertingVHs should be dropped by now.
887 if (V->HasValueHandle) {
888#ifndef NDEBUG // Only in +Asserts mode...
889 dbgs() << "While deleting: " << *V->getType() << " %" << V->getName()
890 << "\n";
891 if (pImpl->ValueHandles[V]->getKind() == Assert)
892 llvm_unreachable("An asserting value handle still pointed to this"::llvm::llvm_unreachable_internal("An asserting value handle still pointed to this"
" value!", "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 893)
893 " value!")::llvm::llvm_unreachable_internal("An asserting value handle still pointed to this"
" value!", "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 893)
;
894
895#endif
896 llvm_unreachable("All references to V were not removed?")::llvm::llvm_unreachable_internal("All references to V were not removed?"
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 896)
;
897 }
898}
899
900void ValueHandleBase::ValueIsRAUWd(Value *Old, Value *New) {
901 assert(Old->HasValueHandle &&"Should only be called if ValueHandles present")((Old->HasValueHandle &&"Should only be called if ValueHandles present"
) ? static_cast<void> (0) : __assert_fail ("Old->HasValueHandle &&\"Should only be called if ValueHandles present\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 901, __PRETTY_FUNCTION__))
;
902 assert(Old != New && "Changing value into itself!")((Old != New && "Changing value into itself!") ? static_cast
<void> (0) : __assert_fail ("Old != New && \"Changing value into itself!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 902, __PRETTY_FUNCTION__))
;
903 assert(Old->getType() == New->getType() &&((Old->getType() == New->getType() && "replaceAllUses of value with new value of different type!"
) ? static_cast<void> (0) : __assert_fail ("Old->getType() == New->getType() && \"replaceAllUses of value with new value of different type!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 904, __PRETTY_FUNCTION__))
904 "replaceAllUses of value with new value of different type!")((Old->getType() == New->getType() && "replaceAllUses of value with new value of different type!"
) ? static_cast<void> (0) : __assert_fail ("Old->getType() == New->getType() && \"replaceAllUses of value with new value of different type!\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 904, __PRETTY_FUNCTION__))
;
905
906 // Get the linked list base, which is guaranteed to exist since the
907 // HasValueHandle flag is set.
908 LLVMContextImpl *pImpl = Old->getContext().pImpl;
909 ValueHandleBase *Entry = pImpl->ValueHandles[Old];
910
911 assert(Entry && "Value bit set but no entries exist")((Entry && "Value bit set but no entries exist") ? static_cast
<void> (0) : __assert_fail ("Entry && \"Value bit set but no entries exist\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 911, __PRETTY_FUNCTION__))
;
912
913 // We use a local ValueHandleBase as an iterator so that
914 // ValueHandles can add and remove themselves from the list without
915 // breaking our iteration. This is not really an AssertingVH; we
916 // just have to give ValueHandleBase some kind.
917 for (ValueHandleBase Iterator(Assert, *Entry); Entry; Entry = Iterator.Next) {
918 Iterator.RemoveFromUseList();
919 Iterator.AddToExistingUseListAfter(Entry);
920 assert(Entry->Next == &Iterator && "Loop invariant broken.")((Entry->Next == &Iterator && "Loop invariant broken."
) ? static_cast<void> (0) : __assert_fail ("Entry->Next == &Iterator && \"Loop invariant broken.\""
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 920, __PRETTY_FUNCTION__))
;
921
922 switch (Entry->getKind()) {
923 case Assert:
924 case Weak:
925 // Asserting and Weak handles do not follow RAUW implicitly.
926 break;
927 case WeakTracking:
928 // Weak goes to the new value, which will unlink it from Old's list.
929 Entry->operator=(New);
930 break;
931 case Callback:
932 // Forward to the subclass's implementation.
933 static_cast<CallbackVH*>(Entry)->allUsesReplacedWith(New);
934 break;
935 }
936 }
937
938#ifndef NDEBUG
939 // If any new weak value handles were added while processing the
940 // list, then complain about it now.
941 if (Old->HasValueHandle)
942 for (Entry = pImpl->ValueHandles[Old]; Entry; Entry = Entry->Next)
943 switch (Entry->getKind()) {
944 case WeakTracking:
945 dbgs() << "After RAUW from " << *Old->getType() << " %"
946 << Old->getName() << " to " << *New->getType() << " %"
947 << New->getName() << "\n";
948 llvm_unreachable(::llvm::llvm_unreachable_internal("A weak tracking value handle still pointed to the old value!\n"
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 949)
949 "A weak tracking value handle still pointed to the old value!\n")::llvm::llvm_unreachable_internal("A weak tracking value handle still pointed to the old value!\n"
, "/build/llvm-toolchain-snapshot-6.0~svn318211/lib/IR/Value.cpp"
, 949)
;
950 default:
951 break;
952 }
953#endif
954}
955
956// Pin the vtable to this file.
957void CallbackVH::anchor() {}

/build/llvm-toolchain-snapshot-6.0~svn318211/include/llvm/ADT/StringMap.h

1//===- StringMap.h - String Hash table map interface ------------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines the StringMap class.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ADT_STRINGMAP_H
15#define LLVM_ADT_STRINGMAP_H
16
17#include "llvm/ADT/StringRef.h"
18#include "llvm/ADT/iterator.h"
19#include "llvm/ADT/iterator_range.h"
20#include "llvm/Support/Allocator.h"
21#include "llvm/Support/PointerLikeTypeTraits.h"
22#include "llvm/Support/ErrorHandling.h"
23#include <algorithm>
24#include <cassert>
25#include <cstdint>
26#include <cstdlib>
27#include <cstring>
28#include <initializer_list>
29#include <iterator>
30#include <utility>
31
32namespace llvm {
33
34template<typename ValueTy> class StringMapConstIterator;
35template<typename ValueTy> class StringMapIterator;
36template<typename ValueTy> class StringMapKeyIterator;
37
38/// StringMapEntryBase - Shared base class of StringMapEntry instances.
39class StringMapEntryBase {
40 unsigned StrLen;
41
42public:
43 explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {}
44
45 unsigned getKeyLength() const { return StrLen; }
46};
47
48/// StringMapImpl - This is the base class of StringMap that is shared among
49/// all of its instantiations.
50class StringMapImpl {
51protected:
52 // Array of NumBuckets pointers to entries, null pointers are holes.
53 // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed
54 // by an array of the actual hash values as unsigned integers.
55 StringMapEntryBase **TheTable = nullptr;
56 unsigned NumBuckets = 0;
57 unsigned NumItems = 0;
58 unsigned NumTombstones = 0;
59 unsigned ItemSize;
60
61protected:
62 explicit StringMapImpl(unsigned itemSize)
63 : ItemSize(itemSize) {}
64 StringMapImpl(StringMapImpl &&RHS)
65 : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets),
66 NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones),
67 ItemSize(RHS.ItemSize) {
68 RHS.TheTable = nullptr;
69 RHS.NumBuckets = 0;
70 RHS.NumItems = 0;
71 RHS.NumTombstones = 0;
72 }
73
74 StringMapImpl(unsigned InitSize, unsigned ItemSize);
75 unsigned RehashTable(unsigned BucketNo = 0);
76
77 /// LookupBucketFor - Look up the bucket that the specified string should end
78 /// up in. If it already exists as a key in the map, the Item pointer for the
79 /// specified bucket will be non-null. Otherwise, it will be null. In either
80 /// case, the FullHashValue field of the bucket will be set to the hash value
81 /// of the string.
82 unsigned LookupBucketFor(StringRef Key);
83
84 /// FindKey - Look up the bucket that contains the specified key. If it exists
85 /// in the map, return the bucket number of the key. Otherwise return -1.
86 /// This does not modify the map.
87 int FindKey(StringRef Key) const;
88
89 /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
90 /// delete it. This aborts if the value isn't in the table.
91 void RemoveKey(StringMapEntryBase *V);
92
93 /// RemoveKey - Remove the StringMapEntry for the specified key from the
94 /// table, returning it. If the key is not in the table, this returns null.
95 StringMapEntryBase *RemoveKey(StringRef Key);
96
97 /// Allocate the table with the specified number of buckets and otherwise
98 /// setup the map as empty.
99 void init(unsigned Size);
100
101public:
102 static StringMapEntryBase *getTombstoneVal() {
103 uintptr_t Val = static_cast<uintptr_t>(-1);
104 Val <<= PointerLikeTypeTraits<StringMapEntryBase *>::NumLowBitsAvailable;
105 return reinterpret_cast<StringMapEntryBase *>(Val);
106 }
107
108 unsigned getNumBuckets() const { return NumBuckets; }
109 unsigned getNumItems() const { return NumItems; }
110
111 bool empty() const { return NumItems == 0; }
112 unsigned size() const { return NumItems; }
113
114 void swap(StringMapImpl &Other) {
115 std::swap(TheTable, Other.TheTable);
116 std::swap(NumBuckets, Other.NumBuckets);
117 std::swap(NumItems, Other.NumItems);
118 std::swap(NumTombstones, Other.NumTombstones);
119 }
120};
121
122/// StringMapEntry - This is used to represent one value that is inserted into
123/// a StringMap. It contains the Value itself and the key: the string length
124/// and data.
125template<typename ValueTy>
126class StringMapEntry : public StringMapEntryBase {
127public:
128 ValueTy second;
129
130 explicit StringMapEntry(unsigned strLen)
131 : StringMapEntryBase(strLen), second() {}
132 template <typename... InitTy>
133 StringMapEntry(unsigned strLen, InitTy &&... InitVals)
134 : StringMapEntryBase(strLen), second(std::forward<InitTy>(InitVals)...) {}
135 StringMapEntry(StringMapEntry &E) = delete;
136
137 StringRef getKey() const {
138 return StringRef(getKeyData(), getKeyLength());
139 }
140
141 const ValueTy &getValue() const { return second; }
142 ValueTy &getValue() { return second; }
143
144 void setValue(const ValueTy &V) { second = V; }
145
146 /// getKeyData - Return the start of the string data that is the key for this
147 /// value. The string data is always stored immediately after the
148 /// StringMapEntry object.
149 const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);}
150
151 StringRef first() const { return StringRef(getKeyData(), getKeyLength()); }
152
153 /// Create a StringMapEntry for the specified key construct the value using
154 /// \p InitiVals.
155 template <typename AllocatorTy, typename... InitTy>
156 static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator,
157 InitTy &&... InitVals) {
158 unsigned KeyLength = Key.size();
159
160 // Allocate a new item with space for the string at the end and a null
161 // terminator.
162 unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+
163 KeyLength+1;
164 unsigned Alignment = alignof(StringMapEntry);
165
166 StringMapEntry *NewItem =
23
'NewItem' initialized here
167 static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
21
Calling 'MallocAllocator::Allocate'
22
Returning from 'MallocAllocator::Allocate'
168
169 if (NewItem == nullptr)
24
Assuming the condition is true
25
Assuming pointer value is null
26
Taking true branch
170 report_bad_alloc_error("Allocation of StringMap entry failed.");
171
172 // Construct the value.
173 new (NewItem) StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...);
174
175 // Copy the string information.
176 char *StrBuffer = const_cast<char*>(NewItem->getKeyData());
27
Called C++ object pointer is null
177 if (KeyLength > 0)
178 memcpy(StrBuffer, Key.data(), KeyLength);
179 StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients.
180 return NewItem;
181 }
182
183 /// Create - Create a StringMapEntry with normal malloc/free.
184 template <typename... InitType>
185 static StringMapEntry *Create(StringRef Key, InitType &&... InitVal) {
186 MallocAllocator A;
187 return Create(Key, A, std::forward<InitType>(InitVal)...);
20
Calling 'StringMapEntry::Create'
188 }
189
190 static StringMapEntry *Create(StringRef Key) {
191 return Create(Key, ValueTy());
19
Calling 'StringMapEntry::Create'
192 }
193
194 /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded
195 /// into a StringMapEntry, return the StringMapEntry itself.
196 static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) {
197 char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>);
198 return *reinterpret_cast<StringMapEntry*>(Ptr);
199 }
200
201 /// Destroy - Destroy this StringMapEntry, releasing memory back to the
202 /// specified allocator.
203 template<typename AllocatorTy>
204 void Destroy(AllocatorTy &Allocator) {
205 // Free memory referenced by the item.
206 unsigned AllocSize =
207 static_cast<unsigned>(sizeof(StringMapEntry)) + getKeyLength() + 1;
208 this->~StringMapEntry();
209 Allocator.Deallocate(static_cast<void *>(this), AllocSize);
210 }
211
212 /// Destroy this object, releasing memory back to the malloc allocator.
213 void Destroy() {
214 MallocAllocator A;
215 Destroy(A);
216 }
217};
218
219/// StringMap - This is an unconventional map that is specialized for handling
220/// keys that are "strings", which are basically ranges of bytes. This does some
221/// funky memory allocation and hashing things to make it extremely efficient,
222/// storing the string data *after* the value in the map.
223template<typename ValueTy, typename AllocatorTy = MallocAllocator>
224class StringMap : public StringMapImpl {
225 AllocatorTy Allocator;
226
227public:
228 using MapEntryTy = StringMapEntry<ValueTy>;
229
230 StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
231
232 explicit StringMap(unsigned InitialSize)
233 : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
234
235 explicit StringMap(AllocatorTy A)
236 : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {}
237
238 StringMap(unsigned InitialSize, AllocatorTy A)
239 : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))),
240 Allocator(A) {}
241
242 StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
243 : StringMapImpl(List.size(), static_cast<unsigned>(sizeof(MapEntryTy))) {
244 for (const auto &P : List) {
245 insert(P);
246 }
247 }
248
249 StringMap(StringMap &&RHS)
250 : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {}
251
252 StringMap(const StringMap &RHS) :
253 StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))),
254 Allocator(RHS.Allocator) {
255 if (RHS.empty())
256 return;
257
258 // Allocate TheTable of the same size as RHS's TheTable, and set the
259 // sentinel appropriately (and NumBuckets).
260 init(RHS.NumBuckets);
261 unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1),
262 *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1);
263
264 NumItems = RHS.NumItems;
265 NumTombstones = RHS.NumTombstones;
266 for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
267 StringMapEntryBase *Bucket = RHS.TheTable[I];
268 if (!Bucket || Bucket == getTombstoneVal()) {
269 TheTable[I] = Bucket;
270 continue;
271 }
272
273 TheTable[I] = MapEntryTy::Create(
274 static_cast<MapEntryTy *>(Bucket)->getKey(), Allocator,
275 static_cast<MapEntryTy *>(Bucket)->getValue());
276 HashTable[I] = RHSHashTable[I];
277 }
278
279 // Note that here we've copied everything from the RHS into this object,
280 // tombstones included. We could, instead, have re-probed for each key to
281 // instantiate this new object without any tombstone buckets. The
282 // assumption here is that items are rarely deleted from most StringMaps,
283 // and so tombstones are rare, so the cost of re-probing for all inputs is
284 // not worthwhile.
285 }
286
287 StringMap &operator=(StringMap RHS) {
288 StringMapImpl::swap(RHS);
289 std::swap(Allocator, RHS.Allocator);
290 return *this;
291 }
292
293 ~StringMap() {
294 // Delete all the elements in the map, but don't reset the elements
295 // to default values. This is a copy of clear(), but avoids unnecessary
296 // work not required in the destructor.
297 if (!empty()) {
298 for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
299 StringMapEntryBase *Bucket = TheTable[I];
300 if (Bucket && Bucket != getTombstoneVal()) {
301 static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
302 }
303 }
304 }
305 free(TheTable);
306 }
307
308 AllocatorTy &getAllocator() { return Allocator; }
309 const AllocatorTy &getAllocator() const { return Allocator; }
310
311 using key_type = const char*;
312 using mapped_type = ValueTy;
313 using value_type = StringMapEntry<ValueTy>;
314 using size_type = size_t;
315
316 using const_iterator = StringMapConstIterator<ValueTy>;
317 using iterator = StringMapIterator<ValueTy>;
318
319 iterator begin() {
320 return iterator(TheTable, NumBuckets == 0);
321 }
322 iterator end() {
323 return iterator(TheTable+NumBuckets, true);
324 }
325 const_iterator begin() const {
326 return const_iterator(TheTable, NumBuckets == 0);
327 }
328 const_iterator end() const {
329 return const_iterator(TheTable+NumBuckets, true);
330 }
331
332 iterator_range<StringMapKeyIterator<ValueTy>> keys() const {
333 return make_range(StringMapKeyIterator<ValueTy>(begin()),
334 StringMapKeyIterator<ValueTy>(end()));
335 }
336
337 iterator find(StringRef Key) {
338 int Bucket = FindKey(Key);
339 if (Bucket == -1) return end();
340 return iterator(TheTable+Bucket, true);
341 }
342
343 const_iterator find(StringRef Key) const {
344 int Bucket = FindKey(Key);
345 if (Bucket == -1) return end();
346 return const_iterator(TheTable+Bucket, true);
347 }
348
349 /// lookup - Return the entry for the specified key, or a default
350 /// constructed value if no such entry exists.
351 ValueTy lookup(StringRef Key) const {
352 const_iterator it = find(Key);
353 if (it != end())
354 return it->second;
355 return ValueTy();
356 }
357
358 /// Lookup the ValueTy for the \p Key, or create a default constructed value
359 /// if the key is not in the map.
360 ValueTy &operator[](StringRef Key) { return try_emplace(Key).first->second; }
361
362 /// count - Return 1 if the element is in the map, 0 otherwise.
363 size_type count(StringRef Key) const {
364 return find(Key) == end() ? 0 : 1;
365 }
366
367 /// insert - Insert the specified key/value pair into the map. If the key
368 /// already exists in the map, return false and ignore the request, otherwise
369 /// insert it and return true.
370 bool insert(MapEntryTy *KeyValue) {
371 unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
372 StringMapEntryBase *&Bucket = TheTable[BucketNo];
373 if (Bucket && Bucket != getTombstoneVal())
374 return false; // Already exists in map.
375
376 if (Bucket == getTombstoneVal())
377 --NumTombstones;
378 Bucket = KeyValue;
379 ++NumItems;
380 assert(NumItems + NumTombstones <= NumBuckets)((NumItems + NumTombstones <= NumBuckets) ? static_cast<
void> (0) : __assert_fail ("NumItems + NumTombstones <= NumBuckets"
, "/build/llvm-toolchain-snapshot-6.0~svn318211/include/llvm/ADT/StringMap.h"
, 380, __PRETTY_FUNCTION__))
;
381
382 RehashTable();
383 return true;
384 }
385
386 /// insert - Inserts the specified key/value pair into the map if the key
387 /// isn't already in the map. The bool component of the returned pair is true
388 /// if and only if the insertion takes place, and the iterator component of
389 /// the pair points to the element with key equivalent to the key of the pair.
390 std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) {
391 return try_emplace(KV.first, std::move(KV.second));
392 }
393
394 /// Emplace a new element for the specified key into the map if the key isn't
395 /// already in the map. The bool component of the returned pair is true
396 /// if and only if the insertion takes place, and the iterator component of
397 /// the pair points to the element with key equivalent to the key of the pair.
398 template <typename... ArgsTy>
399 std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&... Args) {
400 unsigned BucketNo = LookupBucketFor(Key);
401 StringMapEntryBase *&Bucket = TheTable[BucketNo];
402 if (Bucket && Bucket != getTombstoneVal())
403 return std::make_pair(iterator(TheTable + BucketNo, false),
404 false); // Already exists in map.
405
406 if (Bucket == getTombstoneVal())
407 --NumTombstones;
408 Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(Args)...);
409 ++NumItems;
410 assert(NumItems + NumTombstones <= NumBuckets)((NumItems + NumTombstones <= NumBuckets) ? static_cast<
void> (0) : __assert_fail ("NumItems + NumTombstones <= NumBuckets"
, "/build/llvm-toolchain-snapshot-6.0~svn318211/include/llvm/ADT/StringMap.h"
, 410, __PRETTY_FUNCTION__))
;
411
412 BucketNo = RehashTable(BucketNo);
413 return std::make_pair(iterator(TheTable + BucketNo, false), true);
414 }
415
416 // clear - Empties out the StringMap
417 void clear() {
418 if (empty()) return;
419
420 // Zap all values, resetting the keys back to non-present (not tombstone),
421 // which is safe because we're removing all elements.
422 for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
423 StringMapEntryBase *&Bucket = TheTable[I];
424 if (Bucket && Bucket != getTombstoneVal()) {
425 static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
426 }
427 Bucket = nullptr;
428 }
429
430 NumItems = 0;
431 NumTombstones = 0;
432 }
433
434 /// remove - Remove the specified key/value pair from the map, but do not
435 /// erase it. This aborts if the key is not in the map.
436 void remove(MapEntryTy *KeyValue) {
437 RemoveKey(KeyValue);
438 }
439
440 void erase(iterator I) {
441 MapEntryTy &V = *I;
442 remove(&V);
443 V.Destroy(Allocator);
444 }
445
446 bool erase(StringRef Key) {
447 iterator I = find(Key);
448 if (I == end()) return false;
449 erase(I);
450 return true;
451 }
452};
453
454template <typename DerivedTy, typename ValueTy>
455class StringMapIterBase
456 : public iterator_facade_base<DerivedTy, std::forward_iterator_tag,
457 ValueTy> {
458protected:
459 StringMapEntryBase **Ptr = nullptr;
460
461public:
462 StringMapIterBase() = default;
463
464 explicit StringMapIterBase(StringMapEntryBase **Bucket,
465 bool NoAdvance = false)
466 : Ptr(Bucket) {
467 if (!NoAdvance) AdvancePastEmptyBuckets();
468 }
469
470 DerivedTy &operator=(const DerivedTy &Other) {
471 Ptr = Other.Ptr;
472 return static_cast<DerivedTy &>(*this);
473 }
474
475 bool operator==(const DerivedTy &RHS) const { return Ptr == RHS.Ptr; }
476
477 DerivedTy &operator++() { // Preincrement
478 ++Ptr;
479 AdvancePastEmptyBuckets();
480 return static_cast<DerivedTy &>(*this);
481 }
482
483 DerivedTy operator++(int) { // Post-increment
484 DerivedTy Tmp(Ptr);
485 ++*this;
486 return Tmp;
487 }
488
489private:
490 void AdvancePastEmptyBuckets() {
491 while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
492 ++Ptr;
493 }
494};
495
496template <typename ValueTy>
497class StringMapConstIterator
498 : public StringMapIterBase<StringMapConstIterator<ValueTy>,
499 const StringMapEntry<ValueTy>> {
500 using base = StringMapIterBase<StringMapConstIterator<ValueTy>,
501 const StringMapEntry<ValueTy>>;
502
503public:
504 StringMapConstIterator() = default;
505 explicit StringMapConstIterator(StringMapEntryBase **Bucket,
506 bool NoAdvance = false)
507 : base(Bucket, NoAdvance) {}
508
509 const StringMapEntry<ValueTy> &operator*() const {
510 return *static_cast<const StringMapEntry<ValueTy> *>(*this->Ptr);
511 }
512};
513
514template <typename ValueTy>
515class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>,
516 StringMapEntry<ValueTy>> {
517 using base =
518 StringMapIterBase<StringMapIterator<ValueTy>, StringMapEntry<ValueTy>>;
519
520public:
521 StringMapIterator() = default;
522 explicit StringMapIterator(StringMapEntryBase **Bucket,
523 bool NoAdvance = false)
524 : base(Bucket, NoAdvance) {}
525
526 StringMapEntry<ValueTy> &operator*() const {
527 return *static_cast<StringMapEntry<ValueTy> *>(*this->Ptr);
528 }
529
530 operator StringMapConstIterator<ValueTy>() const {
531 return StringMapConstIterator<ValueTy>(this->Ptr, true);
532 }
533};
534
535template <typename ValueTy>
536class StringMapKeyIterator
537 : public iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
538 StringMapConstIterator<ValueTy>,
539 std::forward_iterator_tag, StringRef> {
540 using base = iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
541 StringMapConstIterator<ValueTy>,
542 std::forward_iterator_tag, StringRef>;
543
544public:
545 StringMapKeyIterator() = default;
546 explicit StringMapKeyIterator(StringMapConstIterator<ValueTy> Iter)
547 : base(std::move(Iter)) {}
548
549 StringRef &operator*() {
550 Key = this->wrapped()->getKey();
551 return Key;
552 }
553
554private:
555 StringRef Key;
556};
557
558} // end namespace llvm
559
560#endif // LLVM_ADT_STRINGMAP_H