FTL should sink PutLocals
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 4 Oct 2014 17:18:25 +0000 (17:18 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 4 Oct 2014 17:18:25 +0000 (17:18 +0000)
https://bugs.webkit.org/show_bug.cgi?id=137168

Reviewed by Oliver Hunt.
Source/JavaScriptCore:

We've known for a while that our PutLocal situation was sub-optimal. We emit them anytime we
"pass" arguments to an inlined function call, because we need to enable the runtime to grab
those arguments when doing foo.arguments where foo is inlined: our engine doesn't deoptimize
in that case but rather just relies on the arguments being flushed (i.e. a copy of their
values is spilled) at a well-known place in a well-known format.

The PutLocals incur two costs: (1) they are store instructions and stores ain't free, and (2)
they look like escaping sites and so they inhibit object allocation sinking.

But in most cases, the PutLocals are unnecessary because the inlined code never performs any
side effect that could transitively lead to function.arguments. Even if the inlined code
could do such a side effect, it may be on a rare path so there is no need to penalize the
entire function.

This patch implements one solution to the PutLocal problem: it aggressively sinks PutLocals
to the latest possible point. This is even more aggressive than the object allocation
sinking. That sinking algorithm avoids creating situations where an object could be
materialized more than one along any path. PutLocal sinking, on the other hand, doesn't avoid
this at all - both to make the phase cheaper and simpler and to make it more aggressive.
Every PutLocal is sunk no matter what.

The upside of this patch is that it eliminates many PutLocals: many of them are sunk "past
their death", thus eliminating them completely. Others are sunk to rare paths. This enables a
lot of object allocation sinking and it removes a lot of pointless store instructions.

It also has downsites. Sinking PutLocals increases register pressure because it increases the
live ranges of things like inlined arguments.

This patch is a net performance win in its current form: 1% SunSpider regression, 2% OctaneV2
progression, 0.6% Kraken regression, 1% AsmBench progression, and 0.5% CompressionBench
regression. The biggest win is on Octane/raytrace, which improves by 27%.

Relanding after fixing internal builds. We have to be careful about implicit casts from int64
to int32.

* CMakeLists.txt:
* JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
* JavaScriptCore.xcodeproj/project.pbxproj:
* bytecode/CodeBlock.h:
* bytecode/Operands.h:
(JSC::Operands::dump): Deleted.
* bytecode/OperandsInlines.h:
(JSC::Traits>::dump):
* bytecode/VirtualRegister.h:
(JSC::VirtualRegister::isHeader):
* dfg/DFGByteCodeParser.cpp:
(JSC::DFG::ByteCodeParser::InlineStackEntry::InlineStackEntry):
* dfg/DFGClobberSet.h:
(JSC::DFG::ClobberSetAdd::operator()):
(JSC::DFG::ClobberSetOverlaps::operator()):
* dfg/DFGClobberize.h:
(JSC::DFG::clobberize):
(JSC::DFG::NoOpClobberize::operator()):
(JSC::DFG::CheckClobberize::operator()):
(JSC::DFG::AbstractHeapOverlaps::operator()):
(JSC::DFG::ReadMethodClobberize::operator()):
(JSC::DFG::WriteMethodClobberize::operator()):
(JSC::DFG::DefMethodClobberize::operator()):
* dfg/DFGFlushFormat.h:
(JSC::DFG::merge):
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::Graph):
* dfg/DFGGraph.h:
(JSC::DFG::Graph::capturedVarsFor):
* dfg/DFGObjectAllocationSinkingPhase.cpp:
(JSC::DFG::ObjectAllocationSinkingPhase::determineMaterializationPoints):
(JSC::DFG::ObjectAllocationSinkingPhase::placeMaterializationPoints):
* dfg/DFGPlan.cpp:
(JSC::DFG::Plan::compileInThreadImpl):
* dfg/DFGPreciseLocalClobberize.h: Added.
(JSC::DFG::PreciseLocalClobberizeAdaptor::PreciseLocalClobberizeAdaptor):
(JSC::DFG::PreciseLocalClobberizeAdaptor::read):
(JSC::DFG::PreciseLocalClobberizeAdaptor::write):
(JSC::DFG::PreciseLocalClobberizeAdaptor::def):
(JSC::DFG::PreciseLocalClobberizeAdaptor::callIfAppropriate):
(JSC::DFG::PreciseLocalClobberizeAdaptor::readTop):
(JSC::DFG::PreciseLocalClobberizeAdaptor::writeTop):
(JSC::DFG::forEachLocalReadByUnwind):
(JSC::DFG::preciseLocalClobberize):
* dfg/DFGPutLocalSinkingPhase.cpp: Added.
(JSC::DFG::performPutLocalSinking):
* dfg/DFGPutLocalSinkingPhase.h: Added.
* dfg/DFGSSACalculator.h:
(JSC::DFG::SSACalculator::computePhis):
* dfg/DFGValidate.cpp:

Source/WTF:

Make the set bits of a BitVector iterable.

* wtf/BitVector.h:
(WTF::BitVector::SetBitsIterable::SetBitsIterable):
(WTF::BitVector::SetBitsIterable::iterator::iterator):
(WTF::BitVector::SetBitsIterable::iterator::operator*):
(WTF::BitVector::SetBitsIterable::iterator::operator++):
(WTF::BitVector::SetBitsIterable::iterator::operator==):
(WTF::BitVector::SetBitsIterable::iterator::operator!=):
(WTF::BitVector::SetBitsIterable::begin):
(WTF::BitVector::SetBitsIterable::end):
(WTF::BitVector::setBits):

LayoutTests:

* js/regress/elidable-new-object-then-call-expected.txt: Added.
* js/regress/elidable-new-object-then-call.html: Added.
* js/regress/script-tests/elidable-new-object-then-call.js: Added.
(sumOfArithSeries):
(bar):
(foo):

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

