Netlists

Netlist

Overview

The netlist logically consists of several different components: Blocks, Ports, Pins and Nets Each component in the netlist has a unique template identifier (BlockId, PortId, PinId, NetId) used to retrieve information about it. In this implementation these ID’s are unique throughout the netlist (i.e. every port in the netlist has a unique ID, even if the ports share a common type).

Block

A Block is the primitive netlist element (a node in the netlist hyper-graph). Blocks have various attributes (a name, a type etc.) and are associated with sets of input/output/clock ports.

Block related information can be retrieved using the block_*() member functions.

Pins

Pins define single-bit connections between a block and a net.

Pin related information can be retrieved using the pin_*() member functions.

Nets

Nets represent the connections between blocks (the edges of the netlist hyper-graph). Each net has a single driver pin, and a set of sink pins.

Net related information can be retrieved using the net_*() member functions.

Ports

A Port is a (potentially multi-bit) group of pins.

For example, the two operands and output of an N-bit adder would logically be grouped as three ports. Ports have a specified bit-width which defines how many pins form the port.

Port related information can be retrieved using the port_*() member functions.

Usage

The following provides usage examples for common use-cases.

Walking the netlist

To iterate over the whole netlist use the blocks() and/or nets() member functions:

 Netlist netlist;

 //... initialize the netlist

 //Iterate over all the blocks
 for(BlockId blk_id : netlist.blocks()) {
     //Do something with each block
 }


 //Iterate over all the nets
 for(NetId net_id : netlist.nets()) {
     //Do something with each net
 }
To retrieve information about a netlist component call one of the associated member functions:
 //Print out each block's name
 for(BlockId blk_id : netlist.blocks()) {

     //Get the block name
     const std::string& block_name = netlist.block_name(blk_id);

     //Print it
     printf("Block: %s\n", block_name.c_str());
 }
Note that the member functions are associated with the type of component (e.g. block_name() yields the name of a block, net_name() yields the name of a net).

Tracing cross-references

It is common to need to trace the netlist connectivity. The Netlist allows this to be done efficiently by maintaining cross-references between the various netlist components.

The following diagram shows the main methods and relationships between netlist components:

           +---------+      pin_block()
           |         |<--------------------------+
           |  Block  |                           |
           |         |-----------------------+   |
           +---------+      block_pins()     |   |
              |   ^                          v   |
              |   |                       +---------+  net_pins()  +---------+
              |   |                       |         |<-------------|         |
block_ports() |   | port_block()          |   Pin   |              |   Net   |
              |   |                       |         |------------->|         |
              |   |                       +---------+  pin_net()   +---------+
              v   |                          ^   |
           +---------+      port_pins()      |   |
           |         |-----------------------+   |
           |  Port   |                           |
           |         |<--------------------------+
           +---------+      pin_port()

Note that methods which are plurals (e.g. net_pins()) return multiple components.

As an example consider the case where we wish to find all the blocks associated with a particular net:

 NetId net_id;

 //... Initialize net_id with the net of interest

 //Iterate through each pin on the net to get the associated port
 for(PinId pin_id : netlist.net_pins(net_id)) {

     //Get the port associated with the pin
     PortId port_id = netlist.pin_port(pin_id);

     //Get the block associated with the port
     BlockId blk_id = netlist.port_block(port_id);

     //Print out the block name
     const std::string& block_name = netlist.block_name(blk_id);
     printf("Associated block: %s\n", block_name.c_str());
 }
Netlist also defines some convenience functions for common operations to avoid tracking the intermediate IDs if they are not needed. The following produces the same result as above:
 NetId net_id;

 //... Initialize net_id with the net of interest

 //Iterate through each pin on the net to get the associated port
 for(PinId pin_id : netlist.net_pins(net_id)) {

     //Get the block associated with the pin (bypassing the port)
     BlockId blk_id = netlist.pin_block(pin_id);

     //Print out the block name
     const std::string& block_name = netlist.block_name(blk_id);
     printf("Associated block: %s\n", block_name.c_str());
 }

As another example, consider the inverse problem of identifying the nets connected as inputs to a particular block:

 BlkId blk_id;

 //... Initialize blk_id with the block of interest

 //Iterate through the ports
 for(PortId port_id : netlist.block_input_ports(blk_id)) {

     //Iterate through the pins
     for(PinId pin_id : netlist.port_pins(port_id)) {
         //Retrieve the net
         NetId net_id = netlist.pin_net(pin_id);

         //Get its name
         const std::string& net_name = netlist.net_name(net_id);
         printf("Associated net: %s\n", net_name.c_str());
     }
 }
Here we used the block_input_ports() method which returned an iterable range of all the input ports associated with blk_id. We then used the port_pins() method to get iterable ranges of all the pins associated with each port, from which we can find the associated net.

