[JSC] Record CoW status in ArrayProfile
authorutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 25 Jul 2018 00:41:10 +0000 (00:41 +0000)
committerutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 25 Jul 2018 00:41:10 +0000 (00:41 +0000)
https://bugs.webkit.org/show_bug.cgi?id=187949

Reviewed by Saam Barati.

JSTests:

* stress/array-profile-should-record-copy-on-write.js: Added.
(shouldBe):
(test1):
(test2):
(test3):

Source/JavaScriptCore:

Once CoW array is converted to non-CoW array, subsequent operations are done for this non-CoW array.
Even though these operations are performed onto both CoW and non-CoW arrays in the code, array profiles
in these code typically record only non-CoW arrays since array profiles hold only one StructureID recently
seen. This results emitting CheckStructure for non-CoW arrays in DFG, and it soon causes OSR exits due to
CoW arrays.

In this patch, we record CoW status in ArrayProfile separately to construct more appropriate DFG::ArrayMode
speculation. To do so efficiently, we store union of seen IndexingMode in ArrayProfile.

This patch removes one of Kraken/stanford-crypto-aes's OSR exit reason, and improves the performance by 6-7%.

                              baseline                  patched

stanford-crypto-aes        60.893+-1.346      ^      57.412+-1.298         ^ definitely 1.0606x faster
stanford-crypto-ccm        62.124+-1.992             58.921+-1.844           might be 1.0544x faster

* bytecode/ArrayProfile.cpp:
(JSC::ArrayProfile::briefDescriptionWithoutUpdating):
* bytecode/ArrayProfile.h:
(JSC::asArrayModes):
We simplify asArrayModes instead of giving up Int8ArrayMode - Float64ArrayMode contiguous sequence.

(JSC::ArrayProfile::ArrayProfile):
(JSC::ArrayProfile::addressOfObservedIndexingModes):
(JSC::ArrayProfile::observedIndexingModes const):
Currently, our macro assembler and offlineasm only support `or32` / `ori` operation onto addresses.
So storing the union of seen IndexingMode in `unsigned` instead.

* dfg/DFGArrayMode.cpp:
(JSC::DFG::ArrayMode::fromObserved):
* dfg/DFGArrayMode.h:
(JSC::DFG::ArrayMode::withProfile const):
* jit/JITCall.cpp:
(JSC::JIT::compileOpCall):
* jit/JITCall32_64.cpp:
(JSC::JIT::compileOpCall):
* jit/JITInlines.h:
(JSC::JIT::emitArrayProfilingSiteWithCell):
* llint/LowLevelInterpreter.asm:
* llint/LowLevelInterpreter32_64.asm:
* llint/LowLevelInterpreter64.asm:

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

13 files changed:
JSTests/ChangeLog
JSTests/stress/array-profile-should-record-copy-on-write.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/bytecode/ArrayProfile.cpp
Source/JavaScriptCore/bytecode/ArrayProfile.h
Source/JavaScriptCore/dfg/DFGArrayMode.cpp
Source/JavaScriptCore/dfg/DFGArrayMode.h
Source/JavaScriptCore/jit/JITCall.cpp
Source/JavaScriptCore/jit/JITCall32_64.cpp
Source/JavaScriptCore/jit/JITInlines.h
Source/JavaScriptCore/llint/LowLevelInterpreter.asm
Source/JavaScriptCore/llint/LowLevelInterpreter32_64.asm
Source/JavaScriptCore/llint/LowLevelInterpreter64.asm

index e40deac..b06686d 100644 (file)
@@ -1,3 +1,16 @@
+2018-07-24  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        [JSC] Record CoW status in ArrayProfile
+        https://bugs.webkit.org/show_bug.cgi?id=187949
+
+        Reviewed by Saam Barati.
+
+        * stress/array-profile-should-record-copy-on-write.js: Added.
+        (shouldBe):
+        (test1):
+        (test2):
+        (test3):
+
 2018-07-23  Saam Barati  <sbarati@apple.com>
 
         need to didFoldClobberWorld when we constant fold GetByVal
