[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

 /// Cutoff after which to stop analysing a set of phi nodes potentially involved
 /// in a cycle. Because we are analysing 'through' phi nodes, we need to be
 /// careful with value equivalence. We use reachability to make sure a value
 /// cannot be involved in a cycle.
 const unsigned MaxNumPhiBBsValueReachabilityCheck = 20;
 
 // The max limit of the search depth in DecomposeGEPExpression() and
 // getUnderlyingObject().
-static const unsigned MaxLookupSearchDepth = 6;
+static cl::opt<unsigned>
+    MaxLookupSearchDepth("max-lookup-search-depth", cl::init(6), cl::Hidden,
+                         cl::desc("Max limit of the search depth"));
 
 bool BasicAAResult::invalidate(Function &Fn, const PreservedAnalyses &PA,
                                FunctionAnalysisManager::Invalidator &Inv) {
   // We don't care if this analysis itself is preserved, it has no state. But
   // we need to check that the analyses it depends on have been. Note that we
   // may be created without handles to some analyses and in that case don't
   // depend on them.
   if (Inv.invalidate<AssumptionAnalysis>(Fn, PA) ||
for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
         continue;
       }
 
       // For an array/pointer, add the element offset, explicitly scaled.
       if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) {
         if (CIdx->isZero())
           continue;
 
-        // Don't attempt to analyze GEPs if the scalable index is not zero.
+        // Use VariableGEPIndex with a vscale constant expression if the
+        // scalable index is not zero.
         TypeSize AllocTypeSize = DL.getTypeAllocSize(GTI.getIndexedType());
         if (AllocTypeSize.isScalable()) {
-          Decomposed.Base = V;
-          return Decomposed;
-        }
+          GepHasConstantOffset = false;
+
+          // If the integer type is smaller than the index size, it is
+          // implicitly sign extended or truncated to index size.
+          unsigned Width = Index->getType()->getIntegerBitWidth();
+          unsigned SExtBits = IndexSize > Width ? IndexSize - Width : 0;
+          unsigned TruncBits = IndexSize < Width ? Width - IndexSize : 0;
+          LinearExpression LE = GetLinearExpression(
+              CastedValue(Index, 0, SExtBits, TruncBits), DL, 0, AC, DT);
 
+          // Scale by the type size.
+          unsigned TypeSize = AllocTypeSize.getKnownMinSize();
+          LE = LE.mul(APInt(IndexSize, TypeSize), GEPOp->isInBounds());
+          Decomposed.Offset += LE.Offset.sext(MaxIndexSize);
+          APInt Scale = LE.Scale.sext(MaxIndexSize);
+
+          // Make sure that we have a scale that makes sense for this target's
+          // index size.
+          const uint64_t CValue = CIdx->getSExtValue();
+          Scale = adjustToIndexSize(APInt(IndexSize, CValue), IndexSize);
+
+          VariableGEPIndex Entry = {LE.Val, Scale, CxtI, LE.IsNSW};
+          Decomposed.VarIndices.push_back(Entry);
+        } else
           Decomposed.Offset += AllocTypeSize.getFixedSize() *
                                CIdx->getValue().sextOrTrunc(MaxIndexSize);
         continue;
       }
 
+      // The vscale index is non-constant.
       TypeSize AllocTypeSize = DL.getTypeAllocSize(GTI.getIndexedType());
       if (AllocTypeSize.isScalable()) {
         Decomposed.Base = V;
         return Decomposed;
       }
 
       GepHasConstantOffset = false;
 

llvm/test/Analysis/BasicAA/vscale.ll

-; RUN: opt < %s -aa-pipeline=basic-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=basic-aa -passes=aa-eval -max-lookup-search-depth=7 -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
 
 ; getelementptr
 
 ; CHECK-LABEL: gep_alloca_const_offset_1
 ; CHECK-DAG:  MustAlias:    <vscale x 4 x i32>* %alloc, <vscale x 4 x i32>* %gep1
 ; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %alloc, <vscale x 4 x i32>* %gep2
 ; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %gep1, <vscale x 4 x i32>* %gep2
 define void @gep_alloca_const_offset_1() {
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
 }
