[DAGCombiner][X86] Teach DAGCombiner to fold (not (neg X)) -> (add X, -1)

[craig.topper]

Summary

This is a special case of a more general transform (not (sub Y, X)) -> (add X, ~Y). InstCombine knows the general form. I've restricted to the special case to fix the motivating case PR42118. I tried handling any case where Y was constant, but got some changes on some Mips tests that I couldn't quickly prove where beneficial.

Fixes PR42118

[RKSimon]

LGTM - cheers

[xbolva00]

Yes, it seems the more generalized form causes some regressions on Mips (missing folds?), but also it can improve PR31045.ll (@RKSimon) .

Anyway, this simpler form is fine.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (isAllOnesConstant(N1) && N0.hasOneUse() &&
     if (isa<ConstantSDNode>(RHS) || isa<ConstantSDNode>(LHS)) {
       unsigned NewOpcode = N0Opcode == ISD::AND ? ISD::OR : ISD::AND;
       LHS = DAG.getNode(ISD::XOR, SDLoc(LHS), VT, LHS, N1); // LHS = ~LHS
       RHS = DAG.getNode(ISD::XOR, SDLoc(RHS), VT, RHS, N1); // RHS = ~RHS
       AddToWorklist(LHS.getNode()); AddToWorklist(RHS.getNode());
       return DAG.getNode(NewOpcode, DL, VT, LHS, RHS);
     }
   }
+
+  // fold (not (neg x)) -> (add X, -1)
+  // FIXME: This can be generalized to (not (sub Y, X)) -> (add X, ~Y) if
+  // Y is a constant or the subtract has a single use.
+  if (isAllOnesConstant(N1) && N0.getOpcode() == ISD::SUB &&
+      isNullConstant(N0.getOperand(0))) {
+    return DAG.getNode(ISD::ADD, DL, VT, N0.getOperand(1),
+                       DAG.getAllOnesConstant(DL, VT));
+  }
+
   // fold (xor (and x, y), y) -> (and (not x), y)
   if (N0Opcode == ISD::AND && N0.hasOneUse() && N0->getOperand(1) == N1) {
     SDValue X = N0.getOperand(0);
     SDValue NotX = DAG.getNOT(SDLoc(X), X, VT);
     AddToWorklist(NotX.getNode());
     return DAG.getNode(ISD::AND, DL, VT, NotX, N1);
   }
 

llvm/test/CodeGen/X86/bmi.ll

; X64-NEXT:    retq
   ret i64 %tmp2
 }
 
 declare void @bar()
 
 define void @pr42118_i32(i32 %x) {
 ; X86-LABEL: pr42118_i32:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    movl %eax, %ecx
-; X86-NEXT:    negl %ecx
-; X86-NEXT:    andnl %eax, %ecx, %eax
+; X86-NEXT:    blsrl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    jne .LBB48_1
 ; X86-NEXT:  # %bb.2:
 ; X86-NEXT:    jmp bar # TAILCALL
 ; X86-NEXT:  .LBB48_1:
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: pr42118_i32:
 ; X64:       # %bb.0:
-; X64-NEXT:    movl %edi, %eax
-; X64-NEXT:    negl %eax
-; X64-NEXT:    andnl %edi, %eax, %eax
+; X64-NEXT:    blsrl %edi, %eax
 ; X64-NEXT:    jne .LBB48_1
 ; X64-NEXT:  # %bb.2:
 ; X64-NEXT:    jmp bar # TAILCALL
 ; X64-NEXT:  .LBB48_1:
 ; X64-NEXT:    retq
   %tmp = sub i32 0, %x
   %tmp1 = and i32 %tmp, %x
   %cmp = icmp eq i32 %tmp1, %x
   br i1 %cmp, label %1, label %2
 
   tail call void @bar()
   br label %2
 
   ret void
 }
 
 define void @pr42118_i64(i64 %x) {
 ; X86-LABEL: pr42118_i64:
 ; X86:       # %bb.0:
 ; X86-NEXT:    pushl %esi
 ; X86-NEXT:    .cfi_def_cfa_offset 8
 ; X86-NEXT:    .cfi_offset %esi, -8
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    xorl %edx, %edx
-; X86-NEXT:    movl %eax, %esi
-; X86-NEXT:    negl %esi
-; X86-NEXT:    sbbl %ecx, %edx
-; X86-NEXT:    andnl %ecx, %edx, %ecx
-; X86-NEXT:    andnl %eax, %esi, %eax
-; X86-NEXT:    orl %ecx, %eax
+; X86-NEXT:    movl %eax, %edx
+; X86-NEXT:    addl $-1, %edx
+; X86-NEXT:    movl %ecx, %esi
+; X86-NEXT:    adcl $-1, %esi
+; X86-NEXT:    andl %eax, %edx
+; X86-NEXT:    andl %ecx, %esi
+; X86-NEXT:    orl %edx, %esi
 ; X86-NEXT:    jne .LBB49_1
 ; X86-NEXT:  # %bb.2:
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    .cfi_def_cfa_offset 4
 ; X86-NEXT:    jmp bar # TAILCALL
 ; X86-NEXT:  .LBB49_1:
 ; X86-NEXT:    .cfi_def_cfa_offset 8
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    .cfi_def_cfa_offset 4
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: pr42118_i64:
 ; X64:       # %bb.0:
-; X64-NEXT:    movq %rdi, %rax
-; X64-NEXT:    negq %rax
-; X64-NEXT:    andnq %rdi, %rax, %rax
+; X64-NEXT:    blsrq %rdi, %rax
 ; X64-NEXT:    jne .LBB49_1
 ; X64-NEXT:  # %bb.2:
 ; X64-NEXT:    jmp bar # TAILCALL
 ; X64-NEXT:  .LBB49_1:
 ; X64-NEXT:    retq
   %tmp = sub i64 0, %x
   %tmp1 = and i64 %tmp, %x
   %cmp = icmp eq i64 %tmp1, %x
   br i1 %cmp, label %1, label %2
 
   tail call void @bar()
   br label %2
 
   ret void
 }