[SelectionDAG] Handle unary SelectPatternFlavor for ABS case in SelectionDAGBuilder::visitSelect.

[ikulagin]

Summary

[SelectionDAG] Handle unary SelectPatternFlavor for ABS case in SelectionDAGBuilder::visitSelect.

These changes are related to PR37743 and include:

1. SelectionDAGBuilder::visitSelect handles the unary SelectPatternFlavor::SPF_ABS case to build ABS node.
2. Delete the redundant recognizer of the integer ABS pattern from the DAGCombiner.
3. Add promoting the integer ABS node in the LegalizeIntegerType.
4. Expand-based legalization of integer result for the ABS nodes.
5. Expand-based legalization of ABS vector operations.
6. Add some integer abs testcases for different typesizes for Thumb arch
7. Add the custom ABS expanding and change the SAD pattern recognizer for X86 arch: The i64 result of the ABS is expanded to:

tmp = (SRA, Hi, 31)
Lo = (UADDO tmp, Lo)
Hi = (XOR tmp, (ADDCARRY tmp, hi, Lo:1))
Lo = (XOR tmp, Lo)

The "detectZextAbsDiff" function is changed for the recognition of pattern
with the ABS node. Given a ABS node, detect the following pattern:
(ABS (SUB (ZERO_EXTEND a), (ZERO_EXTEND b))).

8. Change integer abs testcases for codegen with the ABS node support for AArch64.
   • Indicate that the ABS is legal for the i64 type when the NEON is supported.
   • Change the integer abs testcases to show changing of codegen.
9. Add combine and legalization of ABS nodes for Thumb arch.
10. Extend 'matchSelectPattern' to recognize the ABS patterns with ICMP_SGE condition.

For discussion, see https://bugs.llvm.org/show_bug.cgi?id=37743

[spatel]

Note: this change was mentioned in D48754. That patch was split into several pieces, and I think that's the last planned improvement for IR abs() detection/canonicalization.

[lebedev.ri]

The IR pattern produced by D48754 is already matched into ISD::ABS? Or is there a third differential?

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

1395–1397

Inconsistent with the rest.
Unless the final line is longer than 80-chars, make it one line?

[ikulagin]

In D49837#1176658, @lebedev.ri wrote:

The IR pattern produced by D48754 is already matched into ISD::ABS? Or is there a third differential?

This patch produces ISD::ABS when ValueTracking recognizes the pattern from D48754.

But, what DAG should be produced when ValueTraking recognizes the SPF_NABS pattern?
There is no NABS type for DAG nodes. I propose the following (SUB 0, (ABS X)).

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

1395–1397

The code was formatted by clang-format.
Should I reformat it like the rest?

[shchenz]

Please merge your code with the patch in D48754 and run related tests to check there is no failure.

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

2140

add some test for this function?

lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp

927

same as above, need some testcases for this code change

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2918

I am a little confused for IsUnary since abs is not the only unary node. changing to one related with abs?

2981

I think matchSelectionPattern can only find integer abs for now. Maybe we should only consider ISD::ABS for now and add ISD::FABS when matchSelectionPattern supports fabs?

[spatel]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2981

This was discussed in PR37743. We already have an llvm.fabs intrinsic, so I don't see why matchSelectPattern() would ever need to match fabs().

matchSelectPattern() is used for common operations that do *not* have LLVM intrinsics, so they are implemented using 'select' IR.

The fabs code here should be removed from this patch.

2985

I think SPF_NABS will be as described in the summary - sub(0, abs(X)).

Unless there is evidence that the negation gets separated from the ABS dag node and we're failing to produce 'nabs' codegen for targets that support that op? In that case, we might add a ISD::NABS node.

Either way, let's leave nabs for a follow-up patch.

[ikulagin]

In D49837#1177863, @shchenz wrote:

Please merge your code with the patch in D48754 and run related tests to check there is no failure.

I merged my code with the latest commits and run tests for X86 arch. For X86 everything is OK.
Now, I plan to make tests for other architectures and test them.
Or should I leave this for follow-up patches?

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

2140

I think for this function test cases are architecture-specific. For example, the X86 tests contain the iabs.ll tests with few types.

lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp

927

I think, tests are arсhitecture-specific too.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2918

Yes, but the SelectPatternFlavor contains only ABS/NABS patterns relating to unary node. Should I rename it to IsUnaryAbs?

2981

Ok, I'll remove it.

2985

Ok, I'll implement this in another patch later.

[shchenz]

In D49837#1178105, @ikulagin wrote:

In D49837#1177863, @shchenz wrote:

Please merge your code with the patch in D48754 and run related tests to check there is no failure.

I merged my code with the latest commits and run tests for X86 arch. For X86 everything is OK.
Now, I plan to make tests for other architectures and test them.
Or should I leave this for follow-up patches?

I strongly suggest you run tests for all arch for this patch since your code does not only impact X86.
When I did this task by myself, I found there is some case need to promote ISD::ABS for some type, because I hit assert "Do not know how to promote this operator!". You should also meets this issue if you run check for other arch.
Below is one case for your reference:

: 'RUN: at line 1'; /home/shchenz/llvm/llvm/llvm/build/bin/llc -verify-machineinstrs < /home/shchenz/llvm/llvm/llvm/test/CodeGen/PowerPC/2008-07-15-Bswap.ll

And I have another comment, maybe you can split this patch into two parts:
Patch 1: contain first three parts in your description

SelectionDAGBuilder::visitSelect handles the unary SelectPatternFlavor::SPF_ABS case to build ABS node.
Expand-based legalization of integer result for the ABS nodes.
Expand-based legalization of ABS vector operations.

