[BasicAA] Model implicit trunc of GEP indices

[nikic]

Summary

GEP indices larger than the GEP index size are implicitly truncated to the index size. BasicAA currently doesn't model this, resulting in incorrect alias analysis results.

Fix this by explicitly modelling truncation in CastedValue in the same way we do zext and sext. Additionally we need to disable a number of optimizations for truncated values, in particular "non-zero" and "non-equal" may no longer hold after truncation. I believe the constant offset heuristic is also not necessarily correct for truncated values, but wasn't able to come up with a test for that one.

A possible followup here would be to use the new mechanism to model explicit trunc as well (which should be much more common, as it is the canonical form). This is straightforward, but omitted here to separate the correctness fix from the analysis improvement.

(Side note: While I say "index size" above, BasicAA currently uses the pointer size instead. Something for another day...)

[nikic]

Rebase

[nikic]

Rebase & ping

[reames]

Quick scan only. I don't have a lot of context on this code.

Approach wise, it would seem lower risk to model explicit truncates before adding the implicit trunc on gep operands. (i.e. easier to write test cases, less likelihood of wide spread miscompiles if we got it slightly wrong, less interaction w/e.g. "pointer size" piece) Can I ask why you approached it this was instead?

llvm/lib/Analysis/BasicAliasAnalysis.cpp

268

Naming wise, "Extended" no longer seems correct. Can you change this to something like CastedValue? (In a separate NFC is encouraged.)

292

I don't believe this is correct. What if we trunced off non-zero bits and are no zero extending?

[nikic]

In D110977#3067292, @reames wrote:

Quick scan only. I don't have a lot of context on this code.

Approach wise, it would seem lower risk to model explicit truncates before adding the implicit trunc on gep operands. (i.e. easier to write test cases, less likelihood of wide spread miscompiles if we got it slightly wrong, less interaction w/e.g. "pointer size" piece) Can I ask why you approached it this was instead?

We already model explicit truncs correctly, simply by dint of treating them as opaque values. I'm interested in implicit truncs here because they're currently being miscompiled.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

292

This method replaces V with zext(NewV). So we now have something like trunc(zext(NewV)). If we extend less than we truncate, then we'll be left with just a trunc(NewV) (this case). If we truncate less than we extend, we're left with just zext(NewV), which gets folded into the outer zext/sext (the existing case below).

[nikic]

Rebase over rename

[nikic]

Ping :)

[reames]

LGTM

I'm a bit hesitant to LGTM this as I'm not super familiar with the code, but since no one else seems to be reviewing it and I don't spot any obvious problems, I'm doing so. Hopefully the new code is at least "more correct" than the old code.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

