[BasicAA] Be more careful with modulo ops on VariableGEPIndex.

[fhahn]

Summary

(V * Scale) % X may not produce the same result for any possible value
of V, e.g. if the multiplication overflows. This means we currently
incorrectly determine NoAlias in some cases.

This patch adjusts the code linarizing GEPs to try to track if the
modulo semantics are preserved. There might still be GEPs and cases
where we miss, but it should address a few critical cases.

[nikic]

I'm somewhat confused by the implementation approach in this patch. I think there's really two orthogonal cases: The first is if all operations are non-wrapping, in which case we can optimize for arbitrary modulos. The second is that we can always use power of two factors from the GCD, because arithmetic is over a power of two field.

I think handling for these two cases should be split. The first part can be handled via flag, and the second part can be handled by only extracting the power of two part if the flag is not set. I think this should both make the semantics of the flag clear and be more precise.

[fhahn]

Rebased on top of latest changes.

In D99424#2653505, @nikic wrote:

I'm somewhat confused by the implementation approach in this patch. I think there's really two orthogonal cases: The first is if all operations are non-wrapping, in which case we can optimize for arbitrary modulos. The second is that we can always use power of two factors from the GCD, because arithmetic is over a power of two field.

I think handling for these two cases should be split. The first part can be handled via flag, and the second part can be handled by only extracting the power of two part if the flag is not set. I think this should both make the semantics of the flag clear and be more precise.

I'm not sure where the logic should be split? I tried to just have a may-wrap flag and then check if Scale is a power-of-2 when the scale is used for the modulo computations. But I think that wouldn't correctly handle cases like (a + x) * 2^y, if the multiply operand gets distributed. Or were you thinking about something else?

[nikic]

llvm/test/Analysis/BasicAA/gep-modulo.ll

83–84

