From 8d9444b6f0df174fcbf0b9a619ce7793ae5adc02 Mon Sep 17 00:00:00 2001 From: David Shah Date: Mon, 25 Jun 2018 14:45:33 +0200 Subject: ice40: More preparations for carry legalisation Signed-off-by: David Shah --- ice40/cells.cc | 2 + ice40/place_legaliser.cc | 108 ++++++++++++++++++++++++++++++++++------------- 2 files changed, 80 insertions(+), 30 deletions(-) (limited to 'ice40') diff --git a/ice40/cells.cc b/ice40/cells.cc index ddb69f4f..e9c75649 100644 --- a/ice40/cells.cc +++ b/ice40/cells.cc @@ -47,6 +47,8 @@ CellInfo *create_ice_cell(Context *ctx, IdString type, std::string name) new_cell->params[ctx->id("DFF_ENABLE")] = "0"; new_cell->params[ctx->id("SET_NORESET")] = "0"; new_cell->params[ctx->id("ASYNC_SR")] = "0"; + new_cell->params[ctx->id("CIN_CONST")] = "0"; + new_cell->params[ctx->id("CIN_SET")] = "0"; add_port(ctx, new_cell, "I0", PORT_IN); add_port(ctx, new_cell, "I1", PORT_IN); diff --git a/ice40/place_legaliser.cc b/ice40/place_legaliser.cc index 83316d6e..a4e8da0c 100644 --- a/ice40/place_legaliser.cc +++ b/ice40/place_legaliser.cc @@ -61,7 +61,8 @@ std::vector> find_chains(const Context *ctx, F1 cell_typ return chains; } -static void get_chain_midpoint(const Context *ctx, const std::vector &chain, float &x, float &y) { +static void get_chain_midpoint(const Context *ctx, const std::vector &chain, float &x, float &y) +{ float total_x = 0, total_y = 0; int N = 0; for (auto cell : chain) { @@ -79,38 +80,85 @@ static void get_chain_midpoint(const Context *ctx, const std::vector y = total_y / N; } -static CellInfo *make_carry_pass_out(Context *ctx, PortInfo &cout_port) { - assert(cout_port.net != nullptr); - CellInfo *lc = create_ice_cell(ctx, ctx->id("ICESTORM_LC")); - lc->params[ctx->id("LUT_INIT")] = "65280"; // 0xff00: O = I3 - lc->ports.at(ctx->id("O")).net = cout_port.net; - NetInfo *co_i3_net = new NetInfo(); - co_i3_net->name = ctx->id(lc->name.str(ctx) + "$I3"); - co_i3_net->driver = cout_port.net->driver; - PortRef i3_r; - i3_r.port = ctx->id("I3"); - i3_r.cell = lc; - co_i3_net->users.push_back(i3_r); - PortRef o_r; - o_r.port = ctx->id("O"); - o_r.cell = lc; - cout_port.net->driver = o_r; - lc->ports.at(ctx->id("I3")).net = co_i3_net; - return lc; -} +class PlacementLegaliser +{ + public: + PlacementLegaliser(Context *ctx) : ctx(ctx){}; + bool legalise() + { + bool legalised_carries = legalise_carries(); + if (!legalised_carries && !ctx->force) + return false; + return legalised_carries; + } + + private: + bool legalise_carries() + { + std::vector> carry_chains = find_chains( + ctx, is_lc, + [](const Context *ctx, const CellInfo *cell) { + return net_driven_by(ctx, cell->ports.at(ctx->id("CIN")).net, is_lc, ctx->id("COUT")); + }, + [](const Context *ctx, const CellInfo *cell) { + return net_only_drives(ctx, cell->ports.at(ctx->id("COUT")).net, is_lc, ctx->id("CIN"), false); + }); + // TODO + return true; + } + + CellInfo *make_carry_pass_out(PortInfo &cout_port) + { + assert(cout_port.net != nullptr); + CellInfo *lc = create_ice_cell(ctx, ctx->id("ICESTORM_LC")); + lc->params[ctx->id("LUT_INIT")] = "65280"; // 0xff00: O = I3 + lc->ports.at(ctx->id("O")).net = cout_port.net; + NetInfo *co_i3_net = new NetInfo(); + co_i3_net->name = ctx->id(lc->name.str(ctx) + "$I3"); + co_i3_net->driver = cout_port.net->driver; + PortRef i3_r; + i3_r.port = ctx->id("I3"); + i3_r.cell = lc; + co_i3_net->users.push_back(i3_r); + PortRef o_r; + o_r.port = ctx->id("O"); + o_r.cell = lc; + cout_port.net->driver = o_r; + lc->ports.at(ctx->id("I3")).net = co_i3_net; + ctx->cells[lc->name] = lc; + createdCells.insert(lc->name); + return lc; + } + + CellInfo *make_carry_feed_in(CellInfo *cin_cell, PortInfo &cin_port) + { + assert(cin_port.net != nullptr); + CellInfo *lc = create_ice_cell(ctx, ctx->id("ICESTORM_LC")); + lc->params[ctx->id("CARRY_ENABLE")] = "1"; + lc->params[ctx->id("CIN_CONST")] = "1"; + lc->params[ctx->id("CIN_SET")] = "1"; + lc->ports.at(ctx->id("I1")).net = cin_port.net; + cin_port.net->users.erase(std::remove_if(cin_port.net->users.begin(), cin_port.net->users.end(), + [cin_cell, cin_port](const PortRef &usr) { + return usr.cell == cin_cell && usr.port == cin_port.name; + })); + NetInfo *out_net = new NetInfo(); + out_net->name = ctx->id(lc->name.str(ctx) + "$O"); + + ctx->cells[lc->name] = lc; + createdCells.insert(lc->name); + return lc; + } + + Context *ctx; + std::unordered_set rippedCells; + std::unordered_set createdCells; +}; bool legalise_design(Context *ctx) { - std::vector> carry_chains = find_chains( - ctx, is_lc, - [](const Context *ctx, const CellInfo *cell) { - return net_driven_by(ctx, cell->ports.at(ctx->id("CIN")).net, is_lc, ctx->id("COUT")); - }, - [](const Context *ctx, const CellInfo *cell) { - return net_only_drives(ctx, cell->ports.at(ctx->id("COUT")).net, is_lc, ctx->id("CIN"), false); - }); - // TODO - return true; + PlacementLegaliser lg(ctx); + return lg.legalise(); } NEXTPNR_NAMESPACE_END -- cgit v1.2.3 From 6d154cfa1300cf88c1556657b37f7fbcc8da8d6a Mon Sep 17 00:00:00 2001 From: David Shah Date: Mon, 25 Jun 2018 15:39:46 +0200 Subject: ice40: Creating a carry chain splitter function Signed-off-by: David Shah --- ice40/pack.cc | 12 ++++---- ice40/place_legaliser.cc | 78 ++++++++++++++++++++++++++++++++++++++++++------ 2 files changed, 74 insertions(+), 16 deletions(-) (limited to 'ice40') diff --git a/ice40/pack.cc b/ice40/pack.cc index 85c1af8c..54e6dad2 100644 --- a/ice40/pack.cc +++ b/ice40/pack.cc @@ -258,7 +258,7 @@ static void pack_constants(Context *ctx) std::vector dead_nets; - bool gnd_used = false, vcc_used = false; + bool gnd_used = false; for (auto net : sorted(ctx->nets)) { NetInfo *ni = net.second; @@ -268,7 +268,6 @@ static void pack_constants(Context *ctx) dead_nets.push_back(net.first); } else if (ni->driver.cell != nullptr && ni->driver.cell->type == ctx->id("VCC")) { set_net_constant(ctx, ni, vcc_net, true); - vcc_used = true; dead_nets.push_back(net.first); } } @@ -277,11 +276,10 @@ static void pack_constants(Context *ctx) ctx->cells[gnd_cell->name] = gnd_cell; ctx->nets[gnd_net->name] = gnd_net; } - - if (vcc_used) { - ctx->cells[vcc_cell->name] = vcc_cell; - ctx->nets[vcc_net->name] = vcc_net; - } + // Vcc cell always inserted for now, as it may be needed during carry legalisation (TODO: trim later if actually + // never used?) + ctx->cells[vcc_cell->name] = vcc_cell; + ctx->nets[vcc_net->name] = vcc_net; for (auto dn : dead_nets) ctx->nets.erase(dn); diff --git a/ice40/place_legaliser.cc b/ice40/place_legaliser.cc index a4e8da0c..0372ad6c 100644 --- a/ice40/place_legaliser.cc +++ b/ice40/place_legaliser.cc @@ -27,13 +27,18 @@ NEXTPNR_NAMESPACE_BEGIN +struct CellChain +{ + std::vector cells; +}; + // Generic chain finder template -std::vector> find_chains(const Context *ctx, F1 cell_type_predicate, F2 get_previous, - F3 get_next, size_t min_length = 2) +std::vector find_chains(const Context *ctx, F1 cell_type_predicate, F2 get_previous, F3 get_next, + size_t min_length = 2) { std::set chained; - std::vector> chains; + std::vector chains; for (auto cell : sorted(ctx->cells)) { if (chained.find(cell.first) != chained.end()) continue; @@ -45,15 +50,15 @@ std::vector> find_chains(const Context *ctx, F1 cell_typ start = prev_start; prev_start = get_previous(ctx, start); } - std::vector chain; + CellChain chain; CellInfo *end = start; while (end != nullptr) { - chain.push_back(end); + chain.cells.push_back(end); end = get_next(ctx, end); } - if (chain.size() >= min_length) { + if (chain.cells.size() >= min_length) { chains.push_back(chain); - for (auto c : chain) + for (auto c : chain.cells) chained.insert(c->name); } } @@ -95,7 +100,7 @@ class PlacementLegaliser private: bool legalise_carries() { - std::vector> carry_chains = find_chains( + std::vector carry_chains = find_chains( ctx, is_lc, [](const Context *ctx, const CellInfo *cell) { return net_driven_by(ctx, cell->ports.at(ctx->id("CIN")).net, is_lc, ctx->id("COUT")); @@ -103,15 +108,63 @@ class PlacementLegaliser [](const Context *ctx, const CellInfo *cell) { return net_only_drives(ctx, cell->ports.at(ctx->id("COUT")).net, is_lc, ctx->id("CIN"), false); }); - // TODO + for (auto chain : carry_chains) { + } return true; } + // Split a carry chain into multiple legal chains + std::vector split_carry_chain(Context *ctx, CellChain &carryc) + { + bool start_of_chain = true; + std::vector chains; + std::vector tile; + const int max_length = (ctx->chip_info->height - 2) * 8 - 2; + auto curr_cell = carryc.cells.begin(); + while (curr_cell != carryc.cells.end()) { + CellInfo *cell = *curr_cell; + if (tile.size() >= 8) { + tile.clear(); + } + if (start_of_chain) { + tile.clear(); + chains.emplace_back(); + start_of_chain = false; + if (cell->ports.at(ctx->id("CIN")).net) { + // CIN is not constant and not part of a chain. Must feed in from fabric + CellInfo *feedin = make_carry_feed_in(cell, cell->ports.at(ctx->id("CIN"))); + chains.back().cells.push_back(feedin); + tile.push_back(feedin); + } + } + tile.push_back(cell); + chains.back().cells.push_back(cell); + bool split_chain = (!ctx->logicCellsCompatible(tile)) || (int(chains.back().cells.size()) > max_length); + if (split_chain) { + CellInfo *passout = make_carry_pass_out(cell->ports.at(ctx->id("COUT"))); + tile.pop_back(); + chains.back().cells.back() = passout; + start_of_chain = true; + } else { + NetInfo *carry_net = cell->ports.at(ctx->id("COUT")).net; + if (carry_net != nullptr && carry_net->users.size() > 1) { + CellInfo *passout = make_carry_pass_out(cell->ports.at(ctx->id("COUT"))); + chains.back().cells.push_back(passout); + tile.push_back(passout); + } + ++curr_cell; + } + } + return chains; + } + + // Insert a logic cell to legalise a COUT->fabric connection CellInfo *make_carry_pass_out(PortInfo &cout_port) { assert(cout_port.net != nullptr); CellInfo *lc = create_ice_cell(ctx, ctx->id("ICESTORM_LC")); lc->params[ctx->id("LUT_INIT")] = "65280"; // 0xff00: O = I3 + lc->params[ctx->id("CARRY_ENABLE")] = "1"; lc->ports.at(ctx->id("O")).net = cout_port.net; NetInfo *co_i3_net = new NetInfo(); co_i3_net->name = ctx->id(lc->name.str(ctx) + "$I3"); @@ -125,11 +178,18 @@ class PlacementLegaliser o_r.cell = lc; cout_port.net->driver = o_r; lc->ports.at(ctx->id("I3")).net = co_i3_net; + // I1=1 feeds carry up the chain, so no need to actually break the chain + lc->ports.at(ctx->id("I1")).net = ctx->nets.at(ctx->id("$PACKER_VCC_NET")); + PortRef i1_r; + i1_r.port = ctx->id("I1"); + i1_r.cell = lc; + ctx->nets.at(ctx->id("$PACKER_VCC_NET"))->users.push_back(i1_r); ctx->cells[lc->name] = lc; createdCells.insert(lc->name); return lc; } + // Insert a logic cell to legalise a CIN->fabric connection CellInfo *make_carry_feed_in(CellInfo *cin_cell, PortInfo &cin_port) { assert(cin_port.net != nullptr); -- cgit v1.2.3 From bee6bc461d4836fd39bf2142ae1d6b004b514bab Mon Sep 17 00:00:00 2001 From: David Shah Date: Mon, 25 Jun 2018 16:15:47 +0200 Subject: ice40: Working on the placement legaliser Signed-off-by: David Shah --- ice40/place_legaliser.cc | 47 +++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 43 insertions(+), 4 deletions(-) (limited to 'ice40') diff --git a/ice40/place_legaliser.cc b/ice40/place_legaliser.cc index 0372ad6c..52a116b2 100644 --- a/ice40/place_legaliser.cc +++ b/ice40/place_legaliser.cc @@ -66,11 +66,11 @@ std::vector find_chains(const Context *ctx, F1 cell_type_predicate, F return chains; } -static void get_chain_midpoint(const Context *ctx, const std::vector &chain, float &x, float &y) +static void get_chain_midpoint(const Context *ctx, const CellChain &chain, float &x, float &y) { float total_x = 0, total_y = 0; int N = 0; - for (auto cell : chain) { + for (auto cell : chain.cells) { if (cell->bel == BelId()) continue; int bel_x, bel_y; @@ -89,6 +89,7 @@ class PlacementLegaliser { public: PlacementLegaliser(Context *ctx) : ctx(ctx){}; + bool legalise() { bool legalised_carries = legalise_carries(); @@ -98,6 +99,27 @@ class PlacementLegaliser } private: + void init_logic_cells() + { + for (auto bel : ctx->getBels()) { + // Initialise the logic bels vector with unavailable invalid bels, dimensions [0..width][0..height[0..7] + logic_bels.resize(ctx->chip_info->width + 1, + std::vector>>( + ctx->chip_info->height + 1, + std::vector>(8, std::make_pair(BelId(), true)))); + if (ctx->getBelType(bel) == TYPE_ICESTORM_LC) { + // Using the non-standard API here to get (x, y, z) rather than just (x, y) + auto bi = ctx->chip_info->bel_data[bel.index]; + int x = bi.x, y = bi.y, z = bi.z; + IdString cell = ctx->getBoundBelCell(bel); + if (cell != IdString() && ctx->cells.at(cell)->belStrength >= STRENGTH_FIXED) + logic_bels.at(x).at(y).at(z) = std::make_pair(bel, true); + else + logic_bels.at(x).at(y).at(z) = std::make_pair(bel, false); + } + } + } + bool legalise_carries() { std::vector carry_chains = find_chains( @@ -108,13 +130,28 @@ class PlacementLegaliser [](const Context *ctx, const CellInfo *cell) { return net_only_drives(ctx, cell->ports.at(ctx->id("COUT")).net, is_lc, ctx->id("CIN"), false); }); - for (auto chain : carry_chains) { + int width = ctx->chip_info->width, height = ctx->chip_info->height; + for (auto &base_chain : carry_chains) { + std::vector split_chains = split_carry_chain(base_chain); + for (auto &chain : split_chains) { + float mid_x, mid_y; + get_chain_midpoint(ctx, chain, mid_x, mid_y); + float base_x = mid_x, base_y = mid_y - (chain.cells.size() / 16.0f); + // Find Bel meeting requirements closest to the target base + } } return true; } + // Find Bel closest to a location, meeting chain requirements + BelId find_closest_bel(float x, float y, int chain_size) + { + // TODO + return BelId(); + } + // Split a carry chain into multiple legal chains - std::vector split_carry_chain(Context *ctx, CellChain &carryc) + std::vector split_carry_chain(CellChain &carryc) { bool start_of_chain = true; std::vector chains; @@ -213,6 +250,8 @@ class PlacementLegaliser Context *ctx; std::unordered_set rippedCells; std::unordered_set createdCells; + // Go from X and Y position to logic cells, setting occupied to true if a Bel is unavailable + std::vector>>> logic_bels; }; bool legalise_design(Context *ctx) -- cgit v1.2.3