void EarliestEscapeInfo::removeInstruction(Instruction *I) {
   }
 }
 
 //===----------------------------------------------------------------------===//
 // GetElementPtr Instruction Decomposition and Analysis
 //===----------------------------------------------------------------------===//
 
 namespace {
-/// Represents zext(sext(V)).
+/// Represents zext(sext(trunc(V))).
 struct CastedValue {
   const Value *V;
   unsigned ZExtBits = 0;
   unsigned SExtBits = 0;
+  unsigned TruncBits = 0;
 
   explicit CastedValue(const Value *V) : V(V) {}
-  explicit CastedValue(const Value *V, unsigned ZExtBits, unsigned SExtBits)
-      : V(V), ZExtBits(ZExtBits), SExtBits(SExtBits) {}
+  explicit CastedValue(const Value *V, unsigned ZExtBits, unsigned SExtBits,
+                       unsigned TruncBits)
+      : V(V), ZExtBits(ZExtBits), SExtBits(SExtBits), TruncBits(TruncBits) {}
 
   unsigned getBitWidth() const {
-    return V->getType()->getPrimitiveSizeInBits() + ZExtBits + SExtBits;
+    return V->getType()->getPrimitiveSizeInBits() - TruncBits + ZExtBits +
+           SExtBits;
   }
 
   CastedValue withValue(const Value *NewV) const {
-    return CastedValue(NewV, ZExtBits, SExtBits);
+    return CastedValue(NewV, ZExtBits, SExtBits, TruncBits);
   }
 
   /// Replace V with zext(NewV)
   CastedValue withZExtOfValue(const Value *NewV) const {
     unsigned ExtendBy = V->getType()->getPrimitiveSizeInBits() -
                         NewV->getType()->getPrimitiveSizeInBits();
+    if (ExtendBy <= TruncBits)
+      return CastedValue(NewV, ZExtBits, SExtBits, TruncBits - ExtendBy);
+
     // zext(sext(zext(NewV))) == zext(zext(zext(NewV)))
-    return CastedValue(NewV, ZExtBits + SExtBits + ExtendBy, 0);
+    ExtendBy -= TruncBits;
+    return CastedValue(NewV, ZExtBits + SExtBits + ExtendBy, 0, 0);
   }
 
   /// Replace V with sext(NewV)
   CastedValue withSExtOfValue(const Value *NewV) const {
     unsigned ExtendBy = V->getType()->getPrimitiveSizeInBits() -
                         NewV->getType()->getPrimitiveSizeInBits();
+    if (ExtendBy <= TruncBits)
+      return CastedValue(NewV, ZExtBits, SExtBits, TruncBits - ExtendBy);
+
     // zext(sext(sext(NewV)))
-    return CastedValue(NewV, ZExtBits, SExtBits + ExtendBy);
+    ExtendBy -= TruncBits;
+    return CastedValue(NewV, ZExtBits, SExtBits + ExtendBy, 0);
   }
 
   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;
   }
 
   bool canDistributeOver(bool NUW, bool NSW) const {
     // zext(x op<nuw> y) == zext(x) op<nuw> zext(y)
     // sext(x op<nsw> y) == sext(x) op<nsw> sext(y)
+    // trunc(x op y) == trunc(x) op trunc(y)
     return (!ZExtBits || NUW) && (!SExtBits || NSW);
   }
 
   bool hasSameCastsAs(const CastedValue &Other) const {
-    return ZExtBits == Other.ZExtBits && SExtBits == Other.SExtBits;
+    return ZExtBits == Other.ZExtBits && SExtBits == Other.SExtBits &&
+           TruncBits == Other.TruncBits;
   }
 };
 
