[LV] Try to sink users recursively for first-order recurrences.

[fhahn]

Summary

Update isFirstOrderRecurrence to explore all uses of a recurrence phi
and check if we can sink them. If there are multiple users to sink, they
are all mapped to the previous instruction.

Fixes PR44286 (and another PR or two).

[fhahn]

ping

[xbolva00]

https://godbolt.org/z/nXCxW8

This should help to vectorize this code as well, or?

[fhahn]

In D84951#2219722, @xbolva00 wrote:

https://godbolt.org/z/nXCxW8

This should help to vectorize this code as well, or?

I think the unidentified PHI node in the example above is a pointer induction, not a first order recurrence? Looks like the actual problem is that LV only sees the inner loop fully unrolled and the SLP vectorizer does not vectorize the body of the unrolled loop. If built with -fno-unroll-loops, LV will vectorize the inner loop, but it would probably be better if the SLP vectorizer can just vectorize the unrolled body.

[bmahjour]

llvm/lib/Analysis/IVDescriptors.cpp

703

update comment

[xbolva00]

Does this patch improve some public benchmarks?

[fhahn]

Rebased, updated comment, added additional tests.

In D84951#2281155, @xbolva00 wrote:

Does this patch improve some public benchmarks?

It does not really impact the number of vectorized loops in SPEC2000/SPEC2006/MultiSource. But I think it should have a strictly positive impact (module exposing some existing cost model limitations due to vectorizing more complex loops).

[xbolva00]

Cool, great!

[xbolva00]

Any futher comments, @bmahjour?

[bmahjour]

In D84951#2310611, @xbolva00 wrote:

Any futher comments, @bmahjour?

Nope, I'm fine with the changes.

[xbolva00]

In D84951#2312281, @bmahjour wrote:

In D84951#2310611, @xbolva00 wrote:

Any futher comments, @bmahjour?

Nope, I'm fine with the changes.

So probably ok to land this now..

[xbolva00]

In D84951#2312281, @bmahjour wrote:

In D84951#2310611, @xbolva00 wrote:

Any futher comments, @bmahjour?

Nope, I'm fine with the changes.

Can you accept it formally?

[bmahjour]

Sorry, I meant to do a more thorough review before approving. I had a closer look today and found some nits and a couple of questions. Please see inline comments.

llvm/lib/Analysis/IVDescriptors.cpp

705–706

nit: this comment is not describing the lambda that follows it.

755

We need to make sure we don't visit the same user (from the UserWorkList) multiple times. For example if we have a hypothetical scenario where:

%0 = phi [..., %3], [...]
%1 = phi [...], [Previous] ; The "Phi" that seeds the algorithm.
%2 = add %1, %0
%3 = add %2, 1
<Previous>
...

... but I guess that's handled because worklist is actually a set-like container so if we try to add a user that already exists in the worklist, the insertion won't take place and the size of the worklist is unaffected. Could you please put a comment about the choice of the container and how the algorithm guarantees termination?

761–764

users of Previous -> users of Phi

llvm/test/Transforms/LoopVectorize/first-order-recurrence-complex.ll

287

The comment implies that all phi nodes prevent sinking, but I think here the reason %first_time.1 cannot be sunk past %for.next is because (one of) the user(s) of %first_time.1 is the Previous itself. If that's correct, can we say "some phi nodes"?

294

remove or update the comment after ; (here and on lines 300, 303 and 306)

[xbolva00]

Reping. Rebase?

[fhahn]

Rebased and addressed comments, thanks!

A blast from the past :)

[Ayal]

How about making SinkAfter a MapVector instead of DenseMap (to have its iteration order match insertion order) and insert interdependent sink candidates in the desired order?
How about traversing all insns from phi to previous, in order, checking if any is using the phi or a prior insn that was sunk? E.g., by maintaining the set of their users.
This might be clearer, and avoid the sorting.

[fhahn]

Rebased, update to also avoid sinking instructions that may read from memory, as we cannot move them over ones with side-effects, move sort to isFirstOrderRecurrence.

In D84951#2753861, @Ayal wrote:

