#!/usr/bin/env python3
""" Script for addressing CARRY4 output congestion in elaborated netlists.

Usage:

    python3 fix_carry.py < input-netlist-json > output-netlist-json

Description:

    In the 7-series SLICEL (and SLICEM) sites, there can be output congestion
    if both the CO and O of the CARRY4 are used. This congestion can be
    avoided by using a transparent/open latch or register on the output of the
    CARRY4.

    VPR does not currently support either of those options, so for now, if
    both CO and O are used, the CO output is converted into a LUT equation to
    recompute the CO output from O, DI and S.  See carry_map.v and
    clean_carry_map.v for details.

    If VPR could emit the transparent/open latch on output congestion, this
    would no longer be required.  The major problem with transparent latch
    support is that it requires constants to be routed to the G/GE/CLR/PRE
    ports, which VPR cannot express as a result of packing.

    This script identifies CARRY4 chains in the netlist, identifies if there
    is output congestion on the O and CO ports, and marks the congestion by
    changing CARRY_CO_DIRECT (e.g. directly use the CO port) to CARRY_CO_LUT
    (compute the CO value using a LUT equation).


Diagram showing one row of the 7-series CLE, focusing on O/CO congestion.
This diagram shows that if both the O and CO outputs are needed, once must
pass through the flip flop (xFF in the diagram).

                                      CLE Row

+--------------------------------------------------------------------------+
|                                                                          |
|                                                                          |
|                                               +---+                      |
|                                               |    +                     |
|                                               |     +                    |
|                                     +-------->+ O    +                   |
|              CO CHAIN               |         |       +                  |
|                                     |         |       +---------------------> xMUX
|                 ^                   |   +---->+ CO    +                  |
|                 |                   |   |     |      +                   |
|                 |                   |   |     |     +                    |
|       +---------+----------+        |   |     |    +                     |
|       |                    |        |   |     +---+                      |
|       |     CARRY ROW      |        |   |                                |
|  +--->+ S              O   +--------+   |       xOUTMUX                  |
|       |                    |        |   |                                |
|       |                    |        +   |                                |
|  +--->+ DI             CO  +-------+o+--+                                |
|       |      CI CHAIN      |        +   |                                |
|       |                    |        |   |                                |
|       +---------+----------+        |   |       xFFMUX                   |
|                 ^                   |   |                                |
|                 |                   |   |     +---+                      |
|                 +                   |   |     |    +                     |
|                                     |   +     |     +    +-----------+   |
|                                     +--+o+--->+ O    +   |           |   |
|                                         +     |       +  |    xFF    |   |
|                                         |     |       +->--D----   Q +------> xQ
|                                         |     |       +  |           |   |
|                                         +---->+ CO   +   |           |   |
|                                               |     +    +-----------+   |
|                                               |    +                     |
|                                               +---+                      |
|                                                                          |
|                                                                          |
+--------------------------------------------------------------------------+


This script operates on a slightly different cell structure than a plain CARRY4.
carry_map.v converts the CARRY4 into:

                                              +------------------+  +-----------------+
                                              |                  |  |                 |
                                              |              CO3 +->+ CARRY_CO_DIRECT |
                                              |                  |  |                 |
                                              | DI3              |  +-----------------+
                                              |                  |
                                              | S3           O3  |
                                              |                  |
                                              | DI2              |  +-----------------+
                                              |                  |  |                 |
                                              | S2           CO2 +->+ CARRY_CO_DIRECT |
                                              |                  |  |                 |
                                              | DI1              |  +-----------------+
                                              |                  |
                                              | S1           O2  |
                                              |      CARRY4      |
                                              | DI0 (chained)    |  +-----------------+
                                              |                  |  |                 |
                                              | S0           CO1 +->+ CARRY_CO_DIRECT |
                                              |                  |  |                 |
                                              | CYINIT           |  +-----------------+
                                              |                  |
                         +-----------------+  |              O1  |
                         |                 |  |                  |
                      +->+ CARRY_COUT_PLUG +->+ CI               |  +-----------------+
                      |  |                 |  |                  |  |                 |
                      |  +-----------------+  |              CO0 +->+ CARRY_CO_DIRECT |
                      |                       |                  |  |                 |
                      |                       |                  |  +-----------------+
                      +-------------------+   |                  |
                                          |   |              O0  |
+------------------+  +-----------------+ |   |                  |
|                  |  |                 | |   +------------------+
|              CO3 +->+ CARRY_CO_DIRECT +-+
|                  |  |                 |
| DI3              |  +-----------------+
|                  |
| S3           O3  |
|                  |
| DI2              |  +-----------------+
|                  |  |                 |
| S2           CO2 +->+ CARRY_CO_DIRECT |
|                  |  |                 |
| DI1              |  +-----------------+
|                  |
| S1           O2  |
|       CARRY4     |
| DI0   (root)     |  +-----------------+
|                  |  |                 |
| S0           CO1 +->+ CARRY_CO_DIRECT |
|                  |  |                 |
| CYINIT           |  +-----------------+
|                  |
|              O1  |
|                  |
| CI               |  +-----------------+
|                  |  |                 |
|              CO0 +->+ CARRY_CO_DIRECT |
|                  |  |                 |
|                  |  +-----------------+
|                  |
|              O0  |
|                  |
+------------------+

Each CARRY4 spans the 4 rows of the SLICEL/SLICEM.
Row 0 is the S0/DI0/O0/CO0 ports, row 1 is S1/DI1/O1/CO1 ports, etc.

So there are five cases the script has to handle:

 - No congestion is present between O and CO ->

    Do nothing.

 - Congestion is present on rows 0-2 and row above is in use ->

    Change CARRY_CO_DIRECT to CARRY_CO_LUT.

    Routing and LUT delays are incurred in this case.

 - Congestion is present on rows 0-2 and row above is not in use ->

    Remap CO to O from the row above, and set S on the next row to 0 to
    ensure O outputs CI from the row below.

    No additional delays for this change.

 - Congestion is present on row 3 and CO3 is not connected to another CARRY ->

    Change CARRY_CO_DIRECT to CARRY_CO_TOP_POP.  This adds 1 dummy layer to
    the carry chain to output the CO.

    No additional delays for this change.

 - Congestion is present on row 3 and CO3 is connected directly to another
   CARRY4 ->

    Change CARRY_CO_DIRECT to CARRY_CO_LUT *and* change the chained
    CARRY_COUT_PLUG to be directly connected to the previous CO3.

    Routing and LUT delays are incurred in this case.

    Diagram for this case:

                                                 +-------------------+  +-----------------+
                                                 |                   |  |                 |
                                                 |               CO3 +->+ CARRY_CO_DIRECT |
                                                 |                   |  |                 |
                                                 |  DI3              |  +-----------------+
                                                 |                   |
                                                 |  S3           O3  |
                                                 |                   |
                                                 |  DI2              |  +-----------------+
                                                 |                   |  |                 |
                                                 |  S2           CO2 +->+ CARRY_CO_DIRECT |
                                                 |                   |  |                 |
                                                 |  DI1              |  +-----------------+
                                                 |                   |
                                                 |  S1           O2  |
                                                 |       CARRY4      |
                                                 |  DI0 (chained)    |  +-----------------+
                                                 |                   |  |                 |
                                                 |  S0           CO1 +->+ CARRY_CO_DIRECT |
                                                 |                   |  |                 |
                                                 |  CYINIT           |  +-----------------+
                                                 |                   |
                          +-----------------+    |               O1  |
                          |                 |    |                   |
                       +->+ CARRY_COUT_PLUG +--->+  CI               |  +-----------------+
                       |  |                 |    |                   |  |                 |
                       |  +-----------------+    |               CO0 +->+ CARRY_CO_DIRECT |
                       |                         |                   |  |                 |
+-------------------+  |  +-----------------+    |                   |  +-----------------+
|                   |  |  |                 |    |                   |
|               CO3 +--+->+ CARRY_CO_LUT    +-+  |               O0  |
|                   |     |                 | |  |                   |
|  DI3              |     +-----------------+ |  +-------------------+
|                   |                         |
|  S3           O3  |                         +------>
|                   |
|  DI2              |     +-----------------+
|                   |     |                 |
|  S2           CO2 +---->+ CARRY_CO_DIRECT |
|                   |     |                 |
|  DI1              |     +-----------------+
|                   |
|  S1           O2  |
|        CARRY4     |
|  DI0   (root)     |     +-----------------+
|                   |     |                 |
|  S0           CO1 +---->+ CARRY_CO_DIRECT |
|                   |     |                 |
|  CYINIT           |     +-----------------+
|                   |
|               O1  |
|                   |
|  CI               |     +-----------------+
|                   |     |                 |
|               CO0 +---->+ CARRY_CO_DIRECT |
|                   |     |                 |
|                   |     +-----------------+
|                   |
|               O0  |
|                   |
+-------------------+

After this script is run, clean_carry_map.v is used to convert CARRY_CO_DIRECT
into a direct connection, and CARRY_CO_LUT is mapped to a LUT to compute the
carry output.

"""
import json
import sys


