[AArch64] Add legalizations for VECREDUCE_SEQ_FADD

[cameron.mcinally]

Summary

Continuing from D89162...

I think I stumbled across the motivation for the ExpandReductions pass. If we wait until Legalization to expand the ordered reductions, we end up with suboptimal code for illegal types. And it's pretty bad. We could end up with O(n/2) extra operations.

A good example of this can be seen in @test_v3f32 from vecreduce-fadd-legalization-strict.ll. Here we end up with 4 FADDs, instead of the 3 FADDs required. The newly added FADD is the result of widening the illegal v3f32 vector type to v4f32, where the newly added element in the reduction is the "neutral" value, 0.0.

Question is... should we be optimizing for exceptional cases? Eh, probably not IMHO. But I could see users filing bug reports for the extra operations. What does everyone else think?

[*Also note that I decided to turn these new legalizations on for NEON, and not just SVE. NEON had a number of existing tests, so it made sense to reuse them. And I'm still missing legalization support for some other actions, like SoftenFloat and PromoteFloat. I did not find existing tests for those actions.*]

[nikic]

A good example of this can be seen in @test_v3f32 from vecreduce-fadd-legalization-strict.ll. Here we end up with 4 FADDs, instead of the 3 FADDs required. The newly added FADD is the result of widening the illegal v3f32 vector type to v4f32, where the newly added element in the reduction is the "neutral" value, 0.0.

Looking at https://github.com/llvm/llvm-project/blob/5a3ef55a524bf9e072d98286e5febdb218b1fc72/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp#L7477-L7480, shouldn't this just be a matter of using -0.0 as the neutral element instead? If 0.0 is not actually neutral here, then this is not just suboptimal, it's incorrect. (We should fix this for the non-sequential case as well.)

And I'm still missing legalization support for some other actions, like SoftenFloat and PromoteFloat. I did not find existing tests for those actions.

Copying llvm/test/CodeGen/ARM/vecreduce-fadd-legalization-soft-float.ll without the fast fmf should work as test coverage for that.

[cameron.mcinally]

In D90247#2357013, @nikic wrote:

A good example of this can be seen in @test_v3f32 from vecreduce-fadd-legalization-strict.ll. Here we end up with 4 FADDs, instead of the 3 FADDs required. The newly added FADD is the result of widening the illegal v3f32 vector type to v4f32, where the newly added element in the reduction is the "neutral" value, 0.0.

Looking at https://github.com/llvm/llvm-project/blob/5a3ef55a524bf9e072d98286e5febdb218b1fc72/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp#L7477-L7480, shouldn't this just be a matter of using -0.0 as the neutral element instead? If 0.0 is not actually neutral here, then this is not just suboptimal, it's incorrect. (We should fix this for the non-sequential case as well.)

@spatel

Yup, good catch. The (-0.0+0.0 -> +0.0) case is a problem. The identity should be -0.0.

And I'm still missing legalization support for some other actions, like SoftenFloat and PromoteFloat. I did not find existing tests for those actions.

Copying llvm/test/CodeGen/ARM/vecreduce-fadd-legalization-soft-float.ll without the fast fmf should work as test coverage for that.

Ok, I can build that out. Are we okay with the suboptimal legalization though? I'll wait for that decision before putting more time into this.

Or does anyone see a clever fix for the illegal type legalization? It looks like we lost information during widening, so I'm not sure we can get it back in a non-hacky way.

[nikic]

Ok, I can build that out. Are we okay with the suboptimal legalization though? I'll wait for that decision before putting more time into this.

Or does anyone see a clever fix for the illegal type legalization? It looks like we lost information during widening, so I'm not sure we can get it back in a non-hacky way.

Not sure I follow. If the neutral element is fixed, then the extra fadds should also get folded away. Or is there some additional sub-optimality here?

[cameron.mcinally]

In D90247#2357093, @nikic wrote:

Ok, I can build that out. Are we okay with the suboptimal legalization though? I'll wait for that decision before putting more time into this.

Or does anyone see a clever fix for the illegal type legalization? It looks like we lost information during widening, so I'm not sure we can get it back in a non-hacky way.

Not sure I follow. If the neutral element is fixed, then the extra fadds should also get folded away. Or is there some additional sub-optimality here?

Ah, I follow now. Didn't catch the connection...

[cameron.mcinally]

Update 'neutral' element to -0.0.

@nikic, I don't see llvm/test/CodeGen/AArch64/vecreduce-fadd-legalization-soft-float.ll. Is that a test file you have downstream? Or is it just missing for AArch64/?

[cameron.mcinally]

Ah, I see it in ARM/. That will work...

[spatel]

In D90247#2357013, @nikic wrote:

Looking at https://github.com/llvm/llvm-project/blob/5a3ef55a524bf9e072d98286e5febdb218b1fc72/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp#L7477-L7480, shouldn't this just be a matter of using -0.0 as the neutral element instead? If 0.0 is not actually neutral here, then this is not just suboptimal, it's incorrect. (We should fix this for the non-sequential case as well.)

Agree - looks like the -0.0 was missed in D58015. Note that we have semi-redundant logic for this sort of thing in IR with ConstantExpr::getBinOpIdentity(), so we should confirm that everything is lined up and/or try to consolidate code.

[cameron.mcinally]

Comment from ARM/ARMISelLowering.cpp:

// Custom Expand smaller than legal vector reductions to prevent false zero
// items being added.
setOperationAction(ISD::VECREDUCE_FADD, MVT::v4f16, Custom);

So it will probably take some work to truly unwind the 0.0 neutral element code. Just FYI...

[dmgreen]

In D90247#2357606, @cameron.mcinally wrote:

Comment from ARM/ARMISelLowering.cpp:

// Custom Expand smaller than legal vector reductions to prevent false zero
// items being added.
setOperationAction(ISD::VECREDUCE_FADD, MVT::v4f16, Custom);

Those are for MVE. Maybe try NEON instead?

[cameron.mcinally]

Updated patch with, I think, all the needed legalizations.

This patch touches both the ARM and AArch64 backends, to exercise all the different legalizations. If this is too much to review in one patch, we might want to split it up into two Diffs, even if there's a small window of unsupported legalizations in the wild. It should be relatively safe to split.

Also note that my confidence in the softening test changes is low. E.g. @test_v4f32_strict. Is it obvious to anyone if the new instruction sequences are bad?

[nikic]

llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.h

711

Looks like there is no definition for this method. There's probably no way to test it (requires X86), but I'd suggest to still include it, as the implementation is the same as the other soft float legalization. I'd also be fine with not having it, in which case this declaration should be dropped as well.

llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp

826

As this is a recurring pattern, I have extracted an ISD::getVecReduceBaseOpcode() function that does this. Please add VECREDUCE_SEQ_FADD there and then use it here and in expansion.

4908

Again, this is a recurring pattern, so I have extracted a SelectionDAG::getNeutralElement() API for this. The invocation should be:

SDValue NeutralElem = DAG.getNeutralElement(
    ISD::getVecReduceBaseOpcode(N->getOpcode()), dl, ElemVT, Flags);

[cameron.mcinally]

Update patch based on @nikic's comments...

llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.h

711

Implemented.

llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp

4908

I improvised a little here for readability. Is that okay with you, @nikic?

Although, I wonder if getting the BaseOpc is a necessary step here. Did you consider just adding VECREDUCE_* cases to DAG.getNeutralElement(...)?

[nikic]

LGTM with the default action adjusted...

llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp

4908

I improvised a little here for readability. Is that okay with you, @nikic?

Sure!

Although, I wonder if getting the BaseOpc is a necessary step here. Did you consider just adding VECREDUCE_* cases to DAG.getNeutralElement(...)?

Not strictly necessary, but I personally found it a bit more elegant to not repeat the full VECREDUCE list another time here.

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

929

Rather than explicitly marking them as expanded in targets, VECREDUCE_SEQ_FADD should be marked as default expanded using the list at https://github.com/llvm/llvm-project/blob/aa1c6b79878475d61c90c0d4c2af17312242f18e/llvm/lib/CodeGen/TargetLoweringBase.cpp#L722, to stay consistent with other VECREDUCE opcodes.

[cameron.mcinally]

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

929

Oh, cool. Didn't know that list existed. Thanks.

llvm/include/llvm/CodeGen/TargetLowering.h

   /// expansion was successful and populates the Result and Overflow arguments.
   bool expandMULO(SDNode *Node, SDValue &Result, SDValue &Overflow,
                   SelectionDAG &DAG) const;
 
   /// Expand a VECREDUCE_* into an explicit calculation. If Count is specified,
   /// only the first Count elements of the vector are used.
   SDValue expandVecReduce(SDNode *Node, SelectionDAG &DAG) const;
 
+  /// Expand a VECREDUCE_SEQ_* into an explicit ordered calculation.
+  SDValue expandVecReduceSeq(SDNode *Node, SelectionDAG &DAG) const;
+
   /// Expand an SREM or UREM using SDIV/UDIV or SDIVREM/UDIVREM, if legal.
   /// Returns true if the expansion was successful.
   bool expandREM(SDNode *Node, SDValue &Result, SelectionDAG &DAG) const;
 
   //===--------------------------------------------------------------------===//
   // Instruction Emitting Hooks
   //
 

llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

#endif
   case ISD::VECREDUCE_SMIN:
   case ISD::VECREDUCE_UMAX:
   case ISD::VECREDUCE_UMIN:
   case ISD::VECREDUCE_FMAX:
   case ISD::VECREDUCE_FMIN:
     Action = TLI.getOperationAction(
         Node->getOpcode(), Node->getOperand(0).getValueType());
     break;
+  case ISD::VECREDUCE_SEQ_FADD:
+    Action = TLI.getOperationAction(
+        Node->getOpcode(), Node->getOperand(1).getValueType());
+    break;
   default:
     if (Node->getOpcode() >= ISD::BUILTIN_OP_END) {
       Action = TargetLowering::Legal;
     } else {
       Action = TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0));
     }
     break;
   }

llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.h

private:
   SDValue SoftPromoteHalfRes_FP_ROUND(SDNode *N);
   SDValue SoftPromoteHalfRes_LOAD(SDNode *N);
   SDValue SoftPromoteHalfRes_SELECT(SDNode *N);
   SDValue SoftPromoteHalfRes_SELECT_CC(SDNode *N);
   SDValue SoftPromoteHalfRes_UnaryOp(SDNode *N);
   SDValue SoftPromoteHalfRes_XINT_TO_FP(SDNode *N);
   SDValue SoftPromoteHalfRes_UNDEF(SDNode *N);
   SDValue SoftPromoteHalfRes_VECREDUCE(SDNode *N);
 
   bool SoftPromoteHalfOperand(SDNode *N, unsigned OpNo);
   SDValue SoftPromoteHalfOp_BITCAST(SDNode *N);
   SDValue SoftPromoteHalfOp_FCOPYSIGN(SDNode *N, unsigned OpNo);
   SDValue SoftPromoteHalfOp_FP_EXTEND(SDNode *N);
   SDValue SoftPromoteHalfOp_FP_TO_XINT(SDNode *N);
   SDValue SoftPromoteHalfOp_SETCC(SDNode *N);
   SDValue SoftPromoteHalfOp_SELECT_CC(SDNode *N, unsigned OpNo);
   SDValue SoftPromoteHalfOp_STORE(SDNode *N, unsigned OpNo);
