[DAG] select Cond, C, -1 --> or (sext (not Cond)), C when C is MVT::i1

[deadalnix]

Summary

In the spirit of D130765 . Get rid of cbranches and/or cmov. Usually shorter, but sometime not, becaus eit's hard to prededict when dependency breaking xor will be introduced.

[RKSimon]

llvm/test/CodeGen/X86/cmov-promotion.ll

124

Some of these test need duplicating as we need to retain test coverage for the cases where cmov will still be used (i.e. the RHS select != -1) , but also keep these tests for the cmov-less coverage.

[deadalnix]

Add a test case for this spercifically in select_const and modify cmov-promotion so that this optimization doesn't kick in.

[RKSimon]

LGTM

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (shouldConvertSelectOfConstantsToMath(Cond, VT, TLI)) {
       }
 
       // select Cond, -1, C --> or (sext Cond), C
       if (C1->isAllOnes()) {
         Cond = DAG.getSExtOrTrunc(Cond, DL, VT);
         return DAG.getNode(ISD::OR, DL, VT, Cond, N2);
       }
 
+      // select Cond, C, -1 --> or (sext (not Cond)), C
+      if (C2->isAllOnes()) {
+        SDValue NotCond = DAG.getNOT(DL, Cond, MVT::i1);
+        NotCond = DAG.getSExtOrTrunc(NotCond, DL, VT);
+        return DAG.getNode(ISD::OR, DL, VT, NotCond, N1);
+      }
+
       if (SDValue V = foldSelectOfConstantsUsingSra(N, DAG))
         return V;
     }
 
     return SDValue();
   }
 
   // fold (select Cond, 0, 1) -> (xor Cond, 1)

