Index: llvm/lib/Analysis/BasicAliasAnalysis.cpp =================================================================== --- llvm/lib/Analysis/BasicAliasAnalysis.cpp +++ llvm/lib/Analysis/BasicAliasAnalysis.cpp @@ -1088,8 +1088,6 @@ auto *Ty = GetElementPtrInst::getIndexedType( GEP1->getSourceElementType(), IntermediateIndices); - StructType *LastIndexedStruct = dyn_cast(Ty); - if (isa(Ty) || isa(Ty)) { // We know that: // - both GEPs begin indexing from the exact same pointer; @@ -1143,44 +1141,7 @@ } else if (isKnownNonEqual(GEP1LastIdx, GEP2LastIdx, DL)) return NoAlias; } - return MayAlias; - } else if (!LastIndexedStruct || !C1 || !C2) { - return MayAlias; } - - if (C1->getValue().getActiveBits() > 64 || - C2->getValue().getActiveBits() > 64) - return MayAlias; - - // We know that: - // - both GEPs begin indexing from the exact same pointer; - // - the last indices in both GEPs are constants, indexing into a struct; - // - said indices are different, hence, the pointed-to fields are different; - // - both GEPs only index through arrays prior to that. - // - // This lets us determine that the struct that GEP1 indexes into and the - // struct that GEP2 indexes into must either precisely overlap or be - // completely disjoint. Because they cannot partially overlap, indexing into - // different non-overlapping fields of the struct will never alias. - - // Therefore, the only remaining thing needed to show that both GEPs can't - // alias is that the fields are not overlapping. - const StructLayout *SL = DL.getStructLayout(LastIndexedStruct); - const uint64_t StructSize = SL->getSizeInBytes(); - const uint64_t V1Off = SL->getElementOffset(C1->getZExtValue()); - const uint64_t V2Off = SL->getElementOffset(C2->getZExtValue()); - - auto EltsDontOverlap = [StructSize](uint64_t V1Off, uint64_t V1Size, - uint64_t V2Off, uint64_t V2Size) { - return V1Off < V2Off && V1Off + V1Size <= V2Off && - ((V2Off + V2Size <= StructSize) || - (V2Off + V2Size - StructSize <= V1Off)); - }; - - if (EltsDontOverlap(V1Off, V1Size, V2Off, V2Size) || - EltsDontOverlap(V2Off, V2Size, V1Off, V1Size)) - return NoAlias; - return MayAlias; } @@ -1393,15 +1354,14 @@ } if (!DecompGEP1.VarIndices.empty()) { - APInt Modulo(MaxPointerSize, 0); + APInt GCD; bool AllPositive = true; for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) { - - // Try to distinguish something like &A[i][1] against &A[42][0]. - // Grab the least significant bit set in any of the scales. We - // don't need std::abs here (even if the scale's negative) as we'll - // be ^'ing Modulo with itself later. - Modulo |= DecompGEP1.VarIndices[i].Scale; + const APInt &Scale = DecompGEP1.VarIndices[i].Scale; + if (i == 0) + GCD = Scale.abs(); + else + GCD = APIntOps::GreatestCommonDivisor(GCD, Scale.abs()); if (AllPositive) { // If the Value could change between cycles, then any reasoning about @@ -1423,21 +1383,19 @@ // If the variable begins with a zero then we know it's // positive, regardless of whether the value is signed or // unsigned. - APInt Scale = DecompGEP1.VarIndices[i].Scale; AllPositive = (SignKnownZero && Scale.sge(0)) || (SignKnownOne && Scale.slt(0)); } } - Modulo = Modulo ^ (Modulo & (Modulo - 1)); - - // We can compute the difference between the two addresses - // mod Modulo. Check whether that difference guarantees that the - // two locations do not alias. - APInt ModOffset = GEP1BaseOffset & (Modulo - 1); + // We can compute the difference between the two addresses mod GCD. Check + // whether that difference guarantees that the two locations do not alias. + APInt ModOffset = GEP1BaseOffset.srem(GCD); + if (ModOffset.isNegative()) + ModOffset += GCD; // We want mod, not rem. if (V1Size != LocationSize::unknown() && V2Size != LocationSize::unknown() && ModOffset.uge(V2Size.getValue()) && - (Modulo - ModOffset).uge(V1Size.getValue())) + (GCD - ModOffset).uge(V1Size.getValue())) return NoAlias; // If we know all the variables are positive, then GEP1 >= GEP1BasePtr. Index: llvm/test/Analysis/BasicAA/struct-geps.ll =================================================================== --- llvm/test/Analysis/BasicAA/struct-geps.ll +++ llvm/test/Analysis/BasicAA/struct-geps.ll @@ -106,14 +106,14 @@ ; CHECK-DAG: NoAlias: i32* %y, i32* %y2 ; CHECK-DAG: NoAlias: i32* %z, i32* %z2 -; CHECK-DAG: MayAlias: i32* %x, i32* %y2 -; CHECK-DAG: MayAlias: i32* %x, i32* %z2 +; CHECK-DAG: NoAlias: i32* %x, i32* %y2 +; CHECK-DAG: NoAlias: i32* %x, i32* %z2 -; CHECK-DAG: MayAlias: i32* %x2, i32* %y -; CHECK-DAG: MayAlias: i32* %y, i32* %z2 +; CHECK-DAG: NoAlias: i32* %x2, i32* %y +; CHECK-DAG: NoAlias: i32* %y, i32* %z2 -; CHECK-DAG: MayAlias: i32* %x2, i32* %z -; CHECK-DAG: MayAlias: i32* %y2, i32* %z +; CHECK-DAG: NoAlias: i32* %x2, i32* %z +; CHECK-DAG: NoAlias: i32* %y2, i32* %z define void @test_same_underlying_object_same_indices(%struct* %st, i64 %i, i64 %j, i64 %k) { %st2 = getelementptr %struct, %struct* %st, i32 10 @@ -132,14 +132,14 @@ ; CHECK-DAG: MayAlias: i32* %y, i32* %y2 ; CHECK-DAG: MayAlias: i32* %z, i32* %z2 -; CHECK-DAG: MayAlias: i32* %x, i32* %y2 -; CHECK-DAG: MayAlias: i32* %x, i32* %z2 +; CHECK-DAG: NoAlias: i32* %x, i32* %y2 +; CHECK-DAG: NoAlias: i32* %x, i32* %z2 -; CHECK-DAG: MayAlias: i32* %x2, i32* %y -; CHECK-DAG: MayAlias: i32* %y, i32* %z2 +; CHECK-DAG: NoAlias: i32* %x2, i32* %y +; CHECK-DAG: NoAlias: i32* %y, i32* %z2 -; CHECK-DAG: MayAlias: i32* %x2, i32* %z -; CHECK-DAG: MayAlias: i32* %y2, i32* %z +; CHECK-DAG: NoAlias: i32* %x2, i32* %z +; CHECK-DAG: NoAlias: i32* %y2, i32* %z define void @test_same_underlying_object_different_indices(%struct* %st, i64 %i1, i64 %j1, i64 %k1, i64 %i2, i64 %k2, i64 %j2) { %st2 = getelementptr %struct, %struct* %st, i32 10