It has been moved to github, please continue to review, thank you.
https://github.com/llvm/llvm-project/pull/67812

LG, thanks.

In D150851#4648808, @artagnon wrote:

I've looked at this patch several times, and applied it locally and played with it. I might not be the most qualified reviewer, but this patch is ready to land in my opinion. If anyone has any objections, please raise them now.

Rebase.

ping

Remove the unused parameter Prev in RecurrenceDescriptor::isFindLastIVPattern.

@michaelmaitland Yes, with this example, the your transformation is possible.
However, this still remains a challenge that vectorizers need to address because we cannot restrict the input IR that goes into opt.
Therefore, I have provided a new case -- @select_i32_from_icmp_non_const_same_inputs:

Add test case @select_i32_from_icmp_non_const_same_inputs.

Changes:

• Rebase
• Format some code
• New test cases @not_vectorized_select_icmp_const_cmp_in_recurrence and @not_vectorized_select_icmp_cmp_in_recurrence in Transforms/LoopVectorize/iv-select-cmp.ll.
• Not allow the inclusion of cmp instructions in FindLast recurrence, as I mentioned in the pre-commit revision D157375. The examples are @not_vectorized_select_icmp_const_cmp_in_recurrence and @not_vectorized_select_icmp_cmp_in_recurrence in Transforms/LoopVectorize/iv-select-cmp.ll.

Thanks for Florian's reminder!
Rebase and clang-format it again.

In D157375#4591459, @fhahn wrote:

I think it makes sense to have a test like this in any case to make sure it is handled correctly.

Ping

Corrected the debug message in test case.

Rebase.

Minor changes. Remove the changes that should not be in this patch.

Rebase, and here is a summary of the changes:

Rebase, and update the comment.

Change:

• Replaced all SelectCmp.* with AnyOf.*
• Fixed comments.

Fixed typo.

In D150851#4542688, @Joe wrote:

3. Only target induction variables that determine the branch condition in the loop latch. With this approach, we can indirectly determine whether the induction variable is signed using loop guards, and directly perform vectorization according to the signed overflow is undefined behavior.

@Mel-Chen I like this option. But I don't think I understand fully - what's the purposes of determining whether the induction variable is signed?

In D150851#4535194, @artagnon wrote:

Thanks for the detailed thoughts, Mel! My initial reaction is that (2) is probably unworkable due to the fallout, and that (3) isn't general enough. I'm leaning towards trying out (1) -- I'll see how that works out over the next few days.

Rebase and update according to comments.

LG

Based on my response https://reviews.llvm.org/D150851#4531155, do you have any thoughts?
If you choose option 3, this patch can be landed.
If you choose option 1, this case can be cleaned up into three blocks: entry, for.body, and exit.
If you choose option 2, then this test case is not needed.

Update the patch according to the comments.

In D150851#4528089, @artagnon wrote:

In D150851#4523028, @artagnon wrote:

May I suggest using the logic outlined in isInductionMinMaxPattern in D152693?

It's not that simple, as you'd lose the information about hasNoSignedWrap from the AR of the trunc. I've also been playing with attempting to extend this patch to the decreasing IV case, and it seems we've painted ourselves into a corner by being more concerned about the codegen performance than the generality of the patch: the constant IV start is a serious limitation when looking at the decreasing IV case. I think other reviewers like @fhahn and @Ayal have also expressed interest in greater generality (perhaps at the cost of codegen performance).

Changes:

• Rename Select[I|F]Cmp to [I|F]AnyOf
• Rename SelectIV[I|F]Cmp to [I|F]FindLastIV

Changes:

• Drop the suffix of variable name
• Replace select_icmp_const_3 with select_icmp_const_3_variable_rdx_start
• Replace %ii with %rdx.start

Rebase.

Changes:

• Replace select_icmp_min_iv_start_value with select_icmp_min_valid_iv_start

Rebase.

ping

Changes:

• Change the name of phi
• Add a negative test case

In D150851#4480526, @artagnon wrote:

Yes, I can confirm that there is indeed a bug. Thanks for catching it! I'm thinking about a fix now.

In D150851#4480316, @artagnon wrote:

Would be good to try and find more accurate names than using Select*Cmp combinations. A Compare-Select pattern is also used in the existing Min/Max reduction, but has a much better name.

I agree with @Ayal: I also got confused by the SelectCmp naming convention initially. Perhaps [I|F]AnyOfInv, [I|F]AnyOfInc, and [I|F]AnyOfDec, and rename the corresponding function isAnyOfReduction? I don't have a strong preference for the rename.

ping

Update: I could found an example where the approach in D152693 lead to incorrect result:
Assuming start_value is 3, and red_part is {0, 1, 2, 3} in the end. If the 3 is updated from the loop, not from the start_value , red should be 3 instead of 2.

In D150851#4467261, @Ayal wrote:

Would be good to try and find more accurate names than using Select*Cmp combinations. A Compare-Select pattern is also used in the existing Min/Max reduction, but has a much better name.

Changes:

• Update comments. (Artagnon and Shiva's comments)

Changes:

• Fix the test cases, D154415. (Ayal's comment)

In D150851#4440545, @Ayal wrote:

A selecting reduction could report the index of the value reduced in addition to the value itself. If the reduced value appears multiple times, the index of the first or last appearance can be reported. Tests for such MinLast cases, aka argmin, were introduced in 4f04be564907f, and are yet to be vectorized by LV - hope this patch helps us get there! These are compound patterns combining three header phi's: an induction and two reductions.

I'm glad that others have also noticed this, especially the implementation of the select-cmp pattern for decreasing induction variables. The select-cmp pattern for decreasing induction variables is a function that I haven't implemented yet. Have you come across any real applications or benchmarks that make use of it.

Changes:

• Remove the redundant comment. (fhahn's comment)
• Separate testing and implementation. (fhahn's comment)

Changes:

• Format and minor fix

Changes:

• Add test cases
• Check the bound of increasing induction variable

Changes:

• Split SelectIVICmp and SelectIVFCmp out
• Add Comment
• Minor refine the code

Update commit log.