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