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