Rebased, Ping.

Moved finding subtree logic out of getTreeCost() to tryPartialVectorization().

Missed one change, removed braces at 3762.

Rebased, addressed remarks.

Ping.

Fixed all remarks. Also, add a solution for the same treeentry is used several times cost calculation at line 3615. Thanks for finding it.

In D57779#1655984, @ABataev wrote:

Will it work if the same treeentry is used several times in the tree? For example, in diamond merge? If the treeentry, used several times is not profitable?

I might be wrong, but I don't see any difference in terms of cost calculation for reused operations in partial or full vectorization. I mean, for example, if some group of operations has been vectorized and we plan to use those operations then we still need to calculate those operations costs, extract cost and etc. One another thing we don't want to calculate insert costs for the cost of gathering canceled elements(see getInsertCost()) for reused operations since those operations have been already vectorized anyway, I will fix that.

Added link to the article.

In D37648#1653860, @RKSimon wrote:

Abandon this? I think this is being handled by the (WIP) Attributor work to support dereference

no, I think I can rebase the change.

Fixed remarks, rebased.

In D57779#1644586, @dtemirbulatov wrote:

This was due to deciding to vectorize the whole tree(not partially) while revisiting seeds for partial vectorization. Fixed at line 3789.

oh, the decision for the whole vectorization was due to other changes in the BB.

Fixed regression issue on 401.bzip2 and others. This was due to deciding to vectorize the whole tree(not partially) while revisiting seeds for partial vectorization. Fixed at line 3789.
Here are Spec 2006 INT results:
before:
400.perlbench 9770 249 39.3 *
401.bzip2 9650 311 31.1 *
403.gcc 8050 191 42.1 *
429.mcf 9120 217 42.0 *
445.gobmk 10490 330 31.8 *
456.hmmer 9330 267 35.0 *
458.sjeng 12100 394 30.7 *
462.libquantum 20720 241 85.9 *
464.h264ref 22130 334 66.2 *
471.omnetpp 6250 249 25.1 *
473.astar 7020 284 24.7 *
483.xalancbmk 6900 170 40.7 *
Est. SPECint(R)_base2006 38.5
Est. SPECint2006 Not Run

In D57779#1642591, @ABataev wrote:

In D57779#1642570, @dtemirbulatov wrote:

Some of the results are worse than without the patch. Can we investigate why?

yes, I will focus on 401.bzip2, 429.mcf. but this SLP throttling supposes be off by default and it on here just to show the impact on tests.

Even if it off by default, I don't think it is a good idea to have the code that may lead to regressions when we could avoid that.

Some of the results are worse than without the patch. Can we investigate why?

yes, I will focus on 401.bzip2, 429.mcf. but this SLP throttling supposes be off by default and it on here just to show the impact on tests.

Here is SPEC CPU 2006 INT results:

ping

rebased.

ping

I wanted to see if this patch would help with a problem that I'm looking at, but I get this error when trying to build:

Yes, it should be "llvm::" , I will rebase the patch and I am thinking to suggest to you this solution in D64142.

Rebased.

Ping.

looks good to me.

rebased.

fixed formatting issue at line 1308.

Fixed remarks.

Fixed remarks.

Fixed all previous remarks, rebased.

Ping

Fixed typo at line 123.

rebased.

Rebased, fixed previous remarks. Here we still have InstructionsState and I have the full change with the state in TreeEntry but I prefer to break it in several reviews.

Looks good to me, just tryScheduleBundle() function type. I think we could simplify it later, @RKSimon @ABataev any comments?

Ping, if approved I am going to commit with "slp-throttling" disabled by default, it is enabled just to show the impact on the test.

Ping

Rebased.

Overall, I don't see any issues with linking TreeEntry and SchedularData with lane information.

Rebased, updated incorrect comment in treeTraversal() function.

Fixed issue with visiting the same node twice also added the assertation that we are not visiting any node twice and the assertion that all proposed nodes were visited.

Fixed incorrect algorithm implementation in findSubTree() fundction.

Rebased and addressed previous remarks.

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.