This is an archive of the discontinued LLVM Phabricator instance.

[CodeGen][SelectionDAG] Flip Booleans More Often
AbandonedPublic

Authored by Pierre-vh on Apr 1 2020, 2:13 AM.

Details

Summary

This change should increase the chance that something like not(setcc) becomes setcc with an opposite cond.
This works by allowing truncation when calling isConstOrConstSplat and using the resulting ConstantSDNode's value type (instead of the SDNode's value type) to determine if the flip is possible or not in the extractBooleanFlip function.

Note that I'm unsure about this patch, so I'll need some feedback.
It looks fine to me, and it improves codegen in the ARM backend without affecting other backends, but I'm not sure this change is correct.
Is this a good place for this fix, or should this fix be done in the ARM backend instead?

Example result:

// Before the patch
vpnot                    // VPR = !VPR
vpsel q0, q1, q2  // q0 = VPR ? q1 : q2
// After the patch
vpsel q0, q2, q1 // q0 = VPR ? q2 : q1

Diff Detail

Event Timeline

Pierre-vh created this revision.Apr 1 2020, 2:13 AM
Pierre-vh marked an inline comment as done.
Pierre-vh added inline comments.
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2611

This is an accidental change, It's fixed locally

Please update your description - you're not explaining the mechanics of your change at all.

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

Might be a good idea to tag the bools here:

isConstOrConstSplat(V.getOperand(1), /*AllowUndefs*/false, /*AllowTruncation*/true)
Pierre-vh edited the summary of this revision. (Show Details)Apr 1 2020, 2:48 AM

Please update your description - you're not explaining the mechanics of your change at all.

Sure, I tried to update it, but to be honest, I don't fully understand the impact of the change myself, which is why I'm asking for help.
I only did this change because it allowed https://reviews.llvm.org/D77202 to work as intended (without it, the nots it creates aren't folded).

Pierre-vh updated this revision to Diff 254158.Apr 1 2020, 4:04 AM
  • Rebased the patch
  • Removed the deleted blank line
  • Tagged the bools in the isConstOrConstSplat call
Pierre-vh marked an inline comment as done.Apr 1 2020, 4:04 AM

We have to call getBooleanContents on the vector type, not the vector element type. On ARM, a boolean in a vector is ZeroOrNegativeOneBooleanContent. A scalar boolean on its own is ZeroOrOneBooleanContent. If you choose incorrectly, that's a potential miscompile. (Not sure why it isn't showing up as a regression test change for other targets; maybe the specific VSELECT pattern in question is rare after legalization.)

Maybe the code should be truncating the APInt before it checks isAllOnesValue(), though. For a boolean, isOne() and isAllOnesValue() should be equivalent.

We have to call getBooleanContents on the vector type, not the vector element type. On ARM, a boolean in a vector is ZeroOrNegativeOneBooleanContent. A scalar boolean on its own is ZeroOrOneBooleanContent. If you choose incorrectly, that's a potential miscompile. (Not sure why it isn't showing up as a regression test change for other targets; maybe the specific VSELECT pattern in question is rare after legalization.)

Maybe the code should be truncating the APInt before it checks isAllOnesValue(), though. For a boolean, isOne() and isAllOnesValue() should be equivalent.

Thank you for this explanation. Is the kind of change you have in mind? (I tested it and it also works)

ConstantSDNode *Const = isConstOrConstSplat(V.getOperand(1),
                                            /*AllowUndefs*/ false,
                                            /*AllowTruncation*/ true);
if (!Const)
  return SDValue();
EVT VT = V.getValueType();

bool IsFlip = false;
switch(TLI.getBooleanContents(VT)) {
  case TargetLowering::ZeroOrOneBooleanContent:
    IsFlip = Const->isOne();
    break;
  case TargetLowering::ZeroOrNegativeOneBooleanContent:
    IsFlip =  Const->getAPIntValue()
                .sextOrTrunc(Const->getNumValues())
                .isAllOnesValue();
    break;
  case TargetLowering::UndefinedBooleanContent:
    IsFlip = (Const->getAPIntValue() & 0x01) == 1;
    break;
}