Often port information is not relevant so this can be further simplified by iterating over a block’s pins directly (e.g. by calling one of the block_*_pins() functions):

 BlkId blk_id;

 //... Initialize blk_id with the block of interest

 //Iterate over the blocks ports directly
 for(PinId pin_id : netlist.block_input_pins(blk_id)) {

     //Retrieve the net
     NetId net_id = netlist.pin_net(pin_id);

     //Get its name
     const std::string& net_name = netlist.net_name(net_id);
     printf("Associated net: %s\n", net_name.c_str());
 }
Note the use of range-based-for loops in the above examples; it could also have written (more verbosely) using a conventional for loop and explicit iterators as follows:
 BlkId blk_id;

 //... Initialize blk_id with the block of interest

 //Iterate over the blocks ports directly
 auto pins = netlist.block_input_pins(blk_id);
 for(auto pin_iter = pins.begin(); pin_iter != pins.end(); ++pin_iter) {

     //Retrieve the net
     NetId net_id = netlist.pin_net(*pin_iter);

     //Get its name
     const std::string& net_name = netlist.net_name(net_id);
     printf("Associated net: %s\n", net_name.c_str());
 }

Creating the netlist

The netlist can be created by using the create_*() member functions to create individual Blocks/Ports/Pins/Nets.

For instance to create the following netlist (where each block is the same type, and has an input port ‘A’ and output port ‘B’):

 -----------        net1         -----------
 | block_1 |-------------------->| block_2 |
 -----------          |          -----------
                      |
                      |          -----------
                      ---------->| block_3 |
                                 -----------
We could do the following:
 const t_model* blk_model = .... //Initialize the block model appropriately

 Netlist netlist("my_netlist"); //Initialize the netlist with name 'my_netlist'

 //Create the first block
 BlockId blk1 = netlist.create_block("block_1", blk_model);

 //Create the first block's output port
 //  Note that the input/output/clock type of the port is determined
 //  automatically from the block model
 PortId blk1_out = netlist.create_port(blk1, "B");

 //Create the net
 NetId net1 = netlist.create_net("net1");

 //Associate the net with blk1
 netlist.create_pin(blk1_out, 0, net1, PinType::DRIVER);

 //Create block 2 and hook it up to net1
 BlockId blk2 = netlist.create_block("block_2", blk_model);
 PortId blk2_in = netlist.create_port(blk2, "A");
 netlist.create_pin(blk2_in, 0, net1, PinType::SINK);

 //Create block 3 and hook it up to net1
 BlockId blk3 = netlist.create_block("block_3", blk_model);
 PortId blk3_in = netlist.create_port(blk3, "A");
 netlist.create_pin(blk3_in, 0, net1, PinType::SINK);

Modifying the netlist

The netlist can also be modified by using the remove_*() member functions. If we wanted to remove block_3 from the netlist creation example above we could do the following:

 //Mark blk3 and any references to it invalid
 netlist.remove_block(blk3);

 //Compress the netlist to actually remove the data associated with blk3
 // NOTE: This will invalidate all client held IDs (e.g. blk1, blk1_out, net1, blk2, blk2_in)
 netlist.compress();
The resulting netlist connectivity now looks like:
 -----------        net1         -----------
 | block_1 |-------------------->| block_2 |
 -----------                     -----------
Note that until compress() is called any ‘removed’ elements will have invalid IDs (e.g. BlockId::INVALID()). As a result after calling remove_block() (which invalidates blk3) we then called compress() to remove the invalid IDs.

Also note that compress() is relatively slow. As a result avoid calling compress() after every call to a remove_*() function, and instead batch up calls to remove_*() and call compress() only after a set of modifications have been applied.

Verifying the netlist

Particularly after construction and/or modification it is a good idea to check that the netlist is in a valid and consistent state. This can be done with the verify() member function:

 netlist.verify()
If the netlist is not valid verify() will throw an exception, otherwise it returns true.

Invariants

The Netlist maintains stronger invariants if the netlist is in compressed form.

Netlist is compressed (‘not dirty’)

If the netlist is compressed (i.e. !is_dirty(), meaning there have been NO calls to remove_*() since the last call to compress()) the following invariant will hold:

  • Any range returned will contain only valid IDs

In practise this means the following conditions hold:

  • Blocks will not contain empty ports/pins (e.g. ports with no pin/net connections)

  • Ports will not contain pins with no associated net

  • Nets will not contain invalid sink pins

This means that no error checking for invalid IDs is needed if simply iterating through netlist (see below for some exceptions).

NOTE: you may still encounter invalid IDs in the following cases:

  • net_driver() will return an invalid ID if the net is undriven

  • port_pin()/port_net() will return an invalid ID if the bit index corresponds to an unconnected pin

Netlist is NOT compressed (‘dirty’)

If the netlist is not compressed (i.e. is_dirty(), meaning there have been calls to remove_*() with no subsequent calls to compress()) then the invariant above does not hold.

Any range may return invalid IDs. In practise this means,

  • Blocks may contain invalid ports/pins

  • Ports may contain invalid pins

  • Pins may not have a valid associated net

  • Nets may contain invalid sink pins

