[GlobalIsel][X86] Update legalization of G_ADD/G_SUB

[RKSimon]

Summary

Replace the legacy legalizers for G_ADD/G_SUB with an approach that should work for the full mixture of scalar/vector types we need to support for most opcodes.

If we can decide on this as a suitable pattern we can reuse it for the other op types, but G_ADD/G_SUB are the only ones that have decent legalizer test coverage at this stage.

I've also refactored the G_CTPOP/G_LZCNT entries to match for reference (I'll commit these separately).

[tschuett]

This probably does not compile, but it is my prototype for G_AND:

// AND and PAND
unsigned bitWidth = 64;
auto& bitBuilder = getActionDefinitionsBuilder(G_AND);

if (Subtarget.hasAVX512()) {
  bitBuilder.legalFor({/*512 bit*/v64s8, v32s16, v16s32, v8s64,
    /* 256 bit */ v32s8, v16s16, v8s32, v4s64,
    /* 128 bit */ v16s8, v8s16, v4s32, v2s64,
    /* 64 bit */ s8, s16, s32, s64});
  bitWidth = 512;
} else if (Subtarget.hasAVX2()) {
  bitBuilder.legalFor({
    /* 256 bit */ v32s8, v16s16, v8s32, v4s64,
    /* 128 bit */ v16s8, v8s16, v4s32, v2s64,
    /* 64 bit */ s8, s16, s32, s64});
  bitWidth = 256;
} else if (Subtarget.hasSSE2()) {
  bitBuilder.legalFor({
    /* 128 bit */ v16s8, v8s16, v4s32, v2s64,
    /* 64 bit */ s8, s16, s32, s64});
  bitWidth = 128;
} else { // 64-bit
  bitBuilder.legalFor({/* 64 bit */ s8, s16, s32, s64});
}

bitBuilder.widenScalarToNextPow(0, /*Min=*/ 8)
  .clampScalar(0, s8, s64)
  .clampNumElements(0, s8, s64)
  .clampMaxNumElements(0, s8, bitWidth / 8)
  .clampMaxNumElements(0, s16, bitWidth / 16)
  .clampMaxNumElements(0, s32, bitWidth / 32)
  .clampMaxNumElements(0, s64, bitWidth / 64);

[RKSimon]

Yes, logic, mul, fp, shifts, etc are all on my wip branch (as with most of the opcodes the gisel tests need a major cleanup first).

[tschuett]

I found this pattern in AArch64. Note that they invoke legalForonly once! In my prototype, I also legalize only once.

auto &MinMaxActions = getActionDefinitionsBuilder(
    {G_SMIN, G_SMAX, G_UMIN, G_UMAX});
if (HasCSSC)
  MinMaxActions
      .legalFor({s32, s64, v8s8, v16s8, v4s16, v8s16, v2s32, v4s32})
      // Making clamping conditional on CSSC extension as without legal types we
      // lower to CMP which can fold one of the two sxtb's we'd otherwise need
      // if we detect a type smaller than 32-bit.
      .minScalar(0, s32);
else
  MinMaxActions
      .legalFor({v8s8, v16s8, v4s16, v8s16, v2s32, v4s32});
MinMaxActions
    .clampNumElements(0, v8s8, v16s8)
    .clampNumElements(0, v4s16, v8s16)
    .clampNumElements(0, v2s32, v4s32)
    // FIXME: This sholdn't be needed as v2s64 types are going to
    // be expanded anyway, but G_ICMP doesn't support splitting vectors yet
    .clampNumElements(0, v2s64, v2s64)
    .lower();

[RKSimon]

Keep track of the maximum vector element type for type clamping - still not happy with this, but definitely cleaner

[arsenm]

I'm not certain if the legalizer API has a better way we can do this?

I'm not super happy with the legalize rules API. I think it's over-constraining. In particular I don't see the point of having separate fewer/more actions. We could just have one ChangeType/ChangeElement action.

The clamping is also really annoying in the common case where you don't want intermediate non-power-of-2s as you've noticed. Some of the existing rule orderings are also working around missing paths in the legalizer, some of which are fixed. For example if you clamp a non-power-of-2 operation, the requested type ends up being the upper bound of the range and fails for implementations that only handle evenly divisible cases

[RKSimon]

Use legalIf() and split clampNumElements to simplify max num elements logic.

