[DAG] Allow XOR(X,MIN_SIGNED_VALUE) to perform AddLike folds

[RKSimon]

Summary

As raised on PR52267, XOR(X,MIN_SIGNED_VALUE) can be treated as ADD(X,MIN_SIGNED_VALUE), so let these cases use the 'AddLike' folds, similar to how we perform no-common-bits OR(X,Y) cases.

define i8 @src(i8 %x) {
%0:
  %r = xor i8 %x, 128
  ret i8 %r
}
=>
define i8 @tgt(i8 %x) {
%0:
  %r = add i8 %x, 128
  ret i8 %r
}
Transformation seems to be correct!

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

[craig.topper]

What about (add (xor X, MIN_SIGNED), C). Should we check for the XOR inside of visitAddLike for constant folding? I believe we check for ISD::OR with no common bits in there. I'm fine if you want to do it as a separate patch.

[RKSimon]

Add isAddLike() helper to match addlike(addlike(x,y),z) patterns

[RKSimon]

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

4548

Looks like we're missing this fold, but I haven't had time to investigate yet:

----------------------------------------
define i1 @src(i8 %a) {
%0:
  %x = xor i8 %a, 1
  %r = icmp eq i8 %x, 2
  ret i1 %r
}
=>
define i1 @tgt(i8 %a) {
%0:
  %r = icmp eq i8 %a, 3
  ret i1 %r
}
Transformation seems to be correct!

[RKSimon]

rebase

[RKSimon]

rebase

[RKSimon]

rebase - regressions are now fixed

[lebedev.ri]

Seems fine to me.

llvm/include/llvm/CodeGen/SelectionDAGNodes.h

 bool isNullFPConstant(SDValue V);
 
 /// Returns true if \p V is an integer constant with all bits set.
 bool isAllOnesConstant(SDValue V);
 
 /// Returns true if \p V is a constant integer one.
 bool isOneConstant(SDValue V);
 
+/// Returns true if \p V is a constant min signed integer value.
+bool isMinSignedConstant(SDValue V);
+
 /// Return the non-bitcasted source operand of \p V if it exists.
 /// If \p V is not a bitcasted value, it is returned as-is.
 SDValue peekThroughBitcasts(SDValue V);
 
 /// Return the non-bitcasted and one-use source operand of \p V if it exists.
 /// If \p V is not a bitcasted one-use value, it is returned as-is.
 SDValue peekThroughOneUseBitcasts(SDValue V);
 

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

static SDValue foldAddSubOfSignBit(SDNode *N, SelectionDAG &DAG) {
   SDValue NewShift = DAG.getNode(ShOpcode, DL, VT, Not.getOperand(0), ShAmt);
   if (SDValue NewC =
           DAG.FoldConstantArithmetic(IsAdd ? ISD::ADD : ISD::SUB, DL, VT,
                                      {ConstantOp, DAG.getConstant(1, DL, VT)}))
     return DAG.getNode(ISD::ADD, DL, VT, NewShift, NewC);
   return SDValue();
 }
 
+static bool isADDLike(SDValue V, const SelectionDAG &DAG) {
+  unsigned Opcode = V.getOpcode();
+  if (Opcode == ISD::OR)
+    return DAG.haveNoCommonBitsSet(V.getOperand(0), V.getOperand(1));
+  if (Opcode == ISD::XOR)
+    return isMinSignedConstant(V.getOperand(1));
+  return false;
+}
+
 /// Try to fold a node that behaves like an ADD (note that N isn't necessarily
 /// an ISD::ADD here, it could for example be an ISD::OR if we know that there
 /// are no common bits set in the operands).
 SDValue DAGCombiner::visitADDLike(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   EVT VT = N0.getValueType();
   SDLoc DL(N);
if (N0.getOpcode() == ISD::SIGN_EXTEND && N0.hasOneUse() &&
           X.getScalarValueSizeInBits() == 1) {
         SDValue Not = DAG.getNOT(DL, X, X.getValueType());
         return DAG.getNode(ISD::ZERO_EXTEND, DL, VT, Not);
       }
     }
 
     // Fold (add (or x, c0), c1) -> (add x, (c0 + c1)) if (or x, c0) is
     // equivalent to (add x, c0).
