[LV] Avoid building interleaved group in presence of WAW dependency

[ebrevnov]

Summary

This is another attempt to fix an issue from https://reviews.llvm.org/D57180. I have to create a new review since have no permissions to update diff in original review.

I don't think we actually need to do any additional book keeping (as suggested in D57180). Current algorithm already examines all pairs and in case of dependence will invalidate interleaving group. I think the real issue is WAW dependence (on the same iteration) is not collected by LoopAccessInfo in the first place and as a result canReorderMemAccessesForInterleavedGroups returns wrong answer. The fix is to explicitly check for WAW dependence in canReorderMemAccessesForInterleavedGroups.

[Ayal]

From the SUMMARY above:

I don't think we actually need to do any additional book keeping (as suggested in D57180). Current algorithm already examines all pairs and in case of dependence will invalidate interleaving group. I think the real issue is WAW dependence (on the same iteration) is not collected by LoopAccessInfo in the first place and as a result canReorderMemAccessesForInterleavedGroups returns wrong answer. The fix is to explicitly check for WAW dependence in canReorderMemAccessesForInterleavedGroups.

Nice catch! Agree about the real issue being a deficiency of LoopAccessInfo, and that it's better to treat all interleave-group-preventing dependencies the same, w/o dedicating special treatment for same-iteration WAW dependences. Suggest to fix this real issue at its core.

LoopAccessInfo does collect the 6 same-iteration WAR Forward dependences between each of the 3 loads and their 2 subsequent same-address stores, in the testcase below, but these do not interfere with interleave-grouping the stores. So it's perfectly capable of collecting same-iteration WAW Forward dependences as well. (LoopAccessInfo should also already collect any same-iteration RAW dependences, although such cases would hopefully be optimized away.)

The reason why LoopAccessInfo does not collect same-iteration WAW dependences is due to the way areDepsSafe() traverses pairs of DependentAccesses, held in EquivalenceClasses<MemAccessInfo> which clusters stores-to-same-address together (and load-to-same-address together, but separately from the stores). One way of fixing this may be:

