[IVDescriptors] Before moving an instruction in SinkAfter checking if it is target of other instructions

[Carrot]

Summary

The attached test case can cause LLVM crash in buildVPlanWithVPRecipes because invalid VPlan is generated.

FIRST-ORDER-RECURRENCE-PHI ir<%792> = phi ir<%501>, ir<%806>
CLONE ir<%804> = fdiv ir<1.000000e+00>, vp<%17>      // use of %17
CLONE ir<%806> = load ir<%805>
EMIT vp<%17> = first-order splice ir<%792> ir<%806>   // def of %17
...

There is a use before def error on %17.

When vectorizer generates a VPlan, it generates a "first-order splice" instruction for a loop carried variable after its definition. All related PHI users are changed to use this "first-order splice" result, and are moved after it. The move is guided by a MapVector SinkAfter. And the content of SinkAfter is filled by RecurrenceDescriptor::isFixedOrderRecurrence.

Let's look at the first PHI and related instructions

%v792 = phi double [ %v806, %Loop ], [ %d1, %Entry ]
%v802 = fdiv double %v794, %v792
%v804 = fdiv double 1.000000e+00, %v792
%v806 = load double, ptr %v805, align 8

%v806 is a loop carried variable, %v792 is related PHI instruction. 
Vectorizer will generated a new "first-order splice" instruction 
for %v806, and it will be used by %v802 and %v804. So %v802 and %v804 
will be moved after %v806 and its "first-order splice" instruction.
So SinkAfter contains

   %v802   ->  %v806
   %v804   ->  %v802

It means %v802 should be moved after %v806 and %v804 will be moved 
after %v802. Please pay attention that the order is important.

When isFixedOrderRecurrence processing PHI instruction %v794, related
instructions are

  %v793 = phi double [ %v813, %Loop ], [ %d1, %Entry ]
  %v794 = phi double [ %v793, %Loop ], [ %d2, %Entry ]
  %v802 = fdiv double %v794, %v792
  %v813 = load double, ptr %v812, align 8

This time its related loop carried variable is %v813, its user is %v802.
So %v802 should also be moved after %v813. But %v802 is already in 
SinkAfter, because %v813 is later than %v806, so the original %v802 entry
in SinkAfter is deleted, a new %v802 entry is added. Now SinkAfter contains

   %v804   ->  %v802
   %v802   ->  %v813

With these data, %v802 can still be moved after all its operands, but %v804
can't be moved after %v806 and its "first-order splice" instruction. And 
causes use before def error.

So when remove/re-insert an instruction I in SinkAfter, we should also recursively remove instructions targeting I and re-insert them into SinkAfter. But for simplicity I just bail out in this case.

[fhahn]

Thanks for the patch! This should fix an issue also mentioned at D119661

llvm/lib/Analysis/IVDescriptors.cpp

1037

Simpler to use any_of?, as in

if (any_of(SinkAfter, [SinkCandidate](const std::pair<Instruction *, Instruction *> &P) {
      return P.second == SinkCandidate;
           }))

llvm/test/Transforms/LoopVectorize/sinkafter.ll

3 ↗

(On Diff #460889)

The existing tests for higher-order recurrences are in llvm/test/Transforms/LoopVectorize/first-order-recurrence-chains.ll. Could you move your test there as well?

To improve readability, the IR tests there try to use descriptive names, like %for.1 for recurrence phis, %iv for indications and so on. It would be good to try to update the names here to make the test easier to read, rather than using auto-generated names.

Also, @aeubanks posted a simpler test case in the comments for D119661, which may be good to use.

[tvvikram]

LGTM, thanks!

[fhahn]

LGTM, thanks!

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

644

Please use ; CHECK-NOT: vector.body: to make sure this isn't vectorized

666

nit: stray new line.

[Carrot]

Thanks for the review.
I will check in this version.

llvm/lib/Analysis/IVDescriptors.cpp

if (It != SinkAfter.end()) {
       // Bail out if order has not been preserved.
       if (OtherPrev != It->second && !DT->dominates(It->second, OtherPrev))
         return false;
 
       // SinkCandidate is already being sunk after an instruction after
       // Previous. Nothing left to do.
       if (DT->dominates(Previous, OtherPrev) || Previous == OtherPrev)
         return true;
+
+      // If there are other instructions to be sunk after SinkCandidate, remove
+      // and re-insert SinkCandidate can break those instructions. Bail out for
+      // simplicity.
+      if (any_of(SinkAfter,
+          [SinkCandidate](const std::pair<Instruction *, Instruction *> &P) {
+            return P.second == SinkCandidate;
+          }))
+        return false;
+
       // Otherwise, Previous comes after OtherPrev and SinkCandidate needs to be
       // re-sunk to Previous, instead of sinking to OtherPrev. Remove
       // SinkCandidate from SinkAfter to ensure it's insert position is updated.
       SinkAfter.erase(SinkCandidate);
     }
 
     // If we reach a PHI node that is not dominated by Previous, we reached a
     // header PHI. No need for sinking.

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

loop:
   store ptr %ptr.iv, ptr %gep.ptr
   %ptr.iv.next = getelementptr i32, ptr %ptr.iv, i64 1
   %exitcond.not = icmp eq i64 %iv.next, 1000
   br i1 %exitcond.not, label %exit, label %loop
 
 exit:
   ret void
 }
+
+; Make sure LLVM doesn't generate wrong data in SinkAfter, and causes crash in
+; loop vectorizer.
+define void @test_crash(ptr %p) {
+; CHECK-LABEL: @test_crash
+; CHECK-NOT:   vector.body:
+; CHECK:       ret
+Entry:
+  br label %Loop
+
+Loop:
+  %for.1 = phi double [ %iv1, %Loop ], [ 0.000000e+00, %Entry ]
+  %for.2 = phi double [ %iv2, %Loop ], [ 0.000000e+00, %Entry ]
+  %for.3 = phi double [ %for.2, %Loop ], [ 0.000000e+00, %Entry ]
+  %for.4 = phi i64 [ %count, %Loop ], [ 0, %Entry ]
+  %USE_2_INDVARS = fdiv double %for.3, %for.1
+  %div = fdiv double 0.000000e+00, %for.1
+  %iv1 = load double, ptr null, align 8
+  %count = add nuw nsw i64 %for.4, 1
+  %iv2 = load double, ptr null, align 8
+  store double %div, ptr %p, align 8
+  %cond = icmp eq i64 %count, 0
+  br i1 %cond, label %End, label %Loop
+
+End:
+  ret void
+}