17 namespace module_identification
33 std::vector<std::unique_ptr<BaseCandidate>> find_carry_chains(
const Netlist* nl)
35 std::vector<std::vector<Gate*>> carry_chains;
38 std::vector<Gate*> carry_gates = nl->get_gates([](
const Gate* g) {
return g->get_type()->has_property(
GateTypeProperty::c_carry); });
39 std::set<Gate*> carry_gates_set = std::set<Gate*>(carry_gates.begin(), carry_gates.end());
42 while (!carry_gates_set.empty())
44 Gate* current_gate = *carry_gates_set.begin();
45 const GateType* carry_type = current_gate->get_type();
49 if (chain_res.is_error())
51 return std::vector<std::unique_ptr<BaseCandidate>>();
53 std::vector<Gate*> carry_chain = chain_res.get();
56 for (Gate* g : carry_chain)
58 carry_gates_set.erase(g);
62 if (carry_chain.size() >= 2)
64 log_debug(
"module_identification",
"\tcarry_gate: {}", carry_chain.front()->get_name());
65 carry_chains.push_back(carry_chain);
70 std::vector<std::vector<Gate*>> filtered_carry_chains;
71 for (
u32 i = 0; i < carry_chains.size(); i++)
73 auto& c_test = carry_chains.at(i);
74 std::set<Gate*> test_set = {c_test.begin(), c_test.end()};
77 for (
u32 j = 0; j < carry_chains.size(); j++)
84 auto& c_other = carry_chains.at(j);
85 std::set<Gate*> other_set = {c_other.begin(), c_other.end()};
87 if (std::includes(other_set.begin(), other_set.end(), test_set.begin(), test_set.end()))
96 filtered_carry_chains.push_back(c_test);
100 std::vector<std::unique_ptr<BaseCandidate>> base_candidates;
101 for (
const auto& carry_chain : filtered_carry_chains)
103 std::unique_ptr<BaseCandidate> base_candidate = std::make_unique<BaseCandidate>(carry_chain);
104 base_candidates.push_back(std::move(base_candidate));
107 return base_candidates;
120 std::vector<std::unique_ptr<StructuralCandidate>> build_structural_candidates(BaseCandidate* base_candidate)
122 std::vector<std::unique_ptr<StructuralCandidate>> candidates;
124 std::vector<Gate*> carry_chain = base_candidate->m_gates;
126 Gate* first_carry = carry_chain.front();
131 return std::vector<std::unique_ptr<StructuralCandidate>>();
133 log_debug(
"module_identification",
"\tcarry_chain: {}", first_carry->get_name());
137 std::unordered_set<Gate*> big_candidate_gates = {carry_chain.begin(), carry_chain.end()};
138 std::unordered_map<const Net*, std::unordered_set<Gate*>> cache;
140 for (
const auto& gate : carry_chain)
144 bool add_gate =
true;
172 for (
const auto& gate_to_add : gates)
174 big_candidate_gates.insert(gate_to_add);
178 if (big_candidate_gates.size() < (carry_chain.size() * 128))
182 std::unique_ptr<StructuralCandidate> candidate_big = std::make_unique<StructuralCandidate>(base_candidate, gate_vec);
183 log_debug(
"module_identification",
"big_candidate is {} big", candidate_big->m_gates.size());
184 candidates.push_back(std::move(candidate_big));
188 log_debug(
"module_identification",
"big_candidate is too big with {} gates", big_candidate_gates.size());
193 std::vector<Gate*> candidate_gates(carry_chain);
195 std::unique_ptr<StructuralCandidate> first_candidate = std::make_unique<StructuralCandidate>(base_candidate, candidate_gates);
196 if (first_candidate ==
nullptr)
198 log_error(
"module_identification",
"nullptr candidate after creation");
200 candidates.push_back(std::move(first_candidate));
203 for (
const auto& gate : carry_chain)
205 for (
const auto& pred_endp : gate->get_predecessors())
207 auto pred_gate = pred_endp->get_gate();
209 if (pred_gate->is_gnd_gate() || pred_gate->is_vcc_gate())
231 candidate_gates.push_back(pred_gate);
236 std::unique_ptr<StructuralCandidate> candidate_all_gates_infront_level_1 = std::make_unique<StructuralCandidate>(base_candidate, candidate_gates);
237 if (candidate_all_gates_infront_level_1 ==
nullptr)
239 log_error(
"module_identification",
"nullptr candidate after creation");
241 candidates.push_back(std::move(candidate_all_gates_infront_level_1));
244 std::vector<Gate*> si_di0_candidate_gates(carry_chain);
245 std::vector<std::string> allowed_pins_si_di0 = {
"S(0)",
"S(1)",
"S(2)",
"S(3)",
"DI(0)"};
247 for (
const auto& gate : carry_chain)
249 for (
const auto& pin : allowed_pins_si_di0)
251 const auto& pred_endp = gate->get_predecessor(pin);
252 if (pred_endp ==
nullptr)
256 auto pred_gate = pred_endp->get_gate();
257 if (pred_gate->is_gnd_gate() || pred_gate->is_vcc_gate())
264 log_error(
"module_identification",
"\tfound IO gate, but why?");
280 si_di0_candidate_gates.push_back(pred_gate);
284 std::unique_ptr<StructuralCandidate> candidate_gates_infront_of_si_di0 = std::make_unique<StructuralCandidate>(base_candidate, si_di0_candidate_gates);
285 if (candidate_gates_infront_of_si_di0 ==
nullptr)
287 log_error(
"module_identification",
"nullptr candidate after creation");
289 candidates.push_back(std::move(candidate_gates_infront_of_si_di0));
293 std::vector<Gate*> si_di_candidate_gates(carry_chain);
294 std::vector<std::string> allowed_pins_si_di = {
"S(0)",
"S(1)",
"S(2)",
"S(3)",
"DI(0)",
"DI(1)",
"DI(2)",
"DI(3)"};
296 for (
const auto& gate : carry_chain)
298 for (
const auto& pin : allowed_pins_si_di)
300 const auto& pred_endp = gate->get_predecessor(pin);
301 if (pred_endp ==
nullptr)
305 auto pred_gate = pred_endp->get_gate();
306 if (pred_gate->is_gnd_gate() || pred_gate->is_vcc_gate())
313 log_error(
"module_identification",
"\tfound IO gate, but why?");
328 si_di_candidate_gates.push_back(pred_gate);
332 std::unique_ptr<StructuralCandidate> candidate_gates_infront_of_si_di = std::make_unique<StructuralCandidate>(base_candidate, si_di_candidate_gates);
333 if (candidate_gates_infront_of_si_di ==
nullptr)
335 log_error(
"module_identification",
"nullptr candidate after creation");
337 candidates.push_back(std::move(candidate_gates_infront_of_si_di));
340 std::vector<Gate*> si_candidate_gates(carry_chain);
342 std::vector<std::string> allowed_pins_si = {
"S(0)",
"S(1)",
"S(2)",
"S(3)"};
343 for (
const auto& gate : carry_chain)
345 for (
const auto& pin : allowed_pins_si)
347 const auto& pred_endp = gate->get_predecessor(pin);
348 if (pred_endp ==
nullptr)
352 auto pred_gate = pred_endp->get_gate();
353 if (pred_gate->is_gnd_gate() || pred_gate->is_vcc_gate())
360 log_error(
"module_identification",
"\tfound IO gate, but why?");
376 si_candidate_gates.push_back(pred_gate);
381 std::vector<Gate*> candidate_gates_infront_of_si_gates;
382 for (
const auto& g : si_candidate_gates)
384 candidate_gates_infront_of_si_gates.push_back(g);
386 std::unique_ptr<StructuralCandidate> candidate_gates_infront_of_si = std::make_unique<StructuralCandidate>(base_candidate, candidate_gates_infront_of_si_gates);
388 candidates.push_back(std::move(candidate_gates_infront_of_si));
390 std::vector<std::unique_ptr<StructuralCandidate>> candidates_to_add;
393 for (
const auto& cand : candidates)
397 log_error(
"module_identification",
"nullptr candidate");
401 if (cand->m_gates.empty())
403 log_error(
"module_identification",
"candidate has no gates");
406 std::set<Gate*> additional_layer_gates;
408 for (
const auto& gate : cand->m_gates)
415 for (
const auto& pred_endp : gate->get_predecessors())
417 if (pred_endp ==
nullptr)
422 auto pred_gate = pred_endp->get_gate();
424 if (pred_gate ==
nullptr)
429 if (pred_gate->is_gnd_gate() || pred_gate->is_vcc_gate())
451 additional_layer_gates.insert(pred_gate);
455 std::vector<Gate*> all_gates(cand->m_gates);
456 for (
const auto& g : additional_layer_gates)
458 all_gates.push_back(g);
460 std::unique_ptr<StructuralCandidate> additional_gate_candidate = std::make_unique<StructuralCandidate>(base_candidate, all_gates);
461 candidates_to_add.push_back(std::move(additional_gate_candidate));
464 for (
auto& candidate_to_add : candidates_to_add)
466 candidates.push_back(std::move(candidate_to_add));
469 std::vector<std::unique_ptr<StructuralCandidate>> inv_candidates_to_add;
472 for (
const auto& cand : candidates)
476 log_error(
"module_identification",
"nullptr candidate");
480 if (cand->m_gates.empty())
482 log_error(
"module_identification",
"candidate has no gates");
485 std::set<Gate*> additional_layer_gates;
487 for (
const auto& gate : cand->m_gates)
494 for (
const auto& pred_endp : gate->get_predecessors())
496 if (pred_endp ==
nullptr)
501 auto pred_gate = pred_endp->get_gate();
503 if (pred_gate ==
nullptr)
510 additional_layer_gates.insert(pred_gate);
514 std::vector<Gate*> all_gates(cand->m_gates);
515 for (
const auto& g : additional_layer_gates)
517 all_gates.push_back(g);
519 std::unique_ptr<StructuralCandidate> additional_gate_candidate = std::make_unique<StructuralCandidate>(base_candidate, all_gates);
520 inv_candidates_to_add.push_back(std::move(additional_gate_candidate));
523 for (
auto& candidate_to_add : inv_candidates_to_add)
525 candidates.push_back(std::move(candidate_to_add));
531 std::vector<std::unique_ptr<StructuralCandidate>> new_candidates;
532 for (
const auto& c : candidates)
534 for (
const auto& in_net : carry_chain.front()->get_fan_in_nets())
536 if (in_net->is_gnd_net() || in_net->is_vcc_net())
541 for (
const auto& dst : in_net->get_destinations())
543 if (dst->get_gate() == carry_chain.front())
548 if (dst->get_gate() ==
nullptr)
554 bool is_single_input_lut = dst->get_gate()->get_type()->has_property(
GateTypeProperty::c_lut) && (dst->get_gate()->get_boolean_functions().size() == 1)
555 && (dst->get_gate()->get_boolean_functions().begin()->second.get_variable_names().size() == 1);
557 if (!is_inverter && !is_single_input_lut)
562 std::unique_ptr<StructuralCandidate> new_candidate = std::make_unique<StructuralCandidate>(base_candidate, c->m_gates);
563 new_candidate->m_gates.emplace_back(dst->get_gate());
564 new_candidates.emplace_back(std::move(new_candidate));
568 for (
auto& nc : new_candidates)
570 candidates.push_back(std::move(nc));
595 std::vector<std::unique_ptr<StructuralCandidate>> new_candidates;
596 for (
const auto& c : candidates)
598 std::set<Gate*> additional_gates;
602 for (
const auto& input : all_inputs)
604 for (
const auto& dest :
input->get_destinations())
606 if (dest->get_gate() ==
nullptr)
611 if (c_gates.find(dest->get_gate()) != c_gates.end())
616 if (additional_gates.find(dest->get_gate()) != additional_gates.end())
621 const auto gate_inputs = dest->get_gate()->get_fan_in_nets();
624 for (
auto& gi : gate_inputs)
626 if (all_inputs.find(gi) == all_inputs.end())
635 additional_gates.insert(dest->get_gate());
647 auto total_gates = c->m_gates;
648 total_gates.insert(total_gates.end(), additional_gates.begin(), additional_gates.end());
649 new_candidates.push_back(std::make_unique<StructuralCandidate>(base_candidate, total_gates));
651 for (
auto& nc : new_candidates)
653 candidates.push_back(std::move(nc));
657 std::set<std::set<Gate*>> all_sets;
658 u32 old_size = candidates.size();
659 std::vector<std::unique_ptr<StructuralCandidate>> candidates_to_return;
661 for (
auto& cand : candidates)
663 std::set<Gate*> set_gates = {cand->m_gates.begin(), cand->m_gates.end()};
664 if (all_sets.find(set_gates) == all_sets.end())
666 all_sets.insert(set_gates);
667 candidates_to_return.push_back(std::move(cand));
671 return candidates_to_return;
677 std::vector<std::pair<std::unique_ptr<BaseCandidate>, std::vector<std::unique_ptr<StructuralCandidate>>>> base_to_structural_candidates;
679 auto base_candidates = find_carry_chains(nl);
681 log_info(
"module_identification",
"found {} carry chains, building structural variants now...", base_candidates.size());
683 for (
auto& base_candidate : base_candidates)
685 std::vector<std::unique_ptr<StructuralCandidate>> structural_candidates = build_structural_candidates(base_candidate.get());
686 base_to_structural_candidates.push_back({std::move(base_candidate), std::move(structural_candidates)});
689 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_debug(channel,...)
#define log_info(channel,...)
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.
std::vector< Net * > get_input_nets(const std::vector< Gate * > &gates)
Get input nets from a list of gates.
@ xilinx_unisim
Xilinx Unisim FPGA architecture.
Result< std::vector< Gate * > > get_gate_chain(Gate *start_gate, const std::vector< const GatePin * > &input_pins={}, const std::vector< const GatePin * > &output_pins={}, const std::function< bool(const Gate *)> &filter=nullptr)
std::vector< Gate * > get_next_gates(const Gate *gate, bool get_successors, int depth=0, const std::function< bool(const Gate *)> &filter=nullptr)
std::set< T > to_set(const Container< T, Args... > &container)
bool is_subset(const T1 &subset, const T2 &superset)
std::vector< T > to_vector(const Container< T, Args... > &container)
This file contains helper functions for module identification in the HAL framework.
This file contains the class for defining and managing structural candidates within the module identi...
This file contains the function to generate structural candidates for Xilinx Unisim libraries.