1 //===-- Value.cpp - Implement the Value class -----------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the Value, ValueHandle, and User classes.
12 //===----------------------------------------------------------------------===//
14 #include "LLVMContextImpl.h"
15 #include "llvm/Constant.h"
16 #include "llvm/Constants.h"
17 #include "llvm/DerivedTypes.h"
18 #include "llvm/InstrTypes.h"
19 #include "llvm/Instructions.h"
20 #include "llvm/Operator.h"
21 #include "llvm/Module.h"
22 #include "llvm/Metadata.h"
23 #include "llvm/ValueSymbolTable.h"
24 #include "llvm/ADT/SmallString.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Support/ErrorHandling.h"
27 #include "llvm/Support/LeakDetector.h"
28 #include "llvm/Support/ManagedStatic.h"
29 #include "llvm/Support/ValueHandle.h"
30 #include "llvm/Support/raw_ostream.h"
31 #include "llvm/System/RWMutex.h"
32 #include "llvm/System/Threading.h"
33 #include "llvm/ADT/DenseMap.h"
37 //===----------------------------------------------------------------------===//
39 //===----------------------------------------------------------------------===//
41 static inline const Type
*checkType(const Type
*Ty
) {
42 assert(Ty
&& "Value defined with a null type: Error!");
46 Value::Value(const Type
*ty
, unsigned scid
)
47 : SubclassID(scid
), HasValueHandle(0), SubclassOptionalData(0),
48 SubclassData(0), VTy(checkType(ty
)),
50 if (isa
<CallInst
>(this) || isa
<InvokeInst
>(this))
51 assert((VTy
->isFirstClassType() ||
52 VTy
== Type::getVoidTy(ty
->getContext()) ||
53 isa
<OpaqueType
>(ty
) || VTy
->getTypeID() == Type::StructTyID
) &&
54 "invalid CallInst type!");
55 else if (!isa
<Constant
>(this) && !isa
<BasicBlock
>(this))
56 assert((VTy
->isFirstClassType() ||
57 VTy
== Type::getVoidTy(ty
->getContext()) ||
58 isa
<OpaqueType
>(ty
)) &&
59 "Cannot create non-first-class values except for constants!");
63 // Notify all ValueHandles (if present) that this value is going away.
65 ValueHandleBase::ValueIsDeleted(this);
67 #ifndef NDEBUG // Only in -g mode...
68 // Check to make sure that there are no uses of this value that are still
69 // around when the value is destroyed. If there are, then we have a dangling
70 // reference and something is wrong. This code is here to print out what is
71 // still being referenced. The value in question should be printed as
75 errs() << "While deleting: " << *VTy
<< " %" << getNameStr() << "\n";
76 for (use_iterator I
= use_begin(), E
= use_end(); I
!= E
; ++I
)
77 errs() << "Use still stuck around after Def is destroyed:"
81 assert(use_empty() && "Uses remain when a value is destroyed!");
83 // If this value is named, destroy the name. This should not be in a symtab
88 // There should be no uses of this object anymore, remove it.
89 LeakDetector::removeGarbageObject(this);
92 /// hasNUses - Return true if this Value has exactly N users.
94 bool Value::hasNUses(unsigned N
) const {
95 use_const_iterator UI
= use_begin(), E
= use_end();
98 if (UI
== E
) return false; // Too few.
102 /// hasNUsesOrMore - Return true if this value has N users or more. This is
103 /// logically equivalent to getNumUses() >= N.
105 bool Value::hasNUsesOrMore(unsigned N
) const {
106 use_const_iterator UI
= use_begin(), E
= use_end();
109 if (UI
== E
) return false; // Too few.
114 /// isUsedInBasicBlock - Return true if this value is used in the specified
116 bool Value::isUsedInBasicBlock(const BasicBlock
*BB
) const {
117 for (use_const_iterator I
= use_begin(), E
= use_end(); I
!= E
; ++I
) {
118 const Instruction
*User
= dyn_cast
<Instruction
>(*I
);
119 if (User
&& User
->getParent() == BB
)
126 /// getNumUses - This method computes the number of uses of this Value. This
127 /// is a linear time operation. Use hasOneUse or hasNUses to check for specific
129 unsigned Value::getNumUses() const {
130 return (unsigned)std::distance(use_begin(), use_end());
133 static bool getSymTab(Value
*V
, ValueSymbolTable
*&ST
) {
135 if (Instruction
*I
= dyn_cast
<Instruction
>(V
)) {
136 if (BasicBlock
*P
= I
->getParent())
137 if (Function
*PP
= P
->getParent())
138 ST
= &PP
->getValueSymbolTable();
139 } else if (BasicBlock
*BB
= dyn_cast
<BasicBlock
>(V
)) {
140 if (Function
*P
= BB
->getParent())
141 ST
= &P
->getValueSymbolTable();
142 } else if (GlobalValue
*GV
= dyn_cast
<GlobalValue
>(V
)) {
143 if (Module
*P
= GV
->getParent())
144 ST
= &P
->getValueSymbolTable();
145 } else if (Argument
*A
= dyn_cast
<Argument
>(V
)) {
146 if (Function
*P
= A
->getParent())
147 ST
= &P
->getValueSymbolTable();
148 } else if (NamedMDNode
*N
= dyn_cast
<NamedMDNode
>(V
)) {
149 if (Module
*P
= N
->getParent()) {
150 ST
= &P
->getValueSymbolTable();
152 } else if (isa
<MDString
>(V
))
155 assert(isa
<Constant
>(V
) && "Unknown value type!");
156 return true; // no name is setable for this.
161 StringRef
Value::getName() const {
162 // Make sure the empty string is still a C string. For historical reasons,
163 // some clients want to call .data() on the result and expect it to be null
165 if (!Name
) return StringRef("", 0);
166 return Name
->getKey();
169 std::string
Value::getNameStr() const {
170 return getName().str();
173 void Value::setName(const Twine
&NewName
) {
174 // Fast path for common IRBuilder case of setName("") when there is no name.
175 if (NewName
.isTriviallyEmpty() && !hasName())
178 SmallString
<256> NameData
;
179 NewName
.toVector(NameData
);
181 const char *NameStr
= NameData
.data();
182 unsigned NameLen
= NameData
.size();
184 // Name isn't changing?
185 if (getName() == StringRef(NameStr
, NameLen
))
188 assert(getType() != Type::getVoidTy(getContext()) &&
189 "Cannot assign a name to void values!");
191 // Get the symbol table to update for this object.
192 ValueSymbolTable
*ST
;
193 if (getSymTab(this, ST
))
194 return; // Cannot set a name on this value (e.g. constant).
196 if (!ST
) { // No symbol table to update? Just do the change.
198 // Free the name for this value.
207 // NOTE: Could optimize for the case the name is shrinking to not deallocate
210 // Create the new name.
211 Name
= ValueName::Create(NameStr
, NameStr
+NameLen
);
212 Name
->setValue(this);
216 // NOTE: Could optimize for the case the name is shrinking to not deallocate
220 ST
->removeValueName(Name
);
228 // Name is changing to something new.
229 Name
= ST
->createValueName(StringRef(NameStr
, NameLen
), this);
233 /// takeName - transfer the name from V to this value, setting V's name to
234 /// empty. It is an error to call V->takeName(V).
235 void Value::takeName(Value
*V
) {
236 ValueSymbolTable
*ST
= 0;
237 // If this value has a name, drop it.
239 // Get the symtab this is in.
240 if (getSymTab(this, ST
)) {
241 // We can't set a name on this value, but we need to clear V's name if
243 if (V
->hasName()) V
->setName("");
244 return; // Cannot set a name on this value (e.g. constant).
249 ST
->removeValueName(Name
);
254 // Now we know that this has no name.
256 // If V has no name either, we're done.
257 if (!V
->hasName()) return;
259 // Get this's symtab if we didn't before.
261 if (getSymTab(this, ST
)) {
264 return; // Cannot set a name on this value (e.g. constant).
268 // Get V's ST, this should always succed, because V has a name.
269 ValueSymbolTable
*VST
;
270 bool Failure
= getSymTab(V
, VST
);
271 assert(!Failure
&& "V has a name, so it should have a ST!"); Failure
=Failure
;
273 // If these values are both in the same symtab, we can do this very fast.
274 // This works even if both values have no symtab yet.
279 Name
->setValue(this);
283 // Otherwise, things are slightly more complex. Remove V's name from VST and
284 // then reinsert it into ST.
287 VST
->removeValueName(V
->Name
);
290 Name
->setValue(this);
293 ST
->reinsertValue(this);
297 // uncheckedReplaceAllUsesWith - This is exactly the same as replaceAllUsesWith,
298 // except that it doesn't have all of the asserts. The asserts fail because we
299 // are half-way done resolving types, which causes some types to exist as two
300 // different Type*'s at the same time. This is a sledgehammer to work around
303 void Value::uncheckedReplaceAllUsesWith(Value
*New
) {
304 // Notify all ValueHandles (if present) that this value is going away.
306 ValueHandleBase::ValueIsRAUWd(this, New
);
308 while (!use_empty()) {
310 // Must handle Constants specially, we cannot call replaceUsesOfWith on a
311 // constant because they are uniqued.
312 if (Constant
*C
= dyn_cast
<Constant
>(U
.getUser())) {
313 if (!isa
<GlobalValue
>(C
)) {
314 C
->replaceUsesOfWithOnConstant(this, New
, &U
);
323 void Value::replaceAllUsesWith(Value
*New
) {
324 assert(New
&& "Value::replaceAllUsesWith(<null>) is invalid!");
325 assert(New
!= this && "this->replaceAllUsesWith(this) is NOT valid!");
326 assert(New
->getType() == getType() &&
327 "replaceAllUses of value with new value of different type!");
329 uncheckedReplaceAllUsesWith(New
);
332 Value
*Value::stripPointerCasts() {
333 if (!isa
<PointerType
>(getType()))
337 if (GEPOperator
*GEP
= dyn_cast
<GEPOperator
>(V
)) {
338 if (!GEP
->hasAllZeroIndices())
340 V
= GEP
->getPointerOperand();
341 } else if (Operator::getOpcode(V
) == Instruction::BitCast
) {
342 V
= cast
<Operator
>(V
)->getOperand(0);
343 } else if (GlobalAlias
*GA
= dyn_cast
<GlobalAlias
>(V
)) {
344 if (GA
->mayBeOverridden())
346 V
= GA
->getAliasee();
350 assert(isa
<PointerType
>(V
->getType()) && "Unexpected operand type!");
354 Value
*Value::getUnderlyingObject() {
355 if (!isa
<PointerType
>(getType()))
358 unsigned MaxLookup
= 6;
360 if (GEPOperator
*GEP
= dyn_cast
<GEPOperator
>(V
)) {
361 V
= GEP
->getPointerOperand();
362 } else if (Operator::getOpcode(V
) == Instruction::BitCast
) {
363 V
= cast
<Operator
>(V
)->getOperand(0);
364 } else if (GlobalAlias
*GA
= dyn_cast
<GlobalAlias
>(V
)) {
365 if (GA
->mayBeOverridden())
367 V
= GA
->getAliasee();
371 assert(isa
<PointerType
>(V
->getType()) && "Unexpected operand type!");
372 } while (--MaxLookup
);
376 /// DoPHITranslation - If this value is a PHI node with CurBB as its parent,
377 /// return the value in the PHI node corresponding to PredBB. If not, return
378 /// ourself. This is useful if you want to know the value something has in a
379 /// predecessor block.
380 Value
*Value::DoPHITranslation(const BasicBlock
*CurBB
,
381 const BasicBlock
*PredBB
) {
382 PHINode
*PN
= dyn_cast
<PHINode
>(this);
383 if (PN
&& PN
->getParent() == CurBB
)
384 return PN
->getIncomingValueForBlock(PredBB
);
388 LLVMContext
&Value::getContext() const { return VTy
->getContext(); }
390 //===----------------------------------------------------------------------===//
391 // ValueHandleBase Class
392 //===----------------------------------------------------------------------===//
394 /// AddToExistingUseList - Add this ValueHandle to the use list for VP, where
395 /// List is known to point into the existing use list.
396 void ValueHandleBase::AddToExistingUseList(ValueHandleBase
**List
) {
397 assert(List
&& "Handle list is null?");
399 // Splice ourselves into the list.
404 Next
->setPrevPtr(&Next
);
405 assert(VP
== Next
->VP
&& "Added to wrong list?");
409 /// AddToUseList - Add this ValueHandle to the use list for VP.
410 void ValueHandleBase::AddToUseList() {
411 assert(VP
&& "Null pointer doesn't have a use list!");
413 LLVMContextImpl
*pImpl
= VP
->getContext().pImpl
;
415 if (VP
->HasValueHandle
) {
416 // If this value already has a ValueHandle, then it must be in the
417 // ValueHandles map already.
418 ValueHandleBase
*&Entry
= pImpl
->ValueHandles
[VP
];
419 assert(Entry
!= 0 && "Value doesn't have any handles?");
420 AddToExistingUseList(&Entry
);
424 // Ok, it doesn't have any handles yet, so we must insert it into the
425 // DenseMap. However, doing this insertion could cause the DenseMap to
426 // reallocate itself, which would invalidate all of the PrevP pointers that
427 // point into the old table. Handle this by checking for reallocation and
428 // updating the stale pointers only if needed.
429 DenseMap
<Value
*, ValueHandleBase
*> &Handles
= pImpl
->ValueHandles
;
430 const void *OldBucketPtr
= Handles
.getPointerIntoBucketsArray();
432 ValueHandleBase
*&Entry
= Handles
[VP
];
433 assert(Entry
== 0 && "Value really did already have handles?");
434 AddToExistingUseList(&Entry
);
435 VP
->HasValueHandle
= true;
437 // If reallocation didn't happen or if this was the first insertion, don't
439 if (Handles
.isPointerIntoBucketsArray(OldBucketPtr
) ||
440 Handles
.size() == 1) {
444 // Okay, reallocation did happen. Fix the Prev Pointers.
445 for (DenseMap
<Value
*, ValueHandleBase
*>::iterator I
= Handles
.begin(),
446 E
= Handles
.end(); I
!= E
; ++I
) {
447 assert(I
->second
&& I
->first
== I
->second
->VP
&& "List invariant broken!");
448 I
->second
->setPrevPtr(&I
->second
);
452 /// RemoveFromUseList - Remove this ValueHandle from its current use list.
453 void ValueHandleBase::RemoveFromUseList() {
454 assert(VP
&& VP
->HasValueHandle
&& "Pointer doesn't have a use list!");
456 // Unlink this from its use list.
457 ValueHandleBase
**PrevPtr
= getPrevPtr();
458 assert(*PrevPtr
== this && "List invariant broken");
462 assert(Next
->getPrevPtr() == &Next
&& "List invariant broken");
463 Next
->setPrevPtr(PrevPtr
);
467 // If the Next pointer was null, then it is possible that this was the last
468 // ValueHandle watching VP. If so, delete its entry from the ValueHandles
470 LLVMContextImpl
*pImpl
= VP
->getContext().pImpl
;
471 DenseMap
<Value
*, ValueHandleBase
*> &Handles
= pImpl
->ValueHandles
;
472 if (Handles
.isPointerIntoBucketsArray(PrevPtr
)) {
474 VP
->HasValueHandle
= false;
479 void ValueHandleBase::ValueIsDeleted(Value
*V
) {
480 assert(V
->HasValueHandle
&& "Should only be called if ValueHandles present");
482 // Get the linked list base, which is guaranteed to exist since the
483 // HasValueHandle flag is set.
484 LLVMContextImpl
*pImpl
= V
->getContext().pImpl
;
485 ValueHandleBase
*Entry
= pImpl
->ValueHandles
[V
];
486 assert(Entry
&& "Value bit set but no entries exist");
489 // Advance pointer to avoid invalidation.
490 ValueHandleBase
*ThisNode
= Entry
;
493 switch (ThisNode
->getKind()) {
495 #ifndef NDEBUG // Only in -g mode...
496 errs() << "While deleting: " << *V
->getType() << " %" << V
->getNameStr()
499 llvm_unreachable("An asserting value handle still pointed to this"
502 // Weak just goes to null, which will unlink it from the list.
503 ThisNode
->operator=(0);
506 // Forward to the subclass's implementation.
507 static_cast<CallbackVH
*>(ThisNode
)->deleted();
512 // All callbacks and weak references should be dropped by now.
513 assert(!V
->HasValueHandle
&& "All references to V were not removed?");
517 void ValueHandleBase::ValueIsRAUWd(Value
*Old
, Value
*New
) {
518 assert(Old
->HasValueHandle
&&"Should only be called if ValueHandles present");
519 assert(Old
!= New
&& "Changing value into itself!");
521 // Get the linked list base, which is guaranteed to exist since the
522 // HasValueHandle flag is set.
523 LLVMContextImpl
*pImpl
= Old
->getContext().pImpl
;
524 ValueHandleBase
*Entry
= pImpl
->ValueHandles
[Old
];
526 assert(Entry
&& "Value bit set but no entries exist");
529 // Advance pointer to avoid invalidation.
530 ValueHandleBase
*ThisNode
= Entry
;
533 switch (ThisNode
->getKind()) {
535 // Asserting handle does not follow RAUW implicitly.
538 // Weak goes to the new value, which will unlink it from Old's list.
539 ThisNode
->operator=(New
);
542 // Forward to the subclass's implementation.
543 static_cast<CallbackVH
*>(ThisNode
)->allUsesReplacedWith(New
);
549 /// ~CallbackVH. Empty, but defined here to avoid emitting the vtable
551 CallbackVH::~CallbackVH() {}
554 //===----------------------------------------------------------------------===//
556 //===----------------------------------------------------------------------===//
558 // replaceUsesOfWith - Replaces all references to the "From" definition with
559 // references to the "To" definition.
561 void User::replaceUsesOfWith(Value
*From
, Value
*To
) {
562 if (From
== To
) return; // Duh what?
564 assert((!isa
<Constant
>(this) || isa
<GlobalValue
>(this)) &&
565 "Cannot call User::replaceUsesOfWith on a constant!");
567 for (unsigned i
= 0, E
= getNumOperands(); i
!= E
; ++i
)
568 if (getOperand(i
) == From
) { // Is This operand is pointing to oldval?
569 // The side effects of this setOperand call include linking to
570 // "To", adding "this" to the uses list of To, and
571 // most importantly, removing "this" from the use list of "From".
572 setOperand(i
, To
); // Fix it now...