blob: b5af72b858ea9df48bed461d3890ae2b26723c28 [file] [log] [blame]
Chris Lattner2f7c9632001-06-06 20:29:01 +00001//===-- Value.cpp - Implement the Value class -----------------------------===//
Misha Brukmanb1c93172005-04-21 23:48:37 +00002//
John Criswell482202a2003-10-20 19:43:21 +00003// The LLVM Compiler Infrastructure
4//
Chris Lattnerf3ebc3f2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Misha Brukmanb1c93172005-04-21 23:48:37 +00007//
John Criswell482202a2003-10-20 19:43:21 +00008//===----------------------------------------------------------------------===//
Chris Lattner2f7c9632001-06-06 20:29:01 +00009//
Chris Lattner90234f32009-03-31 22:11:05 +000010// This file implements the Value, ValueHandle, and User classes.
Chris Lattner2f7c9632001-06-06 20:29:01 +000011//
12//===----------------------------------------------------------------------===//
13
Chandler Carruth9fb823b2013-01-02 11:36:10 +000014#include "llvm/IR/Value.h"
Owen Andersone8f21852009-08-18 18:28:58 +000015#include "LLVMContextImpl.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000016#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/SmallString.h"
Hal Finkelb0407ba2014-07-18 15:51:28 +000018#include "llvm/IR/CallSite.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000019#include "llvm/IR/Constant.h"
20#include "llvm/IR/Constants.h"
Hal Finkel2e42c342014-07-10 05:27:53 +000021#include "llvm/IR/DataLayout.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000022#include "llvm/IR/DerivedTypes.h"
Chandler Carruth03eb0de2014-03-04 10:40:04 +000023#include "llvm/IR/GetElementPtrTypeIterator.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000024#include "llvm/IR/InstrTypes.h"
25#include "llvm/IR/Instructions.h"
Chandler Carruth4b6845c2014-03-04 12:46:06 +000026#include "llvm/IR/LeakDetector.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000027#include "llvm/IR/Module.h"
28#include "llvm/IR/Operator.h"
Chandler Carruth4220e9c2014-03-04 11:17:44 +000029#include "llvm/IR/ValueHandle.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000030#include "llvm/IR/ValueSymbolTable.h"
Bill Wendling6a462f12006-11-17 08:03:48 +000031#include "llvm/Support/Debug.h"
Torok Edwin6dd27302009-07-08 18:01:40 +000032#include "llvm/Support/ErrorHandling.h"
Chris Lattner90234f32009-03-31 22:11:05 +000033#include "llvm/Support/ManagedStatic.h"
Chris Lattner2f7c9632001-06-06 20:29:01 +000034#include <algorithm>
Chris Lattner189d19f2003-11-21 20:23:48 +000035using namespace llvm;
Brian Gaeke960707c2003-11-11 22:41:34 +000036
Chris Lattner2f7c9632001-06-06 20:29:01 +000037//===----------------------------------------------------------------------===//
38// Value Class
39//===----------------------------------------------------------------------===//
40
Chris Lattner229907c2011-07-18 04:54:35 +000041static inline Type *checkType(Type *Ty) {
Chris Lattner25450e32001-12-13 00:41:27 +000042 assert(Ty && "Value defined with a null type: Error!");
Reid Kleckner16bf89e2014-06-09 23:32:20 +000043 return Ty;
Chris Lattner25450e32001-12-13 00:41:27 +000044}
45
Chris Lattner229907c2011-07-18 04:54:35 +000046Value::Value(Type *ty, unsigned scid)
Reid Kleckner16bf89e2014-06-09 23:32:20 +000047 : VTy(checkType(ty)), UseList(nullptr), Name(nullptr), SubclassID(scid),
48 HasValueHandle(0), SubclassOptionalData(0), SubclassData(0) {
Chris Lattnerb1ed91f2011-07-09 17:41:24 +000049 // FIXME: Why isn't this in the subclass gunk??
Richard Smith4a8e4542012-12-20 04:11:02 +000050 // Note, we cannot call isa<CallInst> before the CallInst has been
51 // constructed.
52 if (SubclassID == Instruction::Call || SubclassID == Instruction::Invoke)
Chris Lattnerb1ed91f2011-07-09 17:41:24 +000053 assert((VTy->isFirstClassType() || VTy->isVoidTy() || VTy->isStructTy()) &&
54 "invalid CallInst type!");
Richard Smith4a8e4542012-12-20 04:11:02 +000055 else if (SubclassID != BasicBlockVal &&
56 (SubclassID < ConstantFirstVal || SubclassID > ConstantLastVal))
Chris Lattnerb1ed91f2011-07-09 17:41:24 +000057 assert((VTy->isFirstClassType() || VTy->isVoidTy()) &&
Chris Lattnerbea72472004-07-06 17:44:17 +000058 "Cannot create non-first-class values except for constants!");
Chris Lattner2f7c9632001-06-06 20:29:01 +000059}
60
Gordon Henriksen14a55692007-12-10 02:14:30 +000061Value::~Value() {
Chris Lattner90234f32009-03-31 22:11:05 +000062 // Notify all ValueHandles (if present) that this value is going away.
63 if (HasValueHandle)
64 ValueHandleBase::ValueIsDeleted(this);
Daniel Dunbar6058b512009-09-20 04:03:34 +000065
Chris Lattner2f7c9632001-06-06 20:29:01 +000066#ifndef NDEBUG // Only in -g mode...
Chris Lattner874ddad2001-06-11 15:04:40 +000067 // Check to make sure that there are no uses of this value that are still
68 // around when the value is destroyed. If there are, then we have a dangling
69 // reference and something is wrong. This code is here to print out what is
Misha Brukmanb1c93172005-04-21 23:48:37 +000070 // still being referenced. The value in question should be printed as
Chris Lattner874ddad2001-06-11 15:04:40 +000071 // a <badref>
72 //
Gordon Henriksen14a55692007-12-10 02:14:30 +000073 if (!use_empty()) {
Benjamin Kramer1f97a5a2011-11-15 16:27:03 +000074 dbgs() << "While deleting: " << *VTy << " %" << getName() << "\n";
Gordon Henriksen14a55692007-12-10 02:14:30 +000075 for (use_iterator I = use_begin(), E = use_end(); I != E; ++I)
David Greene3f907a92010-01-05 01:30:09 +000076 dbgs() << "Use still stuck around after Def is destroyed:"
Bill Wendling6a462f12006-11-17 08:03:48 +000077 << **I << "\n";
Chris Lattner2f7c9632001-06-06 20:29:01 +000078 }
79#endif
Gordon Henriksen14a55692007-12-10 02:14:30 +000080 assert(use_empty() && "Uses remain when a value is destroyed!");
Chris Lattner694285c2009-08-04 23:07:12 +000081
82 // If this value is named, destroy the name. This should not be in a symtab
83 // at this point.
Bill Wendlingc4c568b2012-04-10 20:12:16 +000084 if (Name && SubclassID != MDStringVal)
Chris Lattner694285c2009-08-04 23:07:12 +000085 Name->Destroy();
Daniel Dunbar6058b512009-09-20 04:03:34 +000086
Chris Lattner694285c2009-08-04 23:07:12 +000087 // There should be no uses of this object anymore, remove it.
88 LeakDetector::removeGarbageObject(this);
Chris Lattner2f7c9632001-06-06 20:29:01 +000089}
90
Chris Lattner4947e672005-02-01 01:24:21 +000091bool Value::hasNUses(unsigned N) const {
Gabor Greifc78d7202010-03-25 23:06:16 +000092 const_use_iterator UI = use_begin(), E = use_end();
Chris Lattner4947e672005-02-01 01:24:21 +000093
94 for (; N; --N, ++UI)
95 if (UI == E) return false; // Too few.
96 return UI == E;
97}
98
Chris Lattnerd36552f2005-02-23 16:51:11 +000099bool Value::hasNUsesOrMore(unsigned N) const {
Gabor Greifc78d7202010-03-25 23:06:16 +0000100 const_use_iterator UI = use_begin(), E = use_end();
Chris Lattnerd36552f2005-02-23 16:51:11 +0000101
102 for (; N; --N, ++UI)
103 if (UI == E) return false; // Too few.
104
105 return true;
106}
107
Bill Wendling0c374212008-09-25 22:42:01 +0000108bool Value::isUsedInBasicBlock(const BasicBlock *BB) const {
Jakob Stoklund Olesen0925b242013-05-14 23:45:56 +0000109 // This can be computed either by scanning the instructions in BB, or by
110 // scanning the use list of this Value. Both lists can be very long, but
111 // usually one is quite short.
112 //
113 // Scan both lists simultaneously until one is exhausted. This limits the
114 // search to the shorter list.
115 BasicBlock::const_iterator BI = BB->begin(), BE = BB->end();
Chandler Carruthcdf47882014-03-09 03:16:01 +0000116 const_user_iterator UI = user_begin(), UE = user_end();
Jakob Stoklund Olesen0925b242013-05-14 23:45:56 +0000117 for (; BI != BE && UI != UE; ++BI, ++UI) {
118 // Scan basic block: Check if this Value is used by the instruction at BI.
119 if (std::find(BI->op_begin(), BI->op_end(), this) != BI->op_end())
Benjamin Kramer13231032011-12-05 17:23:27 +0000120 return true;
Jakob Stoklund Olesen0925b242013-05-14 23:45:56 +0000121 // Scan use list: Check if the use at UI is in BB.
122 const Instruction *User = dyn_cast<Instruction>(*UI);
Evan Cheng89553cc2008-06-12 21:15:59 +0000123 if (User && User->getParent() == BB)
124 return true;
125 }
126 return false;
127}
128
Chris Lattner4947e672005-02-01 01:24:21 +0000129unsigned Value::getNumUses() const {
130 return (unsigned)std::distance(use_begin(), use_end());
131}
132
Chris Lattnerb6250822007-02-11 00:37:27 +0000133static bool getSymTab(Value *V, ValueSymbolTable *&ST) {
Craig Topperc6207612014-04-09 06:08:46 +0000134 ST = nullptr;
Chris Lattnerb6250822007-02-11 00:37:27 +0000135 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)) {
Daniel Dunbar6058b512009-09-20 04:03:34 +0000140 if (Function *P = BB->getParent())
Chris Lattnerb6250822007-02-11 00:37:27 +0000141 ST = &P->getValueSymbolTable();
142 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
Daniel Dunbar6058b512009-09-20 04:03:34 +0000143 if (Module *P = GV->getParent())
Chris Lattnerb6250822007-02-11 00:37:27 +0000144 ST = &P->getValueSymbolTable();
145 } else if (Argument *A = dyn_cast<Argument>(V)) {
Daniel Dunbar6058b512009-09-20 04:03:34 +0000146 if (Function *P = A->getParent())
Chris Lattnerb6250822007-02-11 00:37:27 +0000147 ST = &P->getValueSymbolTable();
Devang Patel7428d8a2009-07-22 17:43:22 +0000148 } else if (isa<MDString>(V))
149 return true;
150 else {
Chris Lattnerb6250822007-02-11 00:37:27 +0000151 assert(isa<Constant>(V) && "Unknown value type!");
152 return true; // no name is setable for this.
153 }
154 return false;
155}
Chris Lattner2c6abea2002-10-09 23:12:59 +0000156
Daniel Dunbar32285942009-07-26 00:51:56 +0000157StringRef Value::getName() const {
Daniel Dunbar7cc8f7e2009-07-26 09:22:02 +0000158 // Make sure the empty string is still a C string. For historical reasons,
159 // some clients want to call .data() on the result and expect it to be null
160 // terminated.
161 if (!Name) return StringRef("", 0);
Daniel Dunbar32285942009-07-26 00:51:56 +0000162 return Name->getKey();
Chris Lattner5109a882007-08-10 15:34:35 +0000163}
164
Daniel Dunbard786b512009-07-26 00:34:27 +0000165void Value::setName(const Twine &NewName) {
Bill Wendlingc4c568b2012-04-10 20:12:16 +0000166 assert(SubclassID != MDStringVal &&
167 "Cannot set the name of MDString with this method!");
168
Daniel Dunbarcb13b482009-08-19 23:37:23 +0000169 // Fast path for common IRBuilder case of setName("") when there is no name.
170 if (NewName.isTriviallyEmpty() && !hasName())
171 return;
172
Daniel Dunbaracf0b252009-08-19 05:08:06 +0000173 SmallString<256> NameData;
Benjamin Kramer2e06b932010-01-13 12:45:23 +0000174 StringRef NameRef = NewName.toStringRef(NameData);
Rafael Espindola09d689f2013-11-19 21:12:39 +0000175 assert(NameRef.find_first_of(0) == StringRef::npos &&
176 "Null bytes are not allowed in names");
Daniel Dunbard786b512009-07-26 00:34:27 +0000177
Daniel Dunbara32c9992009-07-26 00:42:33 +0000178 // Name isn't changing?
Benjamin Kramer2e06b932010-01-13 12:45:23 +0000179 if (getName() == NameRef)
Daniel Dunbara32c9992009-07-26 00:42:33 +0000180 return;
181
Benjamin Kramerccce8ba2010-01-05 13:12:22 +0000182 assert(!getType()->isVoidTy() && "Cannot assign a name to void values!");
Daniel Dunbar6058b512009-09-20 04:03:34 +0000183
Chris Lattnerffb37782005-03-06 02:14:28 +0000184 // Get the symbol table to update for this object.
Chris Lattnerb6250822007-02-11 00:37:27 +0000185 ValueSymbolTable *ST;
186 if (getSymTab(this, ST))
187 return; // Cannot set a name on this value (e.g. constant).
Chris Lattnercdb9bfc2005-03-05 19:51:50 +0000188
Michael Ilseman516d7032013-03-01 18:48:54 +0000189 if (Function *F = dyn_cast<Function>(this))
190 getContext().pImpl->IntrinsicIDCache.erase(F);
191
Chris Lattner32ab6432007-02-12 05:18:08 +0000192 if (!ST) { // No symbol table to update? Just do the change.
Benjamin Kramer2e06b932010-01-13 12:45:23 +0000193 if (NameRef.empty()) {
Chris Lattner32ab6432007-02-12 05:18:08 +0000194 // Free the name for this value.
195 Name->Destroy();
Craig Topperc6207612014-04-09 06:08:46 +0000196 Name = nullptr;
Chris Lattner1a5de582007-02-12 18:52:59 +0000197 return;
Chris Lattnerffb37782005-03-06 02:14:28 +0000198 }
Daniel Dunbar6058b512009-09-20 04:03:34 +0000199
Daniel Dunbara32c9992009-07-26 00:42:33 +0000200 if (Name)
Chris Lattner1a5de582007-02-12 18:52:59 +0000201 Name->Destroy();
Daniel Dunbar6058b512009-09-20 04:03:34 +0000202
Chris Lattner1a5de582007-02-12 18:52:59 +0000203 // NOTE: Could optimize for the case the name is shrinking to not deallocate
204 // then reallocated.
Daniel Dunbar6058b512009-09-20 04:03:34 +0000205
Chris Lattner1a5de582007-02-12 18:52:59 +0000206 // Create the new name.
Craig Topper213d2f72014-06-11 05:35:56 +0000207 Name = ValueName::Create(NameRef);
Chris Lattner1a5de582007-02-12 18:52:59 +0000208 Name->setValue(this);
Chris Lattner32ab6432007-02-12 05:18:08 +0000209 return;
Chris Lattnerffb37782005-03-06 02:14:28 +0000210 }
Daniel Dunbar6058b512009-09-20 04:03:34 +0000211
Chris Lattner32ab6432007-02-12 05:18:08 +0000212 // NOTE: Could optimize for the case the name is shrinking to not deallocate
213 // then reallocated.
214 if (hasName()) {
Chris Lattner32ab6432007-02-12 05:18:08 +0000215 // Remove old name.
216 ST->removeValueName(Name);
217 Name->Destroy();
Craig Topperc6207612014-04-09 06:08:46 +0000218 Name = nullptr;
Chris Lattner32ab6432007-02-12 05:18:08 +0000219
Benjamin Kramer2e06b932010-01-13 12:45:23 +0000220 if (NameRef.empty())
Chris Lattner1a5de582007-02-12 18:52:59 +0000221 return;
Chris Lattner32ab6432007-02-12 05:18:08 +0000222 }
223
224 // Name is changing to something new.
Benjamin Kramer2e06b932010-01-13 12:45:23 +0000225 Name = ST->createValueName(NameRef, this);
Chris Lattnercdb9bfc2005-03-05 19:51:50 +0000226}
227
Chris Lattnerb6250822007-02-11 00:37:27 +0000228void Value::takeName(Value *V) {
Bill Wendlingc4c568b2012-04-10 20:12:16 +0000229 assert(SubclassID != MDStringVal && "Cannot take the name of an MDString!");
230
Craig Topperc6207612014-04-09 06:08:46 +0000231 ValueSymbolTable *ST = nullptr;
Chris Lattnercf835ff2007-02-15 20:01:43 +0000232 // If this value has a name, drop it.
233 if (hasName()) {
234 // Get the symtab this is in.
235 if (getSymTab(this, ST)) {
236 // We can't set a name on this value, but we need to clear V's name if
237 // it has one.
Daniel Dunbard786b512009-07-26 00:34:27 +0000238 if (V->hasName()) V->setName("");
Chris Lattnercf835ff2007-02-15 20:01:43 +0000239 return; // Cannot set a name on this value (e.g. constant).
240 }
Daniel Dunbar6058b512009-09-20 04:03:34 +0000241
Chris Lattnercf835ff2007-02-15 20:01:43 +0000242 // Remove old name.
243 if (ST)
244 ST->removeValueName(Name);
245 Name->Destroy();
Craig Topperc6207612014-04-09 06:08:46 +0000246 Name = nullptr;
Daniel Dunbar6058b512009-09-20 04:03:34 +0000247 }
248
Chris Lattnercf835ff2007-02-15 20:01:43 +0000249 // Now we know that this has no name.
Daniel Dunbar6058b512009-09-20 04:03:34 +0000250
Chris Lattnercf835ff2007-02-15 20:01:43 +0000251 // If V has no name either, we're done.
252 if (!V->hasName()) return;
Daniel Dunbar6058b512009-09-20 04:03:34 +0000253
Chris Lattnercf835ff2007-02-15 20:01:43 +0000254 // Get this's symtab if we didn't before.
255 if (!ST) {
256 if (getSymTab(this, ST)) {
257 // Clear V's name.
Daniel Dunbard786b512009-07-26 00:34:27 +0000258 V->setName("");
Chris Lattnercf835ff2007-02-15 20:01:43 +0000259 return; // Cannot set a name on this value (e.g. constant).
260 }
261 }
Daniel Dunbar6058b512009-09-20 04:03:34 +0000262
Chris Lattnercf835ff2007-02-15 20:01:43 +0000263 // Get V's ST, this should always succed, because V has a name.
264 ValueSymbolTable *VST;
265 bool Failure = getSymTab(V, VST);
Jeffrey Yasskin9b43f332010-12-23 00:58:24 +0000266 assert(!Failure && "V has a name, so it should have a ST!"); (void)Failure;
Daniel Dunbar6058b512009-09-20 04:03:34 +0000267
Chris Lattnercf835ff2007-02-15 20:01:43 +0000268 // If these values are both in the same symtab, we can do this very fast.
269 // This works even if both values have no symtab yet.
270 if (ST == VST) {
271 // Take the name!
272 Name = V->Name;
Craig Topperc6207612014-04-09 06:08:46 +0000273 V->Name = nullptr;
Chris Lattnercf835ff2007-02-15 20:01:43 +0000274 Name->setValue(this);
Chris Lattnercba18e32007-02-11 01:04:09 +0000275 return;
276 }
Daniel Dunbar6058b512009-09-20 04:03:34 +0000277
Chris Lattnercf835ff2007-02-15 20:01:43 +0000278 // Otherwise, things are slightly more complex. Remove V's name from VST and
279 // then reinsert it into ST.
Daniel Dunbar6058b512009-09-20 04:03:34 +0000280
Chris Lattnercf835ff2007-02-15 20:01:43 +0000281 if (VST)
282 VST->removeValueName(V->Name);
283 Name = V->Name;
Craig Topperc6207612014-04-09 06:08:46 +0000284 V->Name = nullptr;
Chris Lattnercf835ff2007-02-15 20:01:43 +0000285 Name->setValue(this);
Daniel Dunbar6058b512009-09-20 04:03:34 +0000286
Chris Lattnercf835ff2007-02-15 20:01:43 +0000287 if (ST)
288 ST->reinsertValue(this);
Chris Lattnerb6250822007-02-11 00:37:27 +0000289}
290
Rafael Espindola7e2b7562014-05-13 01:23:21 +0000291#ifndef NDEBUG
Craig Topper71b7b682014-08-21 05:55:13 +0000292static bool contains(SmallPtrSetImpl<ConstantExpr *> &Cache, ConstantExpr *Expr,
Rafael Espindola7e2b7562014-05-13 01:23:21 +0000293 Constant *C) {
294 if (!Cache.insert(Expr))
295 return false;
296
297 for (auto &O : Expr->operands()) {
298 if (O == C)
299 return true;
300 auto *CE = dyn_cast<ConstantExpr>(O);
301 if (!CE)
302 continue;
303 if (contains(Cache, CE, C))
304 return true;
305 }
306 return false;
307}
308
309static bool contains(Value *Expr, Value *V) {
310 if (Expr == V)
311 return true;
312
313 auto *C = dyn_cast<Constant>(V);
314 if (!C)
315 return false;
316
317 auto *CE = dyn_cast<ConstantExpr>(Expr);
318 if (!CE)
319 return false;
320
321 SmallPtrSet<ConstantExpr *, 4> Cache;
322 return contains(Cache, CE, C);
323}
324#endif
Chris Lattnerb6250822007-02-11 00:37:27 +0000325
Chris Lattneraf1783f2011-07-15 06:18:52 +0000326void Value::replaceAllUsesWith(Value *New) {
327 assert(New && "Value::replaceAllUsesWith(<null>) is invalid!");
Rafael Espindola7e2b7562014-05-13 01:23:21 +0000328 assert(!contains(New, this) &&
329 "this->replaceAllUsesWith(expr(this)) is NOT valid!");
Chris Lattneraf1783f2011-07-15 06:18:52 +0000330 assert(New->getType() == getType() &&
331 "replaceAllUses of value with new value of different type!");
332
Chris Lattner90234f32009-03-31 22:11:05 +0000333 // Notify all ValueHandles (if present) that this value is going away.
334 if (HasValueHandle)
335 ValueHandleBase::ValueIsRAUWd(this, New);
Michael Ilseman516d7032013-03-01 18:48:54 +0000336
Chris Lattner4947e672005-02-01 01:24:21 +0000337 while (!use_empty()) {
Gabor Greif715b9d22008-09-19 15:13:20 +0000338 Use &U = *UseList;
Chris Lattner9f158122003-08-29 05:09:37 +0000339 // Must handle Constants specially, we cannot call replaceUsesOfWith on a
Chris Lattner8e5b2c22007-08-21 00:21:07 +0000340 // constant because they are uniqued.
Rafael Espindola6b238632014-05-16 19:35:39 +0000341 if (auto *C = dyn_cast<Constant>(U.getUser())) {
Chris Lattner8e5b2c22007-08-21 00:21:07 +0000342 if (!isa<GlobalValue>(C)) {
Chris Lattner7a1450d2005-10-04 18:13:04 +0000343 C->replaceUsesOfWithOnConstant(this, New, &U);
Chris Lattner8e5b2c22007-08-21 00:21:07 +0000344 continue;
345 }
Chris Lattner9f158122003-08-29 05:09:37 +0000346 }
Michael Ilseman516d7032013-03-01 18:48:54 +0000347
Chris Lattner8e5b2c22007-08-21 00:21:07 +0000348 U.set(New);
Chris Lattner9f158122003-08-29 05:09:37 +0000349 }
Michael Ilseman516d7032013-03-01 18:48:54 +0000350
Jay Foad61ea0e42011-06-23 09:09:15 +0000351 if (BasicBlock *BB = dyn_cast<BasicBlock>(this))
352 BB->replaceSuccessorsPhiUsesWith(cast<BasicBlock>(New));
Chris Lattner9f158122003-08-29 05:09:37 +0000353}
354
Chandler Carruth97f6f032012-03-10 08:39:09 +0000355namespace {
356// Various metrics for how much to strip off of pointers.
357enum PointerStripKind {
358 PSK_ZeroIndices,
Rafael Espindolac229a4f2013-05-06 01:48:55 +0000359 PSK_ZeroIndicesAndAliases,
Chandler Carruth4d1d34f2012-03-14 23:19:53 +0000360 PSK_InBoundsConstantIndices,
361 PSK_InBounds
Chandler Carruth97f6f032012-03-10 08:39:09 +0000362};
363
364template <PointerStripKind StripKind>
365static Value *stripPointerCastsAndOffsets(Value *V) {
366 if (!V->getType()->isPointerTy())
367 return V;
Dan Gohman7c34ece2010-06-28 21:16:52 +0000368
369 // Even though we don't look through PHI nodes, we could be called on an
370 // instruction in an unreachable block, which may be on a cycle.
371 SmallPtrSet<Value *, 4> Visited;
372
Dan Gohman7c34ece2010-06-28 21:16:52 +0000373 Visited.insert(V);
Duncan Sandse59fa782008-12-29 21:06:19 +0000374 do {
Dan Gohmane1019db2009-07-17 23:55:56 +0000375 if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
Chandler Carruth97f6f032012-03-10 08:39:09 +0000376 switch (StripKind) {
Rafael Espindolac229a4f2013-05-06 01:48:55 +0000377 case PSK_ZeroIndicesAndAliases:
Chandler Carruth97f6f032012-03-10 08:39:09 +0000378 case PSK_ZeroIndices:
379 if (!GEP->hasAllZeroIndices())
380 return V;
381 break;
Chandler Carruth4d1d34f2012-03-14 23:19:53 +0000382 case PSK_InBoundsConstantIndices:
Chandler Carruth97f6f032012-03-10 08:39:09 +0000383 if (!GEP->hasAllConstantIndices())
384 return V;
Chandler Carruth4d1d34f2012-03-14 23:19:53 +0000385 // fallthrough
Chandler Carruth97f6f032012-03-10 08:39:09 +0000386 case PSK_InBounds:
387 if (!GEP->isInBounds())
388 return V;
389 break;
Chandler Carruth97f6f032012-03-10 08:39:09 +0000390 }
Dan Gohmane1019db2009-07-17 23:55:56 +0000391 V = GEP->getPointerOperand();
Matt Arsenaultb03bd4d2013-11-15 01:34:59 +0000392 } else if (Operator::getOpcode(V) == Instruction::BitCast ||
393 Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
Dan Gohmane1019db2009-07-17 23:55:56 +0000394 V = cast<Operator>(V)->getOperand(0);
Dan Gohman4ce5ade2009-08-27 17:55:13 +0000395 } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
Rafael Espindolac229a4f2013-05-06 01:48:55 +0000396 if (StripKind == PSK_ZeroIndices || GA->mayBeOverridden())
Dan Gohman4ce5ade2009-08-27 17:55:13 +0000397 return V;
398 V = GA->getAliasee();
Duncan Sandse59fa782008-12-29 21:06:19 +0000399 } else {
400 return V;
Anton Korobeynikovfc2edad2008-05-07 22:54:15 +0000401 }
Duncan Sands19d0b472010-02-16 11:11:14 +0000402 assert(V->getType()->isPointerTy() && "Unexpected operand type!");
Dan Gohman7c34ece2010-06-28 21:16:52 +0000403 } while (Visited.insert(V));
404
405 return V;
Anton Korobeynikovfc2edad2008-05-07 22:54:15 +0000406}
Chandler Carruth97f6f032012-03-10 08:39:09 +0000407} // namespace
408
409Value *Value::stripPointerCasts() {
Rafael Espindolac229a4f2013-05-06 01:48:55 +0000410 return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndAliases>(this);
411}
412
413Value *Value::stripPointerCastsNoFollowAliases() {
Chandler Carruth97f6f032012-03-10 08:39:09 +0000414 return stripPointerCastsAndOffsets<PSK_ZeroIndices>(this);
415}
416
Chandler Carruth4d1d34f2012-03-14 23:19:53 +0000417Value *Value::stripInBoundsConstantOffsets() {
418 return stripPointerCastsAndOffsets<PSK_InBoundsConstantIndices>(this);
Chandler Carruth97f6f032012-03-10 08:39:09 +0000419}
420
Chandler Carruth989e6302013-08-22 11:25:11 +0000421Value *Value::stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL,
422 APInt &Offset) {
423 if (!getType()->isPointerTy())
424 return this;
425
426 assert(Offset.getBitWidth() == DL.getPointerSizeInBits(cast<PointerType>(
427 getType())->getAddressSpace()) &&
428 "The offset must have exactly as many bits as our pointer.");
429
430 // Even though we don't look through PHI nodes, we could be called on an
431 // instruction in an unreachable block, which may be on a cycle.
432 SmallPtrSet<Value *, 4> Visited;
433 Visited.insert(this);
434 Value *V = this;
435 do {
436 if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
437 if (!GEP->isInBounds())
438 return V;
Chandler Carruthba689b32013-08-25 10:46:39 +0000439 APInt GEPOffset(Offset);
440 if (!GEP->accumulateConstantOffset(DL, GEPOffset))
Chandler Carruth989e6302013-08-22 11:25:11 +0000441 return V;
Chandler Carruthba689b32013-08-25 10:46:39 +0000442 Offset = GEPOffset;
Chandler Carruth989e6302013-08-22 11:25:11 +0000443 V = GEP->getPointerOperand();
Hal Finkelb8e7c732014-07-19 03:32:02 +0000444 } else if (Operator::getOpcode(V) == Instruction::BitCast ||
445 Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
Chandler Carruth989e6302013-08-22 11:25:11 +0000446 V = cast<Operator>(V)->getOperand(0);
447 } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
448 V = GA->getAliasee();
449 } else {
450 return V;
451 }
452 assert(V->getType()->isPointerTy() && "Unexpected operand type!");
453 } while (Visited.insert(V));
454
455 return V;
456}
457
Chandler Carruth97f6f032012-03-10 08:39:09 +0000458Value *Value::stripInBoundsOffsets() {
459 return stripPointerCastsAndOffsets<PSK_InBounds>(this);
460}
Anton Korobeynikovfc2edad2008-05-07 22:54:15 +0000461
Duncan P. N. Exon Smithfcece4d2014-10-15 20:28:31 +0000462/// \brief Check if Value is always a dereferenceable pointer.
463///
464/// Test if V is always a pointer to allocated and suitably aligned memory for
465/// a simple load or store.
Hal Finkel2e42c342014-07-10 05:27:53 +0000466static bool isDereferenceablePointer(const Value *V, const DataLayout *DL,
Craig Topper71b7b682014-08-21 05:55:13 +0000467 SmallPtrSetImpl<const Value *> &Visited) {
Dan Gohmana826a882010-11-11 21:23:25 +0000468 // Note that it is not safe to speculate into a malloc'd region because
469 // malloc may return null.
Dan Gohmana826a882010-11-11 21:23:25 +0000470
471 // These are obviously ok.
Nick Lewyckyc31ceda2012-01-23 00:05:17 +0000472 if (isa<AllocaInst>(V)) return true;
Dan Gohmana826a882010-11-11 21:23:25 +0000473
Hal Finkel2e42c342014-07-10 05:27:53 +0000474 // It's not always safe to follow a bitcast, for example:
475 // bitcast i8* (alloca i8) to i32*
476 // would result in a 4-byte load from a 1-byte alloca. However,
477 // if we're casting from a pointer from a type of larger size
478 // to a type of smaller size (or the same size), and the alignment
479 // is at least as large as for the resulting pointer type, then
480 // we can look through the bitcast.
481 if (DL)
482 if (const BitCastInst* BC = dyn_cast<BitCastInst>(V)) {
483 Type *STy = BC->getSrcTy()->getPointerElementType(),
484 *DTy = BC->getDestTy()->getPointerElementType();
Hal Finkel66e23f12014-07-10 06:06:11 +0000485 if (STy->isSized() && DTy->isSized() &&
486 (DL->getTypeStoreSize(STy) >=
Hal Finkel2e42c342014-07-10 05:27:53 +0000487 DL->getTypeStoreSize(DTy)) &&
488 (DL->getABITypeAlignment(STy) >=
489 DL->getABITypeAlignment(DTy)))
490 return isDereferenceablePointer(BC->getOperand(0), DL, Visited);
491 }
492
Dan Gohmana826a882010-11-11 21:23:25 +0000493 // Global variables which can't collapse to null are ok.
Nick Lewyckyc31ceda2012-01-23 00:05:17 +0000494 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
Dan Gohmana826a882010-11-11 21:23:25 +0000495 return !GV->hasExternalWeakLinkage();
496
Hal Finkelb0407ba2014-07-18 15:51:28 +0000497 // byval arguments are okay. Arguments specifically marked as
498 // dereferenceable are okay too.
499 if (const Argument *A = dyn_cast<Argument>(V)) {
500 if (A->hasByValAttr())
501 return true;
502 else if (uint64_t Bytes = A->getDereferenceableBytes()) {
503 Type *Ty = V->getType()->getPointerElementType();
504 if (Ty->isSized() && DL && DL->getTypeStoreSize(Ty) <= Bytes)
505 return true;
506 }
507
508 return false;
509 }
510
511 // Return values from call sites specifically marked as dereferenceable are
512 // also okay.
513 if (ImmutableCallSite CS = V) {
514 if (uint64_t Bytes = CS.getDereferenceableBytes(0)) {
515 Type *Ty = V->getType()->getPointerElementType();
516 if (Ty->isSized() && DL && DL->getTypeStoreSize(Ty) <= Bytes)
517 return true;
518 }
519 }
Nick Lewyckyc31ceda2012-01-23 00:05:17 +0000520
Dan Gohmana826a882010-11-11 21:23:25 +0000521 // For GEPs, determine if the indexing lands within the allocated object.
Nick Lewyckyc31ceda2012-01-23 00:05:17 +0000522 if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
Dan Gohmana826a882010-11-11 21:23:25 +0000523 // Conservatively require that the base pointer be fully dereferenceable.
Nick Lewyckyc31ceda2012-01-23 00:05:17 +0000524 if (!Visited.insert(GEP->getOperand(0)))
525 return false;
Hal Finkel2e42c342014-07-10 05:27:53 +0000526 if (!isDereferenceablePointer(GEP->getOperand(0), DL, Visited))
Dan Gohmana826a882010-11-11 21:23:25 +0000527 return false;
528 // Check the indices.
529 gep_type_iterator GTI = gep_type_begin(GEP);
530 for (User::const_op_iterator I = GEP->op_begin()+1,
531 E = GEP->op_end(); I != E; ++I) {
532 Value *Index = *I;
Chris Lattner229907c2011-07-18 04:54:35 +0000533 Type *Ty = *GTI++;
Dan Gohmana826a882010-11-11 21:23:25 +0000534 // Struct indices can't be out of bounds.
535 if (isa<StructType>(Ty))
536 continue;
537 ConstantInt *CI = dyn_cast<ConstantInt>(Index);
538 if (!CI)
539 return false;
540 // Zero is always ok.
541 if (CI->isZero())
542 continue;
543 // Check to see that it's within the bounds of an array.
Chris Lattner229907c2011-07-18 04:54:35 +0000544 ArrayType *ATy = dyn_cast<ArrayType>(Ty);
Dan Gohmana826a882010-11-11 21:23:25 +0000545 if (!ATy)
546 return false;
547 if (CI->getValue().getActiveBits() > 64)
548 return false;
549 if (CI->getZExtValue() >= ATy->getNumElements())
550 return false;
551 }
552 // Indices check out; this is dereferenceable.
553 return true;
554 }
555
Matt Arsenault199b39e2014-07-14 18:54:12 +0000556 if (const AddrSpaceCastInst *ASC = dyn_cast<AddrSpaceCastInst>(V))
557 return isDereferenceablePointer(ASC->getOperand(0), DL, Visited);
558
Dan Gohmana826a882010-11-11 21:23:25 +0000559 // If we don't know, assume the worst.
560 return false;
561}
562
Hal Finkel2e42c342014-07-10 05:27:53 +0000563bool Value::isDereferenceablePointer(const DataLayout *DL) const {
Hal Finkel9e440c02014-07-19 03:25:16 +0000564 // When dereferenceability information is provided by a dereferenceable
565 // attribute, we know exactly how many bytes are dereferenceable. If we can
566 // determine the exact offset to the attributed variable, we can use that
567 // information here.
568 Type *Ty = getType()->getPointerElementType();
569 if (Ty->isSized() && DL) {
570 APInt Offset(DL->getTypeStoreSizeInBits(getType()), 0);
571 const Value *BV = stripAndAccumulateInBoundsConstantOffsets(*DL, Offset);
572
573 APInt DerefBytes(Offset.getBitWidth(), 0);
574 if (const Argument *A = dyn_cast<Argument>(BV))
575 DerefBytes = A->getDereferenceableBytes();
576 else if (ImmutableCallSite CS = BV)
577 DerefBytes = CS.getDereferenceableBytes(0);
578
579 if (DerefBytes.getBoolValue() && Offset.isNonNegative()) {
580 if (DerefBytes.uge(Offset + DL->getTypeStoreSize(Ty)))
581 return true;
582 }
583 }
584
Nick Lewyckyc31ceda2012-01-23 00:05:17 +0000585 SmallPtrSet<const Value *, 32> Visited;
Hal Finkel2e42c342014-07-10 05:27:53 +0000586 return ::isDereferenceablePointer(this, DL, Visited);
Nick Lewyckyc31ceda2012-01-23 00:05:17 +0000587}
588
Daniel Dunbar6058b512009-09-20 04:03:34 +0000589Value *Value::DoPHITranslation(const BasicBlock *CurBB,
Chris Lattner9c1b5022008-12-02 07:16:45 +0000590 const BasicBlock *PredBB) {
591 PHINode *PN = dyn_cast<PHINode>(this);
592 if (PN && PN->getParent() == CurBB)
593 return PN->getIncomingValueForBlock(PredBB);
594 return this;
595}
596
Owen Anderson47db9412009-07-22 00:24:57 +0000597LLVMContext &Value::getContext() const { return VTy->getContext(); }
598
Duncan P. N. Exon Smith3441ffe2014-08-01 23:28:49 +0000599void Value::reverseUseList() {
600 if (!UseList || !UseList->Next)
601 // No need to reverse 0 or 1 uses.
602 return;
603
604 Use *Head = UseList;
605 Use *Current = UseList->Next;
606 Head->Next = nullptr;
607 while (Current) {
608 Use *Next = Current->Next;
609 Current->Next = Head;
610 Head->setPrev(&Current->Next);
611 Head = Current;
612 Current = Next;
613 }
614 UseList = Head;
615 Head->setPrev(&UseList);
616}
617
Chris Lattner90234f32009-03-31 22:11:05 +0000618//===----------------------------------------------------------------------===//
619// ValueHandleBase Class
620//===----------------------------------------------------------------------===//
621
Chris Lattner90234f32009-03-31 22:11:05 +0000622void ValueHandleBase::AddToExistingUseList(ValueHandleBase **List) {
623 assert(List && "Handle list is null?");
Daniel Dunbar6058b512009-09-20 04:03:34 +0000624
Chris Lattner90234f32009-03-31 22:11:05 +0000625 // Splice ourselves into the list.
626 Next = *List;
627 *List = this;
628 setPrevPtr(List);
629 if (Next) {
630 Next->setPrevPtr(&Next);
Bill Wendling9b2503a2012-04-08 10:16:43 +0000631 assert(VP.getPointer() == Next->VP.getPointer() && "Added to wrong list?");
Chris Lattner90234f32009-03-31 22:11:05 +0000632 }
633}
634
Jeffrey Yasskin406ac812009-10-12 17:43:32 +0000635void ValueHandleBase::AddToExistingUseListAfter(ValueHandleBase *List) {
636 assert(List && "Must insert after existing node");
637
638 Next = List->Next;
639 setPrevPtr(&List->Next);
640 List->Next = this;
641 if (Next)
642 Next->setPrevPtr(&Next);
643}
644
Chris Lattner90234f32009-03-31 22:11:05 +0000645void ValueHandleBase::AddToUseList() {
Bill Wendling9b2503a2012-04-08 10:16:43 +0000646 assert(VP.getPointer() && "Null pointer doesn't have a use list!");
Daniel Dunbar6058b512009-09-20 04:03:34 +0000647
Bill Wendling9b2503a2012-04-08 10:16:43 +0000648 LLVMContextImpl *pImpl = VP.getPointer()->getContext().pImpl;
Daniel Dunbar6058b512009-09-20 04:03:34 +0000649
Bill Wendling9b2503a2012-04-08 10:16:43 +0000650 if (VP.getPointer()->HasValueHandle) {
Chris Lattner90234f32009-03-31 22:11:05 +0000651 // If this value already has a ValueHandle, then it must be in the
652 // ValueHandles map already.
Bill Wendling9b2503a2012-04-08 10:16:43 +0000653 ValueHandleBase *&Entry = pImpl->ValueHandles[VP.getPointer()];
Craig Topper2617dcc2014-04-15 06:32:26 +0000654 assert(Entry && "Value doesn't have any handles?");
Owen Anderson4b660a82009-06-17 17:36:57 +0000655 AddToExistingUseList(&Entry);
Owen Anderson4b660a82009-06-17 17:36:57 +0000656 return;
Chris Lattner90234f32009-03-31 22:11:05 +0000657 }
Daniel Dunbar6058b512009-09-20 04:03:34 +0000658
Chris Lattner90234f32009-03-31 22:11:05 +0000659 // Ok, it doesn't have any handles yet, so we must insert it into the
660 // DenseMap. However, doing this insertion could cause the DenseMap to
661 // reallocate itself, which would invalidate all of the PrevP pointers that
662 // point into the old table. Handle this by checking for reallocation and
663 // updating the stale pointers only if needed.
Owen Andersone8f21852009-08-18 18:28:58 +0000664 DenseMap<Value*, ValueHandleBase*> &Handles = pImpl->ValueHandles;
Chris Lattner90234f32009-03-31 22:11:05 +0000665 const void *OldBucketPtr = Handles.getPointerIntoBucketsArray();
Daniel Dunbar6058b512009-09-20 04:03:34 +0000666
Bill Wendling9b2503a2012-04-08 10:16:43 +0000667 ValueHandleBase *&Entry = Handles[VP.getPointer()];
Craig Topper2617dcc2014-04-15 06:32:26 +0000668 assert(!Entry && "Value really did already have handles?");
Chris Lattner90234f32009-03-31 22:11:05 +0000669 AddToExistingUseList(&Entry);
Bill Wendling9b2503a2012-04-08 10:16:43 +0000670 VP.getPointer()->HasValueHandle = true;
Daniel Dunbar6058b512009-09-20 04:03:34 +0000671
Chris Lattner90234f32009-03-31 22:11:05 +0000672 // If reallocation didn't happen or if this was the first insertion, don't
673 // walk the table.
Daniel Dunbar6058b512009-09-20 04:03:34 +0000674 if (Handles.isPointerIntoBucketsArray(OldBucketPtr) ||
Owen Anderson4b660a82009-06-17 17:36:57 +0000675 Handles.size() == 1) {
Chris Lattner90234f32009-03-31 22:11:05 +0000676 return;
Owen Anderson4b660a82009-06-17 17:36:57 +0000677 }
Daniel Dunbar6058b512009-09-20 04:03:34 +0000678
Chris Lattner90234f32009-03-31 22:11:05 +0000679 // Okay, reallocation did happen. Fix the Prev Pointers.
Owen Andersone8f21852009-08-18 18:28:58 +0000680 for (DenseMap<Value*, ValueHandleBase*>::iterator I = Handles.begin(),
681 E = Handles.end(); I != E; ++I) {
Bill Wendling9b2503a2012-04-08 10:16:43 +0000682 assert(I->second && I->first == I->second->VP.getPointer() &&
683 "List invariant broken!");
Chris Lattner90234f32009-03-31 22:11:05 +0000684 I->second->setPrevPtr(&I->second);
685 }
686}
687
Chris Lattner90234f32009-03-31 22:11:05 +0000688void ValueHandleBase::RemoveFromUseList() {
Bill Wendling9b2503a2012-04-08 10:16:43 +0000689 assert(VP.getPointer() && VP.getPointer()->HasValueHandle &&
690 "Pointer doesn't have a use list!");
Chris Lattner90234f32009-03-31 22:11:05 +0000691
692 // Unlink this from its use list.
693 ValueHandleBase **PrevPtr = getPrevPtr();
694 assert(*PrevPtr == this && "List invariant broken");
Daniel Dunbar6058b512009-09-20 04:03:34 +0000695
Chris Lattner90234f32009-03-31 22:11:05 +0000696 *PrevPtr = Next;
697 if (Next) {
698 assert(Next->getPrevPtr() == &Next && "List invariant broken");
699 Next->setPrevPtr(PrevPtr);
700 return;
701 }
Daniel Dunbar6058b512009-09-20 04:03:34 +0000702
Chris Lattner90234f32009-03-31 22:11:05 +0000703 // If the Next pointer was null, then it is possible that this was the last
704 // ValueHandle watching VP. If so, delete its entry from the ValueHandles
705 // map.
Bill Wendling9b2503a2012-04-08 10:16:43 +0000706 LLVMContextImpl *pImpl = VP.getPointer()->getContext().pImpl;
Owen Andersone8f21852009-08-18 18:28:58 +0000707 DenseMap<Value*, ValueHandleBase*> &Handles = pImpl->ValueHandles;
Chris Lattner90234f32009-03-31 22:11:05 +0000708 if (Handles.isPointerIntoBucketsArray(PrevPtr)) {
Bill Wendling9b2503a2012-04-08 10:16:43 +0000709 Handles.erase(VP.getPointer());
710 VP.getPointer()->HasValueHandle = false;
Chris Lattner90234f32009-03-31 22:11:05 +0000711 }
712}
713
714
715void ValueHandleBase::ValueIsDeleted(Value *V) {
716 assert(V->HasValueHandle && "Should only be called if ValueHandles present");
717
718 // Get the linked list base, which is guaranteed to exist since the
719 // HasValueHandle flag is set.
Owen Andersone8f21852009-08-18 18:28:58 +0000720 LLVMContextImpl *pImpl = V->getContext().pImpl;
721 ValueHandleBase *Entry = pImpl->ValueHandles[V];
Chris Lattner90234f32009-03-31 22:11:05 +0000722 assert(Entry && "Value bit set but no entries exist");
Daniel Dunbar6058b512009-09-20 04:03:34 +0000723
Duncan Sands3bc93c22010-07-24 12:09:22 +0000724 // We use a local ValueHandleBase as an iterator so that ValueHandles can add
725 // and remove themselves from the list without breaking our iteration. This
726 // is not really an AssertingVH; we just have to give ValueHandleBase a kind.
727 // Note that we deliberately do not the support the case when dropping a value
728 // handle results in a new value handle being permanently added to the list
729 // (as might occur in theory for CallbackVH's): the new value handle will not
Duncan Sandsfd5c8322010-07-27 06:53:14 +0000730 // be processed and the checking code will mete out righteous punishment if
Duncan Sands3bc93c22010-07-24 12:09:22 +0000731 // the handle is still present once we have finished processing all the other
732 // value handles (it is fine to momentarily add then remove a value handle).
Jeffrey Yasskin406ac812009-10-12 17:43:32 +0000733 for (ValueHandleBase Iterator(Assert, *Entry); Entry; Entry = Iterator.Next) {
734 Iterator.RemoveFromUseList();
735 Iterator.AddToExistingUseListAfter(Entry);
736 assert(Entry->Next == &Iterator && "Loop invariant broken.");
Daniel Dunbar6058b512009-09-20 04:03:34 +0000737
Jeffrey Yasskin406ac812009-10-12 17:43:32 +0000738 switch (Entry->getKind()) {
Chris Lattner90234f32009-03-31 22:11:05 +0000739 case Assert:
Jeffrey Yasskin406ac812009-10-12 17:43:32 +0000740 break;
Daniel Dunbar70d4fb02009-09-22 02:02:33 +0000741 case Tracking:
742 // Mark that this value has been deleted by setting it to an invalid Value
743 // pointer.
Jeffrey Yasskin406ac812009-10-12 17:43:32 +0000744 Entry->operator=(DenseMapInfo<Value *>::getTombstoneKey());
Daniel Dunbar70d4fb02009-09-22 02:02:33 +0000745 break;
Chris Lattner90234f32009-03-31 22:11:05 +0000746 case Weak:
747 // Weak just goes to null, which will unlink it from the list.
Craig Topperc6207612014-04-09 06:08:46 +0000748 Entry->operator=(nullptr);
Chris Lattner90234f32009-03-31 22:11:05 +0000749 break;
750 case Callback:
Dan Gohman745ad442009-05-02 21:10:48 +0000751 // Forward to the subclass's implementation.
Jeffrey Yasskin406ac812009-10-12 17:43:32 +0000752 static_cast<CallbackVH*>(Entry)->deleted();
Dan Gohman745ad442009-05-02 21:10:48 +0000753 break;
Chris Lattner90234f32009-03-31 22:11:05 +0000754 }
755 }
Daniel Dunbar6058b512009-09-20 04:03:34 +0000756
Jeffrey Yasskin406ac812009-10-12 17:43:32 +0000757 // All callbacks, weak references, and assertingVHs should be dropped by now.
758 if (V->HasValueHandle) {
759#ifndef NDEBUG // Only in +Asserts mode...
Benjamin Kramer1f97a5a2011-11-15 16:27:03 +0000760 dbgs() << "While deleting: " << *V->getType() << " %" << V->getName()
Jeffrey Yasskin406ac812009-10-12 17:43:32 +0000761 << "\n";
762 if (pImpl->ValueHandles[V]->getKind() == Assert)
763 llvm_unreachable("An asserting value handle still pointed to this"
764 " value!");
765
766#endif
767 llvm_unreachable("All references to V were not removed?");
768 }
Chris Lattner90234f32009-03-31 22:11:05 +0000769}
770
771
772void ValueHandleBase::ValueIsRAUWd(Value *Old, Value *New) {
773 assert(Old->HasValueHandle &&"Should only be called if ValueHandles present");
774 assert(Old != New && "Changing value into itself!");
Daniel Dunbar6058b512009-09-20 04:03:34 +0000775
Chris Lattner90234f32009-03-31 22:11:05 +0000776 // Get the linked list base, which is guaranteed to exist since the
777 // HasValueHandle flag is set.
Owen Andersone8f21852009-08-18 18:28:58 +0000778 LLVMContextImpl *pImpl = Old->getContext().pImpl;
779 ValueHandleBase *Entry = pImpl->ValueHandles[Old];
780
Chris Lattner90234f32009-03-31 22:11:05 +0000781 assert(Entry && "Value bit set but no entries exist");
Daniel Dunbar6058b512009-09-20 04:03:34 +0000782
Jeffrey Yasskin406ac812009-10-12 17:43:32 +0000783 // We use a local ValueHandleBase as an iterator so that
784 // ValueHandles can add and remove themselves from the list without
785 // breaking our iteration. This is not really an AssertingVH; we
786 // just have to give ValueHandleBase some kind.
787 for (ValueHandleBase Iterator(Assert, *Entry); Entry; Entry = Iterator.Next) {
788 Iterator.RemoveFromUseList();
789 Iterator.AddToExistingUseListAfter(Entry);
790 assert(Entry->Next == &Iterator && "Loop invariant broken.");
Daniel Dunbar6058b512009-09-20 04:03:34 +0000791
Jeffrey Yasskin406ac812009-10-12 17:43:32 +0000792 switch (Entry->getKind()) {
Chris Lattner90234f32009-03-31 22:11:05 +0000793 case Assert:
794 // Asserting handle does not follow RAUW implicitly.
795 break;
Daniel Dunbar70d4fb02009-09-22 02:02:33 +0000796 case Tracking:
797 // Tracking goes to new value like a WeakVH. Note that this may make it
798 // something incompatible with its templated type. We don't want to have a
799 // virtual (or inline) interface to handle this though, so instead we make
Daniel Dunbar86707c92009-09-22 10:30:34 +0000800 // the TrackingVH accessors guarantee that a client never sees this value.
Daniel Dunbar70d4fb02009-09-22 02:02:33 +0000801
802 // FALLTHROUGH
Chris Lattner90234f32009-03-31 22:11:05 +0000803 case Weak:
804 // Weak goes to the new value, which will unlink it from Old's list.
Jeffrey Yasskin406ac812009-10-12 17:43:32 +0000805 Entry->operator=(New);
Chris Lattner90234f32009-03-31 22:11:05 +0000806 break;
807 case Callback:
Dan Gohman745ad442009-05-02 21:10:48 +0000808 // Forward to the subclass's implementation.
Jeffrey Yasskin406ac812009-10-12 17:43:32 +0000809 static_cast<CallbackVH*>(Entry)->allUsesReplacedWith(New);
Dan Gohman745ad442009-05-02 21:10:48 +0000810 break;
Chris Lattner90234f32009-03-31 22:11:05 +0000811 }
812 }
Duncan Sandsfd5c8322010-07-27 06:53:14 +0000813
814#ifndef NDEBUG
815 // If any new tracking or weak value handles were added while processing the
816 // list, then complain about it now.
817 if (Old->HasValueHandle)
818 for (Entry = pImpl->ValueHandles[Old]; Entry; Entry = Entry->Next)
819 switch (Entry->getKind()) {
820 case Tracking:
821 case Weak:
822 dbgs() << "After RAUW from " << *Old->getType() << " %"
Benjamin Kramer1f97a5a2011-11-15 16:27:03 +0000823 << Old->getName() << " to " << *New->getType() << " %"
824 << New->getName() << "\n";
Duncan Sandsfd5c8322010-07-27 06:53:14 +0000825 llvm_unreachable("A tracking or weak value handle still pointed to the"
826 " old value!\n");
827 default:
828 break;
829 }
830#endif
Chris Lattner90234f32009-03-31 22:11:05 +0000831}
832
Juergen Ributzkad12ccbd2013-11-19 00:57:56 +0000833// Pin the vtable to this file.
834void CallbackVH::anchor() {}