DFG::InsertionSet should be tolerant of occasional out-of-order insertions
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 24 Aug 2015 21:11:17 +0000 (21:11 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 24 Aug 2015 21:11:17 +0000 (21:11 +0000)
https://bugs.webkit.org/show_bug.cgi?id=148367

Reviewed by Geoffrey Garen and Saam Barati.

Since forever, the DFG::InsertionSet has been the way we insert nodes into DFG IR, and it
requires that you walk a block in order and perform insertions in order: you can't insert
something at index J, then at index I where I < J, except if you do a second pass.

This restriction makes sense, because it enables a very fast algorithm. And it's very
rare that a phase would need to insert things out of order.

But sometimes - rarely - we need to insert things slightly out-of-order. For example we
may want to insert a node at index J, but to insert a check associated with that node, we
may need to use index I where I < J. This will come up from the work on
https://bugs.webkit.org/show_bug.cgi?id=145204. And it has already come up in the past.
It seems like it would be best to just lift this restriction.

* CMakeLists.txt:
* JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
* JavaScriptCore.xcodeproj/project.pbxproj:
* dfg/DFGInsertionSet.cpp: Added.
(JSC::DFG::InsertionSet::insertSlow):
* dfg/DFGInsertionSet.h:
(JSC::DFG::InsertionSet::InsertionSet):
(JSC::DFG::InsertionSet::graph):
(JSC::DFG::InsertionSet::insert):
(JSC::DFG::InsertionSet::execute):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@188879 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/DFGInsertionSet.cpp [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGInsertionSet.h

index bfea6db..a883dec 100644 (file)
@@ -187,6 +187,7 @@ set(JavaScriptCore_SOURCES
     dfg/DFGGraphSafepoint.cpp
     dfg/DFGHeapLocation.cpp
     dfg/DFGInPlaceAbstractState.cpp
+    dfg/DFGInsertionSet.cpp
     dfg/DFGIntegerCheckCombiningPhase.cpp
     dfg/DFGIntegerRangeOptimizationPhase.cpp
     dfg/DFGInvalidationPointInjectionPhase.cpp
index 87041d0..74d5c8b 100644 (file)
@@ -1,3 +1,34 @@
+2015-08-22  Filip Pizlo  <fpizlo@apple.com>
+
+        DFG::InsertionSet should be tolerant of occasional out-of-order insertions
+        https://bugs.webkit.org/show_bug.cgi?id=148367
+
+        Reviewed by Geoffrey Garen and Saam Barati.
+
+        Since forever, the DFG::InsertionSet has been the way we insert nodes into DFG IR, and it
+        requires that you walk a block in order and perform insertions in order: you can't insert
+        something at index J, then at index I where I < J, except if you do a second pass.
+
+        This restriction makes sense, because it enables a very fast algorithm. And it's very
+        rare that a phase would need to insert things out of order.
+
+        But sometimes - rarely - we need to insert things slightly out-of-order. For example we
+        may want to insert a node at index J, but to insert a check associated with that node, we
+        may need to use index I where I < J. This will come up from the work on
+        https://bugs.webkit.org/show_bug.cgi?id=145204. And it has already come up in the past.
+        It seems like it would be best to just lift this restriction.
+
+        * CMakeLists.txt:
+        * JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * dfg/DFGInsertionSet.cpp: Added.
+        (JSC::DFG::InsertionSet::insertSlow):
+        * dfg/DFGInsertionSet.h:
+        (JSC::DFG::InsertionSet::InsertionSet):
+        (JSC::DFG::InsertionSet::graph):
+        (JSC::DFG::InsertionSet::insert):
+        (JSC::DFG::InsertionSet::execute):
+
 2015-08-24  Yusuke Suzuki  <utatane.tea@gmail.com>
 
         Create ById IC for ByVal operation only when the specific Id comes more than once
index 1ceac8d..31382ff 100644 (file)
@@ -1,4 +1,4 @@
-<?xml version="1.0" encoding="utf-8"?>
+<?xml version="1.0" encoding="utf-8"?>
 <Project DefaultTargets="Build" ToolsVersion="14.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
   <ItemGroup Label="ProjectConfigurations">
     <ProjectConfiguration Include="DebugSuffix|Win32">
     <ClCompile Include="..\dfg\DFGGraphSafepoint.cpp" />
     <ClCompile Include="..\dfg\DFGHeapLocation.cpp" />
     <ClCompile Include="..\dfg\DFGInPlaceAbstractState.cpp" />
+    <ClCompile Include="..\dfg\DFGInsertionSet.cpp" />
     <ClCompile Include="..\dfg\DFGIntegerCheckCombiningPhase.cpp" />
     <ClCompile Include="..\dfg\DFGIntegerRangeOptimizationPhase.cpp" />
     <ClCompile Include="..\dfg\DFGInvalidationPointInjectionPhase.cpp" />
index dda190b..78dc0b6 100644 (file)
                0F3B3A2C15475002003ED0FF /* DFGValidate.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F3B3A2A15474FF4003ED0FF /* DFGValidate.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F3B7E2A19A11B8000D9BC56 /* CallVariant.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F3B7E2419A11B8000D9BC56 /* CallVariant.cpp */; };
                0F3B7E2B19A11B8000D9BC56 /* CallVariant.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F3B7E2519A11B8000D9BC56 /* CallVariant.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               0F3BD1B71B896A0700598AA6 /* DFGInsertionSet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F3BD1B61B896A0700598AA6 /* DFGInsertionSet.cpp */; };
                0F3E01AA19D353A500F61B7F /* DFGPrePostNumbering.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F3E01A819D353A500F61B7F /* DFGPrePostNumbering.cpp */; };
                0F3E01AB19D353A500F61B7F /* DFGPrePostNumbering.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F3E01A919D353A500F61B7F /* DFGPrePostNumbering.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F426A481460CBB300131F8F /* ValueRecovery.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F426A451460CBAB00131F8F /* ValueRecovery.h */; settings = {ATTRIBUTES = (Private, ); }; };
                E33F50851B8437A000413856 /* JSInternalPromiseDeferred.h in Headers */ = {isa = PBXBuildFile; fileRef = E33F50831B8437A000413856 /* JSInternalPromiseDeferred.h */; settings = {ATTRIBUTES = (Private, ); }; };
                E33F50871B8449EF00413856 /* JSInternalPromiseConstructor.lut.h in Headers */ = {isa = PBXBuildFile; fileRef = E33F50861B8449EF00413856 /* JSInternalPromiseConstructor.lut.h */; };
                E354622B1B6065D100545386 /* ConstructAbility.h in Headers */ = {isa = PBXBuildFile; fileRef = E354622A1B6065D100545386 /* ConstructAbility.h */; settings = {ATTRIBUTES = (Private, ); }; };