Implementation Details

The netlist is stored in Struct-of-Arrays format rather than the more conventional Array-of-Structs. This improves cache locality by keeping component attributes of the same type in contiguous memory. This prevents unneeded member data from being pulled into the cache (since most code accesses only a few attributes at a time this tends to be more efficient).

Clients of this class pass nearly-opaque IDs (BlockId, PortId, PinId, NetId, StringId) to retrieve information. The ID is internally converted to an index to retrieve the required value from it’s associated storage.

By using nearly-opaque IDs we can change the underlying data layout as need to optimize performance/memory, without disrupting client code.

Strings

To minimize memory usage, we store each unique string only once in the netlist and give it a unique ID (StringId). Any references to this string then make use of the StringId.

In particular this prevents the (potentially large) strings from begin duplicated multiple times in various look-ups, instead the more space efficient StringId is duplicated.

Note that StringId is an internal implementation detail and should not be exposed as part of the public interface. Any public functions should take and return std::string’s instead.

Block pins/Block ports data layout

The pins/ports for each block are stored in a similar manner, for brevity we describe only pins here.

The pins for each block (i.e. PinId’s) are stored in a single vector for each block (the block_pins_ member). This allows us to iterate over all pins (i.e. block_pins()), or specific subsets of pins (e.g. only inputs with block_input_pins()).

To accomplish this all pins of the same group (input/output/clock) are located next to each other. An example is shown below, where the block has n input pins, m output pins and k clock pins.

 -------------------------------------------------------------------------------------------------------------------
 | ipin_1 | ipin_2 | ... | ipin_n | opin_1 | opin_2 | ... | opin_m | clock_pin_1 | clock_pin_2 | ... | clock_pin_k |
 -------------------------------------------------------------------------------------------------------------------
 ^                                ^                                ^                                               ^
 |                                |                                |                                               |
begin                         opin_begin                    clock_pin_begin                                       end

Provided we know the internal dividing points (i.e. opin_begin and clock_pin_begin) we can easily build the various ranges of interest:

 all pins   : [begin, end)
 input pins : [begin, opin_begin)
 output pins: [opin_begin, clock_pin_begin)
 clock pins : [clock_pin_begin, end)
Since any reallocation would invalidate any iterators to these internal dividers, we separately store the number of input/output/clock pins per block (i.e. in block_num_input_pins_, block_num_output_pins_ and block_num_clock_pins_). The internal dividers can then be easily calculated (e.g. see block_output_pins()), even if new pins are inserted (provided the counts are updated).

Adding data to the netlist

The Netlist should contain only information directly related to the netlist state (i.e. netlist connectivity). Various mappings to/from elements (e.g. what CLB contains an atom block), and algorithmic state (e.g. if a net is routed) do NOT constitute netlist state and should NOT be stored here.

Such implementation state should be stored in other data structures (which may reference the Netlist’s IDs).

The netlist state should be immutable (i.e. read-only) for most of the CAD flow.

Interactions with other netlists

Currently, the AtomNetlist and ClusteredNetlist are both derived from Netlist. The AtomNetlist has primitive specific details (t_model, TruthTable), and handles all operations with the atoms. The ClusteredNetlist contains information on the CLB (Clustered Logic Block) level, which includes the physical description of the blocks (t_logical_block_type), as well as the internal hierarchy and wiring (t_pb/t_pb_route).

The calling-conventions of the functions in the AtomNetlist and ClusteredNetlist is as follows:

Functions where the derived class (Atom/Clustered) calls the base class (Netlist) create_*()

Functions where the base class calls the derived class (Non-Virtual Interface idiom as described https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Non-Virtual_Interface) remove_*() clean_*() validate_*_sizes() shrink_to_fit() The derived functions based off of the virtual functions have suffix *_impl()

template<typename BlockId = ParentBlockId, typename PortId = ParentPortId, typename PinId = ParentPinId, typename NetId = ParentNetId>
class Netlist

Public Functions

const std::string &netlist_name() const

Retrieve the name of the netlist.

const std::string &netlist_id() const

Retrieve the unique identifier for this netlist This is typically a secure digest of the input file.

bool verify() const

Sanity check for internal consistency (throws an exception on failure)

bool is_dirty() const

Returns true if the netlist has invalid entries due to modifications (e.g. from remove_*() calls)

bool is_compressed() const

Returns true if the netlist has no invalid entries due to modifications (e.g. from remove_*() calls)

Note

This is a convenience method which is the logical inverse of is_dirty()

bool net_is_ignored(const NetId id) const

Returns whether the net is ignored i.e. not routed.

bool net_is_global(const NetId id) const

Returns whether the net is global.

void print_stats() const

Item counts and container info (for debugging)

const std::string &block_name(const BlockId blk_id) const

Returns the name of the specified block.

bool block_is_combinational(const BlockId blk_id) const

