DFG should have a precise view of jump targets
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 5 Feb 2013 22:14:31 +0000 (22:14 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 5 Feb 2013 22:14:31 +0000 (22:14 +0000)
https://bugs.webkit.org/show_bug.cgi?id=108868

Reviewed by Oliver Hunt.

Previously, the DFG relied entirely on the CodeBlock's jump targets list for
determining when to break basic blocks. This worked great, except sometimes it
would be too conservative since the CodeBlock just says where the bytecode
generator inserted labels.

This change keeps the old jump target list in CodeBlock since it is still
valuable to the baseline JIT, but switches the DFG to use its own jump target
calculator. This ought to reduce pressure on the DFG simplifier, which would
previously do a lot of work to try to merge redundantly created basic blocks.
It appears to be a 1% progression on SunSpider.

* CMakeLists.txt:
* GNUmakefile.list.am:
* JavaScriptCore.xcodeproj/project.pbxproj:
* Target.pri:
* bytecode/PreciseJumpTargets.cpp: Added.
(JSC):
(JSC::addSimpleSwitchTargets):
(JSC::computePreciseJumpTargets):
* bytecode/PreciseJumpTargets.h: Added.
(JSC):
* dfg/DFGByteCodeParser.cpp:
(JSC::DFG::ByteCodeParser::parseCodeBlock):

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

Source/JavaScriptCore/CMakeLists.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/GNUmakefile.list.am
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/Target.pri
Source/JavaScriptCore/bytecode/PreciseJumpTargets.cpp [new file with mode: 0644]
Source/JavaScriptCore/bytecode/PreciseJumpTargets.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp

index 31d3ce5..bbf1cb1 100644 (file)
@@ -58,8 +58,9 @@ set(JavaScriptCore_SOURCES
     bytecode/MethodOfGettingAValueProfile.cpp
     bytecode/Opcode.cpp
     bytecode/PolymorphicPutByIdList.cpp
-    bytecode/SpeculatedType.cpp
+    bytecode/PreciseJumpTargets.cpp
     bytecode/PutByIdStatus.cpp
+    bytecode/SpeculatedType.cpp
     bytecode/ReduceWhitespace.cpp
     bytecode/ResolveGlobalStatus.cpp
     bytecode/SamplingTool.cpp
index ca00bd8..ef76fca 100644 (file)
@@ -1,3 +1,34 @@
+2013-02-04  Filip Pizlo  <fpizlo@apple.com>
+
+        DFG should have a precise view of jump targets
+        https://bugs.webkit.org/show_bug.cgi?id=108868
+
+        Reviewed by Oliver Hunt.
+        
+        Previously, the DFG relied entirely on the CodeBlock's jump targets list for
+        determining when to break basic blocks. This worked great, except sometimes it
+        would be too conservative since the CodeBlock just says where the bytecode
+        generator inserted labels.
+        
+        This change keeps the old jump target list in CodeBlock since it is still
+        valuable to the baseline JIT, but switches the DFG to use its own jump target
+        calculator. This ought to reduce pressure on the DFG simplifier, which would
+        previously do a lot of work to try to merge redundantly created basic blocks.
+        It appears to be a 1% progression on SunSpider.
+
+        * CMakeLists.txt:
+        * GNUmakefile.list.am:
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * Target.pri:
+        * bytecode/PreciseJumpTargets.cpp: Added.
+        (JSC):
+        (JSC::addSimpleSwitchTargets):
+        (JSC::computePreciseJumpTargets):
+        * bytecode/PreciseJumpTargets.h: Added.
+        (JSC):
+        * dfg/DFGByteCodeParser.cpp:
+        (JSC::DFG::ByteCodeParser::parseCodeBlock):
+
 2013-02-01  Roger Fong  <roger_fong@apple.com>
 
         Make ConfigurationBuildDir include directories precede WebKitLibraries in JSC.
index 0b20588..f856852 100644 (file)
@@ -133,6 +133,8 @@ javascriptcore_sources += \
        Source/JavaScriptCore/bytecode/Operands.h \
        Source/JavaScriptCore/bytecode/PolymorphicPutByIdList.cpp \
        Source/JavaScriptCore/bytecode/PolymorphicPutByIdList.h \
+       Source/JavaScriptCore/bytecode/PreciseJumpTargets.cpp \
+       Source/JavaScriptCore/bytecode/PreciseJumpTargets.h \
        Source/JavaScriptCore/bytecode/SpeculatedType.cpp \
        Source/JavaScriptCore/bytecode/SpeculatedType.h \
        Source/JavaScriptCore/bytecode/PutByIdStatus.cpp \
index 67309e0..8598c62 100644 (file)
                0F963B3813FC6FE90002D9B2 /* ValueProfile.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F963B3613FC6FDE0002D9B2 /* ValueProfile.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F96EBB316676EF6008BADE3 /* CodeBlockWithJITType.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F96EBB116676EF4008BADE3 /* CodeBlockWithJITType.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F9749711687ADE400A4FF6A /* JSCellInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F97496F1687ADE200A4FF6A /* JSCellInlines.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               0F98206016BFE38100240D02 /* PreciseJumpTargets.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F98205D16BFE37F00240D02 /* PreciseJumpTargets.cpp */; };
+               0F98206116BFE38300240D02 /* PreciseJumpTargets.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F98205E16BFE37F00240D02 /* PreciseJumpTargets.h */; };
                0F9D3370165DBB90005AD387 /* Disassembler.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F9D336E165DBB8D005AD387 /* Disassembler.cpp */; };
                0F9FC8C314E1B5FE00D52AE0 /* PolymorphicPutByIdList.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F9FC8BF14E1B5FB00D52AE0 /* PolymorphicPutByIdList.cpp */; };
                0F9FC8C414E1B60000D52AE0 /* PolymorphicPutByIdList.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F9FC8C014E1B5FB00D52AE0 /* PolymorphicPutByIdList.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F963B3613FC6FDE0002D9B2 /* ValueProfile.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ValueProfile.h; sourceTree = "<group>"; };
                0F96EBB116676EF4008BADE3 /* CodeBlockWithJITType.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CodeBlockWithJITType.h; sourceTree = "<group>"; };
                0F97496F1687ADE200A4FF6A /* JSCellInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JSCellInlines.h; sourceTree = "<group>"; };
+               0F98205D16BFE37F00240D02 /* PreciseJumpTargets.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = PreciseJumpTargets.cpp; sourceTree = "<group>"; };
+               0F98205E16BFE37F00240D02 /* PreciseJumpTargets.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PreciseJumpTargets.h; sourceTree = "<group>"; };
                0F9D336E165DBB8D005AD387 /* Disassembler.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = Disassembler.cpp; path = disassembler/Disassembler.cpp; sourceTree = "<group>"; };
                0F9FC8BF14E1B5FB00D52AE0 /* PolymorphicPutByIdList.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = PolymorphicPutByIdList.cpp; sourceTree = "<group>"; };
                0F9FC8C014E1B5FB00D52AE0 /* PolymorphicPutByIdList.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PolymorphicPutByIdList.h; sourceTree = "<group>"; };
                                0F2BDC2B151FDE8B00CD8910 /* Operands.h */,
                                0F9FC8BF14E1B5FB00D52AE0 /* PolymorphicPutByIdList.cpp */,
                                0F9FC8C014E1B5FB00D52AE0 /* PolymorphicPutByIdList.h */,
