The usage later and documentation above look for a set of references that are consecutive under some permutation. I.e., w/o gaps. The implementation below allows arbitrary gaps, and does not check for zero gaps, i.e., replicated references.

Would it be better to simply do a Pigeonhole sort, and perhaps call it isPermutedConsecutiveAccess():

1. Scan all references to find the one with minimal address. Bail out if any reference is incomparable with the running min.
2. Scan all references and set SortedIndices[i] = difference(VL[i], Minimum). Bail out if this entry is to be set more than once.

Note: it may be good to support replicated references, say when the gaps are internal to the vector to avoid loading out of bounds. Perhaps add a TODO.

Note: it may be good to have LAA provide some common support for both SLP and LV's InterleaveGroup construction, which share some aspects. Perhaps add a TODO.

Use computeConstantDifference() instead of computing it explicitly? It should compare GetUnderlyingObject()'s, if worthwhile, rather than doing so here.

Update above documentation accordingly.

Instead of returning the index when it's not Idx, may as well have getExtractIndex() return it always, and have the caller compare it to Idx?
While we're at it, may as well pass only E and have the callee get its Opcode.

The order which bestOrder() provides is then used to form a vector of instructions. Suggest to have this method supply the desired vector, given the instructions to permute.

and returns the mask for reordering operations, if it allows

should specify more accurately something like:
...and sets \p BestOrder to the identity permutation; otherwise returns False, setting \p BestOrder to either an empty vector or a non-identity permutation that allows...

Update above documentation.

Can the permutations be kept inside NumOpsWantsToKeepOrder, using OrdersType as its key, instead of holding them in OpOrders? So that one could later simply do

++NumOpsWantsToKeepOrder[CurrentOrder];

See, e.g., UniquifierDenseMapInfo in LSR.

Document what DirectOrderNum counts and/or have a more self-explanatory name similar to the original one, e.g., NumOpsWantToKeepOriginalOrder

Can add that NumOpsWantToKeepOriginalOrder holds the count for the identity permutation, instead of holding this count inside NumOpsWantsToKeepOrder along with all other permutations.

BestOrder >> CurrentOrder?

Better early exit by returning here.

This is pretty hard to follow, and deserves an explanation. Would be better to simply do something like ++NumOpsWantToKeepOrder[BestOrder].

Sink the emplace_back to after the handling of non-simple loads?

"BestOrder" >> "CurrentOrder", or "VLOrder"?

Reuse PointerOps and have Value *P0,1 = PointerOps.front,back() instead of LoadInst *L0,1 just to get their PointerOperand (and SCEV) later?

Better have sortPtrAccess() set "BestOrder" only if the given pointers are indeed consecutive once permuted, instead of checking here the Diff of max - min.

Comment that BestOrder is initialize to invalid values.
Perhaps set E = VL.size() here and assign E + 1, to match the later checks for initialized/unset values.

Can simplify by checking if BestOrder is the identify permutation at the end, as done at the end of sortPtrAccesses(); using getExtractIndex(Inst) which returns Idx even if it's equal to I. Better rename BestOrder here too.

Capture this "inversePermutation" in a method, to be called again below?

InsertPoint may be set twice to VL0?

Should we first inverse the permutation and then take its front()?

Would be good to have a testcase where this makes a difference and check it (one way or the other), if there isn't one already.

If only two operations are still allowed, ReorderedOps may as well stay Ops[1], Ops[0].
Provide the generalization below to any permutation when the assert can be dropped, i.e., in a separate patch which handles this TODO?

Provide Ops.size() as operand to constructor of ReorderedOps (multiple similar occurrences).

This redundant sequence of extractions from REORDER_SHUFFLE and insertions into TMP13 is hopefully eliminated later. Is the cost model ignoring it, or can we avoid generating it? Would be good to have the test CHECK the cost.

The documentation above does not say anything about consecutive access. It just states, that the pointers are sorted and that's it. I did it on purpose, so later we could reuse this function for masked loads|stores.
Masked loads are not supported yet, that's why in the SLPVectorizer I added an additional check for the consecutive access.

Tried, it does not work in many cases.

I don't want to add the new entry for operations, that do not require reordering. I'd better the code in another way.

I think it does not matter because the current order is the best order.

I need to use an iterator, will rework the code.

Just like I said, I did it for future support of masked loads|stores.