llvm/test/CodeGen/X86/cmov-promotion.ll

 ; NO_CMOV-NEXT:  .LBB4_2:
 ; NO_CMOV-NEXT:    xorl %edx, %edx
 ; NO_CMOV-NEXT:    retl
   %t0 = select i1 %c, i16 12414, i16 -1
   %ret = zext i16 %t0 to i64
   ret i64 %ret
 }
 
 define i64 @cmov_zpromotion_32_to_64(i1 %c) {
 ; CMOV-LABEL: cmov_zpromotion_32_to_64:
 ; CMOV:       # %bb.0:
-; CMOV-NEXT:    testb $1, %dil
-; CMOV-NEXT:    movl $12414, %ecx # imm = 0x307E
-; CMOV-NEXT:    movl $-1, %eax
-; CMOV-NEXT:    cmovnel %ecx, %eax
+; CMOV-NEXT:    # kill: def $edi killed $edi def $rdi
+; CMOV-NEXT:    andl $1, %edi
+; CMOV-NEXT:    leal -1(%rdi), %eax
+; CMOV-NEXT:    orl $12414, %eax # imm = 0x307E
 ; CMOV-NEXT:    retq
 ;
 ; NO_CMOV-LABEL: cmov_zpromotion_32_to_64:
 ; NO_CMOV:       # %bb.0:
 ; NO_CMOV-NEXT:    testb $1, {{[0-9]+}}(%esp)
 ; NO_CMOV-NEXT:    movl $12414, %eax # imm = 0x307E
 ; NO_CMOV-NEXT:    jne .LBB5_2
 ; NO_CMOV-NEXT:  # %bb.1:
; NO_CMOV-NEXT:    retl
   %t0 = select i1 %c, i8 117, i8 -19
   %ret = sext i8 %t0 to i16
   ret i16 %ret
 }
 
 define i32 @cmov_spromotion_8_to_32(i1 %c) {
 ; CMOV-LABEL: cmov_spromotion_8_to_32:
 ; CMOV:       # %bb.0:
-; CMOV-NEXT:    testb $1, %dil
-; CMOV-NEXT:    movl $126, %ecx
-; CMOV-NEXT:    movl $-1, %eax
-; CMOV-NEXT:    cmovnel %ecx, %eax
+; CMOV-NEXT:    # kill: def $edi killed $edi def $rdi
+; CMOV-NEXT:    andl $1, %edi
+; CMOV-NEXT:    leal -1(%rdi), %eax
+; CMOV-NEXT:    orl $126, %eax
 ; CMOV-NEXT:    retq
 ;
 ; NO_CMOV-LABEL: cmov_spromotion_8_to_32:
 ; NO_CMOV:       # %bb.0:
-; NO_CMOV-NEXT:    testb $1, {{[0-9]+}}(%esp)
-; NO_CMOV-NEXT:    movl $126, %eax
-; NO_CMOV-NEXT:    jne .LBB7_2
-; NO_CMOV-NEXT:  # %bb.1:
-; NO_CMOV-NEXT:    movl $-1, %eax
-; NO_CMOV-NEXT:  .LBB7_2:
+; NO_CMOV-NEXT:    movzbl {{[0-9]+}}(%esp), %eax
+; NO_CMOV-NEXT:    andl $1, %eax
+; NO_CMOV-NEXT:    decl %eax
+; NO_CMOV-NEXT:    orl $126, %eax
 ; NO_CMOV-NEXT:    retl
   %t0 = select i1 %c, i8 12414, i8 -1
   %ret = sext i8 %t0 to i32
   ret i32 %ret
 }
 
 define i64 @cmov_spromotion_8_to_64(i1 %c) {
 ; CMOV-LABEL: cmov_spromotion_8_to_64:
 ; CMOV:       # %bb.0:
-; CMOV-NEXT:    testb $1, %dil
-; CMOV-NEXT:    movl $126, %ecx
-; CMOV-NEXT:    movq $-1, %rax
-; CMOV-NEXT:    cmovneq %rcx, %rax
+; CMOV-NEXT:    # kill: def $edi killed $edi def $rdi
+; CMOV-NEXT:    andl $1, %edi
+; CMOV-NEXT:    leaq -1(%rdi), %rax
+; CMOV-NEXT:    orq $126, %rax
 ; CMOV-NEXT:    retq
 ;
 ; NO_CMOV-LABEL: cmov_spromotion_8_to_64:
 ; NO_CMOV:       # %bb.0:
-; NO_CMOV-NEXT:    testb $1, {{[0-9]+}}(%esp)
-; NO_CMOV-NEXT:    jne .LBB8_1
-; NO_CMOV-NEXT:  # %bb.2:
-; NO_CMOV-NEXT:    movl $-1, %eax
-; NO_CMOV-NEXT:    movl $-1, %edx
-; NO_CMOV-NEXT:    retl
-; NO_CMOV-NEXT:  .LBB8_1:
+; NO_CMOV-NEXT:    movzbl {{[0-9]+}}(%esp), %eax
 ; NO_CMOV-NEXT:    xorl %edx, %edx
-; NO_CMOV-NEXT:    movl $126, %eax
+; NO_CMOV-NEXT:    btl $0, %eax
+; NO_CMOV-NEXT:    adcl $-1, %edx
+; NO_CMOV-NEXT:    andl $1, %eax
+; NO_CMOV-NEXT:    decl %eax
+; NO_CMOV-NEXT:    orl $126, %eax
 ; NO_CMOV-NEXT:    retl
   %t0 = select i1 %c, i8 12414, i8 -1
   %ret = sext i8 %t0 to i64
   ret i64 %ret
 }
 
 define i32 @cmov_spromotion_16_to_32(i1 %c) {
 ; CMOV-LABEL: cmov_spromotion_16_to_32:
 ; CMOV:       # %bb.0:
-; CMOV-NEXT:    testb $1, %dil
-; CMOV-NEXT:    movl $12414, %ecx # imm = 0x307E
-; CMOV-NEXT:    movl $-1, %eax
-; CMOV-NEXT:    cmovnel %ecx, %eax
+; CMOV-NEXT:    # kill: def $edi killed $edi def $rdi
+; CMOV-NEXT:    andl $1, %edi
+; CMOV-NEXT:    leal -1(%rdi), %eax
+; CMOV-NEXT:    orl $12414, %eax # imm = 0x307E
 ; CMOV-NEXT:    retq
 ;
 ; NO_CMOV-LABEL: cmov_spromotion_16_to_32:
 ; NO_CMOV:       # %bb.0:
-; NO_CMOV-NEXT:    testb $1, {{[0-9]+}}(%esp)
-; NO_CMOV-NEXT:    movl $12414, %eax # imm = 0x307E
-; NO_CMOV-NEXT:    jne .LBB9_2
-; NO_CMOV-NEXT:  # %bb.1:
-; NO_CMOV-NEXT:    movl $-1, %eax
-; NO_CMOV-NEXT:  .LBB9_2:
+; NO_CMOV-NEXT:    movzbl {{[0-9]+}}(%esp), %eax
+; NO_CMOV-NEXT:    andl $1, %eax
+; NO_CMOV-NEXT:    decl %eax
+; NO_CMOV-NEXT:    orl $12414, %eax # imm = 0x307E
 ; NO_CMOV-NEXT:    retl
   %t0 = select i1 %c, i16 12414, i16 -1
   %ret = sext i16 %t0 to i32
   ret i32 %ret
 }
 
 define i64 @cmov_spromotion_16_to_64(i1 %c) {
 ; CMOV-LABEL: cmov_spromotion_16_to_64:
 ; CMOV:       # %bb.0:
-; CMOV-NEXT:    testb $1, %dil
-; CMOV-NEXT:    movl $12414, %ecx # imm = 0x307E
-; CMOV-NEXT:    movq $-1, %rax
-; CMOV-NEXT:    cmovneq %rcx, %rax
+; CMOV-NEXT:    # kill: def $edi killed $edi def $rdi
+; CMOV-NEXT:    andl $1, %edi
+; CMOV-NEXT:    leaq -1(%rdi), %rax
+; CMOV-NEXT:    orq $12414, %rax # imm = 0x307E
 ; CMOV-NEXT:    retq
 ;
 ; NO_CMOV-LABEL: cmov_spromotion_16_to_64:
 ; NO_CMOV:       # %bb.0:
-; NO_CMOV-NEXT:    testb $1, {{[0-9]+}}(%esp)
-; NO_CMOV-NEXT:    jne .LBB10_1
-; NO_CMOV-NEXT:  # %bb.2:
-; NO_CMOV-NEXT:    movl $-1, %eax
-; NO_CMOV-NEXT:    movl $-1, %edx
-; NO_CMOV-NEXT:    retl
-; NO_CMOV-NEXT:  .LBB10_1:
+; NO_CMOV-NEXT:    movzbl {{[0-9]+}}(%esp), %eax
 ; NO_CMOV-NEXT:    xorl %edx, %edx
-; NO_CMOV-NEXT:    movl $12414, %eax # imm = 0x307E
+; NO_CMOV-NEXT:    btl $0, %eax
+; NO_CMOV-NEXT:    adcl $-1, %edx
+; NO_CMOV-NEXT:    andl $1, %eax
+; NO_CMOV-NEXT:    decl %eax
+; NO_CMOV-NEXT:    orl $12414, %eax # imm = 0x307E
 ; NO_CMOV-NEXT:    retl
   %t0 = select i1 %c, i16 12414, i16 -1
   %ret = sext i16 %t0 to i64
   ret i64 %ret
 }
 
 define i64 @cmov_spromotion_32_to_64(i1 %c) {
 ; CMOV-LABEL: cmov_spromotion_32_to_64:
 ; CMOV:       # %bb.0:
-; CMOV-NEXT:    testb $1, %dil
-; CMOV-NEXT:    movl $12414, %ecx # imm = 0x307E
-; CMOV-NEXT:    movq $-1, %rax
-; CMOV-NEXT:    cmovneq %rcx, %rax
+; CMOV-NEXT:    # kill: def $edi killed $edi def $rdi
+; CMOV-NEXT:    andl $1, %edi
+; CMOV-NEXT:    leaq -1(%rdi), %rax
+; CMOV-NEXT:    orq $12414, %rax # imm = 0x307E
 ; CMOV-NEXT:    retq
 ;
 ; NO_CMOV-LABEL: cmov_spromotion_32_to_64:
 ; NO_CMOV:       # %bb.0:
-; NO_CMOV-NEXT:    testb $1, {{[0-9]+}}(%esp)
-; NO_CMOV-NEXT:    jne .LBB11_1
-; NO_CMOV-NEXT:  # %bb.2:
-; NO_CMOV-NEXT:    movl $-1, %eax
-; NO_CMOV-NEXT:    movl $-1, %edx
-; NO_CMOV-NEXT:    retl
-; NO_CMOV-NEXT:  .LBB11_1:
+; NO_CMOV-NEXT:    movzbl {{[0-9]+}}(%esp), %eax
 ; NO_CMOV-NEXT:    xorl %edx, %edx
-; NO_CMOV-NEXT:    movl $12414, %eax # imm = 0x307E
+; NO_CMOV-NEXT:    btl $0, %eax
+; NO_CMOV-NEXT:    adcl $-1, %edx
+; NO_CMOV-NEXT:    andl $1, %eax
+; NO_CMOV-NEXT:    decl %eax
+; NO_CMOV-NEXT:    orl $12414, %eax # imm = 0x307E
 ; NO_CMOV-NEXT:    retl
   %t0 = select i1 %c, i32 12414, i32 -1
   %ret = sext i32 %t0 to i64
   ret i64 %ret
 }

