<!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>[192292] trunk/Source/JavaScriptCore</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/192292">192292</a></dd>
<dt>Author</dt> <dd>benjamin@webkit.org</dd>
<dt>Date</dt> <dd>2015-11-10 21:10:43 -0800 (Tue, 10 Nov 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Air should allocate registers
https://bugs.webkit.org/show_bug.cgi?id=150457
Patch by Benjamin Poulain <bpoulain@apple.com> on 2015-11-10
Reviewed by Filip Pizlo.
This is a direct implementation of the Iterated Register Coalescing allocator.
* JavaScriptCore.xcodeproj/project.pbxproj:
* b3/air/AirGenerate.cpp:
(JSC::B3::Air::generate):
* b3/air/AirInstInlines.h:
* b3/air/AirIteratedRegisterCoalescing.cpp: Added.
(JSC::B3::Air::MoveInstHelper<Arg::GP>::mayBeCoalescable):
(JSC::B3::Air::MoveInstHelper<Arg::FP>::mayBeCoalescable):
(JSC::B3::Air::AbsoluteTmpHelper<Arg::GP>::absoluteIndex):
(JSC::B3::Air::AbsoluteTmpHelper<Arg::GP>::tmpFromAbsoluteIndex):
(JSC::B3::Air::AbsoluteTmpHelper<Arg::FP>::absoluteIndex):
(JSC::B3::Air::AbsoluteTmpHelper<Arg::FP>::tmpFromAbsoluteIndex):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::IteratedRegisterCoalescingAllocator):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::build):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::allocate):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::getAlias):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::spilledTmp):
(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::enableMovesOnValueAndAdjacents):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::coalesce):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::canBeSafelyCoalesced):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::precoloredCoalescingHeuristic):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::conservativeHeuristic):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::addWorkList):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::combine):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::freeze):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::freezeMoves):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::selectSpill):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::assignColors):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::dumpInterferenceGraphInDot):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::dumpWorkLists):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::InterferenceEdge):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::first):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::second):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::operator==):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::isHashTableDeletedValue):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::hash):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdgeHash::hash):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdgeHash::equal):
(JSC::B3::Air::isUselessMoveInst):
(JSC::B3::Air::assignRegisterToTmpInProgram):
(JSC::B3::Air::addSpillAndFillToProgram):
(JSC::B3::Air::iteratedRegisterCoalescingOnType):
(JSC::B3::Air::iteratedRegisterCoalescing):
* b3/air/AirIteratedRegisterCoalescing.h: Added.
* b3/air/AirTmp.h:
(JSC::B3::Air::Tmp::internalValue):
(JSC::B3::Air::Tmp::tmpForInternalValue):
* b3/testb3.cpp:
(JSC::B3::testSpillGP):
(JSC::B3::run):</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="#trunkSourceJavaScriptCoreb3airAirGeneratecpp">trunk/Source/JavaScriptCore/b3/air/AirGenerate.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirInstInlinesh">trunk/Source/JavaScriptCore/b3/air/AirInstInlines.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirTmph">trunk/Source/JavaScriptCore/b3/air/AirTmp.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3testb3cpp">trunk/Source/JavaScriptCore/b3/testb3.cpp</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreb3airAirIteratedRegisterCoalescingcpp">trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirIteratedRegisterCoalescingh">trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (192291 => 192292)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-11-11 04:29:59 UTC (rev 192291)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-11-11 05:10:43 UTC (rev 192292)
</span><span class="lines">@@ -1,3 +1,75 @@
</span><ins>+2015-11-10 Benjamin Poulain <bpoulain@apple.com>
+
+ Air should allocate registers
+ https://bugs.webkit.org/show_bug.cgi?id=150457
+
+ Reviewed by Filip Pizlo.
+
+ This is a direct implementation of the Iterated Register Coalescing allocator.
+
+ * JavaScriptCore.xcodeproj/project.pbxproj:
+ * b3/air/AirGenerate.cpp:
+ (JSC::B3::Air::generate):
+ * b3/air/AirInstInlines.h:
+ * b3/air/AirIteratedRegisterCoalescing.cpp: Added.
+ (JSC::B3::Air::MoveInstHelper<Arg::GP>::mayBeCoalescable):
+ (JSC::B3::Air::MoveInstHelper<Arg::FP>::mayBeCoalescable):
+ (JSC::B3::Air::AbsoluteTmpHelper<Arg::GP>::absoluteIndex):
+ (JSC::B3::Air::AbsoluteTmpHelper<Arg::GP>::tmpFromAbsoluteIndex):
+ (JSC::B3::Air::AbsoluteTmpHelper<Arg::FP>::absoluteIndex):
+ (JSC::B3::Air::AbsoluteTmpHelper<Arg::FP>::tmpFromAbsoluteIndex):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::IteratedRegisterCoalescingAllocator):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::build):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::allocate):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::getAlias):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::spilledTmp):
+ (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::enableMovesOnValueAndAdjacents):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::coalesce):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::canBeSafelyCoalesced):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::precoloredCoalescingHeuristic):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::conservativeHeuristic):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::addWorkList):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::combine):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::freeze):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::freezeMoves):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::selectSpill):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::assignColors):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::dumpInterferenceGraphInDot):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::dumpWorkLists):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::InterferenceEdge):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::first):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::second):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::operator==):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::isHashTableDeletedValue):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdge::hash):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdgeHash::hash):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::InterferenceEdgeHash::equal):
+ (JSC::B3::Air::isUselessMoveInst):
+ (JSC::B3::Air::assignRegisterToTmpInProgram):
+ (JSC::B3::Air::addSpillAndFillToProgram):
+ (JSC::B3::Air::iteratedRegisterCoalescingOnType):
+ (JSC::B3::Air::iteratedRegisterCoalescing):
+ * b3/air/AirIteratedRegisterCoalescing.h: Added.
+ * b3/air/AirTmp.h:
+ (JSC::B3::Air::Tmp::internalValue):
+ (JSC::B3::Air::Tmp::tmpForInternalValue):
+ * b3/testb3.cpp:
+ (JSC::B3::testSpillGP):
+ (JSC::B3::run):
+
</ins><span class="cx"> 2015-11-10 Filip Pizlo <fpizlo@apple.com>
</span><span class="cx">
</span><span class="cx"> Unreviewed, add a FIXME referencing https://bugs.webkit.org/show_bug.cgi?id=151128.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj (192291 => 192292)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2015-11-11 04:29:59 UTC (rev 192291)
+++ trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2015-11-11 05:10:43 UTC (rev 192292)
</span><span class="lines">@@ -1074,6 +1074,8 @@
</span><span class="cx"> 1ACF7377171CA6FB00C9BB1E /* Weak.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 1ACF7376171CA6FB00C9BB1E /* Weak.cpp */; };
</span><span class="cx"> 2600B5A6152BAAA70091EE5F /* JSStringJoiner.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 2600B5A4152BAAA70091EE5F /* JSStringJoiner.cpp */; };
</span><span class="cx"> 2600B5A7152BAAA70091EE5F /* JSStringJoiner.h in Headers */ = {isa = PBXBuildFile; fileRef = 2600B5A5152BAAA70091EE5F /* JSStringJoiner.h */; };
</span><ins>+ 26718BA41BE99F780052017B /* AirIteratedRegisterCoalescing.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26718BA21BE99F780052017B /* AirIteratedRegisterCoalescing.cpp */; };
+ 26718BA51BE99F780052017B /* AirIteratedRegisterCoalescing.h in Headers */ = {isa = PBXBuildFile; fileRef = 26718BA31BE99F780052017B /* AirIteratedRegisterCoalescing.h */; };
</ins><span class="cx"> 2A05ABD51961DF2400341750 /* JSPropertyNameEnumerator.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 2A05ABD31961DF2400341750 /* JSPropertyNameEnumerator.cpp */; };
</span><span class="cx"> 2A05ABD61961DF2400341750 /* JSPropertyNameEnumerator.h in Headers */ = {isa = PBXBuildFile; fileRef = 2A05ABD41961DF2400341750 /* JSPropertyNameEnumerator.h */; };
</span><span class="cx"> 2A111245192FCE79005EE18D /* CustomGetterSetter.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 2A111243192FCE79005EE18D /* CustomGetterSetter.cpp */; };
</span><span class="lines">@@ -3083,6 +3085,8 @@
</span><span class="cx"> 2600B5A4152BAAA70091EE5F /* JSStringJoiner.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JSStringJoiner.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 2600B5A5152BAAA70091EE5F /* JSStringJoiner.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JSStringJoiner.h; sourceTree = "<group>"; };
</span><span class="cx"> 264091FA1BE2FD4100684DB2 /* AirOpcode.opcodes */ = {isa = PBXFileReference; lastKnownFileType = text; name = AirOpcode.opcodes; path = b3/air/AirOpcode.opcodes; sourceTree = "<group>"; };
</span><ins>+ 26718BA21BE99F780052017B /* AirIteratedRegisterCoalescing.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirIteratedRegisterCoalescing.cpp; path = b3/air/AirIteratedRegisterCoalescing.cpp; sourceTree = "<group>"; };
+ 26718BA31BE99F780052017B /* AirIteratedRegisterCoalescing.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirIteratedRegisterCoalescing.h; path = b3/air/AirIteratedRegisterCoalescing.h; sourceTree = "<group>"; };
</ins><span class="cx"> 2A05ABD31961DF2400341750 /* JSPropertyNameEnumerator.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JSPropertyNameEnumerator.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 2A05ABD41961DF2400341750 /* JSPropertyNameEnumerator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JSPropertyNameEnumerator.h; sourceTree = "<group>"; };
</span><span class="cx"> 2A111243192FCE79005EE18D /* CustomGetterSetter.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CustomGetterSetter.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -4566,6 +4570,8 @@
</span><span class="cx"> 0FEC855A1BDACDC70080FF74 /* AirInst.cpp */,
</span><span class="cx"> 0FEC855B1BDACDC70080FF74 /* AirInst.h */,
</span><span class="cx"> 0FEC855C1BDACDC70080FF74 /* AirInstInlines.h */,
</span><ins>+ 26718BA21BE99F780052017B /* AirIteratedRegisterCoalescing.cpp */,
+ 26718BA31BE99F780052017B /* AirIteratedRegisterCoalescing.h */,
</ins><span class="cx"> 0FEC855D1BDACDC70080FF74 /* AirLiveness.h */,
</span><span class="cx"> 264091FA1BE2FD4100684DB2 /* AirOpcode.opcodes */,
</span><span class="cx"> 0FEC855E1BDACDC70080FF74 /* AirPhaseScope.cpp */,
</span><span class="lines">@@ -6652,6 +6658,7 @@
</span><span class="cx"> 0FEC85191BDACDAC0080FF74 /* B3Generate.h in Headers */,
</span><span class="cx"> 0FEC851A1BDACDAC0080FF74 /* B3GenericFrequentedBlock.h in Headers */,
</span><span class="cx"> 0FEC85C31BE167A00080FF74 /* B3HeapRange.h in Headers */,
</span><ins>+ 26718BA51BE99F780052017B /* AirIteratedRegisterCoalescing.h in Headers */,
</ins><span class="cx"> 0FEC851B1BDACDAC0080FF74 /* B3IndexMap.h in Headers */,
</span><span class="cx"> 0FEC851C1BDACDAC0080FF74 /* B3IndexSet.h in Headers */,
</span><span class="cx"> 0FEC85BA1BE1462F0080FF74 /* B3InsertionSet.h in Headers */,
</span><span class="lines">@@ -8909,6 +8916,7 @@
</span><span class="cx"> 7B0247561B8682E100542440 /* WASMFunctionParser.cpp in Sources */,
</span><span class="cx"> 7B39F76D1B62DE2E00360FB4 /* WASMModuleParser.cpp in Sources */,
</span><span class="cx"> 7B39F7721B63574D00360FB4 /* WASMReader.cpp in Sources */,
</span><ins>+ 26718BA41BE99F780052017B /* AirIteratedRegisterCoalescing.cpp in Sources */,
</ins><span class="cx"> FED94F2E171E3E2300BE77A4 /* Watchdog.cpp in Sources */,
</span><span class="cx"> 0F919D2515853CE0004A4E7D /* Watchpoint.cpp in Sources */,
</span><span class="cx"> 1ACF7377171CA6FB00C9BB1E /* Weak.cpp in Sources */,
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirGeneratecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirGenerate.cpp (192291 => 192292)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirGenerate.cpp 2015-11-11 04:29:59 UTC (rev 192291)
+++ trunk/Source/JavaScriptCore/b3/air/AirGenerate.cpp 2015-11-11 05:10:43 UTC (rev 192292)
</span><span class="lines">@@ -33,6 +33,7 @@
</span><span class="cx"> #include "AirEliminateDeadCode.h"
</span><span class="cx"> #include "AirGenerationContext.h"
</span><span class="cx"> #include "AirHandleCalleeSaves.h"
</span><ins>+#include "AirIteratedRegisterCoalescing.h"
</ins><span class="cx"> #include "AirReportUsedRegisters.h"
</span><span class="cx"> #include "AirSimplifyCFG.h"
</span><span class="cx"> #include "AirSpillEverything.h"
</span><span class="lines">@@ -68,8 +69,7 @@
</span><span class="cx">
</span><span class="cx"> // This is where we would have a real register allocator. Then, we could use spillEverything()
</span><span class="cx"> // in place of the register allocator only for testing.
</span><del>- // FIXME: https://bugs.webkit.org/show_bug.cgi?id=150457
- spillEverything(code);
</del><ins>+ iteratedRegisterCoalescing(code);
</ins><span class="cx">
</span><span class="cx"> // Prior to this point the prologue and epilogue is implicit. This makes it explicit. It also
</span><span class="cx"> // does things like identify which callee-saves we're using and saves them.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirInstInlinesh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirInstInlines.h (192291 => 192292)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirInstInlines.h 2015-11-11 04:29:59 UTC (rev 192291)
+++ trunk/Source/JavaScriptCore/b3/air/AirInstInlines.h 2015-11-11 05:10:43 UTC (rev 192292)
</span><span class="lines">@@ -67,7 +67,7 @@
</span><span class="cx"> // https://bugs.webkit.org/show_bug.cgi?id=151128
</span><span class="cx">
</span><span class="cx"> functor(stackSlot, role, type);
</span><del>- arg = Arg::stack(stackSlot);
</del><ins>+ arg = Arg::stack(stackSlot, arg.offset());
</ins><span class="cx"> });
</span><span class="cx"> }
</span><span class="cx"> };
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirIteratedRegisterCoalescingcpp"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp (0 => 192292)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp (rev 0)
+++ trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp 2015-11-11 05:10:43 UTC (rev 192292)
</span><span class="lines">@@ -0,0 +1,955 @@
</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.
+ */
+
+#include "config.h"
+#include "AirIteratedRegisterCoalescing.h"
+
+#if ENABLE(B3_JIT)
+
+#include "AirCode.h"
+#include "AirInsertionSet.h"
+#include "AirInstInlines.h"
+#include "AirLiveness.h"
+#include "AirPhaseScope.h"
+#include "AirRegisterPriority.h"
+#include <wtf/ListHashSet.h>
+
+namespace JSC { namespace B3 { namespace Air {
+
+static bool debug = false;
+static bool traceDebug = false;
+
+template<Arg::Type type>
+struct MoveInstHelper;
+
+template<>
+struct MoveInstHelper<Arg::GP> {
+ static bool mayBeCoalescable(const Inst& inst)
+ {
+ bool isMove = inst.opcode == Move;
+ if (!isMove)
+ return false;
+
+ ASSERT_WITH_MESSAGE(inst.args.size() == 2, "We assume coalecable moves only have two arguments in a few places.");
+ ASSERT(inst.args[0].isType(Arg::GP));
+ ASSERT(inst.args[1].isType(Arg::GP));
+
+ return inst.args[0].isTmp() && inst.args[1].isTmp();
+ }
+};
+
+template<>
+struct MoveInstHelper<Arg::FP> {
+ static bool mayBeCoalescable(const Inst& inst)
+ {
+ if (inst.opcode != MoveDouble)
+ return false;
+
+ ASSERT_WITH_MESSAGE(inst.args.size() == 2, "We assume coalecable moves only have two arguments in a few places.");
+ ASSERT(inst.args[0].isType(Arg::FP));
+ ASSERT(inst.args[1].isType(Arg::FP));
+
+ return inst.args[0].isTmp() && inst.args[1].isTmp();
+ }
+};
+
+
+// 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.
+template<Arg::Type type>
+struct AbsoluteTmpHelper;
+
+template<>
+struct AbsoluteTmpHelper<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 AbsoluteTmpHelper<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);
+ }
+};
+
+template<Arg::Type type>
+struct Bank;
+
+template<>
+struct Bank<Arg::GP> {
+ typedef GPRInfo Info;
+};
+
+template<>
+struct Bank<Arg::FP> {
+ typedef FPRInfo Info;
+};
+
+template<Arg::Type type>
+class IteratedRegisterCoalescingAllocator {
+public:
+ IteratedRegisterCoalescingAllocator(Code& code)
+ {
+ initializeDegrees(code);
+
+ unsigned tmpArraySize = this->tmpArraySize(code);
+ m_adjacencyList.resize(tmpArraySize);
+ m_moveList.resize(tmpArraySize);
+ m_coalescedTmps.resize(tmpArraySize);
+ m_isOnSelectStack.ensureSize(tmpArraySize);
+ }
+
+ void build(Inst& inst, const Liveness<Tmp>::LocalCalc& localCalc)
+ {
+ // All the Def()s interfere with eachother.
+ inst.forEachTmp([&] (Tmp& arg, Arg::Role role, Arg::Type argType) {
+ if (argType != type)
+ return;
+
+ if (Arg::isDef(role)) {
+ inst.forEachTmp([&] (Tmp& otherArg, Arg::Role role, Arg::Type) {
+ if (argType != type)
+ return;
+
+ if (Arg::isDef(role))
+ addEdge(arg, otherArg);
+ });
+ }
+ });
+
+ if (MoveInstHelper<type>::mayBeCoalescable(inst)) {
+ for (const Arg& arg : inst.args) {
+ HashSet<Inst*>& list = m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(arg.tmp())];
+ list.add(&inst);
+ }
+ m_worklistMoves.add(&inst);
+
+ // We do not want the Use() of this move to interfere with the Def(), even if it is live
+ // after the Move. If we were to add the interference edge, it would be impossible to
+ // coalesce the Move even if the two Tmp never interfere anywhere.
+ Tmp defTmp;
+ Tmp useTmp;
+ inst.forEachTmp([&defTmp, &useTmp] (Tmp& argTmp, Arg::Role role, Arg::Type) {
+ if (Arg::isDef(role))
+ defTmp = argTmp;
+ else {
+ ASSERT(Arg::isUse(role));
+ useTmp = argTmp;
+ }
+ });
+ ASSERT(defTmp);
+ ASSERT(useTmp);
+
+ for (const Tmp& liveTmp : localCalc.live()) {
+ if (liveTmp != useTmp && liveTmp.isGP() == (type == Arg::GP))
+ addEdge(defTmp, liveTmp);
+ }
+ } else
+ addEdges(inst, localCalc.live());
+ }
+
+ void allocate()
+ {
+ makeWorkList();
+
+ if (debug) {
+ 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;
+ }
+
+ 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, const HashSet<Tmp>& liveTmp)
+ {
+ // All the Def()s interfere with everthing live.
+ inst.forEachTmp([&] (Tmp& arg, Arg::Role role, Arg::Type argType) {
+ if (argType == type && Arg::isDef(role)) {
+ for (const Tmp& liveTmp : liveTmp) {
+ if (liveTmp.isGP() == (type == Arg::GP))
+ addEdge(arg, liveTmp);
+ }
+ }
+ });
+ }
+
+ void addEdge(const Tmp& a, const Tmp& b)
+ {
+ if (a == b)
+ return;
+
+ if (m_interferenceEdges.add(InterferenceEdge(a, b)).isNewEntry) {
+ if (!a.isReg()) {
+ ASSERT(!m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(a)].contains(b));
+ m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(a)].append(b);
+ m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(a)]++;
+ }
+
+ if (!b.isReg()) {
+ ASSERT(!m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(b)].contains(a));
+ m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(b)].append(a);
+ m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(b)]++;
+ }
+ }
+ }
+
+ void makeWorkList()
+ {
+ unsigned firstNonRegIndex = AbsoluteTmpHelper<type>::absoluteIndex(0);
+ for (unsigned i = firstNonRegIndex; i < m_degrees.size(); ++i) {
+ unsigned degree = m_degrees[i];
+ if (!degree)
+ continue;
+
+ Tmp tmp = AbsoluteTmpHelper<type>::tmpFromAbsoluteIndex(i);
+
+ if (degree >= Bank<type>::Info::numberOfRegisters)
+ m_spillWorklist.add(tmp);
+ else if (!m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)].isEmpty())
+ m_freezeWorklist.add(tmp);
+ else
+ m_simplifyWorklist.append(tmp);
+ }
+ }
+
+ void simplify()
+ {
+ Tmp last = m_simplifyWorklist.takeLast();
+
+ ASSERT(!m_selectStack.contains(last));
+ ASSERT(!m_isOnSelectStack.get(AbsoluteTmpHelper<type>::absoluteIndex(last)));
+ m_selectStack.append(last);
+ m_isOnSelectStack.quickSet(AbsoluteTmpHelper<type>::absoluteIndex(last));
+
+ forEachAdjacent(last, [this](Tmp adjacentTmp) {
+ decrementDegree(adjacentTmp);
+ });
+ }
+
+ template<typename Function>
+ void forEachAdjacent(Tmp tmp, Function function)
+ {
+ for (Tmp adjacentTmp : m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]) {
+ if (!hasBeenSimplified(adjacentTmp))
+ function(adjacentTmp);
+ }
+ }
+
+ bool hasBeenSimplified(Tmp tmp)
+ {
+ return m_isOnSelectStack.quickGet(AbsoluteTmpHelper<type>::absoluteIndex(tmp)) || !!m_coalescedTmps[AbsoluteTmpHelper<type>::absoluteIndex(tmp)];
+ }
+
+ void decrementDegree(Tmp tmp)
+ {
+ ASSERT(m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]);
+
+ unsigned oldDegree = m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]--;
+ if (oldDegree == Bank<type>::Info::numberOfRegisters) {
+ enableMovesOnValueAndAdjacents(tmp);
+ m_spillWorklist.remove(tmp);
+ if (isMoveRelated(tmp))
+ m_freezeWorklist.add(tmp);
+ else
+ m_simplifyWorklist.append(tmp);
+ }
+ }
+
+ template<typename Function>
+ void forEachNodeMoves(Tmp tmp, Function function)
+ {
+ for (Inst* inst : m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]) {
+ if (m_activeMoves.contains(inst) || m_worklistMoves.contains(inst))
+ function(*inst);
+ }
+ }
+
+ bool isMoveRelated(Tmp tmp)
+ {
+ for (Inst* inst : m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]) {
+ if (m_activeMoves.contains(inst) || m_worklistMoves.contains(inst))
+ return true;
+ }
+ return false;
+ }
+
+ void enableMovesOnValue(Tmp tmp)
+ {
+ for (Inst* inst : m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]) {
+ if (m_activeMoves.remove(inst))
+ m_worklistMoves.add(inst);
+ }
+ }
+
+ void enableMovesOnValueAndAdjacents(Tmp tmp)
+ {
+ enableMovesOnValue(tmp);
+
+ forEachAdjacent(tmp, [this] (Tmp adjacentTmp) {
+ enableMovesOnValue(adjacentTmp);
+ });
+ }
+
+ void coalesce()
+ {
+ Inst* moveInst = m_worklistMoves.takeLast();
+ ASSERT(moveInst->args.size() == 2);
+
+ Tmp u = moveInst->args[0].tmp();
+ u = getAlias(u);
+ Tmp v = moveInst->args[1].tmp();
+ v = getAlias(v);
+
+ if (v.isReg())
+ std::swap(u, v);
+
+ if (traceDebug)
+ dataLog("Coalescing ", *moveInst, " u = ", u, " v = ", v, "\n");
+
+ if (u == v) {
+ addWorkList(u);
+
+ if (traceDebug)
+ dataLog(" Coalesced\n");
+ } else if (v.isReg() || m_interferenceEdges.contains(InterferenceEdge(u, v))) {
+ addWorkList(u);
+ addWorkList(v);
+
+ if (traceDebug)
+ dataLog(" Constrained\n");
+ } else if (canBeSafelyCoalesced(u, v)) {
+ combine(u, v);
+ addWorkList(u);
+
+ if (traceDebug)
+ dataLog(" Safe Coalescing\n");
+ } else {
+ m_activeMoves.add(moveInst);
+
+ if (traceDebug)
+ dataLog(" Failed coalescing, added to active moves.\n");
+ }
+ }
+
+ bool canBeSafelyCoalesced(Tmp u, Tmp v)
+ {
+ ASSERT(!v.isReg());
+ if (u.isReg())
+ return precoloredCoalescingHeuristic(u, v);
+ return conservativeHeuristic(u, v);
+ }
+
+ bool precoloredCoalescingHeuristic(Tmp u, Tmp v)
+ {
+ ASSERT(u.isReg());
+ ASSERT(!v.isReg());
+
+ // If any adjacent of the non-colored node is not an adjacent of the colored node AND has a degree >= K
+ // there is a risk that this node needs to have the same color as our precolored node. If we coalesce such
+ // move, we may create an uncolorable graph.
+ auto adjacentsOfV = m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(v)];
+ for (Tmp adjacentTmp : adjacentsOfV) {
+ if (!adjacentTmp.isReg()
+ && !hasBeenSimplified(adjacentTmp)
+ && m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(adjacentTmp)] >= Bank<type>::Info::numberOfRegisters
+ && !m_interferenceEdges.contains(InterferenceEdge(u, adjacentTmp)))
+ return false;
+ }
+ return true;
+ }
+
+ bool conservativeHeuristic(Tmp u, Tmp v)
+ {
+ // This is using the Briggs' conservative coalescing rule:
+ // If the number of combined adjacent node with a degree >= K is less than K,
+ // it is safe to combine the two nodes. The reason is that we know that if the graph
+ // is colorable, we have fewer than K adjacents with high order and there is a color
+ // for the current node.
+ ASSERT(u != v);
+ ASSERT(!u.isReg());
+ ASSERT(!v.isReg());
+
+ auto adjacentsOfU = m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(u)];
+ auto adjacentsOfV = m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(v)];
+
+ if (adjacentsOfU.size() + adjacentsOfV.size() < Bank<type>::Info::numberOfRegisters) {
+ // Shortcut: if the total number of adjacents is less than the number of register, the condition is always met.
+ return true;
+ }
+
+ HashSet<Tmp> highOrderAdjacents;
+
+ for (Tmp adjacentTmp : adjacentsOfU) {
+ ASSERT(adjacentTmp != v);
+ ASSERT(adjacentTmp != u);
+ if (!hasBeenSimplified(adjacentTmp) && m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(adjacentTmp)] >= Bank<type>::Info::numberOfRegisters) {
+ auto addResult = highOrderAdjacents.add(adjacentTmp);
+ if (addResult.isNewEntry && highOrderAdjacents.size() >= Bank<type>::Info::numberOfRegisters)
+ return false;
+ }
+ }
+ for (Tmp adjacentTmp : adjacentsOfV) {
+ ASSERT(adjacentTmp != u);
+ ASSERT(adjacentTmp != v);
+ if (!hasBeenSimplified(adjacentTmp) && m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(adjacentTmp)] >= Bank<type>::Info::numberOfRegisters) {
+ auto addResult = highOrderAdjacents.add(adjacentTmp);
+ if (addResult.isNewEntry && highOrderAdjacents.size() >= Bank<type>::Info::numberOfRegisters)
+ return false;
+ }
+ }
+
+ ASSERT(highOrderAdjacents.size() < Bank<type>::Info::numberOfRegisters);
+ return true;
+ }
+
+ void addWorkList(Tmp tmp)
+ {
+ if (!tmp.isReg() && m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(tmp)] < Bank<type>::Info::numberOfRegisters && !isMoveRelated(tmp)) {
+ m_freezeWorklist.remove(tmp);
+ m_simplifyWorklist.append(tmp);
+ }
+ }
+
+ void combine(Tmp u, Tmp v)
+ {
+ if (!m_freezeWorklist.remove(v))
+ m_spillWorklist.remove(v);
+
+ ASSERT(!m_coalescedTmps[AbsoluteTmpHelper<type>::absoluteIndex(v)]);
+ m_coalescedTmps[AbsoluteTmpHelper<type>::absoluteIndex(v)] = u;
+
+ HashSet<Inst*>& vMoves = m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(v)];
+ m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(u)].add(vMoves.begin(), vMoves.end());
+
+ forEachAdjacent(v, [this, u] (Tmp adjacentTmp) {
+ addEdge(adjacentTmp, u);
+ decrementDegree(adjacentTmp);
+ });
+
+ if (m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(u)] >= Bank<type>::Info::numberOfRegisters && m_freezeWorklist.remove(u))
+ m_spillWorklist.add(u);
+ }
+
+ void freeze()
+ {
+ Tmp victim = m_freezeWorklist.takeAny();
+ m_simplifyWorklist.append(victim);
+ freezeMoves(victim);
+ }
+
+ void freezeMoves(Tmp tmp)
+ {
+ forEachNodeMoves(tmp, [this, tmp] (Inst& inst) {
+ if (!m_activeMoves.remove(&inst))
+ m_worklistMoves.remove(&inst);
+
+ Tmp otherTmp = inst.args[0].tmp() != tmp ? inst.args[0].tmp() : inst.args[1].tmp();
+ if (m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(otherTmp)] < Bank<type>::Info::numberOfRegisters && !isMoveRelated(otherTmp)) {
+ m_freezeWorklist.remove(otherTmp);
+ m_simplifyWorklist.append(otherTmp);
+ }
+ });
+ }
+
+ void selectSpill()
+ {
+ // FIXME: we should select a good candidate based on all the information we have.
+ // FIXME: we should never select a spilled tmp as we would never converge.
+
+ auto iterator = m_spillWorklist.begin();
+
+ auto victimIterator = iterator;
+ unsigned maxDegree = m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(*iterator)];
+
+ ++iterator;
+ for (;iterator != m_spillWorklist.end(); ++iterator) {
+ unsigned tmpDegree = m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(*iterator)];
+ if (tmpDegree > maxDegree) {
+ victimIterator = iterator;
+ maxDegree = tmpDegree;
+ }
+ }
+
+ Tmp victimTmp = *victimIterator;
+ m_spillWorklist.remove(victimIterator);
+ m_simplifyWorklist.append(victimTmp);
+ freezeMoves(victimTmp);
+ }
+
+ void assignColors()
+ {
+ ASSERT(m_simplifyWorklist.isEmpty());
+ ASSERT(m_worklistMoves.isEmpty());
+ ASSERT(m_freezeWorklist.isEmpty());
+ ASSERT(m_spillWorklist.isEmpty());
+
+ // Reclaim as much memory as possible.
+ m_interferenceEdges.clear();
+ m_degrees.clear();
+ m_moveList.clear();
+ m_worklistMoves.clear();
+ m_activeMoves.clear();
+ m_simplifyWorklist.clear();
+ m_spillWorklist.clear();
+ m_freezeWorklist.clear();
+
+ // Try to color the Tmp on the stack.
+ m_coloredTmp.resize(m_adjacencyList.size());
+ const auto& registersInPriorityOrder = regsInPriorityOrder(type);
+
+ while (!m_selectStack.isEmpty()) {
+ Tmp tmp = m_selectStack.takeLast();
+ ASSERT(!tmp.isReg());
+ ASSERT(!m_coloredTmp[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]);
+
+ RegisterSet coloredRegisters;
+ for (Tmp adjacentTmp : m_adjacencyList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]) {
+ Tmp aliasTmp = getAlias(adjacentTmp);
+ if (aliasTmp.isReg()) {
+ coloredRegisters.set(aliasTmp.reg());
+ continue;
+ }
+
+ Reg reg = m_coloredTmp[AbsoluteTmpHelper<type>::absoluteIndex(aliasTmp)];
+ if (reg)
+ coloredRegisters.set(reg);
+ }
+
+ bool colorAssigned = false;
+ for (Reg reg : registersInPriorityOrder) {
+ if (!coloredRegisters.get(reg)) {
+ m_coloredTmp[AbsoluteTmpHelper<type>::absoluteIndex(tmp)] = reg;
+ colorAssigned = true;
+ break;
+ }
+ }
+
+ if (!colorAssigned)
+ m_spilledTmp.add(tmp);
+ }
+ m_selectStack.clear();
+
+ if (!m_spilledTmp.isEmpty())
+ m_coloredTmp.clear();
+ }
+
+#pragma mark - Debugging helpers.
+
+ void dumpInterferenceGraphInDot(PrintStream& out)
+ {
+ out.print("graph InterferenceGraph { \n");
+
+ HashSet<Tmp> tmpsWithInterferences;
+ for (const auto& edge : m_interferenceEdges) {
+ tmpsWithInterferences.add(edge.first());
+ tmpsWithInterferences.add(edge.second());
+ }
+
+ for (const auto& tmp : tmpsWithInterferences)
+ out.print(" ", tmp.internalValue(), " [label=\"", tmp, " (", m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(tmp)], ")\"];\n");
+
+ for (const auto& edge : m_interferenceEdges)
+ out.print(" ", edge.first().internalValue(), " -- ", edge.second().internalValue(), ";\n");
+ out.print("}\n");
+ }
+
+ void dumpWorkLists(PrintStream& out)
+ {
+ out.print("Simplify work list:\n");
+ for (Tmp tmp : m_simplifyWorklist)
+ out.print(" ", tmp, "\n");
+ out.print("Moves work list:\n");
+ for (Inst* inst : m_worklistMoves)
+ out.print(" ", *inst, "\n");
+ out.print("Freeze work list:\n");
+ for (Tmp tmp : m_freezeWorklist)
+ out.print(" ", tmp, "\n");
+ out.print("Spill work list:\n");
+ for (Tmp tmp : m_spillWorklist)
+ out.print(" ", tmp, "\n");
+ }
+
+#pragma mark -
+
+ // Interference edges are not directed. An edge between any two Tmps is represented
+ // by the concatenated values of the smallest Tmp followed by the bigger Tmp.
+ class InterferenceEdge {
+ public:
+ InterferenceEdge()
+ {
+ }
+
+ InterferenceEdge(Tmp a, Tmp b)
+ {
+ ASSERT(a.internalValue());
+ ASSERT(b.internalValue());
+ ASSERT_WITH_MESSAGE(a != b, "A Tmp can never interfere with itself. Doing so would force it to be the superposition of two registers.");
+
+ unsigned aInternal = a.internalValue();
+ unsigned bInternal = b.internalValue();
+ if (bInternal < aInternal)
+ std::swap(aInternal, bInternal);
+ m_value = static_cast<uint64_t>(aInternal) << 32 | bInternal;
+ }
+
+ InterferenceEdge(WTF::HashTableDeletedValueType)
+ : m_value(std::numeric_limits<uint64_t>::max())
+ {
+ }
+
+ Tmp first() const
+ {
+ return Tmp::tmpForInternalValue(m_value >> 32);
+ }
+
+ Tmp second() const
+ {
+ return Tmp::tmpForInternalValue(m_value & 0xffffffff);
+ }
+
+ bool operator==(const InterferenceEdge other) const
+ {
+ return m_value == other.m_value;
+ }
+
+ bool isHashTableDeletedValue() const
+ {
+ return *this == InterferenceEdge(WTF::HashTableDeletedValue);
+ }
+
+ unsigned hash() const
+ {
+ return WTF::IntHash<uint64_t>::hash(m_value);
+ }
+
+ private:
+ uint64_t m_value { 0 };
+ };
+
+ struct InterferenceEdgeHash {
+ static unsigned hash(const InterferenceEdge& key) { return key.hash(); }
+ static bool equal(const InterferenceEdge& a, const InterferenceEdge& b) { return a == b; }
+ static const bool safeToCompareToEmptyOrDeleted = true;
+ };
+ typedef SimpleClassHashTraits<InterferenceEdge> InterferenceEdgeHashTraits;
+
+ // The interference graph.
+ HashSet<InterferenceEdge, InterferenceEdgeHash, InterferenceEdgeHashTraits> m_interferenceEdges;
+ Vector<Vector<Tmp, 0, UnsafeVectorOverflow, 4>, 0, UnsafeVectorOverflow> m_adjacencyList;
+ Vector<unsigned, 0, UnsafeVectorOverflow> m_degrees;
+
+ // List of every move instruction associated with a Tmp.
+ Vector<HashSet<Inst*>> m_moveList;
+
+ // Colors.
+ Vector<Reg, 0, UnsafeVectorOverflow> m_coloredTmp;
+ HashSet<Tmp> m_spilledTmp;
+
+ // Values that have been coalesced with an other value.
+ Vector<Tmp> m_coalescedTmps;
+
+ // The stack of Tmp removed from the graph and ready for coloring.
+ BitVector m_isOnSelectStack;
+ Vector<Tmp> m_selectStack;
+
+ // Work lists.
+ // Set of "move" enabled for possible coalescing.
+ ListHashSet<Inst*> m_worklistMoves;
+ // Set of "move" not yet ready for coalescing.
+ HashSet<Inst*> m_activeMoves;
+ // Low-degree, non-Move related.
+ Vector<Tmp> m_simplifyWorklist;
+ // High-degree Tmp.
+ HashSet<Tmp> m_spillWorklist;
+ // Low-degree, Move related.
+ HashSet<Tmp> m_freezeWorklist;
+};
+
+template<Arg::Type type>
+static bool isUselessMoveInst(const Inst& inst)
+{
+ return MoveInstHelper<type>::mayBeCoalescable(inst) && inst.args[0].tmp() == inst.args[1].tmp();
+}
+
+template<Arg::Type type>
+static void assignRegisterToTmpInProgram(Code& code, const IteratedRegisterCoalescingAllocator<type>& allocator)
+{
+ for (BasicBlock* block : code) {
+ // Give Tmp a valid register.
+ for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) {
+ Inst& inst = block->at(instIndex);
+ inst.forEachTmpFast([&] (Tmp& tmp) {
+ if (tmp.isReg() || tmp.isGP() == (type != Arg::GP))
+ return;
+
+ Tmp aliasTmp = allocator.getAlias(tmp);
+ Tmp assignedTmp;
+ if (aliasTmp.isReg())
+ assignedTmp = Tmp(aliasTmp.reg());
+ else {
+ auto reg = allocator.allocatedReg(aliasTmp);
+ ASSERT(reg);
+ assignedTmp = Tmp(reg);
+ }
+ ASSERT(assignedTmp.isReg());
+ tmp = assignedTmp;
+ });
+ }
+
+ // Remove all the useless moves we created in this block.
+ block->insts().removeAllMatching(isUselessMoveInst<type>);
+ }
+}
+
+template<Arg::Type type>
+static void addSpillAndFillToProgram(Code& code, const HashSet<Tmp>& spilledTmp)
+{
+ // Allocate stack slot for each spilled value.
+ HashMap<Tmp, StackSlot*> stackSlots;
+ for (Tmp tmp : spilledTmp) {
+ bool isNewTmp = stackSlots.add(tmp, code.addStackSlot(8, StackSlotKind::Anonymous)).isNewEntry;
+ ASSERT_UNUSED(isNewTmp, isNewTmp);
+ }
+
+ // Rewrite the program to get rid of the spilled Tmp.
+ InsertionSet insertionSet(code);
+ for (BasicBlock* block : code) {
+ for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) {
+ Inst& inst = block->at(instIndex);
+
+ // Try to replace the register use by memory use when possible.
+ for (unsigned i = 0; i < inst.args.size(); ++i) {
+ Arg& arg = inst.args[i];
+ if (arg.isTmp() && arg.type() == type && !arg.isReg()) {
+ auto stackSlotEntry = stackSlots.find(arg.tmp());
+ if (stackSlotEntry == stackSlots.end())
+ continue;
+
+ if (inst.admitsStack(i)) {
+ arg = Arg::stack(stackSlotEntry->value);
+ continue;
+ }
+ }
+ }
+
+ // For every other case, add Load/Store as needed.
+ inst.forEachTmp([&] (Tmp& tmp, Arg::Role role, Arg::Type argType) {
+ if (tmp.isReg() || argType != type)
+ return;
+
+ auto stackSlotEntry = stackSlots.find(tmp);
+ if (stackSlotEntry == stackSlots.end())
+ return;
+
+ Arg arg = Arg::stack(stackSlotEntry->value);
+ Opcode move = type == Arg::GP ? Move : MoveDouble;
+
+ if (Arg::isUse(role)) {
+ Tmp newTmp = code.newTmp(type);
+ insertionSet.insert(instIndex, move, inst.origin, arg, newTmp);
+ tmp = newTmp;
+ }
+ if (Arg::isDef(role))
+ insertionSet.insert(instIndex + 1, move, inst.origin, tmp, arg);
+ });
+ }
+ insertionSet.execute(block);
+ }
+}
+
+template<Arg::Type type>
+static void iteratedRegisterCoalescingOnType(Code& code)
+{
+ while (true) {
+ IteratedRegisterCoalescingAllocator<type> allocator(code);
+ 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);
+ allocator.build(inst, localCalc);
+ localCalc.execute(inst);
+ }
+ }
+
+ allocator.allocate();
+ if (allocator.spilledTmp().isEmpty()) {
+ assignRegisterToTmpInProgram(code, allocator);
+ return;
+ }
+ addSpillAndFillToProgram<type>(code, allocator.spilledTmp());
+ }
+}
+
+void iteratedRegisterCoalescing(Code& code)
+{
+ PhaseScope phaseScope(code, "iteratedRegisterCoalescing");
+
+ bool gpIsColored = false;
+ bool fpIsColored = false;
+
+ // First we run both allocator together as long as they both spill.
+ while (!gpIsColored && !fpIsColored) {
+ IteratedRegisterCoalescingAllocator<Arg::GP> gpAllocator(code);
+ IteratedRegisterCoalescingAllocator<Arg::FP> fpAllocator(code);
+
+ // 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);
+
+ gpAllocator.build(inst, localCalc);
+ fpAllocator.build(inst, localCalc);
+
+ localCalc.execute(inst);
+ }
+ }
+
+ gpAllocator.allocate();
+ if (gpAllocator.spilledTmp().isEmpty()) {
+ assignRegisterToTmpInProgram(code, gpAllocator);
+ gpIsColored = true;
+ } else
+ addSpillAndFillToProgram<Arg::GP>(code, gpAllocator.spilledTmp());
+
+ fpAllocator.allocate();
+ if (fpAllocator.spilledTmp().isEmpty()) {
+ assignRegisterToTmpInProgram(code, fpAllocator);
+ fpIsColored = true;
+ } else
+ addSpillAndFillToProgram<Arg::FP>(code, fpAllocator.spilledTmp());
+ };
+
+ if (!gpIsColored)
+ iteratedRegisterCoalescingOnType<Arg::GP>(code);
+ if (!fpIsColored)
+ iteratedRegisterCoalescingOnType<Arg::FP>(code);
+}
+
+} } } // namespace JSC::B3::Air
+
+#endif // ENABLE(B3_JIT)
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirIteratedRegisterCoalescingh"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.h (0 => 192292)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.h (rev 0)
+++ trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.h 2015-11-11 05:10:43 UTC (rev 192292)
</span><span class="lines">@@ -0,0 +1,44 @@
</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 AirIteratedRegisterCoalescing_h
+#define AirIteratedRegisterCoalescing_h
+
+#if ENABLE(B3_JIT)
+
+namespace JSC { namespace B3 { namespace Air {
+
+class Code;
+
+// This is a register allocation phase based on Andrew Appel's Iterated Register Coalescing
+// http://www.cs.cmu.edu/afs/cs/academic/class/15745-s07/www/papers/george.pdf
+void iteratedRegisterCoalescing(Code&);
+
+} } } // namespace JSC::B3::Air
+
+#endif // ENABLE(B3_JIT)
+
+#endif // AirIteratedRegisterCoalescing_h
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirTmph"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirTmp.h (192291 => 192292)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirTmp.h 2015-11-11 04:29:59 UTC (rev 192291)
+++ trunk/Source/JavaScriptCore/b3/air/AirTmp.h 2015-11-11 05:10:43 UTC (rev 192292)
</span><span class="lines">@@ -172,7 +172,16 @@
</span><span class="cx"> {
</span><span class="cx"> return WTF::IntHash<int>::hash(m_value);
</span><span class="cx"> }
</span><del>-
</del><ins>+
+ unsigned internalValue() const { return static_cast<unsigned>(m_value); }
+
+ static Tmp tmpForInternalValue(unsigned index)
+ {
+ Tmp result;
+ result.m_value = static_cast<int>(index);
+ return result;
+ }
+
</ins><span class="cx"> private:
</span><span class="cx"> static int encodeGP(unsigned index)
</span><span class="cx"> {
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3testb3cpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/testb3.cpp (192291 => 192292)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/testb3.cpp 2015-11-11 04:29:59 UTC (rev 192291)
+++ trunk/Source/JavaScriptCore/b3/testb3.cpp 2015-11-11 05:10:43 UTC (rev 192292)
</span><span class="lines">@@ -1808,6 +1808,29 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+void testSpillGP()
+{
+ Procedure proc;
+ BasicBlock* root = proc.addBlock();
+
+ Vector<Value*> sources;
+ sources.append(root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
+ sources.append(root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1));
+
+ for (unsigned i = 0; i < 30; ++i) {
+ sources.append(
+ root->appendNew<Value>(proc, Add, Origin(), sources[sources.size() - 1], sources[sources.size() - 2])
+ );
+ }
+
+ Value* total = root->appendNew<Const64Value>(proc, Origin(), 0);
+ for (Value* value : sources)
+ total = root->appendNew<Value>(proc, Add, Origin(), total, value);
+
+ root->appendNew<ControlValue>(proc, Return, Origin(), total);
+ compileAndRun<int>(proc, 1, 2);
+}
+
</ins><span class="cx"> void testBranch()
</span><span class="cx"> {
</span><span class="cx"> Procedure proc;
</span><span class="lines">@@ -3302,6 +3325,8 @@
</span><span class="cx"> RUN(testLoad<uint16_t>(Load16Z, 1000000000));
</span><span class="cx"> RUN(testLoad<uint16_t>(Load16Z, -1000000000));
</span><span class="cx">
</span><ins>+ RUN(testSpillGP());
+
</ins><span class="cx"> RUN(testCallSimple(1, 2));
</span><span class="cx"> RUN(testCallFunctionWithHellaArguments());
</span><span class="cx">
</span></span></pre>
</div>
</div>
</body>
</html>