<!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>[195981] 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/195981">195981</a></dd>
<dt>Author</dt> <dd>benjamin@webkit.org</dd>
<dt>Date</dt> <dd>2016-02-01 15:19:26 -0800 (Mon, 01 Feb 2016)</dd>
</dl>
<h3>Log Message</h3>
<pre>[JSC] IRC can coalesce the frame pointer with a Tmp that is modified
https://bugs.webkit.org/show_bug.cgi?id=153694
Reviewed by Filip Pizlo.
Let's say we have:
Move(FP, Tmp1)
Add64(#1, Tmp1)
If we were to coalesce the Move, we would modify the frame pointer.
Well, that's exactly what was happening with IRC.
Since the epilogue is not know to Air before IRC, the liveness analysis
never discovers that FP is live when Tmp1 is UseDef by Add64. Adding
FP would a be a problem anyway for a bunch of reasons.
I tried two ways to prevent IRC to override IRC:
1) Add an interference edge with FP for all non-duplication Defs.
2) Let coalesce() know about FP and constraint any coalescing with a re-Def.
The two are within margin of error for performance. The second one was considerably
more complicated. This patch implements the first one.
Some extra note:
-It is very important to not increment the degree of a Tmp when making it interfere
with FP. FP is not a valid color, it is not counted in the "K" colors considered
for coloring. Increasing the degree with the edge to FP would make every stage
pessimistic since there is an extra degree that can never be removed.
-I put "interferenceEdges" and "adjacencyList" in an inconsistent state.
This is intentional, "interferenceEdges" is used to test the existence of an edge,
"adjacencyList" is used to go over all the edges. In this case, we don't want
the edge with FP to be considered when pruning the graph.
* b3/air/AirIteratedRegisterCoalescing.cpp:
One branch could be transformed into an assertion: TmpLiveness is type specific now.
* b3/testb3.cpp:
(JSC::B3::testOverrideFramePointer):
(JSC::B3::run):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirIteratedRegisterCoalescingcpp">trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3testb3cpp">trunk/Source/JavaScriptCore/b3/testb3.cpp</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (195980 => 195981)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2016-02-01 22:13:21 UTC (rev 195980)
+++ trunk/Source/JavaScriptCore/ChangeLog 2016-02-01 23:19:26 UTC (rev 195981)
</span><span class="lines">@@ -1,3 +1,44 @@
</span><ins>+2016-02-01 Benjamin Poulain <benjamin@webkit.org>
+
+ [JSC] IRC can coalesce the frame pointer with a Tmp that is modified
+ https://bugs.webkit.org/show_bug.cgi?id=153694
+
+ Reviewed by Filip Pizlo.
+
+ Let's say we have:
+ Move(FP, Tmp1)
+ Add64(#1, Tmp1)
+
+ If we were to coalesce the Move, we would modify the frame pointer.
+ Well, that's exactly what was happening with IRC.
+
+ Since the epilogue is not know to Air before IRC, the liveness analysis
+ never discovers that FP is live when Tmp1 is UseDef by Add64. Adding
+ FP would a be a problem anyway for a bunch of reasons.
+
+ I tried two ways to prevent IRC to override IRC:
+ 1) Add an interference edge with FP for all non-duplication Defs.
+ 2) Let coalesce() know about FP and constraint any coalescing with a re-Def.
+
+ The two are within margin of error for performance. The second one was considerably
+ more complicated. This patch implements the first one.
+
+ Some extra note:
+ -It is very important to not increment the degree of a Tmp when making it interfere
+ with FP. FP is not a valid color, it is not counted in the "K" colors considered
+ for coloring. Increasing the degree with the edge to FP would make every stage
+ pessimistic since there is an extra degree that can never be removed.
+ -I put "interferenceEdges" and "adjacencyList" in an inconsistent state.
+ This is intentional, "interferenceEdges" is used to test the existence of an edge,
+ "adjacencyList" is used to go over all the edges. In this case, we don't want
+ the edge with FP to be considered when pruning the graph.
+
+ * b3/air/AirIteratedRegisterCoalescing.cpp:
+ One branch could be transformed into an assertion: TmpLiveness is type specific now.
+ * b3/testb3.cpp:
+ (JSC::B3::testOverrideFramePointer):
+ (JSC::B3::run):
+
</ins><span class="cx"> 2016-02-01 Csaba Osztrogonác <ossy@webkit.org>
</span><span class="cx">
</span><span class="cx"> Unreviewed speculative buildfix.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirIteratedRegisterCoalescingcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp (195980 => 195981)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp 2016-02-01 22:13:21 UTC (rev 195980)
+++ trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp 2016-02-01 23:19:26 UTC (rev 195981)
</span><span class="lines">@@ -891,9 +891,15 @@
</span><span class="cx"> return;
</span><span class="cx">
</span><span class="cx"> for (const Tmp& liveTmp : liveTmps) {
</span><del>- if (liveTmp.isGP() == (type == Arg::GP))
- addEdge(arg, liveTmp);
</del><ins>+ ASSERT(liveTmp.isGP() == (type == Arg::GP));
+ addEdge(arg, liveTmp);
</ins><span class="cx"> }
</span><ins>+
+ if (type == Arg::GP && !arg.isGPR()) {
+ m_interferenceEdges.add(InterferenceEdge(
+ AbsoluteTmpMapper<type>::absoluteIndex(Tmp(MacroAssembler::framePointerRegister)),
+ AbsoluteTmpMapper<type>::absoluteIndex(arg)));
+ }
</ins><span class="cx"> });
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -1068,8 +1074,13 @@
</span><span class="cx"> tmpsWithInterferences.add(AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(edge.second()));
</span><span class="cx"> }
</span><span class="cx">
</span><del>- for (const auto& tmp : tmpsWithInterferences)
- out.print(" ", tmp.internalValue(), " [label=\"", tmp, " (", m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(tmp)], ")\"];\n");
</del><ins>+ for (const auto& tmp : tmpsWithInterferences) {
+ unsigned tmpIndex = AbsoluteTmpMapper<type>::absoluteIndex(tmp);
+ if (tmpIndex < m_degrees.size())
+ out.print(" ", tmp.internalValue(), " [label=\"", tmp, " (", m_degrees[tmpIndex], ")\"];\n");
+ else
+ out.print(" ", tmp.internalValue(), " [label=\"", tmp, "\"];\n");
+ }
</ins><span class="cx">
</span><span class="cx"> for (const auto& edge : m_interferenceEdges)
</span><span class="cx"> out.print(" ", edge.first(), " -- ", edge.second(), ";\n");
</span><span class="lines">@@ -1130,6 +1141,9 @@
</span><span class="cx"> while (true) {
</span><span class="cx"> ++m_numIterations;
</span><span class="cx">
</span><ins>+ if (traceDebug)
+ dataLog("Code at iteration ", m_numIterations, ":\n", m_code);
+
</ins><span class="cx"> // FIXME: One way to optimize this code is to remove the recomputation inside the fixpoint.
</span><span class="cx"> // We need to recompute because spilling adds tmps, but we could just update tmpWidth when we
</span><span class="cx"> // add those tmps. Note that one easy way to remove the recomputation is to make any newly
</span><span class="lines">@@ -1148,6 +1162,9 @@
</span><span class="cx"> ColoringAllocator<type> allocator(m_code, m_tmpWidth, m_useCounts, unspillableTmps);
</span><span class="cx"> if (!allocator.requiresSpilling()) {
</span><span class="cx"> assignRegistersToTmp(allocator);
</span><ins>+ if (traceDebug)
+ dataLog("Successfull allocation at iteration ", m_numIterations, ":\n", m_code);
+
</ins><span class="cx"> return;
</span><span class="cx"> }
</span><span class="cx"> addSpillAndFill<type>(allocator, unspillableTmps);
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3testb3cpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/testb3.cpp (195980 => 195981)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/testb3.cpp 2016-02-01 22:13:21 UTC (rev 195980)
+++ trunk/Source/JavaScriptCore/b3/testb3.cpp 2016-02-01 23:19:26 UTC (rev 195981)
</span><span class="lines">@@ -4983,6 +4983,41 @@
</span><span class="cx"> CHECK(fp >= bitwise_cast<char*>(&proc) - 10000);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+void testOverrideFramePointer()
+{
+ {
+ Procedure proc;
+ BasicBlock* root = proc.addBlock();
+
+ // Add a stack slot to make the frame non trivial.
+ root->appendNew<SlotBaseValue>(proc, Origin(), proc.addStackSlot(8, StackSlotKind::Locked));
+
+ // Sub on x86 UseDef the source. If FP is not protected correctly, it will be overridden since it is the last visible use.
+ Value* offset = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
+ Value* fp = root->appendNew<Value>(proc, FramePointer, Origin());
+ Value* result = root->appendNew<Value>(proc, Sub, Origin(), fp, offset);
+
+ root->appendNew<ControlValue>(proc, Return, Origin(), result);
+ CHECK(compileAndRun<int64_t>(proc, 1));
+ }
+ {
+ Procedure proc;
+ BasicBlock* root = proc.addBlock();
+
+ root->appendNew<SlotBaseValue>(proc, Origin(), proc.addStackSlot(8, StackSlotKind::Locked));
+
+ Value* offset = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
+ Value* fp = root->appendNew<Value>(proc, FramePointer, Origin());
+ Value* offsetFP = root->appendNew<Value>(proc, BitAnd, Origin(), offset, fp);
+ Value* arg = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1);
+ Value* offsetArg = root->appendNew<Value>(proc, Add, Origin(), offset, arg);
+ Value* result = root->appendNew<Value>(proc, Add, Origin(), offsetArg, offsetFP);
+
+ root->appendNew<ControlValue>(proc, Return, Origin(), result);
+ CHECK(compileAndRun<int64_t>(proc, 1, 2));
+ }
+}
+
</ins><span class="cx"> void testStackSlot()
</span><span class="cx"> {
</span><span class="cx"> Procedure proc;
</span><span class="lines">@@ -10766,6 +10801,7 @@
</span><span class="cx"> RUN(testLoadAddrShift(2));
</span><span class="cx"> RUN(testLoadAddrShift(3));
</span><span class="cx"> RUN(testFramePointer());
</span><ins>+ RUN(testOverrideFramePointer());
</ins><span class="cx"> RUN(testStackSlot());
</span><span class="cx"> RUN(testLoadFromFramePointer());
</span><span class="cx"> RUN(testStoreLoadStackSlot(50));
</span></span></pre>
</div>
</div>
</body>
</html>