[SLP]No need to schedule/check parent for extract{element/value} instruction.

[ABataev]

Summary

The instruction extractelement/extractvalue are not required to
be scheduled since they only depend on the source vector/aggregate (with
constant indices), smae applies to the parent basic block checks.
Improves compile time and saves scheduling budget.

[RKSimon]

couple of minors

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

210

Add description comment

212

clang-format has made this pretty messy - maybe split it up?

[ABataev]

Rebase + address comments

[RKSimon]

LGTM cheers

[lebedev.ri]

llvm/test/Transforms/SLPVectorizer/X86/remark_extract_broadcast.ll

19–25

Passing-by remark: i suspect the extract/insert aren't needed here,
the splat/broadcast shuffle can just operate on the load?

[ABataev]

llvm/test/Transforms/SLPVectorizer/X86/remark_extract_broadcast.ll

19–25

Yes, I believe so and hope D107966 will fix it. Will check it later.

[anton-afanasyev]

It looks like this patch causes an issue reported here: https://lists.llvm.org/pipermail/llvm-dev/2021-August/152411.html. Reverting fixes it.

[RKSimon]

In D108703#2974289, @anton-afanasyev wrote:

It looks like this patch causes an issue reported here: https://lists.llvm.org/pipermail/llvm-dev/2021-August/152411.html. Reverting fixes it.

Are you able to see a quick fix? Otherwise we may need to revert and commit the test case for it to be addressed when @ABataev is back.

[anton-afanasyev]

Are you able to see a quick fix? Otherwise we may need to revert and commit the test case for it to be addressed when @ABataev is back.

Yes, I'm looking for a quick fix. I've answered to thread that I'm to revert it if no fix in a short time.

[ABataev]

In D108703#2974303, @anton-afanasyev wrote:

Are you able to see a quick fix? Otherwise we may need to revert and commit the test case for it to be addressed when @ABataev is back.

Yes, I'm looking for a quick fix. I've answered to thread that I'm to revert it if no fix in a short time.

Looks like it crashes on shuffles, just need to add a check for shuffles in assert.

[anton-afanasyev]

Looks like it crashes on shuffles, just need to add a check for shuffles in assert.

No, it crashes on extractelement with non-constant index. I've commented this inline.
The current crash could just be fixed by removing one assert check, but I've found several more minors, so may be it worth to revert? I think this should be recommited with negative tests for extractelement as wel as for insertelement (are we able to schedule insertelement with non-constant index now?)

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

222

Btw, this second ExtractValueInst is redundant, it's checked above.

235

Why do we need this bypass? Looks like this check isn't related to allSameBlock(). One can imagine vector-like-insts with const ops in different BBs. We can explicitly do this check outside allSameBlock() wherever need.

6576

all_of(VL, isVectorLikeInstWithConstOps) should be here instead?

6672

all_of(VL, isVectorLikeInstWithConstOps) should be here instead as well?

6712–6714

We assert here for bundle member not being vector-like-inst-with-const-ops, but check only S.OpValue before in tryScheduleBundle(). Remove this new check?

[ABataev]

In D108703#2974428, @anton-afanasyev wrote:

Looks like it crashes on shuffles, just need to add a check for shuffles in assert.

No, it crashes on extractelement with non-constant index. I've commented this inline.
The current crash could just be fixed by removing one assert check, but I've found several more minors, so may be it worth to revert? I think this should be recommited with negative tests for extractelement as wel as for insertelement (are we able to schedule insertelement with non-constant index now?)

Could you revert the patch and I'll fix it once I'm back from vacation?

[anton-afanasyev]

Could you revert the patch and I'll fix it once I'm back from vacation?

Sure!

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

222

No, it is required and checks for a different thing. It checks that the index is constant for such instructions.

235

Because we don't need to check the parents for such instructions. For InsertsElements it was checked already, for Undefs - no need, for Extracts with constant indices - not required.

6576

No, not needed, just isVectorLikeInstWithConstOps(S.OpValue) is enough. Moreover, if we have inserts/extracts with non-const indices, they should be gathered, we can't vectorize them. Just added a special check in BoUpSLP::buildTree_rec function.

6672

Same as above

6712–6714

No, the assert is correct, we should allow extracts with const indices to be scheduled. It is fixed by the mentioned additional check in BoUpSLP::buildTree_rec

[ABataev]

Fixed handling of the inserts/extracts with non-const indices.

[anton-afanasyev]

Please rebase against llvm/test/Transforms/SLPVectorizer/X86/extract_with_non_const_index.ll commited at aaae726afb0ef.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

222

But you've made check already at line 217, haven't you? Return true for any index if isa<ExtractValueInst>(I).

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

222