def find_top_module(design):
    """
    Looks for the top-level module in the design. Returns its name. Throws
    an exception if none was found.
    """

    for name, module in design["modules"].items():
        attrs = module["attributes"]
        if "top" in attrs and int(attrs["top"]) == 1:
            return name

    raise RuntimeError("No top-level module found in the design!")


def find_carry4_chains(design, top_module, bit_to_cells):
    """ Identify CARRY4 carry chains starting from the root CARRY4.

    All non-root CARRY4 cells should end up as part of a chain, otherwise
    an assertion is raised.

    Arguments:
     design (dict) - "design" field from Yosys JSON format
     top_module (str) - Name of top module.
     bit_to_cells (dict) - Map of net bit identifier and cell information.
        Computes in "create_bit_to_cell_map".

    Returns:
        list of list of strings - List of CARRY4 chains.  Each chain is a list
            of cellnames.  The cells are listed in chain order, starting from
            the root.

    """
    cells = design["modules"][top_module]["cells"]

    used_carry4s = set()
    root_carry4s = []
    nonroot_carry4s = {}
    for cellname in cells:
        cell = cells[cellname]
        if cell["type"] != "CARRY4_VPR":
            continue
        connections = cell["connections"]

        if "CIN" in connections:
            cin_connections = connections["CIN"]
            assert len(cin_connections) == 1

            # Goto driver of CIN, should be a CARRY_COUT_PLUG.
            plug_cellname, port, bit_idx = bit_to_cells[cin_connections[0]][0]
            plug_cell = cells[plug_cellname]
            assert plug_cell["type"] == "CARRY_COUT_PLUG", plug_cellname
            assert port == "COUT"

            plug_connections = plug_cell["connections"]

            cin_connections = plug_connections["CIN"]
            assert len(cin_connections) == 1

            # Goto driver of CIN, should be a CARRY_CO_DIRECT.
            direct_cellname, port, bit_idx = bit_to_cells[cin_connections[0]
                                                          ][0]
            direct_cell = cells[direct_cellname]
            assert direct_cell["type"] == "CARRY_CO_DIRECT", direct_cellname
            assert port == "OUT"

            direct_connections = direct_cell["connections"]

            co_connections = direct_connections["CO"]
            assert len(co_connections) == 1

            nonroot_carry4s[co_connections[0]] = cellname
        else:
            used_carry4s.add(cellname)
            root_carry4s.append(cellname)

    # Walk from each root CARRY4 to each child CARRY4 module.
    chains = []
    for cellname in root_carry4s:
        chain = [cellname]

        while True:
            # Follow CO3 to the next CARRY4, if any.
            cell = cells[cellname]
            connections = cell["connections"]

            co3_connections = connections.get("CO3", None)
            if co3_connections is None:
                # No next CARRY4, stop here.
                break

            found_next_link = False
            for connection in co3_connections:
                next_cellname = nonroot_carry4s.get(connection, None)
                if next_cellname is not None:
                    cellname = next_cellname
                    used_carry4s.add(cellname)
                    chain.append(cellname)
                    found_next_link = True
                    break

            if not found_next_link:
                break

        chains.append(chain)

    # Make sure all non-root CARRY4's got used.
    for bit, cellname in nonroot_carry4s.items():
        assert cellname in used_carry4s, (bit, cellname)

    return chains


