[LoopVectorize] Vectorize select-cmp reduction pattern for increasing integer induction variable

[Mel-Chen]

Summary

Consider the following loop:

int red = ii;
for (int i = 0; i < n; ++i)
  red = (a[i] > b[i]) ? i : red;

We can vectorize this loop if i is an increasing induction variable.
The final reduced value will be tha maximum of i that the condition
a[i] > b[i] is satisfied, or the start value ii.

This patch added new RecurKind enums - IFindLastIV and FFindLastIV.

TODOs:

• Casting increasing induction variable, like truncate, SExt.

[Mel-Chen]

Changes:

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

[fhahn]

llvm/include/llvm/Analysis/IVDescriptors.h

57

To keep the diff more compact, could you split the FP handling off? It also looks like codegen is at least not tested for the FP case?

llvm/lib/Analysis/IVDescriptors.cpp

674

Do we need to distinguish here between no signed/no unsigned wrap and then chose smax/umax during codegen?

llvm/lib/Transforms/Utils/LoopUtils.cpp

1089

What does this mean? The current patch only handles increasing inductions, so there's no mis-compile that needs fixing here( which the comment kind-of implies)?

llvm/test/Transforms/LoopVectorize/iv-select-cmp-no-wrap.ll

1 ↗

(On Diff #526982)

Could you submit the tests separately?

[Mel-Chen]

llvm/include/llvm/Analysis/IVDescriptors.h

57

I am afraid there is misunderstanding.
The test functions starting with "@select_fcmp" are testing the SelectIVFCmp reduction pattern. SelectIVFCmp is similar in semantics to SelectFCmp, where the operand types of the select instruction are integer, and the cmp instruction is fcmp.

llvm/lib/Analysis/IVDescriptors.cpp

674

That's a good point. Implementing the patch for both signed and unsigned induction variables can be challenging in practice.
The current patch only focuses on the signed IV because in most applications, we often encounter induction variables in the form of IV {0, +, step}. When the IV is signed, we can use -1 or the minimum value of the signed data type as a sentinel value. However, when the IV is unsigned, we don't have a value smaller than 0 to use. This doesn't mean that unsigned IV cannot be vectorized, but rather they require additional handling and a more refined approach.

Of course, if an unsigned IV is {1, +, step}, we can directly use the method implemented in this patch. However, such cases are less common, so we decided to focus on handling signed IV first.

llvm/lib/Transforms/Utils/LoopUtils.cpp

1089

My bad. This maybe the note I leave when I implemented this patch. Will Remove it.

llvm/test/Transforms/LoopVectorize/iv-select-cmp-no-wrap.ll

1 ↗

(On Diff #526982)

Sure. Will do.

[artagnon]

llvm/lib/Analysis/IVDescriptors.cpp

613–633

Please update these comments.

661

Why not split this out into its own function?

663–671

We should forbid these cases in the first place instead of checking them.

674

Doesn't the InstDesc tell you if it's signed or unsigned?

677–679

Why is this necessary? Even if it isn't the min signed value, we should codegen just fine, as the codegen just involves applying a mask and applying max/min-reduce.

681–682

getStepRecurrence() from the SCEV AddRec, instead of relying on isInductionPhi()?

llvm/lib/Transforms/Utils/LoopUtils.cpp

1090

Personally, I prefer straight-line codegen as I've done, but I'm probably biased.

[artagnon]

llvm/include/llvm/Analysis/IVDescriptors.h

55–57

Maybe have a max in the name to make it clear that we only do max-reductions?

[shiva0217]

llvm/include/llvm/Transforms/Utils/LoopUtils.h

361–364

or an increasing loop induction variable?

llvm/lib/Transforms/Utils/LoopUtils.cpp

1164

It might be worth to have a comment to describe that the SelectIVICmp and SelectIVFCmp code generation will use Identity value to determine the if condition in the following case has ever been true.

int r = 331;
for (int i = 0; i < n; i++)
  if (src[i] > 111)
    r = i;

When the reduction value(Rdx) equal to the Identity value(Iden), it reveals the condition never been true. So it will select the InitVal.

It might be the reason that in IsIncreasingLoopInduction, the function will check the IV start value to avoid the IV overlapping the Identity value.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4003

Could the function rename to createSelectIVCmpTargetReduction and be called from createSelectCmpTargetReduction?
Perhaps CreateIntMaxReduce can be moved to the function?

llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp

1265

Perhaps a comment to describe that SelectIVICmp and SelectIVFCmp will initial the reduction PHI with Iden and createSentinelValueHandling will use Iden to determine the if condition in the loop has ever been true?

[Ayal]

An important step forward - adding some general thoughts and terminology, going (admittedly nearly two years) back to D108136.

This FindLast compound pattern combines two header phi's: an induction and a reduction. The reduction is a "selecting reduction" which choses one element from the reduced set, or none. The induction is recorded to return the index of the (last) element found. The induction must be monotone and have some out-of-bounds value, which this patch ensures by restricting to signed inductions that start at non-min-signed-value and increase w/o wrapping - restrictions which can be lifted.

Reducing a collection C of values into one value v can be classified as either a "selecting reduction" or a "combining reduction", depending on whether v is always a member of C or not, respectively. Min and max reductions are selecting reductions whereas add (including fmuladd), multiply, or, and, xor are in general combining reductions.
When C is a collection of boolean values, the selecting reductions "max" and "min" practically compute Any and All, respectively, as in std::any_of() and std::all_of(). Support for boolean selecting reductions was introduced in D108136, which should arguably be called [I|F]Any rather than Select[I|F]Cmp. The boolean values produced by Integer/Float Compares such as "(src[i] > 3)" or "(a[i] > b[i])" are essentially being "max" reduced; any desired pair of invariant return values can be set/selected after determining the outcome of the boolean reduction.
Note that an Any reduction can terminate once "true" is encountered, similar to a general max/min reduction encountering max/min-value.

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.

A boolean selecting max/Any reduction reporting the index is typically interested in the index only if the reduced value is 1/"true", otherwise the index is obvious.
This patch deals with boolean selecting Any reductions that report the index of the (last) value reduced, provided it is "true", and may be called FindLast, as in std::find_if() being FindFirst.

When vectorizing and/or unroll-and-interleaving a selecting reduction with index, the indices of multiple candidates need to be compared to determine which is first (or last), during the reduction epilog (for in-loop reductions this is trivial). This comparison requires the indices to be monotone, i.e., to avoid wrapping.
When dealing with Any reductions with index of "true" values, the indicator that a "true" value was encountered can be folded together with the index found so far (of a true value) by using an "invalid" out-of-bounds index - preferably smaller than first iteration for FindLast or larger than last iteration for FindFirst. Such values are overwritten naturally by the (valid) index of any "true" value, when selecting the first or last index. This reduces the pattern to consider a single reduction (of the combined index+indicator value) rather than the two reductions of the general MaxLast case (of index and value).

This FindLast patch currently meets these requirements by restricting to indices that are increasing, signed, and start from a non-min-signed value. It seems unnatural for such indices to wrap, or if PSCEV guards against AddRec wrapping in general(?), but even if an index may wrap and/or does not provide desired out-of-bounds values, a designated IV counting vector iterations could be used from which the original indices can later be reconstructed in the epilog and reduced. Such an IV is immune to wrapping and provides out-of-bound values. This is one of several possible ways to lift these restrictions.

Note that Any reductions reporting the first index can terminate once "true" is encountered, but seem more cumbersome to write (w/o a break), e.g.,:

// FindFirst w/o break.
int red = ii;
int red_set = false;
for (int i = 0; i < n; ++i)
  if (a[i] > b[i]) {
    red = red_set ? red : i;
    red_set = true;
  }

instead of

// FindLast.
int red = ii;
for (int i = 0; i < n; ++i)
  red = (a[i] > b[i]) ? i : red;

A FindLast loop could be optimized into a FindFirst one by reversing the loop.

llvm/test/Transforms/LoopVectorize/select-min-index.ll

89

This test now gets vectorized, being a FindLast loop that reports the last index where a[i] < a[i-1]+1, or zero if none are found. (I.e., proving that a sequence is not strictly increasing, rather than computing MinLast.)
But the vector loop is never reached?

[Mel-Chen]

Changes:

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

[Mel-Chen]

llvm/include/llvm/Analysis/IVDescriptors.h

55–57

It has some functional overlap with max reduction, but it is not exactly the same as max reduction.
If we were to rename it, the change I suggest is:
SelectICmp --> SelectInvICmp
SelectFCmp --> SelectInvFCmp
SelectIVICmp --> SelectIncIVICmp
SelectIVFCmp --> SelectIncIVFCmp
This will also make it easier for you to expand it in the future.

llvm/lib/Analysis/IVDescriptors.cpp

613–633

Nice catch! Will update it.

661

I'm also think about this because I personally feel that this function is a bit long.
Do you think it's better to put it here as a static function, or put it in another file?

663–671

I do not understand. I believe this series of checks already forbids these cases.

674

No, it does not provide signed or unsigned information.

677–679

This is complicated, let me explain why this pattern requires this check.
It is related to our goals: 1) We want to achieve the reduction with one reduce intrinsic. 2) We want to use a static sentinel value.

About 1), , I understand that even without checking the boundaries or ensuring the select operand is increasing or decreasing, we could still vectorize it by using two reductions. However, the most common format we encounter for induction variables is {0, +, 1}. If this IV is signed, we can accomplish the reduction in one reduction. Therefore, this is based on performance considerations.

As for 2), it follows the decision made in 1), which requires us to have a sentinel value. In the case of an increasing IV, the only restriction on the sentinel value is that it must be less than the start value of the IV. In the case of {0, +, 1}, the sentinel value can be -1 or a smaller value, i.e. dynamic sentinel value. However, for easier implementation, we finally decided to use a static sentinel value, which is the minimum value of the data type.

Additional description: If we were to use a dynamic sentinel value, it would involve checking whether the data type can represent IV start value - step (in the case of {0, +, 1}, it would be -1). However, within the LLVM framework, I currently don't have a way to implement a version with a dynamic sentinel value, which is a room for potential improvement.

681–682

Why? What are the shortcomings that make you think isInductionPHI should not be used?
In my mind, better to rely on the existing function rather than trying to reimplement it.

llvm/lib/Transforms/Utils/LoopUtils.cpp

1090

I don't get it. Only one I need is creating a signed max reduce.

[Mel-Chen]

llvm/include/llvm/Transforms/Utils/LoopUtils.h

361–364

Good find! Will correct it.

llvm/lib/Transforms/Utils/LoopUtils.cpp

1164

Sure, will do.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4003

I'm afraid I won't be able to meet this requirement. Placing createSentinelValueHandling in this position is for handling the case when the vector width is 1. You could refer to CHECK-VF1IC4 in the test cases and focus on the middle.block. In implementation, VF1IC4 doesn't call createTargetReduction, but ReducedPartRdx still need to be did the sentinel value fixing.

However, perhaps we can create a new bool function for RK == RecurKind::SelectIVICmp || RK == RecurKind::SelectIVFCmp. This will most likely expand further and cause the if-condition to become too long.

llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp

1265

Sure, will do.

[Mel-Chen]

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.

Yes, this patch was separated from the D143465 based on @fhahn's suggestion. D143465 still need to be refined, so it hasn't been invited to more reviewers yet.

This FindLast patch currently meets these requirements by restricting to indices that are increasing, signed, and start from a non-min-signed value. It seems unnatural for such indices to wrap, or if PSCEV guards against AddRec wrapping in general(?), but even if an index may wrap and/or does not provide desired out-of-bounds values, a designated IV counting vector iterations could be used from which the original indices can later be reconstructed in the epilog and reduced. Such an IV is immune to wrapping and provides out-of-bound values. This is one of several possible ways to lift these restrictions.

This comment inspired me deeply. Let me share my thoughts and plans regarding the select-cmp reduction pattern (referred to as [I|F]Any mentioned in your comment) .

