[DFG] Define defs for MapSet/SetAdd to participate in CSE
authorutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 4 Jan 2018 15:57:04 +0000 (15:57 +0000)
committerutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 4 Jan 2018 15:57:04 +0000 (15:57 +0000)
https://bugs.webkit.org/show_bug.cgi?id=179911

Reviewed by Saam Barati.

JSTests:

In addition to these tests, map-set-cse.js and set-add-cse.js work.

* stress/map-set-change-get.js: Added.
(shouldBe):
(test):
* stress/map-set-create-bucket.js: Added.
(shouldBe):
(test):
* stress/set-add-create-bucket.js: Added.
(shouldBe):

Source/JavaScriptCore:

With this patch, our MapSet and SetAdd DFG nodes participate in CSE.
To handle a bit tricky DFG Map operation nodes, MapSet and SetAdd
produce added bucket as its result. Subsequent GetMapBucket will
be removed by CSE.

* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
* dfg/DFGClobberize.h:
(JSC::DFG::clobberize):
* dfg/DFGNodeType.h:
* dfg/DFGOperations.cpp:
* dfg/DFGOperations.h:
* dfg/DFGPredictionPropagationPhase.cpp:
* dfg/DFGSpeculativeJIT.cpp:
(JSC::DFG::SpeculativeJIT::compileSetAdd):
(JSC::DFG::SpeculativeJIT::compileMapSet):
* dfg/DFGSpeculativeJIT.h:
(JSC::DFG::SpeculativeJIT::callOperation):
* ftl/FTLLowerDFGToB3.cpp:
(JSC::FTL::DFG::LowerDFGToB3::compileSetAdd):
(JSC::FTL::DFG::LowerDFGToB3::compileMapSet):
* jit/JITOperations.h:
* runtime/HashMapImpl.h:
(JSC::HashMapImpl::addNormalized):
(JSC::HashMapImpl::addNormalizedInternal):

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

16 files changed:
JSTests/ChangeLog
JSTests/stress/map-set-change-get.js [new file with mode: 0644]
JSTests/stress/map-set-create-bucket.js [new file with mode: 0644]
JSTests/stress/set-add-create-bucket.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
Source/JavaScriptCore/dfg/DFGClobberize.h
Source/JavaScriptCore/dfg/DFGNodeType.h
Source/JavaScriptCore/dfg/DFGOperations.cpp
Source/JavaScriptCore/dfg/DFGOperations.h
Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.h
Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp
Source/JavaScriptCore/jit/JITOperations.h
Source/JavaScriptCore/runtime/HashMapImpl.h

index b78dc4e..c1a61df 100644 (file)
@@ -1,3 +1,21 @@
+2018-01-04  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        [DFG] Define defs for MapSet/SetAdd to participate in CSE
+        https://bugs.webkit.org/show_bug.cgi?id=179911
+
+        Reviewed by Saam Barati.
+
+        In addition to these tests, map-set-cse.js and set-add-cse.js work.
+
+        * stress/map-set-change-get.js: Added.
+        (shouldBe):
+        (test):
+        * stress/map-set-create-bucket.js: Added.
+        (shouldBe):
+        (test):
+        * stress/set-add-create-bucket.js: Added.
+        (shouldBe):
+
 2018-01-03  Michael Saboff  <msaboff@apple.com>
 
         Disable SharedArrayBuffers from Web API
