From c00545dc3213af24786029ff04d6be31c7baf0b7 Mon Sep 17 00:00:00 2001
From: Nikita Popov <nikita.ppv@gmail.com>
Date: Sat, 7 Nov 2020 19:02:49 +0100
Subject: [PATCH] [BasicAA] Remove checks for GEP decomposition limit reached

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 1a444489e9d90915cfdda0720489893896ef1503. However, I
believe that the problem this was intended to address was later
properly fixed with 1726fc698ccb85fe4bb23c200a50f28b57fc53cb, and
the checks are no longer necessary since then (and were not the
right fix in the first place).

Differential Revision: https://reviews.llvm.org/D91010
---
 llvm/lib/Analysis/BasicAliasAnalysis.cpp           | 23 +++++-----------------
 .../Analysis/BasicAA/gep-decomposition-limit.ll    |  8 ++++----
 2 files changed, 9 insertions(+), 22 deletions(-)

diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
index 9ce23247a11..aa83fed6d3a 100644
--- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
@@ -1259,10 +1259,8 @@ AliasResult BasicAAResult::aliasGEP(
   DecompGEP1.HasCompileTimeConstantScale =
       DecompGEP2.HasCompileTimeConstantScale = true;
 
-  bool GEP1MaxLookupReached =
-    DecomposeGEPExpression(GEP1, DecompGEP1, DL, &AC, DT);
-  bool GEP2MaxLookupReached =
-    DecomposeGEPExpression(V2, DecompGEP2, DL, &AC, DT);
+  DecomposeGEPExpression(GEP1, DecompGEP1, DL, &AC, DT);
+  DecomposeGEPExpression(V2, DecompGEP2, DL, &AC, DT);
 
   // Don't attempt to analyze the decomposed GEP if index scale is not a
   // compile-time constant.
@@ -1280,8 +1278,7 @@ AliasResult BasicAAResult::aliasGEP(
   // 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
@@ -1289,8 +1286,7 @@ AliasResult BasicAAResult::aliasGEP(
   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 =
@@ -1301,8 +1297,7 @@ AliasResult BasicAAResult::aliasGEP(
     // 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)
@@ -1331,10 +1326,6 @@ AliasResult BasicAAResult::aliasGEP(
         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;
@@ -1361,10 +1352,6 @@ AliasResult BasicAAResult::aliasGEP(
       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
diff --git a/llvm/test/Analysis/BasicAA/gep-decomposition-limit.ll b/llvm/test/Analysis/BasicAA/gep-decomposition-limit.ll
index a375c4e7b14..ea33426fc3d 100644
--- a/llvm/test/Analysis/BasicAA/gep-decomposition-limit.ll
+++ b/llvm/test/Analysis/BasicAA/gep-decomposition-limit.ll
@@ -6,13 +6,13 @@
 ; 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
-- 
2.11.0