V4 tracing: Add a scheduler for the tracing JIT IR

This is a scheduler for the graph nodes, which first reconstructs the
control-flow graph, and then places all remaining nodes inside the basic
blocks.

The output of this pass is an MIFunction (MI = Machine Interface),
which uses a representation suitable for feeding to an assembler. Note
however that it still uses "virtual registers" at this point, so the
next pass will have to place those virtual registers in physical
registers or on a stack.

The code for the dominator tree calculation, block scheduling, loop info
and the blockset were lifted from the 5.10 JIT.

Change-Id: I11c4cc3f64fedba6dd4275b35bbea85d30d76f7d
Reviewed-by: Ulf Hermann <ulf.hermann@qt.io>

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>(), &region, 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