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

Question

I am trying to implement a new pass to calculate the sequential depth and complexity of a given module in Yosys. To do so, I am getting inspired by scc pass. To implement it, I need to specifically perform DFS starting from the module's input ports. To do so, I am trying to find all of the cells which are immediately connected to the input ports. I am starting from the module's port and find the associate wires:

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

but the problem that I have is that I am not able to find the cells which are immediately connected to the input ports from there (there is not APR for that purpose in the wires/sigspec/sigpool types).

Any help/hint would be greatly appreciated.

Answer 1

I think the following code example (although not DFS) should contain all the relevant idiomatic Yosys code snippets that you'd need:

    // 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);
    }

The most important things to take away from that:

• Use SigMap to create canonical representations of signal bits (in case two wires are connected to each other and are just "alias names" for the same actual bit).

• Break up your algorithm in two stages: (1) create the index structures that you need and (2) perform the actual algorithm.

You might also find the answers to this and this question useful.

(I'm writing this answer in a hurry.. Please ask further questions in comments below if anything is unclear.)