llvm/test/CodeGen/X86/pr16031.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=i386-unknown-linux-gnu -mcpu=corei7-avx -enable-misched=false | FileCheck %s
 
 define i64 @main(i1 %tobool1) nounwind {
 ; CHECK-LABEL: main:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    testb $1, {{[0-9]+}}(%esp)
-; CHECK-NEXT:    movl $-12, %ecx
-; CHECK-NEXT:    movl $-1, %eax
-; CHECK-NEXT:    cmovnel %ecx, %eax
+; CHECK-NEXT:    movzbl {{[0-9]+}}(%esp), %eax
+; CHECK-NEXT:    andl $1, %eax
+; CHECK-NEXT:    decl %eax
+; CHECK-NEXT:    orl $-12, %eax
 ; CHECK-NEXT:    xorl %ecx, %ecx
 ; CHECK-NEXT:    movl %eax, %edx
 ; CHECK-NEXT:    addl $-1, %edx
 ; CHECK-NEXT:    movl $0, %edx
 ; CHECK-NEXT:    adcl $-2, %edx
 ; CHECK-NEXT:    cmovsl %ecx, %eax
 ; CHECK-NEXT:    xorl %edx, %edx
 ; CHECK-NEXT:    retl

llvm/test/CodeGen/X86/select_const.ll

 }
 
 ; No LEA with 8-bit, but this shouldn't need branches or cmov.
 
 define i8 @sel_1_neg1(i32 %x) {
 ; CHECK-LABEL: sel_1_neg1:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    cmpl $43, %edi
-; CHECK-NEXT:    setge %al
-; CHECK-NEXT:    shlb $2, %al
-; CHECK-NEXT:    decb %al
+; CHECK-NEXT:    setl %al
+; CHECK-NEXT:    negb %al
+; CHECK-NEXT:    orb $3, %al
 ; CHECK-NEXT:    retq
   %cmp = icmp sgt i32 %x, 42
   %sel = select i1 %cmp, i8 3, i8 -1
   ret i8 %sel
 }
 
 ; We get an LEA for 16-bit because we ignore the high-bits.
 

