diff --git a/llvm/include/llvm/ADT/Bitset.h b/llvm/include/llvm/ADT/Bitset.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/ADT/Bitset.h @@ -0,0 +1,160 @@ +//=== 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 +#include +#include +#include + +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 +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 Bits{}; + +protected: + constexpr Bitset(const std::array &B) + : Bits{B} {} + +public: + constexpr Bitset() = default; + constexpr Bitset(std::initializer_list 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 diff --git a/llvm/include/llvm/CodeGen/GlobalISel/GIMatchTableExecutor.h b/llvm/include/llvm/CodeGen/GlobalISel/GIMatchTableExecutor.h --- a/llvm/include/llvm/CodeGen/GlobalISel/GIMatchTableExecutor.h +++ b/llvm/include/llvm/CodeGen/GlobalISel/GIMatchTableExecutor.h @@ -15,6 +15,7 @@ #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" @@ -47,32 +48,6 @@ 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; -/// and updating the constant to suit the target. Tablegen provides a suitable -/// definition for the predicates in use in GenGlobalISel.inc when -/// GET_GLOBALISEL_PREDICATE_BITSET is defined. -template -class PredicateBitsetImpl : public std::bitset { -public: - // Cannot inherit constructors because it's not supported by VC++.. - PredicateBitsetImpl() = default; - - PredicateBitsetImpl(const std::bitset &B) - : std::bitset(B) {} - - PredicateBitsetImpl(std::initializer_list Init) { - for (auto I : Init) - std::bitset::set(I); - } -}; - enum { GICXXPred_Invalid = 0, GICXXCustomAction_Invalid = 0, diff --git a/llvm/test/TableGen/GlobalISelEmitter.td b/llvm/test/TableGen/GlobalISelEmitter.td --- a/llvm/test/TableGen/GlobalISelEmitter.td +++ b/llvm/test/TableGen/GlobalISelEmitter.td @@ -67,7 +67,7 @@ //===- Test the function boilerplate. -------------------------------------===// // CHECK: const unsigned MAX_SUBTARGET_PREDICATES = 3; -// CHECK: using PredicateBitset = llvm::PredicateBitsetImpl; +// CHECK: using PredicateBitset = llvm::Bitset; // CHECK-LABEL: #ifdef GET_GLOBALISEL_TEMPORARIES_DECL // CHECK-NEXT: mutable MatcherState State; @@ -131,7 +131,7 @@ // 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, }, diff --git a/llvm/utils/TableGen/GlobalISelMatchTableExecutorEmitter.cpp b/llvm/utils/TableGen/GlobalISelMatchTableExecutorEmitter.cpp --- a/llvm/utils/TableGen/GlobalISelMatchTableExecutorEmitter.cpp +++ b/llvm/utils/TableGen/GlobalISelMatchTableExecutorEmitter.cpp @@ -79,7 +79,7 @@ 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()) @@ -188,7 +188,7 @@ << "const unsigned MAX_SUBTARGET_PREDICATES = " << SubtargetFeatures.size() << ";\n" << "using PredicateBitset = " - "llvm::PredicateBitsetImpl;\n" + "llvm::Bitset;\n" << "#endif // ifdef " << IfDefName << "\n\n"; }