Index: include/llvm/Analysis/BasicAliasAnalysis.h =================================================================== --- include/llvm/Analysis/BasicAliasAnalysis.h +++ include/llvm/Analysis/BasicAliasAnalysis.h @@ -176,8 +176,10 @@ const DataLayout &DL, AssumptionCache *AC, DominatorTree *DT); static bool isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp, - const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject, - LocationSize ObjectAccessSize); + const DecomposedGEP &DecompGEP, + const DecomposedGEP &DecompObject, + LocationSize ObjectAccessSize, + APInt ASSize); /// A Heuristic for aliasGEP that searches for a constant offset /// between the variables. Index: lib/Analysis/BasicAliasAnalysis.cpp =================================================================== --- lib/Analysis/BasicAliasAnalysis.cpp +++ lib/Analysis/BasicAliasAnalysis.cpp @@ -1246,9 +1246,10 @@ // point into the same object. But since %f0 points to the beginning of %alloca, // the highest %f1 can be is (%alloca + 3). This means %random can not be higher // than (%alloca - 1), and so is not inbounds, a contradiction. -bool BasicAAResult::isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp, - const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject, - LocationSize MaybeObjectAccessSize) { +bool BasicAAResult::isGEPBaseAtNegativeOffset( + const GEPOperator *GEPOp, const DecomposedGEP &DecompGEP, + const DecomposedGEP &DecompObject, LocationSize MaybeObjectAccessSize, + APInt ASSize) { // If the object access size is unknown, or the GEP isn't inbounds, bail. if (MaybeObjectAccessSize == LocationSize::unknown() || !GEPOp->isInBounds()) return false; @@ -1276,6 +1277,14 @@ APInt GEPBaseOffset = DecompGEP.StructOffset; GEPBaseOffset += DecompGEP.OtherOffset; + // Wrap the offsets around zero if negative, to support the case of the + // object taking up more than half of its address space. + if (ObjectBaseOffset.isNegative()) + ObjectBaseOffset += ASSize; + + if (GEPBaseOffset.isNegative()) + GEPBaseOffset += ASSize; + return GEPBaseOffset.sge(ObjectBaseOffset + (int64_t)ObjectAccessSize); } @@ -1291,6 +1300,8 @@ LocationSize V2Size, const AAMDNodes &V2AAInfo, const Value *UnderlyingV1, const Value *UnderlyingV2) { DecomposedGEP DecompGEP1, DecompGEP2; + unsigned PointerSize = + DL.getPointerSizeInBits(GEP1->getPointerAddressSpace()); unsigned MaxPointerSize = getMaxPointerSize(DL); DecompGEP1.StructOffset = DecompGEP1.OtherOffset = APInt(MaxPointerSize, 0); DecompGEP2.StructOffset = DecompGEP2.OtherOffset = APInt(MaxPointerSize, 0); @@ -1307,11 +1318,17 @@ "DecomposeGEPExpression returned a result different from " "GetUnderlyingObject"); + // Size of the address space modulo pointer size. Used to implement offset + // wraparound. + APInt ASSize = PointerSize == MaxPointerSize + ? APInt::getNullValue(MaxPointerSize) + : APInt::getOneBitSet(MaxPointerSize, PointerSize); + // If the GEP's offset relative to its base is such that the base would // fall below the start of the object underlying V2, then the GEP and V2 // cannot alias. if (!GEP1MaxLookupReached && !GEP2MaxLookupReached && - isGEPBaseAtNegativeOffset(GEP1, DecompGEP1, DecompGEP2, V2Size)) + isGEPBaseAtNegativeOffset(GEP1, DecompGEP1, DecompGEP2, V2Size, ASSize)) return NoAlias; // If we have two gep instructions with must-alias or not-alias'ing base // pointers, figure out if the indexes to the GEP tell us anything about the @@ -1320,7 +1337,7 @@ // Check for the GEP base being at a negative offset, this time in the other // direction. if (!GEP1MaxLookupReached && !GEP2MaxLookupReached && - isGEPBaseAtNegativeOffset(GEP2, DecompGEP2, DecompGEP1, V1Size)) + isGEPBaseAtNegativeOffset(GEP2, DecompGEP2, DecompGEP1, V1Size, ASSize)) return NoAlias; // Do the base pointers alias? AliasResult BaseAlias = @@ -1418,33 +1435,54 @@ // is less than the size of the associated memory object, then we know // that the objects are partially overlapping. If the difference is // greater, we know they do not overlap. + // + // Factoring in the wraparound, there are two differences between the + // pointers: one from GEP1 to V2, and one from V2 back to GEP1 in the same + // direction. Analyze both. if (GEP1BaseOffset != 0 && DecompGEP1.VarIndices.empty()) { - if (GEP1BaseOffset.sge(0)) { - if (V2Size != LocationSize::unknown()) { - if (GEP1BaseOffset.ult(V2Size.getValue())) - return PartialAlias; - return NoAlias; - } + // True if in both cases concluded NoAlias. + bool BothNoAlias = true; + + // Look at the distance between V2 and GEP1 (with wraparound): + // + + + // | BaseOffset | + // ---------------->| + // |-->V2Size |-------> V1Size + // V2 GEP1 + if (V2Size != LocationSize::unknown()) { + if ((GEP1BaseOffset.isNonNegative() ? GEP1BaseOffset + : GEP1BaseOffset + ASSize) + .ult(V2Size.getValue())) + return PartialAlias; } else { - // We have the situation where: - // + + - // | BaseOffset | - // ---------------->| - // |-->V1Size |-------> V2Size - // GEP1 V2 - // We need to know that V2Size is not unknown, otherwise we might have - // stripped a gep with negative index ('gep , -1, ...). - if (V1Size != LocationSize::unknown() && - V2Size != LocationSize::unknown()) { - if ((-GEP1BaseOffset).ult(V1Size.getValue())) - return PartialAlias; - return NoAlias; - } + BothNoAlias = false; } + + // Look at the distance between GEP1 and V2 (with wraparound): + // + + + // | BaseOffset | + // ---------------->| + // |-->V1Size |-------> V2Size + // GEP1 V2 + // We need to know that V2Size is not unknown, otherwise we might have + // stripped a gep with negative index ('gep , -1, ...). + if (V1Size != LocationSize::unknown() && + V2Size != LocationSize::unknown()) { + if ((GEP1BaseOffset.isNonNegative() ? ASSize - GEP1BaseOffset + : -GEP1BaseOffset) + .ult(V1Size.getValue())) + return PartialAlias; + } else { + BothNoAlias = false; + } + + if (BothNoAlias) + return NoAlias; } if (!DecompGEP1.VarIndices.empty()) { APInt Modulo(MaxPointerSize, 0); + APInt MaxVarOffset(MaxPointerSize, 0); bool AllPositive = true; for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) { @@ -1476,6 +1514,11 @@ APInt Scale = DecompGEP1.VarIndices[i].Scale; AllPositive = (SignKnownZero && Scale.sge(0)) || (SignKnownOne && Scale.slt(0)); + + // Compute the maximum value of the offset for this index. + MaxVarOffset += (SignKnownZero ? ~Known.Zero : Known.One) + .sextOrSelf(MaxPointerSize) * + Scale.sextOrSelf(MaxPointerSize); } } @@ -1491,11 +1534,18 @@ return NoAlias; // If we know all the variables are positive, then GEP1 >= GEP1BasePtr. - // If GEP1BasePtr > V2 (GEP1BaseOffset > 0) then we know the pointers - // don't alias if V2Size can fit in the gap between V2 and GEP1BasePtr. - if (AllPositive && GEP1BaseOffset.sgt(0) && + // If V2Size can fit in the gap between V2 and GEP1BasePtr (with optional + // wraparound), and V1 can fit in the gap between GEP1 and V2 (with + // optional wraparound), then we know the pointers don't alias. + if (AllPositive && V1Size != LocationSize::unknown() && V2Size != LocationSize::unknown() && - GEP1BaseOffset.uge(V2Size.getValue())) + (GEP1BaseOffset.isNonNegative() ? GEP1BaseOffset + : GEP1BaseOffset + ASSize) + .uge(V2Size.getValue()) && + (GEP1BaseOffset.isNonNegative() ? ASSize - GEP1BaseOffset + : -GEP1BaseOffset) + .uge(MaxVarOffset.uadd_sat( + APInt(MaxPointerSize, V1Size.getValue())))) return NoAlias; if (constantOffsetHeuristic(DecompGEP1.VarIndices, V1Size, V2Size, Index: test/Analysis/BasicAA/cs-cs.ll =================================================================== --- test/Analysis/BasicAA/cs-cs.ll +++ test/Analysis/BasicAA/cs-cs.ll @@ -273,9 +273,9 @@ ; CHECK-LABEL: Function: test8 ; CHECK: NoModRef: Ptr: i8* %p <-> call void @an_inaccessiblememonly_func() ; CHECK: NoModRef: Ptr: i8* %q <-> call void @an_inaccessiblememonly_func() -; CHECK: NoModRef: Ptr: i8* %p <-> call void @an_inaccessibleorargmemonly_func(i8* %q) +; CHECK: Both ModRef: Ptr: i8* %p <-> call void @an_inaccessibleorargmemonly_func(i8* %q) ; CHECK: Both ModRef (MustAlias): Ptr: i8* %q <-> call void @an_inaccessibleorargmemonly_func(i8* %q) -; CHECK: NoModRef: Ptr: i8* %p <-> call void @an_argmemonly_func(i8* %q) +; CHECK: Both ModRef: Ptr: i8* %p <-> call void @an_argmemonly_func(i8* %q) ; CHECK: Both ModRef (MustAlias): Ptr: i8* %q <-> call void @an_argmemonly_func(i8* %q) ; CHECK: Just Ref: call void @a_readonly_func(i8* %p) <-> call void @an_inaccessiblememonly_func() ; CHECK: Just Ref: call void @a_readonly_func(i8* %p) <-> call void @an_inaccessibleorargmemonly_func(i8* %q) @@ -368,9 +368,9 @@ ; CHECK: Just Ref: Ptr: i8* %q <-> call void @a_readonly_func(i8* %p) #6 [ "unknown"() ] ; CHECK: NoModRef: Ptr: i8* %p <-> call void @an_inaccessiblememonly_func() #7 [ "unknown"() ] ; CHECK: NoModRef: Ptr: i8* %q <-> call void @an_inaccessiblememonly_func() #7 [ "unknown"() ] -; CHECK: NoModRef: Ptr: i8* %p <-> call void @an_inaccessibleorargmemonly_func(i8* %q) #8 [ "unknown"() ] +; CHECK: Both ModRef: Ptr: i8* %p <-> call void @an_inaccessibleorargmemonly_func(i8* %q) #8 [ "unknown"() ] ; CHECK: Both ModRef (MustAlias): Ptr: i8* %q <-> call void @an_inaccessibleorargmemonly_func(i8* %q) #8 [ "unknown"() ] -; CHECK: NoModRef: Ptr: i8* %p <-> call void @an_argmemonly_func(i8* %q) #9 [ "unknown"() ] +; CHECK: Both ModRef: Ptr: i8* %p <-> call void @an_argmemonly_func(i8* %q) #9 [ "unknown"() ] ; CHECK: Both ModRef (MustAlias): Ptr: i8* %q <-> call void @an_argmemonly_func(i8* %q) #9 [ "unknown"() ] ; CHECK: Just Ref: call void @a_readonly_func(i8* %p) #6 [ "unknown"() ] <-> call void @an_inaccessiblememonly_func() #7 [ "unknown"() ] ; CHECK: Just Ref: call void @a_readonly_func(i8* %p) #6 [ "unknown"() ] <-> call void @an_inaccessibleorargmemonly_func(i8* %q) #8 [ "unknown"() ] Index: test/Analysis/BasicAA/huge-array.ll =================================================================== --- /dev/null +++ test/Analysis/BasicAA/huge-array.ll @@ -0,0 +1,105 @@ +; RUN: opt < %s -basicaa -gvn -S | FileCheck %s + +target datalayout = "p:8:8" + +; CHECK-LABEL: @func8.noalias() +; CHECK: store i16 4, i16* %e +; CHECK-NEXT: store i16 3, i16* %f +; CHECK-NEXT: ret i16 4 +define i16 @func8.noalias() { + %a = alloca [130 x i8] + %c = getelementptr [130 x i8], [130 x i8]* %a, i8 0, i8 -128 + %d = getelementptr [130 x i8], [130 x i8]* %a, i8 0, i8 126 + %e = bitcast i8* %c to i16* + %f = bitcast i8* %d to i16* + store i16 4, i16* %e + store i16 3, i16* %f + %x = load i16, i16* %e + ret i16 %x +} + +; CHECK-LABEL: @func8.alias() +; CHECK: store i16 4, i16* %e +; CHECK-NEXT: store i16 3, i16* %f +; CHECK-NEXT: [[x:%.+]] = load i16, i16* %e +define i16 @func8.alias() { + %a = alloca [130 x i8] + %c = getelementptr [130 x i8], [130 x i8]* %a, i8 0, i8 -128 + %d = getelementptr [130 x i8], [130 x i8]* %a, i8 0, i8 127 + %e = bitcast i8* %c to i16* + %f = bitcast i8* %d to i16* + store i16 4, i16* %e + store i16 3, i16* %f + %x = load i16, i16* %e + ret i16 %x +} + +; CHECK-LABEL: @func16.noalias() +; CHECK: store i32 4, i32* %e +; CHECK-NEXT: store i32 3, i32* %f +; CHECK-NEXT: ret i32 4 +define i32 @func16.noalias() { + %a = alloca [66 x i16] + %b = call [66 x i16]* @get16([66 x i16]* %a) + %c = getelementptr inbounds [66 x i16], [66 x i16]* %a, i8 0, i8 62 + %d = getelementptr inbounds [66 x i16], [66 x i16]* %b, i8 0, i8 64 + %e = bitcast i16* %c to i32* + %f = bitcast i16* %d to i32* + store i32 4, i32* %e + store i32 3, i32* %f + %x = load i32, i32* %e + ret i32 %x +} + +; CHECK-LABEL: @func16.alias() +; CHECK: store i32 4, i32* %e +; CHECK-NEXT: store i32 3, i32* %f +; CHECK-NEXT: [[x:%.+]] = load i32, i32* %e +define i32 @func16.alias() { + %a = alloca [66 x i16] + %b = call [66 x i16]* @get16([66 x i16]* %a) + %c = getelementptr inbounds [66 x i16], [66 x i16]* %a, i8 0, i8 63 + %d = getelementptr inbounds [66 x i16], [66 x i16]* %b, i8 0, i8 64 + %e = bitcast i16* %c to i32* + %f = bitcast i16* %d to i32* + store i32 4, i32* %e + store i32 3, i32* %f + %x = load i32, i32* %e + ret i32 %x +} + +; CHECK-LABEL: @func16.alias1() +; CHECK: store i32 4, i32* %e +; CHECK-NEXT: store i32 3, i32* %f +; CHECK-NEXT: [[x:%.+]] = load i32, i32* %e +define i32 @func16.alias1() { + %a = alloca [66 x i16] + %b = call [66 x i16]* @get16([66 x i16]* %a) + %c = getelementptr inbounds [66 x i16], [66 x i16]* %a, i8 0, i8 64 + %d = getelementptr inbounds [66 x i16], [66 x i16]* %b, i8 0, i8 62 + %e = bitcast i16* %c to i32* + %f = bitcast i16* %d to i32* + store i32 4, i32* %e + store i32 3, i32* %f + %x = load i32, i32* %e + ret i32 %x +} + +; CHECK-LABEL: @func16.alias2() +; CHECK: store i32 4, i32* %e +; CHECK-NEXT: store i32 3, i32* %f +; CHECK-NEXT: [[x:%.+]] = load i32, i32* %e +define i32 @func16.alias2() { + %a = alloca [66 x i16] + %b = call [66 x i16]* @get16([66 x i16]* %a) + %c = getelementptr inbounds [66 x i16], [66 x i16]* %a, i8 0, i8 64 + %d = getelementptr inbounds [66 x i16], [66 x i16]* %b, i8 0, i8 63 + %e = bitcast i16* %c to i32* + %f = bitcast i16* %d to i32* + store i32 4, i32* %e + store i32 3, i32* %f + %x = load i32, i32* %e + ret i32 %x +} + +declare [66 x i16]* @get16([66 x i16]*) Index: test/Analysis/BasicAA/pr34344.ll =================================================================== --- /dev/null +++ test/Analysis/BasicAA/pr34344.ll @@ -0,0 +1,29 @@ +; RUN: opt < %s -basicaa -gvn -S | FileCheck %s --implicit-check-not=undef + +target datalayout = "p:8:8" + +%ty = type i8 +%arrty = type [130 x %ty] + +define void @foo() { +entry: + %array = alloca %arrty, align 1 + br label %for.body + +for.body: ; preds = %entry, %for.body + %i = phi %ty [ 0, %entry ], [ %inc, %for.body ] + %idx = zext %ty %i to i16 + %addr = getelementptr inbounds %arrty, %arrty* %array, i16 0, i16 %idx + store %ty %i, %ty* %addr, align 1 + %inc = add nuw %ty %i, 1 + %exitcond = icmp ne %ty %inc, 130 + br i1 %exitcond, label %for.body, label %for.cond.cleanup + +for.cond.cleanup: ; preds = %for.body + %addr2 = getelementptr inbounds %arrty, %arrty* %array, i16 0, i16 129 + %0 = load %ty, %ty* %addr2, align 1 + tail call void @bar(%ty %0) + ret void +} + +declare void @bar(%ty)