private:
   SDValue ScalarizeVecOp_CONCAT_VECTORS(SDNode *N);
   SDValue ScalarizeVecOp_EXTRACT_VECTOR_ELT(SDNode *N);
   SDValue ScalarizeVecOp_VSELECT(SDNode *N);
   SDValue ScalarizeVecOp_VSETCC(SDNode *N);
   SDValue ScalarizeVecOp_STORE(StoreSDNode *N, unsigned OpNo);
   SDValue ScalarizeVecOp_FP_ROUND(SDNode *N, unsigned OpNo);
   SDValue ScalarizeVecOp_STRICT_FP_ROUND(SDNode *N, unsigned OpNo);
   SDValue ScalarizeVecOp_VECREDUCE(SDNode *N);
+  SDValue ScalarizeVecOp_VECREDUCE_SEQ(SDNode *N);
 
   //===--------------------------------------------------------------------===//
   // Vector Splitting Support: LegalizeVectorTypes.cpp
   //===--------------------------------------------------------------------===//
 
   /// Given a processed vector Op which was split into vectors of half the size,
   /// this method returns the halves. The first elements of Op coincide with the
   /// elements of Lo; the remaining elements of Op coincide with the elements of
private:
   void SplitVecRes_VECTOR_SHUFFLE(ShuffleVectorSDNode *N, SDValue &Lo,
                                   SDValue &Hi);
   void SplitVecRes_VAARG(SDNode *N, SDValue &Lo, SDValue &Hi);
 
   // Vector Operand Splitting: <128 x ty> -> 2 x <64 x ty>.
   bool SplitVectorOperand(SDNode *N, unsigned OpNo);
   SDValue SplitVecOp_VSELECT(SDNode *N, unsigned OpNo);
   SDValue SplitVecOp_VECREDUCE(SDNode *N, unsigned OpNo);
+  SDValue SplitVecOp_VECREDUCE_SEQ(SDNode *N);
   SDValue SplitVecOp_UnaryOp(SDNode *N);
   SDValue SplitVecOp_TruncateHelper(SDNode *N);
 
   SDValue SplitVecOp_BITCAST(SDNode *N);
   SDValue SplitVecOp_EXTRACT_SUBVECTOR(SDNode *N);
   SDValue SplitVecOp_EXTRACT_VECTOR_ELT(SDNode *N);
   SDValue SplitVecOp_ExtVecInRegOp(SDNode *N);
   SDValue SplitVecOp_STORE(StoreSDNode *N, unsigned OpNo);
private:
   SDValue WidenVecOp_MSCATTER(SDNode* N, unsigned OpNo);
   SDValue WidenVecOp_SETCC(SDNode* N);
   SDValue WidenVecOp_STRICT_FSETCC(SDNode* N);
   SDValue WidenVecOp_VSELECT(SDNode *N);
 
   SDValue WidenVecOp_Convert(SDNode *N);
   SDValue WidenVecOp_FCOPYSIGN(SDNode *N);
   SDValue WidenVecOp_VECREDUCE(SDNode *N);
+  SDValue WidenVecOp_VECREDUCE_SEQ(SDNode *N);
 
   /// Helper function to generate a set of operations to perform
   /// a vector operation for a wider type.
   ///
   SDValue UnrollVectorOp_StrictFP(SDNode *N, unsigned ResNE);
 
   //===--------------------------------------------------------------------===//
   // Vector Widening Utilities Support: LegalizeVectorTypes.cpp

llvm/lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp

#include "llvm/IR/ConstrainedOps.def"
   case ISD::SDIVFIXSAT:
   case ISD::UDIVFIX:
   case ISD::UDIVFIXSAT: {
     unsigned Scale = Node->getConstantOperandVal(2);
     Action = TLI.getFixedPointOperationAction(Node->getOpcode(),
                                               Node->getValueType(0), Scale);
     break;
   }
-  case ISD::VECREDUCE_SEQ_FADD:
-    Action = TLI.getOperationAction(Node->getOpcode(),
-                                    Node->getOperand(1).getValueType());
-    break;
   case ISD::SINT_TO_FP:
   case ISD::UINT_TO_FP:
   case ISD::VECREDUCE_ADD:
   case ISD::VECREDUCE_MUL:
   case ISD::VECREDUCE_AND:
   case ISD::VECREDUCE_OR:
   case ISD::VECREDUCE_XOR:
   case ISD::VECREDUCE_SMAX:
   case ISD::VECREDUCE_SMIN:
   case ISD::VECREDUCE_UMAX:
   case ISD::VECREDUCE_UMIN:
   case ISD::VECREDUCE_FADD:
   case ISD::VECREDUCE_FMUL:
   case ISD::VECREDUCE_FMAX:
   case ISD::VECREDUCE_FMIN:
     Action = TLI.getOperationAction(Node->getOpcode(),
                                     Node->getOperand(0).getValueType());
     break;
