MapHash should speculate on the type of its child node
authorsbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 3 Oct 2016 20:49:34 +0000 (20:49 +0000)
committersbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 3 Oct 2016 20:49:34 +0000 (20:49 +0000)
https://bugs.webkit.org/show_bug.cgi?id=161922

Reviewed by Filip Pizlo.

JSTests:

* microbenchmarks/map-key-well-typed.js: Added.
(assert):
(intKey):
(doubleKey):
(objectKey):
(stringKey):
(booleanKey):
(symbolKey):
(cellKey):
(assert.doubleKey):
(assert.booleanKey):

PerformanceTests:

I gave the main generator a name so it's easier to see what
it is when using the sampling profiler.

* ES6SampleBench/Basic/ast.js:
(Basic.Program):

Source/JavaScriptCore:

This allows us to remove runtime type checks when we've already
proven the type of the incoming value.

This is a 2-3% speedup on ES6SampleBench/Basic.

* dfg/DFGFixupPhase.cpp:
(JSC::DFG::FixupPhase::fixupNode):
* dfg/DFGSpeculativeJIT64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* ftl/FTLLowerDFGToB3.cpp:
(JSC::FTL::DFG::LowerDFGToB3::wangsInt64Hash):
(JSC::FTL::DFG::LowerDFGToB3::mapHashString):
(JSC::FTL::DFG::LowerDFGToB3::compileMapHash):

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

JSTests/ChangeLog
JSTests/microbenchmarks/map-key-well-typed.js [new file with mode: 0644]
PerformanceTests/ChangeLog
PerformanceTests/ES6SampleBench/Basic/ast.js
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGFixupPhase.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp
Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp

index 1d702a0..41a0042 100644 (file)
@@ -1,3 +1,22 @@
+2016-10-03  Saam Barati  <sbarati@apple.com>
+
+        MapHash should speculate on the type of its child node
+        https://bugs.webkit.org/show_bug.cgi?id=161922
+
+        Reviewed by Filip Pizlo.
+
+        * microbenchmarks/map-key-well-typed.js: Added.
+        (assert):
+        (intKey):
+        (doubleKey):
+        (objectKey):
+        (stringKey):
+        (booleanKey):
+        (symbolKey):
+        (cellKey):
+        (assert.doubleKey):
+        (assert.booleanKey):
+
 2016-10-03  Yusuke Suzuki  <utatane.tea@gmail.com>
 
         [ES6] GeneratorFunction (a.k.a. GeneratorWrapperFunction)'s prototype object does not have constructor property