llvm/test/CodeGen/X86/zext-sext.ll

 ; CHECK-LABEL: func:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    movslq (%rsi), %rax
 ; CHECK-NEXT:    movl $4, %esi
 ; CHECK-NEXT:    subq %rax, %rsi
 ; CHECK-NEXT:    movq (%rdx), %rax
 ; CHECK-NEXT:    movswl 8(%rdi), %edx
 ; CHECK-NEXT:    movswl (%rax,%rsi,2), %eax
-; CHECK-NEXT:    movl $1, %esi
 ; CHECK-NEXT:    imull %edx, %eax
-; CHECK-NEXT:    xorl %edx, %edx
 ; CHECK-NEXT:    addl $2138875574, %eax # imm = 0x7F7CA6B6
-; CHECK-NEXT:    cmpl $-8608074, %eax # imm = 0xFF7CA6B6
-; CHECK-NEXT:    movslq %eax, %rdi
-; CHECK-NEXT:    setl %dl
 ; CHECK-NEXT:    cmpl $2138875574, %eax # imm = 0x7F7CA6B6
-; CHECK-NEXT:    movq %rdi, %r8
-; CHECK-NEXT:    leal -1(%rdx,%rdx), %edx
-; CHECK-NEXT:    cmovll %edx, %esi
-; CHECK-NEXT:    subq %rax, %r8
+; CHECK-NEXT:    setl %sil
+; CHECK-NEXT:    cmpl $-8608074, %eax # imm = 0xFF7CA6B6
+; CHECK-NEXT:    setge %dl
+; CHECK-NEXT:    andb %sil, %dl
+; CHECK-NEXT:    movslq %eax, %rsi
+; CHECK-NEXT:    movzbl %dl, %edx
+; CHECK-NEXT:    movq %rsi, %rdi
+; CHECK-NEXT:    subq %rax, %rdi
+; CHECK-NEXT:    negl %edx
 ; CHECK-NEXT:    xorl %eax, %eax
-; CHECK-NEXT:    cmpl $1, %esi
-; CHECK-NEXT:    cmovneq %rax, %r8
-; CHECK-NEXT:    testl %edi, %edi
-; CHECK-NEXT:    cmovnsq %rax, %r8
+; CHECK-NEXT:    testl $-2, %edx
+; CHECK-NEXT:    cmovneq %rax, %rdi
+; CHECK-NEXT:    testl %esi, %esi
+; CHECK-NEXT:    cmovnsq %rax, %rdi
 ; CHECK-NEXT:    movq (%rcx), %rax
-; CHECK-NEXT:    subq %r8, %rdi
-; CHECK-NEXT:    leaq -2138875574(%rax,%rdi), %rax
+; CHECK-NEXT:    subq %rdi, %rsi
+; CHECK-NEXT:    leaq -2138875574(%rax,%rsi), %rax
 ; CHECK-NEXT:    movq %rax, (%rcx)
 ; CHECK-NEXT:    retq
 entry:
   %tmp103 = getelementptr inbounds [40 x i16], ptr %a, i64 0, i64 4
   %tmp104 = load i16, ptr %tmp103, align 2
   %tmp105 = sext i16 %tmp104 to i32
   %tmp106 = load i32, ptr %b, align 4
   %tmp107 = sub nsw i32 4, %tmp106