src/jit/bitsetasshortlong.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 // A set of integers in the range [0..N], for some N defined by the "Env" (via "BitSetTraits").
   6 //
   7 // Represented as a pointer-sized item.  If N bits can fit in this item, the representation is "direct"; otherwise,
   8 // the item is a pointer to an array of K size_t's, where K is the number of size_t's necessary to hold N bits.
   9
  10 #ifndef bitSetAsShortLong_DEFINED
  11 #define bitSetAsShortLong_DEFINED 1
  12
  13 #include "bitset.h"
  14 #include "compilerbitsettraits.h"
  15
  16 typedef size_t* BitSetShortLongRep;
  17
  18 template <typename Env, typename BitSetTraits>
  19 class BitSetOps</*BitSetType*/ BitSetShortLongRep,
  20                 /*Brand*/ BSShortLong,
  21                 /*Env*/ Env,
  22                 /*BitSetTraits*/ BitSetTraits>
  23 {
  24 public:
  25     typedef BitSetShortLongRep Rep;
  26
  27 private:
  28     static const unsigned BitsInSizeT = sizeof(size_t) * BitSetSupport::BitsInByte;
  29
  30     inline static bool IsShort(Env env)
  31     {
  32         return BitSetTraits::GetArrSize(env, sizeof(size_t)) <= 1;
  33     }
  34
  35     // The operations on the "long" (pointer-to-array-of-size_t) versions of the representation.
  36     static void AssignLong(Env env, BitSetShortLongRep& lhs, BitSetShortLongRep rhs);
  37     static BitSetShortLongRep MakeSingletonLong(Env env, unsigned bitNum);
  38     static BitSetShortLongRep MakeCopyLong(Env env, BitSetShortLongRep bs);
  39     static bool IsEmptyLong(Env env, BitSetShortLongRep bs);
  40     static unsigned CountLong(Env env, BitSetShortLongRep bs);
  41     static bool IsEmptyUnionLong(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2);
  42     static void UnionDLong(Env env, BitSetShortLongRep& bs1, BitSetShortLongRep bs2);
  43     static void DiffDLong(Env env, BitSetShortLongRep& bs1, BitSetShortLongRep bs2);
  44     static void AddElemDLong(Env env, BitSetShortLongRep& bs, unsigned i);
  45     static void RemoveElemDLong(Env env, BitSetShortLongRep& bs, unsigned i);
  46     static void ClearDLong(Env env, BitSetShortLongRep& bs);
  47     static BitSetShortLongRep MakeUninitArrayBits(Env env);
  48     static BitSetShortLongRep MakeEmptyArrayBits(Env env);
  49     static BitSetShortLongRep MakeFullArrayBits(Env env);
  50     static bool IsMemberLong(Env env, BitSetShortLongRep bs, unsigned i);
  51     static bool EqualLong(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2);
  52     static bool IsSubsetLong(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2);
  53     static bool IsEmptyIntersectionLong(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2);
  54     static void IntersectionDLong(Env env, BitSetShortLongRep& bs1, BitSetShortLongRep bs2);
  55     static void DataFlowDLong(Env                      env,
  56                               BitSetShortLongRep&      out,
  57                               const BitSetShortLongRep gen,
  58                               const BitSetShortLongRep in);
  59     static void LivenessDLong(Env                      env,
  60                               BitSetShortLongRep&      in,
  61                               const BitSetShortLongRep def,
  62                               const BitSetShortLongRep use,
  63                               const BitSetShortLongRep out);
  64 #ifdef DEBUG
  65     static const char* ToStringLong(Env env, BitSetShortLongRep bs);
  66 #endif
  67
  68 public:
  69     inline static BitSetShortLongRep UninitVal()
  70     {
  71         return nullptr;
  72     }
  73
  74     static bool MayBeUninit(BitSetShortLongRep bs)
  75     {
  76         return bs == UninitVal();
  77     }
  78
  79     static void Assign(Env env, BitSetShortLongRep& lhs, BitSetShortLongRep rhs)
  80     {
  81         // We can't assert that rhs != UninitVal in the Short case, because in that
  82         // case it's a legal value.
  83         if (IsShort(env))
  84         {
  85             // Both are short.
  86             lhs = rhs;
  87         }
  88         else if (lhs == UninitVal())
  89         {
  90             assert(rhs != UninitVal());
  91             lhs = MakeCopy(env, rhs);
  92         }
  93         else
  94         {
  95             AssignLong(env, lhs, rhs);
  96         }
  97     }
  98
  99     static void AssignAllowUninitRhs(Env env, BitSetShortLongRep& lhs, BitSetShortLongRep rhs)
 100     {
 101         if (IsShort(env))
 102         {
 103             // Both are short.
 104             lhs = rhs;
 105         }
 106         else if (rhs == UninitVal())
 107         {
 108             lhs = rhs;
 109         }
 110         else if (lhs == UninitVal())
 111         {
 112             lhs = MakeCopy(env, rhs);
 113         }
 114         else
 115         {
 116             AssignLong(env, lhs, rhs);
 117         }
 118     }
 119
 120     static void AssignNoCopy(Env env, BitSetShortLongRep& lhs, BitSetShortLongRep rhs)
 121     {
 122         lhs = rhs;
 123     }
 124
 125     static void ClearD(Env env, BitSetShortLongRep& bs)
 126     {
 127         if (IsShort(env))
 128         {
 129             bs = (BitSetShortLongRep) nullptr;
 130         }
 131         else
 132         {
 133             assert(bs != UninitVal());
 134             ClearDLong(env, bs);
 135         }
 136     }
 137
 138     static BitSetShortLongRep MakeSingleton(Env env, unsigned bitNum)
 139     {
 140         assert(bitNum < BitSetTraits::GetSize(env));
 141         if (IsShort(env))
 142         {
 143             return BitSetShortLongRep(((size_t)1) << bitNum);
 144         }
 145         else
 146         {
 147             return MakeSingletonLong(env, bitNum);
 148         }
 149     }
 150
 151     static BitSetShortLongRep MakeCopy(Env env, BitSetShortLongRep bs)
 152     {
 153         if (IsShort(env))
 154         {
 155             return bs;
 156         }
 157         else
 158         {
 159             return MakeCopyLong(env, bs);
 160         }
 161     }
 162
 163     static bool IsEmpty(Env env, BitSetShortLongRep bs)
 164     {
 165         if (IsShort(env))
 166         {
 167             return bs == nullptr;
 168         }
 169         else
 170         {
 171             assert(bs != UninitVal());
 172             return IsEmptyLong(env, bs);
 173         }
 174     }
 175
 176     static unsigned Count(Env env, BitSetShortLongRep bs)
 177     {
 178         if (IsShort(env))
 179         {
 180             return BitSetSupport::CountBitsInIntegral(size_t(bs));
 181         }
 182         else
 183         {
 184             assert(bs != UninitVal());
 185             return CountLong(env, bs);
 186         }
 187     }
 188
 189     static bool IsEmptyUnion(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2)
 190     {
 191         if (IsShort(env))
 192         {
 193             return (((size_t)bs1) | ((size_t)bs2)) == 0;
 194         }
 195         else
 196         {
 197             return IsEmptyUnionLong(env, bs1, bs2);
 198         }
 199     }
 200
 201     static void UnionD(Env env, BitSetShortLongRep& bs1, BitSetShortLongRep bs2)
 202     {
 203         if (IsShort(env))
 204         {
 205             bs1 = (BitSetShortLongRep)(((size_t)bs1) | ((size_t)bs2));
 206         }
 207         else
 208         {
 209             UnionDLong(env, bs1, bs2);
 210         }
 211     }
 212     static BitSetShortLongRep Union(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2)
 213     {
 214         BitSetShortLongRep res = MakeCopy(env, bs1);
 215         UnionD(env, res, bs2);
 216         return res;
 217     }
 218
 219     static void DiffD(Env env, BitSetShortLongRep& bs1, BitSetShortLongRep bs2)
 220     {
 221         if (IsShort(env))
 222         {
 223             bs1 = (BitSetShortLongRep)(((size_t)bs1) & (~(size_t)bs2));
 224         }
 225         else
 226         {
 227             DiffDLong(env, bs1, bs2);
 228         }
 229     }
 230     static BitSetShortLongRep Diff(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2)
 231     {
 232         BitSetShortLongRep res = MakeCopy(env, bs1);
 233         DiffD(env, res, bs2);
 234         return res;
 235     }
 236
 237     static void RemoveElemD(Env env, BitSetShortLongRep& bs, unsigned i)
 238     {
 239         assert(i < BitSetTraits::GetSize(env));
 240         if (IsShort(env))
 241         {
 242             size_t mask = ((size_t)1) << i;
 243             mask        = ~mask;
 244             bs          = (BitSetShortLongRep)(((size_t)bs) & mask);
 245         }
 246         else
 247         {
 248             assert(bs != UninitVal());
 249             RemoveElemDLong(env, bs, i);
 250         }
 251     }
 252     static BitSetShortLongRep RemoveElem(Env env, BitSetShortLongRep bs, unsigned i)
 253     {
 254         BitSetShortLongRep res = MakeCopy(env, bs);
 255         RemoveElemD(env, res, i);
 256         return res;
 257     }
 258
 259     static void AddElemD(Env env, BitSetShortLongRep& bs, unsigned i)
 260     {
 261         assert(i < BitSetTraits::GetSize(env));
 262         if (IsShort(env))
 263         {
 264             size_t mask = ((size_t)1) << i;
 265             bs          = (BitSetShortLongRep)(((size_t)bs) | mask);
 266         }
 267         else
 268         {
 269             AddElemDLong(env, bs, i);
 270         }
 271     }
 272     static BitSetShortLongRep AddElem(Env env, BitSetShortLongRep bs, unsigned i)
 273     {
 274         BitSetShortLongRep res = MakeCopy(env, bs);
 275         AddElemD(env, res, i);
 276         return res;
 277     }
 278
 279     static bool IsMember(Env env, const BitSetShortLongRep bs, unsigned i)
 280     {
 281         assert(i < BitSetTraits::GetSize(env));
 282         if (IsShort(env))
 283         {
 284             size_t mask = ((size_t)1) << i;
 285             return (((size_t)bs) & mask) != 0;
 286         }
 287         else
 288         {
 289             assert(bs != UninitVal());
 290             return IsMemberLong(env, bs, i);
 291         }
 292     }
 293
 294     static void IntersectionD(Env env, BitSetShortLongRep& bs1, BitSetShortLongRep bs2)
 295     {
 296         if (IsShort(env))
 297         {
 298             (size_t&)bs1 &= (size_t)bs2;
 299         }
 300         else
 301         {
 302             IntersectionDLong(env, bs1, bs2);
 303         }
 304     }
 305
 306     static BitSetShortLongRep Intersection(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2)
 307     {
 308         BitSetShortLongRep res = MakeCopy(env, bs1);
 309         IntersectionD(env, res, bs2);
 310         return res;
 311     }
 312     static bool IsEmptyIntersection(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2)
 313     {
 314         if (IsShort(env))
 315         {
 316             return (((size_t)bs1) & ((size_t)bs2)) == 0;
 317         }
 318         else
 319         {
 320             return IsEmptyIntersectionLong(env, bs1, bs2);
 321         }
 322     }
 323
 324     static void DataFlowD(Env env, BitSetShortLongRep& out, const BitSetShortLongRep gen, const BitSetShortLongRep in)
 325     {
 326         if (IsShort(env))
 327         {
 328             (size_t&)out = (size_t)out & ((size_t)gen | (size_t)in);
 329         }
 330         else
 331         {
 332             DataFlowDLong(env, out, gen, in);
 333         }
 334     }
 335
 336     static void LivenessD(Env                      env,
 337                           BitSetShortLongRep&      in,
 338                           const BitSetShortLongRep def,
 339                           const BitSetShortLongRep use,
 340                           const BitSetShortLongRep out)
 341     {
 342         if (IsShort(env))
 343         {
 344             (size_t&)in = (size_t)use | ((size_t)out & ~(size_t)def);
 345         }
 346         else
 347         {
 348             LivenessDLong(env, in, def, use, out);
 349         }
 350     }
 351
 352     static bool IsSubset(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2)
 353     {
 354         if (IsShort(env))
 355         {
 356             size_t u1 = (size_t)bs1;
 357             size_t u2 = (size_t)bs2;
 358             return (u1 & u2) == u1;
 359         }
 360         else
 361         {
 362             return IsSubsetLong(env, bs1, bs2);
 363         }
 364     }
 365
 366     static bool Equal(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2)
 367     {
 368         if (IsShort(env))
 369         {
 370             return (size_t)bs1 == (size_t)bs2;
 371         }
 372         else
 373         {
 374             return EqualLong(env, bs1, bs2);
 375         }
 376     }
 377
 378 #ifdef DEBUG
 379     // Returns a string valid until the allocator releases the memory.
 380     static const char* ToString(Env env, BitSetShortLongRep bs)
 381     {
 382         if (IsShort(env))
 383         {
 384             assert(sizeof(BitSetShortLongRep) == sizeof(size_t));
 385             const int CharsForSizeT  = sizeof(size_t) * 2;
 386             char*     res            = nullptr;
 387             const int ShortAllocSize = CharsForSizeT + 4;
 388             res                      = (char*)BitSetTraits::DebugAlloc(env, ShortAllocSize);
 389             size_t   bits            = (size_t)bs;
 390             unsigned remaining       = ShortAllocSize;
 391             char*    ptr             = res;
 392             if (sizeof(size_t) == sizeof(int64_t))
 393             {
 394                 sprintf_s(ptr, remaining, "%016llX", bits);
 395             }
 396             else
 397             {
 398                 assert(sizeof(size_t) == sizeof(int));
 399                 sprintf_s(ptr, remaining, "%08X", bits);
 400             }
 401             return res;
 402         }
 403         else
 404         {
 405             return ToStringLong(env, bs);
 406         }
 407     }
 408 #endif
 409
 410     static BitSetShortLongRep MakeEmpty(Env env)
 411     {
 412         if (IsShort(env))
 413         {
 414             return nullptr;
 415         }
 416         else
 417         {
 418             return MakeEmptyArrayBits(env);
 419         }
 420     }
 421
 422     static BitSetShortLongRep MakeFull(Env env)
 423     {
 424         if (IsShort(env))
 425         {
 426             // Can't just shift by numBits+1, since that might be 32 (and (1 << 32( == 1, for an unsigned).
 427             unsigned numBits = BitSetTraits::GetSize(env);
 428             if (numBits == BitsInSizeT)
 429             {
 430                 // Can't use the implementation below to get all 1's...
 431                 return BitSetShortLongRep(size_t(-1));
 432             }
 433             else
 434             {
 435                 return BitSetShortLongRep((size_t(1) << numBits) - 1);
 436             }
 437         }
 438         else
 439         {
 440             return MakeFullArrayBits(env);
 441         }
 442     }
 443
 444     class Iter
 445     {
 446         // The BitSet that we're iterating over. This is updated to point at the current
 447         // size_t set of bits.
 448         BitSetShortLongRep m_bs;
 449
 450         // The end of the iteration.
 451         BitSetShortLongRep m_bsEnd;
 452
 453         // The remaining bits to be iterated over in the current size_t set of bits.
 454         // In the "short" case, these are all the remaining bits.
 455         // In the "long" case, these are remaining bits in the current element;
 456         // these and the bits in the remaining elements comprise the remaining bits.
 457         size_t m_bits;
 458
 459         // The number of bits that have already been iterated over (set or clear). If you
 460         // add this to the bit number of the next bit in "m_bits", you get the proper bit number of that
 461         // bit in "m_bs". This is only updated when we increment m_bs.
 462         unsigned m_bitNum;
 463
 464     public:
 465         Iter(Env env, const BitSetShortLongRep& bs) : m_bs(bs), m_bitNum(0)
 466         {
 467             if (BitSetOps::IsShort(env))
 468             {
 469                 m_bits = (size_t)bs;
 470
 471                 // Set the iteration end condition, valid even though this is not a pointer in the short case.
 472                 m_bsEnd = bs + 1;
 473             }
 474             else
 475             {
 476                 assert(bs != BitSetOps::UninitVal());
 477                 m_bits = bs[0];
 478
 479                 unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
 480                 m_bsEnd      = bs + len;
 481             }
 482         }
 483
 484         bool NextElem(unsigned* pElem)
 485         {
 486 #if BITSET_TRACK_OPCOUNTS
 487             BitSetStaticsImpl::RecordOp(BitSetStaticsImpl::BSOP_NextBit);
 488 #endif
 489             for (;;)
 490             {
 491                 DWORD nextBit;
 492                 BOOL  hasBit;
 493 #ifdef _HOST_64BIT_
 494                 static_assert_no_msg(sizeof(size_t) == 8);
 495                 hasBit = BitScanForward64(&nextBit, m_bits);
 496 #else
 497                 static_assert_no_msg(sizeof(size_t) == 4);
 498                 hasBit = BitScanForward(&nextBit, m_bits);
 499 #endif
 500
 501                 // If there's a bit, doesn't matter if we're short or long.
 502                 if (hasBit)
 503                 {
 504                     *pElem = m_bitNum + nextBit;
 505                     m_bits &= ~(((size_t)1) << nextBit); // clear bit we just found so we don't find it again
 506                     return true;
 507                 }
 508                 else
 509                 {
 510                     // Go to the next size_t bit element. For short bitsets, this will hit the end condition
 511                     // and exit.
 512                     ++m_bs;
 513                     if (m_bs == m_bsEnd)
 514                     {
 515                         return false;
 516                     }
 517
 518                     // If we get here, it's not a short type, so get the next size_t element.
 519                     m_bitNum += sizeof(size_t) * BitSetSupport::BitsInByte;
 520                     m_bits = *m_bs;
 521                 }
 522             }
 523         }
 524     };
 525
 526     typedef const BitSetShortLongRep& ValArgType;
 527     typedef BitSetShortLongRep        RetValType;
 528 };
 529
 530 template <typename Env, typename BitSetTraits>
 531 void BitSetOps</*BitSetType*/ BitSetShortLongRep,
 532                /*Brand*/ BSShortLong,
 533                /*Env*/ Env,
 534                /*BitSetTraits*/ BitSetTraits>::AssignLong(Env env, BitSetShortLongRep& lhs, BitSetShortLongRep rhs)
 535 {
 536     assert(!IsShort(env));
 537     unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
 538     for (unsigned i = 0; i < len; i++)
 539     {
 540         lhs[i] = rhs[i];
 541     }
 542 }
 543
 544 template <typename Env, typename BitSetTraits>
 545 BitSetShortLongRep BitSetOps</*BitSetType*/ BitSetShortLongRep,
 546                              /*Brand*/ BSShortLong,
 547                              /*Env*/ Env,
 548                              /*BitSetTraits*/ BitSetTraits>::MakeSingletonLong(Env env, unsigned bitNum)
 549 {
 550     assert(!IsShort(env));
 551     BitSetShortLongRep res   = MakeEmptyArrayBits(env);
 552     unsigned           index = bitNum / BitsInSizeT;
 553     res[index]               = ((size_t)1) << (bitNum % BitsInSizeT);
 554     return res;
 555 }
 556
 557 template <typename Env, typename BitSetTraits>
 558 BitSetShortLongRep BitSetOps</*BitSetType*/ BitSetShortLongRep,
 559                              /*Brand*/ BSShortLong,
 560                              /*Env*/ Env,
 561                              /*BitSetTraits*/ BitSetTraits>::MakeCopyLong(Env env, BitSetShortLongRep bs)
 562 {
 563     assert(!IsShort(env));
 564     BitSetShortLongRep res = MakeUninitArrayBits(env);
 565     unsigned           len = BitSetTraits::GetArrSize(env, sizeof(size_t));
 566     for (unsigned i = 0; i < len; i++)
 567     {
 568         res[i] = bs[i];
 569     }
 570     return res;
 571 }
 572
 573 template <typename Env, typename BitSetTraits>
 574 bool BitSetOps</*BitSetType*/ BitSetShortLongRep,
 575                /*Brand*/ BSShortLong,
 576                /*Env*/ Env,
 577                /*BitSetTraits*/ BitSetTraits>::IsEmptyLong(Env env, BitSetShortLongRep bs)
 578 {
 579     assert(!IsShort(env));
 580     unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
 581     for (unsigned i = 0; i < len; i++)
 582     {
 583         if (bs[i] != 0)
 584         {
 585             return false;
 586         }
 587     }
 588     return true;
 589 }
 590
 591 template <typename Env, typename BitSetTraits>
 592 unsigned BitSetOps</*BitSetType*/ BitSetShortLongRep,
 593                    /*Brand*/ BSShortLong,
 594                    /*Env*/ Env,
 595                    /*BitSetTraits*/ BitSetTraits>::CountLong(Env env, BitSetShortLongRep bs)
 596 {
 597     assert(!IsShort(env));
 598     unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
 599     unsigned res = 0;
 600     for (unsigned i = 0; i < len; i++)
 601     {
 602         res += BitSetSupport::CountBitsInIntegral(bs[i]);
 603     }
 604     return res;
 605 }
 606
 607 template <typename Env, typename BitSetTraits>
 608 void BitSetOps</*BitSetType*/ BitSetShortLongRep,
 609                /*Brand*/ BSShortLong,
 610                /*Env*/ Env,
 611                /*BitSetTraits*/ BitSetTraits>::UnionDLong(Env env, BitSetShortLongRep& bs1, BitSetShortLongRep bs2)
 612 {
 613     assert(!IsShort(env));
 614     unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
 615     for (unsigned i = 0; i < len; i++)
 616     {
 617         bs1[i] |= bs2[i];
 618     }
 619 }
 620
 621 template <typename Env, typename BitSetTraits>
 622 void BitSetOps</*BitSetType*/ BitSetShortLongRep,
 623                /*Brand*/ BSShortLong,
 624                /*Env*/ Env,
 625                /*BitSetTraits*/ BitSetTraits>::DiffDLong(Env env, BitSetShortLongRep& bs1, BitSetShortLongRep bs2)
 626 {
 627     assert(!IsShort(env));
 628     unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
 629     for (unsigned i = 0; i < len; i++)
 630     {
 631         bs1[i] &= ~bs2[i];
 632     }
 633 }
 634
 635 template <typename Env, typename BitSetTraits>
 636 void BitSetOps</*BitSetType*/ BitSetShortLongRep,
 637                /*Brand*/ BSShortLong,
 638                /*Env*/ Env,
 639                /*BitSetTraits*/ BitSetTraits>::AddElemDLong(Env env, BitSetShortLongRep& bs, unsigned i)
 640 {
 641     assert(!IsShort(env));
 642     unsigned index = i / BitsInSizeT;
 643     size_t   mask  = ((size_t)1) << (i % BitsInSizeT);
 644     bs[index] |= mask;
 645 }
 646
 647 template <typename Env, typename BitSetTraits>
 648 void BitSetOps</*BitSetType*/ BitSetShortLongRep,
 649                /*Brand*/ BSShortLong,
 650                /*Env*/ Env,
 651                /*BitSetTraits*/ BitSetTraits>::RemoveElemDLong(Env env, BitSetShortLongRep& bs, unsigned i)
 652 {
 653     assert(!IsShort(env));
 654     unsigned index = i / BitsInSizeT;
 655     size_t   mask  = ((size_t)1) << (i % BitsInSizeT);
 656     mask           = ~mask;
 657     bs[index] &= mask;
 658 }
 659
 660 template <typename Env, typename BitSetTraits>
 661 void BitSetOps</*BitSetType*/ BitSetShortLongRep,
 662                /*Brand*/ BSShortLong,
 663                /*Env*/ Env,
 664                /*BitSetTraits*/ BitSetTraits>::ClearDLong(Env env, BitSetShortLongRep& bs)
 665 {
 666     assert(!IsShort(env));
 667     unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
 668     for (unsigned i = 0; i < len; i++)
 669     {
 670         bs[i] = 0;
 671     }
 672 }
 673
 674 template <typename Env, typename BitSetTraits>
 675 BitSetShortLongRep BitSetOps</*BitSetType*/ BitSetShortLongRep,
 676                              /*Brand*/ BSShortLong,
 677                              /*Env*/ Env,
 678                              /*BitSetTraits*/ BitSetTraits>::MakeUninitArrayBits(Env env)
 679 {
 680     assert(!IsShort(env));
 681     unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
 682     assert(len > 1); // Or else would not require an array.
 683     return (BitSetShortLongRep)(BitSetTraits::Alloc(env, len * sizeof(size_t)));
 684 }
 685
 686 template <typename Env, typename BitSetTraits>
 687 BitSetShortLongRep BitSetOps</*BitSetType*/ BitSetShortLongRep,
 688                              /*Brand*/ BSShortLong,
 689                              /*Env*/ Env,
 690                              /*BitSetTraits*/ BitSetTraits>::MakeEmptyArrayBits(Env env)
 691 {
 692     assert(!IsShort(env));
 693     unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
 694     assert(len > 1); // Or else would not require an array.
 695     BitSetShortLongRep res = (BitSetShortLongRep)(BitSetTraits::Alloc(env, len * sizeof(size_t)));
 696     for (unsigned i = 0; i < len; i++)
 697     {
 698         res[i] = 0;
 699     }
 700     return res;
 701 }
 702
 703 template <typename Env, typename BitSetTraits>
 704 BitSetShortLongRep BitSetOps</*BitSetType*/ BitSetShortLongRep,
 705                              /*Brand*/ BSShortLong,
 706                              /*Env*/ Env,
 707                              /*BitSetTraits*/ BitSetTraits>::MakeFullArrayBits(Env env)
 708 {
 709     assert(!IsShort(env));
 710     unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
 711     assert(len > 1); // Or else would not require an array.
 712     BitSetShortLongRep res = (BitSetShortLongRep)(BitSetTraits::Alloc(env, len * sizeof(size_t)));
 713     for (unsigned i = 0; i < len - 1; i++)
 714     {
 715         res[i] = size_t(-1);
 716     }
 717     // Start with all ones, shift in zeros in the last elem.
 718     unsigned lastElemBits = (BitSetTraits::GetSize(env) - 1) % BitsInSizeT + 1;
 719     res[len - 1]          = (size_t(-1) >> (BitsInSizeT - lastElemBits));
 720     return res;
 721 }
 722
 723 template <typename Env, typename BitSetTraits>
 724 bool BitSetOps</*BitSetType*/ BitSetShortLongRep,
 725                /*Brand*/ BSShortLong,
 726                /*Env*/ Env,
 727                /*BitSetTraits*/ BitSetTraits>::IsMemberLong(Env env, BitSetShortLongRep bs, unsigned i)
 728 {
 729     assert(!IsShort(env));
 730     unsigned index     = i / BitsInSizeT;
 731     unsigned bitInElem = (i % BitsInSizeT);
 732     size_t   mask      = ((size_t)1) << bitInElem;
 733     return (bs[index] & mask) != 0;
 734 }
 735
 736 template <typename Env, typename BitSetTraits>
 737 void BitSetOps</*BitSetType*/ BitSetShortLongRep,
 738                /*Brand*/ BSShortLong,
 739                /*Env*/ Env,
 740                /*BitSetTraits*/ BitSetTraits>::IntersectionDLong(Env                 env,
 741                                                                  BitSetShortLongRep& bs1,
 742                                                                  BitSetShortLongRep  bs2)
 743 {
 744     assert(!IsShort(env));
 745     unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
 746     for (unsigned i = 0; i < len; i++)
 747     {
 748         bs1[i] &= bs2[i];
 749     }
 750 }
 751
 752 template <typename Env, typename BitSetTraits>
 753 bool BitSetOps</*BitSetType*/ BitSetShortLongRep,
 754                /*Brand*/ BSShortLong,
 755                /*Env*/ Env,
 756                /*BitSetTraits*/ BitSetTraits>::IsEmptyIntersectionLong(Env                env,
 757                                                                        BitSetShortLongRep bs1,
 758                                                                        BitSetShortLongRep bs2)
 759 {
 760     assert(!IsShort(env));
 761     unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
 762     for (unsigned i = 0; i < len; i++)
 763     {
 764         if ((bs1[i] & bs2[i]) != 0)
 765         {
 766             return false;
 767         }
 768     }
 769     return true;
 770 }
 771
 772 template <typename Env, typename BitSetTraits>
 773 bool BitSetOps</*BitSetType*/ BitSetShortLongRep,
 774                /*Brand*/ BSShortLong,
 775                /*Env*/ Env,
 776                /*BitSetTraits*/ BitSetTraits>::IsEmptyUnionLong(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2)
 777 {
 778     assert(!IsShort(env));
 779     unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
 780     for (unsigned i = 0; i < len; i++)
 781     {
 782         if ((bs1[i] | bs2[i]) != 0)
 783         {
 784             return false;
 785         }
 786     }
 787     return true;
 788 }
 789
 790 template <typename Env, typename BitSetTraits>
 791 void BitSetOps</*BitSetType*/ BitSetShortLongRep,
 792                /*Brand*/ BSShortLong,
 793                /*Env*/ Env,
 794                /*BitSetTraits*/ BitSetTraits>::DataFlowDLong(Env                      env,
 795                                                              BitSetShortLongRep&      out,
 796                                                              const BitSetShortLongRep gen,
 797                                                              const BitSetShortLongRep in)
 798 {
 799     assert(!IsShort(env));
 800     unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
 801     for (unsigned i = 0; i < len; i++)
 802     {
 803         out[i] = out[i] & (gen[i] | in[i]);
 804     }
 805 }
 806
 807 template <typename Env, typename BitSetTraits>
 808 void BitSetOps</*BitSetType*/ BitSetShortLongRep,
 809                /*Brand*/ BSShortLong,
 810                /*Env*/ Env,
 811                /*BitSetTraits*/ BitSetTraits>::LivenessDLong(Env                      env,
 812                                                              BitSetShortLongRep&      in,
 813                                                              const BitSetShortLongRep def,
 814                                                              const BitSetShortLongRep use,
 815                                                              const BitSetShortLongRep out)
 816 {
 817     assert(!IsShort(env));
 818     unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
 819     for (unsigned i = 0; i < len; i++)
 820     {
 821         in[i] = use[i] | (out[i] & ~def[i]);
 822     }
 823 }
 824
 825 template <typename Env, typename BitSetTraits>
 826 bool BitSetOps</*BitSetType*/ BitSetShortLongRep,
 827                /*Brand*/ BSShortLong,
 828                /*Env*/ Env,
 829                /*BitSetTraits*/ BitSetTraits>::EqualLong(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2)
 830 {
 831     assert(!IsShort(env));
 832     unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
 833     for (unsigned i = 0; i < len; i++)
 834     {
 835         if (bs1[i] != bs2[i])
 836         {
 837             return false;
 838         }
 839     }
 840     return true;
 841 }
 842
 843 template <typename Env, typename BitSetTraits>
 844 bool BitSetOps</*BitSetType*/ BitSetShortLongRep,
 845                /*Brand*/ BSShortLong,
 846                /*Env*/ Env,
 847                /*BitSetTraits*/ BitSetTraits>::IsSubsetLong(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2)
 848 {
 849     assert(!IsShort(env));
 850     unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
 851     for (unsigned i = 0; i < len; i++)
 852     {
 853         if ((bs1[i] & bs2[i]) != bs1[i])
 854         {
 855             return false;
 856         }
 857     }
 858     return true;
 859 }
 860
 861 #ifdef DEBUG
 862 template <typename Env, typename BitSetTraits>
 863 const char* BitSetOps</*BitSetType*/ BitSetShortLongRep,
 864                       /*Brand*/ BSShortLong,
 865                       /*Env*/ Env,
 866                       /*BitSetTraits*/ BitSetTraits>::ToStringLong(Env env, BitSetShortLongRep bs)
 867 {
 868     assert(!IsShort(env));
 869     unsigned  len           = BitSetTraits::GetArrSize(env, sizeof(size_t));
 870     const int CharsForSizeT = sizeof(size_t) * 2;
 871     unsigned  allocSz       = len * CharsForSizeT + 4;
 872     unsigned  remaining     = allocSz;
 873     char*     res           = (char*)BitSetTraits::DebugAlloc(env, allocSz);
 874     char*     temp          = res;
 875     for (unsigned i = len; 0 < i; i--)
 876     {
 877         size_t bits = bs[i - 1];
 878         for (unsigned bytesDone = 0; bytesDone < sizeof(size_t); bytesDone += sizeof(unsigned))
 879         {
 880             unsigned bits0 = (unsigned)bits;
 881             sprintf_s(temp, remaining, "%08X", bits0);
 882             temp += 8;
 883             remaining -= 8;
 884             bytesDone += 4;
 885             assert(sizeof(unsigned) == 4);
 886             // Doing this twice by 16, rather than once by 32, avoids warnings when size_t == unsigned.
 887             bits = bits >> 16;
 888             bits = bits >> 16;
 889         }
 890     }
 891     return res;
 892 }
 893 #endif
 894
 895 #endif // bitSetAsShortLong_DEFINED