Returns true if the block is purely combinational (i.e. no input clocks and not a primary input.

attr_range block_attrs(const BlockId blk_id) const

Returns a range of all attributes associated with the specified block.

param_range block_params(const BlockId blk_id) const

Returns a range of all parameters associated with the specified block.

pin_range block_pins(const BlockId blk_id) const

Returns a range of all pins associated with the specified block.

pin_range block_input_pins(const BlockId blk_id) const

Returns a range of all input pins associated with the specified block.

pin_range block_output_pins(const BlockId blk_id) const

Returns a range of all output pins associated with the specified block.

Note

This is typically only data pins, but some blocks (e.g. PLLs) can produce outputs which are clocks.

pin_range block_clock_pins(const BlockId blk_id) const

Returns a range of all clock pins associated with the specified block.

port_range block_ports(const BlockId blk_id) const

Returns a range of all ports associated with the specified block.

port_range block_input_ports(const BlockId blk_id) const

Returns a range consisting of the input ports associated with the specified block.

port_range block_output_ports(const BlockId blk_id) const

Returns a range consisting of the output ports associated with the specified block.

Note

This is typically only data ports, but some blocks (e.g. PLLs) can produce outputs which are clocks.

port_range block_clock_ports(const BlockId blk_id) const

Returns a range consisting of the input clock ports associated with the specified block.

void remove_block(const BlockId blk_id)

Removes a block from the netlist. This will also remove the associated ports and pins.

Parameters:

blk_id – The block to be removed

const std::string &port_name(const PortId port_id) const

Returns the name of the specified port.

BlockId port_block(const PortId port_id) const

Returns the block associated with the specified port.

pin_range port_pins(const PortId port_id) const

Returns the set of valid pins associated with the port.

PinId port_pin(const PortId port_id, const BitIndex port_bit) const

Returns the pin (potentially invalid) associated with the specified port and port bit index.

Note

This function is a synonym for find_pin()

Parameters:
  • port_id – The ID of the associated port

  • port_bit – The bit index of the pin in the port

NetId port_net(const PortId port_id, const BitIndex port_bit) const

Returns the net (potentially invalid) associated with the specified port and port bit index.

Parameters:
  • port_id – The ID of the associated port

  • port_bit – The bit index of the pin in the port

BitIndex port_width(const PortId port_id) const

Returns the width (number of bits) in the specified port.

PortType port_type(const PortId port_id) const

Returns the type of the specified port.

void remove_port(const PortId port_id)

Removes a port from the netlist.

The port’s pins are also marked invalid and removed from any associated nets

Parameters:

port_id – The ID of the port to be removed

std::string pin_name(const PinId pin_id) const

Returns the constructed name (derived from block and port) for the specified pin.

PinType pin_type(const PinId pin_id) const

Returns the type of the specified pin.

NetId pin_net(const PinId pin_id) const

Returns the net associated with the specified pin.

int pin_net_index(const PinId pin_id) const

Returns the index of the specified pin within it’s connected net.

PortId pin_port(const PinId pin_id) const

Returns the port associated with the specified pin.

BitIndex pin_port_bit(const PinId pin_id) const

Returns the port bit index associated with the specified pin.

BlockId pin_block(const PinId pin_id) const

Returns the block associated with the specified pin.

PortType pin_port_type(const PinId pin_id) const

Returns the port type associated with the specified pin.

bool pin_is_constant(const PinId pin_id) const

Returns true if the pin is a constant (i.e. its value never changes)

void remove_pin(const PinId pin_id)

Removes a pin from the netlist.

The pin is marked invalid, and removed from any assoicated nets

Parameters:

pin_id – The pin_id of the pin to be removed

const std::string &net_name(const NetId net_id) const

Returns the name of the specified net.

pin_range net_pins(const NetId net_id) const

Returns a range consisting of all the pins in the net (driver and sinks)

The first element in the range is the driver (and may be invalid) The remaining elements (potentially none) are the sinks

PinId net_pin(const NetId net_id, int net_pin_index) const

Returns the net_pin_index’th pin of the specified net.

BlockId net_pin_block(const NetId net_id, int net_pin_index) const

Returns the block associated with the net_pin_index’th pin of the specified net.

PinId net_driver(const NetId net_id) const

Returns the (potentially invalid) net driver pin.

BlockId net_driver_block(const NetId net_id) const

Returns the (potentially invalid) net driver block.

pin_range net_sinks(const NetId net_id) const

Returns a (potentially empty) range consisting of net’s sink pins.

bool net_is_constant(const NetId net_id) const

Returns true if the net is driven by a constant pin (i.e. its value never changes)

void remove_net(const NetId net_id)

Removes a net from the netlist.

This will mark the net’s pins as having no associated.

Parameters:

net_id – The net to be removed

void remove_net_pin(const NetId net_id, const PinId pin_id)

Removes a connection betwen a net and pin.

The pin is removed from the net and the pin will be marked as having no associated net

Parameters:
  • net_id – The net from which the pin is to be removed

  • pin_id – The pin to be removed from the net

block_range blocks() const

Returns a range consisting of all blocks in the netlist.

port_range ports() const

Returns a range consisting of all ports in the netlist.

net_range nets() const

Returns a range consisting of all nets in the netlist.

pin_range pins() const

Returns a range consisting of all pins in the netlist.

BlockId find_block(const std::string &name) const

Returns the BlockId of the specified block or BlockId::INVALID() if not found.

Parameters:

name – The name of the block

BlockId find_block_by_name_fragment(const std::string &name_substring) const

Finds a block where the block’s name contains the provided input name as a substring. The intented use is to find the block id of a hard block without knowing its name in the netlist. Instead the block’s module name in the HDL design can be used as it will be a substring within its full name in the netlist.

For example, suppose a RAM block was named in the netlist as “top|alu|test_ram|out”. The user instantiated the ram module in the HDL design as “test_ram”. So instead of going through the netlist and finding the ram block’s full name, this function can be used by just providing the module name “test_ram” and using this substring to match the blocks name in the netlist and retrieving its block id. If no blocks matched to input pattern then an invalid block id is returned.

This function runs in linear time (O(N)) as it goes over all the cluster blocks in the netlist. Additionally, if there are multiple blocks that contain the provided input as a substring, then the first block found is returned.

NOTE: This function tries to find blocks by checking for substrings. The clustered netlist class defines another version of this function that find blocks by checking for a pattern match, meaning that the input is a pattern string and the pattern is looked for ine each block name.

Parameters:

name_substring

A substring of a block name for which an ID needs

to be found.

Returns:

A cluster block id representing a unique cluster block that matched to the input string pattern.

PortId find_port(const BlockId blk_id, const std::string &name) const

Returns the PortId of the specifed port if it exists or PortId::INVALID() if not.

Note

This method is typically less efficient than searching by a t_model_port With the overloaded AtomNetlist method

Parameters:
  • blk_id – The ID of the block who’s ports will be checked

  • name – The name of the port to look for

NetId find_net(const std::string &name) const

Returns the NetId of the specified net or NetId::INVALID() if not found.

Parameters:

name – The name of the net

PinId find_pin(const PortId port_id, BitIndex port_bit) const

Returns the PinId of the specified pin or PinId::INVALID() if not found.

Parameters:
  • port_id – The ID of the associated port

  • port_bit – The bit index of the pin in the port

PinId find_pin(const std::string name) const

Returns the PinId of the specified pin or PinId::INVALID() if not found.

Note

This method is SLOW, O(num_pins) &#8212; avoid if possible

Parameters:

name – The name of the pin

void set_pin_net(const PinId pin, PinType pin_type, const NetId net)

Add the specified pin to the specified net as pin_type.

Automatically removes any previous net connection for this pin.

Parameters:
  • pin – The pin to add

  • pin_type – The type of the pin (i.e. driver or sink)

  • net – The net to add the pin to

void set_pin_is_constant(const PinId pin_id, const bool value)

Mark a pin as being a constant generator.

There are some cases where a pin can not be identified as a is constant until after the full netlist has been built; so we expose a way to mark existing pins as constants.

Parameters:
  • pin_id – The pin to be marked

  • value – The boolean value to set the pin_is_constant attribute

void set_block_name(const BlockId blk_id, const std::string new_name)

Re-name a block.

Parameters:
  • blk_id – : The block to be renamed

  • new_name – : The new name for the specified block

void set_block_attr(const BlockId blk_id, const std::string &name, const std::string &value)

Set a block attribute.

Parameters:
  • blk_id – The block to which the attribute is attached

  • name – The name of the attribute to set

  • value – The new value for the specified attribute on the specified block

void set_block_param(const BlockId blk_id, const std::string &name, const std::string &value)

Set a block parameter.

Parameters:
  • blk_id – The block to which the parameter is attached

  • name – The name of the parameter to set

  • value – The new value for the specified parameter on the specified block

void set_net_is_ignored(NetId net_id, bool state)

Sets the flag in net_ignored_ = state.

Parameters:
  • net_id – The Net Id

  • state – true(false): net should(shouldn’t) be ignored

void set_net_is_global(NetId net_id, bool state)

Sets the flag in net_is_global_ = state.

void merge_nets(const NetId driver_net, const NetId sink_net)

Merges sink_net into driver_net.

After merging driver_net will contain all the sinks of sink_net

Parameters:
  • driver_net – The net which includes the driver pin

  • sink_net – The target net to be merged into driver_net (must have no driver pin)

IdRemapper remove_and_compress()

Wrapper for remove_unused() & compress()

This function should be used in the case where a netlist is fully modified

void remove_unused()

This should be called after completing a series of netlist modifications (e.g. removing blocks/ports/pins/nets).

Marks netlist components which have become redundant due to other removals (e.g. ports with only invalid pins) as invalid so they will be destroyed during compress()

IdRemapper compress()

Compresses the netlist, removing any invalid and/or unreferenced blocks/ports/pins/nets.

Note

this invalidates all existing IDs!

Clustered Netlist

Overview

The ClusteredNetlist is derived from the Netlist class, and contains some separate information on Blocks, Pins, and Nets. It does not make use of Ports.

Blocks

The pieces of unique block information are: block_pbs_: Physical block describing the clustering and internal hierarchy structure of each CLB. block_types_: The type of physical block the block is mapped to, e.g. logic block, RAM, DSP (Can be user-defined types). block_nets_: Based on the block’s pins (indexed from [0…num_pins - 1]), lists which pins are used/unused with the net using it. block_pin_nets_: Returns the index of a pin relative to the net, when given a block and a pin’s index on that block (from the type descriptor). Differs from block_nets_.

Differences between block_nets_ & block_pin_nets_

    +-----------+
0-->|           |-->3
1-->|   Block   |-->4
2-->|           |-->5
    +-----------+

block_nets_ tracks all pins on a block, and returns the ClusterNetId to which a pin is connected to. If the pin is unused/open, ClusterNetId::INVALID() is stored.

block_pin_nets_ tracks whether the nets connected to the block are drivers/receivers of that net. Driver/receiver nets are determined by the pin_class of the block’s pin. A net connected to a driver pin in the block has a 0 is stored. A net connected to a receiver has a counter (from [1…num_sinks - 1]).

The net is connected to multiple blocks. Each block_pin_nets_ has a unique number in that net.

E.g.

    +-----------+                   +-----------+
0-->|           |-->3   Net A   0-->|           |-->3
1-->|  Block 1  |---4---------->1-->|  Block 2  |-->4
2-->|           |-->5           2-->|           |-->5
    +-----------+               |   +-----------+
                                |
                                |   +-----------+
                                |   |           |-->1
                                0-->|  Block 3  |
                                    |           |-->2
                                    +-----------+

In the example, Net A is driven by Block 1, and received by Blocks 2 & 3. For Block 1, block_pin_nets_ of pin 4 returns 0, as it is the driver. For Block 2, block_pin_nets_ of pin 1 returns 1 (or 2), non-zero as it is a receiver. For Block 3, block_pin_nets_ of pin 0 returns 2 (or 1), non-zero as it is also a receiver.

The block_pin_nets_ data structure exists for quick indexing, rather than using a linear search with the available functions from the base Netlist, into the net_delay_ structure in the PostClusterDelayCalculator of inter_cluster_delay(). net_delay_ is a 2D array, where the indexing scheme is [net_id] followed by [pin_index on net].

Pins

The only piece of unique pin information is: logical_pin_index_

Example of logical_pin_index_

Given a ClusterPinId, logical_pin_index_ will return the index of the pin within its block relative to the t_logical_block_type (logical description of the block).

    +-----------+
0-->|O         X|-->3
1-->|O  Block  O|-->4
2-->|X         O|-->5 (e.g. ClusterPinId = 92)
    +-----------+

The index skips over unused pins, e.g. CLB has 6 pins (3 in, 3 out, numbered [0…5]), where the first two ins, and last two outs are used. Indices [0,1] represent the ins, and [4,5] represent the outs. Indices [2,3] are unused. Therefore, logical_pin_index_[92] = 5.

Implementation

For all create_* functions, the ClusteredNetlist will wrap and call the Netlist’s version as it contains additional information that the base Netlist does not know about.

All functions with suffix *_impl() follow the Non-Virtual Interface (NVI) idiom. They are called from the base Netlist class to simplify pre/post condition checks and prevent Fragile Base Class (FBC) problems.

Refer to netlist.h for more information.

class ClusteredNetlist : public Netlist<ClusterBlockId, ClusterPortId, ClusterPinId, ClusterNetId>

Public Functions

ClusteredNetlist(std::string name = "", std::string id = "")

Constructs a netlist.

Parameters:
  • name – the name of the netlist (e.g. top-level module)

  • id – a unique identifier for the netlist (e.g. a secure digest of the input file)

t_pb *block_pb(const ClusterBlockId id) const

Returns the physical block.

t_logical_block_type_ptr block_type(const ClusterBlockId id) const

Returns the type of CLB (Logic block, RAM, DSP, etc.)

const std::vector<ClusterBlockId> &blocks_per_type(const t_logical_block_type &blk_type) const

Returns the blocks with the specific block types in the netlist.

ClusterNetId block_net(const ClusterBlockId blk_id, const int pin_index) const

Returns the net of the block attached to the specific pin index.

int block_pin_net_index(const ClusterBlockId blk_id, const int pin_index) const

Returns the count on the net of the block attached.

ClusterPinId block_pin(const ClusterBlockId blk, const int logical_pin_index) const

Returns the logical pin Id associated with the specified block and logical pin index.

bool block_contains_primary_output(const ClusterBlockId blk) const

Returns true if the specified block contains a primary output (e.g. BLIF .output primitive)

int pin_logical_index(const ClusterPinId pin_id) const

Returns the logical pin index (i.e. pin index on the t_logical_block_type) of the cluster pin.

int net_pin_logical_index(const ClusterNetId net_id, int net_pin_index) const

Finds the net_index’th net pin (e.g. the 6th pin of the net) and returns the logical pin index (i.e. pin index on the t_logical_block_type) of the block to which the pin belongs.

Parameters:
  • net_id – The net

  • net_pin_index – The index of the pin in the net

ClusterBlockId create_block(const char *name, t_pb *pb, t_logical_block_type_ptr type)

Create or return an existing block in the netlist.

Parameters:
  • name – The unique name of the block

  • pb – The physical representation of the block

  • type – The type of the CLB

ClusterPortId create_port(const ClusterBlockId blk_id, const std::string &name, BitIndex width, PortType type)

Create or return an existing port in the netlist.

Parameters:
  • blk_id – The block the port is associated with

  • name – The name of the port (must match the name of a port in the block’s model)

  • width – The width (number of bits) of the port

  • type – The type of the port (INPUT, OUTPUT, or CLOCK)

ClusterPinId create_pin(const ClusterPortId port_id, BitIndex port_bit, const ClusterNetId net_id, const PinType pin_type, int pin_index, bool is_const = false)

Create or return an existing pin in the netlist.

Parameters:
  • port_id – The port this pin is associated with

  • port_bit – The bit index of the pin in the port

  • net_id – The net the pin drives/sinks

  • pin_type – The type of the pin (driver/sink)

  • pin_index – The index of the pin relative to its block, excluding OPEN pins)

  • is_const – Indicates whether the pin holds a constant value (e. g. vcc/gnd)

