diff options
Diffstat (limited to 'Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.cpp')
| -rw-r--r-- | Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.cpp | 368 |
1 files changed, 368 insertions, 0 deletions
diff --git a/Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.cpp b/Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.cpp new file mode 100644 index 000000000..2f06646aa --- /dev/null +++ b/Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.cpp @@ -0,0 +1,368 @@ +/* + * Copyright (C) 2013 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 "DFGBackwardsPropagationPhase.h" + +#if ENABLE(DFG_JIT) + +#include "DFGBasicBlockInlines.h" +#include "DFGGraph.h" +#include "DFGPhase.h" +#include "Operations.h" + +namespace JSC { namespace DFG { + +class BackwardsPropagationPhase : public Phase { +public: + BackwardsPropagationPhase(Graph& graph) + : Phase(graph, "backwards propagation") + { + } + + bool run() + { + for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) { + BasicBlock* block = m_graph.m_blocks[blockIndex].get(); + if (!block) + continue; + + // Prevent a tower of overflowing additions from creating a value that is out of the + // safe 2^48 range. + m_allowNestedOverflowingAdditions = block->size() < (1 << 16); + + for (unsigned indexInBlock = block->size(); indexInBlock--;) + propagate(block->at(indexInBlock)); + } + + return true; + } + +private: + bool isNotNegZero(Node* node) + { + if (!m_graph.isNumberConstant(node)) + return false; + double value = m_graph.valueOfNumberConstant(node); + return (value || 1.0 / value > 0.0); + } + + bool isNotPosZero(Node* node) + { + if (!m_graph.isNumberConstant(node)) + return false; + double value = m_graph.valueOfNumberConstant(node); + return (value || 1.0 / value < 0.0); + } + + // Tests if the absolute value is strictly less than the power of two. + template<int power> + bool isWithinPowerOfTwoForConstant(Node* node) + { + JSValue immediateValue = node->valueOfJSConstant(codeBlock()); + if (!immediateValue.isNumber()) + return false; + double immediate = immediateValue.asNumber(); + return immediate > -(static_cast<int64_t>(1) << power) && immediate < (static_cast<int64_t>(1) << power); + } + + template<int power> + bool isWithinPowerOfTwoNonRecursive(Node* node) + { + if (node->op() != JSConstant) + return false; + return isWithinPowerOfTwoForConstant<power>(node); + } + + template<int power> + bool isWithinPowerOfTwo(Node* node) + { + switch (node->op()) { + case JSConstant: { + return isWithinPowerOfTwoForConstant<power>(node); + } + + case BitAnd: { + if (power > 31) + return true; + + return isWithinPowerOfTwoNonRecursive<power>(node->child1().node()) + || isWithinPowerOfTwoNonRecursive<power>(node->child2().node()); + } + + case BitOr: + case BitXor: + case BitLShift: + case ValueToInt32: { + return power > 31; + } + + case BitRShift: + case BitURShift: { + if (power > 31) + return true; + + Node* shiftAmount = node->child2().node(); + if (shiftAmount->op() != JSConstant) + return false; + JSValue immediateValue = shiftAmount->valueOfJSConstant(codeBlock()); + if (!immediateValue.isInt32()) + return false; + return immediateValue.asInt32() > 32 - power; + } + + default: + return false; + } + } + + template<int power> + bool isWithinPowerOfTwo(Edge edge) + { + return isWithinPowerOfTwo<power>(edge.node()); + } + + bool mergeDefaultFlags(Node* node) + { + bool changed = false; + if (node->flags() & NodeHasVarArgs) { + for (unsigned childIdx = node->firstChild(); + childIdx < node->firstChild() + node->numChildren(); + childIdx++) { + if (!!m_graph.m_varArgChildren[childIdx]) + changed |= m_graph.m_varArgChildren[childIdx]->mergeFlags(NodeUsedAsValue); + } + } else { + if (!node->child1()) + return changed; + changed |= node->child1()->mergeFlags(NodeUsedAsValue); + if (!node->child2()) + return changed; + changed |= node->child2()->mergeFlags(NodeUsedAsValue); + if (!node->child3()) + return changed; + changed |= node->child3()->mergeFlags(NodeUsedAsValue); + } + return changed; + } + + void propagate(Node* node) + { + NodeFlags flags = node->flags() & NodeBackPropMask; + + switch (node->op()) { + case GetLocal: { + VariableAccessData* variableAccessData = node->variableAccessData(); + variableAccessData->mergeFlags(flags); + break; + } + + case SetLocal: { + VariableAccessData* variableAccessData = node->variableAccessData(); + if (!variableAccessData->isLoadedFrom()) + break; + node->child1()->mergeFlags(NodeUsedAsValue); + break; + } + + case BitAnd: + case BitOr: + case BitXor: + case BitRShift: + case BitLShift: + case BitURShift: + case ArithIMul: { + flags |= NodeUsedAsInt; + flags &= ~(NodeUsedAsNumber | NodeNeedsNegZero | NodeUsedAsOther); + node->child1()->mergeFlags(flags); + node->child2()->mergeFlags(flags); + break; + } + + case ValueToInt32: { + flags |= NodeUsedAsInt; + flags &= ~(NodeUsedAsNumber | NodeNeedsNegZero | NodeUsedAsOther); + node->child1()->mergeFlags(flags); + break; + } + + case StringCharCodeAt: { + node->child1()->mergeFlags(NodeUsedAsValue); + node->child2()->mergeFlags(NodeUsedAsValue | NodeUsedAsInt); + break; + } + + case Identity: + case UInt32ToNumber: { + node->child1()->mergeFlags(flags); + break; + } + + case ValueAdd: { + if (isNotNegZero(node->child1().node()) || isNotNegZero(node->child2().node())) + flags &= ~NodeNeedsNegZero; + if (node->child1()->hasNumberResult() || node->child2()->hasNumberResult()) + flags &= ~NodeUsedAsOther; + if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2())) + flags |= NodeUsedAsNumber; + if (!m_allowNestedOverflowingAdditions) + flags |= NodeUsedAsNumber; + + node->child1()->mergeFlags(flags); + node->child2()->mergeFlags(flags); + break; + } + + case ArithAdd: { + if (isNotNegZero(node->child1().node()) || isNotNegZero(node->child2().node())) + flags &= ~NodeNeedsNegZero; + if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2())) + flags |= NodeUsedAsNumber; + if (!m_allowNestedOverflowingAdditions) + flags |= NodeUsedAsNumber; + + node->child1()->mergeFlags(flags); + node->child2()->mergeFlags(flags); + break; + } + + case ArithSub: { + if (isNotNegZero(node->child1().node()) || isNotPosZero(node->child2().node())) + flags &= ~NodeNeedsNegZero; + if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2())) + flags |= NodeUsedAsNumber; + if (!m_allowNestedOverflowingAdditions) + flags |= NodeUsedAsNumber; + + node->child1()->mergeFlags(flags); + node->child2()->mergeFlags(flags); + break; + } + + case ArithNegate: { + flags &= ~NodeUsedAsOther; + + node->child1()->mergeFlags(flags); + break; + } + + case ArithMul: { + // As soon as a multiply happens, we can easily end up in the part + // of the double domain where the point at which you do truncation + // can change the outcome. So, ArithMul always forces its inputs to + // check for overflow. Additionally, it will have to check for overflow + // itself unless we can prove that there is no way for the values + // produced to cause double rounding. + + if (!isWithinPowerOfTwo<22>(node->child1().node()) + && !isWithinPowerOfTwo<22>(node->child2().node())) + flags |= NodeUsedAsNumber; + + node->mergeFlags(flags); + + flags |= NodeUsedAsNumber | NodeNeedsNegZero; + flags &= ~NodeUsedAsOther; + + node->child1()->mergeFlags(flags); + node->child2()->mergeFlags(flags); + break; + } + + case ArithDiv: { + flags |= NodeUsedAsNumber | NodeNeedsNegZero; + flags &= ~NodeUsedAsOther; + + node->child1()->mergeFlags(flags); + node->child2()->mergeFlags(flags); + break; + } + + case ArithMod: { + flags |= NodeUsedAsNumber | NodeNeedsNegZero; + flags &= ~NodeUsedAsOther; + + node->child1()->mergeFlags(flags); + node->child2()->mergeFlags(flags); + break; + } + + case GetByVal: { + node->child1()->mergeFlags(NodeUsedAsValue); + node->child2()->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther | NodeUsedAsInt); + break; + } + + case GetMyArgumentByValSafe: { + node->child1()->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther | NodeUsedAsInt); + break; + } + + case NewArrayWithSize: { + node->child1()->mergeFlags(NodeUsedAsValue | NodeUsedAsInt); + break; + } + + case StringCharAt: { + node->child1()->mergeFlags(NodeUsedAsValue); + node->child2()->mergeFlags(NodeUsedAsValue | NodeUsedAsInt); + break; + } + + case ToString: { + node->child1()->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther); + break; + } + + case ToPrimitive: { + node->child1()->mergeFlags(flags); + break; + } + + case PutByVal: { + m_graph.varArgChild(node, 0)->mergeFlags(NodeUsedAsValue); + m_graph.varArgChild(node, 1)->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther | NodeUsedAsInt); + m_graph.varArgChild(node, 2)->mergeFlags(NodeUsedAsValue); + break; + } + + default: + mergeDefaultFlags(node); + break; + } + } + + bool m_allowNestedOverflowingAdditions; +}; + +bool performBackwardsPropagation(Graph& graph) +{ + SamplingRegion samplingRegion("DFG Backwards Propagation Phase"); + return runPhase<BackwardsPropagationPhase>(graph); +} + +} } // namespace JSC::DFG + +#endif // ENABLE(DFG_JIT) + |