Как выполнить поиск в глубину (DFS) внутри модуля, начиная с его портов?

Я пытаюсь реализовать новый проход для вычисления последовательной глубины и сложности данного модуля в 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]))));

но проблема в том, что я не могу найти ячейки, которые сразу подключены к входным портам оттуда (для этого нет APR в типах wires/sigspec/sigpool).

Любая помощь/подсказка будет принята с благодарностью.


yosys
person Mehrdad    schedule 20.05.2016    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Я думаю, что следующий пример кода (хотя и не 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 для создания канонических представлений сигнальных битов (в случае, если два провода соединены друг с другом и являются просто «псевдонимами» для одного и того же фактического бита).

  • Разбейте свой алгоритм на два этапа: (1) создайте необходимые структуры индексов и (2) выполните фактический алгоритм.

Вы также можете найти ответы на этот и этот вопрос полезны.

(Я пишу этот ответ в спешке. Пожалуйста, задавайте дополнительные вопросы в комментариях ниже, если что-то неясно.)

person CliffordVienna    schedule 21.05.2016

arrow_upward
1
arrow_downward

Я смог реализовать эту часть следующим образом, это работает, но я не уверен, что это лучший способ. любой совет/комментарий будет принят с благодарностью.

// 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;
    }
  }
person Mehrdad    schedule 20.05.2016