[BasicAA] Fix nsw handling for negated scales (PR63266)

[nikic]

Summary

We currently preserve the nsw flag when negating scales, which is incorrect for INT_MIN.

However, just dropping the NSW flag in this case makes BasicAA behavior unreliable and asymmetric, because we may or may not drop the NSW flag depending on which side gets subtracted.

Instead, leave the Scale alone and add an additional IsNegated flag, which indicates that the who VarIndex should be interpreted as a subtraction. This allows us to retain the NSW flag.

When accumulating the offset range, we need to use subtraction instead of adding for IsNegated indices. Everything else works on the absolute value of the scale, so the negation does not matter there.

Fixes https://github.com/llvm/llvm-project/issues/63266.

[nikic]

Ping

[fhahn]

LGTM, thanks!

llvm/lib/Analysis/BasicAliasAnalysis.cpp

struct VariableGEPIndex {
   APInt Scale;
 
   // Context instruction to use when querying information about this index.
   const Instruction *CxtI;
 
   /// True if all operations in this expression are NSW.
   bool IsNSW;
 
+  /// True if the index should be subtracted rather than added. We don't simply
+  /// negate the Scale, to avoid losing the NSW flag: X - INT_MIN*1 may be
+  /// non-wrapping, while X + INT_MIN*(-1) wraps.
+  bool IsNegated;
+
+  bool hasNegatedScaleOf(const VariableGEPIndex &Other) const {
+    if (IsNegated == Other.IsNegated)
+      return Scale == -Other.Scale;
+    return Scale == Other.Scale;
+  }
+
   void dump() const {
     print(dbgs());
     dbgs() << "\n";
   }
   void print(raw_ostream &OS) const {
     OS << "(V=" << Val.V->getName()
        << ", zextbits=" << Val.ZExtBits
        << ", sextbits=" << Val.SExtBits
        << ", truncbits=" << Val.TruncBits
-       << ", scale=" << Scale << ")";
+       << ", scale=" << Scale
+       << ", nsw=" << IsNSW
+       << ", negated=" << IsNegated << ")";
   }
 };
 }
 
 // Represents the internal structure of a GEP, decomposed into a base pointer,
 // constant offsets, and variable scaled indices.
 struct BasicAAResult::DecomposedGEP {
   // Base pointer of the GEP
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
       // index size.
       Scale = adjustToIndexSize(Scale, IndexSize);
 
       if (!!Scale) {
-        VariableGEPIndex Entry = {LE.Val, Scale, CxtI, LE.IsNSW};
+        VariableGEPIndex Entry = {LE.Val, Scale, CxtI, LE.IsNSW,
+                                  /* IsNegated */ false};
         Decomposed.VarIndices.push_back(Entry);
       }
     }
 
     // Take care of wrap-arounds
     if (GepHasConstantOffset)
       Decomposed.Offset = adjustToIndexSize(Decomposed.Offset, IndexSize);
 
for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) {
     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 MaxIndexSize");
     if (Index.IsNSW)
-      OffsetRange = OffsetRange.add(CR.smul_sat(ConstantRange(Scale)));
+      CR = CR.smul_sat(ConstantRange(Scale));
+    else
+      CR = CR.smul_fast(ConstantRange(Scale));
+
+    if (Index.IsNegated)
+      OffsetRange = OffsetRange.sub(CR);
     else
-      OffsetRange = OffsetRange.add(CR.smul_fast(ConstantRange(Scale)));
+      OffsetRange = OffsetRange.add(CR);
   }
 
   // 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.
