[LoopVectorize]Teach Loop Vectorizer about interleaved memory access

[• HaoLiu]

Summary

Hi,

Early in this month, I added a patch to teach Loop Vectorizer about interleaved data access in D8820. According to the code review comments. I've made a lot of changes. This new patch is attached. It will identify and vectorize interleaved Accesses into "Loads/Stores + ShuffleVectors".
E.g. It can translate following interleaved loads (If vector factor is 4):

for (i = 0; i < N; i+=3) {
    R = Pic[i];       // Load R color elements
    G = Pic[i+1];     // Load G color elements
    B = Pic[i+2];     // Load B color elements
    ... // do something to R, G, B
}

Into

%wide.vec = load <12 x i32>, <12 x i32>* %ptr               ; load for R,G,B
%R.vec = shufflevector %wide.vec, undef, <0, 3, 6, 9>    ; mask for R load
%G.vec = shufflevector %wide.vec, undef, <1, 4, 7, 10>  ; mask for G load
%B.vec = shufflevector %wide.vec, undef, <2, 5, 8, 11>  ; mask for B load

Or it can translate following interleaved stores (If vector factor is 4):

for (i = 0; i < N; i+=3) {
    ... do something to R, G, B
    Pic[i] = R;     // Store R color elements
    Pic[i+1] = G;     // Store G color elements
    Pic[i+2] = B;     // Store B color elements
}

Into

%RG.vec = shufflevector %R.vec, %G.vec, <0, 1, 2, ..., 7>
%BU.vec = shufflevector %B.vec, undef, <0, 1, 2, 3, u, u, u, u>
%interleaved.vec = shufflevector %RG.vec, %BU.vec,
            <0, 4, 8, 1, 5, 9, 2, 6, 10, 3, 7, 11>  ; mask for interleaved store
store <12 x i32> %interleaved.vec, <12 x i32>* %ptr         ; write for R,G,B

This patch mainly does:

(1) Identify interleaved access. (As some situation can not be covered corrently, I've added a TODO.)
(2) Transfer the indentified interleaved access to ShuffleVectors and Load/Store.
(3) Add a new pass in AArch64 backend to match the interleaved load/store with stride 2,3,4 to ldN/stN intrinsics.

I also added a new target hook to calculate the cost. (As I don't know too much about other targets, I just estimated it roughly.) It can be improved to be more accurate.

For the correctness, I've tested on AArch64 target with LNT, EEMBC, SPEC2000, SPEC2006, which can all pass.
For the performance, as there are other issues could forbid many vectorization opportunities, I don't see obvious improvements. But some benchmarks like EEMBC.RGBcmy and EEMBC.RGByiq are expected to have huge improvements (6 time

[• HaoLiu]

include/llvm/Analysis/LoopAccessAnalysis.h

589

Done.

[rengolin]

include/llvm/Analysis/LoopAccessAnalysis.h

403

Ouch, no!

If you do this, than a perfectly valid sequence like this:

group.eraseFromMap(Map);
group.getDelta(); // there's no way to know that this won't work

will segfault.

A quick fix would be to leave the deletion to whomever is calling the function, so it's clear on the lifetime of the object:

group.eraseFromMap(Map);
group.getDelta();
delete group;
group.getReverse(); // this is obviously wrong

But again, it seems to me that such logic is spread out too much.

So a better fix would be to coalesce all of it into a class in itself. One that contains the maps, the groups, and the control over the lifetime of all its groups in a consistent way, without requiring the caller to know about it.

I'm ok with the temporary solution, as long as you add a FIXME to that effect.

[anemet]

include/llvm/Analysis/LoopAccessAnalysis.h

722–723

I've only started looking at this patch but I have a quick initial, more fundamental comment.

You are modifying an analysis pass (LoopAccessAnalysis). Please add support for printing the new information gathered by the analysis. Please also add tests under test/Analysis/LoopAccessAnalysis to verify the new information.

You may even want separate out the patch for the analysis part (LAA + tests) from the transformation parts (LV + tests + etc).

[• HaoLiu]

I've updated a new patch according to the comments from Renato and Adam. This patch adds a new class InterleavedAccessInfo to handle the analysis about interleaved accesses.

Review please.

Thanks,
-Hao

include/llvm/Analysis/LoopAccessAnalysis.h

403

That's reasonable.

I've added a new class InterleavedAccessInfo to manage this.

722–723

Hi Adam,

I've undated the patch to support printing the new information. I added more test cases as well.

I didn't separate patch as I think there are already a lot of history comments on both parts. Also I think the bound between analysis part and transformation part is clear.

Anyway, I can still separate this patch if you insist.

[mzolotukhin]

Hi Hao,

Please find some comments from me inline. I'll get back to review a bit later.

Also, I think it's a good idea to separate the part for LoopAccessAnalysis part into a separate patch. I think it's fine to keep it in one patch during review (to keep the history), but I'd suggest committing it separately when they are ready. It'll help tracking down any potential issues that could be exposed later.

Thanks,
Michael

include/llvm/Analysis/LoopAccessAnalysis.h

325

We require Align!=0 here, but in the constructor below we explicitly set it to 0. Is one of these unused and could be removed?

495–496

Please fix the indentation here.

include/llvm/Analysis/TargetTransformInfo.h

448

s/vecotor/vector/

449–451

This comment seems to be outdated - there are no arguments SubTy, Index, or Gap in the declaration below.

include/llvm/Analysis/TargetTransformInfoImpl.h

306

Why the cost is Delta?

include/llvm/CodeGen/BasicTTIImpl.h

534

s/divied/divided/

546–547

Am I getting it correctly, that VecTy is the type of 'combined' vector?
I.e. if we have a stride=2, VF=4, and ScalarTy=i32, then VecTy would be <8 x i32>, and SubVT would be <4 x i32>? I'm not sure I've completely understood this part, so please correct me if I'm wrong.

If that's true, then the cost computation doesn't seem correct. Extract 1st or 2nd element from the wide vector isn't the same as extracting odds or even elements.

551

Was it supposed to be +=?

558–564

What's the difference between computing costs for stores and loads?

[• HaoLiu]

Also, I think it's a good idea to separate the part for LoopAccessAnalysis part into a separate patch. I think it's fine to keep it in one patch during review (to keep the history), but I'd suggest committing it separately when they are ready. It'll help tracking down any potential issues that could be exposed later.

Michael, I agree with you and I'll separate the patch when committing.

I've refactored the patch according to comments from Michael.

Review please.

Thanks,
-Hao

include/llvm/Analysis/LoopAccessAnalysis.h

325

Removed the unused constructor.

495–496

Fixed.

include/llvm/Analysis/TargetTransformInfo.h

448

Done.

449–451

Fixed.

include/llvm/Analysis/TargetTransformInfoImpl.h

306

Previously I though there are 'Delta' instructions each costs 1.
Regarding all the default cost in other getXXXCost is 1, I've changed it to be "1".

include/llvm/CodeGen/BasicTTIImpl.h

546–547

Yes, you are right.

The cost is not only "Extract" cost, it also plus the "Insert" cost.

Say we interleaved load two vectors:

%vec = load <8 x i32>, <8 x i32>* %ptr
%v0 = shuffle %vec, undef, <0, 2, 4, 6>
%v1 = shuffle %vec, undef, <1, 3, 5, 7>

The cost consist of 2 parts:

(1) load of <8 x i32>
(2) extract %v0 and %v1 from %vec.

The cost of (2) is estimated as 2 parts:

(a) extract elements at: 0, 1, 2, 3, 4, 5, 6, 7
(b) insert elements 0, 2, 4, 6 into %v0 and insert elements 1, 3, 5, 7 into %v1

The interleaved store is similar.

551

Fixed.

558–564

Say we interleaved store two vectors:

%v0_v1 = shuffle %v0, %v1, <0, 4, 1, 5, 2, 6, 3, 7>
store <8 x i32> %v0_v1, <8 x i32>*

It has two main differences:
(1) The direction is different. It firstly extract elements from two sub vectors and then insert into a wide vector (interleaved Load firstly extract elements from a wide vector and then insert into sub vectors)
(2) The interleaved store doesn't allow gaps, which means we must have member of index 0 (with even elements) and member of index 1 (with odd elements). But interleaved load allows gaps, it could only load even elements such as:

%vec = load <8 x i32>, <8 x i32>* %ptr
%v0 = shuffle <8 x i32> %vec, undef, <0, 2, 4, 6>

This is still beneficial and cheaper than scalar loads.

I've refactored this function to add a new parameter of indices for interleaved load.

[rengolin]

In D9368#175501, @HaoLiu wrote:

Michael, I agree with you and I'll separate the patch when committing.

Unless you can guarantee that trunk will work with just the first patch (ie. you have tested both equally), I don't think it's a good idea to split the patch. The analysis does nothing without the actual vectorisation, and vice versa.

It's a big patch, yes, but also this is a big change. I don't see what splitting the patches would gain us.

The patch now looks more like what we had planned in the beginning, so as long as all comments are addressed, and all tests pass, I'm happy.

Thank you for the effort of bringing this up again.

cheers,
--renato

[• HaoLiu]

In D9368#175547, @rengolin wrote:

In D9368#175501, @HaoLiu wrote:

Michael, I agree with you and I'll separate the patch when committing.

Unless you can guarantee that trunk will work with just the first patch (ie. you have tested both equally), I don't think it's a good idea to split the patch. The analysis does nothing without the actual vectorisation, and vice versa.

It's a big patch, yes, but also this is a big change. I don't see what splitting the patches would gain us.

The patch now looks more like what we had planned in the beginning, so as long as all comments are addressed, and all tests pass, I'm happy.

Thank you for the effort of bringing this up again.

cheers,
--renato

Renato, I also agree with you. I think to commit separately as two patches or commit as a whole patch are similar and have no big differences.

Thanks,
-Hao

[mzolotukhin]

Hi Hao,

Thanks for updating the patch, another bunch of comments from me inline.

Also, sorry for that I give the feedback in parts - it's hard to find enough time to review the entire patch all at once. I know that it might be a bit frustrating sometimes, but in fact I really appreciate your work and see how things converge:)

Thanks,
Michael

include/llvm/Analysis/TargetTransformInfo.h

447–457

Nitpick: Alignment and AddressSpace aren't documented.

lib/Analysis/LoopAccessAnalysis.cpp

918–926

Please add some comments on this struct and its members.

961–962

Using empty() is more efficient than size()==0.

1051–1052

Could we use a range loop here?

1055

Range-based loop?

1059–1060

Why not to return right after we discovered the block needs predication?

1075–1076

What's the rationale behind this? It might be inefficient to vectorize a group with a huge gap, but isn't it a question for cost-model rather than for the analysis?

1118–1126

Could we just check if PosA dominates PosB?

[• HaoLiu]

In D9368#176086, @mzolotukhin wrote:

Hi Hao,

Thanks for updating the patch, another bunch of comments from me inline.

Also, sorry for that I give the feedback in parts - it's hard to find enough time to review the entire patch all at once. I know that it might be a bit frustrating sometimes, but in fact I really appreciate your work and see how things converge:)

Thanks,
Michael

Hi Michael,

Thanks for your comments, which really help me a lot. I've updated a new patch accordingly.

Review please.

Thanks,
-Hao

include/llvm/Analysis/TargetTransformInfo.h

447–457

Done.

lib/Analysis/LoopAccessAnalysis.cpp

918–926

Done.

961–962

Good idea!

1051–1052

Done.

1055

Done.

1059–1060

It's slightly different.
We still support a predicted block if it doesn't have load/store. Because the vectorization of interleaved loads/stores won't break any dependences.
But if a predicted block has loads/stores, we need to handle an interleave group contains mixed normal loads/stores and predicted loads/stores.

1075–1076

This is just a conservative way. I think generally if a group missing more than half members, it is not very beneficial to do vectorization. Also it sounds not reasonable to still call it "interleaved" group.

But I agree with you that it's cost-model's work to decide whether it is beneficial.
The new patch keeps all load groups.
There is also a new situation that: the cost of a load group with a huge gap may even be expensive than the scalar operations. Then I think we need to replace with scalar operations. I've added a FIXME in the new patch as I haven't found an efficient way to fix this.

1118–1126

A good idea!

[rengolin]

lib/Analysis/LoopAccessAnalysis.cpp

1059–1060

This might be a case for indexed loads on AVX, but for now, let's keep it simple. :)

1075–1076

I also agree that the cost model should get this right, but currently, there is no way it can do that.

However, since the interleaved vectorisation is not enabled by default, I think keeping all the groups and fixing the cost model later is the right thing to do.

[rengolin]

Thanks Hao,

I think we're good to go. Michael, any more concerns?

Once we land this in, it'll be easier to test it and fix the issues created by this patch without affecting the rest.

cheers,
--renato

[anemet]

In D9368#174895, @HaoLiu wrote:

I've updated a new patch according to the comments from Renato and Adam. This patch adds a new class InterleavedAccessInfo to handle the analysis about interleaved accesses.

Thanks, Hao. I'll look at this today.

Adam

[mzolotukhin]

Hi Hao,

Please find more remarks from me inline, andI think this is the last bunch of comments from me. With them properly addressed I'm fine with committing the patch. However, I'd also like to hear from Adam regarding the LoopAccessAnalysis part, since he's been working actively on it.

And again, thanks for working on this, it's a much-needed feature!

Michael

include/llvm/Analysis/LoopAccessAnalysis.h

408

Should it be unsigned?

lib/Analysis/LoopAccessAnalysis.cpp

988

I think you missed my question earlier on this part.

This algorithm is clearly quadratic, which is dangerous for compile time. We need to either make it linear, or add some limits (e.g. if number of accesses > 100, give up and don't even try to group them).

Also, if we separate it into two phases: 1) grouping accesses, 2) finding write-after-write pairs, I think we can make it more efficient. Since it's sufficient to compare against any access from a group, we'll be quadratic on the number of groups, not the number of accesses. And when we look for WaW pairs, we can only look only inside a group, not across all accesses in the loop. Does it sound reasonable, or am I missing something?

lib/Transforms/Vectorize/LoopVectorize.cpp

703–712

This change is unnecessary.

1676

Nitpick: s/I.E/I.e./

1756–1757

Maybe it's worth mentioning here that though ConcatenateTwoVectors could extend a vector with UNDEFs, that only could happens with the last vector in the set.

Currently implementation guarantees that, but with the code evolving in future it can be easily violated if it's not stated clearly. Maybe an assertion could be even better here (like if it's not the last pair of vectors, then their sizes should be the same), but it might be an overkill.

1764

Could we just assign TmpList to VecList?

1823

Should we iterate to VF instead of UF here? PtrParts contains VF elements, right?

1835–1836

I'm not sure it's correct if we vectorize *and* unroll the loop. Don't we need to adjust the pointer according to which unrolling-part we are at (instead of using 0)?

1857

Name CallI is very misleading.

1857–1858

Name CallI is very misleading.

1904–1906

Could you please provide an example when this triggers? I'm a bit concerned about legality of this cast.

1919–1920

The name is misleading.

4871

s/even expensive/even more expensive/

test/Transforms/LoopVectorize/interleaved-accesses.ll

2

Is it possible to use noalias attributes for arguments and drop -runtime-memory-check-threshold=24?

[anemet]

Hi Hao,

Thinking about this a bit more, why are we collecting the InterLeaveGroups in LAA? LAA provides loop dependence information and computing this additional, unrelated information comes at a cost. Clients other than LV would pay for this without using it. I think that the InterLeaveGroups analysis should probably live in LV.

What do you think? Let me know if I am missing something from an earlier discussion.

Adam

[• HaoLiu]

I've updated a new patch refactored according to Michael's comments.

Review please.

Thanks,
-Hao

In D9368#176830, @mzolotukhin wrote:

Hi Hao,

Please find more remarks from me inline, andI think this is the last bunch of comments from me. With them properly addressed I'm fine with committing the patch. However, I'd also like to hear from Adam regarding the LoopAccessAnalysis part, since he's been working actively on it.

And again, thanks for working on this, it's a much-needed feature!

Michael

lib/Analysis/LoopAccessAnalysis.cpp

988

For the first question. Previously, I thought you meant to improve the insert member method.
Anyway, I think the algorithm is quadratic, the paper says:

This relies on the pivoting order in which the pairs of accesses are processed and  
reduces the complexity of the grouping algorithm: we iterate over O(n^2 ) pairs of
loads and stores (where n is the number of loads and stores)

But I think we don't need to worry about compile time:

(1) The "n" is only the number of stride loads/stores (|Stride| > 1)
(2) For a case with a lot of loads and stores, it possiblely can not pass previous dependence check, because it could have a lot of runtime memory check or have memory conflict. So it returns early.

On the other hand, if a loop indeed can pass dependence check. say if it has 100 loads, we should analyze the interleave accesses as vectorization on the possible interleave groups can really give us a lot of benefit.

988

For the second question. I think it is slightly different. We should not only consider about Group and Group, a group and a single store may break the dependence.
Say, A[i] = a; // (1)

B[i] = b;          // (2)
A[i+1] = c;      // (3)

The combine of (1) and (3) may break the dependence on "A[i] - B[i]" pair even though B[i] is not in a group.
So I think we should search all the write-write pairs. If we separate into two phases, we'll have to calculate the distance again. I think it may increase the compile time.

lib/Transforms/Vectorize/LoopVectorize.cpp

1823

Slightly different.
'PtrParts' contains UF vectors, and each vector has VF elements.
Here, firstly we want the pointer vector in current unroll part, I.e. 'PtrParts[Part]'.
Then for each pointer vector ''PtrParts[Part]', we want the pointer in lane 0.

E.g.

for (unsigned i = 0; i < 1024; i+=2) {
     A[i] = i;
}

If VF is 4 and UF is 2. Then we'll have two unroll parts:
part 1:

A[0] = 0;
A[2] = 2;
A[4] = 4;
A[6] = 6;

part 2:

A[8] = 8;
...

For this case, 'PtrParts' contains two vectors:

Vector 1 consists pointers to: A[0], A[2], A[4], A[6]
Vector 2  consists pointers to: A[8], A[10], A[12], A[14]

Then we extract lane 0 from Vector 1 to get a pointer pointing to A[0], so that we can use it to load A[0-7] and after that, we can extract A[0, 2, 4, 6] from A[0-7].

If the loads/stores are reverse, we need the pointer in last lane. E.g. the access sequences will be "A[1022], A[1020], A[1018], A[1016]", the last lane is the pointer to A[1016]". We can load A[1016-1023] to extract A[1016, 1018, 1020, 1022].

1835–1836

Yes, we need.
As the above comment says, we get vectors consist of pointers in all unroll parts.

1904–1906

A test case called @int_float_struct tests the interleaved load group:

struct IntFloat {
    int a;
    float b;
 };

 void int_float_struct(struct IntFloat *A) {
    int SumA;
    float SumB;
    for (unsigned i = 0; i < 1024; i++)  {
      SumA += A[i].a;
      SumB += A[i].b;
    }
    SA = SumA;
    SB = SumB;
  }

You can find this case in "interleaved-accesses.ll". The int-float can be long-double, or any pointer types, as long as the structure has elements of the same size.

Actually I have better case:

struct IntFloat {
  int a;
  float b;
};

void int_float_struct(struct IntFloat *A, struct IntFloat *B) {
    for (unsigned i = 0; i < 1024; i++)  {
      B[i].a = A[i].a + 1;
      B[i].b = A[i].b + 1.0;
    }
  }

Unfortunately, this case can not be vectorized as it can not pass dependence check. As we have following code in isDependent() (LoopAccessAnalysis.c):

if (ATy != BTy) {
  DEBUG(dbgs() <<
        "LAA: ReadWrite-Write positive dependency with different types\n");
  return Dependence::Unknown;
}

I think this is a bug. We don't need to check types as we will check dependences based on the memory object size. by removing such code I don't see any failures in benchmarks.
Anyway, as such code, I can not give a test for interleaved write group.

[• HaoLiu]

Thinking about this a bit more, why are we collecting the InterLeaveGroups in LAA? LAA provides loop dependence information and computing this additional, unrelated information comes at a cost. Clients other than LV would pay for this without using it. I think that the InterLeaveGroups analysis should probably live in LV.

What do you think? Let me know if I am missing something from an earlier discussion.

Adam

Hi Adam,

It's easy to move such analysis to LV, but I think it reasonable to analyze interleaved accesses in LoopAccessAnalysis:

(1) Regarding the name "LoopAccessAnalysis", which is responsible for analyzing accesses in a loop. The interleaved access group is a special kind of access in loop.
(2) For clients other than LV, it could disable or enable such analysis. Or we could disable it by default and LV calls function like "analyzeInterleaving()" to do analysis. To achieve this is easy.
(3) For other clients, I think we may also need to modify the memory dependence analysis, which is now dedicated to analyze dependences for loop vectorizer.

Thanks,
-Hao

[• HaoLiu]

test/Transforms/LoopVectorize/interleaved-accesses.ll

2

Hi Michael,

Do you mean by adding "-scoped-noalias". I tried but it doesn't work. I think maybe the runtime check is different from normal alias analysis.

[anemet]

In D9368#176907, @HaoLiu wrote:

It's easy to move such analysis to LV, but I think it reasonable to analyze interleaved accesses in LoopAccessAnalysis:

(1) Regarding the name "LoopAccessAnalysis", which is responsible for analyzing accesses in a loop. The interleaved access group is a special kind of access in loop.

True, I named it LAA because it’s a parallel dependence analysis framework to DependenceAnalysis but the focus is the same: dependence analysis plus run-time alias check generation for may-alias accesses.

I don’t have a problem adding things to the analysis that are free to compute even if it’s only used by a single client of the analysis pass (consider Ashutosh’s recent StoreToInvariantAddress changes). Here however we’re adding a potentially costly new analysis only required by a single client.

(2) For clients other than LV, it could disable or enable such analysis. Or we could disable it by default and LV calls function like "analyzeInterleaving()" to do analysis. To achieve this is easy.

Not really. This is an analysis pass, transform passes may depend on it and the pipeline manager will run this pass depending on transform pass requirements and possibly rerun it if it got invalidated by prior transformations.

As an example, consider this scenario. LAA is performed because of Loop Distribution. We end up not distributing the loop so the result of the analysis is intact and won’t be rerun. Then comes LV but the analysis is lacking the interleaved access analysis part.

Admittedly, we currently have a hack in LAA with regard to symbolic strides which would be similar to what you’re proposing. That however is more of shortcoming of how LAA was split out from LV rather than an example to follow.

(3) For other clients, I think we may also need to modify the memory dependence analysis, which is now dedicated to analyze dependences for loop vectorizer.

I am not sure I understand this point. Can you please elaborate?

Thanks,
Adam

Thanks,
-Hao

[mzolotukhin]

test/Transforms/LoopVectorize/interleaved-accesses.ll

2

No, I meant changing declaration from this:

define void @foo(%struct.ST2* nocapture readonly %A, %struct.ST2* nocapture %B)

to

define void @foo(%struct.ST2* noalias nocapture readonly %A, %struct.ST2* noalias nocapture %B)

It'll tell that A and B don't alias, and thus we won't need runtime checks for them.

[mzolotukhin]

lib/Analysis/LoopAccessAnalysis.cpp

988

Hm.. I'm reading the paper from here:
http://domino.research.ibm.com/library/cyberdig.nsf/papers/EFD6206D4D9A9186852570D2005D9373/$File/H-0235.pdf
And it says:

This relies on the pivoting order in which pairs of accesses are processed, and implies that the complexity of the grouping algorithm is linear in the number of loads and stores.

I'm not sure if it's safe to assume that the dependence check won't be passed. E.g. we might have the following case:

struct A {
int x,y;
};
struct A points[100];
for (int iter = 0; iter < 10000; iter++) { // not to be unrolled
  for (int i = 0; i < 100; i++) { // this loop will be completely unrolled
    points[i].x++;
  }
  // some other computations on the points
}

When the innermost loop is unrolled, we get 100 interleaving accesses, which will require 10^4 pairwise comparisons. I agree that we theoretically can optimize it better if we are not limited on time. However, if a programmer decides to increase number of points by a factor of 10, the compile time might slow down 100x, which won't be acceptable.
I think we have a lot of optimizations that could theoretically find the best solution if they are allowed to consume infinite number of time, however, we usually have some thresholds for them (such thresholds often don't prevent one from catching the cases the optimization is aimed for, but they guard against rare but very nasty cases when the compiler might work for hours).

For the second question, my understanding is that we should have two groups: {A[i], A[i+1]} and {B[i]}. Then we check if an access from the first group can alias with an access from the second group - I think we don't have to check every access in a group for this kind of reasoning. I.e. if leaders of the groups might alias, then any member of the first group can alias with any member of the second group (and if the leaders don't alias, then we can probably assume that the groups are totally independent of each other). Am I missing something here?

lib/Transforms/Vectorize/LoopVectorize.cpp

1823

Thanks for the explanation, sounds good.

1904–1906

It makes sense, thanks for the explanation!

[• HaoLiu]

In D9368#177057, @anemet wrote:

In D9368#176907, @HaoLiu wrote:

It's easy to move such analysis to LV, but I think it reasonable to analyze interleaved accesses in LoopAccessAnalysis:

(1) Regarding the name "LoopAccessAnalysis", which is responsible for analyzing accesses in a loop. The interleaved access group is a special kind of access in loop.

True, I named it LAA because it’s a parallel dependence analysis framework to DependenceAnalysis but the focus is the same: dependence analysis plus run-time alias check generation for may-alias accesses.

I don’t have a problem adding things to the analysis that are free to compute even if it’s only used by a single client of the analysis pass (consider Ashutosh’s recent StoreToInvariantAddress changes). Here however we’re adding a potentially costly new analysis only required by a single client.

(2) For clients other than LV, it could disable or enable such analysis. Or we could disable it by default and LV calls function like "analyzeInterleaving()" to do analysis. To achieve this is easy.

Not really. This is an analysis pass, transform passes may depend on it and the pipeline manager will run this pass depending on transform pass requirements and possibly rerun it if it got invalidated by prior transformations.

As an example, consider this scenario. LAA is performed because of Loop Distribution. We end up not distributing the loop so the result of the analysis is intact and won’t be rerun. Then comes LV but the analysis is lacking the interleaved access analysis part.

Admittedly, we currently have a hack in LAA with regard to symbolic strides which would be similar to what you’re proposing. That however is more of shortcoming of how LAA was split out from LV rather than an example to follow.

(3) For other clients, I think we may also need to modify the memory dependence analysis, which is now dedicated to analyze dependences for loop vectorizer.

I am not sure I understand this point. Can you please elaborate?

I previously thought LoopAccessAnalysis is specific for LV, because there are a lot of LV specific data like C

In D9368#177057, @anemet wrote:

In D9368#176907, @HaoLiu wrote:

It's easy to move such analysis to LV, but I think it reasonable to analyze interleaved accesses in LoopAccessAnalysis:

(1) Regarding the name "LoopAccessAnalysis", which is responsible for analyzing accesses in a loop. The interleaved access group is a special kind of access in loop.

True, I named it LAA because it’s a parallel dependence analysis framework to DependenceAnalysis but the focus is the same: dependence analysis plus run-time alias check generation for may-alias accesses.

I don’t have a problem adding things to the analysis that are free to compute even if it’s only used by a single client of the analysis pass (consider Ashutosh’s recent StoreToInvariantAddress changes). Here however we’re adding a potentially costly new analysis only required by a single client.

(2) For clients other than LV, it could disable or enable such analysis. Or we could disable it by default and LV calls function like "analyzeInterleaving()" to do analysis. To achieve this is easy.

Not really. This is an analysis pass, transform passes may depend on it and the pipeline manager will run this pass depending on transform pass requirements and possibly rerun it if it got invalidated by prior transformations.

As an example, consider this scenario. LAA is performed because of Loop Distribution. We end up not distributing the loop so the result of the analysis is intact and won’t be rerun. Then comes LV but the analysis is lacking the interleaved access analysis part.

Admittedly, we currently have a hack in LAA with regard to symbolic strides which would be similar to what you’re proposing. That however is more of shortcoming of how LAA was split out from LV rather than an example to follow.

(3) For other clients, I think we may also need to modify the memory dependence analysis, which is now dedicated to analyze dependences for loop vectorizer.

I am not sure I understand this point. Can you please elaborate?

Hi Adam,

I think LoopAccessAnalysis is a specific analysis for LV, so it's reasonable to put interleaved access analysis in an analysis specific for LV. If LoopAccessAnalysis is not specific for LV, I agree that we should not put it here. Currently I don't have idea about how other clients could use such interleave information.

But I still wonder how "other" clients use this analysis, as it has a lot of LV specific code like "CanVecMem, force-vector-width, force-vector-interleave", .... I wonder how "other" clients could use such analysis. Adam, do you have any example about other clients using LoopAccessAnalysis?

Thanks
-Hao

[• HaoLiu]

lib/Analysis/LoopAccessAnalysis.cpp

988

I agree with you. I could also find many similar thresholds. I'll add such limitation to the patch.

I think you are right for the second question. I'll try to implement this in the next patch.

[anemet]

In D9368#177506, @HaoLiu wrote:

I think LoopAccessAnalysis is a specific analysis for LV, so it's reasonable to put interleaved access analysis in an analysis specific for LV. If LoopAccessAnalysis is not specific for LV, I agree that we should not put it here. Currently I don't have idea about how other clients could use such interleave information.

But I still wonder how "other" clients use this analysis, as it has a lot of LV specific code like "CanVecMem, force-vector-width, force-vector-interleave", .... I wonder how "other" clients could use such analysis. Adam, do you have any example about other clients using LoopAccessAnalysis?

Sure, I already mentioned both clients: Transforms/Scalar/LoopDistribute.cpp and the still pending Ashutosh's Loop versioning pass in D9151.

Regarding your first specific question on CanVecMem, the basic design principle for splitting out LAA fron LV was to continue to provide the high-level LV-specific answers (i.e. CanVecMem) but also provide more lower-level/generic information about the dependences and run-time checks so that other passes could also use them (see APIs like: getInterestingDependences, getMemoryInstructions, getRuntimeChecks and getInstructionsForAccess).

Your other question was about force-vector-width, etc. These influence what dependences are acceptable for LV for its specific view of the dependence information. The solution here was to provide subtypes like *Vectorizable (see Dependence::DepType). These "subtypes" provide further classification of the dependence. LV uses these to allow vectorization of certain Backward dependences.

Loop Distribution does not use this classification since it only cares about forward vs. backward dependences.

Thus the difference is exposed to the clients and they can chose to treat these types differently or uniformly.

Adam

[• HaoLiu]

In D9368#177534, @anemet wrote:

In D9368#177506, @HaoLiu wrote:

I think LoopAccessAnalysis is a specific analysis for LV, so it's reasonable to put interleaved access analysis in an analysis specific for LV. If LoopAccessAnalysis is not specific for LV, I agree that we should not put it here. Currently I don't have idea about how other clients could use such interleave information.

But I still wonder how "other" clients use this analysis, as it has a lot of LV specific code like "CanVecMem, force-vector-width, force-vector-interleave", .... I wonder how "other" clients could use such analysis. Adam, do you have any example about other clients using LoopAccessAnalysis?

Sure, I already mentioned both clients: Transforms/Scalar/LoopDistribute.cpp and the still pending Ashutosh's Loop versioning pass in D9151.

Regarding your first specific question on CanVecMem, the basic design principle for splitting out LAA fron LV was to continue to provide the high-level LV-specific answers (i.e. CanVecMem) but also provide more lower-level/generic information about the dependences and run-time checks so that other passes could also use them (see APIs like: getInterestingDependences, getMemoryInstructions, getRuntimeChecks and getInstructionsForAccess).

Your other question was about force-vector-width, etc. These influence what dependences are acceptable for LV for its specific view of the dependence information. The solution here was to provide subtypes like *Vectorizable (see Dependence::DepType). These "subtypes" provide further classification of the dependence. LV uses these to allow vectorization of certain Backward dependences.

Loop Distribution does not use this classification since it only cares about forward vs. backward dependences.

Thus the difference is exposed to the clients and they can chose to treat these types differently or uniformly.

Adam

I see. That make sense.

Thanks,
-Hao

[• HaoLiu]

Updated a new patch refactored according to Michael and Adam.
There are two main changes:

(1) Add a threshold MaxInterleaveStride to avoid analyzing accesses with too large stride.
(2) Move the code about analyzing interleaved accesses in LoopAccessAnalysis to LoopVectorizer.

Review please.

Thanks
-Hao

test/Transforms/LoopVectorize/interleaved-accesses.ll

2

I tried this, but it still can not work for some cases like @test_struct_store4. It is a known problem with our runtime memory checks. It will check the dependences in the same array.
E.g. for (i = 0; i < n; i+=4) {

  A[i] = a;
  A[i+1] = b;
  A[i+2] = c;
  A[i+3] = d;
}

A lot of runtime checks with be generated for pairs in {A[i], A[i+1], A[i+2], A[i+3]} and will break the threshold.

[• HaoLiu]

I met a bug in Phabricator. It automatically removed all reviewers when I uploading a new patch. Now I've added reviewers back.

Thanks,
-Hao

[anemet]

lib/Analysis/LoopAccessAnalysis.cpp

790–791

Please split out of this part of the change -- a cleanup, and commit it separately (and upate this patch for easier read)

794–796

I think that these two cases are quite different. The first is essentially proving that accesses like A[2*i] and A[2*i + 1] are independent. This is true in general not just for vectorization. Thus we should be returning NoDep rather than BackwardVectorizable.

Please also add more comments/examples, it took me a long time to figure this out (hopefully I did at the end). Please also add LAA tests.

804–816

I am not sure I follow why you change the structure of the MaxSafeDepDistBytes logic here. Why aren't you simply comparing MaxSafeDepDistBytes with TypeByteSize * NumIter * Stride?

Looks like this will modify the existing behavior for stride=1 which is probably not what you intend.

[• HaoLiu]

Updated a new patch refactored the LoopAccessAnalysis about dependence check on strided accesses.

It's difficult to understand the logic about dependences, so I added many comments to describe it.

Review please.

Thanks,
-Hao

lib/Analysis/LoopAccessAnalysis.cpp

790–791

Hi Adma,

I Agree. I'll do that when commiting the patch.

794–796

Hi Adam,

You are right. I've updated a new patch refactored this logic. I added a lot of new test cases as well.

804–816

I think preivous logic is not correct. If "Distance > MaxSafeDepDistBytes", it is not safe to do vectorization.

[• HaoLiu]

Updated a new patch with slight modifications.

Review please.

Thanks,
-Hao

lib/Analysis/LoopAccessAnalysis.cpp

804–816

Sorry, previously I misunderstood the MaxSafeDepDistBytes. The new patch follows the meaning of MaxSafeDepDistBytes, it also has the same logic for stride = 1.

I also found a problem with MaxSafeDepDistBytes. It cannot handdle cases with different kinds of types. like:

void foo(int *A, char *B) {
    for (unsigned i = 0; i < 1024; i++) {
        A[i+2] = A[i] + 1;
        B[i+2] = B[i] + 1;
    }
}

I think we should use MaxFactor, which stands for the maximum number of iterations to be vectorized & unrolled. I've added a FIXME in the patch.

[anemet]

lib/Analysis/LoopAccessAnalysis.cpp

693–714

I don't think this is GCD. Consider the values Stride=4 and ScaledDistance=6:

4 * i = 4 * j + 6 can not be valid for any integer values of i and j.

I think the Diophantine equation is this: ScaledDistance/Stride = (i - j) where i - j has to be integer.

So the two accesses can only reference the same element if ScaledDistance is a multiple of Stride.

722

areStridedAccessIndependent is the conforming name (funtions are lower-case). Also not the the 'd' at the end of Strided. Same for the previous function.

731–749

If you want to handle this case I prefer we come back to it later as a separate LAA-only patch. Let's focus on the basics here that's needed for LV to handle the basic cases.

793

vectorized is misspelled

796

MinDistanceNeeded is probably a better name.

796–821

I think this is correct but I wonder if the example was less contrived if you used:

for (i = 0; i < 1024; i+= 3)
  A[i + 4] = A[i] + 1

MinSizeNeeded is 4 * 3 * (2 - 1) + 4 = 16 which is equal to the distance.

Also a nit: most or all of this comment is explaining why MinSizeNeeded is computed the way it is so the comment should be before the computation.

test/Analysis/LoopAccessAnalysis/analyze-stride-access-depedences.ll

216–228 ↗

