[X86] Promote i16 CTTZ/CTTZ_ZERO_UNDEF always.

[craig.topper]

Summary

If we're going to emit a rep prefix before bsf as proposed in
D130956, it makes sense to promote i16 operations to i32 to avoid
the false depedency of tzcntw.

[RKSimon]

llvm/test/CodeGen/X86/clz.ll

570

Would it not be better to just perform the OR %EAX, $65536 and avoid the cmp+branch entirely?

[craig.topper]

llvm/test/CodeGen/X86/clz.ll

570

isCheapToSpeculateCTTZ() doesn't give type based control.

[pengfei]

LGTM. Thanks for the patch!

[skan]

LGTM

llvm/lib/Target/X86/X86ISelLowering.cpp

 //===-- X86ISelLowering.cpp - X86 DAG Lowering Implementation -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
if (!Subtarget.useSoftFloat() && Subtarget.hasX87()) {
     setOperationAction(ISD::FLT_ROUNDS_    , MVT::i32  , Custom);
     setOperationAction(ISD::SET_ROUNDING   , MVT::Other, Custom);
   }
 
   // Promote the i8 variants and force them on up to i32 which has a shorter
   // encoding.
   setOperationPromotedToType(ISD::CTTZ           , MVT::i8   , MVT::i32);
   setOperationPromotedToType(ISD::CTTZ_ZERO_UNDEF, MVT::i8   , MVT::i32);
