From 40df4f4f655347dadbebf8cd2eab6f37cdf630e9 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Wed, 17 Feb 2021 18:08:26 -0800 Subject: Add initial constant network support to FPGA interchange arch. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- fpga_interchange/arch.cc | 2 +- fpga_interchange/arch.h | 52 ++++++++++++++++++++++++++++++++++++++++++------ 2 files changed, 47 insertions(+), 7 deletions(-) diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc index 9bcd7f79..b1d5090a 100644 --- a/fpga_interchange/arch.cc +++ b/fpga_interchange/arch.cc @@ -217,7 +217,7 @@ void Arch::setup_byname() const for (int i = 0; i < chip_info->tiles.ssize(); i++) { auto &tile = chip_info->tiles[i]; auto &tile_type = chip_info->tile_types[tile.type]; - for (int j = 0; j < tile_type.number_sites; j++) { + for (int j = 0; j < tile_type.site_types.size(); j++) { auto &site = chip_info->sites[tile.sites[j]]; site_by_name[id(site.name.get())] = std::make_pair(i, j); } diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h index 1118a96b..541a85ec 100644 --- a/fpga_interchange/arch.h +++ b/fpga_interchange/arch.h @@ -120,8 +120,6 @@ NPNR_PACKED_STRUCT(struct ConstraintTagPOD { NPNR_PACKED_STRUCT(struct TileTypeInfoPOD { int32_t name; // Tile type constid - int32_t number_sites; - RelSlice bel_data; RelSlice wire_data; @@ -129,6 +127,8 @@ NPNR_PACKED_STRUCT(struct TileTypeInfoPOD { RelSlice pip_data; RelSlice tags; + + RelSlice site_types; }); NPNR_PACKED_STRUCT(struct SiteInstInfoPOD { @@ -147,7 +147,7 @@ NPNR_PACKED_STRUCT(struct TileInstInfoPOD { // Index into root.tile_types. int32_t type; - // This array is root.tile_types[type].number_sites long. + // This array is root.tile_types[type].site_types.size() long. // Index into root.sites RelSlice sites; @@ -207,6 +207,29 @@ NPNR_PACKED_STRUCT(struct PackagePOD { RelSlice pins; }); +NPNR_PACKED_STRUCT(struct ConstantsPOD { + // Cell type and port for the GND and VCC global source. + int32_t gnd_cell_name; // constid + int32_t gnd_cell_port; // constid + + int32_t vcc_cell_name; // constid + int32_t vcc_cell_port; // constid + + int32_t gnd_bel_tile; + int32_t gnd_bel_index; + int32_t gnd_bel_pin; // constid + + int32_t vcc_bel_tile; + int32_t vcc_bel_index; + int32_t vcc_bel_pin; // constid + + // Name to use for the global GND constant net + int32_t gnd_net_name; // constid + + // Name to use for the global VCC constant net + int32_t vcc_net_name; // constid +}); + NPNR_PACKED_STRUCT(struct ChipInfoPOD { RelPtr name; RelPtr generator; @@ -224,6 +247,7 @@ NPNR_PACKED_STRUCT(struct ChipInfoPOD { RelSlice bel_buckets; RelPtr cell_map; + RelPtr constants; // Constid string data. RelPtr>> constids; @@ -822,7 +846,7 @@ struct Arch : ArchAPI } int getTilePipDimZ(int x, int y) const override { - return chip_info->tile_types[chip_info->tiles[get_tile_index(x, y)].type].number_sites; + return chip_info->tile_types[chip_info->tiles[get_tile_index(x, y)].type].site_types.size(); } char getNameDelimiter() const override { return '/'; } @@ -855,8 +879,8 @@ struct Arch : ArchAPI result.first->second.boundcells.resize(tile_type.bel_data.size()); result.first->second.tags.resize(default_tags.size()); - result.first->second.sites.reserve(tile_type.number_sites); - for (size_t i = 0; i < (size_t)tile_type.number_sites; ++i) { + result.first->second.sites.reserve(tile_type.site_types.size()); + for (size_t i = 0; i < tile_type.site_types.size(); ++i) { result.first->second.sites.push_back(SiteRouter(i)); } } @@ -874,6 +898,22 @@ struct Arch : ArchAPI return tile_status.sites.at(bel_data.site); } + BelId get_vcc_bel() const { + auto &constants = chip_info->constants; + BelId bel; + bel.tile = constants->vcc_bel_tile; + bel.index = constants->vcc_bel_pin; + return bel; + } + + BelId get_gnd_bel() const { + auto &constants = chip_info->constants; + BelId bel; + bel.tile = constants->gnd_bel_tile; + bel.index = constants->gnd_bel_pin; + return bel; + } + void bindBel(BelId bel, CellInfo *cell, PlaceStrength strength) override { NPNR_ASSERT(bel != BelId()); -- cgit v1.2.3 From 761d9d9229f9c1aa5420a12c5d3e4c2aab53bb11 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Wed, 17 Feb 2021 18:08:52 -0800 Subject: Correct some bugs in the create_bba Makefile. Also add debug_test target to debug archcheck. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- fpga_interchange/examples/create_bba/Makefile | 12 +++++++++--- 1 file changed, 9 insertions(+), 3 deletions(-) diff --git a/fpga_interchange/examples/create_bba/Makefile b/fpga_interchange/examples/create_bba/Makefile index 3033daca..ffbc3103 100644 --- a/fpga_interchange/examples/create_bba/Makefile +++ b/fpga_interchange/examples/create_bba/Makefile @@ -30,7 +30,7 @@ include ../common.mk .DELETE_ON_ERROR: -.PHONY: all chipdb +.PHONY: all chipdb test debug_test all: chipdb @@ -66,7 +66,7 @@ $(NEXTPNR_PATH)/build/bba/bbasm: | $(NEXTPNR_PATH)/build cd $(NEXTPNR_PATH)/build && cmake -DARCH=fpga_interchange .. make -j -C $(NEXTPNR_PATH)/build -$(NEXTPNR_PATH)/fpga_interchange/chipdb.bba: build/.setup +build/nextpnr/fpga_interchange/chipdb.bba: build/.setup mkdir -p build/nextpnr/fpga_interchange source build/env/bin/activate && \ cd build/python-fpga-interchange/ && \ @@ -76,7 +76,7 @@ $(NEXTPNR_PATH)/fpga_interchange/chipdb.bba: build/.setup RAPIDWRIGHT_PATH=$(RAPIDWRIGHT_PATH) \ INTERCHANGE_PATH=$(INTERCHANGE_PATH) -$(BBA_PATH): $(NEXTPNR_PATH)/build/bba/bbasm $(NEXTPNR_PATH)/fpga_interchange/chipdb.bba +$(BBA_PATH): $(NEXTPNR_PATH)/build/bba/bbasm build/nextpnr/fpga_interchange/chipdb.bba $(NEXTPNR_PATH)/build/bba/bbasm -l build/nextpnr/fpga_interchange/chipdb.bba $(BBA_PATH) chipdb: $(BBA_PATH) @@ -87,5 +87,11 @@ test: chipdb --package csg324 \ --test +debug_test: chipdb + gdb --args $(NEXTPNR_PATH)/build/nextpnr-fpga_interchange \ + --chipdb $(BBA_PATH) \ + --package csg324 \ + --test + clean: rm -rf build -- cgit v1.2.3 From 3e5a23ed5b25570c33669dfd8bdd226016968bb5 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Wed, 17 Feb 2021 18:34:32 -0800 Subject: Add tests to confirm constant routing import. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- fpga_interchange/examples/archcheck/Makefile | 7 +++ fpga_interchange/examples/archcheck/test_data.yaml | 29 ++++++++++++ python/check_arch_api.py | 51 ++++++++++++++++++---- 3 files changed, 78 insertions(+), 9 deletions(-) diff --git a/fpga_interchange/examples/archcheck/Makefile b/fpga_interchange/examples/archcheck/Makefile index cf82013b..02e1c08e 100644 --- a/fpga_interchange/examples/archcheck/Makefile +++ b/fpga_interchange/examples/archcheck/Makefile @@ -13,4 +13,11 @@ check: check_test_data check_test_data: $(NEXTPNR_BIN) \ --chipdb $(BBA_PATH) \ + --package $(PACKAGE) \ + --run $(NEXTPNR_PATH)/python/check_arch_api.py + +debug_check_test_data: + gdb --args $(NEXTPNR_BIN) \ + --chipdb $(BBA_PATH) \ + --package $(PACKAGE) \ --run $(NEXTPNR_PATH)/python/check_arch_api.py diff --git a/fpga_interchange/examples/archcheck/test_data.yaml b/fpga_interchange/examples/archcheck/test_data.yaml index b41112cf..268d180a 100644 --- a/fpga_interchange/examples/archcheck/test_data.yaml +++ b/fpga_interchange/examples/archcheck/test_data.yaml @@ -1,7 +1,36 @@ pip_test: - src_wire: CLBLM_R_X11Y93/CLBLM_L_D3 dst_wire: SLICE_X15Y93.SLICEL/D3 +pip_chain_test: + - wires: + - $CONSTANTS_X0Y0.$CONSTANTS/$GND_SOURCE + - $CONSTANTS_X0Y0/$GND_NODE + - TIEOFF_X3Y145.TIEOFF/$GND_SITE_WIRE + - TIEOFF_X3Y145.TIEOFF/HARD0GND_HARD0 + - INT_R_X3Y145/GND_WIRE + - wires: + - $CONSTANTS_X0Y0.$CONSTANTS/$VCC_SOURCE + - $CONSTANTS_X0Y0/$VCC_NODE + - TIEOFF_X3Y145.TIEOFF/$VCC_SITE_WIRE + - TIEOFF_X3Y145.TIEOFF/HARD1VCC_HARD1 + - INT_R_X3Y145/VCC_WIRE + - wires: + - $CONSTANTS_X0Y0.$CONSTANTS/$VCC_SOURCE + - $CONSTANTS_X0Y0/$VCC_NODE + - SLICE_X3Y145.SLICEL/$VCC_SITE_WIRE + - SLICE_X3Y145.SLICEL/CEUSEDVCC_HARD1 + - wires: + - $CONSTANTS_X0Y0.$CONSTANTS/$GND_SOURCE + - $CONSTANTS_X0Y0/$GND_NODE + - SLICE_X3Y145.SLICEL/$GND_SITE_WIRE + - SLICE_X3Y145.SLICEL/SRUSEDGND_HARD0 bel_pin_test: - bel: SLICE_X15Y93.SLICEL/D6LUT pin: A3 wire: SLICE_X15Y93.SLICEL/D3 + - bel: $CONSTANTS_X0Y0.$CONSTANTS/GND + pin: G + wire: $CONSTANTS_X0Y0.$CONSTANTS/$GND_SOURCE + - bel: $CONSTANTS_X0Y0.$CONSTANTS/VCC + pin: P + wire: $CONSTANTS_X0Y0.$CONSTANTS/$VCC_SOURCE diff --git a/python/check_arch_api.py b/python/check_arch_api.py index 647faefc..166f1fd3 100644 --- a/python/check_arch_api.py +++ b/python/check_arch_api.py @@ -18,6 +18,11 @@ pin connectivity tests. Example test_data.yaml: pip_test: - src_wire: CLBLM_R_X11Y93/CLBLM_L_D3 dst_wire: SLICE_X15Y93.SLICEL/D3 +pip_chain_test: + - wires: + - $CONSTANTS_X0Y0.$CONSTANTS/$GND_SOURCE + - $CONSTANTS_X0Y0/$GND_NODE + - TIEOFF_X3Y145.TIEOFF/$GND_SITE_WIRE bel_pin_test: - bel: SLICE_X15Y93.SLICEL/D6LUT pin: A3 @@ -25,25 +30,48 @@ bel_pin_test: """ import yaml +import sys + + def check_arch_api(ctx): + success = True pips_tested = 0 + pips_failed = 0 + + def test_pip(src_wire_name, dst_wire_name): + nonlocal success + nonlocal pips_tested + nonlocal pips_failed + + pip = None + for pip_name in ctx.getPipsDownhill(src_wire_name): + if ctx.getPipDstWire(pip_name) == dst_wire_name: + pip = pip_name + src_wire = ctx.getPipSrcWire(pip_name) + assert src_wire == src_wire_name, ( + src_wire, src_wire_name) + + + if pip is None: + success = False + pips_failed += 1 + print('Pip from {} to {} failed'.format(src_wire_name, dst_wire_name)) + else: + pips_tested += 1 bel_pins_tested = 0 with open('test_data.yaml', 'r') as f: test_data = yaml.safe_load(f.read()) if 'pip_test' in test_data: for pip_test in test_data['pip_test']: - pip = None - for pip_name in ctx.getPipsDownhill(pip_test['src_wire']): - if ctx.getPipDstWire(pip_name) == pip_test['dst_wire']: - pip = pip_name - src_wire = ctx.getPipSrcWire(pip_name) - assert src_wire == pip_test['src_wire'], ( - src_wire, pip_test['src_wire']) + test_pip(pip_test['src_wire'], pip_test['dst_wire']) - assert pip is not None - pips_tested += 1 + if 'pip_chain_test' in test_data: + for chain_test in test_data['pip_chain_test']: + wires = chain_test['wires'] + for src_wire, dst_wire in zip(wires, wires[1:]): + test_pip(src_wire, dst_wire) if 'bel_pin_test' in test_data: for bel_pin_test in test_data['bel_pin_test']: @@ -54,4 +82,9 @@ def check_arch_api(ctx): print('Tested {} pips and {} bel pins'.format(pips_tested, bel_pins_tested)) + if not success: + print('{} pips failed'.format(pips_failed)) + sys.exit(-1) + + check_arch_api(ctx) -- cgit v1.2.3 From cf554f9338db84fa0d12afd83e10f7791e62efa1 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Thu, 18 Feb 2021 16:51:05 -0800 Subject: Add constant network test case. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- fpga_interchange/examples/const_wire/Makefile | 8 ++++++++ fpga_interchange/examples/const_wire/run.tcl | 14 ++++++++++++++ fpga_interchange/examples/const_wire/wire.v | 6 ++++++ fpga_interchange/examples/const_wire/wire.xdc | 5 +++++ fpga_interchange/examples/template.mk | 9 +++++++++ 5 files changed, 42 insertions(+) create mode 100644 fpga_interchange/examples/const_wire/Makefile create mode 100644 fpga_interchange/examples/const_wire/run.tcl create mode 100644 fpga_interchange/examples/const_wire/wire.v create mode 100644 fpga_interchange/examples/const_wire/wire.xdc diff --git a/fpga_interchange/examples/const_wire/Makefile b/fpga_interchange/examples/const_wire/Makefile new file mode 100644 index 00000000..49194f53 --- /dev/null +++ b/fpga_interchange/examples/const_wire/Makefile @@ -0,0 +1,8 @@ +DESIGN := wire +DESIGN_TOP := top +PACKAGE := csg324 + +include ../template.mk + +build/wire.json: wire.v | build + yosys -c run.tcl diff --git a/fpga_interchange/examples/const_wire/run.tcl b/fpga_interchange/examples/const_wire/run.tcl new file mode 100644 index 00000000..9127be20 --- /dev/null +++ b/fpga_interchange/examples/const_wire/run.tcl @@ -0,0 +1,14 @@ +yosys -import + +read_verilog wire.v + +synth_xilinx -nolutram -nowidelut -nosrl -nocarry -nodsp + +# opt_expr -undriven makes sure all nets are driven, if only by the $undef +# net. +opt_expr -undriven +opt_clean + +setundef -zero -params + +write_json build/wire.json diff --git a/fpga_interchange/examples/const_wire/wire.v b/fpga_interchange/examples/const_wire/wire.v new file mode 100644 index 00000000..7905c92e --- /dev/null +++ b/fpga_interchange/examples/const_wire/wire.v @@ -0,0 +1,6 @@ +module top(output o, output o2); + +assign o = 1'b0; +assign o2 = 1'b1; + +endmodule diff --git a/fpga_interchange/examples/const_wire/wire.xdc b/fpga_interchange/examples/const_wire/wire.xdc new file mode 100644 index 00000000..beab748e --- /dev/null +++ b/fpga_interchange/examples/const_wire/wire.xdc @@ -0,0 +1,5 @@ +set_property PACKAGE_PIN N15 [get_ports o] +set_property PACKAGE_PIN N16 [get_ports o2] + +set_property IOSTANDARD LVCMOS33 [get_ports o] +set_property IOSTANDARD LVCMOS33 [get_ports o2] diff --git a/fpga_interchange/examples/template.mk b/fpga_interchange/examples/template.mk index 819cdb1f..d12a4e11 100644 --- a/fpga_interchange/examples/template.mk +++ b/fpga_interchange/examples/template.mk @@ -46,6 +46,15 @@ build/$(DESIGN)_phys.yaml: build/$(DESIGN).phys phys_yaml: build/$(DESIGN)_phys.yaml +verbose: build/$(DESIGN).netlist + $(NEXTPNR_BIN) \ + --chipdb $(BBA_PATH) \ + --xdc $(DESIGN).xdc \ + --netlist build/$(DESIGN).netlist \ + --phys build/$(DESIGN).phys \ + --package $(PACKAGE) \ + --verbose + debug: build/$(DESIGN).netlist gdb --args $(NEXTPNR_BIN) \ --chipdb $(BBA_PATH) \ -- cgit v1.2.3 From 15459cae91276f956d2a4734f42162d6afaf1128 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Thu, 18 Feb 2021 16:51:36 -0800 Subject: Initial working constant network support! Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- fpga_interchange/arch.h | 36 +++++++- fpga_interchange/examples/const_wire/wire.v | 4 +- fpga_interchange/examples/const_wire/wire.xdc | 4 + fpga_interchange/fpga_interchange.cpp | 115 ++++++++++++++++++++++++-- 4 files changed, 145 insertions(+), 14 deletions(-) diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h index 541a85ec..0248bf24 100644 --- a/fpga_interchange/arch.h +++ b/fpga_interchange/arch.h @@ -67,7 +67,7 @@ NPNR_PACKED_STRUCT(struct BelInfoPOD { int16_t site; int16_t site_variant; // some sites have alternative types int16_t category; - int16_t padding; + int16_t synthetic; RelPtr pin_map; // Index into CellMapPOD::cell_bel_map }); @@ -128,7 +128,7 @@ NPNR_PACKED_STRUCT(struct TileTypeInfoPOD { RelSlice tags; - RelSlice site_types; + RelSlice site_types; // constid }); NPNR_PACKED_STRUCT(struct SiteInstInfoPOD { @@ -902,7 +902,7 @@ struct Arch : ArchAPI auto &constants = chip_info->constants; BelId bel; bel.tile = constants->vcc_bel_tile; - bel.index = constants->vcc_bel_pin; + bel.index = constants->vcc_bel_index; return bel; } @@ -910,7 +910,7 @@ struct Arch : ArchAPI auto &constants = chip_info->constants; BelId bel; bel.tile = constants->gnd_bel_tile; - bel.index = constants->gnd_bel_pin; + bel.index = constants->gnd_bel_index; return bel; } @@ -1682,6 +1682,34 @@ struct Arch : ArchAPI auto &pip_data = pip_info(chip_info, pip); return site_inst_info(chip_info, pip.tile, pip_data.site); } + + // Is this bel synthetic (e.g. added during import process)? + // + // This is generally used for constant networks, but can also be used for + // static partitions. + bool is_bel_synthetic(BelId bel) const + { + const BelInfoPOD & bel_data = bel_info(chip_info, bel); + + return bel_data.synthetic != 0; + } + + // Is this pip synthetic (e.g. added during import process)? + // + // This is generally used for constant networks, but can also be used for + // static partitions. + bool is_pip_synthetic(PipId pip) const + { + auto &pip_data = pip_info(chip_info, pip); + if(pip_data.site == -1) { + return pip_data.extra_data == -1; + } else { + BelId bel; + bel.tile = pip.tile; + bel.index = pip_data.bel; + return is_bel_synthetic(bel); + } + } }; NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/examples/const_wire/wire.v b/fpga_interchange/examples/const_wire/wire.v index 7905c92e..5b1ab692 100644 --- a/fpga_interchange/examples/const_wire/wire.v +++ b/fpga_interchange/examples/const_wire/wire.v @@ -1,6 +1,8 @@ -module top(output o, output o2); +module top(output o, output o2, output o3, output o4); assign o = 1'b0; assign o2 = 1'b1; +assign o3 = 1'b0; +assign o4 = 1'b1; endmodule diff --git a/fpga_interchange/examples/const_wire/wire.xdc b/fpga_interchange/examples/const_wire/wire.xdc index beab748e..0d96fc45 100644 --- a/fpga_interchange/examples/const_wire/wire.xdc +++ b/fpga_interchange/examples/const_wire/wire.xdc @@ -1,5 +1,9 @@ set_property PACKAGE_PIN N15 [get_ports o] set_property PACKAGE_PIN N16 [get_ports o2] +set_property PACKAGE_PIN P17 [get_ports o3] +set_property PACKAGE_PIN R17 [get_ports o4] set_property IOSTANDARD LVCMOS33 [get_ports o] set_property IOSTANDARD LVCMOS33 [get_ports o2] +set_property IOSTANDARD LVCMOS33 [get_ports o3] +set_property IOSTANDARD LVCMOS33 [get_ports o4] diff --git a/fpga_interchange/fpga_interchange.cpp b/fpga_interchange/fpga_interchange.cpp index 566524b6..ad1dd76d 100644 --- a/fpga_interchange/fpga_interchange.cpp +++ b/fpga_interchange/fpga_interchange.cpp @@ -62,6 +62,10 @@ static PhysicalNetlist::PhysNetlist::RouteBranch::Builder emit_branch( const std::unordered_map &pip_place_strength, PipId pip, PhysicalNetlist::PhysNetlist::RouteBranch::Builder branch) { + if(ctx->is_pip_synthetic(pip)) { + log_error("FPGA interchange should not emit synthetic pip %s\n", ctx->nameOfPip(pip)); + } + const PipInfoPOD & pip_data = pip_info(ctx->chip_info, pip); const TileTypeInfoPOD & tile_type = loc_info(ctx->chip_info, pip); const TileInstInfoPOD & tile = ctx->chip_info->tiles[pip.tile]; @@ -185,6 +189,11 @@ static void init_bel_pin( StringEnumerator * strings, const BelPin &bel_pin, PhysicalNetlist::PhysNetlist::RouteBranch::Builder branch) { + if(ctx->is_bel_synthetic(bel_pin.bel)) { + log_error("FPGA interchange should not emit synthetic BEL pin %s/%s\n", + ctx->nameOfBel(bel_pin.bel), bel_pin.pin.c_str(ctx)); + } + BelId bel = bel_pin.bel; IdString pin_name = bel_pin.pin; @@ -248,6 +257,35 @@ static void emit_net( } } } +static void find_non_synthetic_edges(const Context * ctx, WireId root_wire, + const std::unordered_map> &pip_downhill, + std::vector *root_pips) { + std::vector wires_to_expand; + + wires_to_expand.push_back(root_wire); + while(!wires_to_expand.empty()) { + WireId wire = wires_to_expand.back(); + wires_to_expand.pop_back(); + + auto downhill_iter = pip_downhill.find(wire); + if(downhill_iter == pip_downhill.end()) { + log_warning("Wire %s never entered the real fabric?\n", + ctx->nameOfWire(wire)); + continue; + } + + for(PipId pip : pip_downhill.at(wire)) { + if(!ctx->is_pip_synthetic(pip)) { + // Stop following edges that are non-synthetic, they will be + // followed during emit_net + root_pips->push_back(pip); + } else { + // Continue to follow synthetic edges. + wires_to_expand.push_back(ctx->getPipDstWire(pip)); + } + } + } +} void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::string &filename) { ::capnp::MallocMessageBuilder message; @@ -272,9 +310,15 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str size_t number_placements = 0; for(auto & cell_name : placed_cells) { const CellInfo & cell = *ctx->cells.at(cell_name); - if(!ctx->io_port_types.count(cell.type)) { - number_placements += 1; + + if(ctx->io_port_types.count(cell.type)) { + continue; + } + if(ctx->is_bel_synthetic(cell.bel)) { + continue; } + + number_placements += 1; } std::unordered_map sites; @@ -286,6 +330,9 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str if(ctx->io_port_types.count(cell.type)) { continue; } + if(ctx->is_bel_synthetic(cell.bel)) { + continue; + } IdStringList bel_name = ctx->getBelName(cell.bel); NPNR_ASSERT(bel_name.size() == 2); @@ -339,16 +386,27 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str auto &net = *net_pair.second; auto net_out = *net_iter++; - net_out.setName(strings.get_index(net.name.str(ctx))); + const CellInfo *driver_cell = net.driver.cell; - // FIXME: Mark net as signal/vcc/gnd. - // - // Also vcc/gnd nets needs to get special handling through inverters. + // Handle GND and VCC nets. + if(driver_cell->bel == ctx->get_gnd_bel()) { + IdString gnd_net_name(ctx->chip_info->constants->gnd_net_name); + net_out.setName(strings.get_index(gnd_net_name.str(ctx))); + net_out.setType(PhysicalNetlist::PhysNetlist::NetType::GND); + } else if(driver_cell->bel == ctx->get_vcc_bel()) { + IdString vcc_net_name(ctx->chip_info->constants->vcc_net_name); + net_out.setName(strings.get_index(vcc_net_name.str(ctx))); + net_out.setType(PhysicalNetlist::PhysNetlist::NetType::VCC); + } else { + net_out.setName(strings.get_index(net.name.str(ctx))); + } + + // FIXME: Also vcc/gnd nets needs to get special handling through + // inverters. std::unordered_map root_wires; std::unordered_map> pip_downhill; std::unordered_set pips; - const CellInfo *driver_cell = net.driver.cell; if (driver_cell != nullptr && driver_cell->bel != BelId()) { for(IdString bel_pin_name : driver_cell->cell_bel_pins.at(net.driver.port)) { BelPin driver_bel_pin; @@ -397,7 +455,27 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str } } - auto sources = net_out.initSources(root_wires.size()); + std::vector root_pips; + std::vector roots_to_remove; + + for(const auto & root_pair : root_wires) { + WireId root_wire = root_pair.first; + BelPin src_bel_pin = root_pair.second; + + if(!ctx->is_bel_synthetic(src_bel_pin.bel)) { + continue; + } + + roots_to_remove.push_back(root_wire); + find_non_synthetic_edges(ctx, root_wire, pip_downhill, &root_pips); + } + + // Remove wires that have a synthetic root. + for(WireId wire : roots_to_remove) { + NPNR_ASSERT(root_wires.erase(wire) == 1); + } + + auto sources = net_out.initSources(root_wires.size() + root_pips.size()); auto source_iter = sources.begin(); for(const auto & root_pair : root_wires) { @@ -410,11 +488,30 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str emit_net(ctx, &strings, pip_downhill, sinks, &pips, pip_place_strength, root_wire, source_branch); } + for(const PipId root : root_pips) { + PhysicalNetlist::PhysNetlist::RouteBranch::Builder source_branch = *source_iter++; + + NPNR_ASSERT(pips.erase(root) == 1); + WireId root_wire = ctx->getPipDstWire(root); + source_branch = emit_branch(ctx, &strings, pip_place_strength, root, source_branch); + emit_net(ctx, &strings, pip_downhill, sinks, &pips, pip_place_strength, root_wire, source_branch); + } + // Any pips that were not part of a tree starting from the source are // stubs. - auto stubs = net_out.initStubs(pips.size()); + size_t real_pips = 0; + for(PipId pip : pips) { + if(ctx->is_pip_synthetic(pip)) { + continue; + } + real_pips += 1; + } + auto stubs = net_out.initStubs(real_pips); auto stub_iter = stubs.begin(); for(PipId pip : pips) { + if(ctx->is_pip_synthetic(pip)) { + continue; + } emit_branch(ctx, &strings, pip_place_strength, pip, *stub_iter++); } } -- cgit v1.2.3 From 3ccb164f2aa23a03f1910f891da93f74a6d04a1b Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Thu, 18 Feb 2021 16:57:09 -0800 Subject: Run "make clangformat". Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- fpga_interchange/arch.h | 14 ++++++++------ 1 file changed, 8 insertions(+), 6 deletions(-) diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h index 0248bf24..76ad7e00 100644 --- a/fpga_interchange/arch.h +++ b/fpga_interchange/arch.h @@ -217,11 +217,11 @@ NPNR_PACKED_STRUCT(struct ConstantsPOD { int32_t gnd_bel_tile; int32_t gnd_bel_index; - int32_t gnd_bel_pin; // constid + int32_t gnd_bel_pin; // constid int32_t vcc_bel_tile; int32_t vcc_bel_index; - int32_t vcc_bel_pin; // constid + int32_t vcc_bel_pin; // constid // Name to use for the global GND constant net int32_t gnd_net_name; // constid @@ -898,7 +898,8 @@ struct Arch : ArchAPI return tile_status.sites.at(bel_data.site); } - BelId get_vcc_bel() const { + BelId get_vcc_bel() const + { auto &constants = chip_info->constants; BelId bel; bel.tile = constants->vcc_bel_tile; @@ -906,7 +907,8 @@ struct Arch : ArchAPI return bel; } - BelId get_gnd_bel() const { + BelId get_gnd_bel() const + { auto &constants = chip_info->constants; BelId bel; bel.tile = constants->gnd_bel_tile; @@ -1689,7 +1691,7 @@ struct Arch : ArchAPI // static partitions. bool is_bel_synthetic(BelId bel) const { - const BelInfoPOD & bel_data = bel_info(chip_info, bel); + const BelInfoPOD &bel_data = bel_info(chip_info, bel); return bel_data.synthetic != 0; } @@ -1701,7 +1703,7 @@ struct Arch : ArchAPI bool is_pip_synthetic(PipId pip) const { auto &pip_data = pip_info(chip_info, pip); - if(pip_data.site == -1) { + if (pip_data.site == -1) { return pip_data.extra_data == -1; } else { BelId bel; -- cgit v1.2.3 From 46b38f8a403e071d2d9f2bf50e08ef0e0463d845 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Thu, 18 Feb 2021 19:03:05 -0800 Subject: Fix reference copy. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- fpga_interchange/arch.h | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h index 76ad7e00..a5352b60 100644 --- a/fpga_interchange/arch.h +++ b/fpga_interchange/arch.h @@ -900,19 +900,19 @@ struct Arch : ArchAPI BelId get_vcc_bel() const { - auto &constants = chip_info->constants; + auto &constants = *chip_info->constants; BelId bel; - bel.tile = constants->vcc_bel_tile; - bel.index = constants->vcc_bel_index; + bel.tile = constants.vcc_bel_tile; + bel.index = constants.vcc_bel_index; return bel; } BelId get_gnd_bel() const { - auto &constants = chip_info->constants; + auto &constants = *chip_info->constants; BelId bel; - bel.tile = constants->gnd_bel_tile; - bel.index = constants->gnd_bel_index; + bel.tile = constants.gnd_bel_tile; + bel.index = constants.gnd_bel_index; return bel; } -- cgit v1.2.3 From 5c6e23141289377dbc6ce9d799b0b92ed6234a19 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Fri, 19 Feb 2021 09:44:14 -0800 Subject: Remove some signedness warnings. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- common/exclusive_state_groups.h | 4 ++-- common/exclusive_state_groups.impl.h | 15 +++++++-------- fpga_interchange/arch.cc | 2 +- 3 files changed, 10 insertions(+), 11 deletions(-) diff --git a/common/exclusive_state_groups.h b/common/exclusive_state_groups.h index c9b0df66..f2dcb858 100644 --- a/common/exclusive_state_groups.h +++ b/common/exclusive_state_groups.h @@ -69,7 +69,7 @@ template = 0 && (size_t)next_state < StateCount); // Increment and mark the state as selected. count[next_state] += 1; @@ -92,7 +92,7 @@ template = 0 && (size_t)next_state < StateCount); NPNR_ASSERT(selected_states[next_state]); count[next_state] -= 1; diff --git a/common/exclusive_state_groups.impl.h b/common/exclusive_state_groups.impl.h index 864e16c6..9946e9a6 100644 --- a/common/exclusive_state_groups.impl.h +++ b/common/exclusive_state_groups.impl.h @@ -40,14 +40,14 @@ void ExclusiveStateGroup::print_debug(const Co log_info("%s.%s is currently unselected\n", object.c_str(ctx), definition.prefix.c_str(ctx)); } else if (state >= 0) { log_info("%s.%s = %s, count = %d\n", object.c_str(ctx), definition.prefix.c_str(ctx), - definition.states[state].c_str(ctx), count[state]); + definition.states.at(state).c_str(ctx), count[state]); } else { NPNR_ASSERT(state == kOverConstrained); log_info("%s.%s is currently overconstrained, states selected:\n", object.c_str(ctx), definition.prefix.c_str(ctx)); for (size_t i = 0; i < definition.states.size(); ++i) { if (selected_states[i]) { - log_info(" - %s, count = %d\n", definition.states[i].c_str(ctx), count[i]); + log_info(" - %s, count = %d\n", definition.states.at(i).c_str(ctx), count[i]); } } } @@ -62,9 +62,9 @@ void ExclusiveStateGroup::explain_implies(cons log_info("Placing cell %s at bel %s does not violate %s.%s\n", cell.c_str(ctx), ctx->nameOfBel(bel), object.c_str(ctx), definition.prefix.c_str(ctx)); } else { - NPNR_ASSERT(next_state < definition.states.size()); - log_info("Placing cell %s at bel %s does violates %s.%s.\n", cell.c_str(ctx), ctx->nameOfBel(bel), - object.c_str(ctx), definition.prefix.c_str(ctx)); + log_info("Placing cell %s at bel %s does violates %s.%s, desired state = %s.\n", cell.c_str(ctx), + ctx->nameOfBel(bel), object.c_str(ctx), definition.prefix.c_str(ctx), + definition.states.at(next_state).c_str(ctx)); print_debug(ctx, object, definition); } } @@ -83,11 +83,10 @@ void ExclusiveStateGroup::explain_requires(con log_info("Placing cell %s at bel %s does violates %s.%s, because current state is %s, constraint requires one " "of:\n", cell.c_str(ctx), ctx->nameOfBel(bel), object.c_str(ctx), definition.prefix.c_str(ctx), - definition.states[state].c_str(ctx)); + definition.states.at(state).c_str(ctx)); for (const auto required_state : state_range) { - NPNR_ASSERT(required_state < definition.states.size()); - log_info(" - %s\n", definition.states[required_state].c_str(ctx)); + log_info(" - %s\n", definition.states.at(required_state).c_str(ctx)); } print_debug(ctx, object, definition); } diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc index b1d5090a..4cffd6ca 100644 --- a/fpga_interchange/arch.cc +++ b/fpga_interchange/arch.cc @@ -217,7 +217,7 @@ void Arch::setup_byname() const for (int i = 0; i < chip_info->tiles.ssize(); i++) { auto &tile = chip_info->tiles[i]; auto &tile_type = chip_info->tile_types[tile.type]; - for (int j = 0; j < tile_type.site_types.size(); j++) { + for (size_t j = 0; j < tile_type.site_types.size(); j++) { auto &site = chip_info->sites[tile.sites[j]]; site_by_name[id(site.name.get())] = std::make_pair(i, j); } -- cgit v1.2.3 From cd8297f54d71a5c9f47efab45b3cc93aea86d4e5 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Fri, 19 Feb 2021 09:46:27 -0800 Subject: Move RapidWright git URI back to upstream. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- fpga_interchange/examples/create_bba/Makefile | 6 +----- 1 file changed, 1 insertion(+), 5 deletions(-) diff --git a/fpga_interchange/examples/create_bba/Makefile b/fpga_interchange/examples/create_bba/Makefile index ffbc3103..c29bfa82 100644 --- a/fpga_interchange/examples/create_bba/Makefile +++ b/fpga_interchange/examples/create_bba/Makefile @@ -38,11 +38,7 @@ build: mkdir build build/RapidWright: | build - # FIXME: Update URL / branch as fixes are merged upstream and / or - # interchange branch on Xilinx/RapidWright is merged to master branch. - # - #cd build && git clone -b interchange https://github.com/Xilinx/RapidWright.git - cd build && git clone -b move_strlist https://github.com/litghost/RapidWright.git + cd build && git clone https://github.com/Xilinx/RapidWright.git build/env: | build python3 -mvenv build/env -- cgit v1.2.3 From 2fc353d5592b0bf9ed8428545bbd6a64312cc16e Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Fri, 19 Feb 2021 16:18:59 -0800 Subject: Add initial logic for handling dedicated interconnect situations. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- fpga_interchange/arch.cc | 5 + fpga_interchange/arch.h | 14 +- fpga_interchange/dedicated_interconnect.cc | 351 +++++++++++++++++++++++++++++ fpga_interchange/dedicated_interconnect.h | 129 +++++++++++ fpga_interchange/examples/ff/Makefile | 8 + fpga_interchange/examples/ff/ff.v | 11 + fpga_interchange/examples/ff/ff.xdc | 9 + fpga_interchange/examples/ff/run.tcl | 14 ++ fpga_interchange/fpga_interchange.cpp | 55 +++-- fpga_interchange/main.cc | 11 + fpga_interchange/site_router.cc | 6 + 11 files changed, 587 insertions(+), 26 deletions(-) create mode 100644 fpga_interchange/dedicated_interconnect.cc create mode 100644 fpga_interchange/dedicated_interconnect.h create mode 100644 fpga_interchange/examples/ff/Makefile create mode 100644 fpga_interchange/examples/ff/ff.v create mode 100644 fpga_interchange/examples/ff/ff.xdc create mode 100644 fpga_interchange/examples/ff/run.tcl diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc index 4cffd6ca..0955c376 100644 --- a/fpga_interchange/arch.cc +++ b/fpga_interchange/arch.cc @@ -195,6 +195,11 @@ Arch::Arch(ArchArgs args) : args(args) default_tags.resize(max_tag_count); } + +void Arch::init() { + dedicated_interconnect.init(getCtx()); +} + // ----------------------------------------------------------------------- std::string Arch::getChipName() const { return chip_info->name.get(); } diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h index a5352b60..780382ec 100644 --- a/fpga_interchange/arch.h +++ b/fpga_interchange/arch.h @@ -29,6 +29,7 @@ #include #include "constraints.h" +#include "dedicated_interconnect.h" NEXTPNR_NAMESPACE_BEGIN @@ -772,6 +773,8 @@ struct ArchRanges using BucketBelRangeT = FilteredBelRange; }; +struct DedicatedInterconnect; + struct Arch : ArchAPI { boost::iostreams::mapped_file_source blob_file; @@ -783,8 +786,6 @@ struct Arch : ArchAPI std::unordered_map wire_to_net; std::unordered_map pip_to_net; - std::unordered_map> driving_pip_loc; - std::unordered_map reserved_wires; static constexpr size_t kMaxState = 8; @@ -811,10 +812,12 @@ struct Arch : ArchAPI std::vector sites; }; + DedicatedInterconnect dedicated_interconnect; std::unordered_map tileStatus; ArchArgs args; Arch(ArchArgs args); + void init(); std::string getChipName() const override; @@ -1236,9 +1239,6 @@ struct Arch : ArchAPI NPNR_ASSERT(wire_to_net[dst] == nullptr || wire_to_net[dst] == net); pip_to_net[pip] = net; - std::pair loc; - get_tile_x_y(pip.tile, &loc.first, &loc.second); - driving_pip_loc[dst] = loc; wire_to_net[dst] = net; net->wires[dst].pip = pip; @@ -1509,6 +1509,10 @@ struct Arch : ArchAPI if (cell == nullptr) { return true; } else { + if(!dedicated_interconnect.isBelLocationValid(bel, cell)) { + return false; + } + if (io_port_types.count(cell->type)) { // FIXME: Probably need to actually constraint io port cell/bel, // but the current BBA emission doesn't support that. This only diff --git a/fpga_interchange/dedicated_interconnect.cc b/fpga_interchange/dedicated_interconnect.cc new file mode 100644 index 00000000..82101fbd --- /dev/null +++ b/fpga_interchange/dedicated_interconnect.cc @@ -0,0 +1,351 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2021 Symbiflow Authors + * + * + * 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" +#include "log.h" +#include "util.h" + +NEXTPNR_NAMESPACE_BEGIN + +void DedicatedInterconnect::init(const Context *ctx) { + this->ctx = ctx; + + if(ctx->debug) { + log_info("Finding dedicated interconnect!\n"); + } + + find_dedicated_interconnect(); + if(ctx->debug) { + print_dedicated_interconnect(); + } +} + +bool DedicatedInterconnect::check_routing( + BelId src_bel, IdString src_bel_pin, + BelId dst_bel, IdString dst_bel_pin) const { + // FIXME: Implement. + return false; +} + +bool DedicatedInterconnect::isBelLocationValid(BelId bel, const CellInfo* cell) const { + NPNR_ASSERT(bel != BelId()); + + Loc bel_loc = ctx->getBelLocation(bel); + + const auto &bel_data = bel_info(ctx->chip_info, bel); + + for(const auto &port_pair : cell->ports) { + IdString port_name = port_pair.first; + NetInfo *net = port_pair.second.net; + if(net == nullptr) { + continue; + } + + // Only check sink BELs. + if(net->driver.cell == cell && net->driver.port == port_name) { + continue; + } + + // This net doesn't have a driver, probably not valid? + NPNR_ASSERT(net->driver.cell != nullptr); + + BelId driver_bel = net->driver.cell->bel; + if(driver_bel == BelId()) { + return true; + } + + const auto &driver_bel_data = bel_info(ctx->chip_info, driver_bel); + + Loc driver_loc = ctx->getBelLocation(driver_bel); + + DeltaTileTypeBelPin driver_type_bel_pin; + driver_type_bel_pin.delta_x = driver_loc.x - bel_loc.x; + driver_type_bel_pin.delta_y = driver_loc.y - bel_loc.y; + driver_type_bel_pin.type_bel_pin.tile_type = ctx->chip_info->tiles[driver_bel.tile].type; + driver_type_bel_pin.type_bel_pin.bel_index = driver_bel.index; + driver_type_bel_pin.type_bel_pin.bel_pin = get_only_value(ctx->getBelPinsForCellPin(net->driver.cell, net->driver.port)); + + for(IdString bel_pin : ctx->getBelPinsForCellPin(cell, port_name)) { + TileTypeBelPin type_bel_pin; + type_bel_pin.tile_type = ctx->chip_info->tiles[bel.tile].type; + type_bel_pin.bel_index = bel.index; + type_bel_pin.bel_pin = bel_pin; + + auto iter = pins_with_dedicate_interconnect.find(type_bel_pin); + if(iter == pins_with_dedicate_interconnect.end()) { + // This BEL pin doesn't have a dedicate interconnect. + continue; + } + + if(bel.tile == driver_bel.tile && bel_data.site == driver_bel_data.site) { + // This is a site local routing, even though this is a sink + // with a dedicated interconnect. + continue; + } + + // Do fast routing check to see if the pair of driver and sink + // every are valid. + if(iter->second.count(driver_type_bel_pin) == 0) { + if(ctx->verbose) { + log_info("BEL %s is not valid because pin %s cannot be driven by %s/%s\n", + ctx->nameOfBel(bel), + bel_pin.c_str(ctx), + ctx->nameOfBel(driver_bel), + driver_type_bel_pin.type_bel_pin.bel_pin.c_str(ctx)); + } + return false; + } + + // Do detailed routing check to ensure driver can reach sink. + // + // FIXME: This might be too slow, but it handles a case on + // SLICEL.COUT -> SLICEL.CIN has delta_y = {1, 2}, but the + // delta_y=2 case is rare. + if(!check_routing( + driver_bel, driver_type_bel_pin.type_bel_pin.bel_pin, + bel, bel_pin)) { + if(ctx->verbose) { + log_info("BEL %s is not valid because pin %s cannot be driven by %s/%s (via detailed check)\n", + ctx->nameOfBel(bel), + bel_pin.c_str(ctx), + ctx->nameOfBel(driver_bel), + driver_type_bel_pin.type_bel_pin.bel_pin.c_str(ctx)); + } + return false; + } + } + } + + return true; +} + +void DedicatedInterconnect::print_dedicated_interconnect() const { + log_info("Found %zu sinks with dedicated interconnect\n", pins_with_dedicate_interconnect.size()); + std::vector sorted_keys; + for(const auto & sink_to_srcs : pins_with_dedicate_interconnect) { + sorted_keys.push_back(sink_to_srcs.first); + } + std::sort(sorted_keys.begin(), sorted_keys.end()); + + for(const auto & dst : sorted_keys) { + for(const auto & src : pins_with_dedicate_interconnect.at(dst)) { + const TileTypeInfoPOD & src_tile_type = ctx->chip_info->tile_types[src.type_bel_pin.tile_type]; + const BelInfoPOD & src_bel_info = src_tile_type.bel_data[src.type_bel_pin.bel_index]; + IdString src_site_type = IdString(src_tile_type.site_types[src_bel_info.site]); + IdString src_bel_pin = src.type_bel_pin.bel_pin; + + const TileTypeInfoPOD & dst_tile_type = ctx->chip_info->tile_types[dst.tile_type]; + const BelInfoPOD & dst_bel_info = dst_tile_type.bel_data[dst.bel_index]; + IdString dst_site_type = IdString(dst_tile_type.site_types[dst_bel_info.site]); + IdString dst_bel_pin = dst.bel_pin; + + log_info("%s.%s/%s/%s (%d, %d) -> %s.%s/%s/%s\n", + IdString(src_tile_type.name).c_str(ctx), + src_site_type.c_str(ctx), + IdString(src_bel_info.name).c_str(ctx), + src_bel_pin.c_str(ctx), + src.delta_x, + src.delta_y, + IdString(dst_tile_type.name).c_str(ctx), + dst_site_type.c_str(ctx), + IdString(dst_bel_info.name).c_str(ctx), + dst_bel_pin.c_str(ctx)); + + } + } +} + +void DedicatedInterconnect::find_dedicated_interconnect() { + for(BelId bel : ctx->getBels()) { + const auto & bel_data = bel_info(ctx->chip_info, bel); + if(bel_data.category != BEL_CATEGORY_LOGIC) { + continue; + } + if(bel_data.synthetic) { + continue; + } + + for(size_t i = 0; i < bel_data.num_bel_wires; ++i) { + if(bel_data.types[i] != PORT_IN) { + continue; + } + + WireId wire; + wire.tile = bel.tile; + wire.index = bel_data.wires[i]; + + expand_bel(bel, IdString(bel_data.ports[i]), wire); + } + } +} + +// All legal routes involved at most 2 sites, the source site and the sink +// site. The source site and sink sites may be the same, but that is not +// dedicated routing, that is intra site routing. +// +// Dedicated routing must leave the sink site, traverse some routing and +// terminate at another site. Routing that "flys" over a site is expressed as +// a psuedo-pip connected the relevant site pin wires, rather than traversing +// the site. +enum WireNodeState { + IN_SINK_SITE = 0, + IN_ROUTING = 1, + IN_SOURCE_SITE = 2 +}; + +struct WireNode { + WireId wire; + WireNodeState state; + int depth; +}; + +// Maximum depth that a dedicate interconnect is considered. +// +// Routing networks with depth <= kMaxDepth is considers a dedicated +// interconnect. +constexpr int kMaxDepth = 20; + +void DedicatedInterconnect::expand_bel(BelId bel, IdString pin, WireId wire) { + NPNR_ASSERT(bel != BelId()); + + std::vector nodes_to_expand; + + const auto & src_wire_data = ctx->wire_info(wire); + NPNR_ASSERT(src_wire_data.site != -1); + + WireNode wire_node; + wire_node.wire = wire; + wire_node.state = IN_SINK_SITE; + wire_node.depth = 0; + + nodes_to_expand.push_back(wire_node); + + Loc sink_loc = ctx->getBelLocation(bel); + std::unordered_set srcs; + + while(!nodes_to_expand.empty()) { + WireNode node_to_expand = nodes_to_expand.back(); + nodes_to_expand.pop_back(); + + for(PipId pip : ctx->getPipsUphill(node_to_expand.wire)) { + if(ctx->is_pip_synthetic(pip)) { + continue; + } + + WireId wire = ctx->getPipSrcWire(pip); + if(wire == WireId()) { + continue; + } + + WireNode next_node; + next_node.wire = wire; + next_node.depth = node_to_expand.depth += 1; + + if(next_node.depth > kMaxDepth) { + // Dedicated routing should reach sources by kMaxDepth (with + // tuning). + // + // FIXME: Consider removing kMaxDepth and use kMaxSources? + return; + } + + auto const & wire_data = ctx->wire_info(wire); + + bool expand_node = true; + if(ctx->is_site_port(pip)) { + switch(node_to_expand.state) { + case IN_SINK_SITE: + NPNR_ASSERT(wire_data.site == -1); + next_node.state = IN_ROUTING; + break; + case IN_ROUTING: + NPNR_ASSERT(wire_data.site != -1); + if(wire_data.site == src_wire_data.site) { + // Dedicated routing won't have straight loops, + // general routing looks like that. + return; + } + next_node.state = IN_SOURCE_SITE; + break; + case IN_SOURCE_SITE: + // Once entering a site, do not leave it again. + // This path is not a legal route! + expand_node = false; + break; + default: + // Unreachable!!! + NPNR_ASSERT(false); + } + } else { + next_node.state = node_to_expand.state; + } + + if(expand_node) { + nodes_to_expand.push_back(next_node); + } else { + continue; + } + + if(next_node.state == IN_SOURCE_SITE) { + for(BelPin bel_pin : ctx->getWireBelPins(wire)) { + BelId src_bel = bel_pin.bel; + auto const & bel_data = bel_info(ctx->chip_info, src_bel); + NPNR_ASSERT(bel_data.site != src_wire_data.site); + + if(bel_data.category != BEL_CATEGORY_LOGIC) { + continue; + } + if(bel_data.synthetic) { + continue; + } + if(ctx->getBelPinType(bel_pin.bel, bel_pin.pin) != PORT_OUT) { + continue; + } + + Loc src_loc = ctx->getBelLocation(src_bel); + + DeltaTileTypeBelPin delta_type_bel_pin; + delta_type_bel_pin.delta_x = src_loc.x - sink_loc.x; + delta_type_bel_pin.delta_x = src_loc.y - sink_loc.y; + delta_type_bel_pin.type_bel_pin.tile_type = ctx->chip_info->tiles[src_bel.tile].type; + delta_type_bel_pin.type_bel_pin.bel_index = src_bel.index; + delta_type_bel_pin.type_bel_pin.bel_pin = bel_pin.pin; + srcs.emplace(delta_type_bel_pin); + } + } + } + } + + TileTypeBelPin type_bel_pin; + type_bel_pin.tile_type = ctx->chip_info->tiles[bel.tile].type; + type_bel_pin.bel_index = bel.index; + type_bel_pin.bel_pin = pin; + + auto result = pins_with_dedicate_interconnect.emplace(type_bel_pin, srcs); + if(!result.second) { + // type_bel_pin was already present! Add any new sources from this + // sink type (if any); + for(auto src : srcs) { + result.first->second.emplace(src); + } + } +} + +NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/dedicated_interconnect.h b/fpga_interchange/dedicated_interconnect.h new file mode 100644 index 00000000..5fe61d30 --- /dev/null +++ b/fpga_interchange/dedicated_interconnect.h @@ -0,0 +1,129 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2021 Symbiflow Authors + * + * + * 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. + * + */ + +#ifndef NEXTPNR_H +#error Include "dedicated_interconnect.h" via "nextpnr.h" only. +#endif + +NEXTPNR_NAMESPACE_BEGIN + +struct TileTypeBelPin { + int32_t tile_type; + int32_t bel_index; + IdString bel_pin; + + bool operator < (const TileTypeBelPin &other) const { + if(tile_type >= other.tile_type) { + return false; + } + + if(bel_index >= other.bel_index) { + return false; + } + + return bel_pin < other.bel_pin; + } + + bool operator ==(const TileTypeBelPin &other) const { + return tile_type == other.tile_type && bel_index == other.bel_index && bel_pin == other.bel_pin; + } + bool operator !=(const TileTypeBelPin &other) const { + return tile_type != other.tile_type || bel_index != other.bel_index || bel_pin != other.bel_pin; + } +}; + +struct DeltaTileTypeBelPin { + int32_t delta_x; + int32_t delta_y; + TileTypeBelPin type_bel_pin; + + bool operator ==(const DeltaTileTypeBelPin &other) const { + return delta_x == other.delta_x && delta_y == other.delta_y && type_bel_pin == other.type_bel_pin; + } + bool operator !=(const DeltaTileTypeBelPin &other) const { + return delta_x != other.delta_x || delta_y != other.delta_y || type_bel_pin != other.type_bel_pin; + } +}; + +NEXTPNR_NAMESPACE_END + +template <> struct std::hash +{ + std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX TileTypeBelPin &type_bel_pin) const noexcept + { + std::size_t seed = 0; + boost::hash_combine(seed, std::hash()(type_bel_pin.tile_type)); + boost::hash_combine(seed, std::hash()(type_bel_pin.bel_index)); + boost::hash_combine(seed, std::hash()(type_bel_pin.bel_pin)); + return seed; + } +}; + +template <> struct std::hash +{ + std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX DeltaTileTypeBelPin &delta_bel_pin) const noexcept + { + std::size_t seed = 0; + boost::hash_combine(seed, std::hash()(delta_bel_pin.delta_x)); + boost::hash_combine(seed, std::hash()(delta_bel_pin.delta_y)); + boost::hash_combine(seed, std::hash()(delta_bel_pin.type_bel_pin)); + return seed; + } +}; + +NEXTPNR_NAMESPACE_BEGIN + +struct Context; + +// This class models dedicated interconnect present in the given fabric. +// +// Examples of dedicate interconnect: +// - IBUF.O -> ISERDES.I +// - IBUF.O -> IDELAY.I +// - CARRY4.CO[3] -> CARRY4.CIN +// +// Note that CARRY4.CYINIT does not **require** dedicated interconnect, so +// it doesn't qualify. +// +// This class discovers dedicated interconnect by examing the routing graph. +// This discovery make be expensive, and require caching to accelerate +// startup. +struct DedicatedInterconnect { + const Context *ctx; + + std::unordered_map> pins_with_dedicate_interconnect; + + void init(const Context *ctx); + + // Is this BEL placed in a location that is valid based on dedicated + // interconnect? + // + // Note: Only BEL pin sinks are checked. + bool isBelLocationValid(BelId bel, const CellInfo* cell) const; + + void find_dedicated_interconnect(); + void print_dedicated_interconnect() const; + bool check_routing( + BelId src_bel, IdString src_bel_pin, + BelId dst_bel, IdString dst_bel_pin) const; + void expand_bel(BelId bel, IdString pin, WireId wire); +}; + +NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/examples/ff/Makefile b/fpga_interchange/examples/ff/Makefile new file mode 100644 index 00000000..c6118ff7 --- /dev/null +++ b/fpga_interchange/examples/ff/Makefile @@ -0,0 +1,8 @@ +DESIGN := ff +DESIGN_TOP := top +PACKAGE := csg324 + +include ../template.mk + +build/ff.json: ff.v | build + yosys -c run.tcl diff --git a/fpga_interchange/examples/ff/ff.v b/fpga_interchange/examples/ff/ff.v new file mode 100644 index 00000000..1c271042 --- /dev/null +++ b/fpga_interchange/examples/ff/ff.v @@ -0,0 +1,11 @@ +module top(input clk, input d, input r, output reg q); + +always @(posedge clk) +begin + if(r) + q <= 1'b0; + else + q <= d; +end + +endmodule diff --git a/fpga_interchange/examples/ff/ff.xdc b/fpga_interchange/examples/ff/ff.xdc new file mode 100644 index 00000000..3c132f1d --- /dev/null +++ b/fpga_interchange/examples/ff/ff.xdc @@ -0,0 +1,9 @@ +set_property PACKAGE_PIN P17 [get_ports clk] +set_property PACKAGE_PIN N15 [get_ports d] +set_property PACKAGE_PIN N16 [get_ports r] +set_property PACKAGE_PIN M17 [get_ports q] + +set_property IOSTANDARD LVCMOS33 [get_ports clk] +set_property IOSTANDARD LVCMOS33 [get_ports d] +set_property IOSTANDARD LVCMOS33 [get_ports r] +set_property IOSTANDARD LVCMOS33 [get_ports q] diff --git a/fpga_interchange/examples/ff/run.tcl b/fpga_interchange/examples/ff/run.tcl new file mode 100644 index 00000000..726d86eb --- /dev/null +++ b/fpga_interchange/examples/ff/run.tcl @@ -0,0 +1,14 @@ +yosys -import + +read_verilog ff.v + +synth_xilinx -nolutram -nowidelut -nosrl -nocarry -nodsp + +# opt_expr -undriven makes sure all nets are driven, if only by the $undef +# net. +opt_expr -undriven +opt_clean + +setundef -zero -params + +write_json build/ff.json diff --git a/fpga_interchange/fpga_interchange.cpp b/fpga_interchange/fpga_interchange.cpp index ad1dd76d..fd57e09c 100644 --- a/fpga_interchange/fpga_interchange.cpp +++ b/fpga_interchange/fpga_interchange.cpp @@ -311,9 +311,6 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str for(auto & cell_name : placed_cells) { const CellInfo & cell = *ctx->cells.at(cell_name); - if(ctx->io_port_types.count(cell.type)) { - continue; - } if(ctx->is_bel_synthetic(cell.bel)) { continue; } @@ -321,15 +318,14 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str number_placements += 1; } + std::vector ports; + std::unordered_map sites; auto placements = phys_netlist.initPlacements(number_placements); auto placement_iter = placements.begin(); for(auto & cell_name : placed_cells) { const CellInfo & cell = *ctx->cells.at(cell_name); - if(ctx->io_port_types.count(cell.type)) { - continue; - } if(ctx->is_bel_synthetic(cell.bel)) { continue; } @@ -351,7 +347,13 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str auto placement = *placement_iter++; placement.setCellName(strings.get_index(cell.name.str(ctx))); - placement.setType(strings.get_index(cell.type.str(ctx))); + if(ctx->io_port_types.count(cell.type)) { + // Always mark IO ports as type . + placement.setType(strings.get_index("")); + ports.push_back(cell.name); + } else { + placement.setType(strings.get_index(cell.type.str(ctx))); + } placement.setSite(strings.get_index(site_name)); size_t bel_index = strings.get_index(bel_name[1].str(ctx)); @@ -359,27 +361,38 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str placement.setIsBelFixed(cell.belStrength >= STRENGTH_FIXED); placement.setIsSiteFixed(cell.belStrength >= STRENGTH_FIXED); - size_t pin_count = 0; - for(const auto & pin : cell.cell_bel_pins) { - pin_count += pin.second.size(); - } + if(!ctx->io_port_types.count(cell.type)) { + // Don't emit pin map for ports. + size_t pin_count = 0; + for(const auto & pin : cell.cell_bel_pins) { + pin_count += pin.second.size(); + } - auto pins = placement.initPinMap(pin_count); - auto pin_iter = pins.begin(); + auto pins = placement.initPinMap(pin_count); + auto pin_iter = pins.begin(); - for(const auto & cell_to_bel_pins : cell.cell_bel_pins) { - std::string cell_pin = cell_to_bel_pins.first.str(ctx); - size_t cell_pin_index = strings.get_index(cell_pin); + for(const auto & cell_to_bel_pins : cell.cell_bel_pins) { + std::string cell_pin = cell_to_bel_pins.first.str(ctx); + size_t cell_pin_index = strings.get_index(cell_pin); - for(const auto & bel_pin : cell_to_bel_pins.second) { - auto pin_output = *pin_iter++; - pin_output.setCellPin(cell_pin_index); - pin_output.setBel(bel_index); - pin_output.setBelPin(strings.get_index(bel_pin.str(ctx))); + for(const auto & bel_pin : cell_to_bel_pins.second) { + auto pin_output = *pin_iter++; + pin_output.setCellPin(cell_pin_index); + pin_output.setBel(bel_index); + pin_output.setBelPin(strings.get_index(bel_pin.str(ctx))); + } } } } + auto phys_cells = phys_netlist.initPhysCells(ports.size()); + auto phys_cells_iter = phys_cells.begin(); + for(IdString port : ports) { + auto phys_cell = *phys_cells_iter++; + phys_cell.setCellName(strings.get_index(port.str(ctx))); + phys_cell.setPhysType(PhysicalNetlist::PhysNetlist::PhysCellType::PORT); + } + auto nets = phys_netlist.initPhysNets(ctx->nets.size()); auto net_iter = nets.begin(); for(auto & net_pair : ctx->nets) { diff --git a/fpga_interchange/main.cc b/fpga_interchange/main.cc index 5a49cbdc..958f1d95 100644 --- a/fpga_interchange/main.cc +++ b/fpga_interchange/main.cc @@ -70,6 +70,7 @@ void FpgaInterchangeCommandHandler::customBitstream(Context *ctx) std::unique_ptr FpgaInterchangeCommandHandler::createContext(std::unordered_map &values) { auto start = std::chrono::high_resolution_clock::now(); + ArchArgs chipArgs; if (!vm.count("chipdb")) { log_error("chip database binary must be provided\n"); @@ -81,6 +82,16 @@ std::unique_ptr FpgaInterchangeCommandHandler::createContext(std::unord auto ctx = std::unique_ptr(new Context(chipArgs)); + if (vm.count("verbose")) { + ctx->verbose = true; + } + if (vm.count("debug")) { + ctx->verbose = true; + ctx->debug = true; + } + + ctx->init(); + if (vm.count("netlist")) { ctx->read_logical_netlist(vm["netlist"].as()); } diff --git a/fpga_interchange/site_router.cc b/fpga_interchange/site_router.cc index 09e01507..a22dfcd3 100644 --- a/fpga_interchange/site_router.cc +++ b/fpga_interchange/site_router.cc @@ -260,6 +260,12 @@ struct SiteInformation if (!result.second && result.first->second != net) { // Conflict, this wire is already in use and it's not // doesn't match! + if(verbose_site_router(ctx)) { + log_info("Cannot select route because net %s != net %s\n", + result.first->second->name.c_str(ctx), + net->name.c_str(ctx)); + } + return false; } -- cgit v1.2.3 From 5574455d2a20d3bb950e5dd907ef193d049a2a26 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Fri, 19 Feb 2021 17:28:25 -0800 Subject: Working FF example now that constant merging is done. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- fpga_interchange/arch.cc | 187 +++++++++++++++++++++++++++++++- fpga_interchange/arch.h | 4 +- fpga_interchange/archdefs.h | 1 + fpga_interchange/examples/template.mk | 18 +++ fpga_interchange/examples/wire/wire.xdc | 3 + fpga_interchange/fpga_interchange.cpp | 13 ++- 6 files changed, 218 insertions(+), 8 deletions(-) diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc index 0955c376..966d74f3 100644 --- a/fpga_interchange/arch.cc +++ b/fpga_interchange/arch.cc @@ -606,6 +606,7 @@ bool Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay bool Arch::pack() { + merge_constant_nets(); pack_ports(); return true; } @@ -754,7 +755,7 @@ const std::vector Arch::availablePlacers = {"sa", const std::string Arch::defaultRouter = "router2"; const std::vector Arch::availableRouters = {"router1", "router2"}; -void Arch::map_cell_pins(CellInfo *cell, int32_t mapping) const +void Arch::map_cell_pins(CellInfo *cell, int32_t mapping) { cell->cell_mapping = mapping; cell->cell_bel_pins.clear(); @@ -766,11 +767,32 @@ void Arch::map_cell_pins(CellInfo *cell, int32_t mapping) const IdString bel_pin(pin_map.bel_pin); if (cell_pin.str(this) == "GND") { - // FIXME: Tie this pin to the GND net + PortInfo port_info; + port_info.name = bel_pin; + port_info.type = PORT_IN; + port_info.net = nullptr; + + auto result = cell->ports.emplace(bel_pin, port_info); + NPNR_ASSERT(result.second); + + cell->cell_bel_pins[bel_pin].push_back(bel_pin); + + connectPort(IdString(chip_info->constants->gnd_net_name), cell->name, bel_pin); continue; } + if (cell_pin.str(this) == "VCC") { - // FIXME: Tie this pin to the VCC net + PortInfo port_info; + port_info.name = bel_pin; + port_info.type = PORT_IN; + port_info.net = nullptr; + + auto result = cell->ports.emplace(bel_pin, port_info); + NPNR_ASSERT(result.second); + + cell->cell_bel_pins[bel_pin].push_back(bel_pin); + + connectPort(IdString(chip_info->constants->vcc_net_name), cell->name, bel_pin); continue; } @@ -795,11 +817,30 @@ void Arch::map_cell_pins(CellInfo *cell, int32_t mapping) const IdString bel_pin(pin_map.bel_pin); if (cell_pin.str(this) == "GND") { - // FIXME: Tie this pin to the GND net + PortInfo port_info; + port_info.name = bel_pin; + port_info.type = PORT_IN; + + auto result = cell->ports.emplace(bel_pin, port_info); + NPNR_ASSERT(result.second); + + cell->cell_bel_pins[bel_pin].push_back(bel_pin); + + connectPort(IdString(chip_info->constants->gnd_net_name), cell->name, bel_pin); continue; } + if (cell_pin.str(this) == "VCC") { - // FIXME: Tie this pin to the VCC net + PortInfo port_info; + port_info.name = bel_pin; + port_info.type = PORT_IN; + + auto result = cell->ports.emplace(bel_pin, port_info); + NPNR_ASSERT(result.second); + + cell->cell_bel_pins[bel_pin].push_back(bel_pin); + + connectPort(IdString(chip_info->constants->vcc_net_name), cell->name, bel_pin); continue; } @@ -858,6 +899,142 @@ size_t Arch::get_cell_type_index(IdString cell_type) const return cell_offset; } +void Arch::merge_constant_nets() { + NetInfo* gnd_net = nullptr; + NetInfo* vcc_net = nullptr; + + bool need_gnd_source = false; + bool need_vcc_source = false; + + IdString gnd_net_name(chip_info->constants->gnd_net_name); + IdString gnd_cell_type(chip_info->constants->gnd_cell_name); + IdString gnd_cell_port(chip_info->constants->gnd_cell_port); + + auto gnd_iter = nets.find(gnd_net_name); + if(gnd_iter != nets.end()) { + NPNR_ASSERT(gnd_iter->second->driver.cell != nullptr); + NPNR_ASSERT(gnd_iter->second->driver.cell->type == gnd_cell_type); + NPNR_ASSERT(gnd_iter->second->driver.port == gnd_cell_port); + + gnd_net = gnd_iter->second.get(); + } else { + gnd_net = createNet(gnd_net_name); + need_gnd_source = true; + } + + IdString vcc_net_name(chip_info->constants->vcc_net_name); + IdString vcc_cell_type(chip_info->constants->vcc_cell_name); + IdString vcc_cell_port(chip_info->constants->vcc_cell_port); + + auto vcc_iter = nets.find(vcc_net_name); + if(vcc_iter != nets.end()) { + NPNR_ASSERT(vcc_iter->second->driver.cell != nullptr); + NPNR_ASSERT(vcc_iter->second->driver.cell->type == vcc_cell_type); + NPNR_ASSERT(vcc_iter->second->driver.port == vcc_cell_port); + + vcc_net = vcc_iter->second.get(); + } else { + vcc_net = createNet(vcc_net_name); + need_vcc_source = true; + } + + std::vector other_gnd_nets; + std::vector other_vcc_nets; + + for(auto & net_pair : nets) { + if(net_pair.first == gnd_net_name) { + NPNR_ASSERT(net_pair.second.get() == gnd_net); + continue; + } + + if(net_pair.first == vcc_net_name) { + NPNR_ASSERT(net_pair.second.get() == vcc_net); + continue; + } + + NetInfo *net = net_pair.second.get(); + if(net->driver.cell == nullptr) { + continue; + } + + if(net->driver.cell->type == gnd_cell_type) { + NPNR_ASSERT(net->driver.port == gnd_cell_port); + + other_gnd_nets.push_back(net_pair.first); + + if(need_gnd_source) { + IdString driver_cell = net->driver.cell->name; + disconnectPort(driver_cell, gnd_cell_port); + connectPort(gnd_net_name, driver_cell, gnd_cell_port); + need_gnd_source = false; + } + + NPNR_ASSERT(net->driver.port == gnd_cell_port); + std::vector users_copy = net->users; + for(const PortRef & port_ref : users_copy) { + IdString cell = port_ref.cell->name; + disconnectPort(cell, port_ref.port); + connectPort(gnd_net_name, cell, port_ref.port); + } + } + + if(net->driver.cell->type == vcc_cell_type) { + NPNR_ASSERT(net->driver.port == vcc_cell_port); + + other_vcc_nets.push_back(net_pair.first); + + if(need_vcc_source) { + IdString driver_cell = net->driver.cell->name; + disconnectPort(driver_cell, vcc_cell_port); + connectPort(vcc_net_name, driver_cell, vcc_cell_port); + need_vcc_source = false; + } + + NPNR_ASSERT(net->driver.port == vcc_cell_port); + std::vector users_copy = net->users; + for(const PortRef & port_ref : users_copy) { + IdString cell = port_ref.cell->name; + disconnectPort(cell, port_ref.port); + connectPort(vcc_net_name, cell, port_ref.port); + } + } + } + + for(IdString other_gnd_net : other_gnd_nets) { + NetInfo * net = getNetByAlias(other_gnd_net); + NPNR_ASSERT(net->users.empty()); + } + + for(IdString other_vcc_net : other_vcc_nets) { + NetInfo * net = getNetByAlias(other_vcc_net); + NPNR_ASSERT(net->users.empty()); + } + + for(IdString other_gnd_net : other_gnd_nets) { + NPNR_ASSERT(nets.erase(other_gnd_net)); + gnd_net->aliases.push_back(other_gnd_net); + net_aliases[other_gnd_net] = gnd_net_name; + } + + for(IdString other_vcc_net : other_vcc_nets) { + NPNR_ASSERT(nets.erase(other_vcc_net)); + vcc_net->aliases.push_back(other_vcc_net); + net_aliases[other_vcc_net] = vcc_net_name; + } + + if(need_gnd_source) { + CellInfo * gnd_cell = createCell(gnd_cell_type, gnd_cell_type); + gnd_cell->addOutput(gnd_cell_port); + connectPort(gnd_net_name, gnd_cell_type, gnd_cell_port); + } + + if(need_vcc_source) { + CellInfo * vcc_cell = createCell(vcc_cell_type, vcc_cell_type); + vcc_cell->addOutput(vcc_cell_port); + connectPort(vcc_net_name, vcc_cell_type, vcc_cell_port); + } +} + // Instance constraint templates. template void Arch::ArchConstraints::bindBel(Arch::ArchConstraints::TagState *, const Arch::ConstraintRange); template void Arch::ArchConstraints::unbindBel(Arch::ArchConstraints::TagState *, const Arch::ConstraintRange); diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h index 780382ec..c713ddb9 100644 --- a/fpga_interchange/arch.h +++ b/fpga_interchange/arch.h @@ -871,7 +871,7 @@ struct Arch : ArchAPI uint32_t getBelChecksum(BelId bel) const override { return bel.index; } - void map_cell_pins(CellInfo *cell, int32_t mapping) const; + void map_cell_pins(CellInfo *cell, int32_t mapping); void map_port_pins(BelId bel, CellInfo *cell) const; TileStatus &get_tile_status(int32_t tile) @@ -1716,6 +1716,8 @@ struct Arch : ArchAPI return is_bel_synthetic(bel); } } + + void merge_constant_nets(); }; NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/archdefs.h b/fpga_interchange/archdefs.h index 75af6974..33d999bb 100644 --- a/fpga_interchange/archdefs.h +++ b/fpga_interchange/archdefs.h @@ -106,6 +106,7 @@ struct ArchCellInfo int32_t cell_mapping; std::unordered_map> cell_bel_pins; + std::unordered_set const_ports; }; NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/examples/template.mk b/fpga_interchange/examples/template.mk index d12a4e11..c795544e 100644 --- a/fpga_interchange/examples/template.mk +++ b/fpga_interchange/examples/template.mk @@ -55,6 +55,15 @@ verbose: build/$(DESIGN).netlist --package $(PACKAGE) \ --verbose +verbose2: build/$(DESIGN).netlist + $(NEXTPNR_BIN) \ + --chipdb $(BBA_PATH) \ + --xdc $(DESIGN).xdc \ + --netlist build/$(DESIGN).netlist \ + --phys build/$(DESIGN).phys \ + --package $(PACKAGE) \ + --debug + debug: build/$(DESIGN).netlist gdb --args $(NEXTPNR_BIN) \ --chipdb $(BBA_PATH) \ @@ -63,6 +72,15 @@ debug: build/$(DESIGN).netlist --phys build/$(DESIGN).phys \ --package $(PACKAGE) +debug_verbose: build/$(DESIGN).netlist + gdb --args $(NEXTPNR_BIN) \ + --chipdb $(BBA_PATH) \ + --xdc $(DESIGN).xdc \ + --netlist build/$(DESIGN).netlist \ + --phys build/$(DESIGN).phys \ + --package $(PACKAGE) \ + --verbose + build/$(DESIGN).dcp: build/$(DESIGN).netlist build/$(DESIGN).phys $(DESIGN).xdc RAPIDWRIGHT_PATH=$(RAPIDWRIGHT_PATH) \ $(RAPIDWRIGHT_PATH)/scripts/invoke_rapidwright.sh \ diff --git a/fpga_interchange/examples/wire/wire.xdc b/fpga_interchange/examples/wire/wire.xdc index e1fce5f0..c923f0fc 100644 --- a/fpga_interchange/examples/wire/wire.xdc +++ b/fpga_interchange/examples/wire/wire.xdc @@ -1,2 +1,5 @@ set_property PACKAGE_PIN N16 [get_ports i] set_property PACKAGE_PIN N15 [get_ports o] + +set_property IOSTANDARD LVCMOS33 [get_ports i] +set_property IOSTANDARD LVCMOS33 [get_ports o] diff --git a/fpga_interchange/fpga_interchange.cpp b/fpga_interchange/fpga_interchange.cpp index fd57e09c..027513c8 100644 --- a/fpga_interchange/fpga_interchange.cpp +++ b/fpga_interchange/fpga_interchange.cpp @@ -269,8 +269,10 @@ static void find_non_synthetic_edges(const Context * ctx, WireId root_wire, auto downhill_iter = pip_downhill.find(wire); if(downhill_iter == pip_downhill.end()) { - log_warning("Wire %s never entered the real fabric?\n", - ctx->nameOfWire(wire)); + if(root_wire != wire) { + log_warning("Wire %s never entered the real fabric?\n", + ctx->nameOfWire(wire)); + } continue; } @@ -365,6 +367,9 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str // Don't emit pin map for ports. size_t pin_count = 0; for(const auto & pin : cell.cell_bel_pins) { + if(cell.const_ports.count(pin.first)) { + continue; + } pin_count += pin.second.size(); } @@ -372,6 +377,10 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str auto pin_iter = pins.begin(); for(const auto & cell_to_bel_pins : cell.cell_bel_pins) { + if(cell.const_ports.count(cell_to_bel_pins.first)) { + continue; + } + std::string cell_pin = cell_to_bel_pins.first.str(ctx); size_t cell_pin_index = strings.get_index(cell_pin); -- cgit v1.2.3 From 184665652eaf351bf9337b524c5d82a50ce54041 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Mon, 22 Feb 2021 09:13:44 -0800 Subject: Finish dedicated interconnect implementation. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- fpga_interchange/arch.cc | 45 +- fpga_interchange/dedicated_interconnect.cc | 694 +++++++++++++++++++++++------ fpga_interchange/dedicated_interconnect.h | 11 +- 3 files changed, 611 insertions(+), 139 deletions(-) diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc index 966d74f3..776fbdb0 100644 --- a/fpga_interchange/arch.cc +++ b/fpga_interchange/arch.cc @@ -767,32 +767,45 @@ void Arch::map_cell_pins(CellInfo *cell, int32_t mapping) IdString bel_pin(pin_map.bel_pin); if (cell_pin.str(this) == "GND") { + IdString gnd_net_name(chip_info->constants->gnd_net_name); + PortInfo port_info; port_info.name = bel_pin; port_info.type = PORT_IN; port_info.net = nullptr; auto result = cell->ports.emplace(bel_pin, port_info); - NPNR_ASSERT(result.second); - - cell->cell_bel_pins[bel_pin].push_back(bel_pin); - - connectPort(IdString(chip_info->constants->gnd_net_name), cell->name, bel_pin); + if(result.second) { + cell->cell_bel_pins[bel_pin].push_back(bel_pin); + connectPort(gnd_net_name, cell->name, bel_pin); + } else { + NPNR_ASSERT(result.first->second.net == getNetByAlias(gnd_net_name)); + auto result2 = cell->cell_bel_pins.emplace(bel_pin, std::vector({bel_pin})); + NPNR_ASSERT(result2.first->second.at(0) == bel_pin); + NPNR_ASSERT(result2.first->second.size() == 1); + } continue; } if (cell_pin.str(this) == "VCC") { + IdString vcc_net_name(chip_info->constants->vcc_net_name); + PortInfo port_info; port_info.name = bel_pin; port_info.type = PORT_IN; port_info.net = nullptr; auto result = cell->ports.emplace(bel_pin, port_info); - NPNR_ASSERT(result.second); - - cell->cell_bel_pins[bel_pin].push_back(bel_pin); + if(result.second) { + cell->cell_bel_pins[bel_pin].push_back(bel_pin); + connectPort(vcc_net_name, cell->name, bel_pin); + } else { + NPNR_ASSERT(result.first->second.net == getNetByAlias(vcc_net_name)); + auto result2 = cell->cell_bel_pins.emplace(bel_pin, std::vector({bel_pin})); + NPNR_ASSERT(result2.first->second.at(0) == bel_pin); + NPNR_ASSERT(result2.first->second.size() == 1); + } - connectPort(IdString(chip_info->constants->vcc_net_name), cell->name, bel_pin); continue; } @@ -976,6 +989,8 @@ void Arch::merge_constant_nets() { disconnectPort(cell, port_ref.port); connectPort(gnd_net_name, cell, port_ref.port); } + + continue; } if(net->driver.cell->type == vcc_cell_type) { @@ -1003,11 +1018,23 @@ void Arch::merge_constant_nets() { for(IdString other_gnd_net : other_gnd_nets) { NetInfo * net = getNetByAlias(other_gnd_net); NPNR_ASSERT(net->users.empty()); + if(net->driver.cell) { + PortRef driver = net->driver; + IdString cell_to_remove = driver.cell->name; + disconnectPort(driver.cell->name, driver.port); + NPNR_ASSERT(cells.erase(cell_to_remove)); + } } for(IdString other_vcc_net : other_vcc_nets) { NetInfo * net = getNetByAlias(other_vcc_net); NPNR_ASSERT(net->users.empty()); + if(net->driver.cell) { + PortRef driver = net->driver; + IdString cell_to_remove = driver.cell->name; + disconnectPort(driver.cell->name, driver.port); + NPNR_ASSERT(cells.erase(cell_to_remove)); + } } for(IdString other_gnd_net : other_gnd_nets) { diff --git a/fpga_interchange/dedicated_interconnect.cc b/fpga_interchange/dedicated_interconnect.cc index 82101fbd..b9ef93b5 100644 --- a/fpga_interchange/dedicated_interconnect.cc +++ b/fpga_interchange/dedicated_interconnect.cc @@ -24,6 +24,32 @@ NEXTPNR_NAMESPACE_BEGIN +// All legal routes involved at most 2 sites, the source site and the sink +// site. The source site and sink sites may be the same, but that is not +// dedicated routing, that is intra site routing. +// +// Dedicated routing must leave the sink site, traverse some routing and +// terminate at another site. Routing that "flys" over a site is expressed as +// a psuedo-pip connected the relevant site pin wires, rather than traversing +// the site. +enum WireNodeState { + IN_SINK_SITE = 0, + IN_ROUTING = 1, + IN_SOURCE_SITE = 2 +}; + +struct WireNode { + WireId wire; + WireNodeState state; + int depth; +}; + +// Maximum depth that a dedicate interconnect is considered. +// +// Routing networks with depth <= kMaxDepth is considers a dedicated +// interconnect. +constexpr int kMaxDepth = 20; + void DedicatedInterconnect::init(const Context *ctx) { this->ctx = ctx; @@ -40,94 +66,290 @@ void DedicatedInterconnect::init(const Context *ctx) { bool DedicatedInterconnect::check_routing( BelId src_bel, IdString src_bel_pin, BelId dst_bel, IdString dst_bel_pin) const { - // FIXME: Implement. - return false; -} + std::vector nodes_to_expand; -bool DedicatedInterconnect::isBelLocationValid(BelId bel, const CellInfo* cell) const { - NPNR_ASSERT(bel != BelId()); + WireId src_wire = ctx->getBelPinWire(src_bel, src_bel_pin); - Loc bel_loc = ctx->getBelLocation(bel); + const auto & src_wire_data = ctx->wire_info(src_wire); + NPNR_ASSERT(src_wire_data.site != -1); - const auto &bel_data = bel_info(ctx->chip_info, bel); + WireId dst_wire = ctx->getBelPinWire(dst_bel, dst_bel_pin); - for(const auto &port_pair : cell->ports) { - IdString port_name = port_pair.first; - NetInfo *net = port_pair.second.net; - if(net == nullptr) { - continue; - } + const auto & dst_wire_data = ctx->wire_info(dst_wire); + NPNR_ASSERT(dst_wire_data.site != -1); - // Only check sink BELs. - if(net->driver.cell == cell && net->driver.port == port_name) { - continue; - } + WireNode wire_node; + wire_node.wire = src_wire; + wire_node.state = IN_SOURCE_SITE; + wire_node.depth = 0; - // This net doesn't have a driver, probably not valid? - NPNR_ASSERT(net->driver.cell != nullptr); + nodes_to_expand.push_back(wire_node); - BelId driver_bel = net->driver.cell->bel; - if(driver_bel == BelId()) { - return true; - } + while(!nodes_to_expand.empty()) { + WireNode node_to_expand = nodes_to_expand.back(); + nodes_to_expand.pop_back(); - const auto &driver_bel_data = bel_info(ctx->chip_info, driver_bel); + for(PipId pip : ctx->getPipsDownhill(node_to_expand.wire)) { + if(ctx->is_pip_synthetic(pip)) { + continue; + } - Loc driver_loc = ctx->getBelLocation(driver_bel); + WireId wire = ctx->getPipDstWire(pip); + if(wire == WireId()) { + continue; + } - DeltaTileTypeBelPin driver_type_bel_pin; - driver_type_bel_pin.delta_x = driver_loc.x - bel_loc.x; - driver_type_bel_pin.delta_y = driver_loc.y - bel_loc.y; - driver_type_bel_pin.type_bel_pin.tile_type = ctx->chip_info->tiles[driver_bel.tile].type; - driver_type_bel_pin.type_bel_pin.bel_index = driver_bel.index; - driver_type_bel_pin.type_bel_pin.bel_pin = get_only_value(ctx->getBelPinsForCellPin(net->driver.cell, net->driver.port)); +#ifdef DEBUG_EXPANSION + log_info(" - At wire %s via %s\n", + ctx->nameOfWire(wire), ctx->nameOfPip(pip)); +#endif - for(IdString bel_pin : ctx->getBelPinsForCellPin(cell, port_name)) { - TileTypeBelPin type_bel_pin; - type_bel_pin.tile_type = ctx->chip_info->tiles[bel.tile].type; - type_bel_pin.bel_index = bel.index; - type_bel_pin.bel_pin = bel_pin; + WireNode next_node; + next_node.wire = wire; + next_node.depth = node_to_expand.depth += 1; + + if(next_node.depth > kMaxDepth) { + // Dedicated routing should reach sources by kMaxDepth (with + // tuning). + // + // FIXME: Consider removing kMaxDepth and use kMaxSources? + return false; + } + + auto const & wire_data = ctx->wire_info(wire); - auto iter = pins_with_dedicate_interconnect.find(type_bel_pin); - if(iter == pins_with_dedicate_interconnect.end()) { - // This BEL pin doesn't have a dedicate interconnect. + bool expand_node = true; + if(ctx->is_site_port(pip)) { + switch(node_to_expand.state) { + case IN_SOURCE_SITE: + NPNR_ASSERT(wire_data.site == -1); + next_node.state = IN_ROUTING; + break; + case IN_ROUTING: + NPNR_ASSERT(wire_data.site != -1); + if(wire.tile == src_wire.tile && wire_data.site == src_wire_data.site) { + // Dedicated routing won't have straight loops, + // general routing looks like that. +#ifdef DEBUG_EXPANSION + log_info(" - Not dedicated site routing because loop!"); +#endif + return false; + } + next_node.state = IN_SINK_SITE; + break; + case IN_SINK_SITE: + // Once entering a site, do not leave it again. + // This path is not a legal route! + expand_node = false; + break; + default: + // Unreachable!!! + NPNR_ASSERT(false); + } + } else { + next_node.state = node_to_expand.state; + } + + if(expand_node) { + nodes_to_expand.push_back(next_node); + } else { continue; } - if(bel.tile == driver_bel.tile && bel_data.site == driver_bel_data.site) { + if(next_node.state == IN_SINK_SITE) { + for(BelPin bel_pin : ctx->getWireBelPins(wire)) { + if(bel_pin.bel == dst_bel && bel_pin.pin == dst_bel_pin) { + if(ctx->verbose) { + log_info("Valid dedicated interconnect from %s/%s to %s/%s\n", + ctx->nameOfBel(src_bel), + src_bel_pin.c_str(ctx), + ctx->nameOfBel(dst_bel), + dst_bel_pin.c_str(ctx)); + } + return true; + } + } + } + } + } + + return false; +} + +bool DedicatedInterconnect::is_driver_on_net_valid(BelId driver_bel, + const CellInfo* cell, IdString driver_port, NetInfo *net) const { + const auto &driver_bel_data = bel_info(ctx->chip_info, driver_bel); + + TileTypeBelPin type_bel_pin; + type_bel_pin.tile_type = ctx->chip_info->tiles[driver_bel.tile].type; + type_bel_pin.bel_index = driver_bel.index; + + Loc driver_loc = ctx->getBelLocation(driver_bel); + + for(IdString driver_bel_pin : ctx->getBelPinsForCellPin(cell, driver_port)) { + type_bel_pin.bel_pin = driver_bel_pin; + + auto iter = sources.find(type_bel_pin); + if(iter == sources.end()) { + // This BEL pin doesn't have a dedicate interconnect. + continue; + } + + for(const PortRef & port_ref : net->users) { + NPNR_ASSERT(port_ref.cell != nullptr); + + if(port_ref.cell->bel == BelId()) { + return true; + } + + BelId sink_bel = port_ref.cell->bel; + const auto &sink_bel_data = bel_info(ctx->chip_info, sink_bel); + Loc sink_loc = ctx->getBelLocation(port_ref.cell->bel); + + if(sink_bel.tile == driver_bel.tile && sink_bel_data.site == driver_bel_data.site) { // This is a site local routing, even though this is a sink // with a dedicated interconnect. continue; } - // Do fast routing check to see if the pair of driver and sink - // every are valid. - if(iter->second.count(driver_type_bel_pin) == 0) { - if(ctx->verbose) { - log_info("BEL %s is not valid because pin %s cannot be driven by %s/%s\n", - ctx->nameOfBel(bel), - bel_pin.c_str(ctx), - ctx->nameOfBel(driver_bel), - driver_type_bel_pin.type_bel_pin.bel_pin.c_str(ctx)); + DeltaTileTypeBelPin sink_type_bel_pin; + sink_type_bel_pin.delta_x = sink_loc.x - driver_loc.x; + sink_type_bel_pin.delta_y = sink_loc.y - driver_loc.y; + sink_type_bel_pin.type_bel_pin.tile_type = ctx->chip_info->tiles[sink_bel.tile].type; + sink_type_bel_pin.type_bel_pin.bel_index = sink_bel.index; + + for(IdString sink_bel_pin : ctx->getBelPinsForCellPin(port_ref.cell, port_ref.port)) { + sink_type_bel_pin.type_bel_pin.bel_pin = sink_bel_pin; + + // Do fast routing check to see if the pair of driver and sink + // every are valid. + if(iter->second.count(sink_type_bel_pin) == 0) { + if(ctx->verbose) { + log_info("BEL %s is not valid because pin %s cannot reach %s/%s\n", + ctx->nameOfBel(driver_bel), + driver_bel_pin.c_str(ctx), + ctx->nameOfBel(sink_bel), + sink_bel_pin.c_str(ctx)); + } + return false; } - return false; - } - // Do detailed routing check to ensure driver can reach sink. - // - // FIXME: This might be too slow, but it handles a case on - // SLICEL.COUT -> SLICEL.CIN has delta_y = {1, 2}, but the - // delta_y=2 case is rare. - if(!check_routing( - driver_bel, driver_type_bel_pin.type_bel_pin.bel_pin, - bel, bel_pin)) { - if(ctx->verbose) { - log_info("BEL %s is not valid because pin %s cannot be driven by %s/%s (via detailed check)\n", - ctx->nameOfBel(bel), - bel_pin.c_str(ctx), - ctx->nameOfBel(driver_bel), - driver_type_bel_pin.type_bel_pin.bel_pin.c_str(ctx)); + // Do detailed routing check to ensure driver can reach sink. + // + // FIXME: This might be too slow, but it handles a case on + // SLICEL.COUT -> SLICEL.CIN has delta_y = {1, 2}, but the + // delta_y=2 case is rare. + if(!check_routing( + driver_bel, driver_bel_pin, + sink_bel, sink_bel_pin)) { + if(ctx->verbose) { + log_info("BEL %s is not valid because pin %s cannot be reach %s/%s (via detailed check)\n", + ctx->nameOfBel(driver_bel), + driver_bel_pin.c_str(ctx), + ctx->nameOfBel(sink_bel), + sink_bel_pin.c_str(ctx)); + } + return false; } + } + } + } + + return true; +} + +bool DedicatedInterconnect::is_sink_on_net_valid(BelId bel, const CellInfo* cell, IdString port_name, NetInfo *net) const { + BelId driver_bel = net->driver.cell->bel; + if(driver_bel == BelId()) { + return true; + } + + const auto &bel_data = bel_info(ctx->chip_info, bel); + const auto &driver_bel_data = bel_info(ctx->chip_info, driver_bel); + + Loc bel_loc = ctx->getBelLocation(bel); + Loc driver_loc = ctx->getBelLocation(driver_bel); + + DeltaTileTypeBelPin driver_type_bel_pin; + driver_type_bel_pin.delta_x = driver_loc.x - bel_loc.x; + driver_type_bel_pin.delta_y = driver_loc.y - bel_loc.y; + driver_type_bel_pin.type_bel_pin.tile_type = ctx->chip_info->tiles[driver_bel.tile].type; + driver_type_bel_pin.type_bel_pin.bel_index = driver_bel.index; + driver_type_bel_pin.type_bel_pin.bel_pin = get_only_value(ctx->getBelPinsForCellPin(net->driver.cell, net->driver.port)); + + for(IdString bel_pin : ctx->getBelPinsForCellPin(cell, port_name)) { + TileTypeBelPin type_bel_pin; + type_bel_pin.tile_type = ctx->chip_info->tiles[bel.tile].type; + type_bel_pin.bel_index = bel.index; + type_bel_pin.bel_pin = bel_pin; + + auto iter = sinks.find(type_bel_pin); + if(iter == sinks.end()) { + // This BEL pin doesn't have a dedicate interconnect. + continue; + } + + if(bel.tile == driver_bel.tile && bel_data.site == driver_bel_data.site) { + // This is a site local routing, even though this is a sink + // with a dedicated interconnect. + continue; + } + + // Do fast routing check to see if the pair of driver and sink + // every are valid. + if(iter->second.count(driver_type_bel_pin) == 0) { + if(ctx->verbose) { + log_info("BEL %s is not valid because pin %s cannot be driven by %s/%s\n", + ctx->nameOfBel(bel), + bel_pin.c_str(ctx), + ctx->nameOfBel(driver_bel), + driver_type_bel_pin.type_bel_pin.bel_pin.c_str(ctx)); + } + return false; + } + + // Do detailed routing check to ensure driver can reach sink. + // + // FIXME: This might be too slow, but it handles a case on + // SLICEL.COUT -> SLICEL.CIN has delta_y = {1, 2}, but the + // delta_y=2 case is rare. + if(!check_routing( + driver_bel, driver_type_bel_pin.type_bel_pin.bel_pin, + bel, bel_pin)) { + if(ctx->verbose) { + log_info("BEL %s is not valid because pin %s cannot be driven by %s/%s (via detailed check)\n", + ctx->nameOfBel(bel), + bel_pin.c_str(ctx), + ctx->nameOfBel(driver_bel), + driver_type_bel_pin.type_bel_pin.bel_pin.c_str(ctx)); + } + return false; + } + } + + return true; +} + +bool DedicatedInterconnect::isBelLocationValid(BelId bel, const CellInfo* cell) const { + NPNR_ASSERT(bel != BelId()); + + for(const auto &port_pair : cell->ports) { + IdString port_name = port_pair.first; + NetInfo *net = port_pair.second.net; + if(net == nullptr) { + continue; + } + + // This net doesn't have a driver, probably not valid? + NPNR_ASSERT(net->driver.cell != nullptr); + + // Only check sink BELs. + if(net->driver.cell == cell && net->driver.port == port_name) { + if(!is_driver_on_net_valid(bel, cell, port_name, net)) { + return false; + } + } else { + if(!is_sink_on_net_valid(bel, cell, port_name, net)) { return false; } } @@ -137,37 +359,83 @@ bool DedicatedInterconnect::isBelLocationValid(BelId bel, const CellInfo* cell) } void DedicatedInterconnect::print_dedicated_interconnect() const { - log_info("Found %zu sinks with dedicated interconnect\n", pins_with_dedicate_interconnect.size()); + log_info("Found %zu sinks with dedicated interconnect\n", sinks.size()); + log_info("Found %zu sources with dedicated interconnect\n", sources.size()); std::vector sorted_keys; - for(const auto & sink_to_srcs : pins_with_dedicate_interconnect) { + for(const auto & sink_to_srcs : sinks) { sorted_keys.push_back(sink_to_srcs.first); } + for(const auto & src_to_sinks : sources) { + sorted_keys.push_back(src_to_sinks.first); + } std::sort(sorted_keys.begin(), sorted_keys.end()); - for(const auto & dst : sorted_keys) { - for(const auto & src : pins_with_dedicate_interconnect.at(dst)) { - const TileTypeInfoPOD & src_tile_type = ctx->chip_info->tile_types[src.type_bel_pin.tile_type]; - const BelInfoPOD & src_bel_info = src_tile_type.bel_data[src.type_bel_pin.bel_index]; - IdString src_site_type = IdString(src_tile_type.site_types[src_bel_info.site]); - IdString src_bel_pin = src.type_bel_pin.bel_pin; - - const TileTypeInfoPOD & dst_tile_type = ctx->chip_info->tile_types[dst.tile_type]; - const BelInfoPOD & dst_bel_info = dst_tile_type.bel_data[dst.bel_index]; - IdString dst_site_type = IdString(dst_tile_type.site_types[dst_bel_info.site]); - IdString dst_bel_pin = dst.bel_pin; - - log_info("%s.%s/%s/%s (%d, %d) -> %s.%s/%s/%s\n", - IdString(src_tile_type.name).c_str(ctx), - src_site_type.c_str(ctx), - IdString(src_bel_info.name).c_str(ctx), - src_bel_pin.c_str(ctx), - src.delta_x, - src.delta_y, - IdString(dst_tile_type.name).c_str(ctx), - dst_site_type.c_str(ctx), - IdString(dst_bel_info.name).c_str(ctx), - dst_bel_pin.c_str(ctx)); + for(const auto & key : sorted_keys) { + auto iter = sinks.find(key); + if(iter != sinks.end()) { + auto dst = key; + for(const auto & src_delta : iter->second) { + auto src = src_delta.type_bel_pin; + auto delta_x = src_delta.delta_x; + auto delta_y = src_delta.delta_y; + + const TileTypeInfoPOD & src_tile_type = ctx->chip_info->tile_types[src.tile_type]; + const BelInfoPOD & src_bel_info = src_tile_type.bel_data[src.bel_index]; + IdString src_site_type = IdString(src_tile_type.site_types[src_bel_info.site]); + IdString src_bel_pin = src.bel_pin; + + const TileTypeInfoPOD & dst_tile_type = ctx->chip_info->tile_types[dst.tile_type]; + const BelInfoPOD & dst_bel_info = dst_tile_type.bel_data[dst.bel_index]; + IdString dst_site_type = IdString(dst_tile_type.site_types[dst_bel_info.site]); + IdString dst_bel_pin = dst.bel_pin; + + log_info("%s.%s[%d]/%s/%s (%d, %d) -> %s.%s[%d]/%s/%s\n", + IdString(src_tile_type.name).c_str(ctx), + src_site_type.c_str(ctx), + src_bel_info.site, + IdString(src_bel_info.name).c_str(ctx), + src_bel_pin.c_str(ctx), + delta_x, + delta_y, + IdString(dst_tile_type.name).c_str(ctx), + dst_site_type.c_str(ctx), + dst_bel_info.site, + IdString(dst_bel_info.name).c_str(ctx), + dst_bel_pin.c_str(ctx)); + } + } else { + auto src = key; + for(const auto & dst_delta : sources.at(key)) { + auto dst = dst_delta.type_bel_pin; + auto delta_x = dst_delta.delta_x; + auto delta_y = dst_delta.delta_y; + + const TileTypeInfoPOD & src_tile_type = ctx->chip_info->tile_types[src.tile_type]; + const BelInfoPOD & src_bel_info = src_tile_type.bel_data[src.bel_index]; + IdString src_site_type = IdString(src_tile_type.site_types[src_bel_info.site]); + IdString src_bel_pin = src.bel_pin; + + const TileTypeInfoPOD & dst_tile_type = ctx->chip_info->tile_types[dst.tile_type]; + const BelInfoPOD & dst_bel_info = dst_tile_type.bel_data[dst.bel_index]; + IdString dst_site_type = IdString(dst_tile_type.site_types[dst_bel_info.site]); + IdString dst_bel_pin = dst.bel_pin; + + log_info("%s.%s[%d]/%s/%s -> %s.%s[%d]/%s/%s (%d, %d)\n", + IdString(src_tile_type.name).c_str(ctx), + src_site_type.c_str(ctx), + src_bel_info.site, + IdString(src_bel_info.name).c_str(ctx), + src_bel_pin.c_str(ctx), + IdString(dst_tile_type.name).c_str(ctx), + dst_site_type.c_str(ctx), + dst_bel_info.site, + IdString(dst_bel_info.name).c_str(ctx), + dst_bel_pin.c_str(ctx), + delta_x, + delta_y); + + } } } } @@ -191,53 +459,72 @@ void DedicatedInterconnect::find_dedicated_interconnect() { wire.tile = bel.tile; wire.index = bel_data.wires[i]; - expand_bel(bel, IdString(bel_data.ports[i]), wire); + expand_sink_bel(bel, IdString(bel_data.ports[i]), wire); } } -} -// All legal routes involved at most 2 sites, the source site and the sink -// site. The source site and sink sites may be the same, but that is not -// dedicated routing, that is intra site routing. -// -// Dedicated routing must leave the sink site, traverse some routing and -// terminate at another site. Routing that "flys" over a site is expressed as -// a psuedo-pip connected the relevant site pin wires, rather than traversing -// the site. -enum WireNodeState { - IN_SINK_SITE = 0, - IN_ROUTING = 1, - IN_SOURCE_SITE = 2 -}; + std::unordered_set seen_pins; + for(auto sink_pair : sinks) { + for(auto src : sink_pair.second) { + seen_pins.emplace(src.type_bel_pin); + } + } -struct WireNode { - WireId wire; - WireNodeState state; - int depth; -}; + for(BelId bel : ctx->getBels()) { + const auto & bel_data = bel_info(ctx->chip_info, bel); + if(bel_data.category != BEL_CATEGORY_LOGIC) { + continue; + } + if(bel_data.synthetic) { + continue; + } -// Maximum depth that a dedicate interconnect is considered. -// -// Routing networks with depth <= kMaxDepth is considers a dedicated -// interconnect. -constexpr int kMaxDepth = 20; + for(size_t i = 0; i < bel_data.num_bel_wires; ++i) { + if(bel_data.types[i] != PORT_OUT) { + continue; + } -void DedicatedInterconnect::expand_bel(BelId bel, IdString pin, WireId wire) { - NPNR_ASSERT(bel != BelId()); + + IdString bel_pin(bel_data.ports[i]); + + TileTypeBelPin type_bel_pin; + type_bel_pin.tile_type = ctx->chip_info->tiles[bel.tile].type; + type_bel_pin.bel_index = bel.index; + type_bel_pin.bel_pin = bel_pin; + + // Don't visit src pins already handled in the sink expansion! + if(seen_pins.count(type_bel_pin)) { + continue; + } + + WireId wire; + wire.tile = bel.tile; + wire.index = bel_data.wires[i]; + + expand_source_bel(bel, bel_pin, wire); + } + } +} + +void DedicatedInterconnect::expand_sink_bel(BelId sink_bel, IdString sink_pin, WireId sink_wire) { + NPNR_ASSERT(sink_bel != BelId()); +#ifdef DEBUG_EXPANSION + log_info("Expanding from %s/%s\n", ctx->nameOfBel(sink_bel), pin.c_str(ctx)); +#endif std::vector nodes_to_expand; - const auto & src_wire_data = ctx->wire_info(wire); - NPNR_ASSERT(src_wire_data.site != -1); + const auto & sink_wire_data = ctx->wire_info(sink_wire); + NPNR_ASSERT(sink_wire_data.site != -1); WireNode wire_node; - wire_node.wire = wire; + wire_node.wire = sink_wire; wire_node.state = IN_SINK_SITE; wire_node.depth = 0; nodes_to_expand.push_back(wire_node); - Loc sink_loc = ctx->getBelLocation(bel); + Loc sink_loc = ctx->getBelLocation(sink_bel); std::unordered_set srcs; while(!nodes_to_expand.empty()) { @@ -254,6 +541,11 @@ void DedicatedInterconnect::expand_bel(BelId bel, IdString pin, WireId wire) { continue; } +#ifdef DEBUG_EXPANSION + log_info(" - At wire %s via %s\n", + ctx->nameOfWire(wire), ctx->nameOfPip(pip)); +#endif + WireNode next_node; next_node.wire = wire; next_node.depth = node_to_expand.depth += 1; @@ -277,9 +569,12 @@ void DedicatedInterconnect::expand_bel(BelId bel, IdString pin, WireId wire) { break; case IN_ROUTING: NPNR_ASSERT(wire_data.site != -1); - if(wire_data.site == src_wire_data.site) { + if(wire.tile == sink_wire.tile && wire_data.site == sink_wire_data.site) { // Dedicated routing won't have straight loops, // general routing looks like that. +#ifdef DEBUG_EXPANSION + log_info(" - Not dedicated site routing because loop!"); +#endif return; } next_node.state = IN_SOURCE_SITE; @@ -307,7 +602,6 @@ void DedicatedInterconnect::expand_bel(BelId bel, IdString pin, WireId wire) { for(BelPin bel_pin : ctx->getWireBelPins(wire)) { BelId src_bel = bel_pin.bel; auto const & bel_data = bel_info(ctx->chip_info, src_bel); - NPNR_ASSERT(bel_data.site != src_wire_data.site); if(bel_data.category != BEL_CATEGORY_LOGIC) { continue; @@ -319,11 +613,15 @@ void DedicatedInterconnect::expand_bel(BelId bel, IdString pin, WireId wire) { continue; } +#ifdef DEBUG_EXPANSION + log_info(" - Reached %s/%s\n", ctx->nameOfBel(bel_pin.bel), bel_pin.pin.c_str(ctx)); +#endif + Loc src_loc = ctx->getBelLocation(src_bel); DeltaTileTypeBelPin delta_type_bel_pin; delta_type_bel_pin.delta_x = src_loc.x - sink_loc.x; - delta_type_bel_pin.delta_x = src_loc.y - sink_loc.y; + delta_type_bel_pin.delta_y = src_loc.y - sink_loc.y; delta_type_bel_pin.type_bel_pin.tile_type = ctx->chip_info->tiles[src_bel.tile].type; delta_type_bel_pin.type_bel_pin.bel_index = src_bel.index; delta_type_bel_pin.type_bel_pin.bel_pin = bel_pin.pin; @@ -334,11 +632,11 @@ void DedicatedInterconnect::expand_bel(BelId bel, IdString pin, WireId wire) { } TileTypeBelPin type_bel_pin; - type_bel_pin.tile_type = ctx->chip_info->tiles[bel.tile].type; - type_bel_pin.bel_index = bel.index; - type_bel_pin.bel_pin = pin; + type_bel_pin.tile_type = ctx->chip_info->tiles[sink_bel.tile].type; + type_bel_pin.bel_index = sink_bel.index; + type_bel_pin.bel_pin = sink_pin; - auto result = pins_with_dedicate_interconnect.emplace(type_bel_pin, srcs); + auto result = sinks.emplace(type_bel_pin, srcs); if(!result.second) { // type_bel_pin was already present! Add any new sources from this // sink type (if any); @@ -348,4 +646,144 @@ void DedicatedInterconnect::expand_bel(BelId bel, IdString pin, WireId wire) { } } +void DedicatedInterconnect::expand_source_bel(BelId src_bel, IdString src_pin, WireId src_wire) { + NPNR_ASSERT(src_bel != BelId()); +#ifdef DEBUG_EXPANSION + log_info("Expanding from %s/%s\n", ctx->nameOfBel(src_bel), pin.c_str(ctx)); +#endif + + std::vector nodes_to_expand; + + const auto & src_wire_data = ctx->wire_info(src_wire); + NPNR_ASSERT(src_wire_data.site != -1); + + WireNode wire_node; + wire_node.wire = src_wire; + wire_node.state = IN_SOURCE_SITE; + wire_node.depth = 0; + + nodes_to_expand.push_back(wire_node); + + Loc src_loc = ctx->getBelLocation(src_bel); + std::unordered_set dsts; + + while(!nodes_to_expand.empty()) { + WireNode node_to_expand = nodes_to_expand.back(); + nodes_to_expand.pop_back(); + + for(PipId pip : ctx->getPipsDownhill(node_to_expand.wire)) { + if(ctx->is_pip_synthetic(pip)) { + continue; + } + + WireId wire = ctx->getPipDstWire(pip); + if(wire == WireId()) { + continue; + } + +#ifdef DEBUG_EXPANSION + log_info(" - At wire %s via %s\n", + ctx->nameOfWire(wire), ctx->nameOfPip(pip)); +#endif + + WireNode next_node; + next_node.wire = wire; + next_node.depth = node_to_expand.depth += 1; + + if(next_node.depth > kMaxDepth) { + // Dedicated routing should reach sources by kMaxDepth (with + // tuning). + // + // FIXME: Consider removing kMaxDepth and use kMaxSources? + return; + } + + auto const & wire_data = ctx->wire_info(wire); + + bool expand_node = true; + if(ctx->is_site_port(pip)) { + switch(node_to_expand.state) { + case IN_SOURCE_SITE: + NPNR_ASSERT(wire_data.site == -1); + next_node.state = IN_ROUTING; + break; + case IN_ROUTING: + NPNR_ASSERT(wire_data.site != -1); + if(wire.tile == src_wire.tile && wire_data.site == src_wire_data.site) { + // Dedicated routing won't have straight loops, + // general routing looks like that. +#ifdef DEBUG_EXPANSION + log_info(" - Not dedicated site routing because loop!"); +#endif + return; + } + next_node.state = IN_SINK_SITE; + break; + case IN_SINK_SITE: + // Once entering a site, do not leave it again. + // This path is not a legal route! + expand_node = false; + break; + default: + // Unreachable!!! + NPNR_ASSERT(false); + } + } else { + next_node.state = node_to_expand.state; + } + + if(expand_node) { + nodes_to_expand.push_back(next_node); + } else { + continue; + } + + if(next_node.state == IN_SINK_SITE) { + for(BelPin bel_pin : ctx->getWireBelPins(wire)) { + BelId sink_bel = bel_pin.bel; + auto const & bel_data = bel_info(ctx->chip_info, sink_bel); + + if(bel_data.category != BEL_CATEGORY_LOGIC) { + continue; + } + if(bel_data.synthetic) { + continue; + } + if(ctx->getBelPinType(bel_pin.bel, bel_pin.pin) != PORT_IN) { + continue; + } + +#ifdef DEBUG_EXPANSION + log_info(" - Reached %s/%s\n", ctx->nameOfBel(bel_pin.bel), bel_pin.pin.c_str(ctx)); +#endif + + Loc sink_loc = ctx->getBelLocation(sink_bel); + + DeltaTileTypeBelPin delta_type_bel_pin; + delta_type_bel_pin.delta_x = sink_loc.x - src_loc.x; + delta_type_bel_pin.delta_y = sink_loc.y - src_loc.y; + delta_type_bel_pin.type_bel_pin.tile_type = ctx->chip_info->tiles[sink_bel.tile].type; + delta_type_bel_pin.type_bel_pin.bel_index = sink_bel.index; + delta_type_bel_pin.type_bel_pin.bel_pin = bel_pin.pin; + dsts.emplace(delta_type_bel_pin); + } + } + } + } + + TileTypeBelPin type_bel_pin; + type_bel_pin.tile_type = ctx->chip_info->tiles[src_bel.tile].type; + type_bel_pin.bel_index = src_bel.index; + type_bel_pin.bel_pin = src_pin; + + auto result = sinks.emplace(type_bel_pin, dsts); + if(!result.second) { + // type_bel_pin was already present! Add any new sources from this + // sink type (if any); + for(auto dst : dsts) { + result.first->second.emplace(dst); + } + } +} + NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/dedicated_interconnect.h b/fpga_interchange/dedicated_interconnect.h index 5fe61d30..d603039e 100644 --- a/fpga_interchange/dedicated_interconnect.h +++ b/fpga_interchange/dedicated_interconnect.h @@ -108,7 +108,8 @@ struct Context; struct DedicatedInterconnect { const Context *ctx; - std::unordered_map> pins_with_dedicate_interconnect; + std::unordered_map> sinks; + std::unordered_map> sources; void init(const Context *ctx); @@ -123,7 +124,13 @@ struct DedicatedInterconnect { bool check_routing( BelId src_bel, IdString src_bel_pin, BelId dst_bel, IdString dst_bel_pin) const; - void expand_bel(BelId bel, IdString pin, WireId wire); + void expand_sink_bel(BelId bel, IdString pin, WireId wire); + void expand_source_bel(BelId bel, IdString pin, WireId wire); + + bool is_driver_on_net_valid(BelId driver_bel, + const CellInfo* cell, IdString driver_port, NetInfo *net) const; + bool is_sink_on_net_valid(BelId bel, const CellInfo* cell, + IdString port_name, NetInfo *net) const; }; NEXTPNR_NAMESPACE_END -- cgit v1.2.3 From a30043c8da1b1cc46a2dcfb90aa3a06d4f4ed4e9 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Tue, 23 Feb 2021 13:35:45 -0800 Subject: Fix assorted bugs in FPGA interchange. Fixes: - Only use map constant pins during routing, and not during placement. - Unmapped cell ports have no BEL pins. - Fix SiteRouter congestion not taking into account initial expansion. - Fix psuedo-site pip output. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- fpga_interchange/arch.cc | 243 ++++++++----- fpga_interchange/arch.h | 54 ++- fpga_interchange/arch_pack_io.cc | 4 +- fpga_interchange/dedicated_interconnect.cc | 524 ++++++++++++++--------------- fpga_interchange/dedicated_interconnect.h | 40 ++- fpga_interchange/fpga_interchange.cpp | 52 ++- fpga_interchange/site_router.cc | 86 ++++- fpga_interchange/site_router.h | 45 +++ 8 files changed, 626 insertions(+), 422 deletions(-) create mode 100644 fpga_interchange/site_router.h diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc index 776fbdb0..dc99f1cd 100644 --- a/fpga_interchange/arch.cc +++ b/fpga_interchange/arch.cc @@ -195,10 +195,7 @@ Arch::Arch(ArchArgs args) : args(args) default_tags.resize(max_tag_count); } - -void Arch::init() { - dedicated_interconnect.init(getCtx()); -} +void Arch::init() { dedicated_interconnect.init(getCtx()); } // ----------------------------------------------------------------------- @@ -615,6 +612,14 @@ bool Arch::place() { std::string placer = str_or_default(settings, id("placer"), defaultPlacer); + // Re-map BEL pins without constant pins + for (BelId bel : getBels()) { + CellInfo *cell = getBoundBelCell(bel); + if (cell != nullptr && cell->cell_mapping != -1) { + map_cell_pins(cell, cell->cell_mapping, /*bind_constants=*/false); + } + } + if (placer == "heap") { PlacerHeapCfg cfg(getCtx()); cfg.criticalityExponent = 7; @@ -644,6 +649,14 @@ bool Arch::route() { std::string router = str_or_default(settings, id("router"), defaultRouter); + // Re-map BEL pins with constant pins + for (BelId bel : getBels()) { + CellInfo *cell = getBoundBelCell(bel); + if (cell != nullptr && cell->cell_mapping != -1) { + map_cell_pins(cell, cell->cell_mapping, /*bind_constants=*/true); + } + } + bool result; if (router == "router1") { result = router1(getCtx(), Router1Cfg(getCtx())); @@ -683,13 +696,33 @@ DecalXY Arch::getGroupDecal(GroupId pip) const { return {}; }; delay_t Arch::estimateDelay(WireId src, WireId dst) const { // FIXME: Implement something to push the A* router in the right direction. - return 0; + int src_x, src_y; + get_tile_x_y(src.tile, &src_x, &src_y); + + int dst_x, dst_y; + get_tile_x_y(dst.tile, &dst_x, &dst_y); + + delay_t base = 30 * std::min(std::abs(dst_x - src_x), 18) + 10 * std::max(std::abs(dst_x - src_x) - 18, 0) + + 60 * std::min(std::abs(dst_y - src_y), 6) + 20 * std::max(std::abs(dst_y - src_y) - 6, 0) + 300; + + base = (base * 3) / 2; + return base; } delay_t Arch::predictDelay(const NetInfo *net_info, const PortRef &sink) const { // FIXME: Implement when adding timing-driven place and route. - return 0; + int src_x, src_y; + get_tile_x_y(net_info->driver.cell->bel.tile, &src_x, &src_y); + + int dst_x, dst_y; + get_tile_x_y(sink.cell->bel.tile, &dst_x, &dst_y); + + delay_t base = 30 * std::min(std::abs(dst_x - src_x), 18) + 10 * std::max(std::abs(dst_x - src_x) - 18, 0) + + 60 * std::min(std::abs(dst_y - src_y), 6) + 20 * std::max(std::abs(dst_y - src_y) - 6, 0) + 300; + + base = (base * 3) / 2; + return base; } bool Arch::getCellDelay(const CellInfo *cell, IdString fromPort, IdString toPort, DelayQuad &delay) const @@ -755,57 +788,64 @@ const std::vector Arch::availablePlacers = {"sa", const std::string Arch::defaultRouter = "router2"; const std::vector Arch::availableRouters = {"router1", "router2"}; -void Arch::map_cell_pins(CellInfo *cell, int32_t mapping) +void Arch::map_cell_pins(CellInfo *cell, int32_t mapping, bool bind_constants) { cell->cell_mapping = mapping; cell->cell_bel_pins.clear(); + for (IdString const_port : cell->const_ports) { + NPNR_ASSERT(cell->ports.erase(const_port)); + } const CellBelMapPOD &cell_pin_map = chip_info->cell_map->cell_bel_map[mapping]; + IdString gnd_net_name(chip_info->constants->gnd_net_name); + IdString vcc_net_name(chip_info->constants->vcc_net_name); + for (const auto &pin_map : cell_pin_map.common_pins) { IdString cell_pin(pin_map.cell_pin); IdString bel_pin(pin_map.bel_pin); if (cell_pin.str(this) == "GND") { - IdString gnd_net_name(chip_info->constants->gnd_net_name); - - PortInfo port_info; - port_info.name = bel_pin; - port_info.type = PORT_IN; - port_info.net = nullptr; + if (bind_constants) { + PortInfo port_info; + port_info.name = bel_pin; + port_info.type = PORT_IN; + port_info.net = nullptr; - auto result = cell->ports.emplace(bel_pin, port_info); - if(result.second) { - cell->cell_bel_pins[bel_pin].push_back(bel_pin); - connectPort(gnd_net_name, cell->name, bel_pin); - } else { - NPNR_ASSERT(result.first->second.net == getNetByAlias(gnd_net_name)); - auto result2 = cell->cell_bel_pins.emplace(bel_pin, std::vector({bel_pin})); - NPNR_ASSERT(result2.first->second.at(0) == bel_pin); - NPNR_ASSERT(result2.first->second.size() == 1); + auto result = cell->ports.emplace(bel_pin, port_info); + if (result.second) { + cell->cell_bel_pins[bel_pin].push_back(bel_pin); + connectPort(gnd_net_name, cell->name, bel_pin); + cell->const_ports.emplace(bel_pin); + } else { + NPNR_ASSERT(result.first->second.net == getNetByAlias(gnd_net_name)); + auto result2 = cell->cell_bel_pins.emplace(bel_pin, std::vector({bel_pin})); + NPNR_ASSERT(result2.first->second.at(0) == bel_pin); + NPNR_ASSERT(result2.first->second.size() == 1); + } } continue; } if (cell_pin.str(this) == "VCC") { - IdString vcc_net_name(chip_info->constants->vcc_net_name); - - PortInfo port_info; - port_info.name = bel_pin; - port_info.type = PORT_IN; - port_info.net = nullptr; + if (bind_constants) { + PortInfo port_info; + port_info.name = bel_pin; + port_info.type = PORT_IN; + port_info.net = nullptr; - auto result = cell->ports.emplace(bel_pin, port_info); - if(result.second) { - cell->cell_bel_pins[bel_pin].push_back(bel_pin); - connectPort(vcc_net_name, cell->name, bel_pin); - } else { - NPNR_ASSERT(result.first->second.net == getNetByAlias(vcc_net_name)); - auto result2 = cell->cell_bel_pins.emplace(bel_pin, std::vector({bel_pin})); - NPNR_ASSERT(result2.first->second.at(0) == bel_pin); - NPNR_ASSERT(result2.first->second.size() == 1); + auto result = cell->ports.emplace(bel_pin, port_info); + if (result.second) { + cell->cell_bel_pins[bel_pin].push_back(bel_pin); + connectPort(vcc_net_name, cell->name, bel_pin); + cell->const_ports.emplace(bel_pin); + } else { + NPNR_ASSERT(result.first->second.net == getNetByAlias(vcc_net_name)); + auto result2 = cell->cell_bel_pins.emplace(bel_pin, std::vector({bel_pin})); + NPNR_ASSERT(result2.first->second.at(0) == bel_pin); + NPNR_ASSERT(result2.first->second.size() == 1); + } } - continue; } @@ -830,30 +870,44 @@ void Arch::map_cell_pins(CellInfo *cell, int32_t mapping) IdString bel_pin(pin_map.bel_pin); if (cell_pin.str(this) == "GND") { - PortInfo port_info; - port_info.name = bel_pin; - port_info.type = PORT_IN; - - auto result = cell->ports.emplace(bel_pin, port_info); - NPNR_ASSERT(result.second); - - cell->cell_bel_pins[bel_pin].push_back(bel_pin); - - connectPort(IdString(chip_info->constants->gnd_net_name), cell->name, bel_pin); + if (bind_constants) { + PortInfo port_info; + port_info.name = bel_pin; + port_info.type = PORT_IN; + + auto result = cell->ports.emplace(bel_pin, port_info); + if (result.second) { + cell->cell_bel_pins[bel_pin].push_back(bel_pin); + connectPort(gnd_net_name, cell->name, bel_pin); + cell->const_ports.emplace(bel_pin); + } else { + NPNR_ASSERT(result.first->second.net == getNetByAlias(gnd_net_name)); + auto result2 = cell->cell_bel_pins.emplace(bel_pin, std::vector({bel_pin})); + NPNR_ASSERT(result2.first->second.at(0) == bel_pin); + NPNR_ASSERT(result2.first->second.size() == 1); + } + } continue; } if (cell_pin.str(this) == "VCC") { - PortInfo port_info; - port_info.name = bel_pin; - port_info.type = PORT_IN; - - auto result = cell->ports.emplace(bel_pin, port_info); - NPNR_ASSERT(result.second); - - cell->cell_bel_pins[bel_pin].push_back(bel_pin); - - connectPort(IdString(chip_info->constants->vcc_net_name), cell->name, bel_pin); + if (bind_constants) { + PortInfo port_info; + port_info.name = bel_pin; + port_info.type = PORT_IN; + + auto result = cell->ports.emplace(bel_pin, port_info); + if (result.second) { + cell->cell_bel_pins[bel_pin].push_back(bel_pin); + connectPort(vcc_net_name, cell->name, bel_pin); + cell->const_ports.emplace(bel_pin); + } else { + NPNR_ASSERT(result.first->second.net == getNetByAlias(vcc_net_name)); + auto result2 = cell->cell_bel_pins.emplace(bel_pin, std::vector({bel_pin})); + NPNR_ASSERT(result2.first->second.at(0) == bel_pin); + NPNR_ASSERT(result2.first->second.size() == 1); + } + } continue; } @@ -912,9 +966,10 @@ size_t Arch::get_cell_type_index(IdString cell_type) const return cell_offset; } -void Arch::merge_constant_nets() { - NetInfo* gnd_net = nullptr; - NetInfo* vcc_net = nullptr; +void Arch::merge_constant_nets() +{ + NetInfo *gnd_net = nullptr; + NetInfo *vcc_net = nullptr; bool need_gnd_source = false; bool need_vcc_source = false; @@ -924,7 +979,7 @@ void Arch::merge_constant_nets() { IdString gnd_cell_port(chip_info->constants->gnd_cell_port); auto gnd_iter = nets.find(gnd_net_name); - if(gnd_iter != nets.end()) { + if (gnd_iter != nets.end()) { NPNR_ASSERT(gnd_iter->second->driver.cell != nullptr); NPNR_ASSERT(gnd_iter->second->driver.cell->type == gnd_cell_type); NPNR_ASSERT(gnd_iter->second->driver.port == gnd_cell_port); @@ -940,7 +995,7 @@ void Arch::merge_constant_nets() { IdString vcc_cell_port(chip_info->constants->vcc_cell_port); auto vcc_iter = nets.find(vcc_net_name); - if(vcc_iter != nets.end()) { + if (vcc_iter != nets.end()) { NPNR_ASSERT(vcc_iter->second->driver.cell != nullptr); NPNR_ASSERT(vcc_iter->second->driver.cell->type == vcc_cell_type); NPNR_ASSERT(vcc_iter->second->driver.port == vcc_cell_port); @@ -954,28 +1009,28 @@ void Arch::merge_constant_nets() { std::vector other_gnd_nets; std::vector other_vcc_nets; - for(auto & net_pair : nets) { - if(net_pair.first == gnd_net_name) { + for (auto &net_pair : nets) { + if (net_pair.first == gnd_net_name) { NPNR_ASSERT(net_pair.second.get() == gnd_net); continue; } - if(net_pair.first == vcc_net_name) { + if (net_pair.first == vcc_net_name) { NPNR_ASSERT(net_pair.second.get() == vcc_net); continue; } NetInfo *net = net_pair.second.get(); - if(net->driver.cell == nullptr) { + if (net->driver.cell == nullptr) { continue; } - if(net->driver.cell->type == gnd_cell_type) { + if (net->driver.cell->type == gnd_cell_type) { NPNR_ASSERT(net->driver.port == gnd_cell_port); other_gnd_nets.push_back(net_pair.first); - if(need_gnd_source) { + if (need_gnd_source) { IdString driver_cell = net->driver.cell->name; disconnectPort(driver_cell, gnd_cell_port); connectPort(gnd_net_name, driver_cell, gnd_cell_port); @@ -984,7 +1039,7 @@ void Arch::merge_constant_nets() { NPNR_ASSERT(net->driver.port == gnd_cell_port); std::vector users_copy = net->users; - for(const PortRef & port_ref : users_copy) { + for (const PortRef &port_ref : users_copy) { IdString cell = port_ref.cell->name; disconnectPort(cell, port_ref.port); connectPort(gnd_net_name, cell, port_ref.port); @@ -993,12 +1048,12 @@ void Arch::merge_constant_nets() { continue; } - if(net->driver.cell->type == vcc_cell_type) { + if (net->driver.cell->type == vcc_cell_type) { NPNR_ASSERT(net->driver.port == vcc_cell_port); other_vcc_nets.push_back(net_pair.first); - if(need_vcc_source) { + if (need_vcc_source) { IdString driver_cell = net->driver.cell->name; disconnectPort(driver_cell, vcc_cell_port); connectPort(vcc_net_name, driver_cell, vcc_cell_port); @@ -1007,7 +1062,7 @@ void Arch::merge_constant_nets() { NPNR_ASSERT(net->driver.port == vcc_cell_port); std::vector users_copy = net->users; - for(const PortRef & port_ref : users_copy) { + for (const PortRef &port_ref : users_copy) { IdString cell = port_ref.cell->name; disconnectPort(cell, port_ref.port); connectPort(vcc_net_name, cell, port_ref.port); @@ -1015,10 +1070,10 @@ void Arch::merge_constant_nets() { } } - for(IdString other_gnd_net : other_gnd_nets) { - NetInfo * net = getNetByAlias(other_gnd_net); + for (IdString other_gnd_net : other_gnd_nets) { + NetInfo *net = getNetByAlias(other_gnd_net); NPNR_ASSERT(net->users.empty()); - if(net->driver.cell) { + if (net->driver.cell) { PortRef driver = net->driver; IdString cell_to_remove = driver.cell->name; disconnectPort(driver.cell->name, driver.port); @@ -1026,10 +1081,10 @@ void Arch::merge_constant_nets() { } } - for(IdString other_vcc_net : other_vcc_nets) { - NetInfo * net = getNetByAlias(other_vcc_net); + for (IdString other_vcc_net : other_vcc_nets) { + NetInfo *net = getNetByAlias(other_vcc_net); NPNR_ASSERT(net->users.empty()); - if(net->driver.cell) { + if (net->driver.cell) { PortRef driver = net->driver; IdString cell_to_remove = driver.cell->name; disconnectPort(driver.cell->name, driver.port); @@ -1037,31 +1092,49 @@ void Arch::merge_constant_nets() { } } - for(IdString other_gnd_net : other_gnd_nets) { + for (IdString other_gnd_net : other_gnd_nets) { NPNR_ASSERT(nets.erase(other_gnd_net)); gnd_net->aliases.push_back(other_gnd_net); net_aliases[other_gnd_net] = gnd_net_name; } - for(IdString other_vcc_net : other_vcc_nets) { + for (IdString other_vcc_net : other_vcc_nets) { NPNR_ASSERT(nets.erase(other_vcc_net)); vcc_net->aliases.push_back(other_vcc_net); net_aliases[other_vcc_net] = vcc_net_name; } - if(need_gnd_source) { - CellInfo * gnd_cell = createCell(gnd_cell_type, gnd_cell_type); + if (need_gnd_source) { + CellInfo *gnd_cell = createCell(gnd_cell_type, gnd_cell_type); gnd_cell->addOutput(gnd_cell_port); connectPort(gnd_net_name, gnd_cell_type, gnd_cell_port); } - if(need_vcc_source) { - CellInfo * vcc_cell = createCell(vcc_cell_type, vcc_cell_type); + if (need_vcc_source) { + CellInfo *vcc_cell = createCell(vcc_cell_type, vcc_cell_type); vcc_cell->addOutput(vcc_cell_port); connectPort(vcc_net_name, vcc_cell_type, vcc_cell_port); } } +const std::vector &Arch::getBelPinsForCellPin(const CellInfo *cell_info, IdString pin) const +{ + auto iter = cell_info->cell_bel_pins.find(pin); + if (iter == cell_info->cell_bel_pins.end()) { + return no_pins; + } else { + return iter->second; + } +} + +void Arch::report_invalid_bel(BelId bel, CellInfo *cell) const +{ + int32_t mapping = bel_info(chip_info, bel).pin_map[get_cell_type_index(cell->type)]; + NPNR_ASSERT(mapping < 0); + log_error("Cell %s (%s) cannot be placed at BEL %s (mapping %d)\n", cell->name.c_str(this), cell->type.c_str(this), + nameOfBel(bel), mapping); +} + // Instance constraint templates. template void Arch::ArchConstraints::bindBel(Arch::ArchConstraints::TagState *, const Arch::ConstraintRange); template void Arch::ArchConstraints::unbindBel(Arch::ArchConstraints::TagState *, const Arch::ConstraintRange); diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h index c713ddb9..13cab02f 100644 --- a/fpga_interchange/arch.h +++ b/fpga_interchange/arch.h @@ -30,6 +30,7 @@ #include "constraints.h" #include "dedicated_interconnect.h" +#include "site_router.h" NEXTPNR_NAMESPACE_BEGIN @@ -773,7 +774,14 @@ struct ArchRanges using BucketBelRangeT = FilteredBelRange; }; -struct DedicatedInterconnect; +static constexpr size_t kMaxState = 8; + +struct TileStatus +{ + std::vector> tags; + std::vector boundcells; + std::vector sites; +}; struct Arch : ArchAPI { @@ -787,31 +795,6 @@ struct Arch : ArchAPI std::unordered_map wire_to_net; std::unordered_map pip_to_net; - static constexpr size_t kMaxState = 8; - - struct TileStatus; - struct SiteRouter - { - SiteRouter(int16_t site) : site(site), dirty(false), site_ok(true) {} - - std::unordered_set cells_in_site; - const int16_t site; - - mutable bool dirty; - mutable bool site_ok; - - void bindBel(CellInfo *cell); - void unbindBel(CellInfo *cell); - bool checkSiteRouting(const Context *ctx, const TileStatus &tile_status) const; - }; - - struct TileStatus - { - std::vector> tags; - std::vector boundcells; - std::vector sites; - }; - DedicatedInterconnect dedicated_interconnect; std::unordered_map tileStatus; @@ -871,7 +854,7 @@ struct Arch : ArchAPI uint32_t getBelChecksum(BelId bel) const override { return bel.index; } - void map_cell_pins(CellInfo *cell, int32_t mapping); + void map_cell_pins(CellInfo *cell, int32_t mapping, bool bind_constants); void map_port_pins(BelId bel, CellInfo *cell) const; TileStatus &get_tile_status(int32_t tile) @@ -931,10 +914,13 @@ struct Arch : ArchAPI if (io_port_types.count(cell->type) == 0) { int32_t mapping = bel_info(chip_info, bel).pin_map[get_cell_type_index(cell->type)]; + if (mapping < 0) { + report_invalid_bel(bel, cell); + } NPNR_ASSERT(mapping >= 0); if (cell->cell_mapping != mapping) { - map_cell_pins(cell, mapping); + map_cell_pins(cell, mapping, /*bind_constants=*/false); } constraints.bindBel(tile_status.tags.data(), get_cell_constraints(bel, cell->type)); } else { @@ -1078,10 +1064,7 @@ struct Arch : ArchAPI return str_range; } - const std::vector &getBelPinsForCellPin(const CellInfo *cell_info, IdString pin) const override - { - return cell_info->cell_bel_pins.at(pin); - } + const std::vector &getBelPinsForCellPin(const CellInfo *cell_info, IdString pin) const override; // ------------------------------------------------- @@ -1509,7 +1492,7 @@ struct Arch : ArchAPI if (cell == nullptr) { return true; } else { - if(!dedicated_interconnect.isBelLocationValid(bel, cell)) { + if (!dedicated_interconnect.isBelLocationValid(bel, cell)) { return false; } @@ -1718,6 +1701,11 @@ struct Arch : ArchAPI } void merge_constant_nets(); + void report_invalid_bel(BelId bel, CellInfo *cell) const; + + std::vector no_pins; + IdString gnd_cell_pin; + IdString vcc_cell_pin; }; NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/arch_pack_io.cc b/fpga_interchange/arch_pack_io.cc index 6a0ffe0b..06cfa002 100644 --- a/fpga_interchange/arch_pack_io.cc +++ b/fpga_interchange/arch_pack_io.cc @@ -243,7 +243,9 @@ void Arch::pack_ports() for (CellInfo *cell : placed_cells) { NPNR_ASSERT(cell->bel != BelId()); - NPNR_ASSERT(isBelLocationValid(cell->bel)); + if (!isBelLocationValid(cell->bel)) { + log_error("Tightly bound BEL %s was not valid!\n", nameOfBel(cell->bel)); + } } } } diff --git a/fpga_interchange/dedicated_interconnect.cc b/fpga_interchange/dedicated_interconnect.cc index b9ef93b5..820896a3 100644 --- a/fpga_interchange/dedicated_interconnect.cc +++ b/fpga_interchange/dedicated_interconnect.cc @@ -18,8 +18,8 @@ * */ -#include "nextpnr.h" #include "log.h" +#include "nextpnr.h" #include "util.h" NEXTPNR_NAMESPACE_BEGIN @@ -32,13 +32,15 @@ NEXTPNR_NAMESPACE_BEGIN // terminate at another site. Routing that "flys" over a site is expressed as // a psuedo-pip connected the relevant site pin wires, rather than traversing // the site. -enum WireNodeState { +enum WireNodeState +{ IN_SINK_SITE = 0, IN_ROUTING = 1, IN_SOURCE_SITE = 2 }; -struct WireNode { +struct WireNode +{ WireId wire; WireNodeState state; int depth; @@ -50,32 +52,33 @@ struct WireNode { // interconnect. constexpr int kMaxDepth = 20; -void DedicatedInterconnect::init(const Context *ctx) { +void DedicatedInterconnect::init(const Context *ctx) +{ this->ctx = ctx; - if(ctx->debug) { + if (ctx->debug) { log_info("Finding dedicated interconnect!\n"); } find_dedicated_interconnect(); - if(ctx->debug) { + if (ctx->debug) { print_dedicated_interconnect(); } } -bool DedicatedInterconnect::check_routing( - BelId src_bel, IdString src_bel_pin, - BelId dst_bel, IdString dst_bel_pin) const { +bool DedicatedInterconnect::check_routing(BelId src_bel, IdString src_bel_pin, BelId dst_bel, + IdString dst_bel_pin) const +{ std::vector nodes_to_expand; WireId src_wire = ctx->getBelPinWire(src_bel, src_bel_pin); - const auto & src_wire_data = ctx->wire_info(src_wire); + const auto &src_wire_data = ctx->wire_info(src_wire); NPNR_ASSERT(src_wire_data.site != -1); WireId dst_wire = ctx->getBelPinWire(dst_bel, dst_bel_pin); - const auto & dst_wire_data = ctx->wire_info(dst_wire); + const auto &dst_wire_data = ctx->wire_info(dst_wire); NPNR_ASSERT(dst_wire_data.site != -1); WireNode wire_node; @@ -85,30 +88,29 @@ bool DedicatedInterconnect::check_routing( nodes_to_expand.push_back(wire_node); - while(!nodes_to_expand.empty()) { + while (!nodes_to_expand.empty()) { WireNode node_to_expand = nodes_to_expand.back(); nodes_to_expand.pop_back(); - for(PipId pip : ctx->getPipsDownhill(node_to_expand.wire)) { - if(ctx->is_pip_synthetic(pip)) { + for (PipId pip : ctx->getPipsDownhill(node_to_expand.wire)) { + if (ctx->is_pip_synthetic(pip)) { continue; } WireId wire = ctx->getPipDstWire(pip); - if(wire == WireId()) { + if (wire == WireId()) { continue; } #ifdef DEBUG_EXPANSION - log_info(" - At wire %s via %s\n", - ctx->nameOfWire(wire), ctx->nameOfPip(pip)); + log_info(" - At wire %s via %s\n", ctx->nameOfWire(wire), ctx->nameOfPip(pip)); #endif WireNode next_node; next_node.wire = wire; next_node.depth = node_to_expand.depth += 1; - if(next_node.depth > kMaxDepth) { + if (next_node.depth > kMaxDepth) { // Dedicated routing should reach sources by kMaxDepth (with // tuning). // @@ -116,55 +118,52 @@ bool DedicatedInterconnect::check_routing( return false; } - auto const & wire_data = ctx->wire_info(wire); + auto const &wire_data = ctx->wire_info(wire); bool expand_node = true; - if(ctx->is_site_port(pip)) { - switch(node_to_expand.state) { - case IN_SOURCE_SITE: - NPNR_ASSERT(wire_data.site == -1); - next_node.state = IN_ROUTING; - break; - case IN_ROUTING: - NPNR_ASSERT(wire_data.site != -1); - if(wire.tile == src_wire.tile && wire_data.site == src_wire_data.site) { - // Dedicated routing won't have straight loops, - // general routing looks like that. + if (ctx->is_site_port(pip)) { + switch (node_to_expand.state) { + case IN_SOURCE_SITE: + NPNR_ASSERT(wire_data.site == -1); + next_node.state = IN_ROUTING; + break; + case IN_ROUTING: + NPNR_ASSERT(wire_data.site != -1); + if (wire.tile == src_wire.tile && wire_data.site == src_wire_data.site) { + // Dedicated routing won't have straight loops, + // general routing looks like that. #ifdef DEBUG_EXPANSION - log_info(" - Not dedicated site routing because loop!"); + log_info(" - Not dedicated site routing because loop!"); #endif - return false; - } - next_node.state = IN_SINK_SITE; - break; - case IN_SINK_SITE: - // Once entering a site, do not leave it again. - // This path is not a legal route! - expand_node = false; - break; - default: - // Unreachable!!! - NPNR_ASSERT(false); + return false; + } + next_node.state = IN_SINK_SITE; + break; + case IN_SINK_SITE: + // Once entering a site, do not leave it again. + // This path is not a legal route! + expand_node = false; + break; + default: + // Unreachable!!! + NPNR_ASSERT(false); } } else { next_node.state = node_to_expand.state; } - if(expand_node) { + if (expand_node) { nodes_to_expand.push_back(next_node); } else { continue; } - if(next_node.state == IN_SINK_SITE) { - for(BelPin bel_pin : ctx->getWireBelPins(wire)) { - if(bel_pin.bel == dst_bel && bel_pin.pin == dst_bel_pin) { - if(ctx->verbose) { - log_info("Valid dedicated interconnect from %s/%s to %s/%s\n", - ctx->nameOfBel(src_bel), - src_bel_pin.c_str(ctx), - ctx->nameOfBel(dst_bel), - dst_bel_pin.c_str(ctx)); + if (next_node.state == IN_SINK_SITE) { + for (BelPin bel_pin : ctx->getWireBelPins(wire)) { + if (bel_pin.bel == dst_bel && bel_pin.pin == dst_bel_pin) { + if (ctx->debug) { + log_info("Valid dedicated interconnect from %s/%s to %s/%s\n", ctx->nameOfBel(src_bel), + src_bel_pin.c_str(ctx), ctx->nameOfBel(dst_bel), dst_bel_pin.c_str(ctx)); } return true; } @@ -176,8 +175,9 @@ bool DedicatedInterconnect::check_routing( return false; } -bool DedicatedInterconnect::is_driver_on_net_valid(BelId driver_bel, - const CellInfo* cell, IdString driver_port, NetInfo *net) const { +bool DedicatedInterconnect::is_driver_on_net_valid(BelId driver_bel, const CellInfo *cell, IdString driver_port, + NetInfo *net) const +{ const auto &driver_bel_data = bel_info(ctx->chip_info, driver_bel); TileTypeBelPin type_bel_pin; @@ -186,27 +186,34 @@ bool DedicatedInterconnect::is_driver_on_net_valid(BelId driver_bel, Loc driver_loc = ctx->getBelLocation(driver_bel); - for(IdString driver_bel_pin : ctx->getBelPinsForCellPin(cell, driver_port)) { + for (IdString driver_bel_pin : ctx->getBelPinsForCellPin(cell, driver_port)) { type_bel_pin.bel_pin = driver_bel_pin; auto iter = sources.find(type_bel_pin); - if(iter == sources.end()) { + if (iter == sources.end()) { // This BEL pin doesn't have a dedicate interconnect. continue; } - for(const PortRef & port_ref : net->users) { + for (const PortRef &port_ref : net->users) { NPNR_ASSERT(port_ref.cell != nullptr); - if(port_ref.cell->bel == BelId()) { - return true; + if (port_ref.cell->bel == BelId()) { + // FIXME: This should actually return "unknown!" because the + // sink is unplaced. Once the sink is placed, this constraint + // can be evaluated. + if (ctx->debug) { + log_info("BEL %s is not valid because sink cell %s/%s is not placed\n", ctx->nameOfBel(driver_bel), + port_ref.cell->name.c_str(ctx), port_ref.port.c_str(ctx)); + } + return false; } BelId sink_bel = port_ref.cell->bel; const auto &sink_bel_data = bel_info(ctx->chip_info, sink_bel); Loc sink_loc = ctx->getBelLocation(port_ref.cell->bel); - if(sink_bel.tile == driver_bel.tile && sink_bel_data.site == driver_bel_data.site) { + if (sink_bel.tile == driver_bel.tile && sink_bel_data.site == driver_bel_data.site) { // This is a site local routing, even though this is a sink // with a dedicated interconnect. continue; @@ -218,18 +225,15 @@ bool DedicatedInterconnect::is_driver_on_net_valid(BelId driver_bel, sink_type_bel_pin.type_bel_pin.tile_type = ctx->chip_info->tiles[sink_bel.tile].type; sink_type_bel_pin.type_bel_pin.bel_index = sink_bel.index; - for(IdString sink_bel_pin : ctx->getBelPinsForCellPin(port_ref.cell, port_ref.port)) { + for (IdString sink_bel_pin : ctx->getBelPinsForCellPin(port_ref.cell, port_ref.port)) { sink_type_bel_pin.type_bel_pin.bel_pin = sink_bel_pin; // Do fast routing check to see if the pair of driver and sink // every are valid. - if(iter->second.count(sink_type_bel_pin) == 0) { - if(ctx->verbose) { - log_info("BEL %s is not valid because pin %s cannot reach %s/%s\n", - ctx->nameOfBel(driver_bel), - driver_bel_pin.c_str(ctx), - ctx->nameOfBel(sink_bel), - sink_bel_pin.c_str(ctx)); + if (iter->second.count(sink_type_bel_pin) == 0) { + if (ctx->debug) { + log_info("BEL %s is not valid because pin %s cannot reach %s/%s\n", ctx->nameOfBel(driver_bel), + driver_bel_pin.c_str(ctx), ctx->nameOfBel(sink_bel), sink_bel_pin.c_str(ctx)); } return false; } @@ -239,15 +243,11 @@ bool DedicatedInterconnect::is_driver_on_net_valid(BelId driver_bel, // FIXME: This might be too slow, but it handles a case on // SLICEL.COUT -> SLICEL.CIN has delta_y = {1, 2}, but the // delta_y=2 case is rare. - if(!check_routing( - driver_bel, driver_bel_pin, - sink_bel, sink_bel_pin)) { - if(ctx->verbose) { + if (!check_routing(driver_bel, driver_bel_pin, sink_bel, sink_bel_pin)) { + if (ctx->debug) { log_info("BEL %s is not valid because pin %s cannot be reach %s/%s (via detailed check)\n", - ctx->nameOfBel(driver_bel), - driver_bel_pin.c_str(ctx), - ctx->nameOfBel(sink_bel), - sink_bel_pin.c_str(ctx)); + ctx->nameOfBel(driver_bel), driver_bel_pin.c_str(ctx), ctx->nameOfBel(sink_bel), + sink_bel_pin.c_str(ctx)); } return false; } @@ -258,52 +258,62 @@ bool DedicatedInterconnect::is_driver_on_net_valid(BelId driver_bel, return true; } -bool DedicatedInterconnect::is_sink_on_net_valid(BelId bel, const CellInfo* cell, IdString port_name, NetInfo *net) const { - BelId driver_bel = net->driver.cell->bel; - if(driver_bel == BelId()) { - return true; - } - +bool DedicatedInterconnect::is_sink_on_net_valid(BelId bel, const CellInfo *cell, IdString port_name, + NetInfo *net) const +{ const auto &bel_data = bel_info(ctx->chip_info, bel); - const auto &driver_bel_data = bel_info(ctx->chip_info, driver_bel); - Loc bel_loc = ctx->getBelLocation(bel); - Loc driver_loc = ctx->getBelLocation(driver_bel); - DeltaTileTypeBelPin driver_type_bel_pin; - driver_type_bel_pin.delta_x = driver_loc.x - bel_loc.x; - driver_type_bel_pin.delta_y = driver_loc.y - bel_loc.y; - driver_type_bel_pin.type_bel_pin.tile_type = ctx->chip_info->tiles[driver_bel.tile].type; - driver_type_bel_pin.type_bel_pin.bel_index = driver_bel.index; - driver_type_bel_pin.type_bel_pin.bel_pin = get_only_value(ctx->getBelPinsForCellPin(net->driver.cell, net->driver.port)); + BelId driver_bel = net->driver.cell->bel; - for(IdString bel_pin : ctx->getBelPinsForCellPin(cell, port_name)) { + for (IdString bel_pin : ctx->getBelPinsForCellPin(cell, port_name)) { TileTypeBelPin type_bel_pin; type_bel_pin.tile_type = ctx->chip_info->tiles[bel.tile].type; type_bel_pin.bel_index = bel.index; type_bel_pin.bel_pin = bel_pin; auto iter = sinks.find(type_bel_pin); - if(iter == sinks.end()) { + if (iter == sinks.end()) { // This BEL pin doesn't have a dedicate interconnect. continue; } - if(bel.tile == driver_bel.tile && bel_data.site == driver_bel_data.site) { + if (driver_bel == BelId()) { + // FIXME: This should actually return "unknown!" because the + // driver is unplaced. Once the driver is placed, this constraint + // can be evaluated. + if (ctx->debug) { + log_info("BEL %s is not valid because driver cell %s/%s is not placed\n", ctx->nameOfBel(bel), + net->driver.cell->name.c_str(ctx), net->driver.port.c_str(ctx)); + } + return false; + } + + const auto &driver_bel_data = bel_info(ctx->chip_info, driver_bel); + + if (bel.tile == driver_bel.tile && bel_data.site == driver_bel_data.site) { // This is a site local routing, even though this is a sink // with a dedicated interconnect. continue; } + Loc driver_loc = ctx->getBelLocation(driver_bel); + + DeltaTileTypeBelPin driver_type_bel_pin; + driver_type_bel_pin.delta_x = driver_loc.x - bel_loc.x; + driver_type_bel_pin.delta_y = driver_loc.y - bel_loc.y; + driver_type_bel_pin.type_bel_pin.tile_type = ctx->chip_info->tiles[driver_bel.tile].type; + driver_type_bel_pin.type_bel_pin.bel_index = driver_bel.index; + driver_type_bel_pin.type_bel_pin.bel_pin = + get_only_value(ctx->getBelPinsForCellPin(net->driver.cell, net->driver.port)); + // Do fast routing check to see if the pair of driver and sink // every are valid. - if(iter->second.count(driver_type_bel_pin) == 0) { - if(ctx->verbose) { - log_info("BEL %s is not valid because pin %s cannot be driven by %s/%s\n", - ctx->nameOfBel(bel), - bel_pin.c_str(ctx), - ctx->nameOfBel(driver_bel), - driver_type_bel_pin.type_bel_pin.bel_pin.c_str(ctx)); + if (iter->second.count(driver_type_bel_pin) == 0) { + if (ctx->debug) { + log_info("BEL %s is not valid because pin %s cannot be driven by %s/%s\n", ctx->nameOfBel(bel), + bel_pin.c_str(ctx), ctx->nameOfBel(driver_bel), + driver_type_bel_pin.type_bel_pin.bel_pin.c_str(ctx)); } return false; } @@ -313,15 +323,11 @@ bool DedicatedInterconnect::is_sink_on_net_valid(BelId bel, const CellInfo* cell // FIXME: This might be too slow, but it handles a case on // SLICEL.COUT -> SLICEL.CIN has delta_y = {1, 2}, but the // delta_y=2 case is rare. - if(!check_routing( - driver_bel, driver_type_bel_pin.type_bel_pin.bel_pin, - bel, bel_pin)) { - if(ctx->verbose) { + if (!check_routing(driver_bel, driver_type_bel_pin.type_bel_pin.bel_pin, bel, bel_pin)) { + if (ctx->debug) { log_info("BEL %s is not valid because pin %s cannot be driven by %s/%s (via detailed check)\n", - ctx->nameOfBel(bel), - bel_pin.c_str(ctx), - ctx->nameOfBel(driver_bel), - driver_type_bel_pin.type_bel_pin.bel_pin.c_str(ctx)); + ctx->nameOfBel(bel), bel_pin.c_str(ctx), ctx->nameOfBel(driver_bel), + driver_type_bel_pin.type_bel_pin.bel_pin.c_str(ctx)); } return false; } @@ -330,13 +336,14 @@ bool DedicatedInterconnect::is_sink_on_net_valid(BelId bel, const CellInfo* cell return true; } -bool DedicatedInterconnect::isBelLocationValid(BelId bel, const CellInfo* cell) const { +bool DedicatedInterconnect::isBelLocationValid(BelId bel, const CellInfo *cell) const +{ NPNR_ASSERT(bel != BelId()); - for(const auto &port_pair : cell->ports) { + for (const auto &port_pair : cell->ports) { IdString port_name = port_pair.first; NetInfo *net = port_pair.second.net; - if(net == nullptr) { + if (net == nullptr) { continue; } @@ -344,12 +351,12 @@ bool DedicatedInterconnect::isBelLocationValid(BelId bel, const CellInfo* cell) NPNR_ASSERT(net->driver.cell != nullptr); // Only check sink BELs. - if(net->driver.cell == cell && net->driver.port == port_name) { - if(!is_driver_on_net_valid(bel, cell, port_name, net)) { + if (net->driver.cell == cell && net->driver.port == port_name) { + if (!is_driver_on_net_valid(bel, cell, port_name, net)) { return false; } } else { - if(!is_sink_on_net_valid(bel, cell, port_name, net)) { + if (!is_sink_on_net_valid(bel, cell, port_name, net)) { return false; } } @@ -358,100 +365,84 @@ bool DedicatedInterconnect::isBelLocationValid(BelId bel, const CellInfo* cell) return true; } -void DedicatedInterconnect::print_dedicated_interconnect() const { +void DedicatedInterconnect::print_dedicated_interconnect() const +{ log_info("Found %zu sinks with dedicated interconnect\n", sinks.size()); log_info("Found %zu sources with dedicated interconnect\n", sources.size()); std::vector sorted_keys; - for(const auto & sink_to_srcs : sinks) { + for (const auto &sink_to_srcs : sinks) { sorted_keys.push_back(sink_to_srcs.first); } - for(const auto & src_to_sinks : sources) { + for (const auto &src_to_sinks : sources) { sorted_keys.push_back(src_to_sinks.first); } std::sort(sorted_keys.begin(), sorted_keys.end()); - for(const auto & key : sorted_keys) { + for (const auto &key : sorted_keys) { auto iter = sinks.find(key); - if(iter != sinks.end()) { + if (iter != sinks.end()) { auto dst = key; - for(const auto & src_delta : iter->second) { + for (const auto &src_delta : iter->second) { auto src = src_delta.type_bel_pin; auto delta_x = src_delta.delta_x; auto delta_y = src_delta.delta_y; - const TileTypeInfoPOD & src_tile_type = ctx->chip_info->tile_types[src.tile_type]; - const BelInfoPOD & src_bel_info = src_tile_type.bel_data[src.bel_index]; + const TileTypeInfoPOD &src_tile_type = ctx->chip_info->tile_types[src.tile_type]; + const BelInfoPOD &src_bel_info = src_tile_type.bel_data[src.bel_index]; IdString src_site_type = IdString(src_tile_type.site_types[src_bel_info.site]); IdString src_bel_pin = src.bel_pin; - const TileTypeInfoPOD & dst_tile_type = ctx->chip_info->tile_types[dst.tile_type]; - const BelInfoPOD & dst_bel_info = dst_tile_type.bel_data[dst.bel_index]; + const TileTypeInfoPOD &dst_tile_type = ctx->chip_info->tile_types[dst.tile_type]; + const BelInfoPOD &dst_bel_info = dst_tile_type.bel_data[dst.bel_index]; IdString dst_site_type = IdString(dst_tile_type.site_types[dst_bel_info.site]); IdString dst_bel_pin = dst.bel_pin; - log_info("%s.%s[%d]/%s/%s (%d, %d) -> %s.%s[%d]/%s/%s\n", - IdString(src_tile_type.name).c_str(ctx), - src_site_type.c_str(ctx), - src_bel_info.site, - IdString(src_bel_info.name).c_str(ctx), - src_bel_pin.c_str(ctx), - delta_x, - delta_y, - IdString(dst_tile_type.name).c_str(ctx), - dst_site_type.c_str(ctx), - dst_bel_info.site, - IdString(dst_bel_info.name).c_str(ctx), - dst_bel_pin.c_str(ctx)); - + log_info("%s.%s[%d]/%s/%s (%d, %d) -> %s.%s[%d]/%s/%s\n", IdString(src_tile_type.name).c_str(ctx), + src_site_type.c_str(ctx), src_bel_info.site, IdString(src_bel_info.name).c_str(ctx), + src_bel_pin.c_str(ctx), delta_x, delta_y, IdString(dst_tile_type.name).c_str(ctx), + dst_site_type.c_str(ctx), dst_bel_info.site, IdString(dst_bel_info.name).c_str(ctx), + dst_bel_pin.c_str(ctx)); } } else { auto src = key; - for(const auto & dst_delta : sources.at(key)) { + for (const auto &dst_delta : sources.at(key)) { auto dst = dst_delta.type_bel_pin; auto delta_x = dst_delta.delta_x; auto delta_y = dst_delta.delta_y; - const TileTypeInfoPOD & src_tile_type = ctx->chip_info->tile_types[src.tile_type]; - const BelInfoPOD & src_bel_info = src_tile_type.bel_data[src.bel_index]; + const TileTypeInfoPOD &src_tile_type = ctx->chip_info->tile_types[src.tile_type]; + const BelInfoPOD &src_bel_info = src_tile_type.bel_data[src.bel_index]; IdString src_site_type = IdString(src_tile_type.site_types[src_bel_info.site]); IdString src_bel_pin = src.bel_pin; - const TileTypeInfoPOD & dst_tile_type = ctx->chip_info->tile_types[dst.tile_type]; - const BelInfoPOD & dst_bel_info = dst_tile_type.bel_data[dst.bel_index]; + const TileTypeInfoPOD &dst_tile_type = ctx->chip_info->tile_types[dst.tile_type]; + const BelInfoPOD &dst_bel_info = dst_tile_type.bel_data[dst.bel_index]; IdString dst_site_type = IdString(dst_tile_type.site_types[dst_bel_info.site]); IdString dst_bel_pin = dst.bel_pin; - log_info("%s.%s[%d]/%s/%s -> %s.%s[%d]/%s/%s (%d, %d)\n", - IdString(src_tile_type.name).c_str(ctx), - src_site_type.c_str(ctx), - src_bel_info.site, - IdString(src_bel_info.name).c_str(ctx), - src_bel_pin.c_str(ctx), - IdString(dst_tile_type.name).c_str(ctx), - dst_site_type.c_str(ctx), - dst_bel_info.site, - IdString(dst_bel_info.name).c_str(ctx), - dst_bel_pin.c_str(ctx), - delta_x, - delta_y); - + log_info("%s.%s[%d]/%s/%s -> %s.%s[%d]/%s/%s (%d, %d)\n", IdString(src_tile_type.name).c_str(ctx), + src_site_type.c_str(ctx), src_bel_info.site, IdString(src_bel_info.name).c_str(ctx), + src_bel_pin.c_str(ctx), IdString(dst_tile_type.name).c_str(ctx), dst_site_type.c_str(ctx), + dst_bel_info.site, IdString(dst_bel_info.name).c_str(ctx), dst_bel_pin.c_str(ctx), delta_x, + delta_y); } } } } -void DedicatedInterconnect::find_dedicated_interconnect() { - for(BelId bel : ctx->getBels()) { - const auto & bel_data = bel_info(ctx->chip_info, bel); - if(bel_data.category != BEL_CATEGORY_LOGIC) { +void DedicatedInterconnect::find_dedicated_interconnect() +{ + for (BelId bel : ctx->getBels()) { + const auto &bel_data = bel_info(ctx->chip_info, bel); + if (bel_data.category != BEL_CATEGORY_LOGIC) { continue; } - if(bel_data.synthetic) { + if (bel_data.synthetic) { continue; } - for(size_t i = 0; i < bel_data.num_bel_wires; ++i) { - if(bel_data.types[i] != PORT_IN) { + for (size_t i = 0; i < bel_data.num_bel_wires; ++i) { + if (bel_data.types[i] != PORT_IN) { continue; } @@ -464,27 +455,26 @@ void DedicatedInterconnect::find_dedicated_interconnect() { } std::unordered_set seen_pins; - for(auto sink_pair : sinks) { - for(auto src : sink_pair.second) { + for (auto sink_pair : sinks) { + for (auto src : sink_pair.second) { seen_pins.emplace(src.type_bel_pin); } } - for(BelId bel : ctx->getBels()) { - const auto & bel_data = bel_info(ctx->chip_info, bel); - if(bel_data.category != BEL_CATEGORY_LOGIC) { + for (BelId bel : ctx->getBels()) { + const auto &bel_data = bel_info(ctx->chip_info, bel); + if (bel_data.category != BEL_CATEGORY_LOGIC) { continue; } - if(bel_data.synthetic) { + if (bel_data.synthetic) { continue; } - for(size_t i = 0; i < bel_data.num_bel_wires; ++i) { - if(bel_data.types[i] != PORT_OUT) { + for (size_t i = 0; i < bel_data.num_bel_wires; ++i) { + if (bel_data.types[i] != PORT_OUT) { continue; } - IdString bel_pin(bel_data.ports[i]); TileTypeBelPin type_bel_pin; @@ -493,7 +483,7 @@ void DedicatedInterconnect::find_dedicated_interconnect() { type_bel_pin.bel_pin = bel_pin; // Don't visit src pins already handled in the sink expansion! - if(seen_pins.count(type_bel_pin)) { + if (seen_pins.count(type_bel_pin)) { continue; } @@ -506,7 +496,8 @@ void DedicatedInterconnect::find_dedicated_interconnect() { } } -void DedicatedInterconnect::expand_sink_bel(BelId sink_bel, IdString sink_pin, WireId sink_wire) { +void DedicatedInterconnect::expand_sink_bel(BelId sink_bel, IdString sink_pin, WireId sink_wire) +{ NPNR_ASSERT(sink_bel != BelId()); #ifdef DEBUG_EXPANSION log_info("Expanding from %s/%s\n", ctx->nameOfBel(sink_bel), pin.c_str(ctx)); @@ -514,7 +505,7 @@ void DedicatedInterconnect::expand_sink_bel(BelId sink_bel, IdString sink_pin, W std::vector nodes_to_expand; - const auto & sink_wire_data = ctx->wire_info(sink_wire); + const auto &sink_wire_data = ctx->wire_info(sink_wire); NPNR_ASSERT(sink_wire_data.site != -1); WireNode wire_node; @@ -527,89 +518,91 @@ void DedicatedInterconnect::expand_sink_bel(BelId sink_bel, IdString sink_pin, W Loc sink_loc = ctx->getBelLocation(sink_bel); std::unordered_set srcs; - while(!nodes_to_expand.empty()) { + while (!nodes_to_expand.empty()) { WireNode node_to_expand = nodes_to_expand.back(); nodes_to_expand.pop_back(); - for(PipId pip : ctx->getPipsUphill(node_to_expand.wire)) { - if(ctx->is_pip_synthetic(pip)) { + for (PipId pip : ctx->getPipsUphill(node_to_expand.wire)) { + if (ctx->is_pip_synthetic(pip)) { continue; } WireId wire = ctx->getPipSrcWire(pip); - if(wire == WireId()) { + if (wire == WireId()) { continue; } #ifdef DEBUG_EXPANSION - log_info(" - At wire %s via %s\n", - ctx->nameOfWire(wire), ctx->nameOfPip(pip)); + log_info(" - At wire %s via %s\n", ctx->nameOfWire(wire), ctx->nameOfPip(pip)); #endif WireNode next_node; next_node.wire = wire; next_node.depth = node_to_expand.depth += 1; - if(next_node.depth > kMaxDepth) { + if (next_node.depth > kMaxDepth) { // Dedicated routing should reach sources by kMaxDepth (with // tuning). // // FIXME: Consider removing kMaxDepth and use kMaxSources? +#ifdef DEBUG_EXPANSION + log_info(" - Exceeded max depth!\n"); +#endif return; } - auto const & wire_data = ctx->wire_info(wire); + auto const &wire_data = ctx->wire_info(wire); bool expand_node = true; - if(ctx->is_site_port(pip)) { - switch(node_to_expand.state) { - case IN_SINK_SITE: - NPNR_ASSERT(wire_data.site == -1); - next_node.state = IN_ROUTING; - break; - case IN_ROUTING: - NPNR_ASSERT(wire_data.site != -1); - if(wire.tile == sink_wire.tile && wire_data.site == sink_wire_data.site) { - // Dedicated routing won't have straight loops, - // general routing looks like that. + if (ctx->is_site_port(pip)) { + switch (node_to_expand.state) { + case IN_SINK_SITE: + NPNR_ASSERT(wire_data.site == -1); + next_node.state = IN_ROUTING; + break; + case IN_ROUTING: + NPNR_ASSERT(wire_data.site != -1); + if (wire.tile == sink_wire.tile && wire_data.site == sink_wire_data.site) { + // Dedicated routing won't have straight loops, + // general routing looks like that. #ifdef DEBUG_EXPANSION - log_info(" - Not dedicated site routing because loop!"); + log_info(" - Not dedicated site routing because loop!"); #endif - return; - } - next_node.state = IN_SOURCE_SITE; - break; - case IN_SOURCE_SITE: - // Once entering a site, do not leave it again. - // This path is not a legal route! - expand_node = false; - break; - default: - // Unreachable!!! - NPNR_ASSERT(false); + return; + } + next_node.state = IN_SOURCE_SITE; + break; + case IN_SOURCE_SITE: + // Once entering a site, do not leave it again. + // This path is not a legal route! + expand_node = false; + break; + default: + // Unreachable!!! + NPNR_ASSERT(false); } } else { next_node.state = node_to_expand.state; } - if(expand_node) { + if (expand_node) { nodes_to_expand.push_back(next_node); } else { continue; } - if(next_node.state == IN_SOURCE_SITE) { - for(BelPin bel_pin : ctx->getWireBelPins(wire)) { + if (next_node.state == IN_SOURCE_SITE) { + for (BelPin bel_pin : ctx->getWireBelPins(wire)) { BelId src_bel = bel_pin.bel; - auto const & bel_data = bel_info(ctx->chip_info, src_bel); + auto const &bel_data = bel_info(ctx->chip_info, src_bel); - if(bel_data.category != BEL_CATEGORY_LOGIC) { + if (bel_data.category != BEL_CATEGORY_LOGIC) { continue; } - if(bel_data.synthetic) { + if (bel_data.synthetic) { continue; } - if(ctx->getBelPinType(bel_pin.bel, bel_pin.pin) != PORT_OUT) { + if (ctx->getBelPinType(bel_pin.bel, bel_pin.pin) != PORT_OUT) { continue; } @@ -637,24 +630,25 @@ void DedicatedInterconnect::expand_sink_bel(BelId sink_bel, IdString sink_pin, W type_bel_pin.bel_pin = sink_pin; auto result = sinks.emplace(type_bel_pin, srcs); - if(!result.second) { + if (!result.second) { // type_bel_pin was already present! Add any new sources from this // sink type (if any); - for(auto src : srcs) { + for (auto src : srcs) { result.first->second.emplace(src); } } } -void DedicatedInterconnect::expand_source_bel(BelId src_bel, IdString src_pin, WireId src_wire) { +void DedicatedInterconnect::expand_source_bel(BelId src_bel, IdString src_pin, WireId src_wire) +{ NPNR_ASSERT(src_bel != BelId()); #ifdef DEBUG_EXPANSION - log_info("Expanding from %s/%s\n", ctx->nameOfBel(src_bel), pin.c_str(ctx)); + log_info("Expanding from %s/%s\n", ctx->nameOfBel(src_bel), src_pin.c_str(ctx)); #endif std::vector nodes_to_expand; - const auto & src_wire_data = ctx->wire_info(src_wire); + const auto &src_wire_data = ctx->wire_info(src_wire); NPNR_ASSERT(src_wire_data.site != -1); WireNode wire_node; @@ -667,89 +661,91 @@ void DedicatedInterconnect::expand_source_bel(BelId src_bel, IdString src_pin, W Loc src_loc = ctx->getBelLocation(src_bel); std::unordered_set dsts; - while(!nodes_to_expand.empty()) { + while (!nodes_to_expand.empty()) { WireNode node_to_expand = nodes_to_expand.back(); nodes_to_expand.pop_back(); - for(PipId pip : ctx->getPipsDownhill(node_to_expand.wire)) { - if(ctx->is_pip_synthetic(pip)) { + for (PipId pip : ctx->getPipsDownhill(node_to_expand.wire)) { + if (ctx->is_pip_synthetic(pip)) { continue; } WireId wire = ctx->getPipDstWire(pip); - if(wire == WireId()) { + if (wire == WireId()) { continue; } #ifdef DEBUG_EXPANSION - log_info(" - At wire %s via %s\n", - ctx->nameOfWire(wire), ctx->nameOfPip(pip)); + log_info(" - At wire %s via %s\n", ctx->nameOfWire(wire), ctx->nameOfPip(pip)); #endif WireNode next_node; next_node.wire = wire; next_node.depth = node_to_expand.depth += 1; - if(next_node.depth > kMaxDepth) { + if (next_node.depth > kMaxDepth) { // Dedicated routing should reach sources by kMaxDepth (with // tuning). // // FIXME: Consider removing kMaxDepth and use kMaxSources? +#ifdef DEBUG_EXPANSION + log_info(" - Exceeded max depth!\n"); +#endif return; } - auto const & wire_data = ctx->wire_info(wire); + auto const &wire_data = ctx->wire_info(wire); bool expand_node = true; - if(ctx->is_site_port(pip)) { - switch(node_to_expand.state) { - case IN_SOURCE_SITE: - NPNR_ASSERT(wire_data.site == -1); - next_node.state = IN_ROUTING; - break; - case IN_ROUTING: - NPNR_ASSERT(wire_data.site != -1); - if(wire.tile == src_wire.tile && wire_data.site == src_wire_data.site) { - // Dedicated routing won't have straight loops, - // general routing looks like that. + if (ctx->is_site_port(pip)) { + switch (node_to_expand.state) { + case IN_SOURCE_SITE: + NPNR_ASSERT(wire_data.site == -1); + next_node.state = IN_ROUTING; + break; + case IN_ROUTING: + NPNR_ASSERT(wire_data.site != -1); + if (wire.tile == src_wire.tile && wire_data.site == src_wire_data.site) { + // Dedicated routing won't have straight loops, + // general routing looks like that. #ifdef DEBUG_EXPANSION - log_info(" - Not dedicated site routing because loop!"); + log_info(" - Not dedicated site routing because loop!"); #endif - return; - } - next_node.state = IN_SINK_SITE; - break; - case IN_SINK_SITE: - // Once entering a site, do not leave it again. - // This path is not a legal route! - expand_node = false; - break; - default: - // Unreachable!!! - NPNR_ASSERT(false); + return; + } + next_node.state = IN_SINK_SITE; + break; + case IN_SINK_SITE: + // Once entering a site, do not leave it again. + // This path is not a legal route! + expand_node = false; + break; + default: + // Unreachable!!! + NPNR_ASSERT(false); } } else { next_node.state = node_to_expand.state; } - if(expand_node) { + if (expand_node) { nodes_to_expand.push_back(next_node); } else { continue; } - if(next_node.state == IN_SINK_SITE) { - for(BelPin bel_pin : ctx->getWireBelPins(wire)) { + if (next_node.state == IN_SINK_SITE) { + for (BelPin bel_pin : ctx->getWireBelPins(wire)) { BelId sink_bel = bel_pin.bel; - auto const & bel_data = bel_info(ctx->chip_info, sink_bel); + auto const &bel_data = bel_info(ctx->chip_info, sink_bel); - if(bel_data.category != BEL_CATEGORY_LOGIC) { + if (bel_data.category != BEL_CATEGORY_LOGIC) { continue; } - if(bel_data.synthetic) { + if (bel_data.synthetic) { continue; } - if(ctx->getBelPinType(bel_pin.bel, bel_pin.pin) != PORT_IN) { + if (ctx->getBelPinType(bel_pin.bel, bel_pin.pin) != PORT_IN) { continue; } @@ -776,11 +772,11 @@ void DedicatedInterconnect::expand_source_bel(BelId src_bel, IdString src_pin, W type_bel_pin.bel_index = src_bel.index; type_bel_pin.bel_pin = src_pin; - auto result = sinks.emplace(type_bel_pin, dsts); - if(!result.second) { + auto result = sources.emplace(type_bel_pin, dsts); + if (!result.second) { // type_bel_pin was already present! Add any new sources from this // sink type (if any); - for(auto dst : dsts) { + for (auto dst : dsts) { result.first->second.emplace(dst); } } diff --git a/fpga_interchange/dedicated_interconnect.h b/fpga_interchange/dedicated_interconnect.h index d603039e..66e1d41b 100644 --- a/fpga_interchange/dedicated_interconnect.h +++ b/fpga_interchange/dedicated_interconnect.h @@ -24,40 +24,47 @@ NEXTPNR_NAMESPACE_BEGIN -struct TileTypeBelPin { +struct TileTypeBelPin +{ int32_t tile_type; int32_t bel_index; IdString bel_pin; - bool operator < (const TileTypeBelPin &other) const { - if(tile_type >= other.tile_type) { + bool operator<(const TileTypeBelPin &other) const + { + if (tile_type >= other.tile_type) { return false; } - if(bel_index >= other.bel_index) { + if (bel_index >= other.bel_index) { return false; } return bel_pin < other.bel_pin; } - bool operator ==(const TileTypeBelPin &other) const { + bool operator==(const TileTypeBelPin &other) const + { return tile_type == other.tile_type && bel_index == other.bel_index && bel_pin == other.bel_pin; } - bool operator !=(const TileTypeBelPin &other) const { + bool operator!=(const TileTypeBelPin &other) const + { return tile_type != other.tile_type || bel_index != other.bel_index || bel_pin != other.bel_pin; } }; -struct DeltaTileTypeBelPin { +struct DeltaTileTypeBelPin +{ int32_t delta_x; int32_t delta_y; TileTypeBelPin type_bel_pin; - bool operator ==(const DeltaTileTypeBelPin &other) const { + bool operator==(const DeltaTileTypeBelPin &other) const + { return delta_x == other.delta_x && delta_y == other.delta_y && type_bel_pin == other.type_bel_pin; } - bool operator !=(const DeltaTileTypeBelPin &other) const { + bool operator!=(const DeltaTileTypeBelPin &other) const + { return delta_x != other.delta_x || delta_y != other.delta_y || type_bel_pin != other.type_bel_pin; } }; @@ -105,7 +112,8 @@ struct Context; // This class discovers dedicated interconnect by examing the routing graph. // This discovery make be expensive, and require caching to accelerate // startup. -struct DedicatedInterconnect { +struct DedicatedInterconnect +{ const Context *ctx; std::unordered_map> sinks; @@ -117,20 +125,16 @@ struct DedicatedInterconnect { // interconnect? // // Note: Only BEL pin sinks are checked. - bool isBelLocationValid(BelId bel, const CellInfo* cell) const; + bool isBelLocationValid(BelId bel, const CellInfo *cell) const; void find_dedicated_interconnect(); void print_dedicated_interconnect() const; - bool check_routing( - BelId src_bel, IdString src_bel_pin, - BelId dst_bel, IdString dst_bel_pin) const; + bool check_routing(BelId src_bel, IdString src_bel_pin, BelId dst_bel, IdString dst_bel_pin) const; void expand_sink_bel(BelId bel, IdString pin, WireId wire); void expand_source_bel(BelId bel, IdString pin, WireId wire); - bool is_driver_on_net_valid(BelId driver_bel, - const CellInfo* cell, IdString driver_port, NetInfo *net) const; - bool is_sink_on_net_valid(BelId bel, const CellInfo* cell, - IdString port_name, NetInfo *net) const; + bool is_driver_on_net_valid(BelId driver_bel, const CellInfo *cell, IdString driver_port, NetInfo *net) const; + bool is_sink_on_net_valid(BelId bel, const CellInfo *cell, IdString port_name, NetInfo *net) const; }; NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/fpga_interchange.cpp b/fpga_interchange/fpga_interchange.cpp index 027513c8..a1642789 100644 --- a/fpga_interchange/fpga_interchange.cpp +++ b/fpga_interchange/fpga_interchange.cpp @@ -111,20 +111,37 @@ static PhysicalNetlist::PhysNetlist::RouteBranch::Builder emit_branch( if(bel_data.category == BEL_CATEGORY_LOGIC) { // This is a psuedo site-pip. auto in_bel_pin = branch.getRouteSegment().initBelPin(); - IdString src_wire_name = IdString(tile_type.wire_data[pip_data.src_index].name); - IdString dst_wire_name = IdString(tile_type.wire_data[pip_data.dst_index].name); + WireId src_wire = ctx->getPipSrcWire(pip); + WireId dst_wire = ctx->getPipDstWire(pip); + + IdString src_pin; + IdString dst_pin; + for(IdString pin : ctx->getBelPins(bel)) { + if(ctx->getBelPinWire(bel, pin) == src_wire) { + NPNR_ASSERT(src_pin == IdString()); + src_pin = pin; + } + + if(ctx->getBelPinWire(bel, pin) == dst_wire) { + NPNR_ASSERT(dst_pin == IdString()); + dst_pin = pin; + } + } + + NPNR_ASSERT(src_pin != IdString()); + NPNR_ASSERT(dst_pin != IdString()); int bel_idx = strings->get_index(bel_name[1].str(ctx)); in_bel_pin.setSite(site_idx); in_bel_pin.setBel(bel_idx); - in_bel_pin.setPin(strings->get_index(src_wire_name.str(ctx))); + in_bel_pin.setPin(strings->get_index(src_pin.str(ctx))); auto subbranch = branch.initBranches(1); auto bel_pin_branch = subbranch[0]; auto out_bel_pin = bel_pin_branch.getRouteSegment().initBelPin(); out_bel_pin.setSite(site_idx); out_bel_pin.setBel(bel_idx); - out_bel_pin.setPin(strings->get_index(dst_wire_name.str(ctx))); + out_bel_pin.setPin(strings->get_index(dst_pin.str(ctx))); return bel_pin_branch; } else if(bel_data.category == BEL_CATEGORY_ROUTING) { @@ -614,6 +631,8 @@ struct ModuleReader { ModuleReader(const LogicalNetlistImpl *root, LogicalNetlist::Netlist::CellInstance::Reader cell_inst, bool is_top); + + size_t translate_port_index(LogicalNetlist::Netlist::PortInstance::Reader port_inst) const; }; struct PortReader { @@ -850,8 +869,8 @@ struct LogicalNetlistImpl bool is_vector_bit_constant(const std::vector &bits, int i) const { - // FIXME: Check if this is right. Assumption is that cells have been - // emitted for GND and VCC, e.g. VCC vcc(.P(vcc_net)). + // Note: This appears weird, but is correct. This is because VCC/GND + // nets are not handled in frontend_base for FPGA interchange. return false; } @@ -929,11 +948,8 @@ ModuleReader::ModuleReader(const LogicalNetlistImpl *root, PortKey port_key(inst_idx, port_inst.getPort()); std::vector & port_connections = connections.at(port_key); - if(port_inst.getBusIdx().isSingleBit()) { - port_connections[0] = net_idx; - } else { - port_connections.at(port_inst.getBusIdx().getIdx()) = net_idx; - } + size_t port_idx = translate_port_index(port_inst); + port_connections.at(port_idx) = net_idx; } } @@ -993,5 +1009,19 @@ void FpgaInterchange::read_logical_netlist(Context * ctx, const std::string &fil GenericFrontend(ctx, netlist_reader, /*split_io=*/false)(); } +size_t ModuleReader::translate_port_index(LogicalNetlist::Netlist::PortInstance::Reader port_inst) const { + LogicalNetlist::Netlist::Port::Reader port = root->root.getPortList()[port_inst.getPort()]; + if(port_inst.getBusIdx().isSingleBit()) { + NPNR_ASSERT(port.isBit()); + return 0; + } else { + NPNR_ASSERT(port.isBus()); + uint32_t idx = port_inst.getBusIdx().getIdx(); + size_t width = get_port_width(port); + NPNR_ASSERT(idx >= 0 && idx < width); + return width - 1 - idx; + } +} + NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/site_router.cc b/fpga_interchange/site_router.cc index a22dfcd3..7232b635 100644 --- a/fpga_interchange/site_router.cc +++ b/fpga_interchange/site_router.cc @@ -22,9 +22,9 @@ NEXTPNR_NAMESPACE_BEGIN -bool verbose_site_router(const Context *ctx) { return ctx->verbose; } +bool verbose_site_router(const Context *ctx) { return ctx->debug; } -void Arch::SiteRouter::bindBel(CellInfo *cell) +void SiteRouter::bindBel(CellInfo *cell) { auto result = cells_in_site.emplace(cell); NPNR_ASSERT(result.second); @@ -32,7 +32,7 @@ void Arch::SiteRouter::bindBel(CellInfo *cell) dirty = true; } -void Arch::SiteRouter::unbindBel(CellInfo *cell) +void SiteRouter::unbindBel(CellInfo *cell) { NPNR_ASSERT(cells_in_site.erase(cell) == 1); @@ -56,6 +56,22 @@ struct RouteNode PipId pip; // What pip was taken to reach this node. WireId wire; // What wire is this routing node located at? + + void print_route(const Context *ctx) const + { + log_info(" %s (via %s)\n", ctx->nameOfWire(wire), ctx->nameOfPip(pip)); + + Node node = parent; + while (node != RouteNode::Node()) { + if (node->pip != PipId()) { + log_info(" %s (via %s)\n", ctx->nameOfWire(node->wire), ctx->nameOfPip(node->pip)); + } else { + log_info(" %s\n", ctx->nameOfWire(node->wire)); + } + + node = node->parent; + } + } }; struct RouteNodeStorage @@ -260,10 +276,9 @@ struct SiteInformation if (!result.second && result.first->second != net) { // Conflict, this wire is already in use and it's not // doesn't match! - if(verbose_site_router(ctx)) { - log_info("Cannot select route because net %s != net %s\n", - result.first->second->name.c_str(ctx), - net->name.c_str(ctx)); + if (verbose_site_router(ctx)) { + log_info("Cannot select route because net %s != net %s\n", result.first->second->name.c_str(ctx), + net->name.c_str(ctx)); } return false; @@ -309,6 +324,8 @@ struct SiteInformation std::unordered_set nets_fully_within_site; bool is_net_within_site(const NetInfo *net) const { return nets_fully_within_site.count(net); } + + void print_current_state() const; }; struct SiteExpansionLoop @@ -605,6 +622,10 @@ bool route_site(const Context *ctx, SiteInformation *site_info) std::unordered_map> wire_congestion; + for (auto &consumed_wire : site_info->consumed_wires) { + wire_congestion[consumed_wire.first].emplace(consumed_wire.second); + } + for (auto &expansion_wire : wire_to_expansion) { auto &expansion = *expansion_wire.second; @@ -642,8 +663,15 @@ bool route_site(const Context *ctx, SiteInformation *site_info) if (uncongestion_route != RouteNode::Node()) { // Select a trivially uncongested route if possible. - NPNR_ASSERT(site_info->select_route(expansion.first_wire, uncongestion_route, expansion.net_for_wire, - &newly_consumed_wires)); + if (!site_info->select_route(expansion.first_wire, uncongestion_route, expansion.net_for_wire, + &newly_consumed_wires)) { + log_info("Failed to bind uncongested path with wire %s on net %s\n", + ctx->nameOfWire(expansion.first_wire), expansion.net_for_wire->name.c_str(ctx)); + uncongestion_route->print_route(ctx); + + site_info->print_current_state(); + NPNR_ASSERT(false); + } completed_wires.push_back(expansion.first_wire); } } @@ -676,7 +704,7 @@ bool route_site(const Context *ctx, SiteInformation *site_info) return true; } -bool Arch::SiteRouter::checkSiteRouting(const Context *ctx, const Arch::TileStatus &tile_status) const +bool SiteRouter::checkSiteRouting(const Context *ctx, const TileStatus &tile_status) const { if (!dirty) { return site_ok; @@ -753,4 +781,42 @@ bool Arch::SiteRouter::checkSiteRouting(const Context *ctx, const Arch::TileStat return site_ok; } +void SiteInformation::print_current_state() const +{ + const CellInfo *cell = *cells_in_site.begin(); + BelId bel = cell->bel; + const auto &bel_data = bel_info(ctx->chip_info, bel); + const auto &site_inst = site_inst_info(ctx->chip_info, bel.tile, bel_data.site); + + log_info("Site %s\n", site_inst.name.get()); + + log_info(" Cells in site:\n"); + for (CellInfo *cell : cells_in_site) { + log_info(" - %s (%s)\n", cell->name.c_str(ctx), cell->type.c_str(ctx)); + } + + log_info(" Nets in site:\n"); + for (auto *net : nets_in_site) { + log_info(" - %s, pins in site:\n", net->name.c_str(ctx)); + if (net->driver.cell && cells_in_site.count(net->driver.cell)) { + log_info(" - %s/%s (%s)\n", net->driver.cell->name.c_str(ctx), net->driver.port.c_str(ctx), + net->driver.cell->type.c_str(ctx)); + } + + for (const auto user : net->users) { + if (user.cell && cells_in_site.count(user.cell)) { + log_info(" - %s/%s (%s)\n", user.cell->name.c_str(ctx), user.port.c_str(ctx), + user.cell->type.c_str(ctx)); + } + } + } + + log_info(" Consumed wires:\n"); + for (auto consumed_wire : consumed_wires) { + WireId wire = consumed_wire.first; + const NetInfo *net = consumed_wire.second; + log_info(" - %s is bound to %s\n", ctx->nameOfWire(wire), net->name.c_str(ctx)); + } +} + NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/site_router.h b/fpga_interchange/site_router.h new file mode 100644 index 00000000..561dae9d --- /dev/null +++ b/fpga_interchange/site_router.h @@ -0,0 +1,45 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2021 Symbiflow Authors + * + * + * 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. + * + */ + +#ifndef NEXTPNR_H +#error Include "site_router.h" via "nextpnr.h" only. +#endif + +NEXTPNR_NAMESPACE_BEGIN + +struct Context; +struct TileStatus; + +struct SiteRouter +{ + SiteRouter(int16_t site) : site(site), dirty(false), site_ok(true) {} + + std::unordered_set cells_in_site; + const int16_t site; + + mutable bool dirty; + mutable bool site_ok; + + void bindBel(CellInfo *cell); + void unbindBel(CellInfo *cell); + bool checkSiteRouting(const Context *ctx, const TileStatus &tile_status) const; +}; + +NEXTPNR_NAMESPACE_END -- cgit v1.2.3