[DFG] Introduce {Set,Map,WeakMap}Fields
authorutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 27 Nov 2017 01:46:59 +0000 (01:46 +0000)
committerutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 27 Nov 2017 01:46:59 +0000 (01:46 +0000)
https://bugs.webkit.org/show_bug.cgi?id=179925

Reviewed by Saam Barati.

JSTests:

* stress/map-set-clobber-map-get.js: Added.
(shouldBe):
(test):
* stress/map-set-does-not-clobber-set-has.js: Added.
(shouldBe):
* stress/map-set-does-not-clobber-weak-map-get.js: Added.
(shouldBe):
(test):
* stress/set-add-clobber-set-has.js: Added.
(shouldBe):
* stress/set-add-does-not-clobber-map-get.js: Added.
(shouldBe):

Source/JavaScriptCore:

SetAdd and MapSet uses `write(MiscFields)`, but it is not correct. It accidentally
writes readonly MiscFields which is used by various nodes and make optimization
conservative.

We introduce JSSetFields, JSMapFields, and JSWeakMapFields to precisely model clobberizing of Map, Set, and WeakMap.

* dfg/DFGAbstractHeap.h:
* dfg/DFGByteCodeParser.cpp:
(JSC::DFG::ByteCodeParser::handleIntrinsicCall):
* dfg/DFGClobberize.h:
(JSC::DFG::clobberize):
* dfg/DFGHeapLocation.cpp:
(WTF::printInternal):
* dfg/DFGHeapLocation.h:
* dfg/DFGNode.h:
(JSC::DFG::Node::hasBucketOwnerType):

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

13 files changed:
JSTests/ChangeLog
JSTests/stress/map-set-clobber-map-get.js [new file with mode: 0644]
JSTests/stress/map-set-does-not-clobber-set-has.js [new file with mode: 0644]
JSTests/stress/map-set-does-not-clobber-weak-map-get.js [new file with mode: 0644]
JSTests/stress/set-add-clobber-set-has.js [new file with mode: 0644]
JSTests/stress/set-add-does-not-clobber-map-get.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGAbstractHeap.h
Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp
Source/JavaScriptCore/dfg/DFGClobberize.h
Source/JavaScriptCore/dfg/DFGHeapLocation.cpp
Source/JavaScriptCore/dfg/DFGHeapLocation.h
Source/JavaScriptCore/dfg/DFGNode.h

index 07493ad8cb396fb7819ebfedaf5c35210c99a08a..fb978c7fc068a9f66c057c676a5b715453325fb8 100644 (file)
@@ -1,3 +1,23 @@
+2017-11-26  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        [DFG] Introduce {Set,Map,WeakMap}Fields
+        https://bugs.webkit.org/show_bug.cgi?id=179925
+
+        Reviewed by Saam Barati.
+
+        * stress/map-set-clobber-map-get.js: Added.
+        (shouldBe):
+        (test):
+        * stress/map-set-does-not-clobber-set-has.js: Added.
+        (shouldBe):
+        * stress/map-set-does-not-clobber-weak-map-get.js: Added.
+        (shouldBe):
+        (test):
+        * stress/set-add-clobber-set-has.js: Added.
+        (shouldBe):
+        * stress/set-add-does-not-clobber-map-get.js: Added.
+        (shouldBe):
+
 2017-11-24  Mark Lam  <mark.lam@apple.com>
 
         Move unsafe jsc shell test functions to the $vm object.
