[BasicAA] Generalize base offset modulus handling

[nikic]

Summary

The GEP aliasing implementation currently has two pieces of code that solve two different subsets of the same basic problem: If you have GEPs with offsets 4*x + 0 and 4*y + 1 (assuming access size 1), then they do not alias regardless of whether x and y are the same.

One implementation is in aliasSameBasePointerGEPs(), which looks at this in a limited structural way. It requires both GEP base pointers to be exactly the same, then (optionally) a number of equal indexes, then an unknown index, then a non-equal index into a struct. This set of limitations works, but it's overly restrictive and hides the core property we're trying to exploit.

The second implementation is part of aliasGEP() itself and tries to find a common modulus in the scales, so it can then check that the constant offset doesn't overlap under modular arithmetic. The second implementation has the right idea of what the general problem is, but effectively only considers power of two factors in the scales (while aliasSameBasePointerGEPs also works with non-pow2 struct sizes.)

What this patch does is to adjust the aliasGEP() implementation to instead find the largest common factor in all the scales (i.e. the GCD) and use that as the modulus.

[jdoerfert]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1403

Maybe a comment above this to explain, I don't get the reasoning TBH.

Here is my idea of what is happening but it is not complete:

// X[0:N] is a vector of N+1 unknowns
GEP1 = GEP1BaseOffset + X[0:N] * GEP1.scale[0:N]
GCD = gcd(GEP1.scale[0], ..., GEP1.scale[N])
ModOffset = GEP1BaseOffset % GCD
// Every value of GEP1 looks like: GEP1 := Y * GCD + ModOffset
// and ModOffset < GCD.
Diff = GCD - ModOffset
if (ModOffset >=u V2Size  // I guess V2 fits in the size between Y * GCD and GEP1
 &&      Diff >=u V1Size  // this I don't understand.
  return NoAlias;

[nikic]

Update comment.

[nikic]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1403

Does the new comment make sense to you? We have the second access at [0..V2Size) with the remaining [V2Size..GCD) not being accessed. We don't alias if the first access fits in there, i.e. ModOffset >= V2Size and ModOffset+V1Size <= GCD.

[jdoerfert]

Yes, now I get it. I think I was also missing the "V2 has offset 0" precondition.

I like this, nice cleanup that adds more power. I think it is correct and good to go, would prefer a second opinion though.

[asbirlea]

This makes sense to me too. The additional comment was helpful with the gcd/difference condition.

[fhahn]

Unfortunately we are seeing mis-compiles caused by this patch. I don't think think the use of modulo arithmetic here is safe, unless the index computation is guaranteed to not overflow.

For the example below, this patch determines no-alias for %gep.idx and %gep.6. But if %mul overflows (e.g. %idx == 52), %add == 6 and they are must alias. (https://godbolt.org/z/bWjz86K97)

I pushed a set of test cases in bcc8d80192f1 and put up a candidate fix D99424

; %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) {
  %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
}

llvm/lib/Analysis/BasicAliasAnalysis.cpp

for (unsigned i = 1, e = GEP1->getNumIndices() - 1; i != e; ++i) {
     if (!isa<ArrayType>(GetElementPtrInst::getIndexedType(
             GEP1->getSourceElementType(), IntermediateIndices)))
       return MayAlias;
     IntermediateIndices.push_back(GEP1->getOperand(i + 1));
   }
 
   auto *Ty = GetElementPtrInst::getIndexedType(
     GEP1->getSourceElementType(), IntermediateIndices);
-  StructType *LastIndexedStruct = dyn_cast<StructType>(Ty);
-
   if (isa<ArrayType>(Ty) || isa<VectorType>(Ty)) {
     // We know that:
     // - both GEPs begin indexing from the exact same pointer;
     // - the last indices in both GEPs are constants, indexing into a sequential
     //   type (array or vector);
     // - both GEPs only index through arrays prior to that.
     //
     // Because array indices greater than the number of elements are valid in
if (C1 && C2)
           KnownBits Known2 = computeKnownBits(GEP2LastIdx, DL);
           if (Known1.Zero.intersects(Known2.One) ||
               Known1.One.intersects(Known2.Zero))
             return NoAlias;
         }
       } else if (isKnownNonEqual(GEP1LastIdx, GEP2LastIdx, DL))
         return NoAlias;
     }
-    return MayAlias;
-  } else if (!LastIndexedStruct || !C1 || !C2) {
-    return MayAlias;
   }
