[SLP]Fix PR57447: Assertion `!getTreeEntry(V) && "Scalar already in tree!"' failed.

[ABataev]

Summary

The pointer operands for the ScatterVectorize node may contain
non-instruction values and they are not checked for "already being
vectorized". Need to check that such pointers are already vectorized and
gather them instead of trying to build vectorize node to avoid compiler
crash.

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

4770

"!I" can be replaced with "!isa<Instruction>(V)"
We already have few places of the same pattern addressing specifically the operand of a ScatterVectorize node: " UserTreeIdx.UserTE && UserTreeIdx.UserTE->State == TreeEntry::ScatterVectorize".
We also define isScatterUser variable at line 5221 with the same value.
I'd suggest to pull the variable definition up and use it instead of the repeating pattern.
The comment before the loop is probably worth updating too.

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

4770

A side note. IMO terminology used here in SLP vectorizer wrt vectorizing non-unit stride loads is really confusing as word "scatter" is typically associated with stores. But I'm not about changing the naming in context of this PR. What I wanted to highlight is that IsScatterUser is also not the best choice for the variable name. It is even more confusing because it sounds like "this VL is a user of ScatterVectorizer node" (which by the way may not have users as loads are terminators) rather than "user of this VL is ScatterVectorize node". It would be nice if you come up with better name for the variable (preferably not having "scatter" in its name).

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

4770

(which by the way may not have users

ignore this part:) My brain again thinking of "stores" when I see "scatter" ))

[ABataev]

Address comment

[vdmitrie]

LG. Thanks!

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

if (IsCommutative) {
                 return findBestRootPair(Cand, LookAheadHeuristics::ScoreSplat);
               }))
         return false;
     }
     return true;
   };
   SmallVector<unsigned> SortedIndices;
   BasicBlock *BB = nullptr;
+  bool IsScatterVectorizeUserTE =
+      UserTreeIdx.UserTE &&
+      UserTreeIdx.UserTE->State == TreeEntry::ScatterVectorize;
   bool AreAllSameInsts =
       (S.getOpcode() && allSameBlock(VL)) ||
-      (S.OpValue->getType()->isPointerTy() && UserTreeIdx.UserTE &&
-       UserTreeIdx.UserTE->State == TreeEntry::ScatterVectorize &&
+      (S.OpValue->getType()->isPointerTy() && IsScatterVectorizeUserTE &&
        VL.size() > 2 &&
        all_of(VL,
               [&BB](Value *V) {
                 auto *I = dyn_cast<GetElementPtrInst>(V);
                 if (!I)
                   return doesNotNeedToBeScheduled(V);
                 if (!BB)
                   BB = I->getParent();
if (TreeEntry *E = getTreeEntry(S.OpValue)) {
     E->UserTreeIndices.push_back(UserTreeIdx);
     LLVM_DEBUG(dbgs() << "SLP: Perfect diamond merge at " << *S.OpValue
                       << ".\n");
     return;
   }
 
   // Check that none of the instructions in the bundle are already in the tree.
   for (Value *V : VL) {
-    auto *I = dyn_cast<Instruction>(V);
-    if (!I)
+    if (!IsScatterVectorizeUserTE && !isa<Instruction>(V))
       continue;
-    if (getTreeEntry(I)) {
+    if (getTreeEntry(V)) {
       LLVM_DEBUG(dbgs() << "SLP: The instruction (" << *V
                         << ") is already in tree.\n");
       if (TryToFindDuplicates(S))
         newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
                      ReuseShuffleIndicies);
       return;
     }
   }
case Instruction::GetElementPtr: {
                      << "SLP: not-vectorizable GEP (different types).\n");
           BS.cancelScheduling(VL, VL0);
           newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
                        ReuseShuffleIndicies);
           return;
         }
       }
 
-      bool IsScatterUser =
-          UserTreeIdx.UserTE &&
-          UserTreeIdx.UserTE->State == TreeEntry::ScatterVectorize;
       // We don't combine GEPs with non-constant indexes.
       Type *Ty1 = VL0->getOperand(1)->getType();
       for (Value *V : VL) {
         auto *I = dyn_cast<GetElementPtrInst>(V);
         if (!I)
           continue;
         auto *Op = I->getOperand(1);
-        if ((!IsScatterUser && !isa<ConstantInt>(Op)) ||
+        if ((!IsScatterVectorizeUserTE && !isa<ConstantInt>(Op)) ||
             (Op->getType() != Ty1 &&
-             ((IsScatterUser && !isa<ConstantInt>(Op)) ||
+             ((IsScatterVectorizeUserTE && !isa<ConstantInt>(Op)) ||
               Op->getType()->getScalarSizeInBits() >
                   DL->getIndexSizeInBits(
                       V->getType()->getPointerAddressSpace())))) {
           LLVM_DEBUG(dbgs()
                      << "SLP: not-vectorizable GEP (non-constant indexes).\n");
           BS.cancelScheduling(VL, VL0);
           newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
                        ReuseShuffleIndicies);

llvm/test/Transforms/SLPVectorizer/X86/scatter-vectorize-reused-pointer.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -slp-vectorizer < %s -mtriple=x86_64-unknown-linux-gnu -mcpu=skylake -slp-threshold=-12 | FileCheck %s
+
+define void @test(i1 %c, ptr %arg) {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF:%.*]], label [[ELSE:%.*]]
+; CHECK:       if:
+; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <4 x ptr> poison, ptr [[ARG:%.*]], i32 0
+; CHECK-NEXT:    [[SHUFFLE:%.*]] = shufflevector <4 x ptr> [[TMP1]], <4 x ptr> poison, <4 x i32> zeroinitializer
+; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr i8, <4 x ptr> [[SHUFFLE]], <4 x i64> <i64 32, i64 24, i64 8, i64 0>
+; CHECK-NEXT:    [[TMP3:%.*]] = call <4 x i64> @llvm.masked.gather.v4i64.v4p0(<4 x ptr> [[TMP2]], i32 8, <4 x i1> <i1 true, i1 true, i1 true, i1 true>, <4 x i64> undef)
+; CHECK-NEXT:    br label [[JOIN:%.*]]
+; CHECK:       else:
+; CHECK-NEXT:    [[ARG_1:%.*]] = getelementptr inbounds i8, ptr [[ARG]], i64 8
+; CHECK-NEXT:    [[TMP4:%.*]] = insertelement <2 x ptr> poison, ptr [[ARG]], i32 0
+; CHECK-NEXT:    [[TMP5:%.*]] = insertelement <2 x ptr> [[TMP4]], ptr [[ARG]], i32 1
+; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr i8, <2 x ptr> [[TMP5]], <2 x i64> <i64 32, i64 24>
+; CHECK-NEXT:    [[TMP7:%.*]] = insertelement <4 x ptr> poison, ptr [[ARG]], i32 3
+; CHECK-NEXT:    [[TMP8:%.*]] = shufflevector <2 x ptr> [[TMP6]], <2 x ptr> poison, <4 x i32> <i32 0, i32 1, i32 undef, i32 undef>
+; CHECK-NEXT:    [[TMP9:%.*]] = shufflevector <4 x ptr> [[TMP7]], <4 x ptr> [[TMP8]], <4 x i32> <i32 4, i32 5, i32 2, i32 3>
+; CHECK-NEXT:    [[TMP10:%.*]] = insertelement <4 x ptr> [[TMP9]], ptr [[ARG_1]], i32 2
+; CHECK-NEXT:    [[TMP11:%.*]] = call <4 x i64> @llvm.masked.gather.v4i64.v4p0(<4 x ptr> [[TMP10]], i32 8, <4 x i1> <i1 true, i1 true, i1 true, i1 true>, <4 x i64> undef)
+; CHECK-NEXT:    br label [[JOIN]]
+; CHECK:       join:
+; CHECK-NEXT:    [[TMP12:%.*]] = phi <4 x i64> [ [[TMP3]], [[IF]] ], [ [[TMP11]], [[ELSE]] ]
+; CHECK-NEXT:    ret void
+;
+  br i1 %c, label %if, label %else
+
+if:
+  %i2.0 = load i64, ptr %arg, align 8
+  %arg2.1 = getelementptr inbounds i8, ptr %arg, i64 8
+  %i2.1 = load i64, ptr %arg2.1, align 8
+  %arg2.2 = getelementptr inbounds i8, ptr %arg, i64 24
+  %i2.2 = load i64, ptr %arg2.2, align 8
+  %arg2.3 = getelementptr inbounds i8, ptr %arg, i64 32
+  %i2.3 = load i64, ptr %arg2.3, align 8
+  br label %join
+
+else:
+  %i.0 = load i64, ptr %arg, align 8
+  %arg.1 = getelementptr inbounds i8, ptr %arg, i64 8
+  %i.1 = load i64, ptr %arg.1, align 8
+  %arg.2 = getelementptr inbounds i8, ptr %arg, i64 24
+  %i.2 = load i64, ptr %arg.2, align 8
+  %arg.3 = getelementptr inbounds i8, ptr %arg, i64 32
+  %i.3 = load i64, ptr %arg.3, align 8
+  br label %join
+
+join:
+  %phi.3 = phi i64 [ %i2.3, %if ], [ %i.3, %else ]
+  %phi.2 = phi i64 [ %i2.2, %if ], [ %i.2, %else ]
+  %phi.1 = phi i64 [ %i2.1, %if ], [ %i.1, %else ]
+  %phi.0 = phi i64 [ %i2.0, %if ], [ %i.0, %else ]
+  ret void
+}
+