diff --git a/llvm/include/llvm/Analysis/BasicAliasAnalysis.h b/llvm/include/llvm/Analysis/BasicAliasAnalysis.h
--- a/llvm/include/llvm/Analysis/BasicAliasAnalysis.h
+++ b/llvm/include/llvm/Analysis/BasicAliasAnalysis.h
@@ -116,6 +116,9 @@
     // Context instruction to use when querying information about this index.
     const Instruction *CxtI;
 
+    /// True if ((V * Scale)  + Offset) % X  produces the same result for any X.
+    bool PreservesModulo;
+
     void dump() const {
       print(dbgs());
       dbgs() << "\n";
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
@@ -276,11 +276,15 @@
   APInt Scale;
   APInt Offset;
 
+  /// True if ((Val * Scale) + Offset) % X  produces the same result for any X.
+  bool PreservesModulo;
+
   LinearExpression(const ExtendedValue &Val, const APInt &Scale,
-                   const APInt &Offset)
-      : Val(Val), Scale(Scale), Offset(Offset) {}
+                   const APInt &Offset, bool PreservesModulo)
+      : Val(Val), Scale(Scale), Offset(Offset),
+        PreservesModulo(PreservesModulo) {}
 
-  LinearExpression(const ExtendedValue &Val) : Val(Val) {
+  LinearExpression(const ExtendedValue &Val) : Val(Val), PreservesModulo(true) {
     unsigned BitWidth = Val.getBitWidth();
     Scale = APInt(BitWidth, 1);
     Offset = APInt(BitWidth, 0);
@@ -299,7 +303,7 @@
 
   if (const ConstantInt *Const = dyn_cast<ConstantInt>(Val.V))
     return LinearExpression(Val, APInt(Val.getBitWidth(), 0),
-                            Val.evaluateWith(Const->getValue()));
+                            Val.evaluateWith(Const->getValue()), false);
 
   if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(Val.V)) {
     if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
@@ -314,6 +318,7 @@
       if (!Val.canDistributeOver(NUW, NSW))
         return Val;
 
+      LinearExpression E(Val);
       switch (BOp->getOpcode()) {
       default:
         // We don't understand this instruction, so we can't decompose it any
@@ -328,23 +333,26 @@
 
         LLVM_FALLTHROUGH;
       case Instruction::Add: {
-        LinearExpression E = GetLinearExpression(
-            Val.withValue(BOp->getOperand(0)), DL, Depth + 1, AC, DT);
+        E = GetLinearExpression(Val.withValue(BOp->getOperand(0)), DL,
+                                Depth + 1, AC, DT);
         E.Offset += RHS;
-        return E;
+        E.PreservesModulo &= NUW && NSW;
+        break;
       }
       case Instruction::Sub: {
-        LinearExpression E = GetLinearExpression(
-            Val.withValue(BOp->getOperand(0)), DL, Depth + 1, AC, DT);
+        E = GetLinearExpression(Val.withValue(BOp->getOperand(0)), DL,
+                                Depth + 1, AC, DT);
         E.Offset -= RHS;
-        return E;
+        E.PreservesModulo &= NUW && NSW;
+        break;
       }
       case Instruction::Mul: {
-        LinearExpression E = GetLinearExpression(
-            Val.withValue(BOp->getOperand(0)), DL, Depth + 1, AC, DT);
+        E = GetLinearExpression(Val.withValue(BOp->getOperand(0)), DL,
+                                Depth + 1, AC, DT);
         E.Offset *= RHS;
         E.Scale *= RHS;
-        return E;
+        E.PreservesModulo &= RHS.isPowerOf2() || (NUW && NSW);
+        break;
       }
       case Instruction::Shl:
         // We're trying to linearize an expression of the kind:
@@ -355,12 +363,14 @@
         if (RHS.getLimitedValue() > Val.getBitWidth())
           return Val;
 
-        LinearExpression E = GetLinearExpression(
-            Val.withValue(BOp->getOperand(0)), DL, Depth + 1, AC, DT);
+        E = GetLinearExpression(Val.withValue(BOp->getOperand(0)), DL,
+                                Depth + 1, AC, DT);
         E.Offset <<= RHS.getLimitedValue();
         E.Scale <<= RHS.getLimitedValue();
-        return E;
+        // SHL multiplies by a power-of-2 and always preserves modulo.
+        break;
       }
+      return E;
     }
   }
 
@@ -570,8 +580,9 @@
       Scale = adjustToPointerSize(Scale, PointerSize);
 
       if (!!Scale) {
-        VariableGEPIndex Entry = {LE.Val.V, LE.Val.ZExtBits, LE.Val.SExtBits,
-                                  Scale, CxtI};
+        VariableGEPIndex Entry = {
+            LE.Val.V, LE.Val.ZExtBits,   LE.Val.SExtBits, Scale,
+            CxtI,     LE.PreservesModulo};
         Decomposed.VarIndices.push_back(Entry);
       }
     }
