[DAGCombine] Prevent the transform of combine for multi-use operand

[spatel]

Summary

This is based on example in https://bugs.llvm.org/show_bug.cgi?id=51321

[lebedev.ri]

1. Please upload all patches with full context. (-U99999)
2. I do not understand how one-use check here is acting as a correctness check

[dmgreen]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4944

N0->hasOneUse() would probably be better, to check the Node has one use not the SDValue. (Although here it likely won't make much difference.)

llvm/test/CodeGen/AArch64/arm64-srl-and.ll

2

This needs a triple, and likely doesn't need a -mcpu.

11

Has this deleted some of the check lines?

[lebedev.ri]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4944

*Why* does it matter for the correctness whether the node has other uses or not?
The peephole should only affect the current root use we started with,
and not affect any other uses whatsoever.

[craig.topper]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4944

There is a CombineTo call on N0. That will affect all users of N0.

[lebedev.ri]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4944

Aha, that indeed explains it, and should have been stated in the patch's description, thanks.
But why is it there?
Sounds like this transform should instead be

if (TLI.isLegalAddImmediate(ADDC.getSExtValue())) {
  SDLoc DL0(N0);
  SDValue NewAdd =
    DAG.getNode(ISD::ADD, DL0, VT,
                N0.getOperand(0), DAG.getConstant(ADDC, DL, VT));
  return DAG.getNode(ISD::AND, DL0, VT, NewAdd, N1);
}

[Allen]

In D107692#2932650, @lebedev.ri wrote:

1. Please upload all patches with full context. (-U99999)
2. I do not understand how one-use check here is acting as a correctness check

sorry for late reply, but I think you already know. as the node t46 has multi use, so add t45, 65535 to sub t45, -1 is not save in this case.

t64: i32 = srl t46, Constant:i64<16>

  t14: i32 = and t46, t64
t46: i32 = add t45, Constant:i32<65535>

llvm/test/CodeGen/AArch64/arm64-srl-and.ll

11

yes, as others are not the kernel code about this issue.

[spatel]

The transform that we want to make can be shown with this example (and so this test should be added somewhere as a preliminary commit):

define i32 @src(i32 %x, i32 %y) {
  %add = add i32 %x, 65535 ; --> turn this into -1 because that can be encoded as an immediate operand
  %srl = lshr i32 %y, 16
  %r = and i32 %srl, %add
  ret i32 %r
}

https://alive2.llvm.org/ce/z/Ehadpq

For AArch and PowerPC and possibly all targets (x86 would benefit too), we want this to use a -1 (or sub 1), not an add 65535:

sub w8, w0, #1
and w0, w8, w1, lsr #16

vs.

mov w8, #65535
add w8, w0, w8
and w0, w8, w1, lsr #16

But if you try this test with main today, it doesn't work:
https://godbolt.org/z/fe7h1zYv6

...because this transform has another bug: it doesn't match the commuted variant.

Over in PR51321, I mentioned that I could delete the whole transform and not see any test changes. That's because SimplifyDemandedBits does the same transform. But it has a similar problem - it only catches the case where it processes the shift before it sees the add. So it misses the same commuted pattern. I'm not sure how we'd fix that in DemandedBits; it seems like a generic ordering problem for commutative ops.

So this transform has at least 3 problems (assuming we want to keep it instead of enhancing DemandedBits):

1. It miscompiles the multi-use case because it is coded weirdly and missed a constraint.
2. It misses the commuted case.
3. It misses what is likely profitable for all targets by overspecifying the legality constraints.

[Allen]

this patch is expected to fix the runtime bug, and more cases to be optimized can be consider in another issue :)

When we use w8 replace the w1 , then the following two fragment codes is not equal.
so if the SimplifyDemandedBits does the same transform, a patch can be land separate to fix this firstly to avoid the runtime bug ?

sub w8, w0, #1
and w0, w8, w8, lsr #16

vs.

mov w8, #65535
add w8, w0, w8
and w0, w8, w8, lsr #16

llvm/test/CodeGen/AArch64/arm64-srl-and.ll

2

thanks, done

[RKSimon]

Please can you regenerate the diff with context

llvm/test/CodeGen/AArch64/arm64-srl-and.ll

7

do you need all the dso_local/noundef/local_unnamed_addr attributes?

[lebedev.ri]

Please,

1. either add a comment explaining why the one-use check needed
2. or rewrite the transform the right way, so that the lack of one-use check shows up as extra instruction bloat and not a miscompilation

[spatel]

In D107692#2946669, @lebedev.ri wrote:

Please,

1. either add a comment explaining why the one-use check needed
2. or rewrite the transform the right way, so that the lack of one-use check shows up as extra instruction bloat and not a miscompilation

Since there's a visible miscompile, I'm ok with the quick/small fix since that will be an easy backport for the 13.0 release. But I agree that there should be a FIXME comment on this transform; it is clearly not ideal.

[Allen]

In D107692#2946669, @lebedev.ri wrote:

Please,

1. either add a comment explaining why the one-use check needed
2. or rewrite the transform the right way, so that the lack of one-use check shows up as extra instruction bloat and not a miscompilation