I believe that the select-cmp reduction pattern can be classified into several types based on the selecting variable. Currently, I have categorized them as follows:

1. Select operand is a loop invariant, i.e., Select[I|F]Cmp. This has already been implemented in the D108136 by @david-arm.

2. Select operand is a monotonic increasing/decreasing induction variable, and the start value of the induction variable is not equal to the minimum/maximum value of the data type. This patch handles the case of signed increasing induction variables, while the case of decreasing induction variables is yet to be implemented. The decision to only handle signed variables depends on LLVM's design, the issue including the choice of sentinel values, and the selection of umax|smax reduction intrinsics. If the compiler architecture allows distinguishing between signed and unsigned, the unsigned induction variable case should be easily achievable.

3. Select operand is a monotonic increasing/decreasing induction variable, and there are no restrictions on the start value of the induction variable.

unsigned int red = start_value;
for (unsigned int i = 0; i < n; ++i)
  red = (a[i] > b[i]) ? i : red;

4. Select operand is an any variable.

int red = start_value;
for (int i = 0; i < n; ++i)
  red = (a[i] > b[i]) ? c[i] : red;

Both 1) and 2) can be handled with a single reduction. On the other hand, 3) and 4) are more complex, and require two reductions to be completed.

Although all select-cmp reduction patterns can be vectorized using the vectorization approach in 4), for performance, I believe that the cases in 1) and 2) should be handled with a single reduction first. Therefore, when identifying and classifying the RecurKind for select-cmp reduction patterns, it is preferable to first consider whether they can be handled with cases 1) or 2), and then consider whether cases 3) or 4) need to be applied.

Next, let's discuss cases 3) and 4), which have not been implemented yet.

For case 3), I currently have two approaches to solve it. The first approach is to perform reduction not only on the select part, but also on the boolean value of the cmp operation.

unsigned int red = start_value;
vec_bool cmp_red_part = splat(false);
vec_unsigned_int select_red_part = splat(DTypeMin);
vec_unsigned_int step_vec = {0, 1, 2, ...};
for (unsigned int i = 0; i < n; i+=vl) {
  cmp_red_part = cmp_red_part | (vec_a[i] > vec_b[i]);
  select_red_part = (vec_a[i] > vec_b[i]) ? step_vec: select_red_part;
  step_vec += {vl, vl, vl, ...};
}
bool cmp_red = reduce.or(cmp_red_part);
red = cmp_red ? reduce.smax|umax(select_red_part) : start_value;

The second approach is to directly use the vectorization approach in 4) to vectorize case 3).

int red = start_value;
vec_unsigned_int iter_red_part = splat(0);
vec_unsigned_int red_part = splat(start_value);
vec_unsigned_int step_vec = {0, 1, 2, ...};
for (int i = 0; i < n; i+=vl) {
  iter_red_part = (vec_a[i] > vec_b[i]) ? step_vec : iter_red_part;
  red_part = (vec_a[i] > vec_b[i]) ? vec_c[i] : red_part;
  step_vec += {vl, vl, vl, ...};
}
unsigned int iter_red = reduce.umax(iter_red_part);
mask_bool red_mask = (iter_red_part == splat(iter_red));
red = reduce.or(red_part, red_mask);  // unsure about which reduction operation would be best for the extracting the result at the position red_mask indicated so far

Both approaches require two reductions, and one of the reductions will be a reduction phi that does not appear in the original user code. In other words, the vectorizer needs to have the capability to create a new reduction phi.

These are my thoughts on the select-cmp reduction pattern so far.

Note that Any reductions reporting the first index can terminate once "true" is encountered, but seem more cumbersome to write (w/o a break), e.g.,:

// FindFirst w/o break.
int red = ii;
int red_set = false;
for (int i = 0; i < n; ++i)
  if (a[i] > b[i]) {
    red = red_set ? red : i;
    red_set = true;
  }

instead of

// FindLast.
int red = ii;
for (int i = 0; i < n; ++i)
  red = (a[i] > b[i]) ? i : red;

A FindLast loop could be optimized into a FindFirst one by reversing the loop.

Interesting, I haven't thought about FindFirst yet. If it includes a break statement, it will be another long story - uncountable loop vectorization. Although I haven't deeply considered the FindFirst case, I still have some rough ideas to share.

Perhaps we can simplify the FindFirst w/o break example to:

// FindFirst w/o break.
int red = ii;
int red_set = false;
for (int i = 0; i < n; ++i) {
  if ((a[i] > b[i]) && !red_set)   // reduction 1
    red = i;
  if (a[i] > b[i]) // reduction 2
    red_set = true;
}

In this way, we can clearly see that there are two reductions involved, and the result of one reduction will be masked by the result of the other reduction. This is very interesting, and may similar with the pattern in D143465.
If we can transform the code into:

// FindFirst w/o break.
int red = ii;
int red_set = false;
for (int i = 0; i < n; ++i){
  if ((a[i] > b[i]) && !red_set)   // reduction 1
    red = i;
  red_set = red_set | (a[i] > b[i]);  // reduction 2
}

, perhaps it will lead to better optimization results.

llvm/test/Transforms/LoopVectorize/select-min-index.ll

89

Impressive catch!
We have been focusing only on the vector.body and ignoring the others. I will prioritize clarifying this bug and fixing it as soon as reasonable.

[Ayal]

In D150851#4458987, @Mel-Chen wrote:

[snip]

I believe that the select-cmp reduction pattern can be classified into several types based on the selecting variable. Currently, I have categorized them as follows:

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.

1. Select operand is a loop invariant, i.e., Select[I|F]Cmp. This has already been implemented in the D108136 by @david-arm.

and should be renamed [I|F]Any or something else more accurate. The two invariant operands should be sunk and selected after the loop, according to the outcome if "any" were found or not.

2. Select operand is a monotonic increasing/decreasing induction variable, and the start value of the induction variable is not equal to the minimum/maximum value of the data type. This patch handles the case of signed increasing induction variables, while the case of decreasing induction variables is yet to be implemented. The decision to only handle signed variables depends on LLVM's design, the issue including the choice of sentinel values, and the selection of umax|smax reduction intrinsics. If the compiler architecture allows distinguishing between signed and unsigned, the unsigned induction variable case should be easily achievable.

3. Select operand is a monotonic increasing/decreasing induction variable, and there are no restrictions on the start value of the induction variable.

unsigned int red = start_value;
for (unsigned int i = 0; i < n; ++i)
  red = (a[i] > b[i]) ? i : red;

4. Select operand is an any variable.

int red = start_value;
for (int i = 0; i < n; ++i)
  red = (a[i] > b[i]) ? c[i] : red;

Both 1) and 2) can be handled with a single reduction. On the other hand, 3) and 4) are more complex, and require two reductions to be completed.

Arguably, (2), (3) and (4) are essentially all FindLast reductions, interested in the last loop iteration i for which some predicate p(i) such as a[i]-b[i]>0 holds, plus an indicator if no such iteration was found, followed by some post-processing of these results: in (2), (3) and (4), if no such iteration was found then some invariant "start_value" is returned, regardless if it was originally out-of-bounds or not. In (4), in addition, if a loop iteration i was found satisfying p(i), some f(i) computation of the last such i should be returned, as in c[i]. This is analogous to sinking the invariants of case (1), and may indeed be more elaborate, but also covers simpler cases such as any (other) AddRec/IV that can be evaluated given i, e.g.,: red = (a[i] > b[i]) ? 3*i+8 : red; - so chose any IV you prefer, e.g., one which has the desired no-wrap plus out-of-bound value, even if the original one does not.

In any case, it should be helpful to distill what actually needs to be maintained throughout the reduction loop, even if more appear there originally; be it boolean indicators in Any reductions (cmp_red_part in your example), indices in Find reductions (select_red_part in your example initialized with "unfound" out-of-bound indicators), or compound value+index in e.g. min/max-with-index reductions. The compiler can surely and does introduce new phi's as needed, hopefully having minimal width, but could also try to eliminate existing phi's and reduce the number of values that are live-out of the loop, possibly at the cost of replicating code, e.g., if c[i] is also used inside the loop.

Here's a sketch minimizing the size of the indices maintained throughout the loop, so they would avoid wrapping, provide out-of-bound values, and possibly use narrower types depending on trip-count and vl:

