18 namespace module_identification
32 std::vector<std::unique_ptr<BaseCandidate>> find_carry_chains(
const Netlist* nl)
34 std::vector<std::vector<Gate*>> carry_chains;
37 std::vector<Gate*> carry_gates = nl->get_gates([](
const Gate* g) {
return g->get_type()->has_property(
GateTypeProperty::c_carry); });
38 std::set<Gate*> carry_gates_set = std::set<Gate*>(carry_gates.begin(), carry_gates.end());
41 while (!carry_gates_set.empty())
43 Gate* current_gate = *carry_gates_set.begin();
44 const GateType* carry_type = current_gate->get_type();
47 auto chain_res = NetlistTraversalDecorator(*nl).get_gate_chain(current_gate, {carry_type->get_pin_by_name(
"CI")}, {carry_type->get_pin_by_name(
"CO")});
48 if (chain_res.is_error())
50 return std::vector<std::unique_ptr<BaseCandidate>>();
52 std::vector<Gate*> carry_chain = chain_res.get();
55 for (Gate* g : carry_chain)
57 carry_gates_set.erase(g);
61 if (carry_chain.size() >= 2)
63 carry_chains.push_back(carry_chain);
68 std::vector<std::vector<Gate*>> filtered_carry_chains;
69 for (
u32 i = 0; i < carry_chains.size(); i++)
71 auto& c_test = carry_chains.at(i);
72 std::set<Gate*> test_set = {c_test.begin(), c_test.end()};
75 for (
u32 j = 0; j < carry_chains.size(); j++)
82 auto& c_other = carry_chains.at(j);
83 std::set<Gate*> other_set = {c_other.begin(), c_other.end()};
85 if (std::includes(other_set.begin(), other_set.end(), test_set.begin(), test_set.end()))
94 filtered_carry_chains.push_back(c_test);
98 std::vector<std::unique_ptr<BaseCandidate>> base_candidates;
99 for (
const auto& carry_chain : filtered_carry_chains)
101 std::unique_ptr<BaseCandidate> base_candidate = std::make_unique<BaseCandidate>(carry_chain);
102 base_candidates.emplace_back(std::move(base_candidate));
105 return base_candidates;
117 std::vector<std::vector<Gate*>> generate_carry_chain_variants(
const BaseCandidate* base_candidate,
const std::vector<std::vector<Gate*>>& all_base_candidates_gates)
119 std::set<u32> possible_starting_points = {0};
120 for (
u32 idx = 1; idx < base_candidate->m_gates.size(); idx++)
123 if (idx < (base_candidate->m_gates.size() - 1))
125 const auto& g = base_candidate->m_gates.at(idx);
126 const auto& constant_inputs = g->get_fan_in_nets([](
const auto& n) {
return n->is_gnd_net() || n->is_vcc_net(); });
128 const auto& g_next = base_candidate->m_gates.at(idx + 1);
129 const auto& constant_inputs_next = g_next->get_fan_in_nets([](
const auto& n) {
return n->is_gnd_net() || n->is_vcc_net(); });
131 if (!constant_inputs.empty() && constant_inputs_next.empty())
133 possible_starting_points.insert(idx);
134 possible_starting_points.insert(idx + 1);
139 if (idx < (base_candidate->m_gates.size() - 1))
141 const auto& g_curr = base_candidate->m_gates.at(idx);
143 bool is_part_of_multiple_base_candidates =
false;
144 for (
const auto& bc_gates : all_base_candidates_gates)
146 if (bc_gates == base_candidate->m_gates)
151 if (std::find(bc_gates.begin(), bc_gates.end(), g_curr) != bc_gates.end())
153 is_part_of_multiple_base_candidates =
true;
158 if (is_part_of_multiple_base_candidates)
160 possible_starting_points.insert(idx + 1);
165 const auto& g_prev = base_candidate->m_gates.at(idx - 1);
166 const auto& g_curr = base_candidate->m_gates.at(idx);
168 bool prev_has_outside_succ = !g_prev
169 ->get_successors([&](
const auto _gp,
auto ep) {
171 return std::find(base_candidate->m_gates.begin(), base_candidate->m_gates.end(), ep->get_gate()) == base_candidate->m_gates.end();
174 bool curr_has_outside_succ = !g_curr
175 ->get_successors([&](
const auto _gp,
auto ep) {
177 return std::find(base_candidate->m_gates.begin(), base_candidate->m_gates.end(), ep->get_gate()) == base_candidate->m_gates.end();
181 if (curr_has_outside_succ && !prev_has_outside_succ)
183 possible_starting_points.insert(idx);
188 if (possible_starting_points.size() > 4)
190 return {base_candidate->m_gates};
193 std::vector<std::vector<Gate*>> carry_chain_variants;
194 for (
const auto& idx : possible_starting_points)
196 carry_chain_variants.push_back({base_candidate->m_gates.begin() + idx, base_candidate->m_gates.end()});
199 return carry_chain_variants;
213 std::vector<std::unique_ptr<StructuralCandidate>> build_structural_candidates(BaseCandidate* base_candidate,
const std::vector<Gate*>& carry_chain)
215 std::vector<std::unique_ptr<StructuralCandidate>> candidates;
219 std::set<Gate*> all_comb_gates = {};
220 for (
const auto& g : carry_chain)
226 all_comb_gates.insert(g);
227 all_comb_gates.insert(next_gates.begin(), next_gates.end());
230 std::unique_ptr<StructuralCandidate> all_comb_candidate = std::make_unique<StructuralCandidate>(base_candidate,
utils::to_vector(all_comb_gates));
231 if (all_comb_gates.size() <= (base_candidate->m_gates.size() * 16))
233 candidates.emplace_back(std::move(all_comb_candidate));
240 std::vector<Gate*> starting_gates = carry_chain;
241 std::set<Gate*> successor_gates;
242 for (
const auto& sg : starting_gates)
244 for (
const auto& ep : sg->get_successors())
248 successor_gates.insert(ep->get_gate());
253 starting_gates.insert(starting_gates.end(), successor_gates.begin(), successor_gates.end());
254 std::set<Gate*> all_comb_gates = {};
255 for (
const auto& g : starting_gates)
261 all_comb_gates.insert(g);
262 all_comb_gates.insert(next_gates.begin(), next_gates.end());
266 std::unique_ptr<StructuralCandidate> all_comb_candidate_ext = std::make_unique<StructuralCandidate>(base_candidate,
utils::to_vector(all_comb_gates));
267 if (all_comb_gates.size() <= (base_candidate->m_gates.size() * 8))
269 candidates.emplace_back(std::move(all_comb_candidate_ext));
273 Gate* first_carry = carry_chain.front();
274 Gate* last_carry = carry_chain.back();
276 std::vector<std::vector<Gate*>> candidate_gate_variants = {carry_chain};
277 std::vector<std::vector<Gate*>> candidate_gate_variants_without_last_gate = {carry_chain};
284 log_info(
"module_identification",
"\tcarry_chain: {}", first_carry->get_name());
288 for (
const auto& gate : carry_chain)
290 std::vector<std::vector<Gate*>> new_candidate_gate_variants;
291 std::vector<std::vector<Gate*>> new_candidate_gate_variants_without_last_gate;
293 if ((gate != last_carry) && (gate->get_successors().size() > 4))
298 for (
const auto& suc_endp : gate->get_successors())
300 auto suc_gate = suc_endp->get_gate();
304 log_error(
"module_identification",
"\tfound IO gate, but why?");
313 for (
const auto& cgv : candidate_gate_variants)
315 if (std::find(cgv.begin(), cgv.end(), suc_gate) != cgv.end())
321 new_cgv.push_back(suc_gate);
323 new_candidate_gate_variants.push_back(new_cgv);
326 if (new_candidate_gate_variants.size() > 4)
331 if (gate != last_carry)
333 new_candidate_gate_variants_without_last_gate = new_candidate_gate_variants;
337 new_candidate_gate_variants_without_last_gate = candidate_gate_variants_without_last_gate;
342 if (!new_candidate_gate_variants.empty())
344 candidate_gate_variants = new_candidate_gate_variants;
345 candidate_gate_variants_without_last_gate = new_candidate_gate_variants_without_last_gate;
349 for (
const auto& cgv : candidate_gate_variants)
351 std::set<Gate*> unique_gates = {cgv.begin(), cgv.end()};
352 std::vector<Gate*> cgv_filtered = {unique_gates.begin(), unique_gates.end()};
354 candidates.push_back(std::make_unique<StructuralCandidate>(base_candidate, cgv_filtered));
357 for (
const auto& cgv : candidate_gate_variants_without_last_gate)
359 std::set<Gate*> unique_gates = {cgv.begin(), cgv.end()};
360 std::vector<Gate*> cgv_filtered = {unique_gates.begin(), unique_gates.end()};
362 candidates.push_back(std::make_unique<StructuralCandidate>(base_candidate, cgv_filtered));
366 auto input_nets_first_gate = first_carry->get_fan_in_nets([](Net*
net) {
return !(
net->is_gnd_net() ||
net->is_vcc_net()); });
368 std::vector<Gate*> total_successor_gates;
369 std::vector<Gate*> total_reduced_successor_gates;
370 std::vector<Gate*> total_more_reduced_successor_gates;
372 for (
const auto input_net : input_nets_first_gate)
374 auto successor_enpoints = input_net->get_destinations();
375 for (
const auto& ep : successor_enpoints)
377 auto gate = ep->get_gate();
403 total_successor_gates.push_back(gate);
405 const auto gt = gate->get_type();
409 bool is_not_four_input = gate->get_fan_in_nets([](Net*
net) {
return !(
net->is_gnd_net() ||
net->is_vcc_net()); }).
size() < 4;
411 bool to_be_considered = is_not_four_input;
413 if (!to_be_considered)
418 total_reduced_successor_gates.push_back(gate);
421 bool is_not_three_input = gate->get_fan_in_nets([](Net*
net) {
return !(
net->is_gnd_net() ||
net->is_vcc_net()); }).
size() < 3;
423 bool to_be_more_considered = is_not_three_input && is_not_ao;
425 if (!to_be_more_considered)
430 total_more_reduced_successor_gates.push_back(gate);
434 std::set<std::vector<Gate*>> possible_first_gates;
436 const auto considered_gates =
437 ((total_successor_gates.size() > 16) ? ((total_reduced_successor_gates.size() > 16) ? total_more_reduced_successor_gates : total_reduced_successor_gates) : total_successor_gates);
439 for (
const auto& gate : considered_gates)
441 auto nets = gate->get_fan_in_nets([](Net*
net) {
return !(
net->is_gnd_net() ||
net->is_vcc_net()); });
442 bool consider_gate =
true;
443 for (
auto const& mandatory_input_net : input_nets_first_gate)
445 if (std::find(nets.begin(), nets.end(), mandatory_input_net) == nets.end())
447 consider_gate =
false;
456 possible_first_gates.insert({gate});
459 auto pres_first_gate = gate->get_predecessors();
460 std::vector<Gate*> new_inv_first_gates;
461 for (
const auto& pre_first_gate : pres_first_gate)
465 new_inv_first_gates.emplace_back(pre_first_gate->get_gate());
469 for (
const auto& inv_gate : new_inv_first_gates)
471 possible_first_gates.insert({gate, inv_gate});
475 for (
const auto& gate2 : total_reduced_successor_gates)
482 possible_first_gates.insert({gate, gate2});
489 std::vector<Gate*> first_carry_inverters;
490 for (
const auto& pre_first_carry : first_carry->get_predecessors())
494 first_carry_inverters.emplace_back(pre_first_carry->get_gate());
498 if (possible_first_gates.empty())
500 for (
const auto& gate : considered_gates)
502 possible_first_gates.insert({gate});
504 for (
const auto& inv_gate : first_carry_inverters)
506 possible_first_gates.insert({gate, inv_gate});
510 auto successors = gate->get_successors();
511 if (successors.size() != 1)
515 auto suc_gate = successors.front()->get_gate();
522 possible_first_gates.insert({gate, suc_gate});
527 std::vector<std::vector<Gate*>> new_candidate_gate_variants;
528 for (
const auto& c : candidates)
530 for (
const auto& add_gates : possible_first_gates)
532 auto new_gates = c->m_gates;
533 new_gates.insert(new_gates.end(), add_gates.begin(), add_gates.end());
534 new_candidate_gate_variants.push_back(new_gates);
538 for (
auto& new_cgv : new_candidate_gate_variants)
540 candidates.push_back(std::make_unique<StructuralCandidate>(base_candidate, new_cgv));
543 std::vector<std::unique_ptr<StructuralCandidate>> new_inverter_candidates;
546 for (
const auto& candidate : candidates)
548 u32 inverter_counter = 0;
549 u32 carry_counter = 0;
550 std::unique_ptr<StructuralCandidate> new_candidate = std::make_unique<StructuralCandidate>(base_candidate, candidate->m_gates);
551 for (
const auto& gate : candidate->m_gates)
555 auto suc_endpoints = gate->get_successors();
556 std::vector<Gate*> inverter_successors;
557 for (
const auto& suc_endpoint : suc_endpoints)
559 auto suc_gate = suc_endpoint->get_gate();
562 inverter_successors.push_back(suc_gate);
566 if (inverter_successors.size() > 2)
571 for (
const auto& is : inverter_successors)
574 new_candidate->m_gates.push_back(is);
582 if (inverter_counter >= carry_counter - 1)
584 new_inverter_candidates.emplace_back(std::move(new_candidate));
588 for (
auto& ic : new_inverter_candidates)
590 candidates.push_back(std::move(ic));
594 std::vector<std::unique_ptr<StructuralCandidate>> new_candidates;
598 for (
const auto& candidate : candidates)
600 Gate* last_gate = candidate->m_gates.back();
602 for (
const auto& pred_endp : last_gate->get_predecessors())
604 Gate* pred_gate = pred_endp->get_gate();
610 std::unique_ptr<StructuralCandidate> new_candidate = std::make_unique<StructuralCandidate>(base_candidate, candidate->m_gates);
611 new_candidate->m_gates.emplace_back(pred_gate);
612 new_candidates.emplace_back(std::move(new_candidate));
615 for (
auto& nc : new_candidates)
617 candidates.push_back(std::move(nc));
623 for (
auto& cand : candidates)
625 if (!std::any_of(cand->m_gates.begin(), cand->m_gates.end(), [](
const auto& g) { return g->is_gnd_gate() || g->is_vcc_gate(); }))
631 cand->m_gates.erase(std::remove_if(cand->m_gates.begin(),
634 return g->is_gnd_gate() || g->is_vcc_gate();
636 cand->m_gates.end());
641 std::set<std::set<Gate*>> all_sets;
642 u32 old_size = candidates.size();
643 std::vector<std::unique_ptr<StructuralCandidate>> candidates_to_return;
645 for (
auto& cand : candidates)
647 std::set<Gate*> set_gates = {cand->m_gates.begin(), cand->m_gates.end()};
648 if (all_sets.find(set_gates) == all_sets.end())
650 all_sets.insert(set_gates);
651 candidates_to_return.push_back(std::make_unique<StructuralCandidate>(base_candidate, std::vector<Gate*>{set_gates.begin(), set_gates.end()}));
655 log_info(
"module_identification",
"\tremaining {}/{} after double candidate removal", candidates_to_return.size(), old_size);
656 return candidates_to_return;
662 std::vector<std::pair<std::unique_ptr<BaseCandidate>, std::vector<std::unique_ptr<StructuralCandidate>>>> base_to_structural_candidates;
664 auto base_candidates = find_carry_chains(nl);
666 std::vector<std::vector<Gate*>> all_base_candidates_gates;
667 for (
const auto& bc : base_candidates)
669 all_base_candidates_gates.push_back(bc->m_gates);
672 log_info(
"module_identification",
"found {} carry chains, building structural variants now...", base_candidates.size());
674 for (
auto& base_candidate : base_candidates)
676 const auto& carry_chain_variants = generate_carry_chain_variants(base_candidate.get(), all_base_candidates_gates);
678 std::vector<std::unique_ptr<StructuralCandidate>> structural_candidates;
679 for (
const auto& ccv : carry_chain_variants)
681 auto new_candidates = build_structural_candidates(base_candidate.get(), ccv);
682 for (
auto& nc : new_candidates)
684 structural_candidates.push_back(std::move(nc));
688 base_to_structural_candidates.push_back({std::move(base_candidate), std::move(structural_candidates)});
691 return base_to_structural_candidates;
This file contains the definition of the BaseCandidate class, which represents a base candidate in th...
#define log_error(channel,...)
#define log_info(channel,...)
This file contains the function to generate structural candidates for Lattice iCE40 FPGAs.
std::vector< std::pair< std::unique_ptr< BaseCandidate >, std::vector< std::unique_ptr< StructuralCandidate > > > > generate_structural_candidates(const Netlist *nl)
Generate structural candidates for a given netlist.
@ lattice_ice40
Lattice iCE40 FPGA architecture.
std::vector< Gate * > get_next_gates(const Gate *gate, bool get_successors, int depth=0, const std::function< bool(const Gate *)> &filter=nullptr)
bool is_subset(const T1 &subset, const T2 &superset)
std::vector< T > to_vector(const Container< T, Args... > &container)
This file contains the class for defining and managing structural candidates within the module identi...