Gate-level Layout

The gate-level layout can be layered on top of any clocked layout type at compile time to extend its functionality by a notion of gates that can be assigned to its clock zones. Each gate is identified as a Boolean function. Thereby, this layout type is technology-independent and does not have any concrete implementation, structures, or shapes assigned to its gates. Even the sizes of the clock zones (tiles) are not determined. Consequently, this layout type is best suited for logic-level placement and routing and can be considered fiction‘s most important core data type.

The gate-level layout is implemented in accordance with mockturtle‘s network interface API. Thus, it is itself a mockturtle network that can be passed to various of mockturtle’s algorithms. However, since each logic node (gate) in the layout has to have a concrete position assigned, mockturtle cannot be used to generate valid layouts.

Header: fiction/layouts/gate_level_layout.hpp

template<typename ClockedLayout>
class gate_level_layout : public ClockedLayout

A layout type to layer on top of a clocked layout that allows the assignment of gates to clock zones (aka tiles in this context). This class represents a gate-level FCN layout and, thus, adds a notion of Boolean logic. The gate_level_layout class fulfills the requirements of a mockturtle logic network so that it can be used in many of mockturtle’s algorithms. Since a layout has to assign fixed positions to its gates (logic nodes), most generative member functions like create_pi, create_po, create_and, etc. require additional coordinate parameters. Consequently, mockturtle’s algorithms cannot be used to generate gate_level_layout networks. To make the class compliant with the API anyways, these member functions have their parameters defaulted but they are, in fact required to create meaningful layouts.

The following notion is utilized in this implementation:

  • a node n is an index representing the nth created gate. All properties of said gate, e.g., its type and position, are stored independently and can be requested from the layout. An empty layout has 2 nodes, namely const0 and const1 as required by mockturtle. At the moment, they are not used for anything meaningful but could be.

  • a signal is an unsigned integer representation of a tile, i.e., a coordinate in the layout. It can be seen as a pointer to a position. Consequently, the utilized coordinates need to be convertible to uint64_t.

  • the creation of PIs and POs creates nodes (the latter in contrast to other mockturtle networks) that have a position on the layout.

  • the creation of buffers (create_buf) creates nodes as well. A buffer with more than one output is a fanout such that is_fanout will return true on it. However, it is also still a buffer (is_buf returns true as well). Buffers and wires are used interchangeably.

  • each node has an associated gate function. PIs, POs, and buffers compute the identity function.

  • signals (pointers to tiles) cannot be inverting. Thereby, inverter nodes (gates) have to be created that can be checked for via is_inv.

  • each create_... function requires a tile parameter that determines its placement. If the provided tile is dead, the location will not be stored and the node will not count towards number of gates or wires.

  • a node can be overwritten by creating another node on its location. This can, however, lead to unwanted effects and should be avoided.

  • nodes can be moved via the move_node function. This function can also be used to update their children, i.e., incoming signals.

Most implementation details regarding mockturtle-specific functions are borrowed from mockturtle/networks/klut.hpp. Therefore, mockturtle API functions are only sporadically documented where their behavior might differ. Information on their functionality can be found in mockturtle’s docs.

Template Parameters:

ClockedLayout – The clocked layout that is to be extended by gate functions.

Public Types

using gate_level_layout_storage = mockturtle::storage<gate_level_layout_storage_node, gate_level_layout_storage_data<node, signal>>

tile-based layout storage container

Public Functions

inline explicit gate_level_layout(const typename ClockedLayout::aspect_ratio &ar = {}, const std::string &name = {})

Standard constructor. Creates a named gate-level layout of the given aspect ratio. To this end, it calls ClockedLayout’s standard constructor.

Parameters:

  • ar – Highest possible position in the layout.

  • name – Layout name.

inline gate_level_layout(const typename ClockedLayout::aspect_ratio &ar, const clocking_scheme<tile> &scheme, const std::string &name = {})

Standard constructor. Creates a gate-level layout of the given aspect ratio and clocks it via the given clocking scheme. To this end, it calls ClockedLayout’s standard constructor.

Parameters:

  • ar – Highest possible position in the layout.

  • scheme – Clocking scheme to apply to this layout.

  • name – Layout name.

inline explicit gate_level_layout(storage s)

Copy constructor from another layout’s storage.

Parameters:

s – Storage of another gate_level_layout.