diff --git a/JSTests/microbenchmarks/map-key-well-typed.js b/JSTests/microbenchmarks/map-key-well-typed.js
new file mode 100644 (file)
index 0000000..654003f
--- /dev/null
@@ -0,0 +1,127 @@
+function assert(b) {
+    if (!b)
+        throw new Error("Bad!");
+}
+noInline(assert);
+
+let map = new Map;
+
+function intKey(key) {
+    key++;
+    key--;
+    return map.get(key);
+}
+noInline(intKey);
+
+function doubleKey(key) {
+    key += 0.5;
+    return map.get(key);
+}
+noInline(doubleKey);
+
+function objectKey(o) {
+    o.f;
+    return map.get(o);
+}
+noInline(objectKey);
+
+function stringKey(s) {
+    s = s + s;
+    s = s.toString();
+    return map.get(s);
+}
+noInline(stringKey);
+
+function booleanKey(boolValue) {
+    return map.get(!boolValue);
+}
+noInline(booleanKey);
+
+function symbolKey(o) {
+    let symbol = o.symbol;
+    return map.get(symbol);
+}
+noInline(symbolKey);
+
+function cellKey(k) {
+    return map.get(k);
+}
+noInline(cellKey);
+
+const iters = 300000;
+let start = Date.now();
+
+map.set(20, 50);
+for (let i = 0; i < iters; i++) {
+    assert(intKey(20) === 50);
+}
+
+map.set(20.5, 55);
+for (let i = 0; i < iters; i++) {
+    assert(doubleKey(20.0) === 55);
+}
+
+map.set(30.0, 60);
+for (let i = 0; i < iters; i++) {
+    assert(doubleKey(29.5) === 60);
+}
+
+{
+    let o = {f: 20};
+    map.set(o, o);
+    for (let i = 0; i < iters; i++) {
+        assert(objectKey(o) === o);
+    }
+    let str = "93421njkfsadhjklfsdahuy9i4312";
+    map.set(str, str);
+    for (let i = 0; i < 100; i++)
+        assert(objectKey(str) === str);
+}
+
+{
+    let s = "foofoo";
+    map.set(s, s);
+    for (let i = 0; i < iters; i++) {
+        assert(stringKey("foo") === s);
+    }
+}
+
+map.set(true, "abc");
+for (let i = 0; i < iters; i++) {
+    assert(booleanKey(false) === "abc");
+}
+
+map.set(false, "abcd");
+for (let i = 0; i < iters; i++) {
+    assert(booleanKey(true) === "abcd");
+}
+
+{
+    let symbol = Symbol();
+    let o = {symbol};
+    map.set(symbol, o);
+    for (let i = 0; i < iters; i++) {
+        assert(symbolKey(o) === o);
+    }
+}
+
+{
+    let o1 = {};
+    let o2 = {};
+    let s1 = "s1s1s1s1s1s1";
+    let s2 = "s1s1s1s1s1s1s2";
+    map.set(o1, o2);
+    map.set(s1, s2);
+    let keys = [o1, o2, s1, s2];
+    for (let i = 0; i < iters; i++) {
+        let k = keys[i % keys.length];
+        let result = k === o1 ? o2 : 
+                     k === s1 ? s2 :
+                     undefined;
+        assert(cellKey(k) === result);
+    }
+}
+
+const verbose = false;
+if (verbose)
+    print(Date.now() - start);
index 3ef0bf3..c91c974 100644 (file)
@@ -1,3 +1,16 @@
+2016-10-03  Saam Barati  <sbarati@apple.com>
+
+        MapHash should speculate on the type of its child node
+        https://bugs.webkit.org/show_bug.cgi?id=161922
+
+        Reviewed by Filip Pizlo.
+
+        I gave the main generator a name so it's easier to see what
+        it is when using the sampling profiler.
+
+        * ES6SampleBench/Basic/ast.js:
+        (Basic.Program):
+
 2016-09-19  Sergio Villar Senin  <svillar@igalia.com>
 
         [css-grid] Remove the x2 computation of row sizes with indefinite heights
index 99dba17..56558a7 100644 (file)
@@ -257,7 +257,7 @@ Basic.End = function*(state)
 
 Basic.End.isBlockEnd = true;
 
