[GlobalIsel][x86] Legalize G_CTPOP and G_CTLZ II

[tschuett]

Summary

check plan: ninja check-llvm-codegen-x86

[tschuett]

add missing newlines

[RKSimon]

llvm/lib/Target/X86/X86LegalizerInfo.cpp

389

This isn't correct - CTPOP/LZCNT support is provided by Subtarget.hasPOPCNT/hasLZCNT respectively

[tschuett]

I was also unsure about the availability, but Wikipedia claims:
https://en.wikipedia.org/wiki/X86_Bit_manipulation_instruction_set

ABM is implemented by SSE4.2 and ABM is popcount and lzcnt.

[barannikov88]

In D150755#4349879, @tschuett wrote:

I was also unsure about the availability, but Wikipedia claims:
https://en.wikipedia.org/wiki/X86_Bit_manipulation_instruction_set

ABM is implemented by SSE4.2 and ABM is popcount and lzcnt.

It should be possible to disable the generation of these instructions by passing -mno-popcnt / -mno-lzcnt frontend option even if SSE4.2 is enabled.

[RKSimon]

llvm/lib/Target/X86/X86LegalizerInfo.cpp

394

Additionally, don't we need to guard against 32-bit triples where s64 isn't legal?

[RKSimon]

In D150755#4349879, @tschuett wrote:

I was also unsure about the availability, but Wikipedia claims:
https://en.wikipedia.org/wiki/X86_Bit_manipulation_instruction_set

ABM is implemented by SSE4.2 and ABM is popcount and lzcnt.

Don't trust wikipedia - it might be that all SSE4.2 cpus are known to support ABM as well, but its not under the same feature flags inside llvm (or the same cpuid bits on actual cpus), and AMD in fact support it with older cpus.

[tschuett]

I am on it. It will take a moment.

[tschuett]

https://reviews.llvm.org/D150790

llvm/lib/Target/X86/X86LegalizerInfo.h

bool legalizeIntrinsic(LegalizerHelper &Helper,
                          MachineInstr &MI) const override;
 
 private:
   void setLegalizerInfo32bit();
   void setLegalizerInfo64bit();
   void setLegalizerInfoSSE1();
   void setLegalizerInfoSSE2();
   void setLegalizerInfoSSE41();
+  void setLegalizerInfoSSE42();
   void setLegalizerInfoAVX();
   void setLegalizerInfoAVX2();
   void setLegalizerInfoAVX512();
   void setLegalizerInfoAVX512DQ();
   void setLegalizerInfoAVX512BW();
 };
 } // namespace llvm
 #endif

llvm/lib/Target/X86/X86LegalizerInfo.cpp