I'm pretty happy with this for now in terms of clarity, and it should work easily to let us remove the existing legacy legalizers and then add other legal ops on top.

[tschuett]

No tests? X86 shows this. How would a legalizer API for X86 look like without abusing legalIf.

[RKSimon]

The G_ADD legalizer tests are already in place for the legacy legalizer, I can add equivalent G_SUB coverage pretty easily - support for further opcodes needs better tests before they can be added. I'll start with the logic ops and integer multiplies.

If we wanted to add X86 specific legalizers, legalFor64Bit/legalForSSE2/AVX2 style wrappers etc. would probably be quite clean - can/should LegalizeRuleSet be overloaded on a per-target basis?

[tschuett]

A wrapper class that takes an ActionBuilder and a SubTarget?

llvm/lib/Target/X86/X86LegalizerInfo.cpp

 #include "llvm/CodeGen/TargetOpcodes.h"
 #include "llvm/CodeGen/ValueTypes.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Type.h"
 
 using namespace llvm;
 using namespace TargetOpcode;
 using namespace LegalizeActions;
+using namespace LegalityPredicates;
 
 /// FIXME: The following static functions are SizeChangeStrategy functions
 /// that are meant to temporarily mimic the behaviour of the old legalization
 /// based on doubling/halving non-legal types as closely as possible. This is
 /// not entirly possible as only legalizing the types that are exactly a power
 /// of 2 times the size of the legal types would require specifying all those
 /// sizes explicitly.
 /// In practice, not specifying those isn't a problem, and the below functions
widen_1(const LegacyLegalizerInfo::SizeAndActionsVec &v) {
   result.push_back({Largest + 1, LegacyLegalizeActions::Unsupported});
   return result;
 }
 
 X86LegalizerInfo::X86LegalizerInfo(const X86Subtarget &STI,
                                    const X86TargetMachine &TM)
     : Subtarget(STI), TM(TM) {
 
+  bool Is64Bit = Subtarget.is64Bit();
+  bool HasSSE2 = Subtarget.hasSSE2();
+  bool HasAVX2 = Subtarget.hasAVX2();
+  bool HasAVX512 = Subtarget.hasAVX512();
+  bool HasBWI = Subtarget.hasAVX512() && Subtarget.hasBWI();
+
+  const LLT s8 = LLT::scalar(8);
+  const LLT s16 = LLT::scalar(16);
+  const LLT s32 = LLT::scalar(32);
+  const LLT s64 = LLT::scalar(64);
+  const LLT sMaxScalar = Subtarget.is64Bit() ? s64 : s32;
+
+  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);
+
+  const LLT v32s8 = LLT::fixed_vector(32, 8);
+  const LLT v16s16 = LLT::fixed_vector(16, 16);
+  const LLT v8s32 = LLT::fixed_vector(8, 32);
+  const LLT v4s64 = LLT::fixed_vector(4, 64);
+
+  const LLT v64s8 = LLT::fixed_vector(64, 8);
+  const LLT v32s16 = LLT::fixed_vector(32, 16);
+  const LLT v16s32 = LLT::fixed_vector(16, 32);
+  const LLT v8s64 = LLT::fixed_vector(8, 64);
+
+  // integer addition/subtraction
+  getActionDefinitionsBuilder({G_ADD, G_SUB})
+      .legalIf([=](const LegalityQuery &Query) -> bool {
+        if (typeInSet(0, {s8, s16, s32})(Query))
+          return true;
+        if (Is64Bit && typeInSet(0, {s64})(Query))
+          return true;
+        if (HasSSE2 && typeInSet(0, {v16s8, v8s16, v4s32, v2s64})(Query))
+          return true;
+        if (HasAVX2 && typeInSet(0, {v32s8, v16s16, v8s32, v4s64})(Query))
+          return true;
+        if (HasAVX512 && typeInSet(0, {v16s32, v8s64})(Query))
+          return true;
+        if (HasBWI && typeInSet(0, {v64s8, v32s16})(Query))
+          return true;
+        return false;
+      })
+      .clampMinNumElements(0, s8, 16)
+      .clampMinNumElements(0, s16, 8)
+      .clampMinNumElements(0, s32, 4)
+      .clampMinNumElements(0, s64, 2)
+      .clampMaxNumElements(0, s8, HasBWI ? 64 : (HasAVX2 ? 32 : 16))
+      .clampMaxNumElements(0, s16, HasBWI ? 32 : (HasAVX2 ? 16 : 8))
+      .clampMaxNumElements(0, s32, HasAVX512 ? 16 : (HasAVX2 ? 8 : 4))
+      .clampMaxNumElements(0, s64, HasAVX512 ? 8 : (HasAVX2 ? 4 : 2))
+      .widenScalarToNextPow2(0, /*Min=*/32)
+      .clampScalar(0, s8, sMaxScalar)
+      .scalarize(0);
+
   setLegalizerInfo32bit();
   setLegalizerInfo64bit();
   setLegalizerInfoSSE1();
   setLegalizerInfoSSE2();
   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);
