[BasicAA] Fix the handling of sext and zext in the analysis of GEPs.

Hopefully this will end the GEPs saga!

This commit reverts r245394, i.e., it reapplies r221876 while incorporating the
fixes from D11847.
r221876 was not reapplied alone because it was not safe and D11847 was not
applied alone because it needs r221876 to produce correct results.

This should fix PR24596.

Original commit message for r221876:
Let's try this again...

This reverts r219432, plus a bug fix.

Description of the bug in r219432 (by Nick):

The bug was using AllPositive to break out of the loop; if the loop break
condition i != e is changed to i != e && AllPositive then the
test_modulo_analysis_with_global test I've added will fail as the Modulo will
be calculated incorrectly (as the last loop iteration is skipped, so Modulo
isn't updated with its Scale).

Nick also adds this comment:

ComputeSignBit is safe to use in loops as it takes into account phi nodes, and
the  == EK_ZeroEx check is safe in loops as, no matter how the variable changes
between iterations, zero-extensions will always guarantee a zero sign bit. The
isValueEqualInPotentialCycles check is therefore definitely not needed as all
the variable analysis holds no matter how the variables change between loop
iterations.

And this patch also adds another enhancement to GetLinearExpression - basically
to convert ConstantInts to Offsets (see test_const_eval and
test_const_eval_scaled for the situations this improves).

Original commit message:

This reverts r218944, which reverted r218714, plus a bug fix.

Description of the bug in r218714 (by Nick):

The original patch forgot to check if the Scale in VariableGEPIndex flipped the
sign of the variable. The BasicAA pass iterates over the instructions in the
order they appear in the function, and so BasicAliasAnalysis::aliasGEP is
called with the variable it first comes across as parameter GEP1. Adding a
%reorder label puts the definition of %a after %b so aliasGEP is called with %b
as the first parameter and %a as the second. aliasGEP later calculates that %a
== %b + 1 - %idxprom where %idxprom >= 0 (if %a was passed as the first
parameter it would calculate %b == %a - 1 + %idxprom where %idxprom >= 0) -
ignoring that %idxprom is scaled by -1 here lead the patch to incorrectly
conclude that %a > %b.

Revised patch by Nick White, thanks! Thanks to Lang to isolating the bug.
Slightly modified by me to add an early exit from the loop and avoid
unnecessary, but expensive, function calls.

Original commit message:

Two related things:

1. Fixes a bug when calculating the offset in GetLinearExpression. The code
   previously used zext to extend the offset, so negative offsets were converted
   to large positive ones.

2. Enhance aliasGEP to deduce that, if the difference between two GEP
   allocations is positive and all the variables that govern the offset are also
   positive (i.e. the offset is strictly after the higher base pointer), then
   locations that fit in the gap between the two base pointers are NoAlias.

Patch by Nick White!

Message from D11847:
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).

Differential Revision: http://reviews.llvm.org/D11847
Patch by Nick White <n.j.white@gmail.com>!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@246502 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/include/llvm/Analysis/BasicAliasAnalysis.h b/include/llvm/Analysis/BasicAliasAnalysis.h
index eb476367ae64304e6ffddc9b5709658ce8df29e8..3d3bee08206462530947cb0e5a3617c604f65532 100644 (file)
--- a/include/llvm/Analysis/BasicAliasAnalysis.h
+++ b/include/llvm/Analysis/BasicAliasAnalysis.h
@@ -109,16 +109,25 @@ struct BasicAliasAnalysis : public ImmutablePass, public AliasAnalysis {
   }
 
 private:
   }
 
 private:

