Page MenuHomePhabricator

[LoopVectorize][CostModel] Choose smaller VFs for in-loop reductions with no loads/stores
Needs ReviewPublic

Authored by RosieSumpter on Tue, Nov 16, 1:49 AM.

Details

Summary

For loops that contain in-loop reductions but no loads or stores, large
VFs are chosen because LoopVectorizationCostModel::getSmallestAndWidestTypes
has no element types to check through and so returns the default widths
(-1U for the smallest and 8 for the widest). This results in the widest
VF being chosen for the following example,

float s = 0;
for (int i = 0; i < N; ++i)
  s += (float) i*i;

which, for more computationally intensive loops, leads to large loop
sizes when the operations end up being scalarized.

In this patch, the default max width has been changed from 8 to the
smallest legal int width (if the legal int widths are set) in the case
where ElementTypesInLoop is empty (i.e. in-loop reductions without any
loads or stores). This means VF=4 is chosen instead for the above
example. However, this impacts other targets, and there may be another
solution.

Diff Detail

Event Timeline

RosieSumpter created this revision.Tue, Nov 16, 1:49 AM
RosieSumpter requested review of this revision.Tue, Nov 16, 1:49 AM
Herald added a project: Restricted Project. · View Herald TranscriptTue, Nov 16, 1:49 AM
RosieSumpter edited the summary of this revision. (Show Details)Tue, Nov 16, 1:51 AM
lebedev.ri added inline comments.
llvm/test/Transforms/LoopVectorize/AArch64/smallest-and-widest-types.ll
47–48

Where is ElementTypesInLoop populated?
LoopVectorizationCostModel::collectElementTypesForWidening() suggests that PHI nodes are also queried.

sdesmalen added inline comments.
llvm/test/Transforms/LoopVectorize/AArch64/smallest-and-widest-types.ll
47–48

The function collectElementTypesForWidening() collects types for the following reasons:

  • Types of loads/stores, because these are used in computing a safe dependence distance (and also to have a sensible/natural VF as maximum VF).
  • Types of unordered reductions, in order to avoid generating vector PHI nodes that span multiple registers when the VF is too wide. In-order reductions are not considered, because those PHI nodes remain scalar after vectorization.

If we consider *more* types in the loop in collectElementTypesForWidening(), e.g. for in-order reductions or extends, then this leads to regressions; any type larger than the maximum loaded/stored type will limit the maximum VF. If the maximum VF is limited, then any VF upto the wider maximum will not be considered by the cost-model. So in general, it's better not to limit the VF for those reasons and leave it up to the cost-model to choose the best VF.

In the test-case that @RosieSumpter added, there are no loads/stores and there is no vector PHI node because the reduction is ordered, so it considers any VF up-to the widest-possible VF based on an i8 element type (even if the loop operates on a larger size). The cost-model then only considers the throughput cost, and the per-lane cost is no different between VF=4 and VF=16, so it favours VF=16. It does not consider the additional code-size cost when the operation is scalarized.

I guess the alternative choices are to:

  • Look through the operands of the ordered reduction operation, as well as any casts/extends on those operands, and only consider these element types in collectElementTypesForWidening() if there are no loads/stores in the loop. This heuristic gets quite complicated I think.
  • Consider the code-size cost for in-order reductions, so that it favours shorter VFs (I'm not sure if this is desirable, as it may regress other cases where code-size isn't relevant).

Because the case is so niche (i.e. a loop with *only* in-order reductions), @RosieSumpter thought it made sense to fall back to a more sensible default instead.

I think there is no single right choice, i'm not sure why 32 is more right than 8 or 64 here, for everything?
I'd think this should be in costmodel somewhere, not hardcoded.

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

I suspect this should be querying datalayout for the minimal integer size?

dmgreen added inline comments.Tue, Nov 16, 3:00 PM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
6353

This deliberately excludes InLoopReductions from the maximum width of the register - because the phi remains scalar and it's useful for integer reductions under MVE where they can sum a vecreduce(v16i32 sext(v8i32)) in a single operation. That might not be as useful for float types - and the example loop you showed with no loads/stores in the loop is much less likely for integer - it will already have been simplified.

Perhaps we just remove this for ordered (float) reductions? Or does that lead to regressions?

sdesmalen added inline comments.Wed, Nov 17, 12:44 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
6353

This deliberately excludes InLoopReductions from the maximum width of the register - because the phi remains scalar and it's useful for integer reductions under MVE where they can sum a vecreduce(v16i32 sext(v8i32)) in a single operation.

Yes, the same is true for SVE. There is also code in the cost-model to recognise the extend to the wider type.

I think the actual reason for the reduction-code being here is to avoid ending up with vector PHIs that are too wide (out-of-loop reduction). The checks for in-loop reductions were added later because (1) there is no vector PHI and (2) that it doesn't limit the VF too early so that it lets the cost-model code consider the wider VFs for the reason you described.

Perhaps we just remove this for ordered (float) reductions? Or does that lead to regressions?

I don't think we should add specific knowledge to limit the VF for fp-reductions here, because that means adding target-specific knowledge to the collectElementTypesForWidening, which is something that the cost-model should decide on. Also it would lead to regressions.

dmgreen added inline comments.Wed, Nov 17, 8:04 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
6353

Yeah, we added it in https://reviews.llvm.org/D93476. I would have no objections to removing this for ordered reductions or float types I don't think. There is no such thing (as far as I understand) as an extending in-order float reduction, and we can rely on the UF for things that will become wider-than-legal vectors.

Matt added a subscriber: Matt.Wed, Nov 17, 12:05 PM
RosieSumpter edited the summary of this revision. (Show Details)
  • If there are no element types, only set the max width to 32 if there are no legal int sizes set, otherwise set it to the smallest legal int width.
  • update X86/funclet.ll test.
sdesmalen added inline comments.Mon, Nov 22, 1:41 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
6327

I think the MaxWidth should remain 8 if DL returns no smallest legal integer type? (or if there's no specific datalayout defined)

RosieSumpter edited the summary of this revision. (Show Details)
  • Don't set max width to 32 if there are no legal int widths set (leave as 8)
RosieSumpter marked an inline comment as done.Mon, Nov 22, 1:55 AM
  • Remove changes to LoopVectorize/pr32859.ll and LoopVectorize/pr36983.ll tests
fhahn added inline comments.Mon, Nov 22, 2:40 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
6353

Would it be possible to use TTI to pick the min/max type width to use there for the reduction, which would encode the target specific knowledge?

llvm/test/Transforms/LoopVectorize/AArch64/smallest-and-widest-types.ll
47–48

I think picking the smallest integer type as max width comes with its own problems unfortunately. By choosing 32 bit as max width on AArch64, won't we pessimize codegen for loops with fp16 in loop reductions (by choosing VF 4 instead of VF 8) for example?

It is hard to say what if there are similar impacts on other targets.