[LoopVectorize] Only check for ordered reductions if the op chain was found

[kmclaughlin]

Summary

As we cannot vectorise strict reductions if the reduction is not also
classified as in-loop, we should not call checkOrderedReductions
if getReductionOpChain was not able to find the chain.

This removes the additional check on the number of uses of Exit in
checkOrderedReductions introduced in D114002, added to fix an issue
where IsOrdered was true but the reduction op chain was not found.

[david-arm]

The patch looks good to me @kmclaughlin! I just had one suggestion about maybe leaving the function where it was before.

llvm/lib/Analysis/IVDescriptors.cpp

206

Maybe it's better to leave this function where it was originally so that it's easier to see what's changed? It seems to be just the declaration that's different I think?

[kmclaughlin]

• Moved getReductionOpChain back to the original location in IVDescriptors.cpp

[david-arm]

llvm/lib/Analysis/IVDescriptors.cpp

1041

nit: Thanks for addressing my previous comment - it looks a lot neater now and easier to review. :) Given that RecurrenceDescriptor now has both getReductionOpChain and getReductionChain functions, is it worth renaming getReductionOpChain to something like findReductionOpChain?

1087

Sorry I missed this before - perhaps this change shouldn't be part of this patch because it looks like it may be adding new cases that aren't being tested for correctness?

[kmclaughlin]

• Renamed getReductionOpChain -> findReductionOpChain
• Added !LoopExitInstr->hasNUses(2) back into findReductionOpChain

[david-arm]

LGTM! Thanks for addressing my comments @kmclaughlin. :)

llvm/lib/Analysis/IVDescriptors.cpp

1041–1043

nit: Could you fix the formatting before merging? Thanks!

[fhahn]

It sounds like this fixes an issue, is it possible to have a test?

[fhahn]

Or is it NFC?

[kmclaughlin]

Hi @fhahn, there was a test added in D114002 which covers the changes here. This is just a follow up from some discussion on that patch.

