Skip to content

Commit 5e03b0c

Browse files
committed
[JSC] Make Air stack slot liveness sparse in instructions
https://bugs.webkit.org/show_bug.cgi?id=323526 rdar://186767924 Reviewed by Yijia Huang. Normally Spill stack use is much limited even in very large program compared to pure register / normal-stack / memory-location only instructions. Even in very large function in sqlite3-wasm is having ~7% of instructions using spill stack. However AirAllocateStackByGraphColoring is walking over all Air instructions repeatedly while most of instructions are meaningless since they do not have spills. In this patch, we leverage this sparse characteristics to accelerate performance of this phase. We first walk all Air instructions to collect actions, kill-candidates, move-coalescable-sites in one forward pass. And we run liveness analysis over this collected actions instead. This means that overall graph size gets dramatically smaller (~10%) compared to repeatedly scanning entire Air graph. Then, when building inference graph, we step over spill action boundaries instead of instruction-index step by step, this skips many non-interesting instructions automatically and offers quick graph computation. The analysis and achievement are exactly the same. And this is roughly cutting 50% of time in this phase. * Source/JavaScriptCore/b3/B3VariableLiveness.h: (JSC::B3::VariableLivenessAdapter::forEachActionGroupDescending): (JSC::B3::VariableLivenessAdapter::forEachUseInGroup): (JSC::B3::VariableLivenessAdapter::forEachDefInGroup): (JSC::B3::VariableLivenessAdapter::forEachUseAtTail): * Source/JavaScriptCore/b3/air/AirAllocateStackByGraphColoring.cpp: (JSC::B3::Air::allocateStackByGraphColoring): * Source/JavaScriptCore/b3/air/AirLiveness.h: (JSC::B3::Air::Liveness::Liveness): * Source/JavaScriptCore/b3/air/AirLivenessAdapter.h: (JSC::B3::Air::LivenessAdapter::forEachActionGroupDescending): (JSC::B3::Air::LivenessAdapter::forEachUseInGroup): (JSC::B3::Air::LivenessAdapter::forEachDefInGroup): (JSC::B3::Air::LivenessAdapter::forEachUseAtTail): (JSC::B3::Air::StackSlotLivenessAdapter::StackSlotLivenessAdapter): Deleted. (JSC::B3::Air::StackSlotLivenessAdapter::numIndices): Deleted. (JSC::B3::Air::StackSlotLivenessAdapter::acceptsBank): Deleted. (JSC::B3::Air::StackSlotLivenessAdapter::acceptsRole): Deleted. (JSC::B3::Air::StackSlotLivenessAdapter::valueToIndex): Deleted. (JSC::B3::Air::StackSlotLivenessAdapter::indexToValue): Deleted. * Source/JavaScriptCore/b3/air/AirStackAllocatorStats.h: (JSC::B3::Air::AirStackAllocatorStats::AirStackAllocatorStats): * Source/WTF/wtf/Liveness.h: (WTF::Liveness::Workset::forEachSetBit const): (WTF::Liveness::Workset::initialize): (WTF::Liveness::Workset::clear): (WTF::Liveness::makeWorkset): (WTF::Liveness::copyLiveAtTailInto): (WTF::Liveness::LocalCalc::LocalCalc): (WTF::Liveness::computeDense): (WTF::Liveness::computeSparse): (WTF::Liveness::forEachInDense): Canonical link: https://commits.webkit.org/320943@main
1 parent 8ae0649 commit 5e03b0c

6 files changed

Lines changed: 567 additions & 206 deletions

File tree

‎Source/JavaScriptCore/b3/B3VariableLiveness.h‎

Lines changed: 33 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -38,7 +38,7 @@
3838
namespace JSC { namespace B3 {
3939

4040
struct VariableLivenessAdapter {
41-
static constexpr const char* name = "VariableLiveness";
41+
static constexpr ASCIILiteral name = "VariableLiveness"_s;
4242
typedef B3::CFG CFG;
4343
typedef Variable* Thing;
4444

@@ -63,6 +63,38 @@ struct VariableLivenessAdapter {
6363
{
6464
return block->size();
6565
}
66+
67+
// Any value boundary can be a Get or a Set, so all of them are visited and a group is just the
68+
// boundary itself.
69+
struct ActionGroup {
70+
BasicBlock* block { nullptr };
71+
unsigned boundary { 0 };
72+
};
73+
74+
template<typename Func>
75+
void forEachActionGroupDescending(BasicBlock* block, const Func& func)
76+
{
77+
for (unsigned boundary = block->size() + 1; boundary--;)
78+
func(boundary, ActionGroup { block, boundary });
79+
}
80+
81+
template<typename Func>
82+
void forEachUseInGroup(ActionGroup group, const Func& func)
83+
{
84+
forEachUse(group.block, group.boundary, func);
85+
}
86+
87+
template<typename Func>
88+
void forEachDefInGroup(ActionGroup group, const Func& func)
89+
{
90+
forEachDef(group.block, group.boundary, func);
91+
}
92+
93+
template<typename Func>
94+
void forEachUseAtTail(BasicBlock* block, const Func& func)
95+
{
96+
forEachUse(block, block->size(), func);
97+
}
6698

6799
template<typename Func>
68100
void forEachUse(BasicBlock* block, unsigned valueBoundaryIndex, const Func& func)

0 commit comments

Comments
 (0)