[GlobalISel] Copy the implementation of SubtargetFeature and use it for PredicateBitset.

[craig.topper]

Summary

PredicateBitset currently uses std::bitset, but std::bitset doesn't
have a constexpr constructor or any constexpr methods until C++23.
Each target that supports GlobalIsel has as an array of PredicateBitset
objects that currently use a global constructor.

SubtargetFeature used by the MC layer for feature bits, has its own
implementation of std::bitset that has constexpr constructor and methods
that provides all the capabilities that PredicateBitset needs.

This patch copies the implementation from SubtargetFeature, makes
it a template class, and puts it in ADT. I'll migrate SubtargetFeature
in a separate patch. Adapting all existing users to it being a template
was distracting from the goal of this patch.

This reduces the binary size of llc built with gcc 8.5.0 on my local
build by ~15k.

[MaskRay]

LGTM.

This reduces the binary size of llc built with gcc 8.5.0 on my local build by ~15k.

Interesting. When building llc with near-thunk clang, the size goes down from 47637800 to 47637776 (small decrease). The small change is mainly in bool llvm::GIMatchTableExecutor::executeMatchTable

[MaskRay]

llvm/include/llvm/ADT/Bitset.h

59

The unneeded workaround was copied. I created https://reviews.llvm.org/D158687 as a cleanup.

llvm/include/llvm/ADT/Bitset.h

+//=== llvm/ADT/Bitset.h - constexpr std::bitset -----------------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines a std::bitset like container that can be used in constexprs.
+// That constructor and many of the methods are constexpr. std::bitset doesn't
+// get constexpr methods until C++23. This class also provides a constexpr
+// constructor that accepts an initializer_list of bits to set.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_BITSET_H
+#define LLVM_ADT_BITSET_H
+
+#include <llvm/ADT/STLExtras.h>
+#include <array>
+#include <climits>
+#include <cstdint>
+
+namespace llvm {
+
+/// Container class for subtarget features.
+/// This is a constexpr reimplementation of a subset of std::bitset. It would be
+/// nice to use std::bitset directly, but it doesn't support constant
+/// initialization.
+template <unsigned NumBits>
+class Bitset {
+  typedef uintptr_t BitWord;
+
+  enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT };
+
+  static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32,
+                "Unsupported word size");
+
+  static constexpr unsigned NumWords = (NumBits + BITWORD_SIZE-1) / BITWORD_SIZE;
+  std::array<BitWord, NumWords> Bits{};
+
+protected:
+  constexpr Bitset(const std::array<BitWord, NumWords> &B)
+      : Bits{B} {}
+
+public:
+  constexpr Bitset() = default;
+  constexpr Bitset(std::initializer_list<unsigned> Init) {
+    for (auto I : Init)
+      set(I);
+  }
+
+  Bitset &set() {
+    std::fill(std::begin(Bits), std::end(Bits), -BitWord(0));
+    return *this;
+  }
+
+  constexpr Bitset &set(unsigned I) {
+    // GCC <6.2 crashes if this is written in a single statement.
+    BitWord NewBits = Bits[I / BITWORD_SIZE] | (BitWord(1) << (I % BITWORD_SIZE));
+    Bits[I / BITWORD_SIZE] = NewBits;
+    return *this;
+  }
+
+  constexpr Bitset &reset(unsigned I) {
+    // GCC <6.2 crashes if this is written in a single statement.
+    BitWord NewBits = Bits[I / BITWORD_SIZE] & ~(BitWord(1) << (I % BITWORD_SIZE));
+    Bits[I / BITWORD_SIZE] = NewBits;
+    return *this;
+  }
+
+  constexpr Bitset &flip(unsigned I) {
+    // GCC <6.2 crashes if this is written in a single statement.
+    BitWord NewBits = Bits[I / BITWORD_SIZE] ^ (BitWord(1) << (I % BITWORD_SIZE));
+    Bits[I / BITWORD_SIZE] = NewBits;
+    return *this;
+  }
+
+  constexpr bool operator[](unsigned I) const {
+    BitWord Mask = BitWord(1) << (I % BITWORD_SIZE);
+    return (Bits[I / BITWORD_SIZE] & Mask) != 0;
+  }
+
+  constexpr bool test(unsigned I) const { return (*this)[I]; }
+
+  constexpr size_t size() const { return NumBits; }
+
+  bool any() const {
+    return llvm::any_of(Bits, [](BitWord I) { return I != 0; });
+  }
+  bool none() const { return !any(); }
+  size_t count() const {
+    size_t Count = 0;
+    for (auto B : Bits)
+      Count += llvm::popcount(B);
+    return Count;
+  }
+
+  constexpr Bitset &operator^=(const Bitset &RHS) {
+    for (unsigned I = 0, E = Bits.size(); I != E; ++I) {
+      Bits[I] ^= RHS.Bits[I];
+    }
+    return *this;
+  }
+  constexpr Bitset operator^(const Bitset &RHS) const {
+    Bitset Result = *this;
+    Result ^= RHS;
+    return Result;
+  }
+
+  constexpr Bitset &operator&=(const Bitset &RHS) {
+    for (unsigned I = 0, E = Bits.size(); I != E; ++I) {
+      Bits[I] &= RHS.Bits[I];
+    }
+    return *this;
+  }
+  constexpr Bitset operator&(const Bitset &RHS) const {
+    Bitset Result = *this;
+    Result &= RHS;
+    return Result;
+  }
+
+  constexpr Bitset &operator|=(const Bitset &RHS) {
+    for (unsigned I = 0, E = Bits.size(); I != E; ++I) {
+      Bits[I] |= RHS.Bits[I];
+    }
+    return *this;
+  }
+  constexpr Bitset operator|(const Bitset &RHS) const {
+    Bitset Result = *this;
+    Result |= RHS;
+    return Result;
+  }
+
+  constexpr Bitset operator~() const {
+    Bitset Result = *this;
+    for (auto &B : Result.Bits)
+      B = ~B;
+    return Result;
+  }
+
+  bool operator==(const Bitset &RHS) const {
+    return std::equal(std::begin(Bits), std::end(Bits), std::begin(RHS.Bits));
+  }
+
+  bool operator!=(const Bitset &RHS) const { return !(*this == RHS); }
+
+  bool operator < (const Bitset &Other) const {
+    for (unsigned I = 0, E = size(); I != E; ++I) {
+      bool LHS = test(I), RHS = Other.test(I);
+      if (LHS != RHS)
+        return LHS < RHS;
+    }
+    return false;
+  }
+};
+
+} // end namespace llvm
+
+#endif

