Implement Copy Propagation

[rachitnigam]

trafficstars

Software compilers can optimize the following code:

x = 1
y = x
z = y + 1

To:

x = 1
z = x + 1

The goal of building such a pass in Calyx is computing writes to registers that are not needed. A common place where this occurs is saving the value generated by a port marked as @stable into a register. For example, the out port on a mult_pipe is @stable and therefore can be read directly:

group do_mult {
  mult.go = !mult.done ? 1;
  mult.left = ...; mult.right = ...;
  r.in = mult.done ? mult.out;
  r.write_en = mult.done ? 1;
  do_mult[done] = r.done;
}
group use_r {
  ...
  add.left = r.out;
}

This group saves the value computed by the mult into the register r. However, mult.out is going to be available till the next invocation of mult which means we can just use the value from mult.out directly:

group do_mult {
  mult.go = 1;
  mult.left = ...; mult.right = ...;
  do_mult[done] = mult.done;
}
group use_r {
  ...
  add.left = mult.out;
}

Note that optimization pointless writes to a register is the same problem because register ports are marked @stable as well. Similarly, this pass should also eliminate groups that perform writes to a register that is never used in the future again.

[sampsyo]

Cool idea! FWIW, the typical name for this optimization is "copy propagation."

As a thought experiment, I wonder if it's worth trying to decompose this into two versions: (1) successive copies of registered values in particular (e.g., where x, y, and z are all registers in the first example above); and (2) dealing with @stable values as well. The alternative is that (1) is simply a special case of (2), i.e., we start with any @stable signal, including the output of registers.

If we do something involving @stable, I would strongly urge us to first document the semantics of @stable in English. This is related to https://github.com/cucapra/calyx/issues/304, which concerns inferring the @stable annotation. I think it's critical to be precise about what this means so we can think clearly about what would make a pass that exploits @stable correct.

[rachitnigam]

There is some description of what @stable does in the documentation: https://docs.calyxir.org/lang/attributes.html#stable

[sampsyo]

Ah, thanks! My grep for @stable failed me because it doesn't have the sigil. 🤣

Anyway, maybe we need to nail it down in a bit more detail to do this work… TBH, I'm still a teensy bit fuzzy about what it's supposed to guarantee. Yes, it stays "live" beyond a single group, but for how long? Not indefinitely, to be sure…

[rachitnigam]

So there are two ways to interpret it and I guess I've conflated them somewhat:

1. A @stable marked port is directly connected to some register in the component and therefore can be used after the component is invoked. An example of a port that is not stable is something that is connected to the output of an adder: out = add0.out
2. This pass probably puts an even stronger constraint on @stable port that says the value does not change till the next use. The output port of a register is a canonical example of this-the output only changes when the register is used again.

We probably need to rely on the second interpretation for this pass

[sampsyo]

Right, that's a good way of putting it. In both interpretations, the answer to the "how long does it last?" question is different, although I'm still not exactly sure what the answer is, exactly. It's something like "the value stays the same, and is guaranteed to produce the same value if read multiple times, until we provide any new inputs to the component." So this would rule out, for example, a component that has registered output that changes over time—for example, if it's a counter that increments every 5 cycles. I think? Anyway, nailing this down seems to be the key to crystallizing this pass's responsibilities.

[rachitnigam]

Yeah, I think it better not be something that changes over time. I think "stable" should mean something like: The port retains the exact same value till the next invocation (or use) of the component. A port can only be stable if it is connected to another stable port and that port does not get updated between two invocations.

[rachitnigam]

@bcarlet expressed interest in implementing this pass! Let's chat if you'd like to do this @bcarlet!