[DAGCombiner] Rebuild (setcc x, y, ==) from (xor (xor x, y), 1)

[rogfer01]

Summary

The existing code already considered this case. Unfortunately a typo in the condition prevents it from triggering. Also the existing code, had it run, forgot to do the folding.

This fixes PR42876

[lebedev.ri]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13526–13527

// xor (xor %a, %b), -1

[spatel]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13495–13499

That comment makes me nervous given the logic. Can we assert that N has one user and that user is a br?

13526–13527

The code is checking for '1' not '-1'.
Can we assert that the types are i1 and/or the code should be changed to use llvm::isBitwiseNot()?

[rogfer01]

ChangeLog:

• Tighten conditions in which the fold is executed
• Use isBitwiseNot instead of checking for (xor e, 1)
• Remove TheXor
• Rephrase comments so they are less confusing by not mentioning br.

[rogfer01]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13495–13499

I tried checking that the user is a br but then lots of other unrelated tests started failing.

I will look closer what is going on here.

[rogfer01]

ChangeLog:

• Tighten even more the condition in which the fold is applied
• Rephrase comments so they mention brcond.

[rogfer01]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13495–13499

I must have done something silly earlier because this seems OK.

[spatel]

LGTM

[efriedma]

I don't think this is legal in general unless you restrict it to i1. See https://rise4fun.com/Alive/1Hyj .

[rogfer01]

ChangeLog:

• Constrain fold to i1.

[lebedev.ri]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13496–13499

Why is this one-use restriction being introduced here?

[rogfer01]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13496–13499

There are two callers of this function visitSETCC, which passes a node generated by SimplifySetCC, and visitBRCOND which does indeed check that the passed node has just one use.

I'm less sure about the the node coming out of SimplifySetCC so it might make sense to err on the safe side here?

[lebedev.ri]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13496–13499

(*N->use_begin())->getOpcode() == ISD::BRCOND) should go, or make it an assert.

I'm not really sure what's on the other unsafe side, against what is this protecting?

[rogfer01]

ChangeLog:

• Remove new hasOneUse and assert opcode of operand.

(Apologies it took me so long to get back to this)

[rogfer01]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13496–13499

@lebedev.ri @spatel I removed the "one use" check but I'm under the impression that we still want the assert, do we?

[lebedev.ri]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13496–13499

Hm, no, i would think the assert should go away too.
Since there's no longer one-use check, we can't assume that ISD::BRCOND is he first user.
And i'm not sure against what we'd guarding with that check.

[lenary]

Ping? This is mentioned in a RISC-V bug on llvm bugzilla, and seems like a nice improvement to multiple targets if we can land it.

[lebedev.ri]

@rogfer01 reverse-ping?
I'm not sure why this got stuck. Perhaps the code is fine and only the assert should go.

[rogfer01]

Apologies, I totally forgot about this one. I'll update it ASAP.

[rogfer01]

ChangeLog:

• Remove assert

[asb]

This looks good to land IMHO. It's a nice improvement for RISC-V, and it seems to have been sufficiently reviewed by people active with the DAGCombiner. Thanks Roger.

[lebedev.ri]

LG, i guess we'll deal with fallout if there's something missed.

[rogfer01]

Thanks all for the review, I'll land this shortly.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (Op0.getOpcode() == ISD::AND && Op1.getOpcode() == ISD::Constant) {
           SDLoc DL(N);
           return DAG.getSetCC(DL, getSetCCResultType(Op0.getValueType()),
                               Op0, DAG.getConstant(0, DL, Op0.getValueType()),
                               ISD::SETNE);
         }
       }
     }
   }
 
