diff options
author | Lorry Tar Creator <lorry-tar-importer@lorry> | 2016-04-10 09:28:39 +0000 |
---|---|---|
committer | Lorry Tar Creator <lorry-tar-importer@lorry> | 2016-04-10 09:28:39 +0000 |
commit | 32761a6cee1d0dee366b885b7b9c777e67885688 (patch) | |
tree | d6bec92bebfb216f4126356e55518842c2f476a1 /Source/JavaScriptCore/dfg/DFGPutStackSinkingPhase.cpp | |
parent | a4e969f4965059196ca948db781e52f7cfebf19e (diff) | |
download | WebKitGtk-tarball-32761a6cee1d0dee366b885b7b9c777e67885688.tar.gz |
webkitgtk-2.4.11webkitgtk-2.4.11
Diffstat (limited to 'Source/JavaScriptCore/dfg/DFGPutStackSinkingPhase.cpp')
-rw-r--r-- | Source/JavaScriptCore/dfg/DFGPutStackSinkingPhase.cpp | 593 |
1 files changed, 0 insertions, 593 deletions
diff --git a/Source/JavaScriptCore/dfg/DFGPutStackSinkingPhase.cpp b/Source/JavaScriptCore/dfg/DFGPutStackSinkingPhase.cpp deleted file mode 100644 index 6b0bb0763..000000000 --- a/Source/JavaScriptCore/dfg/DFGPutStackSinkingPhase.cpp +++ /dev/null @@ -1,593 +0,0 @@ -/* - * 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 B3. 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.ensureDominators(); - - 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"); - - Vector<VirtualRegister, 4> reads; - Vector<VirtualRegister, 4> writes; - auto escapeHandler = [&] (VirtualRegister operand) { - if (operand.isHeader()) - return; - if (verbose) - dataLog(" ", operand, " is live at ", node, "\n"); - reads.append(operand); - }; - - auto writeHandler = [&] (VirtualRegister operand) { - RELEASE_ASSERT(node->op() == PutStack || node->op() == LoadVarargs || node->op() == ForwardVarargs); - writes.append(operand); - }; - - preciseLocalClobberize( - m_graph, node, escapeHandler, writeHandler, - [&] (VirtualRegister, LazyNode) { }); - - for (VirtualRegister operand : writes) - live.operand(operand) = false; - for (VirtualRegister operand : reads) - live.operand(operand) = true; - } - - 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. - // - // We need to be precise about liveness in this phase because not doing so - // could cause us to insert a PutStack before a node we thought may escape a - // value that it doesn't really escape. Sinking this PutStack above such a node may - // cause us to insert a GetStack that we forward to the Phi we're feeding into the - // sunken PutStack. Inserting such a GetStack could cause us to load garbage and - // can confuse the AI to claim untrue things (like that the program will exit when - // it really won't). - 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) { - // Handle the case that the input doesn't match our requirements. This is - // really a bug, but it's a benign one if we simply don't run this phase. - // It usually arises because of patterns like: - // - // if (thing) - // PutStack() - // ... - // if (thing) - // GetStack() - // - // Or: - // - // if (never happens) - // GetStack() - // - // Because this phase runs early in SSA, it should be sensible to enforce - // that no such code pattern has arisen yet. So, when validation is - // enabled, we assert that we aren't seeing this. But with validation - // disabled we silently let this fly and we just abort this phase. - // FIXME: Get rid of all remaining cases of conflicting GetStacks. - // https://bugs.webkit.org/show_bug.cgi?id=150398 - - bool isConflicting = - deferred.operand(node->stackAccessData()->local) == ConflictingFlush; - - if (validationEnabled()) - DFG_ASSERT(m_graph, node, !isConflicting); - - if (isConflicting) { - // Oh noes! Abort!! - return false; - } - - // A GetStack doesn't affect anything, since we know which local we are reading - // from. - continue; - } else if (node->op() == PutStack) { - VirtualRegister operand = node->stackAccessData()->local; - deferred.operand(operand) = node->stackAccessData()->format; - 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; - }; - - auto writeHandler = [&] (VirtualRegister operand) { - RELEASE_ASSERT(node->op() == LoadVarargs || node->op() == ForwardVarargs); - deferred.operand(operand) = DeadFlush; - }; - - preciseLocalClobberize( - m_graph, node, escapeHandler, writeHandler, - [&] (VirtualRegister, LazyNode) { }); - } - - 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*> putStacksToSink; - - for (BasicBlock* block : m_graph.blocksInNaturalOrder()) { - for (Node* node : *block) { - switch (node->op()) { - case PutStack: - putStacksToSink.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; - }; - - auto writeHandler = [&] (VirtualRegister operand) { - // LoadVarargs and ForwardVarargs are unconditional writes to the stack - // locations they claim to write to. They do not read from the stack - // locations they write to. This makes those stack locations dead right - // before a LoadVarargs/ForwardVarargs. This means we should never sink - // PutStacks right to this point. - RELEASE_ASSERT(node->op() == LoadVarargs || node->op() == ForwardVarargs); - deferred.operand(operand) = DeadFlush; - }; - - preciseLocalClobberize( - m_graph, node, escapeHandler, writeHandler, - [&] (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 = uncheckedUseKindFor(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 (!putStacksToSink.contains(node)) - continue; - - node->remove(); - } - } - - 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) - |