-  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 {
   struct VariableGEPIndex {

+
+    // An opaque Value - we can't decompose this further.

     const Value *V;
     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 {
     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 {
     }
 
     bool operator!=(const VariableGEPIndex &Other) const {


@@ -150,16 +159,30 @@ private:
   /// Tracks instructions visited by pointsToConstantMemory.
   SmallPtrSet<const Value *, 16> Visited;
 
   /// Tracks instructions visited by pointsToConstantMemory.
   SmallPtrSet<const Value *, 16> Visited;
 

-  static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset,
-                                    ExtensionKind &Extension,
-                                    const DataLayout &DL, unsigned Depth,
-                                    AssumptionCache *AC, DominatorTree *DT);
+  static const Value *
+  GetLinearExpression(const Value *V, APInt &Scale, APInt &Offset,
+                      unsigned &ZExtBits, unsigned &SExtBits,
+                      const DataLayout &DL, unsigned Depth, AssumptionCache *AC,
+                      DominatorTree *DT, bool &NSW, bool &NUW);

 
   static const Value *
   DecomposeGEPExpression(const Value *V, int64_t &BaseOffs,
                          SmallVectorImpl<VariableGEPIndex> &VarIndices,
                          bool &MaxLookupReached, const DataLayout &DL,
                          AssumptionCache *AC, DominatorTree *DT);
 
   static const Value *
   DecomposeGEPExpression(const Value *V, int64_t &BaseOffs,
                          SmallVectorImpl<VariableGEPIndex> &VarIndices,
                          bool &MaxLookupReached, const DataLayout &DL,
                          AssumptionCache *AC, DominatorTree *DT);

+  /// \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);

 
   bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
 
 
   bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
 

diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp
index b73dfa3f72bfe0fa71f7972ec12377c63e5d1f7f..a6a25f9326a015f23fa39c95b1b75f29c288d5c9 100644 (file)
--- a/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/lib/Analysis/BasicAliasAnalysis.cpp
@@ -177,10 +177,10 @@ static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
 ///
 /// Note that this looks through extends, so the high bits may not be
 /// represented in the result.
 ///
 /// Note that this looks through extends, so the high bits may not be
 /// represented in the result.

-/*static*/ Value *BasicAliasAnalysis::GetLinearExpression(
-    Value *V, APInt &Scale, APInt &Offset, ExtensionKind &Extension,
-    const DataLayout &DL, unsigned Depth, AssumptionCache *AC,
-    DominatorTree *DT) {
+/*static*/ const Value *BasicAliasAnalysis::GetLinearExpression(
+    const Value *V, APInt &Scale, APInt &Offset, unsigned &ZExtBits,
+    unsigned &SExtBits, const DataLayout &DL, unsigned Depth,
+    AssumptionCache *AC, DominatorTree *DT, bool &NSW, bool &NUW) {

   assert(V->getType()->isIntegerTy() && "Not an integer value");
 
   // Limit our recursion depth.
   assert(V->getType()->isIntegerTy() && "Not an integer value");
 
   // Limit our recursion depth.


@@ -190,55 +190,125 @@ static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
     return V;
   }
 
     return V;
   }
 

-  if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) {
+  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 (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) {

     if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
     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:
       switch (BOp->getOpcode()) {
       default:

-        break;
+        // 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,
       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:
       // 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:
       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:
       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;
       }
         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.
     }
   }
 
   // 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);
     Value *CastOp = cast<CastInst>(V)->getOperand(0);

-    unsigned OldWidth = Scale.getBitWidth();
+    unsigned NewWidth = V->getType()->getPrimitiveSizeInBits();

     unsigned SmallWidth = CastOp->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);
-    Offset = Offset.zext(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;
   }
 
     return Result;
   }


@@ -318,7 +388,7 @@ static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
     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) {
     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.
       // Compute the (potentially symbolic) offset in bytes for this index.
       if (StructType *STy = dyn_cast<StructType>(*GTI++)) {
         // For a struct, add the member offset.


@@ -331,7 +401,7 @@ static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
       }
 
       // For an array/pointer, add the element offset, explicitly scaled.
       }
 
       // 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();
         if (CIdx->isZero())
           continue;
         BaseOffs += DL.getTypeAllocSize(*GTI) * CIdx->getSExtValue();


@@ -339,18 +409,20 @@ static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
       }
 
       uint64_t Scale = DL.getTypeAllocSize(*GTI);
       }
 
       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 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);
 
       // 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.
 
       // 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.


