Page MenuHomePhabricator
Differential D12802 Diff 34547 lib/Analysis/BasicAliasAnalysis.cpp

Changeset View

Standalone View

View Options

lib/Analysis/BasicAliasAnalysis.cpp

Show First 20 Lines • Show All 727 Lines • ▼ Show 20 Lines if (V1Size == MemoryLocation::UnknownSize ||
V2Size == MemoryLocation::UnknownSize) V2Size == MemoryLocation::UnknownSize)
return MayAlias; return MayAlias;
ConstantInt *C1 = ConstantInt *C1 =
dyn_cast<ConstantInt>(GEP1->getOperand(GEP1->getNumOperands() - 1)); dyn_cast<ConstantInt>(GEP1->getOperand(GEP1->getNumOperands() - 1));
ConstantInt *C2 = ConstantInt *C2 =
dyn_cast<ConstantInt>(GEP2->getOperand(GEP2->getNumOperands() - 1)); dyn_cast<ConstantInt>(GEP2->getOperand(GEP2->getNumOperands() - 1));
// If the last (struct) indices aren't constants, we can't say anything. // If the last (struct) indices are constants and are equal, the other indices
// If they're identical, the other indices might be also be dynamically // might be also be dynamically equal, so the GEPs can alias.
// equal, so the GEPs can alias. if (C1 && C2 && C1 == C2)
if (!C1 || !C2 || C1 == C2)
return MayAlias; return MayAlias;
// Find the last-indexed type of the GEP, i.e., the type you'd get if // Find the last-indexed type of the GEP, i.e., the type you'd get if
// you stripped the last index. // you stripped the last index.
// On the way, look at each indexed type. If there's something other // On the way, look at each indexed type. If there's something other
// than an array, different indices can lead to different final types. // than an array, different indices can lead to different final types.
SmallVector<Value *, 8> IntermediateIndices; SmallVector<Value *, 8> IntermediateIndices;
// Insert the first index; we don't need to check the type indexed // Insert the first index; we don't need to check the type indexed
// through it as it only drops the pointer indirection. // through it as it only drops the pointer indirection.
assert(GEP1->getNumIndices() > 1 && "Not enough GEP indices to examine"); assert(GEP1->getNumIndices() > 1 && "Not enough GEP indices to examine");
IntermediateIndices.push_back(GEP1->getOperand(1)); IntermediateIndices.push_back(GEP1->getOperand(1));
// Insert all the remaining indices but the last one. // Insert all the remaining indices but the last one.
// Also, check that they all index through arrays. // Also, check that they all index through arrays.
for (unsigned i = 1, e = GEP1->getNumIndices() - 1; i != e; ++i) { for (unsigned i = 1, e = GEP1->getNumIndices() - 1; i != e; ++i) {
if (!isa<ArrayType>(GetElementPtrInst::getIndexedType( if (!isa<ArrayType>(GetElementPtrInst::getIndexedType(
GEP1->getSourceElementType(), IntermediateIndices))) GEP1->getSourceElementType(), IntermediateIndices)))
return MayAlias; return MayAlias;
IntermediateIndices.push_back(GEP1->getOperand(i + 1)); IntermediateIndices.push_back(GEP1->getOperand(i + 1));
} }
StructType *LastIndexedStruct = auto *Ty = GetElementPtrInst::getIndexedType(
dyn_cast<StructType>(GetElementPtrInst::getIndexedType( GEP1->getSourceElementType(), IntermediateIndices);
GEP1->getSourceElementType(), IntermediateIndices)); StructType *LastIndexedStruct = dyn_cast<StructType>(Ty);
if (!LastIndexedStruct) if (isa<SequentialType>(Ty)) {
// We know that:
// - both GEPs begin indexing from the exact same pointer;
// - the last indices in both GEPs are constants, indexing into a sequential
hfinkelUnsubmitted
Not Done
ReplyInline Actions

We don't seem to know that here, only below, because of how you've modified the C1,C2 check above. Here, we know only that we don't have equal constants.

hfinkel: We don't seem to know that here, only below, because of how you've modified the C1,C2 check…
// type (array or pointer);
// - both GEPs only index through arrays prior to that.
//
// Because array indices greater than the number of elements are valid in
// GEPs, unless we know the intermediate indices are identical between
// GEP1 and GEP2 we cannot guarantee that the last indexed arrays don't
// partially overlap.
for (unsigned i = 0, e = GEP1->getNumIndices() - 1; i != e; ++i)
if (GEP1->getOperand(i + 1) != GEP2->getOperand(i + 1))
return MayAlias;
// Now we know that the array/pointer that GEP1 indexes into and that
hfinkelUnsubmitted
Not Done
ReplyInline Actions

final 'that' -> 'the array/pointer', or similar, to eliminate the 'that that'

hfinkel: final 'that' -> 'the array/pointer', or similar, to eliminate the 'that that'
// that GEP2 indexes into must either precisely overlap or be disjoint.
// Because they cannot partially overlap and because fields in an array
// cannot overlap, if we can prove the final indices are different between
// GEP1 and GEP2, we can conclude GEP1 and GEP2 don't alias.
// If the last indices are constants, we've already checked they don't
// equal each other so we can exit early.
if (C1 && C2)
return NoAlias;
if (isKnownNonEqual(GEP1->getOperand(GEP1->getNumOperands() - 1),
GEP2->getOperand(GEP2->getNumOperands() - 1),
DL))
return NoAlias;
return MayAlias; return MayAlias;
} else if (!LastIndexedStruct || !C1 || !C2) {
return MayAlias;
}
// We know that: // We know that:
// - both GEPs begin indexing from the exact same pointer; // - both GEPs begin indexing from the exact same pointer;
// - the last indices in both GEPs are constants, indexing into a struct; // - the last indices in both GEPs are constants, indexing into a struct;
// - said indices are different, hence, the pointed-to fields are different; // - said indices are different, hence, the pointed-to fields are different;
// - both GEPs only index through arrays prior to that. // - both GEPs only index through arrays prior to that.
// //
// This lets us determine that the struct that GEP1 indexes into and the // This lets us determine that the struct that GEP1 indexes into and the
▲ Show 20 Lines • Show All 756 Lines • Show Last 20 Lines