diff options
Diffstat (limited to 'src/jit/bitset.h')
| -rw-r--r-- | src/jit/bitset.h | 452 |
1 files changed, 452 insertions, 0 deletions
diff --git a/src/jit/bitset.h b/src/jit/bitset.h new file mode 100644 index 0000000000..4ecb2fc0d4 --- /dev/null +++ b/src/jit/bitset.h @@ -0,0 +1,452 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +// A set of integers in the range [0..N], for some given N. + +/*****************************************************************************/ +#ifndef _BITSET_H_ +#define _BITSET_H_ +/*****************************************************************************/ + +// This class provides some constant declarations and some static utility methods useful +// for bitset implementations. +class BitSetSupport +{ +#ifdef DEBUG + template <typename BitSetType, unsigned Brand, typename Env, typename BitSetTraits> + static void RunTests(Env env); +#endif + +public: + static const unsigned BitsInByte = 8; + + // This maps 4-bit ("nibble") values into the number of 1 bits they contain. + static unsigned BitCountTable[16]; + + // Returns the number of 1 bits in the binary representation of "u". + template <typename T> + static unsigned CountBitsInIntegral(T u) + { + unsigned res = 0; + // We process "u" in 4-bit nibbles, hence the "*2" below. + for (int i = 0; i < sizeof(T) * 2; i++) + { + res += BitCountTable[u & 0xf]; + u >>= 4; + } + return res; + } + +#ifdef DEBUG + // This runs the "TestSuite" method for a few important instantiations of BitSet. + static void TestSuite(IAllocator* env); +#endif + + enum Operation + { +#define BSOPNAME(x) x, +#include "bitsetops.h" +#undef BSOPNAME + BSOP_NUMOPS + }; + static const char* OpNames[BSOP_NUMOPS]; + + class BitSetOpCounter + { + unsigned TotalOps; + unsigned OpCounts[BSOP_NUMOPS]; + const char* m_fileName; + FILE* OpOutputFile; + + public: + BitSetOpCounter(const char* fileName) : TotalOps(0), m_fileName(fileName), OpOutputFile(nullptr) + { + for (unsigned i = 0; i < BSOP_NUMOPS; i++) + { + OpCounts[i] = 0; + } + } + + void RecordOp(Operation op); + }; +}; + +template <> +FORCEINLINE unsigned BitSetSupport::CountBitsInIntegral<unsigned>(unsigned c) +{ + // Make sure we're 32 bit. + assert(sizeof(unsigned) == 4); + c = (c & 0x55555555) + ((c >> 1) & 0x55555555); + c = (c & 0x33333333) + ((c >> 2) & 0x33333333); + c = (c & 0x0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f); + c = (c & 0x00ff00ff) + ((c >> 8) & 0x00ff00ff); + c = (c & 0x0000ffff) + ((c >> 16) & 0x0000ffff); + return c; +} + +// A "BitSet" represents a set of integers from a "universe" [0..N-1]. This implementation assumes that "N" +// (the "Size") is provided by the "Env" template argument type discussed below, and accessed from the Env +// via a static method of the BitSetTraits type discussed below. The intent of "BitSet" is that the set is +// represented as a bit array. Various binary operations therefore only make sense if the operands are +// subsets of the same universe. Further, the integers in the set that the BitSet represents may have +// different interpretations at a higher level, so even if the range of the universe stays the same, +// the higher-level meaning of those bits may change. For these reasons, we assume the Env can provide +// (again, via static methods of the BitSetTraits) the current "epoch" number. The Env must keep the +// Size the same while the epoch has a given value; a BitSet implementation may legally stamp BitSets +// with the current epoch, and assert that BitSets from different epochs are not intermixed. + +// Some implementations may use a representation that (at least sometimes) is a pointer to a +// heap-allocated data structure. (The operations of BitSetOps are static methods, rather than +// declaring a BitSet class type with multiple subtypes, to allow maximally efficient raw +// primitive type representations.) Therefore, we must be careful about assignment and +// initialization. We often want to reason about BitSets as immutable values, and just copying +// the representation would introduce sharing in the indirect case, which is usually not what's +// desired. On the other hand, there are many cases in which the RHS value has just been +// created functionally, and the intialization/assignment is obviously its last use. In these +// cases, allocating a new indirect representation for the lhs (if it does not already have one) +// would be unnecessary and wasteful. Thus, for assignment, we have a "normal" assignment +// function, which makes a copy of the referent data structure in the indirect case, and an +// "AssignNoCopy" version, which does not, and instead introduces sharing in the indirect case. +// Obviously, the latter should be used with care. +// +// (Orthogonally, there are also further versions of assignment that differ in whether the "rhs" +// argument may be uninitialized. The normal assignment operation requires the "rhs" argument not be +// uninitialized; "AssignNoCopy" has the same requirement. The "AssignAllowUninitRhs" version allows +// the "rhs" to be the uninit value, and sets the "lhs" to be uninitialized in that case.) + +// This class has static methods that provide the operations on BitSets. +// +// An instantiation requires: +// typename BitSetType: the representation type of this kind of BitSet. +// +// unsigned Brand: an integer constant. This is unused by the implementation; it exists +// *only* to ensure that we can have, if desired, multiple distinct BitSetOps +// implementations for the same BitSetType, by instantiating these with different +// values for Brand (thus "branding" them so that they are distinct from one another.) +// +// typename Env: a type that determines the (current) size of the given BitSet type, as well +// as an allocation function, and the current epoch (integer that changes when +// "universe" of the BitSet changes) -- all via static methods of the "BitSetTraits" +// type. +// +// typename BitSetTraits: +// An "adapter" class that provides methods that retrieves things from the Env: +// static IAllocator* GetAllococator(Env): yields an "IAllocator*" that the BitSet implementation can use. +// static unsigned GetSize(Env): the current size (= # of bits) of this bitset type. +// static unsigned GetArrSize(Env, unsigned elemSize): The number of "elemSize" chunks sufficient to hold +// "GetSize". A given BitSet implementation must call +// this with only one constant value. Thus, and "Env" +// may compute this result when GetSize changes. +// +// static unsigned GetEpoch(Env): the current epoch. +// +// (For many instantiations, BitSetValueArgType and BitSetValueRetType will be the same as BitSetType; in cases where +// BitSetType is a class, type, BitSetValueArgType may need to be "const BitSetType&", for example.) +// +// In addition to implementing the method signatures here, an instantiation of BitSetOps must also export a +// BitSetOps::Iter type, which supports the following operations: +// Iter(BitSetValueArgType): a constructor +// bool NextElem(unsigned* pElem): returns true if the iteration is not complete, and sets *pElem to the next +// yielded member. +// +// Finally, it should export two further types: +// +// ValArgType: the type used to pass a BitSet as a by-value argument. +// RetValType: the type that should be used to return a BitSet. +// +// For many instantiations, these can be identical to BitSetTypes. When the representation type is a class, +// however, ValArgType may need to be "const BitSetType&", and RetValArg may need to be a helper class, if the +// class hides default copy constructors and assignment operators to detect erroneous usage. +// +template <typename BitSetType, unsigned Brand, typename Env, typename BitSetTraits> +class BitSetOps +{ +#if 0 + // Below are the set of methods that an instantiation of BitSetOps should provide. This is + // #if'd out because it doesn't make any difference; C++ has no mechanism for checking that + // the methods of an instantiation are consistent with these signatures, other than the expectations + // embodied in the program that uses the instantiation(s). But it's useful documentation, and + // we should try to keep it up to date. + + public: + + // The uninitialized value -- not a real bitset (if possible). + static BitSetValueRetType UninitVal(); + + // Returns "true" iff "bs" may be the uninit value. + static bool MayBeUninit(BitSetValueArgType bs); + + // Returns the a new BitSet that is empty. Uses the Allocator of "env" to allocate memory for + // the representation, if necessary. + static BitSetValueRetType MakeEmpty(Env env); + + // Returns the a new BitSet that is "full" -- represents all the integers in the current range. + // Uses the Allocator of "env" to allocate memory for the representation, if necessary. + static BitSetValueRetType MakeFull(Env env); + + // Returns the set containing the single element "bitNum" (which is required to be within the + // BitSet's current range). Uses the Allocator of "env" to allocate memory for the representation, + // if necessary. + static BitSetValueRetType MakeSingleton(Env env, unsigned bitNum); + + // Assign "rhs" to "lhs". "rhs" must not be the uninitialized value. "lhs" may be, in which case + // "rhs" will be copied if necessary. + static void Assign(Env env, BitSetType& lhs, BitSetValueArgType rhs); + + // Assign "rhs" to "lhs"...*even* if "rhs" is the uninitialized value. + static void AssignAllowUninitRhs(Env env, BitSetType& lhs, BitSetValueArgType rhs); + + // This is a "destructive" assignment -- it should only be used if the rhs is "dead" after the assignment. + // In particular, if the rhs has a level of indirection to a heap-allocated data structure, that pointer will + // be copied into the lhs. + static void AssignNoCopy(Env env, BitSetType& lhs, BitSetValueArgType rhs); + + // Destructively set "bs" to be the empty set. This method is unique, in that it does *not* + // require "bs" to be a bitset of the current epoch. It ensures that it is after, however. + // (If the representation is indirect, this requires allocating a new, empty representation. + // If this is a performance issue, we could provide a new version of ClearD that assumes/asserts + // that the rep is for the current epoch -- this would be useful if a given bitset were repeatedly + // cleared within an epoch.) + static void ClearD(Env env, BitSetType& bs); + + // Returns a copy of "bs". If the representation of "bs" involves a level of indirection, the data + // structure is copied and a pointer to the copy is returned. + static BitSetValueRetType MakeCopy(Env env, BitSetValueArgType bs); + + // Returns "true" iff ""bs" represents the empty set. + static bool IsEmpty(Env env, BitSetValueArgType bs); + + // Returns the number of members in "bs". + static unsigned Count(Env env, BitSetValueArgType bs); + + // Returns "true" iff "i" is a member of "bs". + static bool IsMember(Env env, const BitSetValueArgType bs, unsigned i); + + // Destructively modify "bs" to ensure that "i" is a member. + static void AddElemD(Env env, BitSetType& bs, unsigned i); + // Returns a BitSet that is a copy of "bs" with "i" added. + static BitSetValueRetType AddElem(Env env, BitSetValueArgType bs, unsigned i); + + // Destructively modify "bs" to ensure that "i" is not a member. + static void RemoveElemD(Env env, BitSetType& bs, unsigned i); + // Returns a BitSet that is a copy of "bs" with "i" removed. + static BitSetValueRetType RemoveElem(Env env, BitSetValueArgType bs1, unsigned i); + + // Destructively modify "bs1" to be the union of "bs1" and "bs2". + static void UnionD(Env env, BitSetType& bs1, BitSetValueArgType bs2); + // Returns a new BitSet that is the union of "bs1" and "bs2". + static BitSetValueRetType Union(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2); + + // Destructively modify "bs1" to be the intersection of "bs1" and "bs2". + static void IntersectionD(Env env, BitSetType& bs1, BitSetValueArgType bs2); + // Returns a new BitSet that is the intersection of "bs1" and "bs2". + static BitSetValueRetType Intersection(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2); + + // Returns true iff "bs1" and "bs2" have an empty intersection. + static bool IsEmptyIntersection(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2); + + // Destructively modify "bs1" to be the set difference of "bs1" and "bs2". + static void DiffD(Env env, BitSetType& bs1, BitSetValueArgType bs2); + // Returns a new BitSet that is the set difference of "bs1" and "bs2". + static BitSetValueRetType Diff(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2); + + // Returns true iff "bs2" is a subset of "bs1." + static bool IsSubset(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2); + + // Returns true iff "bs1" and "bs2" are equal. + static bool Equal(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2); + +#ifdef DEBUG + // Returns a string representing the contents of "bs". Allocates memory for the representation + // using the Allocator of "env". + static const char* ToString(Env env, BitSetValueArgType bs); +#endif + + // Declare this as a type -- will be a real class in real instantiations. + class Iter { + public: + Iter(Env env, BitSetValueArgType bs) {} + bool NextElem(Env env, unsigned* pElem) { return false; } + }; + + typename ValArgType; + typename RetValType; +#endif // 0 -- the above is #if'd out, since it's really just an extended comment on what an instantiation + // should provide. +}; + +template <typename BitSetType, + unsigned Brand, + typename Env, + typename BitSetTraits, + typename BitSetValueArgType, + typename BitSetValueRetType, + typename BaseIter> +class BitSetOpsWithCounter +{ + typedef BitSetOps<BitSetType, Brand, Env, BitSetTraits> BSO; + +public: + static BitSetValueRetType UninitVal() + { + return BSO::UninitVal(); + } + static bool MayBeUninit(BitSetValueArgType bs) + { + return BSO::MayBeUninit(bs); + } + static BitSetValueRetType MakeEmpty(Env env) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_MakeEmpty); + return BSO::MakeEmpty(env); + } + static BitSetValueRetType MakeFull(Env env) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_MakeFull); + return BSO::MakeFull(env); + } + static BitSetValueRetType MakeSingleton(Env env, unsigned bitNum) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_MakeSingleton); + return BSO::MakeSingleton(env, bitNum); + } + static void Assign(Env env, BitSetType& lhs, BitSetValueArgType rhs) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Assign); + BSO::Assign(env, lhs, rhs); + } + static void AssignAllowUninitRhs(Env env, BitSetType& lhs, BitSetValueArgType rhs) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_AssignAllowUninitRhs); + BSO::AssignAllowUninitRhs(env, lhs, rhs); + } + static void AssignNoCopy(Env env, BitSetType& lhs, BitSetValueArgType rhs) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_AssignNocopy); + BSO::AssignNoCopy(env, lhs, rhs); + } + static void ClearD(Env env, BitSetType& bs) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_ClearD); + BSO::ClearD(env, bs); + } + static BitSetValueRetType MakeCopy(Env env, BitSetValueArgType bs) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_MakeCopy); + return BSO::MakeCopy(env, bs); + } + static bool IsEmpty(Env env, BitSetValueArgType bs) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_IsEmpty); + return BSO::IsEmpty(env, bs); + } + static unsigned Count(Env env, BitSetValueArgType bs) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Count); + return BSO::Count(env, bs); + } + static bool IsMember(Env env, const BitSetValueArgType bs, unsigned i) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_IsMember); + return BSO::IsMember(env, bs, i); + } + static void AddElemD(Env env, BitSetType& bs, unsigned i) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_AddElemD); + BSO::AddElemD(env, bs, i); + } + static BitSetValueRetType AddElem(Env env, BitSetValueArgType bs, unsigned i) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_AddElem); + return BSO::AddElem(env, bs, i); + } + static void RemoveElemD(Env env, BitSetType& bs, unsigned i) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_RemoveElemD); + BSO::RemoveElemD(env, bs, i); + } + static BitSetValueRetType RemoveElem(Env env, BitSetValueArgType bs1, unsigned i) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_RemoveElem); + return BSO::RemoveElem(env, bs1, i); + } + static void UnionD(Env env, BitSetType& bs1, BitSetValueArgType bs2) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_UnionD); + BSO::UnionD(env, bs1, bs2); + } + static BitSetValueRetType Union(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Union); + return BSO::Union(env, bs1, bs2); + } + static void IntersectionD(Env env, BitSetType& bs1, BitSetValueArgType bs2) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_IntersectionD); + BSO::IntersectionD(env, bs1, bs2); + } + static BitSetValueRetType Intersection(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Intersection); + return BSO::Intersection(env, bs1, bs2); + } + static bool IsEmptyIntersection(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_IsEmptyIntersection); + return BSO::IsEmptyIntersection(env, bs1, bs2); + } + static void DiffD(Env env, BitSetType& bs1, BitSetValueArgType bs2) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_DiffD); + BSO::DiffD(env, bs1, bs2); + } + static BitSetValueRetType Diff(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Diff); + return BSO::Diff(env, bs1, bs2); + } + static bool IsSubset(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_IsSubset); + return BSO::IsSubset(env, bs1, bs2); + } + static bool Equal(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Equal); + return BSO::Equal(env, bs1, bs2); + } +#ifdef DEBUG + static const char* ToString(Env env, BitSetValueArgType bs) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_ToString); + return BSO::ToString(env, bs); + } +#endif + + class Iter + { + BaseIter m_iter; + + public: + Iter(Env env, BitSetValueArgType bs) : m_iter(env, bs) + { + } + + bool NextElem(Env env, unsigned* pElem) + { + BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_NextBit); + return m_iter.NextElem(env, pElem); + } + }; +}; + +// We define symbolic names for the various bitset implementations available, to allow choices between them. + +#define BSUInt64 0 +#define BSShortLong 1 +#define BSUInt64Class 2 + +/*****************************************************************************/ +#endif // _BITSET_H_ +/*****************************************************************************/ |