diff --git a/JSTests/stress/array-profile-should-record-copy-on-write.js b/JSTests/stress/array-profile-should-record-copy-on-write.js
new file mode 100644 (file)
index 0000000..204b4c4
--- /dev/null
@@ -0,0 +1,39 @@
+function shouldBe(actual, expected)
+{
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+noInline(shouldBe);
+
+function test1(array)
+{
+    for (var i = 0; i < 5; ++i) {
+        array[0] = array[0] + 1;
+    }
+    return array;
+}
+noInline(test1);
+
+function test2(array)
+{
+    for (var i = 0; i < 5; ++i) {
+        array[0] = array[0] + 1;
+    }
+    return array;
+}
+noInline(test2);
+
+function test3(array)
+{
+    for (var i = 0; i < 5; ++i) {
+        array[0] = array[0] + 1;
+    }
+    return array;
+}
+noInline(test3);
+
+for (var i = 0; i < 1e6; ++i) {
+    shouldBe(String(test1([0, 1, 2, 3, 4])), `5,1,2,3,4`);
+    shouldBe(String(test2([0.1, 1.1, 2.1, 3.1, 4.1])), `5.1,1.1,2.1,3.1,4.1`);
+    shouldBe(String(test3(['C', 'o', 'c', 'o', 'a'])), `C11111,o,c,o,a`);
+}
index e931199..8ab3602 100644 (file)
@@ -1,3 +1,52 @@
+2018-07-24  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        [JSC] Record CoW status in ArrayProfile
+        https://bugs.webkit.org/show_bug.cgi?id=187949
+
+        Reviewed by Saam Barati.
+
+        Once CoW array is converted to non-CoW array, subsequent operations are done for this non-CoW array.
+        Even though these operations are performed onto both CoW and non-CoW arrays in the code, array profiles
+        in these code typically record only non-CoW arrays since array profiles hold only one StructureID recently
+        seen. This results emitting CheckStructure for non-CoW arrays in DFG, and it soon causes OSR exits due to
+        CoW arrays.
+
+        In this patch, we record CoW status in ArrayProfile separately to construct more appropriate DFG::ArrayMode
+        speculation. To do so efficiently, we store union of seen IndexingMode in ArrayProfile.
+
+        This patch removes one of Kraken/stanford-crypto-aes's OSR exit reason, and improves the performance by 6-7%.
+
+                                      baseline                  patched
+
+        stanford-crypto-aes        60.893+-1.346      ^      57.412+-1.298         ^ definitely 1.0606x faster
+        stanford-crypto-ccm        62.124+-1.992             58.921+-1.844           might be 1.0544x faster
+
+        * bytecode/ArrayProfile.cpp:
+        (JSC::ArrayProfile::briefDescriptionWithoutUpdating):
+        * bytecode/ArrayProfile.h:
+        (JSC::asArrayModes):
+        We simplify asArrayModes instead of giving up Int8ArrayMode - Float64ArrayMode contiguous sequence.
+
+        (JSC::ArrayProfile::ArrayProfile):
+        (JSC::ArrayProfile::addressOfObservedIndexingModes):
+        (JSC::ArrayProfile::observedIndexingModes const):
+        Currently, our macro assembler and offlineasm only support `or32` / `ori` operation onto addresses.
+        So storing the union of seen IndexingMode in `unsigned` instead.
+
+        * dfg/DFGArrayMode.cpp:
+        (JSC::DFG::ArrayMode::fromObserved):
+        * dfg/DFGArrayMode.h:
+        (JSC::DFG::ArrayMode::withProfile const):
+        * jit/JITCall.cpp:
+        (JSC::JIT::compileOpCall):
+        * jit/JITCall32_64.cpp:
+        (JSC::JIT::compileOpCall):
+        * jit/JITInlines.h:
+        (JSC::JIT::emitArrayProfilingSiteWithCell):
+        * llint/LowLevelInterpreter.asm:
+        * llint/LowLevelInterpreter32_64.asm:
+        * llint/LowLevelInterpreter64.asm:
+
 2018-07-24  Tim Horton  <timothy_horton@apple.com>
 
         Enable Web Content Filtering on watchOS
index d071b0d..349541a 100644 (file)
@@ -165,6 +165,8 @@ CString ArrayProfile::briefDescriptionWithoutUpdating(const ConcurrentJSLocker&)
         out.print(comma, "Intercept");
     if (m_usesOriginalArrayStructures)
         out.print(comma, "Original");
+    if (isCopyOnWrite(m_observedArrayModes))
+        out.print(comma, "CopyOnWrite");
 
     return out.toCString();
 }
index 220b67e..55d3810 100644 (file)
@@ -39,36 +39,27 @@ class LLIntOffsetsExtractor;
 // There are 9 typed array types taking the bits 16 to 25.
 typedef unsigned ArrayModes;
 
