[LV] Do not add load to group if it moves across conflicting store.

[fhahn]

Summary

This patch prevents invalid load groups from being formed, where a load
needs to be moved across a conflicting store.

Once we hit a store that conflicts with a load with an existing
interleave group, we need to stop adding earlier loads to the group, as
this would force hoisting the previous stores in the group across the
conflicting load.

To detect such cases, add a new CompletedLoadGroups set, which is used
to keep track of load groups to which no earlier loads can be added.

Fixes https://github.com/llvm/llvm-project/issues/63602

[fhahn]

Include test changes

[anna]

LGTM with comment. Thanks!

llvm/lib/Analysis/VectorUtils.cpp

1150

Can we move this above the insertion to LoadGroups since this Group should already be present in LoadGroups?

// Skip B if no new instructions can be added to its load group.
 if (CompletedLoadGroups.contains(Group))
      continue;
LoadGroups.insert(Group)

[fhahn]

llvm/lib/Analysis/VectorUtils.cpp

1150

Thanks, adjusted in the committed version.

[Ayal]

This raises some thoughts (post-commit), discussed with @gilr, including the need for a more thorough fix.

llvm/lib/Analysis/VectorUtils.cpp

1090

Augment the above explanation to address CompletedLoadGroups?

1141

Can hoist it further - a newly created group is surely not completed.

1175

Sketch of one option to fix insertion of Group into CompletedLoadGroups whenever/as-soon-as needed.

1188

Note that it may suffice to take A out of its StoreGroup, along with all other members that precede B, but not necessarily dismantle StoreGroup completely. Worth adding some tests.

The case of a store obstructing a store-group seems symmetric to the case of a store obstructing a load-group, if store-groups are collected top-down (separately from continuing to collect load-groups bottom-up), and may then be better formed along with an analogous CompletedStoreGroups. WDYT?

1191

"(along with all other loads in B's interleave group)"

Unfortunately, earlier loads may already have been added to B's interleave group at this point. Those could either be filtered out now or prevented from insertion earlier. One way to perform the latter is sketched above.

1194–1195

We already got the interleave group of B, aka Group, and better rename it GroupB (along with renaming above StoreGroup to GroupA)?

1207

"we can't add additional instructions to B's group" - i.e., should mark B's group as completed.

llvm/test/Transforms/LoopVectorize/X86/interleaved-accesses-hoist-load-across-store.ll

105–106

Swapping these two loads circumvents the current CompletedLoadGroups, and deserves a separate test case.

This is because only the load which creates an interleaved group (the one appearing last in program order) is compared with obstructing stores.

[anna]

llvm/test/Transforms/LoopVectorize/X86/interleaved-accesses-hoist-load-across-store.ll

105–106

Ayal, I had added this test locally along with the more complete fix you suggested for checking all loads in the interleave load group. I didn't see any change in the output with the complete fix versus what we have currently in the patch (checking only the single load which would be %l2 in this case that doesn't obstruct the store).
I'll place what I have for review.

