summaryrefslogtreecommitdiffstatshomepage
path: root/3rdparty/asmjit/src/asmjit/core/rabuilders_p.h
diff options
context:
space:
mode:
Diffstat (limited to '3rdparty/asmjit/src/asmjit/core/rabuilders_p.h')
-rw-r--r--3rdparty/asmjit/src/asmjit/core/rabuilders_p.h632
1 files changed, 632 insertions, 0 deletions
diff --git a/3rdparty/asmjit/src/asmjit/core/rabuilders_p.h b/3rdparty/asmjit/src/asmjit/core/rabuilders_p.h
new file mode 100644
index 00000000000..6f400ad1c3a
--- /dev/null
+++ b/3rdparty/asmjit/src/asmjit/core/rabuilders_p.h
@@ -0,0 +1,632 @@
+// AsmJit - Machine code generation for C++
+//
+// * Official AsmJit Home Page: https://asmjit.com
+// * Official Github Repository: https://github.com/asmjit/asmjit
+//
+// Copyright (c) 2008-2020 The AsmJit Authors
+//
+// This software is provided 'as-is', without any express or implied
+// warranty. In no event will the authors be held liable for any damages
+// arising from the use of this software.
+//
+// Permission is granted to anyone to use this software for any purpose,
+// including commercial applications, and to alter it and redistribute it
+// freely, subject to the following restrictions:
+//
+// 1. The origin of this software must not be misrepresented; you must not
+// claim that you wrote the original software. If you use this software
+// in a product, an acknowledgment in the product documentation would be
+// appreciated but is not required.
+// 2. Altered source versions must be plainly marked as such, and must not be
+// misrepresented as being the original software.
+// 3. This notice may not be removed or altered from any source distribution.
+
+#ifndef ASMJIT_CORE_RABUILDERS_P_H_INCLUDED
+#define ASMJIT_CORE_RABUILDERS_P_H_INCLUDED
+
+#include "../core/api-config.h"
+#ifndef ASMJIT_NO_COMPILER
+
+#include "../core/rapass_p.h"
+
+ASMJIT_BEGIN_NAMESPACE
+
+//! \cond INTERNAL
+//! \addtogroup asmjit_ra
+//! \{
+
+// ============================================================================
+// [asmjit::RACFGBuilder]
+// ============================================================================
+
+template<typename This>
+class RACFGBuilder {
+public:
+ RAPass* _pass;
+ BaseCompiler* _cc;
+
+ RABlock* _curBlock;
+ RABlock* _retBlock;
+ FuncNode* _funcNode;
+ RARegsStats _blockRegStats;
+ uint32_t _exitLabelId;
+ ZoneVector<uint32_t> _sharedAssignmentsMap;
+
+ // Only used by logging, it's fine to be here to prevent more #ifdefs...
+ bool _hasCode;
+ RABlock* _lastLoggedBlock;
+
+#ifndef ASMJIT_NO_LOGGING
+ Logger* _logger;
+ uint32_t _logFlags;
+ StringTmp<512> _sb;
+#endif
+
+ static constexpr uint32_t kRootIndentation = 2;
+ static constexpr uint32_t kCodeIndentation = 4;
+
+ // NOTE: This is a bit hacky. There are some nodes which are processed twice
+ // (see `onBeforeCall()` and `onBeforeRet()`) as they can insert some nodes
+ // around them. Since we don't have any flags to mark these we just use their
+ // position that is [at that time] unassigned.
+ static constexpr uint32_t kNodePositionDidOnBefore = 0xFFFFFFFFu;
+
+ inline RACFGBuilder(RAPass* pass) noexcept
+ : _pass(pass),
+ _cc(pass->cc()),
+ _curBlock(nullptr),
+ _retBlock(nullptr),
+ _funcNode(nullptr),
+ _blockRegStats{},
+ _exitLabelId(Globals::kInvalidId),
+ _hasCode(false),
+ _lastLoggedBlock(nullptr) {
+#ifndef ASMJIT_NO_LOGGING
+ _logger = _pass->debugLogger();
+ _logFlags = FormatOptions::kFlagPositions;
+
+ if (_logger)
+ _logFlags |= _logger->flags();
+#endif
+ }
+
+ inline BaseCompiler* cc() const noexcept { return _cc; }
+
+ // --------------------------------------------------------------------------
+ // [Run]
+ // --------------------------------------------------------------------------
+
+ //! Called per function by an architecture-specific CFG builder.
+ Error run() noexcept {
+ log("[RAPass::BuildCFG]\n");
+ ASMJIT_PROPAGATE(prepare());
+
+ logNode(_funcNode, kRootIndentation);
+ logBlock(_curBlock, kRootIndentation);
+
+ BaseNode* node = _funcNode->next();
+ if (ASMJIT_UNLIKELY(!node))
+ return DebugUtils::errored(kErrorInvalidState);
+
+ _curBlock->setFirst(node);
+ _curBlock->setLast(node);
+
+ RAInstBuilder ib;
+ ZoneVector<RABlock*> blocksWithUnknownJumps;
+
+ for (;;) {
+ BaseNode* next = node->next();
+ ASMJIT_ASSERT(node->position() == 0 || node->position() == kNodePositionDidOnBefore);
+
+ if (node->isInst()) {
+ // Instruction | Jump | Invoke | Return
+ // ------------------------------------
+
+ // Handle `InstNode`, `FuncCallNode`, and `FuncRetNode`. All of them
+ // share the same interface that provides operands that have read/write
+ // semantics.
+ if (ASMJIT_UNLIKELY(!_curBlock)) {
+ // Unreachable code has to be removed, we cannot allocate registers
+ // in such code as we cannot do proper liveness analysis in such case.
+ removeNode(node);
+ node = next;
+ continue;
+ }
+
+ _hasCode = true;
+
+ if (node->isFuncCall() || node->isFuncRet()) {
+ if (node->position() != kNodePositionDidOnBefore) {
+ // Call and Reg are complicated as they may insert some surrounding
+ // code around them. The simplest approach is to get the previous
+ // node, call the `onBefore()` handlers and then check whether
+ // anything changed and restart if so. By restart we mean that the
+ // current `node` would go back to the first possible inserted node
+ // by `onBeforeCall()` or `onBeforeRet()`.
+ BaseNode* prev = node->prev();
+
+ if (node->type() == BaseNode::kNodeFuncCall)
+ ASMJIT_PROPAGATE(static_cast<This*>(this)->onBeforeCall(node->as<FuncCallNode>()));
+ else
+ ASMJIT_PROPAGATE(static_cast<This*>(this)->onBeforeRet(node->as<FuncRetNode>()));
+
+ if (prev != node->prev()) {
+ // If this was the first node in the block and something was
+ // inserted before it then we have to update the first block.
+ if (_curBlock->first() == node)
+ _curBlock->setFirst(prev->next());
+
+ node->setPosition(kNodePositionDidOnBefore);
+ node = prev->next();
+
+ // `onBeforeCall()` and `onBeforeRet()` can only insert instructions.
+ ASMJIT_ASSERT(node->isInst());
+ }
+
+ // Necessary if something was inserted after `node`, but nothing before.
+ next = node->next();
+ }
+ else {
+ // Change the position back to its original value.
+ node->setPosition(0);
+ }
+ }
+
+ InstNode* inst = node->as<InstNode>();
+ logNode(inst, kCodeIndentation);
+
+ uint32_t controlType = BaseInst::kControlNone;
+ ib.reset();
+ ASMJIT_PROPAGATE(static_cast<This*>(this)->onInst(inst, controlType, ib));
+
+ if (node->isFuncCall()) {
+ ASMJIT_PROPAGATE(static_cast<This*>(this)->onCall(inst->as<FuncCallNode>(), ib));
+ }
+
+ if (node->isFuncRet()) {
+ ASMJIT_PROPAGATE(static_cast<This*>(this)->onRet(inst->as<FuncRetNode>(), ib));
+ controlType = BaseInst::kControlReturn;
+ }
+
+ if (controlType == BaseInst::kControlJump) {
+ uint32_t fixedRegCount = 0;
+ for (RATiedReg& tiedReg : ib) {
+ RAWorkReg* workReg = _pass->workRegById(tiedReg.workId());
+ if (workReg->group() == BaseReg::kGroupGp) {
+ uint32_t useId = tiedReg.useId();
+ if (useId == BaseReg::kIdBad) {
+ useId = _pass->_scratchRegIndexes[fixedRegCount++];
+ tiedReg.setUseId(useId);
+ }
+ _curBlock->addExitScratchGpRegs(Support::bitMask<uint32_t>(useId));
+ }
+ }
+ }
+
+ ASMJIT_PROPAGATE(_pass->assignRAInst(inst, _curBlock, ib));
+ _blockRegStats.combineWith(ib._stats);
+
+ if (controlType != BaseInst::kControlNone) {
+ // Support for conditional and unconditional jumps.
+ if (controlType == BaseInst::kControlJump || controlType == BaseInst::kControlBranch) {
+ _curBlock->setLast(node);
+ _curBlock->addFlags(RABlock::kFlagHasTerminator);
+ _curBlock->makeConstructed(_blockRegStats);
+
+ if (!(inst->instOptions() & BaseInst::kOptionUnfollow)) {
+ // Jmp/Jcc/Call/Loop/etc...
+ uint32_t opCount = inst->opCount();
+ const Operand* opArray = inst->operands();
+
+ // Cannot jump anywhere without operands.
+ if (ASMJIT_UNLIKELY(!opCount))
+ return DebugUtils::errored(kErrorInvalidState);
+
+ if (opArray[opCount - 1].isLabel()) {
+ // Labels are easy for constructing the control flow.
+ LabelNode* labelNode;
+ ASMJIT_PROPAGATE(cc()->labelNodeOf(&labelNode, opArray[opCount - 1].as<Label>()));
+
+ RABlock* targetBlock = _pass->newBlockOrExistingAt(labelNode);
+ if (ASMJIT_UNLIKELY(!targetBlock))
+ return DebugUtils::errored(kErrorOutOfMemory);
+
+ ASMJIT_PROPAGATE(_curBlock->appendSuccessor(targetBlock));
+ }
+ else {
+ // Not a label - could be jump with reg/mem operand, which
+ // means that it can go anywhere. Such jumps must either be
+ // annotated so the CFG can be properly constructed, otherwise
+ // we assume the worst case - can jump to every basic block.
+ JumpAnnotation* jumpAnnotation = nullptr;
+ if (inst->type() == BaseNode::kNodeJump)
+ jumpAnnotation = inst->as<JumpNode>()->annotation();
+
+ if (jumpAnnotation) {
+ uint64_t timestamp = _pass->nextTimestamp();
+ for (uint32_t id : jumpAnnotation->labelIds()) {
+ LabelNode* labelNode;
+ ASMJIT_PROPAGATE(cc()->labelNodeOf(&labelNode, id));
+
+ RABlock* targetBlock = _pass->newBlockOrExistingAt(labelNode);
+ if (ASMJIT_UNLIKELY(!targetBlock))
+ return DebugUtils::errored(kErrorOutOfMemory);
+
+ // Prevents adding basic-block successors multiple times.
+ if (!targetBlock->hasTimestamp(timestamp)) {
+ targetBlock->setTimestamp(timestamp);
+ ASMJIT_PROPAGATE(_curBlock->appendSuccessor(targetBlock));
+ }
+ }
+ ASMJIT_PROPAGATE(shareAssignmentAcrossSuccessors(_curBlock));
+ }
+ else {
+ ASMJIT_PROPAGATE(blocksWithUnknownJumps.append(_pass->allocator(), _curBlock));
+ }
+ }
+ }
+
+ if (controlType == BaseInst::kControlJump) {
+ // Unconditional jump makes the code after the jump unreachable,
+ // which will be removed instantly during the CFG construction;
+ // as we cannot allocate registers for instructions that are not
+ // part of any block. Of course we can leave these instructions
+ // as they are, however, that would only postpone the problem as
+ // assemblers can't encode instructions that use virtual registers.
+ _curBlock = nullptr;
+ }
+ else {
+ node = next;
+ if (ASMJIT_UNLIKELY(!node))
+ return DebugUtils::errored(kErrorInvalidState);
+
+ RABlock* consecutiveBlock;
+ if (node->type() == BaseNode::kNodeLabel) {
+ if (node->hasPassData()) {
+ consecutiveBlock = node->passData<RABlock>();
+ }
+ else {
+ consecutiveBlock = _pass->newBlock(node);
+ if (ASMJIT_UNLIKELY(!consecutiveBlock))
+ return DebugUtils::errored(kErrorOutOfMemory);
+ node->setPassData<RABlock>(consecutiveBlock);
+ }
+ }
+ else {
+ consecutiveBlock = _pass->newBlock(node);
+ if (ASMJIT_UNLIKELY(!consecutiveBlock))
+ return DebugUtils::errored(kErrorOutOfMemory);
+ }
+
+ _curBlock->addFlags(RABlock::kFlagHasConsecutive);
+ ASMJIT_PROPAGATE(_curBlock->prependSuccessor(consecutiveBlock));
+
+ _curBlock = consecutiveBlock;
+ _hasCode = false;
+ _blockRegStats.reset();
+
+ if (_curBlock->isConstructed())
+ break;
+ ASMJIT_PROPAGATE(_pass->addBlock(consecutiveBlock));
+
+ logBlock(_curBlock, kRootIndentation);
+ continue;
+ }
+ }
+
+ if (controlType == BaseInst::kControlReturn) {
+ _curBlock->setLast(node);
+ _curBlock->makeConstructed(_blockRegStats);
+ ASMJIT_PROPAGATE(_curBlock->appendSuccessor(_retBlock));
+
+ _curBlock = nullptr;
+ }
+ }
+ }
+ else if (node->type() == BaseNode::kNodeLabel) {
+ // Label - Basic-Block Management
+ // ------------------------------
+
+ if (!_curBlock) {
+ // If the current code is unreachable the label makes it reachable
+ // again. We may remove the whole block in the future if it's not
+ // referenced.
+ _curBlock = node->passData<RABlock>();
+
+ if (_curBlock) {
+ // If the label has a block assigned we can either continue with
+ // it or skip it if the block has been constructed already.
+ if (_curBlock->isConstructed())
+ break;
+ }
+ else {
+ // No block assigned, to create a new one, and assign it.
+ _curBlock = _pass->newBlock(node);
+ if (ASMJIT_UNLIKELY(!_curBlock))
+ return DebugUtils::errored(kErrorOutOfMemory);
+ node->setPassData<RABlock>(_curBlock);
+ }
+
+ _hasCode = false;
+ _blockRegStats.reset();
+ ASMJIT_PROPAGATE(_pass->addBlock(_curBlock));
+ }
+ else {
+ if (node->hasPassData()) {
+ RABlock* consecutive = node->passData<RABlock>();
+ if (_curBlock == consecutive) {
+ // The label currently processed is part of the current block. This
+ // is only possible for multiple labels that are right next to each
+ // other, or are separated by non-code nodes like directives and comments.
+ if (ASMJIT_UNLIKELY(_hasCode))
+ return DebugUtils::errored(kErrorInvalidState);
+ }
+ else {
+ // Label makes the current block constructed. There is a chance that the
+ // Label is not used, but we don't know that at this point. In the worst
+ // case there would be two blocks next to each other, it's just fine.
+ ASMJIT_ASSERT(_curBlock->last() != node);
+ _curBlock->setLast(node->prev());
+ _curBlock->addFlags(RABlock::kFlagHasConsecutive);
+ _curBlock->makeConstructed(_blockRegStats);
+
+ ASMJIT_PROPAGATE(_curBlock->appendSuccessor(consecutive));
+ ASMJIT_PROPAGATE(_pass->addBlock(consecutive));
+
+ _curBlock = consecutive;
+ _hasCode = false;
+ _blockRegStats.reset();
+ }
+ }
+ else {
+ // First time we see this label.
+ if (_hasCode) {
+ // Cannot continue the current block if it already contains some
+ // code. We need to create a new block and make it a successor.
+ ASMJIT_ASSERT(_curBlock->last() != node);
+ _curBlock->setLast(node->prev());
+ _curBlock->addFlags(RABlock::kFlagHasConsecutive);
+ _curBlock->makeConstructed(_blockRegStats);
+
+ RABlock* consecutive = _pass->newBlock(node);
+ if (ASMJIT_UNLIKELY(!consecutive))
+ return DebugUtils::errored(kErrorOutOfMemory);
+
+ ASMJIT_PROPAGATE(_curBlock->appendSuccessor(consecutive));
+ ASMJIT_PROPAGATE(_pass->addBlock(consecutive));
+
+ _curBlock = consecutive;
+ _hasCode = false;
+ _blockRegStats.reset();
+ }
+
+ node->setPassData<RABlock>(_curBlock);
+ }
+ }
+
+ if (_curBlock && _curBlock != _lastLoggedBlock)
+ logBlock(_curBlock, kRootIndentation);
+ logNode(node, kRootIndentation);
+
+ // Unlikely: Assume that the exit label is reached only once per function.
+ if (ASMJIT_UNLIKELY(node->as<LabelNode>()->id() == _exitLabelId)) {
+ _curBlock->setLast(node);
+ _curBlock->makeConstructed(_blockRegStats);
+ ASMJIT_PROPAGATE(_pass->addExitBlock(_curBlock));
+
+ _curBlock = nullptr;
+ }
+ }
+ else {
+ // Other Nodes | Function Exit
+ // ---------------------------
+
+ logNode(node, kCodeIndentation);
+
+ if (node->type() == BaseNode::kNodeSentinel) {
+ if (node == _funcNode->endNode()) {
+ // Make sure we didn't flow here if this is the end of the function sentinel.
+ if (ASMJIT_UNLIKELY(_curBlock))
+ return DebugUtils::errored(kErrorInvalidState);
+ break;
+ }
+ }
+ else if (node->type() == BaseNode::kNodeFunc) {
+ // RAPass can only compile a single function at a time. If we
+ // encountered a function it must be the current one, bail if not.
+ if (ASMJIT_UNLIKELY(node != _funcNode))
+ return DebugUtils::errored(kErrorInvalidState);
+ // PASS if this is the first node.
+ }
+ else {
+ // PASS if this is a non-interesting or unknown node.
+ }
+ }
+
+ // Advance to the next node.
+ node = next;
+
+ // NOTE: We cannot encounter a NULL node, because every function must be
+ // terminated by a sentinel (`stop`) node. If we encountered a NULL node it
+ // means that something went wrong and this node list is corrupted; bail in
+ // such case.
+ if (ASMJIT_UNLIKELY(!node))
+ return DebugUtils::errored(kErrorInvalidState);
+ }
+
+ if (_pass->hasDanglingBlocks())
+ return DebugUtils::errored(kErrorInvalidState);
+
+ for (RABlock* block : blocksWithUnknownJumps)
+ handleBlockWithUnknownJump(block);
+
+ return _pass->initSharedAssignments(_sharedAssignmentsMap);
+ }
+
+ // --------------------------------------------------------------------------
+ // [Prepare]
+ // --------------------------------------------------------------------------
+
+ //! Prepares the CFG builder of the current function.
+ Error prepare() noexcept {
+ FuncNode* func = _pass->func();
+ BaseNode* node = nullptr;
+
+ // Create entry and exit blocks.
+ _funcNode = func;
+ _retBlock = _pass->newBlockOrExistingAt(func->exitNode(), &node);
+
+ if (ASMJIT_UNLIKELY(!_retBlock))
+ return DebugUtils::errored(kErrorOutOfMemory);
+ ASMJIT_PROPAGATE(_pass->addExitBlock(_retBlock));
+
+ if (node != func) {
+ _curBlock = _pass->newBlock();
+ if (ASMJIT_UNLIKELY(!_curBlock))
+ return DebugUtils::errored(kErrorOutOfMemory);
+ }
+ else {
+ // Function that has no code at all.
+ _curBlock = _retBlock;
+ }
+
+ // Reset everything we may need.
+ _blockRegStats.reset();
+ _exitLabelId = func->exitNode()->id();
+
+ // Initially we assume there is no code in the function body.
+ _hasCode = false;
+
+ return _pass->addBlock(_curBlock);
+ }
+
+ // --------------------------------------------------------------------------
+ // [Utilities]
+ // --------------------------------------------------------------------------
+
+ //! Called when a `node` is removed, e.g. bacause of a dead code elimination.
+ void removeNode(BaseNode* node) noexcept {
+ logNode(node, kRootIndentation, "<Removed>");
+ cc()->removeNode(node);
+ }
+
+ //! Handles block with unknown jump, which could be a jump to a jump table.
+ //!
+ //! If we encounter such block we basically insert all existing blocks as
+ //! successors except the function entry block and a natural successor, if
+ //! such block exists.
+ Error handleBlockWithUnknownJump(RABlock* block) noexcept {
+ RABlocks& blocks = _pass->blocks();
+ size_t blockCount = blocks.size();
+
+ // NOTE: Iterate from `1` as the first block is the entry block, we don't
+ // allow the entry to be a successor of block that ends with unknown jump.
+ RABlock* consecutive = block->consecutive();
+ for (size_t i = 1; i < blockCount; i++) {
+ RABlock* successor = blocks[i];
+ if (successor == consecutive)
+ continue;
+ block->appendSuccessor(successor);
+ }
+
+ return shareAssignmentAcrossSuccessors(block);
+ }
+
+ Error shareAssignmentAcrossSuccessors(RABlock* block) noexcept {
+ if (block->successors().size() <= 1)
+ return kErrorOk;
+
+ RABlock* consecutive = block->consecutive();
+ uint32_t sharedAssignmentId = Globals::kInvalidId;
+
+ for (RABlock* successor : block->successors()) {
+ if (successor == consecutive)
+ continue;
+
+ if (successor->hasSharedAssignmentId()) {
+ if (sharedAssignmentId == Globals::kInvalidId)
+ sharedAssignmentId = successor->sharedAssignmentId();
+ else
+ _sharedAssignmentsMap[successor->sharedAssignmentId()] = sharedAssignmentId;
+ }
+ else {
+ if (sharedAssignmentId == Globals::kInvalidId)
+ ASMJIT_PROPAGATE(newSharedAssignmentId(&sharedAssignmentId));
+ successor->setSharedAssignmentId(sharedAssignmentId);
+ }
+ }
+ return kErrorOk;
+ }
+
+ Error newSharedAssignmentId(uint32_t* out) noexcept {
+ uint32_t id = _sharedAssignmentsMap.size();
+ ASMJIT_PROPAGATE(_sharedAssignmentsMap.append(_pass->allocator(), id));
+
+ *out = id;
+ return kErrorOk;
+ }
+
+ // --------------------------------------------------------------------------
+ // [Logging]
+ // --------------------------------------------------------------------------
+
+#ifndef ASMJIT_NO_LOGGING
+ template<typename... Args>
+ inline void log(const char* fmt, Args&&... args) noexcept {
+ if (_logger)
+ _logger->logf(fmt, std::forward<Args>(args)...);
+ }
+
+ inline void logBlock(RABlock* block, uint32_t indentation = 0) noexcept {
+ if (_logger)
+ _logBlock(block, indentation);
+ }
+
+ inline void logNode(BaseNode* node, uint32_t indentation = 0, const char* action = nullptr) noexcept {
+ if (_logger)
+ _logNode(node, indentation, action);
+ }
+
+ void _logBlock(RABlock* block, uint32_t indentation) noexcept {
+ _sb.clear();
+ _sb.appendChars(' ', indentation);
+ _sb.appendFormat("{#%u}\n", block->blockId());
+ _logger->log(_sb);
+ _lastLoggedBlock = block;
+ }
+
+ void _logNode(BaseNode* node, uint32_t indentation, const char* action) noexcept {
+ _sb.clear();
+ _sb.appendChars(' ', indentation);
+ if (action) {
+ _sb.appendString(action);
+ _sb.appendChar(' ');
+ }
+ Logging::formatNode(_sb, _logFlags, cc(), node);
+ _sb.appendChar('\n');
+ _logger->log(_sb);
+ }
+#else
+ template<typename... Args>
+ inline void log(const char* fmt, Args&&... args) noexcept {
+ DebugUtils::unused(fmt);
+ DebugUtils::unused(std::forward<Args>(args)...);
+ }
+
+ inline void logBlock(RABlock* block, uint32_t indentation = 0) noexcept {
+ DebugUtils::unused(block, indentation);
+ }
+
+ inline void logNode(BaseNode* node, uint32_t indentation = 0, const char* action = nullptr) noexcept {
+ DebugUtils::unused(node, indentation, action);
+ }
+#endif
+};
+
+//! \}
+//! \endcond
+
+ASMJIT_END_NAMESPACE
+
+#endif // !ASMJIT_NO_COMPILER
+#endif // ASMJIT_CORE_RABUILDERS_P_H_INCLUDED