-  // Transform br(xor(x, y)) -> br(x != y)
-  // Transform br(xor(xor(x,y), 1)) -> br (x == y)
-  if (N.getOpcode() == ISD::XOR) {
+  // Transform (brcond (xor x, y)) -> (brcond (setcc, x, y, ne))
+  // Transform (brcond (xor (xor x, y), -1)) -> (brcond (setcc, x, y, eq))
+  if (N.getOpcode() == ISD::XOR && N->hasOneUse() &&
+      (*N->use_begin())->getOpcode() == ISD::BRCOND) {
     // Because we may call this on a speculatively constructed
     // SimplifiedSetCC Node, we need to simplify this node first.
     // Ideally this should be folded into SimplifySetCC and not
     // here. For now, grab a handle to N so we don't lose it from
     // replacements interal to the visit.
     HandleSDNode XORHandle(N);
     while (N.getOpcode() == ISD::XOR) {
       SDValue Tmp = visitXOR(N.getNode());
       // No simplification done.
       if (!Tmp.getNode())
         break;
       // Returning N is form in-visit replacement that may invalidated
       // N. Grab value from Handle.
       if (Tmp.getNode() == N.getNode())
         N = XORHandle.getValue();
       else // Node simplified. Try simplifying again.
         N = Tmp;
     }
 
     if (N.getOpcode() != ISD::XOR)
       return N;
 
-    SDNode *TheXor = N.getNode();
-
-    SDValue Op0 = TheXor->getOperand(0);
-    SDValue Op1 = TheXor->getOperand(1);
+    SDValue Op0 = N->getOperand(0);
+    SDValue Op1 = N->getOperand(1);
 
     if (Op0.getOpcode() != ISD::SETCC && Op1.getOpcode() != ISD::SETCC) {
       bool Equal = false;
-      if (isOneConstant(Op0) && Op0.hasOneUse() &&
-          Op0.getOpcode() == ISD::XOR) {
-        TheXor = Op0.getNode();
+      // (brcond (xor (xor x, y), -1)) -> (brcond (setcc x, y, eq))
+      if (isBitwiseNot(N) && Op0.hasOneUse() && Op0.getOpcode() == ISD::XOR &&
+          Op0.getValueType() == MVT::i1) {
+        N = Op0;
+        Op0 = N->getOperand(0);
+        Op1 = N->getOperand(1);
         Equal = true;
       }
 
       EVT SetCCVT = N.getValueType();
       if (LegalTypes)
         SetCCVT = getSetCCResultType(SetCCVT);
       // Replace the uses of XOR with SETCC
-      return DAG.getSetCC(SDLoc(TheXor), SetCCVT, Op0, Op1,
+      return DAG.getSetCC(SDLoc(N), SetCCVT, Op0, Op1,
                           Equal ? ISD::SETEQ : ISD::SETNE);
     }
   }
 
   return SDValue();
 }
 
 // Operand List for BR_CC: Chain, CondCC, CondLHS, CondRHS, DestBB.

llvm/test/CodeGen/AArch64/cmp-bool.ll

 
 if.end:
   ret void
 }
 
 define void @bool_ne(i1 zeroext %a, i1 zeroext %b, void ()* nocapture %c) nounwind {
 ; CHECK-LABEL: bool_ne:
 ; CHECK:       // %bb.0: // %entry
-; CHECK-NEXT:    eor w8, w0, w1
-; CHECK-NEXT:    cmp w8, #1 // =1
-; CHECK-NEXT:    b.ne .LBB1_2
+; CHECK-NEXT:    cmp w0, w1
+; CHECK-NEXT:    b.eq .LBB1_2
 ; CHECK-NEXT:  // %bb.1: // %if.then
 ; CHECK-NEXT:    br x2
 ; CHECK-NEXT:  .LBB1_2: // %if.end
 ; CHECK-NEXT:    ret
 entry:
   %cmp = xor i1 %a, %b
   br i1 %cmp, label %if.then, label %if.end
 
 if.then:
   tail call void %c() #1
   br label %if.end
 
 if.end:
   ret void
 }

llvm/test/CodeGen/ARM/cmp-bool.ll

 
 if.end:
   ret void
 }
 
 define void @bool_ne(i1 zeroext %a, i1 zeroext %b, void ()* nocapture %c) nounwind {
 ; ARM-LABEL: bool_ne:
 ; ARM:       @ %bb.0: @ %entry
-; ARM-NEXT:    eor r0, r0, r1
-; ARM-NEXT:    cmp r0, #1
-; ARM-NEXT:    bxne lr
+; ARM-NEXT:    cmp r0, r1
+; ARM-NEXT:    bxeq lr
 ; ARM-NEXT:    bx r2
 ;
 ; THUMB-LABEL: bool_ne:
 ; THUMB:       @ %bb.0: @ %entry
 ; THUMB-NEXT:    push {r7, lr}
-; THUMB-NEXT:    eors r0, r1
-; THUMB-NEXT:    cmp r0, #1
-; THUMB-NEXT:    bne .LBB1_2
+; THUMB-NEXT:    cmp r0, r1
+; THUMB-NEXT:    beq .LBB1_2
 ; THUMB-NEXT:  @ %bb.1: @ %if.then
 ; THUMB-NEXT:    blx r2
 ; THUMB-NEXT:  .LBB1_2: @ %if.end
 ; THUMB-NEXT:    pop {r7, pc}
 ;
 ; THUMB2-LABEL: bool_ne:
 ; THUMB2:       @ %bb.0: @ %entry
-; THUMB2-NEXT:    eors r0, r1
-; THUMB2-NEXT:    cmp r0, #1
-; THUMB2-NEXT:    it ne
-; THUMB2-NEXT:    bxne lr
+; THUMB2-NEXT:    cmp r0, r1
+; THUMB2-NEXT:    it eq
+; THUMB2-NEXT:    bxeq lr
 ; THUMB2-NEXT:    bx r2
 entry:
   %cmp = xor i1 %a, %b
   br i1 %cmp, label %if.then, label %if.end
 
 if.then:
   tail call void %c() #1
   br label %if.end
 
 if.end:
   ret void
 }