llvm/include/llvm/Analysis/IVDescriptors.h

 class RecurrenceDescriptor {
 public:
   RecurrenceDescriptor() = default;
 
   RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurKind K,
                        FastMathFlags FMF, Instruction *ExactFP, Type *RT,
                        bool Signed, bool Ordered,
                        SmallPtrSetImpl<Instruction *> &CI,
+                       SmallVectorImpl<Instruction *> &RdxChain,
                        unsigned MinWidthCastToRecurTy)
       : StartValue(Start), LoopExitInstr(Exit), Kind(K), FMF(FMF),
         ExactFPMathInst(ExactFP), RecurrenceType(RT), IsSigned(Signed),
         IsOrdered(Ordered),
         MinWidthCastToRecurrenceType(MinWidthCastToRecurTy) {
     CastInsts.insert(CI.begin(), CI.end());
+    ReductionChain.assign(RdxChain);
   }
 
   /// This POD struct holds information about a potential recurrence operation.
   class InstDesc {
   public:
     InstDesc(bool IsRecur, Instruction *I, Instruction *ExactFP = nullptr)
         : IsRecurrence(IsRecur), PatternLastInst(I),
           RecKind(RecurKind::None), ExactFPMathInst(ExactFP) {}
public:
   /// Returns the type of the recurrence. This type can be narrower than the
   /// actual type of the Phi if the recurrence has been type-promoted.
   Type *getRecurrenceType() const { return RecurrenceType; }
 
   /// Returns a reference to the instructions used for type-promoting the
   /// recurrence.
   const SmallPtrSet<Instruction *, 8> &getCastInsts() const { return CastInsts; }
 
+  /// If found, returns the chain of operations from Phi to LoopExitInst that
+  /// can be treated as a set of reduction instructions for in-loop reductions.
+  const SmallVector<Instruction *, 4> &getReductionChain() const {
+    return ReductionChain;
+  }
+
   /// Returns the minimum width used by the recurrence in bits.
   unsigned getMinWidthCastToRecurrenceTypeInBits() const {
     return MinWidthCastToRecurrenceType;
   }
 
   /// Returns true if all source operands of the recurrence are SExtInsts.
   bool isSigned() const { return IsSigned; }
 
   /// Expose an ordered FP reduction to the instance users.
   bool isOrdered() const { return IsOrdered; }
 
   /// Attempts to find a chain of operations from Phi to LoopExitInst that can
   /// be treated as a set of reductions instructions for in-loop reductions.
-  SmallVector<Instruction *, 4> getReductionOpChain(PHINode *Phi,
-                                                    Loop *L) const;
+  static SmallVector<Instruction *, 4> getReductionOpChain(PHINode *OrigPhi, Loop *L,
+                                                           Instruction *LoopExitInstr,
+                                                           unsigned RedOp);
 
   /// Returns true if the instruction is a call to the llvm.fmuladd intrinsic.
   static bool isFMulAddIntrinsic(Instruction *I) {
     return isa<IntrinsicInst>(I) &&
            cast<IntrinsicInst>(I)->getIntrinsicID() == Intrinsic::fmuladd;
   }
 
 private:
private:
   // True if all source operands of the recurrence are SExtInsts.
   bool IsSigned = false;
   // True if this recurrence can be treated as an in-order reduction.
   // Currently only a non-reassociative FAdd can be considered in-order,
   // if it is also the only FAdd in the PHI's use chain.
   bool IsOrdered = false;
   // Instructions used for type-promoting the recurrence.
   SmallPtrSet<Instruction *, 8> CastInsts;
+  // The chain of operations between the reduction Phi and the exit instruction.
+  SmallVector<Instruction *, 4> ReductionChain;
   // The minimum width used by the recurrence.
   unsigned MinWidthCastToRecurrenceType;
 };
 
 /// A struct for saving information about induction variables.
 class InductionDescriptor {
 public:
   /// This enum represents the kinds of inductions that we support.

llvm/lib/Analysis/IVDescriptors.cpp

while (!Worklist.empty()) {
     // we haven't yet visited.
     for (Value *O : cast<User>(Val)->operands())
       if (auto *I = dyn_cast<Instruction>(O))
         if (TheLoop->contains(I) && !Visited.count(I))
           Worklist.push_back(I);
   }
 }
 
 // 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 and FMulAdd are supported.
   if (Kind != RecurKind::FAdd && Kind != RecurKind::FMulAdd)
     return false;
 
   if (Kind == RecurKind::FAdd && Exit->getOpcode() != Instruction::FAdd)
     return false;
 
   if (Kind == RecurKind::FMulAdd &&
       !RecurrenceDescriptor::isFMulAddIntrinsic(Exit))
     return false;
 
