return ModRef;
}
+ virtual DependenceResult getDependence(const Instruction *First,
+ const Value *FirstPHITranslatedAddr,
+ DependenceQueryFlags FirstFlags,
+ const Instruction *Second,
+ const Value *SecondPHITranslatedAddr,
+ DependenceQueryFlags SecondFlags) {
+ return Unknown;
+ }
+
virtual void deleteValue(Value *V) {}
virtual void copyValue(Value *From, Value *To) {}
// GetElementPtr Instruction Decomposition and Analysis
//===----------------------------------------------------------------------===//
+namespace {
+ enum ExtensionKind {
+ EK_NotExtended,
+ EK_SignExt,
+ EK_ZeroExt
+ };
+
+ struct VariableGEPIndex {
+ const Value *V;
+ ExtensionKind Extension;
+ int64_t Scale;
+ };
+}
+
/// GetLinearExpression - Analyze the specified value as a linear expression:
/// "A*V + B", where A and B are constant integers. Return the scale and offset
-/// values as APInts and return V as a Value*. The incoming Value is known to
-/// have IntegerType. Note that this looks through extends, so the high bits
-/// may not be represented in the result.
+/// values as APInts and return V as a Value*, and return whether we looked
+/// through any sign or zero extends. The incoming Value is known to have
+/// IntegerType and it may already be sign or zero extended.
+///
+/// Note that this looks through extends, so the high bits may not be
+/// represented in the result.
static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset,
- const TargetData *TD, unsigned Depth) {
+ ExtensionKind &Extension,
+ const TargetData &TD, unsigned Depth) {
assert(V->getType()->isIntegerTy() && "Not an integer value");
// Limit our recursion depth.
case Instruction::Or:
// X|C == X+C if all the bits in C are unset in X. Otherwise we can't
// analyze it.
- if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), TD))
+ if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), &TD))
break;
// FALL THROUGH.
case Instruction::Add:
- V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, TD, Depth+1);
+ V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension,
+ TD, Depth+1);
Offset += RHSC->getValue();
return V;
case Instruction::Mul:
- V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, TD, Depth+1);
+ V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension,
+ TD, Depth+1);
Offset *= RHSC->getValue();
Scale *= RHSC->getValue();
return V;
case Instruction::Shl:
- V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, TD, Depth+1);
+ V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension,
+ TD, Depth+1);
Offset <<= RHSC->getValue().getLimitedValue();
Scale <<= RHSC->getValue().getLimitedValue();
return V;
}
// Since GEP indices are sign extended anyway, we don't care about the high
- // bits of a sign extended value - just scales and offsets.
- if (isa<SExtInst>(V)) {
+ // bits of a sign or zero extended value - just scales and offsets. The
+ // extensions have to be consistent though.
+ if ((isa<SExtInst>(V) && Extension != EK_ZeroExt) ||
+ (isa<ZExtInst>(V) && Extension != EK_SignExt)) {
Value *CastOp = cast<CastInst>(V)->getOperand(0);
unsigned OldWidth = Scale.getBitWidth();
unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits();
Scale.trunc(SmallWidth);
Offset.trunc(SmallWidth);
- Value *Result = GetLinearExpression(CastOp, Scale, Offset, TD, Depth+1);
+ Extension = isa<SExtInst>(V) ? EK_SignExt : EK_ZeroExt;
+
+ Value *Result = GetLinearExpression(CastOp, Scale, Offset, Extension,
+ TD, Depth+1);
Scale.zext(OldWidth);
Offset.zext(OldWidth);
+
return Result;
}
///
static const Value *
DecomposeGEPExpression(const Value *V, int64_t &BaseOffs,
- SmallVectorImpl<std::pair<const Value*, int64_t> > &VarIndices,
+ SmallVectorImpl<VariableGEPIndex> &VarIndices,
const TargetData *TD) {
// Limit recursion depth to limit compile time in crazy cases.
unsigned MaxLookup = 6;
// If we are lacking TargetData information, we can't compute the offets of
// elements computed by GEPs. However, we can handle bitcast equivalent
// GEPs.
- if (!TD) {
+ if (TD == 0) {
if (!GEPOp->hasAllZeroIndices())
return V;
V = GEPOp->getOperand(0);
}
uint64_t Scale = TD->getTypeAllocSize(*GTI);
+ ExtensionKind Extension = EK_NotExtended;
- // Use GetLinearExpression to decompose the index into a C1*V+C2 form.
+ // If the integer type is smaller than the pointer size, it is implicitly
+ // sign extended to pointer size.
unsigned Width = cast<IntegerType>(Index->getType())->getBitWidth();
+ if (TD->getPointerSizeInBits() > Width)
+ Extension = EK_SignExt;
+
+ // Use GetLinearExpression to decompose the index into a C1*V+C2 form.
APInt IndexScale(Width, 0), IndexOffset(Width, 0);
- Index = GetLinearExpression(Index, IndexScale, IndexOffset, TD, 0);
+ Index = GetLinearExpression(Index, IndexScale, IndexOffset, Extension,
+ *TD, 0);
// The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale.
// This gives us an aggregate computation of (C1*Scale)*V + C2*Scale.
// A[x][x] -> x*16 + x*4 -> x*20
// This also ensures that 'x' only appears in the index list once.
for (unsigned i = 0, e = VarIndices.size(); i != e; ++i) {
- if (VarIndices[i].first == Index) {
- Scale += VarIndices[i].second;
+ if (VarIndices[i].V == Index &&
+ VarIndices[i].Extension == Extension) {
+ Scale += VarIndices[i].Scale;
VarIndices.erase(VarIndices.begin()+i);
break;
}
Scale >>= ShiftBits;
}
- if (Scale)
- VarIndices.push_back(std::make_pair(Index, Scale));
+ if (Scale) {
+ VariableGEPIndex Entry = {Index, Extension, Scale};
+ VarIndices.push_back(Entry);
+ }
}
// Analyze the base pointer next.
/// decomposed GetElementPtr instructions GEP1 and GEP2 which have common base
/// pointers. Subtract the GEP2 indices from GEP1 to find the symbolic
/// difference between the two pointers.
-static void GetIndexDifference(
- SmallVectorImpl<std::pair<const Value*, int64_t> > &Dest,
- const SmallVectorImpl<std::pair<const Value*, int64_t> > &Src) {
+static void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
+ const SmallVectorImpl<VariableGEPIndex> &Src) {
if (Src.empty()) return;
for (unsigned i = 0, e = Src.size(); i != e; ++i) {
- const Value *V = Src[i].first;
- int64_t Scale = Src[i].second;
+ const Value *V = Src[i].V;
+ ExtensionKind Extension = Src[i].Extension;
+ int64_t Scale = Src[i].Scale;
// Find V in Dest. This is N^2, but pointer indices almost never have more
// than a few variable indexes.
for (unsigned j = 0, e = Dest.size(); j != e; ++j) {
- if (Dest[j].first != V) continue;
+ if (Dest[j].V != V || Dest[j].Extension != Extension) continue;
// If we found it, subtract off Scale V's from the entry in Dest. If it
// goes to zero, remove the entry.
- if (Dest[j].second != Scale)
- Dest[j].second -= Scale;
+ if (Dest[j].Scale != Scale)
+ Dest[j].Scale -= Scale;
else
Dest.erase(Dest.begin()+j);
Scale = 0;
}
// If we didn't consume this entry, add it to the end of the Dest list.
- if (Scale)
- Dest.push_back(std::make_pair(V, -Scale));
+ if (Scale) {
+ VariableGEPIndex Entry = { V, Extension, -Scale };
+ Dest.push_back(Entry);
+ }
}
}
/// For use when the call site is not known.
virtual ModRefBehavior getModRefBehavior(const Function *F);
+ virtual DependenceResult getDependence(const Instruction *First,
+ const Value *FirstPHITranslatedAddr,
+ DependenceQueryFlags FirstFlags,
+ const Instruction *Second,
+ const Value *SecondPHITranslatedAddr,
+ DependenceQueryFlags SecondFlags);
+
/// getAdjustedAnalysisPointer - This method is used when a pass implements
/// an analysis interface through multiple inheritance. If needed, it
/// should override this to adjust the this pointer as needed for the
return AliasAnalysis::getModRefInfo(CS, P, Size);
}
+AliasAnalysis::DependenceResult
+BasicAliasAnalysis::getDependence(const Instruction *First,
+ const Value *FirstPHITranslatedAddr,
+ DependenceQueryFlags FirstFlags,
+ const Instruction *Second,
+ const Value *SecondPHITranslatedAddr,
+ DependenceQueryFlags SecondFlags) {
+ // We don't have anything special to say yet.
+ return getDependenceViaModRefInfo(First, FirstPHITranslatedAddr, FirstFlags,
+ Second, SecondPHITranslatedAddr, SecondFlags);
+}
/// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction
/// against another pointer. We know that V1 is a GEP, but we don't know
return MayAlias;
int64_t GEP1BaseOffset;
- SmallVector<std::pair<const Value*, int64_t>, 4> GEP1VariableIndices;
+ SmallVector<VariableGEPIndex, 4> GEP1VariableIndices;
// If we have two gep instructions with must-alias'ing base pointers, figure
// out if the indexes to the GEP tell us anything about the derived pointer.
DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD);
int64_t GEP2BaseOffset;
- SmallVector<std::pair<const Value*, int64_t>, 4> GEP2VariableIndices;
+ SmallVector<VariableGEPIndex, 4> GEP2VariableIndices;
const Value *GEP2BasePtr =
DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD);
// provides an offset of 4 bytes (assuming a <= 4 byte access).
for (unsigned i = 0, e = GEP1VariableIndices.size();
i != e && GEP1BaseOffset;++i)
- if (int64_t RemovedOffset = GEP1BaseOffset/GEP1VariableIndices[i].second)
- GEP1BaseOffset -= RemovedOffset*GEP1VariableIndices[i].second;
+ if (int64_t RemovedOffset = GEP1BaseOffset/GEP1VariableIndices[i].Scale)
+ GEP1BaseOffset -= RemovedOffset*GEP1VariableIndices[i].Scale;
// If our known offset is bigger than the access size, we know we don't have
// an alias.
projects / oota-llvm.git / blobdiff