diff options
Diffstat (limited to 'src/jit/hashbv.h')
-rw-r--r-- | src/jit/hashbv.h | 363 |
1 files changed, 363 insertions, 0 deletions
diff --git a/src/jit/hashbv.h b/src/jit/hashbv.h new file mode 100644 index 0000000000..cadb182cc6 --- /dev/null +++ b/src/jit/hashbv.h @@ -0,0 +1,363 @@ +// 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. + +#ifndef HASHBV_H +#define HASHBV_H + +#if defined(_M_AMD64) || defined(_M_X86) +#include <xmmintrin.h> +#endif + +#include <stdlib.h> +#include <stdio.h> +#include <memory.h> +#include <windows.h> + +//#define TESTING 1 + +#define LOG2_BITS_PER_ELEMENT 5 +#define LOG2_ELEMENTS_PER_NODE 2 +#define LOG2_BITS_PER_NODE (LOG2_BITS_PER_ELEMENT + LOG2_ELEMENTS_PER_NODE) + +#define BITS_PER_ELEMENT (1 << LOG2_BITS_PER_ELEMENT) +#define ELEMENTS_PER_NODE (1 << LOG2_ELEMENTS_PER_NODE) +#define BITS_PER_NODE (1 << LOG2_BITS_PER_NODE) + +#ifdef _TARGET_AMD64_ +typedef unsigned __int64 elemType; +typedef unsigned __int64 indexType; +#else +typedef unsigned int elemType; +typedef unsigned int indexType; +#endif + +class hashBvNode; +class hashBv; +class hashBvIterator; +class hashBvGlobalData; + +typedef void bitAction(indexType); +typedef void nodeAction(hashBvNode*); +typedef void dualNodeAction(hashBv* left, hashBv* right, hashBvNode* a, hashBvNode* b); + +#define NOMOREBITS -1 + +#ifdef DEBUG +inline void pBit(indexType i) +{ + printf("%d ", i); +} +#endif // DEBUG + +// ------------------------------------------------------------ +// this is essentially a hashtable of small fixed bitvectors. +// for any index, bits select position as follows: +// 32 0 +// ------------------------------------------------------------ +// | ... ... ... | hash | element in node | index in element | +// ------------------------------------------------------------ +// +// +// hashBv +// | // hashtable +// v +// []->node->node->node +// []->node +// [] +// []->node->node +// +// + +#if TESTING +inline int log2(int number) +{ + int result = 0; + number >>= 1; + while (number) + { + result++; + number >>= 1; + } + return result; +} +#endif + +// return greatest power of 2 that is less than or equal +inline int nearest_pow2(unsigned number) +{ + int result = 0; + + if (number > 0xffff) + { + number >>= 16; + result += 16; + } + if (number > 0xff) + { + number >>= 8; + result += 8; + } + if (number > 0xf) + { + number >>= 4; + result += 4; + } + if (number > 0x3) + { + number >>= 2; + result += 2; + } + if (number > 0x1) + { + number >>= 1; + result += 1; + } + return 1 << result; +} + +class hashBvNode +{ +public: + hashBvNode* next; + indexType baseIndex; + elemType elements[ELEMENTS_PER_NODE]; + +public: + hashBvNode(indexType base); + hashBvNode() + { + } + static hashBvNode* Create(indexType base, Compiler* comp); + void Reconstruct(indexType base); + int numElements() + { + return ELEMENTS_PER_NODE; + } + void setBit(indexType base); + void setLowest(indexType numToSet); + bool getBit(indexType base); + void clrBit(indexType base); + bool anySet(); + bool belongsIn(indexType index); + int countBits(); + bool anyBits(); + void foreachBit(bitAction x); + void freeNode(hashBvGlobalData* glob); + bool sameAs(hashBvNode* other); + void copyFrom(hashBvNode* other); + + void AndWith(hashBvNode* other); + void OrWith(hashBvNode* other); + void XorWith(hashBvNode* other); + void Subtract(hashBvNode* other); + + elemType AndWithChange(hashBvNode* other); + elemType OrWithChange(hashBvNode* other); + elemType XorWithChange(hashBvNode* other); + elemType SubtractWithChange(hashBvNode* other); + + bool Intersects(hashBvNode* other); + +#ifdef DEBUG + void dump(); +#endif // DEBUG +}; + +class hashBv +{ +public: + // -------------------------------------- + // data + // -------------------------------------- + hashBvNode** nodeArr; + hashBvNode* initialVector[1]; + + union { + Compiler* compiler; + // for freelist + hashBv* next; + }; + + unsigned short log2_hashSize; + // used for heuristic resizing... could be overflowed in rare circumstances + // but should not affect correctness + unsigned short numNodes; + +public: + hashBv(Compiler* comp); + hashBv(hashBv* other); + // hashBv() {} + static hashBv* Create(Compiler* comp); + static void Init(Compiler* comp); + static hashBv* CreateFrom(hashBv* other, Compiler* comp); + void hbvFree(); +#ifdef DEBUG + void dump(); + void dumpFancy(); +#endif // DEBUG + __forceinline int hashtable_size() + { + return 1 << this->log2_hashSize; + } + + hashBvGlobalData* globalData(); + + static hashBvNode*& nodeFreeList(hashBvGlobalData* globalData); + static hashBv*& hbvFreeList(hashBvGlobalData* data); + + hashBvNode** getInsertionPointForIndex(indexType index); + +private: + hashBvNode* getNodeForIndexHelper(indexType index, bool canAdd); + int getHashForIndex(indexType index, int table_size); + int getRehashForIndex(indexType thisIndex, int thisTableSize, int newTableSize); + + // maintain free lists for vectors + hashBvNode** getNewVector(int vectorLength); + void freeVector(hashBvNode* vect, int vectorLength); + int getNodeCount(); + + hashBvNode* getFreeList(); + +public: + inline hashBvNode* getOrAddNodeForIndex(indexType index) + { + hashBvNode* temp = getNodeForIndexHelper(index, true); + return temp; + } + hashBvNode* getNodeForIndex(indexType index); + void removeNodeAtBase(indexType index); + +public: + void setBit(indexType index); + void setAll(indexType numToSet); + bool testBit(indexType index); + void clearBit(indexType index); + int countBits(); + bool anySet(); + void copyFrom(hashBv* other, Compiler* comp); + void ZeroAll(); + bool CompareWith(hashBv* other); + + void AndWith(hashBv* other); + void OrWith(hashBv* other); + void XorWith(hashBv* other); + void Subtract(hashBv* other); + void Subtract3(hashBv* other, hashBv* other2); + + void UnionMinus(hashBv* a, hashBv* b, hashBv* c); + + bool AndWithChange(hashBv* other); + bool OrWithChange(hashBv* other); + bool OrWithChangeRight(hashBv* other); + bool OrWithChangeLeft(hashBv* other); + bool XorWithChange(hashBv* other); + bool SubtractWithChange(hashBv* other); + + bool Intersects(hashBv* other); + + template <class Action> + bool MultiTraverseLHSBigger(hashBv* other); + template <class Action> + bool MultiTraverseRHSBigger(hashBv* other); + template <class Action> + bool MultiTraverseEqual(hashBv* other); + template <class Action> + bool MultiTraverse(hashBv* other); + + void InorderTraverse(nodeAction a); + void InorderTraverseTwo(hashBv* other, dualNodeAction a); + + void Resize(int newSize); + void Resize(); + void MergeLists(hashBvNode** a, hashBvNode** b); + + bool TooSmall(); + bool TooBig(); + bool IsValid(); +}; + +// -------------------------------------------------------------------- +// -------------------------------------------------------------------- + +class hbvFreeListNode +{ +public: + hbvFreeListNode* next; + int size; +}; + +// -------------------------------------------------------------------- +// -------------------------------------------------------------------- + +class hashBvIterator +{ +public: + unsigned hashtable_size; + unsigned hashtable_index; + hashBv* bv; + hashBvNode* currNode; + indexType current_element; + // base index of current node + indexType current_base; + // working data of current element + elemType current_data; + + hashBvIterator(hashBv* bv); + void initFrom(hashBv* bv); + hashBvIterator(); + indexType nextBit(); + +private: + void nextNode(); +}; + +class hashBvGlobalData +{ + friend class hashBv; + friend class hashBvNode; + + hashBvNode* hbvNodeFreeList; + hashBv* hbvFreeList; + unsigned short hbvHashSizeLog2; + hbvFreeListNode* hbvFreeVectorList; + +public: + hashBvIterator hashBvNextIterator; +}; + +indexType HbvNext(hashBv* bv, Compiler* comp); + +// clang-format off +#define FOREACH_HBV_BIT_SET(index, bv) \ + { \ + for (int hashNum=0; hashNum<(bv)->hashtable_size(); hashNum++) {\ + hashBvNode *node = (bv)->nodeArr[hashNum];\ + while (node) { \ + indexType base = node->baseIndex; \ + for (int el=0; el<node->numElements(); el++) {\ + elemType _i = 0; \ + elemType _e = node->elements[el]; \ + while (_e) { \ + int _result = BitScanForwardPtr((DWORD *) &_i, _e); \ + assert(_result); \ + (index) = base + (el*BITS_PER_ELEMENT) + _i; \ + _e ^= (elemType(1) << _i); + +#define NEXT_HBV_BIT_SET \ + }\ + }\ + node = node->next; \ + }\ + }\ + } \ +//clang-format on + +#ifdef DEBUG +void SimpleDumpNode(hashBvNode *n); +void DumpNode(hashBvNode *n); +void SimpleDumpDualNode(hashBv *a, hashBv *b, hashBvNode *n, hashBvNode *m); +#endif // DEBUG + +#endif |