if (DecompGEP1.VarIndices.size() == 1) {
     }
   } else if (DecompGEP1.VarIndices.size() == 2) {
     // VarIndex = Scale*V0 + (-Scale)*V1.
     // If V0 != V1 then abs(VarIndex) >= abs(Scale).
     // Check that MayBeCrossIteration is false, to avoid reasoning about
     // inequality of values across loop iterations.
     const VariableGEPIndex &Var0 = DecompGEP1.VarIndices[0];
     const VariableGEPIndex &Var1 = DecompGEP1.VarIndices[1];
-    if (Var0.Scale == -Var1.Scale && Var0.Val.TruncBits == 0 &&
+    if (Var0.hasNegatedScaleOf(Var1) && Var0.Val.TruncBits == 0 &&
         Var0.Val.hasSameCastsAs(Var1.Val) && !AAQI.MayBeCrossIteration &&
         isKnownNonEqual(Var0.Val.V, Var1.Val.V, DL, &AC, /* CxtI */ nullptr,
                         DT))
       MinAbsVarIndex = Var0.Scale.abs();
   }
 
   if (MinAbsVarIndex) {
     // The constant offset will have added at least +/-MinAbsVarIndex to it.
for (const VariableGEPIndex &Src : SrcGEP.VarIndices) {
     // than a few variable indexes.
     bool Found = false;
     for (auto I : enumerate(DestGEP.VarIndices)) {
       VariableGEPIndex &Dest = I.value();
       if (!isValueEqualInPotentialCycles(Dest.Val.V, Src.Val.V, AAQI) ||
           !Dest.Val.hasSameCastsAs(Src.Val))
         continue;
 
+      // Normalize IsNegated if we're going to lose the NSW flag anyway.
+      if (Dest.IsNegated) {
+        Dest.Scale = -Dest.Scale;
+        Dest.IsNegated = false;
+        Dest.IsNSW = false;
+      }
+
       // If we found it, subtract off Scale V's from the entry in Dest.  If it
       // goes to zero, remove the entry.
       if (Dest.Scale != Src.Scale) {
         Dest.Scale -= Src.Scale;
         Dest.IsNSW = false;
       } else {
         DestGEP.VarIndices.erase(DestGEP.VarIndices.begin() + I.index());
       }
       Found = true;
       break;
     }
 
     // If we didn't consume this entry, add it to the end of the Dest list.
     if (!Found) {
-      VariableGEPIndex Entry = {Src.Val, -Src.Scale, Src.CxtI, Src.IsNSW};
+      VariableGEPIndex Entry = {Src.Val, Src.Scale, Src.CxtI, Src.IsNSW,
+                                /* IsNegated */ true};
       DestGEP.VarIndices.push_back(Entry);
     }
   }
 }
 
 bool BasicAAResult::constantOffsetHeuristic(const DecomposedGEP &GEP,
                                             LocationSize MaybeV1Size,
                                             LocationSize MaybeV2Size,
                                             AssumptionCache *AC,
                                             DominatorTree *DT,
                                             const AAQueryInfo &AAQI) {
   if (GEP.VarIndices.size() != 2 || !MaybeV1Size.hasValue() ||
       !MaybeV2Size.hasValue())
     return false;
 
   const uint64_t V1Size = MaybeV1Size.getValue();
   const uint64_t V2Size = MaybeV2Size.getValue();
 
   const VariableGEPIndex &Var0 = GEP.VarIndices[0], &Var1 = GEP.VarIndices[1];
 
   if (Var0.Val.TruncBits != 0 || !Var0.Val.hasSameCastsAs(Var1.Val) ||
-      Var0.Scale != -Var1.Scale ||
+      !Var0.hasNegatedScaleOf(Var1) ||
       Var0.Val.V->getType() != Var1.Val.V->getType())
     return false;
 
   // 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.
 
   LinearExpression E0 =

llvm/test/Analysis/BasicAA/range.ll

define void @benign_overflow(ptr %p, i64 %o) {
   %p.o.1 = getelementptr i8, ptr %p.o, i64 1
   load i8, ptr %p
   load i8, ptr %p.neg1
   load i8, ptr %p.o
   load i8, ptr %p.o.1
   ret void
 }
 
-; FIXME: This is a miscompile
 ; CHECK-LABEL: pr63266
-; CHECK: NoAlias: i8* %gep2, i8* %offset16
+; CHECK: MayAlias:  i8* %gep2, i8* %offset16
 define void @pr63266(i1 %c, ptr %base) {
 entry:
   %offset16 = getelementptr inbounds i8, ptr %base, i64 16
   %gep1 = getelementptr i8, ptr %base, i64 -9223372036854775792
   br i1 %c, label %if, label %join
 
 if:
   br label %join