(On Diff #26663)

As a follow-on patch, it would probably be a good idea to print MaxSafeDepDistance in LAI::analyze and check its value here.

224–228 ↗

(On Diff #26663)

Use CHECK-NEXTs where you can. Same later.

331 ↗

(On Diff #26663)

should *look* like?

[• HaoLiu]

Refactored the patch according to Adam's comments.

I also found a bug that write after load to the same location like:

A[i] = a;
b = A[i];

is not looked as store-load forwarding currently. As this could affect the correctness, I fixed this with slight modification. 2 new test cases are added.

Review please.

Thanks,
-Hao

lib/Analysis/LoopAccessAnalysis.cpp

693–714

Ah, not GCD.
You are right!

722

Agree.

731–749

Agree. Also this is rare case. I think it won't affect about the performance.

793

Fixed.

796

Fixed

796–821

This case is vectorizable as MinDistanceNeeded is exactly equal to the distance. If the distance is smaller (even 1 byte smaller), it can not be vectorizable.

Actually we already has a similar case in memdep.ll:

for (i = 0; i < 1024; ++i)
    A[i+2] = A[i] + 1;

The MinDistanceNeeded is 2*4 = 8. The distance is also 8.

test/Analysis/LoopAccessAnalysis/analyze-stride-access-depedences.ll

216–228 ↗

(On Diff #26663)

MaxSafeDepDistance can be printed out in "-debug-only". I don't know how to print it properly. Also as my comments on MaxSafeDepDistance say, I think we should refactor MaxSafeDepDistance as it could prevent some vectorization opportunities.

[anemet]

In D9368#181632, @HaoLiu wrote:

I also found a bug that write after load to the same location like:

A[i] = a;
b = A[i];

is not looked as store-load forwarding currently. As this could affect the correctness, I fixed this with slight modification. 2 new test cases are added.

Why do you think that this is bug? In this case because the vectorized loads and stores are aligned with each other, there should be no problem for the memory unit to figure out store-to-load forwarding. See the big comment in MemoryDepChecker::couldPreventStoreLoadForward.

[• HaoLiu]

In D9368#182268, @anemet wrote:

In D9368#181632, @HaoLiu wrote:

I also found a bug that write after load to the same location like:

A[i] = a;
b = A[i];

is not looked as store-load forwarding currently. As this could affect the correctness, I fixed this with slight modification. 2 new test cases are added.

Why do you think that this is bug? In this case because the vectorized loads and stores are aligned with each other, there should be no problem for the memory unit to figure out store-to-load forwarding. See the big comment in MemoryDepChecker::couldPreventStoreLoadForward.

To my understanding, if a load has to wait until the store is committed, it is store-load forwarding.
For the case:

A[i] = a;     (1)
b = A[i];     (2)

(2) has to waite (1) to be committed. It is store-load forwarding. After vectoring such case, it is still store-load forwarding.

From comment in couldPreventStoreLoadForward, I think it means to prevent generating store-load forwarding by vectorization. If that is ture. The difference for this case is that it is original store-load forwarding. Do you mean that we could vectorize the cases that are original store-load forwarding?

Thanks,
_hao

[• HaoLiu]

Hi Adam,

I updated a new patch by removing the modification about StoreLoadForwarding.

Thanks,
-Hao

[anemet]

In D9368#182273, @HaoLiu wrote:

To my understanding, if a load has to wait until the store is committed, it is store-load forwarding.
For the case:

A[i] = a;     (1)
b = A[i];     (2)

(2) has to waite (1) to be committed. It is store-load forwarding. After vectoring such case, it is still store-load forwarding.

From comment in couldPreventStoreLoadForward, I think it means to prevent generating store-load forwarding by vectorization. If that is ture. The difference for this case is that it is original store-load forwarding. Do you mean that we could vectorize the cases that are original store-load forwarding?

The problem is not whether we can vectorize or not but because we can. It's whether the resulting vector store and load will be subject to the processor's store-to-load forwarding optimization. In this case the store does not have to get fully retired before the load could start executing (assuming an OOO core) but the memory unit will forward the value of the store to the load (and check whether there are intervening stores that make this invalid).

This is easy for the processor to figure out if both operations use the same address. However if they are only partially overlapping it's hard.

[• HaoLiu]

In D9368#182471, @anemet wrote:

In D9368#182273, @HaoLiu wrote:

To my understanding, if a load has to wait until the store is committed, it is store-load forwarding.
For the case:

A[i] = a;     (1)
b = A[i];     (2)

(2) has to waite (1) to be committed. It is store-load forwarding. After vectoring such case, it is still store-load forwarding.

From comment in couldPreventStoreLoadForward, I think it means to prevent generating store-load forwarding by vectorization. If that is ture. The difference for this case is that it is original store-load forwarding. Do you mean that we could vectorize the cases that are original store-load forwarding?

The problem is not whether we can vectorize or not but because we can. It's whether the resulting vector store and load will be subject to the processor's store-to-load forwarding optimization. In this case the store does not have to get fully retired before the load could start executing (assuming an OOO core) but the memory unit will forward the value of the store to the load (and check whether there are intervening stores that make this invalid).

This is easy for the processor to figure out if both operations use the same address. However if they are only partially overlapping it's hard.

Sounds reasonable.

Anyway, I've removed the modification in last patch. Review please.

Thanks,
-Hao

[• HaoLiu]

Hi Adam,

Do you have any other concerns? If not, I'll commit this patch separately as you said.

I think it still has some potential problems, but we can improve it continously in the future. The commit of this patch is the first step. Then I can continue following work.

Thanks,
-Hao

[anemet]

lib/Analysis/LoopAccessAnalysis.cpp

702–723

Now, that I look at this again, the second covers the first case as well (i.e. superset). There is room to simplify it.

796–821

I didn't quite understand what you were saying here but looks like you didn't change the comment, so I guess you disagree that my example is better. Your example is vectorizable if miniter is 2 and so is mine, so I don't understand your reply.

test/Analysis/LoopAccessAnalysis/stride-access-dependence.ll

343–344 ↗

(On Diff #26955)

"It should be vectorizable."

[• HaoLiu]

Hi Adam,

I updated a new patch according to your comments. Also see my comments are inline.

Review please.

Thanks,
-Hao

lib/Analysis/LoopAccessAnalysis.cpp

702–723

You are right, only need "ScaledDist % Stride".

796–821

Previously, I thought you just asked me a question about that case.

Sorry about the misleading.
Actually, your case is "indep", which returns early with "Dependence::NoDep". So it could not reach at this place.

That's why I use an example with dependences.

test/Analysis/LoopAccessAnalysis/stride-access-dependence.ll

343–344 ↗

(On Diff #26955)

Agree. Thanks.

[rengolin]

Hao, Adam, Michael,

I think this review has gone a bit too far for what it is. I agree there are still many points to cover and many issues to fix, but we should do them later, after the initial implementation is in. For what it is, a prototype for strided vectorization, this patch fits the bill. It's not on by default, it's still experimental and won't be used at -O3 or anything, so we're still safe in case it does miss-compile anything.

I'd like to thank Adam and Michael for the extensive comments, it's not easy to get passionate people to do code review. I'd also like to than Hao for his extreme patience with so many and so drastic code reviews! Finally thanks to Arnold and Nadav for the valuable input and discussions to get the first prototype working previously.

But right now, I think it's time we land this patch and continue the review on further patches.

Adam, if you're happy that Hao's last changes address your concerns, please approve the patch and let's start round 2 on a new review.

cheers,
--renato

[anemet]

In D9368#183336, @rengolin wrote:

I think this review has gone a bit too far for what it is. I agree there are still many points to cover and many issues to fix, but we should do them later, after the initial implementation is in. For what it is, a prototype for strided vectorization, this patch fits the bill. It's not on by default, it's still experimental and won't be used at -O3 or anything, so we're still safe in case it does miss-compile anything.

I am very surprised by this sentiment. I would think that if reviews provide you with bugs, you'd be happy to fix them before the code going in. (We effectively performed the bugfixing for you.)

More importantly though, you're incorrect with your facts. Existing paths in LAA were also modified by this patch which affect things like the LoopVectorizer which is on by default.

You also seem to suggest that the changes requested were mostly minor or cosmetic. Clearly the placement of a rather expensive analysis is not a cosmetic change but a basic design decision that should be debated pre-commit.

There is extensive work happening on LAA, so wrong starts like this can be pretty disruptive for other people working on the same module.

Also as I am sure Hao can attest, DependenceAnalysis is a pretty complex topic so it takes time to actually think through the analysis and it's better to do this while we're all focused on the problem at hand. We caught multiple issues in this category and there were probably only one or two cosmetic comments.

I agree that the review lasted longer than usual but I don't see the main reason being our "drastic code reviews".

It would have been much easier if the patch was split up as I originally requested. The existing modularity allowed for this but the patch didn't take advantage of it. Also as we were finding correctness/design issues with the patch, Hao started improving the code (in actually very nice ways, thanks!!) which then needed new reviews again, etc.

We're also in different time zones which didn't help either but I feel like the community should be able to put up with this much slack.

Adam, if you're happy that Hao's last changes address your concerns, please approve the patch and let's start round 2 on a new review.

Yeah, the LAA parts look good now.

[anemet]

LAA parts LGTM.

lib/Analysis/LoopAccessAnalysis.cpp

796–821

Makes sense.

[rengolin]

In D9368#183650, @anemet wrote:

I am very surprised by this sentiment. I would think that if reviews provide you with bugs, you'd be happy to fix them before the code going in. (We effectively performed the bugfixing for you.)

I think you got me wrong. I *am* very happy that you are reviewing with such attention to detail...

More importantly though, you're incorrect with your facts. Existing paths in LAA were also modified by this patch which affect things like the LoopVectorizer which is on by default.

...but I was also (wrongly) assuming that the patch was still self contained. I stand corrected.

I agree with you that in the LAA case we need to make sure the behaviour outside of this patch should go unmodified.

I agree that the review lasted longer than usual but I don't see the main reason being our "drastic code reviews".

I meant it in the good way.

It would have been much easier if the patch was split up as I originally requested. The existing modularity allowed for this but the patch didn't take advantage of it. Also as we were finding correctness/design issues with the patch, Hao started improving the code (in actually very nice ways, thanks!!) which then needed new reviews again, etc. We're also in different time zones which didn't help either but I feel like the community should be able to put up with this much slack.

I'm fully aware of that and none of it was the reason why I asked for a breakpoint. As you said, Hao could have split the patch earlier, but once it was still small and self contained, the other bits would have been lost. This patch was re-written dozens of times and almost none of the original assumptions were kept in the final version. With such a game changer, it's hard to predict the future.

I just interpreted the last reviews as specific to the stride vectorizer, when (as you say), they're generic to LAA. My sincere apologies.

Yeah, the LAA parts look good now.

Great! Round 2! :)

cheers,
--renato

[anemet]

In D9368#183726, @rengolin wrote:

I just interpreted the last reviews as specific to the stride vectorizer, when (as you say), they're generic to LAA. My sincere apologies.

OK, apologies accepted :), thanks for clarifying.

I think that part of the problem is that LAA as an independent pass still has some rough edges. Any help (Hao’s here and Silviu’s in the other thread) improving this situation is much appreciated.

Adam

[mzolotukhin]

Hi,

I’m glad we’re on the same page now. I’m really looking forward to seeing this feature, but I didn’t want to rush with it because it strongly defines directions for future development of the vectorizer. I believe that this code would be a base for many other optimizations (e.g. supporting masks), and that’s why it’s really important for it to be thoroughly reviewed. That’s also a reason for a lot of cosmetic changes I requested - when I see a place that’s harder to understand than it should be, I have to spend additional time on it, and that means that in future many other developers would have to spend their time as well. Also, such places disrupt from the main idea, which makes the review harder.

Thanks,
Michael

[mzolotukhin]

Hi Hao,

The patch LGTM with some minor notes. Thank you for the efforts, your work is very appreciated!

Michael

lib/Analysis/LoopAccessAnalysis.cpp

806–807

Something went wrong with the indentation here.

lib/Transforms/Vectorize/LoopVectorize.cpp

658

Could we rename Delta to InterleaveFactor or something like this. When roaming through the code it'd be much easier to understand what it stands for - especially when the code is in-tree and one doesn't see the context of the current patch.

681

s/Call this class/Use this class/

4228

static_cast isn't needed here.

4325–4329

What is the previous check you are referring to? And if it's guaranteed, could this if be replaced with an assertion?

4333

static_cast isn't necessary here (and if we want to cast everything getIndex should also be casted from unsigned).

test/Transforms/LoopVectorize/interleaved-accesses.ll

2

Which of the tests needs -runtime-memory-check-threshold=24? Could we get rid of this flag by adding noalias attribute, or aliasing metadata?

40

Please run the tests through opt -instnamer to replace %[0-9]+ names - they are really hard to deal with when one need to modify the test.

[• HaoLiu]

I've updated the patch according to Michael's comments. My comments are inline.

Review please.

Thanks,
-Hao

lib/Analysis/LoopAccessAnalysis.cpp

806–807

No, The indentation is intended here to show the distance and overlap between the accesses to array A and B.

lib/Transforms/Vectorize/LoopVectorize.cpp

658

Reasonable. Renamed.

681

Fixed.

4228

std::abs() returns a signed int. Comparing signed to unsigned will cause a warning from the compiler.

To avoid static_cast, I use a temperaral value for "std::abs(Stride)" in the new patch.

4325–4329

It can not be assertion. This comment is hard to be understood. I've replaced it with another comment, which describe the thing we do right here.

A case @interleaved_stores in stride-access-dependence.ll checks for this situation. So no need to clarify this again.

4333

No, the division between signed and unsigned can not be casted.
I tested with a small case:

int a = -4;
unsigned b = 4;
int c = a / b;

The result c is a very large numer (1073741823). Modulo is simialr, I once fixed a bug about "signed % unsigned" (didn't cast unsigned data) in SeparateConstOffsetFromGEP.cpp.

This is different from ADD/SUB.

test/Transforms/LoopVectorize/interleaved-accesses.ll

2

We couldn't. Still too many runtime checks for accesses related to one pointer (Even though they are noalis).
E.g.

for( i = 0; i < 1024; i+=3) {
  A[i] += a;
  A[i+1] += b;
  A[i+2] += c
}

It has 3 loads and 3 stores, which need 11 runtime checks (greater than the current threshold 8). The 3 stores will be compared with each other (3 checks), and each load will be compared with the 3 stores (3 * 3 checks).

This could be improved in the future. No need to compare accesses in the same group. But currently, this is the work around to test.

40

Renamed anonymous names. This is really a helpful command.

[• HaoLiu]

Committed in r239285 (Code about LoopAccessAnalysis) and r239291 (Code about LoopVectorize).

Thanks a lot about the all review work. Especially Renato, Michael and Adam, you are very kind and patient for such a long period of review.

For the following work, my colleagues are working on improving the run time memory check and type promotion problem in Loop Vectorizor. For myself, I have patches for AArch64 and ARM backend to match the generated IRs into ldN/stN instructions. I'll send out later.

Thanks,
-Hao

include/llvm/Analysis/LoopAccessAnalysis.h

public:
   const SmallVectorImpl<Instruction *> &getMemoryInstructions() const {
     return InstMap;
   }
 
   /// \brief Find the set of instructions that read or write via \p Ptr.
   SmallVector<Instruction *, 4> getInstructionsForAccess(Value *Ptr,
                                                          bool isWrite) const;
 
+  /// \brief Check whether the data dependence could prevent store-load
+  /// forwarding.
+  bool couldPreventStoreLoadForward(unsigned Distance, unsigned TypeByteSize);
+
 private:
   ScalarEvolution *SE;
   const Loop *InnermostLoop;
 
   /// \brief Maps access locations (ptr, read/write) to program order.
   DenseMap<MemAccessInfo, std::vector<unsigned> > Accesses;
 
   /// \brief Memory access instructions in program order.
private:
   /// absence of such can't be proved) between the two accesses. If there is a
   /// plausible dependence but the dependence distance is bigger than one
   /// element access it records this distance in \p MaxSafeDepDistBytes (if this
   /// distance is smaller than any other distance encountered so far).
   /// Otherwise, this function returns true signaling a possible dependence.
   Dependence::DepType isDependent(const MemAccessInfo &A, unsigned AIdx,
                                   const MemAccessInfo &B, unsigned BIdx,
                                   const ValueToValueMap &Strides);
+};
 
-  /// \brief Check whether the data dependence could prevent store-load
-  /// forwarding.
-  bool couldPreventStoreLoadForward(unsigned Distance, unsigned TypeByteSize);
+/// \brief The group of interleaved loads/stores sharing the same stride and
+/// close to each other.
+///
+/// Each member in this group has an index starting from 0 and the largest
+/// index should never be greater than Delta (interleaved factor) which is the
+/// absolute value of the access stride.
+///
+/// E.g. Interleaved load group of Delta 4 (with a gap: index 2):
+///        for (unsigned i = 0; i < 1024; i+=4) {
+///          a = A[i];                           // Member of index 0
+///          b = A[i+1];                         // Member of index 1
+///          d = A[i+3];                         // Member of index 3
+///          ...
+///        }
+///
+///      Interleaved store group of Delta 4:
+///        for (unsigned i = 0; i < 1024; i+=4) {
+///          ...
+///          A[i]   = a;                         // Member of index 0
+///          A[i+1] = b;                         // Member of index 1
+///          A[i+2] = c;                         // Member of index 2
+///          A[i+3] = d;                         // Member of index 3
+///        }
+///
+/// Note: the interleaved load group could have gaps (missing members), but
+/// the interleaved store group doesn't allow gap.
+class InterleaveGroup {
+public:
+  InterleaveGroup(Instruction *Instr, int Stride, unsigned Align)
+      : Align(Align), SmallestKey(0), LargestKey(0), InsertPos(nullptr) {
+    assert(Align && "The alignment should be non-zero");
+
+    Delta = std::abs(Stride);
+    assert(Delta > 1 && "Invalid interleave factor");
+
+    Reverse = Stride < 0;
+    Members[0] = Instr;
+  }
+
+  bool isReverse() const { return Reverse; }
+  unsigned getDelta() const { return Delta; }
+  unsigned getAlign() const { return Align; }
+  unsigned getNumMembers() const { return Members.size(); }
+
+  /// \brief Try to insert a new member \p Instr with index \p Index and
+  /// alignment \p NewAlign.
+  ///
+  /// \returns false if the instruction doesn't belong to the group.
+  bool insertMember(Instruction *Instr, int Index, unsigned NewAlign) {
+    assert(NewAlign && "The new member's alignment should be non-zero");
+
+    int Key = Index + SmallestKey;
+
+    // Skip if there is already a member with the same index.
+    if (Members.count(Key))
+      return false;
+
+    if (Key > LargestKey) {
+      // The largest index is always less than the Delta.
+      if (Index >= Delta)
+        return false;
+
+      LargestKey = Key;
+    } else if (Key < SmallestKey) {
+      // The largest index is always less than the Delta.
+      if (LargestKey - Key >= Delta)
+        return false;
+
+      SmallestKey = Key;
+    }
+
+    // It's always safe to select the minimum alignment.
+    Align = std::min(Align, NewAlign);
+    Members[Key] = Instr;
+    return true;
+  }
+
+  /// \brief Get the member with the given index \p Index
+  ///
+  /// \returns nullptr if dosn't contain such member.
+  Instruction *getMember(unsigned Index) const {
+    int Key = SmallestKey + Index;
+    if (!Members.count(Key))
+      return nullptr;
+
+    return Members.find(Key)->second;
+  }
+
+  /// \brief Get the index for the given member. Unlike the key in the member
+  /// map, the index starts from 0.
+  unsigned getIndex(Instruction *Instr) const {
+    for (auto I : Members)
+      if (I.second == Instr)
+        return I.first - SmallestKey;
+
+    llvm_unreachable("InterleaveGroup contains no such member");
+  }
+
+  Instruction *getInsertPos() const { return InsertPos; }
+  void setInsertPos(Instruction *Inst) { InsertPos = Inst; }
+
+  /// \brief Print the group.
+  void print(raw_ostream &OS, unsigned Depth) const {
+    OS.indent(Depth) << "Interleave Group of Delta " << Delta << ":\n";
+
+    for (int i = 0; i < Delta; i++) {
+      Instruction *Member = getMember(i);
+      if (Member)
+        OS.indent(Depth + 2) << "Index " << i << ":" << *Member << "\n";
+    }
+  }
+
+private:
+  int Delta; // Interleave Factor.
+  bool Reverse;
+  unsigned Align;
+  DenseMap<int, Instruction *> Members;
+  int SmallestKey;
+  int LargestKey;
+
+  // To avoid breaking dependences, an interleaved access should be inserted
+  // at either the first load or the last store in program order.
+  // E.g. %even = load i32             // Insert Position
+  //      %add = add i32 %even         // Use of %even
+  //      %odd = load i32
+  //
+  //      store i32 %even
+  //      %odd = add i32               // Def of %odd
+  //      store i32 %odd               // Insert Position
+  Instruction *InsertPos;
+};
+
+/// \brief Drive the analysis of interleaved memory accesses in the loop.
+///
+/// Call this class to analyze interleaved accesses only when the memory
+/// dependence check says we can vectorize the loop. Otherwise it's meaningless
+/// to do analysis as the vectorization on interleaved accesses is unsafe.
+///
+/// The analysis collects interleave groups and records the relationships
+/// between the member and the group in a map.
+class InterleavedAccessInfo {
+public:
+  InterleavedAccessInfo(ScalarEvolution *SE, Loop *L, DominatorTree *DT,
+                        MemoryDepChecker *DepChecker)
+      : SE(SE), TheLoop(L), DT(DT), DepChecker(DepChecker) {}
+
+  ~InterleavedAccessInfo() {
+    SmallSet<InterleaveGroup *, 4> DelSet;
+    // Collecting all the group pointers to avoid release a pointer twice.
+    for (auto &I : InterleaveGroupMap)
+      DelSet.insert(I.second);
+    for (auto *Ptr : DelSet)
+      delete Ptr;
+  }
+
+  /// \brief Analyze the interleaved accesses.  Substitute symbolic strides
+  /// using \p Strides.
+  void analyzeInterleaving(const ValueToValueMap &Strides);
+
+  /// \brief Check if \p Instr belongs to any interleave group.
+  bool isAccessInterleaved(Instruction *Instr) const {
+    return InterleaveGroupMap.count(Instr);
+  }
+
+  /// \brief Get the interleave group that \p Instr belongs to.
+  ///
+  /// \returns nullptr if doesn't have such group.
+  InterleaveGroup *getInterleaveGroup(Instruction *Instr) const {
+    if (InterleaveGroupMap.count(Instr))
+      return InterleaveGroupMap.find(Instr)->second;
+    return nullptr;
+  }
+
+  /// \brief Print the interleave groups.
+  void print(raw_ostream &OS, unsigned Depth) const;
+
+private:
+  ScalarEvolution *SE;
+  Loop *TheLoop;
+  DominatorTree *DT;
+  MemoryDepChecker *DepChecker;
+
+  /// Contains the relationships between the members and the interleave group.
+  DenseMap<Instruction *, InterleaveGroup *> InterleaveGroupMap;
+
+  /// \brief Group the interleaved loads/stores. Record the write-write pairs
+  /// whose dependences may be broken by the vectorization.
+  void groupInterleavedAccesses(
+      ArrayRef<Instruction *> InstrList,
+      SmallVector<std::pair<Instruction *, Instruction *>, 2> &WritePairs,
+      const ValueToValueMap &Strides);
+
+  /// \brief Create a new interleave group with the given instruction \p Instr,
+  /// stride \p Stride and alignment \p Align.
+  ///
+  /// \returns the newly created interleave group.
+  InterleaveGroup *createInterleaveGroup(Instruction *Instr, int Stride,
+                                         unsigned Align) {
+    assert(!InterleaveGroupMap.count(Instr) &&
+           "Already in an interleaved access group");
+    InterleaveGroupMap[Instr] = new InterleaveGroup(Instr, Stride, Align);
+    return InterleaveGroupMap[Instr];
+  }
+
+  /// \brief Release the group and remove all the relationships.
+  void releaseGroup(InterleaveGroup *Group) {
+    for (unsigned i = 0; i < Group->getDelta(); i++)
+      if (Instruction *Member = Group->getMember(i))
+        InterleaveGroupMap.erase(Member);
+
+    delete Group;
+  }
 };
 
 /// \brief Drive the analysis of memory accesses in the loop
 ///
 /// This class is responsible for analyzing the memory accesses of a loop.  It
 /// collects the accesses and then its main helper the AccessAnalysis class
 /// finds and categorizes the dependences in buildDependenceSets.
 ///
 /// For memory dependences that can be analyzed at compile time, it determines
 /// whether the dependence is part of cycle inhibiting vectorization.  This work
 /// is delegated to the MemoryDepChecker class.
 ///
 /// For memory dependences that cannot be determined at compile time, it
 /// generates run-time checks to prove independence.  This is done by
 /// AccessAnalysis::canCheckPtrAtRT and the checks are maintained by the
 /// RuntimePointerCheck class.
+///
+/// If the memory accesses can be vectorized, it will analyze the interleaved
+/// access information, which is delegated to the InterleavedAccessInfo class.
 class LoopAccessInfo {
 public:
   /// This struct holds information about the memory runtime legality check that
   /// a group of pointers do not overlap.
   struct RuntimePointerCheck {
     RuntimePointerCheck() : Need(false) {}
 
     /// Reset the state of the pointer runtime information.
struct RuntimePointerCheck {
     /// Holds the information if this pointer is used for writing to memory.
     SmallVector<bool, 2> IsWritePtr;
     /// Holds the id of the set of pointers that could be dependent because of a
     /// shared underlying object.
     SmallVector<unsigned, 2> DependencySetId;
     /// Holds the id of the disjoint alias set to which this pointer belongs.
     SmallVector<unsigned, 2> AliasSetId;
   };
 
   LoopAccessInfo(Loop *L, ScalarEvolution *SE, const DataLayout &DL,
                  const TargetLibraryInfo *TLI, AliasAnalysis *AA,
                  DominatorTree *DT, LoopInfo *LI,
                  const ValueToValueMap &Strides);
 
   /// Return true we can analyze the memory accesses in the loop and there are
   /// no memory dependence cycles.
   bool canVectorizeMemory() const { return CanVecMem; }
 
   const RuntimePointerCheck *getRuntimePointerCheck() const {
     return &PtrRtCheck;
   }
 
   /// \brief Number of memchecks required to prove independence of otherwise
   /// may-alias pointers.
   unsigned getNumRuntimePointerChecks() const { return NumComparisons; }
 
   /// Return true if the block BB needs to be predicated in order for the loop
   /// to be vectorized.
   static bool blockNeedsPredication(BasicBlock *BB, Loop *TheLoop,
                                     DominatorTree *DT);
 
   /// Returns true if the value V is uniform within the loop.
   bool isUniform(Value *V) const;
 
   unsigned getMaxSafeDepDistBytes() const { return MaxSafeDepDistBytes; }
   unsigned getNumStores() const { return NumStores; }
   unsigned getNumLoads() const { return NumLoads;}
 
   /// \brief Add code that checks at runtime if the accessed arrays overlap.
   ///
   /// Returns a pair of instructions where the first element is the first
   /// instruction generated in possibly a sequence of instructions and the
   /// second value is the final comparator value or NULL if no check is needed.
   ///
   /// If \p PtrPartition is set, it contains the partition number for pointers
   /// (-1 if the pointer belongs to multiple partitions).  In this case omit
   /// checks between pointers belonging to the same partition.
   std::pair<Instruction *, Instruction *>
   addRuntimeCheck(Instruction *Loc,
                   const SmallVectorImpl<int> *PtrPartition = nullptr) const;
 
   /// \brief The diagnostics report generated for the analysis.  E.g. why we
   /// couldn't analyze the loop.
   const Optional<LoopAccessReport> &getReport() const { return Report; }
 
   /// \brief the Memory Dependence Checker which can determine the
   /// loop-independent and loop-carried dependences between memory accesses.
   const MemoryDepChecker &getDepChecker() const { return DepChecker; }
 
   /// \brief Return the list of instructions that use \p Ptr to read or write
   /// memory.
   SmallVector<Instruction *, 4> getInstructionsForAccess(Value *Ptr,
                                                          bool isWrite) const {
     return DepChecker.getInstructionsForAccess(Ptr, isWrite);
   }
 
+  /// \brief Check if \p Instr belongs to any interleave group.
+  bool isAccessInterleaved(Instruction *Instr) const {
+    return InterleaveInfo.isAccessInterleaved(Instr);
+  }
+
+  /// \brief Get the interleave group that \p Instr belongs to.
+  const InterleaveGroup *getInterleavedAccessGroup(Instruction *Instr) const {
+    return InterleaveInfo.getInterleaveGroup(Instr);
+  }
+
   /// \brief Print the information about the memory accesses in the loop.
   void print(raw_ostream &OS, unsigned Depth = 0) const;
 
   /// \brief Used to ensure that if the analysis was run with speculating the
   /// value of symbolic strides, the client queries it with the same assumption.
   /// Only used in DEBUG build but we don't want NDEBUG-dependent ABI.
   unsigned NumSymbolicStrides;
 
   /// \brief Checks existence of store to invariant address inside loop.
   /// If the loop has any store to invariant address, then it returns true,
   /// else returns false.
   bool hasStoreToLoopInvariantAddress() const {
     return StoreToLoopInvariantAddress;
   }
 
 private:
   /// \brief Analyze the loop.  Substitute symbolic strides using Strides.
   void analyzeLoop(const ValueToValueMap &Strides);
 
   /// \brief Check if the structure of the loop allows it to be analyzed by this
   /// pass.
   bool canAnalyzeLoop();
 
   void emitAnalysis(LoopAccessReport &Message);
 
   /// We need to check that all of the pointers in this list are disjoint
   /// at runtime.
   RuntimePointerCheck PtrRtCheck;
 
   /// \brief the Memory Dependence Checker which can determine the
   /// loop-independent and loop-carried dependences between memory accesses.
   MemoryDepChecker DepChecker;
 
+  /// \brief The interleaved access information contains groups of interleaved
+  /// accesses with the same stride and close to each other.
+  InterleavedAccessInfo InterleaveInfo;
+
   /// \brief Number of memchecks required to prove independence of otherwise
   /// may-alias pointers
   unsigned NumComparisons;
 
   Loop *TheLoop;
   ScalarEvolution *SE;
   const DataLayout &DL;
   const TargetLibraryInfo *TLI;
private:
   /// \brief Indicator for storing to uniform addresses.
   /// If a loop has write to a loop invariant address then it should be true.
   bool StoreToLoopInvariantAddress;
 
   /// \brief The diagnostics report generated for the analysis.  E.g. why we
   /// couldn't analyze the loop.
   Optional<LoopAccessReport> Report;
 };
 
 Value *stripIntegerCast(Value *V);
 
 ///\brief Return the SCEV corresponding to a pointer with the symbolic stride
 ///replaced with constant one.
 ///
 /// If \p OrigPtr is not null, use it to look up the stride value instead of \p
 /// Ptr.  \p PtrToStride provides the mapping between the pointer value and its
 /// stride as collected by LoopVectorizationLegality::collectStridedAccess.
 const SCEV *replaceSymbolicStrideSCEV(ScalarEvolution *SE,

include/llvm/Analysis/TargetTransformInfo.h

public:
   /// \return The cost of Load and Store instructions.
   unsigned getMemoryOpCost(unsigned Opcode, Type *Src, unsigned Alignment,
                            unsigned AddressSpace) const;
 
   /// \return The cost of masked Load and Store instructions.
   unsigned getMaskedMemoryOpCost(unsigned Opcode, Type *Src, unsigned Alignment,
                                  unsigned AddressSpace) const;
 
+  /// \return The cost of the interleaved memory operation.
+  /// \p Opcode is the memory operation code
+  /// \p VecTy is the vector type of the interleaved access.
+  /// \p Delta is the interleave factor
+  /// \p Indices is the indices for interleaved load members (as interleaved
+  ///    loads allow gaps)
+  unsigned getInterleavedMemoryOpCost(unsigned Opcode, Type *VecTy,
+                                      unsigned Delta,
+                                      ArrayRef<unsigned> Indices,
+                                      unsigned Alignment,
+                                      unsigned AddressSpace) const;
+
   /// \brief Calculate the cost of performing a vector reduction.
   ///
   /// This is the cost of reducing the vector value of type \p Ty to a scalar
   /// value using the operation denoted by \p Opcode. The form of the reduction
   /// can either be a pairwise reduction or a reduction that splits the vector
   /// at every reduction level.
   ///
   /// Pairwise:
public:
   virtual unsigned getVectorInstrCost(unsigned Opcode, Type *Val,
                                       unsigned Index) = 0;
   virtual unsigned getMemoryOpCost(unsigned Opcode, Type *Src,
                                    unsigned Alignment,
                                    unsigned AddressSpace) = 0;
   virtual unsigned getMaskedMemoryOpCost(unsigned Opcode, Type *Src,
                                          unsigned Alignment,
                                          unsigned AddressSpace) = 0;
+  virtual unsigned getInterleavedMemoryOpCost(unsigned Opcode, Type *VecTy,
+                                              unsigned Delta,
+                                              ArrayRef<unsigned> Indices,
+                                              unsigned Alignment,
+                                              unsigned AddressSpace) = 0;
   virtual unsigned getReductionCost(unsigned Opcode, Type *Ty,
                                     bool IsPairwiseForm) = 0;
   virtual unsigned getIntrinsicInstrCost(Intrinsic::ID ID, Type *RetTy,
                                          ArrayRef<Type *> Tys) = 0;
   virtual unsigned getCallInstrCost(Function *F, Type *RetTy,
                                     ArrayRef<Type *> Tys) = 0;
   virtual unsigned getNumberOfParts(Type *Tp) = 0;
   virtual unsigned getAddressComputationCost(Type *Ty, bool IsComplex) = 0;
public:
   unsigned getMemoryOpCost(unsigned Opcode, Type *Src, unsigned Alignment,
                            unsigned AddressSpace) override {
     return Impl.getMemoryOpCost(Opcode, Src, Alignment, AddressSpace);
   }
   unsigned getMaskedMemoryOpCost(unsigned Opcode, Type *Src, unsigned Alignment,
                                  unsigned AddressSpace) override {
     return Impl.getMaskedMemoryOpCost(Opcode, Src, Alignment, AddressSpace);
   }
+  unsigned getInterleavedMemoryOpCost(unsigned Opcode, Type *VecTy,
+                                      unsigned Delta,
+                                      ArrayRef<unsigned> Indices,
+                                      unsigned Alignment,
+                                      unsigned AddressSpace) override {
+    return Impl.getInterleavedMemoryOpCost(Opcode, VecTy, Delta, Indices,
+                                           Alignment, AddressSpace);
+  }
   unsigned getReductionCost(unsigned Opcode, Type *Ty,
                             bool IsPairwiseForm) override {
     return Impl.getReductionCost(Opcode, Ty, IsPairwiseForm);
   }
   unsigned getIntrinsicInstrCost(Intrinsic::ID ID, Type *RetTy,
                                  ArrayRef<Type *> Tys) override {
     return Impl.getIntrinsicInstrCost(ID, RetTy, Tys);
   }

include/llvm/Analysis/TargetTransformInfoImpl.h

unsigned getMemoryOpCost(unsigned Opcode, Type *Src, unsigned Alignment,
     return 1;
   }
 
   unsigned getMaskedMemoryOpCost(unsigned Opcode, Type *Src, unsigned Alignment,
                                  unsigned AddressSpace) {
     return 1;
   }
 
+  unsigned getInterleavedMemoryOpCost(unsigned Opcode, Type *VecTy,
+                                      unsigned Delta,
+                                      ArrayRef<unsigned> Indices,
+                                      unsigned Alignment,
+                                      unsigned AddressSpace) {
+    return 1;
+  }
+
   unsigned getIntrinsicInstrCost(Intrinsic::ID ID, Type *RetTy,
                                  ArrayRef<Type *> Tys) {
     return 1;
   }
 
   unsigned getCallInstrCost(Function *F, Type *RetTy, ArrayRef<Type *> Tys) {
     return 1;
   }
 
   unsigned getNumberOfParts(Type *Tp) { return 0; }
 

include/llvm/CodeGen/BasicTTIImpl.h

if (Src->isVectorTy() &&
         Cost += getScalarizationOverhead(Src, Opcode != Instruction::Store,
                                          Opcode == Instruction::Store);
       }
     }
 
     return Cost;
   }
 
+  unsigned getInterleavedMemoryOpCost(unsigned Opcode, Type *VecTy,
+                                      unsigned Delta,
+                                      ArrayRef<unsigned> Indices,
+                                      unsigned Alignment,
+                                      unsigned AddressSpace) {
+    VectorType *VT = dyn_cast<VectorType>(VecTy);
+    assert(VT && "Expect vector types");
+
+    unsigned NumElts = VT->getNumElements();
+    assert(Delta >= 2 && !(NumElts % Delta) && "Invalid Delta");
+
+    unsigned NumSubElts = NumElts / Delta;
+    VectorType *SubVT = VectorType::get(VT->getElementType(), NumSubElts);
+
+    // Firstly, the cost of load/store operation.
+    unsigned Cost = getMemoryOpCost(Opcode, VecTy, Alignment, AddressSpace);
+
+    // Then plus the cost of interleave operation.
+    if (Opcode == Instruction::Load) {
+      // The interleave cost is similar to extract elements of the sub vectors
+      // from the wide vector, and insert them into sub vectors.
+      //
+      // E.g. Interleaved load of Delta 3 to 2 sub vectors (%v0, %v2):
+      //      %vec = load <12 x i32>, <12 x i32> %ptr
+      //      %v0 = shuffle %vec, undef, <0, 3, 6, 9>         ; Index 0
+      //      %v2 = shuffle %vec, undef, <2, 5, 8, 11>        ; Index 2
+      // The cost is estimated as extract elements at 0, 2, 3, 5, 6, 8, 9, 11
+      // from the <12 x i32> vector and insert them into two <4 x i32> vectors.
+
+      assert(Indices.size() <= Delta &&
+             "Interleaved memory op has too many members");
+      for (unsigned Index : Indices) {
+        assert(Index < Delta && "Invalid index for interleaved memory op");
+        for (unsigned i = 0; i < NumSubElts; i++)
+          Cost +=
+              getVectorInstrCost(Instruction::ExtractElement, VT, Index + i);
+      }
+
+      unsigned InsSubCost = 0;
+      for (unsigned i = 0; i < NumSubElts; i++)
+        InsSubCost += getVectorInstrCost(Instruction::InsertElement, SubVT, i);
+
+      Cost += Indices.size() * InsSubCost;
+    } else {
+      // The interleave cost is extract each element from sub vectors, and
+      // insert them into the wide vector.
+      //
+      // E.g. Interleaved store with Delta 3 (For vector %v0, %v1, %v2):
+      //      %v0_v1 = shuffle %v0, %v1, <0, 1, 2, 3, 4, 5, 6, 7>
+      //      %v2_u = shuffle %v2, undef, <0, 1, 2, 3, u, u, u, u>
+      //      %interleaved.vec = shuffle %v0_v1, %v2_u,
+      //                                 <0, 4, 8, 1, 5, 9, 2, 6, 10, 3, 7, 11>
+      //      store <12 x i32> %interleaved.vec, <12 x i32>* %ptr
+      // The cost is estimated as extract all elements from the 3 <4 x i32>
+      // vectors (Total 3 * 4 elements) and insert into the <12 x i32> vector.
+
+      unsigned ExtSubCost = 0;
+      for (unsigned i = 0; i < NumSubElts; i++)
+        ExtSubCost += getVectorInstrCost(Instruction::ExtractElement, SubVT, i);
+
+      Cost += Delta * ExtSubCost;
+
+      for (unsigned i = 0; i < NumElts; i++)
+        Cost += getVectorInstrCost(Instruction::InsertElement, VT, i);
+    }
+
+    return Cost;
+  }
+
   unsigned getIntrinsicInstrCost(Intrinsic::ID IID, Type *RetTy,
                                  ArrayRef<Type *> Tys) {
     unsigned ISD = 0;
     switch (IID) {
     default: {
       // Assume that we need to scalarize this intrinsic.
       unsigned ScalarizationCost = 0;
       unsigned ScalarCalls = 1;

lib/Analysis/LoopAccessAnalysis.cpp

 static cl::opt<unsigned, true>
 VectorizationInterleave("force-vector-interleave", cl::Hidden,
                         cl::desc("Sets the vectorization interleave count. "
                                  "Zero is autoselect."),
                         cl::location(
                             VectorizerParams::VectorizationInterleave));
 unsigned VectorizerParams::VectorizationInterleave;
 
+static cl::opt<bool> EnableInterleaving(
+    "enable-interleaving", cl::init(false), cl::Hidden,
+    cl::desc("Enable analyzing interleaved accesses in a loop"));
+
 static cl::opt<unsigned, true> RuntimeMemoryCheckThreshold(
     "runtime-memory-check-threshold", cl::Hidden,
     cl::desc("When performing memory disambiguation checks at runtime do not "
              "generate more than this number of comparisons (default = 8)."),
     cl::location(VectorizerParams::RuntimeMemoryCheckThreshold), cl::init(8));
 unsigned VectorizerParams::RuntimeMemoryCheckThreshold;
 
 /// Maximum SIMD width.
DEBUG(dbgs() << "LAA: Bad stride - Not an AddRecExpr pointer "
           << *Ptr << " SCEV: " << *PtrScev << "\n");
     return 0;
   }
 
   // The accesss function must stride over the innermost loop.
   if (Lp != AR->getLoop()) {
     DEBUG(dbgs() << "LAA: Bad stride - Not striding over innermost loop " <<
           *Ptr << " SCEV: " << *PtrScev << "\n");
   }
 
   // The address calculation must not wrap. Otherwise, a dependence could be
   // inverted.
   // An inbounds getelementptr that is a AddRec with a unit stride
   // cannot wrap per definition. The unit stride requirement is checked later.
   // An getelementptr without an inbounds attribute and unit stride would have
   // to access the pointer value "0" which is undefined behavior in address
   // space 0, therefore we can also vectorize this case.

 MemoryDepChecker::Dependence::DepType
 MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
                               const MemAccessInfo &B, unsigned BIdx,
                               const ValueToValueMap &Strides) {
   assert (AIdx < BIdx && "Must pass arguments in program order");
 
   Value *APtr = A.getPointer();
   Value *BPtr = B.getPointer();
   bool AIsWrite = A.getInt();
   bool BIsWrite = B.getInt();
 
   // Two reads are independent.
   if (!AIsWrite && !BIsWrite)
     return Dependence::NoDep;
 
   // We cannot check pointers in different address spaces.
   if (APtr->getType()->getPointerAddressSpace() !=
       BPtr->getType()->getPointerAddressSpace())
     return Dependence::Unknown;
 
   const SCEV *AScev = replaceSymbolicStrideSCEV(SE, Strides, APtr);
   const SCEV *BScev = replaceSymbolicStrideSCEV(SE, Strides, BPtr);
 
   int StrideAPtr = isStridedPtr(SE, APtr, InnermostLoop, Strides);
   int StrideBPtr = isStridedPtr(SE, BPtr, InnermostLoop, Strides);
 
   const SCEV *Src = AScev;
   const SCEV *Sink = BScev;
 
   // If the induction step is negative we have to invert source and sink of the
   // dependence.
   if (StrideAPtr < 0) {
     //Src = BScev;
     //Sink = AScev;
     std::swap(APtr, BPtr);
     std::swap(Src, Sink);
     std::swap(AIsWrite, BIsWrite);
     std::swap(AIdx, BIdx);
     std::swap(StrideAPtr, StrideBPtr);
   }
 
   const SCEV *Dist = SE->getMinusSCEV(Sink, Src);
 
   DEBUG(dbgs() << "LAA: Src Scev: " << *Src << "Sink Scev: " << *Sink
         << "(Induction step: " << StrideAPtr <<  ")\n");
   DEBUG(dbgs() << "LAA: Distance for " << *InstMap[AIdx] << " to "
         << *InstMap[BIdx] << ": " << *Dist << "\n");
 
   // Need consecutive accesses. We don't want to vectorize
   // "A[B[i]] += ..." and similar code or pointer arithmetic that could wrap in
   // the address space.
   if (!StrideAPtr || !StrideBPtr || StrideAPtr != StrideBPtr){
     DEBUG(dbgs() << "Non-consecutive pointer access\n");
     return Dependence::Unknown;
   }
 
   const SCEVConstant *C = dyn_cast<SCEVConstant>(Dist);
   if (!C) {
     DEBUG(dbgs() << "LAA: Dependence because of non-constant distance\n");
     ShouldRetryWithRuntimeCheck = true;
     return Dependence::Unknown;
   }
 
   Type *ATy = APtr->getType()->getPointerElementType();
   Type *BTy = BPtr->getType()->getPointerElementType();
   auto &DL = InnermostLoop->getHeader()->getModule()->getDataLayout();
   unsigned TypeByteSize = DL.getTypeAllocSize(ATy);
 
   // Negative distances are not plausible dependencies.
   const APInt &Val = C->getValue()->getValue();
   if (Val.isNegative()) {
     bool IsTrueDataDependence = (AIsWrite && !BIsWrite);
     if (IsTrueDataDependence &&
MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
 
   unsigned Distance = (unsigned) Val.getZExtValue();
 
   // Bail out early if passed-in parameters make vectorization not feasible.
   unsigned ForcedFactor = (VectorizerParams::VectorizationFactor ?
                            VectorizerParams::VectorizationFactor : 1);
   unsigned ForcedUnroll = (VectorizerParams::VectorizationInterleave ?
                            VectorizerParams::VectorizationInterleave : 1);
+  // The number of iterations to be vectorized and unrolled.
+  unsigned NumIter = std::max(ForcedFactor * ForcedUnroll, 2U);
 
-  // The distance must be bigger than the size needed for a vectorized version
-  // of the operation and the size of the vectorized operation must not be
-  // bigger than the currrent maximum size.
-  if (Distance < 2*TypeByteSize ||
-      2*TypeByteSize > MaxSafeDepDistBytes ||
-      Distance < TypeByteSize * ForcedUnroll * ForcedFactor) {
-    DEBUG(dbgs() << "LAA: Failure because of Positive distance "
+  unsigned Stride = std::abs(StrideAPtr);
+  // Safe when either one below is true
+  //     Distance < Stride * TypeByteSize
+  //     Distance >= TypeByteSize * NumIter * Stride
+  if (!(Distance < Stride * TypeByteSize ||
+        Distance >= TypeByteSize * NumIter * Stride)) {
+    DEBUG(dbgs() << "LAA: Failure because of positive distance "
                  << Val.getSExtValue() << '\n');
     return Dependence::Backward;
   }
 
-  // Positive distance bigger than max vectorization factor.
-  MaxSafeDepDistBytes = Distance < MaxSafeDepDistBytes ?
-    Distance : MaxSafeDepDistBytes;
+  // Safe when positive distance is not greater than the max safe distance.
+  if (Distance > MaxSafeDepDistBytes) {
+    DEBUG(dbgs() << "LAA: Failure because positive distance "
+                 << Val.getSExtValue() << " is greater than max safe distance "
+                 << MaxSafeDepDistBytes << "\n");
+    return Dependence::Backward;
+  }
+
+  // If Distance < Stride * TypeByteSize, it is always safe. just keep the
+  // current MaxSafeDepDistBytes. Otherwise, update the MaxSafeDepDistBytes.
+  if (Distance >= Stride * TypeByteSize)
+    MaxSafeDepDistBytes = Distance;
 
   bool IsTrueDataDependence = (!AIsWrite && BIsWrite);
   if (IsTrueDataDependence &&
       couldPreventStoreLoadForward(Distance, TypeByteSize))
     return Dependence::BackwardVectorizableButPreventsForwarding;
 
   DEBUG(dbgs() << "LAA: Positive distance " << Val.getSExtValue() <<
         " with max VF = " << MaxSafeDepDistBytes / TypeByteSize << '\n');
 
   return Dependence::BackwardVectorizable;
 }
 
 bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets,
                                    MemAccessInfoSet &CheckDeps,

 void MemoryDepChecker::Dependence::print(
     raw_ostream &OS, unsigned Depth,
     const SmallVectorImpl<Instruction *> &Instrs) const {
   OS.indent(Depth) << DepName[Type] << ":\n";
   OS.indent(Depth + 2) << *Instrs[Source] << " -> \n";
   OS.indent(Depth + 2) << *Instrs[Destination] << "\n";
 }
 
+struct StrideDescriptor {
+  StrideDescriptor(int Stride, const SCEV *Scev, unsigned Size, unsigned Align)
+      : Stride(Stride), Scev(Scev), Size(Size), Align(Align) {}
+
+  int Stride;
+  const SCEV *Scev;
+  unsigned Size;
+  unsigned Align;
+};
+
+void InterleavedAccessInfo::groupInterleavedAccesses(
+    ArrayRef<Instruction *> InstrList,
+    SmallVector<std::pair<Instruction *, Instruction *>, 2> &WritePairs,
+    const ValueToValueMap &Strides) {
+  // Holds all the stride accesses.
+  SmallVector<std::pair<Instruction *, StrideDescriptor>, 16> StrideAccess;
+
+  auto &DL = TheLoop->getHeader()->getModule()->getDataLayout();
+  for (auto I : InstrList) {
+    LoadInst *LI = dyn_cast<LoadInst>(I);
+    StoreInst *SI = dyn_cast<StoreInst>(I);
+    assert((LI || SI) && "Invalid access instruction");
+
+    Value *Ptr = LI ? LI->getPointerOperand() : SI->getPointerOperand();
+    int Stride = isStridedPtr(SE, Ptr, TheLoop, Strides);
+
+    // Only analyze non-unit stride accesses.
+    if (std::abs(Stride) < 2)
+      continue;
+
+    const SCEV *Scev = replaceSymbolicStrideSCEV(SE, Strides, Ptr);
+    PointerType *PtrTy = dyn_cast<PointerType>(Ptr->getType());
+    unsigned Size = DL.getTypeAllocSize(PtrTy->getElementType());
+
+    // An alignment of 0 means target ABI alignment.
+    unsigned Align = LI ? LI->getAlignment() : SI->getAlignment();
+    if (!Align)
+      Align = DL.getABITypeAlignment(PtrTy->getElementType());
+
+    StrideAccess.push_back(
+        std::make_pair(I, StrideDescriptor(Stride, Scev, Size, Align)));
+  }
+
+  if (!StrideAccess.size())
+    return;
+
+  // Search the load-load/write-write pair B-A in bottom-up order and try to
+  // insert B into the interleave group of A according to 3 rules:
+  //   1. A and B have the same stride.
+  //   2. A and B have the same memory object size.
+  //   3. The distance of B to the leader of the group is less than the Delta.
+  //
+  // The bottom-up order can avoid breaking the WAW dependences between two
+  // pointers with the same base.
+  // E.g.  A[i]   = a;   (1)
+  //       A[i]   = b;   (2)
+  //       A[i+1] = c    (3)
+  // We form the group (2)+(3), so that (1) has to form groups with access
+  // above (1), which guarantees that (1) is always above (2).
+  for (auto I = StrideAccess.rbegin(), E = StrideAccess.rend(); I != E; ++I) {
+    Instruction *A = I->first;
+    StrideDescriptor DesA = I->second;
+
+    InterleaveGroup *Group = getInterleaveGroup(A);
+    if (!Group) {
+      DEBUG(dbgs() << "LAA: Creating an interleave group with:" << *A << '\n');
+      Group = createInterleaveGroup(A, DesA.Stride, DesA.Align);
+    }
+
+    for (auto II = std::next(I); II != E; ++II) {
+      Instruction *B = II->first;
+      StrideDescriptor DesB = II->second;
+
+      if (A->mayReadFromMemory() != B->mayReadFromMemory())
+        continue;
+
+      // Check the rule 1 and 2.
+      if (DesB.Stride != DesA.Stride || DesB.Size != DesA.Size)
+        continue;
+
+      // Calculate the distance and prepare for the rule 3.
+      const SCEVConstant *DistToA =
+          dyn_cast<SCEVConstant>(SE->getMinusSCEV(DesB.Scev, DesA.Scev));
+      if (!DistToA)
+        continue;
+
+      int DistanceToA = DistToA->getValue()->getValue().getSExtValue();
+      // Read/write the same location.
+      if (!DistanceToA)
+        continue;
+
+      int Size = static_cast<int>(DesA.Size);
+      if (DistanceToA % Size) {
+        // Record the write-write pairs that could be broken after vectorizaton.
+        //
+        // E.g.  char *Tmp = (char *)A;       // A is int*
+        //       int *B = (int *) (++Tmp);
+        //       for(i = 0; i < n; i+=2) {
+        //         A[i]   = a;                // (1)
+        //         B[i]   = b;                // (2)
+        //         A[i+1] = c;                // (3)
+        //       }
+        // The combine of (1) and (3) will be inserted below (2).
+        if (A->mayWriteToMemory())
+          // Reuse the store-load forwarding check for whether there is overlap.
+          if (DepChecker->couldPreventStoreLoadForward(std::abs(DistanceToA),
+                                                       Size))
+            WritePairs.push_back(std::make_pair(B, A));
+        continue;
+      }
+
+      // Skip if B is already in a Group.
+      if (getInterleaveGroup(B))
+        continue;
+
+      // The index of B is the index of A plus the related index to A.
+      int IndexB = Group->getIndex(A) + DistanceToA / Size;
+
+      // Try to insert B into the group.
+      if (Group->insertMember(B, IndexB, DesB.Align)) {
+        DEBUG(dbgs() << "LAA: Inserted:" << *B << '\n'
+                     << "     into the interleave group with" << *A << '\n');
+        InterleaveGroupMap[B] = Group;
+      }
+    }
+  }
+}
+
+void InterleavedAccessInfo::analyzeInterleaving(
+    const ValueToValueMap &Strides) {
+  // Holds load/store instructions in program order.
+  SmallVector<Instruction *, 16> InstrList;
+
+  for (auto BB = TheLoop->block_begin(), BE = TheLoop->block_end(); BB != BE;
+       ++BB) {
+    bool IsPred = LoopAccessInfo::blockNeedsPredication(*BB, TheLoop, DT);
+
+    for (auto I = (*BB)->begin(), E = (*BB)->end(); I != E; ++I) {
+      if (!isa<LoadInst>(I) && !isa<StoreInst>(I))
+        continue;
+      // FIXME: As currently we can't handle predicated access, return directly.
+      if (IsPred)
+        return;
+
+      InstrList.push_back(I);
+    }
+  }
+
+  if (!InstrList.size())
+    return;
+
+  // Holds the write-write pairs that could be broken by the vectorization.
+  SmallVector<std::pair<Instruction *, Instruction *>, 2> WritePairs;
+
+  DEBUG(dbgs() << "LAA: Analyzing interleaved accesses...\n");
+  groupInterleavedAccesses(InstrList, WritePairs, Strides);
+
+  // Filter eligible groups and set the insert position. We only keep the load
+  // group that has small gaps (less than half Delta) and the fully interleaved
+  // store group (has no gap).
+  for (auto I : InstrList) {
+    InterleaveGroup *Group = getInterleaveGroup(I);
+    if (!Group)
+      continue;
+
+    if (I->mayReadFromMemory()) {
+      if (Group->getNumMembers() >= Group->getDelta() / 2) {
+        // Choose the first load in program order.
+        if (!Group->getInsertPos())
+          Group->setInsertPos(I);
+        continue;
+      }
+    } else if (Group->getNumMembers() == Group->getDelta()) {
+      // Choose the last store in program order.
+      Group->setInsertPos(I);
+      continue;
+    }
+
+    releaseGroup(Group);
+  }
+
+  // Make sure the dependence of each write-write pair is still safe.
+  for (auto Pair : WritePairs) {
+    Instruction *A = Pair.first;
+    Instruction *B = Pair.second;
+    auto GroupA = getInterleaveGroup(A);
+    auto GroupB = getInterleaveGroup(B);
+
+    if (!GroupA && !GroupB)
+      continue;
+
+    Instruction *PosA = GroupA ? GroupA->getInsertPos() : A;
+    Instruction *PosB = GroupB ? GroupB->getInsertPos() : B;
+
+    // Continue if neither A nor B will be moved to another position.
+    if (PosA == A && PosB == B)
+      continue;
+
+    bool IsSafe = true;
+
+    for (auto I = InstrList.rbegin(), E = InstrList.rend(); I != E; ++I) {
+      if (*I == PosB)
+        break;
+      // If the position of A is after the position of B, it is unsafe.
+      if (*I == PosA) {
+        IsSafe = false;
+        break;
+      }
+    }
+
+    if (IsSafe)
+      continue;
+
+    if (PosA != A)
+      releaseGroup(GroupA);
+    if (PosB != B)
+      releaseGroup(GroupB);
+  }
+}
+
+void InterleavedAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
+  OS.indent(Depth) << "Interleaved access groups:\n";
+
+  SmallSet<InterleaveGroup *, 4> Seen;
+  for (auto I : InterleaveGroupMap) {
+    if (Seen.count(I.second))
+      continue;
+
+    // Print the group.
+    I.second->print(OS, Depth + 2);
+    OS << "\n";
+    Seen.insert(I.second);
+  }
+}
+
 bool LoopAccessInfo::canAnalyzeLoop() {
   // We need to have a loop header.
   DEBUG(dbgs() << "LAA: Found a loop: " <<
         TheLoop->getHeader()->getName() << '\n');
 
     // We can only analyze innermost loops.
   if (!TheLoop->empty()) {
     DEBUG(dbgs() << "LAA: loop is not the innermost loop\n");
for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e;
         NumStores++;
         Stores.push_back(St);
         DepChecker.addAccess(St);
       }
     } // Next instr.
   } // Next block.
 
   // Now we have two lists that hold the loads and the stores.
   // Next, we find the pointers that they use.
 
   // Check if we see any stores. If there are no stores, then we don't
   // care if the pointers are *restrict*.
   if (!Stores.size()) {
     DEBUG(dbgs() << "LAA: Found a read-only loop!\n");
     CanVecMem = true;
     return;
   }
 
   MemoryDepChecker::DepCandidates DependentAccesses;
   AccessAnalysis Accesses(TheLoop->getHeader()->getModule()->getDataLayout(),
                           AA, LI, DependentAccesses);
 
   // Holds the analyzed pointers. We don't want to call GetUnderlyingObjects
   // multiple times on the same object. If the ptr is accessed twice, once
   // for read and once for write, it will only appear once (on the write
   // list). This is okay, since we are going to check for conflicts between
   // writes and between reads and writes, but not between reads and reads.
   ValueSet Seen;
 
   ValueVector::iterator I, IE;
   for (I = Stores.begin(), IE = Stores.end(); I != IE; ++I) {
     StoreInst *ST = cast<StoreInst>(*I);
     Value* Ptr = ST->getPointerOperand();
     // Check for store to loop invariant address.
     StoreToLoopInvariantAddress |= isUniform(Ptr);
     // If we did *not* see this pointer before, insert it to  the read-write
     // list. At this phase it is only a 'write' list.
     if (Seen.insert(Ptr).second) {
       ++NumReadWrites;
 
       AliasAnalysis::Location Loc = AA->getLocation(ST);
if (IsAnnotatedParallel) {
     DEBUG(dbgs()
           << "LAA: A loop annotated parallel, ignore memory dependency "
           << "checks.\n");
     CanVecMem = true;
     return;
   }
 
   for (I = Loads.begin(), IE = Loads.end(); I != IE; ++I) {
     LoadInst *LD = cast<LoadInst>(*I);
     Value* Ptr = LD->getPointerOperand();
     // If we did *not* see this pointer before, insert it to the
     // read list. If we *did* see it before, then it is already in
     // the read-write list. This allows us to vectorize expressions
     // such as A[i] += x;  Because the address of A[i] is a read-write
     // pointer. This only works if the index of A[i] is consecutive.
     // If the address of i is unknown (for example A[B[i]]) then we may
     // read a few words, modify, and write a few words, and some of the
     // words may be written to the same address.
bool LoopAccessInfo::blockNeedsPredication(BasicBlock *BB, Loop *TheLoop,
   // Blocks that do not dominate the latch need predication.
   BasicBlock* Latch = TheLoop->getLoopLatch();
   return !DT->dominates(BB, Latch);
 }
 
 void LoopAccessInfo::emitAnalysis(LoopAccessReport &Message) {
   assert(!Report && "Multiple reports generated");
   Report = Message;
 }
 
 bool LoopAccessInfo::isUniform(Value *V) const {
   return (SE->isLoopInvariant(SE->getSCEV(V), TheLoop));
 }
 
 // FIXME: this function is currently a duplicate of the one in
 // LoopVectorize.cpp.
 static Instruction *getFirstInst(Instruction *FirstInst, Value *V,
                                  Instruction *Loc) {
   if (FirstInst)
     return FirstInst;
   if (Instruction *I = dyn_cast<Instruction>(V))
     return I->getParent() == Loc->getParent() ? I : nullptr;
   return nullptr;
 }
 
 std::pair<Instruction *, Instruction *> LoopAccessInfo::addRuntimeCheck(
     Instruction *Loc, const SmallVectorImpl<int> *PtrPartition) const {
   if (!PtrRtCheck.Need)
     return std::make_pair(nullptr, nullptr);
 
   unsigned NumPointers = PtrRtCheck.Pointers.size();
   SmallVector<TrackingVH<Value> , 2> Starts;
   SmallVector<TrackingVH<Value> , 2> Ends;
 
   LLVMContext &Ctx = Loc->getContext();
   SCEVExpander Exp(*SE, DL, "induction");
   Instruction *FirstInst = nullptr;
 
   for (unsigned i = 0; i < NumPointers; ++i) {
     Value *Ptr = PtrRtCheck.Pointers[i];
     const SCEV *Sc = SE->getSCEV(Ptr);
 
     if (SE->isLoopInvariant(Sc, TheLoop)) {
       DEBUG(dbgs() << "LAA: Adding RT check for a loop invariant ptr:" <<
             *Ptr <<"\n");
       Starts.push_back(Ptr);
       Ends.push_back(Ptr);
     } else {
       DEBUG(dbgs() << "LAA: Adding RT check for range:" << *Ptr << '\n');
       unsigned AS = Ptr->getType()->getPointerAddressSpace();
 
       // Use this type for pointer arithmetic.
       Type *PtrArithTy = Type::getInt8PtrTy(Ctx, AS);
 
       Value *Start = Exp.expandCodeFor(PtrRtCheck.Starts[i], PtrArithTy, Loc);
       Value *End = Exp.expandCodeFor(PtrRtCheck.Ends[i], PtrArithTy, Loc);
       Starts.push_back(Start);
       Ends.push_back(End);
     }
   }
 
   IRBuilder<> ChkBuilder(Loc);
   // Our instructions might fold to a constant.
   Value *MemoryRuntimeCheck = nullptr;
   for (unsigned i = 0; i < NumPointers; ++i) {
     for (unsigned j = i+1; j < NumPointers; ++j) {
       if (!PtrRtCheck.needsChecking(i, j, PtrPartition))
         continue;
 
       unsigned AS0 = Starts[i]->getType()->getPointerAddressSpace();
       unsigned AS1 = Starts[j]->getType()->getPointerAddressSpace();
 
       assert((AS0 == Ends[j]->getType()->getPointerAddressSpace()) &&
              (AS1 == Ends[i]->getType()->getPointerAddressSpace()) &&
              "Trying to bounds check pointers with different address spaces");
 
       Type *PtrArithTy0 = Type::getInt8PtrTy(Ctx, AS0);
       Type *PtrArithTy1 = Type::getInt8PtrTy(Ctx, AS1);
 
       Value *Start0 = ChkBuilder.CreateBitCast(Starts[i], PtrArithTy0, "bc");
       Value *Start1 = ChkBuilder.CreateBitCast(Starts[j], PtrArithTy1, "bc");
       Value *End0 =   ChkBuilder.CreateBitCast(Ends[i],   PtrArithTy1, "bc");
       Value *End1 =   ChkBuilder.CreateBitCast(Ends[j],   PtrArithTy0, "bc");
 
       Value *Cmp0 = ChkBuilder.CreateICmpULE(Start0, End1, "bound0");
       FirstInst = getFirstInst(FirstInst, Cmp0, Loc);
       Value *Cmp1 = ChkBuilder.CreateICmpULE(Start1, End0, "bound1");
       FirstInst = getFirstInst(FirstInst, Cmp1, Loc);
       Value *IsConflict = ChkBuilder.CreateAnd(Cmp0, Cmp1, "found.conflict");
       FirstInst = getFirstInst(FirstInst, IsConflict, Loc);
       if (MemoryRuntimeCheck) {
         IsConflict = ChkBuilder.CreateOr(MemoryRuntimeCheck, IsConflict,
                                          "conflict.rdx");
         FirstInst = getFirstInst(FirstInst, IsConflict, Loc);
       }
       MemoryRuntimeCheck = IsConflict;
     }
   }
 
   if (!MemoryRuntimeCheck)
     return std::make_pair(nullptr, nullptr);
 
   // We have to do this trickery because the IRBuilder might fold the check to a
   // constant expression in which case there is no Instruction anchored in a
   // the block.
   Instruction *Check = BinaryOperator::CreateAnd(MemoryRuntimeCheck,
                                                  ConstantInt::getTrue(Ctx));
   ChkBuilder.Insert(Check, "memcheck.conflict");
   FirstInst = getFirstInst(FirstInst, Check, Loc);
   return std::make_pair(FirstInst, Check);
 }
 
 LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE,
                                const DataLayout &DL,
                                const TargetLibraryInfo *TLI, AliasAnalysis *AA,
                                DominatorTree *DT, LoopInfo *LI,
                                const ValueToValueMap &Strides)
-    : DepChecker(SE, L), NumComparisons(0), TheLoop(L), SE(SE), DL(DL),
-      TLI(TLI), AA(AA), DT(DT), LI(LI), NumLoads(0), NumStores(0),
-      MaxSafeDepDistBytes(-1U), CanVecMem(false),
-      StoreToLoopInvariantAddress(false) {
+    : DepChecker(SE, L), InterleaveInfo(SE, L, DT, &DepChecker),
+      NumComparisons(0), TheLoop(L), SE(SE), DL(DL), TLI(TLI), AA(AA), DT(DT),
+      LI(LI), NumLoads(0), NumStores(0), MaxSafeDepDistBytes(-1U),
+      CanVecMem(false), StoreToLoopInvariantAddress(false) {
   if (canAnalyzeLoop())
     analyzeLoop(Strides);
+
+  if (CanVecMem && EnableInterleaving)
+    InterleaveInfo.analyzeInterleaving(Strides);
 }
 
 void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
   if (CanVecMem) {
     if (PtrRtCheck.Need)
       OS.indent(Depth) << "Memory dependences are safe with run-time checks\n";
     else
       OS.indent(Depth) << "Memory dependences are safe\n";
void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
 
   // List the pair of accesses need run-time checks to prove independence.
   PtrRtCheck.print(OS, Depth);
   OS << "\n";
 
   OS.indent(Depth) << "Store to invariant address was "
                    << (StoreToLoopInvariantAddress ? "" : "not ")
                    << "found in loop.\n";
+
+  InterleaveInfo.print(OS, Depth);
+  OS << "\n";
 }
 
 const LoopAccessInfo &
 LoopAccessAnalysis::getInfo(Loop *L, const ValueToValueMap &Strides) {
   auto &LAI = LoopAccessInfoMap[L];
 
 #ifndef NDEBUG
   assert((!LAI || LAI->NumSymbolicStrides == Strides.size()) &&
for (Loop *TopLevelLoop : *LI)
     for (Loop *L : depth_first(TopLevelLoop)) {
       OS.indent(2) << L->getHeader()->getName() << ":\n";
       auto &LAI = LAA.getInfo(L, NoSymbolicStrides);
       LAI.print(OS, 4);
     }
 }
 
 bool LoopAccessAnalysis::runOnFunction(Function &F) {
   SE = &getAnalysis<ScalarEvolution>();
   auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
   TLI = TLIP ? &TLIP->getTLI() : nullptr;
   AA = &getAnalysis<AliasAnalysis>();
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 
   return false;
 }
 
 void LoopAccessAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
     AU.addRequired<ScalarEvolution>();
     AU.addRequired<AliasAnalysis>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<LoopInfoWrapperPass>();
 
     AU.setPreservesAll();
 }
 
 char LoopAccessAnalysis::ID = 0;
 static const char laa_name[] = "Loop Access Analysis";
 #define LAA_NAME "loop-accesses"
 

lib/Analysis/TargetTransformInfo.cpp

 
 unsigned
 TargetTransformInfo::getMaskedMemoryOpCost(unsigned Opcode, Type *Src,
                                            unsigned Alignment,
                                            unsigned AddressSpace) const {
   return TTIImpl->getMaskedMemoryOpCost(Opcode, Src, Alignment, AddressSpace);
 }
 
+unsigned TargetTransformInfo::getInterleavedMemoryOpCost(
+    unsigned Opcode, Type *VecTy, unsigned Delta, ArrayRef<unsigned> Indices,
+    unsigned Alignment, unsigned AddressSpace) const {
+  return TTIImpl->getInterleavedMemoryOpCost(Opcode, VecTy, Delta, Indices,
+                                             Alignment, AddressSpace);
+}
+
 unsigned
 TargetTransformInfo::getIntrinsicInstrCost(Intrinsic::ID ID, Type *RetTy,
                                            ArrayRef<Type *> Tys) const {
   return TTIImpl->getIntrinsicInstrCost(ID, RetTy, Tys);
 }
 
 unsigned TargetTransformInfo::getCallInstrCost(Function *F, Type *RetTy,
                                                ArrayRef<Type *> Tys) const {

lib/Transforms/Vectorize/LoopVectorize.cpp

 //===----------------------------------------------------------------------===//
 //
 // The reduction-variable vectorization is based on the paper:
 //  D. Nuzman and R. Henderson. Multi-platform Auto-vectorization.
 //
 // Variable uniformity checks are inspired by:
 //  Karrenberg, R. and Hack, S. Whole Function Vectorization.
 //
+// The interleaved access vectorization is based on the paper:
+//  Dorit Nuzman, Ira Rosen and Ayal Zaks.  Auto-Vectorization of Interleaved
+//  Data for SIMD
+//
 // Other ideas/concepts are from:
 //  A. Zaks and D. Nuzman. Autovectorization in GCC-two years later.
 //
 //  S. Maleki, Y. Gao, M. Garzaran, T. Wong and D. Padua.  An Evaluation of
 //  Vectorizing Compilers.
 //
 //===----------------------------------------------------------------------===//
 

 static cl::opt<unsigned> ForceTargetMaxVectorInterleaveFactor(
     "force-target-max-vector-interleave", cl::init(0), cl::Hidden,
     cl::desc("A flag that overrides the target's max interleave factor for "
              "vectorized loops."));
 
 static cl::opt<unsigned> ForceTargetInstructionCost(
     "force-target-instruction-cost", cl::init(0), cl::Hidden,
     cl::desc("A flag that overrides the target's expected cost for "
              "an instruction to a single constant value. Mostly "
              "useful for getting consistent testing."));
 
 static cl::opt<unsigned> SmallLoopCost(
     "small-loop-cost", cl::init(20), cl::Hidden,
     cl::desc("The cost of a loop that is considered 'small' by the unroller."));
 
 static cl::opt<bool> LoopVectorizeWithBlockFrequency(
     "loop-vectorize-with-block-frequency", cl::init(false), cl::Hidden,
protected:
 
   /// When we go over instructions in the basic block we rely on previous
   /// values within the current basic block or on loop invariant values.
   /// When we widen (vectorize) values we place them in the map. If the values
   /// are not within the map, they have to be loop invariant, so we simply
   /// broadcast them into a vector.
   VectorParts &getVectorValue(Value *V);
 
+  /// Try to vectorize the interleaved access group that \p Instr belongs to.
+  void vectorizeInterleaveGroup(Instruction *Instr);
+
   /// Generate a shuffle sequence that will reverse the vector Vec.
   virtual Value *reverseVector(Value *Vec);
 
   /// This is a helper class that holds the vectorizer state. It maps scalar
   /// instructions to vector instructions. When the code is 'unrolled' then
   /// then a single scalar value is mapped to multiple vector parts. The parts
   /// are stored in the VectorPart type.
   struct ValueMap {
LoopVectorizationLegality(Loop *L, ScalarEvolution *SE, DominatorTree *DT,
                             Function *F, const TargetTransformInfo *TTI,
                             LoopAccessAnalysis *LAA)
       : NumPredStores(0), TheLoop(L), SE(SE), TLI(TLI), TheFunction(F),
         TTI(TTI), DT(DT), LAA(LAA), LAI(nullptr), Induction(nullptr),
         WidestIndTy(nullptr), HasFunNoNaNAttr(false) {}
 
   /// This enum represents the kinds of inductions that we support.
   enum InductionKind {
     IK_NoInduction,  ///< Not an induction variable.
     IK_IntInduction, ///< Integer induction variable. Step = C.
     IK_PtrInduction  ///< Pointer induction var. Step = C / sizeof(elem).
   };
 
   /// A struct for saving information about induction variables.
   struct InductionInfo {
     InductionInfo(Value *Start, InductionKind K, ConstantInt *Step)
         : StartValue(Start), IK(K), StepValue(Step) {
public:
   /// ReductionList contains the reduction descriptors for all
   /// of the reductions that were found in the loop.
   typedef DenseMap<PHINode*, ReductionDescriptor> ReductionList;
 
   /// InductionList saves induction variables and maps them to the
   /// induction descriptor.
   typedef MapVector<PHINode*, InductionInfo> InductionList;
 
   /// Returns true if it is legal to vectorize this loop.
   /// This does not mean that it is profitable to vectorize this
   /// loop, only that it is legal to do so.
   bool canVectorize();
 
   /// Returns the Induction variable.
   PHINode *getInduction() { return Induction; }
 
   /// Returns the reduction variables found in the loop.
   ReductionList *getReductionVars() { return &Reductions; }
 
   /// Returns the induction variables found in the loop.
   InductionList *getInductionVars() { return &Inductions; }
 
   /// Returns the widest induction type.
   Type *getWidestInductionType() { return WidestIndTy; }
 
   /// Returns True if V is an induction variable in this loop.
   bool isInductionVariable(const Value *V);
 
   /// Return true if the block BB needs to be predicated in order for the loop
   /// to be vectorized.
   bool blockNeedsPredication(BasicBlock *BB);
 
   /// Check if this  pointer is consecutive when vectorizing. This happens
   /// when the last index of the GEP is the induction variable, or that the
   /// pointer itself is an induction variable.
   /// This check allows us to vectorize A[idx] into a wide load/store.
   /// Returns:
   /// 0 - Stride is unknown or non-consecutive.
   /// 1 - Address is consecutive.
   /// -1 - Address is consecutive, and decreasing.
   int isConsecutivePtr(Value *Ptr);
 
   /// Returns true if the value V is uniform within the loop.
   bool isUniform(Value *V);
 
   /// Returns true if this instruction will remain scalar after vectorization.
   bool isUniformAfterVectorization(Instruction* I) { return Uniforms.count(I); }
 
   /// Returns the information that we collected about runtime memory check.
   const LoopAccessInfo::RuntimePointerCheck *getRuntimePointerCheck() const {
     return LAI->getRuntimePointerCheck();
   }
 
-  const LoopAccessInfo *getLAI() const {
-    return LAI;
+  const LoopAccessInfo *getLAI() const { return LAI; }
+
+  /// \brief Check if \p Instr belongs to any interleaved access group.
+  bool isAccessInterleaved(Instruction *Instr) {
+    return LAI->isAccessInterleaved(Instr);
+  }
+
+  /// \brief Get the interleaved access group that \p I belongs to.
+  const InterleaveGroup *getInterleavedAccessGroup(Instruction *Instr) {
+    return LAI->getInterleavedAccessGroup(Instr);
   }
 
   unsigned getMaxSafeDepDistBytes() { return LAI->getMaxSafeDepDistBytes(); }
 
   bool hasStride(Value *V) { return StrideSet.count(V); }
   bool mustCheckStrides() { return !StrideSet.empty(); }
   SmallPtrSet<Value *, 8>::iterator strides_begin() {
     return StrideSet.begin();
Value *InnerLoopVectorizer::reverseVector(Value *Vec) {
   for (unsigned i = 0; i < VF; ++i)
     ShuffleMask.push_back(Builder.getInt32(VF - i - 1));
 
   return Builder.CreateShuffleVector(Vec, UndefValue::get(Vec->getType()),
                                      ConstantVector::get(ShuffleMask),
                                      "reverse");
 }
 
+// Get a mask to interleave \p NumVec vectors into a wide vector.
+// I.E  <0, VF, VF*2, ..., VF*(NumVec-1), 1, VF+1, VF*2+1, ...>
+// E.g. For 2 interleaved vectors, if VF is 4, the mask is:
+//      <0, 4, 1, 5, 2, 6, 3, 7>
+static Constant *getInterleavedMask(IRBuilder<> &Builder, unsigned VF,
+                                    unsigned NumVec) {
+  SmallVector<Constant *, 16> Mask;
+  for (unsigned i = 0; i < VF; i++)
+    for (unsigned j = 0; j < NumVec; j++)
+      Mask.push_back(Builder.getInt32(j * VF + i));
+
+  return ConstantVector::get(Mask);
+}
+
+// Get the strided mask starting from index \p Start.
+// I.E.  <Start, Start + Stride, ..., Start + Stride*(VF-1)>
+static Constant *getStridedMask(IRBuilder<> &Builder, unsigned Start,
+                                unsigned Stride, unsigned VF) {
+  SmallVector<Constant *, 16> Mask;
+  for (unsigned i = 0; i < VF; i++)
+    Mask.push_back(Builder.getInt32(Start + i * Stride));
+
+  return ConstantVector::get(Mask);
+}
+
+// Get a mask of two parts: The first part consist of sequential integers
+// starting from 0, The second part consist of UNDEFs.
+// I.E. <0, 1, 2, ..., NumInt - 1, undef, ..., undef>
+static Constant *getSequentialMask(IRBuilder<> &Builder, unsigned NumInt,
+                                   unsigned NumUndef) {
+  SmallVector<Constant *, 16> Mask;
+  for (unsigned i = 0; i < NumInt; i++)
+    Mask.push_back(Builder.getInt32(i));
+
+  // Return directly if there is no undef value.
+  if (!NumUndef)
+    return ConstantVector::get(Mask);
+
+  Constant *Undef = UndefValue::get(Builder.getInt32Ty());
+  for (unsigned i = 0; i < NumUndef; i++)
+    Mask.push_back(Undef);
+  return ConstantVector::get(Mask);
+}
+
+// Concatenate two vectors with the same element type. The 2nd vector should
+// not have more elements than the 1st vector. If the 2nd vector has less
+// elements, extend it with UNDEFs.
+static Value *ConcatenateTwoVectors(IRBuilder<> &Builder, Value *V1,
+                                    Value *V2) {
+  VectorType *VecTy1 = dyn_cast<VectorType>(V1->getType());
+  VectorType *VecTy2 = dyn_cast<VectorType>(V2->getType());
+  assert(VecTy1 && VecTy2 &&
+         VecTy1->getScalarType() == VecTy2->getScalarType() &&
+         "Expect two vectors with the same element type");
+
+  unsigned NumElts1 = VecTy1->getNumElements();
+  unsigned NumElts2 = VecTy2->getNumElements();
+  assert(NumElts1 >= NumElts2 && "Unexpect the first vector has less elements");
+
+  if (NumElts1 > NumElts2) {
+    // Extend with UNDEFs.
+    Constant *ExtMask =
+        getSequentialMask(Builder, NumElts2, NumElts1 - NumElts2);
+    V2 = Builder.CreateShuffleVector(V2, UndefValue::get(VecTy2), ExtMask);
+  }
+
+  Constant *Mask = getSequentialMask(Builder, NumElts1 + NumElts2, 0);
+  return Builder.CreateShuffleVector(V1, V2, Mask);
+}
+
+// Concatenate vectors in the given list. All vectors have the same type.
+static Value *ConcatenateVectors(IRBuilder<> &Builder,
+                                 ArrayRef<Value *> InputList) {
+  unsigned NumVec = InputList.size();
+  assert(NumVec > 1 && "Should be at least two vectors");
+
+  SmallVector<Value *, 8> VecList;
+  SmallVector<Value *, 8> TmpList;
+  VecList.append(InputList.begin(), InputList.end());
+  do {
+    for (unsigned i = 0; i < NumVec / 2; i++)
+      TmpList.push_back(
+          ConcatenateTwoVectors(Builder, VecList[2 * i], VecList[2 * i + 1]));
+
+    // Push the last vector if the total number of vectors is odd.
+    if (NumVec % 2 != 0)
+      TmpList.push_back(VecList[NumVec - 1]);
+
+    VecList.clear();
+    VecList.append(TmpList.begin(), TmpList.end());
+    NumVec = VecList.size();
+    TmpList.clear();
+  } while (NumVec > 1);
+
+  return VecList[0];
+}
+
+// Try to vectorize the interleave group that \p Instr belongs to.
+//
+// E.g. Translate following interleaved load group (Delta is 3):
+//   for (i = 0; i < N; i+=3) {
+//     R = Pic[i];             // Member of index 0
+//     G = Pic[i+1];           // Member of index 1
+//     B = Pic[i+2];           // Member of index 2
+//     ... // do something to R, G, B
+//   }
+// To:
+//   %wide.vec = load <12 x i32>                       ; Read 4 tuples of R,G,B
+//   %R.vec = shuffle %wide.vec, undef, <0, 3, 6, 9>   ; R elements
+//   %G.vec = shuffle %wide.vec, undef, <1, 4, 7, 10>  ; G elements
+//   %B.vec = shuffle %wide.vec, undef, <2, 5, 8, 11>  ; B elements
+//
+// Or translate following interleaved store group (Delta is 3):
+//   for (i = 0; i < N; i+=3) {
+//     ... do something to R, G, B
+//     Pic[i]   = R;           // Member of index 0
+//     Pic[i+1] = G;           // Member of index 1
+//     Pic[i+2] = B;           // Member of index 2
+//   }
+// To:
+//   %R_G.vec = shuffle %R.vec, %G.vec, <0, 1, 2, ..., 7>
+//   %B_U.vec = shuffle %B.vec, undef, <0, 1, 2, 3, u, u, u, u>
+//   %interleaved.vec = shuffle %R_G.vec, %B_U.vec,
+//        <0, 4, 8, 1, 5, 9, 2, 6, 10, 3, 7, 11>    ; Interleave R,G,B elements
+//   store <12 x i32> %interleaved.vec              ; Write 4 tuples of R,G,B
+void InnerLoopVectorizer::vectorizeInterleaveGroup(Instruction *Instr) {
+  const InterleaveGroup *Group = Legal->getInterleavedAccessGroup(Instr);
+  assert(Group && "Fail to get an interleaved access group.");
+
+  // Skip if current instruction is not the insert position.
+  if (Instr != Group->getInsertPos())
+    return;
+
+  LoadInst *LI = dyn_cast<LoadInst>(Instr);
+  StoreInst *SI = dyn_cast<StoreInst>(Instr);
+  Value *Ptr = LI ? LI->getPointerOperand() : SI->getPointerOperand();
+
+  // Prepare for the vector type of the interleaved load/store.
+  Type *ScalarTy = LI ? LI->getType() : SI->getValueOperand()->getType();
+  unsigned Delta = Group->getDelta();
+  Type *VecTy = VectorType::get(ScalarTy, Delta * VF);
+  Type *PtrTy = VecTy->getPointerTo(Ptr->getType()->getPointerAddressSpace());
+
+  // Prepare for the new pointers.
+  setDebugLocFromInst(Builder, Ptr);
+  VectorParts &PtrParts = getVectorValue(Ptr);
+  SmallVector<Value *, 2> NewPtrs;
+  unsigned Index = Group->getIndex(Instr);
+  for (unsigned Part = 0; Part < UF; Part++) {
+    // Notice current instruction could be any index. Need to adjust the address
+    // to the member of index 0.
+    //
+    // E.g.  a = A[i+1];     // Member of index 1 (Current instruction)
+    //       b = A[i];       // Member of index 0
+    // Current pointer is pointed to A[i+1], adjust it to A[i].
+    //
+    // E.g.  A[i+1] = a;     // Member of index 1
+    //       A[i]   = b;     // Member of index 0
+    //       A[i+2] = c;     // Member of index 2 (Current instruction)
+    // Current pointer is pointed to A[i+2], adjust it to A[i].
+    Value *NewPtr =
+        Builder.CreateExtractElement(PtrParts[Part], Builder.getInt32(0));
+    NewPtr = Builder.CreateGEP(NewPtr, Builder.getInt32(-Index));
+
+    // If the address is reverse, then the vector load/store needs to start at
+    // the last access of index 0.
+    // E.g. For the reversed access of interleaved load with 2 members:
+    //      {A[i], A[i+1]}, {A[i-2], A[i-1]}, {A[i-4], A[i-3]}, {A[i-6], A[i-5]}
+    // The new pointer is now pointed to A[i]. Adjust it to A[i-6].
+    if (Group->isReverse())
+      NewPtr = Builder.CreateGEP(NewPtr, Builder.getInt32(-(Delta * (VF - 1))));
+
+    // Cast to the vector pointer type.
+    NewPtrs.push_back(Builder.CreateBitCast(NewPtr, PtrTy));
+  }
+
+  setDebugLocFromInst(Builder, Instr);
+  Value *UndefVec = UndefValue::get(VecTy);
+
+  // Vectorize the interleaved load group.
+  if (LI) {
+    for (unsigned Part = 0; Part < UF; Part++) {
+      Instruction *CallI = Builder.CreateAlignedLoad(
+          NewPtrs[Part], Group->getAlign(), "wide.vec");
+
+      for (unsigned i = 0; i < Delta; i++) {
+        Instruction *Member = Group->getMember(i);
+
+        // Skip the gaps in the group.
+        if (!Member)
+          continue;
+
+        Constant *StrideMask = getStridedMask(Builder, i, Delta, VF);
+        Value *StridedVec = Builder.CreateShuffleVector(
+            CallI, UndefVec, StrideMask, "strided.vec");
+
+        // If this member has different type, cast the result type.
+        if (Member->getType() != ScalarTy) {
+          VectorType *OtherVTy = VectorType::get(Member->getType(), VF);
+          StridedVec = Builder.CreateBitOrPointerCast(StridedVec, OtherVTy);
+        }
+
+        VectorParts &Entry = WidenMap.get(Member);
+        Entry[Part] =
+            Group->isReverse() ? reverseVector(StridedVec) : StridedVec;
+      }
+
+      propagateMetadata(CallI, Instr);
+    }
+    return;
+  }
+
+  // The sub vector type for current instruction.
+  VectorType *SubVT = VectorType::get(ScalarTy, VF);
+
+  // Vectorize the interleaved store group.
+  for (unsigned Part = 0; Part < UF; Part++) {
+    // Collect the stored vector from each member.
+    SmallVector<Value *, 4> StoredVecs;
+    for (unsigned i = 0; i < Delta; i++) {
+      // Interleaved store group doesn't allow a gap, so each index has a member
+      Instruction *Member = Group->getMember(i);
+      assert(Member && "Fail to get a member from an interleaved store group");
+
+      Value *StoredVec =
+          getVectorValue(dyn_cast<StoreInst>(Member)->getValueOperand())[Part];
+      if (Group->isReverse())
+        StoredVec = reverseVector(StoredVec);
+
+      // If this member has different type, cast it to a unified type.
+      if (StoredVec->getType() != SubVT)
+        StoredVec = Builder.CreateBitOrPointerCast(StoredVec, SubVT);
+
+      StoredVecs.push_back(StoredVec);
+    }
+
+    // Concatenate all vectors into a wide vector.
+    Value *WideVec = ConcatenateVectors(Builder, StoredVecs);
+
+    // Interleave the elements in the vector.
+    Constant *IMask = getInterleavedMask(Builder, VF, Delta);
+    Value *IVec = Builder.CreateShuffleVector(WideVec, UndefVec, IMask,
+                                              "interleaved.vec");
+
+    Instruction *CallI =
+        Builder.CreateAlignedStore(IVec, NewPtrs[Part], Group->getAlign());
+    propagateMetadata(CallI, Instr);
+  }
+}
+
 void InnerLoopVectorizer::vectorizeMemoryInstruction(Instruction *Instr) {
   // Attempt to issue a wide load.
   LoadInst *LI = dyn_cast<LoadInst>(Instr);
   StoreInst *SI = dyn_cast<StoreInst>(Instr);
 
   assert((LI || SI) && "Invalid Load/Store instruction");
 
+  // Try to vectorize the interleave group if this access is interleaved.
+  if (Legal->isAccessInterleaved(Instr))
+    return vectorizeInterleaveGroup(Instr);
+
   Type *ScalarDataTy = LI ? LI->getType() : SI->getValueOperand()->getType();
   Type *DataTy = VectorType::get(ScalarDataTy, VF);
   Value *Ptr = LI ? LI->getPointerOperand() : SI->getPointerOperand();
   unsigned Alignment = LI ? LI->getAlignment() : SI->getAlignment();
   // An alignment of 0 means target abi alignment. We need to use the scalar's
   // target abi alignment in such a case.
   const DataLayout &DL = Instr->getModule()->getDataLayout();
   if (!Alignment)
DEBUG(dbgs() << "LV: We can vectorize this loop" <<
         <<"!\n");
 
   // Okay! We can vectorize. At this point we don't have any other mem analysis
   // which may limit our maximum vectorization factor, so just return true with
   // no restrictions.
   return true;
 }
 
 static Type *convertPointerToIntegerType(const DataLayout &DL, Type *Ty) {
   if (Ty->isPointerTy())
     return DL.getIntPtrType(Ty);
 
   // It is possible that char's or short's overflow when we ask for the loop's
   // trip count, work around this by changing the type size.
   if (Ty->getScalarSizeInBits() < 32)
     return Type::getInt32Ty(Ty->getContext());
 
   return Ty;
 }
 
 static Type* getWiderType(const DataLayout &DL, Type *Ty0, Type *Ty1) {
   Ty0 = convertPointerToIntegerType(DL, Ty0);
   Ty1 = convertPointerToIntegerType(DL, Ty1);
   if (Ty0->getScalarSizeInBits() > Ty1->getScalarSizeInBits())
     return Ty0;
   return Ty1;
 }
 
 /// \brief Check that the instruction has outside loop users and is not an
 /// identified reduction variable.
 static bool hasOutsideLoopUser(const Loop *TheLoop, Instruction *Inst,
                                SmallPtrSetImpl<Value *> &Reductions) {
   // Reduction instructions are allowed to have exit users. All other
   // instructions must not have external users.
   if (!Reductions.count(Inst))
     //Check that all of the users of the loop are inside the BB.
     for (User *U : Inst->users()) {
       Instruction *UI = cast<Instruction>(U);
       // This user may be a reduction exit value.
       if (!TheLoop->contains(UI)) {
         DEBUG(dbgs() << "LV: Found an outside user for : " << *UI << '\n');
         return true;
       }
     }
   return false;
 }
 
 bool LoopVectorizationLegality::canVectorizeInstrs() {
   BasicBlock *PreHeader = TheLoop->getLoopPreheader();
   BasicBlock *Header = TheLoop->getHeader();
 
   // Look for the attribute signaling the absence of NaNs.
   Function &F = *Header->getParent();
   const DataLayout &DL = F.getParent()->getDataLayout();
   if (F.hasFnAttribute("no-nans-fp-math"))
     HasFunNoNaNAttr =
         F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
 
   // For each block in the loop.
   for (Loop::block_iterator bb = TheLoop->block_begin(),
        be = TheLoop->block_end(); bb != be; ++bb) {
 
     // Scan the instructions in the block and look for hazards.
     for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e;
          ++it) {
 
       if (PHINode *Phi = dyn_cast<PHINode>(it)) {
         Type *PhiTy = Phi->getType();
         // Check that this PHI type is allowed.
         if (!PhiTy->isIntegerTy() &&
             !PhiTy->isFloatingPointTy() &&
             !PhiTy->isPointerTy()) {
           emitAnalysis(VectorizationReport(it)
                        << "loop control flow is not understood by vectorizer");
           DEBUG(dbgs() << "LV: Found an non-int non-pointer PHI.\n");
           return false;
         }
 
         // If this PHINode is not in the header block, then we know that we
         // can convert it to select during if-conversion. No need to check if
         // the PHIs in this block are induction or reduction variables.
         if (*bb != Header) {
           // Check that this instruction has no outside users or is an
           // identified reduction value with an outside user.
           if (!hasOutsideLoopUser(TheLoop, it, AllowedExit))
             continue;
           emitAnalysis(VectorizationReport(it) <<
                        "value could not be identified as "
                        "an induction or reduction variable");
           return false;
         }
 
         // We only allow if-converted PHIs with exactly two incoming values.
         if (Phi->getNumIncomingValues() != 2) {
           emitAnalysis(VectorizationReport(it)
                        << "control flow not understood by vectorizer");
           DEBUG(dbgs() << "LV: Found an invalid PHI.\n");
           return false;
         }
 
         // This is the value coming from the preheader.
         Value *StartValue = Phi->getIncomingValueForBlock(PreHeader);
         ConstantInt *StepValue = nullptr;
         // Check if this is an induction variable.
         InductionKind IK = isInductionVariable(Phi, StepValue);
 
         if (IK_NoInduction != IK) {
           // Get the widest type.
           if (!WidestIndTy)
             WidestIndTy = convertPointerToIntegerType(DL, PhiTy);
           else
             WidestIndTy = getWiderType(DL, PhiTy, WidestIndTy);
 
           // Int inductions are special because we only allow one IV.
           if (IK == IK_IntInduction && StepValue->isOne()) {
             // Use the phi node with the widest type as induction. Use the last
             // one if there are multiple (no good reason for doing this other
             // than it is expedient).
             if (!Induction || PhiTy == WidestIndTy)
               Induction = Phi;
           }
 
           DEBUG(dbgs() << "LV: Found an induction variable.\n");
           Inductions[Phi] = InductionInfo(StartValue, IK, StepValue);
 
           // Until we explicitly handle the case of an induction variable with
           // an outside loop user we have to give up vectorizing this loop.
           if (hasOutsideLoopUser(TheLoop, it, AllowedExit)) {
             emitAnalysis(VectorizationReport(it) <<
                          "use of induction value outside of the "
                          "loop is not handled by vectorizer");
             return false;
           }
 
           continue;
         }
 
         if (ReductionDescriptor::isReductionPHI(Phi, TheLoop,
                                                 Reductions[Phi])) {
           AllowedExit.insert(Reductions[Phi].getLoopExitInstr());
           continue;
         }
 
         emitAnalysis(VectorizationReport(it) <<
                      "value that could not be identified as "
                      "reduction is used outside the loop");
         DEBUG(dbgs() << "LV: Found an unidentified PHI."<< *Phi <<"\n");
         return false;
       }// end of PHI handling
 
       // We handle calls that:
       //   * Are debug info intrinsics.
       //   * Have a mapping to an IR intrinsic.
       //   * Have a vector version available.
       CallInst *CI = dyn_cast<CallInst>(it);
       if (CI && !getIntrinsicIDForCall(CI, TLI) && !isa<DbgInfoIntrinsic>(CI) &&
           !(CI->getCalledFunction() && TLI &&
             TLI->isFunctionVectorizable(CI->getCalledFunction()->getName()))) {
         emitAnalysis(VectorizationReport(it) <<
                      "call instruction cannot be vectorized");
         DEBUG(dbgs() << "LV: Found a non-intrinsic, non-libfunc callsite.\n");
         return false;
       }
 
       // Intrinsics such as powi,cttz and ctlz are legal to vectorize if the
       // second argument is the same (i.e. loop invariant)
       if (CI &&
           hasVectorInstrinsicScalarOpd(getIntrinsicIDForCall(CI, TLI), 1)) {
         if (!SE->isLoopInvariant(SE->getSCEV(CI->getOperand(1)), TheLoop)) {
           emitAnalysis(VectorizationReport(it)
                        << "intrinsic instruction cannot be vectorized");
           DEBUG(dbgs() << "LV: Found unvectorizable intrinsic " << *CI << "\n");
           return false;
         }
       }
 
       // Check that the instruction return type is vectorizable.
       // Also, we can't vectorize extractelement instructions.
       if ((!VectorType::isValidElementType(it->getType()) &&
            !it->getType()->isVoidTy()) || isa<ExtractElementInst>(it)) {
         emitAnalysis(VectorizationReport(it)
                      << "instruction return type cannot be vectorized");
         DEBUG(dbgs() << "LV: Found unvectorizable type.\n");
         return false;
       }
 
       // Check that the stored type is vectorizable.
       if (StoreInst *ST = dyn_cast<StoreInst>(it)) {
         Type *T = ST->getValueOperand()->getType();
         if (!VectorType::isValidElementType(T)) {
           emitAnalysis(VectorizationReport(ST) <<
                        "store instruction cannot be vectorized");
           return false;
         }
         if (EnableMemAccessVersioning)
           collectStridedAccess(ST);
       }
 
       if (EnableMemAccessVersioning)
         if (LoadInst *LI = dyn_cast<LoadInst>(it))
           collectStridedAccess(LI);
 
       // Reduction instructions are allowed to have exit users.
       // All other instructions must not have external users.
       if (hasOutsideLoopUser(TheLoop, it, AllowedExit)) {
         emitAnalysis(VectorizationReport(it) <<
                      "value cannot be used outside the loop");
         return false;
       }
 
     } // next instr.
 
   }
 
   if (!Induction) {
     DEBUG(dbgs() << "LV: Did not find one integer induction var.\n");
     if (Inductions.empty()) {
       emitAnalysis(VectorizationReport()
                    << "loop induction variable could not be identified");
       return false;
     }
   }
 
   return true;
 }
 
 ///\brief Remove GEPs whose indices but the last one are loop invariant and
 /// return the induction operand of the gep pointer.
 static Value *stripGetElementPtr(Value *Ptr, ScalarEvolution *SE, Loop *Lp) {
   GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr);
   if (!GEP)
     return Ptr;
 
   unsigned InductionOperand = getGEPInductionOperand(GEP);
 
   // Check that all of the gep indices are uniform except for our induction
   // operand.
   for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i)
     if (i != InductionOperand &&
         !SE->isLoopInvariant(SE->getSCEV(GEP->getOperand(i)), Lp))
       return Ptr;
   return GEP->getOperand(InductionOperand);
 }
 
 ///\brief Look for a cast use of the passed value.
 static Value *getUniqueCastUse(Value *Ptr, Loop *Lp, Type *Ty) {
   Value *UniqueCast = nullptr;
   for (User *U : Ptr->users()) {
     CastInst *CI = dyn_cast<CastInst>(U);
     if (CI && CI->getType() == Ty) {
       if (!UniqueCast)
         UniqueCast = CI;
       else
         return nullptr;
     }
   }
   return UniqueCast;
 }
 
 ///\brief Get the stride of a pointer access in a loop.
 /// Looks for symbolic strides "a[i*stride]". Returns the symbolic stride as a
 /// pointer to the Value, or null otherwise.
 static Value *getStrideFromPointer(Value *Ptr, ScalarEvolution *SE, Loop *Lp) {
   const PointerType *PtrTy = dyn_cast<PointerType>(Ptr->getType());
   if (!PtrTy || PtrTy->isAggregateType())
     return nullptr;
 
   // Try to remove a gep instruction to make the pointer (actually index at this
   // point) easier analyzable. If OrigPtr is equal to Ptr we are analzying the
   // pointer, otherwise, we are analyzing the index.
   Value *OrigPtr = Ptr;
 
   // The size of the pointer access.
   int64_t PtrAccessSize = 1;
 
   Ptr = stripGetElementPtr(Ptr, SE, Lp);
   const SCEV *V = SE->getSCEV(Ptr);
 
   if (Ptr != OrigPtr)
     // Strip off casts.
     while (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(V))
       V = C->getOperand();
 
   const SCEVAddRecExpr *S = dyn_cast<SCEVAddRecExpr>(V);
   if (!S)
     return nullptr;
 
   V = S->getStepRecurrence(*SE);
   if (!V)
     return nullptr;
 
   // Strip off the size of access multiplication if we are still analyzing the
   // pointer.
   if (OrigPtr == Ptr) {
     const DataLayout &DL = Lp->getHeader()->getModule()->getDataLayout();
     DL.getTypeAllocSize(PtrTy->getElementType());
     if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(V)) {
       if (M->getOperand(0)->getSCEVType() != scConstant)
         return nullptr;
 
       const APInt &APStepVal =
           cast<SCEVConstant>(M->getOperand(0))->getValue()->getValue();
 
       // Huge step value - give up.
       if (APStepVal.getBitWidth() > 64)
static Value *getStrideFromPointer(Value *Ptr, ScalarEvolution *SE, Loop *Lp) {
   // If we have stripped off the recurrence cast we have to make sure that we
   // return the value that is used in this loop so that we can replace it later.
   if (StripedOffRecurrenceCast)
     Stride = getUniqueCastUse(Stride, Lp, StripedOffRecurrenceCast);
 
   return Stride;
 }
 
 void LoopVectorizationLegality::collectStridedAccess(Value *MemAccess) {
   Value *Ptr = nullptr;
   if (LoadInst *LI = dyn_cast<LoadInst>(MemAccess))
     Ptr = LI->getPointerOperand();
   else if (StoreInst *SI = dyn_cast<StoreInst>(MemAccess))
     Ptr = SI->getPointerOperand();
   else
     return;
 
LoopVectorizationCostModel::selectVectorizationFactor(bool OptForSize) {
   unsigned WidestRegister = TTI.getRegisterBitWidth(true);
   unsigned MaxSafeDepDist = -1U;
   if (Legal->getMaxSafeDepDistBytes() != -1U)
     MaxSafeDepDist = Legal->getMaxSafeDepDistBytes() * 8;
   WidestRegister = ((WidestRegister < MaxSafeDepDist) ?
                     WidestRegister : MaxSafeDepDist);
   unsigned MaxVectorSize = WidestRegister / WidestType;
   DEBUG(dbgs() << "LV: The Widest type: " << WidestType << " bits.\n");
   DEBUG(dbgs() << "LV: The Widest register is: "
           << WidestRegister << " bits.\n");
 
   if (MaxVectorSize == 0) {
     DEBUG(dbgs() << "LV: The target has no vector registers.\n");
     MaxVectorSize = 1;
   }
 
   assert(MaxVectorSize <= 64 && "Did not expect to pack so many elements"
unsigned LoopVectorizationCostModel::getWidestType() {
   unsigned MaxWidth = 8;
   const DataLayout &DL = TheFunction->getParent()->getDataLayout();
 
   // For each block.
   for (Loop::block_iterator bb = TheLoop->block_begin(),
        be = TheLoop->block_end(); bb != be; ++bb) {
     BasicBlock *BB = *bb;
 
     // For each instruction in the loop.
     for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
       Type *T = it->getType();
 
       // Ignore ephemeral values.
       if (EphValues.count(it))
         continue;
 
       // Only examine Loads, Stores and PHINodes.
       if (!isa<LoadInst>(it) && !isa<StoreInst>(it) && !isa<PHINode>(it))
         continue;
 
       // Examine PHI nodes that are reduction variables.
       if (PHINode *PN = dyn_cast<PHINode>(it))
         if (!Legal->getReductionVars()->count(PN))
           continue;
 
case Instruction::Load: {
     Value *Ptr = SI ? SI->getPointerOperand() : LI->getPointerOperand();
     // We add the cost of address computation here instead of with the gep
     // instruction because only here we know whether the operation is
     // scalarized.
     if (VF == 1)
       return TTI.getAddressComputationCost(VectorTy) +
         TTI.getMemoryOpCost(I->getOpcode(), VectorTy, Alignment, AS);
 
+    // Interleaved access
+    if (Legal->isAccessInterleaved(I)) {
+      auto Group = Legal->getInterleavedAccessGroup(I);
+      assert(Group && "Fail to get an interleaved access group.");
+
+      // Only calculate the cost once.
+      if (Group->getInsertPos() != I)
+        return 0;
+
+      unsigned Delta = Group->getDelta();
+      Type *WideVecTy =
+          VectorType::get(VectorTy->getVectorElementType(),
+                          VectorTy->getVectorNumElements() * Delta);
+
+      SmallVector<unsigned, 4> Indices;
+      if (LI) {
+        // Collect the gaps in interleaved loads. No need to do this for
+        // interleaved stores, which only support fully interleave without gap.
+        for (unsigned i = 0; i < Delta; i++)
+          if (Group->getMember(i))
+            Indices.push_back(i);
+      }
+
+      // Calculate the cost of the whole interleaved group.
+      unsigned Cost = TTI.getInterleavedMemoryOpCost(I->getOpcode(), WideVecTy,
+                                                     Group->getDelta(), Indices,
+                                                     Group->getAlign(), AS);
+
+      if (Group->isReverse())
+        Cost +=
+            Group->getNumMembers() *
+            TTI.getShuffleCost(TargetTransformInfo::SK_Reverse, VectorTy, 0);
+      return Cost;
+    }
+
     // Scalarized loads/stores.
     int ConsecutiveStride = Legal->isConsecutivePtr(Ptr);
     bool Reverse = ConsecutiveStride < 0;
     const DataLayout &DL = I->getModule()->getDataLayout();
     unsigned ScalarAllocatedSize = DL.getTypeAllocSize(ValTy);
     unsigned VectorElementSize = DL.getTypeStoreSize(VectorTy) / VF;
     if (!ConsecutiveStride || ScalarAllocatedSize != VectorElementSize) {
       bool IsComplexComputation =

test/Analysis/LoopAccessAnalysis/analyze-interleaving.ll

+; RUN: opt -S -loop-accesses -analyze -enable-interleaving=true -runtime-memory-check-threshold=24 < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
+
+; Check an interleaved load group of Delta 2 and an interleaved store group of
+; Delta 2.
+
+; int AB[1024];
+; int CD[1024];
+;  void test_array_load2_store2(int C, int D) {
+;   for (int i = 0; i < 1024; i+=2) {
+;     int A = AB[i];
+;     int B = AB[i+1];
+;     CD[i] = A + C;
+;     CD[i+1] = B * D;
+;   }
+; }
+
+; CHECK: Interleaved access groups:
+; CHECK: Interleave Group of Delta 2:
+; CHECK-NEXT:   Index 0:
+; CHECK-NEXT:   Index 1:
+; CHECK: Interleave Group of Delta 2:
+; CHECK-NEXT:   Index 0:
+; CHECK-NEXT:   Index 1:
+
+%struct.ST2 = type { i32, i32 }
+@AB = common global [1024 x i32] zeroinitializer, align 4
+@CD = common global [1024 x i32] zeroinitializer, align 4
+
+define void @test_array_load2_store2(i32 %C, i32 %D) {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx0 = getelementptr inbounds [1024 x i32], [1024 x i32]* @AB, i64 0, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx0, align 4
+  %1 = or i64 %indvars.iv, 1
+  %arrayidx1 = getelementptr inbounds [1024 x i32], [1024 x i32]* @AB, i64 0, i64 %1
+  %2 = load i32, i32* %arrayidx1, align 4
+  %add = add nsw i32 %0, %C
+  %mul = mul nsw i32 %2, %D
+  %arrayidx2 = getelementptr inbounds [1024 x i32], [1024 x i32]* @CD, i64 0, i64 %indvars.iv
+  store i32 %add, i32* %arrayidx2, align 4
+  %arrayidx3 = getelementptr inbounds [1024 x i32], [1024 x i32]* @CD, i64 0, i64 %1
+  store i32 %mul, i32* %arrayidx3, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 2
+  %cmp = icmp slt i64 %indvars.iv.next, 1024
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
+
+; Check an interleaved load group of Delta 3 and an interleaved store group of
+; Delta 3.
+
+; int A[3072];
+; struct ST3 S[1024];
+; void test_struct_st3() {
+;   int *ptr = A;
+;   for (int i = 0; i < 1024; i++) {
+;     int X1 = *ptr++;
+;     int X2 = *ptr++;
+;     int X3 = *ptr++;
+;     S[i].x = X1 + 1;
+;     S[i].y = X2 + 2;
+;     S[i].z = X3 + 3;
+;   }
+; }
+
+; CHECK: Interleaved access groups:
+; CHECK: Interleave Group of Delta 3:
+; CHECK-NEXT:   Index 0:
+; CHECK-NEXT:   Index 1:
+; CHECK-NEXT:   Index 2:
+; CHECK: Interleave Group of Delta 3:
+; CHECK-NEXT:   Index 0:
+; CHECK-NEXT:   Index 1:
+; CHECK-NEXT:   Index 2:
+
+%struct.ST3 = type { i32, i32, i32 }
+@A = common global [3072 x i32] zeroinitializer, align 4
+@S = common global [1024 x %struct.ST3] zeroinitializer, align 4
+
+define void @test_struct_array_load3_store3() {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %ptr.016 = phi i32* [ getelementptr inbounds ([3072 x i32], [3072 x i32]* @A, i64 0, i64 0), %entry ], [ %incdec.ptr2, %for.body ]
+  %incdec.ptr = getelementptr inbounds i32, i32* %ptr.016, i64 1
+  %0 = load i32, i32* %ptr.016, align 4
+  %incdec.ptr1 = getelementptr inbounds i32, i32* %ptr.016, i64 2
+  %1 = load i32, i32* %incdec.ptr, align 4
+  %incdec.ptr2 = getelementptr inbounds i32, i32* %ptr.016, i64 3
+  %2 = load i32, i32* %incdec.ptr1, align 4
+  %add = add nsw i32 %0, 1
+  %x = getelementptr inbounds [1024 x %struct.ST3], [1024 x %struct.ST3]* @S, i64 0, i64 %indvars.iv, i32 0
+  store i32 %add, i32* %x, align 4
+  %add3 = add nsw i32 %1, 2
+  %y = getelementptr inbounds [1024 x %struct.ST3], [1024 x %struct.ST3]* @S, i64 0, i64 %indvars.iv, i32 1
+  store i32 %add3, i32* %y, align 4
+  %add6 = add nsw i32 %2, 3
+  %z = getelementptr inbounds [1024 x %struct.ST3], [1024 x %struct.ST3]* @S, i64 0, i64 %indvars.iv, i32 2
+  store i32 %add6, i32* %z, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 1024
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
+
+; Check an interleaved load group of Delta 4.
+
+; struct ST4{
+;   int x;
+;   int y;
+;   int z;
+;   int w;
+; };
+; int test_struct_load4(struct ST4 *S) {
+;   int r = 0;
+;   for (int i = 0; i < 1024; i++) {
+;      r += S[i].x;
+;      r -= S[i].y;
+;      r += S[i].z;
+;      r -= S[i].w;
+;   }
+;   return r;
+; }
+
+; CHECK: Interleaved access groups:
+; CHECK: Interleave Group of Delta 4:
+; CHECK-NEXT:   Index 0:  %0 = load i32, i32* %x, align 4
+; CHECK-NEXT:   Index 1:  %1 = load i32, i32* %y, align 4
+; CHECK-NEXT:   Index 2:  %2 = load i32, i32* %z, align 4
+; CHECK-NEXT:   Index 3:  %3 = load i32, i32* %w, align 4
+
+%struct.ST4 = type { i32, i32, i32, i32 }
+
+define i32 @test_struct_load4(%struct.ST4* nocapture readonly %S) {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %r.022 = phi i32 [ 0, %entry ], [ %sub8, %for.body ]
+  %x = getelementptr inbounds %struct.ST4, %struct.ST4* %S, i64 %indvars.iv, i32 0
+  %0 = load i32, i32* %x, align 4
+  %add = add nsw i32 %0, %r.022
+  %y = getelementptr inbounds %struct.ST4, %struct.ST4* %S, i64 %indvars.iv, i32 1
+  %1 = load i32, i32* %y, align 4
+  %sub = sub i32 %add, %1
+  %z = getelementptr inbounds %struct.ST4, %struct.ST4* %S, i64 %indvars.iv, i32 2
+  %2 = load i32, i32* %z, align 4
+  %add5 = add nsw i32 %sub, %2
+  %w = getelementptr inbounds %struct.ST4, %struct.ST4* %S, i64 %indvars.iv, i32 3
+  %3 = load i32, i32* %w, align 4
+  %sub8 = sub i32 %add5, %3
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 1024
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret i32 %sub8
+}
+
+; Check on an interleaved store group of Delta 4.
+
+; int B[1024];
+; struct ST4 T[1024];
+; void test_struct_store4() {
+;   int *ptr = B;
+;   for (int i = 0; i < 1024; i++) {
+;     int X = *ptr++;
+;     T[i].x = X + 1;
+;     T[i].y = X * 2;
+;     T[i].z = X + 3;
+;     T[i].w = X + 4;
+;   }
+; }
+
+; CHECK: Interleaved access groups:
+; CHECK: Interleave Group of Delta 4:
+; CHECK-NEXT:   Index 0:  store i32 %add, i32* %x, align 4
+; CHECK-NEXT:   Index 1:  store i32 %mul, i32* %y, align 4
+; CHECK-NEXT:   Index 2:  store i32 %sub, i32* %z, align 4
+; CHECK-NEXT:   Index 3:  store i32 %add5, i32* %w, align 4
+
+@B = common global [1024 x i32] zeroinitializer, align 4
+@T = common global [1024 x %struct.ST4] zeroinitializer, align 4
+
+define void @test_struct_store4() {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %ptr.017 = phi i32* [ getelementptr inbounds ([1024 x i32], [1024 x i32]* @B, i64 0, i64 0), %entry ], [ %incdec.ptr, %for.body ]
+  %incdec.ptr = getelementptr inbounds i32, i32* %ptr.017, i64 1
+  %0 = load i32, i32* %ptr.017, align 4
+  %add = add nsw i32 %0, 1
+  %x = getelementptr inbounds [1024 x %struct.ST4], [1024 x %struct.ST4]* @T, i64 0, i64 %indvars.iv, i32 0
+  store i32 %add, i32* %x, align 4
+  %mul = shl nsw i32 %0, 1
+  %y = getelementptr inbounds [1024 x %struct.ST4], [1024 x %struct.ST4]* @T, i64 0, i64 %indvars.iv, i32 1
+  store i32 %mul, i32* %y, align 4
+  %sub = add nsw i32 %0, 3
+  %z = getelementptr inbounds [1024 x %struct.ST4], [1024 x %struct.ST4]* @T, i64 0, i64 %indvars.iv, i32 2
+  store i32 %sub, i32* %z, align 4
+  %add5 = add nsw i32 %0, 4
+  %w = getelementptr inbounds [1024 x %struct.ST4], [1024 x %struct.ST4]* @T, i64 0, i64 %indvars.iv, i32 3
+  store i32 %add5, i32* %w, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 1024
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
+
+; Check a reverse interleaved load group of Delta 4 and a reverse interleaved
+; store group of Delta 4.
+
+; struct ST2 {
+;  int x;
+;  int y;
+; };
+;
+; void test_reverse_load2_store2(struct ST2 *A, struct ST2 *B) {
+;   for (int i = 1023; i >= 0; i--) {
+;     int a = A[i].x + i;  // interleaved load of index 0
+;     int b = A[i].y - i;  // interleaved load of index 1
+;     B[i].x = a;          // interleaved store of index 0
+;     B[i].y = b;          // interleaved store of index 1
+;   }
+; }
+
+; CHECK: Interleaved access groups:
+; CHECK: Interleave Group of Delta 2:
+; CHECK-NEXT:   Index 0:
+; CHECK-NEXT:   Index 1:
+; CHECK: Interleave Group of Delta 2:
+; CHECK-NEXT:   Index 0:
+; CHECK-NEXT:   Index 1:
+
+define void @test_reverse_load2_store2(%struct.ST2* nocapture readonly %A, %struct.ST2* nocapture %B) {
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 1023, %entry ], [ %indvars.iv.next, %for.body ]
+  %x = getelementptr inbounds %struct.ST2, %struct.ST2* %A, i64 %indvars.iv, i32 0
+  %0 = load i32, i32* %x, align 4
+  %1 = trunc i64 %indvars.iv to i32
+  %add = add nsw i32 %0, %1
+  %y = getelementptr inbounds %struct.ST2, %struct.ST2* %A, i64 %indvars.iv, i32 1
+  %2 = load i32, i32* %y, align 4
+  %sub = sub nsw i32 %2, %1
+  %x5 = getelementptr inbounds %struct.ST2, %struct.ST2* %B, i64 %indvars.iv, i32 0
+  store i32 %add, i32* %x5, align 4
+  %y8 = getelementptr inbounds %struct.ST2, %struct.ST2* %B, i64 %indvars.iv, i32 1
+  store i32 %sub, i32* %y8, align 4
+  %indvars.iv.next = add nsw i64 %indvars.iv, -1
+  %cmp = icmp sgt i64 %indvars.iv, 0
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+}
+
+; Check an interleaved load group of Delta 2 with 1 gap (without the load on
+; odd element).
+
+; void even_load(int *A, int *B) {
+;  for (unsigned i = 0; i < 1024; i+=2)
+;     B[i/2] = A[i] * 2;
+; }
+
+; CHECK: Interleaved access groups:
+; CHECK: Interleave Group of Delta 2:
+; CHECK-NEXT:   Index 0:
+; CHECK-NOT:    Index 1
+
+define void @even_load(i32* nocapture readonly %A, i32* nocapture %B) {
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %mul = shl nsw i32 %0, 1
+  %1 = lshr exact i64 %indvars.iv, 1
+  %arrayidx2 = getelementptr inbounds i32, i32* %B, i64 %1
+  store i32 %mul, i32* %arrayidx2, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 2
+  %cmp = icmp ult i64 %indvars.iv.next, 1024
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+}
+
+; Check an interleaved store group of Delta 2 with 1 gap. We should not identify
+; such case as a group.
+
+; void even_store(int *A, int *B) {
+;  for (unsigned i = 0; i < 1024; i+=2)
+;    A[i] = B[i] + B[i+1];
+; }
+
+; CHECK: Interleaved access groups:
+; CHECK: Interleave Group of Delta 2:
+; CHECK-NOT:    Index 0:  store
+
+define void @even_store(i32* nocapture %A, i32* nocapture readonly %B) {
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds i32, i32* %B, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %1 = or i64 %indvars.iv, 1
+  %arrayidx2 = getelementptr inbounds i32, i32* %B, i64 %1
+  %2 = load i32, i32* %arrayidx2, align 4
+  %add3 = add nsw i32 %2, %0
+  %arrayidx5 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  store i32 %add3, i32* %arrayidx5, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 2
+  %cmp = icmp ult i64 %indvars.iv.next, 1024
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+}
+
+; Check access groups identified from mixed loads and stores.
+
+; void mixed_load_store(int *A, int *B) {
+;   for (unsigned i = 0; i < 1024; i+=2)  {
+;     B[i] = A[i] * A[i+1];
+;     B[i+1] = A[i] + A[i+1];
+;   }
+; }
+
+; CHECK: Interleaved access groups:
+; CHECK: Interleave Group of Delta 2:
+; CHECK-NEXT:   Index 0:
+; CHECK-NEXT:   Index 1:
+; CHECK: Interleave Group of Delta 2:
+; CHECK-NEXT:   Index 0:
+; CHECK-NEXT:   Index 1:
+; CHECK: Interleave Group of Delta 2:
+; CHECK-NEXT:   Index 0:
+; CHECK-NEXT:   Index 1:
+
+define void @mixed_load_store(i32* nocapture readonly %A, i32* nocapture %B) {
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %1 = or i64 %indvars.iv, 1
+  %arrayidx2 = getelementptr inbounds i32, i32* %A, i64 %1
+  %2 = load i32, i32* %arrayidx2, align 4
+  %mul = mul nsw i32 %2, %0
+  %arrayidx4 = getelementptr inbounds i32, i32* %B, i64 %indvars.iv
+  store i32 %mul, i32* %arrayidx4, align 4
+  %3 = load i32, i32* %arrayidx, align 4
+  %4 = load i32, i32* %arrayidx2, align 4
+  %add10 = add nsw i32 %4, %3
+  %arrayidx13 = getelementptr inbounds i32, i32* %B, i64 %1
+  store i32 %add10, i32* %arrayidx13, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 2
+  %cmp = icmp ult i64 %indvars.iv.next, 1024
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+}
+
+; Check access groups identified from members with different kinds of type.
+
+; struct IntFloat {
+;   int a;
+;   float b;
+; };
+; 
+; int SA;
+; float SB;
+;
+; void int_float_struct(struct IntFloat *A) {
+;   int SumA;
+;   float SumB;
+;   for (unsigned i = 0; i < 1024; i++)  {
+;     SumA += A[i].a;
+;     SumB += A[i].b;
+;   }
+;   SA = SumA;
+;   SB = SumB;
+; }
+
+; CHECK: Interleaved access groups:
+; CHECK: Interleave Group of Delta 2:
+; CHECK-NEXT:   Index 0:
+; CHECK-NEXT:   Index 1:
+
+%struct.IntFloat = type { i32, float }
+
+@SA = common global i32 0, align 4
+@SB = common global float 0.000000e+00, align 4
+
+define void @int_float_struct(%struct.IntFloat* nocapture readonly %A) #0 {
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  store i32 %add, i32* @SA, align 4
+  store float %add3, float* @SB, align 4
+  ret void
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %SumB.014 = phi float [ undef, %entry ], [ %add3, %for.body ]
+  %SumA.013 = phi i32 [ undef, %entry ], [ %add, %for.body ]
+  %a = getelementptr inbounds %struct.IntFloat, %struct.IntFloat* %A, i64 %indvars.iv, i32 0
+  %0 = load i32, i32* %a, align 4
+  %add = add nsw i32 %0, %SumA.013
+  %b = getelementptr inbounds %struct.IntFloat, %struct.IntFloat* %A, i64 %indvars.iv, i32 1
+  %1 = load float, float* %b, align 4
+  %add3 = fadd fast float %SumB.014, %1
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 1024
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+attributes #0 = { "unsafe-fp-math"="true" }
+
+; Check two interleaved store groups which will break write after write
+; dependence. We should not identify them as interleaved groups.
+
+; void waw_dep(int *A) {
+;   char *Tmp = (char *)A;
+;   int *B = (int *) (++Tmp);
+;   for(int i = 0; i < 1024; i+=2) {
+;     A[i]   = i;                // (1)
+;     B[i]   = i;                // (2)
+;     A[i+1] = i + 1;            // (3)
+;     B[i+1] = i + 1;            // (4)
+;   }
+; }
+;
+; The combine of (1)+(3) or (2)+(4) will break the dependence.
+
+; CHECK: Interleaved access groups:
+; CHECK-NOT: Interleave Group:
+
+define void @waw_dep(i32* nocapture %A) {
+entry:
+  %0 = bitcast i32* %A to i8*
+  %incdec.ptr = getelementptr inbounds i8, i8* %0, i64 1
+  %1 = bitcast i8* %incdec.ptr to i32*
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %2 = trunc i64 %indvars.iv to i32
+  store i32 %2, i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i32, i32* %1, i64 %indvars.iv
+  store i32 %2, i32* %arrayidx2, align 4
+  %3 = or i64 %indvars.iv, 1
+  %arrayidx5 = getelementptr inbounds i32, i32* %A, i64 %3
+  %4 = trunc i64 %3 to i32
+  store i32 %4, i32* %arrayidx5, align 4
+  %arrayidx9 = getelementptr inbounds i32, i32* %1, i64 %3
+  store i32 %4, i32* %arrayidx9, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 2
+  %cmp = icmp slt i64 %indvars.iv.next, 1024
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+}
+
+; Check two interleaved store groups which won't break write after write
+; dependence.
+
+; void no_waw_dep(int *A) {
+;   char *Tmp = (char *)A;
+;   int *B = (int *) (++Tmp);
+;   for(int i = 0; i < 1024; i+=2) {
+;     A[i]   = i;                // (1)
+;     A[i+1] = i + 1;            // (2)
+;     B[i]   = i;                // (3)
+;     B[i+1] = i + 1;            // (4)
+;   }
+; }
+;
+; The combine of (1)+(2) or (3)+(4) won't break the dependence.
+
+; CHECK: Interleaved access groups:
+; CHECK: Interleave Group of Delta 2:
+; CHECK-NEXT:   Index 0:  store i32 %2
+; CHECK-NEXT:   Index 1:  store i32 %4
+; CHECK: Interleave Group of Delta 2:
+; CHECK-NEXT:   Index 0:  store i32 %2
+; CHECK-NEXT:   Index 1:  store i32 %4
+
+define void @no_waw_dep(i32* nocapture %A) {
+entry:
+  %0 = bitcast i32* %A to i8*
+  %incdec.ptr = getelementptr inbounds i8, i8* %0, i64 1
+  %1 = bitcast i8* %incdec.ptr to i32*
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %2 = trunc i64 %indvars.iv to i32
+  store i32 %2, i32* %arrayidx, align 4
+  %3 = or i64 %indvars.iv, 1
+  %arrayidx3 = getelementptr inbounds i32, i32* %A, i64 %3
+  %4 = trunc i64 %3 to i32
+  store i32 %4, i32* %arrayidx3, align 4
+  %arrayidx5 = getelementptr inbounds i32, i32* %1, i64 %indvars.iv
+  store i32 %2, i32* %arrayidx5, align 4
+  %arrayidx9 = getelementptr inbounds i32, i32* %1, i64 %3
+  store i32 %4, i32* %arrayidx9, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 2
+  %cmp = icmp slt i64 %indvars.iv.next, 1024
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+}

test/Transforms/LoopVectorize/AArch64/arbitrary-induction-step.ll

-; RUN: opt -S < %s -loop-vectorize 2>&1 | FileCheck %s
-; RUN: opt -S < %s -loop-vectorize -force-vector-interleave=1 -force-vector-width=2 | FileCheck %s --check-prefix=FORCE-VEC
+; RUN: opt -S < %s -loop-vectorize -force-vector-interleave=2 -force-vector-width=4 -enable-interleaving=true | FileCheck %s
+; RUN: opt -S < %s -loop-vectorize -force-vector-interleave=1 -force-vector-width=2 -enable-interleaving=true | FileCheck %s --check-prefix=FORCE-VEC
 
 target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
 target triple = "aarch64--linux-gnueabi"
 
 ; Test integer induction variable of step 2:
 ;   for (int i = 0; i < 1024; i+=2) {
 ;     int tmp = *A++;
 ;     sum += i * tmp;

 ; vectorization is not enforced, LV will only do interleave.
 ;   for (int i = 0; i < 1024; i++) {
 ;     int tmp0 = *A++;
 ;     int tmp1 = *A++;
 ;     sum += tmp0 * tmp1;
 ;   }
 
 ; CHECK-LABEL: @ptr_ind_plus2(
-; CHECK: load i32, i32*
-; CHECK: load i32, i32*
-; CHECK: load i32, i32*
-; CHECK: load i32, i32*
-; CHECK: mul nsw i32
-; CHECK: mul nsw i32
-; CHECK: add nsw i32
-; CHECK: add nsw i32
-; CHECK: %index.next = add i64 %index, 2
-; CHECK: %21 = icmp eq i64 %index.next, 1024
+; CHECK: %[[V0:.*]] = load <8 x i32>
+; CHECK: shufflevector <8 x i32> %[[V0]], <8 x i32> undef, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+; CHECK: shufflevector <8 x i32> %[[V0]], <8 x i32> undef, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
+; CHECK: %[[V1:.*]] = load <8 x i32>
+; CHECK: shufflevector <8 x i32> %[[V1]], <8 x i32> undef, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+; CHECK: shufflevector <8 x i32> %[[V1]], <8 x i32> undef, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
+; CHECK: mul nsw <4 x i32>
+; CHECK: mul nsw <4 x i32>
+; CHECK: add nsw <4 x i32>
+; CHECK: add nsw <4 x i32>
+; CHECK: %index.next = add i64 %index, 8
+; CHECK: icmp eq i64 %index.next, 1024
 
 ; FORCE-VEC-LABEL: @ptr_ind_plus2(
-; FORCE-VEC: load i32, i32*
-; FORCE-VEC: insertelement <2 x i32>
-; FORCE-VEC: load i32, i32*
-; FORCE-VEC: insertelement <2 x i32>
-; FORCE-VEC: load i32, i32*
-; FORCE-VEC: insertelement <2 x i32>
-; FORCE-VEC: load i32, i32*
-; FORCE-VEC: insertelement <2 x i32>
+; FORCE-VEC: %[[V:.*]] = load <4 x i32>
+; FORCE-VEC: shufflevector <4 x i32> %[[V]], <4 x i32> undef, <2 x i32> <i32 0, i32 2>
+; FORCE-VEC: shufflevector <4 x i32> %[[V]], <4 x i32> undef, <2 x i32> <i32 1, i32 3>
 ; FORCE-VEC: mul nsw <2 x i32>
 ; FORCE-VEC: add nsw <2 x i32>
 ; FORCE-VEC: %index.next = add i64 %index, 2
 ; FORCE-VEC: icmp eq i64 %index.next, 1024
 define i32 @ptr_ind_plus2(i32* %A) {
 entry:
   br label %for.body
 

test/Transforms/LoopVectorize/interleaved-accesses.ll

+; RUN: opt -S -loop-vectorize -instcombine -force-vector-width=4 -force-vector-interleave=1 -enable-interleaving=true -runtime-memory-check-threshold=24 < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
+
+; Check vectorization on an interleaved load group of Delta 2 and an interleaved
+; store group of Delta 2.
+
+; int AB[1024];
+; int CD[1024];
+;  void test_array_load2_store2(int C, int D) {
+;   for (int i = 0; i < 1024; i+=2) {
+;     int A = AB[i];
+;     int B = AB[i+1];
+;     CD[i] = A + C;
+;     CD[i+1] = B * D;
+;   }
+; }
+
+; CHECK-LABEL: @test_array_load2_store2(
+; CHECK: %wide.vec = load <8 x i32>, <8 x i32>* %{{.*}}, align 4
+; CHECK: shufflevector <8 x i32> %wide.vec, <8 x i32> undef, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+; CHECK: shufflevector <8 x i32> %wide.vec, <8 x i32> undef, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
+; CHECK: add nsw <4 x i32>
+; CHECK: mul nsw <4 x i32>
+; CHECK: %interleaved.vec = shufflevector <4 x i32> {{.*}}, <8 x i32> <i32 0, i32 4, i32 1, i32 5, i32 2, i32 6, i32 3, i32 7>
+; CHECK: store <8 x i32> %interleaved.vec, <8 x i32>* %{{.*}}, align 4
+
+%struct.ST2 = type { i32, i32 }
+@AB = common global [1024 x i32] zeroinitializer, align 4
+@CD = common global [1024 x i32] zeroinitializer, align 4
+
+define void @test_array_load2_store2(i32 %C, i32 %D) {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx0 = getelementptr inbounds [1024 x i32], [1024 x i32]* @AB, i64 0, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx0, align 4
+  %1 = or i64 %indvars.iv, 1
+  %arrayidx1 = getelementptr inbounds [1024 x i32], [1024 x i32]* @AB, i64 0, i64 %1
+  %2 = load i32, i32* %arrayidx1, align 4
+  %add = add nsw i32 %0, %C
+  %mul = mul nsw i32 %2, %D
+  %arrayidx2 = getelementptr inbounds [1024 x i32], [1024 x i32]* @CD, i64 0, i64 %indvars.iv
+  store i32 %add, i32* %arrayidx2, align 4
+  %arrayidx3 = getelementptr inbounds [1024 x i32], [1024 x i32]* @CD, i64 0, i64 %1
+  store i32 %mul, i32* %arrayidx3, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 2
+  %cmp = icmp slt i64 %indvars.iv.next, 1024
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
+
+; Check vectorization on an interleaved load group of Delta 3 and an interleaved
+; store group of Delta 3.
+
+; int A[3072];
+; struct ST S[1024];
+; void test_struct_st3() {
+;   int *ptr = A;
+;   for (int i = 0; i < 1024; i++) {
+;     int X1 = *ptr++;
+;     int X2 = *ptr++;
+;     int X3 = *ptr++;
+;     T[i].x = X1 + 1;
+;     T[i].y = X2 + 2;
+;     T[i].z = X3 + 3;
+;   }
+; }
+
+; CHECK-LABEL: @test_struct_array_load3_store3(
+; CHECK: %wide.vec = load <12 x i32>, <12 x i32>* {{.*}}, align 4
+; CHECK: shufflevector <12 x i32> %wide.vec, <12 x i32> undef, <4 x i32> <i32 0, i32 3, i32 6, i32 9>
+; CHECK: shufflevector <12 x i32> %wide.vec, <12 x i32> undef, <4 x i32> <i32 1, i32 4, i32 7, i32 10>
+; CHECK: shufflevector <12 x i32> %wide.vec, <12 x i32> undef, <4 x i32> <i32 2, i32 5, i32 8, i32 11>
+; CHECK: add nsw <4 x i32> {{.*}}, <i32 1, i32 1, i32 1, i32 1>
+; CHECK: add nsw <4 x i32> {{.*}}, <i32 2, i32 2, i32 2, i32 2>
+; CHECK: add nsw <4 x i32> {{.*}}, <i32 3, i32 3, i32 3, i32 3>
+; CHECK: shufflevector <4 x i32> {{.*}}, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
+; CHECK: shufflevector <4 x i32> {{.*}}, <4 x i32> undef, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 undef, i32 undef, i32 undef, i32 undef>
+; CHECK: %interleaved.vec = shufflevector <8 x i32> {{.*}}, <12 x i32> <i32 0, i32 4, i32 8, i32 1, i32 5, i32 9, i32 2, i32 6, i32 10, i32 3, i32 7, i32 11>
+; CHECK: store <12 x i32> %interleaved.vec, <12 x i32>* {{.*}}, align 4
+
+%struct.ST3 = type { i32, i32, i32 }
+@A = common global [3072 x i32] zeroinitializer, align 4
+@S = common global [1024 x %struct.ST3] zeroinitializer, align 4
+
+define void @test_struct_array_load3_store3() {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %ptr.016 = phi i32* [ getelementptr inbounds ([3072 x i32], [3072 x i32]* @A, i64 0, i64 0), %entry ], [ %incdec.ptr2, %for.body ]
+  %incdec.ptr = getelementptr inbounds i32, i32* %ptr.016, i64 1
+  %0 = load i32, i32* %ptr.016, align 4
+  %incdec.ptr1 = getelementptr inbounds i32, i32* %ptr.016, i64 2
+  %1 = load i32, i32* %incdec.ptr, align 4
+  %incdec.ptr2 = getelementptr inbounds i32, i32* %ptr.016, i64 3
+  %2 = load i32, i32* %incdec.ptr1, align 4
+  %add = add nsw i32 %0, 1
+  %x = getelementptr inbounds [1024 x %struct.ST3], [1024 x %struct.ST3]* @S, i64 0, i64 %indvars.iv, i32 0
+  store i32 %add, i32* %x, align 4
+  %add3 = add nsw i32 %1, 2
+  %y = getelementptr inbounds [1024 x %struct.ST3], [1024 x %struct.ST3]* @S, i64 0, i64 %indvars.iv, i32 1
+  store i32 %add3, i32* %y, align 4
+  %add6 = add nsw i32 %2, 3
+  %z = getelementptr inbounds [1024 x %struct.ST3], [1024 x %struct.ST3]* @S, i64 0, i64 %indvars.iv, i32 2
+  store i32 %add6, i32* %z, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 1024
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
+
+; Check vectorization on an interleaved load group of Delta 4.
+
+; struct ST4{
+;   int x;
+;   int y;
+;   int z;
+;   int w;
+; };
+; int test_struct_load4(struct ST4 *S) {
+;   int r = 0;
+;   for (int i = 0; i < 1024; i++) {
+;      r += S[i].x;
+;      r -= S[i].y;
+;      r += S[i].z;
+;      r -= S[i].w;
+;   }
+;   return r;
+; }
+
+; CHECK-LABEL: @test_struct_load4(
+; CHECK: %wide.vec = load <16 x i32>, <16 x i32>* {{.*}}, align 4
+; CHECK: shufflevector <16 x i32> %wide.vec, <16 x i32> undef, <4 x i32> <i32 0, i32 4, i32 8, i32 12>
+; CHECK: shufflevector <16 x i32> %wide.vec, <16 x i32> undef, <4 x i32> <i32 1, i32 5, i32 9, i32 13>
+; CHECK: shufflevector <16 x i32> %wide.vec, <16 x i32> undef, <4 x i32> <i32 2, i32 6, i32 10, i32 14>
+; CHECK: shufflevector <16 x i32> %wide.vec, <16 x i32> undef, <4 x i32> <i32 3, i32 7, i32 11, i32 15>
+; CHECK: add nsw <4 x i32>
+; CHECK: sub <4 x i32>
+; CHECK: add nsw <4 x i32>
+; CHECK: sub <4 x i32>
+
+%struct.ST4 = type { i32, i32, i32, i32 }
+
+define i32 @test_struct_load4(%struct.ST4* nocapture readonly %S) {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %r.022 = phi i32 [ 0, %entry ], [ %sub8, %for.body ]
+  %x = getelementptr inbounds %struct.ST4, %struct.ST4* %S, i64 %indvars.iv, i32 0
+  %0 = load i32, i32* %x, align 4
+  %add = add nsw i32 %0, %r.022
+  %y = getelementptr inbounds %struct.ST4, %struct.ST4* %S, i64 %indvars.iv, i32 1
+  %1 = load i32, i32* %y, align 4
+  %sub = sub i32 %add, %1
+  %z = getelementptr inbounds %struct.ST4, %struct.ST4* %S, i64 %indvars.iv, i32 2
+  %2 = load i32, i32* %z, align 4
+  %add5 = add nsw i32 %sub, %2
+  %w = getelementptr inbounds %struct.ST4, %struct.ST4* %S, i64 %indvars.iv, i32 3
+  %3 = load i32, i32* %w, align 4
+  %sub8 = sub i32 %add5, %3
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 1024
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret i32 %sub8
+}
+
+; Check vectorization on an interleaved store group of Delta 4.
+
+; int B[1024];
+; struct ST T[1024];
+; void test_struct_store4() {
+;   int *ptr = B;
+;   for (int i = 0; i < 1024; i++) {
+;     int X = *ptr++;
+;     T[i].x = X + 1;
+;     T[i].y = X * 2;
+;     T[i].z = X + 3;
+;     T[i].w = X + 4;
+;   }
+; }
+
+; CHECK-LABEL: @test_struct_store4(
+; CHECK: %[[LD:.*]] = load <4 x i32>, <4 x i32>* 
+; CHECK: add nsw <4 x i32> %[[LD]], <i32 1, i32 1, i32 1, i32 1>
+; CHECK: shl nsw <4 x i32> %[[LD]], <i32 1, i32 1, i32 1, i32 1>
+; CHECK: add nsw <4 x i32> %[[LD]], <i32 3, i32 3, i32 3, i32 3>
+; CHECK: add nsw <4 x i32> %[[LD]], <i32 4, i32 4, i32 4, i32 4>
+; CHECK: shufflevector <4 x i32> {{.*}}, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
+; CHECK: shufflevector <4 x i32> {{.*}}, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
+; CHECK: %interleaved.vec = shufflevector <8 x i32> {{.*}}, <16 x i32> <i32 0, i32 4, i32 8, i32 12, i32 1, i32 5, i32 9, i32 13, i32 2, i32 6, i32 10, i32 14, i32 3, i32 7, i32 11, i32 15>
+; CHECK: store <16 x i32> %interleaved.vec, <16 x i32>* {{.*}}, align 4
+
+@B = common global [1024 x i32] zeroinitializer, align 4
+@T = common global [1024 x %struct.ST4] zeroinitializer, align 4
+
+define void @test_struct_store4() {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %ptr.017 = phi i32* [ getelementptr inbounds ([1024 x i32], [1024 x i32]* @B, i64 0, i64 0), %entry ], [ %incdec.ptr, %for.body ]
+  %incdec.ptr = getelementptr inbounds i32, i32* %ptr.017, i64 1
+  %0 = load i32, i32* %ptr.017, align 4
+  %add = add nsw i32 %0, 1
+  %x = getelementptr inbounds [1024 x %struct.ST4], [1024 x %struct.ST4]* @T, i64 0, i64 %indvars.iv, i32 0
+  store i32 %add, i32* %x, align 4
+  %mul = shl nsw i32 %0, 1
+  %y = getelementptr inbounds [1024 x %struct.ST4], [1024 x %struct.ST4]* @T, i64 0, i64 %indvars.iv, i32 1
+  store i32 %mul, i32* %y, align 4
+  %sub = add nsw i32 %0, 3
+  %z = getelementptr inbounds [1024 x %struct.ST4], [1024 x %struct.ST4]* @T, i64 0, i64 %indvars.iv, i32 2
+  store i32 %sub, i32* %z, align 4
+  %add5 = add nsw i32 %0, 4
+  %w = getelementptr inbounds [1024 x %struct.ST4], [1024 x %struct.ST4]* @T, i64 0, i64 %indvars.iv, i32 3
+  store i32 %add5, i32* %w, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 1024
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
+
+; Check vectorization on a reverse interleaved load group of Delta 2 and
+; a reverse interleaved store group of Delta 2.
+
+; struct ST2 {
+;  int x;
+;  int y;
+; };
+;
+; void test_reversed_load2_store2(struct ST2 *A, struct ST2 *B) {
+;   for (int i = 1023; i >= 0; i--) {
+;     int a = A[i].x + i;  // interleaved load of index 0
+;     int b = A[i].y - i;  // interleaved load of index 1
+;     B[i].x = a;          // interleaved store of index 0
+;     B[i].y = b;          // interleaved store of index 1
+;   }
+; }
+
+; CHECK-LABEL: @test_reversed_load2_store2(
+; CHECK: %wide.vec = load <8 x i32>, <8 x i32>* {{.*}}, align 4
+; CHECK: shufflevector <8 x i32> %wide.vec, <8 x i32> undef, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+; CHECK: shufflevector <4 x i32> {{.*}}, <4 x i32> <i32 3, i32 2, i32 1, i32 0>
+; CHECK: shufflevector <8 x i32> %wide.vec, <8 x i32> undef, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
+; CHECK: shufflevector <4 x i32> {{.*}}, <4 x i32> <i32 3, i32 2, i32 1, i32 0>
+; CHECK: add nsw <4 x i32>
+; CHECK: sub nsw <4 x i32>
+; CHECK: shufflevector <4 x i32> {{.*}}, <4 x i32> <i32 3, i32 2, i32 1, i32 0>
+; CHECK: shufflevector <4 x i32> {{.*}}, <4 x i32> <i32 3, i32 2, i32 1, i32 0>
+; CHECK: %interleaved.vec = shufflevector <4 x i32> {{.*}}, <8 x i32> <i32 0, i32 4, i32 1, i32 5, i32 2, i32 6, i32 3, i32 7>
+; CHECK: store <8 x i32> %interleaved.vec, <8 x i32>* %{{.*}}, align 4
+
+define void @test_reversed_load2_store2(%struct.ST2* nocapture readonly %A, %struct.ST2* nocapture %B) {
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 1023, %entry ], [ %indvars.iv.next, %for.body ]
+  %x = getelementptr inbounds %struct.ST2, %struct.ST2* %A, i64 %indvars.iv, i32 0
+  %0 = load i32, i32* %x, align 4
+  %1 = trunc i64 %indvars.iv to i32
+  %add = add nsw i32 %0, %1
+  %y = getelementptr inbounds %struct.ST2, %struct.ST2* %A, i64 %indvars.iv, i32 1
+  %2 = load i32, i32* %y, align 4
+  %sub = sub nsw i32 %2, %1
+  %x5 = getelementptr inbounds %struct.ST2, %struct.ST2* %B, i64 %indvars.iv, i32 0
+  store i32 %add, i32* %x5, align 4
+  %y8 = getelementptr inbounds %struct.ST2, %struct.ST2* %B, i64 %indvars.iv, i32 1
+  store i32 %sub, i32* %y8, align 4
+  %indvars.iv.next = add nsw i64 %indvars.iv, -1
+  %cmp = icmp sgt i64 %indvars.iv, 0
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+}
+
+; Check vectorization on an interleaved load group of Delta 2 with 1 gap
+; (missing the load of odd elements).
+
+; void even_load(int *A, int *B) {
+;  for (unsigned i = 0; i < 1024; i+=2)
+;     B[i/2] = A[i] * 2;
+; }
+
+; CHECK-LABEL: @even_load(
+; CHECK: %wide.vec = load <8 x i32>, <8 x i32>* %{{.*}}, align 4
+; CHECK: %strided.vec = shufflevector <8 x i32> %wide.vec, <8 x i32> undef, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+; CHECK-NOT: shufflevector <8 x i32> %wide.vec, <8 x i32> undef, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
+; CHECK: shl nsw <4 x i32> %strided.vec, <i32 1, i32 1, i32 1, i32 1>
+define void @even_load(i32* nocapture readonly %A, i32* nocapture %B) {
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %mul = shl nsw i32 %0, 1
+  %1 = lshr exact i64 %indvars.iv, 1
+  %arrayidx2 = getelementptr inbounds i32, i32* %B, i64 %1
+  store i32 %mul, i32* %arrayidx2, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 2
+  %cmp = icmp ult i64 %indvars.iv.next, 1024
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+}
+
+; Check vectorization on interleaved access groups identified from mixed
+; loads/stores.
+; void mixed_load_store(int *A, int *B) {
+;   for (unsigned i = 0; i < 1024; i+=2)  {
+;     B[i] = A[i] * A[i+1];
+;     B[i+1] = A[i] + A[i+1];
+;   }
+; }
+
+; CHECK-LABEL: @mixed_load_store(
+; CHECK: %wide.vec = load <8 x i32>, <8 x i32>* {{.*}}, align 4
+; CHECK: shufflevector <8 x i32> %wide.vec, <8 x i32> undef, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+; CHECK: shufflevector <8 x i32> %wide.vec, <8 x i32> undef, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
+; CHECK: %interleaved.vec = shufflevector <4 x i32> %{{.*}}, <8 x i32> <i32 0, i32 4, i32 1, i32 5, i32 2, i32 6, i32 3, i32 7>
+; CHECK: store <8 x i32> %interleaved.vec
+define void @mixed_load_store(i32* nocapture readonly %A, i32* nocapture %B) #0 {
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %1 = or i64 %indvars.iv, 1
+  %arrayidx2 = getelementptr inbounds i32, i32* %A, i64 %1
+  %2 = load i32, i32* %arrayidx2, align 4
+  %mul = mul nsw i32 %2, %0
+  %arrayidx4 = getelementptr inbounds i32, i32* %B, i64 %indvars.iv
+  store i32 %mul, i32* %arrayidx4, align 4
+  %3 = load i32, i32* %arrayidx, align 4
+  %4 = load i32, i32* %arrayidx2, align 4
+  %add10 = add nsw i32 %4, %3
+  %arrayidx13 = getelementptr inbounds i32, i32* %B, i64 %1
+  store i32 %add10, i32* %arrayidx13, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 2
+  %cmp = icmp ult i64 %indvars.iv.next, 1024
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+}
+
+; Check vectorization on interleaved access groups with members having different
+; kinds of type.
+
+; struct IntFloat {
+;   int a;
+;   float b;
+; };
+; 
+; int SA;
+; float SB;
+;
+; void int_float_struct(struct IntFloat *A) {
+;   int SumA;
+;   float SumB;
+;   for (unsigned i = 0; i < 1024; i++)  {
+;     SumA += A[i].a;
+;     SumB += A[i].b;
+;   }
+;   SA = SumA;
+;   SB = SumB;
+; }
+
+; CHECK-LABEL: @int_float_struct(
+; CHECK: %wide.vec = load <8 x i32>, <8 x i32>* %{{.*}}, align 4
+; CHECK: %[[V0:.*]] = shufflevector <8 x i32> %wide.vec, <8 x i32> undef, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+; CHECK: %[[V1:.*]] = shufflevector <8 x i32> %wide.vec, <8 x i32> undef, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
+; CHECK: bitcast <4 x i32> %[[V1]] to <4 x float>
+; CHECK: add nsw <4 x i32>
+; CHECK: fadd fast <4 x float>
+
+%struct.IntFloat = type { i32, float }
+
+@SA = common global i32 0, align 4
+@SB = common global float 0.000000e+00, align 4
+
+define void @int_float_struct(%struct.IntFloat* nocapture readonly %A) #0 {
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  store i32 %add, i32* @SA, align 4
+  store float %add3, float* @SB, align 4
+  ret void
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %SumB.014 = phi float [ undef, %entry ], [ %add3, %for.body ]
+  %SumA.013 = phi i32 [ undef, %entry ], [ %add, %for.body ]
+  %a = getelementptr inbounds %struct.IntFloat, %struct.IntFloat* %A, i64 %indvars.iv, i32 0
+  %0 = load i32, i32* %a, align 4
+  %add = add nsw i32 %0, %SumA.013
+  %b = getelementptr inbounds %struct.IntFloat, %struct.IntFloat* %A, i64 %indvars.iv, i32 1
+  %1 = load float, float* %b, align 4
+  %add3 = fadd fast float %SumB.014, %1
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 1024
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+attributes #0 = { "unsafe-fp-math"="true" }