+  case ISD::VECREDUCE_SEQ_FADD:
+    Action = TLI.getOperationAction(Node->getOpcode(),
+                                    Node->getOperand(1).getValueType());
+    break;
   }
 
   LLVM_DEBUG(dbgs() << "\nLegalizing vector op: "; Node->dump(&DAG));
 
   SmallVector<SDValue, 8> ResultVals;
   switch (Action) {
   default: llvm_unreachable("This action is not supported yet!");
   case TargetLowering::Promote:
#include "llvm/IR/ConstrainedOps.def"
   case ISD::VECREDUCE_UMAX:
   case ISD::VECREDUCE_UMIN:
   case ISD::VECREDUCE_FADD:
   case ISD::VECREDUCE_FMUL:
   case ISD::VECREDUCE_FMAX:
   case ISD::VECREDUCE_FMIN:
     Results.push_back(TLI.expandVecReduce(Node, DAG));
     return;
+  case ISD::VECREDUCE_SEQ_FADD:
+    Results.push_back(TLI.expandVecReduceSeq(Node, DAG));
+    return;
   case ISD::SREM:
   case ISD::UREM:
     ExpandREM(Node, Results);
     return;
   }
 
   Results.push_back(DAG.UnrollVectorOp(Node));
 }

llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp

#endif
     case ISD::VECREDUCE_SMAX:
     case ISD::VECREDUCE_SMIN:
     case ISD::VECREDUCE_UMAX:
     case ISD::VECREDUCE_UMIN:
     case ISD::VECREDUCE_FMAX:
     case ISD::VECREDUCE_FMIN:
       Res = ScalarizeVecOp_VECREDUCE(N);
       break;
+    case ISD::VECREDUCE_SEQ_FADD:
+      Res = ScalarizeVecOp_VECREDUCE_SEQ(N);
+      break;
     }
   }
 
   // If the result is null, the sub-method took care of registering results etc.
   if (!Res.getNode()) return false;
 
   // If the result is N, the sub-method updated N in place.  Tell the legalizer
   // core about this.

 SDValue DAGTypeLegalizer::ScalarizeVecOp_VECREDUCE(SDNode *N) {
   SDValue Res = GetScalarizedVector(N->getOperand(0));
   // Result type may be wider than element type.
   if (Res.getValueType() != N->getValueType(0))
     Res = DAG.getNode(ISD::ANY_EXTEND, SDLoc(N), N->getValueType(0), Res);
   return Res;
 }
 
+SDValue DAGTypeLegalizer::ScalarizeVecOp_VECREDUCE_SEQ(SDNode *N) {
+  SDValue AccOp = N->getOperand(0);
+  SDValue VecOp = N->getOperand(1);
+  SDNodeFlags Flags = N->getFlags();
+
+  unsigned BaseOpc = 0;
+  switch (N->getOpcode()) {
+  default:
+#ifndef NDEBUG
+    dbgs() << "WidenVectorOp: ";
+    N->dump(&DAG);
+    dbgs() << "\n";
+#endif
+    report_fatal_error("Do not know how to widen this operator!\n");
+  case ISD::VECREDUCE_SEQ_FADD:
+    BaseOpc = ISD::FADD;
+    break;
+  }
+
+  SDValue Op = GetScalarizedVector(VecOp);
+  return DAG.getNode(BaseOpc, SDLoc(N), N->getValueType(0),
+                     AccOp, Op, Flags);
+}
+
 //===----------------------------------------------------------------------===//
 //  Result Vector Splitting
 //===----------------------------------------------------------------------===//
 
 /// This method is called when the specified result of the specified node is
 /// found to need vector splitting. At this point, the node may also have
 /// invalid operands or may have other results that need legalization, we just
 /// know that (at least) one result needs vector splitting.
#endif
     case ISD::VECREDUCE_SMAX:
     case ISD::VECREDUCE_SMIN:
     case ISD::VECREDUCE_UMAX:
     case ISD::VECREDUCE_UMIN:
     case ISD::VECREDUCE_FMAX:
     case ISD::VECREDUCE_FMIN:
       Res = SplitVecOp_VECREDUCE(N, OpNo);
       break;
+    case ISD::VECREDUCE_SEQ_FADD:
+      Res = SplitVecOp_VECREDUCE_SEQ(N);
+      break;
     }
   }
 
   // If the result is null, the sub-method took care of registering results etc.
   if (!Res.getNode()) return false;
 
   // If the result is N, the sub-method updated N in place.  Tell the legalizer
   // core about this.
SDValue DAGTypeLegalizer::SplitVecOp_VECREDUCE(SDNode *N, unsigned OpNo) {
   }
 
   // Use the appropriate scalar instruction on the split subvectors before
   // reducing the now partially reduced smaller vector.
   SDValue Partial = DAG.getNode(CombineOpc, dl, LoOpVT, Lo, Hi, N->getFlags());
   return DAG.getNode(N->getOpcode(), dl, ResVT, Partial, N->getFlags());
 }
 
