DFG overflow check elimination is too smart for its own good
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 12 Mar 2013 06:43:54 +0000 (06:43 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 12 Mar 2013 06:43:54 +0000 (06:43 +0000)
https://bugs.webkit.org/show_bug.cgi?id=111832

Source/JavaScriptCore:

Reviewed by Oliver Hunt and Gavin Barraclough.

Rolling this back in after fixing accidental misuse of JSValue. The code was doing value < someInt
rather than value.asInt32() < someInt. This "worked" when isWithinPowerOfTwo wasn't templatized.
It worked by always being false and always disabling the relvant optimization.

This improves overflow check elimination in three ways:

1) It reduces the amount of time the compiler will spend doing it.

2) It fixes bugs where overflow check elimination was overzealous. Precisely, for a binary operation
   over @a and @b where both @a and @b will type check that their inputs (@a->children, @b->children)
   are int32's and then perform a possibly-overflowing operation, we must be careful not to assume
   that @a's non-int32 parts don't matter if at the point that @a runs we have as yet not proved that
   @b->children are int32's and that hence @b might produce a large enough result that doubles would
   start chopping low bits. The specific implication of this is that for a binary operation to not
   propagate that it cares about non-int32 parts (NodeUsedAsNumber), we must prove that at least one
   of the inputs is guaranteed to produce a result within 2^32 and that there won't be a tower of such
   operations large enough to ultimately produce a double greater than 2^52 (roughly). We achieve the
   latter by disabling this optimization for very large basic blocks. It's noteworthy that blocks that
   large won't even make it into the DFG currently.

3) It makes the overflow check elimination more precise for cases where the inputs to an Add or Sub
   are the outputs of a bit-op. For example in (@a + (@b | 0)) | 0, we don't need to propagate
   NodeUsedAsNumber to either @a or @b.

This is neutral on V8v7 and a slight speed-up on compile time benchmarks.

* CMakeLists.txt:
* GNUmakefile.list.am:
* JavaScriptCore.xcodeproj/project.pbxproj:
* Target.pri:
* dfg/DFGArrayMode.cpp:
(JSC::DFG::ArrayMode::refine):
* dfg/DFGBackwardsPropagationPhase.cpp: Added.
(DFG):
(BackwardsPropagationPhase):
(JSC::DFG::BackwardsPropagationPhase::BackwardsPropagationPhase):
(JSC::DFG::BackwardsPropagationPhase::run):
(JSC::DFG::BackwardsPropagationPhase::isNotNegZero):
(JSC::DFG::BackwardsPropagationPhase::isNotZero):
(JSC::DFG::BackwardsPropagationPhase::isWithinPowerOfTwoForConstant):
(JSC::DFG::BackwardsPropagationPhase::isWithinPowerOfTwoNonRecursive):
(JSC::DFG::BackwardsPropagationPhase::isWithinPowerOfTwo):
(JSC::DFG::BackwardsPropagationPhase::mergeDefaultFlags):
(JSC::DFG::BackwardsPropagationPhase::propagate):
(JSC::DFG::performBackwardsPropagation):
* dfg/DFGBackwardsPropagationPhase.h: Added.
(DFG):
* dfg/DFGCPSRethreadingPhase.cpp:
(JSC::DFG::CPSRethreadingPhase::run):
(JSC::DFG::CPSRethreadingPhase::clearIsLoadedFrom):
(CPSRethreadingPhase):
(JSC::DFG::CPSRethreadingPhase::canonicalizeGetLocalFor):
(JSC::DFG::CPSRethreadingPhase::canonicalizeFlushOrPhantomLocalFor):
* dfg/DFGDriver.cpp:
(JSC::DFG::compile):
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::dump):
* dfg/DFGNodeFlags.cpp:
(JSC::DFG::dumpNodeFlags):
(DFG):
* dfg/DFGNodeFlags.h:
(DFG):
* dfg/DFGPredictionPropagationPhase.cpp:
(PredictionPropagationPhase):
(JSC::DFG::PredictionPropagationPhase::propagate):
* dfg/DFGUnificationPhase.cpp:
(JSC::DFG::UnificationPhase::run):
* dfg/DFGVariableAccessData.h:
(JSC::DFG::VariableAccessData::VariableAccessData):
(JSC::DFG::VariableAccessData::mergeIsLoadedFrom):
(VariableAccessData):
(JSC::DFG::VariableAccessData::setIsLoadedFrom):
(JSC::DFG::VariableAccessData::isLoadedFrom):

LayoutTests:

Reviewed by Oliver Hunt and Gavin Barraclough.

* fast/js/dfg-arith-add-overflow-check-elimination-predicted-but-not-proven-int-expected.txt: Added.
* fast/js/dfg-arith-add-overflow-check-elimination-predicted-but-not-proven-int.html: Added.
* fast/js/dfg-arith-add-overflow-check-elimination-tower-of-large-numbers-expected.txt: Added.
* fast/js/dfg-arith-add-overflow-check-elimination-tower-of-large-numbers.html: Added.
* fast/js/jsc-test-list:
* fast/js/script-tests/dfg-arith-add-overflow-check-elimination-predicted-but-not-proven-int.js: Added.
(foo):
(bar):
* fast/js/script-tests/dfg-arith-add-overflow-check-elimination-tower-of-large-numbers.js: Added.
(foo):
(bar):

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

