[BasicAA] Handle known bits as ranges

[nikic]

Summary

BasicAA currently tries to determine that the offset is positive by checking whether all variable indices are positive based on known bits, multiplied by a positive scale. However, this is incorrect if the scale multiplication might overflow. In the modified test case the original value is positive, but may be negative after a left shift.

Fix this by converting known bits into a constant range and reusing the range-based logic, which handles overflow correctly.

[courbet]

Nice to see all these special cases converging.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

APInt evaluateWith(APInt N) const {
     assert(N.getBitWidth() == V->getType()->getPrimitiveSizeInBits() &&
            "Incompatible bit width");
     if (TruncBits) N = N.trunc(N.getBitWidth() - TruncBits);
     if (SExtBits) N = N.sext(N.getBitWidth() + SExtBits);
     if (ZExtBits) N = N.zext(N.getBitWidth() + ZExtBits);
     return N;
   }
 
-  KnownBits evaluateWith(KnownBits N) const {
-    assert(N.getBitWidth() == V->getType()->getPrimitiveSizeInBits() &&
-           "Incompatible bit width");
-    if (TruncBits) N = N.trunc(N.getBitWidth() - TruncBits);
-    if (SExtBits) N = N.sext(N.getBitWidth() + SExtBits);
-    if (ZExtBits) N = N.zext(N.getBitWidth() + ZExtBits);
-    return N;
-  }
-
   ConstantRange evaluateWith(ConstantRange N) const {
     assert(N.getBitWidth() == V->getType()->getPrimitiveSizeInBits() &&
            "Incompatible bit width");
     if (TruncBits) N = N.truncate(N.getBitWidth() - TruncBits);
     if (SExtBits) N = N.signExtend(N.getBitWidth() + SExtBits);
     if (ZExtBits) N = N.zeroExtend(N.getBitWidth() + ZExtBits);
     return N;
   }
if (VLeftSize.hasValue()) {
         return AR;
       }
       return AliasResult::NoAlias;
     }
   }
 
   if (!DecompGEP1.VarIndices.empty()) {
     APInt GCD;
-    bool AllNonNegative = DecompGEP1.Offset.isNonNegative();
-    bool AllNonPositive = DecompGEP1.Offset.isNonPositive();
     ConstantRange OffsetRange = ConstantRange(DecompGEP1.Offset);
     for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) {
       const VariableGEPIndex &Index = DecompGEP1.VarIndices[i];
       const APInt &Scale = Index.Scale;
       APInt ScaleForGCD = Scale;
       if (!Index.IsNSW)
         ScaleForGCD = APInt::getOneBitSet(Scale.getBitWidth(),
                                           Scale.countTrailingZeros());
 
       if (i == 0)
         GCD = ScaleForGCD.abs();
       else
         GCD = APIntOps::GreatestCommonDivisor(GCD, ScaleForGCD.abs());
 
-      if (AllNonNegative || AllNonPositive) {
-        KnownBits Known = Index.Val.evaluateWith(
-            computeKnownBits(Index.Val.V, DL, 0, &AC, Index.CxtI, DT));
-        bool SignKnownZero = Known.isNonNegative();
-        bool SignKnownOne = Known.isNegative();
-        AllNonNegative &= (SignKnownZero && Scale.isNonNegative()) ||
-                          (SignKnownOne && Scale.isNonPositive());
-        AllNonPositive &= (SignKnownZero && Scale.isNonPositive()) ||
-                          (SignKnownOne && Scale.isNonNegative());
-      }
+      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);
 
       assert(OffsetRange.getBitWidth() == Scale.getBitWidth() &&
              "Bit widths are normalized to MaxPointerSize");
-      OffsetRange = OffsetRange.add(Index.Val
-                            .evaluateWith(computeConstantRange(
-                                Index.Val.V, true, &AC, Index.CxtI))
-                            .sextOrTrunc(OffsetRange.getBitWidth())
+      OffsetRange = OffsetRange.add(
+          Index.Val.evaluateWith(CR).sextOrTrunc(OffsetRange.getBitWidth())
                                     .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.
     APInt ModOffset = DecompGEP1.Offset.srem(GCD);
     if (ModOffset.isNegative())
       ModOffset += GCD; // We want mod, not rem.
     if (V1Size.hasValue() && V2Size.hasValue() &&
         ModOffset.uge(V2Size.getValue()) &&
         (GCD - ModOffset).uge(V1Size.getValue()))
       return AliasResult::NoAlias;
 
-    // If we know all the variables are non-negative, then the total offset is
-    // also non-negative and >= DecompGEP1.Offset. We have the following layout:
-    // [0, V2Size) ... [TotalOffset, TotalOffer+V1Size]
-    // If DecompGEP1.Offset >= V2Size, the accesses don't alias.
-    if (AllNonNegative && V2Size.hasValue() &&
-        DecompGEP1.Offset.uge(V2Size.getValue()))
-      return AliasResult::NoAlias;
-    // Similarly, if the variables are non-positive, then the total offset is
-    // also non-positive and <= DecompGEP1.Offset. We have the following layout:
-    // [TotalOffset, TotalOffset+V1Size) ... [0, V2Size)
-    // If -DecompGEP1.Offset >= V1Size, the accesses don't alias.
-    if (AllNonPositive && V1Size.hasValue() &&
-        (-DecompGEP1.Offset).uge(V1Size.getValue()))
-      return AliasResult::NoAlias;
-
     if (V1Size.hasValue() && V2Size.hasValue()) {
       // Compute ranges of potentially accessed bytes for both accesses. If the
       // interseciton is empty, there can be no overlap.
       unsigned BW = OffsetRange.getBitWidth();
       ConstantRange Range1 = OffsetRange.add(
           ConstantRange(APInt(BW, 0), APInt(BW, V1Size.getValue())));
       ConstantRange Range2 =
           ConstantRange(APInt(BW, 0), APInt(BW, V2Size.getValue()));

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

;
   call void @barrier()
   %c.cmp = icmp sgt i32 %c, -1
   call void @llvm.assume(i1 %c.cmp)
   %c.off = add nuw nsw i32 %c, 1
   %gep2 = getelementptr [0 x i8], [0 x i8]* %ptr, i32 %a, i32 %c.off
   ret void
 }
 
-; TODO: %ptr.neg and %ptr.shl may alias, as the shl renders the previously
+; %ptr.neg and %ptr.shl may alias, as the shl renders the previously
 ; non-negative value potentially negative.
 define void @shl_of_non_negative(i8* %ptr, i64 %a) {
 ; CHECK-LABEL: Function: shl_of_non_negative
 ; CHECK: NoAlias: i8* %ptr.a, i8* %ptr.neg
-; CHECK: NoAlias: i8* %ptr.neg, i8* %ptr.shl
+; CHECK: MayAlias: 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 i64 %a, 1
   %ptr.shl = getelementptr i8, i8* %ptr, i64 %shl
   ret void
 }
 
 declare void @llvm.assume(i1 %cond)
 declare void @barrier()