X-Git-Url: https://git.saurik.com/apple/javascriptcore.git/blobdiff_plain/a253471d7f8e4d91bf6ebabab00155c3b387d3d0..93a3786624b2768d89bfa27e46598dc64e2fb70a:/dfg/DFGCFGSimplificationPhase.cpp diff --git a/dfg/DFGCFGSimplificationPhase.cpp b/dfg/DFGCFGSimplificationPhase.cpp new file mode 100644 index 0000000..c022fce --- /dev/null +++ b/dfg/DFGCFGSimplificationPhase.cpp @@ -0,0 +1,381 @@ +/* + * Copyright (C) 2012, 2013 Apple Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY + * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" +#include "DFGCFGSimplificationPhase.h" + +#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" + +namespace JSC { namespace DFG { + +class CFGSimplificationPhase : public Phase { +public: + CFGSimplificationPhase(Graph& graph) + : Phase(graph, "CFG simplification") + { + } + + bool run() + { + const bool extremeLogging = false; + + bool outerChanged = false; + bool innerChanged; + + do { + innerChanged = false; + for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) { + BasicBlock* block = m_graph.m_blocks[blockIndex].get(); + if (!block) + continue; + ASSERT(block->isReachable); + + switch (block->last()->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 (extremeLogging) + m_graph.dump(); + m_graph.dethread(); + mergeBlocks(blockIndex, m_graph.successor(block, 0), NoBlock); + 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 + // liveness. What we really want is to slam in a phantom at the end of the + // block, after the terminal. But we can't right now. :-( + // Idea: what if I slam the ghosties into my successor? Nope, that's + // 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! + break; + } + + case Branch: { + // 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 + if (extremeLogging) + m_graph.dump(); + m_graph.dethread(); + mergeBlocks( + blockIndex, + m_graph.successorForCondition(block, condition), + m_graph.successorForCondition(block, !condition)); + } 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); + + 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)); + } + 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; + } + + default: + break; + } + } + + if (innerChanged) { + // Here's the reason for this pass: + // Blocks: A, B, C, D, E, F + // A -> B, C + // B -> F + // C -> D, E + // D -> F + // E -> F + // + // Assume that A's branch is determined to go to B. Then the rest of this phase + // is smart enough to simplify down to: + // A -> B + // B -> F + // C -> D, E + // D -> F + // E -> F + // + // We will also merge A and B. But then we don't have any other mechanism to + // remove D, E as predecessors for F. Worse, the rest of this phase does not + // know how to fix the Phi functions of F to ensure that they no longer refer + // to variables in D, E. In general, we need a way to handle Phi simplification + // upon: + // 1) Removal of a predecessor due to branch simplification. The branch + // simplifier already does that. + // 2) Invalidation of a predecessor because said predecessor was rendered + // unreachable. We do this here. + // + // This implies that when a block is unreachable, we must inspect its + // successors' Phi functions to remove any references from them into the + // removed block. + + 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); + } + } + + if (Options::validateGraphAtEachPhase()) + validate(m_graph); + } while (innerChanged); + + return outerChanged; + } + +private: + void killUnreachable(BlockIndex blockIndex) + { + 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(); + } + + void keepOperandAlive(BasicBlock* block, BasicBlock* jettisonedBlock, CodeOrigin codeOrigin, int operand) + { + Node* livenessNode = jettisonedBlock->variablesAtHead.operand(operand); + if (!livenessNode) + return; + if (livenessNode->variableAccessData()->isCaptured()) + return; + block->appendNode( + m_graph, SpecNone, PhantomLocal, codeOrigin, + OpInfo(livenessNode->variableAccessData())); + } + + void jettisonBlock(BlockIndex blockIndex, BlockIndex jettisonedBlockIndex, CodeOrigin boundaryCodeOrigin) + { + 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)); + for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfLocals(); ++i) + keepOperandAlive(block, jettisonedBlock, boundaryCodeOrigin, i); + + fixJettisonedPredecessors(blockIndex, jettisonedBlockIndex); + } + + void fixJettisonedPredecessors(BlockIndex blockIndex, BlockIndex jettisonedBlockIndex) + { +#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; + } + } + + void mergeBlocks( + BlockIndex firstBlockIndex, BlockIndex secondBlockIndex, BlockIndex jettisonedBlockIndex) + { + // 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 + // SetLocals in the first block are relinked. If jettisonedBlock is not NoBlock, + // 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); + + if (jettisonedBlockIndex != NoBlock) { + BasicBlock* jettisonedBlock = m_graph.m_blocks[jettisonedBlockIndex].get(); + + // 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)); + for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfLocals(); ++i) + keepOperandAlive(firstBlock, jettisonedBlock, boundaryCodeOrigin, i); + } + + for (size_t i = 0; i < secondBlock->phis.size(); ++i) + firstBlock->phis.append(secondBlock->phis[i]); + + for (size_t i = 0; i < secondBlock->size(); ++i) + firstBlock->append(secondBlock->at(i)); + + ASSERT(firstBlock->last()->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; + } + } + + // 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); + + firstBlock->valuesAtTail = secondBlock->valuesAtTail; + firstBlock->cfaBranchDirection = secondBlock->cfaBranchDirection; + + m_graph.m_blocks[secondBlockIndex].clear(); + } +}; + +bool performCFGSimplification(Graph& graph) +{ + SamplingRegion samplingRegion("DFG CFG Simplification Phase"); + return runPhase(graph); +} + +} } // namespace JSC::DFG + +#endif // ENABLE(DFG_JIT) + +