1 //===-- Metadata.cpp - Implement Metadata classes -------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements the Metadata classes. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Metadata.h" 15 #include "LLVMContextImpl.h" 16 #include "llvm/LLVMContext.h" 17 #include "llvm/Module.h" 18 #include "llvm/Instruction.h" 19 #include "llvm/ADT/DenseMap.h" 20 #include "llvm/ADT/StringMap.h" 21 #include "llvm/ADT/SmallString.h" 22 #include "llvm/ADT/STLExtras.h" 23 #include "SymbolTableListTraitsImpl.h" 24 #include "llvm/Support/LeakDetector.h" 25 #include "llvm/Support/ValueHandle.h" 26 using namespace llvm; 27 28 //===----------------------------------------------------------------------===// 29 // MDString implementation. 30 // 31 32 MDString::MDString(LLVMContext &C, StringRef S) 33 : Value(Type::getMetadataTy(C), Value::MDStringVal), Str(S) {} 34 35 MDString *MDString::get(LLVMContext &Context, StringRef Str) { 36 LLVMContextImpl *pImpl = Context.pImpl; 37 StringMapEntry<MDString *> &Entry = 38 pImpl->MDStringCache.GetOrCreateValue(Str); 39 MDString *&S = Entry.getValue(); 40 if (!S) S = new MDString(Context, Entry.getKey()); 41 return S; 42 } 43 44 //===----------------------------------------------------------------------===// 45 // MDNodeOperand implementation. 46 // 47 48 // Use CallbackVH to hold MDNode operands. 49 namespace llvm { 50 class MDNodeOperand : public CallbackVH { 51 MDNode *Parent; 52 public: 53 MDNodeOperand(Value *V, MDNode *P) : CallbackVH(V), Parent(P) {} 54 ~MDNodeOperand() {} 55 56 void set(Value *V) { 57 setValPtr(V); 58 } 59 60 virtual void deleted(); 61 virtual void allUsesReplacedWith(Value *NV); 62 }; 63 } // end namespace llvm. 64 65 66 void MDNodeOperand::deleted() { 67 Parent->replaceOperand(this, 0); 68 } 69 70 void MDNodeOperand::allUsesReplacedWith(Value *NV) { 71 Parent->replaceOperand(this, NV); 72 } 73 74 75 76 //===----------------------------------------------------------------------===// 77 // MDNode implementation. 78 // 79 80 /// getOperandPtr - Helper function to get the MDNodeOperand's coallocated on 81 /// the end of the MDNode. 82 static MDNodeOperand *getOperandPtr(MDNode *N, unsigned Op) { 83 // Use <= instead of < to permit a one-past-the-end address. 84 assert(Op <= N->getNumOperands() && "Invalid operand number"); 85 return reinterpret_cast<MDNodeOperand*>(N+1)+Op; 86 } 87 88 MDNode::MDNode(LLVMContext &C, ArrayRef<Value*> Vals, bool isFunctionLocal) 89 : Value(Type::getMetadataTy(C), Value::MDNodeVal) { 90 NumOperands = Vals.size(); 91 92 if (isFunctionLocal) 93 setValueSubclassData(getSubclassDataFromValue() | FunctionLocalBit); 94 95 // Initialize the operand list, which is co-allocated on the end of the node. 96 unsigned i = 0; 97 for (MDNodeOperand *Op = getOperandPtr(this, 0), *E = Op+NumOperands; 98 Op != E; ++Op, ++i) 99 new (Op) MDNodeOperand(Vals[i], this); 100 } 101 102 103 /// ~MDNode - Destroy MDNode. 104 MDNode::~MDNode() { 105 assert((getSubclassDataFromValue() & DestroyFlag) != 0 && 106 "Not being destroyed through destroy()?"); 107 LLVMContextImpl *pImpl = getType()->getContext().pImpl; 108 if (isNotUniqued()) { 109 pImpl->NonUniquedMDNodes.erase(this); 110 } else { 111 pImpl->MDNodeSet.RemoveNode(this); 112 } 113 114 // Destroy the operands. 115 for (MDNodeOperand *Op = getOperandPtr(this, 0), *E = Op+NumOperands; 116 Op != E; ++Op) 117 Op->~MDNodeOperand(); 118 } 119 120 static const Function *getFunctionForValue(Value *V) { 121 if (!V) return NULL; 122 if (Instruction *I = dyn_cast<Instruction>(V)) { 123 BasicBlock *BB = I->getParent(); 124 return BB ? BB->getParent() : 0; 125 } 126 if (Argument *A = dyn_cast<Argument>(V)) 127 return A->getParent(); 128 if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) 129 return BB->getParent(); 130 if (MDNode *MD = dyn_cast<MDNode>(V)) 131 return MD->getFunction(); 132 return NULL; 133 } 134 135 #ifndef NDEBUG 136 static const Function *assertLocalFunction(const MDNode *N) { 137 if (!N->isFunctionLocal()) return 0; 138 139 // FIXME: This does not handle cyclic function local metadata. 140 const Function *F = 0, *NewF = 0; 141 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 142 if (Value *V = N->getOperand(i)) { 143 if (MDNode *MD = dyn_cast<MDNode>(V)) 144 NewF = assertLocalFunction(MD); 145 else 146 NewF = getFunctionForValue(V); 147 } 148 if (F == 0) 149 F = NewF; 150 else 151 assert((NewF == 0 || F == NewF) &&"inconsistent function-local metadata"); 152 } 153 return F; 154 } 155 #endif 156 157 // getFunction - If this metadata is function-local and recursively has a 158 // function-local operand, return the first such operand's parent function. 159 // Otherwise, return null. getFunction() should not be used for performance- 160 // critical code because it recursively visits all the MDNode's operands. 161 const Function *MDNode::getFunction() const { 162 #ifndef NDEBUG 163 return assertLocalFunction(this); 164 #endif 165 if (!isFunctionLocal()) return NULL; 166 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 167 if (const Function *F = getFunctionForValue(getOperand(i))) 168 return F; 169 return NULL; 170 } 171 172 // destroy - Delete this node. Only when there are no uses. 173 void MDNode::destroy() { 174 setValueSubclassData(getSubclassDataFromValue() | DestroyFlag); 175 // Placement delete, the free the memory. 176 this->~MDNode(); 177 free(this); 178 } 179 180 /// isFunctionLocalValue - Return true if this is a value that would require a 181 /// function-local MDNode. 182 static bool isFunctionLocalValue(Value *V) { 183 return isa<Instruction>(V) || isa<Argument>(V) || isa<BasicBlock>(V) || 184 (isa<MDNode>(V) && cast<MDNode>(V)->isFunctionLocal()); 185 } 186 187 MDNode *MDNode::getMDNode(LLVMContext &Context, ArrayRef<Value*> Vals, 188 FunctionLocalness FL, bool Insert) { 189 LLVMContextImpl *pImpl = Context.pImpl; 190 191 // Add all the operand pointers. Note that we don't have to add the 192 // isFunctionLocal bit because that's implied by the operands. 193 // Note that if the operands are later nulled out, the node will be 194 // removed from the uniquing map. 195 FoldingSetNodeID ID; 196 for (unsigned i = 0; i != Vals.size(); ++i) 197 ID.AddPointer(Vals[i]); 198 199 void *InsertPoint; 200 MDNode *N = NULL; 201 202 if ((N = pImpl->MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint))) 203 return N; 204 205 bool isFunctionLocal = false; 206 switch (FL) { 207 case FL_Unknown: 208 for (unsigned i = 0; i != Vals.size(); ++i) { 209 Value *V = Vals[i]; 210 if (!V) continue; 211 if (isFunctionLocalValue(V)) { 212 isFunctionLocal = true; 213 break; 214 } 215 } 216 break; 217 case FL_No: 218 isFunctionLocal = false; 219 break; 220 case FL_Yes: 221 isFunctionLocal = true; 222 break; 223 } 224 225 // Coallocate space for the node and Operands together, then placement new. 226 void *Ptr = malloc(sizeof(MDNode)+Vals.size()*sizeof(MDNodeOperand)); 227 N = new (Ptr) MDNode(Context, Vals, isFunctionLocal); 228 229 // InsertPoint will have been set by the FindNodeOrInsertPos call. 230 pImpl->MDNodeSet.InsertNode(N, InsertPoint); 231 232 return N; 233 } 234 235 MDNode *MDNode::get(LLVMContext &Context, ArrayRef<Value*> Vals) { 236 return getMDNode(Context, Vals, FL_Unknown); 237 } 238 239 MDNode *MDNode::getWhenValsUnresolved(LLVMContext &Context, 240 ArrayRef<Value*> Vals, 241 bool isFunctionLocal) { 242 return getMDNode(Context, Vals, isFunctionLocal ? FL_Yes : FL_No); 243 } 244 245 MDNode *MDNode::getIfExists(LLVMContext &Context, ArrayRef<Value*> Vals) { 246 return getMDNode(Context, Vals, FL_Unknown, false); 247 } 248 249 MDNode *MDNode::getTemporary(LLVMContext &Context, ArrayRef<Value*> Vals) { 250 MDNode *N = 251 (MDNode *)malloc(sizeof(MDNode)+Vals.size()*sizeof(MDNodeOperand)); 252 N = new (N) MDNode(Context, Vals, FL_No); 253 N->setValueSubclassData(N->getSubclassDataFromValue() | 254 NotUniquedBit); 255 LeakDetector::addGarbageObject(N); 256 return N; 257 } 258 259 void MDNode::deleteTemporary(MDNode *N) { 260 assert(N->use_empty() && "Temporary MDNode has uses!"); 261 assert(!N->getContext().pImpl->MDNodeSet.RemoveNode(N) && 262 "Deleting a non-temporary uniqued node!"); 263 assert(!N->getContext().pImpl->NonUniquedMDNodes.erase(N) && 264 "Deleting a non-temporary non-uniqued node!"); 265 assert((N->getSubclassDataFromValue() & NotUniquedBit) && 266 "Temporary MDNode does not have NotUniquedBit set!"); 267 assert((N->getSubclassDataFromValue() & DestroyFlag) == 0 && 268 "Temporary MDNode has DestroyFlag set!"); 269 LeakDetector::removeGarbageObject(N); 270 N->destroy(); 271 } 272 273 /// getOperand - Return specified operand. 274 Value *MDNode::getOperand(unsigned i) const { 275 return *getOperandPtr(const_cast<MDNode*>(this), i); 276 } 277 278 void MDNode::Profile(FoldingSetNodeID &ID) const { 279 // Add all the operand pointers. Note that we don't have to add the 280 // isFunctionLocal bit because that's implied by the operands. 281 // Note that if the operands are later nulled out, the node will be 282 // removed from the uniquing map. 283 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 284 ID.AddPointer(getOperand(i)); 285 } 286 287 void MDNode::setIsNotUniqued() { 288 setValueSubclassData(getSubclassDataFromValue() | NotUniquedBit); 289 LLVMContextImpl *pImpl = getType()->getContext().pImpl; 290 pImpl->NonUniquedMDNodes.insert(this); 291 } 292 293 // Replace value from this node's operand list. 294 void MDNode::replaceOperand(MDNodeOperand *Op, Value *To) { 295 Value *From = *Op; 296 297 // If is possible that someone did GV->RAUW(inst), replacing a global variable 298 // with an instruction or some other function-local object. If this is a 299 // non-function-local MDNode, it can't point to a function-local object. 300 // Handle this case by implicitly dropping the MDNode reference to null. 301 // Likewise if the MDNode is function-local but for a different function. 302 if (To && isFunctionLocalValue(To)) { 303 if (!isFunctionLocal()) 304 To = 0; 305 else { 306 const Function *F = getFunction(); 307 const Function *FV = getFunctionForValue(To); 308 // Metadata can be function-local without having an associated function. 309 // So only consider functions to have changed if non-null. 310 if (F && FV && F != FV) 311 To = 0; 312 } 313 } 314 315 if (From == To) 316 return; 317 318 // Update the operand. 319 Op->set(To); 320 321 // If this node is already not being uniqued (because one of the operands 322 // already went to null), then there is nothing else to do here. 323 if (isNotUniqued()) return; 324 325 LLVMContextImpl *pImpl = getType()->getContext().pImpl; 326 327 // Remove "this" from the context map. FoldingSet doesn't have to reprofile 328 // this node to remove it, so we don't care what state the operands are in. 329 pImpl->MDNodeSet.RemoveNode(this); 330 331 // If we are dropping an argument to null, we choose to not unique the MDNode 332 // anymore. This commonly occurs during destruction, and uniquing these 333 // brings little reuse. Also, this means we don't need to include 334 // isFunctionLocal bits in FoldingSetNodeIDs for MDNodes. 335 if (To == 0) { 336 setIsNotUniqued(); 337 return; 338 } 339 340 // Now that the node is out of the folding set, get ready to reinsert it. 341 // First, check to see if another node with the same operands already exists 342 // in the set. If so, then this node is redundant. 343 FoldingSetNodeID ID; 344 Profile(ID); 345 void *InsertPoint; 346 if (MDNode *N = pImpl->MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint)) { 347 replaceAllUsesWith(N); 348 destroy(); 349 return; 350 } 351 352 // InsertPoint will have been set by the FindNodeOrInsertPos call. 353 pImpl->MDNodeSet.InsertNode(this, InsertPoint); 354 355 // If this MDValue was previously function-local but no longer is, clear 356 // its function-local flag. 357 if (isFunctionLocal() && !isFunctionLocalValue(To)) { 358 bool isStillFunctionLocal = false; 359 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { 360 Value *V = getOperand(i); 361 if (!V) continue; 362 if (isFunctionLocalValue(V)) { 363 isStillFunctionLocal = true; 364 break; 365 } 366 } 367 if (!isStillFunctionLocal) 368 setValueSubclassData(getSubclassDataFromValue() & ~FunctionLocalBit); 369 } 370 } 371 372 //===----------------------------------------------------------------------===// 373 // NamedMDNode implementation. 374 // 375 376 static SmallVector<TrackingVH<MDNode>, 4> &getNMDOps(void *Operands) { 377 return *(SmallVector<TrackingVH<MDNode>, 4>*)Operands; 378 } 379 380 NamedMDNode::NamedMDNode(const Twine &N) 381 : Name(N.str()), Parent(0), 382 Operands(new SmallVector<TrackingVH<MDNode>, 4>()) { 383 } 384 385 NamedMDNode::~NamedMDNode() { 386 dropAllReferences(); 387 delete &getNMDOps(Operands); 388 } 389 390 /// getNumOperands - Return number of NamedMDNode operands. 391 unsigned NamedMDNode::getNumOperands() const { 392 return (unsigned)getNMDOps(Operands).size(); 393 } 394 395 /// getOperand - Return specified operand. 396 MDNode *NamedMDNode::getOperand(unsigned i) const { 397 assert(i < getNumOperands() && "Invalid Operand number!"); 398 return dyn_cast<MDNode>(&*getNMDOps(Operands)[i]); 399 } 400 401 /// addOperand - Add metadata Operand. 402 void NamedMDNode::addOperand(MDNode *M) { 403 assert(!M->isFunctionLocal() && 404 "NamedMDNode operands must not be function-local!"); 405 getNMDOps(Operands).push_back(TrackingVH<MDNode>(M)); 406 } 407 408 /// eraseFromParent - Drop all references and remove the node from parent 409 /// module. 410 void NamedMDNode::eraseFromParent() { 411 getParent()->eraseNamedMetadata(this); 412 } 413 414 /// dropAllReferences - Remove all uses and clear node vector. 415 void NamedMDNode::dropAllReferences() { 416 getNMDOps(Operands).clear(); 417 } 418 419 /// getName - Return a constant reference to this named metadata's name. 420 StringRef NamedMDNode::getName() const { 421 return StringRef(Name); 422 } 423 424 //===----------------------------------------------------------------------===// 425 // Instruction Metadata method implementations. 426 // 427 428 void Instruction::setMetadata(const char *Kind, MDNode *Node) { 429 if (Node == 0 && !hasMetadata()) return; 430 setMetadata(getContext().getMDKindID(Kind), Node); 431 } 432 433 MDNode *Instruction::getMetadataImpl(const char *Kind) const { 434 return getMetadataImpl(getContext().getMDKindID(Kind)); 435 } 436 437 /// setMetadata - Set the metadata of of the specified kind to the specified 438 /// node. This updates/replaces metadata if already present, or removes it if 439 /// Node is null. 440 void Instruction::setMetadata(unsigned KindID, MDNode *Node) { 441 if (Node == 0 && !hasMetadata()) return; 442 443 // Handle 'dbg' as a special case since it is not stored in the hash table. 444 if (KindID == LLVMContext::MD_dbg) { 445 DbgLoc = DebugLoc::getFromDILocation(Node); 446 return; 447 } 448 449 // Handle the case when we're adding/updating metadata on an instruction. 450 if (Node) { 451 LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this]; 452 assert(!Info.empty() == hasMetadataHashEntry() && 453 "HasMetadata bit is wonked"); 454 if (Info.empty()) { 455 setHasMetadataHashEntry(true); 456 } else { 457 // Handle replacement of an existing value. 458 for (unsigned i = 0, e = Info.size(); i != e; ++i) 459 if (Info[i].first == KindID) { 460 Info[i].second = Node; 461 return; 462 } 463 } 464 465 // No replacement, just add it to the list. 466 Info.push_back(std::make_pair(KindID, Node)); 467 return; 468 } 469 470 // Otherwise, we're removing metadata from an instruction. 471 assert(hasMetadataHashEntry() && 472 getContext().pImpl->MetadataStore.count(this) && 473 "HasMetadata bit out of date!"); 474 LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this]; 475 476 // Common case is removing the only entry. 477 if (Info.size() == 1 && Info[0].first == KindID) { 478 getContext().pImpl->MetadataStore.erase(this); 479 setHasMetadataHashEntry(false); 480 return; 481 } 482 483 // Handle removal of an existing value. 484 for (unsigned i = 0, e = Info.size(); i != e; ++i) 485 if (Info[i].first == KindID) { 486 Info[i] = Info.back(); 487 Info.pop_back(); 488 assert(!Info.empty() && "Removing last entry should be handled above"); 489 return; 490 } 491 // Otherwise, removing an entry that doesn't exist on the instruction. 492 } 493 494 MDNode *Instruction::getMetadataImpl(unsigned KindID) const { 495 // Handle 'dbg' as a special case since it is not stored in the hash table. 496 if (KindID == LLVMContext::MD_dbg) 497 return DbgLoc.getAsMDNode(getContext()); 498 499 if (!hasMetadataHashEntry()) return 0; 500 501 LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this]; 502 assert(!Info.empty() && "bit out of sync with hash table"); 503 504 for (LLVMContextImpl::MDMapTy::iterator I = Info.begin(), E = Info.end(); 505 I != E; ++I) 506 if (I->first == KindID) 507 return I->second; 508 return 0; 509 } 510 511 void Instruction::getAllMetadataImpl(SmallVectorImpl<std::pair<unsigned, 512 MDNode*> > &Result) const { 513 Result.clear(); 514 515 // Handle 'dbg' as a special case since it is not stored in the hash table. 516 if (!DbgLoc.isUnknown()) { 517 Result.push_back(std::make_pair((unsigned)LLVMContext::MD_dbg, 518 DbgLoc.getAsMDNode(getContext()))); 519 if (!hasMetadataHashEntry()) return; 520 } 521 522 assert(hasMetadataHashEntry() && 523 getContext().pImpl->MetadataStore.count(this) && 524 "Shouldn't have called this"); 525 const LLVMContextImpl::MDMapTy &Info = 526 getContext().pImpl->MetadataStore.find(this)->second; 527 assert(!Info.empty() && "Shouldn't have called this"); 528 529 Result.append(Info.begin(), Info.end()); 530 531 // Sort the resulting array so it is stable. 532 if (Result.size() > 1) 533 array_pod_sort(Result.begin(), Result.end()); 534 } 535 536 void Instruction:: 537 getAllMetadataOtherThanDebugLocImpl(SmallVectorImpl<std::pair<unsigned, 538 MDNode*> > &Result) const { 539 Result.clear(); 540 assert(hasMetadataHashEntry() && 541 getContext().pImpl->MetadataStore.count(this) && 542 "Shouldn't have called this"); 543 const LLVMContextImpl::MDMapTy &Info = 544 getContext().pImpl->MetadataStore.find(this)->second; 545 assert(!Info.empty() && "Shouldn't have called this"); 546 547 Result.append(Info.begin(), Info.end()); 548 549 // Sort the resulting array so it is stable. 550 if (Result.size() > 1) 551 array_pod_sort(Result.begin(), Result.end()); 552 } 553 554 555 /// clearMetadataHashEntries - Clear all hashtable-based metadata from 556 /// this instruction. 557 void Instruction::clearMetadataHashEntries() { 558 assert(hasMetadataHashEntry() && "Caller should check"); 559 getContext().pImpl->MetadataStore.erase(this); 560 setHasMetadataHashEntry(false); 561 } 562 563