+                               0F98205D16BFE37F00240D02 /* PreciseJumpTargets.cpp */,
+                               0F98205E16BFE37F00240D02 /* PreciseJumpTargets.h */,
                                0F93329914CA7DC10085F3C6 /* PutByIdStatus.cpp */,
                                0F93329A14CA7DC10085F3C6 /* PutByIdStatus.h */,
                                0F9FC8C114E1B5FB00D52AE0 /* PutKind.h */,
                                86704B8812DBA33700A9FE7B /* YarrParser.h in Headers */,
                                86704B8A12DBA33700A9FE7B /* YarrPattern.h in Headers */,
                                86704B4312DB8A8100A9FE7B /* YarrSyntaxChecker.h in Headers */,
+                               0F98206116BFE38300240D02 /* PreciseJumpTargets.h in Headers */,
                        );
                        runOnlyForDeploymentPostprocessing = 0;
                };
                                86704B8612DBA33700A9FE7B /* YarrJIT.cpp in Sources */,
                                86704B8912DBA33700A9FE7B /* YarrPattern.cpp in Sources */,
                                86704B4212DB8A8100A9FE7B /* YarrSyntaxChecker.cpp in Sources */,
+                               0F98206016BFE38100240D02 /* PreciseJumpTargets.cpp in Sources */,
                        );
                        runOnlyForDeploymentPostprocessing = 0;
                };
