Title: [192516] trunk/Source/_javascript_Core
- Revision
- 192516
- Author
- commit-qu...@webkit.org
- Date
- 2015-11-17 11:11:22 -0800 (Tue, 17 Nov 2015)
Log Message
[JSC] IteratedRegisterCoalescingAllocator's freeze can add zombie Tmps to our coloring algorithm
https://bugs.webkit.org/show_bug.cgi?id=151345
Patch by Benjamin Poulain <bpoul...@apple.com> on 2015-11-17
Reviewed by Filip Pizlo.
The extended test of https://bugs.webkit.org/show_bug.cgi?id=151214 revealed a problem with
the Move freezing step of the iterated register allocator.
When freezing a move related Tmp, we go over all the move instructions and update the other
Tmp of the move as needed. If that Tmp is no longer Move related and is of low degree it can
be simplified too.
The problem arise when one of those Tmp was already coalesced. For example, say we have
1: move %tmp42, %tmp43
2: move %tmp42, %tmp44
The first move cannot be coalesced for some reason and is moved to the Active worklist.
The second move is coalesced and %tmp42 is now %tmp44.
When nothing can be simplified or coalesced, we look at freezing a Move-related Tmp.
Let's say we pick %tmp43. The code of freeze() was going to all the Move instructions
to update them. Here you would find @1 above, get %tmp42 as the other Tmp. Since %tmp42
is no longer move related, it is added to the simplify work list.
-> We just added a coalesced Tmp to our worklist!
To fix that, I get the alias of every other Tmp before updating its status.
There is still a problem: multiple Moves instructions may have been coalesced to the same
Tmp. We must not add a Tmp twice to a worklist.
To avoid duplicates, I rely on the fact that the freeze worklist should not contains
aliased Tmps. Before adding something to the simplify worklist, I check that it was
in the freeze worklist.
I cannot find how this problem would have been avoided in the original paper. I suspect
that may have been a bug in the pseudo-code.
* b3/air/AirIteratedRegisterCoalescing.cpp:
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::freeze):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::freezeMoves):
Modified Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (192515 => 192516)
--- trunk/Source/_javascript_Core/ChangeLog 2015-11-17 19:05:29 UTC (rev 192515)
+++ trunk/Source/_javascript_Core/ChangeLog 2015-11-17 19:11:22 UTC (rev 192516)
@@ -1,3 +1,46 @@
+2015-11-17 Benjamin Poulain <bpoul...@apple.com>
+
+ [JSC] IteratedRegisterCoalescingAllocator's freeze can add zombie Tmps to our coloring algorithm
+ https://bugs.webkit.org/show_bug.cgi?id=151345
+
+ Reviewed by Filip Pizlo.
+
+ The extended test of https://bugs.webkit.org/show_bug.cgi?id=151214 revealed a problem with
+ the Move freezing step of the iterated register allocator.
+
+ When freezing a move related Tmp, we go over all the move instructions and update the other
+ Tmp of the move as needed. If that Tmp is no longer Move related and is of low degree it can
+ be simplified too.
+
+ The problem arise when one of those Tmp was already coalesced. For example, say we have
+
+ 1: move %tmp42, %tmp43
+ 2: move %tmp42, %tmp44
+
+ The first move cannot be coalesced for some reason and is moved to the Active worklist.
+ The second move is coalesced and %tmp42 is now %tmp44.
+
+ When nothing can be simplified or coalesced, we look at freezing a Move-related Tmp.
+ Let's say we pick %tmp43. The code of freeze() was going to all the Move instructions
+ to update them. Here you would find @1 above, get %tmp42 as the other Tmp. Since %tmp42
+ is no longer move related, it is added to the simplify work list.
+ -> We just added a coalesced Tmp to our worklist!
+
+ To fix that, I get the alias of every other Tmp before updating its status.
+
+ There is still a problem: multiple Moves instructions may have been coalesced to the same
+ Tmp. We must not add a Tmp twice to a worklist.
+ To avoid duplicates, I rely on the fact that the freeze worklist should not contains
+ aliased Tmps. Before adding something to the simplify worklist, I check that it was
+ in the freeze worklist.
+
+ I cannot find how this problem would have been avoided in the original paper. I suspect
+ that may have been a bug in the pseudo-code.
+
+ * b3/air/AirIteratedRegisterCoalescing.cpp:
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::freeze):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::freezeMoves):
+
2015-11-16 Benjamin Poulain <bpoul...@apple.com>
[JSC] Make FTLOutput's load8() and load16() compatible with B3
Modified: trunk/Source/_javascript_Core/b3/air/AirIteratedRegisterCoalescing.cpp (192515 => 192516)
--- trunk/Source/_javascript_Core/b3/air/AirIteratedRegisterCoalescing.cpp 2015-11-17 19:05:29 UTC (rev 192515)
+++ trunk/Source/_javascript_Core/b3/air/AirIteratedRegisterCoalescing.cpp 2015-11-17 19:11:22 UTC (rev 192516)
@@ -547,6 +547,7 @@
void freeze()
{
Tmp victim = m_freezeWorklist.takeAny();
+ ASSERT_WITH_MESSAGE(getAlias(victim) == victim, "coalesce() should not leave aliased Tmp in the worklist.");
m_simplifyWorklist.append(victim);
freezeMoves(victim);
}
@@ -558,10 +559,11 @@
m_worklistMoves.takeMove(moveIndex);
const MoveOperands& moveOperands = m_coalescingCandidates[moveIndex];
- Tmp otherTmp = moveOperands.src != tmp ? moveOperands.src : moveOperands.dst;
+ Tmp originalOtherTmp = moveOperands.src != tmp ? moveOperands.src : moveOperands.dst;
+ Tmp otherTmp = getAlias(originalOtherTmp);
if (m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(otherTmp)] < m_numberOfRegisters && !isMoveRelated(otherTmp)) {
- m_freezeWorklist.remove(otherTmp);
- m_simplifyWorklist.append(otherTmp);
+ if (m_freezeWorklist.remove(otherTmp))
+ m_simplifyWorklist.append(otherTmp);
}
});
}
_______________________________________________
webkit-changes mailing list
webkit-changes@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-changes
