Is it plausible for Clash to (optionally) automatically insert registers to meet timing requirements?

[tomjaguarpaw]

Sometimes when we write Clash we write large signal computations that are essentially pure expressions. Here's a silly but illustrative example:

mySignal :: Signal Int
mySignal = mySignal1 +. mySignal2 +. mySignal3 +. ... +. mySignal1024
    where (+.) = liftA2 (+)

Even if we reparenthesise this expression so that it is of log depth then it will still be eight additions deep and it is easily possibly that a signal cannot propagate through it properly within one cycle. We could rewrite it thus:

mySignal :: Signal Int
mySignal = r( ... (r (r mySignal1 +. r mySignal2) +. r (r mySignal3 +. r mySignal4)) + ...
    where r = register undefined
          (+.) = liftA2 (+)

That is, we can register every subexpression. If every subexpression meets timing requirements then the rewritten version of mySignal will too. We can be even cleverer and only add registers in the few places where it is necessary (as long as we also add registers in parallel pipelines so that inputs to subsequent combinators are synchronised). (NB it is not possible to add registers into any recursive parts of the design.)

My question is: would it be possible to add an optional register insertion phase to Clash? It is not semantics preserving, because the transformed output may be delayed by more than the original output, but it is semantics preserving up to time shift. Clash could report this time shift to the user.

[ggreif]

IIRC Signals have a Num instance, so you can use (+) directly without lifting.

Just my 2 cents!

[christiaanb]

While it is plausible that clash could one day do this, there are several caveats (some of which you already mentioned):

• registers cannot be inserted into feedback loops.
• we need to develop a heuristic for propagation delay, so that we know when/if to add registers, and also how to space them apart.

I always hoped that we could just place a couple of registers at the output of our circuits, and that the FPGA synthesis tools would just re-time them. However, I've been told they don't (always) do this, so I guess we would need to add such a pass to clash. Certainly plausible, but we would need people to implement it.

Somewhat related, we already have delay-annotated signals in clash: http://hackage.haskell.org/package/clash-prelude-0.10.11/docs/CLaSH-Signal-Delayed.html
Using those we can already statically verify that parallel pipelines are properly synchronized, although the user still needs to manually add the registers.