Index: lib/Analysis/BasicAliasAnalysis.cpp
===================================================================
--- lib/Analysis/BasicAliasAnalysis.cpp
+++ lib/Analysis/BasicAliasAnalysis.cpp
@@ -48,6 +48,7 @@
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Operator.h"
+#include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
@@ -64,6 +65,7 @@
 #define DEBUG_TYPE "basicaa"
 
 using namespace llvm;
+using namespace llvm::PatternMatch;
 
 /// Enable analysis of recursive PHI nodes.
 static cl::opt<bool> EnableRecPhiAnalysis("basicaa-recphi", cl::Hidden,
@@ -998,18 +1000,77 @@
   return AAResultBase::getModRefInfo(CS1, CS2);
 }
 
+static bool isAssumeNonZero(const Value *V, const Instruction *RefI, AssumptionCache *AC, DominatorTree *DT) {
+
+  for (auto &AssumeVH : AC->assumptionsFor(V)) {
+    CallInst *I = cast<CallInst>(AssumeVH);
+
+    if (!isValidAssumeForContext(I, RefI, DT))
+      continue;
+
+    Value *Arg = I->getArgOperand(0);
+
+    CmpInst::Predicate Pred;
+    ConstantInt *C;
+
+    if (match(Arg, m_c_ICmp(Pred, m_Specific(V), m_ConstantInt(C))) &&
+        Pred == ICmpInst::ICMP_NE && C->isZero()) {
+      return true;
+    }
+  }
+
+  return false;
+}
+
 /// Provide ad-hoc rules to disambiguate accesses through two GEP operators,
 /// both having the exact same pointer operand.
 static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
                                             LocationSize MaybeV1Size,
                                             const GEPOperator *GEP2,
                                             LocationSize MaybeV2Size,
-                                            const DataLayout &DL) {
+                                            const DataLayout &DL,
+                                            AssumptionCache *AC,
+                                            DominatorTree *DT) {
   assert(GEP1->getPointerOperand()->stripPointerCastsAndInvariantGroups() ==
              GEP2->getPointerOperand()->stripPointerCastsAndInvariantGroups() &&
          GEP1->getPointerOperandType() == GEP2->getPointerOperandType() &&
          "Expected GEPs with the same pointer operand");
 
+  // Let
+  // %I1 = shl i16 %X, C1
+  // %I2 = shl i16 %X, C2
+  // %G1 = getelementptr i16, i16* %baseptr, i16 %I1
+  // %G2 = getelementptr i16, i16* %baseptr, i16 %I2
+  //
+  // Then %G1 and %G2 do not alias if %C1 != %C2 and %X != 0
+  //
+  // TODO:FIXME: Also need to check V1Size, V2Size and the element size of the
+  // type being accessed.
+  if (GEP1->getNumIndices() == GEP2->getNumIndices() &&
+      GEP1->getNumIndices() == 1) {
+    const Instruction *I1 = dyn_cast<Instruction>(GEP1->getOperand(1));
+    const Instruction *I2 = dyn_cast<Instruction>(GEP2->getOperand(1));
+    if (I1 && I2) {
+      Value *X1, *X2;
+      ConstantInt *C1, *C2;
+
+      if (I1->getOpcode() != Instruction::Shl)
+        std::swap(I1, I2);
+
+      if (match(I1, m_Shl(m_Value(X1), m_ConstantInt(C1))) &&
+          match(I2, m_Shl(m_Value(X2), m_ConstantInt(C2))) &&
+          X1 == X2 && C1->getSExtValue() != C2->getSExtValue() &&
+          isAssumeNonZero(X1, I1, AC, DT))
+        return NoAlias;
+
+      if (match(I1, m_Shl(m_Value(X1), m_ConstantInt(C1))) &&
+          match(I2, m_Mul(m_Value(X2), m_ConstantInt(C2))) &&
+          X1 == X2 && (1 << C1->getSExtValue()) != C2->getSExtValue() &&
+          isAssumeNonZero(X1, I1, AC, DT))
+        return NoAlias;
+    }
+  }
+
   // Try to determine whether GEP1 and GEP2 index through arrays, into structs,
   // such that the struct field accesses provably cannot alias.
   // We also need at least two indices (the pointer, and the struct field).
@@ -1223,6 +1284,26 @@
                         const AAMDNodes &V1AAInfo, const Value *V2,
                         LocationSize V2Size, const AAMDNodes &V2AAInfo,
                         const Value *UnderlyingV1, const Value *UnderlyingV2) {
+  // If %G1 = getelementptr i16, i16* %P, i16 %I1
+  // Then %G1 and %P do not alias if %I1 != 0
+  //
+  // TODO:FIXME: Also need to check V1Size, V2Size and the element size of the
+  // type being accessed.
+  if (UnderlyingV1 == V2 && GEP1->getNumIndices() == 1) {
+    if (const Instruction *I1 = dyn_cast<Instruction>(GEP1->getOperand(1))) {
+      Value *X1;
+      ConstantInt *C1;
+
+      if (match(I1, m_Shl(m_Value(X1), m_ConstantInt(C1))) &&
+          isAssumeNonZero(X1, I1, &AC, DT))
+        return NoAlias;
+
+      if (match(I1, m_Mul(m_Value(X1), m_ConstantInt(C1))) &&
+          isAssumeNonZero(X1, I1, &AC, DT))
+        return NoAlias;
+    }
+  }
+
   DecomposedGEP DecompGEP1, DecompGEP2;
   bool GEP1MaxLookupReached =
     DecomposeGEPExpression(GEP1, DecompGEP1, DL, &AC, DT);
@@ -1292,7 +1373,7 @@
     if (GEP1->getPointerOperand()->stripPointerCastsAndInvariantGroups() ==
             GEP2->getPointerOperand()->stripPointerCastsAndInvariantGroups() &&
         GEP1->getPointerOperandType() == GEP2->getPointerOperandType()) {
-      AliasResult R = aliasSameBasePointerGEPs(GEP1, V1Size, GEP2, V2Size, DL);
+      AliasResult R = aliasSameBasePointerGEPs(GEP1, V1Size, GEP2, V2Size, DL, &AC, DT);
       // If we couldn't find anything interesting, don't abandon just yet.
       if (R != MayAlias)
         return R;