return_type FindLast(return_type unfound_value, vec_predicate_func, found_func) {
  vec_unsigned_int select_red_part = splat(0); // Zero indicates unfound.
  vec_unsigned_int step_vec = splat(1); // Count vector iterations starting at 1.

  for (unsigned int i = 0; i < n; i+=vl, step_vec+=splat(1))
    select_red_part = (vec_predicate_func(i) ? step_vec : select_red_part;

  unsigned vec_indices_ored = reduce.or(select_red_part);
  if (vec_indices_ored == 0)
    return unfound_value;
  unsigned inflated_red_part = (select_red_part - splat(1)) * vl + <0,1,...,vl-1>;
  unsigned last_index = reduce.umax(inflated_red_part);
  return found_func(last_index);
}

Regarding FindFirst, indeed the natural way of writing it with a break would provide the compiler with an uncountable loop that is harder to vectorize due to speculative execution, and so it is natural to start with FindLast. But if written as a countable loop the compiler might be able to vectorize and optimize it by introducing a break. As in an [I|F]Any countable loop that if free of any other side-effects, or a FindLast loop that can be reversed into a FindFirst loop moving backwards and breaking on first finding.

[Mel-Chen]

Changes:

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

[Mel-Chen]

llvm/test/Transforms/LoopVectorize/select-min-index.ll

89

Clarified, it has been confirmed that this is not a bug.
The reason is that the loop trip count in the test case is 0, causing the simplification of min.iters.check to be true. The test case has been fixed in D154415.

[Mel-Chen]

Changes:

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

[Mel-Chen]

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.

Sure, perhaps @artagnon can join the discussion as well. Let me share my experience first: In GCC, I have seen a classification called ExtractLast, which has a similar semantics to what you mentioned as FindLast. Welcome further input and opinions.

1. Select operand is a loop invariant, i.e., Select[I|F]Cmp. This has already been implemented in the D108136 by @david-arm.

and should be renamed [I|F]Any or something else more accurate. The two invariant operands should be sunk and selected after the loop, according to the outcome if "any" were found or not.

How about following the C++ STL, renaming it to [I|F]AnyOf? What do you think, @david-arm?

Here's a sketch minimizing the size of the indices maintained throughout the loop, so they would avoid wrapping, provide out-of-bound values, and possibly use narrower types depending on trip-count and vl:

return_type FindLast(return_type unfound_value, vec_predicate_func, found_func) {
  vec_unsigned_int select_red_part = splat(0); // Zero indicates unfound.
  vec_unsigned_int step_vec = splat(1); // Count vector iterations starting at 1.

  for (unsigned int i = 0; i < n; i+=vl, step_vec+=splat(1))
    select_red_part = (vec_predicate_func(i) ? step_vec : select_red_part;

  unsigned vec_indices_ored = reduce.or(select_red_part);
  if (vec_indices_ored == 0)
    return unfound_value;
  unsigned inflated_red_part = (select_red_part - splat(1)) * vl + <0,1,...,vl-1>;
  unsigned last_index = reduce.umax(inflated_red_part);
  return found_func(last_index);
}

If we focus on removing the wrapping and bound restrictions, I think we can consider the approach proposed by @artagnon in D152693. This method cleverly extends the technique used by @david-arm in SelectICmp. The approach can be summarized as follows:
Consider the loop:

unsigned int red = start_value;
for (unsigned int i = 0; i < n; ++i)
  red = (a[i] > b[i]) ? i : red;

vectorize to:

unsigned int red = start_value;
vec_unsigned_int red_part = splat(start_value);
vec_unsigned_int step_vec = {0, 1, 2, ...};
for (unsigned int i = 0; i < n; i+=vl) {
  red_part = (vec_a[i] > vec_b[i]) ? step_vec : red_part;
  step_vec += {vl, vl, vl, ...};
}
vec_bool ne_start_value = red_part != splat(start_value);
bool may_update = reduce.or(ne_start_value);
vec_unsigned_int masked_red_part = ne_start_value ? red_part : splat(DataTypeMin);
red = may_update ? reduce.smax|umax(masked_red_part) : start_value;

While the conditions checked in this patch are more strict, I believe both approaches should coexist. In general, the IR generated by this patch should have better performance in the same case. Therefore, it should be prioritized when possible. However, when the cases that cannot be handled by this patch, we can apply the approach in D152693.
In addition, there is still room for optimization in this patch. We usually face source code like this:

j = -1;
for (int i = 0; i < n; i++) {
    if (a[i] < b[i]) {
        j = i;
    }
}

When the start value of the reduction is a known constant and is known to be smaller than the start value of the increasing induction variable, we may not even need to use a sentinel value. Simply using the reduce max operation would suffice.

[Mel-Chen]

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.

@artagnon, could you please help to verify it?

If we focus on removing the wrapping and bound restrictions, I think we can consider the approach proposed by @artagnon in D152693. This method cleverly extends the technique used by @david-arm in SelectICmp. The approach can be summarized as follows:
Consider the loop:

unsigned int red = start_value;
for (unsigned int i = 0; i < n; ++i)
  red = (a[i] > b[i]) ? i : red;

vectorize to:

unsigned int red = start_value;
vec_unsigned_int red_part = splat(start_value);
vec_unsigned_int step_vec = {0, 1, 2, ...};
for (unsigned int i = 0; i < n; i+=vl) {
  red_part = (vec_a[i] > vec_b[i]) ? step_vec : red_part;
  step_vec += {vl, vl, vl, ...};
}
vec_bool ne_start_value = red_part != splat(start_value);
bool may_update = reduce.or(ne_start_value);
vec_unsigned_int masked_red_part = ne_start_value ? red_part : splat(DataTypeMin);
red = may_update ? reduce.smax|umax(masked_red_part) : start_value;

[artagnon]

In D150851#4479839, @Mel-Chen wrote:

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.

Sure, perhaps @artagnon can join the discussion as well. Let me share my experience first: In GCC, I have seen a classification called ExtractLast, which has a similar semantics to what you mentioned as FindLast. Welcome further input and opinions.

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.

If we focus on removing the wrapping and bound restrictions, I think we can consider the approach proposed by @artagnon in D152693. This method cleverly extends the technique used by @david-arm in SelectICmp. The approach can be summarized as follows:
Consider the loop:

unsigned int red = start_value;
for (unsigned int i = 0; i < n; ++i)
  red = (a[i] > b[i]) ? i : red;

vectorize to:

unsigned int red = start_value;
vec_unsigned_int red_part = splat(start_value);
vec_unsigned_int step_vec = {0, 1, 2, ...};
for (unsigned int i = 0; i < n; i+=vl) {
  red_part = (vec_a[i] > vec_b[i]) ? step_vec : red_part;
  step_vec += {vl, vl, vl, ...};
}
vec_bool ne_start_value = red_part != splat(start_value);
bool may_update = reduce.or(ne_start_value);
vec_unsigned_int masked_red_part = ne_start_value ? red_part : splat(DataTypeMin);
red = may_update ? reduce.smax|umax(masked_red_part) : start_value;

While the conditions checked in this patch are more strict, I believe both approaches should coexist. In general, the IR generated by this patch should have better performance in the same case. Therefore, it should be prioritized when possible. However, when the cases that cannot be handled by this patch, we can apply the approach in D152693.

Yes, the IR generated by this patch is quite optimized, and I suppose we can fallback to code-gen like in D152693 as a follow-up.

In addition, there is still room for optimization in this patch. We usually face source code like this:

j = -1;
for (int i = 0; i < n; i++) {
    if (a[i] < b[i]) {
        j = i;
    }
}

When the start value of the reduction is a known constant and is known to be smaller than the start value of the increasing induction variable, we may not even need to use a sentinel value. Simply using the reduce max operation would suffice.

I wouldn't worry about this for now. The patch already looks pretty good in its current state, and I think with the renaming that @Ayal proposed, it should be ready to land.

llvm/lib/Analysis/IVDescriptors.cpp

661

A static function would be nice.

[artagnon]

In D150851#4480312, @Mel-Chen wrote:

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.

@artagnon, could you please help to verify it?

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

[Mel-Chen]

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.

My opinion is:
Select[I|F]Cmp --> [I|F]AnyOf
SelectIV[I|F]Cmp --> [I|F]FindLastIV or [I|F]FindLastIncIV

About the function name, I lean towards not renaming it, or renaming it to more easily understandable names like conditional select, conditional assignment, and so on.

[Mel-Chen]

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.

Perhaps Ayal's approach can be helpful. The final found_func allows the approach to be more widely applicable. If we only focus on increasing/decreasing induction variables, we may be able to further streamline the process.

In D150851#4467261, @Ayal wrote:

Here's a sketch minimizing the size of the indices maintained throughout the loop, so they would avoid wrapping, provide out-of-bound values, and possibly use narrower types depending on trip-count and vl:

return_type FindLast(return_type unfound_value, vec_predicate_func, found_func) {
  vec_unsigned_int select_red_part = splat(0); // Zero indicates unfound.
  vec_unsigned_int step_vec = splat(1); // Count vector iterations starting at 1.

  for (unsigned int i = 0; i < n; i+=vl, step_vec+=splat(1))
    select_red_part = (vec_predicate_func(i) ? step_vec : select_red_part;

  unsigned vec_indices_ored = reduce.or(select_red_part);
  if (vec_indices_ored == 0)
    return unfound_value;
  unsigned inflated_red_part = (select_red_part - splat(1)) * vl + <0,1,...,vl-1>;
  unsigned last_index = reduce.umax(inflated_red_part);
  return found_func(last_index);
}

[Mel-Chen]

Rebase.

[shiva0217]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4003

Thanks for the explanation!

Could we use "} else if ((!VF.isVector() && !PhiR->isInLoop()))" to guard the generation?

It could be easier to understand the codegen is needed when VF is not a vector and createTargetReduction won't be invoked.

Should we rename createSentinelValueHandling as createSelectInitValOrReduction?

I feel it could reflect the codegen but in a less strong opinion.

[Mel-Chen]

Rebase.

[Mel-Chen]

Changes:

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

[artagnon]

Hi Mel,

I had the chance to try out your patch today, and it seems that it's really quite restricted in its scope. I tried it out on this simple C program:

#include <stdio.h>

int main() {
      int src[20000] = {4, 5, 2};
      int r = 331;
      for (int i = 0; i < 20000; i++) {
        if (src[i] > 3)
          r = i;
      }
      printf("%d\n", r);
      return 0;
}

Unfortunately, your patch failed to vectorize this simple case, because when you match NonPhi against a PHINode, it is blocked on a trunc:

for.body:                                         ; preds = %entry, %for.body
  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
  %r.05 = phi i32 [ 331, %entry ], [ %spec.select, %for.body ]
  %arrayidx = getelementptr inbounds [20000 x i32], ptr %src, i64 0, i64 %indvars.iv
  %3 = load i32, ptr %arrayidx, align 4, !tbaa !6
  %cmp1 = icmp sgt i32 %3, 3
  %4 = trunc i64 %indvars.iv to i32 // blocked here
  %spec.select = select i1 %cmp1, i32 %4, i32 %r.05
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %exitcond.not = icmp eq i64 %indvars.iv.next, 20000
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body, !llvm.loop !10

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

Thanks.

[artagnon]

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).

[Mel-Chen]

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).

Yes, this issue is known, which is why I left a TODO in the summary.
I made the following modifications before:

   auto IsIncreasingLoopInduction = [&SE, &Loop](Value *V) {
+    // FIXME: Should focus on SExt and Trunc only?
+    if (auto *Cast = dyn_cast<CastInst>(V))
+      V = Cast->getOperand(0);
+
     auto *Phi = dyn_cast<PHINode>(V);

However, this approach is not rigorous.
Regardless of whether the nsw flag can still be used to determine whether to use signed max or unsigned max, proving whether the truncated induction variable is monotonically increasing is already a challenge.
Consider the following scenario:

previous step: i64:0000000000000000000000000000000001111111111111111111111111111111 -> i32:01111111111111111111111111111111
add one
current step: i64:0000000000000000000000000000000010000000000000000000000000000000 -> i32:10000000000000000000000000000000

I have discussed this issue with my colleagues several times, and here are some directions we came up with:

1. Use SCEV overflow check. There is an overflow check generator in PSE that we can use, but it seems to be designed for checking the type of the original induction variable, not the truncated type. Using this approach would require implementing a new check generator and inserting it in the preheader.

2. Prevent the generation of truncated induction variables. In the IndVarSimplifyPass, there is an option called -indvars-widen-indvars https://llvm.org/doxygen/IndVarSimplify_8cpp.html#aea2c111bf1f82fd672acaad1931e7e2d. This transformation widens the type of the induction variable to reduce the number of sign/zero-extends. However, if there are users in the loop that require the narrower original type, truncation will occur. Perhaps we can make some adjustments in this area.

Before IndVarSimplifyPass:
; Preheader:
  for.body.preheader:                               ; preds = %entry
    br label %for.body

  ; Loop:
  for.body:                                         ; preds = %for.body.preheader, %for.body
    %i.011 = phi i32 [ %inc, %for.body ], [ 0, %for.body.preheader ]
    %idx.010 = phi i32 [ %cond, %for.body ], [ %ii, %for.body.preheader ]
    %idxprom = zext i32 %i.011 to i64
    %arrayidx = getelementptr inbounds i64, ptr %a, i64 %idxprom
    %0 = load i64, ptr %arrayidx, align 8, !tbaa !4
    %arrayidx2 = getelementptr inbounds i64, ptr %b, i64 %idxprom
    %1 = load i64, ptr %arrayidx2, align 8, !tbaa !4
    %cmp3 = icmp sgt i64 %0, %1
    %cond = select i1 %cmp3, i32 %i.011, i32 %idx.010
    %inc = add nuw nsw i32 %i.011, 1 
    %cmp = icmp slt i32 %inc, %n
    br i1 %cmp, label %for.body, label %for.cond.cleanup.loopexit, !llvm.loop !8

  ; Exit blocks
  for.cond.cleanup.loopexit:                        ; preds = %for.body
    %cond.lcssa = phi i32 [ %cond, %for.body ]
    br label %for.cond.cleanup

After IndVarSimplifyPass:
; Preheader:
  for.body.preheader:                               ; preds = %entry
    %wide.trip.count = zext i32 %n to i64
    br label %for.body

  ; Loop:
  for.body:                                         ; preds = %for.body.preheader, %for.body
    %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, %for.body ]
    %idx.010 = phi i32 [ %cond, %for.body ], [ %ii, %for.body.preheader ]
    %arrayidx = getelementptr inbounds i64, ptr %a, i64 %indvars.iv
    %0 = load i64, ptr %arrayidx, align 8, !tbaa !4
    %arrayidx2 = getelementptr inbounds i64, ptr %b, i64 %indvars.iv
    %1 = load i64, ptr %arrayidx2, align 8, !tbaa !4
    %cmp3 = icmp sgt i64 %0, %1
    %2 = trunc i64 %indvars.iv to i32
    %cond = select i1 %cmp3, i32 %2, i32 %idx.010
    %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
    %exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count
    br i1 %exitcond, label %for.body, label %for.cond.cleanup.loopexit, !llvm.loop !8

  ; Exit blocks
  for.cond.cleanup.loopexit:                        ; preds = %for.body
    %cond.lcssa = phi i32 [ %cond, %for.body ]
    br label %for.cond.cleanup

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.

Signed IV loop guard:
entry:
  %cmp9 = icmp sgt i32 %n, 0
  br i1 %cmp9, label %for.body.preheader, label %for.cond.cleanup

Unsigned IV loop guard:
entry:
  %cmp9.not = icmp eq i32 %n, 0
  br i1 %cmp9.not, label %for.cond.cleanup, label %for.body.preheader

Currently, I personally prefer option 2, but since the performance impact of this modification is uncertain, our final decision is to proceed with option 3.

And of course, the worst-case would be to use a general conditional selecting reduction method to solve the problem.

[artagnon]

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.

[Joe]

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?

To me, the problem stems from the loss of information that the IV had 32-bit NSW/NUW when IndVarSimplify widens it. Just thinking about alternative options, what if we could retain that information in loop metadata?

[Mel-Chen]

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.

Sounds good! Before you start implementing, I suggest observing the benchmarks to gather more cases. We choose option 3 because, based on our available benchmarks, all the opportunities for the FindLastIV pattern arise from induction variables that determine the branch condition at the loop latch. Therefore, we decided to go with option 3, as it is an implementation that is not too challenging and provides effective results

[Mel-Chen]

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?

We need to determine whether we should use umax or smax in the middle.block. Currently, we have only implemented smax because the application of {1,+,step} unsigned induction variables is relatively uncommon.

To me, the problem stems from the loss of information that the IV had 32-bit NSW/NUW when IndVarSimplify widens it. Just thinking about alternative options, what if we could retain that information in loop metadata?

Yes, this is due to the loss of information. If you would like to use metadata, would it be attached to the step instruction of the induction variable?

[Joe]

In D150851#4546075, @Mel-Chen wrote:

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?

We need to determine whether we should use umax or smax in the middle.block. Currently, we have only implemented smax because the application of {1,+,step} unsigned induction variables is relatively uncommon.

That makes sense, thanks for clarifying :)