diff --git a/JSTests/stress/map-set-change-get.js b/JSTests/stress/map-set-change-get.js
new file mode 100644 (file)
index 0000000..dd49eb7
--- /dev/null
@@ -0,0 +1,21 @@
+function shouldBe(actual, expected) {
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+function test()
+{
+    var map = new Map();
+    map.set(42, 20);
+    var res1 = map.get(42);
+    map.set(42, 400);
+    var res2 = map.get(42);
+    return [res1, res2];
+}
+noInline(test);
+
+for (var i = 0; i < 1e6; ++i) {
+    var [res1, res2] = test();
+    shouldBe(res1, 20);
+    shouldBe(res2, 400);
+}
diff --git a/JSTests/stress/map-set-create-bucket.js b/JSTests/stress/map-set-create-bucket.js
new file mode 100644 (file)
index 0000000..6d90d66
--- /dev/null
@@ -0,0 +1,23 @@
+function shouldBe(actual, expected) {
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+function test()
+{
+    var map = new Map();
+    var res1 = map.get(42);
+    map.set(42, 20);
+    var res2 = map.get(42);
+    map.set(42, 400);
+    var res3 = map.get(42);
+    return [res1, res2, res3];
+}
+noInline(test);
+
+for (var i = 0; i < 1e5; ++i) {
+    var [res1, res2, res3] = test();
+    shouldBe(res1, undefined);
+    shouldBe(res2, 20);
+    shouldBe(res3, 400);
+}
diff --git a/JSTests/stress/set-add-create-bucket.js b/JSTests/stress/set-add-create-bucket.js
new file mode 100644 (file)
index 0000000..879c636
--- /dev/null
@@ -0,0 +1,26 @@
+function shouldBe(actual, expected) {
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+function test()
+{
+    var set = new Set();
+    var res1 = set.has(42);
+    set.add(42);
+    var res2 = set.has(42);
+    set.add(42);
+    var res3 = set.has(42);
+    set.delete(42);
+    var res4 = set.has(42);
+    return [res1, res2, res3, res4];
+}
+noInline(test);
+
+for (var i = 0; i < 1e5; ++i) {
+    var [res1, res2, res3, res4] = test();
+    shouldBe(res1, false);
+    shouldBe(res2, true);
+    shouldBe(res3, true);
+    shouldBe(res4, false);
+}
index c12bd49..834f2a3 100644 (file)
@@ -1,5 +1,38 @@
 2018-01-04  Yusuke Suzuki  <utatane.tea@gmail.com>
 
+        [DFG] Define defs for MapSet/SetAdd to participate in CSE
+        https://bugs.webkit.org/show_bug.cgi?id=179911
+
+        Reviewed by Saam Barati.
+
+        With this patch, our MapSet and SetAdd DFG nodes participate in CSE.
+        To handle a bit tricky DFG Map operation nodes, MapSet and SetAdd
+        produce added bucket as its result. Subsequent GetMapBucket will
+        be removed by CSE.
+
+        * dfg/DFGAbstractInterpreterInlines.h:
+        (JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
+        * dfg/DFGClobberize.h:
+        (JSC::DFG::clobberize):
+        * dfg/DFGNodeType.h:
+        * dfg/DFGOperations.cpp:
+        * dfg/DFGOperations.h:
+        * dfg/DFGPredictionPropagationPhase.cpp:
+        * dfg/DFGSpeculativeJIT.cpp:
+        (JSC::DFG::SpeculativeJIT::compileSetAdd):
+        (JSC::DFG::SpeculativeJIT::compileMapSet):
+        * dfg/DFGSpeculativeJIT.h:
+        (JSC::DFG::SpeculativeJIT::callOperation):
+        * ftl/FTLLowerDFGToB3.cpp:
+        (JSC::FTL::DFG::LowerDFGToB3::compileSetAdd):
+        (JSC::FTL::DFG::LowerDFGToB3::compileMapSet):
+        * jit/JITOperations.h:
+        * runtime/HashMapImpl.h:
+        (JSC::HashMapImpl::addNormalized):
+        (JSC::HashMapImpl::addNormalizedInternal):
+
+2018-01-04  Yusuke Suzuki  <utatane.tea@gmail.com>
+
         [JSC] Remove LocalScope
         https://bugs.webkit.org/show_bug.cgi?id=181206
 
index 6401553..3b203bf 100644 (file)
@@ -1154,7 +1154,11 @@ bool AbstractInterpreter<AbstractStateType>::executeEffects(unsigned clobberLimi
         break;
 
     case SetAdd:
+        forNode(node).set(m_graph, m_vm.hashMapBucketSetStructure.get());
+        break;
+
     case MapSet:
+        forNode(node).set(m_graph, m_vm.hashMapBucketMapStructure.get());
         break;
 
     case WeakMapGet:
index 130d0a0..bf2ac6e 100644 (file)
@@ -1650,16 +1650,18 @@ void clobberize(Graph& graph, Node* node, const ReadFunctor& read, const WriteFu
     }
 
     case SetAdd: {
-        // FIXME: Define defs for them to participate in CSE.
-        // https://bugs.webkit.org/show_bug.cgi?id=179911
+        Edge& mapEdge = node->child1();
+        Edge& keyEdge = node->child2();
         write(JSSetFields);
+        def(HeapLocation(MapBucketLoc, JSSetFields, mapEdge, keyEdge), LazyNode(node));
         return;
     }
 
     case MapSet: {
-        // FIXME: Define defs for them to participate in CSE.
-        // https://bugs.webkit.org/show_bug.cgi?id=179911
+        Edge& mapEdge = graph.varArgChild(node, 0);
+        Edge& keyEdge = graph.varArgChild(node, 1);
         write(JSMapFields);
+        def(HeapLocation(MapBucketLoc, JSMapFields, mapEdge, keyEdge), LazyNode(node));
         return;
     }
 
index 64606d5..fda29b1 100644 (file)
@@ -441,8 +441,8 @@ namespace JSC { namespace DFG {
     macro(GetMapBucketNext, NodeResultJS) \
     macro(LoadKeyFromMapBucket, NodeResultJS) \
     macro(LoadValueFromMapBucket, NodeResultJS) \
-    macro(SetAdd, NodeMustGenerate) \
-    macro(MapSet, NodeMustGenerate | NodeHasVarArgs) \
+    macro(SetAdd, NodeMustGenerate | NodeResultJS) \
+    macro(MapSet, NodeMustGenerate | NodeHasVarArgs | NodeResultJS) \
     /* Nodes for JSWeakMap and JSWeakSet */ \
     macro(WeakMapGet, NodeResultJS) \
     macro(ExtractValueFromWeakMapGet, NodeResultJS) \
index 1f0d8c7..1b7abed 100644 (file)
@@ -2625,18 +2625,24 @@ JSCell* JIT_OPERATION operationJSSetFindBucket(ExecState* exec, JSCell* map, Enc
     return *bucket;
 }
 
-void JIT_OPERATION operationSetAdd(ExecState* exec, JSCell* set, EncodedJSValue key, int32_t hash)
+JSCell* JIT_OPERATION operationSetAdd(ExecState* exec, JSCell* set, EncodedJSValue key, int32_t hash)
 {
     VM& vm = exec->vm();
     NativeCallFrameTracer tracer(&vm, exec);
-    jsCast<JSSet*>(set)->addNormalized(exec, JSValue::decode(key), JSValue(), hash);
+    auto* bucket = jsCast<JSSet*>(set)->addNormalized(exec, JSValue::decode(key), JSValue(), hash);
+    if (!bucket)
+        return vm.sentinelSetBucket.get();
+    return bucket;
 }
 
-void JIT_OPERATION operationMapSet(ExecState* exec, JSCell* map, EncodedJSValue key, EncodedJSValue value, int32_t hash)
+JSCell* JIT_OPERATION operationMapSet(ExecState* exec, JSCell* map, EncodedJSValue key, EncodedJSValue value, int32_t hash)
 {
     VM& vm = exec->vm();
     NativeCallFrameTracer tracer(&vm, exec);
-    jsCast<JSMap*>(map)->addNormalized(exec, JSValue::decode(key), JSValue::decode(value), hash);
+    auto* bucket = jsCast<JSMap*>(map)->addNormalized(exec, JSValue::decode(key), JSValue::decode(value), hash);
+    if (!bucket)
+        return vm.sentinelMapBucket.get();
+    return bucket;
 }
 
 EncodedJSValue JIT_OPERATION operationGetPrototypeOfObject(ExecState* exec, JSObject* thisObject)
index ab75b74..7cf59ff 100644 (file)
@@ -142,8 +142,6 @@ void JIT_OPERATION operationDefineAccessorProperty(ExecState*, JSObject*, Encode
 void JIT_OPERATION operationDefineAccessorPropertyString(ExecState*, JSObject*, JSString*, JSObject*, JSObject*, int32_t) WTF_INTERNAL;
 void JIT_OPERATION operationDefineAccessorPropertyStringIdent(ExecState*, JSObject*, UniquedStringImpl*, JSObject*, JSObject*, int32_t) WTF_INTERNAL;
 void JIT_OPERATION operationDefineAccessorPropertySymbol(ExecState*, JSObject*, Symbol*, JSObject*, JSObject*, int32_t) WTF_INTERNAL;
-void JIT_OPERATION operationSetAdd(ExecState*, JSCell*, EncodedJSValue, int32_t) WTF_INTERNAL;
-void JIT_OPERATION operationMapSet(ExecState*, JSCell*, EncodedJSValue, EncodedJSValue, int32_t) WTF_INTERNAL;
 EncodedJSValue JIT_OPERATION operationArrayPush(ExecState*, EncodedJSValue encodedValue, JSArray*) WTF_INTERNAL;
 EncodedJSValue JIT_OPERATION operationArrayPushMultiple(ExecState*, JSArray*, void* buffer, int32_t elementCount) WTF_INTERNAL;
 EncodedJSValue JIT_OPERATION operationArrayPushDouble(ExecState*, double value, JSArray*) WTF_INTERNAL;
@@ -167,6 +165,8 @@ JSCell* JIT_OPERATION operationCreateClonedArgumentsDuringExit(ExecState*, Inlin
 JSCell* JIT_OPERATION operationCreateClonedArguments(ExecState*, Structure*, Register* argumentStart, int32_t length, JSFunction* callee);
 JSCell* JIT_OPERATION operationCreateRest(ExecState*, Register* argumentStart, unsigned numberOfArgumentsToSkip, unsigned arraySize);
 JSCell* JIT_OPERATION operationNewArrayBuffer(ExecState*, Structure*, JSCell*, size_t) WTF_INTERNAL;
+JSCell* JIT_OPERATION operationSetAdd(ExecState*, JSCell*, EncodedJSValue, int32_t) WTF_INTERNAL;
+JSCell* JIT_OPERATION operationMapSet(ExecState*, JSCell*, EncodedJSValue, EncodedJSValue, int32_t) WTF_INTERNAL;
 double JIT_OPERATION operationFModOnInts(int32_t, int32_t) WTF_INTERNAL;
 size_t JIT_OPERATION operationObjectIsObject(ExecState*, JSGlobalObject*, JSCell*) WTF_INTERNAL;
 size_t JIT_OPERATION operationObjectIsFunction(ExecState*, JSGlobalObject*, JSCell*) WTF_INTERNAL;
index dd8d8e0..bd1b201 100644 (file)
@@ -773,6 +773,8 @@ private:
         case GetMapBucket:
         case GetMapBucketHead:
         case GetMapBucketNext:
+        case SetAdd:
+        case MapSet:
             setPrediction(SpecCellOther);
             break;
 
@@ -1181,8 +1183,6 @@ private:
         case PutDynamicVar:
         case NukeStructureAndSetButterfly:
         case InitializeEntrypointArguments:
-        case SetAdd:
-        case MapSet:
             break;
             
         // This gets ignored because it only pretends to produce a value.
index 8e7b63e..92a5e74 100644 (file)
@@ -11513,9 +11513,11 @@ void SpeculativeJIT::compileSetAdd(Node* node)
     speculateSetObject(node->child1(), setGPR);
 
     flushRegisters();
-    callOperation(operationSetAdd, setGPR, keyRegs, hashGPR);
+    GPRFlushedCallResult result(this);
+    GPRReg resultGPR = result.gpr();
+    callOperation(operationSetAdd, resultGPR, setGPR, keyRegs, hashGPR);
     m_jit.exceptionCheck();
-    noResult(node);
+    cellResult(resultGPR, node);
 }
 
 void SpeculativeJIT::compileMapSet(Node* node)
@@ -11533,9 +11535,11 @@ void SpeculativeJIT::compileMapSet(Node* node)
     speculateMapObject(m_jit.graph().varArgChild(node, 0), mapGPR);
 
     flushRegisters();
-    callOperation(operationMapSet, mapGPR, keyRegs, valueRegs, hashGPR);
+    GPRFlushedCallResult result(this);
+    GPRReg resultGPR = result.gpr();
+    callOperation(operationMapSet, resultGPR, mapGPR, keyRegs, valueRegs, hashGPR);
     m_jit.exceptionCheck();
-    noResult(node);
+    cellResult(resultGPR, node);
 }
 
 void SpeculativeJIT::compileWeakMapGet(Node* node)
index 4048ba5..94f66c9 100644 (file)
@@ -1416,6 +1416,16 @@ public:
         m_jit.setupArgumentsWithExecState(arg1, arg2, arg3);
         return appendCallSetResult(operation, result);
     }
+    JITCompiler::Call callOperation(C_JITOperation_ECJZ operation, GPRReg result, GPRReg arg1, JSValueRegs arg2, GPRReg arg3)
+    {
+        m_jit.setupArgumentsWithExecState(arg1, arg2.payloadGPR(), arg3);
+        return appendCallSetResult(operation, result);
+    }
+    JITCompiler::Call callOperation(C_JITOperation_ECJJZ operation, GPRReg result, GPRReg arg1, JSValueRegs arg2, JSValueRegs arg3, GPRReg arg4)
+    {
+        m_jit.setupArgumentsWithExecState(arg1, arg2.payloadGPR(), arg3.payloadGPR(), arg4);
+        return appendCallSetResult(operation, result);
+    }
     JITCompiler::Call callOperation(C_JITOperation_ECJ operation, GPRReg result, GPRReg arg1, JSValueRegs arg2)
     {
         m_jit.setupArgumentsWithExecState(arg1, arg2.gpr());
@@ -2066,6 +2076,11 @@ public:
         m_jit.setupArgumentsWithExecState(arg1, arg2.payloadGPR(), arg2.tagGPR(), arg3);
         return appendCallSetResult(operation, result);
     }
+    JITCompiler::Call callOperation(C_JITOperation_ECJJZ operation, GPRReg result, GPRReg arg1, JSValueRegs arg2, JSValueRegs arg3, GPRReg arg4)
+    {
+        m_jit.setupArgumentsWithExecState(arg1, arg2.payloadGPR(), arg2.tagGPR(), arg3.payloadGPR(), arg3.tagGPR(), arg4);
+        return appendCallSetResult(operation, result);
+    }
     JITCompiler::Call callOperation(C_JITOperation_ECJ operation, GPRReg result, GPRReg arg1, JSValueRegs arg2)
     {
         m_jit.setupArgumentsWithExecState(arg1, arg2.payloadGPR(), arg2.tagGPR());
index 6271638..496a246 100644 (file)
@@ -8996,7 +8996,7 @@ private:
         LValue key = lowJSValue(m_node->child2());
         LValue hash = lowInt32(m_node->child3());
 
-        vmCall(Void, m_out.operation(operationSetAdd), m_callFrame, set, key, hash);
+        setJSValue(vmCall(pointerType(), m_out.operation(operationSetAdd), m_callFrame, set, key, hash));
     }
 
     void compileMapSet()
@@ -9006,7 +9006,7 @@ private:
         LValue value = lowJSValue(m_graph.varArgChild(m_node, 2));
         LValue hash = lowInt32(m_graph.varArgChild(m_node, 3));
 
-        vmCall(Void, m_out.operation(operationMapSet), m_callFrame, map, key, value, hash);
+        setJSValue(vmCall(pointerType(), m_out.operation(operationMapSet), m_callFrame, map, key, value, hash));
     }
 
     void compileWeakMapGet()
index c27221a..106cfca 100644 (file)
@@ -218,6 +218,7 @@ typedef JSCell* (JIT_OPERATION *C_JITOperation_ECZZ)(ExecState*, JSCell*, int32_
 typedef JSCell* (JIT_OPERATION *C_JITOperation_EZ)(ExecState*, int32_t);
 typedef JSCell* (JIT_OPERATION *C_JITOperation_EJscI)(ExecState*, JSScope*, UniquedStringImpl*);
 typedef JSCell* (JIT_OPERATION *C_JITOperation_ECJZ)(ExecState*, JSCell*, EncodedJSValue, int32_t);
+typedef JSCell* (JIT_OPERATION *C_JITOperation_ECJJZ)(ExecState*, JSCell*, EncodedJSValue, EncodedJSValue, int32_t);
 typedef JSCell* (JIT_OPERATION *C_JITOperation_ECJ)(ExecState*, JSCell*, EncodedJSValue);
 typedef JSCell* (JIT_OPERATION *C_JITOperation_ECO)(ExecState*, JSCell*, JSObject*);
 typedef JSCell* (JIT_OPERATION *C_JITOperation_EJssReo)(ExecState*, JSString*, RegExpObject*);
index 1186202..94ee2e3 100644 (file)
@@ -469,16 +469,17 @@ public:
             rehash(exec);
     }
 
-    ALWAYS_INLINE void addNormalized(ExecState* exec, JSValue key, JSValue value, uint32_t hash)
+    ALWAYS_INLINE HashMapBucketType* addNormalized(ExecState* exec, JSValue key, JSValue value, uint32_t hash)
     {
         ASSERT_WITH_MESSAGE(normalizeMapKey(key) == key, "We expect normalized values flowing into this function.");
         ASSERT_WITH_MESSAGE(jsMapHash(exec, exec->vm(), key) == hash, "We expect hash value is what we expect.");
 
-        addNormalizedInternal(exec->vm(), key, value, hash, [&] (HashMapBucketType* bucket) {
+        auto* bucket = addNormalizedInternal(exec->vm(), key, value, hash, [&] (HashMapBucketType* bucket) {
             return !isDeleted(bucket) && areKeysEqual(exec, key, bucket->key());
         });
         if (shouldRehashAfterAdd())
             rehash(exec);
+        return bucket;
     }
 
     ALWAYS_INLINE bool remove(ExecState* exec, JSValue key)
@@ -606,7 +607,7 @@ private:
     }
 
     template<typename CanUseBucket>
-    ALWAYS_INLINE void addNormalizedInternal(VM& vm, JSValue key, JSValue value, uint32_t hash, const CanUseBucket& canUseBucket)
+    ALWAYS_INLINE HashMapBucketType* addNormalizedInternal(VM& vm, JSValue key, JSValue value, uint32_t hash, const CanUseBucket& canUseBucket)
     {
         ASSERT_WITH_MESSAGE(normalizeMapKey(key) == key, "We expect normalized values flowing into this function.");
 
@@ -617,7 +618,7 @@ private:
         while (!isEmpty(bucket)) {
             if (canUseBucket(bucket)) {
                 bucket->setValue(vm, value);
-                return;
+                return bucket;
             }
             index = (index + 1) & mask;
             bucket = buffer[index];
@@ -635,6 +636,7 @@ private:
         newEntry->setNext(vm, newTail);
 
         ++m_keyCount;
+        return newEntry;
     }
 
     ALWAYS_INLINE HashMapBucketType** findBucketAlreadyHashedAndNormalized(ExecState* exec, JSValue key, uint32_t hash)