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.
4
5#include "jitpch.h"
6#ifdef _MSC_VER
7#pragma hdrstop
8#endif
9#include "bitset.h"
10#include "bitsetasuint64.h"
11#include "bitsetasshortlong.h"
12#include "bitsetasuint64inclass.h"
13
14// clang-format off
15unsigned BitSetSupport::BitCountTable[16] = { 0, 1, 1, 2,
16 1, 2, 2, 3,
17 1, 2, 2, 3,
18 2, 3, 3, 4 };
19// clang-format on
20
21#ifdef DEBUG
22template <typename BitSetType, unsigned Uniq, typename Env, typename BitSetTraits>
23void BitSetSupport::RunTests(Env env)
24{
25
26 typedef BitSetOps<BitSetType, Uniq, Env, BitSetTraits> LclBitSetOps;
27
28 // The tests require that the Size is at least 52...
29 assert(BitSetTraits::GetSize(env) > 51);
30
31 BitSetType bs1;
32 LclBitSetOps::AssignNoCopy(env, bs1, LclBitSetOps::MakeEmpty(env));
33 unsigned bs1bits[] = {0, 10, 44, 45};
34 LclBitSetOps::AddElemD(env, bs1, bs1bits[0]);
35 LclBitSetOps::AddElemD(env, bs1, bs1bits[1]);
36 LclBitSetOps::AddElemD(env, bs1, bs1bits[2]);
37 LclBitSetOps::AddElemD(env, bs1, bs1bits[3]);
38
39 typename LclBitSetOps::Iter bsi(env, bs1);
40 unsigned bitNum = 0;
41 unsigned k = 0;
42 while (bsi.NextElem(&bitNum))
43 {
44 assert(bitNum == bs1bits[k]);
45 k++;
46 }
47 assert(k == 4);
48
49 assert(LclBitSetOps::Equal(env, bs1, LclBitSetOps::Union(env, bs1, bs1)));
50 assert(LclBitSetOps::Equal(env, bs1, LclBitSetOps::Intersection(env, bs1, bs1)));
51 assert(LclBitSetOps::IsSubset(env, bs1, bs1));
52
53 BitSetType bs2;
54 LclBitSetOps::AssignNoCopy(env, bs2, LclBitSetOps::MakeEmpty(env));
55 unsigned bs2bits[] = {0, 10, 50, 51};
56 LclBitSetOps::AddElemD(env, bs2, bs2bits[0]);
57 LclBitSetOps::AddElemD(env, bs2, bs2bits[1]);
58 LclBitSetOps::AddElemD(env, bs2, bs2bits[2]);
59 LclBitSetOps::AddElemD(env, bs2, bs2bits[3]);
60
61 unsigned unionBits[] = {0, 10, 44, 45, 50, 51};
62 BitSetType bsU12;
63 LclBitSetOps::AssignNoCopy(env, bsU12, LclBitSetOps::Union(env, bs1, bs2));
64 k = 0;
65 bsi = typename LclBitSetOps::Iter(env, bsU12);
66 bitNum = 0;
67 while (bsi.NextElem(&bitNum))
68 {
69 assert(bitNum == unionBits[k]);
70 k++;
71 }
72 assert(k == 6);
73
74 k = 0;
75 typename LclBitSetOps::Iter bsiL = typename LclBitSetOps::Iter(env, bsU12);
76 bitNum = 0;
77 while (bsiL.NextElem(&bitNum))
78 {
79 assert(bitNum == unionBits[k]);
80 k++;
81 }
82 assert(k == 6);
83
84 unsigned intersectionBits[] = {0, 10};
85 BitSetType bsI12;
86 LclBitSetOps::AssignNoCopy(env, bsI12, LclBitSetOps::Intersection(env, bs1, bs2));
87 k = 0;
88 bsi = typename LclBitSetOps::Iter(env, bsI12);
89 bitNum = 0;
90 while (bsi.NextElem(&bitNum))
91 {
92 assert(bitNum == intersectionBits[k]);
93 k++;
94 }
95 assert(k == 2);
96}
97
98class TestBitSetTraits
99{
100public:
101 static void* Alloc(CompAllocator alloc, size_t byteSize)
102 {
103 return alloc.allocate<char>(byteSize);
104 }
105 static unsigned GetSize(CompAllocator alloc)
106 {
107 return 64;
108 }
109 static unsigned GetArrSize(CompAllocator alloc, unsigned elemSize)
110 {
111 assert(elemSize == sizeof(size_t));
112 return (64 / 8) / sizeof(size_t);
113 }
114 static unsigned GetEpoch(CompAllocator alloc)
115 {
116 return 0;
117 }
118};
119
120void BitSetSupport::TestSuite(CompAllocator env)
121{
122 BitSetSupport::RunTests<UINT64, BSUInt64, CompAllocator, TestBitSetTraits>(env);
123 BitSetSupport::RunTests<BitSetShortLongRep, BSShortLong, CompAllocator, TestBitSetTraits>(env);
124 BitSetSupport::RunTests<BitSetUint64<CompAllocator, TestBitSetTraits>, BSUInt64Class, CompAllocator,
125 TestBitSetTraits>(env);
126}
127#endif
128
129const char* BitSetSupport::OpNames[BitSetSupport::BSOP_NUMOPS] = {
130#define BSOPNAME(x) #x,
131#include "bitsetops.h"
132#undef BSOPNAME
133};
134
135void BitSetSupport::BitSetOpCounter::RecordOp(BitSetSupport::Operation op)
136{
137 OpCounts[op]++;
138 TotalOps++;
139
140 if ((TotalOps % 1000000) == 0)
141 {
142 if (OpOutputFile == nullptr)
143 {
144 OpOutputFile = fopen(m_fileName, "a");
145 }
146 fprintf(OpOutputFile, "@ %d total ops.\n", TotalOps);
147
148 unsigned OpOrder[BSOP_NUMOPS];
149 bool OpOrdered[BSOP_NUMOPS];
150
151 // First sort by total operations (into an index permutation array, using a simple n^2 sort).
152 for (unsigned k = 0; k < BitSetSupport::BSOP_NUMOPS; k++)
153 {
154 OpOrdered[k] = false;
155 }
156 for (unsigned k = 0; k < BitSetSupport::BSOP_NUMOPS; k++)
157 {
158 bool candSet = false;
159 unsigned cand = 0;
160 unsigned candInd = 0;
161 for (unsigned j = 0; j < BitSetSupport::BSOP_NUMOPS; j++)
162 {
163 if (OpOrdered[j])
164 {
165 continue;
166 }
167 if (!candSet || OpCounts[j] > cand)
168 {
169 candInd = j;
170 cand = OpCounts[j];
171 candSet = true;
172 }
173 }
174 assert(candSet);
175 OpOrder[k] = candInd;
176 OpOrdered[candInd] = true;
177 }
178
179 for (unsigned ii = 0; ii < BitSetSupport::BSOP_NUMOPS; ii++)
180 {
181 unsigned i = OpOrder[ii];
182 fprintf(OpOutputFile, " Op %40s: %8d\n", OpNames[i], OpCounts[i]);
183 }
184 }
185}
186