cfallin opened PR #4953 from mid-end
to main
:
This PR is a draft of an updated version of the egraph patch (and thus supersedes #4249) with the two parts already merged (multi-etors and the egraph crate proper) removed; it includes the Cranelift integration, the egraph build (CLIF to egraph) and elaboration (egraph to CLIF) algorithms, and rule application engine, as well as a set of rewrite rules that replaces the existing mid-end optimizations.
It still needs a bit more productionizing:
- removal of recursion in elaboration;
- removal of recursion in rule application (This one is trickier! Immediate rule application on the sub-nodes created from constructors means more than one ISLE invocation can be on the stack, in a reentrant way. My thought is to use a sort of workqueue to "unstack" it.);
- generalization of the several ad-hoc egraph analyses (loop depth, etc) into a framework.
The purpose of this draft PR is to be a place to do this work on a rebased and up-to-date basis. (Lots happened since the original egraph work branched off in May, including incremental compilation and a good number of smaller changes.)
While patch-wrangling this week, I tried pulling this apart into smaller pieces, but the remaining bits are pretty cyclically entangled, and/or some of the intermediate points that might make sense (e.g. egraph build and elaboration without rule application) require re-synthesizing some scaffolding that would then disappear in the final state, so that seems a bit counterproductive. Once we have a polished state I can try pulling it apart into separate logical commits at least.
cfallin updated PR #4953 from mid-end
to main
.
cfallin updated PR #4953 from mid-end
to main
.
cfallin updated PR #4953 from mid-end
to main
.
cfallin updated PR #4953 from mid-end
to main
.
cfallin updated PR #4953 from mid-end
to main
.
cfallin updated PR #4953 from mid-end
to main
.
cfallin updated PR #4953 from mid-end
to main
.
cfallin has marked PR #4953 as ready for review.
cfallin requested jameysharp for a review on PR #4953.
cfallin updated PR #4953 from mid-end
to main
.
Last updated: Dec 23 2024 at 12:05 UTC