[DAGCombiner] Recognize more patterns for ABS

[kparzysz]

Summary

The Hexagon backend had these recognized in selection patterns. Make the combiner get them instead. One case was already covered, but it failed when the XOR operands were switched.

[spatel]

The subtract version was noted in PR36036:
https://bugs.llvm.org/show_bug.cgi?id=36036

And as commented there, we're now canonicalizing in IR to the form with select:
D40984

And there were more IR improvements for abs() here:
D47041
D47076
D47631

...so can we add the IR canonicalization for the subtract version (solve PR36036) and be done with this? Ie, can we already remove the DAG combine for the half-implemented 'add' version because we're confident that IR is now always going to be in the canonical 'select' form? Is there some place in the DAG that creates abs() in a non-canonical form?

[RKSimon]

While I remember ValueTracking matches SPF_ABS/SPF_NABS selection style patterns - but SelectionDAGBuilder::visitSelect still doesn't support SPF_ABS/SPF_NABS which prevents it being used

[kparzysz]

There are functions in test/CodeGen/Hexagon/abs.ll that will fail without the changes in visitXOR (the "add" pattern).

[kparzysz]

I see what you mean... Adding the sub variant to instcombine, not dagcombine, and deleting all abs from dagcombine. Yes, that should work.

[spatel]

In D47831#1123943, @kparzysz wrote:

I see what you mean... Adding the sub variant to instcombine, not dagcombine, and deleting all abs from dagcombine. Yes, that should work.

Great - I'll add that (simple translation of D40984) if you're not already doing it.

I think nobody is ever quite sure when the IR improvements allow us to remove DAG folds, so we end up with largely dead code in the backend.

But Simon raises a point that has come up before - we should be producing ABS nodes in SelectionDAGBuilder similar to how we already produce MIN/MAX. We'll want to do that before deleting any DAGCombiner code.

[kparzysz]

Is is possible to end up with the abs patterns after simplifying/legalizing an existing DAG, without having them exposed in the IR earlier on?

[spatel]

In D47831#1123973, @kparzysz wrote:

Is is possible to end up with the abs patterns after simplifying/legalizing an existing DAG, without having them exposed in the IR earlier on?

I can't rule it out completely, but that seems very unlikely given that we have a generic ABS node. Some set of smaller DAG transforms would have to unknowingly produce the shift+xor+add/sub instructions independently without realizing it has created the larger ABS node?

[kparzysz]

In D47831#1123994, @spatel wrote:

I can't rule it out completely, but that seems very unlikely given that we have a generic ABS node. Some set of smaller DAG transforms would have to unknowingly produce the shift+xor+add/sub instructions independently without realizing it has created the larger ABS node?

Yes, that's what I meant. I've seen a similar kind of behavior before (different operations though). I can try to create a testcase that shows that. Is this simply something that we assume could happen and have to live with?

[spatel]

In D47831#1124005, @kparzysz wrote:

In D47831#1123994, @spatel wrote:

I can't rule it out completely, but that seems very unlikely given that we have a generic ABS node. Some set of smaller DAG transforms would have to unknowingly produce the shift+xor+add/sub instructions independently without realizing it has created the larger ABS node?

Yes, that's what I meant. I've seen a similar kind of behavior before (different operations though). I can try to create a testcase that shows that. Is this simply something that we assume could happen and have to live with?

No, if it's likely, then we should have a DAGCombine for it. We want the IR canonicalization regardless of that though, so I'll work on the InstCombine patch.

[spatel]

Here's the instcombine patch:
rL334137

If we want to keep going with a DAG patch, we'll need codegen tests. A basic x86 example is shown in PR36036.

A more involved case with multiple uses of the intermediate values would thwart the IR transform, so that would be a good test for either this patch or the value tracking + SelectionDAGBuilder suggestion.

[kparzysz]

In D47831#1124238, @spatel wrote:

If we want to keep going with a DAG patch, we'll need codegen tests. A basic x86 example is shown in PR36036.

Codegen tests already exist: test/CodeGen/Hexagon/abs.ll. That testcase used to rely on Hexagon-specific selection patterns, which this patch removes.

[kparzysz]

Added a check for reversed order of add operands.

Added a test with multiple uses of the sign bit copy, and with the order of add's operands reversed.

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5655 ↗