-const ArrayModes CopyOnWriteArrayWithInt32ArrayMode = 1 << 16;
-const ArrayModes CopyOnWriteArrayWithDoubleArrayMode = 1 << 17;
-const ArrayModes CopyOnWriteArrayWithContiguousArrayMode = 1 << 18;
-
-const ArrayModes Int8ArrayMode = 1 << 19;
-const ArrayModes Int16ArrayMode = 1 << 20;
-const ArrayModes Int32ArrayMode = 1 << 21;
-const ArrayModes Uint8ArrayMode = 1 << 22;
-const ArrayModes Uint8ClampedArrayMode = 1 << 23;
-const ArrayModes Uint16ArrayMode = 1 << 24;
-const ArrayModes Uint32ArrayMode = 1 << 25;
-const ArrayModes Float32ArrayMode = 1 << 26;
-const ArrayModes Float64ArrayMode = 1 << 27;
+// The possible IndexingTypes are limited within (0 - 16, 21, 23, 25).
+// This is because CoW types only appear for JSArrays.
+static_assert(CopyOnWriteArrayWithInt32 == 21, "");
+static_assert(CopyOnWriteArrayWithDouble == 23, "");
+static_assert(CopyOnWriteArrayWithContiguous == 25, "");
+const ArrayModes CopyOnWriteArrayWithInt32ArrayMode = 1 << CopyOnWriteArrayWithInt32;
+const ArrayModes CopyOnWriteArrayWithDoubleArrayMode = 1 << CopyOnWriteArrayWithDouble;
+const ArrayModes CopyOnWriteArrayWithContiguousArrayMode = 1 << CopyOnWriteArrayWithContiguous;
+
+const ArrayModes Int8ArrayMode = 1 << 16;
+const ArrayModes Int16ArrayMode = 1 << 17;
+const ArrayModes Int32ArrayMode = 1 << 18;
+const ArrayModes Uint8ArrayMode = 1 << 19;
+const ArrayModes Uint8ClampedArrayMode = 1 << 20; // 21 - 25 are used for CoW arrays.
+const ArrayModes Uint16ArrayMode = 1 << 26;
+const ArrayModes Uint32ArrayMode = 1 << 27;
+const ArrayModes Float32ArrayMode = 1 << 28;
+const ArrayModes Float64ArrayMode = 1 << 29;
 
 inline constexpr ArrayModes asArrayModes(IndexingType indexingMode)
 {
-    if (isCopyOnWrite(indexingMode)) {
-        switch (indexingMode) {
-        case CopyOnWriteArrayWithInt32:
-            return CopyOnWriteArrayWithInt32ArrayMode;
-        case CopyOnWriteArrayWithDouble:
-            return CopyOnWriteArrayWithDoubleArrayMode;
-        case CopyOnWriteArrayWithContiguous:
-            return CopyOnWriteArrayWithContiguousArrayMode;
-        default:
-            UNREACHABLE_FOR_PLATFORM();
-            return 0;
-        }
-    }
-
     return static_cast<unsigned>(1) << static_cast<unsigned>(indexingMode);
 }
 
