diff options
Diffstat (limited to 'Source/JavaScriptCore/dfg/DFGCFGSimplificationPhase.cpp')
| -rw-r--r-- | Source/JavaScriptCore/dfg/DFGCFGSimplificationPhase.cpp | 326 |
1 files changed, 168 insertions, 158 deletions
diff --git a/Source/JavaScriptCore/dfg/DFGCFGSimplificationPhase.cpp b/Source/JavaScriptCore/dfg/DFGCFGSimplificationPhase.cpp index c022fce2b..5bdd9f746 100644 --- a/Source/JavaScriptCore/dfg/DFGCFGSimplificationPhase.cpp +++ b/Source/JavaScriptCore/dfg/DFGCFGSimplificationPhase.cpp @@ -1,5 +1,5 @@ /* - * Copyright (C) 2012, 2013 Apple Inc. All rights reserved. + * Copyright (C) 2012-2015 Apple Inc. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -28,13 +28,12 @@ #if ENABLE(DFG_JIT) -#include "DFGAbstractState.h" #include "DFGBasicBlockInlines.h" #include "DFGGraph.h" #include "DFGInsertionSet.h" #include "DFGPhase.h" #include "DFGValidate.h" -#include "Operations.h" +#include "JSCInlines.h" namespace JSC { namespace DFG { @@ -47,6 +46,9 @@ public: bool run() { + // FIXME: We should make this work in SSA. https://bugs.webkit.org/show_bug.cgi?id=148260 + DFG_ASSERT(m_graph, nullptr, m_graph.m_form != SSA); + const bool extremeLogging = false; bool outerChanged = false; @@ -54,39 +56,23 @@ public: do { innerChanged = false; - for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) { - BasicBlock* block = m_graph.m_blocks[blockIndex].get(); + for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) { + BasicBlock* block = m_graph.block(blockIndex); if (!block) continue; ASSERT(block->isReachable); - switch (block->last()->op()) { + switch (block->terminal()->op()) { case Jump: { // Successor with one predecessor -> merge. - if (m_graph.m_blocks[m_graph.successor(block, 0)]->m_predecessors.size() == 1) { - ASSERT(m_graph.m_blocks[m_graph.successor(block, 0)]->m_predecessors[0] - == blockIndex); -#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) - dataLogF("CFGSimplify: Jump merge on Block #%u to Block #%u.\n", - blockIndex, m_graph.successor(block, 0)); -#endif + if (block->successor(0)->predecessors.size() == 1) { + ASSERT(block->successor(0)->predecessors[0] == block); if (extremeLogging) m_graph.dump(); m_graph.dethread(); - mergeBlocks(blockIndex, m_graph.successor(block, 0), NoBlock); + mergeBlocks(block, block->successor(0), noBlocks()); innerChanged = outerChanged = true; break; - } else { -#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) - dataLogF("Not jump merging on Block #%u to Block #%u because predecessors = ", - blockIndex, m_graph.successor(block, 0)); - for (unsigned i = 0; i < m_graph.m_blocks[m_graph.successor(block, 0)]->m_predecessors.size(); ++i) { - if (i) - dataLogF(", "); - dataLogF("#%u", m_graph.m_blocks[m_graph.successor(block, 0)]->m_predecessors[i]); - } - dataLogF(".\n"); -#endif } // FIXME: Block only has a jump -> remove. This is tricky though because of @@ -96,6 +82,8 @@ public: // suboptimal, because if my successor has multiple predecessors then we'll // be keeping alive things on other predecessor edges unnecessarily. // What we really need is the notion of end-of-block ghosties! + // FIXME: Allow putting phantoms after terminals. + // https://bugs.webkit.org/show_bug.cgi?id=126778 break; } @@ -103,93 +91,117 @@ public: // Branch on constant -> jettison the not-taken block and merge. if (isKnownDirection(block->cfaBranchDirection)) { bool condition = branchCondition(block->cfaBranchDirection); - BasicBlock* targetBlock = m_graph.m_blocks[ - m_graph.successorForCondition(block, condition)].get(); - if (targetBlock->m_predecessors.size() == 1) { -#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) - dataLogF("CFGSimplify: Known condition (%s) branch merge on Block #%u to Block #%u, jettisoning Block #%u.\n", - condition ? "true" : "false", - blockIndex, m_graph.successorForCondition(block, condition), - m_graph.successorForCondition(block, !condition)); -#endif + BasicBlock* targetBlock = block->successorForCondition(condition); + BasicBlock* jettisonedBlock = block->successorForCondition(!condition); + if (targetBlock->predecessors.size() == 1) { if (extremeLogging) m_graph.dump(); m_graph.dethread(); - mergeBlocks( - blockIndex, - m_graph.successorForCondition(block, condition), - m_graph.successorForCondition(block, !condition)); + mergeBlocks(block, targetBlock, oneBlock(jettisonedBlock)); } else { -#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) - dataLogF("CFGSimplify: Known condition (%s) branch->jump conversion on Block #%u to Block #%u, jettisoning Block #%u.\n", - condition ? "true" : "false", - blockIndex, m_graph.successorForCondition(block, condition), - m_graph.successorForCondition(block, !condition)); -#endif if (extremeLogging) m_graph.dump(); m_graph.dethread(); - BlockIndex takenBlockIndex = m_graph.successorForCondition(block, condition); - BlockIndex notTakenBlockIndex = m_graph.successorForCondition(block, !condition); - - ASSERT(block->last()->isTerminal()); - CodeOrigin boundaryCodeOrigin = block->last()->codeOrigin; - block->last()->convertToPhantom(); - ASSERT(block->last()->refCount() == 1); - - jettisonBlock(blockIndex, notTakenBlockIndex, boundaryCodeOrigin); + + Node* terminal = block->terminal(); + ASSERT(terminal->isTerminal()); + NodeOrigin boundaryNodeOrigin = terminal->origin; + + jettisonBlock(block, jettisonedBlock, boundaryNodeOrigin); + + block->replaceTerminal( + m_graph, SpecNone, Jump, boundaryNodeOrigin, + OpInfo(targetBlock)); + + ASSERT(block->terminal()); - block->appendNode( - m_graph, SpecNone, Jump, boundaryCodeOrigin, - OpInfo(takenBlockIndex)); } innerChanged = outerChanged = true; break; } - if (m_graph.successor(block, 0) == m_graph.successor(block, 1)) { - BlockIndex targetBlockIndex = m_graph.successor(block, 0); - BasicBlock* targetBlock = m_graph.m_blocks[targetBlockIndex].get(); - ASSERT(targetBlock); - ASSERT(targetBlock->isReachable); - if (targetBlock->m_predecessors.size() == 1) { -#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) - dataLogF("CFGSimplify: Branch to same successor merge on Block #%u to Block #%u.\n", - blockIndex, targetBlockIndex); -#endif - m_graph.dethread(); - mergeBlocks(blockIndex, targetBlockIndex, NoBlock); - } else { -#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) - dataLogF("CFGSimplify: Branch->jump conversion to same successor on Block #%u to Block #%u.\n", - blockIndex, targetBlockIndex); -#endif - Node* branch = block->last(); - ASSERT(branch->isTerminal()); - ASSERT(branch->op() == Branch); - branch->convertToPhantom(); - ASSERT(branch->refCount() == 1); - - block->appendNode( - m_graph, SpecNone, Jump, branch->codeOrigin, - OpInfo(targetBlockIndex)); - } + if (block->successor(0) == block->successor(1)) { + convertToJump(block, block->successor(0)); innerChanged = outerChanged = true; break; } -#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) - dataLogF("Not branch simplifying on Block #%u because the successors differ and the condition is not known.\n", - blockIndex); -#endif - // Branch to same destination -> jump. // FIXME: this will currently not be hit because of the lack of jump-only // block simplification. break; } - + + case Switch: { + SwitchData* data = block->terminal()->switchData(); + + // Prune out cases that end up jumping to default. + for (unsigned i = 0; i < data->cases.size(); ++i) { + if (data->cases[i].target.block == data->fallThrough.block) { + data->fallThrough.count += data->cases[i].target.count; + data->cases[i--] = data->cases.last(); + data->cases.removeLast(); + } + } + + // If there are no cases other than default then this turns + // into a jump. + if (data->cases.isEmpty()) { + convertToJump(block, data->fallThrough.block); + innerChanged = outerChanged = true; + break; + } + + // Switch on constant -> jettison all other targets and merge. + Node* terminal = block->terminal(); + if (terminal->child1()->hasConstant()) { + FrozenValue* value = terminal->child1()->constant(); + TriState found = FalseTriState; + BasicBlock* targetBlock = 0; + for (unsigned i = data->cases.size(); found == FalseTriState && i--;) { + found = data->cases[i].value.strictEqual(value); + if (found == TrueTriState) + targetBlock = data->cases[i].target.block; + } + + if (found == MixedTriState) + break; + if (found == FalseTriState) + targetBlock = data->fallThrough.block; + ASSERT(targetBlock); + + Vector<BasicBlock*, 1> jettisonedBlocks; + for (BasicBlock* successor : terminal->successors()) { + if (successor != targetBlock) + jettisonedBlocks.append(successor); + } + + if (targetBlock->predecessors.size() == 1) { + if (extremeLogging) + m_graph.dump(); + m_graph.dethread(); + + mergeBlocks(block, targetBlock, jettisonedBlocks); + } else { + if (extremeLogging) + m_graph.dump(); + m_graph.dethread(); + + NodeOrigin boundaryNodeOrigin = terminal->origin; + + for (unsigned i = jettisonedBlocks.size(); i--;) + jettisonBlock(block, jettisonedBlocks[i], boundaryNodeOrigin); + + block->replaceTerminal( + m_graph, SpecNone, Jump, boundaryNodeOrigin, OpInfo(targetBlock)); + } + innerChanged = outerChanged = true; + break; + } + break; + } + default: break; } @@ -226,85 +238,85 @@ public: // successors' Phi functions to remove any references from them into the // removed block. + m_graph.invalidateCFG(); m_graph.resetReachability(); - - for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) { - BasicBlock* block = m_graph.m_blocks[blockIndex].get(); - if (!block) - continue; - if (block->isReachable) - continue; - - killUnreachable(blockIndex); - } + m_graph.killUnreachableBlocks(); } if (Options::validateGraphAtEachPhase()) - validate(m_graph); + validate(); } while (innerChanged); return outerChanged; } private: - void killUnreachable(BlockIndex blockIndex) + void convertToJump(BasicBlock* block, BasicBlock* targetBlock) { - BasicBlock* block = m_graph.m_blocks[blockIndex].get(); - - ASSERT(block); - ASSERT(!block->isReachable); - - for (unsigned phiIndex = block->phis.size(); phiIndex--;) - m_graph.m_allocator.free(block->phis[phiIndex]); - for (unsigned nodeIndex = block->size(); nodeIndex--;) - m_graph.m_allocator.free(block->at(nodeIndex)); - - m_graph.m_blocks[blockIndex].clear(); + ASSERT(targetBlock); + ASSERT(targetBlock->isReachable); + if (targetBlock->predecessors.size() == 1) { + m_graph.dethread(); + mergeBlocks(block, targetBlock, noBlocks()); + } else { + Node* branch = block->terminal(); + ASSERT(branch->op() == Branch || branch->op() == Switch); + + block->replaceTerminal( + m_graph, SpecNone, Jump, branch->origin, OpInfo(targetBlock)); + } } - void keepOperandAlive(BasicBlock* block, BasicBlock* jettisonedBlock, CodeOrigin codeOrigin, int operand) + void keepOperandAlive(BasicBlock* block, BasicBlock* jettisonedBlock, NodeOrigin nodeOrigin, VirtualRegister operand) { Node* livenessNode = jettisonedBlock->variablesAtHead.operand(operand); if (!livenessNode) return; - if (livenessNode->variableAccessData()->isCaptured()) - return; + NodeType nodeType; + if (livenessNode->flags() & NodeIsFlushed) + nodeType = Flush; + else { + // This seems like it shouldn't be necessary because we could just rematerialize + // PhantomLocals or something similar using bytecode liveness. However, in ThreadedCPS, it's + // worth the sanity to maintain this eagerly. See + // https://bugs.webkit.org/show_bug.cgi?id=144086 + nodeType = PhantomLocal; + } block->appendNode( - m_graph, SpecNone, PhantomLocal, codeOrigin, + m_graph, SpecNone, nodeType, nodeOrigin, OpInfo(livenessNode->variableAccessData())); } - void jettisonBlock(BlockIndex blockIndex, BlockIndex jettisonedBlockIndex, CodeOrigin boundaryCodeOrigin) + void jettisonBlock(BasicBlock* block, BasicBlock* jettisonedBlock, NodeOrigin boundaryNodeOrigin) { - BasicBlock* block = m_graph.m_blocks[blockIndex].get(); - BasicBlock* jettisonedBlock = m_graph.m_blocks[jettisonedBlockIndex].get(); - for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfArguments(); ++i) - keepOperandAlive(block, jettisonedBlock, boundaryCodeOrigin, argumentToOperand(i)); + keepOperandAlive(block, jettisonedBlock, boundaryNodeOrigin, virtualRegisterForArgument(i)); for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfLocals(); ++i) - keepOperandAlive(block, jettisonedBlock, boundaryCodeOrigin, i); + keepOperandAlive(block, jettisonedBlock, boundaryNodeOrigin, virtualRegisterForLocal(i)); - fixJettisonedPredecessors(blockIndex, jettisonedBlockIndex); + fixJettisonedPredecessors(block, jettisonedBlock); } - void fixJettisonedPredecessors(BlockIndex blockIndex, BlockIndex jettisonedBlockIndex) + void fixJettisonedPredecessors(BasicBlock* block, BasicBlock* jettisonedBlock) { -#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) - dataLogF("Fixing predecessors and phis due to jettison of Block #%u from Block #%u.\n", - jettisonedBlockIndex, blockIndex); -#endif - BasicBlock* jettisonedBlock = m_graph.m_blocks[jettisonedBlockIndex].get(); - for (unsigned i = 0; i < jettisonedBlock->m_predecessors.size(); ++i) { - if (jettisonedBlock->m_predecessors[i] != blockIndex) - continue; - jettisonedBlock->m_predecessors[i] = jettisonedBlock->m_predecessors.last(); - jettisonedBlock->m_predecessors.removeLast(); - break; - } + jettisonedBlock->removePredecessor(block); + } + + Vector<BasicBlock*, 1> noBlocks() + { + return Vector<BasicBlock*, 1>(); + } + + Vector<BasicBlock*, 1> oneBlock(BasicBlock* block) + { + Vector<BasicBlock*, 1> result; + result.append(block); + return result; } void mergeBlocks( - BlockIndex firstBlockIndex, BlockIndex secondBlockIndex, BlockIndex jettisonedBlockIndex) + BasicBlock* firstBlock, BasicBlock* secondBlock, + Vector<BasicBlock*, 1> jettisonedBlocks) { // This will add all of the nodes in secondBlock to firstBlock, but in so doing // it will also ensure that any GetLocals from the second block that refer to @@ -312,27 +324,25 @@ private: // then Phantoms are inserted for anything that the jettisonedBlock would have // kept alive. - BasicBlock* firstBlock = m_graph.m_blocks[firstBlockIndex].get(); - BasicBlock* secondBlock = m_graph.m_blocks[secondBlockIndex].get(); - // Remove the terminal of firstBlock since we don't need it anymore. Well, we don't - // really remove it; we actually turn it into a Phantom. - ASSERT(firstBlock->last()->isTerminal()); - CodeOrigin boundaryCodeOrigin = firstBlock->last()->codeOrigin; - firstBlock->last()->convertToPhantom(); - ASSERT(firstBlock->last()->refCount() == 1); + // really remove it; we actually turn it into a check. + Node* terminal = firstBlock->terminal(); + ASSERT(terminal->isTerminal()); + NodeOrigin boundaryNodeOrigin = terminal->origin; + terminal->remove(); + ASSERT(terminal->refCount() == 1); - if (jettisonedBlockIndex != NoBlock) { - BasicBlock* jettisonedBlock = m_graph.m_blocks[jettisonedBlockIndex].get(); + for (unsigned i = jettisonedBlocks.size(); i--;) { + BasicBlock* jettisonedBlock = jettisonedBlocks[i]; // Time to insert ghosties for things that need to be kept alive in case we OSR // exit prior to hitting the firstBlock's terminal, and end up going down a // different path than secondBlock. for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfArguments(); ++i) - keepOperandAlive(firstBlock, jettisonedBlock, boundaryCodeOrigin, argumentToOperand(i)); + keepOperandAlive(firstBlock, jettisonedBlock, boundaryNodeOrigin, virtualRegisterForArgument(i)); for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfLocals(); ++i) - keepOperandAlive(firstBlock, jettisonedBlock, boundaryCodeOrigin, i); + keepOperandAlive(firstBlock, jettisonedBlock, boundaryNodeOrigin, virtualRegisterForLocal(i)); } for (size_t i = 0; i < secondBlock->phis.size(); ++i) @@ -341,30 +351,30 @@ private: for (size_t i = 0; i < secondBlock->size(); ++i) firstBlock->append(secondBlock->at(i)); - ASSERT(firstBlock->last()->isTerminal()); + ASSERT(firstBlock->terminal()->isTerminal()); // Fix the predecessors of my new successors. This is tricky, since we are going to reset // all predecessors anyway due to reachability analysis. But we need to fix the // predecessors eagerly to ensure that we know what they are in case the next block we // consider in this phase wishes to query the predecessors of one of the blocks we // affected. - for (unsigned i = m_graph.numSuccessors(firstBlock); i--;) { - BasicBlock* successor = m_graph.m_blocks[m_graph.successor(firstBlock, i)].get(); - for (unsigned j = 0; j < successor->m_predecessors.size(); ++j) { - if (successor->m_predecessors[j] == secondBlockIndex) - successor->m_predecessors[j] = firstBlockIndex; + for (unsigned i = firstBlock->numSuccessors(); i--;) { + BasicBlock* successor = firstBlock->successor(i); + for (unsigned j = 0; j < successor->predecessors.size(); ++j) { + if (successor->predecessors[j] == secondBlock) + successor->predecessors[j] = firstBlock; } } // Fix the predecessors of my former successors. Again, we'd rather not do this, but it's // an unfortunate necessity. See above comment. - if (jettisonedBlockIndex != NoBlock) - fixJettisonedPredecessors(firstBlockIndex, jettisonedBlockIndex); + for (unsigned i = jettisonedBlocks.size(); i--;) + fixJettisonedPredecessors(firstBlock, jettisonedBlocks[i]); firstBlock->valuesAtTail = secondBlock->valuesAtTail; firstBlock->cfaBranchDirection = secondBlock->cfaBranchDirection; - m_graph.m_blocks[secondBlockIndex].clear(); + m_graph.killBlock(secondBlock); } }; |