Log Message
FTL should eliminate array bounds checks in loops https://bugs.webkit.org/show_bug.cgi?id=145768
Reviewed by Benjamin Poulain.
Source/_javascript_Core:
This adds a phase that does forward propagation of integer inequalities. This allows us
to do the algebraic reasoning we need to eliminate array bounds checks in loops. It
also eliminates overflow checks on ArithAdd with a constant.
The phase's analysis produces results that are powerful enough to do speculative bounds
check hoisting, but this phase currently only does elimination. We can implement
hoisting later.
On programs that just loop over an array like:
for (var i = 0; i < array.length; ++i)
thingy += array[i]
This change is a 60% speed-up.
This is also a ~3% speed-up on Kraken, and it shows various speed-ups on individual
tests in Octane.
* CMakeLists.txt:
* _javascript_Core.vcxproj/_javascript_Core.vcxproj:
* _javascript_Core.xcodeproj/project.pbxproj:
* dfg/DFGIntegerRangeOptimizationPhase.cpp: Added.
(JSC::DFG::performIntegerRangeOptimization):
* dfg/DFGIntegerRangeOptimizationPhase.h: Added.
* dfg/DFGPlan.cpp:
(JSC::DFG::Plan::compileInThreadImpl):
* tests/stress/add-overflows-after-not-equal.js: Added.
* tests/stress/no-abc-skippy-loop.js: Added.
* tests/stress/no-abc-skippy-paired-loop.js: Added.
* tests/stress/sub-overflows-after-not-equal.js: Added.
LayoutTests:
* js/regress/abc-forward-loop-equal-expected.txt: Added.
* js/regress/abc-forward-loop-equal.html: Added.
* js/regress/abc-postfix-backward-loop-expected.txt: Added.
* js/regress/abc-postfix-backward-loop.html: Added.
* js/regress/abc-skippy-loop-expected.txt: Added.
* js/regress/abc-skippy-loop.html: Added.
* js/regress/abc-simple-backward-loop-expected.txt: Added.
* js/regress/abc-simple-backward-loop.html: Added.
* js/regress/abc-simple-forward-loop-expected.txt: Added.
* js/regress/abc-simple-forward-loop.html: Added.
* js/regress/script-tests/abc-forward-loop-equal.js: Added.
* js/regress/script-tests/abc-postfix-backward-loop.js: Added.
* js/regress/script-tests/abc-skippy-loop.js: Added.
* js/regress/script-tests/abc-simple-backward-loop.js: Added.
* js/regress/script-tests/abc-simple-forward-loop.js: Added.
Modified Paths
- trunk/LayoutTests/ChangeLog
- trunk/Source/_javascript_Core/CMakeLists.txt
- trunk/Source/_javascript_Core/ChangeLog
- trunk/Source/_javascript_Core/_javascript_Core.vcxproj/_javascript_Core.vcxproj
- trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj
- trunk/Source/_javascript_Core/dfg/DFGPlan.cpp
Added Paths
- trunk/LayoutTests/js/regress/abc-forward-loop-equal-expected.txt
- trunk/LayoutTests/js/regress/abc-forward-loop-equal.html
- trunk/LayoutTests/js/regress/abc-postfix-backward-loop-expected.txt
- trunk/LayoutTests/js/regress/abc-postfix-backward-loop.html
- trunk/LayoutTests/js/regress/abc-simple-backward-loop-expected.txt
- trunk/LayoutTests/js/regress/abc-simple-backward-loop.html
- trunk/LayoutTests/js/regress/abc-simple-forward-loop-expected.txt
- trunk/LayoutTests/js/regress/abc-simple-forward-loop.html
- trunk/LayoutTests/js/regress/abc-skippy-loop-expected.txt
- trunk/LayoutTests/js/regress/abc-skippy-loop.html
- trunk/LayoutTests/js/regress/script-tests/abc-forward-loop-equal.js
- trunk/LayoutTests/js/regress/script-tests/abc-postfix-backward-loop.js
- trunk/LayoutTests/js/regress/script-tests/abc-simple-backward-loop.js
- trunk/LayoutTests/js/regress/script-tests/abc-simple-forward-loop.js
- trunk/LayoutTests/js/regress/script-tests/abc-skippy-loop.js
- trunk/Source/_javascript_Core/dfg/DFGIntegerRangeOptimizationPhase.cpp
- trunk/Source/_javascript_Core/dfg/DFGIntegerRangeOptimizationPhase.h
- trunk/Source/_javascript_Core/tests/stress/add-overflows-after-not-equal.js
- trunk/Source/_javascript_Core/tests/stress/no-abc-skippy-loop.js
- trunk/Source/_javascript_Core/tests/stress/no-abc-skippy-paired-loop.js
- trunk/Source/_javascript_Core/tests/stress/sub-overflows-after-not-equal.js
Diff
Modified: trunk/LayoutTests/ChangeLog (185639 => 185640)
--- trunk/LayoutTests/ChangeLog 2015-06-17 05:18:21 UTC (rev 185639)
+++ trunk/LayoutTests/ChangeLog 2015-06-17 05:31:30 UTC (rev 185640)
@@ -1,3 +1,26 @@
+2015-06-10 Filip Pizlo <fpi...@apple.com>
+
+ FTL should eliminate array bounds checks in loops
+ https://bugs.webkit.org/show_bug.cgi?id=145768
+
+ Reviewed by Benjamin Poulain.
+
+ * js/regress/abc-forward-loop-equal-expected.txt: Added.
+ * js/regress/abc-forward-loop-equal.html: Added.
+ * js/regress/abc-postfix-backward-loop-expected.txt: Added.
+ * js/regress/abc-postfix-backward-loop.html: Added.
+ * js/regress/abc-skippy-loop-expected.txt: Added.
+ * js/regress/abc-skippy-loop.html: Added.
+ * js/regress/abc-simple-backward-loop-expected.txt: Added.
+ * js/regress/abc-simple-backward-loop.html: Added.
+ * js/regress/abc-simple-forward-loop-expected.txt: Added.
+ * js/regress/abc-simple-forward-loop.html: Added.
+ * js/regress/script-tests/abc-forward-loop-equal.js: Added.
+ * js/regress/script-tests/abc-postfix-backward-loop.js: Added.
+ * js/regress/script-tests/abc-skippy-loop.js: Added.
+ * js/regress/script-tests/abc-simple-backward-loop.js: Added.
+ * js/regress/script-tests/abc-simple-forward-loop.js: Added.
+
2015-06-16 Gyuyoung Kim <gyuyoung....@webkit.org>
[EFL] Unreviewed, EFL gardening on 17th June.
Added: trunk/LayoutTests/js/regress/abc-forward-loop-equal-expected.txt (0 => 185640)
--- trunk/LayoutTests/js/regress/abc-forward-loop-equal-expected.txt (rev 0)
+++ trunk/LayoutTests/js/regress/abc-forward-loop-equal-expected.txt 2015-06-17 05:31:30 UTC (rev 185640)
@@ -0,0 +1,10 @@
+JSRegress/abc-forward-loop-equal
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
Added: trunk/LayoutTests/js/regress/abc-forward-loop-equal.html (0 => 185640)
--- trunk/LayoutTests/js/regress/abc-forward-loop-equal.html (rev 0)
+++ trunk/LayoutTests/js/regress/abc-forward-loop-equal.html 2015-06-17 05:31:30 UTC (rev 185640)
@@ -0,0 +1,12 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src=""
+</head>
+<body>
+<script src=""
+<script src=""
+<script src=""
+<script src=""
+</body>
+</html>
Added: trunk/LayoutTests/js/regress/abc-postfix-backward-loop-expected.txt (0 => 185640)
--- trunk/LayoutTests/js/regress/abc-postfix-backward-loop-expected.txt (rev 0)
+++ trunk/LayoutTests/js/regress/abc-postfix-backward-loop-expected.txt 2015-06-17 05:31:30 UTC (rev 185640)
@@ -0,0 +1,10 @@
+JSRegress/abc-postfix-backward-loop
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
Added: trunk/LayoutTests/js/regress/abc-postfix-backward-loop.html (0 => 185640)
--- trunk/LayoutTests/js/regress/abc-postfix-backward-loop.html (rev 0)
+++ trunk/LayoutTests/js/regress/abc-postfix-backward-loop.html 2015-06-17 05:31:30 UTC (rev 185640)
@@ -0,0 +1,12 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src=""
+</head>
+<body>
+<script src=""
+<script src=""
+<script src=""
+<script src=""
+</body>
+</html>
Added: trunk/LayoutTests/js/regress/abc-simple-backward-loop-expected.txt (0 => 185640)
--- trunk/LayoutTests/js/regress/abc-simple-backward-loop-expected.txt (rev 0)
+++ trunk/LayoutTests/js/regress/abc-simple-backward-loop-expected.txt 2015-06-17 05:31:30 UTC (rev 185640)
@@ -0,0 +1,10 @@
+JSRegress/abc-simple-backward-loop
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
Added: trunk/LayoutTests/js/regress/abc-simple-backward-loop.html (0 => 185640)
--- trunk/LayoutTests/js/regress/abc-simple-backward-loop.html (rev 0)
+++ trunk/LayoutTests/js/regress/abc-simple-backward-loop.html 2015-06-17 05:31:30 UTC (rev 185640)
@@ -0,0 +1,12 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src=""
+</head>
+<body>
+<script src=""
+<script src=""
+<script src=""
+<script src=""
+</body>
+</html>
Added: trunk/LayoutTests/js/regress/abc-simple-forward-loop-expected.txt (0 => 185640)
--- trunk/LayoutTests/js/regress/abc-simple-forward-loop-expected.txt (rev 0)
+++ trunk/LayoutTests/js/regress/abc-simple-forward-loop-expected.txt 2015-06-17 05:31:30 UTC (rev 185640)
@@ -0,0 +1,10 @@
+JSRegress/abc-simple-forward-loop
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
Added: trunk/LayoutTests/js/regress/abc-simple-forward-loop.html (0 => 185640)
--- trunk/LayoutTests/js/regress/abc-simple-forward-loop.html (rev 0)
+++ trunk/LayoutTests/js/regress/abc-simple-forward-loop.html 2015-06-17 05:31:30 UTC (rev 185640)
@@ -0,0 +1,12 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src=""
+</head>
+<body>
+<script src=""
+<script src=""
+<script src=""
+<script src=""
+</body>
+</html>
Added: trunk/LayoutTests/js/regress/abc-skippy-loop-expected.txt (0 => 185640)
--- trunk/LayoutTests/js/regress/abc-skippy-loop-expected.txt (rev 0)
+++ trunk/LayoutTests/js/regress/abc-skippy-loop-expected.txt 2015-06-17 05:31:30 UTC (rev 185640)
@@ -0,0 +1,10 @@
+JSRegress/abc-skippy-loop
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
Added: trunk/LayoutTests/js/regress/abc-skippy-loop.html (0 => 185640)
--- trunk/LayoutTests/js/regress/abc-skippy-loop.html (rev 0)
+++ trunk/LayoutTests/js/regress/abc-skippy-loop.html 2015-06-17 05:31:30 UTC (rev 185640)
@@ -0,0 +1,12 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src=""
+</head>
+<body>
+<script src=""
+<script src=""
+<script src=""
+<script src=""
+</body>
+</html>
Added: trunk/LayoutTests/js/regress/script-tests/abc-forward-loop-equal.js (0 => 185640)
--- trunk/LayoutTests/js/regress/script-tests/abc-forward-loop-equal.js (rev 0)
+++ trunk/LayoutTests/js/regress/script-tests/abc-forward-loop-equal.js 2015-06-17 05:31:30 UTC (rev 185640)
@@ -0,0 +1,14 @@
+function foo(array) {
+ var result = 0;
+ for (var i = 0; i != array.length; ++i)
+ result += array[i];
+ return result;
+}
+
+noInline(foo);
+
+var array = [];
+for (var i = 0; i < 1000; ++i)
+ array.push(i);
+for (var i = 0; i < 50000; ++i)
+ foo(array);
Added: trunk/LayoutTests/js/regress/script-tests/abc-postfix-backward-loop.js (0 => 185640)
--- trunk/LayoutTests/js/regress/script-tests/abc-postfix-backward-loop.js (rev 0)
+++ trunk/LayoutTests/js/regress/script-tests/abc-postfix-backward-loop.js 2015-06-17 05:31:30 UTC (rev 185640)
@@ -0,0 +1,14 @@
+function foo(array) {
+ var result = 0;
+ for (var i = array.length; i--;)
+ result += array[i];
+ return result;
+}
+
+noInline(foo);
+
+var array = [];
+for (var i = 0; i < 1000; ++i)
+ array.push(i);
+for (var i = 0; i < 50000; ++i)
+ foo(array);
Added: trunk/LayoutTests/js/regress/script-tests/abc-simple-backward-loop.js (0 => 185640)
--- trunk/LayoutTests/js/regress/script-tests/abc-simple-backward-loop.js (rev 0)
+++ trunk/LayoutTests/js/regress/script-tests/abc-simple-backward-loop.js 2015-06-17 05:31:30 UTC (rev 185640)
@@ -0,0 +1,14 @@
+function foo(array) {
+ var result = 0;
+ for (var i = array.length - 1; i >= 0; i--)
+ result += array[i];
+ return result;
+}
+
+noInline(foo);
+
+var array = [];
+for (var i = 0; i < 1000; ++i)
+ array.push(i);
+for (var i = 0; i < 50000; ++i)
+ foo(array);
Added: trunk/LayoutTests/js/regress/script-tests/abc-simple-forward-loop.js (0 => 185640)
--- trunk/LayoutTests/js/regress/script-tests/abc-simple-forward-loop.js (rev 0)
+++ trunk/LayoutTests/js/regress/script-tests/abc-simple-forward-loop.js 2015-06-17 05:31:30 UTC (rev 185640)
@@ -0,0 +1,14 @@
+function foo(array) {
+ var result = 0;
+ for (var i = 0; i < array.length; ++i)
+ result += array[i];
+ return result;
+}
+
+noInline(foo);
+
+var array = [];
+for (var i = 0; i < 1000; ++i)
+ array.push(i);
+for (var i = 0; i < 50000; ++i)
+ foo(array);
Added: trunk/LayoutTests/js/regress/script-tests/abc-skippy-loop.js (0 => 185640)
--- trunk/LayoutTests/js/regress/script-tests/abc-skippy-loop.js (rev 0)
+++ trunk/LayoutTests/js/regress/script-tests/abc-skippy-loop.js 2015-06-17 05:31:30 UTC (rev 185640)
@@ -0,0 +1,18 @@
+function foo(array) {
+ var result = 0;
+ for (var i = 0; i < array.length; i += 2) {
+ var element = array[i];
+ if (element === void 0)
+ break;
+ result += array[i];
+ }
+ return result;
+}
+
+noInline(foo);
+
+var array = [];
+for (var i = 0; i < 1000; ++i)
+ array.push(i);
+for (var i = 0; i < 50000; ++i)
+ foo(array);
Modified: trunk/Source/_javascript_Core/CMakeLists.txt (185639 => 185640)
--- trunk/Source/_javascript_Core/CMakeLists.txt 2015-06-17 05:18:21 UTC (rev 185639)
+++ trunk/Source/_javascript_Core/CMakeLists.txt 2015-06-17 05:31:30 UTC (rev 185640)
@@ -181,6 +181,7 @@
dfg/DFGInPlaceAbstractState.cpp
dfg/DFGInsertOSRHintsForUpdate.cpp
dfg/DFGIntegerCheckCombiningPhase.cpp
+ dfg/DFGIntegerRangeOptimizationPhase.cpp
dfg/DFGInvalidationPointInjectionPhase.cpp
dfg/DFGJITCode.cpp
dfg/DFGJITCompiler.cpp
Modified: trunk/Source/_javascript_Core/ChangeLog (185639 => 185640)
--- trunk/Source/_javascript_Core/ChangeLog 2015-06-17 05:18:21 UTC (rev 185639)
+++ trunk/Source/_javascript_Core/ChangeLog 2015-06-17 05:31:30 UTC (rev 185640)
@@ -1,3 +1,41 @@
+2015-06-09 Filip Pizlo <fpi...@apple.com>
+
+ FTL should eliminate array bounds checks in loops
+ https://bugs.webkit.org/show_bug.cgi?id=145768
+
+ Reviewed by Benjamin Poulain.
+
+ This adds a phase that does forward propagation of integer inequalities. This allows us
+ to do the algebraic reasoning we need to eliminate array bounds checks in loops. It
+ also eliminates overflow checks on ArithAdd with a constant.
+
+ The phase's analysis produces results that are powerful enough to do speculative bounds
+ check hoisting, but this phase currently only does elimination. We can implement
+ hoisting later.
+
+ On programs that just loop over an array like:
+
+ for (var i = 0; i < array.length; ++i)
+ thingy += array[i]
+
+ This change is a 60% speed-up.
+
+ This is also a ~3% speed-up on Kraken, and it shows various speed-ups on individual
+ tests in Octane.
+
+ * CMakeLists.txt:
+ * _javascript_Core.vcxproj/_javascript_Core.vcxproj:
+ * _javascript_Core.xcodeproj/project.pbxproj:
+ * dfg/DFGIntegerRangeOptimizationPhase.cpp: Added.
+ (JSC::DFG::performIntegerRangeOptimization):
+ * dfg/DFGIntegerRangeOptimizationPhase.h: Added.
+ * dfg/DFGPlan.cpp:
+ (JSC::DFG::Plan::compileInThreadImpl):
+ * tests/stress/add-overflows-after-not-equal.js: Added.
+ * tests/stress/no-abc-skippy-loop.js: Added.
+ * tests/stress/no-abc-skippy-paired-loop.js: Added.
+ * tests/stress/sub-overflows-after-not-equal.js: Added.
+
2015-06-16 Andreas Kling <akl...@apple.com>
Remove unused template parameter InlineCapacity from SegmentedVector.
Modified: trunk/Source/_javascript_Core/_javascript_Core.vcxproj/_javascript_Core.vcxproj (185639 => 185640)
--- trunk/Source/_javascript_Core/_javascript_Core.vcxproj/_javascript_Core.vcxproj 2015-06-17 05:18:21 UTC (rev 185639)
+++ trunk/Source/_javascript_Core/_javascript_Core.vcxproj/_javascript_Core.vcxproj 2015-06-17 05:31:30 UTC (rev 185640)
@@ -418,6 +418,7 @@
<ClCompile Include="..\dfg\DFGInPlaceAbstractState.cpp" />
<ClCompile Include="..\dfg\DFGInsertOSRHintsForUpdate.cpp" />
<ClCompile Include="..\dfg\DFGIntegerCheckCombiningPhase.cpp" />
+ <ClCompile Include="..\dfg\DFGIntegerRangeOptimizationPhase.cpp" />
<ClCompile Include="..\dfg\DFGInvalidationPointInjectionPhase.cpp" />
<ClCompile Include="..\dfg\DFGJITCode.cpp" />
<ClCompile Include="..\dfg\DFGJITCompiler.cpp" />
@@ -1109,6 +1110,7 @@
<ClInclude Include="..\dfg\DFGInsertOSRHintsForUpdate.h" />
<ClInclude Include="..\dfg\DFGInsertionSet.h" />
<ClInclude Include="..\dfg\DFGIntegerCheckCombiningPhase.h" />
+ <ClInclude Include="..\dfg\DFGIntegerRangeOptimizationPhase.h" />
<ClInclude Include="..\dfg\DFGInvalidationPointInjectionPhase.h" />
<ClInclude Include="..\dfg\DFGJITCode.h" />
<ClInclude Include="..\dfg\DFGJITCompiler.h" />
Modified: trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj (185639 => 185640)
--- trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2015-06-17 05:18:21 UTC (rev 185639)
+++ trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2015-06-17 05:31:30 UTC (rev 185640)
@@ -416,6 +416,8 @@
0F8364B7164B0C110053329A /* DFGBranchDirection.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F8364B5164B0C0E0053329A /* DFGBranchDirection.h */; settings = {ATTRIBUTES = (Private, ); }; };
0F885E111849A3BE00F1E3FA /* BytecodeUseDef.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F885E101849A3BE00F1E3FA /* BytecodeUseDef.h */; settings = {ATTRIBUTES = (Private, ); }; };
0F893BDB1936E23C001211F4 /* DFGStructureAbstractValue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F893BDA1936E23C001211F4 /* DFGStructureAbstractValue.cpp */; };
+ 0F898F311B27689F0083A33C /* DFGIntegerRangeOptimizationPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F898F2F1B27689F0083A33C /* DFGIntegerRangeOptimizationPhase.cpp */; };
+ 0F898F321B27689F0083A33C /* DFGIntegerRangeOptimizationPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F898F301B27689F0083A33C /* DFGIntegerRangeOptimizationPhase.h */; settings = {ATTRIBUTES = (Private, ); }; };
0F8F14331ADF090100ED792C /* DFGEpoch.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F8F142F1ADF090100ED792C /* DFGEpoch.cpp */; };
0F8F14341ADF090100ED792C /* DFGEpoch.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F8F14301ADF090100ED792C /* DFGEpoch.h */; settings = {ATTRIBUTES = (Private, ); }; };
0F8F14351ADF090100ED792C /* DFGMovHintRemovalPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F8F14311ADF090100ED792C /* DFGMovHintRemovalPhase.cpp */; };
@@ -2154,6 +2156,8 @@
0F8364B5164B0C0E0053329A /* DFGBranchDirection.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBranchDirection.h; path = dfg/DFGBranchDirection.h; sourceTree = "<group>"; };
0F885E101849A3BE00F1E3FA /* BytecodeUseDef.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BytecodeUseDef.h; sourceTree = "<group>"; };
0F893BDA1936E23C001211F4 /* DFGStructureAbstractValue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGStructureAbstractValue.cpp; path = dfg/DFGStructureAbstractValue.cpp; sourceTree = "<group>"; };
+ 0F898F2F1B27689F0083A33C /* DFGIntegerRangeOptimizationPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGIntegerRangeOptimizationPhase.cpp; path = dfg/DFGIntegerRangeOptimizationPhase.cpp; sourceTree = "<group>"; };
+ 0F898F301B27689F0083A33C /* DFGIntegerRangeOptimizationPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGIntegerRangeOptimizationPhase.h; path = dfg/DFGIntegerRangeOptimizationPhase.h; sourceTree = "<group>"; };
0F8F142F1ADF090100ED792C /* DFGEpoch.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGEpoch.cpp; path = dfg/DFGEpoch.cpp; sourceTree = "<group>"; };
0F8F14301ADF090100ED792C /* DFGEpoch.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGEpoch.h; path = dfg/DFGEpoch.h; sourceTree = "<group>"; };
0F8F14311ADF090100ED792C /* DFGMovHintRemovalPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGMovHintRemovalPhase.cpp; path = dfg/DFGMovHintRemovalPhase.cpp; sourceTree = "<group>"; };
@@ -4972,6 +4976,8 @@
0F2B9CD919D0BA7D00B1D1B5 /* DFGInsertOSRHintsForUpdate.h */,
0F300B7918AB1B1400A6D72E /* DFGIntegerCheckCombiningPhase.cpp */,
0F300B7A18AB1B1400A6D72E /* DFGIntegerCheckCombiningPhase.h */,
+ 0F898F2F1B27689F0083A33C /* DFGIntegerRangeOptimizationPhase.cpp */,
+ 0F898F301B27689F0083A33C /* DFGIntegerRangeOptimizationPhase.h */,
0FC97F3718202119002C9B26 /* DFGInvalidationPointInjectionPhase.cpp */,
0FC97F3818202119002C9B26 /* DFGInvalidationPointInjectionPhase.h */,
0FEA0A2F170D40BF00BB722C /* DFGJITCode.cpp */,
@@ -5609,6 +5615,7 @@
0F6B1CCA18641DF800845D97 /* ArityCheckFailReturnThunks.h in Headers */,
0F6B1CB91861244C00845D97 /* ArityCheckMode.h in Headers */,
A1A009C11831A26E00CF8711 /* ARM64Assembler.h in Headers */,
+ 0F898F321B27689F0083A33C /* DFGIntegerRangeOptimizationPhase.h in Headers */,
86D3B2C410156BDE002865E7 /* ARMAssembler.h in Headers */,
0FE050281AA9095600D33B33 /* ScopedArguments.h in Headers */,
52C0611F1AA51E1C00B4ADBA /* RuntimeType.h in Headers */,
@@ -7343,6 +7350,7 @@
0F2B66E817B6B5AB00A7AE3F /* JSArrayBufferView.cpp in Sources */,
A7BDAECA17F4EA1400F6140C /* JSArrayIterator.cpp in Sources */,
1421359B0A677F4F00A8195E /* JSBase.cpp in Sources */,
+ 0F898F311B27689F0083A33C /* DFGIntegerRangeOptimizationPhase.cpp in Sources */,
86FA9E91142BBB2E001773B7 /* JSBoundFunction.cpp in Sources */,
1440F8AF0A508D200005F061 /* JSCallbackConstructor.cpp in Sources */,
1440F8920A508B100005F061 /* JSCallbackFunction.cpp in Sources */,
Added: trunk/Source/_javascript_Core/dfg/DFGIntegerRangeOptimizationPhase.cpp (0 => 185640)
--- trunk/Source/_javascript_Core/dfg/DFGIntegerRangeOptimizationPhase.cpp (rev 0)
+++ trunk/Source/_javascript_Core/dfg/DFGIntegerRangeOptimizationPhase.cpp 2015-06-17 05:31:30 UTC (rev 185640)
@@ -0,0 +1,1340 @@
+/*
+ * 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 "DFGIntegerRangeOptimizationPhase.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBlockMapInlines.h"
+#include "DFGGraph.h"
+#include "DFGInsertionSet.h"
+#include "DFGPhase.h"
+#include "DFGPredictionPropagationPhase.h"
+#include "DFGVariableAccessDataDump.h"
+#include "JSCInlines.h"
+
+namespace JSC { namespace DFG {
+
+namespace {
+
+const bool verbose = false;
+
+int64_t clampedSumImpl() { return 0; }
+
+template<typename... Args>
+int64_t clampedSumImpl(int left, Args... args)
+{
+ return static_cast<int64_t>(left) + clampedSumImpl(args...);
+}
+
+template<typename... Args>
+int clampedSum(Args... args)
+{
+ int64_t result = clampedSumImpl(args...);
+ return std::min(
+ static_cast<int64_t>(std::numeric_limits<int>::max()),
+ std::max(
+ static_cast<int64_t>(std::numeric_limits<int>::min()),
+ result));
+}
+
+class Relationship {
+public:
+ enum Kind {
+ LessThan,
+ Equal,
+ NotEqual,
+ GreaterThan
+ };
+
+ static Kind flipped(Kind kind)
+ {
+ switch (kind) {
+ case LessThan:
+ return GreaterThan;
+ case Equal:
+ return Equal;
+ case NotEqual:
+ return NotEqual;
+ case GreaterThan:
+ return LessThan;
+ }
+ RELEASE_ASSERT_NOT_REACHED();
+ return kind;
+ }
+
+ Relationship()
+ : m_left(nullptr)
+ , m_right(nullptr)
+ , m_kind(Equal)
+ , m_offset(0)
+ {
+ }
+
+ Relationship(Node* left, Node* right, Kind kind, int offset = 0)
+ : m_left(left)
+ , m_right(right)
+ , m_kind(kind)
+ , m_offset(offset)
+ {
+ RELEASE_ASSERT(m_left);
+ RELEASE_ASSERT(m_right);
+ RELEASE_ASSERT(m_left != m_right);
+ }
+
+ static Relationship safeCreate(Node* left, Node* right, Kind kind, int offset = 0)
+ {
+ if (!left || !right || left == right)
+ return Relationship();
+ return Relationship(left, right, kind, offset);
+ }
+
+ typedef void* (Relationship::*UnspecifiedBoolType);
+
+ operator UnspecifiedBoolType*() const
+ {
+ return m_left ? reinterpret_cast<UnspecifiedBoolType*>(1) : 0;
+ }
+
+ Node* left() const { return m_left; }
+ Node* right() const { return m_right; }
+ Kind kind() const { return m_kind; }
+ int offset() const { return m_offset; }
+
+ Relationship flipped() const
+ {
+ if (!*this)
+ return Relationship();
+
+ // This should return Relationship() if -m_offset overflows. For example:
+ //
+ // @a > @b - 2**31
+ //
+ // If we flip it we get:
+ //
+ // @b < @a + 2**31
+ //
+ // Except that the sign gets flipped since it's INT_MIN:
+ //
+ // @b < @a - 2**31
+ //
+ // And that makes no sense. To see how little sense it makes, consider:
+ //
+ // @a > @zero - 2**31
+ //
+ // We would flip it to mean:
+ //
+ // @zero < @a - 2**31
+ //
+ // Which is absurd.
+
+ if (m_offset == std::numeric_limits<int>::min())
+ return Relationship();
+
+ return Relationship(m_right, m_left, flipped(m_kind), -m_offset);
+ }
+
+ Relationship inverse() const
+ {
+ if (!*this)
+ return *this;
+
+ switch (m_kind) {
+ case Equal:
+ return Relationship(m_left, m_right, NotEqual, m_offset);
+ case NotEqual:
+ return Relationship(m_left, m_right, Equal, m_offset);
+ case LessThan:
+ if (sumOverflows<int>(m_offset, -1))
+ return Relationship();
+ return Relationship(m_left, m_right, GreaterThan, m_offset - 1);
+ case GreaterThan:
+ if (sumOverflows<int>(m_offset, 1))
+ return Relationship();
+ return Relationship(m_left, m_right, LessThan, m_offset + 1);
+ }
+
+ RELEASE_ASSERT_NOT_REACHED();
+ }
+
+ bool isCanonical() const { return m_left < m_right; }
+
+ Relationship canonical() const
+ {
+ if (isCanonical())
+ return *this;
+ return flipped();
+ }
+
+ bool sameNodesAs(const Relationship& other) const
+ {
+ return m_left == other.m_left
+ && m_right == other.m_right;
+ }
+
+ bool operator==(const Relationship& other) const
+ {
+ return sameNodesAs(other)
+ && m_kind == other.m_kind
+ && m_offset == other.m_offset;
+ }
+
+ bool operator!=(const Relationship& other) const
+ {
+ return !(*this == other);
+ }
+
+ bool operator<(const Relationship& other) const
+ {
+ if (m_left != other.m_left)
+ return m_left < other.m_left;
+ if (m_right != other.m_right)
+ return m_right < other.m_right;
+ if (m_kind != other.m_kind)
+ return m_kind < other.m_kind;
+ return m_offset < other.m_offset;
+ }
+
+ // If possible, returns a form of this relationship where the given node is the left
+ // side. Returns a null relationship if this relationship cannot say anything about this
+ // node.
+ Relationship forNode(Node* node) const
+ {
+ if (m_left == node)
+ return *this;
+ if (m_right == node)
+ return flipped();
+ return Relationship();
+ }
+
+ void setLeft(Node* left)
+ {
+ RELEASE_ASSERT(left != m_right);
+ m_left = left;
+ }
+ bool addToOffset(int offset)
+ {
+ if (sumOverflows<int>(m_offset, offset))
+ return false;
+ m_offset += offset;
+ return true;
+ }
+
+ // Attempts to create a relationship that summarizes the union of this relationship and
+ // the other relationship. The null relationship is returned to indicate TOP. This is used
+ // for merging the current relationship-at-head for some pair of nodes and a new
+ // relationship-at-head being proposed by a predecessor. We wish to create a new
+ // relationship that is true whenever either of them are true, which ensuring that we don't
+ // do this forever. Anytime we create a relationship that is not equal to either of the
+ // previous ones, we will cause the analysis fixpoint to reexecute.
+ //
+ // If *this and other are identical, we just return it.
+ //
+ // If they are different, we pick from a finite set of "general" relationships:
+ //
+ // Eq: this == other + C, where C is -1, 0, or 1.
+ // Lt: this < other + C, where C is -1, 0, or 1.
+ // Gt: this > other + C, where C is -1, 0, or 1.
+ // Ne: this != other + C, where C is -1, 0, or 1.
+ // TOP: the null relationship.
+ //
+ // Constraining C to -1,0,1 is necessary to ensure that the set of general relationships is
+ // finite. This finite set of relationships forms a pretty simple lattice where a
+ // relA->relB means "relB is more general than relA". For example, this<other+1 is more
+ // general than this==other. I'll leave it as an exercise for the reader to see that a
+ // graph between the 13 general relationships is indeed a lattice. The fact that the set of
+ // general relationships is a finite lattice ensures monotonicity of the fixpoint, since
+ // any merge over not-identical relationships returns a relationship that is closer to the
+ // TOP relationship than either of the original relationships. Here's how convergence is
+ // achieved for any pair of relationships over the same nodes:
+ //
+ // - If they are identical, then returning *this means that we won't be responsible for
+ // causing another fixpoint iteration. Once all merges reach this point, we're done.
+ //
+ // - If they are different, then we pick the most constraining of the 13 general
+ // relationships that is true if either *this or other are true. This means that if the
+ // relationships are not identical, the merged relationship will be closer to TOP than
+ // either of the originals. Returning a different relationship means that we will be
+ // responsible for the fixpoint to reloop, but we can only do this at most 13 times since
+ // that's how "deep" the general relationship lattice is.
+ //
+ // Note that C being constrained to -1,0,1 also ensures that we never have to return a
+ // combination of Lt and Gt, as in for example this<other+C && this>other-D. That's why
+ // this function can return zero or one relationships rather than a list of relationships.
+ // The only possible values of C and D where this would work are -1 and 1, but in that case
+ // we just say this==other. That said, the logic for merging two == relationships, like
+ // this==other+C || this==other+D is to attempt to create these two relationships:
+ // this>other+min(C,D)-1 && this<other+max(C,D)+1. But only one of these relationships will
+ // belong to the set of general relationships.
+ //
+ // Here's an example of this in action:
+ //
+ // for (var i = a; ; ++i) { }
+ //
+ // Without C being constrained to -1,0,1, we could end up looping forever: first we'd say
+ // that i==a, then we might say that i<a+2, then i<a+3, then i<a+4, etc. We won't do this
+ // because i<a+2 is not a valid general relationship: so when we merge i==a from the first
+ // iteration and i==a+1 from the second iteration, we create i>a-1 and i<a+2 but then
+ // realize that only i>a-1 is a valid general relationship. This gives us exactly what we
+ // want: a statement that i>=a.
+ Relationship merge(const Relationship& other) const
+ {
+ if (!sameNodesAs(other))
+ return Relationship();
+
+ // Handle the super obvious case first.
+ if (*this == other)
+ return *this;
+
+ // This does some interesting permutations to reduce the amount of duplicate code. For
+ // example:
+ //
+ // initially: @a != @b, @a > @b
+ // @b != @a, @b < @a
+ // @b < @a, @b != @a
+ // finally: @b != a, @b < @a
+ //
+ // Another example:
+ //
+ // initially: @a < @b, @a != @b
+ // finally: @a != @b, @a < @b
+
+ Relationship a = *this;
+ Relationship b = other;
+ bool needFlip = false;
+
+ // Get rid of GreaterThan.
+ if (a.m_kind == GreaterThan || b.m_kind == GreaterThan) {
+ a = a.flipped();
+ b = b.flipped();
+
+ // In rare cases, we might not be able to flip. Just give up on life in those
+ // cases.
+ if (!a || !b)
+ return Relationship();
+
+ needFlip = true;
+
+ // If we still have GreaterThan, then it means that we started with @a < @b and
+ // @a > @b. That's pretty much always a tautology; we don't attempt to do smart
+ // things for that case for now.
+ if (a.m_kind == GreaterThan || b.m_kind == GreaterThan)
+ return Relationship();
+ }
+
+ // Make sure that if we have a LessThan, then it's first.
+ if (b.m_kind == LessThan)
+ std::swap(a, b);
+
+ // Make sure that if we have a NotEqual, then it's first.
+ if (b.m_kind == NotEqual)
+ std::swap(a, b);
+
+ Relationship result = a.mergeImpl(b);
+
+ if (needFlip)
+ return result.flipped();
+
+ return result;
+ }
+
+ // Attempts to construct one Relationship that adequately summarizes the intersection of
+ // this and other. Returns a null relationship if the filtration should be expressed as two
+ // different relationships. Returning null is always safe because relationship lists in
+ // this phase always imply intersection. So, you could soundly skip calling this method and
+ // just put both relationships into the list. But, that could lead the fixpoint to diverge.
+ // Hence this will attempt to combine the two relationships into one as a convergence hack.
+ // In some cases, it will do something conservative. It's always safe for this to return
+ // *this, or to return other. It'll do that sometimes, mainly to accelerate convergence for
+ // things that we don't think are important enough to slow down the analysis.
+ Relationship filter(const Relationship& other) const
+ {
+ // We are only interested in merging relationships over the same nodes.
+ ASSERT(sameNodesAs(other));
+
+ if (*this == other)
+ return *this;
+
+ // From here we can assume that the two relationships are not identical. Usually we use
+ // this to assume that we have different offsets anytime that everything but the offset
+ // is identical.
+
+ // We want equality to take precedent over everything else, and we don't want multiple
+ // independent claims of equality. That would just be a contradiction. When it does
+ // happen, we will be conservative in the sense that we will pick one.
+ if (m_kind == Equal)
+ return *this;
+ if (other.m_kind == Equal)
+ return other;
+
+ // Useful helper for flipping.
+ auto filterFlipped = [&] () -> Relationship {
+ // If we cannot flip, then just conservatively return *this.
+ Relationship a = flipped();
+ Relationship b = other.flipped();
+ if (!a || !b)
+ return *this;
+ Relationship result = a.filter(b);
+ if (!result)
+ return Relationship();
+ result = result.flipped();
+ if (!result)
+ return *this;
+ return result;
+ };
+
+ if (m_kind == NotEqual) {
+ if (other.m_kind == NotEqual) {
+ // We could do something smarter here. We could even keep both NotEqual's. We
+ // would need to make sure that we correctly collapsed them when merging. But
+ // for now, we just pick one of them and hope for the best.
+ return *this;
+ }
+
+ if (other.m_kind == GreaterThan) {
+ // Implement this in terms of NotEqual.filter(LessThan).
+ return filterFlipped();
+ }
+
+ ASSERT(other.m_kind == LessThan);
+ // We have two claims:
+ // @a != @b + C
+ // @a < @b + D
+ //
+ // If C >= D, then the NotEqual is redundant.
+ // If C < D - 1, then we could keep both, but for now we just keep the LessThan.
+ // If C == D - 1, then the LessThan can be turned into:
+ //
+ // @a < @b + C
+ //
+ // Note that C == this.m_offset, D == other.m_offset.
+
+ if (m_offset == other.m_offset - 1)
+ return Relationship(m_left, m_right, LessThan, m_offset);
+
+ return other;
+ }
+
+ if (other.m_kind == NotEqual)
+ return other.filter(*this);
+
+ if (m_kind == LessThan) {
+ if (other.m_kind == LessThan) {
+ return Relationship(
+ m_left, m_right, LessThan, std::min(m_offset, other.m_offset));
+ }
+
+ ASSERT(other.m_kind == GreaterThan);
+ if (sumOverflows<int>(m_offset, -1))
+ return Relationship();
+ if (sumOverflows<int>(other.m_offset, 1))
+ return Relationship();
+ if (m_offset - 1 == other.m_offset + 1)
+ return Relationship(m_left, m_right, Equal, m_offset - 1);
+
+ return Relationship();
+ }
+
+ ASSERT(m_kind == GreaterThan);
+ return filterFlipped();
+ }
+
+ int minValueOfLeft() const
+ {
+ if (m_left->isInt32Constant())
+ return m_left->asInt32();
+
+ if (m_kind == LessThan || m_kind == NotEqual)
+ return std::numeric_limits<int>::min();
+
+ int minRightValue = std::numeric_limits<int>::min();
+ if (m_right->isInt32Constant())
+ minRightValue = m_right->asInt32();
+
+ if (m_kind == GreaterThan)
+ return clampedSum(minRightValue, m_offset, 1);
+ ASSERT(m_kind == Equal);
+ return clampedSum(minRightValue, m_offset);
+ }
+
+ int maxValueOfLeft() const
+ {
+ if (m_left->isInt32Constant())
+ return m_left->asInt32();
+
+ if (m_kind == GreaterThan || m_kind == NotEqual)
+ return std::numeric_limits<int>::max();
+
+ int maxRightValue = std::numeric_limits<int>::max();
+ if (m_right->isInt32Constant())
+ maxRightValue = m_right->asInt32();
+
+ if (m_kind == LessThan)
+ return clampedSum(maxRightValue, m_offset, -1);
+ ASSERT(m_kind == Equal);
+ return clampedSum(maxRightValue, m_offset);
+ }
+
+ void dump(PrintStream& out) const
+ {
+ // This prints out the relationship without any whitespace, like @x<@y+42. This
+ // optimizes for the clarity of a list of relationships. It's easier to read something
+ // like [@1<@2+3, @4==@5-6] than it would be if there was whitespace inside the
+ // relationships.
+
+ if (!*this) {
+ out.print("null");
+ return;
+ }
+
+ out.print(m_left);
+ switch (m_kind) {
+ case LessThan:
+ out.print("<");
+ break;
+ case Equal:
+ out.print("==");
+ break;
+ case NotEqual:
+ out.print("!=");
+ break;
+ case GreaterThan:
+ out.print(">");
+ break;
+ }
+ out.print(m_right);
+ if (m_offset > 0)
+ out.print("+", m_offset);
+ else if (m_offset < 0)
+ out.print("-", -static_cast<int64_t>(m_offset));
+ }
+
+private:
+ Relationship mergeImpl(const Relationship& other) const
+ {
+ ASSERT(sameNodesAs(other));
+ ASSERT(m_kind != GreaterThan);
+ ASSERT(other.m_kind != GreaterThan);
+ ASSERT(*this != other);
+
+ // The purpose of this method is to guarantee that:
+ //
+ // - We avoid having more than one Relationship over the same two nodes. Therefore, if
+ // the merge could be expressed as two Relationships, we prefer to instead pick the
+ // less precise single Relationship form even if that means TOP.
+ //
+ // - If the difference between two Relationships is just the m_offset, then we create a
+ // Relationship that has an offset of -1, 0, or 1. This is an essential convergence
+ // hack. We need -1 and 1 to support <= and >=.
+
+ // From here we can assume that the two relationships are not identical. Usually we use
+ // this to assume that we have different offsets anytime that everything but the offset
+ // is identical.
+
+ if (m_kind == NotEqual) {
+ if (other.m_kind == NotEqual)
+ return Relationship(); // Different offsets, so tautology.
+
+ if (other.m_kind == Equal) {
+ if (m_offset != other.m_offset) {
+ // Saying that you might be B when you've already said that you're anything
+ // but A, where A and B are different, is a tautology. You could just say
+ // that you're anything but A. Adding "(a == b + 1)" to "(a != b + 5)" has
+ // no value.
+ return *this;
+ }
+ // Otherwise, same offsets: we're saying that you're either A or you're not
+ // equal to A.
+
+ return Relationship();
+ }
+
+ RELEASE_ASSERT(other.m_kind == LessThan);
+ // We have these claims, and we're merging them:
+ // @a != @b + C
+ // @a < @b + D
+ //
+ // If we have C == D, then the merge is clearly just the NotEqual.
+ // If we have C < D, then the merge is a tautology.
+ // If we have C > D, then we could keep both claims, but we are cheap, so we
+ // don't. We just use the NotEqual.
+
+ if (m_offset < other.m_offset)
+ return Relationship();
+
+ return *this;
+ }
+
+ if (m_kind == LessThan) {
+ if (other.m_kind == LessThan) {
+ // Figure out what offset to select to merge them. The appropriate offsets are
+ // -1, 0, or 1.
+
+ // First figure out what offset we'd like to use.
+ int bestOffset = std::max(m_offset, other.m_offset);
+
+ // We have something like @a < @b + 2. We can't represent this under the
+ // -1,0,1 rule.
+ if (bestOffset <= 1)
+ return Relationship(m_left, m_right, LessThan, std::max(bestOffset, -1));
+
+ return Relationship();
+ }
+
+ // The only thing left is Equal. We would have eliminated the GreaterThan's, and
+ // if we merge LessThan and NotEqual, the NotEqual always comes first.
+ RELEASE_ASSERT(other.m_kind == Equal);
+
+ // This is the really interesting case. We have:
+ //
+ // @a < @b + C
+ //
+ // and:
+ //
+ // @a == @b + D
+ //
+ // Therefore we'd like to return:
+ //
+ // @a < @b + max(C, D + 1)
+
+ int bestOffset = std::max(m_offset, other.m_offset + 1);
+
+ // We have something like @a < @b + 2. We can't do it.
+ if (bestOffset <= 1)
+ return Relationship(m_left, m_right, LessThan, std::max(bestOffset, -1));
+
+ return Relationship();
+ }
+
+ // The only thing left is Equal, since we would have gotten rid of the GreaterThan's.
+ RELEASE_ASSERT(m_kind == Equal);
+
+ // We would never see NotEqual, because those always come first. We would never
+ // see GreaterThan, because we would have eliminated those. We would never see
+ // LessThan, because those always come first.
+
+ RELEASE_ASSERT(other.m_kind == Equal);
+ // We have @a == @b + C and @a == @b + D, where C != D. Turn this into some
+ // inequality that involves a constant that is -1,0,1. Note that we will never have
+ // lessThan and greaterThan because the constants are constrained to -1,0,1. The only
+ // way for both of them to be valid is a<b+1 and a>b-1, but then we would have said
+ // a==b.
+
+ Relationship lessThan;
+ Relationship greaterThan;
+
+ int lessThanEqOffset = std::max(m_offset, other.m_offset);
+ if (lessThanEqOffset >= -2 && lessThanEqOffset <= 0) {
+ lessThan = Relationship(
+ m_left, other.m_right, LessThan, lessThanEqOffset + 1);
+
+ ASSERT(lessThan.offset() >= -1 && lessThan.offset() <= 1);
+ }
+
+ int greaterThanEqOffset = std::min(m_offset, other.m_offset);
+ if (greaterThanEqOffset >= 0 && greaterThanEqOffset <= 2) {
+ greaterThan = Relationship(
+ m_left, other.m_right, GreaterThan, greaterThanEqOffset - 1);
+
+ ASSERT(greaterThan.offset() >= -1 && greaterThan.offset() <= 1);
+ }
+
+ if (lessThan) {
+ // Both relationships cannot be valid; see above.
+ RELEASE_ASSERT(!greaterThan);
+
+ return lessThan;
+ }
+
+ return greaterThan;
+ }
+
+ Node* m_left;
+ Node* m_right;
+ Kind m_kind;
+ int m_offset; // This offset can be arbitrarily large.
+};
+
+typedef HashMap<Node*, Vector<Relationship>> RelationshipMap;
+
+class IntegerRangeOptimizationPhase : public Phase {
+public:
+ IntegerRangeOptimizationPhase(Graph& graph)
+ : Phase(graph, "integer range optimization")
+ , m_zero(nullptr)
+ , m_relationshipsAtHead(graph)
+ , m_insertionSet(graph)
+ {
+ }
+
+ bool run()
+ {
+ ASSERT(m_graph.m_form == SSA);
+
+ // Before we do anything, make sure that we have a zero constant at the top.
+ for (Node* node : *m_graph.block(0)) {
+ if (node->isInt32Constant() && !node->asInt32()) {
+ m_zero = node;
+ break;
+ }
+ }
+ if (!m_zero) {
+ m_zero = m_insertionSet.insertConstant(0, NodeOrigin(), jsNumber(0));
+ m_insertionSet.execute(m_graph.block(0));
+ }
+
+ if (verbose) {
+ dataLog("Graph before integer range optimization:\n");
+ m_graph.dump();
+ }
+
+ // This performs a fixpoint over the blocks in reverse post-order. Logically, we
+ // maintain a list of relationships at each point in the program. The list should be
+ // read as an intersection. For example if we have {rel1, rel2, ..., relN}, you should
+ // read this as:
+ //
+ // TOP && rel1 && rel2 && ... && relN
+ //
+ // This allows us to express things like:
+ //
+ // @a > @b - 42 && @a < @b + 25
+ //
+ // But not things like:
+ //
+ // @a < @b - 42 || @a > @b + 25
+ //
+ // We merge two lists by merging each relationship in one list with each relationship
+ // in the other list. Merging two relationships will yield a relationship list; as with
+ // all such lists it is an intersction. Merging relationships over different variables
+ // always yields the empty list (i.e. TOP). This merge style is sound because if we
+ // have:
+ //
+ // (A && B && C) || (D && E && F)
+ //
+ // Then a valid merge is just one that will return true if A, B, C are all true, or
+ // that will return true if D, E, F are all true. Our merge style essentially does:
+ //
+ // (A || D) && (A || E) && (A || F) && (B || D) && (B || E) && (B || F) &&
+ // (C || D) && (C || E) && (C || F)
+ //
+ // If A && B && C is true, then this returns true. If D && E && F is true, this also
+ // returns true.
+ //
+ // While this appears at first like a kind of _expression_ explosion, in practice it
+ // isn't. The code that handles this knows that the merge of two relationships over
+ // different variables is TOP (i.e. the empty list). For example if A above is @a < @b
+ // and B above is @c > @d, where @a, @b, @c, and @d are different nodes, the merge will
+ // yield nothing. In fact, the merge algorithm will skip such merges entirely because
+ // the relationship lists are actually keyed by node.
+ //
+ // Note that it's always safe to drop any of relationship from the relationship list.
+ // This merely increases the likelihood of the "_expression_" yielding true, i.e. being
+ // closer to TOP. Optimizations are only performed if we can establish that the
+ // _expression_ implied by the relationship list is false for all of those cases where
+ // some check would have failed.
+ //
+ // There is no notion of BOTTOM because we treat blocks that haven't had their
+ // state-at-head set as a special case: we just transfer all live relationships to such
+ // a block. After the head of a block is set, we perform the merging as above. In all
+ // other places where we would ordinarily need BOTTOM, we approximate it by having some
+ // non-BOTTOM relationship.
+
+ BlockList postOrder = m_graph.blocksInPostOrder();
+
+ // This loop analyzes the IR to give us m_relationshipsAtHead for each block. This
+ // may reexecute blocks many times, but it is guaranteed to converge. The state of
+ // the relationshipsAtHead over any pair of nodes converge monotonically towards the
+ // TOP relationship (i.e. no relationships in the relationship list). The merge rule
+ // when between the current relationshipsAtHead and the relationships being propagated
+ // from a predecessor ensures monotonicity by converting disagreements into one of a
+ // small set of "general" relationships. There are 12 such relationshis, plus TOP. See
+ // the comment above Relationship::merge() for details.
+ bool changed = true;
+ while (changed) {
+ changed = false;
+ for (unsigned postOrderIndex = postOrder.size(); postOrderIndex--;) {
+ BasicBlock* block = postOrder[postOrderIndex];
+ DFG_ASSERT(
+ m_graph, nullptr,
+ block == m_graph.block(0) || m_seenBlocks.contains(block));
+
+ m_relationships = m_relationshipsAtHead[block];
+
+ for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
+ Node* node = block->at(nodeIndex);
+ if (verbose)
+ dataLog("Analysis: at ", node, ": ", listDump(sortedRelationships()), "\n");
+ executeNode(node);
+ }
+
+ // Now comes perhaps the most important piece of cleverness: if we Branch, and
+ // the predicate involves some relation over integers, we propagate different
+ // information to the taken and notTaken paths. This handles:
+ // - Branch on int32.
+ // - Branch on LogicalNot on int32.
+ // - Branch on compare on int32's.
+ // - Branch on LogicalNot of compare on int32's.
+ Node* terminal = block->terminal();
+ bool alreadyMerged = false;
+ if (terminal->op() == Branch) {
+ Relationship relationshipForTrue;
+ BranchData* branchData = terminal->branchData();
+
+ bool invert = false;
+ if (terminal->child1()->op() == LogicalNot) {
+ terminal = terminal->child1().node();
+ invert = true;
+ }
+
+ if (terminal->child1().useKind() == Int32Use) {
+ relationshipForTrue = Relationship::safeCreate(
+ terminal->child1().node(), m_zero, Relationship::NotEqual, 0);
+ } else {
+ Node* compare = terminal->child1().node();
+ switch (compare->op()) {
+ case CompareEq:
+ case CompareStrictEq:
+ case CompareLess:
+ case CompareLessEq:
+ case CompareGreater:
+ case CompareGreaterEq: {
+ if (!compare->isBinaryUseKind(Int32Use))
+ break;
+
+ switch (compare->op()) {
+ case CompareEq:
+ case CompareStrictEq:
+ relationshipForTrue = Relationship::safeCreate(
+ compare->child1().node(), compare->child2().node(),
+ Relationship::Equal, 0);
+ break;
+ case CompareLess:
+ relationshipForTrue = Relationship::safeCreate(
+ compare->child1().node(), compare->child2().node(),
+ Relationship::LessThan, 0);
+ break;
+ case CompareLessEq:
+ relationshipForTrue = Relationship::safeCreate(
+ compare->child1().node(), compare->child2().node(),
+ Relationship::LessThan, 1);
+ break;
+ case CompareGreater:
+ relationshipForTrue = Relationship::safeCreate(
+ compare->child1().node(), compare->child2().node(),
+ Relationship::GreaterThan, 0);
+ break;
+ case CompareGreaterEq:
+ relationshipForTrue = Relationship::safeCreate(
+ compare->child1().node(), compare->child2().node(),
+ Relationship::GreaterThan, -1);
+ break;
+ default:
+ DFG_CRASH(m_graph, compare, "Invalid comparison node type");
+ break;
+ }
+ break;
+ }
+
+ default:
+ break;
+ }
+ }
+
+ if (invert)
+ relationshipForTrue = relationshipForTrue.inverse();
+
+ if (relationshipForTrue) {
+ RelationshipMap forTrue = m_relationships;
+ RelationshipMap forFalse = m_relationships;
+
+ if (verbose)
+ dataLog("Dealing with true:\n");
+ setRelationship(forTrue, relationshipForTrue);
+ if (Relationship relationshipForFalse = relationshipForTrue.inverse()) {
+ if (verbose)
+ dataLog("Dealing with false:\n");
+ setRelationship(forFalse, relationshipForFalse);
+ }
+
+ changed |= mergeTo(forTrue, branchData->taken.block);
+ changed |= mergeTo(forFalse, branchData->notTaken.block);
+ alreadyMerged = true;
+ }
+ }
+
+ if (!alreadyMerged) {
+ for (BasicBlock* successor : block->successors())
+ changed |= mergeTo(m_relationships, successor);
+ }
+ }
+ }
+
+ // Now we transform the code based on the results computed in the previous loop.
+ changed = false;
+ for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+ m_relationships = m_relationshipsAtHead[block];
+ for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
+ Node* node = block->at(nodeIndex);
+ if (verbose)
+ dataLog("Transformation: at ", node, ": ", listDump(sortedRelationships()), "\n");
+
+ // This ends up being pretty awkward to write because we need to decide if we
+ // optimize by using the relationships before the operation, but we need to
+ // call executeNode() before we optimize.
+ switch (node->op()) {
+ case ArithAdd: {
+ if (!node->isBinaryUseKind(Int32Use))
+ break;
+ if (node->arithMode() != Arith::CheckOverflow)
+ break;
+ if (!node->child2()->isInt32Constant())
+ break;
+
+ auto iter = m_relationships.find(node->child1().node());
+ if (iter == m_relationships.end())
+ break;
+
+ int minValue = std::numeric_limits<int>::min();
+ int maxValue = std::numeric_limits<int>::max();
+ for (Relationship relationship : iter->value) {
+ minValue = std::max(minValue, relationship.minValueOfLeft());
+ maxValue = std::min(maxValue, relationship.maxValueOfLeft());
+ }
+
+ if (sumOverflows<int>(minValue, node->child2()->asInt32()) ||
+ sumOverflows<int>(maxValue, node->child2()->asInt32()))
+ break;
+
+ executeNode(block->at(nodeIndex));
+ node->setArithMode(Arith::Unchecked);
+ changed = true;
+ break;
+ }
+
+ case CheckInBounds: {
+ auto iter = m_relationships.find(node->child1().node());
+ if (iter == m_relationships.end())
+ break;
+
+ bool nonNegative = false;
+ bool lessThanLength = false;
+ for (Relationship relationship : iter->value) {
+ if (relationship.minValueOfLeft() >= 0)
+ nonNegative = true;
+
+ if (relationship.right() == node->child2()) {
+ if (relationship.kind() == Relationship::Equal
+ && relationship.offset() < 0)
+ lessThanLength = true;
+
+ if (relationship.kind() == Relationship::LessThan
+ && relationship.offset() <= 0)
+ lessThanLength = true;
+ }
+ }
+
+ if (nonNegative && lessThanLength) {
+ executeNode(block->at(nodeIndex));
+ node->remove();
+ changed = true;
+ }
+ break;
+ }
+
+ default:
+ break;
+ }
+
+ executeNode(block->at(nodeIndex));
+ }
+ }
+
+ return changed;
+ }
+
+private:
+ void executeNode(Node* node)
+ {
+ switch (node->op()) {
+ case CheckInBounds: {
+ setRelationship(Relationship::safeCreate(node->child1().node(), node->child2().node(), Relationship::LessThan));
+ setRelationship(Relationship::safeCreate(node->child1().node(), m_zero, Relationship::GreaterThan, -1));
+ break;
+ }
+
+ case ArithAdd: {
+ // We're only interested in int32 additions and we currently only know how to
+ // handle the non-wrapping ones.
+ if (!node->isBinaryUseKind(Int32Use))
+ break;
+
+ // FIXME: We could handle the unchecked arithmetic case. We just do it don't right
+ // now.
+ if (node->arithMode() != Arith::CheckOverflow)
+ break;
+
+ // Handle add: @value + constant.
+ if (!node->child2()->isInt32Constant())
+ break;
+
+ int offset = node->child2()->asInt32();
+
+ // We add a relationship for @add == @value + constant, and then we copy the
+ // relationships for @value. This gives us a one-deep view of @value's existing
+ // relationships, which matches the one-deep search in setRelationship().
+
+ setRelationship(
+ Relationship(node, node->child1().node(), Relationship::Equal, offset));
+
+ auto iter = m_relationships.find(node->child1().node());
+ if (iter != m_relationships.end()) {
+ Vector<Relationship> toAdd;
+ for (Relationship relationship : iter->value) {
+ // We have:
+ // add: ArithAdd(@x, C)
+ // @x op @y + D
+ //
+ // The following certainly holds:
+ // @x == @add - C
+ //
+ // Which allows us to substitute:
+ // @add - C op @y + D
+ //
+ // And then carry the C over:
+ // @add op @y + D + C
+
+ Relationship newRelationship = relationship;
+ ASSERT(newRelationship.left() == node->child1().node());
+
+ if (newRelationship.right() == node)
+ continue;
+ newRelationship.setLeft(node);
+ if (newRelationship.addToOffset(offset))
+ toAdd.append(newRelationship);
+ }
+ for (Relationship relationship : toAdd)
+ setRelationship(relationship, 0);
+ }
+
+ // Now we want to establish that both the input and the output of the addition are
+ // within a particular range of integers.
+
+ if (offset > 0) {
+ // If we have "add: @value + 1" then we know that @value <= max - 1, i.e. that
+ // @value < max.
+ if (!sumOverflows<int>(std::numeric_limits<int>::max(), -offset, 1)) {
+ setRelationship(
+ Relationship::safeCreate(
+ node->child1().node(), m_zero, Relationship::LessThan,
+ std::numeric_limits<int>::max() - offset + 1),
+ 0);
+ }
+
+ // If we have "add: @value + 1" then we know that @add >= min + 1, i.e. that
+ // @add > min.
+ if (!sumOverflows<int>(std::numeric_limits<int>::min(), offset, -1)) {
+ setRelationship(
+ Relationship(
+ node, m_zero, Relationship::GreaterThan,
+ std::numeric_limits<int>::min() + offset - 1),
+ 0);
+ }
+ }
+
+ if (offset < 0 && offset != std::numeric_limits<int>::min()) {
+ // If we have "add: @value - 1" then we know that @value >= min + 1, i.e. that
+ // @value > min.
+ if (!sumOverflows<int>(std::numeric_limits<int>::min(), offset, -1)) {
+ setRelationship(
+ Relationship::safeCreate(
+ node->child1().node(), m_zero, Relationship::GreaterThan,
+ std::numeric_limits<int>::min() + offset - 1),
+ 0);
+ }
+
+ // If we have "add: @value + 1" then we know that @add <= max - 1, i.e. that
+ // @add < max.
+ if (!sumOverflows<int>(std::numeric_limits<int>::max(), -offset, 1)) {
+ setRelationship(
+ Relationship(
+ node, m_zero, Relationship::LessThan,
+ std::numeric_limits<int>::max() - offset + 1),
+ 0);
+ }
+ }
+ break;
+ }
+
+ case GetArrayLength: {
+ setRelationship(Relationship(node, m_zero, Relationship::GreaterThan, -1));
+ break;
+ }
+
+ case Upsilon: {
+ setRelationship(
+ Relationship::safeCreate(
+ node->child1().node(), node->phi(), Relationship::Equal, 0));
+
+ auto iter = m_relationships.find(node->child1().node());
+ if (iter != m_relationships.end()) {
+ Vector<Relationship> toAdd;
+ for (Relationship relationship : iter->value) {
+ Relationship newRelationship = relationship;
+ if (node->phi() == newRelationship.right())
+ continue;
+ newRelationship.setLeft(node->phi());
+ toAdd.append(newRelationship);
+ }
+ for (Relationship relationship : toAdd)
+ setRelationship(relationship);
+ }
+ break;
+ }
+
+ default:
+ break;
+ }
+ }
+
+ void setRelationship(Relationship relationship, unsigned timeToLive = 1)
+ {
+ setRelationship(m_relationships, relationship, timeToLive);
+ }
+
+ void setRelationship(
+ RelationshipMap& relationshipMap, Relationship relationship, unsigned timeToLive = 1)
+ {
+ setOneSide(relationshipMap, relationship, timeToLive);
+ setOneSide(relationshipMap, relationship.flipped(), timeToLive);
+ }
+
+ void setOneSide(
+ RelationshipMap& relationshipMap, Relationship relationship, unsigned timeToLive = 1)
+ {
+ if (!relationship)
+ return;
+
+ if (verbose)
+ dataLog(" Setting: ", relationship, " (ttl = ", timeToLive, ")\n");
+
+ auto result = relationshipMap.add(
+ relationship.left(), Vector<Relationship>());
+ Vector<Relationship>& relationships = result.iterator->value;
+ Vector<Relationship> toAdd;
+ bool found = false;
+ for (Relationship& otherRelationship : relationships) {
+ if (otherRelationship.sameNodesAs(relationship)) {
+ if (Relationship filtered = otherRelationship.filter(relationship)) {
+ ASSERT(filtered.left() == relationship.left());
+ otherRelationship = filtered;
+ found = true;
+ }
+ }
+
+ if (timeToLive && otherRelationship.kind() == Relationship::Equal) {
+ if (verbose)
+ dataLog(" Considering: ", otherRelationship, "\n");
+
+ // We have:
+ // @a op @b + C
+ // @a == @c + D
+ //
+ // This implies:
+ // @c + D op @b + C
+ // @c op @b + C - D
+ //
+ // Where: @a == relationship.left(), @b == relationship.right(),
+ // @a == otherRelationship.left(), @c == otherRelationship.right().
+
+ if (otherRelationship.offset() != std::numeric_limits<int>::min()) {
+ Relationship newRelationship = relationship;
+ if (newRelationship.right() != otherRelationship.right()) {
+ newRelationship.setLeft(otherRelationship.right());
+ if (newRelationship.addToOffset(-otherRelationship.offset()))
+ toAdd.append(newRelationship);
+ }
+ }
+ }
+ }
+
+ if (!found)
+ relationships.append(relationship);
+
+ for (Relationship anotherRelationship : toAdd) {
+ ASSERT(timeToLive);
+ setOneSide(relationshipMap, anotherRelationship, timeToLive - 1);
+ }
+ }
+
+ bool mergeTo(RelationshipMap& relationshipMap, BasicBlock* target)
+ {
+ if (verbose) {
+ dataLog("Merging to ", pointerDump(target), ":\n");
+ dataLog(" Incoming: ", listDump(sortedRelationships(relationshipMap)), "\n");
+ dataLog(" At head: ", listDump(sortedRelationships(m_relationshipsAtHead[target])), "\n");
+ }
+
+ if (m_seenBlocks.add(target)) {
+ // This is a new block. We copy subject to liveness pruning.
+ auto isLive = [&] (Node* node) {
+ if (node == m_zero)
+ return true;
+ return target->ssa->liveAtHead.contains(node);
+ };
+
+ for (auto& entry : relationshipMap) {
+ if (!isLive(entry.key))
+ continue;
+
+ Vector<Relationship> values;
+ for (Relationship relationship : entry.value) {
+ ASSERT(relationship.left() == entry.key);
+ if (isLive(relationship.right())) {
+ if (verbose)
+ dataLog(" Propagating ", relationship, "\n");
+ values.append(relationship);
+ }
+ }
+
+ std::sort(values.begin(), values.end());
+ m_relationshipsAtHead[target].add(entry.key, values);
+ }
+ return true;
+ }
+
+ // Merge by intersecting. We have no notion of BOTTOM, so we use the omission of
+ // relationships for a pair of nodes to mean TOP. The reason why we don't need BOTTOM
+ // is (1) we just overapproximate contradictions and (2) a value never having been
+ // assigned would only happen if we have not processed the node's predecessor. We
+ // shouldn't process blocks until we have processed the block's predecessor because we
+ // are using reverse postorder.
+ Vector<Node*> toRemove;
+ bool changed = false;
+ for (auto& entry : m_relationshipsAtHead[target]) {
+ auto iter = relationshipMap.find(entry.key);
+ if (iter == relationshipMap.end()) {
+ toRemove.append(entry.key);
+ changed = true;
+ continue;
+ }
+
+ Vector<Relationship> mergedRelationships;
+ for (Relationship targetRelationship : entry.value) {
+ for (Relationship sourceRelationship : iter->value) {
+ if (verbose)
+ dataLog(" Merging ", targetRelationship, " and ", sourceRelationship, ":\n");
+ Relationship newRelationship =
+ targetRelationship.merge(sourceRelationship);
+
+ if (verbose)
+ dataLog(" Got ", newRelationship, "\n");
+
+ if (!newRelationship)
+ continue;
+
+ // We need to filter() to avoid exponential explosion of identical
+ // relationships. We do this here to avoid making setOneSide() do
+ // more work, since we expect setOneSide() will be called more
+ // frequently. Here's an example. At some point someone might start
+ // with two relationships like @a > @b - C and @a < @b + D. Then
+ // someone does a setRelationship() passing something that turns
+ // both of these into @a == @b. Now we have @a == @b duplicated.
+ // Let's say that this duplicate @a == @b ends up at the head of a
+ // loop. If we didn't have this rule, then the loop would propagate
+ // duplicate @a == @b's onto the existing duplicate @a == @b's.
+ // There would be four pairs of @a == @b, each of which would
+ // create a new @a == @b. Now we'd have four of these duplicates
+ // and the next time around we'd have 8, then 16, etc. We avoid
+ // this here by doing this filtration. That might be a bit of
+ // overkill, since it's probably just the identical duplicate
+ // relationship case we want' to avoid. But, I'll keep this until
+ // we have evidence that this is a performance problem. Remember -
+ // we are already dealing with a list that is pruned down to
+ // relationships with identical left operand. It shouldn't be a
+ // large list.
+ bool found = false;
+ for (Relationship& existingRelationship : mergedRelationships) {
+ if (existingRelationship.sameNodesAs(newRelationship)) {
+ Relationship filtered =
+ existingRelationship.filter(newRelationship);
+ if (filtered) {
+ existingRelationship = filtered;
+ found = true;
+ break;
+ }
+ }
+ }
+
+ if (!found)
+ mergedRelationships.append(newRelationship);
+ }
+ }
+ std::sort(mergedRelationships.begin(), mergedRelationships.end());
+ if (entry.value == mergedRelationships)
+ continue;
+
+ entry.value = mergedRelationships;
+ changed = true;
+ }
+ for (Node* node : toRemove)
+ m_relationshipsAtHead[target].remove(node);
+
+ return changed;
+ }
+
+ Vector<Relationship> sortedRelationships(const RelationshipMap& relationships)
+ {
+ Vector<Relationship> result;
+ for (auto& entry : relationships)
+ result.appendVector(entry.value);
+ std::sort(result.begin(), result.end());
+ return result;
+ }
+
+ Vector<Relationship> sortedRelationships()
+ {
+ return sortedRelationships(m_relationships);
+ }
+
+ Node* m_zero;
+ RelationshipMap m_relationships;
+ BlockSet m_seenBlocks;
+ BlockMap<RelationshipMap> m_relationshipsAtHead;
+ InsertionSet m_insertionSet;
+};
+
+} // anonymous namespace
+
+bool performIntegerRangeOptimization(Graph& graph)
+{
+ SamplingRegion samplingRegion("DFG Integer Range Optimization Phase");
+ return runPhase<IntegerRangeOptimizationPhase>(graph);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
Added: trunk/Source/_javascript_Core/dfg/DFGIntegerRangeOptimizationPhase.h (0 => 185640)
--- trunk/Source/_javascript_Core/dfg/DFGIntegerRangeOptimizationPhase.h (rev 0)
+++ trunk/Source/_javascript_Core/dfg/DFGIntegerRangeOptimizationPhase.h 2015-06-17 05:31:30 UTC (rev 185640)
@@ -0,0 +1,47 @@
+/*
+ * 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 DFGIntegerRangeOptimizationPhase_h
+#define DFGIntegerRangeOptimizationPhase_h
+
+#if ENABLE(DFG_JIT)
+
+namespace JSC { namespace DFG {
+
+class Graph;
+
+// Removes overflow checks and out-of-bounds checks by doing a forward flow analysis to prove
+// inequalities. It will remove the overflow and bounds checks in loops like:
+//
+// for (var i = 0; i < array.length; ++i) array[i];
+
+bool performIntegerRangeOptimization(Graph&);
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGIntegerRangeOptimizationPhase_h
+
Modified: trunk/Source/_javascript_Core/dfg/DFGPlan.cpp (185639 => 185640)
--- trunk/Source/_javascript_Core/dfg/DFGPlan.cpp 2015-06-17 05:18:21 UTC (rev 185639)
+++ trunk/Source/_javascript_Core/dfg/DFGPlan.cpp 2015-06-17 05:31:30 UTC (rev 185640)
@@ -44,6 +44,7 @@
#include "DFGFixupPhase.h"
#include "DFGGraphSafepoint.h"
#include "DFGIntegerCheckCombiningPhase.h"
+#include "DFGIntegerRangeOptimizationPhase.h"
#include "DFGInvalidationPointInjectionPhase.h"
#include "DFGJITCompiler.h"
#include "DFGLICMPhase.h"
@@ -357,6 +358,8 @@
performConstantHoisting(dfg);
performGlobalCSE(dfg);
performLivenessAnalysis(dfg);
+ performIntegerRangeOptimization(dfg);
+ performLivenessAnalysis(dfg);
performCFA(dfg);
performConstantFolding(dfg);
performCleanUp(dfg); // Reduce the graph size a lot.
Added: trunk/Source/_javascript_Core/tests/stress/add-overflows-after-not-equal.js (0 => 185640)
--- trunk/Source/_javascript_Core/tests/stress/add-overflows-after-not-equal.js (rev 0)
+++ trunk/Source/_javascript_Core/tests/stress/add-overflows-after-not-equal.js 2015-06-17 05:31:30 UTC (rev 185640)
@@ -0,0 +1,16 @@
+function foo(a) {
+ if (a != 0)
+ return a + 1;
+}
+
+noInline(foo);
+
+for (var i = 0; i < 10000; ++i) {
+ var result = foo(42);
+ if (result != 43)
+ throw "Error: bad result in loop: " + result;
+}
+
+var result = foo(2147483647);
+if (result != 2147483648)
+ throw "Error: bad result at end: " + result;
Added: trunk/Source/_javascript_Core/tests/stress/no-abc-skippy-loop.js (0 => 185640)
--- trunk/Source/_javascript_Core/tests/stress/no-abc-skippy-loop.js (rev 0)
+++ trunk/Source/_javascript_Core/tests/stress/no-abc-skippy-loop.js 2015-06-17 05:31:30 UTC (rev 185640)
@@ -0,0 +1,24 @@
+function foo(array) {
+ var result = 0;
+ for (var i = 0; i != array.length; i += 2) {
+ var element = array[i];
+ if (element === void 0)
+ break;
+ result += array[i];
+ }
+ return result;
+}
+
+noInline(foo);
+
+var array = [1, 2, 3, 4];
+for (var i = 0; i < 10000; ++i) {
+ var result = foo(array);
+ if (result != 4)
+ throw "Error: bad result in loop: " + result;
+}
+
+var array = [1, 2, 3];
+var result = foo(array);
+if (result != 4)
+ throw "Error: bad result at end: " + result;
Added: trunk/Source/_javascript_Core/tests/stress/no-abc-skippy-paired-loop.js (0 => 185640)
--- trunk/Source/_javascript_Core/tests/stress/no-abc-skippy-paired-loop.js (rev 0)
+++ trunk/Source/_javascript_Core/tests/stress/no-abc-skippy-paired-loop.js 2015-06-17 05:31:30 UTC (rev 185640)
@@ -0,0 +1,20 @@
+function foo(array) {
+ var result = 0;
+ for (var i = 0; i < array.length; i += 2)
+ result += array[i] + array[i + 1];
+ return result;
+}
+
+noInline(foo);
+
+var array = [1, 2, 3, 4];
+for (var i = 0; i < 10000; ++i) {
+ var result = foo(array);
+ if (result != 10)
+ throw "Error: bad result in loop: " + result;
+}
+
+var array = [1, 2, 3];
+var result = foo(array);
+if ("" + result != "NaN")
+ throw "Error: bad result at end: " + result;
Added: trunk/Source/_javascript_Core/tests/stress/sub-overflows-after-not-equal.js (0 => 185640)
--- trunk/Source/_javascript_Core/tests/stress/sub-overflows-after-not-equal.js (rev 0)
+++ trunk/Source/_javascript_Core/tests/stress/sub-overflows-after-not-equal.js 2015-06-17 05:31:30 UTC (rev 185640)
@@ -0,0 +1,16 @@
+function foo(a) {
+ if (a != 0)
+ return a - 1;
+}
+
+noInline(foo);
+
+for (var i = 0; i < 10000; ++i) {
+ var result = foo(42);
+ if (result != 41)
+ throw "Error: bad result in loop: " + result;
+}
+
+var result = foo(-2147483648);
+if (result != -2147483649)
+ throw "Error: bad result at end: " + result;
_______________________________________________ webkit-changes mailing list webkit-changes@lists.webkit.org https://lists.webkit.org/mailman/listinfo/webkit-changes
