This is an archive of the discontinued LLVM Phabricator instance.

[SLP] Fix for PR31690: Allow using of extra values in horizontal reductions.
ClosedPublic

Authored by ABataev on Feb 8 2017, 12:41 PM.

Details

Summary

Currently, LLVM supports vectorization of horizontal reduction
instructions with initial value set to 0. Patch supports vectorization
of reduction with non-zero initial values. Also, it supports a
vectorization of instructions with some extra arguments, like:

float f(float x[], int a, int b) {
  float p = a % b;
  p += x[0] + 3;
  for (int i = 1; i < 32; i++)
    p += x[i];
  return p;
}

Patch allows vectorization of this kind of horizontal reductions.

Diff Detail

Event Timeline

ABataev created this revision.Feb 8 2017, 12:41 PM
RKSimon added a subscriber: RKSimon.Feb 8 2017, 2:25 PM
mkuper edited edge metadata.Feb 8 2017, 4:46 PM

So, I understand you decided to vectorize the failing case, instead of bailing on it?
I'm not sure this is a good idea. I'm pretty sure I can craft a test-case where this will retain all of the scalar computation, in addition to performing the scalar one (e.g. have all of %x1 - %x4 as extra arguments). If I understand this code correctly, the cost model will not get adjusted for this, so you'll end up vectorizing cases you really don't want to vectorize, just so you can perform the vector reduction.

Why do you prefer not to bail?

So, I understand you decided to vectorize the failing case, instead of bailing on it?
I'm not sure this is a good idea. I'm pretty sure I can craft a test-case where this will retain all of the scalar computation, in addition to performing the scalar one (e.g. have all of %x1 - %x4 as extra arguments). If I understand this code correctly, the cost model will not get adjusted for this, so you'll end up vectorizing cases you really don't want to vectorize, just so you can perform the vector reduction.

Why do you prefer not to bail?

You're not quite correct. For all extra args I'm creating a virtual instruction user (it is not an instruction actually, but a MapVector<Value *, DebugLoc> ExternallyUsedValues). In function buildTree() if the scalar is found in this MapVector, it is considered as externally used and added to the list of the externally used values with nullptr user (because it is not generated yet, see lines 971-977).

Each new External use registered in ExternalUses list adds a cost of extractvalue instruction (see function getTreeCost(), lines 1973-2000). So, this external use is taken into account in the cost model already.

If cost model allows vectorization with this extra extractvalue instruction, we start vectorization and when extractvalue instruction is generated, we replace the reference to extra arg in ExternallyUsedValues MapVector to this newly generated instruction/value (see lines 2848-2862).

After vectorization we pass all values stored in ExternallyUsedValues MapVector and add extra args/extractvalue extra args to the final reduction value (see lines 4469-4473).

ABataev updated this revision to Diff 87776.Feb 9 2017, 1:39 AM

Added some more comments

mkuper added a comment.Feb 9 2017, 6:29 PM

Oh, ok, I see what's going on now. I've misread the test result, and didn't notice how it's being treated. Sorry for the noise.
(It would have been easier, though, if you updated the patch description and/or added documentation to the original patch, instead of just reusing the description of the original commit).

Some minor comments inline.

lib/Transforms/Vectorize/SLPVectorizer.cpp
2858

Please also change the documentation of ExternalUses to explain that a nullptr "User" is legal, and what it means (Line 589).

2862

Add a meaningful message to the assert.

2864

I guess it's impossible for Vec to be a PHI here, because the real user is going to be a reduction operation, right?
If so, how is it possible for it to be a non-Instruction?

2867

I'd say either have no braces, or braces for both the if and the else block - this looks a bit weird.

mkuper added inline comments.Feb 9 2017, 6:30 PM
lib/Transforms/Vectorize/SLPVectorizer.cpp
2864

Er, actually, what I wrote above doesn't make sense.
Why can't it be a Phi?

ABataev marked 3 inline comments as done.Feb 10 2017, 11:56 AM
ABataev added inline comments.
lib/Transforms/Vectorize/SLPVectorizer.cpp
2864

It does not matter for Vec is it a PHI or not (PHI is an instruction also), it can be a constant, I believe, which is not an instruction.

ABataev updated this revision to Diff 88037.Feb 10 2017, 12:38 PM

Update after review

mkuper accepted this revision.Feb 10 2017, 12:57 PM

LGTM

lib/Transforms/Vectorize/SLPVectorizer.cpp
2864

If VecI is a PHI, std::next(VecI->getIterator()) may not be a valid insertion point, but, never mind, I realized VecI can't be a phi anyway (and below, we don't care about the case VecI is a phi, we care about the case the User is a phi...).
Never mind this.

This revision is now accepted and ready to land.Feb 10 2017, 12:57 PM
This revision was automatically updated to reflect the committed changes.