[BasicAA] Remove checks for GEP decomposition limit reached

[nikic]

Summary

The GEP aliasing code currently checks for the GEP decomposition limit being reached (i.e., we did not reach the "final" underlying object). As far as I can see, these checks are not necessary. It is perfectly fine to work with a GEP whose base can still be further decomposed.

Looking back through the commit history, these checks were originally introduced in https://github.com/llvm/llvm-project/commit/1a444489e9d90915cfdda0720489893896ef1503. However, I believe that the problem this was intended to address was later properly fixed with https://github.com/llvm/llvm-project/commit/1726fc698ccb85fe4bb23c200a50f28b57fc53cb, and the checks are no longer necessary since then (and were not the right fix in the first place).

Is there something I'm missing here?

[jdoerfert]

I would assume the "leftover" parts could just as well be part of the base, right? We'd still run the same logic, wouldn't we?

[nikic]

In D91010#2382933, @jdoerfert wrote:

I would assume the "leftover" parts could just as well be part of the base, right? We'd still run the same logic, wouldn't we?

Right. If the limit is reached, then we would for example have another GEP as base, but that shouldn't influence the treatment it gets in this function.

[jdoerfert]

OK, this sounds sane to me. Can we create a test though?

[nikic]

Add test for behavior at decomposition limit.

[nikic]

llvm/test/Analysis/BasicAA/gep-decomposition-limit.ll

11

The effective change here is that results at the decomposition limit are now as good as results below the limit. Results above it have less precision.

15

