[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]

llvm/include/llvm/Analysis/IVDescriptors.h

37–39

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

610–630

Nice catch! Will update it.

657

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?

659–667

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

670

No, it does not provide signed or unsigned information.

673–675

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.

677–678

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

1089

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

[Mel-Chen]

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

365–366

Good find! Will correct it.

llvm/lib/Transforms/Utils/LoopUtils.cpp

1155

Sure, will do.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

3887

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

1593

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

657

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

3887

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

3887

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

3887

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