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 : #ifndef __PLUMED_asmjit_regalloc_p_h
21 : #define __PLUMED_asmjit_regalloc_p_h
22 : #ifdef __PLUMED_HAS_ASMJIT
23 : #pragma GCC diagnostic push
24 : #pragma GCC diagnostic ignored "-Wpedantic"
25 : // [AsmJit]
26 : // Complete x86/x64 JIT and Remote Assembler for C++.
27 : //
28 : // [License]
29 : // Zlib - See LICENSE.md file in the package.
30 :
31 : // [Guard]
32 : #ifndef _ASMJIT_BASE_REGALLOC_P_H
33 : #define _ASMJIT_BASE_REGALLOC_P_H
34 :
35 : #include "./asmjit_build.h"
36 : #if !defined(ASMJIT_DISABLE_COMPILER)
37 :
38 : // [Dependencies]
39 : #include "./codecompiler.h"
40 : #include "./zone.h"
41 :
42 : // [Api-Begin]
43 : #include "./asmjit_apibegin.h"
44 :
45 : namespace PLMD {
46 : namespace asmjit {
47 :
48 : //! \addtogroup asmjit_base
49 : //! \{
50 :
51 : // ============================================================================
52 : // [asmjit::TiedReg]
53 : // ============================================================================
54 :
55 : //! Tied register (CodeCompiler)
56 : //!
57 : //! Tied register is used to describe one ore more register operands that share
58 : //! the same virtual register. Tied register contains all the data that is
59 : //! essential for register allocation.
60 : struct TiedReg {
61 : //! Flags.
62 : ASMJIT_ENUM(Flags) {
63 : kRReg = 0x00000001U, //!< Register read.
64 : kWReg = 0x00000002U, //!< Register write.
65 : kXReg = 0x00000003U, //!< Register read-write.
66 :
67 : kRMem = 0x00000004U, //!< Memory read.
68 : kWMem = 0x00000008U, //!< Memory write.
69 : kXMem = 0x0000000CU, //!< Memory read-write.
70 :
71 : kRDecide = 0x00000010U, //!< RA can decide between reg/mem read.
72 : kWDecide = 0x00000020U, //!< RA can decide between reg/mem write.
73 : kXDecide = 0x00000030U, //!< RA can decide between reg/mem read-write.
74 :
75 : kRFunc = 0x00000100U, //!< Function argument passed in register.
76 : kWFunc = 0x00000200U, //!< Function return value passed into register.
77 : kXFunc = 0x00000300U, //!< Function argument and return value.
78 : kRCall = 0x00000400U, //!< Function call operand.
79 :
80 : kSpill = 0x00000800U, //!< Variable should be spilled.
81 : kUnuse = 0x00001000U, //!< Variable should be unused at the end of the instruction/node.
82 :
83 : kRAll = kRReg | kRMem | kRDecide | kRFunc | kRCall, //!< All in-flags.
84 : kWAll = kWReg | kWMem | kWDecide | kWFunc, //!< All out-flags.
85 :
86 : kRDone = 0x00400000U, //!< Already allocated on the input.
87 : kWDone = 0x00800000U, //!< Already allocated on the output.
88 :
89 : kX86GpbLo = 0x10000000U,
90 : kX86GpbHi = 0x20000000U,
91 : kX86Fld4 = 0x40000000U,
92 : kX86Fld8 = 0x80000000U
93 : };
94 :
95 : // --------------------------------------------------------------------------
96 : // [Init / Reset]
97 : // --------------------------------------------------------------------------
98 :
99 : ASMJIT_INLINE void init(VirtReg* vreg, uint32_t flags = 0, uint32_t inRegs = 0, uint32_t allocableRegs = 0) noexcept {
100 793577 : this->vreg = vreg;
101 793577 : this->flags = flags;
102 793577 : this->refCount = 0;
103 793577 : this->inPhysId = Globals::kInvalidRegId;
104 793577 : this->outPhysId = Globals::kInvalidRegId;
105 793577 : this->reserved = 0;
106 793577 : this->inRegs = inRegs;
107 13122 : this->allocableRegs = allocableRegs;
108 : }
109 :
110 : // --------------------------------------------------------------------------
111 : // [Accessors]
112 : // --------------------------------------------------------------------------
113 :
114 : //! Get whether the variable has to be allocated in a specific input register.
115 63602 : ASMJIT_INLINE uint32_t hasInPhysId() const { return inPhysId != Globals::kInvalidRegId; }
116 : //! Get whether the variable has to be allocated in a specific output register.
117 368292 : ASMJIT_INLINE uint32_t hasOutPhysId() const { return outPhysId != Globals::kInvalidRegId; }
118 :
119 : //! Set the input register index.
120 475765 : ASMJIT_INLINE void setInPhysId(uint32_t index) { inPhysId = static_cast<uint8_t>(index); }
121 : //! Set the output register index.
122 317812 : ASMJIT_INLINE void setOutPhysId(uint32_t index) { outPhysId = static_cast<uint8_t>(index); }
123 :
124 : // --------------------------------------------------------------------------
125 : // [Operator Overload]
126 : // --------------------------------------------------------------------------
127 :
128 : ASMJIT_INLINE TiedReg& operator=(const TiedReg& other) {
129 : ::memcpy(this, &other, sizeof(TiedReg));
130 : return *this;
131 : }
132 :
133 : // --------------------------------------------------------------------------
134 : // [Members]
135 : // --------------------------------------------------------------------------
136 :
137 : //! Pointer to the associated \ref VirtReg.
138 : VirtReg* vreg;
139 : //! Tied flags.
140 : uint32_t flags;
141 :
142 : union {
143 : struct {
144 : //! How many times the variable is used by the instruction/node.
145 : uint8_t refCount;
146 : //! Input register index or `kInvalidReg` if it's not given.
147 : //!
148 : //! Even if the input register index is not given (i.e. it may by any
149 : //! register), register allocator should assign an index that will be
150 : //! used to persist a variable into this specific index. It's helpful
151 : //! in situations where one variable has to be allocated in multiple
152 : //! registers to determine the register which will be persistent.
153 : uint8_t inPhysId;
154 : //! Output register index or `kInvalidReg` if it's not given.
155 : //!
156 : //! Typically `kInvalidReg` if variable is only used on input.
157 : uint8_t outPhysId;
158 : //! \internal
159 : uint8_t reserved;
160 : };
161 :
162 : //! \internal
163 : //!
164 : //! Packed data #0.
165 : uint32_t packed;
166 : };
167 :
168 : //! Mandatory input registers.
169 : //!
170 : //! Mandatory input registers are required by the instruction even if
171 : //! there are duplicates. This schema allows us to allocate one variable
172 : //! in one or more register when needed. Required mostly by instructions
173 : //! that have implicit register operands (imul, cpuid, ...) and function
174 : //! call.
175 : uint32_t inRegs;
176 :
177 : //! Allocable input registers.
178 : //!
179 : //! Optional input registers is a mask of all allocable registers for a given
180 : //! variable where we have to pick one of them. This mask is usually not used
181 : //! when _inRegs is set. If both masks are used then the register
182 : //! allocator tries first to find an intersection between these and allocates
183 : //! an extra slot if not found.
184 : uint32_t allocableRegs;
185 : };
186 :
187 : // ============================================================================
188 : // [asmjit::RABits]
189 : // ============================================================================
190 :
191 : //! Fixed size bit-array.
192 : //!
193 : //! Used by variable liveness analysis.
194 : struct RABits {
195 : // --------------------------------------------------------------------------
196 : // [Enums]
197 : // --------------------------------------------------------------------------
198 :
199 : enum {
200 : kEntitySize = static_cast<int>(sizeof(uintptr_t)),
201 : kEntityBits = kEntitySize * 8
202 : };
203 :
204 : // --------------------------------------------------------------------------
205 : // [Accessors]
206 : // --------------------------------------------------------------------------
207 :
208 : ASMJIT_INLINE uintptr_t getBit(uint32_t index) const noexcept {
209 2970257 : return (data[index / kEntityBits] >> (index % kEntityBits)) & 1;
210 : }
211 :
212 : ASMJIT_INLINE void setBit(uint32_t index) noexcept {
213 793577 : data[index / kEntityBits] |= static_cast<uintptr_t>(1) << (index % kEntityBits);
214 475765 : }
215 :
216 : ASMJIT_INLINE void delBit(uint32_t index) noexcept {
217 317812 : data[index / kEntityBits] &= ~(static_cast<uintptr_t>(1) << (index % kEntityBits));
218 317812 : }
219 :
220 : // --------------------------------------------------------------------------
221 : // [Interface]
222 : // --------------------------------------------------------------------------
223 :
224 : //! Copy bits from `s0`, returns `true` if at least one bit is set in `s0`.
225 : ASMJIT_INLINE bool copyBits(const RABits* s0, uint32_t len) noexcept {
226 : uintptr_t r = 0;
227 0 : for (uint32_t i = 0; i < len; i++) {
228 0 : uintptr_t t = s0->data[i];
229 0 : data[i] = t;
230 : r |= t;
231 : }
232 : return r != 0;
233 : }
234 :
235 : ASMJIT_INLINE bool addBits(const RABits* s0, uint32_t len) noexcept {
236 : return addBits(this, s0, len);
237 : }
238 :
239 : ASMJIT_INLINE bool addBits(const RABits* s0, const RABits* s1, uint32_t len) noexcept {
240 : uintptr_t r = 0;
241 : for (uint32_t i = 0; i < len; i++) {
242 : uintptr_t t = s0->data[i] | s1->data[i];
243 : data[i] = t;
244 : r |= t;
245 : }
246 : return r != 0;
247 : }
248 :
249 : ASMJIT_INLINE bool andBits(const RABits* s1, uint32_t len) noexcept {
250 : return andBits(this, s1, len);
251 : }
252 :
253 : ASMJIT_INLINE bool andBits(const RABits* s0, const RABits* s1, uint32_t len) noexcept {
254 : uintptr_t r = 0;
255 : for (uint32_t i = 0; i < len; i++) {
256 : uintptr_t t = s0->data[i] & s1->data[i];
257 : data[i] = t;
258 : r |= t;
259 : }
260 : return r != 0;
261 : }
262 :
263 : ASMJIT_INLINE bool delBits(const RABits* s1, uint32_t len) noexcept {
264 : return delBits(this, s1, len);
265 : }
266 :
267 : ASMJIT_INLINE bool delBits(const RABits* s0, const RABits* s1, uint32_t len) noexcept {
268 : uintptr_t r = 0;
269 0 : for (uint32_t i = 0; i < len; i++) {
270 0 : uintptr_t t = s0->data[i] & ~s1->data[i];
271 0 : data[i] = t;
272 0 : r |= t;
273 : }
274 : return r != 0;
275 : }
276 :
277 : ASMJIT_INLINE bool _addBitsDelSource(RABits* s1, uint32_t len) noexcept {
278 : return _addBitsDelSource(this, s1, len);
279 : }
280 :
281 : ASMJIT_INLINE bool _addBitsDelSource(const RABits* s0, RABits* s1, uint32_t len) noexcept {
282 : uintptr_t r = 0;
283 0 : for (uint32_t i = 0; i < len; i++) {
284 0 : uintptr_t a = s0->data[i];
285 0 : uintptr_t b = s1->data[i];
286 :
287 0 : this->data[i] = a | b;
288 0 : b &= ~a;
289 :
290 0 : s1->data[i] = b;
291 0 : r |= b;
292 : }
293 : return r != 0;
294 : }
295 :
296 : // --------------------------------------------------------------------------
297 : // [Members]
298 : // --------------------------------------------------------------------------
299 :
300 : uintptr_t data[1];
301 : };
302 :
303 : // ============================================================================
304 : // [asmjit::RACell]
305 : // ============================================================================
306 :
307 : //! Register allocator's (RA) memory cell.
308 : struct RACell {
309 : RACell* next; //!< Next active cell.
310 : int32_t offset; //!< Cell offset, relative to base-offset.
311 : uint32_t size; //!< Cell size.
312 : uint32_t alignment; //!< Cell alignment.
313 : };
314 :
315 : // ============================================================================
316 : // [asmjit::RAData]
317 : // ============================================================================
318 :
319 : //! Register allocator's (RA) data associated with each \ref CBNode.
320 : struct RAData {
321 : ASMJIT_INLINE RAData(uint32_t tiedTotal) noexcept
322 558149 : : liveness(nullptr),
323 558149 : state(nullptr),
324 558149 : tiedTotal(tiedTotal) {}
325 :
326 : RABits* liveness; //!< Liveness bits (populated by liveness-analysis).
327 : RAState* state; //!< Optional saved \ref RAState.
328 : uint32_t tiedTotal; //!< Total count of \ref TiedReg regs.
329 : };
330 :
331 : // ============================================================================
332 : // [asmjit::RAState]
333 : // ============================================================================
334 :
335 : //! Variables' state.
336 : struct RAState {};
337 :
338 : // ============================================================================
339 : // [asmjit::RAPass]
340 : // ============================================================================
341 :
342 : //! \internal
343 : //!
344 : //! Register allocator pipeline used by \ref CodeCompiler.
345 : struct RAPass : public CBPass {
346 : public:
347 : ASMJIT_NONCOPYABLE(RAPass)
348 :
349 : typedef void (ASMJIT_CDECL* TraceNodeFunc)(RAPass* self, CBNode* node_, const char* prefix);
350 :
351 : // --------------------------------------------------------------------------
352 : // [Construction / Destruction]
353 : // --------------------------------------------------------------------------
354 :
355 : RAPass() noexcept;
356 : virtual ~RAPass() noexcept;
357 :
358 : // --------------------------------------------------------------------------
359 : // [Interface]
360 : // --------------------------------------------------------------------------
361 :
362 : virtual Error process(Zone* zone) noexcept override;
363 :
364 : //! Run the register allocator for a given function `func`.
365 : virtual Error compile(CCFunc* func) noexcept;
366 :
367 : //! Called by `compile()` to prepare the register allocator to process the
368 : //! given function. It should reset and set-up everything (i.e. no states
369 : //! from a previous compilation should prevail).
370 : virtual Error prepare(CCFunc* func) noexcept;
371 :
372 : //! Called after `compile()` to clean everything up, no matter if it
373 : //! succeeded or failed.
374 : virtual void cleanup() noexcept;
375 :
376 : // --------------------------------------------------------------------------
377 : // [Accessors]
378 : // --------------------------------------------------------------------------
379 :
380 : //! Get the associated `CodeCompiler`.
381 64222 : ASMJIT_INLINE CodeCompiler* cc() const noexcept { return static_cast<CodeCompiler*>(_cb); }
382 :
383 : //! Get function.
384 64222 : ASMJIT_INLINE CCFunc* getFunc() const noexcept { return _func; }
385 : //! Get stop node.
386 96333 : ASMJIT_INLINE CBNode* getStop() const noexcept { return _stop; }
387 :
388 : // --------------------------------------------------------------------------
389 : // [State]
390 : // --------------------------------------------------------------------------
391 :
392 : //! Get current state.
393 : ASMJIT_INLINE RAState* getState() const { return _state; }
394 :
395 : //! Load current state from `target` state.
396 : virtual void loadState(RAState* src) = 0;
397 :
398 : //! Save current state, returning new `RAState` instance.
399 : virtual RAState* saveState() = 0;
400 :
401 : //! Change the current state to `target` state.
402 : virtual void switchState(RAState* src) = 0;
403 :
404 : //! Change the current state to the intersection of two states `a` and `b`.
405 : virtual void intersectStates(RAState* a, RAState* b) = 0;
406 :
407 : // --------------------------------------------------------------------------
408 : // [Context]
409 : // --------------------------------------------------------------------------
410 :
411 : ASMJIT_INLINE Error assignRAId(VirtReg* vreg) noexcept {
412 : // Likely as a single virtual register would be mostly used more than once,
413 : // this means that each virtual register will hit one bad case (doesn't
414 : // have id) and then all likely cases.
415 793577 : if (ASMJIT_LIKELY(vreg->_raId != kInvalidValue)) return kErrorOk;
416 :
417 317812 : uint32_t raId = static_cast<uint32_t>(_contextVd.getLength());
418 317812 : ASMJIT_PROPAGATE(_contextVd.append(&_heap, vreg));
419 :
420 317812 : vreg->_raId = raId;
421 0 : return kErrorOk;
422 : }
423 :
424 : // --------------------------------------------------------------------------
425 : // [Mem]
426 : // --------------------------------------------------------------------------
427 :
428 : RACell* _newVarCell(VirtReg* vreg);
429 : RACell* _newStackCell(uint32_t size, uint32_t alignment);
430 :
431 : ASMJIT_INLINE RACell* getVarCell(VirtReg* vreg) {
432 : RACell* cell = vreg->getMemCell();
433 92292 : return cell ? cell : _newVarCell(vreg);
434 : }
435 :
436 : virtual Error resolveCellOffsets();
437 :
438 : // --------------------------------------------------------------------------
439 : // [Bits]
440 : // --------------------------------------------------------------------------
441 :
442 : ASMJIT_INLINE RABits* newBits(uint32_t len) {
443 : return static_cast<RABits*>(
444 32111 : _zone->allocZeroed(static_cast<size_t>(len) * RABits::kEntitySize));
445 : }
446 :
447 : ASMJIT_INLINE RABits* copyBits(const RABits* src, uint32_t len) {
448 : return static_cast<RABits*>(
449 493927 : _zone->dup(src, static_cast<size_t>(len) * RABits::kEntitySize));
450 : }
451 :
452 : // --------------------------------------------------------------------------
453 : // [Fetch]
454 : // --------------------------------------------------------------------------
455 :
456 : //! Fetch.
457 : //!
458 : //! Fetch iterates over all nodes and gathers information about all variables
459 : //! used. The process generates information required by register allocator,
460 : //! variable liveness analysis and translator.
461 : virtual Error fetch() = 0;
462 :
463 : // --------------------------------------------------------------------------
464 : // [Unreachable Code]
465 : // --------------------------------------------------------------------------
466 :
467 : //! Add unreachable-flow data to the unreachable flow list.
468 : ASMJIT_INLINE Error addUnreachableNode(CBNode* node) {
469 32111 : ZoneList<CBNode*>::Link* link = _zone->allocT<ZoneList<CBNode*>::Link>();
470 32111 : if (!link) return DebugUtils::errored(kErrorNoHeapMemory);
471 :
472 : link->setValue(node);
473 : _unreachableList.append(link);
474 :
475 32111 : return kErrorOk;
476 : }
477 :
478 : //! Remove unreachable code.
479 : virtual Error removeUnreachableCode();
480 :
481 : // --------------------------------------------------------------------------
482 : // [Code-Flow]
483 : // --------------------------------------------------------------------------
484 :
485 : //! Add returning node (i.e. node that returns and where liveness analysis
486 : //! should start).
487 : ASMJIT_INLINE Error addReturningNode(CBNode* node) {
488 32111 : ZoneList<CBNode*>::Link* link = _zone->allocT<ZoneList<CBNode*>::Link>();
489 32111 : if (!link) return DebugUtils::errored(kErrorNoHeapMemory);
490 :
491 : link->setValue(node);
492 : _returningList.append(link);
493 :
494 32111 : return kErrorOk;
495 : }
496 :
497 : //! Add jump-flow data to the jcc flow list.
498 : ASMJIT_INLINE Error addJccNode(CBNode* node) {
499 0 : ZoneList<CBNode*>::Link* link = _zone->allocT<ZoneList<CBNode*>::Link>();
500 0 : if (!link) return DebugUtils::errored(kErrorNoHeapMemory);
501 :
502 : link->setValue(node);
503 : _jccList.append(link);
504 :
505 0 : return kErrorOk;
506 : }
507 :
508 : // --------------------------------------------------------------------------
509 : // [Analyze]
510 : // --------------------------------------------------------------------------
511 :
512 : //! Perform variable liveness analysis.
513 : //!
514 : //! Analysis phase iterates over nodes in reverse order and generates a bit
515 : //! array describing variables that are alive at every node in the function.
516 : //! When the analysis start all variables are assumed dead. When a read or
517 : //! read/write operations of a variable is detected the variable becomes
518 : //! alive; when only write operation is detected the variable becomes dead.
519 : //!
520 : //! When a label is found all jumps to that label are followed and analysis
521 : //! repeats until all variables are resolved.
522 : virtual Error livenessAnalysis();
523 :
524 : // --------------------------------------------------------------------------
525 : // [Annotate]
526 : // --------------------------------------------------------------------------
527 :
528 : virtual Error annotate() = 0;
529 : virtual Error formatInlineComment(StringBuilder& dst, CBNode* node);
530 :
531 : // --------------------------------------------------------------------------
532 : // [Translate]
533 : // --------------------------------------------------------------------------
534 :
535 : //! Translate code by allocating registers and handling state changes.
536 : virtual Error translate() = 0;
537 :
538 : // --------------------------------------------------------------------------
539 : // [Members]
540 : // --------------------------------------------------------------------------
541 :
542 : Zone* _zone; //!< Zone passed to `process()`.
543 : ZoneHeap _heap; //!< ZoneHeap that uses `_zone`.
544 :
545 : CCFunc* _func; //!< Function being processed.
546 : CBNode* _stop; //!< Stop node.
547 :
548 : //! \internal
549 : //!
550 : //! Offset (how many bytes to add) to `VarMap` to get `TiedReg` array. Used
551 : //! by liveness analysis shared across all backends. This is needed because
552 : //! `VarMap` is a base class for a specialized version that liveness analysis
553 : //! doesn't use, it just needs `TiedReg` array.
554 : uint32_t _varMapToVaListOffset;
555 :
556 : uint8_t _emitComments; //!< Whether to emit comments.
557 :
558 : ZoneList<CBNode*> _unreachableList; //!< Unreachable nodes.
559 : ZoneList<CBNode*> _returningList; //!< Returning nodes.
560 : ZoneList<CBNode*> _jccList; //!< Jump nodes.
561 :
562 : ZoneVector<VirtReg*> _contextVd; //!< All variables used by the current function.
563 : RACell* _memVarCells; //!< Memory used to spill variables.
564 : RACell* _memStackCells; //!< Memory used to allocate memory on the stack.
565 :
566 : uint32_t _mem1ByteVarsUsed; //!< Count of 1-byte cells.
567 : uint32_t _mem2ByteVarsUsed; //!< Count of 2-byte cells.
568 : uint32_t _mem4ByteVarsUsed; //!< Count of 4-byte cells.
569 : uint32_t _mem8ByteVarsUsed; //!< Count of 8-byte cells.
570 : uint32_t _mem16ByteVarsUsed; //!< Count of 16-byte cells.
571 : uint32_t _mem32ByteVarsUsed; //!< Count of 32-byte cells.
572 : uint32_t _mem64ByteVarsUsed; //!< Count of 64-byte cells.
573 : uint32_t _memStackCellsUsed; //!< Count of stack memory cells.
574 :
575 : uint32_t _memMaxAlign; //!< Maximum memory alignment used by the function.
576 : uint32_t _memVarTotal; //!< Count of bytes used by variables.
577 : uint32_t _memStackTotal; //!< Count of bytes used by stack.
578 : uint32_t _memAllTotal; //!< Count of bytes used by variables and stack after alignment.
579 :
580 : uint32_t _annotationLength; //!< Default length of an annotated instruction.
581 : RAState* _state; //!< Current RA state.
582 : };
583 :
584 : //! \}
585 :
586 : } // asmjit namespace
587 : } // namespace PLMD
588 :
589 : // [Api-End]
590 : #include "./asmjit_apiend.h"
591 :
592 : // [Guard]
593 : #endif // !ASMJIT_DISABLE_COMPILER
594 : #endif // _ASMJIT_BASE_REGALLOC_P_H
595 : #pragma GCC diagnostic pop
596 : #endif // __PLUMED_HAS_ASMJIT
597 : #endif
|