(motivation is another miscompile that looks related to interleaving and I was hoping this more complete fix handles it. Doesn't though. Will add a reproducer upstream).

[Ayal]

llvm/lib/Analysis/VectorUtils.cpp

1175

Anna, here's a more concrete sketch, which also breaks out of the enclosing "for AI" loop as needed:

if (Group && isa<LoadInst>(B)) {
  uint32_t Index = 0, Factor = Group->getFactor();
  for (; Index < Factor; ++Index) {
    Instruction *MemberOfGroupB = Group->getMember(Index);
    if (MemberOfGroupB &&
        !canReorderMemAccessesForInterleavedGroups(
            &*AI, &*AccessStrideInfo.find(MemberOfGroupB)))
      break;
  }
  if (Index < Factor) {
    CompletedLoadGroups.insert(Group);
    break;
  }
}

Curious to learn if it helps.

[anna]

llvm/lib/Analysis/VectorUtils.cpp

1175

thanks Ayal! My fix had missed that we need to break out of the "for AI" loop (the original fix was automatically doing that when we check for canReorderMemAccessesForInterleavedGroups for single BI at line 1208).
With this the modified testcase you suggested optimizes correctly.

llvm/lib/Analysis/VectorUtils.cpp

 //
 // E.g., for the WAW dependence:  A[i] = a;      // (1)
 //                                A[i] = b;      // (2)
 //                                A[i + 1] = c;  // (3)
 //
 // We will first create a store group with (3) and (2). (1) can't be added to
 // this group because it and (2) are dependent. However, (1) can be grouped
 // with other accesses that may precede it in program order. Note that a
 // bottom-up order does not imply that WAW dependences should not be checked.
 void InterleavedAccessInfo::analyzeInterleaving(
                                  bool EnablePredicatedInterleavedMemAccesses) {
   LLVM_DEBUG(dbgs() << "LV: Analyzing interleaved accesses...\n");
   const auto &Strides = LAI->getSymbolicStrides();
 
   // Holds all accesses with a constant stride.
   MapVector<Instruction *, StrideDescriptor> AccessStrideInfo;
   collectConstStrideAccesses(AccessStrideInfo, Strides);
 
   if (AccessStrideInfo.empty())
     return;
 
   // Collect the dependences in the loop.
   collectDependences();
 
   // Holds all interleaved store groups temporarily.
   SmallSetVector<InterleaveGroup<Instruction> *, 4> StoreGroups;
   // Holds all interleaved load groups temporarily.
   SmallSetVector<InterleaveGroup<Instruction> *, 4> LoadGroups;
+  // Groups added to this set cannot have new members added.
+  SmallPtrSet<InterleaveGroup<Instruction> *, 4> CompletedLoadGroups;
 
   // Search in bottom-up program order for pairs of accesses (A and B) that can
   // form interleaved load or store groups. In the algorithm below, access A
   // precedes access B in program order. We initialize a group for B in the
   // outer loop of the algorithm, and then in the inner loop, we attempt to
   // insert each A into B's group if:
   //
   //  1. A and B have the same stride,
for (auto BI = AccessStrideInfo.rbegin(), E = AccessStrideInfo.rend();
     InterleaveGroup<Instruction> *Group = nullptr;
     if (isStrided(DesB.Stride) &&
         (!isPredicated(B->getParent()) || EnablePredicatedInterleavedMemAccesses)) {
       Group = getInterleaveGroup(B);
       if (!Group) {
         LLVM_DEBUG(dbgs() << "LV: Creating an interleave group with:" << *B
                           << '\n');
         Group = createInterleaveGroup(B, DesB.Stride, DesB.Alignment);
       }
       if (B->mayWriteToMemory())
         StoreGroups.insert(Group);
-      else
+      else {
+        // Skip B if no new instructions can be added to its load group.
+        if (CompletedLoadGroups.contains(Group))
+          continue;
         LoadGroups.insert(Group);
       }
+    }
 
     for (auto AI = std::next(BI); AI != E; ++AI) {
       Instruction *A = AI->first;
       StrideDescriptor DesA = AI->second;
 
       // Our code motion strategy implies that we can't have dependences
       // between accesses in an interleaved group and other accesses located
       // between the first and last member of the group. Note that this also
       // means that a group can't have more than one member at a given offset.
       // The accesses in a group can have dependences with other accesses, but
       // we must ensure we don't extend the boundaries of the group such that
       // we encompass those dependent accesses.
       //
       // For example, assume we have the sequence of accesses shown below in a
       // stride-2 loop:
       //
       //  (1, 2) is a group | A[i]   = a;  // (1)
       //                    | A[i-1] = b;  // (2) |
       //                      A[i-3] = c;  // (3)
       //                      A[i]   = d;  // (4) | (2, 4) is not a group
       //
       // Because accesses (2) and (3) are dependent, we can group (2) with (1)
       // but not with (4). If we did, the dependent access (3) would be within
       // the boundaries of the (2, 4) group.
       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 B is a load and part of an interleave group, no earlier loads can
+        // be added to B's interleave group, because this would mean the load B
+        // would need to be moved across store A. Mark the interleave group as
+        // complete.
+        if (isInterleaved(B) && isa<LoadInst>(B)) {
+          InterleaveGroup<Instruction> *LoadGroup = getInterleaveGroup(B);
+
+          LLVM_DEBUG(dbgs() << "LV: Marking interleave group for " << *B
+                            << " as complete.\n");
+
+          CompletedLoadGroups.insert(LoadGroup);
+        }
 
         // 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
         // will only form a group with instructions that it precedes.
         break;
       }
 
       // At this point, we've checked for illegal code motion. If either A or B
       // isn't strided, there's nothing left to do.
       if (!isStrided(DesA.Stride) || !isStrided(DesB.Stride))
         continue;
 

llvm/test/Transforms/LoopVectorize/X86/interleaved-accesses-hoist-load-across-store.ll

 ; CHECK-NEXT:    [[TMP2:%.*]] = add i64 [[OFFSET_IDX]], 3
 ; CHECK-NEXT:    [[TMP3:%.*]] = add i64 [[OFFSET_IDX]], 6
 ; CHECK-NEXT:    [[TMP4:%.*]] = add i64 [[OFFSET_IDX]], 9
 ; CHECK-NEXT:    [[TMP5:%.*]] = mul i64 [[INDEX]], 3
 ; CHECK-NEXT:    [[OFFSET_IDX2:%.*]] = add i64 1, [[TMP5]]
 ; CHECK-NEXT:    [[TMP6:%.*]] = add i64 [[OFFSET_IDX2]], 0
 ; CHECK-NEXT:    [[TMP7:%.*]] = add nuw nsw i64 [[TMP6]], 4
 ; CHECK-NEXT:    [[TMP8:%.*]] = getelementptr inbounds i32, ptr [[ARR]], i64 [[TMP7]]
-; CHECK-NEXT:    [[TMP9:%.*]] = getelementptr inbounds i32, ptr [[TMP8]], i32 -2
+; CHECK-NEXT:    [[TMP9:%.*]] = getelementptr inbounds i32, ptr [[TMP8]], i32 0
 ; CHECK-NEXT:    [[WIDE_VEC:%.*]] = load <12 x i32>, ptr [[TMP9]], align 4
 ; CHECK-NEXT:    [[STRIDED_VEC:%.*]] = shufflevector <12 x i32> [[WIDE_VEC]], <12 x i32> poison, <4 x i32> <i32 0, i32 3, i32 6, i32 9>
-; CHECK-NEXT:    [[STRIDED_VEC3:%.*]] = shufflevector <12 x i32> [[WIDE_VEC]], <12 x i32> poison, <4 x i32> <i32 1, i32 4, i32 7, i32 10>
-; CHECK-NEXT:    [[STRIDED_VEC4:%.*]] = shufflevector <12 x i32> [[WIDE_VEC]], <12 x i32> poison, <4 x i32> <i32 2, i32 5, i32 8, i32 11>
 ; CHECK-NEXT:    [[TMP10:%.*]] = getelementptr inbounds i32, ptr [[ARR]], i64 [[TMP1]]
 ; CHECK-NEXT:    [[TMP11:%.*]] = getelementptr inbounds i32, ptr [[ARR]], i64 [[TMP2]]
 ; CHECK-NEXT:    [[TMP12:%.*]] = getelementptr inbounds i32, ptr [[ARR]], i64 [[TMP3]]
 ; CHECK-NEXT:    [[TMP13:%.*]] = getelementptr inbounds i32, ptr [[ARR]], i64 [[TMP4]]
-; CHECK-NEXT:    [[TMP14:%.*]] = extractelement <4 x i32> [[STRIDED_VEC4]], i32 0
+; CHECK-NEXT:    [[TMP14:%.*]] = extractelement <4 x i32> [[STRIDED_VEC]], i32 0
 ; CHECK-NEXT:    store i32 [[TMP14]], ptr [[TMP10]], align 4
-; CHECK-NEXT:    [[TMP15:%.*]] = extractelement <4 x i32> [[STRIDED_VEC4]], i32 1
+; CHECK-NEXT:    [[TMP15:%.*]] = extractelement <4 x i32> [[STRIDED_VEC]], i32 1
 ; CHECK-NEXT:    store i32 [[TMP15]], ptr [[TMP11]], align 4
-; CHECK-NEXT:    [[TMP16:%.*]] = extractelement <4 x i32> [[STRIDED_VEC4]], i32 2
+; CHECK-NEXT:    [[TMP16:%.*]] = extractelement <4 x i32> [[STRIDED_VEC]], i32 2
 ; CHECK-NEXT:    store i32 [[TMP16]], ptr [[TMP12]], align 4
-; CHECK-NEXT:    [[TMP17:%.*]] = extractelement <4 x i32> [[STRIDED_VEC4]], i32 3
+; CHECK-NEXT:    [[TMP17:%.*]] = extractelement <4 x i32> [[STRIDED_VEC]], i32 3
 ; CHECK-NEXT:    store i32 [[TMP17]], ptr [[TMP13]], align 4
-; CHECK-NEXT:    [[TMP18:%.*]] = add <4 x i32> [[STRIDED_VEC3]], [[STRIDED_VEC]]
-; CHECK-NEXT:    [[TMP19:%.*]] = extractelement <4 x i32> [[TMP18]], i32 0
-; CHECK-NEXT:    store i32 [[TMP19]], ptr [[TMP10]], align 4
-; CHECK-NEXT:    [[TMP20:%.*]] = extractelement <4 x i32> [[TMP18]], i32 1
-; CHECK-NEXT:    store i32 [[TMP20]], ptr [[TMP11]], align 4
-; CHECK-NEXT:    [[TMP21:%.*]] = extractelement <4 x i32> [[TMP18]], i32 2
-; CHECK-NEXT:    store i32 [[TMP21]], ptr [[TMP12]], align 4
-; CHECK-NEXT:    [[TMP22:%.*]] = extractelement <4 x i32> [[TMP18]], i32 3
-; CHECK-NEXT:    store i32 [[TMP22]], ptr [[TMP13]], align 4
+; CHECK-NEXT:    [[TMP18:%.*]] = add nuw nsw i64 [[TMP6]], 2
+; CHECK-NEXT:    [[TMP19:%.*]] = getelementptr inbounds i32, ptr [[ARR]], i64 [[TMP18]]
+; CHECK-NEXT:    [[TMP20:%.*]] = getelementptr inbounds i32, ptr [[TMP19]], i32 0
+; CHECK-NEXT:    [[WIDE_VEC3:%.*]] = load <12 x i32>, ptr [[TMP20]], align 4
+; CHECK-NEXT:    [[STRIDED_VEC4:%.*]] = shufflevector <12 x i32> [[WIDE_VEC3]], <12 x i32> poison, <4 x i32> <i32 0, i32 3, i32 6, i32 9>
+; CHECK-NEXT:    [[STRIDED_VEC5:%.*]] = shufflevector <12 x i32> [[WIDE_VEC3]], <12 x i32> poison, <4 x i32> <i32 1, i32 4, i32 7, i32 10>
+; CHECK-NEXT:    [[TMP21:%.*]] = add <4 x i32> [[STRIDED_VEC5]], [[STRIDED_VEC4]]
+; CHECK-NEXT:    [[TMP22:%.*]] = extractelement <4 x i32> [[TMP21]], i32 0
+; CHECK-NEXT:    store i32 [[TMP22]], ptr [[TMP10]], align 4
+; CHECK-NEXT:    [[TMP23:%.*]] = extractelement <4 x i32> [[TMP21]], i32 1
+; CHECK-NEXT:    store i32 [[TMP23]], ptr [[TMP11]], align 4
+; CHECK-NEXT:    [[TMP24:%.*]] = extractelement <4 x i32> [[TMP21]], i32 2
+; CHECK-NEXT:    store i32 [[TMP24]], ptr [[TMP12]], align 4
+; CHECK-NEXT:    [[TMP25:%.*]] = extractelement <4 x i32> [[TMP21]], i32 3
+; CHECK-NEXT:    store i32 [[TMP25]], ptr [[TMP13]], align 4
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
-; CHECK-NEXT:    [[TMP23:%.*]] = icmp eq i64 [[INDEX_NEXT]], 16
-; CHECK-NEXT:    br i1 [[TMP23]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP0:![0-9]+]]
+; CHECK-NEXT:    [[TMP26:%.*]] = icmp eq i64 [[INDEX_NEXT]], 16
+; CHECK-NEXT:    br i1 [[TMP26]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP0:![0-9]+]]
 ; CHECK:       middle.block:
-; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 17, 16
-; CHECK-NEXT:    br i1 [[CMP_N]], label [[EXIT:%.*]], label [[SCALAR_PH]]
+; CHECK-NEXT:    br label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:
 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ 49, [[MIDDLE_BLOCK]] ], [ 1, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[BC_RESUME_VAL1:%.*]] = phi i64 [ 52, [[MIDDLE_BLOCK]] ], [ 4, [[ENTRY]] ]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV_1:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_1_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[IV_2:%.*]] = phi i64 [ [[BC_RESUME_VAL1]], [[SCALAR_PH]] ], [ [[IV_2_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[IV_1_NEXT]] = add nuw nsw i64 [[IV_1]], 3
 ; CHECK-NEXT:    [[IV_1_PLUS_4:%.*]] = add nuw nsw i64 [[IV_1]], 4
 ; CHECK-NEXT:    [[GEP_IV_1_PLUS_4:%.*]] = getelementptr inbounds i32, ptr [[ARR]], i64 [[IV_1_PLUS_4]]
 ; CHECK-NEXT:    [[L1:%.*]] = load i32, ptr [[GEP_IV_1_PLUS_4]], align 4
 ; CHECK-NEXT:    [[GEP_IV_2:%.*]] = getelementptr inbounds i32, ptr [[ARR]], i64 [[IV_2]]
 ; CHECK-NEXT:    store i32 [[L1]], ptr [[GEP_IV_2]], align 4
 ; CHECK-NEXT:    [[IV_1_PLUS_2:%.*]] = add nuw nsw i64 [[IV_1]], 2
 ; CHECK-NEXT:    [[GEP_IV_1_PLUS_2:%.*]] = getelementptr inbounds i32, ptr [[ARR]], i64 [[IV_1_PLUS_2]]
 ; CHECK-NEXT:    [[L2:%.*]] = load i32, ptr [[GEP_IV_1_PLUS_2]], align 4
 ; CHECK-NEXT:    [[L3:%.*]] = load i32, ptr [[GEP_IV_2]], align 4
 ; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[L3]], [[L2]]
 ; CHECK-NEXT:    store i32 [[ADD]], ptr [[GEP_IV_2]], align 4
 ; CHECK-NEXT:    [[IV_2_NEXT]] = add nuw nsw i64 [[IV_2]], 3
 ; CHECK-NEXT:    [[ICMP:%.*]] = icmp ugt i64 [[IV_2]], 50
-; CHECK-NEXT:    br i1 [[ICMP]], label [[EXIT]], label [[LOOP]], !llvm.loop [[LOOP3:![0-9]+]]
+; CHECK-NEXT:    br i1 [[ICMP]], label [[EXIT:%.*]], label [[LOOP]], !llvm.loop [[LOOP3:![0-9]+]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop
 
 loop:
   %iv.1 = phi i64 [ 1, %entry ], [ %iv.1.next, %loop ]
   %iv.2 = phi i64 [ 4, %entry ], [ %iv.2.next, %loop ]
   %iv.1.next = add nuw nsw i64 %iv.1, 3
   %iv.1.plus.4 = add nuw nsw i64 %iv.1, 4
   %gep.iv.1.plus.4 = getelementptr inbounds i32, ptr %arr, i64 %iv.1.plus.4
   %l1 = load i32, ptr %gep.iv.1.plus.4
   %gep.iv.2 = getelementptr inbounds i32, ptr %arr, i64 %iv.2
   store i32 %l1, ptr %gep.iv.2
   %iv.1.plus.2 = add nuw nsw i64 %iv.1, 2
   %gep.iv.1.plus.2= getelementptr inbounds i32, ptr %arr, i64 %iv.1.plus.2
   %l2 = load i32, ptr %gep.iv.1.plus.2
   %l3 = load i32, ptr %gep.iv.2
   %add = add i32 %l3 , %l2
   store i32 %add, ptr %gep.iv.2
   %iv.2.next = add nuw nsw i64 %iv.2, 3
   %icmp = icmp ugt i64 %iv.2, 50
   br i1 %icmp, label %exit, label %loop
 
 exit:
   ret void
 }
-