DFG::LICMPhase shouldn't hoist type checks unless it knows that the check will succee...
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 19 May 2016 21:25:29 +0000 (21:25 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 19 May 2016 21:25:29 +0000 (21:25 +0000)
https://bugs.webkit.org/show_bug.cgi?id=144527

Reviewed by Saam Barati.

Source/JavaScriptCore:

This adds a control flow equivalence analysis (called ControlEquivalenceAnalysis) based on
dominator analysis over the backwards CFG. Two basic blocks are control flow equivalent if
the execution of one implies that the other one must also execute. It means that the two
blocks' forward and backward dominance are reciprocated: (A dom B and B backdom A) or (B dom
A and A backdom B). LICM now uses it to become more conservative about hoisting checks, if
this has caused problems in the past. If we hoist something that may exit from a block that
was not control equivalent to the pre-header then it's possible that the node's speculation
will fail even though it wouldn't have if it wasn't hoisted. So, we flag these nodes'
origins as being "wasHoisted" and we track all of their exits as "HoistingFailed". LICM will
turn off such speculative hoisting if the CodeBlock from which we are hoisting had the
HoistingFailed exit kind.

Note that this deliberately still allows us to hoist things that may exit even if they are
not control equivalent to the pre-header. This is necessary because the profitability of
hoisting is so huge in all of the cases that we're aware of that it's worth giving it a
shot.

This is neutral on macrobenchmarks since none of the benchmarks we track have a hoistable
operation that would exit only if hoisted. I added microbenchmarks to illustrate the problem
and two of them speed up by ~40% while one of them is neutral (Int52 saves us from having
problems on that program even though LICM previously did the wrong thing).

* JavaScriptCore.xcodeproj/project.pbxproj:
* bytecode/ExitKind.cpp:
(JSC::exitKindToString):
* bytecode/ExitKind.h:
* dfg/DFGAtTailAbstractState.h:
(JSC::DFG::AtTailAbstractState::operator bool):
(JSC::DFG::AtTailAbstractState::initializeTo):
* dfg/DFGBackwardsCFG.h: Added.
(JSC::DFG::BackwardsCFG::BackwardsCFG):
* dfg/DFGBackwardsDominators.h: Added.
(JSC::DFG::BackwardsDominators::BackwardsDominators):
* dfg/DFGCommon.h:
(JSC::DFG::checkAndSet): Deleted.
* dfg/DFGControlEquivalenceAnalysis.h: Added.
(JSC::DFG::ControlEquivalenceAnalysis::ControlEquivalenceAnalysis):
(JSC::DFG::ControlEquivalenceAnalysis::dominatesEquivalently):
(JSC::DFG::ControlEquivalenceAnalysis::areEquivalent):
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::dump):
(JSC::DFG::Graph::dumpBlockHeader):
(JSC::DFG::Graph::invalidateCFG):
(JSC::DFG::Graph::substituteGetLocal):
(JSC::DFG::Graph::handleAssertionFailure):
(JSC::DFG::Graph::ensureDominators):
(JSC::DFG::Graph::ensurePrePostNumbering):
(JSC::DFG::Graph::ensureNaturalLoops):
(JSC::DFG::Graph::ensureBackwardsCFG):
(JSC::DFG::Graph::ensureBackwardsDominators):
(JSC::DFG::Graph::ensureControlEquivalenceAnalysis):
(JSC::DFG::Graph::methodOfGettingAValueProfileFor):
* dfg/DFGGraph.h:
(JSC::DFG::Graph::hasDebuggerEnabled):
* dfg/DFGInPlaceAbstractState.h:
(JSC::DFG::InPlaceAbstractState::operator bool):
(JSC::DFG::InPlaceAbstractState::createValueForNode):
(JSC::DFG::InPlaceAbstractState::forNode):
* dfg/DFGLICMPhase.cpp:
(JSC::DFG::LICMPhase::run):
(JSC::DFG::LICMPhase::attemptHoist):
* dfg/DFGMayExit.cpp:
(JSC::DFG::mayExit):
* dfg/DFGMayExit.h:
* dfg/DFGNode.h:
* dfg/DFGNodeOrigin.cpp:
(JSC::DFG::NodeOrigin::dump):
* dfg/DFGNodeOrigin.h:
(JSC::DFG::NodeOrigin::takeValidExit):
(JSC::DFG::NodeOrigin::withWasHoisted):
(JSC::DFG::NodeOrigin::forInsertingAfter):
* dfg/DFGNullAbstractState.h: Added.
(JSC::DFG::NullAbstractState::NullAbstractState):
(JSC::DFG::NullAbstractState::operator bool):
(JSC::DFG::NullAbstractState::forNode):
* dfg/DFGOSRExit.cpp:
(JSC::DFG::OSRExit::OSRExit):
* dfg/DFGOSRExitBase.cpp:
(JSC::DFG::OSRExitBase::considerAddingAsFrequentExitSiteSlow):
* dfg/DFGOSRExitBase.h:
(JSC::DFG::OSRExitBase::OSRExitBase):
* dfg/DFGTypeCheckHoistingPhase.cpp:
(JSC::DFG::TypeCheckHoistingPhase::run):
* ftl/FTLOSRExit.cpp:
(JSC::FTL::OSRExitDescriptor::prepareOSRExitHandle):
(JSC::FTL::OSRExit::OSRExit):
* ftl/FTLOSRExit.h:

Source/WTF:

This adds an adaptor for graphs called BackwardsGraph. The WTF graph framework is based on
passing around a Graph template argument that follows the protocol shared by DFG::CFG,
B3::CFG, and Air::CFG. These graphs always have a single root node but may have many leaf
nodes. This new BackwardsGraph adaptor reverses the graph by creating a synthetic return
node that it uses as the root in the inverted graph. This currently may resort to some
heuristics in programs that have an infinite loop, but other than that, it'll work well in
the general case.

This allows us to say Dominators<BackwardsGraph<some graph type>> as a way of computing
backwards dominators, which then allows us to easily answer control flow equivalence
queries.

* CMakeLists.txt:
* WTF.xcodeproj/project.pbxproj:
* wtf/BackwardsGraph.h: Added.
(WTF::BackwardsGraph::Node::Node):
(WTF::BackwardsGraph::Node::root):
(WTF::BackwardsGraph::Node::operator==):
(WTF::BackwardsGraph::Node::operator!=):
(WTF::BackwardsGraph::Node::operator bool):
(WTF::BackwardsGraph::Node::isRoot):
(WTF::BackwardsGraph::Node::node):
(WTF::BackwardsGraph::Set::Set):
(WTF::BackwardsGraph::Set::add):
(WTF::BackwardsGraph::Set::remove):
(WTF::BackwardsGraph::Set::contains):
(WTF::BackwardsGraph::Set::dump):
(WTF::BackwardsGraph::Map::Map):
(WTF::BackwardsGraph::Map::clear):
(WTF::BackwardsGraph::Map::size):
(WTF::BackwardsGraph::Map::operator[]):
(WTF::BackwardsGraph::BackwardsGraph):
(WTF::BackwardsGraph::root):
(WTF::BackwardsGraph::newMap):
(WTF::BackwardsGraph::successors):
(WTF::BackwardsGraph::predecessors):
(WTF::BackwardsGraph::index):
(WTF::BackwardsGraph::node):
(WTF::BackwardsGraph::numNodes):
(WTF::BackwardsGraph::dump):
* wtf/Dominators.h:
(WTF::Dominators::Dominators):
(WTF::Dominators::dump):
(WTF::Dominators::LengauerTarjan::computeDepthFirstPreNumbering):
* wtf/GraphNodeWorklist.h:
(WTF::GraphNodeWith::GraphNodeWith):
(WTF::GraphNodeWith::operator bool):
* wtf/StdLibExtras.h:
(WTF::callStatelessLambda):
(WTF::checkAndSet):

LayoutTests:

Add tests for LICM hoisting things that would only exit if hoisted.

* js/regress/licm-dragons-expected.txt: Added.
* js/regress/licm-dragons-out-of-bounds-expected.txt: Added.
* js/regress/licm-dragons-out-of-bounds.html: Added.
* js/regress/licm-dragons-overflow-expected.txt: Added.
* js/regress/licm-dragons-overflow.html: Added.
* js/regress/licm-dragons.html: Added.
* js/regress/script-tests/licm-dragons-out-of-bounds.js: Added.
(foo):
* js/regress/script-tests/licm-dragons-overflow.js: Added.
(foo):
* js/regress/script-tests/licm-dragons.js: Added.
(foo):

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

42 files changed:
LayoutTests/ChangeLog
LayoutTests/js/regress/licm-dragons-expected.txt [new file with mode: 0644]
LayoutTests/js/regress/licm-dragons-out-of-bounds-expected.txt [new file with mode: 0644]
LayoutTests/js/regress/licm-dragons-out-of-bounds.html [new file with mode: 0644]
LayoutTests/js/regress/licm-dragons-overflow-expected.txt [new file with mode: 0644]
LayoutTests/js/regress/licm-dragons-overflow.html [new file with mode: 0644]
LayoutTests/js/regress/licm-dragons.html [new file with mode: 0644]
LayoutTests/js/regress/script-tests/licm-dragons-out-of-bounds.js [new file with mode: 0644]
LayoutTests/js/regress/script-tests/licm-dragons-overflow.js [new file with mode: 0644]
LayoutTests/js/regress/script-tests/licm-dragons.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/bytecode/ExitKind.cpp
Source/JavaScriptCore/bytecode/ExitKind.h
Source/JavaScriptCore/dfg/DFGAtTailAbstractState.h
Source/JavaScriptCore/dfg/DFGBackwardsCFG.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGBackwardsDominators.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGCommon.h
Source/JavaScriptCore/dfg/DFGControlEquivalenceAnalysis.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGGraph.cpp
Source/JavaScriptCore/dfg/DFGGraph.h
Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h
Source/JavaScriptCore/dfg/DFGLICMPhase.cpp
Source/JavaScriptCore/dfg/DFGMayExit.cpp
Source/JavaScriptCore/dfg/DFGMayExit.h
Source/JavaScriptCore/dfg/DFGNode.h
Source/JavaScriptCore/dfg/DFGNodeOrigin.cpp
Source/JavaScriptCore/dfg/DFGNodeOrigin.h
Source/JavaScriptCore/dfg/DFGNullAbstractState.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGOSRExit.cpp
Source/JavaScriptCore/dfg/DFGOSRExitBase.cpp
Source/JavaScriptCore/dfg/DFGOSRExitBase.h
Source/JavaScriptCore/dfg/DFGTypeCheckHoistingPhase.cpp
Source/JavaScriptCore/ftl/FTLOSRExit.cpp
Source/JavaScriptCore/ftl/FTLOSRExit.h
Source/WTF/ChangeLog
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/BackwardsGraph.h [new file with mode: 0644]
Source/WTF/wtf/CMakeLists.txt
Source/WTF/wtf/Dominators.h
Source/WTF/wtf/GraphNodeWorklist.h
Source/WTF/wtf/StdLibExtras.h

