[GlobalIsel][X86] Legalize G_CTLZ and G_CTPOP for 32-bit

[tschuett]

Summary

Note that 32-bit support is very limited

[RKSimon]

llvm/lib/Target/X86/X86LegalizerInfo.cpp

208

Just add the 32-bit handling here along with everything else?

[RKSimon]

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

3

Why not just add these tests to the existing legalize-ctpop.mir / legalize-leading-zeros.mir ?

[tschuett]

The underlying issue is that I can legalize G_CTPOP only once. There is VPOPCNTDQ and it has to be in the same builder! With the current setup, they legalize operations for different features. The famous setLegalizerInfo*functions.

If I invoke setLegalizerInfo32bit() and later setLegalizerInfoAVX512(), then G_CTPOP could be legalized twice, which is forbidden!

[RKSimon]

That sounds like a severe design flaw......

[tschuett]

They rely mostly on the legacy API, where this issue does not come up. But the legacy API is less powerful. The issue is more obvious with X86, which has a wide range of features and vectors. AArch64 seems to have less issues with this constrain.

[tschuett]

G_OR will 64bit, 128bit with SSE2, 256bit with AVX2, and 512bit with AVX512. It be a mess to create a bunch of builders for G_OR. Presumably 4 builders.

[RKSimon]

What about a class that accumulates the supported types through all the subtarget checks and then we call getActionDefinitionsBuilder once at the end with the accumulated list / settings ? I'm not sure what will happen when we start addressing custom legalization cases as well though.

@arsenm Any suggestions?

[arsenm]

In D151459#4373236, @RKSimon wrote:

What about a class that accumulates the supported types through all the subtarget checks and then we call getActionDefinitionsBuilder once at the end with the accumulated list / settings ? I'm not sure what will happen when we start addressing custom legalization cases as well though.

@arsenm Any suggestions?

That’s what I do for some of the AMDGPU cases. Ideally the legal cases are all in the first legalization rule.

Alternatively you can always write an arbitrary legalIf predicate

[tschuett]

In D151459#4373265, @arsenm wrote:

In D151459#4373236, @RKSimon wrote:

What about a class that accumulates the supported types through all the subtarget checks and then we call getActionDefinitionsBuilder once at the end with the accumulated list / settings ? I'm not sure what will happen when we start addressing custom legalization cases as well though.

@arsenm Any suggestions?

That’s what I do for some of the AMDGPU cases. Ideally the legal cases are all in the first legalization rule.

Alternatively you can always write an arbitrary legalIf predicate

It looks similarly messy. The widen rules will differ between the different vector widths.

[tschuett]

It might be less messy with using variables instead of integer literals. maxScalarSizeand minScalarSize, something about vectors ...

[tschuett]

I tried to unify the builders, but I failed. The root issue are std::initializerlist constructs.

rebase

[RKSimon]

LGTM

llvm/lib/Target/X86/X86LegalizerInfo.cpp

