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 f41aa59..6809231 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 2f72c2e..8bc54d0 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 f213d1f..5355c9f 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 79dd7cf..a8cc452 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 b31171d..d1c0777 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 a860425..660a5c4 100644 (file)
@@ -384,7 +384,7 @@ public:
             return 0;
         return symbolTable()->captureEnd();
     }
-
+    
     bool isCaptured(VirtualRegister operand, InlineCallFrame* = 0) const;
     
     int framePointerOffsetToGetActivationRegisters(int machineCaptureStart);
index 92a9564..168aad9 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 74ad60b..c9dee88 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 26e525d..bca836d 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 90b581a..77b2180 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 c309db3..2bd99e2 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 27b350a..2797fd6 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 5dfe495..d76d355 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 aed5c99..ed2042a 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 10e3c00..52a0236 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 4df7e86..cfa0a40 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 0cd15de..e584a19 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 5098974..f7170b8 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 36be0b5..18bc249 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 17515c5..913cadc 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 940935e..4f4f865 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 2f2e00d..4ecc636 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 ce0cdc4..202cc5d 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 0ff2d07..9f86fd0 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()
     {