-Basic.Program = function*(state)
+Basic.Program = function* programGenerator(state)
 {
     state.validate(state.program == this, "State must match program");
     let maxLineNumber = Math.max(...this.statements.keys());
index accb7ec..2f7afc6 100644 (file)
@@ -1,3 +1,24 @@
+2016-10-03  Saam Barati  <sbarati@apple.com>
+
+        MapHash should speculate on the type of its child node
+        https://bugs.webkit.org/show_bug.cgi?id=161922
+
+        Reviewed by Filip Pizlo.
+
+        This allows us to remove runtime type checks when we've already
+        proven the type of the incoming value.
+
+        This is a 2-3% speedup on ES6SampleBench/Basic.
+
+        * dfg/DFGFixupPhase.cpp:
+        (JSC::DFG::FixupPhase::fixupNode):
+        * dfg/DFGSpeculativeJIT64.cpp:
+        (JSC::DFG::SpeculativeJIT::compile):
+        * ftl/FTLLowerDFGToB3.cpp:
+        (JSC::FTL::DFG::LowerDFGToB3::wangsInt64Hash):
+        (JSC::FTL::DFG::LowerDFGToB3::mapHashString):
+        (JSC::FTL::DFG::LowerDFGToB3::compileMapHash):
+
 2016-10-03  Filip Pizlo  <fpizlo@apple.com>
 
         B3 trapping memory accesses should be documented
index 5ad6afd..1904610 100644 (file)
@@ -1599,9 +1599,40 @@ private:
             fixEdge<KnownCellUse>(node->child1());
             break;
 
-        case MapHash:
+        case MapHash: {
+            if (node->child1()->shouldSpeculateBoolean()) {
+                fixEdge<BooleanUse>(node->child1());
+                break;
+            }
+
+            if (node->child1()->shouldSpeculateInt32()) {
+                fixEdge<Int32Use>(node->child1());
+                break;
+            }
+
+            if (node->child1()->shouldSpeculateSymbol()) {
+                fixEdge<SymbolUse>(node->child1());
+                break;
+            }
+
+            if (node->child1()->shouldSpeculateObject()) {
+                fixEdge<ObjectUse>(node->child1());
+                break;
+            }
+
+            if (node->child1()->shouldSpeculateString()) {
+                fixEdge<StringUse>(node->child1());
+                break;
+            }
+
+            if (node->child1()->shouldSpeculateCell()) {
+                fixEdge<CellUse>(node->child1());
+                break;
+            }
+
             fixEdge<UntypedUse>(node->child1());
             break;
+        }
 
 #if !ASSERT_DISABLED
         // Have these no-op cases here to ensure that nobody forgets to add handlers for new opcodes.
index f5ea74b..f6778c5 100644 (file)
@@ -4602,6 +4602,79 @@ void SpeculativeJIT::compile(Node* node)
     }
         
     case MapHash: {
+        switch (node->child1().useKind()) {
+        case BooleanUse:
+        case Int32Use:
+        case SymbolUse:
+        case ObjectUse: {
+            JSValueOperand input(this, node->child1(), ManualOperandSpeculation);
+            GPRTemporary result(this, Reuse, input);
+            GPRTemporary temp(this);
+
+            GPRReg inputGPR = input.gpr();
+            GPRReg resultGPR = result.gpr();
+            GPRReg tempGPR = temp.gpr();
+
+            speculate(node, node->child1());
+
+            m_jit.move(inputGPR, resultGPR);
+            m_jit.wangsInt64Hash(resultGPR, tempGPR);
+            int32Result(resultGPR, node);
+            break;
+        }
+        case CellUse:
+        case StringUse: {
+            SpeculateCellOperand input(this, node->child1());
+            GPRTemporary result(this);
+            Optional<GPRTemporary> temp;
+
+            GPRReg tempGPR;
+            if (node->child1().useKind() == CellUse) {
+                temp = GPRTemporary(this);
+                tempGPR = temp->gpr();
+            }
+
+            GPRReg inputGPR = input.gpr();
+            GPRReg resultGPR = result.gpr();
+
+            MacroAssembler::JumpList slowPath;
+            MacroAssembler::JumpList done;
+
+            if (node->child1().useKind() == StringUse)
+                speculateString(node->child1(), inputGPR);
+            else {
+                auto isString = m_jit.branch8(MacroAssembler::Equal, MacroAssembler::Address(inputGPR, JSCell::typeInfoTypeOffset()), TrustedImm32(StringType));
+                m_jit.move(inputGPR, resultGPR);
+                m_jit.wangsInt64Hash(resultGPR, tempGPR);
+                done.append(m_jit.jump());
+                isString.link(&m_jit);
+            }
+
+            m_jit.loadPtr(MacroAssembler::Address(inputGPR, JSString::offsetOfValue()), resultGPR);
+            slowPath.append(m_jit.branchTestPtr(MacroAssembler::Zero, resultGPR));
+            m_jit.load32(MacroAssembler::Address(resultGPR, StringImpl::flagsOffset()), resultGPR);
+            m_jit.urshift32(MacroAssembler::TrustedImm32(StringImpl::s_flagCount), resultGPR);
+            slowPath.append(m_jit.branchTest32(MacroAssembler::Zero, resultGPR));
+            done.append(m_jit.jump());
+
+            slowPath.link(&m_jit);
+            silentSpillAllRegisters(resultGPR);
+            callOperation(operationMapHash, resultGPR, JSValueRegs(inputGPR));
+            silentFillAllRegisters(resultGPR);
+            m_jit.exceptionCheck();
+
+            done.link(&m_jit);
+            int32Result(resultGPR, node);
+            break;
+        }
+        default:
+            RELEASE_ASSERT(node->child1().useKind() == UntypedUse);
+            break;
+        }
+        
+        if (node->child1().useKind() != UntypedUse)
+            break;
+
         JSValueOperand input(this, node->child1());
         GPRTemporary temp(this);
         GPRTemporary result(this);
index 063cc59..45fd1a8 100644 (file)
@@ -6335,8 +6335,121 @@ private:
         setBoolean(m_out.phi(Int32, notCellResult, cellResult));
     }
 
