Wasmtime GitHub notifications bot (Nov 13 2024 at 20:19): Wasmtime GitHub notifications bot (Nov 13 2024 at 20:19):amartosch opened PR #9603 from amartosch:domtree-semi-nca to bytecodealliance:main:
Compute dominator tree using semi-NCA algorithm, described in
Linear-Time Algorithms for Dominators and Related Problems. Loukas Georgiadis, Princeton University, November 2005.
The algorithm has quadratic worst-case complexity, but usually is much faster. The speedup is minor, but can be noticed on large functions, i.e. in this file.
Also add a differential fuzzing job for the new algorithm, with the old one as baseline. This addition is dubious, because it couldn't find anything overnight.
Wasmtime GitHub notifications bot (Nov 13 2024 at 20:19):amartosch requested alexcrichton for a review on PR #9603.
Wasmtime GitHub notifications bot (Nov 13 2024 at 20:19):amartosch requested wasmtime-fuzz-reviewers for a review on PR #9603.
Wasmtime GitHub notifications bot (Nov 13 2024 at 20:19):amartosch requested cfallin for a review on PR #9603.
Wasmtime GitHub notifications bot (Nov 13 2024 at 20:19):amartosch requested wasmtime-compiler-reviewers for a review on PR #9603.
Wasmtime GitHub notifications bot (Nov 13 2024 at 20:29):amartosch edited PR #9603:
Compute dominator tree using semi-NCA algorithm, described in
Linear-Time Algorithms for Dominators and Related Problems. Loukas Georgiadis, Princeton University, November 2005.
The algorithm has quadratic worst-case complexity, but usually is much faster. The speedup is minor, but can be noticed on large functions, i.e. in this file.
Also add a differential fuzzing job for the new algorithm, with the old one as baseline. This addition is dubious, because it couldn't find anything overnight.
Described in #9481.
Wasmtime GitHub notifications bot (Nov 13 2024 at 21:45):github-actions[bot] commented on PR #9603:
Subscribe to Label Action
cc @fitzgen
<details>
This issue or pull request has been labeled: "cranelift", "fuzzing"Thus the following users have been cc'd because of the following labels:
- fitzgen: fuzzing
To subscribe or unsubscribe from this label, edit the <code>.github/subscribe-to-label.json</code> configuration file.
Learn more.
</details>
Wasmtime GitHub notifications bot (Nov 14 2024 at 14:25):Amanieu submitted PR review.
Wasmtime GitHub notifications bot (Nov 14 2024 at 14:25):Amanieu created PR review comment:
This should be moved to a separate file to make the code cleaner. At the moment it looks messy with 2 separate algorithms in the same file.
Wasmtime GitHub notifications bot (Nov 14 2024 at 21:45):amartosch updated PR #9603.
Wasmtime GitHub notifications bot (Nov 14 2024 at 21:47):amartosch submitted PR review.
Wasmtime GitHub notifications bot (Nov 14 2024 at 21:47):amartosch created PR review comment:
Moved to a separate file
Wasmtime GitHub notifications bot (Nov 15 2024 at 00:08):cfallin submitted PR review:
Thanks very much for this implementation! Some thoughts mostly on comments below but nothing major; given that you've done a fuzzing-based verification of the new algorithm against the old, and seen some compile-time speedups, I'm otherwise confident in it.
Wasmtime GitHub notifications bot (Nov 15 2024 at 00:08):cfallin created PR review comment:
This would be a little cleaner if we pushed the virtual root at construction time (and updated clear to truncate to length 1 instead), I think?
Wasmtime GitHub notifications bot (Nov 15 2024 at 00:08):cfallin created PR review comment:
slight nitpick, but end comments with
.?
Wasmtime GitHub notifications bot (Nov 15 2024 at 00:08):cfallin created PR review comment:
Can we put doc-comments on the fields above?
label,semiandidomdon't tell me much about what's going on.
Wasmtime GitHub notifications bot (Nov 15 2024 at 00:08):cfallin created PR review comment:
Any reason we changed the doc-comment from
Methods for querying the dominator tree.toQuery methods(saying the same thing but missing detail, and no period)?
Wasmtime GitHub notifications bot (Nov 15 2024 at 00:08):cfallin created PR review comment:
The
0sentinel keeps occurring and I think it'd be clearer if we had a name for it -- could you defineconst NOT_VISITED: u32 = 0;or similar in this module?
Wasmtime GitHub notifications bot (Nov 15 2024 at 00:08):cfallin created PR review comment:
Rather than refer to another source file here (which may change or be removed in the future), can we say what the heuristics are, briefly?
Wasmtime GitHub notifications bot (Nov 15 2024 at 00:08):cfallin created PR review comment:
The "don't use..." comment seems out of place here: did you mean to give a reason why we don't use it here? Or is it a reminder (for what context?) or...?
Wasmtime GitHub notifications bot (Nov 15 2024 at 00:08):cfallin created PR review comment:
Is there any reason we have to use the old ("simple") implementation here? Or is the idea that when doing verification, we want to fall back to the more trusted algorithm? (Could we document this reasoning in a comment if so?)
Actually, thinking aloud a bit: I think I'm OK with moving everything over to the new algorithm, including the verifier; it should be enough to have the fuzz-target that checks the algorithm itself against the old algorithm. (If we don't trust that, then we shouldn't use the new algorithm anywhere!)
Wasmtime GitHub notifications bot (Nov 15 2024 at 00:08):cfallin created PR review comment:
I'd prefer full sentences in doc-comments here (or at least complete thoughts) -- maybe something like "Preorder traversal number, or 0 for unreachable blocks." ?
Wasmtime GitHub notifications bot (Nov 15 2024 at 00:08):cfallin created PR review comment:
This name ("eval-compress") doesn't mean anything to the reader -- could you give a more descriptive doc-comment?
Wasmtime GitHub notifications bot (Nov 15 2024 at 22:28):amartosch updated PR #9603.
Wasmtime GitHub notifications bot (Nov 15 2024 at 22:29):amartosch submitted PR review.
Wasmtime GitHub notifications bot (Nov 15 2024 at 22:29):amartosch created PR review comment:
Added.
Wasmtime GitHub notifications bot (Nov 15 2024 at 22:30):amartosch submitted PR review.
Wasmtime GitHub notifications bot (Nov 15 2024 at 22:30):amartosch created PR review comment:
Clarified.
Wasmtime GitHub notifications bot (Nov 15 2024 at 22:30):amartosch submitted PR review.
Wasmtime GitHub notifications bot (Nov 15 2024 at 22:30):amartosch created PR review comment:
Fixed.
Wasmtime GitHub notifications bot (Nov 15 2024 at 22:30):amartosch submitted PR review.
Wasmtime GitHub notifications bot (Nov 15 2024 at 22:30):amartosch created PR review comment:
Yes, this is a mistake. Fixed.
Wasmtime GitHub notifications bot (Nov 15 2024 at 22:30):amartosch submitted PR review.
Wasmtime GitHub notifications bot (Nov 15 2024 at 22:30):amartosch created PR review comment:
Added.
Wasmtime GitHub notifications bot (Nov 15 2024 at 22:34):amartosch updated PR #9603.
Wasmtime GitHub notifications bot (Nov 15 2024 at 22:38):amartosch submitted PR review.
Wasmtime GitHub notifications bot (Nov 15 2024 at 22:38):amartosch created PR review comment:
Yes, the idea was to compare this tree to the more trusted algorithm. Changed to the new.
Last updated: Dec 23 2024 at 12:05 UTC