--- /dev/null
+/*
+ * Copyright (C) 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. AND ITS CONTRIBUTORS ``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 ITS 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 "DFGStoreBarrierInsertionPhase.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGAbstractInterpreterInlines.h"
+#include "DFGBlockMapInlines.h"
+#include "DFGDoesGC.h"
+#include "DFGGraph.h"
+#include "DFGInPlaceAbstractState.h"
+#include "DFGInsertionSet.h"
+#include "DFGPhase.h"
+#include "JSCInlines.h"
+#include <wtf/CommaPrinter.h>
+#include <wtf/HashSet.h>
+
+namespace JSC { namespace DFG {
+
+namespace {
+
+bool verbose = false;
+
+enum class PhaseMode {
+ // Does only a local analysis for store barrier insertion and assumes that pointers live
+ // from predecessor blocks may need barriers. Assumes CPS conventions. Does not use AI for
+ // eliminating store barriers, but does a best effort to eliminate barriers when you're
+ // storing a non-cell value by using Node::result() and by looking at constants. The local
+ // analysis is based on GC epochs, so it will eliminate a lot of locally redundant barriers.
+ Fast,
+
+ // Does a global analysis for store barrier insertion. Reuses the GC-epoch-based analysis
+ // used by Fast, but adds a conservative merge rule for propagating information from one
+ // block to the next. This will ensure for example that if a value V coming from multiple
+ // predecessors in B didn't need any more barriers at the end of each predecessor (either
+ // because it was the last allocated object in that predecessor or because it just had a
+ // barrier executed), then until we hit another GC point in B, we won't need another barrier
+ // on V. Uses AI for eliminating barriers when we know that the value being stored is not a
+ // cell. Assumes SSA conventions.
+ Global
+};
+
+template<PhaseMode mode>
+class StoreBarrierInsertionPhase : public Phase {
+public:
+ StoreBarrierInsertionPhase(Graph& graph)
+ : Phase(graph, mode == PhaseMode::Fast ? "fast store barrier insertion" : "global store barrier insertion")
+ , m_insertionSet(graph)
+ {
+ }
+
+ bool run()
+ {
+ if (verbose) {
+ dataLog("Starting store barrier insertion:\n");
+ m_graph.dump();
+ }
+
+ switch (mode) {
+ case PhaseMode::Fast: {
+ DFG_ASSERT(m_graph, nullptr, m_graph.m_form != SSA);
+
+ m_graph.clearEpochs();
+ for (BasicBlock* block : m_graph.blocksInNaturalOrder())
+ handleBlock(block);
+ return true;
+ }
+
+ case PhaseMode::Global: {
+ DFG_ASSERT(m_graph, nullptr, m_graph.m_form == SSA);
+
+ m_state = std::make_unique<InPlaceAbstractState>(m_graph);
+ m_interpreter = std::make_unique<AbstractInterpreter<InPlaceAbstractState>>(m_graph, *m_state);
+
+ m_isConverged = false;
+
+ // First run the analysis. Inside basic blocks we use an epoch-based analysis that
+ // is very precise. At block boundaries, we just propagate which nodes may need a
+ // barrier. This gives us a very nice bottom->top fixpoint: we start out assuming
+ // that no node needs any barriers at block boundaries, and then we converge
+ // towards believing that all nodes need barriers. "Needing a barrier" is like
+ // saying that the node is in a past epoch. "Not needing a barrier" is like saying
+ // that the node is in the current epoch.
+ m_stateAtHead = std::make_unique<BlockMap<HashSet<Node*>>>(m_graph);
+ m_stateAtTail = std::make_unique<BlockMap<HashSet<Node*>>>(m_graph);
+
+ BlockList postOrder = m_graph.blocksInPostOrder();
+
+ bool changed = true;
+ while (changed) {
+ changed = false;
+
+ // Intentional backwards loop because we are using RPO.
+ for (unsigned blockIndex = postOrder.size(); blockIndex--;) {
+ BasicBlock* block = postOrder[blockIndex];
+
+ if (!handleBlock(block)) {
+ // If the block didn't finish, then it cannot affect the fixpoint.
+ continue;
+ }
+
+ // Construct the state-at-tail based on the epochs of live nodes and the
+ // current epoch. We grow state-at-tail monotonically to ensure convergence.
+ bool thisBlockChanged = false;
+ for (Node* node : block->ssa->liveAtTail) {
+ if (node->epoch() != m_currentEpoch) {
+ // If the node is older than the current epoch, then we may need to
+ // run a barrier on it in the future. So, add it to the state.
+ thisBlockChanged |= m_stateAtTail->at(block).add(node).isNewEntry;
+ }
+ }
+
+ if (!thisBlockChanged) {
+ // This iteration didn't learn anything new about this block.
+ continue;
+ }
+
+ // Changed things. Make sure that we loop one more time.
+ changed = true;
+
+ for (BasicBlock* successor : block->successors()) {
+ for (Node* node : m_stateAtTail->at(block))
+ m_stateAtHead->at(successor).add(node);
+ }
+ }
+ }
+
+ // Tell handleBlock() that it's time to actually insert barriers for real.
+ m_isConverged = true;
+
+ for (BasicBlock* block : m_graph.blocksInNaturalOrder())
+ handleBlock(block);
+
+ return true;
+ } }
+
+ RELEASE_ASSERT_NOT_REACHED();
+ return false;
+ }
+
+private:
+ bool handleBlock(BasicBlock* block)
+ {
+ if (verbose) {
+ dataLog("Dealing with block ", pointerDump(block), "\n");
+ if (reallyInsertBarriers())
+ dataLog(" Really inserting barriers.\n");
+ }
+
+ m_currentEpoch = Epoch::first();
+
+ if (mode == PhaseMode::Global) {
+ if (!block->cfaHasVisited)
+ return false;
+ m_state->beginBasicBlock(block);
+
+ for (Node* node : block->ssa->liveAtHead) {
+ if (m_stateAtHead->at(block).contains(node)) {
+ // If previous blocks tell us that this node may need a barrier in the
+ // future, then put it in the ancient primordial epoch. This forces us to
+ // emit a barrier on any possibly-cell store, regardless of the epoch of the
+ // stored value.
+ node->setEpoch(Epoch());
+ } else {
+ // If previous blocks aren't requiring us to run a barrier on this node,
+ // then put it in the current epoch. This means that we will skip barriers
+ // on this node so long as we don't allocate. It also means that we won't
+ // run barriers on stores to on one such node into another such node. That's
+ // fine, because nodes would be excluded from the state set if at the tails
+ // of all predecessors they always had the current epoch.
+ node->setEpoch(m_currentEpoch);
+ }
+ }
+ }
+
+ bool result = true;
+
+ for (m_nodeIndex = 0; m_nodeIndex < block->size(); ++m_nodeIndex) {
+ m_node = block->at(m_nodeIndex);
+
+ if (verbose) {
+ dataLog(
+ " ", m_currentEpoch, ": Looking at node ", m_node, " with children: ");
+ CommaPrinter comma;
+ m_graph.doToChildren(
+ m_node,
+ [&] (Edge edge) {
+ dataLog(comma, edge, " (", edge->epoch(), ")");
+ });
+ dataLog("\n");
+ }
+
+ if (mode == PhaseMode::Global) {
+ // Execute edges separately because we don't want to insert barriers if the
+ // operation doing the store does a check that ensures that the child is not
+ // a cell.
+ m_interpreter->startExecuting();
+ m_interpreter->executeEdges(m_node);
+ }
+
+ switch (m_node->op()) {
+ case PutByValDirect:
+ case PutByVal:
+ case PutByValAlias: {
+ switch (m_node->arrayMode().modeForPut().type()) {
+ case Array::Contiguous:
+ case Array::ArrayStorage:
+ case Array::SlowPutArrayStorage: {
+ Edge child1 = m_graph.varArgChild(m_node, 0);
+ Edge child3 = m_graph.varArgChild(m_node, 2);
+ considerBarrier(child1, child3);
+ break;
+ }
+ default:
+ break;
+ }
+ break;
+ }
+
+ case ArrayPush: {
+ switch (m_node->arrayMode().type()) {
+ case Array::Contiguous:
+ case Array::ArrayStorage:
+ considerBarrier(m_node->child1(), m_node->child2());
+ break;
+ default:
+ break;
+ }
+ break;
+ }
+
+ case PutStructure: {
+ considerBarrier(m_node->child1());
+ break;
+ }
+
+ case PutClosureVar:
+ case PutToArguments:
+ case PutById:
+ case PutByIdFlush:
+ case PutByIdDirect:
+ case MultiPutByOffset: {
+ considerBarrier(m_node->child1(), m_node->child2());
+ break;
+ }
+
+ case PutByOffset: {
+ considerBarrier(m_node->child2(), m_node->child3());
+ break;
+ }
+
+ case PutGlobalVar: {
+ considerBarrier(m_node->child1(), m_node->child2());
+ break;
+ }
+
+ default:
+ break;
+ }
+
+ if (doesGC(m_graph, m_node))
+ m_currentEpoch.bump();
+
+ switch (m_node->op()) {
+ case NewObject:
+ case NewArray:
+ case NewArrayWithSize:
+ case NewArrayBuffer:
+ case NewTypedArray:
+ case NewRegexp:
+ case MaterializeNewObject:
+ case MaterializeCreateActivation:
+ case NewStringObject:
+ case MakeRope:
+ case CreateActivation:
+ case CreateDirectArguments:
+ case CreateScopedArguments:
+ case CreateClonedArguments:
+ case NewFunction:
+ // Nodes that allocate get to set their epoch because for those nodes we know
+ // that they will be the newest object in the heap.
+ m_node->setEpoch(m_currentEpoch);
+ break;
+
+ case AllocatePropertyStorage:
+ case ReallocatePropertyStorage:
+ // These allocate but then run their own barrier.
+ insertBarrier(m_nodeIndex + 1, m_node->child1().node());
+ m_node->setEpoch(Epoch());
+ break;
+
+ case Upsilon:
+ m_node->phi()->setEpoch(m_node->epoch());
+ m_node->setEpoch(Epoch());
+ break;
+
+ default:
+ // For nodes that aren't guaranteed to allocate, we say that their return value
+ // (if there is one) could be arbitrarily old.
+ m_node->setEpoch(Epoch());
+ break;
+ }
+
+ if (verbose) {
+ dataLog(
+ " ", m_currentEpoch, ": Done with node ", m_node, " (", m_node->epoch(),
+ ") with children: ");
+ CommaPrinter comma;
+ m_graph.doToChildren(
+ m_node,
+ [&] (Edge edge) {
+ dataLog(comma, edge, " (", edge->epoch(), ")");
+ });
+ dataLog("\n");
+ }
+
+ if (mode == PhaseMode::Global) {
+ if (!m_interpreter->executeEffects(m_nodeIndex, m_node)) {
+ result = false;
+ break;
+ }
+ }
+ }
+
+ if (mode == PhaseMode::Global)
+ m_state->reset();
+
+ if (reallyInsertBarriers())
+ m_insertionSet.execute(block);
+
+ return result;
+ }
+
+ void considerBarrier(Edge base, Edge child)
+ {
+ if (verbose)
+ dataLog(" Considering adding barrier ", base, " => ", child, "\n");
+
+ // We don't need a store barrier if the child is guaranteed to not be a cell.
+ switch (mode) {
+ case PhaseMode::Fast: {
+ // Don't try too hard because it's too expensive to run AI.
+ if (child->hasConstant()) {
+ if (!child->asJSValue().isCell()) {
+ if (verbose)
+ dataLog(" Rejecting because of constant type.\n");
+ return;
+ }
+ } else {
+ switch (child->result()) {
+ case NodeResultNumber:
+ case NodeResultDouble:
+ case NodeResultInt32:
+ case NodeResultInt52:
+ case NodeResultBoolean:
+ if (verbose)
+ dataLog(" Rejecting because of result type.\n");
+ return;
+ default:
+ break;
+ }
+ }
+ break;
+ }
+
+ case PhaseMode::Global: {
+ // Go into rage mode to eliminate any chance of a barrier with a non-cell child. We
+ // can afford to keep around AI in Global mode.
+ if (!m_interpreter->needsTypeCheck(child, ~SpecCell)) {
+ if (verbose)
+ dataLog(" Rejecting because of AI type.\n");
+ return;
+ }
+ break;
+ } }
+
+ // We don't need a store barrier if the base is at least as new as the child. For
+ // example this won't need a barrier:
+ //
+ // var o = {}
+ // var p = {}
+ // p.f = o
+ //
+ // This is stronger than the currentEpoch rule in considerBarrier(Edge), because it will
+ // also eliminate barriers in cases like this:
+ //
+ // var o = {} // o.epoch = 1, currentEpoch = 1
+ // var p = {} // o.epoch = 1, p.epoch = 2, currentEpoch = 2
+ // var q = {} // o.epoch = 1, p.epoch = 2, q.epoch = 3, currentEpoch = 3
+ // p.f = o // p.epoch >= o.epoch
+ //
+ // This relationship works because if it holds then we are in one of the following
+ // scenarios. Note that we don't know *which* of these scenarios we are in, but it's
+ // one of them (though without loss of generality, you can replace "a GC happened" with
+ // "many GCs happened").
+ //
+ // 1) There is no GC between the allocation/last-barrier of base, child and now. Then
+ // we definitely don't need a barrier.
+ //
+ // 2) There was a GC after child was allocated but before base was allocated. Then we
+ // don't need a barrier, because base is still a new object.
+ //
+ // 3) There was a GC after both child and base were allocated. Then they are both old.
+ // We don't need barriers on stores of old into old. Note that in this case it
+ // doesn't matter if there was also a GC between the allocation of child and base.
+ //
+ // Note that barriers will lift an object into the current epoch. This is sort of weird.
+ // It means that later if you store that object into some other object, and that other
+ // object was previously newer object, you'll think that you need a barrier. We could
+ // avoid this by tracking allocation epoch and barrier epoch separately. For now I think
+ // that this would be overkill. But this does mean that there are the following
+ // possibilities when this relationship holds:
+ //
+ // 4) Base is allocated first. A GC happens and base becomes old. Then we allocate
+ // child. (Note that alternatively the GC could happen during the allocation of
+ // child.) Then we run a barrier on base. Base will appear to be as new as child
+ // (same epoch). At this point, we don't need another barrier on base.
+ //
+ // 5) Base is allocated first. Then we allocate child. Then we run a GC. Then we run a
+ // barrier on base. Base will appear newer than child. We don't need a barrier
+ // because both objects are old.
+ //
+ // Something we watch out for here is that the null epoch is a catch-all for objects
+ // allocated before we did any epoch tracking. Two objects being in the null epoch
+ // means that we don't know their epoch relationship.
+ if (!!base->epoch() && base->epoch() >= child->epoch()) {
+ if (verbose)
+ dataLog(" Rejecting because of epoch ordering.\n");
+ return;
+ }
+
+ considerBarrier(base);
+ }
+
+ void considerBarrier(Edge base)
+ {
+ if (verbose)
+ dataLog(" Considering adding barrier on ", base, "\n");
+
+ // We don't need a store barrier if the epoch of the base is identical to the current
+ // epoch. That means that we either just allocated the object and so it's guaranteed to
+ // be in newgen, or we just ran a barrier on it so it's guaranteed to be remembered
+ // already.
+ if (base->epoch() == m_currentEpoch) {
+ if (verbose)
+ dataLog(" Rejecting because it's in the current epoch.\n");
+ return;
+ }
+
+ if (verbose)
+ dataLog(" Inserting barrier.\n");
+ insertBarrier(m_nodeIndex, base.node());
+ }
+
+ void insertBarrier(unsigned nodeIndex, Node* base)
+ {
+ // If we're in global mode, we should only insert the barriers once we have converged.
+ if (!reallyInsertBarriers())
+ return;
+
+ // FIXME: We could support StoreBarrier(UntypedUse:). That would be sort of cool.
+ // But right now we don't need it.
+ m_insertionSet.insertNode(
+ nodeIndex, SpecNone, StoreBarrier, m_node->origin, Edge(base, CellUse));
+
+ base->setEpoch(m_currentEpoch);
+ }
+
+ bool reallyInsertBarriers()
+ {
+ return mode == PhaseMode::Fast || m_isConverged;
+ }
+
+ InsertionSet m_insertionSet;
+ Epoch m_currentEpoch;
+ unsigned m_nodeIndex;
+ Node* m_node;
+
+ // Things we only use in Global mode.
+ std::unique_ptr<InPlaceAbstractState> m_state;
+ std::unique_ptr<AbstractInterpreter<InPlaceAbstractState>> m_interpreter;
+ std::unique_ptr<BlockMap<HashSet<Node*>>> m_stateAtHead;
+ std::unique_ptr<BlockMap<HashSet<Node*>>> m_stateAtTail;
+ bool m_isConverged;
+};
+
+} // anonymous namespace
+
+bool performFastStoreBarrierInsertion(Graph& graph)
+{
+ SamplingRegion samplingRegion("DFG Fast Store Barrier Insertion Phase");
+ return runPhase<StoreBarrierInsertionPhase<PhaseMode::Fast>>(graph);
+}
+
+bool performGlobalStoreBarrierInsertion(Graph& graph)
+{
+ SamplingRegion samplingRegion("DFG Global Store Barrier Insertion Phase");
+ return runPhase<StoreBarrierInsertionPhase<PhaseMode::Global>>(graph);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
projects / apple / javascriptcore.git / blobdiff