-  const LLT maxScalar = Subtarget.is64Bit() ? s64 : s32;
-
   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})
+  for (unsigned BinOp : {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();
 
   getActionDefinitionsBuilder(G_BSWAP)
     .legalIf([=](const LegalityQuery &Query) {
         return Query.Types[0] == s32 ||
           (Subtarget.is64Bit() && Query.Types[0] == s64);
       })
     .widenScalarToNextPow2(0, /*Min=*/32)
-    .clampScalar(0, s32, maxScalar);
+    .clampScalar(0, s32, sMaxScalar);
 
   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);
void X86LegalizerInfo::setLegalizerInfo32bit() {
   auto &LegacyInfo = getLegacyLegalizerInfo();
 
   for (auto Ty : {p0, s1, s8, s16, s32})
     LegacyInfo.setAction({G_IMPLICIT_DEF, Ty}, LegacyLegalizeActions::Legal);
 
   for (auto Ty : {s8, s16, s32, p0})
     LegacyInfo.setAction({G_PHI, Ty}, LegacyLegalizeActions::Legal);
 
-  for (unsigned BinOp : {G_ADD, G_SUB, G_MUL, G_AND, G_OR, G_XOR})
+  for (unsigned BinOp : {G_MUL, G_AND, G_OR, G_XOR})
     for (auto Ty : {s8, s16, s32})
       LegacyInfo.setAction({BinOp, Ty}, LegacyLegalizeActions::Legal);
 
   for (unsigned Op : {G_UADDE}) {
     LegacyInfo.setAction({Op, s32}, LegacyLegalizeActions::Legal);
     LegacyInfo.setAction({Op, 1, s1}, LegacyLegalizeActions::Legal);
   }
 
void X86LegalizerInfo::setLegalizerInfo64bit() {
 
   LegacyInfo.setAction({G_IMPLICIT_DEF, s64}, LegacyLegalizeActions::Legal);
   // Need to have that, as tryFoldImplicitDef will create this pattern:
   // s128 = EXTEND (G_IMPLICIT_DEF s32/s64) -> s128 = G_IMPLICIT_DEF
   LegacyInfo.setAction({G_IMPLICIT_DEF, s128}, LegacyLegalizeActions::Legal);
 
   LegacyInfo.setAction({G_PHI, s64}, LegacyLegalizeActions::Legal);
 
-  for (unsigned BinOp : {G_ADD, G_SUB, G_MUL, G_AND, G_OR, G_XOR})
+  for (unsigned BinOp : {G_MUL, G_AND, G_OR, G_XOR})
     LegacyInfo.setAction({BinOp, s64}, LegacyLegalizeActions::Legal);
 
   for (unsigned MemOp : {G_LOAD, G_STORE})
     LegacyInfo.setAction({MemOp, s64}, LegacyLegalizeActions::Legal);
 
   // Pointer-handling
   LegacyInfo.setAction({G_PTR_ADD, 1, s64}, LegacyLegalizeActions::Legal);
   getActionDefinitionsBuilder(G_PTRTOINT)
void X86LegalizerInfo::setLegalizerInfoSSE2() {
   const LLT v4s64 = LLT::fixed_vector(4, 64);
 
   auto &LegacyInfo = getLegacyLegalizerInfo();
 
   for (unsigned BinOp : {G_FADD, G_FSUB, G_FMUL, G_FDIV})
     for (auto Ty : {s64, v2s64})
       LegacyInfo.setAction({BinOp, Ty}, LegacyLegalizeActions::Legal);
 
-  for (unsigned BinOp : {G_ADD, G_SUB})
-    for (auto Ty : {v16s8, v8s16, v4s32, v2s64})
-      LegacyInfo.setAction({BinOp, Ty}, LegacyLegalizeActions::Legal);
-
   LegacyInfo.setAction({G_MUL, v8s16}, LegacyLegalizeActions::Legal);
 
   LegacyInfo.setAction({G_FPEXT, s64}, LegacyLegalizeActions::Legal);
   LegacyInfo.setAction({G_FPEXT, 1, s32}, LegacyLegalizeActions::Legal);
 
   LegacyInfo.setAction({G_FPTRUNC, s32}, LegacyLegalizeActions::Legal);
   LegacyInfo.setAction({G_FPTRUNC, 1, s64}, LegacyLegalizeActions::Legal);
 
void X86LegalizerInfo::setLegalizerInfoAVX2() {
 
   const LLT v64s8 = LLT::fixed_vector(64, 8);
   const LLT v32s16 = LLT::fixed_vector(32, 16);
   const LLT v16s32 = LLT::fixed_vector(16, 32);
   const LLT v8s64 = LLT::fixed_vector(8, 64);
 
   auto &LegacyInfo = getLegacyLegalizerInfo();
 
-  for (unsigned BinOp : {G_ADD, G_SUB})
-    for (auto Ty : {v32s8, v16s16, v8s32, v4s64})
-      LegacyInfo.setAction({BinOp, Ty}, LegacyLegalizeActions::Legal);
-
   for (auto Ty : {v16s16, v8s32})
     LegacyInfo.setAction({G_MUL, Ty}, LegacyLegalizeActions::Legal);
 
   // Merge/Unmerge
   for (const auto &Ty : {v64s8, v32s16, v16s32, v8s64}) {
     LegacyInfo.setAction({G_CONCAT_VECTORS, Ty}, LegacyLegalizeActions::Legal);
     LegacyInfo.setAction({G_UNMERGE_VALUES, 1, Ty},
                          LegacyLegalizeActions::Legal);
void X86LegalizerInfo::setLegalizerInfoAVX512() {
 
   const LLT v64s8 = LLT::fixed_vector(64, 8);
   const LLT v32s16 = LLT::fixed_vector(32, 16);
   const LLT v16s32 = LLT::fixed_vector(16, 32);
   const LLT v8s64 = LLT::fixed_vector(8, 64);
 
   auto &LegacyInfo = getLegacyLegalizerInfo();
 
-  for (unsigned BinOp : {G_ADD, G_SUB})
-    for (auto Ty : {v16s32, v8s64})
-      LegacyInfo.setAction({BinOp, Ty}, LegacyLegalizeActions::Legal);
 
   LegacyInfo.setAction({G_MUL, v16s32}, LegacyLegalizeActions::Legal);
 
   for (unsigned MemOp : {G_LOAD, G_STORE})
     for (auto Ty : {v16s32, v8s64})
       LegacyInfo.setAction({MemOp, Ty}, LegacyLegalizeActions::Legal);
 
   for (auto Ty : {v64s8, v32s16, v16s32, v8s64}) {
void X86LegalizerInfo::setLegalizerInfoAVX512DQ() {
   for (auto Ty : {v2s64, v4s64})
     LegacyInfo.setAction({G_MUL, Ty}, LegacyLegalizeActions::Legal);
 }
 
 void X86LegalizerInfo::setLegalizerInfoAVX512BW() {
   if (!(Subtarget.hasAVX512() && Subtarget.hasBWI()))
     return;
 
-  const LLT v64s8 = LLT::fixed_vector(64, 8);
   const LLT v32s16 = LLT::fixed_vector(32, 16);
 
   auto &LegacyInfo = getLegacyLegalizerInfo();
 
-  for (unsigned BinOp : {G_ADD, G_SUB})
-    for (auto Ty : {v64s8, v32s16})
-      LegacyInfo.setAction({BinOp, Ty}, LegacyLegalizeActions::Legal);
-
   LegacyInfo.setAction({G_MUL, v32s16}, LegacyLegalizeActions::Legal);
 
   /************ VLX *******************/
   if (!Subtarget.hasVLX())
     return;
 
   const LLT v8s16 = LLT::fixed_vector(8, 16);
   const LLT v16s16 = LLT::fixed_vector(16, 16);
 
   for (auto Ty : {v8s16, v16s16})
     LegacyInfo.setAction({G_MUL, Ty}, LegacyLegalizeActions::Legal);
 }