Module `Hardcaml.Signal_graph`

A Signal_graph.t is a created from a list of signals, and defined by tracing back to inputs (unassigned wires or constants). Functions are provided for traversing the graph.

type t

val sexp_of_t : t -> Ppx_sexp_conv_lib.Sexp.t

val create : Signal.t Hardcaml__.Import.list -> t: Create a Signal_graph.t from a list of signals (commonly, circuit outputs).

val inputs : t -> Signal.t Hardcaml__.Import.list Hardcaml__.Import.Or_error.t: Traverse the graph and find all inputs. Badly formed inputs (no name, or multiple names) return an error.

val outputs : ?⁠validate:Hardcaml__.Import.bool -> t -> Signal.t Hardcaml__.Import.list Hardcaml__.Import.Or_error.t: Return the outputs of the signal graph. If validate is true, then the outputs are checked for compatibility with circuit outputs.

val depth_first_search : ?⁠deps:(Signal.t -> Signal.t Hardcaml__.Import.list) -> ?⁠f_before:('a -> Signal.t -> 'a) -> ?⁠f_after:('a -> Signal.t -> 'a) -> t -> init:'a -> 'a

Visit all signals in the graph, starting at the outputs, in a depth-first manner. Each signal is visited only once. f_before is called before recursing on each signal's fan-in. Similiarly, f_after is called after recursing on the fan-in.

If deps is provided it will be used to compute signal dependencies rather than the default definition. This is useful for terminating traversals based on some condition on signals, e.g., if it's a register or a memory.

val fold : t -> init:'a -> f:('a -> Signal.t -> 'a) -> 'a: Fold across all signals in the graph, starting at the outputs. Each signal is visited only once.

val filter : t -> f:(Signal.t -> Hardcaml__.Import.bool) -> Signal.t Hardcaml__.Import.list: Return a list of all signals in the graph for whom f signal returns true.

val iter : t -> f:(Signal.t -> Hardcaml__.Import.unit) -> Hardcaml__.Import.unit: Iterate over all signals in the graph.

val detect_combinational_loops : t -> Hardcaml__.Import.unit Hardcaml__.Import.Or_error.t: Retuns an error if the graph has a combinational loop, that is, a path from a signal back to itself that doesn't pass though a register, memory or instantiation.

val normalize_uids : t -> t: normalize_uids t creates a copy of t that is identical to t except the uids are numbered starting at 1.

val fan_out_map : ?⁠deps:(Signal.t -> Signal.t Hardcaml__.Import.list) -> t -> Signal.Uid_set.t Signal.Uid_map.t: Fan-out of each signal in the signal graph. The fan-out of a signal is the set of signals it drives.

val fan_in_map : ?⁠deps:(Signal.t -> Signal.t Hardcaml__.Import.list) -> t -> Signal.Uid_set.t Signal.Uid_map.t: Fan-in of each signal in the signal graph. The fan-in of a signal is the set of signals that drive it.

val topological_sort : ?⁠deps:(Signal.t -> Signal.t Hardcaml__.Import.list) -> t -> Signal.t Hardcaml__.Import.list: topological_sort t sorts the signals in t so that all the signals in deps s occur before s.

val scheduling_deps : Signal.t -> Signal.t Hardcaml__.Import.list: Signal dependencies used for scheduling. Breaks loops through sequential elements like registers and memories.

val last_layer_of_nodes : is_input:(Signal.t -> Hardcaml__.Import.bool) -> t -> Signal.Uid.t Hardcaml__.Import.List.t: Final layer of combinational nodes which sit on the path between the outputs and any driving register or memory.