Index: llvm/lib/Analysis/AliasAnalysisEvaluator.cpp
===================================================================
--- llvm/lib/Analysis/AliasAnalysisEvaluator.cpp
+++ llvm/lib/Analysis/AliasAnalysisEvaluator.cpp
@@ -170,6 +170,14 @@
         ++MustAliasCount;
         break;
       }
+
+      // We assume that alias(I1, I2) == alias(I2, I1) and only print one
+      // order. Make sure this assumption actually holds.
+      // TODO: We should probably assert this in AA itself under
+      // EXPENSIVE_CHECKS. This would need some more thorough verification that
+      // all AA queries are symmetric first.
+      assert(AR == AA.alias(*I2, I2Size, *I1, I1Size) &&
+             "AA query not symmetric");
     }
   }
 
Index: llvm/lib/Analysis/BasicAliasAnalysis.cpp
===================================================================
--- llvm/lib/Analysis/BasicAliasAnalysis.cpp
+++ llvm/lib/Analysis/BasicAliasAnalysis.cpp
@@ -1394,7 +1394,8 @@
 
   if (!DecompGEP1.VarIndices.empty()) {
     APInt Modulo(MaxPointerSize, 0);
-    bool AllPositive = true;
+    bool AllNonNegative = GEP1BaseOffset.isNonNegative();
+    bool AllNonPositive = GEP1BaseOffset.isNonPositive();
     for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) {
 
       // Try to distinguish something like &A[i][1] against &A[42][0].
@@ -1403,7 +1404,7 @@
       // be ^'ing Modulo with itself later.
       Modulo |= DecompGEP1.VarIndices[i].Scale;
 
-      if (AllPositive) {
+      if (AllNonNegative || AllNonPositive) {
         // If the Value could change between cycles, then any reasoning about
         // the Value this cycle may not hold in the next cycle. We'll just
         // give up if we can't determine conditions that hold for every cycle:
@@ -1420,12 +1421,11 @@
         SignKnownZero |= IsZExt;
         SignKnownOne &= !IsZExt;
 
-        // 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));
+        AllNonNegative &= (SignKnownZero && Scale.isNonNegative()) ||
+                          (SignKnownOne && Scale.isNonPositive());
+        AllNonPositive &= (SignKnownZero && Scale.isNonPositive()) ||
+                          (SignKnownOne && Scale.isNonNegative());
       }
     }
 
@@ -1440,13 +1440,16 @@
         (Modulo - ModOffset).uge(V1Size.getValue()))
       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) &&
-        V2Size != LocationSize::unknown() &&
+    // If we know all the variables are non-negative, then the total offset is
+    // also non-negative and >= GEP1BaseOffset. If GEP1BaseOffset >= V2Size,
+    // then the pointers can't alias. An analogous case holds for the
+    // non-positive case as well.
+    if (AllNonNegative && V2Size != LocationSize::unknown() &&
         GEP1BaseOffset.uge(V2Size.getValue()))
       return NoAlias;
+    if (AllNonPositive && V2Size != LocationSize::unknown() &&
+        (-GEP1BaseOffset).uge(V2Size.getValue()))
+      return NoAlias;
 
     if (constantOffsetHeuristic(DecompGEP1.VarIndices, V1Size, V2Size,
                                 GEP1BaseOffset, &AC, DT))