@@ -1128,7 +1139,9 @@
     bool AllNonPositive = DecompGEP1.Offset.isNonPositive();
     for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) {
       const APInt &Scale = DecompGEP1.VarIndices[i].Scale;
-      if (i == 0)
+      if (!DecompGEP1.VarIndices[i].PreservesModulo)
+        GCD = APInt(Scale.getBitWidth(), 1);
+      else if (i == 0)
         GCD = Scale.abs();
       else
         GCD = APIntOps::GreatestCommonDivisor(GCD, Scale.abs());
@@ -1680,9 +1693,11 @@
 
       // If we found it, subtract off Scale V's from the entry in Dest.  If it
       // goes to zero, remove the entry.
-      if (Dest[j].Scale != Scale)
+      if (Dest[j].Scale != Scale) {
         Dest[j].Scale -= Scale;
-      else
+        // Conservatively assume modulo is not preserved.
+        Dest[j].PreservesModulo = false;
+      } else
         Dest.erase(Dest.begin() + j);
       Scale = 0;
       break;
@@ -1690,7 +1705,8 @@
 
     // If we didn't consume this entry, add it to the end of the Dest list.
     if (!!Scale) {
-      VariableGEPIndex Entry = {V, ZExtBits, SExtBits, -Scale, Src[i].CxtI};
+      VariableGEPIndex Entry = {V,      ZExtBits,    SExtBits,
+                                -Scale, Src[i].CxtI, Src[i].PreservesModulo};
       Dest.push_back(Entry);
     }
   }
diff --git a/llvm/test/Analysis/BasicAA/gep-alias.ll b/llvm/test/Analysis/BasicAA/gep-alias.ll
--- a/llvm/test/Analysis/BasicAA/gep-alias.ll
+++ b/llvm/test/Analysis/BasicAA/gep-alias.ll
@@ -161,7 +161,7 @@
 
 define i8 @test9([4 x i8] *%P, i32 %i, i32 %j) {
   %i2 = shl i32 %i, 2
-  %i3 = add i32 %i2, 1
+  %i3 = add nsw nuw i32 %i2, 1
   ; P2 = P + 1 + 4*i
   %P2 = getelementptr [4 x i8], [4 x i8] *%P, i32 0, i32 %i3
 
diff --git a/llvm/test/Analysis/BasicAA/gep-modulo.ll b/llvm/test/Analysis/BasicAA/gep-modulo.ll
--- a/llvm/test/Analysis/BasicAA/gep-modulo.ll
+++ b/llvm/test/Analysis/BasicAA/gep-modulo.ll
@@ -70,7 +70,7 @@
 ; CHECK-LABEL: Function: may_overflow_mul_sub_i64: 3 pointers, 0 call sites
 ; CHECK-NEXT:    MayAlias:  [16 x i8]* %ptr, i8* %gep.idx
 ; CHECK-NEXT:    PartialAlias: [16 x i8]* %ptr, i8* %gep.3
-; CHECK-NEXT:    NoAlias:  i8* %gep.3, i8* %gep.idx
+; CHECK-NEXT:    MayAlias:  i8* %gep.3, i8* %gep.idx
 ;
   %mul = mul i64 %idx, 5
   %sub = sub i64 %mul, 1
@@ -100,7 +100,7 @@
 ; CHECK-LABEL: Function: only_nsw_mul_sub_i64: 3 pointers, 0 call sites
 ; CHECK-NEXT:    MayAlias:  [16 x i8]* %ptr, i8* %gep.idx
 ; CHECK-NEXT:    PartialAlias: [16 x i8]* %ptr, i8* %gep.3
-; CHECK-NEXT:    NoAlias:  i8* %gep.3, i8* %gep.idx
+; CHECK-NEXT:    MayAlias:  i8* %gep.3, i8* %gep.idx
 ;
   %mul = mul nsw i64 %idx, 5
   %sub = sub nsw i64 %mul, 1
@@ -115,7 +115,7 @@
 ; CHECK-LABEL: Function: only_nuw_mul_sub_i64: 3 pointers, 0 call sites
 ; CHECK-NEXT:    MayAlias:  [16 x i8]* %ptr, i8* %gep.idx
 ; CHECK-NEXT:    PartialAlias: [16 x i8]* %ptr, i8* %gep.3
-; CHECK-NEXT:    NoAlias:  i8* %gep.3, i8* %gep.idx
+; CHECK-NEXT:    MayAlias:  i8* %gep.3, i8* %gep.idx
 ;
   %mul = mul nuw i64 %idx, 5
   %sub = sub nuw i64 %mul, 1
@@ -130,7 +130,7 @@
 ; CHECK-LABEL: Function: may_overflow_mul_pow2_sub_i64: 3 pointers, 0 call sites
 ; CHECK-NEXT:    MayAlias:  [16 x i8]* %ptr, i8* %gep.idx
 ; CHECK-NEXT:    PartialAlias: [16 x i8]* %ptr, i8* %gep.3
-; CHECK-NEXT:    NoAlias:  i8* %gep.3, i8* %gep.idx
+; CHECK-NEXT:    MayAlias:  i8* %gep.3, i8* %gep.idx
 ;
   %mul = mul i64 %idx, 8
   %sub = sub i64 %mul, 1