24 files changed:
LayoutTests/ChangeLog
LayoutTests/fast/js/dfg-arith-add-overflow-check-elimination-predicted-but-not-proven-int-expected.txt [new file with mode: 0644]
LayoutTests/fast/js/dfg-arith-add-overflow-check-elimination-predicted-but-not-proven-int.html [new file with mode: 0644]
LayoutTests/fast/js/dfg-arith-add-overflow-check-elimination-tower-of-large-numbers-expected.txt [new file with mode: 0644]
LayoutTests/fast/js/dfg-arith-add-overflow-check-elimination-tower-of-large-numbers.html [new file with mode: 0644]
LayoutTests/fast/js/jsc-test-list
LayoutTests/fast/js/script-tests/dfg-arith-add-overflow-check-elimination-predicted-but-not-proven-int.js [new file with mode: 0644]
LayoutTests/fast/js/script-tests/dfg-arith-add-overflow-check-elimination-tower-of-large-numbers.js [new file with mode: 0644]
Source/JavaScriptCore/CMakeLists.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/GNUmakefile.list.am
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/Target.pri
Source/JavaScriptCore/dfg/DFGArrayMode.cpp
Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.cpp [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGCPSRethreadingPhase.cpp
Source/JavaScriptCore/dfg/DFGDriver.cpp
Source/JavaScriptCore/dfg/DFGGraph.cpp
Source/JavaScriptCore/dfg/DFGNodeFlags.cpp
Source/JavaScriptCore/dfg/DFGNodeFlags.h
Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp
Source/JavaScriptCore/dfg/DFGUnificationPhase.cpp
Source/JavaScriptCore/dfg/DFGVariableAccessData.h

index 9ac8df8..722a4c7 100644 (file)
@@ -1,3 +1,22 @@
+2013-03-11  Filip Pizlo  <fpizlo@apple.com>
+
+        DFG overflow check elimination is too smart for its own good
+        https://bugs.webkit.org/show_bug.cgi?id=111832
+
+        Reviewed by Oliver Hunt and Gavin Barraclough.
+
+        * fast/js/dfg-arith-add-overflow-check-elimination-predicted-but-not-proven-int-expected.txt: Added.
+        * fast/js/dfg-arith-add-overflow-check-elimination-predicted-but-not-proven-int.html: Added.
+        * fast/js/dfg-arith-add-overflow-check-elimination-tower-of-large-numbers-expected.txt: Added.
+        * fast/js/dfg-arith-add-overflow-check-elimination-tower-of-large-numbers.html: Added.
+        * fast/js/jsc-test-list:
+        * fast/js/script-tests/dfg-arith-add-overflow-check-elimination-predicted-but-not-proven-int.js: Added.
+        (foo):
+        (bar):
+        * fast/js/script-tests/dfg-arith-add-overflow-check-elimination-tower-of-large-numbers.js: Added.
+        (foo):
+        (bar):
+
 2013-03-11  Pavel Feldman  <pfeldman@chromium.org>
 
         Not reviewed: Chromium expectations updated.
diff --git a/LayoutTests/fast/js/dfg-arith-add-overflow-check-elimination-predicted-but-not-proven-int-expected.txt b/LayoutTests/fast/js/dfg-arith-add-overflow-check-elimination-predicted-but-not-proven-int-expected.txt
new file mode 100644 (file)
index 0000000..2665137
--- /dev/null
@@ -0,0 +1,117 @@
+Tests that when values predicted but not proven int are used in a tower of additions, we don't eliminate the overflow check unsoundly.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(1, 2, {f:3}) is 6
+PASS bar(2147483645, 2147483644, {f:9007199254740990}) is -8
+PASS bar(2147483643, 2147483643, {f:18014398509481980}) is -16
+PASS bar(2147483643, 2147483642, {f:36028797018963960}) is -16
+PASS bar(2147483642, 2147483642, {f:36028797018963960}) is -16
+PASS bar(2147483641, 2147483640, {f:144115188075855840}) is -32
+PASS bar(2147483640, 2147483640, {f:144115188075855840}) is -64
+PASS bar(2147483640, 2147483639, {f:288230376151711680}) is -64
+PASS bar(2147483639, 2147483639, {f:288230376151711680}) is -64
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
diff --git a/LayoutTests/fast/js/dfg-arith-add-overflow-check-elimination-predicted-but-not-proven-int.html b/LayoutTests/fast/js/dfg-arith-add-overflow-check-elimination-predicted-but-not-proven-int.html
new file mode 100644 (file)
index 0000000..d829718
--- /dev/null
@@ -0,0 +1,10 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src="resources/js-test-pre.js"></script>
+</head>
+<body>
+<script src="script-tests/dfg-arith-add-overflow-check-elimination-predicted-but-not-proven-int.js"></script>
+<script src="resources/js-test-post.js"></script>
+</body>
+</html>
diff --git a/LayoutTests/fast/js/dfg-arith-add-overflow-check-elimination-tower-of-large-numbers-expected.txt b/LayoutTests/fast/js/dfg-arith-add-overflow-check-elimination-tower-of-large-numbers-expected.txt
new file mode 100644 (file)
index 0000000..4ee91ea
--- /dev/null
@@ -0,0 +1,210 @@
+Tests that if we have a tower of large numerical constants being added to each other, the DFG knows that a sufficiently large tower may produce a large enough value that overflow check elimination must be careful.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(1, 2) is 0
+PASS bar(2147483645, 2147483644) is -10
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
diff --git a/LayoutTests/fast/js/dfg-arith-add-overflow-check-elimination-tower-of-large-numbers.html b/LayoutTests/fast/js/dfg-arith-add-overflow-check-elimination-tower-of-large-numbers.html
new file mode 100644 (file)
index 0000000..6ad20dc
--- /dev/null
@@ -0,0 +1,10 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src="resources/js-test-pre.js"></script>
+</head>
+<body>
+<script src="script-tests/dfg-arith-add-overflow-check-elimination-tower-of-large-numbers.js"></script>
+<script src="resources/js-test-post.js"></script>
+</body>
+</html>
index ea95c22..1712244 100644 (file)
@@ -82,6 +82,8 @@ fast/js/dfg-arguments-osr-exit-multiple-blocks
 fast/js/dfg-arguments-osr-exit-multiple-blocks-before-exit
 fast/js/dfg-arguments-out-of-bounds
 fast/js/dfg-arguments-unexpected-escape
+fast/js/dfg-arith-add-overflow-check-elimination-tower-of-large-numbers
+fast/js/dfg-arith-add-overflow-check-elimination-predicted-but-not-proven-int
 fast/js/dfg-arrayify-elimination
 fast/js/dfg-arrayify-when-late-prevent-extensions
 fast/js/dfg-arrayify-when-prevent-extensions
diff --git a/LayoutTests/fast/js/script-tests/dfg-arith-add-overflow-check-elimination-predicted-but-not-proven-int.js b/LayoutTests/fast/js/script-tests/dfg-arith-add-overflow-check-elimination-predicted-but-not-proven-int.js
new file mode 100644 (file)
index 0000000..52bedd9
--- /dev/null
@@ -0,0 +1,44 @@
+description(
+"Tests that when values predicted but not proven int are used in a tower of additions, we don't eliminate the overflow check unsoundly."
+);
+
+function foo(a, b, o) {
+    return (a + b + o.f) | 0;
+}
+
+function bar(a, b, o) {
+    eval(""); // Prevent this function from being opt compiled.
+    return foo(a, b, o);
+}
+
+var badCases = [
+    {a:2147483645, b:2147483644, c:9007199254740990, expected:-8},
+    {a:2147483643, b:2147483643, c:18014398509481980, expected:-16},
+    {a:2147483643, b:2147483642, c:36028797018963960, expected:-16},
+    {a:2147483642, b:2147483642, c:36028797018963960, expected:-16},
+    {a:2147483641, b:2147483640, c:144115188075855840, expected:-32},
+    {a:2147483640, b:2147483640, c:144115188075855840, expected:-64},
+    {a:2147483640, b:2147483639, c:288230376151711680, expected:-64},
+    {a:2147483639, b:2147483639, c:288230376151711680, expected:-64}
+];
+
+var warmup = 100;
+
+for (var i = 0; i < warmup + badCases.length; ++i) {
+    var a, b, c;
+    var expected;
+    if (i < warmup) {
+        a = 1;
+        b = 2;
+        c = 3;
+        expected = 6;
+    } else {
+        var current = badCases[i - warmup];
+        a = current.a;
+        b = current.b;
+        c = current.c;
+        expected = current.expected;
+    }
+    shouldBe("bar(" + a + ", " + b + ", {f:" + c + "})", "" + expected);
+}
+
diff --git a/LayoutTests/fast/js/script-tests/dfg-arith-add-overflow-check-elimination-tower-of-large-numbers.js b/LayoutTests/fast/js/script-tests/dfg-arith-add-overflow-check-elimination-tower-of-large-numbers.js
new file mode 100644 (file)
index 0000000..4c3656f
--- /dev/null
@@ -0,0 +1,37 @@
+description(
+"Tests that if we have a tower of large numerical constants being added to each other, the DFG knows that a sufficiently large tower may produce a large enough value that overflow check elimination must be careful."
+);
+
+function foo(a, b) {
+    return (a + b + 281474976710655 + 281474976710655 + 281474976710655 + 281474976710655 +
+            281474976710655 + 281474976710655 + 281474976710655 + 281474976710655 +
+            281474976710655 + 281474976710655 + 281474976710655 + 281474976710655 +
+            281474976710655 + 281474976710655 + 281474976710655 + 281474976710655 +
+            281474976710655 + 281474976710655 + 281474976710655 + 281474976710655 +
+            281474976710655 + 281474976710655 + 281474976710655 + 281474976710655 +
+            281474976710655 + 281474976710655 + 281474976710655 + 281474976710655 +
+            281474976710655 + 281474976710655 + 281474976710655 + 281474976710655 + 30) | 0;
+}
+
+function bar(a, b, o) {
+    eval(""); // Prevent this function from being opt compiled.
+    return foo(a, b, o);
+}
+
+var warmup = 200;
+
+for (var i = 0; i < warmup + 1; ++i) {
+    var a, b, c;
+    var expected;
+    if (i < warmup) {
+        a = 1;
+        b = 2;
+        expected = 0;
+    } else {
+        a = 2147483645;
+        b = 2147483644;
+        expected = -10;
+    }
+    shouldBe("bar(" + a + ", " + b + ")", "" + expected);
+}
+
index b573ce1..964b51b 100644 (file)
@@ -78,6 +78,7 @@ set(JavaScriptCore_SOURCES
     dfg/DFGArgumentsSimplificationPhase.cpp
     dfg/DFGArrayMode.cpp
     dfg/DFGAssemblyHelpers.cpp
+    dfg/DFGBackwardsPropagationPhase.cpp
     dfg/DFGByteCodeParser.cpp
     dfg/DFGCapabilities.cpp
     dfg/DFGCommon.cpp
index e4e48c6..9896876 100644 (file)
@@ -1,3 +1,84 @@
+2013-03-11  Filip Pizlo  <fpizlo@apple.com>
+
+        DFG overflow check elimination is too smart for its own good
+        https://bugs.webkit.org/show_bug.cgi?id=111832
+
+        Reviewed by Oliver Hunt and Gavin Barraclough.
+        
+        Rolling this back in after fixing accidental misuse of JSValue. The code was doing value < someInt
+        rather than value.asInt32() < someInt. This "worked" when isWithinPowerOfTwo wasn't templatized.
+        It worked by always being false and always disabling the relvant optimization.
+        
+        This improves overflow check elimination in three ways:
+        
+        1) It reduces the amount of time the compiler will spend doing it.
+        
+        2) It fixes bugs where overflow check elimination was overzealous. Precisely, for a binary operation
+           over @a and @b where both @a and @b will type check that their inputs (@a->children, @b->children)
+           are int32's and then perform a possibly-overflowing operation, we must be careful not to assume
+           that @a's non-int32 parts don't matter if at the point that @a runs we have as yet not proved that
+           @b->children are int32's and that hence @b might produce a large enough result that doubles would
+           start chopping low bits. The specific implication of this is that for a binary operation to not
+           propagate that it cares about non-int32 parts (NodeUsedAsNumber), we must prove that at least one
+           of the inputs is guaranteed to produce a result within 2^32 and that there won't be a tower of such
+           operations large enough to ultimately produce a double greater than 2^52 (roughly). We achieve the
+           latter by disabling this optimization for very large basic blocks. It's noteworthy that blocks that
+           large won't even make it into the DFG currently.
+        
+        3) It makes the overflow check elimination more precise for cases where the inputs to an Add or Sub
+           are the outputs of a bit-op. For example in (@a + (@b | 0)) | 0, we don't need to propagate
+           NodeUsedAsNumber to either @a or @b.
+        
+        This is neutral on V8v7 and a slight speed-up on compile time benchmarks.
+
+        * CMakeLists.txt:
+        * GNUmakefile.list.am:
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * Target.pri:
+        * dfg/DFGArrayMode.cpp:
+        (JSC::DFG::ArrayMode::refine):
+        * dfg/DFGBackwardsPropagationPhase.cpp: Added.
+        (DFG):
+        (BackwardsPropagationPhase):
+        (JSC::DFG::BackwardsPropagationPhase::BackwardsPropagationPhase):
+        (JSC::DFG::BackwardsPropagationPhase::run):
+        (JSC::DFG::BackwardsPropagationPhase::isNotNegZero):
+        (JSC::DFG::BackwardsPropagationPhase::isNotZero):
+        (JSC::DFG::BackwardsPropagationPhase::isWithinPowerOfTwoForConstant):
+        (JSC::DFG::BackwardsPropagationPhase::isWithinPowerOfTwoNonRecursive):
+        (JSC::DFG::BackwardsPropagationPhase::isWithinPowerOfTwo):
+        (JSC::DFG::BackwardsPropagationPhase::mergeDefaultFlags):
+        (JSC::DFG::BackwardsPropagationPhase::propagate):
+        (JSC::DFG::performBackwardsPropagation):
+        * dfg/DFGBackwardsPropagationPhase.h: Added.
+        (DFG):
+        * dfg/DFGCPSRethreadingPhase.cpp:
+        (JSC::DFG::CPSRethreadingPhase::run):
+        (JSC::DFG::CPSRethreadingPhase::clearIsLoadedFrom):
+        (CPSRethreadingPhase):
+        (JSC::DFG::CPSRethreadingPhase::canonicalizeGetLocalFor):
+        (JSC::DFG::CPSRethreadingPhase::canonicalizeFlushOrPhantomLocalFor):
+        * dfg/DFGDriver.cpp:
+        (JSC::DFG::compile):
+        * dfg/DFGGraph.cpp:
+        (JSC::DFG::Graph::dump):
+        * dfg/DFGNodeFlags.cpp:
+        (JSC::DFG::dumpNodeFlags):
+        (DFG):
+        * dfg/DFGNodeFlags.h:
+        (DFG):
+        * dfg/DFGPredictionPropagationPhase.cpp:
+        (PredictionPropagationPhase):
+        (JSC::DFG::PredictionPropagationPhase::propagate):
+        * dfg/DFGUnificationPhase.cpp:
+        (JSC::DFG::UnificationPhase::run):
+        * dfg/DFGVariableAccessData.h:
+        (JSC::DFG::VariableAccessData::VariableAccessData):
+        (JSC::DFG::VariableAccessData::mergeIsLoadedFrom):
+        (VariableAccessData):
+        (JSC::DFG::VariableAccessData::setIsLoadedFrom):
+        (JSC::DFG::VariableAccessData::isLoadedFrom):
+
 2013-03-11  Oliver Hunt  <oliver@apple.com>
 
         Harden JSStringJoiner
