diff options
Diffstat (limited to 'src/qml/jit/qv4schedulers.cpp')
| -rw-r--r-- | src/qml/jit/qv4schedulers.cpp | 912 |
1 files changed, 912 insertions, 0 deletions
diff --git a/src/qml/jit/qv4schedulers.cpp b/src/qml/jit/qv4schedulers.cpp new file mode 100644 index 0000000000..0dffefa951 --- /dev/null +++ b/src/qml/jit/qv4schedulers.cpp @@ -0,0 +1,912 @@ +/**************************************************************************** +** +** Copyright (C) 2018 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtQml module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include <QtCore/qloggingcategory.h> + +#include "qv4schedulers_p.h" +#include "qv4util_p.h" +#include "qv4graph_p.h" +#include "qv4blockscheduler_p.h" +#include "qv4stackframe_p.h" + +QT_BEGIN_NAMESPACE +namespace QV4 { +namespace IR { + +Q_LOGGING_CATEGORY(lcSched, "qt.v4.ir.scheduling") +Q_LOGGING_CATEGORY(lcDotCFG, "qt.v4.ir.scheduling.cfg") + +static bool needsScheduling(Node *n) +{ + if (n->operation()->isConstant()) + return false; + switch (n->opcode()) { + case Meta::Function: Q_FALLTHROUGH(); + case Meta::CppFrame: + case Meta::Phi: + case Meta::EffectPhi: + return false; + default: + return true; + } +} + +bool NodeScheduler::canStartBlock(Node *node) const +{ + switch (node->operation()->kind()) { + case Meta::Start: Q_FALLTHROUGH(); + case Meta::IfTrue: + case Meta::IfFalse: + case Meta::Region: + case Meta::HandleUnwind: + case Meta::OnException: + return true; + + default: + return false; + } +} + +bool NodeScheduler::isControlFlowSplit(Node *node) const +{ + int nOutputs = node->operation()->controlOutputCount(); + if (nOutputs == 2) { + // if there is a "missing" control output, it's for exception flow without unwinder + int controlUses = 0; + auto uses = node->uses(); + for (auto it = uses.begin(), eit = uses.end(); it != eit; ++it) { + if (isLive(*it) && it.isUsedAsControl()) + ++controlUses; + } + return controlUses == 2; + } + return nOutputs > 2; +} + +bool NodeScheduler::isBlockTerminator(Node *node) const +{ + switch (node->operation()->kind()) { + case Meta::Branch: Q_FALLTHROUGH(); + case Meta::Jump: + case Meta::Return: + case Meta::TailCall: + case Meta::UnwindDispatch: + case Meta::End: + return true; + case Meta::Call: + return isControlFlowSplit(node); + default: + return false; + } +} + +MIBlock *NodeScheduler::getCommonDominator(MIBlock *one, MIBlock *other) const +{ + MIBlock::Index a = one->index(); + MIBlock::Index b = other->index(); + + while (a != b) { + if (m_dominatorDepthForBlock[a] < m_dominatorDepthForBlock[b]) + b = m_domTree->immediateDominator(b); + else + a = m_domTree->immediateDominator(a); + } + + return m_miFunction->block(a); +} + +// For Nodes that end up inside loops, it'd be great if we can move (hoist) them out of the loop. +// To do that, we need a block that preceeds the loop. (So the block before the loop header.) +// This function calculates that hoist block if the original block is in a loop. +MIBlock *NodeScheduler::getHoistBlock(MIBlock *block) const +{ + if (m_loopInfo->isLoopHeader(block)) + return m_miFunction->block(m_domTree->immediateDominator(block->index())); + + // make the loop header a candidate: + MIBlock *loopHeader = m_loopInfo->loopHeaderFor(block); + if (loopHeader == nullptr) + return nullptr; // block is not in a loop + + // And now the tricky part: block has to dominate all exits from the loop. If it does not do + // that, it meanse that there is an exit from the loop that can be reached before block. In + // that case, hoisting from "block" to "loopHeader" would mean there now is an extra calculation + // that is not needed for a certain loop exit. + for (MIBlock *outEdge : m_loopInfo->loopExitsForLoop(loopHeader)) { + if (getCommonDominator(block, outEdge) != block) + return nullptr; + } + + return m_miFunction->block(m_domTree->immediateDominator(loopHeader->index())); +} + +NodeScheduler::NodeScheduler(Function *irFunction) + : m_irFunction(irFunction) + , m_vregs(irFunction->graph()->nodeCount(), std::numeric_limits<unsigned>::max()) + , m_live(irFunction->graph(), /*collectUses =*/ false /* do explicitly NOT collect uses! */) +{ +} + +MIFunction *NodeScheduler::buildMIFunction() +{ + m_miFunction = new MIFunction(m_irFunction); + + // step 1: build the CFG + auto roots = buildCFG(); + m_miFunction->renumberBlocks(); + m_miFunction->dump(QStringLiteral("CFG after renumbering")); + + Q_ASSERT(m_miFunction->block(MIFunction::StartBlockIndex)->index() + == MIFunction::StartBlockIndex); + Q_ASSERT(m_miFunction->block(MIFunction::StartBlockIndex)->instructions().front().opcode() + == Meta::Start); + + // step 2: build the dominator tree + if (lcDotCFG().isDebugEnabled()) + dumpDotCFG(); + m_domTree.reset(new DominatorTree(m_miFunction)); + m_dominatorDepthForBlock = m_domTree->calculateNodeDepths(); + + // step 3: find loops + m_loopInfo.reset(new LoopInfo(*m_domTree.data())); + m_loopInfo->detectLoops(); + + // step 4: schedule early + scheduleEarly(roots); + showNodesByBlock(QStringLiteral("nodes per block after early scheduling")); + + // step 5: schedule late + scheduleLate(roots); + showNodesByBlock(QStringLiteral("nodes per block after late scheduling")); + + // step 6: schedule instructions in each block + scheduleNodesInBlock(); + + m_miFunction->dump(QStringLiteral("MI before block scheduling")); + + // step 7: order the basic blocks in the CFG + BlockScheduler blockScheduler(*m_domTree.data(), *m_loopInfo.data()); + m_miFunction->setBlockOrder(blockScheduler.scheduledBlockSequence()); + + // we're done + m_miFunction->renumberInstructions(); + m_miFunction->setVregCount(m_nextVReg); + m_miFunction->dump(QStringLiteral("MI after scheduling")); + return m_miFunction; +} + +static Node *splitEdge(Function *irFunction, Node *node, unsigned inputIndex) +{ + Graph *g = irFunction->graph(); + Node *in = node->input(inputIndex); + Node *region = g->createNode(g->opBuilder()->getRegion(1), &in, 1); + Node *jump = g->createNode(g->opBuilder()->get<Meta::Jump>(), ®ion, 1); + + qCDebug(lcSched) << "splitting critical edge from node" << node->id() + << "to node" << node->input(inputIndex)->id() + << "by inserting jump node" << jump->id() + << "and region node" << region->id(); + + node->replaceInput(inputIndex, jump); + return jump; +} + +// See Chapter 6.3.1 of https://scholarship.rice.edu/bitstream/handle/1911/96451/TR95-252.pdf for +// a description of the algorithm. +std::vector<Node *> NodeScheduler::buildCFG() +{ + std::vector<Node *> roots; + roots.reserve(32); + NodeWorkList todo(m_irFunction->graph()); + + auto enqueueControlInputs = [this, &todo](Node *node) { + for (unsigned i = 0, ei = node->operation()->controlInputCount(); i != ei; ++i) { + const auto inputIndex = node->operation()->indexOfFirstControl() + i; + Node *input = node->input(inputIndex); + Q_ASSERT(input); + if (node->operation()->kind() == Meta::Region + && node->operation()->controlInputCount() > 1 + && isControlFlowSplit(input)) { + // critical edge! + input = splitEdge(m_irFunction, node, inputIndex); + m_live.markReachable(input); + m_live.markReachable(input->controlInput(0)); + } + if (!isBlockTerminator(input)) { + auto g = m_irFunction->graph(); + Node *jump = g->createNode(g->opBuilder()->get<Meta::Jump>(), &input, 1); + node->replaceInput(inputIndex, jump); + m_live.markReachable(jump); + qCDebug(lcSched) << "inserting jump node" << jump->id() + << "between node" << node->id() + << "and node" << input->id(); + input = jump; + } + todo.enqueue(input); + } + }; + + // create the CFG by scheduling control dependencies that start/end blocks: + todo.enqueue(m_irFunction->graph()->endNode()); + while (Node *node = todo.dequeueNextNodeForVisiting()) { + Q_ASSERT(isBlockTerminator(node)); + + if (schedulerData(node)->minimumBlock) + continue; + + MIBlock *b = m_miFunction->addBlock(); + + qCDebug(lcSched) << "scheduling node" << node->id() << "as terminator for new block" + << b->index(); + b->instructions().push_front(createMIInstruction(node)); + placeFixed(node, b, Schedule); + roots.push_back(node); + + if (Node *framestate = node->frameStateInput()) { + placeFixed(framestate, b, DontSchedule); + qCDebug(lcSched) << ".. also scheduling framestate dependency node" << node->id() + << "in block" << b->index(); + } + + if (node->opcode() == Meta::End) { + enqueueControlInputs(node); + continue; + } + + while (true) { + Node *controlDependency = node->controlInput(0); + if (!controlDependency) + break; + if (todo.isVisited(controlDependency)) + break; + if (schedulerData(controlDependency)->isFixed) + break; + + if (controlDependency->opcode() == Meta::Start) { + qCDebug(lcSched) << "placing start node" << controlDependency->id() + << "in block" << b->index(); + handleStartNode(controlDependency, b); + placeFixed(controlDependency, b, Schedule); + roots.push_back(controlDependency); + break; // we're done with this block + } + if (isBlockTerminator(controlDependency)) { + qCDebug(lcSched) << "found terminator node" << controlDependency->id() + << "for another block, so finish block" << b->index(); + Node *merge = m_irFunction->graph()->createNode( + m_irFunction->graph()->opBuilder()->getRegion(1), &controlDependency, 1); + node->replaceInput(node->operation()->indexOfFirstControl(), merge); + addBlockStart(roots, merge, b); + placeFixed(merge, b, Schedule); + m_live.markReachable(merge); + todo.enqueue(controlDependency); + break; // we're done with this block + } + if (canStartBlock(controlDependency) + || schedulerData(controlDependency->controlInput())->isFixed) { + qCDebug(lcSched) << "found block start node" << controlDependency->id() + << "for this block, so finish block" << b->index(); + addBlockStart(roots, controlDependency, b); + placeFixed(controlDependency, b, Schedule); + roots.push_back(controlDependency); + enqueueControlInputs(controlDependency); + break; // we're done with this block + } + qCDebug(lcSched) << "skipping node" << controlDependency->id(); + node = controlDependency; + } + } + + // link the edges of the MIBlocks, and add basic-block arguments: + for (MIBlock *toBlock : m_miFunction->blocks()) { + Q_ASSERT(!toBlock->instructions().empty()); + MIInstr &instr = toBlock->instructions().front(); + Node *toNode = instr.irNode(); + const auto opcode = toNode->operation()->kind(); + if (opcode == Meta::Region) { + unsigned inputNr = 0; + for (Node *input : toNode->inputs()) { + MIBlock *fromBlock = schedulerData(input)->minimumBlock; + fromBlock->addOutEdge(toBlock); + toBlock->addInEdge(fromBlock); + MIInstr &fromTerminator = fromBlock->instructions().back(); + if (fromTerminator.irNode()->opcode() == Meta::Jump || + fromTerminator.irNode()->opcode() == Meta::UnwindDispatch) { + unsigned arg = 0; + for (const MIOperand &bbArg : toBlock->arguments()) { + fromTerminator.setOperand(arg++, + createMIOperand(bbArg.irNode()->input(inputNr))); + } + } + ++inputNr; + } + } else if (opcode == Meta::End) { + for (Node *input : toNode->inputs()) { + MIBlock *fromBlock = schedulerData(input)->minimumBlock; + fromBlock->addOutEdge(toBlock); + toBlock->addInEdge(fromBlock); + } + } else if (Node *fromNode = toNode->controlInput()) { + MIBlock *fromBlock = schedulerData(fromNode)->minimumBlock; + fromBlock->addOutEdge(toBlock); + toBlock->addInEdge(fromBlock); + } + } + + m_irFunction->dump(QStringLiteral("graph after building CFG")); + + auto startBlock = schedulerData(m_irFunction->graph()->startNode())->minimumBlock; + m_miFunction->setStartBlock(startBlock); + + if (lcSched().isDebugEnabled()) + m_miFunction->dump(QStringLiteral("control flow graph before renumbering")); + m_miFunction->verifyCFG(); + + return roots; +} + +// See Chapter 6.3.3 of https://scholarship.rice.edu/bitstream/handle/1911/96451/TR95-252.pdf for +// a description of the algorithm. +void NodeScheduler::scheduleEarly(const std::vector<Node *> &roots) +{ + // scheduling one node might have the effect of queueing its dependencies + NodeWorkList todo(m_irFunction->graph()); + for (Node *root : roots) { + todo.enqueue(root); + while (Node *node = todo.dequeueNextNodeForVisiting()) + scheduleEarly(node, todo); + } +} + +void NodeScheduler::scheduleEarly(Node *node, NodeWorkList &todo) +{ + qCDebug(lcSched) << "Scheduling node" << node->id() << "early..."; + + SchedulerData *sd = schedulerData(node); + + if (sd->isFixed) { + // Fixed nodes already know their schedule early position. + qCDebug(lcSched) << ".. Fixed node" << node->id() << "is on minimum block" + << sd->minimumBlock->index() + << "which has dominator depth" + << m_dominatorDepthForBlock[sd->minimumBlock->index()]; + } + + for (Node *use : node->uses()) { + if (isLive(use)) + propagateMinimumPosition(sd->minimumBlock, use, todo); + else + qCDebug(lcSched) << ".. Skipping node" << use->id() << "as it's not live"; + } +} + +void NodeScheduler::propagateMinimumPosition(MIBlock *newMinimumPosition, Node *toNode, + NodeWorkList &todo) +{ + Q_ASSERT(newMinimumPosition); + + SchedulerData *sd = schedulerData(toNode); + if (sd->isFixed) // nothing to do + return; + + MIBlock::Index minimumBlockIndex = sd->minimumBlock + ? sd->minimumBlock->index() + : MIFunction::StartBlockIndex; + Q_ASSERT(m_domTree->insideSameDominatorChain(newMinimumPosition->index(), minimumBlockIndex)); + if (sd->minimumBlock == nullptr + || m_dominatorDepthForBlock[newMinimumPosition->index()] + > m_dominatorDepthForBlock[minimumBlockIndex]) { + // ok, some input for toNode is scheduled *after* our current minimum depth, so we need + // to adjust out minimal position. (This might involve rescheduling toNode's uses.) + place(toNode, newMinimumPosition); + todo.reEnqueue(toNode); + qCDebug(lcSched) << ".. Propagating minimum block" << sd->minimumBlock->index() + << "which has dominator depth" + << m_dominatorDepthForBlock[newMinimumPosition->index()] + << "to use node" << toNode->id(); + } else { + qCDebug(lcSched) << ".. Minimum position" << newMinimumPosition->index() + << "is not better than" << minimumBlockIndex + << "for node" << toNode->id(); + } +} + +// See Chapter 6.3.4 of https://scholarship.rice.edu/bitstream/handle/1911/96451/TR95-252.pdf for +// a description of the algorithm. +// +// There is one extra detail not described in the thesis mentioned above: loop hoisting. Before we +// place a node in the latest block that dominates all uses, we check if we accidentally sink it +// *into* a loop (meaning the latest block is inside a loop, where it is not if the earliest +// possible block would be chosen). If we detect that a nodes is going to sink into a loop, we walk +// the dominator path from the latest block up to the earliest block, and pick the first block that +// is in the same loop (if any) as the earlieast block. +// +// As noted in the thesis, this strategy might enlongen life times, which could be harmful for +// values that are simple to re-materialized or re-calculate. +void NodeScheduler::scheduleLate(const std::vector<Node *> &roots) +{ + NodeWorkList todo(m_irFunction->graph()); + for (Node *root : roots) + todo.enqueue(root); + + while (Node *node = todo.dequeueNextNodeForVisiting()) + scheduleNodeLate(node, todo); +} + +void NodeScheduler::scheduleNodeLate(Node *node, NodeWorkList &todo) +{ + if (!needsScheduling(node)) + return; + qCDebug(lcSched) << "Scheduling node" << node->id() << "late..."; + + auto sd = schedulerData(node); + if (sd->unscheduledUses == SchedulerData::NotYetCalculated) { + sd->unscheduledUses = 0; + for (Node *use : node->uses()) { + if (!isLive(use)) + continue; + if (!needsScheduling(use)) + continue; + if (schedulerData(use)->isFixed) + continue; + todo.enqueue(use); + ++sd->unscheduledUses; + } + } + + if (sd->isFixed) { + qCDebug(lcSched) << ".. it's fixed"; + enqueueInputs(node, todo); + return; + } + + if (sd->unscheduledUses) { + qCDebug(lcSched).noquote() << ".. not all uses are fixed, postpone it."<< todo.status(node); + return; + } + + MIBlock *&minBlock = sd->minimumBlock; + if (minBlock == nullptr) + minBlock = m_miFunction->block(MIFunction::StartBlockIndex); + MIBlock *commonUseDominator = commonDominatorOfUses(node); + qCDebug(lcSched) << ".. common use dominator: block" << commonUseDominator->index(); + + // the minBlock has to dominate the uses, *and* the common dominator of the uses. + Q_ASSERT(minBlock->index() == commonUseDominator->index() || + m_domTree->dominates(minBlock->index(), commonUseDominator->index())); + + // we now found the deepest block, so use it as the target block: + MIBlock *targetBlock = commonUseDominator; + + if (node->opcode() == Meta::FrameState) { + // never hoist framestates: they're used (among other things) to keep their inputs alive, so + // hoisting them out would end the life-time of those inputs prematurely + } else { + // but we want to prevent blocks sinking into loops unnecessary + MIBlock *hoistBlock = getHoistBlock(targetBlock); + while (hoistBlock + && m_dominatorDepthForBlock[hoistBlock->index()] + >= m_dominatorDepthForBlock[minBlock->index()]) { + qCDebug(lcSched) << ".. hoisting node" << node->id() << "from block" + << targetBlock->index() << "to block" << hoistBlock->index(); + // ok, so there a) is a hoist block and b) it's deeper than the minimum block, + // so lift it up one level ... + targetBlock = hoistBlock; + // ... and see if we can lift it one more level + hoistBlock = getHoistBlock(targetBlock); + } + } + + qCDebug(lcSched) << ".. fixating it in block" << targetBlock->index() + << "where the minimum block was" << minBlock->index(); + + placeFixed(node, targetBlock, DontSchedule); + enqueueInputs(node, todo); +} + +void NodeScheduler::enqueueInputs(Node *node, NodeWorkList &todo) +{ + for (Node *input : node->inputs()) { + if (!input) + continue; + if (!needsScheduling(input)) + continue; + if (!isLive(input)) + continue; + auto sd = schedulerData(input); + if (sd->isFixed) + continue; + qCDebug(lcSched).noquote() << "... enqueueing input node" << input->id() + << todo.status(input); + if (sd->unscheduledUses != SchedulerData::NotYetCalculated) { + if (sd->unscheduledUses > 0) + --sd->unscheduledUses; + if (sd->unscheduledUses == 0) + todo.reEnqueue(input); + } else { + todo.reEnqueue(input); + } + } +} + +Node *NodeScheduler::firstNotFixedUse(Node *node) +{ + for (Node *use : node->uses()) { + if (!isLive(use)) + continue; + if (!schedulerData(use)->isFixed) + return use; + } + return nullptr; +} + +MIBlock *NodeScheduler::commonDominatorOfUses(Node *node) +{ + MIBlock *commonDominator = nullptr; + for (auto useIt = node->uses().begin(), useEIt = node->uses().end(); useIt != useEIt; ++useIt) { + Node *use = *useIt; + if (!isLive(use)) + continue; + // region nodes use other nodes through their control dependency. But those nodes should + // already have been placed as block terminators before. + Q_ASSERT(use->opcode() != Meta::Region); + if (use->opcode() == Meta::Phi || use->opcode() == Meta::EffectPhi) { + // find the predecessor block defining this input + Node *region = use->controlInput(0); + Node *input = region->controlInput(useIt.inputIndex()); + use = input; + } + auto minBlock = schedulerData(use)->minimumBlock; + if (commonDominator == nullptr) + commonDominator = minBlock; + else + commonDominator = getCommonDominator(commonDominator, minBlock); + } + return commonDominator; +} + +void NodeScheduler::scheduleNodesInBlock() +{ + auto startBlock = m_miFunction->block(MIFunction::StartBlockIndex); + for (Node *n : m_live.reachable()) { + auto sd = schedulerData(n); + if (!sd->minimumBlock) + sd->minimumBlock = startBlock; + } + + std::vector<std::vector<SchedulerData *>> nodesForBlock; + nodesForBlock.resize(m_miFunction->blockCount()); + + for (auto sd : m_schedulerData) { + if (sd == nullptr) + continue; + if (!isLive(sd->node)) + continue; + sd->unscheduledUses = 0; + for (Node *use : sd->node->uses()) { + if (!needsScheduling(use)) + continue; + if (schedulerData(use)->isScheduledInBlock) + continue; + if (schedulerData(use)->minimumBlock == sd->minimumBlock) + ++sd->unscheduledUses; + } + if (sd->unscheduledUses == 0) + nodesForBlock[sd->minimumBlock->index()].push_back(sd); + } + + NodeWorkList todo(m_irFunction->graph()); + for (MIBlock *b : m_miFunction->blocks()) { + qCDebug(lcSched) << "Scheduling inside block" << b->index(); + MIInstr *insertionPoint = &b->instructions().back(); + todo.enqueue(insertionPoint->irNode()); + scheduleNodesInBlock(insertionPoint, b, todo); + Q_ASSERT(todo.isEmpty()); + for (auto sd : nodesForBlock[b->index()]) { + if (!sd->isScheduledInBlock) + todo.enqueue(sd->node); + } + scheduleNodesInBlock(insertionPoint, b, todo); + Q_ASSERT(todo.isEmpty()); + todo.reset(); + } +} + +void NodeScheduler::scheduleNodesInBlock(MIInstr *&insertionPoint, MIBlock *b, NodeWorkList &todo) +{ + while (Node *n = todo.dequeueNextNodeForVisiting()) + scheduleNodeInBlock(n, insertionPoint, b, todo); +} + +void NodeScheduler::scheduleNodeInBlock(Node *node, MIInstr *&insertionPoint, MIBlock *b, + NodeWorkList &todo) +{ + Q_ASSERT(!node->isDead()); + + if (!isLive(node)) + return; + + if (!needsScheduling(node)) + return; + + auto nodeData = schedulerData(node); + if (nodeData->minimumBlock != b) + return; + + const bool wasAlreadyScheduled = nodeData->isScheduledInBlock; + if (!wasAlreadyScheduled) { + if (nodeData->unscheduledUses) + return; + + scheduleNodeNow(node, insertionPoint); + } + + if (Node *framestate = node->frameStateInput()) + scheduleNodeInBlock(framestate, insertionPoint, b, todo); + + for (Node *input : node->inputs()) { + if (!input) + continue; + if (!needsScheduling(input)) + continue; + if (!isLive(input)) + continue; + auto inputInfo = schedulerData(input); + if (inputInfo->isScheduledInBlock) + continue; + Q_ASSERT(inputInfo->minimumBlock != nullptr); + if (inputInfo->minimumBlock != b) + continue; + Q_ASSERT(!input->isDead()); + Q_ASSERT(inputInfo->unscheduledUses != SchedulerData::NotYetCalculated); + if (!wasAlreadyScheduled && inputInfo->unscheduledUses > 0) + --inputInfo->unscheduledUses; + if (inputInfo->unscheduledUses == 0) + todo.enqueue(input); + } +} + +void NodeScheduler::scheduleNodeNow(Node *node, MIInstr *&insertionPoint) +{ + qCDebug(lcSched) << ".. scheduling node" << node->id() + << "in block" << insertionPoint->parent()->index() + << "before node" << insertionPoint->irNode()->id(); + + MIInstr *newInstr = createMIInstruction(node); + newInstr->insertBefore(insertionPoint); + insertionPoint = newInstr; +} + +void NodeScheduler::place(Node *node, MIBlock *b) +{ + Q_ASSERT(!node->isDead()); + + if (b == nullptr) + return; + + schedulerData(node)->minimumBlock = b; +} + +void NodeScheduler::placeFixed(Node *node, MIBlock *b, ScheduleOrNot markScheduled) +{ + place(node, b); + auto sd = schedulerData(node); + Q_ASSERT(!sd->isFixed); + sd->isFixed = true; + sd->isScheduledInBlock = markScheduled == Schedule; +} + +unsigned NodeScheduler::vregForNode(Node *node) +{ + unsigned &vreg = m_vregs[unsigned(node->id())]; + if (vreg == std::numeric_limits<unsigned>::max()) + vreg = m_nextVReg++; + return vreg; +} + +void NodeScheduler::addBlockStart(std::vector<Node *> &roots, Node *startNode, MIBlock *block) +{ + block->instructions().insert(block->instructions().begin(), createMIInstruction(startNode)); + if (startNode->opcode() == Meta::Region) { + for (Node *use : startNode->uses()) { + if (use->opcode() == Meta::Phi && isLive(use)) { + block->addArgument(MIOperand::createVirtualRegister(use, vregForNode(use))); + placeFixed(use, block, Schedule); + roots.push_back(use); + } else if (use->opcode() == Meta::EffectPhi && isLive(use)) { + placeFixed(use, block, Schedule); + roots.push_back(use); + } + } + } +} + +void NodeScheduler::handleStartNode(Node *startNode, MIBlock *startBlock) +{ + startBlock->instructions().push_front(createMIInstruction(startNode)); + + QVarLengthArray<Node *, 32> args; + for (Node *use : startNode->uses()) { + switch (use->opcode()) { + case Meta::Engine: Q_FALLTHROUGH(); + case Meta::CppFrame: + case Meta::Function: + placeFixed(use, startBlock, Schedule); + break; + case Meta::Parameter: { + auto param = ParameterPayload::get(*use->operation()); + int idx = int(param->parameterIndex()); + if (args.size() <= idx) + args.resize(idx + 1); + args[int(idx)] = use; + placeFixed(use, startBlock, Schedule); + } + break; + default: + break; + } + } + + for (unsigned i = 0, ei = unsigned(args.size()); i != ei; ++i) { + if (Node *arg = args.at(int(i))) + startBlock->addArgument(MIOperand::createJSStackSlot(arg, i)); + } +} + +static Node *firstControlOutput(Node *n) +{ + for (auto it = n->uses().begin(), eit = n->uses().end(); it != eit; ++it) { + if (it.isUsedAsControl()) + return *it; + } + return nullptr; +} + +MIInstr *NodeScheduler::createMIInstruction(Node *node) +{ + const auto opcode = node->operation()->kind(); + + unsigned nArgs = 0; + switch (opcode) { + case Meta::UnwindDispatch: Q_FALLTHROUGH(); + case Meta::Jump: { + Node *target = firstControlOutput(node); + if (target->opcode() == Meta::Region) { + for (Node *n : target->uses()) { + if (n->opcode() == Meta::Phi && isLive(n)) + ++nArgs; + } + } + } + break; + case Meta::Branch: + nArgs = 1; + break; + case Meta::Return: + nArgs = 1; + break; + default: + nArgs = node->operation()->valueInputCount(); + break; + } + + MIInstr *instr = MIInstr::create(m_irFunction->pool(), node, nArgs); + for (unsigned i = 0, ei = node->operation()->valueInputCount(); i != ei; ++i) + instr->setOperand(i, createMIOperand(node->input(i))); + if (node->opcode() != Meta::Start && node->operation()->valueOutputCount() > 0) + instr->setDestination(createMIOperand(node)); + + schedulerData(node)->isScheduledInBlock = true; + return instr; +} + +MIOperand NodeScheduler::createMIOperand(Node *node) +{ + if (node->operation()->isConstant()) + return MIOperand::createConstant(node); + + auto opcode = node->operation()->kind(); + switch (opcode) { + case Meta::Parameter: + return MIOperand::createJSStackSlot( + node, unsigned(ParameterPayload::get(*node->operation())->parameterIndex())); + case Meta::Engine: + return MIOperand::createEngineRegister(node); + case Meta::CppFrame: + return MIOperand::createCppFrameRegister(node); + case Meta::Function: + return MIOperand::createFunction(node); + default: + if ((node->opcode() == Meta::Call + && CallPayload::get(*node->operation())->callee() == Meta::JSThisToObject) + || node->opcode() == Meta::StoreThis) { + return MIOperand::createJSStackSlot(node, CallData::This); + } else { + return MIOperand::createVirtualRegister(node, vregForNode(node)); + } + } +} + +void NodeScheduler::showNodesByBlock(const QString &description) const +{ + if (!lcSched().isDebugEnabled()) + return; + + qCDebug(lcSched) << description; + + for (MIBlock *b : m_miFunction->blocks()) { + QString s; + for (const SchedulerData *sd : m_schedulerData) { + if (!sd) + continue; + if (!isLive(sd->node)) + continue; + if (sd->minimumBlock == b) { + if (!s.isEmpty()) + s += QStringLiteral(", "); + s += QStringLiteral("%1 (%2)").arg(QString::number(sd->node->id()), + sd->node->operation()->debugString()); + } + } + if (s.isEmpty()) + s = QStringLiteral("<<none>>"); + qCDebug(lcSched, "Nodes in block %u: %s", b->index(), s.toUtf8().constData()); + } +} + +void NodeScheduler::dumpDotCFG() const +{ + QString out; + out += QLatin1Char('\n'); + out += QStringLiteral("digraph{root=\"L%1\" label=\"Control Flow Graph\";" + "node[shape=circle];edge[dir=forward fontsize=10]\n") + .arg(MIFunction::StartBlockIndex); + for (MIBlock *src : m_miFunction->blocks()) { + for (MIBlock *dst : src->outEdges()) { + out += QStringLiteral("L%1->L%2\n").arg(QString::number(src->index()), + QString::number(dst->index())); + } + } + out += QStringLiteral("}\n"); + qCDebug(lcDotCFG).nospace().noquote() << out; +} + +} // IR namespace +} // QV4 namespace +QT_END_NAMESPACE |