[LV] Preserve order of dependences in interleaved accesses analysis

[mssimpso]

Summary

The interleaved access analysis currently assumes that the inserted run-time pointer aliasing checks ensure the absence of dependences that would prevent its instruction reordering. However, this is not the case.

Issues can arise from how code generation is performed for interleaved groups. For a load group, all loads in the group are essentially moved to the location of the first load in program order, and for a store group, all stores in the group are moved to the location of the last store. For groups having members involved in a dependence relation with any other instruction in the loop, this reordering can violate the dependence.

This patch teaches the interleaved access analysis how to avoid breaking such dependences, and should fix PR27626.

An assumption of the original analysis was that the accesses had been collected in "program order". The analysis was then simplified by visiting the accesses bottom-up. However, this ordering was never guaranteed for anything other than single basic block loops. Thus, this patch also enforces the desired ordering.

[sbaranga]

I think non-zero dependences would have already been rejected by LAA. Would this this be the reason why it is correct to only look at the zero distance ones?

Thanks,
Silviu

lib/Transforms/Vectorize/LoopVectorize.cpp

932

I guess we can check this with DT because the loads/stores are not predicated? (same in a bunch of other places).

5159

Wouldn't we need to add B to LoopIndependentRAWStores even if we add it to StoresToRemove?

5177

This sentence seems to be unfinished?

[mssimpso]

Hi Silviu, thanks for the comments.

I think non-zero dependences would have already been rejected by LAA. Would this this be the reason why it is correct to only look at the zero distance ones?

Yes, that should be the case!

lib/Transforms/Vectorize/LoopVectorize.cpp

932

I intended the dominance check to work for the predicated accesses as well. The check says that if the read does not dominate the write, then we have to conservatively assume the write may happen first, leading to a read-after-write dependence.

5159

StoresToRemove holds stores whose groups will definitely be removed. LoopIndependentRAWStores holds stores that we don't yet have enough information about to determine if they need to be removed or not.

In this case, if the current store (B) is already in a group, it means that it will be re-ordered by sinking it to the insert location of the group, violating the dependence. If it's not yet in a group (and thus, won't be re-ordered), we don't yet know that the load (A) won't be hoisted, which would also violate the dependence. Once we know that another load has been added to A's group, we know that A will be re-ordered. When this happens, we move all the stores in LoopIndependentRAWStores to StoresToRemove, to mark them for definite removal.

5177

Thanks for catching that. I'll submit an update

[mssimpso]

Updated comments.

[sbaranga]

Overall I think this looks good, but it would be better if someone else would also have a look before committing.

Thanks,
Silviu

lib/Transforms/Vectorize/LoopVectorize.cpp

932

OK, this makes sense.

[mssimpso]

Thanks very much Silviu! I'll wait for Adam or Hal to provide additional feedback.

[anemet]

In D19984#424731, @mssimpso wrote:

Hi Silviu, thanks for the comments.

I think non-zero dependences would have already been rejected by LAA. Would this this be the reason why it is correct to only look at the zero distance ones?

Yes, that should be the case!

Why are non-zero forward deps rejected by LAA? Because of the HW store-to-load forwarding case? I think that that is only a performance consideration and it's only on conditionally.

I think that we should probably take the time and review the soundness of these code motions with respect to interleaved access vectorization {RAW, WAR, WAW} x {loop-independent, loop-carried}. I've only looked at the LAA aspects of this feature so far but I am a bit worried about this code now.

Matt, do you think you can do this?

I am also thinking if we should disable this feature in the meantime?!

[mssimpso]

Hi Adam,

Why are non-zero forward deps rejected by LAA? Because of the HW store-to-load forwarding case? I think that that is only a performance consideration and it's only on conditionally.

Siviu was referring to a comment I had made in the source. But I think the idea was that LAA had already ensured the absence of the dependences that would have prevented vectorization. So the interleaved access analysis didn't need to worry about them. Regarding the store-to-load forwarding case, yes, that is the assumption the original analysis made, which was incorrect. The current patch attempts to fix that.

I think that we should probably take the time and review the soundness of these code motions with respect to interleaved access vectorization {RAW, WAR, WAW} x {loop-independent, loop-carried}. I've only looked at the LAA aspects of this feature so far but I am a bit worried about this code now.

Matt, do you think you can do this?

I'm happy to give the analysis a very careful second look. I'll do that today and report back.

I am also thinking if we should disable this feature in the meantime?!

We should definitely disable interleaved access vectorization if we can't correct the bug (PR27626) before release time. Doing so would have performance implications for ARM/AArch64, so I'm hoping we can fix it before then. I wouldn't be strongly opposed to disabling it in the meantime. But to my knowledge, the bug isn't currently blocking anyone, and it's been around since the original implementation. Silviu and I only discovered it in passing, and it wasn't something we encountered in the wild. What do you think?

[sbaranga]

Just to expand on the point above:

From the algorithm of constructing interleaved groups, we should be able to exclude both WAW (from the algorithm, see the comments) and WAR (we're interleaving and then moving stores down and loads up, so we cannot break these) - for both loop-carried and loop independent dependences.

So the problem should only be RAW. If it is loop carried, then it is a forward dependence and we cannot vectorize, so this should be safe.
And this should handle the loop independent case.

Also we've probably not seen this until now because other optimizations would simply remove the load before this got to the vectorizer?

Cheers,
Silviu

[anemet]

In D19984#428293, @mssimpso wrote:

Hi Adam,

Why are non-zero forward deps rejected by LAA? Because of the HW store-to-load forwarding case? I think that that is only a performance consideration and it's only on conditionally.

Siviu was referring to a comment I had made in the source. But I think the idea was that LAA had already ensured the absence of the dependences that would have prevented vectorization. So the interleaved access analysis didn't need to worry about them. Regarding the store-to-load forwarding case, yes, that is the assumption the original analysis made, which was incorrect. The current patch attempts to fix that.

No, I was asking about *non-zero* distance deps specifically. The current patch only handles zero-distance deps. So my question was whether for non-zero distance we still rely on the store-to-load forwarding detection code to make the dep unsafe for vectorization.

[anemet]

Hi Silviu,

In D19984#428379, @sbaranga wrote:

Just to expand on the point above:

From the algorithm of constructing interleaved groups, we should be able to exclude both WAW (from the algorithm, see the comments) and WAR (we're interleaving and then moving stores down and loads up, so we cannot break these) - for both loop-carried and loop independent dependences.

What about moving elements of an interleaved group over other dependent accesses not in the same group?

Adam

test/Transforms/LoopVectorize/interleaved-accesses.ll

574–579

You mean p[i].x etc in the loop.

[mssimpso]

Hi Guys,

I've been thinking through these dependence issues more carefully. I'm not yet finished with all the permutations, but I've come across another somewhat unrelated issue. I thought I would post an update about that and respond to some of Adam's questions in the meantime. First the questions:

No, I was asking about *non-zero* distance deps specifically. The current patch only handles zero-distance deps. So my question was whether for non-zero distance we still rely on the store-to-load forwarding detection code to make the dep unsafe for vectorization.

For positive dependences, LAA prevents vectorization if the distance is less than some minimum (which determines the maximum safe VF). For positive dependences between strided accesses, LAA tries to prove independence (the accesses are independent if the distance is not a multiple of the stride). Non-positive dependences are allowed, and LAA checks for store-to-load forwarding conflicts for RAWs. The original analysis assumed the store-to-load detection would guarantee the absence of all RAWs, which was incorrect. So we need to consider the non-positive RAWs (as Silviu said, we should be able to exclude the WAR and WAW cases).

What about moving elements of an interleaved group over other dependent accesses not in the same group?

This would be the RAW case. For example, S1-L2 is a RAW dependence, L1-L2 form a group:

L1: load
S1: store
L2: load  // L2 would be hoisted above S1.

Or alternatively, S1-L1 is a RAW dependence, S1-S2 form a group:

S1: store // S1 would be sunk below L1.
L1: load
S2: store

The other issue I've uncovered is related to the maximum safe VF. We set this based on the positive dependence distance LAA computes. But for the interleaved accesses, the actual VF used during vectorization is VF * IF, where IF is the interleave factor. The idea is that each component of the wide vector would have VF elements after they are shuffled out. However, this could be greater than the maximum safe VF. Here's an example.

; for (int i = 1; i < 1000; ++i) {
;   p[i + 2].x = p[i].x;
;   p[i + 2].y = p[i].y;
; }
%struct.pair = type { i32, i32 }
for.body:
  %indvars.iv = phi i64 [ 1, %entry ], [ %indvars.iv.next, %for.body ]
  %x1 = getelementptr inbounds %struct.pair, %struct.pair* %p, i64 %indvars.iv, i32 0
  %0 = load i32, i32* %x1, align 4
  %1 = add nuw nsw i64 %indvars.iv, 2
  %x4 = getelementptr inbounds %struct.pair, %struct.pair* %p, i64 %1, i32 0
  store i32 %0, i32* %x4, align 4
  %y = getelementptr inbounds %struct.pair, %struct.pair* %p, i64 %indvars.iv, i32 1
  %2 = load i32, i32* %y, align 4
  %y10 = getelementptr inbounds %struct.pair, %struct.pair* %p, i64 %1, i32 1
  store i32 %2, i32* %y10, align 4
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %exitcond = icmp eq i64 %indvars.iv.next, 1000
  br i1 %exitcond, label %for.cond.cleanup, label %for.body
}

We currently generate <8 x i32> loads and stores, but the maximum safe dependence distance is only 16 bytes, so I think we are generating incorrect code here. I think we should probably check for interleaved accesses when selecting the VF.

test/Transforms/LoopVectorize/interleaved-accesses.ll

574–579

Yes, thanks for catching that!

[mssimpso]

I submitted D20241 to correct the issue with the vectorization factor mentioned above.

[sbaranga]

Matt: thanks for doing this analysis!

What about moving elements of an interleaved group over other dependent accesses not in the same group?

Adam

We shouldn't be doing that. We should be preserving dependences, and as long as we do that this should be correct.

It does look like things are more complicated then what I previously stated, at least with regard to RAW. And we do need to consider non-zero distance dependences (because we are essentially moving this loads/stores after interleaving). Here is an example:

for (...) {

a[i].a = a[i + 2].a + 1
tmp = a[i - 1].a * 2
a[i].b = tmp
a[i].c = tmp
a[i].d = tmp

}

The problem here is that by moving the store to a[i].a we're breaking the loop-carried dependence from a[i].a to a[i-1].a (which doesn't stop vectorization).

Cheers,
Silviu

[mssimpso]

I agree, Silviu. That's basically what I've been thinking. I'm working on an updated patch. Thanks for all the feedback!

[mssimpso]

Updated the analysis according to feedback from Adam and Silviu.

Sorry for the delay in getting a new version of this patch ready. This update is notably different from the previous version in the following ways: (1) We collect all memory accesses in collectConstStrideAccesses instead of only the stride-greater-than-one accesses. We have to collect all accesses to check for dependences between interleaved and non-interleaved accesses. The non-strided accesses are ignored when actually creating the groups. (2) We only ignore the WAR case. I think the code generation strategy can only ensure we won't violate write-after-reads. Everything else is checked. (3) For strided accesses, we try and prove independence like is done in LAA. All other constant-distance accesses are considered dependent, and we preserve their order. The dependences are checked in canReorderMemAccs. (4) I've added another test case, and updated existing comments about the algorithm.

[sbaranga]

I have just a few quick remarks (and most of them were inherited from the existing code).

Cheers,
Silviu

lib/Transforms/Vectorize/LoopVectorize.cpp

5061