-/// Represents zext(sext(V)) * Scale + Offset.
+/// Represents zext(sext(trunc(V))) * Scale + Offset.
 struct LinearExpression {
   CastedValue Val;
   APInt Scale;
   APInt Offset;
 
   /// True if all operations in this expression are NSW.
   bool IsNSW;
 
if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
       bool NUW = true, NSW = true;
       if (isa<OverflowingBinaryOperator>(BOp)) {
         NUW &= BOp->hasNoUnsignedWrap();
         NSW &= BOp->hasNoSignedWrap();
       }
       if (!Val.canDistributeOver(NUW, NSW))
         return Val;
 
+      // While we can distribute over trunc, we cannot preserve nowrap flags
+      // in that case.
+      if (Val.TruncBits)
+        NUW = NSW = false;
+
       LinearExpression E(Val);
       switch (BOp->getOpcode()) {
       default:
         // We don't understand this instruction, so we can't decompose it any
         // further.
         return Val;
       case Instruction::Or:
         // X|C == X+C if all the bits in C are unset in X.  Otherwise we can't

 static APInt adjustToPointerSize(const APInt &Offset, unsigned PointerSize) {
   assert(PointerSize <= Offset.getBitWidth() && "Invalid PointerSize!");
   unsigned ShiftBits = Offset.getBitWidth() - PointerSize;
   return (Offset << ShiftBits).ashr(ShiftBits);
 }
 
 namespace {
 // A linear transformation of a Value; this class represents
-// ZExt(SExt(V, SExtBits), ZExtBits) * Scale.
+// ZExt(SExt(Trunc(V, TruncBits), SExtBits), ZExtBits) * Scale.
 struct VariableGEPIndex {
   CastedValue Val;
   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;
 
   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 << ")";
   }
 };
 }
 
 // Represents the internal structure of a GEP, decomposed into a base pointer,
 // constant offsets, and variable scaled indices.
 struct BasicAAResult::DecomposedGEP {
for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
       GepHasConstantOffset = false;
 
       APInt Scale(MaxPointerSize,
                   DL.getTypeAllocSize(GTI.getIndexedType()).getFixedSize());
       // If the integer type is smaller than the pointer size, it is implicitly
       // sign extended to pointer size.
       unsigned Width = Index->getType()->getIntegerBitWidth();
       unsigned SExtBits = PointerSize > Width ? PointerSize - Width : 0;
+      unsigned TruncBits = PointerSize < Width ? Width - PointerSize : 0;
       LinearExpression LE = GetLinearExpression(
-          CastedValue(Index, 0, SExtBits), DL, 0, AC, DT);
+          CastedValue(Index, 0, SExtBits, TruncBits), DL, 0, AC, DT);
 
       // 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.
       //
       // FIXME: C1*Scale and the other operations in the decomposed
       // (C1*Scale)*V+C2*Scale can also overflow. We should check for this
       // possibility.
       bool Overflow;
       APInt ScaledOffset = LE.Offset.sextOrTrunc(MaxPointerSize)
                            .smul_ov(Scale, Overflow);
       if (Overflow) {
-        LE = LinearExpression(CastedValue(Index, 0, SExtBits));
+        LE = LinearExpression(CastedValue(Index, 0, SExtBits, TruncBits));
       } else {
         Decomposed.Offset += ScaledOffset;
         Scale *= LE.Scale.sextOrTrunc(MaxPointerSize);
       }
 
       // If we already had an occurrence of this index variable, merge this
       // scale into it.  For example, we want to handle:
       //   A[x][x] -> x*16 + x*4 -> x*20
for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) {
       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));
-        // TODO: Account for implicit trunc.
         bool SignKnownZero = Known.isNonNegative();
         bool SignKnownOne = Known.isNegative();
         AllNonNegative &= (SignKnownZero && Scale.isNonNegative()) ||
                           (SignKnownOne && Scale.isNonPositive());
         AllNonPositive &= (SignKnownZero && Scale.isNonPositive()) ||
                           (SignKnownOne && Scale.isNonNegative());
       }
     }