-
-  if (C1->getValue().getActiveBits() > 64 ||
-      C2->getValue().getActiveBits() > 64)
-    return MayAlias;
-
-  // We know that:
-  // - both GEPs begin indexing from the exact same pointer;
-  // - the last indices in both GEPs are constants, indexing into a struct;
-  // - said indices are different, hence, the pointed-to fields are different;
-  // - both GEPs only index through arrays prior to that.
-  //
-  // This lets us determine that the struct that GEP1 indexes into and the
-  // struct that GEP2 indexes into must either precisely overlap or be
-  // completely disjoint.  Because they cannot partially overlap, indexing into
-  // different non-overlapping fields of the struct will never alias.
-
-  // Therefore, the only remaining thing needed to show that both GEPs can't
-  // alias is that the fields are not overlapping.
-  const StructLayout *SL = DL.getStructLayout(LastIndexedStruct);
-  const uint64_t StructSize = SL->getSizeInBytes();
-  const uint64_t V1Off = SL->getElementOffset(C1->getZExtValue());
-  const uint64_t V2Off = SL->getElementOffset(C2->getZExtValue());
-
-  auto EltsDontOverlap = [StructSize](uint64_t V1Off, uint64_t V1Size,
-                                      uint64_t V2Off, uint64_t V2Size) {
-    return V1Off < V2Off && V1Off + V1Size <= V2Off &&
-           ((V2Off + V2Size <= StructSize) ||
-            (V2Off + V2Size - StructSize <= V1Off));
-  };
-
-  if (EltsDontOverlap(V1Off, V1Size, V2Off, V2Size) ||
-      EltsDontOverlap(V2Off, V2Size, V1Off, V1Size))
-    return NoAlias;
-
   return MayAlias;
 }
 
 // If a we have (a) a GEP and (b) a pointer based on an alloca, and the
 // beginning of the object the GEP points would have a negative offset with
 // repsect to the alloca, that means the GEP can not alias pointer (b).
 // Note that the pointer based on the alloca may not be a GEP. For
 // example, it may be the alloca itself.
if (GEP1BaseOffset.sge(0)) {
         if ((-GEP1BaseOffset).ult(V1Size.getValue()))
           return PartialAlias;
         return NoAlias;
       }
     }
   }
 
   if (!DecompGEP1.VarIndices.empty()) {
-    APInt Modulo(MaxPointerSize, 0);
+    APInt GCD;
     bool AllPositive = true;
     for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) {
-
-      // Try to distinguish something like &A[i][1] against &A[42][0].
-      // Grab the least significant bit set in any of the scales. We
-      // don't need std::abs here (even if the scale's negative) as we'll
-      // be ^'ing Modulo with itself later.
-      Modulo |= DecompGEP1.VarIndices[i].Scale;
+      const APInt &Scale = DecompGEP1.VarIndices[i].Scale;
+      if (i == 0)
+        GCD = Scale.abs();
+      else
+        GCD = APIntOps::GreatestCommonDivisor(GCD, Scale.abs());
 
       if (AllPositive) {
         // 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:
         const Value *V = DecompGEP1.VarIndices[i].V;
 
         KnownBits Known =
             computeKnownBits(V, DL, 0, &AC, dyn_cast<Instruction>(GEP1), DT);
         bool SignKnownZero = Known.isNonNegative();
         bool SignKnownOne = Known.isNegative();
 
         // Zero-extension widens the variable, and so forces the sign
         // bit to zero.
         bool IsZExt = DecompGEP1.VarIndices[i].ZExtBits > 0 || isa<ZExtInst>(V);
         SignKnownZero |= IsZExt;
         SignKnownOne &= !IsZExt;
 
         // If the variable begins with a zero then we know it's
         // positive, regardless of whether the value is signed or
         // unsigned.
-        APInt Scale = DecompGEP1.VarIndices[i].Scale;
         AllPositive =
             (SignKnownZero && Scale.sge(0)) || (SignKnownOne && Scale.slt(0));
       }
     }
 
-    Modulo = Modulo ^ (Modulo & (Modulo - 1));
-
-    // We can compute the difference between the two addresses
-    // mod Modulo. Check whether that difference guarantees that the
-    // two locations do not alias.
-    APInt ModOffset = GEP1BaseOffset & (Modulo - 1);
+    // We now have accesses at two offsets from the same base:
+    //  1. (...)*GCD + GEP1BaseOffset 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 = GEP1BaseOffset.srem(GCD);
+    if (ModOffset.isNegative())
+      ModOffset += GCD; // We want mod, not rem.
     if (V1Size != LocationSize::unknown() &&
         V2Size != LocationSize::unknown() && ModOffset.uge(V2Size.getValue()) &&
-        (Modulo - ModOffset).uge(V1Size.getValue()))
+        (GCD - ModOffset).uge(V1Size.getValue()))
       return NoAlias;
 
     // If we know all the variables are positive, then GEP1 >= GEP1BasePtr.
     // If GEP1BasePtr > V2 (GEP1BaseOffset > 0) then we know the pointers
     // don't alias if V2Size can fit in the gap between V2 and GEP1BasePtr.
     if (AllPositive && GEP1BaseOffset.sgt(0) &&
         V2Size != LocationSize::unknown() &&
         GEP1BaseOffset.uge(V2Size.getValue()))
       return NoAlias;

