Bug 276977
| Summary: | Use faster iterative algorithm to compute dominators for small CFGs | ||
|---|---|---|---|
| Product: | WebKit | Reporter: | David Degazio <d_degazio> |
| Component: | JavaScriptCore | Assignee: | David Degazio <d_degazio> |
| Status: | RESOLVED FIXED | ||
| Severity: | Normal | CC: | webkit-bug-importer |
| Priority: | P2 | Keywords: | InRadar |
| Version: | WebKit Nightly Build | ||
| Hardware: | Unspecified | ||
| OS: | Unspecified | ||
David Degazio
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
<rdar://problem/132363948>
David Degazio
Pull request: https://github.com/WebKit/WebKit/pull/31168
EWS
Committed 281359@main (64f40e180663): <https://commits.webkit.org/281359@main>
Reviewed commits have been landed. Closing PR #31168 and removing active labels.