egg for assembly optimisation?

[benmkw]

Looking at elvm I was wondering if egg could be used to implement dead code elimination/ redundant store/ load optimisation on its IR (eir). Eir s basically a very restricted set of assembly instructions and adopting egg for eir could prove its feasibility for real world instruction sets as well.
For ELVM specifically it could maybe help reduce code size a bit as it currently lacks any optimisations and there might thus be much low hanging fruit.
Egg could also easily be compared to existing c compilers performance (although one would not expect a real competitive setting here of course).

Specific questions are probably around jmp and side effects, relevant disucssions here seem to be #145 and #106

Any pointers are appreciated :)

[chandrakananandi]

You may be interested in (and maybe have already seen!) this paper: https://ztatlock.net/pubs/2009-popl-equality-saturation-optimizations-egraphs.pdf.

[benmkw]

This paper looks very interesting. I was aware of similar effort in halide and cranelift where they seek to express, combine and execute rewrite rules effectively.

The referenced paper seems to require the translation to their IR, thus I assume egg might not be an obvious/ easy choice for this type of application?

The egg paper references Denali but notes that "it was intended to be used on
straight line code only and therefore, did not apply to large real programs" so I think this means it can't handle control flow? This would come back to my previous question Specific questions are probably around jmp and side effects. The Denali paper states "The language includes higher-level control constructs, such as conditionals and loops." which seems somewhat contradictory to me at the moment because they state their input language can handle more than straight line code.
It also used e-graphs but needs and SMT solver in addition (I did not yet understand how its used/ why/ how it would be needed for egg for optimising assembly with egg)

Coming from the Denali paper it seems to me egg+z3/cvc4 (as an example) should be able to fulfil my goal but I'm not yet sure how exactly :D

I may reframe my question such that I'm wondering if e-graphs can be used to express the flow of execution of a simple assembly program such as one written in EIR, and whether or not the expressiveness of the rewrite rules is appropriate for defining rewrites such as dead code elimination/ redundant load/ store removal.

[mwillsey]

I don't think that syntactic rewrites are a good fit for transformations like dead-code elimination and the like. The 2009 paper above has a lot to say about encoding control flow, but it basically boils down to clever tricks for encoding it as dataflow.

All this is to say that I don't think egg is a good fit for assembly optimization, at least with significant encoding tricks (like the 2009 paper) to make assembly look not-that-much like assembly :).