src/jit/hashbv.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
  10 // --------------------------------------------------------------------
  11 // --------------------------------------------------------------------
  12
  13 #ifdef DEBUG
  14 void hashBvNode::dump()
  15 {
  16     printf("base: %d { ", baseIndex);
  17     this->foreachBit(pBit);
  18     printf("}\n");
  19 }
  20 #endif // DEBUG
  21
  22 void hashBvNode::Reconstruct(indexType base)
  23 {
  24     baseIndex = base;
  25
  26     assert(!(baseIndex % BITS_PER_NODE));
  27
  28     for (int i = 0; i < this->numElements(); i++)
  29     {
  30         elements[i] = 0;
  31     }
  32     next = nullptr;
  33 }
  34
  35 hashBvNode::hashBvNode(indexType base)
  36 {
  37     this->Reconstruct(base);
  38 }
  39
  40 hashBvNode* hashBvNode::Create(indexType base, Compiler* compiler)
  41 {
  42     hashBvNode* result = nullptr;
  43
  44     if (compiler->hbvGlobalData.hbvNodeFreeList)
  45     {
  46         result                                  = compiler->hbvGlobalData.hbvNodeFreeList;
  47         compiler->hbvGlobalData.hbvNodeFreeList = result->next;
  48     }
  49     else
  50     {
  51         result = new (compiler, CMK_hashBv) hashBvNode;
  52     }
  53     result->Reconstruct(base);
  54     return result;
  55 }
  56
  57 void hashBvNode::freeNode(hashBvGlobalData* glob)
  58 {
  59     this->next            = glob->hbvNodeFreeList;
  60     glob->hbvNodeFreeList = this;
  61 }
  62
  63 void hashBvNode::setBit(indexType base)
  64 {
  65     assert(base >= baseIndex);
  66     assert(base - baseIndex < BITS_PER_NODE);
  67
  68     base -= baseIndex;
  69     indexType elem = base / BITS_PER_ELEMENT;
  70     indexType posi = base % BITS_PER_ELEMENT;
  71
  72     elements[elem] |= indexType(1) << posi;
  73 }
  74
  75 void hashBvNode::setLowest(indexType numToSet)
  76 {
  77     assert(numToSet <= BITS_PER_NODE);
  78
  79     int elemIndex = 0;
  80     while (numToSet > BITS_PER_ELEMENT)
  81     {
  82         elements[elemIndex] = ~(elemType(0));
  83         numToSet -= BITS_PER_ELEMENT;
  84         elemIndex++;
  85     }
  86     if (numToSet)
  87     {
  88         elemType allOnes    = ~(elemType(0));
  89         int      numToShift = (int)(BITS_PER_ELEMENT - numToSet);
  90         elements[elemIndex] = allOnes >> numToShift;
  91     }
  92 }
  93
  94 void hashBvNode::clrBit(indexType base)
  95 {
  96     assert(base >= baseIndex);
  97     assert(base - baseIndex < BITS_PER_NODE);
  98
  99     base -= baseIndex;
 100     indexType elem = base / BITS_PER_ELEMENT;
 101     indexType posi = base % BITS_PER_ELEMENT;
 102
 103     elements[elem] &= ~(indexType(1) << posi);
 104 }
 105
 106 bool hashBvNode::belongsIn(indexType index)
 107 {
 108     if (index < baseIndex)
 109     {
 110         return false;
 111     }
 112     if (index >= baseIndex + BITS_PER_NODE)
 113     {
 114         return false;
 115     }
 116     return true;
 117 }
 118
 119 int countBitsInWord(unsigned int bits)
 120 {
 121     // In-place adder tree: perform 16 1-bit adds, 8 2-bit adds,
 122     // 4 4-bit adds, 2 8=bit adds, and 1 16-bit add.
 123     bits = ((bits >> 1) & 0x55555555) + (bits & 0x55555555);
 124     bits = ((bits >> 2) & 0x33333333) + (bits & 0x33333333);
 125     bits = ((bits >> 4) & 0x0F0F0F0F) + (bits & 0x0F0F0F0F);
 126     bits = ((bits >> 8) & 0x00FF00FF) + (bits & 0x00FF00FF);
 127     bits = ((bits >> 16) & 0x0000FFFF) + (bits & 0x0000FFFF);
 128     return (int)bits;
 129 }
 130
 131 int countBitsInWord(unsigned __int64 bits)
 132 {
 133     bits = ((bits >> 1) & 0x5555555555555555) + (bits & 0x5555555555555555);
 134     bits = ((bits >> 2) & 0x3333333333333333) + (bits & 0x3333333333333333);
 135     bits = ((bits >> 4) & 0x0F0F0F0F0F0F0F0F) + (bits & 0x0F0F0F0F0F0F0F0F);
 136     bits = ((bits >> 8) & 0x00FF00FF00FF00FF) + (bits & 0x00FF00FF00FF00FF);
 137     bits = ((bits >> 16) & 0x0000FFFF0000FFFF) + (bits & 0x0000FFFF0000FFFF);
 138     bits = ((bits >> 32) & 0x00000000FFFFFFFF) + (bits & 0x00000000FFFFFFFF);
 139     return (int)bits;
 140 }
 141
 142 int hashBvNode::countBits()
 143 {
 144     int result = 0;
 145
 146     for (int i = 0; i < this->numElements(); i++)
 147     {
 148         elemType bits = elements[i];
 149
 150         result += countBitsInWord(bits);
 151
 152         result += (int)bits;
 153     }
 154     return result;
 155 }
 156
 157 bool hashBvNode::anyBits()
 158 {
 159     for (int i = 0; i < this->numElements(); i++)
 160     {
 161         if (elements[i])
 162         {
 163             return true;
 164         }
 165     }
 166     return false;
 167 }
 168
 169 bool hashBvNode::getBit(indexType base)
 170 {
 171     assert(base >= baseIndex);
 172     assert(base - baseIndex < BITS_PER_NODE);
 173     base -= baseIndex;
 174
 175     indexType elem = base / BITS_PER_ELEMENT;
 176     indexType posi = base % BITS_PER_ELEMENT;
 177
 178     if (elements[elem] & (indexType(1) << posi))
 179     {
 180         return true;
 181     }
 182     else
 183     {
 184         return false;
 185     }
 186 }
 187
 188 bool hashBvNode::anySet()
 189 {
 190     for (int i = 0; i < this->numElements(); i++)
 191     {
 192         if (elements[i])
 193         {
 194             return true;
 195         }
 196     }
 197     return false;
 198 }
 199
 200 void hashBvNode::copyFrom(hashBvNode* other)
 201 {
 202     this->baseIndex = other->baseIndex;
 203     for (int i = 0; i < this->numElements(); i++)
 204     {
 205         this->elements[i] = other->elements[i];
 206     }
 207 }
 208
 209 void hashBvNode::foreachBit(bitAction a)
 210 {
 211     indexType base;
 212     for (int i = 0; i < this->numElements(); i++)
 213     {
 214         base       = baseIndex + i * BITS_PER_ELEMENT;
 215         elemType e = elements[i];
 216         while (e)
 217         {
 218             if (e & 1)
 219             {
 220                 a(base);
 221             }
 222             e >>= 1;
 223             base++;
 224         }
 225     }
 226 }
 227
 228 elemType hashBvNode::AndWithChange(hashBvNode* other)
 229 {
 230     elemType result = 0;
 231
 232     for (int i = 0; i < this->numElements(); i++)
 233     {
 234         elemType src = this->elements[i];
 235         elemType dst;
 236
 237         dst = src & other->elements[i];
 238         result |= src ^ dst;
 239         this->elements[i] = dst;
 240     }
 241     return result;
 242 }
 243
 244 elemType hashBvNode::OrWithChange(hashBvNode* other)
 245 {
 246     elemType result = 0;
 247
 248     for (int i = 0; i < this->numElements(); i++)
 249     {
 250         elemType src = this->elements[i];
 251         elemType dst;
 252
 253         dst = src | other->elements[i];
 254         result |= src ^ dst;
 255         this->elements[i] = dst;
 256     }
 257     return result;
 258 }
 259
 260 elemType hashBvNode::XorWithChange(hashBvNode* other)
 261 {
 262     elemType result = 0;
 263
 264     for (int i = 0; i < this->numElements(); i++)
 265     {
 266         elemType src = this->elements[i];
 267         elemType dst;
 268
 269         dst = src ^ other->elements[i];
 270         result |= src ^ dst;
 271         this->elements[i] = dst;
 272     }
 273     return result;
 274 }
 275
 276 elemType hashBvNode::SubtractWithChange(hashBvNode* other)
 277 {
 278     elemType result = 0;
 279
 280     for (int i = 0; i < this->numElements(); i++)
 281     {
 282         elemType src = this->elements[i];
 283         elemType dst;
 284
 285         dst = src & ~other->elements[i];
 286         result |= src ^ dst;
 287         this->elements[i] = dst;
 288     }
 289     return result;
 290 }
 291
 292 bool hashBvNode::Intersects(hashBvNode* other)
 293 {
 294     for (int i = 0; i < this->numElements(); i++)
 295     {
 296         if ((this->elements[i] & other->elements[i]) != 0)
 297         {
 298             return true;
 299         }
 300     }
 301
 302     return false;
 303 }
 304
 305 void hashBvNode::AndWith(hashBvNode* other)
 306 {
 307     for (int i = 0; i < this->numElements(); i++)
 308     {
 309         this->elements[i] &= other->elements[i];
 310     }
 311 }
 312
 313 void hashBvNode::OrWith(hashBvNode* other)
 314 {
 315     for (int i = 0; i < this->numElements(); i++)
 316     {
 317         this->elements[i] |= other->elements[i];
 318     }
 319 }
 320
 321 void hashBvNode::XorWith(hashBvNode* other)
 322 {
 323     for (int i = 0; i < this->numElements(); i++)
 324     {
 325         this->elements[i] ^= other->elements[i];
 326     }
 327 }
 328
 329 void hashBvNode::Subtract(hashBvNode* other)
 330 {
 331     for (int i = 0; i < this->numElements(); i++)
 332     {
 333         this->elements[i] &= ~other->elements[i];
 334     }
 335 }
 336
 337 bool hashBvNode::sameAs(hashBvNode* other)
 338 {
 339     if (this->baseIndex != other->baseIndex)
 340     {
 341         return false;
 342     }
 343
 344     for (int i = 0; i < this->numElements(); i++)
 345     {
 346         if (this->elements[i] != other->elements[i])
 347         {
 348             return false;
 349         }
 350     }
 351
 352     return true;
 353 }
 354
 355 // --------------------------------------------------------------------
 356 // --------------------------------------------------------------------
 357
 358 hashBv::hashBv(Compiler* comp)
 359 {
 360     this->compiler      = comp;
 361     this->log2_hashSize = globalData()->hbvHashSizeLog2;
 362
 363     int hts = hashtable_size();
 364     nodeArr = getNewVector(hts);
 365
 366     for (int i = 0; i < hts; i++)
 367     {
 368         nodeArr[i] = nullptr;
 369     }
 370     this->numNodes = 0;
 371 }
 372
 373 hashBv* hashBv::Create(Compiler* compiler)
 374 {
 375     hashBv*           result;
 376     hashBvGlobalData* gd = &compiler->hbvGlobalData;
 377
 378     if (hbvFreeList(gd))
 379     {
 380         result          = hbvFreeList(gd);
 381         hbvFreeList(gd) = result->next;
 382         assert(result->nodeArr);
 383     }
 384     else
 385     {
 386         result = new (compiler, CMK_hashBv) hashBv(compiler);
 387         memset(result, 0, sizeof(hashBv));
 388         result->nodeArr = result->initialVector;
 389     }
 390
 391     result->compiler      = compiler;
 392     result->log2_hashSize = 0;
 393     result->numNodes      = 0;
 394
 395     return result;
 396 }
 397
 398 void hashBv::Init(Compiler* compiler)
 399 {
 400     memset(&compiler->hbvGlobalData, 0, sizeof(hashBvGlobalData));
 401 }
 402
 403 hashBvGlobalData* hashBv::globalData()
 404 {
 405     return &compiler->hbvGlobalData;
 406 }
 407
 408 hashBvNode** hashBv::getNewVector(int vectorLength)
 409 {
 410     assert(vectorLength > 0);
 411     assert(isPow2(vectorLength));
 412
 413     hashBvNode** newVector = new (compiler, CMK_hashBv) hashBvNode*[vectorLength]();
 414     return newVector;
 415 }
 416
 417 hashBvNode*& hashBv::nodeFreeList(hashBvGlobalData* data)
 418 {
 419     return data->hbvNodeFreeList;
 420 }
 421
 422 hashBv*& hashBv::hbvFreeList(hashBvGlobalData* data)
 423 {
 424     return data->hbvFreeList;
 425 }
 426
 427 void hashBv::freeVector(hashBvNode* vect, int vectorLength)
 428 {
 429     // not enough space to do anything with it
 430     if (vectorLength < 2)
 431     {
 432         return;
 433     }
 434
 435     hbvFreeListNode* f              = (hbvFreeListNode*)vect;
 436     f->next                         = globalData()->hbvFreeVectorList;
 437     globalData()->hbvFreeVectorList = f;
 438     f->size                         = vectorLength;
 439 }
 440
 441 void hashBv::hbvFree()
 442 {
 443     Compiler* comp = this->compiler;
 444
 445     int hts = hashtable_size();
 446     for (int i = 0; i < hts; i++)
 447     {
 448         while (nodeArr[i])
 449         {
 450             hashBvNode* curr = nodeArr[i];
 451             nodeArr[i]       = curr->next;
 452             curr->freeNode(globalData());
 453         }
 454     }
 455     // keep the vector attached because the whole thing is freelisted
 456     // plus you don't even know if it's freeable
 457
 458     this->next                = hbvFreeList(globalData());
 459     hbvFreeList(globalData()) = this;
 460 }
 461
 462 hashBv* hashBv::CreateFrom(hashBv* other, Compiler* comp)
 463 {
 464     hashBv* result = hashBv::Create(comp);
 465     result->copyFrom(other, comp);
 466     return result;
 467 }
 468
 469 void hashBv::MergeLists(hashBvNode** root1, hashBvNode** root2)
 470 {
 471 }
 472
 473 bool hashBv::TooSmall()
 474 {
 475     return this->numNodes > this->hashtable_size() * 4;
 476 }
 477
 478 bool hashBv::TooBig()
 479 {
 480     return this->hashtable_size() > this->numNodes * 4;
 481 }
 482
 483 int hashBv::getNodeCount()
 484 {
 485     int size   = hashtable_size();
 486     int result = 0;
 487
 488     for (int i = 0; i < size; i++)
 489     {
 490         hashBvNode* last = nodeArr[i];
 491
 492         while (last)
 493         {
 494             last = last->next;
 495             result++;
 496         }
 497     }
 498     return result;
 499 }
 500
 501 bool hashBv::IsValid()
 502 {
 503     int size = hashtable_size();
 504     // is power of 2
 505     assert(((size - 1) & size) == 0);
 506
 507     for (int i = 0; i < size; i++)
 508     {
 509         hashBvNode* last = nodeArr[i];
 510         hashBvNode* curr;
 511         int         lastIndex = -1;
 512
 513         while (last)
 514         {
 515             // the node has been hashed correctly
 516             assert((int)last->baseIndex > lastIndex);
 517             lastIndex = (int)last->baseIndex;
 518             assert(i == getHashForIndex(last->baseIndex, size));
 519             curr = last->next;
 520             // the order is monotonically increasing bases
 521             if (curr)
 522             {
 523                 assert(curr->baseIndex > last->baseIndex);
 524             }
 525             last = curr;
 526         }
 527     }
 528     return true;
 529 }
 530
 531 void hashBv::Resize()
 532 {
 533     // resize to 'optimal' size
 534
 535     this->Resize(this->numNodes);
 536 }
 537
 538 void hashBv::Resize(int newSize)
 539 {
 540     assert(newSize > 0);
 541     newSize = nearest_pow2(newSize);
 542
 543     int oldSize = hashtable_size();
 544
 545     if (newSize == oldSize)
 546     {
 547         return;
 548     }
 549
 550     int oldSizeLog2  = log2_hashSize;
 551     int log2_newSize = genLog2((unsigned)newSize);
 552
 553     hashBvNode** newNodes = this->getNewVector(newSize);
 554
 555     hashBvNode*** insertionPoints = (hashBvNode***)alloca(sizeof(hashBvNode*) * newSize);
 556     memset(insertionPoints, 0, sizeof(hashBvNode*) * newSize);
 557
 558     for (int i = 0; i < newSize; i++)
 559     {
 560         insertionPoints[i] = &(newNodes[i]);
 561     }
 562
 563     if (newSize > oldSize)
 564     {
 565         // for each src list, expand it into multiple dst lists
 566         for (int i = 0; i < oldSize; i++)
 567         {
 568             hashBvNode* next = nodeArr[i];
 569
 570             while (next)
 571             {
 572                 hashBvNode* curr = next;
 573                 next             = curr->next;
 574                 int destination  = getHashForIndex(curr->baseIndex, newSize);
 575
 576                 // ...
 577
 578                 // stick the current node on the end of the selected list
 579                 *(insertionPoints[destination]) = curr;
 580                 insertionPoints[destination]    = &(curr->next);
 581                 curr->next                      = nullptr;
 582             }
 583         }
 584         nodeArr       = newNodes;
 585         log2_hashSize = (unsigned short)log2_newSize;
 586     }
 587     else if (oldSize > newSize)
 588     {
 589         int shrinkFactor = oldSize / newSize;
 590
 591         // shrink multiple lists into one list
 592         // more efficient ways to do this but...
 593         // if the lists are long, you shouldn't be shrinking.
 594         for (int i = 0; i < oldSize; i++)
 595         {
 596             hashBvNode* next = nodeArr[i];
 597
 598             if (next)
 599             {
 600                 // all nodes in this list should have the same destination list
 601                 int          destination    = getHashForIndex(next->baseIndex, newSize);
 602                 hashBvNode** insertionPoint = &newNodes[destination];
 603                 do
 604                 {
 605                     hashBvNode* curr = next;
 606                     // figure out where to insert it
 607                     while (*insertionPoint && (*insertionPoint)->baseIndex < curr->baseIndex)
 608                     {
 609                         insertionPoint = &((*insertionPoint)->next);
 610                     }
 611                     next = curr->next;
 612
 613                     hashBvNode* temp = *insertionPoint;
 614                     *insertionPoint  = curr;
 615                     curr->next       = temp;
 616
 617                 } while (next);
 618             }
 619         }
 620         nodeArr       = newNodes;
 621         log2_hashSize = (unsigned short)log2_newSize;
 622     }
 623     else
 624     {
 625         // same size
 626         assert(oldSize == newSize);
 627     }
 628     assert(this->IsValid());
 629 }
 630
 631 #ifdef DEBUG
 632 void hashBv::dump()
 633 {
 634     bool      first = true;
 635     indexType index;
 636
 637     // uncomment to print internal implementation details
 638     // DBEXEC(TRUE, printf("[%d(%d)(nodes:%d)]{ ", hashtable_size(), countBits(), this->numNodes));
 639
 640     printf("{");
 641     FOREACH_HBV_BIT_SET(index, this)
 642     {
 643         if (!first)
 644         {
 645             printf(" ");
 646         }
 647         printf("%d", index);
 648         first = false;
 649     }
 650     NEXT_HBV_BIT_SET;
 651     printf("}\n");
 652 }
 653
 654 void hashBv::dumpFancy()
 655 {
 656     indexType index;
 657     indexType last_1 = -1;
 658     indexType last_0 = -1;
 659
 660     printf("{");
 661     printf("count:%d", this->countBits());
 662     FOREACH_HBV_BIT_SET(index, this)
 663     {
 664         if (last_1 != index - 1)
 665         {
 666             if (last_0 + 1 != last_1)
 667             {
 668                 printf(" %d-%d", last_0 + 1, last_1);
 669             }
 670             else
 671             {
 672                 printf(" %d", last_1);
 673             }
 674             last_0 = index - 1;
 675         }
 676         last_1 = index;
 677     }
 678     NEXT_HBV_BIT_SET;
 679
 680     // Print the last one
 681     if (last_0 + 1 != last_1)
 682     {
 683         printf(" %d-%d", last_0 + 1, last_1);
 684     }
 685     else
 686     {
 687         printf(" %d", last_1);
 688     }
 689
 690     printf("}\n");
 691 }
 692 #endif // DEBUG
 693
 694 void hashBv::removeNodeAtBase(indexType index)
 695 {
 696     hashBvNode** insertionPoint = this->getInsertionPointForIndex(index);
 697
 698     hashBvNode* node = *insertionPoint;
 699
 700     // make sure that we were called to remove something
 701     // that really was there
 702     assert(node);
 703
 704     // splice it out
 705     *insertionPoint = node->next;
 706     this->numNodes--;
 707 }
 708
 709 int hashBv::getHashForIndex(indexType index, int table_size)
 710 {
 711     indexType hashIndex;
 712
 713     hashIndex = index >> LOG2_BITS_PER_NODE;
 714     hashIndex &= (table_size - 1);
 715
 716     return (int)hashIndex;
 717 }
 718
 719 int hashBv::getRehashForIndex(indexType thisIndex, int thisTableSize, int newTableSize)
 720 {
 721     assert(0);
 722     return 0;
 723 }
 724
 725 hashBvNode** hashBv::getInsertionPointForIndex(indexType index)
 726 {
 727     indexType indexInNode;
 728     indexType hashIndex;
 729     indexType baseIndex;
 730
 731     hashBvNode* result;
 732
 733     hashIndex = getHashForIndex(index, hashtable_size());
 734
 735     baseIndex   = index & ~(BITS_PER_NODE - 1);
 736     indexInNode = index & (BITS_PER_NODE - 1);
 737
 738     // printf("(%x) : hsh=%x, base=%x, index=%x\n", index,
 739     //      hashIndex, baseIndex, indexInNode);
 740
 741     // find the node
 742     hashBvNode** prev = &nodeArr[hashIndex];
 743     result            = nodeArr[hashIndex];
 744
 745     while (result)
 746     {
 747         if (result->baseIndex == baseIndex)
 748         {
 749             return prev;
 750         }
 751         else if (result->baseIndex > baseIndex)
 752         {
 753             return prev;
 754         }
 755         else
 756         {
 757             prev   = &(result->next);
 758             result = result->next;
 759         }
 760     }
 761     return prev;
 762 }
 763
 764 hashBvNode* hashBv::getNodeForIndexHelper(indexType index, bool canAdd)
 765 {
 766     // determine the base index of the node containing this index
 767     index = index & ~(BITS_PER_NODE - 1);
 768
 769     hashBvNode** prev = getInsertionPointForIndex(index);
 770
 771     hashBvNode* node = *prev;
 772
 773     if (node && node->belongsIn(index))
 774     {
 775         return node;
 776     }
 777     else if (canAdd)
 778     {
 779         // missing node, insert it before the current one
 780         hashBvNode* temp = hashBvNode::Create(index, this->compiler);
 781         temp->next       = node;
 782         *prev            = temp;
 783         this->numNodes++;
 784         return temp;
 785     }
 786     else
 787     {
 788         return nullptr;
 789     }
 790 }
 791
 792 hashBvNode* hashBv::getNodeForIndex(indexType index)
 793 {
 794     // determine the base index of the node containing this index
 795     index = index & ~(BITS_PER_NODE - 1);
 796
 797     hashBvNode** prev = getInsertionPointForIndex(index);
 798
 799     hashBvNode* node = *prev;
 800
 801     if (node && node->belongsIn(index))
 802     {
 803         return node;
 804     }
 805     else
 806     {
 807         return nullptr;
 808     }
 809 }
 810
 811 void hashBv::setBit(indexType index)
 812 {
 813     assert(index >= 0);
 814     assert(this->numNodes == this->getNodeCount());
 815     hashBvNode* result = nullptr;
 816
 817     indexType baseIndex = index & ~(BITS_PER_NODE - 1);
 818     indexType base      = index - baseIndex;
 819     indexType elem      = base / BITS_PER_ELEMENT;
 820     indexType posi      = base % BITS_PER_ELEMENT;
 821
 822     // this should be the 99% case :  when there is only one node in the structure
 823     if ((result = nodeArr[0]) && result->baseIndex == baseIndex)
 824     {
 825         result->elements[elem] |= indexType(1) << posi;
 826         return;
 827     }
 828
 829     result = getOrAddNodeForIndex(index);
 830     result->setBit(index);
 831
 832     assert(this->numNodes == this->getNodeCount());
 833
 834     // if it's getting out of control resize it
 835     if (this->numNodes > this->hashtable_size() * 4)
 836     {
 837         this->Resize();
 838     }
 839
 840     return;
 841 }
 842
 843 void hashBv::setAll(indexType numToSet)
 844 {
 845     // TODO-Throughput: this could be more efficient
 846     for (unsigned int i = 0; i < numToSet; i += BITS_PER_NODE)
 847     {
 848         hashBvNode* node        = getOrAddNodeForIndex(i);
 849         indexType   bits_to_set = min(BITS_PER_NODE, numToSet - i);
 850         node->setLowest(bits_to_set);
 851     }
 852 }
 853
 854 void hashBv::clearBit(indexType index)
 855 {
 856     assert(index >= 0);
 857     assert(this->numNodes == this->getNodeCount());
 858     hashBvNode* result = nullptr;
 859
 860     indexType baseIndex = index & ~(BITS_PER_NODE - 1);
 861     indexType hashIndex = getHashForIndex(index, hashtable_size());
 862
 863     hashBvNode** prev = &nodeArr[hashIndex];
 864     result            = nodeArr[hashIndex];
 865
 866     while (result)
 867     {
 868         if (result->baseIndex == baseIndex)
 869         {
 870             result->clrBit(index);
 871             // if nothing left set free it
 872             if (!result->anySet())
 873             {
 874                 *prev = result->next;
 875                 result->freeNode(globalData());
 876                 this->numNodes--;
 877             }
 878             return;
 879         }
 880         else if (result->baseIndex > baseIndex)
 881         {
 882             return;
 883         }
 884         else
 885         {
 886             prev   = &(result->next);
 887             result = result->next;
 888         }
 889     }
 890     assert(this->numNodes == this->getNodeCount());
 891     return;
 892 }
 893
 894 bool hashBv::testBit(indexType index)
 895 {
 896     // determine the base index of the node containing this index
 897     indexType baseIndex = index & ~(BITS_PER_NODE - 1);
 898     // 99% case
 899     if (nodeArr[0] && nodeArr[0]->baseIndex == baseIndex)
 900     {
 901         return nodeArr[0]->getBit(index);
 902     }
 903
 904     indexType hashIndex = getHashForIndex(baseIndex, hashtable_size());
 905
 906     hashBvNode* iter = nodeArr[hashIndex];
 907
 908     while (iter)
 909     {
 910         if (iter->baseIndex == baseIndex)
 911         {
 912             return iter->getBit(index);
 913         }
 914         else
 915         {
 916             iter = iter->next;
 917         }
 918     }
 919     return false;
 920 }
 921
 922 int hashBv::countBits()
 923 {
 924     int result = 0;
 925     int hts    = this->hashtable_size();
 926     for (int hashNum = 0; hashNum < hts; hashNum++)
 927     {
 928         hashBvNode* node = nodeArr[hashNum];
 929         while (node)
 930         {
 931             result += node->countBits();
 932             node = node->next;
 933         }
 934     }
 935     return result;
 936 }
 937
 938 bool hashBv::anySet()
 939 {
 940     int result = 0;
 941
 942     int hts = this->hashtable_size();
 943     for (int hashNum = 0; hashNum < hts; hashNum++)
 944     {
 945         hashBvNode* node = nodeArr[hashNum];
 946         while (node)
 947         {
 948             if (node->anySet())
 949             {
 950                 return true;
 951             }
 952             node = node->next;
 953         }
 954     }
 955     return false;
 956 }
 957
 958 class AndAction
 959 {
 960 public:
 961     static inline void PreAction(hashBv* lhs, hashBv* rhs)
 962     {
 963     }
 964     static inline void PostAction(hashBv* lhs, hashBv* rhs)
 965     {
 966     }
 967     static inline bool DefaultResult()
 968     {
 969         return false;
 970     }
 971
 972     static inline void LeftGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
 973     {
 974         // it's in other, not this
 975         // so skip it
 976         r = r->next;
 977     }
 978     static inline void RightGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
 979     {
 980         // it's in LHS, not RHS
 981         // so have to remove it
 982         hashBvNode* old = *l;
 983         *l              = (*l)->next;
 984         // splice it out
 985         old->freeNode(lhs->globalData());
 986         lhs->numNodes--;
 987         result = true;
 988     }
 989     static inline void BothPresent(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
 990     {
 991         if ((*l)->AndWithChange(r))
 992         {
 993             r      = r->next;
 994             result = true;
 995
 996             if ((*l)->anySet())
 997             {
 998                 l = &((*l)->next);
 999             }
1000             else
1001             {
1002                 hashBvNode* old = *l;
1003                 *l              = (*l)->next;
1004                 old->freeNode(lhs->globalData());
1005                 lhs->numNodes--;
1006             }
1007         }
1008         else
1009         {
1010             r = r->next;
1011             l = &((*l)->next);
1012         }
1013     }
1014     static inline void LeftEmpty(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1015     {
1016         r = r->next;
1017     }
1018 };
1019
1020 class SubtractAction
1021 {
1022 public:
1023     static inline void PreAction(hashBv* lhs, hashBv* rhs)
1024     {
1025     }
1026     static inline void PostAction(hashBv* lhs, hashBv* rhs)
1027     {
1028     }
1029     static inline bool DefaultResult()
1030     {
1031         return false;
1032     }
1033     static inline void LeftGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1034     {
1035         // it's in other, not this
1036         // so skip it
1037         r = r->next;
1038     }
1039     static inline void RightGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1040     {
1041         // in lhs, not rhs
1042         // so skip lhs
1043         l = &((*l)->next);
1044     }
1045     static inline void BothPresent(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1046     {
1047         if ((*l)->SubtractWithChange(r))
1048         {
1049             r      = r->next;
1050             result = true;
1051
1052             if ((*l)->anySet())
1053             {
1054                 l = &((*l)->next);
1055             }
1056             else
1057             {
1058                 hashBvNode* old = *l;
1059                 *l              = (*l)->next;
1060                 old->freeNode(lhs->globalData());
1061                 lhs->numNodes--;
1062             }
1063         }
1064         else
1065         {
1066             r = r->next;
1067             l = &((*l)->next);
1068         }
1069     }
1070     static inline void LeftEmpty(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1071     {
1072         r = r->next;
1073     }
1074 };
1075
1076 class XorAction
1077 {
1078 public:
1079     static inline void PreAction(hashBv* lhs, hashBv* rhs)
1080     {
1081     }
1082     static inline void PostAction(hashBv* lhs, hashBv* rhs)
1083     {
1084     }
1085     static inline bool DefaultResult()
1086     {
1087         return false;
1088     }
1089
1090     static inline void LeftGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1091     {
1092         // it's in other, not this
1093         // so put one in
1094         result           = true;
1095         hashBvNode* temp = hashBvNode::Create(r->baseIndex, lhs->compiler);
1096         lhs->numNodes++;
1097         temp->XorWith(r);
1098         temp->next = (*l)->next;
1099         *l         = temp;
1100         l          = &(temp->next);
1101
1102         r = r->next;
1103     }
1104
1105     static inline void RightGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1106     {
1107         // it's in LHS, not RHS
1108         // so LHS remains the same
1109         l = &((*l)->next);
1110     }
1111
1112     static inline void BothPresent(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1113     {
1114         if ((*l)->XorWithChange(r))
1115         {
1116             result = true;
1117         }
1118         l = &((*l)->next);
1119         r = r->next;
1120     }
1121
1122     static inline void LeftEmpty(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1123     {
1124         // it's in other, not this
1125         // so put one in
1126         result           = true;
1127         hashBvNode* temp = hashBvNode::Create(r->baseIndex, lhs->compiler);
1128         lhs->numNodes++;
1129         temp->XorWith(r);
1130         temp->next = nullptr;
1131         *l         = temp;
1132         l          = &(temp->next);
1133
1134         r = r->next;
1135     }
1136 };
1137
1138 class OrAction
1139 {
1140 public:
1141     static inline void PreAction(hashBv* lhs, hashBv* rhs)
1142     {
1143         if (lhs->log2_hashSize + 2 < rhs->log2_hashSize)
1144         {
1145             lhs->Resize(rhs->numNodes);
1146         }
1147         if (rhs->numNodes > rhs->hashtable_size() * 4)
1148         {
1149             rhs->Resize(rhs->numNodes);
1150         }
1151     }
1152     static inline void PostAction(hashBv* lhs, hashBv* rhs)
1153     {
1154     }
1155     static inline bool DefaultResult()
1156     {
1157         return false;
1158     }
1159
1160     static inline void LeftGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1161     {
1162         // it's in other, not this
1163         // so put one in
1164         result           = true;
1165         hashBvNode* temp = hashBvNode::Create(r->baseIndex, lhs->compiler);
1166         lhs->numNodes++;
1167         temp->OrWith(r);
1168         temp->next = *l;
1169         *l         = temp;
1170         l          = &(temp->next);
1171
1172         r = r->next;
1173     }
1174     static inline void RightGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1175     {
1176         // in lhs, not rhs
1177         // so skip lhs
1178         l = &((*l)->next);
1179     }
1180     static inline void BothPresent(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1181     {
1182         if ((*l)->OrWithChange(r))
1183         {
1184             result = true;
1185         }
1186         l = &((*l)->next);
1187         r = r->next;
1188     }
1189     static inline void LeftEmpty(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1190     {
1191         // other contains something this does not
1192         // copy it
1193         // LeftGap(lhs, l, r, result, terminate);
1194         result           = true;
1195         hashBvNode* temp = hashBvNode::Create(r->baseIndex, lhs->compiler);
1196         lhs->numNodes++;
1197         temp->OrWith(r);
1198         temp->next = nullptr;
1199         *l         = temp;
1200         l          = &(temp->next);
1201
1202         r = r->next;
1203     }
1204 };
1205
1206 class CompareAction
1207 {
1208 public:
1209     static inline void PreAction(hashBv* lhs, hashBv* rhs)
1210     {
1211     }
1212     static inline void PostAction(hashBv* lhs, hashBv* rhs)
1213     {
1214     }
1215     static inline bool DefaultResult()
1216     {
1217         return true;
1218     }
1219
1220     static inline void LeftGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1221     {
1222         terminate = true;
1223         result    = false;
1224     }
1225     static inline void RightGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1226     {
1227         // in lhs, not rhs
1228         // so skip lhs
1229         terminate = true;
1230         result    = false;
1231     }
1232     static inline void BothPresent(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1233     {
1234         if (!(*l)->sameAs(r))
1235         {
1236             terminate = true;
1237             result    = false;
1238         }
1239         l = &((*l)->next);
1240         r = r->next;
1241     }
1242     static inline void LeftEmpty(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1243     {
1244         terminate = true;
1245         result    = false;
1246     }
1247 };
1248
1249 class IntersectsAction
1250 {
1251 public:
1252     static inline void PreAction(hashBv* lhs, hashBv* rhs)
1253     {
1254     }
1255     static inline void PostAction(hashBv* lhs, hashBv* rhs)
1256     {
1257     }
1258     static inline bool DefaultResult()
1259     {
1260         return false;
1261     }
1262
1263     static inline void LeftGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1264     {
1265         // in rhs, not lhs
1266         // so skip rhs
1267         r = r->next;
1268     }
1269     static inline void RightGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1270     {
1271         // in lhs, not rhs
1272         // so skip lhs
1273         l = &((*l)->next);
1274     }
1275     static inline void BothPresent(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1276     {
1277         if ((*l)->Intersects(r))
1278         {
1279             terminate = true;
1280             result    = true;
1281         }
1282     }
1283     static inline void LeftEmpty(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1284     {
1285         r = r->next;
1286     }
1287 };
1288
1289 template <typename Action>
1290 bool hashBv::MultiTraverseLHSBigger(hashBv* other)
1291 {
1292     int hts = this->hashtable_size();
1293     int ots = other->hashtable_size();
1294
1295     bool result    = Action::DefaultResult();
1296     bool terminate = false;
1297
1298     // this is larger
1299     hashBvNode*** cursors;
1300     int           shiftFactor     = this->log2_hashSize - other->log2_hashSize;
1301     int           expansionFactor = hts / ots;
1302     cursors                       = (hashBvNode***)alloca(expansionFactor * sizeof(void*));
1303
1304     for (int h = 0; h < other->hashtable_size(); h++)
1305     {
1306         // set up cursors for the expansion of nodes
1307         for (int i = 0; i < expansionFactor; i++)
1308         {
1309             // ex: for [1024] &= [8]
1310             // for rhs in bin 0
1311             // cursors point to lhs: 0, 8, 16, 24, ...
1312             cursors[i] = &nodeArr[ots * i + h];
1313         }
1314
1315         hashBvNode* o = other->nodeArr[h];
1316         while (o)
1317         {
1318             hashBvNode* next = o->next;
1319             // figure out what dst list this goes to
1320             int          hash     = getHashForIndex(o->baseIndex, hts);
1321             int          dstIndex = (hash - h) >> other->log2_hashSize;
1322             hashBvNode** cursor   = cursors[dstIndex];
1323             hashBvNode*  c        = *cursor;
1324
1325             // figure out where o fits in the cursor
1326
1327             if (!c)
1328             {
1329                 Action::LeftEmpty(this, cursors[dstIndex], o, result, terminate);
1330                 if (terminate)
1331                 {
1332                     return result;
1333                 }
1334             }
1335             else if (c->baseIndex == o->baseIndex)
1336             {
1337                 Action::BothPresent(this, cursors[dstIndex], o, result, terminate);
1338                 if (terminate)
1339                 {
1340                     return result;
1341                 }
1342             }
1343             else if (c->baseIndex > o->baseIndex)
1344             {
1345                 Action::LeftGap(this, cursors[dstIndex], o, result, terminate);
1346                 if (terminate)
1347                 {
1348                     return result;
1349                 }
1350             }
1351             else if (c->baseIndex < o->baseIndex)
1352             {
1353                 Action::RightGap(this, cursors[dstIndex], o, result, terminate);
1354                 if (terminate)
1355                 {
1356                     return result;
1357                 }
1358             }
1359         }
1360         for (int i = 0; i < expansionFactor; i++)
1361         {
1362             while (*(cursors[i]))
1363             {
1364                 Action::RightGap(this, cursors[i], o, result, terminate);
1365                 if (terminate)
1366                 {
1367                     return result;
1368                 }
1369             }
1370         }
1371     }
1372     return result;
1373 }
1374
1375 template <typename Action>
1376 bool hashBv::MultiTraverseRHSBigger(hashBv* other)
1377 {
1378     int hts = this->hashtable_size();
1379     int ots = other->hashtable_size();
1380
1381     bool result    = Action::DefaultResult();
1382     bool terminate = false;
1383
1384     for (int hashNum = 0; hashNum < ots; hashNum++)
1385     {
1386         int destination = getHashForIndex(BITS_PER_NODE * hashNum, this->hashtable_size());
1387         assert(hashNum == getHashForIndex(BITS_PER_NODE * hashNum, other->hashtable_size()));
1388
1389         hashBvNode** pa = &this->nodeArr[destination];
1390         hashBvNode** pb = &other->nodeArr[hashNum];
1391         hashBvNode*  b  = *pb;
1392
1393         while (*pa && b)
1394         {
1395             hashBvNode* a = *pa;
1396             if (a->baseIndex < b->baseIndex)
1397             {
1398                 // in a but not in b
1399                 // but maybe it's someplace else in b
1400                 if (getHashForIndex(a->baseIndex, ots) == hashNum)
1401                 {
1402                     // this contains something other does not
1403                     // need to erase it
1404                     Action::RightGap(this, pa, b, result, terminate);
1405                     if (terminate)
1406                     {
1407                         return result;
1408                     }
1409                 }
1410                 else
1411                 {
1412                     // other might contain this, we don't know yet
1413                     pa = &a->next;
1414                 }
1415             }
1416             else if (a->baseIndex == b->baseIndex)
1417             {
1418                 Action::BothPresent(this, pa, b, result, terminate);
1419                 if (terminate)
1420                 {
1421                     return result;
1422                 }
1423             }
1424             else if (a->baseIndex > b->baseIndex)
1425             {
1426                 // other contains something this does not
1427                 Action::LeftGap(this, pa, b, result, terminate);
1428                 if (terminate)
1429                 {
1430                     return result;
1431                 }
1432             }
1433         }
1434         while (*pa)
1435         {
1436             // if it's in the dest but not in src
1437             // then make sure it's expected to be in this list
1438             if (getHashForIndex((*pa)->baseIndex, ots) == hashNum)
1439             {
1440                 Action::RightGap(this, pa, b, result, terminate);
1441                 if (terminate)
1442                 {
1443                     return result;
1444                 }
1445             }
1446             else
1447             {
1448                 pa = &((*pa)->next);
1449             }
1450         }
1451         while (b)
1452         {
1453             Action::LeftEmpty(this, pa, b, result, terminate);
1454             if (terminate)
1455             {
1456                 return result;
1457             }
1458         }
1459     }
1460     assert(this->numNodes == this->getNodeCount());
1461     return result;
1462 }
1463
1464 // LHSBigger and RHSBigger algorithms both work for equal
1465 // this is a specialized version of RHSBigger which is simpler (and faster)
1466 // because equal sizes are the 99% case
1467 template <typename Action>
1468 bool hashBv::MultiTraverseEqual(hashBv* other)
1469 {
1470     int hts = this->hashtable_size();
1471     assert(other->hashtable_size() == hts);
1472
1473     bool result    = Action::DefaultResult();
1474     bool terminate = false;
1475
1476     for (int hashNum = 0; hashNum < hts; hashNum++)
1477     {
1478         int destination = getHashForIndex(BITS_PER_NODE * hashNum, this->hashtable_size());
1479
1480         hashBvNode** pa = &this->nodeArr[hashNum];
1481         hashBvNode** pb = &other->nodeArr[hashNum];
1482         hashBvNode*  b  = *pb;
1483
1484         while (*pa && b)
1485         {
1486             hashBvNode* a = *pa;
1487             if (a->baseIndex < b->baseIndex)
1488             {
1489                 // in a but not in b
1490                 Action::RightGap(this, pa, b, result, terminate);
1491                 if (terminate)
1492                 {
1493                     return result;
1494                 }
1495             }
1496             else if (a->baseIndex == b->baseIndex)
1497             {
1498                 Action::BothPresent(this, pa, b, result, terminate);
1499                 if (terminate)
1500                 {
1501                     return result;
1502                 }
1503             }
1504             else if (a->baseIndex > b->baseIndex)
1505             {
1506                 // other contains something this does not
1507                 Action::LeftGap(this, pa, b, result, terminate);
1508                 if (terminate)
1509                 {
1510                     return result;
1511                 }
1512             }
1513         }
1514         while (*pa)
1515         {
1516             // if it's in the dest but not in src
1517             Action::RightGap(this, pa, b, result, terminate);
1518             if (terminate)
1519             {
1520                 return result;
1521             }
1522         }
1523         while (b)
1524         {
1525             Action::LeftEmpty(this, pa, b, result, terminate);
1526             if (terminate)
1527             {
1528                 return result;
1529             }
1530         }
1531     }
1532     assert(this->numNodes == this->getNodeCount());
1533     return result;
1534 }
1535
1536 template <class Action>
1537 bool hashBv::MultiTraverse(hashBv* other)
1538 {
1539     bool result = false;
1540
1541     assert(this->numNodes == this->getNodeCount());
1542
1543     Action::PreAction(this, other);
1544
1545     int hts = this->log2_hashSize;
1546     int ots = other->log2_hashSize;
1547
1548     if (hts == ots)
1549     {
1550         return MultiTraverseEqual<Action>(other);
1551     }
1552     else if (hts > ots)
1553     {
1554         return MultiTraverseLHSBigger<Action>(other);
1555     }
1556     else
1557     {
1558         return MultiTraverseRHSBigger<Action>(other);
1559     }
1560 }
1561
1562 bool hashBv::Intersects(hashBv* other)
1563 {
1564     return MultiTraverse<IntersectsAction>(other);
1565 }
1566
1567 bool hashBv::AndWithChange(hashBv* other)
1568 {
1569     return MultiTraverse<AndAction>(other);
1570 }
1571
1572 // same as AND ~x
1573 bool hashBv::SubtractWithChange(hashBv* other)
1574 {
1575     return MultiTraverse<SubtractAction>(other);
1576 }
1577
1578 void hashBv::Subtract(hashBv* other)
1579 {
1580     this->SubtractWithChange(other);
1581 }
1582
1583 void hashBv::Subtract3(hashBv* o1, hashBv* o2)
1584 {
1585     this->copyFrom(o1, compiler);
1586     this->Subtract(o2);
1587 }
1588
1589 void hashBv::UnionMinus(hashBv* src1, hashBv* src2, hashBv* src3)
1590 {
1591     this->Subtract3(src1, src2);
1592     this->OrWithChange(src3);
1593 }
1594
1595 void hashBv::ZeroAll()
1596 {
1597     int hts = this->hashtable_size();
1598
1599     for (int hashNum = 0; hashNum < hts; hashNum++)
1600     {
1601         while (nodeArr[hashNum])
1602         {
1603             hashBvNode* n    = nodeArr[hashNum];
1604             nodeArr[hashNum] = n->next;
1605             n->freeNode(globalData());
1606         }
1607     }
1608     this->numNodes = 0;
1609 }
1610
1611 bool hashBv::OrWithChange(hashBv* other)
1612 {
1613     return MultiTraverse<OrAction>(other);
1614 }
1615
1616 bool hashBv::XorWithChange(hashBv* other)
1617 {
1618     return MultiTraverse<XorAction>(other);
1619 }
1620 void hashBv::OrWith(hashBv* other)
1621 {
1622     this->OrWithChange(other);
1623 }
1624
1625 void hashBv::AndWith(hashBv* other)
1626 {
1627     this->AndWithChange(other);
1628 }
1629
1630 bool hashBv::CompareWith(hashBv* other)
1631 {
1632     return MultiTraverse<CompareAction>(other);
1633 }
1634
1635 void hashBv::copyFrom(hashBv* other, Compiler* comp)
1636 {
1637     assert(this != other);
1638
1639     hashBvNode* freeList = nullptr;
1640
1641     this->ZeroAll();
1642
1643     if (this->log2_hashSize != other->log2_hashSize)
1644     {
1645         this->nodeArr       = this->getNewVector(other->hashtable_size());
1646         this->log2_hashSize = other->log2_hashSize;
1647         assert(this->hashtable_size() == other->hashtable_size());
1648     }
1649
1650     int hts = this->hashtable_size();
1651     // printf("in copyfrom\n");
1652     for (int h = 0; h < hts; h++)
1653     {
1654         // put the current list on the free list
1655         freeList         = this->nodeArr[h];
1656         this->nodeArr[h] = nullptr;
1657
1658         hashBvNode** splicePoint = &(this->nodeArr[h]);
1659         hashBvNode*  otherNode   = other->nodeArr[h];
1660         hashBvNode*  newNode     = nullptr;
1661
1662         while (otherNode)
1663         {
1664             // printf("otherNode is True...\n");
1665             hashBvNode* next = *splicePoint;
1666
1667             this->numNodes++;
1668
1669             if (freeList)
1670             {
1671                 newNode  = freeList;
1672                 freeList = freeList->next;
1673                 newNode->Reconstruct(otherNode->baseIndex);
1674             }
1675             else
1676             {
1677                 newNode = hashBvNode::Create(otherNode->baseIndex, this->compiler);
1678             }
1679             newNode->copyFrom(otherNode);
1680
1681             newNode->next = *splicePoint;
1682             *splicePoint  = newNode;
1683             splicePoint   = &(newNode->next);
1684
1685             otherNode = otherNode->next;
1686         }
1687     }
1688     while (freeList)
1689     {
1690         hashBvNode* next = freeList->next;
1691         freeList->freeNode(globalData());
1692         freeList = next;
1693     }
1694 #if 0
1695     for (int h=0; h<hashtable_size(); h++)
1696     {
1697         printf("%p %p\n", this->nodeArr[h], other->nodeArr[h]);
1698     }
1699 #endif
1700 }
1701
1702 int nodeSort(const void* x, const void* y)
1703 {
1704     hashBvNode* a = (hashBvNode*)x;
1705     hashBvNode* b = (hashBvNode*)y;
1706     return (int)(b->baseIndex - a->baseIndex);
1707 }
1708
1709 void hashBv::InorderTraverse(nodeAction n)
1710 {
1711     int hts = hashtable_size();
1712
1713     hashBvNode** x = new (compiler, CMK_hashBv) hashBvNode*[hts];
1714
1715     {
1716         // keep an array of the current pointers
1717         // into each of the the bitvector lists
1718         // in the hashtable
1719         for (int i = 0; i < hts; i++)
1720         {
1721             x[i] = nodeArr[i];
1722         }
1723
1724         while (1)
1725         {
1726             // pick the lowest node in the hashtable
1727
1728             indexType lowest       = INT_MAX;
1729             int       lowest_index = -1;
1730             for (int i = 0; i < hts; i++)
1731             {
1732                 if (x[i] && x[i]->baseIndex < lowest)
1733                 {
1734                     lowest       = x[i]->baseIndex;
1735                     lowest_index = i;
1736                 }
1737             }
1738             // if there was anything left, use it and update
1739             // the list pointers otherwise we are done
1740             if (lowest_index != -1)
1741             {
1742                 n(x[lowest_index]);
1743                 x[lowest_index] = x[lowest_index]->next;
1744             }
1745             else
1746             {
1747                 break;
1748             }
1749         }
1750     }
1751
1752     delete[] x;
1753 }
1754
1755 void hashBv::InorderTraverseTwo(hashBv* other, dualNodeAction a)
1756 {
1757     int          sizeThis, sizeOther;
1758     hashBvNode **nodesThis, **nodesOther;
1759
1760     sizeThis  = this->hashtable_size();
1761     sizeOther = other->hashtable_size();
1762
1763     nodesThis  = new (compiler, CMK_hashBv) hashBvNode*[sizeThis];
1764     nodesOther = new (compiler, CMK_hashBv) hashBvNode*[sizeOther];
1765
1766     // populate the arrays
1767     for (int i = 0; i < sizeThis; i++)
1768     {
1769         nodesThis[i] = this->nodeArr[i];
1770     }
1771
1772     for (int i = 0; i < sizeOther; i++)
1773     {
1774         nodesOther[i] = other->nodeArr[i];
1775     }
1776
1777     while (1)
1778     {
1779         indexType lowestThis           = INT_MAX;
1780         indexType lowestOther          = INT_MAX;
1781         int       lowestHashIndexThis  = -1;
1782         int       lowestHashIndexOther = -1;
1783
1784         // find the lowest remaining node in each BV
1785         for (int i = 0; i < sizeThis; i++)
1786         {
1787             if (nodesThis[i] && nodesThis[i]->baseIndex < lowestThis)
1788             {
1789                 lowestHashIndexThis = i;
1790                 lowestThis          = nodesThis[i]->baseIndex;
1791             }
1792         }
1793         for (int i = 0; i < sizeOther; i++)
1794         {
1795             if (nodesOther[i] && nodesOther[i]->baseIndex < lowestOther)
1796             {
1797                 lowestHashIndexOther = i;
1798                 lowestOther          = nodesOther[i]->baseIndex;
1799             }
1800         }
1801         hashBvNode *nodeThis, *nodeOther;
1802         nodeThis  = lowestHashIndexThis == -1 ? nullptr : nodesThis[lowestHashIndexThis];
1803         nodeOther = lowestHashIndexOther == -1 ? nullptr : nodesOther[lowestHashIndexOther];
1804         // no nodes left in either, so return
1805         if ((!nodeThis) && (!nodeOther))
1806         {
1807             break;
1808
1809             // there are only nodes left in one bitvector
1810         }
1811         else if ((!nodeThis) || (!nodeOther))
1812         {
1813             a(this, other, nodeThis, nodeOther);
1814             if (nodeThis)
1815             {
1816                 nodesThis[lowestHashIndexThis] = nodesThis[lowestHashIndexThis]->next;
1817             }
1818             if (nodeOther)
1819             {
1820                 nodesOther[lowestHashIndexOther] = nodesOther[lowestHashIndexOther]->next;
1821             }
1822         }
1823         // nodes are left in both so determine if the lowest ones
1824         // match.  if so process them in a pair.  if not then
1825         // process the lower of the two alone
1826         else if (nodeThis && nodeOther)
1827         {
1828             if (nodeThis->baseIndex == nodeOther->baseIndex)
1829             {
1830                 a(this, other, nodeThis, nodeOther);
1831                 nodesThis[lowestHashIndexThis]   = nodesThis[lowestHashIndexThis]->next;
1832                 nodesOther[lowestHashIndexOther] = nodesOther[lowestHashIndexOther]->next;
1833             }
1834             else if (nodeThis->baseIndex < nodeOther->baseIndex)
1835             {
1836                 a(this, other, nodeThis, nullptr);
1837                 nodesThis[lowestHashIndexThis] = nodesThis[lowestHashIndexThis]->next;
1838             }
1839             else if (nodeOther->baseIndex < nodeThis->baseIndex)
1840             {
1841                 a(this, other, nullptr, nodeOther);
1842                 nodesOther[lowestHashIndexOther] = nodesOther[lowestHashIndexOther]->next;
1843             }
1844         }
1845     }
1846     delete[] nodesThis;
1847     delete[] nodesOther;
1848 }
1849
1850 // --------------------------------------------------------------------
1851 // --------------------------------------------------------------------
1852
1853 #ifdef DEBUG
1854 void SimpleDumpNode(hashBvNode* n)
1855 {
1856     printf("base: %d\n", n->baseIndex);
1857 }
1858
1859 void DumpNode(hashBvNode* n)
1860 {
1861     n->dump();
1862 }
1863
1864 void SimpleDumpDualNode(hashBv* a, hashBv* b, hashBvNode* n, hashBvNode* m)
1865 {
1866     printf("nodes: ");
1867     if (n)
1868     {
1869         printf("%d,", n->baseIndex);
1870     }
1871     else
1872     {
1873         printf("----,");
1874     }
1875     if (m)
1876     {
1877         printf("%d\n", m->baseIndex);
1878     }
1879     else
1880     {
1881         printf("----\n");
1882     }
1883 }
1884 #endif // DEBUG
1885
1886 hashBvIterator::hashBvIterator()
1887 {
1888     this->bv = nullptr;
1889 }
1890
1891 hashBvIterator::hashBvIterator(hashBv* bv)
1892 {
1893     this->bv              = bv;
1894     this->hashtable_index = 0;
1895     this->current_element = 0;
1896     this->current_base    = 0;
1897     this->current_data    = 0;
1898
1899     if (bv)
1900     {
1901         this->hashtable_size = bv->hashtable_size();
1902         this->currNode       = bv->nodeArr[0];
1903
1904         if (!this->currNode)
1905         {
1906             this->nextNode();
1907         }
1908     }
1909 }
1910
1911 void hashBvIterator::initFrom(hashBv* bv)
1912 {
1913     this->bv              = bv;
1914     this->hashtable_size  = bv->hashtable_size();
1915     this->hashtable_index = 0;
1916     this->currNode        = bv->nodeArr[0];
1917     this->current_element = 0;
1918     this->current_base    = 0;
1919     this->current_data    = 0;
1920
1921     if (!this->currNode)
1922     {
1923         this->nextNode();
1924     }
1925     if (this->currNode)
1926     {
1927         this->current_data = this->currNode->elements[0];
1928     }
1929 }
1930
1931 void hashBvIterator::nextNode()
1932 {
1933     // if we have a valid node then just get the next one in the chain
1934     if (this->currNode)
1935     {
1936         this->currNode = this->currNode->next;
1937     }
1938
1939     // else step to the next one in the hash table
1940     while (!this->currNode)
1941     {
1942         hashtable_index++;
1943         // no more
1944         if (hashtable_index >= hashtable_size)
1945         {
1946             // printf("nextnode bailed\n");
1947             return;
1948         }
1949
1950         this->currNode = bv->nodeArr[hashtable_index];
1951     }
1952     // first element in the new node
1953     this->current_element = 0;
1954     this->current_base    = this->currNode->baseIndex;
1955     this->current_data    = this->currNode->elements[0];
1956     // printf("nextnode returned base %d\n", this->current_base);
1957     // printf("hti = %d ", hashtable_index);
1958 }
1959
1960 indexType hashBvIterator::nextBit()
1961 {
1962
1963     // printf("in nextbit for bv:\n");
1964     // this->bv->dump();
1965
1966     if (!this->currNode)
1967     {
1968         this->nextNode();
1969     }
1970
1971 top:
1972
1973     if (!this->currNode)
1974     {
1975         return NOMOREBITS;
1976     }
1977
1978 more_data:
1979     if (!this->current_data)
1980     {
1981         current_element++;
1982         // printf("current element is %d\n", current_element);
1983         // reached the end of this node
1984         if (current_element == (indexType) this->currNode->numElements())
1985         {
1986             // printf("going to next node\n");
1987             this->nextNode();
1988             goto top;
1989         }
1990         else
1991         {
1992             assert(current_element < (indexType) this->currNode->numElements());
1993             // printf("getting more data\n");
1994             current_data = this->currNode->elements[current_element];
1995             current_base = this->currNode->baseIndex + current_element * BITS_PER_ELEMENT;
1996             goto more_data;
1997         }
1998     }
1999     else
2000     {
2001         while (current_data)
2002         {
2003             if (current_data & 1)
2004             {
2005                 current_data >>= 1;
2006                 current_base++;
2007
2008                 return current_base - 1;
2009             }
2010             else
2011             {
2012                 current_data >>= 1;
2013                 current_base++;
2014             }
2015         }
2016         goto more_data;
2017     }
2018 }
2019
2020 indexType HbvNext(hashBv* bv, Compiler* comp)
2021 {
2022     if (bv)
2023     {
2024         bv->globalData()->hashBvNextIterator.initFrom(bv);
2025     }
2026     return bv->globalData()->hashBvNextIterator.nextBit();
2027 }