This is an example of the case I have in mind: This can be NoAlias (https://alive2.llvm.org/ce/z/yYFAAz) even though the mul+sub can wrap. Despite the wrapping, we are still guaranteed that the power-of-2 part of the GCD still holds.

[nikic]

llvm/test/Analysis/BasicAA/gep-modulo.ll

83–84

Eh, maybe I'm wrong here regarding the general case. I'll have to think about it more carefully.

[fhahn]

llvm/test/Analysis/BasicAA/gep-modulo.ll

83–84

I think it may hold for cases where we compute % power-of-2, but not if the operand is not a power-of-2? I'm not too familiar with the code that actually uses the modulo, but if that's the case we may be able to use this? If so, we should be able to do so by adjusting the check to
if (!DecompGEP1.VarIndices[i].PreservesModulo && !Scale.isPowerOf2())

[fhahn]

The impact of this seems quite limited. Below the AA stats for MultiSource/SPEC2000/SPEC2006 on X86 with -O3 -flto:

aa.NumMayAlias
Program                                        base      basicaa   diff 
 test-suite...urce/Applications/aha/aha.test   271.00    292.00     7.7%
 test-suite...rks/FreeBench/pifft/pifft.test   14990.00  15689.00   4.7%
 test-suite...CFP2006/433.milc/433.milc.test   13793.00  14243.00   3.3%
 test-suite...-dbl/LinearDependence-dbl.test   522.00    525.00     0.6%
 test-suite...T2000/300.twolf/300.twolf.test   45884.00  46038.00   0.3%
 test-suite...TimberWolfMC/timberwolfmc.test   49643.00  49798.00   0.3%
 test-suite...-flt/LinearDependence-flt.test   1216.00   1219.00    0.2%
 test-suite...CFP2000/177.mesa/177.mesa.test   67899.00  68059.00   0.2%
 test-suite.../CINT2006/429.mcf/429.mcf.test   1134.00   1136.00    0.2%
 test-suite.../CINT2000/181.mcf/181.mcf.test   1173.00   1175.00    0.2%
 test-suite...libquantum/462.libquantum.test   3498.00   3502.00    0.1%
 test-suite...ications/JM/lencod/lencod.test   293097.00 293418.00  0.1%
 test-suite...nal/skidmarks10/skidmarks.test   16112.00  16126.00   0.1%
 test-suite...006/453.povray/453.povray.test   120925.00 121011.00  0.1%
 test-suite.../CINT2000/254.gap/254.gap.test   67251.00  67293.00   0.1%
 Geomean difference                                                 0.5%

aa.NumMustAlias
Program                                        base     basicaa  diff 
 test-suite...CFP2006/433.milc/433.milc.test   1932.00  1901.00  -1.6%
 test-suite.../Benchmarks/Bullet/bullet.test   25887.00 25875.00 -0.0%
 test-suite...CFP2000/177.mesa/177.mesa.test   8657.00  8653.00  -0.0%
 test-suite...006/453.povray/453.povray.test   28386.00 28374.00 -0.0%
 Geomean difference                                              -0.4%

aa.NumNoAlias
Program                                        base       basicaa    diff 
 test-suite...urce/Applications/aha/aha.test   4913.00    4832.00    -1.6%
 test-suite...rks/FreeBench/pifft/pifft.test   96670.00   95195.00   -1.5%
 test-suite...CFP2006/433.milc/433.milc.test   96144.00   95308.00   -0.9%
 test-suite...-dbl/LinearDependence-dbl.test   3488.00    3461.00    -0.8%
 test-suite...-flt/LinearDependence-flt.test   8855.00    8828.00    -0.3%
 test-suite...TimberWolfMC/timberwolfmc.test   306639.00  305968.00  -0.2%
 test-suite...T2000/300.twolf/300.twolf.test   458839.00  458169.00  -0.1%
 test-suite...000/183.equake/183.equake.test   75059.00   75009.00   -0.1%
 test-suite...libquantum/462.libquantum.test   7910.00    7906.00    -0.1%
 test-suite...CFP2000/177.mesa/177.mesa.test   607413.00  607138.00  -0.0%
 test-suite...oxyApps-C/miniAMR/miniAMR.test   120107.00  120076.00  -0.0%
 test-suite.../CINT2000/254.gap/254.gap.test   193489.00  193447.00  -0.0%
 test-suite.../CINT2000/181.mcf/181.mcf.test   10422.00   10420.00   -0.0%
 test-suite.../CINT2006/429.mcf/429.mcf.test   12104.00   12102.00   -0.0%
 test-suite...ications/JM/lencod/lencod.test   2077915.00 2077590.00 -0.0%
 Geomean difference                                                  -0.2%

And the size impact (binary changes to 9 out of 237 binaries)

Same hash: 228 (filtered out)
Remaining: 9
Metric: size.__text

Program                                        base     basicaa  diff
 test-suite...arks/mafft/pairlocalalign.test    233639   233927   0.1%
 test-suite...-dbl/LinearDependence-dbl.test    58195    58243    0.1%
 test-suite.../Benchmarks/Bullet/bullet.test    309159   309175   0.0%
 test-suite...006/453.povray/453.povray.test    1152978  1152994  0.0%
 test-suite...CFP2000/177.mesa/177.mesa.test    694753   694753   0.0%
 test-suite.../CINT2006/403.gcc/403.gcc.test    3238353  3238353  0.0%
 test-suite.../CINT2000/176.gcc/176.gcc.test    1429678  1429678  0.0%
 test-suite...CFP2006/433.milc/433.milc.test    119989   119861  -0.1%
 test-suite...-flt/LinearDependence-flt.test    54951    54743   -0.4%

There's no difference with special handling for % power-of-2.

[fhahn]

ping :)

[fhahn]

ping :)

[nikic]

Okay, I've finally gotten around to looking into this in more detail. Because thinking about this really fries my brain, I ended up modelling this in alive2 (hopefully correctly...)

https://alive2.llvm.org/ce/z/HYBxGs This is the general case and shows that we only need nsw flags on the arithmetic, rather than both nuw and nsw. This makes sense, as all the arithmetic involved is signed.

https://alive2.llvm.org/ce/z/qXicaB This shows that it is indeed safe to always take the power-of-2 portion of the scale, even if the arithmetic is not nsw.

[fhahn]

In D99424#2709964, @nikic wrote:

Okay, I've finally gotten around to looking into this in more detail. Because thinking about this really fries my brain, I ended up modelling this in alive2 (hopefully correctly...)

https://alive2.llvm.org/ce/z/HYBxGs This is the general case and shows that we only need nsw flags on the arithmetic, rather than both nuw and nsw. This makes sense, as all the arithmetic involved is signed.

https://alive2.llvm.org/ce/z/qXicaB This shows that it is indeed safe to always take the power-of-2 portion of the scale, even if the arithmetic is not nsw.

Thanks for checking with Alive. I've updated the code now to just track the NSW flag for LinearExpression/VariableGEPIndex and added a power-of-2 check for the scale.

[fhahn]

ping :)

[nikic]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

242–258

Probably doesn't really matter, but this should be true. Note that the expression here is Val * 0 + Const.

322–328

This should be E.IsNSW &= NSW, to keep it as a plain NSW flag without further semantics.

1158

What I had in mind here is something like this:

APInt Scale = DecompGEP1.VarIndices[i].Scale;
if (!DecompGEP1.VarIndices[i].IsNSW)
  Scale = APInt::getOneBitSet(
      Scale.getBitWidth(), Scale.countTrailingZeros());

And then continue with the previous implementation. This preserves a power of two factor, even if the whole scale is not power of two.

1728

This doesn't appear to be tested.

llvm/test/Analysis/BasicAA/gep-alias.ll

164

With the suggested change to the power of two handling, this change shouldn't be needed anymore.

[fhahn]

Addressed comments, thanks!

[fhahn]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

242–258

Ah right, Val is multiplied by 0 here. Updated.

322–328

Yes, I also removed the outdated comment.

1158

Updated, thanks!

1728

I added a test in ef78325c1033 and also removed the outdated comment.

llvm/test/Analysis/BasicAA/gep-alias.ll

164

Correct, I removed the changes, thanks!

[nikic]

LGTM, thanks!

[mstorsjo]

I’ve bisected a miscompilation to this commit, FYI. Looking into a repro now.

[mstorsjo]

The problem appears with https://martin.st/temp/pixlet-preproc.c, compiled with “clang -target aarch64-w64-mingw32 -c -O3 pixlet-preproc.c”. I haven’t pinpointed exactly what changes and whether that’s wrong or if the source itself relies on something undefined though, or if there’s some strict aliasing violation.

[fhahn]

In D99424#2849458, @mstorsjo wrote:

The problem appears with https://martin.st/temp/pixlet-preproc.c, compiled with “clang -target aarch64-w64-mingw32 -c -O3 pixlet-preproc.c”. I haven’t pinpointed exactly what changes and whether that’s wrong or if the source itself relies on something undefined though, or if there’s some strict aliasing violation.

Thanks for the heads-up!