Oh, yes, missed that you meant ExtractValueInst. Yes, need to remove the check for ExtractValueInst here, it cannot have non-const indices per LLVM IR specification.

[ABataev]

Removed extra check from the function.

[ABataev]

Rebase

[anton-afanasyev]

In D108703#2999778, @anton-afanasyev wrote:

Please rebase against llvm/test/Transforms/SLPVectorizer/X86/extract_with_non_const_index.ll commited at aaae726afb0ef.

LGTM with minor concerning rebase.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

 /// meaningful vectorization path such as x86_fp80 and ppc_f128. This just
 /// avoids spending time checking the cost model and realizing that they will
 /// be inevitably scalarized.
 static bool isValidElementType(Type *Ty) {
   return VectorType::isValidElementType(Ty) && !Ty->isX86_FP80Ty() &&
          !Ty->isPPC_FP128Ty();
 }
 
+/// \returns True if the value is a constant (but not globals/constant
+/// expressions).
+static bool isConstant(Value *V) {
+  return isa<Constant>(V) && !isa<ConstantExpr>(V) && !isa<GlobalValue>(V);
+}
+
+/// Checks if \p V is one of vector-like instructions, i.e. undef,
+/// insertelement/extractelement with constant indices for fixed vector type or
+/// extractvalue instruction.
+static bool isVectorLikeInstWithConstOps(Value *V) {
+  if (!isa<InsertElementInst, ExtractElementInst>(V) &&
+      !isa<ExtractValueInst, UndefValue>(V))
+    return false;
+  auto *I = dyn_cast<Instruction>(V);
+  if (!I || isa<ExtractValueInst>(I))
+    return true;
+  if (!isa<FixedVectorType>(I->getOperand(0)->getType()))
+    return false;
+  if (isa<ExtractElementInst>(I))
+    return isConstant(I->getOperand(1));
+  assert(isa<InsertElementInst>(V) && "Expected only insertelement.");
+  return isConstant(I->getOperand(2));
+}
+
 /// \returns true if all of the instructions in \p VL are in the same block or
 /// false otherwise.
 static bool allSameBlock(ArrayRef<Value *> VL) {
   Instruction *I0 = dyn_cast<Instruction>(VL[0]);
   if (!I0)
     return false;
+  if (all_of(VL, isVectorLikeInstWithConstOps))
+    return true;
+
   BasicBlock *BB = I0->getParent();
   for (int I = 1, E = VL.size(); I < E; I++) {
     auto *II = dyn_cast<Instruction>(VL[I]);
     if (!II)
       return false;
 
     if (BB != II->getParent())
       return false;
   }
   return true;
 }
 
-/// \returns True if the value is a constant (but not globals/constant
-/// expressions).
-static bool isConstant(Value *V) {
-  return isa<Constant>(V) && !isa<ConstantExpr>(V) && !isa<GlobalValue>(V);
-}
-
 /// \returns True if all of the values in \p VL are constants (but not
 /// globals/constant expressions).
 static bool allConstant(ArrayRef<Value *> VL) {
   // Constant expressions and globals can't be vectorized like normal integer/FP
   // constants.
   return all_of(VL, isConstant);
 }
 
void BoUpSLP::buildTree_rec(ArrayRef<Value *> VL, unsigned Depth,
   if (StoreInst *SI = dyn_cast<StoreInst>(S.OpValue))
     if (SI->getValueOperand()->getType()->isVectorTy()) {
       LLVM_DEBUG(dbgs() << "SLP: Gathering due to store vector type.\n");
       newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx);
       return;
     }
 
   // If all of the operands are identical or constant we have a simple solution.
-  if (allConstant(VL) || isSplat(VL) || !allSameBlock(VL) || !S.getOpcode()) {
+  // If we deal with insert/extract instructions, they all must have constant
+  // indices, otherwise we should gather them, not try to vectorize.
+  if (allConstant(VL) || isSplat(VL) || !allSameBlock(VL) || !S.getOpcode() ||
+      (isa<InsertElementInst, ExtractValueInst, ExtractElementInst>(S.MainOp) &&
+       !all_of(VL, isVectorLikeInstWithConstOps))) {
     LLVM_DEBUG(dbgs() << "SLP: Gathering due to C,S,B,O. \n");
     newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx);
     return;
   }
 
   // We now know that this is a vector of instructions of the same type from
   // the same block.
 
