From c7f00b4760493c9ac6d57caaa20d077b0cd37cbc Mon Sep 17 00:00:00 2001 From: David Shah Date: Mon, 6 Jan 2020 19:04:43 +0000 Subject: nexus: Add iterator types based on nextpnr-xilinx Signed-off-by: David Shah --- nexus/arch.h | 371 ++++++++++++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 332 insertions(+), 39 deletions(-) (limited to 'nexus') diff --git a/nexus/arch.h b/nexus/arch.h index e4a7e8ee..5163d9c3 100644 --- a/nexus/arch.h +++ b/nexus/arch.h @@ -162,6 +162,7 @@ NPNR_PACKED_STRUCT(struct ChipInfoPOD { RelPtr device_name; uint16_t width; uint16_t height; + uint32_t num_tiles; RelPtr grid; }); @@ -174,6 +175,330 @@ NPNR_PACKED_STRUCT(struct DatabasePOD { RelPtr loctypes; }); +// ----------------------------------------------------------------------- + +// Helper functions for database access +namespace { +template const LocTypePOD &chip_loc_data(const DatabasePOD *db, const ChipInfoPOD *chip, Id &id) +{ + return db->loctypes[chip->grid[id.tile].loc_type]; +} + +template const LocNeighourhoodPOD &chip_nh_data(const DatabasePOD *db, const ChipInfoPOD *chip, Id &id) +{ + auto &t = chip->grid[id.tile]; + return db->loctypes[t.loc_type].neighbourhoods[t.neighbourhood_type]; +} + +inline const BelInfoPOD &chip_bel_data(const DatabasePOD *db, const ChipInfoPOD *chip, BelId id) +{ + return chip_loc_data(db, chip, id).bels[id.index]; +} +inline const LocWireInfoPOD &chip_wire_data(const DatabasePOD *db, const ChipInfoPOD *chip, WireId &id) +{ + return chip_loc_data(db, chip, id).wires[id.index]; +} +inline const PipInfoPOD &chip_pip_data(const DatabasePOD *db, const ChipInfoPOD *chip, PipId &id) +{ + return chip_loc_data(db, chip, id).pips[id.index]; +} +inline bool chip_rel_tile(const ChipInfoPOD *chip, int32_t base, int16_t rel_x, int16_t rel_y, int32_t &next) +{ + int32_t curr_x = base % chip->width; + int32_t curr_y = base / chip->width; + int32_t new_x = curr_x + rel_x; + int32_t new_y = curr_y + rel_y; + if (new_x < 0 || new_x >= chip->width) + return false; + if (new_y < 0 || new_y >= chip->height) + return false; + next = new_y * chip->width + new_x; + return true; +} +inline WireId chip_canonical_wire(const DatabasePOD *db, const ChipInfoPOD *chip, int32_t tile, uint16_t index) +{ + WireId wire{tile, index}; + // `tile` is the primary location for the wire, so ID is already canonical + if (chip_wire_data(db, chip, wire).flags & WIRE_PRIMARY) + return wire; + // Not primary; find the primary location which forms the canonical ID + auto &nd = chip_nh_data(db, chip, wire); + auto &wn = nd.wire_neighbours[index]; + for (size_t i = 0; i < wn.num_nwires; i++) { + auto &nw = wn.neigh_wires[i]; + if (nw.arc_flags & LOGICAL_TO_PRIMARY) { + if (chip_rel_tile(chip, tile, nw.rel_x, nw.rel_y, wire.tile)) { + wire.index = nw.wire_index; + break; + } + } + } + return wire; +} +inline bool chip_wire_is_primary(const DatabasePOD *db, const ChipInfoPOD *chip, int32_t tile, uint16_t index) +{ + WireId wire{tile, index}; + // `tile` is the primary location for the wire, so ID is already canonical + if (chip_wire_data(db, chip, wire).flags & WIRE_PRIMARY) + return true; + // Not primary; find the primary location which forms the canonical ID + auto &nd = chip_nh_data(db, chip, wire); + auto &wn = nd.wire_neighbours[index]; + for (size_t i = 0; i < wn.num_nwires; i++) { + auto &nw = wn.neigh_wires[i]; + if (nw.arc_flags & LOGICAL_TO_PRIMARY) { + if (chip_rel_tile(chip, tile, nw.rel_x, nw.rel_y, wire.tile)) { + return false; + } + } + } + return true; +} +} // namespace + +// ----------------------------------------------------------------------- + +struct BelIterator +{ + const DatabasePOD *db; + const ChipInfoPOD *chip; + int cursor_index; + int cursor_tile; + + BelIterator operator++() + { + cursor_index++; + while (cursor_tile < int(chip->num_tiles) && + cursor_index >= int(db->loctypes[chip->grid[cursor_tile].loc_type].num_bels)) { + cursor_index = 0; + cursor_tile++; + } + return *this; + } + BelIterator operator++(int) + { + BelIterator prior(*this); + ++(*this); + return prior; + } + + bool operator!=(const BelIterator &other) const + { + return cursor_index != other.cursor_index || cursor_tile != other.cursor_tile; + } + + bool operator==(const BelIterator &other) const + { + return cursor_index == other.cursor_index && cursor_tile == other.cursor_tile; + } + + BelId operator*() const + { + BelId ret; + ret.tile = cursor_tile; + ret.index = cursor_index; + return ret; + } +}; + +struct BelRange +{ + BelIterator b, e; + BelIterator begin() const { return b; } + BelIterator end() const { return e; } +}; + +// ----------------------------------------------------------------------- + +struct WireIterator +{ + const DatabasePOD *db; + const ChipInfoPOD *chip; + int cursor_index; + int cursor_tile = 0; + + WireIterator operator++() + { + // Iterate over nodes first, then tile wires that aren't nodes + do { + cursor_index++; + while (cursor_tile < int(chip->num_tiles) && + cursor_index >= int(db->loctypes[chip->grid[cursor_tile].loc_type].num_wires)) { + cursor_index = 0; + cursor_tile++; + } + } while (cursor_tile < int(chip->num_tiles) && !chip_wire_is_primary(db, chip, cursor_tile, cursor_index)); + + return *this; + } + WireIterator operator++(int) + { + WireIterator prior(*this); + ++(*this); + return prior; + } + + bool operator!=(const WireIterator &other) const + { + return cursor_index != other.cursor_index || cursor_tile != other.cursor_tile; + } + + bool operator==(const WireIterator &other) const + { + return cursor_index == other.cursor_index && cursor_tile == other.cursor_tile; + } + + WireId operator*() const + { + WireId ret; + ret.tile = cursor_tile; + ret.index = cursor_index; + return ret; + } +}; + +struct WireRange +{ + WireIterator b, e; + WireIterator begin() const { return b; } + WireIterator end() const { return e; } +}; + +// Iterate over all neighour wires for a wire +struct TileWireIterator +{ + const DatabasePOD *db; + const ChipInfoPOD *chip; + WireId baseWire; + int cursor = -1; + + void operator++() + { + auto &wn = chip_nh_data(db, chip, baseWire).wire_neighbours[baseWire.index]; + int32_t tile; + do + cursor++; + while (cursor < int(wn.num_nwires) && + ((wn.neigh_wires[cursor].arc_flags & LOGICAL_TO_PRIMARY) || + !chip_rel_tile(chip, baseWire.tile, wn.neigh_wires[cursor].rel_x, wn.neigh_wires[cursor].rel_y, tile))); + } + bool operator!=(const TileWireIterator &other) const { return cursor != other.cursor; } + + // Returns a *denormalised* identifier that may be a non-primary wire (and thus should _not_ be used + // as a WireId in general as it will break invariants) + WireId operator*() const + { + if (cursor == -1) { + return baseWire; + } else { + auto &nw = chip_nh_data(db, chip, baseWire).wire_neighbours[baseWire.index].neigh_wires[cursor]; + WireId result; + result.index = nw.wire_index; + if (!chip_rel_tile(chip, baseWire.tile, nw.rel_x, nw.rel_y, result.tile)) + return WireId(); + return result; + } + } +}; + +// ----------------------------------------------------------------------- + +struct AllPipIterator +{ + const DatabasePOD *db; + const ChipInfoPOD *chip; + int cursor_index; + int cursor_tile; + + AllPipIterator operator++() + { + cursor_index++; + while (cursor_tile < int(chip->num_tiles) && + cursor_index >= int(db->loctypes[chip->grid[cursor_tile].loc_type].num_pips)) { + cursor_index = 0; + cursor_tile++; + } + return *this; + } + AllPipIterator operator++(int) + { + AllPipIterator prior(*this); + ++(*this); + return prior; + } + + bool operator!=(const AllPipIterator &other) const + { + return cursor_index != other.cursor_index || cursor_tile != other.cursor_tile; + } + + bool operator==(const AllPipIterator &other) const + { + return cursor_index == other.cursor_index && cursor_tile == other.cursor_tile; + } + + PipId operator*() const + { + PipId ret; + ret.tile = cursor_tile; + ret.index = cursor_index; + return ret; + } +}; + +struct AllPipRange +{ + AllPipIterator b, e; + AllPipIterator begin() const { return b; } + AllPipIterator end() const { return e; } +}; + +// ----------------------------------------------------------------------- + +struct UpDownhillPipIterator +{ + const DatabasePOD *db; + const ChipInfoPOD *chip; + TileWireIterator twi, twi_end; + int cursor = -1; + bool uphill = false; + + void operator++() + { + cursor++; + while (true) { + if (!(twi != twi_end)) + break; + WireId w = *twi; + auto &tile = db->loctypes[chip->grid[w.tile].loc_type]; + if (cursor < int(uphill ? tile.wires[w.index].num_uphill : tile.wires[w.index].num_downhill)) + break; + ++twi; + cursor = 0; + } + } + bool operator!=(const UpDownhillPipIterator &other) const { return twi != other.twi || cursor != other.cursor; } + + PipId operator*() const + { + PipId ret; + WireId w = *twi; + ret.tile = w.tile; + auto &tile = db->loctypes[chip->grid[w.tile].loc_type]; + ret.index = uphill ? tile.wires[w.index].pips_uh[cursor] : tile.wires[w.index].pips_dh[cursor]; + return ret; + } +}; + +struct UpDownhillPipRange +{ + UpDownhillPipIterator b, e; + UpDownhillPipIterator begin() const { return b; } + UpDownhillPipIterator end() const { return e; } +}; + +// ----------------------------------------------------------------------- + const int bba_version = #include "bba_version.inc" ; @@ -205,52 +530,20 @@ struct Arch : BaseCtx int getTileBelDimZ(int, int) const { return 256; } int getTilePipDimZ(int, int) const { return 1; } - template const LocTypePOD &loc_data(Id &id) const - { - return db->loctypes[chip_info->grid[id.tile].loc_type]; - } + template const LocTypePOD &loc_data(Id &id) const { return chip_loc_data(db, chip_info, id); } - template const LocNeighourhoodPOD &nh_data(Id &id) const - { - auto &t = chip_info->grid[id.tile]; - return db->loctypes[t.loc_type].neighbourhoods[t.neighbourhood_type]; - } + template const LocNeighourhoodPOD &nh_data(Id &id) const { return chip_nh_data(db, chip_info, id); } - inline const BelInfoPOD &bel_data(BelId id) const { return loc_data(id).bels[id.index]; } - inline const LocWireInfoPOD &wire_data(WireId &id) const { return loc_data(id).wires[id.index]; } - inline const PipInfoPOD &pip_data(PipId &id) const { return loc_data(id).pips[id.index]; } + inline const BelInfoPOD &bel_data(BelId id) const { return chip_bel_data(db, chip_info, id); } + inline const LocWireInfoPOD &wire_data(WireId &id) const { return chip_wire_data(db, chip_info, id); } + inline const PipInfoPOD &pip_data(PipId &id) const { return chip_pip_data(db, chip_info, id); } inline bool rel_tile(int32_t base, int16_t rel_x, int16_t rel_y, int32_t &next) { - int32_t curr_x = base % chip_info->width; - int32_t curr_y = base / chip_info->width; - int32_t new_x = curr_x + rel_x; - int32_t new_y = curr_y + rel_y; - if (new_x < 0 || new_x >= chip_info->width) - return false; - if (new_y < 0 || new_y >= chip_info->height) - return false; - next = new_y * chip_info->width + new_x; - return true; + return chip_rel_tile(chip_info, base, rel_x, rel_y, next); } inline const WireId canonical_wire(int32_t tile, uint16_t index) { - WireId wire{tile, index}; - // `tile` is the primary location for the wire, so ID is already canonical - if (wire_data(wire).flags & WIRE_PRIMARY) - return wire; - // Not primary; find the primary location which forms the canonical ID - auto &nd = nh_data(wire); - auto &wn = nd.wire_neighbours[index]; - for (size_t i = 0; i < wn.num_nwires; i++) { - auto &nw = wn.neigh_wires[i]; - if (nw.arc_flags & LOGICAL_TO_PRIMARY) { - if (rel_tile(tile, nw.rel_x, nw.rel_y, wire.tile)) { - wire.index = nw.wire_index; - break; - } - } - } - return wire; + return chip_canonical_wire(db, chip_info, tile, index); } }; -- cgit v1.2.3