ClusterNetId create_net(const std::string &name)

Create an empty, or return an existing net in the netlist.

Parameters:

name – The unique name of the net

ClusterBlockId find_block_by_name_fragment(const std::string &name_pattern, const std::vector<ClusterBlockId> &cluster_block_candidates) const

Given a name of a block and vector of possible cluster blocks that are candidates to match the block name, go through the vector of cluster blocks and return the id of the block where the block name matches the provided name.

Given a string pattern representing a block name and a vector of poissble cluster blocks that are candidates to match to the block name pattern, go through the vector of cluster blocks and return the id of the block where the block name matches to the provided input pattern.

The intented use is to find the block id of a hard block without knowing its name in the netlist. Instead a pattern can be created that we know the block’s name will match to. Generally, we expect the pattern to be constructed using the block’s module name in the HDL design, since we can expect the netlist name of the block to include the module name within it.

For example, suppose a RAM block was named in the netlist as “top|alu|test_ram|out”. The user instantiated the ram module in the HDL design as “test_ram”. So instead of going through the netlist and finding the ram block’s full name, this function can be used by just providing the string pattern as “.*test_ram.*”. We know that the module name should be somewhere within the string, so the pattern we provide says that the netlist name of the block contains arbritary characters then the module name and then some other arbritary characters after. This pattern will then be used to match to the block in the netlist. The matched cluster block id is returned, and if no block matched to the input string then an invalid block id is returned.

