Line data Source code
1 : /* +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
2 : Copyright (c) 2008-2017, Petr Kobalicek
3 :
4 : This software is provided 'as-is', without any express or implied
5 : warranty. In no event will the authors be held liable for any damages
6 : arising from the use of this software.
7 :
8 : Permission is granted to anyone to use this software for any purpose,
9 : including commercial applications, and to alter it and redistribute it
10 : freely, subject to the following restrictions:
11 :
12 : 1. The origin of this software must not be misrepresented; you must not
13 : claim that you wrote the original software. If you use this software
14 : in a product, an acknowledgment in the product documentation would be
15 : appreciated but is not required.
16 : 2. Altered source versions must be plainly marked as such, and must not be
17 : misrepresented as being the original software.
18 : 3. This notice may not be removed or altered from any source distribution.
19 : +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */
20 : #ifdef __PLUMED_HAS_ASMJIT
21 : #pragma GCC diagnostic push
22 : #pragma GCC diagnostic ignored "-Wpedantic"
23 : // [AsmJit]
24 : // Complete x86/x64 JIT and Remote Assembler for C++.
25 : //
26 : // [License]
27 : // Zlib - See LICENSE.md file in the package.
28 :
29 : // [Export]
30 : #define ASMJIT_EXPORTS
31 :
32 : // [Dependencies]
33 : #include "./constpool.h"
34 : #include "./utils.h"
35 :
36 : #include <algorithm>
37 :
38 : // [Api-Begin]
39 : #include "./asmjit_apibegin.h"
40 :
41 : namespace PLMD {
42 : namespace asmjit {
43 :
44 : // Binary tree code is based on Julienne Walker's "Andersson Binary Trees"
45 : // article and implementation. However, only three operations are implemented -
46 : // get, insert and traverse.
47 :
48 : // ============================================================================
49 : // [asmjit::ConstPool::Tree - Ops]
50 : // ============================================================================
51 :
52 : //! \internal
53 : //!
54 : //! Remove left horizontal links.
55 : static ASMJIT_INLINE ConstPool::Node* ConstPoolTree_skewNode(ConstPool::Node* node) noexcept {
56 0 : ConstPool::Node* link = node->_link[0];
57 0 : uint32_t level = node->_level;
58 :
59 0 : if (level != 0 && link && link->_level == level) {
60 0 : node->_link[0] = link->_link[1];
61 0 : link->_link[1] = node;
62 :
63 : node = link;
64 : }
65 :
66 : return node;
67 : }
68 :
69 : //! \internal
70 : //!
71 : //! Remove consecutive horizontal links.
72 : static ASMJIT_INLINE ConstPool::Node* ConstPoolTree_splitNode(ConstPool::Node* node) noexcept {
73 0 : ConstPool::Node* link = node->_link[1];
74 0 : uint32_t level = node->_level;
75 :
76 0 : if (level != 0 && link && link->_link[1] && link->_link[1]->_level == level) {
77 0 : node->_link[1] = link->_link[0];
78 0 : link->_link[0] = node;
79 :
80 : node = link;
81 0 : node->_level++;
82 : }
83 :
84 : return node;
85 : }
86 :
87 0 : ConstPool::Node* ConstPool::Tree::get(const void* data) noexcept {
88 0 : ConstPool::Node* node = _root;
89 0 : size_t dataSize = _dataSize;
90 :
91 0 : while (node) {
92 0 : int c = ::memcmp(node->getData(), data, dataSize);
93 0 : if (c == 0)
94 : return node;
95 0 : node = node->_link[c < 0];
96 : }
97 :
98 : return nullptr;
99 : }
100 :
101 0 : void ConstPool::Tree::put(ConstPool::Node* newNode) noexcept {
102 0 : size_t dataSize = _dataSize;
103 0 : _length++;
104 :
105 0 : if (!_root) {
106 0 : _root = newNode;
107 0 : return;
108 : }
109 :
110 : ConstPool::Node* node = _root;
111 : ConstPool::Node* stack[kHeightLimit];
112 :
113 : unsigned int top = 0;
114 : unsigned int dir;
115 :
116 : // Find a spot and save the stack.
117 : for (;;) {
118 0 : stack[top++] = node;
119 0 : dir = ::memcmp(node->getData(), newNode->getData(), dataSize) < 0;
120 :
121 0 : ConstPool::Node* link = node->_link[dir];
122 0 : if (!link) break;
123 :
124 : node = link;
125 : }
126 :
127 : // Link and rebalance.
128 0 : node->_link[dir] = newNode;
129 :
130 0 : while (top > 0) {
131 : // Which child?
132 0 : node = stack[--top];
133 :
134 0 : if (top != 0) {
135 0 : dir = stack[top - 1]->_link[1] == node;
136 : }
137 :
138 : node = ConstPoolTree_skewNode(node);
139 : node = ConstPoolTree_splitNode(node);
140 :
141 : // Fix the parent.
142 0 : if (top != 0)
143 0 : stack[top - 1]->_link[dir] = node;
144 : else
145 0 : _root = node;
146 : }
147 : }
148 :
149 : // ============================================================================
150 : // [asmjit::ConstPool - Construction / Destruction]
151 : // ============================================================================
152 :
153 0 : ConstPool::ConstPool(Zone* zone) noexcept { reset(zone); }
154 0 : ConstPool::~ConstPool() noexcept {}
155 :
156 : // ============================================================================
157 : // [asmjit::ConstPool - Reset]
158 : // ============================================================================
159 :
160 0 : void ConstPool::reset(Zone* zone) noexcept {
161 0 : _zone = zone;
162 :
163 : size_t dataSize = 1;
164 0 : for (size_t i = 0; i < ASMJIT_ARRAY_SIZE(_tree); i++) {
165 : _tree[i].reset();
166 : _tree[i].setDataSize(dataSize);
167 0 : _gaps[i] = nullptr;
168 0 : dataSize <<= 1;
169 : }
170 :
171 0 : _gapPool = nullptr;
172 0 : _size = 0;
173 0 : _alignment = 0;
174 0 : }
175 :
176 : // ============================================================================
177 : // [asmjit::ConstPool - Ops]
178 : // ============================================================================
179 :
180 : static ASMJIT_INLINE ConstPool::Gap* ConstPool_allocGap(ConstPool* self) noexcept {
181 0 : ConstPool::Gap* gap = self->_gapPool;
182 0 : if (!gap) return self->_zone->allocT<ConstPool::Gap>();
183 :
184 0 : self->_gapPool = gap->_next;
185 0 : return gap;
186 : }
187 :
188 : static ASMJIT_INLINE void ConstPool_freeGap(ConstPool* self, ConstPool::Gap* gap) noexcept {
189 0 : gap->_next = self->_gapPool;
190 0 : self->_gapPool = gap;
191 : }
192 :
193 0 : static void ConstPool_addGap(ConstPool* self, size_t offset, size_t length) noexcept {
194 : ASMJIT_ASSERT(length > 0);
195 :
196 0 : while (length > 0) {
197 : size_t gapIndex;
198 : size_t gapLength;
199 :
200 : gapIndex = ConstPool::kIndex16;
201 0 : if (length >= 16 && Utils::isAligned<size_t>(offset, 16)) {
202 : gapLength = 16;
203 : }
204 0 : else if (length >= 8 && Utils::isAligned<size_t>(offset, 8)) {
205 : gapIndex = ConstPool::kIndex8;
206 : gapLength = 8;
207 : }
208 0 : else if (length >= 4 && Utils::isAligned<size_t>(offset, 4)) {
209 : gapIndex = ConstPool::kIndex4;
210 : gapLength = 4;
211 : }
212 0 : else if (length >= 2 && Utils::isAligned<size_t>(offset, 2)) {
213 : gapIndex = ConstPool::kIndex2;
214 : gapLength = 2;
215 : }
216 : else {
217 : gapIndex = ConstPool::kIndex1;
218 : gapLength = 1;
219 : }
220 :
221 : // We don't have to check for errors here, if this failed nothing really
222 : // happened (just the gap won't be visible) and it will fail again at
223 : // place where checking will cause kErrorNoHeapMemory.
224 : ConstPool::Gap* gap = ConstPool_allocGap(self);
225 0 : if (!gap) return;
226 :
227 0 : gap->_next = self->_gaps[gapIndex];
228 0 : self->_gaps[gapIndex] = gap;
229 :
230 0 : gap->_offset = offset;
231 0 : gap->_length = gapLength;
232 :
233 0 : offset += gapLength;
234 0 : length -= gapLength;
235 : }
236 : }
237 :
238 0 : Error ConstPool::add(const void* data, size_t size, size_t& dstOffset) noexcept {
239 : size_t treeIndex;
240 :
241 0 : if (size == 32)
242 : treeIndex = kIndex32;
243 : else if (size == 16)
244 : treeIndex = kIndex16;
245 : else if (size == 8)
246 : treeIndex = kIndex8;
247 : else if (size == 4)
248 : treeIndex = kIndex4;
249 : else if (size == 2)
250 : treeIndex = kIndex2;
251 : else if (size == 1)
252 : treeIndex = kIndex1;
253 : else
254 : return DebugUtils::errored(kErrorInvalidArgument);
255 :
256 0 : ConstPool::Node* node = _tree[treeIndex].get(data);
257 0 : if (node) {
258 0 : dstOffset = node->_offset;
259 0 : return kErrorOk;
260 : }
261 :
262 : // Before incrementing the current offset try if there is a gap that can
263 : // be used for the requested data.
264 : size_t offset = ~static_cast<size_t>(0);
265 : size_t gapIndex = treeIndex;
266 :
267 0 : while (gapIndex != kIndexCount - 1) {
268 0 : ConstPool::Gap* gap = _gaps[treeIndex];
269 :
270 : // Check if there is a gap.
271 0 : if (gap) {
272 0 : size_t gapOffset = gap->_offset;
273 0 : size_t gapLength = gap->_length;
274 :
275 : // Destroy the gap for now.
276 0 : _gaps[treeIndex] = gap->_next;
277 : ConstPool_freeGap(this, gap);
278 :
279 : offset = gapOffset;
280 : ASMJIT_ASSERT(Utils::isAligned<size_t>(offset, size));
281 :
282 0 : gapLength -= size;
283 0 : if (gapLength > 0)
284 0 : ConstPool_addGap(this, gapOffset, gapLength);
285 : }
286 :
287 0 : gapIndex++;
288 : }
289 :
290 0 : if (offset == ~static_cast<size_t>(0)) {
291 : // Get how many bytes have to be skipped so the address is aligned accordingly
292 : // to the 'size'.
293 0 : size_t diff = Utils::alignDiff<size_t>(_size, size);
294 :
295 0 : if (diff != 0) {
296 0 : ConstPool_addGap(this, _size, diff);
297 0 : _size += diff;
298 : }
299 :
300 0 : offset = _size;
301 0 : _size += size;
302 : }
303 :
304 : // Add the initial node to the right index.
305 0 : node = ConstPool::Tree::_newNode(_zone, data, size, offset, false);
306 0 : if (!node) return DebugUtils::errored(kErrorNoHeapMemory);
307 :
308 0 : _tree[treeIndex].put(node);
309 0 : _alignment = std::max<size_t>(_alignment, size);
310 :
311 0 : dstOffset = offset;
312 :
313 : // Now create a bunch of shared constants that are based on the data pattern.
314 : // We stop at size 4, it probably doesn't make sense to split constants down
315 : // to 1 byte.
316 : size_t pCount = 1;
317 0 : while (size > 4) {
318 0 : size >>= 1;
319 0 : pCount <<= 1;
320 :
321 : ASMJIT_ASSERT(treeIndex != 0);
322 0 : treeIndex--;
323 :
324 : const uint8_t* pData = static_cast<const uint8_t*>(data);
325 0 : for (size_t i = 0; i < pCount; i++, pData += size) {
326 0 : node = _tree[treeIndex].get(pData);
327 0 : if (node) continue;
328 :
329 0 : node = ConstPool::Tree::_newNode(_zone, pData, size, offset + (i * size), true);
330 0 : _tree[treeIndex].put(node);
331 : }
332 : }
333 :
334 : return kErrorOk;
335 : }
336 :
337 : // ============================================================================
338 : // [asmjit::ConstPool - Reset]
339 : // ============================================================================
340 :
341 : struct ConstPoolFill {
342 : ASMJIT_INLINE ConstPoolFill(uint8_t* dst, size_t dataSize) noexcept :
343 : _dst(dst),
344 : _dataSize(dataSize) {}
345 :
346 : ASMJIT_INLINE void visit(const ConstPool::Node* node) noexcept {
347 0 : if (!node->_shared)
348 0 : ::memcpy(_dst + node->_offset, node->getData(), _dataSize);
349 : }
350 :
351 : uint8_t* _dst;
352 : size_t _dataSize;
353 : };
354 :
355 0 : void ConstPool::fill(void* dst) const noexcept {
356 : // Clears possible gaps, asmjit should never emit garbage to the output.
357 0 : ::memset(dst, 0, _size);
358 :
359 : ConstPoolFill filler(static_cast<uint8_t*>(dst), 1);
360 0 : for (size_t i = 0; i < ASMJIT_ARRAY_SIZE(_tree); i++) {
361 : _tree[i].iterate(filler);
362 0 : filler._dataSize <<= 1;
363 : }
364 0 : }
365 :
366 : // ============================================================================
367 : // [asmjit::ConstPool - Test]
368 : // ============================================================================
369 :
370 : #if defined(ASMJIT_TEST)
371 : UNIT(base_constpool) {
372 : Zone zone(32384 - Zone::kZoneOverhead);
373 : ConstPool pool(&zone);
374 :
375 : uint32_t i;
376 : uint32_t kCount = 1000000;
377 :
378 : INFO("Adding %u constants to the pool.", kCount);
379 : {
380 : size_t prevOffset;
381 : size_t curOffset;
382 : uint64_t c = ASMJIT_UINT64_C(0x0101010101010101);
383 :
384 : EXPECT(pool.add(&c, 8, prevOffset) == kErrorOk,
385 : "pool.add() - Returned error");
386 : EXPECT(prevOffset == 0,
387 : "pool.add() - First constant should have zero offset");
388 :
389 : for (i = 1; i < kCount; i++) {
390 : c++;
391 : EXPECT(pool.add(&c, 8, curOffset) == kErrorOk,
392 : "pool.add() - Returned error");
393 : EXPECT(prevOffset + 8 == curOffset,
394 : "pool.add() - Returned incorrect curOffset");
395 : EXPECT(pool.getSize() == (i + 1) * 8,
396 : "pool.getSize() - Reported incorrect size");
397 : prevOffset = curOffset;
398 : }
399 :
400 : EXPECT(pool.getAlignment() == 8,
401 : "pool.getAlignment() - Expected 8-byte alignment");
402 : }
403 :
404 : INFO("Retrieving %u constants from the pool.", kCount);
405 : {
406 : uint64_t c = ASMJIT_UINT64_C(0x0101010101010101);
407 :
408 : for (i = 0; i < kCount; i++) {
409 : size_t offset;
410 : EXPECT(pool.add(&c, 8, offset) == kErrorOk,
411 : "pool.add() - Returned error");
412 : EXPECT(offset == i * 8,
413 : "pool.add() - Should have reused constant");
414 : c++;
415 : }
416 : }
417 :
418 : INFO("Checking if the constants were split into 4-byte patterns");
419 : {
420 : uint32_t c = 0x01010101;
421 : for (i = 0; i < kCount; i++) {
422 : size_t offset;
423 : EXPECT(pool.add(&c, 4, offset) == kErrorOk,
424 : "pool.add() - Returned error");
425 : EXPECT(offset == i * 8,
426 : "pool.add() - Should reuse existing constant");
427 : c++;
428 : }
429 : }
430 :
431 : INFO("Adding 2 byte constant to misalign the current offset");
432 : {
433 : uint16_t c = 0xFFFF;
434 : size_t offset;
435 :
436 : EXPECT(pool.add(&c, 2, offset) == kErrorOk,
437 : "pool.add() - Returned error");
438 : EXPECT(offset == kCount * 8,
439 : "pool.add() - Didn't return expected position");
440 : EXPECT(pool.getAlignment() == 8,
441 : "pool.getAlignment() - Expected 8-byte alignment");
442 : }
443 :
444 : INFO("Adding 8 byte constant to check if pool gets aligned again");
445 : {
446 : uint64_t c = ASMJIT_UINT64_C(0xFFFFFFFFFFFFFFFF);
447 : size_t offset;
448 :
449 : EXPECT(pool.add(&c, 8, offset) == kErrorOk,
450 : "pool.add() - Returned error");
451 : EXPECT(offset == kCount * 8 + 8,
452 : "pool.add() - Didn't return aligned offset");
453 : }
454 :
455 : INFO("Adding 2 byte constant to verify the gap is filled");
456 : {
457 : uint16_t c = 0xFFFE;
458 : size_t offset;
459 :
460 : EXPECT(pool.add(&c, 2, offset) == kErrorOk,
461 : "pool.add() - Returned error");
462 : EXPECT(offset == kCount * 8 + 2,
463 : "pool.add() - Didn't fill the gap");
464 : EXPECT(pool.getAlignment() == 8,
465 : "pool.getAlignment() - Expected 8-byte alignment");
466 : }
467 :
468 : INFO("Checking reset functionality");
469 : {
470 : pool.reset(&zone);
471 : zone.reset();
472 :
473 : EXPECT(pool.getSize() == 0,
474 : "pool.getSize() - Expected pool size to be zero");
475 : EXPECT(pool.getAlignment() == 0,
476 : "pool.getSize() - Expected pool alignment to be zero");
477 : }
478 :
479 : INFO("Checking pool alignment when combined constants are added");
480 : {
481 : uint8_t bytes[32] = { 0 };
482 : size_t offset;
483 :
484 : pool.add(bytes, 1, offset);
485 :
486 : EXPECT(pool.getSize() == 1,
487 : "pool.getSize() - Expected pool size to be 1 byte");
488 : EXPECT(pool.getAlignment() == 1,
489 : "pool.getSize() - Expected pool alignment to be 1 byte");
490 : EXPECT(offset == 0,
491 : "pool.getSize() - Expected offset returned to be zero");
492 :
493 : pool.add(bytes, 2, offset);
494 :
495 : EXPECT(pool.getSize() == 4,
496 : "pool.getSize() - Expected pool size to be 4 bytes");
497 : EXPECT(pool.getAlignment() == 2,
498 : "pool.getSize() - Expected pool alignment to be 2 bytes");
499 : EXPECT(offset == 2,
500 : "pool.getSize() - Expected offset returned to be 2");
501 :
502 : pool.add(bytes, 4, offset);
503 :
504 : EXPECT(pool.getSize() == 8,
505 : "pool.getSize() - Expected pool size to be 8 bytes");
506 : EXPECT(pool.getAlignment() == 4,
507 : "pool.getSize() - Expected pool alignment to be 4 bytes");
508 : EXPECT(offset == 4,
509 : "pool.getSize() - Expected offset returned to be 4");
510 :
511 : pool.add(bytes, 4, offset);
512 :
513 : EXPECT(pool.getSize() == 8,
514 : "pool.getSize() - Expected pool size to be 8 bytes");
515 : EXPECT(pool.getAlignment() == 4,
516 : "pool.getSize() - Expected pool alignment to be 4 bytes");
517 : EXPECT(offset == 4,
518 : "pool.getSize() - Expected offset returned to be 8");
519 :
520 : pool.add(bytes, 32, offset);
521 : EXPECT(pool.getSize() == 64,
522 : "pool.getSize() - Expected pool size to be 64 bytes");
523 : EXPECT(pool.getAlignment() == 32,
524 : "pool.getSize() - Expected pool alignment to be 32 bytes");
525 : EXPECT(offset == 32,
526 : "pool.getSize() - Expected offset returned to be 32");
527 : }
528 : }
529 : #endif // ASMJIT_TEST
530 :
531 : } // asmjit namespace
532 : } // namespace PLMD
533 :
534 : // [Api-End]
535 : #include "./asmjit_apiend.h"
536 : #pragma GCC diagnostic pop
537 : #endif // __PLUMED_HAS_ASMJIT
|
