<!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>[192851] 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/192851">192851</a></dd>
<dt>Author</dt> <dd>benjamin@webkit.org</dd>
<dt>Date</dt> <dd>2015-11-30 18:26:57 -0800 (Mon, 30 Nov 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>[JSC] Speed up Air Liveness Analysis on Tmps
https://bugs.webkit.org/show_bug.cgi?id=151556
Patch by Benjamin Poulain <bpoulain@apple.com> on 2015-11-30
Reviewed by Filip Pizlo.
Source/JavaScriptCore:
Liveness Analysis scales poorly on large graphs like the ones
generated by testComplex().
This patch introduces a faster of Liveness using the continuous indices
of values instead of the values themselves.
There are two main areas of improvements:
1) Reduce the cost of doing a LocalCalc over a BasicBlock.
2) Reduce how many LocalCalc are needed to converge to a solution.
Most of the costs of LocalCalc are from HashSet manipulations.
The HashSet operations are O(1) but the constant is large enough
to be a problem.
I used a similar trick as the Register Allocator to remove hashing
and collision handling: the absolute value of the Tmp is used as an index
into a flat array.
I used Briggs's Sparse Set implementation for the local live information
at each instruction. It has great properties for doing the local calculation:
-No memory reallocation.
-O(1) add() and remove() with a small constant.
-Strict O(n) iteration.
-O(1) clear().
The values Live-At-Head are now stored into a Vector. The Sparse Set
is used to maintain the Tmp uniqueness.
When forwarding new liveness at head to the predecessor, I start by removing
everything that was already in live-at-head. We can assume that any value
in that list has already been added to the predecessors.
This leaves us with a small-ish number of Tmps to add to live-at-head
and to the predecessors.
The speed up convergence, I used the same trick as DFG's liveness: keep
a set of dirty blocks to process. In practice, all the blocks without
back-edges converge quickly, and we only propagate liveness as needed.
This patch reduces the time taken by "testComplex(64, 384)" by another 5%.
The remaining things to do for Liveness are:
-Skip the first block for the fix point (it is often large and doing a local
calc on it is useless).
-Find a better Data Structure for live-at-tail (updating the HashSet takes
> 50% of the total convergence time).
* JavaScriptCore.xcodeproj/project.pbxproj:
* b3/air/AirIteratedRegisterCoalescing.cpp:
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::build):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::getAlias):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::getAliasWhenSpilling):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::allocatedReg):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::tmpArraySize):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::initializeDegrees):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::addEdges):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::addEdge):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::makeWorkList):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::simplify):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::forEachAdjacent):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::hasBeenSimplified):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::decrementDegree):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::forEachNodeMoves):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::isMoveRelated):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::enableMovesOnValue):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::precoloredCoalescingHeuristic):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::conservativeHeuristic):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::addWorkList):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::combine):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::freezeMoves):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::selectSpill):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::assignColors):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::dumpInterferenceGraphInDot):
(JSC::B3::Air::iteratedRegisterCoalescingOnType):
(JSC::B3::Air::iteratedRegisterCoalescing):
(JSC::B3::Air::AbsoluteTmpHelper<Arg::GP>::absoluteIndex): Deleted.
(JSC::B3::Air::AbsoluteTmpHelper<Arg::GP>::tmpFromAbsoluteIndex): Deleted.
(JSC::B3::Air::AbsoluteTmpHelper<Arg::FP>::absoluteIndex): Deleted.
(JSC::B3::Air::AbsoluteTmpHelper<Arg::FP>::tmpFromAbsoluteIndex): Deleted.
* b3/air/AirReportUsedRegisters.cpp:
(JSC::B3::Air::reportUsedRegisters):
* b3/air/AirTmpInlines.h:
(JSC::B3::Air::AbsoluteTmpMapper<Arg::GP>::absoluteIndex):
(JSC::B3::Air::AbsoluteTmpMapper<Arg::GP>::tmpFromAbsoluteIndex):
(JSC::B3::Air::AbsoluteTmpMapper<Arg::FP>::absoluteIndex):
(JSC::B3::Air::AbsoluteTmpMapper<Arg::FP>::tmpFromAbsoluteIndex):
* b3/air/AirLiveness.h: Added.
Source/WTF:
* WTF.xcodeproj/project.pbxproj:
* wtf/IndexSparseSet.h: Added.
(WTF::IndexSparseSet<OverflowHandler>::IndexSparseSet):
(WTF::IndexSparseSet<OverflowHandler>::add):
(WTF::IndexSparseSet<OverflowHandler>::remove):
(WTF::IndexSparseSet<OverflowHandler>::clear):
(WTF::IndexSparseSet<OverflowHandler>::size):
(WTF::IndexSparseSet<OverflowHandler>::isEmpty):
(WTF::IndexSparseSet<OverflowHandler>::contains):</pre>
<h3>Modified Paths</h3>
<ul>
<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="#trunkSourceJavaScriptCoreb3B3IndexMaph">trunk/Source/JavaScriptCore/b3/B3IndexMap.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirAllocateStackcpp">trunk/Source/JavaScriptCore/b3/air/AirAllocateStack.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirIteratedRegisterCoalescingcpp">trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirLivenessh">trunk/Source/JavaScriptCore/b3/air/AirLiveness.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirReportUsedRegisterscpp">trunk/Source/JavaScriptCore/b3/air/AirReportUsedRegisters.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirSpillEverythingcpp">trunk/Source/JavaScriptCore/b3/air/AirSpillEverything.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirTmpInlinesh">trunk/Source/JavaScriptCore/b3/air/AirTmpInlines.h</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>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceWTFwtfIndexSparseSeth">trunk/Source/WTF/wtf/IndexSparseSet.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (192850 => 192851)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-12-01 02:15:47 UTC (rev 192850)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-12-01 02:26:57 UTC (rev 192851)
</span><span class="lines">@@ -1,3 +1,96 @@
</span><ins>+2015-11-30 Benjamin Poulain <bpoulain@apple.com>
+
+ [JSC] Speed up Air Liveness Analysis on Tmps
+ https://bugs.webkit.org/show_bug.cgi?id=151556
+
+ Reviewed by Filip Pizlo.
+
+ Liveness Analysis scales poorly on large graphs like the ones
+ generated by testComplex().
+ This patch introduces a faster of Liveness using the continuous indices
+ of values instead of the values themselves.
+
+ There are two main areas of improvements:
+ 1) Reduce the cost of doing a LocalCalc over a BasicBlock.
+ 2) Reduce how many LocalCalc are needed to converge to a solution.
+
+ Most of the costs of LocalCalc are from HashSet manipulations.
+ The HashSet operations are O(1) but the constant is large enough
+ to be a problem.
+
+ I used a similar trick as the Register Allocator to remove hashing
+ and collision handling: the absolute value of the Tmp is used as an index
+ into a flat array.
+
+ I used Briggs's Sparse Set implementation for the local live information
+ at each instruction. It has great properties for doing the local calculation:
+ -No memory reallocation.
+ -O(1) add() and remove() with a small constant.
+ -Strict O(n) iteration.
+ -O(1) clear().
+
+ The values Live-At-Head are now stored into a Vector. The Sparse Set
+ is used to maintain the Tmp uniqueness.
+
+ When forwarding new liveness at head to the predecessor, I start by removing
+ everything that was already in live-at-head. We can assume that any value
+ in that list has already been added to the predecessors.
+ This leaves us with a small-ish number of Tmps to add to live-at-head
+ and to the predecessors.
+
+ The speed up convergence, I used the same trick as DFG's liveness: keep
+ a set of dirty blocks to process. In practice, all the blocks without
+ back-edges converge quickly, and we only propagate liveness as needed.
+
+ This patch reduces the time taken by "testComplex(64, 384)" by another 5%.
+
+ The remaining things to do for Liveness are:
+ -Skip the first block for the fix point (it is often large and doing a local
+ calc on it is useless).
+ -Find a better Data Structure for live-at-tail (updating the HashSet takes
+ > 50% of the total convergence time).
+
+ * JavaScriptCore.xcodeproj/project.pbxproj:
+ * b3/air/AirIteratedRegisterCoalescing.cpp:
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::build):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::getAlias):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::getAliasWhenSpilling):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::allocatedReg):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::tmpArraySize):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::initializeDegrees):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::addEdges):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::addEdge):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::makeWorkList):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::simplify):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::forEachAdjacent):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::hasBeenSimplified):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::decrementDegree):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::forEachNodeMoves):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::isMoveRelated):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::enableMovesOnValue):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::precoloredCoalescingHeuristic):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::conservativeHeuristic):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::addWorkList):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::combine):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::freezeMoves):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::selectSpill):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::assignColors):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::dumpInterferenceGraphInDot):
+ (JSC::B3::Air::iteratedRegisterCoalescingOnType):
+ (JSC::B3::Air::iteratedRegisterCoalescing):
+ (JSC::B3::Air::AbsoluteTmpHelper<Arg::GP>::absoluteIndex): Deleted.
+ (JSC::B3::Air::AbsoluteTmpHelper<Arg::GP>::tmpFromAbsoluteIndex): Deleted.
+ (JSC::B3::Air::AbsoluteTmpHelper<Arg::FP>::absoluteIndex): Deleted.
+ (JSC::B3::Air::AbsoluteTmpHelper<Arg::FP>::tmpFromAbsoluteIndex): Deleted.
+ * b3/air/AirReportUsedRegisters.cpp:
+ (JSC::B3::Air::reportUsedRegisters):
+ * b3/air/AirTmpInlines.h:
+ (JSC::B3::Air::AbsoluteTmpMapper<Arg::GP>::absoluteIndex):
+ (JSC::B3::Air::AbsoluteTmpMapper<Arg::GP>::tmpFromAbsoluteIndex):
+ (JSC::B3::Air::AbsoluteTmpMapper<Arg::FP>::absoluteIndex):
+ (JSC::B3::Air::AbsoluteTmpMapper<Arg::FP>::tmpFromAbsoluteIndex):
+ * b3/air/AirLiveness.h: Added.
+
</ins><span class="cx"> 2015-11-30 Saam barati <sbarati@apple.com>
</span><span class="cx">
</span><span class="cx"> FTL OSR Exits that are exception handlers should not have two different entrances. Instead, we should have two discrete OSR exits that do different things.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj (192850 => 192851)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2015-12-01 02:15:47 UTC (rev 192850)
+++ trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2015-12-01 02:26:57 UTC (rev 192851)
</span><span class="lines">@@ -814,7 +814,6 @@
</span><span class="cx"> 0FEC857F1BDACDC70080FF74 /* AirInst.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FEC855A1BDACDC70080FF74 /* AirInst.cpp */; };
</span><span class="cx"> 0FEC85801BDACDC70080FF74 /* AirInst.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC855B1BDACDC70080FF74 /* AirInst.h */; };
</span><span class="cx"> 0FEC85811BDACDC70080FF74 /* AirInstInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC855C1BDACDC70080FF74 /* AirInstInlines.h */; };
</span><del>- 0FEC85821BDACDC70080FF74 /* AirLiveness.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC855D1BDACDC70080FF74 /* AirLiveness.h */; };
</del><span class="cx"> 0FEC85831BDACDC70080FF74 /* AirPhaseScope.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FEC855E1BDACDC70080FF74 /* AirPhaseScope.cpp */; };
</span><span class="cx"> 0FEC85841BDACDC70080FF74 /* AirPhaseScope.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC855F1BDACDC70080FF74 /* AirPhaseScope.h */; };
</span><span class="cx"> 0FEC85851BDACDC70080FF74 /* AirRegisterPriority.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FEC85601BDACDC70080FF74 /* AirRegisterPriority.cpp */; };
</span><span class="lines">@@ -1088,6 +1087,7 @@
</span><span class="cx"> 2600B5A7152BAAA70091EE5F /* JSStringJoiner.h in Headers */ = {isa = PBXBuildFile; fileRef = 2600B5A5152BAAA70091EE5F /* JSStringJoiner.h */; };
</span><span class="cx"> 26718BA41BE99F780052017B /* AirIteratedRegisterCoalescing.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26718BA21BE99F780052017B /* AirIteratedRegisterCoalescing.cpp */; };
</span><span class="cx"> 26718BA51BE99F780052017B /* AirIteratedRegisterCoalescing.h in Headers */ = {isa = PBXBuildFile; fileRef = 26718BA31BE99F780052017B /* AirIteratedRegisterCoalescing.h */; };
</span><ins>+ 2684D4381C00161C0081D663 /* AirLiveness.h in Headers */ = {isa = PBXBuildFile; fileRef = 2684D4371C00161C0081D663 /* AirLiveness.h */; };
</ins><span class="cx"> 269D636E1BFBE5D100101B1D /* FTLB3Output.h in Headers */ = {isa = PBXBuildFile; fileRef = 269D636D1BFBE5D000101B1D /* FTLB3Output.h */; };
</span><span class="cx"> 26BB57601BFC4328005F12EB /* FTLB3Output.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26BB575F1BFC4328005F12EB /* FTLB3Output.cpp */; };
</span><span class="cx"> 2A05ABD51961DF2400341750 /* JSPropertyNameEnumerator.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 2A05ABD31961DF2400341750 /* JSPropertyNameEnumerator.cpp */; };
</span><span class="lines">@@ -2895,7 +2895,6 @@
</span><span class="cx"> 0FEC855A1BDACDC70080FF74 /* AirInst.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirInst.cpp; path = b3/air/AirInst.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0FEC855B1BDACDC70080FF74 /* AirInst.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirInst.h; path = b3/air/AirInst.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FEC855C1BDACDC70080FF74 /* AirInstInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirInstInlines.h; path = b3/air/AirInstInlines.h; sourceTree = "<group>"; };
</span><del>- 0FEC855D1BDACDC70080FF74 /* AirLiveness.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirLiveness.h; path = b3/air/AirLiveness.h; sourceTree = "<group>"; };
</del><span class="cx"> 0FEC855E1BDACDC70080FF74 /* AirPhaseScope.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirPhaseScope.cpp; path = b3/air/AirPhaseScope.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0FEC855F1BDACDC70080FF74 /* AirPhaseScope.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirPhaseScope.h; path = b3/air/AirPhaseScope.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FEC85601BDACDC70080FF74 /* AirRegisterPriority.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirRegisterPriority.cpp; path = b3/air/AirRegisterPriority.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -3124,6 +3123,7 @@
</span><span class="cx"> 264091FA1BE2FD4100684DB2 /* AirOpcode.opcodes */ = {isa = PBXFileReference; lastKnownFileType = text; name = AirOpcode.opcodes; path = b3/air/AirOpcode.opcodes; sourceTree = "<group>"; };
</span><span class="cx"> 26718BA21BE99F780052017B /* AirIteratedRegisterCoalescing.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirIteratedRegisterCoalescing.cpp; path = b3/air/AirIteratedRegisterCoalescing.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 26718BA31BE99F780052017B /* AirIteratedRegisterCoalescing.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirIteratedRegisterCoalescing.h; path = b3/air/AirIteratedRegisterCoalescing.h; sourceTree = "<group>"; };
</span><ins>+ 2684D4371C00161C0081D663 /* AirLiveness.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirLiveness.h; path = b3/air/AirLiveness.h; sourceTree = "<group>"; };
</ins><span class="cx"> 269D636D1BFBE5D000101B1D /* FTLB3Output.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = FTLB3Output.h; path = ftl/FTLB3Output.h; sourceTree = "<group>"; };
</span><span class="cx"> 26BB575F1BFC4328005F12EB /* FTLB3Output.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = FTLB3Output.cpp; path = ftl/FTLB3Output.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 2A05ABD31961DF2400341750 /* JSPropertyNameEnumerator.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JSPropertyNameEnumerator.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -4631,7 +4631,7 @@
</span><span class="cx"> 0FEC855C1BDACDC70080FF74 /* AirInstInlines.h */,
</span><span class="cx"> 26718BA21BE99F780052017B /* AirIteratedRegisterCoalescing.cpp */,
</span><span class="cx"> 26718BA31BE99F780052017B /* AirIteratedRegisterCoalescing.h */,
</span><del>- 0FEC855D1BDACDC70080FF74 /* AirLiveness.h */,
</del><ins>+ 2684D4371C00161C0081D663 /* AirLiveness.h */,
</ins><span class="cx"> 264091FA1BE2FD4100684DB2 /* AirOpcode.opcodes */,
</span><span class="cx"> 0FB3878C1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.cpp */,
</span><span class="cx"> 0FB3878D1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.h */,
</span><span class="lines">@@ -6674,7 +6674,6 @@
</span><span class="cx"> 0FEC857E1BDACDC70080FF74 /* AirInsertionSet.h in Headers */,
</span><span class="cx"> 0FEC85801BDACDC70080FF74 /* AirInst.h in Headers */,
</span><span class="cx"> 0FEC85811BDACDC70080FF74 /* AirInstInlines.h in Headers */,
</span><del>- 0FEC85821BDACDC70080FF74 /* AirLiveness.h in Headers */,
</del><span class="cx"> 0FEC85841BDACDC70080FF74 /* AirPhaseScope.h in Headers */,
</span><span class="cx"> 0FEC85861BDACDC70080FF74 /* AirRegisterPriority.h in Headers */,
</span><span class="cx"> 0F45703D1BE45F0A0062A629 /* AirReportUsedRegisters.h in Headers */,
</span><span class="lines">@@ -7697,6 +7696,7 @@
</span><span class="cx"> 0F572D4F16879FDD00E57FBD /* ThunkGenerator.h in Headers */,
</span><span class="cx"> A7386556118697B400540279 /* ThunkGenerators.h in Headers */,
</span><span class="cx"> 141448CD13A1783700F5BA1A /* TinyBloomFilter.h in Headers */,
</span><ins>+ 2684D4381C00161C0081D663 /* AirLiveness.h in Headers */,
</ins><span class="cx"> 0F55989817C86C5800A1E543 /* ToNativeFromValue.h in Headers */,
</span><span class="cx"> 0F2D4DE919832DAC007D4B19 /* ToThisStatus.h in Headers */,
</span><span class="cx"> 5D53726F0E1C54880021E549 /* Tracing.h in Headers */,
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3IndexMaph"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3IndexMap.h (192850 => 192851)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3IndexMap.h 2015-12-01 02:15:47 UTC (rev 192850)
+++ trunk/Source/JavaScriptCore/b3/B3IndexMap.h 2015-12-01 02:26:57 UTC (rev 192851)
</span><span class="lines">@@ -58,6 +58,11 @@
</span><span class="cx"> {
</span><span class="cx"> return m_vector[key->index()];
</span><span class="cx"> }
</span><ins>+
+ void clear()
+ {
+ m_vector.clear();
+ }
</ins><span class="cx">
</span><span class="cx"> private:
</span><span class="cx"> Vector<Value> m_vector;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirAllocateStackcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirAllocateStack.cpp (192850 => 192851)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirAllocateStack.cpp 2015-12-01 02:15:47 UTC (rev 192850)
+++ trunk/Source/JavaScriptCore/b3/air/AirAllocateStack.cpp 2015-12-01 02:26:57 UTC (rev 192851)
</span><span class="lines">@@ -136,16 +136,16 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // Now we handle the anonymous slots.
</span><del>- Liveness<StackSlot*> liveness(code);
</del><ins>+ StackSlotLiveness liveness(code);
</ins><span class="cx"> IndexMap<StackSlot, HashSet<StackSlot*>> interference(code.stackSlots().size());
</span><span class="cx"> Vector<StackSlot*> slots;
</span><span class="cx">
</span><span class="cx"> for (BasicBlock* block : code) {
</span><del>- Liveness<StackSlot*>::LocalCalc localCalc(liveness, block);
</del><ins>+ StackSlotLiveness::LocalCalc localCalc(liveness, block);
</ins><span class="cx">
</span><span class="cx"> auto interfere = [&] (Inst& inst) {
</span><span class="cx"> if (verbose)
</span><del>- dataLog("Interfering: ", pointerListDump(localCalc.live()), "\n");
</del><ins>+ dataLog("Interfering: ", WTF::pointerListDump(localCalc.live()), "\n");
</ins><span class="cx">
</span><span class="cx"> inst.forEachArg(
</span><span class="cx"> [&] (Arg& arg, Arg::Role role, Arg::Type) {
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirIteratedRegisterCoalescingcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp (192850 => 192851)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp 2015-12-01 02:15:47 UTC (rev 192850)
+++ trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp 2015-12-01 02:26:57 UTC (rev 192851)
</span><span class="lines">@@ -34,6 +34,7 @@
</span><span class="cx"> #include "AirLiveness.h"
</span><span class="cx"> #include "AirPhaseScope.h"
</span><span class="cx"> #include "AirRegisterPriority.h"
</span><ins>+#include "AirTmpInlines.h"
</ins><span class="cx"> #include <wtf/ListDump.h>
</span><span class="cx"> #include <wtf/ListHashSet.h>
</span><span class="cx">
</span><span class="lines">@@ -77,75 +78,100 @@
</span><span class="cx"> }
</span><span class="cx"> };
</span><span class="cx">
</span><del>-
-// The speed of the alocator depends directly on how fast we can query information associated with a Tmp
-// and/or its ownership to a set.
-//
-// HashSet/HashMap operations are overly expensive for that.
-//
-// Instead of a Hash structure, Tmp are indexed directly by value in Arrays. The internal integer is used as the index
-// to reference them quickly. In some sets, we do not care about the colored regs, we still allocate the memory for them
-// and just do not use it.
</del><span class="cx"> template<Arg::Type type>
</span><del>-struct AbsoluteTmpHelper;
-
-template<>
-struct AbsoluteTmpHelper<Arg::GP> {
- static unsigned absoluteIndex(const Tmp& tmp)
</del><ins>+class IteratedRegisterCoalescingAllocator {
+public:
+ IteratedRegisterCoalescingAllocator(Code& code, const HashSet<Tmp>& unspillableTmp)
+ : m_unspillableTmp(unspillableTmp)
+ , m_numberOfRegisters(regsInPriorityOrder(type).size())
</ins><span class="cx"> {
</span><del>- ASSERT(tmp.isGP());
- ASSERT(static_cast<int>(tmp.internalValue()) > 0);
- return tmp.internalValue();
</del><ins>+ initializeDegrees(code);
+
+ unsigned tmpArraySize = this->tmpArraySize(code);
+ m_adjacencyList.resize(tmpArraySize);
+ m_moveList.resize(tmpArraySize);
+ m_coalescedTmps.resize(tmpArraySize);
+ m_isOnSelectStack.ensureSize(tmpArraySize);
+
+ build(code);
+ allocate();
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- static unsigned absoluteIndex(unsigned tmpIndex)
</del><ins>+ Tmp getAlias(Tmp tmp) const
</ins><span class="cx"> {
</span><del>- return absoluteIndex(Tmp::gpTmpForIndex(tmpIndex));
</del><ins>+ Tmp alias = tmp;
+ while (Tmp nextAlias = m_coalescedTmps[AbsoluteTmpMapper<type>::absoluteIndex(alias)])
+ alias = nextAlias;
+ return alias;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- static Tmp tmpFromAbsoluteIndex(unsigned tmpIndex)
</del><ins>+ Tmp getAliasWhenSpilling(Tmp tmp) const
</ins><span class="cx"> {
</span><del>- return Tmp::tmpForInternalValue(tmpIndex);
</del><ins>+ ASSERT_WITH_MESSAGE(!m_spilledTmp.isEmpty(), "This function is only valid for coalescing during spilling.");
+
+ if (m_coalescedTmpsAtSpill.isEmpty())
+ return tmp;
+
+ Tmp alias = tmp;
+ while (Tmp nextAlias = m_coalescedTmpsAtSpill[AbsoluteTmpMapper<type>::absoluteIndex(alias)])
+ alias = nextAlias;
+
+ ASSERT_WITH_MESSAGE(!m_spilledTmp.contains(tmp) || alias == tmp, "The aliases at spill should always be colorable. Something went horribly wrong.");
+
+ return alias;
</ins><span class="cx"> }
</span><del>-};
</del><span class="cx">
</span><del>-template<>
-struct AbsoluteTmpHelper<Arg::FP> {
- static unsigned absoluteIndex(const Tmp& tmp)
</del><ins>+ const HashSet<Tmp>& spilledTmp() const { return m_spilledTmp; }
+ Reg allocatedReg(Tmp tmp) const
</ins><span class="cx"> {
</span><del>- ASSERT(tmp.isFP());
- ASSERT(static_cast<int>(tmp.internalValue()) < 0);
- return -tmp.internalValue();
</del><ins>+ ASSERT(!tmp.isReg());
+ ASSERT(m_coloredTmp.size());
+ ASSERT(tmp.isGP() == (type == Arg::GP));
+
+ Reg reg = m_coloredTmp[AbsoluteTmpMapper<type>::absoluteIndex(tmp)];
+ if (!reg) {
+ // We only care about Tmps that interfere. A Tmp that never interfere with anything
+ // can take any register.
+ reg = regsInPriorityOrder(type).first();
+ }
+ return reg;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- static unsigned absoluteIndex(unsigned tmpIndex)
</del><ins>+private:
+ static unsigned tmpArraySize(Code& code)
</ins><span class="cx"> {
</span><del>- return absoluteIndex(Tmp::fpTmpForIndex(tmpIndex));
</del><ins>+ unsigned numTmps = code.numTmps(type);
+ return AbsoluteTmpMapper<type>::absoluteIndex(numTmps);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- static Tmp tmpFromAbsoluteIndex(unsigned tmpIndex)
</del><ins>+ void initializeDegrees(Code& code)
</ins><span class="cx"> {
</span><del>- return Tmp::tmpForInternalValue(-tmpIndex);
</del><ins>+ unsigned tmpArraySize = this->tmpArraySize(code);
+ m_degrees.resize(tmpArraySize);
+
+ // All precolored registers have an "infinite" degree.
+ unsigned firstNonRegIndex = AbsoluteTmpMapper<type>::absoluteIndex(0);
+ for (unsigned i = 0; i < firstNonRegIndex; ++i)
+ m_degrees[i] = std::numeric_limits<unsigned>::max();
+
+ bzero(m_degrees.data() + firstNonRegIndex, (tmpArraySize - firstNonRegIndex) * sizeof(unsigned));
</ins><span class="cx"> }
</span><del>-};
</del><span class="cx">
</span><del>-template<Arg::Type type>
-class IteratedRegisterCoalescingAllocator {
-public:
- IteratedRegisterCoalescingAllocator(Code& code, const HashSet<Tmp>& unspillableTmp)
- : m_unspillableTmp(unspillableTmp)
- , m_numberOfRegisters(regsInPriorityOrder(type).size())
</del><ins>+ void build(Code& code)
</ins><span class="cx"> {
</span><del>- initializeDegrees(code);
-
- unsigned tmpArraySize = this->tmpArraySize(code);
- m_adjacencyList.resize(tmpArraySize);
- m_moveList.resize(tmpArraySize);
- m_coalescedTmps.resize(tmpArraySize);
- m_isOnSelectStack.ensureSize(tmpArraySize);
</del><ins>+ TmpLiveness<type> liveness(code);
+ for (BasicBlock* block : code) {
+ typename TmpLiveness<type>::LocalCalc localCalc(liveness, block);
+ for (unsigned instIndex = block->size(); instIndex--;) {
+ Inst& inst = block->at(instIndex);
+ Inst* nextInst = instIndex + 1 < block->size() ? &block->at(instIndex + 1) : nullptr;
+ build(inst, nextInst, localCalc);
+ localCalc.execute(instIndex);
+ }
+ }
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- void build(Inst& inst, Inst* nextInst, const Liveness<Tmp>::LocalCalc& localCalc)
</del><ins>+ void build(Inst& inst, Inst* nextInst, const typename TmpLiveness<type>::LocalCalc& localCalc)
</ins><span class="cx"> {
</span><span class="cx"> inst.forEachTmpWithExtraClobberedRegs(
</span><span class="cx"> nextInst,
</span><span class="lines">@@ -191,12 +217,12 @@
</span><span class="cx"> m_activeMoves.ensureSize(nextMoveIndex + 1);
</span><span class="cx">
</span><span class="cx"> for (const Arg& arg : inst.args) {
</span><del>- auto& list = m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(arg.tmp())];
</del><ins>+ auto& list = m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(arg.tmp())];
</ins><span class="cx"> list.add(nextMoveIndex);
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> for (const Tmp& liveTmp : localCalc.live()) {
</span><del>- if (liveTmp != useTmp && liveTmp.isGP() == (type == Arg::GP))
</del><ins>+ if (liveTmp != useTmp)
</ins><span class="cx"> addEdge(defTmp, liveTmp);
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -204,8 +230,10 @@
</span><span class="cx"> if (nextInst && nextInst->hasSpecial()) {
</span><span class="cx"> nextInst->extraEarlyClobberedRegs().forEach(
</span><span class="cx"> [&] (Reg reg) {
</span><del>- for (const Tmp& liveTmp : localCalc.live()) {
- addEdge(Tmp(reg), liveTmp);
</del><ins>+ if (reg.isGPR() == (type == Arg::GP)) {
+ for (const Tmp& liveTmp : localCalc.live()) {
+ addEdge(Tmp(reg), liveTmp);
+ }
</ins><span class="cx"> }
</span><span class="cx"> });
</span><span class="cx"> }
</span><span class="lines">@@ -213,105 +241,8 @@
</span><span class="cx"> addEdges(inst, nextInst, localCalc.live());
</span><span class="cx"> }
</span><span class="cx">
</span><del>- void allocate()
</del><ins>+ void addEdges(Inst& inst, Inst* nextInst, typename TmpLiveness<type>::LocalCalc::Iterable liveTmp)
</ins><span class="cx"> {
</span><del>- ASSERT_WITH_MESSAGE(m_activeMoves.size() >= m_coalescingCandidates.size(), "The activeMove set should be big enough for the quick operations of BitVector.");
-
- makeWorkList();
-
- if (debug) {
- dataLog("Interference: ", listDump(m_interferenceEdges), "\n");
- dumpInterferenceGraphInDot(WTF::dataFile());
- dataLog("Initial work list\n");
- dumpWorkLists(WTF::dataFile());
- }
-
- do {
- if (traceDebug) {
- dataLog("Before Graph simplification iteration\n");
- dumpWorkLists(WTF::dataFile());
- }
-
- if (!m_simplifyWorklist.isEmpty())
- simplify();
- else if (!m_worklistMoves.isEmpty())
- coalesce();
- else if (!m_freezeWorklist.isEmpty())
- freeze();
- else if (!m_spillWorklist.isEmpty())
- selectSpill();
-
- if (traceDebug) {
- dataLog("After Graph simplification iteration\n");
- dumpWorkLists(WTF::dataFile());
- }
- } while (!m_simplifyWorklist.isEmpty() || !m_worklistMoves.isEmpty() || !m_freezeWorklist.isEmpty() || !m_spillWorklist.isEmpty());
-
- assignColors();
- }
-
- Tmp getAlias(Tmp tmp) const
- {
- Tmp alias = tmp;
- while (Tmp nextAlias = m_coalescedTmps[AbsoluteTmpHelper<type>::absoluteIndex(alias)])
- alias = nextAlias;
- return alias;
- }
-
- Tmp getAliasWhenSpilling(Tmp tmp) const
- {
- ASSERT_WITH_MESSAGE(!m_spilledTmp.isEmpty(), "This function is only valid for coalescing during spilling.");
-
- if (m_coalescedTmpsAtSpill.isEmpty())
- return tmp;
-
- Tmp alias = tmp;
- while (Tmp nextAlias = m_coalescedTmpsAtSpill[AbsoluteTmpHelper<type>::absoluteIndex(alias)])
- alias = nextAlias;
-
- ASSERT_WITH_MESSAGE(!m_spilledTmp.contains(tmp) || alias == tmp, "The aliases at spill should always be colorable. Something went horribly wrong.");
-
- return alias;
- }
-
- const HashSet<Tmp>& spilledTmp() const { return m_spilledTmp; }
- Reg allocatedReg(Tmp tmp) const
- {
- ASSERT(!tmp.isReg());
- ASSERT(m_coloredTmp.size());
- ASSERT(tmp.isGP() == (type == Arg::GP));
-
- Reg reg = m_coloredTmp[AbsoluteTmpHelper<type>::absoluteIndex(tmp)];
- if (!reg) {
- // We only care about Tmps that interfere. A Tmp that never interfere with anything
- // can take any register.
- reg = regsInPriorityOrder(type).first();
- }
- return reg;
- }
-
-private:
- static unsigned tmpArraySize(Code& code)
- {
- unsigned numTmps = code.numTmps(type);
- return AbsoluteTmpHelper<type>::absoluteIndex(numTmps);
- }
-
- void initializeDegrees(Code& code)
- {
- unsigned tmpArraySize = this->tmpArraySize(code);
- m_degrees.resize(tmpArraySize);
-
- // All precolored registers have an "infinite" degree.
- unsigned firstNonRegIndex = AbsoluteTmpHelper<type>::absoluteIndex(0);
- for (unsigned i = 0; i < firstNonRegIndex; ++i)
- m_degrees[i] = std::numeric_limits<unsigned>::max();
-
- bzero(m_degrees.data() + firstNonRegIndex, (tmpArraySize - firstNonRegIndex) * sizeof(unsigned));
- }
-
- void addEdges(Inst& inst, Inst* nextInst, const HashSet<Tmp>& liveTmp)
- {
</del><span class="cx"> // All the Def()s interfere with everthing live.
</span><span class="cx"> inst.forEachTmpWithExtraClobberedRegs(
</span><span class="cx"> nextInst,
</span><span class="lines">@@ -333,32 +264,32 @@
</span><span class="cx">
</span><span class="cx"> if (m_interferenceEdges.add(InterferenceEdge(a, b)).isNewEntry) {
</span><span class="cx"> if (!a.isReg()) {
</span><del>- ASSERT(!m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(a)].contains(b));
- m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(a)].append(b);
- m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(a)]++;
</del><ins>+ ASSERT(!m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(a)].contains(b));
+ m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(a)].append(b);
+ m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(a)]++;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> if (!b.isReg()) {
</span><del>- ASSERT(!m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(b)].contains(a));
- m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(b)].append(a);
- m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(b)]++;
</del><ins>+ ASSERT(!m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(b)].contains(a));
+ m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(b)].append(a);
+ m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(b)]++;
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void makeWorkList()
</span><span class="cx"> {
</span><del>- unsigned firstNonRegIndex = AbsoluteTmpHelper<type>::absoluteIndex(0);
</del><ins>+ unsigned firstNonRegIndex = AbsoluteTmpMapper<type>::absoluteIndex(0);
</ins><span class="cx"> for (unsigned i = firstNonRegIndex; i < m_degrees.size(); ++i) {
</span><span class="cx"> unsigned degree = m_degrees[i];
</span><span class="cx"> if (!degree)
</span><span class="cx"> continue;
</span><span class="cx">
</span><del>- Tmp tmp = AbsoluteTmpHelper<type>::tmpFromAbsoluteIndex(i);
</del><ins>+ Tmp tmp = AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(i);
</ins><span class="cx">
</span><span class="cx"> if (degree >= m_numberOfRegisters)
</span><span class="cx"> m_spillWorklist.add(tmp);
</span><del>- else if (!m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)].isEmpty())
</del><ins>+ else if (!m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(tmp)].isEmpty())
</ins><span class="cx"> m_freezeWorklist.add(tmp);
</span><span class="cx"> else
</span><span class="cx"> m_simplifyWorklist.append(tmp);
</span><span class="lines">@@ -370,9 +301,9 @@
</span><span class="cx"> Tmp last = m_simplifyWorklist.takeLast();
</span><span class="cx">
</span><span class="cx"> ASSERT(!m_selectStack.contains(last));
</span><del>- ASSERT(!m_isOnSelectStack.get(AbsoluteTmpHelper<type>::absoluteIndex(last)));
</del><ins>+ ASSERT(!m_isOnSelectStack.get(AbsoluteTmpMapper<type>::absoluteIndex(last)));
</ins><span class="cx"> m_selectStack.append(last);
</span><del>- m_isOnSelectStack.quickSet(AbsoluteTmpHelper<type>::absoluteIndex(last));
</del><ins>+ m_isOnSelectStack.quickSet(AbsoluteTmpMapper<type>::absoluteIndex(last));
</ins><span class="cx">
</span><span class="cx"> forEachAdjacent(last, [this](Tmp adjacentTmp) {
</span><span class="cx"> decrementDegree(adjacentTmp);
</span><span class="lines">@@ -382,7 +313,7 @@
</span><span class="cx"> template<typename Function>
</span><span class="cx"> void forEachAdjacent(Tmp tmp, Function function)
</span><span class="cx"> {
</span><del>- for (Tmp adjacentTmp : m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]) {
</del><ins>+ for (Tmp adjacentTmp : m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]) {
</ins><span class="cx"> if (!hasBeenSimplified(adjacentTmp))
</span><span class="cx"> function(adjacentTmp);
</span><span class="cx"> }
</span><span class="lines">@@ -390,14 +321,14 @@
</span><span class="cx">
</span><span class="cx"> bool hasBeenSimplified(Tmp tmp)
</span><span class="cx"> {
</span><del>- return m_isOnSelectStack.quickGet(AbsoluteTmpHelper<type>::absoluteIndex(tmp)) || !!m_coalescedTmps[AbsoluteTmpHelper<type>::absoluteIndex(tmp)];
</del><ins>+ return m_isOnSelectStack.quickGet(AbsoluteTmpMapper<type>::absoluteIndex(tmp)) || !!m_coalescedTmps[AbsoluteTmpMapper<type>::absoluteIndex(tmp)];
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void decrementDegree(Tmp tmp)
</span><span class="cx"> {
</span><del>- ASSERT(m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]);
</del><ins>+ ASSERT(m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]);
</ins><span class="cx">
</span><del>- unsigned oldDegree = m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]--;
</del><ins>+ unsigned oldDegree = m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]--;
</ins><span class="cx"> if (oldDegree == m_numberOfRegisters) {
</span><span class="cx"> enableMovesOnValueAndAdjacents(tmp);
</span><span class="cx"> m_spillWorklist.remove(tmp);
</span><span class="lines">@@ -411,7 +342,7 @@
</span><span class="cx"> template<typename Function>
</span><span class="cx"> void forEachNodeMoves(Tmp tmp, Function function)
</span><span class="cx"> {
</span><del>- for (unsigned moveIndex : m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]) {
</del><ins>+ for (unsigned moveIndex : m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]) {
</ins><span class="cx"> if (m_activeMoves.quickGet(moveIndex) || m_worklistMoves.contains(moveIndex))
</span><span class="cx"> function(moveIndex);
</span><span class="cx"> }
</span><span class="lines">@@ -419,7 +350,7 @@
</span><span class="cx">
</span><span class="cx"> bool isMoveRelated(Tmp tmp)
</span><span class="cx"> {
</span><del>- for (unsigned moveIndex : m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]) {
</del><ins>+ for (unsigned moveIndex : m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]) {
</ins><span class="cx"> if (m_activeMoves.quickGet(moveIndex) || m_worklistMoves.contains(moveIndex))
</span><span class="cx"> return true;
</span><span class="cx"> }
</span><span class="lines">@@ -428,7 +359,7 @@
</span><span class="cx">
</span><span class="cx"> void enableMovesOnValue(Tmp tmp)
</span><span class="cx"> {
</span><del>- for (unsigned moveIndex : m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]) {
</del><ins>+ for (unsigned moveIndex : m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]) {
</ins><span class="cx"> if (m_activeMoves.quickClear(moveIndex))
</span><span class="cx"> m_worklistMoves.returnMove(moveIndex);
</span><span class="cx"> }
</span><span class="lines">@@ -500,11 +431,11 @@
</span><span class="cx"> // If any adjacent of the non-colored node is not an adjacent of the colored node AND has a degree >= K
</span><span class="cx"> // there is a risk that this node needs to have the same color as our precolored node. If we coalesce such
</span><span class="cx"> // move, we may create an uncolorable graph.
</span><del>- const auto& adjacentsOfV = m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(v)];
</del><ins>+ const auto& adjacentsOfV = m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(v)];
</ins><span class="cx"> for (Tmp adjacentTmp : adjacentsOfV) {
</span><span class="cx"> if (!adjacentTmp.isReg()
</span><span class="cx"> && !hasBeenSimplified(adjacentTmp)
</span><del>- && m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(adjacentTmp)] >= m_numberOfRegisters
</del><ins>+ && m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(adjacentTmp)] >= m_numberOfRegisters
</ins><span class="cx"> && !m_interferenceEdges.contains(InterferenceEdge(u, adjacentTmp)))
</span><span class="cx"> return false;
</span><span class="cx"> }
</span><span class="lines">@@ -522,8 +453,8 @@
</span><span class="cx"> ASSERT(!u.isReg());
</span><span class="cx"> ASSERT(!v.isReg());
</span><span class="cx">
</span><del>- const auto& adjacentsOfU = m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(u)];
- const auto& adjacentsOfV = m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(v)];
</del><ins>+ const auto& adjacentsOfU = m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(u)];
+ const auto& adjacentsOfV = m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(v)];
</ins><span class="cx">
</span><span class="cx"> if (adjacentsOfU.size() + adjacentsOfV.size() < m_numberOfRegisters) {
</span><span class="cx"> // Shortcut: if the total number of adjacents is less than the number of register, the condition is always met.
</span><span class="lines">@@ -535,7 +466,7 @@
</span><span class="cx"> for (Tmp adjacentTmp : adjacentsOfU) {
</span><span class="cx"> ASSERT(adjacentTmp != v);
</span><span class="cx"> ASSERT(adjacentTmp != u);
</span><del>- if (!hasBeenSimplified(adjacentTmp) && m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(adjacentTmp)] >= m_numberOfRegisters) {
</del><ins>+ if (!hasBeenSimplified(adjacentTmp) && m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(adjacentTmp)] >= m_numberOfRegisters) {
</ins><span class="cx"> auto addResult = highOrderAdjacents.add(adjacentTmp);
</span><span class="cx"> if (addResult.isNewEntry && highOrderAdjacents.size() >= m_numberOfRegisters)
</span><span class="cx"> return false;
</span><span class="lines">@@ -544,7 +475,7 @@
</span><span class="cx"> for (Tmp adjacentTmp : adjacentsOfV) {
</span><span class="cx"> ASSERT(adjacentTmp != u);
</span><span class="cx"> ASSERT(adjacentTmp != v);
</span><del>- if (!hasBeenSimplified(adjacentTmp) && m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(adjacentTmp)] >= m_numberOfRegisters) {
</del><ins>+ if (!hasBeenSimplified(adjacentTmp) && m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(adjacentTmp)] >= m_numberOfRegisters) {
</ins><span class="cx"> auto addResult = highOrderAdjacents.add(adjacentTmp);
</span><span class="cx"> if (addResult.isNewEntry && highOrderAdjacents.size() >= m_numberOfRegisters)
</span><span class="cx"> return false;
</span><span class="lines">@@ -557,7 +488,7 @@
</span><span class="cx">
</span><span class="cx"> void addWorkList(Tmp tmp)
</span><span class="cx"> {
</span><del>- if (!tmp.isReg() && m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(tmp)] < m_numberOfRegisters && !isMoveRelated(tmp)) {
</del><ins>+ if (!tmp.isReg() && m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(tmp)] < m_numberOfRegisters && !isMoveRelated(tmp)) {
</ins><span class="cx"> m_freezeWorklist.remove(tmp);
</span><span class="cx"> m_simplifyWorklist.append(tmp);
</span><span class="cx"> }
</span><span class="lines">@@ -568,18 +499,18 @@
</span><span class="cx"> if (!m_freezeWorklist.remove(v))
</span><span class="cx"> m_spillWorklist.remove(v);
</span><span class="cx">
</span><del>- ASSERT(!m_coalescedTmps[AbsoluteTmpHelper<type>::absoluteIndex(v)]);
- m_coalescedTmps[AbsoluteTmpHelper<type>::absoluteIndex(v)] = u;
</del><ins>+ ASSERT(!m_coalescedTmps[AbsoluteTmpMapper<type>::absoluteIndex(v)]);
+ m_coalescedTmps[AbsoluteTmpMapper<type>::absoluteIndex(v)] = u;
</ins><span class="cx">
</span><del>- auto& vMoves = m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(v)];
- m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(u)].add(vMoves.begin(), vMoves.end());
</del><ins>+ auto& vMoves = m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(v)];
+ m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(u)].add(vMoves.begin(), vMoves.end());
</ins><span class="cx">
</span><span class="cx"> forEachAdjacent(v, [this, u] (Tmp adjacentTmp) {
</span><span class="cx"> addEdge(adjacentTmp, u);
</span><span class="cx"> decrementDegree(adjacentTmp);
</span><span class="cx"> });
</span><span class="cx">
</span><del>- if (m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(u)] >= m_numberOfRegisters && m_freezeWorklist.remove(u))
</del><ins>+ if (m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(u)] >= m_numberOfRegisters && m_freezeWorklist.remove(u))
</ins><span class="cx"> m_spillWorklist.add(u);
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -600,7 +531,7 @@
</span><span class="cx"> const MoveOperands& moveOperands = m_coalescingCandidates[moveIndex];
</span><span class="cx"> Tmp originalOtherTmp = moveOperands.src != tmp ? moveOperands.src : moveOperands.dst;
</span><span class="cx"> Tmp otherTmp = getAlias(originalOtherTmp);
</span><del>- if (m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(otherTmp)] < m_numberOfRegisters && !isMoveRelated(otherTmp)) {
</del><ins>+ if (m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(otherTmp)] < m_numberOfRegisters && !isMoveRelated(otherTmp)) {
</ins><span class="cx"> if (m_freezeWorklist.remove(otherTmp))
</span><span class="cx"> m_simplifyWorklist.append(otherTmp);
</span><span class="cx"> }
</span><span class="lines">@@ -625,11 +556,11 @@
</span><span class="cx"> RELEASE_ASSERT_WITH_MESSAGE(iterator != m_spillWorklist.end(), "It is not possible to color the Air graph with the number of available registers.");
</span><span class="cx">
</span><span class="cx"> auto victimIterator = iterator;
</span><del>- unsigned maxDegree = m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(*iterator)];
</del><ins>+ unsigned maxDegree = m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(*iterator)];
</ins><span class="cx">
</span><span class="cx"> ++iterator;
</span><span class="cx"> for (;iterator != m_spillWorklist.end(); ++iterator) {
</span><del>- unsigned tmpDegree = m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(*iterator)];
</del><ins>+ unsigned tmpDegree = m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(*iterator)];
</ins><span class="cx"> if (tmpDegree > maxDegree) {
</span><span class="cx"> if (m_unspillableTmp.contains(*iterator))
</span><span class="cx"> continue;
</span><span class="lines">@@ -645,6 +576,43 @@
</span><span class="cx"> freezeMoves(victimTmp);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ void allocate()
+ {
+ ASSERT_WITH_MESSAGE(m_activeMoves.size() >= m_coalescingCandidates.size(), "The activeMove set should be big enough for the quick operations of BitVector.");
+
+ makeWorkList();
+
+ if (debug) {
+ dataLog("Interference: ", listDump(m_interferenceEdges), "\n");
+ dumpInterferenceGraphInDot(WTF::dataFile());
+ dataLog("Initial work list\n");
+ dumpWorkLists(WTF::dataFile());
+ }
+
+ do {
+ if (traceDebug) {
+ dataLog("Before Graph simplification iteration\n");
+ dumpWorkLists(WTF::dataFile());
+ }
+
+ if (!m_simplifyWorklist.isEmpty())
+ simplify();
+ else if (!m_worklistMoves.isEmpty())
+ coalesce();
+ else if (!m_freezeWorklist.isEmpty())
+ freeze();
+ else if (!m_spillWorklist.isEmpty())
+ selectSpill();
+
+ if (traceDebug) {
+ dataLog("After Graph simplification iteration\n");
+ dumpWorkLists(WTF::dataFile());
+ }
+ } while (!m_simplifyWorklist.isEmpty() || !m_worklistMoves.isEmpty() || !m_freezeWorklist.isEmpty() || !m_spillWorklist.isEmpty());
+
+ assignColors();
+ }
+
</ins><span class="cx"> void assignColors()
</span><span class="cx"> {
</span><span class="cx"> ASSERT(m_simplifyWorklist.isEmpty());
</span><span class="lines">@@ -668,17 +636,17 @@
</span><span class="cx"> while (!m_selectStack.isEmpty()) {
</span><span class="cx"> Tmp tmp = m_selectStack.takeLast();
</span><span class="cx"> ASSERT(!tmp.isReg());
</span><del>- ASSERT(!m_coloredTmp[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]);
</del><ins>+ ASSERT(!m_coloredTmp[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]);
</ins><span class="cx">
</span><span class="cx"> RegisterSet coloredRegisters;
</span><del>- for (Tmp adjacentTmp : m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]) {
</del><ins>+ for (Tmp adjacentTmp : m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]) {
</ins><span class="cx"> Tmp aliasTmp = getAlias(adjacentTmp);
</span><span class="cx"> if (aliasTmp.isReg()) {
</span><span class="cx"> coloredRegisters.set(aliasTmp.reg());
</span><span class="cx"> continue;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- Reg reg = m_coloredTmp[AbsoluteTmpHelper<type>::absoluteIndex(aliasTmp)];
</del><ins>+ Reg reg = m_coloredTmp[AbsoluteTmpMapper<type>::absoluteIndex(aliasTmp)];
</ins><span class="cx"> if (reg)
</span><span class="cx"> coloredRegisters.set(reg);
</span><span class="cx"> }
</span><span class="lines">@@ -686,7 +654,7 @@
</span><span class="cx"> bool colorAssigned = false;
</span><span class="cx"> for (Reg reg : registersInPriorityOrder) {
</span><span class="cx"> if (!coloredRegisters.get(reg)) {
</span><del>- m_coloredTmp[AbsoluteTmpHelper<type>::absoluteIndex(tmp)] = reg;
</del><ins>+ m_coloredTmp[AbsoluteTmpMapper<type>::absoluteIndex(tmp)] = reg;
</ins><span class="cx"> colorAssigned = true;
</span><span class="cx"> break;
</span><span class="cx"> }
</span><span class="lines">@@ -718,7 +686,7 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> for (const auto& tmp : tmpsWithInterferences)
</span><del>- out.print(" ", tmp.internalValue(), " [label=\"", tmp, " (", m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(tmp)], ")\"];\n");
</del><ins>+ out.print(" ", tmp.internalValue(), " [label=\"", tmp, " (", m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(tmp)], ")\"];\n");
</ins><span class="cx">
</span><span class="cx"> for (const auto& edge : m_interferenceEdges)
</span><span class="cx"> out.print(" ", edge.first().internalValue(), " -- ", edge.second().internalValue(), ";\n");
</span><span class="lines">@@ -1039,23 +1007,12 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template<Arg::Type type>
</span><del>-static void iteratedRegisterCoalescingOnType(Code& code, HashSet<Tmp>& unspillableTmps, unsigned& numIterations)
</del><ins>+static void iteratedRegisterCoalescingOnType(Code& code, unsigned& numIterations)
</ins><span class="cx"> {
</span><ins>+ HashSet<Tmp> unspillableTmps;
</ins><span class="cx"> while (true) {
</span><span class="cx"> numIterations++;
</span><span class="cx"> IteratedRegisterCoalescingAllocator<type> allocator(code, unspillableTmps);
</span><del>- Liveness<Tmp> liveness(code);
- for (BasicBlock* block : code) {
- Liveness<Tmp>::LocalCalc localCalc(liveness, block);
- for (unsigned instIndex = block->size(); instIndex--;) {
- Inst& inst = block->at(instIndex);
- Inst* nextInst = instIndex + 1 < block->size() ? &block->at(instIndex + 1) : nullptr;
- allocator.build(inst, nextInst, localCalc);
- localCalc.execute(instIndex);
- }
- }
-
- allocator.allocate();
</del><span class="cx"> if (allocator.spilledTmp().isEmpty()) {
</span><span class="cx"> assignRegisterToTmpInProgram(code, allocator);
</span><span class="cx"> return;
</span><span class="lines">@@ -1068,56 +1025,11 @@
</span><span class="cx"> {
</span><span class="cx"> PhaseScope phaseScope(code, "iteratedRegisterCoalescing");
</span><span class="cx">
</span><del>- bool gpIsColored = false;
- bool fpIsColored = false;
</del><span class="cx"> unsigned numIterations = 0;
</span><span class="cx">
</span><del>- HashSet<Tmp> unspillableGPs;
- HashSet<Tmp> unspillableFPs;
</del><ins>+ iteratedRegisterCoalescingOnType<Arg::GP>(code, numIterations);
+ iteratedRegisterCoalescingOnType<Arg::FP>(code, numIterations);
</ins><span class="cx">
</span><del>- // First we run both allocator together as long as they both spill.
- while (!gpIsColored && !fpIsColored) {
- numIterations++;
- IteratedRegisterCoalescingAllocator<Arg::GP> gpAllocator(code, unspillableGPs);
- IteratedRegisterCoalescingAllocator<Arg::FP> fpAllocator(code, unspillableFPs);
-
- // Liveness Analysis can be prohibitively expensive. It is shared
- // between the two allocators to avoid doing it twice.
- Liveness<Tmp> liveness(code);
- for (BasicBlock* block : code) {
- Liveness<Tmp>::LocalCalc localCalc(liveness, block);
- for (unsigned instIndex = block->size(); instIndex--;) {
- Inst& inst = block->at(instIndex);
- Inst* nextInst = instIndex + 1 < block->size() ? &block->at(instIndex + 1) : nullptr;
-
- gpAllocator.build(inst, nextInst, localCalc);
- fpAllocator.build(inst, nextInst, localCalc);
-
- localCalc.execute(instIndex);
- }
- }
-
- gpAllocator.allocate();
- fpAllocator.allocate();
-
- if (gpAllocator.spilledTmp().isEmpty()) {
- assignRegisterToTmpInProgram(code, gpAllocator);
- gpIsColored = true;
- } else
- addSpillAndFillToProgram<Arg::GP>(code, gpAllocator, unspillableGPs);
-
- if (fpAllocator.spilledTmp().isEmpty()) {
- assignRegisterToTmpInProgram(code, fpAllocator);
- fpIsColored = true;
- } else
- addSpillAndFillToProgram<Arg::FP>(code, fpAllocator, unspillableFPs);
- };
-
- if (!gpIsColored)
- iteratedRegisterCoalescingOnType<Arg::GP>(code, unspillableGPs, numIterations);
- if (!fpIsColored)
- iteratedRegisterCoalescingOnType<Arg::FP>(code, unspillableFPs, numIterations);
-
</del><span class="cx"> if (reportStats)
</span><span class="cx"> dataLog("Num iterations = ", numIterations, "\n");
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirLivenessh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirLiveness.h (192850 => 192851)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirLiveness.h 2015-12-01 02:15:47 UTC (rev 192850)
+++ trunk/Source/JavaScriptCore/b3/air/AirLiveness.h 2015-12-01 02:26:57 UTC (rev 192851)
</span><span class="lines">@@ -20,7 +20,7 @@
</span><span class="cx"> * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
</span><span class="cx"> * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
</span><span class="cx"> * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
</span><del>- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
</del><ins>+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
</ins><span class="cx"> */
</span><span class="cx">
</span><span class="cx"> #ifndef AirLiveness_h
</span><span class="lines">@@ -29,130 +29,236 @@
</span><span class="cx"> #if ENABLE(B3_JIT)
</span><span class="cx">
</span><span class="cx"> #include "AirBasicBlock.h"
</span><ins>+#include "AirTmpInlines.h"
</ins><span class="cx"> #include "B3IndexMap.h"
</span><span class="cx"> #include "B3IndexSet.h"
</span><ins>+#include <wtf/IndexSparseSet.h>
</ins><span class="cx">
</span><span class="cx"> namespace JSC { namespace B3 { namespace Air {
</span><span class="cx">
</span><del>-// You can compute liveness over Tmp's or over Arg's. If you compute over Arg's, you get both
-// stack liveness and tmp liveness.
-template<typename Thing>
-class Liveness {
-public:
- template<typename T>
- static bool isAlive(const T& thing) { return thing.isAlive(); }
</del><ins>+template<Arg::Type adapterType>
+struct TmpLivenessAdapter {
+ typedef Tmp Thing;
+ typedef HashSet<unsigned> IndexSet;
</ins><span class="cx">
</span><del>- static bool isAlive(StackSlot* slot) { return slot->kind() == StackSlotKind::Anonymous; }
-
- Liveness(Code& code)
</del><ins>+ TmpLivenessAdapter(Code&) { }
+
+ static unsigned maxIndex(Code& code)
</ins><span class="cx"> {
</span><del>- m_liveAtHead.resize(code.size());
- m_liveAtTail.resize(code.size());
</del><ins>+ unsigned numTmps = code.numTmps(adapterType);
+ return AbsoluteTmpMapper<adapterType>::absoluteIndex(numTmps);
+ }
+ static bool acceptsType(Arg::Type type) { return type == adapterType; }
+ static unsigned valueToIndex(Tmp tmp) { return AbsoluteTmpMapper<adapterType>::absoluteIndex(tmp); }
+ static Tmp indexToValue(unsigned index) { return AbsoluteTmpMapper<adapterType>::tmpFromAbsoluteIndex(index); }
+};
</ins><span class="cx">
</span><ins>+struct StackSlotLivenessAdapter {
+ typedef StackSlot* Thing;
+ typedef HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> IndexSet;
+
+ StackSlotLivenessAdapter(Code& code)
+ : m_code(code)
+ {
+ }
+
+ static unsigned maxIndex(Code& code)
+ {
+ return code.stackSlots().size() - 1;
+ }
+ static bool acceptsType(Arg::Type) { return true; }
+ static unsigned valueToIndex(StackSlot* stackSlot) { return stackSlot->index(); }
+ StackSlot* indexToValue(unsigned index) { return m_code.stackSlots()[index]; }
+
+private:
+ Code& m_code;
+};
+
+template<typename Adapter>
+class AbstractLiveness : private Adapter {
+ struct Workset;
+public:
+ AbstractLiveness(Code& code)
+ : Adapter(code)
+ , m_workset(Adapter::maxIndex(code))
+ , m_liveAtHead(code.size())
+ , m_liveAtTail(code.size())
+ {
</ins><span class="cx"> // The liveAtTail of each block automatically contains the LateUse's of the terminal.
</span><span class="cx"> for (BasicBlock* block : code) {
</span><del>- HashSet<Thing>& live = m_liveAtTail[block];
- block->last().forEach<Thing>(
- [&] (Thing& thing, Arg::Role role, Arg::Type) {
- if (Arg::isLateUse(role))
- live.add(thing);
</del><ins>+ typename Adapter::IndexSet& liveAtTail = m_liveAtTail[block];
+
+ block->last().forEach<typename Adapter::Thing>(
+ [&] (typename Adapter::Thing& thing, Arg::Role role, Arg::Type type) {
+ if (Arg::isLateUse(role) && Adapter::acceptsType(type))
+ liveAtTail.add(Adapter::valueToIndex(thing));
</ins><span class="cx"> });
</span><span class="cx"> }
</span><span class="cx">
</span><del>- IndexSet<BasicBlock> seen;
</del><ins>+ // Blocks with new live values at tail.
+ BitVector dirtyBlocks;
+ for (size_t blockIndex = 0; blockIndex < code.size(); ++blockIndex)
+ dirtyBlocks.set(blockIndex);
</ins><span class="cx">
</span><del>- bool changed = true;
- while (changed) {
</del><ins>+ bool changed;
+ do {
</ins><span class="cx"> changed = false;
</span><span class="cx">
</span><span class="cx"> for (size_t blockIndex = code.size(); blockIndex--;) {
</span><span class="cx"> BasicBlock* block = code.at(blockIndex);
</span><span class="cx"> if (!block)
</span><span class="cx"> continue;
</span><ins>+
+ if (!dirtyBlocks.quickClear(blockIndex))
+ continue;
+
</ins><span class="cx"> LocalCalc localCalc(*this, block);
</span><span class="cx"> for (size_t instIndex = block->size(); instIndex--;)
</span><span class="cx"> localCalc.execute(instIndex);
</span><del>- bool firstTime = seen.add(block);
- if (!firstTime && localCalc.live() == m_liveAtHead[block])
</del><ins>+
+ Vector<unsigned>& liveAtHead = m_liveAtHead[block];
+
+ // We only care about Tmps that were discovered in this iteration. It is impossible
+ // to remove a live value from the head.
+ // We remove all the values we already knew about so that we only have to deal with
+ // what is new in LiveAtHead.
+ if (m_workset.size() == liveAtHead.size())
+ m_workset.clear();
+ else {
+ for (unsigned liveIndexAtHead : liveAtHead)
+ m_workset.remove(liveIndexAtHead);
+ }
+
+ if (m_workset.isEmpty())
</ins><span class="cx"> continue;
</span><del>- changed = true;
</del><ins>+
+ liveAtHead.reserveCapacity(liveAtHead.size() + m_workset.size());
+ for (unsigned newValue : m_workset)
+ liveAtHead.uncheckedAppend(newValue);
+
</ins><span class="cx"> for (BasicBlock* predecessor : block->predecessors()) {
</span><del>- m_liveAtTail[predecessor].add(
- localCalc.live().begin(), localCalc.live().end());
</del><ins>+ typename Adapter::IndexSet& liveAtTail = m_liveAtTail[predecessor];
+ for (unsigned newValue : m_workset) {
+ if (liveAtTail.add(newValue)) {
+ if (dirtyBlocks.quickSet(predecessor->index()))
+ changed = true;
+ }
+ }
</ins><span class="cx"> }
</span><del>- m_liveAtHead[block] = localCalc.takeLive();
</del><span class="cx"> }
</span><del>- }
- }
</del><ins>+ } while (changed);
</ins><span class="cx">
</span><del>- const HashSet<Thing>& liveAtHead(BasicBlock* block) const
- {
- return m_liveAtHead[block];
</del><ins>+ m_liveAtHead.clear();
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- const HashSet<Thing>& liveAtTail(BasicBlock* block) const
- {
- return m_liveAtTail[block];
- }
-
</del><span class="cx"> // This calculator has to be run in reverse.
</span><span class="cx"> class LocalCalc {
</span><span class="cx"> public:
</span><del>- LocalCalc(Liveness& liveness, BasicBlock* block)
- : m_live(liveness.liveAtTail(block))
</del><ins>+ LocalCalc(AbstractLiveness& liveness, BasicBlock* block)
+ : m_liveness(liveness)
</ins><span class="cx"> , m_block(block)
</span><span class="cx"> {
</span><ins>+ auto& workset = liveness.m_workset;
+ workset.clear();
+ typename Adapter::IndexSet& liveAtTail = liveness.m_liveAtTail[block];
+ for (unsigned index : liveAtTail)
+ workset.add(index);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- const HashSet<Thing>& live() const { return m_live; }
- HashSet<Thing>&& takeLive() { return WTF::move(m_live); }
</del><ins>+ struct Iterator {
+ Iterator(Adapter& adapter, IndexSparseSet<UnsafeVectorOverflow>::const_iterator sparceSetIterator)
+ : m_adapter(adapter)
+ , m_sparceSetIterator(sparceSetIterator)
+ {
+ }
</ins><span class="cx">
</span><ins>+ Iterator& operator++()
+ {
+ ++m_sparceSetIterator;
+ return *this;
+ }
+
+ typename Adapter::Thing operator*() const
+ {
+ return m_adapter.indexToValue(*m_sparceSetIterator);
+ }
+
+ bool operator==(const Iterator& other) { return m_sparceSetIterator == other.m_sparceSetIterator; }
+ bool operator!=(const Iterator& other) { return m_sparceSetIterator != other.m_sparceSetIterator; }
+
+ private:
+ Adapter& m_adapter;
+ IndexSparseSet<UnsafeVectorOverflow>::const_iterator m_sparceSetIterator;
+ };
+
+ struct Iterable {
+ Iterable(AbstractLiveness& liveness)
+ : m_liveness(liveness)
+ {
+ }
+
+ Iterator begin() const { return Iterator(m_liveness, m_liveness.m_workset.begin()); }
+ Iterator end() const { return Iterator(m_liveness, m_liveness.m_workset.end()); }
+
+ private:
+ AbstractLiveness& m_liveness;
+ };
+
+ Iterable live() const
+ {
+ return Iterable(m_liveness);
+ }
+
</ins><span class="cx"> void execute(unsigned instIndex)
</span><span class="cx"> {
</span><span class="cx"> Inst& inst = m_block->at(instIndex);
</span><del>-
</del><ins>+ auto& workset = m_liveness.m_workset;
</ins><span class="cx"> // First handle def's.
</span><del>- inst.forEach<Thing>(
- [this] (Thing& arg, Arg::Role role, Arg::Type) {
- if (!isAlive(arg))
- return;
- if (Arg::isDef(role))
- m_live.remove(arg);
</del><ins>+ inst.forEach<typename Adapter::Thing>(
+ [&] (typename Adapter::Thing& thing, Arg::Role role, Arg::Type type) {
+ if (Arg::isDef(role) && Adapter::acceptsType(type))
+ workset.remove(Adapter::valueToIndex(thing));
</ins><span class="cx"> });
</span><span class="cx">
</span><span class="cx"> // Then handle use's.
</span><del>- inst.forEach<Thing>(
- [this] (Thing& arg, Arg::Role role, Arg::Type) {
- if (!isAlive(arg))
- return;
- if (Arg::isEarlyUse(role))
- m_live.add(arg);
</del><ins>+ inst.forEach<typename Adapter::Thing>(
+ [&] (typename Adapter::Thing& thing, Arg::Role role, Arg::Type type) {
+ if (Arg::isEarlyUse(role) && Adapter::acceptsType(type))
+ workset.add(Adapter::valueToIndex(thing));
</ins><span class="cx"> });
</span><span class="cx">
</span><span class="cx"> // And finally, handle the late use's of the previous instruction.
</span><span class="cx"> if (instIndex) {
</span><span class="cx"> Inst& prevInst = m_block->at(instIndex - 1);
</span><del>-
- prevInst.forEach<Thing>(
- [this] (Thing& arg, Arg::Role role, Arg::Type) {
- if (!Arg::isLateUse(role))
- return;
- if (isAlive(arg))
- m_live.add(arg);
</del><ins>+ prevInst.forEach<typename Adapter::Thing>(
+ [&] (typename Adapter::Thing& thing, Arg::Role role, Arg::Type type) {
+ if (Arg::isLateUse(role) && Adapter::acceptsType(type))
+ workset.add(Adapter::valueToIndex(thing));
</ins><span class="cx"> });
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> private:
</span><del>- HashSet<Thing> m_live;
</del><ins>+ AbstractLiveness& m_liveness;
</ins><span class="cx"> BasicBlock* m_block;
</span><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> private:
</span><del>- IndexMap<BasicBlock, HashSet<Thing>> m_liveAtHead;
- IndexMap<BasicBlock, HashSet<Thing>> m_liveAtTail;
</del><ins>+ friend class LocalCalc;
+ friend struct LocalCalc::Iterable;
+
+ IndexSparseSet<UnsafeVectorOverflow> m_workset;
+ IndexMap<BasicBlock, Vector<unsigned>> m_liveAtHead;
+ IndexMap<BasicBlock, typename Adapter::IndexSet> m_liveAtTail;
</ins><span class="cx"> };
</span><span class="cx">
</span><ins>+template<Arg::Type type>
+using TmpLiveness = AbstractLiveness<TmpLivenessAdapter<type>>;
+
+typedef AbstractLiveness<TmpLivenessAdapter<Arg::GP>> GPLiveness;
+typedef AbstractLiveness<TmpLivenessAdapter<Arg::FP>> FPLiveness;
+typedef AbstractLiveness<StackSlotLivenessAdapter> StackSlotLiveness;
+
</ins><span class="cx"> } } } // namespace JSC::B3::Air
</span><span class="cx">
</span><span class="cx"> #endif // ENABLE(B3_JIT)
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirReportUsedRegisterscpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirReportUsedRegisters.cpp (192850 => 192851)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirReportUsedRegisters.cpp 2015-12-01 02:15:47 UTC (rev 192850)
+++ trunk/Source/JavaScriptCore/b3/air/AirReportUsedRegisters.cpp 2015-12-01 02:26:57 UTC (rev 192851)
</span><span class="lines">@@ -41,22 +41,29 @@
</span><span class="cx">
</span><span class="cx"> // FIXME: We should tell liveness to only track Regs.
</span><span class="cx"> // https://bugs.webkit.org/show_bug.cgi?id=150751
</span><del>- Liveness<Tmp> liveness(code);
</del><ins>+ GPLiveness gpLiveness(code);
+ FPLiveness fpLiveness(code);
</ins><span class="cx">
</span><span class="cx"> for (BasicBlock* block : code) {
</span><del>- Liveness<Tmp>::LocalCalc localCalc(liveness, block);
</del><ins>+ GPLiveness::LocalCalc gpLocalCalc(gpLiveness, block);
+ FPLiveness::LocalCalc fpLocalCalc(fpLiveness, block);
</ins><span class="cx">
</span><span class="cx"> for (unsigned instIndex = block->size(); instIndex--;) {
</span><span class="cx"> Inst& inst = block->at(instIndex);
</span><span class="cx"> if (inst.hasSpecial()) {
</span><span class="cx"> RegisterSet registerSet;
</span><del>- for (Tmp tmp : localCalc.live()) {
- if (tmp.isReg())
- registerSet.set(tmp.reg());
</del><ins>+ for (Tmp tmp : gpLocalCalc.live()) {
+ ASSERT(tmp.isGP());
+ registerSet.set(tmp.reg());
</ins><span class="cx"> }
</span><ins>+ for (Tmp tmp : fpLocalCalc.live()) {
+ ASSERT(tmp.isFP());
+ registerSet.set(tmp.reg());
+ }
</ins><span class="cx"> inst.reportUsedRegisters(registerSet);
</span><span class="cx"> }
</span><del>- localCalc.execute(instIndex);
</del><ins>+ gpLocalCalc.execute(instIndex);
+ fpLocalCalc.execute(instIndex);
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirSpillEverythingcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirSpillEverything.cpp (192850 => 192851)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirSpillEverything.cpp 2015-12-01 02:15:47 UTC (rev 192850)
+++ trunk/Source/JavaScriptCore/b3/air/AirSpillEverything.cpp 2015-12-01 02:26:57 UTC (rev 192851)
</span><span class="lines">@@ -44,17 +44,24 @@
</span><span class="cx">
</span><span class="cx"> // We want to know the set of registers used at every point in every basic block.
</span><span class="cx"> IndexMap<BasicBlock, Vector<RegisterSet>> usedRegisters(code.size());
</span><del>- Liveness<Tmp> liveness(code);
</del><ins>+ GPLiveness gpLiveness(code);
+ FPLiveness fpLiveness(code);
</ins><span class="cx"> for (BasicBlock* block : code) {
</span><del>- Liveness<Tmp>::LocalCalc localCalc(liveness, block);
</del><ins>+ GPLiveness::LocalCalc gpLocalCalc(gpLiveness, block);
+ FPLiveness::LocalCalc fpLocalCalc(fpLiveness, block);
+
</ins><span class="cx"> usedRegisters[block].resize(block->size() + 1);
</span><span class="cx">
</span><span class="cx"> auto setUsedRegisters = [&] (unsigned index, Inst& inst) {
</span><span class="cx"> RegisterSet& registerSet = usedRegisters[block][index];
</span><del>- for (Tmp tmp : localCalc.live()) {
</del><ins>+ for (Tmp tmp : gpLocalCalc.live()) {
</ins><span class="cx"> if (tmp.isReg())
</span><span class="cx"> registerSet.set(tmp.reg());
</span><span class="cx"> }
</span><ins>+ for (Tmp tmp : fpLocalCalc.live()) {
+ if (tmp.isReg())
+ registerSet.set(tmp.reg());
+ }
</ins><span class="cx">
</span><span class="cx"> // Gotta account for dead assignments to registers. These may happen because the input
</span><span class="cx"> // code is suboptimal.
</span><span class="lines">@@ -69,7 +76,8 @@
</span><span class="cx"> for (unsigned instIndex = block->size(); instIndex--;) {
</span><span class="cx"> Inst& inst = block->at(instIndex);
</span><span class="cx"> setUsedRegisters(instIndex + 1, inst);
</span><del>- localCalc.execute(instIndex);
</del><ins>+ gpLocalCalc.execute(instIndex);
+ fpLocalCalc.execute(instIndex);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> Inst nop;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirTmpInlinesh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirTmpInlines.h (192850 => 192851)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirTmpInlines.h 2015-12-01 02:15:47 UTC (rev 192850)
+++ trunk/Source/JavaScriptCore/b3/air/AirTmpInlines.h 2015-12-01 02:26:57 UTC (rev 192851)
</span><span class="lines">@@ -38,6 +38,51 @@
</span><span class="cx"> *this = arg.tmp();
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+// When a Hash structure is too slow or when Sets contains most values, you can
+// use direct array addressing with Tmps.
+template<Arg::Type type>
+struct AbsoluteTmpMapper;
+
+template<>
+struct AbsoluteTmpMapper<Arg::GP> {
+ static unsigned absoluteIndex(const Tmp& tmp)
+ {
+ ASSERT(tmp.isGP());
+ ASSERT(static_cast<int>(tmp.internalValue()) > 0);
+ return tmp.internalValue();
+ }
+
+ static unsigned absoluteIndex(unsigned tmpIndex)
+ {
+ return absoluteIndex(Tmp::gpTmpForIndex(tmpIndex));
+ }
+
+ static Tmp tmpFromAbsoluteIndex(unsigned tmpIndex)
+ {
+ return Tmp::tmpForInternalValue(tmpIndex);
+ }
+};
+
+template<>
+struct AbsoluteTmpMapper<Arg::FP> {
+ static unsigned absoluteIndex(const Tmp& tmp)
+ {
+ ASSERT(tmp.isFP());
+ ASSERT(static_cast<int>(tmp.internalValue()) < 0);
+ return -tmp.internalValue();
+ }
+
+ static unsigned absoluteIndex(unsigned tmpIndex)
+ {
+ return absoluteIndex(Tmp::fpTmpForIndex(tmpIndex));
+ }
+
+ static Tmp tmpFromAbsoluteIndex(unsigned tmpIndex)
+ {
+ return Tmp::tmpForInternalValue(-tmpIndex);
+ }
+};
+
</ins><span class="cx"> } } } // namespace JSC::B3::Air
</span><span class="cx">
</span><span class="cx"> #endif // ENABLE(B3_JIT)
</span></span></pre></div>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (192850 => 192851)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog 2015-12-01 02:15:47 UTC (rev 192850)
+++ trunk/Source/WTF/ChangeLog 2015-12-01 02:26:57 UTC (rev 192851)
</span><span class="lines">@@ -1,3 +1,20 @@
</span><ins>+2015-11-30 Benjamin Poulain <bpoulain@apple.com>
+
+ [JSC] Speed up Air Liveness Analysis on Tmps
+ https://bugs.webkit.org/show_bug.cgi?id=151556
+
+ Reviewed by Filip Pizlo.
+
+ * WTF.xcodeproj/project.pbxproj:
+ * wtf/IndexSparseSet.h: Added.
+ (WTF::IndexSparseSet<OverflowHandler>::IndexSparseSet):
+ (WTF::IndexSparseSet<OverflowHandler>::add):
+ (WTF::IndexSparseSet<OverflowHandler>::remove):
+ (WTF::IndexSparseSet<OverflowHandler>::clear):
+ (WTF::IndexSparseSet<OverflowHandler>::size):
+ (WTF::IndexSparseSet<OverflowHandler>::isEmpty):
+ (WTF::IndexSparseSet<OverflowHandler>::contains):
+
</ins><span class="cx"> 2015-11-30 Tim Horton <timothy_horton@apple.com>
</span><span class="cx">
</span><span class="cx"> Get rid of the !USE(ASYNC_NSTEXTINPUTCLIENT) codepath
</span></span></pre></div>
<a id="trunkSourceWTFWTFxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (192850 => 192851)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-12-01 02:15:47 UTC (rev 192850)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-12-01 02:26:57 UTC (rev 192851)
</span><span class="lines">@@ -86,6 +86,7 @@
</span><span class="cx"> 1FA47C8B152502DA00568D1B /* WebCoreThread.h in Headers */ = {isa = PBXBuildFile; fileRef = 1FA47C89152502DA00568D1B /* WebCoreThread.h */; };
</span><span class="cx"> 26147B0A15DDCCDC00DDB907 /* IntegerToStringConversion.h in Headers */ = {isa = PBXBuildFile; fileRef = 26147B0815DDCCDC00DDB907 /* IntegerToStringConversion.h */; };
</span><span class="cx"> 26299B6E17A9E5B800ADEBE5 /* Ref.h in Headers */ = {isa = PBXBuildFile; fileRef = 26299B6D17A9E5B800ADEBE5 /* Ref.h */; };
</span><ins>+ 2684D4361C000D400081D663 /* IndexSparseSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 2684D4351C000D400081D663 /* IndexSparseSet.h */; };
</ins><span class="cx"> 2C05385415BC819000F21B96 /* GregorianDateTime.h in Headers */ = {isa = PBXBuildFile; fileRef = 2C05385315BC819000F21B96 /* GregorianDateTime.h */; };
</span><span class="cx"> 2CCD892A15C0390200285083 /* GregorianDateTime.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 2CCD892915C0390200285083 /* GregorianDateTime.cpp */; };
</span><span class="cx"> 2CDED0EF18115C38004DBA70 /* RunLoopCF.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 2CDED0EE18115C38004DBA70 /* RunLoopCF.cpp */; };
</span><span class="lines">@@ -386,6 +387,7 @@
</span><span class="cx"> 1FA47C89152502DA00568D1B /* WebCoreThread.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WebCoreThread.h; sourceTree = "<group>"; };
</span><span class="cx"> 26147B0815DDCCDC00DDB907 /* IntegerToStringConversion.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IntegerToStringConversion.h; sourceTree = "<group>"; };
</span><span class="cx"> 26299B6D17A9E5B800ADEBE5 /* Ref.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Ref.h; sourceTree = "<group>"; };
</span><ins>+ 2684D4351C000D400081D663 /* IndexSparseSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IndexSparseSet.h; sourceTree = "<group>"; };
</ins><span class="cx"> 2C05385315BC819000F21B96 /* GregorianDateTime.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = GregorianDateTime.h; sourceTree = "<group>"; };
</span><span class="cx"> 2CCD892915C0390200285083 /* GregorianDateTime.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = GregorianDateTime.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 2CDED0EE18115C38004DBA70 /* RunLoopCF.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RunLoopCF.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -801,6 +803,7 @@
</span><span class="cx"> A8A472B9151A825A004123FF /* HashTable.h */,
</span><span class="cx"> A8A472BA151A825A004123FF /* HashTraits.h */,
</span><span class="cx"> A8A472BB151A825A004123FF /* HexNumber.h */,
</span><ins>+ 2684D4351C000D400081D663 /* IndexSparseSet.h */,
</ins><span class="cx"> A8A472BC151A825A004123FF /* InlineASM.h */,
</span><span class="cx"> A70DA0821799F04D00529A9B /* Insertion.h */,
</span><span class="cx"> 7CDD7FF7186D291E007433CD /* IteratorAdaptors.h */,
</span><span class="lines">@@ -1229,6 +1232,7 @@
</span><span class="cx"> A748745317A0BDAE00FA04CB /* SixCharacterHash.h in Headers */,
</span><span class="cx"> A8A47426151A825B004123FF /* Spectrum.h in Headers */,
</span><span class="cx"> A8A47428151A825B004123FF /* StackBounds.h in Headers */,
</span><ins>+ 2684D4361C000D400081D663 /* IndexSparseSet.h in Headers */,
</ins><span class="cx"> FEDACD3E1630F83F00C69634 /* StackStats.h in Headers */,
</span><span class="cx"> A8A47429151A825B004123FF /* StaticConstructors.h in Headers */,
</span><span class="cx"> A8A4742A151A825B004123FF /* StdLibExtras.h in Headers */,
</span></span></pre></div>
<a id="trunkSourceWTFwtfIndexSparseSeth"></a>
<div class="addfile"><h4>Added: trunk/Source/WTF/wtf/IndexSparseSet.h (0 => 192851)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/IndexSparseSet.h (rev 0)
+++ trunk/Source/WTF/wtf/IndexSparseSet.h 2015-12-01 02:26:57 UTC (rev 192851)
</span><span class="lines">@@ -0,0 +1,143 @@
</span><ins>+/*
+ * Copyright (C) 2015 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 IndexSparseSet_h
+#define IndexSparseSet_h
+
+#include <wtf/Vector.h>
+
+namespace WTF {
+
+// IndexSparseSet is an efficient set of integers that can only be valued
+// between zero and size() - 1.
+//
+// The implementation is using Briggs Sparse Set representation. We allocate
+// memory from 0 to size() - 1 to do mapping in O(1), but we never initialize
+// that memory. When adding/removing values to the set, they are added in a list
+// and the corresponding bucket is initialized to the position in the list.
+//
+// The assumption here is that we only need a sparse subset of number live at any
+// time.
+
+template<typename OverflowHandler = CrashOnOverflow>
+class IndexSparseSet {
+ typedef Vector<unsigned, 0, OverflowHandler> ValueList;
+public:
+ explicit IndexSparseSet(unsigned maxValue);
+
+ void add(unsigned);
+ void remove(unsigned);
+ void clear();
+
+ unsigned size() const;
+ bool isEmpty() const;
+ bool contains(unsigned) const;
+
+ typedef typename ValueList::const_iterator const_iterator;
+ const_iterator begin() const;
+ const_iterator end() const;
+
+private:
+ Vector<unsigned, 0, OverflowHandler, 1> m_map;
+ ValueList m_values;
+};
+
+template<typename OverflowHandler>
+inline IndexSparseSet<OverflowHandler>::IndexSparseSet(unsigned maxValue)
+{
+ m_map.resize(maxValue + 1);
+}
+
+template<typename OverflowHandler>
+inline void IndexSparseSet<OverflowHandler>::add(unsigned value)
+{
+ if (contains(value))
+ return;
+
+ unsigned newPosition = m_values.size();
+ m_values.append(value);
+ m_map[value] = newPosition;
+}
+
+template<typename OverflowHandler>
+inline void IndexSparseSet<OverflowHandler>::remove(unsigned value)
+{
+ unsigned position = m_map[value];
+ if (position >= m_values.size())
+ return;
+
+ if (m_values[position] == value) {
+ unsigned lastValue = m_values.last();
+ m_values[position] = lastValue;
+ m_map[lastValue] = position;
+ m_values.removeLast();
+ }
+}
+
+template<typename OverflowHandler>
+void IndexSparseSet<OverflowHandler>::clear()
+{
+ m_values.resize(0);
+}
+
+template<typename OverflowHandler>
+unsigned IndexSparseSet<OverflowHandler>::size() const
+{
+ return m_values.size();
+}
+
+template<typename OverflowHandler>
+bool IndexSparseSet<OverflowHandler>::isEmpty() const
+{
+ return !size();
+}
+
+template<typename OverflowHandler>
+bool IndexSparseSet<OverflowHandler>::contains(unsigned value) const
+{
+ unsigned position = m_map[value];
+ if (position >= m_values.size())
+ return false;
+
+ return m_values[position] == value;
+}
+
+template<typename OverflowHandler>
+auto IndexSparseSet<OverflowHandler>::begin() const -> const_iterator
+{
+ return m_values.begin();
+}
+
+template<typename OverflowHandler>
+auto IndexSparseSet<OverflowHandler>::end() const -> const_iterator
+{
+ return m_values.end();
+}
+
+} // namespace WTF
+
+using WTF::IndexSparseSet;
+
+#endif // IndexSparseSet_h
</ins></span></pre>
</div>
</div>
</body>
</html>