Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: f8b9ab1a0bfafddda9d8d541e6b33047de427811
https://github.com/WebKit/WebKit/commit/f8b9ab1a0bfafddda9d8d541e6b33047de427811
Author: Dan Hecht <[email protected]>
Date: 2026-03-17 (Tue, 17 Mar 2026)
Changed paths:
M Source/JavaScriptCore/b3/air/AirAllocateRegistersByGreedy.cpp
M Source/JavaScriptCore/b3/air/AirRegisterAllocatorStats.h
Log Message:
-----------
[JSC] Rewrite of the greedy register allocator's coalescing strategy
https://bugs.webkit.org/show_bug.cgi?id=309992
rdar://172621751
Reviewed by Yusuke Suzuki and Yijia Huang.
The existing strategy is inefficient when the number of coalescable
tmps is large. That's not normally the case, but it can be true with
some wasm code since it's generally generated code.
Use the IntervalSet data-structure to accumulate each group's aggregate
live ranges to perform group conflict checking similarly to how the
core register allocation works. However, in the case of coalescing,
live ranges are allowed to overlap when it is known that the live
tmps hold the same value. The new LivenessMap accommodates this.
Additionally, remove the logic that splits coalesced groups back into their
subgroups / leafs as that is also inefficient when there are a lot
of coalescable tmps. Instead, allow the coalesced group's representative
tmp to be split just like any other tmp. That way, live range splitting
can be done strategically and uniformly regardless of whether the tmp was
created by coalescing or pre-existing. The group splitting logic
predates the other split logic and is generally no longer needed. This
also sets things up for additional strategic splitting techniques to be
added in the future.
Decrease the const def spill cost as these should generally be the first
tmps to spill and gives groups a better chance at allocation.
Tested by existing JSC stress tests.
* Source/JavaScriptCore/b3/air/AirAllocateRegistersByGreedy.cpp:
(JSC::B3::Air::Greedy::TmpData::dump const):
(JSC::B3::Air::Greedy::TmpData::validate):
(JSC::B3::Air::Greedy::GreedyAllocator::run):
(JSC::B3::Air::Greedy::GreedyAllocator::assignedReg):
(JSC::B3::Air::Greedy::GreedyAllocator::spillSlot):
(JSC::B3::Air::Greedy::GreedyAllocator::validateAssignments):
(JSC::B3::Air::Greedy::GreedyAllocator::isInCoalescables):
(JSC::B3::Air::Greedy::GreedyAllocator::LivenessMap::LivenessMap):
(JSC::B3::Air::Greedy::GreedyAllocator::LivenessMap::add):
(JSC::B3::Air::Greedy::GreedyAllocator::LivenessMap::merge):
(JSC::B3::Air::Greedy::GreedyAllocator::LivenessMap::forEachOverlap const):
(JSC::B3::Air::Greedy::GreedyAllocator::LivenessMap::forEachPairwiseOverlap):
(JSC::B3::Air::Greedy::GreedyAllocator::LivenessMap::buildLiveRange const):
(JSC::B3::Air::Greedy::GreedyAllocator::LivenessMap::EncodedTmpList::dump
const):
(JSC::B3::Air::Greedy::GreedyAllocator::LivenessMap::isSingleton):
(JSC::B3::Air::Greedy::GreedyAllocator::LivenessMap::encodeSingleton):
(JSC::B3::Air::Greedy::GreedyAllocator::LivenessMap::decodeSingleton):
(JSC::B3::Air::Greedy::GreedyAllocator::LivenessMap::encodeIndex):
(JSC::B3::Air::Greedy::GreedyAllocator::LivenessMap::decodeIndex):
(JSC::B3::Air::Greedy::GreedyAllocator::LivenessMap::decodeTmpList const):
(JSC::B3::Air::Greedy::GreedyAllocator::LivenessMap::insertInterval):
(JSC::B3::Air::Greedy::GreedyAllocator::LivenessMap::eraseInterval):
(JSC::B3::Air::Greedy::GreedyAllocator::LivenessMap::addInterval):
(JSC::B3::Air::Greedy::GreedyAllocator::LivenessMap::concatLists):
(JSC::B3::Air::Greedy::GreedyAllocator::AffinityGroup::AffinityGroup):
(JSC::B3::Air::Greedy::GreedyAllocator::AffinityGroup::addMember):
(JSC::B3::Air::Greedy::GreedyAllocator::AffinityGroup::merge):
(JSC::B3::Air::Greedy::GreedyAllocator::AffinityGroup::members const):
(JSC::B3::Air::Greedy::GreedyAllocator::AffinityGroup::size const):
(JSC::B3::Air::Greedy::GreedyAllocator::AffinityGroup::isEmpty const):
(JSC::B3::Air::Greedy::GreedyAllocator::AffinityGroup::buildLiveRange const):
(JSC::B3::Air::Greedy::GreedyAllocator::AffinityGroup::forEachOverlap const):
(JSC::B3::Air::Greedy::GreedyAllocator::AffinityGroup::forEachPairwiseOverlap):
(JSC::B3::Air::Greedy::GreedyAllocator::AffinityGroup::dump const):
(JSC::B3::Air::Greedy::GreedyAllocator::coalesceSingletons):
(JSC::B3::Air::Greedy::GreedyAllocator::tryCoalesceSingletonWithGroup):
(JSC::B3::Air::Greedy::GreedyAllocator::tryCoalesceGroups):
(JSC::B3::Air::Greedy::GreedyAllocator::coalesceTmps):
(JSC::B3::Air::Greedy::GreedyAllocator::buildCoalescingGroups):
(JSC::B3::Air::Greedy::GreedyAllocator::validateCoalescing):
(JSC::B3::Air::Greedy::GreedyAllocator::createGroupRepresentatives):
(JSC::B3::Air::Greedy::GreedyAllocator::rewriteCoalescedTmps):
(JSC::B3::Air::Greedy::GreedyAllocator::initSpillCosts):
(JSC::B3::Air::Greedy::GreedyAllocator::setStageAndEnqueue):
(JSC::B3::Air::Greedy::GreedyAllocator::allocateRegisters):
(JSC::B3::Air::Greedy::GreedyAllocator::doStageTryAllocate):
(JSC::B3::Air::Greedy::GreedyAllocator::tryAllocate):
(JSC::B3::Air::Greedy::GreedyAllocator::assignImpl):
(JSC::B3::Air::Greedy::GreedyAllocator::evict):
(JSC::B3::Air::Greedy::GreedyAllocator::trySplit):
(JSC::B3::Air::Greedy::GreedyAllocator::trySplitIntraBlock):
(JSC::B3::Air::Greedy::GreedyAllocator::spill):
(JSC::B3::Air::Greedy::GreedyAllocator::emitSpillCodeAndEnqueueNewTmps):
(JSC::B3::Air::Greedy::TmpData::isGroup): Deleted.
(JSC::B3::Air::Greedy::GreedyAllocator::groupForSpill): Deleted.
(JSC::B3::Air::Greedy::GreedyAllocator::groupForReg): Deleted.
(JSC::B3::Air::Greedy::GreedyAllocator::forEachTmpInGroup): Deleted.
(JSC::B3::Air::Greedy::GreedyAllocator::finalizeGroups): Deleted.
(JSC::B3::Air::Greedy::GreedyAllocator::trySplitGroup): Deleted.
(JSC::B3::Air::Greedy::GreedyAllocator::ensureGroupSpillSlot): Deleted.
* Source/JavaScriptCore/b3/air/AirRegisterAllocatorStats.h:
Canonical link: https://commits.webkit.org/309407@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