-               E35E035F1B7AB43E0073AD2A /* InspectorInstrumentationObject.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E35E035D1B7AB43E0073AD2A /* InspectorInstrumentationObject.cpp */; };
-               E35E03601B7AB43E0073AD2A /* InspectorInstrumentationObject.h in Headers */ = {isa = PBXBuildFile; fileRef = E35E035E1B7AB43E0073AD2A /* InspectorInstrumentationObject.h */; settings = {ATTRIBUTES = (Private, ); }; };
                E355F3521B7DC85300C50DC5 /* ModuleLoaderObject.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E355F3501B7DC85300C50DC5 /* ModuleLoaderObject.cpp */; };
                E355F3531B7DC85300C50DC5 /* ModuleLoaderObject.h in Headers */ = {isa = PBXBuildFile; fileRef = E355F3511B7DC85300C50DC5 /* ModuleLoaderObject.h */; };
+               E35E035F1B7AB43E0073AD2A /* InspectorInstrumentationObject.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E35E035D1B7AB43E0073AD2A /* InspectorInstrumentationObject.cpp */; };
+               E35E03601B7AB43E0073AD2A /* InspectorInstrumentationObject.h in Headers */ = {isa = PBXBuildFile; fileRef = E35E035E1B7AB43E0073AD2A /* InspectorInstrumentationObject.h */; settings = {ATTRIBUTES = (Private, ); }; };
                E3794E751B77EB97005543AE /* ModuleAnalyzer.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E3794E731B77EB97005543AE /* ModuleAnalyzer.cpp */; };
                E3794E761B77EB97005543AE /* ModuleAnalyzer.h in Headers */ = {isa = PBXBuildFile; fileRef = E3794E741B77EB97005543AE /* ModuleAnalyzer.h */; settings = {ATTRIBUTES = (Private, ); }; };
                E3963CEE1B73F75000EB4CE5 /* NodesAnalyzeModule.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E3963CEC1B73F75000EB4CE5 /* NodesAnalyzeModule.cpp */; };
                0F3B3A2A15474FF4003ED0FF /* DFGValidate.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGValidate.h; path = dfg/DFGValidate.h; sourceTree = "<group>"; };
                0F3B7E2419A11B8000D9BC56 /* CallVariant.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CallVariant.cpp; sourceTree = "<group>"; };
                0F3B7E2519A11B8000D9BC56 /* CallVariant.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CallVariant.h; sourceTree = "<group>"; };
+               0F3BD1B61B896A0700598AA6 /* DFGInsertionSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGInsertionSet.cpp; path = dfg/DFGInsertionSet.cpp; sourceTree = "<group>"; };
                0F3E01A819D353A500F61B7F /* DFGPrePostNumbering.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGPrePostNumbering.cpp; path = dfg/DFGPrePostNumbering.cpp; sourceTree = "<group>"; };
                0F3E01A919D353A500F61B7F /* DFGPrePostNumbering.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGPrePostNumbering.h; path = dfg/DFGPrePostNumbering.h; sourceTree = "<group>"; };
                0F426A451460CBAB00131F8F /* ValueRecovery.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ValueRecovery.h; sourceTree = "<group>"; };
                E33F507F1B8429A400413856 /* JSInternalPromise.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JSInternalPromise.h; sourceTree = "<group>"; };
                E33F50821B8437A000413856 /* JSInternalPromiseDeferred.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JSInternalPromiseDeferred.cpp; sourceTree = "<group>"; };
                E33F50831B8437A000413856 /* JSInternalPromiseDeferred.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JSInternalPromiseDeferred.h; sourceTree = "<group>"; };
-               E33F50861B8449EF00413856 /* JSInternalPromiseConstructor.lut.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = JSInternalPromiseConstructor.lut.h; path = JSInternalPromiseConstructor.lut.h; sourceTree = "<group>"; };
+               E33F50861B8449EF00413856 /* JSInternalPromiseConstructor.lut.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JSInternalPromiseConstructor.lut.h; sourceTree = "<group>"; };
                E33F50881B844A1A00413856 /* InternalPromiseConstructor.js */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.javascript; path = InternalPromiseConstructor.js; sourceTree = "<group>"; };
                E354622A1B6065D100545386 /* ConstructAbility.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ConstructAbility.h; sourceTree = "<group>"; };
+               E355F3501B7DC85300C50DC5 /* ModuleLoaderObject.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ModuleLoaderObject.cpp; sourceTree = "<group>"; };
+               E355F3511B7DC85300C50DC5 /* ModuleLoaderObject.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ModuleLoaderObject.h; sourceTree = "<group>"; };
                E35E035D1B7AB43E0073AD2A /* InspectorInstrumentationObject.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = InspectorInstrumentationObject.cpp; sourceTree = "<group>"; };
                E35E035E1B7AB43E0073AD2A /* InspectorInstrumentationObject.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = InspectorInstrumentationObject.h; sourceTree = "<group>"; };
                E35E03611B7AB4850073AD2A /* InspectorInstrumentationObject.js */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.javascript; path = InspectorInstrumentationObject.js; sourceTree = "<group>"; };
