[BasicAA] Fix zext & sext handling

[njw45]

Summary

Un-revert of r241981 and fix for PR23626. The 'Or' case of GetLinearExpression delegates to 'Add' if possible, and if not it returns an Opaque value. Unfortunately the Scale and Offsets weren't being set (and so defaulted to 0) - and a scale of zero effectively removes the variable from the GEP instruction. This meant that BasicAA would return MustAliases when it should have been returning PartialAliases (and PR23626 was an example of the GVN pass using an incorrect MustAlias to merge loads from what should have been different pointers).

[hfinkel]

A few small comment improvements, but otherwise, LGTM.

lib/Analysis/BasicAliasAnalysis.cpp

170

The formatting would be better here if you broke the line before the ZExt(

205

We should document what NSW/NUW mean (I realize this is somewhat obvious, but even so) and that they should both be set to true before calling this at the top level.

Similarly, ZExtBits, SExtBits, Offset and Scale need to be zero, and we should say that as well.

222

if -> If

229

The comment here says, "and remove the variable", but this seems slightly misleading (I'd assume that means returning a nullptr or Undef). Really, the value will be ignored because the Scale is never changed from zero.

624

The comment should explain what the return value actually means.

[hans]

Did this get committed? Is this a fix we need for 3.7?

[hfinkel]

In D11847#227037, @hans wrote:

Did this get committed? Is this a fix we need for 3.7?

From what qcolombet mentioned, this fixes a bug introduced in r221876. That would make it nice to have in 3.7, and I'm fine with it being committed to trunk and making my requested commentary improvements in follow-up. However, this is not purely a bug fix, and furthermore, this fix itself has been committed/reverted before as well. I'm nervous about merging it into the release branch late in the release cycle. It might be best to revert r221876 in the release branch instead. Is there going to be another release candidate at this point before 3.7?

[hans]

In D11847#227064, @hfinkel wrote:

In D11847#227037, @hans wrote:

Did this get committed? Is this a fix we need for 3.7?

From what qcolombet mentioned, this fixes a bug introduced in r221876. That would make it nice to have in 3.7, and I'm fine with it being committed to trunk and making my requested commentary improvements in follow-up. However, this is not purely a bug fix, and furthermore, this fix itself has been committed/reverted before as well. I'm nervous about merging it into the release branch late in the release cycle. It might be best to revert r221876 in the release branch instead. Is there going to be another release candidate at this point before 3.7?

r221876 also doesn't look like a trivial patch. It's hard to follow along with all the reverted reverts here.

From what I understand, PR23626 that's mentioned here was already fixed by reverting something else on 3.7, so maybe we don't need this or reverting r221876?

There have been a number of merges after 3.7-rc2, so there will be an rc3, but I'm hoping that will become the final one.

[hfinkel]

In D11847#227079, @hans wrote:

In D11847#227064, @hfinkel wrote:

In D11847#227037, @hans wrote:

Did this get committed? Is this a fix we need for 3.7?

From what qcolombet mentioned, this fixes a bug introduced in r221876. That would make it nice to have in 3.7, and I'm fine with it being committed to trunk and making my requested commentary improvements in follow-up. However, this is not purely a bug fix, and furthermore, this fix itself has been committed/reverted before as well. I'm nervous about merging it into the release branch late in the release cycle. It might be best to revert r221876 in the release branch instead. Is there going to be another release candidate at this point before 3.7?

r221876 also doesn't look like a trivial patch. It's hard to follow along with all the reverted reverts here.

From what I understand, PR23626 that's mentioned here was already fixed by reverting something else on 3.7, so maybe we don't need this or reverting r221876?

There have been a number of merges after 3.7-rc2, so there will be an rc3, but I'm hoping that will become the final one.

Okay; I'll make sure this gets committed today.

[qcolombet]

• msg-8651-136.txt666 BDownload
• with.ll8 KBDownload
• without.ll9 KBDownload

[qcolombet]

Committed on Nick’s behalf in r246502.

lib/Analysis/BasicAliasAnalysis.cpp

static bool isObjectSize(const Value *V, uint64_t Size,
   return ObjectSize != MemoryLocation::UnknownSize && ObjectSize == Size;
 }
 
 //===----------------------------------------------------------------------===//
 // GetElementPtr Instruction Decomposition and Analysis
 //===----------------------------------------------------------------------===//
 
 namespace {
-  enum ExtensionKind {
-    EK_NotExtended,
-    EK_SignExt,
-    EK_ZeroExt
-  };
 
+  // A linear transformation of a Value; this class represents ZExt(SExt(V,
+  // SExtBits), ZExtBits) * Scale + Offset.
   struct VariableGEPIndex {
+
+    // An opaque Value - we can't decompose this further.
     const Value *V;
-    ExtensionKind Extension;
+
+    // We need to track what extensions we've done as we consider the same Value
+    // with different extensions as different variables in a GEP's linear
+    // expression;
+    // e.g.: if V == -1, then sext(x) != zext(x).
+    unsigned ZExtBits;
+    unsigned SExtBits;
+
     int64_t Scale;
 
     bool operator==(const VariableGEPIndex &Other) const {
-      return V == Other.V && Extension == Other.Extension &&
-        Scale == Other.Scale;
+      return V == Other.V && ZExtBits == Other.ZExtBits &&
+             SExtBits == Other.SExtBits && Scale == Other.Scale;
     }
 
     bool operator!=(const VariableGEPIndex &Other) const {
       return !operator==(Other);
     }
   };
 }
 
 
 /// GetLinearExpression - Analyze the specified value as a linear expression:
 /// "A*V + B", where A and B are constant integers.  Return the scale and offset
 /// values as APInts and return V as a Value*, and return whether we looked
 /// through any sign or zero extends.  The incoming Value is known to have
 /// IntegerType and it may already be sign or zero extended.
 ///
 /// Note that this looks through extends, so the high bits may not be
 /// represented in the result.
-static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset,
-                                  ExtensionKind &Extension,
+static const Value *GetLinearExpression(const Value *V, APInt &Scale,
+                                        APInt &Offset, unsigned &ZExtBits,
+                                        unsigned &SExtBits,
                                         const DataLayout &DL, unsigned Depth,
-                                  AssumptionCache *AC, DominatorTree *DT) {
+                                        AssumptionCache *AC, DominatorTree *DT,
+                                        bool &NSW, bool &NUW) {
   assert(V->getType()->isIntegerTy() && "Not an integer value");
 
   // Limit our recursion depth.
   if (Depth == 6) {
     Scale = 1;
     Offset = 0;
     return V;
   }
 
-  if (ConstantInt *Const = dyn_cast<ConstantInt>(V)) {
-    // if it's a constant, just convert it to an offset
-    // and remove the variable.
-    Offset += Const->getValue();
+  if (const ConstantInt *Const = dyn_cast<ConstantInt>(V)) {
+    // if it's a constant, just convert it to an offset and remove the variable.
+    // If we've been called recursively the Offset bit width will be greater
+    // than the constant's (the Offset's always as wide as the outermost call),
+    // so we'll zext here and process any extension in the isa<SExtInst> &
+    // isa<ZExtInst> cases below.
+    Offset += Const->getValue().zextOrSelf(Offset.getBitWidth());
     assert(Scale == 0 && "Constant values don't have a scale");
     return V;
   }
 
-  if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) {
+  if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) {
     if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
+
+      // If we've been called recursively then Offset and Scale will be wider
+      // that the BOp operands. We'll always zext it here as we'll process sign
+      // extensions below (see the isa<SExtInst> / isa<ZExtInst> cases).
+      APInt RHS = RHSC->getValue().zextOrSelf(Offset.getBitWidth());
+
       switch (BOp->getOpcode()) {
-      default: break;
+      default:
+        // We don't understand this instruction, so we can't decompose it any
+        // further.
+        Scale = 1;
+        Offset = 0;
+        return V;
       case Instruction::Or:
         // X|C == X+C if all the bits in C are unset in X.  Otherwise we can't
         // analyze it.
         if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), DL, 0, AC,
-                               BOp, DT))
-          break;
+                               BOp, DT)) {
+          Scale = 1;
+          Offset = 0;
+          return V;
+        }
         // FALL THROUGH.
       case Instruction::Add:
