如何从其端口开始在模块内执行深度优先搜索（DFS）？

Question

我正在尝试实现一个新的通道来计算 Yosys 中给定模块的顺序深度和复杂性。为此，我受到了 scc pass 的启发。要实现它，我需要专门从模块的输入端口开始执行 DFS。为此，我试图找到所有立即连接到输入端口的单元格。我从模块的端口开始并找到关联线：

SigPool inputPorts;
for (auto &it : module->ports) 
  if (module->wires_[it]->port_input)  
     inputPorts.add((sigmap(RTLIL::SigSpec(module->wires_[it]))));

但我遇到的问题是我无法从那里找到立即连接到输入端口的单元（在 wires/sigspec/sigpool 类型中没有用于该目的的 APR）。

任何 help/hint 将不胜感激。

Answer 1

我能够按如下方式实现该部分，可行，但我不确定这是否是最佳方式。任何 advice/comment 将不胜感激。

// for all input the cells of the module find its incoming signals (inputSignals in this code), and for each bit of them do the following:
for (auto &bit : inputSignals)
  if (bit.wire != NULL) {
    if (inputPortsSet.count(bit.wire->port_id)) {
      log ("found an input port\n");
      log ("%s :",cell->name.c_str());
      log(" %s ", bit.wire->name.c_str());
      log(" %d \n", bit.wire->port_id);       
      break;
    }
  }

Answer 2

我认为以下代码示例（尽管不是 DFS）应该包含您需要的所有相关惯用 Yosys 代码片段：

    // create canonical versions of all sigbits
    SigMap sigmap(module);

    // first layer of bits
    pool<SigBit> input_bits;

    for (auto wire : module->wires())
        if (wire->port_input)
            for (auto bit : sigmap(wire))
                input_bits.insert(bit);

    // index: from sigbit to driven cells
    dict<SigBit, pool<Cell*>> bit2cells;

    // index: from cell to driven sigbits
    dict<Cell*, pool<SigBit>> cell2bits;

    for (auto cell : module->cells())
    for (auto &conn : cell->connections()) {
        if (cell->input(conn.first)) {
            for (auto bit : sigmap(conn.second))
                bit2cells[bit].insert(cell);
        }
        if (cell->output(conn.first)) {
            for (auto bit : sigmap(conn.second))
                cell2bits[cell].insert(bit);
        }
    }

    pool<SigBit> queue = input_bits;
    pool<Cell*> visited_cells;

    while (!queue.empty())
    {
        log("------\n");

        pool<Cell*> this_iter_cells;

        for (auto bit : queue)
        for (auto cell : bit2cells[bit])
            if (!visited_cells.count(cell)) {
                log("  %s\n", log_id(cell));
                visited_cells.insert(cell);
                this_iter_cells.insert(cell);
            }

        queue.clear();
        for (auto cell : this_iter_cells)
        for (auto bit : cell2bits[cell])
            queue.insert(bit);
    }

最重要的事情是：

使用SigMap创建信号位的规范表示（如果两条线相互连接并且只是"alias names"相同的实际位）。
将您的算法分为两个阶段：(1) 创建您需要的索引结构，(2) 执行实际算法。

您可能还会发现 and 问题的答案很有用。

（仓促写下，有不明白的请在下方评论区提问）

如何从其端口开始在模块内执行深度优先搜索（DFS）？

How to perform Depth First Search (DFS) inside a module starting from its ports?

yosys