Network interface API

This page describes the interface of a logic network data structure in mockturtle.

Mandatory types and constants

The interaction with a logic network data structure is performed using four types for which no application details are assumed. The following four types must be defined within the network data structure. They can be implemented as nested type, but may also be exposed as type alias.

class mockturtle::network

Public Types

using base_type = network

Type referring to itself.

The base_type is the network type itself. It is required, because views may extend networks, and this type provides a way to determine the underlying network type.

struct node

Type representing a node.

A node is a node in the logic network. It could be a constant, a primary input or a logic gate.

struct signal

Type representing a signal.

A signal can be seen as a pointer to a node, or an outgoing edge of a node towards its parents. Depending on the kind of logic network, it may carry additional information such as a complement attribute.

struct storage

Type representing the storage.

A storage is some container that can contain all data necessary to store the logic network. It can be constructed outside of the logic network and passed as a reference to the constructor. It may be shared among several logic networks. A std::shared_ptr<T> is a convenient data structure to hold a storage in a logic network.

Further, a network must expose the following compile-time constants:

static constexpr uint32_t min_fanin_size;
static constexpr uint32_t max_fanin_size;

The struct is_network_type can be used to check at compile time whether a given type contains all required types and constants to implement a network type. It should be used in the beginning of an algorithm that expects a network type:

template<typename Ntk>
void algorithm( Ntk const& ntk )
{
  static_assert( is_network_type_v<Ntk>, "Ntk is not a network type" );
}

Constructors and copy assignment

class mockturtle::network

Public Functions

network()

Default constructor.

Constructs an empty network.

explicit network(storage s)

Constructor taking a storage.

network &operator=(const network &other) = default

Default copy assignment operator.

Currently, most network implementations in mockturtle use std::shared_ptr<storage> to hold and share the storage. Thus, the default behavior of copy-assigning a network only copies the pointer, but not really duplicating the contents in the storage data structure. In other words, it makes a shallow copy by default.

Methods

The remainder lists methods that may be implemented by a network data structure. Algorithms can check whether a method method is implemented using the has_method struct. As an example to check whether the method get_constant is implemented one of the following two static assertions can be added to the beginning of an algorithm:

// variant 1
static_assert( has_get_constant<Ntk>::value, "Ntk does not implement the get_constant method" );

// variant 2
static_assert( has_get_constant_v<Ntk>, "Ntk does not implement the get_constant method" );

Duplicate network

class mockturtle::network

Public Functions

network clone()

Explicitly duplicate a network.

Deep copy a network by duplicating the storage. Note that this method does not duplicate the network events.

Primary I/O and constants

class mockturtle::network

Public Functions

signal get_constant(bool value) const

Gets constant value represented by network.

A constant node is the only node that must be created when initializing the network. For this reason, this method has constant access and is not called create_constant.

Parameters

value – Constant value

signal create_pi(std::string const &name = std::string())

Creates a primary input in the network.

Each created primary input is stored in a node and contributes to the size of the network.

Parameters

name – Optional name for the input

void create_po(signal const &s, std::string const &name = std::string())

Creates a primary output in the network.

A primary output is not stored in terms of a node, and it also does not contribute to the size of the network. A primary output is created for a signal in the network and it is possible that multiple primary outputs point to the same signal.

Parameters
  • s – Signal that drives the created primary output

  • name – Optional name for the output

signal create_ro(std::string const &name = std::string())

Creates a register output in the network.

Each created register output is stored in a node and contributes to the size of the network. Register outputs must be created after all primary inputs have been created and must have a corresponding register input that is created with create_ri.

Register outputs serve as inputs for the network.

Register outputs and register inputs always have to be created in pairs; they are associated to each other by index, i.e., the first created register output corresponds to the first created register input, etc.

Parameters

name – Optional name for the register output

void create_ri(signal const &s, std::string const &name = std::string())

Creates a register input in the network.

A register input is not stored in terms of a node, and it also does not contribute to the size of the network. A register input is created for a signal in the network and it is possible that multiple register inputs point to the same signal. Register inputs must be created after all primary outputs have been created and must have a corresponding register output that is created with create_ro.

Register inputs serve as outputs for the network.

Register outputs and register inputs always have to be created in pairs; they are associated to each other by index, i.e., the first created register output corresponds to the first created register input, etc.

Parameters
  • s – Signal that drives the created primary output

  • name – Optional name for the output

bool is_combinational() const

Checks whether the network is combinational.

Returns true if and only if the network has no registers (neither register outputs nor register inputs).

bool is_constant(node const &n) const

Checks whether a node is a constant node.

bool is_ci(node const &n) const

