Hoist and combine array bounds checks
https://bugs.webkit.org/show_bug.cgi?id=125433
Source/JavaScriptCore:
Reviewed by Mark Hahnenberg.
This adds a phase for reasoning about overflow checks and array bounds checks. It's
block-local, and removes both overflow checks and bounds checks in one go.
This also improves reasoning about commutative operations, and CSE between
CheckOverflow and Unchecked arithmetic.
This strangely uncovered a DFG backend bug where we were trying to extract an int32
from a constant even when that constant was just simply a number. I fixed that bug.
* CMakeLists.txt:
* GNUmakefile.list.am:
* JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
* JavaScriptCore.xcodeproj/project.pbxproj:
* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
* dfg/DFGAbstractValue.cpp:
(JSC::DFG::AbstractValue::set):
* dfg/DFGArgumentsSimplificationPhase.cpp:
(JSC::DFG::ArgumentsSimplificationPhase::run):
* dfg/DFGArithMode.h:
(JSC::DFG::subsumes):
* dfg/DFGByteCodeParser.cpp:
(JSC::DFG::ByteCodeParser::handleIntrinsic):
* dfg/DFGCSEPhase.cpp:
(JSC::DFG::CSEPhase::pureCSE):
(JSC::DFG::CSEPhase::int32ToDoubleCSE):
(JSC::DFG::CSEPhase::performNodeCSE):
* dfg/DFGClobberize.h:
(JSC::DFG::clobberize):
* dfg/DFGEdge.cpp:
(JSC::DFG::Edge::dump):
* dfg/DFGEdge.h:
(JSC::DFG::Edge::sanitized):
(JSC::DFG::Edge::hash):
* dfg/DFGFixupPhase.cpp:
(JSC::DFG::FixupPhase::fixupNode):
* dfg/DFGGraph.h:
(JSC::DFG::Graph::valueOfInt32Constant):
* dfg/DFGInsertionSet.h:
(JSC::DFG::InsertionSet::insertConstant):
* dfg/DFGIntegerCheckCombiningPhase.cpp: Added.
(JSC::DFG::IntegerCheckCombiningPhase::IntegerCheckCombiningPhase):
(JSC::DFG::IntegerCheckCombiningPhase::run):
(JSC::DFG::IntegerCheckCombiningPhase::handleBlock):
(JSC::DFG::IntegerCheckCombiningPhase::rangeKeyAndAddend):
(JSC::DFG::IntegerCheckCombiningPhase::isValid):
(JSC::DFG::IntegerCheckCombiningPhase::insertAdd):
(JSC::DFG::IntegerCheckCombiningPhase::insertMustAdd):
(JSC::DFG::performIntegerCheckCombining):
* dfg/DFGIntegerCheckCombiningPhase.h: Added.
* dfg/DFGNode.h:
(JSC::DFG::Node::willHaveCodeGenOrOSR):
* dfg/DFGNodeType.h:
* dfg/DFGPlan.cpp:
(JSC::DFG::Plan::compileInThreadImpl):
* dfg/DFGPredictionPropagationPhase.cpp:
(JSC::DFG::PredictionPropagationPhase::propagate):
* dfg/DFGSafeToExecute.h:
(JSC::DFG::safeToExecute):
* dfg/DFGSpeculativeJIT.cpp:
(JSC::DFG::SpeculativeJIT::compileAdd):
* dfg/DFGSpeculativeJIT32_64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGSpeculativeJIT64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGStrengthReductionPhase.cpp:
(JSC::DFG::StrengthReductionPhase::handleNode):
(JSC::DFG::StrengthReductionPhase::handleCommutativity):
* dfg/DFGTypeCheckHoistingPhase.cpp:
(JSC::DFG::TypeCheckHoistingPhase::identifyRedundantStructureChecks):
(JSC::DFG::TypeCheckHoistingPhase::identifyRedundantArrayChecks):
* ftl/FTLCapabilities.cpp:
(JSC::FTL::canCompile):
* ftl/FTLLowerDFGToLLVM.cpp:
(JSC::FTL::LowerDFGToLLVM::compileNode):
* jsc.cpp:
(GlobalObject::finishCreation):
(functionFalse):
* runtime/Identifier.h:
* runtime/Intrinsic.h:
* runtime/JSObject.h:
* tests/stress/get-by-id-untyped.js: Added.
(foo):
* tests/stress/inverted-additive-subsumption.js: Added.
(foo):
* tests/stress/redundant-add-overflow-checks.js: Added.
(foo):
* tests/stress/redundant-array-bounds-checks-addition-skip-first.js: Added.
(foo):
(arraycmp):
* tests/stress/redundant-array-bounds-checks-addition.js: Added.
(foo):
(arraycmp):
* tests/stress/redundant-array-bounds-checks-unchecked-addition.js: Added.
(foo):
(arraycmp):
* tests/stress/redundant-array-bounds-checks.js: Added.
(foo):
(arraycmp):
* tests/stress/tricky-array-bounds-checks.js: Added.
(foo):
(arraycmp):
Source/WTF:
Reviewed by Mark Hahnenberg.
* GNUmakefile.list.am:
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* wtf/CMakeLists.txt:
* wtf/HashMethod.h: Added.
(WTF::HashMethod::operator()):
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@164059 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/Source/JavaScriptCore/dfg/DFGStrengthReductionPhase.cpp b/Source/JavaScriptCore/dfg/DFGStrengthReductionPhase.cpp
index 27fa678..41472cf 100644
--- a/Source/JavaScriptCore/dfg/DFGStrengthReductionPhase.cpp
+++ b/Source/JavaScriptCore/dfg/DFGStrengthReductionPhase.cpp
@@ -71,13 +71,8 @@
{
switch (m_node->op()) {
case BitOr:
- if (m_node->child1()->isConstant()) {
- JSValue op1 = m_graph.valueOfJSConstant(m_node->child1().node());
- if (op1.isInt32() && !op1.asInt32()) {
- convertToIdentityOverChild2();
- break;
- }
- }
+ handleCommutativity();
+
if (m_node->child2()->isConstant()) {
JSValue op2 = m_graph.valueOfJSConstant(m_node->child2().node());
if (op2.isInt32() && !op2.asInt32()) {
@@ -87,6 +82,11 @@
}
break;
+ case BitXor:
+ case BitAnd:
+ handleCommutativity();
+ break;
+
case BitLShift:
case BitRShift:
case BitURShift:
@@ -112,6 +112,38 @@
}
break;
+ case ArithAdd:
+ handleCommutativity();
+
+ if (m_graph.isInt32Constant(m_node->child2().node())) {
+ int32_t value = m_graph.valueOfInt32Constant(
+ m_node->child2().node());
+ if (!value) {
+ convertToIdentityOverChild1();
+ break;
+ }
+ }
+ break;
+
+ case ArithMul:
+ handleCommutativity();
+ break;
+
+ case ArithSub:
+ if (m_graph.isInt32Constant(m_node->child2().node())
+ && m_node->isBinaryUseKind(Int32Use)) {
+ int32_t value = m_graph.valueOfInt32Constant(m_node->child2().node());
+ if (-value != value) {
+ m_node->setOp(ArithAdd);
+ m_node->child2().setNode(
+ m_insertionSet.insertConstant(
+ m_nodeIndex, m_node->origin, jsNumber(-value)));
+ m_changed = true;
+ break;
+ }
+ }
+ break;
+
case GetArrayLength:
if (JSArrayBufferView* view = m_graph.tryGetFoldableViewForChild1(m_node))
foldTypedArrayPropertyToConstant(view, jsNumber(view->length()));
@@ -179,6 +211,28 @@
m_nodeIndex, SpecNone, Phantom, m_node->origin, m_node->children);
}
+ void handleCommutativity()
+ {
+ // If the right side is a constant then there is nothing left to do.
+ if (m_node->child2()->hasConstant())
+ return;
+
+ // This case ensures that optimizations that look for x + const don't also have
+ // to look for const + x.
+ if (m_node->child1()->hasConstant()) {
+ std::swap(m_node->child1(), m_node->child2());
+ m_changed = true;
+ return;
+ }
+
+ // This case ensures that CSE is commutativity-aware.
+ if (m_node->child1().node() > m_node->child2().node()) {
+ std::swap(m_node->child1(), m_node->child2());
+ m_changed = true;
+ return;
+ }
+ }
+
InsertionSet m_insertionSet;
BasicBlock* m_block;
unsigned m_nodeIndex;
