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