if (V1Size.hasValue() && V2Size.hasValue()) {
       // VarIndexRange is such that:
       //    (VarIndex <= -MinAbsVarIndex || MinAbsVarIndex <= VarIndex) &&
       //    VarIndexRange.contains(VarIndex)
       Optional<APInt> MinAbsVarIndex;
       Optional<ConstantRange> VarIndexRange;
       if (DecompGEP1.VarIndices.size() == 1) {
         // VarIndex = Scale*V.
         const VariableGEPIndex &Var = DecompGEP1.VarIndices[0];
-        if (isKnownNonZero(Var.Val.V, DL, 0, &AC, Var.CxtI, DT)) {
+        if (Var.Val.TruncBits == 0 &&
+            isKnownNonZero(Var.Val.V, DL, 0, &AC, Var.CxtI, DT)) {
           // If V != 0 then abs(VarIndex) >= abs(Scale).
           MinAbsVarIndex = Var.Scale.abs();
         }
         ConstantRange R = Var.Val.evaluateWith(
             computeConstantRange(Var.Val.V, true, &AC, Var.CxtI));
         if (!R.isFullSet() && !R.isEmptySet())
           VarIndexRange = R.sextOrTrunc(Var.Scale.getBitWidth())
                               .smul_fast(ConstantRange(Var.Scale));
       } else if (DecompGEP1.VarIndices.size() == 2) {
         // VarIndex = Scale*V0 + (-Scale)*V1.
         // If V0 != V1 then abs(VarIndex) >= abs(Scale).
         // Check that VisitedPhiBBs is empty, 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 &&
+        if (Var0.Scale == -Var1.Scale && Var0.Val.TruncBits == 0 &&
             Var0.Val.hasSameCastsAs(Var1.Val) && VisitedPhiBBs.empty() &&
             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.
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.hasSameCastsAs(Var1.Val) || Var0.Scale != -Var1.Scale ||
+  if (Var0.Val.TruncBits != 0 || !Var0.Val.hasSameCastsAs(Var1.Val) ||
+      Var0.Scale != -Var1.Scale ||
       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/gep-implicit-trunc-32-bit-pointers.ll

 ;
   %gep.1 = getelementptr i8, i8* %ptr, i64 4294967296
   store i8 0, i8* %gep.1
   %gep.2 = getelementptr i8, i8* %ptr, i64 1
   store i8 1, i8* %gep.2
   ret void
 }
 
-; FIXME: Currently we incorrectly determine NoAlias for %gep.1 and %gep.2. The
-; GEP indices get implicitly truncated to 32 bit, so multiples of 2^32
+; The GEP indices get implicitly truncated to 32 bit, so multiples of 2^32
 ; (=4294967296) will be 0.
 ; See https://alive2.llvm.org/ce/z/HHjQgb.
 define void @mustalias_overflow_in_32_bit_add_mul_gep(i8* %ptr, i64 %i) {
 ; CHECK-LABEL: Function: mustalias_overflow_in_32_bit_add_mul_gep: 3 pointers, 1 call sites
-; CHECK-NEXT:    NoAlias:  i8* %gep.1, i8* %ptr
-; CHECK-NEXT:    NoAlias:  i8* %gep.2, i8* %ptr
-; CHECK-NEXT:    NoAlias:  i8* %gep.1, i8* %gep.2
+; CHECK-NEXT:    MayAlias: i8* %gep.1, i8* %ptr
+; CHECK-NEXT:    MayAlias: i8* %gep.2, i8* %ptr
+; CHECK-NEXT:    MayAlias: i8* %gep.1, i8* %gep.2
 ;
   %s.1 = icmp sgt i64 %i, 0
   call void @llvm.assume(i1 %s.1)
 
   %mul = mul nuw nsw i64 %i, 4294967296
   %add = add nuw nsw i64 %mul, %i
   %gep.1 = getelementptr i8, i8* %ptr, i64 %add
   store i8 0, i8* %gep.1
   %gep.2 = getelementptr i8, i8* %ptr, i64 %i
   store i8 1, i8* %gep.2
   ret void
 }
 
-; FIXME: While %n is non-zero, its low 32 bits may not be.
 define void @mayalias_overflow_in_32_bit_non_zero(i8* %ptr, i64 %n) {
 ; CHECK-LABEL: Function: mayalias_overflow_in_32_bit_non_zero
-; CHECK:    NoAlias: i8* %gep, i8* %ptr
+; CHECK:    MayAlias: i8* %gep, i8* %ptr
 ;
   %c = icmp ne i64 %n, 0
   call void @llvm.assume(i1 %c)
   store i8 0, i8* %ptr
   %gep = getelementptr i8, i8* %ptr, i64 %n
   store i8 1, i8* %gep
   ret void
 }
 
-; FIXME: While %n is positive, its low 32 bits may not be.
 define void @mayalias_overflow_in_32_bit_positive(i8* %ptr, i64 %n) {
 ; CHECK-LABEL: Function: mayalias_overflow_in_32_bit_positive
 ; CHECK:    NoAlias: i8* %gep.1, i8* %ptr
-; CHECK:    NoAlias: i8* %gep.2, i8* %ptr
-; CHECK:    NoAlias: i8* %gep.1, i8* %gep.2
+; CHECK:    MayAlias: i8* %gep.2, i8* %ptr
+; CHECK:    MayAlias: i8* %gep.1, i8* %gep.2
 ;
   %c = icmp sgt i64 %n, 0
   call void @llvm.assume(i1 %c)
   %gep.1 = getelementptr i8, i8* %ptr, i64 -1
   store i8 0, i8* %gep.1
   %gep.2 = getelementptr i8, i8* %ptr, i64 %n
   store i8 1, i8* %gep.2
   ret void
 }