Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: c03651a49eb908c397709c0fae4596049cbe8bca
https://github.com/WebKit/WebKit/commit/c03651a49eb908c397709c0fae4596049cbe8bca
Author: Dan Hecht <[email protected]>
Date: 2026-03-20 (Fri, 20 Mar 2026)
Changed paths:
M Source/JavaScriptCore/b3/air/AirAllocateStackByGraphColoring.cpp
M Source/JavaScriptCore/b3/air/AirStackAllocation.cpp
M Source/JavaScriptCore/b3/air/AirStackAllocation.h
M Source/JavaScriptCore/b3/air/testair.cpp
Log Message:
-----------
[JSC] Improve worst case performance of Air stack allocation
https://bugs.webkit.org/show_bug.cgi?id=310376
rdar://173019617
Reviewed by Yusuke Suzuki.
Eventually we may want to replace the interference graph based stack
allocator with one based on live-range intervals (similar to the
greedy register allocator).
But in the meantime, optimize the stack slot assignment algorithm from
O(n²) to O(n log n). The old code tried each candidate position and
re-scanned all interfering slots to verify no overlap. The new code sorts
the interference list by offset and does a single sweep, pushing the
candidate down past any overlapping slot.
This also makes the assignment truly first-fit (closest to FP), whereas
the old code iterated interference lists in arbitrary order and took the
first valid position found.
Improves testair performance from ~5 minutes to a few seconds because
a test case (testZDefOfSpillSlotWithOffsetNeedingToBeMaterializedInARegister)
had a lot of interfering tmps.
Test: Source/JavaScriptCore/b3/air/testair.cpp
* Source/JavaScriptCore/b3/air/testair.cpp:
* Source/JavaScriptCore/b3/air/AirAllocateStackByGraphColoring.cpp:
* Source/JavaScriptCore/b3/air/AirStackAllocation.cpp:
(JSC::B3::Air::assign):
(JSC::B3::Air::attemptAssignment): Deleted.
* Source/JavaScriptCore/b3/air/AirStackAllocation.h:
Canonical link: https://commits.webkit.org/309668@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
