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