[BasicAA] Use saturating multiply on range if nsw

[nikic]

Summary

If we know that the var * scale multiplication is nsw, we can use a saturating multiplication on the range (as a good approximation of an nsw multiply). This recovers some cases where the fix from D112611 is unnecessarily strict. (This can be further strengthened by using a saturating add, but we currently don't track all the necessary information for that.)

This exposes an issue in our NSW tracking for multiplies. The code was assuming that (X +nsw Y) *nsw Z results in (X *nsw Z) +nsw (Y *nsw Z) -- however, it is possible that the distributed multiplications overflow, even if the non-distributed one does not. We should discard the nsw flag if the the offset is non-zero. If we just have (X *nsw Y) *nsw Z then concluding X *nsw (Y *nsw Z) is fine. I'm happy to land this part separately -- I've bundled these because I don't think it's possible to actually cause a miscompile otherwise, due to the specific way the NSW flag was previously used.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

struct LinearExpression {
 
   LinearExpression(const CastedValue &Val) : Val(Val), IsNSW(true) {
     unsigned BitWidth = Val.getBitWidth();
     Scale = APInt(BitWidth, 1);
     Offset = APInt(BitWidth, 0);
   }
 
   LinearExpression mul(const APInt &Other, bool MulIsNSW) const {
-    return LinearExpression(Val, Scale * Other, Offset * Other,
-                            IsNSW && (Other.isOne() || MulIsNSW));
+    // The check for zero offset is necessary, because generally
+    // (X +nsw Y) *nsw Z does not imply (X *nsw Z) +nsw (Y *nsw Z).
+    bool NSW = IsNSW && (Other.isOne() || (MulIsNSW && Offset.isZero()));
+    return LinearExpression(Val, Scale * Other, Offset * Other, NSW);
   }
 };
 }
 
 /// Analyzes the specified value as a linear expression: "A*V + B", where A and
 /// B are constant integers.
 static LinearExpression GetLinearExpression(
     const CastedValue &Val,  const DataLayout &DL, unsigned Depth,
for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) {
 
       ConstantRange CR =
           computeConstantRange(Index.Val.V, true, &AC, Index.CxtI);
       KnownBits Known =
           computeKnownBits(Index.Val.V, DL, 0, &AC, Index.CxtI, DT);
       CR = CR.intersectWith(
           ConstantRange::fromKnownBits(Known, /* Signed */ true),
           ConstantRange::Signed);
+      CR = Index.Val.evaluateWith(CR).sextOrTrunc(OffsetRange.getBitWidth());
 
       assert(OffsetRange.getBitWidth() == Scale.getBitWidth() &&
              "Bit widths are normalized to MaxPointerSize");
-      OffsetRange = OffsetRange.add(
-          Index.Val.evaluateWith(CR).sextOrTrunc(OffsetRange.getBitWidth())
-                                    .smul_fast(ConstantRange(Scale)));
+      if (Index.IsNSW)
+        OffsetRange = OffsetRange.add(CR.smul_sat(ConstantRange(Scale)));
+      else
+        OffsetRange = OffsetRange.add(CR.smul_fast(ConstantRange(Scale)));
     }
 
     // We now have accesses at two offsets from the same base:
     //  1. (...)*GCD + DecompGEP1.Offset with size V1Size
     //  2. 0 with size V2Size
     // Using arithmetic modulo GCD, the accesses are at
     // [ModOffset..ModOffset+V1Size) and [0..V2Size). If the first access fits
     // into the range [V2Size..GCD), then we know they cannot overlap.

llvm/test/Analysis/BasicAA/assume-index-positive.ll

; CHECK: MayAlias: i8* %ptr.neg, i8* %ptr.shl
   call void @llvm.assume(i1 %a.cmp)
   %ptr.neg = getelementptr i8, i8* %ptr, i64 -2
   %ptr.a = getelementptr i8, i8* %ptr, i64 %a
   %shl = shl i64 %a, 1
   %ptr.shl = getelementptr i8, i8* %ptr, i64 %shl
   ret void
 }
 
-; TODO: Unlike the previous case, %ptr.neg and %ptr.shl can't alias, because
+; Unlike the previous case, %ptr.neg and %ptr.shl can't alias, because
 ; shl nsw of non-negative is non-negative.
 define void @shl_nsw_of_non_negative(i8* %ptr, i64 %a) {
 ; CHECK-LABEL: Function: shl_nsw_of_non_negative
 ; CHECK: NoAlias: i8* %ptr.a, i8* %ptr.neg
-; CHECK: MayAlias: i8* %ptr.neg, i8* %ptr.shl
+; CHECK: NoAlias: i8* %ptr.neg, i8* %ptr.shl
   %a.cmp = icmp sge i64 %a, 0
   call void @llvm.assume(i1 %a.cmp)
   %ptr.neg = getelementptr i8, i8* %ptr, i64 -2
   %ptr.a = getelementptr i8, i8* %ptr, i64 %a
   %shl = shl nsw i64 %a, 1
   %ptr.shl = getelementptr i8, i8* %ptr, i64 %shl
   ret void
 }
 
 declare void @llvm.assume(i1 %cond)
 declare void @barrier()