diff options
Diffstat (limited to 'src/jit/hashbv.cpp')
-rw-r--r-- | src/jit/hashbv.cpp | 2028 |
1 files changed, 2028 insertions, 0 deletions
diff --git a/src/jit/hashbv.cpp b/src/jit/hashbv.cpp new file mode 100644 index 0000000000..fa06ec7b1e --- /dev/null +++ b/src/jit/hashbv.cpp @@ -0,0 +1,2028 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +#include "jitpch.h" +#ifdef _MSC_VER +#pragma hdrstop +#endif + +// -------------------------------------------------------------------- +// -------------------------------------------------------------------- + +#ifdef DEBUG +void hashBvNode::dump() +{ + printf("base: %d { ", baseIndex); + this->foreachBit(pBit); + printf("}\n"); +} +#endif // DEBUG + +void hashBvNode::Reconstruct(indexType base) +{ + baseIndex = base; + + assert(!(baseIndex % BITS_PER_NODE)); + + for (int i = 0; i < this->numElements(); i++) + { + elements[i] = 0; + } + next = nullptr; +} + +hashBvNode::hashBvNode(indexType base) +{ + this->Reconstruct(base); +} + +hashBvNode* hashBvNode::Create(indexType base, Compiler* compiler) +{ + hashBvNode* result = nullptr; + + if (compiler->hbvGlobalData.hbvNodeFreeList) + { + result = compiler->hbvGlobalData.hbvNodeFreeList; + compiler->hbvGlobalData.hbvNodeFreeList = result->next; + } + else + { + result = new (compiler, CMK_hashBv) hashBvNode; + } + result->Reconstruct(base); + return result; +} + +void hashBvNode::freeNode(hashBvGlobalData* glob) +{ + this->next = glob->hbvNodeFreeList; + glob->hbvNodeFreeList = this; +} + +void hashBvNode::setBit(indexType base) +{ + assert(base >= baseIndex); + assert(base - baseIndex < BITS_PER_NODE); + + base -= baseIndex; + indexType elem = base / BITS_PER_ELEMENT; + indexType posi = base % BITS_PER_ELEMENT; + + elements[elem] |= indexType(1) << posi; +} + +void hashBvNode::setLowest(indexType numToSet) +{ + assert(numToSet <= BITS_PER_NODE); + + int elemIndex = 0; + while (numToSet > BITS_PER_ELEMENT) + { + elements[elemIndex] = ~(elemType(0)); + numToSet -= BITS_PER_ELEMENT; + elemIndex++; + } + if (numToSet) + { + elemType allOnes = ~(elemType(0)); + int numToShift = (int)(BITS_PER_ELEMENT - numToSet); + elements[elemIndex] = allOnes >> numToShift; + } +} + +void hashBvNode::clrBit(indexType base) +{ + assert(base >= baseIndex); + assert(base - baseIndex < BITS_PER_NODE); + + base -= baseIndex; + indexType elem = base / BITS_PER_ELEMENT; + indexType posi = base % BITS_PER_ELEMENT; + + elements[elem] &= ~(indexType(1) << posi); +} + +bool hashBvNode::belongsIn(indexType index) +{ + if (index < baseIndex) + { + return false; + } + if (index >= baseIndex + BITS_PER_NODE) + { + return false; + } + return true; +} + +int countBitsInWord(unsigned int bits) +{ + // In-place adder tree: perform 16 1-bit adds, 8 2-bit adds, + // 4 4-bit adds, 2 8=bit adds, and 1 16-bit add. + bits = ((bits >> 1) & 0x55555555) + (bits & 0x55555555); + bits = ((bits >> 2) & 0x33333333) + (bits & 0x33333333); + bits = ((bits >> 4) & 0x0F0F0F0F) + (bits & 0x0F0F0F0F); + bits = ((bits >> 8) & 0x00FF00FF) + (bits & 0x00FF00FF); + bits = ((bits >> 16) & 0x0000FFFF) + (bits & 0x0000FFFF); + return (int)bits; +} + +int countBitsInWord(unsigned __int64 bits) +{ + bits = ((bits >> 1) & 0x5555555555555555) + (bits & 0x5555555555555555); + bits = ((bits >> 2) & 0x3333333333333333) + (bits & 0x3333333333333333); + bits = ((bits >> 4) & 0x0F0F0F0F0F0F0F0F) + (bits & 0x0F0F0F0F0F0F0F0F); + bits = ((bits >> 8) & 0x00FF00FF00FF00FF) + (bits & 0x00FF00FF00FF00FF); + bits = ((bits >> 16) & 0x0000FFFF0000FFFF) + (bits & 0x0000FFFF0000FFFF); + bits = ((bits >> 32) & 0x00000000FFFFFFFF) + (bits & 0x00000000FFFFFFFF); + return (int)bits; +} + +int hashBvNode::countBits() +{ + int result = 0; + + for (int i = 0; i < this->numElements(); i++) + { + elemType bits = elements[i]; + + result += countBitsInWord(bits); + + result += (int)bits; + } + return result; +} + +bool hashBvNode::anyBits() +{ + for (int i = 0; i < this->numElements(); i++) + { + if (elements[i]) + { + return true; + } + } + return false; +} + +bool hashBvNode::getBit(indexType base) +{ + assert(base >= baseIndex); + assert(base - baseIndex < BITS_PER_NODE); + base -= baseIndex; + + indexType elem = base / BITS_PER_ELEMENT; + indexType posi = base % BITS_PER_ELEMENT; + + if (elements[elem] & (indexType(1) << posi)) + { + return true; + } + else + { + return false; + } +} + +bool hashBvNode::anySet() +{ + for (int i = 0; i < this->numElements(); i++) + { + if (elements[i]) + { + return true; + } + } + return false; +} + +void hashBvNode::copyFrom(hashBvNode* other) +{ + this->baseIndex = other->baseIndex; + for (int i = 0; i < this->numElements(); i++) + { + this->elements[i] = other->elements[i]; + } +} + +void hashBvNode::foreachBit(bitAction a) +{ + indexType base; + for (int i = 0; i < this->numElements(); i++) + { + base = baseIndex + i * BITS_PER_ELEMENT; + elemType e = elements[i]; + while (e) + { + if (e & 1) + { + a(base); + } + e >>= 1; + base++; + } + } +} + +elemType hashBvNode::AndWithChange(hashBvNode* other) +{ + elemType result = 0; + + for (int i = 0; i < this->numElements(); i++) + { + elemType src = this->elements[i]; + elemType dst; + + dst = src & other->elements[i]; + result |= src ^ dst; + this->elements[i] = dst; + } + return result; +} + +elemType hashBvNode::OrWithChange(hashBvNode* other) +{ + elemType result = 0; + + for (int i = 0; i < this->numElements(); i++) + { + elemType src = this->elements[i]; + elemType dst; + + dst = src | other->elements[i]; + result |= src ^ dst; + this->elements[i] = dst; + } + return result; +} + +elemType hashBvNode::XorWithChange(hashBvNode* other) +{ + elemType result = 0; + + for (int i = 0; i < this->numElements(); i++) + { + elemType src = this->elements[i]; + elemType dst; + + dst = src ^ other->elements[i]; + result |= src ^ dst; + this->elements[i] = dst; + } + return result; +} + +elemType hashBvNode::SubtractWithChange(hashBvNode* other) +{ + elemType result = 0; + + for (int i = 0; i < this->numElements(); i++) + { + elemType src = this->elements[i]; + elemType dst; + + dst = src & ~other->elements[i]; + result |= src ^ dst; + this->elements[i] = dst; + } + return result; +} + +bool hashBvNode::Intersects(hashBvNode* other) +{ + for (int i = 0; i < this->numElements(); i++) + { + if ((this->elements[i] & other->elements[i]) != 0) + { + return true; + } + } + + return false; +} + +void hashBvNode::AndWith(hashBvNode* other) +{ + for (int i = 0; i < this->numElements(); i++) + { + this->elements[i] &= other->elements[i]; + } +} + +void hashBvNode::OrWith(hashBvNode* other) +{ + for (int i = 0; i < this->numElements(); i++) + { + this->elements[i] |= other->elements[i]; + } +} + +void hashBvNode::XorWith(hashBvNode* other) +{ + for (int i = 0; i < this->numElements(); i++) + { + this->elements[i] ^= other->elements[i]; + } +} + +void hashBvNode::Subtract(hashBvNode* other) +{ + for (int i = 0; i < this->numElements(); i++) + { + this->elements[i] &= ~other->elements[i]; + } +} + +bool hashBvNode::sameAs(hashBvNode* other) +{ + if (this->baseIndex != other->baseIndex) + { + return false; + } + + for (int i = 0; i < this->numElements(); i++) + { + if (this->elements[i] != other->elements[i]) + { + return false; + } + } + + return true; +} + +// -------------------------------------------------------------------- +// -------------------------------------------------------------------- + +hashBv::hashBv(Compiler* comp) +{ + this->compiler = comp; + this->log2_hashSize = globalData()->hbvHashSizeLog2; + + int hts = hashtable_size(); + nodeArr = getNewVector(hts); + + for (int i = 0; i < hts; i++) + { + nodeArr[i] = nullptr; + } + this->numNodes = 0; +} + +hashBv* hashBv::Create(Compiler* compiler) +{ + hashBv* result; + hashBvGlobalData* gd = &compiler->hbvGlobalData; + + if (hbvFreeList(gd)) + { + result = hbvFreeList(gd); + hbvFreeList(gd) = result->next; + assert(result->nodeArr); + } + else + { + result = new (compiler, CMK_hashBv) hashBv(compiler); + memset(result, 0, sizeof(hashBv)); + result->nodeArr = result->initialVector; + } + + result->compiler = compiler; + result->log2_hashSize = 0; + result->numNodes = 0; + + return result; +} + +void hashBv::Init(Compiler* compiler) +{ + memset(&compiler->hbvGlobalData, 0, sizeof(hashBvGlobalData)); +} + +hashBvGlobalData* hashBv::globalData() +{ + return &compiler->hbvGlobalData; +} + +hashBvNode** hashBv::getNewVector(int vectorLength) +{ + assert(vectorLength > 0); + assert(isPow2(vectorLength)); + + hashBvNode** newVector = new (compiler, CMK_hashBv) hashBvNode*[vectorLength](); + return newVector; +} + +hashBvNode*& hashBv::nodeFreeList(hashBvGlobalData* data) +{ + return data->hbvNodeFreeList; +} + +hashBv*& hashBv::hbvFreeList(hashBvGlobalData* data) +{ + return data->hbvFreeList; +} + +void hashBv::freeVector(hashBvNode* vect, int vectorLength) +{ + // not enough space to do anything with it + if (vectorLength < 2) + { + return; + } + + hbvFreeListNode* f = (hbvFreeListNode*)vect; + f->next = globalData()->hbvFreeVectorList; + globalData()->hbvFreeVectorList = f; + f->size = vectorLength; +} + +void hashBv::hbvFree() +{ + Compiler* comp = this->compiler; + + int hts = hashtable_size(); + for (int i = 0; i < hts; i++) + { + while (nodeArr[i]) + { + hashBvNode* curr = nodeArr[i]; + nodeArr[i] = curr->next; + curr->freeNode(globalData()); + } + } + // keep the vector attached because the whole thing is freelisted + // plus you don't even know if it's freeable + + this->next = hbvFreeList(globalData()); + hbvFreeList(globalData()) = this; +} + +hashBv* hashBv::CreateFrom(hashBv* other, Compiler* comp) +{ + hashBv* result = hashBv::Create(comp); + result->copyFrom(other, comp); + return result; +} + +void hashBv::MergeLists(hashBvNode** root1, hashBvNode** root2) +{ +} + +bool hashBv::TooSmall() +{ + return this->numNodes > this->hashtable_size() * 4; +} + +bool hashBv::TooBig() +{ + return this->hashtable_size() > this->numNodes * 4; +} + +int hashBv::getNodeCount() +{ + int size = hashtable_size(); + int result = 0; + + for (int i = 0; i < size; i++) + { + hashBvNode* last = nodeArr[i]; + + while (last) + { + last = last->next; + result++; + } + } + return result; +} + +bool hashBv::IsValid() +{ + int size = hashtable_size(); + // is power of 2 + assert(((size - 1) & size) == 0); + + for (int i = 0; i < size; i++) + { + hashBvNode* last = nodeArr[i]; + hashBvNode* curr; + int lastIndex = -1; + + while (last) + { + // the node has been hashed correctly + assert((int)last->baseIndex > lastIndex); + lastIndex = (int)last->baseIndex; + assert(i == getHashForIndex(last->baseIndex, size)); + curr = last->next; + // the order is monotonically increasing bases + if (curr) + { + assert(curr->baseIndex > last->baseIndex); + } + last = curr; + } + } + return true; +} + +void hashBv::Resize() +{ + // resize to 'optimal' size + + this->Resize(this->numNodes); +} + +void hashBv::Resize(int newSize) +{ + assert(newSize > 0); + newSize = nearest_pow2(newSize); + + int oldSize = hashtable_size(); + + if (newSize == oldSize) + { + return; + } + + int oldSizeLog2 = log2_hashSize; + int log2_newSize = genLog2((unsigned)newSize); + int size; + + hashBvNode** newNodes = this->getNewVector(newSize); + + hashBvNode*** insertionPoints = (hashBvNode***)alloca(sizeof(hashBvNode*) * newSize); + memset(insertionPoints, 0, sizeof(hashBvNode*) * newSize); + + for (int i = 0; i < newSize; i++) + { + insertionPoints[i] = &(newNodes[i]); + } + + if (newSize > oldSize) + { + // for each src list, expand it into multiple dst lists + for (int i = 0; i < oldSize; i++) + { + hashBvNode* next = nodeArr[i]; + + while (next) + { + hashBvNode* curr = next; + next = curr->next; + int destination = getHashForIndex(curr->baseIndex, newSize); + + // ... + + // stick the current node on the end of the selected list + *(insertionPoints[destination]) = curr; + insertionPoints[destination] = &(curr->next); + curr->next = nullptr; + } + } + nodeArr = newNodes; + log2_hashSize = (unsigned short)log2_newSize; + } + else if (oldSize > newSize) + { + int shrinkFactor = oldSize / newSize; + + // shrink multiple lists into one list + // more efficient ways to do this but... + // if the lists are long, you shouldn't be shrinking. + for (int i = 0; i < oldSize; i++) + { + hashBvNode* next = nodeArr[i]; + + if (next) + { + // all nodes in this list should have the same destination list + int destination = getHashForIndex(next->baseIndex, newSize); + hashBvNode** insertionPoint = &newNodes[destination]; + do + { + hashBvNode* curr = next; + // figure out where to insert it + while (*insertionPoint && (*insertionPoint)->baseIndex < curr->baseIndex) + { + insertionPoint = &((*insertionPoint)->next); + } + next = curr->next; + + hashBvNode* temp = *insertionPoint; + *insertionPoint = curr; + curr->next = temp; + + } while (next); + } + } + nodeArr = newNodes; + log2_hashSize = (unsigned short)log2_newSize; + } + else + { + // same size + assert(oldSize == newSize); + } + assert(this->IsValid()); +} + +#ifdef DEBUG +void hashBv::dump() +{ + bool first = true; + indexType index; + + // uncomment to print internal implementation details + // DBEXEC(TRUE, printf("[%d(%d)(nodes:%d)]{ ", hashtable_size(), countBits(), this->numNodes)); + + printf("{"); + FOREACH_HBV_BIT_SET(index, this) + { + if (!first) + { + printf(" "); + } + printf("%d", index); + first = false; + } + NEXT_HBV_BIT_SET; + printf("}\n"); +} + +void hashBv::dumpFancy() +{ + indexType index; + indexType last_1 = -1; + indexType last_0 = -1; + + printf("{"); + printf("count:%d", this->countBits()); + FOREACH_HBV_BIT_SET(index, this) + { + if (last_1 != index - 1) + { + if (last_0 + 1 != last_1) + { + printf(" %d-%d", last_0 + 1, last_1); + } + else + { + printf(" %d", last_1); + } + last_0 = index - 1; + } + last_1 = index; + } + NEXT_HBV_BIT_SET; + + // Print the last one + if (last_0 + 1 != last_1) + { + printf(" %d-%d", last_0 + 1, last_1); + } + else + { + printf(" %d", last_1); + } + + printf("}\n"); +} +#endif // DEBUG + +void hashBv::removeNodeAtBase(indexType index) +{ + hashBvNode** insertionPoint = this->getInsertionPointForIndex(index); + + hashBvNode* node = *insertionPoint; + + // make sure that we were called to remove something + // that really was there + assert(node); + + // splice it out + *insertionPoint = node->next; + this->numNodes--; +} + +int hashBv::getHashForIndex(indexType index, int table_size) +{ + indexType hashIndex; + + hashIndex = index >> LOG2_BITS_PER_NODE; + hashIndex &= (table_size - 1); + + return (int)hashIndex; +} + +int hashBv::getRehashForIndex(indexType thisIndex, int thisTableSize, int newTableSize) +{ + assert(0); + return 0; +} + +hashBvNode** hashBv::getInsertionPointForIndex(indexType index) +{ + indexType indexInNode; + indexType hashIndex; + indexType baseIndex; + + hashBvNode* result; + + hashIndex = getHashForIndex(index, hashtable_size()); + + baseIndex = index & ~(BITS_PER_NODE - 1); + indexInNode = index & (BITS_PER_NODE - 1); + + // printf("(%x) : hsh=%x, base=%x, index=%x\n", index, + // hashIndex, baseIndex, indexInNode); + + // find the node + hashBvNode** prev = &nodeArr[hashIndex]; + result = nodeArr[hashIndex]; + + while (result) + { + if (result->baseIndex == baseIndex) + { + return prev; + } + else if (result->baseIndex > baseIndex) + { + return prev; + } + else + { + prev = &(result->next); + result = result->next; + } + } + return prev; +} + +hashBvNode* hashBv::getNodeForIndexHelper(indexType index, bool canAdd) +{ + // determine the base index of the node containing this index + index = index & ~(BITS_PER_NODE - 1); + + hashBvNode** prev = getInsertionPointForIndex(index); + + hashBvNode* node = *prev; + + if (node && node->belongsIn(index)) + { + return node; + } + else if (canAdd) + { + // missing node, insert it before the current one + hashBvNode* temp = hashBvNode::Create(index, this->compiler); + temp->next = node; + *prev = temp; + this->numNodes++; + return temp; + } + else + { + return nullptr; + } +} + +hashBvNode* hashBv::getNodeForIndex(indexType index) +{ + // determine the base index of the node containing this index + index = index & ~(BITS_PER_NODE - 1); + + hashBvNode** prev = getInsertionPointForIndex(index); + + hashBvNode* node = *prev; + + if (node && node->belongsIn(index)) + { + return node; + } + else + { + return nullptr; + } +} + +void hashBv::setBit(indexType index) +{ + assert(index >= 0); + assert(this->numNodes == this->getNodeCount()); + hashBvNode* result = nullptr; + + indexType baseIndex = index & ~(BITS_PER_NODE - 1); + indexType base = index - baseIndex; + indexType elem = base / BITS_PER_ELEMENT; + indexType posi = base % BITS_PER_ELEMENT; + + // this should be the 99% case : when there is only one node in the structure + if ((result = nodeArr[0]) && result->baseIndex == baseIndex) + { + result->elements[elem] |= indexType(1) << posi; + return; + } + + result = getOrAddNodeForIndex(index); + result->setBit(index); + + assert(this->numNodes == this->getNodeCount()); + + // if it's getting out of control resize it + if (this->numNodes > this->hashtable_size() * 4) + { + this->Resize(); + } + + return; +} + +void hashBv::setAll(indexType numToSet) +{ + // TODO-Throughput: this could be more efficient + for (unsigned int i = 0; i < numToSet; i += BITS_PER_NODE) + { + hashBvNode* node = getOrAddNodeForIndex(i); + indexType bits_to_set = min(BITS_PER_NODE, numToSet - i); + node->setLowest(bits_to_set); + } +} + +void hashBv::clearBit(indexType index) +{ + assert(index >= 0); + assert(this->numNodes == this->getNodeCount()); + hashBvNode* result = nullptr; + + indexType baseIndex = index & ~(BITS_PER_NODE - 1); + indexType hashIndex = getHashForIndex(index, hashtable_size()); + + hashBvNode** prev = &nodeArr[hashIndex]; + result = nodeArr[hashIndex]; + + while (result) + { + if (result->baseIndex == baseIndex) + { + result->clrBit(index); + // if nothing left set free it + if (!result->anySet()) + { + *prev = result->next; + result->freeNode(globalData()); + this->numNodes--; + } + return; + } + else if (result->baseIndex > baseIndex) + { + return; + } + else + { + prev = &(result->next); + result = result->next; + } + } + assert(this->numNodes == this->getNodeCount()); + return; +} + +bool hashBv::testBit(indexType index) +{ + // determine the base index of the node containing this index + indexType baseIndex = index & ~(BITS_PER_NODE - 1); + // 99% case + if (nodeArr[0] && nodeArr[0]->baseIndex == baseIndex) + { + return nodeArr[0]->getBit(index); + } + + indexType hashIndex = getHashForIndex(baseIndex, hashtable_size()); + + hashBvNode* iter = nodeArr[hashIndex]; + + while (iter) + { + if (iter->baseIndex == baseIndex) + { + return iter->getBit(index); + } + else + { + iter = iter->next; + } + } + return false; +} + +int hashBv::countBits() +{ + int result = 0; + int hts = this->hashtable_size(); + for (int hashNum = 0; hashNum < hts; hashNum++) + { + hashBvNode* node = nodeArr[hashNum]; + while (node) + { + result += node->countBits(); + node = node->next; + } + } + return result; +} + +bool hashBv::anySet() +{ + int result = 0; + + int hts = this->hashtable_size(); + for (int hashNum = 0; hashNum < hts; hashNum++) + { + hashBvNode* node = nodeArr[hashNum]; + while (node) + { + if (node->anySet()) + { + return true; + } + node = node->next; + } + } + return false; +} + +class AndAction +{ +public: + static inline void PreAction(hashBv* lhs, hashBv* rhs) + { + } + static inline void PostAction(hashBv* lhs, hashBv* rhs) + { + } + static inline bool DefaultResult() + { + return false; + } + + static inline void LeftGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + // it's in other, not this + // so skip it + r = r->next; + } + static inline void RightGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + // it's in LHS, not RHS + // so have to remove it + hashBvNode* old = *l; + *l = (*l)->next; + // splice it out + old->freeNode(lhs->globalData()); + lhs->numNodes--; + result = true; + } + static inline void BothPresent(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + if ((*l)->AndWithChange(r)) + { + r = r->next; + result = true; + + if ((*l)->anySet()) + { + l = &((*l)->next); + } + else + { + hashBvNode* old = *l; + *l = (*l)->next; + old->freeNode(lhs->globalData()); + lhs->numNodes--; + } + } + else + { + r = r->next; + l = &((*l)->next); + } + } + static inline void LeftEmpty(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + r = r->next; + } +}; + +class SubtractAction +{ +public: + static inline void PreAction(hashBv* lhs, hashBv* rhs) + { + } + static inline void PostAction(hashBv* lhs, hashBv* rhs) + { + } + static inline bool DefaultResult() + { + return false; + } + static inline void LeftGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + // it's in other, not this + // so skip it + r = r->next; + } + static inline void RightGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + // in lhs, not rhs + // so skip lhs + l = &((*l)->next); + } + static inline void BothPresent(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + if ((*l)->SubtractWithChange(r)) + { + r = r->next; + result = true; + + if ((*l)->anySet()) + { + l = &((*l)->next); + } + else + { + hashBvNode* old = *l; + *l = (*l)->next; + old->freeNode(lhs->globalData()); + lhs->numNodes--; + } + } + else + { + r = r->next; + l = &((*l)->next); + } + } + static inline void LeftEmpty(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + r = r->next; + } +}; + +class XorAction +{ +public: + static inline void PreAction(hashBv* lhs, hashBv* rhs) + { + } + static inline void PostAction(hashBv* lhs, hashBv* rhs) + { + } + static inline bool DefaultResult() + { + return false; + } + + static inline void LeftGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + // it's in other, not this + // so put one in + result = true; + hashBvNode* temp = hashBvNode::Create(r->baseIndex, lhs->compiler); + lhs->numNodes++; + temp->XorWith(r); + temp->next = (*l)->next; + *l = temp; + l = &(temp->next); + + r = r->next; + } + + static inline void RightGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + // it's in LHS, not RHS + // so LHS remains the same + l = &((*l)->next); + } + + static inline void BothPresent(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + if ((*l)->XorWithChange(r)) + { + result = true; + } + l = &((*l)->next); + r = r->next; + } + + static inline void LeftEmpty(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + // it's in other, not this + // so put one in + result = true; + hashBvNode* temp = hashBvNode::Create(r->baseIndex, lhs->compiler); + lhs->numNodes++; + temp->XorWith(r); + temp->next = nullptr; + *l = temp; + l = &(temp->next); + + r = r->next; + } +}; + +class OrAction +{ +public: + static inline void PreAction(hashBv* lhs, hashBv* rhs) + { + if (lhs->log2_hashSize + 2 < rhs->log2_hashSize) + { + lhs->Resize(rhs->numNodes); + } + if (rhs->numNodes > rhs->hashtable_size() * 4) + { + rhs->Resize(rhs->numNodes); + } + } + static inline void PostAction(hashBv* lhs, hashBv* rhs) + { + } + static inline bool DefaultResult() + { + return false; + } + + static inline void LeftGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + // it's in other, not this + // so put one in + result = true; + hashBvNode* temp = hashBvNode::Create(r->baseIndex, lhs->compiler); + lhs->numNodes++; + temp->OrWith(r); + temp->next = *l; + *l = temp; + l = &(temp->next); + + r = r->next; + } + static inline void RightGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + // in lhs, not rhs + // so skip lhs + l = &((*l)->next); + } + static inline void BothPresent(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + if ((*l)->OrWithChange(r)) + { + result = true; + } + l = &((*l)->next); + r = r->next; + } + static inline void LeftEmpty(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + // other contains something this does not + // copy it + // LeftGap(lhs, l, r, result, terminate); + result = true; + hashBvNode* temp = hashBvNode::Create(r->baseIndex, lhs->compiler); + lhs->numNodes++; + temp->OrWith(r); + temp->next = nullptr; + *l = temp; + l = &(temp->next); + + r = r->next; + } +}; + +class CompareAction +{ +public: + static inline void PreAction(hashBv* lhs, hashBv* rhs) + { + } + static inline void PostAction(hashBv* lhs, hashBv* rhs) + { + } + static inline bool DefaultResult() + { + return true; + } + + static inline void LeftGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + terminate = true; + result = false; + } + static inline void RightGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + // in lhs, not rhs + // so skip lhs + terminate = true; + result = false; + } + static inline void BothPresent(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + if (!(*l)->sameAs(r)) + { + terminate = true; + result = false; + } + l = &((*l)->next); + r = r->next; + } + static inline void LeftEmpty(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + terminate = true; + result = false; + } +}; + +class IntersectsAction +{ +public: + static inline void PreAction(hashBv* lhs, hashBv* rhs) + { + } + static inline void PostAction(hashBv* lhs, hashBv* rhs) + { + } + static inline bool DefaultResult() + { + return false; + } + + static inline void LeftGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + // in rhs, not lhs + // so skip rhs + r = r->next; + } + static inline void RightGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + // in lhs, not rhs + // so skip lhs + l = &((*l)->next); + } + static inline void BothPresent(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + if ((*l)->Intersects(r)) + { + terminate = true; + result = true; + } + } + static inline void LeftEmpty(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate) + { + r = r->next; + } +}; + +template <typename Action> +bool hashBv::MultiTraverseLHSBigger(hashBv* other) +{ + int hts = this->hashtable_size(); + int ots = other->hashtable_size(); + + bool result = Action::DefaultResult(); + bool terminate = false; + + // this is larger + hashBvNode*** cursors; + int shiftFactor = this->log2_hashSize - other->log2_hashSize; + int expansionFactor = hts / ots; + cursors = (hashBvNode***)alloca(expansionFactor * sizeof(void*)); + + for (int h = 0; h < other->hashtable_size(); h++) + { + // set up cursors for the expansion of nodes + for (int i = 0; i < expansionFactor; i++) + { + // ex: for [1024] &= [8] + // for rhs in bin 0 + // cursors point to lhs: 0, 8, 16, 24, ... + cursors[i] = &nodeArr[ots * i + h]; + } + + hashBvNode* o = other->nodeArr[h]; + while (o) + { + hashBvNode* next = o->next; + // figure out what dst list this goes to + int hash = getHashForIndex(o->baseIndex, hts); + int dstIndex = (hash - h) >> other->log2_hashSize; + hashBvNode** cursor = cursors[dstIndex]; + hashBvNode* c = *cursor; + + // figure out where o fits in the cursor + + if (!c) + { + Action::LeftEmpty(this, cursors[dstIndex], o, result, terminate); + if (terminate) + { + return result; + } + } + else if (c->baseIndex == o->baseIndex) + { + Action::BothPresent(this, cursors[dstIndex], o, result, terminate); + if (terminate) + { + return result; + } + } + else if (c->baseIndex > o->baseIndex) + { + Action::LeftGap(this, cursors[dstIndex], o, result, terminate); + if (terminate) + { + return result; + } + } + else if (c->baseIndex < o->baseIndex) + { + Action::RightGap(this, cursors[dstIndex], o, result, terminate); + if (terminate) + { + return result; + } + } + } + for (int i = 0; i < expansionFactor; i++) + { + while (*(cursors[i])) + { + Action::RightGap(this, cursors[i], o, result, terminate); + if (terminate) + { + return result; + } + } + } + } + return result; +} + +template <typename Action> +bool hashBv::MultiTraverseRHSBigger(hashBv* other) +{ + int hts = this->hashtable_size(); + int ots = other->hashtable_size(); + + bool result = Action::DefaultResult(); + bool terminate = false; + + for (int hashNum = 0; hashNum < ots; hashNum++) + { + int destination = getHashForIndex(BITS_PER_NODE * hashNum, this->hashtable_size()); + assert(hashNum == getHashForIndex(BITS_PER_NODE * hashNum, other->hashtable_size())); + + hashBvNode** pa = &this->nodeArr[destination]; + hashBvNode** pb = &other->nodeArr[hashNum]; + hashBvNode* b = *pb; + + while (*pa && b) + { + hashBvNode* a = *pa; + if (a->baseIndex < b->baseIndex) + { + // in a but not in b + // but maybe it's someplace else in b + if (getHashForIndex(a->baseIndex, ots) == hashNum) + { + // this contains something other does not + // need to erase it + Action::RightGap(this, pa, b, result, terminate); + if (terminate) + { + return result; + } + } + else + { + // other might contain this, we don't know yet + pa = &a->next; + } + } + else if (a->baseIndex == b->baseIndex) + { + Action::BothPresent(this, pa, b, result, terminate); + if (terminate) + { + return result; + } + } + else if (a->baseIndex > b->baseIndex) + { + // other contains something this does not + Action::LeftGap(this, pa, b, result, terminate); + if (terminate) + { + return result; + } + } + } + while (*pa) + { + // if it's in the dest but not in src + // then make sure it's expected to be in this list + if (getHashForIndex((*pa)->baseIndex, ots) == hashNum) + { + Action::RightGap(this, pa, b, result, terminate); + if (terminate) + { + return result; + } + } + else + { + pa = &((*pa)->next); + } + } + while (b) + { + Action::LeftEmpty(this, pa, b, result, terminate); + if (terminate) + { + return result; + } + } + } + assert(this->numNodes == this->getNodeCount()); + return result; +} + +// LHSBigger and RHSBigger algorithms both work for equal +// this is a specialized version of RHSBigger which is simpler (and faster) +// because equal sizes are the 99% case +template <typename Action> +bool hashBv::MultiTraverseEqual(hashBv* other) +{ + int hts = this->hashtable_size(); + assert(other->hashtable_size() == hts); + + bool result = Action::DefaultResult(); + bool terminate = false; + + for (int hashNum = 0; hashNum < hts; hashNum++) + { + int destination = getHashForIndex(BITS_PER_NODE * hashNum, this->hashtable_size()); + + hashBvNode** pa = &this->nodeArr[hashNum]; + hashBvNode** pb = &other->nodeArr[hashNum]; + hashBvNode* b = *pb; + + while (*pa && b) + { + hashBvNode* a = *pa; + if (a->baseIndex < b->baseIndex) + { + // in a but not in b + Action::RightGap(this, pa, b, result, terminate); + if (terminate) + { + return result; + } + } + else if (a->baseIndex == b->baseIndex) + { + Action::BothPresent(this, pa, b, result, terminate); + if (terminate) + { + return result; + } + } + else if (a->baseIndex > b->baseIndex) + { + // other contains something this does not + Action::LeftGap(this, pa, b, result, terminate); + if (terminate) + { + return result; + } + } + } + while (*pa) + { + // if it's in the dest but not in src + Action::RightGap(this, pa, b, result, terminate); + if (terminate) + { + return result; + } + } + while (b) + { + Action::LeftEmpty(this, pa, b, result, terminate); + if (terminate) + { + return result; + } + } + } + assert(this->numNodes == this->getNodeCount()); + return result; +} + +template <class Action> +bool hashBv::MultiTraverse(hashBv* other) +{ + bool result = false; + + assert(this->numNodes == this->getNodeCount()); + + Action::PreAction(this, other); + + int hts = this->log2_hashSize; + int ots = other->log2_hashSize; + + if (hts == ots) + { + return MultiTraverseEqual<Action>(other); + } + else if (hts > ots) + { + return MultiTraverseLHSBigger<Action>(other); + } + else + { + return MultiTraverseRHSBigger<Action>(other); + } +} + +bool hashBv::Intersects(hashBv* other) +{ + return MultiTraverse<IntersectsAction>(other); +} + +bool hashBv::AndWithChange(hashBv* other) +{ + return MultiTraverse<AndAction>(other); +} + +// same as AND ~x +bool hashBv::SubtractWithChange(hashBv* other) +{ + return MultiTraverse<SubtractAction>(other); +} + +void hashBv::Subtract(hashBv* other) +{ + this->SubtractWithChange(other); +} + +void hashBv::Subtract3(hashBv* o1, hashBv* o2) +{ + this->copyFrom(o1, compiler); + this->Subtract(o2); +} + +void hashBv::UnionMinus(hashBv* src1, hashBv* src2, hashBv* src3) +{ + this->Subtract3(src1, src2); + this->OrWithChange(src3); +} + +void hashBv::ZeroAll() +{ + int hts = this->hashtable_size(); + + for (int hashNum = 0; hashNum < hts; hashNum++) + { + while (nodeArr[hashNum]) + { + hashBvNode* n = nodeArr[hashNum]; + nodeArr[hashNum] = n->next; + n->freeNode(globalData()); + } + } + this->numNodes = 0; +} + +bool hashBv::OrWithChange(hashBv* other) +{ + return MultiTraverse<OrAction>(other); +} + +bool hashBv::XorWithChange(hashBv* other) +{ + return MultiTraverse<XorAction>(other); +} +void hashBv::OrWith(hashBv* other) +{ + this->OrWithChange(other); +} + +void hashBv::AndWith(hashBv* other) +{ + this->AndWithChange(other); +} + +bool hashBv::CompareWith(hashBv* other) +{ + return MultiTraverse<CompareAction>(other); +} + +void hashBv::copyFrom(hashBv* other, Compiler* comp) +{ + assert(this != other); + + hashBvNode* freeList = nullptr; + + this->ZeroAll(); + + if (this->log2_hashSize != other->log2_hashSize) + { + this->nodeArr = this->getNewVector(other->hashtable_size()); + this->log2_hashSize = other->log2_hashSize; + assert(this->hashtable_size() == other->hashtable_size()); + } + + int hts = this->hashtable_size(); + // printf("in copyfrom\n"); + for (int h = 0; h < hts; h++) + { + // put the current list on the free list + freeList = this->nodeArr[h]; + this->nodeArr[h] = nullptr; + + hashBvNode** splicePoint = &(this->nodeArr[h]); + hashBvNode* otherNode = other->nodeArr[h]; + hashBvNode* newNode = nullptr; + + while (otherNode) + { + // printf("otherNode is True...\n"); + hashBvNode* next = *splicePoint; + + this->numNodes++; + + if (freeList) + { + newNode = freeList; + freeList = freeList->next; + newNode->Reconstruct(otherNode->baseIndex); + } + else + { + newNode = hashBvNode::Create(otherNode->baseIndex, this->compiler); + } + newNode->copyFrom(otherNode); + + newNode->next = *splicePoint; + *splicePoint = newNode; + splicePoint = &(newNode->next); + + otherNode = otherNode->next; + } + } + while (freeList) + { + hashBvNode* next = freeList->next; + freeList->freeNode(globalData()); + freeList = next; + } +#if 0 + for (int h=0; h<hashtable_size(); h++) + { + printf("%p %p\n", this->nodeArr[h], other->nodeArr[h]); + } +#endif +} + +int nodeSort(const void* x, const void* y) +{ + hashBvNode* a = (hashBvNode*)x; + hashBvNode* b = (hashBvNode*)y; + return (int)(b->baseIndex - a->baseIndex); +} + +void hashBv::InorderTraverse(nodeAction n) +{ + int hts = hashtable_size(); + + hashBvNode** x = new (compiler, CMK_hashBv) hashBvNode*[hts]; + + { + // keep an array of the current pointers + // into each of the the bitvector lists + // in the hashtable + for (int i = 0; i < hts; i++) + { + x[i] = nodeArr[i]; + } + + while (1) + { + // pick the lowest node in the hashtable + + indexType lowest = INT_MAX; + int lowest_index = -1; + for (int i = 0; i < hts; i++) + { + if (x[i] && x[i]->baseIndex < lowest) + { + lowest = x[i]->baseIndex; + lowest_index = i; + } + } + // if there was anything left, use it and update + // the list pointers otherwise we are done + if (lowest_index != -1) + { + n(x[lowest_index]); + x[lowest_index] = x[lowest_index]->next; + } + else + { + break; + } + } + } + + delete[] x; +} + +void hashBv::InorderTraverseTwo(hashBv* other, dualNodeAction a) +{ + int sizeThis, sizeOther; + hashBvNode **nodesThis, **nodesOther; + + sizeThis = this->hashtable_size(); + sizeOther = other->hashtable_size(); + + nodesThis = new (compiler, CMK_hashBv) hashBvNode*[sizeThis]; + nodesOther = new (compiler, CMK_hashBv) hashBvNode*[sizeOther]; + + // populate the arrays + for (int i = 0; i < sizeThis; i++) + { + nodesThis[i] = this->nodeArr[i]; + } + + for (int i = 0; i < sizeOther; i++) + { + nodesOther[i] = other->nodeArr[i]; + } + + while (1) + { + indexType lowestThis = INT_MAX; + indexType lowestOther = INT_MAX; + int lowestHashIndexThis = -1; + int lowestHashIndexOther = -1; + + // find the lowest remaining node in each BV + for (int i = 0; i < sizeThis; i++) + { + if (nodesThis[i] && nodesThis[i]->baseIndex < lowestThis) + { + lowestHashIndexThis = i; + lowestThis = nodesThis[i]->baseIndex; + } + } + for (int i = 0; i < sizeOther; i++) + { + if (nodesOther[i] && nodesOther[i]->baseIndex < lowestOther) + { + lowestHashIndexOther = i; + lowestOther = nodesOther[i]->baseIndex; + } + } + hashBvNode *nodeThis, *nodeOther; + nodeThis = lowestHashIndexThis == -1 ? nullptr : nodesThis[lowestHashIndexThis]; + nodeOther = lowestHashIndexOther == -1 ? nullptr : nodesOther[lowestHashIndexOther]; + // no nodes left in either, so return + if ((!nodeThis) && (!nodeOther)) + { + break; + + // there are only nodes left in one bitvector + } + else if ((!nodeThis) || (!nodeOther)) + { + a(this, other, nodeThis, nodeOther); + if (nodeThis) + { + nodesThis[lowestHashIndexThis] = nodesThis[lowestHashIndexThis]->next; + } + if (nodeOther) + { + nodesOther[lowestHashIndexOther] = nodesOther[lowestHashIndexOther]->next; + } + } + // nodes are left in both so determine if the lowest ones + // match. if so process them in a pair. if not then + // process the lower of the two alone + else if (nodeThis && nodeOther) + { + if (nodeThis->baseIndex == nodeOther->baseIndex) + { + a(this, other, nodeThis, nodeOther); + nodesThis[lowestHashIndexThis] = nodesThis[lowestHashIndexThis]->next; + nodesOther[lowestHashIndexOther] = nodesOther[lowestHashIndexOther]->next; + } + else if (nodeThis->baseIndex < nodeOther->baseIndex) + { + a(this, other, nodeThis, nullptr); + nodesThis[lowestHashIndexThis] = nodesThis[lowestHashIndexThis]->next; + } + else if (nodeOther->baseIndex < nodeThis->baseIndex) + { + a(this, other, nullptr, nodeOther); + nodesOther[lowestHashIndexOther] = nodesOther[lowestHashIndexOther]->next; + } + } + } + delete[] nodesThis; + delete[] nodesOther; +} + +// -------------------------------------------------------------------- +// -------------------------------------------------------------------- + +#ifdef DEBUG +void SimpleDumpNode(hashBvNode* n) +{ + printf("base: %d\n", n->baseIndex); +} + +void DumpNode(hashBvNode* n) +{ + n->dump(); +} + +void SimpleDumpDualNode(hashBv* a, hashBv* b, hashBvNode* n, hashBvNode* m) +{ + printf("nodes: "); + if (n) + { + printf("%d,", n->baseIndex); + } + else + { + printf("----,"); + } + if (m) + { + printf("%d\n", m->baseIndex); + } + else + { + printf("----\n"); + } +} +#endif // DEBUG + +hashBvIterator::hashBvIterator() +{ + this->bv = nullptr; +} + +hashBvIterator::hashBvIterator(hashBv* bv) +{ + this->bv = bv; + this->hashtable_index = 0; + this->current_element = 0; + this->current_base = 0; + this->current_data = 0; + + if (bv) + { + this->hashtable_size = bv->hashtable_size(); + this->currNode = bv->nodeArr[0]; + + if (!this->currNode) + { + this->nextNode(); + } + } +} + +void hashBvIterator::initFrom(hashBv* bv) +{ + this->bv = bv; + this->hashtable_size = bv->hashtable_size(); + this->hashtable_index = 0; + this->currNode = bv->nodeArr[0]; + this->current_element = 0; + this->current_base = 0; + this->current_data = 0; + + if (!this->currNode) + { + this->nextNode(); + } + if (this->currNode) + { + this->current_data = this->currNode->elements[0]; + } +} + +void hashBvIterator::nextNode() +{ + // if we have a valid node then just get the next one in the chain + if (this->currNode) + { + this->currNode = this->currNode->next; + } + + // else step to the next one in the hash table + while (!this->currNode) + { + hashtable_index++; + // no more + if (hashtable_index >= hashtable_size) + { + // printf("nextnode bailed\n"); + return; + } + + this->currNode = bv->nodeArr[hashtable_index]; + } + // first element in the new node + this->current_element = 0; + this->current_base = this->currNode->baseIndex; + this->current_data = this->currNode->elements[0]; + // printf("nextnode returned base %d\n", this->current_base); + // printf("hti = %d ", hashtable_index); +} + +indexType hashBvIterator::nextBit() +{ + + // printf("in nextbit for bv:\n"); + // this->bv->dump(); + + if (!this->currNode) + { + this->nextNode(); + } + +top: + + if (!this->currNode) + { + return NOMOREBITS; + } + +more_data: + if (!this->current_data) + { + current_element++; + // printf("current element is %d\n", current_element); + // reached the end of this node + if (current_element == (indexType) this->currNode->numElements()) + { + // printf("going to next node\n"); + this->nextNode(); + goto top; + } + else + { + assert(current_element < (indexType) this->currNode->numElements()); + // printf("getting more data\n"); + current_data = this->currNode->elements[current_element]; + current_base = this->currNode->baseIndex + current_element * BITS_PER_ELEMENT; + goto more_data; + } + } + else + { + while (current_data) + { + if (current_data & 1) + { + current_data >>= 1; + current_base++; + + return current_base - 1; + } + else + { + current_data >>= 1; + current_base++; + } + } + goto more_data; + } +} + +indexType HbvNext(hashBv* bv, Compiler* comp) +{ + if (bv) + { + bv->globalData()->hashBvNextIterator.initFrom(bv); + } + return bv->globalData()->hashBvNextIterator.nextBit(); +} |