Module autopipe 

Pipelining combinational logic to a target clock with the fewest register bits, the cut certified optimal.

pipeline gives every node of a combinational TimingGraph a stage: its inputs at 0, its outputs at the latency, registers only where Cuts allows them (on the nets the design names, the cuts a designer writes into its source; or on any net, for a pipeline emit writes out), and no path between registers deeper than the period. It is the minimum-area retiming of Leiserson & Saxe (Retiming synchronous circuitry, 1991) of the logic with its outputs fed back to its inputs through the latency’s registers, written as a linear program over differences of stages:

• an edge out of a node no register may follow holds none, so its ends share a stage; any other edge holds s(to) − s(from) ≥ 0;
• a node where the depth from wherever a stage can begin (past a register on a net into it, or an input) first passes the period lies at least a stage later. These constraints number a node’s reach over the period, every node over; only those a schedule breaks are added, found by walking each stage of the schedule from where it begins, and the schedule solved again until it breaks none. The rest it meets as they stand, so its optimum over the constraints added is the optimum over them all, its certificate the same flow;
• the registers on a net are shared by its readers, so a net costs the most any reader needs, through a mirror node no earlier than any reader (Leiserson & Saxe’s fanout sharing).

Its dual is a minimum-cost flow (logicaffeine_proof::min_cost_flow): the flow’s potentials are the stages, integral and optimal by complementary slackness, and a latency too short for the period is the dual’s negative cycle. check replays a plan against the graph: every register count it implies is whole and where a register may go, every input is at stage 0 and every output reaches the latency, and the depth between registers is within the period. emit writes a plan out as a Verilog module, every connection reading its source through the registers the plan puts on it.

Structs

Plan

A pipeline: each node’s stage, and the registers each net bit carries.

Enums

Cuts

Where registers may go.

EmitError

Why a plan could not be written out.

PipeError

Why logic was not pipelined.

Functions

check

Whether plan pipelines graph: every edge’s register count is the difference of its ends’ stages, never below zero and zero out of a node its policy puts no register after; every input at stage 0 and every output with the registers to reach the latency; every named net’s registers the most its readers and the latency need; and no path between registers deeper than the period.

emit

graph’s logic pipelined by plan as a Verilog module named module: every connection reads its source through as many registers as the plan puts on it, clocked by clk and, when enable names a port, stepping only when it is high. An input of the source with one of those names that no logic reads is that port; one the logic reads is refused.

min_latency

The least latency graph pipelines in at period: the latest any output’s sink must be in the earliest schedule the difference constraints allow.

pipeline

The pipeline of graph at period and latency with the fewest register bits, its registers where policy allows.

unpipelined

The logic of a pipeline with its registers taken out, and the latency they made: a graph pipeline cuts afresh at any period. A pipeline’s registers are plain flip-flops, one registered edge into each, and every path from its inputs to a node holds as many of them, so every output is the same number of clocks late; taken out, each is a wire from its data, or its data’s constant when the source hands it one. A register with more in than its data (an enable, a reset, a memory’s port) is refused by name, and so is a node whose paths hold different numbers of registers; a register in a loop leaves logic looping through none.