Rebased.

Well, ideally we should be able to handle any combination and nesting of scalars, vectors and aggregates in a unified way.
For example:

{float, <2 x float>, float},
{float, float, <2 x float>},
{{float, float}, <4 x float>, <2 x float>},
{{float}, {float}, [2 x float]}, 
{{{float, float}, float}, float}

etc.
This would require some redesign of the code, which is why I think it makes sense to have a single patch for all of them.

I think we cannot handle several similar cases with aggregates inside aggregates (e.g., [2 x {float, float}], {{float, float}, {float, float}}). Perhaps we could address some of these cases too with this patch? Please see the tests below:

Rebased.

@RKSimon any comments about the latest changes?

This fixes the issue reported by @Carrot. It updates getShallowScore() to better cope with extracts from consecutive locations of the same vector (see last lit test). @Carrot, if you have the time please verify that this patch no longer causes a regression. Thanks!

Thanks @Carrot, I will investigate the issue.

Rebased.

@RKSimon Yes, I will update this patch in a day or two.

Addressed latest comments

Just a couple more comments.

Addressed comments.

Addressed comments.

Addressed comments (and rebased).

No, there is no single BB. There can be more than one operand BBs that will have to be walked. For example, a TreeEntry in BB0 could have all its left operands in BB1 and all its right operands in BB2. In such case we would need to walk through both of them and perhaps keep the maximum cost? But anyway, given the lack of accuracy in the spill cost estimation I am not sure this is worth the trouble.

I guess it would be better if it visited all the BBs. You could traverse the VectorizableTree once and collect the BBs to be visited before you walk through them. Btw the TreeEntries now have operands, which can help you collect the BBs in the right order.
But I am not sure this is worth the trouble, because it looks to me that the spill cost estimation function is not very accurate in the first place. It only considers the spill cost over calls, and while doing so it is not comparing it against the spill cost of the scalar code, which if I am not mistaken could be equal to that of the vector code in many cases. Someone who knows more about the assumptions made here should probably comment on it.

Rebased.

Thanks for sharing the example.

I am probably missing out something, but isn't this profitable only if we have more than one of these scalar loads extracting from the same vector load? Perhaps we could use these scalar loads as seeds and do short top-down SLP?
Also isn't it better to run this after vectorizeStoreChains() ?

Abandoning this patch. The fix can now be found in D60897.

Fixed the compilation-time issue with the introduction of the user budget limit from D63948. Also added lit test for it.

OK let me try to create a test that causes a change in the IR.

Not sure what kind of test would be suitable for this change. It simply restricts the look-ahead heuristic to not visit more than 2 operands and 2 uses, which is not something visible in the output IR.

Let's ping some of the reviewers.
@RKSimon @ABataev @dtemirbulatov any comments?

Updated option variable names.

The fix for the compilation-time issue reported by @phosek is in D63948 .

Thank you @phosek for testing it, I am glad it fixed the issue.
Let me add reviewers. I will push the change as soon as it gets approved by someone.

Oops sorry about that @phosek . I wonder how none of the lit tests failed. Please try this one.

Fixed the failure.

Yes, I agree @lebedev.ri they should be options with some documentation describing what they do.
Let's first get a confirmation that this is the actual cause of the compilation-time increase.

Please try this patch @phosek . Please let us know if it fixes the compilation-time issue. Thanks!

Thanks, that would be really helpful @phosek . Let me create the quick patch.

I think There are two possible causes for the compilation time increase:

1. Line 901 : We can restrict the number of operands to a max of 2
2. Line 820: We can restrict the visited users to a ma x of 2.

I can either create a quick patch, or I can revert it. Either is fine.

Rebased.

Rebased.

Addressed comments and rebased.

Fixed crash in chromium reported by @rnk.

Yes, @RKSimon . It was posted in llvm-commits. I did reproduce it and I will update the patch with the fix + lit test.

This was reverted in r364111 since it was causing a failure in Chromium reported by @rnk.

Please commit the patch, I don't have commit access.

Rebased.

Thank you for the reviews. Please commit the patch.

Rebased

@ABataev @RKSimon any comments?

Hmm I am now getting the same failure as you @dtemirbulatov . I am not sure what was wrong before, but it seems that the change in PR39774.ll is no longer needed.

Removed changes in PR39774.ll.

Rebased.

I am not sure about the value safety assumptions here. Is there any unsafe-math flag that would allow us to override the integer overflow flags?

Rebased.

Thank you for the reviews. Please commit it if @ABataev is also happy with it.

I investigated the two AArch64 failing tests. These tests feature the exact problem that we are trying to solve with this look-ahead heuristic. A commutative instruction had operands of the same opcode that the current heuristic has no way of reordering in an informed way. The current reordering was just lucky to pick the proper one, while the look-ahead heuristic was reordering the operands according to the score. However, the problem was that the score calculation was not considering external uses and was therefore favoring a sub-optimal operand ordering.

Addressed the review comments.

Rebased.

Addressed @dtemirbulatov 's comment.

Thanks for committing the test @RKSimon . I will follow up on this soon.

Minor comment update.

Yes, I will take a look. Maybe it is worth using TTI for the scores after all.

Rebased.

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.

Thanks for the review. Please commit the change.