def create_bit_to_cell_map(design, top_module):
    """ Create map from net bit identifier to cell information.

    Arguments:
     design (dict) - "design" field from Yosys JSON format
     top_module (str) - Name of top module.

    Returns:
     bit_to_cells (dict) - Map of net bit identifier and cell information.

    The map keys are the net bit identifier used to mark which net a cell port
    is connected too.  The map values are a list of cell ports that are in the
    net.  The first element of the list is the driver port, and the remaining
    elements are sink ports.

    The list elements are 3-tuples with:
      cellname (str) - The name of the cell this port belongs too
      port (str) - The name of the port this element is connected too.
      bit_idx (int) - For multi bit ports, a 0-based index into the port.

    """
    bit_to_cells = {}

    cells = design["modules"][top_module]["cells"]

    for cellname in cells:
        cell = cells[cellname]
        port_directions = cell["port_directions"]
        for port, connections in cell["connections"].items():
            is_output = port_directions[port] == "output"
            for bit_idx, bit in enumerate(connections):

                list_of_cells = bit_to_cells.get(bit, None)
                if list_of_cells is None:
                    list_of_cells = [None]
                    bit_to_cells[bit] = list_of_cells

                if is_output:
                    # First element of list of cells is net driver.
                    assert list_of_cells[0] is None, (
                        bit, list_of_cells[0], cellname
                    )
                    list_of_cells[0] = (cellname, port, bit_idx)
                else:
                    list_of_cells.append((cellname, port, bit_idx))

    return bit_to_cells


