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_
28typedef unsigned __int64 elemType;
29typedef unsigned __int64 indexType;
30#else
31typedef unsigned int elemType;
32typedef unsigned int indexType;
33#endif
34
35class hashBvNode;
36class hashBv;
37class hashBvIterator;
38class hashBvGlobalData;
39
40typedef void bitAction(indexType);
41typedef void nodeAction(hashBvNode*);
42typedef void dualNodeAction(hashBv* left, hashBv* right, hashBvNode* a, hashBvNode* b);
43
44#define NOMOREBITS -1
45
46#ifdef DEBUG
47inline 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
73inline 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
87inline 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
119class hashBvNode
120{
121public:
122 hashBvNode* next;
123 indexType baseIndex;
124 elemType elements[ELEMENTS_PER_NODE];
125
126public:
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
167class hashBv
168{
169public:
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
187public:
188 hashBv(Compiler* comp);
189 static hashBv* Create(Compiler* comp);
190 static void Init(Compiler* comp);
191 static hashBv* CreateFrom(hashBv* other, Compiler* comp);
192 void hbvFree();
193#ifdef DEBUG
194 void dump();
195 void dumpFancy();
196#endif // DEBUG
197 __forceinline int hashtable_size()
198 {
199 return 1 << this->log2_hashSize;
200 }
201
202 hashBvGlobalData* globalData();
203
204 static hashBvNode*& nodeFreeList(hashBvGlobalData* globalData);
205 static hashBv*& hbvFreeList(hashBvGlobalData* data);
206
207 hashBvNode** getInsertionPointForIndex(indexType index);
208
209private:
210 hashBvNode* getNodeForIndexHelper(indexType index, bool canAdd);
211 int getHashForIndex(indexType index, int table_size);
212 int getRehashForIndex(indexType thisIndex, int thisTableSize, int newTableSize);
213
214 // maintain free lists for vectors
215 hashBvNode** getNewVector(int vectorLength);
216 int getNodeCount();
217
218public:
219 inline hashBvNode* getOrAddNodeForIndex(indexType index)
220 {
221 hashBvNode* temp = getNodeForIndexHelper(index, true);
222 return temp;
223 }
224 hashBvNode* getNodeForIndex(indexType index);
225 void removeNodeAtBase(indexType index);
226
227public:
228 void setBit(indexType index);
229 void setAll(indexType numToSet);
230 bool testBit(indexType index);
231 void clearBit(indexType index);
232 int countBits();
233 bool anySet();
234 void copyFrom(hashBv* other, Compiler* comp);
235 void ZeroAll();
236 bool CompareWith(hashBv* other);
237
238 void AndWith(hashBv* other);
239 void OrWith(hashBv* other);
240 void XorWith(hashBv* other);
241 void Subtract(hashBv* other);
242 void Subtract3(hashBv* other, hashBv* other2);
243
244 void UnionMinus(hashBv* a, hashBv* b, hashBv* c);
245
246 bool AndWithChange(hashBv* other);
247 bool OrWithChange(hashBv* other);
248 bool OrWithChangeRight(hashBv* other);
249 bool OrWithChangeLeft(hashBv* other);
250 bool XorWithChange(hashBv* other);
251 bool SubtractWithChange(hashBv* other);
252
253 bool Intersects(hashBv* other);
254
255 template <class Action>
256 bool MultiTraverseLHSBigger(hashBv* other);
257 template <class Action>
258 bool MultiTraverseRHSBigger(hashBv* other);
259 template <class Action>
260 bool MultiTraverseEqual(hashBv* other);
261 template <class Action>
262 bool MultiTraverse(hashBv* other);
263
264 void InorderTraverse(nodeAction a);
265 void InorderTraverseTwo(hashBv* other, dualNodeAction a);
266
267 void Resize(int newSize);
268 void Resize();
269 void MergeLists(hashBvNode** a, hashBvNode** b);
270
271 bool TooSmall();
272 bool TooBig();
273 bool IsValid();
274};
275
276// --------------------------------------------------------------------
277// --------------------------------------------------------------------
278
279class hashBvIterator
280{
281public:
282 unsigned hashtable_size;
283 unsigned hashtable_index;
284 hashBv* bv;
285 hashBvNode* currNode;
286 indexType current_element;
287 // base index of current node
288 indexType current_base;
289 // working data of current element
290 elemType current_data;
291
292 hashBvIterator(hashBv* bv);
293 void initFrom(hashBv* bv);
294 hashBvIterator();
295 indexType nextBit();
296
297private:
298 void nextNode();
299};
300
301class hashBvGlobalData
302{
303 friend class hashBv;
304 friend class hashBvNode;
305
306 hashBvNode* hbvNodeFreeList;
307 hashBv* hbvFreeList;
308};
309
310// clang-format off
311#define FOREACH_HBV_BIT_SET(index, bv) \
312 { \
313 for (int hashNum=0; hashNum<(bv)->hashtable_size(); hashNum++) {\
314 hashBvNode *node = (bv)->nodeArr[hashNum];\
315 while (node) { \
316 indexType base = node->baseIndex; \
317 for (int el=0; el<node->numElements(); el++) {\
318 elemType _i = 0; \
319 elemType _e = node->elements[el]; \
320 while (_e) { \
321 int _result = BitScanForwardPtr((DWORD *) &_i, _e); \
322 assert(_result); \
323 (index) = base + (el*BITS_PER_ELEMENT) + _i; \
324 _e ^= (elemType(1) << _i);
325
326#define NEXT_HBV_BIT_SET \
327 }\
328 }\
329 node = node->next; \
330 }\
331 }\
332 } \
333//clang-format on
334
335#ifdef DEBUG
336void SimpleDumpNode(hashBvNode *n);
337void DumpNode(hashBvNode *n);
338void SimpleDumpDualNode(hashBv *a, hashBv *b, hashBvNode *n, hashBvNode *m);
339#endif // DEBUG
340
341#endif
342