It should be possible to hoist all constants in DFG SSA
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 9 Jun 2015 00:45:59 +0000 (00:45 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 9 Jun 2015 00:45:59 +0000 (00:45 +0000)
https://bugs.webkit.org/show_bug.cgi?id=145769

Reviewed by Geoffrey Garen.

It's sometimes somewhat more efficient, and convenient, to have all constants at the
top of the root block. We don't require this as an IR invariant because too many phases
want to be able to insert constants in weird places. But, this phase will be great for
preparing for https://bugs.webkit.org/show_bug.cgi?id=145768.

* CMakeLists.txt:
* JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
* JavaScriptCore.xcodeproj/project.pbxproj:
* dfg/DFGConstantHoistingPhase.cpp: Added.
(JSC::DFG::performConstantHoisting):
* dfg/DFGConstantHoistingPhase.h: Added.
* dfg/DFGPlan.cpp:
(JSC::DFG::Plan::compileInThreadImpl):

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

Source/JavaScriptCore/CMakeLists.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/dfg/DFGConstantHoistingPhase.cpp [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGConstantHoistingPhase.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGPlan.cpp

index d34d3c3..7637f3c 100644 (file)
@@ -154,6 +154,7 @@ set(JavaScriptCore_SOURCES
     dfg/DFGCompilationKey.cpp
     dfg/DFGCompilationMode.cpp
     dfg/DFGConstantFoldingPhase.cpp
+    dfg/DFGConstantHoistingPhase.cpp
     dfg/DFGCriticalEdgeBreakingPhase.cpp
     dfg/DFGDCEPhase.cpp
     dfg/DFGDesiredIdentifiers.cpp
index ed7b1ae..622bdf7 100644 (file)
@@ -1,3 +1,24 @@
+2015-06-08  Filip Pizlo  <fpizlo@apple.com>
+
+        It should be possible to hoist all constants in DFG SSA
+        https://bugs.webkit.org/show_bug.cgi?id=145769
+
+        Reviewed by Geoffrey Garen.
+        
+        It's sometimes somewhat more efficient, and convenient, to have all constants at the
+        top of the root block. We don't require this as an IR invariant because too many phases
+        want to be able to insert constants in weird places. But, this phase will be great for
+        preparing for https://bugs.webkit.org/show_bug.cgi?id=145768.
+
+        * CMakeLists.txt:
+        * JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * dfg/DFGConstantHoistingPhase.cpp: Added.
+        (JSC::DFG::performConstantHoisting):
+        * dfg/DFGConstantHoistingPhase.h: Added.
+        * dfg/DFGPlan.cpp:
+        (JSC::DFG::Plan::compileInThreadImpl):
+
 2015-06-07  Filip Pizlo  <fpizlo@apple.com>
 
         The tiny set magic in StructureSet should be available in WTF
index 6c3066a..2ea4034 100644 (file)
     <ClCompile Include="..\dfg\DFGCompilationKey.cpp" />
     <ClCompile Include="..\dfg\DFGCompilationMode.cpp" />
     <ClCompile Include="..\dfg\DFGConstantFoldingPhase.cpp" />
+    <ClCompile Include="..\dfg\DFGConstantHoistingPhase.cpp" />
     <ClCompile Include="..\dfg\DFGCPSRethreadingPhase.cpp" />
     <ClCompile Include="..\dfg\DFGCriticalEdgeBreakingPhase.cpp" />
     <ClCompile Include="..\dfg\DFGCSEPhase.cpp" />
     <ClInclude Include="..\dfg\DFGCompilationKey.h" />
     <ClInclude Include="..\dfg\DFGCompilationMode.h" />
     <ClInclude Include="..\dfg\DFGConstantFoldingPhase.h" />
+    <ClInclude Include="..\dfg\DFGConstantHoistingPhase.h" />
     <ClInclude Include="..\dfg\DFGCPSRethreadingPhase.h" />
     <ClInclude Include="..\dfg\DFGCriticalEdgeBreakingPhase.h" />
     <ClInclude Include="..\dfg\DFGCSEPhase.h" />
index 8e62d1b..38cbe50 100644 (file)
                0FEA0A33170D40BF00BB722C /* DFGJITCode.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FEA0A2F170D40BF00BB722C /* DFGJITCode.cpp */; };
                0FEA0A34170D40BF00BB722C /* DFGJITCode.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEA0A30170D40BF00BB722C /* DFGJITCode.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0FEB3ECF16237F6C00AB67AD /* MacroAssembler.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FEB3ECE16237F6700AB67AD /* MacroAssembler.cpp */; };
+               0FED67B91B26256D0066CE15 /* DFGConstantHoistingPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FED67B71B26256D0066CE15 /* DFGConstantHoistingPhase.cpp */; };
+               0FED67BA1B26256D0066CE15 /* DFGConstantHoistingPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FED67B81B26256D0066CE15 /* DFGConstantHoistingPhase.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0FEE98411A8865B700754E93 /* SetupVarargsFrame.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEE98401A8865B600754E93 /* SetupVarargsFrame.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0FEE98431A89227500754E93 /* SetupVarargsFrame.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FEE98421A89227500754E93 /* SetupVarargsFrame.cpp */; };
                0FEFC9AA1681A3B300567F53 /* DFGOSRExitJumpPlaceholder.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FEFC9A71681A3B000567F53 /* DFGOSRExitJumpPlaceholder.cpp */; };
                0FEA0A2F170D40BF00BB722C /* DFGJITCode.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGJITCode.cpp; path = dfg/DFGJITCode.cpp; sourceTree = "<group>"; };
                0FEA0A30170D40BF00BB722C /* DFGJITCode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGJITCode.h; path = dfg/DFGJITCode.h; sourceTree = "<group>"; };
                0FEB3ECE16237F6700AB67AD /* MacroAssembler.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = MacroAssembler.cpp; sourceTree = "<group>"; };
+               0FED67B71B26256D0066CE15 /* DFGConstantHoistingPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGConstantHoistingPhase.cpp; path = dfg/DFGConstantHoistingPhase.cpp; sourceTree = "<group>"; };
+               0FED67B81B26256D0066CE15 /* DFGConstantHoistingPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGConstantHoistingPhase.h; path = dfg/DFGConstantHoistingPhase.h; sourceTree = "<group>"; };
                0FEE98401A8865B600754E93 /* SetupVarargsFrame.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SetupVarargsFrame.h; sourceTree = "<group>"; };
                0FEE98421A89227500754E93 /* SetupVarargsFrame.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SetupVarargsFrame.cpp; sourceTree = "<group>"; };
                0FEFC9A71681A3B000567F53 /* DFGOSRExitJumpPlaceholder.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGOSRExitJumpPlaceholder.cpp; path = dfg/DFGOSRExitJumpPlaceholder.cpp; sourceTree = "<group>"; };
                                0F38B01617CFE75500B144D3 /* DFGCompilationMode.h */,
                                0F3B3A17153E68EF003ED0FF /* DFGConstantFoldingPhase.cpp */,
                                0F3B3A18153E68EF003ED0FF /* DFGConstantFoldingPhase.h */,