That's the right idea. getNumValues() seems wrong, though.

That's the right idea. getNumValues() seems wrong, though.

What should I use instead?
(Sorry if it's a lot questions - I'm pretty new to the SelectionDAG so I'm not entirely sure what the best choice is here.)

VT.getScalarSizeInBits(), I think.

I understand you're new to this, but please try to take a little more time to understand what the various APIs you're calling actually do.

Pierre-vh updated this revision to Diff 254721.Apr 3 2020, 1:06 AM

Here is the change using VT.getScalarSizeInBits().

Thank you very much for your help.
I'll try to be more careful next time and spend more time reading the documentation.

efriedma added inline comments.Apr 3 2020, 11:51 AM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2602

For consistency, we should probably change the ZeroOrOneBooleanContent case as well. Not sure it has any practical impact, given the way we normally choose to build constants, but it would be easier to understand. Maybe move the Const->getAPIntValue().sextOrTrunc(VT.getScalarSizeInBits()) expression out of the switch so it can be used in both cases.

Pierre-vh updated this revision to Diff 255283.Apr 6 2020, 4:11 AM
  • Moved the Const->getAPIntValue().sextOrTrunc(VT.getScalarSizeInBits()) expression out of the switch, storing it in ConstValue
  • Changed the ZeroOrOneBooleanContent case to use ConstValue as well
Pierre-vh marked an inline comment as done.Apr 6 2020, 4:12 AM
efriedma accepted this revision.Apr 6 2020, 11:43 AM

LGTM.

Not sure if you have commit access. If you want me to commit this for you, please let me know how to credit you in the "Author" line of the git commit (name and email).

This revision is now accepted and ready to land.Apr 6 2020, 11:43 AM
Pierre-vh added a comment.EditedApr 7 2020, 12:21 AM

LGTM.

Not sure if you have commit access. If you want me to commit this for you, please let me know how to credit you in the "Author" line of the git commit (name and email).

It's fine, I have commit access and I just pushed it. Thank you very much for your help on this patch!

This revision was automatically updated to reflect the committed changes.
This revision is now accepted and ready to land.Apr 7 2020, 1:14 AM
thakis added a subscriber: thakis.Apr 7 2020, 3:37 AM

I had to revert this change because it seemed to have caused multiple buildbot failures:

This seems to repro locally when running check-llvm. llc hangs in an infinite loop for e.g. llvm/test/CodeGen/X86/avx512-vec-cmp.ll

I had to revert this change because it seemed to have caused multiple buildbot failures:

This seems to repro locally when running check-llvm. llc hangs in an infinite loop for e.g. llvm/test/CodeGen/X86/avx512-vec-cmp.ll

Exactly, llvm/test/CodeGen/X86/avx512-select.ll also causes an infinite loop in pr31515 with this run line:
; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=avx512bw | FileCheck %s --check-prefixes=X64,X64-AVX512BW

I've found that the DAGCombiner is transforming a VSELECT Cond, A, B into something close to VSELECT !Cond, B, A in some specific conditions and it just goes into an infinite loop (due to this change), swapping the condition over and over again, creating nodes endlessly.
I'm working on it, I'll try to find a fix and update this patch when I have a fix, or if I get stuck.

Pierre-vh abandoned this revision.Apr 7 2020, 7:07 AM

Hello again,

I found the source of the issue. It was a AVX512 thing in the X86 Backend.
There is a transformation in X86ISelLowering.cpp, around line 39476, that transforms a vselect cond, a, b into vselect !cond, b, a in _some_ situations.
It caused an infinite loop with this change: the X86 Combiner was making the change, the DAGCombiner was reverting it, and so on.

I'm going to abandon this revision in favor of a ARMISelLowering.cpp patch that implements a similar transform for ARM/MVE only. It'll be much safer.

Thanks again for all the help, and sorry for the trouble!