Patch 2: handle X86 specific

What do you think?

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

2140

Sorry I don't understand what you mean by test cases are architecture-specific?
Yes, I see there are some cases for abs already in X86. But these cases pass without this patch. IMO, ideally there should be test cases for every patch with functionality changing to show what's current patch's improvement or fixing compared with trunk.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2918

Yes, it would be more clear.

[ikulagin]

And I have another comment, maybe you can split this patch into two parts:
Patch 1: contain first three parts in your description

SelectionDAGBuilder::visitSelect handles the unary SelectPatternFlavor::SPF_ABS case to build ABS node.
Expand-based legalization of integer result for the ABS nodes.
Expand-based legalization of ABS vector operations.
Patch 2: handle X86 specific

What do you think?

It make sense. But we must take into account that patches should be applied together, because changes from the patch 1 requires the patch 2 for correct testing the x86 and the subsequent patches for the rest architectures.

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

2140

It is impossible to test only "Expand" without account subsequent "DAGCombining" and other DAG optimizations during the instruction selection for different architectures. I think, that the testing of ABS node with the different scalar/vector types for every architecture is better. Otherwise, there will be a lot of similar tests for every architecture that estimate the same thing.

[RKSimon]

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

1395–1397

Yes please - keep the styling consistent in cases like this (and we don't want to clang-format the whole thing as it makes blaming/diffs tricky).

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

3003

Shouldn't we only do this if TLI.isOperationLegalOrCustom(Opc, VT) ? That probably removes the need for some of the legalization code from this initial patch.

[ikulagin]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

3003

Yes, I think so too, It removes the need for some legalization, but in this case for the absolute value code the DAGBuilder can produce 2 different DAGs (one of which is the select node and the other is the ABS node). This will lead to the more complex DAGCombiner, because the DAGCombiner should support the same patterns with different DAGs. For example, the X86 recognizer of SAD pattern will be needed to handle the case based on the SELECT node and the case based on the ABS node. I think that this makes code bloat with the redundant supported patterns.
Also, the DAG based on the SELECT has 3 nodes (SELECT, SUB, SETCC) and on the ABS only 1.

I have gone deeper into this task and I have some thoughts.
What if we make the DAGBuilder and the Legalization for the ABS more general? I mean that we can always generate the ABS and on the Legalization stage we can perform a simple transformation, but on the Combine stage we can produce the optimal architecture-specific DAG with more complexity transformations.
I think it will allow building a DAG with a smaller number of nodes and performing a legalization of a smaller number of nodes too.
What do you think about this?

[ikulagin]

I have excluded the X86 SAD pattern recognizer from this patch. It will be in another diff.
Now, I am implementing the target-depended ABS handling and the test cases for it.
I will create a new diff for the target-depended handling + test cases over this patch.

[ikulagin]

Rebase the patch

[craig.topper]

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

2147

Isn't this wrong if the value of high is 0x80000000? The absolute value of that would be 0x80000000 which would cause us to leave the low bits unchanged. But if the full value is 0x80000000_00000001 then the absolute value should be 0x7fffffff_ffffffff.

[RKSimon]

@ikulagin You might want to look at https://reviews.llvm.org/D26357 which was my old attempt to add an Intrinsic::abs IR intrinsic - you might be able to reuse some of the legalizers from that?

[ikulagin]

In D49837#1221997, @RKSimon wrote:

@ikulagin You might want to look at https://reviews.llvm.org/D26357 which was my old attempt to add an Intrinsic::abs IR intrinsic - you might be able to reuse some of the legalizers from that?

Thank you for that differential. I'll use some of the legalizers.

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

2147

I'm sorry for the late response. Yes, this is wrong. I left out the case when the low/high parts contain values that are greater/smaller than the MAX/MIN for the given number of bits. I will redo it.

[ikulagin]

Rebase and fix expand-based legalization of integer result for the ABS nodes.

[RKSimon]

lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

2599

Safer to use getScalaraSizeInBits - in case vector types ever use this.

[RKSimon]

lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp

937

Unless these ops are legal/custom (or promote for xor) on the vector type I think we need to unroll.

[RKSimon]

@ikulagin Are you still working on this? If not would you mind if I commandeer and complete this?

[ikulagin]

Are you still working on this?

Yes I am. I would like to do this. I have just waited for the feedback. If it is an urgent task I would like to continue my work.

[RKSimon]

lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

2602

You might want to consider creating just TargetLowering::ExpandABS and getting both SelectionDAGLegalize/VectorLegalizer to call it - see the other TargetLowering::Expand* functions for examples.

[ikulagin]

Changes in this patch require the changes in target specific parts (AArch64, X86, etc), otherwise
some tests will fail. Should I include these target specific changes into the current differential or into a separate one?
Now they are in separate differential.

[RKSimon]

In D49837#1278151, @ikulagin wrote:

Changes in this patch require the changes in target specific parts (AArch64, X86, etc), otherwise
some tests will fail. Should I include these target specific changes into the current differential or into a separate one?
Now they are in separate differential.

Better to merge them all into this patch - reviewers will be able to advise if anything can be cherry picked out then.

[ikulagin]

Rebase and merge changes to one patch.

Well, I have to do changes for NVPTX backend, because the idioms.ll test failed due to the matchSelectPattern doesn't recognize the ABS pattern for that case.
(this test uses icmp sge but matchSelectPattern recognize only ICMP_SGT and ICMP_SLT cases).

Please pay attention to how I supported Arch and Thumb.
I wait feedback to correct this if it is need.

[ikulagin]

Extend 'matchSelectPattern' to recognize the ABS patterns with ICMP_SGE condition.

[RKSimon]

lib/CodeGen/SelectionDAG/TargetLowering.cpp

4458 ↗

(On Diff #171631)

The shift constant needs to use a getShiftAmountTy type

lib/Target/ARM/ARMISelLowering.cpp

1210 ↗

(On Diff #171631)

Don't include commented out code

10309 ↗

(On Diff #171631)

Just call TargetLowering::expandABS ?

lib/Target/X86/X86ISelLowering.cpp

26030 ↗

(On Diff #171631)

Seems a shame this (and the ARM) code can't be put into the legalizers

test/CodeGen/Thumb/iabs.ll

76 ↗

(On Diff #171631)

Add these new tests to trunk now so the patch shows the codegen diff

[spatel]

lib/Analysis/ValueTracking.cpp

4856 ↗

(On Diff #171631)

This is saying that:
X >= -1 ? X : -X
...is an abs(). But that's not correct:
https://rise4fun.com/Alive/eVzs

This diff should be split into its own patch and include correctness tests. Preferably, the tests can go in:
llvm/unittests/Analysis/ValueTrackingTest.cpp

[ikulagin]

lib/Target/ARM/ARMISelLowering.cpp

1210 ↗

(On Diff #171631)

Sorry for that, I did not notice.

lib/Target/X86/X86ISelLowering.cpp

26030 ↗

(On Diff #171631)

Could you explain in more detail, or give some advice, please?

test/CodeGen/Thumb/iabs.ll

76 ↗

(On Diff #171631)

It is already exist, I have created diff early -- D52138.

[ikulagin]

lib/Analysis/ValueTracking.cpp

4856 ↗

(On Diff #171631)

Yes, for that pattern we need something like follow:

// (X >= 0) ? X : -X or (X >= 1) ? X : -x --> ABS(X)
if (Pred == ICmpInst::ICMP_SGE && match(CmpRHS, ZeroOrOne))
  return {SPF_ABS, SPNB_NA, false};

[RKSimon]

@ikulagin are you still looking at this?

[ikulagin]

In D49837#1351290, @RKSimon wrote:

@ikulagin are you still looking at this?

I am waiting for feedback and I want to coordinate the activity.

[RKSimon]

In D49837#1352348, @ikulagin wrote:

In D49837#1351290, @RKSimon wrote:

@ikulagin are you still looking at this?

I am waiting for feedback and I want to coordinate the activity.

AFAICT you have outstanding fixes that you promised to complete?

[RKSimon]

@ikulagin Please can you rebase now that rL350998 has landed?

[RKSimon]

@ikulagin I'm keen to get this finished - do you have time to look at this or can I commandeer please?

[ikulagin]

In D49837#1376976, @RKSimon wrote:

@ikulagin I'm keen to get this finished - do you have time to look at this or can I commandeer please?

I have a outstanding few changes. I am planning rebase it and send patch by this Saturday. If the changes are needed earlier you can continue this task. What do you think?

[RKSimon]

SGTM - thanks for the update

[ikulagin]

Rebase and some fixes.

There is a need to determine ways to legalize ABS for PowerPC. Now it fails on the tests ppc64-P9-vabsd.ll pre-inc-disable.ll.

[RKSimon]

In D49837#1382083, @ikulagin wrote:

Rebase and some fixes.

There is a need to determine ways to legalize ABS for PowerPC. Now it fails on the tests ppc64-P9-vabsd.ll pre-inc-disable.ll.

Please can you include the current test change so the ppc guys can comment more easily

[RKSimon]

@inouehrs may also be able to advise - IIRC he was investigating powerpc absolutes at some point (for SAD - D46101).

[ikulagin]

@RKSimon I forgot to clarify, the PPC tests crashed on ppc64-P9-vabsd.ll: lsub_absv_16_ext and pre-inc-disable.ll: test_pre_inc_disable_1, because now the PPC uses custom lowering the ISD::ABS node for vector types,

for (MVT VT : MVT::vector_valuetypes()) {
  // add/sub are legal for all supported vector VT's.
  setOperationAction(ISD::ADD, VT, Legal);
  setOperationAction(ISD::SUB, VT, Legal);
  setOperationAction(ISD::ABS, VT, Custom);

but the custom lowering for this architecture is not specified.

[ikulagin]

Rebase and several changes in Thumb test iabs.ll.

[ikulagin]

Rebase and separate testcases for Thumb arch from this patch to D52138.

Do you have any offers to support ABS legalizing for PowerPC?

[nemanjai]

I will apply this patch and take a look at what breaks on PPC. I'll advise soon on what is needed for us.

[nemanjai]

OK, it appears that the PPC issue is really just a phase ordering problem that is quite easy to resolve. We now get the ISD::ABS node earlier so we may very well end up in a situation where we need to legalize the result type of such node. So our Custom legalization of all vector types can't really work any longer. Applying this in PPCISelLowering.cpp should fix the UNREACHABLE failure:

@@ -551,7 +552,9 @@ PPCTargetLowering::PPCTargetLowering(const PPCTarg
       // add/sub are legal for all supported vector VT's.
       setOperationAction(ISD::ADD, VT, Legal);
       setOperationAction(ISD::SUB, VT, Legal);
-      setOperationAction(ISD::ABS, VT, Custom);
+      // Custom lowering for legal vector result types.
+      if (VT.getSizeInBits() == 128)
+        setOperationAction(ISD::ABS, VT, Custom);

       // Vector instructions introduced in P8
       if (Subtarget.hasP8Altivec() && (VT.SimpleTy != MVT::v1i128)) {

[ikulagin]

Applied @nemanjai's fixes and rebased.

[RKSimon]

llvm/test/CodeGen/AArch64/iabs.ll

46 ↗

(On Diff #190509)

@efriedma IIRC we hit this before?

[efriedma]

llvm/test/CodeGen/AArch64/iabs.ll

46 ↗

(On Diff #190509)

Yes; we intentionally marked "abs" as Expand for i64 to avoid this sort of sequence, since it's much higher latency. Not sure why this patch is reversing that decision.

[ikulagin]

llvm/test/CodeGen/AArch64/iabs.ll

46 ↗

(On Diff #190509)

it is, indeed, so. Latency 3 (abs) + 2*3(fmov) vs 1 (cneg) + 1(cmp). Fixed.

[ikulagin]

Reverted legalization of ABS for i64 for AArch64.

[RKSimon]

llvm/lib/Target/PowerPC/PPCISelLowering.cpp

554 ↗

(On Diff #190787)

@nemanjai Use VT.is128BitVector() ? Worth adding as a pre-commit now?

[RKSimon]

I think this can go in now. The PPC ABS fix could go in as pre-commit but its not vital.

[RKSimon]

@ikulagin Do you have commit access ?

[ikulagin]

No I don't. Could you commit it, please?

[tlively]

This commit breaks the following IR:

target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
target triple = "wasm32-unknown-unknown"

define void @foo() local_unnamed_addr {
entry:
  %x0 = load <4 x i8>, <4 x i8>* undef, align 1
  %0 = load <4 x i8>, <4 x i8>* null, align 1
  %t6 = srem <4 x i8> %0, %x0
  %1 = ashr <4 x i8> %t6, <i8 7, i8 7, i8 7, i8 7>
  %2 = icmp slt <4 x i8> %x0, zeroinitializer
  %3 = sub <4 x i8> zeroinitializer, %x0
  %4 = select <4 x i1> %2, <4 x i8> %3, <4 x i8> %x0
  %5 = and <4 x i8> %1, %4
  %6 = add <4 x i8> %5, %t6
  store <4 x i8> %6, <4 x i8>* undef, align 1
  ret void
}

Running llc on that IR gives the following error:

ScalarizeVectorResult #0: t28: v1i8 = abs t26

LLVM ERROR: Do not know how to scalarize the result of this operator!

This was reported at https://bugs.llvm.org/show_bug.cgi?id=41149.

[mstorsjo]

This commit also broke compilation of some files for me, for ARM, where compilation now doesn't finish (files that normally compile within a second now doesn't finish after half an hour. See https://bugs.llvm.org/show_bug.cgi?id=41160 for details and a reproduction sample.

[ikulagin]

In D49837#1436966, @mstorsjo wrote:

This commit also broke compilation of some files for me, for ARM, where compilation now doesn't finish (files that normally compile within a second now doesn't finish after half an hour. See https://bugs.llvm.org/show_bug.cgi?id=41160 for details and a reproduction sample.

DAG combining loops forever after legalize types. I am looking for reason of it.

[nemanjai]

It would appear that the fix for PR 41149 should be fairly straightforward. The vector type legalizer just needs to learn about ISD::ABS. Likely just another case to be added in ScalarizeVectorResult().
PR 41160 is a common pitfall with DAG combines. I've gone ahead and reduced the test case provided in the PR.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (!LegalOperations ||
       // shl setcc result by log2 n2c
       return DAG.getNode(
           ISD::SHL, DL, N2.getValueType(), Temp,
           DAG.getConstant(N2C->getAPIntValue().logBase2(), SDLoc(Temp),
                           getShiftAmountTy(Temp.getValueType())));
     }
   }
 
-  // Check to see if this is an integer abs.
-  // select_cc setg[te] X,  0,  X, -X ->
-  // select_cc setgt    X, -1,  X, -X ->
-  // select_cc setl[te] X,  0, -X,  X ->
-  // select_cc setlt    X,  1, -X,  X ->
-  // Y = sra (X, size(X)-1); xor (add (X, Y), Y)
-  if (N1C) {
-    ConstantSDNode *SubC = nullptr;
-    if (((N1C->isNullValue() && (CC == ISD::SETGT || CC == ISD::SETGE)) ||
-         (N1C->isAllOnesValue() && CC == ISD::SETGT)) &&
-        N0 == N2 && N3.getOpcode() == ISD::SUB && N0 == N3.getOperand(1))
-      SubC = dyn_cast<ConstantSDNode>(N3.getOperand(0));
-    else if (((N1C->isNullValue() && (CC == ISD::SETLT || CC == ISD::SETLE)) ||
-              (N1C->isOne() && CC == ISD::SETLT)) &&
-             N0 == N3 && N2.getOpcode() == ISD::SUB && N0 == N2.getOperand(1))
-      SubC = dyn_cast<ConstantSDNode>(N2.getOperand(0));
-
-    EVT XType = N0.getValueType();
-    if (SubC && SubC->isNullValue() && XType.isInteger()) {
-      SDLoc DL(N0);
-      SDValue Shift = DAG.getNode(ISD::SRA, DL, XType,
-                                  N0,
-                                  DAG.getConstant(XType.getSizeInBits() - 1, DL,
-                                         getShiftAmountTy(N0.getValueType())));
-      SDValue Add = DAG.getNode(ISD::ADD, DL,
-                                XType, N0, Shift);
-      AddToWorklist(Shift.getNode());
-      AddToWorklist(Add.getNode());
-      return DAG.getNode(ISD::XOR, DL, XType, Add, Shift);
-    }
-  }
-
   // select_cc seteq X, 0, sizeof(X), ctlz(X) -> ctlz(X)
   // select_cc seteq X, 0, sizeof(X), ctlz_zero_undef(X) -> ctlz(X)
   // select_cc seteq X, 0, sizeof(X), cttz(X) -> cttz(X)
   // select_cc seteq X, 0, sizeof(X), cttz_zero_undef(X) -> cttz(X)
   // select_cc setne X, 0, ctlz(X), sizeof(X) -> ctlz(X)
   // select_cc setne X, 0, ctlz_zero_undef(X), sizeof(X) -> ctlz(X)
   // select_cc setne X, 0, cttz(X), sizeof(X) -> cttz(X)
   // select_cc setne X, 0, cttz_zero_undef(X), sizeof(X) -> cttz(X)

lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

private:
   SDValue ExpandFABS(SDNode *Node) const;
   SDValue ExpandLegalINT_TO_FP(bool isSigned, SDValue Op0, EVT DestVT,
                                const SDLoc &dl);
   SDValue PromoteLegalINT_TO_FP(SDValue LegalOp, EVT DestVT, bool isSigned,
                                 const SDLoc &dl);
   SDValue PromoteLegalFP_TO_INT(SDValue LegalOp, EVT DestVT, bool isSigned,
                                 const SDLoc &dl);
 
+  SDValue ExpandABS(SDNode *Node, const SDLoc &dl);
+
   SDValue ExpandBITREVERSE(SDValue Op, const SDLoc &dl);
   SDValue ExpandBSWAP(SDValue Op, const SDLoc &dl);
   SDValue ExpandBitCount(unsigned Opc, SDValue Op, const SDLoc &dl);
 
   SDValue ExpandExtractFromVectorThroughStack(SDValue Op);
   SDValue ExpandInsertToVectorThroughStack(SDValue Op);
   SDValue ExpandVectorBuildThroughStack(SDNode* Node);
 
SDValue SelectionDAGLegalize::PromoteLegalFP_TO_INT(SDValue LegalOp, EVT DestVT,
   // Okay, we found the operation and type to use.
   SDValue Operation = DAG.getNode(OpToUse, dl, NewOutTy, LegalOp);
 
   // Truncate the result of the extended FP_TO_*INT operation to the desired
   // size.
   return DAG.getNode(ISD::TRUNCATE, dl, DestVT, Operation);
 }
 
+/// Expand the ABS node to SRA + ADD + XOR nodes.
+/// (ABS x) -> (XOR (ADD x, (SRA x, type_size)), (SRA x, type_size))
+SDValue SelectionDAGLegalize::ExpandABS(SDNode *Node, const SDLoc &dl) {
+  EVT VT = Node->getValueType(0);
+  SDValue N0 = Node->getOperand(0);
+
+  SDValue Shift = DAG.getNode(ISD::SRA, dl, VT, N0,
+                              DAG.getConstant(VT.getSizeInBits() - 1, dl, VT));
+  SDValue Add = DAG.getNode(ISD::ADD, dl, VT, N0, Shift);
+
+  return DAG.getNode(ISD::XOR, dl, VT, Add, Shift);
+}
+
 /// Legalize a BITREVERSE scalar/vector operation as a series of mask + shifts.
 SDValue SelectionDAGLegalize::ExpandBITREVERSE(SDValue Op, const SDLoc &dl) {
   EVT VT = Op.getValueType();
   EVT SHVT = TLI.getShiftAmountTy(VT, DAG.getDataLayout());
   unsigned Sz = VT.getScalarSizeInBits();
 
   SDValue Tmp, Tmp2, Tmp3;
 

 
 bool SelectionDAGLegalize::ExpandNode(SDNode *Node) {
   LLVM_DEBUG(dbgs() << "Trying to expand node\n");
   SmallVector<SDValue, 8> Results;
   SDLoc dl(Node);
   SDValue Tmp1, Tmp2, Tmp3, Tmp4;
   bool NeedInvert;
   switch (Node->getOpcode()) {
+  case ISD::ABS:
+    Results.push_back(ExpandABS(Node, dl));
+    break;
   case ISD::CTPOP:
   case ISD::CTLZ:
   case ISD::CTLZ_ZERO_UNDEF:
   case ISD::CTTZ:
   case ISD::CTTZ_ZERO_UNDEF:
     Tmp1 = ExpandBitCount(Node->getOpcode(), Node->getOperand(0), dl);
     Results.push_back(Tmp1);
     break;

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

#endif
   case ISD::UADDO:
   case ISD::USUBO:       Res = PromoteIntRes_UADDSUBO(N, ResNo); break;
   case ISD::SMULO:
   case ISD::UMULO:       Res = PromoteIntRes_XMULO(N, ResNo); break;
 
   case ISD::ADDCARRY:
   case ISD::SUBCARRY:    Res = PromoteIntRes_ADDSUBCARRY(N, ResNo); break;
 
+  case ISD::ABS:         Res = PromoteIntRes_ABS(N); break;
+
   case ISD::ATOMIC_LOAD:
     Res = PromoteIntRes_Atomic0(cast<AtomicSDNode>(N)); break;
 
   case ISD::ATOMIC_LOAD_ADD:
   case ISD::ATOMIC_LOAD_SUB:
   case ISD::ATOMIC_LOAD_AND:
   case ISD::ATOMIC_LOAD_CLR:
   case ISD::ATOMIC_LOAD_OR:
SDValue Res = DAG.getNode(N->getOpcode(), SDLoc(N), DAG.getVTList(ValueVTs),
                             LHS, RHS, N->getOperand(2));
 
   // Update the users of the original carry/borrow value.
   ReplaceValueWith(SDValue(N, 1), Res.getValue(1));
 
   return SDValue(Res.getNode(), 0);
 }
 
+SDValue DAGTypeLegalizer::PromoteIntRes_ABS(SDNode *N) {
+  SDValue Op0 = SExtPromotedInteger(N->getOperand(0));
+  return DAG.getNode(ISD::ABS, SDLoc(N), Op0.getValueType(), Op0);
+}
+
 SDValue DAGTypeLegalizer::PromoteIntRes_XMULO(SDNode *N, unsigned ResNo) {
   // Promote the overflow bit trivially.
   if (ResNo == 1)
     return PromoteIntRes_Overflow(N);
 
   SDValue LHS = N->getOperand(0), RHS = N->getOperand(1);
   SDLoc DL(N);
   EVT SmallVT = LHS.getValueType();
#endif
   case ISD::VAARG:              ExpandRes_VAARG(N, Lo, Hi); break;
 
   case ISD::ANY_EXTEND:  ExpandIntRes_ANY_EXTEND(N, Lo, Hi); break;
   case ISD::AssertSext:  ExpandIntRes_AssertSext(N, Lo, Hi); break;
   case ISD::AssertZext:  ExpandIntRes_AssertZext(N, Lo, Hi); break;
   case ISD::BITREVERSE:  ExpandIntRes_BITREVERSE(N, Lo, Hi); break;
   case ISD::BSWAP:       ExpandIntRes_BSWAP(N, Lo, Hi); break;
   case ISD::Constant:    ExpandIntRes_Constant(N, Lo, Hi); break;
+  case ISD::ABS:         ExpandIntRes_ABS(N, Lo, Hi); break;
   case ISD::CTLZ_ZERO_UNDEF:
   case ISD::CTLZ:        ExpandIntRes_CTLZ(N, Lo, Hi); break;
   case ISD::CTPOP:       ExpandIntRes_CTPOP(N, Lo, Hi); break;
   case ISD::CTTZ_ZERO_UNDEF:
   case ISD::CTTZ:        ExpandIntRes_CTTZ(N, Lo, Hi); break;
   case ISD::FLT_ROUNDS_: ExpandIntRes_FLT_ROUNDS(N, Lo, Hi); break;
   case ISD::FP_TO_SINT:  ExpandIntRes_FP_TO_SINT(N, Lo, Hi); break;
   case ISD::FP_TO_UINT:  ExpandIntRes_FP_TO_UINT(N, Lo, Hi); break;
   case ISD::LOAD:        ExpandIntRes_LOAD(cast<LoadSDNode>(N), Lo, Hi); break;
   case ISD::MUL:         ExpandIntRes_MUL(N, Lo, Hi); break;
void DAGTypeLegalizer::ExpandIntRes_Constant(SDNode *N,
   bool IsTarget = Constant->isTargetOpcode();
   bool IsOpaque = Constant->isOpaque();
   SDLoc dl(N);
   Lo = DAG.getConstant(Cst.trunc(NBitWidth), dl, NVT, IsTarget, IsOpaque);
   Hi = DAG.getConstant(Cst.lshr(NBitWidth).trunc(NBitWidth), dl, NVT, IsTarget,
                        IsOpaque);
 }
 
+void DAGTypeLegalizer::ExpandIntRes_ABS(SDNode *N, SDValue &Lo, SDValue &Hi) {
+  SDLoc dl(N);
+  SDValue Tmp;
+
+  GetExpandedInteger(N->getOperand(0), Lo, Tmp);
+  EVT OpType = Tmp.getValueType();
+
+  Hi = DAG.getNode(ISD::ABS, dl, OpType, Tmp);
+  // Lo = Hi==abs(Hi) ? Lo : 0 - Lo;
+  Lo = DAG.getSelectCC(
+        dl, Tmp, Hi, Lo,
+        DAG.getNode(ISD::SUB, dl, OpType, DAG.getConstant(0, dl, OpType), Lo),
+        ISD::SETEQ);
+}
+
 void DAGTypeLegalizer::ExpandIntRes_CTLZ(SDNode *N,
                                          SDValue &Lo, SDValue &Hi) {
   SDLoc dl(N);
   // ctlz (HiLo) -> Hi != 0 ? ctlz(Hi) : (ctlz(Lo)+32)
   GetExpandedInteger(N->getOperand(0), Lo, Hi);
   EVT NVT = Lo.getValueType();
 
   SDValue HiNotZero = DAG.getSetCC(dl, getSetCCResultType(NVT), Hi,

lib/CodeGen/SelectionDAG/LegalizeTypes.h

private:
   SDValue PromoteIntRes_SRA(SDNode *N);
   SDValue PromoteIntRes_SRL(SDNode *N);
   SDValue PromoteIntRes_TRUNCATE(SDNode *N);
   SDValue PromoteIntRes_UADDSUBO(SDNode *N, unsigned ResNo);
   SDValue PromoteIntRes_ADDSUBCARRY(SDNode *N, unsigned ResNo);
   SDValue PromoteIntRes_UNDEF(SDNode *N);
   SDValue PromoteIntRes_VAARG(SDNode *N);
   SDValue PromoteIntRes_XMULO(SDNode *N, unsigned ResNo);
+  SDValue PromoteIntRes_ABS(SDNode *N);
 
   // Integer Operand Promotion.
   bool PromoteIntegerOperand(SDNode *N, unsigned OpNo);
   SDValue PromoteIntOp_ANY_EXTEND(SDNode *N);
   SDValue PromoteIntOp_ATOMIC_STORE(AtomicSDNode *N);
   SDValue PromoteIntOp_BITCAST(SDNode *N);
   SDValue PromoteIntOp_BUILD_PAIR(SDNode *N);
   SDValue PromoteIntOp_BR_CC(SDNode *N, unsigned OpNo);
private:
   void SetExpandedInteger(SDValue Op, SDValue Lo, SDValue Hi);
 
   // Integer Result Expansion.
   void ExpandIntegerResult(SDNode *N, unsigned ResNo);
   void ExpandIntRes_ANY_EXTEND        (SDNode *N, SDValue &Lo, SDValue &Hi);
   void ExpandIntRes_AssertSext        (SDNode *N, SDValue &Lo, SDValue &Hi);
   void ExpandIntRes_AssertZext        (SDNode *N, SDValue &Lo, SDValue &Hi);
   void ExpandIntRes_Constant          (SDNode *N, SDValue &Lo, SDValue &Hi);
+  void ExpandIntRes_ABS               (SDNode *N, SDValue &Lo, SDValue &Hi);
   void ExpandIntRes_CTLZ              (SDNode *N, SDValue &Lo, SDValue &Hi);
   void ExpandIntRes_CTPOP             (SDNode *N, SDValue &Lo, SDValue &Hi);
   void ExpandIntRes_CTTZ              (SDNode *N, SDValue &Lo, SDValue &Hi);
   void ExpandIntRes_LOAD          (LoadSDNode *N, SDValue &Lo, SDValue &Hi);
   void ExpandIntRes_READCYCLECOUNTER  (SDNode *N, SDValue &Lo, SDValue &Hi);
   void ExpandIntRes_SIGN_EXTEND       (SDNode *N, SDValue &Lo, SDValue &Hi);
   void ExpandIntRes_SIGN_EXTEND_INREG (SDNode *N, SDValue &Lo, SDValue &Hi);
   void ExpandIntRes_TRUNCATE          (SDNode *N, SDValue &Lo, SDValue &Hi);

lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp

class VectorLegalizer {
   SDValue ExpandSIGN_EXTEND_VECTOR_INREG(SDValue Op);
 
   /// Implement expansion for ZERO_EXTEND_VECTOR_INREG.
   ///
   /// Shuffles the low lanes of the operand into place and blends zeros into
   /// the remaining lanes, finally bitcasting to the proper type.
   SDValue ExpandZERO_EXTEND_VECTOR_INREG(SDValue Op);
 
+  /// Implement expand-based legalization of ABS vector operations.
+  ///
+  /// (ABS x) --> (XOR (ADD x, (SRA x, sizeof(x)-1)), (SRA x, sizeof(x)-1)).
+  SDValue ExpandABS(SDValue Op);
+
   /// Expand bswap of vectors into a shuffle if legal.
   SDValue ExpandBSWAP(SDValue Op);
 
   /// Implement vselect in terms of XOR, AND, OR when blend is not
   /// supported by the target.
   SDValue ExpandVSELECT(SDValue Op);
   SDValue ExpandSELECT(SDValue Op);
   SDValue ExpandLoad(SDValue Op);
SDValue VectorLegalizer::LegalizeOp(SDValue Op) {
   case ISD::FADD:
   case ISD::FSUB:
   case ISD::FMUL:
   case ISD::FDIV:
   case ISD::FREM:
   case ISD::AND:
   case ISD::OR:
   case ISD::XOR:
+  case ISD::ABS:
   case ISD::SHL:
   case ISD::SRA:
   case ISD::SRL:
   case ISD::ROTL:
   case ISD::ROTR:
   case ISD::BSWAP:
   case ISD::BITREVERSE:
   case ISD::CTLZ:
SDValue VectorLegalizer::Expand(SDValue Op) {
   case ISD::SIGN_EXTEND_INREG:
     return ExpandSEXTINREG(Op);
   case ISD::ANY_EXTEND_VECTOR_INREG:
     return ExpandANY_EXTEND_VECTOR_INREG(Op);
   case ISD::SIGN_EXTEND_VECTOR_INREG:
     return ExpandSIGN_EXTEND_VECTOR_INREG(Op);
   case ISD::ZERO_EXTEND_VECTOR_INREG:
     return ExpandZERO_EXTEND_VECTOR_INREG(Op);
+  case ISD::ABS:
+    return ExpandABS(Op);
   case ISD::BSWAP:
     return ExpandBSWAP(Op);
   case ISD::VSELECT:
     return ExpandVSELECT(Op);
   case ISD::SELECT:
     return ExpandSELECT(Op);
   case ISD::UINT_TO_FP:
     return ExpandUINT_TO_FLOAT(Op);

 
 static void createBSWAPShuffleMask(EVT VT, SmallVectorImpl<int> &ShuffleMask) {
   int ScalarSizeInBytes = VT.getScalarSizeInBits() / 8;
   for (int I = 0, E = VT.getVectorNumElements(); I != E; ++I)
     for (int J = ScalarSizeInBytes - 1; J >= 0; --J)
       ShuffleMask.push_back((I * ScalarSizeInBytes) + J);
 }
 
+SDValue VectorLegalizer::ExpandABS(SDValue Op) {
+  EVT VT = Op.getValueType();
+  SDValue N0 = Op.getOperand(0);
+  SDLoc DL(Op);
+
+  SDValue Shift =
+      DAG.getNode(ISD::SRA, DL, VT, N0,
+                  DAG.getConstant(VT.getScalarSizeInBits() - 1, DL, VT));
+  SDValue Add = DAG.getNode(ISD::ADD, DL, VT, N0, Shift);
+
+  return DAG.getNode(ISD::XOR, DL, VT, Add, Shift);
+}
+
 SDValue VectorLegalizer::ExpandBSWAP(SDValue Op) {
   EVT VT = Op.getValueType();
 
   // Generate a byte wise shuffle mask for the BSWAP.
   SmallVector<int, 16> ShuffleMask;
   createBSWAPShuffleMask(VT, ShuffleMask);
   EVT ByteVT = EVT::getVectorVT(*DAG.getContext(), MVT::i8, ShuffleMask.size());
 

lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp

case ISD::VECTOR_SHUFFLE:
     break;
 
   case ISD::ANY_EXTEND_VECTOR_INREG:
   case ISD::SIGN_EXTEND_VECTOR_INREG:
   case ISD::ZERO_EXTEND_VECTOR_INREG:
     SplitVecRes_ExtVecInRegOp(N, Lo, Hi);
     break;
 
+  case ISD::ABS:
   case ISD::BITREVERSE:
   case ISD::BSWAP:
   case ISD::CTLZ:
   case ISD::CTTZ:
   case ISD::CTLZ_ZERO_UNDEF:
   case ISD::CTTZ_ZERO_UNDEF:
   case ISD::CTPOP:
   case ISD::FABS:

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

void SelectionDAGBuilder::visitSelect(const User &I) {
   SmallVector<SDValue, 4> Values(NumValues);
   SDValue Cond     = getValue(I.getOperand(0));
   SDValue LHSVal   = getValue(I.getOperand(1));
   SDValue RHSVal   = getValue(I.getOperand(2));
   auto BaseOps = {Cond};
   ISD::NodeType OpCode = Cond.getValueType().isVector() ?
     ISD::VSELECT : ISD::SELECT;
 
+  bool IsUnaryAbs = false;
+
   // Min/max matching is only viable if all output VTs are the same.
   if (std::equal(ValueVTs.begin(), ValueVTs.end(), ValueVTs.begin())) {
     EVT VT = ValueVTs[0];
     LLVMContext &Ctx = *DAG.getContext();
     auto &TLI = DAG.getTargetLoweringInfo();
 
     // We care about the legality of the operation after it has been type
     // legalized.
case SPF_FMAXNUM:
         else if (TLI.isOperationLegalOrCustom(ISD::FMAXNAN, VT))
           Opc = ISD::FMAXNAN;
         else if (UseScalarMinMax)
           Opc = TLI.isOperationLegalOrCustom(ISD::FMAXNUM, VT.getScalarType()) ?
             ISD::FMAXNUM : ISD::FMAXNAN;
         break;
       }
       break;
+    case SPF_ABS:
+      IsUnaryAbs = true;
+      Opc = ISD::ABS;
+      break;
+    case SPF_NABS:
+      // TODO: we need to produce sub(0, abs(X)).
     default: break;
     }
 
-    if (Opc != ISD::DELETED_NODE &&
+    if (!IsUnaryAbs && Opc != ISD::DELETED_NODE &&
         (TLI.isOperationLegalOrCustom(Opc, VT) ||
          (UseScalarMinMax &&
           TLI.isOperationLegalOrCustom(Opc, VT.getScalarType()))) &&
         // If the underlying comparison instruction is used by any other
         // instruction, the consumed instructions won't be destroyed, so it is
         // not profitable to convert to a min/max.
         hasOnlySelectUsers(cast<SelectInst>(I).getCondition())) {
       OpCode = Opc;
       LHSVal = getValue(LHS);
       RHSVal = getValue(RHS);
       BaseOps = {};
     }
+
+    if (IsUnaryAbs) {
+      OpCode = Opc;
+      LHSVal = getValue(LHS);
+      BaseOps = {};
+    }
   }
 
+  if (IsUnaryAbs) {
+    for (unsigned i = 0; i != NumValues; ++i) {
+      Values[i] =
+          DAG.getNode(OpCode, getCurSDLoc(),
+                      LHSVal.getNode()->getValueType(LHSVal.getResNo() + i),
+                      SDValue(LHSVal.getNode(), LHSVal.getResNo() + i));
+    }
+  } else {
     for (unsigned i = 0; i != NumValues; ++i) {
       SmallVector<SDValue, 3> Ops(BaseOps.begin(), BaseOps.end());
       Ops.push_back(SDValue(LHSVal.getNode(), LHSVal.getResNo() + i));
       Ops.push_back(SDValue(RHSVal.getNode(), RHSVal.getResNo() + i));
-    Values[i] = DAG.getNode(OpCode, getCurSDLoc(),
-                            LHSVal.getNode()->getValueType(LHSVal.getResNo()+i),
-                            Ops);
+      Values[i] = DAG.getNode(
+          OpCode, getCurSDLoc(),
+          LHSVal.getNode()->getValueType(LHSVal.getResNo() + i), Ops);
+    }
   }
 
   setValue(&I, DAG.getNode(ISD::MERGE_VALUES, getCurSDLoc(),
                            DAG.getVTList(ValueVTs), Values));
 }
 
 void SelectionDAGBuilder::visitTrunc(const User &I) {
   // TruncInst cannot be a no-op cast because sizeof(src) > sizeof(dest).