Title: [286045] trunk/Source/_javascript_Core
- Revision
- 286045
- Author
- [email protected]
- Date
- 2021-11-18 22:06:32 -0800 (Thu, 18 Nov 2021)
Log Message
[JSC/Air] Optimize enableMovesOnValueAndAdjacents in IRC
https://bugs.webkit.org/show_bug.cgi?id=228615
Reviewed by Saam Barati.
The Iterated Register Coalescing (IRC) register allocator spends a very significant fraction of its time in JS2 in enableMovesOnValueAndAdjacents (816ms out of 2.07s spent in register allocation for Wasm code in one run I looked at with Instruments).
The reason is that if this function is called on N nodes that are neighbors of each other, then enableMovesOnValue (which is kinda expensive as it iterates a SmallSet which is not always small) will be called N times on each of the N nodes. This can trivially be fixed by keeping track of which nodes need enableMovesOnValue called on them and only calling it on them once.
It is a bit tricky to measure the performance impact of this, as it heavily depends on whether some very large functions reach Air or not, so there is a lot of noise.
Here are the numbers out of 4 runs of JS2 (cli version) on an M1 MBP with --airForceIRCAllocator=1:
Baseline : total time in allocateRegistersByGraphColoring ranges from 2090ms to 3018ms, most time for a single function ranges from 631ms to 849ms
With this patch: total time in allocateRegistersByGraphColoring ranges from 1580ms to 2333ms, most time for a single function ranges from 337ms to 560ms
So despite the noise it seems quite clearly a win.
* b3/air/AirAllocateRegistersByGraphColoring.cpp:
Modified Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (286044 => 286045)
--- trunk/Source/_javascript_Core/ChangeLog 2021-11-19 04:18:12 UTC (rev 286044)
+++ trunk/Source/_javascript_Core/ChangeLog 2021-11-19 06:06:32 UTC (rev 286045)
@@ -1,3 +1,21 @@
+2021-11-18 Robin Morisset <[email protected]>
+
+ [JSC/Air] Optimize enableMovesOnValueAndAdjacents in IRC
+ https://bugs.webkit.org/show_bug.cgi?id=228615
+
+ Reviewed by Saam Barati.
+
+ The Iterated Register Coalescing (IRC) register allocator spends a very significant fraction of its time in JS2 in enableMovesOnValueAndAdjacents (816ms out of 2.07s spent in register allocation for Wasm code in one run I looked at with Instruments).
+ The reason is that if this function is called on N nodes that are neighbors of each other, then enableMovesOnValue (which is kinda expensive as it iterates a SmallSet which is not always small) will be called N times on each of the N nodes. This can trivially be fixed by keeping track of which nodes need enableMovesOnValue called on them and only calling it on them once.
+
+ It is a bit tricky to measure the performance impact of this, as it heavily depends on whether some very large functions reach Air or not, so there is a lot of noise.
+ Here are the numbers out of 4 runs of JS2 (cli version) on an M1 MBP with --airForceIRCAllocator=1:
+ Baseline : total time in allocateRegistersByGraphColoring ranges from 2090ms to 3018ms, most time for a single function ranges from 631ms to 849ms
+ With this patch: total time in allocateRegistersByGraphColoring ranges from 1580ms to 2333ms, most time for a single function ranges from 337ms to 560ms
+ So despite the noise it seems quite clearly a win.
+
+ * b3/air/AirAllocateRegistersByGraphColoring.cpp:
+
2021-11-18 Mark Lam <[email protected]>
SubSpace constructors should take a const HeapCellType& instead of a HeapCellType*.
Modified: trunk/Source/_javascript_Core/b3/air/AirAllocateRegistersByGraphColoring.cpp (286044 => 286045)
--- trunk/Source/_javascript_Core/b3/air/AirAllocateRegistersByGraphColoring.cpp 2021-11-19 04:18:12 UTC (rev 286044)
+++ trunk/Source/_javascript_Core/b3/air/AirAllocateRegistersByGraphColoring.cpp 2021-11-19 06:06:32 UTC (rev 286045)
@@ -912,6 +912,7 @@
public:
IRC(Code& code, const Vector<Reg>& regsInPriorityOrder, IndexType lastPrecoloredRegisterIndex, unsigned tmpArraySize, const BitVector& unspillableTmps, const UseCounts& useCounts)
: Base(code, regsInPriorityOrder, lastPrecoloredRegisterIndex, tmpArraySize, unspillableTmps, useCounts)
+ , m_movesToEnable(tmpArraySize)
{
}
@@ -941,6 +942,8 @@
if (!m_simplifyWorklist.isEmpty())
simplify();
+ else if (!m_movesToEnable.isEmpty())
+ enableMoves();
else if (!m_worklistMoves.isEmpty())
coalesce();
else if (!m_freezeWorklist.isEmpty())
@@ -1103,7 +1106,7 @@
unsigned oldDegree = m_degrees[tmpIndex]--;
if (oldDegree == registerCount()) {
- enableMovesOnValueAndAdjacents(tmpIndex);
+ lazyEnableMovesOnValueAndAdjacents(tmpIndex);
m_spillWorklist.quickClear(tmpIndex);
if (isMoveRelated(tmpIndex))
m_freezeWorklist.add(tmpIndex);
@@ -1146,6 +1149,14 @@
}
}
+ void lazyEnableMovesOnValueAndAdjacents(IndexType tmpIndex)
+ {
+ m_movesToEnable.quickSet(tmpIndex);
+ forEachAdjacent(tmpIndex, [this] (IndexType adjacentTmpIndex) {
+ m_movesToEnable.quickSet(adjacentTmpIndex);
+ });
+ }
+
void enableMovesOnValue(IndexType tmpIndex)
{
for (unsigned moveIndex : m_moveList[tmpIndex]) {
@@ -1154,13 +1165,11 @@
}
}
- void enableMovesOnValueAndAdjacents(IndexType tmpIndex)
+ void enableMoves()
{
- enableMovesOnValue(tmpIndex);
-
- forEachAdjacent(tmpIndex, [this] (IndexType adjacentTmpIndex) {
- enableMovesOnValue(adjacentTmpIndex);
- });
+ for (IndexType tmpIndex : m_movesToEnable)
+ enableMovesOnValue(tmpIndex);
+ m_movesToEnable.clearAll();
}
struct OrderedMoveSet {
@@ -1309,6 +1318,8 @@
OrderedMoveSet m_worklistMoves;
// Set of "move" not yet ready for coalescing.
BitVector m_activeMoves;
+ // Set of Tmps whose moves are now ready for possible coalescing.
+ BitVector m_movesToEnable;
};
// This perform all the tasks that are specific to certain register type.
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