+SDValue DAGTypeLegalizer::SplitVecOp_VECREDUCE_SEQ(SDNode *N) {
+  EVT ResVT = N->getValueType(0);
+  SDValue Lo, Hi;
+  SDLoc dl(N);
+
+  SDValue AccOp = N->getOperand(0);
+  SDValue VecOp = N->getOperand(1);
+  EVT VecVT = VecOp.getValueType();
+  assert(VecVT.isVector() && "Can only split reduce vector operand");
+  GetSplitVector(VecOp, Lo, Hi);
+  EVT LoOpVT, HiOpVT;
+  std::tie(LoOpVT, HiOpVT) = DAG.GetSplitDestVTs(VecVT);
+
+  // Reduce low half.
+  SDValue Partial = DAG.getNode(N->getOpcode(), dl, ResVT,
+                                AccOp, Lo, N->getFlags());
+
+  // Reduce high half, using low half result as initial value.
+  return DAG.getNode(N->getOpcode(), dl, ResVT, Partial, Hi, N->getFlags());
+}
+
 SDValue DAGTypeLegalizer::SplitVecOp_UnaryOp(SDNode *N) {
   // The result has a legal vector type, but the input needs splitting.
   EVT ResVT = N->getValueType(0);
   SDValue Lo, Hi;
   SDLoc dl(N);
   GetSplitVector(N->getOperand(N->isStrictFPOpcode() ? 1 : 0), Lo, Hi);
   EVT InVT = Lo.getValueType();
 
#endif
   case ISD::VECREDUCE_SMAX:
   case ISD::VECREDUCE_SMIN:
   case ISD::VECREDUCE_UMAX:
   case ISD::VECREDUCE_UMIN:
   case ISD::VECREDUCE_FMAX:
   case ISD::VECREDUCE_FMIN:
     Res = WidenVecOp_VECREDUCE(N);
     break;
+  case ISD::VECREDUCE_SEQ_FADD:
+    Res = WidenVecOp_VECREDUCE_SEQ(N);
+    break;
   }
 
   // If Res is null, the sub-method took care of registering the result.
   if (!Res.getNode()) return false;
 
   // If the result is N, the sub-method updated N in place.  Tell the legalizer
   // core about this.
   if (Res.getNode() == N)
SDValue DAGTypeLegalizer::WidenVecOp_VECREDUCE(SDNode *N) {
   unsigned WideElts = WideVT.getVectorNumElements();
   for (unsigned Idx = OrigElts; Idx < WideElts; Idx++)
     Op = DAG.getNode(ISD::INSERT_VECTOR_ELT, dl, WideVT, Op, NeutralElem,
                      DAG.getVectorIdxConstant(Idx, dl));
 
   return DAG.getNode(N->getOpcode(), dl, N->getValueType(0), Op, Flags);
 }
 
+SDValue DAGTypeLegalizer::WidenVecOp_VECREDUCE_SEQ(SDNode *N) {
+  SDLoc dl(N);
+  SDValue AccOp = N->getOperand(0);
+  SDValue VecOp = N->getOperand(1);
+  SDValue Op = GetWidenedVector(VecOp);
+
+  EVT OrigVT = VecOp.getValueType();
+  EVT WideVT = Op.getValueType();
+  EVT ElemVT = OrigVT.getVectorElementType();
+  SDNodeFlags Flags = N->getFlags();
+
+  SDValue NeutralElem;
+  switch (N->getOpcode()) {
+  default:
+#ifndef NDEBUG
+    dbgs() << "WidenVectorOp: ";
+    N->dump(&DAG);
+    dbgs() << "\n";
+#endif
+    report_fatal_error("Do not know how to widen this operator!\n");
+  case ISD::VECREDUCE_SEQ_FADD:
+    NeutralElem = DAG.getConstantFP(-0.0, dl, ElemVT);
+    break;
+  }
+
+  // Pad the vector with the neutral element.
+  unsigned OrigElts = OrigVT.getVectorNumElements();
+  unsigned WideElts = WideVT.getVectorNumElements();
+  for (unsigned Idx = OrigElts; Idx < WideElts; Idx++)
+    Op = DAG.getNode(ISD::INSERT_VECTOR_ELT, dl, WideVT, Op, NeutralElem,
+                     DAG.getVectorIdxConstant(Idx, dl));
+
+  return DAG.getNode(N->getOpcode(), dl, N->getValueType(0), AccOp, Op, Flags);
+}
+
 SDValue DAGTypeLegalizer::WidenVecOp_VSELECT(SDNode *N) {
   // This only gets called in the case that the left and right inputs and
   // result are of a legal odd vector type, and the condition is illegal i1 of
   // the same odd width that needs widening.
   EVT VT = N->getValueType(0);
   assert(VT.isVector() && !VT.isPow2VectorType() && isTypeLegal(VT));
 
   SDValue Cond = GetWidenedVector(N->getOperand(0));

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

for (unsigned i = 1; i < NumElts; i++)
     Res = DAG.getNode(BaseOpcode, dl, EltVT, Res, Ops[i], Node->getFlags());
 
   // Result type may be wider than element type.
   if (EltVT != Node->getValueType(0))
     Res = DAG.getNode(ISD::ANY_EXTEND, dl, Node->getValueType(0), Res);
   return Res;
 }
 