We should improve this at some point to check for NoDep (which is what we're really looking for here) and is implied by this test.

5067

This makes assumptions on how LAA works. It might be technically true at the moment, but if the dependence analysis would be improved it would possibly invalidate this.

I think the case where we memcheck each pointer is an edge case? I'm not sure it's worth doing the interleaved access vectorization in this case.

The more common case could be if two pointers are in different alias sets or have different underlying objects? But that should be expressed as a NoDep.

5083

Same here. Ideally we would know we have NoDep from LAA.

Some of the checks here seem to be specifically related to forming the interleaved groups, and less about reordering accesses.

[mssimpso]

Hi Silviu,

It sounds like you're suggesting that we should just query LAA to determine if any dependence exists between the two candidate instructions, and if so, prevent reordering. Does that sound right?

lib/Transforms/Vectorize/LoopVectorize.cpp

5083

If you're referring to the type and factor checks, those are required before we can call areStridedAccessesIndependent.

[mssimpso]

Addressed Silviu's comments.

Hi Silviu,

I've updated the patch to use LAA for checking for the presence of dependences like you suggested. This is actually much simpler. Thanks! I had to make one change to LAA: We now try to prove strided accesses independent before handling the negative distance cases.

Matt.

[anemet]

In D19984#433539, @mssimpso wrote:

I had to make one change to LAA: We now try to prove strided accesses independent before handling the negative distance cases.

Yes, I've seen this recently too. Can you please split this out (and commit) with an appropriate LAA testcase.

[sbaranga]

Thanks for making the changes. I think this looks much better.

Cheers,
Silviu

lib/Transforms/Vectorize/LoopVectorize.cpp

5062

We should be able to do this faster than O(n) - maybe with some pre-processing of dependences.

[mssimpso]

In D19984#433930, @anemet wrote:

Yes, I've seen this recently too. Can you please split this out (and commit) with an appropriate LAA testcase.

Sure. I committed the LAA portion in rL270072. I'll post a rebased version of this patch and address Silviu's latest comments.

[anemet]

I am not done reviewing this but I just want to say that I am having a much better feeling about this analysis after your changes. As I said I had major issues with its soundness. Thanks for your patience for working through all this!

I am also sending my initial comments but there may be more coming.

lib/Transforms/Vectorize/LoopVectorize.cpp

922–924

Somewhere this should state the criteria for reordering. In theory you can reorder backward dependences but looks like you don't allow any (which is fine).

5042

I am wondering if it's time to change the name of this. After your change it no longer contains only "interesting" strided accesses. How about like AccessStrideInfo?

5046

I think that we've been using Accesses pretty consistently without any abbreviation.

5077–5079

I would drop the part about memchecks. This is already pretty long and that part is trivial.

[mssimpso]

Addressed comments from Silviu and Adam.

Thanks very much for all the feedback! I agree, this is definitely looking better. In this update, I pre-process the dependences to enable constant-time queries like Silviu suggested, and I address Adam's latest comments.

lib/Transforms/Vectorize/LoopVectorize.cpp

5042

Sounds good to me. I'll rename StridedAccesses prior to committing the current patch.

[anemet]

lib/Transforms/Vectorize/LoopVectorize.cpp

5124–5128

Here I think we're validating the correctness of:

1. Potentially moving 'A' an interleaved load before any store 'B' or
2. Potentially moving 'B' an interleaved store after any load/store 'A'.

If I am right, I don't think either the comment or the code is tight enough to reflect this.

It would also be good to add testcases for this.

It would be also great to add a testcase to the earlier problem that only candidate accesses were dependency-checked.

What do you think?

[mssimpso]

lib/Transforms/Vectorize/LoopVectorize.cpp

5124–5128

Adam,

I think you're mostly right in the description of what we're validating the correctness of. When you have a chance, would you mind elaborating a bit more as to why you think we're not satisfying both of the cases you mention? The algorithm works bottom-up, so B will always precede A in program order, and we always investigate B's that are closest to A first (some dependences do temporarily slip by but are later checked, see below). Also note that we don't yet handle loops with predicated blocks. I'm working on that in D19694.

For case (1) the bottom-up ordering implies that if we can move a load A before a store B, we know that we can also move A before any store that B precedes. Case (2) is a bit more subtle and is probalby confusing. Say we have the case below:

S1: Store  // depends on L1
L1: Load   // depends on S1
S2: Store

When A is S2 and B is S1, we might say that these are independent, and S1 could be sunk to S2's location. We will add S1 to S2's group. But when A is L1 and B is S1, we will notice the dependence. When we do, we check to see if S1 is already in a group, and if so, invalidate it. This prevents us from moving S1.

Please let me know if I'm still missing something here. We could probably improve the comment and/or rename "canReorderMemAccesses", since this doesn't quite capture what's happening with the instruction ordering.

And yes, we can definitely add more tests.

[anemet]

lib/Transforms/Vectorize/LoopVectorize.cpp

5124–5128

I think you're mostly right in the description of what we're validating the correctness of. When you have a chance, would you mind elaborating a bit more as to why you think we're not satisfying both of the cases you mention?

I said "not tight enough" not that it's incorrect, sorry if that was unclear.

I think I would like to include the above two cases in the comment (or an improved version) and then have the checks in the code reflect that. I.e. right now we don't check that at least one of 'A' or 'B' is interleaved.

The algorithm works bottom-up, so B will always precede A in program order, and we always investigate B's that are closest to A first (some dependences do temporarily slip by but are later checked, see below). Also note that we don't yet handle loops with predicated blocks. I'm working on that in D19694.

For case (1) the bottom-up ordering implies that if we can move a load A before a store B, we know that we can also move A before any store that B precedes. Case (2) is a bit more subtle and is probalby confusing. Say we have the case below:

S1: Store depends on L1
L1: Load depends on S1
S2: Store
When A is S2 and B is S1, we might say that these are independent, and S1 could be sunk to S2's location. We will add S1 to S2's group. But when A is L1 and B is S1, we will notice the dependence. When we do, we check to see if S1 is already in a group, and if so, invalidate it. This prevents us from moving S1.

Make sense.

I am wondering now if there is a simpler way to formulate this analysis with the same result. Aren't we simply saying that we don't consider an interleaved access for merging if it's either a source or the destination of a dependence? I.e. something like this in the outer loop:

if (isDepSource(A) && A->mayWriteToMemory() || isDepDestination(A))
  break:

and then no need for the inner loop?

Please let me know if I'm still missing something here. We could probably improve the comment and/or rename "canReorderMemAccesses", since this doesn't quite capture what's happening with the instruction ordering.

And yes, we can definitely add more tests.

Thanks!

[mssimpso]

lib/Transforms/Vectorize/LoopVectorize.cpp

5124–5128

I think I would like to include the above two cases in the comment (or an improved version) and then have the checks in the code reflect that. I.e. right now we don't check that at least one of 'A' or 'B' is interleaved.

I see, yes this makes sense.

I am wondering now if there is a simpler way to formulate this analysis with the same result. Aren't we simply saying that we don't consider an interleaved access for merging if it's either a source or the destination of a dependence?

This sounds right to me. Let me think it over before posting another update. Thanks again for all the feedback, Adam!

[mssimpso]

Addressed Adam's latest round of comments.

Adam,

I've updated the comments and code to be more precise as you suggested. I've also added a couple of new test cases so that we are checking the conditions you enumerated in your last review. I'll reply to your other points inline. Thanks!

Matt.

[mssimpso]

lib/Transforms/Vectorize/LoopVectorize.cpp

5124–5128

It would be also great to add a testcase to the earlier problem that only candidate accesses were dependency-checked.

I've tried constructing a testcase that would generate incorrect code for this, but I think the current limitations of LAA might actually make this unrealizable at the moment. After the memory checks, two access can be dependent only at constant distances. Thus, if one access is strided, a dependent access at a constant distance would have to be strided as well.

This sounds right to me. Let me think it over before posting another update.

After thinking about this more carefully, I think we will miss cases with a simplification like the one you suggested. For example, if we have a set of interleaved loads followed by a set of interleaved stores that access the same location (or vice versa), giving up in the outer loop would prevent the two groups from being created.

[sbaranga]

This looks sensible to me. LGTM! (you should wait for further comments from Adam before committing)

Cheers,
Silviu

[anemet]

Hi Matt,

Sorry about the delay. As I said in my earlier heads-up I was on vacation.

My main comment is the reply to your testcase remark. The other ones are just nitpicks but I haven't finished going through the patch. I am just curious what you think about the idea regarding the testcase.

Adam

lib/Transforms/Vectorize/LoopVectorize.cpp

933–934

Both A and B are not necessarily strided here.

950–951

This requirement is part of the API so it should be in the function comment. Also a nit, can you please flip the order. I think that A preceding B is the more intuitive. Let me know if you disagree.

5124–5128

I've tried constructing a testcase that would generate incorrect code for this, but I think the current limitations of LAA might actually make this unrealizable at the moment. After the memory checks, two access can be dependent only at constant distances. Thus, if one access is strided, a dependent access at a constant distance would have to be strided as well.

Can't we use larger than stride offsets/indices to emulate non-interleaved accesses? I believe that these are currently ignored by interleaved analysis. I mean something like:

for (i = 0; i < n; i+=3) {
   ... = A[i]
   A[i+4] = ...
   ... = A[i+1]
}

And then A[i+1] shouldn't be moved across A[i+4]

I haven't tried this, it's just an idea....

[mssimpso]

Adam,

Welcome back! Thanks for following up. I replied to your comments inline.

Matt.

lib/Transforms/Vectorize/LoopVectorize.cpp

933–934

True. I will rename this and update the comments.

950–951

Sounds good.

5124–5128

This was my first thought as well. In this case, A[i+4] is still a stride-greater-than-one access, so it would've been collected in SrideAccesses and sent through the original analysis. If its stride is equal to anything other than that of the other accesses (e.g, one or some value greater than MaxInterleaveGroupFactor), the distance between it and the other accesses will be non-constant (some SCEV expression). If the distance isn't constant LAA will report Dependence::Unknown, and we will create the memory checks.

[mssimpso]

Addressed Adam's comments.

[anemet]

lib/Transforms/Vectorize/LoopVectorize.cpp

5124–5128

Matt, I am not sure I follow, which of these accesses is not constant distance in my example?

I just tried this example:

void
f(char *a, char * __restrict c, int n) {
  for (int i = 0; i < n; i+=3) {
    c[i] = a[i];
    a[i+4] = c[i+4];
    c[i+1] = a[i+1];
  }
}

If you compile this on x86_64 with:

-O3 -mllvm -enable-load-pre=0 -mllvm -store-to-load-forwarding-conflict-detection=0 -mllvm -enable-interleaved-mem-accesses -mllvm -force-vector-width=2

Then the loads from 'a' will be merged which breaks the forward dependence between the store of a[i+4] and the load of a[i+1].

No?

[mssimpso]

lib/Transforms/Vectorize/LoopVectorize.cpp

5124–5128

Adam,

We may be talking past each other a bit. I think your original request (correct me if I'm wrong) was for a test case showing that the existing analysis doesn't consider checking memory accesses that are not "candidates" for interleaved groups. Candidate accesses are the ones collected in StrideAccesses prior to the analysis. However, every access in your example actually is a candidate access because they are all strided. They are not ignored. Yes, we currently do the wrong thing here, but that's because the current analysis isn't correctly checking dependences between the actual candidate accesses, not because it isn't considering a dependence between a candidate access and a non-candidate access.

Are you asking for something different?

[anemet]

lib/Transforms/Vectorize/LoopVectorize.cpp

5124–5128

Ah, the disconnect was that I didn't realize that accesses with offsets larger than the stride were considered as candidates. The idea was to have these mimic non-strided accesses.

I guess it makes sense to consider these candidates as well because the offset is not really an offset but rather the distance between two accesses.

So I guess we can't have a testcase for this case at the moment...

I'll continue reviewing the patch.

[anemet]

This is very close I just want to take extra care to update/improve the comments while this is all fresh in our memory.

lib/Transforms/Vectorize/LoopVectorize.cpp

933–934

Actually sorry, let's make this even more precise. At this point the function is called with *any* accesses. (The function later checks that if both accesses are non-strided we don't bother checking deps since we would never reorder those.)

937

We should probably have some qualification in the name, something like canReorderAccessesForInterleavedGroups or something like that. This is not a general canReorder predicate but takes into consideration the actual code motion strategy.

5063–5070

Is my understanding correct, that you removed this because we no longer support this case? I.e. the dep 1->2 does not currently allow for this.

If this is true, we should probably add a FIXME.

Also, I thought the WAW case was the only reason for the bottom-up ordering. That is a bit confusing now too.

5124–5127

It would be nice to use A and B related iterators in this part because that is what you mention in the comment. E.g. AI, BI or IA, IB.

[mssimpso]

lib/Transforms/Vectorize/LoopVectorize.cpp

937

Sounds good. I'll update this and the comments.

5063–5070

No, we do still support this case, for essentially the reason the existing comment states. When the outer loop of the analysis is on (3) and we visit (2) and (1) in the inner loop, we will form the (3,2) group. (1) can't be added to (3,2) because a member already exists in group (3,2) with the same offset. When the outer loop is on (2), we will again visit (1) in the inner loop. This time we will see the dependence between (1) and (2) and give up trying to add additional accesses to (2)'s group. (1) is not yet in a group, so the outer loop moves on to (1). Thus, (1) must form a group with accesses that precede it and won't be sunk, as the existing comment says.

I removed this comment because I thought it was somewhat misleading. The bottom-up ordering is not sufficient to prevent us from breaking WAW dependencies. We still have to explicitly check for them. For example, if we had something like the following for a factor 2 group:

A[i]   = x  (1)
A[i+2] = y  (2)
A[i+1] = z  (3)

The analysis would proceed as before. When the outer loop is on (3): this time (2) is not added to (3)'s group because its index is too large. (1) is temporarily added to (3)'s group, creating a (3,1) group. When the outer loop is on (2): we see the dependence between (1) and (2). As before, we stop trying to add additional instructions to (2)'s group. But now since (1) is already in a group, and we now know it shouldn't be reordered, we release the (3,1) group. So the bottom-up ordering isn't sufficient as we still have to check for the dependence.

It's probably worth adding a comment that clarifies why the analysis is bottom-up.

5124–5127

I agree. I think we should also swap A and B in this function to match what we did to the canReorderMemAccesses function. There, A precedes B, but here B precedes A. They should be consistent.

[mssimpso]

lib/Transforms/Vectorize/LoopVectorize.cpp

5063–5070

I got the second example here slightly wrong, but the idea is the same. I was intending to describe something like:

A[i-1] = x  (1)
A[i-3] = y  (2)
A[i]   = z  (3)

Now, the dependence between (1) and (2) will cause the (3,1) group to be released, as I originally described. I'm adding test cases for both of these WAW examples.

5124–5127

Actually, swapping A with B in this function will make the review very difficult. I think I'd rather swap A and B in canReorderMemAccesses to make things consistent. This will mean B precedes A both places. We can then swap them both in an NFC patch if we want A to precede B.

[mssimpso]

Addressed Adam's comments.

• Renamed canReorderMemAccesses and updated comments
• Swapped A and B in canReorderMemAccesses to be consistent with the reset of the analysis (i.e., B precedes A). We can swap the entire analysis in a follow-on.
• Updated iterators to be more descriptive (i.e., AI and BI).
• Commented about the bottom-up ordering.
• Added test cases for the two WAW examples mentioned in my last update.

[mssimpso]

Adam,

Do you have any additional comments for this patch? Thanks!

Matt.

[anemet]

Matt,

All agreed, I just have a few more suggestions to improve comments for this complex piece.

Let me know what you think.

Adam

lib/Transforms/Vectorize/LoopVectorize.cpp

5063–5070

Wow, this is very subtle too. This and the previous case of why we need to remove elements from a group needs a high-level comment somewhere around the call to canReorder... See my comments on the particular lines.

5118–5127

I don't think the comment is sufficient to cover all the subtleties here. I would prefer to say something like:

We can't have dependences between accesses in a group and other accesses that are located between the first and the last element of group.

Probably before the break statement we should also say that:

It's OK to have dependences between accesses in a group and other accesses before the first instruction we just can't extend the group beyond these.

I am also wondering if we need a picture to further visualize this, i.e. a case where there is an intervening access and one where falls outside the range of the group.

5123–5124

OK.

test/Transforms/LoopVectorize/interleaved-accesses.ll

769–770

... but exclude a[i] = x

[mssimpso]

Adam,

Thanks very much for the suggestions. They all look good to me! I will update the patch.

Matt.

[mssimpso]

Sharpened comments according to Adam's feedback.

[anemet]

Looks great to me! Thanks for the improvements and of course initially taking this on!

[mssimpso]

Thanks Adam and Silviu for all the detailed feedback! Getting these dependences right can be tricky, so I appreciate the attention.

lib/Transforms/Vectorize/LoopVectorize.cpp

 /// a 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(PredicatedScalarEvolution &PSE, Loop *L,
-                        DominatorTree *DT)
-      : PSE(PSE), TheLoop(L), DT(DT), RequiresScalarEpilogue(false) {}
+                        DominatorTree *DT, LoopInfo *LI)
+      : PSE(PSE), TheLoop(L), DT(DT), LI(LI), RequiresScalarEpilogue(false) {}
 
   ~InterleavedAccessInfo() {
     SmallSet<InterleaveGroup *, 4> DelSet;
     // Avoid releasing a pointer twice.
     for (auto &I : InterleaveGroupMap)
       DelSet.insert(I.second);
     for (auto *Ptr : DelSet)
       delete Ptr;

 private:
   /// A wrapper around ScalarEvolution, used to add runtime SCEV checks.
   /// Simplifies SCEV expressions in the context of existing SCEV assumptions.
   /// The interleaved access analysis can also add new predicates (for example
   /// by versioning strides of pointers).
   PredicatedScalarEvolution &PSE;
   Loop *TheLoop;
   DominatorTree *DT;
+  LoopInfo *LI;
 
   /// True if the loop may contain non-reversed interleaved groups with
   /// out-of-bounds accesses. We ensure we don't speculatively access memory
   /// out-of-bounds by executing at least one scalar epilogue iteration.
   bool RequiresScalarEpilogue;
 
   /// Holds the relationships between the members and the interleave group.
   DenseMap<Instruction *, InterleaveGroup *> InterleaveGroupMap;
void releaseGroup(InterleaveGroup *Group) {
 
     delete Group;
   }
 
   /// \brief Collect all the accesses with a constant stride in program order.
   void collectConstStridedAccesses(
       MapVector<Instruction *, StrideDescriptor> &StrideAccesses,
       const ValueToValueMap &Strides);
+
+  /// \brief Returns true if there is a loop-independent read-after-write
+  /// dependence between instructions \p R and \p W.
+  ///
+  /// Such a dependence exists if the dependence distance between the
+  /// instructions is zero and the write may be executed before the read.
+  bool isLoopIndependentRAW(Instruction *R, Instruction *W, int Distance) {
+    if (!Distance && R->mayReadFromMemory() && W->mayWriteToMemory() &&
+        !DT->dominates(R, W))
+      return true;
+    return false;
+  }
 };
 
 /// Utility class for getting and setting loop vectorizer hints in the form
 /// of loop metadata.
 /// This class keeps a number of loop annotations locally (as member variables)
 /// and can, upon request, write them back as metadata on the loop. It will
 /// initially scan the loop for existing metadata, and will update the local
 /// values based on information in the loop.
 /// We cannot write all values to metadata, as the mere presence of some info,
 /// for example 'force', means a decision has been made. So, we need to be
 /// careful NOT to add them if the user hasn't specifically asked so.
 class LoopVectorizeHints {
   enum HintKind { HK_WIDTH, HK_UNROLL, HK_FORCE };
 
   /// Hint - associates name and validation with the hint value.
   struct Hint {
     const char *Name;
     unsigned Value; // This may have to change for non-numeric values.
     HintKind Kind;
 
     Hint(const char *Name, unsigned Value, HintKind Kind)
         : Name(Name), Value(Value), Kind(Kind) {}
 
     bool validate(unsigned Val) {
       switch (Kind) {
       case HK_WIDTH:
         return isPowerOf2_32(Val) && Val <= VectorizerParams::MaxVectorWidth;

 /// This class is also used by InnerLoopVectorizer for identifying
 /// induction variable and the different reduction variables.
 class LoopVectorizationLegality {
 public:
   LoopVectorizationLegality(Loop *L, PredicatedScalarEvolution &PSE,
                             DominatorTree *DT, TargetLibraryInfo *TLI,
                             AliasAnalysis *AA, Function *F,
                             const TargetTransformInfo *TTI,
-                            LoopAccessAnalysis *LAA,
+                            LoopAccessAnalysis *LAA, LoopInfo *LI,
                             LoopVectorizationRequirements *R,
                             LoopVectorizeHints *H)
       : NumPredStores(0), TheLoop(L), PSE(PSE), TLI(TLI), TheFunction(F),
-        TTI(TTI), DT(DT), LAA(LAA), LAI(nullptr), InterleaveInfo(PSE, L, DT),
-        Induction(nullptr), WidestIndTy(nullptr), HasFunNoNaNAttr(false),
-        Requirements(R), Hints(H) {}
+        TTI(TTI), DT(DT), LAA(LAA), LAI(nullptr),
+        InterleaveInfo(PSE, L, DT, LI), Induction(nullptr),
+        WidestIndTy(nullptr), HasFunNoNaNAttr(false), Requirements(R),
+        Hints(H) {}
 
   /// ReductionList contains the reduction descriptors for all
   /// of the reductions that were found in the loop.
   typedef DenseMap<PHINode *, RecurrenceDescriptor> ReductionList;
 
   /// InductionList saves induction variables and maps them to the
   /// induction descriptor.
   typedef MapVector<PHINode *, InductionDescriptor> InductionList;
if (TC > 0u && TC < TinyTripCountVectorThreshold) {
         return false;
       }
     }
 
     PredicatedScalarEvolution PSE(*SE, *L);
 
     // Check if it is legal to vectorize the loop.
     LoopVectorizationRequirements Requirements;
-    LoopVectorizationLegality LVL(L, PSE, DT, TLI, AA, F, TTI, LAA,
+    LoopVectorizationLegality LVL(L, PSE, DT, TLI, AA, F, TTI, LAA, LI,
                                   &Requirements, &Hints);
     if (!LVL.canVectorize()) {
       DEBUG(dbgs() << "LV: Not vectorizing: Cannot prove legality.\n");
       emitMissedWarning(F, L, Hints);
       return false;
     }
 
     // Collect values we want to ignore in the cost model. This includes

 }
 
 void InterleavedAccessInfo::collectConstStridedAccesses(
     MapVector<Instruction *, StrideDescriptor> &StrideAccesses,
     const ValueToValueMap &Strides) {
   // Holds load/store instructions in program order.
   SmallVector<Instruction *, 16> AccessList;
 
-  for (auto *BB : TheLoop->getBlocks()) {
+  // Since it's desired that the load/store instructions be maintained in
+  // "program order" for the interleaved access analysis, we have to visit the
+  // blocks in the loop in reverse postorder (i.e., in a topological order).
+  // Such an ordering will ensure that any load/store that may be executed
+  // before a second load/store will precede the second load/store in the
+  // AccessList.
+  LoopBlocksDFS DFS(TheLoop);
+  DFS.perform(LI);
+  for (LoopBlocksDFS::RPOIterator I = DFS.beginRPO(), E = DFS.endRPO(); I != E;
+       ++I) {
+    BasicBlock *BB = *I;
     bool IsPred = LoopAccessInfo::blockNeedsPredication(BB, TheLoop, DT);
 
     for (auto &I : *BB) {
       if (!isa<LoadInst>(&I) && !isa<StoreInst>(&I))
         continue;
       // FIXME: Currently we can't handle mixed accesses and predicated accesses
       if (IsPred)
         return;
for (auto I : AccessList) {
     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());
 
     StrideAccesses[I] = StrideDescriptor(Stride, Scev, Size, Align);
   }
 }
 
 // Analyze interleaved accesses and collect them into interleave groups.
 //
 // Notice that the vectorization on interleaved groups will change instruction
 // orders and may break dependences. But the memory dependence check guarantees
 // that there is no overlap between two pointers of different strides, element
 // sizes or underlying bases.
 //
 // For pointers sharing the same stride, element size and underlying base, no
-// need to worry about Read-After-Write dependences and Write-After-Read
-// dependences.
-//
-// E.g. The RAW dependence:  A[i] = a;
-//                           b = A[i];
-// This won't exist as it is a store-load forwarding conflict, which has
-// already been checked and forbidden in the dependence check.
+// need to worry about Write-After-Read dependences. However, Read-After-Write
+// dependences must be considered.
 //
 // E.g. The WAR dependence:  a = A[i];  // (1)
 //                           A[i] = b;  // (2)
 // The store group of (2) is always inserted at or below (2), and the load group
 // of (1) is always inserted at or above (1). The dependence is safe.
+//
+// E.g. The RAW dependence:  A[i] = a;  // (1)
+//                           b = A[i];  // (2)
+// We have to ensure that the insert position of the store group of (1) may not
+// be below the insert position of the load group of (2). If this condition
+// does not hold, (1) and (2) would be reordered, breaking the dependence.
 void InterleavedAccessInfo::analyzeInterleaving(
     const ValueToValueMap &Strides) {
   DEBUG(dbgs() << "LV: Analyzing interleaved accesses...\n");
 
   // Holds all the stride accesses.
   MapVector<Instruction *, StrideDescriptor> StrideAccesses;
   collectConstStridedAccesses(StrideAccesses, Strides);
 
   if (StrideAccesses.empty())
     return;
 
   // Holds all interleaved store groups temporarily.
   SmallSetVector<InterleaveGroup *, 4> StoreGroups;
   // Holds all interleaved load groups temporarily.
   SmallSetVector<InterleaveGroup *, 4> LoadGroups;
+  // Holds store instructions whose interleaved groups must be removed from
+  // consideration due to the possibility of breaking read-after-write
+  // dependences.
+  SmallPtrSet<Instruction *, 4> StoresToRemove;
 
   // 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. B belongs to the group according to the distance.
   //
   // The bottom-up order can avoid breaking the Write-After-Write dependences
   // between two pointers of the same base.
   // E.g.  A[i]   = a;   (1)
   //       A[i]   = b;   (2)
   //       A[i+1] = c    (3)
   // We form the group (2)+(3) in front, so (1) has to form groups with accesses
   // above (1), which guarantees that (1) is always above (2).
   for (auto I = StrideAccesses.rbegin(), E = StrideAccesses.rend(); I != E;
        ++I) {
     Instruction *A = I->first;
     StrideDescriptor DesA = I->second;
 
     InterleaveGroup *Group = getInterleaveGroup(A);
     if (!Group) {
       DEBUG(dbgs() << "LV: Creating an interleave group with:" << *A << '\n');
       Group = createInterleaveGroup(A, DesA.Stride, DesA.Align);
     }
 
     if (A->mayWriteToMemory())
       StoreGroups.insert(Group);
     else
       LoadGroups.insert(Group);
 
+    // Holds store instructions that may be involved in a broken
+    // read-after-write dependence.
+    SmallVector<Instruction *, 2> LoopIndependentRAWStores;
+
     for (auto II = std::next(I); II != E; ++II) {
       Instruction *B = II->first;
       StrideDescriptor DesB = II->second;
 
-      // Ignore if B is already in a group or B is a different memory operation.
-      if (isInterleaved(B) || 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>(
           PSE.getSE()->getMinusSCEV(DesB.Scev, DesA.Scev));
       if (!DistToA)
         continue;
 
       int DistanceToA = DistToA->getAPInt().getSExtValue();
 
+      // Check for a loop-independent read-after-write dependence from B (a
+      // possible store) to A (a possible load).
+      //
+      // If a dependence may exist, and the store is already in an interleaved
+      // group, the store will be "moved" to the insert position of the group.
+      // If the insert position may follow the load (it should, given the
+      // bottom-up order in which we are visiting the instructions), the
+      // read-after-write dependence would be broken. Thus, mark the store for
+      // removal, and prevent further loads from being added to the group. If
+      // additional loads were to be added to the group, this would cause the
+      // current load to "move" to a new location, breaking the dependence.
+      //
+      // If a dependence may exist, and the store is not already in an
+      // interleaved group, this is not necessary a problem. We don't yet know
+      // if the load or store will be "moved" to a new insert position. Save
+      // the store for later consideration. If we try and add another load to
+      // the group, the dependence would then be broken.
+      if (isLoopIndependentRAW(A, B, DistanceToA)) {
+        if (isInterleaved(B))
+          if (!DT->dominates(getInterleaveGroup(B)->getInsertPos(), A)) {
+            StoresToRemove.insert(B);
+            break;
+          }
+        LoopIndependentRAWStores.push_back(B);
+      }
+
+      // Ignore if B is already in a group or B is a different memory operation.
+      if (isInterleaved(B) || A->mayReadFromMemory() != B->mayReadFromMemory())
+        continue;
+
       // Skip if the distance is not multiple of size as they are not in the
       // same group.
       if (DistanceToA % static_cast<int>(DesA.Size))
         continue;
 
+      // Ensure that "moving" A (a load) to the insert position of B (a load)
+      // will not violate a loop-independent read-after-write dependence.
+      //
+      // The store instructions involved in any read-after-write dependences
+      // have already been recorded. If a dependence would be violated, mark
+      // the store for removal, and prevent further loads from being added to
+      // the group.
+      if (A->mayReadFromMemory() && !LoopIndependentRAWStores.empty()) {
+        for (Instruction *Store : LoopIndependentRAWStores)
+          if (!DT->dominates(Store, B))
+            StoresToRemove.insert(Store);
+        break;
+      }
+
       // The index of B is the index of A plus the related index to A.
       int IndexB =
           Group->getIndex(A) + DistanceToA / static_cast<int>(DesA.Size);
 
       // Try to insert B into the group.
       if (Group->insertMember(B, IndexB, DesB.Align)) {
         DEBUG(dbgs() << "LV: Inserted:" << *B << '\n'
                      << "    into the interleave group with" << *A << '\n');
         InterleaveGroupMap[B] = Group;
 
         // Set the first load in program order as the insert position.
         if (B->mayReadFromMemory())
           Group->setInsertPos(B);
       }
     } // Iteration on instruction B
   }   // Iteration on instruction A
 
+  // Remove interleaved store groups having members involved in a potentially
+  // broken read-after-write dependence. We simply remove the entire group
+  // instead of the offending members since store groups with gaps will be
+  // removed anyway.
+  for (Instruction *Store : StoresToRemove)
+    if (isInterleaved(Store)) {
+      InterleaveGroup *StoreGroup = getInterleaveGroup(Store);
+      StoreGroups.remove(StoreGroup);
+      releaseGroup(StoreGroup);
+    }
+
   // Remove interleaved store groups with gaps.
   for (InterleaveGroup *Group : StoreGroups)
     if (Group->getNumMembers() != Group->getFactor())
       releaseGroup(Group);
 
   // If there is a non-reversed interleaved load group with gaps, we will need
   // to execute at least one scalar epilogue iteration. This will ensure that
   // we don't speculatively access memory out-of-bounds. Note that we only need

test/Transforms/LoopVectorize/interleaved-accesses.ll

for.body:                                         ; preds = %for.body, %entry
   %b = getelementptr inbounds %struct.IntFloat, %struct.IntFloat* %A, i64 %indvars.iv, i32 1
   %tmp1 = load float, float* %b, align 4
   %add3 = fadd fast float %SumB.014, %tmp1
   %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
 }
 
+; Check vectorization of interleaved accesses groups in the presence of a
+; loop-independent read-after-write dependence. When generating code,
+; interleaved loads are inserted at the location of the first load, and
+; interleaved stores are inserted at the location of the last store. This
+; load/store re-ordering can break RAW dependences.
+;
+; In this test, we create two separate load groups with gaps to avoid breaking
+; the dependence. We do the same for the stores. Because the interleaved store
+; groups have gaps, they are scalarized. Because the interleaved load groups
+; have gaps, we must execute at least one iteration of the scalar epligue loop.
+
+; struct pair {
+;  int x;
+;  int y;
+; };
+;
+; void PR27626(struct pair *p, int n) {
+;   for (int i = 0; i < n; i++) {
+;     p->x = p->y;
+;     p->y = p->x;
+;   }
+; }
+
+; CHECK-LABEL: @PR27626(
+; CHECK: min.iters.checked:
+; CHECK:   %n.mod.vf = and i64 %[[N:.+]], 3
+; CHECK:   %[[IsZero:[a-zA-Z0-9]+]] = icmp eq i64 %n.mod.vf, 0
+; CHECK:   %[[R:[a-zA-Z0-9]+]] = select i1 %[[IsZero]], i64 4, i64 %n.mod.vf
+; CHECK:   %n.vec = sub i64 %[[N]], %[[R]]
+; CHECK: vector.body:
+; CHECK:   %[[L1:.+]] = load <8 x i64>, <8 x i64>* {{.*}}
+; CHECK:   %[[X1:.+]] = extractelement <8 x i64> %[[L1]], i32 0
+; CHECK:   store i64 %[[X1]], {{.*}}
+; CHECK:   %[[X2:.+]] = extractelement <8 x i64> %[[L1]], i32 2
+; CHECK:   store i64 %[[X2]], {{.*}}
+; CHECK:   %[[X3:.+]] = extractelement <8 x i64> %[[L1]], i32 4
+; CHECK:   store i64 %[[X3]], {{.*}}
+; CHECK:   %[[X4:.+]] = extractelement <8 x i64> %[[L1]], i32 6
+; CHECK:   store i64 %[[X4]], {{.*}}
+; CHECK:   %[[L2:.+]] = load <8 x i64>, <8 x i64>* {{.*}}
+; CHECK:   %[[X5:.+]] = extractelement <8 x i64> %[[L2]], i32 0
+; CHECK:   store i64 %[[X5]], {{.*}}
+; CHECK:   %[[X6:.+]] = extractelement <8 x i64> %[[L2]], i32 2
+; CHECK:   store i64 %[[X6]], {{.*}}
+; CHECK:   %[[X7:.+]] = extractelement <8 x i64> %[[L2]], i32 4
+; CHECK:   store i64 %[[X7]], {{.*}}
+; CHECK:   %[[X8:.+]] = extractelement <8 x i64> %[[L2]], i32 6
+; CHECK:   store i64 %[[X8]], {{.*}}
+; CHECK: middle.block:
+; CHECK:   br i1 false, label %for.end, label %scalar.ph
+
+define void @PR27626(%pair *%p, i64 %n) {
+
+entry:
+  br label %for.body
+
+for.body:
+  %i  = phi i64 [ %i.next, %for.body ], [ 0, %entry ]
+  %p.0 = getelementptr inbounds %pair, %pair* %p, i64 %i, i32 0
+  %p.1 = getelementptr inbounds %pair, %pair* %p, i64 %i, i32 1
+  %0 = load i64, i64* %p.1, align 8
+  store i64 %0, i64* %p.0, align 8
+  %1 = load i64, i64* %p.0, align 8
+  store i64 %1, i64 *%p.1, align 8
+  %i.next = add nuw nsw i64 %i, 1
+  %cond = icmp slt i64 %i.next, %n
+  br i1 %cond, label %for.body, label %for.end
+
+for.end:
+  ret void
+}
+
 attributes #0 = { "unsafe-fp-math"="true" }