Checks whether a node is a combinational input (PI or RO).

bool is_pi(node const &n) const

Checks whether a node is a primary input.

bool is_ro(node const &n) const

Checks whether a node is a register output.

bool constant_value(node const &n) const

Gets the Boolean value of the constant node.

The method expects that n is a constant node.

Create unary functions

class mockturtle::network

Public Functions

signal create_buf(signal const &f)

Creates signal that computes f.

This method is not required to create a gate in the network. A network implementation can also just return f.

Parameters

f – Child signal

signal create_not(signal const &f)

Creates a signal that inverts f.

This method is not required to create a gate in the network. If a network supports complemented attributes on signals, it can just return the complemented signal f.

Parameters

f – Child signal

Create binary functions

class mockturtle::network

Public Functions

signal create_and(signal const &f, signal const &g)

Creates a signal that computes the binary AND.

signal create_nand(signal const &f, signal const &g)

Creates a signal that computes the binary NAND.

signal create_or(signal const &f, signal const &g)

Creates a signal that computes the binary OR.

signal create_nor(signal const &f, signal const &g)

Creates a signal that computes the binary NOR.

signal create_lt(signal const &f, signal const &g)

Creates a signal that computes the binary less-than.

The signal is true if and only if f is 0 and g is 1.

signal create_le(signal const &f, signal const &g)

Creates a signal that computes the binary less-than-or-equal.

The signal is true if and only if f is 0 or g is 1.

signal create_gt(signal const &f, signal const &g)

Creates a signal that computes the binary greater-than.

The signal is true if and only if f is 1 and g is 0.

signal create_ge(signal const &f, signal const &g)

Creates a signal that computes the binary greater-than-or-equal.

The signal is true if and only if f is 1 or g is 0.

signal create_xor(signal const &f, signal const &g)

Creates a signal that computes the binary XOR.

signal create_xnor(signal const &f, signal const &g)

Creates a signal that computes the binary XNOR.

Create ternary functions

class mockturtle::network

Public Functions

signal create_maj(signal const &f, signal const &g, signal const &h)

Creates a signal that computes the majority-of-3.

signal create_ite(signal const &cond, signal const &f_then, signal const &f_else)

Creates a signal that computes the if-then-else operation.

Parameters
  • cond – Condition for ITE operator

  • f_then – Then-case for ITE operator

  • f_else – Else-case for ITE operator

signal create_xor3(signal const &a, signal const &b, signal const &c)

Creates a signal that computes the ternary XOR operation.

Create nary functions

class mockturtle::network

Public Functions

signal create_nary_and(std::vector<signal> const &fs)

Creates a signal that computes the n-ary AND.

If fs is empty, it returns constant-1.

signal create_nary_or(std::vector<signal> const &fs)

Creates a signal that computes the n-ary OR.

If fs is empty, it returns constant-0.

signal create_nary_xor(std::vector<signal> const &fs)

Creates a signal that computes the n-ary XOR.

If fs is empty, it returns constant-0.

Create arbitrary functions

class mockturtle::network

Public Functions

signal create_node(std::vector<signal> const &fanin, kitty::dynamic_truth_table const &function)

Creates node with arbitrary function.

The number of variables in function must match the number of fanin signals in fanin. fanin[0] will correspond to the least-significant variable in function.

Parameters
  • fanin – Fan-in signals

  • function – Truth table for node function

signal clone_node(network const &other, node const &source, std::vector<signal> const &fanin)

Clones a node from another network of same type.

This method can clone a node from a different network other, which is from the same type. The node source is a node in the source network other, but the signals in fanin refer to signals in the target network, which are assumed to be in the same order as in the source network.

Parameters
  • other – Other network of same type

  • source – Node in other

  • children – Fan-in signals from the current network

Returns

New signal representing node in current network

Restructuring

class mockturtle::network

Public Functions

void substitute_node(node const &old_node, signal const &new_signal)

Replaces one node in a network by another signal.

This method causes all nodes that have old_node as fanin to have new_signal as fanin instead. In doing so, a possible polarity of new_signal is taken into account. Afterwards, the fan-out count of old_node is guaranteed to be 0.

It does not update custom values or visited flags of a node.

old_node Node to replace new_signal Signal to replace old_node with

void substitute_nodes(std::list<std::pair<node, signal>> substitutions)

Perform multiple node-signal replacements in a network.

This method replaces all occurrences of a node with a signal for all pairs (node, signal) in the substitution list.

substitutions A list of (node, signal) replacement pairs

std::optional<std::pair<node, signal>> replace_in_node(node const &n, node const &old_node, signal new_signal)

