diff options
| -rw-r--r-- | src/qml/jit/jit.pri | 15 | ||||
| -rw-r--r-- | src/qml/jit/qv4blockscheduler.cpp | 208 | ||||
| -rw-r--r-- | src/qml/jit/qv4blockscheduler_p.h | 155 | ||||
| -rw-r--r-- | src/qml/jit/qv4domtree.cpp | 436 | ||||
| -rw-r--r-- | src/qml/jit/qv4domtree_p.h | 136 | ||||
| -rw-r--r-- | src/qml/jit/qv4loopinfo.cpp | 199 | ||||
| -rw-r--r-- | src/qml/jit/qv4loopinfo_p.h | 159 | ||||
| -rw-r--r-- | src/qml/jit/qv4mi.cpp | 251 | ||||
| -rw-r--r-- | src/qml/jit/qv4mi_p.h | 627 | ||||
| -rw-r--r-- | src/qml/jit/qv4miblockset_p.h | 291 | ||||
| -rw-r--r-- | src/qml/jit/qv4node_p.h | 22 | ||||
| -rw-r--r-- | src/qml/jit/qv4schedulers.cpp | 912 | ||||
| -rw-r--r-- | src/qml/jit/qv4schedulers_p.h | 162 | ||||
| -rw-r--r-- | src/qml/jit/qv4tracingjit.cpp | 7 |
14 files changed, 3559 insertions, 21 deletions
diff --git a/src/qml/jit/jit.pri b/src/qml/jit/jit.pri index e8d5860498..bc0d20dba7 100644 --- a/src/qml/jit/jit.pri +++ b/src/qml/jit/jit.pri @@ -19,7 +19,12 @@ SOURCES += \ $$PWD/qv4graph.cpp \ $$PWD/qv4graphbuilder.cpp \ $$PWD/qv4lowering.cpp \ - $$PWD/qv4tracingjit.cpp + $$PWD/qv4tracingjit.cpp \ + $$PWD/qv4mi.cpp \ + $$PWD/qv4domtree.cpp \ + $$PWD/qv4schedulers.cpp \ + $$PWD/qv4blockscheduler.cpp \ + $$PWD/qv4loopinfo.cpp HEADERS += \ $$PWD/qv4ir_p.h \ @@ -28,5 +33,11 @@ HEADERS += \ $$PWD/qv4node_p.h \ $$PWD/qv4graph_p.h \ $$PWD/qv4graphbuilder_p.h \ - $$PWD/qv4lowering_p.h + $$PWD/qv4lowering_p.h \ + $$PWD/qv4mi_p.h \ + $$PWD/qv4miblockset_p.h \ + $$PWD/qv4domtree_p.h \ + $$PWD/qv4schedulers_p.h \ + $$PWD/qv4blockscheduler_p.h \ + $$PWD/qv4loopinfo_p.h } diff --git a/src/qml/jit/qv4blockscheduler.cpp b/src/qml/jit/qv4blockscheduler.cpp new file mode 100644 index 0000000000..3e2bfe15c5 --- /dev/null +++ b/src/qml/jit/qv4blockscheduler.cpp @@ -0,0 +1,208 @@ +/**************************************************************************** +** +** Copyright (C) 2018 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtQml module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include <QtCore/qloggingcategory.h> + +#include "qv4blockscheduler_p.h" +#include "qv4domtree_p.h" +#include "qv4loopinfo_p.h" + +QT_BEGIN_NAMESPACE +namespace QV4 { +namespace IR { + +Q_LOGGING_CATEGORY(lcBlockScheduler, "qt.v4.ir.blockscheduler") + +bool BlockScheduler::checkCandidate(MIBlock *candidate) +{ + Q_ASSERT(loopInfo.loopHeaderFor(candidate) == currentGroup.group); + + for (MIBlock *pred : candidate->inEdges()) { + if (pred->isDeoptBlock()) + continue; + + if (emitted.alreadyProcessed(pred)) + continue; + + if (dominatorTree.dominates(candidate->index(), pred->index())) { + // this is a loop, where there in + // -> candidate edge is the jump back to the top of the loop. + continue; + } + + if (pred == candidate) + // this is a very tight loop, e.g.: + // L1: ... + // goto L1 + // This can happen when, for example, the basic-block merging gets rid of the empty + // body block. In this case, we can safely schedule this block (if all other + // incoming edges are either loop-back edges, or have been scheduled already). + continue; + + return false; // an incoming edge that is not yet emitted, and is not a back-edge + } + + if (loopInfo.isLoopHeader(candidate)) { + // postpone everything, and schedule the loop first. + postponedGroups.push(currentGroup); + currentGroup = WorkForGroup(candidate); + } + + return true; +} + +MIBlock *BlockScheduler::pickNext() +{ + while (true) { + while (currentGroup.postponed.isEmpty()) { + if (postponedGroups.isEmpty()) + return nullptr; + if (currentGroup.group) // record the first and the last node of a group + loopsStartEnd[currentGroup.group] = sequence.back(); + currentGroup = postponedGroups.pop(); + } + + MIBlock *next = currentGroup.postponed.pop(); + if (checkCandidate(next)) + return next; + } + + Q_UNREACHABLE(); + return nullptr; +} + +void BlockScheduler::emitBlock(MIBlock *bb) +{ + if (emitted.alreadyProcessed(bb)) + return; + + sequence.push_back(bb); + emitted.markAsProcessed(bb); +} + +void BlockScheduler::schedule(MIBlock *functionEntryPoint) +{ + MIBlock *next = functionEntryPoint; + + while (next) { + emitBlock(next); + // postpone all outgoing edges, if they were not already processed + QVarLengthArray<MIBlock *, 32> nonExceptionEdges; + // first postpone all exception edges, so they will be processed last + for (int i = next->outEdges().size(); i != 0; ) { + --i; + MIBlock *out = next->outEdges().at(i); + if (emitted.alreadyProcessed(out)) + continue; + if (out == nullptr) + continue; + if (out->instructions().front().opcode() == Meta::OnException) + postpone(out); + else + nonExceptionEdges.append(out); + } + for (MIBlock *edge : nonExceptionEdges) + postpone(edge); + next = pickNext(); + } + + // finally schedule all de-optimization blocks at the end + for (auto bb : dominatorTree.function()->blocks()) { + if (bb->isDeoptBlock()) + emitBlock(bb); + } +} + +void BlockScheduler::postpone(MIBlock *bb) +{ + if (currentGroup.group == loopInfo.loopHeaderFor(bb)) { + currentGroup.postponed.append(bb); + return; + } + + for (int i = postponedGroups.size(); i != 0; ) { + --i; + WorkForGroup &g = postponedGroups[i]; + if (g.group == loopInfo.loopHeaderFor(bb)) { + g.postponed.append(bb); + return; + } + } + + Q_UNREACHABLE(); +} + +void BlockScheduler::dump() const +{ + if (!lcBlockScheduler().isDebugEnabled()) + return; + + QString s = QStringLiteral("Scheduled blocks:\n"); + for (auto *bb : sequence) { + s += QLatin1String(" L") + QString::number(bb->index()); + MIBlock *loopEnd = loopsStartEnd[bb]; + if (loopEnd) + s += QLatin1String(", loop start, ends at L") + QString::number(loopEnd->index()); + s += QLatin1Char('\n'); + } + qCDebug(lcBlockScheduler).noquote().nospace() << s; +} + +BlockScheduler::BlockScheduler(const DominatorTree &dominatorTree, const LoopInfo &loopInfo) + : dominatorTree(dominatorTree) + , loopInfo(loopInfo) + , sequence(0) + , emitted(dominatorTree.function()) +{ + schedule(dominatorTree.function()->blocks().front()); + + dump(); + + if (dominatorTree.function()->blockCount() != sequence.size()) { + qFatal("The block scheduler did not schedule all blocks. This is most likely due to" + "a non-natural loop."); + // Usually caused by having an execution path that manages to skip over unwind handler + // reset: any exception happening after will jump back to the unwind handler, and thereby + // creating a loop that can be entered in 2 different ways. + } +} + +} // IR namespace +} // QV4 namespace +QT_END_NAMESPACE diff --git a/src/qml/jit/qv4blockscheduler_p.h b/src/qml/jit/qv4blockscheduler_p.h new file mode 100644 index 0000000000..1289fda9f0 --- /dev/null +++ b/src/qml/jit/qv4blockscheduler_p.h @@ -0,0 +1,155 @@ +/**************************************************************************** +** +** Copyright (C) 2018 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtQml module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QV4BLOCKSCHEDULER_P_H +#define QV4BLOCKSCHEDULER_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists purely as an +// implementation detail. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include <QtCore/qstack.h> + +#include "qv4mi_p.h" +#include "qv4util_p.h" + +QT_REQUIRE_CONFIG(qml_tracing); + +QT_BEGIN_NAMESPACE + +namespace QV4 { +namespace IR { + +class DominatorTree; +class LoopInfo; + +// High-level algorithm: +// 0. start with the first node (the start node) of a function +// 1. emit the node +// 2. add all outgoing edges that are not yet emitted to the postponed stack +// 3. When the postponed stack is empty, pop a stack from the loop stack. If that is empty too, +// we're done. +// 4. pop a node from the postponed stack, and check if it can be scheduled: +// a. if all incoming edges are scheduled, go to 4. +// b. if an incoming edge is unscheduled, but it's a back-edge (an edge in a loop that jumps +// back to the start of the loop), ignore it +// c. if there is any unscheduled edge that is not a back-edge, ignore this node, and go to 4. +// 5. if this node is the start of a loop, push the postponed stack on the loop stack. +// 6. go back to 1. +// +// The postponing action in step 2 will put the node into its containing group. The case where this +// is important is when a (labeled) continue or a (labeled) break statement occur in a loop: the +// outgoing edge points to a node that is not part of the current loop (and possibly not of the +// parent loop). +// +// Linear scan register allocation benefits greatly from short life-time intervals with few holes +// (see for example section 4 (Lifetime Analysis) of [Wimmer1]). This algorithm makes sure that the +// blocks of a group are scheduled together, with no non-loop blocks in between. This applies +// recursively for nested loops. It also schedules groups of if-then-else-endif blocks together for +// the same reason. +class BlockScheduler +{ + const DominatorTree &dominatorTree; + const LoopInfo &loopInfo; + + struct WorkForGroup + { + MIBlock *group; + QStack<MIBlock *> postponed; + + WorkForGroup(MIBlock *group = nullptr) : group(group) {} + }; + WorkForGroup currentGroup; + QStack<WorkForGroup> postponedGroups; + std::vector<MIBlock *> sequence; + + class ProcessedBlocks + { + BitVector processed; + + public: + ProcessedBlocks(MIFunction *function) + : processed(int(function->blockCount()), false) + {} + + bool alreadyProcessed(MIBlock *bb) const + { + Q_ASSERT(bb); + + return processed.at(bb->index()); + } + + void markAsProcessed(MIBlock *bb) + { + processed.setBit(bb->index()); + } + } emitted; + QHash<MIBlock *, MIBlock *> loopsStartEnd; + + bool checkCandidate(MIBlock *candidate); + MIBlock *pickNext(); + void emitBlock(MIBlock *bb); + void schedule(MIBlock *functionEntryPoint); + void postpone(MIBlock *bb); + void dump() const; + +public: + BlockScheduler(const DominatorTree &dominatorTree, const LoopInfo &loopInfo); + + const std::vector<MIBlock *> &scheduledBlockSequence() const + { return sequence; } + + QHash<MIBlock *, MIBlock *> loopEndsByStartBlock() const + { return loopsStartEnd; } +}; + + +} // namespace IR +} // namespace QV4 + +QT_END_NAMESPACE + +#endif // QV4BLOCKSCHEDULER_P_H diff --git a/src/qml/jit/qv4domtree.cpp b/src/qml/jit/qv4domtree.cpp new file mode 100644 index 0000000000..9484f4e2dc --- /dev/null +++ b/src/qml/jit/qv4domtree.cpp @@ -0,0 +1,436 @@ +/**************************************************************************** +** +** Copyright (C) 2018 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtQml module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include <QtCore/qloggingcategory.h> +#include <QtCore/qbuffer.h> + +#include "qv4domtree_p.h" + +QT_BEGIN_NAMESPACE +namespace QV4 { +namespace IR { + +Q_LOGGING_CATEGORY(lcDomTree, "qt.v4.ir.domTree") +Q_LOGGING_CATEGORY(lcDomFrontier, "qt.v4.ir.domFrontier") + +DominatorTree::DominatorTree(MIFunction *f) + : m_function(f) + , m_data(new Data) +{ + calculateIDoms(); + m_data.reset(); +} + +void DominatorTree::dumpImmediateDominators() const +{ + QBuffer buf; + buf.open(QIODevice::WriteOnly); + QTextStream qout(&buf); + qout << "Immediate dominators for " << m_function->irFunction()->name() << ":" << endl; + for (MIBlock *to : m_function->blocks()) { + MIBlock::Index from = m_idom.at(to->index()); + if (from != MIBlock::InvalidIndex) + qout << " " << from; + else + qout << " (none)"; + qout << " dominates " << to->index() << endl; + } + qCDebug(lcDomTree, "%s", buf.data().constData()); +} + +void DominatorTree::setImmediateDominator(MIBlock::Index dominated, MIBlock::Index dominator) +{ + if (m_idom.size() <= size_t(dominated)) + m_idom.resize(dominated + 1); + m_idom[dominated] = dominator; +} + +bool DominatorTree::dominates(MIBlock::Index dominator, MIBlock::Index dominated) const +{ + // dominator can be Invalid when the dominated block has no dominator (i.e. the start node) + Q_ASSERT(dominated != MIBlock::InvalidIndex); + + if (dominator == dominated) + return false; + + for (MIBlock::Index it = m_idom[dominated]; it != MIBlock::InvalidIndex; it = m_idom[it]) { + if (it == dominator) + return true; + } + + return false; +} + +// Calculate a depth-first iteration order on the nodes of the dominator tree. +// +// The order of the nodes in the vector is not the same as one where a recursive depth-first +// iteration is done on a tree. Rather, the nodes are (reverse) sorted on tree depth. +// So for the: +// 1 dominates 2 +// 2 dominates 3 +// 3 dominates 4 +// 2 dominates 5 +// the order will be: +// 4, 3, 5, 2, 1 +// or: +// 4, 5, 3, 2, 1 +// So the order of nodes on the same depth is undefined, but it will be after the nodes +// they dominate, and before the nodes that dominate them. +// +// The reason for this order is that a proper DFS pre-/post-order would require inverting +// the idom vector by either building a real tree datastructure or by searching the idoms +// for siblings and children. Both have a higher time complexity than sorting by depth. +std::vector<MIBlock *> DominatorTree::calculateDFNodeIterOrder() const +{ + std::vector<int> depths = calculateNodeDepths(); + std::vector<MIBlock *> order = m_function->blocks(); + std::sort(order.begin(), order.end(), [&depths](MIBlock *one, MIBlock *two) -> bool { + return depths.at(one->index()) > depths.at(two->index()); + }); + return order; +} + +// Algorithm: +// - for each node: +// - get the depth of a node. If it's unknown (-1): +// - get the depth of the immediate dominator. +// - if that's unknown too, calculate it by calling calculateNodeDepth +// - set the current node's depth to that of immediate dominator + 1 +std::vector<int> DominatorTree::calculateNodeDepths() const +{ + std::vector<int> nodeDepths(size_t(m_function->blockCount()), -1); + for (MIBlock *bb : m_function->blocks()) { + int &bbDepth = nodeDepths[bb->index()]; + if (bbDepth == -1) { + const int immDom = m_idom[bb->index()]; + if (immDom == -1) { + // no immediate dominator, so it's either the start block, or an unreachable block + bbDepth = 0; + } else { + int immDomDepth = nodeDepths[immDom]; + if (immDomDepth == -1) + immDomDepth = calculateNodeDepth(immDom, nodeDepths); + bbDepth = immDomDepth + 1; + } + } + } + return nodeDepths; +} + +// Algorithm: +// - search for the first dominator of a node that has a known depth. As all nodes are +// reachable from the start node, and that node's depth is 0, this is finite. +// - while doing that search, put all unknown nodes in the worklist +// - pop all nodes from the worklist, and set their depth to the previous' (== dominating) +// node's depth + 1 +// This way every node's depth is calculated once, and the complexity is O(n). +int DominatorTree::calculateNodeDepth(MIBlock::Index nodeIdx, std::vector<int> &nodeDepths) const +{ + std::vector<int> worklist; + worklist.reserve(8); + int depth = -1; + + do { + worklist.push_back(nodeIdx); + nodeIdx = m_idom[nodeIdx]; + depth = nodeDepths[nodeIdx]; + } while (depth == -1); + + for (auto it = worklist.rbegin(), eit = worklist.rend(); it != eit; ++it) + nodeDepths[*it] = ++depth; + + return depth; +} + +namespace { +struct DFSTodo { + MIBlock::Index node = MIBlock::InvalidIndex; + MIBlock::Index parent = MIBlock::InvalidIndex; + + DFSTodo() = default; + DFSTodo(MIBlock::Index node, MIBlock::Index parent) + : node(node) + , parent(parent) + {} +}; +} // anonymous namespace + +void DominatorTree::dfs(MIBlock::Index node) +{ + std::vector<DFSTodo> worklist; + worklist.reserve(m_data->vertex.capacity() / 2); + DFSTodo todo(node, MIBlock::InvalidIndex); + + while (true) { + MIBlock::Index n = todo.node; + + if (m_data->dfnum[n] == 0) { + m_data->dfnum[n] = m_data->size; + m_data->vertex[m_data->size] = n; + m_data->parent[n] = todo.parent; + ++m_data->size; + + MIBlock::OutEdges out = m_function->block(n)->outEdges(); + for (int i = out.size() - 1; i > 0; --i) + worklist.emplace_back(out[i]->index(), n); + + if (!out.isEmpty()) { + todo.node = out.first()->index(); + todo.parent = n; + continue; + } + } + + if (worklist.empty()) + break; + + todo = worklist.back(); + worklist.pop_back(); + } +} + +void DominatorTree::link(MIBlock::Index p, MIBlock::Index n) +{ + m_data->ancestor[n] = p; + m_data->best[n] = n; +} + +void DominatorTree::calculateIDoms() +{ + Q_ASSERT(m_function->block(0)->inEdges().count() == 0); + + const size_t bbCount = m_function->blockCount(); + m_data->vertex = std::vector<MIBlock::Index>(bbCount, MIBlock::InvalidIndex); + m_data->parent = std::vector<MIBlock::Index>(bbCount, MIBlock::InvalidIndex); + m_data->dfnum = std::vector<unsigned>(bbCount, 0); + m_data->semi = std::vector<MIBlock::Index>(bbCount, MIBlock::InvalidIndex); + m_data->ancestor = std::vector<MIBlock::Index>(bbCount, MIBlock::InvalidIndex); + m_idom = std::vector<MIBlock::Index>(bbCount, MIBlock::InvalidIndex); + m_data->samedom = std::vector<MIBlock::Index>(bbCount, MIBlock::InvalidIndex); + m_data->best = std::vector<MIBlock::Index>(bbCount, MIBlock::InvalidIndex); + + QHash<MIBlock::Index, std::vector<MIBlock::Index>> bucket; + bucket.reserve(int(bbCount)); + + dfs(m_function->block(0)->index()); + + std::vector<MIBlock::Index> worklist; + worklist.reserve(m_data->vertex.capacity() / 2); + + for (int i = m_data->size - 1; i > 0; --i) { + MIBlock::Index n = m_data->vertex[i]; + MIBlock::Index p = m_data->parent[n]; + MIBlock::Index s = p; + + for (auto inEdge : m_function->block(n)->inEdges()) { + if (inEdge->isDeoptBlock()) + continue; + MIBlock::Index v = inEdge->index(); + MIBlock::Index ss = MIBlock::InvalidIndex; + if (m_data->dfnum[v] <= m_data->dfnum[n]) + ss = v; + else + ss = m_data->semi[ancestorWithLowestSemi(v, worklist)]; + if (m_data->dfnum[ss] < m_data->dfnum[s]) + s = ss; + } + m_data->semi[n] = s; + bucket[s].push_back(n); + link(p, n); + if (bucket.contains(p)) { + for (MIBlock::Index v : bucket[p]) { + MIBlock::Index y = ancestorWithLowestSemi(v, worklist); + MIBlock::Index semi_v = m_data->semi[v]; + if (m_data->semi[y] == semi_v) + m_idom[v] = semi_v; + else + m_data->samedom[v] = y; + } + bucket.remove(p); + } + } + + for (unsigned i = 1; i < m_data->size; ++i) { + MIBlock::Index n = m_data->vertex[i]; + Q_ASSERT(n != MIBlock::InvalidIndex); + Q_ASSERT(!bucket.contains(n)); + Q_ASSERT(m_data->ancestor[n] != MIBlock::InvalidIndex); + Q_ASSERT((m_data->semi[n] != MIBlock::InvalidIndex + && m_data->dfnum[m_data->ancestor[n]] <= m_data->dfnum[m_data->semi[n]]) + || m_data->semi[n] == n); + MIBlock::Index sdn = m_data->samedom[n]; + if (sdn != MIBlock::InvalidIndex) + m_idom[n] = m_idom[sdn]; + } + + if (lcDomTree().isDebugEnabled()) + dumpImmediateDominators(); + + m_data.reset(nullptr); +} + +MIBlock::Index DominatorTree::ancestorWithLowestSemi(MIBlock::Index v, + std::vector<MIBlock::Index> &worklist) +{ + worklist.clear(); + for (MIBlock::Index it = v; it != MIBlock::InvalidIndex; it = m_data->ancestor[it]) + worklist.push_back(it); + + if (worklist.size() < 2) + return m_data->best[v]; + + MIBlock::Index b = MIBlock::InvalidIndex; + MIBlock::Index last = worklist.back(); + Q_ASSERT(worklist.size() <= INT_MAX); + for (int it = static_cast<int>(worklist.size()) - 2; it >= 0; --it) { + MIBlock::Index bbIt = worklist[it]; + m_data->ancestor[bbIt] = last; + MIBlock::Index &best_it = m_data->best[bbIt]; + if (b != MIBlock::InvalidIndex + && m_data->dfnum[m_data->semi[b]] < m_data->dfnum[m_data->semi[best_it]]) { + best_it = b; + } else { + b = best_it; + } + } + return b; +} + +void DominatorFrontier::compute(const DominatorTree &domTree) +{ + struct NodeProgress { + std::vector<MIBlock::Index> children; + std::vector<MIBlock::Index> todo; + }; + + MIFunction *function = domTree.function(); + m_df.resize(function->blockCount()); + + // compute children of each node in the dominator tree + std::vector<std::vector<MIBlock::Index> > children; // BasicBlock index -> children + children.resize(function->blockCount()); + for (MIBlock *n : function->blocks()) { + const MIBlock::Index nodeIndex = n->index(); + Q_ASSERT(function->block(nodeIndex) == n); + const MIBlock::Index nodeDominator = domTree.immediateDominator(nodeIndex); + if (nodeDominator == MIBlock::InvalidIndex) + continue; // there is no dominator to add this node to as a child (e.g. the start node) + children[nodeDominator].push_back(nodeIndex); + } + + // Fill the worklist and initialize the node status for each basic-block + std::vector<NodeProgress> nodeStatus; + nodeStatus.resize(function->blockCount()); + std::vector<MIBlock::Index> worklist; + worklist.reserve(function->blockCount()); + for (MIBlock *bb : function->blocks()) { + MIBlock::Index nodeIndex = bb->index(); + worklist.push_back(nodeIndex); + NodeProgress &np = nodeStatus[nodeIndex]; + np.children = children[nodeIndex]; + np.todo = children[nodeIndex]; + } + + BitVector DF_done(int(function->blockCount()), false); + + while (!worklist.empty()) { + MIBlock::Index node = worklist.back(); + + if (DF_done.at(node)) { + worklist.pop_back(); + continue; + } + + NodeProgress &np = nodeStatus[node]; + auto it = np.todo.begin(); + while (it != np.todo.end()) { + if (DF_done.at(*it)) { + it = np.todo.erase(it); + } else { + worklist.push_back(*it); + break; + } + } + + if (np.todo.empty()) { + MIBlockSet &miBlockSet = m_df[node]; + miBlockSet.init(function); + for (MIBlock *y : function->block(node)->outEdges()) { + if (domTree.immediateDominator(y->index()) != node) + miBlockSet.insert(y); + } + for (MIBlock::Index child : np.children) { + const MIBlockSet &ws = m_df[child]; + for (auto w : ws) { + const MIBlock::Index wIndex = w->index(); + if (node == wIndex || !domTree.dominates(node, w->index())) + miBlockSet.insert(w); + } + } + DF_done.setBit(node); + worklist.pop_back(); + } + } + + if (lcDomFrontier().isDebugEnabled()) + dump(domTree.function()); +} + +void DominatorFrontier::dump(MIFunction *function) +{ + QBuffer buf; + buf.open(QIODevice::WriteOnly); + QTextStream qout(&buf); + qout << "Dominator Frontiers:" << endl; + for (MIBlock *n : function->blocks()) { + qout << "\tDF[" << n->index() << "]: {"; + const MIBlockSet &SList = m_df[n->index()]; + for (MIBlockSet::const_iterator i = SList.begin(), ei = SList.end(); i != ei; ++i) { + if (i != SList.begin()) + qout << ", "; + qout << (*i)->index(); + } + qout << "}" << endl; + } + qCDebug(lcDomFrontier, "%s", buf.data().constData()); +} + +} // IR namespace +} // QV4 namespace +QT_END_NAMESPACE diff --git a/src/qml/jit/qv4domtree_p.h b/src/qml/jit/qv4domtree_p.h new file mode 100644 index 0000000000..703e17ab61 --- /dev/null +++ b/src/qml/jit/qv4domtree_p.h @@ -0,0 +1,136 @@ +/**************************************************************************** +** +** Copyright (C) 2018 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtQml module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QV4DOMTREE_P_H +#define QV4DOMTREE_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists purely as an +// implementation detail. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include "qv4mi_p.h" +#include "qv4miblockset_p.h" + +QT_REQUIRE_CONFIG(qml_tracing); + +QT_BEGIN_NAMESPACE + +namespace QV4 { +namespace IR { + +class DominatorTree +{ + Q_DISABLE_COPY_MOVE(DominatorTree) + +public: + DominatorTree(MIFunction *f); + ~DominatorTree() = default; + + void dumpImmediateDominators() const; + MIFunction *function() const + { return m_function; } + + void setImmediateDominator(MIBlock::Index dominated, MIBlock::Index dominator); + + MIBlock::Index immediateDominator(MIBlock::Index blockIndex) const + { return m_idom[blockIndex]; } + + bool dominates(MIBlock::Index dominator, MIBlock::Index dominated) const; + + bool insideSameDominatorChain(MIBlock::Index one, MIBlock::Index other) const + { return one == other || dominates(one, other) || dominates(other, one); } + + std::vector<MIBlock *> calculateDFNodeIterOrder() const; + + std::vector<int> calculateNodeDepths() const; + +private: // functions + int calculateNodeDepth(MIBlock::Index nodeIdx, std::vector<int> &nodeDepths) const; + void link(MIBlock::Index p, MIBlock::Index n); + void calculateIDoms(); + void dfs(MIBlock::Index node); + MIBlock::Index ancestorWithLowestSemi(MIBlock::Index v, std::vector<MIBlock::Index> &worklist); + +private: // data + struct Data { + std::vector<unsigned> dfnum; // MIBlock index -> dfnum + std::vector<MIBlock::Index> vertex; + std::vector<MIBlock::Index> parent; // MIBlock index -> parent MIBlock index + std::vector<MIBlock::Index> ancestor; // MIBlock index -> ancestor MIBlock index + std::vector<MIBlock::Index> best; // MIBlock index -> best MIBlock index + std::vector<MIBlock::Index> semi; // MIBlock index -> semi dominator MIBlock index + std::vector<MIBlock::Index> samedom; // MIBlock index -> same dominator MIBlock index + unsigned size = 0; + }; + + MIFunction *m_function; + QScopedPointer<Data> m_data; + std::vector<MIBlock::Index> m_idom; // MIBlock index -> immediate dominator MIBlock index +}; + +class DominatorFrontier +{ +public: + DominatorFrontier(const DominatorTree &domTree) + { compute(domTree); } + + const MIBlockSet &operator[](MIBlock *n) const + { return m_df[n->index()]; } + +private: // functions + void compute(const DominatorTree &domTree); + void dump(MIFunction *function); + +private: // data + std::vector<MIBlockSet> m_df; // MIBlock index -> dominator frontier +}; + +} // namespace IR +} // namespace QV4 + +QT_END_NAMESPACE + +#endif // QV4DOMTREE_P_H diff --git a/src/qml/jit/qv4loopinfo.cpp b/src/qml/jit/qv4loopinfo.cpp new file mode 100644 index 0000000000..0366c49e30 --- /dev/null +++ b/src/qml/jit/qv4loopinfo.cpp @@ -0,0 +1,199 @@ +/**************************************************************************** +** +** Copyright (C) 2018 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtQml module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include <QtCore/qloggingcategory.h> + +#include "qv4loopinfo_p.h" +#include "qv4domtree_p.h" + +QT_BEGIN_NAMESPACE +namespace QV4 { +namespace IR { + +Q_LOGGING_CATEGORY(lcLoopinfo, "qt.v4.ir.loopinfo") + +void LoopInfo::detectLoops() +{ + blockInfos.resize(dt.function()->blockCount()); + + std::vector<MIBlock *> backedges; + backedges.reserve(4); + + const auto order = dt.calculateDFNodeIterOrder(); + for (MIBlock *bb : order) { + if (bb->isDeoptBlock()) + continue; + + backedges.clear(); + + for (MIBlock *pred : bb->inEdges()) { + if (bb == pred || dt.dominates(bb->index(), pred->index())) + backedges.push_back(pred); + } + + if (!backedges.empty()) + subLoop(bb, backedges); + } + + collectLoopExits(); + + dump(); +} + +void LoopInfo::collectLoopExits() +{ + for (MIBlock::Index i = 0, ei = MIBlock::Index(blockInfos.size()); i != ei; ++i) { + BlockInfo &bi = blockInfos[i]; + MIBlock *currentBlock = dt.function()->block(i); + if (bi.isLoopHeader) { + for (MIBlock *outEdge : currentBlock->outEdges()) { + if (outEdge != currentBlock && !inLoopOrSubLoop(outEdge, currentBlock)) + bi.loopExits.push_back(outEdge); + } + } + if (MIBlock *containingLoop = bi.loopHeader) { + BlockInfo &loopInfo = blockInfos[containingLoop->index()]; + for (MIBlock *outEdge : currentBlock->outEdges()) { + if (outEdge != containingLoop && !inLoopOrSubLoop(outEdge, containingLoop)) + loopInfo.loopExits.push_back(outEdge); + } + } + } +} + +bool LoopInfo::inLoopOrSubLoop(MIBlock *block, MIBlock *loopHeader) const +{ + const BlockInfo &bi = blockInfos[block->index()]; + MIBlock *loopHeaderForBlock = bi.loopHeader; + if (loopHeaderForBlock == nullptr) + return false; // block is not in any loop + + while (loopHeader) { + if (loopHeader == loopHeaderForBlock) + return true; + // look into the parent loop of loopHeader to see if block is contained there + loopHeader = blockInfos[loopHeader->index()].loopHeader; + } + + return false; +} + +void LoopInfo::subLoop(MIBlock *loopHead, const std::vector<MIBlock *> &backedges) +{ + blockInfos[loopHead->index()].isLoopHeader = true; + + std::vector<MIBlock *> worklist; + worklist.reserve(backedges.size() + 8); + worklist.insert(worklist.end(), backedges.begin(), backedges.end()); + while (!worklist.empty()) { + MIBlock *predIt = worklist.back(); + worklist.pop_back(); + + MIBlock *subloop = blockInfos[predIt->index()].loopHeader; + if (subloop) { + // This is a discovered block. Find its outermost discovered loop. + while (MIBlock *parentLoop = blockInfos[subloop->index()].loopHeader) + subloop = parentLoop; + + // If it is already discovered to be a subloop of this loop, continue. + if (subloop == loopHead) + continue; + + // Yay, it's a subloop of this loop. + blockInfos[subloop->index()].loopHeader = loopHead; + predIt = subloop; + + // Add all predecessors of the subloop header to the worklist, as long as + // those predecessors are not in the current subloop. It might be the case + // that they are in other loops, which we will then add as a subloop to the + // current loop. + for (MIBlock *predIn : predIt->inEdges()) + if (blockInfos[predIn->index()].loopHeader != subloop) + worklist.push_back(predIn); + } else { + if (predIt == loopHead) + continue; + + // This is an undiscovered block. Map it to the current loop. + blockInfos[predIt->index()].loopHeader = loopHead; + + // Add all incoming edges to the worklist. + for (MIBlock *bb : predIt->inEdges()) + worklist.push_back(bb); + } + } +} + +void LoopInfo::dump() const +{ + if (!lcLoopinfo().isDebugEnabled()) + return; + + QString s = QStringLiteral("Loop information:\n"); + for (size_t i = 0, ei = blockInfos.size(); i != ei; ++i) { + const BlockInfo &bi = blockInfos[i]; + s += QStringLiteral(" %1 : is loop header: %2, contained in loop header's loop: ") + .arg(i).arg(bi.isLoopHeader ? QLatin1String("yes") : QLatin1String("no")); + if (bi.loopHeader) + s += QString::number(bi.loopHeader->index()); + else + s += QLatin1String("<none>"); + if (bi.isLoopHeader) { + s += QStringLiteral(", loop exits: "); + if (bi.loopExits.empty()) { + s += QLatin1String("<none>"); + } else { + bool first = true; + for (MIBlock *exit : bi.loopExits) { + if (first) + first = false; + else + s += QStringLiteral(", "); + s += QString::number(exit->index()); + } + } + } + s += QLatin1Char('\n'); + } + qCDebug(lcLoopinfo).noquote().nospace() << s; +} + +} // IR namespace +} // QV4 namespace +QT_END_NAMESPACE diff --git a/src/qml/jit/qv4loopinfo_p.h b/src/qml/jit/qv4loopinfo_p.h new file mode 100644 index 0000000000..6a865e6dc6 --- /dev/null +++ b/src/qml/jit/qv4loopinfo_p.h @@ -0,0 +1,159 @@ +/**************************************************************************** +** +** Copyright (C) 2018 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtQml module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QV4LOOPINFO_P_H +#define QV4LOOPINFO_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists purely as an +// implementation detail. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include "qv4mi_p.h" + +#include <QHash> + +QT_REQUIRE_CONFIG(qml_tracing); + +QT_BEGIN_NAMESPACE + +namespace QV4 { +namespace IR { + +class DominatorTree; + +// Detect all (sub-)loops in a function. +// +// Doing loop detection on the CFG is better than relying on the statement information in +// order to mark loops. Although JavaScript only has natural loops, it can still be the case +// that something is not a loop even though a loop-like-statement is in the source. For +// example: +// while (true) { +// if (i > 0) +// break; +// else +// break; +// } +// +// Algorithm: +// - do a DFS on the dominator tree, where for each node: +// - collect all back-edges +// - if there are back-edges, the node is a loop-header for a new loop, so: +// - walk the CFG is reverse-direction, and for every node: +// - if the node already belongs to a loop, we've found a nested loop: +// - get the loop-header for the (outermost) nested loop +// - add that loop-header to the current loop +// - continue by walking all incoming edges that do not yet belong to the current loop +// - if the node does not belong to a loop yet, add it to the current loop, and +// go on with all incoming edges +// +// Loop-header detection by checking for back-edges is very straight forward: a back-edge is +// an incoming edge where the other node is dominated by the current node. Meaning: all +// execution paths that reach that other node have to go through the current node, that other +// node ends with a (conditional) jump back to the loop header. +// +// The exact order of the DFS on the dominator tree is not important. The only property has to +// be that a node is only visited when all the nodes it dominates have been visited before. +// The reason for the DFS is that for nested loops, the inner loop's loop-header is dominated +// by the outer loop's header. So, by visiting depth-first, sub-loops are identified before +// their containing loops, which makes nested-loop identification free. An added benefit is +// that the nodes for those sub-loops are only processed once. +// +// Note: independent loops that share the same header are merged together. For example, in +// the code snippet below, there are 2 back-edges into the loop-header, but only one single +// loop will be detected. +// while (a) { +// if (b) +// continue; +// else +// continue; +// } +class LoopInfo +{ + Q_DISABLE_COPY_MOVE(LoopInfo) + + struct BlockInfo + { + MIBlock *loopHeader = nullptr; + bool isLoopHeader = false; + std::vector<MIBlock *> loopExits; + }; + +public: + LoopInfo(const DominatorTree &dt) + : dt(dt) + {} + + ~LoopInfo() = default; + + void detectLoops(); + + MIBlock *loopHeaderFor(MIBlock *bodyBlock) const + { return blockInfos[bodyBlock->index()].loopHeader; } + + bool isLoopHeader(MIBlock *block) const + { return blockInfos[block->index()].isLoopHeader; } + + const std::vector<MIBlock *> loopExitsForLoop(MIBlock *loopHeader) const + { return blockInfos[loopHeader->index()].loopExits; } + +private: + void subLoop(MIBlock *loopHead, const std::vector<MIBlock *> &backedges); + void collectLoopExits(); + bool inLoopOrSubLoop(MIBlock *block, MIBlock *loopHeader) const; + + void dump() const; + +private: + const DominatorTree &dt; + std::vector<BlockInfo> blockInfos; +}; + +} // namespace IR +} // namespace QV4 + +QT_END_NAMESPACE + +#endif // QV4LOOPINFO_P_H diff --git a/src/qml/jit/qv4mi.cpp b/src/qml/jit/qv4mi.cpp new file mode 100644 index 0000000000..f0b172243d --- /dev/null +++ b/src/qml/jit/qv4mi.cpp @@ -0,0 +1,251 @@ +/**************************************************************************** +** +** Copyright (C) 2018 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtQml module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include <QtCore/qloggingcategory.h> +#include <private/qqmlglobal_p.h> + +#include "qv4mi_p.h" +#include "qv4node_p.h" + +QT_BEGIN_NAMESPACE +namespace QV4 { +namespace IR { + +Q_LOGGING_CATEGORY(lcMI, "qt.v4.ir.mi") + +QString MIOperand::debugString() const +{ + switch (kind()) { + case Invalid: return QStringLiteral("<<INVALID>>"); + case Constant: return ConstantPayload::debugString(constantValue()); + case VirtualRegister: return QStringLiteral("vreg%1").arg(virtualRegister()); + case EngineRegister: return QStringLiteral("engine"); + case CppFrameRegister: return QStringLiteral("cppFrame"); + case Function: return QStringLiteral("function"); + case JSStackSlot: return QStringLiteral("jsstack[%1]").arg(stackSlot()); + case BoolStackSlot: return QStringLiteral("bstack[%1]").arg(stackSlot()); + case JumpTarget: return targetBlock() ? QStringLiteral("L%1").arg(targetBlock()->index()) + : QStringLiteral("<<INVALID BLOCK>>"); + default: Q_UNREACHABLE(); + } +} + +MIInstr *MIInstr::create(QQmlJS::MemoryPool *pool, Node *irNode, unsigned nOperands) +{ + return pool->New<MIInstr>(irNode, pool, nOperands); +} + +static QString commentIndent(const QString &line) +{ + int spacing = std::max(70 - line.length(), 1); + return line + QString(spacing, QLatin1Char(' ')); +} + +static QString indent(int nr) +{ + QString s = nr == -1 ? QString() : QString::number(nr); + int padding = 6 - s.size(); + if (padding > 0) + s = QString(padding, QLatin1Char(' ')) + s; + return s; +} + +MIFunction::MIFunction(Function *irFunction) + : m_irFunction(irFunction) +{} + +void MIFunction::renumberBlocks() +{ + for (size_t i = 0, ei = m_blocks.size(); i != ei; ++i) { + MIBlock *b = m_blocks[i]; + b->setIndex(unsigned(i)); + } +} + +void MIFunction::renumberInstructions() +{ + int pos = 0; + for (MIBlock *b : m_blocks) { + for (MIInstr &instr : b->instructions()) { + pos += 2; + instr.setPosition(pos); + } + } +} + +void MIFunction::dump(const QString &description) const +{ + if (!lcMI().isDebugEnabled()) + return; + + QString s = description + QLatin1String(":\n"); + QString name; + if (auto n = irFunction()->v4Function()->name()) + name = n->toQString(); + if (name.isEmpty()) + QString::asprintf("%p", static_cast<void *>(irFunction()->v4Function())); + QString line = QStringLiteral("function %1 {").arg(name); + auto loc = irFunction()->v4Function()->sourceLocation(); + s += commentIndent(line) + QStringLiteral("; %1:%2:%3\n").arg(loc.sourceFile, + QString::number(loc.line), + QString::number(loc.column)); + for (const MIBlock *b : blocks()) { + line = QStringLiteral("L%1").arg(b->index()); + bool first = true; + if (!b->arguments().empty()) { + line += QLatin1Char('('); + for (const MIOperand &arg : b->arguments()) { + if (first) + first = false; + else + line += QStringLiteral(", "); + line += arg.debugString(); + } + line += QLatin1Char(')'); + } + line += QLatin1Char(':'); + line = commentIndent(line) + QStringLiteral("; preds: "); + if (b->inEdges().isEmpty()) { + line += QStringLiteral("<none>"); + } else { + bool first = true; + for (MIBlock *in : b->inEdges()) { + if (first) + first = false; + else + line += QStringLiteral(", "); + line += QStringLiteral("L%1").arg(in->index()); + } + } + s += line + QLatin1Char('\n'); + for (const MIInstr &i : b->instructions()) { + line = indent(i.position()) + QLatin1String(": "); + if (i.hasDestination()) + line += i.destination().debugString() + QStringLiteral(" = "); + line += i.irNode()->operation()->debugString(); + bool first = true; + for (const MIOperand &op : i.operands()) { + if (first) + first = false; + else + line += QLatin1Char(','); + line += QLatin1Char(' ') + op.debugString(); + } + line = commentIndent(line) + QStringLiteral("; node-id: %1").arg(i.irNode()->id()); + if (i.irNode()->operation()->needsBytecodeOffsets()) + line += QStringLiteral(", bytecode-offset: %1").arg(irFunction()->nodeInfo(i.irNode())->currentInstructionOffset()); + s += line + QLatin1Char('\n'); + } + s += commentIndent(QString()) + QStringLiteral("; succs: "); + if (b->outEdges().isEmpty()) { + s += QStringLiteral("<none>"); + } else { + bool first = true; + for (MIBlock *succ : b->outEdges()) { + if (first) + first = false; + else + s += QStringLiteral(", "); + s += QStringLiteral("L%1").arg(succ->index()); + } + } + s += QLatin1Char('\n'); + } + s += QLatin1Char('}'); + + for (const QStringRef &line : s.splitRef('\n')) + qCDebug(lcMI).noquote().nospace() << line; +} + +unsigned MIFunction::extraJSSlots() const +{ + uint interpreterFrameSize = CppStackFrame::requiredJSStackFrameSize(irFunction()->v4Function()); + if (m_jsSlotCount <= interpreterFrameSize) + return 0; + return m_jsSlotCount - interpreterFrameSize; +} + +void MIFunction::setStartBlock(MIBlock *newStartBlock) +{ + auto it = std::find(m_blocks.begin(), m_blocks.end(), newStartBlock); + Q_ASSERT(it != m_blocks.end()); + std::swap(*m_blocks.begin(), *it); +} + +void MIFunction::setStackSlotCounts(unsigned dword, unsigned qword, unsigned js) +{ + m_vregCount = 0; + m_dwordSlotCount = dword; + m_qwordSlotCount = qword; + m_jsSlotCount = js; +} + +void MIFunction::verifyCFG() const +{ + if (block(MIFunction::StartBlockIndex)->instructions().front().opcode() != Meta::Start) + qFatal("MIFunction block 0 is not the start block"); + + for (MIBlock *b : m_blocks) { + for (MIBlock *in : b->inEdges()) { + if (!in->outEdges().contains(b)) + qFatal("block %u has incoming edge from block %u, " + "but does not appear in that block's outgoing edges", + b->index(), in->index()); + } + for (MIBlock *out : b->outEdges()) { + if (!out->inEdges().contains(b)) + qFatal("block %u has outgoing edge from block %u, " + "but does not appear in that block's incoming edges", + b->index(), out->index()); + } + } +} + +MIBlock *MIBlock::findEdgeTo(Operation::Kind target) const +{ + for (MIBlock *outEdge : outEdges()) { + if (outEdge->instructions().front().opcode() == target) + return outEdge; + } + return nullptr; +} + +} // IR namespace +} // QV4 namespace +QT_END_NAMESPACE diff --git a/src/qml/jit/qv4mi_p.h b/src/qml/jit/qv4mi_p.h new file mode 100644 index 0000000000..f976d1dc94 --- /dev/null +++ b/src/qml/jit/qv4mi_p.h @@ -0,0 +1,627 @@ +/**************************************************************************** +** +** Copyright (C) 2018 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtQml module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QV4MI_P_H +#define QV4MI_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists purely as an +// implementation detail. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include <private/qv4global_p.h> +#include <private/qv4ir_p.h> +#include <private/qv4node_p.h> +#include <private/qv4operation_p.h> + +#include <llvm/ADT/iterator.h> +#include <llvm/ADT/iterator_range.h> +#include <llvm/ADT/ilist.h> +#include <llvm/ADT/ilist_node.h> + +QT_REQUIRE_CONFIG(qml_tracing); + +QT_BEGIN_NAMESPACE + +namespace QV4 { +namespace IR { + +// This file contains the Machine Interface (MI) data structures, on which ultimately the assembler +// will operate: + +class MIFunction; // containing all basic blocks, and a reference to the IR function + +class MIBlock; // containing an ordered sequence of instructions + +class MIInstr; // containing operands, and a reference to the IR node, that indicates which + // operation is represented by an instruction + +class MIOperand; // contains a description of where to get/put the input/result of an operation + +// A detail about the stack slots: there two stacks, the JS stack and the native stack. A frame on +// the native stack is divided in two parts: the quad-word part and the double-word part. The +// qword part holds 64bit values, like doubles, and pointers on 64bit architectures. The dword part +// holds 32bit values, like int32s, booleans, and pointers on 32bit architectures. We need to know +// the type of value a slot holds, because if we have to move it to the JS stack, we have to box it +// correctly. +class MIOperand final +{ +public: + enum Kind { + Invalid = 0, + Constant, + VirtualRegister, + + EngineRegister, + CppFrameRegister, + Function, + + JSStackSlot, + BoolStackSlot, + + JumpTarget, + }; + + using List = QQmlJS::FixedPoolArray<MIOperand>; + +public: + MIOperand() = default; + + static MIOperand createConstant(Node *irNode) + { + MIOperand op; + op.m_kind = Constant; + op.m_irNode = irNode; + return op; + } + + static MIOperand createVirtualRegister(Node *irNode, unsigned vreg) + { + MIOperand op; + op.m_kind = VirtualRegister; + op.m_irNode = irNode; + op.m_vreg = vreg; + return op; + } + + static MIOperand createEngineRegister(Node *irNode) + { + MIOperand op; + op.m_kind = EngineRegister; + op.m_irNode = irNode; + return op; + } + + static MIOperand createCppFrameRegister(Node *irNode) + { + MIOperand op; + op.m_kind = CppFrameRegister; + op.m_irNode = irNode; + return op; + } + + static MIOperand createFunction(Node *irNode) + { + MIOperand op; + op.m_kind = Function; + op.m_irNode = irNode; + return op; + } + + static MIOperand createJSStackSlot(Node *irNode, unsigned slot) + { + MIOperand op; + op.m_kind = JSStackSlot; + op.m_irNode = irNode; + op.m_slot = slot; + return op; + } + + static MIOperand createBoolStackSlot(Node *irNode, unsigned slot) + { + MIOperand op; + op.m_kind = BoolStackSlot; + op.m_irNode = irNode; + op.m_slot = slot; + return op; + } + + //### or name this createDeoptBlock? + static MIOperand createJumpTarget(Node *irNode, MIBlock *targetBlock) + { + MIOperand op; + op.m_kind = JumpTarget; + op.m_irNode = irNode; + op.m_targetBlock = targetBlock; + return op; + } + + Kind kind() const + { return m_kind; } + + bool isValid() const + { return m_kind != Invalid; } + + bool isConstant() const + { return m_kind == Constant; } + + bool isVirtualRegister() const + { return kind() == VirtualRegister; } + + bool isEngineRegister() const + { return kind() == EngineRegister; } + + bool isCppFrameRegister() const + { return kind() == CppFrameRegister; } + + bool isFunction() const + { return kind() == Function; } + + bool isJSStackSlot() const + { return kind() == JSStackSlot; } + + bool isBoolStackSlot() const + { return kind() == BoolStackSlot; } + + bool isStackSlot() const + { return isJSStackSlot() || isDWordSlot() || isQWordSlot(); } + + bool isJumpTarget() const + { return kind() == JumpTarget; } + + Node *irNode() const + { return m_irNode; } + + inline Type nodeType(MIFunction *f) const; + + QString debugString() const; + + QV4::Value constantValue() const + { + Q_ASSERT(isConstant()); + if (irNode()->opcode() == Meta::Undefined) + return QV4::Value::undefinedValue(); + if (irNode()->opcode() == Meta::Empty) + return QV4::Value::emptyValue(); + return ConstantPayload::get(*irNode()->operation())->value(); + } + + unsigned virtualRegister() const + { Q_ASSERT(isVirtualRegister()); return m_vreg; } + + unsigned stackSlot() const + { Q_ASSERT(isStackSlot()); return m_slot; } + + MIBlock *targetBlock() const + { Q_ASSERT(isJumpTarget()); return m_targetBlock; } + + inline bool operator==(const MIOperand &other) const + { + if (kind() != other.kind()) + return false; + + if (isStackSlot()) + return stackSlot() == other.stackSlot(); + + switch (kind()) { + case MIOperand::Invalid: + return !other.isValid(); + case MIOperand::Constant: + return constantValue().asReturnedValue() == other.constantValue().asReturnedValue(); + case MIOperand::VirtualRegister: + return virtualRegister() == other.virtualRegister(); + case MIOperand::JumpTarget: + return targetBlock() == other.targetBlock(); + default: + Q_UNREACHABLE(); + return false; + } + } + + bool isDWordSlot() const + { + switch (kind()) { + case BoolStackSlot: + return true; + default: + return false; + } + } + + bool isQWordSlot() const + { + switch (kind()) { + //### TODO: double slots + default: + return false; + } + } + + bool overlaps(const MIOperand &other) const + { + if ((isDWordSlot() && other.isDWordSlot()) || (isQWordSlot() && other.isQWordSlot())) + ; // fine, these are the same + else if (kind() != other.kind()) + return false; + + if (isStackSlot()) + return stackSlot() == other.stackSlot(); + + return false; + } + +private: + Node *m_irNode = nullptr; + union { + unsigned m_vreg; + unsigned m_slot; + MIBlock *m_targetBlock = nullptr; + }; + Kind m_kind = Invalid; +}; + +template <typename NodeTy> struct MIInstrListParentType {}; +template <> struct MIInstrListParentType<MIInstr> { using type = MIBlock; }; + +template <typename NodeTy> class MIInstrList; + +template <typename MISubClass> +class MIInstrListTraits : public llvm::ilist_noalloc_traits<MISubClass> +{ +protected: + using ListTy = MIInstrList<MISubClass>; + using iterator = typename llvm::simple_ilist<MISubClass>::iterator; + using ItemParentClass = typename MIInstrListParentType<MISubClass>::type; + +public: + MIInstrListTraits() = default; + +protected: + void setListOwner(ItemParentClass *listOwner) + { m_owner = listOwner; } + +private: + ItemParentClass *m_owner = nullptr; + + /// getListOwner - Return the object that owns this list. If this is a list + /// of instructions, it returns the BasicBlock that owns them. + ItemParentClass *getListOwner() const { + return m_owner; + } + + static ListTy &getList(ItemParentClass *Par) { + return Par->*(Par->getSublistAccess()); + } + + static MIInstrListTraits<MISubClass> *getSymTab(ItemParentClass *Par) { + return Par ? toPtr(Par->getValueSymbolTable()) : nullptr; + } + +public: + void addNodeToList(MISubClass *V) { V->setParent(getListOwner()); } + void removeNodeFromList(MISubClass *V) { V->setParent(nullptr); } + void transferNodesFromList(MIInstrListTraits &L2, iterator first, + iterator last); +}; + +template <class T> +class MIInstrList: public llvm::iplist_impl<llvm::simple_ilist<T>, MIInstrListTraits<T>> +{ +public: + MIInstrList(typename MIInstrListTraits<T>::ItemParentClass *owner) + { this->setListOwner(owner); } +}; + +class MIInstr final : public llvm::ilist_node_with_parent<MIInstr, MIBlock> +{ + Q_DISABLE_COPY_MOVE(MIInstr) // heap use only! + +protected: + friend class QQmlJS::MemoryPool; + MIInstr() : m_operands(nullptr, 0) {} + + explicit MIInstr(Node *irNode, QQmlJS::MemoryPool *pool, unsigned nOperands) + : m_irNode(irNode) + , m_operands(pool, nOperands) + {} + + ~MIInstr() = default; + +public: + static MIInstr *create(QQmlJS::MemoryPool *pool, Node *irNode, unsigned nOperands); + + MIBlock *parent() const + { return m_parent; } + + MIBlock *getParent() const // for ilist_node_with_parent + { return parent(); } + + void setParent(MIBlock *parent) + { m_parent = parent; } + + Node *irNode() const + { return m_irNode; } + + Operation::Kind opcode() const + { return m_irNode->opcode(); } + + int position() const + { return m_position; } + + inline void insertBefore(MIInstr *insertPos); + inline void insertAfter(MIInstr *insertPos); + inline MIInstrList<MIInstr>::iterator eraseFromParent(); + + bool hasDestination() const + { return m_destination.isValid(); } + + MIOperand destination() const + { return m_destination; } + + void setDestination(const MIOperand &dest) + { m_destination = dest; } + + const MIOperand &operand(unsigned index) const + { return m_operands.at(index); } + + void setOperand(unsigned index, const MIOperand &op) + { m_operands.at(index) = op; } + + MIOperand &operand(unsigned index) + { return m_operands.at(index); } + + const MIOperand::List &operands() const + { return m_operands; } + + MIOperand::List &operands() + { return m_operands; } + +private: + friend MIFunction; + void setPosition(int newPosition) + { m_position = newPosition; } + +private: + MIBlock *m_parent = nullptr; + Node *m_irNode = nullptr; + int m_position = -1; + MIOperand m_destination; + MIOperand::List m_operands; +}; + +class MIBlock final +{ + Q_DISABLE_COPY_MOVE(MIBlock) + +public: + using Index = unsigned; + enum : Index { InvalidIndex = std::numeric_limits<Index>::max() }; + + using MIInstructionList = MIInstrList<MIInstr>; + + using InEdges = QVarLengthArray<MIBlock *, 4>; + using OutEdges = QVarLengthArray<MIBlock *, 2>; + +protected: + friend MIFunction; + explicit MIBlock(Index index) + : m_instructions(this), + m_index(index) + {} + + void setIndex(Index newIndex) + { m_index = newIndex; } + +public: + ~MIBlock() = default; + + const MIInstructionList &instructions() const + { return m_instructions; } + + MIInstructionList &instructions() + { return m_instructions; } + + static MIInstructionList MIBlock::*getSublistAccess(MIInstr * = nullptr) + { return &MIBlock::m_instructions; } + + void addArgument(MIOperand &&arg) + { m_arguments.push_back(arg); } + + const std::vector<MIOperand> &arguments() const + { return m_arguments; } + + std::vector<MIOperand> &arguments() + { return m_arguments; } + + void clearArguments() + { m_arguments.resize(0); } + + const InEdges &inEdges() const + { return m_inEdges; } + + void addInEdge(MIBlock *edge) + { m_inEdges.append(edge); } + + const OutEdges &outEdges() const + { return m_outEdges; } + + void addOutEdge(MIBlock *edge) + { m_outEdges.append(edge); } + + Index index() const + { return m_index; } + + MIBlock *findEdgeTo(Operation::Kind target) const; + + bool isDeoptBlock() const + { return m_isDeoptBlock; } + + void markAsDeoptBlock() + { m_isDeoptBlock = true; } + +private: + std::vector<MIOperand> m_arguments; + MIInstructionList m_instructions; + InEdges m_inEdges; + OutEdges m_outEdges; + Index m_index; + bool m_isDeoptBlock = false; +}; + +class MIFunction final +{ + Q_DISABLE_COPY_MOVE(MIFunction) + +public: + static constexpr MIBlock::Index StartBlockIndex = 0; + +public: + MIFunction(Function *irFunction); + ~MIFunction() + { qDeleteAll(m_blocks); } + + Function *irFunction() const + { return m_irFunction; } + + void setStartBlock(MIBlock *newStartBlock); + void renumberBlocks(); + void renumberInstructions(); + + void dump(const QString &description) const; + + size_t blockCount() const + { return blocks().size(); } + + MIBlock *block(MIBlock::Index index) const + { return m_blocks[index]; } + + const std::vector<MIBlock *> &blocks() const + { return m_blocks; } + + MIBlock *addBlock() + { + auto *b = new MIBlock(unsigned(m_blocks.size())); + m_blocks.push_back(b); + return b; + } + + void setBlockOrder(const std::vector<MIBlock *> &newSequence) + { m_blocks = newSequence; } + + unsigned vregCount() const + { return m_vregCount; } + + void setVregCount(unsigned vregCount) + { m_vregCount = vregCount; } + + unsigned dwordSlotCount() const + { return m_dwordSlotCount; } + + unsigned qwordSlotCount() const + { return m_qwordSlotCount; } + + unsigned jsSlotCount() const + { return m_jsSlotCount; } + + unsigned extraJSSlots() const; + + void setStackSlotCounts(unsigned dword, unsigned qword, unsigned js); + + void verifyCFG() const; + +private: + Function *m_irFunction = nullptr; + std::vector<MIBlock *> m_blocks; + unsigned m_vregCount = 0; + unsigned m_dwordSlotCount = 0; + unsigned m_qwordSlotCount = 0; + unsigned m_jsSlotCount = 0; +}; + +Type MIOperand::nodeType(MIFunction *f) const +{ + return f->irFunction()->nodeInfo(irNode())->type(); +} + +inline uint qHash(const MIOperand &key, uint seed) +{ + uint h = ::qHash(key.kind(), seed); + switch (key.kind()) { + case MIOperand::VirtualRegister: + h ^= key.virtualRegister(); + break; + case MIOperand::BoolStackSlot: Q_FALLTHROUGH(); + case MIOperand::JSStackSlot: + h ^= key.stackSlot(); + break; + default: + qFatal("%s: cannot hash %s", Q_FUNC_INFO, key.debugString().toUtf8().constData()); + } + return h; +} + +void MIInstr::insertBefore(MIInstr *insertPos) +{ + insertPos->parent()->instructions().insert(insertPos->getIterator(), this); +} + +void MIInstr::insertAfter(MIInstr *insertPos) +{ + insertPos->parent()->instructions().insert(++insertPos->getIterator(), this); +} + +MIInstrList<MIInstr>::iterator MIInstr::eraseFromParent() +{ + auto p = parent(); + setParent(nullptr); + return p->instructions().erase(getIterator()); +} + +} // namespace IR +} // namespace QV4 + +QT_END_NAMESPACE + +#endif // QV4MI_P_H diff --git a/src/qml/jit/qv4miblockset_p.h b/src/qml/jit/qv4miblockset_p.h new file mode 100644 index 0000000000..5f814b99e0 --- /dev/null +++ b/src/qml/jit/qv4miblockset_p.h @@ -0,0 +1,291 @@ +/**************************************************************************** +** +** Copyright (C) 2018 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtQml module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QV4MIBLOCKSET_P_H +#define QV4MIBLOCKSET_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists purely as an +// implementation detail. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include "qv4mi_p.h" +#include "qv4util_p.h" + +QT_REQUIRE_CONFIG(qml_tracing); + +QT_BEGIN_NAMESPACE + +namespace QV4 { +namespace IR { + +class MIBlockSet +{ + using Flags = BitVector; + + QVarLengthArray<MIBlock::Index, 8> blockNumbers; + Flags *blockFlags = nullptr; + MIFunction *function = nullptr; + enum { MaxVectorCapacity = 8 }; + +public: + class const_iterator; + friend class const_iterator; + +public: + MIBlockSet(MIFunction *f = nullptr) + { + if (f) + init(f); + } + + MIBlockSet(MIBlockSet &&other) noexcept + { + std::swap(blockNumbers, other.blockNumbers); + std::swap(blockFlags, other.blockFlags); + std::swap(function, other.function); + } + + MIBlockSet(const MIBlockSet &other) + : function(other.function) + { + if (other.blockFlags) + blockFlags = new Flags(*other.blockFlags); + blockNumbers = other.blockNumbers; + } + + MIBlockSet &operator=(const MIBlockSet &other) + { + if (blockFlags) { + delete blockFlags; + blockFlags = nullptr; + } + function = other.function; + if (other.blockFlags) + blockFlags = new Flags(*other.blockFlags); + blockNumbers = other.blockNumbers; + return *this; + } + + MIBlockSet &operator=(MIBlockSet &&other) noexcept + { + if (&other != this) { + std::swap(blockNumbers, other.blockNumbers); + + delete blockFlags; + blockFlags = other.blockFlags; + other.blockFlags = nullptr; + + function = other.function; + } + return *this; + } + + ~MIBlockSet() + { + delete blockFlags; + } + + void init(MIFunction *f) + { + Q_ASSERT(!function); + Q_ASSERT(f); + function = f; + } + + bool empty() const; + + void insert(MIBlock *bb) + { + Q_ASSERT(function); + + if (blockFlags) { + blockFlags->setBit(bb->index()); + return; + } + + for (unsigned int blockNumber : qAsConst(blockNumbers)) { + if (blockNumber == bb->index()) + return; + } + + if (blockNumbers.size() == MaxVectorCapacity) { + blockFlags = new Flags(int(function->blockCount()), false); + for (unsigned int blockNumber : qAsConst(blockNumbers)) { + blockFlags->setBit(int(blockNumber)); + } + blockNumbers.clear(); + blockFlags->setBit(int(bb->index())); + } else { + blockNumbers.append(bb->index()); + } + } + + void remove(MIBlock *bb) + { + Q_ASSERT(function); + + if (blockFlags) { + blockFlags->clearBit(bb->index()); + return; + } + + for (int i = 0; i < blockNumbers.size(); ++i) { + if (blockNumbers[i] == bb->index()) { + blockNumbers.remove(i); + return; + } + } + } + + const_iterator begin() const; + const_iterator end() const; + + void collectValues(std::vector<MIBlock *> &bbs) const; + + bool contains(MIBlock *bb) const + { + Q_ASSERT(function); + + if (blockFlags) + return blockFlags->at(bb->index()); + + for (unsigned int blockNumber : blockNumbers) { + if (blockNumber == bb->index()) + return true; + } + + return false; + } +}; + +class MIBlockSet::const_iterator +{ + const MIBlockSet &set; + // ### These two members could go into a union, but clang won't compile + // (https://codereview.qt-project.org/#change,74259) + QVarLengthArray<MIBlock::Index, 8>::const_iterator numberIt; + MIBlock::Index flagIt; + + friend class MIBlockSet; + const_iterator(const MIBlockSet &set, bool end) + : set(set) + { + if (end || !set.function) { + if (!set.blockFlags) + numberIt = set.blockNumbers.end(); + else + flagIt = set.blockFlags->size(); + } else { + if (!set.blockFlags) + numberIt = set.blockNumbers.begin(); + else + findNextWithFlags(0); + } + } + + void findNextWithFlags(int start) + { + flagIt = MIBlock::Index(set.blockFlags->findNext(start, true, /*wrapAround = */false)); + Q_ASSERT(flagIt <= MIBlock::Index(set.blockFlags->size())); + } + +public: + MIBlock *operator*() const + { + if (!set.blockFlags) + return set.function->block(*numberIt); + + Q_ASSERT(flagIt <= set.function->blockCount()); + return set.function->block(flagIt); + + } + + bool operator==(const const_iterator &other) const + { + if (&set != &other.set) + return false; + if (!set.blockFlags) + return numberIt == other.numberIt; + return flagIt == other.flagIt; + } + + bool operator!=(const const_iterator &other) const + { return !(*this == other); } + + const_iterator &operator++() + { + if (!set.blockFlags) + ++numberIt; + else + findNextWithFlags(flagIt + 1); + + return *this; + } +}; + +inline bool MIBlockSet::empty() const +{ return begin() == end(); } + +inline MIBlockSet::const_iterator MIBlockSet::begin() const +{ return const_iterator(*this, false); } + +inline MIBlockSet::const_iterator MIBlockSet::end() const +{ return const_iterator(*this, true); } + +inline void MIBlockSet::collectValues(std::vector<MIBlock *> &bbs) const +{ + Q_ASSERT(function); + + for (auto it : *this) + bbs.push_back(it); +} + +} // namespace IR +} // namespace QV4 + +QT_END_NAMESPACE + +#endif // QV4MIBLOCKSET_P_H diff --git a/src/qml/jit/qv4node_p.h b/src/qml/jit/qv4node_p.h index 679a29764a..76065fb1bc 100644 --- a/src/qml/jit/qv4node_p.h +++ b/src/qml/jit/qv4node_p.h @@ -472,17 +472,6 @@ public: m_worklist.push_back(n); } - void reEnqueueLate(Node *n) - { - if (!n) - return; - State &s = nodeState(n); - if (s == Queued) - return; - s = Queued; - m_worklist.insert(m_worklist.begin(), n); - } - void enqueueAllInputs(Node *n) { for (Node *input : n->inputs()) @@ -519,19 +508,14 @@ public: Node *n = m_worklist.back(); m_worklist.pop_back(); State &s = nodeState(n); - if (s == Queued) { - s = Visited; - return n; - } - Q_UNREACHABLE(); + Q_ASSERT(s == Queued); + s = Visited; + return n; } return nullptr; } - void markAsVisited(Node *n) - { nodeState(n) = Visited; } - bool isVisited(Node *n) const { return nodeState(n) == Visited; } diff --git a/src/qml/jit/qv4schedulers.cpp b/src/qml/jit/qv4schedulers.cpp new file mode 100644 index 0000000000..0dffefa951 --- /dev/null +++ b/src/qml/jit/qv4schedulers.cpp @@ -0,0 +1,912 @@ +/**************************************************************************** +** +** Copyright (C) 2018 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtQml module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include <QtCore/qloggingcategory.h> + +#include "qv4schedulers_p.h" +#include "qv4util_p.h" +#include "qv4graph_p.h" +#include "qv4blockscheduler_p.h" +#include "qv4stackframe_p.h" + +QT_BEGIN_NAMESPACE +namespace QV4 { +namespace IR { + +Q_LOGGING_CATEGORY(lcSched, "qt.v4.ir.scheduling") +Q_LOGGING_CATEGORY(lcDotCFG, "qt.v4.ir.scheduling.cfg") + +static bool needsScheduling(Node *n) +{ + if (n->operation()->isConstant()) + return false; + switch (n->opcode()) { + case Meta::Function: Q_FALLTHROUGH(); + case Meta::CppFrame: + case Meta::Phi: + case Meta::EffectPhi: + return false; + default: + return true; + } +} + +bool NodeScheduler::canStartBlock(Node *node) const +{ + switch (node->operation()->kind()) { + case Meta::Start: Q_FALLTHROUGH(); + case Meta::IfTrue: + case Meta::IfFalse: + case Meta::Region: + case Meta::HandleUnwind: + case Meta::OnException: + return true; + + default: + return false; + } +} + +bool NodeScheduler::isControlFlowSplit(Node *node) const +{ + int nOutputs = node->operation()->controlOutputCount(); + if (nOutputs == 2) { + // if there is a "missing" control output, it's for exception flow without unwinder + int controlUses = 0; + auto uses = node->uses(); + for (auto it = uses.begin(), eit = uses.end(); it != eit; ++it) { + if (isLive(*it) && it.isUsedAsControl()) + ++controlUses; + } + return controlUses == 2; + } + return nOutputs > 2; +} + +bool NodeScheduler::isBlockTerminator(Node *node) const +{ + switch (node->operation()->kind()) { + case Meta::Branch: Q_FALLTHROUGH(); + case Meta::Jump: + case Meta::Return: + case Meta::TailCall: + case Meta::UnwindDispatch: + case Meta::End: + return true; + case Meta::Call: + return isControlFlowSplit(node); + default: + return false; + } +} + +MIBlock *NodeScheduler::getCommonDominator(MIBlock *one, MIBlock *other) const +{ + MIBlock::Index a = one->index(); + MIBlock::Index b = other->index(); + + while (a != b) { + if (m_dominatorDepthForBlock[a] < m_dominatorDepthForBlock[b]) + b = m_domTree->immediateDominator(b); + else + a = m_domTree->immediateDominator(a); + } + + return m_miFunction->block(a); +} + +// For Nodes that end up inside loops, it'd be great if we can move (hoist) them out of the loop. +// To do that, we need a block that preceeds the loop. (So the block before the loop header.) +// This function calculates that hoist block if the original block is in a loop. +MIBlock *NodeScheduler::getHoistBlock(MIBlock *block) const +{ + if (m_loopInfo->isLoopHeader(block)) + return m_miFunction->block(m_domTree->immediateDominator(block->index())); + + // make the loop header a candidate: + MIBlock *loopHeader = m_loopInfo->loopHeaderFor(block); + if (loopHeader == nullptr) + return nullptr; // block is not in a loop + + // And now the tricky part: block has to dominate all exits from the loop. If it does not do + // that, it meanse that there is an exit from the loop that can be reached before block. In + // that case, hoisting from "block" to "loopHeader" would mean there now is an extra calculation + // that is not needed for a certain loop exit. + for (MIBlock *outEdge : m_loopInfo->loopExitsForLoop(loopHeader)) { + if (getCommonDominator(block, outEdge) != block) + return nullptr; + } + + return m_miFunction->block(m_domTree->immediateDominator(loopHeader->index())); +} + +NodeScheduler::NodeScheduler(Function *irFunction) + : m_irFunction(irFunction) + , m_vregs(irFunction->graph()->nodeCount(), std::numeric_limits<unsigned>::max()) + , m_live(irFunction->graph(), /*collectUses =*/ false /* do explicitly NOT collect uses! */) +{ +} + +MIFunction *NodeScheduler::buildMIFunction() +{ + m_miFunction = new MIFunction(m_irFunction); + + // step 1: build the CFG + auto roots = buildCFG(); + m_miFunction->renumberBlocks(); + m_miFunction->dump(QStringLiteral("CFG after renumbering")); + + Q_ASSERT(m_miFunction->block(MIFunction::StartBlockIndex)->index() + == MIFunction::StartBlockIndex); + Q_ASSERT(m_miFunction->block(MIFunction::StartBlockIndex)->instructions().front().opcode() + == Meta::Start); + + // step 2: build the dominator tree + if (lcDotCFG().isDebugEnabled()) + dumpDotCFG(); + m_domTree.reset(new DominatorTree(m_miFunction)); + m_dominatorDepthForBlock = m_domTree->calculateNodeDepths(); + + // step 3: find loops + m_loopInfo.reset(new LoopInfo(*m_domTree.data())); + m_loopInfo->detectLoops(); + + // step 4: schedule early + scheduleEarly(roots); + showNodesByBlock(QStringLiteral("nodes per block after early scheduling")); + + // step 5: schedule late + scheduleLate(roots); + showNodesByBlock(QStringLiteral("nodes per block after late scheduling")); + + // step 6: schedule instructions in each block + scheduleNodesInBlock(); + + m_miFunction->dump(QStringLiteral("MI before block scheduling")); + + // step 7: order the basic blocks in the CFG + BlockScheduler blockScheduler(*m_domTree.data(), *m_loopInfo.data()); + m_miFunction->setBlockOrder(blockScheduler.scheduledBlockSequence()); + + // we're done + m_miFunction->renumberInstructions(); + m_miFunction->setVregCount(m_nextVReg); + m_miFunction->dump(QStringLiteral("MI after scheduling")); + return m_miFunction; +} + +static Node *splitEdge(Function *irFunction, Node *node, unsigned inputIndex) +{ + Graph *g = irFunction->graph(); + Node *in = node->input(inputIndex); + Node *region = g->createNode(g->opBuilder()->getRegion(1), &in, 1); + Node *jump = g->createNode(g->opBuilder()->get<Meta::Jump>(), ®ion, 1); + + qCDebug(lcSched) << "splitting critical edge from node" << node->id() + << "to node" << node->input(inputIndex)->id() + << "by inserting jump node" << jump->id() + << "and region node" << region->id(); + + node->replaceInput(inputIndex, jump); + return jump; +} + +// See Chapter 6.3.1 of https://scholarship.rice.edu/bitstream/handle/1911/96451/TR95-252.pdf for +// a description of the algorithm. +std::vector<Node *> NodeScheduler::buildCFG() +{ + std::vector<Node *> roots; + roots.reserve(32); + NodeWorkList todo(m_irFunction->graph()); + + auto enqueueControlInputs = [this, &todo](Node *node) { + for (unsigned i = 0, ei = node->operation()->controlInputCount(); i != ei; ++i) { + const auto inputIndex = node->operation()->indexOfFirstControl() + i; + Node *input = node->input(inputIndex); + Q_ASSERT(input); + if (node->operation()->kind() == Meta::Region + && node->operation()->controlInputCount() > 1 + && isControlFlowSplit(input)) { + // critical edge! + input = splitEdge(m_irFunction, node, inputIndex); + m_live.markReachable(input); + m_live.markReachable(input->controlInput(0)); + } + if (!isBlockTerminator(input)) { + auto g = m_irFunction->graph(); + Node *jump = g->createNode(g->opBuilder()->get<Meta::Jump>(), &input, 1); + node->replaceInput(inputIndex, jump); + m_live.markReachable(jump); + qCDebug(lcSched) << "inserting jump node" << jump->id() + << "between node" << node->id() + << "and node" << input->id(); + input = jump; + } + todo.enqueue(input); + } + }; + + // create the CFG by scheduling control dependencies that start/end blocks: + todo.enqueue(m_irFunction->graph()->endNode()); + while (Node *node = todo.dequeueNextNodeForVisiting()) { + Q_ASSERT(isBlockTerminator(node)); + + if (schedulerData(node)->minimumBlock) + continue; + + MIBlock *b = m_miFunction->addBlock(); + + qCDebug(lcSched) << "scheduling node" << node->id() << "as terminator for new block" + << b->index(); + b->instructions().push_front(createMIInstruction(node)); + placeFixed(node, b, Schedule); + roots.push_back(node); + + if (Node *framestate = node->frameStateInput()) { + placeFixed(framestate, b, DontSchedule); + qCDebug(lcSched) << ".. also scheduling framestate dependency node" << node->id() + << "in block" << b->index(); + } + + if (node->opcode() == Meta::End) { + enqueueControlInputs(node); + continue; + } + + while (true) { + Node *controlDependency = node->controlInput(0); + if (!controlDependency) + break; + if (todo.isVisited(controlDependency)) + break; + if (schedulerData(controlDependency)->isFixed) + break; + + if (controlDependency->opcode() == Meta::Start) { + qCDebug(lcSched) << "placing start node" << controlDependency->id() + << "in block" << b->index(); + handleStartNode(controlDependency, b); + placeFixed(controlDependency, b, Schedule); + roots.push_back(controlDependency); + break; // we're done with this block + } + if (isBlockTerminator(controlDependency)) { + qCDebug(lcSched) << "found terminator node" << controlDependency->id() + << "for another block, so finish block" << b->index(); + Node *merge = m_irFunction->graph()->createNode( + m_irFunction->graph()->opBuilder()->getRegion(1), &controlDependency, 1); + node->replaceInput(node->operation()->indexOfFirstControl(), merge); + addBlockStart(roots, merge, b); + placeFixed(merge, b, Schedule); + m_live.markReachable(merge); + todo.enqueue(controlDependency); + break; // we're done with this block + } + if (canStartBlock(controlDependency) + || schedulerData(controlDependency->controlInput())->isFixed) { + qCDebug(lcSched) << "found block start node" << controlDependency->id() + << "for this block, so finish block" << b->index(); + addBlockStart(roots, controlDependency, b); + placeFixed(controlDependency, b, Schedule); + roots.push_back(controlDependency); + enqueueControlInputs(controlDependency); + break; // we're done with this block + } + qCDebug(lcSched) << "skipping node" << controlDependency->id(); + node = controlDependency; + } + } + + // link the edges of the MIBlocks, and add basic-block arguments: + for (MIBlock *toBlock : m_miFunction->blocks()) { + Q_ASSERT(!toBlock->instructions().empty()); + MIInstr &instr = toBlock->instructions().front(); + Node *toNode = instr.irNode(); + const auto opcode = toNode->operation()->kind(); + if (opcode == Meta::Region) { + unsigned inputNr = 0; + for (Node *input : toNode->inputs()) { + MIBlock *fromBlock = schedulerData(input)->minimumBlock; + fromBlock->addOutEdge(toBlock); + toBlock->addInEdge(fromBlock); + MIInstr &fromTerminator = fromBlock->instructions().back(); + if (fromTerminator.irNode()->opcode() == Meta::Jump || + fromTerminator.irNode()->opcode() == Meta::UnwindDispatch) { + unsigned arg = 0; + for (const MIOperand &bbArg : toBlock->arguments()) { + fromTerminator.setOperand(arg++, + createMIOperand(bbArg.irNode()->input(inputNr))); + } + } + ++inputNr; + } + } else if (opcode == Meta::End) { + for (Node *input : toNode->inputs()) { + MIBlock *fromBlock = schedulerData(input)->minimumBlock; + fromBlock->addOutEdge(toBlock); + toBlock->addInEdge(fromBlock); + } + } else if (Node *fromNode = toNode->controlInput()) { + MIBlock *fromBlock = schedulerData(fromNode)->minimumBlock; + fromBlock->addOutEdge(toBlock); + toBlock->addInEdge(fromBlock); + } + } + + m_irFunction->dump(QStringLiteral("graph after building CFG")); + + auto startBlock = schedulerData(m_irFunction->graph()->startNode())->minimumBlock; + m_miFunction->setStartBlock(startBlock); + + if (lcSched().isDebugEnabled()) + m_miFunction->dump(QStringLiteral("control flow graph before renumbering")); + m_miFunction->verifyCFG(); + + return roots; +} + +// See Chapter 6.3.3 of https://scholarship.rice.edu/bitstream/handle/1911/96451/TR95-252.pdf for +// a description of the algorithm. +void NodeScheduler::scheduleEarly(const std::vector<Node *> &roots) +{ + // scheduling one node might have the effect of queueing its dependencies + NodeWorkList todo(m_irFunction->graph()); + for (Node *root : roots) { + todo.enqueue(root); + while (Node *node = todo.dequeueNextNodeForVisiting()) + scheduleEarly(node, todo); + } +} + +void NodeScheduler::scheduleEarly(Node *node, NodeWorkList &todo) +{ + qCDebug(lcSched) << "Scheduling node" << node->id() << "early..."; + + SchedulerData *sd = schedulerData(node); + + if (sd->isFixed) { + // Fixed nodes already know their schedule early position. + qCDebug(lcSched) << ".. Fixed node" << node->id() << "is on minimum block" + << sd->minimumBlock->index() + << "which has dominator depth" + << m_dominatorDepthForBlock[sd->minimumBlock->index()]; + } + + for (Node *use : node->uses()) { + if (isLive(use)) + propagateMinimumPosition(sd->minimumBlock, use, todo); + else + qCDebug(lcSched) << ".. Skipping node" << use->id() << "as it's not live"; + } +} + +void NodeScheduler::propagateMinimumPosition(MIBlock *newMinimumPosition, Node *toNode, + NodeWorkList &todo) +{ + Q_ASSERT(newMinimumPosition); + + SchedulerData *sd = schedulerData(toNode); + if (sd->isFixed) // nothing to do + return; + + MIBlock::Index minimumBlockIndex = sd->minimumBlock + ? sd->minimumBlock->index() + : MIFunction::StartBlockIndex; + Q_ASSERT(m_domTree->insideSameDominatorChain(newMinimumPosition->index(), minimumBlockIndex)); + if (sd->minimumBlock == nullptr + || m_dominatorDepthForBlock[newMinimumPosition->index()] + > m_dominatorDepthForBlock[minimumBlockIndex]) { + // ok, some input for toNode is scheduled *after* our current minimum depth, so we need + // to adjust out minimal position. (This might involve rescheduling toNode's uses.) + place(toNode, newMinimumPosition); + todo.reEnqueue(toNode); + qCDebug(lcSched) << ".. Propagating minimum block" << sd->minimumBlock->index() + << "which has dominator depth" + << m_dominatorDepthForBlock[newMinimumPosition->index()] + << "to use node" << toNode->id(); + } else { + qCDebug(lcSched) << ".. Minimum position" << newMinimumPosition->index() + << "is not better than" << minimumBlockIndex + << "for node" << toNode->id(); + } +} + +// See Chapter 6.3.4 of https://scholarship.rice.edu/bitstream/handle/1911/96451/TR95-252.pdf for +// a description of the algorithm. +// +// There is one extra detail not described in the thesis mentioned above: loop hoisting. Before we +// place a node in the latest block that dominates all uses, we check if we accidentally sink it +// *into* a loop (meaning the latest block is inside a loop, where it is not if the earliest +// possible block would be chosen). If we detect that a nodes is going to sink into a loop, we walk +// the dominator path from the latest block up to the earliest block, and pick the first block that +// is in the same loop (if any) as the earlieast block. +// +// As noted in the thesis, this strategy might enlongen life times, which could be harmful for +// values that are simple to re-materialized or re-calculate. +void NodeScheduler::scheduleLate(const std::vector<Node *> &roots) +{ + NodeWorkList todo(m_irFunction->graph()); + for (Node *root : roots) + todo.enqueue(root); + + while (Node *node = todo.dequeueNextNodeForVisiting()) + scheduleNodeLate(node, todo); +} + +void NodeScheduler::scheduleNodeLate(Node *node, NodeWorkList &todo) +{ + if (!needsScheduling(node)) + return; + qCDebug(lcSched) << "Scheduling node" << node->id() << "late..."; + + auto sd = schedulerData(node); + if (sd->unscheduledUses == SchedulerData::NotYetCalculated) { + sd->unscheduledUses = 0; + for (Node *use : node->uses()) { + if (!isLive(use)) + continue; + if (!needsScheduling(use)) + continue; + if (schedulerData(use)->isFixed) + continue; + todo.enqueue(use); + ++sd->unscheduledUses; + } + } + + if (sd->isFixed) { + qCDebug(lcSched) << ".. it's fixed"; + enqueueInputs(node, todo); + return; + } + + if (sd->unscheduledUses) { + qCDebug(lcSched).noquote() << ".. not all uses are fixed, postpone it."<< todo.status(node); + return; + } + + MIBlock *&minBlock = sd->minimumBlock; + if (minBlock == nullptr) + minBlock = m_miFunction->block(MIFunction::StartBlockIndex); + MIBlock *commonUseDominator = commonDominatorOfUses(node); + qCDebug(lcSched) << ".. common use dominator: block" << commonUseDominator->index(); + + // the minBlock has to dominate the uses, *and* the common dominator of the uses. + Q_ASSERT(minBlock->index() == commonUseDominator->index() || + m_domTree->dominates(minBlock->index(), commonUseDominator->index())); + + // we now found the deepest block, so use it as the target block: + MIBlock *targetBlock = commonUseDominator; + + if (node->opcode() == Meta::FrameState) { + // never hoist framestates: they're used (among other things) to keep their inputs alive, so + // hoisting them out would end the life-time of those inputs prematurely + } else { + // but we want to prevent blocks sinking into loops unnecessary + MIBlock *hoistBlock = getHoistBlock(targetBlock); + while (hoistBlock + && m_dominatorDepthForBlock[hoistBlock->index()] + >= m_dominatorDepthForBlock[minBlock->index()]) { + qCDebug(lcSched) << ".. hoisting node" << node->id() << "from block" + << targetBlock->index() << "to block" << hoistBlock->index(); + // ok, so there a) is a hoist block and b) it's deeper than the minimum block, + // so lift it up one level ... + targetBlock = hoistBlock; + // ... and see if we can lift it one more level + hoistBlock = getHoistBlock(targetBlock); + } + } + + qCDebug(lcSched) << ".. fixating it in block" << targetBlock->index() + << "where the minimum block was" << minBlock->index(); + + placeFixed(node, targetBlock, DontSchedule); + enqueueInputs(node, todo); +} + +void NodeScheduler::enqueueInputs(Node *node, NodeWorkList &todo) +{ + for (Node *input : node->inputs()) { + if (!input) + continue; + if (!needsScheduling(input)) + continue; + if (!isLive(input)) + continue; + auto sd = schedulerData(input); + if (sd->isFixed) + continue; + qCDebug(lcSched).noquote() << "... enqueueing input node" << input->id() + << todo.status(input); + if (sd->unscheduledUses != SchedulerData::NotYetCalculated) { + if (sd->unscheduledUses > 0) + --sd->unscheduledUses; + if (sd->unscheduledUses == 0) + todo.reEnqueue(input); + } else { + todo.reEnqueue(input); + } + } +} + +Node *NodeScheduler::firstNotFixedUse(Node *node) +{ + for (Node *use : node->uses()) { + if (!isLive(use)) + continue; + if (!schedulerData(use)->isFixed) + return use; + } + return nullptr; +} + +MIBlock *NodeScheduler::commonDominatorOfUses(Node *node) +{ + MIBlock *commonDominator = nullptr; + for (auto useIt = node->uses().begin(), useEIt = node->uses().end(); useIt != useEIt; ++useIt) { + Node *use = *useIt; + if (!isLive(use)) + continue; + // region nodes use other nodes through their control dependency. But those nodes should + // already have been placed as block terminators before. + Q_ASSERT(use->opcode() != Meta::Region); + if (use->opcode() == Meta::Phi || use->opcode() == Meta::EffectPhi) { + // find the predecessor block defining this input + Node *region = use->controlInput(0); + Node *input = region->controlInput(useIt.inputIndex()); + use = input; + } + auto minBlock = schedulerData(use)->minimumBlock; + if (commonDominator == nullptr) + commonDominator = minBlock; + else + commonDominator = getCommonDominator(commonDominator, minBlock); + } + return commonDominator; +} + +void NodeScheduler::scheduleNodesInBlock() +{ + auto startBlock = m_miFunction->block(MIFunction::StartBlockIndex); + for (Node *n : m_live.reachable()) { + auto sd = schedulerData(n); + if (!sd->minimumBlock) + sd->minimumBlock = startBlock; + } + + std::vector<std::vector<SchedulerData *>> nodesForBlock; + nodesForBlock.resize(m_miFunction->blockCount()); + + for (auto sd : m_schedulerData) { + if (sd == nullptr) + continue; + if (!isLive(sd->node)) + continue; + sd->unscheduledUses = 0; + for (Node *use : sd->node->uses()) { + if (!needsScheduling(use)) + continue; + if (schedulerData(use)->isScheduledInBlock) + continue; + if (schedulerData(use)->minimumBlock == sd->minimumBlock) + ++sd->unscheduledUses; + } + if (sd->unscheduledUses == 0) + nodesForBlock[sd->minimumBlock->index()].push_back(sd); + } + + NodeWorkList todo(m_irFunction->graph()); + for (MIBlock *b : m_miFunction->blocks()) { + qCDebug(lcSched) << "Scheduling inside block" << b->index(); + MIInstr *insertionPoint = &b->instructions().back(); + todo.enqueue(insertionPoint->irNode()); + scheduleNodesInBlock(insertionPoint, b, todo); + Q_ASSERT(todo.isEmpty()); + for (auto sd : nodesForBlock[b->index()]) { + if (!sd->isScheduledInBlock) + todo.enqueue(sd->node); + } + scheduleNodesInBlock(insertionPoint, b, todo); + Q_ASSERT(todo.isEmpty()); + todo.reset(); + } +} + +void NodeScheduler::scheduleNodesInBlock(MIInstr *&insertionPoint, MIBlock *b, NodeWorkList &todo) +{ + while (Node *n = todo.dequeueNextNodeForVisiting()) + scheduleNodeInBlock(n, insertionPoint, b, todo); +} + +void NodeScheduler::scheduleNodeInBlock(Node *node, MIInstr *&insertionPoint, MIBlock *b, + NodeWorkList &todo) +{ + Q_ASSERT(!node->isDead()); + + if (!isLive(node)) + return; + + if (!needsScheduling(node)) + return; + + auto nodeData = schedulerData(node); + if (nodeData->minimumBlock != b) + return; + + const bool wasAlreadyScheduled = nodeData->isScheduledInBlock; + if (!wasAlreadyScheduled) { + if (nodeData->unscheduledUses) + return; + + scheduleNodeNow(node, insertionPoint); + } + + if (Node *framestate = node->frameStateInput()) + scheduleNodeInBlock(framestate, insertionPoint, b, todo); + + for (Node *input : node->inputs()) { + if (!input) + continue; + if (!needsScheduling(input)) + continue; + if (!isLive(input)) + continue; + auto inputInfo = schedulerData(input); + if (inputInfo->isScheduledInBlock) + continue; + Q_ASSERT(inputInfo->minimumBlock != nullptr); + if (inputInfo->minimumBlock != b) + continue; + Q_ASSERT(!input->isDead()); + Q_ASSERT(inputInfo->unscheduledUses != SchedulerData::NotYetCalculated); + if (!wasAlreadyScheduled && inputInfo->unscheduledUses > 0) + --inputInfo->unscheduledUses; + if (inputInfo->unscheduledUses == 0) + todo.enqueue(input); + } +} + +void NodeScheduler::scheduleNodeNow(Node *node, MIInstr *&insertionPoint) +{ + qCDebug(lcSched) << ".. scheduling node" << node->id() + << "in block" << insertionPoint->parent()->index() + << "before node" << insertionPoint->irNode()->id(); + + MIInstr *newInstr = createMIInstruction(node); + newInstr->insertBefore(insertionPoint); + insertionPoint = newInstr; +} + +void NodeScheduler::place(Node *node, MIBlock *b) +{ + Q_ASSERT(!node->isDead()); + + if (b == nullptr) + return; + + schedulerData(node)->minimumBlock = b; +} + +void NodeScheduler::placeFixed(Node *node, MIBlock *b, ScheduleOrNot markScheduled) +{ + place(node, b); + auto sd = schedulerData(node); + Q_ASSERT(!sd->isFixed); + sd->isFixed = true; + sd->isScheduledInBlock = markScheduled == Schedule; +} + +unsigned NodeScheduler::vregForNode(Node *node) +{ + unsigned &vreg = m_vregs[unsigned(node->id())]; + if (vreg == std::numeric_limits<unsigned>::max()) + vreg = m_nextVReg++; + return vreg; +} + +void NodeScheduler::addBlockStart(std::vector<Node *> &roots, Node *startNode, MIBlock *block) +{ + block->instructions().insert(block->instructions().begin(), createMIInstruction(startNode)); + if (startNode->opcode() == Meta::Region) { + for (Node *use : startNode->uses()) { + if (use->opcode() == Meta::Phi && isLive(use)) { + block->addArgument(MIOperand::createVirtualRegister(use, vregForNode(use))); + placeFixed(use, block, Schedule); + roots.push_back(use); + } else if (use->opcode() == Meta::EffectPhi && isLive(use)) { + placeFixed(use, block, Schedule); + roots.push_back(use); + } + } + } +} + +void NodeScheduler::handleStartNode(Node *startNode, MIBlock *startBlock) +{ + startBlock->instructions().push_front(createMIInstruction(startNode)); + + QVarLengthArray<Node *, 32> args; + for (Node *use : startNode->uses()) { + switch (use->opcode()) { + case Meta::Engine: Q_FALLTHROUGH(); + case Meta::CppFrame: + case Meta::Function: + placeFixed(use, startBlock, Schedule); + break; + case Meta::Parameter: { + auto param = ParameterPayload::get(*use->operation()); + int idx = int(param->parameterIndex()); + if (args.size() <= idx) + args.resize(idx + 1); + args[int(idx)] = use; + placeFixed(use, startBlock, Schedule); + } + break; + default: + break; + } + } + + for (unsigned i = 0, ei = unsigned(args.size()); i != ei; ++i) { + if (Node *arg = args.at(int(i))) + startBlock->addArgument(MIOperand::createJSStackSlot(arg, i)); + } +} + +static Node *firstControlOutput(Node *n) +{ + for (auto it = n->uses().begin(), eit = n->uses().end(); it != eit; ++it) { + if (it.isUsedAsControl()) + return *it; + } + return nullptr; +} + +MIInstr *NodeScheduler::createMIInstruction(Node *node) +{ + const auto opcode = node->operation()->kind(); + + unsigned nArgs = 0; + switch (opcode) { + case Meta::UnwindDispatch: Q_FALLTHROUGH(); + case Meta::Jump: { + Node *target = firstControlOutput(node); + if (target->opcode() == Meta::Region) { + for (Node *n : target->uses()) { + if (n->opcode() == Meta::Phi && isLive(n)) + ++nArgs; + } + } + } + break; + case Meta::Branch: + nArgs = 1; + break; + case Meta::Return: + nArgs = 1; + break; + default: + nArgs = node->operation()->valueInputCount(); + break; + } + + MIInstr *instr = MIInstr::create(m_irFunction->pool(), node, nArgs); + for (unsigned i = 0, ei = node->operation()->valueInputCount(); i != ei; ++i) + instr->setOperand(i, createMIOperand(node->input(i))); + if (node->opcode() != Meta::Start && node->operation()->valueOutputCount() > 0) + instr->setDestination(createMIOperand(node)); + + schedulerData(node)->isScheduledInBlock = true; + return instr; +} + +MIOperand NodeScheduler::createMIOperand(Node *node) +{ + if (node->operation()->isConstant()) + return MIOperand::createConstant(node); + + auto opcode = node->operation()->kind(); + switch (opcode) { + case Meta::Parameter: + return MIOperand::createJSStackSlot( + node, unsigned(ParameterPayload::get(*node->operation())->parameterIndex())); + case Meta::Engine: + return MIOperand::createEngineRegister(node); + case Meta::CppFrame: + return MIOperand::createCppFrameRegister(node); + case Meta::Function: + return MIOperand::createFunction(node); + default: + if ((node->opcode() == Meta::Call + && CallPayload::get(*node->operation())->callee() == Meta::JSThisToObject) + || node->opcode() == Meta::StoreThis) { + return MIOperand::createJSStackSlot(node, CallData::This); + } else { + return MIOperand::createVirtualRegister(node, vregForNode(node)); + } + } +} + +void NodeScheduler::showNodesByBlock(const QString &description) const +{ + if (!lcSched().isDebugEnabled()) + return; + + qCDebug(lcSched) << description; + + for (MIBlock *b : m_miFunction->blocks()) { + QString s; + for (const SchedulerData *sd : m_schedulerData) { + if (!sd) + continue; + if (!isLive(sd->node)) + continue; + if (sd->minimumBlock == b) { + if (!s.isEmpty()) + s += QStringLiteral(", "); + s += QStringLiteral("%1 (%2)").arg(QString::number(sd->node->id()), + sd->node->operation()->debugString()); + } + } + if (s.isEmpty()) + s = QStringLiteral("<<none>>"); + qCDebug(lcSched, "Nodes in block %u: %s", b->index(), s.toUtf8().constData()); + } +} + +void NodeScheduler::dumpDotCFG() const +{ + QString out; + out += QLatin1Char('\n'); + out += QStringLiteral("digraph{root=\"L%1\" label=\"Control Flow Graph\";" + "node[shape=circle];edge[dir=forward fontsize=10]\n") + .arg(MIFunction::StartBlockIndex); + for (MIBlock *src : m_miFunction->blocks()) { + for (MIBlock *dst : src->outEdges()) { + out += QStringLiteral("L%1->L%2\n").arg(QString::number(src->index()), + QString::number(dst->index())); + } + } + out += QStringLiteral("}\n"); + qCDebug(lcDotCFG).nospace().noquote() << out; +} + +} // IR namespace +} // QV4 namespace +QT_END_NAMESPACE diff --git a/src/qml/jit/qv4schedulers_p.h b/src/qml/jit/qv4schedulers_p.h new file mode 100644 index 0000000000..f9179816df --- /dev/null +++ b/src/qml/jit/qv4schedulers_p.h @@ -0,0 +1,162 @@ +/**************************************************************************** +** +** Copyright (C) 2018 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtQml module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QV4SCHEDULER_P_H +#define QV4SCHEDULER_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists purely as an +// implementation detail. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include "qv4global_p.h" +#include "qv4mi_p.h" +#include "qv4node_p.h" +#include "qv4domtree_p.h" +#include "qv4loopinfo_p.h" + +QT_REQUIRE_CONFIG(qml_tracing); + +QT_BEGIN_NAMESPACE + +namespace QV4 { +namespace IR { + +// Node scheduling "flattens" the graph into basic blocks with an ordered list of instructions. +// +// The various steps are mentioned in buildMIFunction, but the general idea is described in +// https://scholarship.rice.edu/bitstream/handle/1911/96451/TR95-252.pdf in chapter 6. +class NodeScheduler final +{ + Q_DISABLE_COPY_MOVE(NodeScheduler) + + class SchedulerData final { + Q_DISABLE_COPY_MOVE(SchedulerData) + public: + static SchedulerData *create(QQmlJS::MemoryPool *pool) + { return pool->New<SchedulerData>(); } + + SchedulerData() = default; + ~SchedulerData() = default; + + Node *node = nullptr; + MIBlock *minimumBlock = nullptr; + bool isFixed = false; + bool isScheduledInBlock = false; + static constexpr unsigned NotYetCalculated = std::numeric_limits<unsigned>::max(); + unsigned unscheduledUses = NotYetCalculated; + }; + +public: + NodeScheduler(Function *irFunction); + ~NodeScheduler() = default; + + MIFunction *buildMIFunction(); + +private: + std::vector<Node *> buildCFG(); + void scheduleEarly(const std::vector<Node *> &roots); + void scheduleEarly(Node *node, NodeWorkList &todo); + void propagateMinimumPosition(MIBlock *newMinimumPosition, Node *toNode, NodeWorkList &todo); + void scheduleLate(const std::vector<Node *> &roots); + void scheduleNodeLate(Node *node, NodeWorkList &todo); + void enqueueInputs(Node *node, NodeWorkList &todo); + Node *firstNotFixedUse(Node *node); + MIBlock *commonDominatorOfUses(Node *node); + void scheduleNodesInBlock(); + void scheduleNodesInBlock(MIInstr *&insertionPoint, MIBlock *b, NodeWorkList &todo); + void scheduleNodeInBlock(Node *node, MIInstr *&insertionPoint, MIBlock *b, NodeWorkList &todo); + void scheduleNodeNow(Node *node, MIInstr *&insertionPoint); + + void place(Node *node, MIBlock *b); + enum ScheduleOrNot { DontSchedule, Schedule }; + void placeFixed(Node *node, MIBlock *b, ScheduleOrNot markScheduled); + unsigned vregForNode(Node *node); + void addBlockStart(std::vector<Node *> &roots, Node *startNode, MIBlock *block); + void enqueueControlInputs(Node *node); + void handleStartNode(Node *startNode, MIBlock *startBlock); + MIInstr *createMIInstruction(Node *node); + MIOperand createMIOperand(Node *node); + SchedulerData *schedulerData(Node *n) + { + if (Q_UNLIKELY(m_schedulerData.size() <= n->id())) + m_schedulerData.resize(n->id() + 8); + SchedulerData *&sd = m_schedulerData[n->id()]; + if (Q_UNLIKELY(sd == nullptr)) { + sd = SchedulerData::create(m_irFunction->pool()); + sd->node = n; + } + return sd; + } + bool isLive(Node *n) const + { return m_live.isReachable(n->id()); } + bool canStartBlock(Node *node) const; + bool isControlFlowSplit(Node *node) const; + bool isBlockTerminator(Node *node) const; + MIBlock *getCommonDominator(MIBlock *one, MIBlock *other) const; + MIBlock *getHoistBlock(MIBlock *block) const; + + void showNodesByBlock(const QString &description) const; + + void dumpDotCFG() const; + +private: + Function *m_irFunction = nullptr; + MIFunction *m_miFunction = nullptr; + QScopedPointer<LoopInfo> m_loopInfo; + QScopedPointer<DominatorTree> m_domTree; + std::vector<int> m_dominatorDepthForBlock; + std::vector<unsigned> m_vregs; + std::vector<SchedulerData *> m_schedulerData; + NodeCollector m_live; + unsigned m_nextVReg = 0; +}; + +} // namespace IR +} // namespace QV4 + +QT_END_NAMESPACE + +#endif // QV4SCHEDULER_P_H diff --git a/src/qml/jit/qv4tracingjit.cpp b/src/qml/jit/qv4tracingjit.cpp index 889c0516d3..c8974b3a1b 100644 --- a/src/qml/jit/qv4tracingjit.cpp +++ b/src/qml/jit/qv4tracingjit.cpp @@ -42,6 +42,8 @@ #include "qv4vme_moth_p.h" #include "qv4graphbuilder_p.h" #include "qv4lowering_p.h" +#include "qv4mi_p.h" +#include "qv4schedulers_p.h" QT_BEGIN_NAMESPACE @@ -78,6 +80,11 @@ void Moth::runTracingJit(QV4::Function *function) IR::GenericLowering(irFunction).lower(); irFunction.dump(QStringLiteral("after generic lowering")); irFunction.verify(); + + IR::NodeScheduler scheduler(&irFunction); + QScopedPointer<IR::MIFunction> miFunction(scheduler.buildMIFunction()); + miFunction->dump(QStringLiteral("initial MI")); + irFunction.verify(); } } // QV4 namespace |