-        V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension,
-                                DL, Depth + 1, AC, DT);
-        Offset += RHSC->getValue();
-        return V;
+        V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
+                                SExtBits, DL, Depth + 1, AC, DT, NSW, NUW);
+        Offset += RHS;
+        break;
+      case Instruction::Sub:
+        V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
+                                SExtBits, DL, Depth + 1, AC, DT, NSW, NUW);
+        Offset -= RHS;
+        break;
       case Instruction::Mul:
-        V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension,
-                                DL, Depth + 1, AC, DT);
-        Offset *= RHSC->getValue();
-        Scale *= RHSC->getValue();
-        return V;
+        V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
+                                SExtBits, DL, Depth + 1, AC, DT, NSW, NUW);
+        Offset *= RHS;
+        Scale *= RHS;
+        break;
       case Instruction::Shl:
-        V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension,
-                                DL, Depth + 1, AC, DT);
-        Offset <<= RHSC->getValue().getLimitedValue();
-        Scale <<= RHSC->getValue().getLimitedValue();
+        V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
+                                SExtBits, DL, Depth + 1, AC, DT, NSW, NUW);
+        Offset <<= RHS.getLimitedValue();
+        Scale <<= RHS.getLimitedValue();
+        // the semantics of nsw and nuw for left shifts don't match those of
+        // multiplications, so we won't propagate them.
+        NSW = NUW = false;
         return V;
       }