How about making SinkAfter a MapVector instead of DenseMap (to have its iteration order match insertion order) and insert interdependent sink candidates in the desired order?
How about traversing all insns from phi to previous, in order, checking if any is using the phi or a prior insn that was sunk? E.g., by maintaining the set of their users.
This might be clearer, and avoid the sorting.

I'm not sure if it is possible to maintain the order by dominance in the map as we go along, because we an instruction could be used by multiple others and we may visit them in reverse dominance order (relative to each other), so we would miss the fact we need to 'fix' the order of the first instruction. I think it is also difficult & expensive to change the order of multiple entries in the map vector.

I added a few more interesting scenarios as tests in 68d52f0dbe2e and c62f984814c4.

I *think* however it should be enough to sort only sort the instructions to sink per FOR phi, as we currently allow sinking for each instruction only once. That should certainly be better, as we have less to sort overall and everything is contained in IVDescriptor.cpp. The new code already maintains a vector of instructions to sink, so the sort fits in quite nicely. WDYT?

[Ayal]

In D84951#2760659, @fhahn wrote:

Rebased, update to also avoid sinking instructions that may read from memory, as we cannot move them over ones with side-effects, move sort to isFirstOrderRecurrence.

In D84951#2753861, @Ayal wrote:

How about making SinkAfter a MapVector instead of DenseMap (to have its iteration order match insertion order) and insert interdependent sink candidates in the desired order?
How about traversing all insns from phi to previous, in order, checking if any is using the phi or a prior insn that was sunk? E.g., by maintaining the set of their users.
This might be clearer, and avoid the sorting.

I'm not sure if it is possible to maintain the order by dominance in the map as we go along, because we an instruction could be used by multiple others and we may visit them in reverse dominance order (relative to each other), so we would miss the fact we need to 'fix' the order of the first instruction. I think it is also difficult & expensive to change the order of multiple entries in the map vector.

I added a few more interesting scenarios as tests in 68d52f0dbe2e and c62f984814c4.

I *think* however it should be enough to sort only sort the instructions to sink per FOR phi, as we currently allow sinking for each instruction only once. That should certainly be better, as we have less to sort overall and everything is contained in IVDescriptor.cpp. The new code already maintains a vector of instructions to sink, so the sort fits in quite nicely. WDYT?

The instructions to sink reside inside the header block in the desired order. It should be possible to traverse them, once, from the FOR phi to the terminator or Previous, w/o sorting nor changing order, by maintaining the set of phi's (direct and indirect) users. When encountering such a user during the traversal, check if it is sunkable, append it to be moved after the last sunken user (or after Previous if this is the first user being sunk), and add its users to the set - those that belong to the header block, others need to be dominated by (and distinct from) Previous.
Perhaps this would also help support sinking memory instructions in the future.
Sounds reasonable?

[fhahn]

In D84951#2776110, @Ayal wrote:

The instructions to sink reside inside the header block in the desired order. It should be possible to traverse them, once, from the FOR phi to the terminator or Previous, w/o sorting nor changing order, by maintaining the set of phi's (direct and indirect) users. When encountering such a user during the traversal, check if it is sunkable, append it to be moved after the last sunken user (or after Previous if this is the first user being sunk), and add its users to the set - those that belong to the header block, others need to be dominated by (and distinct from) Previous.
Perhaps this would also help support sinking memory instructions in the future.
Sounds reasonable?

IIUC your suggestion would require to iterate over the instructions in the header block compared to just traversing the def-use chains from the PHI we are analyzing as we do at the moment? That would work, as we would visit the candidates in the correct order. But requiring to potentially iterate over all instructions in the header block might be worse in practice than sorting the (probably few) instructions that require sinking?

It will be indeed required once we want to sink memory operations, but until then it seems to me that just traversing the def-use chains + sorting would probably be less work in general for the cases we currently support (also given the interface that requires us to analyze each FOR separately). Please let me know if I understood correctly. Happy to update the patch as suggested if you think it's beneficial on its own.

[Ayal]

In D84951#2777544, @fhahn wrote:

In D84951#2776110, @Ayal wrote:

The instructions to sink reside inside the header block in the desired order. It should be possible to traverse them, once, from the FOR phi to the terminator or Previous, w/o sorting nor changing order, by maintaining the set of phi's (direct and indirect) users. When encountering such a user during the traversal, check if it is sunkable, append it to be moved after the last sunken user (or after Previous if this is the first user being sunk), and add its users to the set - those that belong to the header block, others need to be dominated by (and distinct from) Previous.
Perhaps this would also help support sinking memory instructions in the future.
Sounds reasonable?

IIUC your suggestion would require to iterate over the instructions in the header block compared to just traversing the def-use chains from the PHI we are analyzing as we do at the moment? That would work, as we would visit the candidates in the correct order. But requiring to potentially iterate over all instructions in the header block might be worse in practice than sorting the (probably few) instructions that require sinking?

It will be indeed required once we want to sink memory operations, but until then it seems to me that just traversing the def-use chains + sorting would probably be less work in general for the cases we currently support (also given the interface that requires us to analyze each FOR separately). Please let me know if I understood correctly. Happy to update the patch as suggested if you think it's beneficial on its own.

Happy to go with your sorting InstrsToSink approach, added some comments to it below.

Right, this order-preserving alternative requires iterating over the instructions in the header block from the FOR phi until its last header-block-user is encountered. Agree that this would probably take longer than sorting InstrsToSink, e.g., if there's a user close to the end of the header. Mainly pointed out as an alternative, towards supporting sinking memory instructions (supporting multiple FOR phi's would be possible in a single scan, but seems an overkill), and as a response to

I'm not sure if it is possible to maintain the order by dominance in the map as we go along...

;-)

llvm/lib/Analysis/IVDescriptors.cpp

707

The candidates need to be maintained in a set in order to avoid considering them repeatedly. May as well have this set ordered by dominance relation, instead of sorting it at the end.
E.g., let UserWorkList be a SmallVector that is pushed and popped until empty, where candidates are checked to be sunkable when being pushed into it (instead of when being popped/traversed), after successfully inserting them into the sorted InstrsToSink set. WDYT?

732

This sounds right, given that we only consider I's that post-dominate the FOR phi.
Seems somewhat odd though, calls for an assert and a testcase.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7439–7451

Sort multiple users in reverse instead of reversing all here?
Or rather - have them sink after each other instead of all sinking after Previous, thereby expressing their desired order and dependencies directly?

llvm/test/Transforms/LoopVectorize/first-order-recurrence-complex.ll

287

The (first) reason %first_time.1 cannot be sunk is because it appears outside the header and is not dominated by Previous. The fact that it feeds Previous is a second sinking-preventing reason.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7439–7451

(BTW, note that by having multiple users sink after each other, it is also possible to reorder them lazily instead of sorting: when moving Sink after Target, check if Target should also be sunk - and if so sink it first, recursively, while taking care to sink each SinkAfter instruction once. Multiple users is the only exception to sinking an instruction after a Target that should itself sink.)

[fhahn]

Address latest comments: Use ordered set for instructions to sink, entries in SinkAfter are chained together now as well, instead of all sinking after the same 'previous' instruction. I hope I did not miss anything.

[fhahn]

Adjust worklist logic.

[fhahn]

llvm/lib/Analysis/IVDescriptors.cpp

707

I updated the code to use a ordered set for InstrToSink as suggested. I think the only thing is that we might check the same instruction multiple times, if it is already dominated by Previous. In that case, it won't get inserted into InstrToSink. But I think that should be fine.

732

I think there's already a test case where this can happen: @sink_into_replication_region. I added an assert that the instruction must be in the same BB as the starting phi.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7439–7451

I went with Or rather - have them sink after each other instead of all sinking after Previous, thereby expressing their desired order and dependencies directly

The dependencies are chained together in SinkAfter now. But keeping them sorted to start with seems simpler overall and ensures that map is accurate. WDYT?

llvm/test/Transforms/LoopVectorize/first-order-recurrence-complex.ll

287

Good point, I adjusted the comment.

[Ayal]

llvm/lib/Analysis/IVDescriptors.cpp

759

