--- /dev/null
+/*
+ * 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 "DFGCombinedLiveness.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);
+ m_combinedLiveness = CombinedLiveness(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 (!m_combinedLiveness.liveAtTail[block].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 (m_combinedLiveness.liveAtTail[block].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 (!m_combinedLiveness.liveAtHead[block].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 : m_combinedLiveness.liveAtHead[block]) {
+ 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* symbolTableNode = m_insertionSet.insertConstant(
+ nodeIndex + 1, node->origin, node->cellOperand());
+ m_insertionSet.insert(
+ nodeIndex + 1,
+ PromotedHeapLocation(ActivationSymbolTablePLoc, node).createHint(
+ m_graph, node->origin, symbolTableNode));
+
+ {
+ SymbolTable* symbolTable = node->castOperand<SymbolTable*>();
+ Node* undefined = m_insertionSet.insertConstant(
+ nodeIndex + 1, node->origin, jsUndefined());
+ ConcurrentJITLocker locker(symbolTable->m_lock);
+ for (auto iter = symbolTable->begin(locker), end = symbolTable->end(locker); iter != end; ++iter) {
+ m_insertionSet.insert(
+ nodeIndex + 1,
+ PromotedHeapLocation(
+ ClosureVarPLoc, node, iter->value.scopeOffset().offset()).createHint(
+ m_graph, node->origin, undefined));
+ }
+ }
+
+ 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()));
+ Node* symbolTableNode = m_insertionSet.insertConstant(
+ nodeIndex + 1, node->origin, node->cellOperand());
+ m_insertionSet.insert(
+ nodeIndex + 1,
+ PromotedHeapLocation(ActivationSymbolTablePLoc, node).createHint(
+ m_graph, node->origin, symbolTableNode));
+ 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: {
+ DFG_CRASH(m_graph, node, "Unexpected store barrier during sinking.");
+ 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 (!m_combinedLiveness.liveAtHead[block].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();
+ escape(node->child1().node());
+ break;
+
+ case CreateActivation:
+ if (!node->castOperand<SymbolTable*>()->singletonScope()->isStillValid())
+ sinkCandidate();
+ escape(node->child1().node());
+ break;
+
+ case Check:
+ m_graph.doToChildren(
+ node,
+ [&] (Edge edge) {
+ if (edge.willNotHaveCheck())
+ return;
+
+ if (alreadyChecked(edge.useKind(), SpecObject))
+ return;
+
+ escape(edge.node());
+ });
+ break;
+
+ case MovHint:
+ case PutHint:
+ 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 GetClosureVar: {
+ Node* target = node->child1().node();
+ if (!target->isActivationAllocation())
+ escape(target);
+ break;
+ }
+
+ case PutClosureVar: {
+ Node* target = node->child1().node();
+ if (!target->isActivationAllocation())
+ escape(target);
+ escape(node->child2().node());
+ break;
+ }
+
+ case GetScope: {
+ Node* target = node->child1().node();
+ if (!target->isFunctionAllocation())
+ escape(target);
+ break;
+ }
+
+ case GetExecutable: {
+ Node* target = node->child1().node();
+ if (!target->isFunctionAllocation())
+ escape(target);
+ break;
+ }
+
+ case SkipScope: {
+ Node* target = node->child1().node();
+ if (!target->isActivationAllocation())
+ escape(target);
+ 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();
+ FrozenValue* symbolTable = escapee->cellOperand();
+ result = m_graph.addNode(
+ escapee->prediction(), Node::VarArg, MaterializeCreateActivation,
+ NodeOrigin(
+ escapee->origin.semantic,
+ where->origin.forExit),
+ OpInfo(data), OpInfo(symbolTable), 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);
+ PromotedHeapLocation symbolTable(ActivationSymbolTablePLoc, 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 ActivationSymbolTablePLoc: {
+ ASSERT(locations[i] == symbolTable);
+ 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;
+ }
+ }
+
+ CombinedLiveness m_combinedLiveness;
+ 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)
+
projects / apple / javascriptcore.git / blobdiff