To me, the problem stems from the loss of information that the IV had 32-bit NSW/NUW when IndVarSimplify widens it. Just thinking about alternative options, what if we could retain that information in loop metadata?

Yes, this is due to the loss of information. If you would like to use metadata, would it be attached to the step instruction of the induction variable?

I (naively) thought this would be attached to the loop metadata, but I haven't looked at implementation details. To be honest, I don't think this is the best option - I prefer option 3.

[shiva0217]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4003

Oops, I think I mix the patch with some local changes. Please ignore the comment.

[Mel-Chen]

Rebase, and here is a summary of the changes:

1. Avoid the use of the SelectCmp.* series to indicate to AnyOf and FindLastIV, as @Ayal expressed concerns about potential confusion with min/max reduction.
2. I attempted to use FindLast.* as a collective term for AnyOf and FindLastIV, but it was deemed less readable upon completion, so the current version uses separate functions for AnyOf and FindLastIV.
3. Discovered an issue with AnyOf reduction while inserting AddReductionVar. A pre-commit revision D157375 has been opened to discuss this.

[Mel-Chen]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4003

No problem. And I've just rebased this patch. Please continue with the review. Thank you.

[Mel-Chen]

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

[Mel-Chen]

Rebase.

[Mel-Chen]

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.

[Mel-Chen]

Remove the unused parameter Prev in RecurrenceDescriptor::isFindLastIVPattern.

[Mel-Chen]

ping

[artagnon]

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.

[Mel-Chen]

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.

Hi, artagnon, Thank you. We have some new fixes, but for some unknown reason, I can't use arc diff --update to update the changes. I'm considering moving the patch directly to a GitHub pull request.

[Mel-Chen]

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

llvm/include/llvm/Analysis/IVDescriptors.h

enum class RecurKind {
   UMax,       ///< Unsigned integer max implemented in terms of select(cmp()).
   FAdd,       ///< Sum of floats.
   FMul,       ///< Product of floats.
   FMin,       ///< FP min implemented in terms of select(cmp()).
   FMax,       ///< FP max implemented in terms of select(cmp()).
   FMulAdd,    ///< Fused multiply-add of floats (a * b + c).
   SelectICmp, ///< Integer select(icmp(),x,y) where one of (x,y) is loop
               ///< invariant
-  SelectFCmp  ///< Integer select(fcmp(),x,y) where one of (x,y) is loop
+  SelectFCmp, ///< Integer select(fcmp(),x,y) where one of (x,y) is loop
               ///< invariant
+  SelectIVICmp, ///< Integer select(icmp(),x,y) where one of (x,y) is increasing
+                ///< loop induction PHI
+  SelectIVFCmp, ///< Integer select(fcmp(),x,y) where one of (x,y) is increasing
+                ///< loop induction PHI
 };
 
 /// The RecurrenceDescriptor is used to identify recurrences variables in a
 /// loop. Reduction is a special case of recurrence that has uses of the
 /// recurrence variable outside the loop. The method isReductionPHI identifies
 /// reductions that are basic recurrences.
 ///
 /// Basic recurrences are defined as the summation, product, OR, AND, XOR, min,
public:
   /// Returns a struct describing if the instruction 'I' can be a recurrence
   /// variable of type 'Kind' for a Loop \p L and reduction PHI \p Phi.
   /// If the recurrence is a min/max pattern of select(icmp()) this function
   /// advances the instruction pointer 'I' from the compare instruction to the
   /// select instruction and stores this pointer in 'PatternLastInst' member of
   /// the returned struct.
   static InstDesc isRecurrenceInstr(Loop *L, PHINode *Phi, Instruction *I,
                                     RecurKind Kind, InstDesc &Prev,
-                                    FastMathFlags FuncFMF);
+                                    FastMathFlags FuncFMF, ScalarEvolution *SE);
 
   /// Returns true if instruction I has multiple uses in Insts
   static bool hasMultipleUsesOf(Instruction *I,
                                 SmallPtrSetImpl<Instruction *> &Insts,
                                 unsigned MaxNumUses);
 
   /// Returns true if all uses of the instruction I is within the Set.
   static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set);
 
   /// Returns a struct describing if the instruction is a llvm.(s/u)(min/max),
   /// llvm.minnum/maxnum or a Select(ICmp(X, Y), X, Y) pair of instructions
   /// corresponding to a min(X, Y) or max(X, Y), matching the recurrence kind \p
   /// Kind. \p Prev specifies the description of an already processed select
   /// instruction, so its corresponding cmp can be matched to it.
   static InstDesc isMinMaxPattern(Instruction *I, RecurKind Kind,
                                   const InstDesc &Prev);
 
   /// Returns a struct describing whether the instruction is either a
   ///   Select(ICmp(A, B), X, Y), or
   ///   Select(FCmp(A, B), X, Y)
-  /// where one of (X, Y) is a loop invariant integer and the other is a PHI
-  /// value. \p Prev specifies the description of an already processed select
-  /// instruction, so its corresponding cmp can be matched to it.
+  /// where one of (X, Y) is a loop invariant integer or an increasing loop
+  /// induction variable and the other is a PHI value. \p Prev specifies the
+  /// description of an already processed select instruction, so its
+  /// corresponding cmp can be matched to it.
   static InstDesc isSelectCmpPattern(Loop *Loop, PHINode *OrigPhi,
-                                     Instruction *I, InstDesc &Prev);
+                                     Instruction *I, InstDesc &Prev,
+                                     ScalarEvolution *SE);
 
   /// Returns a struct describing if the instruction is a
   /// Select(FCmp(X, Y), (Z = X op PHINode), PHINode) instruction pattern.
   static InstDesc isConditionalRdxPattern(RecurKind Kind, Instruction *I);
 
   /// Returns identity corresponding to the RecurrenceKind.
   Value *getRecurrenceIdentity(RecurKind K, Type *Tp, FastMathFlags FMF) const;
 
public:
   /// Returns true if the recurrence kind is any min/max kind.
   static bool isMinMaxRecurrenceKind(RecurKind Kind) {
     return isIntMinMaxRecurrenceKind(Kind) || isFPMinMaxRecurrenceKind(Kind);
   }
 
   /// Returns true if the recurrence kind is of the form
   ///   select(cmp(),x,y) where one of (x,y) is loop invariant.
   static bool isSelectCmpRecurrenceKind(RecurKind Kind) {
-    return Kind == RecurKind::SelectICmp || Kind == RecurKind::SelectFCmp;
+    return Kind == RecurKind::SelectICmp || Kind == RecurKind::SelectFCmp ||
+           Kind == RecurKind::SelectIVICmp || Kind == RecurKind::SelectIVFCmp;
   }
 
   /// Returns the type of the recurrence. This type can be narrower than the
   /// actual type of the Phi if the recurrence has been type-promoted.
   Type *getRecurrenceType() const { return RecurrenceType; }
 
   /// Returns a reference to the instructions used for type-promoting the
   /// recurrence.

llvm/include/llvm/Transforms/Utils/LoopUtils.h

 Intrinsic::ID getMinMaxReductionIntrinsicOp(RecurKind RK);
 
 /// Returns the comparison predicate used when expanding a min/max reduction.
 CmpInst::Predicate getMinMaxReductionPredicate(RecurKind RK);
 
 /// See RecurrenceDescriptor::isSelectCmpPattern for a description of the
 /// pattern we are trying to match. In this pattern we are only ever selecting
 /// between two values: 1) an initial PHI start value, and 2) a loop invariant
-/// value. This function uses \p LoopExitInst to determine 2), which we then use
-/// to select between \p Left and \p Right. Any lane value in \p Left that
-/// matches 2) will be merged into \p Right.
+/// value and increasing loop induction variable. This function uses \p
+/// LoopExitInst to determine 2), which we then use to select between \p Left
+/// and \p Right. Any lane value in \p Left that matches 2) will be merged into
+/// \p Right.
 Value *createSelectCmpOp(IRBuilderBase &Builder, Value *StartVal, RecurKind RK,
                          Value *Left, Value *Right);
 
 /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
 /// The Builder's fast-math-flags must be set to propagate the expected values.
 Value *createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left,
                       Value *Right);
 

 /// Fast-math-flags are propagated using the IRBuilder's setting.
 Value *createSimpleTargetReduction(IRBuilderBase &B,
                                    const TargetTransformInfo *TTI, Value *Src,
                                    RecurKind RdxKind);
 
 /// Create a target reduction of the given vector \p Src for a reduction of the
 /// kind RecurKind::SelectICmp or RecurKind::SelectFCmp. The reduction operation
 /// is described by \p Desc.
+Value *createInvariantSelectCmpTargetReduction(IRBuilderBase &B,
+                                               const TargetTransformInfo *TTI,
+                                               Value *Src,
+                                               const RecurrenceDescriptor &Desc,
+                                               PHINode *OrigPhi);
+
+/// Create a target reduction of the given vector \p Src for a reduction of the
+/// kind conforms to RecurrenceDescriptor::isSelectCmpPattern. The reduction
+/// operation is described by \p Desc.
 Value *createSelectCmpTargetReduction(IRBuilderBase &B,
                                       const TargetTransformInfo *TTI,
                                       Value *Src,
                                       const RecurrenceDescriptor &Desc,
                                       PHINode *OrigPhi);
 
 /// Create a generic target reduction using a recurrence descriptor \p Desc
 /// The target is queried to determine if intrinsics or shuffle sequences are
 /// required to implement the reduction.
 /// Fast-math-flags are propagated using the RecurrenceDescriptor.
 Value *createTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI,
                              const RecurrenceDescriptor &Desc, Value *Src,
                              PHINode *OrigPhi = nullptr);
 
 /// Create an ordered reduction intrinsic using the given recurrence
 /// descriptor \p Desc.
 Value *createOrderedReduction(IRBuilderBase &B,
                               const RecurrenceDescriptor &Desc, Value *Src,
                               Value *Start);
 
