There is another issue which I tracked down to this patch but it is kind of hidden. In order to reveal the issue please apply attached patch ( that is basically enabling expensive checks and added verifyFunction right after vectorized code generated.

Looks good. Thanks for the fix.

In D127531#3602238, @ABataev wrote:

In D127531#3602215, @vdmitrie wrote:

I'm not sure about how the test case affected supposed to execute the changes.
Could you please consider adding more tests to be clearer about the patch purpose?

It is for compile time mostly, nothing else. Just allows to detect gathered elements before scheduling.

I'm not sure about how the test case affected supposed to execute the changes.
Could you please consider adding more tests to be clearer about the patch purpose?

I guess the "crash" the patch suggested to fix looked like this:
llvm-project/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:8214: llvm::Value* llvm::slpvectorizer::BoUpSLP::vectorizeTree(llvm::slpvectorizer::BoUpSLP::ExtraValueToDebugLocsMap&): Assertion `Vec && "Can't find vectorizable value"' failed.

LG

BTW. One interesting thing I noticed from the test case.
We might want to special case this:

i32 *%addr
%gep3 = getelementptr inbounds i32, i32* %addr, i32 2
%gep5 = getelementptr inbounds i32, i32* %addr, i32 4

...

%gep15 = getelementptr inbounds i32, i32* %addr, i32 14

Test case for collection.

Looks good yo me.
@RKSimon , @ABataev , do you have any comments/objections?

Looks good with a nit.

to reproduce crash: opt -slp-vectorizer -disable-output reduced.ll
Fails on assertion:
... llvm-project/llvm/include/llvm/ADT/DenseMap.h:1244: llvm::DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, IsConst>::value_type* llvm::DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, IsConst>::operator->() const [with KeyT = const llvm::slpvectorizer::BoUpSLP::TreeEntry*; ValueT = llvm::SmallVector<unsigned int, 4>; KeyInfoT = llvm::DenseMapInfo<const llvm::slpvectorizer::BoUpSLP::TreeEntry*, void>; Bucket = llvm::detail::DenseMapPair<const llvm::slpvectorizer::BoUpSLP::TreeEntry*, llvm::SmallVector<unsigned int, 4> >; bool IsConst = false; llvm::DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, IsConst>::pointer = llvm::detail::DenseMapPair<const llvm::slpvectorizer::BoUpSLP::TreeEntry*, llvm::SmallVector<unsigned int, 4> >*; llvm::DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, IsConst>::value_type = llvm::detail::DenseMapPair<const llvm::slpvectorizer::BoUpSLP::TreeEntry*, llvm::SmallVector<unsigned int, 4> >]: Assertion `Ptr != End && "dereferencing end() iterator"' failed.

I'm also observing a stability issue. I'll submit a test case once reduce it.

Hi Alexey. Here is another crash reproducer:

rebased + applied suggestions

https://reviews.llvm.org/D124313 is the NFC split.

In D124309#3469277, @ABataev wrote:

Hi Valery, thanks for the patch. This looks good! Could you split it into 2 patches: one that renames lookahead heuristics (NFC) and the second (functional) one?

Added test description and renamed function as per suggestion.

Thank you Vasileios. Looks good.

I believe https://reviews.llvm.org/D120492 supposed to fix the issue I reported earlier, but that did not happen. The test I've sent earlier is a simplified one. I just slightly modified it to show misbehaving of the reordering.

I have a question wrt this patch. Consider this test case:
define dso_local void @test(i32* noalias nocapture readonly %0, i32* noalias nocapture readonly %1, i32* noalias nocapture %2) {

%4 = getelementptr inbounds i32, i32* %1, i64 0
%5 = load i32, i32* %4, align 4
%6 = getelementptr inbounds i32, i32* %0, i64 0
%7 = load i32, i32* %6, align 4
%8 = getelementptr inbounds i32, i32* %1, i64 4
%9 = load i32, i32* %8, align 4
%10 = getelementptr inbounds i32, i32* %0, i64 4
%11 = load i32, i32* %10, align 4
%12 = getelementptr inbounds i32, i32* %1, i64 1
%13 = load i32, i32* %12, align 4
%14 = getelementptr inbounds i32, i32* %0, i64 1
%15 = load i32, i32* %14, align 4
%16 = getelementptr inbounds i32, i32* %1, i64 5
%17 = load i32, i32* %16, align 4
%18 = getelementptr inbounds i32, i32* %0, i64 5
%19 = load i32, i32* %18, align 4
%20 = getelementptr inbounds i32, i32* %1, i64 2
%21 = load i32, i32* %20, align 4
%22 = getelementptr inbounds i32, i32* %0, i64 2
%23 = load i32, i32* %22, align 4
%24 = getelementptr inbounds i32, i32* %1, i64 6
%25 = load i32, i32* %24, align 4
%26 = getelementptr inbounds i32, i32* %0, i64 6
%27 = load i32, i32* %26, align 4
%28 = getelementptr inbounds i32, i32* %1, i64 3
%29 = load i32, i32* %28, align 4
%30 = getelementptr inbounds i32, i32* %0, i64 3
%31 = load i32, i32* %30, align 4
%32 = getelementptr inbounds i32, i32* %1, i64 7
%33 = load i32, i32* %32, align 4
%34 = getelementptr inbounds i32, i32* %0, i64 7
%35 = load i32, i32* %34, align 4
%36 = sub i32 %33, %31
%37 = sub i32 %36, %35
%38 = add i32 %37, %29
%39 = sub i32 %25, %23
%40 = sub i32 %39, %27
%41 = add i32 %40, %21
%42 = sub i32 %17, %15
%43 = sub i32 %42, %19
%44 = add i32 %43, %13
%45 = sub i32 %9, %7
%46 = sub i32 %45, %11
%47 = add i32 %46, %5
%48 = getelementptr inbounds i32, i32* %2, i64 0
%49 = add i32 %41, %38
%50 = add i32 %49, %47
%51 = add i32 %50, %44
store i32 %51, i32* %48, align 4
%52 = getelementptr inbounds i32, i32* %2, i64 2
%53 = add i32 %47, %44
%54 = sub i32 %53, %38
%55 = sub i32 %54, %41
store i32 %55, i32* %52, align 4
%56 = getelementptr inbounds i32, i32* %2, i64 1
%57 = add i32 %47, %41
%58 = sub i32 %57, %44
%59 = sub i32 %58, %38
store i32 %59, i32* %56, align 4
%60 = getelementptr inbounds i32, i32* %2, i64 3
%61 = sub i32 %38, %44
%62 = sub i32 %61, %41
%63 = add i32 %62, %47
store i32 %63, i32* %60, align 4
ret void

}

https://reviews.llvm.org/rG8e9216fe877c

LG with a nit.

LGTM. Thank you, Alexey.

Hi, there is another issue that can be reproduced with existing test case:

Hi Florian, I just came across this patch. Could you please follow up to update descriptions of some methods that you have updated with the patch?
I did not check the most recent LLVM project version, thus if you see that a comment is irrelevant anymore then disregard it.
Thank you.
Valery

It sounds like throttling patch should resolve this issue as cutting out ScatterVectorize entry with high cost will effectively return to previous behavior.