+
+      if (isa<OverflowingBinaryOperator>(BOp)) {
+        NUW &= BOp->hasNoUnsignedWrap();
+        NSW &= BOp->hasNoSignedWrap();
+      }
+      return V;
     }
   }
 
   // Since GEP indices are sign extended anyway, we don't care about the high
   // bits of a sign or zero extended value - just scales and offsets.  The
   // extensions have to be consistent though.
-  if ((isa<SExtInst>(V) && Extension != EK_ZeroExt) ||
-      (isa<ZExtInst>(V) && Extension != EK_SignExt)) {
+  if (isa<SExtInst>(V) || isa<ZExtInst>(V)) {
     Value *CastOp = cast<CastInst>(V)->getOperand(0);
-    unsigned OldWidth = Scale.getBitWidth();
+    unsigned NewWidth = V->getType()->getPrimitiveSizeInBits();
     unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits();
-    Scale = Scale.trunc(SmallWidth);
-    Offset = Offset.trunc(SmallWidth);
-    Extension = isa<SExtInst>(V) ? EK_SignExt : EK_ZeroExt;
-
-    Value *Result = GetLinearExpression(CastOp, Scale, Offset, Extension, DL,
-                                        Depth + 1, AC, DT);
-    Scale = Scale.zext(OldWidth);
-
-    // We have to sign-extend even if Extension == EK_ZeroExt as we can't
-    // decompose a sign extension (i.e. zext(x - 1) != zext(x) - zext(-1)).
-    Offset = Offset.sext(OldWidth);
+    unsigned OldZExtBits = ZExtBits, OldSExtBits = SExtBits;
+    const Value *Result =
+        GetLinearExpression(CastOp, Scale, Offset, ZExtBits, SExtBits, DL,
+                            Depth + 1, AC, DT, NSW, NUW);
+
+    // zext(zext(%x)) == zext(%x), and similiarly for sext; we'll handle this
+    // by just incrementing the number of bits we've extended by.
+    unsigned ExtendedBy = NewWidth - SmallWidth;
+
+    if (isa<SExtInst>(V) && ZExtBits == 0) {
+      // sext(sext(%x, a), b) == sext(%x, a + b)
+
+      if (NSW) {
+        // We haven't sign-wrapped, so it's valid to decompose sext(%x + c)
+        // into sext(%x) + sext(c). We'll sext the Offset ourselves:
+        unsigned OldWidth = Offset.getBitWidth();
+        Offset = Offset.trunc(SmallWidth).sext(NewWidth).zextOrSelf(OldWidth);
+      } else {
+        // We may have signed-wrapped, so don't decompose sext(%x + c) into
+        // sext(%x) + sext(c)
+        Scale = 1;
+        Offset = 0;
+        Result = CastOp;
+        ZExtBits = OldZExtBits;
+        SExtBits = OldSExtBits;
+      }
+      SExtBits += ExtendedBy;
+    } else {
+      // sext(zext(%x, a), b) = zext(zext(%x, a), b) = zext(%x, a + b)
+
+      if (!NUW) {
+        // We may have unsigned-wrapped, so don't decompose zext(%x + c) into
+        // zext(%x) + zext(c)
+        Scale = 1;
+        Offset = 0;
+        Result = CastOp;
+        ZExtBits = OldZExtBits;
+        SExtBits = OldSExtBits;
+      }
+      ZExtBits += ExtendedBy;
+    }
 
     return Result;
   }
 
   Scale = 1;
   Offset = 0;
   return V;
 }
