| /* |
| * 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<CFGSimplificationPhase>(graph); |
| } |
| |
| } } // namespace JSC::DFG |
| |
| #endif // ENABLE(DFG_JIT) |
| |
| |