+                               0FED67B71B26256D0066CE15 /* DFGConstantHoistingPhase.cpp */,
+                               0FED67B81B26256D0066CE15 /* DFGConstantHoistingPhase.h */,
                                0FBE0F6B16C1DB010082C5E8 /* DFGCPSRethreadingPhase.cpp */,
                                0FBE0F6C16C1DB010082C5E8 /* DFGCPSRethreadingPhase.h */,
                                A7D89CE617A0B8CC00773AD8 /* DFGCriticalEdgeBreakingPhase.cpp */,
                                0FEA0A241709606900BB722C /* FTLIntrinsicRepository.h in Headers */,
                                0FEA0A0E170513DB00BB722C /* FTLJITCode.h in Headers */,
                                A78A9781179738D5009DF744 /* FTLJITFinalizer.h in Headers */,
+                               0FED67BA1B26256D0066CE15 /* DFGConstantHoistingPhase.h in Headers */,
                                0F6B1CB6185FC9E900845D97 /* FTLJSCall.h in Headers */,
                                0F8F2B96172E04A3007DBDA5 /* FTLLink.h in Headers */,
                                0FCEFAE0180738C000472CE4 /* FTLLocation.h in Headers */,
                                14469DE6107EC7E700650446 /* ObjectPrototype.cpp in Sources */,
                                E124A8F80E555775003091F1 /* OpaqueJSString.cpp in Sources */,
                                969A079A0ED1D3AE00F1F681 /* Opcode.cpp in Sources */,
+                               0FED67B91B26256D0066CE15 /* DFGConstantHoistingPhase.cpp in Sources */,
                                14280850107EC0D70013E7B2 /* Operations.cpp in Sources */,
                                0FE228EE1436AB2C00196C48 /* Options.cpp in Sources */,
                                148F21BC107EC54D0042EC2C /* Parser.cpp in Sources */,