index 08f0cf9..2312154 100644 (file)
@@ -184,6 +184,8 @@ javascriptcore_sources += \
        Source/JavaScriptCore/dfg/DFGArrayifySlowPathGenerator.h \
        Source/JavaScriptCore/dfg/DFGAssemblyHelpers.cpp \
        Source/JavaScriptCore/dfg/DFGAssemblyHelpers.h \
+       Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.cpp \
+       Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.h \
        Source/JavaScriptCore/dfg/DFGBasicBlock.h \
        Source/JavaScriptCore/dfg/DFGBasicBlockInlines.h \
        Source/JavaScriptCore/dfg/DFGBranchDirection.h \
index b8ef06c..c6d25e0 100644 (file)
                0F63948515E4811B006A597C /* DFGArrayMode.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F63948215E48114006A597C /* DFGArrayMode.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F66E16B14DF3F1600B7B2E4 /* DFGAdjacencyList.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F66E16814DF3F1300B7B2E4 /* DFGAdjacencyList.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F66E16C14DF3F1600B7B2E4 /* DFGEdge.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F66E16914DF3F1300B7B2E4 /* DFGEdge.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               0F714CA416EA92F000F3EBEB /* DFGBackwardsPropagationPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F714CA116EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.cpp */; };
+               0F714CA516EA92F200F3EBEB /* DFGBackwardsPropagationPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F714CA216EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F73D7AE165A142D00ACAB71 /* ClosureCallStubRoutine.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F73D7AB165A142A00ACAB71 /* ClosureCallStubRoutine.cpp */; };
                0F73D7AF165A143000ACAB71 /* ClosureCallStubRoutine.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F73D7AC165A142A00ACAB71 /* ClosureCallStubRoutine.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F766D2815A8CC1E008F363E /* JITStubRoutine.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F766D2615A8CC1B008F363E /* JITStubRoutine.cpp */; };
                0F63948215E48114006A597C /* DFGArrayMode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGArrayMode.h; path = dfg/DFGArrayMode.h; sourceTree = "<group>"; };
                0F66E16814DF3F1300B7B2E4 /* DFGAdjacencyList.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGAdjacencyList.h; path = dfg/DFGAdjacencyList.h; sourceTree = "<group>"; };
                0F66E16914DF3F1300B7B2E4 /* DFGEdge.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGEdge.h; path = dfg/DFGEdge.h; sourceTree = "<group>"; };
+               0F714CA116EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGBackwardsPropagationPhase.cpp; path = dfg/DFGBackwardsPropagationPhase.cpp; sourceTree = "<group>"; };
+               0F714CA216EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBackwardsPropagationPhase.h; path = dfg/DFGBackwardsPropagationPhase.h; sourceTree = "<group>"; };
                0F73D7AB165A142A00ACAB71 /* ClosureCallStubRoutine.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ClosureCallStubRoutine.cpp; sourceTree = "<group>"; };
                0F73D7AC165A142A00ACAB71 /* ClosureCallStubRoutine.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ClosureCallStubRoutine.h; sourceTree = "<group>"; };
                0F766D1C15A5028D008F363E /* JITStubRoutine.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JITStubRoutine.h; sourceTree = "<group>"; };
                                0F63948215E48114006A597C /* DFGArrayMode.h */,
                                0FC0976B1468AB4A00CF2442 /* DFGAssemblyHelpers.cpp */,
                                0FC0976C1468AB4A00CF2442 /* DFGAssemblyHelpers.h */,
+                               0F714CA116EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.cpp */,
+                               0F714CA216EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.h */,
                                0F620170143FCD2F0068B77C /* DFGBasicBlock.h */,
                                0FD5652216AB780A00197653 /* DFGBasicBlockInlines.h */,
                                0F8364B5164B0C0E0053329A /* DFGBranchDirection.h */,
                                0FFB921F16D033050055A5DB /* (null) in Headers */,
                                0FFB922016D033B70055A5DB /* NodeConstructors.h in Headers */,
                                0FCCAE4516D0CF7400D0C65B /* ParserError.h in Headers */,
+                               0F714CA516EA92F200F3EBEB /* DFGBackwardsPropagationPhase.h in Headers */,
                        );
                        runOnlyForDeploymentPostprocessing = 0;
                };
                                0FBE0F7616C1DB0F0082C5E8 /* DFGUnificationPhase.cpp in Sources */,
                                0F493AFA16D0CAD30084508B /* SourceProvider.cpp in Sources */,
                                ADE39FFF16DD144B0003CD4A /* PropertyTable.cpp in Sources */,
+                               0F714CA416EA92F000F3EBEB /* DFGBackwardsPropagationPhase.cpp in Sources */,
                        );
                        runOnlyForDeploymentPostprocessing = 0;
                };
index 8fefc65..3b062f2 100644 (file)
@@ -114,6 +114,7 @@ SOURCES += \
     dfg/DFGArgumentsSimplificationPhase.cpp \
     dfg/DFGArrayMode.cpp \
     dfg/DFGAssemblyHelpers.cpp \
+    dfg/DFGBackwardsPropagationPhase.cpp \
     dfg/DFGByteCodeParser.cpp \
     dfg/DFGCapabilities.cpp \
     dfg/DFGCommon.cpp \