do {
     if (!GEPOp->getOperand(0)->getType()->getPointerElementType()->isSized())
       return V;
 
     unsigned AS = GEPOp->getPointerAddressSpace();
     // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices.
     gep_type_iterator GTI = gep_type_begin(GEPOp);
     for (User::const_op_iterator I = GEPOp->op_begin()+1,
          E = GEPOp->op_end(); I != E; ++I) {
-      Value *Index = *I;
+      const Value *Index = *I;
       // Compute the (potentially symbolic) offset in bytes for this index.
       if (StructType *STy = dyn_cast<StructType>(*GTI++)) {
         // For a struct, add the member offset.
         unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
         if (FieldNo == 0) continue;
 
         BaseOffs += DL.getStructLayout(STy)->getElementOffset(FieldNo);
         continue;
       }
 
       // For an array/pointer, add the element offset, explicitly scaled.
-      if (ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) {
+      if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) {
         if (CIdx->isZero()) continue;
         BaseOffs += DL.getTypeAllocSize(*GTI) * CIdx->getSExtValue();
         continue;
       }
 
       uint64_t Scale = DL.getTypeAllocSize(*GTI);
-      ExtensionKind Extension = EK_NotExtended;
+      unsigned ZExtBits = 0, SExtBits = 0;
 
       // If the integer type is smaller than the pointer size, it is implicitly
       // sign extended to pointer size.
       unsigned Width = Index->getType()->getIntegerBitWidth();
-      if (DL.getPointerSizeInBits(AS) > Width)
-        Extension = EK_SignExt;
+      unsigned PointerSize = DL.getPointerSizeInBits(AS);
+      if (PointerSize > Width)
+        SExtBits += PointerSize - Width;
 
       // Use GetLinearExpression to decompose the index into a C1*V+C2 form.
       APInt IndexScale(Width, 0), IndexOffset(Width, 0);
-      Index = GetLinearExpression(Index, IndexScale, IndexOffset, Extension, DL,
-                                  0, AC, DT);
+      bool NSW = true, NUW = true;
+      Index = GetLinearExpression(Index, IndexScale, IndexOffset, ZExtBits,
+                                  SExtBits, DL, 0, AC, DT, NSW, NUW);
 
       // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale.
       // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale.
       BaseOffs += IndexOffset.getSExtValue()*Scale;
       Scale *= IndexScale.getSExtValue();
 
       // If we already had an occurrence of this index variable, merge this
       // scale into it.  For example, we want to handle:
       //   A[x][x] -> x*16 + x*4 -> x*20
       // This also ensures that 'x' only appears in the index list once.
       for (unsigned i = 0, e = VarIndices.size(); i != e; ++i) {
-        if (VarIndices[i].V == Index &&
-            VarIndices[i].Extension == Extension) {
+        if (VarIndices[i].V == Index && VarIndices[i].ZExtBits == ZExtBits &&
+            VarIndices[i].SExtBits == SExtBits) {
           Scale += VarIndices[i].Scale;
           VarIndices.erase(VarIndices.begin()+i);
           break;
         }
       }
 
       // Make sure that we have a scale that makes sense for this target's
       // pointer size.
-      if (unsigned ShiftBits = 64 - DL.getPointerSizeInBits(AS)) {
+      if (unsigned ShiftBits = 64 - PointerSize) {
         Scale <<= ShiftBits;
         Scale = (int64_t)Scale >> ShiftBits;
       }
 
       if (Scale) {
-        VariableGEPIndex Entry = {Index, Extension,
+        VariableGEPIndex Entry = {Index, ZExtBits, SExtBits,
                                   static_cast<int64_t>(Scale)};
         VarIndices.push_back(Entry);
       }
     }
 
     // Analyze the base pointer next.
     V = GEPOp->getOperand(0);
   } while (--MaxLookup);
private:
     ///
     /// In addition to pointer equivalence of \p V1 and \p V2 this checks
     /// whether they can not be part of a cycle in the value graph by looking at
     /// all visited phi nodes an making sure that the phis cannot reach the
     /// value. We have to do this because we are looking through phi nodes (That
     /// is we say noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB).
     bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
 
+    /// \brief A Heuristic for aliasGEP that searches for a constant offset
+    /// between the variables.
+    ///
+    /// GetLinearExpression has some limitations, as generally zext(%x + 1)
+    /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
+    /// will therefore conservatively refuse to decompose these expressions.
+    /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if
+    /// the addition overflows.
+    bool
+    constantOffsetHeuristic(const SmallVectorImpl<VariableGEPIndex> &VarIndices,
+                            uint64_t V1Size, uint64_t V2Size,
+                            int64_t BaseOffset, const DataLayout *DL,
+                            AssumptionCache *AC, DominatorTree *DT);
+
     /// \brief Dest and Src are the variable indices from two decomposed
     /// GetElementPtr instructions GEP1 and GEP2 which have common base
     /// pointers.  Subtract the GEP2 indices from GEP1 to find the symbolic
     /// difference between the two pointers.
     void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
                             const SmallVectorImpl<VariableGEPIndex> &Src);
 
     // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP
static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
 
   if (EltsDontOverlap(V1Off, V1Size, V2Off, V2Size) ||
       EltsDontOverlap(V2Off, V2Size, V1Off, V1Size))
     return NoAlias;
 
   return MayAlias;
 }
 
+bool BasicAliasAnalysis::constantOffsetHeuristic(
+    const SmallVectorImpl<VariableGEPIndex> &VarIndices, uint64_t V1Size,
+    uint64_t V2Size, int64_t BaseOffset, const DataLayout *DL,
+    AssumptionCache *AC, DominatorTree *DT) {
+  if (VarIndices.size() != 2 || V1Size == MemoryLocation::UnknownSize ||
+      V2Size == MemoryLocation::UnknownSize || !DL)
+    return false;
+
+  const VariableGEPIndex &Var0 = VarIndices[0], &Var1 = VarIndices[1];
+
+  if (Var0.ZExtBits != Var1.ZExtBits || Var0.SExtBits != Var1.SExtBits ||
+      Var0.Scale != -Var1.Scale)
+    return false;
+
+  unsigned Width = Var1.V->getType()->getIntegerBitWidth();
+
+  // We'll strip off the Extensions of Var0 and Var1 and do another round
+  // of GetLinearExpression decomposition. In the example above, if Var0
+  // is zext(%x + 1) we should get V1 == %x and V1Offset == 1.
+
+  APInt V0Scale(Width, 0), V0Offset(Width, 0), V1Scale(Width, 0),
+      V1Offset(Width, 0);
+  bool NSW = true, NUW = true;
+  unsigned V0ZExtBits = 0, V0SExtBits = 0, V1ZExtBits = 0, V1SExtBits = 0;
+  const Value *V0 = GetLinearExpression(Var0.V, V0Scale, V0Offset, V0ZExtBits,
+                                        V0SExtBits, *DL, 0, AC, DT, NSW, NUW);
+  NSW = true, NUW = true;
+  const Value *V1 = GetLinearExpression(Var1.V, V1Scale, V1Offset, V1ZExtBits,
+                                        V1SExtBits, *DL, 0, AC, DT, NSW, NUW);
+
+  if (V0Scale != V1Scale || V0ZExtBits != V1ZExtBits ||
+      V0SExtBits != V1SExtBits || !isValueEqualInPotentialCycles(V0, V1))
+    return false;
+
+  // We have a hit - Var0 and Var1 only differ by a constant offset!
+
+  // If we've been sext'ed then zext'd the maximum difference between Var0 and
+  // Var1 is possible to calculate, but we're just interested in the absolute
+  // minumum difference between the two. The minimum distance may occur due to
+  // wrapping; consider "add i3 %i, 5": if %i == 7 then 7 + 5 mod 8 == 4, and so
+  // the minimum distance between %i and %i + 5 is 3.
+  APInt MinDiff = V0Offset - V1Offset,
+        Wrapped = APInt::getMaxValue(Width) - MinDiff + APInt(Width, 1);
+  MinDiff = APIntOps::umin(MinDiff, Wrapped);
+  uint64_t MinDiffBytes = MinDiff.getZExtValue() * std::abs(Var0.Scale);
+
+  // We can't definitely say whether GEP1 is before or after V2 due to wrapping
+  // arithmetic (i.e. for some values of GEP1 and V2 GEP1 < V2, and for other
+  // values GEP1 > V2). We'll therefore only declare NoAlias if both V1Size and
+  // V2Size can fit in the MinDiffBytes gap.
+  return V1Size + std::abs(BaseOffset) <= MinDiffBytes &&
+         V2Size + std::abs(BaseOffset) <= MinDiffBytes;
+}
+
 /// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction
 /// against another pointer.  We know that V1 is a GEP, but we don't know
 /// anything about V2.  UnderlyingV1 is GetUnderlyingObject(GEP1, DL),
 /// UnderlyingV2 is the same for V2.
 ///
 AliasResult BasicAliasAnalysis::aliasGEP(
     const GEPOperator *GEP1, uint64_t V1Size, const AAMDNodes &V1AAInfo,
     const Value *V2, uint64_t V2Size, const AAMDNodes &V2AAInfo,
for (unsigned i = 0, e = GEP1VariableIndices.size(); i != e; ++i) {
         const Value *V = GEP1VariableIndices[i].V;
 
         bool SignKnownZero, SignKnownOne;
         ComputeSignBit(const_cast<Value *>(V), SignKnownZero, SignKnownOne, *DL,
                        0, AC1, nullptr, DT);
 
         // Zero-extension widens the variable, and so forces the sign
         // bit to zero.
-        bool IsZExt = GEP1VariableIndices[i].Extension == EK_ZeroExt;
+        bool IsZExt = GEP1VariableIndices[i].ZExtBits > 0 || isa<ZExtInst>(V);
         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.
         int64_t Scale = GEP1VariableIndices[i].Scale;
         AllPositive =
if (V1Size != MemoryLocation::UnknownSize &&
         V1Size <= Modulo - ModOffset)
       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 > 0 && V2Size <= (uint64_t) GEP1BaseOffset)
       return NoAlias;
+
+    if (constantOffsetHeuristic(GEP1VariableIndices, V1Size, V2Size,
+                                GEP1BaseOffset, DL, AC1, DT))
+      return NoAlias;
   }
 
   // Statically, we can see that the base objects are the same, but the
   // pointers have dynamic offsets which we can't resolve. And none of our
   // little tricks above worked.
   //
   // TODO: Returning PartialAlias instead of MayAlias is a mild hack; the
   // practical effect of this is protecting TBAA in the case of dynamic

 void BasicAliasAnalysis::GetIndexDifference(
     SmallVectorImpl<VariableGEPIndex> &Dest,
     const SmallVectorImpl<VariableGEPIndex> &Src) {
   if (Src.empty())
     return;
 
   for (unsigned i = 0, e = Src.size(); i != e; ++i) {
     const Value *V = Src[i].V;
-    ExtensionKind Extension = Src[i].Extension;
+    unsigned ZExtBits = Src[i].ZExtBits, SExtBits = Src[i].SExtBits;
     int64_t Scale = Src[i].Scale;
 
     // Find V in Dest.  This is N^2, but pointer indices almost never have more
     // than a few variable indexes.
     for (unsigned j = 0, e = Dest.size(); j != e; ++j) {
       if (!isValueEqualInPotentialCycles(Dest[j].V, V) ||
-          Dest[j].Extension != Extension)
+          Dest[j].ZExtBits != ZExtBits || Dest[j].SExtBits != SExtBits)
         continue;
 
       // 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)
         Dest[j].Scale -= Scale;
       else
         Dest.erase(Dest.begin() + j);
       Scale = 0;
       break;
     }
 
     // If we didn't consume this entry, add it to the end of the Dest list.
     if (Scale) {
-      VariableGEPIndex Entry = { V, Extension, -Scale };
+      VariableGEPIndex Entry = {V, ZExtBits, SExtBits, -Scale};
       Dest.push_back(Entry);
     }
   }
 }