Slightly non-obvious: The reason why we get a better result on the last one is that we strip off an offset 6 from both sides (from inc6 because that's all there is, from inc7 because of the limit). As the offset is the same, the recursive query can preserves access sizes, so we get a precise end result. For the other cases we'll strip off an asymmetric offset (5 and 6, or 7 and 6) and thus the recursive query is performed without sizes, so we don't get precise results there.

[jdoerfert]

LGTM

llvm/lib/Analysis/BasicAliasAnalysis.cpp

AliasResult BasicAAResult::aliasGEP(
     const Value *UnderlyingV1, const Value *UnderlyingV2, AAQueryInfo &AAQI) {
   DecomposedGEP DecompGEP1, DecompGEP2;
   unsigned MaxPointerSize = getMaxPointerSize(DL);
   DecompGEP1.Offset = APInt(MaxPointerSize, 0);
   DecompGEP2.Offset = APInt(MaxPointerSize, 0);
   DecompGEP1.HasCompileTimeConstantScale =
       DecompGEP2.HasCompileTimeConstantScale = true;
 
-  bool GEP1MaxLookupReached =
-    DecomposeGEPExpression(GEP1, DecompGEP1, DL, &AC, DT);
-  bool GEP2MaxLookupReached =
-    DecomposeGEPExpression(V2, DecompGEP2, DL, &AC, DT);
 
   // Don't attempt to analyze the decomposed GEP if index scale is not a
   // compile-time constant.
   if (!DecompGEP1.HasCompileTimeConstantScale ||
       !DecompGEP2.HasCompileTimeConstantScale)
     return MayAlias;
 
   APInt GEP1BaseOffset = DecompGEP1.Offset;
   APInt GEP2BaseOffset = DecompGEP2.Offset;
 
   assert(DecompGEP1.Base == UnderlyingV1 && DecompGEP2.Base == UnderlyingV2 &&
          "DecomposeGEPExpression returned a result different from "
          "getUnderlyingObject");
 
   // If the GEP's offset relative to its base is such that the base would
   // fall below the start of the object underlying V2, then the GEP and V2
   // cannot alias.
-  if (!GEP1MaxLookupReached && !GEP2MaxLookupReached &&
-      isGEPBaseAtNegativeOffset(GEP1, DecompGEP1, DecompGEP2, V2Size))
+  if (isGEPBaseAtNegativeOffset(GEP1, DecompGEP1, DecompGEP2, V2Size))
     return NoAlias;
   // If we have two gep instructions with must-alias or not-alias'ing base
   // pointers, figure out if the indexes to the GEP tell us anything about the
   // derived pointer.
   if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) {
     // Check for the GEP base being at a negative offset, this time in the other
     // direction.
-    if (!GEP1MaxLookupReached && !GEP2MaxLookupReached &&
-        isGEPBaseAtNegativeOffset(GEP2, DecompGEP2, DecompGEP1, V1Size))
+    if (isGEPBaseAtNegativeOffset(GEP2, DecompGEP2, DecompGEP1, V1Size))
       return NoAlias;
     // Do the base pointers alias?
     AliasResult BaseAlias =
         aliasCheck(UnderlyingV1, LocationSize::unknown(), AAMDNodes(),
                    UnderlyingV2, LocationSize::unknown(), AAMDNodes(), AAQI);
 
     // For GEPs with identical sizes and offsets, we can preserve the size
     // and AAInfo when performing the alias check on the underlying objects.
     if (BaseAlias == MayAlias && V1Size == V2Size &&
         GEP1BaseOffset == GEP2BaseOffset &&
-        DecompGEP1.VarIndices == DecompGEP2.VarIndices &&
-        !GEP1MaxLookupReached && !GEP2MaxLookupReached) {
+        DecompGEP1.VarIndices == DecompGEP2.VarIndices) {
       AliasResult PreciseBaseAlias = aliasCheck(
           UnderlyingV1, V1Size, V1AAInfo, UnderlyingV2, V2Size, V2AAInfo, AAQI);
       if (PreciseBaseAlias == NoAlias)
         return NoAlias;
     }
 
     // If we get a No or May, then return it immediately, no amount of analysis
     // will improve this situation.
if (GEP1->getPointerOperand()->stripPointerCastsAndInvariantGroups() ==
             GEP2->getPointerOperand()->stripPointerCastsAndInvariantGroups() &&
         GEP1->getPointerOperandType() == GEP2->getPointerOperandType()) {
       AliasResult R = aliasSameBasePointerGEPs(GEP1, V1Size, GEP2, V2Size, DL);
       // If we couldn't find anything interesting, don't abandon just yet.
       if (R != MayAlias)
         return R;
     }
 
-    // If the max search depth is reached, the result is undefined
-    if (GEP2MaxLookupReached || GEP1MaxLookupReached)
-      return MayAlias;
-
     // Subtract the GEP2 pointer from the GEP1 pointer to find out their
     // symbolic difference.
     GEP1BaseOffset -= GEP2BaseOffset;
     GetIndexDifference(DecompGEP1.VarIndices, DecompGEP2.VarIndices);
 
   } else {
     // Check to see if these two pointers are related by the getelementptr
     // instruction.  If one pointer is a GEP with a non-zero index of the other
if (R != MustAlias) {
       // If V2 may alias GEP base pointer, conservatively returns MayAlias.
       // If V2 is known not to alias GEP base pointer, then the two values
       // cannot alias per GEP semantics: "Any memory access must be done through
       // a pointer value associated with an address range of the memory access,
       // otherwise the behavior is undefined.".
       assert(R == NoAlias || R == MayAlias);
       return R;
     }
-
-    // If the max search depth is reached the result is undefined
-    if (GEP1MaxLookupReached)
-      return MayAlias;
   }
 
   // In the two GEP Case, if there is no difference in the offsets of the
   // computed pointers, the resultant pointers are a must alias.  This
   // happens when we have two lexically identical GEP's (for example).
   //
   // In the other case, if we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2
   // must aliases the GEP, the end result is a must alias also.

llvm/test/Analysis/BasicAA/gep-decomposition-limit.ll

 ; RUN: opt -S -basic-aa -aa-eval -print-all-alias-modref-info -disable-output < %s 2>&1 | FileCheck %s
 
 ; CHECK-LABEL: Function: test
 ;; Before limit:
 ; CHECK-DAG: MustAlias: i8* %gep.add5, i8* %gep.inc5
 ; CHECK-DAG: NoAlias: i8* %gep.inc3, i8* %gep.inc5
 ; CHECK-DAG: NoAlias: i8* %gep.inc4, i8* %gep.inc5
 ;; At limit:
-; CHECK-DAG: MayAlias: i8* %gep.add6, i8* %gep.inc6
-; CHECK-DAG: MayAlias: i8* %gep.inc4, i8* %gep.inc6
-; CHECK-DAG: MayAlias: i8* %gep.inc5, i8* %gep.inc6
+; CHECK-DAG: MustAlias: i8* %gep.add6, i8* %gep.inc6
+; CHECK-DAG: NoAlias: i8* %gep.inc4, i8* %gep.inc6
+; CHECK-DAG: NoAlias: i8* %gep.inc5, i8* %gep.inc6
 ;; After limit:
 ; CHECK-DAG: MayAlias: i8* %gep.add7, i8* %gep.inc7
 ; CHECK-DAG: MayAlias: i8* %gep.inc5, i8* %gep.inc7
-; CHECK-DAG: MayAlias: i8* %gep.inc6, i8* %gep.inc7
+; CHECK-DAG: NoAlias: i8* %gep.inc6, i8* %gep.inc7
 
 define void @test(i8* %base) {
   %gep.add5 = getelementptr i8, i8* %base, i64 5
   %gep.add6 = getelementptr i8, i8* %base, i64 6
   %gep.add7 = getelementptr i8, i8* %base, i64 7
 
   %gep.inc1 = getelementptr i8, i8* %base, i64 1
   %gep.inc2 = getelementptr i8, i8* %gep.inc1, i64 1
   %gep.inc3 = getelementptr i8, i8* %gep.inc2, i64 1
   %gep.inc4 = getelementptr i8, i8* %gep.inc3, i64 1
   %gep.inc5 = getelementptr i8, i8* %gep.inc4, i64 1
   %gep.inc6 = getelementptr i8, i8* %gep.inc5, i64 1
   %gep.inc7 = getelementptr i8, i8* %gep.inc6, i64 1
 
   ret void
 }