@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.

Minor change: Fixed double printing of TreeEntry index in the dumpVectorizableTree() debug function.

Thanks for the review. Please commit the change, I don't have commit access.

Fixed the formatting issue.

Please try not to introduce a new Node structure or a new graph. You can use TreeEntry instead and you can add any necessary fields to it.

Updated getBestOperand() to use getLookAheadScore() for Load and Constant, not just Opcode.

Addressed comments and updated lit test.

Rebased.

@ABataev requested this to be checked in before the look-ahead patch. Please commit this if it looks good, I don't have commit access.

Thank you for the reviews, and @uabelho for reporting the issue.
Please commit the patch as I don't have commit access.

Removed triple.

Added FileCheck

Accept undef in OpLastLane if Op contains an Instruction.

Cleaned up the lit test variable names.

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

Thank you for the reviews. @RKSimon any more comments ?

Addressed the latest comments.

Addressed @ABataev 's comments.

Addressed the comments and also moved the reordering-related functions inside the VLOperands class.

I am not sure how to proceed with the operandorder.ll test. @ABataev do you know we would give higher priority to broadcasts?

Updated getBestOperand() to better handle undefs. This fixes the regression in crash_smallpt.ll.

Rebased + some minor changes.

Addressed the comments.

Fixed doxygen tags.

I also rebased to support the commutative predicates of D59992.

Thanks @RKSimon . Moving the operator<<() within the EdgeInfo struct fixes the build issue with clang 7.0.1.

Please commit this, I don't have commit access.

Correct me if I am wrong, but I think your algorithm can only remove the rightmost branch of the SLP graph (and maybe several of them if they are close by), as StopAt is a single index in VectorizableTree and we remove all nodes > StopAt.
I think this could be improved if we could find all possible entries where we could stop at, not just one of them. Then, in the final traversal, we could remove all branches starting from each of these nodes all the way to the leaves.
Also, I think the Delta in reduceTreeCost() should not be needed as we should run this regardless of whether the original tree is profitable or not.

Hi Florian, yes I am happy with the changes, thanks!
Just please try to add an assertion that checks that the graph is a tree (see inline comment) to make sure that the graph is the one we expect.