I suspect that setting Scale = APInt::getOneBitSet(Scale.getBitWidth(), may be at fault here. With the change below, which makes BasicAA more conservative for that case, I don't get any differences with your reproducer. Could you try if that fixes the end-to-end miscomputation?

diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
index da489b8d457f..81823b7ea778 100644
--- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
@@ -1149,8 +1149,7 @@ AliasResult BasicAAResult::aliasGEP(
     for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) {
       APInt Scale = DecompGEP1.VarIndices[i].Scale;
       if (!DecompGEP1.VarIndices[i].IsNSW)
-        Scale = APInt::getOneBitSet(Scale.getBitWidth(),
-                                    Scale.countTrailingZeros());
+        GCD = APInt(Scale.getBitWidth(), 1);

       if (i == 0)
         GCD = Scale.abs();

[fhahn]

In D99424#2849581, @fhahn wrote:

In D99424#2849458, @mstorsjo wrote:

The problem appears with https://martin.st/temp/pixlet-preproc.c, compiled with “clang -target aarch64-w64-mingw32 -c -O3 pixlet-preproc.c”. I haven’t pinpointed exactly what changes and whether that’s wrong or if the source itself relies on something undefined though, or if there’s some strict aliasing violation.

If you manage to reduce it further down, that would be very helpful. Unfortunately it looks like the only difference comes from the MachineScheduler, so it is a bit tricky to extract a nice test case.

[uabelho]

I've also bisected a miscompile to this patch. I don't know at all what is happening but the suggested fix

-        Scale = APInt::getOneBitSet(Scale.getBitWidth(),
-                                    Scale.countTrailingZeros());
+        GCD = APInt(Scale.getBitWidth(), 1);

makes the miscompile go away.

[fhahn]

In D99424#2849817, @uabelho wrote:

I've also bisected a miscompile to this patch. I don't know at all what is happening but the suggested fix

Any chance you could share the reproducer?

[uabelho]

In D99424#2849830, @fhahn wrote:

In D99424#2849817, @uabelho wrote:

I've also bisected a miscompile to this patch. I don't know at all what is happening but the suggested fix

Any chance you could share the reproducer?

I'll see. It's for my out-of-tree target so it takes a bit of fiddling to extract something that could be useful to you.

[mstorsjo]

In D99424#2849581, @fhahn wrote:

In D99424#2849458, @mstorsjo wrote:

The problem appears with https://martin.st/temp/pixlet-preproc.c, compiled with “clang -target aarch64-w64-mingw32 -c -O3 pixlet-preproc.c”. I haven’t pinpointed exactly what changes and whether that’s wrong or if the source itself relies on something undefined though, or if there’s some strict aliasing violation.

Thanks for the heads-up!

I suspect that setting Scale = APInt::getOneBitSet(Scale.getBitWidth(), may be at fault here. With the change below, which makes BasicAA more conservative for that case, I don't get any differences with your reproducer. Could you try if that fixes the end-to-end miscomputation?

Thanks! That does indeed fix my issue, and it also fixes another failed testcase that I hadn’t inspected closer yet.

[mstorsjo]

In D99424#2849596, @fhahn wrote:

In D99424#2849581, @fhahn wrote:

In D99424#2849458, @mstorsjo wrote:

The problem appears with https://martin.st/temp/pixlet-preproc.c, compiled with “clang -target aarch64-w64-mingw32 -c -O3 pixlet-preproc.c”. I haven’t pinpointed exactly what changes and whether that’s wrong or if the source itself relies on something undefined though, or if there’s some strict aliasing violation.

If you manage to reduce it further down, that would be very helpful. Unfortunately it looks like the only difference comes from the MachineScheduler, so it is a bit tricky to extract a nice test case.

FWIW, if you’ve got access to aarch64 linux, I would expect that you can reproduce the same issue there. (I haven’t verified myself yet.) To try it out at runtime, you should be able to do this:

git clone git://source.ffmpeg.org/ffmpeg
cd ffmpeg
./configure --cc=clang --samples=/path/to/empty/dir
make fate-rsync # sync data samples for running tests, into the path specified above
make -j$(nproc) fate-pixlet-rgb fate-twinvq

The miscompilation happens in object files libavcodec/pixlet.o and libavcodec/twinvq.o.

(Sorry I'm not of more assistance in narrowing down the actual change itself at the moment.)

[fhahn]

Ok, after another look, I think the problem was that setting Scale as in this patch may turn Scale from a negative to a positive number, which in turn means that AllNonNegative may be set incorrectly, which should be independent of the scale used for the GCD.

I pushed a test for that scenario (returned noalias based on all indices being non-negative) in f4ea6531e677. And a fix to avoid nuking the sign of the original Scale: e6d22d0174e0 . This is likely only temporary, as relying on the sign of the scale is also problematic when the operations wrap.

@nikic it would be great if you could take a quick look at the commits. I'll probably post a follow-up in the next few days for review.

@mstorsjo @uabelho could you check if e6d22d0174e0 fixes the issues you are seeing? I checked with @mstorsjo's example and with the new patch we get the same results as with D99424 reverted.

[mstorsjo]

In D99424#2851015, @fhahn wrote:

@mstorsjo @uabelho could you check if e6d22d0174e0 fixes the issues you are seeing? I checked with @mstorsjo's example and with the new patch we get the same results as with D99424 reverted.

Thanks! It does seem like that commit fixes the issues I was observing in both those two testcases.

[uabelho]

In D99424#2851015, @fhahn wrote:

Ok, after another look, I think the problem was that setting Scale as in this patch may turn Scale from a negative to a positive number, which in turn means that AllNonNegative may be set incorrectly, which should be independent of the scale used for the GCD.

I pushed a test for that scenario (returned noalias based on all indices being non-negative) in f4ea6531e677. And a fix to avoid nuking the sign of the original Scale: e6d22d0174e0 . This is likely only temporary, as relying on the sign of the scale is also problematic when the operations wrap.

@nikic it would be great if you could take a quick look at the commits. I'll probably post a follow-up in the next few days for review.

@mstorsjo @uabelho could you check if e6d22d0174e0 fixes the issues you are seeing? I checked with @mstorsjo's example and with the new patch we get the same results as with D99424 reverted.

It helps in my case. The miscompile goes away with e6d22d0174e0. Thanks!

[fhahn]

Thanks @mstorsjo & @uabelho !

llvm/include/llvm/Analysis/BasicAliasAnalysis.h

struct VariableGEPIndex {
     // 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;
 
     APInt Scale;
 
+    /// True if (V * Scale) % X  produces the same result for any X.
+    bool PreservesModulo;
+
     // Context instruction to use when querying information about this index.
     const Instruction *CxtI;
 
     void dump() const {
       print(dbgs());
       dbgs() << "\n";
     }
     void print(raw_ostream &OS) const {
private:
   ///   %addr2 = gep  %alloca2, 0, (%l + 1)
   ///      alias(%p, %addr1) -> MayAlias !
   ///   store %l, ...
   SmallPtrSet<const BasicBlock *, 8> VisitedPhiBBs;
 
   /// Tracks instructions visited by pointsToConstantMemory.
   SmallPtrSet<const Value *, 16> Visited;
 
-  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 *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, bool &PreservesModulo);
 
   static DecomposedGEP
   DecomposeGEPExpression(const Value *V, const DataLayout &DL,
                          AssumptionCache *AC, DominatorTree *DT);
 
   static bool isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp,
       const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject,
       LocationSize ObjectAccessSize);

llvm/lib/Analysis/BasicAliasAnalysis.cpp

 /// 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*/ const Value *BasicAAResult::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) {
+    AssumptionCache *AC, DominatorTree *DT, bool &NSW, bool &NUW,
+    bool &PreservesModulo) {
   assert(V->getType()->isIntegerTy() && "Not an integer value");
 
   // Limit our recursion depth.
   if (Depth == 6) {
     Scale = 1;
     Offset = 0;
     return 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 we've been called recursively, then Offset and Scale will be wider
       // than 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());
 
+      bool LocalPreservesModulo = false;
       switch (BOp->getOpcode()) {
       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)) {
           Scale = 1;
           Offset = 0;
           return V;
         }
         LLVM_FALLTHROUGH;
       case Instruction::Add:
         V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
-                                SExtBits, DL, Depth + 1, AC, DT, NSW, NUW);
+                                SExtBits, DL, Depth + 1, AC, DT, NSW, NUW,
+                                PreservesModulo);
         Offset += RHS;
         break;
       case Instruction::Sub:
         V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
-                                SExtBits, DL, Depth + 1, AC, DT, NSW, NUW);
+                                SExtBits, DL, Depth + 1, AC, DT, NSW, NUW,
+                                PreservesModulo);
         Offset -= RHS;
         break;
       case Instruction::Mul:
         V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