test/Analysis/BasicAA/bug.23540.ll

+; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@c = external global i32
+
+; CHECK-LABEL: f
+; CHECK: PartialAlias: i32* %arrayidx, i32* %arrayidx6
+define void @f() {
+  %idxprom = zext i32 undef to i64
+  %add4 = add i32 0, 1
+  %idxprom5 = zext i32 %add4 to i64
+  %arrayidx6 = getelementptr inbounds i32, i32* @c, i64 %idxprom5
+  %arrayidx = getelementptr inbounds i32, i32* @c, i64 %idxprom
+  ret void
+}
+

test/Analysis/BasicAA/bug.23626.ll

+; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-darwin13.4.0"
+
+; CHECK-LABEL: compute1
+; CHECK: PartialAlias:  i32* %arrayidx8, i32* %out
+; CHECK: PartialAlias:  i32* %arrayidx11, i32* %out
+; CHECK: PartialAlias:  i32* %arrayidx11, i32* %arrayidx8
+; CHECK: PartialAlias:  i32* %arrayidx14, i32* %out
+; CHECK: PartialAlias:  i32* %arrayidx14, i32* %arrayidx8
+; CHECK: PartialAlias:  i32* %arrayidx11, i32* %arrayidx14
+define void @compute1(i32 %num.0.lcssa, i32* %out) {
+  %idxprom = zext i32 %num.0.lcssa to i64
+  %arrayidx8 = getelementptr inbounds i32, i32* %out, i64 %idxprom
+  %add9 = or i32 %num.0.lcssa, 1
+  %idxprom10 = zext i32 %add9 to i64
+  %arrayidx11 = getelementptr inbounds i32, i32* %out, i64 %idxprom10
+  %add12 = or i32 %num.0.lcssa, 2
+  %idxprom13 = zext i32 %add12 to i64
+  %arrayidx14 = getelementptr inbounds i32, i32* %out, i64 %idxprom13
+  ret void
+}
+
+; CHECK-LABEL: compute2
+; CHECK: PartialAlias: i32* %arrayidx11, i32* %out.addr
+define void @compute2(i32 %num, i32* %out.addr) {
+  %add9 = add i32 %num, 1
+  %idxprom10 = zext i32 %add9 to i64
+  %arrayidx11 = getelementptr inbounds i32, i32* %out.addr, i64 %idxprom10
+  ret void
+}