index 11c0cea..22b32a0 100644 (file)
@@ -1,3 +1,25 @@
+2016-05-18  Filip Pizlo  <fpizlo@apple.com>
+
+        DFG::LICMPhase shouldn't hoist type checks unless it knows that the check will succeed at the loop pre-header
+        https://bugs.webkit.org/show_bug.cgi?id=144527
+
+        Reviewed by Saam Barati.
+        
+        Add tests for LICM hoisting things that would only exit if hoisted.
+
+        * js/regress/licm-dragons-expected.txt: Added.
+        * js/regress/licm-dragons-out-of-bounds-expected.txt: Added.
+        * js/regress/licm-dragons-out-of-bounds.html: Added.
+        * js/regress/licm-dragons-overflow-expected.txt: Added.
+        * js/regress/licm-dragons-overflow.html: Added.
+        * js/regress/licm-dragons.html: Added.
+        * js/regress/script-tests/licm-dragons-out-of-bounds.js: Added.
+        (foo):
+        * js/regress/script-tests/licm-dragons-overflow.js: Added.
+        (foo):
+        * js/regress/script-tests/licm-dragons.js: Added.
+        (foo):
+
 2016-05-19  Brian Burg  <bburg@apple.com>
 
         Web Inspector: use a consistent prefix for injected scripts
diff --git a/LayoutTests/js/regress/licm-dragons-expected.txt b/LayoutTests/js/regress/licm-dragons-expected.txt
new file mode 100644 (file)
index 0000000..1fd6328
--- /dev/null
@@ -0,0 +1,10 @@
+JSRegress/licm-dragons
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
diff --git a/LayoutTests/js/regress/licm-dragons-out-of-bounds-expected.txt b/LayoutTests/js/regress/licm-dragons-out-of-bounds-expected.txt
new file mode 100644 (file)
index 0000000..b7f2d58
--- /dev/null
@@ -0,0 +1,10 @@
+JSRegress/licm-dragons-out-of-bounds
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
diff --git a/LayoutTests/js/regress/licm-dragons-out-of-bounds.html b/LayoutTests/js/regress/licm-dragons-out-of-bounds.html
new file mode 100644 (file)
index 0000000..7063f80
--- /dev/null
@@ -0,0 +1,12 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src="../../resources/js-test-pre.js"></script>
+</head>
+<body>
+<script src="../../resources/regress-pre.js"></script>
+<script src="script-tests/licm-dragons-out-of-bounds.js"></script>
+<script src="../../resources/regress-post.js"></script>
+<script src="../../resources/js-test-post.js"></script>
+</body>
+</html>
diff --git a/LayoutTests/js/regress/licm-dragons-overflow-expected.txt b/LayoutTests/js/regress/licm-dragons-overflow-expected.txt
new file mode 100644 (file)
index 0000000..1f1c12b
--- /dev/null
@@ -0,0 +1,10 @@
+JSRegress/licm-dragons-overflow
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
diff --git a/LayoutTests/js/regress/licm-dragons-overflow.html b/LayoutTests/js/regress/licm-dragons-overflow.html
new file mode 100644 (file)
index 0000000..35736fd
--- /dev/null
@@ -0,0 +1,12 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src="../../resources/js-test-pre.js"></script>
+</head>
+<body>
+<script src="../../resources/regress-pre.js"></script>
+<script src="script-tests/licm-dragons-overflow.js"></script>
+<script src="../../resources/regress-post.js"></script>
+<script src="../../resources/js-test-post.js"></script>
+</body>
+</html>
diff --git a/LayoutTests/js/regress/licm-dragons.html b/LayoutTests/js/regress/licm-dragons.html
new file mode 100644 (file)
index 0000000..990e51b
--- /dev/null
@@ -0,0 +1,12 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src="../../resources/js-test-pre.js"></script>
+</head>
+<body>
+<script src="../../resources/regress-pre.js"></script>
+<script src="script-tests/licm-dragons.js"></script>
+<script src="../../resources/regress-post.js"></script>
+<script src="../../resources/js-test-post.js"></script>
+</body>
+</html>
diff --git a/LayoutTests/js/regress/script-tests/licm-dragons-out-of-bounds.js b/LayoutTests/js/regress/script-tests/licm-dragons-out-of-bounds.js
new file mode 100644 (file)
index 0000000..9354205
--- /dev/null
@@ -0,0 +1,30 @@
+function foo(p, o, i) {
+    var result = 0;
+    for (var j = 0; j < 1000; ++j) {
+        if (p)
+            result += o[i];
+        else
+            result++;
+    }
+    return result;
+}
+
+noInline(foo);
+
+var o = [42];
+
+var result = 0;
+
+for (var i = 0; i < 1000; ++i) {
+    result += foo(true, o, 0);
+    result += foo(false, o, 1);
+}
+
+for (var i = 0; i < 10000; ++i)
+    result += foo(false, o, 1);
+
+for (var i = 0; i < 20000; ++i)
+    result += foo(true, o, 0);
+
+if (result != 893000000)
+    throw "Error: bad result: " + result;
diff --git a/LayoutTests/js/regress/script-tests/licm-dragons-overflow.js b/LayoutTests/js/regress/script-tests/licm-dragons-overflow.js
new file mode 100644 (file)
index 0000000..d73936c
--- /dev/null
@@ -0,0 +1,28 @@
+function foo(p, a, b) {
+    var result = 0;
+    for (var i = 0; i < 1000; ++i) {
+        if (p)
+            result += a + b;
+        else
+            result += a - b;
+    }
+    return result;
+}
+
+noInline(foo);
+
+var result = 0;
+
+for (var i = 0; i < 1000; ++i) {
+    result += foo(true, 1, 2);
+    result += foo(false, 2000000000, 2000000000);
+}
+
+for (var i = 0; i < 10000; ++i)
+    result += foo(false, 2000000000, 2000000000);
+
+for (var i = 0; i < 10000; ++i)
+    result += foo(true, 1, 2);
+
+if (result != 33000000)
+    throw "Error: bad result: " + result;
diff --git a/LayoutTests/js/regress/script-tests/licm-dragons.js b/LayoutTests/js/regress/script-tests/licm-dragons.js
new file mode 100644 (file)
index 0000000..9b368e8
--- /dev/null
@@ -0,0 +1,31 @@
+function foo(p, o) {
+    var result = 0;
+    for (var i = 0; i < 1000; ++i) {
+        if (p)
+            result += o.f;
+        else
+            result++;
+    }
+    return result;
+}
+
+noInline(foo);
+
+var o = {f:42};
+var p = {};
+
+var result = 0;
+
+for (var i = 0; i < 1000; ++i) {
+    result += foo(true, o);
+    result += foo(false, p);
+}
+
+for (var i = 0; i < 10000; ++i)
+    result += foo(false, p);
+
+for (var i = 0; i < 30000; ++i)
+    result += foo(true, o);
+
+if (result != 1313000000)
+    throw "Error: bad result: " + result;
index f819940..784af33 100644 (file)
@@ -1,3 +1,98 @@
+2016-05-18  Filip Pizlo  <fpizlo@apple.com>
+
+        DFG::LICMPhase shouldn't hoist type checks unless it knows that the check will succeed at the loop pre-header
+        https://bugs.webkit.org/show_bug.cgi?id=144527
+
+        Reviewed by Saam Barati.
+        
+        This adds a control flow equivalence analysis (called ControlEquivalenceAnalysis) based on
+        dominator analysis over the backwards CFG. Two basic blocks are control flow equivalent if
+        the execution of one implies that the other one must also execute. It means that the two
+        blocks' forward and backward dominance are reciprocated: (A dom B and B backdom A) or (B dom
+        A and A backdom B). LICM now uses it to become more conservative about hoisting checks, if
+        this has caused problems in the past. If we hoist something that may exit from a block that
+        was not control equivalent to the pre-header then it's possible that the node's speculation
+        will fail even though it wouldn't have if it wasn't hoisted. So, we flag these nodes'
+        origins as being "wasHoisted" and we track all of their exits as "HoistingFailed". LICM will
+        turn off such speculative hoisting if the CodeBlock from which we are hoisting had the
+        HoistingFailed exit kind.
+        
+        Note that this deliberately still allows us to hoist things that may exit even if they are
+        not control equivalent to the pre-header. This is necessary because the profitability of
+        hoisting is so huge in all of the cases that we're aware of that it's worth giving it a
+        shot.
+        
+        This is neutral on macrobenchmarks since none of the benchmarks we track have a hoistable
+        operation that would exit only if hoisted. I added microbenchmarks to illustrate the problem
+        and two of them speed up by ~40% while one of them is neutral (Int52 saves us from having
+        problems on that program even though LICM previously did the wrong thing).
+
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * bytecode/ExitKind.cpp:
+        (JSC::exitKindToString):
+        * bytecode/ExitKind.h:
+        * dfg/DFGAtTailAbstractState.h:
+        (JSC::DFG::AtTailAbstractState::operator bool):
+        (JSC::DFG::AtTailAbstractState::initializeTo):
+        * dfg/DFGBackwardsCFG.h: Added.
+        (JSC::DFG::BackwardsCFG::BackwardsCFG):
+        * dfg/DFGBackwardsDominators.h: Added.
+        (JSC::DFG::BackwardsDominators::BackwardsDominators):
+        * dfg/DFGCommon.h:
+        (JSC::DFG::checkAndSet): Deleted.
+        * dfg/DFGControlEquivalenceAnalysis.h: Added.
+        (JSC::DFG::ControlEquivalenceAnalysis::ControlEquivalenceAnalysis):
+        (JSC::DFG::ControlEquivalenceAnalysis::dominatesEquivalently):
+        (JSC::DFG::ControlEquivalenceAnalysis::areEquivalent):
+        * dfg/DFGGraph.cpp:
+        (JSC::DFG::Graph::dump):
+        (JSC::DFG::Graph::dumpBlockHeader):
+        (JSC::DFG::Graph::invalidateCFG):
+        (JSC::DFG::Graph::substituteGetLocal):
+        (JSC::DFG::Graph::handleAssertionFailure):
+        (JSC::DFG::Graph::ensureDominators):
+        (JSC::DFG::Graph::ensurePrePostNumbering):
+        (JSC::DFG::Graph::ensureNaturalLoops):
+        (JSC::DFG::Graph::ensureBackwardsCFG):
+        (JSC::DFG::Graph::ensureBackwardsDominators):
+        (JSC::DFG::Graph::ensureControlEquivalenceAnalysis):
+        (JSC::DFG::Graph::methodOfGettingAValueProfileFor):
+        * dfg/DFGGraph.h:
+        (JSC::DFG::Graph::hasDebuggerEnabled):
+        * dfg/DFGInPlaceAbstractState.h:
+        (JSC::DFG::InPlaceAbstractState::operator bool):
+        (JSC::DFG::InPlaceAbstractState::createValueForNode):
+        (JSC::DFG::InPlaceAbstractState::forNode):
+        * dfg/DFGLICMPhase.cpp:
+        (JSC::DFG::LICMPhase::run):
+        (JSC::DFG::LICMPhase::attemptHoist):
+        * dfg/DFGMayExit.cpp:
+        (JSC::DFG::mayExit):
+        * dfg/DFGMayExit.h:
+        * dfg/DFGNode.h:
+        * dfg/DFGNodeOrigin.cpp:
+        (JSC::DFG::NodeOrigin::dump):
+        * dfg/DFGNodeOrigin.h:
+        (JSC::DFG::NodeOrigin::takeValidExit):
+        (JSC::DFG::NodeOrigin::withWasHoisted):
+        (JSC::DFG::NodeOrigin::forInsertingAfter):
+        * dfg/DFGNullAbstractState.h: Added.
+        (JSC::DFG::NullAbstractState::NullAbstractState):
+        (JSC::DFG::NullAbstractState::operator bool):
+        (JSC::DFG::NullAbstractState::forNode):
+        * dfg/DFGOSRExit.cpp:
+        (JSC::DFG::OSRExit::OSRExit):
+        * dfg/DFGOSRExitBase.cpp:
+        (JSC::DFG::OSRExitBase::considerAddingAsFrequentExitSiteSlow):
+        * dfg/DFGOSRExitBase.h:
+        (JSC::DFG::OSRExitBase::OSRExitBase):
+        * dfg/DFGTypeCheckHoistingPhase.cpp:
+        (JSC::DFG::TypeCheckHoistingPhase::run):
+        * ftl/FTLOSRExit.cpp:
+        (JSC::FTL::OSRExitDescriptor::prepareOSRExitHandle):
+        (JSC::FTL::OSRExit::OSRExit):
+        * ftl/FTLOSRExit.h:
+
 2016-05-19  Mark Lam  <mark.lam@apple.com>
 
         Code that null checks the VM pointer before any use should ref the VM.