-               E355F3501B7DC85300C50DC5 /* ModuleLoaderObject.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ModuleLoaderObject.cpp; sourceTree = "<group>"; };
-               E355F3511B7DC85300C50DC5 /* ModuleLoaderObject.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ModuleLoaderObject.h; sourceTree = "<group>"; };
                E3794E731B77EB97005543AE /* ModuleAnalyzer.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ModuleAnalyzer.cpp; sourceTree = "<group>"; };
                E3794E741B77EB97005543AE /* ModuleAnalyzer.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ModuleAnalyzer.h; sourceTree = "<group>"; };
                E3963CEC1B73F75000EB4CE5 /* NodesAnalyzeModule.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = NodesAnalyzeModule.cpp; sourceTree = "<group>"; };
                                0FB14E2218130955009B6B4D /* DFGInlineCacheWrapperInlines.h */,
                                A704D90017A0BAA8006BA554 /* DFGInPlaceAbstractState.cpp */,
                                A704D90117A0BAA8006BA554 /* DFGInPlaceAbstractState.h */,
+                               0F3BD1B61B896A0700598AA6 /* DFGInsertionSet.cpp */,
                                0F2BDC1F151E803800CD8910 /* DFGInsertionSet.h */,
                                0F300B7918AB1B1400A6D72E /* DFGIntegerCheckCombiningPhase.cpp */,
                                0F300B7A18AB1B1400A6D72E /* DFGIntegerCheckCombiningPhase.h */,
                                E33F50841B8437A000413856 /* JSInternalPromiseDeferred.cpp in Sources */,
                                0F9D36941AE9CC33000D4DFB /* DFGCleanUpPhase.cpp in Sources */,
                                A7D89CF717A0B8CC00773AD8 /* DFGFlushFormat.cpp in Sources */,