index f610aeb..8c1d07e 100644 (file)
@@ -68,6 +68,7 @@ SOURCES += \
     bytecode/MethodOfGettingAValueProfile.cpp \
     bytecode/Opcode.cpp \
     bytecode/PolymorphicPutByIdList.cpp \
+    bytecode/PreciseJumpTargets.cpp \
     bytecode/PutByIdStatus.cpp \
     bytecode/ReduceWhitespace.cpp \
     bytecode/ResolveGlobalStatus.cpp \
diff --git a/Source/JavaScriptCore/bytecode/PreciseJumpTargets.cpp b/Source/JavaScriptCore/bytecode/PreciseJumpTargets.cpp
new file mode 100644 (file)
index 0000000..87e1af8
--- /dev/null
@@ -0,0 +1,133 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "config.h"
+#include "PreciseJumpTargets.h"
+
+namespace JSC {
+
+static void addSimpleSwitchTargets(SimpleJumpTable& jumpTable, unsigned bytecodeOffset, Vector<unsigned, 32>& out)
+{
+    for (unsigned i = jumpTable.branchOffsets.size(); i--;)
+        out.append(bytecodeOffset + jumpTable.branchOffsets[i]);
+}
+
+void computePreciseJumpTargets(CodeBlock* codeBlock, Vector<unsigned, 32>& out)
+{
+    ASSERT(out.isEmpty());
+    
+    // We will derive a superset of the jump targets that the code block thinks it has.
+    // So, if the code block claims there are none, then we are done.
+    if (!codeBlock->numberOfJumpTargets())
+        return;
+    
+    for (unsigned i = codeBlock->numberOfExceptionHandlers(); i--;)
+        out.append(codeBlock->exceptionHandler(i).target);
+    
+    Interpreter* interpreter = codeBlock->globalData()->interpreter;
+    Instruction* instructionsBegin = codeBlock->instructions().begin();
+    unsigned instructionCount = codeBlock->instructions().size();
+    for (unsigned bytecodeOffset = 0; bytecodeOffset < instructionCount;) {
+        OpcodeID opcodeID = interpreter->getOpcodeID(instructionsBegin[bytecodeOffset].u.opcode);
+        Instruction* current = instructionsBegin + bytecodeOffset;
+        switch (opcodeID) {
+        case op_jmp:
+        case op_loop:
+            out.append(bytecodeOffset + current[1].u.operand);
+            break;
+        case op_jtrue:
+        case op_jfalse:
+        case op_jeq_null:
+        case op_jneq_null:
+        case op_jmp_scopes:
+        case op_loop_if_true:
+        case op_loop_if_false:
+            out.append(bytecodeOffset + current[2].u.operand);
+            break;
+        case op_jneq_ptr:
+        case op_jless:
+        case op_jlesseq:
+        case op_jgreater:
+        case op_jgreatereq:
+        case op_jnless:
+        case op_jnlesseq:
+        case op_jngreater:
+        case op_jngreatereq:
+        case op_loop_if_less:
+        case op_loop_if_lesseq:
+        case op_loop_if_greater:
+        case op_loop_if_greatereq:
+            out.append(bytecodeOffset + current[3].u.operand);
+            break;
+        case op_switch_imm:
+            addSimpleSwitchTargets(codeBlock->immediateSwitchJumpTable(current[1].u.operand), bytecodeOffset, out);
+            out.append(bytecodeOffset + current[2].u.operand);
+            break;
+        case op_switch_char:
+            addSimpleSwitchTargets(codeBlock->characterSwitchJumpTable(current[1].u.operand), bytecodeOffset, out);
+            out.append(bytecodeOffset + current[2].u.operand);
+            break;
+        case op_switch_string: {
+            StringJumpTable& table = codeBlock->stringSwitchJumpTable(current[1].u.operand);
+            StringJumpTable::StringOffsetTable::iterator iter = table.offsetTable.begin();
+            StringJumpTable::StringOffsetTable::iterator end = table.offsetTable.end();
+            for (; iter != end; ++iter)
+                out.append(bytecodeOffset + iter->value.branchOffset);
+            out.append(bytecodeOffset + current[2].u.operand);
+            break;
+        }
+        case op_get_pnames:
+            out.append(bytecodeOffset + current[5].u.operand);
+            break;
+        case op_next_pname:
+            out.append(bytecodeOffset + current[6].u.operand);
+            break;
+        case op_check_has_instance:
+            out.append(bytecodeOffset + current[4].u.operand);
+            break;
+        default:
+            break;
+        }
+        bytecodeOffset += opcodeLengths[opcodeID];
+    }
+    
+    std::sort(out.begin(), out.end());
+    
+    // We will have duplicates, and we must remove them.
+    unsigned toIndex = 0;
+    unsigned fromIndex = 0;
+    unsigned lastValue = UINT_MAX;
+    while (fromIndex < out.size()) {
+        unsigned value = out[fromIndex++];
+        if (value == lastValue)
+            continue;
+        out[toIndex++] = value;
+        lastValue = value;
+    }
+    out.resize(toIndex);
+}
+
+} // namespace JSC
+
diff --git a/Source/JavaScriptCore/bytecode/PreciseJumpTargets.h b/Source/JavaScriptCore/bytecode/PreciseJumpTargets.h
new file mode 100644 (file)
index 0000000..109c40c
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef PreciseJumpTargets_h
+#define PreciseJumpTargets_h
+
+#include "CodeBlock.h"
+
+namespace JSC {
+
+void computePreciseJumpTargets(CodeBlock*, Vector<unsigned, 32>& out);
+
+} // namespace JSC
+
+#endif // PreciseJumpTargets_h
+
index f96f3a2..39bbb8c 100644 (file)
 #include "DFGCapabilities.h"
 #include "GetByIdStatus.h"
 #include "JSCJSValueInlines.h"
