diff options
Diffstat (limited to 'Source/JavaScriptCore/dfg/DFGCSEPhase.cpp')
| -rw-r--r-- | Source/JavaScriptCore/dfg/DFGCSEPhase.cpp | 733 |
1 files changed, 733 insertions, 0 deletions
diff --git a/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp b/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp new file mode 100644 index 000000000..a3c27ebc1 --- /dev/null +++ b/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp @@ -0,0 +1,733 @@ +/* + * Copyright (C) 2011 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 "DFGCSEPhase.h" + +#if ENABLE(DFG_JIT) + +#include "DFGGraph.h" +#include "DFGPhase.h" + +namespace JSC { namespace DFG { + +class CSEPhase : public Phase { +public: + CSEPhase(Graph& graph) + : Phase(graph, "common subexpression elimination") + { + // Replacements are used to implement local common subexpression elimination. + m_replacements.resize(m_graph.size()); + + for (unsigned i = 0; i < m_graph.size(); ++i) + m_replacements[i] = NoNode; + + for (unsigned i = 0; i < LastNodeId; ++i) + m_lastSeen[i] = NoNode; + } + + void run() + { + for (unsigned block = 0; block < m_graph.m_blocks.size(); ++block) + performBlockCSE(*m_graph.m_blocks[block]); + } + +private: + + NodeIndex canonicalize(NodeIndex nodeIndex) + { + if (nodeIndex == NoNode) + return NoNode; + + if (m_graph[nodeIndex].op == ValueToInt32) + nodeIndex = m_graph[nodeIndex].child1().index(); + + return nodeIndex; + } + NodeIndex canonicalize(NodeUse nodeUse) + { + return canonicalize(nodeUse.indexUnchecked()); + } + + // Computes where the search for a candidate for CSE should start. Don't call + // this directly; call startIndex() instead as it does logging in debug mode. + NodeIndex computeStartIndexForChildren(NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode) + { + const unsigned limit = 300; + + NodeIndex start = m_start; + if (m_compileIndex - start > limit) + start = m_compileIndex - limit; + + ASSERT(start >= m_start); + + NodeIndex child = canonicalize(child1); + if (child == NoNode) + return start; + + if (start < child) + start = child; + + child = canonicalize(child2); + if (child == NoNode) + return start; + + if (start < child) + start = child; + + child = canonicalize(child3); + if (child == NoNode) + return start; + + if (start < child) + start = child; + + return start; + } + + NodeIndex startIndexForChildren(NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode) + { + NodeIndex result = computeStartIndexForChildren(child1, child2, child3); +#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) + dataLog(" lookback %u: ", result); +#endif + return result; + } + + NodeIndex startIndex() + { + Node& node = m_graph[m_compileIndex]; + return startIndexForChildren( + node.child1().indexUnchecked(), + node.child2().indexUnchecked(), + node.child3().indexUnchecked()); + } + + NodeIndex endIndexForPureCSE() + { + NodeIndex result = m_lastSeen[m_graph[m_compileIndex].op & NodeIdMask]; + if (result == NoNode) + result = 0; + else + result++; + ASSERT(result <= m_compileIndex); +#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) + dataLog(" limit %u: ", result); +#endif + return result; + } + + NodeIndex pureCSE(Node& node) + { + NodeIndex child1 = canonicalize(node.child1()); + NodeIndex child2 = canonicalize(node.child2()); + NodeIndex child3 = canonicalize(node.child3()); + + NodeIndex start = startIndex(); + for (NodeIndex index = endIndexForPureCSE(); index-- > start;) { + Node& otherNode = m_graph[index]; + if (node.op != otherNode.op) + continue; + + if (node.arithNodeFlagsForCompare() != otherNode.arithNodeFlagsForCompare()) + continue; + + NodeIndex otherChild = canonicalize(otherNode.child1()); + if (otherChild == NoNode) + return index; + if (otherChild != child1) + continue; + + otherChild = canonicalize(otherNode.child2()); + if (otherChild == NoNode) + return index; + if (otherChild != child2) + continue; + + otherChild = canonicalize(otherNode.child3()); + if (otherChild == NoNode) + return index; + if (otherChild != child3) + continue; + + return index; + } + return NoNode; + } + + bool isPredictedNumerical(Node& node) + { + PredictedType left = m_graph[node.child1()].prediction(); + PredictedType right = m_graph[node.child2()].prediction(); + return isNumberPrediction(left) && isNumberPrediction(right); + } + + bool logicalNotIsPure(Node& node) + { + PredictedType prediction = m_graph[node.child1()].prediction(); + return isBooleanPrediction(prediction) || !prediction; + } + + bool byValIsPure(Node& node) + { + return m_graph[node.child2()].shouldSpeculateInteger() + && ((node.op == PutByVal || node.op == PutByValAlias) + ? isActionableMutableArrayPrediction(m_graph[node.child1()].prediction()) + : isActionableArrayPrediction(m_graph[node.child1()].prediction())); + } + + bool clobbersWorld(NodeIndex nodeIndex) + { + Node& node = m_graph[nodeIndex]; + if (node.op & NodeClobbersWorld) + return true; + if (!(node.op & NodeMightClobber)) + return false; + switch (node.op) { + case ValueAdd: + case CompareLess: + case CompareLessEq: + case CompareGreater: + case CompareGreaterEq: + case CompareEq: + return !isPredictedNumerical(node); + case LogicalNot: + return !logicalNotIsPure(node); + case GetByVal: + return !byValIsPure(node); + default: + ASSERT_NOT_REACHED(); + return true; // If by some oddity we hit this case in release build it's safer to have CSE assume the worst. + } + } + + NodeIndex impureCSE(Node& node) + { + NodeIndex child1 = canonicalize(node.child1()); + NodeIndex child2 = canonicalize(node.child2()); + NodeIndex child3 = canonicalize(node.child3()); + + NodeIndex start = startIndex(); + for (NodeIndex index = m_compileIndex; index-- > start;) { + Node& otherNode = m_graph[index]; + if (node.op == otherNode.op + && node.arithNodeFlagsForCompare() == otherNode.arithNodeFlagsForCompare()) { + NodeIndex otherChild = canonicalize(otherNode.child1()); + if (otherChild == NoNode) + return index; + if (otherChild == child1) { + otherChild = canonicalize(otherNode.child2()); + if (otherChild == NoNode) + return index; + if (otherChild == child2) { + otherChild = canonicalize(otherNode.child3()); + if (otherChild == NoNode) + return index; + if (otherChild == child3) + return index; + } + } + } + if (clobbersWorld(index)) + break; + } + return NoNode; + } + + NodeIndex globalVarLoadElimination(unsigned varNumber, JSGlobalObject* globalObject) + { + NodeIndex start = startIndexForChildren(); + for (NodeIndex index = m_compileIndex; index-- > start;) { + Node& node = m_graph[index]; + switch (node.op) { + case GetGlobalVar: + if (node.varNumber() == varNumber && codeBlock()->globalObjectFor(node.codeOrigin) == globalObject) + return index; + break; + case PutGlobalVar: + if (node.varNumber() == varNumber && codeBlock()->globalObjectFor(node.codeOrigin) == globalObject) + return node.child1().index(); + break; + default: + break; + } + if (clobbersWorld(index)) + break; + } + return NoNode; + } + + NodeIndex getByValLoadElimination(NodeIndex child1, NodeIndex child2) + { + NodeIndex start = startIndexForChildren(child1, child2); + for (NodeIndex index = m_compileIndex; index-- > start;) { + Node& node = m_graph[index]; + switch (node.op) { + case GetByVal: + if (!byValIsPure(node)) + return NoNode; + if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2)) + return index; + break; + case PutByVal: + case PutByValAlias: + if (!byValIsPure(node)) + return NoNode; + if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2)) + return node.child3().index(); + // We must assume that the PutByVal will clobber the location we're getting from. + // FIXME: We can do better; if we know that the PutByVal is accessing an array of a + // different type than the GetByVal, then we know that they won't clobber each other. + return NoNode; + case PutStructure: + case PutByOffset: + // GetByVal currently always speculates that it's accessing an + // array with an integer index, which means that it's impossible + // for a structure change or a put to property storage to affect + // the GetByVal. + break; + case ArrayPush: + // A push cannot affect previously existing elements in the array. + break; + default: + if (clobbersWorld(index)) + return NoNode; + break; + } + } + return NoNode; + } + + bool checkFunctionElimination(JSFunction* function, NodeIndex child1) + { + NodeIndex start = startIndexForChildren(child1); + for (NodeIndex index = endIndexForPureCSE(); index-- > start;) { + Node& node = m_graph[index]; + if (node.op == CheckFunction && node.child1() == child1 && node.function() == function) + return true; + } + return false; + } + + bool checkStructureLoadElimination(const StructureSet& structureSet, NodeIndex child1) + { + NodeIndex start = startIndexForChildren(child1); + for (NodeIndex index = m_compileIndex; index-- > start;) { + Node& node = m_graph[index]; + switch (node.op) { + case CheckStructure: + if (node.child1() == child1 + && structureSet.isSupersetOf(node.structureSet())) + return true; + break; + + case PutStructure: + if (node.child1() == child1 + && structureSet.contains(node.structureTransitionData().newStructure)) + return true; + if (structureSet.contains(node.structureTransitionData().previousStructure)) + return false; + break; + + case PutByOffset: + // Setting a property cannot change the structure. + break; + + case PutByVal: + case PutByValAlias: + if (byValIsPure(node)) { + // If PutByVal speculates that it's accessing an array with an + // integer index, then it's impossible for it to cause a structure + // change. + break; + } + return false; + + default: + if (clobbersWorld(index)) + return false; + break; + } + } + return false; + } + + NodeIndex getByOffsetLoadElimination(unsigned identifierNumber, NodeIndex child1) + { + NodeIndex start = startIndexForChildren(child1); + for (NodeIndex index = m_compileIndex; index-- > start;) { + Node& node = m_graph[index]; + switch (node.op) { + case GetByOffset: + if (node.child1() == child1 + && m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber) + return index; + break; + + case PutByOffset: + if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber) { + if (node.child2() == child1) + return node.child3().index(); + return NoNode; + } + break; + + case PutStructure: + // Changing the structure cannot change the outcome of a property get. + break; + + case PutByVal: + case PutByValAlias: + if (byValIsPure(node)) { + // If PutByVal speculates that it's accessing an array with an + // integer index, then it's impossible for it to cause a structure + // change. + break; + } + return NoNode; + + default: + if (clobbersWorld(index)) + return NoNode; + break; + } + } + return NoNode; + } + + NodeIndex getPropertyStorageLoadElimination(NodeIndex child1) + { + NodeIndex start = startIndexForChildren(child1); + for (NodeIndex index = m_compileIndex; index-- > start;) { + Node& node = m_graph[index]; + switch (node.op) { + case GetPropertyStorage: + if (node.child1() == child1) + return index; + break; + + case PutByOffset: + case PutStructure: + // Changing the structure or putting to the storage cannot + // change the property storage pointer. + break; + + case PutByVal: + case PutByValAlias: + if (byValIsPure(node)) { + // If PutByVal speculates that it's accessing an array with an + // integer index, then it's impossible for it to cause a structure + // change. + break; + } + return NoNode; + + default: + if (clobbersWorld(index)) + return NoNode; + break; + } + } + return NoNode; + } + + NodeIndex getIndexedPropertyStorageLoadElimination(NodeIndex child1, bool hasIntegerIndexPrediction) + { + NodeIndex start = startIndexForChildren(child1); + for (NodeIndex index = m_compileIndex; index-- > start;) { + Node& node = m_graph[index]; + switch (node.op) { + case GetIndexedPropertyStorage: { + PredictedType basePrediction = m_graph[node.child2()].prediction(); + bool nodeHasIntegerIndexPrediction = !(!(basePrediction & PredictInt32) && basePrediction); + if (node.child1() == child1 && hasIntegerIndexPrediction == nodeHasIntegerIndexPrediction) + return index; + break; + } + + case PutByOffset: + case PutStructure: + // Changing the structure or putting to the storage cannot + // change the property storage pointer. + break; + + case PutByValAlias: + // PutByValAlias can't change the indexed storage pointer + break; + + case PutByVal: + if (isFixedIndexedStorageObjectPrediction(m_graph[node.child1()].prediction()) && byValIsPure(node)) + break; + return NoNode; + + default: + if (clobbersWorld(index)) + return NoNode; + break; + } + } + return NoNode; + } + + NodeIndex getScopeChainLoadElimination(unsigned depth) + { + NodeIndex start = startIndexForChildren(); + for (NodeIndex index = endIndexForPureCSE(); index-- > start;) { + Node& node = m_graph[index]; + if (node.op == GetScopeChain + && node.scopeChainDepth() == depth) + return index; + } + return NoNode; + } + + void performSubstitution(NodeUse& child, bool addRef = true) + { + // Check if this operand is actually unused. + if (!child) + return; + + // Check if there is any replacement. + NodeIndex replacement = m_replacements[child.index()]; + if (replacement == NoNode) + return; + + child.setIndex(replacement); + + // There is definitely a replacement. Assert that the replacement does not + // have a replacement. + ASSERT(m_replacements[child.index()] == NoNode); + + if (addRef) + m_graph[child].ref(); + } + + void setReplacement(NodeIndex replacement) + { + if (replacement == NoNode) + return; + + // Be safe. Don't try to perform replacements if the predictions don't + // agree. + if (m_graph[m_compileIndex].prediction() != m_graph[replacement].prediction()) + return; + +#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) + dataLog(" Replacing @%u -> @%u", m_compileIndex, replacement); +#endif + + Node& node = m_graph[m_compileIndex]; + node.op = Phantom; + node.setRefCount(1); + + // At this point we will eliminate all references to this node. + m_replacements[m_compileIndex] = replacement; + } + + void eliminate() + { +#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) + dataLog(" Eliminating @%u", m_compileIndex); +#endif + + Node& node = m_graph[m_compileIndex]; + ASSERT(node.refCount() == 1); + ASSERT(node.mustGenerate()); + node.op = Phantom; + } + + void performNodeCSE(Node& node) + { + bool shouldGenerate = node.shouldGenerate(); + + if (node.op & NodeHasVarArgs) { + for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++) + performSubstitution(m_graph.m_varArgChildren[childIdx], shouldGenerate); + } else { + performSubstitution(node.children.child1(), shouldGenerate); + performSubstitution(node.children.child2(), shouldGenerate); + performSubstitution(node.children.child3(), shouldGenerate); + } + + if (!shouldGenerate) + return; + +#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) + dataLog(" %s @%u: ", Graph::opName(m_graph[m_compileIndex].op), m_compileIndex); +#endif + + // NOTE: there are some nodes that we deliberately don't CSE even though we + // probably could, like StrCat and ToPrimitive. That's because there is no + // evidence that doing CSE on these nodes would result in a performance + // progression. Hence considering these nodes in CSE would just mean that this + // code does more work with no win. Of course, we may want to reconsider this, + // since StrCat is trivially CSE-able. It's not trivially doable for + // ToPrimitive, but we could change that with some speculations if we really + // needed to. + + switch (node.op) { + + // Handle the pure nodes. These nodes never have any side-effects. + case BitAnd: + case BitOr: + case BitXor: + case BitRShift: + case BitLShift: + case BitURShift: + case ArithAdd: + case ArithSub: + case ArithMul: + case ArithMod: + case ArithDiv: + case ArithAbs: + case ArithMin: + case ArithMax: + case ArithSqrt: + case GetByteArrayLength: + case GetInt8ArrayLength: + case GetInt16ArrayLength: + case GetInt32ArrayLength: + case GetUint8ArrayLength: + case GetUint8ClampedArrayLength: + case GetUint16ArrayLength: + case GetUint32ArrayLength: + case GetFloat32ArrayLength: + case GetFloat64ArrayLength: + case GetCallee: + case GetStringLength: + case StringCharAt: + case StringCharCodeAt: + setReplacement(pureCSE(node)); + break; + + case GetArrayLength: + setReplacement(impureCSE(node)); + break; + + case GetScopeChain: + setReplacement(getScopeChainLoadElimination(node.scopeChainDepth())); + break; + + // Handle nodes that are conditionally pure: these are pure, and can + // be CSE'd, so long as the prediction is the one we want. + case ValueAdd: + case CompareLess: + case CompareLessEq: + case CompareGreater: + case CompareGreaterEq: + case CompareEq: { + if (isPredictedNumerical(node)) { + NodeIndex replacementIndex = pureCSE(node); + if (replacementIndex != NoNode && isPredictedNumerical(m_graph[replacementIndex])) + setReplacement(replacementIndex); + } + break; + } + + case LogicalNot: { + if (logicalNotIsPure(node)) { + NodeIndex replacementIndex = pureCSE(node); + if (replacementIndex != NoNode && logicalNotIsPure(m_graph[replacementIndex])) + setReplacement(replacementIndex); + } + break; + } + + // Finally handle heap accesses. These are not quite pure, but we can still + // optimize them provided that some subtle conditions are met. + case GetGlobalVar: + setReplacement(globalVarLoadElimination(node.varNumber(), codeBlock()->globalObjectFor(node.codeOrigin))); + break; + + case GetByVal: + if (byValIsPure(node)) + setReplacement(getByValLoadElimination(node.child1().index(), node.child2().index())); + break; + + case PutByVal: + if (byValIsPure(node) && getByValLoadElimination(node.child1().index(), node.child2().index()) != NoNode) + node.op = PutByValAlias; + break; + + case CheckStructure: + if (checkStructureLoadElimination(node.structureSet(), node.child1().index())) + eliminate(); + break; + + case CheckFunction: + if (checkFunctionElimination(node.function(), node.child1().index())) + eliminate(); + break; + + case GetIndexedPropertyStorage: { + PredictedType basePrediction = m_graph[node.child2()].prediction(); + bool nodeHasIntegerIndexPrediction = !(!(basePrediction & PredictInt32) && basePrediction); + setReplacement(getIndexedPropertyStorageLoadElimination(node.child1().index(), nodeHasIntegerIndexPrediction)); + break; + } + + case GetPropertyStorage: + setReplacement(getPropertyStorageLoadElimination(node.child1().index())); + break; + + case GetByOffset: + setReplacement(getByOffsetLoadElimination(m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber, node.child1().index())); + break; + + default: + // do nothing. + break; + } + + m_lastSeen[node.op & NodeIdMask] = m_compileIndex; +#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) + dataLog("\n"); +#endif + } + + void performBlockCSE(BasicBlock& block) + { + m_start = block.begin; + NodeIndex end = block.end; + for (m_compileIndex = m_start; m_compileIndex < end; ++m_compileIndex) + performNodeCSE(m_graph[m_compileIndex]); + } + + NodeIndex m_start; + NodeIndex m_compileIndex; + Vector<NodeIndex, 16> m_replacements; + FixedArray<NodeIndex, LastNodeId> m_lastSeen; +}; + +void performCSE(Graph& graph) +{ + runPhase<CSEPhase>(graph); +} + +} } // namespace JSC::DFG + +#endif // ENABLE(DFG_JIT) + + |