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