Smoketest: Churchroad multiply expression compiled and simulated via Lakeroad

[gussmith23]

A simple first smoketest would be to use Churchroad to compile a design which Lakeroad can already synthesize by itself: a multiply narrow enough to fit on a single DSP.

Essentially, the steps are this:

• [x] 1. Begin with a combinational multiply expression in Verilog.
• [x] 2. Import design into Churchroad; something like (Op2 (Mul) a b) of <18 bits.
• [x] 3. Rewrite the multiply to a DSP primitive (using the generic primitive interfaces from Lakeroad). Something like (rewrite (Op2 (Mul) a b [of a certain bitwidth]) (PrimitiveInterface (DSP <params>) a b)
• [x] #85
• [ ] 5. If Lakeroad returns successfully, which it should, insert the compiled version back into the egraph.
• [ ] 6. Extract a compiled design from the egraph.
• [ ] 7. Compile extracted design to Verilog.
• [ ] 8. Simulate against original design to validate correctness.

[gussmith23]

2024-07-10

Current step: given an egraph with primitive interfaces in it, (1) find the primitive interfaces and (2) call Lakeroad on them.

Working on (1).

Ah, something I messed up: I thought I needed to extract the PrimitiveInterface expressions and run them through Lakeroad. That is true, because it tells us what template to use (or in the future, allows us to generate sketch templates automatically). But I also need to extract something concrete to use as the spec. E.g. if the PrimitiveInterface was merged with a Mul expression, i need the Mul.

Currently once again confused about what extract_variants actually does. I want it to give me a bunch of variants from a value, but it seems to be failing to give me even one variant!

[gussmith23]

2024-07-11

Oliver says that the extract_variants behavior is odd. I'm debugging now. I put in a print inside the function that's always outputtting the same thing:

[/Users/gus/egglog/src/extract.rs:87:17] func.nodes.iter(false).filter(|&(_, output)|
            (output.value == output_value)).collect::<Vec<_>>() = []

Seems odd that this is always empty.

The value it's being compared against is

[/Users/gus/egglog/src/extract.rs:75:9] value = Value {
    tag: "Expr",
    bits: 23,
}

I don't know exactly what this is. But I guess the question is, is

Oh! figured it out! They were comparing Values without first converting the Value to the leader Value for the eclass.

I think I want to build a custom Extractor for this problem in the end anyway...I don't quite know how to use the output of extract_variants in a useful way.

I'm running into what's quickly becoming a familiar issue: I have to do some things over an egglog::EGraph and some things over an egraph_serialize::EGraph, and correlating eclasses between them is really not easy.

2024-07-12

Seems like you should be able to go back and forth between eclass ids in serialized an nonserialized egraphs based on classids. https://github.com/egraphs-good/egglog/blob/0da32092999b558486b521b5a106a523d032ffd4/src/serialize.rs#L105C57-L106

2024-07-14

Nearly have Churchroad calling out to Lakeroad. Current issue is that Verilog produced is incorrect: outputs don't have bitwidths. Switching to merging Andrew's PR because I think it has some code that will help.

[gussmith23]

2024-07-16

I'm at the stage where I've run Lakeroad and gotten a result, and I have to stick it back in the egrpah. To do so, I'm using the plugin to convert it to egglog commands. However, the call to the plugin is just failing w/o much error. It's failing in the churchroad pass itself.

I'm gonna just run the plugin manually and see what's happening.

Here's the issue: there's a DSP instance, but we don't have the definition of the DSP module. This means that we know what ports are connected up in the DSP, but we don't actually know what direction each of the ports is. Currently, the plugin relies on port direction, because it treats inputs and outputs differently when generating egglog code.

I think the easiest solution is to just expect that all modules are fully defined, but also ensure that when we generate egglog code we don't necessarily generate all of the egglog for the referenced modules. I mean, we could also just geenrate that code as well, but it'll clutter the egraph at this point.

Next thing: we need those module port input/output declarations to be fed in to the smoketest somehow, too. The real solution to this is to include the DSP48E2 semantics officially somewhere in churchroad (or have them be specified by Lakeroad, or by the user). A quicker bandaid would be to just concat the DSP definition onto the output of Lakeroad, as a hack.

Ok, implemented that hack.

Next issue: churchroad code being produced isn't portable. I think there's gonna be a number of this type of bug. Basically, it's not safe to just run it on the egraph, it generally expects to be run on an empty egraph already.

First issue of this type: we're attempting to re-let-bind names that have already been bound.

This could be fixed pretty simply by just adding a random string to the names, i suspect.

[gussmith23]

2024-07-24

Okay, I added salt.

Now the issue is that the output egglog defines let bindings for inputs e.g. a.

I'm wondering if we just get rid of those entirely, and instead enforce the use of something that reads the IsPort relation. I could also make it a flag on the Yosys pass to optionally make let bindings.

Two other things we'll run into.

First is that we always define the inputs to be Vars. That won't be right, in our case, though---instead of Vars we want something that we can union to the input eclasses.

Second is that we define a let binding for the output.

One question re: inputs---should they be Vars at all? They could also be Wires. What's the difference between a Var and a Wire? Wire doesn't get looked up during interpretation. Wire can't be interpreted (for now). Var implies that it's an input. Wire implies that it'll be connected to something. Should we just support both? Should we force the user to decide between them? We could also allow the user to specify an expression to union each input to -- that would probably work best in our situation, to avoid the hassle of having to generate temporary, non-clashing names for input and output exprs.

[gussmith23]

2024-07-25

So how to solve the issue of colliding let bindings on ports? I think we include an option to optionally disable/enable let bindings for ports. That's just a convenience feature.

Okay, I did that. Now I just need to include a way to add custom merge statements, that will merge the ports with the relevant expressions in the existing egraph.

Alright, i'm nearly done with that too. might need to stop soon though.

Ok, i'm figuring out how to pass in the expressions to Yosys and quoting is giving me trouble (unsurprisingly, maybe)

[gussmith23]

2024-07-26

How does the arg parser in Yosys work?

See question and notes in here https://github.com/YosysHQ/yosys/issues/4511

[gussmith23]

2024-07-28

I think I should probably just hack this for now until the Yosys team tells me how to fix it. Basically just replace spaces with underscores on the way in.

OK that worked! Woohoo!

Now just have to extract a program from the egraph, convert to Verilog, and simulate.

Working on the extractor now. Gonna just build an extractor that filters out all non-structural Verilog.

Running into the following issue. When trying to extract a Verilog program, I found that the egraph had at least one Concat node with no children. I suspected that the children had been deleted, so I disabled the delete statements on the Yosys plugin, and indeed that bug went away. But then a new bug manifested: there are now eclasses with only Wires in them, which means that, if I tell the structural Verilog extractor to ban Wire nodes, there are unextractable eclasses.

The root of this must be that there's some bad Verilog being generated somewhere, or we're translating Verilog to egglog incorrectly.

How would this happen? Basically, we're generating wires that don't get unioned to anything.

We should add something that detects this in the future. IT would be pretty easy to do.

Found it:

    ; P_0[47:16]
    (let v19-1722205243451808000 (Wire "v19-1722205243451808000" 32))

This wire isn't unioned with anything. Taht's maybe unsurprising -- it's the unused portion of the output wire. It is very literally not connected to anything. No port or anything. It is, correctly, an unused wire.

So how to handle this? Seems like filtering out all wires is not correct. What if we leave wires in, but we prioritize everything above them? And then we can hopefully just implement to-verilog with them.

That may have worked -- at least the current error went away. I'm now generating Verilog, but I doubt it's legal (but hoping it's close to correct). Time to simulate it and see what happens. Getting so close!!!!

See #92, #93.