Perhaps the logic could be simplified somewhat, compressed to see it all together here:

WorkList = { Phi }
while WorkList not empty {
  Insn = pop from WorkList
  for (User *User : Insn->users()) {
    // Cyclic dependence
    if (Previous == User)
      return false;
    // No need to sink User
    if (DT->dominates(Previous, User) ||
        isa<PHINode>(User))
      continue;
    // Cannot sink User
    if ((User->getParent() != PhiBB) ||
        User->mayHaveSideEffects() ||
        User->mayReadFromMemory() ||
        (User->getParent()->getTerminator() == User) ||
        (SinkAfter.find(User) != SinkAfter.end()))
      return false;
    // Sink User tentatively and check its users
    if InstsToSink.insert(User)
      append User to Worklist
  }
}

[fhahn]

Simplify/compact code as suggested.

[fhahn]

llvm/lib/Analysis/IVDescriptors.cpp

759

Thanks! I adjusted/compacted the code as suggested, but with keeping the check if the instruction has been sunk already and the assertion is UserI is a PHINode.

[Ayal]

llvm/lib/Analysis/IVDescriptors.cpp

707

Agreed. We could cache/memoize a set of confirmed users in addition to InstrToSink, but their re-confirmation should be quick, and reaching users multiple times is probably infrequent.

716

Assert they have a common parent (as done by comesBefore())?
If sorting should work (somehow) across basic blocks, better enumerate them somehow, otherwise both A < B and A > B may both hold.

719

Indeed, better check this first, than check last if insertion fails!

730

The isa<PHInode> case belongs here, with the "we're fine with UserI's current position" case.
(The property we're really after here is conditional dominance: Previous dominates UserI conditional on having reached FOR Phi)

732

Agreed. (Nice test, where an add accumulating the FOR phi is sunk after a previous udiv, and the fact that the add feeds its reduction header phi is fine.)

744

// We cannot [sink] user.

747

While we're here, simply check !UserI->isTerminator()?
Worth retaining the uninformative comment?

748

Would be good to retain the TODO comment about supporting sinking a user after multiple (deepest) previouses.

749

Relevant if isa<PHINode> is moved above.
If it stays here, it's redundant, as we bailed-out earlier if UserI is not in PhiBB.

762

Suffice to provide each User of Current to TryToPushSinkableUser[s](), i.e., how about doing

for (User *User : Current->users())
  if (!TryToPushSinkableUser(cast<Instruction>(User)))
    return false;

to simplify the lambda?

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7439–7451

Agreed. The map itself is accurate whether sorted or not in this case, but lazy reordering may potentially enter an infinite loop (if buggy), and requires marking sunk instructions. Given that a set is needed to ensure uniqueness, it may as well provide the desired order, as done above.

[fhahn]

Address latest comments, thanks!

llvm/lib/Analysis/IVDescriptors.cpp

716

This is needed so we conveniently check if arbitrary instructions are in the set, but those instructions should never be inserted. But I can change it to only query the set for instructions in the same BB. (comesBefore already asserts that they are in the same BB)

730

At this point we don't know if the PHI is in the same block or not. (checked only below). We may incorrectly skip a PHI node in a different BB, which is not dominated by Previous (tested in cannot_sink_phi in first-order-recurrence-complex.ll). I left the check at it's original place, so it only takes place after we ensure that the parents match.

744

removed the whole comment.

747

Updated & comment removed.

748

Sounds good. I split off the SinkAfter check again, so it's clear which single check the comment refers to.

749

As mentioned above, I think the check needs to happen after we checked that they are in the same BB. I added the assert to catch inconsistencies if the code is moved, but it's not too helpful. I removed it.

[Ayal]

This looks good to me, thanks!
Title might emphasize "[LV] Try to sink multiple users ..."
Noting another couple of TODO thoughts.

llvm/lib/Analysis/IVDescriptors.cpp

716

Ah, ok.
Another potential TODO is to sink users in non-header basic blocks that post-dominate the header, which may extend CompareByComesBefore to distinct blocks using their domination.

730

Ah, right; cannot_sink_phi may be one case where Previous needs to be hoisted before a user, instead of vice versa, assuming no other reorder-preventing reasons exist...

llvm/include/llvm/Analysis/IVDescriptors.h

static bool isReductionPHI(PHINode *Phi, Loop *TheLoop,
                              DominatorTree *DT = nullptr);
 
   /// Returns true if Phi is a first-order recurrence. A first-order recurrence
   /// is a non-reduction recurrence relation in which the value of the
   /// recurrence in the current loop iteration equals a value defined in the
   /// previous iteration. \p SinkAfter includes pairs of instructions where the
   /// first will be rescheduled to appear after the second if/when the loop is
   /// vectorized. It may be augmented with additional pairs if needed in order
-  /// to handle Phi as a first-order recurrence.
+  /// to handle Phi as a first-order recurrence. \p SinkAfter can contain
+  /// multiple instructions to sink after the same instruction. Clients have to
+  /// ensure the relative ordering of those instructions is preserved when
+  /// moving those instructions.
   static bool
   isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop,
                          DenseMap<Instruction *, Instruction *> &SinkAfter,
                          DominatorTree *DT);
 
   RecurrenceKind getRecurrenceKind() { return Kind; }
 
   MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; }

