<!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>[193682] 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/193682">193682</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2015-12-07 18:46:22 -0800 (Mon, 07 Dec 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>FTL B3 should be able to flag the tag constants as being super important so that B3 can hoist them and Air can force them into registers
https://bugs.webkit.org/show_bug.cgi?id=151955
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
Taught B3 about the concept of "fast constants". A client of B3 can now tell B3 which
constants are super important. B3 will not spill the constant in that case and will ensure
that the constant is materialized only once: statically once, and dynamically once per
procedure execution. The hoistFastConstants() algorithm in B3MoveConstants.cpp achieves this
by first picking the lowest common dominator of all uses of each fast constant, and then
picking the materialization point by finding the lowest dominator of that dominator that is
tied for lowest block frequency. In practice, the second step ensures that this is the lowest
point in the program that is not in a loop (i.e. executes no more than once dynamically per
procedure invocation).
Taught Air about the concept of "fast tmps". B3 tells Air that a tmp is fast if it is used to
hold the materialization of a fast constant. IRC will use the lowest possible spill score for
fast tmps. In practice, this ensures that fast constants are never spilled.
Added a small snippet of code to FTL::LowerDFGToLLVM that makes both of the tag constants
into fast constants.
My hope is that this very brute-force heuristic is good enough that we don't have to think
about constants for a while. Based on my experience with how LLVM's constant hoisting works
out, the heuristic in this patch is going to be tough to beat. LLVM's constant hoisting does
good things when it hoists the tags, and usually causes nothing but problems when it hoists
anything else. This is because there is no way a low-level compiler to really understand how
a constant materialization impacts some operation's contribution to the overall execution
time of a procedure. But, in the FTL we know that constant materializations for type checks
are a bummer because we are super comfortable placing type checks on the hottest of paths. So
those are the last paths where extra instructions should be added by the compiler. On the
other hand, all other large constant uses are on relatively cold paths, or paths that are
already expensive for other reasons. For example, global variable accesses have to
materialize a pointer to the global. But that's not really a big deal, since a load from a
global involves first the load itself and then type checks on the result - so probably the
constant materialization is just not interesting. A store to a global often involves a store
barrier, so the constant materialization is really not interesting. This patch codifies this
heuristic in a pact between Air, B3, and the FTL: FTL demands that B3 pin the two tags in
registers, and B3 relays the demand to Air.
* JavaScriptCore.xcodeproj/project.pbxproj:
* b3/B3CFG.h: Added.
(JSC::B3::CFG::CFG):
(JSC::B3::CFG::root):
(JSC::B3::CFG::newMap):
(JSC::B3::CFG::successors):
(JSC::B3::CFG::predecessors):
(JSC::B3::CFG::index):
(JSC::B3::CFG::node):
(JSC::B3::CFG::numNodes):
(JSC::B3::CFG::dump):
* b3/B3Dominators.h: Added.
(JSC::B3::Dominators::Dominators):
* b3/B3IndexMap.h:
(JSC::B3::IndexMap::resize):
(JSC::B3::IndexMap::size):
(JSC::B3::IndexMap::operator[]):
* b3/B3LowerMacros.cpp:
* b3/B3LowerToAir.cpp:
(JSC::B3::Air::LowerToAir::tmp):
* b3/B3MoveConstants.cpp:
* b3/B3Opcode.h:
(JSC::B3::constPtrOpcode):
(JSC::B3::isConstant):
* b3/B3Procedure.cpp:
(JSC::B3::Procedure::Procedure):
(JSC::B3::Procedure::resetReachability):
(JSC::B3::Procedure::invalidateCFG):
(JSC::B3::Procedure::dump):
(JSC::B3::Procedure::deleteValue):
(JSC::B3::Procedure::dominators):
(JSC::B3::Procedure::addFastConstant):
(JSC::B3::Procedure::isFastConstant):
(JSC::B3::Procedure::addDataSection):
* b3/B3Procedure.h:
(JSC::B3::Procedure::size):
(JSC::B3::Procedure::cfg):
(JSC::B3::Procedure::setLastPhaseName):
* b3/B3ReduceStrength.cpp:
* b3/B3ValueInlines.h:
(JSC::B3::Value::isConstant):
(JSC::B3::Value::isInteger):
* b3/B3ValueKey.h:
(JSC::B3::ValueKey::canMaterialize):
(JSC::B3::ValueKey::isConstant):
* b3/air/AirCode.cpp:
(JSC::B3::Air::Code::findNextBlock):
(JSC::B3::Air::Code::addFastTmp):
* b3/air/AirCode.h:
(JSC::B3::Air::Code::specials):
(JSC::B3::Air::Code::isFastTmp):
(JSC::B3::Air::Code::setLastPhaseName):
* b3/air/AirIteratedRegisterCoalescing.cpp:
* dfg/DFGDominators.h:
* dfg/DFGSSACalculator.cpp:
* ftl/FTLLowerDFGToLLVM.cpp:
(JSC::FTL::DFG::LowerDFGToLLVM::lower):
Source/WTF:
Remove some remaining DFG-specific snippets from Dominators. This used to be a non-template
DFG class, and some time ago I hoisted it into WTF and made it generic. But since the only
user of the class was the DFG, this class still had a handful of DFG-specific snippets that
didn't compile when I started using it from B3.
Also renamed immediateDominatorOf() to idom(). This is the sort of abbreviation that we
wouldn't ordinarily want to have in WebKit. But WebKit does allow for abbreviations that are
"more canonical". The term "idom" is definitely more canonical than "immediateDominatorOf".
* wtf/Dominators.h:
(WTF::Dominators::dominates):
(WTF::Dominators::idom):
(WTF::Dominators::forAllStrictDominatorsOf):
(WTF::Dominators::NaiveDominators::dominates):
(WTF::Dominators::NaiveDominators::dump):
(WTF::Dominators::ValidationContext::handleErrors):</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="#trunkSourceJavaScriptCoreb3B3LowerMacroscpp">trunk/Source/JavaScriptCore/b3/B3LowerMacros.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3LowerToAircpp">trunk/Source/JavaScriptCore/b3/B3LowerToAir.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3MoveConstantscpp">trunk/Source/JavaScriptCore/b3/B3MoveConstants.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3Opcodeh">trunk/Source/JavaScriptCore/b3/B3Opcode.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3Procedurecpp">trunk/Source/JavaScriptCore/b3/B3Procedure.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3Procedureh">trunk/Source/JavaScriptCore/b3/B3Procedure.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3ReduceStrengthcpp">trunk/Source/JavaScriptCore/b3/B3ReduceStrength.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3ValueInlinesh">trunk/Source/JavaScriptCore/b3/B3ValueInlines.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3ValueKeyh">trunk/Source/JavaScriptCore/b3/B3ValueKey.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirCodecpp">trunk/Source/JavaScriptCore/b3/air/AirCode.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirCodeh">trunk/Source/JavaScriptCore/b3/air/AirCode.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirIteratedRegisterCoalescingcpp">trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGCFGh">trunk/Source/JavaScriptCore/dfg/DFGCFG.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGDominatorsh">trunk/Source/JavaScriptCore/dfg/DFGDominators.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGSSACalculatorcpp">trunk/Source/JavaScriptCore/dfg/DFGSSACalculator.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreftlFTLLowerDFGToLLVMcpp">trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp</a></li>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFwtfDominatorsh">trunk/Source/WTF/wtf/Dominators.h</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreb3B3CFGh">trunk/Source/JavaScriptCore/b3/B3CFG.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3Dominatorsh">trunk/Source/JavaScriptCore/b3/B3Dominators.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (193681 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-12-08 02:38:37 UTC (rev 193681)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -1,3 +1,103 @@
</span><ins>+2015-12-07 Filip Pizlo <fpizlo@apple.com>
+
+ FTL B3 should be able to flag the tag constants as being super important so that B3 can hoist them and Air can force them into registers
+ https://bugs.webkit.org/show_bug.cgi?id=151955
+
+ Reviewed by Geoffrey Garen.
+
+ Taught B3 about the concept of "fast constants". A client of B3 can now tell B3 which
+ constants are super important. B3 will not spill the constant in that case and will ensure
+ that the constant is materialized only once: statically once, and dynamically once per
+ procedure execution. The hoistFastConstants() algorithm in B3MoveConstants.cpp achieves this
+ by first picking the lowest common dominator of all uses of each fast constant, and then
+ picking the materialization point by finding the lowest dominator of that dominator that is
+ tied for lowest block frequency. In practice, the second step ensures that this is the lowest
+ point in the program that is not in a loop (i.e. executes no more than once dynamically per
+ procedure invocation).
+
+ Taught Air about the concept of "fast tmps". B3 tells Air that a tmp is fast if it is used to
+ hold the materialization of a fast constant. IRC will use the lowest possible spill score for
+ fast tmps. In practice, this ensures that fast constants are never spilled.
+
+ Added a small snippet of code to FTL::LowerDFGToLLVM that makes both of the tag constants
+ into fast constants.
+
+ My hope is that this very brute-force heuristic is good enough that we don't have to think
+ about constants for a while. Based on my experience with how LLVM's constant hoisting works
+ out, the heuristic in this patch is going to be tough to beat. LLVM's constant hoisting does
+ good things when it hoists the tags, and usually causes nothing but problems when it hoists
+ anything else. This is because there is no way a low-level compiler to really understand how
+ a constant materialization impacts some operation's contribution to the overall execution
+ time of a procedure. But, in the FTL we know that constant materializations for type checks
+ are a bummer because we are super comfortable placing type checks on the hottest of paths. So
+ those are the last paths where extra instructions should be added by the compiler. On the
+ other hand, all other large constant uses are on relatively cold paths, or paths that are
+ already expensive for other reasons. For example, global variable accesses have to
+ materialize a pointer to the global. But that's not really a big deal, since a load from a
+ global involves first the load itself and then type checks on the result - so probably the
+ constant materialization is just not interesting. A store to a global often involves a store
+ barrier, so the constant materialization is really not interesting. This patch codifies this
+ heuristic in a pact between Air, B3, and the FTL: FTL demands that B3 pin the two tags in
+ registers, and B3 relays the demand to Air.
+
+ * JavaScriptCore.xcodeproj/project.pbxproj:
+ * b3/B3CFG.h: Added.
+ (JSC::B3::CFG::CFG):
+ (JSC::B3::CFG::root):
+ (JSC::B3::CFG::newMap):
+ (JSC::B3::CFG::successors):
+ (JSC::B3::CFG::predecessors):
+ (JSC::B3::CFG::index):
+ (JSC::B3::CFG::node):
+ (JSC::B3::CFG::numNodes):
+ (JSC::B3::CFG::dump):
+ * b3/B3Dominators.h: Added.
+ (JSC::B3::Dominators::Dominators):
+ * b3/B3IndexMap.h:
+ (JSC::B3::IndexMap::resize):
+ (JSC::B3::IndexMap::size):
+ (JSC::B3::IndexMap::operator[]):
+ * b3/B3LowerMacros.cpp:
+ * b3/B3LowerToAir.cpp:
+ (JSC::B3::Air::LowerToAir::tmp):
+ * b3/B3MoveConstants.cpp:
+ * b3/B3Opcode.h:
+ (JSC::B3::constPtrOpcode):
+ (JSC::B3::isConstant):
+ * b3/B3Procedure.cpp:
+ (JSC::B3::Procedure::Procedure):
+ (JSC::B3::Procedure::resetReachability):
+ (JSC::B3::Procedure::invalidateCFG):
+ (JSC::B3::Procedure::dump):
+ (JSC::B3::Procedure::deleteValue):
+ (JSC::B3::Procedure::dominators):
+ (JSC::B3::Procedure::addFastConstant):
+ (JSC::B3::Procedure::isFastConstant):
+ (JSC::B3::Procedure::addDataSection):
+ * b3/B3Procedure.h:
+ (JSC::B3::Procedure::size):
+ (JSC::B3::Procedure::cfg):
+ (JSC::B3::Procedure::setLastPhaseName):
+ * b3/B3ReduceStrength.cpp:
+ * b3/B3ValueInlines.h:
+ (JSC::B3::Value::isConstant):
+ (JSC::B3::Value::isInteger):
+ * b3/B3ValueKey.h:
+ (JSC::B3::ValueKey::canMaterialize):
+ (JSC::B3::ValueKey::isConstant):
+ * b3/air/AirCode.cpp:
+ (JSC::B3::Air::Code::findNextBlock):
+ (JSC::B3::Air::Code::addFastTmp):
+ * b3/air/AirCode.h:
+ (JSC::B3::Air::Code::specials):
+ (JSC::B3::Air::Code::isFastTmp):
+ (JSC::B3::Air::Code::setLastPhaseName):
+ * b3/air/AirIteratedRegisterCoalescing.cpp:
+ * dfg/DFGDominators.h:
+ * dfg/DFGSSACalculator.cpp:
+ * ftl/FTLLowerDFGToLLVM.cpp:
+ (JSC::FTL::DFG::LowerDFGToLLVM::lower):
+
</ins><span class="cx"> 2015-12-07 Andy VanWagoner <thetalecrafter@gmail.com>
</span><span class="cx">
</span><span class="cx"> [INTL] Implement String.prototype.toLocaleUpperCase in ECMA-402
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj (193681 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2015-12-08 02:38:37 UTC (rev 193681)
+++ trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -306,6 +306,8 @@
</span><span class="cx"> 0F338E1E1BF286EA0013C88F /* B3LowerMacros.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338E1A1BF286EA0013C88F /* B3LowerMacros.h */; };
</span><span class="cx"> 0F33FCF71C136E2500323F67 /* B3StackmapGenerationParams.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F33FCF51C136E2500323F67 /* B3StackmapGenerationParams.cpp */; };
</span><span class="cx"> 0F33FCF81C136E2500323F67 /* B3StackmapGenerationParams.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F33FCF61C136E2500323F67 /* B3StackmapGenerationParams.h */; };
</span><ins>+ 0F33FCFB1C1625BE00323F67 /* B3CFG.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F33FCF91C1625BE00323F67 /* B3CFG.h */; };
+ 0F33FCFC1C1625BE00323F67 /* B3Dominators.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F33FCFA1C1625BE00323F67 /* B3Dominators.h */; };
</ins><span class="cx"> 0F34B14916D42010001CDA5A /* DFGUseKind.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F34B14716D4200E001CDA5A /* DFGUseKind.cpp */; };
</span><span class="cx"> 0F34B14A16D42013001CDA5A /* DFGUseKind.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F34B14816D4200E001CDA5A /* DFGUseKind.h */; };
</span><span class="cx"> 0F37308C1C0BD29100052BFA /* B3PhiChildren.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F37308A1C0BD29100052BFA /* B3PhiChildren.cpp */; };
</span><span class="lines">@@ -2404,6 +2406,8 @@
</span><span class="cx"> 0F338E1A1BF286EA0013C88F /* B3LowerMacros.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3LowerMacros.h; path = b3/B3LowerMacros.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F33FCF51C136E2500323F67 /* B3StackmapGenerationParams.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3StackmapGenerationParams.cpp; path = b3/B3StackmapGenerationParams.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0F33FCF61C136E2500323F67 /* B3StackmapGenerationParams.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3StackmapGenerationParams.h; path = b3/B3StackmapGenerationParams.h; sourceTree = "<group>"; };
</span><ins>+ 0F33FCF91C1625BE00323F67 /* B3CFG.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3CFG.h; path = b3/B3CFG.h; sourceTree = "<group>"; };
+ 0F33FCFA1C1625BE00323F67 /* B3Dominators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3Dominators.h; path = b3/B3Dominators.h; sourceTree = "<group>"; };
</ins><span class="cx"> 0F34B14716D4200E001CDA5A /* DFGUseKind.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGUseKind.cpp; path = dfg/DFGUseKind.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0F34B14816D4200E001CDA5A /* DFGUseKind.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGUseKind.h; path = dfg/DFGUseKind.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F37308A1C0BD29100052BFA /* B3PhiChildren.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3PhiChildren.cpp; path = b3/B3PhiChildren.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -4567,6 +4571,7 @@
</span><span class="cx"> 0FEC84BA1BDACDAC0080FF74 /* B3BlockWorklist.h */,
</span><span class="cx"> 0F338DF71BE96AA80013C88F /* B3CCallValue.cpp */,
</span><span class="cx"> 0F338DF81BE96AA80013C88F /* B3CCallValue.h */,
</span><ins>+ 0F33FCF91C1625BE00323F67 /* B3CFG.h */,
</ins><span class="cx"> 0FEC84BB1BDACDAC0080FF74 /* B3CheckSpecial.cpp */,
</span><span class="cx"> 0FEC84BC1BDACDAC0080FF74 /* B3CheckSpecial.h */,
</span><span class="cx"> 0FEC84BD1BDACDAC0080FF74 /* B3CheckValue.cpp */,
</span><span class="lines">@@ -4590,6 +4595,7 @@
</span><span class="cx"> 0FEC84CA1BDACDAC0080FF74 /* B3ControlValue.h */,
</span><span class="cx"> 0F338E011BF0276C0013C88F /* B3DataSection.cpp */,
</span><span class="cx"> 0F338E021BF0276C0013C88F /* B3DataSection.h */,
</span><ins>+ 0F33FCFA1C1625BE00323F67 /* B3Dominators.h */,
</ins><span class="cx"> 0FEC85C41BE16F5A0080FF74 /* B3Effects.cpp */,
</span><span class="cx"> 0FEC85BE1BE167A00080FF74 /* B3Effects.h */,
</span><span class="cx"> 0FEC84CB1BDACDAC0080FF74 /* B3FrequencyClass.cpp */,
</span><span class="lines">@@ -7518,6 +7524,7 @@
</span><span class="cx"> 9928FF3C18AC4AEC00B8CF12 /* JSReplayInputs.h in Headers */,
</span><span class="cx"> BC18C4260E16F5CD00B34460 /* JSRetainPtr.h in Headers */,
</span><span class="cx"> 14874AE615EBDE4A002E3587 /* JSScope.h in Headers */,
</span><ins>+ 0F33FCFB1C1625BE00323F67 /* B3CFG.h in Headers */,
</ins><span class="cx"> A7C0C4AC168103020017011D /* JSScriptRefPrivate.h in Headers */,
</span><span class="cx"> FE1220271BE7F58C0039E6F2 /* JITAddGenerator.h in Headers */,
</span><span class="cx"> 0F919D11157F332C004A4E7D /* JSSegmentedVariableObject.h in Headers */,
</span><span class="lines">@@ -7797,6 +7804,7 @@
</span><span class="cx"> 705B41AE1A6E501E00716757 /* SymbolConstructor.h in Headers */,
</span><span class="cx"> 996B73271BDA08EF00331B84 /* SymbolConstructor.lut.h in Headers */,
</span><span class="cx"> 705B41B01A6E501E00716757 /* SymbolObject.h in Headers */,
</span><ins>+ 0F33FCFC1C1625BE00323F67 /* B3Dominators.h in Headers */,
</ins><span class="cx"> 705B41B21A6E501E00716757 /* SymbolPrototype.h in Headers */,
</span><span class="cx"> 996B73281BDA08EF00331B84 /* SymbolPrototype.lut.h in Headers */,
</span><span class="cx"> BC18C46B0E16F5CD00B34460 /* SymbolTable.h in Headers */,
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3CFGh"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/b3/B3CFG.h (0 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3CFG.h (rev 0)
+++ trunk/Source/JavaScriptCore/b3/B3CFG.h 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -0,0 +1,80 @@
</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 B3CFG_h
+#define B3CFG_h
+
+#if ENABLE(B3_JIT)
+
+#include "B3BasicBlock.h"
+#include "B3IndexMap.h"
+#include "B3IndexSet.h"
+#include "B3Procedure.h"
+
+namespace JSC { namespace B3 {
+
+class CFG {
+ WTF_MAKE_NONCOPYABLE(CFG);
+ WTF_MAKE_FAST_ALLOCATED;
+public:
+ typedef BasicBlock* Node;
+ typedef IndexSet<BasicBlock> Set;
+ template<typename T> using Map = IndexMap<BasicBlock, T>;
+ typedef Vector<BasicBlock*, 4> List;
+
+ CFG(Procedure& proc)
+ : m_proc(proc)
+ {
+ }
+
+ Node root() { return m_proc[0]; }
+
+ template<typename T>
+ Map<T> newMap() { return IndexMap<BasicBlock, T>(m_proc.size()); }
+
+ SuccessorCollection<BasicBlock, BasicBlock::SuccessorList> successors(Node node) { return node->successorBlocks(); }
+ BasicBlock::PredecessorList& predecessors(Node node) { return node->predecessors(); }
+
+ unsigned index(Node node) const { return node->index(); }
+ Node node(unsigned index) const { return m_proc[index]; }
+ unsigned numNodes() const { return m_proc.size(); }
+
+ PointerDump<BasicBlock> dump(Node node) const { return pointerDump(node); }
+
+ void dump(PrintStream& out) const
+ {
+ m_proc.dump(out);
+ }
+
+private:
+ Procedure& m_proc;
+};
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
+#endif // B3CFG_h
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3Dominatorsh"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/b3/B3Dominators.h (0 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3Dominators.h (rev 0)
+++ trunk/Source/JavaScriptCore/b3/B3Dominators.h 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -0,0 +1,55 @@
</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 B3Dominators_h
+#define B3Dominators_h
+
+#if ENABLE(B3_JIT)
+
+#include "B3CFG.h"
+#include "B3Common.h"
+#include "B3Procedure.h"
+#include <wtf/Dominators.h>
+#include <wtf/FastMalloc.h>
+#include <wtf/Noncopyable.h>
+
+namespace JSC { namespace B3 {
+
+class Dominators : public WTF::Dominators<CFG> {
+ WTF_MAKE_NONCOPYABLE(Dominators);
+ WTF_MAKE_FAST_ALLOCATED;
+public:
+ Dominators(Procedure& proc)
+ : WTF::Dominators<CFG>(proc.cfg(), shouldValidateIR())
+ {
+ }
+};
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
+#endif // B3Dominators_h
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3IndexMaph"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3IndexMap.h (193681 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3IndexMap.h 2015-12-08 02:38:37 UTC (rev 193681)
+++ trunk/Source/JavaScriptCore/b3/B3IndexMap.h 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -49,6 +49,18 @@
</span><span class="cx"> m_vector.fill(Value(), size);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ size_t size() const { return m_vector.size(); }
+
+ Value& operator[](size_t index)
+ {
+ return m_vector[index];
+ }
+
+ const Value& operator[](size_t index) const
+ {
+ return m_vector[index];
+ }
+
</ins><span class="cx"> Value& operator[](Key* key)
</span><span class="cx"> {
</span><span class="cx"> return m_vector[key->index()];
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3LowerMacroscpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3LowerMacros.cpp (193681 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3LowerMacros.cpp 2015-12-08 02:38:37 UTC (rev 193681)
+++ trunk/Source/JavaScriptCore/b3/B3LowerMacros.cpp 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -58,8 +58,10 @@
</span><span class="cx"> processCurrentBlock();
</span><span class="cx"> }
</span><span class="cx"> m_changed |= m_blockInsertionSet.execute();
</span><del>- if (m_changed)
</del><ins>+ if (m_changed) {
</ins><span class="cx"> m_proc.resetReachability();
</span><ins>+ m_proc.invalidateCFG();
+ }
</ins><span class="cx"> return m_changed;
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3LowerToAircpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3LowerToAir.cpp (193681 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3LowerToAir.cpp 2015-12-08 02:38:37 UTC (rev 193681)
+++ trunk/Source/JavaScriptCore/b3/B3LowerToAir.cpp 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -302,8 +302,11 @@
</span><span class="cx"> while (shouldCopyPropagate(value))
</span><span class="cx"> value = value->child(0);
</span><span class="cx"> Tmp& realTmp = m_valueToTmp[value];
</span><del>- if (!realTmp)
</del><ins>+ if (!realTmp) {
</ins><span class="cx"> realTmp = m_code.newTmp(Arg::typeForB3Type(value->type()));
</span><ins>+ if (m_procedure.isFastConstant(value->key()))
+ m_code.addFastTmp(realTmp);
+ }
</ins><span class="cx"> tmp = realTmp;
</span><span class="cx"> }
</span><span class="cx"> return tmp;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3MoveConstantscpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3MoveConstants.cpp (193681 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3MoveConstants.cpp 2015-12-08 02:38:37 UTC (rev 193681)
+++ trunk/Source/JavaScriptCore/b3/B3MoveConstants.cpp 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -29,12 +29,15 @@
</span><span class="cx"> #if ENABLE(B3_JIT)
</span><span class="cx">
</span><span class="cx"> #include "B3BasicBlockInlines.h"
</span><ins>+#include "B3Dominators.h"
</ins><span class="cx"> #include "B3InsertionSetInlines.h"
</span><span class="cx"> #include "B3MemoryValue.h"
</span><span class="cx"> #include "B3PhaseScope.h"
</span><span class="cx"> #include "B3ProcedureInlines.h"
</span><span class="cx"> #include "B3ValueInlines.h"
</span><span class="cx"> #include "B3ValueKeyInlines.h"
</span><ins>+#include <wtf/HashMap.h>
+#include <wtf/Vector.h>
</ins><span class="cx">
</span><span class="cx"> namespace JSC { namespace B3 {
</span><span class="cx">
</span><span class="lines">@@ -50,27 +53,137 @@
</span><span class="cx">
</span><span class="cx"> void run()
</span><span class="cx"> {
</span><del>- // Eventually this phase will do smart things. For now, it uses a super simple heuristic: it
- // places constants in the block that uses them, and makes sure that each block has only one
- // materialization for each constant. Note that this mostly only matters for large constants, since
- // small constants get fused into the instructions that use them. But it might matter for small
- // constants if they are used in instructions that don't do immediates, like conditional moves.
</del><ins>+ // This phase uses super simple heuristics to ensure that constants are in profitable places
+ // and also lowers constant materialization code. Constants marked "fast" by the client are
+ // hoisted to the lowest common dominator. A table is created for constants that need to be
+ // loaded to be materialized, and all of their Values are turned into loads from that table.
+ // Non-fast constants get materialized in the block that uses them. Constants that are
+ // materialized by loading get special treatment when they get used in some kind of Any in a
+ // StackmapValue. In that case, the Constants are sunk to the point of use, since that allows
+ // the instruction selector to sink the constants into an Arg::imm64.
</ins><span class="cx">
</span><del>- // FIXME: Implement a better story for constants. At a minimum this should allow the B3
- // client to specify important constants that always get hoisted. Also, the table used to
- // hold double constants should have a pointer to it that is hoisted. If we wanted to be more
- // aggressive, we could make constant materialization be a feature of Air: we could label
- // some Tmps as being unmaterialized constants and have a late Air phase - post register
- // allocation - that creates materializations of those constant Tmps by scavenging leftover
- // registers.
</del><ins>+ // FIXME: Implement a better story for constants. For example, the table used to hold double
+ // constants should have a pointer to it that is hoisted. If we wanted to be more aggressive,
+ // we could make constant materialization be a feature of Air: we could label some Tmps as
+ // being unmaterialized constants and have a late Air phase - post register allocation - that
+ // creates materializations of those constant Tmps by scavenging leftover registers.
</ins><span class="cx">
</span><ins>+ hoistFastConstants();
+ sinkSlowConstants();
+ }
+
+private:
+ void hoistFastConstants()
+ {
+ Dominators& dominators = m_proc.dominators();
+ HashMap<ValueKey, Value*> valueForConstant;
+ IndexMap<BasicBlock, Vector<Value*>> materializations(m_proc.size());
+
+ // We determine where things get materialized based on where they are used.
+ for (BasicBlock* block : m_proc) {
+ for (Value* value : *block) {
+ for (Value*& child : value->children()) {
+ ValueKey key = child->key();
+ if (!m_proc.isFastConstant(key))
+ continue;
+
+ auto result = valueForConstant.add(key, child);
+ if (result.isNewEntry) {
+ // Assume that this block is where we want to materialize the value.
+ child->owner = block;
+ continue;
+ }
+
+ // Make 'value' use the canonical constant rather than the one it was using.
+ child = result.iterator->value;
+
+ // Determine the least common dominator. That's the lowest place in the CFG where
+ // we could materialize the constant while still having only one materialization
+ // in the resulting code.
+ while (!dominators.dominates(child->owner, block))
+ child->owner = dominators.idom(child->owner);
+ }
+ }
+ }
+
+ // Make sure that each basic block knows what to materialize. This also refines the
+ // materialization block based on execution frequency. It finds the minimum block frequency
+ // of all of its dominators, and selects the closest block amongst those that are tied for
+ // lowest frequency.
+ for (auto& entry : valueForConstant) {
+ Value* value = entry.value;
+ for (BasicBlock* block = value->owner; block; block = dominators.idom(block)) {
+ if (block->frequency() < value->owner->frequency())
+ value->owner = block;
+ }
+ materializations[entry.value->owner].append(entry.value);
+ }
+
+ // Get rid of Value's that are fast constants but aren't canonical. Also remove the canonical
+ // ones from the CFG, since we're going to reinsert them elsewhere.
+ for (BasicBlock* block : m_proc) {
+ for (Value*& value : *block) {
+ ValueKey key = value->key();
+ if (!m_proc.isFastConstant(key))
+ continue;
+
+ if (valueForConstant.get(key) == value)
+ value = m_proc.add<Value>(Nop, value->origin());
+ else
+ value->replaceWithNop();
+ }
+ }
+
+ // Now make sure that we move constants to where they are supposed to go. Again, we do this
+ // based on uses.
+ for (BasicBlock* block : m_proc) {
+ for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
+ Value* value = block->at(valueIndex);
+ for (Value* child : value->children()) {
+ ValueKey key = child->key();
+ if (!m_proc.isFastConstant(key))
+ continue;
+
+ // If we encounter a fast constant, then it must be canonical, since we already
+ // got rid of the non-canonical ones.
+ ASSERT(valueForConstant.get(key) == child);
+
+ if (child->owner != block) {
+ // This constant isn't our problem. It's going to be materialized in another
+ // block.
+ continue;
+ }
+
+ // We're supposed to materialize this constant in this block, and we haven't
+ // done it yet.
+ m_insertionSet.insertValue(valueIndex, child);
+ child->owner = nullptr;
+ }
+ }
+
+ // We may have some constants that need to be materialized right at the end of this
+ // block.
+ for (Value* value : materializations[block]) {
+ if (!value->owner) {
+ // It's already materialized in this block.
+ continue;
+ }
+
+ m_insertionSet.insertValue(block->size() - 1, value);
+ }
+ m_insertionSet.execute(block);
+ }
+ }
+
+ void sinkSlowConstants()
+ {
</ins><span class="cx"> // First we need to figure out which constants go into the data section. These are non-zero
</span><span class="cx"> // double constants.
</span><span class="cx"> for (Value* value : m_proc.values()) {
</span><del>- if (!needsMotion(value))
</del><ins>+ ValueKey key = value->key();
+ if (!needsMotion(key))
</ins><span class="cx"> continue;
</span><span class="cx"> m_toRemove.append(value);
</span><del>- ValueKey key = value->key();
</del><span class="cx"> if (goesInTable(key))
</span><span class="cx"> m_constTable.add(key, m_constTable.size());
</span><span class="cx"> }
</span><span class="lines">@@ -87,10 +200,10 @@
</span><span class="cx"> StackmapValue* stackmap = value->as<StackmapValue>();
</span><span class="cx"> for (unsigned childIndex = 0; childIndex < value->numChildren(); ++childIndex) {
</span><span class="cx"> Value*& child = value->child(childIndex);
</span><del>- if (!needsMotion(child))
</del><ins>+ ValueKey key = child->key();
+ if (!needsMotion(key))
</ins><span class="cx"> continue;
</span><span class="cx">
</span><del>- ValueKey key = child->key();
</del><span class="cx"> if (stackmap
</span><span class="cx"> && goesInTable(key)
</span><span class="cx"> && stackmap->constrainedChild(childIndex).rep().isAny()) {
</span><span class="lines">@@ -115,8 +228,7 @@
</span><span class="cx"> for (Value* toRemove : m_toRemove)
</span><span class="cx"> toRemove->replaceWithNop();
</span><span class="cx"> }
</span><del>-
-private:
</del><ins>+
</ins><span class="cx"> Value* materialize(unsigned valueIndex, const ValueKey& key, const Origin& origin)
</span><span class="cx"> {
</span><span class="cx"> if (Value* result = m_constants.get(key))
</span><span class="lines">@@ -147,9 +259,9 @@
</span><span class="cx"> return key.opcode() == ConstDouble && key != doubleZero();
</span><span class="cx"> }
</span><span class="cx">
</span><del>- bool needsMotion(const Value* value)
</del><ins>+ bool needsMotion(const ValueKey& key)
</ins><span class="cx"> {
</span><del>- return value->isConstant();
</del><ins>+ return key.isConstant() && !m_proc.isFastConstant(key);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> static ValueKey doubleZero()
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3Opcodeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3Opcode.h (193681 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3Opcode.h 2015-12-08 02:38:37 UTC (rev 193681)
+++ trunk/Source/JavaScriptCore/b3/B3Opcode.h 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -231,6 +231,18 @@
</span><span class="cx"> return Const32;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+inline bool isConstant(Opcode opcode)
+{
+ switch (opcode) {
+ case Const32:
+ case Const64:
+ case ConstDouble:
+ return true;
+ default:
+ return false;
+ }
+}
+
</ins><span class="cx"> } } // namespace JSC::B3
</span><span class="cx">
</span><span class="cx"> namespace WTF {
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3Procedurecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3Procedure.cpp (193681 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3Procedure.cpp 2015-12-08 02:38:37 UTC (rev 193681)
+++ trunk/Source/JavaScriptCore/b3/B3Procedure.cpp 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -32,14 +32,17 @@
</span><span class="cx"> #include "B3BasicBlockInlines.h"
</span><span class="cx"> #include "B3BasicBlockUtils.h"
</span><span class="cx"> #include "B3BlockWorklist.h"
</span><ins>+#include "B3CFG.h"
</ins><span class="cx"> #include "B3DataSection.h"
</span><ins>+#include "B3Dominators.h"
</ins><span class="cx"> #include "B3OpaqueByproducts.h"
</span><span class="cx"> #include "B3ValueInlines.h"
</span><span class="cx">
</span><span class="cx"> namespace JSC { namespace B3 {
</span><span class="cx">
</span><span class="cx"> Procedure::Procedure()
</span><del>- : m_lastPhaseName("initial")
</del><ins>+ : m_cfg(new CFG(*this))
+ , m_lastPhaseName("initial")
</ins><span class="cx"> , m_byproducts(std::make_unique<OpaqueByproducts>())
</span><span class="cx"> , m_code(new Air::Code(*this))
</span><span class="cx"> {
</span><span class="lines">@@ -113,6 +116,11 @@
</span><span class="cx"> });
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+void Procedure::invalidateCFG()
+{
+ m_dominators = nullptr;
+}
+
</ins><span class="cx"> void Procedure::dump(PrintStream& out) const
</span><span class="cx"> {
</span><span class="cx"> for (BasicBlock* block : *this)
</span><span class="lines">@@ -138,6 +146,26 @@
</span><span class="cx"> m_values[value->index()] = nullptr;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+Dominators& Procedure::dominators()
+{
+ if (!m_dominators)
+ m_dominators = std::make_unique<Dominators>(*this);
+ return *m_dominators;
+}
+
+void Procedure::addFastConstant(const ValueKey& constant)
+{
+ RELEASE_ASSERT(constant.isConstant());
+ m_fastConstants.add(constant);
+}
+
+bool Procedure::isFastConstant(const ValueKey& constant)
+{
+ if (!constant)
+ return false;
+ return m_fastConstants.contains(constant);
+}
+
</ins><span class="cx"> void* Procedure::addDataSection(size_t size)
</span><span class="cx"> {
</span><span class="cx"> if (!size)
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3Procedureh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3Procedure.h (193681 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3Procedure.h 2015-12-08 02:38:37 UTC (rev 193681)
+++ trunk/Source/JavaScriptCore/b3/B3Procedure.h 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -31,10 +31,12 @@
</span><span class="cx"> #include "B3OpaqueByproducts.h"
</span><span class="cx"> #include "B3Origin.h"
</span><span class="cx"> #include "B3Type.h"
</span><ins>+#include "B3ValueKey.h"
</ins><span class="cx"> #include "PureNaN.h"
</span><span class="cx"> #include "RegisterAtOffsetList.h"
</span><span class="cx"> #include <wtf/Bag.h>
</span><span class="cx"> #include <wtf/FastMalloc.h>
</span><ins>+#include <wtf/HashSet.h>
</ins><span class="cx"> #include <wtf/Noncopyable.h>
</span><span class="cx"> #include <wtf/PrintStream.h>
</span><span class="cx"> #include <wtf/TriState.h>
</span><span class="lines">@@ -44,6 +46,8 @@
</span><span class="cx">
</span><span class="cx"> class BasicBlock;
</span><span class="cx"> class BlockInsertionSet;
</span><ins>+class CFG;
+class Dominators;
</ins><span class="cx"> class Value;
</span><span class="cx">
</span><span class="cx"> namespace Air { class Code; }
</span><span class="lines">@@ -70,6 +74,10 @@
</span><span class="cx"> void resetValueOwners();
</span><span class="cx"> void resetReachability();
</span><span class="cx">
</span><ins>+ // This destroys CFG analyses. If we ask for them again, we will recompute them. Usually you
+ // should call this anytime you call resetReachability().
+ void invalidateCFG();
+
</ins><span class="cx"> JS_EXPORT_PRIVATE void dump(PrintStream&) const;
</span><span class="cx">
</span><span class="cx"> unsigned size() const { return m_blocks.size(); }
</span><span class="lines">@@ -200,6 +208,13 @@
</span><span class="cx">
</span><span class="cx"> void deleteValue(Value*);
</span><span class="cx">
</span><ins>+ CFG& cfg() const { return *m_cfg; }
+
+ Dominators& dominators();
+
+ void addFastConstant(const ValueKey&);
+ bool isFastConstant(const ValueKey&);
+
</ins><span class="cx"> // The name has to be a string literal, since we don't do any memory management for the string.
</span><span class="cx"> void setLastPhaseName(const char* name)
</span><span class="cx"> {
</span><span class="lines">@@ -240,6 +255,9 @@
</span><span class="cx"> Vector<std::unique_ptr<BasicBlock>> m_blocks;
</span><span class="cx"> Vector<std::unique_ptr<Value>> m_values;
</span><span class="cx"> Vector<size_t> m_valueIndexFreeList;
</span><ins>+ std::unique_ptr<CFG> m_cfg;
+ std::unique_ptr<Dominators> m_dominators;
+ HashSet<ValueKey> m_fastConstants;
</ins><span class="cx"> const char* m_lastPhaseName;
</span><span class="cx"> std::unique_ptr<OpaqueByproducts> m_byproducts;
</span><span class="cx"> std::unique_ptr<Air::Code> m_code;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3ReduceStrengthcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3ReduceStrength.cpp (193681 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3ReduceStrength.cpp 2015-12-08 02:38:37 UTC (rev 193681)
+++ trunk/Source/JavaScriptCore/b3/B3ReduceStrength.cpp 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -117,6 +117,7 @@
</span><span class="cx">
</span><span class="cx"> if (m_changedCFG) {
</span><span class="cx"> m_proc.resetReachability();
</span><ins>+ m_proc.invalidateCFG();
</ins><span class="cx"> m_changed = true;
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3ValueInlinesh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3ValueInlines.h (193681 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3ValueInlines.h 2015-12-08 02:38:37 UTC (rev 193681)
+++ trunk/Source/JavaScriptCore/b3/B3ValueInlines.h 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -54,14 +54,7 @@
</span><span class="cx">
</span><span class="cx"> inline bool Value::isConstant() const
</span><span class="cx"> {
</span><del>- switch (opcode()) {
- case Const32:
- case Const64:
- case ConstDouble:
- return true;
- default:
- return false;
- }
</del><ins>+ return B3::isConstant(opcode());
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> inline bool Value::isInteger() const
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3ValueKeyh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3ValueKey.h (193681 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3ValueKey.h 2015-12-08 02:38:37 UTC (rev 193681)
+++ trunk/Source/JavaScriptCore/b3/B3ValueKey.h 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -120,6 +120,11 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ bool isConstant() const
+ {
+ return B3::isConstant(opcode());
+ }
+
</ins><span class="cx"> // Attempts to materialize the Value for this ValueKey. May return nullptr if the value cannot
</span><span class="cx"> // be materialized. This happens for CheckAdd and friends. You can use canMaterialize() to check
</span><span class="cx"> // if your key is materializable.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirCodecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirCode.cpp (193681 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirCode.cpp 2015-12-08 02:38:37 UTC (rev 193681)
+++ trunk/Source/JavaScriptCore/b3/air/AirCode.cpp 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -134,6 +134,11 @@
</span><span class="cx"> return nullptr;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+void Code::addFastTmp(Tmp tmp)
+{
+ m_fastTmps.add(tmp);
+}
+
</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="trunkSourceJavaScriptCoreb3airAirCodeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirCode.h (193681 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirCode.h 2015-12-08 02:38:37 UTC (rev 193681)
+++ trunk/Source/JavaScriptCore/b3/air/AirCode.h 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -31,6 +31,7 @@
</span><span class="cx"> #include "AirBasicBlock.h"
</span><span class="cx"> #include "AirSpecial.h"
</span><span class="cx"> #include "AirStackSlot.h"
</span><ins>+#include "AirTmp.h"
</ins><span class="cx"> #include "RegisterAtOffsetList.h"
</span><span class="cx"> #include "StackAlignment.h"
</span><span class="cx">
</span><span class="lines">@@ -289,6 +290,9 @@
</span><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> SpecialsCollection specials() const { return SpecialsCollection(*this); }
</span><ins>+
+ void addFastTmp(Tmp);
+ bool isFastTmp(Tmp tmp) const { return m_fastTmps.contains(tmp); }
</ins><span class="cx">
</span><span class="cx"> // The name has to be a string literal, since we don't do any memory management for the string.
</span><span class="cx"> void setLastPhaseName(const char* name)
</span><span class="lines">@@ -307,6 +311,7 @@
</span><span class="cx"> Vector<std::unique_ptr<StackSlot>> m_stackSlots;
</span><span class="cx"> Vector<std::unique_ptr<BasicBlock>> m_blocks;
</span><span class="cx"> Vector<std::unique_ptr<Special>> m_specials;
</span><ins>+ HashSet<Tmp> m_fastTmps;
</ins><span class="cx"> CCallSpecial* m_cCallSpecial { nullptr };
</span><span class="cx"> unsigned m_numGPTmps { 0 };
</span><span class="cx"> unsigned m_numFPTmps { 0 };
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirIteratedRegisterCoalescingcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp (193681 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp 2015-12-08 02:38:37 UTC (rev 193681)
+++ trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -563,6 +563,11 @@
</span><span class="cx"> // Higher score means more desirable to spill. Lower scores maximize the likelihood that a tmp
</span><span class="cx"> // gets a register.
</span><span class="cx"> auto score = [&] (Tmp tmp) -> double {
</span><ins>+ // Air exposes the concept of "fast tmps", and we interpret that to mean that the tmp
+ // should always be in a register.
+ if (m_code.isFastTmp(tmp))
+ return 0;
+
</ins><span class="cx"> // All else being equal, the score should be directly related to the degree.
</span><span class="cx"> double degree = static_cast<double>(m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]);
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGCFGh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGCFG.h (193681 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGCFG.h 2015-12-08 02:38:37 UTC (rev 193681)
+++ trunk/Source/JavaScriptCore/dfg/DFGCFG.h 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -36,6 +36,8 @@
</span><span class="cx"> namespace JSC { namespace DFG {
</span><span class="cx">
</span><span class="cx"> class CFG {
</span><ins>+ WTF_MAKE_NONCOPYABLE(CFG);
+ WTF_MAKE_FAST_ALLOCATED;
</ins><span class="cx"> public:
</span><span class="cx"> typedef BasicBlock* Node;
</span><span class="cx"> typedef BlockSet Set;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGDominatorsh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGDominators.h (193681 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGDominators.h 2015-12-08 02:38:37 UTC (rev 193681)
+++ trunk/Source/JavaScriptCore/dfg/DFGDominators.h 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2011, 2014 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2011, 2014, 2015 Apple Inc. All rights reserved.
</ins><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="cx"> * modification, are permitted provided that the following conditions
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGSSACalculatorcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGSSACalculator.cpp (193681 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGSSACalculator.cpp 2015-12-08 02:38:37 UTC (rev 193681)
+++ trunk/Source/JavaScriptCore/dfg/DFGSSACalculator.cpp 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -95,12 +95,12 @@
</span><span class="cx">
</span><span class="cx"> SSACalculator::Def* SSACalculator::nonLocalReachingDef(BasicBlock* block, Variable* variable)
</span><span class="cx"> {
</span><del>- return reachingDefAtTail(m_graph.m_dominators->immediateDominatorOf(block), variable);
</del><ins>+ return reachingDefAtTail(m_graph.m_dominators->idom(block), variable);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> SSACalculator::Def* SSACalculator::reachingDefAtTail(BasicBlock* block, Variable* variable)
</span><span class="cx"> {
</span><del>- for (; block; block = m_graph.m_dominators->immediateDominatorOf(block)) {
</del><ins>+ for (; block; block = m_graph.m_dominators->idom(block)) {
</ins><span class="cx"> if (Def* def = m_data[block].m_defs.get(variable))
</span><span class="cx"> return def;
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreftlFTLLowerDFGToLLVMcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp (193681 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp 2015-12-08 02:38:37 UTC (rev 193681)
+++ trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -303,6 +303,13 @@
</span><span class="cx"> #endif
</span><span class="cx"> m_tagTypeNumber = m_out.constInt64(TagTypeNumber);
</span><span class="cx"> m_tagMask = m_out.constInt64(TagMask);
</span><ins>+
+#if FTL_USES_B3
+ // Make sure that B3 knows that we really care about the mask registers. This forces the
+ // constants to be materialized in registers.
+ m_proc.addFastConstant(m_tagTypeNumber->key());
+ m_proc.addFastConstant(m_tagMask->key());
+#endif // FTL_USES_B3
</ins><span class="cx">
</span><span class="cx"> m_out.storePtr(m_out.constIntPtr(codeBlock()), addressFor(JSStack::CodeBlock));
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (193681 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog 2015-12-08 02:38:37 UTC (rev 193681)
+++ trunk/Source/WTF/ChangeLog 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -1,3 +1,27 @@
</span><ins>+2015-12-07 Filip Pizlo <fpizlo@apple.com>
+
+ FTL B3 should be able to flag the tag constants as being super important so that B3 can hoist them and Air can force them into registers
+ https://bugs.webkit.org/show_bug.cgi?id=151955
+
+ Reviewed by Geoffrey Garen.
+
+ Remove some remaining DFG-specific snippets from Dominators. This used to be a non-template
+ DFG class, and some time ago I hoisted it into WTF and made it generic. But since the only
+ user of the class was the DFG, this class still had a handful of DFG-specific snippets that
+ didn't compile when I started using it from B3.
+
+ Also renamed immediateDominatorOf() to idom(). This is the sort of abbreviation that we
+ wouldn't ordinarily want to have in WebKit. But WebKit does allow for abbreviations that are
+ "more canonical". The term "idom" is definitely more canonical than "immediateDominatorOf".
+
+ * wtf/Dominators.h:
+ (WTF::Dominators::dominates):
+ (WTF::Dominators::idom):
+ (WTF::Dominators::forAllStrictDominatorsOf):
+ (WTF::Dominators::NaiveDominators::dominates):
+ (WTF::Dominators::NaiveDominators::dump):
+ (WTF::Dominators::ValidationContext::handleErrors):
+
</ins><span class="cx"> 2015-12-03 Anders Carlsson <andersca@apple.com>
</span><span class="cx">
</span><span class="cx"> Remove Objective-C GC support
</span></span></pre></div>
<a id="trunkSourceWTFwtfDominatorsh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/Dominators.h (193681 => 193682)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/Dominators.h 2015-12-08 02:38:37 UTC (rev 193681)
+++ trunk/Source/WTF/wtf/Dominators.h 2015-12-08 02:46:22 UTC (rev 193682)
</span><span class="lines">@@ -26,6 +26,7 @@
</span><span class="cx"> #ifndef WTFDominators_h
</span><span class="cx"> #define WTFDominators_h
</span><span class="cx">
</span><ins>+#include <wtf/FastBitVector.h>
</ins><span class="cx"> #include <wtf/GraphNodeWorklist.h>
</span><span class="cx">
</span><span class="cx"> namespace WTF {
</span><span class="lines">@@ -120,8 +121,9 @@
</span><span class="cx"> {
</span><span class="cx"> return from == to || strictlyDominates(from, to);
</span><span class="cx"> }
</span><del>-
- typename Graph::Node immediateDominatorOf(typename Graph::Node block) const
</del><ins>+
+ // Returns the immediate dominator of this block. Returns null for the root block.
+ typename Graph::Node idom(typename Graph::Node block) const
</ins><span class="cx"> {
</span><span class="cx"> return m_data[block].idomParent;
</span><span class="cx"> }
</span><span class="lines">@@ -555,7 +557,7 @@
</span><span class="cx">
</span><span class="cx"> bool dominates(typename Graph::Node from, typename Graph::Node to) const
</span><span class="cx"> {
</span><del>- return dominates(from->index, to->index);
</del><ins>+ return dominates(m_graph.index(from), m_graph.index(to));
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void dump(PrintStream& out) const
</span><span class="lines">@@ -593,7 +595,7 @@
</span><span class="cx"> return m_results[idx].setAndCheck(m_scratch);
</span><span class="cx"> }
</span><span class="cx">
</span><del>- Graph m_graph;
</del><ins>+ Graph& m_graph;
</ins><span class="cx"> Vector<FastBitVector> m_results; // For each block, the bitvector of blocks that dominate it.
</span><span class="cx"> FastBitVector m_scratch; // A temporary bitvector with bit for each block. We recycle this to save new/deletes.
</span><span class="cx"> };
</span><span class="lines">@@ -636,12 +638,12 @@
</span><span class="cx"> continue;
</span><span class="cx"> dataLog(" Block ", graph.dump(graph.node(blockIndex)), ": successors = [");
</span><span class="cx"> CommaPrinter comma;
</span><del>- for (unsigned i = 0; i < block->numSuccessors(); ++i)
- dataLog(comma, graph.dump(block->successor(i)));
</del><ins>+ for (auto successor : graph.successors(block))
+ dataLog(comma, graph.dump(successor));
</ins><span class="cx"> dataLog("], predecessors = [");
</span><span class="cx"> comma = CommaPrinter();
</span><del>- for (unsigned i = 0; i < block->predecessors.size(); ++i)
- dataLog(comma, graph.dump(block->predecessors[i]));
</del><ins>+ for (auto predecessor : graph.predecessors(block))
+ dataLog(comma, graph.dump(predecessor));
</ins><span class="cx"> dataLog("]\n");
</span><span class="cx"> }
</span><span class="cx"> dataLog("\n");
</span></span></pre>
</div>
</div>
</body>
</html>