[DFG] Add NormalizeMapKey DFG IR
authorutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 27 Nov 2017 07:51:16 +0000 (07:51 +0000)
committerutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 27 Nov 2017 07:51:16 +0000 (07:51 +0000)
https://bugs.webkit.org/show_bug.cgi?id=179912

Reviewed by Saam Barati.

JSTests:

* stress/map-untyped-normalize-cse.js: Added.
(shouldBe):
(test):
* stress/map-untyped-normalize.js: Added.
(shouldBe):
(test):
* stress/set-untyped-normalize-cse.js: Added.
(shouldBe):
(set return.set has.set has):
* stress/set-untyped-normalize.js: Added.
(shouldBe):
(set return.set has):

Source/JavaScriptCore:

This patch introduces NormalizeMapKey DFG node. It executes what normalizeMapKey does in inlined manner.
By separating this from MapHash and Map/Set related operations, we can perform CSE onto that, and we
do not need to call normalizeMapKey conservatively in DFG operations.
This can reduce slow path case in Untyped GetMapBucket since we can normalize keys in DFG/FTL.

* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
* dfg/DFGByteCodeParser.cpp:
(JSC::DFG::ByteCodeParser::handleIntrinsicCall):
* dfg/DFGClobberize.h:
(JSC::DFG::clobberize):
* dfg/DFGDoesGC.cpp:
(JSC::DFG::doesGC):
* dfg/DFGFixupPhase.cpp:
(JSC::DFG::FixupPhase::fixupNode):
(JSC::DFG::FixupPhase::fixupNormalizeMapKey):
* dfg/DFGNodeType.h:
* dfg/DFGOperations.cpp:
* dfg/DFGPredictionPropagationPhase.cpp:
* dfg/DFGSafeToExecute.h:
(JSC::DFG::safeToExecute):
* dfg/DFGSpeculativeJIT.cpp:
(JSC::DFG::SpeculativeJIT::compileNormalizeMapKey):
* dfg/DFGSpeculativeJIT.h:
* dfg/DFGSpeculativeJIT32_64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGSpeculativeJIT64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* ftl/FTLCapabilities.cpp:
(JSC::FTL::canCompile):
* ftl/FTLLowerDFGToB3.cpp:
(JSC::FTL::DFG::LowerDFGToB3::compileNode):
(JSC::FTL::DFG::LowerDFGToB3::compileMapHash):
(JSC::FTL::DFG::LowerDFGToB3::compileNormalizeMapKey):
(JSC::FTL::DFG::LowerDFGToB3::compileGetMapBucket):
* runtime/HashMapImpl.h:

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

24 files changed:
JSTests/ChangeLog
JSTests/stress/map-untyped-normalize-cse.js [new file with mode: 0644]
JSTests/stress/map-untyped-normalize.js [new file with mode: 0644]
JSTests/stress/normalize-map-key-constant-folding.js [new file with mode: 0644]
JSTests/stress/set-untyped-normalize-cse.js [new file with mode: 0644]
JSTests/stress/set-untyped-normalize.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp
Source/JavaScriptCore/dfg/DFGClobberize.h
Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp
Source/JavaScriptCore/dfg/DFGDoesGC.cpp
Source/JavaScriptCore/dfg/DFGFixupPhase.cpp
Source/JavaScriptCore/dfg/DFGNodeType.h
Source/JavaScriptCore/dfg/DFGOperations.cpp
Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp
Source/JavaScriptCore/dfg/DFGSafeToExecute.h
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.h
Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp
Source/JavaScriptCore/ftl/FTLCapabilities.cpp
Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp
Source/JavaScriptCore/runtime/HashMapImpl.h

index 46c2870..b535da9 100644 (file)
@@ -1,3 +1,23 @@
+2017-11-21  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        [DFG] Add NormalizeMapKey DFG IR
+        https://bugs.webkit.org/show_bug.cgi?id=179912
+
+        Reviewed by Saam Barati.
+
+        * stress/map-untyped-normalize-cse.js: Added.
+        (shouldBe):
+        (test):
+        * stress/map-untyped-normalize.js: Added.
+        (shouldBe):
+        (test):
+        * stress/set-untyped-normalize-cse.js: Added.
+        (shouldBe):
+        (set return.set has.set has):
+        * stress/set-untyped-normalize.js: Added.
+        (shouldBe):
+        (set return.set has):
+
 2017-11-26  Yusuke Suzuki  <utatane.tea@gmail.com>
 
         [FTL] Support DeleteById and DeleteByVal