diff --git a/Source/JavaScriptCore/dfg/DFGConstantHoistingPhase.cpp b/Source/JavaScriptCore/dfg/DFGConstantHoistingPhase.cpp
new file mode 100644 (file)
index 0000000..68f3651
--- /dev/null
@@ -0,0 +1,149 @@
+/*
+ * Copyright (C) 2015 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 "DFGConstantHoistingPhase.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGGraph.h"
+#include "DFGInsertionSet.h"
+#include "DFGPhase.h"
+#include "DFGPredictionPropagationPhase.h"
+#include "DFGVariableAccessDataDump.h"
+#include "JSCInlines.h"
+
+namespace JSC { namespace DFG {
+
+namespace {
+
+class ConstantHoistingPhase : public Phase {
+public:
+    ConstantHoistingPhase(Graph& graph)
+        : Phase(graph, "constant hoisting")
+    {
+    }
+    
+    bool run()
+    {
+        DFG_ASSERT(m_graph, nullptr, m_graph.m_form == SSA);
+        
+        m_graph.clearReplacements();
+        
+        HashMap<FrozenValue*, Node*> jsValues;
+        HashMap<FrozenValue*, Node*> doubleValues;
+        HashMap<FrozenValue*, Node*> int52Values;
+        
+        auto valuesFor = [&] (NodeType op) -> HashMap<FrozenValue*, Node*>& {
+            // Use a roundabout approach because clang thinks that this closure returning a
+            // reference to a stack-allocated value in outer scope is a bug. It's not.
+            HashMap<FrozenValue*, Node*>* result;
+            
+            switch (op) {
+            case JSConstant:
+                result = &jsValues;
+                break;
+            case DoubleConstant:
+                result = &doubleValues;
+                break;
+            case Int52Constant:
+                result = &int52Values;
+                break;
+            default:
+                DFG_CRASH(m_graph, nullptr, "Invalid node type in valuesFor()");
+                result = nullptr;
+                break;
+            }
+            
+            return *result;
+        };
+        
+        Vector<Node*> toFree;
+        
+        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+            unsigned sourceIndex = 0;
+            unsigned targetIndex = 0;
+            while (sourceIndex < block->size()) {
+                Node* node = block->at(sourceIndex++);
+                switch (node->op()) {
+                case JSConstant:
+                case DoubleConstant:
+                case Int52Constant: {
+                    HashMap<FrozenValue*, Node*>& values = valuesFor(node->op());
+                    auto result = values.add(node->constant(), node);
+                    if (result.isNewEntry)
+                        node->origin = NodeOrigin();
+                    else {
+                        node->setReplacement(result.iterator->value);
+                        toFree.append(node);
+                    }
+                    break;
+                }
+                default:
+                    block->at(targetIndex++) = node;
+                    break;
+                }
+            }
+            block->resize(targetIndex);
+        }
+        
+        // Insert the constants into the root block.
+        InsertionSet insertionSet(m_graph);
+        auto insertConstants = [&] (const HashMap<FrozenValue*, Node*>& values) {
+            for (auto& entry : values)
+                insertionSet.insert(0, entry.value);
+        };
+        insertConstants(jsValues);
+        insertConstants(doubleValues);
+        insertConstants(int52Values);
+        insertionSet.execute(m_graph.block(0));
+        
+        // Perform all of the substitutions. We want all instances of the removed constants to
+        // point at their replacements.
+        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+            for (Node* node : *block)
+                m_graph.performSubstitution(node);
+        }
+        
+        // And finally free the constants that we removed.
+        for (Node* node : toFree)
+            m_graph.m_allocator.free(node);
+        
+        return true;
+    }
+};
+
+} // anonymous namespace
+    
+bool performConstantHoisting(Graph& graph)
+{
+    SamplingRegion samplingRegion("DFG Constant Hoisting Phase");
+    return runPhase<ConstantHoistingPhase>(graph);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
diff --git a/Source/JavaScriptCore/dfg/DFGConstantHoistingPhase.h b/Source/JavaScriptCore/dfg/DFGConstantHoistingPhase.h
new file mode 100644 (file)
index 0000000..5124f16
--- /dev/null
@@ -0,0 +1,43 @@
+/*
+ * Copyright (C) 2015 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 DFGConstantHoistingPhase_h
+#define DFGConstantHoistingPhase_h
+
+#if ENABLE(DFG_JIT)
+
+namespace JSC { namespace DFG {
+
+class Graph;
+
+// Hoists all constants to the top of the root block.
+
+bool performConstantHoisting(Graph&);
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGConstantHoistingPhase_h
index 0814dcb..a2e27d5 100644 (file)
@@ -37,6 +37,7 @@
 #include "DFGCSEPhase.h"
 #include "DFGCleanUpPhase.h"
 #include "DFGConstantFoldingPhase.h"
+#include "DFGConstantHoistingPhase.h"
 #include "DFGCriticalEdgeBreakingPhase.h"
 #include "DFGDCEPhase.h"
 #include "DFGFailedFinalizer.h"
@@ -353,6 +354,7 @@ Plan::CompilationPath Plan::compileInThreadImpl(LongLivedState& longLivedState)
         performArgumentsElimination(dfg);
         performPutStackSinking(dfg);
         
+        performConstantHoisting(dfg);
         performGlobalCSE(dfg);
         performLivenessAnalysis(dfg);
         performCFA(dfg);