src/jit/bitsetasuint64.h

   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 #ifndef bitSetAsUint64_DEFINED
   6 #define bitSetAsUint64_DEFINED 1
   7
   8 #include "bitset.h"
   9
  10 template <typename Env, typename BitSetTraits>
  11 class BitSetOps</*BitSetType*/ UINT64,
  12                 /*Brand*/ BSUInt64,
  13                 /*Env*/ Env,
  14                 /*BitSetTraits*/ BitSetTraits>
  15 {
  16 public:
  17     typedef UINT64 Rep;
  18
  19 private:
  20     static UINT64 Singleton(unsigned bitNum)
  21     {
  22         assert(bitNum < sizeof(UINT64) * BitSetSupport::BitsInByte);
  23         return (UINT64)1 << bitNum;
  24     }
  25
  26 public:
  27     static void Assign(Env env, UINT64& lhs, UINT64 rhs)
  28     {
  29         lhs = rhs;
  30     }
  31
  32     static void AssignNouninit(Env env, UINT64& lhs, UINT64 rhs)
  33     {
  34         lhs = rhs;
  35     }
  36
  37     static void AssignAllowUninitRhs(Env env, UINT64& lhs, UINT64 rhs)
  38     {
  39         lhs = rhs;
  40     }
  41
  42     static void AssignNoCopy(Env env, UINT64& lhs, UINT64 rhs)
  43     {
  44         lhs = rhs;
  45     }
  46
  47     static void ClearD(Env env, UINT64& bs)
  48     {
  49         bs = 0;
  50     }
  51
  52     static UINT64 MakeSingleton(Env env, unsigned bitNum)
  53     {
  54         assert(bitNum < BitSetTraits::GetSize(env));
  55         return Singleton(bitNum);
  56     }
  57
  58     static UINT64 MakeCopy(Env env, UINT64 bs)
  59     {
  60         return bs;
  61     }
  62
  63     static bool IsEmpty(Env env, UINT64 bs)
  64     {
  65         return bs == 0;
  66     }
  67
  68     static unsigned Count(Env env, UINT64 bs)
  69     {
  70         return BitSetSupport::CountBitsInIntegral(bs);
  71     }
  72
  73     static bool IsEmptyUnion(Env env, UINT64 bs1, UINT64 bs2)
  74     {
  75         return (bs1 | bs2) == 0;
  76     }
  77
  78     static void UnionD(Env env, UINT64& bs1, UINT64 bs2)
  79     {
  80         bs1 |= bs2;
  81     }
  82
  83     static UINT64 Union(Env env, UINT64& bs1, UINT64 bs2)
  84     {
  85         return bs1 | bs2;
  86     }
  87
  88     static void DiffD(Env env, UINT64& bs1, UINT64 bs2)
  89     {
  90         bs1 = bs1 & ~bs2;
  91     }
  92
  93     static UINT64 Diff(Env env, UINT64 bs1, UINT64 bs2)
  94     {
  95         return bs1 & ~bs2;
  96     }
  97
  98     static void RemoveElemD(Env env, UINT64& bs1, unsigned i)
  99     {
 100         assert(i < BitSetTraits::GetSize(env));
 101         bs1 &= ~Singleton(i);
 102     }
 103
 104     static UINT64 RemoveElem(Env env, UINT64 bs1, unsigned i)
 105     {
 106         return bs1 & ~Singleton(i);
 107     }
 108
 109     static void AddElemD(Env env, UINT64& bs1, unsigned i)
 110     {
 111         assert(i < BitSetTraits::GetSize(env));
 112         bs1 |= Singleton(i);
 113     }
 114
 115     static UINT64 AddElem(Env env, UINT64 bs1, unsigned i)
 116     {
 117         assert(i < BitSetTraits::GetSize(env));
 118         return bs1 | Singleton(i);
 119     }
 120
 121     static bool IsMember(Env env, const UINT64 bs1, unsigned i)
 122     {
 123         assert(i < BitSetTraits::GetSize(env));
 124         return (bs1 & Singleton(i)) != 0;
 125     }
 126
 127     static void IntersectionD(Env env, UINT64& bs1, UINT64 bs2)
 128     {
 129         bs1 &= bs2;
 130     }
 131
 132     static UINT64 Intersection(Env env, UINT64 bs1, UINT64 bs2)
 133     {
 134         return bs1 & bs2;
 135     }
 136
 137     static bool IsEmptyIntersection(Env env, UINT64 bs1, UINT64 bs2)
 138     {
 139         return (bs1 & bs2) == 0;
 140     }
 141
 142     static void LivenessD(Env env, UINT64& in, const UINT64 def, const UINT64 use, const UINT64 out)
 143     {
 144         in = use | (out & ~def);
 145     }
 146
 147     static bool IsSubset(Env env, UINT64 bs1, UINT64 bs2)
 148     {
 149         return ((bs1 & bs2) == bs1);
 150     }
 151
 152     static bool Equal(Env env, UINT64 bs1, UINT64 bs2)
 153     {
 154         return bs1 == bs2;
 155     }
 156
 157     static UINT64 MakeEmpty(Env env)
 158     {
 159         return 0;
 160     }
 161
 162     static UINT64 MakeFull(Env env)
 163     {
 164         unsigned sz = BitSetTraits::GetSize(env);
 165         if (sz == sizeof(UINT64) * 8)
 166         {
 167             return UINT64(-1);
 168         }
 169         else
 170         {
 171             return (UINT64(1) << sz) - 1;
 172         }
 173     }
 174
 175 #ifdef DEBUG
 176     static const char* ToString(Env env, UINT64 bs)
 177     {
 178         const int CharsForUINT64 = sizeof(UINT64) * 2;
 179         char*     res            = nullptr;
 180         const int AllocSize      = CharsForUINT64 + 4;
 181         res                      = (char*)BitSetTraits::DebugAlloc(env, AllocSize);
 182         UINT64   bits            = bs;
 183         unsigned remaining       = AllocSize;
 184         char*    ptr             = res;
 185         for (unsigned bytesDone = 0; bytesDone < sizeof(UINT64); bytesDone += sizeof(unsigned))
 186         {
 187             unsigned bits0 = (unsigned)bits;
 188             sprintf_s(ptr, remaining, "%08X", bits0);
 189             ptr += 8;
 190             remaining -= 8;
 191             bytesDone += 4;
 192             assert(sizeof(unsigned) == 4);
 193             // Doing this twice by 16, rather than once by 32, avoids warnings when size_t == unsigned.
 194             bits = bits >> 16;
 195             bits = bits >> 16;
 196         }
 197         return res;
 198     }
 199 #endif
 200
 201     static UINT64 UninitVal()
 202     {
 203         return 0;
 204     }
 205
 206     static bool MayBeUninit(UINT64 bs)
 207     {
 208         return bs == UninitVal();
 209     }
 210
 211     class Iter
 212     {
 213         UINT64 m_bits;
 214
 215         // The number of bits that have already been iterated over (set or clear).
 216         unsigned m_bitNum;
 217
 218     public:
 219         Iter(Env env, const UINT64& bits) : m_bits(bits), m_bitNum(0)
 220         {
 221         }
 222
 223         bool NextElem(unsigned* pElem)
 224         {
 225             // TODO-Throughtput: use BitScanForward64() intrinsic (see short/long implementation).
 226             if (m_bits)
 227             {
 228                 unsigned bitNum = m_bitNum;
 229                 while ((m_bits & 0x1) == 0)
 230                 {
 231                     bitNum++;
 232                     m_bits >>= 1;
 233                 }
 234                 *pElem   = bitNum;
 235                 m_bitNum = bitNum + 1;
 236                 m_bits >>= 1;
 237                 return true;
 238             }
 239             else
 240             {
 241                 return false;
 242             }
 243         }
 244     };
 245
 246     typedef const UINT64 ValArgType;
 247     typedef UINT64       RetValType;
 248 };
 249
 250 #endif // bitSetAsUint64_DEFINED