30 files changed:
LayoutTests/ChangeLog
LayoutTests/js/regress/elidable-new-object-then-call-expected.txt [new file with mode: 0644]
LayoutTests/js/regress/elidable-new-object-then-call.html [new file with mode: 0644]
LayoutTests/js/regress/script-tests/elidable-new-object-then-call.js [new file with mode: 0644]
Source/JavaScriptCore/CMakeLists.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/bytecode/CodeBlock.h
Source/JavaScriptCore/bytecode/Operands.h
Source/JavaScriptCore/bytecode/OperandsInlines.h
Source/JavaScriptCore/bytecode/VirtualRegister.h
Source/JavaScriptCore/dfg/DFGAbstractHeap.h
Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp
Source/JavaScriptCore/dfg/DFGClobberSet.h
Source/JavaScriptCore/dfg/DFGClobberize.h
Source/JavaScriptCore/dfg/DFGFlushFormat.h
Source/JavaScriptCore/dfg/DFGGraph.cpp
Source/JavaScriptCore/dfg/DFGGraph.h
Source/JavaScriptCore/dfg/DFGMayExit.cpp
Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp
Source/JavaScriptCore/dfg/DFGPlan.cpp
Source/JavaScriptCore/dfg/DFGPreciseLocalClobberize.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGPutLocalSinkingPhase.cpp [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGPutLocalSinkingPhase.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGSSACalculator.h
Source/JavaScriptCore/dfg/DFGValidate.cpp
Source/WTF/ChangeLog
Source/WTF/wtf/BitVector.h

index f41aa597cb50b214951c02eae72d286636c39858..6809231591bc01742af197726ca70faa3b328a22 100644 (file)
@@ -1,3 +1,17 @@
+2014-10-04  Filip Pizlo  <fpizlo@apple.com>
+
+        FTL should sink PutLocals
+        https://bugs.webkit.org/show_bug.cgi?id=137168
+
+        Reviewed by Oliver Hunt.
+
+        * js/regress/elidable-new-object-then-call-expected.txt: Added.
+        * js/regress/elidable-new-object-then-call.html: Added.
+        * js/regress/script-tests/elidable-new-object-then-call.js: Added.
+        (sumOfArithSeries):
+        (bar):
+        (foo):
+
 2014-10-04  Tim Horton  <timothy_horton@apple.com>
 
         Make it possible to test page overlays
diff --git a/LayoutTests/js/regress/elidable-new-object-then-call-expected.txt b/LayoutTests/js/regress/elidable-new-object-then-call-expected.txt
new file mode 100644 (file)
index 0000000..70244c4
--- /dev/null
@@ -0,0 +1,10 @@
+JSRegress/elidable-new-object-then-call
+
+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/elidable-new-object-then-call.html b/LayoutTests/js/regress/elidable-new-object-then-call.html
new file mode 100644 (file)
index 0000000..946704d
--- /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/elidable-new-object-then-call.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/elidable-new-object-then-call.js b/LayoutTests/js/regress/script-tests/elidable-new-object-then-call.js
new file mode 100644 (file)
index 0000000..496c2a1
--- /dev/null
@@ -0,0 +1,28 @@
+function sumOfArithSeries(limit) {
+    return limit * (limit + 1) / 2;
+}
+
+var n = 10000000;
+
+function bar(p, o) {
+    if (p)
+        return 5;
+    else
+        return 6;
+}
+
+function foo() {
+    var result = 0;
+    for (var i = 0; i < n; ++i) {
+        var o = {f: i};
+        var p = {f: i + 1};
+        bar(i, o);
+        bar(i, p);
+        result += o.f + p.f;
+    }
+    return result;
+}
+
+var result = foo();
+if (result != sumOfArithSeries(n - 1) + sumOfArithSeries(n))
+    throw "Error: bad result: " + result;
index 2f72c2e4299b1ef747e20b3d383889c61afb29e8..8bc54d0dd090f29e2720094fece156448298001b 100644 (file)
@@ -207,6 +207,7 @@ set(JavaScriptCore_SOURCES
     dfg/DFGPredictionPropagationPhase.cpp
     dfg/DFGPromotedHeapLocation.cpp
     dfg/DFGPureValue.cpp
+    dfg/DFGPutLocalSinkingPhase.cpp
     dfg/DFGResurrectionForValidationPhase.cpp
     dfg/DFGSSACalculator.cpp
     dfg/DFGSSAConversionPhase.cpp
index f213d1f2eb7f64a9e68d5520a61988b30b06161a..5355c9f52837aff13722791568efd4da29b58636 100644 (file)
@@ -1,3 +1,96 @@
+2014-10-04  Filip Pizlo  <fpizlo@apple.com>
+
+        FTL should sink PutLocals
+        https://bugs.webkit.org/show_bug.cgi?id=137168
+
+        Reviewed by Oliver Hunt.
+        
+        We've known for a while that our PutLocal situation was sub-optimal. We emit them anytime we
+        "pass" arguments to an inlined function call, because we need to enable the runtime to grab
+        those arguments when doing foo.arguments where foo is inlined: our engine doesn't deoptimize
+        in that case but rather just relies on the arguments being flushed (i.e. a copy of their
+        values is spilled) at a well-known place in a well-known format.
+        
+        The PutLocals incur two costs: (1) they are store instructions and stores ain't free, and (2)
+        they look like escaping sites and so they inhibit object allocation sinking.
+        
+        But in most cases, the PutLocals are unnecessary because the inlined code never performs any
+        side effect that could transitively lead to function.arguments. Even if the inlined code
+        could do such a side effect, it may be on a rare path so there is no need to penalize the
+        entire function.
+        
+        This patch implements one solution to the PutLocal problem: it aggressively sinks PutLocals
+        to the latest possible point. This is even more aggressive than the object allocation
+        sinking. That sinking algorithm avoids creating situations where an object could be
+        materialized more than one along any path. PutLocal sinking, on the other hand, doesn't avoid
+        this at all - both to make the phase cheaper and simpler and to make it more aggressive.
+        Every PutLocal is sunk no matter what.
+        
+        The upside of this patch is that it eliminates many PutLocals: many of them are sunk "past
+        their death", thus eliminating them completely. Others are sunk to rare paths. This enables a
+        lot of object allocation sinking and it removes a lot of pointless store instructions.
+        
+        It also has downsites. Sinking PutLocals increases register pressure because it increases the
+        live ranges of things like inlined arguments.
+        
+        This patch is a net performance win in its current form: 1% SunSpider regression, 2% OctaneV2
+        progression, 0.6% Kraken regression, 1% AsmBench progression, and 0.5% CompressionBench
+        regression. The biggest win is on Octane/raytrace, which improves by 27%.
+        
+        Relanding after fixing internal builds. We have to be careful about implicit casts from int64
+        to int32.
+
+        * CMakeLists.txt:
+        * JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * bytecode/CodeBlock.h:
+        * bytecode/Operands.h:
+        (JSC::Operands::dump): Deleted.
+        * bytecode/OperandsInlines.h:
+        (JSC::Traits>::dump):
+        * bytecode/VirtualRegister.h:
+        (JSC::VirtualRegister::isHeader):
+        * dfg/DFGByteCodeParser.cpp:
+        (JSC::DFG::ByteCodeParser::InlineStackEntry::InlineStackEntry):
+        * dfg/DFGClobberSet.h:
+        (JSC::DFG::ClobberSetAdd::operator()):
+        (JSC::DFG::ClobberSetOverlaps::operator()):
+        * dfg/DFGClobberize.h:
+        (JSC::DFG::clobberize):
+        (JSC::DFG::NoOpClobberize::operator()):
+        (JSC::DFG::CheckClobberize::operator()):
+        (JSC::DFG::AbstractHeapOverlaps::operator()):
+        (JSC::DFG::ReadMethodClobberize::operator()):
+        (JSC::DFG::WriteMethodClobberize::operator()):
+        (JSC::DFG::DefMethodClobberize::operator()):
+        * dfg/DFGFlushFormat.h:
+        (JSC::DFG::merge):
+        * dfg/DFGGraph.cpp:
+        (JSC::DFG::Graph::Graph):
+        * dfg/DFGGraph.h:
+        (JSC::DFG::Graph::capturedVarsFor):
+        * dfg/DFGObjectAllocationSinkingPhase.cpp:
+        (JSC::DFG::ObjectAllocationSinkingPhase::determineMaterializationPoints):
+        (JSC::DFG::ObjectAllocationSinkingPhase::placeMaterializationPoints):
+        * dfg/DFGPlan.cpp:
+        (JSC::DFG::Plan::compileInThreadImpl):
+        * dfg/DFGPreciseLocalClobberize.h: Added.
+        (JSC::DFG::PreciseLocalClobberizeAdaptor::PreciseLocalClobberizeAdaptor):
+        (JSC::DFG::PreciseLocalClobberizeAdaptor::read):
+        (JSC::DFG::PreciseLocalClobberizeAdaptor::write):
+        (JSC::DFG::PreciseLocalClobberizeAdaptor::def):
+        (JSC::DFG::PreciseLocalClobberizeAdaptor::callIfAppropriate):
+        (JSC::DFG::PreciseLocalClobberizeAdaptor::readTop):
+        (JSC::DFG::PreciseLocalClobberizeAdaptor::writeTop):
+        (JSC::DFG::forEachLocalReadByUnwind):
+        (JSC::DFG::preciseLocalClobberize):
+        * dfg/DFGPutLocalSinkingPhase.cpp: Added.
+        (JSC::DFG::performPutLocalSinking):
+        * dfg/DFGPutLocalSinkingPhase.h: Added.
+        * dfg/DFGSSACalculator.h:
+        (JSC::DFG::SSACalculator::computePhis):
+        * dfg/DFGValidate.cpp:
+
 2014-10-03  Michael Saboff  <msaboff@apple.com>
 
         REGRESSION(r174216): CodeBlock::dumpByteCodes crashes on op_push_name_scope
index 79dd7cf7fa77056e786f926ee331b32542a5021a..a8cc452cb5d35cd4007b622733fa2895a7698b11 100644 (file)
     <ClCompile Include="..\dfg\DFGPredictionPropagationPhase.cpp" />
     <ClCompile Include="..\dfg\DFGPromotedHeapLocation.cpp" />
     <ClCompile Include="..\dfg\DFGPureValue.cpp" />
+    <ClCompile Include="..\dfg\DFGPutLocalSinkingPhase.cpp" />
     <ClCompile Include="..\dfg\DFGResurrectionForValidationPhase.cpp" />
     <ClCompile Include="..\dfg\DFGSafepoint.cpp" />
     <ClCompile Include="..\dfg\DFGSpeculativeJIT.cpp" />
     <ClInclude Include="..\dfg\DFGPhiChildren.h" />
     <ClInclude Include="..\dfg\DFGPlan.h" />
     <ClInclude Include="..\dfg\DFGPrePostNumbering.h" />
+    <ClInclude Include="..\dfg\DFGPreciseLocalClobberize.h" />
     <ClInclude Include="..\dfg\DFGPredictionInjectionPhase.h" />
     <ClInclude Include="..\dfg\DFGPredictionPropagationPhase.h" />
     <ClInclude Include="..\dfg\DFGPromoteHeapAccess.h" />
     <ClInclude Include="..\dfg\DFGPromotedHeapLocation.h" />
     <ClInclude Include="..\dfg\DFGPureValue.h" />
+    <ClInclude Include="..\dfg\DFGPutLocalSinkingPhase.h" />
     <ClInclude Include="..\dfg\DFGRegisterBank.h" />
     <ClInclude Include="..\dfg\DFGRegisterSet.h" />
     <ClInclude Include="..\dfg\DFGResurrectionForValidationPhase.h" />
index b31171d5bb752cadde15ac28cafad399f14b6a15..d1c07779e9137d394f162df45e1b245ef5c33157 100644 (file)
                C49FE4AA19AAC83E00F40CE9 /* generate_protocol_types_implementation.py in Resources */ = {isa = PBXBuildFile; fileRef = C49FE4A819AAC83E00F40CE9 /* generate_protocol_types_implementation.py */; };
                C49FE4AB19AAC86100F40CE9 /* generate_protocol_types_header.py in Headers */ = {isa = PBXBuildFile; fileRef = C49FE4A719AAC83E00F40CE9 /* generate_protocol_types_header.py */; settings = {ATTRIBUTES = (Private, ); }; };
                C49FE4AC19AAC86100F40CE9 /* generate_protocol_types_implementation.py in Headers */ = {isa = PBXBuildFile; fileRef = C49FE4A819AAC83E00F40CE9 /* generate_protocol_types_implementation.py */; settings = {ATTRIBUTES = (Private, ); }; };
+               DC00039319D8BE6F00023EB0 /* DFGPreciseLocalClobberize.h in Headers */ = {isa = PBXBuildFile; fileRef = DC00039019D8BE6F00023EB0 /* DFGPreciseLocalClobberize.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               DC00039819DBA70600023EB0 /* DFGPutLocalSinkingPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = DC00039619DBA70600023EB0 /* DFGPutLocalSinkingPhase.cpp */; };
+               DC00039919DBA70600023EB0 /* DFGPutLocalSinkingPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = DC00039719DBA70600023EB0 /* DFGPutLocalSinkingPhase.h */; settings = {ATTRIBUTES = (Private, ); }; };
                E124A8F70E555775003091F1 /* OpaqueJSString.h in Headers */ = {isa = PBXBuildFile; fileRef = E124A8F50E555775003091F1 /* OpaqueJSString.h */; settings = {ATTRIBUTES = (Private, ); }; };
                E124A8F80E555775003091F1 /* OpaqueJSString.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E124A8F60E555775003091F1 /* OpaqueJSString.cpp */; };
                E18E3A590DF9278C00D90B34 /* VM.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E18E3A570DF9278C00D90B34 /* VM.cpp */; };
                C49FE4A819AAC83E00F40CE9 /* generate_protocol_types_implementation.py */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.script.python; path = generate_protocol_types_implementation.py; sourceTree = "<group>"; };
                D21202280AD4310C00ED79B6 /* DateConversion.cpp */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.cpp.cpp; path = DateConversion.cpp; sourceTree = "<group>"; };
                D21202290AD4310C00ED79B6 /* DateConversion.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = DateConversion.h; sourceTree = "<group>"; };
+               DC00039019D8BE6F00023EB0 /* DFGPreciseLocalClobberize.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGPreciseLocalClobberize.h; path = dfg/DFGPreciseLocalClobberize.h; sourceTree = "<group>"; };
+               DC00039619DBA70600023EB0 /* DFGPutLocalSinkingPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGPutLocalSinkingPhase.cpp; path = dfg/DFGPutLocalSinkingPhase.cpp; sourceTree = "<group>"; };
+               DC00039719DBA70600023EB0 /* DFGPutLocalSinkingPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGPutLocalSinkingPhase.h; path = dfg/DFGPutLocalSinkingPhase.h; sourceTree = "<group>"; };
                E124A8F50E555775003091F1 /* OpaqueJSString.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = OpaqueJSString.h; sourceTree = "<group>"; };
                E124A8F60E555775003091F1 /* OpaqueJSString.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = OpaqueJSString.cpp; sourceTree = "<group>"; };
                E178633F0D9BEC0000D74E75 /* InitializeThreading.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = InitializeThreading.h; sourceTree = "<group>"; };
                                0F2B9CDF19D0BA7D00B1D1B5 /* DFGPhiChildren.h */,
                                A78A9772179738B8009DF744 /* DFGPlan.cpp */,
                                A78A9773179738B8009DF744 /* DFGPlan.h */,