@@ -362,7 +434,8 @@ static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
       //   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) {
       //   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;
           Scale += VarIndices[i].Scale;
           VarIndices.erase(VarIndices.begin() + i);
           break;


@@ -371,13 +444,13 @@ static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
 
       // Make sure that we have a scale that makes sense for this target's
       // pointer size.
 
       // 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) {
         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);
       }
                                   static_cast<int64_t>(Scale)};
         VarIndices.push_back(Entry);
       }


@@ -948,12 +1021,42 @@ AliasResult BasicAliasAnalysis::aliasGEP(
     }
   }
 
     }
   }
 

-  // Try to distinguish something like &A[i][1] against &A[42][0].
-  // Grab the least significant bit set in any of the scales.

   if (!GEP1VariableIndices.empty()) {
     uint64_t Modulo = 0;
   if (!GEP1VariableIndices.empty()) {
     uint64_t Modulo = 0;

-    for (unsigned i = 0, e = GEP1VariableIndices.size(); i != e; ++i)
+    bool AllPositive = true;
+    for (unsigned i = 0, e = GEP1VariableIndices.size(); i != e; ++i) {
+
+      // Try to distinguish something like &A[i][1] against &A[42][0].
+      // Grab the least significant bit set in any of the scales. We
+      // don't need std::abs here (even if the scale's negative) as we'll
+      // be ^'ing Modulo with itself later.

       Modulo |= (uint64_t)GEP1VariableIndices[i].Scale;
       Modulo |= (uint64_t)GEP1VariableIndices[i].Scale;

+
+      if (AllPositive) {
+        // 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:
+        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].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 =
+            (SignKnownZero && Scale >= 0) || (SignKnownOne && Scale < 0);
+      }
+    }
+

     Modulo = Modulo ^ (Modulo & (Modulo - 1));
 
     // We can compute the difference between the two addresses
     Modulo = Modulo ^ (Modulo & (Modulo - 1));
 
     // We can compute the difference between the two addresses


@@ -964,6 +1067,16 @@ AliasResult BasicAliasAnalysis::aliasGEP(
         V2Size != MemoryLocation::UnknownSize && ModOffset >= V2Size &&
         V1Size <= Modulo - ModOffset)
       return NoAlias;
         V2Size != MemoryLocation::UnknownSize && ModOffset >= V2Size &&
         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
   }
 
   // Statically, we can see that the base objects are the same, but the


@@ -1333,14 +1446,14 @@ void BasicAliasAnalysis::GetIndexDifference(
 
   for (unsigned i = 0, e = Src.size(); i != e; ++i) {
     const Value *V = Src[i].V;
 
   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) ||
     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
         continue;
 
       // If we found it, subtract off Scale V's from the entry in Dest.  If it


@@ -1355,8 +1468,62 @@ void BasicAliasAnalysis::GetIndexDifference(
 
     // If we didn't consume this entry, add it to the end of the Dest list.
     if (Scale) {
 
     // 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);
     }
   }
 }
       Dest.push_back(Entry);
     }
   }
 }

+
+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;
+}

diff --git a/test/Analysis/BasicAA/bug.23540.ll b/test/Analysis/BasicAA/bug.23540.ll
new file mode 100644 (file)
index 0000000..f693bcf
--- /dev/null
+++ b/test/Analysis/BasicAA/bug.23540.ll
@@ -0,0 +1,17 @@
+; 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
+}
+

diff --git a/test/Analysis/BasicAA/bug.23626.ll b/test/Analysis/BasicAA/bug.23626.ll
new file mode 100644 (file)
index 0000000..6a1478c
--- /dev/null
+++ b/test/Analysis/BasicAA/bug.23626.ll
@@ -0,0 +1,31 @@
+; 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
+}