+/// Returns a set of cmp and select instructions as shown below:
+///   Select(Cmp(NE, Rdx, Iden), Rdx, InitVal)
+/// where \p Rdx is a scalar value generated by target reduction, Iden is the
+/// sentinel value of the recurrence descriptor \p Desc, and InitVal is the
+/// start value of the recurrence descriptor \p Desc.
+Value *createSentinelValueHandling(IRBuilderBase &Builder,
+                                   const TargetTransformInfo *TTI,
+                                   const RecurrenceDescriptor &Desc,
+                                   Value *Rdx);
+
 /// Get the intersection (logical and) of all of the potential IR flags
 /// of each scalar operation (VL) that will be converted into a vector (I).
 /// If OpValue is non-null, we only consider operations similar to OpValue
 /// when intersecting.
 /// Flag set: NSW, NUW (if IncludeWrapFlags is true), exact, and all of
 /// fast-math.
 void propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue = nullptr,
                       bool IncludeWrapFlags = true);

llvm/lib/Analysis/IVDescriptors.cpp

bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurKind Kind) {
   case RecurKind::And:
   case RecurKind::Xor:
   case RecurKind::SMax:
   case RecurKind::SMin:
   case RecurKind::UMax:
   case RecurKind::UMin:
   case RecurKind::SelectICmp:
   case RecurKind::SelectFCmp:
+  case RecurKind::SelectIVICmp:
+  case RecurKind::SelectIVFCmp:
     return true;
   }
   return false;
 }
 
 bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurKind Kind) {
   return (Kind != RecurKind::None) && !isIntegerRecurrenceKind(Kind);
 }