X86LegalizerInfo::X86LegalizerInfo(const X86Subtarget &STI,
   setLegalizerInfoSSE41();
   setLegalizerInfoSSE42();
   setLegalizerInfoAVX();
   setLegalizerInfoAVX2();
   setLegalizerInfoAVX512();
   setLegalizerInfoAVX512DQ();
   setLegalizerInfoAVX512BW();
 
+  const LLT s16 = LLT::scalar(16);
+  const LLT s32 = LLT::scalar(32);
+  const LLT s64 = LLT::scalar(64);
+
   getActionDefinitionsBuilder(G_INTRINSIC_ROUNDEVEN)
     .scalarize(0)
     .minScalar(0, LLT::scalar(32))
     .libcall();
 
   auto &LegacyInfo = getLegacyLegalizerInfo();
   LegacyInfo.setLegalizeScalarToDifferentSizeStrategy(G_PHI, 0, widen_1);
   for (unsigned BinOp : {G_SUB, G_MUL, G_AND, G_OR, G_XOR})
     LegacyInfo.setLegalizeScalarToDifferentSizeStrategy(BinOp, 0, widen_1);
   for (unsigned MemOp : {G_LOAD, G_STORE})
     LegacyInfo.setLegalizeScalarToDifferentSizeStrategy(
         MemOp, 0, LegacyLegalizerInfo::narrowToSmallerAndWidenToSmallest);
   LegacyInfo.setLegalizeScalarToDifferentSizeStrategy(
       G_PTR_ADD, 1,
       LegacyLegalizerInfo::widenToLargerTypesUnsupportedOtherwise);
   LegacyInfo.setLegalizeScalarToDifferentSizeStrategy(
       G_CONSTANT, 0,
       LegacyLegalizerInfo::widenToLargerTypesAndNarrowToLargest);
 
   getActionDefinitionsBuilder({G_MEMCPY, G_MEMMOVE, G_MEMSET}).libcall();
 
+
+  if (Subtarget.is64Bit()) {
+    if (Subtarget.hasPOPCNT()) {
+      // popcount
+      getActionDefinitionsBuilder(G_CTPOP)
+        .legalFor({{s16, s16}, {s32, s32}, {s64, s64}})
+        .widenScalarToNextPow2(1, /*Min=*/16)
+        .clampScalar(1, s16, s64);
+    }
+
+    if (Subtarget.hasLZCNT()) {
+      // count leading zeros (LZCNT)
+      getActionDefinitionsBuilder(G_CTLZ)
+        .legalFor({{s16, s16}, {s32, s32}, {s64, s64}})
+        .widenScalarToNextPow2(1, /*Min=*/16)
+        .clampScalar(1, s16, s64);
+    }
+  } else { // 32-bit
+    if (Subtarget.hasPOPCNT()) {
+      // popcount
+      getActionDefinitionsBuilder(G_CTPOP)
+        .legalFor({{s16, s16}, {s32, s32}})
+        .widenScalarToNextPow2(1, /*Min=*/16)
+        .clampScalar(1, s16, s32);
+    }
+
+    if (Subtarget.hasLZCNT()) {
+      // count leading zeros (LZCNT)
+      getActionDefinitionsBuilder(G_CTLZ)
+        .legalFor({{s16, s16}, {s32, s32}})
+        .widenScalarToNextPow2(1, /*Min=*/16)
+        .clampScalar(1, s16, s32);
+    }
+  }
+
   LegacyInfo.computeTables();
   verify(*STI.getInstrInfo());
 }
 
 bool X86LegalizerInfo::legalizeIntrinsic(LegalizerHelper &Helper,
                                          MachineInstr &MI) const {
   return true;
 }
getActionDefinitionsBuilder(
         {G_SHL, G_LSHR, G_ASHR})
       .legalFor({{s8, s8}, {s16, s8}, {s32, s8}})
       .clampScalar(0, s8, s32)
       .clampScalar(1, s8, s8);
 
     // Comparison
     getActionDefinitionsBuilder(G_ICMP)
         .legalForCartesianProduct({s8}, {s8, s16, s32, p0})
         .clampScalar(0, s8, s8);
   }
 
   // Control-flow
   LegacyInfo.setAction({G_BRCOND, s1}, LegacyLegalizeActions::Legal);
 
   // Constants
   for (auto Ty : {s8, s16, s32, p0})
     LegacyInfo.setAction({TargetOpcode::G_CONSTANT, Ty},
void X86LegalizerInfo::setLegalizerInfo64bit() {
 
   // Merge/Unmerge
   LegacyInfo.setAction({G_MERGE_VALUES, s128}, LegacyLegalizeActions::Legal);
   LegacyInfo.setAction({G_UNMERGE_VALUES, 1, s128},
                        LegacyLegalizeActions::Legal);
   LegacyInfo.setAction({G_MERGE_VALUES, 1, s128}, LegacyLegalizeActions::Legal);
   LegacyInfo.setAction({G_UNMERGE_VALUES, s128}, LegacyLegalizeActions::Legal);
 
-  if (Subtarget.hasPOPCNT()) {
-    // popcount
-    getActionDefinitionsBuilder(G_CTPOP)
-      .legalFor({{s16, s16}, {s32, s32}, {s64, s64}})
-      .widenScalarToNextPow2(1, /*Min=*/16)
-      .clampScalar(1, s16, s64);
-  }
-
-  if (Subtarget.hasLZCNT()) {
-    // count leading zeros (LZCNT)
-    getActionDefinitionsBuilder(G_CTLZ)
-      .legalFor({{s16, s16}, {s32, s32}, {s64, s64}})
-      .widenScalarToNextPow2(1, /*Min=*/16)
-      .clampScalar(1, s16, s64);
-  }
-
 }
 
 void X86LegalizerInfo::setLegalizerInfoSSE1() {
   if (!Subtarget.hasSSE1())
     return;
 
   const LLT s32 = LLT::scalar(32);
   const LLT s64 = LLT::scalar(64);

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

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py UTC_ARGS: --version 2
+# RUN: llc -mtriple=i386-linux-gnu -mattr=+popcnt -run-pass=legalizer %s -o - | FileCheck %s
+
+# test popcount for s8, s16, and s32
+
+---
+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_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-32.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py UTC_ARGS: --version 2
+# RUN: llc -mtriple=i386-linux-gnu -mattr=+lzcnt -run-pass=legalizer %s -o - | FileCheck %s
+
+# test count leading zeros for s8, s16, and s32
+
+---
+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_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
+
+...