Index: llvm/lib/Analysis/BasicAliasAnalysis.cpp
===================================================================
--- llvm/lib/Analysis/BasicAliasAnalysis.cpp
+++ llvm/lib/Analysis/BasicAliasAnalysis.cpp
@@ -1315,15 +1315,16 @@
         (-DecompGEP1.Offset).uge(V1Size.getValue()))
       return AliasResult::NoAlias;
 
-    if (!Range.isEmptySet()) {
-      // We know that Offset >= MinOffset.
-      // (MinOffset >= V2Size) => (Offset >= V2Size) => NoAlias.
-      if (V2Size.hasValue() && Range.getSignedMin().sge(V2Size.getValue()))
-        return AliasResult::NoAlias;
-
-      // We know that Offset <= MaxOffset.
-      // (MaxOffset <= -V1Size) => (Offset <= -V1Size) => NoAlias.
-      if (V1Size.hasValue() && Range.getSignedMax().sle(-V1Size.getValue()))
+    if (V1Size.hasValue() && V2Size.hasValue()) {
+      // Range currently holds possible offsets. Convert it into a range of
+      // potentially accessed bytes and intersect it with potentially accessed
+      // bytes of the other access.
+      unsigned BW = Range.getBitWidth();
+      Range = Range.add(ConstantRange(APInt(BW, 0),
+                                      APInt(BW, V1Size.getValue())));
+      ConstantRange Range2 =
+          ConstantRange(APInt(BW, 0), APInt(BW, V2Size.getValue()));
+      if (Range.intersectWith(Range2).isEmptySet())
         return AliasResult::NoAlias;
     }
 
Index: llvm/test/Analysis/BasicAA/range.ll
===================================================================
--- llvm/test/Analysis/BasicAA/range.ll
+++ llvm/test/Analysis/BasicAA/range.ll
@@ -196,13 +196,13 @@
   ret void
 }
 
-; TODO: p.neg1 and p.o.1 don't alias, even though the addition o+1 may overflow.
+; p.neg1 and p.o.1 don't alias, even though the addition o+1 may overflow.
 ; While it makes INT_MIN a possible offset, offset -1 is not possible.
 ; CHECK-LABEL: Function: benign_overflow
 ; CHECK: MayAlias: i8* %p, i8* %p.o
 ; CHECK: MayAlias: i8* %p.neg1, i8* %p.o
 ; CHECK: MayAlias: i8* %p, i8* %p.o.1
-; CHECK: MayAlias: i8* %p.neg1, i8* %p.o.1
+; CHECK: NoAlias: i8* %p.neg1, i8* %p.o.1
 ; CHECK: NoAlias:  i8* %p.o, i8* %p.o.1
 define void @benign_overflow(i8* %p, i64 %o) {
   %c = icmp sge i64 %o, -1