inline gate_level_layout(storage s, event_storage e)

Copy constructor from another layout’s storage.

Parameters:
inline explicit gate_level_layout(const ClockedLayout &lyt)

Copy constructor from another ClockedLayout.

Parameters:

lyt – Clocked layout.

inline gate_level_layout clone() const noexcept

Clones the layout returning a deep copy.

Returns:

Deep copy of the layout.

inline bool is_pi_tile(const tile &t) const noexcept

Check whether tile t hosts a primary input.

Parameters:

t – Tile to be checked.

Returns:

true iff the node located at tile t is a PI.

inline bool is_po_tile(const tile &t) const noexcept

Check whether tile t hosts a primary output.

Parameters:

t – Tile to be checked.

Returns:

true iff the node located at tile t is a PO.

inline auto size() const noexcept

Does NOT return the layout dimensions but the number of nodes (including constants and dead ones) in accordance with the mockturtle API.

Returns:

Number of all nodes.

inline auto num_gates() const noexcept

Returns the number of placed nodes in the layout that do not compute the identity function.

Returns:

Number of gates in the layout.

inline auto num_wires() const noexcept

Returns the number of placed nodes in the layout that compute the identity function including PIs and POs.

Returns:

Number of wires in the layout.

inline auto num_crossings() const noexcept

Returns the number of placed nodes in the layout that compute the identity function and cross other nodes.

Returns:

Number of crossings in the layout.

inline bool is_empty() const noexcept

Checks whether there are no gates or wires assigned to the layout’s coordinates.

Returns:

true iff the layout is empty.

template<bool RespectClocking = true>
inline auto fanin_size(const node n) const

Returns the number of incoming, adjacently placed, and properly clocked signals to the given node.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanins.

Parameters:

n – Node to check.

Returns:

Number of fanins to n.

template<bool RespectClocking = true>
inline auto fanout_size(const node n) const

Returns the number of outgoing, adjacently placed, and properly clocked signals of the given node.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanouts.

Parameters:

n – Node to check.

Returns:

Number of fanouts to n.

inline node get_node(const signal &s) const noexcept

Fetches the node that is placed onto a tile pointed to by a given signal. If no node is placed there, the const0 node is returned.

Parameters:

s – Pointer to a tile.

Returns:

Node at position t where s points at t; or 0 if no node is placed at t.

inline node get_node(const tile &t) const noexcept

Fetches the node that is placed onto the provided tile If no node is placed there, the const0 node is returned.

Parameters:

t – Tile in the layout.

Returns:

Node at position t; or 0 if no node is placed at t.

inline tile get_tile(const node n) const noexcept

The inverse function of get_node. Fetches the tile that the provided node is placed on. Returns a default dead tile if the node is not placed.

Parameters:

n – Node whose location is desired.

Returns:

Tile at which n is placed or a default dead tile if n is not placed.

inline bool is_dead(const node n) const noexcept

Checks whether a node (not its assigned tile) is dead. Nodes can be dead for a variety of reasons. For instance if they are dangling (see the mockturtle API). In this layout type, nodes are also marked dead when they are not assigned to a tile (which is considered equivalent to dangling).

Parameters:

n – Node to check for liveliness.

Returns:

true iff n is dead.

inline signal make_signal(const node n) const noexcept

Invokes the same behavior as get_tile(n) but additionally casts the return value to a signal. That is, this function returns the signal representation of the tile that the node n is assigned to.

Parameters:

n – Node whose signal is desired.

Returns:

Signal that points to n.

inline signal move_node(const node n, const tile &t, const std::vector<signal> &new_children = {}) noexcept

Moves a given node to a new position and also updates its children, i.e., incoming signals.

Parameters:

  • n – Node to move.

  • t – Tile to move n to.

  • new_children – New incoming signals to n.

Returns:

Signal pointing to n’s new tile.

inline signal connect(const signal &s, const node n) noexcept

Connects the given signal s to the given node n as a child. The new child s is appended at the end of n’s list of children. Thus, if the order of children is important, move_node() should be used instead. Otherwise, this function has a smaller overhead and is to be preferred.

Parameters:

  • s – New incoming signal to n.

  • n – Node that should add s as its child.

Returns:

Signal pointing to n.

inline void clear_tile(const tile &t) noexcept

Removes all assigned nodes from the given tile and marks them as dead.

Note

