[cider] Flattening the interpreter

[EclecticGriffin]

This is a tracking issue for the work being done toward #1183.

• [x] Translate the normal IR into the internal flat representation (FIR, perhaps pronounced "fear")
  • [x] Print out the groups and assignments as a sanity check (#1547, #1572)
• [x] Instantiate the program environment (#1578)
• [x] Print the program state in a nice human readable way (#1580)
• [ ] Program counter
  • [ ] Sketch a basic design for the program counter in the single component case. Must account for the control flow stack and the state machine for control flow operators (e.g. seq)
• [ ] Primitives
  • [ ] Flesh out the new interface
    • [ ] Instantiating a primitive requires giving it either a list of ports or an offset into the global list. May also wish to add a sanity check using the names of ports since otherwise changes in ordering within primitive definitions could break things. Probably just want to make a good macro for this.
  • [ ] Translate primitives implementations to the new interface

[sampsyo]

Looks great. One minor thing we've talked about here is the thought that we could run a primitive-free program after the "PC" step. It is of course really hard to write a primitive-free Calyx program that does anything, but maybe it works to just write the input directly into the output. But if we could write and run such a program, it would go some way to indicating that we are on the right track before trying to tack on primitives.

One possible high-level design for the PC thing is: we do not even try to represent the "intra-group" part of the state. That is, if the conceptual interpretation loop is:

for stmt in control:  # control loop
    for cycle in cycles:  # cycle loop
        while not changed:  # stabilization loop
            propagate combinational assignments

…then the "PC" would only represent progress through the outermost (control) loop. We would not attempt to have a representation for being "part way through the evaluation of a given group" for example. The result is that the PC could be pretty simple, i.e., just $n$ pointers to leaf statements in the control statement for each cell in the program (where $n$ maybe zero for inactive cells). Would this make sense?

[EclecticGriffin]

On the topic of primitive-free programs: anything I come up with either has a primitive or is arguably UB according to #1526. There's also the question about whether components must take at least one cycle which further complicates things.

I think that PC approach makes sense, with the caveat that starting/finishing a group require a few extra steps (managing the go/done ports correctly and such). The n pointers to leaf statements makes sense but we also need a program stack somewhere to handle the control flow, this can either be a separate structure in which case PC has a more direct meaning as "literally what is active" but some extra work would need to be done to make sure that the program stack(s) behave appropriately in the place of multiple parallel arms. e.g. if I finish group A which of the parallel threads was this group being called from? Or worse, what if multiple threads call the same group (comfortable ignoring this for the immediate moment).

[sampsyo]

That makes sense! Too bad it's not easier to write a primitive-free program. Maybe we have to forge ahead and get registers or something working before we have a v0 that can execute anything…

I'm not quite sure I understand the "stack" thing. Maybe I'm thinking about this wrong, but if (for example) multiple threads activate the same group, the "PC" would point to those many different group activations (i.e., control statements). So this would be enough information to always know what happens next, at the granularity of the control loop. Does this make sense?

[rachitnigam]

@EclecticGriffin is this tracker still being actively used? If not, we should close this and migrate to the new one.

[EclecticGriffin]

Oops yeah forgot about this one, we can close it. All the current stuff is happening in #1913