+    LValue wangsInt64Hash(LValue input)
+    {
+        // key += ~(key << 32);
+        LValue key = input;
+        LValue temp = key;
+        temp = m_out.shl(temp, m_out.constInt32(32));
+        temp = m_out.bitNot(temp);
+        key = m_out.add(key, temp);
+        // key ^= (key >> 22);
+        temp = key;
+        temp = m_out.lShr(temp, m_out.constInt32(22));
+        key = m_out.bitXor(key, temp);
+        // key += ~(key << 13);
+        temp = key;
+        temp = m_out.shl(temp, m_out.constInt32(13));
+        temp = m_out.bitNot(temp);
+        key = m_out.add(key, temp);
+        // key ^= (key >> 8);
+        temp = key;
+        temp = m_out.lShr(temp, m_out.constInt32(8));
+        key = m_out.bitXor(key, temp);
+        // key += (key << 3);
+        temp = key;
+        temp = m_out.shl(temp, m_out.constInt32(3));
+        key = m_out.add(key, temp);
+        // key ^= (key >> 15);
+        temp = key;
+        temp = m_out.lShr(temp, m_out.constInt32(15));
+        key = m_out.bitXor(key, temp);
+        // key += ~(key << 27);
+        temp = key;
+        temp = m_out.shl(temp, m_out.constInt32(27));
+        temp = m_out.bitNot(temp);
+        key = m_out.add(key, temp);
+        // key ^= (key >> 31);
+        temp = key;
+        temp = m_out.lShr(temp, m_out.constInt32(31));
+        key = m_out.bitXor(key, temp);
+        key = m_out.castToInt32(key);
+
+        return key;
+    }
+
+    LValue mapHashString(LValue string)
+    {
+        LBasicBlock nonEmptyStringCase = m_out.newBlock();
+        LBasicBlock slowCase = m_out.newBlock();
+        LBasicBlock continuation = m_out.newBlock();
+
+        LValue stringImpl = m_out.loadPtr(string, m_heaps.JSString_value);
+        m_out.branch(
+            m_out.equal(stringImpl, m_out.constIntPtr(0)), unsure(slowCase), unsure(nonEmptyStringCase));
+
+        LBasicBlock lastNext = m_out.appendTo(nonEmptyStringCase, slowCase);
+        LValue hash = m_out.lShr(m_out.load32(stringImpl, m_heaps.StringImpl_hashAndFlags), m_out.constInt32(StringImpl::s_flagCount));
+        ValueFromBlock nonEmptyStringHashResult = m_out.anchor(hash);
+        m_out.branch(m_out.equal(hash, m_out.constInt32(0)),
+            unsure(slowCase), unsure(continuation));
+
+        m_out.appendTo(slowCase, continuation);
+        ValueFromBlock slowResult = m_out.anchor(
+            vmCall(Int32, m_out.operation(operationMapHash), m_callFrame, string));
+        m_out.jump(continuation);
+
+        m_out.appendTo(continuation, lastNext);
+        return m_out.phi(Int32, slowResult, nonEmptyStringHashResult);
+    }
+
     void compileMapHash()
     {
+        switch (m_node->child1().useKind()) {
+        case BooleanUse:
+        case Int32Use:
+        case SymbolUse:
+        case ObjectUse: {
+            LValue key = lowJSValue(m_node->child1(), ManualOperandSpeculation);
+            speculate(m_node->child1());
+            setInt32(wangsInt64Hash(key));
+            return;
+        }
+
+        case CellUse: {
+            LBasicBlock isString = m_out.newBlock();
+            LBasicBlock notString = m_out.newBlock();
+            LBasicBlock continuation = m_out.newBlock();
+
+            LValue value = lowCell(m_node->child1());
+            LValue isStringValue = m_out.equal(m_out.load8ZeroExt32(value, m_heaps.JSCell_typeInfoType), m_out.constInt32(StringType));
+            m_out.branch(
+                isStringValue, unsure(isString), unsure(notString));
+
+            LBasicBlock lastNext = m_out.appendTo(isString, notString);
+            ValueFromBlock stringResult = m_out.anchor(mapHashString(value));
+            m_out.jump(continuation);
+
+            m_out.appendTo(notString, continuation);
+            ValueFromBlock notStringResult = m_out.anchor(wangsInt64Hash(value));
+            m_out.jump(continuation);
+
+            m_out.appendTo(continuation, lastNext);
+            setInt32(m_out.phi(Int32, stringResult, notStringResult));
+            return;
+        }
+
+        case StringUse: {
+            LValue string = lowString(m_node->child1());
+            setInt32(mapHashString(string));
+            return;
+        }
+
+        default:
+            RELEASE_ASSERT(m_node->child1().useKind() == UntypedUse);
+            break;
+        }
+
         LValue value = lowJSValue(m_node->child1());
 
         LBasicBlock isCellCase = m_out.newBlock();
@@ -6365,7 +6478,7 @@ private:
         LValue hash = m_out.lShr(m_out.load32(stringImpl, m_heaps.StringImpl_hashAndFlags), m_out.constInt32(StringImpl::s_flagCount));
         ValueFromBlock nonEmptyStringHashResult = m_out.anchor(hash);
         m_out.branch(m_out.equal(hash, m_out.constInt32(0)),
-            rarely(slowCase), usually(continuation));
+            unsure(slowCase), unsure(continuation));
 
         m_out.appendTo(notCell, isNumberCase);
         m_out.branch(
@@ -6376,45 +6489,7 @@ private:
             isInt32(value), unsure(straightHash), unsure(slowCase));
 
         m_out.appendTo(straightHash, slowCase);
