<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[195417] trunk/Source</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/195417">195417</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2016-01-21 11:54:51 -0800 (Thu, 21 Jan 2016)</dd>
</dl>
<h3>Log Message</h3>
<pre>B3 should have load elimination
https://bugs.webkit.org/show_bug.cgi?id=153288
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
This adds a complete GCSE pass that includes load elimination. It would have been super hard
to make this work as part of the reduceStrength() fixpoint, since GCSE needs to analyze
control flow and reduceStrength() is messing with control flow. So, I did a compromise: I
factored out the pure CSE that reduceStrength() was already doing, and now we have:
- reduceStrength() still does pure CSE using the new PureCSE helper.
- eliminateCommonSubexpressions() is a separate phase that does general CSE. It uses the
PureCSE helper for pure values and does its own special thing for memory values.
Unfortunately, this doesn't help any benchmark right now. It doesn't hurt anything, either,
and it's likely to become a bigger pay-off once we implement other features, like mapping
FTL's abstract heaps onto B3's heap ranges.
* CMakeLists.txt:
* JavaScriptCore.xcodeproj/project.pbxproj:
* b3/B3EliminateCommonSubexpressions.cpp: Added.
(JSC::B3::eliminateCommonSubexpressions):
* b3/B3EliminateCommonSubexpressions.h: Added.
* b3/B3Generate.cpp:
(JSC::B3::generateToAir):
* b3/B3HeapRange.h:
(JSC::B3::HeapRange::HeapRange):
* b3/B3InsertionSet.h:
(JSC::B3::InsertionSet::InsertionSet):
(JSC::B3::InsertionSet::isEmpty):
(JSC::B3::InsertionSet::code):
(JSC::B3::InsertionSet::appendInsertion):
* b3/B3MemoryValue.h:
* b3/B3PureCSE.cpp: Added.
(JSC::B3::PureCSE::PureCSE):
(JSC::B3::PureCSE::~PureCSE):
(JSC::B3::PureCSE::clear):
(JSC::B3::PureCSE::process):
* b3/B3PureCSE.h: Added.
* b3/B3ReduceStrength.cpp:
* b3/B3ReduceStrength.h:
* b3/B3Validate.cpp:
Source/WTF:
I needed a way to track sets of ranges, where there is a high likelihood that all of the
ranges overlap. So I created RangeSet. It's a usually-sorted list of coalesced ranges.
Practically this means that right now, FTL B3 will end up with two kinds of range sets: a set
that just contains top and a set that contains nothing. In the future, most sets will either
be top of empty but some of them will contain a handful of other things.
* WTF.xcodeproj/project.pbxproj:
* wtf/CMakeLists.txt:
* wtf/MathExtras.h:
(WTF::leftShiftWithSaturation):
(WTF::nonEmptyRangesOverlap):
(WTF::rangesOverlap):
* wtf/RangeSet.h: Added.
(WTF::RangeSet::RangeSet):
(WTF::RangeSet::~RangeSet):
(WTF::RangeSet::add):
(WTF::RangeSet::contains):
(WTF::RangeSet::overlaps):
(WTF::RangeSet::clear):
(WTF::RangeSet::dump):
(WTF::RangeSet::dumpRaw):
(WTF::RangeSet::compact):
(WTF::RangeSet::overlapsNonEmpty):
(WTF::RangeSet::subsumesNonEmpty):
(WTF::RangeSet::findRange):
* wtf/StdLibExtras.h:
(WTF::binarySearchImpl):
(WTF::binarySearch):
(WTF::tryBinarySearch):
(WTF::approximateBinarySearch):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreCMakeListstxt">trunk/Source/JavaScriptCore/CMakeLists.txt</a></li>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj">trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3Generatecpp">trunk/Source/JavaScriptCore/b3/B3Generate.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3HeapRangeh">trunk/Source/JavaScriptCore/b3/B3HeapRange.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3InsertionSeth">trunk/Source/JavaScriptCore/b3/B3InsertionSet.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3MemoryValueh">trunk/Source/JavaScriptCore/b3/B3MemoryValue.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3ReduceStrengthcpp">trunk/Source/JavaScriptCore/b3/B3ReduceStrength.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3ReduceStrengthh">trunk/Source/JavaScriptCore/b3/B3ReduceStrength.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3Validatecpp">trunk/Source/JavaScriptCore/b3/B3Validate.cpp</a></li>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFWTFxcodeprojprojectpbxproj">trunk/Source/WTF/WTF.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceWTFwtfCMakeListstxt">trunk/Source/WTF/wtf/CMakeLists.txt</a></li>
<li><a href="#trunkSourceWTFwtfMathExtrash">trunk/Source/WTF/wtf/MathExtras.h</a></li>
<li><a href="#trunkSourceWTFwtfStdLibExtrash">trunk/Source/WTF/wtf/StdLibExtras.h</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreb3B3EliminateCommonSubexpressionscpp">trunk/Source/JavaScriptCore/b3/B3EliminateCommonSubexpressions.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3EliminateCommonSubexpressionsh">trunk/Source/JavaScriptCore/b3/B3EliminateCommonSubexpressions.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3PureCSEcpp">trunk/Source/JavaScriptCore/b3/B3PureCSE.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3PureCSEh">trunk/Source/JavaScriptCore/b3/B3PureCSE.h</a></li>
<li><a href="#trunkSourceWTFwtfRangeSeth">trunk/Source/WTF/wtf/RangeSet.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreCMakeListstxt"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/CMakeLists.txt (195416 => 195417)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/CMakeLists.txt 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/JavaScriptCore/CMakeLists.txt 2016-01-21 19:54:51 UTC (rev 195417)
</span><span class="lines">@@ -120,6 +120,7 @@
</span><span class="cx"> b3/B3DataSection.cpp
</span><span class="cx"> b3/B3DuplicateTails.cpp
</span><span class="cx"> b3/B3Effects.cpp
</span><ins>+ b3/B3EliminateCommonSubexpressions.cpp
</ins><span class="cx"> b3/B3FixSSA.cpp
</span><span class="cx"> b3/B3FoldPathConstants.cpp
</span><span class="cx"> b3/B3FrequencyClass.cpp
</span><span class="lines">@@ -142,6 +143,7 @@
</span><span class="cx"> b3/B3PhaseScope.cpp
</span><span class="cx"> b3/B3PhiChildren.cpp
</span><span class="cx"> b3/B3Procedure.cpp
</span><ins>+ b3/B3PureCSE.cpp
</ins><span class="cx"> b3/B3ReduceDoubleToFloat.cpp
</span><span class="cx"> b3/B3ReduceStrength.cpp
</span><span class="cx"> b3/B3SSACalculator.cpp
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (195416 => 195417)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/JavaScriptCore/ChangeLog 2016-01-21 19:54:51 UTC (rev 195417)
</span><span class="lines">@@ -1,3 +1,49 @@
</span><ins>+2016-01-21 Filip Pizlo <fpizlo@apple.com>
+
+ B3 should have load elimination
+ https://bugs.webkit.org/show_bug.cgi?id=153288
+
+ Reviewed by Geoffrey Garen.
+
+ This adds a complete GCSE pass that includes load elimination. It would have been super hard
+ to make this work as part of the reduceStrength() fixpoint, since GCSE needs to analyze
+ control flow and reduceStrength() is messing with control flow. So, I did a compromise: I
+ factored out the pure CSE that reduceStrength() was already doing, and now we have:
+
+ - reduceStrength() still does pure CSE using the new PureCSE helper.
+
+ - eliminateCommonSubexpressions() is a separate phase that does general CSE. It uses the
+ PureCSE helper for pure values and does its own special thing for memory values.
+
+ Unfortunately, this doesn't help any benchmark right now. It doesn't hurt anything, either,
+ and it's likely to become a bigger pay-off once we implement other features, like mapping
+ FTL's abstract heaps onto B3's heap ranges.
+
+ * CMakeLists.txt:
+ * JavaScriptCore.xcodeproj/project.pbxproj:
+ * b3/B3EliminateCommonSubexpressions.cpp: Added.
+ (JSC::B3::eliminateCommonSubexpressions):
+ * b3/B3EliminateCommonSubexpressions.h: Added.
+ * b3/B3Generate.cpp:
+ (JSC::B3::generateToAir):
+ * b3/B3HeapRange.h:
+ (JSC::B3::HeapRange::HeapRange):
+ * b3/B3InsertionSet.h:
+ (JSC::B3::InsertionSet::InsertionSet):
+ (JSC::B3::InsertionSet::isEmpty):
+ (JSC::B3::InsertionSet::code):
+ (JSC::B3::InsertionSet::appendInsertion):
+ * b3/B3MemoryValue.h:
+ * b3/B3PureCSE.cpp: Added.
+ (JSC::B3::PureCSE::PureCSE):
+ (JSC::B3::PureCSE::~PureCSE):
+ (JSC::B3::PureCSE::clear):
+ (JSC::B3::PureCSE::process):
+ * b3/B3PureCSE.h: Added.
+ * b3/B3ReduceStrength.cpp:
+ * b3/B3ReduceStrength.h:
+ * b3/B3Validate.cpp:
+
</ins><span class="cx"> 2016-01-21 Keith Miller <keith_miller@apple.com>
</span><span class="cx">
</span><span class="cx"> Fix bug in TypedArray.prototype.set and add tests
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj (195416 => 195417)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2016-01-21 19:54:51 UTC (rev 195417)
</span><span class="lines">@@ -467,6 +467,10 @@
</span><span class="cx"> 0F7025AA1714B0FC00382C0E /* DFGOSRExitCompilerCommon.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F7025A81714B0F800382C0E /* DFGOSRExitCompilerCommon.h */; };
</span><span class="cx"> 0F714CA416EA92F000F3EBEB /* DFGBackwardsPropagationPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F714CA116EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.cpp */; };
</span><span class="cx"> 0F714CA516EA92F200F3EBEB /* DFGBackwardsPropagationPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F714CA216EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.h */; };
</span><ins>+ 0F725CA71C503DED00AD943A /* B3EliminateCommonSubexpressions.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F725CA31C503DED00AD943A /* B3EliminateCommonSubexpressions.cpp */; };
+ 0F725CA81C503DED00AD943A /* B3EliminateCommonSubexpressions.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F725CA41C503DED00AD943A /* B3EliminateCommonSubexpressions.h */; };
+ 0F725CA91C503DED00AD943A /* B3PureCSE.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F725CA51C503DED00AD943A /* B3PureCSE.cpp */; };
+ 0F725CAA1C503DED00AD943A /* B3PureCSE.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F725CA61C503DED00AD943A /* B3PureCSE.h */; };
</ins><span class="cx"> 0F725CAF1C506D3B00AD943A /* B3FoldPathConstants.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F725CAD1C506D3B00AD943A /* B3FoldPathConstants.cpp */; };
</span><span class="cx"> 0F725CB01C506D3B00AD943A /* B3FoldPathConstants.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F725CAE1C506D3B00AD943A /* B3FoldPathConstants.h */; };
</span><span class="cx"> 0F743BAA16B88249009F9277 /* ARM64Disassembler.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 652A3A201651C66100A80AFE /* ARM64Disassembler.cpp */; };
</span><span class="lines">@@ -2647,6 +2651,10 @@
</span><span class="cx"> 0F7025A81714B0F800382C0E /* DFGOSRExitCompilerCommon.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGOSRExitCompilerCommon.h; path = dfg/DFGOSRExitCompilerCommon.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F714CA116EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGBackwardsPropagationPhase.cpp; path = dfg/DFGBackwardsPropagationPhase.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0F714CA216EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBackwardsPropagationPhase.h; path = dfg/DFGBackwardsPropagationPhase.h; sourceTree = "<group>"; };
</span><ins>+ 0F725CA31C503DED00AD943A /* B3EliminateCommonSubexpressions.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3EliminateCommonSubexpressions.cpp; path = b3/B3EliminateCommonSubexpressions.cpp; sourceTree = "<group>"; };
+ 0F725CA41C503DED00AD943A /* B3EliminateCommonSubexpressions.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3EliminateCommonSubexpressions.h; path = b3/B3EliminateCommonSubexpressions.h; sourceTree = "<group>"; };
+ 0F725CA51C503DED00AD943A /* B3PureCSE.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3PureCSE.cpp; path = b3/B3PureCSE.cpp; sourceTree = "<group>"; };
+ 0F725CA61C503DED00AD943A /* B3PureCSE.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3PureCSE.h; path = b3/B3PureCSE.h; sourceTree = "<group>"; };
</ins><span class="cx"> 0F725CAD1C506D3B00AD943A /* B3FoldPathConstants.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3FoldPathConstants.cpp; path = b3/B3FoldPathConstants.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0F725CAE1C506D3B00AD943A /* B3FoldPathConstants.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3FoldPathConstants.h; path = b3/B3FoldPathConstants.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F766D1C15A5028D008F363E /* JITStubRoutine.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JITStubRoutine.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -4783,6 +4791,8 @@
</span><span class="cx"> 0F6B8AD71C4EDDA200969052 /* B3DuplicateTails.h */,
</span><span class="cx"> 0FEC85C41BE16F5A0080FF74 /* B3Effects.cpp */,
</span><span class="cx"> 0FEC85BE1BE167A00080FF74 /* B3Effects.h */,
</span><ins>+ 0F725CA31C503DED00AD943A /* B3EliminateCommonSubexpressions.cpp */,
+ 0F725CA41C503DED00AD943A /* B3EliminateCommonSubexpressions.h */,
</ins><span class="cx"> 0F6B8AE01C4EFE1700969052 /* B3FixSSA.cpp */,
</span><span class="cx"> 0F6B8AE11C4EFE1700969052 /* B3FixSSA.h */,
</span><span class="cx"> 0F725CAD1C506D3B00AD943A /* B3FoldPathConstants.cpp */,
</span><span class="lines">@@ -4834,6 +4844,8 @@
</span><span class="cx"> 0FEC84E11BDACDAC0080FF74 /* B3Procedure.cpp */,
</span><span class="cx"> 0FEC84E21BDACDAC0080FF74 /* B3Procedure.h */,
</span><span class="cx"> 0FEC84E31BDACDAC0080FF74 /* B3ProcedureInlines.h */,
</span><ins>+ 0F725CA51C503DED00AD943A /* B3PureCSE.cpp */,
+ 0F725CA61C503DED00AD943A /* B3PureCSE.h */,
</ins><span class="cx"> 43422A641C16221E00E2EB98 /* B3ReduceDoubleToFloat.cpp */,
</span><span class="cx"> 43422A651C16221E00E2EB98 /* B3ReduceDoubleToFloat.h */,
</span><span class="cx"> 0FEC85B71BE1462F0080FF74 /* B3ReduceStrength.cpp */,
</span><span class="lines">@@ -7324,6 +7336,7 @@
</span><span class="cx"> 0FC97F3E18202119002C9B26 /* DFGInvalidationPointInjectionPhase.h in Headers */,
</span><span class="cx"> 0FEA0A34170D40BF00BB722C /* DFGJITCode.h in Headers */,
</span><span class="cx"> 86EC9DCC1328DF82002B2AD7 /* DFGJITCompiler.h in Headers */,
</span><ins>+ 0F725CA81C503DED00AD943A /* B3EliminateCommonSubexpressions.h in Headers */,
</ins><span class="cx"> A78A9779179738B8009DF744 /* DFGJITFinalizer.h in Headers */,
</span><span class="cx"> 0FC97F4018202119002C9B26 /* DFGJumpReplacement.h in Headers */,
</span><span class="cx"> A73A535B1799CD5D00170C19 /* DFGLazyJSValue.h in Headers */,
</span><span class="lines">@@ -7651,6 +7664,7 @@
</span><span class="cx"> A1D792FD1B43864B004516F5 /* IntlNumberFormat.h in Headers */,
</span><span class="cx"> A1D792FF1B43864B004516F5 /* IntlNumberFormatConstructor.h in Headers */,
</span><span class="cx"> A125846E1B45A36000CC7F6C /* IntlNumberFormatConstructor.lut.h in Headers */,
</span><ins>+ 0F725CAA1C503DED00AD943A /* B3PureCSE.h in Headers */,
</ins><span class="cx"> A1D793011B43864B004516F5 /* IntlNumberFormatPrototype.h in Headers */,
</span><span class="cx"> A125846F1B45A36000CC7F6C /* IntlNumberFormatPrototype.lut.h in Headers */,
</span><span class="cx"> A55165D31BDF0B9E003B75C1 /* InspectorScriptProfilerAgent.h in Headers */,
</span><span class="lines">@@ -8880,6 +8894,7 @@
</span><span class="cx"> A7D9A29417A0BC7400EE2618 /* DFGAtTailAbstractState.cpp in Sources */,
</span><span class="cx"> 0F666EC61835672B00D017F1 /* DFGAvailability.cpp in Sources */,
</span><span class="cx"> 0F2B9CE219D0BA7D00B1D1B5 /* DFGAvailabilityMap.cpp in Sources */,
</span><ins>+ 0F725CA71C503DED00AD943A /* B3EliminateCommonSubexpressions.cpp in Sources */,
</ins><span class="cx"> 0F714CA416EA92F000F3EBEB /* DFGBackwardsPropagationPhase.cpp in Sources */,
</span><span class="cx"> A7D89CF217A0B8CC00773AD8 /* DFGBasicBlock.cpp in Sources */,
</span><span class="cx"> A7D89CF317A0B8CC00773AD8 /* DFGBlockInsertionSet.cpp in Sources */,
</span><span class="lines">@@ -9328,6 +9343,7 @@
</span><span class="cx"> 14D2F3DA139F4BE200491031 /* MarkedSpace.cpp in Sources */,
</span><span class="cx"> 142D6F1113539A4100B02E86 /* MarkStack.cpp in Sources */,
</span><span class="cx"> 70B791981C024A29002481E2 /* GeneratorPrototype.cpp in Sources */,
</span><ins>+ 0F725CA91C503DED00AD943A /* B3PureCSE.cpp in Sources */,
</ins><span class="cx"> 4340A4841A9051AF00D73CCA /* MathCommon.cpp in Sources */,
</span><span class="cx"> 0F37308C1C0BD29100052BFA /* B3PhiChildren.cpp in Sources */,
</span><span class="cx"> 14469DDF107EC7E700650446 /* MathObject.cpp in Sources */,
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3EliminateCommonSubexpressionscpp"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/b3/B3EliminateCommonSubexpressions.cpp (0 => 195417)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3EliminateCommonSubexpressions.cpp (rev 0)
+++ trunk/Source/JavaScriptCore/b3/B3EliminateCommonSubexpressions.cpp 2016-01-21 19:54:51 UTC (rev 195417)
</span><span class="lines">@@ -0,0 +1,378 @@
</span><ins>+/*
+ * Copyright (C) 2016 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "B3EliminateCommonSubexpressions.h"
+
+#if ENABLE(B3_JIT)
+
+#include "B3BasicBlockInlines.h"
+#include "B3BlockWorklist.h"
+#include "B3Dominators.h"
+#include "B3HeapRange.h"
+#include "B3InsertionSetInlines.h"
+#include "B3MemoryValue.h"
+#include "B3PhaseScope.h"
+#include "B3ProcedureInlines.h"
+#include "B3PureCSE.h"
+#include "B3ValueKey.h"
+#include "B3ValueInlines.h"
+#include <wtf/HashMap.h>
+#include <wtf/RangeSet.h>
+
+namespace JSC { namespace B3 {
+
+namespace {
+
+const bool verbose = false;
+
+// FIXME: We could treat Patchpoints with a non-empty set of reads as a "memory value" and somehow
+// eliminate redundant ones. We would need some way of determining if two patchpoints are replacable.
+// It doesn't seem right to use the reads set for this. We could use the generator, but that feels
+// lame because the FTL will pretty much use a unique generator for each patchpoint even when two
+// patchpoints have the same semantics as far as CSE would be concerned. We could invent something
+// like a "value ID" for patchpoints. By default, each one gets a unique value ID, but FTL could force
+// some patchpoints to share the same one as a signal that they will return the same value if executed
+// in the same heap with the same inputs.
+
+typedef Vector<MemoryValue*, 1> MemoryMatches;
+
+struct ImpureBlockData {
+ RangeSet<HeapRange> writes;
+
+ // Maps an address base to all of the MemoryValues that do things to it. After we're done
+ // processing a map, this tells us the values at tail.
+ HashMap<Value*, MemoryMatches> memoryValues;
+};
+
+class CSE {
+public:
+ CSE(Procedure& proc)
+ : m_proc(proc)
+ , m_dominators(proc.dominators())
+ , m_impureBlockData(proc.size())
+ , m_insertionSet(proc)
+ {
+ }
+
+ bool run()
+ {
+ if (verbose)
+ dataLog("B3 before CSE:\n", m_proc);
+
+ m_proc.resetValueOwners();
+
+ for (BasicBlock* block : m_proc) {
+ m_data = &m_impureBlockData[block];
+ for (Value* value : *block)
+ m_data->writes.add(value->effects().writes);
+ }
+
+ for (BasicBlock* block : m_proc.blocksInPreOrder()) {
+ m_block = block;
+ m_data = &m_impureBlockData[block];
+ m_writes.clear();
+ for (m_index = 0; m_index < block->size(); ++m_index) {
+ m_value = block->at(m_index);
+ process();
+ }
+ m_insertionSet.execute(block);
+ }
+
+ return m_changed;
+ }
+
+private:
+ void process()
+ {
+ m_value->performSubstitution();
+
+ if (m_pureCSE.process(m_value, m_dominators)) {
+ ASSERT(!m_value->effects().writes);
+ m_changed = true;
+ return;
+ }
+
+ if (HeapRange writes = m_value->effects().writes)
+ clobber(writes);
+
+ if (MemoryValue* memory = m_value->as<MemoryValue>())
+ processMemory(memory);
+ }
+
+ void clobber(HeapRange writes)
+ {
+ m_writes.add(writes);
+
+ m_data->memoryValues.removeIf(
+ [&] (HashMap<Value*, MemoryMatches>::KeyValuePairType& entry) -> bool {
+ entry.value.removeAllMatching(
+ [&] (MemoryValue* memory) -> bool {
+ return memory->range().overlaps(writes);
+ });
+ return entry.value.isEmpty();
+ });
+ }
+
+ void processMemory(MemoryValue* memory)
+ {
+ Value* ptr = memory->lastChild();
+ HeapRange range = memory->range();
+ int32_t offset = memory->offset();
+ Type type = memory->type();
+
+ // FIXME: Empower this to insert more casts and shifts. For example, a Load8 could match a
+ // Store and mask the result. You could even have:
+ //
+ // Store(@value, @ptr, offset = 0)
+ // Load8Z(@ptr, offset = 2)
+ //
+ // Which could be turned into something like this:
+ //
+ // Store(@value, @ptr, offset = 0)
+ // ZShr(@value, 16)
+
+ switch (memory->opcode()) {
+ case Load8Z: {
+ MemoryValue* match = findMemoryValue(
+ ptr, range, [&] (MemoryValue* candidate) -> bool {
+ return candidate->offset() == offset
+ && (candidate->opcode() == Load8Z || candidate->opcode() == Store8);
+ });
+ if (replace(match))
+ break;
+ addMemoryValue(memory);
+ break;
+ }
+
+ case Load8S: {
+ MemoryValue* match = findMemoryValue(
+ ptr, range, [&] (MemoryValue* candidate) -> bool {
+ return candidate->offset() == offset
+ && (candidate->opcode() == Load8S || candidate->opcode() == Store8);
+ });
+ if (match) {
+ if (match->opcode() == Store8) {
+ m_value->replaceWithIdentity(
+ m_insertionSet.insert<Value>(
+ m_index, SExt8, m_value->origin(), match->child(0)));
+ m_changed = true;
+ break;
+ }
+ replace(match);
+ break;
+ }
+ addMemoryValue(memory);
+ break;
+ }
+
+ case Load16Z: {
+ MemoryValue* match = findMemoryValue(
+ ptr, range, [&] (MemoryValue* candidate) -> bool {
+ return candidate->offset() == offset
+ && (candidate->opcode() == Load16Z || candidate->opcode() == Store16);
+ });
+ if (replace(match))
+ break;
+ addMemoryValue(memory);
+ break;
+ }
+
+ case Load16S: {
+ MemoryValue* match = findMemoryValue(
+ ptr, range, [&] (MemoryValue* candidate) -> bool {
+ return candidate->offset() == offset
+ && (candidate->opcode() == Load16S || candidate->opcode() == Store16);
+ });
+ if (match) {
+ if (match->opcode() == Store16) {
+ m_value->replaceWithIdentity(
+ m_insertionSet.insert<Value>(
+ m_index, SExt16, m_value->origin(), match->child(0)));
+ m_changed = true;
+ break;
+ }
+ replace(match);
+ break;
+ }
+ addMemoryValue(memory);
+ break;
+ }
+
+ case Load: {
+ MemoryValue* match = findMemoryValue(
+ ptr, range, [&] (MemoryValue* candidate) -> bool {
+ if (candidate->offset() != offset)
+ return false;
+
+ if (candidate->opcode() == Load && candidate->type() == type)
+ return true;
+
+ if (candidate->opcode() == Store && candidate->child(0)->type() == type)
+ return true;
+
+ return false;
+ });
+ if (replace(match))
+ break;
+ addMemoryValue(memory);
+ break;
+ }
+
+ case Store8:
+ case Store16:
+ case Store: {
+ addMemoryValue(memory);
+ break;
+ }
+
+ default:
+ dataLog("Bad memory value: ", deepDump(m_proc, m_value), "\n");
+ RELEASE_ASSERT_NOT_REACHED();
+ break;
+ }
+ }
+
+ bool replace(MemoryValue* match)
+ {
+ if (!match)
+ return false;
+
+ if (verbose)
+ dataLog("Eliminating ", *m_value, " due to ", *match, "\n");
+
+ if (match->isStore())
+ m_value->replaceWithIdentity(match->child(0));
+ else
+ m_value->replaceWithIdentity(match);
+ m_changed = true;
+ return true;
+ }
+
+ void addMemoryValue(MemoryValue* memory)
+ {
+ addMemoryValue(*m_data, memory);
+ }
+
+ void addMemoryValue(ImpureBlockData& data, MemoryValue* memory)
+ {
+ MemoryMatches& matches =
+ data.memoryValues.add(memory->lastChild(), MemoryMatches()).iterator->value;
+
+ if (matches.contains(memory))
+ return;
+
+ matches.append(memory);
+ }
+
+ template<typename Filter>
+ MemoryValue* findMemoryValue(Value* ptr, HeapRange range, const Filter& filter)
+ {
+ auto find = [&] (ImpureBlockData& data) -> MemoryValue* {
+ auto iter = data.memoryValues.find(ptr);
+ if (iter != data.memoryValues.end()) {
+ for (MemoryValue* candidate : iter->value) {
+ if (filter(candidate))
+ return candidate;
+ }
+ }
+ return nullptr;
+ };
+
+ if (MemoryValue* match = find(*m_data))
+ return match;
+
+ if (m_writes.overlaps(range))
+ return nullptr;
+
+ BlockWorklist worklist;
+ Vector<BasicBlock*, 8> seenList;
+
+ worklist.pushAll(m_block->predecessors());
+
+ MemoryValue* match = nullptr;
+
+ while (BasicBlock* block = worklist.pop()) {
+ seenList.append(block);
+
+ ImpureBlockData& data = m_impureBlockData[block];
+
+ if (m_dominators.strictlyDominates(block, m_block)) {
+ match = find(data);
+ if (match)
+ continue;
+ }
+
+ if (data.writes.overlaps(range))
+ return nullptr;
+
+ worklist.pushAll(block->predecessors());
+ }
+
+ if (!match)
+ return nullptr;
+
+ for (BasicBlock* block : seenList)
+ addMemoryValue(m_impureBlockData[block], match);
+ addMemoryValue(match);
+
+ return match;
+ }
+
+ typedef Vector<Value*, 1> Matches;
+
+ Procedure& m_proc;
+
+ Dominators& m_dominators;
+ PureCSE m_pureCSE;
+
+ IndexMap<BasicBlock, ImpureBlockData> m_impureBlockData;
+
+ ImpureBlockData* m_data;
+ RangeSet<HeapRange> m_writes;
+
+ BasicBlock* m_block;
+ unsigned m_index;
+ Value* m_value;
+
+ InsertionSet m_insertionSet;
+
+ bool m_changed { false };
+};
+
+} // anonymous namespace
+
+bool eliminateCommonSubexpressions(Procedure& proc)
+{
+ PhaseScope phaseScope(proc, "eliminateCommonSubexpressions");
+
+ CSE cse(proc);
+ return cse.run();
+}
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3EliminateCommonSubexpressionsh"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/b3/B3EliminateCommonSubexpressions.h (0 => 195417)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3EliminateCommonSubexpressions.h (rev 0)
+++ trunk/Source/JavaScriptCore/b3/B3EliminateCommonSubexpressions.h 2016-01-21 19:54:51 UTC (rev 195417)
</span><span class="lines">@@ -0,0 +1,44 @@
</span><ins>+/*
+ * Copyright (C) 2016 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef B3EliminateCommonSubexpressions_h
+#define B3EliminateCommonSubexpressions_h
+
+#if ENABLE(B3_JIT)
+
+namespace JSC { namespace B3 {
+
+class Procedure;
+
+// This does global common subexpression elimination (CSE) over both pure values and memory accesses.
+
+bool eliminateCommonSubexpressions(Procedure&);
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
+#endif // B3EliminateCommonSubexpressions_h
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3Generatecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3Generate.cpp (195416 => 195417)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3Generate.cpp 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/JavaScriptCore/b3/B3Generate.cpp 2016-01-21 19:54:51 UTC (rev 195417)
</span><span class="lines">@@ -33,6 +33,7 @@
</span><span class="cx"> #include "AirInstInlines.h"
</span><span class="cx"> #include "B3Common.h"
</span><span class="cx"> #include "B3DuplicateTails.h"
</span><ins>+#include "B3EliminateCommonSubexpressions.h"
</ins><span class="cx"> #include "B3FoldPathConstants.h"
</span><span class="cx"> #include "B3LegalizeMemoryOffsets.h"
</span><span class="cx"> #include "B3LowerMacros.h"
</span><span class="lines">@@ -78,6 +79,7 @@
</span><span class="cx"> if (optLevel >= 1) {
</span><span class="cx"> reduceDoubleToFloat(procedure);
</span><span class="cx"> reduceStrength(procedure);
</span><ins>+ eliminateCommonSubexpressions(procedure);
</ins><span class="cx"> duplicateTails(procedure);
</span><span class="cx"> foldPathConstants(procedure);
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3HeapRangeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3HeapRange.h (195416 => 195417)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3HeapRange.h 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/JavaScriptCore/b3/B3HeapRange.h 2016-01-21 19:54:51 UTC (rev 195417)
</span><span class="lines">@@ -40,6 +40,8 @@
</span><span class="cx">
</span><span class="cx"> class HeapRange {
</span><span class="cx"> public:
</span><ins>+ typedef unsigned Type;
+
</ins><span class="cx"> HeapRange()
</span><span class="cx"> : m_begin(0)
</span><span class="cx"> , m_end(0)
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3InsertionSeth"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3InsertionSet.h (195416 => 195417)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3InsertionSet.h 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/JavaScriptCore/b3/B3InsertionSet.h 2016-01-21 19:54:51 UTC (rev 195417)
</span><span class="lines">@@ -48,6 +48,8 @@
</span><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ bool isEmpty() const { return m_insertions.isEmpty(); }
+
</ins><span class="cx"> Procedure& code() { return m_procedure; }
</span><span class="cx">
</span><span class="cx"> void appendInsertion(const Insertion& insertion)
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3MemoryValueh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3MemoryValue.h (195416 => 195417)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3MemoryValue.h 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/JavaScriptCore/b3/B3MemoryValue.h 2016-01-21 19:54:51 UTC (rev 195417)
</span><span class="lines">@@ -60,6 +60,9 @@
</span><span class="cx"> const HeapRange& range() const { return m_range; }
</span><span class="cx"> void setRange(const HeapRange& range) { m_range = range; }
</span><span class="cx">
</span><ins>+ bool isStore() const { return type() == Void; }
+ bool isLoad() const { return type() != Void; }
+
</ins><span class="cx"> size_t accessByteSize() const;
</span><span class="cx">
</span><span class="cx"> protected:
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3PureCSEcpp"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/b3/B3PureCSE.cpp (0 => 195417)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3PureCSE.cpp (rev 0)
+++ trunk/Source/JavaScriptCore/b3/B3PureCSE.cpp 2016-01-21 19:54:51 UTC (rev 195417)
</span><span class="lines">@@ -0,0 +1,74 @@
</span><ins>+/*
+ * Copyright (C) 2016 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "B3PureCSE.h"
+
+#if ENABLE(B3_JIT)
+
+#include "B3Dominators.h"
+#include "B3Value.h"
+
+namespace JSC { namespace B3 {
+
+PureCSE::PureCSE()
+{
+}
+
+PureCSE::~PureCSE()
+{
+}
+
+void PureCSE::clear()
+{
+ m_map.clear();
+}
+
+bool PureCSE::process(Value* value, Dominators& dominators)
+{
+ if (value->opcode() == Identity)
+ return false;
+
+ ValueKey key = value->key();
+ if (!key)
+ return false;
+
+ Matches& matches = m_map.add(key, Matches()).iterator->value;
+
+ for (Value* match : matches) {
+ if (dominators.dominates(match->owner, value->owner)) {
+ value->replaceWithIdentity(match);
+ return true;
+ }
+ }
+
+ matches.append(value);
+ return false;
+}
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3PureCSEh"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/b3/B3PureCSE.h (0 => 195417)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3PureCSE.h (rev 0)
+++ trunk/Source/JavaScriptCore/b3/B3PureCSE.h 2016-01-21 19:54:51 UTC (rev 195417)
</span><span class="lines">@@ -0,0 +1,62 @@
</span><ins>+/*
+ * Copyright (C) 2016 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef B3PureCSE_h
+#define B3PureCSE_h
+
+#if ENABLE(B3_JIT)
+
+#include "B3ValueKey.h"
+#include <wtf/HashMap.h>
+#include <wtf/Vector.h>
+
+namespace JSC { namespace B3 {
+
+class Dominators;
+class Value;
+
+typedef Vector<Value*, 1> Matches;
+
+// This is a reusable utility for doing pure CSE. You can use it to do pure CSE on a program by just
+// proceeding in order an calling process().
+class PureCSE {
+public:
+ PureCSE();
+ ~PureCSE();
+
+ void clear();
+
+ bool process(Value*, Dominators&);
+
+private:
+ HashMap<ValueKey, Matches> m_map;
+};
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
+#endif // B3PureCSE_h
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3ReduceStrengthcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3ReduceStrength.cpp (195416 => 195417)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3ReduceStrength.cpp 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/JavaScriptCore/b3/B3ReduceStrength.cpp 2016-01-21 19:54:51 UTC (rev 195417)
</span><span class="lines">@@ -38,6 +38,7 @@
</span><span class="cx"> #include "B3PhaseScope.h"
</span><span class="cx"> #include "B3PhiChildren.h"
</span><span class="cx"> #include "B3ProcedureInlines.h"
</span><ins>+#include "B3PureCSE.h"
</ins><span class="cx"> #include "B3UpsilonValue.h"
</span><span class="cx"> #include "B3UseCounts.h"
</span><span class="cx"> #include "B3ValueKey.h"
</span><span class="lines">@@ -282,7 +283,7 @@
</span><span class="cx">
</span><span class="cx"> m_proc.resetValueOwners();
</span><span class="cx"> m_dominators = &m_proc.dominators(); // Recompute if necessary.
</span><del>- m_pureValues.clear();
</del><ins>+ m_pureCSE.clear();
</ins><span class="cx">
</span><span class="cx"> for (BasicBlock* block : m_proc.blocksInPreOrder()) {
</span><span class="cx"> m_block = block;
</span><span class="lines">@@ -1751,31 +1752,7 @@
</span><span class="cx">
</span><span class="cx"> void replaceIfRedundant()
</span><span class="cx"> {
</span><del>- // This does a very simple pure dominator-based CSE. In the future we could add load elimination.
- // Note that if we add load elimination, we should do it by directly matching load and store
- // instructions instead of using the ValueKey functionality or doing DFG HeapLocation-like
- // things.
-
- // Don't bother with identities. We kill those anyway.
- if (m_value->opcode() == Identity)
- return;
-
- ValueKey key = m_value->key();
- if (!key)
- return;
-
- Vector<Value*, 1>& matches = m_pureValues.add(key, Vector<Value*, 1>()).iterator->value;
-
- // Replace this value with whichever value dominates us.
- for (Value* match : matches) {
- if (m_dominators->dominates(match->owner, m_value->owner)) {
- m_value->replaceWithIdentity(match);
- m_changed = true;
- return;
- }
- }
-
- matches.append(m_value);
</del><ins>+ m_changed |= m_pureCSE.process(m_value, *m_dominators);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void simplifyCFG()
</span><span class="lines">@@ -2042,7 +2019,7 @@
</span><span class="cx"> unsigned m_index { 0 };
</span><span class="cx"> Value* m_value { nullptr };
</span><span class="cx"> Dominators* m_dominators { nullptr };
</span><del>- HashMap<ValueKey, Vector<Value*, 1>> m_pureValues;
</del><ins>+ PureCSE m_pureCSE;
</ins><span class="cx"> bool m_changed { false };
</span><span class="cx"> bool m_changedCFG { false };
</span><span class="cx"> };
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3ReduceStrengthh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3ReduceStrength.h (195416 => 195417)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3ReduceStrength.h 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/JavaScriptCore/b3/B3ReduceStrength.h 2016-01-21 19:54:51 UTC (rev 195417)
</span><span class="lines">@@ -32,11 +32,13 @@
</span><span class="cx">
</span><span class="cx"> class Procedure;
</span><span class="cx">
</span><del>-// Does strength reduction, constant folding, canonicalization, CFG simplification, DCE, and CSE. This
-// phase runs those optimizations to fixpoint. The goal of the phase is to dramatically reduce the
-// complexity of the code. In the future, it's preferable to add optimizations to this phase rather than
-// creating new optimizations because then the optimizations can participate in the fixpoint. However,
-// this phase shouldn't become too expensive, so expensive optimizations should be separate.
</del><ins>+// Does strength reduction, constant folding, canonicalization, CFG simplification, DCE, and very
+// simple CSE. This phase runs those optimizations to fixpoint. The goal of the phase is to
+// dramatically reduce the complexity of the code. In the future, it's preferable to add optimizations
+// to this phase rather than creating new optimizations because then the optimizations can participate
+// in the fixpoint. However, because of the many interlocking optimizations, it can be difficult to
+// add sophisticated optimizations to it. For that reason we have full CSE in a different phase, for
+// example.
</ins><span class="cx">
</span><span class="cx"> bool reduceStrength(Procedure&);
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3Validatecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3Validate.cpp (195416 => 195417)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3Validate.cpp 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/JavaScriptCore/b3/B3Validate.cpp 2016-01-21 19:54:51 UTC (rev 195417)
</span><span class="lines">@@ -371,6 +371,8 @@
</span><span class="cx"> VALIDATE(value->type() == Void, ("At ", *value));
</span><span class="cx"> break;
</span><span class="cx"> }
</span><ins>+
+ VALIDATE(!(value->effects().writes && value->key()), ("At ", *value));
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (195416 => 195417)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/WTF/ChangeLog 2016-01-21 19:54:51 UTC (rev 195417)
</span><span class="lines">@@ -1,3 +1,41 @@
</span><ins>+2016-01-21 Filip Pizlo <fpizlo@apple.com>
+
+ B3 should have load elimination
+ https://bugs.webkit.org/show_bug.cgi?id=153288
+
+ Reviewed by Geoffrey Garen.
+
+ I needed a way to track sets of ranges, where there is a high likelihood that all of the
+ ranges overlap. So I created RangeSet. It's a usually-sorted list of coalesced ranges.
+ Practically this means that right now, FTL B3 will end up with two kinds of range sets: a set
+ that just contains top and a set that contains nothing. In the future, most sets will either
+ be top of empty but some of them will contain a handful of other things.
+
+ * WTF.xcodeproj/project.pbxproj:
+ * wtf/CMakeLists.txt:
+ * wtf/MathExtras.h:
+ (WTF::leftShiftWithSaturation):
+ (WTF::nonEmptyRangesOverlap):
+ (WTF::rangesOverlap):
+ * wtf/RangeSet.h: Added.
+ (WTF::RangeSet::RangeSet):
+ (WTF::RangeSet::~RangeSet):
+ (WTF::RangeSet::add):
+ (WTF::RangeSet::contains):
+ (WTF::RangeSet::overlaps):
+ (WTF::RangeSet::clear):
+ (WTF::RangeSet::dump):
+ (WTF::RangeSet::dumpRaw):
+ (WTF::RangeSet::compact):
+ (WTF::RangeSet::overlapsNonEmpty):
+ (WTF::RangeSet::subsumesNonEmpty):
+ (WTF::RangeSet::findRange):
+ * wtf/StdLibExtras.h:
+ (WTF::binarySearchImpl):
+ (WTF::binarySearch):
+ (WTF::tryBinarySearch):
+ (WTF::approximateBinarySearch):
+
</ins><span class="cx"> 2016-01-19 Ada Chan <adachan@apple.com>
</span><span class="cx">
</span><span class="cx"> Make it possible to enable VIDEO_PRESENTATION_MODE on other Cocoa platforms.
</span></span></pre></div>
<a id="trunkSourceWTFWTFxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (195416 => 195417)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2016-01-21 19:54:51 UTC (rev 195417)
</span><span class="lines">@@ -27,6 +27,7 @@
</span><span class="cx"> 0F3501641BB258D500F0A2A3 /* WeakRandom.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F3501631BB258C800F0A2A3 /* WeakRandom.h */; };
</span><span class="cx"> 0F4570431BE5B58F0062A629 /* Dominators.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4570421BE5B58F0062A629 /* Dominators.h */; };
</span><span class="cx"> 0F4570451BE834410062A629 /* BubbleSort.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4570441BE834410062A629 /* BubbleSort.h */; };
</span><ins>+ 0F725CAC1C50461600AD943A /* RangeSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F725CAB1C50461600AD943A /* RangeSet.h */; };
</ins><span class="cx"> 0F824A681B7443A0002E345D /* ParkingLot.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F824A641B7443A0002E345D /* ParkingLot.cpp */; };
</span><span class="cx"> 0F824A691B7443A0002E345D /* ParkingLot.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F824A651B7443A0002E345D /* ParkingLot.h */; };
</span><span class="cx"> 0F87105A16643F190090B0AD /* RawPointer.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F87105916643F190090B0AD /* RawPointer.h */; };
</span><span class="lines">@@ -332,6 +333,7 @@
</span><span class="cx"> 0F3501631BB258C800F0A2A3 /* WeakRandom.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WeakRandom.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F4570421BE5B58F0062A629 /* Dominators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Dominators.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F4570441BE834410062A629 /* BubbleSort.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BubbleSort.h; sourceTree = "<group>"; };
</span><ins>+ 0F725CAB1C50461600AD943A /* RangeSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RangeSet.h; sourceTree = "<group>"; };
</ins><span class="cx"> 0F824A641B7443A0002E345D /* ParkingLot.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ParkingLot.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0F824A651B7443A0002E345D /* ParkingLot.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ParkingLot.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F87105916643F190090B0AD /* RawPointer.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RawPointer.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -876,6 +878,7 @@
</span><span class="cx"> A8A472FB151A825B004123FF /* RandomNumber.cpp */,
</span><span class="cx"> A8A472FC151A825B004123FF /* RandomNumber.h */,
</span><span class="cx"> A8A472FD151A825B004123FF /* RandomNumberSeed.h */,
</span><ins>+ 0F725CAB1C50461600AD943A /* RangeSet.h */,
</ins><span class="cx"> 0F87105916643F190090B0AD /* RawPointer.h */,
</span><span class="cx"> A8A472FE151A825B004123FF /* RedBlackTree.h */,
</span><span class="cx"> 26299B6D17A9E5B800ADEBE5 /* Ref.h */,
</span><span class="lines">@@ -1168,6 +1171,7 @@
</span><span class="cx"> A8A473B4151A825B004123FF /* fast-dtoa.h in Headers */,
</span><span class="cx"> 0FD81AC5154FB22E00983E72 /* FastBitVector.h in Headers */,
</span><span class="cx"> A8A473C4151A825B004123FF /* FastMalloc.h in Headers */,
</span><ins>+ 0F725CAC1C50461600AD943A /* RangeSet.h in Headers */,
</ins><span class="cx"> B38FD7BD168953E80065C969 /* FeatureDefines.h in Headers */,
</span><span class="cx"> 0F9D3361165DBA73005AD387 /* FilePrintStream.h in Headers */,
</span><span class="cx"> A8A473B6151A825B004123FF /* fixed-dtoa.h in Headers */,
</span></span></pre></div>
<a id="trunkSourceWTFwtfCMakeListstxt"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/CMakeLists.txt (195416 => 195417)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/CMakeLists.txt 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2016-01-21 19:54:51 UTC (rev 195417)
</span><span class="lines">@@ -77,6 +77,7 @@
</span><span class="cx"> RAMSize.h
</span><span class="cx"> RandomNumber.h
</span><span class="cx"> RandomNumberSeed.h
</span><ins>+ RangeSet.h
</ins><span class="cx"> RawPointer.h
</span><span class="cx"> RedBlackTree.h
</span><span class="cx"> Ref.h
</span></span></pre></div>
<a id="trunkSourceWTFwtfMathExtrash"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/MathExtras.h (195416 => 195417)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/MathExtras.h 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/WTF/wtf/MathExtras.h 2016-01-21 19:54:51 UTC (rev 195417)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2006, 2007, 2008, 2009, 2010, 2013 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2006, 2007, 2008, 2009, 2010, 2013, 2016 Apple Inc. All rights reserved.
</ins><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="cx"> * modification, are permitted provided that the following conditions
</span><span class="lines">@@ -419,6 +419,20 @@
</span><span class="cx"> return result;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+// Check if two ranges overlap assuming that neither range is empty.
+template<typename T>
+inline bool nonEmptyRangesOverlap(T leftMin, T leftMax, T rightMin, T rightMax)
+{
+ ASSERT(leftMin < leftMax);
+ ASSERT(rightMin < rightMax);
+
+ if (leftMin <= rightMin && leftMax > rightMin)
+ return true;
+ if (rightMin <= leftMin && rightMax > leftMin)
+ return true;
+ return false;
+}
+
</ins><span class="cx"> // Pass ranges with the min being inclusive and the max being exclusive. For example, this should
</span><span class="cx"> // return false:
</span><span class="cx"> //
</span><span class="lines">@@ -434,12 +448,8 @@
</span><span class="cx"> return false;
</span><span class="cx"> if (rightMin == rightMax)
</span><span class="cx"> return false;
</span><del>-
- if (leftMin <= rightMin && leftMax > rightMin)
- return true;
- if (rightMin <= leftMin && rightMax > leftMin)
- return true;
- return false;
</del><ins>+
+ return nonEmptyRangesOverlap(leftMin, leftMax, rightMin, rightMax);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> } // namespace WTF
</span></span></pre></div>
<a id="trunkSourceWTFwtfRangeSeth"></a>
<div class="addfile"><h4>Added: trunk/Source/WTF/wtf/RangeSet.h (0 => 195417)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/RangeSet.h (rev 0)
+++ trunk/Source/WTF/wtf/RangeSet.h 2016-01-21 19:54:51 UTC (rev 195417)
</span><span class="lines">@@ -0,0 +1,213 @@
</span><ins>+/*
+ * Copyright (C) 2016 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef WTF_RangeSet_h
+#define WTF_RangeSet_h
+
+#include <wtf/ListDump.h>
+#include <wtf/MathExtras.h>
+#include <wtf/StdLibExtras.h>
+#include <wtf/Vector.h>
+
+namespace WTF {
+
+// A RangeSet is a set of numerical ranges. A value belongs to the set if it is within any of the
+// ranges. A range belongs to the set if every value in the range belongs to the set. A range overlaps
+// the set if any value in the range belongs to the set. You can add ranges and query range
+// membership. The internal representation is a list of ranges that gets periodically compacted. This
+// representation is optimal so long as the number of distinct ranges tends to be small, and the
+// number of range sets tends to be small as well. This works reasonably well in a bunch of compiler
+// algorithms, where the top range ends up being used a lot.
+//
+// The initial user of this is JSC::B3::HeapRange, which is used to perform alias analysis. You can
+// model new users on that class. Basically, you need to define:
+//
+// T::Type - the type of the members of the range. HeapRange uses unsigned.
+// T(T::Type begin, T::Type end) - construct a new range.
+// T::Type T::begin() const - instance method giving the inclusive beginning of the range.
+// T::Type T::end() const - instance method giving the exclusive end of the range.
+// void T::dump(PrintStream&) const - some kind of dumping.
+
+template<typename RangeType>
+class RangeSet {
+public:
+ typedef RangeType Range;
+ typedef typename Range::Type Type;
+
+ RangeSet()
+ {
+ }
+
+ ~RangeSet()
+ {
+ }
+
+ void add(const Range& range)
+ {
+ if (range.begin() == range.end())
+ return;
+
+ // We expect the range set to become top in a lot of cases. We also expect the same range to
+ // be added repeatedly. That's why this is here.
+ if (!m_ranges.isEmpty() && subsumesNonEmpty(m_ranges.last(), range))
+ return;
+
+ m_isCompact = false;
+
+ // We append without compacting only if doing so is guaranteed not to resize the vector.
+ if (m_ranges.size() + 1 < m_ranges.capacity()) {
+ m_ranges.append(range);
+ return;
+ }
+
+ m_ranges.append(range);
+ compact();
+ }
+
+ bool contains(const Range& range) const
+ {
+ if (range.begin() == range.end())
+ return false;
+
+ unsigned index = findRange(range);
+ if (index + 1 < m_ranges.size()
+ && subsumesNonEmpty(m_ranges[index + 1], range))
+ return true;
+ if (index < m_ranges.size()
+ && subsumesNonEmpty(m_ranges[index], range))
+ return true;
+ if (static_cast<unsigned>(index - 1) < m_ranges.size()
+ && subsumesNonEmpty(m_ranges[index - 1], range))
+ return true;
+ return false;
+ }
+
+ bool overlaps(const Range& range) const
+ {
+ if (range.begin() == range.end())
+ return false;
+
+ unsigned index = findRange(range);
+ if (index + 1 < m_ranges.size()
+ && overlapsNonEmpty(m_ranges[index + 1], range))
+ return true;
+ if (index < m_ranges.size()
+ && overlapsNonEmpty(m_ranges[index], range))
+ return true;
+ if (static_cast<unsigned>(index - 1) < m_ranges.size()
+ && overlapsNonEmpty(m_ranges[index - 1], range))
+ return true;
+ return false;
+ }
+
+ void clear()
+ {
+ m_ranges.clear();
+ m_isCompact = true;
+ }
+
+ void dump(PrintStream& out) const
+ {
+ const_cast<RangeSet*>(this)->compact();
+ out.print(listDump(m_ranges));
+ }
+
+ void dumpRaw(PrintStream& out) const
+ {
+ out.print("{", listDump(m_ranges), ", isCompact = ", m_isCompact, "}");
+ }
+
+private:
+ void compact()
+ {
+ if (m_isCompact)
+ return;
+
+ if (m_ranges.isEmpty()) {
+ m_isCompact = true;
+ return;
+ }
+
+ std::sort(
+ m_ranges.begin(), m_ranges.end(),
+ [&] (const Range& a, const Range& b) -> bool {
+ return a.begin() < b.begin();
+ });
+
+ unsigned srcIndex = 1;
+ unsigned dstIndex = 1;
+ Range* lastRange = &m_ranges[0];
+ while (srcIndex < m_ranges.size()) {
+ Range range = m_ranges[srcIndex++];
+ ASSERT(range.begin() >= lastRange->begin());
+ if (range.end() <= lastRange->end())
+ continue;
+ if (range.begin() <= lastRange->end()) {
+ *lastRange = Range(lastRange->begin(), range.end());
+ continue;
+ }
+ ASSERT(!overlapsNonEmpty(*lastRange, range));
+ lastRange = &m_ranges[dstIndex++];
+ *lastRange = range;
+ }
+ m_ranges.resize(dstIndex);
+
+ m_isCompact = true;
+ }
+
+ static bool overlapsNonEmpty(const Range& a, const Range& b)
+ {
+ return nonEmptyRangesOverlap(a.begin(), a.end(), b.begin(), b.end());
+ }
+
+ static bool subsumesNonEmpty(const Range& a, const Range& b)
+ {
+ return a.begin() <= b.begin() && a.end() >= b.end();
+ }
+
+ unsigned findRange(const Range& range) const
+ {
+ const_cast<RangeSet*>(this)->compact();
+
+ const Range* found = approximateBinarySearch<const Range, Type>(
+ m_ranges, m_ranges.size(), range.begin(), [&] (const Range* range) -> Type {
+ return range->begin();
+ });
+ if (!found)
+ return UINT_MAX;
+
+ return found - m_ranges.begin();
+ }
+
+ Vector<Range, 8> m_ranges;
+ bool m_isCompact { true };
+};
+
+} // namespace WTF
+
+using WTF::RangeSet;
+
+#endif // WTF_RangeSet_h
+
</ins></span></pre></div>
<a id="trunkSourceWTFwtfStdLibExtrash"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/StdLibExtras.h (195416 => 195417)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/StdLibExtras.h 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/WTF/wtf/StdLibExtras.h 2016-01-21 19:54:51 UTC (rev 195417)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2008 Apple Inc. All Rights Reserved.
</del><ins>+ * Copyright (C) 2008, 2016 Apple Inc. All Rights Reserved.
</ins><span class="cx"> * Copyright (C) 2013 Patrick Gansterer <paroga@paroga.com>
</span><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="lines">@@ -212,7 +212,7 @@
</span><span class="cx"> ASSERT(mode != KeyMustBePresentInArray || size);
</span><span class="cx"> }
</span><span class="cx">
</span><del>- if (mode == KeyMightNotBePresentInArray && !size)
</del><ins>+ if (mode != KeyMustBePresentInArray && !size)
</ins><span class="cx"> return 0;
</span><span class="cx">
</span><span class="cx"> ArrayElementType* result = &array[offset];
</span><span class="lines">@@ -230,38 +230,38 @@
</span><span class="cx">
</span><span class="cx"> // If the element is not found, crash if asserts are enabled, and behave like approximateBinarySearch in release builds.
</span><span class="cx"> template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
</span><del>-inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
</del><ins>+inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
</ins><span class="cx"> {
</span><span class="cx"> return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(array, size, key, extractKey);
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // Return zero if the element is not found.
</span><span class="cx"> template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
</span><del>-inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
</del><ins>+inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
</ins><span class="cx"> {
</span><span class="cx"> return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(array, size, key, extractKey);
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // Return the element that is either to the left, or the right, of where the element would have been found.
</span><span class="cx"> template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
</span><del>-inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
</del><ins>+inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
</ins><span class="cx"> {
</span><span class="cx"> return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(array, size, key, extractKey);
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // Variants of the above that use const.
</span><span class="cx"> template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
</span><del>-inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
</del><ins>+inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
</ins><span class="cx"> {
</span><span class="cx"> return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
</span><span class="cx"> }
</span><span class="cx"> template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
</span><del>-inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
</del><ins>+inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
</ins><span class="cx"> {
</span><span class="cx"> return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
</span><span class="cx"> }
</span><span class="cx"> template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
</span><del>-inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
</del><ins>+inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
</ins><span class="cx"> {
</span><span class="cx"> return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(const_cast<ArrayType&>(array), size, key, extractKey);
</span><span class="cx"> }
</span></span></pre>
</div>
</div>
</body>
</html>