| /* |
| * Copyright (C) 2012 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 "DFGBasicBlock.h" |
| #include "DFGGraph.h" |
| #include "DFGInsertionSet.h" |
| #include "DFGPhase.h" |
| #include "DFGValidate.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 (m_graph[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(); |
| 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(); |
| 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(); |
| BlockIndex takenBlockIndex = m_graph.successorForCondition(block, condition); |
| BlockIndex notTakenBlockIndex = m_graph.successorForCondition(block, !condition); |
| |
| ASSERT(m_graph[block->last()].isTerminal()); |
| CodeOrigin boundaryCodeOrigin = m_graph[block->last()].codeOrigin; |
| m_graph[block->last()].setOpAndDefaultFlags(Phantom); |
| ASSERT(m_graph[block->last()].refCount() == 1); |
| |
| jettisonBlock(blockIndex, notTakenBlockIndex, boundaryCodeOrigin); |
| |
| NodeIndex jumpNodeIndex = m_graph.size(); |
| Node jump(Jump, boundaryCodeOrigin, OpInfo(takenBlockIndex)); |
| jump.ref(); |
| m_graph.append(jump); |
| block->append(jumpNodeIndex); |
| } |
| 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 |
| 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 |
| ASSERT(m_graph[block->last()].isTerminal()); |
| Node& branch = m_graph[block->last()]; |
| ASSERT(branch.isTerminal()); |
| ASSERT(branch.op() == Branch); |
| branch.setOpAndDefaultFlags(Phantom); |
| ASSERT(branch.refCount() == 1); |
| |
| Node jump(Jump, branch.codeOrigin, OpInfo(targetBlockIndex)); |
| jump.ref(); |
| NodeIndex jumpNodeIndex = m_graph.size(); |
| m_graph.append(jump); |
| block->append(jumpNodeIndex); |
| } |
| 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); |
| } |
| } |
| |
| 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); |
| |
| // 1) Remove references from other blocks to this block. |
| for (unsigned i = m_graph.numSuccessors(block); i--;) |
| fixPhis(blockIndex, m_graph.successor(block, i)); |
| |
| // 2) Kill the block |
| m_graph.m_blocks[blockIndex].clear(); |
| } |
| |
| void keepOperandAlive(BasicBlock* block, CodeOrigin codeOrigin, int operand) |
| { |
| NodeIndex nodeIndex = block->variablesAtTail.operand(operand); |
| if (nodeIndex == NoNode) |
| return; |
| if (m_graph[nodeIndex].variableAccessData()->isCaptured()) |
| return; |
| if (m_graph[nodeIndex].op() == SetLocal) |
| nodeIndex = m_graph[nodeIndex].child1().index(); |
| Node& node = m_graph[nodeIndex]; |
| if (!node.shouldGenerate()) |
| return; |
| ASSERT(m_graph[nodeIndex].op() != SetLocal); |
| NodeIndex phantomNodeIndex = m_graph.size(); |
| Node phantom(Phantom, codeOrigin, nodeIndex); |
| m_graph.append(phantom); |
| m_graph.ref(phantomNodeIndex); |
| block->append(phantomNodeIndex); |
| } |
| |
| void fixPossibleGetLocal(BasicBlock* block, Edge& edge, bool changeRef) |
| { |
| Node& child = m_graph[edge]; |
| if (child.op() != GetLocal) |
| return; |
| #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) |
| dataLogF(" Considering GetLocal at @%u, local r%d.\n", edge.index(), child.local()); |
| #endif |
| if (child.variableAccessData()->isCaptured()) { |
| #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) |
| dataLogF(" It's captured.\n"); |
| #endif |
| return; |
| } |
| NodeIndex originalNodeIndex = block->variablesAtTail.operand(child.local()); |
| #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) |
| dataLogF(" Dealing with original @%u.\n", originalNodeIndex); |
| #endif |
| ASSERT(originalNodeIndex != NoNode); |
| Node* originalNode = &m_graph[originalNodeIndex]; |
| #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) |
| dataLogF(" Original has local r%d.\n", originalNode->local()); |
| #endif |
| ASSERT(child.local() == originalNode->local()); |
| // Possibilities: |
| // SetLocal -> the secondBlock is getting the value of something that is immediately |
| // available in the first block with a known NodeIndex. |
| // GetLocal -> the secondBlock is getting the value of something that the first |
| // block also gets. |
| // Phi -> the secondBlock is asking for keep-alive on an operand that the first block |
| // was also asking for keep-alive on. |
| // SetArgument -> the secondBlock is asking for keep-alive on an operand that the |
| // first block was keeping alive by virtue of the firstBlock being the root and |
| // the operand being an argument. |
| // Flush -> the secondBlock is asking for keep-alive on an operand that the first |
| // block was forcing to be alive, so the second block should refer child of |
| // the flush. |
| if (originalNode->op() == Flush) { |
| originalNodeIndex = originalNode->child1().index(); |
| originalNode = &m_graph[originalNodeIndex]; |
| } |
| switch (originalNode->op()) { |
| case SetLocal: { |
| if (changeRef) |
| ASSERT(originalNode->shouldGenerate()); |
| #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) |
| dataLogF(" It's a SetLocal.\n"); |
| #endif |
| m_graph.changeIndex(edge, originalNode->child1().index(), changeRef); |
| break; |
| } |
| case GetLocal: { |
| #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) |
| dataLogF(" It's a GetLocal.\n"); |
| #endif |
| if (originalNode->shouldGenerate()) |
| m_graph.changeIndex(edge, originalNodeIndex, changeRef); |
| // If we have a GetLocal that points to a child GetLocal that is dead, then |
| // we have no need to do anything: this original GetLocal is still valid. |
| break; |
| } |
| case Phi: |
| case SetArgument: { |
| if (changeRef) |
| ASSERT(originalNode->shouldGenerate()); |
| #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) |
| dataLogF(" It's Phi/SetArgument.\n"); |
| #endif |
| // Keep the GetLocal! |
| break; |
| } |
| default: |
| ASSERT_NOT_REACHED(); |
| break; |
| } |
| } |
| |
| 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, boundaryCodeOrigin, argumentToOperand(i)); |
| for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfLocals(); ++i) |
| keepOperandAlive(block, boundaryCodeOrigin, i); |
| |
| fixJettisonedPredecessors(blockIndex, jettisonedBlockIndex); |
| } |
| |
| void fixPhis(BlockIndex sourceBlockIndex, BlockIndex destinationBlockIndex) |
| { |
| BasicBlock* sourceBlock = m_graph.m_blocks[sourceBlockIndex].get(); |
| BasicBlock* destinationBlock = m_graph.m_blocks[destinationBlockIndex].get(); |
| if (!destinationBlock) { |
| // If we're trying to kill off the source block and the destination block is already |
| // dead, then we're done! |
| return; |
| } |
| for (size_t i = 0; i < destinationBlock->phis.size(); ++i) { |
| NodeIndex phiNodeIndex = destinationBlock->phis[i]; |
| Node& phiNode = m_graph[phiNodeIndex]; |
| NodeIndex myNodeIndex = sourceBlock->variablesAtTail.operand(phiNode.local()); |
| #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) |
| dataLogF("Considering removing reference from phi @%u to @%u on local r%d:", |
| phiNodeIndex, myNodeIndex, phiNode.local()); |
| #endif |
| if (myNodeIndex == NoNode) { |
| // This will happen if there is a phi in the destination that refers into |
| // the destination itself. |
| continue; |
| } |
| Node& myNode = m_graph[myNodeIndex]; |
| if (myNode.op() == GetLocal) |
| myNodeIndex = myNode.child1().index(); |
| for (unsigned j = 0; j < AdjacencyList::Size; ++j) |
| removePotentiallyDeadPhiReference(myNodeIndex, phiNode, j, sourceBlock->isReachable); |
| #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) |
| dataLogF("\n"); |
| #endif |
| } |
| } |
| |
| 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; |
| } |
| |
| fixPhis(blockIndex, jettisonedBlockIndex); |
| } |
| |
| void removePotentiallyDeadPhiReference(NodeIndex myNodeIndex, Node& phiNode, unsigned edgeIndex, bool changeRef) |
| { |
| if (phiNode.children.child(edgeIndex).indexUnchecked() != myNodeIndex) |
| return; |
| #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) |
| dataLogF(" Removing reference at child %u.", edgeIndex); |
| #endif |
| if (changeRef && phiNode.shouldGenerate()) |
| m_graph.deref(myNodeIndex); |
| phiNode.children.removeEdgeFromBag(edgeIndex); |
| } |
| |
| struct OperandSubstitution { |
| OperandSubstitution() |
| : oldChild(NoNode) |
| , newChild(NoNode) |
| { |
| } |
| |
| explicit OperandSubstitution(NodeIndex oldChild) |
| : oldChild(oldChild) |
| , newChild(oldChild) |
| { |
| } |
| |
| OperandSubstitution(NodeIndex oldChild, NodeIndex newChild) |
| : oldChild(oldChild) |
| , newChild(newChild) |
| { |
| ASSERT((oldChild == NoNode) == (newChild == NoNode)); |
| } |
| |
| void dump(FILE* out) |
| { |
| if (oldChild == NoNode) |
| fprintf(out, "-"); |
| else |
| fprintf(out, "@%u -> @%u", oldChild, newChild); |
| } |
| |
| NodeIndex oldChild; |
| NodeIndex newChild; |
| }; |
| |
| NodeIndex skipGetLocal(NodeIndex nodeIndex) |
| { |
| if (nodeIndex == NoNode) |
| return NoNode; |
| Node& node = m_graph[nodeIndex]; |
| if (node.op() == GetLocal) |
| return node.child1().index(); |
| return nodeIndex; |
| } |
| |
| void recordPossibleIncomingReference( |
| BasicBlock* secondBlock, Operands<OperandSubstitution>& substitutions, int operand) |
| { |
| substitutions.operand(operand) = OperandSubstitution( |
| skipGetLocal(secondBlock->variablesAtTail.operand(operand))); |
| } |
| |
| void recordNewTarget(Operands<OperandSubstitution>& substitutions, int operand, NodeIndex nodeIndex) |
| { |
| ASSERT(m_graph[nodeIndex].op() == SetLocal |
| || m_graph[nodeIndex].op() == SetArgument |
| || m_graph[nodeIndex].op() == Flush |
| || m_graph[nodeIndex].op() == Phi); |
| substitutions.operand(operand).newChild = nodeIndex; |
| } |
| |
| void fixTailOperand( |
| BasicBlock* firstBlock, BasicBlock* secondBlock, int operand, |
| Operands<OperandSubstitution>& substitutions) |
| { |
| NodeIndex atSecondTail = secondBlock->variablesAtTail.operand(operand); |
| |
| if (atSecondTail == NoNode) { |
| // If the variable is dead at the end of the second block, then do nothing; essentially |
| // this means that we want the tail state to reflect whatever the first block did. |
| return; |
| } |
| |
| Node& secondNode = m_graph[atSecondTail]; |
| |
| switch (secondNode.op()) { |
| case SetLocal: |
| case Flush: { |
| // The second block did interesting things to the variables, so update the tail |
| // accordingly. |
| firstBlock->variablesAtTail.operand(operand) = atSecondTail; |
| break; |
| } |
| |
| case Phi: { |
| // Keep what was in the first block. |
| ASSERT(firstBlock->variablesAtTail.operand(operand) != NoNode); |
| recordNewTarget(substitutions, operand, skipGetLocal(firstBlock->variablesAtTail.operand(operand))); |
| break; |
| } |
| |
| case GetLocal: { |
| // If it's a GetLocal on a captured var, then definitely keep what was |
| // in the second block. In particular, it's possible that the first |
| // block doesn't even know about this variable. |
| if (secondNode.variableAccessData()->isCaptured()) { |
| firstBlock->variablesAtTail.operand(operand) = atSecondTail; |
| recordNewTarget(substitutions, operand, secondNode.child1().index()); |
| break; |
| } |
| |
| // It's possible that the second block had a GetLocal and the first block |
| // had a SetArgument or a Phi. Then update the tail. Otherwise keep what was in the |
| // first block. |
| NodeIndex atFirstTail = firstBlock->variablesAtTail.operand(operand); |
| ASSERT(atFirstTail != NoNode); |
| switch (m_graph[atFirstTail].op()) { |
| case SetArgument: |
| case Phi: |
| firstBlock->variablesAtTail.operand(operand) = atSecondTail; |
| recordNewTarget(substitutions, operand, secondNode.child1().index()); |
| break; |
| |
| default: |
| // Keep what was in the first block, and adjust the substitution to account for |
| // the fact that successors will refer to the child of the GetLocal. |
| ASSERT(firstBlock->variablesAtTail.operand(operand) != NoNode); |
| recordNewTarget(substitutions, operand, skipGetLocal(firstBlock->variablesAtTail.operand(operand))); |
| break; |
| } |
| break; |
| } |
| |
| default: |
| ASSERT_NOT_REACHED(); |
| } |
| } |
| |
| 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(m_graph[firstBlock->last()].isTerminal()); |
| CodeOrigin boundaryCodeOrigin = m_graph[firstBlock->last()].codeOrigin; |
| m_graph[firstBlock->last()].setOpAndDefaultFlags(Phantom); |
| ASSERT(m_graph[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, boundaryCodeOrigin, argumentToOperand(i)); |
| for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfLocals(); ++i) |
| keepOperandAlive(firstBlock, boundaryCodeOrigin, i); |
| } |
| |
| for (size_t i = 0; i < secondBlock->phis.size(); ++i) |
| firstBlock->phis.append(secondBlock->phis[i]); |
| |
| // Before we start changing the second block's graph, record what nodes would |
| // be referenced by successors of the second block. |
| Operands<OperandSubstitution> substitutions( |
| secondBlock->variablesAtTail.numberOfArguments(), |
| secondBlock->variablesAtTail.numberOfLocals()); |
| for (size_t i = 0; i < secondBlock->variablesAtTail.numberOfArguments(); ++i) |
| recordPossibleIncomingReference(secondBlock, substitutions, argumentToOperand(i)); |
| for (size_t i = 0; i < secondBlock->variablesAtTail.numberOfLocals(); ++i) |
| recordPossibleIncomingReference(secondBlock, substitutions, i); |
| |
| for (size_t i = 0; i < secondBlock->size(); ++i) { |
| NodeIndex nodeIndex = secondBlock->at(i); |
| Node& node = m_graph[nodeIndex]; |
| |
| bool childrenAlreadyFixed = false; |
| |
| switch (node.op()) { |
| case Phantom: { |
| if (!node.child1()) |
| break; |
| |
| ASSERT(node.shouldGenerate()); |
| Node& possibleLocalOp = m_graph[node.child1()]; |
| if (possibleLocalOp.op() != GetLocal |
| && possibleLocalOp.hasLocal() |
| && !possibleLocalOp.variableAccessData()->isCaptured()) { |
| NodeIndex setLocalIndex = |
| firstBlock->variablesAtTail.operand(possibleLocalOp.local()); |
| Node& setLocal = m_graph[setLocalIndex]; |
| if (setLocal.op() == SetLocal) { |
| m_graph.changeEdge(node.children.child1(), setLocal.child1()); |
| ASSERT(!node.child2()); |
| ASSERT(!node.child3()); |
| childrenAlreadyFixed = true; |
| } |
| } |
| break; |
| } |
| |
| case Flush: |
| case GetLocal: { |
| // A Flush could use a GetLocal, SetLocal, SetArgument, or a Phi. |
| // If it uses a GetLocal, it'll be taken care of below. If it uses a |
| // SetLocal or SetArgument, then it must be using a node from the |
| // same block. But if it uses a Phi, then we should redirect it to |
| // use whatever the first block advertised as a tail operand. |
| // Similarly for GetLocal; it could use any of those except for |
| // GetLocal. If it uses a Phi then it should be redirected to use a |
| // Phi from the tail operand. |
| if (m_graph[node.child1()].op() != Phi) |
| break; |
| |
| NodeIndex atFirstIndex = firstBlock->variablesAtTail.operand(node.local()); |
| m_graph.changeEdge(node.children.child1(), Edge(skipGetLocal(atFirstIndex)), node.shouldGenerate()); |
| childrenAlreadyFixed = true; |
| break; |
| } |
| |
| default: |
| break; |
| } |
| |
| if (!childrenAlreadyFixed) { |
| bool changeRef = node.shouldGenerate(); |
| |
| // If the child is a GetLocal, then we might like to fix it. |
| if (node.flags() & NodeHasVarArgs) { |
| for (unsigned childIdx = node.firstChild(); |
| childIdx < node.firstChild() + node.numChildren(); |
| ++childIdx) { |
| if (!!m_graph.m_varArgChildren[childIdx]) |
| fixPossibleGetLocal(firstBlock, m_graph.m_varArgChildren[childIdx], changeRef); |
| } |
| } else if (!!node.child1()) { |
| fixPossibleGetLocal(firstBlock, node.children.child1(), changeRef); |
| if (!!node.child2()) { |
| fixPossibleGetLocal(firstBlock, node.children.child2(), changeRef); |
| if (!!node.child3()) |
| fixPossibleGetLocal(firstBlock, node.children.child3(), changeRef); |
| } |
| } |
| } |
| |
| firstBlock->append(nodeIndex); |
| } |
| |
| ASSERT(m_graph[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); |
| |
| // Fix up the variables at tail. |
| for (size_t i = 0; i < secondBlock->variablesAtHead.numberOfArguments(); ++i) |
| fixTailOperand(firstBlock, secondBlock, argumentToOperand(i), substitutions); |
| for (size_t i = 0; i < secondBlock->variablesAtHead.numberOfLocals(); ++i) |
| fixTailOperand(firstBlock, secondBlock, i, substitutions); |
| |
| // Fix up the references from our new successors. |
| 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->phis.size(); ++j) { |
| NodeIndex phiNodeIndex = successor->phis[j]; |
| Node& phiNode = m_graph[phiNodeIndex]; |
| bool changeRef = phiNode.shouldGenerate(); |
| OperandSubstitution substitution = substitutions.operand(phiNode.local()); |
| #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) |
| dataLogF(" Performing operand substitution @%u -> @%u.\n", |
| substitution.oldChild, substitution.newChild); |
| #endif |
| if (!phiNode.child1()) |
| continue; |
| if (phiNode.child1().index() == substitution.oldChild) |
| m_graph.changeIndex(phiNode.children.child1(), substitution.newChild, changeRef); |
| if (!phiNode.child2()) |
| continue; |
| if (phiNode.child2().index() == substitution.oldChild) |
| m_graph.changeIndex(phiNode.children.child2(), substitution.newChild, changeRef); |
| if (!phiNode.child3()) |
| continue; |
| if (phiNode.child3().index() == substitution.oldChild) |
| m_graph.changeIndex(phiNode.children.child3(), substitution.newChild, changeRef); |
| } |
| } |
| |
| 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) |
| |
| |