+SDValue TargetLowering::expandVecReduceSeq(SDNode *Node, SelectionDAG &DAG) const {
+  SDLoc dl(Node);
+  SDValue AccOp = Node->getOperand(0);
+  SDValue VecOp = Node->getOperand(1);
+
+  EVT VT = VecOp.getValueType();
+  EVT EltVT = VT.getVectorElementType();
+  unsigned NumElts = VT.getVectorNumElements();
+
+  SmallVector<SDValue, 8> Ops;
+  DAG.ExtractVectorElements(VecOp, Ops, 0, NumElts);
+
+  unsigned BaseOpcode = 0;
+  switch (Node->getOpcode()) {
+  default: llvm_unreachable("Expected VECREDUCE_SEQ opcode");
+  case ISD::VECREDUCE_SEQ_FADD: BaseOpcode = ISD::FADD; break;
+  }
+
+  SDValue Res = AccOp;
+  for (unsigned i = 0; i < NumElts; i++)
+    Res = DAG.getNode(BaseOpcode, dl, EltVT, Res, Ops[i], Node->getFlags());
+
+  return Res;
+}
+
 bool TargetLowering::expandREM(SDNode *Node, SDValue &Result,
                                SelectionDAG &DAG) const {
   EVT VT = Node->getValueType(0);
   SDLoc dl(Node);
   bool isSigned = Node->getOpcode() == ISD::SREM;
   unsigned DivOpc = isSigned ? ISD::SDIV : ISD::UDIV;
   unsigned DivRemOpc = isSigned ? ISD::SDIVREM : ISD::UDIVREM;
   SDValue Dividend = Node->getOperand(0);

llvm/lib/Target/AArch64/AArch64ISelLowering.h

public:
   /// merge. However, merging them creates a BUILD_VECTOR that is just as
   /// illegal as the original, thus leading to an infinite legalisation loop.
   /// NOTE: Once BUILD_VECTOR is legal or can be custom lowered for all legal
   /// vector types this override can be removed.
   bool mergeStoresAfterLegalization(EVT VT) const override {
     return !useSVEForFixedLengthVectors();
   }
 
-  // FIXME: Move useSVEForFixedLengthVectors*() back to private scope once
-  // reduction legalization is complete.      
-  bool useSVEForFixedLengthVectors() const;
-  // Normally SVE is only used for byte size vectors that do not fit within a
-  // NEON vector. This changes when OverrideNEON is true, allowing SVE to be
-  // used for 64bit and 128bit vectors as well.
-  bool useSVEForFixedLengthVectorVT(EVT VT, bool OverrideNEON = false) const;
-
 private:
   /// Keep a pointer to the AArch64Subtarget around so that we can
   /// make the right decision when generating code for different targets.
   const AArch64Subtarget *Subtarget;
 
   bool isExtFreeImpl(const Instruction *Ext) const override;
 
   void addTypeForNEON(MVT VT, MVT PromotedBitwiseVT);
void ReplaceExtractSubVectorResults(SDNode *N,
                                       SelectionDAG &DAG) const;
 
   bool shouldNormalizeToSelectSequence(LLVMContext &, EVT) const override;
 
   void finalizeLowering(MachineFunction &MF) const override;
 
   bool shouldLocalize(const MachineInstr &MI,
                       const TargetTransformInfo *TTI) const override;
+
+  bool useSVEForFixedLengthVectors() const;
+  // Normally SVE is only used for byte size vectors that do not fit within a
+  // NEON vector. This changes when OverrideNEON is true, allowing SVE to be
+  // used for 64bit and 128bit vectors as well.
+  bool useSVEForFixedLengthVectorVT(EVT VT, bool OverrideNEON = false) const;
 };
 
 namespace AArch64 {
 FastISel *createFastISel(FunctionLoweringInfo &funcInfo,
                          const TargetLibraryInfo *libInfo);
 } // end namespace AArch64
 
 } // end namespace llvm
 
 #endif

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

