Wasmtime GitHub notifications bot (May 03 2022 at 06:08): Wasmtime GitHub notifications bot (May 03 2022 at 06:08):cfallin opened PR #4093 from isle-prio-bug to main:
This PR fixes a bug in the ISLE compiler related to rule priorities.
An important note first: the bug did not affect the correctness of the Cranelift backends, either in theory (because the rules should be correct applied in any order, even contrary to the stated priorities) or in practice (because the generated code actually does not change at all with the DSL compiler fix, only with a separate minimized bug example).
The issue was a simple swap of
minformax(see first commit). This is the minimal fix, I think, to get a correct priority-trie with the minimized bug example in the last commit.However, while debugging this, I started to convince myself that the complexity of merging multiple priority ranges using the sort of hybrid interval tree / string-matching trie data structure was unneeded. The original design was built with the assumption we might have a bunch of different priority levels, and would need the efficiency of merging where possible. But in practice we haven't used priorities this way: the vast majority of lowering rules exist at the default (priority 0), and just a few overrides are explicitly at prio 1, 2 or (rarely) 3.
So, it turns out to be a lot simpler to label trie edges with (prio, symbol) rather than (prio-range, symbol), and delete the whole mess of interval-splitting logic on insertion. It's easier (IMHO) to convince oneself that the resulting insertion algorithm is correct.
I was worried that this might impact the size of the generated Rust code or its runtime, but In fact, to my initial surprise (but it makes sense given the above "rarely used" factor), the generated code with this compiler fix is exactly the same. I rebuilt with
--features rebuild-isle,all-archbut... there were no diffs to commit! This is to me the simplest evidence that we didn't really need that complexity.The first commit here makes the minimal fix to the complex algorithm, to show the initial bug for completeness; the second commit deletes the whole mess (and the simpler ISLE compiler generates the same result); and the third commit adds the minimal reproducer that I got from the
Amodecode that exposed this bug.
Wasmtime GitHub notifications bot (May 03 2022 at 06:08):cfallin requested abrown for a review on PR #4093.
Wasmtime GitHub notifications bot (May 03 2022 at 06:08):cfallin requested fitzgen for a review on PR #4093.
Wasmtime GitHub notifications bot (May 03 2022 at 16:01):fitzgen submitted PR review.
Wasmtime GitHub notifications bot (May 03 2022 at 16:16):cfallin merged PR #4093.
Last updated: Nov 22 2024 at 16:03 UTC