llvm/test/CodeGen/RISCV/cmp-bool.ll

if.end:
   ret void
 }
 
 define void @bool_ne(i1 zeroext %a, i1 zeroext %b, void ()* nocapture %c) nounwind {
 ; RV32-LABEL: bool_ne:
 ; RV32:       # %bb.0: # %entry
 ; RV32-NEXT:    addi sp, sp, -16
 ; RV32-NEXT:    sw ra, 12(sp)
-; RV32-NEXT:    xor a0, a0, a1
-; RV32-NEXT:    addi a1, zero, 1
-; RV32-NEXT:    bne a0, a1, .LBB1_2
+; RV32-NEXT:    beq a0, a1, .LBB1_2
 ; RV32-NEXT:  # %bb.1: # %if.then
 ; RV32-NEXT:    jalr a2
 ; RV32-NEXT:  .LBB1_2: # %if.end
 ; RV32-NEXT:    lw ra, 12(sp)
 ; RV32-NEXT:    addi sp, sp, 16
 ; RV32-NEXT:    ret
 ;
 ; RV64-LABEL: bool_ne:
 ; RV64:       # %bb.0: # %entry
 ; RV64-NEXT:    addi sp, sp, -16
 ; RV64-NEXT:    sd ra, 8(sp)
-; RV64-NEXT:    xor a0, a0, a1
-; RV64-NEXT:    addi a1, zero, 1
-; RV64-NEXT:    bne a0, a1, .LBB1_2
+; RV64-NEXT:    beq a0, a1, .LBB1_2
 ; RV64-NEXT:  # %bb.1: # %if.then
 ; RV64-NEXT:    jalr a2
 ; RV64-NEXT:  .LBB1_2: # %if.end
 ; RV64-NEXT:    ld ra, 8(sp)
 ; RV64-NEXT:    addi sp, sp, 16
 ; RV64-NEXT:    ret
 entry:
   %cmp = xor i1 %a, %b

llvm/test/CodeGen/WebAssembly/reg-stackify.ll

 ; CHECK-NEXT: i32.const   $push[[L1:[0-9]+]]=, 2{{$}}
 ; CHECK-NEXT: i32.lt_s    $push[[L2:[0-9]+]]=, $1, $pop[[L1]]{{$}}
 ; CHECK-NEXT: i32.xor     $push[[L5:[0-9]+]]=, $pop[[L0]], $pop[[L2]]{{$}}
 ; CHECK-NEXT: i32.const   $push[[L12:[0-9]+]]=, 1{{$}}
 ; CHECK-NEXT: i32.lt_s    $push[[L3:[0-9]+]]=, $2, $pop[[L12]]{{$}}
 ; CHECK-NEXT: i32.const   $push[[L11:[0-9]+]]=, 2{{$}}
 ; CHECK-NEXT: i32.lt_s    $push[[L4:[0-9]+]]=, $3, $pop[[L11]]{{$}}
 ; CHECK-NEXT: i32.xor     $push[[L6:[0-9]+]]=, $pop[[L3]], $pop[[L4]]{{$}}
-; CHECK-NEXT: i32.xor     $push[[L7:[0-9]+]]=, $pop[[L5]], $pop[[L6]]{{$}}
-; CHECK-NEXT: i32.const   $push10=, 1{{$}}
-; CHECK-NEXT: i32.ne      $push8=, $pop7, $pop10{{$}}
-; CHECK-NEXT: br_if       0, $pop8{{$}}
-; CHECK-NEXT: i32.const   $push9=, 0{{$}}
-; CHECK-NEXT: return      $pop9{{$}}
+; CHECK-NEXT: i32.eq      $push7=, $pop[[L5]], $pop[[L6]]{{$}}
+; CHECK-NEXT: br_if       0, $pop7{{$}}
+; CHECK-NEXT: i32.const   $push8=, 0{{$}}
+; CHECK-NEXT: return      $pop8{{$}}
 ; CHECK-NEXT: .LBB{{[0-9]+}}_2:
 ; CHECK-NEXT: end_block{{$}}
-; CHECK-NEXT: i32.const   $push14=, 1{{$}}
-; CHECK-NEXT: return      $pop14{{$}}
+; CHECK-NEXT: i32.const   $push12=, 1{{$}}
+; CHECK-NEXT: return      $pop12{{$}}
 ; NOREGS-LABEL: stack_uses:
 ; NOREGS: .functype stack_uses (i32, i32, i32, i32) -> (i32){{$}}
 ; NOREGS-NEXT: block {{$}}
 ; NOREGS-NEXT: local.get 0{{$}}
 ; NOREGS-NEXT: i32.const   1{{$}}
 ; NOREGS-NEXT: i32.lt_s
 ; NOREGS-NEXT: local.get 1{{$}}
 ; NOREGS-NEXT: i32.const   2{{$}}
 ; NOREGS-NEXT: i32.lt_s
 ; NOREGS-NEXT: i32.xor {{$}}
 ; NOREGS-NEXT: local.get 2{{$}}
 ; NOREGS-NEXT: i32.const   1{{$}}
 ; NOREGS-NEXT: i32.lt_s
 ; NOREGS-NEXT: local.get 3{{$}}
 ; NOREGS-NEXT: i32.const   2{{$}}
 ; NOREGS-NEXT: i32.lt_s
 ; NOREGS-NEXT: i32.xor {{$}}
-; NOREGS-NEXT: i32.xor {{$}}
-; NOREGS-NEXT: i32.const   1{{$}}
-; NOREGS-NEXT: i32.ne {{$}}
+; NOREGS-NEXT: i32.eq {{$}}
 ; NOREGS-NEXT: br_if       0{{$}}
 ; NOREGS-NEXT: i32.const   0{{$}}
 ; NOREGS-NEXT: return{{$}}
 ; NOREGS-NEXT: .LBB{{[0-9]+}}_2:
 ; NOREGS-NEXT: end_block{{$}}
 ; NOREGS-NEXT: i32.const   1{{$}}
 ; NOREGS-NEXT: return{{$}}
 define i32 @stack_uses(i32 %x, i32 %y, i32 %z, i32 %w) {

llvm/test/CodeGen/X86/cmp-bool.ll

 
 if.end:
   ret void
 }
 
 define void @bool_ne(i1 zeroext %a, i1 zeroext %b, void ()* nocapture %c) nounwind {
 ; CHECK-LABEL: bool_ne:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    xorl %esi, %edi
-; CHECK-NEXT:    cmpb $1, %dil
-; CHECK-NEXT:    jne .LBB1_1
+; CHECK-NEXT:    cmpb %sil, %dil
+; CHECK-NEXT:    je .LBB1_1
 ; CHECK-NEXT:  # %bb.2: # %if.then
 ; CHECK-NEXT:    jmpq *%rdx # TAILCALL
 ; CHECK-NEXT:  .LBB1_1: # %if.end
 ; CHECK-NEXT:    retq
 entry:
   %cmp = xor i1 %a, %b
   br i1 %cmp, label %if.then, label %if.end
 
 if.then:
   tail call void %c() #1
   br label %if.end
 
 if.end:
   ret void
 }