[BasicAA] Make alias GEP positive offset handling symmetric

[nikic]

Summary

aliasGEP() currently implements some special handling for the case where all variable offsets are positive, in which case the constant offset can be taken as the minimal offset. However, it does not perform the same handling for the all-negative case. This means that the alias-analysis result between two GEPs is asymmetric: If GEP1 - GEP2 is all-positive, then GEP2 - GEP1 is all-negative, and the first will result in NoAlias, while the second will result in MayAlias.

Apart from producing sub-optimal results for one order, this also violates our caching assumption. In particular, if BatchAA is used, the cached result depends on the order of the GEPs in the first query. This results in an inconsistency in BatchAA and AA results, which is how I noticed this issue.

[nikic]

llvm/lib/Analysis/AliasAnalysisEvaluator.cpp

177

This assertion currently fails on Analysis/BasicAA/zext.ll.

Arguably this should be asserted in AA itself, but a) I'm not confident enough that this is the only asymmetry that exists right now and b) a more general assertion would have to be behind EXPENSIVE_CHECKS, so I figured this would be a good place to verify this initially.

[jdoerfert]

llvm/lib/Analysis/AliasAnalysisEvaluator.cpp

177

Can you add the reasoning as a TODO maybe?

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1451

Copy paste error?

[nikic]

Add TODO.

[nikic]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1451

Um, where? I'm not seeing it ^

[jdoerfert]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1451

I think I was simply confused. Maybe today is not the day to finish this review (for me). I'll give it another shot tomorrow ;)

[asbirlea]

I wouldn't be surprised if there are other asymmetries, thank you for digging further here.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1451

I believe this is correct :-).

[nikic]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1451

I think @jdoerfert was right, and there is a mistake here: This should be comparing against V1Size rather than V2Size.

// Non-negative case:
0 ... V2Size ... GEP1BaseOffset ... GEP1BaseOffset+V1Size
// Non-positive case:
GEP1BaseOffset ... GEP1BaseOffset+V1Size ... 0 ... V2Size

We need to check that V1Size fits between GEP1BaseOffset and 0, the V2Size access is above zero and not relevant.

I'll have to add a test where both access sizes are different.

[asbirlea]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1451

Adding a test will be the best solution here, but here's where I went back and forth here and I ended up concluding the above is correct.

// Non-negative case:
0 ... V2 ... GEP1BasePoint
//       \____/<- V2 needs to fit here;
// All offsets are +,  and GEP1BaseOffset already had GEP2 subtracted.

// Non-positive case:
// Initializing like above: "AllNonPositive = GEP1BaseOffset.isNonPositive();", means:
GEP1BasePoint ... V2 ... 0
// All offsets are -, so it's still V2Size that needs to fit between V2 and GEP1BasePoint.

Initially I thought we need to fit V1Size, and in order to match the condition for non-negatives (and fit V2) you'd need to initialize AllNonPositive = GEP1BaseOffset.isNonNegative();
So you'd get:
V2 ... GEP1BasePoint ... 0
But the indices are negative as well.

Again, +1 on a test to clarify either way.

[nikic]

Use correct size, add test with different sizes.

[nikic]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1451

I've now added a test that asserted with the previous code. The thing to keep in mind here is that while the GEP offset is negative, the access size still points in the positive direction. So for the negative case, what we need is that access 1 fits between the negative GEP1BaseOffset and zero, because zero is where the access 2 starts.

[asbirlea]

As talked offline, this lgtm.

[uabelho]

Hello!

The following hits an assertion with this patch. If I run

opt -S -o - aa.ll -aa-eval

I get