The function here additionally requires a vector of possible cluster blocks that can match to the input pattern. This vector can be the entire netlist or a subset. For example, if the intended use is to find hard blocks, it is quite inefficient to go through all the blocks to find a matching one. Instead, a a filtered vector can be passed that is a subset of the entire netlist and can only contain blocks of a certain logical block type (blocks that can be placed on a specific hard block). The idea here is that the filtered vector should be considereably smaller that a vector of every block in the netlist and this should help improve run time.

This function runs in linear time (O(N)) as it goes over the vector of ‘cluster_block_candidates’. ‘cluster_block_candidates’ could be the whole netlist or a subset as explained above. Additionally, if there are multiple blocks that match to the provided input pattern, then the first block found is returned.

Parameters:
  • name_pattern

    A regex string pattern that can be used to match to

    a clustered block name within the netlist.

  • cluster_block_candidates – A vector of clustered block ids that represent a subset of the clustered netlist. The blocks in this vector will be used to compare and match to the input string pattern.

Returns:

A cluster block id representing a unique cluster block that matched to the input string pattern.

Atom Netlist

Overview

The AtomNetlist is derived from the Netlist class, and contains information on the primitives. This includes basic components (Blocks, Ports, Pins, & Nets), and physical descriptions (t_model) of the primitives.