diff --git a/JSTests/stress/map-untyped-normalize-cse.js b/JSTests/stress/map-untyped-normalize-cse.js
new file mode 100644 (file)
index 0000000..c31b0ae
--- /dev/null
@@ -0,0 +1,46 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+var keys = [
+    "Cappuccino",
+    -0.0,
+    Symbol("Cocoa"),
+    42,
+    -42,
+    null,
+    undefined,
+    420.5,
+    0xffffffff,
+    0x80000000,
+    -1,
+    -2147483648,
+    {},
+    [],
+    false,
+    true,
+    NaN,
+];
+
+let i = 0;
+let map = new Map();
+for (let key of keys)
+    map.set(key, i++);
+
+function test(map, key)
+{
+    return map.get(key) + map.get(key);
+}
+noInline(test);
+
+for (let i = 0; i < 1e4; ++i) {
+    let j = 0;
+    for (let key of keys) {
+        let result = j + j;
+        j++
+        shouldBe(test(map, key), result);
+    }
+}
+shouldBe(test(map, 0.0), 2);
diff --git a/JSTests/stress/map-untyped-normalize.js b/JSTests/stress/map-untyped-normalize.js
new file mode 100644 (file)
index 0000000..5e5e103
--- /dev/null
@@ -0,0 +1,44 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+var keys = [
+    "Cappuccino",
+    -0.0,
+    Symbol("Cocoa"),
+    42,
+    -42,
+    null,
+    undefined,
+    420.5,
+    0xffffffff,
+    0x80000000,
+    -1,
+    -2147483648,
+    {},
+    [],
+    false,
+    true,
+    NaN,
+];
+
+let i = 0;
+let map = new Map();
+for (let key of keys)
+    map.set(key, i++);
+
+function test(map, key)
+{
+    return map.get(key);
+}
+noInline(test);
+
+for (let i = 0; i < 1e4; ++i) {
+    let j = 0;
+    for (let key of keys) {
+        shouldBe(test(map, key), j++);
+    }
+}
+shouldBe(test(map, 0.0), 1);
diff --git a/JSTests/stress/normalize-map-key-constant-folding.js b/JSTests/stress/normalize-map-key-constant-folding.js
new file mode 100644 (file)
index 0000000..e30437a
--- /dev/null
@@ -0,0 +1,13 @@
+function test(i)
+{
+    var map = new Map();
+    var key = "Hello";
+    if (i & 0x1)
+        key = 42;
+    map.set(key, 42);
+    return map;
+}
+noInline(test);
+
+for (var i = 0; i < 1e6; ++i)
+    test(i);
diff --git a/JSTests/stress/set-untyped-normalize-cse.js b/JSTests/stress/set-untyped-normalize-cse.js
new file mode 100644 (file)
index 0000000..d258749
--- /dev/null
@@ -0,0 +1,44 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+var keys = [
+    "Cappuccino",
+    -0.0,
+    Symbol("Cocoa"),
+    42,
+    -42,
+    null,
+    undefined,
+    420.5,
+    0xffffffff,
+    0x80000000,
+    -1,
+    -2147483648,
+    {},
+    [],
+    false,
+    true,
+    NaN,
+];
+
+let i = 0;
+let set = new Set();
+for (let key of keys)
+    set.add(key);
+
+function test(set, key)
+{
+    return set.has(key) + set.has(key);
+}
+noInline(test);
+
+for (let i = 0; i < 1e4; ++i) {
+    let j = 0;
+    for (let key of keys) {
+        shouldBe(test(set, key), 2);
+    }
+}
+shouldBe(test(set, 0.0), 2);
diff --git a/JSTests/stress/set-untyped-normalize.js b/JSTests/stress/set-untyped-normalize.js
new file mode 100644 (file)
index 0000000..22c4eac
--- /dev/null
@@ -0,0 +1,44 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+var keys = [
+    "Cappuccino",
+    -0.0,
+    Symbol("Cocoa"),
+    42,
+    -42,
+    null,
+    undefined,
+    420.5,
+    0xffffffff,
+    0x80000000,
+    -1,
+    -2147483648,
+    {},
+    [],
+    false,
+    true,
+    NaN,
+];
+
+let i = 0;
+let set = new Set();
+for (let key of keys)
+    set.add(key);
+
+function test(set, key)
+{
+    return set.has(key);
+}
+noInline(test);
+
+for (let i = 0; i < 1e4; ++i) {
+    let j = 0;
+    for (let key of keys) {
+        shouldBe(test(set, key), true);
+    }
+}
+shouldBe(test(set, 0.0), true);
index d8c5991..e2e61d3 100644 (file)
@@ -1,3 +1,47 @@
+2017-11-21  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        [DFG] Add NormalizeMapKey DFG IR
+        https://bugs.webkit.org/show_bug.cgi?id=179912
+
+        Reviewed by Saam Barati.
+
+        This patch introduces NormalizeMapKey DFG node. It executes what normalizeMapKey does in inlined manner.
+        By separating this from MapHash and Map/Set related operations, we can perform CSE onto that, and we
+        do not need to call normalizeMapKey conservatively in DFG operations.
+        This can reduce slow path case in Untyped GetMapBucket since we can normalize keys in DFG/FTL.
+
+        * dfg/DFGAbstractInterpreterInlines.h:
+        (JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
+        * dfg/DFGByteCodeParser.cpp:
+        (JSC::DFG::ByteCodeParser::handleIntrinsicCall):
+        * dfg/DFGClobberize.h:
+        (JSC::DFG::clobberize):
+        * dfg/DFGDoesGC.cpp:
+        (JSC::DFG::doesGC):
+        * dfg/DFGFixupPhase.cpp:
+        (JSC::DFG::FixupPhase::fixupNode):
+        (JSC::DFG::FixupPhase::fixupNormalizeMapKey):
+        * dfg/DFGNodeType.h:
+        * dfg/DFGOperations.cpp:
+        * dfg/DFGPredictionPropagationPhase.cpp:
+        * dfg/DFGSafeToExecute.h:
+        (JSC::DFG::safeToExecute):
+        * dfg/DFGSpeculativeJIT.cpp:
+        (JSC::DFG::SpeculativeJIT::compileNormalizeMapKey):
+        * dfg/DFGSpeculativeJIT.h:
+        * dfg/DFGSpeculativeJIT32_64.cpp:
+        (JSC::DFG::SpeculativeJIT::compile):
+        * dfg/DFGSpeculativeJIT64.cpp:
+        (JSC::DFG::SpeculativeJIT::compile):
+        * ftl/FTLCapabilities.cpp:
+        (JSC::FTL::canCompile):
+        * ftl/FTLLowerDFGToB3.cpp:
+        (JSC::FTL::DFG::LowerDFGToB3::compileNode):
+        (JSC::FTL::DFG::LowerDFGToB3::compileMapHash):
+        (JSC::FTL::DFG::LowerDFGToB3::compileNormalizeMapKey):
+        (JSC::FTL::DFG::LowerDFGToB3::compileGetMapBucket):
+        * runtime/HashMapImpl.h:
+
 2017-11-26  Yusuke Suzuki  <utatane.tea@gmail.com>
 
         [FTL] Support DeleteById and DeleteByVal
index b660469..59071df 100644 (file)
@@ -1099,6 +1099,23 @@ bool AbstractInterpreter<AbstractStateType>::executeEffects(unsigned clobberLimi
         break;
     }
 
+    case NormalizeMapKey: {
+        if (JSValue key = forNode(node->child1()).value()) {
+            setConstant(node, *m_graph.freeze(normalizeMapKey(key)));
+            break;
+        }
+
+        SpeculatedType typeMaybeNormalized = (SpecFullNumber & ~SpecInt32Only);
+        if (!(forNode(node->child1()).m_type & typeMaybeNormalized)) {
+            m_state.setFoundConstants(true);
+            forNode(node) = forNode(node->child1());
+            break;
+        }
+
+        forNode(node).makeHeapTop();
+        break;
+    }
+
     case StringSlice: {
         forNode(node).setType(m_graph, SpecString);
         break;
index 5789566..87a8206 100644 (file)
@@ -2873,8 +2873,9 @@ bool ByteCodeParser::handleIntrinsicCall(Node* callee, int resultOperand, Intrin
         insertChecks();
         Node* map = get(virtualRegisterForArgument(0, registerOffset));
         Node* key = get(virtualRegisterForArgument(1, registerOffset));
-        Node* hash = addToGraph(MapHash, key);
-        Node* bucket = addToGraph(GetMapBucket, Edge(map, MapObjectUse), Edge(key), Edge(hash));
+        Node* normalizedKey = addToGraph(NormalizeMapKey, key);
+        Node* hash = addToGraph(MapHash, normalizedKey);
+        Node* bucket = addToGraph(GetMapBucket, Edge(map, MapObjectUse), Edge(normalizedKey), Edge(hash));
         Node* result = addToGraph(LoadValueFromMapBucket, OpInfo(BucketOwnerType::Map), OpInfo(prediction), bucket);
         set(VirtualRegister(resultOperand), result);
         return true;
@@ -2888,9 +2889,10 @@ bool ByteCodeParser::handleIntrinsicCall(Node* callee, int resultOperand, Intrin
         insertChecks();
         Node* mapOrSet = get(virtualRegisterForArgument(0, registerOffset));
         Node* key = get(virtualRegisterForArgument(1, registerOffset));
-        Node* hash = addToGraph(MapHash, key);
+        Node* normalizedKey = addToGraph(NormalizeMapKey, key);
+        Node* hash = addToGraph(MapHash, normalizedKey);
         UseKind useKind = intrinsic == JSSetHasIntrinsic ? SetObjectUse : MapObjectUse;
-        Node* bucket = addToGraph(GetMapBucket, OpInfo(0), Edge(mapOrSet, useKind), Edge(key), Edge(hash));
+        Node* bucket = addToGraph(GetMapBucket, OpInfo(0), Edge(mapOrSet, useKind), Edge(normalizedKey), Edge(hash));
         JSCell* sentinel = nullptr;
         if (intrinsic == JSMapHasIntrinsic)
             sentinel = m_vm->sentinelMapBucket.get();
@@ -2911,8 +2913,9 @@ bool ByteCodeParser::handleIntrinsicCall(Node* callee, int resultOperand, Intrin
         insertChecks();
         Node* base = get(virtualRegisterForArgument(0, registerOffset));
         Node* key = get(virtualRegisterForArgument(1, registerOffset));
-        Node* hash = addToGraph(MapHash, key);
-        addToGraph(SetAdd, base, key, hash);
+        Node* normalizedKey = addToGraph(NormalizeMapKey, key);
+        Node* hash = addToGraph(MapHash, normalizedKey);
+        addToGraph(SetAdd, base, normalizedKey, hash);
         set(VirtualRegister(resultOperand), base);
         return true;
     }
@@ -2925,10 +2928,12 @@ bool ByteCodeParser::handleIntrinsicCall(Node* callee, int resultOperand, Intrin
         Node* base = get(virtualRegisterForArgument(0, registerOffset));
         Node* key = get(virtualRegisterForArgument(1, registerOffset));
         Node* value = get(virtualRegisterForArgument(2, registerOffset));
-        Node* hash = addToGraph(MapHash, key);
+
+        Node* normalizedKey = addToGraph(NormalizeMapKey, key);
+        Node* hash = addToGraph(MapHash, normalizedKey);
 
         addVarArgChild(base);
-        addVarArgChild(key);
+        addVarArgChild(normalizedKey);
         addVarArgChild(value);
         addVarArgChild(hash);
         addToGraph(Node::VarArg, MapSet, OpInfo(0), OpInfo(0));
@@ -2992,8 +2997,9 @@ bool ByteCodeParser::handleIntrinsicCall(Node* callee, int resultOperand, Intrin
         insertChecks();
         Node* map = get(virtualRegisterForArgument(0, registerOffset));
         Node* key = get(virtualRegisterForArgument(1, registerOffset));
-        Node* hash = addToGraph(MapHash, key);
-        Node* result = addToGraph(WeakMapGet, OpInfo(), OpInfo(prediction), map, key, hash);
+        Node* normalizedKey = addToGraph(NormalizeMapKey, key);
+        Node* hash = addToGraph(MapHash, normalizedKey);
+        Node* result = addToGraph(WeakMapGet, OpInfo(), OpInfo(prediction), map, normalizedKey, hash);
         set(VirtualRegister(resultOperand), result);
         return true;
     }
index a5974fc..7cc8f64 100644 (file)
@@ -1591,6 +1591,10 @@ void clobberize(Graph& graph, Node* node, const ReadFunctor& read, const WriteFu
         def(PureValue(node));
         return;
 
+    case NormalizeMapKey:
+        def(PureValue(node));
+        return;
+
     case GetMapBucket: {
         Edge& mapEdge = node->child1();
         Edge& keyEdge = node->child2();
index 510988a..3b2b0bb 100644 (file)
@@ -635,6 +635,16 @@ private:
                 break;
             }
 
+            case NormalizeMapKey: {
+                SpeculatedType typeMaybeNormalized = (SpecFullNumber & ~SpecInt32Only);
+                if (m_state.forNode(node->child1()).m_type & typeMaybeNormalized)
+                    break;
+
+                node->convertToIdentity();
+                changed = true;
+                break;
+            }
+
             case ParseInt: {
                 AbstractValue& value = m_state.forNode(node->child1());
                 if (!value.m_type || (value.m_type & ~SpecInt32Only))
index 2332a7c..fe93e32 100644 (file)
@@ -203,6 +203,7 @@ bool doesGC(Graph& graph, Node* node)
     case CheckTraps:
     case StringFromCharCode:
     case MapHash:
+    case NormalizeMapKey:
     case GetMapBucket:
     case GetMapBucketHead:
     case GetMapBucketNext:
index 2a7bf2a..4a78ea9 100644 (file)
@@ -1940,6 +1940,11 @@ private:
             break;
         }
 
+        case NormalizeMapKey: {
+            fixupNormalizeMapKey(node);
+            break;
+        }
+
         case WeakMapGet: {
             fixEdge<WeakMapObjectUse>(node->child1());
             fixEdge<ObjectUse>(node->child2());
@@ -3203,6 +3208,47 @@ private:
         fixEdge<Int32Use>(node->child2());
     }
 
+    void fixupNormalizeMapKey(Node* node)
+    {
+        if (node->child1()->shouldSpeculateBoolean()) {
+            fixEdge<BooleanUse>(node->child1());
+            node->convertToIdentity();
+            return;
+        }
+
+        if (node->child1()->shouldSpeculateInt32()) {
+            fixEdge<Int32Use>(node->child1());
+            node->convertToIdentity();
+            return;
+        }
+
+        if (node->child1()->shouldSpeculateSymbol()) {
+            fixEdge<SymbolUse>(node->child1());
+            node->convertToIdentity();
+            return;
+        }
+
+        if (node->child1()->shouldSpeculateObject()) {
+            fixEdge<ObjectUse>(node->child1());
+            node->convertToIdentity();
+            return;
+        }
+
+        if (node->child1()->shouldSpeculateString()) {
+            fixEdge<StringUse>(node->child1());
+            node->convertToIdentity();
+            return;
+        }
+
+        if (node->child1()->shouldSpeculateCell()) {
+            fixEdge<CellUse>(node->child1());
+            node->convertToIdentity();
+            return;
+        }
+
+        fixEdge<UntypedUse>(node->child1());
+    }
+
     bool attemptToMakeCallDOM(Node* node)
     {
         if (m_graph.hasExitSite(node->origin.semantic, BadType))
index 181f919..6fdc7fe 100644 (file)
@@ -435,6 +435,7 @@ namespace JSC { namespace DFG {
     macro(ToIndexString, NodeResultJS) \
     /* Nodes for JSMap and JSSet */ \
     macro(MapHash, NodeResultInt32) \
+    macro(NormalizeMapKey, NodeResultJS) \
     macro(GetMapBucket, NodeResultJS) \
     macro(GetMapBucketHead, NodeResultJS) \
     macro(GetMapBucketNext, NodeResultJS) \
index 50802dc..5ac2af3 100644 (file)
@@ -2533,14 +2533,14 @@ int32_t JIT_OPERATION operationMapHash(ExecState* exec, EncodedJSValue input)
     VM& vm = exec->vm();
     NativeCallFrameTracer tracer(&vm, exec);
 
-    return jsMapHash(exec, vm, normalizeMapKey(JSValue::decode(input)));
+    return jsMapHash(exec, vm, JSValue::decode(input));
 }
 
 JSCell* JIT_OPERATION operationJSMapFindBucket(ExecState* exec, JSCell* map, EncodedJSValue key, int32_t hash)
 {
     VM& vm = exec->vm();
     NativeCallFrameTracer tracer(&vm, exec);
-    JSMap::BucketType** bucket = jsCast<JSMap*>(map)->findBucket(exec, normalizeMapKey(JSValue::decode(key)), hash);
+    JSMap::BucketType** bucket = jsCast<JSMap*>(map)->findBucket(exec, JSValue::decode(key), hash);
     if (!bucket)
         return vm.sentinelMapBucket.get();
     return *bucket;
@@ -2550,26 +2550,24 @@ JSCell* JIT_OPERATION operationJSSetFindBucket(ExecState* exec, JSCell* map, Enc
 {
     VM& vm = exec->vm();
     NativeCallFrameTracer tracer(&vm, exec);
-    JSSet::BucketType** bucket = jsCast<JSSet*>(map)->findBucket(exec, normalizeMapKey(JSValue::decode(key)), hash);
+    JSSet::BucketType** bucket = jsCast<JSSet*>(map)->findBucket(exec, JSValue::decode(key), hash);
     if (!bucket)
         return vm.sentinelSetBucket.get();
     return *bucket;
 }
 
-// FIXME: Add NormalizeMapKey DFG node.
-// https://bugs.webkit.org/show_bug.cgi?id=179912
 void 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, normalizeMapKey(JSValue::decode(key)), JSValue(), hash);
+    jsCast<JSSet*>(set)->addNormalized(exec, JSValue::decode(key), JSValue(), hash);
 }
 
 void 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, normalizeMapKey(JSValue::decode(key)), JSValue::decode(value), hash);
+    jsCast<JSMap*>(map)->addNormalized(exec, JSValue::decode(key), JSValue::decode(value), hash);
 }
 
 EncodedJSValue JIT_OPERATION operationGetPrototypeOfObject(ExecState* exec, JSObject* thisObject)
index 3e86d1f..b0510a0 100644 (file)
@@ -462,6 +462,13 @@ private:
             break;
         }
 
+        case NormalizeMapKey: {
+            SpeculatedType prediction = node->child1()->prediction();
+            if (prediction)
+                changed |= mergePrediction(prediction);
+            break;
+        }
+
         default:
             break;
         }
@@ -1024,6 +1031,7 @@ private:
         case GetByVal:
         case ToThis:
         case ToPrimitive: 
+        case NormalizeMapKey:
         case AtomicsAdd:
         case AtomicsAnd:
         case AtomicsCompareExchange:
index f033334..0f1a372 100644 (file)
@@ -416,6 +416,7 @@ bool safeToExecute(AbstractStateType& state, Graph& graph, Node* node)
     case ResolveScopeForHoistingFuncDeclInEval:
     case ResolveScope:
     case MapHash:
+    case NormalizeMapKey:
     case StringSlice:
     case ToLowerCase:
     case GetMapBucket:
index 34e6475..cb8ac19 100644 (file)
@@ -10737,6 +10737,47 @@ void SpeculativeJIT::emitAllocateButterfly(GPRReg storageResultGPR, GPRReg sizeG
     m_jit.store32(sizeGPR, MacroAssembler::Address(storageResultGPR, Butterfly::offsetOfVectorLength()));
 }
 
+void SpeculativeJIT::compileNormalizeMapKey(Node* node)
+{
+    ASSERT(node->child1().useKind() == UntypedUse);
+    JSValueOperand key(this, node->child1());
+    JSValueRegsTemporary result(this, Reuse, key);
+    GPRTemporary scratch(this);
+    FPRTemporary doubleValue(this);
+    FPRTemporary temp(this);
+
+    JSValueRegs keyRegs = key.jsValueRegs();
+    JSValueRegs resultRegs = result.regs();
+    GPRReg scratchGPR = scratch.gpr();
+    FPRReg doubleValueFPR = doubleValue.fpr();
+    FPRReg tempFPR = temp.fpr();
+
+    CCallHelpers::JumpList passThroughCases;
+
+    passThroughCases.append(m_jit.branchIfNotNumber(keyRegs, scratchGPR));
+    passThroughCases.append(m_jit.branchIfInt32(keyRegs));
+
+#if USE(JSVALUE64)
+    m_jit.unboxDoubleWithoutAssertions(keyRegs.gpr(), scratchGPR, doubleValueFPR);
+#else
+    unboxDouble(keyRegs.tagGPR(), keyRegs.payloadGPR(), doubleValueFPR, tempFPR);
+#endif
+    passThroughCases.append(m_jit.branchDouble(JITCompiler::DoubleNotEqualOrUnordered, doubleValueFPR, doubleValueFPR));
+
+    m_jit.truncateDoubleToInt32(doubleValueFPR, scratchGPR);
+    m_jit.convertInt32ToDouble(scratchGPR, tempFPR);
+    passThroughCases.append(m_jit.branchDouble(JITCompiler::DoubleNotEqual, doubleValueFPR, tempFPR));
+
+    m_jit.boxInt32(scratchGPR, resultRegs);
+    auto done = m_jit.jump();
+
+    passThroughCases.link(&m_jit);
+    m_jit.moveValueRegs(keyRegs, resultRegs);
+
+    done.link(&m_jit);
+    jsValueResult(resultRegs, node);
+}
+
 void SpeculativeJIT::compileGetMapBucketHead(Node* node)
 {
     SpeculateCellOperand map(this, node->child1());
index 2956494..557c0ea 100644 (file)
@@ -2894,6 +2894,7 @@ public:
     void compileCallDOMGetter(Node*);
     void compileCallDOM(Node*);
     void compileCheckSubClass(Node*);
+    void compileNormalizeMapKey(Node*);
     void compileGetMapBucketHead(Node*);
     void compileGetMapBucketNext(Node*);
     void compileSetAdd(Node*);
index 3feb84c..45b2e35 100644 (file)
@@ -4822,6 +4822,11 @@ void SpeculativeJIT::compile(Node* node)
         break;
     }
 
+    case NormalizeMapKey: {
+        compileNormalizeMapKey(node);
+        break;
+    }
+
     case GetMapBucket: {
         SpeculateCellOperand map(this, node->child1());
         JSValueOperand key(this, node->child2());
index a5cfcea..fa84ed6 100644 (file)
@@ -5072,7 +5072,7 @@ void SpeculativeJIT::compile(Node* node)
 
         MacroAssembler::JumpList straightHash;
         MacroAssembler::JumpList done;
-        auto isNotCell = m_jit.branchIfNotCell(inputGPR);
+        straightHash.append(m_jit.branchIfNotCell(inputGPR));
         MacroAssembler::JumpList slowPath;
         straightHash.append(m_jit.branch8(MacroAssembler::NotEqual, MacroAssembler::Address(inputGPR, JSCell::typeInfoTypeOffset()), TrustedImm32(StringType)));
         m_jit.loadPtr(MacroAssembler::Address(inputGPR, JSString::offsetOfValue()), resultGPR);
@@ -5082,11 +5082,6 @@ void SpeculativeJIT::compile(Node* node)
         slowPath.append(m_jit.branchTest32(MacroAssembler::Zero, resultGPR));
         done.append(m_jit.jump());
 
-        isNotCell.link(&m_jit);
-        straightHash.append(m_jit.branchIfNotNumber(inputGPR));
-        straightHash.append(m_jit.branchIfInt32(JSValueRegs(inputGPR)));
-        slowPath.append(m_jit.jump());
-
         straightHash.link(&m_jit);
         m_jit.move(inputGPR, resultGPR);
         m_jit.wangsInt64Hash(resultGPR, tempGPR);
@@ -5102,6 +5097,12 @@ void SpeculativeJIT::compile(Node* node)
         int32Result(resultGPR, node);
         break;
     }
+
+    case NormalizeMapKey: {
+        compileNormalizeMapKey(node);
+        break;
+    }
+
     case GetMapBucket: {
         SpeculateCellOperand map(this, node->child1());
         JSValueOperand key(this, node->child2(), ManualOperandSpeculation);
@@ -5182,7 +5183,8 @@ void SpeculativeJIT::compile(Node* node)
         }
         case UntypedUse: { 
             done.append(m_jit.branch64(MacroAssembler::Equal, bucketGPR, keyGPR)); // They're definitely the same value, we found the bucket we were looking for!
-            auto oneIsntCell = m_jit.branchIfNotCell(JSValueRegs(bucketGPR));
+            // The input key and bucket's key are already normalized. So if 64-bit compare fails and one is not a cell, they're definitely not equal.
+            loopAround.append(m_jit.branchIfNotCell(JSValueRegs(bucketGPR)));
             // first is a cell here.
             loopAround.append(m_jit.branchIfNotCell(JSValueRegs(keyGPR)));
             // Both are cells here.
@@ -5193,14 +5195,6 @@ void SpeculativeJIT::compile(Node* node)
                 JITCompiler::Address(keyGPR, JSCell::typeInfoTypeOffset()), TrustedImm32(StringType)));
             // The first is a string, but the second is not, we continue to loop around.
             loopAround.append(m_jit.jump());
-
-            oneIsntCell.link(&m_jit);
-            // We've already done a 64-bit compare at this point, so if one is not a number, they're definitely not equal.
-            loopAround.append(m_jit.branchIfNotNumber(bucketGPR));
-            loopAround.append(m_jit.branchIfNotNumber(keyGPR));
-            // Both are definitely numbers. If we see a double, we go to the slow path.
-            slowPathCases.append(m_jit.branchIfNotInt32(bucketGPR));
-            slowPathCases.append(m_jit.branchIfNotInt32(keyGPR));
             break;
         }
         default:
index daa132e..5b808a0 100644 (file)
@@ -202,6 +202,7 @@ inline CapabilityLevel canCompile(Node* node)
     case HasOwnProperty:
     case IsCellWithType:
     case MapHash:
+    case NormalizeMapKey:
     case GetMapBucket:
     case GetMapBucketHead:
     case GetMapBucketNext:
index 2971c7d..dbb74c0 100644 (file)
@@ -1043,6 +1043,9 @@ private:
         case MapHash:
             compileMapHash();
             break;
+        case NormalizeMapKey:
+            compileNormalizeMapKey();
+            break;
         case GetMapBucket:
             compileGetMapBucket();
             break;
@@ -8527,16 +8530,14 @@ private:
         LValue value = lowJSValue(m_node->child1());
 
         LBasicBlock isCellCase = m_out.newBlock();
-        LBasicBlock notCell = m_out.newBlock();
         LBasicBlock slowCase = m_out.newBlock();
         LBasicBlock straightHash = m_out.newBlock();
-        LBasicBlock isNumberCase = m_out.newBlock();
         LBasicBlock isStringCase = m_out.newBlock();
         LBasicBlock nonEmptyStringCase = m_out.newBlock();
         LBasicBlock continuation = m_out.newBlock();
 
         m_out.branch(
-            isCell(value, provenType(m_node->child1())), unsure(isCellCase), unsure(notCell));
+            isCell(value, provenType(m_node->child1())), unsure(isCellCase), unsure(straightHash));
 
         LBasicBlock lastNext = m_out.appendTo(isCellCase, isStringCase);
         LValue isString = m_out.equal(m_out.load8ZeroExt32(value, m_heaps.JSCell_typeInfoType), m_out.constInt32(StringType));
@@ -8548,20 +8549,12 @@ private:
         m_out.branch(
             m_out.equal(stringImpl, m_out.constIntPtr(0)), rarely(slowCase), usually(nonEmptyStringCase));
 
-        m_out.appendTo(nonEmptyStringCase, notCell);
+        m_out.appendTo(nonEmptyStringCase, straightHash);
         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(notCell, isNumberCase);
-        m_out.branch(
-            isNumber(value), unsure(isNumberCase), unsure(straightHash));
-
-        m_out.appendTo(isNumberCase, straightHash);
-        m_out.branch(
-            isInt32(value), unsure(straightHash), unsure(slowCase));
-
         m_out.appendTo(straightHash, slowCase);
         ValueFromBlock fastResult = m_out.anchor(wangsInt64Hash(value));
         m_out.jump(continuation);
@@ -8575,6 +8568,42 @@ private:
         setInt32(m_out.phi(Int32, fastResult, slowResult, nonEmptyStringHashResult));
     }
 
