src/jit/bitset.cpp

   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
  15 unsigned 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
  22 template <typename BitSetType, unsigned Uniq, typename Env, typename BitSetTraits>
  23 void 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
  98 class TestBitSetTraits
  99 {
 100 public:
 101     static void* Alloc(CompAllocator* alloc, size_t byteSize)
 102     {
 103         return alloc->Alloc(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
 120 void 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
 129 const char* BitSetSupport::OpNames[BitSetSupport::BSOP_NUMOPS] = {
 130 #define BSOPNAME(x) #x,
 131 #include "bitsetops.h"
 132 #undef BSOPNAME
 133 };
 134
 135 void 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 }