-  // Ensure the exit instruction has only one user other than the reduction PHI
-  if (Exit != ExactFPMathInst || Exit->hasNUsesOrMore(3))
+  if (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 *Op0 = Exit->getOperand(0);
   auto *Op1 = Exit->getOperand(1);
   if (Kind == RecurKind::FAdd && Op0 != Phi && Op1 != Phi)
     return false;
if (isMinMaxRecurrenceKind(Kind) && NumCmpSelectPatternInst != 2 &&
     return false;
 
   if (isSelectCmpRecurrenceKind(Kind) && NumCmpSelectPatternInst != 1)
     return false;
 
   if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
     return false;
 
-  const bool IsOrdered = checkOrderedReduction(
-      Kind, ReduxDesc.getExactFPMathInst(), ExitInstruction, Phi);
+  SmallVector<Instruction *, 4> ReductionChain;
+  ReductionChain =
+      getReductionOpChain(Phi, TheLoop, ExitInstruction, getOpcode(Kind));
+
+  bool IsOrdered = false;
+  if (!ReductionChain.empty())
+    IsOrdered = checkOrderedReduction(Kind, ReduxDesc.getExactFPMathInst(),
+                                      ExitInstruction, Phi);
 
   if (Start != Phi) {
     // If the starting value is not the same as the phi node, we speculatively
     // looked through an 'and' instruction when evaluating a potential
     // arithmetic reduction to determine if it may have been type-promoted.
     //
     // We now compute the minimal bit width that is required to represent the
     // reduction. If this is the same width that was indicated by the 'and', we
bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurKind Kind,
   // only have a single instruction with out-of-loop users.
 
   // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
   // is saved as part of the RecurrenceDescriptor.
 
   // Save the description of this reduction variable.
   RecurrenceDescriptor RD(RdxStart, ExitInstruction, Kind, FMF,
                           ReduxDesc.getExactFPMathInst(), RecurrenceType,
-                          IsSigned, IsOrdered, CastInsts,
+                          IsSigned, IsOrdered, CastInsts, ReductionChain,
                           MinWidthCastToRecurrenceType);
   RedDes = RD;
 
   return true;
 }
 
 // We are looking for loops that do something like this:
 //   int r = 0;
unsigned RecurrenceDescriptor::getOpcode(RecurKind Kind) {
   case RecurKind::FMin:
   case RecurKind::SelectFCmp:
     return Instruction::FCmp;
   default:
     llvm_unreachable("Unknown recurrence operation");
   }
 }
 
 SmallVector<Instruction *, 4>
-RecurrenceDescriptor::getReductionOpChain(PHINode *Phi, Loop *L) const {
+RecurrenceDescriptor::getReductionOpChain(PHINode *Phi, Loop *L,
+                                          Instruction *LoopExitInstr,
+                                          unsigned RedOp) {
   SmallVector<Instruction *, 4> ReductionOperations;
-  unsigned RedOp = getOpcode(Kind);
 
   // Search down from the Phi to the LoopExitInstr, looking for instructions
   // with a single user of the correct type for the reduction.
 
   // Note that we check that the type of the operand is correct for each item in
   // the chain, including the last (the loop exit value). This can come up from
   // sub, which would otherwise be treated as an add reduction. MinMax also need
   // to check for a pair of icmp/select, for which we use getNextInstruction and
auto isCorrectOpcode = [&](Instruction *Cur) {
 
     return Cur->getOpcode() == RedOp;
   };
 
   // The loop exit instruction we check first (as a quick test) but add last. We
   // check the opcode is correct (and dont allow them to be Subs) and that they
   // have expected to have the expected number of uses. They will have one use
   // from the phi and one from a LCSSA value, no matter the type.
-  if (!isCorrectOpcode(LoopExitInstr) || !LoopExitInstr->hasNUses(2))
+  if (!isCorrectOpcode(LoopExitInstr))
     return {};
 
   // Check that the Phi has one (or two for min/max) uses.
   if (!Phi->hasNUses(ExpectedUses))
     return {};
   Instruction *Cur = getNextInstruction(Phi);
 
   // Each other instruction in the chain should have the expected number of uses

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

if (!PreferInLoopReductions && !useOrderedReductions(RdxDesc) &&
         !TTI.preferInLoopReduction(Opcode, Phi->getType(),
                                    TargetTransformInfo::ReductionFlags()))
       continue;
 
     // Check that we can correctly put the reductions into the loop, by
     // finding the chain of operations that leads from the phi to the loop
     // exit value.
     SmallVector<Instruction *, 4> ReductionOperations =
-        RdxDesc.getReductionOpChain(Phi, TheLoop);
+        RdxDesc.getReductionChain();
     bool InLoop = !ReductionOperations.empty();
     if (InLoop) {
       InLoopReductionChains[Phi] = ReductionOperations;
       // Add the elements to InLoopReductionImmediateChains for cost modelling.
       Instruction *LastChain = Phi;
       for (auto *I : ReductionOperations) {
         InLoopReductionImmediateChains[I] = LastChain;
         LastChain = I;