-                                SExtBits, DL, Depth + 1, AC, DT, NSW, NUW);
+                                SExtBits, DL, Depth + 1, AC, DT, NSW, NUW,
+                                PreservesModulo);
         Offset *= RHS;
         Scale *= RHS;
+        LocalPreservesModulo = RHS.isPowerOf2();
         break;
       case Instruction::Shl:
         V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
-                                SExtBits, DL, Depth + 1, AC, DT, NSW, NUW);
+                                SExtBits, DL, Depth + 1, AC, DT, NSW, NUW,
+                                PreservesModulo);
 
         // We're trying to linearize an expression of the kind:
         //   shl i8 -128, 36
         // where the shift count exceeds the bitwidth of the type.
         // We can't decompose this further (the expression would return
         // a poison value).
         if (Offset.getBitWidth() < RHS.getLimitedValue() ||
             Scale.getBitWidth() < RHS.getLimitedValue()) {
           Scale = 1;
           Offset = 0;
           return V;
         }
 
         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;
+        // shl preserves modulo.
         return V;
       }
 
       if (isa<OverflowingBinaryOperator>(BOp)) {
         NUW &= BOp->hasNoUnsignedWrap();
         NSW &= BOp->hasNoSignedWrap();
+        LocalPreservesModulo |=
+            BOp->hasNoUnsignedWrap() && BOp->hasNoSignedWrap();
       }
