[BasicAA] Fix aliasGEP/DecomposeGEPExpression for scalable type.

[huihuiz]

Summary

Don't attempt to analyze the decomposed GEP for scalable type.
GEP index scale is not compile-time constant for scalable type.
Be conservative, return MayAlias.

Explicitly call TypeSize::getFixedSize() to assert on places where
scalable type doesn't make sense.

Add unit tests to check functionality of -basicaa for scalable type.

This patch is needed for D76944.

[huihuiz]

Current upstream is producing wrong AliasResult for scalable type.

take test.ll , run: opt -basicaa -aa-eval -print-all-alias-modref-info -disable-output test.ll.

Then you will see " MustAlias: i32* %gep1, i32* %gep2 "
gep1,gep2 should be MayAlias, not MustAlias.

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
  ret void
}

[efriedma]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1326

I think this still doesn't completely block off all the relevant cases.

DecomposeGEPExpression is recursive, so there are can be multiple levels of GEPs. The GEP over the scalable vector may not be GEP1; it could be GEP1->getPointerOperand(), or something like that.

[huihuiz]

Address review comments.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

1326

Good catch, Thanks Eli!

Moving the checks to DecomposeGEPExpression, so we have knowledge of scalable type given multiple levels of GEPs.

Patch updated accordingly, and with more tests in recursive geps.

[efriedma]

LGTM

llvm/lib/Analysis/BasicAliasAnalysis.cpp

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;
         Decomposed.OtherOffset +=
-          (DL.getTypeAllocSize(GTI.getIndexedType()) *
+            (DL.getTypeAllocSize(GTI.getIndexedType()).getFixedSize() *
              CIdx->getValue().sextOrSelf(MaxPointerSize))
                 .sextOrTrunc(MaxPointerSize);
         continue;
       }
 
       GepHasConstantOffset = false;
 
-      APInt Scale(MaxPointerSize, DL.getTypeAllocSize(GTI.getIndexedType()));
+      APInt Scale(MaxPointerSize,
+                  DL.getTypeAllocSize(GTI.getIndexedType()).getFixedSize());
       unsigned ZExtBits = 0, SExtBits = 0;
 
       // If the integer type is smaller than the pointer size, it is implicitly
       // sign extended to pointer size.
       unsigned Width = Index->getType()->getIntegerBitWidth();
       if (PointerSize > Width)
         SExtBits += PointerSize - Width;
 
