Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: cc124cd0885255b7c5b924b588c080ac36bf567d
https://github.com/WebKit/WebKit/commit/cc124cd0885255b7c5b924b588c080ac36bf567d
Author: Dan Hecht <dan.he...@apple.com>
Date: 2025-08-27 (Wed, 27 Aug 2025)
Changed paths:
M Source/JavaScriptCore/b3/air/AirAllocateRegistersByGreedy.cpp
M Source/WTF/WTF.xcodeproj/project.pbxproj
M Source/WTF/wtf/CMakeLists.txt
A Source/WTF/wtf/IntervalSet.h
M Tools/TestWebKitAPI/CMakeLists.txt
M Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj
A Tools/TestWebKitAPI/Tests/WTF/IntervalSet.cpp
Log Message:
-----------
[JSC] GreedyRegAlloc: use a B+ tree to track RegisterRanges
https://bugs.webkit.org/show_bug.cgi?id=297937
rdar://159234031
Reviewed by Yusuke Suzuki.
The most frequent operation on a RegisterRange is to query
whether a LiveRange overlaps any current assignment. Currently,
RegisterRange is built on top of an std::set which is not optimal
for this since it requires many pointer indirections often across
various cache lines to answer this question.
So, introduce IntervalSet which is an B+ tree specialized for Interval
queries and is cache-line aware. The node order (aka branch factor) is
determined by the desired size of a node, specified in terms of cache
lines. By having a larger node order (inner order is 12 and leaf
order is 16), tree height is greatly reduced, leading to much less
pointer indirection when querying for interval overlaps. Additionally,
neighboring intervals have better cache locality helping to speed up the
iteration of conflicts when deciding whether to evict.
The result is that for large functions with many Tmps, the
GreedyRegAlloc::allocateRegister sub-phase runs almost 2x faster.
This sub-phase tends to be the most expensive B3/Air phase for
these large functions.
Ultimately, this boils down to searching a segmented array, so other
segmented array data-structures could probably work well. B+ tree seems
to be a reasonable choice since it still supports relatively fast
insert and erase.
Also note that LLVM uses a B+ tree at the core of its greedy register
allocator, though various details are probably different.
Canonical link: https://commits.webkit.org/299207@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
_______________________________________________
webkit-changes mailing list
webkit-changes@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-changes
