diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
--- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
@@ -31,6 +31,7 @@
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/Constant.h"
+#include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
@@ -1211,13 +1212,35 @@
       return NoAlias;
 
     if (V1Size.hasValue() && V2Size.hasValue()) {
-      // Try to determine whether abs(VarIndex) > 0.
+      // Try to determine the range of values for VarIndex.
+      // VarIndexRange is such that:
+      //    (VarIndex <= -MinAbsVarIndex || MinAbsVarIndex <= VarIndex) &&
+      //    MinVarIndex <= VarIndex && VarIndex <= MaxVarIndex
       Optional<APInt> MinAbsVarIndex;
+      Optional<APInt> MinVarIndex;
+      Optional<APInt> MaxVarIndex;
       if (DecompGEP1.VarIndices.size() == 1) {
-        // VarIndex = Scale*V. If V != 0 then abs(VarIndex) >= abs(Scale).
+        // VarIndex = Scale*V.
         const VariableGEPIndex &Var = DecompGEP1.VarIndices[0];
-        if (isKnownNonZero(Var.V, DL, 0, &AC, Var.CxtI, DT))
+        if (isKnownNonZero(Var.V, DL, 0, &AC, Var.CxtI, DT)) {
+          // If V != 0 then abs(VarIndex) >= abs(Scale).
           MinAbsVarIndex = Var.Scale.abs();
+        }
+        ConstantRange R = computeConstantRange(Var.V, true, &AC, Var.CxtI);
+        if (!R.isFullSet() && !R.isEmptySet()) {
+          // Close the open range.
+          APInt MinV = R.getLower();
+          APInt MaxV = R.getUpper() - 1;
+          // If Scale < 0, inverse the range so that Scale >= 0.
+          if (Var.Scale.isNegative()) {
+            MinV = -MaxV;
+            MaxV = -MinV;
+          }
+          MinVarIndex =
+              Var.Scale.abs() * MinV.sextOrTrunc(Var.Scale.getBitWidth());
+          MaxVarIndex =
+              Var.Scale.abs() * MaxV.sextOrTrunc(Var.Scale.getBitWidth());
+        }
       } else if (DecompGEP1.VarIndices.size() == 2) {
         // VarIndex = Scale*V0 + (-Scale)*V1.
         // If V0 != V1 then abs(VarIndex) >= abs(Scale).
@@ -1235,12 +1258,29 @@
         // The constant offset will have added at least +/-MinAbsVarIndex to it.
         APInt OffsetLo = DecompGEP1.Offset - *MinAbsVarIndex;
         APInt OffsetHi = DecompGEP1.Offset + *MinAbsVarIndex;
-        // Check that an access at OffsetLo or lower, and an access at OffsetHi
-        // or higher both do not alias.
+        // We know that Offset <= OffsetLo || Offset >= OffsetHi
         if (OffsetLo.isNegative() && (-OffsetLo).uge(V1Size.getValue()) &&
             OffsetHi.isNonNegative() && OffsetHi.uge(V2Size.getValue()))
           return NoAlias;
       }
+
+      if (MinVarIndex) {
+        APInt MinOffset = DecompGEP1.Offset + *MinVarIndex;
+        // We know that Offset >= MinOffset.
+        // (MinOffset >= V2Size) => (Offset >= V2Size) => NoAlias.
+        if (MinOffset.sge(V2Size.getValue())) {
+          return NoAlias;
+        }
+      }
+
+      if (MaxVarIndex) {
+        APInt MaxOffset = DecompGEP1.Offset + *MaxVarIndex;
+        // We know that Offset <= MaxOffset.
+        // (MaxOffset <= -V1Size) => (Offset <= -V1Size) => NoAlias.
+        if (MaxOffset.sle(-V1Size.getValue())) {
+          return NoAlias;
+        }
+      }
     }
 
     if (constantOffsetHeuristic(DecompGEP1.VarIndices, V1Size, V2Size,
diff --git a/llvm/test/Analysis/BasicAA/assume-index-positive.ll b/llvm/test/Analysis/BasicAA/assume-index-positive.ll
--- a/llvm/test/Analysis/BasicAA/assume-index-positive.ll
+++ b/llvm/test/Analysis/BasicAA/assume-index-positive.ll
@@ -59,9 +59,9 @@
 define void @test3(double* %ptr, i32 %skip) {
 ; CHECK-LABEL: Function: test3: 4 pointers, 1 call sites
 ; CHECK-NEXT:  MustAlias:   <6 x double>* %col.ptr.1, double* %ptr
-; CHECK-NEXT:  MayAlias:    double* %col.ptr.2, double* %ptr
+; CHECK-NEXT:  NoAlias:     double* %col.ptr.2, double* %ptr
 ; CHECK-NEXT:  MayAlias:    <6 x double>* %col.ptr.1, double* %col.ptr.2
-; CHECK-NEXT:  MayAlias:    <6 x double>* %col.ptr.2.cast, double* %ptr
+; CHECK-NEXT:  NoAlias:     <6 x double>* %col.ptr.2.cast, double* %ptr
 ; CHECK-NEXT:  MayAlias:    <6 x double>* %col.ptr.1, <6 x double>* %col.ptr.2.cast
 ; CHECK-NEXT:  MustAlias:   <6 x double>* %col.ptr.2.cast, double* %col.ptr.2
 ; CHECK-NEXT:  NoModRef:  Ptr: double* %ptr <->  call void @llvm.assume(i1 %gt)
diff --git a/llvm/test/Analysis/BasicAA/range.ll b/llvm/test/Analysis/BasicAA/range.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Analysis/BasicAA/range.ll
@@ -0,0 +1,119 @@
+; RUN: opt < %s -basic-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+%struct.S = type { i32, [2 x i32], i32 }
+
+declare i32 @llvm.annotation.i32(i32, i8*, i8*, i32)
+declare void @llvm.assume(i1)
+
+; CHECK: Function: t1
+; CHECK: NoAlias: i32* %gep1, i32* %gep2
+define void @t1(%struct.S* %s) {
+  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 1
+  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 0
+  ret void
+}
+
+; CHECK: Function: t2_fwd
+; CHECK: MayAlias: i32* %gep1, i32* %gep2
+define void @t2_fwd(%struct.S* %s, i32* %q) {
+  %in_array = load i32, i32* %q, !range !0
+  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %in_array
+  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 0
+  ret void
+}
+
+; CHECK: Function: t2_rev
+; CHECK: MayAlias: i32* %gep1, i32* %gep2
+define void @t2_rev(%struct.S* %s, i32* %q) {
+  %in_array = load i32, i32* %q, !range !0
+  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 0
+  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %in_array
+  ret void
+}
+
+; CHECK: Function: t3_fwd
+; CHECK: NoAlias: i32* %gep1, i32* %gep2
+define void @t3_fwd(%struct.S* %s, i32* %q) {
+  %knownzero = load i32, i32* %q, !range !1
+  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %knownzero
+  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 1
+  ret void
+}
+
+; CHECK: Function: t3_rev
+; CHECK: NoAlias: i32* %gep1, i32* %gep2
+define void @t3_rev(%struct.S* %s, i32* %q) {
+  %knownzero = load i32, i32* %q, !range !1
+  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 1
+  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %knownzero
+  ret void
+}
+
+; CHECK: Function: member_after
+; CHECK: NoAlias: i32* %gep1, i32* %gep2
+define void @member_after(%struct.S* %s, i32* %q) {
+  %in_array = load i32, i32* %q, !range !0
+  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %in_array
+  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 2
+  ret void
+}
+
+; CHECK: Function: member_after_rev
+; CHECK: NoAlias: i32* %gep1, i32* %gep2
+define void @member_after_rev(%struct.S* %s, i32* %q) {
+  %in_array = load i32, i32* %q, !range !0
+  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 2
+  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %in_array
+  ret void
+}
+
+; CHECK: Function: member_before
+; CHECK: NoAlias: i32* %gep1, i32* %gep2
+define void @member_before(%struct.S* %s, i32* %q) {
+  %in_array = load i32, i32* %q, !range !0
+  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %in_array
+  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 0
+  ret void
+}
+
+; CHECK: Function: member_before_rev
+; CHECK: NoAlias: i32* %gep1, i32* %gep2
+define void @member_before_rev(%struct.S* %s, i32* %q) {
+  %in_array = load i32, i32* %q, !range !0
+  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 0
+  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %in_array
+  ret void
+}
+
+; CHECK: Function: member_before_with_assume
+; CHECK: NoAlias: i32* %gep1, i32* %gep2
+define void @member_before_with_assume(%struct.S* %s, i32 %in_array) {
+  %cmp1 = icmp sge i32 %in_array, 0
+  %cmp2 = icmp slt i32 %in_array, 2
+  %cmp = and i1 %cmp1, %cmp2
+  call void @llvm.assume(i1 %cmp)
+  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %in_array
+  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 0
+  ret void
+}
+
+; CHECK: Function: member_before_with_inrange
+; CHECK: NoAlias: i32* %gep1, i32* %gep2
+define void @member_before_with_inrange(%struct.S* %s, i32 %in_array) {
+  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, inrange i32 %in_array
+  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 0
+  ret void
+}
+
+; CHECK: Function: member_before_with_assume_bundle
+; CHECK: NoAlias: i32* %gep1, i32* %gep2
+define void @member_before_with_assume_bundle(%struct.S* %s, i32 %in_array) {
+  call void @llvm.assume(i1 true) ["range"(i32 %in_array, i32 0, i32 2)]
+  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %in_array
+  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 0
+  ret void
+}
+
+!0 = !{ i32 0, i32 2 }
+!1 = !{ i32 0, i32 1 }
+!2 = !{ i32 1, i32 2 }
diff --git a/llvm/test/Analysis/BasicAA/sequential-gep.ll b/llvm/test/Analysis/BasicAA/sequential-gep.ll
--- a/llvm/test/Analysis/BasicAA/sequential-gep.ll
+++ b/llvm/test/Analysis/BasicAA/sequential-gep.ll
@@ -124,24 +124,24 @@
 ; CHECK-LABEL: non_zero_index_simple
 ; CHECK: NoAlias: i32* %gep, i32* %p
 ; CHECK: NoAlias: i16* %gep.16, i32* %p
-; CHECK: MayAlias: i32* %p, i64* %gep.64
+; CHECK: NoAlias: i32* %p, i64* %gep.64
 define void @non_zero_index_simple(i32* %p, i32* %q) {
-  %knownnonzero = load i32, i32* %q, !range !0
-  %gep = getelementptr i32, i32* %p, i32 %knownnonzero
+  %known_in_1_5 = load i32, i32* %q, !range !0
+  %gep = getelementptr i32, i32* %p, i32 %known_in_1_5
   %gep.16 = bitcast i32* %gep to i16*
   %gep.64 = bitcast i32* %gep to i64*
   ret void
 }
 
 ; CHECK-LABEL: non_zero_index_with_offset
-; CHECK: MayAlias: i32* %gep, i32* %p
+; CHECK: NoAlias: i32* %gep, i32* %p
 ; CHECK: NoAlias: i16* %gep.16, i32* %p
 define void @non_zero_index_with_offset(i32* %p, i32* %q) {
-  %knownnonzero = load i32, i32* %q, !range !0
+  %known_in_1_5 = load i32, i32* %q, !range !0
   %p.8 = bitcast i32* %p to i8*
   %p.off.8 = getelementptr i8, i8* %p.8, i32 2
   %p.off = bitcast i8* %p.off.8 to i32*
-  %gep = getelementptr i32, i32* %p.off, i32 %knownnonzero
+  %gep = getelementptr i32, i32* %p.off, i32 %known_in_1_5
   %gep.16 = bitcast i32* %gep to i16*
   ret void
 }