| /* |
| * 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(); |
| } |
| |
| m_graph.m_dominators.computeIfNecessary(m_graph); |
| |
| 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); |
| } |
| |
| for (unsigned local = deferredAtHead.atIndex(0).numberOfLocals(); local--;) |
| deferredAtHead.atIndex(0).local(local) = 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) { |
| DFG_ASSERT( |
| m_graph, node, |
| deferred.operand(node->stackAccessData()->local) != ConflictingFlush); |
| |
| // A GetStack doesn't affect anything, since we know which local we are reading |
| // from. |
| continue; |
| } |
| |
| auto escapeHandler = [&] (VirtualRegister operand) { |
| if (verbose) |
| dataLog("For ", node, " escaping ", operand, "\n"); |
| 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, block->at(0)->origin.withInvalidExit()); |
| 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)) { |
| DFG_ASSERT( |
| m_graph, node, |
| deferred.operand(data->local) != ConflictingFlush); |
| |
| // 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 (verbose) |
| dataLog("For ", node, " escaping ", operand, "\n"); |
| |
| if (operand.isHeader()) |
| return; |
| |
| FlushFormat format = deferred.operand(operand); |
| if (!isConcrete(format)) { |
| // It's dead now, rather than conflicting. |
| deferred.operand(operand) = DeadFlush; |
| 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, uncheckedUseKindFor(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. |
| for (BasicBlock* block : m_graph.blocksInNaturalOrder()) { |
| for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) { |
| Node* node = block->at(nodeIndex); |
| |
| if (!putLocalsToSink.contains(node)) |
| continue; |
| |
| 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) |
| |
