File: | lib/IR/Value.cpp |
Warning: | line 176, column 41 Called C++ object pointer is null |
[?] Use j/k keys for keyboard navigation
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 | ||||
40 | using namespace llvm; | |||
41 | ||||
42 | //===----------------------------------------------------------------------===// | |||
43 | // Value Class | |||
44 | //===----------------------------------------------------------------------===// | |||
45 | static 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 | ||||
50 | Value::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 | ||||
69 | Value::~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 | ||||
95 | void 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 | ||||
121 | void Value::destroyValueName() { | |||
122 | ValueName *Name = getValueName(); | |||
123 | if (Name) | |||
124 | Name->Destroy(); | |||
125 | setValueName(nullptr); | |||
126 | } | |||
127 | ||||
128 | bool 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 | ||||
136 | bool 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 | ||||
145 | bool 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 | ||||
166 | unsigned Value::getNumUses() const { | |||
167 | return (unsigned)std::distance(use_begin(), use_end()); | |||
168 | } | |||
169 | ||||
170 | static 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 | ||||
192 | ValueName *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 | ||||
203 | void 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 | ||||
220 | StringRef 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 | ||||
229 | void 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)) | |||
232 | return; | |||
233 | ||||
234 | // Fast path for common IRBuilder case of setName("") when there is no name. | |||
235 | if (NewName.isTriviallyEmpty() && !hasName()) | |||
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) | |||
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)) | |||
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. | |||
255 | if (NameRef.empty()) { | |||
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)); | |||
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 | ||||
286 | void Value::setName(const Twine &NewName) { | |||
287 | setNameImpl(NewName); | |||
288 | if (Function *F = dyn_cast<Function>(this)) | |||
289 | F->recalculateIntrinsicID(); | |||
290 | } | |||
291 | ||||
292 | void Value::takeName(Value *V) { | |||
293 | ValueSymbolTable *ST = nullptr; | |||
294 | // If this value has a name, drop it. | |||
295 | if (hasName()) { | |||
| ||||
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; | |||
314 | ||||
315 | // Get this's symtab if we didn't before. | |||
316 | if (!ST) { | |||
317 | if (getSymTab(this, ST)) { | |||
318 | // Clear V's name. | |||
319 | V->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 | ||||
352 | void 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 | |||
365 | static 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 | ||||
382 | static 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 | ||||
399 | void 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 | ||||
430 | void Value::replaceAllUsesWith(Value *New) { | |||
431 | doRAUW(New, false /* NoMetadata */); | |||
432 | } | |||
433 | ||||
434 | void 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. | |||
440 | void 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 | ||||
459 | void 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 | ||||
488 | namespace { | |||
489 | // Various metrics for how much to strip off of pointers. | |||
490 | enum PointerStripKind { | |||
491 | PSK_ZeroIndices, | |||
492 | PSK_ZeroIndicesAndAliases, | |||
493 | PSK_ZeroIndicesAndAliasesAndBarriers, | |||
494 | PSK_InBoundsConstantIndices, | |||
495 | PSK_InBounds | |||
496 | }; | |||
497 | ||||
498 | template <PointerStripKind StripKind> | |||
499 | static 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 | ||||
558 | const Value *Value::stripPointerCasts() const { | |||
559 | return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndAliases>(this); | |||
560 | } | |||
561 | ||||
562 | const Value *Value::stripPointerCastsNoFollowAliases() const { | |||
563 | return stripPointerCastsAndOffsets<PSK_ZeroIndices>(this); | |||
564 | } | |||
565 | ||||
566 | const Value *Value::stripInBoundsConstantOffsets() const { | |||
567 | return stripPointerCastsAndOffsets<PSK_InBoundsConstantIndices>(this); | |||
568 | } | |||
569 | ||||
570 | const Value *Value::stripPointerCastsAndBarriers() const { | |||
571 | return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndAliasesAndBarriers>( | |||
572 | this); | |||
573 | } | |||
574 | ||||
575 | const Value * | |||
576 | Value::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 | ||||
618 | const Value *Value::stripInBoundsOffsets() const { | |||
619 | return stripPointerCastsAndOffsets<PSK_InBounds>(this); | |||
620 | } | |||
621 | ||||
622 | uint64_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 | ||||
674 | unsigned 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 | ||||
721 | const 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 | ||||
729 | LLVMContext &Value::getContext() const { return VTy->getContext(); } | |||
730 | ||||
731 | void 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 | ||||
750 | bool 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 | ||||
764 | void 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 | ||||
777 | void 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 | ||||
787 | void 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 | ||||
830 | void 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 | ||||
856 | void 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 | ||||
909 | void 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. | |||
966 | void CallbackVH::anchor() {} |
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 | ||||
32 | namespace llvm { | |||
33 | ||||
34 | template<typename ValueTy> class StringMapConstIterator; | |||
35 | template<typename ValueTy> class StringMapIterator; | |||
36 | template<typename ValueTy> class StringMapKeyIterator; | |||
37 | ||||
38 | /// StringMapEntryBase - Shared base class of StringMapEntry instances. | |||
39 | class StringMapEntryBase { | |||
40 | unsigned StrLen; | |||
41 | ||||
42 | public: | |||
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. | |||
50 | class StringMapImpl { | |||
51 | protected: | |||
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 | ||||
61 | protected: | |||
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 | ||||
101 | public: | |||
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. | |||
125 | template<typename ValueTy> | |||
126 | class StringMapEntry : public StringMapEntryBase { | |||
127 | public: | |||
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 = | |||
167 | static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment)); | |||
168 | ||||
169 | if (NewItem == nullptr) | |||
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()); | |||
| ||||
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)...); | |||
188 | } | |||
189 | ||||
190 | static StringMapEntry *Create(StringRef Key) { | |||
191 | return Create(Key, ValueTy()); | |||
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. | |||
223 | template<typename ValueTy, typename AllocatorTy = MallocAllocator> | |||
224 | class StringMap : public StringMapImpl { | |||
225 | AllocatorTy Allocator; | |||
226 | ||||
227 | public: | |||
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 | ||||
454 | template <typename DerivedTy, typename ValueTy> | |||
455 | class StringMapIterBase | |||
456 | : public iterator_facade_base<DerivedTy, std::forward_iterator_tag, | |||
457 | ValueTy> { | |||
458 | protected: | |||
459 | StringMapEntryBase **Ptr = nullptr; | |||
460 | ||||
461 | public: | |||
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 | ||||
489 | private: | |||
490 | void AdvancePastEmptyBuckets() { | |||
491 | while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal()) | |||
492 | ++Ptr; | |||
493 | } | |||
494 | }; | |||
495 | ||||
496 | template <typename ValueTy> | |||
497 | class StringMapConstIterator | |||
498 | : public StringMapIterBase<StringMapConstIterator<ValueTy>, | |||
499 | const StringMapEntry<ValueTy>> { | |||
500 | using base = StringMapIterBase<StringMapConstIterator<ValueTy>, | |||
501 | const StringMapEntry<ValueTy>>; | |||
502 | ||||
503 | public: | |||
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 | ||||
514 | template <typename ValueTy> | |||
515 | class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>, | |||
516 | StringMapEntry<ValueTy>> { | |||
517 | using base = | |||
518 | StringMapIterBase<StringMapIterator<ValueTy>, StringMapEntry<ValueTy>>; | |||
519 | ||||
520 | public: | |||
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 | ||||
535 | template <typename ValueTy> | |||
536 | class 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 | ||||
544 | public: | |||
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 | ||||
554 | private: | |||
555 | StringRef Key; | |||
556 | }; | |||
557 | ||||
558 | } // end namespace llvm | |||
559 | ||||
560 | #endif // LLVM_ADT_STRINGMAP_H |