# Changeset View

Changeset View

# Standalone View

Standalone View

# 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 | |||||

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 Actionsfinal '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 |

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.