if (Subtarget->hasNEON()) {
     setOperationAction(ISD::FSQRT, MVT::v1f64, Expand);
     setOperationAction(ISD::FSUB, MVT::v1f64, Expand);
     setOperationAction(ISD::FTRUNC, MVT::v1f64, Expand);
     setOperationAction(ISD::SETCC, MVT::v1f64, Expand);
     setOperationAction(ISD::BR_CC, MVT::v1f64, Expand);
     setOperationAction(ISD::SELECT, MVT::v1f64, Expand);
     setOperationAction(ISD::SELECT_CC, MVT::v1f64, Expand);
     setOperationAction(ISD::FP_EXTEND, MVT::v1f64, Expand);
+    setOperationAction(ISD::VECREDUCE_SEQ_FADD, MVT::v1f64, Expand);
 
     setOperationAction(ISD::FP_TO_SINT, MVT::v1i64, Expand);
     setOperationAction(ISD::FP_TO_UINT, MVT::v1i64, Expand);
     setOperationAction(ISD::SINT_TO_FP, MVT::v1i64, Expand);
     setOperationAction(ISD::UINT_TO_FP, MVT::v1i64, Expand);
     setOperationAction(ISD::FP_ROUND, MVT::v1f64, Expand);
 
     setOperationAction(ISD::MUL, MVT::v1i64, Expand);
for (MVT VT : { MVT::v8i8, MVT::v4i16, MVT::v2i32,
       setOperationAction(ISD::USUBSAT, VT, Legal);
     }
 
     // Vector reductions
     for (MVT VT : { MVT::v4f16, MVT::v2f32,
                     MVT::v8f16, MVT::v4f32, MVT::v2f64 }) {
       setOperationAction(ISD::VECREDUCE_FMAX, VT, Custom);
       setOperationAction(ISD::VECREDUCE_FMIN, VT, Custom);
+      setOperationAction(ISD::VECREDUCE_SEQ_FADD, VT, Expand);
     }
     for (MVT VT : { MVT::v8i8, MVT::v4i16, MVT::v2i32,
                     MVT::v16i8, MVT::v8i16, MVT::v4i32 }) {
       setOperationAction(ISD::VECREDUCE_ADD, VT, Custom);
       setOperationAction(ISD::VECREDUCE_SMAX, VT, Custom);
       setOperationAction(ISD::VECREDUCE_SMIN, VT, Custom);
       setOperationAction(ISD::VECREDUCE_UMAX, VT, Custom);
       setOperationAction(ISD::VECREDUCE_UMIN, VT, Custom);

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.h

int getInterleavedMemoryOpCost(
       bool UseMaskForCond = false, bool UseMaskForGaps = false);
 
   bool
   shouldConsiderAddressTypePromotion(const Instruction &I,
                                      bool &AllowPromotionWithoutCommonHeader);
 
   bool shouldExpandReduction(const IntrinsicInst *II) const {
     switch (II->getIntrinsicID()) {
-    case Intrinsic::vector_reduce_fadd: {
-      Value *VecOp = II->getArgOperand(1);
-      EVT VT = TLI->getValueType(getDataLayout(), VecOp->getType());
-      if (ST->hasSVE() &&
-          TLI->useSVEForFixedLengthVectorVT(VT, /*OverrideNEON=*/true))
-        return false;
-
-      return !II->getFastMathFlags().allowReassoc();
-    }
     case Intrinsic::vector_reduce_fmul:
-      // We don't have legalization support for ordered FP reductions.
+      // We don't have legalization support for ordered FMUL reductions.
       return !II->getFastMathFlags().allowReassoc();
 
     default:
       // Don't expand anything else, let legalization deal with it.
       return false;
     }
   }
 

llvm/test/CodeGen/AArch64/sve-fixed-length-fp-reduce.ll

 define half @fadda_v32f16(half %start, <32 x half>* %a) #0 {
 ; CHECK-LABEL: fadda_v32f16:
 ; VBITS_GE_512: ptrue [[PG:p[0-9]+]].h, vl32
 ; VBITS_GE_512-NEXT: ld1h { [[OP:z[0-9]+]].h }, [[PG]]/z, [x0]
 ; VBITS_GE_512-NEXT: fadda h0, [[PG]], h0, [[OP]].h
 ; VBITS_GE_512-NEXT: ret
 
 ; Ensure sensible type legalisation.
-; VBITS_EQ_256-COUNT-32: fadd
-; VBITS_EQ_256: ret
+; VBITS_EQ_256: add x8, x0, #32
+; VBITS_EQ_256-NEXT: ptrue [[PG:p[0-9]+]].h, vl16
+; VBITS_EQ_256-DAG: ld1h { [[LO:z[0-9]+]].h }, [[PG]]/z, [x0]
+; VBITS_EQ_256-DAG: ld1h { [[HI:z[0-9]+]].h }, [[PG]]/z, [x8]
+; VBITS_EQ_256-NEXT: fadda h0, [[PG]], h0, [[LO]].h
+; VBITS_EQ_256-NEXT: fadda h0, [[PG]], h0, [[HI]].h
+; VBITS_EQ_256-NEXT: ret
   %op = load <32 x half>, <32 x half>* %a
   %res = call half @llvm.vector.reduce.fadd.v32f16(half %start, <32 x half> %op)
   ret half %res
 }
 
 define half @fadda_v64f16(half %start, <64 x half>* %a) #0 {
 ; CHECK-LABEL: fadda_v64f16:
 ; VBITS_GE_1024: ptrue [[PG:p[0-9]+]].h, vl64

 define float @fadda_v16f32(float %start, <16 x float>* %a) #0 {
 ; CHECK-LABEL: fadda_v16f32:
 ; VBITS_GE_512: ptrue [[PG:p[0-9]+]].s, vl16
 ; VBITS_GE_512-NEXT: ld1w { [[OP:z[0-9]+]].s }, [[PG]]/z, [x0]
 ; VBITS_GE_512-NEXT: fadda s0, [[PG]], s0, [[OP]].s
 ; VBITS_GE_512-NEXT: ret
 
 ; Ensure sensible type legalisation.
-; VBITS_EQ_256-COUNT-16: fadd
-; VBITS_EQ_256: ret
+; VBITS_EQ_256: add x8, x0, #32
+; VBITS_EQ_256-NEXT: ptrue [[PG:p[0-9]+]].s, vl8
+; VBITS_EQ_256-DAG: ld1w { [[LO:z[0-9]+]].s }, [[PG]]/z, [x0]
+; VBITS_EQ_256-DAG: ld1w { [[HI:z[0-9]+]].s }, [[PG]]/z, [x8]
+; VBITS_EQ_256-NEXT: fadda s0, [[PG]], s0, [[LO]].s
+; VBITS_EQ_256-NEXT: fadda s0, [[PG]], s0, [[HI]].s
+; VBITS_EQ_256-NEXT: ret
   %op = load <16 x float>, <16 x float>* %a
   %res = call float @llvm.vector.reduce.fadd.v16f32(float %start, <16 x float> %op)
   ret float %res
 }
 
 define float @fadda_v32f32(float %start, <32 x float>* %a) #0 {
 ; CHECK-LABEL: fadda_v32f32:
 ; VBITS_GE_1024: ptrue [[PG:p[0-9]+]].s, vl32

 define double @fadda_v8f64(double %start, <8 x double>* %a) #0 {
 ; CHECK-LABEL: fadda_v8f64:
 ; VBITS_GE_512: ptrue [[PG:p[0-9]+]].d, vl8
 ; VBITS_GE_512-NEXT: ld1d { [[OP:z[0-9]+]].d }, [[PG]]/z, [x0]
 ; VBITS_GE_512-NEXT: fadda d0, [[PG]], d0, [[OP]].d
 ; VBITS_GE_512-NEXT: ret
 
 ; Ensure sensible type legalisation.
-; VBITS_EQ_256-COUNT-8: fadd
-; VBITS_EQ_256: ret
+; VBITS_EQ_256: add x8, x0, #32
+; VBITS_EQ_256-NEXT: ptrue [[PG:p[0-9]+]].d, vl4
+; VBITS_EQ_256-DAG: ld1d { [[LO:z[0-9]+]].d }, [[PG]]/z, [x0]
+; VBITS_EQ_256-DAG: ld1d { [[HI:z[0-9]+]].d }, [[PG]]/z, [x8]
+; VBITS_EQ_256-NEXT: fadda d0, [[PG]], d0, [[LO]].d
+; VBITS_EQ_256-NEXT: fadda d0, [[PG]], d0, [[HI]].d
+; VBITS_EQ_256-NEXT: ret
   %op = load <8 x double>, <8 x double>* %a
   %res = call double @llvm.vector.reduce.fadd.v8f64(double %start, <8 x double> %op)
   ret double %res
 }
 
 define double @fadda_v16f64(double %start, <16 x double>* %a) #0 {
 ; CHECK-LABEL: fadda_v16f64:
 ; VBITS_GE_1024: ptrue [[PG:p[0-9]+]].d, vl16

