[ISel] Port AArch64 HADD and RHADD to ISel

[dmgreen]

Summary

This ports the aarch64 combines for HADD and RHADD over to DAG combine, so that they can be used in more architectures (notably MVE in a followup patch). They are renamed to AVGFLOOR and AVGCEIL in the process, to avoid confusion with instructions such as X86 hadd. The code was also rewritten slightly to remove the AArch64 idiosyncrasies.

The general pattern for a AVGFLOORS is

%xe = sext i8 %x to i32
%ye = sext i8 %y to i32
%a = add i32 %xe, %ye
%r = lshr i32 %a, 1
%t = trunc i32 %r to i8

An AVGFLOORU is equivalent with zext. Because of the truncate lshr==ashr, as the top bits are not demanded. An AVGCEIL also includes an extra rounding, so includes an extra add of 1.

[RKSimon]

X86 might be able to reuse this for X86ISD::AVG

llvm/include/llvm/CodeGen/ISDOpcodes.h

617

having add?
Maybe add a code snippet?

622

Maybe add a code snippet?

[efriedma]

llvm/include/llvm/CodeGen/ISDOpcodes.h

617

There's really very little incentive to keep ISD opcode names short, particularly rarely used ones like this. I'd prefer to spell it out (particularly the "h"; for example, x86 has "haddps", where the "h" stands for "horizontal").

Maybe ADD_HALVE_UNSIGNED_ROUND_DOWN and ADD_HALVE_SIGNED_ROUND_UP?

[RKSimon]

@dmgreen - if you're still looking at this, the patch needs a rename of the node enum types and preferably we replace X86ISD::AVG to use this as well.

[craig.topper]

llvm/include/llvm/CodeGen/ISDOpcodes.h

617

Halide calls these halving_add and rounding_halving_add.

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

935 ↗