This function does not reduce the number of nodes in the layout nor does it reduce the number of PIs that are being returned via num_pis() even if the tile to clear is an input tile. However, the number of POs is reduced if the tile to clear is an output tile. While this seems counter-intuitive and inconsistent, it is in line with mockturtle’s understanding of nodes and primary outputs.

Parameters:

t – Tile whose nodes are to be removed.

inline bool is_complemented(const signal &s) const noexcept

Necessary function in the mockturtle API. However, in this layout type, signals cannot be complemented.

Parameters:

s – Signal to check.

Returns:

false.

inline bool is_gate(const node n) const noexcept

Returns whether a given node is a gate in accordance with mockturtle’s definition, i.e., whether it not a constant and not a PI. Thereby, any wire/buffer (including POs) is a gate if this function is used to check for it. This poses an inconsistency but is required to comply with certain mockturtle algorithms.

Parameters:

n – Node to check.

Returns:

true iff n is neither a constant nor a PI.

inline bool is_buf(const node n) const noexcept

Returns whether n computes the identity function.

Parameters:

n – Node to check.

Returns:

true iff n computes the identity.

inline bool is_wire(const node n) const noexcept

Equivalent to is_buf.

inline bool is_inv(const node n) const noexcept

Returns whether n computes the binary inversion (NOT gate).

Parameters:

n – Node to check.

Returns:

true iff n is a NOT gate.

inline bool is_fanout(const node n) const noexcept

Returns whether n is a wire and has multiple outputs, thereby, acting as a fanout gate. Note that a fanout will return true for both is_wire and is_fanout.

Parameters:

n – Node to check.

Returns:

true iff n is a fanout gate.

inline bool is_function(const node n) const

Returns whether node n computes a function. That is, this function returns true iff n is not a constant.

Parameters:

n – Node to check.

Returns:

true iff n is not a constant.

inline bool is_gate_tile(const tile &t) const noexcept

Returns whether the node assigned to t fulfills is_gate (in accordance with mockturtle’s definition of gates).

Parameters:

t – Tile to check.

Returns:

true iff t hosts a node that is a neither a constant nor a PI.

inline bool is_wire_tile(const tile &t) const noexcept

Returns whether the node assigned to t fulfills is_wire.

Parameters:

t – Tile to check.

Returns:

true iff t hosts a node that computes the identity.

inline bool is_empty_tile(const tile &t) const noexcept

Returns whether t does not have a node assigned to it.

Parameters:

t – Tile to check.

Returns:

true iff t is an empty tile.

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

Applies a function to all primary input nodes (including dead ones) in the layout.

Template Parameters:

Fn – Functor type that has to comply with the restrictions imposed by mockturtle::foreach_element_transform.

Parameters:

fn – Functor to apply to each primary input node.

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

Applies a function to all primary output signals (including those that point to dead nodes) in the layout. Note the difference to foreach_pi in the signature of fn. This function applies to all POs as signals whereas foreach_pi applies to all PIs as nodes. This is with respect to mockturtle’s API.

Template Parameters:

Fn – Functor type that has to comply with the restrictions imposed by mockturtle::foreach_element_transform.

Parameters:

fn – Functor to apply to each primary output signal.

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

Applies a function to all nodes (excluding dead ones) in the layout.

Template Parameters:

Fn – Functor type that has to comply with the restrictions imposed by mockturtle::foreach_element_if.

Parameters:

fn – Functor to apply to each node that is not dead.

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

Applies a function to all gates (excluding dead ones) in the layout. Uses is_gate to check whether a node is a gate.

Template Parameters:

Fn – Functor type that has to comply with the restrictions imposed by mockturtle::foreach_element_if.

Parameters:

fn – Functor to apply to each gate that is not dead.

template<typename Fn>
inline void foreach_wire(Fn &&fn) const

Applies a function to all wires (excluding dead ones) in the layout. Uses is_wire to check whether a node is a wire.

Template Parameters:

Fn – Functor type that has to comply with the restrictions imposed by mockturtle::foreach_element_if.

Parameters:

fn – Functor to apply to each wire that is not dead.

template<typename Fn, bool RespectClocking = true>
inline void foreach_fanin(const node n, Fn &&fn) const

