summaryrefslogtreecommitdiff
path: root/src/jit/bitset.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/jit/bitset.cpp')
-rw-r--r--src/jit/bitset.cpp185
1 files changed, 185 insertions, 0 deletions
diff --git a/src/jit/bitset.cpp b/src/jit/bitset.cpp
new file mode 100644
index 0000000000..90ef253199
--- /dev/null
+++ b/src/jit/bitset.cpp
@@ -0,0 +1,185 @@
+// 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.
+
+#include "jitpch.h"
+#ifdef _MSC_VER
+#pragma hdrstop
+#endif
+#include "bitset.h"
+#include "bitsetasuint64.h"
+#include "bitsetasshortlong.h"
+#include "bitsetasuint64inclass.h"
+
+// clang-format off
+unsigned BitSetSupport::BitCountTable[16] = { 0, 1, 1, 2,
+ 1, 2, 2, 3,
+ 1, 2, 2, 3,
+ 2, 3, 3, 4 };
+// clang-format on
+
+#ifdef DEBUG
+template <typename BitSetType, unsigned Uniq, typename Env, typename BitSetTraits>
+void BitSetSupport::RunTests(Env env)
+{
+
+ typedef BitSetOps<BitSetType, Uniq, Env, BitSetTraits> LclBitSetOps;
+
+ // The tests require that the Size is at least 52...
+ assert(BitSetTraits::GetSize(env) > 51);
+
+ BitSetType bs1;
+ LclBitSetOps::AssignNoCopy(env, bs1, LclBitSetOps::MakeEmpty(env));
+ unsigned bs1bits[] = {0, 10, 44, 45};
+ LclBitSetOps::AddElemD(env, bs1, bs1bits[0]);
+ LclBitSetOps::AddElemD(env, bs1, bs1bits[1]);
+ LclBitSetOps::AddElemD(env, bs1, bs1bits[2]);
+ LclBitSetOps::AddElemD(env, bs1, bs1bits[3]);
+
+ typename LclBitSetOps::Iter bsi(env, bs1);
+ unsigned bitNum = 0;
+ unsigned k = 0;
+ while (bsi.NextElem(env, &bitNum))
+ {
+ assert(bitNum == bs1bits[k]);
+ k++;
+ }
+ assert(k == 4);
+
+ assert(LclBitSetOps::Equal(env, bs1, LclBitSetOps::Union(env, bs1, bs1)));
+ assert(LclBitSetOps::Equal(env, bs1, LclBitSetOps::Intersection(env, bs1, bs1)));
+ assert(LclBitSetOps::IsSubset(env, bs1, bs1));
+
+ BitSetType bs2;
+ LclBitSetOps::AssignNoCopy(env, bs2, LclBitSetOps::MakeEmpty(env));
+ unsigned bs2bits[] = {0, 10, 50, 51};
+ LclBitSetOps::AddElemD(env, bs2, bs2bits[0]);
+ LclBitSetOps::AddElemD(env, bs2, bs2bits[1]);
+ LclBitSetOps::AddElemD(env, bs2, bs2bits[2]);
+ LclBitSetOps::AddElemD(env, bs2, bs2bits[3]);
+
+ unsigned unionBits[] = {0, 10, 44, 45, 50, 51};
+ BitSetType bsU12;
+ LclBitSetOps::AssignNoCopy(env, bsU12, LclBitSetOps::Union(env, bs1, bs2));
+ k = 0;
+ bsi = typename LclBitSetOps::Iter(env, bsU12);
+ bitNum = 0;
+ while (bsi.NextElem(env, &bitNum))
+ {
+ assert(bitNum == unionBits[k]);
+ k++;
+ }
+ assert(k == 6);
+
+ k = 0;
+ typename LclBitSetOps::Iter bsiL = typename LclBitSetOps::Iter(env, bsU12);
+ bitNum = 0;
+ while (bsiL.NextElem(env, &bitNum))
+ {
+ assert(bitNum == unionBits[k]);
+ k++;
+ }
+ assert(k == 6);
+
+ unsigned intersectionBits[] = {0, 10};
+ BitSetType bsI12;
+ LclBitSetOps::AssignNoCopy(env, bsI12, LclBitSetOps::Intersection(env, bs1, bs2));
+ k = 0;
+ bsi = typename LclBitSetOps::Iter(env, bsI12);
+ bitNum = 0;
+ while (bsi.NextElem(env, &bitNum))
+ {
+ assert(bitNum == intersectionBits[k]);
+ k++;
+ }
+ assert(k == 2);
+}
+
+class TestBitSetTraits
+{
+public:
+ static IAllocator* GetAllocator(IAllocator* alloc)
+ {
+ return alloc;
+ }
+ static unsigned GetSize(IAllocator* alloc)
+ {
+ return 64;
+ }
+ static unsigned GetArrSize(IAllocator* alloc, unsigned elemSize)
+ {
+ assert(elemSize == sizeof(size_t));
+ return (64 / 8) / sizeof(size_t);
+ }
+ static unsigned GetEpoch(IAllocator* alloc)
+ {
+ return 0;
+ }
+};
+
+void BitSetSupport::TestSuite(IAllocator* env)
+{
+ BitSetSupport::RunTests<UINT64, BSUInt64, IAllocator*, TestBitSetTraits>(env);
+ BitSetSupport::RunTests<BitSetShortLongRep, BSShortLong, IAllocator*, TestBitSetTraits>(env);
+ BitSetSupport::RunTests<BitSetUint64<IAllocator*, TestBitSetTraits>, BSUInt64Class, IAllocator*, TestBitSetTraits>(
+ env);
+}
+#endif
+
+const char* BitSetSupport::OpNames[BitSetSupport::BSOP_NUMOPS] = {
+#define BSOPNAME(x) #x,
+#include "bitsetops.h"
+#undef BSOPNAME
+};
+
+void BitSetSupport::BitSetOpCounter::RecordOp(BitSetSupport::Operation op)
+{
+ OpCounts[op]++;
+ TotalOps++;
+
+ if ((TotalOps % 1000000) == 0)
+ {
+ if (OpOutputFile == nullptr)
+ {
+ OpOutputFile = fopen(m_fileName, "a");
+ }
+ fprintf(OpOutputFile, "@ %d total ops.\n", TotalOps);
+
+ unsigned OpOrder[BSOP_NUMOPS];
+ bool OpOrdered[BSOP_NUMOPS];
+
+ // First sort by total operations (into an index permutation array, using a simple n^2 sort).
+ for (unsigned k = 0; k < BitSetSupport::BSOP_NUMOPS; k++)
+ {
+ OpOrdered[k] = false;
+ }
+ for (unsigned k = 0; k < BitSetSupport::BSOP_NUMOPS; k++)
+ {
+ bool candSet = false;
+ unsigned cand = 0;
+ unsigned candInd = 0;
+ for (unsigned j = 0; j < BitSetSupport::BSOP_NUMOPS; j++)
+ {
+ if (OpOrdered[j])
+ {
+ continue;
+ }
+ if (!candSet || OpCounts[j] > cand)
+ {
+ candInd = j;
+ cand = OpCounts[j];
+ candSet = true;
+ }
+ }
+ assert(candSet);
+ OpOrder[k] = candInd;
+ OpOrdered[candInd] = true;
+ }
+
+ for (unsigned ii = 0; ii < BitSetSupport::BSOP_NUMOPS; ii++)
+ {
+ unsigned i = OpOrder[ii];
+ fprintf(OpOutputFile, " Op %40s: %8d\n", OpNames[i], OpCounts[i]);
+ }
+ }
+}