llvm/test/CodeGen/AArch64/vecreduce-fadd-legalization-strict.ll

 ; CHECK-NEXT:    ret
   %b = call fp128 @llvm.vector.reduce.fadd.f128.v2f128(fp128 zeroinitializer, <2 x fp128> %a)
   ret fp128 %b
 }
 
 define float @test_v16f32(<16 x float> %a) nounwind {
 ; CHECK-LABEL: test_v16f32:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    fmov s4, wzr
-; CHECK-NEXT:    mov s5, v0.s[1]
-; CHECK-NEXT:    fadd s4, s0, s4
-; CHECK-NEXT:    fadd s4, s4, s5
-; CHECK-NEXT:    mov s5, v0.s[2]
-; CHECK-NEXT:    mov s0, v0.s[3]
-; CHECK-NEXT:    fadd s4, s4, s5
-; CHECK-NEXT:    fadd s0, s4, s0
-; CHECK-NEXT:    mov s5, v1.s[1]
-; CHECK-NEXT:    fadd s0, s0, s1
-; CHECK-NEXT:    mov s4, v1.s[2]
-; CHECK-NEXT:    fadd s0, s0, s5
-; CHECK-NEXT:    mov s1, v1.s[3]
-; CHECK-NEXT:    fadd s0, s0, s4
-; CHECK-NEXT:    fadd s0, s0, s1
-; CHECK-NEXT:    mov s5, v2.s[1]
-; CHECK-NEXT:    fadd s0, s0, s2
-; CHECK-NEXT:    mov s4, v2.s[2]
-; CHECK-NEXT:    fadd s0, s0, s5
-; CHECK-NEXT:    mov s1, v2.s[3]
-; CHECK-NEXT:    fadd s0, s0, s4
-; CHECK-NEXT:    fadd s0, s0, s1
-; CHECK-NEXT:    mov s2, v3.s[1]
-; CHECK-NEXT:    fadd s0, s0, s3
-; CHECK-NEXT:    mov s5, v3.s[2]
-; CHECK-NEXT:    fadd s0, s0, s2
-; CHECK-NEXT:    fadd s0, s0, s5
-; CHECK-NEXT:    mov s1, v3.s[3]
-; CHECK-NEXT:    fadd s0, s0, s1
-; CHECK-NEXT:    ret
+; CHECK-NEXT: fmov  s24, wzr
+; CHECK-NEXT: mov s21, v0.s[3]
+; CHECK-NEXT: mov s22, v0.s[2]
+; CHECK-NEXT: mov s23, v0.s[1]
+; CHECK-NEXT: fadd  s0, s0, s24
+; CHECK-NEXT: fadd  s0, s0, s23
+; CHECK-NEXT: fadd  s0, s0, s22
+; CHECK-NEXT: fadd  s0, s0, s21
+; CHECK-NEXT: mov s20, v1.s[1]
+; CHECK-NEXT: fadd  s0, s0, s1
+; CHECK-NEXT: mov s19, v1.s[2]
+; CHECK-NEXT: fadd  s0, s0, s20
+; CHECK-NEXT: mov s18, v1.s[3]
+; CHECK-NEXT: fadd  s0, s0, s19
+; CHECK-NEXT: fadd  s0, s0, s18
+; CHECK-NEXT: mov s17, v2.s[1]
+; CHECK-NEXT: fadd  s0, s0, s2
+; CHECK-NEXT: mov s16, v2.s[2]
+; CHECK-NEXT: fadd  s0, s0, s17
+; CHECK-NEXT: mov s7, v2.s[3]
+; CHECK-NEXT: fadd  s0, s0, s16
+; CHECK-NEXT: fadd  s0, s0, s7
+; CHECK-NEXT: mov s6, v3.s[1]
+; CHECK-NEXT: fadd  s0, s0, s3
+; CHECK-NEXT: mov s5, v3.s[2]
+; CHECK-NEXT: fadd  s0, s0, s6
+; CHECK-NEXT: mov s4, v3.s[3]
+; CHECK-NEXT: fadd  s0, s0, s5
+; CHECK-NEXT: fadd  s0, s0, s4
+; CHECK-NEXT: ret
   %b = call float @llvm.vector.reduce.fadd.f32.v16f32(float 0.0, <16 x float> %a)
   ret float %b
 }