llvm/lib/Analysis/IVDescriptors.cpp

bool RecurrenceDescriptor::isFirstOrderRecurrence(
   if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous) ||
       SinkAfter.count(Previous)) // Cannot rely on dominance due to motion.
     return false;
 
   // Ensure every user of the phi node is dominated by the previous value.
   // The dominance requirement ensures the loop vectorizer will not need to
   // vectorize the initial value prior to the first iteration of the loop.
   // TODO: Consider extending this sinking to handle memory instructions and
   // phis with multiple users.
 
   // Returns true, if all users of I are dominated by DominatedBy.
-  auto allUsesDominatedBy = [DT](Instruction *I, Instruction *DominatedBy) {
-    return all_of(I->uses(), [DT, DominatedBy](Use &U) {
-      return DT->dominates(DominatedBy, U);
-    });
+  SetVector<Instruction *> UserWorkList;
+  auto PushUsers = [&UserWorkList](Instruction *I) {
+    for (User *User : I->users())
+      UserWorkList.insert(cast<Instruction>(User));
   };
 
-  if (Phi->hasOneUse()) {
-    Instruction *I = Phi->user_back();
-
+  // We optimistically assume we can sink all users after Previous. Keep list of
+  // instructions to sink after Previous. It will be applied to SinkAfter if all
+  // users can be sunk.
+  SmallVector<Instruction *, 4> InstrsToSink;
+  // Try to sink instruction I after Previous. Queue users of I for further
+  // processin in UserWorkList.
+  auto TryToSinkUser = [&](Instruction *I) {
     // If the user of the PHI is also the incoming value, we potentially have a
     // reduction and which cannot be handled by sinking.
     if (Previous == I)
       return false;
 
+    if (DT->dominates(Previous, I)) // We already are good w/o sinking.
+      return true;
+
     // We cannot sink terminator instructions.
     if (I->getParent()->getTerminator() == I)
       return false;
 
+    // If we reach a PHI node that is not dominated by Previous, we reached a
+    // header PHI. No need for sinking.
+    if (isa<PHINode>(I))
+      return true;
+
+    if (I->getParent() != Phi->getParent() || I->mayHaveSideEffects())
+      return false;
+
     // Do not try to sink an instruction multiple times (if multiple operands
     // are first order recurrences).
     // TODO: We can support this case, by sinking the instruction after the
     // 'deepest' previous instruction.
     if (SinkAfter.find(I) != SinkAfter.end())
       return false;
 
-    if (DT->dominates(Previous, I)) // We already are good w/o sinking.
-      return true;
+    // We can sink I after Previous, if all users can also be sunk or are
+    // dominated by Previous.
+    InstrsToSink.push_back(I);
+    PushUsers(I);
+  };
+  PushUsers(Phi);
 
-    // We can sink any instruction without side effects, as long as all users
-    // are dominated by the instruction we are sinking after.
-    if (I->getParent() == Phi->getParent() && !I->mayHaveSideEffects() &&
-        allUsesDominatedBy(I, Previous)) {
-      SinkAfter[I] = Previous;
-      return true;
-    }
+  // Try to recursively sink instructions and their users after Previous.
+  for (unsigned I = 0; I < UserWorkList.size(); ++I) {
+    Instruction *Current = UserWorkList[I];
+    if (!TryToSinkUser(Current))
+      return false;
   }
 
-  return allUsesDominatedBy(Phi, Previous);
+  // We can sink all users of Previous. Update the mapping.
+  for (Instruction *I : InstrsToSink)
+    SinkAfter[I] = Previous;
+  return true;
 }
 
 /// This function returns the identity element (or neutral element) for
 /// the operation K.
 Constant *RecurrenceDescriptor::getRecurrenceIdentity(RecurrenceKind K,
                                                       Type *Tp) {
   switch (K) {
   case RK_IntegerXor:

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
   delete PreEntry;
 
   // ---------------------------------------------------------------------------
   // Transform initial VPlan: Apply previously taken decisions, in order, to
   // bring the VPlan to its final state.
   // ---------------------------------------------------------------------------
 
   // Apply Sink-After legal constraints.
-  for (auto &Entry : SinkAfter) {
+  // Multiple instructions can be marked for sinking after the same instruction.
+  // Convert map to a vector of pairs and sort them by the reverse order of the
+  // original IR. That way the instructions that dominate others are inserted
+  // after them and they will come before instructions dominated by them, due to
+  // using moveAfter.
+  SmallVector<std::pair<Instruction *, Instruction *>, 4> SinkAfterV;
+  for (auto &Entry : SinkAfter)
+    SinkAfterV.emplace_back(Entry.first, Entry.second);
+  sort(SinkAfterV, [](const std::pair<Instruction *, Instruction *> &A,
+                      const std::pair<Instruction *, Instruction *> &B) {
+    return B.first->comesBefore(A.first);
+  });
+  for (auto &Entry : SinkAfterV) {
     VPRecipeBase *Sink = RecipeBuilder.getRecipe(Entry.first);
     VPRecipeBase *Target = RecipeBuilder.getRecipe(Entry.second);
     Sink->moveAfter(Target);
   }
 
   // Interleave memory: for each Interleave Group we marked earlier as relevant
   // for this VPlan, replace the Recipes widening its memory instructions with a
   // single VPInterleaveRecipe at its insertion point.

llvm/test/Transforms/LoopVectorize/first-order-recurrence-complex.ll

for:
   %iv.next = add nuw nsw i64 %iv, 1
   %exitcond = icmp eq i64 %iv.next, 2000
   br i1 %exitcond, label %exit, label %for
 
 exit:
   ret void
 }
 
-; FIXME: Currently we can only sink a single instruction. For the example below,
-;        we also have to sink users.
-define void @cannot_sink_with_additional_user(i32 %x, i32* %ptr, i64 %tc) {
-; CHECK-LABEL: define void @cannot_sink_with_additional_user(
-; CHECK-NEXT: entry:
-; CHECK-NEXT:   br label %preheader
+; Sink users of %pre.phi recursively.
+define void @can_sink_with_additional_user(i32 %x, i32* %ptr, i64 %tc) {
+; CHECK-LABEL: define void @can_sink_with_additional_user(
 
-; CHECK-LABEL: preheader:                                        ; preds = %entry
-; CHECK:  br label %for
-
-; CHECK-LABEL: for:                                              ; preds = %for, %preheader
-; CHECK:  br i1 %exitcond, label %exit, label %for
+; CHECK-LABEL: vector.ph:
+; CHECK-NEXT:    %broadcast.splatinsert = insertelement <4 x i32> undef, i32 %x, i32 0
+; CHECK-NEXT:    %broadcast.splat = shufflevector <4 x i32> %broadcast.splatinsert, <4 x i32> undef, <4 x i32> zeroinitializer
+; CHECK-NEXT:    %vector.recur.init = insertelement <4 x i32> undef, i32 %.pre, i32 3
+; CHECK-NEXT:    br label %vector.body
 
-; CHECK-LABEL: exit:
-; CHECK-NEXT:    ret void
+; CHECK-LABEL: vector.body:
+; CHECK-NEXT:    %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
+; CHECK-NEXT:    %vector.recur = phi <4 x i32> [ %vector.recur.init, %vector.ph ], [ %wide.load, %vector.body ]
+; CHECK-NEXT:    %offset.idx = add i64 1, %index
+; CHECK-NEXT:    %0 = add i64 %offset.idx, 0
+; CHECK-NEXT:    %1 = getelementptr inbounds [257 x i32], [257 x i32]* @p, i64 0, i64 %0
+; CHECK-NEXT:    %2 = getelementptr inbounds i32, i32* %1, i32 0
+; CHECK-NEXT:    %3 = bitcast i32* %2 to <4 x i32>*
+; CHECK-NEXT:    %wide.load = load <4 x i32>, <4 x i32>* %3, align 4
+; CHECK-NEXT:    %4 = shufflevector <4 x i32> %vector.recur, <4 x i32> %wide.load, <4 x i32> <i32 3, i32 4, i32 5, i32 6>
+; CHECK-NEXT:    %5 = add <4 x i32> %4, %broadcast.splat
+; CHECK-NEXT:    %6 = add <4 x i32> %5, %broadcast.splat
+; CHECK-NEXT:    %7 = add <4 x i32> %5, %wide.load
+; CHECK-NEXT:    %8 = add <4 x i32> %6, %7
+; CHECK-NEXT:    %9 = getelementptr inbounds [257 x i32], [257 x i32]* @q, i64 0, i64 %0
+; CHECK-NEXT:    %10 = getelementptr inbounds i32, i32* %9, i32 0
+; CHECK-NEXT:    %11 = bitcast i32* %10 to <4 x i32>*
+; CHECK-NEXT:    store <4 x i32> %8, <4 x i32>* %11, align 4
+; CHECK-NEXT:    %index.next = add i64 %index, 4
+; CHECK-NEXT:    %12 = icmp eq i64 %index.next, 1996
+; CHECK-NEXT:    br i1 %12, label %middle.block, label %vector.body, !llvm.loop !6
 
 entry:
   br label %preheader
 
 preheader:
   %idx.phi.trans = getelementptr inbounds [257 x i32], [257 x i32]* @p, i64 0, i64 1
   %.pre = load i32, i32* %idx.phi.trans, align 4
   br label %for
bb13:                                             ; preds = %bb13, %bb
   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
   %tmp49 = load float, float* undef, align 4
   %tmp60 = load float, float* undef, align 4
   %tmp12 = icmp slt i64 %indvars.iv, undef
   br i1 %tmp12, label %bb13, label %bb74
 
 bb74:                                             ; preds = %bb13
   ret void
 }

llvm/test/Transforms/LoopVectorize/first-order-recurrence.ll

for.end:
   ret void
 }
 
 ; void no_sink_after(short *a, int n, int *b) {
 ;   for(int i = 0; i < n; i++)
 ;     b[i] = ((a[i] + 2) * a[i + 1]);
 ; }
 ;
-; NO-SINK-AFTER-LABEL: no_sink_after
-; NO-SINK-AFTER-NOT:   vector.ph:
-; NO-SINK-AFTER:       }
+; SINK-AFTER-LABEL:  @sink_after_with_multiple_users
+; SINK-AFTER-LABEL:  vector.ph:
+; SINK-AFTER-NEXT:    %n.mod.vf = urem i64 %n, 4
+; SINK-AFTER-NEXT:    %n.vec = sub i64 %n, %n.mod.vf
+; SINK-AFTER-NEXT:    %vector.recur.init = insertelement <4 x i16> undef, i16 %.pre, i32 3
+; SINK-AFTER-NEXT:    br label %vector.body
+
+; SINK-AFTER-LABEL:  vector.body:
+; SINK-AFTER-NEXT:    %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
+; SINK-AFTER-NEXT:    %vector.recur = phi <4 x i16> [ %vector.recur.init, %vector.ph ], [ %wide.load, %vector.body ]
+; SINK-AFTER-NEXT:    %1 = add i64 %index, 0
+; SINK-AFTER-NEXT:    %2 = add nuw nsw i64 %1, 1
+; SINK-AFTER-NEXT:    %3 = getelementptr inbounds i16, i16* %a, i64 %2
+; SINK-AFTER-NEXT:    %4 = getelementptr inbounds i16, i16* %3, i32 0
+; SINK-AFTER-NEXT:    %5 = bitcast i16* %4 to <4 x i16>*
+; SINK-AFTER-NEXT:    %wide.load = load <4 x i16>, <4 x i16>* %5, align 2, !alias.scope !43
+; SINK-AFTER-NEXT:    %6 = shufflevector <4 x i16> %vector.recur, <4 x i16> %wide.load, <4 x i32> <i32 3, i32 4, i32 5, i32 6>
+; SINK-AFTER-NEXT:    %7 = sext <4 x i16> %6 to <4 x i32>
+; SINK-AFTER-NEXT:    %8 = add nsw <4 x i32> %7, <i32 2, i32 2, i32 2, i32 2>
+; SINK-AFTER-NEXT:    %9 = sext <4 x i16> %wide.load to <4 x i32>
+; SINK-AFTER-NEXT:    %10 = mul nsw <4 x i32> %8, %9
+; SINK-AFTER-NEXT:    %11 = getelementptr inbounds i32, i32* %b, i64 %1
+; SINK-AFTER-NEXT:    %12 = getelementptr inbounds i32, i32* %11, i32 0
+; SINK-AFTER-NEXT:    %13 = bitcast i32* %12 to <4 x i32>*
+; SINK-AFTER-NEXT:    store <4 x i32> %10, <4 x i32>* %13, align 4, !alias.scope !46, !noalias !43
+; SINK-AFTER-NEXT:    %index.next = add i64 %index, 4
+; SINK-AFTER-NEXT:    %14 = icmp eq i64 %index.next, %n.vec
+; SINK-AFTER-NEXT:    br i1 %14, label %middle.block, label %vector.body, !llvm.loop !48
 ;
-define void @no_sink_after(i16* %a, i32* %b, i64 %n) {
+define void @sink_after_with_multiple_users(i16* %a, i32* %b, i64 %n) {
 entry:
   %.pre = load i16, i16* %a
   br label %for.body
 
 for.body:
   %0 = phi i16 [ %.pre, %entry ], [ %1, %for.body ]
   %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
   %conv = sext i16 %0 to i32

 ; SINK-AFTER-NEXT:    %1 = zext <4 x i16> %0 to <4 x i32>
 ; SINK-AFTER-NEXT:    %2 = shufflevector <4 x i32> %vector.recur2, <4 x i32> %1, <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 ; SINK-AFTER-NEXT:    %3 = add <4 x i16> %0, <i16 5, i16 5, i16 5, i16 5>
 ; SINK-AFTER-NEXT:    %4 = shufflevector <4 x i16> %vector.recur, <4 x i16> %3, <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 ; SINK-AFTER-NEXT:    %5 = sub <4 x i16> %4, <i16 10, i16 10, i16 10, i16 10>
 ; SINK-AFTER-NEXT:    %index.next = add i32 %index, 4
 ; SINK-AFTER-NEXT:    %vec.ind.next = add <4 x i16> %vec.ind, <i16 4, i16 4, i16 4, i16 4>
 ; SINK-AFTER-NEXT:    %6 = icmp eq i32 %index.next, 40
-; SINK-AFTER-NEXT:    br i1 %6, label %middle.block, label %vector.body, !llvm.loop !43
+; SINK-AFTER-NEXT:    br i1 %6, label %middle.block, label %vector.body, !llvm.loop !50
 ;
 entry:
   br label %for.cond
 
 for.cond:
   %iv = phi i16 [ -27, %entry ], [ %iv.next, %for.cond ]
   %rec.1 = phi i16 [ 0, %entry ], [ %rec.1.prev, %for.cond ]
   %rec.2 = phi i32 [ -27, %entry ], [ %rec.2.prev, %for.cond ]