Applies a function to all nodes that are incoming to a given one. Thereby, only incoming clocked zones (+/- one layer to include crossings) are being considered whose data flow connections are respectively established. That is, the given function is applied to all nodes that are connected to the one assigned to t as fanins on neighboring tiles.

Template Parameters:

  • Fn – Functor type that has to comply with the restrictions imposed by mockturtle::foreach_element_transform.

  • RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanins.

Parameters:

  • n – Node whose fanins are desired.

  • fn – Functor to apply to each of n’s fanins.

template<bool RespectClocking = true>
inline auto incoming_data_flow(const tile &t) const noexcept

Returns a container that contains all tiles that feed information to the given one. Thereby, only incoming clocked zones (+/- one layer to include crossings) are being considered whose data flow connections are respectively established. That is, the returned container contains all tiles that host nodes that are connected to the one assigned to t as fanins.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanins.

Parameters:

t – Tile whose incoming data flow ones are desired.

Returns:

A container that contains all of t’s incoming data flow tiles.

template<typename Fn, bool RespectClocking = true>
inline void foreach_fanout(const node n, Fn &&fn) const

Applies a function to all nodes that are outgoing from a given one. Thereby, only outgoing clocked zones (+/- one layer to include crossings) are being considered whose data flow connections are respectively established. That is, the given function is applied to all nodes that are connected to the one assigned to t as fanouts on neighboring tiles.

Template Parameters:

  • Fn – Functor type that has to comply with the restrictions imposed by mockturtle::foreach_element_transform.

  • RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanouts.

Parameters:

  • n – Node whose fanouts are desired.

  • fn – Functor to apply to each of n’s fanouts.

template<bool RespectClocking = true>
inline auto outgoing_data_flow(const tile &t) const noexcept

Returns a container that contains all tiles that accept information from the given one. Thereby, only outgoing clocked zones (+/- one layer to include crossings) are being considered whose data flow connections are respectively established. That is, the returned container contains all tiles that host nodes that are connected to the one assigned to t as fanouts.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanouts.

Parameters:

t – Tile whose outgoing data flow ones are desired.

Returns:

A container that contains all of t’s outgoing data flow tiles.

template<bool RespectClocking = true>
inline bool is_incoming_signal(const tile &t, const signal &s) const noexcept

Checks whether signal s is incoming to tile t. That is, whether tile t hosts a node that has a fanin assigned to the tile that signal s points to.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanins.

Parameters:

  • t – Base tile.

  • s – Signal pointing to a potential incoming tile to t.

Returns:

true iff s is incoming to t.

template<bool RespectClocking = true>
inline bool has_northern_incoming_signal(const tile &t) const noexcept

Checks whether the given tile has an incoming one in northern direction.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanins.

Parameters:

t – Base tile.

Returns:

true iff north(t) is incoming to t.

template<bool RespectClocking = true>
inline bool has_north_eastern_incoming_signal(const tile &t) const noexcept

Checks whether the given tile has an incoming one in north-eastern direction.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanins.

Parameters:

t – Base tile.

Returns:

true iff north_east(t) is incoming to t.

template<bool RespectClocking = true>
inline bool has_eastern_incoming_signal(const tile &t) const noexcept

Checks whether the given tile has an incoming one in eastern direction.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanins.

Parameters:

t – Base tile.

Returns:

true iff east(t) is incoming to t.

template<bool RespectClocking = true>
inline bool has_south_eastern_incoming_signal(const tile &t) const noexcept

Checks whether the given tile has an incoming one in south-eastern direction.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanins.

Parameters:

t – Base tile.

Returns:

true iff south_east(t) is incoming to t.

template<bool RespectClocking = true>
inline bool has_southern_incoming_signal(const tile &t) const noexcept

Checks whether the given tile has an incoming one in southern direction.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanins.

Parameters:

t – Base tile.

Returns:

true iff south(t) is incoming to t.

template<bool RespectClocking = true>
inline bool has_south_western_incoming_signal(const tile &t) const noexcept

Checks whether the given tile has an incoming one in south-western direction.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanins.

Parameters:

t – Base tile.

Returns:

true iff south_west(t) is incoming to t.

template<bool RespectClocking = true>
inline bool has_western_incoming_signal(const tile &t) const noexcept

Checks whether the given tile has an incoming one in western direction.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanins.

Parameters:

t – Base tile.

Returns:

true iff west(t) is incoming to t.

