Changeset 164059 in webkit for trunk/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp

Timestamp:

Feb 13, 2014, 2:46:51 PM (11 years ago)

Author:

[email protected]

Message:

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()):

File:

• trunk/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp (modified) (9 diffs)

trunk/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp

@@ -128 +128 @@
     Node* pureCSE(Node* node)
     {
-        Edge child1 = node->child1();
-        Edge child2 = node->child2();
-        Edge child3 = node->child3();
+        Edge child1 = node->child1().sanitized();
+        Edge child2 = node->child2().sanitized();
+        Edge child3 = node->child3().sanitized();
         
         for (unsigned i = endIndexForPureCSE(); i--;) {
@@ -140 +140 @@
                 continue;
             
-            if (node->hasArithMode()) {
-                if (node->arithMode() != otherNode->arithMode())
-                    continue;
-            }
-            
-            Edge otherChild = otherNode->child1();
+            Edge otherChild = otherNode->child1().sanitized();
             if (!otherChild)
                 return otherNode;
@@ -151 +146 @@
                 continue;
             
-            otherChild = otherNode->child2();
+            otherChild = otherNode->child2().sanitized();
             if (!otherChild)
                 return otherNode;
@@ -157 +152 @@
                 continue;
             
-            otherChild = otherNode->child3();
+            otherChild = otherNode->child3().sanitized();
             if (!otherChild)
                 return otherNode;
@@ -176 +171 @@
             switch (otherNode->op()) {
             case Int32ToDouble:
-                if (otherNode->child1() == node->child1())
+                if (otherNode->child1().sanitized() == node->child1().sanitized())
                     return otherNode;
                 break;
@@ -1096 +1091 @@
         case BitLShift:
         case BitURShift:
-        case ArithAdd:
-        case ArithSub:
-        case ArithNegate:
-        case ArithMul:
-        case ArithMod:
-        case ArithDiv:
         case ArithAbs:
         case ArithMin:
@@ -1116 +1105 @@
         case IsObject:
         case IsFunction:
-        case DoubleAsInt32:
         case LogicalNot:
         case SkipTopScope:
@@ -1132 +1120 @@
             setReplacement(pureCSE(node));
             break;
+            
+        case ArithAdd:
+        case ArithSub:
+        case ArithNegate:
+        case ArithMul:
+        case ArithDiv:
+        case ArithMod:
+        case UInt32ToNumber:
+        case DoubleAsInt32: {
+            if (cseMode == StoreElimination)
+                break;
+            Node* candidate = pureCSE(node);
+            if (!candidate)
+                break;
+            if (!subsumes(candidate->arithMode(), node->arithMode())) {
+                if (!subsumes(node->arithMode(), candidate->arithMode()))
+                    break;
+                candidate->setArithMode(node->arithMode());
+            }
+            setReplacement(candidate);
+            break;
+        }
             
         case Int32ToDouble:
@@ -1408 +1418 @@
         case Phantom:
             // FIXME: we ought to remove Phantom's that have no children.
+            // NB. It would be incorrect to do this for HardPhantom. In fact, the whole point
+            // of HardPhantom is that we *don't* do this for HardPhantoms, since they signify
+            // a more strict kind of liveness than the Phantom bytecode liveness.
             eliminateIrrelevantPhantomChildren(node);
             break;