HAL  v4.5.0-83-g30c8f0afc
The Hardware Analyzer - a comprehensive reverse engineering and manipulation framework for gate-level netlists.
xilinx_unisim.cpp
Go to the documentation of this file.
2 
3 #include "hal_core/defines.h"
12 
13 #include <vector>
14 
15 namespace hal
16 {
17  namespace module_identification
18  {
19  namespace xilinx_unisim
20  {
21  namespace
22  {
33  std::vector<std::unique_ptr<BaseCandidate>> find_carry_chains(const Netlist* nl)
34  {
35  std::vector<std::vector<Gate*>> carry_chains;
36 
37  // retrieve all carry gates
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());
40 
41  // collect carry chains until all carry gates have been analyzed
42  while (!carry_gates_set.empty())
43  {
44  Gate* current_gate = *carry_gates_set.begin();
45  const GateType* carry_type = current_gate->get_type();
46 
47  // get carry chains by defining appropriate filter function
48  auto chain_res = netlist_utils::get_gate_chain(current_gate, {carry_type->get_pin_by_name("CI")}, {carry_type->get_pin_by_name("CO(3)")});
49  if (chain_res.is_error())
50  {
51  return std::vector<std::unique_ptr<BaseCandidate>>();
52  }
53  std::vector<Gate*> carry_chain = chain_res.get();
54 
55  // remove shift register gates from candidate set
56  for (Gate* g : carry_chain)
57  {
58  carry_gates_set.erase(g);
59  }
60 
61  // only consider carry chains with more than 2 gates for now
62  if (carry_chain.size() >= 2)
63  {
64  log_debug("module_identification", "\tcarry_gate: {}", carry_chain.front()->get_name());
65  carry_chains.push_back(carry_chain);
66  }
67  }
68 
69  // check whether a carry chain is a subset of another one
70  std::vector<std::vector<Gate*>> filtered_carry_chains;
71  for (u32 i = 0; i < carry_chains.size(); i++)
72  {
73  auto& c_test = carry_chains.at(i);
74  std::set<Gate*> test_set = {c_test.begin(), c_test.end()};
75 
76  bool is_subset = false;
77  for (u32 j = 0; j < carry_chains.size(); j++)
78  {
79  if (i == j)
80  {
81  continue;
82  }
83 
84  auto& c_other = carry_chains.at(j);
85  std::set<Gate*> other_set = {c_other.begin(), c_other.end()};
86 
87  if (std::includes(other_set.begin(), other_set.end(), test_set.begin(), test_set.end()))
88  {
89  is_subset = true;
90  break;
91  }
92  }
93 
94  if (!is_subset)
95  {
96  filtered_carry_chains.push_back(c_test);
97  }
98  }
99 
100  std::vector<std::unique_ptr<BaseCandidate>> base_candidates;
101  for (const auto& carry_chain : filtered_carry_chains)
102  {
103  std::unique_ptr<BaseCandidate> base_candidate = std::make_unique<BaseCandidate>(carry_chain);
104  base_candidates.push_back(std::move(base_candidate));
105  }
106 
107  return base_candidates;
108  }
109 
120  std::vector<std::unique_ptr<StructuralCandidate>> build_structural_candidates(BaseCandidate* base_candidate)
121  {
122  std::vector<std::unique_ptr<StructuralCandidate>> candidates;
123 
124  std::vector<Gate*> carry_chain = base_candidate->m_gates;
125 
126  Gate* first_carry = carry_chain.front();
127 
128  // check if first gate is carry
129  if (!first_carry->get_type()->has_property(GateTypeProperty::c_carry))
130  {
131  return std::vector<std::unique_ptr<StructuralCandidate>>();
132  }
133  log_debug("module_identification", "\tcarry_chain: {}", first_carry->get_name());
134 
135  // generate very big candidates and go back until sequential gate or IO
136  {
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;
139 
140  for (const auto& gate : carry_chain)
141  {
142  // TODO make this use the NetlistTraversal decorator
143  auto gates = netlist_utils::get_next_gates(gate, false, 0, [](const Gate* g) {
144  bool add_gate = true;
145  if (g->get_type()->has_property(hal::GateTypeProperty::io))
146  {
147  add_gate = false;
148  }
149  // if (g->get_type()->has_property(hal::GateTypeProperty::c_carry))
150  // {
151  // add_gate = false;
152  // }
153  if (g->get_type()->has_property(hal::GateTypeProperty::dsp))
154  {
155  add_gate = false;
156  }
157  if (g->get_type()->has_property(hal::GateTypeProperty::power))
158  {
159  add_gate = false;
160  }
161  if (g->get_type()->has_property(hal::GateTypeProperty::ground))
162  {
163  add_gate = false;
164  }
165  if (!g->get_type()->has_property(hal::GateTypeProperty::combinational))
166  {
167  add_gate = false;
168  }
169  return add_gate;
170  });
171 
172  for (const auto& gate_to_add : gates)
173  {
174  big_candidate_gates.insert(gate_to_add);
175  }
176  }
177 
178  if (big_candidate_gates.size() < (carry_chain.size() * 128))
179  {
180  // create candidate with many many gates
181  auto gate_vec = utils::to_vector(big_candidate_gates);
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));
185  }
186  else
187  {
188  log_debug("module_identification", "big_candidate is too big with {} gates", big_candidate_gates.size());
189  }
190  }
191 
192  // create candidate with only carry chain, nothing else
193  std::vector<Gate*> candidate_gates(carry_chain);
194 
195  std::unique_ptr<StructuralCandidate> first_candidate = std::make_unique<StructuralCandidate>(base_candidate, candidate_gates);
196  if (first_candidate == nullptr)
197  {
198  log_error("module_identification", "nullptr candidate after creation");
199  }
200  candidates.push_back(std::move(first_candidate));
201 
202  // get gates infront of CARRY
203  for (const auto& gate : carry_chain)
204  {
205  for (const auto& pred_endp : gate->get_predecessors())
206  {
207  auto pred_gate = pred_endp->get_gate();
208 
209  if (pred_gate->is_gnd_gate() || pred_gate->is_vcc_gate())
210  {
211  continue;
212  }
213 
214  if (pred_gate->get_type()->has_property(hal::GateTypeProperty::io))
215  {
216  continue;
217  }
218 
219  if (pred_gate->get_type()->has_property(hal::GateTypeProperty::c_carry))
220  {
221  continue;
222  }
223 
224  if (pred_gate->get_type()->has_property(hal::GateTypeProperty::sequential))
225  {
226  continue;
227  }
228 
229  if (pred_gate->get_type()->has_property(hal::GateTypeProperty::combinational))
230  {
231  candidate_gates.push_back(pred_gate);
232  }
233  }
234  }
235 
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)
238  {
239  log_error("module_identification", "nullptr candidate after creation");
240  }
241  candidates.push_back(std::move(candidate_all_gates_infront_level_1));
242 
243  // get gates infront of SI and DI of CARRY
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)"};
246 
247  for (const auto& gate : carry_chain)
248  {
249  for (const auto& pin : allowed_pins_si_di0)
250  {
251  const auto& pred_endp = gate->get_predecessor(pin);
252  if (pred_endp == nullptr)
253  {
254  continue;
255  }
256  auto pred_gate = pred_endp->get_gate();
257  if (pred_gate->is_gnd_gate() || pred_gate->is_vcc_gate())
258  {
259  continue;
260  }
261 
262  if (pred_gate->get_type()->has_property(hal::GateTypeProperty::io))
263  {
264  log_error("module_identification", "\tfound IO gate, but why?");
265  continue;
266  }
267 
268  if (pred_gate->get_type()->has_property(hal::GateTypeProperty::c_carry))
269  {
270  continue;
271  }
272  if (pred_gate->get_type()->has_property(hal::GateTypeProperty::sequential))
273  {
274  continue;
275  }
276 
277  if (pred_gate->get_type()->has_property(hal::GateTypeProperty::combinational))
278  {
279  // log_debug("module_identification", "\t\tadding {}", pred_gate->get_name());
280  si_di0_candidate_gates.push_back(pred_gate);
281  }
282  }
283  }
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)
286  {
287  log_error("module_identification", "nullptr candidate after creation");
288  }
289  candidates.push_back(std::move(candidate_gates_infront_of_si_di0));
290 
291  // get gates infront of SI and DI of CARRY
292  // log_debug("module_identification", "\tsi_di pred:");
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)"};
295 
296  for (const auto& gate : carry_chain)
297  {
298  for (const auto& pin : allowed_pins_si_di)
299  {
300  const auto& pred_endp = gate->get_predecessor(pin);
301  if (pred_endp == nullptr)
302  {
303  continue;
304  }
305  auto pred_gate = pred_endp->get_gate();
306  if (pred_gate->is_gnd_gate() || pred_gate->is_vcc_gate())
307  {
308  continue;
309  }
310 
311  if (pred_gate->get_type()->has_property(hal::GateTypeProperty::io))
312  {
313  log_error("module_identification", "\tfound IO gate, but why?");
314  continue;
315  }
316 
317  if (pred_gate->get_type()->has_property(hal::GateTypeProperty::c_carry))
318  {
319  continue;
320  }
321  if (pred_gate->get_type()->has_property(hal::GateTypeProperty::sequential))
322  {
323  continue;
324  }
325 
326  if (pred_gate->get_type()->has_property(hal::GateTypeProperty::combinational))
327  {
328  si_di_candidate_gates.push_back(pred_gate);
329  }
330  }
331  }
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)
334  {
335  log_error("module_identification", "nullptr candidate after creation");
336  }
337  candidates.push_back(std::move(candidate_gates_infront_of_si_di));
338 
339  // get gates infront of SI of CARRY
340  std::vector<Gate*> si_candidate_gates(carry_chain);
341 
342  std::vector<std::string> allowed_pins_si = {"S(0)", "S(1)", "S(2)", "S(3)"};
343  for (const auto& gate : carry_chain)
344  {
345  for (const auto& pin : allowed_pins_si)
346  {
347  const auto& pred_endp = gate->get_predecessor(pin);
348  if (pred_endp == nullptr)
349  {
350  continue;
351  }
352  auto pred_gate = pred_endp->get_gate();
353  if (pred_gate->is_gnd_gate() || pred_gate->is_vcc_gate())
354  {
355  continue;
356  }
357 
358  if (pred_gate->get_type()->has_property(hal::GateTypeProperty::io))
359  {
360  log_error("module_identification", "\tfound IO gate, but why?");
361  continue;
362  }
363 
364  if (pred_gate->get_type()->has_property(hal::GateTypeProperty::c_carry))
365  {
366  continue;
367  }
368  if (pred_gate->get_type()->has_property(hal::GateTypeProperty::sequential))
369  {
370  continue;
371  }
372 
373  if (pred_gate->get_type()->has_property(hal::GateTypeProperty::combinational))
374  {
375  // log_debug("module_identification", "\t\tadding {}", pred_gate->get_name());
376  si_candidate_gates.push_back(pred_gate);
377  }
378  }
379  }
380 
381  std::vector<Gate*> candidate_gates_infront_of_si_gates;
382  for (const auto& g : si_candidate_gates)
383  {
384  candidate_gates_infront_of_si_gates.push_back(g);
385  }
386  std::unique_ptr<StructuralCandidate> candidate_gates_infront_of_si = std::make_unique<StructuralCandidate>(base_candidate, candidate_gates_infront_of_si_gates);
387 
388  candidates.push_back(std::move(candidate_gates_infront_of_si));
389 
390  std::vector<std::unique_ptr<StructuralCandidate>> candidates_to_add;
391 
392  // get additional layer
393  for (const auto& cand : candidates)
394  {
395  if (cand == nullptr)
396  {
397  log_error("module_identification", "nullptr candidate");
398  continue;
399  }
400 
401  if (cand->m_gates.empty())
402  {
403  log_error("module_identification", "candidate has no gates");
404  continue;
405  }
406  std::set<Gate*> additional_layer_gates;
407 
408  for (const auto& gate : cand->m_gates)
409  {
410  if (gate->get_type()->has_property(hal::GateTypeProperty::c_carry))
411  {
412  continue;
413  }
414 
415  for (const auto& pred_endp : gate->get_predecessors())
416  {
417  if (pred_endp == nullptr)
418  {
419  continue;
420  }
421 
422  auto pred_gate = pred_endp->get_gate();
423 
424  if (pred_gate == nullptr)
425  {
426  continue;
427  }
428 
429  if (pred_gate->is_gnd_gate() || pred_gate->is_vcc_gate())
430  {
431  continue;
432  }
433 
434  if (pred_gate->get_type()->has_property(hal::GateTypeProperty::io))
435  {
436  continue;
437  }
438 
439  if (pred_gate->get_type()->has_property(hal::GateTypeProperty::c_carry))
440  {
441  continue;
442  }
443 
444  if (pred_gate->get_type()->has_property(hal::GateTypeProperty::sequential))
445  {
446  continue;
447  }
448 
449  if (pred_gate->get_type()->has_property(hal::GateTypeProperty::combinational))
450  {
451  additional_layer_gates.insert(pred_gate);
452  }
453  }
454  }
455  std::vector<Gate*> all_gates(cand->m_gates);
456  for (const auto& g : additional_layer_gates)
457  {
458  all_gates.push_back(g);
459  }
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));
462  }
463 
464  for (auto& candidate_to_add : candidates_to_add)
465  {
466  candidates.push_back(std::move(candidate_to_add));
467  }
468 
469  std::vector<std::unique_ptr<StructuralCandidate>> inv_candidates_to_add;
470 
471  // get only inverters in front of candidate
472  for (const auto& cand : candidates)
473  {
474  if (cand == nullptr)
475  {
476  log_error("module_identification", "nullptr candidate");
477  continue;
478  }
479 
480  if (cand->m_gates.empty())
481  {
482  log_error("module_identification", "candidate has no gates");
483  continue;
484  }
485  std::set<Gate*> additional_layer_gates;
486 
487  for (const auto& gate : cand->m_gates)
488  {
489  if (gate->get_type()->has_property(hal::GateTypeProperty::c_carry))
490  {
491  continue;
492  }
493 
494  for (const auto& pred_endp : gate->get_predecessors())
495  {
496  if (pred_endp == nullptr)
497  {
498  continue;
499  }
500 
501  auto pred_gate = pred_endp->get_gate();
502 
503  if (pred_gate == nullptr)
504  {
505  continue;
506  }
507 
508  if (pred_gate->get_type()->has_property(hal::GateTypeProperty::c_inverter))
509  {
510  additional_layer_gates.insert(pred_gate);
511  }
512  }
513  }
514  std::vector<Gate*> all_gates(cand->m_gates);
515  for (const auto& g : additional_layer_gates)
516  {
517  all_gates.push_back(g);
518  }
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));
521  }
522 
523  for (auto& candidate_to_add : inv_candidates_to_add)
524  {
525  candidates.push_back(std::move(candidate_to_add));
526  }
527 
528  // NOTE: i noticed that there are counter candidates that are not built correctly
529  // for each input net of the first carry gate and for each of its successors gates add a new candidate that includes this gate
530  {
531  std::vector<std::unique_ptr<StructuralCandidate>> new_candidates;
532  for (const auto& c : candidates)
533  {
534  for (const auto& in_net : carry_chain.front()->get_fan_in_nets())
535  {
536  if (in_net->is_gnd_net() || in_net->is_vcc_net())
537  {
538  continue;
539  }
540 
541  for (const auto& dst : in_net->get_destinations())
542  {
543  if (dst->get_gate() == carry_chain.front())
544  {
545  continue;
546  }
547 
548  if (dst->get_gate() == nullptr)
549  {
550  continue;
551  }
552 
553  bool is_inverter = dst->get_gate()->get_type()->has_property(GateTypeProperty::c_inverter);
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);
556  // place some constraints on the added gate
557  if (!is_inverter && !is_single_input_lut)
558  {
559  continue;
560  }
561 
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));
565  }
566  }
567  }
568  for (auto& nc : new_candidates)
569  {
570  candidates.push_back(std::move(nc));
571  }
572  }
573 
574  // TODO only required for debugging
575  // std::vector<std::unique_ptr<StructuralCandidate>> filtered_candidates;
576  // for (auto& c : candidates)
577  // {
578  // std::set<u32> id_set;
579  // for (const auto& g : c->m_gates)
580  // {
581  // id_set.insert(g->get_id());
582  // }
583 
584  // std::set<u32> filter_set = {};
585  // if (id_set == filter_set)
586  // {
587  // std::cout << "Found filter candidate!" << std::endl;
588  // filtered_candidates.push_back(std::move(c));
589  // break;
590  // }
591  // }
592  // candidates = std::move(filtered_candidates);
593 
594  // iterate over all candidates and add additional candidate variants that include all gates that are only connected to inputs that are already leading to the candidate
595  std::vector<std::unique_ptr<StructuralCandidate>> new_candidates;
596  for (const auto& c : candidates)
597  {
598  std::set<Gate*> additional_gates;
599 
600  const auto c_gates = utils::to_set(c->m_gates);
601  const auto all_inputs = utils::to_set(get_input_nets(c->m_gates));
602  for (const auto& input : all_inputs)
603  {
604  for (const auto& dest : input->get_destinations())
605  {
606  if (dest->get_gate() == nullptr)
607  {
608  continue;
609  }
610 
611  if (c_gates.find(dest->get_gate()) != c_gates.end())
612  {
613  continue;
614  }
615 
616  if (additional_gates.find(dest->get_gate()) != additional_gates.end())
617  {
618  continue;
619  }
620 
621  const auto gate_inputs = dest->get_gate()->get_fan_in_nets();
622 
623  bool is_subset = true;
624  for (auto& gi : gate_inputs)
625  {
626  if (all_inputs.find(gi) == all_inputs.end())
627  {
628  is_subset = false;
629  break;
630  }
631  }
632 
633  if (is_subset)
634  {
635  additional_gates.insert(dest->get_gate());
636  }
637  }
638  }
639 
640  // TODO remove debug print
641  // std::cout << "considering additional gates: " << std::endl;
642  // for (const auto& g : additional_gates)
643  // {
644  // std::cout << g->get_id() << " / " << g->get_name() << std::endl;
645  // }
646 
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));
650  }
651  for (auto& nc : new_candidates)
652  {
653  candidates.push_back(std::move(nc));
654  }
655 
656  // remove same candidates
657  std::set<std::set<Gate*>> all_sets;
658  u32 old_size = candidates.size();
659  std::vector<std::unique_ptr<StructuralCandidate>> candidates_to_return;
660 
661  for (auto& cand : candidates)
662  {
663  std::set<Gate*> set_gates = {cand->m_gates.begin(), cand->m_gates.end()};
664  if (all_sets.find(set_gates) == all_sets.end())
665  {
666  all_sets.insert(set_gates);
667  candidates_to_return.push_back(std::move(cand));
668  }
669  }
670 
671  return candidates_to_return;
672  }
673  } // namespace
674 
675  std::vector<std::pair<std::unique_ptr<BaseCandidate>, std::vector<std::unique_ptr<StructuralCandidate>>>> generate_structural_candidates(const Netlist* nl)
676  {
677  std::vector<std::pair<std::unique_ptr<BaseCandidate>, std::vector<std::unique_ptr<StructuralCandidate>>>> base_to_structural_candidates;
678 
679  auto base_candidates = find_carry_chains(nl);
680 
681  log_info("module_identification", "found {} carry chains, building structural variants now...", base_candidates.size());
682 
683  for (auto& base_candidate : base_candidates)
684  {
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)});
687  }
688 
689  return base_to_structural_candidates;
690  }
691  } // namespace xilinx_unisim
692  } // namespace module_identification
693 } // namespace hal
This file contains the definition of the BaseCandidate class, which represents a base candidate in th...
uint32_t u32
Definition: defines.h:41
#define log_error(channel,...)
Definition: log.h:78
#define log_debug(channel,...)
Definition: log.h:74
#define log_info(channel,...)
Definition: log.h:70
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.
Definition: utils.cpp:25
@ 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)
Definition: utils.h:527
bool is_subset(const T1 &subset, const T2 &superset)
Definition: utils.h:541
std::vector< T > to_vector(const Container< T, Args... > &container)
Definition: utils.h:515
Definition: defines.h:45
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.