Extracting cycles

[gussmith23]

Hi all!

I love that egglog nominally supports cycles -- in my representation I depend on them! However, unsurprisingly, some basic things break when there are cycles in the graph. For one, extraction. Here's a simple demo:
https://egraphs-good.github.io/egglog/?program=XQAAgACKAAAAAAAAAAAUGQgnfMUD9dO1z8bgG1j6kawVXUEg4-OjMnSkFig1BMUpLoB11m8lN7hs54k_jrWDgBom1pM_un2sTDWT7pJvZctos6Jh0hvJbf7tfYE6ERJ36amoV-zVXgDzTnL-s6VA

I'm wondering if there are quick and dirty hacks for getting a representative of an eclass, when that representative is guaranteed to have a cycle. I realize that this can go wrong (1) during naive, bottom-up extraction, but even if extraction worked, (2) when we try to print. I assume the current egglog extraction is bottom-up, which is why this is happening, but maybe I'm wrong? And if it's the case, are there any other implemented extraction strategies?

[oflatt]

I think so far we don't have an extraction algorithm that allows cycles.
Why do you need such a thing?
One thing we could do is experiment with such algorithms in the extraction-gym repo

[gussmith23]

Lakeroad explicitly uses a graph-based (and not tree- or DAG-based) representation to represent hardware designs. It actually turns out this is quite natural, and is exactly what Verilog does as well, though it took me years to realize it. Regardless, cyclic graphs are very natural in hardware. Happy to give concrete examples if it helps. In fact, there's one visually laid out here:
https://github.com/uwsampl/lakeroad/blob/fbcb0936462ca092ef8e3ea868f54552ce401eec/lakeroad-egglog/tests/egglog_tests/construct_sequential_cycle.egg#L12-L21

I'm happy to experiment on this. Do you or any egglog people have quick thoughts about any "obvious" first approaches to implementing this?

[oflatt]

Interesting!
Could you break cycles by adding a name to something, and extracting that name as well as the thing itself?
Or does that not always work?
Example: Make a placeholder name for the registers

[oflatt]

If you can't break the cycles, you need a way to extract with cycles
I think in the ILP encoding of extraction, allowing cycles actually makes it easier. So you might be able to implement that for egglog
https://github.com/egraphs-good/extraction-gym/blob/main/src/extract/ilp_cbc.rs
I think it might be slow though...