FTL should eliminate array bounds checks in loops
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 17 Jun 2015 05:31:30 +0000 (05:31 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 17 Jun 2015 05:31:30 +0000 (05:31 +0000)
commit621677b15f68f73b374a3e713365f54dc23ddef2
tree11e21f2ce095cb6fe8129674a1ca6ec7cf01fc36
parent2a8a500c14a9f2ea25e6ae4d1667765f27f1de50
FTL should eliminate array bounds checks in loops
https://bugs.webkit.org/show_bug.cgi?id=145768

Reviewed by Benjamin Poulain.
Source/JavaScriptCore:

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:
* JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
* JavaScriptCore.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.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@185640 268f45cc-cd09-0410-ab3c-d52691b4dbfc
27 files changed:
LayoutTests/ChangeLog
LayoutTests/js/regress/abc-forward-loop-equal-expected.txt [new file with mode: 0644]
LayoutTests/js/regress/abc-forward-loop-equal.html [new file with mode: 0644]
LayoutTests/js/regress/abc-postfix-backward-loop-expected.txt [new file with mode: 0644]
LayoutTests/js/regress/abc-postfix-backward-loop.html [new file with mode: 0644]
LayoutTests/js/regress/abc-simple-backward-loop-expected.txt [new file with mode: 0644]
LayoutTests/js/regress/abc-simple-backward-loop.html [new file with mode: 0644]
LayoutTests/js/regress/abc-simple-forward-loop-expected.txt [new file with mode: 0644]
LayoutTests/js/regress/abc-simple-forward-loop.html [new file with mode: 0644]
LayoutTests/js/regress/abc-skippy-loop-expected.txt [new file with mode: 0644]
LayoutTests/js/regress/abc-skippy-loop.html [new file with mode: 0644]
LayoutTests/js/regress/script-tests/abc-forward-loop-equal.js [new file with mode: 0644]
LayoutTests/js/regress/script-tests/abc-postfix-backward-loop.js [new file with mode: 0644]
LayoutTests/js/regress/script-tests/abc-simple-backward-loop.js [new file with mode: 0644]
LayoutTests/js/regress/script-tests/abc-simple-forward-loop.js [new file with mode: 0644]
LayoutTests/js/regress/script-tests/abc-skippy-loop.js [new file with mode: 0644]
Source/JavaScriptCore/CMakeLists.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGPlan.cpp
Source/JavaScriptCore/tests/stress/add-overflows-after-not-equal.js [new file with mode: 0644]
Source/JavaScriptCore/tests/stress/no-abc-skippy-loop.js [new file with mode: 0644]
Source/JavaScriptCore/tests/stress/no-abc-skippy-paired-loop.js [new file with mode: 0644]
Source/JavaScriptCore/tests/stress/sub-overflows-after-not-equal.js [new file with mode: 0644]