Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: f74305d8e5507b0e3da7e4dfc9b3dd3476cb8c6b
https://github.com/WebKit/WebKit/commit/f74305d8e5507b0e3da7e4dfc9b3dd3476cb8c6b
Author: Dan Hecht <[email protected]>
Date: 2025-02-19 (Wed, 19 Feb 2025)
Changed paths:
M Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
M Source/JavaScriptCore/Sources.txt
M Source/JavaScriptCore/b3/air/AirAllocateRegistersByGraphColoring.cpp
A Source/JavaScriptCore/b3/air/AirAllocateRegistersByGreedy.cpp
A Source/JavaScriptCore/b3/air/AirAllocateRegistersByGreedy.h
M Source/JavaScriptCore/b3/air/AirCode.h
M Source/JavaScriptCore/b3/air/AirGenerate.cpp
M Source/JavaScriptCore/b3/air/AirTmpWidth.cpp
M Source/JavaScriptCore/b3/air/AirTmpWidth.h
M Source/JavaScriptCore/runtime/OptionsList.h
Log Message:
-----------
[JSC] Introduce the "Greedy" Register Allocator for B3 Air
https://bugs.webkit.org/show_bug.cgi?id=287663
rdar://144792183
Reviewed by Yusuke Suzuki.
Currently disabled but functional.
See the comment at the top of AirAllocateRegistersByGraphColoring.cpp for
a high level view of the design.
Currently B3 Air uses four different register allocator variants:
1. GenerateAndAllocateRegisters allocator: used when optLevel == 0
2. Linear scan: used when optLevel == 1 or there are more tmps than
Options::maximumTmpsForGraphColoring(), and SIMD is not used by the
procedure.
3. IRC graph coloring: used by OMG on ARM and x86, and JS on x86
4. Briggs graph coloring: used by JS on ARM
It'd be nice to have a single register allocator for FTL/OMG that works well
in all configurations. Additionally, the graph coloring allocator can be time
and memory consuming when there are lots of tmps and interference.
This register allocator is inspired by LLVM's Greedy register allocator and
may work across these configurations with less overhead.
The eventual goal is to enable this allocator by default and phase out and
remove the other register allocators.
* Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj:
* Source/JavaScriptCore/Sources.txt:
* Source/JavaScriptCore/b3/air/AirAllocateRegistersByGraphColoring.cpp:
(JSC::B3::Air::allocateRegistersByGraphColoring):
* Source/JavaScriptCore/b3/air/AirAllocateRegistersByGreedy.cpp: Added.
(JSC::B3::Air::Greedy::verbose):
(JSC::B3::Air::Greedy::LiveRange::validate):
(JSC::B3::Air::Greedy::LiveRange::prepend):
(JSC::B3::Air::Greedy::LiveRange::append):
(JSC::B3::Air::Greedy::LiveRange::crossBasicBlockBoundary):
(JSC::B3::Air::Greedy::LiveRange::isLocal const):
(JSC::B3::Air::Greedy::LiveRange::intervals const):
(JSC::B3::Air::Greedy::LiveRange::size):
(JSC::B3::Air::Greedy::LiveRange::overlaps):
(JSC::B3::Air::Greedy::LiveRange::merge):
(JSC::B3::Air::Greedy::LiveRange::subtract):
(JSC::B3::Air::Greedy::LiveRange::dump const):
(JSC::B3::Air::Greedy::TmpPriority::pack_priority):
(JSC::B3::Air::Greedy::TmpPriority::TmpPriority):
(JSC::B3::Air::Greedy::TmpPriority::tmp):
(JSC::B3::Air::Greedy::TmpPriority::stage const):
(JSC::B3::Air::Greedy::TmpPriority::dump const):
(JSC::B3::Air::Greedy::TmpPriority::isHigherPriority):
(JSC::B3::Air::Greedy::RegisterRange::AllocatedInterval::operator< const):
(JSC::B3::Air::Greedy::RegisterRange::AllocatedInterval::dump const):
(JSC::B3::Air::Greedy::RegisterRange::add):
(JSC::B3::Air::Greedy::RegisterRange::evict):
(JSC::B3::Air::Greedy::RegisterRange::hasConflict):
(JSC::B3::Air::Greedy::RegisterRange::forEachConflict):
(JSC::B3::Air::Greedy::RegisterRange::dump const):
(JSC::B3::Air::Greedy::RegisterRange::findFirstIntervalEndingAfter):
(JSC::B3::Air::Greedy::TmpData::CoalescableWith::dump const):
(JSC::B3::Air::Greedy::TmpData::dump const):
(JSC::B3::Air::Greedy::TmpData::isGroup):
(JSC::B3::Air::Greedy::TmpData::validate):
(JSC::B3::Air::Greedy::SplitMetadata::dump const):
(JSC::B3::Air::Greedy::GreedyAllocator::GreedyAllocator):
(JSC::B3::Air::Greedy::GreedyAllocator::run):
(JSC::B3::Air::Greedy::GreedyAllocator::buildRegisterSets):
(JSC::B3::Air::Greedy::GreedyAllocator::buildIndices):
(JSC::B3::Air::Greedy::GreedyAllocator::findBlockContainingPoint):
(JSC::B3::Air::Greedy::GreedyAllocator::positionOfHead):
(JSC::B3::Air::Greedy::GreedyAllocator::positionOfTail):
(JSC::B3::Air::Greedy::GreedyAllocator::instIndex):
(JSC::B3::Air::Greedy::GreedyAllocator::positionOfEarly):
(JSC::B3::Air::Greedy::GreedyAllocator::earlyInterval):
(JSC::B3::Air::Greedy::GreedyAllocator::lateInterval):
(JSC::B3::Air::Greedy::GreedyAllocator::earlyAndLateInterval):
(JSC::B3::Air::Greedy::GreedyAllocator::interval):
(JSC::B3::Air::Greedy::GreedyAllocator::intervalForSpill):
(JSC::B3::Air::Greedy::GreedyAllocator::groupForTmp):
(JSC::B3::Air::Greedy::GreedyAllocator::assignedReg):
(JSC::B3::Air::Greedy::GreedyAllocator::spillSlot):
(JSC::B3::Air::Greedy::GreedyAllocator::adjustedBlockFrequency):
(JSC::B3::Air::Greedy::GreedyAllocator::validateAssignments):
(JSC::B3::Air::Greedy::GreedyAllocator::buildLiveRanges):
(JSC::B3::Air::Greedy::GreedyAllocator::forEachTmpInGroup):
(JSC::B3::Air::Greedy::GreedyAllocator::finalizeGroups):
(JSC::B3::Air::Greedy::GreedyAllocator::initSpillCosts):
(JSC::B3::Air::Greedy::GreedyAllocator::newTmp):
(JSC::B3::Air::Greedy::GreedyAllocator::addSpillTmpWithInterval):
(JSC::B3::Air::Greedy::GreedyAllocator::dumpRegRanges):
(JSC::B3::Air::Greedy::GreedyAllocator::setStageAndEnqueue):
(JSC::B3::Air::Greedy::GreedyAllocator::allocateRegisters):
(JSC::B3::Air::Greedy::GreedyAllocator::tryAllocate):
(JSC::B3::Air::Greedy::GreedyAllocator::tryEvict):
(JSC::B3::Air::Greedy::GreedyAllocator::assign):
(JSC::B3::Air::Greedy::GreedyAllocator::evict):
(JSC::B3::Air::Greedy::GreedyAllocator::trySplit):
(JSC::B3::Air::Greedy::GreedyAllocator::trySplitGroup):
(JSC::B3::Air::Greedy::GreedyAllocator::trySplitAroundClobbers):
(JSC::B3::Air::Greedy::GreedyAllocator::stackSlotMinimumWidth):
(JSC::B3::Air::Greedy::GreedyAllocator::spill):
(JSC::B3::Air::Greedy::GreedyAllocator::queueContainsOnlySpills):
(JSC::B3::Air::Greedy::GreedyAllocator::moveOpcode):
(JSC::B3::Air::Greedy::GreedyAllocator::emitSpillCodeAndEnqueueNewTmps):
(JSC::B3::Air::Greedy::GreedyAllocator::insertFixupCode):
(JSC::B3::Air::Greedy::GreedyAllocator::mayBeCoalescable):
(JSC::B3::Air::Greedy::GreedyAllocator::assignRegisters):
(JSC::B3::Air::allocateRegistersByGreedy):
* Source/JavaScriptCore/b3/air/AirAllocateRegistersByGreedy.h: Added.
* Source/JavaScriptCore/b3/air/AirCode.h:
(JSC::B3::Air::Code::forEachTmp):
* Source/JavaScriptCore/b3/air/AirGenerate.cpp:
(JSC::B3::Air::prepareForGeneration):
* Source/JavaScriptCore/b3/air/AirTmpWidth.cpp:
(JSC::B3::Air::TmpWidth::ensureSize):
(JSC::B3::Air::TmpWidth::setWidths):
* Source/JavaScriptCore/b3/air/AirTmpWidth.h:
* Source/JavaScriptCore/runtime/OptionsList.h:
Canonical link: https://commits.webkit.org/290639@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