ok, I'll add a comment as compare between current change and rewritting the transform , current change has more effective code (less inst) .

the following code is with rewritting the transform in your comment.

adrp	x8, :got:g
	ldr	x8, [x8, :got_lo12:g]
	mov	w9, #50
	mov	w10, #65535
	ldrh	w8, [x8]
	eor	w9, w8, w9
	add	w9, w9, w10
	sub	w8, w8, #1
	and	w0, w8, w9, lsr #16
	ret

llvm/test/CodeGen/AArch64/arm64-srl-and.ll

7

yes, they are not essential, and i'll delete them later

[RKSimon]

llvm/test/CodeGen/AArch64/arm64-srl-and.ll

4

Please rephrase this and actually explain the "dagcombine" you're referring to in the comment

[lebedev.ri]

llvm/test/CodeGen/AArch64/arm64-srl-and.ll

1

Please precommit this test before landing the fix

[lebedev.ri]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5152–5156

How can this FIXME ever be addressed, given that there already is an one-use check?

[spatel]

Reverse ping @Allen
I'm not sure if we have already missed the deadline for 13.0, but we really should fix this miscompile. Someone can commandeer the patch if you can't work on it (just need to fix the comments?).

[spatel]

Same minimal fix (hopefully can still make the release branch), but updated the code and test comments

[lebedev.ri]

LG, thank you.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::hoistLogicOpWithSameOpcodeHands(SDNode *N) {
   // If both shuffles use the same mask, and both shuffle within a single
   // vector, then it is worthwhile to move the swizzle after the operation.
   // The type-legalizer generates this pattern when loading illegal
   // vector types from memory. In many cases this allows additional shuffle
   // optimizations.
   // There are other cases where moving the shuffle after the xor/and/or
   // is profitable even if shuffles don't perform a swizzle.
   // If both shuffles use the same mask, and both shuffles have the same first
   // or second operand, then it might still be profitable to move the shuffle
   // after the xor/and/or operation.
   if (HandOpcode == ISD::VECTOR_SHUFFLE && Level < AfterLegalizeDAG) {
     auto *SVN0 = cast<ShuffleVectorSDNode>(N0);
     auto *SVN1 = cast<ShuffleVectorSDNode>(N1);
     assert(X.getValueType() == Y.getValueType() &&
            "Inputs to shuffles are not the same type");
 
     // Check that both shuffles use the same mask. The masks are known to be of
SDValue DAGCombiner::visitANDLike(SDValue N0, SDValue N1, SDNode *N) {
 
   // fold (and x, undef) -> 0
   if (N0.isUndef() || N1.isUndef())
     return DAG.getConstant(0, DL, VT);
 
   if (SDValue V = foldLogicOfSetCCs(true, N0, N1, DL))
     return V;
 
+  // TODO: Rewrite this to return a new 'AND' instead of using CombineTo.
   if (N0.getOpcode() == ISD::ADD && N1.getOpcode() == ISD::SRL &&
-      VT.getSizeInBits() <= 64) {
+      VT.getSizeInBits() <= 64 && N0->hasOneUse()) {
     if (ConstantSDNode *ADDI = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
       if (ConstantSDNode *SRLI = dyn_cast<ConstantSDNode>(N1.getOperand(1))) {
         // Look for (and (add x, c1), (lshr y, c2)). If C1 wasn't a legal
         // immediate for an add, but it is legal if its top c2 bits are set,
         // transform the ADD so the immediate doesn't need to be materialized
         // in a register.
         APInt ADDC = ADDI->getAPIntValue();
         APInt SRLC = SRLI->getAPIntValue();
         if (ADDC.getMinSignedBits() <= 64 &&
             SRLC.ult(VT.getSizeInBits()) &&

llvm/test/CodeGen/AArch64/arm64-srl-and.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=aarch64-linux-gnu -O3 < %s | FileCheck %s
 
-; Disable the dagcombine if operand has multi use
+; This used to miscompile:
+; The 16-bit -1 should not become 32-bit -1 (sub w8, w8, #1).
 
 @g = global i16 0, align 4
 define i32 @srl_and()  {
 ; CHECK-LABEL: srl_and:
 ; CHECK:       // %bb.0: // %entry
 ; CHECK-NEXT:    adrp x8, :got:g
 ; CHECK-NEXT:    ldr x8, [x8, :got_lo12:g]
 ; CHECK-NEXT:    mov w9, #50
 ; CHECK-NEXT:    ldrh w8, [x8]
 ; CHECK-NEXT:    eor w8, w8, w9
-; CHECK-NEXT:    sub w8, w8, #1
+; CHECK-NEXT:    mov w9, #65535
+; CHECK-NEXT:    add w8, w8, w9
 ; CHECK-NEXT:    and w0, w8, w8, lsr #16
 ; CHECK-NEXT:    ret
 entry:
   %0 = load i16, i16* @g, align 4
   %1 = xor i16 %0, 50
   %tobool = icmp ne i16 %1, 0
   %lor.ext = zext i1 %tobool to i32
   %sub = add i16 %1, -1
 
   %srl = zext i16 %sub to i32
   %and = and i32 %srl, %lor.ext
 
   ret i32 %and
 }