Replaces a child node by a new signal in a node.

If n has a child pointing to old_node, then it will be replaced by new_signal. If the replacement catches a trivial case, e.g., n becomes a constant, then this will be returned as an optional replacement candidate by the function.

The function updates the hash table. If no trivial case was found, it updates the hash table according to the new structure of n.

n Node which may have old_node as a child old_node Child to be replaced new_signal Signel to replace old_node with

Returns

May return new recursive replacement candidate

void replace_in_outputs(node const &old_node, signal const &new_signal)

Replaces a output driver by a new signal.

If old_node is drive to some output, then it will be replaced by new_signal.

old_node Driver to be replaced new_signal Signal replace old_node with

void take_out_node(node const &n)

Removes a node (and potentially its fanins) from the hash table .

The node will be marked dead. This status can be checked with is_dead. The node is no longer visited in the foreach_node and foreach_gate methods. It still contributes to the overall size of the network, but num_gates does not take dead nodes into account. Taking out a node does not change the indexes of other nodes. The node will be removed from the hash table. The reference counters of all fanin will be decremented and take_out_node will be recursively invoked on all fanins if their fanout count reach 0.

void substitute_node_of_parents(std::vector<node> const &parents, node const &old_node, signal const &new_signal)

Replaces one node in a network by another signal.

This method causes all nodes in parents that have old_node as fanin to have new_signal as fanin instead. In doing so, a possible polarity of new_signal is taken into account. It also replaces old_node with new_signal, if it drives primary outputs.

It does not update custom values or visited flags of a node.

parents Vector of parents old_node Node to replace new_signal Signal to replace old_node with

Structural properties

class mockturtle::network

Public Functions

uint32_t size() const

Returns the number of nodes (incl. constants and PIs and dead nodes).

uint32_t num_cis() const

Returns the number of combinational inputs.

uint32_t num_cos() const

Returns the number of combinational outputs.

uint32_t num_pis() const

Returns the number of primary inputs.

uint32_t num_pos() const

Returns the number of primary outputs.

uint32_t num_gates() const

Returns the number of gates (without dead nodes)

uint32_t num_registers() const

Returns the number of registers.

This number is usually equal to the number of register outputs and register inputs because they have to appear in pairs. During the construction of a network, the number of register outputs and register inputs may diverge.

uint32_t fanin_size(node const &n) const

Returns the fanin size of a node.

uint32_t fanout_size(node const &n) const

Returns the fanout size of a node.

uint32_t incr_fanout_size(node const &n) const

Increments fanout size and returns old value.

This is useful for ref-counting based algorithm. The user of this function should make sure to bring the value back to a consistent state.

uint32_t decr_fanout_size(node const &n) const

Decrements fanout size and returns new value.

This is useful for ref-counting based algorithm. The user of this function should make sure to bring the value back to a consistent state.

uint32_t depth() const

Returns the length of the critical path.

uint32_t level(node const &n) const

Returns the level of a node.

bool is_and(node const &n) const

Returns true if node is a 2-input AND gate.

bool is_or(node const &n) const

Returns true if node is a 2-input OR gate.

bool is_xor(node const &n) const

Returns true if node is a 2-input XOR gate.

bool is_maj(node const &n) const

Returns true if node is a majority-of-3 gate.

bool is_ite(node const &n) const

Returns true if node is a if-then-else gate.

bool is_xor3(node const &n) const

Returns true if node is a 3-input XOR gate.

bool is_function(node const &n) const

Returns true if node is a general function node.

Functional properties

class mockturtle::network

Public Functions

kitty::dynamic_truth_table node_function(node const &n) const

Returns the gate function of a node.

Note that this function returns the gate function represented by a node in terms of the intended gate. For example, in an AIG, all gate functions are AND, complemented edges are not taken into account. Also, in an MIG, all gate functions are MAJ, independently of complemented edges and possible constant inputs.

In order to retreive a function with respect to complemented edges one can use the compute function with a truth table as simulation value.

Nodes and signals

class mockturtle::network

Public Functions

node get_node(signal const &f) const

Get the node a signal is pointing to.

signal make_signal(node const &n) const

Create a signal from a node (without edge attributes).

bool is_complemented(signal const &f) const

Check whether a signal is complemented.

This method may also be provided by network implementations that do not have complemented edges. In this case, the method simply returns false for each node.

uint32_t node_to_index(node const &n) const

Returns the index of a node.

The index of a node must be a unique for each node and must be between 0 (inclusive) and the size of a network (exclusive, value returned by size()).

node index_to_node(uint32_t index) const

Returns the node for an index.

This is the inverse function to node_to_index.

Parameters

