Wasmtime GitHub notifications bot (Apr 29 2024 at 17:59): Wasmtime GitHub notifications bot (Apr 29 2024 at 17:59):jameysharp requested abrown for a review on PR #8503.
Wasmtime GitHub notifications bot (Apr 29 2024 at 17:59):jameysharp requested wasmtime-compiler-reviewers for a review on PR #8503.
Wasmtime GitHub notifications bot (Apr 29 2024 at 17:59):jameysharp opened PR #8503 from jameysharp:vcode-split-preds to bytecodealliance:main:
This establishes the property that the VCode's various lists of ranges each fully cover the index range of another list. Previously, the block_succ_range list covered the first half of block_succs_preds, and the block_pred_range list covered the second half.
While I was in the area, I replaced the O(n log n) sort in compute_preds_from_succs with a linear-time counting sort, which uses less temporary storage and directly computes the ranges we want as a byproduct.
Wasmtime GitHub notifications bot (Apr 29 2024 at 18:21):cfallin submitted PR review:
This is super-cool! IMHO this is the "Book" algorithm (in the Paul Erdos sense) for finding preds from succs. Clean and direct.
Out of curiosity have you measured the compile-time impact of this? I wonder if it'll show up in code with complex CFGs... we should take it in any case though.
Wasmtime GitHub notifications bot (Apr 29 2024 at 20:10):jameysharp merged PR #8503.
Wasmtime GitHub notifications bot (Apr 29 2024 at 20:10):jameysharp commented on PR #8503:
I hadn't measured, but according to Hyperfine, compiling the Spidermonkey benchmark from Sightglass is unchanged with this commit. I think that's unsurprising; the largest function has 2650 blocks and 6777 edges (before legalization and critical-edge splitting), and that's just not that many. But I'm still absurdly pleased with finding a situation where a linear-time sort is actually the best choice.
Last updated: Dec 23 2024 at 12:05 UTC