From cd0fe7d7860f490b43cacb37752fe9bf983e2279 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Sun, 3 Nov 2013 22:01:32 +0100 Subject: Added simple topological sort to edif backend --- backends/edif/edif.cc | 32 ++++++++++++++++++++++++++++++-- 1 file changed, 30 insertions(+), 2 deletions(-) diff --git a/backends/edif/edif.cc b/backends/edif/edif.cc index a4d8c175..ced0c8e6 100644 --- a/backends/edif/edif.cc +++ b/backends/edif/edif.cc @@ -198,12 +198,40 @@ struct EdifBackend : public Backend { } fprintf(f, " )\n"); + std::vector sorted_modules; + + // extract module dependencies + std::map> module_deps; + for (auto &mod_it : design->modules) { + module_deps[mod_it.second] = std::set(); + for (auto &cell_it : mod_it.second->cells) + if (design->modules.count(cell_it.second->type) > 0) + module_deps[mod_it.second].insert(design->modules.at(cell_it.second->type)); + } + + // bubble-sort equivialent to topological sort.. + while (module_deps.size() > 0) { + size_t sorted_modules_idx = sorted_modules.size(); + for (auto &it : module_deps) { + for (auto &dep : it.second) + if (module_deps.count(dep) > 0) + goto no_ready_yet; + // log("Next in topological sort: %s\n", RTLIL::id2cstr(it.first->name)); + sorted_modules.push_back(it.first); + no_ready_yet:; + } + if (sorted_modules_idx == sorted_modules.size()) + log_error("Cyclic dependency between modules found! Cycle includes module %s.\n", RTLIL::id2cstr(module_deps.begin()->first->name)); + while (sorted_modules_idx < sorted_modules.size()) + module_deps.erase(sorted_modules.at(sorted_modules_idx++)); + } + + fprintf(f, " (library DESIGN\n"); fprintf(f, " (edifLevel 0)\n"); fprintf(f, " (technology (numberDefinition))\n"); - for (auto module_it : design->modules) + for (auto module : sorted_modules) { - RTLIL::Module *module = module_it.second; if (module->get_bool_attribute("\\placeholder")) continue; -- cgit v1.2.3