index – A value between 0 (inclusive) and the size of the network (exclusive)

node ci_at(uint32_t index) const

Returns the combinational input node for an index.

Parameters

index – A value between 0 (inclusive) and the number of combinational inputs (exclusive).

signal co_at(uint32_t index) const

Returns the combinational output signal for an index.

Parameters

index – A value between 0 (inclusive) and the number of combinational outputs (exclusive).

node pi_at(uint32_t index) const

Returns the primary input node for an index.

Parameters

index – A value between 0 (inclusive) and the number of primary inputs (exclusive).

signal po_at(uint32_t index) const

Returns the primary output signal for an index.

Parameters

index – A value between 0 (inclusive) and the number of primary outputs (exclusive).

node ro_at(uint32_t index) const

Returns the register output node for an index.

Parameters

index – A value between 0 (inclusive) and the number of register outputs (exclusive).

signal ri_at(uint32_t index) const

Returns the register input signal for an index.

Parameters

index – A value between 0 (inclusive) and the number of register inputs (exclusive).

signal ro_to_ri(signal const &s) const

Returns the register input signal to a register output node.

Parameters

signal – A signal of a register output.

node ri_to_ro(node const &n) const

Returns the register output node for a register input signal.

Parameters

signal – A node of a register input.

Node and signal iterators

class mockturtle::network

Public Functions

template<typename Fn>
void foreach_node(Fn &&fn) const

Calls fn on every node in network.

The order of nodes depends on the implementation and must not guarantee topological order. The paramater fn is any callable that must have one of the following four signatures.

  • void(node const&)

  • void(node const&, uint32_t)

  • bool(node const&)

  • bool(node const&, uint32_t)

If fn has two parameters, the second parameter is an index starting from 0 and incremented in every iteration. If fn returns a bool, then it can interrupt the iteration by returning false.

template<typename Fn>
void foreach_pi(Fn &&fn) const

Calls fn on every primary input node in the network.

The order is in the same order as primary inputs have been created with create_pi. The paramater fn is any callable that must have one of the following four signatures.

  • void(node const&)

  • void(node const&, uint32_t)

  • bool(node const&)

  • bool(node const&, uint32_t)

If fn has two parameters, the second parameter is an index starting from 0 and incremented in every iteration. If fn returns a bool, then it can interrupt the iteration by returning false.

template<typename Fn>
void foreach_po(Fn &&fn) const

Calls fn on every primary output signal in the network.

The order is in the same order as primary outputs have been created with create_po. The function is called on the signal that is driving the output and may occur more than once in the iteration, if it drives more than one output. The paramater fn is any callable that must have one of the following four signatures.

  • void(signal const&)

  • void(signal const&, uint32_t)

  • bool(signal const&)

  • bool(signal const&, uint32_t)

If fn has two parameters, the second parameter is an index starting from 0 and incremented in every iteration. If fn returns a bool, then it can interrupt the iteration by returning false.

template<typename Fn>
void foreach_gate(Fn &&fn) const

Calls fn on every gate node in the network.

Calls each node that is not constant and not a primary input. The paramater fn is any callable that must have one of the following four signatures.

  • void(node const&)

  • void(node const&, uint32_t)

  • bool(node const&)

  • bool(node const&, uint32_t)

If fn has two parameters, the second parameter is an index starting from 0 and incremented in every iteration. If fn returns a bool, then it can interrupt the iteration by returning false.

template<typename Fn>
void foreach_register(Fn &&fn) const

Calls fn on every pair of register input signal and register output node in the network.

Calls each pair of a register input signal and the associated register output node. The paramater fn is any callable that must have one of the following four signatures.

  • void(std::pair<signal, node> const&)

  • void(std::pair<signal, node> const&, uint32_t)

  • bool(std::pair<signal, node> const&)

  • bool(std::pair<signal, node> const&, uint32_t)

If fn has two parameters, the second parameter is an index starting from 0 and incremented in every iteration. If fn returns a bool, then it can interrupt the iteration by returning false.

template<typename Fn>
void foreach_fanin(node const &n, Fn &&fn) const

Calls fn on every fanin of a node.

The order of the fanins is in the same order that was used to create the node. The paramater fn is any callable that must have one of the following four signatures.

  • void(signal const&)

  • void(signal const&, uint32_t)

  • bool(signal const&)

  • bool(signal const&, uint32_t)

If fn has two parameters, the second parameter is an index starting from 0 and incremented in every iteration. If fn returns a bool, then it can interrupt the iteration by returning false.

template<typename Fn>
void foreach_fanout(node const &n, Fn &&fn) const

Calls fn on every fanout of a node.

