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