| /* |
| * Copyright (C) 2014, 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 |
| * 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 "DFGObjectAllocationSinkingPhase.h" |
| |
| #if ENABLE(DFG_JIT) |
| |
| #include "DFGAbstractHeap.h" |
| #include "DFGBlockMapInlines.h" |
| #include "DFGClobberize.h" |
| #include "DFGGraph.h" |
| #include "DFGInsertOSRHintsForUpdate.h" |
| #include "DFGInsertionSet.h" |
| #include "DFGLivenessAnalysisPhase.h" |
| #include "DFGOSRAvailabilityAnalysisPhase.h" |
| #include "DFGPhase.h" |
| #include "DFGPromoteHeapAccess.h" |
| #include "DFGSSACalculator.h" |
| #include "DFGValidate.h" |
| #include "JSCInlines.h" |
| |
| namespace JSC { namespace DFG { |
| |
| static bool verbose = false; |
| |
| class ObjectAllocationSinkingPhase : public Phase { |
| public: |
| ObjectAllocationSinkingPhase(Graph& graph) |
| : Phase(graph, "object allocation sinking") |
| , m_ssaCalculator(graph) |
| , m_insertionSet(graph) |
| { |
| } |
| |
| bool run() |
| { |
| ASSERT(m_graph.m_fixpointState == FixpointNotConverged); |
| |
| m_graph.m_dominators.computeIfNecessary(m_graph); |
| |
| // Logically we wish to consider every NewObject and sink it. However it's probably not |
| // profitable to sink a NewObject that will always escape. So, first we do a very simple |
| // forward flow analysis that determines the set of NewObject nodes that have any chance |
| // of benefiting from object allocation sinking. Then we fixpoint the following rules: |
| // |
| // - For each NewObject, we turn the original NewObject into a PhantomNewObject and then |
| // we insert MaterializeNewObject just before those escaping sites that come before any |
| // other escaping sites - that is, there is no path between the allocation and those sites |
| // that would see any other escape. Note that Upsilons constitute escaping sites. Then we |
| // insert additional MaterializeNewObject nodes on Upsilons that feed into Phis that mix |
| // materializations and the original PhantomNewObject. We then turn each PutByOffset over a |
| // PhantomNewObject into a PutHint. |
| // |
| // - We perform the same optimization for MaterializeNewObject. This allows us to cover |
| // cases where we had MaterializeNewObject flowing into a PutHint. |
| // |
| // We could also add this rule: |
| // |
| // - If all of the Upsilons of a Phi have a MaterializeNewObject that isn't used by anyone |
| // else, then replace the Phi with the MaterializeNewObject. |
| // |
| // FIXME: Implement this. Note that this totally doable but it requires some gnarly |
| // code, and to be effective the pruner needs to be aware of it. Currently any Upsilon |
| // is considered to be an escape even by the pruner, so it's unlikely that we'll see |
| // many cases of Phi over Materializations. |
| // https://bugs.webkit.org/show_bug.cgi?id=136927 |
| |
| if (!performSinking()) |
| return false; |
| |
| while (performSinking()) { } |
| |
| if (verbose) { |
| dataLog("Graph after sinking:\n"); |
| m_graph.dump(); |
| } |
| |
| return true; |
| } |
| |
| private: |
| bool performSinking() |
| { |
| m_graph.computeRefCounts(); |
| performLivenessAnalysis(m_graph); |
| performOSRAvailabilityAnalysis(m_graph); |
| |
| CString graphBeforeSinking; |
| if (Options::verboseValidationFailure() && Options::validateGraphAtEachPhase()) { |
| StringPrintStream out; |
| m_graph.dump(out); |
| graphBeforeSinking = out.toCString(); |
| } |
| |
| if (verbose) { |
| dataLog("Graph before sinking:\n"); |
| m_graph.dump(); |
| } |
| |
| determineMaterializationPoints(); |
| if (m_sinkCandidates.isEmpty()) |
| return false; |
| |
| // At this point we are committed to sinking the sinking candidates. |
| placeMaterializationPoints(); |
| lowerNonReadingOperationsOnPhantomAllocations(); |
| promoteSunkenFields(); |
| |
| if (Options::validateGraphAtEachPhase()) |
| validate(m_graph, DumpGraph, graphBeforeSinking); |
| |
| if (verbose) |
| dataLog("Sinking iteration changed the graph.\n"); |
| return true; |
| } |
| |
| void determineMaterializationPoints() |
| { |
| // The premise of this pass is that if there exists a point in the program where some |
| // path from a phantom allocation site to that point causes materialization, then *all* |
| // paths cause materialization. This should mean that there are never any redundant |
| // materializations. |
| |
| m_sinkCandidates.clear(); |
| m_materializationToEscapee.clear(); |
| m_materializationSiteToMaterializations.clear(); |
| |
| BlockMap<HashMap<Node*, bool>> materializedAtHead(m_graph); |
| BlockMap<HashMap<Node*, bool>> materializedAtTail(m_graph); |
| |
| bool changed; |
| do { |
| if (verbose) |
| dataLog("Doing iteration of materialization point placement.\n"); |
| changed = false; |
| for (BasicBlock* block : m_graph.blocksInNaturalOrder()) { |
| HashMap<Node*, bool> materialized = materializedAtHead[block]; |
| if (verbose) |
| dataLog(" Looking at block ", pointerDump(block), "\n"); |
| for (Node* node : *block) { |
| handleNode( |
| node, |
| [&] () { |
| materialized.add(node, false); |
| }, |
| [&] (Node* escapee) { |
| auto iter = materialized.find(escapee); |
| if (iter != materialized.end()) { |
| if (verbose) |
| dataLog(" ", escapee, " escapes at ", node, "\n"); |
| iter->value = true; |
| } |
| }); |
| } |
| |
| if (verbose) |
| dataLog(" Materialized at tail of ", pointerDump(block), ": ", mapDump(materialized), "\n"); |
| |
| if (materialized == materializedAtTail[block]) |
| continue; |
| |
| materializedAtTail[block] = materialized; |
| changed = true; |
| |
| // Only propagate things to our successors if they are alive in all successors. |
| // So, we prune materialized-at-tail to only include things that are live. |
| Vector<Node*> toRemove; |
| for (auto pair : materialized) { |
| if (!block->ssa->liveAtTail.contains(pair.key)) |
| toRemove.append(pair.key); |
| } |
| for (Node* key : toRemove) |
| materialized.remove(key); |
| |
| for (BasicBlock* successorBlock : block->successors()) { |
| for (auto pair : materialized) { |
| materializedAtHead[successorBlock].add( |
| pair.key, false).iterator->value |= pair.value; |
| } |
| } |
| } |
| } while (changed); |
| |
| // Determine the sink candidates. Broadly, a sink candidate is a node that handleNode() |
| // believes is sinkable, and one of the following is true: |
| // |
| // 1) There exists a basic block with only backward outgoing edges (or no outgoing edges) |
| // in which the node wasn't materialized. This is meant to catch effectively-infinite |
| // loops in which we don't need to have allocated the object. |
| // |
| // 2) There exists a basic block at the tail of which the node is not materialized and the |
| // node is dead. |
| // |
| // 3) The sum of execution counts of the materializations is less than the sum of |
| // execution counts of the original node. |
| // |
| // We currently implement only rule #2. |
| // FIXME: Implement the two other rules. |
| // https://bugs.webkit.org/show_bug.cgi?id=137073 (rule #1) |
| // https://bugs.webkit.org/show_bug.cgi?id=137074 (rule #3) |
| |
| for (BasicBlock* block : m_graph.blocksInNaturalOrder()) { |
| for (auto pair : materializedAtTail[block]) { |
| if (pair.value) |
| continue; // It was materialized. |
| |
| if (block->ssa->liveAtTail.contains(pair.key)) |
| continue; // It might still get materialized in all of the successors. |
| |
| // We know that it died in this block and it wasn't materialized. That means that |
| // if we sink this allocation, then *this* will be a path along which we never |
| // have to allocate. Profit! |
| m_sinkCandidates.add(pair.key); |
| } |
| } |
| |
| if (m_sinkCandidates.isEmpty()) |
| return; |
| |
| // A materialization edge exists at any point where a node escapes but hasn't been |
| // materialized yet. We do this in two parts. First we find all of the nodes that cause |
| // escaping to happen, where the escapee had not yet been materialized. This catches |
| // everything but loops. We then catch loops - as well as weirder control flow constructs - |
| // in a subsequent pass that looks at places in the CFG where an edge exists from a block |
| // that hasn't materialized to a block that has. We insert the materialization along such an |
| // edge, and we rely on the fact that critical edges were already broken so that we actually |
| // either insert the materialization at the head of the successor or the tail of the |
| // predecessor. |
| // |
| // FIXME: This can create duplicate allocations when we really only needed to perform one. |
| // For example: |
| // |
| // var o = new Object(); |
| // if (rare) { |
| // if (stuff) |
| // call(o); // o escapes here. |
| // return; |
| // } |
| // // o doesn't escape down here. |
| // |
| // In this example, we would place a materialization point at call(o) and then we would find |
| // ourselves having to insert another one at the implicit else case of that if statement |
| // ('cause we've broken critical edges). We would instead really like to just have one |
| // materialization point right at the top of the then case of "if (rare)". To do this, we can |
| // find the LCA of the various materializations in the dom tree. |
| // https://bugs.webkit.org/show_bug.cgi?id=137124 |
| |
| // First pass: find intra-block materialization points. |
| for (BasicBlock* block : m_graph.blocksInNaturalOrder()) { |
| HashSet<Node*> materialized; |
| for (auto pair : materializedAtHead[block]) { |
| if (pair.value && m_sinkCandidates.contains(pair.key)) |
| materialized.add(pair.key); |
| } |
| |
| if (verbose) |
| dataLog("Placing materialization points in ", pointerDump(block), " with materialization set ", listDump(materialized), "\n"); |
| |
| for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) { |
| Node* node = block->at(nodeIndex); |
| |
| handleNode( |
| node, |
| [&] () { }, |
| [&] (Node* escapee) { |
| if (verbose) |
| dataLog("Seeing ", escapee, " escape at ", node, "\n"); |
| |
| if (!m_sinkCandidates.contains(escapee)) { |
| if (verbose) |
| dataLog(" It's not a sink candidate.\n"); |
| return; |
| } |
| |
| if (!materialized.add(escapee).isNewEntry) { |
| if (verbose) |
| dataLog(" It's already materialized.\n"); |
| return; |
| } |
| |
| createMaterialize(escapee, node); |
| }); |
| } |
| } |
| |
| // Second pass: find CFG edge materialization points. |
| for (BasicBlock* block : m_graph.blocksInNaturalOrder()) { |
| for (BasicBlock* successorBlock : block->successors()) { |
| for (auto pair : materializedAtHead[successorBlock]) { |
| Node* allocation = pair.key; |
| |
| // We only care if it is materialized in the successor. |
| if (!pair.value) |
| continue; |
| |
| // We only care about sinking candidates. |
| if (!m_sinkCandidates.contains(allocation)) |
| continue; |
| |
| // We only care if it isn't materialized in the predecessor. |
| if (materializedAtTail[block].get(allocation)) |
| continue; |
| |
| // We need to decide if we put the materialization at the head of the successor, |
| // or the tail of the predecessor. It needs to be placed so that the allocation |
| // is never materialized before, and always materialized after. |
| |
| // Is it never materialized in any of successor's predecessors? I like to think |
| // of "successors' predecessors" and "predecessor's successors" as the "shadow", |
| // because of what it looks like when you draw it. |
| bool neverMaterializedInShadow = true; |
| for (BasicBlock* shadowBlock : successorBlock->predecessors) { |
| if (materializedAtTail[shadowBlock].get(allocation)) { |
| neverMaterializedInShadow = false; |
| break; |
| } |
| } |
| |
| if (neverMaterializedInShadow) { |
| createMaterialize(allocation, successorBlock->firstOriginNode()); |
| continue; |
| } |
| |
| // Because we had broken critical edges, it must be the case that the |
| // predecessor's successors all materialize the object. This is because the |
| // previous case is guaranteed to catch the case where the successor only has |
| // one predecessor. When critical edges are broken, this is also the only case |
| // where the predecessor could have had multiple successors. Therefore we have |
| // already handled the case where the predecessor has multiple successors. |
| DFG_ASSERT(m_graph, block, block->numSuccessors() == 1); |
| |
| createMaterialize(allocation, block->terminal()); |
| } |
| } |
| } |
| } |
| |
| void placeMaterializationPoints() |
| { |
| m_ssaCalculator.reset(); |
| |
| // The "variables" are the object allocations that we are sinking. So, nodeToVariable maps |
| // sink candidates (aka escapees) to the SSACalculator's notion of Variable, and indexToNode |
| // maps in the opposite direction using the SSACalculator::Variable::index() as the key. |
| HashMap<Node*, SSACalculator::Variable*> nodeToVariable; |
| Vector<Node*> indexToNode; |
| |
| for (Node* node : m_sinkCandidates) { |
| SSACalculator::Variable* variable = m_ssaCalculator.newVariable(); |
| nodeToVariable.add(node, variable); |
| ASSERT(indexToNode.size() == variable->index()); |
| indexToNode.append(node); |
| } |
| |
| for (BasicBlock* block : m_graph.blocksInNaturalOrder()) { |
| for (Node* node : *block) { |
| if (SSACalculator::Variable* variable = nodeToVariable.get(node)) |
| m_ssaCalculator.newDef(variable, block, node); |
| |
| for (Node* materialize : m_materializationSiteToMaterializations.get(node)) { |
| m_ssaCalculator.newDef( |
| nodeToVariable.get(m_materializationToEscapee.get(materialize)), |
| block, materialize); |
| } |
| } |
| } |
| |
| m_ssaCalculator.computePhis( |
| [&] (SSACalculator::Variable* variable, BasicBlock* block) -> Node* { |
| Node* allocation = indexToNode[variable->index()]; |
| if (!block->ssa->liveAtHead.contains(allocation)) |
| return nullptr; |
| |
| Node* phiNode = m_graph.addNode(allocation->prediction(), Phi, NodeOrigin()); |
| phiNode->mergeFlags(NodeResultJS); |
| return phiNode; |
| }); |
| |
| // Place Phis in the right places. Replace all uses of any allocation with the appropriate |
| // materialization. Create the appropriate Upsilon nodes. |
| LocalOSRAvailabilityCalculator availabilityCalculator; |
| for (BasicBlock* block : m_graph.blocksInNaturalOrder()) { |
| HashMap<Node*, Node*> mapping; |
| |
| for (Node* candidate : block->ssa->liveAtHead) { |
| SSACalculator::Variable* variable = nodeToVariable.get(candidate); |
| if (!variable) |
| continue; |
| |
| SSACalculator::Def* def = m_ssaCalculator.reachingDefAtHead(block, variable); |
| if (!def) |
| continue; |
| |
| mapping.set(indexToNode[variable->index()], def->value()); |
| } |
| |
| availabilityCalculator.beginBlock(block); |
| for (SSACalculator::Def* phiDef : m_ssaCalculator.phisForBlock(block)) { |
| m_insertionSet.insert(0, phiDef->value()); |
| |
| Node* originalNode = indexToNode[phiDef->variable()->index()]; |
| insertOSRHintsForUpdate( |
| m_insertionSet, 0, NodeOrigin(), availabilityCalculator.m_availability, |
| originalNode, phiDef->value()); |
| |
| mapping.set(originalNode, phiDef->value()); |
| } |
| |
| for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) { |
| Node* node = block->at(nodeIndex); |
| |
| for (Node* materialize : m_materializationSiteToMaterializations.get(node)) { |
| Node* escapee = m_materializationToEscapee.get(materialize); |
| m_insertionSet.insert(nodeIndex, materialize); |
| insertOSRHintsForUpdate( |
| m_insertionSet, nodeIndex, node->origin, |
| availabilityCalculator.m_availability, escapee, materialize); |
| mapping.set(escapee, materialize); |
| } |
| |
| availabilityCalculator.executeNode(node); |
| |
| m_graph.doToChildren( |
| node, |
| [&] (Edge& edge) { |
| if (Node* materialize = mapping.get(edge.node())) |
| edge.setNode(materialize); |
| }); |
| |
| // If you cause an escape, you shouldn't see the original escapee. |
| if (validationEnabled()) { |
| handleNode( |
| node, |
| [&] () { }, |
| [&] (Node* escapee) { |
| DFG_ASSERT(m_graph, node, !m_sinkCandidates.contains(escapee)); |
| }); |
| } |
| } |
| |
| NodeAndIndex terminal = block->findTerminal(); |
| size_t upsilonInsertionPoint = terminal.index; |
| Node* upsilonWhere = terminal.node; |
| NodeOrigin upsilonOrigin = upsilonWhere->origin; |
| for (BasicBlock* successorBlock : block->successors()) { |
| for (SSACalculator::Def* phiDef : m_ssaCalculator.phisForBlock(successorBlock)) { |
| Node* phiNode = phiDef->value(); |
| SSACalculator::Variable* variable = phiDef->variable(); |
| Node* allocation = indexToNode[variable->index()]; |
| |
| Node* incoming = mapping.get(allocation); |
| DFG_ASSERT(m_graph, incoming, incoming != allocation); |
| |
| m_insertionSet.insertNode( |
| upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin, |
| OpInfo(phiNode), incoming->defaultEdge()); |
| } |
| } |
| |
| m_insertionSet.execute(block); |
| } |
| |
| // At this point we have dummy materialization nodes along with edges to them. This means |
| // that the part of the control flow graph that prefers to see actual object allocations |
| // is completely fixed up, except for the materializations themselves. |
| } |
| |
| void lowerNonReadingOperationsOnPhantomAllocations() |
| { |
| // Lower everything but reading operations on phantom allocations. We absolutely have to |
| // lower all writes so as to reveal them to the SSA calculator. We cannot lower reads |
| // because the whole point is that those go away completely. |
| |
| for (BasicBlock* block : m_graph.blocksInNaturalOrder()) { |
| for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) { |
| Node* node = block->at(nodeIndex); |
| switch (node->op()) { |
| case PutByOffset: { |
| Node* target = node->child2().node(); |
| if (m_sinkCandidates.contains(target)) { |
| ASSERT(target->isPhantomObjectAllocation()); |
| node->convertToPutByOffsetHint(); |
| } |
| break; |
| } |
| |
| case PutClosureVar: { |
| Node* target = node->child1().node(); |
| if (m_sinkCandidates.contains(target)) { |
| ASSERT(target->isPhantomActivationAllocation()); |
| node->convertToPutClosureVarHint(); |
| } |
| break; |
| } |
| |
| case PutStructure: { |
| Node* target = node->child1().node(); |
| if (m_sinkCandidates.contains(target)) { |
| ASSERT(target->isPhantomObjectAllocation()); |
| Node* structure = m_insertionSet.insertConstant( |
| nodeIndex, node->origin, JSValue(node->transition()->next)); |
| node->convertToPutStructureHint(structure); |
| } |
| break; |
| } |
| |
| case NewObject: { |
| if (m_sinkCandidates.contains(node)) { |
| Node* structure = m_insertionSet.insertConstant( |
| nodeIndex + 1, node->origin, JSValue(node->structure())); |
| m_insertionSet.insert( |
| nodeIndex + 1, |
| PromotedHeapLocation(StructurePLoc, node).createHint( |
| m_graph, node->origin, structure)); |
| node->convertToPhantomNewObject(); |
| } |
| break; |
| } |
| |
| case MaterializeNewObject: { |
| if (m_sinkCandidates.contains(node)) { |
| m_insertionSet.insert( |
| nodeIndex + 1, |
| PromotedHeapLocation(StructurePLoc, node).createHint( |
| m_graph, node->origin, m_graph.varArgChild(node, 0).node())); |
| for (unsigned i = 0; i < node->objectMaterializationData().m_properties.size(); ++i) { |
| unsigned identifierNumber = |
| node->objectMaterializationData().m_properties[i].m_identifierNumber; |
| m_insertionSet.insert( |
| nodeIndex + 1, |
| PromotedHeapLocation( |
| NamedPropertyPLoc, node, identifierNumber).createHint( |
| m_graph, node->origin, |
| m_graph.varArgChild(node, i + 1).node())); |
| } |
| node->convertToPhantomNewObject(); |
| } |
| break; |
| } |
| |
| case NewFunction: { |
| if (m_sinkCandidates.contains(node)) { |
| Node* executable = m_insertionSet.insertConstant( |
| nodeIndex + 1, node->origin, node->cellOperand()); |
| m_insertionSet.insert( |
| nodeIndex + 1, |
| PromotedHeapLocation(FunctionExecutablePLoc, node).createHint( |
| m_graph, node->origin, executable)); |
| m_insertionSet.insert( |
| nodeIndex + 1, |
| PromotedHeapLocation(FunctionActivationPLoc, node).createHint( |
| m_graph, node->origin, node->child1().node())); |
| node->convertToPhantomNewFunction(); |
| } |
| break; |
| } |
| |
| case CreateActivation: { |
| if (m_sinkCandidates.contains(node)) { |
| m_insertionSet.insert( |
| nodeIndex + 1, |
| PromotedHeapLocation(ActivationScopePLoc, node).createHint( |
| m_graph, node->origin, node->child1().node())); |
| node->convertToPhantomCreateActivation(); |
| } |
| break; |
| } |
| |
| case MaterializeCreateActivation: { |
| if (m_sinkCandidates.contains(node)) { |
| m_insertionSet.insert( |
| nodeIndex + 1, |
| PromotedHeapLocation(ActivationScopePLoc, node).createHint( |
| m_graph, node->origin, m_graph.varArgChild(node, 0).node())); |
| ObjectMaterializationData& data = node->objectMaterializationData(); |
| for (unsigned i = 0; i < data.m_properties.size(); ++i) { |
| unsigned identifierNumber = data.m_properties[i].m_identifierNumber; |
| m_insertionSet.insert( |
| nodeIndex + 1, |
| PromotedHeapLocation( |
| ClosureVarPLoc, node, identifierNumber).createHint( |
| m_graph, node->origin, |
| m_graph.varArgChild(node, i + 1).node())); |
| } |
| node->convertToPhantomCreateActivation(); |
| } |
| break; |
| } |
| |
| case StoreBarrier: |
| case StoreBarrierWithNullCheck: { |
| Node* target = node->child1().node(); |
| if (m_sinkCandidates.contains(target)) { |
| ASSERT(target->isPhantomAllocation()); |
| node->remove(); |
| } |
| break; |
| } |
| |
| default: |
| break; |
| } |
| |
| m_graph.doToChildren( |
| node, |
| [&] (Edge& edge) { |
| if (m_sinkCandidates.contains(edge.node())) |
| edge.setUseKind(KnownCellUse); |
| }); |
| } |
| m_insertionSet.execute(block); |
| } |
| } |
| |
| void promoteSunkenFields() |
| { |
| // Collect the set of heap locations that we will be operating over. |
| HashSet<PromotedHeapLocation> locations; |
| for (BasicBlock* block : m_graph.blocksInNaturalOrder()) { |
| for (Node* node : *block) { |
| promoteHeapAccess( |
| node, |
| [&] (PromotedHeapLocation location, Edge) { |
| if (m_sinkCandidates.contains(location.base())) |
| locations.add(location); |
| }, |
| [&] (PromotedHeapLocation location) { |
| if (m_sinkCandidates.contains(location.base())) |
| locations.add(location); |
| }); |
| } |
| } |
| |
| // Figure out which locations belong to which allocations. |
| m_locationsForAllocation.clear(); |
| for (PromotedHeapLocation location : locations) { |
| auto result = m_locationsForAllocation.add(location.base(), Vector<PromotedHeapLocation>()); |
| ASSERT(!result.iterator->value.contains(location)); |
| result.iterator->value.append(location); |
| } |
| |
| // For each sunken thingy, make sure we create Bottom values for all of its fields. |
| // Note that this has the hilarious slight inefficiency of creating redundant hints for |
| // things that were previously materializations. This should only impact compile times and |
| // not code quality, and it's necessary for soundness without some data structure hackage. |
| // For example, a MaterializeNewObject that we choose to sink may have new fields added to |
| // it conditionally. That would necessitate Bottoms. |
| Node* bottom = nullptr; |
| for (BasicBlock* block : m_graph.blocksInNaturalOrder()) { |
| if (block == m_graph.block(0)) |
| bottom = m_insertionSet.insertConstant(0, NodeOrigin(), jsUndefined()); |
| |
| for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) { |
| Node* node = block->at(nodeIndex); |
| for (PromotedHeapLocation location : m_locationsForAllocation.get(node)) { |
| m_insertionSet.insert( |
| nodeIndex + 1, location.createHint(m_graph, node->origin, bottom)); |
| } |
| } |
| m_insertionSet.execute(block); |
| } |
| |
| m_ssaCalculator.reset(); |
| |
| // Collect the set of "variables" that we will be sinking. |
| m_locationToVariable.clear(); |
| m_indexToLocation.clear(); |
| for (PromotedHeapLocation location : locations) { |
| SSACalculator::Variable* variable = m_ssaCalculator.newVariable(); |
| m_locationToVariable.add(location, variable); |
| ASSERT(m_indexToLocation.size() == variable->index()); |
| m_indexToLocation.append(location); |
| } |
| |
| // Create Defs from the existing hints. |
| for (BasicBlock* block : m_graph.blocksInNaturalOrder()) { |
| for (Node* node : *block) { |
| promoteHeapAccess( |
| node, |
| [&] (PromotedHeapLocation location, Edge value) { |
| if (!m_sinkCandidates.contains(location.base())) |
| return; |
| SSACalculator::Variable* variable = m_locationToVariable.get(location); |
| m_ssaCalculator.newDef(variable, block, value.node()); |
| }, |
| [&] (PromotedHeapLocation) { }); |
| } |
| } |
| |
| // OMG run the SSA calculator to create Phis! |
| m_ssaCalculator.computePhis( |
| [&] (SSACalculator::Variable* variable, BasicBlock* block) -> Node* { |
| PromotedHeapLocation location = m_indexToLocation[variable->index()]; |
| if (!block->ssa->liveAtHead.contains(location.base())) |
| return nullptr; |
| |
| Node* phiNode = m_graph.addNode(SpecHeapTop, Phi, NodeOrigin()); |
| phiNode->mergeFlags(NodeResultJS); |
| return phiNode; |
| }); |
| |
| // Place Phis in the right places, replace all uses of any load with the appropriate |
| // value, and create the appropriate Upsilon nodes. |
| m_graph.clearReplacements(); |
| for (BasicBlock* block : m_graph.blocksInPreOrder()) { |
| // This mapping table is intended to be lazy. If something is omitted from the table, |
| // it means that there haven't been any local stores to that promoted heap location. |
| m_localMapping.clear(); |
| |
| // Insert the Phi functions that we had previously created. |
| for (SSACalculator::Def* phiDef : m_ssaCalculator.phisForBlock(block)) { |
| PromotedHeapLocation location = m_indexToLocation[phiDef->variable()->index()]; |
| |
| m_insertionSet.insert( |
| 0, phiDef->value()); |
| m_insertionSet.insert( |
| 0, location.createHint(m_graph, NodeOrigin(), phiDef->value())); |
| m_localMapping.add(location, phiDef->value()); |
| } |
| |
| if (verbose) |
| dataLog("Local mapping at ", pointerDump(block), ": ", mapDump(m_localMapping), "\n"); |
| |
| // Process the block and replace all uses of loads with the promoted value. |
| for (Node* node : *block) { |
| m_graph.performSubstitution(node); |
| |
| if (Node* escapee = m_materializationToEscapee.get(node)) |
| populateMaterialize(block, node, escapee); |
| |
| promoteHeapAccess( |
| node, |
| [&] (PromotedHeapLocation location, Edge value) { |
| if (m_sinkCandidates.contains(location.base())) |
| m_localMapping.set(location, value.node()); |
| }, |
| [&] (PromotedHeapLocation location) { |
| if (m_sinkCandidates.contains(location.base())) { |
| switch (node->op()) { |
| case CheckStructure: |
| node->convertToCheckStructureImmediate(resolve(block, location)); |
| break; |
| |
| default: |
| node->replaceWith(resolve(block, location)); |
| break; |
| } |
| } |
| }); |
| } |
| |
| // Gotta drop some Upsilons. |
| NodeAndIndex terminal = block->findTerminal(); |
| size_t upsilonInsertionPoint = terminal.index; |
| NodeOrigin upsilonOrigin = terminal.node->origin; |
| for (BasicBlock* successorBlock : block->successors()) { |
| for (SSACalculator::Def* phiDef : m_ssaCalculator.phisForBlock(successorBlock)) { |
| Node* phiNode = phiDef->value(); |
| SSACalculator::Variable* variable = phiDef->variable(); |
| PromotedHeapLocation location = m_indexToLocation[variable->index()]; |
| Node* incoming = resolve(block, location); |
| |
| m_insertionSet.insertNode( |
| upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin, |
| OpInfo(phiNode), incoming->defaultEdge()); |
| } |
| } |
| |
| m_insertionSet.execute(block); |
| } |
| } |
| |
| Node* resolve(BasicBlock* block, PromotedHeapLocation location) |
| { |
| if (Node* result = m_localMapping.get(location)) |
| return result; |
| |
| // This implies that there is no local mapping. Find a non-local mapping. |
| SSACalculator::Def* def = m_ssaCalculator.nonLocalReachingDef( |
| block, m_locationToVariable.get(location)); |
| ASSERT(def); |
| ASSERT(def->value()); |
| m_localMapping.add(location, def->value()); |
| return def->value(); |
| } |
| |
| template<typename SinkCandidateFunctor, typename EscapeFunctor> |
| void handleNode( |
| Node* node, |
| const SinkCandidateFunctor& sinkCandidate, |
| const EscapeFunctor& escape) |
| { |
| switch (node->op()) { |
| case NewObject: |
| case MaterializeNewObject: |
| case MaterializeCreateActivation: |
| sinkCandidate(); |
| m_graph.doToChildren( |
| node, |
| [&] (Edge edge) { |
| escape(edge.node()); |
| }); |
| break; |
| |
| case NewFunction: |
| if (!node->castOperand<FunctionExecutable*>()->singletonFunction()->isStillValid()) |
| sinkCandidate(); |
| m_graph.doToChildren( |
| node, |
| [&] (Edge edge) { |
| escape(edge.node()); |
| }); |
| break; |
| |
| case CreateActivation: |
| if (!m_graph.symbolTableFor(node->origin.semantic)->singletonScope()->isStillValid()) |
| sinkCandidate(); |
| m_graph.doToChildren( |
| node, |
| [&] (Edge edge) { |
| escape(edge.node()); |
| }); |
| break; |
| |
| case MovHint: |
| case Check: |
| case PutHint: |
| case StoreBarrier: |
| case StoreBarrierWithNullCheck: |
| break; |
| |
| case PutStructure: |
| case CheckStructure: |
| case GetByOffset: |
| case MultiGetByOffset: |
| case GetGetterSetterByOffset: { |
| Node* target = node->child1().node(); |
| if (!target->isObjectAllocation()) |
| escape(target); |
| break; |
| } |
| |
| case PutByOffset: { |
| Node* target = node->child2().node(); |
| if (!target->isObjectAllocation()) { |
| escape(target); |
| escape(node->child1().node()); |
| } |
| escape(node->child3().node()); |
| break; |
| } |
| |
| case PutClosureVar: { |
| Node* target = node->child1().node(); |
| if (!target->isActivationAllocation()) |
| escape(target); |
| escape(node->child2().node()); |
| break; |
| } |
| |
| case MultiPutByOffset: |
| // FIXME: In the future we should be able to handle this. It's just a matter of |
| // building the appropriate *Hint variant of this instruction, along with a |
| // PhantomStructureSelect node - since this transforms the Structure in a conditional |
| // way. |
| // https://bugs.webkit.org/show_bug.cgi?id=136924 |
| escape(node->child1().node()); |
| escape(node->child2().node()); |
| break; |
| |
| default: |
| m_graph.doToChildren( |
| node, |
| [&] (Edge edge) { |
| escape(edge.node()); |
| }); |
| break; |
| } |
| } |
| |
| Node* createMaterialize(Node* escapee, Node* where) |
| { |
| Node* result = nullptr; |
| |
| switch (escapee->op()) { |
| case NewObject: |
| case MaterializeNewObject: { |
| ObjectMaterializationData* data = m_graph.m_objectMaterializationData.add(); |
| |
| result = m_graph.addNode( |
| escapee->prediction(), Node::VarArg, MaterializeNewObject, |
| NodeOrigin( |
| escapee->origin.semantic, |
| where->origin.forExit), |
| OpInfo(data), OpInfo(), 0, 0); |
| break; |
| } |
| |
| case NewFunction: |
| result = m_graph.addNode( |
| escapee->prediction(), NewFunction, |
| NodeOrigin( |
| escapee->origin.semantic, |
| where->origin.forExit), |
| OpInfo(escapee->cellOperand()), |
| escapee->child1()); |
| break; |
| |
| case CreateActivation: |
| case MaterializeCreateActivation: { |
| ObjectMaterializationData* data = m_graph.m_objectMaterializationData.add(); |
| |
| result = m_graph.addNode( |
| escapee->prediction(), Node::VarArg, MaterializeCreateActivation, |
| NodeOrigin( |
| escapee->origin.semantic, |
| where->origin.forExit), |
| OpInfo(data), OpInfo(), 0, 0); |
| break; |
| } |
| |
| default: |
| DFG_CRASH(m_graph, escapee, "Bad escapee op"); |
| break; |
| } |
| |
| if (verbose) |
| dataLog("Creating materialization point at ", where, " for ", escapee, ": ", result, "\n"); |
| |
| m_materializationToEscapee.add(result, escapee); |
| m_materializationSiteToMaterializations.add( |
| where, Vector<Node*>()).iterator->value.append(result); |
| |
| return result; |
| } |
| |
| void populateMaterialize(BasicBlock* block, Node* node, Node* escapee) |
| { |
| switch (node->op()) { |
| case MaterializeNewObject: { |
| ObjectMaterializationData& data = node->objectMaterializationData(); |
| unsigned firstChild = m_graph.m_varArgChildren.size(); |
| |
| Vector<PromotedHeapLocation> locations = m_locationsForAllocation.get(escapee); |
| |
| PromotedHeapLocation structure(StructurePLoc, escapee); |
| ASSERT(locations.contains(structure)); |
| |
| m_graph.m_varArgChildren.append(Edge(resolve(block, structure), KnownCellUse)); |
| |
| for (unsigned i = 0; i < locations.size(); ++i) { |
| switch (locations[i].kind()) { |
| case StructurePLoc: { |
| ASSERT(locations[i] == structure); |
| break; |
| } |
| |
| case NamedPropertyPLoc: { |
| Node* value = resolve(block, locations[i]); |
| if (value->op() == BottomValue) { |
| // We can skip Bottoms entirely. |
| break; |
| } |
| |
| data.m_properties.append(PhantomPropertyValue(locations[i].info())); |
| m_graph.m_varArgChildren.append(value); |
| break; |
| } |
| |
| default: |
| DFG_CRASH(m_graph, node, "Bad location kind"); |
| } |
| } |
| |
| node->children = AdjacencyList( |
| AdjacencyList::Variable, |
| firstChild, m_graph.m_varArgChildren.size() - firstChild); |
| break; |
| } |
| |
| case MaterializeCreateActivation: { |
| ObjectMaterializationData& data = node->objectMaterializationData(); |
| |
| unsigned firstChild = m_graph.m_varArgChildren.size(); |
| |
| Vector<PromotedHeapLocation> locations = m_locationsForAllocation.get(escapee); |
| |
| PromotedHeapLocation scope(ActivationScopePLoc, escapee); |
| ASSERT(locations.contains(scope)); |
| |
| m_graph.m_varArgChildren.append(Edge(resolve(block, scope), KnownCellUse)); |
| |
| for (unsigned i = 0; i < locations.size(); ++i) { |
| switch (locations[i].kind()) { |
| case ActivationScopePLoc: { |
| ASSERT(locations[i] == scope); |
| break; |
| } |
| |
| case ClosureVarPLoc: { |
| Node* value = resolve(block, locations[i]); |
| if (value->op() == BottomValue) |
| break; |
| |
| data.m_properties.append(PhantomPropertyValue(locations[i].info())); |
| m_graph.m_varArgChildren.append(value); |
| break; |
| } |
| |
| default: |
| DFG_CRASH(m_graph, node, "Bad location kind"); |
| } |
| } |
| |
| node->children = AdjacencyList( |
| AdjacencyList::Variable, |
| firstChild, m_graph.m_varArgChildren.size() - firstChild); |
| break; |
| } |
| |
| case NewFunction: { |
| if (!ASSERT_DISABLED) { |
| Vector<PromotedHeapLocation> locations = m_locationsForAllocation.get(escapee); |
| |
| ASSERT(locations.size() == 2); |
| |
| PromotedHeapLocation executable(FunctionExecutablePLoc, escapee); |
| ASSERT(locations.contains(executable)); |
| |
| PromotedHeapLocation activation(FunctionActivationPLoc, escapee); |
| ASSERT(locations.contains(activation)); |
| |
| for (unsigned i = 0; i < locations.size(); ++i) { |
| switch (locations[i].kind()) { |
| case FunctionExecutablePLoc: { |
| ASSERT(locations[i] == executable); |
| break; |
| } |
| |
| case FunctionActivationPLoc: { |
| ASSERT(locations[i] == activation); |
| break; |
| } |
| |
| default: |
| DFG_CRASH(m_graph, node, "Bad location kind"); |
| } |
| } |
| } |
| |
| break; |
| } |
| |
| default: |
| DFG_CRASH(m_graph, node, "Bad materialize op"); |
| break; |
| } |
| } |
| |
| SSACalculator m_ssaCalculator; |
| HashSet<Node*> m_sinkCandidates; |
| HashMap<Node*, Node*> m_materializationToEscapee; |
| HashMap<Node*, Vector<Node*>> m_materializationSiteToMaterializations; |
| HashMap<Node*, Vector<PromotedHeapLocation>> m_locationsForAllocation; |
| HashMap<PromotedHeapLocation, SSACalculator::Variable*> m_locationToVariable; |
| Vector<PromotedHeapLocation> m_indexToLocation; |
| HashMap<PromotedHeapLocation, Node*> m_localMapping; |
| InsertionSet m_insertionSet; |
| }; |
| |
| bool performObjectAllocationSinking(Graph& graph) |
| { |
| SamplingRegion samplingRegion("DFG Object Allocation Sinking Phase"); |
| return runPhase<ObjectAllocationSinkingPhase>(graph); |
| } |
| |
| } } // namespace JSC::DFG |
| |
| #endif // ENABLE(DFG_JIT) |
| |