The method gives no guarantee on the order of the fanout. The parameter fn is any callable that must have one of the following signatures.

  • void(node const&)

  • void(node const&, uint32_t)

  • bool(node const&)

  • bool(node const&, uint32_t)

If fn has two parameters, the second parameter is an index starting from 0 and incremented in every iteration. If fn returns a bool, then it can interrupt the iteration by returning false.

Simulate values

class mockturtle::network

Public Functions

template<typename Iterator>
iterates_over_t<Iterator, T> compute(node const &n, Iterator begin, Iterator end) const

Simulates arbitrary value on a node.

This is a generic simulation method that can be implemented multiple times for a network interface for different types. One only needs to change the implementation and change the value for the type parameter T, which indicates the element type of the iterators.

Examples for simulation types are bool, kitty::dynamic_truth_table, bit masks, or BDDs.

The begin and end iterator point to values which are assumed to be assigned to the fanin of the node. Consequently, the distance from begin to end must equal the fanin size of the node.

Parameters
  • n – Node to simulate (used to retrieve the node function)

  • begin – Begin iterator to simulation values of fanin

  • end – End iterator to simulation values of fanin

Returns

Returns computed simulation value of type T

Mapping

The following methods are used to represent a mapping that is annotated to a subject graph. The interface can, e.g., be used for LUT mapping or standard cell mapping. For a common terminology, we call a collection of nodes that belong to the same unit a cell, which has a single root. The mapped node is the cell root. A cell root, and therefore the cell it represents, may be assigned a function by means of a truth table.

Note

If a network implements has_mapping it also needs to implement all other mapping methods, except cell_function and set_cell_function, which are optional but must be implemented both if one is present.

class mockturtle::network

Public Functions

bool has_mapping() const

Returns true, if network has a mapping.

bool is_cell_root(node const &n) const

Returns true, if node is the root of a mapped cell.

void clear_mapping()

Clears a mapping.

uint32_t num_cells() const

Number of cells, i.e, mapped nodes.

template<typename LeavesIterator>
void add_to_mapping(node const &n, LeavesIterator begin, LeavesIterator end)

Adds a node to the mapping.

void remove_from_mapping(node const &n)

Remove from mapping.

kitty::dynamic_truth_table cell_function(node const &n)

Gets function of the cell.

The parameter n is a node that must be a cell root.

void set_cell_function(node const &n, kitty::dynamic_truth_table const &function)

Sets cell function.

The parameter n is a node that must be a cell root.

template<typename Fn>
void foreach_cell_fanin(node const &n, Fn &&fn) const

Iterators over cell’s fan-ins. The parameter n is a node that must be a cell root. The paramater fn is any callable that must have one of the following four signatures.

  • void(node const&)

  • void(node const&, uint32_t)

  • bool(node const&)

  • bool(node const&, uint32_t)

Custom node values

Each node can be assigned a value, which is a 32-bit unsigned integer. The default value is 0. Note that all value-functions are constant, because a change to the values is considered transparent to the network. If a caller passes a constant network to an algorithm, the algorithm may change the values but cannot change the structure of the network or any other visible property.

Warning

Values are meant to use internally in the implementation of an algorithm. Users of these utility function should make sure not to call other algorithms that may overwrite the values. Exclusive access to temporary storage can only be guaranteed by using custom containers.

class mockturtle::network

Public Functions

void clear_values() const

Reset all values to 0.

uint32_t value(node const &n) const

Returns value of a node.

void set_value(node const &n, uint32_t value) const

Sets value of a node.

uint32_t incr_value(node const &n) const

Increments value of a node and returns previous value.

uint32_t decr_value(node const &n) const

Decrements value of a node and returns new value.

Visited flags

Visited flags are similar to custom node values, but are used for the specific purpose of checking whether a node was visited in traversing algorithms. Again, all visited-functions are constant, because a change to the visited flags is considered transparent to the network. If a caller passes a constant network to an algorithm, the algorithm may change the visited flags but cannot change the structure of the network or any other visible property. The use of traversal ids helps to use unique visited flags in multiple depending contexts.

class mockturtle::network

Public Functions

void clear_visited() const

Reset all visited values to 0.

uint32_t visited(node const &n) const

Returns the visited value of a node.

void set_visited(node const &n, uint32_t v) const

Sets the visited value of a node.

uint32_t trav_id() const

Returns the current traversal id.

void incr_trav_id() const

Increment the current traversal id.

General methods

class mockturtle::network

Public Functions

network_events<base_type> &events() const

Returns network events object.

Clients can register callbacks for network events to this object. Events include adding nodes, modifying nodes, and deleting nodes.