Register Retiming: Moving Flip-Flops Across Combinational Logic

Pipelining a design by hand means rewriting the RTL: cutting a long expression, inserting a register in the middle, and adjusting every consumer’s latency to match. Retiming does the same thing at the netlist level, automatically, by moving existing registers across logic without changing the number of registers on a cycle or the function the circuit computes. The tool can pull a register forward through a multiplexer, push it backward past an adder, and duplicate it across a fanout so that each branch gets its own copy at the right depth. None of those moves appear in the source, and the netlist that results can have a different latency structure from the one that was written.

The transformation is worth understanding because it explains two things that otherwise look like tool bugs: a timing report whose path depth does not match the RTL, and an equivalence check that fails on a design that was never functionally changed.

The legality condition

Model the circuit as a directed graph whose vertices are combinational gates and whose edges are wires, with each edge carrying a non-negative integer: the number of registers on that wire. A retiming is an assignment of an integer label $r(v)$ to every vertex. For an edge $u \to v$ with weight $w$, the retimed weight is

$$w’(u \to v) = w(u \to v) + r(v) - r(u)$$

and the retiming is legal only if every $w’$ is non-negative. The labels have a physical reading: a positive $r(v)$ moves the vertex later in time relative to its neighbours, taking a register off each of its output edges and placing one on each input edge; a negative label moves it earlier and does the reverse.

For any cycle in the graph, summing the retimed weights telescopes: the $r$ terms cancel and the total register count around the cycle is unchanged. That is the conservation law of retiming, and it is the reason the transformation preserves behaviour. The number of registers on a path between two sequential elements can change, but the number around any loop cannot, so the input-output behaviour of the circuit is unchanged even though individual paths gain or lose latency. A path that had one register and now has two has been pipelined, and the extra latency is absorbed by the other paths that feed the same destination.

The telescoping also gives the fundamental limit. If a cycle in the graph has $k$ registers and $d$ total delay around it, then no retiming can put more than $k$ registers in the cycle, so the best achievable clock period for that loop is $d/k$ plus register overhead. A loop with one register and a long dependency chain cannot be pipelined by retiming at all; the register count has to increase, which means changing the algorithm: interleaving iterations, or restructuring the computation so the loop body can be split. This is the reason some feedback structures never close timing no matter how the tool is configured.

The moves, and what each costs

Three transformations make up practical retiming, and each has a precondition.

Forward movement takes a register from every input of a gate and places one on every output. It is legal only when all of the gate’s input edges carry at least one register; otherwise the retimed weight of a bare input would go negative. It reduces the logic depth between the register and the gate’s successors while increasing it on the gate’s inputs.

Backward movement pushes a register from all outputs to all inputs. It is the inverse and is used when a path is too deep in front of a gate rather than behind it.

Register duplication splits a register at a fanout point into one copy per branch, so each branch can then be retimed independently. This is where register count can grow: duplicating a register across three branches produces three registers where there was one. It does not change the total around any cycle if the branches reconverge, but it does change the total in the design, and area grows accordingly.

The reverse move, merging registers that fan out from the same point, reduces area and is applied when it does not hurt timing. Tools decide between duplication and merging on the same cost model that drives the rest of optimization: slack gained per unit of area.

Before:                        After retiming:
  A --> R --> [logic] --> B      A --> [logic] --> R1 --> B
  R --------------> C            A --------------> R2 --> C

The figure is the smallest interesting case: a register that fed two destinations, one through logic and one directly. Retiming duplicates it, moves one copy forward through the logic, and leaves the other in place for the direct path. The move is legal because the copy that crosses the logic starts with a register on every input edge of that logic.

Where the register count comes from

The classical formulation minimizes area subject to a period constraint, or minimizes period subject to an area constraint, and the problem is solvable in polynomial time for the period-constrained version because the feasibility of a given period can be expressed as a set of difference constraints on the $r$ labels. The constraints have the form $r(u) - r(v) \le w(u \to v) - 1$ for each edge whose two endpoint delays together exceed the target period, which forces at least one register onto that edge, and a system of difference constraints is solved by shortest-path computation. Practical tools add library-specific delays, fanout limits, and the fact that a register has a cost and a setup time, so the clean polynomial result is a starting point rather than the algorithm.

Retiming also interacts with the physical design. A register moved across a gate changes which wires are long, and a retiming decision that looked good on estimated wire loads can be poor once placement is known. Tools therefore either retime before placement with statistical wire models or retime after placement with extracted parasitics, and some flows do both. Retiming after placement is constrained by the legal register positions, since a register that moves has to be re-placed, and the gain is often smaller than the pre-placement estimate.

Retiming is not free in verification terms

The netlist after retiming is not a gate-for-gate translation of the RTL. Registers have moved, duplicated, and merged, so a state-by-state comparison against the RTL fails by construction. This is the point at which combinational equivalence checking stops applying and sequential equivalence checking is needed, which is the subject of equivalence checking after synthesis. The practical consequence is that the retiming step is usually the boundary of the formal sign-off: combinational equivalence is proven between RTL and the pre-retiming netlist, and the retiming step is trusted, or proven separately by a tool that reasons about sequential behaviour.

There is also a design-intent problem. A register in the RTL is sometimes there for a reason that the tool cannot see: it holds a value that must be observable at a specific cycle for a testbench, or it isolates a reset domain, or it is a synchronizer stage. Tools provide attributes to mark registers as fixed, and the marks matter: an unmarked synchronizer stage can be moved or merged, and the metastability analysis that justified the two-flop structure then no longer describes the netlist.

The same is true of registers that form a pipeline whose depth is part of an interface contract, such as a fixed-latency memory port or a protocol pipeline. Retiming a register out of such a path changes the latency and breaks the protocol, and no timing check catches it. The constraint language has constructs for excluding paths from optimization, and using them is a design decision rather than a tool setting.

When retiming is the wrong answer

Three cases where the transformation cannot help, each with a different cause.

The design has a combinational path from an input port to an output port with no register on it. Retiming moves registers across gates; with no register on the path, there is nothing to move, and the path’s delay is fixed by the logic. The remedy is a register, which changes the interface’s latency.

The critical loop is a feedback path with one register and deep logic, as above. The conservation law forbids adding registers, so the clock period is bounded below by the loop’s delay divided by its register count. Closing it requires algorithmic change.

The path is already balanced and the tool’s move would only shift the critical path to a different branch. Retiming optimizes a global cost, and a design where two paths are equally critical gains nothing from moving registers between them; the slack report will show the same worst path before and after. Recognizing this saves a great deal of time spent re-running the tool with different settings.

What retiming genuinely buys is the case it was designed for: a design whose total logic delay is acceptable but whose distribution across registers is not, because the RTL author placed pipeline stages by hand at convenient expression boundaries rather than at balanced delay boundaries. Moving those registers to where the delay actually is recovers the slack without a source change, and the resulting netlist implements the same function with the same number of registers around every loop. That is a narrow but common condition, and it is why the transformation is standard in synthesis rather than an exotic option.