DFG should be able to inline string equality comparisons
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 9 Apr 2013 00:10:16 +0000 (00:10 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 9 Apr 2013 00:10:16 +0000 (00:10 +0000)
https://bugs.webkit.org/show_bug.cgi?id=114224

Source/JavaScriptCore:

Reviewed by Oliver Hunt.

Inline 8-bit string equality, go to slow path for 16-bit strings. 2x speed-up for string equality
comparisons on 8-bit strings. 20-50% speed-up on JSRegress/HashMap tests. 30% speed-up on
string-fasta. 2% speed-up on SunSpider overall. Some small speed-ups elsewhere.

This is a gnarly change but we have loads of test coverage already between the HashMap tests and
preexisting DFG string equality tests (which appear to have been designed to test OSR exits, but
also give us good overall coverage on string equality behavior).

* dfg/DFGFixupPhase.cpp:
(JSC::DFG::FixupPhase::fixupNode):
* dfg/DFGOperations.cpp:
* dfg/DFGOperations.h:
* dfg/DFGSpeculativeJIT.cpp:
(JSC::DFG::SpeculativeJIT::compilePeepHoleBranch):
(JSC::DFG::SpeculativeJIT::compare):
(JSC::DFG::SpeculativeJIT::compileStrictEq):
(JSC::DFG::SpeculativeJIT::compileStringEquality):
(DFG):
* dfg/DFGSpeculativeJIT.h:
(SpeculativeJIT):

LayoutTests:

Reviewed by Oliver Hunt.

* fast/js/regress/script-tests/string-equality.js: Added.
(foo):
* fast/js/regress/string-equality-expected.txt: Added.
* fast/js/regress/string-equality.html: Added.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@147965 268f45cc-cd09-0410-ab3c-d52691b4dbfc

LayoutTests/ChangeLog
LayoutTests/fast/js/regress/script-tests/string-equality.js [new file with mode: 0644]
LayoutTests/fast/js/regress/string-equality-expected.txt [new file with mode: 0644]
LayoutTests/fast/js/regress/string-equality.html [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGFixupPhase.cpp
Source/JavaScriptCore/dfg/DFGOperations.cpp
Source/JavaScriptCore/dfg/DFGOperations.h
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.h

index 864aebe..2356f2f 100644 (file)
@@ -1,3 +1,15 @@
+2013-04-08  Filip Pizlo  <fpizlo@apple.com>
+
+        DFG should be able to inline string equality comparisons
+        https://bugs.webkit.org/show_bug.cgi?id=114224
+
+        Reviewed by Oliver Hunt.
+
+        * fast/js/regress/script-tests/string-equality.js: Added.
+        (foo):
+        * fast/js/regress/string-equality-expected.txt: Added.
+        * fast/js/regress/string-equality.html: Added.
+
 2013-04-08  Benjamin Poulain  <bpoulain@apple.com>
 
         [Mac][WebKit2] The test images-enabled-unset-can-block-image-and-can-reload-in-place.html passes
diff --git a/LayoutTests/fast/js/regress/script-tests/string-equality.js b/LayoutTests/fast/js/regress/script-tests/string-equality.js
new file mode 100644 (file)
index 0000000..aef2723
--- /dev/null
@@ -0,0 +1,16 @@
+var array = [ "a", "b", "c", "d" ];
+
+function foo(array, s) {
+    for (var i = 0; i < array.length; ++i) {
+        if (array[i] == s)
+            return true;
+    }
+    return false;
+}
+
+var result = 0;
+for (var i = 0; i < 1000000; ++i)
+    result += foo(array, "d");
+
+if (result != 1000000)
+    throw "Bad result: " + result;
diff --git a/LayoutTests/fast/js/regress/string-equality-expected.txt b/LayoutTests/fast/js/regress/string-equality-expected.txt
new file mode 100644 (file)
index 0000000..7b90d80
--- /dev/null
@@ -0,0 +1,10 @@
+JSRegress/string-equality
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
diff --git a/LayoutTests/fast/js/regress/string-equality.html b/LayoutTests/fast/js/regress/string-equality.html
new file mode 100644 (file)
index 0000000..45ef787
--- /dev/null
@@ -0,0 +1,12 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src="../resources/js-test-pre.js"></script>
+</head>
+<body>
+<script src="resources/regress-pre.js"></script>
+<script src="script-tests/string-equality.js"></script>
+<script src="resources/regress-post.js"></script>
+<script src="../resources/js-test-post.js"></script>
+</body>
+</html>
index 7449863..976ce62 100644 (file)
@@ -1,3 +1,31 @@
+2013-04-08  Filip Pizlo  <fpizlo@apple.com>
+
+        DFG should be able to inline string equality comparisons
+        https://bugs.webkit.org/show_bug.cgi?id=114224
+
+        Reviewed by Oliver Hunt.
+        
+        Inline 8-bit string equality, go to slow path for 16-bit strings. 2x speed-up for string equality
+        comparisons on 8-bit strings. 20-50% speed-up on JSRegress/HashMap tests. 30% speed-up on
+        string-fasta. 2% speed-up on SunSpider overall. Some small speed-ups elsewhere.
+
+        This is a gnarly change but we have loads of test coverage already between the HashMap tests and
+        preexisting DFG string equality tests (which appear to have been designed to test OSR exits, but
+        also give us good overall coverage on string equality behavior).
+
+        * dfg/DFGFixupPhase.cpp:
+        (JSC::DFG::FixupPhase::fixupNode):
+        * dfg/DFGOperations.cpp:
+        * dfg/DFGOperations.h:
+        * dfg/DFGSpeculativeJIT.cpp:
+        (JSC::DFG::SpeculativeJIT::compilePeepHoleBranch):
+        (JSC::DFG::SpeculativeJIT::compare):
+        (JSC::DFG::SpeculativeJIT::compileStrictEq):
+        (JSC::DFG::SpeculativeJIT::compileStringEquality):
+        (DFG):
+        * dfg/DFGSpeculativeJIT.h:
+        (SpeculativeJIT):
+
 2013-04-08  Geoffrey Garen  <ggaren@apple.com>
 
         Stop #include-ing all of JavaScriptCore in every DOM-related file
index 4debbac..3a15c30 100644 (file)
@@ -284,14 +284,15 @@ private:
             break;
         }
             
+        case CompareEqConstant: {
+            break;
+        }
+
         case CompareEq:
-        case CompareEqConstant:
         case CompareLess:
         case CompareLessEq:
         case CompareGreater:
         case CompareGreaterEq: {
-            if (node->op() == CompareEqConstant)
-                break;
             if (Node::shouldSpeculateInteger(node->child1().node(), node->child2().node())) {
                 setUseKindAndUnboxIfProfitable<Int32Use>(node->child1());
                 setUseKindAndUnboxIfProfitable<Int32Use>(node->child2());
@@ -304,8 +305,11 @@ private:
             }
             if (node->op() != CompareEq)
                 break;
-            if (node->child1()->shouldSpeculateString() && node->child2()->shouldSpeculateString())
+            if (node->child1()->shouldSpeculateString() && node->child2()->shouldSpeculateString() && GPRInfo::numberOfRegisters >= 7) {
+                setUseKindAndUnboxIfProfitable<StringUse>(node->child1());
+                setUseKindAndUnboxIfProfitable<StringUse>(node->child2());
                 break;
+            }
             if (node->child1()->shouldSpeculateObject() && node->child2()->shouldSpeculateObject()) {
                 setUseKindAndUnboxIfProfitable<ObjectUse>(node->child1());
                 setUseKindAndUnboxIfProfitable<ObjectUse>(node->child2());
@@ -324,10 +328,11 @@ private:
             break;
         }
             
-        case CompareStrictEq:
         case CompareStrictEqConstant: {
-            if (node->op() == CompareStrictEqConstant)
-                break;
+            break;
+        }
+            
+        case CompareStrictEq: {
             if (Node::shouldSpeculateInteger(node->child1().node(), node->child2().node())) {
                 setUseKindAndUnboxIfProfitable<Int32Use>(node->child1());
                 setUseKindAndUnboxIfProfitable<Int32Use>(node->child2());
@@ -338,8 +343,11 @@ private:
                 fixDoubleEdge<NumberUse>(node->child2());
                 break;
             }
-            if (node->child1()->shouldSpeculateString() && node->child2()->shouldSpeculateString())
+            if (node->child1()->shouldSpeculateString() && node->child2()->shouldSpeculateString() && GPRInfo::numberOfRegisters >= 7) {
+                setUseKindAndUnboxIfProfitable<StringUse>(node->child1());
+                setUseKindAndUnboxIfProfitable<StringUse>(node->child2());
                 break;
+            }
             if (node->child1()->shouldSpeculateObject() && node->child2()->shouldSpeculateObject()) {
                 setUseKindAndUnboxIfProfitable<ObjectUse>(node->child1());
                 setUseKindAndUnboxIfProfitable<ObjectUse>(node->child2());
index b2025a6..2765e90 100644 (file)
@@ -995,6 +995,23 @@ size_t DFG_OPERATION operationCompareEq(ExecState* exec, EncodedJSValue encodedO
     return JSValue::equalSlowCaseInline(exec, JSValue::decode(encodedOp1), JSValue::decode(encodedOp2));
 }
 
+#if USE(JSVALUE64)
+EncodedJSValue DFG_OPERATION operationCompareStringEq(ExecState* exec, JSCell* left, JSCell* right)
+#else
+size_t DFG_OPERATION operationCompareStringEq(ExecState* exec, JSCell* left, JSCell* right)
+#endif
+{
+    JSGlobalData* globalData = &exec->globalData();
+    NativeCallFrameTracer tracer(globalData, exec);
+    
+    bool result = asString(left)->value(exec) == asString(right)->value(exec);
+#if USE(JSVALUE64)
+    return JSValue::encode(jsBoolean(result));
+#else
+    return result;
+#endif
+}
+
 size_t DFG_OPERATION operationCompareStrictEqCell(ExecState* exec, EncodedJSValue encodedOp1, EncodedJSValue encodedOp2)
 {
     JSGlobalData* globalData = &exec->globalData();
index f8c4907..b664812 100644 (file)
@@ -183,6 +183,11 @@ size_t DFG_OPERATION operationCompareLessEq(ExecState*, EncodedJSValue encodedOp
 size_t DFG_OPERATION operationCompareGreater(ExecState*, EncodedJSValue encodedOp1, EncodedJSValue encodedOp2) WTF_INTERNAL;
 size_t DFG_OPERATION operationCompareGreaterEq(ExecState*, EncodedJSValue encodedOp1, EncodedJSValue encodedOp2) WTF_INTERNAL;
 size_t DFG_OPERATION operationCompareEq(ExecState*, EncodedJSValue encodedOp1, EncodedJSValue encodedOp2) WTF_INTERNAL;
+#if USE(JSVALUE64)
+EncodedJSValue DFG_OPERATION operationCompareStringEq(ExecState*, JSCell* left, JSCell* right) WTF_INTERNAL;
+#else
+size_t DFG_OPERATION operationCompareStringEq(ExecState*, JSCell* left, JSCell* right) WTF_INTERNAL;
+#endif
 size_t DFG_OPERATION operationCompareStrictEqCell(ExecState*, EncodedJSValue encodedOp1, EncodedJSValue encodedOp2) WTF_INTERNAL;
 size_t DFG_OPERATION operationCompareStrictEq(ExecState*, EncodedJSValue encodedOp1, EncodedJSValue encodedOp2) WTF_INTERNAL;
 char* DFG_OPERATION operationVirtualCall(ExecState*) WTF_INTERNAL;
index f773903..1b19af6 100644 (file)
@@ -1518,8 +1518,8 @@ bool SpeculativeJIT::compilePeepHoleBranch(Node* node, MacroAssembler::Relationa
             compilePeepHoleDoubleBranch(node, branchNode, doubleCondition);
         else if (node->op() == CompareEq) {
             if (node->isBinaryUseKind(StringUse)) {
-                nonSpeculativePeepholeBranch(node, branchNode, condition, operation);
-                return true;
+                // Use non-peephole comparison, for now.
+                return false;
             }
             if (node->isBinaryUseKind(ObjectUse))
                 compilePeepHoleObjectEquality(node, branchNode);
@@ -3476,7 +3476,7 @@ bool SpeculativeJIT::compare(Node* node, MacroAssembler::RelationalCondition con
     
     if (node->op() == CompareEq) {
         if (node->isBinaryUseKind(StringUse)) {
-            nonSpeculativeNonPeepholeCompare(node, condition, operation);
+            compileStringEquality(node);
             return false;
         }
         
@@ -3610,7 +3610,8 @@ bool SpeculativeJIT::compileStrictEq(Node* node)
     }
         
     case StringUse: {
-        return nonSpeculativeStrictEq(node);
+        compileStringEquality(node);
+        return false;
     }
         
     case ObjectUse: {
@@ -3638,6 +3639,111 @@ bool SpeculativeJIT::compileStrictEq(Node* node)
     }
 }
 
+void SpeculativeJIT::compileStringEquality(Node* node)
+{
+    SpeculateCellOperand left(this, node->child1());
+    SpeculateCellOperand right(this, node->child2());
+    GPRTemporary length(this);
+    GPRTemporary leftTemp(this);
+    GPRTemporary rightTemp(this);
+    GPRTemporary leftTemp2(this, left);
+    GPRTemporary rightTemp2(this, right);
+    
+    GPRReg leftGPR = left.gpr();
+    GPRReg rightGPR = right.gpr();
+    GPRReg lengthGPR = length.gpr();
+    GPRReg leftTempGPR = leftTemp.gpr();
+    GPRReg rightTempGPR = rightTemp.gpr();
+    GPRReg leftTemp2GPR = leftTemp2.gpr();
+    GPRReg rightTemp2GPR = rightTemp2.gpr();
+    
+    JITCompiler::JumpList trueCase;
+    JITCompiler::JumpList falseCase;
+    JITCompiler::JumpList slowCase;
+    
+    DFG_TYPE_CHECK(
+        JSValueSource::unboxedCell(leftGPR), node->child1(), SpecString, m_jit.branchPtr(
+            MacroAssembler::NotEqual,
+            MacroAssembler::Address(leftGPR, JSCell::structureOffset()),
+            MacroAssembler::TrustedImmPtr(m_jit.globalData()->stringStructure.get())));
+    
+    // It's safe to branch around the type check below, since proving that the values are
+    // equal does indeed prove that the right value is a string.
+    trueCase.append(m_jit.branchPtr(MacroAssembler::Equal, leftGPR, rightGPR));
+    
+    DFG_TYPE_CHECK(
+        JSValueSource::unboxedCell(rightGPR), node->child2(), SpecString, m_jit.branchPtr(
+            MacroAssembler::NotEqual,
+            MacroAssembler::Address(rightGPR, JSCell::structureOffset()),
+            MacroAssembler::TrustedImmPtr(m_jit.globalData()->stringStructure.get())));
+
+    m_jit.load32(MacroAssembler::Address(leftGPR, JSString::offsetOfLength()), lengthGPR);
+    
+    falseCase.append(m_jit.branch32(
+        MacroAssembler::NotEqual,
+        MacroAssembler::Address(rightGPR, JSString::offsetOfLength()),
+        lengthGPR));
+    
+    trueCase.append(m_jit.branchTest32(MacroAssembler::Zero, lengthGPR));
+    
+    m_jit.loadPtr(MacroAssembler::Address(leftGPR, JSString::offsetOfValue()), leftTempGPR);
+    m_jit.loadPtr(MacroAssembler::Address(rightGPR, JSString::offsetOfValue()), rightTempGPR);
+    
+    slowCase.append(m_jit.branchTestPtr(MacroAssembler::Zero, leftTempGPR));
+    slowCase.append(m_jit.branchTestPtr(MacroAssembler::Zero, rightTempGPR));
+    
+    slowCase.append(m_jit.branchTest32(
+        MacroAssembler::Zero,
+        MacroAssembler::Address(leftTempGPR, StringImpl::flagsOffset()),
+        TrustedImm32(StringImpl::flagIs8Bit())));
+    slowCase.append(m_jit.branchTest32(
+        MacroAssembler::Zero,
+        MacroAssembler::Address(rightTempGPR, StringImpl::flagsOffset()),
+        TrustedImm32(StringImpl::flagIs8Bit())));
+    
+    m_jit.loadPtr(MacroAssembler::Address(leftTempGPR, StringImpl::dataOffset()), leftTempGPR);
+    m_jit.loadPtr(MacroAssembler::Address(rightTempGPR, StringImpl::dataOffset()), rightTempGPR);
+    
+    MacroAssembler::Label loop = m_jit.label();
+    
+    m_jit.sub32(TrustedImm32(1), lengthGPR);
+
+    // This isn't going to generate the best code on x86. But that's OK, it's still better
+    // than not inlining.
+    m_jit.load8(MacroAssembler::BaseIndex(leftTempGPR, lengthGPR, MacroAssembler::TimesOne), leftTemp2GPR);
+    m_jit.load8(MacroAssembler::BaseIndex(rightTempGPR, lengthGPR, MacroAssembler::TimesOne), rightTemp2GPR);
+    falseCase.append(m_jit.branch32(MacroAssembler::NotEqual, leftTemp2GPR, rightTemp2GPR));
+    
+    m_jit.branchTest32(MacroAssembler::NonZero, lengthGPR).linkTo(loop, &m_jit);
+    
+    trueCase.link(&m_jit);
+#if USE(JSVALUE64)
+    m_jit.move(TrustedImm64(ValueTrue), leftTempGPR);
+#else
+    m_jit.move(TrustedImm32(true), leftTempGPR);
+#endif
+    
+    JITCompiler::Jump done = m_jit.jump();
+
+    falseCase.link(&m_jit);
+#if USE(JSVALUE64)
+    m_jit.move(TrustedImm64(ValueFalse), leftTempGPR);
+#else
+    m_jit.move(TrustedImm32(false), leftTempGPR);
+#endif
+    
+    done.link(&m_jit);
+    addSlowPathGenerator(
+        slowPathCall(
+            slowCase, this, operationCompareStringEq, leftTempGPR, leftGPR, rightGPR));
+    
+#if USE(JSVALUE64)
+    jsValueResult(leftTempGPR, node, DataFormatJSBoolean);
+#else
+    booleanResult(leftTempGPR, node);
+#endif
+}
+
 void SpeculativeJIT::compileGetIndexedPropertyStorage(Node* node)
 {
     SpeculateCellOperand base(this, node->child1());
index 352f28e..2359ae0 100644 (file)
@@ -2071,6 +2071,7 @@ public:
     void compileValueAdd(Node*);
     void compileObjectOrOtherLogicalNot(Edge value);
     void compileLogicalNot(Node*);
+    void compileStringEquality(Node*);
     void emitObjectOrOtherBranch(Edge value, BlockIndex taken, BlockIndex notTaken);
     void emitBranch(Node*);