#include "llvm/ADT/SmallString.h"
#include "llvm/ADT/STLExtras.h"
#include "SymbolTableListTraitsImpl.h"
+#include "llvm/Support/ConstantRange.h"
#include "llvm/Support/LeakDetector.h"
#include "llvm/Support/ValueHandle.h"
using namespace llvm;
void MDString::anchor() { }
-MDString::MDString(LLVMContext &C, StringRef S)
- : Value(Type::getMetadataTy(C), Value::MDStringVal), Str(S) {}
+MDString::MDString(LLVMContext &C)
+ : Value(Type::getMetadataTy(C), Value::MDStringVal) {}
MDString *MDString::get(LLVMContext &Context, StringRef Str) {
LLVMContextImpl *pImpl = Context.pImpl;
- StringMapEntry<MDString *> &Entry =
+ StringMapEntry<Value*> &Entry =
pImpl->MDStringCache.GetOrCreateValue(Str);
- MDString *&S = Entry.getValue();
- if (!S) S = new MDString(Context, Entry.getKey());
- return S;
+ Value *&S = Entry.getValue();
+ if (!S) S = new MDString(Context);
+ S->setValueName(&Entry);
+ return cast<MDString>(S);
}
//===----------------------------------------------------------------------===//
// Use CallbackVH to hold MDNode operands.
namespace llvm {
class MDNodeOperand : public CallbackVH {
- MDNode *Parent;
+ MDNode *getParent() {
+ MDNodeOperand *Cur = this;
+
+ while (Cur->getValPtrInt() != 1)
+ --Cur;
+
+ assert(Cur->getValPtrInt() == 1 &&
+ "Couldn't find the beginning of the operand list!");
+ return reinterpret_cast<MDNode*>(Cur) - 1;
+ }
+
public:
- MDNodeOperand(Value *V, MDNode *P) : CallbackVH(V), Parent(P) {}
+ MDNodeOperand(Value *V) : CallbackVH(V) {}
~MDNodeOperand() {}
void set(Value *V) {
- setValPtr(V);
+ unsigned IsFirst = this->getValPtrInt();
+ this->setValPtr(V);
+ this->setAsFirstOperand(IsFirst);
}
+ /// setAsFirstOperand - Accessor method to mark the operand as the first in
+ /// the list.
+ void setAsFirstOperand(unsigned V) { this->setValPtrInt(V); }
+
virtual void deleted();
virtual void allUsesReplacedWith(Value *NV);
};
void MDNodeOperand::deleted() {
- Parent->replaceOperand(this, 0);
+ getParent()->replaceOperand(this, 0);
}
void MDNodeOperand::allUsesReplacedWith(Value *NV) {
- Parent->replaceOperand(this, NV);
+ getParent()->replaceOperand(this, NV);
}
-
-
//===----------------------------------------------------------------------===//
// MDNode implementation.
//
static MDNodeOperand *getOperandPtr(MDNode *N, unsigned Op) {
// Use <= instead of < to permit a one-past-the-end address.
assert(Op <= N->getNumOperands() && "Invalid operand number");
- return reinterpret_cast<MDNodeOperand*>(N+1)+Op;
+ return reinterpret_cast<MDNodeOperand*>(N + 1) + Op;
}
void MDNode::replaceOperandWith(unsigned i, Value *Val) {
// Initialize the operand list, which is co-allocated on the end of the node.
unsigned i = 0;
for (MDNodeOperand *Op = getOperandPtr(this, 0), *E = Op+NumOperands;
- Op != E; ++Op, ++i)
- new (Op) MDNodeOperand(Vals[i], this);
-}
+ Op != E; ++Op, ++i) {
+ new (Op) MDNodeOperand(Vals[i]);
+ // Mark the first MDNodeOperand as being the first in the list of operands.
+ if (i == 0)
+ Op->setAsFirstOperand(1);
+ }
+}
/// ~MDNode - Destroy MDNode.
MDNode::~MDNode() {
// destroy - Delete this node. Only when there are no uses.
void MDNode::destroy() {
setValueSubclassData(getSubclassDataFromValue() | DestroyFlag);
- // Placement delete, the free the memory.
+ // Placement delete, then free the memory.
this->~MDNode();
free(this);
}
}
// Coallocate space for the node and Operands together, then placement new.
- void *Ptr = malloc(sizeof(MDNode)+Vals.size()*sizeof(MDNodeOperand));
+ void *Ptr = malloc(sizeof(MDNode) + Vals.size() * sizeof(MDNodeOperand));
N = new (Ptr) MDNode(Context, Vals, isFunctionLocal);
+ // Cache the operand hash.
+ N->Hash = ID.ComputeHash();
+
// InsertPoint will have been set by the FindNodeOrInsertPos call.
pImpl->MDNodeSet.InsertNode(N, InsertPoint);
MDNode *MDNode::getTemporary(LLVMContext &Context, ArrayRef<Value*> Vals) {
MDNode *N =
- (MDNode *)malloc(sizeof(MDNode)+Vals.size()*sizeof(MDNodeOperand));
+ (MDNode *)malloc(sizeof(MDNode) + Vals.size() * sizeof(MDNodeOperand));
N = new (N) MDNode(Context, Vals, FL_No);
N->setValueSubclassData(N->getSubclassDataFromValue() |
NotUniquedBit);
return;
}
+ // Cache the operand hash.
+ Hash = ID.ComputeHash();
// InsertPoint will have been set by the FindNodeOrInsertPos call.
pImpl->MDNodeSet.InsertNode(this, InsertPoint);
}
}
+MDNode *MDNode::getMostGenericTBAA(MDNode *A, MDNode *B) {
+ if (!A || !B)
+ return NULL;
+
+ if (A == B)
+ return A;
+
+ SmallVector<MDNode *, 4> PathA;
+ MDNode *T = A;
+ while (T) {
+ PathA.push_back(T);
+ T = T->getNumOperands() >= 2 ? cast_or_null<MDNode>(T->getOperand(1)) : 0;
+ }
+
+ SmallVector<MDNode *, 4> PathB;
+ T = B;
+ while (T) {
+ PathB.push_back(T);
+ T = T->getNumOperands() >= 2 ? cast_or_null<MDNode>(T->getOperand(1)) : 0;
+ }
+
+ int IA = PathA.size() - 1;
+ int IB = PathB.size() - 1;
+
+ MDNode *Ret = 0;
+ while (IA >= 0 && IB >=0) {
+ if (PathA[IA] == PathB[IB])
+ Ret = PathA[IA];
+ else
+ break;
+ --IA;
+ --IB;
+ }
+ return Ret;
+}
+
+MDNode *MDNode::getMostGenericFPMath(MDNode *A, MDNode *B) {
+ if (!A || !B)
+ return NULL;
+
+ APFloat AVal = cast<ConstantFP>(A->getOperand(0))->getValueAPF();
+ APFloat BVal = cast<ConstantFP>(B->getOperand(0))->getValueAPF();
+ if (AVal.compare(BVal) == APFloat::cmpLessThan)
+ return A;
+ return B;
+}
+
+static bool isContiguous(const ConstantRange &A, const ConstantRange &B) {
+ return A.getUpper() == B.getLower() || A.getLower() == B.getUpper();
+}
+
+static bool canBeMerged(const ConstantRange &A, const ConstantRange &B) {
+ return !A.intersectWith(B).isEmptySet() || isContiguous(A, B);
+}
+
+static bool tryMergeRange(SmallVector<Value*, 4> &EndPoints, ConstantInt *Low,
+ ConstantInt *High) {
+ ConstantRange NewRange(Low->getValue(), High->getValue());
+ unsigned Size = EndPoints.size();
+ APInt LB = cast<ConstantInt>(EndPoints[Size - 2])->getValue();
+ APInt LE = cast<ConstantInt>(EndPoints[Size - 1])->getValue();
+ ConstantRange LastRange(LB, LE);
+ if (canBeMerged(NewRange, LastRange)) {
+ ConstantRange Union = LastRange.unionWith(NewRange);
+ Type *Ty = High->getType();
+ EndPoints[Size - 2] = ConstantInt::get(Ty, Union.getLower());
+ EndPoints[Size - 1] = ConstantInt::get(Ty, Union.getUpper());
+ return true;
+ }
+ return false;
+}
+
+static void addRange(SmallVector<Value*, 4> &EndPoints, ConstantInt *Low,
+ ConstantInt *High) {
+ if (!EndPoints.empty())
+ if (tryMergeRange(EndPoints, Low, High))
+ return;
+
+ EndPoints.push_back(Low);
+ EndPoints.push_back(High);
+}
+
+MDNode *MDNode::getMostGenericRange(MDNode *A, MDNode *B) {
+ // Given two ranges, we want to compute the union of the ranges. This
+ // is slightly complitade by having to combine the intervals and merge
+ // the ones that overlap.
+
+ if (!A || !B)
+ return NULL;
+
+ if (A == B)
+ return A;
+
+ // First, walk both lists in older of the lower boundary of each interval.
+ // At each step, try to merge the new interval to the last one we adedd.
+ SmallVector<Value*, 4> EndPoints;
+ int AI = 0;
+ int BI = 0;
+ int AN = A->getNumOperands() / 2;
+ int BN = B->getNumOperands() / 2;
+ while (AI < AN && BI < BN) {
+ ConstantInt *ALow = cast<ConstantInt>(A->getOperand(2 * AI));
+ ConstantInt *BLow = cast<ConstantInt>(B->getOperand(2 * BI));
+
+ if (ALow->getValue().slt(BLow->getValue())) {
+ addRange(EndPoints, ALow, cast<ConstantInt>(A->getOperand(2 * AI + 1)));
+ ++AI;
+ } else {
+ addRange(EndPoints, BLow, cast<ConstantInt>(B->getOperand(2 * BI + 1)));
+ ++BI;
+ }
+ }
+ while (AI < AN) {
+ addRange(EndPoints, cast<ConstantInt>(A->getOperand(2 * AI)),
+ cast<ConstantInt>(A->getOperand(2 * AI + 1)));
+ ++AI;
+ }
+ while (BI < BN) {
+ addRange(EndPoints, cast<ConstantInt>(B->getOperand(2 * BI)),
+ cast<ConstantInt>(B->getOperand(2 * BI + 1)));
+ ++BI;
+ }
+
+ // If we have more than 2 ranges (4 endpoints) we have to try to merge
+ // the last and first ones.
+ unsigned Size = EndPoints.size();
+ if (Size > 4) {
+ ConstantInt *FB = cast<ConstantInt>(EndPoints[0]);
+ ConstantInt *FE = cast<ConstantInt>(EndPoints[1]);
+ if (tryMergeRange(EndPoints, FB, FE)) {
+ for (unsigned i = 0; i < Size - 2; ++i) {
+ EndPoints[i] = EndPoints[i + 2];
+ }
+ EndPoints.resize(Size - 2);
+ }
+ }
+
+ // If in the end we have a single range, it is possible that it is now the
+ // full range. Just drop the metadata in that case.
+ if (EndPoints.size() == 2) {
+ ConstantRange Range(cast<ConstantInt>(EndPoints[0])->getValue(),
+ cast<ConstantInt>(EndPoints[1])->getValue());
+ if (Range.isFullSet())
+ return NULL;
+ }
+
+ return MDNode::get(A->getContext(), EndPoints);
+}
+
//===----------------------------------------------------------------------===//
// NamedMDNode implementation.
//
projects / oota-llvm.git / blobdiff