test/Analysis/BasicAA/q.bad.ll

+; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "thumbv7--linux-gnueabi"
+
+; CHECK-LABEL: test_zext_sext_amounts255
+; CHECK: NoAlias: i8* %a, i8* %b
+define void @test_zext_sext_amounts255(i8* %mem) {
+  %sext.1 = sext i8 255 to i16
+  %sext.zext.1 = zext i16 %sext.1 to i64
+  %sext.2 = sext i8 255 to i32
+  %sext.zext.2 = zext i32 %sext.2 to i64
+  %a = getelementptr inbounds i8, i8* %mem, i64 %sext.zext.1
+  %b = getelementptr inbounds i8, i8* %mem, i64 %sext.zext.2
+  ret void
+}
+
+; CHECK-LABEL: test_zext_sext_amounts
+; CHECK: PartialAlias: i8* %a, i8* %b
+; %a and %b only PartialAlias as, although they're both zext(sext(%num)) they'll extend the sign by a different
+; number of bits before zext-ing the remainder.
+define void @test_zext_sext_amounts(i8* %mem, i8 %num) {
+  %sext.1 = sext i8 %num to i16
+  %sext.zext.1 = zext i16 %sext.1 to i64
+  %sext.2 = sext i8 %num to i32
+  %sext.zext.2 = zext i32 %sext.2 to i64
+  %a = getelementptr inbounds i8, i8* %mem, i64 %sext.zext.1
+  %b = getelementptr inbounds i8, i8* %mem, i64 %sext.zext.2
+  ret void
+}
+
+; CHECK-LABEL: based_on_pr18068
+; CHECK: NoAlias: i8* %a, i8* %b
+; CHECK: NoAlias: i8* %a, i8* %c
+define void @based_on_pr18068(i32 %loaded, i8* %mem) {
+  %loaded.64 = zext i32 %loaded to i64
+  %add1 = add i32 %loaded, -1 ; unsigned wraps unless %loaded == 0
+  %add1.64 = zext i32 %add1 to i64 ; is zext(%loaded) always != zext(%loaded - 1)? Yes -> NoAlias
+  %sub1 = sub i32 %loaded, 1 ; unsigned wraps iff %loaded == 0
+  %sub1.64 = zext i32 %sub1 to i64 ; is zext(%loaded) always != zext(%loaded - 1)? Yes -> NoAlias
+  %a = getelementptr inbounds i8, i8* %mem, i64 %loaded.64
+  %b = getelementptr inbounds i8, i8* %mem, i64 %add1.64
+  %c = getelementptr inbounds i8, i8* %mem, i64 %sub1.64
+  ret void
+}
+
+; CHECK-LABEL: test_path_dependence
+; CHECK: PartialAlias: i8* %a, i8* %b
+; CHECK: MustAlias: i8* %a, i8* %c
+; CHECK: PartialAlias: i8* %a, i8* %d
+define void @test_path_dependence(i32 %p, i8* %mem) {
+  %p.minus1 = add i32 %p, -1 ; this will always unsigned-wrap, unless %p == 0
+  %p.minus1.64 = zext i32 %p.minus1 to i64
+  %p.64.again = add i64 %p.minus1.64, 1 ; either %p (if we wrapped) or 4294967296 (if we didn't)
+
+  %p.nsw.nuw.minus1 = sub nsw nuw i32 %p, 1 ; as nuw we know %p >= 1, and as nsw %p <=   2147483647
+  %p.nsw.nuw.minus1.64 = zext i32 %p.nsw.nuw.minus1 to i64
+  %p.nsw.nuw.64.again = add nsw nuw i64 %p.nsw.nuw.minus1.64, 1 ; ...so always exactly %p
+
+  %p.nsw.minus1 = sub nsw i32 %p, 1 ; only nsw, so can only guarantee %p != 0x10000000
+  %p.nsw.minus1.64 = zext i32 %p.nsw.minus1 to i64 ; when %p > 0x10000000 (ie <= 0 as a signed number) then the zext will make this a huge positive number
+  %p.nsw.64.again = add nsw i64 %p.nsw.minus1.64, 1 ; ...and so this is very much != %p
+
+  %p.64 = zext i32 %p to i64
+  %a = getelementptr inbounds i8, i8* %mem, i64 %p.64
+  %b = getelementptr inbounds i8, i8* %mem, i64 %p.64.again
+  %c = getelementptr inbounds i8, i8* %mem, i64 %p.nsw.nuw.64.again
+  %d = getelementptr inbounds i8, i8* %mem, i64 %p.nsw.64.again
+  ret void
+}
+
+; CHECK-LABEL: test_zext_sext_255
+; CHECK: NoAlias: i8* %a, i8* %b
+define void @test_zext_sext_255(i8* %mem) {
+  %zext.255 = zext i8 255 to i16 ; 0x00FF
+  %sext.255 = sext i8 255 to i16 ; 0xFFFF
+  %zext.sext.255 = zext i16 %sext.255 to i32 ; 0x0000FFFF
+  %sext.zext.255 = sext i16 %zext.255 to i32 ; 0x000000FF
+  %zext.zext.sext.255 = zext i32 %zext.sext.255 to i64
+  %zext.sext.zext.255 = zext i32 %sext.zext.255 to i64
+  %a = getelementptr inbounds i8, i8* %mem, i64 %zext.zext.sext.255
+  %b = getelementptr inbounds i8, i8* %mem, i64 %zext.sext.zext.255
+  ret void
+}
+
+; CHECK-LABEL: test_zext_sext_num
+; CHECK: PartialAlias: i8* %a, i8* %b
+; %a and %b NoAlias if %num == 255 (see @test_zext_sext_255), but %a and %b NoAlias for other values of %num (e.g. 0)
+define void @test_zext_sext_num(i8* %mem, i8 %num) {
+  %zext.num = zext i8 %num to i16
+  %sext.num = sext i8 %num to i16
+  %zext.sext.num = zext i16 %sext.num to i32
+  %sext.zext.num = sext i16 %zext.num to i32
+  %zext.zext.sext.num = zext i32 %zext.sext.num to i64
+  %zext.sext.zext.num = zext i32 %sext.zext.num to i64
+  %a = getelementptr inbounds i8, i8* %mem, i64 %zext.zext.sext.num
+  %b = getelementptr inbounds i8, i8* %mem, i64 %zext.sext.zext.num
+  ret void
+}
+
+; CHECK-LABEL: uncompressStream
+; CHECK: MustAlias:  i8* %a, i8* %b
+; CHECK: NoAlias:  i8* %a, i8* %c
+define void @uncompressStream(i8* %mem) {
+  %zext.255 = zext i8 255 to i32
+  %sext.255 = sext i8 255 to i32
+  %a = getelementptr inbounds i8, i8* %mem, i32 255
+  %b = getelementptr inbounds i8, i8* %mem, i32 %zext.255
+  %c = getelementptr inbounds i8, i8* %mem, i32 %sext.255
+  ret void
+}
+
+; CHECK-LABEL: constantOffsetHeuristic_i3_i32
+; CHECK: NoAlias:  i32* %a, i32* %b
+; CHECK: NoAlias:  i32* %a, i32* %c
+; CHECK: NoAlias:  i32* %b, i32* %c
+define void @constantOffsetHeuristic_i3_i32(i32* %mem, i3 %val) {
+  %zext.plus.7 = add nsw i3 %val, 7
+  %zext.plus.4 = add nsw i3 %val, 4
+  %zext.val = zext i3 %val to i32
+  %zext.4 = zext i3 %zext.plus.4 to i32
+  %zext.7 = zext i3 %zext.plus.7 to i32
+  %a = getelementptr inbounds i32, i32* %mem, i32 %zext.4
+  %b = getelementptr inbounds i32, i32* %mem, i32 %zext.7
+  %c = getelementptr inbounds i32, i32* %mem, i32 %zext.val
+  ret void
+}
+
+; CHECK-LABEL: constantOffsetHeuristic_i8_i32
+; CHECK: NoAlias:  i32* %a, i32* %b
+; CHECK: NoAlias:  i32* %a, i32* %c
+; CHECK: NoAlias:  i32* %b, i32* %c
+define void @constantOffsetHeuristic_i8_i32(i32* %mem, i8 %val) {
+  %zext.plus.7 = add nsw i8 %val, 7
+  %zext.plus.4 = add nsw i8 %val, 4
+  %zext.val = zext i8 %val to i32
+  %zext.4 = zext i8 %zext.plus.4 to i32
+  %zext.7 = zext i8 %zext.plus.7 to i32
+  %a = getelementptr inbounds i32, i32* %mem, i32 %zext.4
+  %b = getelementptr inbounds i32, i32* %mem, i32 %zext.7
+  %c = getelementptr inbounds i32, i32* %mem, i32 %zext.val
+  ret void
+}
+
+; CHECK-LABEL: constantOffsetHeuristic_i3_i8
+; CHECK: PartialAlias:  i32* %a, i32* %b
+; CHECK: NoAlias:  i32* %a, i32* %c
+; CHECK: PartialAlias:  i32* %b, i32* %c
+define void @constantOffsetHeuristic_i3_i8(i8* %mem, i3 %val) {
+  %zext.plus.7 = add nsw i3 %val, 7
+  %zext.plus.4 = add nsw i3 %val, 4
+  %zext.val = zext i3 %val to i32
+  %zext.4 = zext i3 %zext.plus.4 to i32
+  %zext.7 = zext i3 %zext.plus.7 to i32
+  %a.8 = getelementptr inbounds i8, i8* %mem, i32 %zext.4
+  %b.8 = getelementptr inbounds i8, i8* %mem, i32 %zext.7
+  %c.8 = getelementptr inbounds i8, i8* %mem, i32 %zext.val
+  %a = bitcast i8* %a.8 to i32*
+  %b = bitcast i8* %b.8 to i32*
+  %c = bitcast i8* %c.8 to i32*
+  ret void
+}
+
+; CHECK-LABEL: constantOffsetHeuristic_i8_i8
+; CHECK: PartialAlias:  i32* %a, i32* %b
+; CHECK: NoAlias:  i32* %a, i32* %c
+; CHECK: NoAlias:  i32* %b, i32* %c
+define void @constantOffsetHeuristic_i8_i8(i8* %mem, i8 %val) {
+  %zext.plus.7 = add nsw i8 %val, 7
+  %zext.plus.4 = add nsw i8 %val, 4
+  %zext.val = zext i8 %val to i32
+  %zext.4 = zext i8 %zext.plus.4 to i32
+  %zext.7 = zext i8 %zext.plus.7 to i32
+  %a.8 = getelementptr inbounds i8, i8* %mem, i32 %zext.4
+  %b.8 = getelementptr inbounds i8, i8* %mem, i32 %zext.7
+  %c.8 = getelementptr inbounds i8, i8* %mem, i32 %zext.val
+  %a = bitcast i8* %a.8 to i32*
+  %b = bitcast i8* %b.8 to i32*
+  %c = bitcast i8* %c.8 to i32*
+  ret void
+}