Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: 53209b2d1762797af5e7192311ee825092720436
https://github.com/WebKit/WebKit/commit/53209b2d1762797af5e7192311ee825092720436
Author: Yusuke Suzuki <[email protected]>
Date: 2026-06-15 (Mon, 15 Jun 2026)
Changed paths:
M Source/WTF/WTF.xcodeproj/project.pbxproj
M Source/WTF/wtf/BitVector.h
M Source/WTF/wtf/CMakeLists.txt
M Source/WTF/wtf/Liveness.h
A Source/WTF/wtf/SparseBitVector.h
M Tools/TestWebKitAPI/CMakeLists.txt
M Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj
A Tools/TestWebKitAPI/Tests/WTF/SparseBitVector.cpp
Log Message:
-----------
[JSC] Make Liveness analysis faster
https://bugs.webkit.org/show_bug.cgi?id=317062
rdar://179544464
Reviewed by Dan Hecht.
WTF::Liveness is slow in two cases,
1. Simply even in small graph, it is slow due to repeated sorting
2. In large graph, this is further slower
We should use BitVector, traditional textbook approach to liveness analysis.
But if graph is large (e.g. Air graph), it takes significant amount of
memory because these BitVector becomes sparse due to # of Air values.
Thus this patch adds SparseBitVector. This is managing Vector of BitSet,
maintaining sparse version of BitVector efficiently. It also has the
last accessed m_hint cache as similar to LLVM's SparseBitVector.
Liveness analysis code switches the underlying implementation based on
the graph size. If it is small, then we use (conceptually) BitVector,
otherwise using SparseBitVector.
To extremely optimize, we use Vector and doing word-level operations
directly instead of using BitVector.
Test: Tools/TestWebKitAPI/Tests/WTF/SparseBitVector.cpp
* Source/WTF/WTF.xcodeproj/project.pbxproj:
* Source/WTF/wtf/BitVector.h:
* Source/WTF/wtf/CMakeLists.txt:
* Source/WTF/wtf/Liveness.h:
(WTF::Liveness::compute):
(WTF::Liveness::computeDense):
(WTF::Liveness::computeSparse):
* Source/WTF/wtf/SparseBitVector.h: Added.
(WTF::SparseBitVector::ensureSize):
(WTF::SparseBitVector::clear):
(WTF::SparseBitVector::isEmpty const):
(WTF::SparseBitVector::set):
(WTF::SparseBitVector::reset):
(WTF::SparseBitVector::contains const):
(WTF::SparseBitVector::forEachSetBit const):
(WTF::SparseBitVector::allElementsNonEmpty const):
(WTF::SparseBitVector::find const):
(WTF::SparseBitVector::findOrInsert):
(WTF::SparseBitVector::lowerBound const):
* Tools/TestWebKitAPI/CMakeLists.txt:
* Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
* Tools/TestWebKitAPI/Tests/WTF/SparseBitVector.cpp: Added.
(TestWebKitAPI::collect):
(TestWebKitAPI::TEST(WTF_SparseBitVector, Empty)):
(TestWebKitAPI::TEST(WTF_SparseBitVector, SetAndContains)):
(TestWebKitAPI::TEST(WTF_SparseBitVector, ForEachSetBitIsAscending)):
(TestWebKitAPI::TEST(WTF_SparseBitVector, Clear)):
(TestWebKitAPI::TEST(WTF_SparseBitVector, ElementBoundaries)):
(TestWebKitAPI::TEST(WTF_SparseBitVector, RandomizedAgainstReference)):
(TestWebKitAPI::TEST(WTF_SparseBitVector, SetAndReset)):
(TestWebKitAPI::TEST(WTF_SparseBitVector, RandomizedAddRemoveAgainstReference)):
Canonical link: https://commits.webkit.org/315242@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
