- Revision
- 188879
- Author
- [email protected]
- Date
- 2015-08-24 14:11:17 -0700 (Mon, 24 Aug 2015)
Log Message
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:
* _javascript_Core.vcxproj/_javascript_Core.vcxproj:
* _javascript_Core.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):
Modified Paths
Added Paths
Diff
Modified: trunk/Source/_javascript_Core/CMakeLists.txt (188878 => 188879)
--- trunk/Source/_javascript_Core/CMakeLists.txt 2015-08-24 20:26:05 UTC (rev 188878)
+++ trunk/Source/_javascript_Core/CMakeLists.txt 2015-08-24 21:11:17 UTC (rev 188879)
@@ -187,6 +187,7 @@
dfg/DFGGraphSafepoint.cpp
dfg/DFGHeapLocation.cpp
dfg/DFGInPlaceAbstractState.cpp
+ dfg/DFGInsertionSet.cpp
dfg/DFGIntegerCheckCombiningPhase.cpp
dfg/DFGIntegerRangeOptimizationPhase.cpp
dfg/DFGInvalidationPointInjectionPhase.cpp
Modified: trunk/Source/_javascript_Core/ChangeLog (188878 => 188879)
--- trunk/Source/_javascript_Core/ChangeLog 2015-08-24 20:26:05 UTC (rev 188878)
+++ trunk/Source/_javascript_Core/ChangeLog 2015-08-24 21:11:17 UTC (rev 188879)
@@ -1,3 +1,34 @@
+2015-08-22 Filip Pizlo <[email protected]>
+
+ 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:
+ * _javascript_Core.vcxproj/_javascript_Core.vcxproj:
+ * _javascript_Core.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 <[email protected]>
Create ById IC for ByVal operation only when the specific Id comes more than once
Modified: trunk/Source/_javascript_Core/_javascript_Core.vcxproj/_javascript_Core.vcxproj (188878 => 188879)
--- trunk/Source/_javascript_Core/_javascript_Core.vcxproj/_javascript_Core.vcxproj 2015-08-24 20:26:05 UTC (rev 188878)
+++ trunk/Source/_javascript_Core/_javascript_Core.vcxproj/_javascript_Core.vcxproj 2015-08-24 21:11:17 UTC (rev 188879)
@@ -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">
@@ -423,6 +423,7 @@
<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" />
Modified: trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj (188878 => 188879)
--- trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2015-08-24 20:26:05 UTC (rev 188878)
+++ trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2015-08-24 21:11:17 UTC (rev 188879)
@@ -295,6 +295,7 @@
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, ); }; };
@@ -1709,10 +1710,10 @@
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, ); }; };
+ 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, ); }; };
- E355F3521B7DC85300C50DC5 /* ModuleLoaderObject.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E355F3501B7DC85300C50DC5 /* ModuleLoaderObject.cpp */; };
- E355F3531B7DC85300C50DC5 /* ModuleLoaderObject.h in Headers */ = {isa = PBXBuildFile; fileRef = E355F3511B7DC85300C50DC5 /* ModuleLoaderObject.h */; };
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 */; };
@@ -2106,6 +2107,7 @@
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>"; };
@@ -3556,14 +3558,14 @@
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>"; };
@@ -5189,6 +5191,7 @@
0FB14E2218130955009B6B4D /* DFGInlineCacheWrapperInlines.h */,
A704D90017A0BAA8006BA554 /* DFGInPlaceAbstractState.cpp */,
A704D90117A0BAA8006BA554 /* DFGInPlaceAbstractState.h */,
+ 0F3BD1B61B896A0700598AA6 /* DFGInsertionSet.cpp */,
0F2BDC1F151E803800CD8910 /* DFGInsertionSet.h */,
0F300B7918AB1B1400A6D72E /* DFGIntegerCheckCombiningPhase.cpp */,
0F300B7A18AB1B1400A6D72E /* DFGIntegerCheckCombiningPhase.h */,
@@ -7430,6 +7433,7 @@
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 */,
Added: trunk/Source/_javascript_Core/dfg/DFGInsertionSet.cpp (0 => 188879)
--- trunk/Source/_javascript_Core/dfg/DFGInsertionSet.cpp (rev 0)
+++ trunk/Source/_javascript_Core/dfg/DFGInsertionSet.cpp 2015-08-24 21:11:17 UTC (rev 188879)
@@ -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)
+
Modified: trunk/Source/_javascript_Core/dfg/DFGInsertionSet.h (188878 => 188879)
--- trunk/Source/_javascript_Core/dfg/DFGInsertionSet.h 2015-08-24 20:26:05 UTC (rev 188878)
+++ trunk/Source/_javascript_Core/dfg/DFGInsertionSet.h 2015-08-24 21:11:17 UTC (rev 188879)
@@ -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 @@
}
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 @@
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;
};