llvm/test/Analysis/BasicAA/struct-geps.ll

 }
 
 ; CHECK-LABEL: test_same_underlying_object_same_indices
 
 ; CHECK-DAG: NoAlias: i32* %x, i32* %x2
 ; CHECK-DAG: NoAlias: i32* %y, i32* %y2
 ; CHECK-DAG: NoAlias: i32* %z, i32* %z2
 
-; CHECK-DAG: MayAlias: i32* %x, i32* %y2
-; CHECK-DAG: MayAlias: i32* %x, i32* %z2
+; CHECK-DAG: NoAlias: i32* %x, i32* %y2
+; CHECK-DAG: NoAlias: i32* %x, i32* %z2
 
-; CHECK-DAG: MayAlias: i32* %x2, i32* %y
-; CHECK-DAG: MayAlias: i32* %y, i32* %z2
+; CHECK-DAG: NoAlias: i32* %x2, i32* %y
+; CHECK-DAG: NoAlias: i32* %y, i32* %z2
 
-; CHECK-DAG: MayAlias: i32* %x2, i32* %z
-; CHECK-DAG: MayAlias: i32* %y2, i32* %z
+; CHECK-DAG: NoAlias: i32* %x2, i32* %z
+; CHECK-DAG: NoAlias: i32* %y2, i32* %z
 
 define void @test_same_underlying_object_same_indices(%struct* %st, i64 %i, i64 %j, i64 %k) {
   %st2 = getelementptr %struct, %struct* %st, i32 10
   %x2 = getelementptr %struct, %struct* %st2, i64 %i, i32 0
   %y2 = getelementptr %struct, %struct* %st2, i64 %j, i32 1
   %z2 = getelementptr %struct, %struct* %st2, i64 %k, i32 2
   %x = getelementptr %struct, %struct* %st, i64 %i, i32 0
   %y = getelementptr %struct, %struct* %st, i64 %j, i32 1
   %z = getelementptr %struct, %struct* %st, i64 %k, i32 2
   ret void
 }
 
 ; CHECK-LABEL: test_same_underlying_object_different_indices
 
 ; CHECK-DAG: MayAlias: i32* %x, i32* %x2
 ; CHECK-DAG: MayAlias: i32* %y, i32* %y2
 ; CHECK-DAG: MayAlias: i32* %z, i32* %z2
 
-; CHECK-DAG: MayAlias: i32* %x, i32* %y2
-; CHECK-DAG: MayAlias: i32* %x, i32* %z2
+; CHECK-DAG: NoAlias: i32* %x, i32* %y2
+; CHECK-DAG: NoAlias: i32* %x, i32* %z2
 
-; CHECK-DAG: MayAlias: i32* %x2, i32* %y
-; CHECK-DAG: MayAlias: i32* %y, i32* %z2
+; CHECK-DAG: NoAlias: i32* %x2, i32* %y
+; CHECK-DAG: NoAlias: i32* %y, i32* %z2
 
-; CHECK-DAG: MayAlias: i32* %x2, i32* %z
-; CHECK-DAG: MayAlias: i32* %y2, i32* %z
+; CHECK-DAG: NoAlias: i32* %x2, i32* %z
+; CHECK-DAG: NoAlias: i32* %y2, i32* %z
 
 define void @test_same_underlying_object_different_indices(%struct* %st, i64 %i1, i64 %j1, i64 %k1, i64 %i2, i64 %k2, i64 %j2) {
   %st2 = getelementptr %struct, %struct* %st, i32 10
   %x2 = getelementptr %struct, %struct* %st2, i64 %i2, i32 0
   %y2 = getelementptr %struct, %struct* %st2, i64 %j2, i32 1
   %z2 = getelementptr %struct, %struct* %st2, i64 %k2, i32 2
   %x = getelementptr %struct, %struct* %st, i64 %i1, i32 0
   %y = getelementptr %struct, %struct* %st, i64 %j1, i32 1