-        // key += ~(key << 32);
-        LValue key = value;
-        LValue temp = key;
-        temp = m_out.shl(temp, m_out.constInt32(32));
-        temp = m_out.bitNot(temp);
-        key = m_out.add(key, temp);
-        // key ^= (key >> 22);
-        temp = key;
-        temp = m_out.lShr(temp, m_out.constInt32(22));
-        key = m_out.bitXor(key, temp);
-        // key += ~(key << 13);
-        temp = key;
-        temp = m_out.shl(temp, m_out.constInt32(13));
-        temp = m_out.bitNot(temp);
-        key = m_out.add(key, temp);
-        // key ^= (key >> 8);
-        temp = key;
-        temp = m_out.lShr(temp, m_out.constInt32(8));
-        key = m_out.bitXor(key, temp);
-        // key += (key << 3);
-        temp = key;
-        temp = m_out.shl(temp, m_out.constInt32(3));
-        key = m_out.add(key, temp);
-        // key ^= (key >> 15);
-        temp = key;
-        temp = m_out.lShr(temp, m_out.constInt32(15));
-        key = m_out.bitXor(key, temp);
-        // key += ~(key << 27);
-        temp = key;
-        temp = m_out.shl(temp, m_out.constInt32(27));
-        temp = m_out.bitNot(temp);
-        key = m_out.add(key, temp);
-        // key ^= (key >> 31);
-        temp = key;
-        temp = m_out.lShr(temp, m_out.constInt32(31));
-        key = m_out.bitXor(key, temp);
-        key = m_out.castToInt32(key);
-
-        ValueFromBlock fastResult = m_out.anchor(key);
+        ValueFromBlock fastResult = m_out.anchor(wangsInt64Hash(value));
         m_out.jump(continuation);
 
         m_out.appendTo(slowCase, continuation);