llvm/include/llvm/CodeGen/GlobalISel/GIMatchTableExecutor.h

 /// by the match table, and some associated data structures used by the
 /// executor's implementation (see `GIMatchTableExecutorImpl.h`).
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_GLOBALISEL_GIMATCHTABLEEXECUTOR_H
 #define LLVM_CODEGEN_GLOBALISEL_GIMATCHTABLEEXECUTOR_H
 
+#include "llvm/ADT/Bitset.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/CodeGen/GlobalISel/Utils.h"
 #include "llvm/CodeGen/LowLevelType.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/IR/Function.h"
 #include <bitset>
 #include <cstddef>

 class MachineInstrBuilder;
 class MachineFunction;
 class MachineOperand;
 class MachineRegisterInfo;
 class RegisterBankInfo;
 class TargetInstrInfo;
 class TargetRegisterInfo;
 
-/// Container class for CodeGen predicate results.
-/// This is convenient because std::bitset does not have a constructor
-/// with an initializer list of set bits.
-///
-/// Each GIMatchTableExecutor subclass should define a PredicateBitset class
-/// with:
-///   const unsigned MAX_SUBTARGET_PREDICATES = 192;
-///   using PredicateBitset = PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;
-/// and updating the constant to suit the target. Tablegen provides a suitable
-/// definition for the predicates in use in <Target>GenGlobalISel.inc when
-/// GET_GLOBALISEL_PREDICATE_BITSET is defined.
-template <std::size_t MaxPredicates>
-class PredicateBitsetImpl : public std::bitset<MaxPredicates> {
-public:
-  // Cannot inherit constructors because it's not supported by VC++..
-  PredicateBitsetImpl() = default;
-
-  PredicateBitsetImpl(const std::bitset<MaxPredicates> &B)
-      : std::bitset<MaxPredicates>(B) {}
-
-  PredicateBitsetImpl(std::initializer_list<unsigned> Init) {
-    for (auto I : Init)
-      std::bitset<MaxPredicates>::set(I);
-  }
-};
-
 enum {
   GICXXPred_Invalid = 0,
   GICXXCustomAction_Invalid = 0,
 };
 
 enum {
   /// Begin a try-block to attempt a match and jump to OnFail if it is
   /// unsuccessful.

llvm/test/TableGen/GlobalISelEmitter.td

 
 def HasA : Predicate<"Subtarget->hasA()">;
 def HasB : Predicate<"Subtarget->hasB()">;
 def HasC : Predicate<"Subtarget->hasC()"> { let RecomputePerFunction = 1; }
 
 //===- Test the function boilerplate. -------------------------------------===//
 
 // CHECK: const unsigned MAX_SUBTARGET_PREDICATES = 3;
-// CHECK: using PredicateBitset = llvm::PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;
+// CHECK: using PredicateBitset = llvm::Bitset<MAX_SUBTARGET_PREDICATES>;
 
 // CHECK-LABEL: #ifdef GET_GLOBALISEL_TEMPORARIES_DECL
 // CHECK-NEXT:    mutable MatcherState State;
 // CHECK-NEXT:    typedef ComplexRendererFns(MyTargetInstructionSelector::*ComplexMatcherMemFn)(MachineOperand &) const;
 // CHECK-NEXT:    typedef void(MyTargetInstructionSelector::*CustomRendererFn)(MachineInstrBuilder &, const MachineInstr &, int) const;
 // CHECK-NEXT:    const ExecInfoTy<PredicateBitset, ComplexMatcherMemFn, CustomRendererFn> ExecInfo;
 // CHECK-NEXT:    static MyTargetInstructionSelector::ComplexMatcherMemFn ComplexPredicateFns[];
 // CHECK-NEXT:    static MyTargetInstructionSelector::CustomRendererFn CustomRenderers[];

 // CHECK-NEXT:  }
 
 // CHECK-LABEL: // Feature bitsets.
 // CHECK-NEXT:  enum {
 // CHECK-NEXT:    GIFBS_Invalid,
 // CHECK-NEXT:    GIFBS_HasA,
 // CHECK-NEXT:    GIFBS_HasA_HasB_HasC,
 // CHECK-NEXT:  }
-// CHECK-NEXT:  const static PredicateBitset FeatureBitsets[] {
+// CHECK-NEXT:  constexpr static PredicateBitset FeatureBitsets[] {
 // CHECK-NEXT:    {}, // GIFBS_Invalid
 // CHECK-NEXT:    {Feature_HasABit, },
 // CHECK-NEXT:    {Feature_HasABit, Feature_HasBBit, Feature_HasCBit, },
 // CHECK-NEXT:  };
 
 // CHECK-LABEL: // ComplexPattern predicates.
 // CHECK-NEXT:  enum {
 // CHECK-NEXT:    GICP_Invalid,

llvm/utils/TableGen/GlobalISelMatchTableExecutorEmitter.cpp

OS << "// Feature bitsets.\n"
      << "enum {\n"
      << "  GIFBS_Invalid,\n";
   for (const auto &FeatureBitset : FeatureBitsets) {
     if (FeatureBitset.empty())
       continue;
     OS << "  " << getNameForFeatureBitset(FeatureBitset) << ",\n";
   }
   OS << "};\n"
-     << "const static PredicateBitset FeatureBitsets[] {\n"
+     << "constexpr static PredicateBitset FeatureBitsets[] {\n"
      << "  {}, // GIFBS_Invalid\n";
   for (const auto &FeatureBitset : FeatureBitsets) {
     if (FeatureBitset.empty())
       continue;
     OS << "  {";
     for (const auto &Feature : FeatureBitset) {
       const auto &I = SubtargetFeatures.find(Feature);
       assert(I != SubtargetFeatures.end() && "Didn't import predicate?");

 }
 
 void GlobalISelMatchTableExecutorEmitter::emitPredicateBitset(
     raw_ostream &OS, StringRef IfDefName) {
   OS << "#ifdef " << IfDefName << "\n"
      << "const unsigned MAX_SUBTARGET_PREDICATES = " << SubtargetFeatures.size()
      << ";\n"
      << "using PredicateBitset = "
-        "llvm::PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;\n"
+        "llvm::Bitset<MAX_SUBTARGET_PREDICATES>;\n"
      << "#endif // ifdef " << IfDefName << "\n\n";
 }
 
 void GlobalISelMatchTableExecutorEmitter::emitTemporariesDecl(
     raw_ostream &OS, StringRef IfDefName) {
   OS << "#ifdef " << IfDefName << "\n"
      << "  mutable MatcherState State;\n"
      << "  typedef "