define void @gep_different_base_const_offset(<vscale x 4 x i32>* noalias %p1, <vscale x 4 x i32>* noalias %p2) {
   ret void
 }
 
 ; getelementptr + bitcast
 
 ; CHECK-LABEL: gep_bitcast_1
 ; CHECK-DAG:   MustAlias:    <vscale x 4 x i32>* %p, i32* %p2
 ; CHECK-DAG:   MayAlias:     i32* %gep1, <vscale x 4 x i32>* %p
-; CHECK-DAG:   MayAlias:     i32* %gep1, i32* %p2
+; CHECK-DAG:   NoAlias:     i32* %gep1, i32* %p2
 ; CHECK-DAG:   MayAlias:     i32* %gep2, <vscale x 4 x i32>* %p
 ; CHECK-DAG:   MayAlias:     i32* %gep1, i32* %gep2
 ; CHECK-DAG:   NoAlias:      i32* %gep2, i32* %p2
 define void @gep_bitcast_1(<vscale x 4 x i32>* %p) {
   %gep1 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %p, i64 1, i64 0
   %p2 = bitcast <vscale x 4 x i32>* %p to i32*
   %gep2 = getelementptr i32, i32* %p2, i64 4
   load <vscale x 4 x i32>, <vscale x 4 x i32>* %p
   load i32, i32* %gep1
   load i32, i32* %gep2
   load i32, i32* %p2
   ret void
 }
 
 ; CHECK-LABEL: gep_bitcast_2
 ; CHECK-DAG:  MustAlias:    <vscale x 4 x i32>* %p, <vscale x 4 x float>* %p2
 ; CHECK-DAG:  MayAlias:     i32* %gep1, <vscale x 4 x i32>* %p
 ; CHECK-DAG:  MayAlias:     i32* %gep1, <vscale x 4 x float>* %p2
 ; CHECK-DAG:  MayAlias:     float* %gep2, <vscale x 4 x i32>* %p
