Optimize value-producing assembly

[Wv5twkFEKh54vo4tta9yu7dHa3]

Hi, I've been looking into egg recently to help optimize a simple assembly language that produces values into registers. The thing I want to start with is using registers optimally: there are 4 registers and current assembly generation only uses one. So I want to go from

(fetchAttribute (data (key "key") (dreg 1)))
(bitwise (data (sreg 1) (dreg 1) (op BOOL) (len 4) (mask ffffff00) (xor 00000000)))
(byteorder (data (sreg 1) (dreg 1) (op 1) (len 4) (size 4)))
(cmp (data (sreg 1) (op GTE) (cmpData 00000400)))
(fetchAttribute (data (key "key") (dreg 1)))
(bitwise (data (sreg 1) (dreg 1) (op BOOL) (len 4) (mask ffffff00) (xor 00000000)))
(byteorder (data (sreg 1) (dreg 1) (op 1) (len 4) (size 4)))
(cmp (data (sreg 1) (op LTE) (cmpData 000004ff)))
(fetchAttribute (data (key "key") (dreg 1)))
(bitwise (data (sreg 1) (dreg 1) (op BOOL) (len 4) (mask ffffff00) (xor 00000000)))
(setAttribute (data (key "key2") (sreg 1)))

To

(fetchAttribute (data (key "key") (dreg 1)))
(bitwise (data (sreg 1) (dreg 1) (op BOOL) (len 4) (mask ffffff00) (xor 00000000)))
(byteorder (data (sreg 1) (dreg 2) (op 1) (len 4) (size 4)))
(cmp (data (sreg 2) (op GTE) (cmpData 00000400)))
(cmp (data (sreg 2) (op LTE) (cmpData 000004ff)))
(setAttribute (data (key "key2") (sreg 1)))

Is this something I can do using egg at all? I did an implementation doing graph coloring to allocate registers and re-use already computed values, but this is only one of the many optimizations I would like to do and the part where I don't have to think about what order to apply optimizations in and maintain all the equivalent representations sounds really interesting to me.

[mwillsey]

I do not think that register allocation is a problem well-suited to e-graphs; you don't want to be representing all possible ways to allocate registers. However, if you plan on doing some other kind of optimization in the e-graph, it's certainly possible to do things "outside" the e-graph and cooperate with those optimizations. For example, you might do a little optimization in the e-graph, extract some version of the program and do register coloring on that, and then re-insert that into the e-graph. I would also advise you that sequential instructions are not the friendliest representation for e-graphs; it is typically better to do some kind of conversion to dataflow first.

[Wv5twkFEKh54vo4tta9yu7dHa3]

Thanks for your answer, I will go another way and maybe come back to egg later as it doesn't seem to fit the problem I'm working on, but it's very cool regardless :)