+                               DC00039019D8BE6F00023EB0 /* DFGPreciseLocalClobberize.h */,
                                0FBE0F6D16C1DB010082C5E8 /* DFGPredictionInjectionPhase.cpp */,
                                0FBE0F6E16C1DB010082C5E8 /* DFGPredictionInjectionPhase.h */,
                                0FFFC95114EF909500C72532 /* DFGPredictionPropagationPhase.cpp */,
                                0FAA3E0819D0C2CB00FAC9E2 /* DFGPromoteHeapAccess.h */,
                                0FB1765E196B8F9E0091052A /* DFGPureValue.cpp */,
                                0FB1765F196B8F9E0091052A /* DFGPureValue.h */,
+                               DC00039619DBA70600023EB0 /* DFGPutLocalSinkingPhase.cpp */,
+                               DC00039719DBA70600023EB0 /* DFGPutLocalSinkingPhase.h */,
                                86EC9DC11328DF82002B2AD7 /* DFGRegisterBank.h */,
                                0F666ECA1836B37E00D017F1 /* DFGResurrectionForValidationPhase.cpp */,
                                0F666ECB1836B37E00D017F1 /* DFGResurrectionForValidationPhase.h */,
                                0FEA0A08170513DB00BB722C /* FTLAbbreviations.h in Headers */,
                                A53CE08A18BC21C300BEDF76 /* ConsoleClient.h in Headers */,
                                0FEA0A1D1708B00700BB722C /* FTLAbstractHeap.h in Headers */,
+                               DC00039319D8BE6F00023EB0 /* DFGPreciseLocalClobberize.h in Headers */,
                                0FEA0A1F1708B00700BB722C /* FTLAbstractHeapRepository.h in Headers */,
                                0F485328187DFDEC0083B687 /* FTLAvailableRecovery.h in Headers */,
                                0FEA0A0A170513DB00BB722C /* FTLCapabilities.h in Headers */,
                                BC18C4280E16F5CD00B34460 /* JSStringRef.h in Headers */,
                                BC18C4290E16F5CD00B34460 /* JSStringRefCF.h in Headers */,
                                1A28D4A8177B71C80007FA3C /* JSStringRefPrivate.h in Headers */,
+                               DC00039919DBA70600023EB0 /* DFGPutLocalSinkingPhase.h in Headers */,
                                0F919D0D157EE0A2004A4E7D /* JSSymbolTableObject.h in Headers */,
                                BC18C42A0E16F5CD00B34460 /* JSType.h in Headers */,
                                0F2B66FB17B6B5AB00A7AE3F /* JSTypedArrayConstructors.h in Headers */,
                                A7D89CF517A0B8CC00773AD8 /* DFGCriticalEdgeBreakingPhase.cpp in Sources */,
                                0FFFC95914EF90A600C72532 /* DFGCSEPhase.cpp in Sources */,
                                0F2FC77216E12F710038D976 /* DFGDCEPhase.cpp in Sources */,
+                               DC00039819DBA70600023EB0 /* DFGPutLocalSinkingPhase.cpp in Sources */,
                                0F8F2B99172F04FF007DBDA5 /* DFGDesiredIdentifiers.cpp in Sources */,
                                C2C0F7CD17BBFC5B00464FE4 /* DFGDesiredTransitions.cpp in Sources */,
                                0FE8534B1723CDA500B618F5 /* DFGDesiredWatchpoints.cpp in Sources */,
index a86042569f69ea402e100567a6d4f4f357ee26c5..660a5c4e612d795f483c8cd6e88fd599cfb848d6 100644 (file)
@@ -384,7 +384,7 @@ public:
             return 0;
         return symbolTable()->captureEnd();
     }
-
+    
     bool isCaptured(VirtualRegister operand, InlineCallFrame* = 0) const;
     
     int framePointerOffsetToGetActivationRegisters(int machineCaptureStart);
index 92a9564383b71003d14c246aa33dcd130bc34387..168aad9669f75fe66f16cb2b01ddc921384e6de6 100644 (file)
@@ -252,11 +252,7 @@ public:
     }
     
     void dumpInContext(PrintStream& out, DumpContext* context) const;
-    
-    void dump(PrintStream& out) const
-    {
-        dumpInContext(out, 0);
-    }
+    void dump(PrintStream& out) const;
     
 private:
     Vector<T, 8> m_arguments;