Most of the functionality relevant to components and their accessors/cross-accessors is implemented in the Netlist class. Refer to netlist.(h|tpp) for more information.

Components

There are 4 components in the Netlist: Blocks, Ports, Pins, and Nets. Each component has a unique ID in the netlist, as well as various associations to their related components (e.g. A pin knows which port it belongs to, and what net it connects to)

Blocks

Blocks refer to the atoms (AKA primitives) that are in the the netlist. Each block contains input/output/clock ports. Blocks have names, and various functionalities (LUTs, FFs, RAMs, …) Each block has an associated t_model, describing the physical properties.

Ports

Ports are composed of a set of pins that have specific directionality (INPUT, OUTPUT, or CLOCK). The ports in the AtomNetlist are respective to the atoms. (i.e. the AtomNetlist does not contain ports of a Clustered Logic Block). Each port has an associated t_model_port, describing the physical properties.

Pins

Pins are single-wire input/outputs. They are part of a port, and are connected to a single net.

Nets

Nets in the AtomNetlist track the wiring connections between the atoms.

Models

There are two main models, the primitive itself (t_model) and the ports of that primitive (t_model_ports). The models are created from the architecture file, and describe the physical properties of the atom.

Truth Table

The AtomNetlist also contains a TruthTable for each block, which indicates what the LUTs contain.

