src/jit/hashbv.h

   1 // Licensed to the .NET Foundation under one or more agreements.
   2 // The .NET Foundation licenses this file to you under the MIT license.
   3 // See the LICENSE file in the project root for more information.
   4
   5 #ifndef HASHBV_H
   6 #define HASHBV_H
   7
   8 #if defined(_M_AMD64) || defined(_M_X86)
   9 #include <xmmintrin.h>
  10 #endif
  11
  12 #include <stdlib.h>
  13 #include <stdio.h>
  14 #include <memory.h>
  15 #include <windows.h>
  16
  17 //#define TESTING 1
  18
  19 #define LOG2_BITS_PER_ELEMENT 5
  20 #define LOG2_ELEMENTS_PER_NODE 2
  21 #define LOG2_BITS_PER_NODE (LOG2_BITS_PER_ELEMENT + LOG2_ELEMENTS_PER_NODE)
  22
  23 #define BITS_PER_ELEMENT (1 << LOG2_BITS_PER_ELEMENT)
  24 #define ELEMENTS_PER_NODE (1 << LOG2_ELEMENTS_PER_NODE)
  25 #define BITS_PER_NODE (1 << LOG2_BITS_PER_NODE)
  26
  27 #ifdef _TARGET_AMD64_
  28 typedef unsigned __int64 elemType;
  29 typedef unsigned __int64 indexType;
  30 #else
  31 typedef unsigned int elemType;
  32 typedef unsigned int indexType;
  33 #endif
  34
  35 class hashBvNode;
  36 class hashBv;
  37 class hashBvIterator;
  38 class hashBvGlobalData;
  39
  40 typedef void bitAction(indexType);
  41 typedef void nodeAction(hashBvNode*);
  42 typedef void dualNodeAction(hashBv* left, hashBv* right, hashBvNode* a, hashBvNode* b);
  43
  44 #define NOMOREBITS -1
  45
  46 #ifdef DEBUG
  47 inline void pBit(indexType i)
  48 {
  49     printf("%d ", i);
  50 }
  51 #endif // DEBUG
  52
  53 // ------------------------------------------------------------
  54 //  this is essentially a hashtable of small fixed bitvectors.
  55 //  for any index, bits select position as follows:
  56 //   32                                                      0
  57 // ------------------------------------------------------------
  58 //  | ... ... ... | hash | element in node | index in element |
  59 // ------------------------------------------------------------
  60 //
  61 //
  62 // hashBv
  63 // | // hashtable
  64 // v
  65 // []->node->node->node
  66 // []->node
  67 // []
  68 // []->node->node
  69 //
  70 //
  71
  72 #if TESTING
  73 inline int log2(int number)
  74 {
  75     int result = 0;
  76     number >>= 1;
  77     while (number)
  78     {
  79         result++;
  80         number >>= 1;
  81     }
  82     return result;
  83 }
  84 #endif
  85
  86 // return greatest power of 2 that is less than or equal
  87 inline int nearest_pow2(unsigned number)
  88 {
  89     int result = 0;
  90
  91     if (number > 0xffff)
  92     {
  93         number >>= 16;
  94         result += 16;
  95     }
  96     if (number > 0xff)
  97     {
  98         number >>= 8;
  99         result += 8;
 100     }
 101     if (number > 0xf)
 102     {
 103         number >>= 4;
 104         result += 4;
 105     }
 106     if (number > 0x3)
 107     {
 108         number >>= 2;
 109         result += 2;
 110     }
 111     if (number > 0x1)
 112     {
 113         number >>= 1;
 114         result += 1;
 115     }
 116     return 1 << result;
 117 }
 118
 119 class hashBvNode
 120 {
 121 public:
 122     hashBvNode* next;
 123     indexType   baseIndex;
 124     elemType    elements[ELEMENTS_PER_NODE];
 125
 126 public:
 127     hashBvNode(indexType base);
 128     hashBvNode()
 129     {
 130     }
 131     static hashBvNode* Create(indexType base, Compiler* comp);
 132     void Reconstruct(indexType base);
 133     int numElements()
 134     {
 135         return ELEMENTS_PER_NODE;
 136     }
 137     void setBit(indexType base);
 138     void setLowest(indexType numToSet);
 139     bool getBit(indexType base);
 140     void clrBit(indexType base);
 141     bool anySet();
 142     bool belongsIn(indexType index);
 143     int  countBits();
 144     bool anyBits();
 145     void foreachBit(bitAction x);
 146     void freeNode(hashBvGlobalData* glob);
 147     bool sameAs(hashBvNode* other);
 148     void copyFrom(hashBvNode* other);
 149
 150     void AndWith(hashBvNode* other);
 151     void OrWith(hashBvNode* other);
 152     void XorWith(hashBvNode* other);
 153     void Subtract(hashBvNode* other);
 154
 155     elemType AndWithChange(hashBvNode* other);
 156     elemType OrWithChange(hashBvNode* other);
 157     elemType XorWithChange(hashBvNode* other);
 158     elemType SubtractWithChange(hashBvNode* other);
 159
 160     bool Intersects(hashBvNode* other);
 161
 162 #ifdef DEBUG
 163     void dump();
 164 #endif // DEBUG
 165 };
 166
 167 class hashBv
 168 {
 169 public:
 170     // --------------------------------------
 171     // data
 172     // --------------------------------------
 173     hashBvNode** nodeArr;
 174     hashBvNode*  initialVector[1];
 175
 176     union {
 177         Compiler* compiler;
 178         // for freelist
 179         hashBv* next;
 180     };
 181
 182     unsigned short log2_hashSize;
 183     // used for heuristic resizing... could be overflowed in rare circumstances
 184     // but should not affect correctness
 185     unsigned short numNodes;
 186
 187 public:
 188     hashBv(Compiler* comp);
 189     hashBv(hashBv* other);
 190     // hashBv() {}
 191     static hashBv* Create(Compiler* comp);
 192     static void Init(Compiler* comp);
 193     static hashBv* CreateFrom(hashBv* other, Compiler* comp);
 194     void hbvFree();
 195 #ifdef DEBUG
 196     void dump();
 197     void dumpFancy();
 198 #endif // DEBUG
 199     __forceinline int hashtable_size()
 200     {
 201         return 1 << this->log2_hashSize;
 202     }
 203
 204     hashBvGlobalData* globalData();
 205
 206     static hashBvNode*& nodeFreeList(hashBvGlobalData* globalData);
 207     static hashBv*& hbvFreeList(hashBvGlobalData* data);
 208
 209     hashBvNode** getInsertionPointForIndex(indexType index);
 210
 211 private:
 212     hashBvNode* getNodeForIndexHelper(indexType index, bool canAdd);
 213     int getHashForIndex(indexType index, int table_size);
 214     int getRehashForIndex(indexType thisIndex, int thisTableSize, int newTableSize);
 215
 216     // maintain free lists for vectors
 217     hashBvNode** getNewVector(int vectorLength);
 218     void freeVector(hashBvNode* vect, int vectorLength);
 219     int getNodeCount();
 220
 221     hashBvNode* getFreeList();
 222
 223 public:
 224     inline hashBvNode* getOrAddNodeForIndex(indexType index)
 225     {
 226         hashBvNode* temp = getNodeForIndexHelper(index, true);
 227         return temp;
 228     }
 229     hashBvNode* getNodeForIndex(indexType index);
 230     void removeNodeAtBase(indexType index);
 231
 232 public:
 233     void setBit(indexType index);
 234     void setAll(indexType numToSet);
 235     bool testBit(indexType index);
 236     void clearBit(indexType index);
 237     int  countBits();
 238     bool anySet();
 239     void copyFrom(hashBv* other, Compiler* comp);
 240     void ZeroAll();
 241     bool CompareWith(hashBv* other);
 242
 243     void AndWith(hashBv* other);
 244     void OrWith(hashBv* other);
 245     void XorWith(hashBv* other);
 246     void Subtract(hashBv* other);
 247     void Subtract3(hashBv* other, hashBv* other2);
 248
 249     void UnionMinus(hashBv* a, hashBv* b, hashBv* c);
 250
 251     bool AndWithChange(hashBv* other);
 252     bool OrWithChange(hashBv* other);
 253     bool OrWithChangeRight(hashBv* other);
 254     bool OrWithChangeLeft(hashBv* other);
 255     bool XorWithChange(hashBv* other);
 256     bool SubtractWithChange(hashBv* other);
 257
 258     bool Intersects(hashBv* other);
 259
 260     template <class Action>
 261     bool MultiTraverseLHSBigger(hashBv* other);
 262     template <class Action>
 263     bool MultiTraverseRHSBigger(hashBv* other);
 264     template <class Action>
 265     bool MultiTraverseEqual(hashBv* other);
 266     template <class Action>
 267     bool MultiTraverse(hashBv* other);
 268
 269     void InorderTraverse(nodeAction a);
 270     void InorderTraverseTwo(hashBv* other, dualNodeAction a);
 271
 272     void Resize(int newSize);
 273     void Resize();
 274     void MergeLists(hashBvNode** a, hashBvNode** b);
 275
 276     bool TooSmall();
 277     bool TooBig();
 278     bool IsValid();
 279 };
 280
 281 // --------------------------------------------------------------------
 282 // --------------------------------------------------------------------
 283
 284 class hbvFreeListNode
 285 {
 286 public:
 287     hbvFreeListNode* next;
 288     int              size;
 289 };
 290
 291 // --------------------------------------------------------------------
 292 // --------------------------------------------------------------------
 293
 294 class hashBvIterator
 295 {
 296 public:
 297     unsigned    hashtable_size;
 298     unsigned    hashtable_index;
 299     hashBv*     bv;
 300     hashBvNode* currNode;
 301     indexType   current_element;
 302     // base index of current node
 303     indexType current_base;
 304     // working data of current element
 305     elemType current_data;
 306
 307     hashBvIterator(hashBv* bv);
 308     void initFrom(hashBv* bv);
 309     hashBvIterator();
 310     indexType nextBit();
 311
 312 private:
 313     void nextNode();
 314 };
 315
 316 class hashBvGlobalData
 317 {
 318     friend class hashBv;
 319     friend class hashBvNode;
 320
 321     hashBvNode*      hbvNodeFreeList;
 322     hashBv*          hbvFreeList;
 323     unsigned short   hbvHashSizeLog2;
 324     hbvFreeListNode* hbvFreeVectorList;
 325
 326 public:
 327     hashBvIterator hashBvNextIterator;
 328 };
 329
 330 indexType HbvNext(hashBv* bv, Compiler* comp);
 331
 332 // clang-format off
 333 #define FOREACH_HBV_BIT_SET(index, bv) \
 334     { \
 335         for (int hashNum=0; hashNum<(bv)->hashtable_size(); hashNum++) {\
 336             hashBvNode *node = (bv)->nodeArr[hashNum];\
 337             while (node) { \
 338                 indexType base = node->baseIndex; \
 339                 for (int el=0; el<node->numElements(); el++) {\
 340                     elemType _i = 0; \
 341                     elemType _e = node->elements[el]; \
 342                     while (_e) { \
 343                     int _result = BitScanForwardPtr((DWORD *) &_i, _e); \
 344                         assert(_result); \
 345                         (index) = base + (el*BITS_PER_ELEMENT) + _i; \
 346                         _e ^= (elemType(1) << _i);
 347
 348 #define NEXT_HBV_BIT_SET \
 349                     }\
 350                 }\
 351                 node = node->next; \
 352             }\
 353         }\
 354     } \
 355 //clang-format on
 356
 357 #ifdef DEBUG
 358 void SimpleDumpNode(hashBvNode *n);
 359 void DumpNode(hashBvNode *n);
 360 void SimpleDumpDualNode(hashBv *a, hashBv *b, hashBvNode *n, hashBvNode *m);
 361 #endif // DEBUG
 362
 363 #endif