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
39using namespace llvm;
40
41static 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//===----------------------------------------------------------------------===//
48static inline Type *checkType(Type *Ty) {
49  assert(Ty && "Value defined with a null type: Error!");
50  return Ty;
51}
52
53Value::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
73Value::~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
103void 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
133void Value::destroyValueName() {
134  ValueName *Name = getValueName();
135  if (Name) {
136    MallocAllocator Allocator;
137    Name->Destroy(Allocator);
138  }
139  setValueName(nullptr);
140}
141
142bool Value::hasNUses(unsigned N) const {
143  return hasNItems(use_begin(), use_end(), N);
144}
145
146bool Value::hasNUsesOrMore(unsigned N) const {
147  return hasNItemsOrMore(use_begin(), use_end(), N);
148}
149
150static bool isUnDroppableUser(const User *U) { return !U->isDroppable(); }
151
152Use *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
164bool Value::hasNUndroppableUses(unsigned int N) const {
165  return hasNItems(user_begin(), user_end(), N, isUnDroppableUser);
166}
167
168bool Value::hasNUndroppableUsesOrMore(unsigned int N) const {
169  return hasNItemsOrMore(user_begin(), user_end(), N, isUnDroppableUser);
170}
171
172void 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
195bool 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
216unsigned Value::getNumUses() const {
217  return (unsigned)std::distance(use_begin(), use_end());
218}
219
220static 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
242ValueName *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
253void 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
270StringRef 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
279void 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
342void Value::setName(const Twine &NewName) {
343  setNameImpl(NewName);
344  if (Function *F = dyn_cast<Function>(this))
345    F->recalculateIntrinsicID();
346}
347
348void 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
408void 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
421static 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
438static 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
455void 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
486void Value::replaceAllUsesWith(Value *New) {
487  doRAUW(New, ReplaceMetadataUses::Yes);
488}
489
490void 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.
496void 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
511namespace {
512// Various metrics for how much to strip off of pointers.
513enum PointerStripKind {
514  PSK_ZeroIndices,
515  PSK_ZeroIndicesAndAliases,
516  PSK_ZeroIndicesSameRepresentation,
517  PSK_ZeroIndicesAndInvariantGroups,
518  PSK_InBoundsConstantIndices,
519  PSK_InBounds
520};
521
522template <PointerStripKind StripKind> static void NoopCallback(const Value *) {}
523
524template <PointerStripKind StripKind>
525static 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
593const Value *Value::stripPointerCasts() const {
594  return stripPointerCastsAndOffsets<PSK_ZeroIndices>(this);
595}
596
597const Value *Value::stripPointerCastsAndAliases() const {
598  return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndAliases>(this);
599}
600
601const Value *Value::stripPointerCastsSameRepresentation() const {
602  return stripPointerCastsAndOffsets<PSK_ZeroIndicesSameRepresentation>(this);
603}
604
605const Value *Value::stripInBoundsConstantOffsets() const {
606  return stripPointerCastsAndOffsets<PSK_InBoundsConstantIndices>(this);
607}
608
609const Value *Value::stripPointerCastsAndInvariantGroups() const {
610  return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndInvariantGroups>(this);
611}
612
613const 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
681const Value *
682Value::stripInBoundsOffsets(function_ref<void(const Value *)> Func) const {
683  return stripPointerCastsAndOffsets<PSK_InBounds>(this, Func);
684}
685
686uint64_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
753Align 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
818const 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
826LLVMContext &Value::getContext() const { return VTy->getContext(); }
827
828void 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
847bool 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
861void 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
874void 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
884void 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
927void 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
953void 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
1006void 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.
1063void CallbackVH::anchor() {}
1064