-; CHECK-DAG:  MayAlias:     i32* %gep1, float* %gep2
+; CHECK-DAG:  MustAlias:     i32* %gep1, float* %gep2
 ; CHECK-DAG:  MayAlias:     float* %gep2, <vscale x 4 x float>* %p2
 define void @gep_bitcast_2(<vscale x 4 x i32>* %p) {
   %gep1 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %p, i64 1, i64 0
   %p2 = bitcast <vscale x 4 x i32>* %p to <vscale x 4 x float>*
   %gep2 = getelementptr <vscale x 4 x float>, <vscale x 4 x float>* %p2, i64 1, i64 0
   load i32, i32* %gep1
   load float, float* %gep2
   load <vscale x 4 x i32>, <vscale x 4 x i32>* %p
define void @gep_recursion_level_1(i32* %a, <vscale x 4 x i32>* %p) {
   load i32, i32* %a
   load i32, i32* %gep
   load i32, i32* %gep_rec_1
   ret void
 }
 
 ; CHECK-LABEL: gep_recursion_level_1_bitcast
 ; CHECK-DAG:  MustAlias:    i32* %a, <vscale x 4 x i32>* %p
-; CHECK-DAG:  MayAlias:     i32* %a, i32* %gep
-; CHECK-DAG:  MayAlias:     i32* %a, i32* %gep_rec_1
+; CHECK-DAG:  NoAlias:     i32* %a, i32* %gep
+; CHECK-DAG:  NoAlias:     i32* %a, i32* %gep_rec_1
 ; CHECK-DAG:  MayAlias:     i32* %gep, <vscale x 4 x i32>* %p
 ; CHECK-DAG:  MayAlias:     i32* %gep_rec_1, <vscale x 4 x i32>* %p
 ; CHECK-DAG:  NoAlias:      i32* %gep, i32* %gep_rec_1
 define void @gep_recursion_level_1_bitcast(i32* %a) {
   %p = bitcast i32* %a to <vscale x 4 x i32>*
   %gep = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %p, i64 1, i64 2
   %gep_rec_1 = getelementptr i32, i32* %gep, i64 1
   load <vscale x 4 x i32>, <vscale x 4 x i32>* %p

 ; CHECK-DAG: NoAlias:      i32* %gep_rec_2, i32* %gep_rec_5
 ; CHECK-DAG: NoAlias:      i32* %gep_rec_2, i32* %gep_rec_6
 ; CHECK-DAG: NoAlias:      i32* %gep_rec_3, i32* %gep_rec_4
 ; CHECK-DAG: NoAlias:      i32* %gep_rec_3, i32* %gep_rec_5
 ; CHECK-DAG: NoAlias:      i32* %gep_rec_3, i32* %gep_rec_6
 ; CHECK-DAG: NoAlias:      i32* %gep_rec_4, i32* %gep_rec_5
 ; CHECK-DAG: NoAlias:      i32* %gep_rec_4, i32* %gep_rec_6
 ; CHECK-DAG: NoAlias:      i32* %gep_rec_5, i32* %gep_rec_6
-; GEP max lookup depth was set to 6.
+; GEP max lookup depth was set to 7.
 define void @gep_recursion_max_lookup_depth_reached(i32* %a, <vscale x 4 x i32>* %p) {
   %gep = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %p, i64 1, i64 2
   %gep_rec_1 = getelementptr i32, i32* %gep, i64 1
   %gep_rec_2 = getelementptr i32, i32* %gep_rec_1, i64 1
   %gep_rec_3 = getelementptr i32, i32* %gep_rec_2, i64 1
   %gep_rec_4 = getelementptr i32, i32* %gep_rec_3, i64 1
   %gep_rec_5 = getelementptr i32, i32* %gep_rec_4, i64 1
   %gep_rec_6 = getelementptr i32, i32* %gep_rec_5, i64 1

llvm/test/Transforms/GVN/vscale.ll

;
   %load1 = load i32, i32* %gep1
   %p2 = bitcast <vscale x 4 x i32>* %p to i32*
   %gep2 = getelementptr i32, i32* %p2, i64 4
   %load2 = load i32, i32* %gep2 ; <- can not determine at compile-time if %load1 and %load2 are same addr
   %add = add i32 %load1, %load2
   ret i32 %add
 }
 
-; TODO: BasicAA return MayAlias for %gep1,%gep2, could improve as MustAlias.
+; BasicAA return MayAlias for %gep1,%gep2, could improve as MustAlias.
 define i32 @load_clobber_load_gep3(<vscale x 4 x i32>* %p) {
 ; CHECK-LABEL: @load_clobber_load_gep3(
 ; CHECK-NEXT:    [[GEP1:%.*]] = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* [[P:%.*]], i64 1, i64 0
 ; CHECK-NEXT:    [[LOAD1:%.*]] = load i32, i32* [[GEP1]], align 4
-; CHECK-NEXT:    [[P2:%.*]] = bitcast <vscale x 4 x i32>* [[P]] to <vscale x 4 x float>*
-; CHECK-NEXT:    [[GEP2:%.*]] = getelementptr <vscale x 4 x float>, <vscale x 4 x float>* [[P2]], i64 1, i64 0
-; CHECK-NEXT:    [[LOAD2:%.*]] = load float, float* [[GEP2]], align 4
-; CHECK-NEXT:    [[CAST:%.*]] = bitcast float [[LOAD2]] to i32
-; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[LOAD1]], [[CAST]]
+; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[LOAD1]], [[LOAD1]]
 ; CHECK-NEXT:    ret i32 [[ADD]]
 ;
   %gep1 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %p, i64 1, i64 0
   %load1 = load i32, i32* %gep1
   %p2 = bitcast <vscale x 4 x i32>* %p to <vscale x 4 x float>*
   %gep2 = getelementptr <vscale x 4 x float>, <vscale x 4 x float>* %p2, i64 1, i64 0
   %load2 = load float, float* %gep2 ; <- load could be eliminated
   %cast = bitcast float %load2 to i32

 ; 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