[AA] Improve the BasicAA analysis capability

[Allen]

Summary

According https://discourse.llvm.org/t/memoryssa-does-the-accessedbetween-support-scalable-vector-pointer/65052,
scalable vector support in BasicAA is currently essentially limited,
and should be improved effectively for a constant offset GEP if the scalable index is zero, eg:

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

[nikic]

This is not the correct way to address the issue. Support for scalable vectors needs to be added inside DecomposeGEPExpression().

[Allen]

refactor in BasicAAResult::DecomposeGEPExpression

[Allen]

In D133567#3779695, @nikic wrote:

This is not the correct way to address the issue. Support for scalable vectors needs to be added inside DecomposeGEPExpression().

apply your comment, thanks @nikic

[nikic]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

615

Instead of checking the source element type, this should check whether the getTypeAllocSize fetched below isScalable.

624

nit: Drop else after continue.

llvm/test/Transforms/GVN/vscale.ll

49

Drop TODO.

[Allen]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

615

apply your comment, thanks

llvm/test/Transforms/GVN/vscale.ll

49

DONE

[nikic]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

615

Please store the getTypeAllocSize() result in a variable and reuse it below. Also, the num operands checks is no longer needed.

629

Here again we should be checking the alloc size, not the source element type. It should be possible to support something like getelementptr <vscale x 4 x i32>, ptr %p, i64 0, i64 %i, where the variable is on a non-scalable index.

[Allen]

Address the comment, and store the getTypeAllocSize() result in a variable and reuse it, then it extend
getelementptr <vscale x 4 x i32>, ptr %p, i64 0, i64 c --> getelementptr <vscale x 4 x i32>, ptr %p, i64 0, i64 %i

[Allen]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

615

Thanks for detail

629

Yes, good catch, thanks very much

[nikic]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

597

Please move this below the StructType check, this call is expensive.

629

Can you please also add a test for this case? Something like using %i and %j = add %i, 1 as indices. should probably work.

[Allen]

Add a new case redundant_load_elimination_zero_index_1 according comment

[nikic]

LGTM

[Allen]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

597

Done, thanks

629

Of course, added new case redundant_load_elimination_zero_index_1

llvm/lib/Analysis/BasicAliasAnalysis.cpp

