1 // Licensed to the .NET Foundation under one or more agreements.
2 // The .NET Foundation licenses this file to you under the MIT license.
3 // See the LICENSE file in the project root for more information.
5 // A set of integers in the range [0..N], for some given N.
7 /*****************************************************************************/
10 /*****************************************************************************/
12 // This class provides some constant declarations and some static utility methods useful
13 // for bitset implementations.
17 template <typename BitSetType, unsigned Brand, typename Env, typename BitSetTraits>
18 static void RunTests(Env env);
22 static const unsigned BitsInByte = 8;
24 // This maps 4-bit ("nibble") values into the number of 1 bits they contain.
25 static unsigned BitCountTable[16];
27 // Returns the number of 1 bits in the binary representation of "u".
29 static unsigned CountBitsInIntegral(T u)
32 // We process "u" in 4-bit nibbles, hence the "*2" below.
33 for (int i = 0; i < sizeof(T) * 2; i++)
35 res += BitCountTable[u & 0xf];
42 // This runs the "TestSuite" method for a few important instantiations of BitSet.
43 static void TestSuite(CompAllocator* env);
48 #define BSOPNAME(x) x,
49 #include "bitsetops.h"
53 static const char* OpNames[BSOP_NUMOPS];
58 unsigned OpCounts[BSOP_NUMOPS];
59 const char* m_fileName;
63 BitSetOpCounter(const char* fileName) : TotalOps(0), m_fileName(fileName), OpOutputFile(nullptr)
65 for (unsigned i = 0; i < BSOP_NUMOPS; i++)
71 void RecordOp(Operation op);
76 FORCEINLINE unsigned BitSetSupport::CountBitsInIntegral<unsigned>(unsigned c)
78 // Make sure we're 32 bit.
79 assert(sizeof(unsigned) == 4);
80 c = (c & 0x55555555) + ((c >> 1) & 0x55555555);
81 c = (c & 0x33333333) + ((c >> 2) & 0x33333333);
82 c = (c & 0x0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f);
83 c = (c & 0x00ff00ff) + ((c >> 8) & 0x00ff00ff);
84 c = (c & 0x0000ffff) + ((c >> 16) & 0x0000ffff);
88 // A "BitSet" represents a set of integers from a "universe" [0..N-1]. This implementation assumes that "N"
89 // (the "Size") is provided by the "Env" template argument type discussed below, and accessed from the Env
90 // via a static method of the BitSetTraits type discussed below. The intent of "BitSet" is that the set is
91 // represented as a bit array. Various binary operations therefore only make sense if the operands are
92 // subsets of the same universe. Further, the integers in the set that the BitSet represents may have
93 // different interpretations at a higher level, so even if the range of the universe stays the same,
94 // the higher-level meaning of those bits may change. For these reasons, we assume the Env can provide
95 // (again, via static methods of the BitSetTraits) the current "epoch" number. The Env must keep the
96 // Size the same while the epoch has a given value; a BitSet implementation may legally stamp BitSets
97 // with the current epoch, and assert that BitSets from different epochs are not intermixed.
99 // Some implementations may use a representation that (at least sometimes) is a pointer to a
100 // heap-allocated data structure. (The operations of BitSetOps are static methods, rather than
101 // declaring a BitSet class type with multiple subtypes, to allow maximally efficient raw
102 // primitive type representations.) Therefore, we must be careful about assignment and
103 // initialization. We often want to reason about BitSets as immutable values, and just copying
104 // the representation would introduce sharing in the indirect case, which is usually not what's
105 // desired. On the other hand, there are many cases in which the RHS value has just been
106 // created functionally, and the intialization/assignment is obviously its last use. In these
107 // cases, allocating a new indirect representation for the lhs (if it does not already have one)
108 // would be unnecessary and wasteful. Thus, for assignment, we have a "normal" assignment
109 // function, which makes a copy of the referent data structure in the indirect case, and an
110 // "AssignNoCopy" version, which does not, and instead introduces sharing in the indirect case.
111 // Obviously, the latter should be used with care.
113 // (Orthogonally, there are also further versions of assignment that differ in whether the "rhs"
114 // argument may be uninitialized. The normal assignment operation requires the "rhs" argument not be
115 // uninitialized; "AssignNoCopy" has the same requirement. The "AssignAllowUninitRhs" version allows
116 // the "rhs" to be the uninit value, and sets the "lhs" to be uninitialized in that case.)
118 // This class has static methods that provide the operations on BitSets.
120 // An instantiation requires:
121 // typename BitSetType: the representation type of this kind of BitSet.
123 // unsigned Brand: an integer constant. This is unused by the implementation; it exists
124 // *only* to ensure that we can have, if desired, multiple distinct BitSetOps
125 // implementations for the same BitSetType, by instantiating these with different
126 // values for Brand (thus "branding" them so that they are distinct from one another.)
128 // typename Env: a type that determines the (current) size of the given BitSet type, as well
129 // as an allocation function, and the current epoch (integer that changes when
130 // "universe" of the BitSet changes) -- all via static methods of the "BitSetTraits"
133 // typename BitSetTraits:
134 // An "adapter" class that provides methods that retrieves things from the Env:
135 // static void* Alloc(Env, size_t byteSize): Allocates memory the BitSet implementation can use.
136 // static unsigned GetSize(Env): the current size (= # of bits) of this bitset type.
137 // static unsigned GetArrSize(Env, unsigned elemSize): The number of "elemSize" chunks sufficient to hold
138 // "GetSize". A given BitSet implementation must call
139 // this with only one constant value. Thus, and "Env"
140 // may compute this result when GetSize changes.
142 // static unsigned GetEpoch(Env): the current epoch.
144 // (For many instantiations, BitSetValueArgType and BitSetValueRetType will be the same as BitSetType; in cases where
145 // BitSetType is a class, type, BitSetValueArgType may need to be "const BitSetType&", for example.)
147 // In addition to implementing the method signatures here, an instantiation of BitSetOps must also export a
148 // BitSetOps::Iter type, which supports the following operations:
149 // Iter(BitSetValueArgType): a constructor
150 // bool NextElem(unsigned* pElem): returns true if the iteration is not complete, and sets *pElem to the next
153 // Finally, it should export two further types:
155 // ValArgType: the type used to pass a BitSet as a by-value argument.
156 // RetValType: the type that should be used to return a BitSet.
158 // For many instantiations, these can be identical to BitSetTypes. When the representation type is a class,
159 // however, ValArgType may need to be "const BitSetType&", and RetValArg may need to be a helper class, if the
160 // class hides default copy constructors and assignment operators to detect erroneous usage.
162 template <typename BitSetType, unsigned Brand, typename Env, typename BitSetTraits>
166 // Below are the set of methods that an instantiation of BitSetOps should provide. This is
167 // #if'd out because it doesn't make any difference; C++ has no mechanism for checking that
168 // the methods of an instantiation are consistent with these signatures, other than the expectations
169 // embodied in the program that uses the instantiation(s). But it's useful documentation, and
170 // we should try to keep it up to date.
174 // The uninitialized value -- not a real bitset (if possible).
175 static BitSetValueRetType UninitVal();
177 // Returns "true" iff "bs" may be the uninit value.
178 static bool MayBeUninit(BitSetValueArgType bs);
180 // Returns the a new BitSet that is empty. Uses the Allocator of "env" to allocate memory for
181 // the representation, if necessary.
182 static BitSetValueRetType MakeEmpty(Env env);
184 // Returns the a new BitSet that is "full" -- represents all the integers in the current range.
185 // Uses the Allocator of "env" to allocate memory for the representation, if necessary.
186 static BitSetValueRetType MakeFull(Env env);
188 // Returns the set containing the single element "bitNum" (which is required to be within the
189 // BitSet's current range). Uses the Allocator of "env" to allocate memory for the representation,
191 static BitSetValueRetType MakeSingleton(Env env, unsigned bitNum);
193 // Assign "rhs" to "lhs". "rhs" must not be the uninitialized value. "lhs" may be, in which case
194 // "rhs" will be copied if necessary.
195 static void Assign(Env env, BitSetType& lhs, BitSetValueArgType rhs);
197 // Assign "rhs" to "lhs"...*even* if "rhs" is the uninitialized value.
198 static void AssignAllowUninitRhs(Env env, BitSetType& lhs, BitSetValueArgType rhs);
200 // This is a "destructive" assignment -- it should only be used if the rhs is "dead" after the assignment.
201 // In particular, if the rhs has a level of indirection to a heap-allocated data structure, that pointer will
202 // be copied into the lhs.
203 static void AssignNoCopy(Env env, BitSetType& lhs, BitSetValueArgType rhs);
205 // Destructively set "bs" to be the empty set.
206 static void ClearD(Env env, BitSetType& bs);
208 // Returns a copy of "bs". If the representation of "bs" involves a level of indirection, the data
209 // structure is copied and a pointer to the copy is returned.
210 static BitSetValueRetType MakeCopy(Env env, BitSetValueArgType bs);
212 // Returns "true" iff ""bs" represents the empty set.
213 static bool IsEmpty(Env env, BitSetValueArgType bs);
215 // Returns the number of members in "bs".
216 static unsigned Count(Env env, BitSetValueArgType bs);
218 // Return true if the union of bs1 and bs2 is empty.
219 static bool IsEmptyUnion(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2);
221 // Returns "true" iff "i" is a member of "bs".
222 static bool IsMember(Env env, const BitSetValueArgType bs, unsigned i);
224 // Destructively modify "bs" to ensure that "i" is a member.
225 static void AddElemD(Env env, BitSetType& bs, unsigned i);
226 // Returns a BitSet that is a copy of "bs" with "i" added.
227 static BitSetValueRetType AddElem(Env env, BitSetValueArgType bs, unsigned i);
229 // Destructively modify "bs" to ensure that "i" is not a member.
230 static void RemoveElemD(Env env, BitSetType& bs, unsigned i);
231 // Returns a BitSet that is a copy of "bs" with "i" removed.
232 static BitSetValueRetType RemoveElem(Env env, BitSetValueArgType bs1, unsigned i);
234 // Destructively modify "bs1" to be the union of "bs1" and "bs2".
235 static void UnionD(Env env, BitSetType& bs1, BitSetValueArgType bs2);
236 // Returns a new BitSet that is the union of "bs1" and "bs2".
237 static BitSetValueRetType Union(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2);
239 // Destructively modify "bs1" to be the intersection of "bs1" and "bs2".
240 static void IntersectionD(Env env, BitSetType& bs1, BitSetValueArgType bs2);
241 // Returns a new BitSet that is the intersection of "bs1" and "bs2".
242 static BitSetValueRetType Intersection(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2);
244 // Returns true iff "bs1" and "bs2" have an empty intersection.
245 static bool IsEmptyIntersection(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2);
247 // Destructively modify "bs1" to be the set difference of "bs1" and "bs2".
248 static void DiffD(Env env, BitSetType& bs1, BitSetValueArgType bs2);
250 // Returns a new BitSet that is the set difference of "bs1" and "bs2".
251 static BitSetValueRetType Diff(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2);
253 // Compute the live_in set. Variable is alive if there is use or it is out set, but not in def.
254 // in = use | (out & ~def)
255 static void LivenessD(Env env, BitSetType& in, BitSetValueArgType def, BitSetValueArgType use, BitSetValueArgType out);
257 // Returns true iff "bs2" is a subset of "bs1."
258 static bool IsSubset(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2);
260 // Returns true iff "bs1" and "bs2" are equal.
261 static bool Equal(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2);
264 // Returns a string representing the contents of "bs". Allocates memory for the representation
265 // using the Allocator of "env".
266 static const char* ToString(Env env, BitSetValueArgType bs);
269 // Declare this as a type -- will be a real class in real instantiations.
272 Iter(Env env, BitSetValueArgType bs) {}
273 bool NextElem(unsigned* pElem) { return false; }
278 #endif // 0 -- the above is #if'd out, since it's really just an extended comment on what an instantiation
282 template <typename BitSetType,
285 typename BitSetTraits,
286 typename BitSetValueArgType,
287 typename BitSetValueRetType,
289 class BitSetOpsWithCounter
291 typedef BitSetOps<BitSetType, Brand, Env, BitSetTraits> BSO;
294 static BitSetValueRetType UninitVal()
296 return BSO::UninitVal();
298 static bool MayBeUninit(BitSetValueArgType bs)
300 return BSO::MayBeUninit(bs);
302 static BitSetValueRetType MakeEmpty(Env env)
304 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_MakeEmpty);
305 return BSO::MakeEmpty(env);
307 static BitSetValueRetType MakeFull(Env env)
309 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_MakeFull);
310 return BSO::MakeFull(env);
312 static BitSetValueRetType MakeSingleton(Env env, unsigned bitNum)
314 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_MakeSingleton);
315 return BSO::MakeSingleton(env, bitNum);
317 static void Assign(Env env, BitSetType& lhs, BitSetValueArgType rhs)
319 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Assign);
320 BSO::Assign(env, lhs, rhs);
322 static void AssignAllowUninitRhs(Env env, BitSetType& lhs, BitSetValueArgType rhs)
324 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_AssignAllowUninitRhs);
325 BSO::AssignAllowUninitRhs(env, lhs, rhs);
327 static void AssignNoCopy(Env env, BitSetType& lhs, BitSetValueArgType rhs)
329 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_AssignNocopy);
330 BSO::AssignNoCopy(env, lhs, rhs);
332 static void ClearD(Env env, BitSetType& bs)
334 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_ClearD);
335 BSO::ClearD(env, bs);
337 static BitSetValueRetType MakeCopy(Env env, BitSetValueArgType bs)
339 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_MakeCopy);
340 return BSO::MakeCopy(env, bs);
342 static bool IsEmpty(Env env, BitSetValueArgType bs)
344 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_IsEmpty);
345 return BSO::IsEmpty(env, bs);
347 static unsigned Count(Env env, BitSetValueArgType bs)
349 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Count);
350 return BSO::Count(env, bs);
352 static bool IsMember(Env env, const BitSetValueArgType bs, unsigned i)
354 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_IsMember);
355 return BSO::IsMember(env, bs, i);
357 static void AddElemD(Env env, BitSetType& bs, unsigned i)
359 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_AddElemD);
360 BSO::AddElemD(env, bs, i);
362 static BitSetValueRetType AddElem(Env env, BitSetValueArgType bs, unsigned i)
364 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_AddElem);
365 return BSO::AddElem(env, bs, i);
367 static void RemoveElemD(Env env, BitSetType& bs, unsigned i)
369 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_RemoveElemD);
370 BSO::RemoveElemD(env, bs, i);
372 static BitSetValueRetType RemoveElem(Env env, BitSetValueArgType bs1, unsigned i)
374 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_RemoveElem);
375 return BSO::RemoveElem(env, bs1, i);
377 static void UnionD(Env env, BitSetType& bs1, BitSetValueArgType bs2)
379 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_UnionD);
380 BSO::UnionD(env, bs1, bs2);
382 static BitSetValueRetType Union(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2)
384 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Union);
385 return BSO::Union(env, bs1, bs2);
387 static void IntersectionD(Env env, BitSetType& bs1, BitSetValueArgType bs2)
389 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_IntersectionD);
390 BSO::IntersectionD(env, bs1, bs2);
392 static BitSetValueRetType Intersection(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2)
394 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Intersection);
395 return BSO::Intersection(env, bs1, bs2);
397 static bool IsEmptyIntersection(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2)
399 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_IsEmptyIntersection);
400 return BSO::IsEmptyIntersection(env, bs1, bs2);
402 static void DiffD(Env env, BitSetType& bs1, BitSetValueArgType bs2)
404 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_DiffD);
405 BSO::DiffD(env, bs1, bs2);
407 static BitSetValueRetType Diff(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2)
409 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Diff);
410 return BSO::Diff(env, bs1, bs2);
412 static bool IsSubset(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2)
414 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_IsSubset);
415 return BSO::IsSubset(env, bs1, bs2);
417 static bool Equal(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2)
419 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Equal);
420 return BSO::Equal(env, bs1, bs2);
423 static const char* ToString(Env env, BitSetValueArgType bs)
425 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_ToString);
426 return BSO::ToString(env, bs);
436 Iter(Env env, BitSetValueArgType bs) : m_iter(env, bs), m_env(env)
440 bool NextElem(unsigned* pElem)
442 BitSetTraits::GetOpCounter(m_env)->RecordOp(BitSetSupport::BSOP_NextBit);
443 return m_iter.NextElem(pElem);
448 // We define symbolic names for the various bitset implementations available, to allow choices between them.
451 #define BSShortLong 1
452 #define BSUInt64Class 2
454 /*****************************************************************************/
456 /*****************************************************************************/