Bug Summary

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

Annotated Source Code

[?] Use j/k keys for keyboard navigation

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

/build/llvm-toolchain-snapshot-6.0~svn321639/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)(static_cast <bool> (NumItems + NumTombstones <= NumBuckets
) ? void (0) : __assert_fail ("NumItems + NumTombstones <= NumBuckets"
, "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/ADT/StringMap.h"
, 380, __extension__ __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)(static_cast <bool> (NumItems + NumTombstones <= NumBuckets
) ? void (0) : __assert_fail ("NumItems + NumTombstones <= NumBuckets"
, "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/ADT/StringMap.h"
, 410, __extension__ __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