diff --git a/test/Analysis/BasicAA/phi-aa.ll b/test/Analysis/BasicAA/phi-aa.ll
index a72778277bb241a5233475d94e3f2f443d1107a7..3944e9e435666fa2cd0a4fdee6c744c88d14b411 100644 (file)
--- a/test/Analysis/BasicAA/phi-aa.ll
+++ b/test/Analysis/BasicAA/phi-aa.ll
@@ -39,6 +39,7 @@ return:
 
 ; CHECK-LABEL: pr18068
 ; CHECK: MayAlias: i32* %0, i32* %arrayidx5
 
 ; CHECK-LABEL: pr18068
 ; CHECK: MayAlias: i32* %0, i32* %arrayidx5

+; CHECK: NoAlias: i32* %arrayidx13, i32* %arrayidx5

 
 define i32 @pr18068(i32* %jj7, i32* %j) {
 entry:
 
 define i32 @pr18068(i32* %jj7, i32* %j) {
 entry:

diff --git a/test/Analysis/BasicAA/q.bad.ll b/test/Analysis/BasicAA/q.bad.ll
new file mode 100644 (file)
index 0000000..f2de6a7
--- /dev/null
+++ b/test/Analysis/BasicAA/q.bad.ll
@@ -0,0 +1,180 @@
+; 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
+}

diff --git a/test/Analysis/BasicAA/zext.ll b/test/Analysis/BasicAA/zext.ll
new file mode 100644 (file)
index 0000000..685d45b
--- /dev/null
+++ b/test/Analysis/BasicAA/zext.ll
@@ -0,0 +1,231 @@
+; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; CHECK-LABEL: test_with_zext
+; CHECK:  NoAlias: i8* %a, i8* %b
+
+define void @test_with_zext() {
+  %1 = tail call i8* @malloc(i64 120)
+  %a = getelementptr inbounds i8, i8* %1, i64 8
+  %2 = getelementptr inbounds i8, i8* %1, i64 16
+  %3 = zext i32 3 to i64
+  %b = getelementptr inbounds i8, i8* %2, i64 %3
+  ret void
+}
+
+; CHECK-LABEL: test_with_lshr
+; CHECK:  NoAlias: i8* %a, i8* %b
+
+define void @test_with_lshr(i64 %i) {
+  %1 = tail call i8* @malloc(i64 120)
+  %a = getelementptr inbounds i8, i8* %1, i64 8
+  %2 = getelementptr inbounds i8, i8* %1, i64 16
+  %3 = lshr i64 %i, 2
+  %b = getelementptr inbounds i8, i8* %2, i64 %3
+  ret void
+}
+
+; CHECK-LABEL: test_with_a_loop
+; CHECK:  NoAlias: i8* %a, i8* %b
+
+define void @test_with_a_loop(i8* %mem) {
+  br label %for.loop
+
+for.loop:
+  %i = phi i32 [ 0, %0 ], [ %i.plus1, %for.loop ]
+  %a = getelementptr inbounds i8, i8* %mem, i64 8
+  %a.plus1 = getelementptr inbounds i8, i8* %mem, i64 16
+  %i.64 = zext i32 %i to i64
+  %b = getelementptr inbounds i8, i8* %a.plus1, i64 %i.64
+  %i.plus1 = add nuw nsw i32 %i, 1
+  %cmp = icmp eq i32 %i.plus1, 10
+  br i1 %cmp, label %for.loop.exit, label %for.loop
+
+for.loop.exit:
+  ret void
+}
+
+; CHECK-LABEL: test_with_varying_base_pointer_in_loop
+; CHECK:  NoAlias: i8* %a, i8* %b
+
+define void @test_with_varying_base_pointer_in_loop(i8* %mem.orig) {
+  br label %for.loop
+
+for.loop:
+  %mem = phi i8* [ %mem.orig, %0 ], [ %mem.plus1, %for.loop ]
+  %i = phi i32 [ 0, %0 ], [ %i.plus1, %for.loop ]
+  %a = getelementptr inbounds i8, i8* %mem, i64 8
+  %a.plus1 = getelementptr inbounds i8, i8* %mem, i64 16
+  %i.64 = zext i32 %i to i64
+  %b = getelementptr inbounds i8, i8* %a.plus1, i64 %i.64
+  %i.plus1 = add nuw nsw i32 %i, 1
+  %mem.plus1 = getelementptr inbounds i8, i8* %mem, i64 8
+  %cmp = icmp eq i32 %i.plus1, 10
+  br i1 %cmp, label %for.loop.exit, label %for.loop
+
+for.loop.exit:
+  ret void
+}
+
+; CHECK-LABEL: test_sign_extension
+; CHECK:  PartialAlias: i64* %b.i64, i8* %a
+
+define void @test_sign_extension(i32 %p) {
+  %1 = tail call i8* @malloc(i64 120)
+  %p.64 = zext i32 %p to i64
+  %a = getelementptr inbounds i8, i8* %1, i64 %p.64
+  %p.minus1 = add i32 %p, -1
+  %p.minus1.64 = zext i32 %p.minus1 to i64
+  %b.i8 = getelementptr inbounds i8, i8* %1, i64 %p.minus1.64
+  %b.i64 = bitcast i8* %b.i8 to i64*
+  ret void
+}
+
+; CHECK-LABEL: test_fe_tools
+; CHECK:  PartialAlias: i32* %a, i32* %b
+
+define void @test_fe_tools([8 x i32]* %values) {
+  br label %reorder
+
+for.loop:
+  %i = phi i32 [ 0, %reorder ], [ %i.next, %for.loop ]
+  %idxprom = zext i32 %i to i64
+  %b = getelementptr inbounds [8 x i32], [8 x i32]* %values, i64 0, i64 %idxprom
+  %i.next = add nuw nsw i32 %i, 1
+  %1 = icmp eq i32 %i.next, 10
+  br i1 %1, label %for.loop.exit, label %for.loop
+
+reorder:
+  %a = getelementptr inbounds [8 x i32], [8 x i32]* %values, i64 0, i64 1
+  br label %for.loop
+
+for.loop.exit:
+  ret void
+}
+
+@b = global i32 0, align 4
+@d = global i32 0, align 4
+
+; CHECK-LABEL: test_spec2006
+; CHECK:  PartialAlias: i32** %x, i32** %y
+
+define void @test_spec2006() {
+  %h = alloca [1 x [2 x i32*]], align 16
+  %d.val = load i32, i32* @d, align 4
+  %d.promoted = sext i32 %d.val to i64
+  %1 = icmp slt i32 %d.val, 2
+  br i1 %1, label %.lr.ph, label %3
+
+.lr.ph:                                           ; preds = %0
+  br label %2
+
+; <label>:2                                       ; preds = %.lr.ph, %2
+  %i = phi i32 [ %d.val, %.lr.ph ], [ %i.plus1, %2 ]
+  %i.promoted = sext i32 %i to i64
+  %x = getelementptr inbounds [1 x [2 x i32*]], [1 x [2 x i32*]]* %h, i64 0, i64 %d.promoted, i64 %i.promoted
+  %i.plus1 = add nsw i32 %i, 1
+  %cmp = icmp slt i32 %i.plus1, 2
+  br i1 %cmp, label %2, label %3
+
+; <label>:3                                      ; preds = %._crit_edge, %0
+  %y = getelementptr inbounds [1 x [2 x i32*]], [1 x [2 x i32*]]* %h, i64 0, i64 0, i64 1
+  ret void
+}
+
+; CHECK-LABEL: test_modulo_analysis_easy_case
+; CHECK:  NoAlias: i32** %x, i32** %y
+
+define void @test_modulo_analysis_easy_case(i64 %i) {
+  %h = alloca [1 x [2 x i32*]], align 16
+  %x = getelementptr inbounds [1 x [2 x i32*]], [1 x [2 x i32*]]* %h, i64 0, i64 %i, i64 0
+  %y = getelementptr inbounds [1 x [2 x i32*]], [1 x [2 x i32*]]* %h, i64 0, i64 0, i64 1
+  ret void
+}
+
+; CHECK-LABEL: test_modulo_analysis_in_loop
+; CHECK:  NoAlias: i32** %x, i32** %y
+
+define void @test_modulo_analysis_in_loop() {
+  %h = alloca [1 x [2 x i32*]], align 16
+  br label %for.loop
+
+for.loop:
+  %i = phi i32 [ 0, %0 ], [ %i.plus1, %for.loop ]
+  %i.promoted = sext i32 %i to i64
+  %x = getelementptr inbounds [1 x [2 x i32*]], [1 x [2 x i32*]]* %h, i64 0, i64 %i.promoted, i64 0
+  %y = getelementptr inbounds [1 x [2 x i32*]], [1 x [2 x i32*]]* %h, i64 0, i64 0, i64 1
+  %i.plus1 = add nsw i32 %i, 1
+  %cmp = icmp slt i32 %i.plus1, 2
+  br i1 %cmp, label %for.loop, label %for.loop.exit
+
+for.loop.exit:
+  ret void
+}
+
+; CHECK-LABEL: test_modulo_analysis_with_global
+; CHECK:  PartialAlias: i32** %x, i32** %y
+
+define void @test_modulo_analysis_with_global() {
+  %h = alloca [1 x [2 x i32*]], align 16
+  %b = load i32, i32* @b, align 4
+  %b.promoted = sext i32 %b to i64
+  br label %for.loop
+
+for.loop:
+  %i = phi i32 [ 0, %0 ], [ %i.plus1, %for.loop ]
+  %i.promoted = sext i32 %i to i64
+  %x = getelementptr inbounds [1 x [2 x i32*]], [1 x [2 x i32*]]* %h, i64 0, i64 %i.promoted, i64 %b.promoted
+  %y = getelementptr inbounds [1 x [2 x i32*]], [1 x [2 x i32*]]* %h, i64 0, i64 0, i64 1
+  %i.plus1 = add nsw i32 %i, 1
+  %cmp = icmp slt i32 %i.plus1, 2
+  br i1 %cmp, label %for.loop, label %for.loop.exit
+
+for.loop.exit:
+  ret void
+}
+
+; CHECK-LABEL: test_const_eval
+; CHECK: NoAlias: i8* %a, i8* %b
+define void @test_const_eval(i8* %ptr, i64 %offset) {
+  %a = getelementptr inbounds i8, i8* %ptr, i64 %offset
+  %a.dup = getelementptr inbounds i8, i8* %ptr, i64 %offset
+  %three = zext i32 3 to i64
+  %b = getelementptr inbounds i8, i8* %a.dup, i64 %three
+  ret void
+}
+
+; CHECK-LABEL: test_const_eval_scaled
+; CHECK: MustAlias: i8* %a, i8* %b
+define void @test_const_eval_scaled(i8* %ptr) {
+  %three = zext i32 3 to i64
+  %six = mul i64 %three, 2
+  %a = getelementptr inbounds i8, i8* %ptr, i64 %six
+  %b = getelementptr inbounds i8, i8* %ptr, i64 6
+  ret void
+}
+
+; CHECK-LABEL: Function: foo
+; CHECK: MustAlias:    float* %arrayidx, float* %arrayidx4.84
+define float @foo(i32 *%A, float %rend, float** %wayar)  {
+entry:
+  %x0 = load i32, i32* %A, align 4
+  %conv = sext i32 %x0 to i64
+  %mul = shl nsw i64 %conv, 3
+  %call = tail call i8* @malloc(i64 %mul)
+  %x1 = bitcast i8* %call to float*
+
+  %sub = add nsw i32 %x0, -1
+  %idxprom = sext i32 %sub to i64
+  %arrayidx = getelementptr inbounds float, float* %x1, i64 %idxprom
+  store float %rend, float* %arrayidx, align 8
+
+  %indvars.iv76.83 = add nsw i64 %conv, -1
+  %arrayidx4.84 = getelementptr inbounds float, float* %x1, i64 %indvars.iv76.83
+  %x4 = load float, float* %arrayidx4.84, align 8
+
+  ret float %x4
+}
+
+; Function Attrs: nounwind
+declare noalias i8* @malloc(i64)