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