-
-  if (Subtarget.hasBMI()) {
-    // Promote the i16 zero undef variant and force it on up to i32 when tzcnt
-    // is enabled.
-    setOperationPromotedToType(ISD::CTTZ_ZERO_UNDEF, MVT::i16, MVT::i32);
-  } else {
-    setOperationAction(ISD::CTTZ, MVT::i16, Custom);
+  // Promoted i16. tzcntw has a false dependency on Intel CPUs. For BSF, we emit
+  // a REP prefix to encode it as TZCNT for modern CPUs so it makes sense to
+  // promote that too.
+  setOperationPromotedToType(ISD::CTTZ           , MVT::i16  , MVT::i32);
+  setOperationPromotedToType(ISD::CTTZ_ZERO_UNDEF, MVT::i16  , MVT::i32);
+
+  if (!Subtarget.hasBMI()) {
     setOperationAction(ISD::CTTZ           , MVT::i32  , Custom);
-    setOperationAction(ISD::CTTZ_ZERO_UNDEF, MVT::i16  , Legal);
     setOperationAction(ISD::CTTZ_ZERO_UNDEF, MVT::i32  , Legal);
     if (Subtarget.is64Bit()) {
       setOperationAction(ISD::CTTZ         , MVT::i64  , Custom);
       setOperationAction(ISD::CTTZ_ZERO_UNDEF, MVT::i64, Legal);
     }
   }
 
   if (Subtarget.hasLZCNT()) {

llvm/test/CodeGen/X86/bmi-intrinsics-fast-isel.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -fast-isel -mtriple=i686-unknown-unknown -mattr=+bmi | FileCheck %s --check-prefix=X86
 ; RUN: llc < %s -fast-isel -mtriple=x86_64-unknown-unknown -mattr=+bmi | FileCheck %s --check-prefix=X64
 
 ; NOTE: This should use IR equivalent to what is generated by clang/test/CodeGen/bmi-builtins.c
 
 ;
 ; AMD Intrinsics
 ;
 
 define i16 @test__tzcnt_u16(i16 %a0) {
 ; X86-LABEL: test__tzcnt_u16:
 ; X86:       # %bb.0:
-; X86-NEXT:    tzcntw {{[0-9]+}}(%esp), %ax
+; X86-NEXT:    movzwl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    orl $65536, %eax # imm = 0x10000
+; X86-NEXT:    tzcntl %eax, %eax
+; X86-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test__tzcnt_u16:
 ; X64:       # %bb.0:
-; X64-NEXT:    tzcntw %di, %ax
+; X64-NEXT:    orl $65536, %edi # imm = 0x10000
+; X64-NEXT:    tzcntl %edi, %eax
+; X64-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X64-NEXT:    retq
   %zext = zext i16 %a0 to i32
   %cmp = icmp ne i32 %zext, 0
   %cttz = call i16 @llvm.cttz.i16(i16 %a0, i1 false)
   ret i16 %cttz
 }
 
 define i32 @test__andn_u32(i32 %a0, i32 %a1) {

 
 ;
 ; Intel intrinsics
 ;
 
 define i16 @test_tzcnt_u16(i16 %a0) {
 ; X86-LABEL: test_tzcnt_u16:
 ; X86:       # %bb.0:
-; X86-NEXT:    tzcntw {{[0-9]+}}(%esp), %ax
+; X86-NEXT:    movzwl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    orl $65536, %eax # imm = 0x10000
+; X86-NEXT:    tzcntl %eax, %eax
+; X86-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test_tzcnt_u16:
 ; X64:       # %bb.0:
-; X64-NEXT:    tzcntw %di, %ax
+; X64-NEXT:    orl $65536, %edi # imm = 0x10000
+; X64-NEXT:    tzcntl %edi, %eax
+; X64-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X64-NEXT:    retq
   %zext = zext i16 %a0 to i32
   %cmp = icmp ne i32 %zext, 0
   %cttz = call i16 @llvm.cttz.i16(i16 %a0, i1 false)
   ret i16 %cttz
 }
 
 define i32 @test_andn_u32(i32 %a0, i32 %a1) {

llvm/test/CodeGen/X86/clz.ll

 ; X64-CLZ-NEXT:    retq
   %tmp = call i8 @llvm.cttz.i8( i8 %x, i1 true )
   ret i8 %tmp
 }
 
 define i16 @cttz_i16(i16 %x)  {
 ; X86-LABEL: cttz_i16:
 ; X86:       # %bb.0:
-; X86-NEXT:    bsfw {{[0-9]+}}(%esp), %ax
+; X86-NEXT:    bsfl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: cttz_i16:
 ; X64:       # %bb.0:
-; X64-NEXT:    bsfw %di, %ax
+; X64-NEXT:    bsfl %edi, %eax
+; X64-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X64-NEXT:    retq
 ;
 ; X86-CLZ-LABEL: cttz_i16:
 ; X86-CLZ:       # %bb.0:
 ; X86-CLZ-NEXT:    tzcntl {{[0-9]+}}(%esp), %eax
 ; X86-CLZ-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X86-CLZ-NEXT:    retl
 ;

 ; Generate a test and branch to handle zero inputs because bsr/bsf are very slow.
 define i16 @cttz_i16_zero_test(i16 %n) {
 ; X86-LABEL: cttz_i16_zero_test:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movzwl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    testw %ax, %ax
 ; X86-NEXT:    je .LBB13_1
 ; X86-NEXT:  # %bb.2: # %cond.false
-; X86-NEXT:    bsfw %ax, %ax
+; X86-NEXT:    bsfl %eax, %eax
+; X86-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X86-NEXT:    retl
 ; X86-NEXT:  .LBB13_1:
 ; X86-NEXT:    movw $16, %ax
+; X86-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: cttz_i16_zero_test:
 ; X64:       # %bb.0:
 ; X64-NEXT:    testw %di, %di
 ; X64-NEXT:    je .LBB13_1
 ; X64-NEXT:  # %bb.2: # %cond.false
-; X64-NEXT:    bsfw %di, %ax
+; X64-NEXT:    bsfl %edi, %eax
+; X64-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X64-NEXT:    retq
 ; X64-NEXT:  .LBB13_1:
 ; X64-NEXT:    movw $16, %ax
+; X64-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X64-NEXT:    retq
 ;
 ; X86-CLZ-LABEL: cttz_i16_zero_test:
 ; X86-CLZ:       # %bb.0:
-; X86-CLZ-NEXT:    tzcntw {{[0-9]+}}(%esp), %ax
+; X86-CLZ-NEXT:    movl $65536, %eax # imm = 0x10000
+; X86-CLZ-NEXT:    orl {{[0-9]+}}(%esp), %eax
+; X86-CLZ-NEXT:    tzcntl %eax, %eax
+; X86-CLZ-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X86-CLZ-NEXT:    retl
 ;
 ; X64-CLZ-LABEL: cttz_i16_zero_test:
 ; X64-CLZ:       # %bb.0:
-; X64-CLZ-NEXT:    tzcntw %di, %ax
+; X64-CLZ-NEXT:    orl $65536, %edi # imm = 0x10000
+; X64-CLZ-NEXT:    tzcntl %edi, %eax
+; X64-CLZ-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X64-CLZ-NEXT:    retq
   %tmp1 = call i16 @llvm.cttz.i16(i16 %n, i1 false)
   ret i16 %tmp1
 }
 
 ; Generate a test and branch to handle zero inputs because bsr/bsf are very slow.
 define i32 @cttz_i32_zero_test(i32 %n) {
 ; X86-LABEL: cttz_i32_zero_test:

llvm/test/CodeGen/X86/lzcnt-tzcnt.ll

; CHECK-NEXT:    retq
   %cond = select i1 %tobool, i64 64, i64 %cnt
   ret i64 %cond
 }
 
 
 define i16 @test1_cttz(i16 %v) {
 ; CHECK-LABEL: test1_cttz:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    tzcntw %di, %ax
+; CHECK-NEXT:    orl $65536, %edi # imm = 0x10000
+; CHECK-NEXT:    tzcntl %edi, %eax
+; CHECK-NEXT:    # kill: def $ax killed $ax killed $eax
 ; CHECK-NEXT:    retq
   %cnt = tail call i16 @llvm.cttz.i16(i16 %v, i1 true)
   %tobool = icmp eq i16 %v, 0
   %cond = select i1 %tobool, i16 16, i16 %cnt
   ret i16 %cond
 }
 
 
; CHECK-NEXT:    retq
   %cond = select i1 %tobool, i64 64, i64 %cnt
   ret i64 %cond
 }
 
 
 define i16 @test4_cttz(i16 %v) {
 ; CHECK-LABEL: test4_cttz:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    tzcntw %di, %ax
+; CHECK-NEXT:    orl $65536, %edi # imm = 0x10000
+; CHECK-NEXT:    tzcntl %edi, %eax
+; CHECK-NEXT:    # kill: def $ax killed $ax killed $eax
 ; CHECK-NEXT:    retq
   %cnt = tail call i16 @llvm.cttz.i16(i16 %v, i1 true)
   %tobool = icmp eq i16 0, %v
   %cond = select i1 %tobool, i16 16, i16 %cnt
   ret i16 %cond
 }
 
 
; CHECK-NEXT:    retq
   %cond = select i1 %tobool, i64 64, i64 %cnt
   ret i64 %cond
 }
 
 
 define i16 @test10_cttz(ptr %ptr) {
 ; CHECK-LABEL: test10_cttz:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    tzcntw (%rdi), %ax
+; CHECK-NEXT:    movzwl (%rdi), %eax
+; CHECK-NEXT:    orl $65536, %eax # imm = 0x10000
+; CHECK-NEXT:    tzcntl %eax, %eax
+; CHECK-NEXT:    # kill: def $ax killed $ax killed $eax
 ; CHECK-NEXT:    retq
   %v = load i16, ptr %ptr
   %cnt = tail call i16 @llvm.cttz.i16(i16 %v, i1 true)
   %tobool = icmp eq i16 %v, 0
   %cond = select i1 %tobool, i16 16, i16 %cnt
   ret i16 %cond
 }
 
; CHECK-NEXT:    retq
   %cond = select i1 %tobool, i64 64, i64 %cnt
   ret i64 %cond
 }
 
 
 define i16 @test13_cttz(ptr %ptr) {
 ; CHECK-LABEL: test13_cttz:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    tzcntw (%rdi), %ax
+; CHECK-NEXT:    movzwl (%rdi), %eax
+; CHECK-NEXT:    orl $65536, %eax # imm = 0x10000
+; CHECK-NEXT:    tzcntl %eax, %eax
+; CHECK-NEXT:    # kill: def $ax killed $ax killed $eax
 ; CHECK-NEXT:    retq
   %v = load i16, ptr %ptr
   %cnt = tail call i16 @llvm.cttz.i16(i16 %v, i1 true)
   %tobool = icmp eq i16 0, %v
   %cond = select i1 %tobool, i16 16, i16 %cnt
   ret i16 %cond
 }
 
; CHECK-NEXT:    retq
   %cond = select i1 %tobool, i64 %cnt, i64 64
   ret i64 %cond
 }
 
 
 define i16 @test4b_cttz(i16 %v) {
 ; CHECK-LABEL: test4b_cttz:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    tzcntw %di, %ax
+; CHECK-NEXT:    orl $65536, %edi # imm = 0x10000
+; CHECK-NEXT:    tzcntl %edi, %eax
+; CHECK-NEXT:    # kill: def $ax killed $ax killed $eax
 ; CHECK-NEXT:    retq
   %cnt = tail call i16 @llvm.cttz.i16(i16 %v, i1 true)
   %tobool = icmp ne i16 %v, 0
   %cond = select i1 %tobool, i16 %cnt, i16 16
   ret i16 %cond
 }