summaryrefslogtreecommitdiff
path: root/src/jit/bitset.h
blob: a0192e62e8de562154d24b02d8c5897719eeeb62 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
// 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(CompAllocator 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 void* Alloc(Env, size_t byteSize): Allocates memory 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.
    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);

    // Return true if the union of bs1 and bs2 is empty.
    static bool IsEmptyUnion(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2);

    // 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);

    // Compute the live_in set. Variable is alive if there is use or it is out set, but not in def.
    // in = use | (out & ~def)
    static void LivenessD(Env env, BitSetType& in, BitSetValueArgType def, BitSetValueArgType use, BitSetValueArgType out);

    // 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(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;
        Env      m_env;

    public:
        Iter(Env env, BitSetValueArgType bs) : m_iter(env, bs), m_env(env)
        {
        }

        bool NextElem(unsigned* pElem)
        {
            BitSetTraits::GetOpCounter(m_env)->RecordOp(BitSetSupport::BSOP_NextBit);
            return m_iter.NextElem(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_
/*****************************************************************************/