-- PSL - Utils -- Copyright (C) 2002-2016 Tristan Gingold -- -- This program is free software: you can redistribute it and/or modify -- it under the terms of the GNU General Public License as published by -- the Free Software Foundation, either version 2 of the License, or -- (at your option) any later version. -- -- This program is distributed in the hope that it will be useful, -- but WITHOUT ANY WARRANTY; without even the implied warranty of -- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -- GNU General Public License for more details. -- -- You should have received a copy of the GNU General Public License -- along with this program. If not, see . with PSL.Types; use PSL.Types; with PSL.Nodes_Priv; with PSL.Errors; use PSL.Errors; package body PSL.NFAs.Utils is generic with function Get_First_Edge (S : NFA_State) return NFA_Edge; with function Get_Next_Edge (E : NFA_Edge) return NFA_Edge; with procedure Set_First_Edge (S : NFA_State; E : NFA_Edge); with procedure Set_Next_Edge (E : NFA_Edge; N_E : NFA_Edge); with function Get_Edge_State (E : NFA_Edge) return NFA_State; package Sort_Edges is procedure Sort_Edges (S : NFA_State); procedure Sort_Edges (N : NFA); end Sort_Edges; package body Sort_Edges is -- Use merge sort to sort a list of edges. -- The first edge is START and the list has LEN edges. -- RES is the head of the sorted list. -- NEXT_EDGE is the LEN + 1 edge (not sorted). procedure Edges_Merge_Sort (Start : NFA_Edge; Len : Natural; Res : out NFA_Edge; Next_Edge : out NFA_Edge) is function Lt (L, R : NFA_Edge) return Boolean is L_Expr : constant Node := Get_Edge_Expr (L); R_Expr : constant Node := Get_Edge_Expr (R); begin return PSL.Nodes_Priv."<" (L_Expr, R_Expr) or else (L_Expr = R_Expr and then Get_Edge_State (L) < Get_Edge_State (R)); end Lt; pragma Inline (Lt); Half : constant Natural := Len / 2; Left_Start, Right_Start : NFA_Edge; Left_Next, Right_Next : NFA_Edge; L, R : NFA_Edge; Last, E : NFA_Edge; begin -- With less than 2 elements, the sort is trivial. if Len < 2 then if Len = 0 then Next_Edge := Start; else Next_Edge := Get_Next_Edge (Start); end if; Res := Start; return; end if; -- Sort each half. Edges_Merge_Sort (Start, Half, Left_Start, Left_Next); Edges_Merge_Sort (Left_Next, Len - Half, Right_Start, Right_Next); -- Merge. L := Left_Start; R := Right_Start; Last := No_Edge; loop -- Take from left iff: -- * it is not empty -- * right is empty or else (left < right) if L /= Left_Next and then (R = Right_Next or else Lt (L, R)) then E := L; L := Get_Next_Edge (L); -- Take from right if right is not empty. elsif R /= Right_Next then E := R; R := Get_Next_Edge (R); -- Both left are right are empty. else exit; end if; if Last = No_Edge then Res := E; else Set_Next_Edge (Last, E); end if; Last := E; end loop; -- Let the link clean. Next_Edge := Right_Next; Set_Next_Edge (Last, Next_Edge); end Edges_Merge_Sort; procedure Sort_Edges (S : NFA_State) is Nbr_Edges : Natural; First_E, E, Res : NFA_Edge; begin -- Count number of edges. Nbr_Edges := 0; First_E := Get_First_Edge (S); E := First_E; while E /= No_Edge loop Nbr_Edges := Nbr_Edges + 1; E := Get_Next_Edge (E); end loop; -- Sort edges by expression. Edges_Merge_Sort (First_E, Nbr_Edges, Res, E); pragma Assert (E = No_Edge); Set_First_Edge (S, Res); end Sort_Edges; procedure Sort_Edges (N : NFA) is S : NFA_State; begin -- Iterate on states. S := Get_First_State (N); while S /= No_State loop Sort_Edges (S); S := Get_Next_State (S); end loop; end Sort_Edges; end Sort_Edges; package Sort_Src_Edges_Pkg is new Sort_Edges (Get_First_Edge => Get_First_Src_Edge, Get_Next_Edge => Get_Next_Src_Edge, Set_First_Edge => Set_First_Src_Edge, Set_Next_Edge => Set_Next_Src_Edge, Get_Edge_State => Get_Edge_Dest); procedure Sort_Src_Edges (S : NFA_State) renames Sort_Src_Edges_Pkg.Sort_Edges; procedure Sort_Src_Edges (N : NFA) renames Sort_Src_Edges_Pkg.Sort_Edges; package Sort_Dest_Edges_Pkg is new Sort_Edges (Get_First_Edge => Get_First_Dest_Edge, Get_Next_Edge => Get_Next_Dest_Edge, Set_First_Edge => Set_First_Dest_Edge, Set_Next_Edge => Set_Next_Dest_Edge, Get_Edge_State => Get_Edge_Src); procedure Sort_Dest_Edges (S : NFA_State) renames Sort_Dest_Edges_Pkg.Sort_Edges; procedure Sort_Dest_Edges (N : NFA) renames Sort_Dest_Edges_Pkg.Sort_Edges; generic with function Get_First_Edge_Reverse (S : NFA_State) return NFA_Edge; with function Get_First_Edge (S : NFA_State) return NFA_Edge; with procedure Set_First_Edge (S : NFA_State; E : NFA_Edge); with function Get_Next_Edge (E : NFA_Edge) return NFA_Edge; with procedure Set_Next_Edge (E : NFA_Edge; E1 : NFA_Edge); with procedure Set_Edge_State (E : NFA_Edge; S : NFA_State); procedure Merge_State (N : NFA; S : NFA_State; S1 : NFA_State); procedure Merge_State (N : NFA; S : NFA_State; S1 : NFA_State) is E, First_E, Next_E : NFA_Edge; begin pragma Assert (S /= S1); -- Discard outgoing edges of S1. loop E := Get_First_Edge_Reverse (S1); exit when E = No_Edge; Remove_Edge (E); end loop; -- Prepend incoming edges of S1 to S. First_E := Get_First_Edge (S); E := Get_First_Edge (S1); while E /= No_Edge loop Next_E := Get_Next_Edge (E); Set_Next_Edge (E, First_E); Set_Edge_State (E, S); First_E := E; E := Next_E; end loop; Set_First_Edge (S, First_E); Set_First_Edge (S1, No_Edge); -- Move the active state if it is deleted. if Get_Active_State (N) = S1 then Set_Active_State (N, S); end if; Remove_State (N, S1); end Merge_State; procedure Merge_State_Dest_1 is new Merge_State (Get_First_Edge_Reverse => Get_First_Src_Edge, Get_First_Edge => Get_First_Dest_Edge, Set_First_Edge => Set_First_Dest_Edge, Get_Next_Edge => Get_Next_Dest_Edge, Set_Next_Edge => Set_Next_Dest_Edge, Set_Edge_State => Set_Edge_Dest); procedure Merge_State_Dest (N : NFA; S : NFA_State; S1 : NFA_State) renames Merge_State_Dest_1; procedure Merge_State_Src_1 is new Merge_State (Get_First_Edge_Reverse => Get_First_Dest_Edge, Get_First_Edge => Get_First_Src_Edge, Set_First_Edge => Set_First_Src_Edge, Get_Next_Edge => Get_Next_Src_Edge, Set_Next_Edge => Set_Next_Src_Edge, Set_Edge_State => Set_Edge_Src); procedure Merge_State_Src (N : NFA; S : NFA_State; S1 : NFA_State) renames Merge_State_Src_1; procedure Sort_Outgoing_Edges (N : NFA; Nbr_States : Natural) is Last_State : constant NFA_State := NFA_State (Nbr_States) - 1; type Edge_Array is array (0 .. Last_State) of NFA_Edge; Edges : Edge_Array := (others => No_Edge); S, D : NFA_State; E, Next_E : NFA_Edge; First_Edge, Last_Edge : NFA_Edge; begin -- Iterate on states. S := Get_First_State (N); while S /= No_State loop -- Create an array of edges E := Get_First_Dest_Edge (S); while E /= No_Edge loop Next_E := Get_Next_Dest_Edge (E); D := Get_Edge_Dest (E); if Edges (D) /= No_Edge then -- TODO: merge edges. raise Program_Error; end if; Edges (D) := E; E := Next_E; end loop; -- Rebuild the edge list (sorted by destina
/*
 *  nextpnr -- Next Generation Place and Route
 *
 *  Copyright (C) 2021  Symbiflow Authors
 *
 *
 *  Permission to use, copy, modify, and/or distribute this software for any
 *  purpose with or without fee is hereby granted, provided that the above
 *  copyright notice and this permission notice appear in all copies.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 *  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 *  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 *  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 *  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 *
 */

#include "design_utils.h"
#include "log.h"
#include "nextpnr.h"
#include "util.h"

NEXTPNR_NAMESPACE_BEGIN

static const MacroPOD *lookup_macro(const ChipInfoPOD *chip, IdString cell_type)
{
    for (const auto &macro : chip->macros) {
        if (IdString(macro.name) == cell_type)
            return &macro;
    }
    return nullptr;
}

static const MacroExpansionPOD *lookup_macro_rules(const ChipInfoPOD *chip, IdString cell_type)
{
    for (const auto &rule : chip->macro_rules) {
        if (IdString(rule.prim_name) == cell_type)
            return &rule;
    }
    return nullptr;
}

static IdString derived_name(Context *ctx, IdString base_name, IdString suffix)
{
    return ctx->id(stringf("%s/%s", base_name.c_str(ctx), suffix.c_str(ctx)));
}

void Arch::expand_macros()
{
    // Make up a list of cells, so we don't have modify-while-iterating issues
    Context *ctx = getCtx();
    std::vector<CellInfo *> cells;
    for (auto &cell : ctx->cells)
        cells.push_back(cell.second.get());

    std::vector<CellInfo *> next_cells;

    bool first_iter = false;
    do {
        // Expand cells
        for (auto cell : cells) {
            // TODO: consult exception map
            const MacroExpansionPOD *exp = lookup_macro_rules(chip_info, cell->type);

            // Block infinite expansion loop due to a macro being expanded in the same primitive.
            // E.g.: OBUFTDS expands into the following cells, with an infinite loop being generated:
            //          - 2 OBUFTDS
            //          - 1 INV
            if (exp && first_iter)
                continue;

            const MacroPOD *macro = lookup_macro(chip_info, exp ? IdString(exp->macro_name) : cell->type);
            if (macro == nullptr)
                continue;

            // Get the ultimate root of this macro expansion
            IdString parent = (cell->macro_parent == IdString()) ? cell->name : cell->macro_parent;
            // Create child instances
            for (const auto &inst : macro->cell_insts) {
                CellInfo *inst_cell =
                        ctx->createCell(derived_name(ctx, cell->name, IdString(inst.name)), IdString(inst.type));
                for (const auto &param : inst.parameters) {
                    inst_cell->params[IdString(param.key)] = IdString(param.value).str(ctx);
                }
                inst_cell->macro_parent = parent;
                next_cells.push_back(inst_cell);
            }
            // Create and connect nets
            for (const auto &net_data : macro->nets) {
                NetInfo *net = nullptr;
                // If there is a top level port, use that as the net
                for (const auto &net_port : net_data.ports) {
                    if (net_port.instance != 0)
                        continue;
                    // TODO: case of multiple top level ports on the same net?
                    NPNR_ASSERT(net == nullptr);
                    // Use the corresponding pre-expansion port net
                    net = get_net_or_empty(cell, IdString(net_port.port));
                    // Disconnect the original port pre-expansion
                    disconnect_port(ctx, cell, IdString(net_port.port));
                }
                // If not on a top level port, create a new net
                if (net == nullptr)
                    net = ctx->createNet(derived_name(ctx, cell->name, IdString(net_data.name)));
                // Create and connect instance ports
                for (const auto &net_port : net_data.ports) {
                    if (net_port.instance == 0)
                        continue;
                    IdString port_name(net_port.port);
                    CellInfo *inst_cell =
                            ctx->cells.at(derived_name(ctx, cell->name, IdString(net_port.instance))).get();
                    inst_cell->ports[port_name].name = port_name;
                    inst_cell->ports[port_name].type = PortType(net_port.dir);
                    connect_port(ctx, net, inst_cell, port_name);
                }
            }

            if (exp != nullptr) {
                // Convert parameters, according to the exception rules
                for (const auto &param_rule : exp->param_rules) {
                    IdString prim_param(param_rule.prim_param);
                    if (!cell->params.count(prim_param))
                        continue;
                    const auto &prim_param_val = cell->params.at(prim_param);
                    IdString inst_name = derived_name(ctx, cell->name, IdString(param_rule.inst_name));
                    CellInfo *inst_cell = ctx->cells.at(inst_name).get();
                    IdString inst_param(param_rule.inst_param);
                    if (param_rule.rule_type == PARAM_MAP_COPY) {
                        inst_cell->params[inst_param] = prim_param_val;
                    } else if (param_rule.rule_type == PARAM_MAP_SLICE) {
                        auto prim_bits = cell_parameters.parse_int_like(ctx, cell->type, prim_param, prim_param_val);
                        Property value(0, param_rule.slice_bits.ssize());
                        for (int i = 0; i < param_rule.slice_bits.ssize(); i++) {
                            size_t bit = param_rule.slice_bits[i];
                            if (bit >= prim_bits.size())
                                continue;
                            value.str.at(i) = prim_bits.get(bit) ? Property::S1 : Property::S0;
                        }
                        inst_cell->params[inst_param] = value;
                    } else if (param_rule.rule_type == PARAM_MAP_TABLE) {
                        const std::string &prim_str = prim_param_val.as_string();
                        IdString prim_id = ctx->id(prim_str);
                        for (auto &tbl_entry : param_rule.map_table) {
                            if (IdString(tbl_entry.key) == prim_id) {
                                inst_cell->params[inst_param] = IdString(tbl_entry.value).str(ctx);
                                break;
                            }
                        }
                        if (!inst_cell->params.count(inst_param))
                            log_error("Unsupported value '%s' for property '%s' of cell %s:%s\n", prim_str.c_str(),
                                      ctx->nameOf(prim_param), ctx->nameOf(cell), ctx->nameOf(cell->type));
                    }
                }
            }

            // Remove the now-expanded cell, but first make sure we don't leave behind any dangling references
            for (const auto &port : cell->ports)
                if (port.second.net != nullptr)
                    log_error("Macro expansion of %s:%s left dangling port %s.", ctx->nameOf(cell),
                              ctx->nameOf(cell->type), ctx->nameOf(port.first));
            ctx->cells.erase(cell->name);
        }

        // Iterate until no more expansions are possible
        // The next iteration only needs to look at cells created in this iteration
        std::swap(next_cells, cells);
        next_cells.clear();

        first_iter = true;
    } while (!cells.empty());
    // Do this at the end, otherwise we might add cells that are later destroyed
    for (auto &cell : ctx->cells)
        macro_to_cells[cell.second->macro_parent].push_back(cell.second.get());
}

NEXTPNR_NAMESPACE_END
generated by cgit v1.2.3 (git 2.25.1) at 2025-05-28 19:29:55 +0000