+    void compileNormalizeMapKey()
+    {
+        ASSERT(m_node->child1().useKind() == UntypedUse);
+
+        LBasicBlock isNumberCase = m_out.newBlock();
+        LBasicBlock notInt32NumberCase = m_out.newBlock();
+        LBasicBlock notNaNCase = m_out.newBlock();
+        LBasicBlock convertibleCase = m_out.newBlock();
+        LBasicBlock continuation = m_out.newBlock();
+
+        LBasicBlock lastNext = m_out.insertNewBlocksBefore(isNumberCase);
+
+        LValue key = lowJSValue(m_node->child1());
+        ValueFromBlock fastResult = m_out.anchor(key);
+        m_out.branch(isNotNumber(key), unsure(continuation), unsure(isNumberCase));
+
+        m_out.appendTo(isNumberCase, notInt32NumberCase);
+        m_out.branch(isInt32(key), unsure(continuation), unsure(notInt32NumberCase));
+
+        m_out.appendTo(notInt32NumberCase, notNaNCase);
+        LValue doubleValue = unboxDouble(key);
+        m_out.branch(m_out.doubleNotEqualOrUnordered(doubleValue, doubleValue), unsure(continuation), unsure(notNaNCase));
+
+        m_out.appendTo(notNaNCase, convertibleCase);
+        LValue integerValue = m_out.doubleToInt(doubleValue);
+        LValue integerValueConvertedToDouble = m_out.intToDouble(integerValue);
+        m_out.branch(m_out.doubleNotEqualOrUnordered(doubleValue, integerValueConvertedToDouble), unsure(continuation), unsure(convertibleCase));
+
+        m_out.appendTo(convertibleCase, continuation);
+        ValueFromBlock slowResult = m_out.anchor(boxInt32(integerValue));
+        m_out.jump(continuation);
+
+        m_out.appendTo(continuation, lastNext);
+        setJSValue(m_out.phi(Int64, fastResult, slowResult));
+    }
+
     void compileGetMapBucket()
     {
         LBasicBlock loopStart = m_out.newBlock();
@@ -8676,17 +8705,13 @@ private:
             LBasicBlock bucketKeyIsCell = m_out.newBlock();
             LBasicBlock bothAreCells = m_out.newBlock();
             LBasicBlock bucketKeyIsString = m_out.newBlock();
-            LBasicBlock bucketKeyNotCell = m_out.newBlock();
-            LBasicBlock bucketKeyIsNumber = m_out.newBlock();
-            LBasicBlock bothAreNumbers = m_out.newBlock();
-            LBasicBlock bucketKeyIsInt32 = m_out.newBlock();
 
             m_out.branch(m_out.equal(key, bucketKey),
                 unsure(continuation), unsure(notBitEqual));
 
             m_out.appendTo(notBitEqual, bucketKeyIsCell);
             m_out.branch(isCell(bucketKey),
-                unsure(bucketKeyIsCell), unsure(bucketKeyNotCell));
+                unsure(bucketKeyIsCell), unsure(loopAround));
 
             m_out.appendTo(bucketKeyIsCell, bothAreCells);
             m_out.branch(isCell(key),
@@ -8696,25 +8721,9 @@ private:
             m_out.branch(isString(bucketKey),
                 unsure(bucketKeyIsString), unsure(loopAround));
 
-            m_out.appendTo(bucketKeyIsString, bucketKeyNotCell);
+            m_out.appendTo(bucketKeyIsString, loopAround);
             m_out.branch(isString(key),
                 unsure(slowPath), unsure(loopAround));
-
-            m_out.appendTo(bucketKeyNotCell, bucketKeyIsNumber);
-            m_out.branch(isNotNumber(bucketKey),
-                unsure(loopAround), unsure(bucketKeyIsNumber));
-
-            m_out.appendTo(bucketKeyIsNumber, bothAreNumbers);
-            m_out.branch(isNotNumber(key),
-                unsure(loopAround), unsure(bothAreNumbers));
-
-            m_out.appendTo(bothAreNumbers, bucketKeyIsInt32);
-            m_out.branch(isNotInt32(bucketKey),
-                unsure(slowPath), unsure(bucketKeyIsInt32));
-
-            m_out.appendTo(bucketKeyIsInt32, loopAround);
-            m_out.branch(isNotInt32(key),
-                unsure(slowPath), unsure(loopAround));
             break;
         }
         default:
index a2b73a4..d0ab1fc 100644 (file)
@@ -233,6 +233,8 @@ ALWAYS_INLINE static bool areKeysEqual(ExecState* exec, JSValue a, JSValue b)
     return sameValue(exec, a, b);
 }
 
+// Note that normalization is inlined in DFG's NormalizeMapKey.
+// Keep in sync with the implementation of DFG and FTL normalization.
 ALWAYS_INLINE JSValue normalizeMapKey(JSValue key)
 {
     if (!key.isNumber())