if (isa<ArrayType>(Ty) || isa<VectorType>(Ty)) {
     // - both GEPs only index through arrays prior to that.
     //
     // Because array indices greater than the number of elements are valid in
     // GEPs, unless we know the intermediate indices are identical between
     // GEP1 and GEP2 we cannot guarantee that the last indexed arrays don't
     // partially overlap. We also need to check that the loaded size matches
     // the element size, otherwise we could still have overlap.
     Type *LastElementTy = GetElementPtrInst::getTypeAtIndex(Ty, (uint64_t)0);
-    const uint64_t ElementSize = DL.getTypeStoreSize(LastElementTy);
+    const uint64_t ElementSize =
+        DL.getTypeStoreSize(LastElementTy).getFixedSize();
     if (V1Size != ElementSize || V2Size != ElementSize)
       return MayAlias;
 
     for (unsigned i = 0, e = GEP1->getNumIndices() - 1; i != e; ++i)
       if (GEP1->getOperand(i + 1) != GEP2->getOperand(i + 1))
         return MayAlias;
 
     // Now we know that the array/pointer that GEP1 indexes into and that

 ///
 /// We know that V1 is a GEP, but we don't know anything about V2.
 /// UnderlyingV1 is GetUnderlyingObject(GEP1, DL), UnderlyingV2 is the same for
 /// V2.
 AliasResult BasicAAResult::aliasGEP(
     const GEPOperator *GEP1, LocationSize V1Size, const AAMDNodes &V1AAInfo,
     const Value *V2, LocationSize V2Size, const AAMDNodes &V2AAInfo,
     const Value *UnderlyingV1, const Value *UnderlyingV2, AAQueryInfo &AAQI) {
+  // Don't attempt to decompose GEP for scalable type. GEP index scale is
+  // unknown at compile-time for scalable type.
+  Type *SrcEleTy1 = GEP1->getSourceElementType();
+  Type *SrcEleTy2 = isa<GEPOperator>(V2)
+                        ? cast<GEPOperator>(V2)->getSourceElementType()
+                        : nullptr;
+  if ((SrcEleTy1->isVectorTy() && SrcEleTy1->getVectorIsScalable()) ||
+      (SrcEleTy2 && SrcEleTy2->isVectorTy() &&
+       SrcEleTy2->getVectorIsScalable()))
+    return MayAlias;
+
   DecomposedGEP DecompGEP1, DecompGEP2;
   unsigned MaxPointerSize = getMaxPointerSize(DL);
   DecompGEP1.StructOffset = DecompGEP1.OtherOffset = APInt(MaxPointerSize, 0);
   DecompGEP2.StructOffset = DecompGEP2.OtherOffset = APInt(MaxPointerSize, 0);
 
   bool GEP1MaxLookupReached =
     DecomposeGEPExpression(GEP1, DecompGEP1, DL, &AC, DT);
   bool GEP2MaxLookupReached =

llvm/test/Analysis/BasicAA/vscale.ll

+; RUN: opt < %s -basicaa -aa-eval -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() {
+  %alloc = alloca <vscale x 4 x i32>
+  %gep1 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %alloc, i64 0
+  %gep2 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %alloc, i64 1
+  ret void
+}
+
+; CHECK-LABEL: gep_alloca_const_offset_2
+; CHECK-DAG:  MayAlias:     <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
+; TODO: AliasResult for gep1,gep2 can be improved as MustAlias
+; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %gep1, <vscale x 4 x i32>* %gep2
+define void @gep_alloca_const_offset_2() {
+  %alloc = alloca <vscale x 4 x i32>
+  %gep1 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %alloc, i64 1
+  %gep2 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %alloc, i64 1
+  ret void
+}
+
+; CHECK-LABEL: gep_alloca_const_offset_3
+; CHECK-DAG:  MustAlias:    <vscale x 4 x i32>* %alloc, <vscale x 4 x i32>* %gep1
+; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %alloc, i32* %gep2
+; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %gep1, i32* %gep2
+define void @gep_alloca_const_offset_3() {
+  %alloc = alloca <vscale x 4 x i32>
+  %gep1 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %alloc, i64 0
+  %gep2 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %alloc, i64 0, i64 1
+  ret void
+}
+
+; CHECK-LABEL: gep_alloca_const_offset_4
+; CHECK-DAG:  MustAlias:    <vscale x 4 x i32>* %alloc, <vscale x 4 x i32>* %gep1
+; CHECK-DAG:  MustAlias:    <vscale x 4 x i32>* %alloc, i32* %gep2
+; CHECK-DAG:  MustAlias:    <vscale x 4 x i32>* %gep1, i32* %gep2
+define void @gep_alloca_const_offset_4() {
+  %alloc = alloca <vscale x 4 x i32>
+  %gep1 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %alloc, i64 0
+  %gep2 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %alloc, i64 0, i64 0
+  ret void
+}
+
+; CHECK-LABEL: gep_alloca_symbolic_offset
+; CHECK-DAG:  MayAlias:     <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_symbolic_offset(i64 %idx1, i64 %idx2) {
+  %alloc = alloca <vscale x 4 x i32>
+  %gep1 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %alloc, i64 %idx1
+  %gep2 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %alloc, i64 %idx2
+  ret void
+}
+
+; CHECK-LABEL: gep_same_base_const_offset
+; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %p, i32* %gep1
+; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %p, i32* %gep2
+; TODO: AliasResult for gep1,gep2 can be improved as NoAlias
+; CHECK-DAG:  MayAlias:     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
+  ret void
+}
+
+; CHECK-LABEL: gep_same_base_symbolic_offset
+; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %gep1, <vscale x 4 x i32>* %p
+; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %gep2, <vscale x 4 x i32>* %p
+; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %gep1, <vscale x 4 x i32>* %gep2
+define void @gep_same_base_symbolic_offset(<vscale x 4 x i32>* %p, i64 %idx1, i64 %idx2) {
+  %gep1 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %p, i64 %idx1
+  %gep2 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %p, i64 %idx2
+  ret void
+}
+
+; CHECK-LABEL: gep_different_base_const_offset
+; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %gep1, <vscale x 4 x i32>* %p1
+; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %gep2, <vscale x 4 x i32>* %p2
+; CHECK-DAG:  NoAlias:      <vscale x 4 x i32>* %p1, <vscale x 4 x i32>* %p2
+; CHECK-DAG:  NoAlias:      <vscale x 4 x i32>* %gep1, <vscale x 4 x i32>* %p2
+; CHECK-DAG:  NoAlias:      <vscale x 4 x i32>* %gep2, <vscale x 4 x i32>* %p1
+; CHECK-DAG:  NoAlias:      <vscale x 4 x i32>* %gep1, <vscale x 4 x i32>* %gep2
+define void @gep_different_base_const_offset(<vscale x 4 x i32>* noalias %p1, <vscale x 4 x i32>* noalias %p2) {
+  %gep1 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %p1, i64 1
+  %gep2 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %p2, i64 1
+  ret void
+}
+
+; getelementptr + bitcast
+
+; CHECK-LABEL: gep_bitcast_1
+; CHECK-DAG:   MustAlias:    <vscale x 4 x i32>* %p, i32* %p2
+; CHECK-DAG:   MayAlias:     <vscale x 4 x i32>* %p, i32* %gep1
+; CHECK-DAG:   MayAlias:     i32* %gep1, i32* %p2
+; CHECK-DAG:   MayAlias:     <vscale x 4 x i32>* %p, i32* %gep2
+; 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
+  ret void
+}
+
+; CHECK-LABEL: gep_bitcast_2
+; CHECK-DAG:  MustAlias:    <vscale x 4 x float>* %p2, <vscale x 4 x i32>* %p
+; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %p, i32* %gep1
+; CHECK-DAG:  MayAlias:     <vscale x 4 x float>* %p2, i32* %gep1
+; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %p, float* %gep2
+; CHECK-DAG:  MayAlias:     float* %gep2, i32* %gep1
+; CHECK-DAG:  MayAlias:     <vscale x 4 x float>* %p2, float* %gep2
+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
+  ret void
+}