index b1cbaba..7ebbccc 100644 (file)
                DC605B601CE26EA700593718 /* ProfilerUID.h in Headers */ = {isa = PBXBuildFile; fileRef = DC605B5C1CE26E9800593718 /* ProfilerUID.h */; settings = {ATTRIBUTES = (Private, ); }; };
                DC7997831CDE9FA0004D4A09 /* TagRegistersMode.h in Headers */ = {isa = PBXBuildFile; fileRef = DC7997821CDE9F9E004D4A09 /* TagRegistersMode.h */; settings = {ATTRIBUTES = (Private, ); }; };
                DC7997841CDE9FA2004D4A09 /* TagRegistersMode.cpp in Sources */ = {isa = PBXBuildFile; fileRef = DC7997811CDE9F9E004D4A09 /* TagRegistersMode.cpp */; };
+               DCEE22091CEB9895000C2396 /* DFGBackwardsCFG.h in Headers */ = {isa = PBXBuildFile; fileRef = DCEE22061CEB9890000C2396 /* DFGBackwardsCFG.h */; };
+               DCEE220A1CEB9895000C2396 /* DFGBackwardsDominators.h in Headers */ = {isa = PBXBuildFile; fileRef = DCEE22071CEB9890000C2396 /* DFGBackwardsDominators.h */; };
+               DCEE220B1CEB9895000C2396 /* DFGControlEquivalenceAnalysis.h in Headers */ = {isa = PBXBuildFile; fileRef = DCEE22081CEB9890000C2396 /* DFGControlEquivalenceAnalysis.h */; };
+               DCEE220D1CEBAF75000C2396 /* DFGNullAbstractState.h in Headers */ = {isa = PBXBuildFile; fileRef = DCEE220C1CEBAF73000C2396 /* DFGNullAbstractState.h */; };
                DCF3D5691CD2946D003D5C65 /* LazyClassStructure.cpp in Sources */ = {isa = PBXBuildFile; fileRef = DCF3D5641CD29468003D5C65 /* LazyClassStructure.cpp */; };
                DCF3D56A1CD29470003D5C65 /* LazyClassStructure.h in Headers */ = {isa = PBXBuildFile; fileRef = DCF3D5651CD29468003D5C65 /* LazyClassStructure.h */; settings = {ATTRIBUTES = (Private, ); }; };
                DCF3D56B1CD29472003D5C65 /* LazyClassStructureInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = DCF3D5661CD29468003D5C65 /* LazyClassStructureInlines.h */; };
                DC605B5C1CE26E9800593718 /* ProfilerUID.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = ProfilerUID.h; path = profiler/ProfilerUID.h; sourceTree = "<group>"; };
                DC7997811CDE9F9E004D4A09 /* TagRegistersMode.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = TagRegistersMode.cpp; sourceTree = "<group>"; };
                DC7997821CDE9F9E004D4A09 /* TagRegistersMode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TagRegistersMode.h; sourceTree = "<group>"; };
+               DCEE22061CEB9890000C2396 /* DFGBackwardsCFG.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBackwardsCFG.h; path = dfg/DFGBackwardsCFG.h; sourceTree = "<group>"; };
+               DCEE22071CEB9890000C2396 /* DFGBackwardsDominators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBackwardsDominators.h; path = dfg/DFGBackwardsDominators.h; sourceTree = "<group>"; };
+               DCEE22081CEB9890000C2396 /* DFGControlEquivalenceAnalysis.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGControlEquivalenceAnalysis.h; path = dfg/DFGControlEquivalenceAnalysis.h; sourceTree = "<group>"; };
+               DCEE220C1CEBAF73000C2396 /* DFGNullAbstractState.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGNullAbstractState.h; path = dfg/DFGNullAbstractState.h; sourceTree = "<group>"; };
                DCF3D5641CD29468003D5C65 /* LazyClassStructure.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LazyClassStructure.cpp; sourceTree = "<group>"; };
                DCF3D5651CD29468003D5C65 /* LazyClassStructure.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LazyClassStructure.h; sourceTree = "<group>"; };
                DCF3D5661CD29468003D5C65 /* LazyClassStructureInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LazyClassStructureInlines.h; sourceTree = "<group>"; };
                                0F666EC31835672B00D017F1 /* DFGAvailability.h */,
                                0F2B9CD619D0BA7D00B1D1B5 /* DFGAvailabilityMap.cpp */,
                                0F2B9CD719D0BA7D00B1D1B5 /* DFGAvailabilityMap.h */,
+                               DCEE22061CEB9890000C2396 /* DFGBackwardsCFG.h */,
+                               DCEE22071CEB9890000C2396 /* DFGBackwardsDominators.h */,
                                0F714CA116EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.cpp */,
                                0F714CA216EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.h */,
                                A7D89CE317A0B8CC00773AD8 /* DFGBasicBlock.cpp */,
                                0F3B3A18153E68EF003ED0FF /* DFGConstantFoldingPhase.h */,
                                0FED67B71B26256D0066CE15 /* DFGConstantHoistingPhase.cpp */,
                                0FED67B81B26256D0066CE15 /* DFGConstantHoistingPhase.h */,
+                               DCEE22081CEB9890000C2396 /* DFGControlEquivalenceAnalysis.h */,
                                0FBE0F6B16C1DB010082C5E8 /* DFGCPSRethreadingPhase.cpp */,
                                0FBE0F6C16C1DB010082C5E8 /* DFGCPSRethreadingPhase.h */,
                                A7D89CE617A0B8CC00773AD8 /* DFGCriticalEdgeBreakingPhase.cpp */,
                                0F5D085C1B8CF99D001143B4 /* DFGNodeOrigin.cpp */,
                                0F300B7718AB051100A6D72E /* DFGNodeOrigin.h */,
                                0FA581B9150E952A00B9A2D9 /* DFGNodeType.h */,