diff --git a/JSTests/stress/map-set-clobber-map-get.js b/JSTests/stress/map-set-clobber-map-get.js
new file mode 100644 (file)
index 0000000..043dcf8
--- /dev/null
@@ -0,0 +1,18 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+function test()
+{
+    var map = new Map();
+    map.set(42, 42);
+    var res1 = map.get(42);
+    map.set(42, 100);
+    var res2 = map.get(42);
+    return res1 + res2;
+}
+
+for (var i = 0; i < 1e6; ++i)
+    shouldBe(test(), 142);
diff --git a/JSTests/stress/map-set-does-not-clobber-set-has.js b/JSTests/stress/map-set-does-not-clobber-set-has.js
new file mode 100644 (file)
index 0000000..e11b9d2
--- /dev/null
@@ -0,0 +1,19 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+function test()
+{
+    var map = new Map();
+    var set = new Set();
+    set.add(42);
+    var res1 = set.has(42);
+    map.set(42, 42);
+    var res2 = set.has(42);
+    return res1 + res2;
+}
+
+for (var i = 0; i < 1e6; ++i)
+    shouldBe(test(), 2);
diff --git a/JSTests/stress/map-set-does-not-clobber-weak-map-get.js b/JSTests/stress/map-set-does-not-clobber-weak-map-get.js
new file mode 100644 (file)
index 0000000..56499f6
--- /dev/null
@@ -0,0 +1,26 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+function test()
+{
+    var map = new Map();
+    var weakMap = new WeakMap();
+    var key = {};
+
+    var res1 = weakMap.get(key);
+    map.set(key, key);
+    var res2 = weakMap.get(key);
+    weakMap.set(key, 42);
+    var res3 = weakMap.get(key);
+    return [undefined, undefined, 42];
+}
+
+for (var i = 0; i < 1e5; ++i) {
+    var [res1, res2, res3] = test();
+    shouldBe(res1, undefined);
+    shouldBe(res2, undefined);
+    shouldBe(res3, 42);
+}
diff --git a/JSTests/stress/set-add-clobber-set-has.js b/JSTests/stress/set-add-clobber-set-has.js
new file mode 100644 (file)
index 0000000..1f2dc9a
--- /dev/null
@@ -0,0 +1,20 @@
+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);
+    return [res1, res2];
+}
+
+for (var i = 0; i < 1e6; ++i) {
+    var [res1, res2] = test();
+    shouldBe(res1, false);
+    shouldBe(res2, true);
+}
diff --git a/JSTests/stress/set-add-does-not-clobber-map-get.js b/JSTests/stress/set-add-does-not-clobber-map-get.js
new file mode 100644 (file)
index 0000000..120e8ed
--- /dev/null
@@ -0,0 +1,19 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+function test()
+{
+    var map = new Map();
+    var set = new Set();
+    map.set(42, 42);
+    var res1 = map.get(42);
+    set.add(42);
+    var res2 = map.get(42);
+    return res1 + res2;
+}
+
+for (var i = 0; i < 1e6; ++i)
+    shouldBe(test(), 84);
index 042bb1f4d4ff531df0d1769c95e79b2023fa104d..306da106228a9401b5874cecc80dc4d0af402ea8 100644 (file)
@@ -1,3 +1,27 @@
+2017-11-26  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        [DFG] Introduce {Set,Map,WeakMap}Fields
+        https://bugs.webkit.org/show_bug.cgi?id=179925
+
+        Reviewed by Saam Barati.
+
+        SetAdd and MapSet uses `write(MiscFields)`, but it is not correct. It accidentally
+        writes readonly MiscFields which is used by various nodes and make optimization
+        conservative.
+
+        We introduce JSSetFields, JSMapFields, and JSWeakMapFields to precisely model clobberizing of Map, Set, and WeakMap.
+
+        * dfg/DFGAbstractHeap.h:
+        * dfg/DFGByteCodeParser.cpp:
+        (JSC::DFG::ByteCodeParser::handleIntrinsicCall):
+        * dfg/DFGClobberize.h:
+        (JSC::DFG::clobberize):
+        * dfg/DFGHeapLocation.cpp:
+        (WTF::printInternal):
+        * dfg/DFGHeapLocation.h:
+        * dfg/DFGNode.h:
+        (JSC::DFG::Node::hasBucketOwnerType):
+
 2017-11-26  Yusuke Suzuki  <utatane.tea@gmail.com>
 
         [JSC] Remove JSStringBuilder
