Page MenuHomePhabricator

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

Authored by ikulagin on Jul 26 2018, 12:40 AM.

Details

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))).

  1. 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.
  2. Add combine and legalization of ABS nodes for Thumb arch.
  3. Extend 'matchSelectPattern' to recognize the ABS patterns with ICMP_SGE condition.

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

Diff Detail

Repository
rL LLVM

Event Timeline

ikulagin created this revision.Jul 26 2018, 12:40 AM

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.

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

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
1435–1437

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

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
1435–1437

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

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

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
2185

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
2946

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

3009

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 added inline comments.Jul 27 2018, 4:21 AM
lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
3009

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.

3013

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.

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
2185

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
2946

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

3009

Ok, I'll remove it.

3013

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

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
2185

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
2946

Yes, it would be more clear.

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
2185

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 added inline comments.Jul 30 2018, 4:56 AM
lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
1435–1437

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
3031

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 added inline comments.Jul 30 2018, 10:38 AM
lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
3031

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 updated this revision to Diff 158522.Aug 1 2018, 7:01 AM
ikulagin marked 11 inline comments as done.
ikulagin edited the summary of this revision. (Show Details)

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 updated this revision to Diff 158965.Aug 3 2018, 3:36 AM
ikulagin retitled this revision from [SelectionDAG][X86] Handle unary SelectPatternFlavor for ABS case in SelectionDAGBuilder::visitSelect. to [SelectionDAG] Handle unary SelectPatternFlavor for ABS case in SelectionDAGBuilder::visitSelect..
ikulagin edited the summary of this revision. (Show Details)

Rebase the patch

craig.topper added inline comments.Aug 10 2018, 3:42 PM
lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
2192

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.

@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 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
2192

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 updated this revision to Diff 163980.Sep 5 2018, 1:49 AM

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

RKSimon added inline comments.Sep 12 2018, 5:06 AM
lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
2511

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

RKSimon added inline comments.Sep 13 2018, 1:55 AM
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.

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

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 added inline comments.Oct 26 2018, 1:41 AM
lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
2514

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.

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.

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 marked 3 inline comments as done.Oct 27 2018, 5:49 AM
ikulagin updated this revision to Diff 171439.Oct 28 2018, 1:47 PM
ikulagin edited the summary of this revision. (Show Details)

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 updated this revision to Diff 171631.Oct 29 2018, 8:32 PM
ikulagin edited the summary of this revision. (Show Details)

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

RKSimon added inline comments.Oct 30 2018, 3:31 AM
lib/CodeGen/SelectionDAG/TargetLowering.cpp
4458

The shift constant needs to use a getShiftAmountTy type

lib/Target/ARM/ARMISelLowering.cpp
1210

Don't include commented out code

10309

Just call TargetLowering::expandABS ?

lib/Target/X86/X86ISelLowering.cpp
26030

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

test/CodeGen/Thumb/iabs.ll
76

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

spatel added inline comments.Oct 30 2018, 8:41 AM
lib/Analysis/ValueTracking.cpp
4856

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 added inline comments.Oct 30 2018, 12:44 PM
lib/Target/ARM/ARMISelLowering.cpp
1210

Sorry for that, I did not notice.

lib/Target/X86/X86ISelLowering.cpp
26030

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

test/CodeGen/Thumb/iabs.ll
76

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

ikulagin added inline comments.Oct 30 2018, 1:30 PM
lib/Analysis/ValueTracking.cpp
4856

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};
@ikulagin are you still looking at this?

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

@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?

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