hashbv.cpp

// 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
voidhashBvNode::dump()
{
printf("base: %d { ", baseIndex);
this->foreachBit(pBit);
printf("}\n");
}
#endif// DEBUG

voidhashBvNode::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;
}

voidhashBvNode::freeNode(hashBvGlobalData* glob)
{
this->next = glob->hbvNodeFreeList;
 glob->hbvNodeFreeList = this;
}

voidhashBvNode::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;
}

voidhashBvNode::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;
 }
}

voidhashBvNode::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);
}

boolhashBvNode::belongsIn(indexType index)
{
if (index < baseIndex)
 {
returnfalse;
 }
if (index >= baseIndex + BITS_PER_NODE)
 {
returnfalse;
 }
returntrue;
}

intcountBitsInWord(unsignedint 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;
}

intcountBitsInWord(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;
}

inthashBvNode::countBits()
{
int result = 0;

for (int i = 0; i < this->numElements(); i++)
 {
 elemType bits = elements[i];

 result += countBitsInWord(bits);

 result += (int)bits;
 }
return result;
}

boolhashBvNode::anyBits()
{
for (int i = 0; i < this->numElements(); i++)
 {
if (elements[i])
 {
returntrue;
 }
 }
returnfalse;
}

boolhashBvNode::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))
 {
returntrue;
 }
else
 {
returnfalse;
 }
}

boolhashBvNode::anySet()
{
for (int i = 0; i < this->numElements(); i++)
 {
if (elements[i])
 {
returntrue;
 }
 }
returnfalse;
}

voidhashBvNode::copyFrom(hashBvNode* other)
{
this->baseIndex = other->baseIndex;
for (int i = 0; i < this->numElements(); i++)
 {
this->elements[i] = other->elements[i];
 }
}

voidhashBvNode::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;
}

boolhashBvNode::Intersects(hashBvNode* other)
{
for (int i = 0; i < this->numElements(); i++)
 {
if ((this->elements[i] & other->elements[i]) != 0)
 {
returntrue;
 }
 }

returnfalse;
}

voidhashBvNode::AndWith(hashBvNode* other)
{
for (int i = 0; i < this->numElements(); i++)
 {
this->elements[i] &= other->elements[i];
 }
}

voidhashBvNode::OrWith(hashBvNode* other)
{
for (int i = 0; i < this->numElements(); i++)
 {
this->elements[i] |= other->elements[i];
 }
}

voidhashBvNode::XorWith(hashBvNode* other)
{
for (int i = 0; i < this->numElements(); i++)
 {
this->elements[i] ^= other->elements[i];
 }
}

voidhashBvNode::Subtract(hashBvNode* other)
{
for (int i = 0; i < this->numElements(); i++)
 {
this->elements[i] &= ~other->elements[i];
 }
}

boolhashBvNode::sameAs(hashBvNode* other)
{
if (this->baseIndex != other->baseIndex)
 {
returnfalse;
 }

for (int i = 0; i < this->numElements(); i++)
 {
if (this->elements[i] != other->elements[i])
 {
returnfalse;
 }
 }

returntrue;
}

// --------------------------------------------------------------------
// --------------------------------------------------------------------

hashBv::hashBv(Compiler* comp)
{
this->compiler = comp;
this->log2_hashSize = 0;

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;
}

voidhashBv::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;
}

voidhashBv::hbvFree()
{
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;
}

voidhashBv::MergeLists(hashBvNode** root1, hashBvNode** root2)
{
}

boolhashBv::TooSmall()
{
returnthis->numNodes > this->hashtable_size() * 4;
}

boolhashBv::TooBig()
{
returnthis->hashtable_size() > this->numNodes * 4;
}

inthashBv::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;
}

boolhashBv::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;
 }
 }
returntrue;
}

voidhashBv::Resize()
{
// resize to 'optimal' size

this->Resize(this->numNodes);
}

voidhashBv::Resize(int newSize)
{
assert(newSize > 0);
 newSize = nearest_pow2(newSize);

int oldSize = hashtable_size();

if (newSize == oldSize)
 {
return;
 }

int log2_newSize = genLog2((unsigned)newSize);

 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 = (unsignedshort)log2_newSize;
 }
elseif (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 = (unsignedshort)log2_newSize;
 }
else
 {
// same size
assert(oldSize == newSize);
 }
assert(this->IsValid());
}

#ifdef DEBUG
voidhashBv::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");
}

voidhashBv::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

voidhashBv::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--;
}

inthashBv::getHashForIndex(indexType index, int table_size)
{
 indexType hashIndex;

 hashIndex = index >> LOG2_BITS_PER_NODE;
 hashIndex &= (table_size - 1);

return (int)hashIndex;
}

inthashBv::getRehashForIndex(indexType thisIndex, int thisTableSize, int newTableSize)
{
assert(0);
return0;
}

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;
 }
elseif (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;
 }
elseif (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
 {
returnnullptr;
 }
}

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
 {
returnnullptr;
 }
}

voidhashBv::setBit(indexType index)
{
assert(index >= 0);
assert(this->numNodes == this->getNodeCount());

 indexType baseIndex = index & ~(BITS_PER_NODE - 1);
 indexType base = index - baseIndex;
 indexType elem = base / BITS_PER_ELEMENT;
 indexType posi = base % BITS_PER_ELEMENT;

 hashBvNode* result = nodeArr[0];

// this should be the 99% case : when there is only one node in the structure
if ((result != nullptr) && (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;
}

voidhashBv::setAll(indexType numToSet)
{
// TODO-Throughput: this could be more efficient
for (unsignedint 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);
 }
}

voidhashBv::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;
 }
elseif (result->baseIndex > baseIndex)
 {
return;
 }
else
 {
 prev = &(result->next);
 result = result->next;
 }
 }
assert(this->numNodes == this->getNodeCount());
return;
}

boolhashBv::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;
 }
 }
returnfalse;
}

inthashBv::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;
}

boolhashBv::anySet()
{
int hts = this->hashtable_size();
for (int hashNum = 0; hashNum < hts; hashNum++)
 {
 hashBvNode* node = nodeArr[hashNum];
while (node)
 {
if (node->anySet())
 {
returntrue;
 }
 node = node->next;
 }
 }
returnfalse;
}

classAndAction
{
public:
staticinlinevoidPreAction(hashBv* lhs, hashBv* rhs)
 {
 }
staticinlinevoidPostAction(hashBv* lhs, hashBv* rhs)
 {
 }
staticinlineboolDefaultResult()
 {
returnfalse;
 }

staticinlinevoidLeftGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
 {
// it's in other, not this
// so skip it
 r = r->next;
 }
staticinlinevoidRightGap(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;
 }
staticinlinevoidBothPresent(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);
 }
 }
staticinlinevoidLeftEmpty(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
 {
 r = r->next;
 }
};

classSubtractAction