BB vectorizer does not fuse shifts with multiplies

[sebpop]

Bugzilla Link	11973
Resolution	WONTFIX
Resolved on	Jul 01, 2017 06:17
Version	unspecified
OS	Linux
Attachments	testcase
CC	@hfinkel,@rotateright

Extended Description

Looking at the dumps of

clang -O2 test.c -mllvm -vectorize
-mllvm -debug-only=bb-vectorize
-mllvm -bb-vectorize-debug-pair-selection
-mllvm -bb-vectorize-debug-candidate-selection

when test.c does not contain coefficients that can be transformed into shifts, the vectorizer matches different pairable instructions than when it contains a multiple of 2.

For instance, when I replace the first write to w of the attached testcase with:
w++ = 2a - 5b + 7c;
The debugging dumps look like this:
BBV: looking at %mul = shl i8 %0, 1 <-> %3 = mul i8 %1, -5

Whereas if that first write to w is like this:
w++ = 3a - 5b + 7c;
we have the following candidate pair:
BBV: looking at %mul = mul i8 %0, 3 <-> %3 = mul i8 %1, -5
BBV: candidate pair %mul = mul i8 %0, 3 <-> %3 = mul i8 %1, -5

[llvmbot]

Hi Sebastian,

I am new to LLVM hands on however I have been following its development for some time.I would like to start by working on this bug.

Having gone through this bug's description, I would like to know the expected result for the given test case.I am sorry if my question seems irrelevant.

Regards,
Shahid

[llvmbot]

Hi,

At first instance it looks, this is due to missing "Asymmetric parings" indicated by Hal in this presentation,

http://llvm.org/devmtg/2012-04-12/Slides/Hal_Finkel.pdf

Is this the case?

Regards,
Shahid

[hfinkel]

Hi,

At first instance it looks, this is due to missing "Asymmetric parings"
indicated by Hal in this presentation,

http://llvm.org/devmtg/2012-04-12/Slides/Hal_Finkel.pdf

Is this the case?

This is not quite what I had in mind, but is similar. By asymmetric parings I meant the ability, for example, to form combination add/subtract vector instructions (which add some lanes and subtract others).

In this case, both operations are performing the same operation, and we should account for that. In other words, we need to un-canonicalize the shifts into multiplies when considering whether or not the two instructions can be paired.

To make this work, there are a few things that need to be updated. First, we need to generalize the part of the code that calls J->isSameOperationAs(I, ...) in BBVectorize::areInstsCompatible to pick up this kind of pairing. Further down in this function, the associated cost needs to be updated:
unsigned VCost = getInstrCost(I->getOpcode(), VT1, VT2);

Finally, BBVectorize::fuseChosenPairs() needs to be updated. Specifically, "Instruction *K = L->clone();" needs some generalization and also getReplacementInputsForPair() needs to be updated.

In short, there are a few places in the code that assume that both instructions in a pair have the same opcode, and these need to be updated.

I'd be happy to assist if you have any further questions. Thanks for looking at this!

Regards,
Shahid

[llvmbot]

Hello Hal,

Thanks for the clarification.Following is the approach I am contemplating.

Since BBVectorize::areInstsCompatible() returns true for pairable instructions and
further passes such as BBVectorize::fuseChosenPairs() and getReplacementInputsForPair() assume that the pairable instructions are same, I feel modifying the shifs into multiplies accordingly before returning from
BBVectorize::areInstsCompatible() should be enough to accomplish this.
Of course I need to generalize this for other cases too.

Does this make sense?

Regards,
Shahid

[hfinkel]

Hello Hal,

Thanks for the clarification.Following is the approach I am contemplating.

Since BBVectorize::areInstsCompatible() returns true for pairable
instructions and
further passes such as BBVectorize::fuseChosenPairs() and
getReplacementInputsForPair() assume that the pairable instructions are
same, I feel modifying the shifs into multiplies accordingly before
returning from
BBVectorize::areInstsCompatible() should be enough to accomplish this.
Of course I need to generalize this for other cases too.

Does this make sense?

Unfortunately, I think that we should not do it this way. No modifications should be made to the instructions in the basic block until we reach fuseChosenPairs() [we should not speculatively modify blocks, please remember that this is not "free"]. Changing the few things that I outlined to deal with pairs with different opcodes (in certain limited circumstances) is a better approach, and will also help later in dealing with asymmetric pairings.

Thanks again!

Regards,
Shahid

[llvmbot]

Thanks, got your point.

[llvmbot]

Hello Hal,

Sorry for the lack of updates.

With the ugly modification I was trying to check merging of scalar operation into vector for the given test case.

With the modification vectorizer is able to consider it as 'candidate pair', however could not get the vectorized instruction probably because the cost saving is equal to '0'.

What is the expected behavior if the cost saving is '0' ?

Regards,
Shahid

[hfinkel]

Hello Hal,

Sorry for the lack of updates.

With the ugly modification I was trying to check merging of scalar operation
into vector for the given test case.

With the modification vectorizer is able to consider it as 'candidate pair',
however could not get the vectorized instruction probably because the cost
saving is equal to '0'.