@@ -221,26 +212,15 @@ inline bool hasSeenCopyOnWriteArray(ArrayModes arrayModes)
 class ArrayProfile {
 public:
     ArrayProfile()
-        : m_bytecodeOffset(std::numeric_limits<unsigned>::max())
-        , m_lastSeenStructureID(0)
-        , m_mayStoreToHole(false)
-        , m_outOfBounds(false)
-        , m_mayInterceptIndexedAccesses(false)
-        , m_usesOriginalArrayStructures(true)
-        , m_didPerformFirstRunPruning(false)
-        , m_observedArrayModes(0)
+        : ArrayProfile(std::numeric_limits<unsigned>::max())
     {
     }
     
-    ArrayProfile(unsigned bytecodeOffset)
+    explicit ArrayProfile(unsigned bytecodeOffset)
         : m_bytecodeOffset(bytecodeOffset)
-        , m_lastSeenStructureID(0)
-        , m_mayStoreToHole(false)
-        , m_outOfBounds(false)
         , m_mayInterceptIndexedAccesses(false)
         , m_usesOriginalArrayStructures(true)
         , m_didPerformFirstRunPruning(false)
-        , m_observedArrayModes(0)
     {
     }
     
@@ -252,7 +232,9 @@ public:
 
     void setOutOfBounds() { m_outOfBounds = true; }
     bool* addressOfOutOfBounds() { return &m_outOfBounds; }
-    
+
+    unsigned* addressOfObservedIndexingModes() { return &m_observedIndexingModes; }
+
     void observeStructure(Structure* structure)
     {
         m_lastSeenStructureID = structure->id();
@@ -265,6 +247,7 @@ public:
     void observeIndexedRead(VM&, JSCell*, unsigned index);
 
     ArrayModes observedArrayModes(const ConcurrentJSLocker&) const { return m_observedArrayModes; }
+    IndexingType observedIndexingModes(const ConcurrentJSLocker&) const { return m_observedIndexingModes; }
     bool mayInterceptIndexedAccesses(const ConcurrentJSLocker&) const { return m_mayInterceptIndexedAccesses; }
     
     bool mayStoreToHole(const ConcurrentJSLocker&) const { return m_mayStoreToHole; }
@@ -281,13 +264,14 @@ private:
     static Structure* polymorphicStructure() { return static_cast<Structure*>(reinterpret_cast<void*>(1)); }
     
     unsigned m_bytecodeOffset;
-    StructureID m_lastSeenStructureID;
-    bool m_mayStoreToHole; // This flag may become overloaded to indicate other special cases that were encountered during array access, as it depends on indexing type. Since we currently have basically just one indexing type (two variants of ArrayStorage), this flag for now just means exactly what its name implies.
-    bool m_outOfBounds;
+    StructureID m_lastSeenStructureID { 0 };
+    ArrayModes m_observedArrayModes { 0 };
+    unsigned m_observedIndexingModes { 0 };
+    bool m_mayStoreToHole { false }; // This flag may become overloaded to indicate other special cases that were encountered during array access, as it depends on indexing type. Since we currently have basically just one indexing type (two variants of ArrayStorage), this flag for now just means exactly what its name implies.
+    bool m_outOfBounds { false };
     bool m_mayInterceptIndexedAccesses : 1;
     bool m_usesOriginalArrayStructures : 1;
     bool m_didPerformFirstRunPruning : 1;
-    ArrayModes m_observedArrayModes;
 };
 
 typedef SegmentedVector<ArrayProfile, 4> ArrayProfileVector;
index dfd68e6..8b3087f 100644 (file)
@@ -57,6 +57,10 @@ ArrayMode ArrayMode::fromObserved(const ConcurrentJSLocker& locker, ArrayProfile
         } else
             isArray = Array::Array;
 
+        bool includesCopyOnWrite = isCopyOnWrite(profile->observedIndexingModes(locker));
+        if (includesCopyOnWrite && !(observed & asArrayModes(toIndexingShape(type) | ArrayClass | CopyOnWrite)))
+            observed |= asArrayModes(toIndexingShape(type) | ArrayClass | CopyOnWrite);
+
         if (action == Array::Write && (observed & asArrayModes(toIndexingShape(type) | ArrayClass | CopyOnWrite)))
             converts = Array::Convert;
         else
index 0ac2ecc..f4b77e8 100644 (file)
@@ -208,9 +208,10 @@ public:
         if (isJSArray()) {
             if (profile->usesOriginalArrayStructures(locker) && benefitsFromOriginalArray()) {
                 ArrayModes arrayModes = profile->observedArrayModes(locker);
-                if (hasSeenCopyOnWriteArray(arrayModes) && !hasSeenWritableArray(arrayModes))
+                IndexingType observedIndexingModes = profile->observedIndexingModes(locker);
+                if ((hasSeenCopyOnWriteArray(arrayModes) || isCopyOnWrite(observedIndexingModes)) && !hasSeenWritableArray(arrayModes))
                     myArrayClass = Array::OriginalCopyOnWriteArray;
-                else if (!hasSeenCopyOnWriteArray(arrayModes) && hasSeenWritableArray(arrayModes))
+                else if ((!hasSeenCopyOnWriteArray(arrayModes) && !isCopyOnWrite(observedIndexingModes)) && hasSeenWritableArray(arrayModes))
                     myArrayClass = Array::OriginalArray;
                 else
                     myArrayClass = Array::Array;
index 50ab48b..538c894 100644 (file)
@@ -164,10 +164,13 @@ void JIT::compileOpCall(OpcodeID opcodeID, Instruction* instruction, unsigned ca
         int registerOffset = -instruction[4].u.operand;
 
         if (opcodeID == op_call && shouldEmitProfiling()) {
+            ArrayProfile* arrayProfile = instruction[OPCODE_LENGTH(op_call) - 2].u.arrayProfile;
             emitGetVirtualRegister(registerOffset + CallFrame::argumentOffsetIncludingThis(0), regT0);
             Jump done = branchIfNotCell(regT0);
-            load32(Address(regT0, JSCell::structureIDOffset()), regT0);
-            store32(regT0, instruction[OPCODE_LENGTH(op_call) - 2].u.arrayProfile->addressOfLastSeenStructureID());
+            load32(Address(regT0, JSCell::structureIDOffset()), regT1);
+            store32(regT1, arrayProfile->addressOfLastSeenStructureID());
+            load8(Address(regT0, JSCell::indexingTypeAndMiscOffset()), regT1);
+            or32(regT1, AbsoluteAddress(arrayProfile->addressOfObservedIndexingModes()));
             done.link(this);
         }
     
index 88bef12..d3f7eb0 100644 (file)
@@ -248,10 +248,13 @@ void JIT::compileOpCall(OpcodeID opcodeID, Instruction* instruction, unsigned ca
         int registerOffset = -instruction[4].u.operand;
         
         if (opcodeID == op_call && shouldEmitProfiling()) {
+            ArrayProfile* arrayProfile = instruction[OPCODE_LENGTH(op_call) - 2].u.arrayProfile;
             emitLoad(registerOffset + CallFrame::argumentOffsetIncludingThis(0), regT0, regT1);
             Jump done = branchIfNotCell(regT0);
-            loadPtr(Address(regT1, JSCell::structureIDOffset()), regT1);
-            storePtr(regT1, instruction[OPCODE_LENGTH(op_call) - 2].u.arrayProfile->addressOfLastSeenStructureID());
+            loadPtr(Address(regT1, JSCell::structureIDOffset()), regT0);
+            storePtr(regT0, arrayProfile->addressOfLastSeenStructureID());
+            load8(Address(regT1, JSCell::indexingTypeAndMiscOffset()), regT0);
+            or32(regT0, AbsoluteAddress(arrayProfile->addressOfObservedIndexingModes()));
             done.link(this);
         }
     
index 2bb67f1..a190b0a 100644 (file)
@@ -348,6 +348,8 @@ inline void JIT::emitArrayProfilingSiteWithCell(RegisterID cell, RegisterID inde
     }
 
     load8(Address(cell, JSCell::indexingTypeAndMiscOffset()), indexingType);
+    if (shouldEmitProfiling())
+        or32(indexingType, AbsoluteAddress(arrayProfile->addressOfObservedIndexingModes()));
 }
 
 inline void JIT::emitArrayProfilingSiteForBytecodeIndexWithCell(RegisterID cell, RegisterID indexingType, unsigned bytecodeIndex)
index 88b80d3..15bccde 100644 (file)
@@ -931,6 +931,7 @@ macro arrayProfile(cellAndIndexingType, profile, scratch)
     loadi JSCell::m_structureID[cell], scratch
     storei scratch, ArrayProfile::m_lastSeenStructureID[profile]
     loadb JSCell::m_indexingTypeAndMisc[cell], indexingType
+    ori indexingType, ArrayProfile::m_observedIndexingModes[profile]
 end
 
 macro skipIfIsRememberedOrInEden(cell, slowPath)
index 80f41d8..3982461 100644 (file)
@@ -1990,9 +1990,11 @@ macro arrayProfileForCall()
     negi t3
     bineq ThisArgumentOffset + TagOffset[cfr, t3, 8], CellTag, .done
     loadi ThisArgumentOffset + PayloadOffset[cfr, t3, 8], t0
-    loadp JSCell::m_structureID[t0], t0
+    loadp JSCell::m_structureID[t0], t3
     loadpFromInstruction(CallOpCodeSize - 2, t1)
-    storep t0, ArrayProfile::m_lastSeenStructureID[t1]
+    storep t3, ArrayProfile::m_lastSeenStructureID[t1]
+    loadb JSCell::m_indexingTypeAndMisc[t0], t3
+    ori t3, ArrayProfile::m_observedIndexingModes[t1]
 .done:
 end
 
index f867597..d85c855 100644 (file)
@@ -2033,6 +2033,8 @@ macro arrayProfileForCall()
     loadpFromInstruction((CallOpCodeSize - 2), t1)
     loadi JSCell::m_structureID[t0], t3
     storei t3, ArrayProfile::m_lastSeenStructureID[t1]
+    loadb JSCell::m_indexingTypeAndMisc[t0], t3
+    ori t3, ArrayProfile::m_observedIndexingModes[t1]
 .done:
 end