template<bool RespectClocking = true>
inline bool has_north_western_incoming_signal(const tile &t) const noexcept

Checks whether the given tile has an incoming one in north-western direction.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanins.

Parameters:

t – Base tile.

Returns:

true iff north_west(t) is incoming to t.

template<bool RespectClocking = true>
inline bool has_no_incoming_signal(const tile &t) const noexcept

Checks whether the given tile has no incoming tiles.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanins.

Parameters:

t – Base tile.

Returns:

true iff t does not have incoming tiles.

template<bool RespectClocking = true>
inline bool is_outgoing_signal(const tile &t, const signal &s) const noexcept

Checks whether signal s is outgoing from tile t. That is, whether tile t hosts a node that has a fanout assigned to the tile that signal s points to.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanouts.

Parameters:

  • t – Base tile.

  • s – Signal pointing to a potential outgoing tile of t.

Returns:

true iff s is outgoing from t.

template<bool RespectClocking = true>
inline bool has_northern_outgoing_signal(const tile &t) const noexcept

Checks whether the given tile has an outgoing one in northern direction.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanouts.

Parameters:

t – Base tile.

Returns:

true iff north(t) is outgoing from t.

template<bool RespectClocking = true>
inline bool has_north_eastern_outgoing_signal(const tile &t) const noexcept

Checks whether the given tile has an outgoing one in north-eastern direction.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanouts.

Parameters:

t – Base tile.

Returns:

true iff north_east(t) is outgoing from t.

template<bool RespectClocking = true>
inline bool has_eastern_outgoing_signal(const tile &t) const noexcept

Checks whether the given tile has an outgoing one in eastern direction.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanouts.

Parameters:

t – Base tile.

Returns:

true iff east(t) is outgoing from t.

template<bool RespectClocking = true>
inline bool has_south_eastern_outgoing_signal(const tile &t) const noexcept

Checks whether the given tile has an outgoing one in south-eastern direction.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanouts.

Parameters:

t – Base tile.

Returns:

true iff south_east(t) is outgoing from t.

template<bool RespectClocking = true>
inline bool has_southern_outgoing_signal(const tile &t) const noexcept

Checks whether the given tile has an outgoing one in southern direction.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanouts.

Parameters:

t – Base tile.

Returns:

true iff south(t) is outgoing from t.

template<bool RespectClocking = true>
inline bool has_south_western_outgoing_signal(const tile &t) const noexcept

Checks whether the given tile has an outgoing one in south-western direction.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanouts.

Parameters:

t – Base tile.

Returns:

true iff south_west(t) is outgoing from t.

template<bool RespectClocking = true>
inline bool has_western_outgoing_signal(const tile &t) const noexcept

Checks whether the given tile has an outgoing one in western direction.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanouts.

Parameters:

t – Base tile.

Returns:

true iff west(t) is outgoing from t.

template<bool RespectClocking = true>
inline bool has_north_western_outgoing_signal(const tile &t) const noexcept

Checks whether the given tile has an outgoing one in north-western direction.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanouts.

Parameters:

t – Base tile.

Returns:

true iff north_west(t) is outgoing from t.

template<bool RespectClocking = true>
inline bool has_no_outgoing_signal(const tile &t) const noexcept

Checks whether the given tile has no outgoing tiles.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanouts.

Parameters:

t – Base tile.

Returns:

true iff t does not have outgoing tiles.

template<bool RespectClocking = true>
inline bool has_opposite_incoming_and_outgoing_signals(const tile &t) const noexcept

Checks whether the given tile t has its incoming and outgoing signals on opposite sides of the tile. For this purpose, the function relies on foreach_adjacent_opposite_coordinates of the underlying ClockedLayout.

This function is very helpful for many gate libraries to check for (non-)straight gates, which might look different.

Template Parameters:

RespectClocking – Flag to indicate that the underlying clocking is to be respected when evaluating fanins and fanouts.

Parameters:

t – Base tile.

Returns:

true iff t has incoming and outgoing signals on opposite sides.

template<typename Node, typename Tile>
struct gate_level_layout_storage_data
struct gate_level_layout_storage_node : public mockturtle::mixed_fanin_node<2>

gate-level layout node

data[0].h1: Internal (data-flow independent) fan-out size (MSB indicates dead nodes) data[0].h2: Application-specific value data[1].h1: Function literal in truth table cache data[2].h2: Visited flags