- Revision
- 195981
- Author
- [email protected]
- Date
- 2016-02-01 15:19:26 -0800 (Mon, 01 Feb 2016)
Log Message
[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):
Modified Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (195980 => 195981)
--- trunk/Source/_javascript_Core/ChangeLog 2016-02-01 22:13:21 UTC (rev 195980)
+++ trunk/Source/_javascript_Core/ChangeLog 2016-02-01 23:19:26 UTC (rev 195981)
@@ -1,3 +1,44 @@
+2016-02-01 Benjamin Poulain <[email protected]>
+
+ [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):
+
2016-02-01 Csaba Osztrogonác <[email protected]>
Unreviewed speculative buildfix.
Modified: trunk/Source/_javascript_Core/b3/air/AirIteratedRegisterCoalescing.cpp (195980 => 195981)
--- trunk/Source/_javascript_Core/b3/air/AirIteratedRegisterCoalescing.cpp 2016-02-01 22:13:21 UTC (rev 195980)
+++ trunk/Source/_javascript_Core/b3/air/AirIteratedRegisterCoalescing.cpp 2016-02-01 23:19:26 UTC (rev 195981)
@@ -891,9 +891,15 @@
return;
for (const Tmp& liveTmp : liveTmps) {
- if (liveTmp.isGP() == (type == Arg::GP))
- addEdge(arg, liveTmp);
+ ASSERT(liveTmp.isGP() == (type == Arg::GP));
+ addEdge(arg, liveTmp);
}
+
+ if (type == Arg::GP && !arg.isGPR()) {
+ m_interferenceEdges.add(InterferenceEdge(
+ AbsoluteTmpMapper<type>::absoluteIndex(Tmp(MacroAssembler::framePointerRegister)),
+ AbsoluteTmpMapper<type>::absoluteIndex(arg)));
+ }
});
}
@@ -1068,8 +1074,13 @@
tmpsWithInterferences.add(AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(edge.second()));
}
- for (const auto& tmp : tmpsWithInterferences)
- out.print(" ", tmp.internalValue(), " [label=\"", tmp, " (", m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(tmp)], ")\"];\n");
+ 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");
+ }
for (const auto& edge : m_interferenceEdges)
out.print(" ", edge.first(), " -- ", edge.second(), ";\n");
@@ -1130,6 +1141,9 @@
while (true) {
++m_numIterations;
+ if (traceDebug)
+ dataLog("Code at iteration ", m_numIterations, ":\n", m_code);
+
// FIXME: One way to optimize this code is to remove the recomputation inside the fixpoint.
// We need to recompute because spilling adds tmps, but we could just update tmpWidth when we
// add those tmps. Note that one easy way to remove the recomputation is to make any newly
@@ -1148,6 +1162,9 @@
ColoringAllocator<type> allocator(m_code, m_tmpWidth, m_useCounts, unspillableTmps);
if (!allocator.requiresSpilling()) {
assignRegistersToTmp(allocator);
+ if (traceDebug)
+ dataLog("Successfull allocation at iteration ", m_numIterations, ":\n", m_code);
+
return;
}
addSpillAndFill<type>(allocator, unspillableTmps);
Modified: trunk/Source/_javascript_Core/b3/testb3.cpp (195980 => 195981)
--- trunk/Source/_javascript_Core/b3/testb3.cpp 2016-02-01 22:13:21 UTC (rev 195980)
+++ trunk/Source/_javascript_Core/b3/testb3.cpp 2016-02-01 23:19:26 UTC (rev 195981)
@@ -4983,6 +4983,41 @@
CHECK(fp >= bitwise_cast<char*>(&proc) - 10000);
}
+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));
+ }
+}
+
void testStackSlot()
{
Procedure proc;
@@ -10766,6 +10801,7 @@
RUN(testLoadAddrShift(2));
RUN(testLoadAddrShift(3));
RUN(testFramePointer());
+ RUN(testOverrideFramePointer());
RUN(testStackSlot());
RUN(testLoadFromFramePointer());
RUN(testStoreLoadStackSlot(50));
