diff options
84 files changed, 4792 insertions, 370 deletions
diff --git a/.cirrus.yml b/.cirrus.yml index c97b521c..5cac994e 100644 --- a/.cirrus.yml +++ b/.cirrus.yml @@ -2,7 +2,7 @@ task: name: build-test-ubuntu1604 container: cpu: 4 - memory: 16 + memory: 20 dockerfile: .cirrus/Dockerfile.ubuntu16.04 build_script: mkdir build && cd build && cmake .. -DARCH=all -DTRELLIS_ROOT=/usr/local/src/prjtrellis -DBUILD_TESTS=on && make -j $(nproc) @@ -11,5 +11,6 @@ task: test_ice40_script: cd build && ./nextpnr-ice40-test smoketest_ice40_script: export NEXTPNR=$(pwd)/build/nextpnr-ice40 && cd ice40/smoketest/attosoc && ./smoketest.sh test_ecp5_script: cd build && ./nextpnr-ecp5-test + smoketest_generic_script: export NEXTPNR=$(pwd)/build/nextpnr-generic && cd generic/examples && ./simple.sh regressiontest_ice40_script: make -j $(nproc) -C tests/ice40/regressions NPNR=$(pwd)/build/nextpnr-ice40 regressiontest_ecp5_script: make -j $(nproc) -C tests/ecp5/regressions NPNR=$(pwd)/build/nextpnr-ecp5 diff --git a/.cirrus/Dockerfile.ubuntu16.04 b/.cirrus/Dockerfile.ubuntu16.04 index 1b93cfb8..4b149b7b 100644 --- a/.cirrus/Dockerfile.ubuntu16.04 +++ b/.cirrus/Dockerfile.ubuntu16.04 @@ -8,7 +8,7 @@ RUN set -e -x ;\ apt-get -y install \ build-essential autoconf cmake clang bison wget flex gperf \ libreadline-dev gawk tcl-dev libffi-dev graphviz xdot python3-dev \ - libboost-all-dev qt5-default git libftdi-dev pkg-config + libboost-all-dev qt5-default git libftdi-dev pkg-config libeigen3-dev RUN set -e -x ;\ mkdir -p /usr/local/src ;\ @@ -36,7 +36,7 @@ RUN set -e -x ;\ cd /usr/local/src ;\ git clone --recursive https://github.com/YosysHQ/yosys.git ;\ cd yosys ;\ - git reset --hard 47a5dfdaa4bd7d400c6e3d58476de80904df460d ;\ + git reset --hard ea8ac0aaad3a1f89ead8eb44b2fef5927f29a099 ;\ make -j $(nproc) ;\ make install ;\ rm -rf /usr/local/src/yosys diff --git a/CMakeLists.txt b/CMakeLists.txt index 4f29d132..ade76d60 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -5,6 +5,8 @@ project(nextpnr) option(BUILD_GUI "Build GUI" ON) option(BUILD_PYTHON "Build Python Integration" ON) option(BUILD_TESTS "Build GUI" OFF) +option(BUILD_HEAP "Build HeAP analytic placer" ON) +option(USE_OPENMP "Use OpenMP to accelerate analytic placer" OFF) option(COVERAGE "Add code coverage info" OFF) option(STATIC_BUILD "Create static build" OFF) option(EXTERNAL_CHIPDB "Create build with pre-built chipdb binaries" OFF) @@ -53,12 +55,16 @@ endforeach() set(CMAKE_CXX_STANDARD 11) if (MSVC) -set(CMAKE_CONFIGURATION_TYPES "Debug;Release" CACHE STRING "" FORCE) -set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} /D_DEBUG /W4 /wd4100 /wd4244 /wd4125 /wd4800 /wd4456 /wd4458 /wd4305 /wd4459 /wd4121 /wd4996") -set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} /W4 /wd4100 /wd4244 /wd4125 /wd4800 /wd4456 /wd4458 /wd4305 /wd4459 /wd4121 /wd4996 /wd4127") + set(CMAKE_CONFIGURATION_TYPES "Debug;Release" CACHE STRING "" FORCE) + set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} /D_DEBUG /W4 /wd4100 /wd4244 /wd4125 /wd4800 /wd4456 /wd4458 /wd4305 /wd4459 /wd4121 /wd4996") + set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} /W4 /wd4100 /wd4244 /wd4125 /wd4800 /wd4456 /wd4458 /wd4305 /wd4459 /wd4121 /wd4996 /wd4127") else() -set(CMAKE_CXX_FLAGS_DEBUG "-Wall -fPIC -ggdb -pipe") -set(CMAKE_CXX_FLAGS_RELEASE "-Wall -fPIC -O3 -g -pipe") + set(CMAKE_CXX_FLAGS_DEBUG "-Wall -fPIC -ggdb -pipe") + if (USE_OPENMP) + set(CMAKE_CXX_FLAGS_RELEASE "-Wall -fPIC -O3 -g -pipe -fopenmp") + else() + set(CMAKE_CXX_FLAGS_RELEASE "-Wall -fPIC -O3 -g -pipe") + endif() endif() set(CMAKE_DEFIN) @@ -181,6 +187,14 @@ if (BUILD_PYTHON) endif() include_directories(common/ json/ ${Boost_INCLUDE_DIRS} ${PYTHON_INCLUDE_DIRS}) + +if(BUILD_HEAP) + find_package (Eigen3 REQUIRED NO_MODULE) + include_directories(${EIGEN3_INCLUDE_DIRS}) + add_definitions(${EIGEN3_DEFINITIONS}) + add_definitions(-DWITH_HEAP) +endif() + aux_source_directory(common/ COMMON_SRC_FILES) aux_source_directory(json/ JSON_PARSER_FILES) set(COMMON_FILES ${COMMON_SRC_FILES} ${JSON_PARSER_FILES}) @@ -14,6 +14,9 @@ We hope to see Xilinx 7 Series thanks to supported in the future. We would love your help in developing this awesome new project! +A brief (academic) paper describing the Yosys+nextpnr flow can be found +on [arXiv](https://arxiv.org/abs/1903.10407). + Here is a screenshot of nextpnr for iCE40. Build instructions and [getting started notes](#getting-started) can be found below. @@ -36,10 +39,12 @@ of the selected architecture: - Python 3.5 or later, including development libraries (`python3-dev` for Ubuntu) - on Windows make sure to install same version as supported by [vcpkg](https://github.com/Microsoft/vcpkg/blob/master/ports/python3/CONTROL) - Boost libraries (`libboost-dev libboost-filesystem-dev libboost-thread-dev libboost-program-options-dev libboost-python-dev libboost-dev` or `libboost-all-dev` for Ubuntu) +- Eigen3 (`libeigen3-dev` for Ubuntu) is required to build the analytic placer - Latest git Yosys is required to synthesise the demo design - For building on Windows with MSVC, usage of vcpkg is advised for dependency installation. - - For 32 bit builds: `vcpkg install boost-filesystem boost-program-options boost-thread boost-python qt5-base` - - For 64 bit builds: `vcpkg install boost-filesystem:x64-windows boost-program-options:x64-windows boost-thread:x64-windows boost-python:x64-windows qt5-base:x64-windows` + - For 32 bit builds: `vcpkg install boost-filesystem boost-program-options boost-thread boost-python qt5-base eigen3` + - For 64 bit builds: `vcpkg install boost-filesystem:x64-windows boost-program-options:x64-windows boost-thread:x64-windows boost-python:x64-windows qt5-base:x64-windows eigen3:x64-windows` + - A copy of Python that matches the version in vcpkg (currently Python 3.6.4). You can download the [Embeddable Zip File](https://www.python.org/downloads/release/python-364/) and extract it. You may need to extract `python36.zip` within the embeddable zip file to a new directory called "Lib". - For building on macOS, brew utility is needed. - Install all needed packages `brew install cmake python boost boost-python3 qt5` - Do not forget to add qt5 in path as well `echo 'export PATH="/usr/local/opt/qt/bin:$PATH"' >> ~/.bash_profile` @@ -60,11 +65,18 @@ make -j$(nproc) sudo make install ``` -A simple example that runs on the iCEstick dev board can be found in `ice40/blinky.*`. +On Windows, you may specify paths explicitly: + +``` +cmake -DARCH=ice40 -DICEBOX_ROOT=C:/ProgramData/icestorm/share/icebox -DCMAKE_TOOLCHAIN_FILE=C:/vcpkg/scripts/buildsystems/vcpkg.cmake -DVCPKG_TARGET_TRIPLET=x64-windows -G "Visual Studio 15 2017 Win64" -DPYTHON_EXECUTABLE=C:/Python364/python.exe -DPYTHON_LIBRARY=C:/vcpkg/packages/python3_x64-windows/lib/python36.lib -DPYTHON_INCLUDE_DIR=C:/vcpkg/packages/python3_x64-windows/include/python3.6 +cmake --build . --config Release +``` + +A simple example that runs on the iCEstick dev board can be found in `ice40/examples/blinky/blinky.*`. Usage example: ``` -cd ice40 +cd ice40/examples/blinky yosys -p 'synth_ice40 -top blinky -json blinky.json' blinky.v # synthesize into blinky.json nextpnr-ice40 --hx1k --json blinky.json --pcf blinky.pcf --asc blinky.asc # run place and route icepack blinky.asc blinky.bin # generate binary bitstream file @@ -119,11 +131,11 @@ Use cmake `-D` options to specify which version of nextpnr you want to build. Use `-DARCH=...` to set the architecture. It is a semicolon separated list. Use `cmake . -DARCH=all` to build all supported architectures. -The following runs a debug build of the iCE40 architecture without GUI -and without Python support and only HX1K support: +The following runs a debug build of the iCE40 architecture without GUI, + without Python support, without the HeAP analytic placer and only HX1K support: ``` -cmake -DARCH=ice40 -DCMAKE_BUILD_TYPE=Debug -DBUILD_PYTHON=OFF -DBUILD_GUI=OFF -DICE40_HX1K_ONLY=1 . +cmake -DARCH=ice40 -DCMAKE_BUILD_TYPE=Debug -DBUILD_PYTHON=OFF -DBUILD_GUI=OFF -DBUILD_HEAP=OFF -DICE40_HX1K_ONLY=1 . make -j$(nproc) ``` @@ -134,6 +146,9 @@ cmake -DARCH=ice40 -DBUILD_PYTHON=OFF -DBUILD_GUI=OFF -DSTATIC_BUILD=ON . make -j$(nproc) ``` +The HeAP placer's solver can optionally use OpenMP for a speedup on very large designs. Enable this by passing +`-DUSE_OPENMP=yes` to cmake (compiler support may vary). + You can change the location where nextpnr will be installed (this will usually default to `/usr/local`) by using `-DCMAKE_INSTALL_PREFIX=/install/prefix`. diff --git a/common/command.cc b/common/command.cc index 1399efdb..3eafdb17 100644 --- a/common/command.cc +++ b/common/command.cc @@ -27,6 +27,7 @@ #include "pybindings.h" #endif +#include <boost/algorithm/string/join.hpp> #include <boost/filesystem/convenience.hpp> #include <boost/program_options.hpp> #include <fstream> @@ -86,8 +87,8 @@ bool CommandHandler::executeBeforeContext() if (vm.count("log")) { std::string logfilename = vm["log"].as<std::string>(); - logfile = std::ofstream(logfilename); - if (!logfile) + logfile.open(logfilename); + if (!logfile.is_open()) log_error("Failed to open log file '%s' for writing.\n", logfilename.c_str()); log_streams.push_back(std::make_pair(&logfile, LogLevel::LOG_MSG)); } @@ -106,6 +107,7 @@ po::options_description CommandHandler::getGeneralOptions() general.add_options()("force,f", "keep running after errors"); #ifndef NO_GUI general.add_options()("gui", "start gui"); + general.add_options()("gui-no-aa", "disable anti aliasing (use together with --gui option)"); #endif #ifndef NO_PYTHON general.add_options()("run", po::value<std::vector<std::string>>(), @@ -120,8 +122,18 @@ po::options_description CommandHandler::getGeneralOptions() general.add_options()("json", po::value<std::string>(), "JSON design file to ingest"); general.add_options()("seed", po::value<int>(), "seed value for random number generator"); general.add_options()("randomize-seed,r", "randomize seed value for random number generator"); + + general.add_options()( + "placer", po::value<std::string>(), + std::string("placer algorithm to use; available: " + boost::algorithm::join(Arch::availablePlacers, ", ") + + "; default: " + Arch::defaultPlacer) + .c_str()); + general.add_options()("slack_redist_iter", po::value<int>(), "number of iterations between slack redistribution"); general.add_options()("cstrweight", po::value<float>(), "placer weighting for relative constraint satisfaction"); + general.add_options()("starttemp", po::value<float>(), "placer SA start temperature"); + general.add_options()("placer-budgets", "use budget rather than criticality in placer timing weights"); + general.add_options()("pack-only", "pack design only without placement or routing"); general.add_options()("ignore-loops", "ignore combinational loops in timing analysis"); @@ -183,10 +195,27 @@ void CommandHandler::setupContext(Context *ctx) settings->set("timing/allowFail", true); } + if (vm.count("placer")) { + std::string placer = vm["placer"].as<std::string>(); + if (std::find(Arch::availablePlacers.begin(), Arch::availablePlacers.end(), placer) == + Arch::availablePlacers.end()) + log_error("Placer algorithm '%s' is not supported (available options: %s)\n", placer.c_str(), + boost::algorithm::join(Arch::availablePlacers, ", ").c_str()); + settings->set("placer", placer); + } else { + settings->set("placer", Arch::defaultPlacer); + } + if (vm.count("cstrweight")) { settings->set("placer1/constraintWeight", vm["cstrweight"].as<float>()); } + if (vm.count("starttemp")) { + settings->set("placer1/startTemp", vm["starttemp"].as<float>()); + } + if (vm.count("placer-budgets")) { + settings->set("placer1/budgetBased", true); + } if (vm.count("freq")) { auto freq = vm["freq"].as<double>(); if (freq > 0) @@ -207,7 +236,7 @@ int CommandHandler::executeMain(std::unique_ptr<Context> ctx) #ifndef NO_GUI if (vm.count("gui")) { - Application a(argc, argv); + Application a(argc, argv, (vm.count("gui-no-aa") > 0)); MainWindow w(std::move(ctx), chipArgs); try { if (vm.count("json")) { diff --git a/common/design_utils.cc b/common/design_utils.cc index da170030..bdf5ca5c 100644 --- a/common/design_utils.cc +++ b/common/design_utils.cc @@ -129,4 +129,21 @@ void connect_ports(Context *ctx, CellInfo *cell1, IdString port1_name, CellInfo connect_port(ctx, port1.net, cell2, port2_name); } +void rename_port(Context *ctx, CellInfo *cell, IdString old_name, IdString new_name) +{ + if (!cell->ports.count(old_name)) + return; + PortInfo pi = cell->ports.at(old_name); + if (pi.net != nullptr) { + if (pi.net->driver.cell == cell && pi.net->driver.port == old_name) + pi.net->driver.port = new_name; + for (auto &usr : pi.net->users) + if (usr.cell == cell && usr.port == old_name) + usr.port = new_name; + } + cell->ports.erase(old_name); + pi.name = new_name; + cell->ports[new_name] = pi; +} + NEXTPNR_NAMESPACE_END diff --git a/common/design_utils.h b/common/design_utils.h index 8a42d21f..3eb9024f 100644 --- a/common/design_utils.h +++ b/common/design_utils.h @@ -91,6 +91,9 @@ void disconnect_port(const Context *ctx, CellInfo *cell, IdString port_name); // Connect two ports together void connect_ports(Context *ctx, CellInfo *cell1, IdString port1_name, CellInfo *cell2, IdString port2_name); +// Rename a port if it exists on a cell +void rename_port(Context *ctx, CellInfo *cell, IdString old_name, IdString new_name); + void print_utilisation(const Context *ctx); NEXTPNR_NAMESPACE_END diff --git a/common/nextpnr.cc b/common/nextpnr.cc index bb941d3d..daaadf28 100644 --- a/common/nextpnr.cc +++ b/common/nextpnr.cc @@ -221,6 +221,9 @@ delay_t Context::getNetinfoRouteDelay(const NetInfo *net_info, const PortRef &us return 0; #endif + if (net_info->wires.empty()) + return predictDelay(net_info, user_info); + WireId src_wire = getNetinfoSourceWire(net_info); if (src_wire == WireId()) return 0; @@ -421,4 +424,33 @@ void BaseCtx::addClock(IdString net, float freq) } } +void BaseCtx::createRectangularRegion(IdString name, int x0, int y0, int x1, int y1) +{ + std::unique_ptr<Region> new_region(new Region()); + new_region->name = name; + new_region->constr_bels = true; + new_region->constr_pips = false; + new_region->constr_wires = false; + for (int x = x0; x <= x1; x++) { + for (int y = y0; y <= y1; y++) { + for (auto bel : getCtx()->getBelsByTile(x, y)) + new_region->bels.insert(bel); + } + } + region[name] = std::move(new_region); +} +void BaseCtx::addBelToRegion(IdString name, BelId bel) { region[name]->bels.insert(bel); } +void BaseCtx::constrainCellToRegion(IdString cell, IdString region_name) +{ + cells[cell]->region = region[region_name].get(); +} +DecalXY BaseCtx::constructDecalXY(DecalId decal, float x, float y) +{ + DecalXY dxy; + dxy.decal = decal; + dxy.x = x; + dxy.y = y; + return dxy; +} + NEXTPNR_NAMESPACE_END diff --git a/common/nextpnr.h b/common/nextpnr.h index d58ae529..fc49300e 100644 --- a/common/nextpnr.h +++ b/common/nextpnr.h @@ -181,6 +181,9 @@ struct GraphicElement float x1 = 0, y1 = 0, x2 = 0, y2 = 0, z = 0; std::string text; + GraphicElement(){}; + GraphicElement(type_t type, style_t style, float x1, float y1, float x2, float y2, float z) + : type(type), style(style), x1(x1), y1(y1), x2(x2), y2(y2), z(z){}; }; struct Loc @@ -637,6 +640,12 @@ struct BaseCtx // Intended to simplify Python API void addClock(IdString net, float freq); + void createRectangularRegion(IdString name, int x0, int y0, int x1, int y1); + void addBelToRegion(IdString name, BelId bel); + void constrainCellToRegion(IdString cell, IdString region_name); + + // Workaround for lack of wrappable constructors + DecalXY constructDecalXY(DecalId decal, float x, float y); }; NEXTPNR_NAMESPACE_END diff --git a/common/place_common.cc b/common/place_common.cc index b3eb4267..73a320d0 100644 --- a/common/place_common.cc +++ b/common/place_common.cc @@ -304,7 +304,7 @@ class ConstraintLegaliseWorker // Set the strength to locked on all cells in chain void lockdown_chain(CellInfo *root) { - root->belStrength = STRENGTH_LOCKED; + root->belStrength = STRENGTH_STRONG; for (auto child : root->constr_children) lockdown_chain(child); } @@ -380,7 +380,7 @@ class ConstraintLegaliseWorker rippedCells.insert(confl_cell->name); } } - ctx->bindBel(target, ctx->cells.at(cp.first).get(), STRENGTH_LOCKED); + ctx->bindBel(target, ctx->cells.at(cp.first).get(), STRENGTH_STRONG); rippedCells.erase(cp.first); } for (auto cp : solution) { @@ -529,4 +529,12 @@ int get_constraints_distance(const Context *ctx, const CellInfo *cell) return dist; } +bool check_cell_bel_region(const CellInfo *cell, BelId bel) +{ + if (cell->region != nullptr && cell->region->constr_bels && !cell->region->bels.count(bel)) + return false; + else + return true; +} + NEXTPNR_NAMESPACE_END diff --git a/common/place_common.h b/common/place_common.h index 79dec067..fa5ce4c2 100644 --- a/common/place_common.h +++ b/common/place_common.h @@ -49,6 +49,10 @@ bool legalise_relative_constraints(Context *ctx); // Get the total distance from satisfied constraints for a cell int get_constraints_distance(const Context *ctx, const CellInfo *cell); + +// Check that a Bel is within the region for a cell +bool check_cell_bel_region(const CellInfo *cell, BelId bel); + NEXTPNR_NAMESPACE_END #endif diff --git a/common/placer1.cc b/common/placer1.cc index cec37847..a8ddd8a6 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -24,6 +24,7 @@ #include "placer1.h" #include <algorithm> #include <boost/lexical_cast.hpp> +#include <boost/range/adaptor/reversed.hpp> #include <chrono> #include <cmath> #include <iostream> @@ -43,10 +44,33 @@ #include "timing.h" #include "util.h" +namespace std { +template <> struct hash<std::pair<NEXTPNR_NAMESPACE_PREFIX IdString, std::size_t>> +{ + std::size_t operator()(const std::pair<NEXTPNR_NAMESPACE_PREFIX IdString, std::size_t> &idp) const noexcept + { + std::size_t seed = 0; + boost::hash_combine(seed, hash<NEXTPNR_NAMESPACE_PREFIX IdString>()(idp.first)); + boost::hash_combine(seed, hash<std::size_t>()(idp.second)); + return seed; + } +}; +} // namespace std + NEXTPNR_NAMESPACE_BEGIN class SAPlacer { + private: + struct BoundingBox + { + // Actual bounding box + int x0 = 0, x1 = 0, y0 = 0, y1 = 0; + // Number of cells at each extremity + int nx0 = 0, nx1 = 0, ny0 = 0, ny1 = 0; + wirelen_t hpwl() const { return wirelen_t((x1 - x0) + (y1 - y0)); } + }; + public: SAPlacer(Context *ctx, Placer1Cfg cfg) : ctx(ctx), cfg(cfg) { @@ -78,13 +102,41 @@ class SAPlacer } diameter = std::max(max_x, max_y) + 1; - costs.resize(ctx->nets.size()); + net_bounds.resize(ctx->nets.size()); + net_arc_tcost.resize(ctx->nets.size()); old_udata.reserve(ctx->nets.size()); + net_by_udata.reserve(ctx->nets.size()); decltype(NetInfo::udata) n = 0; for (auto &net : ctx->nets) { old_udata.emplace_back(net.second->udata); + net_arc_tcost.at(n).resize(net.second->users.size()); net.second->udata = n++; + net_by_udata.push_back(net.second.get()); } + for (auto ®ion : sorted(ctx->region)) { + Region *r = region.second; + BoundingBox bb; + if (r->constr_bels) { + bb.x0 = std::numeric_limits<int>::max(); + bb.x1 = std::numeric_limits<int>::min(); + bb.y0 = std::numeric_limits<int>::max(); + bb.y1 = std::numeric_limits<int>::min(); + for (auto bel : r->bels) { + Loc loc = ctx->getBelLocation(bel); + bb.x0 = std::min(bb.x0, loc.x); + bb.x1 = std::max(bb.x1, loc.x); + bb.y0 = std::min(bb.y0, loc.y); + bb.y1 = std::max(bb.y1, loc.y); + } + } else { + bb.x0 = 0; + bb.y0 = 0; + bb.x1 = max_x; + bb.y1 = max_y; + } + region_bounds[r->name] = bb; + } + build_port_index(); } ~SAPlacer() @@ -93,97 +145,122 @@ class SAPlacer net.second->udata = old_udata[net.second->udata]; } - bool place() + bool place(bool refine = false) { log_break(); ctx->lock(); size_t placed_cells = 0; - // Initial constraints placer - for (auto &cell_entry : ctx->cells) { - CellInfo *cell = cell_entry.second.get(); - auto loc = cell->attrs.find(ctx->id("BEL")); - if (loc != cell->attrs.end()) { - std::string loc_name = loc->second; - BelId bel = ctx->getBelByName(ctx->id(loc_name)); - if (bel == BelId()) { - log_error("No Bel named \'%s\' located for " - "this chip (processing BEL attribute on \'%s\')\n", - loc_name.c_str(), cell->name.c_str(ctx)); - } + std::vector<CellInfo *> autoplaced; + std::vector<CellInfo *> chain_basis; + if (!refine) { + // Initial constraints placer + for (auto &cell_entry : ctx->cells) { + CellInfo *cell = cell_entry.second.get(); + auto loc = cell->attrs.find(ctx->id("BEL")); + if (loc != cell->attrs.end()) { + std::string loc_name = loc->second; + BelId bel = ctx->getBelByName(ctx->id(loc_name)); + if (bel == BelId()) { + log_error("No Bel named \'%s\' located for " + "this chip (processing BEL attribute on \'%s\')\n", + loc_name.c_str(), cell->name.c_str(ctx)); + } - IdString bel_type = ctx->getBelType(bel); - if (bel_type != cell->type) { - log_error("Bel \'%s\' of type \'%s\' does not match cell " - "\'%s\' of type \'%s\'\n", - loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx)); - } - if (!ctx->isValidBelForCell(cell, bel)) { - log_error("Bel \'%s\' of type \'%s\' is not valid for cell " - "\'%s\' of type \'%s\'\n", - loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx)); - } + IdString bel_type = ctx->getBelType(bel); + if (bel_type != cell->type) { + log_error("Bel \'%s\' of type \'%s\' does not match cell " + "\'%s\' of type \'%s\'\n", + loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx)); + } + if (!ctx->isValidBelForCell(cell, bel)) { + log_error("Bel \'%s\' of type \'%s\' is not valid for cell " + "\'%s\' of type \'%s\'\n", + loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx)); + } - auto bound_cell = ctx->getBoundBelCell(bel); - if (bound_cell) { - log_error("Cell \'%s\' cannot be bound to bel \'%s\' since it is already bound to cell \'%s\'\n", - cell->name.c_str(ctx), loc_name.c_str(), bound_cell->name.c_str(ctx)); - } + auto bound_cell = ctx->getBoundBelCell(bel); + if (bound_cell) { + log_error( + "Cell \'%s\' cannot be bound to bel \'%s\' since it is already bound to cell \'%s\'\n", + cell->name.c_str(ctx), loc_name.c_str(), bound_cell->name.c_str(ctx)); + } - ctx->bindBel(bel, cell, STRENGTH_USER); - locked_bels.insert(bel); - placed_cells++; + ctx->bindBel(bel, cell, STRENGTH_USER); + locked_bels.insert(bel); + placed_cells++; + } } - } - int constr_placed_cells = placed_cells; - log_info("Placed %d cells based on constraints.\n", int(placed_cells)); - ctx->yield(); + int constr_placed_cells = placed_cells; + log_info("Placed %d cells based on constraints.\n", int(placed_cells)); + ctx->yield(); - // Sort to-place cells for deterministic initial placement - std::vector<CellInfo *> autoplaced; - for (auto &cell : ctx->cells) { - CellInfo *ci = cell.second.get(); - if (ci->bel == BelId()) { - autoplaced.push_back(cell.second.get()); + // Sort to-place cells for deterministic initial placement + + for (auto &cell : ctx->cells) { + CellInfo *ci = cell.second.get(); + if (ci->bel == BelId()) { + autoplaced.push_back(cell.second.get()); + } } - } - std::sort(autoplaced.begin(), autoplaced.end(), [](CellInfo *a, CellInfo *b) { return a->name < b->name; }); - ctx->shuffle(autoplaced); - auto iplace_start = std::chrono::high_resolution_clock::now(); - // Place cells randomly initially - log_info("Creating initial placement for remaining %d cells.\n", int(autoplaced.size())); + std::sort(autoplaced.begin(), autoplaced.end(), [](CellInfo *a, CellInfo *b) { return a->name < b->name; }); + ctx->shuffle(autoplaced); + auto iplace_start = std::chrono::high_resolution_clock::now(); + // Place cells randomly initially + log_info("Creating initial placement for remaining %d cells.\n", int(autoplaced.size())); - for (auto cell : autoplaced) { - place_initial(cell); - placed_cells++; - if ((placed_cells - constr_placed_cells) % 500 == 0) + for (auto cell : autoplaced) { + place_initial(cell); + placed_cells++; + if ((placed_cells - constr_placed_cells) % 500 == 0) + log_info(" initial placement placed %d/%d cells\n", int(placed_cells - constr_placed_cells), + int(autoplaced.size())); + } + if ((placed_cells - constr_placed_cells) % 500 != 0) log_info(" initial placement placed %d/%d cells\n", int(placed_cells - constr_placed_cells), int(autoplaced.size())); + if (cfg.budgetBased && ctx->slack_redist_iter > 0) + assign_budget(ctx); + ctx->yield(); + auto iplace_end = std::chrono::high_resolution_clock::now(); + log_info("Initial placement time %.02fs\n", + std::chrono::duration<float>(iplace_end - iplace_start).count()); + log_info("Running simulated annealing placer.\n"); + } else { + for (auto &cell : ctx->cells) { + CellInfo *ci = cell.second.get(); + if (ci->belStrength > STRENGTH_STRONG) + continue; + else if (ci->constr_parent != nullptr) + continue; + else if (!ci->constr_children.empty() || ci->constr_z != ci->UNCONSTR) + chain_basis.push_back(ci); + else + autoplaced.push_back(ci); + } + require_legal = false; + diameter = 3; + log_info("Running simulated annealing placer for refinement.\n"); } - if ((placed_cells - constr_placed_cells) % 500 != 0) - log_info(" initial placement placed %d/%d cells\n", int(placed_cells - constr_placed_cells), - int(autoplaced.size())); - if (ctx->slack_redist_iter > 0) - assign_budget(ctx); - ctx->yield(); - auto iplace_end = std::chrono::high_resolution_clock::now(); - log_info("Initial placement time %.02fs\n", std::chrono::duration<float>(iplace_end - iplace_start).count()); auto saplace_start = std::chrono::high_resolution_clock::now(); - log_info("Running simulated annealing placer.\n"); - // Calculate metric after initial placement - curr_metric = 0; - curr_tns = 0; - for (auto &net : ctx->nets) { - wirelen_t wl = get_net_metric(ctx, net.second.get(), MetricType::COST, curr_tns); - costs[net.second->udata] = CostChange{wl, -1}; - curr_metric += wl; - } + // Invoke timing analysis to obtain criticalities + if (!cfg.budgetBased) + get_criticalities(ctx, &net_crit); + + // Calculate costs after initial placement + setup_costs(); + moveChange.init(this); + curr_wirelen_cost = total_wirelen_cost(); + curr_timing_cost = total_timing_cost(); + last_wirelen_cost = curr_wirelen_cost; + last_timing_cost = curr_timing_cost; + + wirelen_t avg_wirelen = curr_wirelen_cost; + wirelen_t min_wirelen = curr_wirelen_cost; int n_no_progress = 0; - wirelen_t min_metric = curr_metric; - double avg_metric = curr_metric; - temp = 10000; + temp = refine ? 1e-7 : cfg.startTemp; // Main simulated annealing loop for (int iter = 1;; iter++) { @@ -191,9 +268,9 @@ class SAPlacer improved = false; if (iter % 5 == 0 || iter == 1) - log_info(" at iteration #%d: temp = %f, cost = " - "%.0f, est tns = %.02fns\n", - iter, temp, double(curr_metric), curr_tns); + log_info(" at iteration #%d: temp = %f, timing cost = " + "%.0f, wirelen = %.0f\n", + iter, temp, double(curr_timing_cost), double(curr_wirelen_cost)); for (int m = 0; m < 15; ++m) { // Loop through all automatically placed cells @@ -205,10 +282,35 @@ class SAPlacer if (try_bel != BelId() && try_bel != cell->bel) try_swap_position(cell, try_bel); } + // Also try swapping chains, if applicable + for (auto cb : chain_basis) { + Loc chain_base_loc = ctx->getBelLocation(cb->bel); + BelId try_base = random_bel_for_cell(cb, chain_base_loc.z); + if (try_base != BelId() && try_base != cb->bel) + try_swap_chain(cb, try_base); + } + } + + if (ctx->debug) { + // Verify correctness of incremental wirelen updates + for (size_t i = 0; i < net_bounds.size(); i++) { + auto net = net_by_udata[i]; + if (ignore_net(net)) + continue; + auto &incr = net_bounds.at(i), gold = get_net_bounds(net); + NPNR_ASSERT(incr.x0 == gold.x0); + NPNR_ASSERT(incr.x1 == gold.x1); + NPNR_ASSERT(incr.y0 == gold.y0); + NPNR_ASSERT(incr.y1 == gold.y1); + NPNR_ASSERT(incr.nx0 == gold.nx0); + NPNR_ASSERT(incr.nx1 == gold.nx1); + NPNR_ASSERT(incr.ny0 == gold.ny0); + NPNR_ASSERT(incr.ny1 == gold.ny1); + } } - if (curr_metric < min_metric) { - min_metric = curr_metric; + if (curr_wirelen_cost < min_wirelen) { + min_wirelen = curr_wirelen_cost; improved = true; } @@ -218,9 +320,10 @@ class SAPlacer else n_no_progress++; - if (temp <= 1e-3 && n_no_progress >= 5) { - if (iter % 5 != 0) - log_info(" at iteration #%d: temp = %f, cost = %f\n", iter, temp, double(curr_metric)); + if (temp <= 1e-7 && n_no_progress >= (refine ? 1 : 5)) { + log_info(" at iteration #%d: temp = %f, timing cost = " + "%.0f, wirelen = %.0f \n", + iter, temp, double(curr_timing_cost), double(curr_wirelen_cost)); break; } @@ -228,61 +331,68 @@ class SAPlacer int M = std::max(max_x, max_y) + 1; - double upper = 0.6, lower = 0.4; + if (ctx->verbose) + log("iter #%d: temp = %f, timing cost = " + "%.0f, wirelen = %.0f, dia = %d, Ra = %.02f \n", + iter, temp, double(curr_timing_cost), double(curr_wirelen_cost), diameter, Raccept); - if (curr_metric < 0.95 * avg_metric) { - avg_metric = 0.8 * avg_metric + 0.2 * curr_metric; + if (curr_wirelen_cost < 0.95 * avg_wirelen && curr_wirelen_cost > 0) { + avg_wirelen = 0.8 * avg_wirelen + 0.2 * curr_wirelen_cost; } else { - if (Raccept >= 0.8) { - temp *= 0.7; - } else if (Raccept > upper) { - if (diameter < M) - diameter++; - else - temp *= 0.9; - } else if (Raccept > lower) { + double diam_next = diameter * (1.0 - 0.44 + Raccept); + diameter = std::max<int>(1, std::min<int>(M, int(diam_next + 0.5))); + if (Raccept > 0.96) { + temp *= 0.5; + } else if (Raccept > 0.8) { + temp *= 0.9; + } else if (Raccept > 0.15 && diameter > 1) { temp *= 0.95; } else { - // Raccept < 0.3 - if (diameter > 1) - diameter--; - else - temp *= 0.8; + temp *= 0.8; } } // Once cooled below legalise threshold, run legalisation and start requiring // legal moves only - if (temp < legalise_temp && require_legal) { + if (diameter < legalise_dia && require_legal) { if (legalise_relative_constraints(ctx)) { // Only increase temperature if something was moved autoplaced.clear(); + chain_basis.clear(); for (auto cell : sorted(ctx->cells)) { - if (cell.second->belStrength < STRENGTH_STRONG) + if (cell.second->belStrength <= STRENGTH_STRONG && cell.second->constr_parent == nullptr && + !cell.second->constr_children.empty()) + chain_basis.push_back(cell.second); + else if (cell.second->belStrength < STRENGTH_STRONG) autoplaced.push_back(cell.second); } - temp = post_legalise_temp; - diameter *= post_legalise_dia_scale; + // temp = post_legalise_temp; + // diameter = std::min<int>(M, diameter * post_legalise_dia_scale); ctx->shuffle(autoplaced); // Legalisation is a big change so force a slack redistribution here - if (ctx->slack_redist_iter > 0) + if (ctx->slack_redist_iter > 0 && cfg.budgetBased) assign_budget(ctx, true /* quiet */); } require_legal = false; - } else if (ctx->slack_redist_iter > 0 && iter % ctx->slack_redist_iter == 0) { + } else if (cfg.budgetBased && ctx->slack_redist_iter > 0 && iter % ctx->slack_redist_iter == 0) { assign_budget(ctx, true /* quiet */); } + // Invoke timing analysis to obtain criticalities + if (!cfg.budgetBased && ctx->timing_driven) + get_criticalities(ctx, &net_crit); + // Need to rebuild costs after criticalities change + setup_costs(); + // Reset incremental bounds + moveChange.reset(this); + moveChange.new_net_bounds = net_bounds; + // Recalculate total metric entirely to avoid rounding errors // accumulating over time - curr_metric = 0; - curr_tns = 0; - for (auto &net : ctx->nets) { - wirelen_t wl = get_net_metric(ctx, net.second.get(), MetricType::COST, curr_tns); - costs[net.second->udata] = CostChange{wl, -1}; - curr_metric += wl; - } - + curr_wirelen_cost = total_wirelen_cost(); + curr_timing_cost = total_timing_cost(); + last_wirelen_cost = curr_wirelen_cost; + last_timing_cost = curr_timing_cost; // Let the UI show visualization updates. ctx->yield(); } @@ -334,7 +444,8 @@ class SAPlacer ctx->unbindBel(cell->bel); } IdString targetType = cell->type; - for (auto bel : ctx->getBels()) { + + auto proc_bel = [&](BelId bel) { if (ctx->getBelType(bel) == targetType && ctx->isValidBelForCell(cell, bel)) { if (ctx->checkBelAvail(bel)) { uint64_t score = ctx->rng64(); @@ -352,7 +463,18 @@ class SAPlacer } } } + }; + + if (cell->region != nullptr && cell->region->constr_bels) { + for (auto bel : cell->region->bels) { + proc_bel(bel); + } + } else { + for (auto bel : ctx->getBels()) { + proc_bel(bel); + } } + if (best_bel == BelId()) { if (iters == 0 || ripup_bel == BelId()) log_error("failed to place cell '%s' of type '%s'\n", cell->name.c_str(ctx), cell->type.c_str(ctx)); @@ -373,49 +495,38 @@ class SAPlacer // Attempt a SA position swap, return true on success or false on failure bool try_swap_position(CellInfo *cell, BelId newBel) { - static std::vector<NetInfo *> updates; - updates.clear(); + static const double epsilon = 1e-20; + moveChange.reset(this); + if (!require_legal && is_constrained(cell)) + return false; BelId oldBel = cell->bel; CellInfo *other_cell = ctx->getBoundBelCell(newBel); - if (other_cell != nullptr && other_cell->belStrength > STRENGTH_WEAK) { + if (!require_legal && other_cell != nullptr && + (is_constrained(other_cell) || other_cell->belStrength > STRENGTH_WEAK)) { return false; } int old_dist = get_constraints_distance(ctx, cell); int new_dist; if (other_cell != nullptr) old_dist += get_constraints_distance(ctx, other_cell); - wirelen_t new_metric = 0, delta; + double delta = 0; ctx->unbindBel(oldBel); if (other_cell != nullptr) { ctx->unbindBel(newBel); } - for (const auto &port : cell->ports) { - if (port.second.net != nullptr) { - auto &cost = costs[port.second.net->udata]; - if (cost.new_cost == 0) - continue; - cost.new_cost = 0; - updates.emplace_back(port.second.net); - } - } + ctx->bindBel(newBel, cell, STRENGTH_WEAK); if (other_cell != nullptr) { - for (const auto &port : other_cell->ports) - if (port.second.net != nullptr) { - auto &cost = costs[port.second.net->udata]; - if (cost.new_cost == 0) - continue; - cost.new_cost = 0; - updates.emplace_back(port.second.net); - } + ctx->bindBel(oldBel, other_cell, STRENGTH_WEAK); } - ctx->bindBel(newBel, cell, STRENGTH_WEAK); + add_move_cell(moveChange, cell, oldBel); if (other_cell != nullptr) { - ctx->bindBel(oldBel, other_cell, STRENGTH_WEAK); + add_move_cell(moveChange, other_cell, newBel); } + if (!ctx->isBelLocationValid(newBel) || ((other_cell != nullptr && !ctx->isBelLocationValid(oldBel)))) { ctx->unbindBel(newBel); if (other_cell != nullptr) @@ -423,26 +534,18 @@ class SAPlacer goto swap_fail; } - new_metric = curr_metric; - // Recalculate metrics for all nets touched by the peturbation - for (const auto &net : updates) { - auto &c = costs[net->udata]; - new_metric -= c.curr_cost; - float temp_tns = 0; - wirelen_t net_new_wl = get_net_metric(ctx, net, MetricType::COST, temp_tns); - new_metric += net_new_wl; - c.new_cost = net_new_wl; - } + compute_cost_changes(moveChange); new_dist = get_constraints_distance(ctx, cell); if (other_cell != nullptr) new_dist += get_constraints_distance(ctx, other_cell); - delta = new_metric - curr_metric; - delta += (cfg.constraintWeight / temp) * (new_dist - old_dist); + delta = lambda * (moveChange.timing_delta / std::max<double>(last_timing_cost, epsilon)) + + (1 - lambda) * (double(moveChange.wirelen_delta) / std::max<double>(last_wirelen_cost, epsilon)); + delta += (cfg.constraintWeight / temp) * (new_dist - old_dist) / last_wirelen_cost; n_move++; // SA acceptance criterea - if (delta < 0 || (temp > 1e-6 && (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / temp))) { + if (delta < 0 || (temp > 1e-8 && (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / temp))) { n_accept++; } else { if (other_cell != nullptr) @@ -450,32 +553,149 @@ class SAPlacer ctx->unbindBel(newBel); goto swap_fail; } - curr_metric = new_metric; - for (const auto &net : updates) { - auto &c = costs[net->udata]; - c = CostChange{c.new_cost, -1}; - } - + commit_cost_changes(moveChange); +#if 0 + log_info("swap %s -> %s\n", cell->name.c_str(ctx), ctx->getBelName(newBel).c_str(ctx)); + if (other_cell != nullptr) + log_info("swap %s -> %s\n", other_cell->name.c_str(ctx), ctx->getBelName(oldBel).c_str(ctx)); +#endif return true; swap_fail: ctx->bindBel(oldBel, cell, STRENGTH_WEAK); if (other_cell != nullptr) { ctx->bindBel(newBel, other_cell, STRENGTH_WEAK); } - for (const auto &net : updates) - costs[net->udata].new_cost = -1; + return false; + } + + inline bool is_constrained(CellInfo *cell) + { + return cell->constr_parent != nullptr || !cell->constr_children.empty(); + } + + // Swap the Bel of a cell with another, return the original location + BelId swap_cell_bels(CellInfo *cell, BelId newBel) + { + BelId oldBel = cell->bel; +#if 0 + log_info("%s old: %s new: %s\n", cell->name.c_str(ctx), ctx->getBelName(cell->bel).c_str(ctx), ctx->getBelName(newBel).c_str(ctx)); +#endif + CellInfo *bound = ctx->getBoundBelCell(newBel); + if (bound != nullptr) + ctx->unbindBel(newBel); + ctx->unbindBel(oldBel); + ctx->bindBel(newBel, cell, is_constrained(cell) ? STRENGTH_STRONG : STRENGTH_WEAK); + if (bound != nullptr) + ctx->bindBel(oldBel, bound, is_constrained(bound) ? STRENGTH_STRONG : STRENGTH_WEAK); + return oldBel; + } + + // Discover the relative positions of all cells in a chain + void discover_chain(Loc baseLoc, CellInfo *cell, std::vector<std::pair<CellInfo *, Loc>> &cell_rel) + { + Loc cellLoc = ctx->getBelLocation(cell->bel); + Loc rel{cellLoc.x - baseLoc.x, cellLoc.y - baseLoc.y, cellLoc.z}; + cell_rel.emplace_back(std::make_pair(cell, rel)); + for (auto child : cell->constr_children) + discover_chain(baseLoc, child, cell_rel); + } + + // Attempt to swap a chain with a non-chain + bool try_swap_chain(CellInfo *cell, BelId newBase) + { + std::vector<std::pair<CellInfo *, Loc>> cell_rel; + std::unordered_set<IdString> cells; + std::vector<std::pair<CellInfo *, BelId>> moves_made; + std::vector<std::pair<CellInfo *, BelId>> dest_bels; + double delta = 0; + moveChange.reset(this); + if (ctx->debug) + log_info("finding cells for chain swap %s\n", cell->name.c_str(ctx)); + + Loc baseLoc = ctx->getBelLocation(cell->bel); + discover_chain(baseLoc, cell, cell_rel); + Loc newBaseLoc = ctx->getBelLocation(newBase); + NPNR_ASSERT(newBaseLoc.z == baseLoc.z); + for (const auto &cr : cell_rel) + cells.insert(cr.first->name); + + for (const auto &cr : cell_rel) { + Loc targetLoc = {newBaseLoc.x + cr.second.x, newBaseLoc.y + cr.second.y, cr.second.z}; + BelId targetBel = ctx->getBelByLocation(targetLoc); + if (targetBel == BelId()) + return false; + if (ctx->getBelType(targetBel) != cell->type) + return false; + CellInfo *bound = ctx->getBoundBelCell(targetBel); + // We don't consider swapping chains with other chains, at least for the time being - unless it is + // part of this chain + if (bound != nullptr && !cells.count(bound->name) && + (bound->belStrength >= STRENGTH_STRONG || is_constrained(bound))) + return false; + dest_bels.emplace_back(std::make_pair(cr.first, targetBel)); + } + if (ctx->debug) + log_info("trying chain swap %s\n", cell->name.c_str(ctx)); + // <cell, oldBel> + for (const auto &db : dest_bels) { + BelId oldBel = swap_cell_bels(db.first, db.second); + moves_made.emplace_back(std::make_pair(db.first, oldBel)); + CellInfo *bound = ctx->getBoundBelCell(oldBel); + add_move_cell(moveChange, db.first, oldBel); + if (bound != nullptr) + add_move_cell(moveChange, bound, db.second); + } + for (const auto &mm : moves_made) { + if (!ctx->isBelLocationValid(mm.first->bel) || !check_cell_bel_region(mm.first, mm.first->bel)) + goto swap_fail; + if (!ctx->isBelLocationValid(mm.second)) + goto swap_fail; + CellInfo *bound = ctx->getBoundBelCell(mm.second); + if (bound && !check_cell_bel_region(bound, bound->bel)) + goto swap_fail; + } + compute_cost_changes(moveChange); + delta = lambda * (moveChange.timing_delta / last_timing_cost) + + (1 - lambda) * (double(moveChange.wirelen_delta) / last_wirelen_cost); + n_move++; + // SA acceptance criterea + if (delta < 0 || (temp > 1e-9 && (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / temp))) { + n_accept++; + if (ctx->debug) + log_info("accepted chain swap %s\n", cell->name.c_str(ctx)); + } else { + goto swap_fail; + } + commit_cost_changes(moveChange); + return true; + swap_fail: + for (const auto &entry : boost::adaptors::reverse(moves_made)) + swap_cell_bels(entry.first, entry.second); return false; } // Find a random Bel of the correct type for a cell, within the specified // diameter - BelId random_bel_for_cell(CellInfo *cell) + BelId random_bel_for_cell(CellInfo *cell, int force_z = -1) { IdString targetType = cell->type; Loc curr_loc = ctx->getBelLocation(cell->bel); + int count = 0; + + int dx = diameter, dy = diameter; + if (cell->region != nullptr && cell->region->constr_bels) { + dx = std::min(diameter, (region_bounds[cell->region->name].x1 - region_bounds[cell->region->name].x0) + 1); + dy = std::min(diameter, (region_bounds[cell->region->name].y1 - region_bounds[cell->region->name].y0) + 1); + // Clamp location to within bounds + curr_loc.x = std::max(region_bounds[cell->region->name].x0, curr_loc.x); + curr_loc.x = std::min(region_bounds[cell->region->name].x1, curr_loc.x); + curr_loc.y = std::max(region_bounds[cell->region->name].y0, curr_loc.y); + curr_loc.y = std::min(region_bounds[cell->region->name].y1, curr_loc.y); + } + while (true) { - int nx = ctx->rng(2 * diameter + 1) + std::max(curr_loc.x - diameter, 0); - int ny = ctx->rng(2 * diameter + 1) + std::max(curr_loc.y - diameter, 0); + int nx = ctx->rng(2 * dx + 1) + std::max(curr_loc.x - dx, 0); + int ny = ctx->rng(2 * dy + 1) + std::max(curr_loc.y - dy, 0); int beltype_idx, beltype_cnt; std::tie(beltype_idx, beltype_cnt) = bel_types.at(targetType); if (beltype_cnt < cfg.minBelsForGridPick) @@ -488,41 +708,436 @@ class SAPlacer if (fb.size() == 0) continue; BelId bel = fb.at(ctx->rng(int(fb.size()))); + if (force_z != -1) { + Loc loc = ctx->getBelLocation(bel); + if (loc.z != force_z) + continue; + } + if (!check_cell_bel_region(cell, bel)) + continue; if (locked_bels.find(bel) != locked_bels.end()) continue; + count++; return bel; } } + // Return true if a net is to be entirely ignored + inline bool ignore_net(NetInfo *net) + { + return net->driver.cell == nullptr || net->driver.cell->bel == BelId() || + ctx->getBelGlobalBuf(net->driver.cell->bel); + } + + // Get the bounding box for a net + inline BoundingBox get_net_bounds(NetInfo *net) + { + BoundingBox bb; + NPNR_ASSERT(net->driver.cell != nullptr); + Loc dloc = ctx->getBelLocation(net->driver.cell->bel); + bb.x0 = dloc.x; + bb.x1 = dloc.x; + bb.y0 = dloc.y; + bb.y1 = dloc.y; + bb.nx0 = 1; + bb.nx1 = 1; + bb.ny0 = 1; + bb.ny1 = 1; + for (auto user : net->users) { + if (user.cell->bel == BelId()) + continue; + Loc uloc = ctx->getBelLocation(user.cell->bel); + if (bb.x0 == uloc.x) + ++bb.nx0; + else if (uloc.x < bb.x0) { + bb.x0 = uloc.x; + bb.nx0 = 1; + } + if (bb.x1 == uloc.x) + ++bb.nx1; + else if (uloc.x > bb.x1) { + bb.x1 = uloc.x; + bb.nx1 = 1; + } + if (bb.y0 == uloc.y) + ++bb.ny0; + else if (uloc.y < bb.y0) { + bb.y0 = uloc.y; + bb.ny0 = 1; + } + if (bb.y1 == uloc.y) + ++bb.ny1; + else if (uloc.y > bb.y1) { + bb.y1 = uloc.y; + bb.ny1 = 1; + } + } + + return bb; + } + + // Get the timing cost for an arc of a net + inline double get_timing_cost(NetInfo *net, size_t user) + { + int cc; + if (net->driver.cell == nullptr) + return 0; + if (ctx->getPortTimingClass(net->driver.cell, net->driver.port, cc) == TMG_IGNORE) + return 0; + if (cfg.budgetBased) { + double delay = ctx->getDelayNS(ctx->predictDelay(net, net->users.at(user))); + return std::min(10.0, std::exp(delay - ctx->getDelayNS(net->users.at(user).budget) / 10)); + } else { + auto crit = net_crit.find(net->name); + if (crit == net_crit.end() || crit->second.criticality.empty()) + return 0; + double delay = ctx->getDelayNS(ctx->predictDelay(net, net->users.at(user))); + return delay * std::pow(crit->second.criticality.at(user), crit_exp); + } + } + + // Set up the cost maps + void setup_costs() + { + for (auto net : sorted(ctx->nets)) { + NetInfo *ni = net.second; + if (ignore_net(ni)) + continue; + net_bounds[ni->udata] = get_net_bounds(ni); + if (ctx->timing_driven && int(ni->users.size()) < cfg.timingFanoutThresh) + for (size_t i = 0; i < ni->users.size(); i++) + net_arc_tcost[ni->udata][i] = get_timing_cost(ni, i); + } + } + + // Get the total wiring cost for the design + wirelen_t total_wirelen_cost() + { + wirelen_t cost = 0; + for (const auto &net : net_bounds) + cost += net.hpwl(); + return cost; + } + + // Get the total timing cost for the design + double total_timing_cost() + { + double cost = 0; + for (const auto &net : net_arc_tcost) { + for (auto arc_cost : net) { + cost += arc_cost; + } + } + return cost; + } + + // Cost-change-related data for a move + struct MoveChangeData + { + + enum BoundChangeType + { + NO_CHANGE, + CELL_MOVED_INWARDS, + CELL_MOVED_OUTWARDS, + FULL_RECOMPUTE + }; + + std::vector<decltype(NetInfo::udata)> bounds_changed_nets_x, bounds_changed_nets_y; + std::vector<std::pair<decltype(NetInfo::udata), size_t>> changed_arcs; + + std::vector<BoundChangeType> already_bounds_changed_x, already_bounds_changed_y; + std::vector<std::vector<bool>> already_changed_arcs; + + std::vector<BoundingBox> new_net_bounds; + std::vector<std::pair<std::pair<decltype(NetInfo::udata), size_t>, double>> new_arc_costs; + + wirelen_t wirelen_delta = 0; + double timing_delta = 0; + + void init(SAPlacer *p) + { + already_bounds_changed_x.resize(p->ctx->nets.size()); + already_bounds_changed_y.resize(p->ctx->nets.size()); + already_changed_arcs.resize(p->ctx->nets.size()); + for (auto &net : p->ctx->nets) { + already_changed_arcs.at(net.second->udata).resize(net.second->users.size()); + } + new_net_bounds = p->net_bounds; + } + + void reset(SAPlacer *p) + { + for (auto bc : bounds_changed_nets_x) { + new_net_bounds[bc] = p->net_bounds[bc]; + already_bounds_changed_x[bc] = NO_CHANGE; + } + for (auto bc : bounds_changed_nets_y) { + new_net_bounds[bc] = p->net_bounds[bc]; + already_bounds_changed_y[bc] = NO_CHANGE; + } + for (const auto &tc : changed_arcs) + already_changed_arcs[tc.first][tc.second] = false; + bounds_changed_nets_x.clear(); + bounds_changed_nets_y.clear(); + changed_arcs.clear(); + new_arc_costs.clear(); + wirelen_delta = 0; + timing_delta = 0; + } + + } moveChange; + + void add_move_cell(MoveChangeData &mc, CellInfo *cell, BelId old_bel) + { + Loc curr_loc = ctx->getBelLocation(cell->bel); + Loc old_loc = ctx->getBelLocation(old_bel); + // Check net bounds + for (const auto &port : cell->ports) { + NetInfo *pn = port.second.net; + if (pn == nullptr) + continue; + if (ignore_net(pn)) + continue; + BoundingBox &curr_bounds = mc.new_net_bounds[pn->udata]; + // Incremental bounding box updates + // Note that everything other than full updates are applied immediately rather than being queued, + // so further updates to the same net in the same move are dealt with correctly. + // If a full update is already queued, this can be considered a no-op + if (mc.already_bounds_changed_x[pn->udata] != MoveChangeData::FULL_RECOMPUTE) { + // Bounds x0 + if (curr_loc.x < curr_bounds.x0) { + // Further out than current bounds x0 + curr_bounds.x0 = curr_loc.x; + curr_bounds.nx0 = 1; + if (mc.already_bounds_changed_x[pn->udata] == MoveChangeData::NO_CHANGE) { + // Checking already_bounds_changed_x ensures that each net is only added once + // to bounds_changed_nets, lest we add its HPWL change multiple times skewing the + // overall cost change + mc.already_bounds_changed_x[pn->udata] = MoveChangeData::CELL_MOVED_OUTWARDS; + mc.bounds_changed_nets_x.push_back(pn->udata); + } + } else if (curr_loc.x == curr_bounds.x0 && old_loc.x > curr_bounds.x0) { + curr_bounds.nx0++; + if (mc.already_bounds_changed_x[pn->udata] == MoveChangeData::NO_CHANGE) { + mc.already_bounds_changed_x[pn->udata] = MoveChangeData::CELL_MOVED_OUTWARDS; + mc.bounds_changed_nets_x.push_back(pn->udata); + } + } else if (old_loc.x == curr_bounds.x0 && curr_loc.x > curr_bounds.x0) { + if (mc.already_bounds_changed_x[pn->udata] == MoveChangeData::NO_CHANGE) + mc.bounds_changed_nets_x.push_back(pn->udata); + if (curr_bounds.nx0 == 1) { + mc.already_bounds_changed_x[pn->udata] = MoveChangeData::FULL_RECOMPUTE; + } else { + curr_bounds.nx0--; + if (mc.already_bounds_changed_x[pn->udata] == MoveChangeData::NO_CHANGE) + mc.already_bounds_changed_x[pn->udata] = MoveChangeData::CELL_MOVED_INWARDS; + } + } + + // Bounds x1 + if (curr_loc.x > curr_bounds.x1) { + // Further out than current bounds x1 + curr_bounds.x1 = curr_loc.x; + curr_bounds.nx1 = 1; + if (mc.already_bounds_changed_x[pn->udata] == MoveChangeData::NO_CHANGE) { + // Checking already_bounds_changed_x ensures that each net is only added once + // to bounds_changed_nets, lest we add its HPWL change multiple times skewing the + // overall cost change + mc.already_bounds_changed_x[pn->udata] = MoveChangeData::CELL_MOVED_OUTWARDS; + mc.bounds_changed_nets_x.push_back(pn->udata); + } + } else if (curr_loc.x == curr_bounds.x1 && old_loc.x < curr_bounds.x1) { + curr_bounds.nx1++; + if (mc.already_bounds_changed_x[pn->udata] == MoveChangeData::NO_CHANGE) { + mc.already_bounds_changed_x[pn->udata] = MoveChangeData::CELL_MOVED_OUTWARDS; + mc.bounds_changed_nets_x.push_back(pn->udata); + } + } else if (old_loc.x == curr_bounds.x1 && curr_loc.x < curr_bounds.x1) { + if (mc.already_bounds_changed_x[pn->udata] == MoveChangeData::NO_CHANGE) + mc.bounds_changed_nets_x.push_back(pn->udata); + if (curr_bounds.nx1 == 1) { + mc.already_bounds_changed_x[pn->udata] = MoveChangeData::FULL_RECOMPUTE; + } else { + curr_bounds.nx1--; + if (mc.already_bounds_changed_x[pn->udata] == MoveChangeData::NO_CHANGE) + mc.already_bounds_changed_x[pn->udata] = MoveChangeData::CELL_MOVED_INWARDS; + } + } + } + if (mc.already_bounds_changed_y[pn->udata] != MoveChangeData::FULL_RECOMPUTE) { + // Bounds y0 + if (curr_loc.y < curr_bounds.y0) { + // Further out than current bounds y0 + curr_bounds.y0 = curr_loc.y; + curr_bounds.ny0 = 1; + if (mc.already_bounds_changed_y[pn->udata] == MoveChangeData::NO_CHANGE) { + mc.already_bounds_changed_y[pn->udata] = MoveChangeData::CELL_MOVED_OUTWARDS; + mc.bounds_changed_nets_y.push_back(pn->udata); + } + } else if (curr_loc.y == curr_bounds.y0 && old_loc.y > curr_bounds.y0) { + curr_bounds.ny0++; + if (mc.already_bounds_changed_y[pn->udata] == MoveChangeData::NO_CHANGE) { + mc.already_bounds_changed_y[pn->udata] = MoveChangeData::CELL_MOVED_OUTWARDS; + mc.bounds_changed_nets_y.push_back(pn->udata); + } + } else if (old_loc.y == curr_bounds.y0 && curr_loc.y > curr_bounds.y0) { + if (mc.already_bounds_changed_y[pn->udata] == MoveChangeData::NO_CHANGE) + mc.bounds_changed_nets_y.push_back(pn->udata); + if (curr_bounds.ny0 == 1) { + mc.already_bounds_changed_y[pn->udata] = MoveChangeData::FULL_RECOMPUTE; + } else { + curr_bounds.ny0--; + if (mc.already_bounds_changed_y[pn->udata] == MoveChangeData::NO_CHANGE) + mc.already_bounds_changed_y[pn->udata] = MoveChangeData::CELL_MOVED_INWARDS; + } + } + + // Bounds y1 + if (curr_loc.y > curr_bounds.y1) { + // Further out than current bounds y1 + curr_bounds.y1 = curr_loc.y; + curr_bounds.ny1 = 1; + if (mc.already_bounds_changed_y[pn->udata] == MoveChangeData::NO_CHANGE) { + mc.already_bounds_changed_y[pn->udata] = MoveChangeData::CELL_MOVED_OUTWARDS; + mc.bounds_changed_nets_y.push_back(pn->udata); + } + } else if (curr_loc.y == curr_bounds.y1 && old_loc.y < curr_bounds.y1) { + curr_bounds.ny1++; + if (mc.already_bounds_changed_y[pn->udata] == MoveChangeData::NO_CHANGE) { + mc.already_bounds_changed_y[pn->udata] = MoveChangeData::CELL_MOVED_OUTWARDS; + mc.bounds_changed_nets_y.push_back(pn->udata); + } + } else if (old_loc.y == curr_bounds.y1 && curr_loc.y < curr_bounds.y1) { + if (mc.already_bounds_changed_y[pn->udata] == MoveChangeData::NO_CHANGE) + mc.bounds_changed_nets_y.push_back(pn->udata); + if (curr_bounds.ny1 == 1) { + mc.already_bounds_changed_y[pn->udata] = MoveChangeData::FULL_RECOMPUTE; + } else { + curr_bounds.ny1--; + if (mc.already_bounds_changed_y[pn->udata] == MoveChangeData::NO_CHANGE) + mc.already_bounds_changed_y[pn->udata] = MoveChangeData::CELL_MOVED_INWARDS; + } + } + } + + if (ctx->timing_driven && int(pn->users.size()) < cfg.timingFanoutThresh) { + // Output ports - all arcs change timing + if (port.second.type == PORT_OUT) { + int cc; + TimingPortClass cls = ctx->getPortTimingClass(cell, port.first, cc); + if (cls != TMG_IGNORE) + for (size_t i = 0; i < pn->users.size(); i++) + if (!mc.already_changed_arcs[pn->udata][i]) { + mc.changed_arcs.emplace_back(std::make_pair(pn->udata, i)); + mc.already_changed_arcs[pn->udata][i] = true; + } + } else if (port.second.type == PORT_IN) { + auto usr = fast_port_to_user.at(&port.second); + if (!mc.already_changed_arcs[pn->udata][usr]) { + mc.changed_arcs.emplace_back(std::make_pair(pn->udata, usr)); + mc.already_changed_arcs[pn->udata][usr] = true; + } + } + } + } + } + + void compute_cost_changes(MoveChangeData &md) + { + for (const auto &bc : md.bounds_changed_nets_x) { + if (md.already_bounds_changed_x[bc] == MoveChangeData::FULL_RECOMPUTE) + md.new_net_bounds[bc] = get_net_bounds(net_by_udata[bc]); + } + for (const auto &bc : md.bounds_changed_nets_y) { + if (md.already_bounds_changed_x[bc] != MoveChangeData::FULL_RECOMPUTE && + md.already_bounds_changed_y[bc] == MoveChangeData::FULL_RECOMPUTE) + md.new_net_bounds[bc] = get_net_bounds(net_by_udata[bc]); + } + + for (const auto &bc : md.bounds_changed_nets_x) + md.wirelen_delta += md.new_net_bounds[bc].hpwl() - net_bounds[bc].hpwl(); + for (const auto &bc : md.bounds_changed_nets_y) + if (md.already_bounds_changed_x[bc] == MoveChangeData::NO_CHANGE) + md.wirelen_delta += md.new_net_bounds[bc].hpwl() - net_bounds[bc].hpwl(); + + if (ctx->timing_driven) { + for (const auto &tc : md.changed_arcs) { + double old_cost = net_arc_tcost.at(tc.first).at(tc.second); + double new_cost = get_timing_cost(net_by_udata.at(tc.first), tc.second); + md.new_arc_costs.emplace_back(std::make_pair(tc, new_cost)); + md.timing_delta += (new_cost - old_cost); + md.already_changed_arcs[tc.first][tc.second] = false; + } + } + } + + void commit_cost_changes(MoveChangeData &md) + { + for (const auto &bc : md.bounds_changed_nets_x) + net_bounds[bc] = md.new_net_bounds[bc]; + for (const auto &bc : md.bounds_changed_nets_y) + net_bounds[bc] = md.new_net_bounds[bc]; + for (const auto &tc : md.new_arc_costs) + net_arc_tcost[tc.first.first].at(tc.first.second) = tc.second; + curr_wirelen_cost += md.wirelen_delta; + curr_timing_cost += md.timing_delta; + } + // Build the cell port -> user index + void build_port_index() + { + for (auto net : sorted(ctx->nets)) { + NetInfo *ni = net.second; + for (size_t i = 0; i < ni->users.size(); i++) { + auto &usr = ni->users.at(i); + fast_port_to_user[&(usr.cell->ports.at(usr.port))] = i; + } + } + } + + // Get the combined wirelen/timing metric + inline double curr_metric() { return lambda * curr_timing_cost + (1 - lambda) * curr_wirelen_cost; } + + // Map nets to their bounding box (so we can skip recompute for moves that do not exceed the bounds + std::vector<BoundingBox> net_bounds; + // Map net arcs to their timing cost (criticality * delay ns) + std::vector<std::vector<double>> net_arc_tcost; + + // Fast lookup for cell port to net user index + std::unordered_map<const PortInfo *, size_t> fast_port_to_user; + + // Wirelength and timing cost at last and current iteration + wirelen_t last_wirelen_cost, curr_wirelen_cost; + double last_timing_cost, curr_timing_cost; + + // Criticality data from timing analysis + NetCriticalityMap net_crit; + Context *ctx; - wirelen_t curr_metric = std::numeric_limits<wirelen_t>::max(); - float curr_tns = 0; - float temp = 1000; + float temp = 10; + float crit_exp = 8; + float lambda = 0.5; bool improved = false; int n_move, n_accept; int diameter = 35, max_x = 1, max_y = 1; std::unordered_map<IdString, std::tuple<int, int>> bel_types; + std::unordered_map<IdString, BoundingBox> region_bounds; std::vector<std::vector<std::vector<std::vector<BelId>>>> fast_bels; std::unordered_set<BelId> locked_bels; + std::vector<NetInfo *> net_by_udata; + std::vector<decltype(NetInfo::udata)> old_udata; bool require_legal = true; - const float legalise_temp = 1; - const float post_legalise_temp = 10; - const float post_legalise_dia_scale = 1.5; + const int legalise_dia = 4; Placer1Cfg cfg; - - struct CostChange - { - wirelen_t curr_cost; - wirelen_t new_cost; - }; - std::vector<CostChange> costs; - std::vector<decltype(NetInfo::udata)> old_udata; }; Placer1Cfg::Placer1Cfg(Context *ctx) : Settings(ctx) { constraintWeight = get<float>("placer1/constraintWeight", 10); minBelsForGridPick = get<int>("placer1/minBelsForGridPick", 64); + budgetBased = get<bool>("placer1/budgetBased", false); + startTemp = get<float>("placer1/startTemp", 1); + timingFanoutThresh = std::numeric_limits<int>::max(); } bool placer1(Context *ctx, Placer1Cfg cfg) @@ -545,4 +1160,24 @@ bool placer1(Context *ctx, Placer1Cfg cfg) } } +bool placer1_refine(Context *ctx, Placer1Cfg cfg) +{ + try { + SAPlacer placer(ctx, cfg); + placer.place(true); + log_info("Checksum: 0x%08x\n", ctx->checksum()); +#ifndef NDEBUG + ctx->lock(); + ctx->check(); + ctx->unlock(); +#endif + return true; + } catch (log_execution_error_exception) { +#ifndef NDEBUG + ctx->check(); +#endif + return false; + } +} + NEXTPNR_NAMESPACE_END diff --git a/common/placer1.h b/common/placer1.h index 7305f4b1..4c7c7339 100644 --- a/common/placer1.h +++ b/common/placer1.h @@ -29,9 +29,13 @@ struct Placer1Cfg : public Settings Placer1Cfg(Context *ctx); float constraintWeight; int minBelsForGridPick; + bool budgetBased; + float startTemp; + int timingFanoutThresh; }; extern bool placer1(Context *ctx, Placer1Cfg cfg); +extern bool placer1_refine(Context *ctx, Placer1Cfg cfg); NEXTPNR_NAMESPACE_END diff --git a/common/placer_heap.cc b/common/placer_heap.cc new file mode 100644 index 00000000..f9b639f8 --- /dev/null +++ b/common/placer_heap.cc @@ -0,0 +1,1545 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2019 David Shah <david@symbioticeda.com> + * + * 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. + * + * [[cite]] HeAP + * Analytical Placement for Heterogeneous FPGAs, Marcel Gort and Jason H. Anderson + * https://janders.eecg.utoronto.ca/pdfs/marcelfpl12.pdf + * + * [[cite]] SimPL + * SimPL: An Effective Placement Algorithm, Myung-Chul Kim, Dong-Jin Lee and Igor L. Markov + * http://www.ece.umich.edu/cse/awards/pdfs/iccad10-simpl.pdf + * + * Notable changes from the original algorithm + * - Following the other nextpnr placer, Bels are placed rather than CLBs. This means a strict legalisation pass is + * added in addition to coarse legalisation (referred to as "spreading" to avoid confusion with strict legalisation) + * as described in HeAP to ensure validity. This searches random bels in the vicinity of the position chosen by + * spreading, with diameter increasing over iterations, with a heuristic to prefer lower wirelength choices. + * - To make the placer timing-driven, the bound2bound weights are multiplied by (1 + 10 * crit^2) + */ + +#ifdef WITH_HEAP + +#include "placer_heap.h" +#include <Eigen/Core> +#include <Eigen/IterativeLinearSolvers> +#include <boost/optional.hpp> +#include <chrono> +#include <deque> +#include <fstream> +#include <numeric> +#include <queue> +#include <thread> +#include <tuple> +#include <unordered_map> +#include "log.h" +#include "nextpnr.h" +#include "place_common.h" +#include "placer1.h" +#include "timing.h" +#include "util.h" +NEXTPNR_NAMESPACE_BEGIN + +namespace { +// A simple internal representation for a sparse system of equations Ax = rhs +// This is designed to decouple the functions that build the matrix to the engine that +// solves it, and the representation that requires +template <typename T> struct EquationSystem +{ + + EquationSystem(size_t rows, size_t cols) + { + A.resize(cols); + rhs.resize(rows); + } + + // Simple sparse format, easy to convert to CCS for solver + std::vector<std::vector<std::pair<int, T>>> A; // col -> (row, x[row, col]) sorted by row + std::vector<T> rhs; // RHS vector + void reset() + { + for (auto &col : A) + col.clear(); + std::fill(rhs.begin(), rhs.end(), T()); + } + + void add_coeff(int row, int col, T val) + { + auto &Ac = A.at(col); + // Binary search + int b = 0, e = int(Ac.size()) - 1; + while (b <= e) { + int i = (b + e) / 2; + if (Ac.at(i).first == row) { + Ac.at(i).second += val; + return; + } + if (Ac.at(i).first > row) + e = i - 1; + else + b = i + 1; + } + Ac.insert(Ac.begin() + b, std::make_pair(row, val)); + } + + void add_rhs(int row, T val) { rhs[row] += val; } + + void solve(std::vector<T> &x) + { + using namespace Eigen; + if (x.empty()) + return; + NPNR_ASSERT(x.size() == A.size()); + + VectorXd vx(x.size()), vb(rhs.size()); + SparseMatrix<T> mat(A.size(), A.size()); + + std::vector<int> colnnz; + for (auto &Ac : A) + colnnz.push_back(int(Ac.size())); + mat.reserve(colnnz); + for (int col = 0; col < int(A.size()); col++) { + auto &Ac = A.at(col); + for (auto &el : Ac) + mat.insert(el.first, col) = el.second; + } + + for (int i = 0; i < int(x.size()); i++) + vx[i] = x.at(i); + for (int i = 0; i < int(rhs.size()); i++) + vb[i] = rhs.at(i); + + ConjugateGradient<SparseMatrix<T>, Lower | Upper> solver; + solver.setTolerance(1e-5); + VectorXd xr = solver.compute(mat).solveWithGuess(vb, vx); + for (int i = 0; i < int(x.size()); i++) + x.at(i) = xr[i]; + // for (int i = 0; i < int(x.size()); i++) + // log_info("x[%d] = %f\n", i, x.at(i)); + } +}; + +} // namespace + +class HeAPPlacer +{ + public: + HeAPPlacer(Context *ctx, PlacerHeapCfg cfg) : ctx(ctx), cfg(cfg) { Eigen::initParallel(); } + + bool place() + { + auto startt = std::chrono::high_resolution_clock::now(); + + ctx->lock(); + place_constraints(); + build_fast_bels(); + seed_placement(); + update_all_chains(); + wirelen_t hpwl = total_hpwl(); + log_info("Creating initial analytic placement for %d cells, random placement wirelen = %d.\n", + int(place_cells.size()), int(hpwl)); + for (int i = 0; i < 4; i++) { + setup_solve_cells(); + auto solve_startt = std::chrono::high_resolution_clock::now(); + std::thread xaxis([&]() { build_solve_direction(false, -1); }); + build_solve_direction(true, -1); + xaxis.join(); + auto solve_endt = std::chrono::high_resolution_clock::now(); + solve_time += std::chrono::duration<double>(solve_endt - solve_startt).count(); + + update_all_chains(); + + hpwl = total_hpwl(); + log_info(" at initial placer iter %d, wirelen = %d\n", i, int(hpwl)); + } + + wirelen_t solved_hpwl = 0, spread_hpwl = 0, legal_hpwl = 0, best_hpwl = std::numeric_limits<wirelen_t>::max(); + int iter = 0, stalled = 0; + + std::vector<std::tuple<CellInfo *, BelId, PlaceStrength>> solution; + + std::vector<std::unordered_set<IdString>> heap_runs; + std::unordered_set<IdString> all_celltypes; + std::unordered_map<IdString, int> ct_count; + + for (auto cell : place_cells) { + if (!all_celltypes.count(cell->type)) { + heap_runs.push_back(std::unordered_set<IdString>{cell->type}); + all_celltypes.insert(cell->type); + } + ct_count[cell->type]++; + } + // If more than 98% of cells are one cell type, always solve all at once + // Otherwise, follow full HeAP strategy of rotate&all + for (auto &c : ct_count) + if (c.second >= 0.98 * int(place_cells.size())) { + heap_runs.clear(); + break; + } + + heap_runs.push_back(all_celltypes); + // The main HeAP placer loop + log_info("Running main analytical placer.\n"); + while (stalled < 5 && (solved_hpwl <= legal_hpwl * 0.8)) { + // Alternate between particular Bel types and all bels + for (auto &run : heap_runs) { + auto run_startt = std::chrono::high_resolution_clock::now(); + + setup_solve_cells(&run); + if (solve_cells.empty()) + continue; + // Heuristic: don't bother with threading below a certain size + auto solve_startt = std::chrono::high_resolution_clock::now(); + + if (solve_cells.size() < 500) { + build_solve_direction(false, (iter == 0) ? -1 : iter); + build_solve_direction(true, (iter == 0) ? -1 : iter); + } else { + std::thread xaxis([&]() { build_solve_direction(false, (iter == 0) ? -1 : iter); }); + build_solve_direction(true, (iter == 0) ? -1 : iter); + xaxis.join(); + } + auto solve_endt = std::chrono::high_resolution_clock::now(); + solve_time += std::chrono::duration<double>(solve_endt - solve_startt).count(); + update_all_chains(); + solved_hpwl = total_hpwl(); + + update_all_chains(); + for (auto type : sorted(run)) + CutSpreader(this, type).run(); + + update_all_chains(); + spread_hpwl = total_hpwl(); + legalise_placement_strict(true); + update_all_chains(); + + legal_hpwl = total_hpwl(); + auto run_stopt = std::chrono::high_resolution_clock::now(); + log_info(" at iteration #%d, type %s: wirelen solved = %d, spread = %d, legal = %d; time = %.02fs\n", + iter + 1, (run.size() > 1 ? "ALL" : run.begin()->c_str(ctx)), int(solved_hpwl), + int(spread_hpwl), int(legal_hpwl), + std::chrono::duration<double>(run_stopt - run_startt).count()); + } + + if (ctx->timing_driven) + get_criticalities(ctx, &net_crit); + + if (legal_hpwl < best_hpwl) { + best_hpwl = legal_hpwl; + stalled = 0; + // Save solution + solution.clear(); + for (auto cell : sorted(ctx->cells)) { + solution.emplace_back(cell.second, cell.second->bel, cell.second->belStrength); + } + } else { + ++stalled; + } + for (auto &cl : cell_locs) { + cl.second.legal_x = cl.second.x; + cl.second.legal_y = cl.second.y; + } + ctx->yield(); + ++iter; + } + + // Apply saved solution + for (auto &sc : solution) { + CellInfo *cell = std::get<0>(sc); + if (cell->bel != BelId()) + ctx->unbindBel(cell->bel); + } + for (auto &sc : solution) { + CellInfo *cell; + BelId bel; + PlaceStrength strength; + std::tie(cell, bel, strength) = sc; + ctx->bindBel(bel, cell, strength); + } + + for (auto cell : sorted(ctx->cells)) { + if (cell.second->bel == BelId()) + log_error("Found unbound cell %s\n", cell.first.c_str(ctx)); + if (ctx->getBoundBelCell(cell.second->bel) != cell.second) + log_error("Found cell %s with mismatched binding\n", cell.first.c_str(ctx)); + if (ctx->debug) + log_info("AP soln: %s -> %s\n", cell.first.c_str(ctx), ctx->getBelName(cell.second->bel).c_str(ctx)); + } + + ctx->unlock(); + auto endtt = std::chrono::high_resolution_clock::now(); + log_info("HeAP Placer Time: %.02fs\n", std::chrono::duration<double>(endtt - startt).count()); + log_info(" of which solving equations: %.02fs\n", solve_time); + log_info(" of which spreading cells: %.02fs\n", cl_time); + log_info(" of which strict legalisation: %.02fs\n", sl_time); + + ctx->check(); + + placer1_refine(ctx, Placer1Cfg(ctx)); + + return true; + } + + private: + Context *ctx; + PlacerHeapCfg cfg; + + int max_x = 0, max_y = 0; + std::vector<std::vector<std::vector<std::vector<BelId>>>> fast_bels; + std::unordered_map<IdString, std::tuple<int, int>> bel_types; + + // For fast handling of heterogeneosity during initial placement without full legalisation, + // for each Bel type this goes from x or y to the nearest x or y where a Bel of a given type exists + // This is particularly important for the iCE40 architecture, where multipliers and BRAM only exist at the + // edges and corners respectively + std::vector<std::vector<int>> nearest_row_with_bel; + std::vector<std::vector<int>> nearest_col_with_bel; + + // In some cases, we can't use bindBel because we allow overlap in the earlier stages. So we use this custom + // structure instead + struct CellLocation + { + int x, y; + int legal_x, legal_y; + double rawx, rawy; + bool locked, global; + }; + std::unordered_map<IdString, CellLocation> cell_locs; + // The set of cells that we will actually place. This excludes locked cells and children cells of macros/chains + // (only the root of each macro is placed.) + std::vector<CellInfo *> place_cells; + + // The cells in the current equation being solved (a subset of place_cells in some cases, where we only place + // cells of a certain type) + std::vector<CellInfo *> solve_cells; + + // For cells in a chain, this is the ultimate root cell of the chain (sometimes this is not constr_parent + // where chains are within chains + std::unordered_map<IdString, CellInfo *> chain_root; + std::unordered_map<IdString, int> chain_size; + + // The offset from chain_root to a cell in the chain + std::unordered_map<IdString, std::pair<int, int>> cell_offsets; + + // Performance counting + double solve_time = 0, cl_time = 0, sl_time = 0; + + NetCriticalityMap net_crit; + + // Place cells with the BEL attribute set to constrain them + void place_constraints() + { + size_t placed_cells = 0; + // Initial constraints placer + for (auto &cell_entry : ctx->cells) { + CellInfo *cell = cell_entry.second.get(); + auto loc = cell->attrs.find(ctx->id("BEL")); + if (loc != cell->attrs.end()) { + std::string loc_name = loc->second; + BelId bel = ctx->getBelByName(ctx->id(loc_name)); + if (bel == BelId()) { + log_error("No Bel named \'%s\' located for " + "this chip (processing BEL attribute on \'%s\')\n", + loc_name.c_str(), cell->name.c_str(ctx)); + } + + IdString bel_type = ctx->getBelType(bel); + if (bel_type != cell->type) { + log_error("Bel \'%s\' of type \'%s\' does not match cell " + "\'%s\' of type \'%s\'\n", + loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx)); + } + if (!ctx->isValidBelForCell(cell, bel)) { + log_error("Bel \'%s\' of type \'%s\' is not valid for cell " + "\'%s\' of type \'%s\'\n", + loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx)); + } + + auto bound_cell = ctx->getBoundBelCell(bel); + if (bound_cell) { + log_error("Cell \'%s\' cannot be bound to bel \'%s\' since it is already bound to cell \'%s\'\n", + cell->name.c_str(ctx), loc_name.c_str(), bound_cell->name.c_str(ctx)); + } + + ctx->bindBel(bel, cell, STRENGTH_USER); + placed_cells++; + } + } + log_info("Placed %d cells based on constraints.\n", int(placed_cells)); + ctx->yield(); + } + + // Construct the fast_bels, nearest_row_with_bel and nearest_col_with_bel + void build_fast_bels() + { + + int num_bel_types = 0; + for (auto bel : ctx->getBels()) { + IdString type = ctx->getBelType(bel); + if (bel_types.find(type) == bel_types.end()) { + bel_types[type] = std::tuple<int, int>(num_bel_types++, 1); + } else { + std::get<1>(bel_types.at(type))++; + } + } + for (auto bel : ctx->getBels()) { + if (!ctx->checkBelAvail(bel)) + continue; + Loc loc = ctx->getBelLocation(bel); + IdString type = ctx->getBelType(bel); + int type_idx = std::get<0>(bel_types.at(type)); + if (int(fast_bels.size()) < type_idx + 1) + fast_bels.resize(type_idx + 1); + if (int(fast_bels.at(type_idx).size()) < (loc.x + 1)) + fast_bels.at(type_idx).resize(loc.x + 1); + if (int(fast_bels.at(type_idx).at(loc.x).size()) < (loc.y + 1)) + fast_bels.at(type_idx).at(loc.x).resize(loc.y + 1); + max_x = std::max(max_x, loc.x); + max_y = std::max(max_y, loc.y); + fast_bels.at(type_idx).at(loc.x).at(loc.y).push_back(bel); + } + + nearest_row_with_bel.resize(num_bel_types, std::vector<int>(max_y + 1, -1)); + nearest_col_with_bel.resize(num_bel_types, std::vector<int>(max_x + 1, -1)); + for (auto bel : ctx->getBels()) { + if (!ctx->checkBelAvail(bel)) + continue; + Loc loc = ctx->getBelLocation(bel); + int type_idx = std::get<0>(bel_types.at(ctx->getBelType(bel))); + auto &nr = nearest_row_with_bel.at(type_idx), &nc = nearest_col_with_bel.at(type_idx); + // Traverse outwards through nearest_row_with_bel and nearest_col_with_bel, stopping once + // another row/col is already recorded as being nearer + for (int x = loc.x; x <= max_x; x++) { + if (nc.at(x) != -1 && std::abs(loc.x - nc.at(x)) <= (x - loc.x)) + break; + nc.at(x) = loc.x; + } + for (int x = loc.x - 1; x >= 0; x--) { + if (nc.at(x) != -1 && std::abs(loc.x - nc.at(x)) <= (loc.x - x)) + break; + nc.at(x) = loc.x; + } + for (int y = loc.y; y <= max_y; y++) { + if (nr.at(y) != -1 && std::abs(loc.y - nr.at(y)) <= (y - loc.y)) + break; + nr.at(y) = loc.y; + } + for (int y = loc.y - 1; y >= 0; y--) { + if (nr.at(y) != -1 && std::abs(loc.y - nr.at(y)) <= (loc.y - y)) + break; + nr.at(y) = loc.y; + } + } + } + + // Build and solve in one direction + void build_solve_direction(bool yaxis, int iter) + { + for (int i = 0; i < 5; i++) { + EquationSystem<double> esx(solve_cells.size(), solve_cells.size()); + build_equations(esx, yaxis, iter); + solve_equations(esx, yaxis); + } + } + + // Check if a cell has any meaningful connectivity + bool has_connectivity(CellInfo *cell) + { + for (auto port : cell->ports) { + if (port.second.net != nullptr && port.second.net->driver.cell != nullptr && + !port.second.net->users.empty()) + return true; + } + return false; + } + + // Build up a random initial placement, without regard to legality + // FIXME: Are there better approaches to the initial placement (e.g. greedy?) + void seed_placement() + { + std::unordered_map<IdString, std::deque<BelId>> available_bels; + for (auto bel : ctx->getBels()) { + if (!ctx->checkBelAvail(bel)) + continue; + available_bels[ctx->getBelType(bel)].push_back(bel); + } + for (auto &t : available_bels) { + std::random_shuffle(t.second.begin(), t.second.end(), [&](size_t n) { return ctx->rng(int(n)); }); + } + for (auto cell : sorted(ctx->cells)) { + CellInfo *ci = cell.second; + if (ci->bel != BelId()) { + Loc loc = ctx->getBelLocation(ci->bel); + cell_locs[cell.first].x = loc.x; + cell_locs[cell.first].y = loc.y; + cell_locs[cell.first].locked = true; + cell_locs[cell.first].global = ctx->getBelGlobalBuf(ci->bel); + } else if (ci->constr_parent == nullptr) { + bool placed = false; + while (!placed) { + if (!available_bels.count(ci->type) || available_bels.at(ci->type).empty()) + log_error("Unable to place cell '%s', no Bels remaining of type '%s'\n", ci->name.c_str(ctx), + ci->type.c_str(ctx)); + BelId bel = available_bels.at(ci->type).back(); + available_bels.at(ci->type).pop_back(); + Loc loc = ctx->getBelLocation(bel); + cell_locs[cell.first].x = loc.x; + cell_locs[cell.first].y = loc.y; + cell_locs[cell.first].locked = false; + cell_locs[cell.first].global = ctx->getBelGlobalBuf(bel); + // FIXME + if (has_connectivity(cell.second) && !cfg.ioBufTypes.count(ci->type)) { + place_cells.push_back(ci); + placed = true; + } else { + if (ctx->isValidBelForCell(ci, bel)) { + ctx->bindBel(bel, ci, STRENGTH_STRONG); + cell_locs[cell.first].locked = true; + placed = true; + } else { + available_bels.at(ci->type).push_front(bel); + } + } + } + } + } + } + + // Setup the cells to be solved, returns the number of rows + int setup_solve_cells(std::unordered_set<IdString> *celltypes = nullptr) + { + int row = 0; + solve_cells.clear(); + // First clear the udata of all cells + for (auto cell : sorted(ctx->cells)) + cell.second->udata = dont_solve; + // Then update cells to be placed, which excludes cell children + for (auto cell : place_cells) { + if (celltypes && !celltypes->count(cell->type)) + continue; + cell->udata = row++; + solve_cells.push_back(cell); + } + // Finally, update the udata of children + for (auto chained : chain_root) + ctx->cells.at(chained.first)->udata = chained.second->udata; + return row; + } + + // Update the location of all children of a chain + void update_chain(CellInfo *cell, CellInfo *root) + { + const auto &base = cell_locs[cell->name]; + for (auto child : cell->constr_children) { + chain_size[root->name]++; + if (child->constr_x != child->UNCONSTR) + cell_locs[child->name].x = std::min(max_x, base.x + child->constr_x); + else + cell_locs[child->name].x = base.x; // better handling of UNCONSTR? + if (child->constr_y != child->UNCONSTR) + cell_locs[child->name].y = std::min(max_y, base.y + child->constr_y); + else + cell_locs[child->name].y = base.y; // better handling of UNCONSTR? + chain_root[child->name] = root; + if (!child->constr_children.empty()) + update_chain(child, root); + } + } + + // Update all chains + void update_all_chains() + { + for (auto cell : place_cells) { + chain_size[cell->name] = 1; + if (!cell->constr_children.empty()) + update_chain(cell, cell); + } + } + + // Run a function on all ports of a net - including the driver and all users + template <typename Tf> void foreach_port(NetInfo *net, Tf func) + { + if (net->driver.cell != nullptr) + func(net->driver, -1); + for (size_t i = 0; i < net->users.size(); i++) + func(net->users.at(i), i); + } + + // Build the system of equations for either X or Y + void build_equations(EquationSystem<double> &es, bool yaxis, int iter = -1) + { + // Return the x or y position of a cell, depending on ydir + auto cell_pos = [&](CellInfo *cell) { return yaxis ? cell_locs.at(cell->name).y : cell_locs.at(cell->name).x; }; + auto legal_pos = [&](CellInfo *cell) { + return yaxis ? cell_locs.at(cell->name).legal_y : cell_locs.at(cell->name).legal_x; + }; + + es.reset(); + + for (auto net : sorted(ctx->nets)) { + NetInfo *ni = net.second; + if (ni->driver.cell == nullptr) + continue; + if (ni->users.empty()) + continue; + if (cell_locs.at(ni->driver.cell->name).global) + continue; + // Find the bounds of the net in this axis, and the ports that correspond to these bounds + PortRef *lbport = nullptr, *ubport = nullptr; + int lbpos = std::numeric_limits<int>::max(), ubpos = std::numeric_limits<int>::min(); + foreach_port(ni, [&](PortRef &port, int user_idx) { + int pos = cell_pos(port.cell); + if (pos < lbpos) { + lbpos = pos; + lbport = &port; + } + if (pos > ubpos) { + ubpos = pos; + ubport = &port; + } + }); + NPNR_ASSERT(lbport != nullptr); + NPNR_ASSERT(ubport != nullptr); + + auto stamp_equation = [&](PortRef &var, PortRef &eqn, double weight) { + if (eqn.cell->udata == dont_solve) + return; + int row = eqn.cell->udata; + int v_pos = cell_pos(var.cell); + if (var.cell->udata != dont_solve) { + es.add_coeff(row, var.cell->udata, weight); + } else { + es.add_rhs(row, -v_pos * weight); + } + if (cell_offsets.count(var.cell->name)) { + es.add_rhs(row, -(yaxis ? cell_offsets.at(var.cell->name).second + : cell_offsets.at(var.cell->name).first) * + weight); + } + }; + + // Add all relevant connections to the matrix + foreach_port(ni, [&](PortRef &port, int user_idx) { + int this_pos = cell_pos(port.cell); + auto process_arc = [&](PortRef *other) { + if (other == &port) + return; + int o_pos = cell_pos(other->cell); + double weight = 1.0 / (ni->users.size() * std::max<double>(1, std::abs(o_pos - this_pos))); + + if (user_idx != -1 && net_crit.count(ni->name)) { + auto &nc = net_crit.at(ni->name); + if (user_idx < int(nc.criticality.size())) + weight *= (1.0 + cfg.timingWeight * + std::pow(nc.criticality.at(user_idx), cfg.criticalityExponent)); + } + + // If cell 0 is not fixed, it will stamp +w on its equation and -w on the other end's equation, + // if the other end isn't fixed + stamp_equation(port, port, weight); + stamp_equation(port, *other, -weight); + stamp_equation(*other, *other, weight); + stamp_equation(*other, port, -weight); + }; + process_arc(lbport); + process_arc(ubport); + }); + } + if (iter != -1) { + float alpha = cfg.alpha; + for (size_t row = 0; row < solve_cells.size(); row++) { + int l_pos = legal_pos(solve_cells.at(row)); + int c_pos = cell_pos(solve_cells.at(row)); + + double weight = alpha * iter / std::max<double>(1, std::abs(l_pos - c_pos)); + // Add an arc from legalised to current position + es.add_coeff(row, row, weight); + es.add_rhs(row, weight * l_pos); + } + } + } + + // Build the system of equations for either X or Y + void solve_equations(EquationSystem<double> &es, bool yaxis) + { + // Return the x or y position of a cell, depending on ydir + auto cell_pos = [&](CellInfo *cell) { return yaxis ? cell_locs.at(cell->name).y : cell_locs.at(cell->name).x; }; + std::vector<double> vals; + std::transform(solve_cells.begin(), solve_cells.end(), std::back_inserter(vals), cell_pos); + es.solve(vals); + for (size_t i = 0; i < vals.size(); i++) + if (yaxis) { + cell_locs.at(solve_cells.at(i)->name).rawy = vals.at(i); + cell_locs.at(solve_cells.at(i)->name).y = std::min(max_y, std::max(0, int(vals.at(i)))); + } else { + cell_locs.at(solve_cells.at(i)->name).rawx = vals.at(i); + cell_locs.at(solve_cells.at(i)->name).x = std::min(max_x, std::max(0, int(vals.at(i)))); + } + } + + // Compute HPWL + wirelen_t total_hpwl() + { + wirelen_t hpwl = 0; + for (auto net : sorted(ctx->nets)) { + NetInfo *ni = net.second; + if (ni->driver.cell == nullptr) + continue; + CellLocation &drvloc = cell_locs.at(ni->driver.cell->name); + if (drvloc.global) + continue; + int xmin = drvloc.x, xmax = drvloc.x, ymin = drvloc.y, ymax = drvloc.y; + for (auto &user : ni->users) { + CellLocation &usrloc = cell_locs.at(user.cell->name); + xmin = std::min(xmin, usrloc.x); + xmax = std::max(xmax, usrloc.x); + ymin = std::min(ymin, usrloc.y); + ymax = std::max(ymax, usrloc.y); + } + hpwl += (xmax - xmin) + (ymax - ymin); + } + return hpwl; + } + + // Strict placement legalisation, performed after the initial HeAP spreading + void legalise_placement_strict(bool require_validity = false) + { + auto startt = std::chrono::high_resolution_clock::now(); + + // Unbind all cells placed in this solution + for (auto cell : sorted(ctx->cells)) { + CellInfo *ci = cell.second; + if (ci->bel != BelId() && (ci->udata != dont_solve || + (chain_root.count(ci->name) && chain_root.at(ci->name)->udata != dont_solve))) + ctx->unbindBel(ci->bel); + } + + // At the moment we don't follow the full HeAP algorithm using cuts for legalisation, instead using + // the simple greedy largest-macro-first approach. + std::priority_queue<std::pair<int, IdString>> remaining; + for (auto cell : solve_cells) { + remaining.emplace(chain_size[cell->name], cell->name); + } + int ripup_radius = 2; + int total_iters = 0; + while (!remaining.empty()) { + auto top = remaining.top(); + remaining.pop(); + + CellInfo *ci = ctx->cells.at(top.second).get(); + // Was now placed, ignore + if (ci->bel != BelId()) + continue; + // log_info(" Legalising %s (%s)\n", top.second.c_str(ctx), ci->type.c_str(ctx)); + int bt = std::get<0>(bel_types.at(ci->type)); + auto &fb = fast_bels.at(bt); + int radius = 0; + int iter = 0; + int iter_at_radius = 0; + bool placed = false; + BelId bestBel; + int best_inp_len = std::numeric_limits<int>::max(); + + total_iters++; + if (total_iters > int(solve_cells.size())) { + total_iters = 0; + ripup_radius = std::max(std::max(max_x, max_y), ripup_radius * 2); + } + + while (!placed) { + + int nx = ctx->rng(2 * radius + 1) + std::max(cell_locs.at(ci->name).x - radius, 0); + int ny = ctx->rng(2 * radius + 1) + std::max(cell_locs.at(ci->name).y - radius, 0); + + iter++; + iter_at_radius++; + if (iter >= (10 * (radius + 1))) { + radius = std::min(std::max(max_x, max_y), radius + 1); + while (radius < std::max(max_x, max_y)) { + for (int x = std::max(0, cell_locs.at(ci->name).x - radius); + x <= std::min(max_x, cell_locs.at(ci->name).x + radius); x++) { + if (x >= int(fb.size())) + break; + for (int y = std::max(0, cell_locs.at(ci->name).y - radius); + y <= std::min(max_y, cell_locs.at(ci->name).y + radius); y++) { + if (y >= int(fb.at(x).size())) + break; + if (fb.at(x).at(y).size() > 0) + goto notempty; + } + } + radius = std::min(std::max(max_x, max_y), radius + 1); + } + notempty: + iter_at_radius = 0; + iter = 0; + } + if (nx < 0 || nx > max_x) + continue; + if (ny < 0 || ny > max_y) + continue; + + // ny = nearest_row_with_bel.at(bt).at(ny); + // nx = nearest_col_with_bel.at(bt).at(nx); + + if (nx >= int(fb.size())) + continue; + if (ny >= int(fb.at(nx).size())) + continue; + if (fb.at(nx).at(ny).empty()) + continue; + + int need_to_explore = 2 * radius; + + if (iter_at_radius >= need_to_explore && bestBel != BelId()) { + CellInfo *bound = ctx->getBoundBelCell(bestBel); + if (bound != nullptr) { + ctx->unbindBel(bound->bel); + remaining.emplace(chain_size[bound->name], bound->name); + } + ctx->bindBel(bestBel, ci, STRENGTH_WEAK); + placed = true; + Loc loc = ctx->getBelLocation(bestBel); + cell_locs[ci->name].x = loc.x; + cell_locs[ci->name].y = loc.y; + break; + } + + if (ci->constr_children.empty() && !ci->constr_abs_z) { + for (auto sz : fb.at(nx).at(ny)) { + if (ctx->checkBelAvail(sz) || (radius > ripup_radius || ctx->rng(20000) < 10)) { + CellInfo *bound = ctx->getBoundBelCell(sz); + if (bound != nullptr) { + if (bound->constr_parent != nullptr || !bound->constr_children.empty() || + bound->constr_abs_z) + continue; + ctx->unbindBel(bound->bel); + } + ctx->bindBel(sz, ci, STRENGTH_WEAK); + if (require_validity && !ctx->isBelLocationValid(sz)) { + ctx->unbindBel(sz); + if (bound != nullptr) + ctx->bindBel(sz, bound, STRENGTH_WEAK); + } else if (iter_at_radius < need_to_explore) { + ctx->unbindBel(sz); + if (bound != nullptr) + ctx->bindBel(sz, bound, STRENGTH_WEAK); + int input_len = 0; + for (auto &port : ci->ports) { + auto &p = port.second; + if (p.type != PORT_IN || p.net == nullptr || p.net->driver.cell == nullptr) + continue; + CellInfo *drv = p.net->driver.cell; + auto drv_loc = cell_locs.find(drv->name); + if (drv_loc == cell_locs.end()) + continue; + if (drv_loc->second.global) + continue; + input_len += std::abs(drv_loc->second.x - nx) + std::abs(drv_loc->second.y - ny); + } + if (input_len < best_inp_len) { + best_inp_len = input_len; + bestBel = sz; + } + break; + } else { + if (bound != nullptr) + remaining.emplace(chain_size[bound->name], bound->name); + Loc loc = ctx->getBelLocation(sz); + cell_locs[ci->name].x = loc.x; + cell_locs[ci->name].y = loc.y; + placed = true; + break; + } + } + } + } else { + for (auto sz : fb.at(nx).at(ny)) { + Loc loc = ctx->getBelLocation(sz); + if (ci->constr_abs_z && loc.z != ci->constr_z) + continue; + std::vector<std::pair<CellInfo *, BelId>> targets; + std::vector<std::pair<BelId, CellInfo *>> swaps_made; + std::queue<std::pair<CellInfo *, Loc>> visit; + visit.emplace(ci, loc); + while (!visit.empty()) { + CellInfo *vc = visit.front().first; + NPNR_ASSERT(vc->bel == BelId()); + Loc ploc = visit.front().second; + visit.pop(); + BelId target = ctx->getBelByLocation(ploc); + CellInfo *bound; + if (target == BelId() || ctx->getBelType(target) != vc->type) + goto fail; + bound = ctx->getBoundBelCell(target); + // Chains cannot overlap + if (bound != nullptr) + if (bound->constr_z != bound->UNCONSTR || bound->constr_parent != nullptr || + !bound->constr_children.empty() || bound->belStrength > STRENGTH_WEAK) + goto fail; + targets.emplace_back(vc, target); + for (auto child : vc->constr_children) { + Loc cloc = ploc; + if (child->constr_x != child->UNCONSTR) + cloc.x += child->constr_x; + if (child->constr_y != child->UNCONSTR) + cloc.y += child->constr_y; + if (child->constr_z != child->UNCONSTR) + cloc.z = child->constr_abs_z ? child->constr_z : (ploc.z + child->constr_z); + visit.emplace(child, cloc); + } + } + + for (auto &target : targets) { + CellInfo *bound = ctx->getBoundBelCell(target.second); + if (bound != nullptr) + ctx->unbindBel(target.second); + ctx->bindBel(target.second, target.first, STRENGTH_STRONG); + swaps_made.emplace_back(target.second, bound); + } + + for (auto &sm : swaps_made) { + if (!ctx->isBelLocationValid(sm.first)) + goto fail; + } + + if (false) { + fail: + for (auto &swap : swaps_made) { + ctx->unbindBel(swap.first); + if (swap.second != nullptr) + ctx->bindBel(swap.first, swap.second, STRENGTH_WEAK); + } + continue; + } + for (auto &target : targets) { + Loc loc = ctx->getBelLocation(target.second); + cell_locs[target.first->name].x = loc.x; + cell_locs[target.first->name].y = loc.y; + // log_info("%s %d %d %d\n", target.first->name.c_str(ctx), loc.x, loc.y, loc.z); + } + for (auto &swap : swaps_made) { + if (swap.second != nullptr) + remaining.emplace(chain_size[swap.second->name], swap.second->name); + } + + placed = true; + break; + } + } + } + } + auto endt = std::chrono::high_resolution_clock::now(); + sl_time += std::chrono::duration<float>(endt - startt).count(); + } + // Implementation of the cut-based spreading as described in the HeAP/SimPL papers + static constexpr float beta = 0.9; + + struct ChainExtent + { + int x0, y0, x1, y1; + }; + + struct SpreaderRegion + { + int id; + int x0, y0, x1, y1; + int cells, bels; + bool overused() const + { + if (bels < 4) + return cells > bels; + else + return cells > beta * bels; + } + }; + + class CutSpreader + { + public: + CutSpreader(HeAPPlacer *p, IdString beltype) + : p(p), ctx(p->ctx), beltype(beltype), fb(p->fast_bels.at(std::get<0>(p->bel_types.at(beltype)))) + { + } + static int seq; + void run() + { + auto startt = std::chrono::high_resolution_clock::now(); + init(); + find_overused_regions(); + for (auto &r : regions) { + if (merged_regions.count(r.id)) + continue; +#if 0 + log_info("%s (%d, %d) |_> (%d, %d) %d/%d\n", beltype.c_str(ctx), r.x0, r.y0, r.x1, r.y1, r.cells, + r.bels); +#endif + } + expand_regions(); + std::queue<std::pair<int, bool>> workqueue; +#if 0 + std::vector<std::pair<double, double>> orig; + if (ctx->debug) + for (auto c : p->solve_cells) + orig.emplace_back(p->cell_locs[c->name].rawx, p->cell_locs[c->name].rawy); +#endif + for (auto &r : regions) { + if (merged_regions.count(r.id)) + continue; +#if 0 + log_info("%s (%d, %d) |_> (%d, %d) %d/%d\n", beltype.c_str(ctx), r.x0, r.y0, r.x1, r.y1, r.cells, + r.bels); +#endif + workqueue.emplace(r.id, false); + // cut_region(r, false); + } + while (!workqueue.empty()) { + auto front = workqueue.front(); + workqueue.pop(); + auto &r = regions.at(front.first); + if (r.cells == 0) + continue; + auto res = cut_region(r, front.second); + if (res) { + workqueue.emplace(res->first, !front.second); + workqueue.emplace(res->second, !front.second); + } else { + // Try the other dir, in case stuck in one direction only + auto res2 = cut_region(r, !front.second); + if (res2) { + // log_info("RETRY SUCCESS\n"); + workqueue.emplace(res2->first, front.second); + workqueue.emplace(res2->second, front.second); + } + } + } +#if 0 + if (ctx->debug) { + std::ofstream sp("spread" + std::to_string(seq) + ".csv"); + for (size_t i = 0; i < p->solve_cells.size(); i++) { + auto &c = p->solve_cells.at(i); + if (c->type != beltype) + continue; + sp << orig.at(i).first << "," << orig.at(i).second << "," << p->cell_locs[c->name].rawx << "," << p->cell_locs[c->name].rawy << std::endl; + } + std::ofstream oc("cells" + std::to_string(seq) + ".csv"); + for (size_t y = 0; y <= p->max_y; y++) { + for (size_t x = 0; x <= p->max_x; x++) { + oc << cells_at_location.at(x).at(y).size() << ", "; + } + oc << std::endl; + } + ++seq; + } +#endif + auto endt = std::chrono::high_resolution_clock::now(); + p->cl_time += std::chrono::duration<float>(endt - startt).count(); + } + + private: + HeAPPlacer *p; + Context *ctx; + IdString beltype; + std::vector<std::vector<int>> occupancy; + std::vector<std::vector<int>> groups; + std::vector<std::vector<ChainExtent>> chaines; + std::map<IdString, ChainExtent> cell_extents; + + std::vector<std::vector<std::vector<BelId>>> &fb; + + std::vector<SpreaderRegion> regions; + std::unordered_set<int> merged_regions; + // Cells at a location, sorted by real (not integer) x and y + std::vector<std::vector<std::vector<CellInfo *>>> cells_at_location; + + int occ_at(int x, int y) { return occupancy.at(x).at(y); } + + int bels_at(int x, int y) + { + if (x >= int(fb.size()) || y >= int(fb.at(x).size())) + return 0; + return int(fb.at(x).at(y).size()); + } + + void init() + { + occupancy.resize(p->max_x + 1, std::vector<int>(p->max_y + 1, 0)); + groups.resize(p->max_x + 1, std::vector<int>(p->max_y + 1, -1)); + chaines.resize(p->max_x + 1, std::vector<ChainExtent>(p->max_y + 1)); + cells_at_location.resize(p->max_x + 1, std::vector<std::vector<CellInfo *>>(p->max_y + 1)); + for (int x = 0; x <= p->max_x; x++) + for (int y = 0; y <= p->max_y; y++) { + occupancy.at(x).at(y) = 0; + groups.at(x).at(y) = -1; + chaines.at(x).at(y) = {x, y, x, y}; + } + + auto set_chain_ext = [&](IdString cell, int x, int y) { + if (!cell_extents.count(cell)) + cell_extents[cell] = {x, y, x, y}; + else { + cell_extents[cell].x0 = std::min(cell_extents[cell].x0, x); + cell_extents[cell].y0 = std::min(cell_extents[cell].y0, y); + cell_extents[cell].x1 = std::max(cell_extents[cell].x1, x); + cell_extents[cell].y1 = std::max(cell_extents[cell].y1, y); + } + }; + + for (auto &cell : p->cell_locs) { + if (ctx->cells.at(cell.first)->type != beltype) + continue; + if (ctx->cells.at(cell.first)->belStrength > STRENGTH_STRONG) + continue; + occupancy.at(cell.second.x).at(cell.second.y)++; + // Compute ultimate extent of each chain root + if (p->chain_root.count(cell.first)) { + set_chain_ext(p->chain_root.at(cell.first)->name, cell.second.x, cell.second.y); + } else if (!ctx->cells.at(cell.first)->constr_children.empty()) { + set_chain_ext(cell.first, cell.second.x, cell.second.y); + } + } + for (auto &cell : p->cell_locs) { + if (ctx->cells.at(cell.first)->type != beltype) + continue; + // Transfer chain extents to the actual chaines structure + ChainExtent *ce = nullptr; + if (p->chain_root.count(cell.first)) + ce = &(cell_extents.at(p->chain_root.at(cell.first)->name)); + else if (!ctx->cells.at(cell.first)->constr_children.empty()) + ce = &(cell_extents.at(cell.first)); + if (ce) { + auto &lce = chaines.at(cell.second.x).at(cell.second.y); + lce.x0 = std::min(lce.x0, ce->x0); + lce.y0 = std::min(lce.y0, ce->y0); + lce.x1 = std::max(lce.x1, ce->x1); + lce.y1 = std::max(lce.y1, ce->y1); + } + } + for (auto cell : p->solve_cells) { + if (cell->type != beltype) + continue; + cells_at_location.at(p->cell_locs.at(cell->name).x).at(p->cell_locs.at(cell->name).y).push_back(cell); + } + } + void merge_regions(SpreaderRegion &merged, SpreaderRegion &mergee) + { + // Prevent grow_region from recursing while doing this + for (int x = mergee.x0; x <= mergee.x1; x++) + for (int y = mergee.y0; y <= mergee.y1; y++) { + // log_info("%d %d\n", groups.at(x).at(y), mergee.id); + NPNR_ASSERT(groups.at(x).at(y) == mergee.id); + groups.at(x).at(y) = merged.id; + merged.cells += occ_at(x, y); + merged.bels += bels_at(x, y); + } + merged_regions.insert(mergee.id); + grow_region(merged, mergee.x0, mergee.y0, mergee.x1, mergee.y1); + } + + void grow_region(SpreaderRegion &r, int x0, int y0, int x1, int y1, bool init = false) + { + // log_info("growing to (%d, %d) |_> (%d, %d)\n", x0, y0, x1, y1); + if ((x0 >= r.x0 && y0 >= r.y0 && x1 <= r.x1 && y1 <= r.y1) || init) + return; + int old_x0 = r.x0 + (init ? 1 : 0), old_y0 = r.y0, old_x1 = r.x1, old_y1 = r.y1; + r.x0 = std::min(r.x0, x0); + r.y0 = std::min(r.y0, y0); + r.x1 = std::max(r.x1, x1); + r.y1 = std::max(r.y1, y1); + + auto process_location = [&](int x, int y) { + // Merge with any overlapping regions + if (groups.at(x).at(y) == -1) { + r.bels += bels_at(x, y); + r.cells += occ_at(x, y); + } + if (groups.at(x).at(y) != -1 && groups.at(x).at(y) != r.id) + merge_regions(r, regions.at(groups.at(x).at(y))); + groups.at(x).at(y) = r.id; + // Grow to cover any chains + auto &chaine = chaines.at(x).at(y); + grow_region(r, chaine.x0, chaine.y0, chaine.x1, chaine.y1); + }; + for (int x = r.x0; x < old_x0; x++) + for (int y = r.y0; y <= r.y1; y++) + process_location(x, y); + for (int x = old_x1 + 1; x <= x1; x++) + for (int y = r.y0; y <= r.y1; y++) + process_location(x, y); + for (int y = r.y0; y < old_y0; y++) + for (int x = r.x0; x <= r.x1; x++) + process_location(x, y); + for (int y = old_y1 + 1; y <= r.y1; y++) + for (int x = r.x0; x <= r.x1; x++) + process_location(x, y); + } + + void find_overused_regions() + { + for (int x = 0; x <= p->max_x; x++) + for (int y = 0; y <= p->max_y; y++) { + // Either already in a group, or not overutilised. Ignore + if (groups.at(x).at(y) != -1 || (occ_at(x, y) <= bels_at(x, y))) + continue; + // log_info("%d %d %d\n", x, y, occ_at(x, y)); + int id = int(regions.size()); + groups.at(x).at(y) = id; + SpreaderRegion reg; + reg.id = id; + reg.x0 = reg.x1 = x; + reg.y0 = reg.y1 = y; + reg.bels = bels_at(x, y); + reg.cells = occ_at(x, y); + // Make sure we cover carries, etc + grow_region(reg, reg.x0, reg.y0, reg.x1, reg.y1, true); + + bool expanded = true; + while (expanded) { + expanded = false; + // Keep trying expansion in x and y, until we find no over-occupancy cells + // or hit grouped cells + + // First try expanding in x + if (reg.x1 < p->max_x) { + bool over_occ_x = false; + for (int y1 = reg.y0; y1 <= reg.y1; y1++) { + if (occ_at(reg.x1 + 1, y1) > bels_at(reg.x1 + 1, y1)) { + // log_info("(%d, %d) occ %d bels %d\n", reg.x1+ 1, y1, occ_at(reg.x1 + 1, y1), + // bels_at(reg.x1 + 1, y1)); + over_occ_x = true; + break; + } + } + if (over_occ_x) { + expanded = true; + grow_region(reg, reg.x0, reg.y0, reg.x1 + 1, reg.y1); + } + } + + if (reg.y1 < p->max_y) { + bool over_occ_y = false; + for (int x1 = reg.x0; x1 <= reg.x1; x1++) { + if (occ_at(x1, reg.y1 + 1) > bels_at(x1, reg.y1 + 1)) { + // log_info("(%d, %d) occ %d bels %d\n", x1, reg.y1 + 1, occ_at(x1, reg.y1 + 1), + // bels_at(x1, reg.y1 + 1)); + over_occ_y = true; + break; + } + } + if (over_occ_y) { + expanded = true; + grow_region(reg, reg.x0, reg.y0, reg.x1, reg.y1 + 1); + } + } + } + regions.push_back(reg); + } + } + + void expand_regions() + { + std::queue<int> overu_regions; + for (auto &r : regions) { + if (!merged_regions.count(r.id) && r.overused()) + overu_regions.push(r.id); + } + while (!overu_regions.empty()) { + int rid = overu_regions.front(); + overu_regions.pop(); + if (merged_regions.count(rid)) + continue; + auto ® = regions.at(rid); + while (reg.overused()) { + bool changed = false; + if (reg.x0 > 0) { + grow_region(reg, reg.x0 - 1, reg.y0, reg.x1, reg.y1); + changed = true; + if (!reg.overused()) + break; + } + if (reg.x1 < p->max_x) { + grow_region(reg, reg.x0, reg.y0, reg.x1 + 1, reg.y1); + changed = true; + if (!reg.overused()) + break; + } + if (reg.y0 > 0) { + grow_region(reg, reg.x0, reg.y0 - 1, reg.x1, reg.y1); + changed = true; + if (!reg.overused()) + break; + } + if (reg.y1 < p->max_y) { + grow_region(reg, reg.x0, reg.y0, reg.x1, reg.y1 + 1); + changed = true; + if (!reg.overused()) + break; + } + if (!changed) { + if (reg.cells > reg.bels) + log_error("Failed to expand region (%d, %d) |_> (%d, %d) of %d %ss\n", reg.x0, reg.y0, + reg.x1, reg.y1, reg.cells, beltype.c_str(ctx)); + else + break; + } + } + } + } + + // Implementation of the recursive cut-based spreading as described in the HeAP paper + // Note we use "left" to mean "-x/-y" depending on dir and "right" to mean "+x/+y" depending on dir + + std::vector<CellInfo *> cut_cells; + + boost::optional<std::pair<int, int>> cut_region(SpreaderRegion &r, bool dir) + { + cut_cells.clear(); + auto &cal = cells_at_location; + int total_cells = 0, total_bels = 0; + for (int x = r.x0; x <= r.x1; x++) { + for (int y = r.y0; y <= r.y1; y++) { + std::copy(cal.at(x).at(y).begin(), cal.at(x).at(y).end(), std::back_inserter(cut_cells)); + total_bels += bels_at(x, y); + } + } + for (auto &cell : cut_cells) { + total_cells += p->chain_size.count(cell->name) ? p->chain_size.at(cell->name) : 1; + } + std::sort(cut_cells.begin(), cut_cells.end(), [&](const CellInfo *a, const CellInfo *b) { + return dir ? (p->cell_locs.at(a->name).rawy < p->cell_locs.at(b->name).rawy) + : (p->cell_locs.at(a->name).rawx < p->cell_locs.at(b->name).rawx); + }); + + if (cut_cells.size() < 2) + return {}; + // Find the cells midpoint, counting chains in terms of their total size - making the initial source cut + int pivot_cells = 0; + int pivot = 0; + for (auto &cell : cut_cells) { + pivot_cells += p->chain_size.count(cell->name) ? p->chain_size.at(cell->name) : 1; + if (pivot_cells >= total_cells / 2) + break; + pivot++; + } + if (pivot == int(cut_cells.size())) + pivot = int(cut_cells.size()) - 1; + // log_info("orig pivot %d lc %d rc %d\n", pivot, pivot_cells, r.cells - pivot_cells); + + // Find the clearance required either side of the pivot + int clearance_l = 0, clearance_r = 0; + for (size_t i = 0; i < cut_cells.size(); i++) { + int size; + if (cell_extents.count(cut_cells.at(i)->name)) { + auto &ce = cell_extents.at(cut_cells.at(i)->name); + size = dir ? (ce.y1 - ce.y0 + 1) : (ce.x1 - ce.x0 + 1); + } else { + size = 1; + } + if (int(i) < pivot) + clearance_l = std::max(clearance_l, size); + else + clearance_r = std::max(clearance_r, size); + } + // Find the target cut that minimises difference in utilisation, whilst trying to ensure that all chains + // still fit + + // First trim the boundaries of the region in the axis-of-interest, skipping any rows/cols without any + // bels of the appropriate type + int trimmed_l = dir ? r.y0 : r.x0, trimmed_r = dir ? r.y1 : r.x1; + while (trimmed_l < (dir ? r.y1 : r.x1)) { + bool have_bels = false; + for (int i = dir ? r.x0 : r.y0; i <= (dir ? r.x1 : r.y1); i++) + if (bels_at(dir ? i : trimmed_l, dir ? trimmed_l : i) > 0) { + have_bels = true; + break; + } + if (have_bels) + break; + trimmed_l++; + } + while (trimmed_r > (dir ? r.y0 : r.x0)) { + bool have_bels = false; + for (int i = dir ? r.x0 : r.y0; i <= (dir ? r.x1 : r.y1); i++) + if (bels_at(dir ? i : trimmed_r, dir ? trimmed_r : i) > 0) { + have_bels = true; + break; + } + if (have_bels) + break; + trimmed_r--; + } + // log_info("tl %d tr %d cl %d cr %d\n", trimmed_l, trimmed_r, clearance_l, clearance_r); + if ((trimmed_r - trimmed_l + 1) <= std::max(clearance_l, clearance_r)) + return {}; + // Now find the initial target cut that minimises utilisation imbalance, whilst + // meeting the clearance requirements for any large macros + int left_cells = pivot_cells, right_cells = total_cells - pivot_cells; + int left_bels = 0, right_bels = total_bels; + int best_tgt_cut = -1; + double best_deltaU = std::numeric_limits<double>::max(); + std::pair<int, int> target_cut_bels; + for (int i = trimmed_l; i <= trimmed_r; i++) { + int slither_bels = 0; + for (int j = dir ? r.x0 : r.y0; j <= (dir ? r.x1 : r.y1); j++) { + slither_bels += dir ? bels_at(j, i) : bels_at(i, j); + } + left_bels += slither_bels; + right_bels -= slither_bels; + if (((i - trimmed_l) + 1) >= clearance_l && ((trimmed_r - i) + 1) >= clearance_r) { + // Solution is potentially valid + double aU = + std::abs(double(left_cells) / double(left_bels) - double(right_cells) / double(right_bels)); + if (aU < best_deltaU) { + best_deltaU = aU; + best_tgt_cut = i; + target_cut_bels = std::make_pair(left_bels, right_bels); + } + } + } + if (best_tgt_cut == -1) + return {}; + left_bels = target_cut_bels.first; + right_bels = target_cut_bels.second; + // log_info("pivot %d target cut %d lc %d lb %d rc %d rb %d\n", pivot, best_tgt_cut, left_cells, left_bels, + // right_cells, right_bels); + + // Peturb the source cut to eliminate overutilisation + while (pivot > 0 && (double(left_cells) / double(left_bels) > double(right_cells) / double(right_bels))) { + auto &move_cell = cut_cells.at(pivot); + int size = p->chain_size.count(move_cell->name) ? p->chain_size.at(move_cell->name) : 1; + left_cells -= size; + right_cells += size; + pivot--; + } + while (pivot < int(cut_cells.size()) - 1 && + (double(left_cells) / double(left_bels) < double(right_cells) / double(right_bels))) { + auto &move_cell = cut_cells.at(pivot + 1); + int size = p->chain_size.count(move_cell->name) ? p->chain_size.at(move_cell->name) : 1; + left_cells += size; + right_cells -= size; + pivot++; + } + // log_info("peturbed pivot %d lc %d lb %d rc %d rb %d\n", pivot, left_cells, left_bels, right_cells, + // right_bels); + // Split regions into bins, and then spread cells by linear interpolation within those bins + auto spread_binlerp = [&](int cells_start, int cells_end, double area_l, double area_r) { + int N = cells_end - cells_start; + if (N <= 2) { + for (int i = cells_start; i < cells_end; i++) { + auto &pos = dir ? p->cell_locs.at(cut_cells.at(i)->name).rawy + : p->cell_locs.at(cut_cells.at(i)->name).rawx; + pos = area_l + i * ((area_r - area_l) / N); + } + return; + } + // Split region into up to 10 (K) bins + int K = std::min<int>(N, 10); + std::vector<std::pair<int, double>> bin_bounds; // [(cell start, area start)] + bin_bounds.emplace_back(cells_start, area_l); + for (int i = 1; i < K; i++) + bin_bounds.emplace_back(cells_start + (N * i) / K, area_l + ((area_r - area_l + 0.99) * i) / K); + bin_bounds.emplace_back(cells_end, area_r + 0.99); + for (int i = 0; i < K; i++) { + auto &bl = bin_bounds.at(i), br = bin_bounds.at(i + 1); + double orig_left = dir ? p->cell_locs.at(cut_cells.at(bl.first)->name).rawy + : p->cell_locs.at(cut_cells.at(bl.first)->name).rawx; + double orig_right = dir ? p->cell_locs.at(cut_cells.at(br.first - 1)->name).rawy + : p->cell_locs.at(cut_cells.at(br.first - 1)->name).rawx; + double m = (br.second - bl.second) / std::max(0.00001, orig_right - orig_left); + for (int j = bl.first; j < br.first; j++) { + auto &pos = dir ? p->cell_locs.at(cut_cells.at(j)->name).rawy + : p->cell_locs.at(cut_cells.at(j)->name).rawx; + NPNR_ASSERT(pos >= orig_left && pos <= orig_right); + pos = bl.second + m * (pos - orig_left); + // log("[%f, %f] -> [%f, %f]: %f -> %f\n", orig_left, orig_right, bl.second, br.second, + // orig_pos, pos); + } + } + }; + spread_binlerp(0, pivot + 1, trimmed_l, best_tgt_cut); + spread_binlerp(pivot + 1, int(cut_cells.size()), best_tgt_cut + 1, trimmed_r); + // Update various data structures + for (int x = r.x0; x <= r.x1; x++) + for (int y = r.y0; y <= r.y1; y++) { + cells_at_location.at(x).at(y).clear(); + } + for (auto cell : cut_cells) { + auto &cl = p->cell_locs.at(cell->name); + cl.x = std::min(r.x1, std::max(r.x0, int(cl.rawx))); + cl.y = std::min(r.y1, std::max(r.y0, int(cl.rawy))); + cells_at_location.at(cl.x).at(cl.y).push_back(cell); + // log_info("spread pos %d %d\n", cl.x, cl.y); + } + SpreaderRegion rl, rr; + rl.id = int(regions.size()); + rl.x0 = r.x0; + rl.y0 = r.y0; + rl.x1 = dir ? r.x1 : best_tgt_cut; + rl.y1 = dir ? best_tgt_cut : r.y1; + rl.cells = left_cells; + rl.bels = left_bels; + rr.id = int(regions.size()) + 1; + rr.x0 = dir ? r.x0 : (best_tgt_cut + 1); + rr.y0 = dir ? (best_tgt_cut + 1) : r.y0; + rr.x1 = r.x1; + rr.y1 = r.y1; + rr.cells = right_cells; + rr.bels = right_bels; + regions.push_back(rl); + regions.push_back(rr); + for (int x = rl.x0; x <= rl.x1; x++) + for (int y = rl.y0; y <= rl.y1; y++) + groups.at(x).at(y) = rl.id; + for (int x = rr.x0; x <= rr.x1; x++) + for (int y = rr.y0; y <= rr.y1; y++) + groups.at(x).at(y) = rr.id; + return std::make_pair(rl.id, rr.id); + }; + }; + typedef decltype(CellInfo::udata) cell_udata_t; + cell_udata_t dont_solve = std::numeric_limits<cell_udata_t>::max(); +}; +int HeAPPlacer::CutSpreader::seq = 0; + +bool placer_heap(Context *ctx, PlacerHeapCfg cfg) { return HeAPPlacer(ctx, cfg).place(); } + +PlacerHeapCfg::PlacerHeapCfg(Context *ctx) : Settings(ctx) +{ + alpha = get<float>("placerHeap/alpha", 0.1); + criticalityExponent = get<int>("placerHeap/criticalityExponent", 2); + timingWeight = get<int>("placerHeap/timingWeight", 10); +} + +NEXTPNR_NAMESPACE_END + +#else + +#include "log.h" +#include "nextpnr.h" +#include "placer_heap.h" + +NEXTPNR_NAMESPACE_BEGIN +bool placer_heap(Context *ctx, PlacerHeapCfg cfg) +{ + log_error("nextpnr was built without the HeAP placer\n"); + return false; +} + +PlacerHeapCfg::PlacerHeapCfg(Context *ctx) : Settings(ctx) {} + +NEXTPNR_NAMESPACE_END + +#endif diff --git a/common/placer_heap.h b/common/placer_heap.h new file mode 100644 index 00000000..841aa0d9 --- /dev/null +++ b/common/placer_heap.h @@ -0,0 +1,47 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2019 David Shah <david@symbioticeda.com> + * + * 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. + * + * [[cite]] HeAP + * Analytical Placement for Heterogeneous FPGAs, Marcel Gort and Jason H. Anderson + * https://janders.eecg.utoronto.ca/pdfs/marcelfpl12.pdf + * + * [[cite]] SimPL + * SimPL: An Effective Placement Algorithm, Myung-Chul Kim, Dong-Jin Lee and Igor L. Markov + * http://www.ece.umich.edu/cse/awards/pdfs/iccad10-simpl.pdf + */ + +#ifndef PLACER_HEAP_H +#define PLACER_HEAP_H +#include "nextpnr.h" +#include "settings.h" + +NEXTPNR_NAMESPACE_BEGIN + +struct PlacerHeapCfg : public Settings +{ + PlacerHeapCfg(Context *ctx); + + float alpha; + float criticalityExponent; + float timingWeight; + + std::unordered_set<IdString> ioBufTypes; +}; + +extern bool placer_heap(Context *ctx, PlacerHeapCfg cfg); +NEXTPNR_NAMESPACE_END +#endif diff --git a/common/pybindings.cc b/common/pybindings.cc index 6cae889d..60f87e27 100644 --- a/common/pybindings.cc +++ b/common/pybindings.cc @@ -23,8 +23,10 @@ #include "pybindings.h" #include "arch_pybindings.h" #include "jsonparse.h" +#include "log.h" #include "nextpnr.h" +#include <boost/filesystem.hpp> #include <fstream> #include <memory> #include <signal.h> @@ -87,7 +89,26 @@ BOOST_PYTHON_MODULE(MODULE_NAME) using namespace PythonConversion; + enum_<GraphicElement::type_t>("GraphicElementType") + .value("TYPE_NONE", GraphicElement::TYPE_NONE) + .value("TYPE_LINE", GraphicElement::TYPE_LINE) + .value("TYPE_ARROW", GraphicElement::TYPE_ARROW) + .value("TYPE_BOX", GraphicElement::TYPE_BOX) + .value("TYPE_CIRCLE", GraphicElement::TYPE_CIRCLE) + .value("TYPE_LABEL", GraphicElement::TYPE_LABEL) + .export_values(); + + enum_<GraphicElement::style_t>("GraphicElementStyle") + .value("STYLE_GRID", GraphicElement::STYLE_GRID) + .value("STYLE_FRAME", GraphicElement::STYLE_FRAME) + .value("STYLE_HIDDEN", GraphicElement::STYLE_HIDDEN) + .value("STYLE_INACTIVE", GraphicElement::STYLE_INACTIVE) + .value("STYLE_ACTIVE", GraphicElement::STYLE_ACTIVE) + .export_values(); + class_<GraphicElement>("GraphicElement") + .def(init<GraphicElement::type_t, GraphicElement::style_t, float, float, float, float, float>( + (args("type"), "style", "x1", "y1", "x2", "y2", "z"))) .def_readwrite("type", &GraphicElement::type) .def_readwrite("x1", &GraphicElement::x1) .def_readwrite("y1", &GraphicElement::y1) @@ -104,9 +125,16 @@ BOOST_PYTHON_MODULE(MODULE_NAME) typedef std::unordered_map<IdString, std::string> AttrMap; typedef std::unordered_map<IdString, PortInfo> PortMap; typedef std::unordered_map<IdString, IdString> PinMap; + typedef std::unordered_map<IdString, std::unique_ptr<Region>> RegionMap; class_<BaseCtx, BaseCtx *, boost::noncopyable>("BaseCtx", no_init); + auto loc_cls = class_<Loc>("Loc") + .def(init<int, int, int>()) + .def_readwrite("x", &Loc::x) + .def_readwrite("y", &Loc::y) + .def_readwrite("z", &Loc::z); + auto ci_cls = class_<ContextualWrapper<CellInfo &>>("CellInfo", no_init); readwrite_wrapper<CellInfo &, decltype(&CellInfo::name), &CellInfo::name, conv_to_str<IdString>, conv_from_str<IdString>>::def_wrap(ci_cls, "name"); @@ -135,6 +163,8 @@ BOOST_PYTHON_MODULE(MODULE_NAME) typedef std::vector<PortRef> PortRefVector; typedef std::unordered_map<WireId, PipMap> WireMap; + typedef std::unordered_set<BelId> BelSet; + typedef std::unordered_set<WireId> WireSet; auto ni_cls = class_<ContextualWrapper<NetInfo &>>("NetInfo", no_init); readwrite_wrapper<NetInfo &, decltype(&NetInfo::name), &NetInfo::name, conv_to_str<IdString>, @@ -163,10 +193,25 @@ BOOST_PYTHON_MODULE(MODULE_NAME) def("parse_json", parse_json_shim); def("load_design", load_design_shim, return_value_policy<manage_new_object>()); + auto region_cls = class_<ContextualWrapper<Region &>>("Region", no_init); + readwrite_wrapper<Region &, decltype(&Region::name), &Region::name, conv_to_str<IdString>, + conv_from_str<IdString>>::def_wrap(region_cls, "name"); + readwrite_wrapper<Region &, decltype(&Region::constr_bels), &Region::constr_bels, pass_through<bool>, + pass_through<bool>>::def_wrap(region_cls, "constr_bels"); + readwrite_wrapper<Region &, decltype(&Region::constr_wires), &Region::constr_wires, pass_through<bool>, + pass_through<bool>>::def_wrap(region_cls, "constr_bels"); + readwrite_wrapper<Region &, decltype(&Region::constr_pips), &Region::constr_pips, pass_through<bool>, + pass_through<bool>>::def_wrap(region_cls, "constr_pips"); + readonly_wrapper<Region &, decltype(&Region::bels), &Region::bels, wrap_context<BelSet &>>::def_wrap(region_cls, + "bels"); + readonly_wrapper<Region &, decltype(&Region::wires), &Region::wires, wrap_context<WireSet &>>::def_wrap(region_cls, + "wires"); + WRAP_MAP(AttrMap, pass_through<std::string>, "AttrMap"); WRAP_MAP(PortMap, wrap_context<PortInfo &>, "PortMap"); WRAP_MAP(PinMap, conv_to_str<IdString>, "PinMap"); WRAP_MAP(WireMap, wrap_context<PipMap &>, "WireMap"); + WRAP_MAP_UPTR(RegionMap, "RegionMap"); WRAP_VECTOR(PortRefVector, wrap_context<PortRef &>); @@ -190,8 +235,14 @@ void init_python(const char *executable, bool first) PyImport_AppendInittab(TOSTRING(MODULE_NAME), PYINIT_MODULE_NAME); Py_SetProgramName(program); Py_Initialize(); - if (first) - PyImport_ImportModule(TOSTRING(MODULE_NAME)); + + // Add cwd to Python's search path so `import` can be used in user scripts + boost::filesystem::path cwd = boost::filesystem::absolute("./").normalize(); + PyObject *sys_path = PySys_GetObject("path"); + PyList_Insert(sys_path, 0, PyUnicode_FromString(cwd.string().c_str())); + + PyImport_ImportModule(TOSTRING(MODULE_NAME)); + PyRun_SimpleString("from " TOSTRING(MODULE_NAME) " import *"); } catch (boost::python::error_already_set const &) { // Parse and output the exception std::string perror_str = parse_python_exception(); @@ -217,12 +268,15 @@ void execute_python_file(const char *python_file) fprintf(stderr, "Fatal error: file not found %s\n", python_file); exit(1); } - PyRun_SimpleFile(fp, python_file); + int result = PyRun_SimpleFile(fp, python_file); fclose(fp); + if (result == -1) { + log_error("Error occurred while executing Python script %s\n", python_file); + } } catch (boost::python::error_already_set const &) { // Parse and output the exception std::string perror_str = parse_python_exception(); - std::cout << "Error in Python: " << perror_str << std::endl; + log_error("Error in Python: %s\n", perror_str.c_str()); } } diff --git a/common/pycontainers.h b/common/pycontainers.h index 70f69c51..5de2f6d2 100644 --- a/common/pycontainers.h +++ b/common/pycontainers.h @@ -345,6 +345,12 @@ template <typename T, typename value_conv> struct map_wrapper std::terminate(); } + static bool contains(wrapped_map &x, std::string const &i) + { + K k = PythonConversion::string_converter<K>().from_str(x.ctx, i); + return x.base.count(k); + } + static void wrap(const char *map_name, const char *kv_name, const char *kv_iter_name, const char *iter_name) { map_pair_wrapper<typename KV::first_type, typename KV::second_type, value_conv>::wrap(kv_name, kv_iter_name); @@ -353,6 +359,7 @@ template <typename T, typename value_conv> struct map_wrapper class_<wrapped_map>(map_name, no_init) .def("__iter__", rw::iter) .def("__len__", len) + .def("__contains__", contains) .def("__getitem__", get) .def("__setitem__", set, with_custodian_and_ward<1, 2>()); } @@ -465,6 +472,12 @@ template <typename T> struct map_wrapper_uptr std::terminate(); } + static bool contains(wrapped_map &x, std::string const &i) + { + K k = PythonConversion::string_converter<K>().from_str(x.ctx, i); + return x.base.count(k); + } + static void wrap(const char *map_name, const char *kv_name, const char *kv_iter_name, const char *iter_name) { map_pair_wrapper_uptr<typename KV::first_type, typename KV::second_type>::wrap(kv_name, kv_iter_name); @@ -473,6 +486,7 @@ template <typename T> struct map_wrapper_uptr class_<wrapped_map>(map_name, no_init) .def("__iter__", rw::iter) .def("__len__", len) + .def("__contains__", contains) .def("__getitem__", get) .def("__setitem__", set, with_custodian_and_ward<1, 2>()); } diff --git a/common/pywrappers.h b/common/pywrappers.h index 4e463afd..1d970985 100644 --- a/common/pywrappers.h +++ b/common/pywrappers.h @@ -155,11 +155,15 @@ template <typename Class, typename FuncT, FuncT fn, typename rv_conv> struct fn_ using class_type = typename WrapIfNotContext<Class>::maybe_wrapped_t; using conv_result_type = typename rv_conv::ret_type; - static conv_result_type wrapped_fn(class_type &cls) + static object wrapped_fn(class_type &cls) { Context *ctx = get_ctx<Class>(cls); Class &base = get_base<Class>(cls); - return rv_conv()(ctx, (base.*fn)()); + try { + return object(rv_conv()(ctx, (base.*fn)())); + } catch (bad_wrap &) { + return object(); + } } template <typename WrapCls> static void def_wrap(WrapCls cls_, const char *name) { cls_.def(name, wrapped_fn); } @@ -172,11 +176,15 @@ template <typename Class, typename FuncT, FuncT fn, typename rv_conv, typename a using conv_result_type = typename rv_conv::ret_type; using conv_arg1_type = typename arg1_conv::arg_type; - static conv_result_type wrapped_fn(class_type &cls, conv_arg1_type arg1) + static object wrapped_fn(class_type &cls, conv_arg1_type arg1) { Context *ctx = get_ctx<Class>(cls); Class &base = get_base<Class>(cls); - return rv_conv()(ctx, (base.*fn)(arg1_conv()(ctx, arg1))); + try { + return object(rv_conv()(ctx, (base.*fn)(arg1_conv()(ctx, arg1)))); + } catch (bad_wrap &) { + return object(); + } } template <typename WrapCls> static void def_wrap(WrapCls cls_, const char *name) { cls_.def(name, wrapped_fn); } @@ -191,11 +199,15 @@ struct fn_wrapper_2a using conv_arg1_type = typename arg1_conv::arg_type; using conv_arg2_type = typename arg2_conv::arg_type; - static conv_result_type wrapped_fn(class_type &cls, conv_arg1_type arg1, conv_arg2_type arg2) + static object wrapped_fn(class_type &cls, conv_arg1_type arg1, conv_arg2_type arg2) { Context *ctx = get_ctx<Class>(cls); Class &base = get_base<Class>(cls); - return rv_conv()(ctx, (base.*fn)(arg1_conv()(ctx, arg1), arg2_conv()(ctx, arg2))); + try { + return object(rv_conv()(ctx, (base.*fn)(arg1_conv()(ctx, arg1), arg2_conv()(ctx, arg2)))); + } catch (bad_wrap &) { + return object(); + } } template <typename WrapCls> static void def_wrap(WrapCls cls_, const char *name) { cls_.def(name, wrapped_fn); } @@ -212,11 +224,16 @@ struct fn_wrapper_3a using conv_arg2_type = typename arg2_conv::arg_type; using conv_arg3_type = typename arg3_conv::arg_type; - static conv_result_type wrapped_fn(class_type &cls, conv_arg1_type arg1, conv_arg2_type arg2, conv_arg3_type arg3) + static object wrapped_fn(class_type &cls, conv_arg1_type arg1, conv_arg2_type arg2, conv_arg3_type arg3) { Context *ctx = get_ctx<Class>(cls); Class &base = get_base<Class>(cls); - return rv_conv()(ctx, (base.*fn)(arg1_conv()(ctx, arg1), arg2_conv()(ctx, arg2), arg3_conv()(ctx, arg3))); + try { + return object( + rv_conv()(ctx, (base.*fn)(arg1_conv()(ctx, arg1), arg2_conv()(ctx, arg2), arg3_conv()(ctx, arg3)))); + } catch (bad_wrap &) { + return object(); + } } template <typename WrapCls> static void def_wrap(WrapCls cls_, const char *name) { cls_.def(name, wrapped_fn); } @@ -250,6 +267,11 @@ template <typename Class, typename FuncT, FuncT fn, typename arg1_conv> struct f } template <typename WrapCls> static void def_wrap(WrapCls cls_, const char *name) { cls_.def(name, wrapped_fn); } + + template <typename WrapCls, typename Ta> static void def_wrap(WrapCls cls_, const char *name, Ta a = arg("arg1")) + { + cls_.def(name, wrapped_fn, a); + } }; // Two parameters, one return @@ -267,9 +289,14 @@ template <typename Class, typename FuncT, FuncT fn, typename arg1_conv, typename } template <typename WrapCls> static void def_wrap(WrapCls cls_, const char *name) { cls_.def(name, wrapped_fn); } + + template <typename WrapCls, typename Ta> static void def_wrap(WrapCls cls_, const char *name, const Ta &a) + { + cls_.def(name, wrapped_fn, a); + } }; -// Three parameters, one return +// Three parameters, no return template <typename Class, typename FuncT, FuncT fn, typename arg1_conv, typename arg2_conv, typename arg3_conv> struct fn_wrapper_3a_v { @@ -286,6 +313,98 @@ struct fn_wrapper_3a_v } template <typename WrapCls> static void def_wrap(WrapCls cls_, const char *name) { cls_.def(name, wrapped_fn); } + + template <typename WrapCls, typename Ta> static void def_wrap(WrapCls cls_, const char *name, const Ta &a) + { + cls_.def(name, wrapped_fn, a); + } +}; + +// Four parameters, no return +template <typename Class, typename FuncT, FuncT fn, typename arg1_conv, typename arg2_conv, typename arg3_conv, + typename arg4_conv> +struct fn_wrapper_4a_v +{ + using class_type = typename WrapIfNotContext<Class>::maybe_wrapped_t; + using conv_arg1_type = typename arg1_conv::arg_type; + using conv_arg2_type = typename arg2_conv::arg_type; + using conv_arg3_type = typename arg3_conv::arg_type; + using conv_arg4_type = typename arg4_conv::arg_type; + + static void wrapped_fn(class_type &cls, conv_arg1_type arg1, conv_arg2_type arg2, conv_arg3_type arg3, + conv_arg4_type arg4) + { + Context *ctx = get_ctx<Class>(cls); + Class &base = get_base<Class>(cls); + return (base.*fn)(arg1_conv()(ctx, arg1), arg2_conv()(ctx, arg2), arg3_conv()(ctx, arg3), + arg4_conv()(ctx, arg4)); + } + + template <typename WrapCls> static void def_wrap(WrapCls cls_, const char *name) { cls_.def(name, wrapped_fn); } + + template <typename WrapCls, typename Ta> static void def_wrap(WrapCls cls_, const char *name, const Ta &a) + { + cls_.def(name, wrapped_fn, a); + } +}; + +// Five parameters, no return +template <typename Class, typename FuncT, FuncT fn, typename arg1_conv, typename arg2_conv, typename arg3_conv, + typename arg4_conv, typename arg5_conv> +struct fn_wrapper_5a_v +{ + using class_type = typename WrapIfNotContext<Class>::maybe_wrapped_t; + using conv_arg1_type = typename arg1_conv::arg_type; + using conv_arg2_type = typename arg2_conv::arg_type; + using conv_arg3_type = typename arg3_conv::arg_type; + using conv_arg4_type = typename arg4_conv::arg_type; + using conv_arg5_type = typename arg5_conv::arg_type; + + static void wrapped_fn(class_type &cls, conv_arg1_type arg1, conv_arg2_type arg2, conv_arg3_type arg3, + conv_arg4_type arg4, conv_arg5_type arg5) + { + Context *ctx = get_ctx<Class>(cls); + Class &base = get_base<Class>(cls); + return (base.*fn)(arg1_conv()(ctx, arg1), arg2_conv()(ctx, arg2), arg3_conv()(ctx, arg3), + arg4_conv()(ctx, arg4), arg5_conv()(ctx, arg5)); + } + + template <typename WrapCls> static void def_wrap(WrapCls cls_, const char *name) { cls_.def(name, wrapped_fn); } + + template <typename WrapCls, typename Ta> static void def_wrap(WrapCls cls_, const char *name, const Ta &a) + { + cls_.def(name, wrapped_fn, a); + } +}; + +// Six parameters, no return +template <typename Class, typename FuncT, FuncT fn, typename arg1_conv, typename arg2_conv, typename arg3_conv, + typename arg4_conv, typename arg5_conv, typename arg6_conv> +struct fn_wrapper_6a_v +{ + using class_type = typename WrapIfNotContext<Class>::maybe_wrapped_t; + using conv_arg1_type = typename arg1_conv::arg_type; + using conv_arg2_type = typename arg2_conv::arg_type; + using conv_arg3_type = typename arg3_conv::arg_type; + using conv_arg4_type = typename arg4_conv::arg_type; + using conv_arg5_type = typename arg5_conv::arg_type; + using conv_arg6_type = typename arg6_conv::arg_type; + + static void wrapped_fn(class_type &cls, conv_arg1_type arg1, conv_arg2_type arg2, conv_arg3_type arg3, + conv_arg4_type arg4, conv_arg5_type arg5, conv_arg6_type arg6) + { + Context *ctx = get_ctx<Class>(cls); + Class &base = get_base<Class>(cls); + return (base.*fn)(arg1_conv()(ctx, arg1), arg2_conv()(ctx, arg2), arg3_conv()(ctx, arg3), + arg4_conv()(ctx, arg4), arg5_conv()(ctx, arg5), arg6_conv()(ctx, arg6)); + } + + template <typename WrapCls> static void def_wrap(WrapCls cls_, const char *name) { cls_.def(name, wrapped_fn); } + + template <typename WrapCls, typename Ta> static void def_wrap(WrapCls cls_, const char *name, const Ta &a) + { + cls_.def(name, wrapped_fn, a); + } }; // Wrapped getter diff --git a/common/settings.h b/common/settings.h index 0c4a67db..b57947c9 100644 --- a/common/settings.h +++ b/common/settings.h @@ -45,19 +45,30 @@ class Settings return defaultValue; } - template <typename T> void set(const char *name, T value) - { - IdString id = ctx->id(name); - auto pair = ctx->settings.emplace(id, std::to_string(value)); - if (!pair.second) { - ctx->settings[pair.first->first] = value; - } - } + template <typename T> void set(const char *name, T value); private: Context *ctx; }; +template <typename T> inline void Settings::set(const char *name, T value) +{ + IdString id = ctx->id(name); + auto pair = ctx->settings.emplace(id, std::to_string(value)); + if (!pair.second) { + ctx->settings[pair.first->first] = value; + } +} + +template <> inline void Settings::set<std::string>(const char *name, std::string value) +{ + IdString id = ctx->id(name); + auto pair = ctx->settings.emplace(id, value); + if (!pair.second) { + ctx->settings[pair.first->first] = value; + } +} + NEXTPNR_NAMESPACE_END #endif // SETTINGS_H diff --git a/common/timing.cc b/common/timing.cc index 2a0af874..e67ac231 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -546,7 +546,8 @@ struct Timing for (size_t i = 0; i < sink_net->users.size(); i++) { auto &user = sink_net->users.at(i); if (user.cell == drv.cell && user.port == port.first) { - sink_nd.min_required.at(i) = net_min_required - comb_delay.maxDelay(); + sink_nd.min_required.at(i) = std::min(sink_nd.min_required.at(i), + net_min_required - comb_delay.maxDelay()); break; } } @@ -752,7 +753,7 @@ void timing_analysis(Context *ctx, bool print_histogram, bool print_fmax, bool p } if (clock_reports.empty()) { - log_warning("No clocks found in design"); + log_warning("No clocks found in design\n"); } std::sort(xclock_paths.begin(), xclock_paths.end(), [ctx](const ClockPair &a, const ClockPair &b) { @@ -904,10 +905,9 @@ void timing_analysis(Context *ctx, bool print_histogram, bool print_fmax, bool p if (!warn_on_failure || passed) log_info("Max frequency for clock %*s'%s': %.02f MHz (%s at %.02f MHz)\n", width, "", clock_name.c_str(), clock_fmax[clock.first], passed ? "PASS" : "FAIL", target); - else - if (bool_or_default(ctx->settings, ctx->id("timing/allowFail"), false)) + else if (bool_or_default(ctx->settings, ctx->id("timing/allowFail"), false)) log_warning("Max frequency for clock %*s'%s': %.02f MHz (%s at %.02f MHz)\n", width, "", - clock_name.c_str(), clock_fmax[clock.first], passed ? "PASS" : "FAIL", target); + clock_name.c_str(), clock_fmax[clock.first], passed ? "PASS" : "FAIL", target); else log_nonfatal_error("Max frequency for clock %*s'%s': %.02f MHz (%s at %.02f MHz)\n", width, "", clock_name.c_str(), clock_fmax[clock.first], passed ? "PASS" : "FAIL", target); diff --git a/common/timing_opt.cc b/common/timing_opt.cc index c0968db7..898222ab 100644 --- a/common/timing_opt.cc +++ b/common/timing_opt.cc @@ -84,6 +84,7 @@ class TimingOptimiser bool optimise() { log_info("Running timing-driven placement optimisation...\n"); + ctx->lock(); if (ctx->verbose) timing_analysis(ctx, false, true, false, false); for (int i = 0; i < 30; i++) { @@ -96,6 +97,7 @@ class TimingOptimiser if (ctx->verbose) timing_analysis(ctx, false, true, false, false); } + ctx->unlock(); return true; } diff --git a/docs/archapi.md b/docs/archapi.md index 3c938865..6e59ecdb 100644 --- a/docs/archapi.md +++ b/docs/archapi.md @@ -490,3 +490,14 @@ a certain number of different clock signals allowed for a group of bels. Returns true if a bell in the current configuration is valid, i.e. if `isValidBelForCell()` would return true for the current mapping. + + +### static const std::string defaultPlacer + +Name of the default placement algorithm for the architecture, if +`--placer` isn't specified on the command line. + +### static const std::vector\<std::string\> availablePlacers + +Name of available placer algorithms for the architecture, used +to provide help for and validate `--placer`.
\ No newline at end of file diff --git a/docs/generic.md b/docs/generic.md new file mode 100644 index 00000000..d6ddbfb6 --- /dev/null +++ b/docs/generic.md @@ -0,0 +1,119 @@ +# nextpnr Generic Architecture + +Instead of implementing the [C++ API](archapi.md), you can programmatically +build up a description of an FPGA using the generic architecture and the +Python API. + +A basic packer is provided that supports LUTs, flipflops and IO buffer insertion. +Packing could also be implemented using the Python API. + +At present there is no support for cell timing in the generic architecture. This +will be worked on in the future. + +## Python API + +All identifiers (`IdString`) are automatically converted to +and from a Python string, so no manual conversion is required. + +Argument names are included in the Python bindings, +so named arguments may be used. + +### void addWire(IdString name, IdString type, int x, int y); + +Adds a wire with a name, type (for user purposes only, ignored by all nextpnr code other than the UI) to the FPGA description. x and y give a nominal location of the wire for delay estimation purposes. Delay estimates are important for router performance (as the router uses an A* type algorithm), even if timing is not of importance. + +### addPip(IdString name, IdString type, IdString srcWire, IdString dstWire, DelayInfo delay, Loc loc); + +Adds a pip (programmable connection between two named wires). Pip delays that correspond to delay estimates are important for router performance (as the router uses an A* type algorithm), even if timing is otherwise not of importance. + +Loc is constructed using `Loc(x, y, z)`. 'z' for pips is only important if region constraints (e.g. for partial reconfiguration regions) are used. + +### void addAlias(IdString name, IdString type, IdString srcWire, IdString dstWire, DelayInfo delay); + +Adds a wire alias (fixed connection between two named wires). Alias delays that correspond to delay estimates are important for router performance (as the router uses an A* type algorithm), even if timing is otherwise not of importance. + +### void addBel(IdString name, IdString type, Loc loc, bool gb); + +Adds a bel to the FPGA description. Bel type should match the type of cells in the netlist that are placed at this bel (see below for information on special bel types supported by the packer). Loc is constructed using `Loc(x, y, z)` and must be unique. + +### void addBelInput(IdString bel, IdString name, IdString wire); +### void addBelOutput(IdString bel, IdString name, IdString wire); +### void addBelInout(IdString bel, IdString name, IdString wire); + +Adds an input, output or inout pin to a bel, with an associated wire. Note that both `bel` and `wire` must have been created before calling this function. + +### void addGroupBel(IdString group, IdString bel); +### void addGroupWire(IdString group, IdString wire); +### void addGroupPip(IdString group, IdString pip); +### void addGroupGroup(IdString group, IdString grp); + +Add a bel, wire, pip or subgroup to a group, which will be created if it doesn't already exist. Groups are purely for visual presentation purposes in the user interface and are not used by any place-and-route algorithms. + +### void addDecalGraphic(DecalId decal, const GraphicElement &graphic); + +Add a graphic element to a _decal_, a reusable drawing that may be used to represent multiple wires, pips, bels or groups in the UI (with different offsets). The decal will be created if it doesn't already exist + +### void setWireDecal(WireId wire, DecalXY decalxy); +### void setPipDecal(PipId pip, DecalXY decalxy); +### void setBelDecal(BelId bel, DecalXY decalxy); +### void setGroupDecal(GroupId group, DecalXY decalxy); + +Sets the decal ID and offset for a wire, bel, pip or group in the UI. + +### void setWireAttr(IdString wire, IdString key, const std::string &value); +### void setPipAttr(IdString pip, IdString key, const std::string &value); +### void setBelAttr(IdString bel, IdString key, const std::string &value); + +Sets an attribute on a wire, pip or bel. Attributes are displayed in the tree view in the UI, but have no bearing on place-and-route itself. + +### void setLutK(int K); + +Sets the number of input pins a LUT in the architecture has. Only affects the generic packer, if a custom packer or no packer is used this value has no effect - there is no need for the architecture to have LUTs at all in this case. + +### void setDelayScaling(double scale, double offset); + +Set the linear scaling vs distance and fixed offset (both values in nanoseconds) for routing delay estimates. + +### void addCellTimingClock(IdString cell, IdString port); + +Set the timing class of a port on a particular cell to a clock input. + +_NOTE: All cell timing functions apply to an individual named cell and not a cell type. This is because +cell-specific configuration might affect timing, e.g. whether or not the register is used for a slice._ + +### void addCellTimingDelay(IdString cell, IdString fromPort, IdString toPort, DelayInfo delay); + +Specify the combinational delay between two ports of a cell, and set the timing class of + those ports as combinational input/output. + +### void addCellTimingSetupHold(IdString cell, IdString port, IdString clock, DelayInfo setup, DelayInfo hold); + +Specify setup and hold timings for a port of a cell, and set the timing class of that port as register input. + +### void addCellTimingClockToOut(IdString cell, IdString port, IdString clock, DelayInfo clktoq); + +Specify clock-to-out time for a port of a cell, and set the timing class of that port as register output. + +## Generic Packer + +The generic packer combines K-input LUTs (`LUT` cells) and simple D-type flip flops (`DFF` cells) (posedge clock only, no set/reset or enable) into a `GENERIC_SLICE` cell. It also inserts `GENERIC_IOB`s onto any top level IO pins without an IO buffer. + +Thus, the architecture should provide bels with the following ports in order to use the generic packer: + + - `GENERIC_SLICE` bels with `CLK` input, `I[0]` .. `I[K-1]` LUT inputs and `Q` LUT/FF output (N.B. both LUT and FF outputs are not available at the same time) + - `GENERIC_IOB` bels with `I` output buffer input, `EN` output enable input, and `O` input buffer output. + +See [prims.v](../generic/synth/prims.v) for Verilog simulation models for all these cells. + +[synth_generic.tcl](../generic/synth/synth_generic.tcl) can be used with Yosys to perform synthesis to the generic `LUT` and `DFF` cells which the generic packer supports. Invoke it using `tcl synth_generic.tcl K out.json` where _K_ is the number of LUT inputs and _out.json_ the name of the JSON file to write. + +## Validity Checks + +The following constraints are enforced by the generic architecture during placement. + + - `GENERIC_SLICE` bels may only have one clock signal per tile (xy location) + - If the `PACK_GROUP` attribute is set to a non-zero value on cells, then only cells with the same `PACK_GROUP` attribute (or `PACK_GROUP` negative or unset) may share a tile. This could be set by the Python API or during synthesis. + +## Implementation Example + +An artificial, procedural architecture is included in the [generic/examples](../generic/examples) folder. [simple.py](../generic/examples/simple.py) sets up the architecture, and [report.py](../generic/examples/report.py) saves post-place-and-route design to a text file (in place of bitstream generation). [simple.sh](../generic/examples/simple.sh) can be used to synthesise and place-and-route a simple blinky for this architecture. diff --git a/ecp5/arch.cc b/ecp5/arch.cc index da0f7b1a..91db8d81 100644 --- a/ecp5/arch.cc +++ b/ecp5/arch.cc @@ -28,6 +28,7 @@ #include "log.h" #include "nextpnr.h" #include "placer1.h" +#include "placer_heap.h" #include "router1.h" #include "timing.h" #include "util.h" @@ -456,7 +457,8 @@ delay_t Arch::estimateDelay(WireId src, WireId dst) const auto src_loc = est_location(src), dst_loc = est_location(dst); int dx = abs(src_loc.first - dst_loc.first), dy = abs(src_loc.second - dst_loc.second); - return (130 - 25 * args.speed) * + + return (120 - 22 * args.speed) * (6 + std::max(dx - 5, 0) + std::max(dy - 5, 0) + 2 * (std::min(dx, 5) + std::min(dy, 5))); } @@ -467,7 +469,6 @@ delay_t Arch::predictDelay(const NetInfo *net_info, const PortRef &sink) const return 0; auto driver_loc = getBelLocation(driver.cell->bel); auto sink_loc = getBelLocation(sink.cell->bel); - // Encourage use of direct interconnect if (driver_loc.x == sink_loc.x && driver_loc.y == sink_loc.y) { if ((sink.port == id_A0 || sink.port == id_A1) && (driver.port == id_F1) && @@ -485,7 +486,8 @@ delay_t Arch::predictDelay(const NetInfo *net_info, const PortRef &sink) const } int dx = abs(driver_loc.x - sink_loc.x), dy = abs(driver_loc.y - sink_loc.y); - return (130 - 25 * args.speed) * + + return (120 - 22 * args.speed) * (6 + std::max(dx - 5, 0) + std::max(dy - 5, 0) + 2 * (std::min(dx, 5) + std::min(dy, 5))); } @@ -502,14 +504,29 @@ bool Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay } } +delay_t Arch::getRipupDelayPenalty() const { return 400; } + // ----------------------------------------------------------------------- bool Arch::place() { - bool result = placer1(getCtx(), Placer1Cfg(getCtx())); - if (result) - permute_luts(); - return result; + std::string placer = str_or_default(settings, id("placer"), defaultPlacer); + + if (placer == "heap") { + PlacerHeapCfg cfg(getCtx()); + cfg.criticalityExponent = 4; + cfg.ioBufTypes.insert(id_TRELLIS_IO); + if (!placer_heap(getCtx(), cfg)) + return false; + } else if (placer == "sa") { + if (!placer1(getCtx(), Placer1Cfg(getCtx()))) + return false; + } else { + log_error("ECP5 architecture does not support placer '%s'\n", placer.c_str()); + } + + permute_luts(); + return true; } bool Arch::route() @@ -605,6 +622,11 @@ DecalXY Arch::getGroupDecal(GroupId pip) const { return {}; }; bool Arch::getDelayFromTimingDatabase(IdString tctype, IdString from, IdString to, DelayInfo &delay) const { + auto fnd_dk = celldelay_cache.find({tctype, from, to}); + if (fnd_dk != celldelay_cache.end()) { + delay = fnd_dk->second.second; + return fnd_dk->second.first; + } for (int i = 0; i < speed_grade->num_cell_timings; i++) { const auto &tc = speed_grade->cell_timings[i]; if (tc.cell_type == tctype.index) { @@ -613,9 +635,11 @@ bool Arch::getDelayFromTimingDatabase(IdString tctype, IdString from, IdString t if (dly.from_port == from.index && dly.to_port == to.index) { delay.max_delay = dly.max_delay; delay.min_delay = dly.min_delay; + celldelay_cache[{tctype, from, to}] = std::make_pair(true, delay); return true; } } + celldelay_cache[{tctype, from, to}] = std::make_pair(false, DelayInfo()); return false; } } @@ -645,7 +669,6 @@ void Arch::getSetupHoldFromTimingDatabase(IdString tctype, IdString clock, IdStr bool Arch::getCellDelay(const CellInfo *cell, IdString fromPort, IdString toPort, DelayInfo &delay) const { - // Data for -8 grade if (cell->type == id_TRELLIS_SLICE) { bool has_carry = cell->sliceInfo.is_carry; @@ -965,4 +988,16 @@ WireId Arch::getBankECLK(int bank, int eclk) return getWireByLocAndBasename(Location(0, 0), "G_BANK" + std::to_string(bank) + "ECLK" + std::to_string(eclk)); } +#ifdef WITH_HEAP +const std::string Arch::defaultPlacer = "heap"; +#else +const std::string Arch::defaultPlacer = "sa"; +#endif + +const std::vector<std::string> Arch::availablePlacers = {"sa", +#ifdef WITH_HEAP + "heap" +#endif +}; + NEXTPNR_NAMESPACE_END diff --git a/ecp5/arch.h b/ecp5/arch.h index ab4a4e00..cee071e7 100644 --- a/ecp5/arch.h +++ b/ecp5/arch.h @@ -448,6 +448,30 @@ struct ArchArgs } speed = SPEED_6; }; +struct DelayKey +{ + IdString celltype, from, to; + inline bool operator==(const DelayKey &other) const + { + return celltype == other.celltype && from == other.from && to == other.to; + } +}; + +NEXTPNR_NAMESPACE_END +namespace std { +template <> struct hash<NEXTPNR_NAMESPACE_PREFIX DelayKey> +{ + std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX DelayKey &dk) const noexcept + { + std::size_t seed = std::hash<NEXTPNR_NAMESPACE_PREFIX IdString>()(dk.celltype); + seed ^= std::hash<NEXTPNR_NAMESPACE_PREFIX IdString>()(dk.from) + 0x9e3779b9 + (seed << 6) + (seed >> 2); + seed ^= std::hash<NEXTPNR_NAMESPACE_PREFIX IdString>()(dk.to) + 0x9e3779b9 + (seed << 6) + (seed >> 2); + return seed; + } +}; +} // namespace std +NEXTPNR_NAMESPACE_BEGIN + struct Arch : BaseCtx { const ChipInfoPOD *chip_info; @@ -918,7 +942,7 @@ struct Arch : BaseCtx delay_t estimateDelay(WireId src, WireId dst) const; delay_t predictDelay(const NetInfo *net_info, const PortRef &sink) const; delay_t getDelayEpsilon() const { return 20; } - delay_t getRipupDelayPenalty() const { return 400; } + delay_t getRipupDelayPenalty() const; float getDelayNS(delay_t v) const { return v * 0.001; } DelayInfo getDelayFromNS(float ns) const { @@ -1019,6 +1043,11 @@ struct Arch : BaseCtx IdString id_clk, id_lsr; IdString id_clkmux, id_lsrmux; IdString id_srmode, id_mode; + + mutable std::unordered_map<DelayKey, std::pair<bool, DelayInfo>> celldelay_cache; + + static const std::string defaultPlacer; + static const std::vector<std::string> availablePlacers; }; NEXTPNR_NAMESPACE_END diff --git a/ecp5/arch_pybindings.cc b/ecp5/arch_pybindings.cc index 5e73a673..18d21112 100644 --- a/ecp5/arch_pybindings.cc +++ b/ecp5/arch_pybindings.cc @@ -133,6 +133,13 @@ void arch_wrap_python() fn_wrapper_2a_v<Context, decltype(&Context::addClock), &Context::addClock, conv_from_str<IdString>, pass_through<float>>::def_wrap(ctx_cls, "addClock"); + fn_wrapper_5a_v<Context, decltype(&Context::createRectangularRegion), &Context::createRectangularRegion, + conv_from_str<IdString>, pass_through<int>, pass_through<int>, pass_through<int>, + pass_through<int>>::def_wrap(ctx_cls, "createRectangularRegion"); + fn_wrapper_2a_v<Context, decltype(&Context::addBelToRegion), &Context::addBelToRegion, conv_from_str<IdString>, + conv_from_str<BelId>>::def_wrap(ctx_cls, "addBelToRegion"); + fn_wrapper_2a_v<Context, decltype(&Context::constrainCellToRegion), &Context::constrainCellToRegion, + conv_from_str<IdString>, conv_from_str<IdString>>::def_wrap(ctx_cls, "constrainCellToRegion"); WRAP_RANGE(Bel, conv_to_str<BelId>); WRAP_RANGE(Wire, conv_to_str<WireId>); diff --git a/ecp5/bitstream.cc b/ecp5/bitstream.cc index a9c82524..d549a727 100644 --- a/ecp5/bitstream.cc +++ b/ecp5/bitstream.cc @@ -134,7 +134,7 @@ inline int chtohex(char c) return hex.find(c); } -std::vector<bool> parse_init_str(const std::string &str, int length) +std::vector<bool> parse_init_str(const std::string &str, int length, const char *cellname) { // Parse a string that may be binary or hex std::vector<bool> result; @@ -161,7 +161,8 @@ std::vector<bool> parse_init_str(const std::string &str, int length) log_error("hex string value too long, expected up to %d bits and found %d.\n", length, int(str.length())); for (int i = 0; i < int(str.length()); i++) { char c = str.at((str.size() - i) - 1); - NPNR_ASSERT(c == '0' || c == '1' || c == 'X' || c == 'x'); + if (c != '0' && c != '1' && c != 'X' && c != 'x') + log_error("Found illegal character '%c' while processing parameters for cell '%s'\n", c, cellname); result.at(i) = (c == '1'); } } @@ -970,7 +971,7 @@ void write_bitstream(Context *ctx, std::string base_config_file, std::string tex for (int i = 0; i <= 0x3F; i++) { IdString param = ctx->id("INITVAL_" + fmt_str(std::hex << std::uppercase << std::setw(2) << std::setfill('0') << i)); - auto value = parse_init_str(str_or_default(ci->params, param, "0"), 320); + auto value = parse_init_str(str_or_default(ci->params, param, "0"), 320, ci->name.c_str(ctx)); for (int j = 0; j < 16; j++) { // INIT parameter consists of 16 18-bit words with 2-bit padding int ofs = 20 * j; @@ -1078,17 +1079,21 @@ void write_bitstream(Context *ctx, std::string base_config_file, std::string tex tg.config.add_enum(dsp + ".MASKPAT_SOURCE", str_or_default(ci->params, ctx->id("MASKPAT_SOURCE"), "STATIC")); tg.config.add_word(dsp + ".MASK01", - parse_init_str(str_or_default(ci->params, ctx->id("MASK01"), "0x00000000000000"), 56)); + parse_init_str(str_or_default(ci->params, ctx->id("MASK01"), "0x00000000000000"), 56, + ci->name.c_str(ctx))); tg.config.add_enum(dsp + ".CLK0_DIV", str_or_default(ci->params, ctx->id("CLK0_DIV"), "ENABLED")); tg.config.add_enum(dsp + ".CLK1_DIV", str_or_default(ci->params, ctx->id("CLK1_DIV"), "ENABLED")); tg.config.add_enum(dsp + ".CLK2_DIV", str_or_default(ci->params, ctx->id("CLK2_DIV"), "ENABLED")); tg.config.add_enum(dsp + ".CLK3_DIV", str_or_default(ci->params, ctx->id("CLK3_DIV"), "ENABLED")); tg.config.add_word(dsp + ".MCPAT", - parse_init_str(str_or_default(ci->params, ctx->id("MCPAT"), "0x00000000000000"), 56)); + parse_init_str(str_or_default(ci->params, ctx->id("MCPAT"), "0x00000000000000"), 56, + ci->name.c_str(ctx))); tg.config.add_word(dsp + ".MASKPAT", - parse_init_str(str_or_default(ci->params, ctx->id("MASKPAT"), "0x00000000000000"), 56)); + parse_init_str(str_or_default(ci->params, ctx->id("MASKPAT"), "0x00000000000000"), 56, + ci->name.c_str(ctx))); tg.config.add_word(dsp + ".RNDPAT", - parse_init_str(str_or_default(ci->params, ctx->id("RNDPAT"), "0x00000000000000"), 56)); + parse_init_str(str_or_default(ci->params, ctx->id("RNDPAT"), "0x00000000000000"), 56, + ci->name.c_str(ctx))); tg.config.add_enum(dsp + ".GSR", str_or_default(ci->params, ctx->id("GSR"), "ENABLED")); tg.config.add_enum(dsp + ".RESETMODE", str_or_default(ci->params, ctx->id("RESETMODE"), "SYNC")); tg.config.add_enum(dsp + ".FORCE_ZERO_BARREL_SHIFT", diff --git a/ecp5/family.cmake b/ecp5/family.cmake index 799851b2..ca7dc9e9 100644 --- a/ecp5/family.cmake +++ b/ecp5/family.cmake @@ -6,18 +6,18 @@ if (NOT EXTERNAL_CHIPDB) set(TRELLIS_ROOT "/usr/local/share/trellis") endif() - file(GLOB found_pytrellis ${TRELLIS_ROOT}/libtrellis/pytrellis.* - /usr/lib/pytrellis.* - /usr/lib64/pytrellis.* - /usr/lib/trellis/pytrellis.* - /usr/lib64/trellis/pytrellis.*) + if (NOT DEFINED PYTRELLIS_LIBDIR) + find_library(PYTRELLIS pytrellis.so + PATHS ${TRELLIS_ROOT}/libtrellis + PATH_SUFFIXES trellis + DOC "Location of pytrellis library") - if ("${found_pytrellis}" STREQUAL "") - message(FATAL_ERROR "failed to locate pytrellis library!") - endif() + if ("${PYTRELLIS}" STREQUAL "PYTRELLIS-NOTFOUND") + message(FATAL_ERROR "Failed to locate pytrellis library!") + endif() - list(GET found_pytrellis 0 PYTRELLIS_LIB) - get_filename_component(PYTRELLIS_LIBDIR ${PYTRELLIS_LIB} DIRECTORY) + get_filename_component(PYTRELLIS_LIBDIR ${PYTRELLIS} DIRECTORY) + endif() set(DB_PY ${CMAKE_CURRENT_SOURCE_DIR}/ecp5/trellis_import.py) @@ -27,9 +27,9 @@ if (NOT EXTERNAL_CHIPDB) target_include_directories(ecp5_chipdb PRIVATE ${family}/) if (CMAKE_HOST_WIN32) - set(ENV_CMD ${CMAKE_COMMAND} -E env "PYTHONPATH=\"${PYTRELLIS_LIBDIR}\;${TRELLIS_ROOT}/util/common\;${TRELLIS_ROOT}/timing/util\"") + set(ENV_CMD ${CMAKE_COMMAND} -E env "PYTHONPATH=\"${PYTRELLIS_LIBDIR}\;${TRELLIS_ROOT}/util/common\;${TRELLIS_ROOT}/timing/util\"") else() - set(ENV_CMD ${CMAKE_COMMAND} -E env "PYTHONPATH=${PYTRELLIS_LIBDIR}\:${TRELLIS_ROOT}/util/common:${TRELLIS_ROOT}/timing/util") + set(ENV_CMD ${CMAKE_COMMAND} -E env "PYTHONPATH=${PYTRELLIS_LIBDIR}\:${TRELLIS_ROOT}/util/common:${TRELLIS_ROOT}/timing/util") endif() if (MSVC) @@ -38,15 +38,15 @@ if (NOT EXTERNAL_CHIPDB) foreach (dev ${devices}) set(DEV_CC_DB ${CMAKE_CURRENT_SOURCE_DIR}/ecp5/chipdbs/chipdb-${dev}.bin) set(DEV_CC_BBA_DB ${CMAKE_CURRENT_SOURCE_DIR}/ecp5/chipdbs/chipdb-${dev}.bba) - set(DEV_CONSTIDS_INC ${CMAKE_CURRENT_SOURCE_DIR}/ecp5/constids.inc) + set(DEV_CONSTIDS_INC ${CMAKE_CURRENT_SOURCE_DIR}/ecp5/constids.inc) add_custom_command(OUTPUT ${DEV_CC_BBA_DB} - COMMAND ${ENV_CMD} python3 ${DB_PY} -p ${DEV_CONSTIDS_INC} ${dev} > ${DEV_CC_BBA_DB} - DEPENDS ${DB_PY} - ) + COMMAND ${ENV_CMD} python3 ${DB_PY} -p ${DEV_CONSTIDS_INC} ${dev} > ${DEV_CC_BBA_DB} + DEPENDS ${DB_PY} + ) add_custom_command(OUTPUT ${DEV_CC_DB} - COMMAND bbasm ${DEV_CC_BBA_DB} ${DEV_CC_DB} - DEPENDS bbasm ${DEV_CC_BBA_DB} - ) + COMMAND bbasm ${DEV_CC_BBA_DB} ${DEV_CC_DB} + DEPENDS bbasm ${DEV_CC_BBA_DB} + ) target_sources(ecp5_chipdb PRIVATE ${DEV_CC_DB}) set_source_files_properties(${DEV_CC_DB} PROPERTIES HEADER_FILE_ONLY TRUE) foreach (target ${family_targets}) @@ -58,17 +58,17 @@ if (NOT EXTERNAL_CHIPDB) foreach (dev ${devices}) set(DEV_CC_DB ${CMAKE_CURRENT_SOURCE_DIR}/ecp5/chipdbs/chipdb-${dev}.cc) set(DEV_CC_BBA_DB ${CMAKE_CURRENT_SOURCE_DIR}/ecp5/chipdbs/chipdb-${dev}.bba) - set(DEV_CONSTIDS_INC ${CMAKE_CURRENT_SOURCE_DIR}/ecp5/constids.inc) + set(DEV_CONSTIDS_INC ${CMAKE_CURRENT_SOURCE_DIR}/ecp5/constids.inc) add_custom_command(OUTPUT ${DEV_CC_BBA_DB} - COMMAND ${ENV_CMD} python3 ${DB_PY} -p ${DEV_CONSTIDS_INC} ${dev} > ${DEV_CC_BBA_DB}.new - COMMAND mv ${DEV_CC_BBA_DB}.new ${DEV_CC_BBA_DB} - DEPENDS ${DB_PY} - ) + COMMAND ${ENV_CMD} python3 ${DB_PY} -p ${DEV_CONSTIDS_INC} ${dev} > ${DEV_CC_BBA_DB}.new + COMMAND mv ${DEV_CC_BBA_DB}.new ${DEV_CC_BBA_DB} + DEPENDS ${DB_PY} + ) add_custom_command(OUTPUT ${DEV_CC_DB} - COMMAND bbasm --c ${DEV_CC_BBA_DB} ${DEV_CC_DB}.new - COMMAND mv ${DEV_CC_DB}.new ${DEV_CC_DB} - DEPENDS bbasm ${DEV_CC_BBA_DB} - ) + COMMAND bbasm --c ${DEV_CC_BBA_DB} ${DEV_CC_DB}.new + COMMAND mv ${DEV_CC_DB}.new ${DEV_CC_DB} + DEPENDS bbasm ${DEV_CC_BBA_DB} + ) target_sources(ecp5_chipdb PRIVATE ${DEV_CC_DB}) foreach (target ${family_targets}) target_sources(${target} PRIVATE $<TARGET_OBJECTS:ecp5_chipdb>) diff --git a/ecp5/main.cc b/ecp5/main.cc index 15027a5a..bb18aa58 100644 --- a/ecp5/main.cc +++ b/ecp5/main.cc @@ -149,8 +149,8 @@ std::unique_ptr<Context> ECP5CommandHandler::createContext() chipArgs.speed = ArchArgs::SPEED_6; } } - - return std::unique_ptr<Context>(new Context(chipArgs)); + auto ctx = std::unique_ptr<Context>(new Context(chipArgs)); + return ctx; } void ECP5CommandHandler::customAfterLoad(Context *ctx) diff --git a/ecp5/pack.cc b/ecp5/pack.cc index 1b07c2ae..7f00de1f 100644 --- a/ecp5/pack.cc +++ b/ecp5/pack.cc @@ -1390,6 +1390,19 @@ class Ecp5Packer } } + // Miscellaneous packer tasks + void pack_misc() + { + for (auto cell : sorted(ctx->cells)) { + CellInfo *ci = cell.second; + if (ci->type == id_USRMCLK) { + rename_port(ctx, ci, ctx->id("USRMCLKI"), id_PADDO); + rename_port(ctx, ci, ctx->id("USRMCLKTS"), id_PADDT); + rename_port(ctx, ci, ctx->id("USRMCLKO"), id_PADDI); + } + } + } + // Preplace PLL void preplace_plls() { @@ -2371,6 +2384,7 @@ class Ecp5Packer pack_ebr(); pack_dsps(); pack_dcus(); + pack_misc(); preplace_plls(); pack_constants(); pack_dram(); diff --git a/generic/arch.cc b/generic/arch.cc index 77417d27..5617fa63 100644 --- a/generic/arch.cc +++ b/generic/arch.cc @@ -17,10 +17,12 @@ * */ +#include <iostream> #include <math.h> #include "nextpnr.h" #include "placer1.h" #include "router1.h" +#include "util.h" NEXTPNR_NAMESPACE_BEGIN @@ -190,9 +192,53 @@ void Arch::setPipAttr(IdString pip, IdString key, const std::string &value) { pi void Arch::setBelAttr(IdString bel, IdString key, const std::string &value) { bels.at(bel).attrs[key] = value; } +void Arch::setLutK(int K) { args.K = K; } + +void Arch::setDelayScaling(double scale, double offset) +{ + args.delayScale = scale; + args.delayOffset = offset; +} + +void Arch::addCellTimingClock(IdString cell, IdString port) { cellTiming[cell].portClasses[port] = TMG_CLOCK_INPUT; } + +void Arch::addCellTimingDelay(IdString cell, IdString fromPort, IdString toPort, DelayInfo delay) +{ + if (get_or_default(cellTiming[cell].portClasses, fromPort, TMG_IGNORE) == TMG_IGNORE) + cellTiming[cell].portClasses[fromPort] = TMG_COMB_INPUT; + if (get_or_default(cellTiming[cell].portClasses, toPort, TMG_IGNORE) == TMG_IGNORE) + cellTiming[cell].portClasses[toPort] = TMG_COMB_OUTPUT; + cellTiming[cell].combDelays[CellDelayKey{fromPort, toPort}] = delay; +} + +void Arch::addCellTimingSetupHold(IdString cell, IdString port, IdString clock, DelayInfo setup, DelayInfo hold) +{ + TimingClockingInfo ci; + ci.clock_port = clock; + ci.edge = RISING_EDGE; + ci.setup = setup; + ci.hold = hold; + cellTiming[cell].clockingInfo[port].push_back(ci); + cellTiming[cell].portClasses[port] = TMG_REGISTER_INPUT; +} + +void Arch::addCellTimingClockToOut(IdString cell, IdString port, IdString clock, DelayInfo clktoq) +{ + TimingClockingInfo ci; + ci.clock_port = clock; + ci.edge = RISING_EDGE; + ci.clockToQ = clktoq; + cellTiming[cell].clockingInfo[port].push_back(ci); + cellTiming[cell].portClasses[port] = TMG_REGISTER_OUTPUT; +} + // --------------------------------------------------------------- -Arch::Arch(ArchArgs args) : chipName("generic"), args(args) {} +Arch::Arch(ArchArgs args) : chipName("generic"), args(args) +{ + // Dummy for empty decals + decal_graphics[IdString()]; +} void IdString::initialize_arch(const BaseCtx *ctx) {} @@ -259,7 +305,13 @@ IdString Arch::getBelType(BelId bel) const { return bels.at(bel).type; } const std::map<IdString, std::string> &Arch::getBelAttrs(BelId bel) const { return bels.at(bel).attrs; } -WireId Arch::getBelPinWire(BelId bel, IdString pin) const { return bels.at(bel).pins.at(pin).wire; } +WireId Arch::getBelPinWire(BelId bel, IdString pin) const +{ + const auto &bdata = bels.at(bel); + if (!bdata.pins.count(pin)) + log_error("bel '%s' has no pin '%s'\n", bel.c_str(this), pin.c_str(this)); + return bdata.pins.at(pin).wire; +} PortType Arch::getBelPinType(BelId bel, IdString pin) const { return bels.at(bel).pins.at(pin).type; } @@ -421,7 +473,7 @@ delay_t Arch::estimateDelay(WireId src, WireId dst) const const WireInfo &d = wires.at(dst); int dx = abs(s.x - d.x); int dy = abs(s.y - d.y); - return (dx + dy) * grid_distance_to_delay; + return (dx + dy) * args.delayScale + args.delayOffset; } delay_t Arch::predictDelay(const NetInfo *net_info, const PortRef &sink) const @@ -430,22 +482,38 @@ delay_t Arch::predictDelay(const NetInfo *net_info, const PortRef &sink) const auto driver_loc = getBelLocation(driver.cell->bel); auto sink_loc = getBelLocation(sink.cell->bel); - int dx = abs(driver_loc.x - driver_loc.x); - int dy = abs(sink_loc.y - sink_loc.y); - return (dx + dy) * grid_distance_to_delay; + int dx = abs(sink_loc.x - driver_loc.x); + int dy = abs(sink_loc.y - driver_loc.y); + return (dx + dy) * args.delayScale + args.delayOffset; } bool Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay_t &budget) const { return false; } // --------------------------------------------------------------- -bool Arch::place() { return placer1(getCtx(), Placer1Cfg(getCtx())); } +bool Arch::place() +{ + std::string placer = str_or_default(settings, id("placer"), defaultPlacer); + // FIXME: No HeAP because it needs a list of IO buffers + if (placer == "sa") { + return placer1(getCtx(), Placer1Cfg(getCtx())); + } else { + log_error("Generic architecture does not support placer '%s'\n", placer.c_str()); + } +} bool Arch::route() { return router1(getCtx(), Router1Cfg(getCtx())); } // --------------------------------------------------------------- -const std::vector<GraphicElement> &Arch::getDecalGraphics(DecalId decal) const { return decal_graphics.at(decal); } +const std::vector<GraphicElement> &Arch::getDecalGraphics(DecalId decal) const +{ + if (!decal_graphics.count(decal)) { + std::cerr << "No decal named " << decal.str(this) << std::endl; + log_error("No decal named %s!\n", decal.c_str(this)); + } + return decal_graphics.at(decal); +} DecalXY Arch::getBelDecal(BelId bel) const { return bels.at(bel).decalxy; } @@ -459,21 +527,103 @@ DecalXY Arch::getGroupDecal(GroupId group) const { return groups.at(group).decal bool Arch::getCellDelay(const CellInfo *cell, IdString fromPort, IdString toPort, DelayInfo &delay) const { - return false; + if (!cellTiming.count(cell->name)) + return false; + const auto &tmg = cellTiming.at(cell->name); + auto fnd = tmg.combDelays.find(CellDelayKey{fromPort, toPort}); + if (fnd != tmg.combDelays.end()) { + delay = fnd->second; + return true; + } else { + return false; + } } // Get the port class, also setting clockPort if applicable TimingPortClass Arch::getPortTimingClass(const CellInfo *cell, IdString port, int &clockInfoCount) const { - return TMG_IGNORE; + if (!cellTiming.count(cell->name)) + return TMG_IGNORE; + const auto &tmg = cellTiming.at(cell->name); + if (tmg.clockingInfo.count(port)) + clockInfoCount = int(tmg.clockingInfo.at(port).size()); + else + clockInfoCount = 0; + return get_or_default(tmg.portClasses, port, TMG_IGNORE); } TimingClockingInfo Arch::getPortClockingInfo(const CellInfo *cell, IdString port, int index) const { - NPNR_ASSERT_FALSE("no clocking info for generic"); + NPNR_ASSERT(cellTiming.count(cell->name)); + const auto &tmg = cellTiming.at(cell->name); + NPNR_ASSERT(tmg.clockingInfo.count(port)); + return tmg.clockingInfo.at(port).at(index); +} + +bool Arch::isValidBelForCell(CellInfo *cell, BelId bel) const +{ + std::vector<const CellInfo *> cells; + cells.push_back(cell); + Loc loc = getBelLocation(bel); + for (auto tbel : getBelsByTile(loc.x, loc.y)) { + if (tbel == bel) + continue; + CellInfo *bound = getBoundBelCell(tbel); + if (bound != nullptr) + cells.push_back(bound); + } + return cellsCompatible(cells.data(), int(cells.size())); +} + +bool Arch::isBelLocationValid(BelId bel) const +{ + std::vector<const CellInfo *> cells; + Loc loc = getBelLocation(bel); + for (auto tbel : getBelsByTile(loc.x, loc.y)) { + CellInfo *bound = getBoundBelCell(tbel); + if (bound != nullptr) + cells.push_back(bound); + } + return cellsCompatible(cells.data(), int(cells.size())); +} + +const std::string Arch::defaultPlacer = "sa"; +const std::vector<std::string> Arch::availablePlacers = {"sa"}; + +void Arch::assignArchInfo() +{ + for (auto &cell : getCtx()->cells) { + CellInfo *ci = cell.second.get(); + if (ci->type == id("GENERIC_SLICE")) { + ci->is_slice = true; + ci->slice_clk = get_net_or_empty(ci, id("CLK")); + } else { + ci->is_slice = false; + } + ci->user_group = int_or_default(ci->attrs, id("PACK_GROUP"), -1); + } } -bool Arch::isValidBelForCell(CellInfo *cell, BelId bel) const { return true; } -bool Arch::isBelLocationValid(BelId bel) const { return true; } +bool Arch::cellsCompatible(const CellInfo **cells, int count) const +{ + const NetInfo *clk = nullptr; + int group = -1; + for (int i = 0; i < count; i++) { + const CellInfo *ci = cells[i]; + if (ci->is_slice && ci->slice_clk != nullptr) { + if (clk == nullptr) + clk = ci->slice_clk; + else if (clk != ci->slice_clk) + return false; + } + if (ci->user_group != -1) { + if (group == -1) + group = ci->user_group; + else if (group != ci->user_group) + return false; + } + } + return true; +} NEXTPNR_NAMESPACE_END diff --git a/generic/arch.h b/generic/arch.h index dc4258cc..e9d3593c 100644 --- a/generic/arch.h +++ b/generic/arch.h @@ -25,6 +25,11 @@ NEXTPNR_NAMESPACE_BEGIN struct ArchArgs { + // Number of LUT inputs + int K = 4; + // y = mx + c relationship between distance and delay for interconnect + // delay estimates + double delayScale = 0.1, delayOffset = 0; }; struct WireInfo; @@ -81,6 +86,33 @@ struct GroupInfo DecalXY decalxy; }; +struct CellDelayKey +{ + IdString from, to; + inline bool operator==(const CellDelayKey &other) const { return from == other.from && to == other.to; } +}; + +NEXTPNR_NAMESPACE_END +namespace std { +template <> struct hash<NEXTPNR_NAMESPACE_PREFIX CellDelayKey> +{ + std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX CellDelayKey &dk) const noexcept + { + std::size_t seed = std::hash<NEXTPNR_NAMESPACE_PREFIX IdString>()(dk.from); + seed ^= std::hash<NEXTPNR_NAMESPACE_PREFIX IdString>()(dk.to) + 0x9e3779b9 + (seed << 6) + (seed >> 2); + return seed; + } +}; +} // namespace std +NEXTPNR_NAMESPACE_BEGIN + +struct CellTiming +{ + std::unordered_map<IdString, TimingPortClass> portClasses; + std::unordered_map<CellDelayKey, DelayInfo> combDelays; + std::unordered_map<IdString, std::vector<TimingClockingInfo>> clockingInfo; +}; + struct Arch : BaseCtx { std::string chipName; @@ -101,7 +133,7 @@ struct Arch : BaseCtx std::vector<std::vector<int>> tileBelDimZ; std::vector<std::vector<int>> tilePipDimZ; - float grid_distance_to_delay; + std::unordered_map<IdString, CellTiming> cellTiming; void addWire(IdString name, IdString type, int x, int y); void addPip(IdString name, IdString type, IdString srcWire, IdString dstWire, DelayInfo delay, Loc loc); @@ -127,6 +159,14 @@ struct Arch : BaseCtx void setPipAttr(IdString pip, IdString key, const std::string &value); void setBelAttr(IdString bel, IdString key, const std::string &value); + void setLutK(int K); + void setDelayScaling(double scale, double offset); + + void addCellTimingClock(IdString cell, IdString port); + void addCellTimingDelay(IdString cell, IdString fromPort, IdString toPort, DelayInfo delay); + void addCellTimingSetupHold(IdString cell, IdString port, IdString clock, DelayInfo setup, DelayInfo hold); + void addCellTimingClockToOut(IdString cell, IdString port, IdString clock, DelayInfo clktoq); + // --------------------------------------------------------------- // Common Arch API. Every arch must provide the following methods. @@ -208,8 +248,8 @@ struct Arch : BaseCtx delay_t estimateDelay(WireId src, WireId dst) const; delay_t predictDelay(const NetInfo *net_info, const PortRef &sink) const; - delay_t getDelayEpsilon() const { return 0.01; } - delay_t getRipupDelayPenalty() const { return 1.0; } + delay_t getDelayEpsilon() const { return 0.001; } + delay_t getRipupDelayPenalty() const { return 0.015; } float getDelayNS(delay_t v) const { return v; } DelayInfo getDelayFromNS(float ns) const @@ -222,7 +262,7 @@ struct Arch : BaseCtx uint32_t getDelayChecksum(delay_t v) const { return 0; } bool getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay_t &budget) const; - bool pack() { return true; } + bool pack(); bool place(); bool route(); @@ -240,6 +280,14 @@ struct Arch : BaseCtx bool isValidBelForCell(CellInfo *cell, BelId bel) const; bool isBelLocationValid(BelId bel) const; + + static const std::string defaultPlacer; + static const std::vector<std::string> availablePlacers; + + // --------------------------------------------------------------- + // Internal usage + void assignArchInfo(); + bool cellsCompatible(const CellInfo **cells, int count) const; }; NEXTPNR_NAMESPACE_END diff --git a/generic/arch_pybindings.cc b/generic/arch_pybindings.cc index 186b2c13..8526e409 100644 --- a/generic/arch_pybindings.cc +++ b/generic/arch_pybindings.cc @@ -23,18 +23,215 @@ #include "arch_pybindings.h" #include "nextpnr.h" #include "pybindings.h" +#include "pywrappers.h" NEXTPNR_NAMESPACE_BEGIN +namespace PythonConversion { +template <> struct string_converter<const IdString &> +{ + const IdString &from_str(Context *ctx, std::string name) { NPNR_ASSERT_FALSE("unsupported"); } + + std::string to_str(Context *ctx, const IdString &id) { return id.str(ctx); } +}; +} // namespace PythonConversion void arch_wrap_python() { using namespace PythonConversion; + auto arch_cls = class_<Arch, Arch *, bases<BaseCtx>, boost::noncopyable>("Arch", init<ArchArgs>()); + + auto dxy_cls = class_<ContextualWrapper<DecalXY>>("DecalXY_", no_init); + readwrite_wrapper<DecalXY, decltype(&DecalXY::decal), &DecalXY::decal, conv_to_str<DecalId>, + conv_from_str<DecalId>>::def_wrap(dxy_cls, "decal"); + readwrite_wrapper<DecalXY, decltype(&DecalXY::x), &DecalXY::x, pass_through<float>, pass_through<float>>::def_wrap( + dxy_cls, "x"); + readwrite_wrapper<DecalXY, decltype(&DecalXY::y), &DecalXY::y, pass_through<float>, pass_through<float>>::def_wrap( + dxy_cls, "y"); + auto ctx_cls = class_<Context, Context *, bases<Arch>, boost::noncopyable>("Context", no_init) .def("checksum", &Context::checksum) .def("pack", &Context::pack) .def("place", &Context::place) .def("route", &Context::route); + + class_<BelPin>("BelPin").def_readwrite("bel", &BelPin::bel).def_readwrite("pin", &BelPin::pin); + + class_<DelayInfo>("DelayInfo").def("maxDelay", &DelayInfo::maxDelay).def("minDelay", &DelayInfo::minDelay); + + fn_wrapper_1a<Context, decltype(&Context::getBelType), &Context::getBelType, conv_to_str<IdString>, + conv_from_str<BelId>>::def_wrap(ctx_cls, "getBelType"); + fn_wrapper_1a<Context, decltype(&Context::checkBelAvail), &Context::checkBelAvail, pass_through<bool>, + conv_from_str<BelId>>::def_wrap(ctx_cls, "checkBelAvail"); + fn_wrapper_1a<Context, decltype(&Context::getBelChecksum), &Context::getBelChecksum, pass_through<uint32_t>, + conv_from_str<BelId>>::def_wrap(ctx_cls, "getBelChecksum"); + fn_wrapper_3a_v<Context, decltype(&Context::bindBel), &Context::bindBel, conv_from_str<BelId>, + addr_and_unwrap<CellInfo>, pass_through<PlaceStrength>>::def_wrap(ctx_cls, "bindBel"); + fn_wrapper_1a_v<Context, decltype(&Context::unbindBel), &Context::unbindBel, conv_from_str<BelId>>::def_wrap( + ctx_cls, "unbindBel"); + fn_wrapper_1a<Context, decltype(&Context::getBoundBelCell), &Context::getBoundBelCell, deref_and_wrap<CellInfo>, + conv_from_str<BelId>>::def_wrap(ctx_cls, "getBoundBelCell"); + fn_wrapper_1a<Context, decltype(&Context::getConflictingBelCell), &Context::getConflictingBelCell, + deref_and_wrap<CellInfo>, conv_from_str<BelId>>::def_wrap(ctx_cls, "getConflictingBelCell"); + fn_wrapper_0a<Context, decltype(&Context::getBels), &Context::getBels, + wrap_context<const std::vector<BelId> &>>::def_wrap(ctx_cls, "getBels"); + + fn_wrapper_2a<Context, decltype(&Context::getBelPinWire), &Context::getBelPinWire, conv_to_str<WireId>, + conv_from_str<BelId>, conv_from_str<IdString>>::def_wrap(ctx_cls, "getBelPinWire"); + fn_wrapper_1a<Context, decltype(&Context::getWireBelPins), &Context::getWireBelPins, + wrap_context<const std::vector<BelPin> &>, conv_from_str<WireId>>::def_wrap(ctx_cls, + "getWireBelPins"); + + fn_wrapper_1a<Context, decltype(&Context::getWireChecksum), &Context::getWireChecksum, pass_through<uint32_t>, + conv_from_str<WireId>>::def_wrap(ctx_cls, "getWireChecksum"); + fn_wrapper_3a_v<Context, decltype(&Context::bindWire), &Context::bindWire, conv_from_str<WireId>, + addr_and_unwrap<NetInfo>, pass_through<PlaceStrength>>::def_wrap(ctx_cls, "bindWire"); + fn_wrapper_1a_v<Context, decltype(&Context::unbindWire), &Context::unbindWire, conv_from_str<WireId>>::def_wrap( + ctx_cls, "unbindWire"); + fn_wrapper_1a<Context, decltype(&Context::checkWireAvail), &Context::checkWireAvail, pass_through<bool>, + conv_from_str<WireId>>::def_wrap(ctx_cls, "checkWireAvail"); + fn_wrapper_1a<Context, decltype(&Context::getBoundWireNet), &Context::getBoundWireNet, deref_and_wrap<NetInfo>, + conv_from_str<WireId>>::def_wrap(ctx_cls, "getBoundWireNet"); + fn_wrapper_1a<Context, decltype(&Context::getConflictingWireNet), &Context::getConflictingWireNet, + deref_and_wrap<NetInfo>, conv_from_str<WireId>>::def_wrap(ctx_cls, "getConflictingWireNet"); + + fn_wrapper_0a<Context, decltype(&Context::getWires), &Context::getWires, + wrap_context<const std::vector<WireId> &>>::def_wrap(ctx_cls, "getWires"); + + fn_wrapper_0a<Context, decltype(&Context::getPips), &Context::getPips, + wrap_context<const std::vector<PipId> &>>::def_wrap(ctx_cls, "getPips"); + fn_wrapper_1a<Context, decltype(&Context::getPipChecksum), &Context::getPipChecksum, pass_through<uint32_t>, + conv_from_str<PipId>>::def_wrap(ctx_cls, "getPipChecksum"); + fn_wrapper_3a_v<Context, decltype(&Context::bindPip), &Context::bindPip, conv_from_str<PipId>, + addr_and_unwrap<NetInfo>, pass_through<PlaceStrength>>::def_wrap(ctx_cls, "bindPip"); + fn_wrapper_1a_v<Context, decltype(&Context::unbindPip), &Context::unbindPip, conv_from_str<PipId>>::def_wrap( + ctx_cls, "unbindPip"); + fn_wrapper_1a<Context, decltype(&Context::checkPipAvail), &Context::checkPipAvail, pass_through<bool>, + conv_from_str<PipId>>::def_wrap(ctx_cls, "checkPipAvail"); + fn_wrapper_1a<Context, decltype(&Context::getBoundPipNet), &Context::getBoundPipNet, deref_and_wrap<NetInfo>, + conv_from_str<PipId>>::def_wrap(ctx_cls, "getBoundPipNet"); + fn_wrapper_1a<Context, decltype(&Context::getConflictingPipNet), &Context::getConflictingPipNet, + deref_and_wrap<NetInfo>, conv_from_str<PipId>>::def_wrap(ctx_cls, "getConflictingPipNet"); + + fn_wrapper_1a<Context, decltype(&Context::getPipsDownhill), &Context::getPipsDownhill, + wrap_context<const std::vector<PipId> &>, conv_from_str<WireId>>::def_wrap(ctx_cls, + "getPipsDownhill"); + fn_wrapper_1a<Context, decltype(&Context::getPipsUphill), &Context::getPipsUphill, + wrap_context<const std::vector<PipId> &>, conv_from_str<WireId>>::def_wrap(ctx_cls, "getPipsUphill"); + fn_wrapper_1a<Context, decltype(&Context::getWireAliases), &Context::getWireAliases, + wrap_context<const std::vector<PipId> &>, conv_from_str<WireId>>::def_wrap(ctx_cls, "getWireAliases"); + + fn_wrapper_1a<Context, decltype(&Context::getPipSrcWire), &Context::getPipSrcWire, conv_to_str<WireId>, + conv_from_str<PipId>>::def_wrap(ctx_cls, "getPipSrcWire"); + fn_wrapper_1a<Context, decltype(&Context::getPipDstWire), &Context::getPipDstWire, conv_to_str<WireId>, + conv_from_str<PipId>>::def_wrap(ctx_cls, "getPipDstWire"); + fn_wrapper_1a<Context, decltype(&Context::getPipDelay), &Context::getPipDelay, pass_through<DelayInfo>, + conv_from_str<PipId>>::def_wrap(ctx_cls, "getPipDelay"); + + fn_wrapper_1a<Context, decltype(&Context::getDelayFromNS), &Context::getDelayFromNS, pass_through<DelayInfo>, + pass_through<double>>::def_wrap(ctx_cls, "getDelayFromNS"); + + fn_wrapper_0a<Context, decltype(&Context::getChipName), &Context::getChipName, pass_through<std::string>>::def_wrap( + ctx_cls, "getChipName"); + fn_wrapper_0a<Context, decltype(&Context::archId), &Context::archId, conv_to_str<IdString>>::def_wrap(ctx_cls, + "archId"); + + fn_wrapper_3a<Context, decltype(&Context::constructDecalXY), &Context::constructDecalXY, wrap_context<DecalXY>, + conv_from_str<DecalId>, pass_through<float>, pass_through<float>>::def_wrap(ctx_cls, "DecalXY"); + + typedef std::unordered_map<IdString, std::unique_ptr<CellInfo>> CellMap; + typedef std::unordered_map<IdString, std::unique_ptr<NetInfo>> NetMap; + + readonly_wrapper<Context, decltype(&Context::cells), &Context::cells, wrap_context<CellMap &>>::def_wrap(ctx_cls, + "cells"); + readonly_wrapper<Context, decltype(&Context::nets), &Context::nets, wrap_context<NetMap &>>::def_wrap(ctx_cls, + "nets"); + + fn_wrapper_2a_v<Context, decltype(&Context::addClock), &Context::addClock, conv_from_str<IdString>, + pass_through<float>>::def_wrap(ctx_cls, "addClock"); + + // Generic arch construction API + fn_wrapper_4a_v<Context, decltype(&Context::addWire), &Context::addWire, conv_from_str<IdString>, + conv_from_str<IdString>, pass_through<int>, pass_through<int>>::def_wrap(ctx_cls, "addWire", + (arg("name"), "type", "x", + "y")); + fn_wrapper_6a_v<Context, decltype(&Context::addPip), &Context::addPip, conv_from_str<IdString>, + conv_from_str<IdString>, conv_from_str<IdString>, conv_from_str<IdString>, pass_through<DelayInfo>, + pass_through<Loc>>::def_wrap(ctx_cls, "addPip", + (arg("name"), "type", "srcWire", "dstWire", "delay", "loc")); + fn_wrapper_5a_v<Context, decltype(&Context::addAlias), &Context::addAlias, conv_from_str<IdString>, + conv_from_str<IdString>, conv_from_str<IdString>, conv_from_str<IdString>, + pass_through<DelayInfo>>::def_wrap(ctx_cls, "addAlias", + (arg("name"), "type", "srcWire", "dstWire", "delay")); + + fn_wrapper_4a_v<Context, decltype(&Context::addBel), &Context::addBel, conv_from_str<IdString>, + conv_from_str<IdString>, pass_through<Loc>, pass_through<bool>>::def_wrap(ctx_cls, "addBel", + (arg("name"), "type", + "loc", "gb")); + fn_wrapper_3a_v<Context, decltype(&Context::addBelInput), &Context::addBelInput, conv_from_str<IdString>, + conv_from_str<IdString>, conv_from_str<IdString>>::def_wrap(ctx_cls, "addBelInput", + (arg("bel"), "name", "wire")); + fn_wrapper_3a_v<Context, decltype(&Context::addBelOutput), &Context::addBelOutput, conv_from_str<IdString>, + conv_from_str<IdString>, conv_from_str<IdString>>::def_wrap(ctx_cls, "addBelOutput", + (arg("bel"), "name", "wire")); + fn_wrapper_3a_v<Context, decltype(&Context::addBelInout), &Context::addBelInout, conv_from_str<IdString>, + conv_from_str<IdString>, conv_from_str<IdString>>::def_wrap(ctx_cls, "addBelInout", + (arg("bel"), "name", "wire")); + + fn_wrapper_2a_v<Context, decltype(&Context::addGroupBel), &Context::addGroupBel, conv_from_str<IdString>, + conv_from_str<IdString>>::def_wrap(ctx_cls, "addGroupBel", (arg("group"), "bel")); + fn_wrapper_2a_v<Context, decltype(&Context::addGroupWire), &Context::addGroupWire, conv_from_str<IdString>, + conv_from_str<IdString>>::def_wrap(ctx_cls, "addGroupWire", (arg("group"), "wire")); + fn_wrapper_2a_v<Context, decltype(&Context::addGroupPip), &Context::addGroupPip, conv_from_str<IdString>, + conv_from_str<IdString>>::def_wrap(ctx_cls, "addGroupPip", (arg("group"), "pip")); + fn_wrapper_2a_v<Context, decltype(&Context::addGroupGroup), &Context::addGroupPip, conv_from_str<IdString>, + conv_from_str<IdString>>::def_wrap(ctx_cls, "addGroupGroup", (arg("group"), "grp")); + + fn_wrapper_2a_v<Context, decltype(&Context::addDecalGraphic), &Context::addDecalGraphic, conv_from_str<DecalId>, + pass_through<GraphicElement>>::def_wrap(ctx_cls, "addDecalGraphic", (arg("decal"), "graphic")); + fn_wrapper_2a_v<Context, decltype(&Context::setWireDecal), &Context::setWireDecal, conv_from_str<DecalId>, + unwrap_context<DecalXY>>::def_wrap(ctx_cls, "setWireDecal", (arg("wire"), "decalxy")); + fn_wrapper_2a_v<Context, decltype(&Context::setPipDecal), &Context::setPipDecal, conv_from_str<DecalId>, + unwrap_context<DecalXY>>::def_wrap(ctx_cls, "setPipDecal", (arg("pip"), "decalxy")); + fn_wrapper_2a_v<Context, decltype(&Context::setBelDecal), &Context::setBelDecal, conv_from_str<DecalId>, + unwrap_context<DecalXY>>::def_wrap(ctx_cls, "setBelDecal", (arg("bel"), "decalxy")); + fn_wrapper_2a_v<Context, decltype(&Context::setGroupDecal), &Context::setGroupDecal, conv_from_str<DecalId>, + unwrap_context<DecalXY>>::def_wrap(ctx_cls, "setGroupDecal", (arg("group"), "decalxy")); + + fn_wrapper_3a_v<Context, decltype(&Context::setWireAttr), &Context::setWireAttr, conv_from_str<DecalId>, + conv_from_str<IdString>, pass_through<std::string>>::def_wrap(ctx_cls, "setWireAttr", + (arg("wire"), "key", "value")); + fn_wrapper_3a_v<Context, decltype(&Context::setBelAttr), &Context::setBelAttr, conv_from_str<DecalId>, + conv_from_str<IdString>, pass_through<std::string>>::def_wrap(ctx_cls, "setBelAttr", + (arg("bel"), "key", "value")); + fn_wrapper_3a_v<Context, decltype(&Context::setPipAttr), &Context::setPipAttr, conv_from_str<DecalId>, + conv_from_str<IdString>, pass_through<std::string>>::def_wrap(ctx_cls, "setPipAttr", + (arg("pip"), "key", "value")); + + fn_wrapper_1a_v<Context, decltype(&Context::setLutK), &Context::setLutK, pass_through<int>>::def_wrap( + ctx_cls, "setLutK", arg("K")); + fn_wrapper_2a_v<Context, decltype(&Context::setDelayScaling), &Context::setDelayScaling, pass_through<double>, + pass_through<double>>::def_wrap(ctx_cls, "setDelayScaling", (arg("scale"), "offset")); + + fn_wrapper_2a_v<Context, decltype(&Context::addCellTimingClock), &Context::addCellTimingClock, + conv_from_str<IdString>, conv_from_str<IdString>>::def_wrap(ctx_cls, "addCellTimingClock", + (arg("cell"), "port")); + fn_wrapper_4a_v<Context, decltype(&Context::addCellTimingDelay), &Context::addCellTimingDelay, + conv_from_str<IdString>, conv_from_str<IdString>, conv_from_str<IdString>, + pass_through<DelayInfo>>::def_wrap(ctx_cls, "addCellTimingDelay", + (arg("cell"), "fromPort", "toPort", "delay")); + fn_wrapper_5a_v<Context, decltype(&Context::addCellTimingSetupHold), &Context::addCellTimingSetupHold, + conv_from_str<IdString>, conv_from_str<IdString>, conv_from_str<IdString>, pass_through<DelayInfo>, + pass_through<DelayInfo>>::def_wrap(ctx_cls, "addCellTimingSetupHold", + (arg("cell"), "port", "clock", "setup", "hold")); + fn_wrapper_4a_v<Context, decltype(&Context::addCellTimingClockToOut), &Context::addCellTimingClockToOut, + conv_from_str<IdString>, conv_from_str<IdString>, conv_from_str<IdString>, + pass_through<DelayInfo>>::def_wrap(ctx_cls, "addCellTimingClockToOut", + (arg("cell"), "port", "clock", "clktoq")); + + WRAP_MAP_UPTR(CellMap, "IdCellMap"); + WRAP_MAP_UPTR(NetMap, "IdNetMap"); + WRAP_VECTOR(const std::vector<IdString>, conv_to_str<IdString>); } NEXTPNR_NAMESPACE_END diff --git a/generic/archdefs.h b/generic/archdefs.h index 2452aa17..978c9c9b 100644 --- a/generic/archdefs.h +++ b/generic/archdefs.h @@ -55,8 +55,18 @@ typedef IdString DecalId; struct ArchNetInfo { }; + +struct NetInfo; + struct ArchCellInfo { + // Custom grouping set via "PACK_GROUP" attribute. All cells with the same group + // value may share a tile (-1 = don't care, default if not set) + int user_group; + // Is a slice type primitive + bool is_slice; + // Only packing rule for slice type primitives is a single clock per tile + const NetInfo *slice_clk; }; NEXTPNR_NAMESPACE_END diff --git a/generic/cells.cc b/generic/cells.cc new file mode 100644 index 00000000..14b368b2 --- /dev/null +++ b/generic/cells.cc @@ -0,0 +1,139 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2019 David Shah <david@symbioticeda.com> + * + * 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 "cells.h" +#include "design_utils.h" +#include "log.h" +#include "util.h" + +NEXTPNR_NAMESPACE_BEGIN + +void add_port(const Context *ctx, CellInfo *cell, std::string name, PortType dir) +{ + IdString id = ctx->id(name); + NPNR_ASSERT(cell->ports.count(id) == 0); + cell->ports[id] = PortInfo{id, nullptr, dir}; +} + +std::unique_ptr<CellInfo> create_generic_cell(Context *ctx, IdString type, std::string name) +{ + static int auto_idx = 0; + std::unique_ptr<CellInfo> new_cell = std::unique_ptr<CellInfo>(new CellInfo()); + if (name.empty()) { + new_cell->name = ctx->id("$nextpnr_" + type.str(ctx) + "_" + std::to_string(auto_idx++)); + } else { + new_cell->name = ctx->id(name); + } + new_cell->type = type; + if (type == ctx->id("GENERIC_SLICE")) { + new_cell->params[ctx->id("K")] = std::to_string(ctx->args.K); + new_cell->params[ctx->id("INIT")] = "0"; + new_cell->params[ctx->id("FF_USED")] = "0"; + + for (int i = 0; i < ctx->args.K; i++) + add_port(ctx, new_cell.get(), "I[" + std::to_string(i) + "]", PORT_IN); + + add_port(ctx, new_cell.get(), "CLK", PORT_IN); + + add_port(ctx, new_cell.get(), "Q", PORT_OUT); + } else if (type == ctx->id("GENERIC_IOB")) { + new_cell->params[ctx->id("INPUT_USED")] = "0"; + new_cell->params[ctx->id("OUTPUT_USED")] = "0"; + new_cell->params[ctx->id("ENABLE_USED")] = "0"; + + add_port(ctx, new_cell.get(), "PAD", PORT_INOUT); + add_port(ctx, new_cell.get(), "I", PORT_IN); + add_port(ctx, new_cell.get(), "EN", PORT_IN); + add_port(ctx, new_cell.get(), "O", PORT_OUT); + } else { + log_error("unable to create generic cell of type %s", type.c_str(ctx)); + } + return new_cell; +} + +void lut_to_lc(const Context *ctx, CellInfo *lut, CellInfo *lc, bool no_dff) +{ + lc->params[ctx->id("INIT")] = lut->params[ctx->id("INIT")]; + + int lut_k = int_or_default(lut->params, ctx->id("K"), 4); + NPNR_ASSERT(lut_k <= ctx->args.K); + + for (int i = 0; i < lut_k; i++) { + IdString port = ctx->id("I[" + std::to_string(i) + "]"); + replace_port(lut, port, lc, port); + } + + if (no_dff) { + replace_port(lut, ctx->id("Q"), lc, ctx->id("Q")); + lc->params[ctx->id("FF_USED")] = "0"; + } +} + +void dff_to_lc(const Context *ctx, CellInfo *dff, CellInfo *lc, bool pass_thru_lut) +{ + lc->params[ctx->id("FF_USED")] = "1"; + replace_port(dff, ctx->id("CLK"), lc, ctx->id("CLK")); + + if (pass_thru_lut) { + lc->params[ctx->id("INIT")] = "2"; + replace_port(dff, ctx->id("D"), lc, ctx->id("I[0]")); + } + + replace_port(dff, ctx->id("Q"), lc, ctx->id("Q")); +} + +void nxio_to_iob(Context *ctx, CellInfo *nxio, CellInfo *iob, std::unordered_set<IdString> &todelete_cells) +{ + if (nxio->type == ctx->id("$nextpnr_ibuf")) { + iob->params[ctx->id("INPUT_USED")] = "1"; + replace_port(nxio, ctx->id("O"), iob, ctx->id("O")); + } else if (nxio->type == ctx->id("$nextpnr_obuf")) { + iob->params[ctx->id("OUTPUT_USED")] = "1"; + replace_port(nxio, ctx->id("I"), iob, ctx->id("I")); + } else if (nxio->type == ctx->id("$nextpnr_iobuf")) { + // N.B. tristate will be dealt with below + iob->params[ctx->id("INPUT_USED")] = "1"; + iob->params[ctx->id("OUTPUT_USED")] = "1"; + replace_port(nxio, ctx->id("I"), iob, ctx->id("I")); + replace_port(nxio, ctx->id("O"), iob, ctx->id("O")); + } else { + NPNR_ASSERT(false); + } + NetInfo *donet = iob->ports.at(ctx->id("I")).net; + CellInfo *tbuf = net_driven_by( + ctx, donet, [](const Context *ctx, const CellInfo *cell) { return cell->type == ctx->id("$_TBUF_"); }, + ctx->id("Y")); + if (tbuf) { + iob->params[ctx->id("ENABLE_USED")] = "1"; + replace_port(tbuf, ctx->id("A"), iob, ctx->id("I")); + replace_port(tbuf, ctx->id("E"), iob, ctx->id("EN")); + + if (donet->users.size() > 1) { + for (auto user : donet->users) + log_info(" remaining tristate user: %s.%s\n", user.cell->name.c_str(ctx), user.port.c_str(ctx)); + log_error("unsupported tristate IO pattern for IO buffer '%s', " + "instantiate GENERIC_IOB manually to ensure correct behaviour\n", + nxio->name.c_str(ctx)); + } + ctx->nets.erase(donet->name); + todelete_cells.insert(tbuf->name); + } +} + +NEXTPNR_NAMESPACE_END diff --git a/generic/cells.h b/generic/cells.h new file mode 100644 index 00000000..646d738d --- /dev/null +++ b/generic/cells.h @@ -0,0 +1,55 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2019 David Shah <david@symbioticeda.com> + * + * 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 "nextpnr.h" + +#ifndef GENERIC_CELLS_H +#define GENERIC_CELLS_H + +NEXTPNR_NAMESPACE_BEGIN + +// Create a generic arch cell and return it +// Name will be automatically assigned if not specified +std::unique_ptr<CellInfo> create_generic_cell(Context *ctx, IdString type, std::string name = ""); + +// Return true if a cell is a LUT +inline bool is_lut(const BaseCtx *ctx, const CellInfo *cell) { return cell->type == ctx->id("LUT"); } + +// Return true if a cell is a flipflop +inline bool is_ff(const BaseCtx *ctx, const CellInfo *cell) { return cell->type == ctx->id("DFF"); } + +inline bool is_lc(const BaseCtx *ctx, const CellInfo *cell) { return cell->type == ctx->id("GENERIC_SLICE"); } + +// Convert a LUT primitive to (part of) an GENERIC_SLICE, swapping ports +// as needed. Set no_dff if a DFF is not being used, so that the output +// can be reconnected +void lut_to_lc(const Context *ctx, CellInfo *lut, CellInfo *lc, bool no_dff = true); + +// Convert a DFF primitive to (part of) an GENERIC_SLICE, setting parameters +// and reconnecting signals as necessary. If pass_thru_lut is True, the LUT will +// be configured as pass through and D connected to I0, otherwise D will be +// ignored +void dff_to_lc(const Context *ctx, CellInfo *dff, CellInfo *lc, bool pass_thru_lut = false); + +// Convert a nextpnr IO buffer to a GENERIC_IOB +void nxio_to_iob(Context *ctx, CellInfo *nxio, CellInfo *sbio, std::unordered_set<IdString> &todelete_cells); + +NEXTPNR_NAMESPACE_END + +#endif diff --git a/generic/examples/.gitignore b/generic/examples/.gitignore new file mode 100644 index 00000000..38e95de5 --- /dev/null +++ b/generic/examples/.gitignore @@ -0,0 +1,3 @@ +blinky.fasm +__pycache__ +*.pyc diff --git a/generic/examples/README.md b/generic/examples/README.md new file mode 100644 index 00000000..9fd106d9 --- /dev/null +++ b/generic/examples/README.md @@ -0,0 +1,14 @@ +# Generic Architecture Example + +This contains a simple, artificial, example of the nextpnr generic API. + + - simple.py procedurally generates a simple FPGA architecture with IO at the edges, + logic slices in all other tiles, and interconnect only between adjacent tiles + + - simple_timing.py annotates cells with timing data (this is a separate script that must be run after packing) + + - write_fasm.py uses the nextpnr Python API to write a FASM file for a design + + - bitstream.py uses write_fasm.py to create a FASM ("FPGA assembly") file for the place-and-routed design + + - Run simple.sh to build an example design on the FPGA above
\ No newline at end of file diff --git a/generic/examples/__init__.py b/generic/examples/__init__.py new file mode 100644 index 00000000..e69de29b --- /dev/null +++ b/generic/examples/__init__.py diff --git a/generic/examples/bitstream.py b/generic/examples/bitstream.py new file mode 100644 index 00000000..1ab94f0c --- /dev/null +++ b/generic/examples/bitstream.py @@ -0,0 +1,17 @@ +from write_fasm import * +from simple_config import K + +# Need to tell FASM generator how to write parameters +# (celltype, parameter) -> ParameterConfig +param_map = { + ("GENERIC_SLICE", "K"): ParameterConfig(write=False), + ("GENERIC_SLICE", "INIT"): ParameterConfig(write=True, numeric=True, width=2**K), + ("GENERIC_SLICE", "FF_USED"): ParameterConfig(write=True, numeric=True, width=1), + + ("GENERIC_IOB", "INPUT_USED"): ParameterConfig(write=True, numeric=True, width=1), + ("GENERIC_IOB", "OUTPUT_USED"): ParameterConfig(write=True, numeric=True, width=1), + ("GENERIC_IOB", "ENABLE_USED"): ParameterConfig(write=True, numeric=True, width=1), +} + +with open("blinky.fasm", "w") as f: + write_fasm(ctx, param_map, f)
\ No newline at end of file diff --git a/generic/examples/blinky.v b/generic/examples/blinky.v new file mode 100644 index 00000000..b7cb1b86 --- /dev/null +++ b/generic/examples/blinky.v @@ -0,0 +1,9 @@ +module top(input clk, output reg [7:0] leds); + +reg [25:0] ctr; +always @(posedge clk) + ctr <= ctr + 1'b1; + +assign leds = ctr[25:18]; + +endmodule
\ No newline at end of file diff --git a/generic/examples/simple.py b/generic/examples/simple.py new file mode 100644 index 00000000..9339b68a --- /dev/null +++ b/generic/examples/simple.py @@ -0,0 +1,72 @@ +from simple_config import * + +def is_io(x, y): + return x == 0 or x == X-1 or y == 0 or y == Y-1 + +for x in range(X): + for y in range(Y): + # Bel port wires + for z in range(N): + ctx.addWire(name="X%dY%dZ%d_CLK" % (x, y, z), type="BEL_CLK", x=x, y=y) + ctx.addWire(name="X%dY%dZ%d_Q" % (x, y, z), type="BEL_Q", x=x, y=y) + for i in range(K): + ctx.addWire(name="X%dY%dZ%d_I%d" % (x, y, z, i), type="BEL_I", x=x, y=y) + # Local wires + for l in range(Wl): + ctx.addWire(name="X%dY%d_LOCAL%d" % (x, y, l), type="LOCAL", x=x, y=y) + # Create bels + if is_io(x, y): + if x == y: + continue + for z in range(2): + ctx.addBel(name="X%dY%d_IO%d" % (x, y, z), type="GENERIC_IOB", loc=Loc(x, y, z), gb=False) + ctx.addBelInput(bel="X%dY%d_IO%d" % (x, y, z), name="I", wire="X%dY%dZ%d_I0" % (x, y, z)) + ctx.addBelInput(bel="X%dY%d_IO%d" % (x, y, z), name="EN", wire="X%dY%dZ%d_I1" % (x, y, z)) + ctx.addBelOutput(bel="X%dY%d_IO%d" % (x, y, z), name="O", wire="X%dY%dZ%d_Q" % (x, y, z)) + else: + for z in range(N): + ctx.addBel(name="X%dY%d_SLICE%d" % (x, y, z), type="GENERIC_SLICE", loc=Loc(x, y, z), gb=False) + ctx.addBelInput(bel="X%dY%d_SLICE%d" % (x, y, z), name="CLK", wire="X%dY%dZ%d_CLK" % (x, y, z)) + for k in range(K): + ctx.addBelInput(bel="X%dY%d_SLICE%d" % (x, y, z), name="I[%d]" % k, wire="X%dY%dZ%d_I%d" % (x, y, z, k)) + ctx.addBelOutput(bel="X%dY%d_SLICE%d" % (x, y, z), name="Q", wire="X%dY%dZ%d_Q" % (x, y, z)) + +for x in range(X): + for y in range(Y): + # Pips driving bel input wires + # Bel input wires are driven by every Si'th local with an offset + def create_input_pips(dst, offset, skip): + for i in range(offset % skip, Wl, skip): + src = "X%dY%d_LOCAL%d" % (x, y, i) + ctx.addPip(name="X%dY%d.%s.%s" % (x, y, src, dst), type="BEL_INPUT", + srcWire=src, dstWire=dst, delay=ctx.getDelayFromNS(0.05), loc=Loc(x, y, 0)) + for z in range(N): + create_input_pips("X%dY%dZ%d_CLK" % (x, y, z), 0, Si) + for k in range(K): + create_input_pips("X%dY%dZ%d_I%d" % (x, y, z, k), k % Si, Si) + + # Pips from bel outputs to locals + def create_output_pips(dst, offset, skip): + for i in range(offset % skip, N, skip): + src = "X%dY%dZ%d_Q" % (x, y, i) + ctx.addPip(name="X%dY%d.%s.%s" % (x, y, src, dst), type="BEL_OUTPUT", + srcWire=src, dstWire=dst, delay=ctx.getDelayFromNS(0.05), loc=Loc(x, y, 0)) + # Pips from neighbour locals to locals + def create_neighbour_pips(dst, nx, ny, offset, skip): + if nx < 0 or nx >= X or ny < 0 or ny >= Y: + return + for i in range(offset % skip, Wl, skip): + src = "X%dY%d_LOCAL%d" % (nx, ny, i) + ctx.addPip(name="X%dY%d.%s.%s" % (x, y, src, dst), type="NEIGHBOUR", + srcWire=src, dstWire=dst, delay=ctx.getDelayFromNS(0.05), loc=Loc(x, y, 0)) + for l in range(Wl): + dst = "X%dY%d_LOCAL%d" % (x, y, l) + create_output_pips(dst, l % Sq, Sq) + create_neighbour_pips(dst, x-1, y-1, (l + 1) % Sl, Sl) + create_neighbour_pips(dst, x-1, y, (l + 2) % Sl, Sl) + create_neighbour_pips(dst, x-1, y+1, (l + 2) % Sl, Sl) + create_neighbour_pips(dst, x, y-1, (l + 3) % Sl, Sl) + create_neighbour_pips(dst, x, y+1, (l + 4) % Sl, Sl) + create_neighbour_pips(dst, x+1, y-1, (l + 5) % Sl, Sl) + create_neighbour_pips(dst, x+1, y, (l + 6) % Sl, Sl) + create_neighbour_pips(dst, x+1, y+1, (l + 7) % Sl, Sl)
\ No newline at end of file diff --git a/generic/examples/simple.sh b/generic/examples/simple.sh new file mode 100755 index 00000000..8ae903f9 --- /dev/null +++ b/generic/examples/simple.sh @@ -0,0 +1,4 @@ +#!/usr/bin/env bash +set -ex +yosys -p "tcl ../synth/synth_generic.tcl 4 blinky.json" blinky.v +${NEXTPNR:-../../nextpnr-generic} --pre-pack simple.py --pre-place simple_timing.py --json blinky.json --post-route bitstream.py diff --git a/generic/examples/simple_config.py b/generic/examples/simple_config.py new file mode 100644 index 00000000..dfb38f1c --- /dev/null +++ b/generic/examples/simple_config.py @@ -0,0 +1,15 @@ +# Grid size including IOBs at edges +X = 12 +Y = 12 +# SLICEs per tile +N = 8 +# LUT input count +K = 4 +# Number of local wires +Wl = N*(K+1) + 8 +# 1/Fc for bel input wire pips +Si = 4 +# 1/Fc for Q to local wire pips +Sq = 4 +# ~1/Fc local to neighbour local wire pips +Sl = 8
\ No newline at end of file diff --git a/generic/examples/simple_timing.py b/generic/examples/simple_timing.py new file mode 100644 index 00000000..a955c8d7 --- /dev/null +++ b/generic/examples/simple_timing.py @@ -0,0 +1,15 @@ +for cname, cell in ctx.cells: + if cell.type != "GENERIC_SLICE": + continue + if cname in ("$PACKER_GND", "$PACKER_VCC"): + continue + K = int(cell.params["K"]) + if cell.params["FF_USED"] == "1": + ctx.addCellTimingClock(cell=cname, port="CLK") + for i in range(K): + ctx.addCellTimingSetupHold(cell=cname, port="I[%d]" % i, clock="CLK", + setup=ctx.getDelayFromNS(0.2), hold=ctx.getDelayFromNS(0)) + ctx.addCellTimingClockToOut(cell=cname, port="Q", clock="CLK", clktoq=ctx.getDelayFromNS(0.2)) + else: + for i in range(K): + ctx.addCellTimingDelay(cell=cname, fromPort="I[%d]" % i, toPort="Q", delay=ctx.getDelayFromNS(0.2))
\ No newline at end of file diff --git a/generic/examples/write_fasm.py b/generic/examples/write_fasm.py new file mode 100644 index 00000000..1f279b63 --- /dev/null +++ b/generic/examples/write_fasm.py @@ -0,0 +1,52 @@ +from collections import namedtuple + +""" + write: set to True to enable writing this parameter to FASM + + numeric: set to True to write this parameter as a bit array (width>1) or + single bit (width==1) named after the parameter. Otherwise this + parameter will be written as `name.value` + + width: width of numeric parameter (ignored for non-numeric parameters) + + alias: an alternative name for this parameter (parameter name used if alias + is None) +""" +ParameterConfig = namedtuple('ParameterConfig', 'write numeric width alias') + +# FIXME use defaults= once Python 3.7 is standard +ParameterConfig.__new__.__defaults__ = (False, True, 1, None) + + +""" +Write a design as FASM + + ctx: nextpnr context + paramCfg: map from (celltype, parametername) -> ParameterConfig describing how to write parameters + f: output file +""" +def write_fasm(ctx, paramCfg, f): + for nname, net in sorted(ctx.nets, key=lambda x: str(x[1].name)): + print("# Net %s" % nname, file=f) + for wire, pip in sorted(net.wires, key=lambda x: str(x[1])): + if pip.pip != "": + print("%s" % pip.pip, file=f) + print("", file=f) + for cname, cell in sorted(ctx.cells, key=lambda x: str(x[1].name)): + print("# Cell %s at %s" % (cname, cell.bel), file=f) + for param, val in sorted(cell.params, key=lambda x: str(x)): + cfg = paramCfg[(cell.type, param)] + if not cfg.write: + continue + fasm_name = cfg.alias if cfg.alias is not None else param + if cfg.numeric: + if cfg.width == 1: + if int(val) != 0: + print("%s.%s" % (cell.bel, fasm_name), file=f) + else: + # Parameters with width >32 are direct binary, otherwise denary + binval = val if cfg.width > 32 else "{:0{}b}".format(int(val), cfg.width) + print("%s.%s[%d:0] = %d'b%s" % (cell.bel, fasm_name, cfg.width-1, cfg.width, binval), file=f) + else: + print("%s.%s.%s" % (cell.bel, fasm_name, val), file=f) + print("", file=f)
\ No newline at end of file diff --git a/generic/main.cc b/generic/main.cc index 08b0b348..c203f35c 100644 --- a/generic/main.cc +++ b/generic/main.cc @@ -49,7 +49,7 @@ po::options_description GenericCommandHandler::getArchOptions() return specific; } -void GenericCommandHandler::customBitstream(Context *ctx) { log_error("Here is when bitstream gets created"); } +void GenericCommandHandler::customBitstream(Context *ctx) {} std::unique_ptr<Context> GenericCommandHandler::createContext() { diff --git a/generic/pack.cc b/generic/pack.cc new file mode 100644 index 00000000..26ae9182 --- /dev/null +++ b/generic/pack.cc @@ -0,0 +1,293 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2018-19 David Shah <david@symbioticeda.com> + * + * 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 <algorithm> +#include <iterator> +#include <unordered_set> +#include "cells.h" +#include "design_utils.h" +#include "log.h" +#include "util.h" + +NEXTPNR_NAMESPACE_BEGIN + +// Pack LUTs and LUT-FF pairs +static void pack_lut_lutffs(Context *ctx) +{ + log_info("Packing LUT-FFs..\n"); + + std::unordered_set<IdString> packed_cells; + std::vector<std::unique_ptr<CellInfo>> new_cells; + for (auto cell : sorted(ctx->cells)) { + CellInfo *ci = cell.second; + if (ctx->verbose) + log_info("cell '%s' is of type '%s'\n", ci->name.c_str(ctx), ci->type.c_str(ctx)); + if (is_lut(ctx, ci)) { + std::unique_ptr<CellInfo> packed = + create_generic_cell(ctx, ctx->id("GENERIC_SLICE"), ci->name.str(ctx) + "_LC"); + std::copy(ci->attrs.begin(), ci->attrs.end(), std::inserter(packed->attrs, packed->attrs.begin())); + packed_cells.insert(ci->name); + if (ctx->verbose) + log_info("packed cell %s into %s\n", ci->name.c_str(ctx), packed->name.c_str(ctx)); + // See if we can pack into a DFF + // TODO: LUT cascade + NetInfo *o = ci->ports.at(ctx->id("Q")).net; + CellInfo *dff = net_only_drives(ctx, o, is_ff, ctx->id("D"), true); + auto lut_bel = ci->attrs.find(ctx->id("BEL")); + bool packed_dff = false; + if (dff) { + if (ctx->verbose) + log_info("found attached dff %s\n", dff->name.c_str(ctx)); + auto dff_bel = dff->attrs.find(ctx->id("BEL")); + if (lut_bel != ci->attrs.end() && dff_bel != dff->attrs.end() && lut_bel->second != dff_bel->second) { + // Locations don't match, can't pack + } else { + lut_to_lc(ctx, ci, packed.get(), false); + dff_to_lc(ctx, dff, packed.get(), false); + ctx->nets.erase(o->name); + if (dff_bel != dff->attrs.end()) + packed->attrs[ctx->id("BEL")] = dff_bel->second; + packed_cells.insert(dff->name); + if (ctx->verbose) + log_info("packed cell %s into %s\n", dff->name.c_str(ctx), packed->name.c_str(ctx)); + packed_dff = true; + } + } + if (!packed_dff) { + lut_to_lc(ctx, ci, packed.get(), true); + } + new_cells.push_back(std::move(packed)); + } + } + for (auto pcell : packed_cells) { + ctx->cells.erase(pcell); + } + for (auto &ncell : new_cells) { + ctx->cells[ncell->name] = std::move(ncell); + } +} + +// Pack FFs not packed as LUTFFs +static void pack_nonlut_ffs(Context *ctx) +{ + log_info("Packing non-LUT FFs..\n"); + + std::unordered_set<IdString> packed_cells; + std::vector<std::unique_ptr<CellInfo>> new_cells; + + for (auto cell : sorted(ctx->cells)) { + CellInfo *ci = cell.second; + if (is_ff(ctx, ci)) { + std::unique_ptr<CellInfo> packed = + create_generic_cell(ctx, ctx->id("GENERIC_SLICE"), ci->name.str(ctx) + "_DFFLC"); + std::copy(ci->attrs.begin(), ci->attrs.end(), std::inserter(packed->attrs, packed->attrs.begin())); + if (ctx->verbose) + log_info("packed cell %s into %s\n", ci->name.c_str(ctx), packed->name.c_str(ctx)); + packed_cells.insert(ci->name); + dff_to_lc(ctx, ci, packed.get(), true); + new_cells.push_back(std::move(packed)); + } + } + for (auto pcell : packed_cells) { + ctx->cells.erase(pcell); + } + for (auto &ncell : new_cells) { + ctx->cells[ncell->name] = std::move(ncell); + } +} + +static bool net_is_constant(const Context *ctx, NetInfo *net, bool &value) +{ + if (net == nullptr) + return false; + if (net->name == ctx->id("$PACKER_GND_NET") || net->name == ctx->id("$PACKER_VCC_NET")) { + value = (net->name == ctx->id("$PACKER_VCC_NET")); + return true; + } else { + return false; + } +} + +// Merge a net into a constant net +static void set_net_constant(const Context *ctx, NetInfo *orig, NetInfo *constnet, bool constval) +{ + orig->driver.cell = nullptr; + for (auto user : orig->users) { + if (user.cell != nullptr) { + CellInfo *uc = user.cell; + if (ctx->verbose) + log_info("%s user %s\n", orig->name.c_str(ctx), uc->name.c_str(ctx)); + if ((is_lut(ctx, uc) || is_lc(ctx, uc)) && (user.port.str(ctx).at(0) == 'I') && !constval) { + uc->ports[user.port].net = nullptr; + } else { + uc->ports[user.port].net = constnet; + constnet->users.push_back(user); + } + } + } + orig->users.clear(); +} + +// Pack constants (simple implementation) +static void pack_constants(Context *ctx) +{ + log_info("Packing constants..\n"); + + std::unique_ptr<CellInfo> gnd_cell = create_generic_cell(ctx, ctx->id("GENERIC_SLICE"), "$PACKER_GND"); + gnd_cell->params[ctx->id("INIT")] = "0"; + std::unique_ptr<NetInfo> gnd_net = std::unique_ptr<NetInfo>(new NetInfo); + gnd_net->name = ctx->id("$PACKER_GND_NET"); + gnd_net->driver.cell = gnd_cell.get(); + gnd_net->driver.port = ctx->id("Q"); + gnd_cell->ports.at(ctx->id("Q")).net = gnd_net.get(); + + std::unique_ptr<CellInfo> vcc_cell = create_generic_cell(ctx, ctx->id("GENERIC_SLICE"), "$PACKER_VCC"); + vcc_cell->params[ctx->id("INIT")] = "1"; + std::unique_ptr<NetInfo> vcc_net = std::unique_ptr<NetInfo>(new NetInfo); + vcc_net->name = ctx->id("$PACKER_VCC_NET"); + vcc_net->driver.cell = vcc_cell.get(); + vcc_net->driver.port = ctx->id("Q"); + vcc_cell->ports.at(ctx->id("Q")).net = vcc_net.get(); + + std::vector<IdString> dead_nets; + + bool gnd_used = false; + + for (auto net : sorted(ctx->nets)) { + NetInfo *ni = net.second; + if (ni->driver.cell != nullptr && ni->driver.cell->type == ctx->id("GND")) { + IdString drv_cell = ni->driver.cell->name; + set_net_constant(ctx, ni, gnd_net.get(), false); + gnd_used = true; + dead_nets.push_back(net.first); + ctx->cells.erase(drv_cell); + } else if (ni->driver.cell != nullptr && ni->driver.cell->type == ctx->id("VCC")) { + IdString drv_cell = ni->driver.cell->name; + set_net_constant(ctx, ni, vcc_net.get(), true); + dead_nets.push_back(net.first); + ctx->cells.erase(drv_cell); + } + } + + if (gnd_used) { + ctx->cells[gnd_cell->name] = std::move(gnd_cell); + ctx->nets[gnd_net->name] = std::move(gnd_net); + } + // Vcc cell always inserted for now, as it may be needed during carry legalisation (TODO: trim later if actually + // never used?) + ctx->cells[vcc_cell->name] = std::move(vcc_cell); + ctx->nets[vcc_net->name] = std::move(vcc_net); + + for (auto dn : dead_nets) { + ctx->nets.erase(dn); + } +} + +static bool is_nextpnr_iob(Context *ctx, CellInfo *cell) +{ + return cell->type == ctx->id("$nextpnr_ibuf") || cell->type == ctx->id("$nextpnr_obuf") || + cell->type == ctx->id("$nextpnr_iobuf"); +} + +static bool is_generic_iob(const Context *ctx, const CellInfo *cell) { return cell->type == ctx->id("GENERIC_IOB"); } + +// Pack IO buffers +static void pack_io(Context *ctx) +{ + std::unordered_set<IdString> packed_cells; + std::unordered_set<IdString> delete_nets; + + std::vector<std::unique_ptr<CellInfo>> new_cells; + log_info("Packing IOs..\n"); + + for (auto cell : sorted(ctx->cells)) { + CellInfo *ci = cell.second; + if (is_nextpnr_iob(ctx, ci)) { + CellInfo *iob = nullptr; + if (ci->type == ctx->id("$nextpnr_ibuf") || ci->type == ctx->id("$nextpnr_iobuf")) { + iob = net_only_drives(ctx, ci->ports.at(ctx->id("O")).net, is_generic_iob, ctx->id("PAD"), true, ci); + + } else if (ci->type == ctx->id("$nextpnr_obuf")) { + NetInfo *net = ci->ports.at(ctx->id("I")).net; + iob = net_only_drives(ctx, net, is_generic_iob, ctx->id("PAD"), true, ci); + } + if (iob != nullptr) { + // Trivial case, GENERIC_IOB used. Just destroy the net and the + // iobuf + log_info("%s feeds GENERIC_IOB %s, removing %s %s.\n", ci->name.c_str(ctx), iob->name.c_str(ctx), + ci->type.c_str(ctx), ci->name.c_str(ctx)); + NetInfo *net = iob->ports.at(ctx->id("PAD")).net; + if (((ci->type == ctx->id("$nextpnr_ibuf") || ci->type == ctx->id("$nextpnr_iobuf")) && + net->users.size() > 1) || + (ci->type == ctx->id("$nextpnr_obuf") && (net->users.size() > 2 || net->driver.cell != nullptr))) + log_error("PAD of %s '%s' connected to more than a single top level IO.\n", iob->type.c_str(ctx), + iob->name.c_str(ctx)); + + if (net != nullptr) { + delete_nets.insert(net->name); + iob->ports.at(ctx->id("PAD")).net = nullptr; + } + if (ci->type == ctx->id("$nextpnr_iobuf")) { + NetInfo *net2 = ci->ports.at(ctx->id("I")).net; + if (net2 != nullptr) { + delete_nets.insert(net2->name); + } + } + } else { + // Create a GENERIC_IOB buffer + std::unique_ptr<CellInfo> ice_cell = + create_generic_cell(ctx, ctx->id("GENERIC_IOB"), ci->name.str(ctx) + "$iob"); + nxio_to_iob(ctx, ci, ice_cell.get(), packed_cells); + new_cells.push_back(std::move(ice_cell)); + iob = new_cells.back().get(); + } + packed_cells.insert(ci->name); + std::copy(ci->attrs.begin(), ci->attrs.end(), std::inserter(iob->attrs, iob->attrs.begin())); + } + } + for (auto pcell : packed_cells) { + ctx->cells.erase(pcell); + } + for (auto dnet : delete_nets) { + ctx->nets.erase(dnet); + } + for (auto &ncell : new_cells) { + ctx->cells[ncell->name] = std::move(ncell); + } +} + +// Main pack function +bool Arch::pack() +{ + Context *ctx = getCtx(); + try { + log_break(); + pack_constants(ctx); + pack_io(ctx); + pack_lut_lutffs(ctx); + pack_nonlut_ffs(ctx); + ctx->assignArchInfo(); + log_info("Checksum: 0x%08x\n", ctx->checksum()); + return true; + } catch (log_execution_error_exception) { + return false; + } +} + +NEXTPNR_NAMESPACE_END diff --git a/generic/synth/cells_map.v b/generic/synth/cells_map.v new file mode 100644 index 00000000..a6027534 --- /dev/null +++ b/generic/synth/cells_map.v @@ -0,0 +1,10 @@ +module \$lut (A, Y); + parameter WIDTH = 0; + parameter LUT = 0; + input [WIDTH-1:0] A; + output Y; + + LUT #(.K(`LUT_K), .INIT(LUT)) _TECHMAP_REPLACE_ (.I(A), .Q(Y)); +endmodule + +module \$_DFF_P_ (input D, C, output Q); DFF _TECHMAP_REPLACE_ (.D(D), .Q(Q), .CLK(C)); endmodule diff --git a/generic/synth/prims.v b/generic/synth/prims.v new file mode 100644 index 00000000..95fcfac7 --- /dev/null +++ b/generic/synth/prims.v @@ -0,0 +1,59 @@ +// LUT and DFF are combined to a GENERIC_SLICE + +module LUT #( + parameter K = 4, + parameter [2**K-1:0] INIT = 0, +) ( + input [K-1:0] I, + output Q +); + assign Q = INIT[I]; +endmodule + +module DFF ( + input CLK, D, + output reg Q +); + always @(posedge CLK) + Q <= D; +endmodule + +module GENERIC_SLICE #( + parameter K = 4, + parameter [2**K-1:0] INIT = 0, + parameter FF_USED = 1'b0 +) ( + input CLK, + input [K-1:0] I, + output Q +); + + wire lut_q; + LUT #(.K(K), .INIT(INIT)) lut_i(.I(I), .Q(lut_q)); + + generate if (FF_USED) + DFF dff_i(.CLK(CLK), .D(lut_q), .Q(Q)); + else + assign Q = lut_q; + endgenerate +endmodule + +module GENERIC_IOB #( + parameter INPUT_USED = 1'b0, + parameter OUTPUT_USED = 1'b0, + parameter ENABLE_USED = 1'b0 +) ( + inout PAD, + input I, EN, + output O +); + generate if (OUTPUT_USED && ENABLE_USED) + assign PAD = EN ? I : 1'bz; + else if (OUTPUT_USED) + assign PAD = I; + endgenerate + + generate if (INPUT_USED) + assign O = PAD; + endgenerate +endmodule
\ No newline at end of file diff --git a/generic/synth/synth_generic.tcl b/generic/synth/synth_generic.tcl new file mode 100644 index 00000000..e5d88e0d --- /dev/null +++ b/generic/synth/synth_generic.tcl @@ -0,0 +1,24 @@ +# Usage +# tcl synth_generic.tcl {K} {out.json} + +set LUT_K 4 +if {$argc > 0} { set LUT_K [lindex $argv 0] } +yosys read_verilog -lib [file dirname [file normalize $argv0]]/prims.v +yosys hierarchy -check +yosys proc +yosys flatten +yosys tribuf -logic +yosys deminout +yosys synth -run coarse +yosys memory_map +yosys opt -full +yosys techmap -map +/techmap.v +yosys opt -fast +yosys abc -lut $LUT_K -dress +yosys clean +yosys techmap -D LUT_K=$LUT_K -map [file dirname [file normalize $argv0]]/cells_map.v +yosys clean +yosys hierarchy -check +yosys stat + +if {$argc > 1} { yosys write_json [lindex $argv 1] } diff --git a/gui/application.cc b/gui/application.cc index 7751e6f1..33a106bc 100644 --- a/gui/application.cc +++ b/gui/application.cc @@ -21,9 +21,11 @@ #include "application.h" #include <QMessageBox> +#include <QOpenGLContext> #include <QSurfaceFormat> #include <QTextStream> #include <exception> +#include "log.h" NEXTPNR_NAMESPACE_BEGIN @@ -37,12 +39,28 @@ BOOL WINAPI WinHandler(DWORD dwCtrlType) } #endif -Application::Application(int &argc, char **argv) : QApplication(argc, argv) +Application::Application(int &argc, char **argv, bool noantialiasing) : QApplication(argc, argv) { QSurfaceFormat fmt; - fmt.setSamples(10); + if (!noantialiasing) + fmt.setSamples(10); fmt.setProfile(QSurfaceFormat::CoreProfile); + // macOS is very picky about this version matching + // the version of openGL used in ImGuiRenderer + fmt.setMajorVersion(3); + fmt.setMinorVersion(2); QSurfaceFormat::setDefaultFormat(fmt); + + QOpenGLContext glContext; + fmt = glContext.format(); + if (fmt.majorVersion() < 3) { + printf("Could not get OpenGL 3.0 context. Aborting.\n"); + log_abort(); + } + if (fmt.minorVersion() < 2) { + printf("Could not get OpenGL 3.2 context - trying anyway...\n "); + } + #ifdef _WIN32 SetConsoleCtrlHandler((PHANDLER_ROUTINE)WinHandler, TRUE); #endif @@ -53,7 +71,7 @@ bool Application::notify(QObject *receiver, QEvent *event) bool retVal = true; try { retVal = QApplication::notify(receiver, event); - } catch (assertion_failure ex) { + } catch (const assertion_failure &ex) { QString msg; QTextStream out(&msg); out << ex.filename.c_str() << " at " << ex.line << "\n"; diff --git a/gui/application.h b/gui/application.h index 321f6b65..ad5de62f 100644 --- a/gui/application.h +++ b/gui/application.h @@ -29,7 +29,7 @@ NEXTPNR_NAMESPACE_BEGIN class Application : public QApplication { public: - Application(int &argc, char **argv); + Application(int &argc, char **argv, bool noantialiasing); bool notify(QObject *receiver, QEvent *event); }; diff --git a/gui/designwidget.cc b/gui/designwidget.cc index fc99cd14..1617340b 100644 --- a/gui/designwidget.cc +++ b/gui/designwidget.cc @@ -444,9 +444,9 @@ TreeModel::Model *DesignWidget::getTreeByElementType(ElementType type) return treeModel[1];
if (type == ElementType::PIP)
return treeModel[2];
- if (type == ElementType::NET)
- return treeModel[3];
if (type == ElementType::CELL)
+ return treeModel[3];
+ if (type == ElementType::NET)
return treeModel[4];
return nullptr;
}
@@ -460,9 +460,9 @@ int DesignWidget::getIndexByElementType(ElementType type) return 1;
if (type == ElementType::PIP)
return 2;
- if (type == ElementType::NET)
- return 3;
if (type == ElementType::CELL)
+ return 3;
+ if (type == ElementType::NET)
return 4;
if (type == ElementType::GROUP)
return 5;
diff --git a/gui/fpgaviewwidget.cc b/gui/fpgaviewwidget.cc index c932c3e7..f2929d6e 100644 --- a/gui/fpgaviewwidget.cc +++ b/gui/fpgaviewwidget.cc @@ -59,20 +59,6 @@ FPGAViewWidget::FPGAViewWidget(QWidget *parent) rendererArgs_->gridChanged = false; rendererArgs_->zoomOutbound = true; - auto fmt = format(); - fmt.setMajorVersion(3); - fmt.setMinorVersion(2); - setFormat(fmt); - - fmt = format(); - if (fmt.majorVersion() < 3) { - printf("Could not get OpenGL 3.0 context. Aborting.\n"); - log_abort(); - } - if (fmt.minorVersion() < 2) { - printf("Could not get OpenGL 3.2 context - trying anyway...\n "); - } - connect(&paintTimer_, SIGNAL(timeout()), this, SLOT(update())); paintTimer_.start(1000 / 20); // paint GL 20 times per second @@ -645,10 +631,10 @@ void FPGAViewWidget::mousePressEvent(QMouseEvent *event) return; bool shift = QApplication::keyboardModifiers().testFlag(Qt::ShiftModifier); - bool ctrl = QApplication::keyboardModifiers().testFlag(Qt::ControlModifier); + bool ctrl = QApplication::keyboardModifiers().testFlag(Qt::ControlModifier); bool btn_right = event->buttons() & Qt::RightButton; - bool btn_mid = event->buttons() & Qt::MidButton; - bool btn_left = event->buttons() & Qt::LeftButton; + bool btn_mid = event->buttons() & Qt::MidButton; + bool btn_left = event->buttons() & Qt::LeftButton; if (btn_right || btn_mid || (btn_left && shift)) { lastDragPos_ = event->pos(); @@ -687,8 +673,8 @@ void FPGAViewWidget::mouseMoveEvent(QMouseEvent *event) bool shift = QApplication::keyboardModifiers().testFlag(Qt::ShiftModifier); bool btn_right = event->buttons() & Qt::RightButton; - bool btn_mid = event->buttons() & Qt::MidButton; - bool btn_left = event->buttons() & Qt::LeftButton; + bool btn_mid = event->buttons() & Qt::MidButton; + bool btn_left = event->buttons() & Qt::LeftButton; if (btn_right || btn_mid || (btn_left && shift)) { const int dx = event->x() - lastDragPos_.x(); diff --git a/gui/generic/mainwindow.cc b/gui/generic/mainwindow.cc index 12912cc9..54d1f2c8 100644 --- a/gui/generic/mainwindow.cc +++ b/gui/generic/mainwindow.cc @@ -19,6 +19,9 @@ #include "mainwindow.h"
+#include <QMessageBox>
+#include <cstdlib>
+
static void initMainResource() { Q_INIT_RESOURCE(nextpnr); }
NEXTPNR_NAMESPACE_BEGIN
@@ -26,14 +29,8 @@ NEXTPNR_NAMESPACE_BEGIN MainWindow::MainWindow(std::unique_ptr<Context> context, ArchArgs args, QWidget *parent)
: BaseMainWindow(std::move(context), args, parent)
{
- initMainResource();
-
- std::string title = "nextpnr-generic - [EMPTY]";
- setWindowTitle(title.c_str());
-
- connect(this, &BaseMainWindow::contextChanged, this, &MainWindow::newContext);
-
- createMenu();
+ QMessageBox::critical(0, "Error - FIXME", "No GUI support for nextpnr-generic");
+ std::exit(1);
}
MainWindow::~MainWindow() {}
diff --git a/gui/lineshader.h b/gui/lineshader.h index 98042051..4c54bf46 100644 --- a/gui/lineshader.h +++ b/gui/lineshader.h @@ -172,10 +172,10 @@ class LineShader LineShader(QObject *parent) : parent_(parent), program_(nullptr) {} static constexpr const char *vertexShaderSource_ = - "#version 110\n" - "attribute highp vec2 position;\n" - "attribute highp vec2 normal;\n" - "attribute highp float miter;\n" + "#version 150\n" + "in highp vec2 position;\n" + "in highp vec2 normal;\n" + "in highp float miter;\n" "uniform highp float thickness;\n" "uniform highp mat4 projection;\n" "void main() {\n" @@ -183,10 +183,11 @@ class LineShader " gl_Position = projection * vec4(p, 0.0, 1.0);\n" "}\n"; - static constexpr const char *fragmentShaderSource_ = "#version 110\n" + static constexpr const char *fragmentShaderSource_ = "#version 150\n" "uniform lowp vec4 color;\n" + "out vec4 Out_Color;\n" "void main() {\n" - " gl_FragColor = color;\n" + " Out_Color = color;\n" "}\n"; // Must be called on initialization. diff --git a/gui/pythontab.cc b/gui/pythontab.cc index 827f1907..c83f1ece 100644 --- a/gui/pythontab.cc +++ b/gui/pythontab.cc @@ -96,9 +96,10 @@ void PythonTab::newContext(Context *ctx) console->clear();
pyinterpreter_preinit();
- init_python("nextpnr", !initialized);
+ init_python("nextpnr", true);
pyinterpreter_initialize();
pyinterpreter_aquire();
+ init_python("nextpnr", false);
python_export_global("ctx", ctx);
pyinterpreter_release();
diff --git a/ice40/arch.cc b/ice40/arch.cc index c822d5c4..80e1fb4c 100644 --- a/ice40/arch.cc +++ b/ice40/arch.cc @@ -26,10 +26,10 @@ #include "log.h" #include "nextpnr.h" #include "placer1.h" +#include "placer_heap.h" #include "router1.h" #include "timing_opt.h" #include "util.h" - NEXTPNR_NAMESPACE_BEGIN // ----------------------------------------------------------------------- @@ -56,7 +56,7 @@ const char *chipdb_blob_5k = nullptr; const char *chipdb_blob_u4k = nullptr; const char *chipdb_blob_8k = nullptr; -boost::iostreams::mapped_file_source blob_files[4]; +boost::iostreams::mapped_file_source blob_files[5]; const char *mmap_file(int index, const char *filename) { @@ -75,8 +75,8 @@ void load_chipdb() chipdb_blob_384 = mmap_file(0, EXTERNAL_CHIPDB_ROOT "/ice40/chipdb-384.bin"); chipdb_blob_1k = mmap_file(1, EXTERNAL_CHIPDB_ROOT "/ice40/chipdb-1k.bin"); chipdb_blob_5k = mmap_file(2, EXTERNAL_CHIPDB_ROOT "/ice40/chipdb-5k.bin"); - chipdb_blob_u4k = mmap_file(2, EXTERNAL_CHIPDB_ROOT "/ice40/chipdb-u4k.bin"); - chipdb_blob_8k = mmap_file(3, EXTERNAL_CHIPDB_ROOT "/ice40/chipdb-8k.bin"); + chipdb_blob_u4k = mmap_file(3, EXTERNAL_CHIPDB_ROOT "/ice40/chipdb-u4k.bin"); + chipdb_blob_8k = mmap_file(4, EXTERNAL_CHIPDB_ROOT "/ice40/chipdb-8k.bin"); } #endif Arch::Arch(ArchArgs args) : args(args) @@ -671,8 +671,18 @@ bool Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay bool Arch::place() { - if (!placer1(getCtx(), Placer1Cfg(getCtx()))) - return false; + std::string placer = str_or_default(settings, id("placer"), defaultPlacer); + if (placer == "heap") { + PlacerHeapCfg cfg(getCtx()); + cfg.ioBufTypes.insert(id_SB_IO); + if (!placer_heap(getCtx(), cfg)) + return false; + } else if (placer == "sa") { + if (!placer1(getCtx(), Placer1Cfg(getCtx()))) + return false; + } else { + log_error("iCE40 architecture does not support placer '%s'\n", placer.c_str()); + } if (bool_or_default(settings, id("opt_timing"), false)) { TimingOptCfg tocfg(getCtx()); tocfg.cellTypes.insert(id_ICESTORM_LC); @@ -1035,6 +1045,14 @@ TimingPortClass Arch::getPortTimingClass(const CellInfo *cell, IdString port, in return TMG_COMB_INPUT; } else if (cell->type == id_SB_WARMBOOT) { return TMG_ENDPOINT; + } else if (cell->type == id_SB_LED_DRV_CUR) { + if (port == id_LEDPU) + return TMG_IGNORE; + return TMG_ENDPOINT; + } else if (cell->type == id_SB_RGB_DRV) { + if (port == id_RGB0 || port == id_RGB1 || port == id_RGB2 || port == id_RGBPU) + return TMG_IGNORE; + return TMG_ENDPOINT; } else if (cell->type == id_SB_RGBA_DRV) { if (port == id_RGB0 || port == id_RGB1 || port == id_RGB2) return TMG_IGNORE; @@ -1043,6 +1061,16 @@ TimingPortClass Arch::getPortTimingClass(const CellInfo *cell, IdString port, in if (port == id_CLK || port == id_CLOCK) return TMG_CLOCK_INPUT; return TMG_IGNORE; + } else if (cell->type == id_SB_I2C || cell->type == id_SB_SPI) { + if (port == this->id("SBCLKI")) + return TMG_CLOCK_INPUT; + + clockInfoCount = 1; + + if (cell->ports.at(port).type == PORT_OUT) + return TMG_REGISTER_OUTPUT; + else + return TMG_REGISTER_INPUT; } log_error("cell type '%s' is unsupported (instantiated as '%s')\n", cell->type.c_str(this), cell->name.c_str(this)); } @@ -1134,6 +1162,17 @@ TimingClockingInfo Arch::getPortClockingInfo(const CellInfo *cell, IdString port info.setup.delay = 100; info.hold.delay = 0; } + } else if (cell->type == id_SB_I2C || cell->type == id_SB_SPI) { + info.clock_port = this->id("SBCLKI"); + info.edge = RISING_EDGE; + if (cell->ports.at(port).type == PORT_OUT) { + /* Dummy number */ + info.clockToQ.delay = 1500; + } else { + /* Dummy number */ + info.setup.delay = 1500; + info.hold.delay = 0; + } } else { NPNR_ASSERT_FALSE("unhandled cell type in getPortClockingInfo"); } @@ -1190,12 +1229,20 @@ void Arch::assignCellInfo(CellInfo *cell) } else if (cell->type == id_SB_IO) { cell->ioInfo.lvds = str_or_default(cell->params, id_IO_STANDARD, "SB_LVCMOS") == "SB_LVDS_INPUT"; cell->ioInfo.global = bool_or_default(cell->attrs, this->id("GLOBAL")); - cell->ioInfo.pintype = int_or_default(cell->attrs, this->id("PIN_TYPE")); - cell->ioInfo.negtrig = bool_or_default(cell->attrs, this->id("NEG_TRIGGER")); + cell->ioInfo.pintype = int_or_default(cell->params, this->id("PIN_TYPE")); + cell->ioInfo.negtrig = bool_or_default(cell->params, this->id("NEG_TRIGGER")); } else if (cell->type == id_SB_GB) { cell->gbInfo.forPadIn = bool_or_default(cell->attrs, this->id("FOR_PAD_IN")); } } +const std::string Arch::defaultPlacer = "sa"; + +const std::vector<std::string> Arch::availablePlacers = {"sa", +#ifdef WITH_HEAP + "heap" +#endif +}; + NEXTPNR_NAMESPACE_END diff --git a/ice40/arch.h b/ice40/arch.h index 706043b2..ea29f4f1 100644 --- a/ice40/arch.h +++ b/ice40/arch.h @@ -897,6 +897,9 @@ struct Arch : BaseCtx IdString glb_net = getWireName(getBelPinWire(bel, id_GLOBAL_BUFFER_OUTPUT)); return std::stoi(std::string("") + glb_net.str(this).back()); } + + static const std::string defaultPlacer; + static const std::vector<std::string> availablePlacers; }; void ice40DelayFuzzerMain(Context *ctx); diff --git a/ice40/arch_place.cc b/ice40/arch_place.cc index 90bb62b9..ede8d47f 100644 --- a/ice40/arch_place.cc +++ b/ice40/arch_place.cc @@ -91,6 +91,18 @@ bool Arch::isBelLocationValid(BelId bel) const } } +static inline bool _io_pintype_need_clk_in(unsigned pin_type) { return (pin_type & 0x01) == 0x00; } + +static inline bool _io_pintype_need_clk_out(unsigned pin_type) +{ + return ((pin_type & 0x30) == 0x30) || ((pin_type & 0x3c) && ((pin_type & 0x0c) != 0x08)); +} + +static inline bool _io_pintype_need_clk_en(unsigned pin_type) +{ + return _io_pintype_need_clk_in(pin_type) || _io_pintype_need_clk_out(pin_type); +} + bool Arch::isValidBelForCell(CellInfo *cell, BelId bel) const { if (cell->type == id_ICESTORM_LC) { @@ -157,6 +169,30 @@ bool Arch::isValidBelForCell(CellInfo *cell, BelId bel) const CellInfo *compCell = getBoundBelCell(compBel); if (compCell && compCell->ioInfo.lvds) return false; + + // Check for conflicts on shared nets + // - CLOCK_ENABLE + // - OUTPUT_CLK + // - INPUT_CLK + if (compCell) { + bool use[6] = { + _io_pintype_need_clk_in(cell->ioInfo.pintype), + _io_pintype_need_clk_in(compCell->ioInfo.pintype), + _io_pintype_need_clk_out(cell->ioInfo.pintype), + _io_pintype_need_clk_out(compCell->ioInfo.pintype), + _io_pintype_need_clk_en(cell->ioInfo.pintype), + _io_pintype_need_clk_en(compCell->ioInfo.pintype), + }; + NetInfo *nets[] = { + cell->ports[id_INPUT_CLK].net, compCell->ports[id_INPUT_CLK].net, + cell->ports[id_OUTPUT_CLK].net, compCell->ports[id_OUTPUT_CLK].net, + cell->ports[id_CLOCK_ENABLE].net, compCell->ports[id_CLOCK_ENABLE].net, + }; + + for (int i = 0; i < 6; i++) + if (use[i] && (nets[i] != nets[i ^ 1]) && (use[i ^ 1] || (nets[i ^ 1] != nullptr))) + return false; + } } return getBelPackagePin(bel) != ""; diff --git a/ice40/arch_pybindings.cc b/ice40/arch_pybindings.cc index f0ca584b..bc0bfb84 100644 --- a/ice40/arch_pybindings.cc +++ b/ice40/arch_pybindings.cc @@ -144,6 +144,13 @@ void arch_wrap_python() fn_wrapper_2a_v<Context, decltype(&Context::addClock), &Context::addClock, conv_from_str<IdString>, pass_through<float>>::def_wrap(ctx_cls, "addClock"); + fn_wrapper_5a_v<Context, decltype(&Context::createRectangularRegion), &Context::createRectangularRegion, + conv_from_str<IdString>, pass_through<int>, pass_through<int>, pass_through<int>, + pass_through<int>>::def_wrap(ctx_cls, "createRectangularRegion"); + fn_wrapper_2a_v<Context, decltype(&Context::addBelToRegion), &Context::addBelToRegion, conv_from_str<IdString>, + conv_from_str<BelId>>::def_wrap(ctx_cls, "addBelToRegion"); + fn_wrapper_2a_v<Context, decltype(&Context::constrainCellToRegion), &Context::constrainCellToRegion, + conv_from_str<IdString>, conv_from_str<IdString>>::def_wrap(ctx_cls, "constrainCellToRegion"); WRAP_RANGE(Bel, conv_to_str<BelId>); WRAP_RANGE(Wire, conv_to_str<WireId>); diff --git a/ice40/archdefs.h b/ice40/archdefs.h index 956fcb4c..89591af5 100644 --- a/ice40/archdefs.h +++ b/ice40/archdefs.h @@ -159,6 +159,10 @@ struct ArchCellInfo { bool forPadIn; } gbInfo; + struct + { + bool ledCurConnected; + } ledInfo; }; }; diff --git a/ice40/bitstream.cc b/ice40/bitstream.cc index fe0d592d..7632b443 100644 --- a/ice40/bitstream.cc +++ b/ice40/bitstream.cc @@ -610,6 +610,14 @@ void write_asc(const Context *ctx, std::ostream &out) set_config(ti_ramt, config.at(y + 1).at(x), "RamConfig.CBIT_1", write_mode & 0x2); set_config(ti_ramt, config.at(y + 1).at(x), "RamConfig.CBIT_2", read_mode & 0x1); set_config(ti_ramt, config.at(y + 1).at(x), "RamConfig.CBIT_3", read_mode & 0x2); + } else if (cell.second->type == ctx->id("SB_LED_DRV_CUR")) { + set_ec_cbit(config, ctx, get_ec_config(ctx->chip_info, cell.second->bel), "LED_DRV_CUR_EN", true, + "IpConfig."); + } else if (cell.second->type == ctx->id("SB_RGB_DRV")) { + const std::vector<std::pair<std::string, int>> rgb_params = { + {"RGB0_CURRENT", 6}, {"RGB1_CURRENT", 6}, {"RGB2_CURRENT", 6}}; + configure_extra_cell(config, ctx, cell.second.get(), rgb_params, true, std::string("IpConfig.")); + set_ec_cbit(config, ctx, get_ec_config(ctx->chip_info, cell.second->bel), "RGB_DRV_EN", true, "IpConfig."); } else if (cell.second->type == ctx->id("SB_RGBA_DRV")) { const std::vector<std::pair<std::string, int>> rgba_params = { {"CURRENT_MODE", 1}, {"RGB0_CURRENT", 6}, {"RGB1_CURRENT", 6}, {"RGB2_CURRENT", 6}}; @@ -618,6 +626,28 @@ void write_asc(const Context *ctx, std::ostream &out) } else if (cell.second->type == ctx->id("SB_WARMBOOT") || cell.second->type == ctx->id("ICESTORM_LFOSC") || cell.second->type == ctx->id("SB_LEDDA_IP")) { // No config needed + } else if (cell.second->type == ctx->id("SB_I2C")) { + bool sda_in_dly = !cell.second->attrs.count(ctx->id("SDA_INPUT_DELAYED")) || + std::stoi(cell.second->attrs[ctx->id("SDA_INPUT_DELAYED")]); + bool sda_out_dly = !cell.second->attrs.count(ctx->id("SDA_OUTPUT_DELAYED")) || + std::stoi(cell.second->attrs[ctx->id("SDA_OUTPUT_DELAYED")]); + set_ec_cbit(config, ctx, get_ec_config(ctx->chip_info, cell.second->bel), "SDA_INPUT_DELAYED", sda_in_dly, + "IpConfig."); + set_ec_cbit(config, ctx, get_ec_config(ctx->chip_info, cell.second->bel), "SDA_OUTPUT_DELAYED", sda_out_dly, + "IpConfig."); + set_ec_cbit(config, ctx, get_ec_config(ctx->chip_info, cell.second->bel), "I2C_ENABLE_0", true, + "IpConfig."); + set_ec_cbit(config, ctx, get_ec_config(ctx->chip_info, cell.second->bel), "I2C_ENABLE_1", true, + "IpConfig."); + } else if (cell.second->type == ctx->id("SB_SPI")) { + set_ec_cbit(config, ctx, get_ec_config(ctx->chip_info, cell.second->bel), "SPI_ENABLE_0", true, + "IpConfig."); + set_ec_cbit(config, ctx, get_ec_config(ctx->chip_info, cell.second->bel), "SPI_ENABLE_1", true, + "IpConfig."); + set_ec_cbit(config, ctx, get_ec_config(ctx->chip_info, cell.second->bel), "SPI_ENABLE_2", true, + "IpConfig."); + set_ec_cbit(config, ctx, get_ec_config(ctx->chip_info, cell.second->bel), "SPI_ENABLE_3", true, + "IpConfig."); } else if (cell.second->type == ctx->id("ICESTORM_SPRAM")) { const BelInfoPOD &beli = ci.bel_data[bel.index]; int x = beli.x, y = beli.y, z = beli.z; diff --git a/ice40/cells.cc b/ice40/cells.cc index 35a5346f..a2abcea4 100644 --- a/ice40/cells.cc +++ b/ice40/cells.cc @@ -260,6 +260,22 @@ std::unique_ptr<CellInfo> create_ice_cell(Context *ctx, IdString type, std::stri add_port(ctx, new_cell.get(), "RGB0", PORT_OUT); add_port(ctx, new_cell.get(), "RGB1", PORT_OUT); add_port(ctx, new_cell.get(), "RGB2", PORT_OUT); + } else if (type == ctx->id("SB_LED_DRV_CUR")) { + add_port(ctx, new_cell.get(), "EN", PORT_IN); + add_port(ctx, new_cell.get(), "LEDPU", PORT_OUT); + } else if (type == ctx->id("SB_RGB_DRV")) { + new_cell->params[ctx->id("RGB0_CURRENT")] = "0b000000"; + new_cell->params[ctx->id("RGB1_CURRENT")] = "0b000000"; + new_cell->params[ctx->id("RGB2_CURRENT")] = "0b000000"; + + add_port(ctx, new_cell.get(), "RGBPU", PORT_IN); + add_port(ctx, new_cell.get(), "RGBLEDEN", PORT_IN); + add_port(ctx, new_cell.get(), "RGB0PWM", PORT_IN); + add_port(ctx, new_cell.get(), "RGB1PWM", PORT_IN); + add_port(ctx, new_cell.get(), "RGB2PWM", PORT_IN); + add_port(ctx, new_cell.get(), "RGB0", PORT_OUT); + add_port(ctx, new_cell.get(), "RGB1", PORT_OUT); + add_port(ctx, new_cell.get(), "RGB2", PORT_OUT); } else if (type == ctx->id("SB_LEDDA_IP")) { add_port(ctx, new_cell.get(), "LEDDCS", PORT_IN); add_port(ctx, new_cell.get(), "LEDDCLK", PORT_IN); @@ -275,6 +291,53 @@ std::unique_ptr<CellInfo> create_ice_cell(Context *ctx, IdString type, std::stri add_port(ctx, new_cell.get(), "PWMOUT1", PORT_OUT); add_port(ctx, new_cell.get(), "PWMOUT2", PORT_OUT); add_port(ctx, new_cell.get(), "LEDDON", PORT_OUT); + } else if (type == ctx->id("SB_I2C")) { + new_cell->params[ctx->id("I2C_SLAVE_INIT_ADDR")] = "0b1111100001"; + new_cell->params[ctx->id("BUS_ADDR74")] = "0b0001"; + for (int i = 0; i < 8; i++) { + add_port(ctx, new_cell.get(), "SBADRI" + std::to_string(i), PORT_IN); + add_port(ctx, new_cell.get(), "SBDATI" + std::to_string(i), PORT_IN); + add_port(ctx, new_cell.get(), "SBDATO" + std::to_string(i), PORT_OUT); + } + add_port(ctx, new_cell.get(), "SBCLKI", PORT_IN); + add_port(ctx, new_cell.get(), "SBRWI", PORT_IN); + add_port(ctx, new_cell.get(), "SBSTBI", PORT_IN); + add_port(ctx, new_cell.get(), "SCLI", PORT_IN); + add_port(ctx, new_cell.get(), "SDAI", PORT_IN); + add_port(ctx, new_cell.get(), "SBACKO", PORT_OUT); + add_port(ctx, new_cell.get(), "I2CIRQ", PORT_OUT); + add_port(ctx, new_cell.get(), "I2CWKUP", PORT_OUT); + add_port(ctx, new_cell.get(), "SCLO", PORT_OUT); + add_port(ctx, new_cell.get(), "SCLOE", PORT_OUT); + add_port(ctx, new_cell.get(), "SDAO", PORT_OUT); + add_port(ctx, new_cell.get(), "SDAOE", PORT_OUT); + } else if (type == ctx->id("SB_SPI")) { + new_cell->params[ctx->id("BUS_ADDR74")] = "0b0000"; + for (int i = 0; i < 8; i++) { + add_port(ctx, new_cell.get(), "SBADRI" + std::to_string(i), PORT_IN); + add_port(ctx, new_cell.get(), "SBDATI" + std::to_string(i), PORT_IN); + add_port(ctx, new_cell.get(), "SBDATO" + std::to_string(i), PORT_OUT); + } + add_port(ctx, new_cell.get(), "SBCLKI", PORT_IN); + add_port(ctx, new_cell.get(), "SBRWI", PORT_IN); + add_port(ctx, new_cell.get(), "SBSTBI", PORT_IN); + add_port(ctx, new_cell.get(), "MI", PORT_IN); + add_port(ctx, new_cell.get(), "SI", PORT_IN); + add_port(ctx, new_cell.get(), "SCKI", PORT_IN); + add_port(ctx, new_cell.get(), "SCSNI", PORT_IN); + add_port(ctx, new_cell.get(), "SBACKO", PORT_OUT); + add_port(ctx, new_cell.get(), "SPIIRQ", PORT_OUT); + add_port(ctx, new_cell.get(), "SPIWKUP", PORT_OUT); + add_port(ctx, new_cell.get(), "SO", PORT_OUT); + add_port(ctx, new_cell.get(), "SOE", PORT_OUT); + add_port(ctx, new_cell.get(), "MO", PORT_OUT); + add_port(ctx, new_cell.get(), "MOE", PORT_OUT); + add_port(ctx, new_cell.get(), "SCKO", PORT_OUT); + add_port(ctx, new_cell.get(), "SCKOE", PORT_OUT); + for (int i = 0; i < 4; i++) { + add_port(ctx, new_cell.get(), "MCSNO" + std::to_string(i), PORT_OUT); + add_port(ctx, new_cell.get(), "MCSNOE" + std::to_string(i), PORT_OUT); + } } else { log_error("unable to create iCE40 cell of type %s", type.c_str(ctx)); } diff --git a/ice40/cells.h b/ice40/cells.h index 93ef3db4..3d9358da 100644 --- a/ice40/cells.h +++ b/ice40/cells.h @@ -76,8 +76,19 @@ inline bool is_sb_mac16(const BaseCtx *ctx, const CellInfo *cell) { return cell- inline bool is_sb_rgba_drv(const BaseCtx *ctx, const CellInfo *cell) { return cell->type == ctx->id("SB_RGBA_DRV"); } +inline bool is_sb_rgb_drv(const BaseCtx *ctx, const CellInfo *cell) { return cell->type == ctx->id("SB_RGB_DRV"); } + +inline bool is_sb_led_drv_cur(const BaseCtx *ctx, const CellInfo *cell) +{ + return cell->type == ctx->id("SB_LED_DRV_CUR"); +} + inline bool is_sb_ledda_ip(const BaseCtx *ctx, const CellInfo *cell) { return cell->type == ctx->id("SB_LEDDA_IP"); } +inline bool is_sb_i2c(const BaseCtx *ctx, const CellInfo *cell) { return cell->type == ctx->id("SB_I2C"); } + +inline bool is_sb_spi(const BaseCtx *ctx, const CellInfo *cell) { return cell->type == ctx->id("SB_SPI"); } + inline bool is_sb_pll40(const BaseCtx *ctx, const CellInfo *cell) { return cell->type == ctx->id("SB_PLL40_PAD") || cell->type == ctx->id("SB_PLL40_2_PAD") || diff --git a/ice40/chipdb.py b/ice40/chipdb.py index 42ca6ac1..cc7be01f 100644 --- a/ice40/chipdb.py +++ b/ice40/chipdb.py @@ -81,6 +81,8 @@ constids["SPI"] = constids["SB_SPI"] constids["LEDDA_IP"] = constids["SB_LEDDA_IP"] constids["RGBA_DRV"] = constids["SB_RGBA_DRV"] constids["SPRAM"] = constids["ICESTORM_SPRAM"] +constids["LED_DRV_CUR"] = constids["SB_LED_DRV_CUR"] +constids["RGB_DRV"] = constids["SB_RGB_DRV"] with open(args.gfxh) as f: state = 0 diff --git a/ice40/constids.inc b/ice40/constids.inc index 366a3a9d..6aa5c4c0 100644 --- a/ice40/constids.inc +++ b/ice40/constids.inc @@ -355,6 +355,9 @@ X(PWMOUT0) X(PWMOUT1) X(PWMOUT2) +X(LEDPU) +X(EN) +X(RGBPU) X(CURREN) X(RGB0PWM) X(RGB1PWM) @@ -438,6 +441,8 @@ X(IO_I3C) X(SB_LEDDA_IP) X(SB_RGBA_DRV) X(ICESTORM_SPRAM) +X(SB_LED_DRV_CUR) +X(SB_RGB_DRV) // cell parameters X(DFF_ENABLE) diff --git a/ice40/blinky.pcf b/ice40/examples/blinky/blinky.pcf index 141dfcc8..141dfcc8 100644 --- a/ice40/blinky.pcf +++ b/ice40/examples/blinky/blinky.pcf diff --git a/ice40/blinky.proj b/ice40/examples/blinky/blinky.proj index f5bb9f88..f5bb9f88 100644 --- a/ice40/blinky.proj +++ b/ice40/examples/blinky/blinky.proj diff --git a/ice40/blinky.sh b/ice40/examples/blinky/blinky.sh index a2326fc3..a2326fc3 100755 --- a/ice40/blinky.sh +++ b/ice40/examples/blinky/blinky.sh diff --git a/ice40/blinky.v b/ice40/examples/blinky/blinky.v index 36eaee86..36eaee86 100644 --- a/ice40/blinky.v +++ b/ice40/examples/blinky/blinky.v diff --git a/ice40/blinky.ys b/ice40/examples/blinky/blinky.ys index a5dd2c85..a5dd2c85 100644 --- a/ice40/blinky.ys +++ b/ice40/examples/blinky/blinky.ys diff --git a/ice40/blinky_tb.v b/ice40/examples/blinky/blinky_tb.v index f80b5e64..f80b5e64 100644 --- a/ice40/blinky_tb.v +++ b/ice40/examples/blinky/blinky_tb.v diff --git a/ice40/examples/floorplan/.gitignore b/ice40/examples/floorplan/.gitignore new file mode 100644 index 00000000..d93659be --- /dev/null +++ b/ice40/examples/floorplan/.gitignore @@ -0,0 +1,4 @@ +*.json +*.asc +*.bin +__pycache__
\ No newline at end of file diff --git a/ice40/examples/floorplan/floorplan.py b/ice40/examples/floorplan/floorplan.py new file mode 100644 index 00000000..85c53ccd --- /dev/null +++ b/ice40/examples/floorplan/floorplan.py @@ -0,0 +1,5 @@ +ctx.createRectangularRegion("osc", 1, 1, 1, 4) +for cell, cellinfo in ctx.cells: + if "ringosc" in cellinfo.attrs: + print("Floorplanned cell %s" % cell) + ctx.constrainCellToRegion(cell, "osc") diff --git a/ice40/examples/floorplan/floorplan.sh b/ice40/examples/floorplan/floorplan.sh new file mode 100755 index 00000000..e0ed7a64 --- /dev/null +++ b/ice40/examples/floorplan/floorplan.sh @@ -0,0 +1,6 @@ +#!/usr/bin/env bash +set -ex +yosys -p "synth_ice40 -top top -json floorplan.json" floorplan.v +../../../nextpnr-ice40 --up5k --json floorplan.json --pcf icebreaker.pcf --asc floorplan.asc --ignore-loops --pre-place floorplan.py +icepack floorplan.asc floorplan.bin +iceprog floorplan.bin diff --git a/ice40/examples/floorplan/floorplan.v b/ice40/examples/floorplan/floorplan.v new file mode 100644 index 00000000..8f99ed4e --- /dev/null +++ b/ice40/examples/floorplan/floorplan.v @@ -0,0 +1,22 @@ +module top(output LED1, LED2, LED3, LED4, LED5); + localparam N = 31; + wire [N:0] x; + assign x[0] = x[N]; + + genvar ii; + generate + + for (ii = 0; ii < N; ii = ii + 1) begin + (* ringosc *) + SB_LUT4 #(.LUT_INIT(1)) lut_i(.I0(x[ii]), .I1(), .I2(), .I3(), .O(x[ii+1])); + end + endgenerate + + assign clk = x[N]; + + + reg [19:0] ctr; + always @(posedge clk) + ctr <= ctr + 1'b1; + assign {LED5, LED4, LED3, LED2, LED1} = ctr[19:15]; +endmodule diff --git a/ice40/examples/floorplan/icebreaker.pcf b/ice40/examples/floorplan/icebreaker.pcf new file mode 100644 index 00000000..ac7ebf9e --- /dev/null +++ b/ice40/examples/floorplan/icebreaker.pcf @@ -0,0 +1,5 @@ +set_io -nowarn LED1 26 +set_io -nowarn LED2 27 +set_io -nowarn LED3 25 +set_io -nowarn LED4 23 +set_io -nowarn LED5 21 diff --git a/ice40/main.cc b/ice40/main.cc index 2313c2ae..9b79a08c 100644 --- a/ice40/main.cc +++ b/ice40/main.cc @@ -176,7 +176,6 @@ std::unique_ptr<Context> Ice40CommandHandler::createContext() ctx->settings[ctx->id("opt_timing")] = "1"; if (vm.count("pcf-allow-unconstrained")) ctx->settings[ctx->id("pcf_allow_unconstrained")] = "1"; - return ctx; } diff --git a/ice40/pack.cc b/ice40/pack.cc index c22c4e8c..f520b295 100644 --- a/ice40/pack.cc +++ b/ice40/pack.cc @@ -383,12 +383,9 @@ static void pack_constants(Context *ctx) } } -static std::unique_ptr<CellInfo> create_padin_gbuf(Context *ctx, CellInfo *cell, IdString port_name, - std::string gbuf_name) +static BelId find_padin_gbuf(Context *ctx, BelId bel, IdString port_name) { - // Find the matching SB_GB BEL connected to the same global network BelId gb_bel; - BelId bel = ctx->getBelByName(ctx->id(cell->attrs[ctx->id("BEL")])); auto wire = ctx->getBelPinWire(bel, port_name); if (wire == WireId()) @@ -401,6 +398,15 @@ static std::unique_ptr<CellInfo> create_padin_gbuf(Context *ctx, CellInfo *cell, } } + return gb_bel; +} + +static std::unique_ptr<CellInfo> create_padin_gbuf(Context *ctx, CellInfo *cell, IdString port_name, + std::string gbuf_name) +{ + // Find the matching SB_GB BEL connected to the same global network + BelId bel = ctx->getBelByName(ctx->id(cell->attrs[ctx->id("BEL")])); + BelId gb_bel = find_padin_gbuf(ctx, bel, port_name); NPNR_ASSERT(gb_bel != BelId()); // Create a SB_GB Cell and lock it there @@ -444,7 +450,8 @@ static void pack_io(Context *ctx) } else if (ci->type == ctx->id("$nextpnr_obuf")) { NetInfo *net = ci->ports.at(ctx->id("I")).net; sb = net_only_drives(ctx, net, is_ice_iob, ctx->id("PACKAGE_PIN"), true, ci); - if (net && net->driver.cell && is_sb_rgba_drv(ctx, net->driver.cell)) + if (net && net->driver.cell && + (is_sb_rgba_drv(ctx, net->driver.cell) || is_sb_rgb_drv(ctx, net->driver.cell))) rgb = net->driver.cell; } if (sb != nullptr) { @@ -470,7 +477,8 @@ static void pack_io(Context *ctx) } } } else if (rgb != nullptr) { - log_info("%s use by SB_RGBA_DRV %s, not creating SB_IO\n", ci->name.c_str(ctx), rgb->name.c_str(ctx)); + log_info("%s use by SB_RGBA_DRV/SB_RGB_DRV %s, not creating SB_IO\n", ci->name.c_str(ctx), + rgb->name.c_str(ctx)); disconnect_port(ctx, ci, ctx->id("I")); packed_cells.insert(ci->name); continue; @@ -502,6 +510,19 @@ static void pack_io(Context *ctx) // Make it a normal SB_IO with global marker ci->type = ctx->id("SB_IO"); ci->attrs[ctx->id("GLOBAL")] = "1"; + } else if (is_sb_io(ctx, ci)) { + // Disconnect unused inputs + NetInfo *net_in0 = ci->ports.count(id_D_IN_0) ? ci->ports[id_D_IN_0].net : nullptr; + NetInfo *net_in1 = ci->ports.count(id_D_IN_1) ? ci->ports[id_D_IN_1].net : nullptr; + + if (net_in0 != nullptr && net_in0->users.size() == 0) { + delete_nets.insert(net_in0->name); + ci->ports[id_D_IN_0].net = nullptr; + } + if (net_in1 != nullptr && net_in1->users.size() == 0) { + delete_nets.insert(net_in1->name); + ci->ports[id_D_IN_1].net = nullptr; + } } } for (auto pcell : packed_cells) { @@ -691,14 +712,15 @@ static void promote_globals(Context *ctx) // Figure out where to place PLLs static void place_plls(Context *ctx) { - std::map<BelId, std::pair<BelPin, BelPin>> pll_all_bels; + std::map<BelId, std::tuple<BelPin, BelId, BelPin, BelId>> pll_all_bels; std::map<BelId, CellInfo *> pll_used_bels; std::vector<CellInfo *> pll_cells; std::map<BelId, CellInfo *> bel2io; + std::map<BelId, CellInfo *> bel2gb; log_info("Placing PLLs..\n"); - // Find all the PLLs BELs and matching IO sites + // Find all the PLLs BELs and matching IO sites and global networks for (auto bel : ctx->getBels()) { if (ctx->getBelType(bel) != id_ICESTORM_PLL) continue; @@ -707,8 +729,10 @@ static void place_plls(Context *ctx) auto io_a_pin = ctx->getIOBSharingPLLPin(bel, id_PLLOUT_A); auto io_b_pin = ctx->getIOBSharingPLLPin(bel, id_PLLOUT_B); + auto gb_a = find_padin_gbuf(ctx, bel, id_PLLOUT_A_GLOBAL); + auto gb_b = find_padin_gbuf(ctx, bel, id_PLLOUT_B_GLOBAL); - pll_all_bels[bel] = std::make_pair(io_a_pin, io_b_pin); + pll_all_bels[bel] = std::make_tuple(io_a_pin, gb_a, io_b_pin, gb_b); } // Find all the PLLs cells we need to place and do pre-checks @@ -813,7 +837,8 @@ static void place_plls(Context *ctx) for (auto placed_pll : pll_used_bels) { BelPin pll_io_a, pll_io_b; - std::tie(pll_io_a, pll_io_b) = pll_all_bels[placed_pll.first]; + BelId gb_a, gb_b; + std::tie(pll_io_a, gb_a, pll_io_b, gb_b) = pll_all_bels[placed_pll.first]; if (io_bel == pll_io_a.bel) { // All the PAD type PLL stuff already checked above,so only // check for conflict with a user placed CORE PLL @@ -831,6 +856,47 @@ static void place_plls(Context *ctx) bel2io[io_bel] = io_ci; } + // Scan all SB_GBs to check for conflicts with PLL BELs + for (auto gb_cell : sorted(ctx->cells)) { + CellInfo *gb_ci = gb_cell.second; + if (!is_gbuf(ctx, gb_ci)) + continue; + + // Only consider the bound ones + if (!gb_ci->attrs.count(ctx->id("BEL"))) + continue; + + // Check all placed PLL (either forced by user, or forced by PACKAGEPIN) + BelId gb_bel = ctx->getBelByName(ctx->id(gb_ci->attrs[ctx->id("BEL")])); + + for (auto placed_pll : pll_used_bels) { + CellInfo *ci = placed_pll.second; + + // Used global connections + bool gb_a_used = ci->ports.count(id_PLLOUT_A_GLOBAL) && (ci->ports[id_PLLOUT_A_GLOBAL].net != nullptr) && + (ci->ports[id_PLLOUT_A_GLOBAL].net->users.size() > 0); + bool gb_b_used = is_sb_pll40_dual(ctx, ci) && ci->ports.count(id_PLLOUT_B_GLOBAL) && + (ci->ports[id_PLLOUT_B_GLOBAL].net != nullptr) && + (ci->ports[id_PLLOUT_B_GLOBAL].net->users.size() > 0); + + // Check for conflict + BelPin pll_io_a, pll_io_b; + BelId gb_a, gb_b; + std::tie(pll_io_a, gb_a, pll_io_b, gb_b) = pll_all_bels[placed_pll.first]; + if (gb_a_used && (gb_bel == gb_a)) { + log_error("PLL '%s' A output conflict with SB_GB '%s'\n", placed_pll.second->name.c_str(ctx), + gb_cell.second->name.c_str(ctx)); + } + if (gb_b_used && (gb_bel == gb_b)) { + log_error("PLL '%s' B output conflicts with SB_GB '%s'\n", placed_pll.second->name.c_str(ctx), + gb_cell.second->name.c_str(ctx)); + } + } + + // Save for later checks + bel2gb[gb_bel] = gb_ci; + } + // Scan all the CORE PLLs and place them in remaining available PLL BELs // (in two pass ... first do the dual ones, harder to place, then single port) for (int i = 0; i < 2; i++) { @@ -849,6 +915,13 @@ static void place_plls(Context *ctx) log_error("PLL '%s' is of CORE type but doesn't have a valid REFERENCECLK connection\n", ci->name.c_str(ctx)); + // Used global connections + bool gb_a_used = ci->ports.count(id_PLLOUT_A_GLOBAL) && (ci->ports[id_PLLOUT_A_GLOBAL].net != nullptr) && + (ci->ports[id_PLLOUT_A_GLOBAL].net->users.size() > 0); + bool gb_b_used = is_sb_pll40_dual(ctx, ci) && ci->ports.count(id_PLLOUT_B_GLOBAL) && + (ci->ports[id_PLLOUT_B_GLOBAL].net != nullptr) && + (ci->ports[id_PLLOUT_B_GLOBAL].net->users.size() > 0); + // Could this be a PAD PLL ? bool could_be_pad = false; BelId pad_bel; @@ -858,8 +931,11 @@ static void place_plls(Context *ctx) // Find a BEL for it BelId found_bel; for (auto bel_pll : pll_all_bels) { + if (pll_used_bels.count(bel_pll.first)) + continue; BelPin pll_io_a, pll_io_b; - std::tie(pll_io_a, pll_io_b) = bel_pll.second; + BelId gb_a, gb_b; + std::tie(pll_io_a, gb_a, pll_io_b, gb_b) = bel_pll.second; if (bel2io.count(pll_io_a.bel)) { if (pll_io_a.bel == pad_bel) could_be_pad = !bel2io.count(pll_io_b.bel) || !is_sb_pll40_dual(ctx, ci); @@ -867,6 +943,10 @@ static void place_plls(Context *ctx) } if (bel2io.count(pll_io_b.bel) && is_sb_pll40_dual(ctx, ci)) continue; + if (gb_a_used && bel2gb.count(gb_a)) + continue; + if (gb_b_used && bel2gb.count(gb_b)) + continue; found_bel = bel_pll.first; break; } @@ -960,6 +1040,27 @@ static void pack_special(Context *ctx) std::unordered_set<IdString> packed_cells; std::vector<std::unique_ptr<CellInfo>> new_cells; + // Handle LED_DRV_CUR first to set the ledCurConnected flag before RGB_DRV is handled below. + for (auto cell : sorted(ctx->cells)) { + CellInfo *ci = cell.second; + if (is_sb_led_drv_cur(ctx, ci)) { + /* Force placement (no choices anyway) */ + cell_place_unique(ctx, ci); + + NetInfo *ledpu_net = ci->ports.at(ctx->id("LEDPU")).net; + for (auto &user : ledpu_net->users) { + if (!is_sb_rgb_drv(ctx, user.cell)) { + log_error("SB_LED_DRV_CUR LEDPU port can only be connected to SB_RGB_DRV!\n"); + } else { + user.cell->ledInfo.ledCurConnected = true; + user.cell->ports.at(user.port).net = nullptr; + } + } + ci->ports.erase(ctx->id("LEDPU")); + ctx->nets.erase(ledpu_net->name); + } + } + for (auto cell : sorted(ctx->cells)) { CellInfo *ci = cell.second; if (is_sb_lfosc(ctx, ci)) { @@ -983,9 +1084,14 @@ static void pack_special(Context *ctx) create_ice_cell(ctx, ctx->id("ICESTORM_HFOSC"), ci->name.str(ctx) + "_OSC"); packed_cells.insert(ci->name); cell_place_unique(ctx, packed.get()); + packed->params[ctx->id("TRIM_EN")] = str_or_default(ci->params, ctx->id("TRIM_EN"), "0b0"); packed->params[ctx->id("CLKHF_DIV")] = str_or_default(ci->params, ctx->id("CLKHF_DIV"), "0b00"); replace_port(ci, ctx->id("CLKHFEN"), packed.get(), ctx->id("CLKHFEN")); replace_port(ci, ctx->id("CLKHFPU"), packed.get(), ctx->id("CLKHFPU")); + for (int i = 0; i < 10; i++) { + auto port = ctx->id("TRIM" + std::to_string(i)); + replace_port(ci, port, packed.get(), port); + } if (bool_or_default(ci->attrs, ctx->id("ROUTE_THROUGH_FABRIC"))) { replace_port(ci, ctx->id("CLKHF"), packed.get(), ctx->id("CLKHF_FABRIC")); } else { @@ -1030,7 +1136,7 @@ static void pack_special(Context *ctx) replace_port(ci, ctx->id(pi.name.c_str(ctx)), packed.get(), ctx->id(newname)); } new_cells.push_back(std::move(packed)); - } else if (is_sb_rgba_drv(ctx, ci)) { + } else if (is_sb_rgba_drv(ctx, ci) || is_sb_rgb_drv(ctx, ci)) { /* Force placement (no choices anyway) */ cell_place_unique(ctx, ci); @@ -1042,21 +1148,44 @@ static void pack_special(Context *ctx) if (net == nullptr) continue; + if ((pi.name != ctx->id("RGB0")) && (pi.name != ctx->id("RGB1")) && (pi.name != ctx->id("RGB2"))) continue; if (net->users.size() > 0) - log_error("SB_RGBA_DRV port connected to more than just package pin !\n"); + log_error("SB_RGB_DRV/SB_RGBA_DRV port connected to more than just package pin !\n"); ctx->nets.erase(net->name); } + + if (is_sb_rgb_drv(ctx, ci) && !ci->ledInfo.ledCurConnected) + log_error("Port RGBPU of SB_RGB_DRV should be driven by port LEDPU of SB_LED_DRV_CUR!\n"); + + ci->ports.erase(ctx->id("RGBPU")); ci->ports.erase(ctx->id("RGB0")); ci->ports.erase(ctx->id("RGB1")); ci->ports.erase(ctx->id("RGB2")); } else if (is_sb_ledda_ip(ctx, ci)) { /* Force placement (no choices anyway) */ cell_place_unique(ctx, ci); - + } else if (is_sb_i2c(ctx, ci) || is_sb_spi(ctx, ci)) { + const std::map<std::tuple<IdString, std::string>, Loc> map_ba74 = { + {std::make_tuple(id_SB_SPI, "0b0000"), Loc(0, 0, 0)}, + {std::make_tuple(id_SB_I2C, "0b0001"), Loc(0, 31, 0)}, + {std::make_tuple(id_SB_SPI, "0b0010"), Loc(25, 0, 1)}, + {std::make_tuple(id_SB_I2C, "0b0011"), Loc(25, 31, 0)}, + }; + if (map_ba74.find(std::make_tuple(ci->type, ci->params[ctx->id("BUS_ADDR74")])) == map_ba74.end()) + log_error("Invalid value for BUS_ADDR74 for cell '%s' of type '%s'\n", ci->name.c_str(ctx), + ci->type.c_str(ctx)); + Loc bel_loc = map_ba74.at(std::make_tuple(ci->type, ci->params[ctx->id("BUS_ADDR74")])); + BelId bel = ctx->getBelByLocation(bel_loc); + if (bel == BelId() || ctx->getBelType(bel) != ci->type) + log_error("Unable to find placement for cell '%s' of type '%s'\n", ci->name.c_str(ctx), + ci->type.c_str(ctx)); + IdString bel_name = ctx->getBelName(bel); + ci->attrs[ctx->id("BEL")] = bel_name.str(ctx); + log_info(" constrained %s '%s' to %s\n", ci->type.c_str(ctx), ci->name.c_str(ctx), bel_name.c_str(ctx)); } else if (is_sb_pll40(ctx, ci)) { bool is_pad = is_sb_pll40_pad(ctx, ci); bool is_core = !is_pad; @@ -1259,10 +1388,20 @@ static void pack_special(Context *ctx) else continue; - std::unique_ptr<CellInfo> gb = - create_padin_gbuf(ctx, packed.get(), pi.name, - "$gbuf_" + ci->name.str(ctx) + "_pllout_" + (is_b_port ? "b" : "a")); - new_cells.push_back(std::move(gb)); + // Only if there is actually a net ... + if (pi.net != nullptr) { + // ... and it's used + if (pi.net->users.size() > 0) { + std::unique_ptr<CellInfo> gb = + create_padin_gbuf(ctx, packed.get(), pi.name, + "$gbuf_" + ci->name.str(ctx) + "_pllout_" + (is_b_port ? "b" : "a")); + new_cells.push_back(std::move(gb)); + } else { + // If not, remove it to avoid routing issues + ctx->nets.erase(pi.net->name); + packed->ports[pi.name].net = nullptr; + } + } } new_cells.push_back(std::move(packed)); diff --git a/ice40/pcf.cc b/ice40/pcf.cc index a8273dd6..15132800 100644 --- a/ice40/pcf.cc +++ b/ice40/pcf.cc @@ -77,8 +77,11 @@ bool apply_pcf(Context *ctx, std::string filename, std::istream &in) } args_end++; } - if (args_end >= words.size() - 1) + if (args_end > words.size() - 2) log_error("expected PCF syntax 'set_io cell pin' (on line %d)\n", lineno); + else if (args_end < words.size() - 2 && !nowarn) + log_warning("Ignoring trailing PCF settings (on line %d)\n", lineno); + std::string cell = words.at(args_end); std::string pin = words.at(args_end + 1); auto fnd_cell = ctx->cells.find(ctx->id(cell)); diff --git a/json/jsonparse.cc b/json/jsonparse.cc index 5f4df0a2..d463d8ce 100644 --- a/json/jsonparse.cc +++ b/json/jsonparse.cc @@ -285,7 +285,7 @@ void vcc_net(Context *ctx, NetInfo *net) // true, false otherwise bool is_blackbox(JsonNode *node) { - JsonNode *attr_node, *bbox_node; + JsonNode *attr_node, *bbox_node = nullptr, *wbox_node = nullptr; if (node->data_dict.count("attributes") == 0) return false; @@ -296,14 +296,19 @@ bool is_blackbox(JsonNode *node) return false; if (GetSize(attr_node->data_dict) == 0) return false; - if (attr_node->data_dict.count("blackbox") == 0) + if (attr_node->data_dict.count("blackbox")) + bbox_node = attr_node->data_dict.at("blackbox"); + if (attr_node->data_dict.count("whitebox")) + wbox_node = attr_node->data_dict.at("whitebox"); + if (bbox_node == NULL && wbox_node == NULL) return false; - bbox_node = attr_node->data_dict.at("blackbox"); - if (bbox_node == NULL) + if (bbox_node && bbox_node->type != 'N') + log_error("JSON module blackbox attribute value is not a number\n"); + if (bbox_node && bbox_node->data_number == 0) return false; - if (bbox_node->type != 'N') - log_error("JSON module blackbox is not a number\n"); - if (bbox_node->data_number == 0) + if (wbox_node && wbox_node->type != 'N') + log_error("JSON module whitebox attribute value is not a number\n"); + if (wbox_node && wbox_node->data_number == 0) return false; return true; } @@ -337,7 +342,7 @@ static int const_net_idx = 0; template <typename F> void json_import_ports(Context *ctx, const string &modname, const std::vector<IdString> &netnames, const string &obj_name, const string &port_name, JsonNode *dir_node, JsonNode *wire_group_node, - F visitor) + bool upto, int start_offset, F visitor) { // Examine a port of a cell or the design. For every bit of the port, // the connected net will be processed and `visitor` will be called @@ -406,8 +411,11 @@ void json_import_ports(Context *ctx, const string &modname, const std::vector<Id wire_node = wire_group_node->data_array[index]; // // Pick a name for this port + int ndx = index + start_offset; + if (upto) + ndx = start_offset + wire_group_node->data_array.size() - index - 1; if (is_bus) - this_port.name = ctx->id(port_info.name.str(ctx) + "[" + std::to_string(index) + "]"); + this_port.name = ctx->id(port_info.name.str(ctx) + "[" + std::to_string(ndx) + "]"); else this_port.name = port_info.name; this_port.type = port_info.type; @@ -584,7 +592,7 @@ void json_import_cell(Context *ctx, string modname, const std::vector<IdString> dir_node = pdir_node->data_dict.at(port_name); wire_group_node = connections->data_dict.at(port_name); - json_import_ports(ctx, modname, netnames, cell->name.str(ctx), port_name, dir_node, wire_group_node, + json_import_ports(ctx, modname, netnames, cell->name.str(ctx), port_name, dir_node, wire_group_node, false, 0, [&cell, ctx](PortType type, const std::string &name, NetInfo *net) { cell->ports[ctx->id(name)] = PortInfo{ctx->id(name), net, type}; PortRef pr; @@ -680,8 +688,20 @@ void json_import_toplevel_port(Context *ctx, const string &modname, const std::v { JsonNode *dir_node = node->data_dict.at("direction"); JsonNode *nets_node = node->data_dict.at("bits"); + bool upto = false; + int start_offset = 0; + if (node->data_dict.count("upto") != 0) { + JsonNode *val = node->data_dict.at("upto"); + if (val->type == 'N') + upto = val->data_number != 0; + } + if (node->data_dict.count("offset") != 0) { + JsonNode *val = node->data_dict.at("offset"); + if (val->type == 'N') + start_offset = val->data_number; + } json_import_ports( - ctx, modname, netnames, "Top Level IO", portname, dir_node, nets_node, + ctx, modname, netnames, "Top Level IO", portname, dir_node, nets_node, upto, start_offset, [ctx](PortType type, const std::string &name, NetInfo *net) { insert_iobuf(ctx, net, type, name); }); } @@ -692,11 +712,22 @@ void json_import(Context *ctx, string modname, JsonNode *node) log_info("Importing module %s\n", modname.c_str()); + JsonNode *ports_parent = nullptr; + if (node->data_dict.count("ports") > 0) + ports_parent = node->data_dict.at("ports"); + // Multiple labels might refer to the same net. For now we resolve conflicts thus: + // - (toplevel) ports are always preferred // - names with fewer $ are always prefered // - between equal $ counts, fewer .s are prefered // - ties are resolved alphabetically - auto prefer_netlabel = [](const std::string &a, const std::string &b) { + auto prefer_netlabel = [ports_parent](const std::string &a, const std::string &b) { + if (ports_parent != nullptr) { + if (ports_parent->data_dict.count(a)) + return true; + if (ports_parent->data_dict.count(b)) + return false; + } if (b.empty()) return true; long a_dollars = std::count(a.begin(), a.end(), '$'), b_dollars = std::count(b.begin(), b.end(), '$'); @@ -721,6 +752,18 @@ void json_import(Context *ctx, string modname, JsonNode *node) here = cell_parent->data_dict.at(cell_parent->data_dict_keys[nnid]); std::string basename = cell_parent->data_dict_keys[nnid]; + bool upto = false; + int start_offset = 0; + if (here->data_dict.count("upto") != 0) { + JsonNode *val = here->data_dict.at("upto"); + if (val->type == 'N') + upto = val->data_number != 0; + } + if (here->data_dict.count("offset") != 0) { + JsonNode *val = here->data_dict.at("offset"); + if (val->type == 'N') + start_offset = val->data_number; + } if (here->data_dict.count("bits")) { JsonNode *bits = here->data_dict.at("bits"); assert(bits->type == 'A'); @@ -729,8 +772,11 @@ void json_import(Context *ctx, string modname, JsonNode *node) int netid = bits->data_array.at(i)->data_number; if (netid >= int(netlabels.size())) netlabels.resize(netid + 1); + int ndx = i + start_offset; + if (upto) + ndx = start_offset + num_bits - i - 1; std::string name = - basename + (num_bits == 1 ? "" : std::string("[") + std::to_string(i) + std::string("]")); + basename + (num_bits == 1 ? "" : std::string("[") + std::to_string(ndx) + std::string("]")); if (prefer_netlabel(name, netlabels.at(netid))) netlabels.at(netid) = name; } @@ -753,16 +799,29 @@ void json_import(Context *ctx, string modname, JsonNode *node) } } - if (node->data_dict.count("ports")) { - JsonNode *ports_parent = node->data_dict.at("ports"); - + if (ports_parent != nullptr) { // N.B. ports must be imported after cells for tristate behaviour // to be correct - // Loop through all ports + // Loop through all ports, first non-tristate then tristate to handle + // interconnected ports correctly for (int portid = 0; portid < GetSize(ports_parent->data_dict_keys); portid++) { JsonNode *here; here = ports_parent->data_dict.at(ports_parent->data_dict_keys[portid]); + JsonNode *dir_node = here->data_dict.at("direction"); + NPNR_ASSERT(dir_node->type == 'S'); + if (dir_node->data_string == "inout") + continue; + json_import_toplevel_port(ctx, modname, netids, ports_parent->data_dict_keys[portid], here); + } + for (int portid = 0; portid < GetSize(ports_parent->data_dict_keys); portid++) { + JsonNode *here; + + here = ports_parent->data_dict.at(ports_parent->data_dict_keys[portid]); + JsonNode *dir_node = here->data_dict.at("direction"); + NPNR_ASSERT(dir_node->type == 'S'); + if (dir_node->data_string != "inout") + continue; json_import_toplevel_port(ctx, modname, netids, ports_parent->data_dict_keys[portid], here); } } diff --git a/tests b/tests -Subproject ee3ff3c4bdce20c47bd6c35a2f7430497b28380 +Subproject 5182fd4bec49a568cc3fa37d62d9f9a82f28091 |