+      PreservesModulo = LocalPreservesModulo;
       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) || isa<ZExtInst>(V)) {
     Value *CastOp = cast<CastInst>(V)->getOperand(0);
     unsigned NewWidth = V->getType()->getPrimitiveSizeInBits();
     unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits();
     unsigned OldZExtBits = ZExtBits, OldSExtBits = SExtBits;
     const Value *Result =
         GetLinearExpression(CastOp, Scale, Offset, ZExtBits, SExtBits, DL,
-                            Depth + 1, AC, DT, NSW, NUW);
+                            Depth + 1, AC, DT, NSW, NUW, PreservesModulo);
 
     // zext(zext(%x)) == zext(%x), and similarly 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)
 
for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
       // If the integer type is smaller than the pointer size, it is implicitly
       // sign extended to pointer size.
       unsigned Width = Index->getType()->getIntegerBitWidth();
       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);
-      bool NSW = true, NUW = true;
+      bool NSW = true, NUW = true, PreservesModulo = true;
       const Value *OrigIndex = Index;
       Index = GetLinearExpression(Index, IndexScale, IndexOffset, ZExtBits,
-                                  SExtBits, DL, 0, AC, DT, NSW, NUW);
+                                  SExtBits, DL, 0, AC, DT, NSW, NUW,
+                                  PreservesModulo);
 
       // 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.
 
       // It can be the case that, even through C1*V+C2 does not overflow for
       // relevant values of V, (C2*Scale) can overflow. In that case, we cannot
       // decompose the expression in this way.
       //
for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
         }
       }
 
       // Make sure that we have a scale that makes sense for this target's
       // pointer size.
       Scale = adjustToPointerSize(Scale, PointerSize);
 
       if (!!Scale) {
-        VariableGEPIndex Entry = {Index, ZExtBits, SExtBits, Scale, CxtI};
+        VariableGEPIndex Entry = {Index, ZExtBits,        SExtBits,
+                                  Scale, PreservesModulo, CxtI};
         Decomposed.VarIndices.push_back(Entry);
       }
     }
 
     // Take care of wrap-arounds
     if (GepHasConstantOffset)
       Decomposed.Offset = adjustToPointerSize(Decomposed.Offset, PointerSize);
 
AliasResult BasicAAResult::aliasGEP(
   }
 
   if (!DecompGEP1.VarIndices.empty()) {
     APInt GCD;
     bool AllNonNegative = DecompGEP1.Offset.isNonNegative();
     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());
 
       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:
for (unsigned i = 0, e = Src.size(); i != e; ++i) {
     // than a few variable indexes.
     for (unsigned j = 0, e = Dest.size(); j != e; ++j) {
       if (!isValueEqualInPotentialCycles(Dest[j].V, V) ||
           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)
+      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;
     }
 
     // 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].PreservesModulo, Src[i].CxtI};
       Dest.push_back(Entry);
     }
   }
 }
 
 bool BasicAAResult::constantOffsetHeuristic(
     const SmallVectorImpl<VariableGEPIndex> &VarIndices,
     LocationSize MaybeV1Size, LocationSize MaybeV2Size, const APInt &BaseOffset,
bool BasicAAResult::constantOffsetHeuristic(
   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;
+  bool NSW = true, NUW = true, PreservesModulo = 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);
+  const Value *V0 =
+      GetLinearExpression(Var0.V, V0Scale, V0Offset, V0ZExtBits, V0SExtBits, DL,
+                          0, AC, DT, NSW, NUW, PreservesModulo);
   NSW = true;
   NUW = true;
-  const Value *V1 = GetLinearExpression(Var1.V, V1Scale, V1Offset, V1ZExtBits,
-                                        V1SExtBits, DL, 0, AC, DT, NSW, NUW);
+  PreservesModulo = true;
+  const Value *V1 =
+      GetLinearExpression(Var1.V, V1Scale, V1Offset, V1ZExtBits, V1SExtBits, DL,
+                          0, AC, DT, NSW, NUW, PreservesModulo);
 
   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

llvm/test/Analysis/BasicAA/gep-alias.ll

define i32 @test8(i32* %p, i16 %i) {
   %z = sub i32 %x, %y
   ret i32 %z
 ; CHECK-LABEL: @test8(
 ; CHECK: ret i32 0
 }
 
 define i8 @test9([4 x i8] *%P, i32 %i, i32 %j) {
   %i2 = shl i32 %i, 2
-  %i3 = add i32 %i2, 1
+  %i3 = add nuw nsw i32 %i2, 1
   ; P2 = P + 1 + 4*i
   %P2 = getelementptr [4 x i8], [4 x i8] *%P, i32 0, i32 %i3
 
   %j2 = shl i32 %j, 2
 
   ; P4 = P + 4*j
   %P4 = getelementptr [4 x i8], [4 x i8]* %P, i32 0, i32 %j2
 

llvm/test/Analysis/BasicAA/gep-modulo.ll

 ; RUN: opt -basic-aa -aa-eval -print-all-alias-modref-info %s 2>&1 | FileCheck %s
 
 target datalayout = "p:64:64:64"
 
 ; %gep.idx and %gep.6 must-alias if %mul overflows (e.g. %idx == 52).
 define void @may_overflow_mul_add_i8([16 x i8]* %ptr, i8 %idx) {
 ; CHECK-LABEL: Function: may_overflow_mul_add_i8: 3 pointers, 0 call sites
 ; CHECK-NEXT:    MayAlias:  [16 x i8]* %ptr, i8* %gep.idx
 ; CHECK-NEXT:    PartialAlias: [16 x i8]* %ptr, i8* %gep.6
-; CHECK-NEXT:    NoAlias:  i8* %gep.6, i8* %gep.idx
+; CHECK-NEXT:    MayAlias:  i8* %gep.6, i8* %gep.idx
 ;
   %mul = mul i8 %idx, 5
   %add = add i8 %mul, 2
   %gep.idx = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i8 %add
   store i8 0, i8* %gep.idx, align 1
   %gep.6 = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i32 6
   store i8 1, i8* %gep.6, align 1
   ret void
;
   ret void
 }
 
 ; %gep.idx and %gep.3 must-alias if %mul overflows (e.g. %idx == 52).
 define void @may_overflow_mul_sub_i8([16 x i8]* %ptr, i8 %idx) {
 ; CHECK-LABEL: Function: may_overflow_mul_sub_i8: 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 i8 %idx, 5
   %sub = sub i8 %mul, 1
   %gep.idx = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i8 %sub
   store i8 0, i8* %gep.idx, align 1
   %gep.3 = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i32 3
   store i8 1, i8* %gep.3, align 1
   ret void

 }
 
 ; %gep.idx and %gep.3 must-alias if %mul overflows
 ; (e.g. %idx == 3689348814741910323).
 define void @may_overflow_mul_sub_i64([16 x i8]* %ptr, i64 %idx) {
 ; 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
   %gep.idx = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 %sub
   store i8 0, i8* %gep.idx, align 1
   %gep.3 = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 3
   store i8 1, i8* %gep.3, align 1
   ret void
 }
 
 ; %gep.idx and %gep.3 must-alias if %mul overflows (e.g. %idx == 110).
 define void @may_overflow_i32_sext([16 x i8]* %ptr, i32 %idx) {
 ; CHECK-LABEL: Function: may_overflow_i32_sext: 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:    MayAlias:  i8* %gep.3, i8* %gep.idx
 ;
   %mul = mul i32 %idx, 678152731
   %sub = sub i32 %mul, 1582356375