do {
     // all geps parsed were in bounds.
     if (Decomposed.InBounds == None)
       Decomposed.InBounds = GEPOp->isInBounds();
     else if (!GEPOp->isInBounds())
       Decomposed.InBounds = false;
 
     assert(GEPOp->getSourceElementType()->isSized() && "GEP must be sized");
 
-    // Don't attempt to analyze GEPs if index scale is not a compile-time
-    // constant.
-    if (isa<ScalableVectorType>(GEPOp->getSourceElementType())) {
-      Decomposed.Base = V;
-      return Decomposed;
-    }
-
     unsigned AS = GEPOp->getPointerAddressSpace();
     // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices.
     gep_type_iterator GTI = gep_type_begin(GEPOp);
     unsigned IndexSize = DL.getIndexSizeInBits(AS);
     // Assume all GEP operands are constants until proven otherwise.
     bool GepHasConstantOffset = true;
     for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
          I != E; ++I, ++GTI) {
       const Value *Index = *I;
       // Compute the (potentially symbolic) offset in bytes for this index.
       if (StructType *STy = GTI.getStructTypeOrNull()) {
         // For a struct, add the member offset.
         unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
         if (FieldNo == 0)
           continue;
 
         Decomposed.Offset += DL.getStructLayout(STy)->getElementOffset(FieldNo);
         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.
+        if (isa<ScalableVectorType>(GEPOp->getSourceElementType()) &&
+            (I - GEPOp->op_begin() != GEPOp->getNumOperands() - 1)) {
+          Decomposed.Base = V;
+          return Decomposed;
+        }
+
         Decomposed.Offset +=
             DL.getTypeAllocSize(GTI.getIndexedType()).getFixedSize() *
             CIdx->getValue().sextOrTrunc(MaxIndexSize);
         continue;
+      } else if (isa<ScalableVectorType>(GEPOp->getSourceElementType())) {
+        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);

llvm/test/Transforms/GVN/vscale.ll

 ;
   %load1 = load <vscale x 4 x i32>, <vscale x 4 x i32>* %p
   store <vscale x 4 x i32> zeroinitializer, <vscale x 4 x i32>* %p2
   %load2 = load <vscale x 4 x i32>, <vscale x 4 x i32>* %p ; <- load to be eliminated
   %add = add <vscale x 4 x i32> %load1, %load2
   ret <vscale x 4 x i32> %add
 }
 
 ; TODO: BasicAA return MayAlias for %gep1,%gep2, could improve as MustAlias.
 define i32 @load_clobber_load_gep1(<vscale x 4 x i32>* %p) {
 ; CHECK-LABEL: @load_clobber_load_gep1(
 ; CHECK-NEXT:    [[GEP1:%.*]] = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* [[P:%.*]], i64 0, i64 1
 ; CHECK-NEXT:    [[LOAD1:%.*]] = load i32, i32* [[GEP1]], align 4
-; CHECK-NEXT:    [[P2:%.*]] = bitcast <vscale x 4 x i32>* [[P]] to i32*
-; CHECK-NEXT:    [[GEP2:%.*]] = getelementptr i32, i32* [[P2]], i64 1
-; CHECK-NEXT:    [[LOAD2:%.*]] = load i32, i32* [[GEP2]], align 4
-; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[LOAD1]], [[LOAD2]]
+; 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 0, i64 1
   %load1 = load i32, i32* %gep1
   %p2 = bitcast <vscale x 4 x i32>* %p to i32*
   %gep2 = getelementptr i32, i32* %p2, i64 1
   %load2 = load i32, i32* %gep2 ; <- load could be eliminated
   %add = add i32 %load1, %load2
;
   store <vscale x 4 x i32> zeroinitializer, <vscale x 4 x i32>* %p
   call void asm sideeffect "", ""()
   %load = load <vscale x 4 x i32>, <vscale x 4 x i32>* %p
   ret <vscale x 4 x i32> %load
 }
 
 define i32 @store_clobber_load() {
 ; CHECK-LABEL: @store_clobber_load(
-; CHECK-NEXT:    [[ALLOC:%.*]] = alloca <vscale x 4 x i32>
+; CHECK-NEXT:    [[ALLOC:%.*]] = alloca <vscale x 4 x i32>, align 16
 ; CHECK-NEXT:    store <vscale x 4 x i32> undef, <vscale x 4 x i32>* [[ALLOC]], align 16
 ; CHECK-NEXT:    [[PTR:%.*]] = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* [[ALLOC]], i32 0, i32 1
 ; CHECK-NEXT:    [[LOAD:%.*]] = load i32, i32* [[PTR]], align 4
 ; CHECK-NEXT:    ret i32 [[LOAD]]
 ;
   %alloc = alloca <vscale x 4 x i32>
   store <vscale x 4 x i32> undef, <vscale x 4 x i32>* %alloc
   %ptr = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %alloc, i32 0, i32 1

 }
 
 
 ; Load elimination across BBs
 
 define <vscale x 4 x i32>* @load_from_alloc_replaced_with_undef() {
 ; CHECK-LABEL: @load_from_alloc_replaced_with_undef(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[A:%.*]] = alloca <vscale x 4 x i32>
+; CHECK-NEXT:    [[A:%.*]] = alloca <vscale x 4 x i32>, align 16
 ; CHECK-NEXT:    br i1 undef, label [[IF_END:%.*]], label [[IF_THEN:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    store <vscale x 4 x i32> zeroinitializer, <vscale x 4 x i32>* [[A]], align 16
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
 ; CHECK-NEXT:    ret <vscale x 4 x i32>* [[A]]
 ;
 entry:
if.then:
   br label %if.end
 
 if.end:
   %result = phi i32 [ %add, %if.then ], [ %load1, %entry ]
   ret i32 %result
 }
 
 ; TODO: BasicAA return MayAlias for %gep1,%gep2, could improve as NoAlias.
-define void @redundant_load_elimination_2(i1 %c, <vscale x 4 x i32>* %p, i32* %q, <vscale x 4 x i32> %v) {
+define void @redundant_load_elimination_2(i1 %c, <vscale x 4 x i32>* %p, i32* %q) {
 ; 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:
if.then:
   %t = load i32, i32* %gep1 ; <- load could be eliminated
   store i32 %t, i32* %q
   ret void
 
 if.else:
   ret void
 }
 
+define void @redundant_load_elimination_zero_index(i1 %c, <vscale x 4 x i32>* %p, i32* %q) {
+; CHECK-LABEL: @redundant_load_elimination_zero_index(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[GEP1:%.*]] = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* [[P:%.*]], i64 0, 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 0, 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:    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 0, i64 1
+  store i32 0, i32* %gep1
+  %gep2 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %p, i64 0, i64 0
+  store i32 1, i32* %gep2
+  br i1 %c, label %if.else, label %if.then
+
+if.then:
+  %t = load i32, i32* %gep1 ; <- load could be eliminated
+  store i32 %t, i32* %q
+  ret void
+
+if.else:
+  ret void
+}
+
 ; TODO: load in if.then could have been eliminated
 define void @missing_load_elimination(i1 %c, <vscale x 4 x i32>* %p, <vscale x 4 x i32>* %q, <vscale x 4 x i32> %v) {
 ; CHECK-LABEL: @missing_load_elimination(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    store <vscale x 4 x i32> zeroinitializer, <vscale x 4 x i32>* [[P:%.*]], align 16
 ; CHECK-NEXT:    [[P1:%.*]] = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* [[P]], i64 1
 ; CHECK-NEXT:    store <vscale x 4 x i32> [[V:%.*]], <vscale x 4 x i32>* [[P1]], align 16
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF_ELSE:%.*]], label [[IF_THEN:%.*]]