if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
         !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))
       return false;
 
     // Any reduction instruction must be of one of the allowed kinds. We ignore
     // the starting value (the Phi or an AND instruction if the Phi has been
     // type-promoted).
     if (Cur != Start) {
       ReduxDesc =
-          isRecurrenceInstr(TheLoop, Phi, Cur, Kind, ReduxDesc, FuncFMF);
+          isRecurrenceInstr(TheLoop, Phi, Cur, Kind, ReduxDesc, FuncFMF, SE);
       ExactFPMathInst = ExactFPMathInst == nullptr
                             ? ReduxDesc.getExactFPMathInst()
                             : ExactFPMathInst;
       if (!ReduxDesc.isRecurrence())
         return false;
       // FIXME: FMF is allowed on phi, but propagation is not handled correctly.
       if (isa<FPMathOperator>(ReduxDesc.getPatternInst()) && !IsAPhi) {
         FastMathFlags CurFMF = ReduxDesc.getPatternInst()->getFastMathFlags();
if (!IsAPhi && !IsASelect && !isMinMaxRecurrenceKind(Kind) &&
         !isSelectCmpRecurrenceKind(Kind) &&
         hasMultipleUsesOf(Cur, VisitedInsts, 1))
       return false;
 
     // All inputs to a PHI node must be a reduction value.
     if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
       return false;
 
-    if ((isIntMinMaxRecurrenceKind(Kind) || Kind == RecurKind::SelectICmp) &&
+    if ((isIntMinMaxRecurrenceKind(Kind) || Kind == RecurKind::SelectICmp ||
+         Kind == RecurKind::SelectIVICmp) &&
         (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
       ++NumCmpSelectPatternInst;
-    if ((isFPMinMaxRecurrenceKind(Kind) || Kind == RecurKind::SelectFCmp) &&
+    if ((isFPMinMaxRecurrenceKind(Kind) || Kind == RecurKind::SelectFCmp ||
+         Kind == RecurKind::SelectIVFCmp) &&
         (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
       ++NumCmpSelectPatternInst;
 
     // Check  whether we found a reduction operator.
     FoundReduxOp |= !IsAPhi && Cur != Start;
 
     // Process users of current instruction. Push non-PHI nodes after PHI nodes
     // onto the stack. This way we are going to have seen all inputs to PHI
for (User *U : Cur->users()) {
             return false;
           }
           NonPHIs.push_back(UI);
         }
       } else if (!isa<PHINode>(UI) &&
                  ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
                    !isa<SelectInst>(UI)) ||
                   (!isConditionalRdxPattern(Kind, UI).isRecurrence() &&
-                   !isSelectCmpPattern(TheLoop, Phi, UI, IgnoredVal)
+                   !isSelectCmpPattern(TheLoop, Phi, UI, IgnoredVal, SE)
                         .isRecurrence() &&
                    !isMinMaxPattern(UI, Kind, IgnoredVal).isRecurrence())))
         return false;
 
       // Remember that we completed the cycle.
       if (UI == Phi)
         FoundStartPHI = true;
     }
bool RecurrenceDescriptor::AddReductionVar(
   RecurrenceDescriptor RD(RdxStart, ExitInstruction, IntermediateStore, Kind,
                           FMF, ExactFPMathInst, RecurrenceType, IsSigned,
                           IsOrdered, CastInsts, MinWidthCastToRecurrenceType);
   RedDes = RD;
 
   return true;
 }
 
 // We are looking for loops that do something like this:
 //   int r = 0;
 //   for (int i = 0; i < n; i++) {
 //     if (src[i] > 3)
 //       r = 3;
 //   }
 // where the reduction value (r) only has two states, in this example 0 or 3.
 // The generated LLVM IR for this type of loop will be like this:
 //   for.body:
 //     %r = phi i32 [ %spec.select, %for.body ], [ 0, %entry ]
 //     ...
 //     %cmp = icmp sgt i32 %5, 3
 //     %spec.select = select i1 %cmp, i32 3, i32 %r
 //     ...
 // In general we can support vectorization of loops where 'r' flips between
 // any two non-constants, provided they are loop invariant. The only thing
 // we actually care about at the end of the loop is whether or not any lane
 // in the selected vector is different from the start value. The final
 // across-vector reduction after the loop simply involves choosing the start
 // value if nothing changed (0 in the example above) or the other selected
 // value (3 in the example above).
 RecurrenceDescriptor::InstDesc
 RecurrenceDescriptor::isSelectCmpPattern(Loop *Loop, PHINode *OrigPhi,
-                                         Instruction *I, InstDesc &Prev) {
+                                         Instruction *I, InstDesc &Prev,
+                                         ScalarEvolution *SE) {
   // We must handle the select(cmp(),x,y) as a single instruction. Advance to
   // the select.
   CmpInst::Predicate Pred;
   if (match(I, m_OneUse(m_Cmp(Pred, m_Value(), m_Value())))) {
     if (auto *Select = dyn_cast<SelectInst>(*I->user_begin()))
       return InstDesc(Select, Prev.getRecKind());
   }
 
   // Only match select with single use cmp condition.
   if (!match(I, m_Select(m_OneUse(m_Cmp(Pred, m_Value(), m_Value())), m_Value(),
                          m_Value())))
     return InstDesc(false, I);
 
   SelectInst *SI = cast<SelectInst>(I);
   Value *NonPhi = nullptr;
 
   if (OrigPhi == dyn_cast<PHINode>(SI->getTrueValue()))
     NonPhi = SI->getFalseValue();
   else if (OrigPhi == dyn_cast<PHINode>(SI->getFalseValue()))
     NonPhi = SI->getTrueValue();
   else
     return InstDesc(false, I);
 
+  auto IsIncreasingLoopInduction = [&SE, &Loop](Value *V) {
+    if (!SE)
+      return false;
+
+    auto *Phi = dyn_cast<PHINode>(V);
+    if (!Phi)
+      return false;
+
+    auto LB = Loop::LoopBounds::getBounds(*Loop, *Phi, *SE);
+    if (!LB)
+      return false;
+
+    auto Direction = LB->getDirection();
+    return Direction == Loop::LoopBounds::Direction::Increasing;
+  };
+
   // We are looking for selects of the form:
   //   select(cmp(), phi, loop_invariant) or
   //   select(cmp(), loop_invariant, phi)
-  if (!Loop->isLoopInvariant(NonPhi))
-    return InstDesc(false, I);
-
+  if (Loop->isLoopInvariant(NonPhi))
     return InstDesc(I, isa<ICmpInst>(I->getOperand(0)) ? RecurKind::SelectICmp
                                                        : RecurKind::SelectFCmp);
+  // or
+  //   select(cmp(), phi, loop_induction) or
+  //   select(cmp(), loop_induction, phi)
+  if (IsIncreasingLoopInduction(NonPhi))
+    return InstDesc(I, isa<ICmpInst>(I->getOperand(0))
+                           ? RecurKind::SelectIVICmp
+                           : RecurKind::SelectIVFCmp);
+
+  return InstDesc(false, I);
 }
 
 RecurrenceDescriptor::InstDesc
 RecurrenceDescriptor::isMinMaxPattern(Instruction *I, RecurKind Kind,
                                       const InstDesc &Prev) {
   assert((isa<CmpInst>(I) || isa<SelectInst>(I) || isa<CallInst>(I)) &&
          "Expected a cmp or select or call instruction");
   if (!isMinMaxRecurrenceKind(Kind))
RecurrenceDescriptor::isConditionalRdxPattern(RecurKind Kind, Instruction *I) {
   Instruction *IPhi = isa<PHINode>(*Op1) ? dyn_cast<Instruction>(Op1)
                                          : dyn_cast<Instruction>(Op2);
   if (!IPhi || IPhi != FalseVal)
     return InstDesc(false, I);
 
   return InstDesc(true, SI);
 }
 
-RecurrenceDescriptor::InstDesc
-RecurrenceDescriptor::isRecurrenceInstr(Loop *L, PHINode *OrigPhi,
-                                        Instruction *I, RecurKind Kind,
-                                        InstDesc &Prev, FastMathFlags FuncFMF) {
+RecurrenceDescriptor::InstDesc RecurrenceDescriptor::isRecurrenceInstr(
+    Loop *L, PHINode *OrigPhi, Instruction *I, RecurKind Kind, InstDesc &Prev,
+    FastMathFlags FuncFMF, ScalarEvolution *SE) {
   assert(Prev.getRecKind() == RecurKind::None || Prev.getRecKind() == Kind);
   switch (I->getOpcode()) {
   default:
     return InstDesc(false, I);
   case Instruction::PHI:
     return InstDesc(I, Prev.getRecKind(), Prev.getExactFPMathInst());
   case Instruction::Sub:
   case Instruction::Add:
case Instruction::Select:
     if (Kind == RecurKind::FAdd || Kind == RecurKind::FMul ||
         Kind == RecurKind::Add || Kind == RecurKind::Mul)
       return isConditionalRdxPattern(Kind, I);
     [[fallthrough]];
   case Instruction::FCmp:
   case Instruction::ICmp:
   case Instruction::Call:
     if (isSelectCmpRecurrenceKind(Kind))
-      return isSelectCmpPattern(L, OrigPhi, I, Prev);
+      return isSelectCmpPattern(L, OrigPhi, I, Prev, SE);
     if (isIntMinMaxRecurrenceKind(Kind) ||
         (((FuncFMF.noNaNs() && FuncFMF.noSignedZeros()) ||
           (isa<FPMathOperator>(I) && I->hasNoNaNs() &&
            I->hasNoSignedZeros())) &&
          isFPMinMaxRecurrenceKind(Kind)))
       return isMinMaxPattern(I, Kind, Prev);
     else if (isFMulAddIntrinsic(I))
       return InstDesc(Kind == RecurKind::FMulAdd, I,
Value *RecurrenceDescriptor::getRecurrenceIdentity(RecurKind K, Type *Tp,
   case RecurKind::FMax:
     assert((FMF.noNaNs() && FMF.noSignedZeros()) &&
            "nnan, nsz is expected to be set for FP max reduction.");
     return ConstantFP::getInfinity(Tp, true /*Negative*/);
   case RecurKind::SelectICmp:
   case RecurKind::SelectFCmp:
     return getRecurrenceStartValue();
     break;
+  case RecurKind::SelectIVICmp:
+  case RecurKind::SelectIVFCmp:
+    // FIXME: SMax or UMax, I'm not sure which one is correct.
+    return getRecurrenceIdentity(RecurKind::SMax, Tp, FMF);
   default:
     llvm_unreachable("Unknown recurrence kind");
   }
 }
 
 unsigned RecurrenceDescriptor::getOpcode(RecurKind Kind) {
   switch (Kind) {
   case RecurKind::Add:
unsigned RecurrenceDescriptor::getOpcode(RecurKind Kind) {
   case RecurKind::FMulAdd:
   case RecurKind::FAdd:
     return Instruction::FAdd;
   case RecurKind::SMax:
   case RecurKind::SMin:
   case RecurKind::UMax:
   case RecurKind::UMin:
   case RecurKind::SelectICmp:
+  case RecurKind::SelectIVICmp:
     return Instruction::ICmp;
   case RecurKind::FMax:
   case RecurKind::FMin:
   case RecurKind::SelectFCmp:
+  case RecurKind::SelectIVFCmp:
     return Instruction::FCmp;
   default:
     llvm_unreachable("Unknown recurrence operation");
   }
 }
 
 SmallVector<Instruction *, 4>
 RecurrenceDescriptor::getReductionOpChain(PHINode *Phi, Loop *L) const {

llvm/lib/Transforms/Utils/LoopUtils.cpp

case RecurKind::FMin:
     return CmpInst::FCMP_OLT;
   case RecurKind::FMax:
     return CmpInst::FCMP_OGT;
   }
 }
 
 Value *llvm::createSelectCmpOp(IRBuilderBase &Builder, Value *StartVal,
                                RecurKind RK, Value *Left, Value *Right) {
+  switch (RK) {
+  case RecurKind::SelectICmp:
+  case RecurKind::SelectFCmp: {
     if (auto VTy = dyn_cast<VectorType>(Left->getType()))
       StartVal = Builder.CreateVectorSplat(VTy->getElementCount(), StartVal);
     Value *Cmp =
         Builder.CreateCmp(CmpInst::ICMP_NE, Left, StartVal, "rdx.select.cmp");
     return Builder.CreateSelect(Cmp, Left, Right, "rdx.select");
   }
+  case RecurKind::SelectIVICmp:
+  case RecurKind::SelectIVFCmp:
+    // TODO: SMax or UMax?
+    return createMinMaxOp(Builder, RecurKind::SMax, Left, Right);
+  default:
+    llvm_unreachable("Unknown SelectCmp recurrence kind");
+  }
+}
 
 Value *llvm::createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left,
                             Value *Right) {
   Type *Ty = Left->getType();
   if (Ty->isIntOrIntVectorTy()) {
     // TODO: Add float minnum/maxnum support when FMF nnan is set.
     Intrinsic::ID Id = getMinMaxReductionIntrinsicOp(RK);
     return Builder.CreateIntrinsic(Ty, Id, {Left, Right}, nullptr,
if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
              "Invalid min/max");
       TmpVec = createMinMaxOp(Builder, RdxKind, TmpVec, Shuf);
     }
   }
   // The result is in the first element of the vector.
   return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
 }
 
-Value *llvm::createSelectCmpTargetReduction(IRBuilderBase &Builder,
-                                            const TargetTransformInfo *TTI,
-                                            Value *Src,
-                                            const RecurrenceDescriptor &Desc,
-                                            PHINode *OrigPhi) {
-  assert(RecurrenceDescriptor::isSelectCmpRecurrenceKind(
-             Desc.getRecurrenceKind()) &&
+Value *llvm::createInvariantSelectCmpTargetReduction(
+    IRBuilderBase &Builder, const TargetTransformInfo *TTI, Value *Src,
+    const RecurrenceDescriptor &Desc, PHINode *OrigPhi) {
+  assert((Desc.getRecurrenceKind() == RecurKind::SelectICmp ||
+          Desc.getRecurrenceKind() == RecurKind::SelectFCmp) &&
          "Unexpected reduction kind");
   Value *InitVal = Desc.getRecurrenceStartValue();
   Value *NewVal = nullptr;
 
   // First use the original phi to determine the new value we're trying to
   // select from in the loop.
   SelectInst *SI = nullptr;
   for (auto *U : OrigPhi->users()) {
Value *llvm::createInvariantSelectCmpTargetReduction(
   Value *Cmp =
       Builder.CreateCmp(CmpInst::ICMP_NE, Src, Right, "rdx.select.cmp");
 
   // If any predicate is true it means that we want to select the new value.
   Cmp = Builder.CreateOrReduce(Cmp);
   return Builder.CreateSelect(Cmp, NewVal, InitVal, "rdx.select");
 }
 
+Value *llvm::createSelectCmpTargetReduction(IRBuilderBase &Builder,
+                                            const TargetTransformInfo *TTI,
+                                            Value *Src,
+                                            const RecurrenceDescriptor &Desc,
+                                            PHINode *OrigPhi) {
+  assert(RecurrenceDescriptor::isSelectCmpRecurrenceKind(
+             Desc.getRecurrenceKind()) &&
+         "Unexpected reduction kind");
+  RecurKind RdxKind = Desc.getRecurrenceKind();
+  switch (RdxKind) {
+  case RecurKind::SelectICmp:
+  case RecurKind::SelectFCmp:
+    return createInvariantSelectCmpTargetReduction(Builder, TTI, Src, Desc,
+                                                   OrigPhi);
+  case RecurKind::SelectIVICmp:
+  case RecurKind::SelectIVFCmp:
+    // FIXME: SMax or UMax?
+    // TODO: Decreasing induction need fix here
+    return Builder.CreateIntMaxReduce(Src, true);
+  default:
+    llvm_unreachable("Unknown SelectCmp recurrence kind");
+  }
+}
+
 Value *llvm::createSimpleTargetReduction(IRBuilderBase &Builder,
                                          const TargetTransformInfo *TTI,
                                          Value *Src, RecurKind RdxKind) {
   auto *SrcVecEltTy = cast<VectorType>(Src->getType())->getElementType();
   switch (RdxKind) {
   case RecurKind::Add:
     return Builder.CreateAddReduce(Src);
   case RecurKind::Mul:
assert((Desc.getRecurrenceKind() == RecurKind::FAdd ||
           Desc.getRecurrenceKind() == RecurKind::FMulAdd) &&
          "Unexpected reduction kind");
   assert(Src->getType()->isVectorTy() && "Expected a vector type");
   assert(!Start->getType()->isVectorTy() && "Expected a scalar type");
 
   return B.CreateFAddReduce(Start, Src);
 }
 
+Value *llvm::createSentinelValueHandling(IRBuilderBase &Builder,
+                                         const TargetTransformInfo *TTI,
+                                         const RecurrenceDescriptor &Desc,
+                                         Value *Rdx) {
+  Value *InitVal = Desc.getRecurrenceStartValue();
+  Value *Iden = Desc.getRecurrenceIdentity(
+      Desc.getRecurrenceKind(), Rdx->getType(), Desc.getFastMathFlags());
+  Value *Cmp = Builder.CreateCmp(CmpInst::ICMP_NE, Rdx, Iden, "rdx.select.cmp");
+  return Builder.CreateSelect(Cmp, Rdx, InitVal, "rdx.select");
+}
+
 void llvm::propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue,
                             bool IncludeWrapFlags) {
   auto *VecOp = dyn_cast<Instruction>(I);
   if (!VecOp)
     return;
   auto *Intersection = (OpValue == nullptr) ? dyn_cast<Instruction>(VL[0])
                                             : dyn_cast<Instruction>(OpValue);
   if (!Intersection)

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

if (VF.isVector() && !PhiR->isInLoop()) {
     // If the reduction can be performed in a smaller type, we need to extend
     // the reduction to the wider type before we branch to the original loop.
     if (PhiTy != RdxDesc.getRecurrenceType())
       ReducedPartRdx = RdxDesc.isSigned()
                            ? Builder.CreateSExt(ReducedPartRdx, PhiTy)
                            : Builder.CreateZExt(ReducedPartRdx, PhiTy);
   }
 
+  if (RK == RecurKind::SelectIVICmp || RK == RecurKind::SelectIVFCmp)
+    ReducedPartRdx =
+        createSentinelValueHandling(Builder, TTI, RdxDesc, ReducedPartRdx);
+
   PHINode *ResumePhi =
       dyn_cast<PHINode>(PhiR->getStartValue()->getUnderlyingValue());
 
   // Create a phi node that merges control-flow from the backedge-taken check
   // block and the middle block.
   PHINode *BCBlockPhi = PHINode::Create(PhiTy, 2, "bc.merge.rdx",
                                         LoopScalarPreHeader->getTerminator());
 

llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp

void VPReductionPHIRecipe::execute(VPTransformState &State) {
   // Reductions do not have to start at zero. They can start with
   // any loop invariant values.
   VPValue *StartVPV = getStartValue();
   Value *StartV = StartVPV->getLiveInIRValue();
 
   Value *Iden = nullptr;
   RecurKind RK = RdxDesc.getRecurrenceKind();
   if (RecurrenceDescriptor::isMinMaxRecurrenceKind(RK) ||
-      RecurrenceDescriptor::isSelectCmpRecurrenceKind(RK)) {
+      (RK == RecurKind::SelectICmp || RK == RecurKind::SelectFCmp)) {
     // MinMax reduction have the start value as their identify.
     if (ScalarPHI) {
       Iden = StartV;
     } else {
       IRBuilderBase::InsertPointGuard IPBuilder(Builder);
       Builder.SetInsertPoint(VectorPH->getTerminator());
       StartV = Iden =
           Builder.CreateVectorSplat(State.VF, StartV, "minmax.ident");
     }
+  } else if (RK == RecurKind::SelectIVICmp || RK == RecurKind::SelectIVFCmp) {
+    StartV = Iden = RdxDesc.getRecurrenceIdentity(RK, VecTy->getScalarType(),
+                                                  RdxDesc.getFastMathFlags());
+    if (!ScalarPHI) {
+      IRBuilderBase::InsertPointGuard IPBuilder(Builder);
+      Builder.SetInsertPoint(VectorPH->getTerminator());
+      StartV = Iden = Builder.CreateVectorSplat(State.VF, Iden);
+    }
   } else {
     Iden = RdxDesc.getRecurrenceIdentity(RK, VecTy->getScalarType(),
                                          RdxDesc.getFastMathFlags());
 
     if (!ScalarPHI) {
       Iden = Builder.CreateVectorSplat(State.VF, Iden);
       IRBuilderBase::InsertPointGuard IPBuilder(Builder);
       Builder.SetInsertPoint(VectorPH->getTerminator());

llvm/test/Transforms/LoopVectorize/select-min-index.ll

-; RUN: opt -passes=loop-vectorize -force-vector-width=4 -force-vector-interleave=1 -S %s | FileCheck %s
-; RUN: opt -passes=loop-vectorize -force-vector-width=4 -force-vector-interleave=2 -S %s | FileCheck %s
-; RUN: opt -passes=loop-vectorize -force-vector-width=1 -force-vector-interleave=2 -S %s | FileCheck %s
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function test_not_vectorize_select_no_min_reduction --version 2
+; RUN: opt -passes=loop-vectorize -force-vector-width=4 -force-vector-interleave=1 -S %s | FileCheck %s --check-prefix=CHECK-VF4IC1 --check-prefix=CHECK
+; RUN: opt -passes=loop-vectorize -force-vector-width=4 -force-vector-interleave=2 -S %s | FileCheck %s --check-prefix=CHECK-VF4IC2 --check-prefix=CHECK
+; RUN: opt -passes=loop-vectorize -force-vector-width=1 -force-vector-interleave=2 -S %s | FileCheck %s --check-prefix=CHECK-VF1IC2 --check-prefix=CHECK
 
 ; Test cases for selecting the index with the minimum value.
 
 define i64 @test_vectorize_select_umin_idx(ptr %src) {
 ; CHECK-LABEL: @test_vectorize_select_umin_idx(
 ; CHECK-NOT:   vector.body:
 ;
 entry:
loop:
   br i1 %exitcond.not, label %exit, label %loop
 
 exit:
   %res = phi i64 [ %min.idx.next, %loop ]
   ret i64 %res
 }
 
 define i64 @test_not_vectorize_select_no_min_reduction(ptr %src) {
-; CHECK-LABEL: @test_not_vectorize_select_no_min_reduction(
-; CHECK-NOT:   vector.body:
+; CHECK-VF4IC1-LABEL: define i64 @test_not_vectorize_select_no_min_reduction
+; CHECK-VF4IC1-SAME: (ptr [[SRC:%.*]]) {
+; CHECK-VF4IC1-NEXT:  entry:
+; CHECK-VF4IC1-NEXT:    br i1 true, label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
+; CHECK-VF4IC1:       vector.ph:
+; CHECK-VF4IC1-NEXT:    br label [[VECTOR_BODY:%.*]]
+; CHECK-VF4IC1:       vector.body:
+; CHECK-VF4IC1-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
+; CHECK-VF4IC1-NEXT:    [[VEC_IND:%.*]] = phi <4 x i64> [ <i64 0, i64 1, i64 2, i64 3>, [[VECTOR_PH]] ], [ [[VEC_IND_NEXT:%.*]], [[VECTOR_BODY]] ]
+; CHECK-VF4IC1-NEXT:    [[VEC_PHI:%.*]] = phi <4 x i64> [ <i64 -9223372036854775808, i64 -9223372036854775808, i64 -9223372036854775808, i64 -9223372036854775808>, [[VECTOR_PH]] ], [ [[TMP6:%.*]], [[VECTOR_BODY]] ]
+; CHECK-VF4IC1-NEXT:    [[VECTOR_RECUR:%.*]] = phi <4 x i64> [ <i64 poison, i64 poison, i64 poison, i64 0>, [[VECTOR_PH]] ], [ [[TMP3:%.*]], [[VECTOR_BODY]] ]
+; CHECK-VF4IC1-NEXT:    [[TMP0:%.*]] = add i64 [[INDEX]], 0
+; CHECK-VF4IC1-NEXT:    [[TMP1:%.*]] = getelementptr i64, ptr [[SRC]], i64 [[TMP0]]
+; CHECK-VF4IC1-NEXT:    [[TMP2:%.*]] = getelementptr i64, ptr [[TMP1]], i32 0
+; CHECK-VF4IC1-NEXT:    [[WIDE_LOAD:%.*]] = load <4 x i64>, ptr [[TMP2]], align 4
+; CHECK-VF4IC1-NEXT:    [[TMP3]] = add <4 x i64> [[WIDE_LOAD]], <i64 1, i64 1, i64 1, i64 1>
+; CHECK-VF4IC1-NEXT:    [[TMP4:%.*]] = shufflevector <4 x i64> [[VECTOR_RECUR]], <4 x i64> [[TMP3]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
+; CHECK-VF4IC1-NEXT:    [[TMP5:%.*]] = icmp ugt <4 x i64> [[TMP4]], [[WIDE_LOAD]]
+; CHECK-VF4IC1-NEXT:    [[TMP6]] = select <4 x i1> [[TMP5]], <4 x i64> [[VEC_IND]], <4 x i64> [[VEC_PHI]]
+; CHECK-VF4IC1-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
+; CHECK-VF4IC1-NEXT:    [[VEC_IND_NEXT]] = add <4 x i64> [[VEC_IND]], <i64 4, i64 4, i64 4, i64 4>
+; CHECK-VF4IC1-NEXT:    [[TMP7:%.*]] = icmp eq i64 [[INDEX_NEXT]], 0
+; CHECK-VF4IC1-NEXT:    br i1 [[TMP7]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP0:![0-9]+]]
+; CHECK-VF4IC1:       middle.block:
+; CHECK-VF4IC1-NEXT:    [[TMP8:%.*]] = call i64 @llvm.vector.reduce.smax.v4i64(<4 x i64> [[TMP6]])
+; CHECK-VF4IC1-NEXT:    [[RDX_SELECT_CMP:%.*]] = icmp ne i64 [[TMP8]], -9223372036854775808
+; CHECK-VF4IC1-NEXT:    [[RDX_SELECT:%.*]] = select i1 [[RDX_SELECT_CMP]], i64 [[TMP8]], i64 0
+; CHECK-VF4IC1-NEXT:    [[CMP_N:%.*]] = icmp eq i64 0, 0
+; CHECK-VF4IC1-NEXT:    [[VECTOR_RECUR_EXTRACT:%.*]] = extractelement <4 x i64> [[TMP3]], i32 3
+; CHECK-VF4IC1-NEXT:    br i1 [[CMP_N]], label [[EXIT:%.*]], label [[SCALAR_PH]]
+; CHECK-VF4IC1:       scalar.ph:
+; CHECK-VF4IC1-NEXT:    [[SCALAR_RECUR_INIT:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[VECTOR_RECUR_EXTRACT]], [[MIDDLE_BLOCK]] ]
+; CHECK-VF4IC1-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ 0, [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY]] ]
+; CHECK-VF4IC1-NEXT:    [[BC_MERGE_RDX:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[RDX_SELECT]], [[MIDDLE_BLOCK]] ]
+; CHECK-VF4IC1-NEXT:    br label [[LOOP:%.*]]
+; CHECK-VF4IC1:       loop:
+; CHECK-VF4IC1-NEXT:    [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-VF4IC1-NEXT:    [[MIN_IDX:%.*]] = phi i64 [ [[BC_MERGE_RDX]], [[SCALAR_PH]] ], [ [[MIN_IDX_NEXT:%.*]], [[LOOP]] ]
+; CHECK-VF4IC1-NEXT:    [[SCALAR_RECUR:%.*]] = phi i64 [ [[SCALAR_RECUR_INIT]], [[SCALAR_PH]] ], [ [[MIN_VAL_NEXT:%.*]], [[LOOP]] ]
+; CHECK-VF4IC1-NEXT:    [[GEP:%.*]] = getelementptr i64, ptr [[SRC]], i64 [[IV]]
+; CHECK-VF4IC1-NEXT:    [[L:%.*]] = load i64, ptr [[GEP]], align 4
+; CHECK-VF4IC1-NEXT:    [[CMP:%.*]] = icmp ugt i64 [[SCALAR_RECUR]], [[L]]
+; CHECK-VF4IC1-NEXT:    [[MIN_VAL_NEXT]] = add i64 [[L]], 1
+; CHECK-VF4IC1-NEXT:    [[FOO:%.*]] = call i64 @llvm.umin.i64(i64 [[SCALAR_RECUR]], i64 [[L]])
+; CHECK-VF4IC1-NEXT:    [[MIN_IDX_NEXT]] = select i1 [[CMP]], i64 [[IV]], i64 [[MIN_IDX]]
+; CHECK-VF4IC1-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-VF4IC1-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i64 [[IV_NEXT]], 0
+; CHECK-VF4IC1-NEXT:    br i1 [[EXITCOND_NOT]], label [[EXIT]], label [[LOOP]], !llvm.loop [[LOOP3:![0-9]+]]
+; CHECK-VF4IC1:       exit:
+; CHECK-VF4IC1-NEXT:    [[RES:%.*]] = phi i64 [ [[MIN_IDX_NEXT]], [[LOOP]] ], [ [[RDX_SELECT]], [[MIDDLE_BLOCK]] ]
+; CHECK-VF4IC1-NEXT:    ret i64 [[RES]]
+;
+; CHECK-VF4IC2-LABEL: define i64 @test_not_vectorize_select_no_min_reduction
+; CHECK-VF4IC2-SAME: (ptr [[SRC:%.*]]) {
+; CHECK-VF4IC2-NEXT:  entry:
+; CHECK-VF4IC2-NEXT:    br i1 true, label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
+; CHECK-VF4IC2:       vector.ph:
+; CHECK-VF4IC2-NEXT:    br label [[VECTOR_BODY:%.*]]
+; CHECK-VF4IC2:       vector.body:
+; CHECK-VF4IC2-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
+; CHECK-VF4IC2-NEXT:    [[VEC_IND:%.*]] = phi <4 x i64> [ <i64 0, i64 1, i64 2, i64 3>, [[VECTOR_PH]] ], [ [[VEC_IND_NEXT:%.*]], [[VECTOR_BODY]] ]
+; CHECK-VF4IC2-NEXT:    [[VEC_PHI:%.*]] = phi <4 x i64> [ <i64 -9223372036854775808, i64 -9223372036854775808, i64 -9223372036854775808, i64 -9223372036854775808>, [[VECTOR_PH]] ], [ [[TMP12:%.*]], [[VECTOR_BODY]] ]
+; CHECK-VF4IC2-NEXT:    [[VEC_PHI2:%.*]] = phi <4 x i64> [ <i64 -9223372036854775808, i64 -9223372036854775808, i64 -9223372036854775808, i64 -9223372036854775808>, [[VECTOR_PH]] ], [ [[TMP13:%.*]], [[VECTOR_BODY]] ]
+; CHECK-VF4IC2-NEXT:    [[VECTOR_RECUR:%.*]] = phi <4 x i64> [ <i64 poison, i64 poison, i64 poison, i64 0>, [[VECTOR_PH]] ], [ [[TMP7:%.*]], [[VECTOR_BODY]] ]
+; CHECK-VF4IC2-NEXT:    [[STEP_ADD:%.*]] = add <4 x i64> [[VEC_IND]], <i64 4, i64 4, i64 4, i64 4>
+; CHECK-VF4IC2-NEXT:    [[TMP0:%.*]] = add i64 [[INDEX]], 0
+; CHECK-VF4IC2-NEXT:    [[TMP1:%.*]] = add i64 [[INDEX]], 4
+; CHECK-VF4IC2-NEXT:    [[TMP2:%.*]] = getelementptr i64, ptr [[SRC]], i64 [[TMP0]]
+; CHECK-VF4IC2-NEXT:    [[TMP3:%.*]] = getelementptr i64, ptr [[SRC]], i64 [[TMP1]]
+; CHECK-VF4IC2-NEXT:    [[TMP4:%.*]] = getelementptr i64, ptr [[TMP2]], i32 0
+; CHECK-VF4IC2-NEXT:    [[WIDE_LOAD:%.*]] = load <4 x i64>, ptr [[TMP4]], align 4
+; CHECK-VF4IC2-NEXT:    [[TMP5:%.*]] = getelementptr i64, ptr [[TMP2]], i32 4
+; CHECK-VF4IC2-NEXT:    [[WIDE_LOAD3:%.*]] = load <4 x i64>, ptr [[TMP5]], align 4
+; CHECK-VF4IC2-NEXT:    [[TMP6:%.*]] = add <4 x i64> [[WIDE_LOAD]], <i64 1, i64 1, i64 1, i64 1>
+; CHECK-VF4IC2-NEXT:    [[TMP7]] = add <4 x i64> [[WIDE_LOAD3]], <i64 1, i64 1, i64 1, i64 1>
+; CHECK-VF4IC2-NEXT:    [[TMP8:%.*]] = shufflevector <4 x i64> [[VECTOR_RECUR]], <4 x i64> [[TMP6]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
+; CHECK-VF4IC2-NEXT:    [[TMP9:%.*]] = shufflevector <4 x i64> [[TMP6]], <4 x i64> [[TMP7]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
+; CHECK-VF4IC2-NEXT:    [[TMP10:%.*]] = icmp ugt <4 x i64> [[TMP8]], [[WIDE_LOAD]]
+; CHECK-VF4IC2-NEXT:    [[TMP11:%.*]] = icmp ugt <4 x i64> [[TMP9]], [[WIDE_LOAD3]]
+; CHECK-VF4IC2-NEXT:    [[TMP12]] = select <4 x i1> [[TMP10]], <4 x i64> [[VEC_IND]], <4 x i64> [[VEC_PHI]]
+; CHECK-VF4IC2-NEXT:    [[TMP13]] = select <4 x i1> [[TMP11]], <4 x i64> [[STEP_ADD]], <4 x i64> [[VEC_PHI2]]
+; CHECK-VF4IC2-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 8
+; CHECK-VF4IC2-NEXT:    [[VEC_IND_NEXT]] = add <4 x i64> [[STEP_ADD]], <i64 4, i64 4, i64 4, i64 4>
+; CHECK-VF4IC2-NEXT:    [[TMP14:%.*]] = icmp eq i64 [[INDEX_NEXT]], 0
+; CHECK-VF4IC2-NEXT:    br i1 [[TMP14]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP0:![0-9]+]]
+; CHECK-VF4IC2:       middle.block:
+; CHECK-VF4IC2-NEXT:    [[RDX_MINMAX:%.*]] = call <4 x i64> @llvm.smax.v4i64(<4 x i64> [[TMP12]], <4 x i64> [[TMP13]])
+; CHECK-VF4IC2-NEXT:    [[TMP15:%.*]] = call i64 @llvm.vector.reduce.smax.v4i64(<4 x i64> [[RDX_MINMAX]])
+; CHECK-VF4IC2-NEXT:    [[RDX_SELECT_CMP:%.*]] = icmp ne i64 [[TMP15]], -9223372036854775808
+; CHECK-VF4IC2-NEXT:    [[RDX_SELECT:%.*]] = select i1 [[RDX_SELECT_CMP]], i64 [[TMP15]], i64 0
+; CHECK-VF4IC2-NEXT:    [[CMP_N:%.*]] = icmp eq i64 0, 0
+; CHECK-VF4IC2-NEXT:    [[VECTOR_RECUR_EXTRACT:%.*]] = extractelement <4 x i64> [[TMP7]], i32 3
+; CHECK-VF4IC2-NEXT:    br i1 [[CMP_N]], label [[EXIT:%.*]], label [[SCALAR_PH]]
+; CHECK-VF4IC2:       scalar.ph:
+; CHECK-VF4IC2-NEXT:    [[SCALAR_RECUR_INIT:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[VECTOR_RECUR_EXTRACT]], [[MIDDLE_BLOCK]] ]
+; CHECK-VF4IC2-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ 0, [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY]] ]
+; CHECK-VF4IC2-NEXT:    [[BC_MERGE_RDX:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[RDX_SELECT]], [[MIDDLE_BLOCK]] ]
+; CHECK-VF4IC2-NEXT:    br label [[LOOP:%.*]]
+; CHECK-VF4IC2:       loop:
+; CHECK-VF4IC2-NEXT:    [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-VF4IC2-NEXT:    [[MIN_IDX:%.*]] = phi i64 [ [[BC_MERGE_RDX]], [[SCALAR_PH]] ], [ [[MIN_IDX_NEXT:%.*]], [[LOOP]] ]
+; CHECK-VF4IC2-NEXT:    [[SCALAR_RECUR:%.*]] = phi i64 [ [[SCALAR_RECUR_INIT]], [[SCALAR_PH]] ], [ [[MIN_VAL_NEXT:%.*]], [[LOOP]] ]
+; CHECK-VF4IC2-NEXT:    [[GEP:%.*]] = getelementptr i64, ptr [[SRC]], i64 [[IV]]
+; CHECK-VF4IC2-NEXT:    [[L:%.*]] = load i64, ptr [[GEP]], align 4
+; CHECK-VF4IC2-NEXT:    [[CMP:%.*]] = icmp ugt i64 [[SCALAR_RECUR]], [[L]]
+; CHECK-VF4IC2-NEXT:    [[MIN_VAL_NEXT]] = add i64 [[L]], 1
+; CHECK-VF4IC2-NEXT:    [[FOO:%.*]] = call i64 @llvm.umin.i64(i64 [[SCALAR_RECUR]], i64 [[L]])
+; CHECK-VF4IC2-NEXT:    [[MIN_IDX_NEXT]] = select i1 [[CMP]], i64 [[IV]], i64 [[MIN_IDX]]
+; CHECK-VF4IC2-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-VF4IC2-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i64 [[IV_NEXT]], 0
+; CHECK-VF4IC2-NEXT:    br i1 [[EXITCOND_NOT]], label [[EXIT]], label [[LOOP]], !llvm.loop [[LOOP3:![0-9]+]]
+; CHECK-VF4IC2:       exit:
+; CHECK-VF4IC2-NEXT:    [[RES:%.*]] = phi i64 [ [[MIN_IDX_NEXT]], [[LOOP]] ], [ [[RDX_SELECT]], [[MIDDLE_BLOCK]] ]
+; CHECK-VF4IC2-NEXT:    ret i64 [[RES]]
+;
+; CHECK-VF1IC2-LABEL: define i64 @test_not_vectorize_select_no_min_reduction
+; CHECK-VF1IC2-SAME: (ptr [[SRC:%.*]]) {
+; CHECK-VF1IC2-NEXT:  entry:
+; CHECK-VF1IC2-NEXT:    br i1 true, label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
+; CHECK-VF1IC2:       vector.ph:
+; CHECK-VF1IC2-NEXT:    br label [[VECTOR_BODY:%.*]]
+; CHECK-VF1IC2:       vector.body:
+; CHECK-VF1IC2-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
+; CHECK-VF1IC2-NEXT:    [[VEC_PHI:%.*]] = phi i64 [ -9223372036854775808, [[VECTOR_PH]] ], [ [[TMP10:%.*]], [[VECTOR_BODY]] ]
+; CHECK-VF1IC2-NEXT:    [[VEC_PHI1:%.*]] = phi i64 [ -9223372036854775808, [[VECTOR_PH]] ], [ [[TMP11:%.*]], [[VECTOR_BODY]] ]
+; CHECK-VF1IC2-NEXT:    [[VECTOR_RECUR:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[TMP7:%.*]], [[VECTOR_BODY]] ]
+; CHECK-VF1IC2-NEXT:    [[TMP0:%.*]] = add i64 [[INDEX]], 0
+; CHECK-VF1IC2-NEXT:    [[TMP1:%.*]] = add i64 [[INDEX]], 1
+; CHECK-VF1IC2-NEXT:    [[TMP2:%.*]] = getelementptr i64, ptr [[SRC]], i64 [[TMP0]]
+; CHECK-VF1IC2-NEXT:    [[TMP3:%.*]] = getelementptr i64, ptr [[SRC]], i64 [[TMP1]]
+; CHECK-VF1IC2-NEXT:    [[TMP4:%.*]] = load i64, ptr [[TMP2]], align 4
+; CHECK-VF1IC2-NEXT:    [[TMP5:%.*]] = load i64, ptr [[TMP3]], align 4
+; CHECK-VF1IC2-NEXT:    [[TMP6:%.*]] = add i64 [[TMP4]], 1
+; CHECK-VF1IC2-NEXT:    [[TMP7]] = add i64 [[TMP5]], 1
+; CHECK-VF1IC2-NEXT:    [[TMP8:%.*]] = icmp ugt i64 [[VECTOR_RECUR]], [[TMP4]]
+; CHECK-VF1IC2-NEXT:    [[TMP9:%.*]] = icmp ugt i64 [[TMP6]], [[TMP5]]
+; CHECK-VF1IC2-NEXT:    [[TMP10]] = select i1 [[TMP8]], i64 [[TMP0]], i64 [[VEC_PHI]]
+; CHECK-VF1IC2-NEXT:    [[TMP11]] = select i1 [[TMP9]], i64 [[TMP1]], i64 [[VEC_PHI1]]
+; CHECK-VF1IC2-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 2
+; CHECK-VF1IC2-NEXT:    [[TMP12:%.*]] = icmp eq i64 [[INDEX_NEXT]], 0
+; CHECK-VF1IC2-NEXT:    br i1 [[TMP12]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP0:![0-9]+]]
+; CHECK-VF1IC2:       middle.block:
+; CHECK-VF1IC2-NEXT:    [[RDX_MINMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[TMP10]], i64 [[TMP11]])
+; CHECK-VF1IC2-NEXT:    [[RDX_SELECT_CMP:%.*]] = icmp ne i64 [[RDX_MINMAX]], -9223372036854775808
+; CHECK-VF1IC2-NEXT:    [[RDX_SELECT:%.*]] = select i1 [[RDX_SELECT_CMP]], i64 [[RDX_MINMAX]], i64 0
+; CHECK-VF1IC2-NEXT:    [[CMP_N:%.*]] = icmp eq i64 0, 0
+; CHECK-VF1IC2-NEXT:    br i1 [[CMP_N]], label [[EXIT:%.*]], label [[SCALAR_PH]]
+; CHECK-VF1IC2:       scalar.ph:
+; CHECK-VF1IC2-NEXT:    [[SCALAR_RECUR_INIT:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[TMP7]], [[MIDDLE_BLOCK]] ]
+; CHECK-VF1IC2-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ 0, [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY]] ]
+; CHECK-VF1IC2-NEXT:    [[BC_MERGE_RDX:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[RDX_SELECT]], [[MIDDLE_BLOCK]] ]
+; CHECK-VF1IC2-NEXT:    br label [[LOOP:%.*]]
+; CHECK-VF1IC2:       loop:
+; CHECK-VF1IC2-NEXT:    [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-VF1IC2-NEXT:    [[MIN_IDX:%.*]] = phi i64 [ [[BC_MERGE_RDX]], [[SCALAR_PH]] ], [ [[MIN_IDX_NEXT:%.*]], [[LOOP]] ]
+; CHECK-VF1IC2-NEXT:    [[SCALAR_RECUR:%.*]] = phi i64 [ [[SCALAR_RECUR_INIT]], [[SCALAR_PH]] ], [ [[MIN_VAL_NEXT:%.*]], [[LOOP]] ]
+; CHECK-VF1IC2-NEXT:    [[GEP:%.*]] = getelementptr i64, ptr [[SRC]], i64 [[IV]]
+; CHECK-VF1IC2-NEXT:    [[L:%.*]] = load i64, ptr [[GEP]], align 4
+; CHECK-VF1IC2-NEXT:    [[CMP:%.*]] = icmp ugt i64 [[SCALAR_RECUR]], [[L]]
+; CHECK-VF1IC2-NEXT:    [[MIN_VAL_NEXT]] = add i64 [[L]], 1
+; CHECK-VF1IC2-NEXT:    [[FOO:%.*]] = call i64 @llvm.umin.i64(i64 [[SCALAR_RECUR]], i64 [[L]])
+; CHECK-VF1IC2-NEXT:    [[MIN_IDX_NEXT]] = select i1 [[CMP]], i64 [[IV]], i64 [[MIN_IDX]]
+; CHECK-VF1IC2-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-VF1IC2-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i64 [[IV_NEXT]], 0
+; CHECK-VF1IC2-NEXT:    br i1 [[EXITCOND_NOT]], label [[EXIT]], label [[LOOP]], !llvm.loop [[LOOP3:![0-9]+]]
+; CHECK-VF1IC2:       exit:
+; CHECK-VF1IC2-NEXT:    [[RES:%.*]] = phi i64 [ [[MIN_IDX_NEXT]], [[LOOP]] ], [ [[RDX_SELECT]], [[MIDDLE_BLOCK]] ]
+; CHECK-VF1IC2-NEXT:    ret i64 [[RES]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
   %min.idx = phi i64 [ 0, %entry ], [ %min.idx.next, %loop ]
   %min.val = phi i64 [ 0, %entry ], [ %min.val.next, %loop ]

 
 exit:
   %res = phi i64 [ %min.idx.next, %loop ]
   ret i64 %res
 }
 
 declare i64 @llvm.umin.i64(i64, i64)
 declare i16 @llvm.umin.i16(i16, i16)
+;; NOTE: These prefixes are unused and the list is autogenerated. Do not add tests below this line:
+; CHECK: {{.*}}