--- /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 "DFGPutStackSinkingPhase.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBlockMapInlines.h"
+#include "DFGGraph.h"
+#include "DFGInsertionSet.h"
+#include "DFGPhase.h"
+#include "DFGPreciseLocalClobberize.h"
+#include "DFGSSACalculator.h"
+#include "DFGValidate.h"
+#include "JSCInlines.h"
+#include "OperandsInlines.h"
+
+namespace JSC { namespace DFG {
+
+namespace {
+
+bool verbose = false;
+
+class PutStackSinkingPhase : public Phase {
+public:
+ PutStackSinkingPhase(Graph& graph)
+ : Phase(graph, "PutStack sinking")
+ {
+ }
+
+ bool run()
+ {
+ // FIXME: One of the problems of this approach is that it will create a duplicate Phi graph
+ // for sunken PutStacks in the presence of interesting control flow merges, and where the
+ // value being PutStack'd is also otherwise live in the DFG code. We could work around this
+ // by doing the sinking over CPS, or maybe just by doing really smart hoisting. It's also
+ // possible that the duplicate Phi graph can be deduplicated by LLVM. It would be best if we
+ // could observe that there is already a Phi graph in place that does what we want. In
+ // principle if we have a request to place a Phi at a particular place, we could just check
+ // if there is already a Phi that does what we want. Because PutStackSinkingPhase runs just
+ // after SSA conversion, we have almost a guarantee that the Phi graph we produce here would
+ // be trivially redundant to the one we already have.
+
+ // FIXME: This phase doesn't adequately use KillStacks. KillStack can be viewed as a def.
+ // This is mostly inconsequential; it would be a bug to have a local live at a KillStack.
+ // More important is that KillStack should swallow any deferral. After a KillStack, the
+ // local should behave like a TOP deferral because it would be invalid for anyone to trust
+ // the stack. It's not clear to me if this is important or not.
+ // https://bugs.webkit.org/show_bug.cgi?id=145296
+
+ if (verbose) {
+ dataLog("Graph before PutStack sinking:\n");
+ m_graph.dump();
+ }
+
+ SSACalculator ssaCalculator(m_graph);
+ InsertionSet insertionSet(m_graph);
+
+ // First figure out where various locals are live.
+ BlockMap<Operands<bool>> liveAtHead(m_graph);
+ BlockMap<Operands<bool>> liveAtTail(m_graph);
+
+ for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+ liveAtHead[block] = Operands<bool>(OperandsLike, block->variablesAtHead);
+ liveAtTail[block] = Operands<bool>(OperandsLike, block->variablesAtHead);
+
+ liveAtHead[block].fill(false);
+ liveAtTail[block].fill(false);
+ }
+
+ bool changed;
+ do {
+ changed = false;
+
+ for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+ BasicBlock* block = m_graph.block(blockIndex);
+ if (!block)
+ continue;
+
+ Operands<bool> live = liveAtTail[block];
+ for (unsigned nodeIndex = block->size(); nodeIndex--;) {
+ Node* node = block->at(nodeIndex);
+ if (verbose)
+ dataLog("Live at ", node, ": ", live, "\n");
+
+ auto escapeHandler = [&] (VirtualRegister operand) {
+ if (operand.isHeader())
+ return;
+ if (verbose)
+ dataLog(" ", operand, " is live at ", node, "\n");
+ live.operand(operand) = true;
+ };
+
+ // FIXME: This might mishandle LoadVarargs and ForwardVarargs. It might make us
+ // think that the locals being written are stack-live here. They aren't. This
+ // should be harmless since we overwrite them anyway, but still, it's sloppy.
+ // https://bugs.webkit.org/show_bug.cgi?id=145295
+ preciseLocalClobberize(
+ m_graph, node, escapeHandler, escapeHandler,
+ [&] (VirtualRegister operand, LazyNode source) {
+ RELEASE_ASSERT(source.isNode());
+
+ if (source.asNode() == node) {
+ // This is a load. Ignore it.
+ return;
+ }
+
+ RELEASE_ASSERT(node->op() == PutStack);
+ live.operand(operand) = false;
+ });
+ }
+
+ if (live == liveAtHead[block])
+ continue;
+
+ liveAtHead[block] = live;
+ changed = true;
+
+ for (BasicBlock* predecessor : block->predecessors) {
+ for (size_t i = live.size(); i--;)
+ liveAtTail[predecessor][i] |= live[i];
+ }
+ }
+
+ } while (changed);
+
+ // All of the arguments should be live at head of root. Note that we may find that some
+ // locals are live at head of root. This seems wrong but isn't. This will happen for example
+ // if the function accesses closure variable #42 for some other function and we either don't
+ // have variable #42 at all or we haven't set it at root, for whatever reason. Basically this
+ // arises since our aliasing for closure variables is conservatively based on variable number
+ // and ignores the owning symbol table. We should probably fix this eventually and make our
+ // aliasing more precise.
+ //
+ // For our purposes here, the imprecision in the aliasing is harmless. It just means that we
+ // may not do as much Phi pruning as we wanted.
+ for (size_t i = liveAtHead.atIndex(0).numberOfArguments(); i--;)
+ DFG_ASSERT(m_graph, nullptr, liveAtHead.atIndex(0).argument(i));
+
+ // Next identify where we would want to sink PutStacks to. We say that there is a deferred
+ // flush if we had a PutStack with a given FlushFormat but it hasn't been materialized yet.
+ // Deferrals have the following lattice; but it's worth noting that the TOP part of the
+ // lattice serves an entirely different purpose than the rest of the lattice: it just means
+ // that we're in a region of code where nobody should have been relying on the value. The
+ // rest of the lattice means that we either have a PutStack that is deferred (i.e. still
+ // needs to be executed) or there isn't one (because we've alraedy executed it).
+ //
+ // Bottom:
+ // Represented as DeadFlush.
+ // Means that all previous PutStacks have been executed so there is nothing deferred.
+ // During merging this is subordinate to the other kinds of deferrals, because it
+ // represents the fact that we've already executed all necessary PutStacks. This implies
+ // that there *had* been some PutStacks that we should have executed.
+ //
+ // Top:
+ // Represented as ConflictingFlush.
+ // Represents the fact that we know, via forward flow, that there isn't any value in the
+ // given local that anyone should have been relying on. This comes into play at the
+ // prologue (because in SSA form at the prologue no local has any value) or when we merge
+ // deferrals for different formats's. A lexical scope in which a local had some semantic
+ // meaning will by this point share the same format; if we had stores from different
+ // lexical scopes that got merged together then we may have a conflicting format. Hence
+ // a conflicting format proves that we're no longer in an area in which the variable was
+ // in scope. Note that this is all approximate and only precise enough to later answer
+ // questions pertinent to sinking. For example, this doesn't always detect when a local
+ // is no longer semantically relevant - we may well have a deferral from inside some
+ // inlined call survive outside of that inlined code, and this is generally OK. In the
+ // worst case it means that we might think that a deferral that is actually dead must
+ // still be executed. But we usually catch that with liveness. Liveness usually catches
+ // such cases, but that's not guaranteed since liveness is conservative.
+ //
+ // What Top does give us is detects situations where we both don't need to care about a
+ // deferral and there is no way that we could reason about it anyway. If we merged
+ // deferrals for different formats then we wouldn't know the format to use. So, we use
+ // Top in that case because that's also a case where we know that we can ignore the
+ // deferral.
+ //
+ // Deferral with a concrete format:
+ // Represented by format values other than DeadFlush or ConflictingFlush.
+ // Represents the fact that the original code would have done a PutStack but we haven't
+ // identified an operation that would have observed that PutStack.
+ //
+ // This code has some interesting quirks because of the fact that neither liveness nor
+ // deferrals are very precise. They are only precise enough to be able to correctly tell us
+ // when we may [sic] need to execute PutStacks. This means that they may report the need to
+ // execute a PutStack in cases where we actually don't really need it, and that's totally OK.
+ BlockMap<Operands<FlushFormat>> deferredAtHead(m_graph);
+ BlockMap<Operands<FlushFormat>> deferredAtTail(m_graph);
+
+ for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+ deferredAtHead[block] =
+ Operands<FlushFormat>(OperandsLike, block->variablesAtHead);
+ deferredAtTail[block] =
+ Operands<FlushFormat>(OperandsLike, block->variablesAtHead);
+ }
+
+ deferredAtHead.atIndex(0).fill(ConflictingFlush);
+
+ do {
+ changed = false;
+
+ for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+ Operands<FlushFormat> deferred = deferredAtHead[block];
+
+ for (Node* node : *block) {
+ if (verbose)
+ dataLog("Deferred at ", node, ":", deferred, "\n");
+
+ if (node->op() == GetStack) {
+ // A GetStack doesn't affect anything, since we know which local we are reading
+ // from.
+ continue;
+ }
+
+ auto escapeHandler = [&] (VirtualRegister operand) {
+ if (operand.isHeader())
+ return;
+ // We will materialize just before any reads.
+ deferred.operand(operand) = DeadFlush;
+ };
+
+ preciseLocalClobberize(
+ m_graph, node, escapeHandler, escapeHandler,
+ [&] (VirtualRegister operand, LazyNode source) {
+ RELEASE_ASSERT(source.isNode());
+
+ if (source.asNode() == node) {
+ // This is a load. Ignore it.
+ return;
+ }
+
+ deferred.operand(operand) = node->stackAccessData()->format;
+ });
+ }
+
+ if (deferred == deferredAtTail[block])
+ continue;
+
+ deferredAtTail[block] = deferred;
+ changed = true;
+
+ for (BasicBlock* successor : block->successors()) {
+ for (size_t i = deferred.size(); i--;) {
+ if (verbose)
+ dataLog("Considering ", VirtualRegister(deferred.operandForIndex(i)), " at ", pointerDump(block), "->", pointerDump(successor), ": ", deferred[i], " and ", deferredAtHead[successor][i], " merges to ");
+
+ deferredAtHead[successor][i] =
+ merge(deferredAtHead[successor][i], deferred[i]);
+
+ if (verbose)
+ dataLog(deferredAtHead[successor][i], "\n");
+ }
+ }
+ }
+
+ } while (changed);
+
+ // We wish to insert PutStacks at all of the materialization points, which are defined
+ // implicitly as the places where we set deferred to Dead while it was previously not Dead.
+ // To do this, we may need to build some Phi functions to handle stuff like this:
+ //
+ // Before:
+ //
+ // if (p)
+ // PutStack(r42, @x)
+ // else
+ // PutStack(r42, @y)
+ //
+ // After:
+ //
+ // if (p)
+ // Upsilon(@x, ^z)
+ // else
+ // Upsilon(@y, ^z)
+ // z: Phi()
+ // PutStack(r42, @z)
+ //
+ // This means that we have an SSACalculator::Variable for each local, and a Def is any
+ // PutStack in the original program. The original PutStacks will simply vanish.
+
+ Operands<SSACalculator::Variable*> operandToVariable(
+ OperandsLike, m_graph.block(0)->variablesAtHead);
+ Vector<VirtualRegister> indexToOperand;
+ for (size_t i = m_graph.block(0)->variablesAtHead.size(); i--;) {
+ VirtualRegister operand(m_graph.block(0)->variablesAtHead.operandForIndex(i));
+
+ SSACalculator::Variable* variable = ssaCalculator.newVariable();
+ operandToVariable.operand(operand) = variable;
+ ASSERT(indexToOperand.size() == variable->index());
+ indexToOperand.append(operand);
+ }
+
+ HashSet<Node*> putLocalsToSink;
+
+ for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+ for (Node* node : *block) {
+ switch (node->op()) {
+ case PutStack:
+ putLocalsToSink.add(node);
+ ssaCalculator.newDef(
+ operandToVariable.operand(node->stackAccessData()->local),
+ block, node->child1().node());
+ break;
+ case GetStack:
+ ssaCalculator.newDef(
+ operandToVariable.operand(node->stackAccessData()->local),
+ block, node);
+ break;
+ default:
+ break;
+ }
+ }
+ }
+
+ ssaCalculator.computePhis(
+ [&] (SSACalculator::Variable* variable, BasicBlock* block) -> Node* {
+ VirtualRegister operand = indexToOperand[variable->index()];
+
+ if (!liveAtHead[block].operand(operand))
+ return nullptr;
+
+ FlushFormat format = deferredAtHead[block].operand(operand);
+
+ // We could have an invalid deferral because liveness is imprecise.
+ if (!isConcrete(format))
+ return nullptr;
+
+ if (verbose)
+ dataLog("Adding Phi for ", operand, " at ", pointerDump(block), "\n");
+
+ Node* phiNode = m_graph.addNode(SpecHeapTop, Phi, NodeOrigin());
+ phiNode->mergeFlags(resultFor(format));
+ return phiNode;
+ });
+
+ Operands<Node*> mapping(OperandsLike, m_graph.block(0)->variablesAtHead);
+ Operands<FlushFormat> deferred;
+ for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+ mapping.fill(nullptr);
+
+ for (size_t i = mapping.size(); i--;) {
+ VirtualRegister operand(mapping.operandForIndex(i));
+
+ SSACalculator::Variable* variable = operandToVariable.operand(operand);
+ SSACalculator::Def* def = ssaCalculator.reachingDefAtHead(block, variable);
+ if (!def)
+ continue;
+
+ mapping.operand(operand) = def->value();
+ }
+
+ if (verbose)
+ dataLog("Mapping at top of ", pointerDump(block), ": ", mapping, "\n");
+
+ for (SSACalculator::Def* phiDef : ssaCalculator.phisForBlock(block)) {
+ VirtualRegister operand = indexToOperand[phiDef->variable()->index()];
+
+ insertionSet.insert(0, phiDef->value());
+
+ if (verbose)
+ dataLog(" Mapping ", operand, " to ", phiDef->value(), "\n");
+ mapping.operand(operand) = phiDef->value();
+ }
+
+ deferred = deferredAtHead[block];
+ for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
+ Node* node = block->at(nodeIndex);
+ if (verbose)
+ dataLog("Deferred at ", node, ":", deferred, "\n");
+
+ switch (node->op()) {
+ case PutStack: {
+ StackAccessData* data = node->stackAccessData();
+ VirtualRegister operand = data->local;
+ deferred.operand(operand) = data->format;
+ if (verbose)
+ dataLog(" Mapping ", operand, " to ", node->child1().node(), " at ", node, "\n");
+ mapping.operand(operand) = node->child1().node();
+ break;
+ }
+
+ case GetStack: {
+ StackAccessData* data = node->stackAccessData();
+ FlushFormat format = deferred.operand(data->local);
+ if (!isConcrete(format)) {
+ // This means there is no deferral. No deferral means that the most
+ // authoritative value for this stack slot is what is stored in the stack. So,
+ // keep the GetStack.
+ mapping.operand(data->local) = node;
+ break;
+ }
+
+ // We have a concrete deferral, which means a PutStack that hasn't executed yet. It
+ // would have stored a value with a certain format. That format must match our
+ // format. But more importantly, we can simply use the value that the PutStack would
+ // have stored and get rid of the GetStack.
+ DFG_ASSERT(m_graph, node, format == data->format);
+
+ Node* incoming = mapping.operand(data->local);
+ node->child1() = incoming->defaultEdge();
+ node->convertToIdentity();
+ break;
+ }
+
+ default: {
+ auto escapeHandler = [&] (VirtualRegister operand) {
+ if (operand.isHeader())
+ return;
+
+ FlushFormat format = deferred.operand(operand);
+ if (!isConcrete(format))
+ return;
+
+ // Gotta insert a PutStack.
+ if (verbose)
+ dataLog("Inserting a PutStack for ", operand, " at ", node, "\n");
+
+ Node* incoming = mapping.operand(operand);
+ DFG_ASSERT(m_graph, node, incoming);
+
+ insertionSet.insertNode(
+ nodeIndex, SpecNone, PutStack, node->origin,
+ OpInfo(m_graph.m_stackAccessData.add(operand, format)),
+ Edge(incoming, useKindFor(format)));
+
+ deferred.operand(operand) = DeadFlush;
+ };
+
+ preciseLocalClobberize(
+ m_graph, node, escapeHandler, escapeHandler,
+ [&] (VirtualRegister, LazyNode) { });
+ break;
+ } }
+ }
+
+ NodeAndIndex terminal = block->findTerminal();
+ size_t upsilonInsertionPoint = terminal.index;
+ NodeOrigin upsilonOrigin = terminal.node->origin;
+ for (BasicBlock* successorBlock : block->successors()) {
+ for (SSACalculator::Def* phiDef : ssaCalculator.phisForBlock(successorBlock)) {
+ Node* phiNode = phiDef->value();
+ SSACalculator::Variable* variable = phiDef->variable();
+ VirtualRegister operand = indexToOperand[variable->index()];
+ if (verbose)
+ dataLog("Creating Upsilon for ", operand, " at ", pointerDump(block), "->", pointerDump(successorBlock), "\n");
+ FlushFormat format = deferredAtHead[successorBlock].operand(operand);
+ DFG_ASSERT(m_graph, nullptr, isConcrete(format));
+ UseKind useKind = useKindFor(format);
+
+ // We need to get a value for the stack slot. This phase doesn't really have a
+ // good way of determining if a stack location got clobbered. It just knows if
+ // there is a deferral. The lack of a deferral might mean that a PutStack or
+ // GetStack had never happened, or it might mean that the value was read, or
+ // that it was written. It's OK for us to make some bad decisions here, since
+ // GCSE will clean it up anyway.
+ Node* incoming;
+ if (isConcrete(deferred.operand(operand))) {
+ incoming = mapping.operand(operand);
+ DFG_ASSERT(m_graph, phiNode, incoming);
+ } else {
+ // Issue a GetStack to get the value. This might introduce some redundancy
+ // into the code, but if it's bad enough, GCSE will clean it up.
+ incoming = insertionSet.insertNode(
+ upsilonInsertionPoint, SpecNone, GetStack, upsilonOrigin,
+ OpInfo(m_graph.m_stackAccessData.add(operand, format)));
+ incoming->setResult(resultFor(format));
+ }
+
+ insertionSet.insertNode(
+ upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
+ OpInfo(phiNode), Edge(incoming, useKind));
+ }
+ }
+
+ insertionSet.execute(block);
+ }
+
+ // Finally eliminate the sunken PutStacks by turning them into Checks. This keeps whatever
+ // type check they were doing. Also prepend KillStacks to them to ensure that we know that
+ // the relevant value was *not* stored to the stack.
+ for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+ for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
+ Node* node = block->at(nodeIndex);
+
+ if (!putLocalsToSink.contains(node))
+ continue;
+
+ insertionSet.insertNode(
+ nodeIndex, SpecNone, KillStack, node->origin, OpInfo(node->stackAccessData()->local.offset()));
+ node->remove();
+ }
+
+ insertionSet.execute(block);
+ }
+
+ if (verbose) {
+ dataLog("Graph after PutStack sinking:\n");
+ m_graph.dump();
+ }
+
+ return true;
+ }
+};
+
+} // anonymous namespace
+
+bool performPutStackSinking(Graph& graph)
+{
+ SamplingRegion samplingRegion("DFG PutStack Sinking Phase");
+ return runPhase<PutStackSinkingPhase>(graph);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
projects / apple / javascriptcore.git / blobdiff