Metadata.cpp revision 249259
1249259Sdim//===-- Metadata.cpp - Implement Metadata classes -------------------------===// 2249259Sdim// 3249259Sdim// The LLVM Compiler Infrastructure 4249259Sdim// 5249259Sdim// This file is distributed under the University of Illinois Open Source 6249259Sdim// License. See LICENSE.TXT for details. 7249259Sdim// 8249259Sdim//===----------------------------------------------------------------------===// 9249259Sdim// 10249259Sdim// This file implements the Metadata classes. 11249259Sdim// 12249259Sdim//===----------------------------------------------------------------------===// 13249259Sdim 14249259Sdim#include "llvm/IR/Metadata.h" 15249259Sdim#include "LLVMContextImpl.h" 16249259Sdim#include "SymbolTableListTraitsImpl.h" 17249259Sdim#include "llvm/ADT/DenseMap.h" 18249259Sdim#include "llvm/ADT/STLExtras.h" 19249259Sdim#include "llvm/ADT/SmallString.h" 20249259Sdim#include "llvm/ADT/StringMap.h" 21249259Sdim#include "llvm/IR/Instruction.h" 22249259Sdim#include "llvm/IR/LLVMContext.h" 23249259Sdim#include "llvm/IR/Module.h" 24249259Sdim#include "llvm/Support/ConstantRange.h" 25249259Sdim#include "llvm/Support/LeakDetector.h" 26249259Sdim#include "llvm/Support/ValueHandle.h" 27249259Sdimusing namespace llvm; 28249259Sdim 29249259Sdim//===----------------------------------------------------------------------===// 30249259Sdim// MDString implementation. 31249259Sdim// 32249259Sdim 33249259Sdimvoid MDString::anchor() { } 34249259Sdim 35249259SdimMDString::MDString(LLVMContext &C) 36249259Sdim : Value(Type::getMetadataTy(C), Value::MDStringVal) {} 37249259Sdim 38249259SdimMDString *MDString::get(LLVMContext &Context, StringRef Str) { 39249259Sdim LLVMContextImpl *pImpl = Context.pImpl; 40249259Sdim StringMapEntry<Value*> &Entry = 41249259Sdim pImpl->MDStringCache.GetOrCreateValue(Str); 42249259Sdim Value *&S = Entry.getValue(); 43249259Sdim if (!S) S = new MDString(Context); 44249259Sdim S->setValueName(&Entry); 45249259Sdim return cast<MDString>(S); 46249259Sdim} 47249259Sdim 48249259Sdim//===----------------------------------------------------------------------===// 49249259Sdim// MDNodeOperand implementation. 50249259Sdim// 51249259Sdim 52249259Sdim// Use CallbackVH to hold MDNode operands. 53249259Sdimnamespace llvm { 54249259Sdimclass MDNodeOperand : public CallbackVH { 55249259Sdim MDNode *getParent() { 56249259Sdim MDNodeOperand *Cur = this; 57249259Sdim 58249259Sdim while (Cur->getValPtrInt() != 1) 59249259Sdim --Cur; 60249259Sdim 61249259Sdim assert(Cur->getValPtrInt() == 1 && 62249259Sdim "Couldn't find the beginning of the operand list!"); 63249259Sdim return reinterpret_cast<MDNode*>(Cur) - 1; 64249259Sdim } 65249259Sdim 66249259Sdimpublic: 67249259Sdim MDNodeOperand(Value *V) : CallbackVH(V) {} 68249259Sdim ~MDNodeOperand() {} 69249259Sdim 70249259Sdim void set(Value *V) { 71249259Sdim unsigned IsFirst = this->getValPtrInt(); 72249259Sdim this->setValPtr(V); 73249259Sdim this->setAsFirstOperand(IsFirst); 74249259Sdim } 75249259Sdim 76249259Sdim /// setAsFirstOperand - Accessor method to mark the operand as the first in 77249259Sdim /// the list. 78249259Sdim void setAsFirstOperand(unsigned V) { this->setValPtrInt(V); } 79249259Sdim 80249259Sdim virtual void deleted(); 81249259Sdim virtual void allUsesReplacedWith(Value *NV); 82249259Sdim}; 83249259Sdim} // end namespace llvm. 84249259Sdim 85249259Sdim 86249259Sdimvoid MDNodeOperand::deleted() { 87249259Sdim getParent()->replaceOperand(this, 0); 88249259Sdim} 89249259Sdim 90249259Sdimvoid MDNodeOperand::allUsesReplacedWith(Value *NV) { 91249259Sdim getParent()->replaceOperand(this, NV); 92249259Sdim} 93249259Sdim 94249259Sdim//===----------------------------------------------------------------------===// 95249259Sdim// MDNode implementation. 96249259Sdim// 97249259Sdim 98249259Sdim/// getOperandPtr - Helper function to get the MDNodeOperand's coallocated on 99249259Sdim/// the end of the MDNode. 100249259Sdimstatic MDNodeOperand *getOperandPtr(MDNode *N, unsigned Op) { 101249259Sdim // Use <= instead of < to permit a one-past-the-end address. 102249259Sdim assert(Op <= N->getNumOperands() && "Invalid operand number"); 103249259Sdim return reinterpret_cast<MDNodeOperand*>(N + 1) + Op; 104249259Sdim} 105249259Sdim 106249259Sdimvoid MDNode::replaceOperandWith(unsigned i, Value *Val) { 107249259Sdim MDNodeOperand *Op = getOperandPtr(this, i); 108249259Sdim replaceOperand(Op, Val); 109249259Sdim} 110249259Sdim 111249259SdimMDNode::MDNode(LLVMContext &C, ArrayRef<Value*> Vals, bool isFunctionLocal) 112249259Sdim: Value(Type::getMetadataTy(C), Value::MDNodeVal) { 113249259Sdim NumOperands = Vals.size(); 114249259Sdim 115249259Sdim if (isFunctionLocal) 116249259Sdim setValueSubclassData(getSubclassDataFromValue() | FunctionLocalBit); 117249259Sdim 118249259Sdim // Initialize the operand list, which is co-allocated on the end of the node. 119249259Sdim unsigned i = 0; 120249259Sdim for (MDNodeOperand *Op = getOperandPtr(this, 0), *E = Op+NumOperands; 121249259Sdim Op != E; ++Op, ++i) { 122249259Sdim new (Op) MDNodeOperand(Vals[i]); 123249259Sdim 124249259Sdim // Mark the first MDNodeOperand as being the first in the list of operands. 125249259Sdim if (i == 0) 126249259Sdim Op->setAsFirstOperand(1); 127249259Sdim } 128249259Sdim} 129249259Sdim 130249259Sdim/// ~MDNode - Destroy MDNode. 131249259SdimMDNode::~MDNode() { 132249259Sdim assert((getSubclassDataFromValue() & DestroyFlag) != 0 && 133249259Sdim "Not being destroyed through destroy()?"); 134249259Sdim LLVMContextImpl *pImpl = getType()->getContext().pImpl; 135249259Sdim if (isNotUniqued()) { 136249259Sdim pImpl->NonUniquedMDNodes.erase(this); 137249259Sdim } else { 138249259Sdim pImpl->MDNodeSet.RemoveNode(this); 139249259Sdim } 140249259Sdim 141249259Sdim // Destroy the operands. 142249259Sdim for (MDNodeOperand *Op = getOperandPtr(this, 0), *E = Op+NumOperands; 143249259Sdim Op != E; ++Op) 144249259Sdim Op->~MDNodeOperand(); 145249259Sdim} 146249259Sdim 147249259Sdimstatic const Function *getFunctionForValue(Value *V) { 148249259Sdim if (!V) return NULL; 149249259Sdim if (Instruction *I = dyn_cast<Instruction>(V)) { 150249259Sdim BasicBlock *BB = I->getParent(); 151249259Sdim return BB ? BB->getParent() : 0; 152249259Sdim } 153249259Sdim if (Argument *A = dyn_cast<Argument>(V)) 154249259Sdim return A->getParent(); 155249259Sdim if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) 156249259Sdim return BB->getParent(); 157249259Sdim if (MDNode *MD = dyn_cast<MDNode>(V)) 158249259Sdim return MD->getFunction(); 159249259Sdim return NULL; 160249259Sdim} 161249259Sdim 162249259Sdim#ifndef NDEBUG 163249259Sdimstatic const Function *assertLocalFunction(const MDNode *N) { 164249259Sdim if (!N->isFunctionLocal()) return 0; 165249259Sdim 166249259Sdim // FIXME: This does not handle cyclic function local metadata. 167249259Sdim const Function *F = 0, *NewF = 0; 168249259Sdim for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 169249259Sdim if (Value *V = N->getOperand(i)) { 170249259Sdim if (MDNode *MD = dyn_cast<MDNode>(V)) 171249259Sdim NewF = assertLocalFunction(MD); 172249259Sdim else 173249259Sdim NewF = getFunctionForValue(V); 174249259Sdim } 175249259Sdim if (F == 0) 176249259Sdim F = NewF; 177249259Sdim else 178249259Sdim assert((NewF == 0 || F == NewF) &&"inconsistent function-local metadata"); 179249259Sdim } 180249259Sdim return F; 181249259Sdim} 182249259Sdim#endif 183249259Sdim 184249259Sdim// getFunction - If this metadata is function-local and recursively has a 185249259Sdim// function-local operand, return the first such operand's parent function. 186249259Sdim// Otherwise, return null. getFunction() should not be used for performance- 187249259Sdim// critical code because it recursively visits all the MDNode's operands. 188249259Sdimconst Function *MDNode::getFunction() const { 189249259Sdim#ifndef NDEBUG 190249259Sdim return assertLocalFunction(this); 191249259Sdim#else 192249259Sdim if (!isFunctionLocal()) return NULL; 193249259Sdim for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 194249259Sdim if (const Function *F = getFunctionForValue(getOperand(i))) 195249259Sdim return F; 196249259Sdim return NULL; 197249259Sdim#endif 198249259Sdim} 199249259Sdim 200249259Sdim// destroy - Delete this node. Only when there are no uses. 201249259Sdimvoid MDNode::destroy() { 202249259Sdim setValueSubclassData(getSubclassDataFromValue() | DestroyFlag); 203249259Sdim // Placement delete, then free the memory. 204249259Sdim this->~MDNode(); 205249259Sdim free(this); 206249259Sdim} 207249259Sdim 208249259Sdim/// isFunctionLocalValue - Return true if this is a value that would require a 209249259Sdim/// function-local MDNode. 210249259Sdimstatic bool isFunctionLocalValue(Value *V) { 211249259Sdim return isa<Instruction>(V) || isa<Argument>(V) || isa<BasicBlock>(V) || 212249259Sdim (isa<MDNode>(V) && cast<MDNode>(V)->isFunctionLocal()); 213249259Sdim} 214249259Sdim 215249259SdimMDNode *MDNode::getMDNode(LLVMContext &Context, ArrayRef<Value*> Vals, 216249259Sdim FunctionLocalness FL, bool Insert) { 217249259Sdim LLVMContextImpl *pImpl = Context.pImpl; 218249259Sdim 219249259Sdim // Add all the operand pointers. Note that we don't have to add the 220249259Sdim // isFunctionLocal bit because that's implied by the operands. 221249259Sdim // Note that if the operands are later nulled out, the node will be 222249259Sdim // removed from the uniquing map. 223249259Sdim FoldingSetNodeID ID; 224249259Sdim for (unsigned i = 0; i != Vals.size(); ++i) 225249259Sdim ID.AddPointer(Vals[i]); 226249259Sdim 227249259Sdim void *InsertPoint; 228249259Sdim MDNode *N = pImpl->MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint); 229249259Sdim 230249259Sdim if (N || !Insert) 231249259Sdim return N; 232249259Sdim 233249259Sdim bool isFunctionLocal = false; 234249259Sdim switch (FL) { 235249259Sdim case FL_Unknown: 236249259Sdim for (unsigned i = 0; i != Vals.size(); ++i) { 237249259Sdim Value *V = Vals[i]; 238249259Sdim if (!V) continue; 239249259Sdim if (isFunctionLocalValue(V)) { 240249259Sdim isFunctionLocal = true; 241249259Sdim break; 242249259Sdim } 243249259Sdim } 244249259Sdim break; 245249259Sdim case FL_No: 246249259Sdim isFunctionLocal = false; 247249259Sdim break; 248249259Sdim case FL_Yes: 249249259Sdim isFunctionLocal = true; 250249259Sdim break; 251249259Sdim } 252249259Sdim 253249259Sdim // Coallocate space for the node and Operands together, then placement new. 254249259Sdim void *Ptr = malloc(sizeof(MDNode) + Vals.size() * sizeof(MDNodeOperand)); 255249259Sdim N = new (Ptr) MDNode(Context, Vals, isFunctionLocal); 256249259Sdim 257249259Sdim // Cache the operand hash. 258249259Sdim N->Hash = ID.ComputeHash(); 259249259Sdim 260249259Sdim // InsertPoint will have been set by the FindNodeOrInsertPos call. 261249259Sdim pImpl->MDNodeSet.InsertNode(N, InsertPoint); 262249259Sdim 263249259Sdim return N; 264249259Sdim} 265249259Sdim 266249259SdimMDNode *MDNode::get(LLVMContext &Context, ArrayRef<Value*> Vals) { 267249259Sdim return getMDNode(Context, Vals, FL_Unknown); 268249259Sdim} 269249259Sdim 270249259SdimMDNode *MDNode::getWhenValsUnresolved(LLVMContext &Context, 271249259Sdim ArrayRef<Value*> Vals, 272249259Sdim bool isFunctionLocal) { 273249259Sdim return getMDNode(Context, Vals, isFunctionLocal ? FL_Yes : FL_No); 274249259Sdim} 275249259Sdim 276249259SdimMDNode *MDNode::getIfExists(LLVMContext &Context, ArrayRef<Value*> Vals) { 277249259Sdim return getMDNode(Context, Vals, FL_Unknown, false); 278249259Sdim} 279249259Sdim 280249259SdimMDNode *MDNode::getTemporary(LLVMContext &Context, ArrayRef<Value*> Vals) { 281249259Sdim MDNode *N = 282249259Sdim (MDNode *)malloc(sizeof(MDNode) + Vals.size() * sizeof(MDNodeOperand)); 283249259Sdim N = new (N) MDNode(Context, Vals, FL_No); 284249259Sdim N->setValueSubclassData(N->getSubclassDataFromValue() | 285249259Sdim NotUniquedBit); 286249259Sdim LeakDetector::addGarbageObject(N); 287249259Sdim return N; 288249259Sdim} 289249259Sdim 290249259Sdimvoid MDNode::deleteTemporary(MDNode *N) { 291249259Sdim assert(N->use_empty() && "Temporary MDNode has uses!"); 292249259Sdim assert(!N->getContext().pImpl->MDNodeSet.RemoveNode(N) && 293249259Sdim "Deleting a non-temporary uniqued node!"); 294249259Sdim assert(!N->getContext().pImpl->NonUniquedMDNodes.erase(N) && 295249259Sdim "Deleting a non-temporary non-uniqued node!"); 296249259Sdim assert((N->getSubclassDataFromValue() & NotUniquedBit) && 297249259Sdim "Temporary MDNode does not have NotUniquedBit set!"); 298249259Sdim assert((N->getSubclassDataFromValue() & DestroyFlag) == 0 && 299249259Sdim "Temporary MDNode has DestroyFlag set!"); 300249259Sdim LeakDetector::removeGarbageObject(N); 301249259Sdim N->destroy(); 302249259Sdim} 303249259Sdim 304249259Sdim/// getOperand - Return specified operand. 305249259SdimValue *MDNode::getOperand(unsigned i) const { 306249259Sdim assert(i < getNumOperands() && "Invalid operand number"); 307249259Sdim return *getOperandPtr(const_cast<MDNode*>(this), i); 308249259Sdim} 309249259Sdim 310249259Sdimvoid MDNode::Profile(FoldingSetNodeID &ID) const { 311249259Sdim // Add all the operand pointers. Note that we don't have to add the 312249259Sdim // isFunctionLocal bit because that's implied by the operands. 313249259Sdim // Note that if the operands are later nulled out, the node will be 314249259Sdim // removed from the uniquing map. 315249259Sdim for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 316249259Sdim ID.AddPointer(getOperand(i)); 317249259Sdim} 318249259Sdim 319249259Sdimvoid MDNode::setIsNotUniqued() { 320249259Sdim setValueSubclassData(getSubclassDataFromValue() | NotUniquedBit); 321249259Sdim LLVMContextImpl *pImpl = getType()->getContext().pImpl; 322249259Sdim pImpl->NonUniquedMDNodes.insert(this); 323249259Sdim} 324249259Sdim 325249259Sdim// Replace value from this node's operand list. 326249259Sdimvoid MDNode::replaceOperand(MDNodeOperand *Op, Value *To) { 327249259Sdim Value *From = *Op; 328249259Sdim 329249259Sdim // If is possible that someone did GV->RAUW(inst), replacing a global variable 330249259Sdim // with an instruction or some other function-local object. If this is a 331249259Sdim // non-function-local MDNode, it can't point to a function-local object. 332249259Sdim // Handle this case by implicitly dropping the MDNode reference to null. 333249259Sdim // Likewise if the MDNode is function-local but for a different function. 334249259Sdim if (To && isFunctionLocalValue(To)) { 335249259Sdim if (!isFunctionLocal()) 336249259Sdim To = 0; 337249259Sdim else { 338249259Sdim const Function *F = getFunction(); 339249259Sdim const Function *FV = getFunctionForValue(To); 340249259Sdim // Metadata can be function-local without having an associated function. 341249259Sdim // So only consider functions to have changed if non-null. 342249259Sdim if (F && FV && F != FV) 343249259Sdim To = 0; 344249259Sdim } 345249259Sdim } 346249259Sdim 347249259Sdim if (From == To) 348249259Sdim return; 349249259Sdim 350249259Sdim // Update the operand. 351249259Sdim Op->set(To); 352249259Sdim 353249259Sdim // If this node is already not being uniqued (because one of the operands 354249259Sdim // already went to null), then there is nothing else to do here. 355249259Sdim if (isNotUniqued()) return; 356249259Sdim 357249259Sdim LLVMContextImpl *pImpl = getType()->getContext().pImpl; 358249259Sdim 359249259Sdim // Remove "this" from the context map. FoldingSet doesn't have to reprofile 360249259Sdim // this node to remove it, so we don't care what state the operands are in. 361249259Sdim pImpl->MDNodeSet.RemoveNode(this); 362249259Sdim 363249259Sdim // If we are dropping an argument to null, we choose to not unique the MDNode 364249259Sdim // anymore. This commonly occurs during destruction, and uniquing these 365249259Sdim // brings little reuse. Also, this means we don't need to include 366249259Sdim // isFunctionLocal bits in FoldingSetNodeIDs for MDNodes. 367249259Sdim if (To == 0) { 368249259Sdim setIsNotUniqued(); 369249259Sdim return; 370249259Sdim } 371249259Sdim 372249259Sdim // Now that the node is out of the folding set, get ready to reinsert it. 373249259Sdim // First, check to see if another node with the same operands already exists 374249259Sdim // in the set. If so, then this node is redundant. 375249259Sdim FoldingSetNodeID ID; 376249259Sdim Profile(ID); 377249259Sdim void *InsertPoint; 378249259Sdim if (MDNode *N = pImpl->MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint)) { 379249259Sdim replaceAllUsesWith(N); 380249259Sdim destroy(); 381249259Sdim return; 382249259Sdim } 383249259Sdim 384249259Sdim // Cache the operand hash. 385249259Sdim Hash = ID.ComputeHash(); 386249259Sdim // InsertPoint will have been set by the FindNodeOrInsertPos call. 387249259Sdim pImpl->MDNodeSet.InsertNode(this, InsertPoint); 388249259Sdim 389249259Sdim // If this MDValue was previously function-local but no longer is, clear 390249259Sdim // its function-local flag. 391249259Sdim if (isFunctionLocal() && !isFunctionLocalValue(To)) { 392249259Sdim bool isStillFunctionLocal = false; 393249259Sdim for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { 394249259Sdim Value *V = getOperand(i); 395249259Sdim if (!V) continue; 396249259Sdim if (isFunctionLocalValue(V)) { 397249259Sdim isStillFunctionLocal = true; 398249259Sdim break; 399249259Sdim } 400249259Sdim } 401249259Sdim if (!isStillFunctionLocal) 402249259Sdim setValueSubclassData(getSubclassDataFromValue() & ~FunctionLocalBit); 403249259Sdim } 404249259Sdim} 405249259Sdim 406249259SdimMDNode *MDNode::getMostGenericTBAA(MDNode *A, MDNode *B) { 407249259Sdim if (!A || !B) 408249259Sdim return NULL; 409249259Sdim 410249259Sdim if (A == B) 411249259Sdim return A; 412249259Sdim 413249259Sdim SmallVector<MDNode *, 4> PathA; 414249259Sdim MDNode *T = A; 415249259Sdim while (T) { 416249259Sdim PathA.push_back(T); 417249259Sdim T = T->getNumOperands() >= 2 ? cast_or_null<MDNode>(T->getOperand(1)) : 0; 418249259Sdim } 419249259Sdim 420249259Sdim SmallVector<MDNode *, 4> PathB; 421249259Sdim T = B; 422249259Sdim while (T) { 423249259Sdim PathB.push_back(T); 424249259Sdim T = T->getNumOperands() >= 2 ? cast_or_null<MDNode>(T->getOperand(1)) : 0; 425249259Sdim } 426249259Sdim 427249259Sdim int IA = PathA.size() - 1; 428249259Sdim int IB = PathB.size() - 1; 429249259Sdim 430249259Sdim MDNode *Ret = 0; 431249259Sdim while (IA >= 0 && IB >=0) { 432249259Sdim if (PathA[IA] == PathB[IB]) 433249259Sdim Ret = PathA[IA]; 434249259Sdim else 435249259Sdim break; 436249259Sdim --IA; 437249259Sdim --IB; 438249259Sdim } 439249259Sdim return Ret; 440249259Sdim} 441249259Sdim 442249259SdimMDNode *MDNode::getMostGenericFPMath(MDNode *A, MDNode *B) { 443249259Sdim if (!A || !B) 444249259Sdim return NULL; 445249259Sdim 446249259Sdim APFloat AVal = cast<ConstantFP>(A->getOperand(0))->getValueAPF(); 447249259Sdim APFloat BVal = cast<ConstantFP>(B->getOperand(0))->getValueAPF(); 448249259Sdim if (AVal.compare(BVal) == APFloat::cmpLessThan) 449249259Sdim return A; 450249259Sdim return B; 451249259Sdim} 452249259Sdim 453249259Sdimstatic bool isContiguous(const ConstantRange &A, const ConstantRange &B) { 454249259Sdim return A.getUpper() == B.getLower() || A.getLower() == B.getUpper(); 455249259Sdim} 456249259Sdim 457249259Sdimstatic bool canBeMerged(const ConstantRange &A, const ConstantRange &B) { 458249259Sdim return !A.intersectWith(B).isEmptySet() || isContiguous(A, B); 459249259Sdim} 460249259Sdim 461249259Sdimstatic bool tryMergeRange(SmallVector<Value*, 4> &EndPoints, ConstantInt *Low, 462249259Sdim ConstantInt *High) { 463249259Sdim ConstantRange NewRange(Low->getValue(), High->getValue()); 464249259Sdim unsigned Size = EndPoints.size(); 465249259Sdim APInt LB = cast<ConstantInt>(EndPoints[Size - 2])->getValue(); 466249259Sdim APInt LE = cast<ConstantInt>(EndPoints[Size - 1])->getValue(); 467249259Sdim ConstantRange LastRange(LB, LE); 468249259Sdim if (canBeMerged(NewRange, LastRange)) { 469249259Sdim ConstantRange Union = LastRange.unionWith(NewRange); 470249259Sdim Type *Ty = High->getType(); 471249259Sdim EndPoints[Size - 2] = ConstantInt::get(Ty, Union.getLower()); 472249259Sdim EndPoints[Size - 1] = ConstantInt::get(Ty, Union.getUpper()); 473249259Sdim return true; 474249259Sdim } 475249259Sdim return false; 476249259Sdim} 477249259Sdim 478249259Sdimstatic void addRange(SmallVector<Value*, 4> &EndPoints, ConstantInt *Low, 479249259Sdim ConstantInt *High) { 480249259Sdim if (!EndPoints.empty()) 481249259Sdim if (tryMergeRange(EndPoints, Low, High)) 482249259Sdim return; 483249259Sdim 484249259Sdim EndPoints.push_back(Low); 485249259Sdim EndPoints.push_back(High); 486249259Sdim} 487249259Sdim 488249259SdimMDNode *MDNode::getMostGenericRange(MDNode *A, MDNode *B) { 489249259Sdim // Given two ranges, we want to compute the union of the ranges. This 490249259Sdim // is slightly complitade by having to combine the intervals and merge 491249259Sdim // the ones that overlap. 492249259Sdim 493249259Sdim if (!A || !B) 494249259Sdim return NULL; 495249259Sdim 496249259Sdim if (A == B) 497249259Sdim return A; 498249259Sdim 499249259Sdim // First, walk both lists in older of the lower boundary of each interval. 500249259Sdim // At each step, try to merge the new interval to the last one we adedd. 501249259Sdim SmallVector<Value*, 4> EndPoints; 502249259Sdim int AI = 0; 503249259Sdim int BI = 0; 504249259Sdim int AN = A->getNumOperands() / 2; 505249259Sdim int BN = B->getNumOperands() / 2; 506249259Sdim while (AI < AN && BI < BN) { 507249259Sdim ConstantInt *ALow = cast<ConstantInt>(A->getOperand(2 * AI)); 508249259Sdim ConstantInt *BLow = cast<ConstantInt>(B->getOperand(2 * BI)); 509249259Sdim 510249259Sdim if (ALow->getValue().slt(BLow->getValue())) { 511249259Sdim addRange(EndPoints, ALow, cast<ConstantInt>(A->getOperand(2 * AI + 1))); 512249259Sdim ++AI; 513249259Sdim } else { 514249259Sdim addRange(EndPoints, BLow, cast<ConstantInt>(B->getOperand(2 * BI + 1))); 515249259Sdim ++BI; 516249259Sdim } 517249259Sdim } 518249259Sdim while (AI < AN) { 519249259Sdim addRange(EndPoints, cast<ConstantInt>(A->getOperand(2 * AI)), 520249259Sdim cast<ConstantInt>(A->getOperand(2 * AI + 1))); 521249259Sdim ++AI; 522249259Sdim } 523249259Sdim while (BI < BN) { 524249259Sdim addRange(EndPoints, cast<ConstantInt>(B->getOperand(2 * BI)), 525249259Sdim cast<ConstantInt>(B->getOperand(2 * BI + 1))); 526249259Sdim ++BI; 527249259Sdim } 528249259Sdim 529249259Sdim // If we have more than 2 ranges (4 endpoints) we have to try to merge 530249259Sdim // the last and first ones. 531249259Sdim unsigned Size = EndPoints.size(); 532249259Sdim if (Size > 4) { 533249259Sdim ConstantInt *FB = cast<ConstantInt>(EndPoints[0]); 534249259Sdim ConstantInt *FE = cast<ConstantInt>(EndPoints[1]); 535249259Sdim if (tryMergeRange(EndPoints, FB, FE)) { 536249259Sdim for (unsigned i = 0; i < Size - 2; ++i) { 537249259Sdim EndPoints[i] = EndPoints[i + 2]; 538249259Sdim } 539249259Sdim EndPoints.resize(Size - 2); 540249259Sdim } 541249259Sdim } 542249259Sdim 543249259Sdim // If in the end we have a single range, it is possible that it is now the 544249259Sdim // full range. Just drop the metadata in that case. 545249259Sdim if (EndPoints.size() == 2) { 546249259Sdim ConstantRange Range(cast<ConstantInt>(EndPoints[0])->getValue(), 547249259Sdim cast<ConstantInt>(EndPoints[1])->getValue()); 548249259Sdim if (Range.isFullSet()) 549249259Sdim return NULL; 550249259Sdim } 551249259Sdim 552249259Sdim return MDNode::get(A->getContext(), EndPoints); 553249259Sdim} 554249259Sdim 555249259Sdim//===----------------------------------------------------------------------===// 556249259Sdim// NamedMDNode implementation. 557249259Sdim// 558249259Sdim 559249259Sdimstatic SmallVector<TrackingVH<MDNode>, 4> &getNMDOps(void *Operands) { 560249259Sdim return *(SmallVector<TrackingVH<MDNode>, 4>*)Operands; 561249259Sdim} 562249259Sdim 563249259SdimNamedMDNode::NamedMDNode(const Twine &N) 564249259Sdim : Name(N.str()), Parent(0), 565249259Sdim Operands(new SmallVector<TrackingVH<MDNode>, 4>()) { 566249259Sdim} 567249259Sdim 568249259SdimNamedMDNode::~NamedMDNode() { 569249259Sdim dropAllReferences(); 570249259Sdim delete &getNMDOps(Operands); 571249259Sdim} 572249259Sdim 573249259Sdim/// getNumOperands - Return number of NamedMDNode operands. 574249259Sdimunsigned NamedMDNode::getNumOperands() const { 575249259Sdim return (unsigned)getNMDOps(Operands).size(); 576249259Sdim} 577249259Sdim 578249259Sdim/// getOperand - Return specified operand. 579249259SdimMDNode *NamedMDNode::getOperand(unsigned i) const { 580249259Sdim assert(i < getNumOperands() && "Invalid Operand number!"); 581249259Sdim return dyn_cast<MDNode>(&*getNMDOps(Operands)[i]); 582249259Sdim} 583249259Sdim 584249259Sdim/// addOperand - Add metadata Operand. 585249259Sdimvoid NamedMDNode::addOperand(MDNode *M) { 586249259Sdim assert(!M->isFunctionLocal() && 587249259Sdim "NamedMDNode operands must not be function-local!"); 588249259Sdim getNMDOps(Operands).push_back(TrackingVH<MDNode>(M)); 589249259Sdim} 590249259Sdim 591249259Sdim/// eraseFromParent - Drop all references and remove the node from parent 592249259Sdim/// module. 593249259Sdimvoid NamedMDNode::eraseFromParent() { 594249259Sdim getParent()->eraseNamedMetadata(this); 595249259Sdim} 596249259Sdim 597249259Sdim/// dropAllReferences - Remove all uses and clear node vector. 598249259Sdimvoid NamedMDNode::dropAllReferences() { 599249259Sdim getNMDOps(Operands).clear(); 600249259Sdim} 601249259Sdim 602249259Sdim/// getName - Return a constant reference to this named metadata's name. 603249259SdimStringRef NamedMDNode::getName() const { 604249259Sdim return StringRef(Name); 605249259Sdim} 606249259Sdim 607249259Sdim//===----------------------------------------------------------------------===// 608249259Sdim// Instruction Metadata method implementations. 609249259Sdim// 610249259Sdim 611249259Sdimvoid Instruction::setMetadata(StringRef Kind, MDNode *Node) { 612249259Sdim if (Node == 0 && !hasMetadata()) return; 613249259Sdim setMetadata(getContext().getMDKindID(Kind), Node); 614249259Sdim} 615249259Sdim 616249259SdimMDNode *Instruction::getMetadataImpl(StringRef Kind) const { 617249259Sdim return getMetadataImpl(getContext().getMDKindID(Kind)); 618249259Sdim} 619249259Sdim 620249259Sdim/// setMetadata - Set the metadata of of the specified kind to the specified 621249259Sdim/// node. This updates/replaces metadata if already present, or removes it if 622249259Sdim/// Node is null. 623249259Sdimvoid Instruction::setMetadata(unsigned KindID, MDNode *Node) { 624249259Sdim if (Node == 0 && !hasMetadata()) return; 625249259Sdim 626249259Sdim // Handle 'dbg' as a special case since it is not stored in the hash table. 627249259Sdim if (KindID == LLVMContext::MD_dbg) { 628249259Sdim DbgLoc = DebugLoc::getFromDILocation(Node); 629249259Sdim return; 630249259Sdim } 631249259Sdim 632249259Sdim // Handle the case when we're adding/updating metadata on an instruction. 633249259Sdim if (Node) { 634249259Sdim LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this]; 635249259Sdim assert(!Info.empty() == hasMetadataHashEntry() && 636249259Sdim "HasMetadata bit is wonked"); 637249259Sdim if (Info.empty()) { 638249259Sdim setHasMetadataHashEntry(true); 639249259Sdim } else { 640249259Sdim // Handle replacement of an existing value. 641249259Sdim for (unsigned i = 0, e = Info.size(); i != e; ++i) 642249259Sdim if (Info[i].first == KindID) { 643249259Sdim Info[i].second = Node; 644249259Sdim return; 645249259Sdim } 646249259Sdim } 647249259Sdim 648249259Sdim // No replacement, just add it to the list. 649249259Sdim Info.push_back(std::make_pair(KindID, Node)); 650249259Sdim return; 651249259Sdim } 652249259Sdim 653249259Sdim // Otherwise, we're removing metadata from an instruction. 654249259Sdim assert((hasMetadataHashEntry() == 655249259Sdim getContext().pImpl->MetadataStore.count(this)) && 656249259Sdim "HasMetadata bit out of date!"); 657249259Sdim if (!hasMetadataHashEntry()) 658249259Sdim return; // Nothing to remove! 659249259Sdim LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this]; 660249259Sdim 661249259Sdim // Common case is removing the only entry. 662249259Sdim if (Info.size() == 1 && Info[0].first == KindID) { 663249259Sdim getContext().pImpl->MetadataStore.erase(this); 664249259Sdim setHasMetadataHashEntry(false); 665249259Sdim return; 666249259Sdim } 667249259Sdim 668249259Sdim // Handle removal of an existing value. 669249259Sdim for (unsigned i = 0, e = Info.size(); i != e; ++i) 670249259Sdim if (Info[i].first == KindID) { 671249259Sdim Info[i] = Info.back(); 672249259Sdim Info.pop_back(); 673249259Sdim assert(!Info.empty() && "Removing last entry should be handled above"); 674249259Sdim return; 675249259Sdim } 676249259Sdim // Otherwise, removing an entry that doesn't exist on the instruction. 677249259Sdim} 678249259Sdim 679249259SdimMDNode *Instruction::getMetadataImpl(unsigned KindID) const { 680249259Sdim // Handle 'dbg' as a special case since it is not stored in the hash table. 681249259Sdim if (KindID == LLVMContext::MD_dbg) 682249259Sdim return DbgLoc.getAsMDNode(getContext()); 683249259Sdim 684249259Sdim if (!hasMetadataHashEntry()) return 0; 685249259Sdim 686249259Sdim LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this]; 687249259Sdim assert(!Info.empty() && "bit out of sync with hash table"); 688249259Sdim 689249259Sdim for (LLVMContextImpl::MDMapTy::iterator I = Info.begin(), E = Info.end(); 690249259Sdim I != E; ++I) 691249259Sdim if (I->first == KindID) 692249259Sdim return I->second; 693249259Sdim return 0; 694249259Sdim} 695249259Sdim 696249259Sdimvoid Instruction::getAllMetadataImpl(SmallVectorImpl<std::pair<unsigned, 697249259Sdim MDNode*> > &Result) const { 698249259Sdim Result.clear(); 699249259Sdim 700249259Sdim // Handle 'dbg' as a special case since it is not stored in the hash table. 701249259Sdim if (!DbgLoc.isUnknown()) { 702249259Sdim Result.push_back(std::make_pair((unsigned)LLVMContext::MD_dbg, 703249259Sdim DbgLoc.getAsMDNode(getContext()))); 704249259Sdim if (!hasMetadataHashEntry()) return; 705249259Sdim } 706249259Sdim 707249259Sdim assert(hasMetadataHashEntry() && 708249259Sdim getContext().pImpl->MetadataStore.count(this) && 709249259Sdim "Shouldn't have called this"); 710249259Sdim const LLVMContextImpl::MDMapTy &Info = 711249259Sdim getContext().pImpl->MetadataStore.find(this)->second; 712249259Sdim assert(!Info.empty() && "Shouldn't have called this"); 713249259Sdim 714249259Sdim Result.append(Info.begin(), Info.end()); 715249259Sdim 716249259Sdim // Sort the resulting array so it is stable. 717249259Sdim if (Result.size() > 1) 718249259Sdim array_pod_sort(Result.begin(), Result.end()); 719249259Sdim} 720249259Sdim 721249259Sdimvoid Instruction:: 722249259SdimgetAllMetadataOtherThanDebugLocImpl(SmallVectorImpl<std::pair<unsigned, 723249259Sdim MDNode*> > &Result) const { 724249259Sdim Result.clear(); 725249259Sdim assert(hasMetadataHashEntry() && 726249259Sdim getContext().pImpl->MetadataStore.count(this) && 727249259Sdim "Shouldn't have called this"); 728249259Sdim const LLVMContextImpl::MDMapTy &Info = 729249259Sdim getContext().pImpl->MetadataStore.find(this)->second; 730249259Sdim assert(!Info.empty() && "Shouldn't have called this"); 731249259Sdim Result.append(Info.begin(), Info.end()); 732249259Sdim 733249259Sdim // Sort the resulting array so it is stable. 734249259Sdim if (Result.size() > 1) 735249259Sdim array_pod_sort(Result.begin(), Result.end()); 736249259Sdim} 737249259Sdim 738249259Sdim/// clearMetadataHashEntries - Clear all hashtable-based metadata from 739249259Sdim/// this instruction. 740249259Sdimvoid Instruction::clearMetadataHashEntries() { 741249259Sdim assert(hasMetadataHashEntry() && "Caller should check"); 742249259Sdim getContext().pImpl->MetadataStore.erase(this); 743249259Sdim setHasMetadataHashEntry(false); 744249259Sdim} 745249259Sdim 746