src/jit/bitsetasuint64inclass.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 bitSetAsUint64InClass_DEFINED
   6 #define bitSetAsUint64InClass_DEFINED 1
   7
   8 #include "bitset.h"
   9 #include "bitsetasuint64.h"
  10 #include "stdmacros.h"
  11
  12 template <typename Env, typename BitSetTraits>
  13 class BitSetUint64ValueRetType;
  14
  15 template <typename Env, typename BitSetTraits>
  16 class BitSetUint64Iter;
  17
  18 template <typename Env, typename BitSetTraits>
  19 class BitSetUint64
  20 {
  21 public:
  22     typedef BitSetUint64<Env, BitSetTraits> Rep;
  23
  24 private:
  25     friend class BitSetOps</*BitSetType*/ BitSetUint64<Env, BitSetTraits>,
  26                            /*Brand*/ BSUInt64Class,
  27                            /*Env*/ Env,
  28                            /*BitSetTraits*/ BitSetTraits>;
  29
  30     friend class BitSetUint64ValueRetType<Env, BitSetTraits>;
  31
  32     UINT64 m_bits;
  33
  34 #ifdef DEBUG
  35     unsigned m_epoch;
  36 #endif
  37
  38     typedef BitSetOps<UINT64, BSUInt64, Env, BitSetTraits> Uint64BitSetOps;
  39
  40     void CheckEpoch(Env env) const
  41     {
  42 #ifdef DEBUG
  43         assert(m_epoch == BitSetTraits::GetEpoch(env));
  44 #endif
  45     }
  46
  47     bool operator==(const BitSetUint64& bs) const
  48     {
  49         return m_bits == bs.m_bits
  50 #ifdef DEBUG
  51                && m_epoch == bs.m_epoch
  52 #endif
  53             ;
  54     }
  55
  56 public:
  57     BitSetUint64& operator=(const BitSetUint64& bs)
  58     {
  59         m_bits = bs.m_bits;
  60 #ifdef DEBUG
  61         m_epoch = bs.m_epoch;
  62 #endif // DEBUG
  63         return (*this);
  64     }
  65
  66     BitSetUint64(const BitSetUint64& bs)
  67         : m_bits(bs.m_bits)
  68 #ifdef DEBUG
  69         , m_epoch(bs.m_epoch)
  70 #endif
  71     {
  72     }
  73
  74 private:
  75     // Return the number of bits set in the BitSet.
  76     inline unsigned Count(Env env) const
  77     {
  78         CheckEpoch(env);
  79         return Uint64BitSetOps::Count(env, m_bits);
  80     }
  81
  82     inline void DiffD(Env env, const BitSetUint64& bs2)
  83     {
  84         CheckEpoch(env);
  85         bs2.CheckEpoch(env);
  86         Uint64BitSetOps::DiffD(env, m_bits, bs2.m_bits);
  87     }
  88
  89     inline BitSetUint64 Diff(Env env, const BitSetUint64& bs2) const
  90     {
  91         CheckEpoch(env);
  92         bs2.CheckEpoch(env);
  93         BitSetUint64 res(*this);
  94         Uint64BitSetOps::DiffD(env, res.m_bits, bs2.m_bits);
  95         return res;
  96     }
  97
  98     inline void RemoveElemD(Env env, unsigned i)
  99     {
 100         CheckEpoch(env);
 101         Uint64BitSetOps::RemoveElemD(env, m_bits, i);
 102     }
 103
 104     inline BitSetUint64 RemoveElem(Env env, unsigned i) const
 105     {
 106         CheckEpoch(env);
 107         BitSetUint64 res(*this);
 108         Uint64BitSetOps::RemoveElemD(env, res.m_bits, i);
 109         return res;
 110     }
 111
 112     inline void AddElemD(Env env, unsigned i)
 113     {
 114         CheckEpoch(env);
 115         Uint64BitSetOps::AddElemD(env, m_bits, i);
 116     }
 117
 118     inline BitSetUint64 AddElem(Env env, unsigned i) const
 119     {
 120         CheckEpoch(env);
 121         BitSetUint64 res(*this);
 122         Uint64BitSetOps::AddElemD(env, res.m_bits, i);
 123         return res;
 124     }
 125
 126     inline bool IsMember(Env env, unsigned i) const
 127     {
 128         CheckEpoch(env);
 129         return Uint64BitSetOps::IsMember(env, m_bits, i);
 130     }
 131
 132     inline void IntersectionD(Env env, const BitSetUint64& bs2)
 133     {
 134         CheckEpoch(env);
 135         bs2.CheckEpoch(env);
 136         m_bits = m_bits & bs2.m_bits;
 137     }
 138
 139     inline BitSetUint64 Intersection(Env env, const BitSetUint64& bs2) const
 140     {
 141         CheckEpoch(env);
 142         bs2.CheckEpoch(env);
 143         BitSetUint64 res(*this);
 144         Uint64BitSetOps::IntersectionD(env, res.m_bits, bs2.m_bits);
 145         return res;
 146     }
 147
 148     inline bool IsEmptyUnion(Env env, const BitSetUint64& bs2) const
 149     {
 150         CheckEpoch(env);
 151         bs2.CheckEpoch(env);
 152         return Uint64BitSetOps::IsEmptyUnion(env, m_bits, bs2.m_bits);
 153     }
 154
 155     inline void UnionD(Env env, const BitSetUint64& bs2)
 156     {
 157         CheckEpoch(env);
 158         bs2.CheckEpoch(env);
 159         Uint64BitSetOps::UnionD(env, m_bits, bs2.m_bits);
 160     }
 161
 162     inline BitSetUint64 Union(Env env, const BitSetUint64& bs2) const
 163     {
 164         CheckEpoch(env);
 165         bs2.CheckEpoch(env);
 166         BitSetUint64 res(*this);
 167         Uint64BitSetOps::UnionD(env, res.m_bits, bs2.m_bits);
 168         return res;
 169     }
 170
 171     inline void ClearD(Env env)
 172     {
 173         assert(m_epoch == BitSetTraits::GetEpoch(env));
 174         Uint64BitSetOps::ClearD(env, m_bits);
 175     }
 176
 177     inline bool IsEmpty(Env env) const
 178     {
 179         CheckEpoch(env);
 180         return Uint64BitSetOps::IsEmpty(env, m_bits);
 181     }
 182
 183     inline void LivenessD(Env env, const BitSetUint64& def, const BitSetUint64& use, const BitSetUint64& out)
 184     {
 185         CheckEpoch(env);
 186         def.CheckEpoch(env);
 187         use.CheckEpoch(env);
 188         out.CheckEpoch(env);
 189         return Uint64BitSetOps::LivenessD(env, m_bits, def.m_bits, use.m_bits, out.m_bits);
 190     }
 191
 192     inline bool IsSubset(Env env, const BitSetUint64& bs2) const
 193     {
 194         CheckEpoch(env);
 195         bs2.CheckEpoch(env);
 196         return Uint64BitSetOps::IsSubset(env, m_bits, bs2.m_bits);
 197     }
 198
 199     inline bool IsEmptyIntersection(Env env, const BitSetUint64& bs2) const
 200     {
 201         CheckEpoch(env);
 202         bs2.CheckEpoch(env);
 203         return Uint64BitSetOps::IsEmptyIntersection(env, m_bits, bs2.m_bits);
 204     }
 205
 206     inline bool Equal(Env env, const BitSetUint64& bs2) const
 207     {
 208         CheckEpoch(env);
 209         bs2.CheckEpoch(env);
 210         return Uint64BitSetOps::Equal(env, m_bits, bs2.m_bits);
 211     }
 212
 213     const char* ToString(Env env) const
 214     {
 215         return Uint64BitSetOps::ToString(env, m_bits);
 216     }
 217
 218 public:
 219     // Uninint
 220     BitSetUint64()
 221         : m_bits(0)
 222 #ifdef DEBUG
 223         , m_epoch(UINT32_MAX) // Undefined.
 224 #endif
 225     {
 226     }
 227
 228     BitSetUint64(Env env, bool full = false)
 229         : m_bits(0)
 230 #ifdef DEBUG
 231         , m_epoch(BitSetTraits::GetEpoch(env))
 232 #endif
 233     {
 234         if (full)
 235         {
 236             m_bits = Uint64BitSetOps::MakeFull(env);
 237         }
 238     }
 239
 240     inline BitSetUint64(const BitSetUint64ValueRetType<Env, BitSetTraits>& rt);
 241
 242     BitSetUint64(Env env, unsigned bitNum)
 243         : m_bits(Uint64BitSetOps::MakeSingleton(env, bitNum))
 244 #ifdef DEBUG
 245         , m_epoch(BitSetTraits::GetEpoch(env))
 246 #endif
 247     {
 248         assert(bitNum < BitSetTraits::GetSize(env));
 249     }
 250 };
 251
 252 template <typename Env, typename BitSetTraits>
 253 class BitSetUint64ValueRetType
 254 {
 255     friend class BitSetUint64<Env, BitSetTraits>;
 256
 257     BitSetUint64<Env, BitSetTraits> m_bs;
 258
 259 public:
 260     BitSetUint64ValueRetType(const BitSetUint64<Env, BitSetTraits>& bs) : m_bs(bs)
 261     {
 262     }
 263 };
 264
 265 template <typename Env, typename BitSetTraits>
 266 BitSetUint64<Env, BitSetTraits>::BitSetUint64(const BitSetUint64ValueRetType<Env, BitSetTraits>& rt)
 267     : m_bits(rt.m_bs.m_bits)
 268 #ifdef DEBUG
 269     , m_epoch(rt.m_bs.m_epoch)
 270 #endif
 271 {
 272 }
 273
 274 template <typename Env, typename BitSetTraits>
 275 class BitSetOps</*BitSetType*/ BitSetUint64<Env, BitSetTraits>,
 276                 /*Brand*/ BSUInt64Class,
 277                 /*Env*/ Env,
 278                 /*BitSetTraits*/ BitSetTraits>
 279 {
 280     typedef BitSetUint64<Env, BitSetTraits>             BST;
 281     typedef const BitSetUint64<Env, BitSetTraits>&      BSTValArg;
 282     typedef BitSetUint64ValueRetType<Env, BitSetTraits> BSTRetVal;
 283
 284 public:
 285     static BSTRetVal UninitVal()
 286     {
 287         return BitSetUint64<Env, BitSetTraits>();
 288     }
 289
 290     static bool MayBeUninit(BSTValArg bs)
 291     {
 292         return bs == UninitVal();
 293     }
 294
 295     static void Assign(Env env, BST& lhs, BSTValArg rhs)
 296     {
 297         lhs = rhs;
 298     }
 299
 300     static void AssignNouninit(Env env, BST& lhs, BSTValArg rhs)
 301     {
 302         lhs = rhs;
 303     }
 304
 305     static void AssignAllowUninitRhs(Env env, BST& lhs, BSTValArg rhs)
 306     {
 307         lhs = rhs;
 308     }
 309
 310     static void AssignNoCopy(Env env, BST& lhs, BSTValArg rhs)
 311     {
 312         lhs = rhs;
 313     }
 314
 315     static void ClearD(Env env, BST& bs)
 316     {
 317         bs.ClearD(env);
 318     }
 319
 320     static BSTRetVal MakeSingleton(Env env, unsigned bitNum)
 321     {
 322         assert(bitNum < BitSetTraits::GetSize(env));
 323         return BST(env, bitNum);
 324     }
 325
 326     static BSTRetVal MakeCopy(Env env, BSTValArg bs)
 327     {
 328         return bs;
 329     }
 330
 331     static bool IsEmpty(Env env, BSTValArg bs)
 332     {
 333         return bs.IsEmpty(env);
 334     }
 335
 336     static unsigned Count(Env env, BSTValArg bs)
 337     {
 338         return bs.Count(env);
 339     }
 340
 341     static bool IsEmptyUnion(Env env, BSTValArg bs1, BSTValArg bs2)
 342     {
 343         return bs1.IsEmptyUnion(env, bs2);
 344     }
 345
 346     static void UnionD(Env env, BST& bs1, BSTValArg bs2)
 347     {
 348         bs1.UnionD(env, bs2);
 349     }
 350
 351     static BSTRetVal Union(Env env, BSTValArg bs1, BSTValArg bs2)
 352     {
 353         return bs1.Union(env, bs2);
 354     }
 355
 356     static void DiffD(Env env, BST& bs1, BSTValArg bs2)
 357     {
 358         bs1.DiffD(env, bs2);
 359     }
 360
 361     static BSTRetVal Diff(Env env, BSTValArg bs1, BSTValArg bs2)
 362     {
 363         return bs1.Diff(env, bs2);
 364     }
 365
 366     static void RemoveElemD(Env env, BST& bs1, unsigned i)
 367     {
 368         assert(i < BitSetTraits::GetSize(env));
 369         bs1.RemoveElemD(env, i);
 370     }
 371
 372     static BSTRetVal RemoveElem(Env env, BSTValArg bs1, unsigned i)
 373     {
 374         assert(i < BitSetTraits::GetSize(env));
 375         return bs1.RemoveElem(env, i);
 376     }
 377
 378     static void AddElemD(Env env, BST& bs1, unsigned i)
 379     {
 380         assert(i < BitSetTraits::GetSize(env));
 381         bs1.AddElemD(env, i);
 382     }
 383
 384     static BSTRetVal AddElem(Env env, BSTValArg bs1, unsigned i)
 385     {
 386         assert(i < BitSetTraits::GetSize(env));
 387         return bs1.AddElem(env, i);
 388     }
 389
 390     static bool IsMember(Env env, BSTValArg bs1, unsigned i)
 391     {
 392         assert(i < BitSetTraits::GetSize(env));
 393         return bs1.IsMember(env, i);
 394     }
 395
 396     static void IntersectionD(Env env, BST& bs1, BSTValArg bs2)
 397     {
 398         bs1.IntersectionD(env, bs2);
 399     }
 400
 401     static BSTRetVal Intersection(Env env, BSTValArg bs1, BSTValArg bs2)
 402     {
 403         return bs1.Intersection(env, bs2);
 404     }
 405
 406     static bool IsEmptyIntersection(Env env, BSTValArg bs1, BSTValArg bs2)
 407     {
 408         return bs1.IsEmptyIntersection(env, bs2);
 409     }
 410
 411     static void LivenessD(Env env, BST& in, BSTValArg def, BSTValArg use, BSTValArg out)
 412     {
 413         in.LivenessD(env, def, use, out);
 414     }
 415     static bool IsSubset(Env env, BSTValArg bs1, BSTValArg bs2)
 416     {
 417         return bs1.IsSubset(env, bs2);
 418     }
 419
 420     static bool Equal(Env env, BSTValArg bs1, BSTValArg bs2)
 421     {
 422         return bs1.Equal(env, bs2);
 423     }
 424
 425     static bool NotEqual(Env env, BSTValArg bs1, BSTValArg bs2)
 426     {
 427         return !bs1.Equal(env, bs2);
 428     }
 429
 430     static BSTRetVal MakeEmpty(Env env)
 431     {
 432         return BST(env);
 433     }
 434
 435     static BSTRetVal MakeFull(Env env)
 436     {
 437         return BST(env, /*full*/ true);
 438     }
 439
 440 #ifdef DEBUG
 441     static const char* ToString(Env env, BSTValArg bs)
 442     {
 443         return bs.ToString(env);
 444     }
 445 #endif
 446
 447     // You *can* clear a bit after it's been iterated.  But you shouldn't otherwise mutate the
 448     // bitset during bit iteration.
 449     class Iter
 450     {
 451         UINT64   m_bits;
 452         unsigned m_bitNum;
 453
 454     public:
 455         Iter(Env env, const BitSetUint64<Env, BitSetTraits>& bs) : m_bits(bs.m_bits), m_bitNum(0)
 456         {
 457         }
 458
 459         bool NextElem(unsigned* pElem)
 460         {
 461             static const unsigned UINT64_SIZE = 64;
 462
 463             if ((m_bits & 0x1) != 0)
 464             {
 465                 *pElem = m_bitNum;
 466                 m_bitNum++;
 467                 m_bits >>= 1;
 468                 return true;
 469             }
 470             else
 471             {
 472                 // Skip groups of 4 zeros -- an optimization for sparse bitsets.
 473                 while (m_bitNum < UINT64_SIZE && (m_bits & 0xf) == 0)
 474                 {
 475                     m_bitNum += 4;
 476                     m_bits >>= 4;
 477                 }
 478                 while (m_bitNum < UINT64_SIZE && (m_bits & 0x1) == 0)
 479                 {
 480                     m_bitNum += 1;
 481                     m_bits >>= 1;
 482                 }
 483                 if (m_bitNum < UINT64_SIZE)
 484                 {
 485                     *pElem = m_bitNum;
 486                     m_bitNum++;
 487                     m_bits >>= 1;
 488                     return true;
 489                 }
 490                 else
 491                 {
 492                     return false;
 493                 }
 494             }
 495         }
 496     };
 497
 498     typedef const BitSetUint64<Env, BitSetTraits>&      ValArgType;
 499     typedef BitSetUint64ValueRetType<Env, BitSetTraits> RetValType;
 500 };
 501 #endif // bitSetAsUint64InClass_DEFINED