RESOLVED FIXED 276977
Use faster iterative algorithm to compute dominators for small CFGs 
https://bugs.webkit.org/show_bug.cgi?id=276977
Summary Use faster iterative algorithm to compute dominators for small CFGs
David Degazio
Reported 2024-07-23 17:09:05 PDT
Currently, we always use the simple Lengauer-Tarjan algorithm to compute dominators for control flow graphs in our compiler tiers. This gets us a pretty decent asymptotic complexity at O(n log n) (for n nodes) but is a fairly complex algorithm that has potentially high constant factors. Instead, we can consider the algorithm described in "A Simple, Fast Dominance Algorithm" (Cooper, Harvey, and Kennedy 2001), which is O(DE) for E edges and D dominance tree depth - worst-case quadratic, but likely better for most real-world examples. The paper suggests that their improved iterative algorithm is up to 2.5x faster than Lengauer-Tarjan, and remains faster up to graphs of tens of thousands of nodes. So, let's try using it for graphs under that threshold.
Attachments
Add attachment proposed patch, testcase, etc.
Radar WebKit Bug Importer
Comment 1 2024-07-23 17:09:20 PDT
<rdar://problem/132363948>
David Degazio
Comment 2 2024-07-24 10:03:27 PDT
Pull request: https://github.com/WebKit/WebKit/pull/31168
EWS
Comment 3 2024-07-25 12:45:27 PDT
Committed 281359@main (64f40e180663): <https://commits.webkit.org/281359@main> Reviewed commits have been landed. Closing PR #31168 and removing active labels.
Note You need to log in before you can comment on or make changes to this bug.