LGTM.

hmm, I have another failure with this change on my setup, now it is PR39774.ll. Probably, it might be sort algorithm differents of similar, since it just swap of two inserts. I don't have this failure if PR39774.ll is intact.

In D62938#1533142, @RKSimon wrote:

In D62938#1532286, @lebedev.ri wrote:

Please can you add a better explanation of the problem to the description of the patch?
I'm not sure what the problem is, you are allowed to drop nuw/nsw flags: https://rise4fun.com/Alive/plNm
So the new vectorized binop should simply take the smallest common subset of flags, which likely most often means no flags.

@dtemirbulatov It might be worth adding tests that check that we do retain the common subset?

fixed a typo.

Rebased, fixed all remarks.

In D62938#1533142, @RKSimon wrote:

In D62938#1532286, @lebedev.ri wrote:

Please can you add a better explanation of the problem to the description of the patch?
I'm not sure what the problem is, you are allowed to drop nuw/nsw flags: https://rise4fun.com/Alive/plNm
So the new vectorized binop should simply take the smallest common subset of flags, which likely most often means no flags.

@dtemirbulatov It might be worth adding tests that check that we do retain the common subset?

In D62938#1532286, @lebedev.ri wrote:

Please can you add a better explanation of the problem to the description of the patch?
I'm not sure what the problem is, you are allowed to drop nuw/nsw flags: https://rise4fun.com/Alive/plNm
So the new vectorized binop should simply take the smallest common subset of flags, which likely most often means no flags.

LGTM.

looks good to me.

Addressing last remarks, rebased.

oh, I notice some regression with the change for AArch64/matmul.ll and AArch64/transpose.ll. Maybe there is a way to isolate it with heuristics?

In D57779#1509166, @vporpo wrote:

I think the first throttling patch should implement a very simple and fast algorithm for finding the cut:

1. Add new fields to TreeEntry for Cost, ExtractCost and PredecessorsCost.
2. During getTreeCost() set the TE.Cost and TE.ExtractCost (as you did in an earlier version of the patch if I am not mistaken)
3. Do a single top-down traversal of the tree in reverse postorder and set the TE.PredecessorsCost equal to the cost of all the predecessor's costs until TE. While doing so, you can compare the cost of cutting just below TE by comparing the gather cost of TE versus the Cost + PredecessorsCost. This is very fast as you only need to visit each TreeEntry node once, so the complexity is linear to the size of the tree.
   
   For example, in slp-throttle.ll the bundle that needs to be scalarized [%add19, %sub22] has costs of Cost=1, ExtractCost = 0, PredecessorsCost=1 (because of bundle [%mul18, undef]). Cutting below the bundle has a cost of +1, while keeping it vectorized has a cost of +2 (Cost=1 + PredecessorsCost=1).
   
   This should be good-enough for most simple cases. We can improve it later, if needed, with follow-up patches. What do you think?

yes, Looks good.

Rebased.

ping

LGTM.

Looks good to me either.

Added comments to cutBranch() and extendSubTree() functions. Removed dupicate variable "I" in extendSubTree() function.

Again, the slp-throttling is on to just show the impact on SLP tests.

Looks like fixed all remark, rebased.

LGTM.

looks like "class nodes_iterator" definition at 1856 is not formatted properly.

Found typo in the previous upload.

Rebased. Simplified solution by removing leaves structure and any notion of branches. Left "slp-throttling" flag true by default just to show the impact on SLP tests.

Implemented tree/graph throttling solution.

LGTM.

Looks good to me. Abataev, any objections?

In D57779#1439895, @xbolva00 wrote:

Did you check the 462.libquantum 's regression?

Changed getTreeCost loop to condition "--I;".

Fixed remarks, removed Cost state from TreeEntry, turned cl::opt throttling flag false by default.

Fixed cost estimation for canceled elements to be inserted to interact with vectorized.
Replaced main throttling loop in reverse-post-order traversal as it was suggested in the previous remarks.
Making final decision on throttle inside getTreeCost() we don't need to hold cost estimations in TreeEntry.
Avoid vectorizing any flow instructions during partial vectorization.
Added cl::opt flag for Throtelling, it is now on by default to show the impact on tests, but during commit, I could make this option off by default to estimate the whole impact before enabling everywhere.
Here are the spec cup 2006 numbers before and after:

Delete unnecessary variables from getTreeCost().

Rebase the change, Fix Vasileios remarks.

Add cost calculation for in vectorizable tree operation to be extracted for the canceled tree elements use. Fix performance regression on Phoronix's c-ray-1.2.0 test-suite by avoiding to vectorize just one seed instruction. Spec 2006 numbers are unchanged with several instances of new vectorizations but not hot enough to change the numbers. Also, I noticed a good vectorizations example with Phoronix's encode-mp3-1.7.3 of two FFT kernels with ~8% faster for fft_short kernel and ~3% faster for fft_long on Intel(R) Core(TM) i7-6700HQ.

Change the decision of reducing tree if only the cost of vectorizing is too high and reduce the tree to the highest element of the tree that is minimally profitable.

In D57779#1410490, @xbolva00 wrote:

Since cost computing was changed, can you rerun spec benchmarks?

sorry, I found my previous result not quite reliable, I have changed my methodology, I will rerun spec benchmarks.

Fix cost calculation, fix the run-time error by adding external users for canceled elements in reduceTree(), add testcase.

looks like, I addressed the issue of leaf gather nodes.

oh, Rechecked the algorithm at 2660 at it looks correct. sorry.

I found an incorrect way of summing costs at line 2660, it should be backward loop here.

Fix several issues with cost estimation, add support for tree hight reduction even for profitable trees.

Clean the current SLP throttle implementation, Applied some Vasileios remarks. Here is spec 2k6 results before and after the change on i7-6700HQ.

This is quite rare cases when it decide to duplicate after limiting to a maximum number of elements of less than half of vector size and calculating cost of this transformation. Abandoning.

update duplicate.ll testcase.

removed bundle reordering by replacing pseudo instructions with real ones.

Introduced InstructionOrPseudo structure and removed "Instruction::Invoke" out of tryToRepresentAsInstArg() function with error example in invoke.ll testcase.

In D28907#1318422, @RKSimon wrote:

@dtemirbulatov Any movement on this? It'd be great to get this in for the 8.0 release!

LGTM, with @spatel remark about the comment.

Ops, I found a few typos, Formated tryToRepresentAsInstArg() and removed the second SRem from isRemainder().

Looks like I fixed all previous remarks also during testing I found two more issues with the change and I fixed both.

Implemented Map<Instruction*, std::pair<Value *Parent, unsigned Opcode> indexing for ScalarToTreeEntry, PseudoInstScheduleDataMap.
Added reorderBundles() function to reorder bundles that have common instructions according to instructions layout after SLP scheduling.

LGFM

Update after I found another couple of errors after additional testing the change. Here are changes:
Removed OpValue field out of PseudoScheduleData.
Forbid any bundles with non-alternative operations and remainder operation, see rem-bundle.ll.
Fixed error in setInsertPointAfterBundle() function by using getScheduleData() instead of getInstrScheduleData and if a bundle member is present multiple bundles at the same time then walk through the bundle to find the last scheduled member of the bundle. see insert-after-multiple-bundle.ll
Restore MemoryDependencies to SmallVector, we don't have to count a member presents in calculateDependencies().