X86LegalizerInfo::X86LegalizerInfo(const X86Subtarget &STI,
                                    const X86TargetMachine &TM)
     : Subtarget(STI), TM(TM) {
 
   setLegalizerInfo32bit();
   setLegalizerInfo64bit();
   setLegalizerInfoSSE1();
   setLegalizerInfoSSE2();
   setLegalizerInfoSSE41();
+  setLegalizerInfoSSE42();
   setLegalizerInfoAVX();
   setLegalizerInfoAVX2();
   setLegalizerInfoAVX512();
   setLegalizerInfoAVX512DQ();
   setLegalizerInfoAVX512BW();
 
   getActionDefinitionsBuilder(G_INTRINSIC_ROUNDEVEN)
     .scalarize(0)
void X86LegalizerInfo::setLegalizerInfoSSE41() {
 
   const LLT v4s32 = LLT::fixed_vector(4, 32);
 
   auto &LegacyInfo = getLegacyLegalizerInfo();
 
   LegacyInfo.setAction({G_MUL, v4s32}, LegacyLegalizeActions::Legal);
 }
 
+void X86LegalizerInfo::setLegalizerInfoSSE42() {
+  if (!Subtarget.hasSSE42())
+    return;
+
+  const LLT s16 = LLT::scalar(16);
+  const LLT s32 = LLT::scalar(32);
+  const LLT s64 = LLT::scalar(64);
+
+  // popcount
+  getActionDefinitionsBuilder(G_CTPOP)
+    .legalFor({{s16, s16}, {s32, s32}, {s64, s64}})
+    .widenScalarToNextPow2(1, /*Min=*/16)
+    .clampScalar(1, s16, s64);
+
+  // count leading zeros (LZCNT)
+  getActionDefinitionsBuilder(G_CTLZ)
+    .legalFor({{s16, s16}, {s32, s32}, {s64, s64}})
+    .widenScalarToNextPow2(1, /*Min=*/16)
+    .clampScalar(1, s16, s64);
+}
+
 void X86LegalizerInfo::setLegalizerInfoAVX() {
   if (!Subtarget.hasAVX())
     return;
 
   const LLT v16s8 = LLT::fixed_vector(16, 8);
   const LLT v8s16 = LLT::fixed_vector(8, 16);
   const LLT v4s32 = LLT::fixed_vector(4, 32);
   const LLT v2s64 = LLT::fixed_vector(2, 64);

llvm/test/CodeGen/X86/GlobalISel/legalize-ctpop.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py UTC_ARGS: --version 2
+# RUN: llc -mtriple=x86_64-linux-gnu -mattr=+sse4.2 -run-pass=legalizer %s -o - | FileCheck %s
+
+# test popcount for s16, s32, and s64
+
+---
+name:            test_ctpop35
+alignment:       16
+legalized:       false
+regBankSelected: false
+registers:
+  - { id: 0, class: _, preferred-register: '' }
+  - { id: 1, class: _, preferred-register: '' }
+body:             |
+  bb.1:
+    ; CHECK-LABEL: name: test_ctpop35
+    ; CHECK: [[DEF:%[0-9]+]]:_(s35) = IMPLICIT_DEF
+    ; CHECK-NEXT: [[ZEXT:%[0-9]+]]:_(s64) = G_ZEXT [[DEF]](s35)
+    ; CHECK-NEXT: [[CTPOP:%[0-9]+]]:_(s64) = G_CTPOP [[ZEXT]](s64)
+    ; CHECK-NEXT: [[TRUNC:%[0-9]+]]:_(s35) = G_TRUNC [[CTPOP]](s64)
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(s35) = COPY [[TRUNC]](s35)
+    ; CHECK-NEXT: RET 0, implicit [[COPY]](s35)
+    %0:_(s35) = IMPLICIT_DEF
+    %1:_(s35) = G_CTPOP %0
+    %2:_(s35) = COPY %1(s35)
+    RET 0, implicit %2
+
+...
+---
+name:            test_ctpop8
+alignment:       16
+legalized:       false
+regBankSelected: false
+registers:
+  - { id: 0, class: _, preferred-register: '' }
+  - { id: 1, class: _, preferred-register: '' }
+body:             |
+  bb.1:
+    ; CHECK-LABEL: name: test_ctpop8
+    ; CHECK: [[DEF:%[0-9]+]]:_(s8) = IMPLICIT_DEF
+    ; CHECK-NEXT: [[ZEXT:%[0-9]+]]:_(s16) = G_ZEXT [[DEF]](s8)
+    ; CHECK-NEXT: [[CTPOP:%[0-9]+]]:_(s16) = G_CTPOP [[ZEXT]](s16)
+    ; CHECK-NEXT: [[TRUNC:%[0-9]+]]:_(s8) = G_TRUNC [[CTPOP]](s16)
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(s8) = COPY [[TRUNC]](s8)
+    ; CHECK-NEXT: RET 0, implicit [[COPY]](s8)
+    %0:_(s8) = IMPLICIT_DEF
+    %1:_(s8) = G_CTPOP %0
+    %2:_(s8) = COPY %1(s8)
+    RET 0, implicit %2
+
+...
+---
+name:            test_ctpop64
+alignment:       16
+legalized:       false
+regBankSelected: false
+registers:
+  - { id: 0, class: _, preferred-register: '' }
+  - { id: 1, class: _, preferred-register: '' }
+body:             |
+  bb.1:
+    ; CHECK-LABEL: name: test_ctpop64
+    ; CHECK: [[DEF:%[0-9]+]]:_(s64) = IMPLICIT_DEF
+    ; CHECK-NEXT: [[CTPOP:%[0-9]+]]:_(s64) = G_CTPOP [[DEF]](s64)
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(s64) = COPY [[CTPOP]](s64)
+    ; CHECK-NEXT: RET 0, implicit [[COPY]](s64)
+    %0:_(s64) = IMPLICIT_DEF
+    %1:_(s64) = G_CTPOP %0
+    %2:_(s64) = COPY %1(s64)
+    RET 0, implicit %2
+
+...
+---
+name:            test_ctpop32
+alignment:       16
+legalized:       false
+regBankSelected: false
+registers:
+  - { id: 0, class: _, preferred-register: '' }
+  - { id: 1, class: _, preferred-register: '' }
+body:             |
+  bb.1:
+    ; CHECK-LABEL: name: test_ctpop32
+    ; CHECK: [[DEF:%[0-9]+]]:_(s32) = IMPLICIT_DEF
+    ; CHECK-NEXT: [[CTPOP:%[0-9]+]]:_(s32) = G_CTPOP [[DEF]](s32)
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(s32) = COPY [[CTPOP]](s32)
+    ; CHECK-NEXT: RET 0, implicit [[COPY]](s32)
+    %0:_(s32) = IMPLICIT_DEF
+    %1:_(s32) = G_CTPOP %0
+    %2:_(s32) = COPY %1(s32)
+    RET 0, implicit %2
+
+...
+---
+name:            test_ctpop16
+alignment:       16
+legalized:       false
+regBankSelected: false
+registers:
+  - { id: 0, class: _, preferred-register: '' }
+  - { id: 1, class: _, preferred-register: '' }
+body:             |
+  bb.1:
+    ; CHECK-LABEL: name: test_ctpop16
+    ; CHECK: [[DEF:%[0-9]+]]:_(s16) = IMPLICIT_DEF
+    ; CHECK-NEXT: [[CTPOP:%[0-9]+]]:_(s16) = G_CTPOP [[DEF]](s16)
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(s16) = COPY [[CTPOP]](s16)
+    ; CHECK-NEXT: RET 0, implicit [[COPY]](s16)
+    %0:_(s16) = IMPLICIT_DEF
+    %1:_(s16) = G_CTPOP %0
+    %2:_(s16) = COPY %1(s16)
+    RET 0, implicit %2
+
+...

llvm/test/CodeGen/X86/GlobalISel/legalize-leading-zeros.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py UTC_ARGS: --version 2
+# RUN: llc -mtriple=x86_64-linux-gnu -mattr=+sse4.2 -run-pass=legalizer %s -o - | FileCheck %s
+
+# test count leading zeros for s16, s32, and s64
+
+---
+name:            test_ctlz35
+alignment:       16
+legalized:       false
+regBankSelected: false
+registers:
+  - { id: 0, class: _, preferred-register: '' }
+  - { id: 1, class: _, preferred-register: '' }
+body:             |
+  bb.1:
+    ; CHECK-LABEL: name: test_ctlz35
+    ; CHECK: [[DEF:%[0-9]+]]:_(s35) = IMPLICIT_DEF
+    ; CHECK-NEXT: [[ZEXT:%[0-9]+]]:_(s64) = G_ZEXT [[DEF]](s35)
+    ; CHECK-NEXT: [[CTLZ:%[0-9]+]]:_(s64) = G_CTLZ [[ZEXT]](s64)
+    ; CHECK-NEXT: [[C:%[0-9]+]]:_(s64) = G_CONSTANT i64 29
+    ; CHECK-NEXT: [[SUB:%[0-9]+]]:_(s64) = G_SUB [[CTLZ]], [[C]]
+    ; CHECK-NEXT: [[TRUNC:%[0-9]+]]:_(s35) = G_TRUNC [[SUB]](s64)
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(s35) = COPY [[TRUNC]](s35)
+    ; CHECK-NEXT: RET 0, implicit [[COPY]](s35)
+    %0:_(s35) = IMPLICIT_DEF
+    %1:_(s35) = G_CTLZ %0
+    %2:_(s35) = COPY %1(s35)
+    RET 0, implicit %2
+
+...
+---
+name:            test_ctlz8
+alignment:       16
+legalized:       false
+regBankSelected: false
+registers:
+  - { id: 0, class: _, preferred-register: '' }
+  - { id: 1, class: _, preferred-register: '' }
+body:             |
+  bb.1:
+    ; CHECK-LABEL: name: test_ctlz8
+    ; CHECK: [[DEF:%[0-9]+]]:_(s8) = IMPLICIT_DEF
+    ; CHECK-NEXT: [[ZEXT:%[0-9]+]]:_(s16) = G_ZEXT [[DEF]](s8)
+    ; CHECK-NEXT: [[CTLZ:%[0-9]+]]:_(s16) = G_CTLZ [[ZEXT]](s16)
+    ; CHECK-NEXT: [[C:%[0-9]+]]:_(s16) = G_CONSTANT i16 8
+    ; CHECK-NEXT: [[SUB:%[0-9]+]]:_(s16) = G_SUB [[CTLZ]], [[C]]
+    ; CHECK-NEXT: [[TRUNC:%[0-9]+]]:_(s8) = G_TRUNC [[SUB]](s16)
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(s8) = COPY [[TRUNC]](s8)
+    ; CHECK-NEXT: RET 0, implicit [[COPY]](s8)
+    %0:_(s8) = IMPLICIT_DEF
+    %1:_(s8) = G_CTLZ %0
+    %2:_(s8) = COPY %1(s8)
+    RET 0, implicit %2
+
+...
+---
+name:            test_ctlz64
+alignment:       16
+legalized:       false
+regBankSelected: false
+registers:
+  - { id: 0, class: _, preferred-register: '' }
+  - { id: 1, class: _, preferred-register: '' }
+body:             |
+  bb.1:
+    ; CHECK-LABEL: name: test_ctlz64
+    ; CHECK: [[DEF:%[0-9]+]]:_(s64) = IMPLICIT_DEF
+    ; CHECK-NEXT: [[CTLZ:%[0-9]+]]:_(s64) = G_CTLZ [[DEF]](s64)
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(s64) = COPY [[CTLZ]](s64)
+    ; CHECK-NEXT: RET 0, implicit [[COPY]](s64)
+    %0:_(s64) = IMPLICIT_DEF
+    %1:_(s64) = G_CTLZ %0
+    %2:_(s64) = COPY %1(s64)
+    RET 0, implicit %2
+
+...
+---
+name:            test_ctlz32
+alignment:       16
+legalized:       false
+regBankSelected: false
+registers:
+  - { id: 0, class: _, preferred-register: '' }
+  - { id: 1, class: _, preferred-register: '' }
+body:             |
+  bb.1:
+    ; CHECK-LABEL: name: test_ctlz32
+    ; CHECK: [[DEF:%[0-9]+]]:_(s32) = IMPLICIT_DEF
+    ; CHECK-NEXT: [[CTLZ:%[0-9]+]]:_(s32) = G_CTLZ [[DEF]](s32)
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(s32) = COPY [[CTLZ]](s32)
+    ; CHECK-NEXT: RET 0, implicit [[COPY]](s32)
+    %0:_(s32) = IMPLICIT_DEF
+    %1:_(s32) = G_CTLZ %0
+    %2:_(s32) = COPY %1(s32)
+    RET 0, implicit %2
+
+...
+---
+name:            test_ctlz16
+alignment:       16
+legalized:       false
+regBankSelected: false
+registers:
+  - { id: 0, class: _, preferred-register: '' }
+  - { id: 1, class: _, preferred-register: '' }
+body:             |
+  bb.1:
+    ; CHECK-LABEL: name: test_ctlz16
+    ; CHECK: [[DEF:%[0-9]+]]:_(s16) = IMPLICIT_DEF
+    ; CHECK-NEXT: [[CTLZ:%[0-9]+]]:_(s16) = G_CTLZ [[DEF]](s16)
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(s16) = COPY [[CTLZ]](s16)
+    ; CHECK-NEXT: RET 0, implicit [[COPY]](s16)
+    %0:_(s16) = IMPLICIT_DEF
+    %1:_(s16) = G_CTLZ %0
+    %2:_(s16) = COPY %1(s16)
+    RET 0, implicit %2
+
+...