index 6df637d..7a6f108 100644 (file)
@@ -167,14 +167,14 @@ ArrayMode ArrayMode::refine(SpeculatedType base, SpeculatedType index, Speculate
         return withTypeAndConversion(Array::Contiguous, Array::Convert);
         
     case Array::Double:
-        if (flags & NodeUsedAsIntLocally)
+        if (flags & NodeUsedAsInt)
             return withTypeAndConversion(Array::Contiguous, Array::RageConvert);
         if (!value || isNumberSpeculation(value))
             return *this;
         return withTypeAndConversion(Array::Contiguous, Array::Convert);
         
     case Array::Contiguous:
-        if (doesConversion() && (flags & NodeUsedAsIntLocally))
+        if (doesConversion() && (flags & NodeUsedAsInt))
             return withConversion(Array::RageConvert);
         return *this;
         
diff --git a/Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.cpp b/Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.cpp
new file mode 100644 (file)
index 0000000..0ed78f0
--- /dev/null
@@ -0,0 +1,369 @@
+/*
+ * Copyright (C) 2013 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 "DFGBackwardsPropagationPhase.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBasicBlockInlines.h"
+#include "DFGGraph.h"
+#include "DFGPhase.h"
+#include "Operations.h"
+
+namespace JSC { namespace DFG {
+
+class BackwardsPropagationPhase : public Phase {
+public:
+    BackwardsPropagationPhase(Graph& graph)
+        : Phase(graph, "backwards propagation")
+    {
+    }
+    
+    bool run()
+    {
+        for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
+            BasicBlock* block = m_graph.m_blocks[blockIndex].get();
+            if (!block)
+                continue;
+            
+            // Prevent a tower of overflowing additions from creating a value that is out of the
+            // safe 2^48 range.
+            m_allowNestedOverflowingAdditions = block->size() < (1 << 16);
+            
+            for (unsigned indexInBlock = block->size(); indexInBlock--;)
+                propagate(block->at(indexInBlock));
+        }
+        
+        return true;
+    }
+
+private:
+    bool isNotNegZero(Node* node)
+    {
+        if (!m_graph.isNumberConstant(node))
+            return false;
+        double value = m_graph.valueOfNumberConstant(node);
+        return !value && 1.0 / value < 0.0;
+    }
+    
+    bool isNotZero(Node* node)
+    {
+        if (!m_graph.isNumberConstant(node))
+            return false;
+        return !!m_graph.valueOfNumberConstant(node);
+    }
+
+    // Tests if the absolute value is strictly less than the power of two.
+    template<int power>
+    bool isWithinPowerOfTwoForConstant(Node* node)
+    {
+        JSValue immediateValue = node->valueOfJSConstant(codeBlock());
+        if (!immediateValue.isNumber())
+            return false;
+        double immediate = immediateValue.asNumber();
+        return immediate > -(static_cast<int64_t>(1) << power) && immediate < (static_cast<int64_t>(1) << power);
+    }
+    
+    template<int power>
+    bool isWithinPowerOfTwoNonRecursive(Node* node)
+    {
+        if (node->op() != JSConstant)
+            return false;
+        return isWithinPowerOfTwoForConstant<power>(node);
+    }
+    
+    template<int power>
+    bool isWithinPowerOfTwo(Node* node)
+    {
+        switch (node->op()) {
+        case JSConstant: {
+            return isWithinPowerOfTwoForConstant<power>(node);
+        }
+            
+        case BitAnd: {
+            if (power > 31)
+                return true;
+            
+            return isWithinPowerOfTwoNonRecursive<power>(node->child1().node())
+                || isWithinPowerOfTwoNonRecursive<power>(node->child2().node());
+        }
+            
+        case BitOr:
+        case BitXor:
+        case BitLShift:
+        case ValueToInt32: {
+            return power > 31;
+        }
+            
+        case BitRShift:
+        case BitURShift: {
+            if (power > 31)
+                return true;
+            
+            Node* shiftAmount = node->child2().node();
+            if (shiftAmount->op() != JSConstant)
+                return false;
+            JSValue immediateValue = shiftAmount->valueOfJSConstant(codeBlock());
+            if (!immediateValue.isInt32())
+                return false;
+            return immediateValue.asInt32() > 32 - power;
+        }
+            
+        default:
+            return false;
+        }
+    }
+
+    template<int power>
+    bool isWithinPowerOfTwo(Edge edge)
+    {
+        return isWithinPowerOfTwo<power>(edge.node());
+    }
+
+    bool mergeDefaultFlags(Node* node)
+    {
+        bool changed = false;
+        if (node->flags() & NodeHasVarArgs) {
+            for (unsigned childIdx = node->firstChild();
+                childIdx < node->firstChild() + node->numChildren();
+                childIdx++) {
+                if (!!m_graph.m_varArgChildren[childIdx])
+                    changed |= m_graph.m_varArgChildren[childIdx]->mergeFlags(NodeUsedAsValue);
+            }
+        } else {
+            if (!node->child1())
+                return changed;
+            changed |= node->child1()->mergeFlags(NodeUsedAsValue);
+            if (!node->child2())
+                return changed;
+            changed |= node->child2()->mergeFlags(NodeUsedAsValue);
+            if (!node->child3())
+                return changed;
+            changed |= node->child3()->mergeFlags(NodeUsedAsValue);
+        }
+        return changed;
+    }
+    
+    void propagate(Node* node)
+    {
+        NodeFlags flags = node->flags() & NodeBackPropMask;
+        
+        switch (node->op()) {
+        case GetLocal: {
+            VariableAccessData* variableAccessData = node->variableAccessData();
+            variableAccessData->mergeFlags(flags);
+            break;
+        }
+            
+        case SetLocal: {
+            VariableAccessData* variableAccessData = node->variableAccessData();
+            if (!variableAccessData->isLoadedFrom())
+                break;
+            node->child1()->mergeFlags(NodeUsedAsValue);
+            break;
+        }
+            
+        case BitAnd:
+        case BitOr:
+        case BitXor:
+        case BitRShift:
+        case BitLShift:
+        case BitURShift: {
+            flags |= NodeUsedAsInt;
+            flags &= ~(NodeUsedAsNumber | NodeNeedsNegZero | NodeUsedAsOther);
+            node->child1()->mergeFlags(flags);
+            node->child2()->mergeFlags(flags);
+            break;
+        }
+            
+        case ValueToInt32: {
+            flags |= NodeUsedAsInt;
+            flags &= ~(NodeUsedAsNumber | NodeNeedsNegZero | NodeUsedAsOther);
+            node->child1()->mergeFlags(flags);
+            break;
+        }
+            
+        case StringCharCodeAt: {
+            node->child1()->mergeFlags(NodeUsedAsValue);
+            node->child2()->mergeFlags(NodeUsedAsValue | NodeUsedAsInt);
+            break;
+        }
+            
+        case Identity: 
+        case UInt32ToNumber: {
+            node->child1()->mergeFlags(flags);
+            break;
+        }
+
+        case ValueAdd: {
+            if (isNotNegZero(node->child1().node()) || isNotNegZero(node->child2().node()))
+                flags &= ~NodeNeedsNegZero;
+            if (node->child1()->hasNumberResult() || node->child2()->hasNumberResult())
+                flags &= ~NodeUsedAsOther;
+            if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2()))
+                flags |= NodeUsedAsNumber;
+            if (!m_allowNestedOverflowingAdditions)
+                flags |= NodeUsedAsNumber;
+            
+            node->child1()->mergeFlags(flags);
+            node->child2()->mergeFlags(flags);
+            break;
+        }
+            
+        case ArithAdd: {
+            if (isNotNegZero(node->child1().node()) || isNotNegZero(node->child2().node()))
+                flags &= ~NodeNeedsNegZero;
+            if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2()))
+                flags |= NodeUsedAsNumber;
+            if (!m_allowNestedOverflowingAdditions)
+                flags |= NodeUsedAsNumber;
+            
+            node->child1()->mergeFlags(flags);
+            node->child2()->mergeFlags(flags);
+            break;
+        }
+            
+        case ArithSub: {
+            if (isNotZero(node->child1().node()) || isNotZero(node->child2().node()))
+                flags &= ~NodeNeedsNegZero;
+            if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2()))
+                flags |= NodeUsedAsNumber;
+            if (!m_allowNestedOverflowingAdditions)
+                flags |= NodeUsedAsNumber;
+            
+            node->child1()->mergeFlags(flags);
+            node->child2()->mergeFlags(flags);
+            break;
+        }
+            
+        case ArithNegate: {
+            flags &= ~NodeUsedAsOther;
+
+            node->child1()->mergeFlags(flags);
+            break;
+        }
+            
+        case ArithMul: {
+            // As soon as a multiply happens, we can easily end up in the part
+            // of the double domain where the point at which you do truncation
+            // can change the outcome. So, ArithMul always forces its inputs to
+            // check for overflow. Additionally, it will have to check for overflow
+            // itself unless we can prove that there is no way for the values
+            // produced to cause double rounding.
+            
+            if (!isWithinPowerOfTwo<22>(node->child1().node())
+                && !isWithinPowerOfTwo<22>(node->child2().node()))
+                flags |= NodeUsedAsNumber;
+            
+            node->mergeFlags(flags);
+            
+            flags |= NodeUsedAsNumber | NodeNeedsNegZero;
+            flags &= ~NodeUsedAsOther;
+
+            node->child1()->mergeFlags(flags);
+            node->child2()->mergeFlags(flags);
+            break;
+        }
+            
+        case ArithDiv: {
+            flags |= NodeUsedAsNumber | NodeNeedsNegZero;
+            flags &= ~NodeUsedAsOther;
+
+            node->child1()->mergeFlags(flags);
+            node->child2()->mergeFlags(flags);
+            break;
+        }
+            
+        case ArithMod: {
+            flags |= NodeUsedAsNumber | NodeNeedsNegZero;
+            flags &= ~NodeUsedAsOther;
+
+            node->child1()->mergeFlags(flags);
+            node->child2()->mergeFlags(flags);
+            break;
+        }
+            
+        case GetByVal: {
+            node->child1()->mergeFlags(NodeUsedAsValue);
+            node->child2()->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther | NodeUsedAsInt);
+            break;
+        }
+            
+        case GetMyArgumentByValSafe: {
+            node->child1()->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther | NodeUsedAsInt);
+            break;
+        }
+            
+        case NewArrayWithSize: {
+            node->child1()->mergeFlags(NodeUsedAsValue | NodeUsedAsInt);
+            break;
+        }
+            
+        case StringCharAt: {
+            node->child1()->mergeFlags(NodeUsedAsValue);
+            node->child2()->mergeFlags(NodeUsedAsValue | NodeUsedAsInt);
+            break;
+        }
+            
+        case StrCat: {
+            for (unsigned childIdx = node->firstChild();
+                childIdx < node->firstChild() + node->numChildren();
+                ++childIdx)
+                m_graph.m_varArgChildren[childIdx]->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther);
+            break;
+        }
+            
+        case ToPrimitive: {
+            node->child1()->mergeFlags(flags);
+            break;
+        }
+            
+        case PutByVal: {
+            m_graph.varArgChild(node, 0)->mergeFlags(NodeUsedAsValue);
+            m_graph.varArgChild(node, 1)->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther | NodeUsedAsInt);
+            m_graph.varArgChild(node, 2)->mergeFlags(NodeUsedAsValue);
+            break;
+        }
+            
+        default:
+            mergeDefaultFlags(node);
+            break;
+        }
+    }
+    
+    bool m_allowNestedOverflowingAdditions;
+};
+
+bool performBackwardsPropagation(Graph& graph)
+{
+    SamplingRegion samplingRegion("DFG Backwards Propagation Phase");
+    return runPhase<BackwardsPropagationPhase>(graph);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
diff --git a/Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.h b/Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.h
new file mode 100644 (file)
index 0000000..4386846
--- /dev/null
@@ -0,0 +1,49 @@
+/*
+ * Copyright (C) 2013 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 DFGBackwardsPropagationPhase_h
+#define DFGBackwardsPropagationPhase_h
+
+#include <wtf/Platform.h>
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGCommon.h"
+
+namespace JSC { namespace DFG {
+
+class Graph;
+
+// Infer basic information about how nodes are used by doing a block-local
+// backwards flow analysis.
+
+bool performBackwardsPropagation(Graph&);
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGBackwardsPropagationPhase_h
+
index 96ce188..a10fbe8 100644 (file)
@@ -47,6 +47,7 @@ public:
         if (m_graph.m_form == ThreadedCPS)
             return false;
         
+        clearIsLoadedFrom();
         freeUnnecessaryNodes();
         canonicalizeLocalsInBlocks();
         propagatePhis<LocalOperand>();
@@ -58,6 +59,12 @@ public:
 
 private:
     
+    void clearIsLoadedFrom()
+    {
+        for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i)
+            m_graph.m_variableAccessData[i].setIsLoadedFrom(false);
+    }
+    
     void freeUnnecessaryNodes()
     {
         SamplingRegion samplingRegion("DFG CPS Rethreading: freeUnnecessaryNodes");
@@ -170,12 +177,14 @@ private:
             ASSERT(otherNode->variableAccessData() == variable);
             
             if (otherNode->op() == SetArgument) {
+                variable->setIsLoadedFrom(true);
                 node->children.setChild1(Edge(otherNode));
                 m_block->variablesAtTail.atFor<operandKind>(idx) = node;
                 return;
             }
             
             if (variable->isCaptured()) {
+                variable->setIsLoadedFrom(true);
                 if (otherNode->op() == GetLocal)
                     otherNode = otherNode->child1().node();
                 else
@@ -200,6 +209,7 @@ private:
             return;
         }
         
+        variable->setIsLoadedFrom(true);
         Node* phi = addPhi<operandKind>(node->codeOrigin, variable, idx);
         node->children.setChild1(Edge(phi));
         m_block->variablesAtHead.atFor<operandKind>(idx) = phi;
@@ -256,6 +266,7 @@ private:
                 return;
             }
             
+            variable->setIsLoadedFrom(true);
             // There is nothing wrong with having redundant Flush's. It just needs to
             // be linked appropriately. Note that if there had already been a previous
             // use at tail then we don't override it. It's fine for variablesAtTail to
@@ -266,6 +277,7 @@ private:
             return;
         }
         
+        variable->setIsLoadedFrom(true);
         node->children.setChild1(Edge(addPhi<operandKind>(node->codeOrigin, variable, idx)));
         m_block->variablesAtHead.atFor<operandKind>(idx) = node;
         m_block->variablesAtTail.atFor<operandKind>(idx) = node;
index c92da40..7623412 100644 (file)
@@ -33,6 +33,7 @@
 #if ENABLE(DFG_JIT)
 
 #include "DFGArgumentsSimplificationPhase.h"
+#include "DFGBackwardsPropagationPhase.h"
 #include "DFGByteCodeParser.h"
 #include "DFGCFAPhase.h"
 #include "DFGCFGSimplificationPhase.h"
@@ -122,6 +123,7 @@ inline bool compile(CompileMode compileMode, ExecState* exec, CodeBlock* codeBlo
     if (validationEnabled())
         validate(dfg);
     
+    performBackwardsPropagation(dfg);
     performPredictionPropagation(dfg);
     performFixup(dfg);
     performStructureCheckHoisting(dfg);
index 7fbb526..aaf9f85 100644 (file)
@@ -179,8 +179,8 @@ void Graph::dump(PrintStream& out, const char* prefix, Node* node)
             out.print(comma, node->child3());
     }
 
-    if (strlen(nodeFlagsAsString(node->flags())))
-        out.print(comma, nodeFlagsAsString(node->flags()));
+    if (toCString(NodeFlagsDump(node->flags())) != "<empty>")
+        out.print(comma, NodeFlagsDump(node->flags()));
     if (node->hasArrayMode())
         out.print(comma, node->arrayMode());
     if (node->hasVarNumber())
index a605113..c5753d2 100644 (file)
 
 #if ENABLE(DFG_JIT)
 
-#include <wtf/BoundsCheckedPointer.h>
+#include <wtf/CommaPrinter.h>
 
 namespace JSC { namespace DFG {
 
-const char* nodeFlagsAsString(NodeFlags flags)
+void dumpNodeFlags(PrintStream& out, NodeFlags flags)
 {
-    if (!(flags ^ NodeDoesNotExit))
-        return "<empty>";
+    if (!(flags ^ NodeDoesNotExit)) {
+        out.print("<empty>");
+        return;
+    }
 
-    static const int size = 128;
-    static char description[size];
-    BoundsCheckedPointer<char> ptr(description, size);
-    
-    bool hasPrinted = false;
+    CommaPrinter comma("|");
     
     if (flags & NodeResultMask) {
         switch (flags & NodeResultMask) {
         case NodeResultJS:
-            ptr.strcat("JS");
+            out.print(comma, "JS");
             break;
         case NodeResultNumber:
-            ptr.strcat("Number");
+            out.print(comma, "Number");
             break;
         case NodeResultInt32:
-            ptr.strcat("Int32");
+            out.print(comma, "Int32");
             break;
         case NodeResultBoolean:
-            ptr.strcat("Boolean");
+            out.print(comma, "Boolean");
             break;
         case NodeResultStorage:
-            ptr.strcat("Storage");
+            out.print(comma, "Storage");
             break;
         default:
             RELEASE_ASSERT_NOT_REACHED();
             break;
         }
-        hasPrinted = true;
     }
     
-    if (flags & NodeMustGenerate) {
-        if (hasPrinted)
-            ptr.strcat("|");
-        ptr.strcat("MustGen");
-        hasPrinted = true;
-    }
+    if (flags & NodeMustGenerate)
+        out.print(comma, "MustGen");
     
-    if (flags & NodeHasVarArgs) {
-        if (hasPrinted)
-            ptr.strcat("|");
-        ptr.strcat("VarArgs");
-        hasPrinted = true;
-    }
+    if (flags & NodeHasVarArgs)
+        out.print(comma, "VarArgs");
     
-    if (flags & NodeClobbersWorld) {
-        if (hasPrinted)
-            ptr.strcat("|");
-        ptr.strcat("Clobbers");
-        hasPrinted = true;
-    }
+    if (flags & NodeClobbersWorld)
+        out.print(comma, "Clobbers");
     
-    if (flags & NodeMightClobber) {
-        if (hasPrinted)
-            ptr.strcat("|");
-        ptr.strcat("MightClobber");
-        hasPrinted = true;
-    }
+    if (flags & NodeMightClobber)
+        out.print(comma, "MightClobber");
     
     if (flags & NodeResultMask) {
-        if (!(flags & NodeUsedAsNumber) && !(flags & NodeNeedsNegZero)) {
-            if (hasPrinted)
-                ptr.strcat("|");
-            ptr.strcat("PureInt");
-            hasPrinted = true;
-        } else if (!(flags & NodeUsedAsNumber)) {
-            if (hasPrinted)
-                ptr.strcat("|");
-            ptr.strcat("PureInt(w/ neg zero)");
-            hasPrinted = true;
-        } else if (!(flags & NodeNeedsNegZero)) {
-            if (hasPrinted)
-                ptr.strcat("|");
-            ptr.strcat("PureNum");
-            hasPrinted = true;
-        }
-        if (flags & NodeUsedAsOther) {
-            if (hasPrinted)
-                ptr.strcat("|");
-            ptr.strcat("UseAsOther");
-            hasPrinted = true;
-        }
+        if (!(flags & NodeUsedAsNumber) && !(flags & NodeNeedsNegZero))
+            out.print(comma, "PureInt");
+        else if (!(flags & NodeUsedAsNumber))
+            out.print(comma, "PureInt(w/ neg zero)");
+        else if (!(flags & NodeNeedsNegZero))
+            out.print(comma, "PureNum");
+        if (flags & NodeUsedAsOther)
+            out.print(comma, "UseAsOther");
     }
     
-    if (flags & NodeMayOverflow) {
-        if (hasPrinted)
-            ptr.strcat("|");
-        ptr.strcat("MayOverflow");
-        hasPrinted = true;
-    }
-    
-    if (flags & NodeMayNegZero) {
-        if (hasPrinted)
-            ptr.strcat("|");
-        ptr.strcat("MayNegZero");
-        hasPrinted = true;
-    }
-    
-    if (flags & NodeUsedAsInt) {
-        if (hasPrinted)
-            ptr.strcat("|");
-        ptr.strcat("UseAsInt");
-        hasPrinted = true;
-    }
+    if (flags & NodeMayOverflow)
+        out.print(comma, "MayOverflow");
     
-    if (!(flags & NodeDoesNotExit)) {
-        if (hasPrinted)
-            ptr.strcat("|");
-        ptr.strcat("CanExit");
-        hasPrinted = true;
-    }
+    if (flags & NodeMayNegZero)
+        out.print(comma, "MayNegZero");
     
-    if (flags & NodeExitsForward) {
-        if (hasPrinted)
-            ptr.strcat("|");
-        ptr.strcat("NodeExitsForward");
-        hasPrinted = true;
-    }
+    if (flags & NodeUsedAsInt)
+        out.print(comma, "UseAsInt");
     
-    *ptr++ = 0;
+    if (!(flags & NodeDoesNotExit))
+        out.print(comma, "CanExit");
     
-    return description;
+    if (flags & NodeExitsForward)
+        out.print(comma, "NodeExitsForward");
 }
 
-
 } } // namespace JSC::DFG
 
 #endif // ENABLE(DFG_JIT)
index b352d16..926f371 100644 (file)
@@ -30,6 +30,7 @@
 
 #if ENABLE(DFG_JIT)
 
+#include <wtf/PrintStream.h>
 #include <wtf/StdLibExtras.h>
 
 namespace JSC { namespace DFG {
@@ -59,15 +60,14 @@ namespace JSC { namespace DFG {
 #define NodeUsedAsOther          0x0800 // The result of this computation may be used in a context that distinguishes between NaN and other things (like undefined).
 #define NodeUsedAsValue          (NodeUsedAsNumber | NodeNeedsNegZero | NodeUsedAsOther)
 #define NodeUsedAsInt            0x1000 // The result of this computation is known to be used in a context that prefers, but does not require, integer values.
-#define NodeUsedAsIntLocally     0x2000 // Same as NodeUsedAsInt, but within the same basic block.
 
 #define NodeArithFlagsMask       (NodeBehaviorMask | NodeBackPropMask)
 
-#define NodeDoesNotExit          0x4000 // This flag is negated to make it natural for the default to be that a node does exit.
+#define NodeDoesNotExit          0x2000 // This flag is negated to make it natural for the default to be that a node does exit.
 
-#define NodeRelevantToOSR        0x8000
+#define NodeRelevantToOSR        0x4000
 
-#define NodeExitsForward        0x10000
+#define NodeExitsForward         0x8000
 
 typedef uint32_t NodeFlags;
 
@@ -102,7 +102,8 @@ static inline bool nodeCanSpeculateInteger(NodeFlags flags)
     return true;
 }
 
-const char* nodeFlagsAsString(NodeFlags);
+void dumpNodeFlags(PrintStream&, NodeFlags);
+MAKE_PRINT_ADAPTOR(NodeFlagsDump, NodeFlags, dumpNodeFlags);
 
 } } // namespace JSC::DFG
 
index e5b5925..c041361 100644 (file)
@@ -106,65 +106,6 @@ private:
         return m_currentNode->predict(prediction);
     }
     
-    bool isNotNegZero(Node* node)
-    {
-        if (!m_graph.isNumberConstant(node))
-            return false;
-        double value = m_graph.valueOfNumberConstant(node);
-        return !value && 1.0 / value < 0.0;
-    }
-    
-    bool isNotZero(Node* node)
-    {
-        if (!m_graph.isNumberConstant(node))
-            return false;
-        return !!m_graph.valueOfNumberConstant(node);
-    }
-    
-    bool isWithinPowerOfTwoForConstant(Node* node, int power)
-    {
-        JSValue immediateValue = node->valueOfJSConstant(codeBlock());
-        if (!immediateValue.isInt32())
-            return false;
-        int32_t intImmediate = immediateValue.asInt32();
-        return intImmediate > -(1 << power) && intImmediate < (1 << power);
-    }
-    
-    bool isWithinPowerOfTwoNonRecursive(Node* node, int power)
-    {
-        if (node->op() != JSConstant)
-            return false;
-        return isWithinPowerOfTwoForConstant(node, power);
-    }
-    
-    bool isWithinPowerOfTwo(Node* node, int power)
-    {
-        switch (node->op()) {
-        case JSConstant: {
-            return isWithinPowerOfTwoForConstant(node, power);
-        }
-            
-        case BitAnd: {
-            return isWithinPowerOfTwoNonRecursive(node->child1().node(), power)
-                || isWithinPowerOfTwoNonRecursive(node->child2().node(), power);
-        }
-            
-        case BitRShift:
-        case BitURShift: {
-            Node* shiftAmount = node->child2().node();
-            if (shiftAmount->op() != JSConstant)
-                return false;
-            JSValue immediateValue = shiftAmount->valueOfJSConstant(codeBlock());
-            if (!immediateValue.isInt32())
-                return false;
-            return immediateValue > 32 - power;
-        }
-            
-        default:
-            return false;
-        }
-    }
-
     SpeculatedType speculatedDoubleTypeForPrediction(SpeculatedType value)
     {
         if (!isNumberSpeculation(value))
@@ -182,10 +123,9 @@ private:
     void propagate(Node* node)
     {
         NodeType op = node->op();
-        NodeFlags flags = node->flags() & NodeBackPropMask;
 
 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
-        dataLog("   ", Graph::opName(op), " ", m_currentNode, ": ", nodeFlagsAsString(flags), " ");
+        dataLog("   ", Graph::opName(op), " ", m_currentNode, ": ", NodeFlagsDump(node->flags()), " ");
 #endif
         
         bool changed = false;
@@ -202,29 +142,12 @@ private:
             SpeculatedType prediction = variableAccessData->prediction();
             if (prediction)
                 changed |= mergePrediction(prediction);
-            
-            // Assume conservatively that a SetLocal implies that the value may flow through a loop,
-            // and so we would have overflow leading to the program "observing" numbers even if all
-            // users of the value are doing toInt32. It might be worthwhile to revisit this at some
-            // point and actually check if the data flow involves loops, but right now I don't think
-            // we have evidence that this would be beneficial for benchmarks.
-            
-            changed |= variableAccessData->mergeFlags((flags & ~NodeUsedAsIntLocally) | NodeUsedAsNumber);
             break;
         }
             
         case SetLocal: {
             VariableAccessData* variableAccessData = node->variableAccessData();
             changed |= variableAccessData->predict(node->child1()->prediction());
-
-            changed |= node->child1()->mergeFlags(variableAccessData->flags());
-            break;
-        }
-            
-        case Flush: {
-            // Make sure that the analysis knows that flushed locals escape.
-            VariableAccessData* variableAccessData = node->variableAccessData();
-            changed |= variableAccessData->mergeFlags(NodeUsedAsValue);
             break;
         }
             
@@ -235,45 +158,36 @@ private:
         case BitLShift:
         case BitURShift: {
             changed |= setPrediction(SpecInt32);
-            flags |= NodeUsedAsInt | NodeUsedAsIntLocally;
-            flags &= ~(NodeUsedAsNumber | NodeNeedsNegZero | NodeUsedAsOther);
-            changed |= node->child1()->mergeFlags(flags);
-            changed |= node->child2()->mergeFlags(flags);
             break;
         }
             
         case ValueToInt32: {
             changed |= setPrediction(SpecInt32);
-            flags |= NodeUsedAsInt | NodeUsedAsIntLocally;
-            flags &= ~(NodeUsedAsNumber | NodeNeedsNegZero | NodeUsedAsOther);
-            changed |= node->child1()->mergeFlags(flags);
             break;
         }
             
-        case ArrayPop: {
-            changed |= mergePrediction(node->getHeapPrediction());
-            changed |= mergeDefaultFlags(node);
-            break;
-        }
-
-        case ArrayPush: {
-            changed |= mergePrediction(node->getHeapPrediction());
-            changed |= node->child1()->mergeFlags(NodeUsedAsValue);
-            changed |= node->child2()->mergeFlags(NodeUsedAsValue);
-            break;
-        }
-
+        case ArrayPop:
+        case ArrayPush:
         case RegExpExec:
-        case RegExpTest: {
-            changed |= mergePrediction(node->getHeapPrediction());
-            changed |= mergeDefaultFlags(node);
+        case RegExpTest:
+        case GetById:
+        case GetByIdFlush:
+        case GetMyArgumentByValSafe:
+        case GetByOffset:
+        case Call:
+        case Construct:
+        case GetGlobalVar:
+        case GetScopedVar:
+        case Resolve:
+        case ResolveBase:
+        case ResolveBaseStrictPut:
+        case ResolveGlobal: {
+            changed |= setPrediction(node->getHeapPrediction());
             break;
         }
 
         case StringCharCodeAt: {
-            changed |= mergePrediction(SpecInt32);
-            changed |= node->child1()->mergeFlags(NodeUsedAsValue);
-            changed |= node->child2()->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther | NodeUsedAsInt | NodeUsedAsIntLocally);
+            changed |= setPrediction(SpecInt32);
             break;
         }
 
@@ -282,8 +196,6 @@ private:
                 changed |= mergePrediction(SpecInt32);
             else
                 changed |= mergePrediction(SpecNumber);
-            
-            changed |= node->child1()->mergeFlags(flags);
             break;
         }
 
@@ -291,11 +203,9 @@ private:
             SpeculatedType left = node->child1()->prediction();
             SpeculatedType right = node->child2()->prediction();
             
-            AddSpeculationMode mode = DontSpeculateInteger;
-            
             if (left && right) {
                 if (isNumberSpeculationExpectingDefined(left) && isNumberSpeculationExpectingDefined(right)) {
-                    if ((mode = m_graph.addSpeculationMode(node)) != DontSpeculateInteger)
+                    if (m_graph.addSpeculationMode(node) != DontSpeculateInteger)
                         changed |= mergePrediction(SpecInt32);
                     else
                         changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
@@ -305,17 +215,6 @@ private:
                 } else
                     changed |= mergePrediction(SpecString | SpecInt32 | SpecDouble);
             }
-            
-            if (isNotNegZero(node->child1().node()) || isNotNegZero(node->child2().node()))
-                flags &= ~NodeNeedsNegZero;
-            if (node->child1()->hasNumberResult() || node->child2()->hasNumberResult())
-                flags &= ~NodeUsedAsOther;
-            
-            if (mode != SpeculateInteger)
-                flags |= NodeUsedAsNumber;
-            
-            changed |= node->child1()->mergeFlags(flags);
-            changed |= node->child2()->mergeFlags(flags);
             break;
         }
             
@@ -323,24 +222,12 @@ private:
             SpeculatedType left = node->child1()->prediction();
             SpeculatedType right = node->child2()->prediction();
             
-            AddSpeculationMode mode = DontSpeculateInteger;
-            
             if (left && right) {
-                if ((mode = m_graph.addSpeculationMode(node)) != DontSpeculateInteger)
+                if (m_graph.addSpeculationMode(node) != DontSpeculateInteger)
                     changed |= mergePrediction(SpecInt32);
                 else
                     changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
             }
-            
-            if (isNotNegZero(node->child1().node()) || isNotNegZero(node->child2().node()))
-                flags &= ~NodeNeedsNegZero;
-            flags &= ~NodeUsedAsOther;
-            
-            if (mode != SpeculateInteger)
-                flags |= NodeUsedAsNumber;
-            
-            changed |= node->child1()->mergeFlags(flags);
-            changed |= node->child2()->mergeFlags(flags);
             break;
         }
             
@@ -348,24 +235,12 @@ private:
             SpeculatedType left = node->child1()->prediction();
             SpeculatedType right = node->child2()->prediction();
             
-            AddSpeculationMode mode = DontSpeculateInteger;
-            
             if (left && right) {
-                if ((mode = m_graph.addSpeculationMode(node)) != DontSpeculateInteger)
+                if (m_graph.addSpeculationMode(node) != DontSpeculateInteger)
                     changed |= mergePrediction(SpecInt32);
                 else
                     changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
             }
-
-            if (isNotZero(node->child1().node()) || isNotZero(node->child2().node()))
-                flags &= ~NodeNeedsNegZero;
-            flags &= ~NodeUsedAsOther;
-            
-            if (mode != SpeculateInteger)
-                flags |= NodeUsedAsNumber;
-            
-            changed |= node->child1()->mergeFlags(flags);
-            changed |= node->child2()->mergeFlags(flags);
             break;
         }
             
@@ -376,10 +251,6 @@ private:
                 else
                     changed |= mergePrediction(speculatedDoubleTypeForPrediction(node->child1()->prediction()));
             }
-
-            flags &= ~NodeUsedAsOther;
-
-            changed |= node->child1()->mergeFlags(flags);
             break;
             
         case ArithMin:
@@ -394,12 +265,6 @@ private:
                 else
                     changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
             }
-
-            flags |= NodeUsedAsNumber;
-            flags &= ~NodeUsedAsOther;
-
-            changed |= node->child1()->mergeFlags(flags);
-            changed |= node->child2()->mergeFlags(flags);
             break;
         }
 
@@ -413,25 +278,6 @@ private:
                 else
                     changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
             }
-
-            // As soon as a multiply happens, we can easily end up in the part
-            // of the double domain where the point at which you do truncation
-            // can change the outcome. So, ArithMul always forces its inputs to
-            // check for overflow. Additionally, it will have to check for overflow
-            // itself unless we can prove that there is no way for the values
-            // produced to cause double rounding.
-            
-            if (!isWithinPowerOfTwo(node->child1().node(), 22)
-                && !isWithinPowerOfTwo(node->child2().node(), 22))
-                flags |= NodeUsedAsNumber;
-            
-            changed |= node->mergeFlags(flags);
-            
-            flags |= NodeUsedAsNumber | NodeNeedsNegZero;
-            flags &= ~NodeUsedAsOther;
-
-            changed |= node->child1()->mergeFlags(flags);
-            changed |= node->child2()->mergeFlags(flags);
             break;
         }
             
@@ -446,17 +292,6 @@ private:
                 else
                     changed |= mergePrediction(SpecDouble);
             }
-
-            // As soon as a multiply happens, we can easily end up in the part
-            // of the double domain where the point at which you do truncation
-            // can change the outcome. So, ArithDiv always checks for overflow
-            // no matter what, and always forces its inputs to check as well.
-            
-            flags |= NodeUsedAsNumber | NodeNeedsNegZero;
-            flags &= ~NodeUsedAsOther;
-
-            changed |= node->child1()->mergeFlags(flags);
-            changed |= node->child2()->mergeFlags(flags);
             break;
         }
             
@@ -471,20 +306,11 @@ private:
                 else
                     changed |= mergePrediction(SpecDouble);
             }
-            
-            flags |= NodeUsedAsNumber | NodeNeedsNegZero;
-            flags &= ~NodeUsedAsOther;
-
-            changed |= node->child1()->mergeFlags(flags);
-            changed |= node->child2()->mergeFlags(flags);
             break;
         }
             
         case ArithSqrt: {
             changed |= setPrediction(SpecDouble);
-            flags |= NodeUsedAsNumber | NodeNeedsNegZero;
-            flags &= ~NodeUsedAsOther;
-            changed |= node->child1()->mergeFlags(flags);
             break;
         }
             
@@ -495,8 +321,6 @@ private:
                 changed |= mergePrediction(SpecInt32);
             else
                 changed |= mergePrediction(speculatedDoubleTypeForPrediction(child));
-
-            changed |= node->child1()->mergeFlags(flags);
             break;
         }
             
@@ -517,42 +341,20 @@ private:
         case IsObject:
         case IsFunction: {
             changed |= setPrediction(SpecBoolean);
-            changed |= mergeDefaultFlags(node);
             break;
         }
 
         case TypeOf: {
             changed |= setPrediction(SpecString);
-            changed |= mergeDefaultFlags(node);
             break;
         }
 
-        case GetById: {
-            changed |= mergePrediction(node->getHeapPrediction());
-            changed |= mergeDefaultFlags(node);
-            break;
-        }
-            
-        case GetByIdFlush:
-            changed |= mergePrediction(node->getHeapPrediction());
-            changed |= mergeDefaultFlags(node);
-            break;
-            
         case GetByVal: {
             if (node->child1()->shouldSpeculateFloat32Array()
                 || node->child1()->shouldSpeculateFloat64Array())
                 changed |= mergePrediction(SpecDouble);
             else
                 changed |= mergePrediction(node->getHeapPrediction());
-
-            changed |= node->child1()->mergeFlags(NodeUsedAsValue);
-            changed |= node->child2()->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther | NodeUsedAsInt | NodeUsedAsIntLocally);
-            break;
-        }
-            
-        case GetMyArgumentByValSafe: {
-            changed |= mergePrediction(node->getHeapPrediction());
-            changed |= node->child1()->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther | NodeUsedAsInt | NodeUsedAsIntLocally);
             break;
         }
             
@@ -567,26 +369,9 @@ private:
         case AllocatePropertyStorage:
         case ReallocatePropertyStorage: {
             changed |= setPrediction(SpecOther);
-            changed |= mergeDefaultFlags(node);
             break;
         }
 
-        case GetByOffset: {
-            changed |= mergePrediction(node->getHeapPrediction());
-            changed |= mergeDefaultFlags(node);
-            break;
-        }
-            
-        case Call:
-        case Construct: {
-            changed |= mergePrediction(node->getHeapPrediction());
-            for (unsigned childIdx = node->firstChild();
-                childIdx < node->firstChild() + node->numChildren();
-                ++childIdx)
-                changed |= m_graph.m_varArgChildren[childIdx]->mergeFlags(NodeUsedAsValue);
-            break;
-        }
-            
         case ConvertThis: {
             SpeculatedType prediction = node->child1()->prediction();
             if (prediction) {
@@ -596,28 +381,6 @@ private:
                 }
                 changed |= mergePrediction(prediction);
             }
-            changed |= mergeDefaultFlags(node);
-            break;
-        }
-            
-        case GetGlobalVar: {
-            changed |= mergePrediction(node->getHeapPrediction());
-            break;
-        }
-            
-        case PutGlobalVar:
-        case PutGlobalVarCheck: {
-            changed |= node->child1()->mergeFlags(NodeUsedAsValue);
-            break;
-        }
-            
-        case GetScopedVar:
-        case Resolve:
-        case ResolveBase:
-        case ResolveBaseStrictPut:
-        case ResolveGlobal: {
-            SpeculatedType prediction = node->getHeapPrediction();
-            changed |= mergePrediction(prediction);
             break;
         }
             
@@ -636,48 +399,25 @@ private:
         case CreateThis:
         case NewObject: {
             changed |= setPrediction(SpecFinalObject);
-            changed |= mergeDefaultFlags(node);
-            break;
-        }
-            
-        case NewArray: {
-            changed |= setPrediction(SpecArray);
-            for (unsigned childIdx = node->firstChild();
-                childIdx < node->firstChild() + node->numChildren();
-                ++childIdx)
-                changed |= m_graph.m_varArgChildren[childIdx]->mergeFlags(NodeUsedAsValue);
-            break;
-        }
-            
-        case NewArrayWithSize: {
-            changed |= setPrediction(SpecArray);
-            changed |= node->child1()->mergeFlags(NodeUsedAsValue | NodeUsedAsInt | NodeUsedAsIntLocally);
             break;
         }
             
+        case NewArray:
+        case NewArrayWithSize:
         case NewArrayBuffer: {
             changed |= setPrediction(SpecArray);
             break;
         }
             
-        case NewRegexp: {
+        case NewRegexp:
+        case CreateActivation: {
             changed |= setPrediction(SpecObjectOther);
             break;
         }
         
-        case StringCharAt: {
-            changed |= setPrediction(SpecString);
-            changed |= node->child1()->mergeFlags(NodeUsedAsValue);
-            changed |= node->child2()->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther | NodeUsedAsInt | NodeUsedAsIntLocally);
-            break;
-        }
-            
+        case StringCharAt:
         case StrCat: {
             changed |= setPrediction(SpecString);
-            for (unsigned childIdx = node->firstChild();
-                childIdx < node->firstChild() + node->numChildren();
-                ++childIdx)
-                changed |= m_graph.m_varArgChildren[childIdx]->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther);
             break;
         }
             
@@ -699,12 +439,6 @@ private:
                 } else
                     changed |= mergePrediction(child);
             }
-            changed |= node->child1()->mergeFlags(flags);
-            break;
-        }
-            
-        case CreateActivation: {
-            changed |= setPrediction(SpecObjectOther);
             break;
         }
             
@@ -743,51 +477,27 @@ private:
             break;
         }
         
-        case PutByVal:
-            changed |= m_graph.varArgChild(node, 0)->mergeFlags(NodeUsedAsValue);
-            changed |= m_graph.varArgChild(node, 1)->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther | NodeUsedAsInt | NodeUsedAsIntLocally);
-            changed |= m_graph.varArgChild(node, 2)->mergeFlags(NodeUsedAsValue);
-            break;
-
-        case PutScopedVar:
-            changed |= node->child1()->mergeFlags(NodeUsedAsValue);
-            changed |= node->child3()->mergeFlags(NodeUsedAsValue);
-            break;
-            
-        case Return:
-        case Throw:
-            changed |= node->child1()->mergeFlags(NodeUsedAsValue);
-            break;
-
-        case PutById:
-        case PutByIdDirect:
-            changed |= node->child1()->mergeFlags(NodeUsedAsValue);
-            changed |= node->child2()->mergeFlags(NodeUsedAsValue);
-            break;
-
-        case PutByOffset:
-            changed |= node->child1()->mergeFlags(NodeUsedAsValue);
-            changed |= node->child3()->mergeFlags(NodeUsedAsValue);
-            break;
-            
         case Phi:
             // Phis should not be visible here since we're iterating the all-but-Phi's
             // part of basic blocks.
             CRASH();
             break;
 
-        case SetCallee:
-        case SetMyScope:
-            changed |= node->child1()->mergeFlags(NodeUsedAsValue);
-            break;
-            
         case GetScope:
-            changed |= node->child1()->mergeFlags(NodeUsedAsValue);
             changed |= setPrediction(SpecCellOther);
             break;
 
 #ifndef NDEBUG
         // These get ignored because they don't return anything.
+        case PutByVal:
+        case PutScopedVar:
+        case Return:
+        case Throw:
+        case PutById:
+        case PutByIdDirect:
+        case PutByOffset:
+        case SetCallee:
+        case SetMyScope:
         case DFG::Jump:
         case Branch:
         case Breakpoint:
@@ -809,7 +519,8 @@ private:
         case GarbageValue:
         case AllocationProfileWatchpoint:
         case Phantom:
-            changed |= mergeDefaultFlags(node);
+        case PutGlobalVar:
+        case PutGlobalVarCheck:
             break;
             
         // These gets ignored because it doesn't do anything.
@@ -817,6 +528,7 @@ private:
         case Nop:
         case CountExecution:
         case PhantomLocal:
+        case Flush:
             break;
             
         case LastNodeType:
@@ -824,7 +536,6 @@ private:
             break;
 #else
         default:
-            changed |= mergeDefaultFlags(node);
             break;
 #endif
         }
@@ -836,30 +547,6 @@ private:
         m_changed |= changed;
     }
         
-    bool mergeDefaultFlags(Node* node)
-    {
-        bool changed = false;
-        if (node->flags() & NodeHasVarArgs) {
-            for (unsigned childIdx = node->firstChild();
-                childIdx < node->firstChild() + node->numChildren();
-                childIdx++) {
-                if (!!m_graph.m_varArgChildren[childIdx])
-                    changed |= m_graph.m_varArgChildren[childIdx]->mergeFlags(NodeUsedAsValue);
-            }
-        } else {
-            if (!node->child1())
-                return changed;
-            changed |= node->child1()->mergeFlags(NodeUsedAsValue);
-            if (!node->child2())
-                return changed;
-            changed |= node->child2()->mergeFlags(NodeUsedAsValue);
-            if (!node->child3())
-                return changed;
-            changed |= node->child3()->mergeFlags(NodeUsedAsValue);
-        }
-        return changed;
-    }
-    
     void propagateForward()
     {
 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
index f906a23..9109f09 100644 (file)
@@ -73,6 +73,7 @@ public:
             data->find()->mergeIsCaptured(data->isCaptured());
             data->find()->mergeStructureCheckHoistingFailed(data->structureCheckHoistingFailed());
             data->find()->mergeShouldNeverUnbox(data->shouldNeverUnbox());
+            data->find()->mergeIsLoadedFrom(data->isLoadedFrom());
         }
         
         m_graph.m_unificationState = GloballyUnified;
index c836c1e..feb0247 100644 (file)
@@ -51,6 +51,7 @@ public:
         , m_isArgumentsAlias(false)
         , m_structureCheckHoistingFailed(false)
         , m_isProfitableToUnbox(false)
+        , m_isLoadedFrom(false)
         , m_doubleFormatState(EmptyDoubleFormatState)
     {
         clearVotes();
@@ -149,6 +150,21 @@ public:
         return m_isArgumentsAlias;
     }
     
+    bool mergeIsLoadedFrom(bool isLoadedFrom)
+    {
+        return checkAndSet(m_isLoadedFrom, m_isLoadedFrom | isLoadedFrom);
+    }
+    
+    void setIsLoadedFrom(bool isLoadedFrom)
+    {
+        m_isLoadedFrom = isLoadedFrom;
+    }
+    
+    bool isLoadedFrom()
+    {
+        return m_isLoadedFrom;
+    }
+    
     bool predict(SpeculatedType prediction)
     {
         VariableAccessData* self = find();
@@ -306,6 +322,7 @@ private:
     bool m_isArgumentsAlias;
     bool m_structureCheckHoistingFailed;
     bool m_isProfitableToUnbox;
+    bool m_isLoadedFrom;
 
     float m_votes[2]; // Used primarily for double voting but may be reused for other purposes.
     DoubleFormatState m_doubleFormatState;