[AA] Improve the BasicAA analysis capability base on GEP

[Allen]

Summary

Improved effectively for a constant offset GEP if the scalable index is same.

getelementptr <vscale x 4 x i32>, ptr %p, i64 1, i64 %i
getelementptr <vscale x 4 x i32>, ptr %p, i64 1, i64 %j

[nikic]

If you want to support this, it must be part of GEP decomposition.

If you are only interested in constants for the vscale index, then it's probably possible to support this with relatively low effort by using a VariableGEPIndex with a vscale constant expression. That should allow all the existing modelling to handle it (possibly including range analysis based on vscale_range attributes).

If you are interested in variables for the vscale index, then this won't work, and it would be necessary to add first class vscale support to VariableGEPIndex (i.e. a separate bool, which all code working on decomposed GEPs has to handle in the appropriate way).

[Allen]

Refactor in DecomposeGEPExpression

[Allen]

In D133844#3789000, @nikic wrote:

If you want to support this, it must be part of GEP decomposition.

If you are only interested in constants for the vscale index, then it's probably possible to support this with relatively low effort by using a VariableGEPIndex with a vscale constant expression. That should allow all the existing modelling to handle it (possibly including range analysis based on vscale_range attributes).

If you are interested in variables for the vscale index, then this won't work, and it would be necessary to add first class vscale support to VariableGEPIndex (i.e. a separate bool, which all code working on decomposed GEPs has to handle in the appropriate way).

Thanks for your suggestion, Firstly I hope to address the constants vscale index only.

[nikic]

I don't get how this patch is supposed to work. It seems to create a VariableGEPIndex -- but I don't see the vscale factor represented anywhere in there?

Worth noting that https://reviews.llvm.org/D134648 plans to make vscale non-constant, so making the use of vscale constant expressions is likely not going to be possible going forward...

[Allen]

In D133844#3844770, @nikic wrote:

I don't get how this patch is supposed to work. It seems to create a VariableGEPIndex -- but I don't see the vscale factor represented anywhere in there?

Worth noting that https://reviews.llvm.org/D134648 plans to make vscale non-constant, so making the use of vscale constant expressions is likely not going to be possible going forward...

Thank @nikic for your guidance. It looks a little more complicated than I expected. Yes, this need more work as the vscale is non-constant in the whole project.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

if (!V1Size.hasValue() && !V2Size.hasValue()) {
     // objects don't alias.
     AliasResult BaseAlias = getBestAAResults().alias(
         MemoryLocation::getBeforeOrAfter(UnderlyingV1),
         MemoryLocation::getBeforeOrAfter(UnderlyingV2), AAQI);
     return BaseAlias == AliasResult::NoAlias ? AliasResult::NoAlias
                                              : AliasResult::MayAlias;
   }
 
+  // If it can be confirmed NoAlias, no further decomposition is required.
+  if (isa<GEPOperator>(V2) && UnderlyingV1 == UnderlyingV2 &&
+      V1Size.hasValue() && V2Size.hasValue()) {
+    auto *EltTy1 = GEP1->getResultElementType();
+    auto *EltTy2 = cast<GEPOperator>(V2)->getResultElementType();
+    unsigned MaxIndexSize = DL.getMaxIndexSizeInBits() - 1;
+    TypeSize AllocaTypeSize = DL.getTypeAllocSize(EltTy1);
+    Optional<int64_t> Offset = isPointerOffset(GEP1, V2, DL);
+    if ((EltTy1 == EltTy2) && Offset && !AllocaTypeSize.isScalable() &&
+        std::max(V1Size.getValue(), V2Size.getValue()) <= std::abs(*Offset) &&
+        (std::abs(*Offset) < 1ULL << MaxIndexSize))
+      return AliasResult::NoAlias;
+  }
+
   DecomposedGEP DecompGEP1 = DecomposeGEPExpression(GEP1, DL, &AC, DT);
   DecomposedGEP DecompGEP2 = DecomposeGEPExpression(V2, DL, &AC, DT);
 
   // Bail if we were not able to decompose anything.
   if (DecompGEP1.Base == GEP1 && DecompGEP2.Base == V2)
     return AliasResult::MayAlias;
 
   // Subtract the GEP2 pointer from the GEP1 pointer to find out their

llvm/test/Analysis/BasicAA/vscale.ll

define void @gep_alloca_symbolic_offset(i64 %idx1, i64 %idx2) {
   load <vscale x 4 x i32>, <vscale x 4 x i32>* %gep1
   load <vscale x 4 x i32>, <vscale x 4 x i32>* %gep2
   ret void
 }
 
 ; CHECK-LABEL: gep_same_base_const_offset
 ; CHECK-DAG:  MayAlias:     i32* %gep1, <vscale x 4 x i32>* %p
 ; CHECK-DAG:  MayAlias:     i32* %gep2, <vscale x 4 x i32>* %p
-; TODO: AliasResult for gep1,gep2 can be improved as NoAlias
-; CHECK-DAG:  MayAlias:     i32* %gep1, i32* %gep2
+;  AliasResult for gep1,gep2 can be improved as NoAlias
+; CHECK-DAG:  NoAlias:     i32* %gep1, i32* %gep2
 define void @gep_same_base_const_offset(<vscale x 4 x i32>* %p) {
   %gep1 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %p, i64 1, i64 0
   %gep2 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %p, i64 1, i64 1
   load <vscale x 4 x i32>, <vscale x 4 x i32>* %p
   load i32, i32* %gep1
   load i32, i32* %gep2
   ret void
 }

llvm/test/Transforms/GVN/vscale.ll

 ; CHECK-LABEL: @redundant_load_elimination_2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[GEP1:%.*]] = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* [[P:%.*]], i64 1, i64 1
 ; CHECK-NEXT:    store i32 0, i32* [[GEP1]], align 4
 ; CHECK-NEXT:    [[GEP2:%.*]] = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* [[P]], i64 1, i64 0
 ; CHECK-NEXT:    store i32 1, i32* [[GEP2]], align 4
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF_ELSE:%.*]], label [[IF_THEN:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    [[T:%.*]] = load i32, i32* [[GEP1]], align 4
-; CHECK-NEXT:    store i32 [[T]], i32* [[Q:%.*]], align 4
+; CHECK-NEXT:    store i32 0, i32* [[Q:%.*]], align 4
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.else:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %gep1 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %p, i64 1, i64 1
   store i32 0, i32* %gep1
   %gep2 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %p, i64 1, i64 0