(On Diff #150353)

Brackets for clarity : (OpSizeInBits - 1)

lib/Target/ARM/ARMInstrNEON.td

5399 ↗

(On Diff #150353)

Is there existing test coverage for these?

[kparzysz]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5655 ↗

(On Diff #150353)

I actually removed them for clarity (I forgot about the "sub" case)...

lib/Target/ARM/ARMInstrNEON.td

5399 ↗

(On Diff #150353)

test/CodeGen/ARM/neon_vabs.ll failed without those. I think the patterns above it will no longer be triggered actually, but I didn't want to remove them.

[kparzysz]

Add the parentheses back.

[RKSimon]

lib/Target/ARM/ARMInstrNEON.td

5399 ↗

(On Diff #150353)

@jmolloy @rengolin Any thoughts?

[efriedma]

lib/Target/ARM/ARMInstrNEON.td

5399 ↗

(On Diff #150353)

The new patterns look fine; please delete the old patterns.

[kparzysz]

Removed unnecessary patterns from ARMInstrNEON.td, changed the SUB pattern to recognize XOR operands in reversed order.

[kparzysz]

lib/Target/ARM/ARMInstrNEON.td

5400 ↗

(On Diff #150941)

This should say VABDL, not VABD. I'll fix it before commit.

[efriedma]

LGTM

llvm/trunk/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

return DAG.getNode(ISD::SUB, DL, VT, N0.getOperand(0),
                        N0.getOperand(1).getOperand(0));
 
   // If either operand of a sub is undef, the result is undef
   if (N0.isUndef())
     return N0;
   if (N1.isUndef())
     return N1;
 
+  // fold Y = sra (X, size(X)-1); sub (xor (X, Y), Y) -> (abs X)
+  if (TLI.isOperationLegalOrCustom(ISD::ABS, VT)) {
+    if (N0.getOpcode() == ISD::XOR && N1.getOpcode() == ISD::SRA) {
+      SDValue X0 = N0.getOperand(0), X1 = N0.getOperand(1);
+      SDValue S0 = N1.getOperand(0);
+      if ((X0 == S0 && X1 == N1) || (X0 == N1 && X1 == S0)) {
+        unsigned OpSizeInBits = VT.getScalarSizeInBits();
+        if (ConstantSDNode *C = isConstOrConstSplat(N1.getOperand(1)))
+          if (C->getAPIntValue() == (OpSizeInBits - 1))
+            return DAG.getNode(ISD::ABS, SDLoc(N), VT, S0);
+      }
+    }
+  }
+
   // If the relocation model supports it, consider symbol offsets.
   if (GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(N0))
     if (!LegalOperations && TLI.isOffsetFoldingLegal(GA)) {
       // fold (sub Sym, c) -> Sym-c
       if (N1C && GA->getOpcode() == ISD::GlobalAddress)
         return DAG.getGlobalAddress(GA->getGlobal(), SDLoc(N1C), VT,
                                     GA->getOffset() -
                                         (uint64_t)N1C->getSExtValue());
if (N0.getOpcode() == ISD::AND && N0.getNode()->hasOneUse() &&
       N0->getOperand(1) == N1) {
     SDValue X = N0->getOperand(0);
     SDValue NotX = DAG.getNOT(SDLoc(X), X, VT);
     AddToWorklist(NotX.getNode());
     return DAG.getNode(ISD::AND, SDLoc(N), VT, NotX, N1);
   }
 
   // fold Y = sra (X, size(X)-1); xor (add (X, Y), Y) -> (abs X)
+  if (TLI.isOperationLegalOrCustom(ISD::ABS, VT)) {
+    SDValue A = N0.getOpcode() == ISD::ADD ? N0 : N1;
+    SDValue S = N0.getOpcode() == ISD::SRA ? N0 : N1;
+    if (A.getOpcode() == ISD::ADD && S.getOpcode() == ISD::SRA) {
+      SDValue A0 = A.getOperand(0), A1 = A.getOperand(1);
+      SDValue S0 = S.getOperand(0);
+      if ((A0 == S && A1 == S0) || (A1 == S && A0 == S0)) {
         unsigned OpSizeInBits = VT.getScalarSizeInBits();
-  if (N0.getOpcode() == ISD::ADD && N0.getOperand(1) == N1 &&
-      N1.getOpcode() == ISD::SRA && N1.getOperand(0) == N0.getOperand(0) &&
-      TLI.isOperationLegalOrCustom(ISD::ABS, VT)) {
-    if (ConstantSDNode *C = isConstOrConstSplat(N1.getOperand(1)))
+        if (ConstantSDNode *C = isConstOrConstSplat(S.getOperand(1)))
           if (C->getAPIntValue() == (OpSizeInBits - 1))
-        return DAG.getNode(ISD::ABS, SDLoc(N), VT, N0.getOperand(0));
+            return DAG.getNode(ISD::ABS, SDLoc(N), VT, S0);
+      }
+    }
   }
 
   // fold (xor x, x) -> 0
   if (N0 == N1)
     return tryFoldToZero(SDLoc(N), TLI, VT, DAG, LegalOperations, LegalTypes);
 
   // fold (xor (shl 1, x), -1) -> (rotl ~1, x)
   // Here is a concrete example of this equivalence:

llvm/trunk/lib/Target/ARM/ARMInstrNEON.td

def  VABDhq   : N3VQInt<1, 0, 0b11, 0b1101, 0, N3RegFrm, IIC_VBINQ,
                 Requires<[HasNEON, HasFullFP16]>;
 
 //   VABDL    : Vector Absolute Difference Long (Q = | D - D |)
 defm VABDLs   : N3VLIntExt_QHS<0,1,0b0111,0, IIC_VSUBi4Q,
                                "vabdl", "s", int_arm_neon_vabds, zext, 1>;
 defm VABDLu   : N3VLIntExt_QHS<1,1,0b0111,0, IIC_VSUBi4Q,
                                "vabdl", "u", int_arm_neon_vabdu, zext, 1>;
 
+def : Pat<(v8i16 (abs (sub (zext (v8i8 DPR:$opA)), (zext (v8i8 DPR:$opB))))),
+          (VABDLuv8i16 DPR:$opA, DPR:$opB)>;
+def : Pat<(v4i32 (abs (sub (zext (v4i16 DPR:$opA)), (zext (v4i16 DPR:$opB))))),
+          (VABDLuv4i32 DPR:$opA, DPR:$opB)>;
+
+// ISD::ABS is not legal for v2i64, so VABDL needs to be matched from the
+// shift/xor pattern for ABS.
+
 def abd_shr :
     PatFrag<(ops node:$in1, node:$in2, node:$shift),
             (NEONvshrs (sub (zext node:$in1),
                             (zext node:$in2)), (i32 $shift))>;
 
-def : Pat<(xor (v4i32 (bitconvert (v8i16 (abd_shr (v8i8 DPR:$opA), (v8i8 DPR:$opB), 15)))),
-               (v4i32 (bitconvert (v8i16 (add (sub (zext (v8i8 DPR:$opA)),
-                                                   (zext (v8i8 DPR:$opB))),
-                                              (v8i16 (abd_shr (v8i8 DPR:$opA), (v8i8 DPR:$opB), 15))))))),
-          (VABDLuv8i16 DPR:$opA, DPR:$opB)>;
-
-def : Pat<(xor (v4i32 (abd_shr (v4i16 DPR:$opA), (v4i16 DPR:$opB), 31)),
-               (v4i32 (add (sub (zext (v4i16 DPR:$opA)),
-                                (zext (v4i16 DPR:$opB))),
-                           (abd_shr (v4i16 DPR:$opA), (v4i16 DPR:$opB), 31)))),
-          (VABDLuv4i32 DPR:$opA, DPR:$opB)>;
-
 def : Pat<(xor (v4i32 (bitconvert (v2i64 (abd_shr (v2i32 DPR:$opA), (v2i32 DPR:$opB), 63)))),
                (v4i32 (bitconvert (v2i64 (add (sub (zext (v2i32 DPR:$opA)),
                                                    (zext (v2i32 DPR:$opB))),
                                          (abd_shr (v2i32 DPR:$opA), (v2i32 DPR:$opB), 63)))))),
           (VABDLuv2i64 DPR:$opA, DPR:$opB)>;
 
 //   VABA     : Vector Absolute Difference and Accumulate
 defm VABAs    : N3VIntOp_QHS<0,0,0b0111,1, IIC_VABAD, IIC_VABAQ,

llvm/trunk/lib/Target/Hexagon/HexagonISelLowering.cpp

HexagonTargetLowering::HexagonTargetLowering(const TargetMachine &TM,
   setOperationAction(ISD::DYNAMIC_STACKALLOC, MVT::i32, Custom);
 
   if (EmitJumpTables)
     setMinimumJumpTableEntries(MinimumJumpTables);
   else
     setMinimumJumpTableEntries(std::numeric_limits<int>::max());
   setOperationAction(ISD::BR_JT, MVT::Other, Expand);
 
+  setOperationAction(ISD::ABS, MVT::i32, Legal);
+  setOperationAction(ISD::ABS, MVT::i64, Legal);
+
   // Hexagon has A4_addp_c and A4_subp_c that take and generate a carry bit,
   // but they only operate on i64.
   for (MVT VT : MVT::integer_valuetypes()) {
     setOperationAction(ISD::UADDO,    VT, Expand);
     setOperationAction(ISD::USUBO,    VT, Expand);
     setOperationAction(ISD::SADDO,    VT, Expand);
     setOperationAction(ISD::SSUBO,    VT, Expand);
     setOperationAction(ISD::ADDCARRY, VT, Expand);

llvm/trunk/lib/Target/Hexagon/HexagonPatterns.td

let Predicates = [HasV5T] in {
   def: Pat<(fabs F64:$Rs),
            (Combinew (S2_clrbit_i (HiReg $Rs), 31),
                      (i32 (LoReg $Rs)))>;
   def: Pat<(fneg F64:$Rs),
            (Combinew (S2_togglebit_i (HiReg $Rs), 31),
                      (i32 (LoReg $Rs)))>;
 }
 
-let AddedComplexity = 50 in
-multiclass Abs_pat<InstHexagon MI, PatFrag RsPred, int Sh> {
-  // Let y = x >> 31 (for 32-bit), i.e. the sign bit repeated.
-  // abs(x) = (x + y) ^ y
-  def: Pat<(xor (add (sra RsPred:$Rs, (i32 Sh)), RsPred:$Rs),
-                (sra RsPred:$Rs, (i32 Sh))),
-           (MI RsPred:$Rs)>;
-  // abs(x) = (x ^ y) - y
-  def: Pat<(sub (xor RsPred:$Rs, (sra RsPred:$Rs, (i32 Sh))),
-                (sra RsPred:$Rs, (i32 Sh))),
-           (MI RsPred:$Rs)>;
-}
-
-defm: Abs_pat<A2_abs,  I32, 31>;
-defm: Abs_pat<A2_absp, I64, 63>;
-
 def: Pat<(add I32:$Rs, anyimm:$s16),   (A2_addi   I32:$Rs,  imm:$s16)>;
 def: Pat<(or  I32:$Rs, anyimm:$s10),   (A2_orir   I32:$Rs,  imm:$s10)>;
 def: Pat<(and I32:$Rs, anyimm:$s10),   (A2_andir  I32:$Rs,  imm:$s10)>;
 def: Pat<(sub anyimm:$s10, I32:$Rs),   (A2_subri  imm:$s10, I32:$Rs)>;
 
 def: OpR_RR_pat<A2_add,       Add,        i32,   I32>;
 def: OpR_RR_pat<A2_sub,       Sub,        i32,   I32>;
 def: OpR_RR_pat<A2_and,       And,        i32,   I32>;

llvm/trunk/test/CodeGen/Hexagon/abs.ll

 ; CHECK: r1:0 = abs(r1:0)
 define i64 @f5(i64 %a0) #0 {
   %v0 = icmp slt i64 %a0, 0
   %v1 = sub nsw i64 0, %a0
   %v2 = select i1 %v0, i64 %v1, i64 %a0
   ret i64 %v2
 }
 
-attributes #0 = { nounwind readnone "target-cpu"="hexagonv60" }
+; CHECK-LABEL: f6:
+; CHECK: r[[R60:[0-9]+]] = abs(r0)
+; CHECK: r[[R61:[0-9]+]] = asr(r0,#31)
+; CHECK: r0 = addasl(r[[R61]],r[[R60]],#1)
+define i32 @f6(i32 %a0) #0 {
+  %v0 = ashr i32 %a0, 31
+  %v1 = add i32 %a0, %v0
+  %v2 = xor i32 %v0, %v1
+  %v3 = mul i32 %v2, 2
+  %v4 = add i32 %v0, %v3
+  ret i32 %v4
+}
+
+; CHECK-LABEL: f7:
+; CHECK: r[[R70:[0-9]+]] = abs(r0)
+; CHECK: r[[R71:[0-9]+]] = asr(r0,#31)
+; CHECK: r0 = addasl(r[[R71]],r[[R70]],#1)
+define i32 @f7(i32 %a0) #0 {
+  %v0 = ashr i32 %a0, 31
+  %v1 = add i32 %v0, %a0
+  %v2 = xor i32 %v0, %v1
+  %v3 = shl i32 %v2, 1
+  %v4 = add i32 %v0, %v3
+  ret i32 %v4
+}
+
+attributes #0 = { nounwind readnone "target-cpu"="hexagonv60" "target-features"="-packets" }