+#include "PreciseJumpTargets.h"
 #include "PutByIdStatus.h"
 #include "ResolveGlobalStatus.h"
+#include <wtf/CommaPrinter.h>
 #include <wtf/HashMap.h>
 #include <wtf/MathExtras.h>
 
@@ -3630,9 +3632,19 @@ void ByteCodeParser::parseCodeBlock()
         codeBlock->baselineVersion()->dumpBytecode();
     }
     
-    for (unsigned jumpTargetIndex = 0; jumpTargetIndex <= codeBlock->numberOfJumpTargets(); ++jumpTargetIndex) {
+    Vector<unsigned, 32> jumpTargets;
+    computePreciseJumpTargets(codeBlock, jumpTargets);
+    if (Options::dumpBytecodeAtDFGTime()) {
+        dataLog("Jump targets: ");
+        CommaPrinter comma;
+        for (unsigned i = 0; i < jumpTargets.size(); ++i)
+            dataLog(comma, jumpTargets[i]);
+        dataLog("\n");
+    }
+    
+    for (unsigned jumpTargetIndex = 0; jumpTargetIndex <= jumpTargets.size(); ++jumpTargetIndex) {
         // The maximum bytecode offset to go into the current basicblock is either the next jump target, or the end of the instructions.
-        unsigned limit = jumpTargetIndex < codeBlock->numberOfJumpTargets() ? codeBlock->jumpTarget(jumpTargetIndex) : codeBlock->instructions().size();
+        unsigned limit = jumpTargetIndex < jumpTargets.size() ? jumpTargets[jumpTargetIndex] : codeBlock->instructions().size();
 #if DFG_ENABLE(DEBUG_VERBOSE)
         dataLog(
             "Parsing bytecode with limit ", pointerDump(m_inlineStackTop->m_inlineCallFrame),