diff options
Diffstat (limited to 'src/qml/jit/qv4schedulers.cpp')
| -rw-r--r-- | src/qml/jit/qv4schedulers.cpp | 912 |
1 files changed, 0 insertions, 912 deletions
diff --git a/src/qml/jit/qv4schedulers.cpp b/src/qml/jit/qv4schedulers.cpp deleted file mode 100644 index 0dffefa951..0000000000 --- a/src/qml/jit/qv4schedulers.cpp +++ /dev/null @@ -1,912 +0,0 @@ -/**************************************************************************** -** -** Copyright (C) 2018 The Qt Company Ltd. -** Contact: https://www.qt.io/licensing/ -** -** This file is part of the QtQml module of the Qt Toolkit. -** -** $QT_BEGIN_LICENSE:LGPL$ -** Commercial License Usage -** Licensees holding valid commercial Qt licenses may use this file in -** accordance with the commercial license agreement provided with the -** Software or, alternatively, in accordance with the terms contained in -** a written agreement between you and The Qt Company. For licensing terms -** and conditions see https://www.qt.io/terms-conditions. For further -** information use the contact form at https://www.qt.io/contact-us. -** -** GNU Lesser General Public License Usage -** Alternatively, this file may be used under the terms of the GNU Lesser -** General Public License version 3 as published by the Free Software -** Foundation and appearing in the file LICENSE.LGPL3 included in the -** packaging of this file. Please review the following information to -** ensure the GNU Lesser General Public License version 3 requirements -** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. -** -** GNU General Public License Usage -** Alternatively, this file may be used under the terms of the GNU -** General Public License version 2.0 or (at your option) the GNU General -** Public license version 3 or any later version approved by the KDE Free -** Qt Foundation. The licenses are as published by the Free Software -** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 -** included in the packaging of this file. Please review the following -** information to ensure the GNU General Public License requirements will -** be met: https://www.gnu.org/licenses/gpl-2.0.html and -** https://www.gnu.org/licenses/gpl-3.0.html. -** -** $QT_END_LICENSE$ -** -****************************************************************************/ - -#include <QtCore/qloggingcategory.h> - -#include "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 |