index 74ad60bc18a80c4b292f0b08ab1f1e98755bcc90..c9dee88c7a03e400c447e48d841b0c315ecfedf5 100644 (file)
@@ -47,6 +47,22 @@ void Operands<T, Traits>::dumpInContext(PrintStream& out, DumpContext* context)
     }
 }
 
+template<typename T, typename Traits>
+void Operands<T, Traits>::dump(PrintStream& out) const
+{
+    CommaPrinter comma(" ");
+    for (size_t argumentIndex = numberOfArguments(); argumentIndex--;) {
+        if (Traits::isEmptyForDump(argument(argumentIndex)))
+            continue;
+        out.print(comma, "arg", argumentIndex, ":", argument(argumentIndex));
+    }
+    for (size_t localIndex = 0; localIndex < numberOfLocals(); ++localIndex) {
+        if (Traits::isEmptyForDump(local(localIndex)))
+            continue;
+        out.print(comma, "loc", localIndex, ":", local(localIndex));
+    }
+}
+
 } // namespace JSC
 
 #endif // OperandsInlines_h
index 26e525d48bd43e90b9f9b1134982dbf63f74d96c..bca836df1a1f55c3c1cb51bfc8b668bd7fc5d751 100644 (file)
@@ -59,6 +59,7 @@ public:
     bool isValid() const { return (m_virtualRegister != s_invalidVirtualRegister); }
     bool isLocal() const { return operandIsLocal(m_virtualRegister); }
     bool isArgument() const { return operandIsArgument(m_virtualRegister); }
+    bool isHeader() const { return m_virtualRegister >= 0 && m_virtualRegister < JSStack::ThisArgument; }
     bool isConstant() const { return m_virtualRegister >= s_firstConstantRegisterIndex; }
     int toLocal() const { ASSERT(isLocal()); return operandToLocal(m_virtualRegister); }
     int toArgument() const { ASSERT(isArgument()); return operandToArgument(m_virtualRegister); }
index 90b581a232f0b3818c83fb061d252c7c8e4c3091..77b218019b508cdc0cee6ea8c33a3959d5440099 100644 (file)
@@ -127,6 +127,11 @@ public:
             return m_value;
         }
         
+        int32_t value32() const
+        {
+            return static_cast<int32_t>(value());
+        }
+        
         bool operator==(const Payload& other) const
         {
             return m_isTop == other.m_isTop
index c309db3e50ace682fdccb3d9e8e620459f083130..2bd99e202c6dcf6fea7e1c102afe10209ae098c1 100644 (file)
@@ -109,7 +109,7 @@ void AbstractInterpreter<AbstractStateType>::verifyEdge(Node* node, Edge edge)
     if (!(forNode(edge).m_type & ~typeFilterFor(edge.useKind())))
         return;
     
-    DFG_CRASH(m_graph, node, toCString("Edge verification error: ", node, "->", edge, " was expected to have type ", SpeculationDump(typeFilterFor(edge.useKind())), " but has type ", SpeculationDump(forNode(edge).m_type)).data());
+    DFG_CRASH(m_graph, node, toCString("Edge verification error: ", node, "->", edge, " was expected to have type ", SpeculationDump(typeFilterFor(edge.useKind())), " but has type ", SpeculationDump(forNode(edge).m_type), " (", forNode(edge).m_type, ")").data());
 }
 
 template<typename AbstractStateType>
