Rebased. PING

In D28907#2278838, @xbolva00 wrote:

Reping

Ping

Rebased. Moved InternalTreeUses population out of (UseScalar != U || !InTreeUserNeedToExtract(Scalar, UserInst, TLI)) limitation, since we have to consider every interal user for partial vectorization.

In D57779#2258046, @xbolva00 wrote:

Good enough for initial implementation?

yes, For me, it looks like ready.

Rebased. Ping.

Removed unnecessary check for "UserTE" at 3305.

Fixed remarks, rebased.

Corrected paper citation, added -slp-throttle=false to llvm/test/Transforms/SLPVectorizer/X86/slp-throttle.ll, rebased.

Rebased after rGb1600d8b8971

oh, I missed to fully remove from diff at 7269, Fixed

Rebased, Fixed.

Fixed.

Rebased, Ping

oh, sorry I misspelled:
For example, in the first loops, we could change from Entry1 TreeEntry::ProposedToGather to TreeEntry::NeedToGather status, but we later could encounter another use of this Entry1 and from another Entry2()let's say) with TreeEntry::Vectorize status and we could NOT tell difference with just canceled item and not considered to vectorize Entry. thus ExternalUses would not be properly populated.

Rebased, addressed comments

ping

Addressed remarks, rebased.

Addressed comments, rebased.

Addressed remarks, rebased.

ping

I found type and unformatted changes.

Rebased, addressed the comments.

Resolved comments

Rebased, Address comments.

Addressed the comment

Why do you need to compare flow and operation instructions count? Also, why use hardcoded 3 as a limit of vectorizable nodes?

and I removed any limitation and introduced TreeState to avoid rebuilding the tree repeatedly. Now without limitations, I could not see any regressions on compilable CPU2006 FP and Int.

Ping, Rebased.

Restoring accidentally removed comment.

Addressed comments.

Fix typo.

ping

The CPU2006 testing was done on a dedicated machine with i7-6700HQ (turbo disabled) with at least 30 repeats and "-march=core-avx2 -m64" flag applied.

Rebased, reestablished limiter to partially vectorize since I removed it a couple of revisions back. I have SPEC CPU 2006 ~1% improvement in 464.h264ref and ~0.3% 433.milc and 482.sphinx3. Looks like I don't have any performance regressions at C and C++ compilable and runnable CPU2006 tests. With this revision, I fixed regressions compared to my previous change at the following tests: 471.omnetpp, 450.soplex, 482.sphinx3, 433.milc. Also estimated runtime increase for the SLP pass overall for SPECINT is the same as before from ~0.1% to 0.3%.

I measured the total time increase for SPEC2006 INT using "-ftime-trace" just for the SLP pass with "-mllvm -slp-throttle=true" and "-mllvm -slp-throttle=false" for the same compiler and the difference is about ~0.1%. This is for the last revision.

I found a build error with 453.povray, I was missed to set successful vectorization status, this revision fixes the issue.

Rebased, removed limiter to minimal subtree hight of 3 elements after correcting getInsertCost() now those examples look good on benchmarking, added cost base estimations when to avoid throttling: "Tree cost" + "All reducible cost" > -SLPCostThreshold, corrected the error in findSubTree() to sort all positive elements from a tree instead of first n-elements.

Rebased, removed isGoodSubTreeToVectorize() function because there is just one user to this function. Now, I think the change is ready to review, Please review this revision.

Rebased, added the following changes:

• removed TreeState from the proposed change since after fixing getInsertCost I could not observe any regressions.
• reduced default number of cost recalculations to 32 after noticing the new approach to find a subtree works efficiently.
• added support for reductions.

Changed getInsetCost() to correct insert cost calculation by allowing getEntryCost to handle entries that proposed to gather similarly as NeedToGather entries.

Rebased, Removed tree traversal approach and implemented suggestion by Alexey Bataev : "Did you think about recalculating the cost of the reduced tree instead of using a scheme with cost subtraction?", This looks like more efficient than tree traversal.

In D57779#1924824, @wwei wrote:

Do you have any plan to support throttling for horizontal reduction?

yes, I noticed some regression with my first implementation, but certainly, it worth adding after basic functionality.

Did you think about recalculating the cost of the reduced tree instead of using a scheme with cost subtraction? This looks to be a lot more natural way. I mean, in the same loop, where we try to vectorize the original tree, try to reduce the tree (+, maybe, check that the cost for the removed nodes is going to be negative) and then just recalculate the cost of the reduced tree? The current scheme looks >overcomplicated. This is just a suggestion.

I am doing now the whole tree cost substruction in the main cutPath() loop, except spill cost and we usually don't need it unless CallInst occurs. And I am thinking it is better to follow the tree structure.

Replaced to remove_if at 5207

Replaced auto with "SmallVector<std::unique_ptr<TreeState>, 8>::iterator " at 5207

Rebased, fix regression in pr35497.ll with extra extract instruction, it was caused by partial vectorization preventing the reduction by changing BB too early. Added functionality of doing throttling as the last one but without rebuilding tree again. It is done by saving tree states for profitable trees, this could allow us to estimate which vectorization to choose based on the cost in the future.

Resolved previous remarks, except that we are still using "cost subtraction" and we don't need now to call getTreeCost() all the time we can now subtract all cost components, except spill cost, in the main path traversing loop. Fixed issue with incorrect cost calculation in getInsertCost().

Update once again.

oh, sorry, it l

Try to restore the context.

Rebased after committing the first part as NFC, it looks like resolved all remarks.

Removed record seeds functionality.

Addressed remarks.

In D57779#1740020, @xbolva00 wrote:

Re-ping