def is_bit_used(bit_to_cells, bit):
    """ Is the net bit specified used by any sinks? """
    list_of_cells = bit_to_cells[bit]

    return len(list_of_cells) > 1


def is_bit_used_other_than_carry4_cin(design, top_module, bit, bit_to_cells):
    """ Is the net bit specified used by any sinks other than a carry chain? """
    cells = design["modules"][top_module]["cells"]
    list_of_cells = bit_to_cells[bit]
    assert len(list_of_cells) == 2, bit

    direct_cellname, port, _ = list_of_cells[1]
    direct_cell = cells[direct_cellname]
    assert direct_cell['type'] == "CARRY_CO_DIRECT"
    assert port == "CO"

    # Follow to output
    connections = direct_cell["connections"]["OUT"]
    assert len(connections) == 1

    for cellname, port, bit_idx in bit_to_cells[connections[0]][1:]:
        cell = cells[cellname]
        if cell["type"] == "CARRY_COUT_PLUG" and port == "CIN":
            continue
        else:
            return True, direct_cellname

    return False, direct_cellname


def create_bit_to_net_map(design, top_module):
    """ Create map from net bit identifier to net information.

    Arguments:
     design (dict) - "design" field from Yosys JSON format
     top_module (str) - Name of top module.

    Returns:
     bit_to_nets (dict) - Map of net bit identifier to net information.
    """
    bit_to_nets = {}

    nets = design["modules"][top_module]["netnames"]

    for net in nets:
        for bit_idx, bit in enumerate(nets[net]["bits"]):
            bit_to_nets[bit] = (net, bit_idx)

    return bit_to_nets


def fixup_cin(design, top_module, bit_to_cells, co_bit, direct_cellname):
    """ Move connection from CARRY_CO_LUT.OUT -> CARRY_COUT_PLUG.CIN to
        directly to preceeding CARRY4.
    """
    cells = design["modules"][top_module]["cells"]

    direct_cell = cells[direct_cellname]
    assert direct_cell["type"] == "CARRY_CO_LUT"

    # Follow to output
    connections = direct_cell["connections"]["OUT"]
    assert len(connections) == 1

    for cellname, port, bit_idx in bit_to_cells[connections[0]][1:]:
        cell = cells[cellname]
        if cell["type"] == "CARRY_COUT_PLUG" and port == "CIN":
            assert bit_idx == 0

            cells[cellname]["connections"]["CIN"][0] = co_bit


