<!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>[191977] 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/191977">191977</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2015-11-03 14:03:48 -0800 (Tue, 03 Nov 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>B3::LowerToAir should do copy propagation
https://bugs.webkit.org/show_bug.cgi?id=150775
Reviewed by Geoffrey Garen.
What we are trying to do is remove the unnecessary Move's and Move32's from Trunc and ZExt32.
You could think of this as an Air optimization, and indeed, Air is powerful enough that we
could write a phase that does copy propagation through Move's and Move32's. For Move32's it
would only copy-propagate if it proved that the value was already zero-extended. We could
know this by just adding a Def32 role to Air.
But this patch takes a different approach: we ensure that we don't generate such redundant
Move's and Move32's to begin with. The reason is that it's much cheaper to do analysis over
B3 than over Air. So, whenever possible, and optimization should be implemented in B3. In
this case the optimization can't quite be implemented in B3 because you cannot remove a Trunc
or ZExt32 without violating the B3 type system. So, the best place to do this optimization is
during lowering: we can use B3 for our analysis and we can use Air to express the
transformation.
Copy propagating during B3->Air lowering is natural because we are creating "SSA-like" Tmps
from the B3 Values. They are SSA-like in the sense that except the tmp for a Phi, we know
that the Tmp will be assigned once and that the assignment will dominate all uses. So, if we
see an operation like Trunc that is semantically just a Move, we can skip the Move and just
claim that the Trunc has the same Tmp as its child. We do something similar for ZExt32,
except with that one we have to analyze IR to ensure that the value will actually be zero
extended. Note that this kind of reasoning about how Tmps work in Air is only possible in the
B3->Air lowering, since at that point we know for sure which Tmps behave this way. If we
wanted to do anything like this as a later Air phase, we'd have to do more analysis to first
prove that Tmps behave in this way.
* b3/B3LowerToAir.cpp:
(JSC::B3::Air::LowerToAir::run):
(JSC::B3::Air::LowerToAir::highBitsAreZero):
(JSC::B3::Air::LowerToAir::shouldCopyPropagate):
(JSC::B3::Air::LowerToAir::tmp):
(JSC::B3::Air::LowerToAir::tryStore):
(JSC::B3::Air::LowerToAir::tryTrunc):
(JSC::B3::Air::LowerToAir::tryZExt32):
(JSC::B3::Air::LowerToAir::tryIdentity):
(JSC::B3::Air::LowerToAir::tryTruncArgumentReg): Deleted.
* b3/B3LoweringMatcher.patterns:</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3LowerToAircpp">trunk/Source/JavaScriptCore/b3/B3LowerToAir.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3LoweringMatcherpatterns">trunk/Source/JavaScriptCore/b3/B3LoweringMatcher.patterns</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (191976 => 191977)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-11-03 21:56:35 UTC (rev 191976)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-11-03 22:03:48 UTC (rev 191977)
</span><span class="lines">@@ -1,3 +1,47 @@
</span><ins>+2015-11-03 Filip Pizlo <fpizlo@apple.com>
+
+ B3::LowerToAir should do copy propagation
+ https://bugs.webkit.org/show_bug.cgi?id=150775
+
+ Reviewed by Geoffrey Garen.
+
+ What we are trying to do is remove the unnecessary Move's and Move32's from Trunc and ZExt32.
+ You could think of this as an Air optimization, and indeed, Air is powerful enough that we
+ could write a phase that does copy propagation through Move's and Move32's. For Move32's it
+ would only copy-propagate if it proved that the value was already zero-extended. We could
+ know this by just adding a Def32 role to Air.
+
+ But this patch takes a different approach: we ensure that we don't generate such redundant
+ Move's and Move32's to begin with. The reason is that it's much cheaper to do analysis over
+ B3 than over Air. So, whenever possible, and optimization should be implemented in B3. In
+ this case the optimization can't quite be implemented in B3 because you cannot remove a Trunc
+ or ZExt32 without violating the B3 type system. So, the best place to do this optimization is
+ during lowering: we can use B3 for our analysis and we can use Air to express the
+ transformation.
+
+ Copy propagating during B3->Air lowering is natural because we are creating "SSA-like" Tmps
+ from the B3 Values. They are SSA-like in the sense that except the tmp for a Phi, we know
+ that the Tmp will be assigned once and that the assignment will dominate all uses. So, if we
+ see an operation like Trunc that is semantically just a Move, we can skip the Move and just
+ claim that the Trunc has the same Tmp as its child. We do something similar for ZExt32,
+ except with that one we have to analyze IR to ensure that the value will actually be zero
+ extended. Note that this kind of reasoning about how Tmps work in Air is only possible in the
+ B3->Air lowering, since at that point we know for sure which Tmps behave this way. If we
+ wanted to do anything like this as a later Air phase, we'd have to do more analysis to first
+ prove that Tmps behave in this way.
+
+ * b3/B3LowerToAir.cpp:
+ (JSC::B3::Air::LowerToAir::run):
+ (JSC::B3::Air::LowerToAir::highBitsAreZero):
+ (JSC::B3::Air::LowerToAir::shouldCopyPropagate):
+ (JSC::B3::Air::LowerToAir::tmp):
+ (JSC::B3::Air::LowerToAir::tryStore):
+ (JSC::B3::Air::LowerToAir::tryTrunc):
+ (JSC::B3::Air::LowerToAir::tryZExt32):
+ (JSC::B3::Air::LowerToAir::tryIdentity):
+ (JSC::B3::Air::LowerToAir::tryTruncArgumentReg): Deleted.
+ * b3/B3LoweringMatcher.patterns:
+
</ins><span class="cx"> 2015-11-03 Joseph Pecoraro <pecoraro@apple.com>
</span><span class="cx">
</span><span class="cx"> Web Inspector: Move ScriptDebugServer::Task to WorkerScriptDebugServer where it is actually used
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3LowerToAircpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3LowerToAir.cpp (191976 => 191977)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3LowerToAir.cpp 2015-11-03 21:56:35 UTC (rev 191976)
+++ trunk/Source/JavaScriptCore/b3/B3LowerToAir.cpp 2015-11-03 22:03:48 UTC (rev 191977)
</span><span class="lines">@@ -120,11 +120,56 @@
</span><span class="cx"> insertionSet.execute(code[0]);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ bool highBitsAreZero(Value* value)
+ {
+ switch (value->opcode()) {
+ case Const32:
+ // We will use a Move immediate instruction, which may sign extend.
+ return value->asInt32() >= 0;
+ case Trunc:
+ // Trunc is copy-propagated, so the value may have garbage in the high bits.
+ return false;
+ case CCall:
+ // Calls are allowed to have garbage in their high bits.
+ return false;
+ case Patchpoint:
+ // For now, we assume that patchpoints may return garbage in the high bits. This simplifies
+ // the interface. We may revisit for performance reasons later.
+ return false;
+ case Phi:
+ // FIXME: We could do this right.
+ // https://bugs.webkit.org/show_bug.cgi?id=150845
+ return false;
+ default:
+ // All other operations that return Int32 should lower to something that zero extends.
+ return value->type() == Int32;
+ }
+ }
+
+ // NOTE: This entire mechanism could be done over Air, if we felt that this would be fast enough.
+ // For now we're assuming that it's faster to do this here, since analyzing B3 is so cheap.
+ bool shouldCopyPropagate(Value* value)
+ {
+ switch (value->opcode()) {
+ case Trunc:
+ case Identity:
+ return true;
+ case ZExt32:
+ return highBitsAreZero(value->child(0));
+ default:
+ return false;
+ }
+ }
+
</ins><span class="cx"> Tmp tmp(Value* value)
</span><span class="cx"> {
</span><span class="cx"> Tmp& tmp = valueToTmp[value];
</span><del>- if (!tmp)
</del><ins>+ if (!tmp) {
+ while (shouldCopyPropagate(value))
+ value = value->child(0);
</ins><span class="cx"> tmp = code.newTmp(isInt(value->type()) ? Arg::GP : Arg::FP);
</span><ins>+ valueToTmp[value] = tmp;
+ }
</ins><span class="cx"> return tmp;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -664,27 +709,19 @@
</span><span class="cx"> return true;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- bool tryTruncArgumentReg(Value* argumentReg)
- {
- prologue.append(Inst(
- Move, currentValue,
- Tmp(argumentReg->as<ArgumentRegValue>()->argumentReg()),
- tmp(currentValue)));
- return true;
- }
-
</del><span class="cx"> bool tryTrunc(Value* value)
</span><span class="cx"> {
</span><del>- // FIXME: This could just be a copy propagation rule.
- // https://bugs.webkit.org/show_bug.cgi?id=150775
- append(Move, tmp(value), tmp(currentValue));
</del><ins>+ ASSERT_UNUSED(value, tmp(value) == tmp(currentValue));
</ins><span class="cx"> return true;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> bool tryZExt32(Value* value)
</span><span class="cx"> {
</span><del>- // FIXME: This could just be a copy propagation rule, with caveats. ;-)
- // https://bugs.webkit.org/show_bug.cgi?id=150775
</del><ins>+ if (highBitsAreZero(value)) {
+ ASSERT(tmp(value) == tmp(currentValue));
+ return true;
+ }
+
</ins><span class="cx"> append(Move32, tmp(value), tmp(currentValue));
</span><span class="cx"> return true;
</span><span class="cx"> }
</span><span class="lines">@@ -839,7 +876,7 @@
</span><span class="cx">
</span><span class="cx"> bool tryIdentity(Value* value)
</span><span class="cx"> {
</span><del>- append(relaxedMoveForType(value->type()), immOrTmp(value), tmp(currentValue));
</del><ins>+ ASSERT_UNUSED(value, tmp(value) == tmp(currentValue));
</ins><span class="cx"> return true;
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3LoweringMatcherpatterns"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3LoweringMatcher.patterns (191976 => 191977)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3LoweringMatcher.patterns 2015-11-03 21:56:35 UTC (rev 191976)
+++ trunk/Source/JavaScriptCore/b3/B3LoweringMatcher.patterns 2015-11-03 22:03:48 UTC (rev 191977)
</span><span class="lines">@@ -41,7 +41,6 @@
</span><span class="cx"> StoreAndLoad = Store(BitAnd(left, right), address)
</span><span class="cx"> Store = Store(value, address)
</span><span class="cx">
</span><del>-TruncArgumentReg = Trunc(argumentReg = ArgumentReg())
</del><span class="cx"> Trunc = Trunc(value)
</span><span class="cx">
</span><span class="cx"> ZExt32 = ZExt32(value)
</span></span></pre>
</div>
</div>
</body>
</html>