index 97c3a34faca145e10540909f8dabe5f5eccf68f7..7d532bf75f62a62d93d252795149ce22db18ae23 100644 (file)
@@ -72,6 +72,9 @@ namespace JSC { namespace DFG {
     macro(HeapObjectCount) /* Used to reflect the fact that some allocations reveal object identity */\
     macro(RegExpState) \
     macro(MathDotRandomState) \
+    macro(JSMapFields) \
+    macro(JSSetFields) \
+    macro(JSWeakMapFields) \
     macro(InternalState) \
     macro(Absolute) \
     /* DOMJIT tells the heap range with the pair of integers. */\
index b841c7a3a0fb2d5d8d38fe1b22b12b925ba72d9c..5789566050e3ee33af0aeb4d95a0f2a2478f9ef7 100644 (file)
@@ -2875,7 +2875,7 @@ bool ByteCodeParser::handleIntrinsicCall(Node* callee, int resultOperand, Intrin
         Node* key = get(virtualRegisterForArgument(1, registerOffset));
         Node* hash = addToGraph(MapHash, key);
         Node* bucket = addToGraph(GetMapBucket, Edge(map, MapObjectUse), Edge(key), Edge(hash));
-        Node* result = addToGraph(LoadValueFromMapBucket, OpInfo(), OpInfo(prediction), bucket);
+        Node* result = addToGraph(LoadValueFromMapBucket, OpInfo(BucketOwnerType::Map), OpInfo(prediction), bucket);
         set(VirtualRegister(resultOperand), result);
         return true;
     }
@@ -2966,7 +2966,8 @@ bool ByteCodeParser::handleIntrinsicCall(Node* callee, int resultOperand, Intrin
 
         insertChecks();
         Node* bucket = get(virtualRegisterForArgument(1, registerOffset));
-        Node* result = addToGraph(LoadKeyFromMapBucket, OpInfo(), OpInfo(prediction), bucket);
+        BucketOwnerType type = intrinsic == JSSetBucketKeyIntrinsic ? BucketOwnerType::Set : BucketOwnerType::Map;
+        Node* result = addToGraph(LoadKeyFromMapBucket, OpInfo(type), OpInfo(prediction), bucket);
         set(VirtualRegister(resultOperand), result);
         return true;
     }
@@ -2976,7 +2977,7 @@ bool ByteCodeParser::handleIntrinsicCall(Node* callee, int resultOperand, Intrin
 
         insertChecks();
         Node* bucket = get(virtualRegisterForArgument(1, registerOffset));
-        Node* result = addToGraph(LoadValueFromMapBucket, OpInfo(), OpInfo(prediction), bucket);
+        Node* result = addToGraph(LoadValueFromMapBucket, OpInfo(BucketOwnerType::Map), OpInfo(prediction), bucket);
         set(VirtualRegister(resultOperand), result);
         return true;
     }
index d9affffa447da2e77ecdc47124da59502c34ad88..a5974fc215f6e852135fbf9e5979888b60c7b485 100644 (file)
@@ -1592,57 +1592,65 @@ void clobberize(Graph& graph, Node* node, const ReadFunctor& read, const WriteFu
         return;
 
     case GetMapBucket: {
-        read(MiscFields);
         Edge& mapEdge = node->child1();
         Edge& keyEdge = node->child2();
-        def(HeapLocation(MapBucketLoc, MiscFields, mapEdge, keyEdge), LazyNode(node));
+        AbstractHeapKind heap = (mapEdge.useKind() == MapObjectUse) ? JSMapFields : JSSetFields;
+        read(heap);
+        def(HeapLocation(MapBucketLoc, heap, mapEdge, keyEdge), LazyNode(node));
         return;
     }
 
     case GetMapBucketHead: {
-        read(MiscFields);
         Edge& mapEdge = node->child1();
-        def(HeapLocation(MapBucketHeadLoc, MiscFields, mapEdge), LazyNode(node));
+        AbstractHeapKind heap = (mapEdge.useKind() == MapObjectUse) ? JSMapFields : JSSetFields;
+        read(heap);
+        def(HeapLocation(MapBucketHeadLoc, heap, mapEdge), LazyNode(node));
         return;
     }
 
     case GetMapBucketNext: {
-        read(MiscFields);
-        LocationKind locationKind = MapBucketMapNextLoc;
-        if (node->bucketOwnerType() == BucketOwnerType::Set)
-            locationKind = MapBucketSetNextLoc;
+        AbstractHeapKind heap = (node->bucketOwnerType() == BucketOwnerType::Map) ? JSMapFields : JSSetFields;
+        read(heap);
         Edge& bucketEdge = node->child1();
-        def(HeapLocation(locationKind, MiscFields, bucketEdge), LazyNode(node));
+        def(HeapLocation(MapBucketNextLoc, heap, bucketEdge), LazyNode(node));
         return;
     }
 
     case LoadKeyFromMapBucket: {
-        read(MiscFields);
+        AbstractHeapKind heap = (node->bucketOwnerType() == BucketOwnerType::Map) ? JSMapFields : JSSetFields;
+        read(heap);
         Edge& bucketEdge = node->child1();
-        def(HeapLocation(MapBucketKeyLoc, MiscFields, bucketEdge), LazyNode(node));
+        def(HeapLocation(MapBucketKeyLoc, heap, bucketEdge), LazyNode(node));
         return;
     }
 
     case LoadValueFromMapBucket: {
-        read(MiscFields);
+        AbstractHeapKind heap = (node->bucketOwnerType() == BucketOwnerType::Map) ? JSMapFields : JSSetFields;
+        read(heap);
         Edge& bucketEdge = node->child1();
-        def(HeapLocation(MapBucketValueLoc, MiscFields, bucketEdge), LazyNode(node));
+        def(HeapLocation(MapBucketValueLoc, heap, bucketEdge), LazyNode(node));
         return;
     }
 
     case WeakMapGet: {
-        read(MiscFields);
         Edge& mapEdge = node->child1();
         Edge& keyEdge = node->child2();
-        def(HeapLocation(WeakMapGetLoc, MiscFields, mapEdge, keyEdge), LazyNode(node));
+        read(JSWeakMapFields);
+        def(HeapLocation(WeakMapGetLoc, JSWeakMapFields, mapEdge, keyEdge), LazyNode(node));
+        return;
+    }
+
+    case SetAdd: {
+        // FIXME: Define defs for them to participate in CSE.
+        // https://bugs.webkit.org/show_bug.cgi?id=179911
+        write(JSSetFields);
         return;
     }
 
-    case SetAdd:
     case MapSet: {
         // FIXME: Define defs for them to participate in CSE.
         // https://bugs.webkit.org/show_bug.cgi?id=179911
-        write(MiscFields);
+        write(JSMapFields);
         return;
     }
 
index 20d9269fcea28aa47430981eed53532664048699..aa86cb4b64b722f0d5d19cd1f881cca8ee9be8be 100644 (file)
@@ -180,12 +180,8 @@ void printInternal(PrintStream& out, LocationKind kind)
         out.print("MapBucketValueLoc");
         return;
 
-    case MapBucketMapNextLoc:
-        out.print("MapBucketMapNextLoc");
-        return;
-
-    case MapBucketSetNextLoc:
-        out.print("MapBucketSetNextLoc");
+    case MapBucketNextLoc:
+        out.print("MapBucketNextLoc");
         return;
 
     case WeakMapGetLoc:
index a7e1427f0adf44f65dd1d16974ebe2de160b4cd2..c822b8fac7233f057a57c98b61d327999ea8a763 100644 (file)
@@ -67,8 +67,7 @@ enum LocationKind {
     MapBucketHeadLoc,
     MapBucketValueLoc,
     MapBucketKeyLoc,
-    MapBucketMapNextLoc,
-    MapBucketSetNextLoc,
+    MapBucketNextLoc,
     WeakMapGetLoc,
     DOMStateLoc,
 };
index 56224e2d7028c0cc9e3ecbef432f711d06c4e867..a65a8406a8fcfaf4d3768d56650a0515473854ad 100644 (file)
@@ -2633,7 +2633,7 @@ public:
 
     bool hasBucketOwnerType()
     {
-        return op() == GetMapBucketNext;
+        return op() == GetMapBucketNext || op() == LoadKeyFromMapBucket || op() == LoadValueFromMapBucket;
     }
 
     BucketOwnerType bucketOwnerType()