What is the expected behavior if the cost saving is '0' ?

A pair with a cost savings of 0 should still be considered for later DAG selection. The entire DAG currently needs a positive cost savings, but some individual candidate pairs in that DAG can have 0 cost savings.

Regards,
Shahid

[llvmbot]

Hello Hal,

Sorry for the lack of updates.

With the ugly modification I was trying to check merging of scalar operation
into vector for the given test case.

With the modification vectorizer is able to consider it as 'candidate pair',
however could not get the vectorized instruction probably because the cost
saving is equal to '0'.

What is the expected behavior if the cost saving is '0' ?

A pair with a cost savings of 0 should still be considered for later DAG
selection. The entire DAG currently needs a positive cost savings, but some
individual candidate pairs in that DAG can have 0 cost savings.

Confirmed, that the 'candidate pair' is rejected during DAG selection which is selecting best DAG based on depth & size.
Finding a proper test case is required to verify the actual fusion of pairs?

Regards,
Shahid

[hfinkel]

Hello Hal,

Sorry for the lack of updates.

With the ugly modification I was trying to check merging of scalar operation
into vector for the given test case.

With the modification vectorizer is able to consider it as 'candidate pair',
however could not get the vectorized instruction probably because the cost
saving is equal to '0'.

What is the expected behavior if the cost saving is '0' ?

A pair with a cost savings of 0 should still be considered for later DAG
selection. The entire DAG currently needs a positive cost savings, but some
individual candidate pairs in that DAG can have 0 cost savings.

Confirmed, that the 'candidate pair' is rejected during DAG selection which
is selecting best DAG based on depth & size.
Finding a proper test case is required to verify the actual fusion of pairs?

In general you'll want a profitable test case. Nevertheless, you might be able to force it vectorize by passing: -bb-vectorize-ignore-target-info -bb-vectorize-req-chain-depth=2 (or some small number).

Regards,
Shahid

[llvmbot]

Hello Hal,

Thanks for the information about options.

The induced inconsistency due to the dissimilar ops in the chosen pair list made me struggle for a while.Needed to modify the chosen pair list accordingly before actual fusion.

Now its able to fuse the instructions.Now I need to do some generalization.

Is there any direct way to verify for the correctness of the fusion?

Regards,
Shahid

[hfinkel]

Hello Hal,

Thanks for the information about options.

The induced inconsistency due to the dissimilar ops in the chosen pair list
made me struggle for a while.Needed to modify the chosen pair list
accordingly before actual fusion.

Now its able to fuse the instructions.Now I need to do some generalization.

That's great!

Is there any direct way to verify for the correctness of the fusion?

I don't think so; what kinds of errors would you like to catch? Regardless, you'll want to run a bunch of test cases (and run through the test suite). There may be no better way.

Regards,
Shahid

[llvmbot]

Hello Hal,

Thanks for the information about options.

The induced inconsistency due to the dissimilar ops in the chosen pair list
made me struggle for a while.Needed to modify the chosen pair list
accordingly before actual fusion.

Now its able to fuse the instructions.Now I need to do some generalization.

That's great!

Is there any direct way to verify for the correctness of the fusion?

I don't think so; what kinds of errors would you like to catch? Regardless,
you'll want to run a bunch of test cases (and run through the test suite).
There may be no better way.

'make check' reports failure for a test case "cycle.ll" with the following assertion; "!FoundVal && "Key already in new map?"
I am trying to figure it out.Do you have any specific deadline for this fix?

Regards,
Shahid

[hfinkel]

Hello Hal,

Thanks for the information about options.

The induced inconsistency due to the dissimilar ops in the chosen pair list
made me struggle for a while.Needed to modify the chosen pair list
accordingly before actual fusion.

Now its able to fuse the instructions.Now I need to do some generalization.

That's great!

Is there any direct way to verify for the correctness of the fusion?

I don't think so; what kinds of errors would you like to catch? Regardless,
you'll want to run a bunch of test cases (and run through the test suite).
There may be no better way.

'make check' reports failure for a test case "cycle.ll" with the following
assertion; "!FoundVal && "Key already in new map?"

I can try to provide some advice, but please provide a backtrace.

I am trying to figure it out.Do you have any specific deadline for this fix?

No.

Thanks again!

Regards,
Shahid

[llvmbot]

Hello Hal,

Thanks for the information about options.

The induced inconsistency due to the dissimilar ops in the chosen pair list
made me struggle for a while.Needed to modify the chosen pair list
accordingly before actual fusion.

Now its able to fuse the instructions.Now I need to do some generalization.

That's great!

Is there any direct way to verify for the correctness of the fusion?

I don't think so; what kinds of errors would you like to catch? Regardless,
you'll want to run a bunch of test cases (and run through the test suite).
There may be no better way.

'make check' reports failure for a test case "cycle.ll" with the following
assertion; "!FoundVal && "Key already in new map?"

I can try to provide some advice, but please provide a backtrace.

Thankfully, I found the issue and resolved it.

I am trying to figure it out.Do you have any specific deadline for this fix?

No.

Thanks again!

Regards,
Shahid