void BoUpSLP::optimizeGatherSequence() {
   GatherSeq.clear();
 }
 
 // Groups the instructions to a bundle (which is then a single scheduling entity)
 // and schedules instructions until the bundle gets ready.
 Optional<BoUpSLP::ScheduleData *>
 BoUpSLP::BlockScheduling::tryScheduleBundle(ArrayRef<Value *> VL, BoUpSLP *SLP,
                                             const InstructionsState &S) {
-  if (isa<PHINode>(S.OpValue) || isa<InsertElementInst>(S.OpValue))
+  // No need to schedule PHIs, insertelement, extractelement and extractvalue
+  // instructions.
+  if (isa<PHINode>(S.OpValue) || isVectorLikeInstWithConstOps(S.OpValue))
     return nullptr;
 
   // Initialize the instruction bundle.
   Instruction *OldScheduleEnd = ScheduleEnd;
   ScheduleData *PrevInBundle = nullptr;
   ScheduleData *Bundle = nullptr;
   bool ReSchedule = false;
   LLVM_DEBUG(dbgs() << "SLP:  bundle: " << *S.OpValue << "\n");
if (!Bundle->isReady()) {
     cancelScheduling(VL, S.OpValue);
     return None;
   }
   return Bundle;
 }
 
 void BoUpSLP::BlockScheduling::cancelScheduling(ArrayRef<Value *> VL,
                                                 Value *OpValue) {
-  if (isa<PHINode>(OpValue) || isa<InsertElementInst>(OpValue))
+  if (isa<PHINode>(OpValue) || isVectorLikeInstWithConstOps(OpValue))
     return;
 
   ScheduleData *Bundle = getScheduleData(OpValue);
   LLVM_DEBUG(dbgs() << "SLP:  cancel scheduling of " << *Bundle << "\n");
   assert(!Bundle->IsScheduled &&
          "Can't cancel bundle which is already scheduled");
   assert(Bundle->isSchedulingEntity() && Bundle->isPartOfBundle() &&
          "tried to unbundle something which is not a bundle");

 }
 
 bool BoUpSLP::BlockScheduling::extendSchedulingRegion(Value *V,
                                                       const InstructionsState &S) {
   if (getScheduleData(V, isOneOf(S, V)))
     return true;
   Instruction *I = dyn_cast<Instruction>(V);
   assert(I && "bundle member must be an instruction");
-  assert(!isa<PHINode>(I) && !isa<InsertElementInst>(I) &&
-         "phi nodes/insertelements don't need to be scheduled");
+  assert(!isa<PHINode>(I) && !isVectorLikeInstWithConstOps(I) &&
+         "phi nodes/insertelements/extractelements/extractvalues don't need to "
+         "be scheduled");
   auto &&CheckSheduleForI = [this, &S](Instruction *I) -> bool {
     ScheduleData *ISD = getScheduleData(I);
     if (!ISD)
       return false;
     assert(isInSchedulingRegion(ISD) &&
            "ScheduleData not in scheduling region");
     ScheduleData *SD = allocateScheduleDataChunks();
     SD->Inst = I;
void BoUpSLP::scheduleBlock(BlockScheduling *BS) {
 
   // Ensure that all dependency data is updated and fill the ready-list with
   // initial instructions.
   int Idx = 0;
   int NumToSchedule = 0;
   for (auto *I = BS->ScheduleStart; I != BS->ScheduleEnd;
        I = I->getNextNode()) {
     BS->doForAllOpcodes(I, [this, &Idx, &NumToSchedule, BS](ScheduleData *SD) {
-      assert((isa<InsertElementInst>(SD->Inst) ||
+      assert((isVectorLikeInstWithConstOps(SD->Inst) ||
               SD->isPartOfBundle() == (getTreeEntry(SD->Inst) != nullptr)) &&
              "scheduler and vectorizer bundle mismatch");
       SD->FirstInBundle->SchedulingPriority = Idx++;
       if (SD->isSchedulingEntity()) {
         BS->calculateDependencies(SD, false, this);
         NumToSchedule++;
       }
     });

llvm/test/Transforms/SLPVectorizer/X86/remark_extract_broadcast.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -mtriple=x86_64-pc-linux-gnu -mcpu=generic -mattr=sse2 -slp-vectorizer -pass-remarks-output=%t < %s -slp-threshold=-2 | FileCheck %s
 ; RUN: FileCheck --input-file=%t --check-prefix=YAML %s
 
 define void @fextr(i16* %ptr) {
 ; CHECK-LABEL: @fextr(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LD:%.*]] = load <8 x i16>, <8 x i16>* undef, align 16
-; CHECK-NEXT:    [[V0:%.*]] = extractelement <8 x i16> [[LD]], i32 0
 ; CHECK-NEXT:    br label [[T:%.*]]
 ; CHECK:       t:
-; CHECK-NEXT:    [[V1:%.*]] = extractelement <8 x i16> [[LD]], i32 1
-; CHECK-NEXT:    [[V2:%.*]] = extractelement <8 x i16> [[LD]], i32 2
-; CHECK-NEXT:    [[V3:%.*]] = extractelement <8 x i16> [[LD]], i32 3
-; CHECK-NEXT:    [[V4:%.*]] = extractelement <8 x i16> [[LD]], i32 4
-; CHECK-NEXT:    [[V5:%.*]] = extractelement <8 x i16> [[LD]], i32 5
-; CHECK-NEXT:    [[V6:%.*]] = extractelement <8 x i16> [[LD]], i32 6
-; CHECK-NEXT:    [[V7:%.*]] = extractelement <8 x i16> [[LD]], i32 7
 ; CHECK-NEXT:    [[P0:%.*]] = getelementptr inbounds i16, i16* [[PTR:%.*]], i64 0
 ; CHECK-NEXT:    [[P1:%.*]] = getelementptr inbounds i16, i16* [[PTR]], i64 1
 ; CHECK-NEXT:    [[P2:%.*]] = getelementptr inbounds i16, i16* [[PTR]], i64 2
 ; CHECK-NEXT:    [[P3:%.*]] = getelementptr inbounds i16, i16* [[PTR]], i64 3
 ; CHECK-NEXT:    [[P4:%.*]] = getelementptr inbounds i16, i16* [[PTR]], i64 4
 ; CHECK-NEXT:    [[P5:%.*]] = getelementptr inbounds i16, i16* [[PTR]], i64 5
 ; CHECK-NEXT:    [[P6:%.*]] = getelementptr inbounds i16, i16* [[PTR]], i64 6
 ; CHECK-NEXT:    [[P7:%.*]] = getelementptr inbounds i16, i16* [[PTR]], i64 7
-; CHECK-NEXT:    [[TMP0:%.*]] = insertelement <8 x i16> poison, i16 [[V0]], i32 0
-; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <8 x i16> [[TMP0]], i16 [[V1]], i32 1
-; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <8 x i16> [[TMP1]], i16 [[V2]], i32 2
-; CHECK-NEXT:    [[TMP3:%.*]] = insertelement <8 x i16> [[TMP2]], i16 [[V3]], i32 3
-; CHECK-NEXT:    [[TMP4:%.*]] = insertelement <8 x i16> [[TMP3]], i16 [[V4]], i32 4
-; CHECK-NEXT:    [[TMP5:%.*]] = insertelement <8 x i16> [[TMP4]], i16 [[V5]], i32 5
-; CHECK-NEXT:    [[TMP6:%.*]] = insertelement <8 x i16> [[TMP5]], i16 [[V6]], i32 6
-; CHECK-NEXT:    [[TMP7:%.*]] = insertelement <8 x i16> [[TMP6]], i16 [[V7]], i32 7
-; CHECK-NEXT:    [[SHUFFLE:%.*]] = shufflevector <8 x i16> [[TMP0]], <8 x i16> poison, <8 x i32> <i32 0, i32 undef, i32 0, i32 0, i32 0, i32 0, i32 0, i32 0>
-; CHECK-NEXT:    [[TMP8:%.*]] = add <8 x i16> [[TMP7]], [[SHUFFLE]]
-; CHECK-NEXT:    [[TMP9:%.*]] = bitcast i16* [[P0]] to <8 x i16>*
-; CHECK-NEXT:    store <8 x i16> [[TMP8]], <8 x i16>* [[TMP9]], align 2
+; CHECK-NEXT:    [[TMP0:%.*]] = extractelement <8 x i16> [[LD]], i32 0
+; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <8 x i16> poison, i16 [[TMP0]], i32 0
+; CHECK-NEXT:    [[SHUFFLE:%.*]] = shufflevector <8 x i16> [[TMP1]], <8 x i16> poison, <8 x i32> <i32 0, i32 undef, i32 0, i32 0, i32 0, i32 0, i32 0, i32 0>
+; CHECK-NEXT:    [[TMP2:%.*]] = add <8 x i16> [[LD]], [[SHUFFLE]]
+; CHECK-NEXT:    [[TMP3:%.*]] = bitcast i16* [[P0]] to <8 x i16>*
+; CHECK-NEXT:    store <8 x i16> [[TMP2]], <8 x i16>* [[TMP3]], align 2
 ; CHECK-NEXT:    ret void
 ;
 ; YAML:      Pass:            slp-vectorizer
 ; YAML-NEXT: Name:            StoresVectorized
 ; YAML-NEXT: Function:        fextr
 ; YAML-NEXT: Args:
 ; YAML-NEXT:   - String:          'Stores SLP vectorized with cost '
-; YAML-NEXT:   - Cost:            '-4'
+; YAML-NEXT:   - Cost:            '-20'
 ; YAML-NEXT:   - String:          ' and with tree size '
 ; YAML-NEXT:   - TreeSize:        '4'
 
 entry:
   %LD = load <8 x i16>, <8 x i16>* undef
   %V0 = extractelement <8 x i16> %LD, i32 0
   br label %t