Stream: cranelift

Topic: How to cite ægraphs

view this post on Zulip Jules Merckx (Oct 24 2024 at 14:33):

I'm working on research that builds on Cranelift's scoped elaboration algorithm. Is there a preferred way to cite this work? (@Chris Fallin )

view this post on Zulip Chris Fallin (Oct 24 2024 at 14:53):

Great question! I should really publish an actual paper :sweat_smile: for now, the EGRAPHS 2023 keynote is probably the most academic citation -- something like (in bibtex)

@misc{aegraphs-egraphs2023,
author = {C Fallin},
title = {aegraphs: Acyclic E-graphs for Efficient Optimization in a Production Compiler},
howpublished = {{EGRAPHS} 2023 keynote},
}

if that works?

view this post on Zulip Chris Fallin (Oct 24 2024 at 14:54):

and you could also cite the RFC (https://github.com/bytecodealliance/rfcs/pull/27)

Cranelift: Using E-Graphs for Verified, Cooperating Middle-End Optimizations by cfallin · Pull Request #27 · bytecodealliance/rfcs
Rendered This RFC proposes to add a middle-end optimization framework to Cranelift based on e-graphs. A middle-end optimization framework works to improve the target-independent IR (intermediate re...

view this post on Zulip Jules Merckx (Oct 24 2024 at 14:57):

That works definitely, thanks! If you don't prefer the RFC to be cited, I'd go with the keynote.

view this post on Zulip Jules Merckx (Oct 24 2024 at 14:57):

One more small question if you don't mind, if I understand correctly, currently e-graph extraction happens greedy? That is, there is no consideration of node reuse during extraction, only during elaboration, is that right?

view this post on Zulip Chris Fallin (Oct 24 2024 at 15:05):

Sure, yep, keynote is great.

Re: extraction -- that's correct, the costs don't update as we do selection. Doing so is an NP-hard problem I think (weighted set cover or something like that?). If you have ideas here on better heuristics though I'd love to hear them!

view this post on Zulip Jules Merckx (Oct 24 2024 at 15:10):

Chris Fallin said:

Re: extraction -- that's correct, the costs don't update as we do selection. Doing so is an NP-hard problem I think (weighted set cover or something like that?). If you have ideas here on better heuristics though I'd love to hear them!

Thanks for your answers, they're extremely helpful!
Yes NP-hard (https://effect.systems/blog/egraph-extraction.html). In my work, I formulated the problem as an ILP problem and for the cases I'm looking at it works well but this can't be the way to go for a production compiler, especially in JIT context :sweat_smile:

view this post on Zulip Chris Fallin (Oct 24 2024 at 15:12):

(I mean, all you have to do is show that P=NP with a practical reduction...)

view this post on Zulip Chris Fallin (Oct 24 2024 at 15:13):

I guess it's an interesting question whether we could have some heuristic that does better -- divide costs by number of users, or propagate (decayed) cost upward or downward, or something like that

Last updated: Dec 23 2024 at 12:05 UTC