index 27b350a8d714472673f13639a5d46861f1eb1689..2797fd64c9b73bfbeaf9c903800151a322606e84 100644 (file)
@@ -3692,12 +3692,8 @@ ByteCodeParser::InlineStackEntry::InlineStackEntry(
         
         if (m_inlineCallFrame->caller.inlineCallFrame)
             m_inlineCallFrame->capturedVars = m_inlineCallFrame->caller.inlineCallFrame->capturedVars;
-        else {
-            for (int i = byteCodeParser->m_codeBlock->m_numVars; i--;) {
-                if (byteCodeParser->m_codeBlock->isCaptured(virtualRegisterForLocal(i)))
-                    m_inlineCallFrame->capturedVars.set(i);
-            }
-        }
+        else
+            m_inlineCallFrame->capturedVars = byteCodeParser->m_graph.m_outermostCapturedVars;
 
         for (int i = argumentCountIncludingThis; i--;) {
             VirtualRegister argument = virtualRegisterForArgument(i);
index 5dfe495fafee24eb0b66f94b4b53dd3cfc432f20..d76d3559d943613718618ecd9a56e7f9bf2ebda3 100644 (file)
@@ -80,7 +80,7 @@ public:
     {
     }
     
-    void operator()(AbstractHeap heap)
+    void operator()(AbstractHeap heap) const
     {
         m_set.add(heap);
     }
@@ -96,7 +96,7 @@ public:
     {
     }
     
-    void operator()(AbstractHeap heap)
+    void operator()(AbstractHeap heap) const
     {
         m_result |= m_set.overlaps(heap);
     }
@@ -105,7 +105,7 @@ public:
     
 private:
     const ClobberSet& m_set;
-    bool m_result;
+    mutable bool m_result;
 };
 
 void addReads(Graph&, Node*, ClobberSet&);
index aed5c99272380530698f8c5d903fa320e9cac410..ed2042a2f4985a8843f52728c17d50e8adaf061a 100644 (file)
@@ -1,4 +1,4 @@
- /*
+/*
  * Copyright (C) 2013, 2014 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -37,7 +37,7 @@
 namespace JSC { namespace DFG {
 
 template<typename ReadFunctor, typename WriteFunctor, typename DefFunctor>
-void clobberize(Graph& graph, Node* node, ReadFunctor& read, WriteFunctor& write, DefFunctor& def)
+void clobberize(Graph& graph, Node* node, const ReadFunctor& read, const WriteFunctor& write, const DefFunctor& def)
 {
     // Some notes:
     //
@@ -897,7 +897,7 @@ class NoOpClobberize {
 public:
     NoOpClobberize() { }
     template<typename... T>
-    void operator()(T...) { }
+    void operator()(T...) const { }
 };
 
 class CheckClobberize {
@@ -908,12 +908,12 @@ public:
     }
     
     template<typename... T>
-    void operator()(T...) { m_result = true; }
+    void operator()(T...) const { m_result = true; }
     
     bool result() const { return m_result; }
     
 private:
-    bool m_result;
+    mutable bool m_result;
 };
 
 bool doesWrites(Graph&, Node*);
@@ -926,7 +926,7 @@ public:
     {
     }
     
-    void operator()(AbstractHeap otherHeap)
+    void operator()(AbstractHeap otherHeap) const
     {
         if (m_result)
             return;
@@ -937,7 +937,7 @@ public:
 
 private:
     AbstractHeap m_heap;
-    bool m_result;
+    mutable bool m_result;
 };
 
 bool accessesOverlap(Graph&, Node*, AbstractHeap);
@@ -954,7 +954,7 @@ public:
     {
     }
     
-    void operator()(AbstractHeap heap)
+    void operator()(AbstractHeap heap) const
     {
         m_value.read(heap);
     }
@@ -970,7 +970,7 @@ public:
     {
     }
     
-    void operator()(AbstractHeap heap)
+    void operator()(AbstractHeap heap) const
     {
         m_value.write(heap);
     }
@@ -986,12 +986,12 @@ public:
     {
     }
     
-    void operator()(PureValue value)
+    void operator()(PureValue value) const
     {
         m_value.def(value);
     }
     
-    void operator()(HeapLocation location, Node* node)
+    void operator()(HeapLocation location, Node* node) const
     {
         m_value.def(location, node);
     }
index 10e3c0090ae32944f5bd52f439e8254b53e481d3..52a02360b51151a073fbbefe96d0bfd04d56dbb6 100644 (file)
@@ -118,6 +118,17 @@ inline DataFormat dataFormatFor(FlushFormat format)
     return DataFormatDead;
 }
 
+inline FlushFormat merge(FlushFormat a, FlushFormat b)
+{
+    if (a == DeadFlush)
+        return b;
+    if (b == DeadFlush)
+        return a;
+    if (a == b)
+        return a;
+    return ConflictingFlush;
+}
+
 } } // namespace JSC::DFG
 
 namespace WTF {
index 4df7e8659b9c6586a818b2d52a02aeb4e0fdc80d..cfa0a40c9b7a179274e0d6c87346696f31920f5d 100644 (file)
@@ -75,6 +75,11 @@ Graph::Graph(VM& vm, Plan& plan, LongLivedState& longLivedState)
     
     for (unsigned i = m_mustHandleValues.size(); i--;)
         m_mustHandleValues[i] = freezeFragile(plan.mustHandleValues[i]);
+    
+    for (unsigned i = m_codeBlock->m_numVars; i--;) {
+        if (m_codeBlock->isCaptured(virtualRegisterForLocal(i)))
+            m_outermostCapturedVars.set(i);
+    }
 }
 
 Graph::~Graph()
index 0cd15de47c6455c293a52151bbbf61a916ffc215..e584a19d9ba4ebb1c52737f2ad3bc7d55ae61f38 100644 (file)
@@ -367,6 +367,13 @@ public:
         return baselineCodeBlockForOriginAndBaselineCodeBlock(codeOrigin, m_profiledBlock);
     }
     
+    const BitVector& capturedVarsFor(InlineCallFrame* inlineCallFrame)
+    {
+        if (!inlineCallFrame)
+            return m_outermostCapturedVars;
+        return inlineCallFrame->capturedVars;
+    }
+    
     bool isStrictModeFor(CodeOrigin codeOrigin)
     {
         if (!codeOrigin.inlineCallFrame)
@@ -894,6 +901,7 @@ public:
     unsigned m_parameterSlots;
     int m_machineCaptureStart;
     std::unique_ptr<SlowArgument[]> m_slowArguments;
+    BitVector m_outermostCapturedVars;
 
 #if USE(JSVALUE32_64)
     std::unordered_map<int64_t, double*> m_doubleConstantsMap;
index 50989743d3f2db30b25bbaffa4a60cbeb917f49e..f7170b83cd3e6cd5d49978304b059977e48b89ee 100644 (file)
@@ -79,6 +79,8 @@ bool mayExit(Graph& graph, Node* node)
     case PutStructureHint:
     case PutByOffsetHint:
     case PhantomNewObject:
+    case PutLocal:
+    case KillLocal:
         break;
         
     default:
index 36be0b587a7dfa4453df0319d667d1f3dcdb58a2..18bc24971274c6cbd688019d23f4903a279bb569 100644 (file)
@@ -158,6 +158,8 @@ private:
             changed = false;
             for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
                 HashMap<Node*, bool> materialized = materializedAtHead[block];
+                if (verbose)
+                    dataLog("    Looking at block ", pointerDump(block), "\n");
                 for (Node* node : *block) {
                     handleNode(
                         node,
@@ -166,8 +168,11 @@ private:
                         },
                         [&] (Node* escapee) {
                             auto iter = materialized.find(escapee);
-                            if (iter != materialized.end())
+                            if (iter != materialized.end()) {
+                                if (verbose)
+                                    dataLog("    ", escapee, " escapes at ", node, "\n");
                                 iter->value = true;
+                            }
                         });
                 }
                 
@@ -271,6 +276,9 @@ private:
                     materialized.add(pair.key);
             }
             
+            if (verbose)
+                dataLog("Placing materialization points in ", pointerDump(block), " with materialization set ", listDump(materialized), "\n");
+            
             for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
                 Node* node = block->at(nodeIndex);
                 
@@ -278,11 +286,20 @@ private:
                     node,
                     [&] () { },
                     [&] (Node* escapee) {
-                        if (!m_sinkCandidates.contains(escapee))
+                        if (verbose)
+                            dataLog("Seeing ", escapee, " escape at ", node, "\n");
+                        
+                        if (!m_sinkCandidates.contains(escapee)) {
+                            if (verbose)
+                                dataLog("    It's not a sink candidate.\n");
                             return;
+                        }
                         
-                        if (!materialized.add(escapee).isNewEntry)
+                        if (!materialized.add(escapee).isNewEntry) {
+                            if (verbose)
+                                dataLog("   It's already materialized.\n");
                             return;
+                        }
                         
                         createMaterialize(escapee, node);
                     });
@@ -432,6 +449,16 @@ private:
                         if (Node* materialize = mapping.get(edge.node()))
                             edge.setNode(materialize);
                     });
+                
+                // If you cause an escape, you shouldn't see the original escapee.
+                if (validationEnabled()) {
+                    handleNode(
+                        node,
+                        [&] () { },
+                        [&] (Node* escapee) {
+                            DFG_ASSERT(m_graph, node, !m_sinkCandidates.contains(escapee));
+                        });
+                }
             }
             
             size_t upsilonInsertionPoint = block->size() - 1;
index 17515c5c10a6d0791643e0914ac994f77bb5a9f4..913cadc57e2524ad7414cbcde7600d8b5fe60c58 100644 (file)
@@ -54,6 +54,7 @@
 #include "DFGPhantomRemovalPhase.h"
 #include "DFGPredictionInjectionPhase.h"
 #include "DFGPredictionPropagationPhase.h"
+#include "DFGPutLocalSinkingPhase.h"
 #include "DFGResurrectionForValidationPhase.h"
 #include "DFGSSAConversionPhase.h"
 #include "DFGSSALoweringPhase.h"
@@ -322,6 +323,7 @@ Plan::CompilationPath Plan::compileInThreadImpl(LongLivedState& longLivedState)
         performCPSRethreading(dfg);
         performSSAConversion(dfg);
         performSSALowering(dfg);
+        performPutLocalSinking(dfg);
         performGlobalCSE(dfg);
         performLivenessAnalysis(dfg);
         performCFA(dfg);
@@ -355,7 +357,7 @@ Plan::CompilationPath Plan::compileInThreadImpl(LongLivedState& longLivedState)
         performCFA(dfg);
         if (Options::validateFTLOSRExitLiveness())
             performResurrectionForValidation(dfg);
-        performDCE(dfg); // We rely on this to convert dead SetLocals into the appropriate hint, and to kill dead code that won't be recognized as dead by LLVM.
+        performDCE(dfg); // We rely on this to kill dead code that won't be recognized as dead by LLVM.
         performStackLayout(dfg);
         performLivenessAnalysis(dfg);
         performOSRAvailabilityAnalysis(dfg);
diff --git a/Source/JavaScriptCore/dfg/DFGPreciseLocalClobberize.h b/Source/JavaScriptCore/dfg/DFGPreciseLocalClobberize.h
new file mode 100644 (file)
index 0000000..75b676a
--- /dev/null
@@ -0,0 +1,192 @@
+/*
+ * Copyright (C) 2014 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 DFGPreciseLocalClobberize_h
+#define DFGPreciseLocalClobberize_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGClobberize.h"
+#include "DFGMayExit.h"
+
+namespace JSC { namespace DFG {
+
+template<typename ReadFunctor, typename WriteFunctor, typename DefFunctor>
+class PreciseLocalClobberizeAdaptor {
+public:
+    PreciseLocalClobberizeAdaptor(
+        Graph& graph, Node* node,
+        const ReadFunctor& read, const WriteFunctor& write, const DefFunctor& def)
+        : m_graph(graph)
+        , m_node(node)
+        , m_read(read)
+        , m_write(write)
+        , m_def(def)
+    {
+    }
+    
+    void read(AbstractHeap heap)
+    {
+        if (heap.kind() == Variables) {
+            if (heap.payload().isTop()) {
+                readTop();
+                return;
+            }
+            
+            callIfAppropriate(m_read, VirtualRegister(heap.payload().value32()));
+            return;
+        }
+        
+        if (heap.overlaps(Variables)) {
+            readTop();
+            return;
+        }
+    }
+    
+    void write(AbstractHeap heap)
+    {
+        if (heap.kind() == Variables) {
+            if (heap.payload().isTop()) {
+                writeTop();
+                return;
+            }
+            
+            callIfAppropriate(m_write, VirtualRegister(heap.payload().value32()));
+            return;
+        }
+        
+        if (heap.overlaps(Variables)) {
+            writeTop();
+            return;
+        }
+    }
+    
+    void def(PureValue)
+    {
+        // PureValue defs never have anything to do with locals, so ignore this.
+    }
+    
+    void def(HeapLocation location, Node* node)
+    {
+        if (location.kind() != VariableLoc)
+            return;
+        
+        RELEASE_ASSERT(location.heap().kind() == Variables);
+        
+        m_def(VirtualRegister(location.heap().payload().value32()), node);
+    }
+    
+private:
+    template<typename Functor>
+    void callIfAppropriate(const Functor& functor, VirtualRegister operand)
+    {
+        if (operand.isLocal() && static_cast<unsigned>(operand.toLocal()) >= m_graph.block(0)->variablesAtHead.numberOfLocals())
+            return;
+        
+        if (operand.isArgument() && !operand.isHeader() && static_cast<unsigned>(operand.toArgument()) >= m_graph.block(0)->variablesAtHead.numberOfArguments())
+            return;
+        
+        functor(operand);
+    }
+    
+    void readTop()
+    {
+        // All of the outermost arguments, except this, are definitely read.
+        for (unsigned i = m_graph.m_codeBlock->numParameters(); i-- > 1;)
+            m_read(virtualRegisterForArgument(i));
+        
+        // The stack header is read.
+        for (unsigned i = 0; i < JSStack::ThisArgument; ++i)
+            m_read(VirtualRegister(i));
+        
+        // Read all of the captured variables.
+        const BitVector& capturedVars =
+            m_graph.capturedVarsFor(m_node->origin.semantic.inlineCallFrame);
+        for (unsigned i : capturedVars.setBits())
+            m_read(virtualRegisterForLocal(i));
+        
+        // Read all of the inline arguments and call frame headers that we didn't already capture.
+        for (InlineCallFrame* inlineCallFrame = m_node->origin.semantic.inlineCallFrame; inlineCallFrame; inlineCallFrame = inlineCallFrame->caller.inlineCallFrame) {
+            for (unsigned i = inlineCallFrame->arguments.size(); i-- > 1;)
+                m_read(VirtualRegister(inlineCallFrame->stackOffset + virtualRegisterForArgument(i).offset()));
+            if (inlineCallFrame->isClosureCall) {
+                m_read(VirtualRegister(inlineCallFrame->stackOffset + JSStack::ScopeChain));
+                m_read(VirtualRegister(inlineCallFrame->stackOffset + JSStack::Callee));
+            }
+        }
+    }
+    
+    void writeTop()
+    {
+        if (m_graph.m_codeBlock->usesArguments()) {
+            for (unsigned i = m_graph.m_codeBlock->numParameters(); i-- > 1;)
+                m_write(virtualRegisterForArgument(i));
+        }
+
+        const BitVector& capturedVars =
+            m_graph.capturedVarsFor(m_node->origin.semantic.inlineCallFrame);
+        for (unsigned i : capturedVars.setBits())
+            m_write(virtualRegisterForLocal(i));
+    }
+    
+    Graph& m_graph;
+    Node* m_node;
+    const ReadFunctor& m_read;
+    const WriteFunctor& m_write;
+    const DefFunctor& m_def;
+};
+
+template<typename ReadFunctor>
+void forEachLocalReadByUnwind(Graph& graph, CodeOrigin codeOrigin, const ReadFunctor& read)
+{
+    if (graph.uncheckedActivationRegister().isValid())
+        read(graph.activationRegister());
+    if (graph.m_codeBlock->usesArguments())
+        read(unmodifiedArgumentsRegister(graph.argumentsRegisterFor(nullptr)));
+    
+    for (InlineCallFrame* inlineCallFrame = codeOrigin.inlineCallFrame; inlineCallFrame; inlineCallFrame = inlineCallFrame->caller.inlineCallFrame) {
+        if (inlineCallFrame->executable->usesArguments())
+            read(unmodifiedArgumentsRegister(graph.argumentsRegisterFor(inlineCallFrame)));
+    }
+}
+
+template<typename ReadFunctor, typename WriteFunctor, typename DefFunctor>
+void preciseLocalClobberize(
+    Graph& graph, Node* node,
+    const ReadFunctor& read, const WriteFunctor& write, const DefFunctor& def)
+{
+    PreciseLocalClobberizeAdaptor<ReadFunctor, WriteFunctor, DefFunctor>
+        adaptor(graph, node, read, write, def);
+    clobberize(graph, node, adaptor);
+    if (mayExit(graph, node))
+        forEachLocalReadByUnwind(graph, node->origin.forExit, read);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGPreciseLocalClobberize_h
+
diff --git a/Source/JavaScriptCore/dfg/DFGPutLocalSinkingPhase.cpp b/Source/JavaScriptCore/dfg/DFGPutLocalSinkingPhase.cpp
new file mode 100644 (file)
index 0000000..1b11f3b
--- /dev/null
@@ -0,0 +1,517 @@
+/*
+ * Copyright (C) 2014 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 "DFGPutLocalSinkingPhase.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBlockMapInlines.h"
+#include "DFGGraph.h"
+#include "DFGInsertionSet.h"
+#include "DFGPhase.h"
+#include "DFGPreciseLocalClobberize.h"
+#include "DFGSSACalculator.h"
+#include "DFGValidate.h"
+#include "JSCInlines.h"
+#include "OperandsInlines.h"
+
+namespace JSC { namespace DFG {
+
+namespace {
+
+bool verbose = false;
+
+class VariableDeferral {
+public:
+    VariableDeferral(VariableAccessData* variable = nullptr)
+        : m_variable(variable)
+    {
+    }
+    
+    static VariableDeferral conflict()
+    {
+        return VariableDeferral(conflictMarker());
+    }
+    
+    bool operator!() const { return !m_variable; }
+    
+    bool hasVariable() const { return !!*this && !isConflict(); }
+    
+    VariableAccessData* variable() const
+    {
+        ASSERT(hasVariable());
+        return m_variable;
+    }
+    
+    bool isConflict() const
+    {
+        return m_variable == conflictMarker();
+    }
+    
+    VariableDeferral merge(VariableDeferral other) const
+    {
+        if (*this == other || !other)
+            return *this;
+        if (!*this)
+            return other;
+        return conflict();
+    }
+    
+    bool operator==(VariableDeferral other) const
+    {
+        return m_variable == other.m_variable;
+    }
+    
+    void dump(PrintStream& out) const
+    {
+        if (!*this)
+            out.print("-");
+        else if (isConflict())
+            out.print("Conflict");
+        else
+            out.print(RawPointer(m_variable));
+    }
+    
+    void dumpInContext(PrintStream& out, DumpContext*) const
+    {
+        dump(out);
+    }
+    
+private:
+    static VariableAccessData* conflictMarker()
+    {
+        return bitwise_cast<VariableAccessData*>(static_cast<intptr_t>(1));
+    }
+    
+    VariableAccessData* m_variable;
+};
+
+class PutLocalSinkingPhase : public Phase {
+public:
+    PutLocalSinkingPhase(Graph& graph)
+        : Phase(graph, "PutLocal sinking")
+    {
+    }
+    
+    bool run()
+    {
+        // FIXME: One of the problems of this approach is that it will create a duplicate Phi graph
+        // for sunken PutLocals in the presence of interesting control flow merges, and where the
+        // value being PutLocal'd is also otherwise live in the DFG code. We could work around this
+        // by doing the sinking over CPS, or maybe just by doing really smart hoisting. It's also
+        // possible that the duplicate Phi graph can be deduplicated by LLVM. It would be best if we
+        // could observe that there is already a Phi graph in place that does what we want. In
+        // principle if we have a request to place a Phi at a particular place, we could just check
+        // if there is already a Phi that does what we want. Because PutLocalSinkingPhase runs just
+        // after SSA conversion, we have almost a guarantee that the Phi graph we produce here would
+        // be trivially redundant to the one we already have.
+        
+        if (verbose) {
+            dataLog("Graph before PutLocal sinking:\n");
+            m_graph.dump();
+        }
+        
+        SSACalculator ssaCalculator(m_graph);
+        InsertionSet insertionSet(m_graph);
+        
+        // First figure out where various locals are live.
+        BlockMap<Operands<bool>> liveAtHead(m_graph);
+        BlockMap<Operands<bool>> liveAtTail(m_graph);
+        
+        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+            liveAtHead[block] = Operands<bool>(OperandsLike, block->variablesAtHead);
+            liveAtTail[block] = Operands<bool>(OperandsLike, block->variablesAtHead);
+            
+            liveAtHead[block].fill(false);
+            liveAtTail[block].fill(false);
+        }
+        
+        bool changed;
+        do {
+            changed = false;
+            
+            for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+                BasicBlock* block = m_graph.block(blockIndex);
+                if (!block)
+                    continue;
+                
+                Operands<bool> live = liveAtTail[block];
+                for (unsigned nodeIndex = block->size(); nodeIndex--;) {
+                    Node* node = block->at(nodeIndex);
+                    if (verbose)
+                        dataLog("Live at ", node, ": ", live, "\n");
+                    
+                    auto escapeHandler = [&] (VirtualRegister operand) {
+                        if (operand.isHeader())
+                            return;
+                        if (verbose)
+                            dataLog("    r", operand, " is live at ", node, "\n");
+                        live.operand(operand) = true;
+                    };
+                    
+                    preciseLocalClobberize(
+                        m_graph, node, escapeHandler, escapeHandler,
+                        [&] (VirtualRegister operand, Node* source) {
+                            if (source == node) {
+                                // This is a load. Ignore it.
+                                return;
+                            }
+                            
+                            RELEASE_ASSERT(node->op() == PutLocal);
+                            live.operand(operand) = false;
+                        });
+                }
+                
+                if (live == liveAtHead[block])
+                    continue;
+                
+                liveAtHead[block] = live;
+                changed = true;
+                
+                for (BasicBlock* predecessor : block->predecessors) {
+                    for (size_t i = live.size(); i--;)
+                        liveAtTail[predecessor][i] |= live[i];
+                }
+            }
+            
+        } while (changed);
+        
+        // All of the arguments should be live at head of root. Note that we may find that some
+        // locals are live at head of root. This seems wrong but isn't. This will happen for example
+        // if the function accesses closure variable #42 for some other function and we either don't
+        // have variable #42 at all or we haven't set it at root, for whatever reason. Basically this
+        // arises since our aliasing for closure variables is conservatively based on variable number
+        // and ignores the owning symbol table. We should probably fix this eventually and make our
+        // aliasing more precise.
+        //
+        // For our purposes here, the imprecision in the aliasing is harmless. It just means that we
+        // may not do as much Phi pruning as we wanted.
+        for (size_t i = liveAtHead.atIndex(0).numberOfArguments(); i--;)
+            DFG_ASSERT(m_graph, nullptr, liveAtHead.atIndex(0).argument(i));
+        
+        // Next identify where we would want to sink PutLocals to. We say that there is a deferred
+        // flush if we had a PutLocal with a given VariableAccessData* but it hasn't been
+        // materialized yet.
+        BlockMap<Operands<VariableDeferral>> deferredAtHead(m_graph);
+        BlockMap<Operands<VariableDeferral>> deferredAtTail(m_graph);
+        
+        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+            deferredAtHead[block] =
+                Operands<VariableDeferral>(OperandsLike, block->variablesAtHead);
+            deferredAtTail[block] =
+                Operands<VariableDeferral>(OperandsLike, block->variablesAtHead);
+        }
+        
+        deferredAtHead.atIndex(0).fill(VariableDeferral::conflict());
+        
+        do {
+            changed = false;
+            
+            for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+                Operands<VariableDeferral> deferred = deferredAtHead[block];
+                
+                for (Node* node : *block) {
+                    if (verbose)
+                        dataLog("Deferred at ", node, ":", deferred, "\n");
+                    
+                    if (node->op() == KillLocal) {
+                        deferred.operand(node->unlinkedLocal()) = VariableDeferral::conflict();
+                        continue;
+                    }
+                    
+                    auto escapeHandler = [&] (VirtualRegister operand) {
+                        if (operand.isHeader())
+                            return;
+                        // We will materialize just before any reads.
+                        deferred.operand(operand) = VariableDeferral();
+                    };
+                    
+                    preciseLocalClobberize(
+                        m_graph, node, escapeHandler, escapeHandler,
+                        [&] (VirtualRegister operand, Node* source) {
+                            if (source == node) {
+                                // This is a load. Ignore it.
+                                return;
+                            }
+                            
+                            deferred.operand(operand) = VariableDeferral(node->variableAccessData());
+                        });
+                }
+                
+                if (deferred == deferredAtTail[block])
+                    continue;
+                
+                deferredAtTail[block] = deferred;
+                changed = true;
+                
+                for (BasicBlock* successor : block->successors()) {
+                    for (size_t i = deferred.size(); i--;) {
+                        if (verbose)
+                            dataLog("Considering r", deferred.operandForIndex(i), " at ", pointerDump(block), "->", pointerDump(successor), ": ", deferred[i], " and ", deferredAtHead[successor][i], " merges to ");
+
+                        deferredAtHead[successor][i] =
+                            deferredAtHead[successor][i].merge(deferred[i]);
+                        
+                        if (verbose)
+                            dataLog(deferredAtHead[successor][i], "\n");
+                    }
+                }
+            }
+            
+        } while (changed);
+        
+        // We wish to insert PutLocals at all of the materialization points, which are defined
+        // implicitly as the places where we set deferred to Dead while it was previously not Dead.
+        // To do this, we may need to build some Phi functions to handle stuff like this:
+        //
+        // Before:
+        //
+        //     if (p)
+        //         PutLocal(r42, @x)
+        //     else
+        //         PutLocal(r42, @y)
+        //
+        // After:
+        //
+        //     if (p)
+        //         Upsilon(@x, ^z)
+        //     else
+        //         Upsilon(@y, ^z)
+        //     z: Phi()
+        //     PutLocal(r42, @z)
+        //
+        // This means that we have an SSACalculator::Variable for each local, and a Def is any
+        // PutLocal in the original program. The original PutLocals will simply vanish.
+        
+        Operands<SSACalculator::Variable*> operandToVariable(
+            OperandsLike, m_graph.block(0)->variablesAtHead);
+        Vector<VirtualRegister> indexToOperand;
+        for (size_t i = m_graph.block(0)->variablesAtHead.size(); i--;) {
+            VirtualRegister operand(m_graph.block(0)->variablesAtHead.operandForIndex(i));
+            
+            SSACalculator::Variable* variable = ssaCalculator.newVariable();
+            operandToVariable.operand(operand) = variable;
+            ASSERT(indexToOperand.size() == variable->index());
+            indexToOperand.append(operand);
+        }
+        
+        HashSet<Node*> putLocalsToSink;
+        
+        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+            for (Node* node : *block) {
+                switch (node->op()) {
+                case PutLocal:
+                    putLocalsToSink.add(node);
+                    ssaCalculator.newDef(
+                        operandToVariable.operand(node->local()), block, node->child1().node());
+                    break;
+                case GetArgument:
+                    ssaCalculator.newDef(
+                        operandToVariable.operand(node->local()), block, node);
+                    break;
+                default:
+                    break;
+                }
+            }
+        }
+        
+        ssaCalculator.computePhis(
+            [&] (SSACalculator::Variable* variable, BasicBlock* block) -> Node* {
+                VirtualRegister operand = indexToOperand[variable->index()];
+                
+                if (!liveAtHead[block].operand(operand))
+                    return nullptr;
+                
+                VariableDeferral variableDeferral = deferredAtHead[block].operand(operand);
+
+                // We could have an invalid deferral because liveness is imprecise.
+                if (!variableDeferral.hasVariable())
+                    return nullptr;
+
+                if (verbose)
+                    dataLog("Adding Phi for r", operand, " at ", pointerDump(block), "\n");
+                
+                Node* phiNode = m_graph.addNode(SpecHeapTop, Phi, NodeOrigin());
+                DFG_ASSERT(m_graph, nullptr, variableDeferral.hasVariable());
+                FlushFormat format = variableDeferral.variable()->flushFormat();
+                phiNode->mergeFlags(resultFor(format));
+                return phiNode;
+            });
+        
+        Operands<Node*> mapping(OperandsLike, m_graph.block(0)->variablesAtHead);
+        Operands<VariableDeferral> deferred;
+        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+            mapping.fill(nullptr);
+            
+            for (size_t i = mapping.size(); i--;) {
+                VirtualRegister operand(mapping.operandForIndex(i));
+                
+                SSACalculator::Variable* variable = operandToVariable.operand(operand);
+                SSACalculator::Def* def = ssaCalculator.reachingDefAtHead(block, variable);
+                if (!def)
+                    continue;
+                
+                mapping.operand(operand) = def->value();
+            }
+            
+            if (verbose)
+                dataLog("Mapping at top of ", pointerDump(block), ": ", mapping, "\n");
+            
+            for (SSACalculator::Def* phiDef : ssaCalculator.phisForBlock(block)) {
+                VirtualRegister operand = indexToOperand[phiDef->variable()->index()];
+                
+                insertionSet.insert(0, phiDef->value());
+                
+                if (verbose)
+                    dataLog("   Mapping r", operand, " to ", phiDef->value(), "\n");
+                mapping.operand(operand) = phiDef->value();
+            }
+            
+            deferred = deferredAtHead[block];
+            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
+                Node* node = block->at(nodeIndex);
+                if (verbose)
+                    dataLog("Deferred at ", node, ":", deferred, "\n");
+                
+                switch (node->op()) {
+                case PutLocal: {
+                    VariableAccessData* variable = node->variableAccessData();
+                    VirtualRegister operand = variable->local();
+                    deferred.operand(operand) = VariableDeferral(variable);
+                    if (verbose)
+                        dataLog("   Mapping r", operand, " to ", node->child1().node(), " at ", node, "\n");
+                    mapping.operand(operand) = node->child1().node();
+                    break;
+                }
+                    
+                case GetArgument: {
+                    VariableAccessData* variable = node->variableAccessData();
+                    VirtualRegister operand = variable->local();
+                    mapping.operand(operand) = node;
+                    break;
+                }
+                    
+                case KillLocal: {
+                    deferred.operand(node->unlinkedLocal()) = VariableDeferral();
+                    break;
+                }
+                
+                default: {
+                    auto escapeHandler = [&] (VirtualRegister operand) {
+                        if (operand.isHeader())
+                            return;
+                    
+                        VariableDeferral variableDeferral = deferred.operand(operand);
+                        if (!variableDeferral.hasVariable())
+                            return;
+                    
+                        // Gotta insert a PutLocal.
+                        if (verbose)
+                            dataLog("Inserting a PutLocal for r", operand, " at ", node, "\n");
+
+                        Node* incoming = mapping.operand(operand);
+                        DFG_ASSERT(m_graph, node, incoming);
+                    
+                        insertionSet.insertNode(
+                            nodeIndex, SpecNone, PutLocal, node->origin,
+                            OpInfo(variableDeferral.variable()),
+                            Edge(incoming, useKindFor(variableDeferral.variable()->flushFormat())));
+                    
+                        deferred.operand(operand) = nullptr;
+                    };
+                
+                    preciseLocalClobberize(
+                        m_graph, node, escapeHandler, escapeHandler,
+                        [&] (VirtualRegister, Node*) { });
+                    break;
+                } }
+            }
+            
+            size_t upsilonInsertionPoint = block->size() - 1;
+            NodeOrigin upsilonOrigin = block->last()->origin;
+            for (BasicBlock* successorBlock : block->successors()) {
+                for (SSACalculator::Def* phiDef : ssaCalculator.phisForBlock(successorBlock)) {
+                    Node* phiNode = phiDef->value();
+                    SSACalculator::Variable* variable = phiDef->variable();
+                    VirtualRegister operand = indexToOperand[variable->index()];
+                    if (verbose)
+                        dataLog("Creating Upsilon for r", operand, " at ", pointerDump(block), "->", pointerDump(successorBlock), "\n");
+                    VariableDeferral variableDeferral =
+                        deferredAtHead[successorBlock].operand(operand);
+                    DFG_ASSERT(m_graph, nullptr, variableDeferral.hasVariable());
+                    FlushFormat format = variableDeferral.variable()->flushFormat();
+                    UseKind useKind = useKindFor(format);
+                    Node* incoming = mapping.operand(operand);
+                    DFG_ASSERT(m_graph, nullptr, incoming);
+                    
+                    insertionSet.insertNode(
+                        upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
+                        OpInfo(phiNode), Edge(incoming, useKind));
+                }
+            }
+            
+            insertionSet.execute(block);
+        }
+        
+        // Finally eliminate the sunken PutLocals by turning them into Phantoms. This keeps whatever
+        // type check they were doing. Also prepend KillLocals to them to ensure that we know that
+        // the relevant value was *not* stored to the stack.
+        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
+                Node* node = block->at(nodeIndex);
+                
+                if (!putLocalsToSink.contains(node))
+                    continue;
+                
+                insertionSet.insertNode(
+                    nodeIndex, SpecNone, KillLocal, node->origin, OpInfo(node->local().offset()));
+                node->convertToPhantom();
+            }
+            
+            insertionSet.execute(block);
+        }
+        
+        if (verbose) {
+            dataLog("Graph after PutLocal sinking:\n");
+            m_graph.dump();
+        }
+        
+        return true;
+    }
+};
+
+} // anonymous namespace
+    
+bool performPutLocalSinking(Graph& graph)
+{
+    SamplingRegion samplingRegion("DFG PutLocal Sinking Phase");
+    return runPhase<PutLocalSinkingPhase>(graph);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
diff --git a/Source/JavaScriptCore/dfg/DFGPutLocalSinkingPhase.h b/Source/JavaScriptCore/dfg/DFGPutLocalSinkingPhase.h
new file mode 100644 (file)
index 0000000..5f41138
--- /dev/null
@@ -0,0 +1,46 @@
+ /*
+ * Copyright (C) 2014 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 DFGPutLocalSinkingPhase_h
+#define DFGPutLocalSinkingPhase_h
+
+#if ENABLE(DFG_JIT)
+
+namespace JSC { namespace DFG {
+
+class Graph;
+
+// Sinks PutLocals to the absolute latest point where they can possibly happen, which is usually
+// side-effects that may observe them. This eliminates PutLocals if it sinks them past the point of
+// their deaths.
+
+bool performPutLocalSinking(Graph&);
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGPutLocalSinkingPhase_h
+
index 940935e3900f76dd59e1ca0555b40d6fe8ab40e5..4f4f86529e69bc59a9a3f7ced7bbd3988f66c256 100644 (file)
@@ -174,7 +174,7 @@ public:
     // nonLocalReachingDef() will find it later. Note that it is generally always sound to not
     // prune any Phis (that is, to always have the functor insert a Phi and never return nullptr).
     template<typename PhiInsertionFunctor>
-    void computePhis(PhiInsertionFunctor functor)
+    void computePhis(const PhiInsertionFunctor& functor)
     {
         DFG_ASSERT(m_graph, nullptr, m_graph.m_dominators.isValid());
         
index 2f2e00dbd74606e70137a64397cb2a6edca2fbe4..4ecc636f3ca772e23b9829193ebe3222ac1e0ded 100644 (file)
@@ -74,7 +74,7 @@ public:
     } while (0)
 
     #define notSet (static_cast<size_t>(-1))
-
+        
     void validate()
     {
         // NB. This code is not written for performance, since it is not intended to run
index ce0cdc44c87a1e25efbcad59e4e5180215e22b85..202cc5d1c01c1d86ec2ccefcc0c88fad3d6bbec5 100644 (file)
@@ -1,3 +1,23 @@
+2014-10-04  Filip Pizlo  <fpizlo@apple.com>
+
+        FTL should sink PutLocals
+        https://bugs.webkit.org/show_bug.cgi?id=137168
+
+        Reviewed by Oliver Hunt.
+        
+        Make the set bits of a BitVector iterable.
+
+        * wtf/BitVector.h:
+        (WTF::BitVector::SetBitsIterable::SetBitsIterable):
+        (WTF::BitVector::SetBitsIterable::iterator::iterator):
+        (WTF::BitVector::SetBitsIterable::iterator::operator*):
+        (WTF::BitVector::SetBitsIterable::iterator::operator++):
+        (WTF::BitVector::SetBitsIterable::iterator::operator==):
+        (WTF::BitVector::SetBitsIterable::iterator::operator!=):
+        (WTF::BitVector::SetBitsIterable::begin):
+        (WTF::BitVector::SetBitsIterable::end):
+        (WTF::BitVector::setBits):
+
 2014-10-03  Commit Queue  <commit-queue@webkit.org>
 
         Unreviewed, rolling out r174275.
index 0ff2d071f792fcccb3a8465f8d0155fb6307e66e..9f86fd06108b3d554312f8e11f8beb316e051f7d 100644 (file)
@@ -269,6 +269,58 @@ public:
         return IntHash<uintptr_t>::hash(value);
     }
     
+    class SetBitsIterable {
+    public:
+        SetBitsIterable(const BitVector& bitVector)
+            : m_bitVector(bitVector)
+        {
+        }
+        
+        class iterator {
+        public:
+            iterator()
+                : m_bitVector(nullptr)
+                , m_index(0)
+            {
+            }
+            
+            iterator(const BitVector& bitVector, size_t index)
+                : m_bitVector(&bitVector)
+                , m_index(index)
+            {
+            }
+            
+            size_t operator*() const { return m_index; }
+            
+            iterator& operator++()
+            {
+                m_index = m_bitVector->findBit(m_index + 1, true);
+                return *this;
+            }
+            
+            bool operator==(const iterator& other) const
+            {
+                return m_index == other.m_index;
+            }
+            
+            bool operator!=(const iterator& other) const
+            {
+                return !(*this == other);
+            }
+        private:
+            const BitVector* m_bitVector;
+            size_t m_index;
+        };
+        
+        iterator begin() const { return iterator(m_bitVector, m_bitVector.findBit(0, true)); }
+        iterator end() const { return iterator(m_bitVector, m_bitVector.size()); }
+        
+    private:
+        const BitVector& m_bitVector;
+    };
+    
+    SetBitsIterable setBits() const { return SetBitsIterable(*this); }
+    
 private:
     static unsigned bitsInPointer()
     {