1009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner//===-- Value.cpp - Implement the Value class -----------------------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 10722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner// This file implements the Value, ValueHandle, and User classes. 11009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 12009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner//===----------------------------------------------------------------------===// 13009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 140b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Value.h" 154d919438898d542850449235da7f6dc55e6ca152Owen Anderson#include "LLVMContextImpl.h" 16d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/DenseMap.h" 17d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallString.h" 180b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constant.h" 190b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 20cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/IR/DataLayout.h" 210b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DerivedTypes.h" 2236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/GetElementPtrTypeIterator.h" 230b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/InstrTypes.h" 240b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 2536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/LeakDetector.h" 260b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 270b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Operator.h" 2836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/ValueHandle.h" 290b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/ValueSymbolTable.h" 302e3def1177c462e14b20ddad71adf5c6b7c3e867Bill Wendling#include "llvm/Support/Debug.h" 31ab7c09b6b6f4516a631fd6788918c237c83939afTorok Edwin#include "llvm/Support/ErrorHandling.h" 32722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner#include "llvm/Support/ManagedStatic.h" 33009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner#include <algorithm> 3431f8499e83dc4dccbb57ea7e76d1fd49b7010d0cChris Lattnerusing namespace llvm; 35d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 36009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner//===----------------------------------------------------------------------===// 37009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// Value Class 38009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner//===----------------------------------------------------------------------===// 39009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 40db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattnerstatic inline Type *checkType(Type *Ty) { 4182d18aa0e42a4858c2cb7c15934cc3e567432490Chris Lattner assert(Ty && "Value defined with a null type: Error!"); 42cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return Ty; 4382d18aa0e42a4858c2cb7c15934cc3e567432490Chris Lattner} 4482d18aa0e42a4858c2cb7c15934cc3e567432490Chris Lattner 45db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris LattnerValue::Value(Type *ty, unsigned scid) 46cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines : VTy(checkType(ty)), UseList(nullptr), Name(nullptr), SubclassID(scid), 47cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines HasValueHandle(0), SubclassOptionalData(0), SubclassData(0) { 481afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner // FIXME: Why isn't this in the subclass gunk?? 49488fdce9821a06732631aececa351ad75a224b19Richard Smith // Note, we cannot call isa<CallInst> before the CallInst has been 50488fdce9821a06732631aececa351ad75a224b19Richard Smith // constructed. 51488fdce9821a06732631aececa351ad75a224b19Richard Smith if (SubclassID == Instruction::Call || SubclassID == Instruction::Invoke) 521afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner assert((VTy->isFirstClassType() || VTy->isVoidTy() || VTy->isStructTy()) && 531afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner "invalid CallInst type!"); 54488fdce9821a06732631aececa351ad75a224b19Richard Smith else if (SubclassID != BasicBlockVal && 55488fdce9821a06732631aececa351ad75a224b19Richard Smith (SubclassID < ConstantFirstVal || SubclassID > ConstantLastVal)) 561afcace3a3a138b1b18e5c6270caa8dae2261ae2Chris Lattner assert((VTy->isFirstClassType() || VTy->isVoidTy()) && 57a9e7781b3b8e457946491529816feab73c66d774Chris Lattner "Cannot create non-first-class values except for constants!"); 58009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 59009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 60afba8fe662d65b25b4baf46bb26cc18e1f9cc0a5Gordon HenriksenValue::~Value() { 61722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // Notify all ValueHandles (if present) that this value is going away. 62722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner if (HasValueHandle) 63722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner ValueHandleBase::ValueIsDeleted(this); 64ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 65009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner#ifndef NDEBUG // Only in -g mode... 66ee976f33713016a96e3fbb394b7d0c5465be25d7Chris Lattner // Check to make sure that there are no uses of this value that are still 67ee976f33713016a96e3fbb394b7d0c5465be25d7Chris Lattner // around when the value is destroyed. If there are, then we have a dangling 68ee976f33713016a96e3fbb394b7d0c5465be25d7Chris Lattner // reference and something is wrong. This code is here to print out what is 69fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman // still being referenced. The value in question should be printed as 70ee976f33713016a96e3fbb394b7d0c5465be25d7Chris Lattner // a <badref> 71ee976f33713016a96e3fbb394b7d0c5465be25d7Chris Lattner // 72afba8fe662d65b25b4baf46bb26cc18e1f9cc0a5Gordon Henriksen if (!use_empty()) { 73a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer dbgs() << "While deleting: " << *VTy << " %" << getName() << "\n"; 74afba8fe662d65b25b4baf46bb26cc18e1f9cc0a5Gordon Henriksen for (use_iterator I = use_begin(), E = use_end(); I != E; ++I) 756892c7a92d0d2132b8361f7324824a680d09134cDavid Greene dbgs() << "Use still stuck around after Def is destroyed:" 762e3def1177c462e14b20ddad71adf5c6b7c3e867Bill Wendling << **I << "\n"; 77009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner } 78009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner#endif 79afba8fe662d65b25b4baf46bb26cc18e1f9cc0a5Gordon Henriksen assert(use_empty() && "Uses remain when a value is destroyed!"); 804f95d2bda4235d36acd95688d0744d7363214706Chris Lattner 814f95d2bda4235d36acd95688d0744d7363214706Chris Lattner // If this value is named, destroy the name. This should not be in a symtab 824f95d2bda4235d36acd95688d0744d7363214706Chris Lattner // at this point. 833ecb447f52d169dea6663b95b5b5b43e9bb5826bBill Wendling if (Name && SubclassID != MDStringVal) 844f95d2bda4235d36acd95688d0744d7363214706Chris Lattner Name->Destroy(); 85ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 864f95d2bda4235d36acd95688d0744d7363214706Chris Lattner // There should be no uses of this object anymore, remove it. 874f95d2bda4235d36acd95688d0744d7363214706Chris Lattner LeakDetector::removeGarbageObject(this); 88009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 89009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 9029d1ca6c424df225b9fd48473f0d6419fdd44bd7Chris Lattner/// hasNUses - Return true if this Value has exactly N users. 9129d1ca6c424df225b9fd48473f0d6419fdd44bd7Chris Lattner/// 9229d1ca6c424df225b9fd48473f0d6419fdd44bd7Chris Lattnerbool Value::hasNUses(unsigned N) const { 9360ad781c61815ca5b8dc2a45a102e1c8af65992fGabor Greif const_use_iterator UI = use_begin(), E = use_end(); 9429d1ca6c424df225b9fd48473f0d6419fdd44bd7Chris Lattner 9529d1ca6c424df225b9fd48473f0d6419fdd44bd7Chris Lattner for (; N; --N, ++UI) 9629d1ca6c424df225b9fd48473f0d6419fdd44bd7Chris Lattner if (UI == E) return false; // Too few. 9729d1ca6c424df225b9fd48473f0d6419fdd44bd7Chris Lattner return UI == E; 9829d1ca6c424df225b9fd48473f0d6419fdd44bd7Chris Lattner} 9929d1ca6c424df225b9fd48473f0d6419fdd44bd7Chris Lattner 1008daf056c90c2590709090b0c27045e1a45803461Chris Lattner/// hasNUsesOrMore - Return true if this value has N users or more. This is 1018daf056c90c2590709090b0c27045e1a45803461Chris Lattner/// logically equivalent to getNumUses() >= N. 1028daf056c90c2590709090b0c27045e1a45803461Chris Lattner/// 1038daf056c90c2590709090b0c27045e1a45803461Chris Lattnerbool Value::hasNUsesOrMore(unsigned N) const { 10460ad781c61815ca5b8dc2a45a102e1c8af65992fGabor Greif const_use_iterator UI = use_begin(), E = use_end(); 1058daf056c90c2590709090b0c27045e1a45803461Chris Lattner 1068daf056c90c2590709090b0c27045e1a45803461Chris Lattner for (; N; --N, ++UI) 1078daf056c90c2590709090b0c27045e1a45803461Chris Lattner if (UI == E) return false; // Too few. 1088daf056c90c2590709090b0c27045e1a45803461Chris Lattner 1098daf056c90c2590709090b0c27045e1a45803461Chris Lattner return true; 1108daf056c90c2590709090b0c27045e1a45803461Chris Lattner} 1118daf056c90c2590709090b0c27045e1a45803461Chris Lattner 112502a4f5162498ec420e3cb22f667808d726dd7daEvan Cheng/// isUsedInBasicBlock - Return true if this value is used in the specified 113502a4f5162498ec420e3cb22f667808d726dd7daEvan Cheng/// basic block. 114c4f72dd6e759a170808ecfc6be784f8598367484Bill Wendlingbool Value::isUsedInBasicBlock(const BasicBlock *BB) const { 115a88d974ce274152d2f8f28660ba277906bde2384Jakob Stoklund Olesen // This can be computed either by scanning the instructions in BB, or by 116a88d974ce274152d2f8f28660ba277906bde2384Jakob Stoklund Olesen // scanning the use list of this Value. Both lists can be very long, but 117a88d974ce274152d2f8f28660ba277906bde2384Jakob Stoklund Olesen // usually one is quite short. 118a88d974ce274152d2f8f28660ba277906bde2384Jakob Stoklund Olesen // 119a88d974ce274152d2f8f28660ba277906bde2384Jakob Stoklund Olesen // Scan both lists simultaneously until one is exhausted. This limits the 120a88d974ce274152d2f8f28660ba277906bde2384Jakob Stoklund Olesen // search to the shorter list. 121a88d974ce274152d2f8f28660ba277906bde2384Jakob Stoklund Olesen BasicBlock::const_iterator BI = BB->begin(), BE = BB->end(); 12236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const_user_iterator UI = user_begin(), UE = user_end(); 123a88d974ce274152d2f8f28660ba277906bde2384Jakob Stoklund Olesen for (; BI != BE && UI != UE; ++BI, ++UI) { 124a88d974ce274152d2f8f28660ba277906bde2384Jakob Stoklund Olesen // Scan basic block: Check if this Value is used by the instruction at BI. 125a88d974ce274152d2f8f28660ba277906bde2384Jakob Stoklund Olesen if (std::find(BI->op_begin(), BI->op_end(), this) != BI->op_end()) 1264da7f90b1780e4d1ba38da64c849b9c2b1c67071Benjamin Kramer return true; 127a88d974ce274152d2f8f28660ba277906bde2384Jakob Stoklund Olesen // Scan use list: Check if the use at UI is in BB. 128a88d974ce274152d2f8f28660ba277906bde2384Jakob Stoklund Olesen const Instruction *User = dyn_cast<Instruction>(*UI); 129502a4f5162498ec420e3cb22f667808d726dd7daEvan Cheng if (User && User->getParent() == BB) 130502a4f5162498ec420e3cb22f667808d726dd7daEvan Cheng return true; 131502a4f5162498ec420e3cb22f667808d726dd7daEvan Cheng } 132502a4f5162498ec420e3cb22f667808d726dd7daEvan Cheng return false; 133502a4f5162498ec420e3cb22f667808d726dd7daEvan Cheng} 134502a4f5162498ec420e3cb22f667808d726dd7daEvan Cheng 1358daf056c90c2590709090b0c27045e1a45803461Chris Lattner 13629d1ca6c424df225b9fd48473f0d6419fdd44bd7Chris Lattner/// getNumUses - This method computes the number of uses of this Value. This 13729d1ca6c424df225b9fd48473f0d6419fdd44bd7Chris Lattner/// is a linear time operation. Use hasOneUse or hasNUses to check for specific 13829d1ca6c424df225b9fd48473f0d6419fdd44bd7Chris Lattner/// values. 13929d1ca6c424df225b9fd48473f0d6419fdd44bd7Chris Lattnerunsigned Value::getNumUses() const { 14029d1ca6c424df225b9fd48473f0d6419fdd44bd7Chris Lattner return (unsigned)std::distance(use_begin(), use_end()); 14129d1ca6c424df225b9fd48473f0d6419fdd44bd7Chris Lattner} 14229d1ca6c424df225b9fd48473f0d6419fdd44bd7Chris Lattner 1437216811ea22d68cbf8df092cda8e64e13e394ac8Chris Lattnerstatic bool getSymTab(Value *V, ValueSymbolTable *&ST) { 144dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ST = nullptr; 1457216811ea22d68cbf8df092cda8e64e13e394ac8Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) { 1460d1e40728d668085257b78657b381e1f13d77d52Chris Lattner if (BasicBlock *P = I->getParent()) 1470d1e40728d668085257b78657b381e1f13d77d52Chris Lattner if (Function *PP = P->getParent()) 14878d033e086e19e016273de014f9214aa6f3f844bReid Spencer ST = &PP->getValueSymbolTable(); 1497216811ea22d68cbf8df092cda8e64e13e394ac8Chris Lattner } else if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) { 150ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar if (Function *P = BB->getParent()) 151ef9b9a793949469cdaa4ab6d0173136229dcab7bReid Spencer ST = &P->getValueSymbolTable(); 1527216811ea22d68cbf8df092cda8e64e13e394ac8Chris Lattner } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 153ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar if (Module *P = GV->getParent()) 154ef9b9a793949469cdaa4ab6d0173136229dcab7bReid Spencer ST = &P->getValueSymbolTable(); 1557216811ea22d68cbf8df092cda8e64e13e394ac8Chris Lattner } else if (Argument *A = dyn_cast<Argument>(V)) { 156ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar if (Function *P = A->getParent()) 157ef9b9a793949469cdaa4ab6d0173136229dcab7bReid Spencer ST = &P->getValueSymbolTable(); 158e54abc90fe9942ef3902040a7ac475ce0c369dc9Devang Patel } else if (isa<MDString>(V)) 159e54abc90fe9942ef3902040a7ac475ce0c369dc9Devang Patel return true; 160e54abc90fe9942ef3902040a7ac475ce0c369dc9Devang Patel else { 1617216811ea22d68cbf8df092cda8e64e13e394ac8Chris Lattner assert(isa<Constant>(V) && "Unknown value type!"); 1627216811ea22d68cbf8df092cda8e64e13e394ac8Chris Lattner return true; // no name is setable for this. 1630d1e40728d668085257b78657b381e1f13d77d52Chris Lattner } 1647216811ea22d68cbf8df092cda8e64e13e394ac8Chris Lattner return false; 1657216811ea22d68cbf8df092cda8e64e13e394ac8Chris Lattner} 1667216811ea22d68cbf8df092cda8e64e13e394ac8Chris Lattner 167499027fb4826e25919f2ea154ca4db73842560afDaniel DunbarStringRef Value::getName() const { 1684fa4990bdcb1fc2aa7831b1e6b113998366b2918Daniel Dunbar // Make sure the empty string is still a C string. For historical reasons, 1694fa4990bdcb1fc2aa7831b1e6b113998366b2918Daniel Dunbar // some clients want to call .data() on the result and expect it to be null 1704fa4990bdcb1fc2aa7831b1e6b113998366b2918Daniel Dunbar // terminated. 1714fa4990bdcb1fc2aa7831b1e6b113998366b2918Daniel Dunbar if (!Name) return StringRef("", 0); 172499027fb4826e25919f2ea154ca4db73842560afDaniel Dunbar return Name->getKey(); 17371996e73d8050d2b8805b14a48ab635155b11a12Chris Lattner} 17471996e73d8050d2b8805b14a48ab635155b11a12Chris Lattner 1753f53fa9a51c4ce7ba81170ca7ab2e49bd37281b0Daniel Dunbarvoid Value::setName(const Twine &NewName) { 1763ecb447f52d169dea6663b95b5b5b43e9bb5826bBill Wendling assert(SubclassID != MDStringVal && 1773ecb447f52d169dea6663b95b5b5b43e9bb5826bBill Wendling "Cannot set the name of MDString with this method!"); 1783ecb447f52d169dea6663b95b5b5b43e9bb5826bBill Wendling 1795149932068f535e1ff13b91c9669f55718c60a07Daniel Dunbar // Fast path for common IRBuilder case of setName("") when there is no name. 1805149932068f535e1ff13b91c9669f55718c60a07Daniel Dunbar if (NewName.isTriviallyEmpty() && !hasName()) 1815149932068f535e1ff13b91c9669f55718c60a07Daniel Dunbar return; 1825149932068f535e1ff13b91c9669f55718c60a07Daniel Dunbar 183e476004b94582c64a0fabaa0e251a0f070909843Daniel Dunbar SmallString<256> NameData; 184b357e06f672996400343d38b08014a5b6a7d5b2dBenjamin Kramer StringRef NameRef = NewName.toStringRef(NameData); 18536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(NameRef.find_first_of(0) == StringRef::npos && 18636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "Null bytes are not allowed in names"); 187042ad36871d67a2db48bf41a8dbde3a5676fc96fChris Lattner 18807f6903cbefe268d7fbf7f17fc8c1cddae16db5aDaniel Dunbar // Name isn't changing? 189b357e06f672996400343d38b08014a5b6a7d5b2dBenjamin Kramer if (getName() == NameRef) 19007f6903cbefe268d7fbf7f17fc8c1cddae16db5aDaniel Dunbar return; 19107f6903cbefe268d7fbf7f17fc8c1cddae16db5aDaniel Dunbar 192f012705c7e4ca8cf90b6b734ce1d5355daca5ba5Benjamin Kramer assert(!getType()->isVoidTy() && "Cannot assign a name to void values!"); 193ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 1947216811ea22d68cbf8df092cda8e64e13e394ac8Chris Lattner // Get the symbol table to update for this object. 1957216811ea22d68cbf8df092cda8e64e13e394ac8Chris Lattner ValueSymbolTable *ST; 1967216811ea22d68cbf8df092cda8e64e13e394ac8Chris Lattner if (getSymTab(this, ST)) 1977216811ea22d68cbf8df092cda8e64e13e394ac8Chris Lattner return; // Cannot set a name on this value (e.g. constant). 1980d1e40728d668085257b78657b381e1f13d77d52Chris Lattner 1994c8e74f0b75cb10820c45c86399fbd02e4a8832aMichael Ilseman if (Function *F = dyn_cast<Function>(this)) 2004c8e74f0b75cb10820c45c86399fbd02e4a8832aMichael Ilseman getContext().pImpl->IntrinsicIDCache.erase(F); 2014c8e74f0b75cb10820c45c86399fbd02e4a8832aMichael Ilseman 202dec628eead87b20773c98a00830580df211acc98Chris Lattner if (!ST) { // No symbol table to update? Just do the change. 203b357e06f672996400343d38b08014a5b6a7d5b2dBenjamin Kramer if (NameRef.empty()) { 204dec628eead87b20773c98a00830580df211acc98Chris Lattner // Free the name for this value. 205dec628eead87b20773c98a00830580df211acc98Chris Lattner Name->Destroy(); 206dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Name = nullptr; 207042ad36871d67a2db48bf41a8dbde3a5676fc96fChris Lattner return; 20804cb800c324ef661017aff474e266ed7f2cddb90Chris Lattner } 209ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 21007f6903cbefe268d7fbf7f17fc8c1cddae16db5aDaniel Dunbar if (Name) 211042ad36871d67a2db48bf41a8dbde3a5676fc96fChris Lattner Name->Destroy(); 212ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 213042ad36871d67a2db48bf41a8dbde3a5676fc96fChris Lattner // NOTE: Could optimize for the case the name is shrinking to not deallocate 214042ad36871d67a2db48bf41a8dbde3a5676fc96fChris Lattner // then reallocated. 215ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 216042ad36871d67a2db48bf41a8dbde3a5676fc96fChris Lattner // Create the new name. 217cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Name = ValueName::Create(NameRef); 218042ad36871d67a2db48bf41a8dbde3a5676fc96fChris Lattner Name->setValue(this); 219dec628eead87b20773c98a00830580df211acc98Chris Lattner return; 220dec628eead87b20773c98a00830580df211acc98Chris Lattner } 221ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 222dec628eead87b20773c98a00830580df211acc98Chris Lattner // NOTE: Could optimize for the case the name is shrinking to not deallocate 223dec628eead87b20773c98a00830580df211acc98Chris Lattner // then reallocated. 224dec628eead87b20773c98a00830580df211acc98Chris Lattner if (hasName()) { 225dec628eead87b20773c98a00830580df211acc98Chris Lattner // Remove old name. 226dec628eead87b20773c98a00830580df211acc98Chris Lattner ST->removeValueName(Name); 227dec628eead87b20773c98a00830580df211acc98Chris Lattner Name->Destroy(); 228dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Name = nullptr; 229dec628eead87b20773c98a00830580df211acc98Chris Lattner 230b357e06f672996400343d38b08014a5b6a7d5b2dBenjamin Kramer if (NameRef.empty()) 231042ad36871d67a2db48bf41a8dbde3a5676fc96fChris Lattner return; 23204cb800c324ef661017aff474e266ed7f2cddb90Chris Lattner } 233dec628eead87b20773c98a00830580df211acc98Chris Lattner 234dec628eead87b20773c98a00830580df211acc98Chris Lattner // Name is changing to something new. 235b357e06f672996400343d38b08014a5b6a7d5b2dBenjamin Kramer Name = ST->createValueName(NameRef, this); 2360d1e40728d668085257b78657b381e1f13d77d52Chris Lattner} 2370d1e40728d668085257b78657b381e1f13d77d52Chris Lattner 238042ad36871d67a2db48bf41a8dbde3a5676fc96fChris Lattner 2397216811ea22d68cbf8df092cda8e64e13e394ac8Chris Lattner/// takeName - transfer the name from V to this value, setting V's name to 240ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar/// empty. It is an error to call V->takeName(V). 2417216811ea22d68cbf8df092cda8e64e13e394ac8Chris Lattnervoid Value::takeName(Value *V) { 2423ecb447f52d169dea6663b95b5b5b43e9bb5826bBill Wendling assert(SubclassID != MDStringVal && "Cannot take the name of an MDString!"); 2433ecb447f52d169dea6663b95b5b5b43e9bb5826bBill Wendling 244dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ValueSymbolTable *ST = nullptr; 2450878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner // If this value has a name, drop it. 2460878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner if (hasName()) { 2470878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner // Get the symtab this is in. 2480878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner if (getSymTab(this, ST)) { 2490878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner // We can't set a name on this value, but we need to clear V's name if 2500878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner // it has one. 2513f53fa9a51c4ce7ba81170ca7ab2e49bd37281b0Daniel Dunbar if (V->hasName()) V->setName(""); 2520878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner return; // Cannot set a name on this value (e.g. constant). 2530878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner } 254ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 2550878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner // Remove old name. 2560878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner if (ST) 2570878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner ST->removeValueName(Name); 2580878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner Name->Destroy(); 259dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Name = nullptr; 260ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar } 261ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 2620878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner // Now we know that this has no name. 263ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 2640878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner // If V has no name either, we're done. 2650878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner if (!V->hasName()) return; 266ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 2670878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner // Get this's symtab if we didn't before. 2680878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner if (!ST) { 2690878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner if (getSymTab(this, ST)) { 2700878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner // Clear V's name. 2713f53fa9a51c4ce7ba81170ca7ab2e49bd37281b0Daniel Dunbar V->setName(""); 2720878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner return; // Cannot set a name on this value (e.g. constant). 2730878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner } 2740878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner } 275ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 2760878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner // Get V's ST, this should always succed, because V has a name. 2770878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner ValueSymbolTable *VST; 2780878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner bool Failure = getSymTab(V, VST); 2798e68c3873549ca31533e2e3e40dda3a43cb79566Jeffrey Yasskin assert(!Failure && "V has a name, so it should have a ST!"); (void)Failure; 280ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 2810878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner // If these values are both in the same symtab, we can do this very fast. 2820878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner // This works even if both values have no symtab yet. 2830878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner if (ST == VST) { 2840878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner // Take the name! 2850878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner Name = V->Name; 286dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines V->Name = nullptr; 2870878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner Name->setValue(this); 288f41916e75dc9c622fa81b91eb6a5e0a36fa13754Chris Lattner return; 289f41916e75dc9c622fa81b91eb6a5e0a36fa13754Chris Lattner } 290ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 2910878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner // Otherwise, things are slightly more complex. Remove V's name from VST and 2920878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner // then reinsert it into ST. 293ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 2940878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner if (VST) 2950878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner VST->removeValueName(V->Name); 2960878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner Name = V->Name; 297dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines V->Name = nullptr; 2980878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner Name->setValue(this); 299ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 3000878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner if (ST) 3010878c310596d564e75657bf3c771431b4ef7eea5Chris Lattner ST->reinsertValue(this); 3027216811ea22d68cbf8df092cda8e64e13e394ac8Chris Lattner} 3037216811ea22d68cbf8df092cda8e64e13e394ac8Chris Lattner 304dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#ifndef NDEBUG 305dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic bool contains(SmallPtrSet<ConstantExpr *, 4> &Cache, ConstantExpr *Expr, 306dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Constant *C) { 307dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Cache.insert(Expr)) 308dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return false; 309dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 310dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (auto &O : Expr->operands()) { 311dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (O == C) 312dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return true; 313dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto *CE = dyn_cast<ConstantExpr>(O); 314dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!CE) 315dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines continue; 316dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (contains(Cache, CE, C)) 317dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return true; 318dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 319dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return false; 320dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 321dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 322dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic bool contains(Value *Expr, Value *V) { 323dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Expr == V) 324dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return true; 325dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 326dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto *C = dyn_cast<Constant>(V); 327dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!C) 328dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return false; 329dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 330dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto *CE = dyn_cast<ConstantExpr>(Expr); 331dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!CE) 332dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return false; 333dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 334dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SmallPtrSet<ConstantExpr *, 4> Cache; 335dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return contains(Cache, CE, C); 336dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 337dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#endif 3387216811ea22d68cbf8df092cda8e64e13e394ac8Chris Lattner 339678f9e05c949bc565b736b0bb4337bffb0f3c687Chris Lattnervoid Value::replaceAllUsesWith(Value *New) { 340678f9e05c949bc565b736b0bb4337bffb0f3c687Chris Lattner assert(New && "Value::replaceAllUsesWith(<null>) is invalid!"); 341dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(!contains(New, this) && 342dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "this->replaceAllUsesWith(expr(this)) is NOT valid!"); 343678f9e05c949bc565b736b0bb4337bffb0f3c687Chris Lattner assert(New->getType() == getType() && 344678f9e05c949bc565b736b0bb4337bffb0f3c687Chris Lattner "replaceAllUses of value with new value of different type!"); 345678f9e05c949bc565b736b0bb4337bffb0f3c687Chris Lattner 346722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // Notify all ValueHandles (if present) that this value is going away. 347722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner if (HasValueHandle) 348722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner ValueHandleBase::ValueIsRAUWd(this, New); 3494c8e74f0b75cb10820c45c86399fbd02e4a8832aMichael Ilseman 35029d1ca6c424df225b9fd48473f0d6419fdd44bd7Chris Lattner while (!use_empty()) { 3516f4266506bca785828bacda55bd5db9172f990c6Gabor Greif Use &U = *UseList; 3522bc065b63a8377456ddbe149621b3daf15f052a4Chris Lattner // Must handle Constants specially, we cannot call replaceUsesOfWith on a 3532d691333acec66118ede55b6d7ec7a3083bc1e01Chris Lattner // constant because they are uniqued. 354dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (auto *C = dyn_cast<Constant>(U.getUser())) { 3552d691333acec66118ede55b6d7ec7a3083bc1e01Chris Lattner if (!isa<GlobalValue>(C)) { 356d0ff1adbdb4b7b565b7f8f191aac0731e80aa1efChris Lattner C->replaceUsesOfWithOnConstant(this, New, &U); 3572d691333acec66118ede55b6d7ec7a3083bc1e01Chris Lattner continue; 3582d691333acec66118ede55b6d7ec7a3083bc1e01Chris Lattner } 3592bc065b63a8377456ddbe149621b3daf15f052a4Chris Lattner } 3604c8e74f0b75cb10820c45c86399fbd02e4a8832aMichael Ilseman 3612d691333acec66118ede55b6d7ec7a3083bc1e01Chris Lattner U.set(New); 3622bc065b63a8377456ddbe149621b3daf15f052a4Chris Lattner } 3634c8e74f0b75cb10820c45c86399fbd02e4a8832aMichael Ilseman 36495c3e48f9557adb6064d580684bb14cacec2f826Jay Foad if (BasicBlock *BB = dyn_cast<BasicBlock>(this)) 36595c3e48f9557adb6064d580684bb14cacec2f826Jay Foad BB->replaceSuccessorsPhiUsesWith(cast<BasicBlock>(New)); 3662bc065b63a8377456ddbe149621b3daf15f052a4Chris Lattner} 3672bc065b63a8377456ddbe149621b3daf15f052a4Chris Lattner 36884dfc32ff906271c373819595e60a173624e1184Chandler Carruthnamespace { 36984dfc32ff906271c373819595e60a173624e1184Chandler Carruth// Various metrics for how much to strip off of pointers. 37084dfc32ff906271c373819595e60a173624e1184Chandler Carruthenum PointerStripKind { 37184dfc32ff906271c373819595e60a173624e1184Chandler Carruth PSK_ZeroIndices, 372eaf14786ca3975266ed7041ac242122c02baf1cfRafael Espindola PSK_ZeroIndicesAndAliases, 373274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth PSK_InBoundsConstantIndices, 374274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth PSK_InBounds 37584dfc32ff906271c373819595e60a173624e1184Chandler Carruth}; 37684dfc32ff906271c373819595e60a173624e1184Chandler Carruth 37784dfc32ff906271c373819595e60a173624e1184Chandler Carruthtemplate <PointerStripKind StripKind> 37884dfc32ff906271c373819595e60a173624e1184Chandler Carruthstatic Value *stripPointerCastsAndOffsets(Value *V) { 37984dfc32ff906271c373819595e60a173624e1184Chandler Carruth if (!V->getType()->isPointerTy()) 38084dfc32ff906271c373819595e60a173624e1184Chandler Carruth return V; 38150f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman 38250f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman // Even though we don't look through PHI nodes, we could be called on an 38350f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman // instruction in an unreachable block, which may be on a cycle. 38450f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman SmallPtrSet<Value *, 4> Visited; 38550f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman 38650f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman Visited.insert(V); 387f08bf1193c390bfe4b25d8533f146742d0277d06Duncan Sands do { 388016de81177ec5c950f1668be4a48992bc1ee0d75Dan Gohman if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 38984dfc32ff906271c373819595e60a173624e1184Chandler Carruth switch (StripKind) { 390eaf14786ca3975266ed7041ac242122c02baf1cfRafael Espindola case PSK_ZeroIndicesAndAliases: 39184dfc32ff906271c373819595e60a173624e1184Chandler Carruth case PSK_ZeroIndices: 39284dfc32ff906271c373819595e60a173624e1184Chandler Carruth if (!GEP->hasAllZeroIndices()) 39384dfc32ff906271c373819595e60a173624e1184Chandler Carruth return V; 39484dfc32ff906271c373819595e60a173624e1184Chandler Carruth break; 395274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth case PSK_InBoundsConstantIndices: 39684dfc32ff906271c373819595e60a173624e1184Chandler Carruth if (!GEP->hasAllConstantIndices()) 39784dfc32ff906271c373819595e60a173624e1184Chandler Carruth return V; 398274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth // fallthrough 39984dfc32ff906271c373819595e60a173624e1184Chandler Carruth case PSK_InBounds: 40084dfc32ff906271c373819595e60a173624e1184Chandler Carruth if (!GEP->isInBounds()) 40184dfc32ff906271c373819595e60a173624e1184Chandler Carruth return V; 40284dfc32ff906271c373819595e60a173624e1184Chandler Carruth break; 40384dfc32ff906271c373819595e60a173624e1184Chandler Carruth } 404016de81177ec5c950f1668be4a48992bc1ee0d75Dan Gohman V = GEP->getPointerOperand(); 40559d3ae6cdc4316ad338cd848251f33a236ccb36cMatt Arsenault } else if (Operator::getOpcode(V) == Instruction::BitCast || 40659d3ae6cdc4316ad338cd848251f33a236ccb36cMatt Arsenault Operator::getOpcode(V) == Instruction::AddrSpaceCast) { 407016de81177ec5c950f1668be4a48992bc1ee0d75Dan Gohman V = cast<Operator>(V)->getOperand(0); 408aac1bfb99a7a43ce145748f41f64f970f5499de6Dan Gohman } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 409eaf14786ca3975266ed7041ac242122c02baf1cfRafael Espindola if (StripKind == PSK_ZeroIndices || GA->mayBeOverridden()) 410aac1bfb99a7a43ce145748f41f64f970f5499de6Dan Gohman return V; 411aac1bfb99a7a43ce145748f41f64f970f5499de6Dan Gohman V = GA->getAliasee(); 412f08bf1193c390bfe4b25d8533f146742d0277d06Duncan Sands } else { 413f08bf1193c390bfe4b25d8533f146742d0277d06Duncan Sands return V; 4140b12ecf6ff6b5d3a144178257b6206f0c4788792Anton Korobeynikov } 4151df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands assert(V->getType()->isPointerTy() && "Unexpected operand type!"); 41650f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman } while (Visited.insert(V)); 41750f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman 41850f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman return V; 4190b12ecf6ff6b5d3a144178257b6206f0c4788792Anton Korobeynikov} 42084dfc32ff906271c373819595e60a173624e1184Chandler Carruth} // namespace 42184dfc32ff906271c373819595e60a173624e1184Chandler Carruth 42284dfc32ff906271c373819595e60a173624e1184Chandler CarruthValue *Value::stripPointerCasts() { 423eaf14786ca3975266ed7041ac242122c02baf1cfRafael Espindola return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndAliases>(this); 424eaf14786ca3975266ed7041ac242122c02baf1cfRafael Espindola} 425eaf14786ca3975266ed7041ac242122c02baf1cfRafael Espindola 426eaf14786ca3975266ed7041ac242122c02baf1cfRafael EspindolaValue *Value::stripPointerCastsNoFollowAliases() { 42784dfc32ff906271c373819595e60a173624e1184Chandler Carruth return stripPointerCastsAndOffsets<PSK_ZeroIndices>(this); 42884dfc32ff906271c373819595e60a173624e1184Chandler Carruth} 42984dfc32ff906271c373819595e60a173624e1184Chandler Carruth 430274d377ea68195989c3238fe96ce2ca812a12fafChandler CarruthValue *Value::stripInBoundsConstantOffsets() { 431274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth return stripPointerCastsAndOffsets<PSK_InBoundsConstantIndices>(this); 43284dfc32ff906271c373819595e60a173624e1184Chandler Carruth} 43384dfc32ff906271c373819595e60a173624e1184Chandler Carruth 434f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler CarruthValue *Value::stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL, 435f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth APInt &Offset) { 436f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth if (!getType()->isPointerTy()) 437f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth return this; 438f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth 439f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth assert(Offset.getBitWidth() == DL.getPointerSizeInBits(cast<PointerType>( 440f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth getType())->getAddressSpace()) && 441f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth "The offset must have exactly as many bits as our pointer."); 442f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth 443f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth // Even though we don't look through PHI nodes, we could be called on an 444f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth // instruction in an unreachable block, which may be on a cycle. 445f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth SmallPtrSet<Value *, 4> Visited; 446f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth Visited.insert(this); 447f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth Value *V = this; 448f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth do { 449f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 450f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth if (!GEP->isInBounds()) 451f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth return V; 452c99a0d8586cd1b3f6d3b13bb839205e22375235dChandler Carruth APInt GEPOffset(Offset); 453c99a0d8586cd1b3f6d3b13bb839205e22375235dChandler Carruth if (!GEP->accumulateConstantOffset(DL, GEPOffset)) 454f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth return V; 455c99a0d8586cd1b3f6d3b13bb839205e22375235dChandler Carruth Offset = GEPOffset; 456f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth V = GEP->getPointerOperand(); 457f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth } else if (Operator::getOpcode(V) == Instruction::BitCast) { 458f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth V = cast<Operator>(V)->getOperand(0); 459f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 460f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth V = GA->getAliasee(); 461f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth } else { 462f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth return V; 463f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth } 464f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth assert(V->getType()->isPointerTy() && "Unexpected operand type!"); 465f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth } while (Visited.insert(V)); 466f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth 467f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth return V; 468f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth} 469f73826bef09fcc38d2db7b69baf0b8a45c9788f8Chandler Carruth 47084dfc32ff906271c373819595e60a173624e1184Chandler CarruthValue *Value::stripInBoundsOffsets() { 47184dfc32ff906271c373819595e60a173624e1184Chandler Carruth return stripPointerCastsAndOffsets<PSK_InBounds>(this); 47284dfc32ff906271c373819595e60a173624e1184Chandler Carruth} 4730b12ecf6ff6b5d3a144178257b6206f0c4788792Anton Korobeynikov 4744d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman/// isDereferenceablePointer - Test if this value is always a pointer to 47567b6464377a444a15a1a26fb8ca7cd54fc056de8Nick Lewycky/// allocated and suitably aligned memory for a simple load or store. 476cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesstatic bool isDereferenceablePointer(const Value *V, const DataLayout *DL, 47737abc488a0527bb682af5aa6c4f376b5b99d67e4Nick Lewycky SmallPtrSet<const Value *, 32> &Visited) { 4784d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman // Note that it is not safe to speculate into a malloc'd region because 4794d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman // malloc may return null. 4804d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman 4814d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman // These are obviously ok. 48237abc488a0527bb682af5aa6c4f376b5b99d67e4Nick Lewycky if (isa<AllocaInst>(V)) return true; 4834d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman 484cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // It's not always safe to follow a bitcast, for example: 485cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // bitcast i8* (alloca i8) to i32* 486cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // would result in a 4-byte load from a 1-byte alloca. However, 487cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // if we're casting from a pointer from a type of larger size 488cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // to a type of smaller size (or the same size), and the alignment 489cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // is at least as large as for the resulting pointer type, then 490cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // we can look through the bitcast. 491cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (DL) 492cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (const BitCastInst* BC = dyn_cast<BitCastInst>(V)) { 493cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Type *STy = BC->getSrcTy()->getPointerElementType(), 494cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines *DTy = BC->getDestTy()->getPointerElementType(); 495cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (STy->isSized() && DTy->isSized() && 496cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines (DL->getTypeStoreSize(STy) >= 497cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines DL->getTypeStoreSize(DTy)) && 498cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines (DL->getABITypeAlignment(STy) >= 499cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines DL->getABITypeAlignment(DTy))) 500cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return isDereferenceablePointer(BC->getOperand(0), DL, Visited); 501cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 502cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 5034d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman // Global variables which can't collapse to null are ok. 50437abc488a0527bb682af5aa6c4f376b5b99d67e4Nick Lewycky if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 5054d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman return !GV->hasExternalWeakLinkage(); 5064d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman 5073928af6ac47f9abef7dff32823a5fd41743c8fbcChris Lattner // byval arguments are ok. 50837abc488a0527bb682af5aa6c4f376b5b99d67e4Nick Lewycky if (const Argument *A = dyn_cast<Argument>(V)) 5093928af6ac47f9abef7dff32823a5fd41743c8fbcChris Lattner return A->hasByValAttr(); 51037abc488a0527bb682af5aa6c4f376b5b99d67e4Nick Lewycky 5114d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman // For GEPs, determine if the indexing lands within the allocated object. 51237abc488a0527bb682af5aa6c4f376b5b99d67e4Nick Lewycky if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 5134d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman // Conservatively require that the base pointer be fully dereferenceable. 51437abc488a0527bb682af5aa6c4f376b5b99d67e4Nick Lewycky if (!Visited.insert(GEP->getOperand(0))) 51537abc488a0527bb682af5aa6c4f376b5b99d67e4Nick Lewycky return false; 516cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (!isDereferenceablePointer(GEP->getOperand(0), DL, Visited)) 5174d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman return false; 5184d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman // Check the indices. 5194d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman gep_type_iterator GTI = gep_type_begin(GEP); 5204d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman for (User::const_op_iterator I = GEP->op_begin()+1, 5214d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman E = GEP->op_end(); I != E; ++I) { 5224d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman Value *Index = *I; 523db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *Ty = *GTI++; 5244d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman // Struct indices can't be out of bounds. 5254d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman if (isa<StructType>(Ty)) 5264d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman continue; 5274d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman ConstantInt *CI = dyn_cast<ConstantInt>(Index); 5284d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman if (!CI) 5294d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman return false; 5304d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman // Zero is always ok. 5314d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman if (CI->isZero()) 5324d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman continue; 5334d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman // Check to see that it's within the bounds of an array. 534db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner ArrayType *ATy = dyn_cast<ArrayType>(Ty); 5354d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman if (!ATy) 5364d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman return false; 5374d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman if (CI->getValue().getActiveBits() > 64) 5384d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman return false; 5394d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman if (CI->getZExtValue() >= ATy->getNumElements()) 5404d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman return false; 5414d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman } 5424d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman // Indices check out; this is dereferenceable. 5434d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman return true; 5444d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman } 5454d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman 5464d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman // If we don't know, assume the worst. 5474d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman return false; 5484d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman} 5494d70a2949007edeaad4662d5cdcb2d272cb2b2ffDan Gohman 55037abc488a0527bb682af5aa6c4f376b5b99d67e4Nick Lewycky/// isDereferenceablePointer - Test if this value is always a pointer to 55137abc488a0527bb682af5aa6c4f376b5b99d67e4Nick Lewycky/// allocated and suitably aligned memory for a simple load or store. 552cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesbool Value::isDereferenceablePointer(const DataLayout *DL) const { 55337abc488a0527bb682af5aa6c4f376b5b99d67e4Nick Lewycky SmallPtrSet<const Value *, 32> Visited; 554cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return ::isDereferenceablePointer(this, DL, Visited); 55537abc488a0527bb682af5aa6c4f376b5b99d67e4Nick Lewycky} 55637abc488a0527bb682af5aa6c4f376b5b99d67e4Nick Lewycky 55701c8e0233d086354b55d2047506ac6a8fc3c9f65Chris Lattner/// DoPHITranslation - If this value is a PHI node with CurBB as its parent, 558c7f7c1dc5067a36c8ae337610dcbbe55d525c80cChris Lattner/// return the value in the PHI node corresponding to PredBB. If not, return 559c7f7c1dc5067a36c8ae337610dcbbe55d525c80cChris Lattner/// ourself. This is useful if you want to know the value something has in a 560c7f7c1dc5067a36c8ae337610dcbbe55d525c80cChris Lattner/// predecessor block. 561ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel DunbarValue *Value::DoPHITranslation(const BasicBlock *CurBB, 562c7f7c1dc5067a36c8ae337610dcbbe55d525c80cChris Lattner const BasicBlock *PredBB) { 563c7f7c1dc5067a36c8ae337610dcbbe55d525c80cChris Lattner PHINode *PN = dyn_cast<PHINode>(this); 564c7f7c1dc5067a36c8ae337610dcbbe55d525c80cChris Lattner if (PN && PN->getParent() == CurBB) 565c7f7c1dc5067a36c8ae337610dcbbe55d525c80cChris Lattner return PN->getIncomingValueForBlock(PredBB); 566c7f7c1dc5067a36c8ae337610dcbbe55d525c80cChris Lattner return this; 567c7f7c1dc5067a36c8ae337610dcbbe55d525c80cChris Lattner} 568c7f7c1dc5067a36c8ae337610dcbbe55d525c80cChris Lattner 569e922c0201916e0b980ab3cfe91e1413e68d55647Owen AndersonLLVMContext &Value::getContext() const { return VTy->getContext(); } 570e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson 571722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner//===----------------------------------------------------------------------===// 572722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner// ValueHandleBase Class 573722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner//===----------------------------------------------------------------------===// 574722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner 575fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump/// AddToExistingUseList - Add this ValueHandle to the use list for VP, where 576fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump/// List is known to point into the existing use list. 577722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattnervoid ValueHandleBase::AddToExistingUseList(ValueHandleBase **List) { 578722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner assert(List && "Handle list is null?"); 579ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 580722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // Splice ourselves into the list. 581722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner Next = *List; 582722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner *List = this; 583722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner setPrevPtr(List); 584722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner if (Next) { 585722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner Next->setPrevPtr(&Next); 5865252c432dd93147fa70a536be58a15ef329de0b7Bill Wendling assert(VP.getPointer() == Next->VP.getPointer() && "Added to wrong list?"); 587722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner } 588722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner} 589722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner 5906a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskinvoid ValueHandleBase::AddToExistingUseListAfter(ValueHandleBase *List) { 5916a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin assert(List && "Must insert after existing node"); 5926a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin 5936a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin Next = List->Next; 5946a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin setPrevPtr(&List->Next); 5956a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin List->Next = this; 5966a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin if (Next) 5976a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin Next->setPrevPtr(&Next); 5986a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin} 5996a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin 600722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner/// AddToUseList - Add this ValueHandle to the use list for VP. 601722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattnervoid ValueHandleBase::AddToUseList() { 6025252c432dd93147fa70a536be58a15ef329de0b7Bill Wendling assert(VP.getPointer() && "Null pointer doesn't have a use list!"); 603ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 6045252c432dd93147fa70a536be58a15ef329de0b7Bill Wendling LLVMContextImpl *pImpl = VP.getPointer()->getContext().pImpl; 605ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 6065252c432dd93147fa70a536be58a15ef329de0b7Bill Wendling if (VP.getPointer()->HasValueHandle) { 607722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // If this value already has a ValueHandle, then it must be in the 608722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // ValueHandles map already. 6095252c432dd93147fa70a536be58a15ef329de0b7Bill Wendling ValueHandleBase *&Entry = pImpl->ValueHandles[VP.getPointer()]; 610dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(Entry && "Value doesn't have any handles?"); 611f2aac28d3040f9c716b4597ec90d237f27883866Owen Anderson AddToExistingUseList(&Entry); 612f2aac28d3040f9c716b4597ec90d237f27883866Owen Anderson return; 613722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner } 614ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 615722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // Ok, it doesn't have any handles yet, so we must insert it into the 616722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // DenseMap. However, doing this insertion could cause the DenseMap to 617722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // reallocate itself, which would invalidate all of the PrevP pointers that 618722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // point into the old table. Handle this by checking for reallocation and 619722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // updating the stale pointers only if needed. 6204d919438898d542850449235da7f6dc55e6ca152Owen Anderson DenseMap<Value*, ValueHandleBase*> &Handles = pImpl->ValueHandles; 621722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner const void *OldBucketPtr = Handles.getPointerIntoBucketsArray(); 622ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 6235252c432dd93147fa70a536be58a15ef329de0b7Bill Wendling ValueHandleBase *&Entry = Handles[VP.getPointer()]; 624dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(!Entry && "Value really did already have handles?"); 625722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner AddToExistingUseList(&Entry); 6265252c432dd93147fa70a536be58a15ef329de0b7Bill Wendling VP.getPointer()->HasValueHandle = true; 627ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 628722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // If reallocation didn't happen or if this was the first insertion, don't 629722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // walk the table. 630ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar if (Handles.isPointerIntoBucketsArray(OldBucketPtr) || 631f2aac28d3040f9c716b4597ec90d237f27883866Owen Anderson Handles.size() == 1) { 632722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner return; 633f2aac28d3040f9c716b4597ec90d237f27883866Owen Anderson } 634ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 635722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // Okay, reallocation did happen. Fix the Prev Pointers. 6364d919438898d542850449235da7f6dc55e6ca152Owen Anderson for (DenseMap<Value*, ValueHandleBase*>::iterator I = Handles.begin(), 6374d919438898d542850449235da7f6dc55e6ca152Owen Anderson E = Handles.end(); I != E; ++I) { 6385252c432dd93147fa70a536be58a15ef329de0b7Bill Wendling assert(I->second && I->first == I->second->VP.getPointer() && 6395252c432dd93147fa70a536be58a15ef329de0b7Bill Wendling "List invariant broken!"); 640722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner I->second->setPrevPtr(&I->second); 641722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner } 642722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner} 643722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner 644722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner/// RemoveFromUseList - Remove this ValueHandle from its current use list. 645722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattnervoid ValueHandleBase::RemoveFromUseList() { 6465252c432dd93147fa70a536be58a15ef329de0b7Bill Wendling assert(VP.getPointer() && VP.getPointer()->HasValueHandle && 6475252c432dd93147fa70a536be58a15ef329de0b7Bill Wendling "Pointer doesn't have a use list!"); 648722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner 649722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // Unlink this from its use list. 650722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner ValueHandleBase **PrevPtr = getPrevPtr(); 651722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner assert(*PrevPtr == this && "List invariant broken"); 652ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 653722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner *PrevPtr = Next; 654722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner if (Next) { 655722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner assert(Next->getPrevPtr() == &Next && "List invariant broken"); 656722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner Next->setPrevPtr(PrevPtr); 657722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner return; 658722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner } 659ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 660722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // If the Next pointer was null, then it is possible that this was the last 661722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // ValueHandle watching VP. If so, delete its entry from the ValueHandles 662722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // map. 6635252c432dd93147fa70a536be58a15ef329de0b7Bill Wendling LLVMContextImpl *pImpl = VP.getPointer()->getContext().pImpl; 6644d919438898d542850449235da7f6dc55e6ca152Owen Anderson DenseMap<Value*, ValueHandleBase*> &Handles = pImpl->ValueHandles; 665722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner if (Handles.isPointerIntoBucketsArray(PrevPtr)) { 6665252c432dd93147fa70a536be58a15ef329de0b7Bill Wendling Handles.erase(VP.getPointer()); 6675252c432dd93147fa70a536be58a15ef329de0b7Bill Wendling VP.getPointer()->HasValueHandle = false; 668722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner } 669722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner} 670722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner 671722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner 672722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattnervoid ValueHandleBase::ValueIsDeleted(Value *V) { 673722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner assert(V->HasValueHandle && "Should only be called if ValueHandles present"); 674722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner 675722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // Get the linked list base, which is guaranteed to exist since the 676722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // HasValueHandle flag is set. 6774d919438898d542850449235da7f6dc55e6ca152Owen Anderson LLVMContextImpl *pImpl = V->getContext().pImpl; 6784d919438898d542850449235da7f6dc55e6ca152Owen Anderson ValueHandleBase *Entry = pImpl->ValueHandles[V]; 679722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner assert(Entry && "Value bit set but no entries exist"); 680ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 681ffe8c8871a1c7119440b2b02dce746901794fa5eDuncan Sands // We use a local ValueHandleBase as an iterator so that ValueHandles can add 682ffe8c8871a1c7119440b2b02dce746901794fa5eDuncan Sands // and remove themselves from the list without breaking our iteration. This 683ffe8c8871a1c7119440b2b02dce746901794fa5eDuncan Sands // is not really an AssertingVH; we just have to give ValueHandleBase a kind. 684ffe8c8871a1c7119440b2b02dce746901794fa5eDuncan Sands // Note that we deliberately do not the support the case when dropping a value 685ffe8c8871a1c7119440b2b02dce746901794fa5eDuncan Sands // handle results in a new value handle being permanently added to the list 686ffe8c8871a1c7119440b2b02dce746901794fa5eDuncan Sands // (as might occur in theory for CallbackVH's): the new value handle will not 6872c11046fa186a4489bfd562cd81ff8a4883cb223Duncan Sands // be processed and the checking code will mete out righteous punishment if 688ffe8c8871a1c7119440b2b02dce746901794fa5eDuncan Sands // the handle is still present once we have finished processing all the other 689ffe8c8871a1c7119440b2b02dce746901794fa5eDuncan Sands // value handles (it is fine to momentarily add then remove a value handle). 6906a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin for (ValueHandleBase Iterator(Assert, *Entry); Entry; Entry = Iterator.Next) { 6916a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin Iterator.RemoveFromUseList(); 6926a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin Iterator.AddToExistingUseListAfter(Entry); 6936a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin assert(Entry->Next == &Iterator && "Loop invariant broken."); 694ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 6956a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin switch (Entry->getKind()) { 696722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner case Assert: 6976a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin break; 698e5b18362dbafc8ee44ae864664fffe47066f685aDaniel Dunbar case Tracking: 699e5b18362dbafc8ee44ae864664fffe47066f685aDaniel Dunbar // Mark that this value has been deleted by setting it to an invalid Value 700e5b18362dbafc8ee44ae864664fffe47066f685aDaniel Dunbar // pointer. 7016a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin Entry->operator=(DenseMapInfo<Value *>::getTombstoneKey()); 702e5b18362dbafc8ee44ae864664fffe47066f685aDaniel Dunbar break; 703722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner case Weak: 704722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // Weak just goes to null, which will unlink it from the list. 705dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Entry->operator=(nullptr); 706722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner break; 707722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner case Callback: 708c09b12c62208f09de9d107b320f5420ae6e4fc38Dan Gohman // Forward to the subclass's implementation. 7096a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin static_cast<CallbackVH*>(Entry)->deleted(); 710c09b12c62208f09de9d107b320f5420ae6e4fc38Dan Gohman break; 711722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner } 712722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner } 713ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 7146a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin // All callbacks, weak references, and assertingVHs should be dropped by now. 7156a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin if (V->HasValueHandle) { 7166a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin#ifndef NDEBUG // Only in +Asserts mode... 717a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer dbgs() << "While deleting: " << *V->getType() << " %" << V->getName() 7186a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin << "\n"; 7196a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin if (pImpl->ValueHandles[V]->getKind() == Assert) 7206a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin llvm_unreachable("An asserting value handle still pointed to this" 7216a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin " value!"); 7226a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin 7236a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin#endif 7246a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin llvm_unreachable("All references to V were not removed?"); 7256a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin } 726722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner} 727722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner 728722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner 729722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattnervoid ValueHandleBase::ValueIsRAUWd(Value *Old, Value *New) { 730722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner assert(Old->HasValueHandle &&"Should only be called if ValueHandles present"); 731722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner assert(Old != New && "Changing value into itself!"); 732ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 733722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // Get the linked list base, which is guaranteed to exist since the 734722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // HasValueHandle flag is set. 7354d919438898d542850449235da7f6dc55e6ca152Owen Anderson LLVMContextImpl *pImpl = Old->getContext().pImpl; 7364d919438898d542850449235da7f6dc55e6ca152Owen Anderson ValueHandleBase *Entry = pImpl->ValueHandles[Old]; 7374d919438898d542850449235da7f6dc55e6ca152Owen Anderson 738722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner assert(Entry && "Value bit set but no entries exist"); 739ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 7406a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin // We use a local ValueHandleBase as an iterator so that 7416a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin // ValueHandles can add and remove themselves from the list without 7426a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin // breaking our iteration. This is not really an AssertingVH; we 7436a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin // just have to give ValueHandleBase some kind. 7446a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin for (ValueHandleBase Iterator(Assert, *Entry); Entry; Entry = Iterator.Next) { 7456a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin Iterator.RemoveFromUseList(); 7466a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin Iterator.AddToExistingUseListAfter(Entry); 7476a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin assert(Entry->Next == &Iterator && "Loop invariant broken."); 748ce99a6e49ee5f849c33aa1a989b4cc08c71c3c9bDaniel Dunbar 7496a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin switch (Entry->getKind()) { 750722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner case Assert: 751722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // Asserting handle does not follow RAUW implicitly. 752722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner break; 753e5b18362dbafc8ee44ae864664fffe47066f685aDaniel Dunbar case Tracking: 754e5b18362dbafc8ee44ae864664fffe47066f685aDaniel Dunbar // Tracking goes to new value like a WeakVH. Note that this may make it 755e5b18362dbafc8ee44ae864664fffe47066f685aDaniel Dunbar // something incompatible with its templated type. We don't want to have a 756e5b18362dbafc8ee44ae864664fffe47066f685aDaniel Dunbar // virtual (or inline) interface to handle this though, so instead we make 757460a786b349cceb79917cb76712ec4941bef69ccDaniel Dunbar // the TrackingVH accessors guarantee that a client never sees this value. 758e5b18362dbafc8ee44ae864664fffe47066f685aDaniel Dunbar 759e5b18362dbafc8ee44ae864664fffe47066f685aDaniel Dunbar // FALLTHROUGH 760722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner case Weak: 761722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner // Weak goes to the new value, which will unlink it from Old's list. 7626a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin Entry->operator=(New); 763722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner break; 764722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner case Callback: 765c09b12c62208f09de9d107b320f5420ae6e4fc38Dan Gohman // Forward to the subclass's implementation. 7666a9291ad55cf3b3731d3512eb5aa72ac7cdf02f9Jeffrey Yasskin static_cast<CallbackVH*>(Entry)->allUsesReplacedWith(New); 767c09b12c62208f09de9d107b320f5420ae6e4fc38Dan Gohman break; 768722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner } 769722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner } 7702c11046fa186a4489bfd562cd81ff8a4883cb223Duncan Sands 7712c11046fa186a4489bfd562cd81ff8a4883cb223Duncan Sands#ifndef NDEBUG 7722c11046fa186a4489bfd562cd81ff8a4883cb223Duncan Sands // If any new tracking or weak value handles were added while processing the 7732c11046fa186a4489bfd562cd81ff8a4883cb223Duncan Sands // list, then complain about it now. 7742c11046fa186a4489bfd562cd81ff8a4883cb223Duncan Sands if (Old->HasValueHandle) 7752c11046fa186a4489bfd562cd81ff8a4883cb223Duncan Sands for (Entry = pImpl->ValueHandles[Old]; Entry; Entry = Entry->Next) 7762c11046fa186a4489bfd562cd81ff8a4883cb223Duncan Sands switch (Entry->getKind()) { 7772c11046fa186a4489bfd562cd81ff8a4883cb223Duncan Sands case Tracking: 7782c11046fa186a4489bfd562cd81ff8a4883cb223Duncan Sands case Weak: 7792c11046fa186a4489bfd562cd81ff8a4883cb223Duncan Sands dbgs() << "After RAUW from " << *Old->getType() << " %" 780a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer << Old->getName() << " to " << *New->getType() << " %" 781a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer << New->getName() << "\n"; 7822c11046fa186a4489bfd562cd81ff8a4883cb223Duncan Sands llvm_unreachable("A tracking or weak value handle still pointed to the" 7832c11046fa186a4489bfd562cd81ff8a4883cb223Duncan Sands " old value!\n"); 7842c11046fa186a4489bfd562cd81ff8a4883cb223Duncan Sands default: 7852c11046fa186a4489bfd562cd81ff8a4883cb223Duncan Sands break; 7862c11046fa186a4489bfd562cd81ff8a4883cb223Duncan Sands } 7872c11046fa186a4489bfd562cd81ff8a4883cb223Duncan Sands#endif 788722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner} 789722272df41d8de9c7683811b7bd8e901ee2f2785Chris Lattner 790354362524a72b3fa43a6c09380b7ae3b2380cbbaJuergen Ributzka// Pin the vtable to this file. 791354362524a72b3fa43a6c09380b7ae3b2380cbbaJuergen Ributzkavoid CallbackVH::anchor() {} 792