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