+                               0F3BD1B71B896A0700598AA6 /* DFGInsertionSet.cpp in Sources */,
                                7B39F76D1B62DE2E00360FB4 /* WASMModuleParser.cpp in Sources */,
                                0F3A1BF91A9ECB7D000DE01A /* DFGPutStackSinkingPhase.cpp in Sources */,
                                86EC9DC71328DF82002B2AD7 /* DFGGraph.cpp in Sources */,
diff --git a/Source/JavaScriptCore/dfg/DFGInsertionSet.cpp b/Source/JavaScriptCore/dfg/DFGInsertionSet.cpp
new file mode 100644 (file)
index 0000000..c2d95f9
--- /dev/null
@@ -0,0 +1,56 @@
+/*
+ * 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 "DFGInsertionSet.h"
+
+#if ENABLE(DFG_JIT)
+
+namespace JSC { namespace DFG {
+
+void InsertionSet::insertSlow(const Insertion& insertion)
+{
+    ASSERT(!m_insertions.isEmpty());
+    ASSERT(m_insertions.last().index() > insertion.index());
+    
+    for (size_t index = m_insertions.size() - 1; index--;) {
+        if (m_insertions[index].index() <= insertion.index()) {
+            m_insertions.insert(index + 1, insertion);
+            return;
+        }
+    }
+
+    RELEASE_ASSERT_NOT_REACHED();
+}
+
+void InsertionSet::execute(BasicBlock* block)
+{
+    executeInsertions(*block, m_insertions);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
index 966c086..57ff55f 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2012, 2013, 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2012-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
@@ -44,11 +44,17 @@ public:
     }
     
     Graph& graph() { return m_graph; }
-    
+
+    // Adds another code insertion. It's expected that you'll usually insert things in order. If
+    // you don't, this function will perform a linear search to find the largest insertion point
+    // at which insertion order would be preserved. This is essentially equivalent to if you did
+    // a stable sort on the insertions.
     Node* insert(const Insertion& insertion)
     {
-        ASSERT(!m_insertions.size() || m_insertions.last().index() <= insertion.index());
-        m_insertions.append(insertion);
+        if (LIKELY(!m_insertions.size() || m_insertions.last().index() <= insertion.index()))
+            m_insertions.append(insertion);
+        else
+            insertSlow(insertion);
         return insertion.element();
     }
     
@@ -123,11 +129,11 @@ public:
         return nullptr;
     }
     
-    void execute(BasicBlock* block)
-    {
-        executeInsertions(*block, m_insertions);
-    }
+    void execute(BasicBlock* block);
+
 private:
+    void insertSlow(const Insertion&);
+    
     Graph& m_graph;
     Vector<Insertion, 8> m_insertions;
 };