Implementation

For all create_* functions, the AtomNetlist will wrap and call the Netlist’s version as it contains additional information that the base Netlist does not know about.

All functions with suffix *_impl() follow the Non-Virtual Interface (NVI) idiom. They are called from the base Netlist class to simplify pre/post condition checks and prevent Fragile Base Class (FBC) problems.

Refer to netlist.h for more information.

class AtomNetlist : public Netlist<AtomBlockId, AtomPortId, AtomPinId, AtomNetId>

Public Functions

AtomNetlist(std::string name = "", std::string id = "")

Constructs a netlist.

Parameters:
  • name – the name of the netlist (e.g. top-level module)

  • id – a unique identifier for the netlist (e.g. a secure digest of the input file)

AtomBlockType block_type(const AtomBlockId id) const

Returns the type of the specified block.

const t_model *block_model(const AtomBlockId id) const

Returns the model associated with the block.

const TruthTable &block_truth_table(const AtomBlockId id) const

Returns the truth table associated with the block.

For LUTs the truth table stores the single-output cover representing the logic function.

For FF/Latches there is only a single entry representing the initial state

Note

This is only non-empty for LUTs and Flip-Flops/latches.

const t_model_ports *port_model(const AtomPortId id) const

Returns the model port of the specified port or nullptr if not.

Parameters:

id – The ID of the port to look for

AtomPortId find_atom_port(const AtomBlockId blk_id, const t_model_ports *model_port) const

Returns the AtomPortId of the specifed port if it exists or AtomPortId::INVALID() if not.

Note

This method is typically more efficient than searching by name

Parameters:
  • blk_id – The ID of the block who’s ports will be checked

  • model_port – The port model to look for

AtomBlockId find_atom_pin_driver(const AtomBlockId blk_id, const t_model_ports *model_port, const BitIndex port_bit) const

Returns the AtomBlockId of the atom driving the specified pin if it exists or AtomBlockId::INVALID() if not.

Parameters:
  • blk_id – The ID of the block whose ports will be checked

  • model_port – The port model to look for

  • port_bit – The pin number in this port

std::unordered_set<std::string> net_aliases(const std::string net_name) const

Returns the a set of aliases relative to the net name.

If no aliases are found, returns a set with the original net name.

Parameters:

net_name – name of the net from which the aliases are extracted

AtomBlockId create_block(const std::string name, const t_model *model, const TruthTable truth_table = TruthTable())

Create or return an existing block in the netlist.

Parameters:
  • name – The unique name of the block

  • model – The primitive type of the block

  • truth_table – The single-output cover defining the block’s logic function The truth_table is optional and only relevant for LUTs (where it describes the logic function) and Flip-Flops/latches (where it consists of a single entry defining the initial state).

AtomPortId create_port(const AtomBlockId blk_id, const t_model_ports *model_port)

Create or return an existing port in the netlist.

Parameters:
  • blk_id – The block the port is associated with

  • model_port – The model port the port is associated with

AtomPinId create_pin(const AtomPortId port_id, BitIndex port_bit, const AtomNetId net_id, const PinType pin_type, bool is_const = false)

Create or return an existing pin in the netlist.

Parameters:
  • port_id – The port this pin is associated with

  • port_bit – The bit index of the pin in the port

  • net_id – The net the pin drives/sinks

  • pin_type – The type of the pin (driver/sink)

  • is_const – Indicates whether the pin holds a constant value (e. g. vcc/gnd)

AtomNetId create_net(const std::string name)

Create an empty, or return an existing net in the netlist.

Parameters:

name – The unique name of the net

AtomNetId add_net(const std::string name, AtomPinId driver, std::vector<AtomPinId> sinks)

Create a completely specified net from specified driver and sinks.

Parameters:
  • name – The name of the net (Note: must not already exist)

  • driver – The net’s driver pin

  • sinks – The net’s sink pins

void add_net_alias(const std::string net_name, std::string alias_net_name)

Adds a value to the net aliases set for a given net name in the net_aliases_map.

If there is no key/value pair in the net_aliases_map, creates a new set and adds it to the map.

Parameters:
  • net_name – The net to be added to the map

  • alias_net_name – The alias of the assigned clock net id