Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: 5e66de200545adb37f2a61b13893b22505143f8c
https://github.com/WebKit/WebKit/commit/5e66de200545adb37f2a61b13893b22505143f8c
Author: Yusuke Suzuki <[email protected]>
Date: 2026-06-26 (Fri, 26 Jun 2026)
Changed paths:
M Source/JavaScriptCore/b3/B3Procedure.cpp
M Source/WTF/wtf/Dominators.h
Log Message:
-----------
[JSC] Implement Semi-NCA for WTF::Dominators
https://bugs.webkit.org/show_bug.cgi?id=317531
rdar://180210650
Reviewed by Yijia Huang.
This patch implements Semi-NCA algorithm to compute Dominators
efficiently. Previously, we were using iterative dominance computation
algorithm for smaller graph (and for larger graph, using Lengauer-Tarjan
algorithm), but Semi-NCA is faster than iterative dominance computation
and in general it is near-linear complexity. This algorithm is used in
LLVM as well.
Empirically, we observed Semi-NCA is 1.4x - 2.0x faster than iterative
dominance and it is in general 1.4x faster than Lengauer-Tarjan. However
since it has still pathological case which causes O(N^2), we are falling
back to Lengauer-Tarjan for large graph as a safety measure.
* Source/JavaScriptCore/b3/B3Procedure.cpp:
* Source/WTF/wtf/Dominators.h:
(WTF::Dominators::Dominators):
(WTF::Dominators::SemiNCA::SemiNCA):
(WTF::Dominators::SemiNCA::compute):
(WTF::Dominators::SemiNCA::immediateDominator):
(WTF::Dominators::IterativeDominance::IterativeDominance): Deleted.
(WTF::Dominators::IterativeDominance::computeReversePostorder): Deleted.
(WTF::Dominators::IterativeDominance::intersect): Deleted.
(WTF::Dominators::IterativeDominance::compute): Deleted.
(WTF::Dominators::IterativeDominance::immediateDominator): Deleted.
Canonical link: https://commits.webkit.org/315938@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