diff --git a/llvm/lib/Analysis/LoopAccessAnalysis.cpp b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
index 36bd9a8b7ea..a3f40826861 100644
--- a/llvm/lib/Analysis/LoopAccessAnalysis.cpp
+++ b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
@@ -1641,13 +1641,21 @@ bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets,
     // Check every access pair.
     while (AI != AE) {
       Visited.insert(*AI);
-      EquivalenceClasses<MemAccessInfo>::member_iterator OI = std::next(AI);
+      bool AIIsWrite = AI->getInt();
+      // Check loads only against next equivalent class, but stores also against
+      // other stores in the same equivalence class - to the same address.
+      EquivalenceClasses<MemAccessInfo>::member_iterator OI =
+          (AIIsWrite ? AI : std::next(AI));
       while (OI != AE) {
         // Check every accessing instruction pair in program order.
         for (std::vector<unsigned>::iterator I1 = Accesses[*AI].begin(),
              I1E = Accesses[*AI].end(); I1 != I1E; ++I1)
-          for (std::vector<unsigned>::iterator I2 = Accesses[*OI].begin(),
-               I2E = Accesses[*OI].end(); I2 != I2E; ++I2) {
+          // Scan all accesses of another equivalence class, but only the next
+          // accesses of the same equivalent class.
+          for (std::vector<unsigned>::iterator
+                   I2 = (OI == AI ? std::next(I1) : Accesses[*OI].begin()),
+                   I2E = (OI == AI ? I1E : Accesses[*OI].end());
+               I2 != I2E; ++I2) {
             auto A = std::make_pair(&*AI, *I1);
             auto B = std::make_pair(&*OI, *I2);

(could possibly save dependences by recording only those between pairs of adjacent stores to same address, relying on transitivity)

include/llvm/Analysis/VectorUtils.h

612 ↗

(On Diff #207236)

Src and Sink should only be StoreInst's here, right?

[ebrevnov]

include/llvm/Analysis/VectorUtils.h

612 ↗

(On Diff #207236)

On enter to canReorderMemAccessesForInterleavedGroups we can have load or store only. mayWriteToMemory treats some types of loads as writing to memory. Thus load is possible here as well.

[ebrevnov]

In D63981#1579704, @Ayal wrote:

From the SUMMARY above:

I don't think we actually need to do any additional book keeping (as suggested in D57180). Current algorithm already examines all pairs and in case of dependence will invalidate interleaving group. I think the real issue is WAW dependence (on the same iteration) is not collected by LoopAccessInfo in the first place and as a result canReorderMemAccessesForInterleavedGroups returns wrong answer. The fix is to explicitly check for WAW dependence in canReorderMemAccessesForInterleavedGroups.

Nice catch! Agree about the real issue being a deficiency of LoopAccessInfo, and that it's better to treat all interleave-group-preventing dependencies the same, w/o dedicating special treatment for same-iteration WAW dependences. Suggest to fix this real issue at its core.

LoopAccessInfo does collect the 6 same-iteration WAR Forward dependences between each of the 3 loads and their 2 subsequent same-address stores, in the testcase below, but these do not interfere with interleave-grouping the stores. So it's perfectly capable of collecting same-iteration WAW Forward dependences as well. (LoopAccessInfo should also already collect any same-iteration RAW dependences, although such cases would hopefully be optimized away.)

The reason why LoopAccessInfo does not collect same-iteration WAW dependences is due to the way areDepsSafe() traverses pairs of DependentAccesses, held in EquivalenceClasses<MemAccessInfo> which clusters stores-to-same-address together (and load-to-same-address together, but separately from the stores). One way of fixing this may be:

diff --git a/llvm/lib/Analysis/LoopAccessAnalysis.cpp b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
index 36bd9a8b7ea..a3f40826861 100644
--- a/llvm/lib/Analysis/LoopAccessAnalysis.cpp
+++ b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
@@ -1641,13 +1641,21 @@ bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets,
     // Check every access pair.
     while (AI != AE) {
       Visited.insert(*AI);
-      EquivalenceClasses<MemAccessInfo>::member_iterator OI = std::next(AI);
+      bool AIIsWrite = AI->getInt();
+      // Check loads only against next equivalent class, but stores also against
+      // other stores in the same equivalence class - to the same address.
+      EquivalenceClasses<MemAccessInfo>::member_iterator OI =
+          (AIIsWrite ? AI : std::next(AI));
       while (OI != AE) {
         // Check every accessing instruction pair in program order.
         for (std::vector<unsigned>::iterator I1 = Accesses[*AI].begin(),
              I1E = Accesses[*AI].end(); I1 != I1E; ++I1)
-          for (std::vector<unsigned>::iterator I2 = Accesses[*OI].begin(),
-               I2E = Accesses[*OI].end(); I2 != I2E; ++I2) {
+          // Scan all accesses of another equivalence class, but only the next
+          // accesses of the same equivalent class.
+          for (std::vector<unsigned>::iterator
+                   I2 = (OI == AI ? std::next(I1) : Accesses[*OI].begin()),
+                   I2E = (OI == AI ? I1E : Accesses[*OI].end());
+               I2 != I2E; ++I2) {
             auto A = std::make_pair(&*AI, *I1);
             auto B = std::make_pair(&*OI, *I2);

(could possibly save dependences by recording only those between pairs of adjacent stores to same address, relying on transitivity)

Ayal, thanks for paying attention to this :-). Solution your are proposing looks more solid to me. But I'm a bit worry if reporting such WAW dependencies by LoopAccessInfo will affect many other places...and possibly compile time. What do you think?

[Ayal]

In D63981#1580294, @ebrevnov wrote:

[snip]
But I'm a bit worry if reporting such WAW dependencies by LoopAccessInfo will affect many other places...and possibly compile time. What do you think?

I think same-iteration WAW dependences should be reported just as (and especially given that) same-iteration WAR dependences are. There's already a MaxDependences threshold in place to bail out when there are too many dependences. Admittedly borderline cases may now bail out with these extra WAW dependencies. But how many stores to the same address do we expect... and as commented in D57180 - best optimize them into one. Also, as commented, it should suffice to record only a path of dependences between pairs of adjacent stores, e.g., by setting I2E to std::next(I2) instead of I1E, unless I2==I2E.

[ebrevnov]

Updating patch to use implementation proposed by Ayal.

[ebrevnov]

Hi @hsaito!

Would be nice if you find time to take a look.

Thanks
Evgeniy

[hsaito]

In D63981#1607984, @ebrevnov wrote:

Hi @hsaito!

Would be nice if you find time to take a look.

@ebrevnov, thanks for pinging. This fell into the stack of not yet processed e-mails accumulated during vacation. Will take a look today.

[hsaito]

Indeed, this is a much cleaner fix. LGTM.

[ebrevnov]

Thanks for quick response @hsaito ! May I ask you to commit it as well since I don't have committer rights yet.

[hsaito]

In D63981#1609626, @ebrevnov wrote:

Thanks for quick response @hsaito ! May I ask you to commit it as well since I don't have committer rights yet.

Sure. Will do it tonight.

[hsaito]

r367654 | hsaito | 2019-08-01 23:31:50 -0700 (Thu, 01 Aug 2019) | 12 lines

[LV] Avoid building interleaved group in presence of WAW dependency

Reviewers: hsaito, Ayal, fhahn, anna, mkazantsev

Reviewed By: hsaito

Patch by evrevnov, thanks!

Differential Revision: https://reviews.llvm.org/D63981

[hsaito]

LIT test has been moved to X86 subdir, in response to ps4-buildslave1 buildbot failure.

[hsaito]

Reported buildbot fails for Evgueni to follow up as needed:

http://lab.llvm.org:8011/builders/clang-with-thin-lto-ubuntu/builds/18311 --- blamelist had only this commit. Resolved by moving the LIT test to X86.

http://lab.llvm.org:8011/builders/clang-cmake-thumbv7-full-sh/builds/2185 --- I think this is not relevant. "clang -emit-llvm -O0".

http://lab.llvm.org:8011/builders/ppc64le-lld-multistage-test/builds/5742 --- not relevant. Something to do with the test infrastructure.

[ebrevnov]

In D63981#1613097, @hsaito wrote:

Reported buildbot fails for Evgueni to follow up as needed:

http://lab.llvm.org:8011/builders/clang-with-thin-lto-ubuntu/builds/18311 --- blamelist had only this commit. Resolved by moving the LIT test to X86.

http://lab.llvm.org:8011/builders/clang-cmake-thumbv7-full-sh/builds/2185 --- I think this is not relevant. "clang -emit-llvm -O0".

Pretty sure that was caused by https://reviews.llvm.org/D65286. which introduces failing check.

http://lab.llvm.org:8011/builders/ppc64le-lld-multistage-test/builds/5742 --- not relevant. Something to do with the test infrastructure.

llvm/trunk/lib/Analysis/LoopAccessAnalysis.cpp

for (MemAccessInfo CurAccess : CheckDeps) {
     EquivalenceClasses<MemAccessInfo>::member_iterator AI =
         AccessSets.member_begin(I);
     EquivalenceClasses<MemAccessInfo>::member_iterator AE =
         AccessSets.member_end();
 
     // Check every access pair.
     while (AI != AE) {
       Visited.insert(*AI);
-      EquivalenceClasses<MemAccessInfo>::member_iterator OI = std::next(AI);
+      bool AIIsWrite = AI->getInt();
+      // Check loads only against next equivalent class, but stores also against
+      // other stores in the same equivalence class - to the same address.
+      EquivalenceClasses<MemAccessInfo>::member_iterator OI =
+          (AIIsWrite ? AI : std::next(AI));
       while (OI != AE) {
         // Check every accessing instruction pair in program order.
         for (std::vector<unsigned>::iterator I1 = Accesses[*AI].begin(),
              I1E = Accesses[*AI].end(); I1 != I1E; ++I1)
-          for (std::vector<unsigned>::iterator I2 = Accesses[*OI].begin(),
-               I2E = Accesses[*OI].end(); I2 != I2E; ++I2) {
+          // Scan all accesses of another equivalence class, but only the next
+          // accesses of the same equivalent class.
+          for (std::vector<unsigned>::iterator
+                   I2 = (OI == AI ? std::next(I1) : Accesses[*OI].begin()),
+                   I2E = (OI == AI ? I1E : Accesses[*OI].end());
+               I2 != I2E; ++I2) {
             auto A = std::make_pair(&*AI, *I1);
             auto B = std::make_pair(&*OI, *I2);
 
             assert(*I1 != *I2);
             if (*I1 > *I2)
               std::swap(A, B);
 
             Dependence::DepType Type =

llvm/trunk/lib/Analysis/VectorUtils.cpp

for (auto AI = std::next(BI); AI != E; ++AI) {
       if (!canReorderMemAccessesForInterleavedGroups(&*AI, &*BI)) {
         // If a dependence exists and A is already in a group, we know that A
         // must be a store since A precedes B and WAR dependences are allowed.
         // Thus, A would be sunk below B. We release A's group to prevent this
         // illegal code motion. A will then be free to form another group with
         // instructions that precede it.
         if (isInterleaved(A)) {
           InterleaveGroup<Instruction> *StoreGroup = getInterleaveGroup(A);
+
+          LLVM_DEBUG(dbgs() << "LV: Invalidated store group due to "
+                               "dependence between " << *A << " and "<< *B << '\n');
+
           StoreGroups.remove(StoreGroup);
           releaseGroup(StoreGroup);
         }
 
         // If a dependence exists and A is not already in a group (or it was
         // and we just released it), B might be hoisted above A (if B is a
         // load) or another store might be sunk below A (if B is a store). In
         // either case, we can't add additional instructions to B's group. B

llvm/trunk/test/Transforms/LoopVectorize/interleaved-accesses-waw-dependency.ll

+; RUN: opt < %s -loop-vectorize -force-vector-width=4 -force-vector-interleave=2 -debug-only=vectorutils -disable-output -enable-interleaved-mem-accesses=true 2>&1 | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; PR40291
+; The loop does the following operation 3 times:
+; 1. Load x from memory;
+; 2. Store (x + 1) to this memory;
+; 3. if (x < 1), store 0 to this memory.
+
+; When scalar version stores 0 in all locations, the vector version should do
+; the same thing. However, with interleaving it does not honour the WAW dependency between
+; store 0 and store (x + 1) to the same memory.
+; For now, we identify such unsafe dependency and disable adding the
+; store into the interleaved group.
+; In this test case, because we disable adding store into i32* %storeaddr12 and
+; storeaddr22, we create interleaved groups with gaps and
+; disable that interleaved group. So, we are only left with valid interleaved
+; groups.
+
+
+
+
+; CHECK:      LV: Analyzing interleaved accesses...
+; CHECK:      LV: Creating an interleave group with:  store i32 %tmp34, i32* %storeaddr32, align 4
+; CHECK-NEXT: LV: Inserted:  store i32 %tmp24, i32* %storeaddr22, align 4
+; CHECK-NEXT:     into the interleave group with  store i32 %tmp34, i32* %storeaddr32, align 4
+; CHECK-NEXT: LV: Inserted:  store i32 %tmp14, i32* %storeaddr12, align 4
+; CHECK-NEXT:     into the interleave group with  store i32 %tmp34, i32* %storeaddr32, align 4
+; CHECK:      LV: Invalidated store group due to dependence between   store i32 %tmp24, i32* %storeaddr22, align 4 and   store i32 0, i32* %storeaddr22, align 4
+; CHECK-NEXT: LV: Creating an interleave group with:  store i32 %tmp24, i32* %storeaddr22, align 4
+; CHECK-NEXT: LV: Inserted:  store i32 %tmp14, i32* %storeaddr12, align 4
+; CHECK-NEXT:     into the interleave group with  store i32 %tmp24, i32* %storeaddr22, align 4
+; CHECK-NEXT: LV: Invalidated store group due to dependence between   store i32 %tmp14, i32* %storeaddr12, align 4 and   store i32 0, i32* %storeaddr12, align 4
+
+
+define void @test(i8* nonnull align 8 dereferenceable_or_null(24) %arg) {
+bb:
+  %tmp = getelementptr inbounds i8, i8* %arg, i64 16
+  %tmp1 = bitcast i8* %tmp to i8**
+  %tmp2 = load i8*, i8** %tmp1, align 8
+  %tmp3 = getelementptr inbounds i8, i8* %arg, i64 8
+  %tmp4 = bitcast i8* %tmp3 to i8**
+  %tmp5 = load i8*, i8** %tmp4, align 8
+  %tmp6 = getelementptr inbounds i8, i8* %tmp5, i64 12
+  %tmp7 = bitcast i8* %tmp6 to i32*
+  %tmp8 = getelementptr inbounds i8, i8* %tmp2, i64 12
+  br label %header
+
+header:                                              ; preds = %latch, %bb
+  %tmp10 = phi i64 [ %tmp41, %latch ], [ 3, %bb ]
+  %tmp11 = add nsw i64 %tmp10, -1
+  %storeaddr12 = getelementptr inbounds i32, i32* %tmp7, i64 %tmp11
+  %tmp13 = load i32, i32* %storeaddr12, align 4
+  %tmp14 = add i32 %tmp13, 1
+  store i32 %tmp14, i32* %storeaddr12, align 4
+  %tmp15 = icmp slt i32 %tmp13, 1
+  %tmp16 = xor i1 %tmp15, true
+  %tmp17 = zext i1 %tmp16 to i8
+  %tmp18 = getelementptr inbounds i8, i8* %tmp8, i64 %tmp10
+  store i8 %tmp17, i8* %tmp18, align 1
+  br i1 %tmp15, label %bb19, label %bb20
+
+bb19:                                             ; preds = %header
+  store i32 0, i32* %storeaddr12, align 4
+  br label %bb20
+
+bb20:                                             ; preds = %bb19, %header
+  %tmp21 = add nuw nsw i64 %tmp10, 1
+  %storeaddr22 = getelementptr inbounds i32, i32* %tmp7, i64 %tmp10
+  %tmp23 = load i32, i32* %storeaddr22, align 4
+  %tmp24 = add i32 %tmp23, 1
+  store i32 %tmp24, i32* %storeaddr22, align 4
+  %tmp25 = icmp slt i32 %tmp23, 1
+  %tmp26 = xor i1 %tmp25, true
+  %tmp27 = zext i1 %tmp26 to i8
+  %tmp28 = getelementptr inbounds i8, i8* %tmp8, i64 %tmp21
+  store i8 %tmp27, i8* %tmp28, align 1
+  br i1 %tmp25, label %bb29, label %bb30
+
+bb29:                                             ; preds = %bb20
+  store i32 0, i32* %storeaddr22, align 4
+  br label %bb30
+
+bb30:                                             ; preds = %bb29, %bb20
+  %tmp31 = add nuw nsw i64 %tmp10, 2
+  %storeaddr32 = getelementptr inbounds i32, i32* %tmp7, i64 %tmp21
+  %tmp33 = load i32, i32* %storeaddr32, align 4
+  %tmp34 = add i32 %tmp33, 1
+  store i32 %tmp34, i32* %storeaddr32, align 4
+  %tmp35 = icmp slt i32 %tmp33, 1
+  %tmp36 = xor i1 %tmp35, true
+  %tmp37 = zext i1 %tmp36 to i8
+  %tmp38 = getelementptr inbounds i8, i8* %tmp8, i64 %tmp31
+  store i8 %tmp37, i8* %tmp38, align 1
+  br i1 %tmp35, label %bb39, label %latch
+
+bb39:                                             ; preds = %bb30
+  store i32 0, i32* %storeaddr32, align 4
+  br label %latch
+
+latch:                                             ; preds = %bb39, %bb30
+  %tmp41 = add nuw nsw i64 %tmp10, 3
+  %tmp42 = icmp ugt i64 %tmp31, 67
+  br i1 %tmp42, label %exit, label %header
+
+exit:                                             ; preds = %latch
+  ret void
+}