I like the idea of exhaustive search, which the simplicity of the 6502 seems ideally suited for, but the search speed seems a bit limiting. I wonder if there's not potential for more generation restriction (e.g. code can only use a specific N bytes of zero page) and heavy search pruning to speed it up? If it could generate optimal 20-30 op sequences in semi-reasonable time that'd make it very useful.

Having it only use operations that use a specific set of zero-page addresses is already supported, yep!

20-30 ops is probably impossible, unfortunately. The combinatorial explosion is just too enormous.

e-graphs have been repeatedly reinvented across decades for many purposes. One of them is superoptimization.

https://en.wikipedia.org/wiki/E-graph

https://www.cs.cornell.edu/courses/cs6120/2025sp/blog/supero...

https://github.com/philzook58/awesome-egraphs