Page MenuHomePhabricator

[LoopVectorize] Vectorize the reduction pattern of integer min/max with index.
Needs ReviewPublic

Authored by Mel-Chen on Feb 6 2023, 11:09 PM.

Details

Reviewers
ABataev
fhahn
Summary

Consider the following loops:

int idx = ii;
int max = mm;
for (int i = 0; i < n; ++i) {
  int x = a[i];
  if (max < x) {
    max = x;
    idx = i;
  }
}

and

int idx = ii;
int max = mm;
for (int i = 0; i < n; ++i) {
  int x = a[i];
  if (max <= x) {
    max = x;
    idx = i;
  }
}

Changes:

  • New recurrence kinds: SelectIVICmp and SelectIVFCmp. This is temporary. Eventually, SelectICmp/SelectFCmp should be able to fully support conditional scalar assignment. At that time, SelectIVICmp/SelectIVFCmp will be removed.
  • New recurrence Kinds: MinMaxFirstIdx and MinMaxLastIdx. This kind is not directly generated by function AddReductionVar, but converted from SelectIVICmp/SelectIVFCmp.

TODOs:

  • Now have not support that the min/max recurrence without exit instruction. Refer to test case smax_idx_max_no_exit_user.
  • Support the min/max recurrence in select(cmp()). Refer to test case smax_idx_select_cmp.
  • Support FP min/max recurrence.

Diff Detail

Event Timeline

Mel-Chen created this revision.Feb 6 2023, 11:09 PM
Mel-Chen requested review of this revision.Feb 6 2023, 11:09 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 6 2023, 11:09 PM
Mel-Chen retitled this revision from [LoopVectorize] Vectorize the reduction pattern of integer min/max with index. to [LoopVectorize] Vectorize the reduction pattern of integer min/max with index. (WIP).Feb 7 2023, 12:16 AM
Mel-Chen edited the summary of this revision. (Show Details)Feb 7 2023, 12:21 AM
Mel-Chen updated this revision to Diff 496034.Feb 8 2023, 11:40 PM

Rebase and update the command in test case.

Mel-Chen updated this revision to Diff 496879.Feb 13 2023, 2:07 AM

Changes:

  • Fix interleave code generation for SelectIVICmp and SelectIVFCmp.
  • Fix the internal compiler error for MinMaxFirstIdx and MinMaxLastIdx when -force-vector-width=1.
  • Update test cases. Add more run command lines.
Mel-Chen updated this revision to Diff 496947.Feb 13 2023, 5:51 AM

Changes:

  • Rebase
  • Split the patch of test case and implementation
  • Update FIXME
Mel-Chen edited the summary of this revision. (Show Details)Feb 13 2023, 5:57 AM
Mel-Chen updated this revision to Diff 497320.Feb 14 2023, 7:20 AM

Changes:

  • Remove function createInductionSelectCmpTargetReduction
  • Add function createSentinelValueHandling
  • Fix the start value of SelectCmp and MinMaxIdx

And then I don't know why all FIXME has been fixed, will confirm.

Mel-Chen updated this revision to Diff 497548.Feb 14 2023, 10:18 PM

Rebase and fix the check prefix in test cases.

Mel-Chen updated this revision to Diff 497615.EditedFeb 15 2023, 3:24 AM
Mel-Chen added a subscriber: test.

Changes:

  • Confirm the operands of intrinsic and cmp. Fixed test case @smax_idx_not_vec_1.
  • Format code.
Mel-Chen retitled this revision from [LoopVectorize] Vectorize the reduction pattern of integer min/max with index. (WIP) to [LoopVectorize] Vectorize the reduction pattern of integer min/max with index..Feb 15 2023, 3:24 AM
Mel-Chen edited the summary of this revision. (Show Details)

@fhahn Ping. What do you think of my approach? I am looking forward to your reply.

Mel-Chen updated this revision to Diff 499753.Thu, Feb 23, 12:22 AM

Changes:

  • Rebase
  • Fix the bug of predicate normalization
Mel-Chen updated this revision to Diff 504121.Fri, Mar 10, 6:05 AM

Rebase and update test case result.

fhahn added inline comments.Sun, Mar 19, 2:15 PM
llvm/include/llvm/Analysis/IVDescriptors.h
379

It would be helpful to document how the new system of recurrences depending on other recurrences would work I think, possibly also with an explanation of the whole approach in the patch description.

llvm/lib/Analysis/IVDescriptors.cpp
733

nit: Variables should start with upper case

also, move definition to use?

758

The naming here is a bit confusing now, NonPhi can be an increasing loop induction? In that case it would be a phi, right?

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
777

We are in the process of removing those kinds of global maps that are used to carry information used during codegen and later. Ideally the combination of values would be modeled explicitly in the exit block of the plan, but we are not there yet. This is the main reason for D132063 doing things the way it does.

3805

this would need documenting.

llvm/test/Transforms/LoopVectorize/smax-idx.ll
1

Could you add new tests as a separate patch?

Mel-Chen added inline comments.Wed, Mar 22, 7:31 AM
llvm/include/llvm/Analysis/IVDescriptors.h
379

Sure. I will document the whole approach. and update in the summary tomorrow.
Quickly explain the function of UserRecurPhi . The purpose of UserRecurPhi is to allow the recurrence to be used in the loop (loop internal use), and to ensure that the user is also a recurrence. UserRecurPhi will record the candidate user recurrence phi, and UserRecurKind will recored the excepted user recurrence kind. Currently I'm limiting candidates to one, but it should be possible to have more than one.

llvm/lib/Analysis/IVDescriptors.cpp
758

Yes, it's a little confusing here. It could be better to replace NonPhi with NonRecurPhi. By the way, are you interested in supporting full functional SelectCmp pattern? I think min max with index pattern really needs to depend on the SelectCmp to be safe.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
777

I see., but DependRecurrenceMasks exists for a reason. Consider the following case:

int idx = ii;
int foo = jj;
int max = mm;
for (int i = 0; i < n; ++i) {
  int x = a[i];
  if (max < x) {
    max = x;
    idx = i;
    foo = b[i];
  }
}

That mask has the chance to be reused, and I try to keep that flexibility. Of course, we can recalculate the mask for each reduction that needs a mask, but currently using the global maps to preserve the mask is a relatively simple method that I think of.
I have heard that VPlan is going to be extended to other blocks, could you share the relevant discussion links?

3805

Sure. Quick explanation: min/max recurrence should be done earlier than min max idx recurrence, because idx recurrence depends on the mask produced by min max recurrence. Here is to ensure that the recurrence dependencies are correct.

llvm/test/Transforms/LoopVectorize/smax-idx.ll
1

Of course. I will split an NFC patch tomorrow.

Mel-Chen updated this revision to Diff 507716.Thu, Mar 23, 6:08 AM

Split test case into parent revision.

Mel-Chen added inline comments.Thu, Mar 23, 6:13 AM
llvm/include/llvm/Analysis/IVDescriptors.h
379

Too busy today. The document will be available in next week.