[LoopVectorize] Check the number of uses of an FAdd before classifying as ordered

[kmclaughlin]

Summary

checkOrderedReductions looks for Phi nodes which can be classified as in-order,
meaning they can be vectorised without unsafe math. In order to vectorise the
reduction it should also be classified as in-loop by getReductionOpChain, which
checks that the reduction has two uses.

In this patch, a similar check is added to checkOrderedReductions so that we
now return false if there are more than two uses of the FAdd instruction.
This fixes PR52515.

[fhahn]

LGTM with the comment addressed

llvm/lib/Analysis/IVDescriptors.cpp

203

please use hasNUsesOrMore instead of getNumUses. hasNUsesOrMore doesn't have to traverse the full use list.

[dmgreen]

Thanks for putting together the fix.

I don't remember why the LoopExitValue needs a single user for InLoopReductions. It should have one Phi use, and only other uses outside loop, but I don't think it really needs to be a single user unless I'm missing something.

The underlying issue seems to be that AddReductionVar returns a reduction, whereas getReductionOpChain cannot find the chain. Are there more situations that could happen? Would it be better to somehow detect that getReductionOpChain will fail to find the chain?

[kmclaughlin]

In D114002#3136096, @dmgreen wrote:

The underlying issue seems to be that AddReductionVar returns a reduction, whereas getReductionOpChain cannot find the chain. Are there more situations that could happen? Would it be better to somehow detect that getReductionOpChain will fail to find the chain?

Thanks for taking a look at this, @dmgreen! I do think it would be worth checking if getReductionOpChain will fail to find the chain in AddReductionVar, so that we don't classify a reduction as ordered if it won't be found by collectInLoopReductions. I tried adding something like this to AddReductionVar, though at the point checkOrderedReduction is called we haven't created the RecurrenceDescriptor yet. I think with some refactoring it would be possible to do this, and I'm happy to follow up on this separately? For now I think this patch ensures that we are at least as strict as getReductionOpChain in terms of checking the number of uses of the FAdd.

[david-arm]

LGTM! I think this fix looks right for now, especially since it will unblock the users who reported the original issue in bugzilla. It does sound like cleaning up this area with a bit of refactoring and removing duplication would make sense though!

[dmgreen]

Yeah that sounds fine. I took another look and checkOrderedReduction is already checking for a small subset of what getReductionOpChain is testing for. It would be nice that if we fixed getReductionOpChain to not require a single user it would just work without extra changes, but it's simple enough to fix both places.

llvm/lib/Analysis/IVDescriptors.cpp

 // Check if a given Phi node can be recognized as an ordered reduction for
 // vectorizing floating point operations without unsafe math.
 static bool checkOrderedReduction(RecurKind Kind, Instruction *ExactFPMathInst,
                                   Instruction *Exit, PHINode *Phi) {
   // Currently only FAdd is supported
   if (Kind != RecurKind::FAdd)
     return false;
 
-  if (Exit->getOpcode() != Instruction::FAdd || Exit != ExactFPMathInst)
+  // Ensure the exit instruction is an FAdd, and that it only has one user
+  // other than the reduction PHI
+  if (Exit->getOpcode() != Instruction::FAdd || Exit->hasNUsesOrMore(3) ||
+      Exit != ExactFPMathInst)
     return false;
 
   // The only pattern accepted is the one in which the reduction PHI
   // is used as one of the operands of the exit instruction
   auto *LHS = Exit->getOperand(0);
   auto *RHS = Exit->getOperand(1);
   if (LHS != Phi && RHS != Phi)
     return false;

llvm/test/Transforms/LoopVectorize/AArch64/strict-fadd.ll

loop:
   %ec = icmp eq i32 %iv.next, 0
   br i1 %ec, label %exit, label %loop, !llvm.loop !13
 
 exit:
   %res = phi double [ %red.next, %loop ]
   ret double %res
 }
 
+; We should not mark the fadd as an ordered reduction here as there are
+; more than 2 uses of the instruction
+define float @fadd_multiple_use(i64 %n) {
+; CHECK-ORDERED-LABEL: @fadd_multiple_use
+; CHECK-ORDERED-LABEL-NOT: vector.body
+
+; CHECK-UNORDERED-LABEL: @fadd_multiple_use
+; CHECK-UNORDERED-LABEL-NOT: vector.body
+
+; CHECK-NOT-VECTORIZED-LABEL: @fadd_multiple_use
+; CHECK-NOT-VECTORIZED-NOT: vector.body
+entry:
+  br label %for.body
+
+for.body:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next2, %bb2 ]
+  %red = phi float [ 0.0, %entry ], [ %fadd, %bb2 ]
+  %phi1 = phi i64 [ 0, %entry ], [ %iv.next, %bb2 ]
+  %fadd = fadd float %red, 1.000000e+00
+  %iv.next = add nsw i64 %phi1, 1
+  %cmp = icmp ult i64 %iv, %n
+  br i1 %cmp, label %bb2, label %bb1
+
+bb1:
+  %phi2 = phi float [ %fadd, %for.body ]
+  ret float %phi2
+
+bb2:
+  %iv.next2 = add nuw nsw i64 %iv, 1
+  br i1 false, label %for.end, label %for.body
+
+for.end:
+  %phi3 = phi float [ %fadd, %bb2 ]
+  ret float %phi3
+}
+
 !0 = distinct !{!0, !5, !9, !11}
 !1 = distinct !{!1, !5, !10, !11}
 !2 = distinct !{!2, !6, !9, !11}
 !3 = distinct !{!3, !7, !9, !11, !12}
 !4 = distinct !{!4, !8, !10, !11}
 !5 = !{!"llvm.loop.vectorize.width", i32 8}
 !6 = !{!"llvm.loop.vectorize.width", i32 4}
 !7 = !{!"llvm.loop.vectorize.width", i32 2}
 !8 = !{!"llvm.loop.vectorize.width", i32 1}
 !9 = !{!"llvm.loop.interleave.count", i32 1}
 !10 = !{!"llvm.loop.interleave.count", i32 4}
 !11 = !{!"llvm.loop.vectorize.enable", i1 true}
 !12 = !{!"llvm.loop.vectorize.predicate.enable", i1 true}
 !13 = distinct !{!13, !6, !9, !11}