(On Diff #359623)

Is zext supposed to be sext?

945 ↗

(On Diff #359623)

Can this be DemandedBits.isPositive() or DemandedBits.isSignBitClear()? Counting bits seems like overkill.

[craig.topper]

Instead of making this part of SimplifyDemandedBits, could you emit (and (sext (hadds X, Y)), 0x7fffffff) for the (lshr (add (sext(X), sext(Y)), 1) case and let the AND be optimized by itself? Or would the transform not be profitable if it doesn't get removed?

[dmgreen]

I haven't had a change to look at it recently - I've been busy with other things. I hope to get back to this at some point - it would be good to share it between backends.

llvm/include/llvm/CodeGen/ISDOpcodes.h

617

I'll be honest - I didn't much like the sound of ADD_HALVE_UNSIGNED_ROUND_DOWN. I'm not a fan of how long that name is. Arm uses the name HADD, with S/U or V before it. X86 uses AVG and RISCV uses AAVG I believe, if I was looking up the right instruction. I'm not sure if they have the same concepts of rounding RHADD though, which rounds up. I think gcc calls them AVG_FLOOR and AVG_CEIL.

Any of those names or HALVING_ADD would be find by me.

[dmgreen]

In D106237#3112542, @craig.topper wrote:

Instead of making this part of SimplifyDemandedBits, could you emit (and (sext (hadds X, Y)), 0x7fffffff) for the (lshr (add (sext(X), sext(Y)), 1) case and let the AND be optimized by itself? Or would the transform not be profitable if it doesn't get removed?

Yeah that might work. Like https://alive2.llvm.org/ce/z/9pwKEi. I'll have to check if it looks worse anywhere - I think it should be fine in general, possibly minus the cost of materializing the constant.

[dmgreen]

This now:

• Calls the nodes AVGFLOOR and AVGCEIL.
• Ports X86ISD::AVG to use AVGCEILU.
• Doesn't remove detectAVGPattern, as it can detect more pattern, such as illegal types. It adds some basic widening support to handle them.

[lebedev.ri]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

908 ↗

(On Diff #395353)

There's also the case where one of the operands is a constant, so you don't have an explicit +1

947–950 ↗

(On Diff #395353)

Since you have already avoided the other misdesign (by starting from the shift and not trunc),
can we also avoid one here, by looking at the known sign/leading zero bits instead of an explicit extension?

960–961 ↗

(On Diff #395353)

Don't you need to check that the addition is no-wrap,
i.e. don't you need to check how many bits were added during extension?

Right now this seems like a miscompile, one that will be avoided
if you use known bits instead of looking for extensions.

[dmgreen]

Now using some known bits.

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

908 ↗

(On Diff #395353)

For ARM/Arch64 that would be an hadd (avgfloor), IIUC. For X86 where avgceil is legal but avgfloor is not, we can probably do something about that if needed, or make it target specific. It's probably best not to try and address ever issue in this single patch though.

947–950 ↗

(On Diff #395353)

Sure, sounds good. I've given it a go, but it might be a bit messy. We have to get a type to use for the legalization, which was previously just using the extend type. Let me know if you have any suggestions.

960–961 ↗

(On Diff #395353)

MVE already has some nowrap tablegen patterns, as they don't require any extends and can be recognised from a add+shift.

I've not added anything with nowrap here (maybe we can extend this in a future patch, so long as this is correct so far). The other patterns mostly verify with a single bit of extension, so long as I have that right, and I've added checks where they seem to need 2.

[lebedev.ri]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

987–988 ↗

(On Diff #396444)

Can we get to here where the operations aren't legal yet?

908 ↗

(On Diff #395353)

Sure, this can be done in a follow-up.

What i'm saying is that if you want to catch more cases,
you might want to try to deal with add(ext, C) as with add(ext, add(C-1, 1)) (or vice versa).
Probably this might be best done by adding a wrapper function,
and adding a parameter to this function, bool LookingForCeil.

[dmgreen]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

987–988 ↗

(On Diff #396444)

Yes I think so (IIUYC). It'll be run as part of any of the DAG combines. There is very little legalization for AVG at the moment, so I'm not sure we can create a lot of illegal nodes.

(But I'm not an expert of when it's best to create illegal target-independent nodes and when not)

[craig.topper]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

18554

This APInt goes with the code after this new code. Move it down?

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

946 ↗

(On Diff #396444)

This needs to forward the Depth from the caller.

957 ↗

(On Diff #396444)

ComputeNumSignBits can call computeKnownBits internally and will count leading 0s as sign bits. Does the zero check need to have priority here?

[craig.topper]

In D106237#3114240, @dmgreen wrote:

In D106237#3112542, @craig.topper wrote:

Instead of making this part of SimplifyDemandedBits, could you emit (and (sext (hadds X, Y)), 0x7fffffff) for the (lshr (add (sext(X), sext(Y)), 1) case and let the AND be optimized by itself? Or would the transform not be profitable if it doesn't get removed?

Yeah that might work. Like https://alive2.llvm.org/ce/z/9pwKEi. I'll have to check if it looks worse anywhere - I think it should be fine in general, possibly minus the cost of materializing the constant.

Did you check on this?

[RKSimon]

llvm/lib/Target/X86/X86ISelLowering.cpp

1351 ↗

(On Diff #396444)

These can be custom lowered on AVX1 targets by splitting, but I'm OK with just a TODO for now.

1654 ↗

(On Diff #396444)

These can be custom lowered on non-AVX512BW targets by splitting, but I'm OK with just a TODO for now.

[dmgreen]

In D106237#3228430, @craig.topper wrote:

In D106237#3114240, @dmgreen wrote:

In D106237#3112542, @craig.topper wrote:

Instead of making this part of SimplifyDemandedBits, could you emit (and (sext (hadds X, Y)), 0x7fffffff) for the (lshr (add (sext(X), sext(Y)), 1) case and let the AND be optimized by itself? Or would the transform not be profitable if it doesn't get removed?

Yeah that might work. Like https://alive2.llvm.org/ce/z/9pwKEi. I'll have to check if it looks worse anywhere - I think it should be fine in general, possibly minus the cost of materializing the constant.

Did you check on this?

Yeah - AArch64 as a saddl instruction that can perform 'add(sext, sext)' as a single instruction. That with a shift will be better than a hadd;extend;bic, and it will look worse if the And is less efficient (possibly having to dup a constant).

With the trunc it will perform OK, I'm not sure what the likelyhood of sext with lshr will be without it. With the trunc it will be one of the most common cases, given how the ashr is converted to a lshr.

Providing that the depth is limited, is there an issue with doing it as a demand bits combine?

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

957 ↗

(On Diff #396444)

I was trying to keep SRA producing HADDS, and SRL preferring HADDU. I think it should be using the known bits to preferably make the lowest bitwidth hadd.

llvm/lib/Target/X86/X86ISelLowering.cpp

1351 ↗

(On Diff #396444)

Thanks. I thought that the natural splitting of vectors would capture that already.

[craig.topper]

Providing that the depth is limited, is there an issue with doing it as a demand bits combine?

My main reason for questioning was because as far as I know this is a larger transform than anything else we do in SimplifiedDemandedBits. So it seemed a bit of a new direction for SimplifiedDemandedBits, but if we're not concerned about that then I don't object to this patch.

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

953 ↗

(On Diff #402013)

I'm not sure, but would it be better to use countMaxActiveBits and ComputeMaxSignificantBits. And do all the comparisons against the scalar bit width instead of against 1 and 2.

1000 ↗

(On Diff #402013)

changeVectorElementType is a little broken. If the VT is an MVT, but the VT with the element type replaced isn't an MVT, the function will assert because it needs an LLVMContext to create an EVT which it can't get from the MVT.

Maybe it's ok in this case as long as our MVTs always have all power of 2 element types smaller for each MVT. Like MVT::vXi32 would need MVT::vXi16 and MVT::vXi8 to exist.

[dmgreen]

Now uses EVT::getVectorVT

[dmgreen]

In D106237#3263993, @craig.topper wrote:

Providing that the depth is limited, is there an issue with doing it as a demand bits combine?

My main reason for questioning was because as far as I know this is a larger transform than anything else we do in SimplifiedDemandedBits. So it seemed a bit of a new direction for SimplifiedDemandedBits, but if we're not concerned about that then I don't object to this patch.

Yeah that's fair enough. I had considered it, and was hoping that the initial condition (ConstantSDNode *N1C = isConstOrConstSplat(Op.getOperand(1)); if(N1C && N1C->isOne())..) would rule most stuff out, limiting how expensive this is in practice. In my mind recursing into a SimplifiedDemandedBits call for "N" steps is going to be more expensive than any one transform inside it, due to the number of nodes potentially visited. But they will be related, and I have no hard evidence about which part is potentially slower.

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

953 ↗

(On Diff #402013)

In my mind, saying an add requires a single extra bit is simpler than dealing with MaxActiveBits and BitWidths. But if you think it's worth changing I'm happy to change it.

[RKSimon]

I've lost track of this patch a little - would it make sense to split it into two parts - the first just replaces the target opcodes with the generic ISD variants, and the second then begins the process of moving the matching into generic DAG?

[dmgreen]

Yeah sounds good. This patch was certainly feeling too big

[dmgreen]

This is now a more straight-forward porting of the code from AArch64 to DAGCombine. The X86 parts have been moved into a different patch, and this now starts at a truncate in the same way that the AArch64 code did.

[RKSimon]

Please tidyup the clang-format warnings.

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

14361

update the urhadd references

[dmgreen]

Attempt to clean up formatting, spelling and some node names.

[RKSimon]

LGTM with a few minors

llvm/include/llvm/CodeGen/ISDOpcodes.h

619

Really pedantic but none of these description refer to these being averaging adds, yet a lot of the comments in other places just refers to them as averages.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

12610

assert(N->getOpcode() == ISD::TRUNCATE && "TRUNCATE node expected");

12670

Is this assert necessary?

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

14353

update these as well

llvm/include/llvm/CodeGen/ISDOpcodes.h

enum NodeType {
   STEP_VECTOR,
 
   /// MULHU/MULHS - Multiply high - Multiply two integers of type iN,
   /// producing an unsigned/signed value of type i[2*N], then return the top
   /// part.
   MULHU,
   MULHS,
 
+  /// AVGFLOORS/AVGFLOORU - Halving add - Add two integers using an integer of
+  /// type i[N+1], halving the result by shifting it one bit right.
+  /// shr(add(ext(X), ext(Y)), 1)
+  AVGFLOORS,
+  AVGFLOORU,
+  /// AVGCEILS/AVGCEILU - Rounding halving add - Add two integers using an
+  /// integer of type i[N+2], add 1 and halve the result by shifting it one bit
+  /// right. shr(add(ext(X), ext(Y), 1), 1)
+  AVGCEILS,
+  AVGCEILU,
+
   // ABDS/ABDU - Absolute difference - Return the absolute difference between
   // two numbers interpreted as signed/unsigned.
   // i.e trunc(abs(sext(Op0) - sext(Op1))) becomes abds(Op0, Op1)
   //  or trunc(abs(zext(Op0) - zext(Op1))) becomes abdu(Op0, Op1)
   ABDS,
   ABDU,
 
   /// [US]{MIN/MAX} - Binary minimum or maximum of signed or unsigned

llvm/include/llvm/CodeGen/TargetLowering.h

virtual bool isCommutativeBinOp(unsigned Opcode) const {
     case ISD::SADDSAT:
     case ISD::UADDSAT:
     case ISD::FMINNUM:
     case ISD::FMAXNUM:
     case ISD::FMINNUM_IEEE:
     case ISD::FMAXNUM_IEEE:
     case ISD::FMINIMUM:
     case ISD::FMAXIMUM:
+    case ISD::AVGFLOORS:
+    case ISD::AVGFLOORU:
+    case ISD::AVGCEILS:
+    case ISD::AVGCEILU:
       return true;
     default: return false;
     }
   }
 
   /// Return true if the node is a math/logic binary operator.
   virtual bool isBinOp(unsigned Opcode) const {
     // A commutative binop must be a binop.

llvm/include/llvm/Target/TargetSelectionDAG.td

 
 def add        : SDNode<"ISD::ADD"       , SDTIntBinOp   ,
                         [SDNPCommutative, SDNPAssociative]>;
 def sub        : SDNode<"ISD::SUB"       , SDTIntBinOp>;
 def mul        : SDNode<"ISD::MUL"       , SDTIntBinOp,
                         [SDNPCommutative, SDNPAssociative]>;
 def mulhs      : SDNode<"ISD::MULHS"     , SDTIntBinOp, [SDNPCommutative]>;
 def mulhu      : SDNode<"ISD::MULHU"     , SDTIntBinOp, [SDNPCommutative]>;
+def avgfloors  : SDNode<"ISD::AVGFLOORS" , SDTIntBinOp, [SDNPCommutative]>;
+def avgflooru  : SDNode<"ISD::AVGFLOORU" , SDTIntBinOp, [SDNPCommutative]>;
+def avgceils   : SDNode<"ISD::AVGCEILS"  , SDTIntBinOp, [SDNPCommutative]>;
+def avgceilu   : SDNode<"ISD::AVGCEILU"  , SDTIntBinOp, [SDNPCommutative]>;
 def abds       : SDNode<"ISD::ABDS"      , SDTIntBinOp, [SDNPCommutative]>;
 def abdu       : SDNode<"ISD::ABDU"      , SDTIntBinOp, [SDNPCommutative]>;
 def smullohi   : SDNode<"ISD::SMUL_LOHI" , SDTIntBinHiLoOp, [SDNPCommutative]>;
 def umullohi   : SDNode<"ISD::UMUL_LOHI" , SDTIntBinHiLoOp, [SDNPCommutative]>;
 def sdiv       : SDNode<"ISD::SDIV"      , SDTIntBinOp>;
 def udiv       : SDNode<"ISD::UDIV"      , SDTIntBinOp>;
 def srem       : SDNode<"ISD::SREM"      , SDTIntBinOp>;
 def urem       : SDNode<"ISD::UREM"      , SDTIntBinOp>;

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (SDValue Res = tryToFoldExtendOfConstant(N, TLI, DAG, LegalTypes))
     return Res;
 
   if (SimplifyDemandedVectorElts(SDValue(N, 0)))
     return SDValue(N, 0);
 
   return SDValue();
 }
 
+// Attempt to form one of the avg patterns from:
+// truncate(shr(add(zext(OpB), zext(OpA)), 1))
+// Creating avgflooru/avgfloors/avgceilu/avgceils, with the ceiling having an
+// extra rounding add:
+// truncate(shr(add(zext(OpB), zext(OpA), 1), 1))
+// This starts at a truncate, meaning the shift will always be shl, as the top
+// bits are known to not be demanded.
+static SDValue performAvgCombine(SDNode *N, SelectionDAG &DAG) {
+  EVT VT = N->getValueType(0);
+
+  SDValue Shift = N->getOperand(0);
+  if (Shift.getOpcode() != ISD::SRL)
+    return SDValue();
+
+  // Is the right shift using an immediate value of 1?
+  ConstantSDNode *N1C = isConstOrConstSplat(Shift.getOperand(1));
+  if (!N1C || !N1C->isOne())
+    return SDValue();
+
+  // We are looking for an avgfloor
+  // add(ext, ext)
+  // or one of these as a avgceil
+  // add(add(ext, ext), 1)
+  // add(add(ext, 1), ext)
+  // add(ext, add(ext, 1))
+  SDValue Add = Shift.getOperand(0);
+  if (Add.getOpcode() != ISD::ADD)
+    return SDValue();
+
+  SDValue ExtendOpA = Add.getOperand(0);
+  SDValue ExtendOpB = Add.getOperand(1);
+  auto MatchOperands = [&](SDValue Op1, SDValue Op2, SDValue Op3) {
+    ConstantSDNode *ConstOp;
+    if ((ConstOp = isConstOrConstSplat(Op1)) && ConstOp->isOne()) {
+      ExtendOpA = Op2;
+      ExtendOpB = Op3;
+      return true;
+    }
+    if ((ConstOp = isConstOrConstSplat(Op2)) && ConstOp->isOne()) {
+      ExtendOpA = Op1;
+      ExtendOpB = Op3;
+      return true;
+    }
+    if ((ConstOp = isConstOrConstSplat(Op3)) && ConstOp->isOne()) {
+      ExtendOpA = Op1;
+      ExtendOpB = Op2;
+      return true;
+    }
+    return false;
+  };
+  bool IsCeil = (ExtendOpA.getOpcode() == ISD::ADD &&
+                 MatchOperands(ExtendOpA.getOperand(0), ExtendOpA.getOperand(1),
+                               ExtendOpB)) ||
+                (ExtendOpB.getOpcode() == ISD::ADD &&
+                 MatchOperands(ExtendOpB.getOperand(0), ExtendOpB.getOperand(1),
+                               ExtendOpA));
+
+  unsigned ExtendOpAOpc = ExtendOpA.getOpcode();
+  unsigned ExtendOpBOpc = ExtendOpB.getOpcode();
+  if (!(ExtendOpAOpc == ExtendOpBOpc &&
+        (ExtendOpAOpc == ISD::ZERO_EXTEND || ExtendOpAOpc == ISD::SIGN_EXTEND)))
+    return SDValue();
+
+  // Is the result of the right shift being truncated to the same value type as
+  // the original operands, OpA and OpB?
+  SDValue OpA = ExtendOpA.getOperand(0);
+  SDValue OpB = ExtendOpB.getOperand(0);
+  EVT OpAVT = OpA.getValueType();
+  assert(ExtendOpA.getValueType() == ExtendOpB.getValueType());
+  if (VT != OpAVT || OpAVT != OpB.getValueType())
+    return SDValue();
+
+  bool IsSignExtend = ExtendOpAOpc == ISD::SIGN_EXTEND;
+  unsigned AVGOpc = IsSignExtend ? (IsCeil ? ISD::AVGCEILS : ISD::AVGFLOORS)
+                                 : (IsCeil ? ISD::AVGCEILU : ISD::AVGFLOORU);
+  if (!DAG.getTargetLoweringInfo().isOperationLegalOrCustom(AVGOpc, VT))
+    return SDValue();
+
+  return DAG.getNode(AVGOpc, SDLoc(N), VT, OpA, OpB);
+}
+
 SDValue DAGCombiner::visitTRUNCATE(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   EVT VT = N->getValueType(0);
   EVT SrcVT = N0.getValueType();
   bool isLE = DAG.getDataLayout().isLittleEndian();
 
   // noop truncate
   if (SrcVT == VT)
if (N00.getOpcode() == ISD::SIGN_EXTEND ||
           VT.getVectorElementType())
         return DAG.getNode(ISD::EXTRACT_SUBVECTOR, SDLoc(N0->getOperand(0)), VT,
                            N00.getOperand(0), N0.getOperand(1));
     }
   }
 
   if (SDValue NewVSel = matchVSelectOpSizesWithSetCC(N))
     return NewVSel;
+  if (SDValue M = performAvgCombine(N, DAG))
+    return M;
 
   // Narrow a suitable binary operation with a non-opaque constant operand by
   // moving it ahead of the truncate. This is limited to pre-legalization
   // because targets may prefer a wider type during later combines and invert
   // this transform.
   switch (N0.getOpcode()) {
   case ISD::ADD:
   case ISD::SUB:
if (ST->isTruncatingStore() && ST->isUnindexed() &&
     if ((Value.getOpcode() == ISD::ZERO_EXTEND ||
          Value.getOpcode() == ISD::SIGN_EXTEND ||
          Value.getOpcode() == ISD::ANY_EXTEND) &&
         Value.getOperand(0).getValueType() == ST->getMemoryVT() &&
         TLI.isOperationLegalOrCustom(ISD::STORE, ST->getMemoryVT()))
       return DAG.getStore(Chain, SDLoc(N), Value.getOperand(0), Ptr,
                           ST->getMemOperand());
 
     APInt TruncDemandedBits =
         APInt::getLowBitsSet(Value.getScalarValueSizeInBits(),
                              ST->getMemoryVT().getScalarSizeInBits());
 
     // See if we can simplify the input to this truncstore with knowledge that
     // only the low bits are being used.  For example:
     // "truncstore (or (shl x, 8), y), i8"  -> "truncstore y, i8"
     AddToWorklist(Value.getNode());
     if (SDValue Shorter = DAG.GetDemandedBits(Value, TruncDemandedBits))

llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp

#endif
   case ISD::UADDSAT:
   case ISD::SADDSAT:
   case ISD::USUBSAT:
   case ISD::SSUBSAT:
   case ISD::SSHLSAT:
   case ISD::USHLSAT:
   case ISD::ROTL:
   case ISD::ROTR:
+  case ISD::AVGFLOORS:
+  case ISD::AVGFLOORU:
+  case ISD::AVGCEILS:
+  case ISD::AVGCEILU:
   // Vector-predicated binary op widening. Note that -- unlike the
   // unpredicated versions -- we don't have to worry about trapping on
   // operations like UDIV, FADD, etc., as we pass on the original vector
   // length parameter. This means the widened elements containing garbage
   // aren't active.
   case ISD::VP_SDIV:
   case ISD::VP_UDIV:
   case ISD::VP_SREM:

llvm/lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp

#endif
   case ISD::STRICT_FLOG10:              return "strict_flog10";
 
   // Binary operators
   case ISD::ADD:                        return "add";
   case ISD::SUB:                        return "sub";
   case ISD::MUL:                        return "mul";
   case ISD::MULHU:                      return "mulhu";
   case ISD::MULHS:                      return "mulhs";
+  case ISD::AVGFLOORU:                  return "avgflooru";
+  case ISD::AVGFLOORS:                  return "avgfloors";
+  case ISD::AVGCEILU:                   return "avgceilu";
+  case ISD::AVGCEILS:                   return "avgceils";
   case ISD::ABDS:                       return "abds";
   case ISD::ABDU:                       return "abdu";
   case ISD::SDIV:                       return "sdiv";
   case ISD::UDIV:                       return "udiv";
   case ISD::SREM:                       return "srem";
   case ISD::UREM:                       return "urem";
   case ISD::SMUL_LOHI:                  return "smul_lohi";
   case ISD::UMUL_LOHI:                  return "umul_lohi";

llvm/lib/CodeGen/TargetLoweringBase.cpp

for (MVT VT : MVT::all_valuetypes()) {
     setOperationAction(ISD::SSUBO_CARRY, VT, Expand);
 
     // ADDC/ADDE/SUBC/SUBE default to expand.
     setOperationAction(ISD::ADDC, VT, Expand);
     setOperationAction(ISD::ADDE, VT, Expand);
     setOperationAction(ISD::SUBC, VT, Expand);
     setOperationAction(ISD::SUBE, VT, Expand);
 
+    // Halving adds
+    setOperationAction(ISD::AVGFLOORS, VT, Expand);
+    setOperationAction(ISD::AVGFLOORU, VT, Expand);
+    setOperationAction(ISD::AVGCEILS, VT, Expand);
+    setOperationAction(ISD::AVGCEILU, VT, Expand);
+
     // Absolute difference
     setOperationAction(ISD::ABDS, VT, Expand);
     setOperationAction(ISD::ABDU, VT, Expand);
 
     // These default to Expand so they will be expanded to CTLZ/CTTZ by default.
     setOperationAction(ISD::CTLZ_ZERO_UNDEF, VT, Expand);
     setOperationAction(ISD::CTTZ_ZERO_UNDEF, VT, Expand);
 

llvm/lib/Target/AArch64/AArch64ISelLowering.h

enum NodeType : unsigned {
   FCMLEz,
   FCMLTz,
 
   // Vector across-lanes addition
   // Only the lower result lane is defined.
   SADDV,
   UADDV,
 
-  // Vector halving addition
-  SHADD,
-  UHADD,
-
-  // Vector rounding halving addition
-  SRHADD,
-  URHADD,
-
   // Add Long Pairwise
   SADDLP,
   UADDLP,
 
   // udot/sdot instructions
   UDOT,
   SDOT,
 

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

#undef LCALLNAME5
 
   setTargetDAGCombine(ISD::INTRINSIC_WO_CHAIN);
 
   setTargetDAGCombine(ISD::ANY_EXTEND);
   setTargetDAGCombine(ISD::ZERO_EXTEND);
   setTargetDAGCombine(ISD::SIGN_EXTEND);
   setTargetDAGCombine(ISD::VECTOR_SPLICE);
   setTargetDAGCombine(ISD::SIGN_EXTEND_INREG);
-  setTargetDAGCombine(ISD::TRUNCATE);
   setTargetDAGCombine(ISD::CONCAT_VECTORS);
   setTargetDAGCombine(ISD::INSERT_SUBVECTOR);
   setTargetDAGCombine(ISD::STORE);
   if (Subtarget->supportsAddressTopByteIgnored())
     setTargetDAGCombine(ISD::LOAD);
 
   setTargetDAGCombine(ISD::MUL);
 
for (MVT VT : { MVT::v8i8, MVT::v4i16, MVT::v2i32,
       setOperationAction(ISD::SADDSAT, VT, Legal);
       setOperationAction(ISD::UADDSAT, VT, Legal);
       setOperationAction(ISD::SSUBSAT, VT, Legal);
       setOperationAction(ISD::USUBSAT, VT, Legal);
     }
 
     for (MVT VT : {MVT::v8i8, MVT::v4i16, MVT::v2i32, MVT::v16i8, MVT::v8i16,
                    MVT::v4i32}) {
+      setOperationAction(ISD::AVGFLOORS, VT, Legal);
+      setOperationAction(ISD::AVGFLOORU, VT, Legal);
+      setOperationAction(ISD::AVGCEILS, VT, Legal);
+      setOperationAction(ISD::AVGCEILU, VT, Legal);
       setOperationAction(ISD::ABDS, VT, Legal);
       setOperationAction(ISD::ABDU, VT, Legal);
     }
 
     // Vector reductions
     for (MVT VT : { MVT::v4f16, MVT::v2f32,
                     MVT::v8f16, MVT::v4f32, MVT::v2f64 }) {
       if (VT.getVectorElementType() != MVT::f16 || Subtarget->hasFullFP16()) {
case AArch64ISD::FIRST_NUMBER:
     MAKE_CASE(AArch64ISD::CMLTz)
     MAKE_CASE(AArch64ISD::FCMEQz)
     MAKE_CASE(AArch64ISD::FCMGEz)
     MAKE_CASE(AArch64ISD::FCMGTz)
     MAKE_CASE(AArch64ISD::FCMLEz)
     MAKE_CASE(AArch64ISD::FCMLTz)
     MAKE_CASE(AArch64ISD::SADDV)
     MAKE_CASE(AArch64ISD::UADDV)
-    MAKE_CASE(AArch64ISD::SRHADD)
-    MAKE_CASE(AArch64ISD::URHADD)
-    MAKE_CASE(AArch64ISD::SHADD)
-    MAKE_CASE(AArch64ISD::UHADD)
     MAKE_CASE(AArch64ISD::SDOT)
     MAKE_CASE(AArch64ISD::UDOT)
     MAKE_CASE(AArch64ISD::SMINV)
     MAKE_CASE(AArch64ISD::UMINV)
     MAKE_CASE(AArch64ISD::SMAXV)
     MAKE_CASE(AArch64ISD::UMAXV)
     MAKE_CASE(AArch64ISD::SADDV_PRED)
     MAKE_CASE(AArch64ISD::UADDV_PRED)
SDValue AArch64TargetLowering::LowerINTRINSIC_WO_CHAIN(SDValue Op,
   case Intrinsic::aarch64_neon_srhadd:
   case Intrinsic::aarch64_neon_urhadd:
   case Intrinsic::aarch64_neon_shadd:
   case Intrinsic::aarch64_neon_uhadd: {
     bool IsSignedAdd = (IntNo == Intrinsic::aarch64_neon_srhadd ||
                         IntNo == Intrinsic::aarch64_neon_shadd);
     bool IsRoundingAdd = (IntNo == Intrinsic::aarch64_neon_srhadd ||
                           IntNo == Intrinsic::aarch64_neon_urhadd);
-    unsigned Opcode =
-        IsSignedAdd ? (IsRoundingAdd ? AArch64ISD::SRHADD : AArch64ISD::SHADD)
-                    : (IsRoundingAdd ? AArch64ISD::URHADD : AArch64ISD::UHADD);
+    unsigned Opcode = IsSignedAdd
+                          ? (IsRoundingAdd ? ISD::AVGCEILS : ISD::AVGFLOORS)
+                          : (IsRoundingAdd ? ISD::AVGCEILU : ISD::AVGFLOORU);
     return DAG.getNode(Opcode, dl, Op.getValueType(), Op.getOperand(1),
                        Op.getOperand(2));
   }
   case Intrinsic::aarch64_neon_sabd:
   case Intrinsic::aarch64_neon_uabd: {
     unsigned Opcode = IntNo == Intrinsic::aarch64_neon_uabd ? ISD::ABDU
                                                             : ISD::ABDS;
     return DAG.getNode(Opcode, dl, Op.getValueType(), Op.getOperand(1),
if ((NewOp = tryAdvSIMDModImm32(AArch64ISD::BICi, SDValue(N, 0), DAG,
         (NewOp = tryAdvSIMDModImm16(AArch64ISD::BICi, SDValue(N, 0), DAG,
                                     UndefBits, &LHS)))
       return NewOp;
   }
 
   return SDValue();
 }
 
-// Attempt to form urhadd(OpA, OpB) from
-// truncate(vlshr(sub(zext(OpB), xor(zext(OpA), Ones(ElemSizeInBits))), 1))
-// or uhadd(OpA, OpB) from truncate(vlshr(add(zext(OpA), zext(OpB)), 1)).
-// The original form of the first expression is
-// truncate(srl(add(zext(OpB), add(zext(OpA), 1)), 1)) and the
-// (OpA + OpB + 1) subexpression will have been changed to (OpB - (~OpA)).
-// Before this function is called the srl will have been lowered to
-// AArch64ISD::VLSHR.
-// This pass can also recognize signed variants of the patterns that use sign
-// extension instead of zero extension and form a srhadd(OpA, OpB) or a
-// shadd(OpA, OpB) from them.
-static SDValue
-performVectorTruncateCombine(SDNode *N, TargetLowering::DAGCombinerInfo &DCI,
-                             SelectionDAG &DAG) {
-  EVT VT = N->getValueType(0);
-
-  // Since we are looking for a right shift by a constant value of 1 and we are
-  // operating on types at least 16 bits in length (sign/zero extended OpA and
-  // OpB, which are at least 8 bits), it follows that the truncate will always
-  // discard the shifted-in bit and therefore the right shift will be logical
-  // regardless of the signedness of OpA and OpB.
-  SDValue Shift = N->getOperand(0);
-  if (Shift.getOpcode() != AArch64ISD::VLSHR)
-    return SDValue();
-
-  // Is the right shift using an immediate value of 1?
-  uint64_t ShiftAmount = Shift.getConstantOperandVal(1);
-  if (ShiftAmount != 1)
-    return SDValue();
-
-  SDValue ExtendOpA, ExtendOpB;
-  SDValue ShiftOp0 = Shift.getOperand(0);
-  unsigned ShiftOp0Opc = ShiftOp0.getOpcode();
-  if (ShiftOp0Opc == ISD::SUB) {
-
-    SDValue Xor = ShiftOp0.getOperand(1);
-    if (Xor.getOpcode() != ISD::XOR)
-      return SDValue();
-
-    // Is the XOR using a constant amount of all ones in the right hand side?
-    uint64_t C;
-    if (!isAllConstantBuildVector(Xor.getOperand(1), C))
-      return SDValue();
-
-    unsigned ElemSizeInBits = VT.getScalarSizeInBits();
-    APInt CAsAPInt(ElemSizeInBits, C);
-    if (CAsAPInt != APInt::getAllOnes(ElemSizeInBits))
-      return SDValue();
-
-    ExtendOpA = Xor.getOperand(0);
-    ExtendOpB = ShiftOp0.getOperand(0);
-  } else if (ShiftOp0Opc == ISD::ADD) {
-    ExtendOpA = ShiftOp0.getOperand(0);
-    ExtendOpB = ShiftOp0.getOperand(1);
-  } else
-    return SDValue();
-
-  unsigned ExtendOpAOpc = ExtendOpA.getOpcode();
-  unsigned ExtendOpBOpc = ExtendOpB.getOpcode();
-  if (!(ExtendOpAOpc == ExtendOpBOpc &&
-        (ExtendOpAOpc == ISD::ZERO_EXTEND || ExtendOpAOpc == ISD::SIGN_EXTEND)))
-    return SDValue();
-
-  // Is the result of the right shift being truncated to the same value type as
-  // the original operands, OpA and OpB?
-  SDValue OpA = ExtendOpA.getOperand(0);
-  SDValue OpB = ExtendOpB.getOperand(0);
-  EVT OpAVT = OpA.getValueType();
-  assert(ExtendOpA.getValueType() == ExtendOpB.getValueType());
-  if (!(VT == OpAVT && OpAVT == OpB.getValueType()))
-    return SDValue();
-
-  SDLoc DL(N);
-  bool IsSignExtend = ExtendOpAOpc == ISD::SIGN_EXTEND;
-  bool IsRHADD = ShiftOp0Opc == ISD::SUB;
-  unsigned HADDOpc = IsSignExtend
-                         ? (IsRHADD ? AArch64ISD::SRHADD : AArch64ISD::SHADD)
-                         : (IsRHADD ? AArch64ISD::URHADD : AArch64ISD::UHADD);
-  SDValue ResultHADD = DAG.getNode(HADDOpc, DL, VT, OpA, OpB);
-
-  return ResultHADD;
-}
-
 static bool hasPairwiseAdd(unsigned Opcode, EVT VT, bool FullFP16) {
   switch (Opcode) {
   case ISD::FADD:
     return (FullFP16 && VT == MVT::f16) || VT == MVT::f32 || VT == MVT::f64;
   case ISD::ADD:
     return VT == MVT::i64;
   default:
     return false;
if (N->getNumOperands() == 2 && N0Opc == ISD::TRUNCATE &&
     }
   }
 
   // Wait 'til after everything is legalized to try this. That way we have
   // legal vector types and such.
   if (DCI.isBeforeLegalizeOps())
     return SDValue();
 
-  // Optimise concat_vectors of two [us]rhadds or [us]hadds that use extracted
-  // subvectors from the same original vectors. Combine these into a single
-  // [us]rhadd or [us]hadd that operates on the two original vectors. Example:
-  //  (v16i8 (concat_vectors (v8i8 (urhadd (extract_subvector (v16i8 OpA, <0>),
-  //                                        extract_subvector (v16i8 OpB,
-  //                                        <0>))),
-  //                         (v8i8 (urhadd (extract_subvector (v16i8 OpA, <8>),
-  //                                        extract_subvector (v16i8 OpB,
-  //                                        <8>)))))
+  // Optimise concat_vectors of two [us]avgceils or [us]avgfloors that use
+  // extracted subvectors from the same original vectors. Combine these into a
+  // single [us]rhadd or [us]hadd that operates on the two original vectors.
+  // avgceil is the target independant name for rhadd, avgfloor is a hadd.
+  // Example:
+  //  (concat_vectors (v8i8 (avgceils (extract_subvector (v16i8 OpA, <0>),
+  //                                   extract_subvector (v16i8 OpB, <0>))),
+  //                  (v8i8 (avgceils (extract_subvector (v16i8 OpA, <8>),
+  //                                   extract_subvector (v16i8 OpB, <8>)))))
   // ->
-  //  (v16i8(urhadd(v16i8 OpA, v16i8 OpB)))
+  //  (v16i8(avgceils(v16i8 OpA, v16i8 OpB)))
   if (N->getNumOperands() == 2 && N0Opc == N1Opc &&
-      (N0Opc == AArch64ISD::URHADD || N0Opc == AArch64ISD::SRHADD ||
-       N0Opc == AArch64ISD::UHADD || N0Opc == AArch64ISD::SHADD)) {
+      (N0Opc == ISD::AVGCEILU || N0Opc == ISD::AVGCEILS ||
+       N0Opc == ISD::AVGFLOORU || N0Opc == ISD::AVGFLOORS)) {
     SDValue N00 = N0->getOperand(0);
     SDValue N01 = N0->getOperand(1);
     SDValue N10 = N1->getOperand(0);
     SDValue N11 = N1->getOperand(1);
 
     EVT N00VT = N00.getValueType();
     EVT N10VT = N10.getValueType();
 
SDValue AArch64TargetLowering::PerformDAGCombine(SDNode *N,
   case ISD::INTRINSIC_WO_CHAIN:
     return performIntrinsicCombine(N, DCI, Subtarget);
   case ISD::ANY_EXTEND:
   case ISD::ZERO_EXTEND:
   case ISD::SIGN_EXTEND:
     return performExtendCombine(N, DCI, DAG);
   case ISD::SIGN_EXTEND_INREG:
     return performSignExtendInRegCombine(N, DCI, DAG);
-  case ISD::TRUNCATE:
-    return performVectorTruncateCombine(N, DCI, DAG);
   case ISD::CONCAT_VECTORS:
     return performConcatVectorsCombine(N, DCI, DAG);
   case ISD::INSERT_SUBVECTOR:
     return performInsertSubvectorCombine(N, DCI, DAG);
   case ISD::SELECT:
     return performSelectCombine(N, DCI);
   case ISD::VSELECT:
     return performVSelectCombine(N, DCI.DAG);

llvm/lib/Target/AArch64/AArch64InstrInfo.td

 
 def AArch64saddv    : SDNode<"AArch64ISD::SADDV", SDT_AArch64UnaryVec>;
 def AArch64uaddv    : SDNode<"AArch64ISD::UADDV", SDT_AArch64UnaryVec>;
 def AArch64sminv    : SDNode<"AArch64ISD::SMINV", SDT_AArch64UnaryVec>;
 def AArch64uminv    : SDNode<"AArch64ISD::UMINV", SDT_AArch64UnaryVec>;
 def AArch64smaxv    : SDNode<"AArch64ISD::SMAXV", SDT_AArch64UnaryVec>;
 def AArch64umaxv    : SDNode<"AArch64ISD::UMAXV", SDT_AArch64UnaryVec>;
 
-def AArch64srhadd   : SDNode<"AArch64ISD::SRHADD", SDT_AArch64binvec>;
-def AArch64urhadd   : SDNode<"AArch64ISD::URHADD", SDT_AArch64binvec>;
-def AArch64shadd   : SDNode<"AArch64ISD::SHADD", SDT_AArch64binvec>;
-def AArch64uhadd   : SDNode<"AArch64ISD::UHADD", SDT_AArch64binvec>;
-
 def AArch64uabd     : PatFrags<(ops node:$lhs, node:$rhs),
                                [(abdu node:$lhs, node:$rhs),
                                 (int_aarch64_neon_uabd node:$lhs, node:$rhs)]>;
 def AArch64sabd     : PatFrags<(ops node:$lhs, node:$rhs),
                                [(abds node:$lhs, node:$rhs),
                                 (int_aarch64_neon_sabd node:$lhs, node:$rhs)]>;
 
 def AArch64uaddlp_n : SDNode<"AArch64ISD::UADDLP", SDT_AArch64uaddlp>;

 defm MLA      : SIMDThreeSameVectorBHSTied<0, 0b10010, "mla", null_frag>;
 defm MLS      : SIMDThreeSameVectorBHSTied<1, 0b10010, "mls", null_frag>;
 
 defm MUL      : SIMDThreeSameVectorBHS<0, 0b10011, "mul", mul>;
 defm PMUL     : SIMDThreeSameVectorB<1, 0b10011, "pmul", int_aarch64_neon_pmul>;
 defm SABA     : SIMDThreeSameVectorBHSTied<0, 0b01111, "saba",
       TriOpFrag<(add node:$LHS, (AArch64sabd node:$MHS, node:$RHS))> >;
 defm SABD     : SIMDThreeSameVectorBHS<0,0b01110,"sabd", AArch64sabd>;
-defm SHADD    : SIMDThreeSameVectorBHS<0,0b00000,"shadd", AArch64shadd>;
+defm SHADD    : SIMDThreeSameVectorBHS<0,0b00000,"shadd", avgfloors>;
 defm SHSUB    : SIMDThreeSameVectorBHS<0,0b00100,"shsub", int_aarch64_neon_shsub>;
 defm SMAXP    : SIMDThreeSameVectorBHS<0,0b10100,"smaxp", int_aarch64_neon_smaxp>;
 defm SMAX     : SIMDThreeSameVectorBHS<0,0b01100,"smax", smax>;
 defm SMINP    : SIMDThreeSameVectorBHS<0,0b10101,"sminp", int_aarch64_neon_sminp>;
 defm SMIN     : SIMDThreeSameVectorBHS<0,0b01101,"smin", smin>;
 defm SQADD    : SIMDThreeSameVector<0,0b00001,"sqadd", int_aarch64_neon_sqadd>;
 defm SQDMULH  : SIMDThreeSameVectorHS<0,0b10110,"sqdmulh",int_aarch64_neon_sqdmulh>;
 defm SQRDMULH : SIMDThreeSameVectorHS<1,0b10110,"sqrdmulh",int_aarch64_neon_sqrdmulh>;
 defm SQRSHL   : SIMDThreeSameVector<0,0b01011,"sqrshl", int_aarch64_neon_sqrshl>;
 defm SQSHL    : SIMDThreeSameVector<0,0b01001,"sqshl", int_aarch64_neon_sqshl>;
 defm SQSUB    : SIMDThreeSameVector<0,0b00101,"sqsub", int_aarch64_neon_sqsub>;
-defm SRHADD   : SIMDThreeSameVectorBHS<0,0b00010,"srhadd", AArch64srhadd>;
+defm SRHADD   : SIMDThreeSameVectorBHS<0,0b00010,"srhadd", avgceils>;
 defm SRSHL    : SIMDThreeSameVector<0,0b01010,"srshl", int_aarch64_neon_srshl>;
 defm SSHL     : SIMDThreeSameVector<0,0b01000,"sshl", int_aarch64_neon_sshl>;
 defm SUB      : SIMDThreeSameVector<1,0b10000,"sub", sub>;
 defm UABA     : SIMDThreeSameVectorBHSTied<1, 0b01111, "uaba",
       TriOpFrag<(add node:$LHS, (AArch64uabd node:$MHS, node:$RHS))> >;
 defm UABD     : SIMDThreeSameVectorBHS<1,0b01110,"uabd", AArch64uabd>;
-defm UHADD    : SIMDThreeSameVectorBHS<1,0b00000,"uhadd", AArch64uhadd>;
+defm UHADD    : SIMDThreeSameVectorBHS<1,0b00000,"uhadd", avgflooru>;
 defm UHSUB    : SIMDThreeSameVectorBHS<1,0b00100,"uhsub", int_aarch64_neon_uhsub>;
 defm UMAXP    : SIMDThreeSameVectorBHS<1,0b10100,"umaxp", int_aarch64_neon_umaxp>;
 defm UMAX     : SIMDThreeSameVectorBHS<1,0b01100,"umax", umax>;
 defm UMINP    : SIMDThreeSameVectorBHS<1,0b10101,"uminp", int_aarch64_neon_uminp>;
 defm UMIN     : SIMDThreeSameVectorBHS<1,0b01101,"umin", umin>;
 defm UQADD    : SIMDThreeSameVector<1,0b00001,"uqadd", int_aarch64_neon_uqadd>;
 defm UQRSHL   : SIMDThreeSameVector<1,0b01011,"uqrshl", int_aarch64_neon_uqrshl>;
 defm UQSHL    : SIMDThreeSameVector<1,0b01001,"uqshl", int_aarch64_neon_uqshl>;
 defm UQSUB    : SIMDThreeSameVector<1,0b00101,"uqsub", int_aarch64_neon_uqsub>;
-defm URHADD   : SIMDThreeSameVectorBHS<1,0b00010,"urhadd", AArch64urhadd>;
+defm URHADD   : SIMDThreeSameVectorBHS<1,0b00010,"urhadd", avgceilu>;
 defm URSHL    : SIMDThreeSameVector<1,0b01010,"urshl", int_aarch64_neon_urshl>;
 defm USHL     : SIMDThreeSameVector<1,0b01000,"ushl", int_aarch64_neon_ushl>;
 defm SQRDMLAH : SIMDThreeSameVectorSQRDMLxHTiedHS<1,0b10000,"sqrdmlah",
                                                   int_aarch64_neon_sqrdmlah>;
 defm SQRDMLSH : SIMDThreeSameVectorSQRDMLxHTiedHS<1,0b10001,"sqrdmlsh",
                                                     int_aarch64_neon_sqrdmlsh>;
 
 // Extra saturate patterns, other than the intrinsics matches above