diff options
Diffstat (limited to 'src/qml/jit/qv4domtree.cpp')
| -rw-r--r-- | src/qml/jit/qv4domtree.cpp | 436 |
1 files changed, 0 insertions, 436 deletions
diff --git a/src/qml/jit/qv4domtree.cpp b/src/qml/jit/qv4domtree.cpp deleted file mode 100644 index 9484f4e2dc..0000000000 --- a/src/qml/jit/qv4domtree.cpp +++ /dev/null @@ -1,436 +0,0 @@ -/**************************************************************************** -** -** 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 |