opt: ../lib/Analysis/AliasAnalysisEvaluator.cpp:180: void llvm::AAEvaluator::runInternal(llvm::Function &, llvm::AAResults &): Assertion `AR == AA.alias(*I2, I2Size, *I1, I1Size) && "AA query not symmetric"' failed.

with aa.ll being

define void @dll(i32* %outputdata_p) {
entry:
  br label %while.body

while.body:                                       ; preds = %cond.end, %entry
  %outputdata_p.addr.042 = phi i32* [ %outputdata_p, %entry ], [ %incdec.ptr6, %cond.end ]
  br label %cond.end

cond.end:                                         ; preds = %while.body
  %incdec.ptr6 = getelementptr inbounds i32, i32* %outputdata_p.addr.042, i32 1
  br i1 undef, label %while.body, label %crit_edge44

crit_edge44:                                      ; preds = %cond.end
  %split45 = phi i32* [ %incdec.ptr6, %cond.end ]
  unreachable
}

[nikic]

@uabelho Thanks for the report! I have reverted the assert in https://github.com/llvm/llvm-project/commit/85ccdcaa502ee2c478f2d0ba2b1e217117b69032. We'll have to fix this asymmetric in phi-phi aliasing before re-enabling it.

[uabelho]

In D91383#2403369, @nikic wrote:

@uabelho Thanks for the report! I have reverted the assert in https://github.com/llvm/llvm-project/commit/85ccdcaa502ee2c478f2d0ba2b1e217117b69032. We'll have to fix this asymmetric in phi-phi aliasing before re-enabling it.

Thanks!

llvm/lib/Analysis/AliasAnalysisEvaluator.cpp

for (SetVector<Value *>::iterator I2 = Pointers.begin(); I2 != I1; ++I2) {
         PrintResults(AR, PrintPartialAlias, *I1, *I2, F.getParent());
         ++PartialAliasCount;
         break;
       case MustAlias:
         PrintResults(AR, PrintMustAlias, *I1, *I2, F.getParent());
         ++MustAliasCount;
         break;
       }
+
+      // We assume that alias(I1, I2) == alias(I2, I1) and only print one
+      // order. Make sure this assumption actually holds.
+      // TODO: We should probably assert this in AA itself under
+      // EXPENSIVE_CHECKS. This would need some more thorough verification that
+      // all AA queries are symmetric first.
+      assert(AR == AA.alias(*I2, I2Size, *I1, I1Size) &&
+             "AA query not symmetric");
     }
   }
 
   if (EvalAAMD) {
     // iterate over all pairs of load, store
     for (Value *Load : Loads) {
       for (Value *Store : Stores) {
         AliasResult AR = AA.alias(MemoryLocation::get(cast<LoadInst>(Load)),

llvm/lib/Analysis/BasicAliasAnalysis.cpp

if (GEP1BaseOffset.sge(0)) {
           return PartialAlias;
         return NoAlias;
       }
     }
   }
 
   if (!DecompGEP1.VarIndices.empty()) {
     APInt Modulo(MaxPointerSize, 0);
-    bool AllPositive = true;
+    bool AllNonNegative = GEP1BaseOffset.isNonNegative();
+    bool AllNonPositive = GEP1BaseOffset.isNonPositive();
     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;
 
-      if (AllPositive) {
+      if (AllNonNegative || AllNonPositive) {
         // 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));
+        AllNonNegative &= (SignKnownZero && Scale.isNonNegative()) ||
+                          (SignKnownOne && Scale.isNonPositive());
+        AllNonPositive &= (SignKnownZero && Scale.isNonPositive()) ||
+                          (SignKnownOne && Scale.isNonNegative());
       }
     }
 
     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);
     if (V1Size != LocationSize::unknown() &&
         V2Size != LocationSize::unknown() && ModOffset.uge(V2Size.getValue()) &&
         (Modulo - 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() &&
+    // If we know all the variables are non-negative, then the total offset is
+    // also non-negative and >= GEP1BaseOffset. We have the following layout:
+    // [0, V2Size) ... [TotalOffset, TotalOffer+V1Size]
+    // If GEP1BaseOffset >= V2Size, the accesses don't alias.
+    if (AllNonNegative && V2Size != LocationSize::unknown() &&
         GEP1BaseOffset.uge(V2Size.getValue()))
       return NoAlias;
+    // Similarly, if the variables are non-positive, then the total offset is
+    // also non-positive and <= GEP1BaseOffset. We have the following layout:
+    // [TotalOffset, TotalOffset+V1Size) ... [0, V2Size)
+    // If -GEP1BaseOffset >= V1Size, the accesses don't alias.
+    if (AllNonPositive && V1Size != LocationSize::unknown() &&
+        (-GEP1BaseOffset).uge(V1Size.getValue()))
+      return NoAlias;
 
     if (constantOffsetHeuristic(DecompGEP1.VarIndices, V1Size, V2Size,
                                 GEP1BaseOffset, &AC, DT))
       return NoAlias;
   }
 
   // Statically, we can see that the base objects are the same, but the
   // pointers have dynamic offsets which we can't resolve. And none of our

llvm/test/Analysis/BasicAA/zext.ll

define void @test_with_lshr(i64 %i) {
   %1 = tail call i8* @malloc(i64 120)
   %a = getelementptr inbounds i8, i8* %1, i64 8
   %2 = getelementptr inbounds i8, i8* %1, i64 16
   %3 = lshr i64 %i, 2
   %b = getelementptr inbounds i8, i8* %2, i64 %3
   ret void
 }
 
+; CHECK-LABEL: test_with_lshr_different_sizes
+; CHECK:  NoAlias: i16* %m2.idx, i8* %m1
+
+define void @test_with_lshr_different_sizes(i64 %i) {
+  %m0 = tail call i8* @malloc(i64 120)
+  %m1 = getelementptr inbounds i8, i8* %m0, i64 1
+  %m2 = getelementptr inbounds i8, i8* %m0, i64 2
+  %idx = lshr i64 %i, 2
+  %m2.i16 = bitcast i8* %m2 to i16*
+  %m2.idx = getelementptr inbounds i16, i16* %m2.i16, i64 %idx
+  ret void
+}
+
 ; CHECK-LABEL: test_with_a_loop
 ; CHECK:  NoAlias: i8* %a, i8* %b
 
 define void @test_with_a_loop(i8* %mem) {
   br label %for.loop
 
 for.loop:
   %i = phi i32 [ 0, %0 ], [ %i.plus1, %for.loop ]