def fixup_congested_rows(design, top_module, bit_to_cells, bit_to_nets, chain):
    """ Walk the specified carry chain, and identify if any outputs are congested.

    Arguments:
     design (dict) - "design" field from Yosys JSON format
     top_module (str) - Name of top module.
     bit_to_cells (dict) - Map of net bit identifier and cell information.
        Computes in "create_bit_to_cell_map".
     bit_to_nets (dict) - Map of net bit identifier to net information.
        Computes in "create_bit_to_net_map".
     chain (list of str) - List of cells in the carry chain.

    """
    cells = design["modules"][top_module]["cells"]

    O_ports = ["O0", "O1", "O2", "O3"]
    CO_ports = ["CO0", "CO1", "CO2", "CO3"]

    def check_if_rest_of_carry4_is_unused(cellname, cell_idx):
        assert cell_idx < len(O_ports)

        cell = cells[cellname]
        connections = cell["connections"]

        for o, co in zip(O_ports[cell_idx:], CO_ports[cell_idx:]):
            o_conns = connections[o]
            assert len(o_conns) == 1
            o_bit = o_conns[0]
            if is_bit_used(bit_to_cells, o_bit):
                return False

            co_conns = connections[co]
            assert len(co_conns) == 1
            co_bit = co_conns[0]
            if is_bit_used(bit_to_cells, co_bit):
                return False

        return True

    # Carry chain is congested if both O and CO is used at the same level.
    # CO to next element in the chain is fine.
    for chain_idx, cellname in enumerate(chain):
        cell = cells[cellname]
        connections = cell["connections"]
        for cell_idx, (o, co) in enumerate(zip(O_ports, CO_ports)):
            o_conns = connections[o]
            assert len(o_conns) == 1
            o_bit = o_conns[0]

            co_conns = connections[co]
            assert len(co_conns) == 1
            co_bit = co_conns[0]

            is_o_used = is_bit_used(bit_to_cells, o_bit)
            is_co_used, direct_cellname = is_bit_used_other_than_carry4_cin(
                design, top_module, co_bit, bit_to_cells
            )

            if is_o_used and is_co_used:
                # Output at this row is congested.
                direct_cell = cells[direct_cellname]

                if co == 'CO3' and chain_idx == len(chain) - 1:
                    # This congestion is on the top of the carry chain,
                    # emit a dummy layer to the chain.
                    direct_cell["type"] = "CARRY_CO_TOP_POP"
                    assert int(direct_cell["parameters"]["TOP_OF_CHAIN"]) == 1
                # If this is the last CARRY4 in the chain, see if the
                # remaining part of the chain is idle.
                elif chain_idx == len(chain) - 1 and \
                    check_if_rest_of_carry4_is_unused(cellname, cell_idx + 1):

                    # Because the rest of the CARRY4 is idle, it is safe to
                    # use the next row up to output the top of the carry.
                    connections["S{}".format(cell_idx + 1)] = ["1'b0"]

                    next_o_conns = connections[O_ports[cell_idx + 1]]
                    assert len(next_o_conns) == 1
                    direct_cell["connections"]["CO"][0] = next_o_conns[0]

                    netname, bit_idx = bit_to_nets[next_o_conns[0]]
                    assert bit_idx == 0

                    # Update annotation that this net is now in use.
                    net = design["module"][top_module]["netnames"][netname]
                    assert net["attributes"].get("unused_bits", None) == "0 "
                    del net["attributes"]["unused_bits"]
                else:
                    # The previous two stragies (use another layer of carry)
                    # only work for the top of the chain.  This appears to be
                    # in the middle of the chain, so just spill it out to a
                    # LUT, and fixup the direct carry chain (if any).
                    direct_cell["type"] = "CARRY_CO_LUT"

                    fixup_cin(
                        design, top_module, bit_to_cells, co_bit,
                        direct_cellname
                    )


def main():
    design = json.load(sys.stdin)
    top_module = find_top_module(design)

    bit_to_cells = create_bit_to_cell_map(design, top_module)
    bit_to_nets = create_bit_to_net_map(design, top_module)

    for chain in find_carry4_chains(design, top_module, bit_to_cells):
        fixup_congested_rows(
            design, top_module, bit_to_cells, bit_to_nets, chain
        )

    json.dump(design, sys.stdout, indent=2)


if __name__ == "__main__":
    main()