-    if (N0.getOpcode() == ISD::OR &&
-        isConstantOrConstantVector(N0.getOperand(1), /* NoOpaque */ true) &&
-        DAG.haveNoCommonBitsSet(N0.getOperand(0), N0.getOperand(1))) {
+    // Fold (add (xor x, c0), c1) -> (add x, (c0 + c1)) if (xor x, c0) is
+    // equivalent to (add x, c0).
+    if (isADDLike(N0, DAG) && 
+        isConstantOrConstantVector(N0.getOperand(1), /* NoOpaque */ true)) {
       if (SDValue Add0 = DAG.FoldConstantArithmetic(ISD::ADD, DL, VT,
                                                     {N1, N0.getOperand(1)}))
         return DAG.getNode(ISD::ADD, DL, VT, N0.getOperand(0), Add0);
     }
   }
 
   if (SDValue NewSel = foldBinOpIntoSelect(N))
     return NewSel;
 
   // reassociate add
   if (!reassociationCanBreakAddressingModePattern(ISD::ADD, DL, N0, N1)) {
     if (SDValue RADD = reassociateOps(ISD::ADD, DL, N0, N1, N->getFlags()))
       return RADD;
 
     // Reassociate (add (or x, c), y) -> (add add(x, y), c)) if (or x, c) is
     // equivalent to (add x, c).
+    // Reassociate (add (xor x, c), y) -> (add add(x, y), c)) if (xor x, c) is
+    // equivalent to (add x, c).
     auto ReassociateAddOr = [&](SDValue N0, SDValue N1) {
-      if (N0.getOpcode() == ISD::OR && N0.hasOneUse() &&
-          isConstantOrConstantVector(N0.getOperand(1), /* NoOpaque */ true) &&
-          DAG.haveNoCommonBitsSet(N0.getOperand(0), N0.getOperand(1))) {
+      if (isADDLike(N0, DAG) && N0.hasOneUse() &&
+          isConstantOrConstantVector(N0.getOperand(1), /* NoOpaque */ true)) {
         return DAG.getNode(ISD::ADD, DL, VT,
                            DAG.getNode(ISD::ADD, DL, VT, N1, N0.getOperand(0)),
                            N0.getOperand(1));
       }
       return SDValue();
     };
     if (SDValue Add = ReassociateAddOr(N0, N1))
       return Add;
SDValue DAGCombiner::visitXOR(SDNode *N) {
 
   if (SDValue NewSel = foldBinOpIntoSelect(N))
     return NewSel;
 
   // reassociate xor
   if (SDValue RXOR = reassociateOps(ISD::XOR, DL, N0, N1, N->getFlags()))
     return RXOR;
 
+  // look for AddLike folds:
+  // XOR(N0,MIN_SIGNED_VALUE) == ADD(N0,MIN_SIGNED_VALUE)
+  if ((!LegalOperations || TLI.isOperationLegal(ISD::ADD, VT)) &&
+      isMinSignedConstant(N1))
+    if (SDValue Combined = visitADDLike(N))
+      return Combined;
+
   // fold !(x cc y) -> (x !cc y)
   unsigned N0Opcode = N0.getOpcode();
   SDValue LHS, RHS, CC;
   if (TLI.isConstTrueVal(N1) &&
       isSetCCEquivalent(N0, LHS, RHS, CC, /*MatchStrict*/ true)) {
     ISD::CondCode NotCC = ISD::getSetCCInverse(cast<CondCodeSDNode>(CC)->get(),
                                                LHS.getValueType());
     if (!LegalOperations ||

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

   return Const != nullptr && Const->isAllOnes();
 }
 
 bool llvm::isOneConstant(SDValue V) {
   ConstantSDNode *Const = dyn_cast<ConstantSDNode>(V);
   return Const != nullptr && Const->isOne();
 }
 
+bool llvm::isMinSignedConstant(SDValue V) {
+  ConstantSDNode *Const = dyn_cast<ConstantSDNode>(V);
+  return Const != nullptr && Const->isMinSignedValue();
+}
+
 SDValue llvm::peekThroughBitcasts(SDValue V) {
   while (V.getOpcode() == ISD::BITCAST)
     V = V.getOperand(0);
   return V;
 }
 
 SDValue llvm::peekThroughOneUseBitcasts(SDValue V) {
   while (V.getOpcode() == ISD::BITCAST && V.getOperand(0).hasOneUse())

llvm/test/CodeGen/ARM/dsp-mlal.ll

entry:
   %0 = lshr i64 %add3, 32
   %conv4 = trunc i64 %0 to i32
   ret i32 %conv4
 }
 
 define hidden i32 @NOT_SMMLA(i32 %a, i32 %b, i32 %c) local_unnamed_addr {
 ; DSP-LABEL: NOT_SMMLA:
 ; DSP:       @ %bb.0: @ %entry
-; DSP-NEXT:    smmul r1, r2, r1
-; DSP-NEXT:    eor r1, r1, #-2147483648
-; DSP-NEXT:    add r0, r1
+; DSP-NEXT:    smmla r0, r1, r2, r0
+; DSP-NEXT:    add.w r0, r0, #-2147483648
 ; DSP-NEXT:    bx lr
 ;
 ; ARM7-LABEL: NOT_SMMLA:
 ; ARM7:       @ %bb.0: @ %entry
-; ARM7-NEXT:    smmul r1, r2, r1
-; ARM7-NEXT:    eor r1, r1, #-2147483648
-; ARM7-NEXT:    add r0, r1, r0
+; ARM7-NEXT:    smmla r0, r2, r1, r0
+; ARM7-NEXT:    add r0, r0, #-2147483648
 ; ARM7-NEXT:    bx lr
 ;
 ; NODSP-LABEL: NOT_SMMLA:
 ; NODSP:       @ %bb.0: @ %entry
 ; NODSP-NEXT:    smull r1, r2, r2, r1
-; NODSP-NEXT:    eor r1, r2, #-2147483648
-; NODSP-NEXT:    add r0, r1
+; NODSP-NEXT:    add r0, r2
+; NODSP-NEXT:    add.w r0, r0, #-2147483648
 ; NODSP-NEXT:    bx lr
 entry:
   %conv = sext i32 %b to i64
   %conv1 = sext i32 %c to i64
   %mul = mul nsw i64 %conv1, %conv
   %0 = lshr i64 %mul, 32
   %conv2 = trunc i64 %0 to i32
   %add = xor i32 %conv2, -2147483648
   %add3 = add i32 %add, %a
   ret i32 %add3
 }

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

; SKX-NEXT:    retq
   ret i1 %val
 }
 
 define i32 @PR39665_c_ray(<2 x double> %x, <2 x double> %y) {
 ; SSE-LABEL: PR39665_c_ray:
 ; SSE:       # %bb.0:
 ; SSE-NEXT:    cmpltpd %xmm0, %xmm1
 ; SSE-NEXT:    movmskpd %xmm1, %eax
-; SSE-NEXT:    cmpb $3, %al
+; SSE-NEXT:    xorb $1, %al
+; SSE-NEXT:    cmpb $2, %al
 ; SSE-NEXT:    movl $42, %ecx
 ; SSE-NEXT:    movl $99, %eax
 ; SSE-NEXT:    cmovel %ecx, %eax
 ; SSE-NEXT:    retq
 ;
 ; AVX1OR2-LABEL: PR39665_c_ray:
 ; AVX1OR2:       # %bb.0:
 ; AVX1OR2-NEXT:    vcmpltpd %xmm0, %xmm1, %xmm0
 ; AVX1OR2-NEXT:    vmovmskpd %xmm0, %eax
-; AVX1OR2-NEXT:    cmpb $3, %al
+; AVX1OR2-NEXT:    xorb $1, %al
+; AVX1OR2-NEXT:    cmpb $2, %al
 ; AVX1OR2-NEXT:    movl $42, %ecx
 ; AVX1OR2-NEXT:    movl $99, %eax
 ; AVX1OR2-NEXT:    cmovel %ecx, %eax
 ; AVX1OR2-NEXT:    retq
 ;
 ; KNL-LABEL: PR39665_c_ray:
 ; KNL:       # %bb.0:
 ; KNL-NEXT:    # kill: def $xmm1 killed $xmm1 def $zmm1

llvm/test/CodeGen/X86/setcc-combine.ll

; CHECK-NEXT:    retq
   ret void
 }
 
 ; This should not get folded to 0.
 
 define i64 @PR40657(i8 %var2, i8 %var9) {
 ; CHECK-LABEL: PR40657:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    notb %sil
-; CHECK-NEXT:    addb %dil, %sil
-; CHECK-NEXT:    movzbl %sil, %eax
+; CHECK-NEXT:    addb %sil, %dil
+; CHECK-NEXT:    incb %dil
+; CHECK-NEXT:    movzbl %dil, %eax
 ; CHECK-NEXT:    andl $1, %eax
 ; CHECK-NEXT:    retq
   %var6 = trunc i8 %var9 to i1
   %var7 = trunc i8 175 to i1
   %var3 = sub nsw i1 %var6, %var7
   %var4 = icmp eq i64 1114591064, 1114591064
   %var1 = udiv i1 %var3, %var4
   %var0 = trunc i8 %var2 to i1

llvm/test/CodeGen/X86/xor-lea.ll

; X64-NEXT:    retq
   %s = add i8 %x, %y
   %r = xor i8 %s, 128
   ret i8 %r
 }
 
 define i16 @xor_sub_sminval_i16(i16 %x) {
 ; X86-LABEL: xor_sub_sminval_i16:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    addl $-2, %eax
-; X86-NEXT:    xorl $32768, %eax # imm = 0x8000
+; X86-NEXT:    movl $32766, %eax # imm = 0x7FFE
+; X86-NEXT:    addl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: xor_sub_sminval_i16:
 ; X64:       # %bb.0:
 ; X64-NEXT:    # kill: def $edi killed $edi def $rdi
-; X64-NEXT:    leal -2(%rdi), %eax
-; X64-NEXT:    xorl $32768, %eax # imm = 0x8000
+; X64-NEXT:    leal 32766(%rdi), %eax
 ; X64-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X64-NEXT:    retq
   %s = sub i16 %x, 2
   %r = xor i16 %s, 32768
   ret i16 %r
 }
 
 define i32 @xor_add_sminval_i32(i32 %x) {
 ; X86-LABEL: xor_add_sminval_i32:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl $512, %eax # imm = 0x200
+; X86-NEXT:    movl $-2147483136, %eax # imm = 0x80000200
 ; X86-NEXT:    addl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    xorl $-2147483648, %eax # imm = 0x80000000
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: xor_add_sminval_i32:
 ; X64:       # %bb.0:
 ; X64-NEXT:    # kill: def $edi killed $edi def $rdi
-; X64-NEXT:    leal 512(%rdi), %eax
-; X64-NEXT:    xorl $-2147483648, %eax # imm = 0x80000000
+; X64-NEXT:    leal -2147483136(%rdi), %eax
 ; X64-NEXT:    retq
   %s = add i32 %x, 512
   %r = xor i32 %s, 2147483648
   ret i32 %r
 }
 
 define i64 @xor_add_sminval_i64(i64 %x, i64 %y) {
 ; X86-LABEL: xor_add_sminval_i64:
; X64-NEXT:    retq
   %r = xor i8 %x, 128
   %s = sub i8 %r, %y
   ret i8 %s
 }
 
 define i16 @add_xor_sminval_i16(i16 %x) {
 ; X86-LABEL: add_xor_sminval_i16:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl $-32768, %eax # imm = 0x8000
-; X86-NEXT:    xorl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    addl $2, %eax
+; X86-NEXT:    movl $-32766, %eax # imm = 0x8002
+; X86-NEXT:    addl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: add_xor_sminval_i16:
 ; X64:       # %bb.0:
 ; X64-NEXT:    # kill: def $edi killed $edi def $rdi
-; X64-NEXT:    xorl $-32768, %edi # imm = 0x8000
-; X64-NEXT:    leal 2(%rdi), %eax
+; X64-NEXT:    leal -32766(%rdi), %eax
 ; X64-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X64-NEXT:    retq
   %r = xor i16 %x, 32768
   %s = add i16 %r, 2
   ret i16 %s
 }
 
 define i32 @sub_xor_sminval_i32(i32 %x) {
 ; X86-LABEL: sub_xor_sminval_i32:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl $-2147483648, %eax # imm = 0x80000000
-; X86-NEXT:    xorl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    addl $-512, %eax # imm = 0xFE00
+; X86-NEXT:    movl $2147483136, %eax # imm = 0x7FFFFE00
+; X86-NEXT:    addl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: sub_xor_sminval_i32:
 ; X64:       # %bb.0:
 ; X64-NEXT:    # kill: def $edi killed $edi def $rdi
-; X64-NEXT:    xorl $-2147483648, %edi # imm = 0x80000000
-; X64-NEXT:    leal -512(%rdi), %eax
+; X64-NEXT:    leal 2147483136(%rdi), %eax
 ; X64-NEXT:    retq
   %r = xor i32 %x, 2147483648
   %s = sub i32 %r, 512
   ret i32 %s
 }
 
 define i64 @add_xor_sminval_i64(i64 %x, i64 %y) {
 ; X86-LABEL: add_xor_sminval_i64:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    movl $-2147483648, %edx # imm = 0x80000000
-; X86-NEXT:    xorl {{[0-9]+}}(%esp), %edx
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
 ; X86-NEXT:    addl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    adcl {{[0-9]+}}(%esp), %edx
+; X86-NEXT:    addl $-2147483648, %edx # imm = 0x80000000
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: add_xor_sminval_i64:
 ; X64:       # %bb.0:
 ; X64-NEXT:    movabsq $-9223372036854775808, %rax # imm = 0x8000000000000000
-; X64-NEXT:    xorq %rdi, %rax
+; X64-NEXT:    addq %rdi, %rax
 ; X64-NEXT:    addq %rsi, %rax
 ; X64-NEXT:    retq
   %r = xor i64 %x, -9223372036854775808
   %s = add i64 %y, %r
   ret i64 %s
 }
 
 ;