+                               DCEE220C1CEBAF73000C2396 /* DFGNullAbstractState.h */,
                                0F2B9CDA19D0BA7D00B1D1B5 /* DFGObjectAllocationSinkingPhase.cpp */,
                                0F2B9CDB19D0BA7D00B1D1B5 /* DFGObjectAllocationSinkingPhase.h */,
                                0F2B9CDC19D0BA7D00B1D1B5 /* DFGObjectMaterializationData.cpp */,
                        buildActionMask = 2147483647;
                        files = (
                                0FFA549816B8835300B3A982 /* A64DOpcode.h in Headers */,
+                               DCEE220A1CEB9895000C2396 /* DFGBackwardsDominators.h in Headers */,
                                0F1FE51C1922A3BC006987C5 /* AbortReason.h in Headers */,
                                860161E30F3A83C100F84710 /* AbstractMacroAssembler.h in Headers */,
                                0F55F0F514D1063C00AC7649 /* AbstractPC.h in Headers */,
                                BC18C3E50E16F5CD00B34460 /* APICast.h in Headers */,
                                FE3A06BE1C11041200390FDD /* JITLeftShiftGenerator.h in Headers */,
                                BCF605140E203EF800B9A64D /* ArgList.h in Headers */,
+                               DCEE22091CEB9895000C2396 /* DFGBackwardsCFG.h in Headers */,
                                0FE050141AA9091100D33B33 /* ArgumentsMode.h in Headers */,
                                0F6B1CB91861244C00845D97 /* ArityCheckMode.h in Headers */,
                                A1A009C11831A26E00CF8711 /* ARM64Assembler.h in Headers */,
                                0FF729B9166AD360000F5BA3 /* ProfilerBytecodes.h in Headers */,
                                0F13912A16771C36009CCB07 /* ProfilerBytecodeSequence.h in Headers */,
                                0FB387901BFBC44D00E3AB1E /* AirOptimizeBlockOrder.h in Headers */,
+                               DCEE220D1CEBAF75000C2396 /* DFGNullAbstractState.h in Headers */,
                                0FF729BA166AD360000F5BA3 /* ProfilerCompilation.h in Headers */,
                                0FF729BB166AD360000F5BA3 /* ProfilerCompilationKind.h in Headers */,
                                0F4A38FA1C8E13DF00190318 /* SuperSampler.h in Headers */,
                                141448CD13A1783700F5BA1A /* TinyBloomFilter.h in Headers */,
                                2684D4381C00161C0081D663 /* AirLiveness.h in Headers */,
                                0F55989817C86C5800A1E543 /* ToNativeFromValue.h in Headers */,
+                               DCEE220B1CEB9895000C2396 /* DFGControlEquivalenceAnalysis.h in Headers */,
                                0F2D4DE919832DAC007D4B19 /* ToThisStatus.h in Headers */,
                                0F952ABD1B487A7700C367C5 /* TrackedReferences.h in Headers */,
                                0F2B670617B6B5AB00A7AE3F /* TypedArrayAdaptors.h in Headers */,
index 84ff57b..f1ea76d 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2012-2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2012-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -76,6 +76,8 @@ const char* exitKindToString(ExitKind kind)
         return "VarargsOverflow";
     case TDZFailure:
         return "TDZFailure";
+    case HoistingFailed:
+        return "HoistingFailed";
     case Uncountable:
         return "Uncountable";
     case UncountableInvalidation:
index 22a54a1..9a3c1b0 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2012-2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2012-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -50,6 +50,7 @@ enum ExitKind : uint8_t {
     NotStringObject, // We exited because we shouldn't have attempted to optimize string object access.
     VarargsOverflow, // We exited because a varargs call passed more arguments than we expected.
     TDZFailure, // We exited because we were in the TDZ and accessed the variable.
+    HoistingFailed, // Something that was hoisted exited. So, assume that hoisting is a bad idea.
     Uncountable, // We exited for none of the above reasons, and we should not count it. Most uses of this should be viewed as a FIXME.
     UncountableInvalidation, // We exited because the code block was invalidated; this means that we've already counted the reasons why the code block was invalidated.
     WatchdogTimerFired, // We exited because we need to service the watchdog timer.
index cd6a080..d0d8c42 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2013, 2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -40,6 +40,8 @@ public:
     
     ~AtTailAbstractState();
     
+    explicit operator bool() const { return true; }
+    
     void initializeTo(BasicBlock* block)
     {
         m_block = block;
diff --git a/Source/JavaScriptCore/dfg/DFGBackwardsCFG.h b/Source/JavaScriptCore/dfg/DFGBackwardsCFG.h
new file mode 100644 (file)
index 0000000..97df73f
--- /dev/null
@@ -0,0 +1,51 @@
+/*
+ * Copyright (C) 2016 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 DFGBackwardsCFG_h
+#define DFGBackwardsCFG_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGCFG.h"
+#include <wtf/BackwardsGraph.h>
+
+namespace JSC { namespace DFG {
+
+class BackwardsCFG : public BackwardsGraph<CFG> {
+    WTF_MAKE_NONCOPYABLE(BackwardsCFG);
+    WTF_MAKE_FAST_ALLOCATED;
+public:
+    BackwardsCFG(Graph& graph)
+        : BackwardsGraph<CFG>(*graph.m_cfg)
+    {
+    }
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGBackwardsCFG_h
+
diff --git a/Source/JavaScriptCore/dfg/DFGBackwardsDominators.h b/Source/JavaScriptCore/dfg/DFGBackwardsDominators.h
new file mode 100644 (file)
index 0000000..0eef3b5
--- /dev/null
@@ -0,0 +1,52 @@
+/*
+ * Copyright (C) 2016 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 DFGBackwardsDominators_h
+#define DFGBackwardsDominators_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBackwardsCFG.h"
+#include <wtf/Dominators.h>
+#include <wtf/FastMalloc.h>
+#include <wtf/Noncopyable.h>
+
+namespace JSC { namespace DFG {
+
+class BackwardsDominators : public WTF::Dominators<BackwardsCFG> {
+    WTF_MAKE_NONCOPYABLE(BackwardsDominators);
+    WTF_MAKE_FAST_ALLOCATED;
+public:
+    BackwardsDominators(Graph& graph)
+        : WTF::Dominators<BackwardsCFG>(graph.ensureBackwardsCFG())
+    {
+    }
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGDominators_h
index 01a0b35..bd3754f 100644 (file)
@@ -255,15 +255,6 @@ enum class PlanStage {
     AfterFixup
 };
 
-template<typename T, typename U>
-bool checkAndSet(T& left, U right)
-{
-    if (left == right)
-        return false;
-    left = right;
-    return true;
-}
-
 // If possible, this will acquire a lock to make sure that if multiple threads
 // start crashing at the same time, you get coherent dump output. Use this only
 // when you're forcing a crash with diagnostics.
diff --git a/Source/JavaScriptCore/dfg/DFGControlEquivalenceAnalysis.h b/Source/JavaScriptCore/dfg/DFGControlEquivalenceAnalysis.h
new file mode 100644 (file)
index 0000000..e5045d6
--- /dev/null
@@ -0,0 +1,88 @@
+/*
+ * Copyright (C) 2016 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 DFGControlEquivalenceAnalysis_h
+#define DFGControlEquivalenceAnalysis_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBackwardsDominators.h"
+#include "DFGDominators.h"
+
+namespace JSC { namespace DFG {
+
+class ControlEquivalenceAnalysis {
+    WTF_MAKE_NONCOPYABLE(ControlEquivalenceAnalysis);
+    WTF_MAKE_FAST_ALLOCATED;
+public:
+    ControlEquivalenceAnalysis(Graph& graph)
+        : m_dominators(graph.ensureDominators())
+        , m_backwardsDominators(graph.ensureBackwardsDominators())
+    {
+    }
+    
+    // This returns true iff:
+    //
+    // - If b executes then a must have executed before it (a dominates b).
+    // - If a executes then b will execute after it (b backwards-dominates a).
+    //
+    // Note that like Dominators and BackwardsDominators, this analysis ignores OSR:
+    //
+    // - This may return true even if we OSR enter in beteen a and b. OSR entry would mean that b
+    //   could execute even if a had not executed. This is impossible in DFG SSA but it's possible
+    //   in DFG CPS.
+    // - This may return true even if we OSR exit in between a and b. OSR exit would mean that a
+    //   could execute even though b will not execute. This is possible in all forms of DFG IR.
+    //
+    // In DFG SSA you only have to worry about the definition being weaked by exits. This is usually
+    // OK, since we use this analysis to determine the cost of moving exits from one block to
+    // another. If we move an exit from b to a and a equivalently dominates b then at worst we have
+    // made the exit happen sooner. If we move an exit from b to a and a dominates b but not
+    // equivalently then we've done something much worse: the program may now exit even if it would
+    // not have ever exited before.
+    bool dominatesEquivalently(BasicBlock* a, BasicBlock* b)
+    {
+        return m_dominators.dominates(a, b)
+            && m_backwardsDominators.dominates(b, a);
+    }
+    
+    // This returns true iff the execution of a implies that b also executes and vice-versa.
+    bool areEquivalent(BasicBlock* a, BasicBlock* b)
+    {
+        return dominatesEquivalently(a, b)
+            || dominatesEquivalently(b, a);
+    }
+
+private:
+    Dominators& m_dominators;
+    BackwardsDominators& m_backwardsDominators;
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGControlEquivalenceAnalysis_h
+
index 06681bd..ea308f5 100644 (file)
 #include "BytecodeLivenessAnalysisInlines.h"
 #include "CodeBlock.h"
 #include "CodeBlockWithJITType.h"
+#include "DFGBackwardsCFG.h"
+#include "DFGBackwardsDominators.h"
 #include "DFGBlockWorklist.h"
+#include "DFGCFG.h"
 #include "DFGClobberSet.h"
 #include "DFGClobbersExitState.h"
-#include "DFGCFG.h"
+#include "DFGControlEquivalenceAnalysis.h"
 #include "DFGDominators.h"
 #include "DFGJITCode.h"
 #include "DFGMayExit.h"
@@ -375,6 +378,8 @@ void Graph::dump(PrintStream& out, const char* prefix, Node* node, DumpContext*
     }
     if (!node->origin.exitOK)
         out.print(comma, "ExitInvalid");
+    if (node->origin.wasHoisted)
+        out.print(comma, "WasHoisted");
     out.print(")");
 
     if (node->hasVariableAccessData(*this) && node->tryGetVariableAccessData())
@@ -419,6 +424,18 @@ void Graph::dumpBlockHeader(PrintStream& out, const char* prefix, BasicBlock* bl
         out.print(prefix, "  Dominance Frontier: ", m_dominators->dominanceFrontierOf(block), "\n");
         out.print(prefix, "  Iterated Dominance Frontier: ", m_dominators->iteratedDominanceFrontierOf(BlockList(1, block)), "\n");
     }
+    if (m_backwardsDominators && terminalsAreValid()) {
+        out.print(prefix, "  Backwards dominates by: ", m_backwardsDominators->dominatorsOf(block), "\n");
+        out.print(prefix, "  Backwards dominates: ", m_backwardsDominators->blocksDominatedBy(block), "\n");
+    }
+    if (m_controlEquivalenceAnalysis && terminalsAreValid()) {
+        out.print(prefix, "  Control equivalent to:");
+        for (BasicBlock* otherBlock : blocksInNaturalOrder()) {
+            if (m_controlEquivalenceAnalysis->areEquivalent(block, otherBlock))
+                out.print(" ", *otherBlock);
+        }
+        out.print("\n");
+    }
     if (m_prePostNumbering)
         out.print(prefix, "  Pre/Post Numbering: ", m_prePostNumbering->preNumber(block), "/", m_prePostNumbering->postNumber(block), "\n");
     if (m_naturalLoops) {
@@ -753,6 +770,9 @@ void Graph::invalidateCFG()
     m_dominators = nullptr;
     m_naturalLoops = nullptr;
     m_prePostNumbering = nullptr;
+    m_controlEquivalenceAnalysis = nullptr;
+    m_backwardsDominators = nullptr;
+    m_backwardsCFG = nullptr;
 }
 
 void Graph::substituteGetLocal(BasicBlock& block, unsigned startIndexInBlock, VariableAccessData* variableAccessData, Node* newGetLocal)
@@ -1426,23 +1446,47 @@ void Graph::handleAssertionFailure(
     crash(*this, toCString("While handling block ", pointerDump(block), "\n\n"), file, line, function, assertion);
 }
 
-void Graph::ensureDominators()
+Dominators& Graph::ensureDominators()
 {
     if (!m_dominators)
         m_dominators = std::make_unique<Dominators>(*this);
+    return *m_dominators;
 }
 
-void Graph::ensurePrePostNumbering()
+PrePostNumbering& Graph::ensurePrePostNumbering()
 {
     if (!m_prePostNumbering)
         m_prePostNumbering = std::make_unique<PrePostNumbering>(*this);
+    return *m_prePostNumbering;
 }
 
-void Graph::ensureNaturalLoops()
+NaturalLoops& Graph::ensureNaturalLoops()
 {
     ensureDominators();
     if (!m_naturalLoops)
         m_naturalLoops = std::make_unique<NaturalLoops>(*this);
+    return *m_naturalLoops;
+}
+
+BackwardsCFG& Graph::ensureBackwardsCFG()
+{
+    if (!m_backwardsCFG)
+        m_backwardsCFG = std::make_unique<BackwardsCFG>(*this);
+    return *m_backwardsCFG;
+}
+
+BackwardsDominators& Graph::ensureBackwardsDominators()
+{
+    if (!m_backwardsDominators)
+        m_backwardsDominators = std::make_unique<BackwardsDominators>(*this);
+    return *m_backwardsDominators;
+}
+
+ControlEquivalenceAnalysis& Graph::ensureControlEquivalenceAnalysis()
+{
+    if (!m_controlEquivalenceAnalysis)
+        m_controlEquivalenceAnalysis = std::make_unique<ControlEquivalenceAnalysis>(*this);
+    return *m_controlEquivalenceAnalysis;
 }
 
 MethodOfGettingAValueProfile Graph::methodOfGettingAValueProfileFor(Node* node)
index 86b3eef..a043a48 100644 (file)
@@ -56,7 +56,10 @@ class ExecState;
 
 namespace DFG {
 
+class BackwardsCFG;
+class BackwardsDominators;
 class CFG;
+class ControlEquivalenceAnalysis;
 class Dominators;
 class NaturalLoops;
 class PrePostNumbering;
@@ -800,9 +803,12 @@ public:
 
     bool hasDebuggerEnabled() const { return m_hasDebuggerEnabled; }
 
-    void ensureDominators();
-    void ensurePrePostNumbering();
-    void ensureNaturalLoops();
+    Dominators& ensureDominators();
+    PrePostNumbering& ensurePrePostNumbering();
+    NaturalLoops& ensureNaturalLoops();
+    BackwardsCFG& ensureBackwardsCFG();
+    BackwardsDominators& ensureBackwardsDominators();
+    ControlEquivalenceAnalysis& ensureControlEquivalenceAnalysis();
 
     // This function only makes sense to call after bytecode parsing
     // because it queries the m_hasExceptionHandlers boolean whose value
@@ -879,6 +885,9 @@ public:
     std::unique_ptr<PrePostNumbering> m_prePostNumbering;
     std::unique_ptr<NaturalLoops> m_naturalLoops;
     std::unique_ptr<CFG> m_cfg;
+    std::unique_ptr<BackwardsCFG> m_backwardsCFG;
+    std::unique_ptr<BackwardsDominators> m_backwardsDominators;
+    std::unique_ptr<ControlEquivalenceAnalysis> m_controlEquivalenceAnalysis;
     unsigned m_localVars;
     unsigned m_nextMachineLocal;
     unsigned m_parameterSlots;
index 10220cd..794ad8a 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2013, 2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -42,6 +42,8 @@ public:
     
     ~InPlaceAbstractState();
     
+    explicit operator bool() const { return true; }
+    
     void createValueForNode(Node*) { }
     
     AbstractValue& forNode(Node* node)
index 667622b..86f4a6b 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013-2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2013-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
 #include "DFGBasicBlockInlines.h"
 #include "DFGClobberSet.h"
 #include "DFGClobberize.h"
+#include "DFGControlEquivalenceAnalysis.h"
 #include "DFGEdgeDominates.h"
 #include "DFGGraph.h"
 #include "DFGInsertionSet.h"
+#include "DFGMayExit.h"
 #include "DFGNaturalLoops.h"
 #include "DFGPhase.h"
 #include "DFGSafeToExecute.h"
@@ -74,6 +76,7 @@ public:
         
         m_graph.ensureDominators();
         m_graph.ensureNaturalLoops();
+        m_graph.ensureControlEquivalenceAnalysis();
 
         if (verbose) {
             dataLog("Graph before LICM:\n");
@@ -260,43 +263,6 @@ private:
         // we could still hoist just the checks.
         // https://bugs.webkit.org/show_bug.cgi?id=144525
         
-        // FIXME: If a node has a type check - even something like a CheckStructure - then we should
-        // only hoist the node if we know that it will execute on every loop iteration or if we know
-        // that the type check will always succeed at the loop pre-header through some other means
-        // (like looking at prediction propagation results). Otherwise, we might make a mistake like
-        // this:
-        //
-        // var o = ...; // sometimes null and sometimes an object with structure S1.
-        // for (...) {
-        //     if (o)
-        //         ... = o.f; // CheckStructure and GetByOffset, which we will currently hoist.
-        // }
-        //
-        // When we encounter such code, we'll hoist the CheckStructure and GetByOffset and then we
-        // will have a recompile. We'll then end up thinking that the get_by_id needs to be
-        // polymorphic, which is false.
-        //
-        // We can counter this by either having a control flow equivalence check, or by consulting
-        // prediction propagation to see if the check would always succeed. Prediction propagation
-        // would not be enough for things like:
-        //
-        // var p = ...; // some boolean predicate
-        // var o = {};
-        // if (p)
-        //     o.f = 42;
-        // for (...) {
-        //     if (p)
-        //         ... = o.f;
-        // }
-        //
-        // Prediction propagation can't tell us anything about the structure, and the CheckStructure
-        // will appear to be hoistable because the loop doesn't clobber structures. The cell check
-        // in the CheckStructure will be hoistable though, since prediction propagation can tell us
-        // that o is always SpecFinalObject. In cases like this, control flow equivalence is the
-        // only effective guard.
-        //
-        // https://bugs.webkit.org/show_bug.cgi?id=144527
-        
         if (readsOverlap(m_graph, node, data.writes)) {
             if (verbose) {
                 dataLog(
@@ -315,6 +281,25 @@ private:
             return false;
         }
         
+        NodeOrigin originalOrigin = node->origin;
+
+        // NOTE: We could just use BackwardsDominators here directly, since we already know that the
+        // preHeader dominates fromBlock. But we wouldn't get anything from being so clever, since
+        // dominance checks are O(1) and only a few integer compares.
+        bool addsBlindSpeculation = mayExit(m_graph, node, m_state)
+            && !m_graph.m_controlEquivalenceAnalysis->dominatesEquivalently(data.preHeader, fromBlock);
+        
+        if (addsBlindSpeculation
+            && m_graph.baselineCodeBlockFor(originalOrigin.semantic)->hasExitSite(FrequentExitSite(HoistingFailed))) {
+            if (verbose) {
+                dataLog(
+                    "    Not hoisting ", node, " because it may exit and the pre-header (",
+                    *data.preHeader, ") is not control equivalent to the node's original block (",
+                    *fromBlock, ") and hoisting had previously failed.\n");
+            }
+            return false;
+        }
+        
         if (verbose) {
             dataLog(
                 "    Hoisting ", node, " from ", *fromBlock, " to ", *data.preHeader,
@@ -326,8 +311,9 @@ private:
         // https://bugs.webkit.org/show_bug.cgi?id=148544
         data.preHeader->insertBeforeTerminal(node);
         node->owner = data.preHeader;
-        NodeOrigin originalOrigin = node->origin;
-        node->origin = data.preHeader->terminal()->origin.withSemantic(node->origin.semantic);
+        NodeOrigin terminalOrigin = data.preHeader->terminal()->origin;
+        node->origin = terminalOrigin.withSemantic(node->origin.semantic);
+        node->origin.wasHoisted |= addsBlindSpeculation;
         
         // Modify the states at the end of the preHeader of the loop we hoisted to,
         // and all pre-headers inside the loop. This isn't a stability bottleneck right now
index 5c5c60e..aee1cff 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
 
 #if ENABLE(DFG_JIT)
 
+#include "DFGAtTailAbstractState.h"
 #include "DFGGraph.h"
 #include "DFGNode.h"
+#include "DFGNullAbstractState.h"
 #include "Operations.h"
 
 namespace JSC { namespace DFG {
 
 namespace {
 
-class EdgeMayExit {
-public:
-    EdgeMayExit()
-        : m_result(false)
-    {
-    }
-    
-    void operator()(Node*, Edge edge)
-    {
-        // FIXME: Maybe this should call mayHaveTypeCheck(edge.useKind()) instead.
-        // https://bugs.webkit.org/show_bug.cgi?id=148545
-        if (edge.willHaveCheck()) {
-            m_result = true;
-            return;
-        }
-
-        switch (edge.useKind()) {
-        // These are shady because nodes that have these use kinds will typically exit for
-        // unrelated reasons. For example CompareEq doesn't usually exit, but if it uses ObjectUse
-        // then it will.
-        case ObjectUse:
-        case ObjectOrOtherUse:
-            m_result = true;
-            break;
-            
-        // These are shady because they check the structure even if the type of the child node
-        // passes the StringObject type filter.
-        case StringObjectUse:
-        case StringOrStringObjectUse:
-            m_result = true;
-            break;
-            
-        default:
-            break;
-        }
-    }
-    
-    bool result() const { return m_result; }
-    
-private:
-    bool m_result;
-};
-
-} // anonymous namespace
-
-ExitMode mayExit(Graph& graph, Node* node)
+template<typename StateType>
+ExitMode mayExitImpl(Graph& graph, Node* node, StateType& state)
 {
     ExitMode result = DoesNotExit;
     
@@ -154,15 +112,68 @@ ExitMode mayExit(Graph& graph, Node* node)
         // If in doubt, return true.
         return Exits;
     }
-
-    EdgeMayExit functor;
-    DFG_NODE_DO_TO_CHILDREN(graph, node, functor);
-    if (functor.result())
-        result = Exits;
     
+    graph.doToChildren(
+        node,
+        [&] (Edge& edge) {
+            if (state) {
+                // Ignore the Check flag on the edge. This is important because that flag answers
+                // the question: "would this edge have had a check if it executed wherever it
+                // currently resides in control flow?" But when a state is passed, we want to ask a
+                // different question: "would this edge have a check if it executed wherever this
+                // state is?" Using the Check flag for this purpose wouldn't even be conservatively
+                // correct. It would be wrong in both directions.
+                if (mayHaveTypeCheck(edge.useKind())
+                    && (state.forNode(edge).m_type & ~typeFilterFor(edge.useKind()))) {
+                    result = Exits;
+                    return;
+                }
+            } else {
+                // FIXME: Maybe this should call mayHaveTypeCheck(edge.useKind()) instead.
+                // https://bugs.webkit.org/show_bug.cgi?id=148545
+                if (edge.willHaveCheck()) {
+                    result = Exits;
+                    return;
+                }
+            }
+            
+            switch (edge.useKind()) {
+            // These are shady because nodes that have these use kinds will typically exit for
+            // unrelated reasons. For example CompareEq doesn't usually exit, but if it uses
+            // ObjectUse then it will.
+            case ObjectUse:
+            case ObjectOrOtherUse:
+                result = Exits;
+                break;
+                
+            // These are shady because they check the structure even if the type of the child node
+            // passes the StringObject type filter.
+            case StringObjectUse:
+            case StringOrStringObjectUse:
+                result = Exits;
+                break;
+                
+            default:
+                break;
+            }
+        });
+
     return result;
 }
 
+} // anonymous namespace
+
+ExitMode mayExit(Graph& graph, Node* node)
+{
+    NullAbstractState state;
+    return mayExitImpl(graph, node, state);
+}
+
+ExitMode mayExit(Graph& graph, Node* node, AtTailAbstractState& state)
+{
+    return mayExitImpl(graph, node, state);
+}
+
 } } // namespace JSC::DFG
 
 namespace WTF {
index 7cece0d..cd139cf 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -30,6 +30,7 @@
 
 namespace JSC { namespace DFG {
 
+class AtTailAbstractState;
 class Graph;
 struct Node;
 
@@ -74,6 +75,11 @@ enum ExitMode {
 
 ExitMode mayExit(Graph&, Node*);
 
+// Like mayExit(), but instead of using the Check: flag to determine if something exits, it
+// evaluates whether it will exit based on the tail state. This is useful for LICM. This *may* also
+// use the AtTailAbstractState to return more precise answers for other nodes.
+ExitMode mayExit(Graph&, Node*, AtTailAbstractState&);
+
 } } // namespace JSC::DFG
 
 namespace WTF {
index 865d52b..fdefbaa 100644 (file)
@@ -2299,7 +2299,7 @@ struct Node {
 
 private:
     unsigned m_op : 10; // real type is NodeType
-    unsigned m_flags : 22;
+    unsigned m_flags : 20;
     // The virtual register number (spill location) associated with this .
     VirtualRegister m_virtualRegister;
     // The number of uses of the result of this operation (+1 for 'must generate' nodes, which have side-effects).
index 5c086d7..94b6715 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -32,7 +32,7 @@ namespace JSC { namespace DFG {
 
 void NodeOrigin::dump(PrintStream& out) const
 {
-    out.print("{semantic: ", semantic, ", forExit: ", forExit, ", exitOK: ", exitOK, "}");
+    out.print("{semantic: ", semantic, ", forExit: ", forExit, ", exitOK: ", exitOK, ", wasHoisted: ", wasHoisted, "}");
 }
 
 } } // namespace JSC::DFG
index 6697a76..d77aa32 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -92,6 +92,13 @@ struct NodeOrigin {
         return withExitOK(exitOK & std::exchange(canExit, false));
     }
     
+    NodeOrigin withWasHoisted() const
+    {
+        NodeOrigin result = *this;
+        result.wasHoisted = true;
+        return result;
+    }
+    
     NodeOrigin forInsertingAfter(Graph& graph, Node* node) const
     {
         NodeOrigin result = *this;
@@ -121,6 +128,8 @@ struct NodeOrigin {
     CodeOrigin forExit;
     // Whether or not it is legal to exit here.
     bool exitOK { false };
+    // Whether or not the node has been hoisted.
+    bool wasHoisted { false };
 };
 
 } } // namespace JSC::DFG
diff --git a/Source/JavaScriptCore/dfg/DFGNullAbstractState.h b/Source/JavaScriptCore/dfg/DFGNullAbstractState.h
new file mode 100644 (file)
index 0000000..03fd884
--- /dev/null
@@ -0,0 +1,66 @@
+/*
+ * Copyright (C) 2016 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 DFGNullAbstractState_h
+#define DFGNullAbstractState_h
+
+#if ENABLE(DFG_JIT)
+
+namespace JSC { namespace DFG {
+
+class Edge;
+struct AbstractValue;
+struct Node;
+
+// Use this as a stub for things that can optionally take some kind of abstract state but you wish
+// to not pass any abstract state. This works if the templatized code also does a check (using the
+// operator bool) to see if the state is valid.
+class NullAbstractState {
+    WTF_MAKE_FAST_ALLOCATED;
+public:
+    NullAbstractState() { }
+    
+    explicit operator bool() const { return false; }
+    
+    AbstractValue& forNode(Node*)
+    {
+        RELEASE_ASSERT_NOT_REACHED();
+        return *bitwise_cast<AbstractValue*>(static_cast<intptr_t>(0x1234));
+    }
+    
+    AbstractValue& forNode(Edge)
+    {
+        return forNode(nullptr);
+    }
+    
+    // It's valid to add more stub methods here as needed.
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGNullAbstractState_h
+
index b95d409..c4efa4f 100644 (file)
@@ -37,7 +37,7 @@
 namespace JSC { namespace DFG {
 
 OSRExit::OSRExit(ExitKind kind, JSValueSource jsValueSource, MethodOfGettingAValueProfile valueProfile, SpeculativeJIT* jit, unsigned streamIndex, unsigned recoveryIndex)
-    : OSRExitBase(kind, jit->m_origin.forExit, jit->m_origin.semantic)
+    : OSRExitBase(kind, jit->m_origin.forExit, jit->m_origin.semantic, jit->m_origin.wasHoisted)
     , m_jsValueSource(jsValueSource)
     , m_valueProfile(valueProfile)
     , m_patchableCodeOffset(0)
index 0197f2c..7bd5f04 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2013, 2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -41,8 +41,14 @@ void OSRExitBase::considerAddingAsFrequentExitSiteSlow(CodeBlock* profiledCodeBl
     CodeBlock* sourceProfiledCodeBlock =
         baselineCodeBlockForOriginAndBaselineCodeBlock(
             m_codeOriginForExitProfile, profiledCodeBlock);
-    if (sourceProfiledCodeBlock)
-        sourceProfiledCodeBlock->addFrequentExitSite(FrequentExitSite(m_codeOriginForExitProfile.bytecodeIndex, m_kind, jitType));
+    if (sourceProfiledCodeBlock) {
+        FrequentExitSite site;
+        if (m_wasHoisted)
+            site = FrequentExitSite(HoistingFailed, jitType);
+        else
+            site = FrequentExitSite(m_codeOriginForExitProfile.bytecodeIndex, m_kind, jitType);
+        sourceProfiledCodeBlock->addFrequentExitSite(site);
+    }
 }
 
 } } // namespace JSC::DFG
index 78510c1..465acf0 100644 (file)
@@ -40,9 +40,10 @@ struct Node;
 // and the FTL.
 
 struct OSRExitBase {
-    OSRExitBase(ExitKind kind, CodeOrigin origin, CodeOrigin originForProfile)
+    OSRExitBase(ExitKind kind, CodeOrigin origin, CodeOrigin originForProfile, bool wasHoisted)
         : m_kind(kind)
         , m_count(0)
+        , m_wasHoisted(wasHoisted)
         , m_codeOrigin(origin)
         , m_codeOriginForExitProfile(originForProfile)
     {
@@ -52,6 +53,7 @@ struct OSRExitBase {
     
     ExitKind m_kind;
     uint32_t m_count;
+    bool m_wasHoisted;
     
     CodeOrigin m_codeOrigin;
     CodeOrigin m_codeOriginForExitProfile;
index 3366c72..23df296 100644 (file)
@@ -88,7 +88,7 @@ public:
     bool run()
     {
         ASSERT(m_graph.m_form == ThreadedCPS);
-
+        
         clearVariableVotes();
         identifyRedundantStructureChecks();
         disableHoistingForVariablesWithInsufficientVotes<StructureTypeCheck>();
index a9cd3b9..d7b7838 100644 (file)
@@ -92,7 +92,7 @@ RefPtr<OSRExitHandle> OSRExitDescriptor::prepareOSRExitHandle(
 {
     unsigned index = state.jitCode->osrExit.size();
     OSRExit& exit = state.jitCode->osrExit.alloc(
-        this, exitKind, nodeOrigin.forExit, nodeOrigin.semantic);
+        this, exitKind, nodeOrigin.forExit, nodeOrigin.semantic, nodeOrigin.wasHoisted);
     RefPtr<OSRExitHandle> handle = adoptRef(new OSRExitHandle(index, exit));
     for (unsigned i = offset; i < params.size(); ++i)
         exit.m_valueReps.append(params[i]);
@@ -101,9 +101,9 @@ RefPtr<OSRExitHandle> OSRExitDescriptor::prepareOSRExitHandle(
 }
 
 OSRExit::OSRExit(
-    OSRExitDescriptor* descriptor,
-    ExitKind exitKind, CodeOrigin codeOrigin, CodeOrigin codeOriginForExitProfile)
-    : OSRExitBase(exitKind, codeOrigin, codeOriginForExitProfile)
+    OSRExitDescriptor* descriptor, ExitKind exitKind, CodeOrigin codeOrigin,
+    CodeOrigin codeOriginForExitProfile, bool wasHoisted)
+    : OSRExitBase(exitKind, codeOrigin, codeOriginForExitProfile, wasHoisted)
     , m_descriptor(descriptor)
 {
 }
index 903527a..f6989ce 100644 (file)
@@ -117,10 +117,7 @@ private:
 };
 
 struct OSRExit : public DFG::OSRExitBase {
-    OSRExit(
-        OSRExitDescriptor*, ExitKind,
-        CodeOrigin, CodeOrigin codeOriginForExitProfile
-        );
+    OSRExit(OSRExitDescriptor*, ExitKind, CodeOrigin, CodeOrigin codeOriginForExitProfile, bool wasHoisted);
 
     OSRExitDescriptor* m_descriptor;
     MacroAssemblerCodeRef m_code;
index bcead2c..16fe234 100644 (file)
@@ -1,3 +1,61 @@
+2016-05-18  Filip Pizlo  <fpizlo@apple.com>
+
+        DFG::LICMPhase shouldn't hoist type checks unless it knows that the check will succeed at the loop pre-header
+        https://bugs.webkit.org/show_bug.cgi?id=144527
+
+        Reviewed by Saam Barati.
+        
+        This adds an adaptor for graphs called BackwardsGraph. The WTF graph framework is based on
+        passing around a Graph template argument that follows the protocol shared by DFG::CFG,
+        B3::CFG, and Air::CFG. These graphs always have a single root node but may have many leaf
+        nodes. This new BackwardsGraph adaptor reverses the graph by creating a synthetic return
+        node that it uses as the root in the inverted graph. This currently may resort to some
+        heuristics in programs that have an infinite loop, but other than that, it'll work well in
+        the general case.
+        
+        This allows us to say Dominators<BackwardsGraph<some graph type>> as a way of computing
+        backwards dominators, which then allows us to easily answer control flow equivalence
+        queries.
+
+        * CMakeLists.txt:
+        * WTF.xcodeproj/project.pbxproj:
+        * wtf/BackwardsGraph.h: Added.
+        (WTF::BackwardsGraph::Node::Node):
+        (WTF::BackwardsGraph::Node::root):
+        (WTF::BackwardsGraph::Node::operator==):
+        (WTF::BackwardsGraph::Node::operator!=):
+        (WTF::BackwardsGraph::Node::operator bool):
+        (WTF::BackwardsGraph::Node::isRoot):
+        (WTF::BackwardsGraph::Node::node):
+        (WTF::BackwardsGraph::Set::Set):
+        (WTF::BackwardsGraph::Set::add):
+        (WTF::BackwardsGraph::Set::remove):
+        (WTF::BackwardsGraph::Set::contains):
+        (WTF::BackwardsGraph::Set::dump):
+        (WTF::BackwardsGraph::Map::Map):
+        (WTF::BackwardsGraph::Map::clear):
+        (WTF::BackwardsGraph::Map::size):
+        (WTF::BackwardsGraph::Map::operator[]):
+        (WTF::BackwardsGraph::BackwardsGraph):
+        (WTF::BackwardsGraph::root):
+        (WTF::BackwardsGraph::newMap):
+        (WTF::BackwardsGraph::successors):
+        (WTF::BackwardsGraph::predecessors):
+        (WTF::BackwardsGraph::index):
+        (WTF::BackwardsGraph::node):
+        (WTF::BackwardsGraph::numNodes):
+        (WTF::BackwardsGraph::dump):
+        * wtf/Dominators.h:
+        (WTF::Dominators::Dominators):
+        (WTF::Dominators::dump):
+        (WTF::Dominators::LengauerTarjan::computeDepthFirstPreNumbering):
+        * wtf/GraphNodeWorklist.h:
+        (WTF::GraphNodeWith::GraphNodeWith):
+        (WTF::GraphNodeWith::operator bool):
+        * wtf/StdLibExtras.h:
+        (WTF::callStatelessLambda):
+        (WTF::checkAndSet):
+
 2016-05-18  Saam barati  <sbarati@apple.com>
 
         StringBuilder::appendQuotedJSONString doesn't properly protect against the math it's doing. Make the math fit the assertion.
index 69050ae..67bc4de 100644 (file)
                CD5497AD15857D0300B5BC30 /* MediaTime.h in Headers */ = {isa = PBXBuildFile; fileRef = CD5497AB15857D0300B5BC30 /* MediaTime.h */; };
                CE46516E19DB1FB4003ECA05 /* NSMapTableSPI.h in Headers */ = {isa = PBXBuildFile; fileRef = CE46516D19DB1FB4003ECA05 /* NSMapTableSPI.h */; };
                CE73E02519DCB7AB00580D5C /* XPCSPI.h in Headers */ = {isa = PBXBuildFile; fileRef = CE73E02419DCB7AB00580D5C /* XPCSPI.h */; };
+               DCEE22051CEB9869000C2396 /* BackwardsGraph.h in Headers */ = {isa = PBXBuildFile; fileRef = DCEE22041CEB9869000C2396 /* BackwardsGraph.h */; };
                DCEE21FB1CEA7538000C2396 /* CFBundleSPI.h in Headers */ = {isa = PBXBuildFile; fileRef = DCEE21FA1CEA7538000C2396 /* CFBundleSPI.h */; };
                DCEE22001CEA7551000C2396 /* BlockObjCExceptions.h in Headers */ = {isa = PBXBuildFile; fileRef = DCEE21FC1CEA7551000C2396 /* BlockObjCExceptions.h */; };
                DCEE22011CEA7551000C2396 /* BlockObjCExceptions.mm in Sources */ = {isa = PBXBuildFile; fileRef = DCEE21FD1CEA7551000C2396 /* BlockObjCExceptions.mm */; };
                CD5497AB15857D0300B5BC30 /* MediaTime.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = MediaTime.h; sourceTree = "<group>"; };
                CE46516D19DB1FB4003ECA05 /* NSMapTableSPI.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = NSMapTableSPI.h; sourceTree = "<group>"; };
                CE73E02419DCB7AB00580D5C /* XPCSPI.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = XPCSPI.h; sourceTree = "<group>"; };
+               DCEE22041CEB9869000C2396 /* BackwardsGraph.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BackwardsGraph.h; sourceTree = "<group>"; };
                DCEE21FA1CEA7538000C2396 /* CFBundleSPI.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = CFBundleSPI.h; path = cf/CFBundleSPI.h; sourceTree = "<group>"; };
                DCEE21FC1CEA7551000C2396 /* BlockObjCExceptions.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BlockObjCExceptions.h; sourceTree = "<group>"; };
                DCEE21FD1CEA7551000C2396 /* BlockObjCExceptions.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = BlockObjCExceptions.mm; sourceTree = "<group>"; };
                                A8A4725D151A825A004123FF /* Atomics.h */,
                                1469419A16EAB10A0024E146 /* AutodrainedPool.h */,
                                1469419B16EAB10A0024E146 /* AutodrainedPoolMac.mm */,
+                               DCEE22041CEB9869000C2396 /* BackwardsGraph.h */,
                                0FB14E18180FA218009B6B4D /* Bag.h */,
                                0FB14E1A1810E1DA009B6B4D /* BagToHashMap.h */,
                                A8A4725F151A825A004123FF /* Bitmap.h */,
                                A8A47391151A825B004123FF /* BumpPointerAllocator.h in Headers */,
                                EB95E1F0161A72410089A2F5 /* ByteOrder.h in Headers */,
                                A8A473AD151A825B004123FF /* cached-powers.h in Headers */,
+                               DCEE22051CEB9869000C2396 /* BackwardsGraph.h in Headers */,
                                A8A4745E151A825B004123FF /* CharacterNames.h in Headers */,
                                A8A47394151A825B004123FF /* CheckedArithmetic.h in Headers */,
                                A8A47395151A825B004123FF /* CheckedBoolean.h in Headers */,
diff --git a/Source/WTF/wtf/BackwardsGraph.h b/Source/WTF/wtf/BackwardsGraph.h
new file mode 100644 (file)
index 0000000..2c2ca14
--- /dev/null
@@ -0,0 +1,296 @@
+/*
+ * Copyright (C) 2016 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 WTF_BackwardsGraph_h
+#define WTF_BackwardsGraph_h
+
+#include <wtf/FastMalloc.h>
+#include <wtf/GraphNodeWorklist.h>
+#include <wtf/Noncopyable.h>
+#include <wtf/Optional.h>
+#include <wtf/StdLibExtras.h>
+
+namespace WTF {
+
+template<typename Graph>
+class BackwardsGraph {
+    WTF_MAKE_NONCOPYABLE(BackwardsGraph);
+    WTF_MAKE_FAST_ALLOCATED;
+public:
+    // We use "#end" to refer to the synthetic root we have created.
+    static const char* rootName = "#end";
+
+    class Node {
+    public:
+        Node(typename Graph::Node node = typename Graph::Node())
+            : m_node(node)
+        {
+        }
+
+        static Node root()
+        {
+            Node result;
+            result.m_node = 0;
+            result.m_isRoot = true;
+            return result;
+        }
+
+        bool operator==(const Node& other) const
+        {
+            return m_node == other.m_node
+                && m_isRoot == other.m_isRoot;
+        }
+
+        bool operator!=(const Node& other) const
+        {
+            return !(*this == other);
+        }
+
+        explicit operator bool() const { return *this != Node(); }
+
+        bool isRoot() const
+        {
+            return m_isRoot;
+        }
+
+        typename Graph::Node node() const { return m_node; }
+
+    private:
+        typename Graph::Node m_node;
+        bool m_isRoot { false };
+    };
+
+    class Set {
+    public:
+        Set()
+        {
+        }
+        
+        bool add(const Node& node)
+        {
+            if (node.isRoot())
+                return checkAndSet(m_hasRoot, true);
+            return m_set.add(node.node());
+        }
+
+        bool remove(const Node& node)
+        {
+            if (node.isRoot())
+                return checkAndSet(m_hasRoot, false);
+            return m_set.remove(node.node());
+        }
+
+        bool contains(const Node& node)
+        {
+            if (node.isRoot())
+                return m_hasRoot;
+            return m_set.contains(node.node());
+        }
+
+        void dump(PrintStream& out) const
+        {
+            if (m_hasRoot)
+                out.print(rootName, " ");
+            out.print(m_set);
+        }
+        
+    private:
+        typename Graph::Set m_set;
+        bool m_hasRoot { false };
+    };
+
+    template<typename T>
+    class Map {
+    public:
+        Map(Graph& graph)
+            : m_map(graph.template newMap<T>())
+        {
+        }
+
+        void clear()
+        {
+            m_map.clear();
+            m_root = T();
+        }
+
+        size_t size() const { return m_map.size() + 1; }
+
+        T& operator[](size_t index)
+        {
+            if (!index)
+                return m_root;
+            return m_map[index - 1];
+        }
+
+        const T& operator[](size_t index) const
+        {
+            return (*const_cast<Map*>(this))[index];
+        }
+
+        T& operator[](const Node& node)
+        {
+            if (node.isRoot())
+                return m_root;
+            return m_map[node.node()];
+        }
+
+        const T& operator[](const Node& node) const
+        {
+            return (*const_cast<Map*>(this))[node];
+        }
+        
+    private:
+        typename Graph::template Map<T> m_map;
+        T m_root;
+    };
+
+    typedef Vector<Node, 4> List;
+
+    BackwardsGraph(Graph& graph)
+        : m_graph(graph)
+    {
+        GraphNodeWorklist<typename Graph::Node, typename Graph::Set> worklist;
+
+        auto addRootSuccessor = [&] (typename Graph::Node node) {
+            if (worklist.push(node)) {
+                m_rootSuccessorList.append(node);
+                m_rootSuccessorSet.add(node);
+                while (typename Graph::Node node = worklist.pop())
+                    worklist.pushAll(graph.predecessors(node));
+            }
+        };
+
+        for (unsigned i = 0; i < graph.numNodes(); ++i) {
+            if (typename Graph::Node node = graph.node(i)) {
+                if (!graph.successors(node).size())
+                    addRootSuccessor(node);
+            }
+        }
+
+        // At this point there will be some nodes in the graph that aren't known to the worklist. We
+        // could add any or all of them to the root successors list. Adding all of them would be a bad
+        // pessimisation. Ideally we would pick the ones that have backward edges but no forward
+        // edges. That would require thinking, so we just use a rough heuristic: add the highest
+        // numbered nodes first, which is totally fine if the input program is already sorted nicely.
+        for (unsigned i = graph.numNodes(); i--;) {
+            if (typename Graph::Node node = graph.node(i))
+                addRootSuccessor(node);
+        }
+    }
+
+    Node root() { return Node::root(); }
+
+    template<typename T>
+    Map<T> newMap() { return Map<T>(m_graph); }
+
+    List successors(const Node& node) const
+    {
+        if (node.isRoot())
+            return m_rootSuccessorList;
+        List result;
+        for (typename Graph::Node predecessor : m_graph.predecessors(node.node()))
+            result.append(predecessor);
+        return result;
+    }
+
+    List predecessors(const Node& node) const
+    {
+        if (node.isRoot())
+            return { };
+
+        List result;
+        
+        if (m_rootSuccessorSet.contains(node.node()))
+            result.append(Node::root());
+
+        for (typename Graph::Node successor : m_graph.successors(node.node()))
+            result.append(successor);
+
+        return result;
+    }
+
+    unsigned index(const Node& node) const
+    {
+        if (node.isRoot())
+            return 0;
+        return m_graph.index(node.node()) + 1;
+    }
+
+    Node node(unsigned index) const
+    {
+        if (!index)
+            return Node::root();
+        return m_graph.node(index - 1);
+    }
+
+    unsigned numNodes() const
+    {
+        return m_graph.numNodes() + 1;
+    }
+
+    CString dump(Node node) const
+    {
+        StringPrintStream out;
+        if (!node)
+            out.print("<null>");
+        else if (node.isRoot())
+            out.print(rootName);
+        else
+            out.print(m_graph.dump(node.node()));
+        return out.toCString();
+    }
+
+    void dump(PrintStream& out) const
+    {
+        for (unsigned i = 0; i < numNodes(); ++i) {
+            Node node = this->node(i);
+            if (!node)
+                continue;
+            out.print(dump(node), ":\n");
+            out.print("    Preds: ");
+            CommaPrinter comma;
+            for (Node predecessor : predecessors(node))
+                out.print(comma, dump(predecessor));
+            out.print("\n");
+            out.print("    Succs: ");
+            comma = CommaPrinter();
+            for (Node successor : successors(node))
+                out.print(comma, dump(successor));
+            out.print("\n");
+        }
+    }
+
+private:
+    Graph& m_graph;
+    List m_rootSuccessorList;
+    typename Graph::Set m_rootSuccessorSet;
+};
+
+} // namespace WTF
+
+using WTF::BackwardsGraph;
+
+#endif // WTF_BackwardsGraph_h
+
index 2ef0542..af91395 100644 (file)
@@ -2,6 +2,7 @@ set(WTF_HEADERS
     ASCIICType.h
     Assertions.h
     Atomics.h
+    BackwardsGraph.h
     Bag.h
     BagToHashMap.h
     BitVector.h
index e613d40..386b3c4 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2011, 2014, 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2011, 2014-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -41,6 +41,7 @@ class Dominators {
 public:
     Dominators(Graph& graph, bool selfCheck = false)
         : m_graph(graph)
+        , m_data(graph.template newMap<BlockData>())
     {
         LengauerTarjan lengauerTarjan(m_graph);
         lengauerTarjan.compute();
@@ -67,7 +68,7 @@ public:
     
         // Plain stack-based worklist because we are guaranteed to see each block exactly once anyway.
         Vector<GraphNodeWithOrder<typename Graph::Node>> worklist;
-        worklist.append(GraphNodeWithOrder<typename Graph::Node>(m_graph.node(0), GraphVisitOrder::Pre));
+        worklist.append(GraphNodeWithOrder<typename Graph::Node>(m_graph.root(), GraphVisitOrder::Pre));
         while (!worklist.isEmpty()) {
             GraphNodeWithOrder<typename Graph::Node> item = worklist.takeLast();
             switch (item.order) {
@@ -279,10 +280,10 @@ public:
             if (m_data[blockIndex].preNumber == UINT_MAX)
                 continue;
             
-            out.print("    Block #", blockIndex, ": idom = ", pointerDump(m_data[blockIndex].idomParent), ", idomKids = [");
+            out.print("    Block #", blockIndex, ": idom = ", m_graph.dump(m_data[blockIndex].idomParent), ", idomKids = [");
             CommaPrinter comma;
             for (unsigned i = 0; i < m_data[blockIndex].idomKids.size(); ++i)
-                out.print(comma, *m_data[blockIndex].idomKids[i]);
+                out.print(comma, m_graph.dump(m_data[blockIndex].idomKids[i]));
             out.print("], pre/post = ", m_data[blockIndex].preNumber, "/", m_data[blockIndex].postNumber, "\n");
         }
     }
@@ -347,7 +348,7 @@ private:
             // of not noticing A->C until we're done processing B.
 
             ExtendedGraphNodeWorklist<typename Graph::Node, unsigned, typename Graph::Set> worklist;
-            worklist.push(m_graph.node(0), 0);
+            worklist.push(m_graph.root(), 0);
         
             while (GraphNodeWith<typename Graph::Node, unsigned> item = worklist.pop()) {
                 typename Graph::Node block = item.node;
index b5f2dba..d4f7137 100644 (file)
@@ -83,7 +83,7 @@ struct GraphNodeWith {
     {
     }
 
-    explicit operator bool() const { return node; }
+    explicit operator bool() const { return !!node; }
     
     Node node;
     T data;
index 9eb373b..b120c26 100644 (file)
@@ -299,6 +299,15 @@ ResultType callStatelessLambda(ArgumentTypes&&... arguments)
     return (*bitwise_cast<Func*>(data))(std::forward<ArgumentTypes>(arguments)...);
 }
 
+template<typename T, typename U>
+bool checkAndSet(T& left, U right)
+{
+    if (left == right)
+        return false;
+    left = right;
+    return true;
+}
+
 } // namespace WTF
 
 // This version of placement new omits a 0 check.
@@ -409,17 +418,18 @@ ALWAYS_INLINE constexpr typename remove_reference<T>::type&& move(T&& value)
 
 using WTF::KB;
 using WTF::MB;
-using WTF::isCompilationThread;
+using WTF::approximateBinarySearch;
+using WTF::binarySearch;
+using WTF::bitwise_cast;
+using WTF::callStatelessLambda;
+using WTF::checkAndSet;
 using WTF::insertIntoBoundedVector;
+using WTF::isCompilationThread;
 using WTF::isPointerAligned;
+using WTF::isStatelessLambda;
 using WTF::is8ByteAligned;
-using WTF::binarySearch;
-using WTF::tryBinarySearch;
-using WTF::approximateBinarySearch;
-using WTF::bitwise_cast;
 using WTF::safeCast;
-using WTF::isStatelessLambda;
-using WTF::callStatelessLambda;
+using WTF::tryBinarySearch;
 
 #if COMPILER_SUPPORTS(CXX_USER_LITERALS)
 // We normally don't want to bring in entire std namespaces, but literals are an exception.