Check the boolean flag is faster than to perform N comparisons. That's why I'd prefer to leave it as is.

Missed it, thanks.

There are several tests already that test that this is correct code.
SLPVectorizer/X86/PR32086.ll, SLPVectorizer/X86/jumbled-load.ll, SLPVectorizer/X86/store-jumbled.ll etc.

Yes, InstCombiner will squash all these instructions into one shuffle. Yes, cost model is aware of these operations and ignores their cost (canReuseExtract() is intended to do this).

By "The documentation above" I meant the one example of a[i+2], a[i+0], a[i+1] and a[i+3] which is a permutation of consecutive addresses.

Masked loads and stores (will) also require that all pointers be within range of a single vector, right?

Then that should be fixed, worth opening a PR?

Understood; suggested before to simply document that one could alternatively hold the count for the identity permutation inside NumOpsWantsToKeepOrder map, but we're instead keeping it outside using NumOpsWantToKeepOriginalOrder counter.

The current order may not be the best order, the first time the tree is built, right?

Right; it could simplify the code though, and N is usually very small.

Very good, thanks.
Can CurrentOrder be used instead of I->getFirst()?
Can ++NumOpsWantToKeepOrder[CurrentOrder] work? After all the trouble...

May as well use E when resizing Mask.

Another inversePermutation?

Fold by feeding the constructor with the size.

1. I see.
2. Right

I'm not sure that this is a bug, it is a feature :) . computeConstantDifference() is used to get the difference between the pointer returned by the GetUnderlyingObject() and kind of a GEP %ptr, 0, n, where n is constant. But this function does not work if the first load element is from GEP %ptr, 0, m, not from %ptr, and others are from GEP %ptr, 0, m+1, GEP %ptr, 0, m+2 etc.

Added a comment to the declaration of NumOpsWantToKeepOrder

Yes, but this is the best order for this particular bundle. Anyway, I renamed it.

No, we cannot use CurrentOrder. I tried to reduce the memory usage and instead of copying the CurrentOrder in the newTreEntry() function I keep the ArrayRef for this order. But CurrentOrder is the local variable and it will be destroyed when we exit out of its declaration scope. And, thus, we will keep the reference to incorrect memory. Instead, I need to use the reference that will exist until the end of the vectorization process (as the key of the map)

Oh, yes, missed it, thanks.

Yup, thanks.

Reworked it, thanks.

Check for zero gaps, i.e., replicated references?
These are currently not supported, when checking canReuseExtract().

ok, right; computeConstantDifference() is lightweight. But it would be good to refactor a more time consuming variant which checks if getMinusSCEV returns a constant, and first compares UnderlyingObjects; and also AddressSpaces, following LoopVectorize.

OK, so sortPtrAccesses() can serve more general cases where max - min > VF. It would still be helpful to wrap it, and refactor the above code/usage inside an isPermutedConsecutiveAccess() method which would call sortPtrAccesses().

OK, right; it's clear why each Tree Entry should not hold an OrdersType object, and that newTreeEntry() should be given the object stored inside NumOpsWantToKeepOrder rather than the equivalent temporary CurrentOrder.

So ++NumOpsWantToKeepOrder[CurrentOrder] can work, but then newTreeEntry() will need to be given NumOpsWantToKeepOrder.find(CurrentOrder)->getFirst()?

Add a message to the assert.

"\a" >> "\p"

"DirectOrderNum" >> "NumOpsWantToKeepOriginalOrder" instead of adding the comment?

May be helpful to also dump CurrentOrder into dbgs().

Fold the size into the constructor.

// Assign initial value to of all items to E + 1 so we can check if the

// Assign to all items the initial value E + 1 so we can check if the

(if at least one element of ... ).

", by checking that no element of CurrentOrder still has value E + 1."
Note that there is no such check later.

It may be easier to read if instead of clearing CurrentOrder at each early exit, we break from the loop, and right after the loop check if it exited early and if (I < E) clear CurrentOrder and return false.

Agree, will add checks

Added checks for addressspace, comparison for underlying objects already were there.

Ok

This check is not required, it is checked automatically. We check that number of the extract elements is the same as the vector length at first. If later we try to write the index to element that does not equals E+1 it means that at least one element will still have E+1 as the value and we're have at least 2 elements with the same index.