HAL  v4.5.0-83-g30c8f0afc
The Hardware Analyzer - a comprehensive reverse engineering and manipulation framework for gate-level netlists.
netlist_preprocessing.cpp
Go to the documentation of this file.
1 #include "netlist_preprocessing/netlist_preprocessing.h"
2 
3 #include "hal_core/netlist/boolean_function/solver.h"
4 #include "hal_core/netlist/decorators/boolean_function_decorator.h"
5 #include "hal_core/netlist/decorators/boolean_function_net_decorator.h"
6 #include "hal_core/netlist/decorators/netlist_modification_decorator.h"
7 #include "hal_core/netlist/decorators/subgraph_netlist_decorator.h"
8 #include "hal_core/netlist/gate.h"
9 #include "hal_core/netlist/gate_library/gate_library_manager.h"
10 #include "hal_core/netlist/module.h"
11 #include "hal_core/netlist/net.h"
12 #include "hal_core/netlist/netlist.h"
13 #include "hal_core/utilities/token_stream.h"
14 #include "nlohmann/json.hpp"
15 #include "rapidjson/document.h"
16 #include "resynthesis/resynthesis.h"
17 #include "z3_utils/netlist_comparison.h"
18 
19 #include <fstream>
20 #include <queue>
21 #include <regex>
22 
23 namespace hal
24 {
25  namespace netlist_preprocessing
26  {
27  Result<u32> remove_unused_lut_inputs(Netlist* nl)
28  {
29  u32 num_eps = 0;
30 
31  // get net connected to GND
32  const std::vector<Gate*>& gnd_gates = nl->get_gnd_gates();
33  if (gnd_gates.empty())
34  {
35  return ERR("could not remove unused LUT endpoints from netlist with ID " + std::to_string(nl->get_id()) + ": no GND net available within netlist");
36  }
37  Net* gnd_net = gnd_gates.front()->get_fan_out_nets().front();
38 
39  // iterate all LUT gates
40  for (const auto& gate : nl->get_gates([](const Gate* g) { return g->get_type()->has_property(GateTypeProperty::c_lut); }))
41  {
42  std::vector<Endpoint*> fan_in = gate->get_fan_in_endpoints();
43  std::unordered_map<std::string, BooleanFunction> functions = gate->get_boolean_functions();
44 
45  // skip if more than one function
46  if (functions.size() != 1)
47  {
48  continue;
49  }
50 
51  // only pins used as variables in Boolean function are considered active
52  auto active_pins = functions.begin()->second.get_variable_names();
53 
54  // if there are more fan-in nets than there are active pins, remove those that are not used within the Boolean function and reconnect to GND
55  if (fan_in.size() > active_pins.size())
56  {
57  for (const auto& ep : fan_in)
58  {
59  if (ep->get_net()->is_gnd_net() || ep->get_net()->is_vcc_net())
60  {
61  continue;
62  }
63 
64  if (std::find(active_pins.begin(), active_pins.end(), ep->get_pin()->get_name()) == active_pins.end())
65  {
66  GatePin* pin = ep->get_pin();
67  if (!ep->get_net()->remove_destination(gate, pin))
68  {
69  log_warning(
70  "netlist_preprocessing", "failed to remove unused input from LUT gate '{}' with ID {} from netlist with ID {}.", gate->get_name(), gate->get_id(), nl->get_id());
71  continue;
72  }
73  if (!gnd_net->add_destination(gate, pin))
74  {
75  log_warning("netlist_preprocessing",
76  "failed to reconnect unused input of LUT gate '{}' with ID {} to GND in netlist with ID {}.",
77  gate->get_name(),
78  gate->get_id(),
79  nl->get_id());
80  continue;
81  }
82  num_eps++;
83  }
84  }
85  }
86  }
87 
88  log_info("netlist_preprocessing", "removed {} unused LUT endpoints from netlist with ID {}.", num_eps, nl->get_id());
89  return OK(num_eps);
90  }
91 
92  // TODO make this check every pin of a gate and check whether the generated boolean function (with replaced gnd and vcc nets) is just a variable.
93  // Afterwards just connect input net to buffer destination. Do this for all pins and delete gate if it has no more successors and not global outputs
94  Result<u32> remove_buffers(Netlist* nl)
95  {
96  u32 num_gates = 0;
97 
98  std::queue<Gate*> gates_to_be_deleted;
99 
100  for (const auto& gate : nl->get_gates())
101  {
102  std::vector<Endpoint*> fan_out = gate->get_fan_out_endpoints();
103 
104  GateType* gt = gate->get_type();
105 
106  // continue if of invalid base type
107  if (!gt->has_property(GateTypeProperty::combinational) || gt->has_property(GateTypeProperty::power) || gt->has_property(GateTypeProperty::ground))
108  {
109  continue;
110  }
111 
112  // continue if more than one fan-out net
113  if (fan_out.size() != 1)
114  {
115  continue;
116  }
117 
118  // continue if more than one Boolean function
119  std::unordered_map<std::string, BooleanFunction> functions = gate->get_boolean_functions();
120  if (functions.size() != 1)
121  {
122  continue;
123  }
124 
125  // continue if Boolean function name does not match output pin
126  Endpoint* out_endpoint = *(fan_out.begin());
127  if (out_endpoint->get_pin()->get_name() != (functions.begin())->first)
128  {
129  continue;
130  }
131 
132  std::vector<Endpoint*> fan_in = gate->get_fan_in_endpoints();
133  BooleanFunction func = functions.begin()->second;
134 
135  // simplify Boolean function for constant 0 or 1 inputs (takes care of, e.g., an AND2 connected to an input and logic 1)
136  const auto substitute_res = BooleanFunctionDecorator(func).substitute_power_ground_pins(gate);
137  if (substitute_res.is_error())
138  {
139  return ERR_APPEND(substitute_res.get_error(),
140  "Cannot replace buffers: failed to substitute pins with constants at gate " + gate->get_name() + " with ID " + std::to_string(gate->get_id()));
141  }
142 
143  func = substitute_res.get().simplify_local();
144 
145  bool failed = false;
146  std::vector<std::string> in_pins = gt->get_input_pin_names();
147  if (func.is_variable() && std::find(in_pins.begin(), in_pins.end(), func.get_variable_name().get()) != in_pins.end())
148  {
149  Net* out_net = out_endpoint->get_net();
150 
151  // check all input endpoints and ...
152  for (Endpoint* in_endpoint : fan_in)
153  {
154  Net* in_net = in_endpoint->get_net();
155  if (in_endpoint->get_pin()->get_name() == func.get_variable_name().get())
156  {
157  // const auto merge_res = netlist_utils::merge_nets(nl, in_net, out_net, true);
158  const auto merge_res = NetlistModificationDecorator(*nl).connect_nets(out_net, in_net);
159  if (merge_res.is_error())
160  {
161  log_warning("netlist_preprocessing", "{}", merge_res.get_error().get());
162  failed = true;
163  }
164  }
165  else
166  {
167  // completely remove the input endpoint otherwise
168  if (!in_net->remove_destination(in_endpoint))
169  {
170  log_warning("netlist_preprocessing",
171  "failed to remove destination from input net '{}' with ID {} of buffer gate '{}' with ID {} from netlist with ID {}.",
172  in_net->get_name(),
173  in_net->get_id(),
174  gate->get_name(),
175  gate->get_id(),
176  nl->get_id());
177  failed = true;
178  }
179  }
180 
181  if (failed)
182  {
183  break;
184  }
185  }
186 
187  if (!failed)
188  {
189  gates_to_be_deleted.push(gate);
190  }
191  }
192  // TODO this functionality is not a buffer and is covered by propagate_constants
193  /*
194  else if (func.is_constant() && (func.has_constant_value(0) || func.has_constant_value(1)))
195  {
196  auto* out_net = out_endpoint->get_net();
197 
198  const auto& gnd_gates = nl->get_gnd_gates();
199  const auto& vcc_gates = nl->get_vcc_gates();
200  if (gnd_gates.empty() || vcc_gates.empty())
201  {
202  continue;
203  }
204  auto* gnd_net = gnd_gates.front()->get_fan_out_nets().front();
205  auto* vcc_net = vcc_gates.front()->get_fan_out_nets().front();
206 
207  for (auto* in_endpoint : fan_in)
208  {
209  auto* in_net = in_endpoint->get_net();
210 
211  // remove the input endpoint otherwise
212  if (!in_net->remove_destination(gate, in_endpoint->get_pin()))
213  {
214  log_warning("netlist_preprocessing",
215  "failed to remove destination from input net '{}' with ID {} of buffer gate '{}' with ID {} from netlist with ID {}.",
216  in_net->get_name(),
217  in_net->get_id(),
218  gate->get_name(),
219  gate->get_id(),
220  nl->get_id());
221  failed = true;
222  break;
223  }
224  }
225  if (!failed && func.has_constant_value(0))
226  {
227  for (auto* dst : out_net->get_destinations())
228  {
229  auto* dst_gate = dst->get_gate();
230  auto* dst_pin = dst->get_pin();
231  if (!out_net->remove_destination(dst))
232  {
233  log_warning("netlist_preprocessing",
234  "failed to remove destination from output net '{}' with ID {} of buffer gate '{}' with ID {} from netlist with ID {}.",
235  out_net->get_name(),
236  out_net->get_id(),
237  gate->get_name(),
238  gate->get_id(),
239  nl->get_id());
240  failed = true;
241  break;
242  }
243  if (!gnd_net->add_destination(dst_gate, dst_pin))
244  {
245  log_warning("netlist_preprocessing",
246  "failed to add buffer gate '{}' with ID {} as destination to GND net '{}' with ID {} in netlist with ID {}.",
247  gnd_net->get_name(),
248  gnd_net->get_id(),
249  gate->get_name(),
250  gate->get_id(),
251  nl->get_id());
252  failed = true;
253  break;
254  }
255  }
256  }
257  else if (!failed && func.has_constant_value(1))
258  {
259  for (Endpoint* dst : out_net->get_destinations())
260  {
261  Gate* dst_gate = dst->get_gate();
262  GatePin* dst_pin = dst->get_pin();
263  if (!out_net->remove_destination(dst))
264  {
265  log_warning("netlist_preprocessing",
266  "failed to remove destination from output net '{}' with ID {} of buffer gate '{}' with ID {} from netlist with ID {}.",
267  out_net->get_name(),
268  out_net->get_id(),
269  gate->get_name(),
270  gate->get_id(),
271  nl->get_id());
272  failed = true;
273  break;
274  }
275  if (!vcc_net->add_destination(dst_gate, dst_pin))
276  {
277  log_warning("netlist_preprocessing",
278  "failed to add buffer gate '{}' with ID {} as destination to VCC net '{}' with ID {} in netlist with ID {}.",
279  vcc_net->get_name(),
280  vcc_net->get_id(),
281  gate->get_name(),
282  gate->get_id(),
283  nl->get_id());
284  failed = true;
285  break;
286  }
287  }
288  }
289 
290  // delete output net and buffer gate
291  if (!failed && !nl->delete_net(out_net))
292  {
293  log_warning("netlist_preprocessing",
294  "failed to remove output net '{}' with ID {} of buffer gate '{}' with ID {} from netlist with ID {}.",
295  out_net->get_name(),
296  out_net->get_id(),
297  gate->get_name(),
298  gate->get_id(),
299  nl->get_id());
300  continue;
301  }
302  if (!failed)
303  {
304  gates_to_be_deleted.push(gate);
305  }
306  }
307  */
308  }
309 
310  log_debug("netlist_preprocessing", "removing {} buffer gates...", gates_to_be_deleted.size());
311 
312  while (!gates_to_be_deleted.empty())
313  {
314  Gate* gate = gates_to_be_deleted.front();
315  gates_to_be_deleted.pop();
316  if (!nl->delete_gate(gate))
317  {
318  log_warning("netlist_preprocessing", "failed to remove buffer gate '{}' with ID {} from netlist with ID {}.", gate->get_name(), gate->get_id(), nl->get_id());
319  continue;
320  }
321  num_gates++;
322  }
323 
324  log_info("netlist_preprocessing", "removed {} buffer gates from netlist with ID {}.", num_gates, nl->get_id());
325  return OK(num_gates);
326  }
327 
328  namespace
329  {
330  std::unordered_map<Gate*, std::vector<std::string>> restore_ff_replacements(const Netlist* nl)
331  {
332  std::unordered_map<Gate*, std::vector<std::string>> replacements;
333 
334  for (auto& g : nl->get_gates())
335  {
336  if (g->has_data("preprocessing_information", "replaced_gates"))
337  {
338  const auto& [_, s] = g->get_data("preprocessing_information", "replaced_gates");
339  std::vector<std::string> replaced_gate_names = nlohmann::json::parse(s);
340  replacements.insert({g, replaced_gate_names});
341  }
342  }
343 
344  return replacements;
345  }
346 
347  void update_ff_replacements(std::unordered_map<Gate*, std::vector<std::string>>& replacements)
348  {
349  for (auto& [g, r] : replacements)
350  {
351  const nlohmann::json j = r;
352  const std::string s = j.dump();
353 
354  g->set_data("preprocessing_information", "replaced_gates", "string", s);
355  }
356 
357  return;
358  }
359 
360  void annotate_ff_survivor(std::unordered_map<Gate*, std::vector<std::string>>& replacements, Gate* survivor, Gate* to_be_replaced)
361  {
362  auto& it_s = replacements[survivor];
363 
364  if (const auto& it = replacements.find(to_be_replaced); it != replacements.end())
365  {
366  for (const auto& s : it->second)
367  {
368  it_s.push_back(s);
369  }
370  replacements.erase(it);
371  }
372 
373  it_s.push_back(to_be_replaced->get_name());
374 
375  return;
376  }
377  } // namespace
378 
379  Result<u32> remove_redundant_gates(Netlist* nl, const std::function<bool(const Gate*)>& filter)
380  {
381  auto config = hal::SMT::QueryConfig();
382 
383 #ifdef BITWUZLA_LIBRARY
384  auto s_type = hal::SMT::SolverType::Bitwuzla;
385  auto s_call = hal::SMT::SolverCall::Library;
386  config = config.with_solver(s_type).with_call(s_call);
387 #endif
388  struct GateFingerprint
389  {
390  const GateType* type;
391  std::map<GatePin*, Net*> ordered_fan_in = {};
392  std::set<Net*> unordered_fan_in = {};
393  u8 truth_table_hw = 0;
394 
395  bool operator<(const GateFingerprint& other) const
396  {
397  return (other.type < type) || (other.type == type && other.ordered_fan_in < ordered_fan_in)
398  || (other.type == type && other.ordered_fan_in == ordered_fan_in && other.unordered_fan_in < unordered_fan_in)
399  || (other.type == type && other.ordered_fan_in == ordered_fan_in && other.unordered_fan_in == unordered_fan_in && other.truth_table_hw < truth_table_hw);
400  }
401  };
402 
403  static std::vector<u8> hw_map = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
404 
405  u32 num_gates = 0;
406  bool progress;
407 
408  std::vector<Gate*> target_gates;
409  if (filter)
410  {
411  target_gates = nl->get_gates([filter](const Gate* g) {
412  const auto& type = g->get_type();
413  return (type->has_property(GateTypeProperty::combinational) || type->has_property(GateTypeProperty::ff)) && filter(g);
414  });
415  }
416  else
417  {
418  target_gates = nl->get_gates([](const Gate* g) {
419  const auto& type = g->get_type();
420  return type->has_property(GateTypeProperty::combinational) || type->has_property(GateTypeProperty::ff);
421  });
422  }
423 
424  auto ff_replacements = restore_ff_replacements(nl);
425 
426  do
427  {
428  std::map<GateFingerprint, std::vector<Gate*>> fingerprinted_gates;
429 
430  progress = false;
431 
432  for (auto* gate : target_gates)
433  {
434  GateFingerprint fingerprint;
435  fingerprint.type = gate->get_type();
436  if (fingerprint.type->has_property(GateTypeProperty::combinational))
437  {
438  const auto& fan_in_nets = gate->get_fan_in_nets();
439  fingerprint.unordered_fan_in.insert(fan_in_nets.cbegin(), fan_in_nets.cend());
440  if (fingerprint.type->has_property(GateTypeProperty::c_lut))
441  {
442  if (const auto res = gate->get_init_data(); res.is_ok())
443  {
444  const auto& init_str = res.get().front();
445  for (const auto c : init_str)
446  {
447  u8 tmp = std::toupper(c) - 0x30;
448  if (tmp > 9)
449  {
450  tmp -= 0x7;
451  }
452  fingerprint.truth_table_hw += hw_map.at(tmp);
453  }
454  }
455  }
456  }
457  else if (fingerprint.type->has_property(GateTypeProperty::ff))
458  {
459  for (const auto& ep : gate->get_fan_in_endpoints())
460  {
461  fingerprint.ordered_fan_in[ep->get_pin()] = ep->get_net();
462  }
463  }
464 
465  fingerprinted_gates[fingerprint].push_back(gate);
466  }
467 
468  std::vector<std::vector<Gate*>> duplicate_gates;
469  for (const auto& [fingerprint, gates] : fingerprinted_gates)
470  {
471  if (gates.size() == 1)
472  {
473  continue;
474  }
475 
476  if (fingerprint.type->has_property(GateTypeProperty::combinational))
477  {
478  std::set<const Gate*> visited;
479  for (size_t i = 0; i < gates.size(); i++)
480  {
481  Gate* master_gate = gates.at(i);
482 
483  if (visited.find(master_gate) != visited.cend())
484  {
485  continue;
486  }
487 
488  std::vector<Gate*> current_duplicates = {master_gate};
489 
490  for (size_t j = i + 1; j < gates.size(); j++)
491  {
492  Gate* current_gate = gates.at(j);
493  bool equal = true;
494  for (const auto* pin : fingerprint.type->get_output_pins())
495  {
496  const auto solver_res =
497  master_gate->get_resolved_boolean_function(pin)
498  .map<BooleanFunction>([pin, current_gate](BooleanFunction&& bf_master) {
499  return current_gate->get_resolved_boolean_function(pin).map<BooleanFunction>([bf_master = std::move(bf_master)](BooleanFunction&& bf_current) mutable {
500  return BooleanFunction::Eq(std::move(bf_master), std::move(bf_current), 1);
501  });
502  })
503  .map<BooleanFunction>([](auto&& bf_eq) -> Result<BooleanFunction> { return BooleanFunction::Not(std::move(bf_eq), 1); })
504  .map<SMT::SolverResult>([&config](auto&& bf_not) -> Result<SMT::SolverResult> { return SMT::Solver({SMT::Constraint(std::move(bf_not))}).query(config); });
505 
506  if (solver_res.is_error() || !solver_res.get().is_unsat())
507  {
508  equal = false;
509  }
510  }
511 
512  if (equal)
513  {
514  current_duplicates.push_back(current_gate);
515  visited.insert(current_gate);
516  }
517  }
518 
519  if (current_duplicates.size() > 1)
520  {
521  duplicate_gates.push_back(current_duplicates);
522  }
523  }
524  }
525  else if (fingerprint.type->has_property(GateTypeProperty::ff))
526  {
527  duplicate_gates.push_back(std::move(gates));
528  }
529  }
530 
531  std::set<Gate*> affected_gates;
532  for (auto& current_duplicates : duplicate_gates)
533  {
534  std::sort(current_duplicates.begin(), current_duplicates.end(), [](const auto& g1, const auto& g2) { return g1->get_name().length() < g2->get_name().length(); });
535 
536  auto* survivor_gate = current_duplicates.front();
537  std::map<GatePin*, Net*> out_pins_to_nets;
538  for (auto* ep : survivor_gate->get_fan_out_endpoints())
539  {
540  Net* out_net = ep->get_net();
541  out_pins_to_nets[ep->get_pin()] = out_net;
542  for (const auto* dst : out_net->get_destinations())
543  {
544  auto* dst_gate = dst->get_gate();
545  auto* dst_type = dst_gate->get_type();
546  if (dst_type->has_property(GateTypeProperty::combinational) || dst_type->has_property(GateTypeProperty::ff))
547  {
548  affected_gates.insert(dst_gate);
549  }
550  }
551  }
552 
553  for (u32 k = 1; k < current_duplicates.size(); k++)
554  {
555  auto* current_gate = current_duplicates.at(k);
556  for (auto* ep : current_gate->get_fan_out_endpoints())
557  {
558  auto* ep_net = ep->get_net();
559  auto* ep_pin = ep->get_pin();
560 
561  if (auto it = out_pins_to_nets.find(ep_pin); it != out_pins_to_nets.cend())
562  {
563  // survivor already has net connected to this output -> add destination to survivor's net
564  for (auto* dst : ep_net->get_destinations())
565  {
566  auto* dst_gate = dst->get_gate();
567  auto* dst_pin = dst->get_pin();
568  dst->get_net()->remove_destination(dst);
569  it->second->add_destination(dst_gate, dst_pin);
570 
571  auto* dst_type = dst_gate->get_type();
572  if (dst_type->has_property(GateTypeProperty::combinational) || dst_type->has_property(GateTypeProperty::ff))
573  {
574  affected_gates.insert(dst_gate);
575  }
576  }
577  if (!nl->delete_net(ep_net))
578  {
579  log_warning("netlist_preprocessing", "could not delete net '{}' with ID {} from netlist with ID {}.", ep_net->get_name(), ep_net->get_id(), nl->get_id());
580  }
581  }
582  else
583  {
584  // survivor does not feature net on this output pin -> connect this net to survivor
585  ep_net->add_source(survivor_gate, ep_pin);
586  out_pins_to_nets[ep_pin] = ep_net;
587  for (auto* dst : ep_net->get_destinations())
588  {
589  auto* dst_gate = dst->get_gate();
590  auto* dst_type = dst_gate->get_type();
591  if (dst_type->has_property(GateTypeProperty::combinational) || dst_type->has_property(GateTypeProperty::ff))
592  {
593  affected_gates.insert(dst_gate);
594  }
595  }
596  }
597  }
598 
599  annotate_ff_survivor(ff_replacements, survivor_gate, current_gate);
600 
601  affected_gates.erase(current_gate);
602  if (!nl->delete_gate(current_gate))
603  {
604  log_warning("netlist_preprocessing", "could not delete gate '{}' with ID {} from netlist with ID {}.", current_gate->get_name(), current_gate->get_id(), nl->get_id());
605  }
606  else
607  {
608  progress = true;
609  num_gates++;
610  }
611  }
612  }
613  target_gates = std::vector<Gate*>(affected_gates.cbegin(), affected_gates.cend());
614  } while (progress);
615 
616  update_ff_replacements(ff_replacements);
617 
618  log_info("netlist_preprocessing", "removed {} redundant gates from netlist with ID {}.", num_gates, nl->get_id());
619  return OK(num_gates);
620  }
621 
622  Result<u32> remove_redundant_loops(Netlist* nl)
623  {
624  struct LoopFingerprint
625  {
626  std::map<const GateType*, u32> types;
627  std::set<std::string> external_variable_names;
628  std::set<const Net*> ff_control_nets;
629 
630  bool operator<(const LoopFingerprint& other) const
631  {
632  return (other.types < types) || (other.types == types && other.external_variable_names < external_variable_names)
633  || (other.types == types && other.external_variable_names == external_variable_names && other.ff_control_nets < ff_control_nets);
634  }
635  };
636 
637  auto config = hal::SMT::QueryConfig();
638 
639 #ifdef BITWUZLA_LIBRARY
640  auto s_type = hal::SMT::SolverType::Bitwuzla;
641  auto s_call = hal::SMT::SolverCall::Library;
642  config = config.with_solver(s_type).with_call(s_call);
643 #endif
644 
645  u32 num_gates = 0;
646 
647  auto ff_replacements = restore_ff_replacements(nl);
648 
649  static const std::set<PinType> ff_control_pin_types = {PinType::clock, PinType::enable, PinType::reset, PinType::set};
650 
651  // detect combinational loops that begin and end at the same FF
652  // for some FFs, multiple combinational lops may exist; such loops wil be merged into a single one
653  std::unordered_map<Gate*, std::unordered_set<Gate*>> loops_by_start_gate;
654  for (auto* start_ff : nl->get_gates([](const Gate* g) { return g->get_type()->has_property(GateTypeProperty::ff); }))
655  {
656  std::vector<Gate*> stack = {start_ff};
657  std::vector<Gate*> previous_gates;
658  std::unordered_set<Gate*> visited_gates;
659  std::unordered_set<Gate*> cache;
660 
661  while (!stack.empty())
662  {
663  auto* current_gate = stack.back();
664 
665  if (!previous_gates.empty() && current_gate == previous_gates.back())
666  {
667  stack.pop_back();
668  previous_gates.pop_back();
669  continue;
670  }
671 
672  visited_gates.insert(current_gate);
673 
674  bool added = false;
675  for (const auto* suc_ep : current_gate->get_successors())
676  {
677  if (ff_control_pin_types.find(suc_ep->get_pin()->get_type()) != ff_control_pin_types.end())
678  {
679  continue;
680  }
681 
682  auto* suc_gate = suc_ep->get_gate();
683  if (suc_gate == start_ff || cache.find(suc_gate) != cache.end())
684  {
685  loops_by_start_gate[start_ff].insert(current_gate);
686  cache.insert(current_gate);
687  for (auto it = ++(previous_gates.begin()); it != previous_gates.end(); it++)
688  {
689  cache.insert(*it);
690  loops_by_start_gate[start_ff].insert(*it);
691  }
692  }
693  else if (suc_gate->get_type()->has_property(GateTypeProperty::combinational))
694  {
695  if (visited_gates.find(suc_gate) == visited_gates.end())
696  {
697  stack.push_back(suc_gate);
698  added = true;
699  }
700  }
701  }
702 
703  if (added)
704  {
705  previous_gates.push_back(current_gate);
706  }
707  else
708  {
709  stack.pop_back();
710  }
711  }
712  }
713 
714  std::map<LoopFingerprint, std::vector<std::pair<std::vector<Gate*>, BooleanFunction>>> fingerprinted_loops;
715  for (const auto& [start_ff, comb_gates] : loops_by_start_gate)
716  {
717  LoopFingerprint fingerprint;
718 
719  // do not consider loop of more than 30 gates
720  if (comb_gates.size() > 30)
721  {
722  continue;
723  }
724 
725  // collect FF control and data nets
726  std::vector<const Endpoint*> data_in;
727  for (const auto* ep : start_ff->get_fan_in_endpoints())
728  {
729  auto pin_type = ep->get_pin()->get_type();
730  if (ff_control_pin_types.find(pin_type) != ff_control_pin_types.end())
731  {
732  fingerprint.ff_control_nets.insert(ep->get_net());
733  }
734  else if (pin_type == PinType::data)
735  {
736  data_in.push_back(ep);
737  }
738  }
739 
740  if (data_in.size() != 1)
741  {
742  continue;
743  }
744 
745  // collect gate types
746  fingerprint.types[start_ff->get_type()] = 1;
747  for (const auto* g : comb_gates)
748  {
749  const auto* gt = g->get_type();
750  if (const auto type_it = fingerprint.types.find(gt); type_it == fingerprint.types.end())
751  {
752  fingerprint.types[gt] = 0;
753  }
754  fingerprint.types[gt]++;
755  }
756 
757  std::vector<const Gate*> comb_gates_vec(comb_gates.cbegin(), comb_gates.cend());
758  if (auto function_res = SubgraphNetlistDecorator(*nl).get_subgraph_function(comb_gates_vec, data_in.front()->get_net()); function_res.is_ok())
759  {
760  // get Boolean function variable names
761  BooleanFunction function = function_res.get();
762  fingerprint.external_variable_names = function.get_variable_names();
763 
764  // replace FF output net identifier from function variables (otherwise varies depending on FF, preventing later SMT check)
765  for (const auto* ep : start_ff->get_fan_out_endpoints())
766  {
767  if (const auto it = fingerprint.external_variable_names.find(BooleanFunctionNetDecorator(*(ep->get_net())).get_boolean_variable_name());
768  it != fingerprint.external_variable_names.end())
769  {
770  function = function.substitute(*it, ep->get_pin()->get_name());
771  fingerprint.external_variable_names.erase(it);
772  }
773  }
774 
775  std::vector<Gate*> loop_gates = {start_ff};
776  loop_gates.insert(loop_gates.end(), comb_gates.begin(), comb_gates.end());
777  fingerprinted_loops[fingerprint].push_back(std::make_pair(loop_gates, std::move(function)));
778  }
779  }
780 
781  std::vector<std::vector<std::vector<Gate*>>> duplicate_loops;
782  for (const auto& [_, loops] : fingerprinted_loops)
783  {
784  if (loops.size() == 1)
785  {
786  continue;
787  }
788 
789  std::set<u32> visited;
790  for (u32 i = 0; i < loops.size(); i++)
791  {
792  if (visited.find(i) != visited.cend())
793  {
794  continue;
795  }
796 
797  const auto& master_loop = loops.at(i);
798 
799  std::vector<std::vector<Gate*>> current_duplicates = {std::get<0>(master_loop)};
800 
801  for (size_t j = i + 1; j < loops.size(); j++)
802  {
803  const auto& current_loop = loops.at(j);
804  const auto solver_res =
805  BooleanFunction::Eq(std::get<1>(master_loop).clone(), std::get<1>(current_loop).clone(), 1)
806  .map<BooleanFunction>([](auto&& bf_eq) -> Result<BooleanFunction> { return BooleanFunction::Not(std::move(bf_eq), 1); })
807  .map<SMT::SolverResult>([&config](auto&& bf_not) -> Result<SMT::SolverResult> { return SMT::Solver({SMT::Constraint(std::move(bf_not))}).query(config); });
808 
809  if (solver_res.is_ok() && solver_res.get().is_unsat())
810  {
811  current_duplicates.push_back(std::get<0>(current_loop));
812  visited.insert(j);
813  }
814  }
815 
816  if (current_duplicates.size() > 1)
817  {
818  duplicate_loops.push_back(std::move(current_duplicates));
819  }
820  }
821  }
822 
823  for (const auto& current_duplicates : duplicate_loops)
824  {
825  // TODO the "replace" logic where the output of the survivor ff is connected to new sources and the old gates are deleted is a duplicate of the above functionality
826  const auto& survivor_loop = current_duplicates.front();
827  auto* survivor_ff = survivor_loop.front();
828 
829  std::map<GatePin*, Net*> out_pins_to_nets;
830  for (auto* ep : survivor_ff->get_fan_out_endpoints())
831  {
832  Net* out_net = ep->get_net();
833  out_pins_to_nets[ep->get_pin()] = out_net;
834  }
835 
836  for (u32 i = 1; i < current_duplicates.size(); i++)
837  {
838  auto* current_ff = current_duplicates.at(i).front();
839  for (auto* ep : current_ff->get_fan_out_endpoints())
840  {
841  auto* ep_net = ep->get_net();
842  auto* ep_pin = ep->get_pin();
843 
844  if (auto it = out_pins_to_nets.find(ep_pin); it != out_pins_to_nets.cend())
845  {
846  // survivor already has net connected to this output -> add destination to survivor's net
847  for (auto* dst : ep_net->get_destinations())
848  {
849  auto* dst_gate = dst->get_gate();
850  auto* dst_pin = dst->get_pin();
851  dst->get_net()->remove_destination(dst);
852  it->second->add_destination(dst_gate, dst_pin);
853  }
854  if (!nl->delete_net(ep_net))
855  {
856  log_warning("netlist_preprocessing", "could not delete net '{}' with ID {} from netlist with ID {}.", ep_net->get_name(), ep_net->get_id(), nl->get_id());
857  }
858  }
859  else
860  {
861  // survivor does not feature net on this output pin -> connect this net to survivor
862  ep_net->add_source(survivor_ff, ep_pin);
863  out_pins_to_nets[ep_pin] = ep_net;
864  }
865  }
866 
867  annotate_ff_survivor(ff_replacements, survivor_ff, current_ff);
868 
869  if (!nl->delete_gate(current_ff))
870  {
871  log_warning("netlist_preprocessing", "could not delete gate '{}' with ID {} from netlist with ID {}.", current_ff->get_name(), current_ff->get_id(), nl->get_id());
872  }
873  else
874  {
875  num_gates++;
876  }
877  }
878  }
879 
880  update_ff_replacements(ff_replacements);
881 
882  log_info("netlist_preprocessing", "removed {} redundant loops from netlist with ID {}.", num_gates, nl->get_id());
883  return OK(num_gates);
884  }
885 
886  Result<u32> remove_redundant_logic_trees(Netlist* nl)
887  {
888  struct TreeFingerprint
889  {
890  std::set<const Net*> external_inputs;
891  // std::set<std::string> external_inputs;
892 
893  bool operator<(const TreeFingerprint& other) const
894  {
895  return (other.external_inputs < external_inputs);
896  }
897  };
898 
899  const std::vector<Gate*> all_comb_gates_vec = nl->get_gates([](const auto& g) { return g->get_type()->has_property(GateTypeProperty::combinational); });
900  // const std::unordered_set<Gate*> all_comb_gates_set = {all_comb_gates_vec.begin(), all_comb_gates_vec.end()};
901 
902  std::map<TreeFingerprint, std::set<Net*>> fingerprint_to_nets;
903  for (const auto& g : all_comb_gates_vec)
904  {
905  for (const auto& out_ep : g->get_fan_out_endpoints())
906  {
907  // const auto non_comb_destinations = out_ep->get_net()->get_destinations([](const auto& in_ep){ return !in_ep->get_gate()->get_type()->has_property(GateTypeProperty::combinational);});
908  // if (!non_comb_destinations.empty())
909  {
910  const auto& out_net = out_ep->get_net();
911  auto inputs_res = SubgraphNetlistDecorator(*nl).get_subgraph_function_inputs(all_comb_gates_vec, out_net);
912  if (inputs_res.is_error())
913  {
914  return ERR_APPEND(inputs_res.get_error(),
915  "Unable to remove redundant logic trees: failed to gather inputs for net " + out_net->get_name() + " with ID " + std::to_string(out_net->get_id()));
916  }
917  TreeFingerprint tf;
918  tf.external_inputs = inputs_res.get();
919  // tf.external_inputs = SubgraphNetlistDecorator(*nl).get_subgraph_function(all_comb_gates_vec, out_net).get().simplify().get_variable_names();
920 
921  fingerprint_to_nets[tf].insert(out_net);
922  }
923  }
924  }
925 
926  std::vector<std::vector<Net*>> equality_classes;
927 
928  for (const auto& [_fingerprint, nets] : fingerprint_to_nets)
929  {
930  // TODO remove
931  // std::cout << "Fingerprint(" << _fingerprint.external_inputs.size() << "): " << std::endl;
932  // for (const auto& n : _fingerprint.external_inputs)
933  // {
934  // std::cout << "\t" << n << std::endl;
935  // }
936  // std::cout << "Checking nets: " << std::endl;
937  // for (const auto& n : nets)
938  // {
939  // std::cout << "\t" << n->get_name() << std::endl;
940  // }
941 
942  std::vector<Net*> current_candidate_nets = {nets.begin(), nets.end()};
943  std::vector<Net*> next_candidate_nets;
944 
945  while (!current_candidate_nets.empty())
946  {
947  const auto n = current_candidate_nets.back();
948  current_candidate_nets.pop_back();
949 
950  std::vector<Net*> new_equality_class = {n};
951 
952  for (const auto& m : current_candidate_nets)
953  {
954  auto comp_res = z3_utils::compare_nets(nl, nl, n, m);
955  if (comp_res.is_error())
956  {
957  return ERR_APPEND(comp_res.get_error(),
958  "Unable to remove redundant logic trees: failed to compare net " + n->get_name() + " with ID " + std::to_string(n->get_id()) + " with net "
959  + m->get_name() + " with ID " + std::to_string(m->get_id()));
960  }
961  const auto are_equal = comp_res.get();
962 
963  if (are_equal)
964  {
965  new_equality_class.push_back(m);
966  }
967  else
968  {
969  next_candidate_nets.push_back(m);
970  }
971  }
972 
973  equality_classes.push_back(new_equality_class);
974  current_candidate_nets = next_candidate_nets;
975  next_candidate_nets.clear();
976  }
977  }
978 
979  u32 counter = 0;
980  for (const auto& eq_class : equality_classes)
981  {
982  // TODO remove
983  // std::cout << "Equal nets: " << std::endl;
984  // for (const auto& n : eq_class)
985  // {
986  // std::cout << n->get_name() << std::endl;
987  // }
988 
989  auto survivor_net = eq_class.front();
990 
991  for (u32 i = 1; i < eq_class.size(); i++)
992  {
993  auto victim_net = eq_class.at(i);
994  for (const auto& dst : victim_net->get_destinations())
995  {
996  auto dst_gate = dst->get_gate();
997  auto dst_pin = dst->get_pin();
998 
999  if (!victim_net->remove_destination(dst))
1000  {
1001  return ERR("Unable to remove redundant logic trees: failed to remove destination of net " + victim_net->get_name() + " with ID " + std::to_string(victim_net->get_id())
1002  + " at gate " + dst_gate->get_name() + " with ID " + std::to_string(dst_gate->get_id()) + " and pin " + dst_pin->get_name());
1003  }
1004  if (!survivor_net->add_destination(dst_gate, dst_pin))
1005  {
1006  return ERR("Unable to remove redundant logic trees: failed to add destination to net " + survivor_net->get_name() + " with ID " + std::to_string(survivor_net->get_id())
1007  + " at gate " + dst_gate->get_name() + " with ID " + std::to_string(dst_gate->get_id()) + " and pin " + dst_pin->get_name());
1008  }
1009 
1010  counter += 1;
1011  }
1012  }
1013  }
1014 
1015  auto clean_up_res = remove_unconnected_looped(nl);
1016  if (clean_up_res.is_error())
1017  {
1018  return ERR_APPEND(clean_up_res.get_error(), "Unable to remove redundant logic trees: failed to clean up dangling trees");
1019  }
1020 
1021  return OK(clean_up_res.get() + counter);
1022  }
1023 
1024  Result<u32> remove_unconnected_gates(Netlist* nl)
1025  {
1026  u32 num_gates = 0;
1027  std::vector<Gate*> to_delete;
1028  do
1029  {
1030  to_delete.clear();
1031 
1032  for (const auto& g : nl->get_gates())
1033  {
1034  bool is_unconnected = true;
1035  for (const auto& on : g->get_fan_out_nets())
1036  {
1037  if (!on->get_destinations().empty() || on->is_global_output_net())
1038  {
1039  is_unconnected = false;
1040  }
1041  }
1042 
1043  if (is_unconnected)
1044  {
1045  to_delete.push_back(g);
1046  }
1047  }
1048 
1049  for (const auto& g : to_delete)
1050  {
1051  if (!nl->delete_gate(g))
1052  {
1053  log_warning("netlist_preprocessing", "could not delete gate '{}' with ID {} from netlist with ID {}.", g->get_name(), g->get_id(), nl->get_id());
1054  }
1055  else
1056  {
1057  num_gates++;
1058  }
1059  }
1060  } while (!to_delete.empty());
1061 
1062  log_info("netlist_preprocessing", "removed {} unconnected gates from netlist with ID {}.", num_gates, nl->get_id());
1063  return OK(num_gates);
1064  }
1065 
1066  Result<u32> remove_unconnected_nets(Netlist* nl)
1067  {
1068  u32 num_nets = 0;
1069 
1070  std::vector<Net*> to_delete;
1071 
1072  for (const auto& n : nl->get_nets())
1073  {
1074  if (!n->is_global_input_net() && n->get_sources().empty() && !n->is_global_output_net() && n->get_destinations().empty())
1075  {
1076  to_delete.push_back(n);
1077  }
1078  }
1079 
1080  for (const auto& n : to_delete)
1081  {
1082  if (!nl->delete_net(n))
1083  {
1084  log_warning("netlist_preprocessing", "could not delete net '{}' with ID {} from netlist with ID {}.", n->get_name(), n->get_id(), nl->get_id());
1085  }
1086  else
1087  {
1088  num_nets++;
1089  }
1090  }
1091 
1092  log_info("netlist_preprocessing", "removed {} unconnected nets from netlist with ID {}.", num_nets, nl->get_id());
1093  return OK(num_nets);
1094  }
1095 
1096  Result<u32> remove_unconnected_looped(Netlist* nl)
1097  {
1098  u32 total_removed = 0;
1099 
1100  while (true)
1101  {
1102  auto gate_res = remove_unconnected_gates(nl);
1103  if (gate_res.is_error())
1104  {
1105  return ERR_APPEND(gate_res.get_error(), "unable to execute clean up loop: failed to remove unconnected gates");
1106  }
1107 
1108  auto net_res = remove_unconnected_nets(nl);
1109  if (net_res.is_error())
1110  {
1111  return ERR_APPEND(net_res.get_error(), "unable to execute clean up loop: failed to remove unconnected nets");
1112  }
1113 
1114  const u32 removed = gate_res.get() + net_res.get();
1115  total_removed += removed;
1116  if (!removed)
1117  {
1118  break;
1119  }
1120  }
1121 
1122  return OK(total_removed);
1123  }
1124 
1125  namespace
1126  {
1127  Result<u32> remove_encasing_inverters(Netlist* nl)
1128  {
1129  // check whether all inputs and output are inverted -> remove all inverters
1130 
1131  // TODO: this only considers HAL muxes, but i do not see a reason why. There is no resynthesis happening here
1132  std::vector<Gate*> muxes = nl->get_gates([](const Gate* g) { return (g->get_type()->get_name().find("HAL_MUX") != std::string::npos); });
1133 
1134  u32 delete_count = 0;
1135  std::vector<Gate*> delete_gate_q;
1136 
1137  for (const auto& g : muxes)
1138  {
1139  if (g->get_successors().size() > 1)
1140  {
1141  continue;
1142  }
1143 
1144  auto data_pins = g->get_type()->get_pins([](const GatePin* pin) { return (pin->get_type() == PinType::data) && (pin->get_direction() == PinDirection::input); });
1145  auto out_pins = g->get_type()->get_pins([](const GatePin* pin) { return (pin->get_direction() == PinDirection::output); });
1146 
1147  if (data_pins.size() < 2)
1148  {
1149  continue;
1150  }
1151 
1152  if (out_pins.size() != 1)
1153  {
1154  continue;
1155  }
1156 
1157  bool preceded_by_inv = true;
1158  for (const auto& pin : data_pins)
1159  {
1160  const auto pred = g->get_predecessor(pin);
1161  if (pred == nullptr || pred->get_gate() == nullptr || !pred->get_gate()->get_type()->has_property(GateTypeProperty::c_inverter))
1162  {
1163  preceded_by_inv = false;
1164  break;
1165  }
1166  }
1167 
1168  if (!preceded_by_inv)
1169  {
1170  continue;
1171  }
1172 
1173  bool succeded_by_inv = true;
1174  for (const auto& pin : out_pins)
1175  {
1176  const auto suc = g->get_successor(pin);
1177  if (suc == nullptr || suc->get_gate() == nullptr || !suc->get_gate()->get_type()->has_property(GateTypeProperty::c_inverter))
1178  {
1179  succeded_by_inv = false;
1180  break;
1181  }
1182  }
1183 
1184  if (!succeded_by_inv)
1185  {
1186  continue;
1187  }
1188 
1189  // delete all connections from and to inverters (and inverter gates if they do not share any other connection)
1190  for (const auto& pin : data_pins)
1191  {
1192  const auto pred = g->get_predecessor(pin);
1193 
1194  // disconnect inverter output from mux
1195  pred->get_net()->remove_destination(g, pin);
1196 
1197  // connect inverter input net to mux
1198  auto in_net = pred->get_gate()->get_fan_in_nets().front();
1199  in_net->add_destination(g, pin);
1200 
1201  // delete inverter gate if it does not have any successors
1202  if (pred->get_gate()->get_successors().empty())
1203  {
1204  delete_gate_q.push_back(pred->get_gate());
1205  }
1206  }
1207 
1208  for (const auto& pin : out_pins)
1209  {
1210  const auto suc = g->get_successor(pin);
1211 
1212  // disconnect inverter input from mux
1213  suc->get_net()->remove_source(g, pin);
1214 
1215  // connect inverter output net to mux
1216  auto in_net = suc->get_gate()->get_fan_out_nets().front();
1217  in_net->add_source(g, pin);
1218 
1219  // delete inverter gate if it does not have any predecessors
1220  if (suc->get_gate()->get_predecessors().empty())
1221  {
1222  delete_gate_q.push_back(suc->get_gate());
1223  }
1224  }
1225  }
1226 
1227  for (auto g : delete_gate_q)
1228  {
1229  nl->delete_gate(g);
1230  delete_count++;
1231  }
1232 
1233  log_info("netlist_preprocessing", "removed {} encasing inverters", delete_count);
1234 
1235  return OK(delete_count);
1236  }
1237 
1238  struct MuxFingerprint
1239  {
1240  GateType* type;
1241  std::set<GatePin*> inverters;
1242 
1243  bool operator<(const MuxFingerprint& other) const
1244  {
1245  return (other.type < type) || (other.type == type && other.inverters < inverters);
1246  }
1247  };
1248 
1249  Result<u32> unify_inverted_select_signals(Netlist* nl, GateLibrary* mux_inv_gl)
1250  {
1251  if (nl == nullptr)
1252  {
1253  return ERR("netlist is a nullptr");
1254  }
1255 
1256  if (mux_inv_gl == nullptr)
1257  {
1258  return ERR("gate library is a nullptr");
1259  }
1260 
1261  auto base_path_res = utils::get_unique_temp_directory("resynthesis_");
1262  if (base_path_res.is_error())
1263  {
1264  return ERR_APPEND(base_path_res.get_error(), "unable to resynthesize boolean functions with yosys: failed to get unique temp directory");
1265  }
1266  const std::filesystem::path base_path = base_path_res.get();
1267  const std::filesystem::path genlib_path = base_path / "mux_inv.genlib";
1268  std::filesystem::create_directory(base_path);
1269 
1270  const auto gl_save_res = gate_library_manager::save(genlib_path, mux_inv_gl, true);
1271  if (!gl_save_res)
1272  {
1273  return ERR("unable to unify muxe select signals: failed to save gate library " + mux_inv_gl->get_name() + " to location " + genlib_path.string());
1274  }
1275 
1276  const i64 initial_size = nl->get_gates().size();
1277 
1278  // resynthesize all muxes where any select signal is preceded by an inverter hoping to unify the structure with regards to other muxes conntected to the same select signal
1279 
1280  // TODO: as long as resynthezising the subgraph this can only consider HAL muxes
1281  std::vector<Gate*> muxes = nl->get_gates([](const Gate* g) { return (g->get_type()->get_name().find("HAL_MUX") != std::string::npos); });
1282 
1283  std::map<MuxFingerprint, std::unique_ptr<Netlist>> resynth_cache;
1284 
1285  for (const auto& g : muxes)
1286  {
1287  // MUX fingerprint for caching resynthesis results
1288  MuxFingerprint mf;
1289  mf.type = g->get_type();
1290 
1291  // mapping from MUX select pins to either the input net of the preceding inverter or the net directly connected to the select pin
1292  std::map<GatePin*, Net*> pin_to_input;
1293 
1294  auto select_pins = g->get_type()->get_pins([](const GatePin* pin) { return (pin->get_type() == PinType::select) && (pin->get_direction() == PinDirection::input); });
1295 
1296  std::vector<Gate*> preceding_inverters;
1297  for (const auto& pin : g->get_type()->get_input_pins())
1298  {
1299  const auto pred = g->get_predecessor(pin);
1300  const auto is_select = (std::find(select_pins.begin(), select_pins.end(), pin) != select_pins.end());
1301  if (!is_select || pred == nullptr || pred->get_gate() == nullptr || !pred->get_gate()->get_type()->has_property(GateTypeProperty::c_inverter)
1302  || (pred->get_gate()->get_fan_in_endpoints().size() != 1))
1303  {
1304  pin_to_input.insert({pin, g->get_fan_in_net(pin)});
1305  }
1306  else
1307  {
1308  auto inv_gate = pred->get_gate();
1309  preceding_inverters.push_back(inv_gate);
1310  pin_to_input.insert({pin, inv_gate->get_fan_in_endpoints().front()->get_net()});
1311  mf.inverters.insert(pin);
1312  }
1313  }
1314 
1315  // if there is at least one inverter in front of the mux gate we build a subgraph containing all inverters and the mux gate and resynthesize
1316  if (!preceding_inverters.empty())
1317  {
1318  const Netlist* resynth_nl;
1319 
1320  auto subgraph = preceding_inverters;
1321  subgraph.push_back(g);
1322 
1323  // try to use cached resynth netlist
1324  if (const auto it = resynth_cache.find(mf); it == resynth_cache.end())
1325  {
1326  std::unordered_map<std::string, BooleanFunction> bfs;
1327  for (const auto& ep : g->get_fan_out_endpoints())
1328  {
1329  const auto bf_res = SubgraphNetlistDecorator(*nl).get_subgraph_function(subgraph, ep->get_net());
1330  if (bf_res.is_error())
1331  {
1332  return ERR_APPEND(bf_res.get_error(),
1333  "unable to unify muxes select signals: failed to build boolean function for mux " + g->get_name() + " with ID " + std::to_string(g->get_id())
1334  + " at output " + ep->get_pin()->get_name());
1335  }
1336  auto bf = bf_res.get();
1337 
1338  // replace all net id vars with generic vaiables refering to their connectivity to the mux
1339  for (const auto& [pin, net] : pin_to_input)
1340  {
1341  auto sub_res = bf.substitute(BooleanFunctionNetDecorator(*net).get_boolean_variable_name(), BooleanFunction::Var(pin->get_name(), 1));
1342  if (sub_res.is_error())
1343  {
1344  return ERR_APPEND(sub_res.get_error(), "unable to unify muxes select signals: failed to substitute net_id variable with generic variable");
1345  }
1346  bf = sub_res.get();
1347  }
1348 
1349  bfs.insert({ep->get_pin()->get_name(), std::move(bf)});
1350  }
1351 
1352  auto resynth_res = resynthesis::generate_resynth_netlist_for_boolean_functions(bfs, genlib_path, mux_inv_gl, true);
1353  if (resynth_res.is_error())
1354  {
1355  return ERR_APPEND(resynth_res.get_error(), "unable to unify select signals of muxes: failed to resynthesize mux subgraph to netlist");
1356  }
1357  auto unique_resynth_nl = resynth_res.get();
1358  resynth_nl = unique_resynth_nl.get();
1359  resynth_cache.insert({mf, std::move(unique_resynth_nl)});
1360  }
1361  else
1362  {
1363  resynth_nl = it->second.get();
1364  }
1365 
1366  std::unordered_map<Net*, std::vector<Net*>> global_io_mapping;
1367 
1368  // use top module pin names to find correponding nets in original netlist
1369  for (const auto& pin : resynth_nl->get_top_module()->get_input_pins())
1370  {
1371  auto net_it = pin_to_input.find(g->get_type()->get_pin_by_name(pin->get_name()));
1372  if (net_it == pin_to_input.end())
1373  {
1374  return ERR("unable to unify muxes select signals:: failed to locate net in destination netlist from global input " + pin->get_name() + " in resynthesized netlist");
1375  }
1376  global_io_mapping[pin->get_net()].push_back(net_it->second);
1377  }
1378  for (const auto& pin : resynth_nl->get_top_module()->get_output_pins())
1379  {
1380  auto net = g->get_fan_out_net(pin->get_name());
1381  if (net == nullptr)
1382  {
1383  return ERR("unable to unify muxes select signals:: failed to locate net in destination netlist from global output " + pin->get_name() + " in resynthesized netlist");
1384  }
1385  global_io_mapping[pin->get_net()].push_back(net);
1386  }
1387 
1388  auto replace_res = resynthesis::replace_subgraph_with_netlist(subgraph, global_io_mapping, resynth_nl, nl, false);
1389  if (replace_res.is_error())
1390  {
1391  return ERR("unable to unify muxes select signals: failed to replace mux subgraph with resynthesized netlist");
1392  }
1393 
1394  // delete old subgraph gates that only fed into the mux
1395  std::vector<Gate*> to_delete;
1396  for (const auto g : subgraph)
1397  {
1398  bool has_no_outside_destinations = true;
1399  bool has_only_outside_destinations = true;
1400  for (const auto& suc : g->get_successors())
1401  {
1402  const auto it = std::find(subgraph.begin(), subgraph.end(), suc->get_gate());
1403  if (it == subgraph.end())
1404  {
1405  has_no_outside_destinations = false;
1406  }
1407 
1408  if (it != subgraph.end())
1409  {
1410  has_only_outside_destinations = false;
1411  }
1412  }
1413 
1414  if (has_no_outside_destinations || has_only_outside_destinations)
1415  {
1416  to_delete.push_back(g);
1417  }
1418  }
1419 
1420  for (const auto& g : to_delete)
1421  {
1422  if (!nl->delete_gate(g))
1423  {
1424  return ERR("unable to unify muxes select signals: failed to delete gate " + g->get_name() + " with ID " + std::to_string(g->get_id()) + " in destination netlist");
1425  }
1426  }
1427  }
1428  }
1429 
1430  // delete the created directory and the contained files
1431  std::filesystem::remove_all(base_path);
1432 
1433  const i64 new_size = nl->get_gates().size();
1434  const i64 difference = std::abs(initial_size - new_size);
1435 
1436  return OK(u32(difference));
1437  }
1438 
1439  Result<u32> unify_select_signals(Netlist* nl)
1440  {
1441  if (nl == nullptr)
1442  {
1443  return ERR("netlist is a nullptr");
1444  }
1445 
1446  u32 changed_connections = 0;
1447 
1448  // sort into groups of same type and identical select signals
1449  std::map<std::pair<GateType*, std::set<Net*>>, std::vector<Gate*>> grouped_muxes;
1450  for (const auto& g : nl->get_gates([](const Gate* g) { return g->get_type()->has_property(GateTypeProperty::c_mux); }))
1451  {
1452  std::set<Net*> select_signals;
1453  const auto select_pins = g->get_type()->get_pins([](const GatePin* pin) { return (pin->get_type() == PinType::select) && (pin->get_direction() == PinDirection::input); });
1454  for (const auto& sp : select_pins)
1455  {
1456  select_signals.insert(g->get_fan_in_net(sp));
1457  }
1458 
1459  grouped_muxes[{g->get_type(), select_signals}].push_back(g);
1460  }
1461 
1462  // unify select signals for each group
1463  for (const auto& [finger_print, mux_group] : grouped_muxes)
1464  {
1465  const auto& [type, select_signals_set] = finger_print;
1466  const auto select_pins = type->get_pins([](const GatePin* pin) { return (pin->get_type() == PinType::select) && (pin->get_direction() == PinDirection::input); });
1467  const auto output_pins = type->get_pins([](const GatePin* pin) { return pin->get_direction() == PinDirection::output; });
1468 
1469  if (output_pins.size() != 1)
1470  {
1471  log_warning("netlist_preprocessing",
1472  "Cannot unify select signals for muxes of type {} since the type has {} output signals and we can only handle 1.",
1473  type->get_name(),
1474  output_pins.size());
1475  continue;
1476  }
1477 
1478  // check whether there is one mapping from select signals to select pins
1479  std::map<std::map<GatePin*, Net*>, std::vector<Gate*>> select_map_to_muxes;
1480  for (const auto& g : mux_group)
1481  {
1482  std::map<GatePin*, Net*> select_map;
1483  for (const auto& sp : select_pins)
1484  {
1485  select_map.insert({sp, g->get_fan_in_net(sp)});
1486  }
1487 
1488  select_map_to_muxes[select_map].push_back(g);
1489  }
1490 
1491  if (select_map_to_muxes.size() == 1)
1492  {
1493  continue;
1494  }
1495 
1496  const std::vector<Net*> select_signals = {select_signals_set.begin(), select_signals_set.end()};
1497 
1498  // collect a new mapping from net to gate pin for each mux gate
1499  std::map<Gate*, std::map<GatePin*, Net*>> new_net_to_pin;
1500 
1501  // add newly ordered select signals to pin/net mapping
1502  for (const auto& g : mux_group)
1503  {
1504  for (u32 select_index = 0; select_index < select_pins.size(); select_index++)
1505  {
1506  auto select_pin = select_pins.at(select_index);
1507  auto select_signal = select_signals.at(select_index);
1508  new_net_to_pin[g][select_pin] = select_signal;
1509  }
1510  }
1511 
1512  // determine new pin/net connection for each "data" signal
1513  auto type_bf = type->get_boolean_function(output_pins.front());
1514  for (u32 select_val = 0; select_val < (1 << select_signals.size()); select_val++)
1515  {
1516  std::map<std::string, BooleanFunction> type_substitution;
1517  for (u32 select_idx = 0; select_idx < select_pins.size(); select_idx++)
1518  {
1519  auto select_pin = select_pins.at(select_idx);
1520 
1521  auto type_substitution_val = ((select_val >> select_idx) & 0x1) ? BooleanFunction::Const(1, 1) : BooleanFunction::Const(0, 1);
1522  type_substitution.insert({select_pin->get_name(), type_substitution_val});
1523  }
1524 
1525  auto type_substitution_res = type_bf.substitute(type_substitution);
1526  if (type_substitution_res.is_error())
1527  {
1528  return ERR_APPEND(type_substitution_res.get_error(), "cannot unify mux select signals: failed to substitute type Boolean function with select signal value mapping.");
1529  }
1530  auto input = type_substitution_res.get().simplify_local();
1531 
1532  if (!input.is_variable())
1533  {
1534  return ERR("cannot unify mux select signals: substituted and simplified type Boolean function (" + input.to_string() + ") is not a variable");
1535  }
1536 
1537  const auto pin_name = input.get_variable_name().get();
1538  auto pin = type->get_pins([pin_name](const auto& p) { return p->get_name() == pin_name; }).front();
1539 
1540  for (const auto& g : mux_group)
1541  {
1542  auto gate_bf_res = g->get_resolved_boolean_function(output_pins.front(), false);
1543  if (gate_bf_res.is_error())
1544  {
1545  return ERR_APPEND(gate_bf_res.get_error(),
1546  "cannot unify mux select signals: failed to build Boolean function for gate " + g->get_name() + " with ID " + std::to_string(g->get_id()));
1547  }
1548  auto gate_bf = gate_bf_res.get();
1549 
1550  std::map<std::string, BooleanFunction> gate_substitution;
1551 
1552  for (u32 select_idx = 0; select_idx < select_pins.size(); select_idx++)
1553  {
1554  auto gate_substitution_val = ((select_val >> select_idx) & 0x1) ? BooleanFunction::Const(1, 1) : BooleanFunction::Const(0, 1);
1555  gate_substitution.insert({BooleanFunctionNetDecorator(*(select_signals.at(select_idx))).get_boolean_variable_name(), gate_substitution_val});
1556  }
1557 
1558  auto gate_substitution_res = gate_bf.substitute(gate_substitution);
1559  if (gate_substitution_res.is_error())
1560  {
1561  return ERR_APPEND(gate_substitution_res.get_error(), "cannot unify mux select signals: failed to substitute gate Boolean function with select signal value mapping.");
1562  }
1563  auto input_net_var = gate_substitution_res.get().simplify_local();
1564  auto net_res = BooleanFunctionNetDecorator::get_net_from(nl, input_net_var);
1565 
1566  if (net_res.is_error())
1567  {
1568  return ERR_APPEND(net_res.get_error(), "cannot unify mux select signals: failed to extract net from substituted and simplified gate Boolean function");
1569  }
1570 
1571  auto net = net_res.get();
1572  new_net_to_pin[g][pin] = net;
1573  }
1574  }
1575 
1576  // apply new pin/net mapping to all gates
1577  for (auto& [g, pin_net] : new_net_to_pin)
1578  {
1579  for (const auto& [pin, net] : pin_net)
1580  {
1581  auto connected_net = g->get_fan_in_net(pin);
1582  if (net == connected_net)
1583  {
1584  continue;
1585  }
1586 
1587  connected_net->remove_destination(g, pin);
1588  net->add_destination(g, pin);
1589 
1590  changed_connections += 1;
1591  }
1592  }
1593  }
1594 
1595  return OK(changed_connections);
1596  }
1597  } // namespace
1598 
1599  Result<u32> manual_mux_optimizations(Netlist* nl, GateLibrary* mux_inv_gl)
1600  {
1601  u32 res_count = 0;
1602 
1603  if (nl == nullptr)
1604  {
1605  return ERR("netlist is a nullptr");
1606  }
1607 
1608  if (mux_inv_gl == nullptr)
1609  {
1610  return ERR("gate library is a nullptr");
1611  }
1612 
1613  auto remove_res = remove_encasing_inverters(nl);
1614  if (remove_res.is_error())
1615  {
1616  return ERR_APPEND(remove_res.get_error(), "unable to apply manual mux optimizations: failed to remove encasing inverters");
1617  }
1618  res_count += remove_res.get();
1619 
1620  auto unify_inverted_res = unify_inverted_select_signals(nl, mux_inv_gl);
1621  if (unify_inverted_res.is_error())
1622  {
1623  return ERR_APPEND(unify_inverted_res.get_error(), "unable to apply manual mux optimizations: failed to unify inverted select signals");
1624  }
1625  res_count += unify_inverted_res.get();
1626 
1627  auto unify_res = unify_select_signals(nl);
1628  if (unify_res.is_error())
1629  {
1630  return ERR_APPEND(unify_res.get_error(), "unable to apply manual mux optimizations: failed to unify select signals");
1631  }
1632  res_count += unify_res.get();
1633 
1634  return OK(res_count);
1635  }
1636 
1637  Result<u32> propagate_constants(Netlist* nl)
1638  {
1639  if (nl == nullptr)
1640  {
1641  return ERR("netlist is a nullptr");
1642  }
1643 
1644  Net* gnd_net = nl->get_gnd_gates().empty() ? nullptr : nl->get_gnd_gates().front()->get_fan_out_nets().front();
1645  Net* vcc_net = nl->get_vcc_gates().empty() ? nullptr : nl->get_vcc_gates().front()->get_fan_out_nets().front();
1646 
1647  u32 total_replaced_dst_count = 0;
1648 
1649  while (true)
1650  {
1651  u32 replaced_dst_count = 0;
1652  std::vector<Gate*> to_delete;
1653  for (const auto g : nl->get_gates([](const auto g) {
1654  return g->get_type()->has_property(GateTypeProperty::combinational) && !g->get_type()->has_property(GateTypeProperty::ground)
1655  && !g->get_type()->has_property(GateTypeProperty::power);
1656  }))
1657  {
1658  bool has_global_output = false;
1659  for (const auto ep : g->get_fan_out_endpoints())
1660  {
1661  if (ep->get_net()->is_global_output_net())
1662  {
1663  has_global_output = true;
1664  }
1665 
1666  auto bf_res = g->get_resolved_boolean_function(ep->get_pin(), false);
1667  if (bf_res.is_error())
1668  {
1669  return ERR_APPEND(bf_res.get_error(),
1670  "unable to propagate constants: failed to generate boolean function at gate " + g->get_name() + " with ID " + std::to_string(g->get_id()) + " for pin "
1671  + ep->get_pin()->get_name());
1672  }
1673  auto bf = bf_res.get();
1674  auto sub_res = BooleanFunctionDecorator(bf).substitute_power_ground_nets(nl);
1675  if (sub_res.is_error())
1676  {
1677  return ERR_APPEND(bf_res.get_error(),
1678  "unable to propagate constants: failed to substitue power and ground nets in boolean function of gate " + g->get_name() + " with ID "
1679  + std::to_string(g->get_id()) + " for pin " + ep->get_pin()->get_name());
1680  }
1681  bf = sub_res.get();
1682  bf = bf.simplify_local();
1683 
1684  // if boolean function of output pin can be simplified to a constant connect all its successors to gnd/vcc instead
1685  if (bf.is_constant())
1686  {
1687  Net* new_source;
1688  if (bf.has_constant_value(0))
1689  {
1690  new_source = gnd_net;
1691  }
1692  else if (bf.has_constant_value(1))
1693  {
1694  new_source = vcc_net;
1695  }
1696  else
1697  {
1698  continue;
1699  }
1700 
1701  if (new_source == nullptr)
1702  {
1703  // log_error("netlist_preprocessing", "failed to replace bf {} with constant net because netlist is missing GND gate or VCC gate");
1704  return ERR("unable to propagate constants: netlist is missing gnd or vcc net!");
1705  }
1706 
1707  std::vector<std::pair<Gate*, GatePin*>> to_replace;
1708  for (auto dst : ep->get_net()->get_destinations())
1709  {
1710  to_replace.push_back({dst->get_gate(), dst->get_pin()});
1711  }
1712 
1713  for (const auto& [dst_g, dst_p] : to_replace)
1714  {
1715  ep->get_net()->remove_destination(dst_g, dst_p);
1716  new_source->add_destination(dst_g, dst_p);
1717 
1718  replaced_dst_count++;
1719  }
1720 
1721  nl->delete_net(ep->get_net());
1722  }
1723  }
1724 
1725  if (!has_global_output && g->get_successors().empty())
1726  {
1727  to_delete.push_back(g);
1728  }
1729  }
1730 
1731  for (auto g : to_delete)
1732  {
1733  nl->delete_gate(g);
1734  }
1735 
1736  if (replaced_dst_count == 0)
1737  {
1738  break;
1739  }
1740 
1741  log_debug("netlist_preprocessing", "replaced {} destinations this with power/ground nets this iteration", replaced_dst_count);
1742  total_replaced_dst_count += replaced_dst_count;
1743  }
1744 
1745  log_info("netlist_preprocessing", "replaced {} destinations with power/ground nets in total", total_replaced_dst_count);
1746  return OK(total_replaced_dst_count);
1747  }
1748 
1749  Result<u32> remove_consecutive_inverters(Netlist* nl)
1750  {
1751  if (nl == nullptr)
1752  {
1753  return ERR("netlist is a nullptr");
1754  }
1755 
1756  std::set<Gate*> gates_to_delete;
1757  for (auto* inv_gate : nl->get_gates([](const Gate* g) { return g->get_type()->has_property(GateTypeProperty::c_inverter); }))
1758  {
1759  if (gates_to_delete.find(inv_gate) != gates_to_delete.end())
1760  {
1761  continue;
1762  }
1763 
1764  const auto& connection_endpoints = inv_gate->get_fan_in_endpoints();
1765  if (connection_endpoints.size() != 1)
1766  {
1767  log_warning("netlist_preprocessing", "could not handle gate '{}' with ID {} due to a fan-in size != 1", inv_gate->get_name(), inv_gate->get_id());
1768  continue;
1769  }
1770 
1771  auto* middle_fan_in_ep = connection_endpoints.front();
1772  auto* middle_net = middle_fan_in_ep->get_net();
1773  if (middle_net->get_sources().size() != 1)
1774  {
1775  log_warning("netlist_preprocessing", "could not handle gate '{}' with ID {} due to a number of predecessors != 1", inv_gate->get_name(), inv_gate->get_id());
1776  continue;
1777  }
1778  auto* pred_gate = middle_net->get_sources().front()->get_gate();
1779 
1780  if (pred_gate->get_type()->has_property(GateTypeProperty::c_inverter))
1781  {
1782  const auto& fan_in = pred_gate->get_fan_in_endpoints();
1783  if (fan_in.size() != 1)
1784  {
1785  log_warning("netlist_preprocessing", "could not handle gate '{}' with ID {} due to a fan-in size != 1", pred_gate->get_name(), pred_gate->get_id());
1786  continue;
1787  }
1788  if (pred_gate->get_fan_out_endpoints().size() != 1)
1789  {
1790  log_warning("netlist_preprocessing", "could not handle gate '{}' with ID {} due to a fan-out size != 1", pred_gate->get_name(), pred_gate->get_id());
1791  continue;
1792  }
1793  auto* in_net = fan_in.front()->get_net();
1794 
1795  const auto& fan_out = inv_gate->get_fan_out_endpoints();
1796  if (fan_out.size() != 1)
1797  {
1798  log_warning("netlist_preprocessing", "could not handle gate '{}' with ID {} due to a fan-out size != 1", inv_gate->get_name(), inv_gate->get_id());
1799  continue;
1800  }
1801  auto* out_net = fan_out.front()->get_net();
1802 
1803  for (auto* dst_ep : out_net->get_destinations())
1804  {
1805  auto* dst_pin = dst_ep->get_pin();
1806  auto* dst_gate = dst_ep->get_gate();
1807 
1808  out_net->remove_destination(dst_ep);
1809  in_net->add_destination(dst_gate, dst_pin);
1810  }
1811 
1812  middle_net->remove_destination(middle_fan_in_ep);
1813 
1814  if (middle_net->get_num_of_destinations() == 0)
1815  {
1816  nl->delete_net(middle_net);
1817  gates_to_delete.insert(pred_gate);
1818  }
1819 
1820  gates_to_delete.insert(inv_gate);
1821  }
1822  }
1823 
1824  u32 removed_ctr = 0;
1825  for (auto* g : gates_to_delete)
1826  {
1827  nl->delete_gate(g);
1828  removed_ctr++;
1829  }
1830 
1831  return OK(removed_ctr);
1832  }
1833 
1834  namespace
1835  {
1836  std::string generate_hex_truth_table_string(const std::vector<BooleanFunction::Value>& tt)
1837  {
1838  std::string tt_str = "";
1839 
1840  u32 acc = 0;
1841  for (u32 i = 0; i < tt.size(); i++)
1842  {
1843  const BooleanFunction::Value bit = tt.at(i);
1844  if (bit == BooleanFunction::Value::ONE)
1845  {
1846  acc += (1 << (i % 4));
1847  }
1848 
1849  if ((i % 4) == 3)
1850  {
1851  std::stringstream stream;
1852  stream << std::hex << acc;
1853 
1854  tt_str = stream.str() + tt_str;
1855 
1856  acc = 0;
1857  }
1858  }
1859 
1860  return tt_str;
1861  }
1862  } // namespace
1863 
1864  Result<u32> simplify_lut_inits(Netlist* nl)
1865  {
1866  u32 num_inits = 0;
1867 
1868  for (auto g : nl->get_gates([](const auto& g) { return g->get_type()->has_property(GateTypeProperty::c_lut); }))
1869  {
1870  auto res = g->get_init_data();
1871  if (res.is_error())
1872  {
1873  return ERR_APPEND(res.get_error(),
1874  "unable to simplify lut init string for gate " + g->get_name() + " with ID " + std::to_string(g->get_id()) + ": failed to get original INIT string");
1875  }
1876 
1877  const auto original_inits = res.get();
1878 
1879  if (original_inits.size() != 1)
1880  {
1881  return ERR("unable to simplify lut init string for gate " + g->get_name() + " with ID " + std::to_string(g->get_id()) + ": found " + std::to_string(original_inits.size())
1882  + " init data strings but expected exactly 1.");
1883  }
1884 
1885  const auto original_init = original_inits.front();
1886 
1887  // skip if the gate type has more than one fan out endpoints
1888  if (g->get_type()->get_output_pins().size() != 1)
1889  {
1890  continue;
1891  }
1892 
1893  const auto out_ep = g->get_fan_out_endpoints().front();
1894 
1895  // skip if the gate has more than one boolean function
1896  if (g->get_boolean_functions().size() != 1)
1897  {
1898  continue;
1899  }
1900 
1901  const auto bf_org = g->get_boolean_function(out_ep->get_pin());
1902  const auto org_vars = bf_org.get_variable_names();
1903 
1904  const auto bf_replaced_res = BooleanFunctionDecorator(bf_org).substitute_power_ground_pins(g);
1905  if (bf_replaced_res.is_error())
1906  {
1907  return ERR_APPEND(bf_replaced_res.get_error(),
1908  "cannot simplify LUT inits: failed to replace power and ground pins for gate " + g->get_name() + " with ID " + std::to_string(g->get_id()));
1909  }
1910  const auto bf_replaced = bf_replaced_res.get();
1911  const auto bf_simplified = bf_replaced.simplify_local();
1912 
1913  const auto new_vars = bf_simplified.get_variable_names();
1914 
1915  if (org_vars.size() == new_vars.size())
1916  {
1917  continue;
1918  }
1919 
1920  auto bf_extended = bf_simplified.clone();
1921  for (const auto& in_pin : g->get_type()->get_input_pin_names())
1922  {
1923  if (new_vars.find(in_pin) == new_vars.end())
1924  {
1925  auto bf_filler = BooleanFunction::Var(in_pin) | (~BooleanFunction::Var(in_pin));
1926  bf_extended = BooleanFunction::And(std::move(bf_extended), std::move(bf_filler), 1).get();
1927  }
1928  }
1929 
1930  const auto tt = bf_extended.compute_truth_table().get();
1931  const auto new_init_string = generate_hex_truth_table_string(tt.front());
1932 
1933  // std::cout << "Org Init: " << g->get_init_data().get().front() << std::endl;
1934  // std::cout << "New Init: " << new_init_string << std::endl;
1935 
1936  g->set_init_data({new_init_string}).get();
1937  g->set_data("preprocessing_information", "original_init", "string", original_init);
1938 
1939  // const auto bf_test = g->get_boolean_function(out_ep->get_pin());
1940 
1941  // std::cout << "Org: " << bf_org << std::endl;
1942  // std::cout << "Rep: " << bf_replaced << std::endl;
1943  // std::cout << "Simp: " << bf_simplified << std::endl;
1944  // std::cout << "Test: " << bf_test << std::endl;
1945  // std::cout << "Ext: " << bf_extended << std::endl;
1946 
1947  num_inits++;
1948  }
1949 
1950  log_info("netlist_preprocessing", "simplified {} LUT INIT strings inside of netlist with ID {}.", num_inits, nl->get_id());
1951  return OK(num_inits);
1952  }
1953 
1954  namespace
1955  {
1956  struct indexed_identifier
1957  {
1958  indexed_identifier(const std::string& p_identifier, const u32 p_index, const std::string& p_origin) : identifier{p_identifier}, index{p_index}, origin{p_origin}
1959  {
1960  }
1961 
1962  std::string identifier;
1963  u32 index;
1964  std::string origin;
1965  };
1966 
1967  // TODO when the verilog parser changes are merged into the master this will no longer be needed
1968  const std::string hal_instance_index_pattern = "__\\[(\\d+)\\]__";
1969  const std::string hal_instance_index_pattern_reverse = "<HAL>(\\d+)<HAL>";
1970 
1971  std::string replace_hal_instance_index(const std::string& name)
1972  {
1973  std::regex re(hal_instance_index_pattern);
1974 
1975  std::string input = name;
1976  std::string index;
1977  std::smatch match;
1978  while (std::regex_search(input, match, re))
1979  {
1980  index = match[1];
1981  input = utils::replace(input, match.str(), "<HAL>" + index + "<HAL>");
1982  }
1983 
1984  return input;
1985  }
1986 
1987  std::string reconstruct_hal_instance_index(const std::string& name)
1988  {
1989  std::regex re(hal_instance_index_pattern_reverse);
1990 
1991  std::string input = name;
1992  std::string index;
1993  std::smatch match;
1994  while (std::regex_search(input, match, re))
1995  {
1996  index = match[1];
1997  input = utils::replace(input, match.str(), "__[" + index + "]__");
1998  }
1999 
2000  return input;
2001  }
2002 
2003  const std::string net_index_pattern = "\\((\\d+)\\)";
2004  const std::string gate_index_pattern = "\\[(\\d+)\\]";
2005 
2006  // Extracts an index from a string by taking the last integer enclosed by parentheses
2007  std::optional<indexed_identifier> extract_index(const std::string& name, const std::string& index_pattern, const std::string& origin)
2008  {
2009  std::regex re(index_pattern);
2010 
2011  std::string input = name;
2012  std::optional<std::string> last_match;
2013  std::optional<u32> last_index;
2014 
2015  // Search for last match within string
2016  std::smatch match;
2017  while (std::regex_search(input, match, re))
2018  {
2019  // Capture integer and update input string to search from after the match
2020  last_index = std::stoi(match[1]);
2021  last_match = match.str();
2022  input = match.suffix().str();
2023  }
2024 
2025  if (!last_index.has_value())
2026  {
2027  return std::nullopt;
2028  }
2029 
2030  const auto found_match = last_match.value();
2031  auto identifier_name = name;
2032  identifier_name = identifier_name.replace(name.rfind(found_match), found_match.size(), "");
2033 
2034  return std::optional<indexed_identifier>{{identifier_name, last_index.value(), origin}};
2035  }
2036 
2037  // annotate all found identifiers to a gate
2038  bool annotate_indexed_identifiers(Gate* gate, const std::vector<indexed_identifier>& identifiers)
2039  {
2040  std::string json_identifier_str =
2041  "[" + utils::join(", ", identifiers, [](const auto& i) { return std::string("[") + '"' + i.identifier + '"' + ", " + std::to_string(i.index) + ", " + '"' + i.origin + '"' + "]"; })
2042  + "]";
2043 
2044  return gate->set_data("preprocessing_information", "multi_bit_indexed_identifiers", "string", json_identifier_str);
2045  }
2046 
2047  // search for a net that connects to the gate at a pin of a specific type and tries to reconstruct an indexed identifier from its name or form a name of its merged wires
2048  std::vector<indexed_identifier> check_net_at_pin(const PinType pin_type, Gate* gate)
2049  {
2050  const auto typed_pins = gate->get_type()->get_pins([pin_type](const auto p) { return p->get_type() == pin_type; });
2051 
2052  std::vector<indexed_identifier> found_identfiers;
2053 
2054  for (const auto& pin : typed_pins)
2055  {
2056  const auto typed_net = (pin->get_direction() == PinDirection::output) ? gate->get_fan_out_net(pin) : gate->get_fan_in_net(pin);
2057 
2058  // 0) make sure pin is connected to net
2059  if (! typed_net)
2060  {
2061  continue;
2062  }
2063 
2064  // 1) search the net name itself
2065  const auto net_name_index = extract_index(typed_net->get_name(), net_index_pattern, "net_name");
2066  if (net_name_index.has_value())
2067  {
2068  found_identfiers.push_back(net_name_index.value());
2069  }
2070 
2071  // 2) search all the names of the wires that where merged into this net
2072  if (!typed_net->has_data("parser_annotation", "merged_nets"))
2073  {
2074  continue;
2075  }
2076 
2077  const auto all_merged_nets_str = std::get<1>(typed_net->get_data("parser_annotation", "merged_nets"));
2078 
2079  if (all_merged_nets_str.empty())
2080  {
2081  continue;
2082  }
2083 
2084  // parse json list of merged net names
2085  rapidjson::Document doc;
2086  doc.Parse(all_merged_nets_str.c_str());
2087 
2088  for (u32 i = 0; i < doc.GetArray().Size(); i++)
2089  {
2090  const auto list = doc[i].GetArray();
2091  for (u32 j = 0; j < list.Size(); j++)
2092  {
2093  const auto merged_wire_name = list[j].GetString();
2094 
2095  const auto merged_wire_name_index = extract_index(merged_wire_name, net_index_pattern, "net_name");
2096  if (merged_wire_name_index.has_value())
2097  {
2098  found_identfiers.push_back(merged_wire_name_index.value());
2099  }
2100  }
2101  }
2102  }
2103 
2104  return found_identfiers;
2105  }
2106  } // namespace
2107 
2108  Result<u32> reconstruct_indexed_ff_identifiers(Netlist* nl)
2109  {
2110  u32 counter = 0;
2111  for (auto& ff : nl->get_gates([](const auto g) { return g->get_type()->has_property(GateTypeProperty::ff); }))
2112  {
2113  std::vector<indexed_identifier> all_identifiers;
2114 
2115  // 1) Check whether the ff gate already has an index annotated in its gate name
2116  const auto cleaned_gate_name = replace_hal_instance_index(ff->get_name());
2117  const auto gate_name_index = extract_index(cleaned_gate_name, gate_index_pattern, "gate_name");
2118 
2119  if (gate_name_index.has_value())
2120  {
2121  auto found_identifier = gate_name_index.value();
2122  found_identifier.identifier = reconstruct_hal_instance_index(found_identifier.identifier);
2123  all_identifiers.push_back(found_identifier);
2124  }
2125 
2126  static const std::vector<PinType> relevant_pin_types = {PinType::state, PinType::neg_state, PinType::data};
2127 
2128  // 2) Check all relevant pin_types
2129  for (const auto& pt : relevant_pin_types)
2130  {
2131  const auto found_identifiers = check_net_at_pin(pt, ff);
2132  all_identifiers.insert(all_identifiers.end(), found_identifiers.begin(), found_identifiers.end());
2133  }
2134 
2135  if (!all_identifiers.empty())
2136  {
2137  counter++;
2138  }
2139 
2140  annotate_indexed_identifiers(ff, all_identifiers);
2141  }
2142 
2143  return OK(counter);
2144  }
2145 
2146  Result<u32> reconstruct_top_module_pin_groups(Netlist* nl)
2147  {
2148  std::map<std::string, std::map<u32, std::vector<ModulePin*>>> pg_name_to_indexed_pins;
2149 
2150  for (const auto& pin : nl->get_top_module()->get_pins())
2151  {
2152  auto reconstruct = extract_index(pin->get_name(), net_index_pattern, "");
2153  if (!reconstruct.has_value())
2154  {
2155  continue;
2156  }
2157 
2158  auto [pg_name, index, _] = reconstruct.value();
2159 
2160  pg_name_to_indexed_pins[pg_name][index].push_back(pin);
2161  }
2162 
2163  u32 reconstructed_counter = 0;
2164  for (const auto& [pg_name, indexed_pins] : pg_name_to_indexed_pins)
2165  {
2166  std::vector<ModulePin*> ordered_pins;
2167 
2168  bool valid_indices = true;
2169  // NOTE: since the map already orders the indices from low to high, if we iterate over it we also get the pins in the right order
2170  for (const auto& [_index, pins] : indexed_pins)
2171  {
2172  if (pins.size() > 1)
2173  {
2174  valid_indices = false;
2175  break;
2176  }
2177 
2178  ordered_pins.push_back(pins.front());
2179  }
2180 
2181  if (!valid_indices)
2182  {
2183  continue;
2184  }
2185 
2186  auto res = nl->get_top_module()->create_pin_group(pg_name, ordered_pins);
2187  if (res.is_error())
2188  {
2189  return ERR_APPEND(res.get_error(), "cannot reconstruct top module pin groups: failed to create pin group " + pg_name);
2190  }
2191 
2192  reconstructed_counter++;
2193  }
2194 
2195  return OK(reconstructed_counter);
2196  }
2197 
2198  namespace
2199  {
2200  struct ComponentData
2201  {
2202  std::string name;
2203  std::string type;
2204  u64 x;
2205  u64 y;
2206  };
2207 
2208  TokenStream<std::string> tokenize(std::stringstream& ss)
2209  {
2210  const std::string delimiters = " ;-";
2211  std::string current_token;
2212  u32 line_number = 0;
2213 
2214  std::string line;
2215  bool escaped = false;
2216 
2217  std::vector<Token<std::string>> parsed_tokens;
2218  while (std::getline(ss, line))
2219  {
2220  line_number++;
2221 
2222  for (char c : line)
2223  {
2224  // deal with escaping and strings
2225  if (c == '\\')
2226  {
2227  escaped = true;
2228  continue;
2229  }
2230  else if (escaped && std::isspace(c))
2231  {
2232  escaped = false;
2233  continue;
2234  }
2235 
2236  if (((!std::isspace(c) && delimiters.find(c) == std::string::npos) || escaped))
2237  {
2238  current_token += c;
2239  }
2240  else
2241  {
2242  if (!current_token.empty())
2243  {
2244  parsed_tokens.emplace_back(line_number, current_token);
2245  current_token.clear();
2246  }
2247 
2248  if (!std::isspace(c))
2249  {
2250  parsed_tokens.emplace_back(line_number, std::string(1, c));
2251  }
2252  }
2253  }
2254 
2255  if (!current_token.empty())
2256  {
2257  parsed_tokens.emplace_back(line_number, current_token);
2258  current_token.clear();
2259  }
2260  }
2261 
2262  return TokenStream(parsed_tokens, {}, {});
2263  }
2264 
2265  Result<std::unordered_map<std::string, ComponentData>> parse_tokens(TokenStream<std::string>& ts)
2266  {
2267  ts.consume_until("COMPONENTS");
2268  ts.consume("COMPONENTS");
2269  const auto component_count_str = ts.consume().string;
2270  ts.consume(";");
2271 
2272  u32 component_count;
2273  if (const auto res = utils::wrapped_stoul(component_count_str); res.is_ok())
2274  {
2275  component_count = res.get();
2276  }
2277  else
2278  {
2279  return ERR_APPEND(res.get_error(), "could not parse tokens: failed to read component count from token" + component_count_str);
2280  }
2281 
2282  std::cout << "Component count: " << component_count << std::endl;
2283 
2284  std::unordered_map<std::string, ComponentData> component_data;
2285  for (u32 c_idx = 0; c_idx < component_count; c_idx++)
2286  {
2287  // parse a line
2288  ComponentData new_data_entry;
2289  ts.consume("-");
2290  new_data_entry.name = ts.consume().string;
2291  new_data_entry.type = ts.consume().string;
2292  ts.consume("+");
2293  ts.consume("SOURCE");
2294  ts.consume("DIST");
2295  ts.consume("TIMING");
2296  ts.consume("+");
2297  ts.consume("PLACED");
2298  ts.consume("FIXED");
2299  ts.consume("(");
2300 
2301  if (const auto res = utils::wrapped_stoull(ts.consume().string); res.is_ok())
2302  {
2303  new_data_entry.x = res.get();
2304  }
2305  else
2306  {
2307  return ERR_APPEND(res.get_error(), "could not parse tokens: failed to read x coordinate from token");
2308  }
2309 
2310  if (const auto res = utils::wrapped_stoull(ts.consume().string); res.is_ok())
2311  {
2312  new_data_entry.y = res.get();
2313  }
2314  else
2315  {
2316  return ERR_APPEND(res.get_error(), "could not parse tokens: failed to read y coordinate from token");
2317  }
2318 
2319  ts.consume(")");
2320 
2321  ts.consume_current_line();
2322 
2323  component_data.insert({new_data_entry.name, new_data_entry});
2324  }
2325 
2326  return OK(component_data);
2327  }
2328  } // namespace
2329 
2330  Result<std::monostate> parse_def_file(Netlist* nl, const std::filesystem::path& def_file)
2331  {
2332  std::stringstream ss;
2333  std::ifstream ifs;
2334  ifs.open(def_file.string(), std::ifstream::in);
2335  if (!ifs.is_open())
2336  {
2337  return ERR("could not parse DEF (Design Exchange Format) file '" + def_file.string() + "' : unable to open file");
2338  }
2339  ss << ifs.rdbuf();
2340  ifs.close();
2341 
2342  auto ts = tokenize(ss);
2343 
2344  std::unordered_map<std::string, ComponentData> component_data;
2345  // parse tokens
2346  try
2347  {
2348  if (auto res = parse_tokens(ts); res.is_error())
2349  {
2350  return ERR_APPEND(res.get_error(), "could not parse Design Exchange Format file '" + def_file.string() + "': unable to parse tokens");
2351  }
2352  else
2353  {
2354  component_data = res.get();
2355  }
2356  }
2357  catch (TokenStream<std::string>::TokenStreamException& e)
2358  {
2359  if (e.line_number != (u32)-1)
2360  {
2361  return ERR("could not parse Design Exchange Format file '" + def_file.string() + "': " + e.message + " (line " + std::to_string(e.line_number) + ")");
2362  }
2363  else
2364  {
2365  return ERR("could not parse Design Exchange Format file '" + def_file.string() + "': " + e.message);
2366  }
2367  }
2368 
2369  std::unordered_map<std::string, Gate*> name_to_gate;
2370  for (auto g : nl->get_gates())
2371  {
2372  name_to_gate.insert({g->get_name(), g});
2373  }
2374 
2375  u32 counter = 0;
2376  for (const auto& [gate_name, data] : component_data)
2377  {
2378  if (const auto& g_it = name_to_gate.find(gate_name); g_it != name_to_gate.end())
2379  {
2380  // TODO figure out whereever we are saving coordinates now...
2381  g_it->second->set_location_x(data.x);
2382  g_it->second->set_location_y(data.y);
2383 
2384  counter++;
2385  }
2386  }
2387 
2388  log_info("netlist_preprocessing", "reconstructed coordinates for {} / {} ({:.2}) gates", counter, nl->get_gates().size(), (double)counter / (double)nl->get_gates().size());
2389 
2390  return OK({});
2391  }
2392 
2393  Result<std::vector<Module*>> create_multi_bit_gate_modules(Netlist* nl, const std::map<std::string, std::map<std::string, std::vector<std::string>>>& concatenated_pin_groups)
2394  {
2395  std::vector<Module*> all_modules;
2396  for (const auto& [gt_name, pin_groups] : concatenated_pin_groups)
2397  {
2398  const auto& gt = nl->get_gate_library()->get_gate_type_by_name(gt_name);
2399  if (gt == nullptr)
2400  {
2401  return ERR("unable to create multi bit gate module for gate type " + gt_name + ": failed to find gate type with that name in gate library " + nl->get_gate_library()->get_name());
2402  }
2403 
2404  for (const auto& g : nl->get_gates([&gt](const auto& g) { return g->get_type() == gt; }))
2405  {
2406  auto m = nl->create_module("module_" + g->get_name(), g->get_module(), {g});
2407 
2408  for (const auto& [module_pg_name, gate_pg_names] : pin_groups)
2409  {
2410  std::vector<ModulePin*> module_pins;
2411  for (const auto& gate_pg_name : gate_pg_names)
2412  {
2413  const auto& gate_pg = g->get_type()->get_pin_group_by_name(gate_pg_name);
2414 
2415  if (gate_pg == nullptr)
2416  {
2417  return ERR("unable to create multi-bit gate module for gate type " + gt_name + " and pin group " + gate_pg_name + ": failed to find pin group with that name");
2418  }
2419 
2420  std::vector<GatePin*> pin_list = gate_pg->get_pins();
2421  if (!gate_pg->is_ascending())
2422  {
2423  std::reverse(pin_list.begin(), pin_list.end());
2424  }
2425 
2426  for (const auto& gate_pin : pin_list)
2427  {
2428  const auto net = (gate_pin->get_direction() == PinDirection::output) ? g->get_fan_out_net(gate_pin) : g->get_fan_in_net(gate_pin);
2429  if (net == nullptr)
2430  {
2431  continue;
2432  }
2433 
2434  if (net->is_gnd_net() || net->is_vcc_net())
2435  {
2436  continue;
2437  }
2438 
2439  const auto module_pin = m->get_pin_by_net(net);
2440 
2441  module_pins.push_back(module_pin);
2442  }
2443  }
2444 
2445  m->create_pin_group(module_pg_name, module_pins);
2446  u32 idx_counter = 0;
2447  for (const auto& mp : module_pins)
2448  {
2449  m->set_pin_name(mp, module_pg_name + "_" + std::to_string(idx_counter));
2450  idx_counter++;
2451  }
2452  }
2453 
2454  all_modules.push_back(m);
2455  }
2456  }
2457 
2458  return OK(all_modules);
2459  }
2460 
2461  Result<std::vector<Net*>> create_nets_at_unconnected_pins(Netlist* nl)
2462  {
2463  std::vector<Net*> created_nets;
2464 
2465  for (const auto& g : nl->get_gates())
2466  {
2467  for (const auto& p : g->get_type()->get_output_pins())
2468  {
2469  if (g->get_fan_out_net(p) == nullptr)
2470  {
2471  auto new_net = nl->create_net("TEMP");
2472  new_net->set_name("HAL_UNCONNECTED_" + std::to_string(new_net->get_id()));
2473  new_net->add_source(g, p);
2474 
2475  created_nets.push_back(new_net);
2476  }
2477  }
2478  }
2479 
2480  return OK(created_nets);
2481  }
2482 
2483  Result<u32> unify_ff_outputs(Netlist* nl, const std::vector<Gate*>& ffs, GateType* inverter_type)
2484  {
2485  if (nl == nullptr)
2486  {
2487  return ERR("netlist is a nullptr");
2488  }
2489 
2490  if (inverter_type == nullptr)
2491  {
2492  const auto* gl = nl->get_gate_library();
2493  const auto inv_types =
2494  gl->get_gate_types([](const GateType* gt) { return gt->has_property(GateTypeProperty::c_inverter) && gt->get_input_pins().size() == 1 && gt->get_output_pins().size() == 1; });
2495  if (inv_types.empty())
2496  {
2497  return ERR("gate library '" + gl->get_name() + "' of netlist does not contain an inverter gate");
2498  }
2499  inverter_type = inv_types.begin()->second;
2500  }
2501  else
2502  {
2503  if (inverter_type->get_gate_library() != nl->get_gate_library())
2504  {
2505  return ERR("inverter gate type '" + inverter_type->get_name() + "' of gate library '" + inverter_type->get_gate_library()->get_name() + "' does not belong to gate library '"
2506  + nl->get_gate_library()->get_name() + "' of provided netlist");
2507  }
2508 
2509  if (!inverter_type->has_property(GateTypeProperty::c_inverter))
2510  {
2511  return ERR("gate type '" + inverter_type->get_name() + "' of gate library '" + inverter_type->get_gate_library()->get_name() + "' is not an inverter gate type");
2512  }
2513 
2514  if (inverter_type->get_input_pins().size() != 1 || inverter_type->get_output_pins().size() != 1)
2515  {
2516  return ERR("inverter gate type '" + inverter_type->get_name() + "' of gate library '" + inverter_type->get_gate_library()->get_name()
2517  + "' has an invalid number of input pins or output pins");
2518  }
2519  }
2520 
2521  auto inv_in_pin = inverter_type->get_input_pins().front();
2522  auto inv_out_pin = inverter_type->get_output_pins().front();
2523 
2524  u32 ctr = 0;
2525 
2526  const std::vector<Gate*>& gates = ffs.empty() ? nl->get_gates() : ffs;
2527 
2528  for (auto* ff : gates)
2529  {
2530  auto* ff_type = ff->get_type();
2531 
2532  if (!ff_type->has_property(GateTypeProperty::ff))
2533  {
2534  continue;
2535  }
2536 
2537  GatePin* state_pin = nullptr;
2538  GatePin* neg_state_pin = nullptr;
2539 
2540  for (auto* o_pin : ff_type->get_output_pins())
2541  {
2542  if (o_pin->get_type() == PinType::state)
2543  {
2544  state_pin = o_pin;
2545  }
2546  else if (o_pin->get_type() == PinType::neg_state)
2547  {
2548  neg_state_pin = o_pin;
2549  }
2550  }
2551 
2552  if (neg_state_pin == nullptr)
2553  {
2554  continue;
2555  }
2556 
2557  auto* neg_state_ep = ff->get_fan_out_endpoint(neg_state_pin);
2558  if (neg_state_ep == nullptr)
2559  {
2560  continue;
2561  }
2562  auto* neg_state_net = neg_state_ep->get_net();
2563 
2564  auto state_net = ff->get_fan_out_net(state_pin);
2565  if (state_net == nullptr)
2566  {
2567  state_net = nl->create_net(ff->get_name() + "__STATE_NET__");
2568  state_net->add_source(ff, state_pin);
2569  }
2570 
2571  auto* inv = nl->create_gate(inverter_type, ff->get_name() + "__NEG_STATE_INVERT__");
2572  state_net->add_destination(inv, inv_in_pin);
2573  neg_state_net->remove_source(neg_state_ep);
2574  neg_state_net->add_source(inv, inv_out_pin);
2575  ctr++;
2576  }
2577 
2578  return OK(ctr);
2579  }
2580  } // namespace netlist_preprocessing
2581 } // namespace hal
boolean_function_decorator.h
boolean_function_net_decorator.h
hal::BasePin::get_name
const std::string & get_name() const
Definition: base_pin.h:110
hal::BooleanFunctionDecorator::substitute_power_ground_nets
Result< BooleanFunction > substitute_power_ground_nets(const Netlist *nl) const
Definition: boolean_function_decorator.cpp:16
hal::BooleanFunctionDecorator::substitute_power_ground_pins
Result< BooleanFunction > substitute_power_ground_pins(const Gate *g) const
Definition: boolean_function_decorator.cpp:59
hal::BooleanFunction::Eq
static Result< BooleanFunction > Eq(BooleanFunction &&p0, BooleanFunction &&p1, u16 size)
Definition: boolean_function.cpp:549
hal::BooleanFunction::Var
static BooleanFunction Var(const std::string &name, u16 size=1)
Definition: boolean_function.cpp:251
hal::BooleanFunction::get_variable_name
Result< std::string > get_variable_name() const
Definition: boolean_function.cpp:767
hal::BooleanFunction::get_variable_names
std::set< std::string > get_variable_names() const
Definition: boolean_function.cpp:887
hal::BooleanFunction::Value
Value
represents the type of the node
Definition: boolean_function.h:74
hal::BooleanFunction::simplify_local
BooleanFunction simplify_local() const
Definition: boolean_function.cpp:1107
hal::BooleanFunction::Const
static BooleanFunction Const(const BooleanFunction::Value &value)
Definition: boolean_function.cpp:256
hal::BooleanFunction::Not
static Result< BooleanFunction > Not(BooleanFunction &&p0, u16 size)
Definition: boolean_function.cpp:305
hal::BooleanFunction::And
static Result< BooleanFunction > And(BooleanFunction &&p0, BooleanFunction &&p1, u16 size)
Definition: boolean_function.cpp:283
hal::BooleanFunctionNetDecorator::get_net_from
static Result< Net * > get_net_from(const Netlist *netlist, const BooleanFunction &var)
Definition: boolean_function_net_decorator.cpp:44
hal::Endpoint::get_net
Net * get_net() const
Definition: endpoint.cpp:33
hal::Endpoint::get_pin
GatePin * get_pin() const
Definition: endpoint.cpp:28
hal::Gate
Definition: gate.h:58
hal::Gate::get_type
GateType * get_type() const
Definition: gate.cpp:125
hal::Gate::get_resolved_boolean_function
Result< BooleanFunction > get_resolved_boolean_function(const GatePin *pin, const bool use_net_variables=false) const
Definition: gate.cpp:287
hal::Gate::get_successors
std::vector< Endpoint * > get_successors(const std::function< bool(const GatePin *pin, Endpoint *ep)> &filter=nullptr) const
Definition: gate.cpp:966
hal::Gate::get_name
const std::string & get_name() const
Definition: gate.cpp:105
hal::Gate::get_predecessor
Endpoint * get_predecessor(const std::string &pin_name) const
Definition: gate.cpp:938
hal::Gate::get_successor
Endpoint * get_successor(const std::string &pin_name) const
Definition: gate.cpp:1018
hal::Gate::get_id
u32 get_id() const
Definition: gate.cpp:95
hal::GateLibrary::get_gate_types
std::unordered_map< std::string, GateType * > get_gate_types(const std::function< bool(const GateType *)> &filter=nullptr) const
Definition: gate_library.cpp:139
hal::GateLibrary::get_gate_type_by_name
GateType * get_gate_type_by_name(const std::string &name) const
Definition: gate_library.cpp:128
hal::GateLibrary::get_name
std::string get_name() const
Definition: gate_library.cpp:13
hal::GateType::get_input_pin_names
std::vector< std::string > get_input_pin_names() const
Definition: gate_type.cpp:277
hal::GateType::get_gate_library
GateLibrary * get_gate_library() const
Definition: gate_type.cpp:106
hal::GateType::get_output_pins
std::vector< GatePin * > get_output_pins() const
Definition: gate_type.cpp:285
hal::GateType::get_name
const std::string & get_name() const
Definition: gate_type.cpp:64
hal::GateType::has_property
bool has_property(GateTypeProperty property) const
Definition: gate_type.cpp:101
hal::GateType::get_input_pins
std::vector< GatePin * > get_input_pins() const
Definition: gate_type.cpp:269
hal::GateType::get_boolean_functions
const std::unordered_map< std::string, BooleanFunction > & get_boolean_functions() const
Definition: gate_type.cpp:746
hal::GateType::get_pins
std::vector< GatePin * > get_pins(const std::function< bool(GatePin *)> &filter=nullptr) const
Definition: gate_type.cpp:210
hal::Module::get_pins
std::vector< ModulePin * > get_pins(const std::function< bool(ModulePin *)> &filter=nullptr) const
Definition: module.cpp:873
hal::Module::create_pin_group
Result< PinGroup< ModulePin > * > create_pin_group(const u32 id, const std::string &name, const std::vector< ModulePin * > pins={}, PinDirection direction=PinDirection::none, PinType type=PinType::none, bool ascending=true, u32 start_index=0, bool delete_empty_groups=true, bool force_name=false)
Definition: module.cpp:1253
hal::Module::get_type
std::string get_type() const
Definition: module.cpp:106
hal::Net
Definition: net.h:58
hal::Net::get_id
u32 get_id() const
Definition: net.cpp:88
hal::Net::add_destination
Endpoint * add_destination(Gate *gate, const std::string &pin_name)
Definition: net.cpp:300
hal::Net::remove_source
bool remove_source(Gate *gate, const std::string &pin_name)
Definition: net.cpp:169
hal::Net::set_name
void set_name(const std::string &name)
Definition: net.cpp:103
hal::Net::add_source
Endpoint * add_source(Gate *gate, const std::string &pin_name)
Definition: net.cpp:127
hal::Net::get_name
const std::string & get_name() const
Definition: net.cpp:98
hal::Net::get_destinations
std::vector< Endpoint * > get_destinations(const std::function< bool(Endpoint *ep)> &filter=nullptr) const
Definition: net.cpp:450
hal::Net::remove_destination
bool remove_destination(Gate *gate, const std::string &pin_name)
Definition: net.cpp:343
hal::Netlist::get_top_module
Module * get_top_module() const
Definition: netlist.cpp:608
hal::Netlist::get_gates
const std::vector< Gate * > & get_gates() const
Definition: netlist.cpp:204
hal::Netlist::delete_net
bool delete_net(Net *net)
Definition: netlist.cpp:343
hal::Netlist::create_net
Net * create_net(const u32 net_id, const std::string &name)
Definition: netlist.cpp:333
hal::Netlist::get_gnd_gates
const std::vector< Gate * > & get_gnd_gates() const
Definition: netlist.cpp:309
hal::Netlist::get_vcc_gates
const std::vector< Gate * > & get_vcc_gates() const
Definition: netlist.cpp:304
hal::Netlist::delete_gate
bool delete_gate(Gate *gate)
Definition: netlist.cpp:183
hal::Netlist::get_id
u32 get_id() const
Definition: netlist.cpp:75
hal::Netlist::create_gate
Gate * create_gate(const u32 gate_id, GateType *gate_type, const std::string &name="", i32 x=-1, i32 y=-1)
Definition: netlist.cpp:173
hal::Netlist::get_nets
const std::vector< Net * > & get_nets() const
Definition: netlist.cpp:364
hal::Netlist::get_gate_library
const GateLibrary * get_gate_library() const
Definition: netlist.cpp:132
hal::Netlist::create_module
Module * create_module(const u32 module_id, const std::string &name, Module *parent, const std::vector< Gate * > &gates={})
Definition: netlist.cpp:587
hal::NetlistModificationDecorator::connect_nets
Result< Net * > connect_nets(Net *master_net, Net *slave_net)
Definition: netlist_modification_decorator.cpp:192
hal::SubgraphNetlistDecorator::get_subgraph_function_inputs
Result< std::set< const Net * > > get_subgraph_function_inputs(const std::vector< const Gate * > &subgraph_gates, const Net *subgraph_output) const
Definition: subgraph_netlist_decorator.cpp:481
hal::SubgraphNetlistDecorator::get_subgraph_function
Result< BooleanFunction > get_subgraph_function(const std::vector< const Gate * > &subgraph_gates, const Net *subgraph_output, std::map< std::pair< u32, const GatePin * >, BooleanFunction > &cache) const
Definition: subgraph_netlist_decorator.cpp:371
u64
uint64_t u64
Definition: defines.h:42
u32
uint32_t u32
Definition: defines.h:41
i64
int64_t i64
Definition: defines.h:37
u8
uint8_t u8
Definition: defines.h:39
gate_library_manager.h
log_debug
#define log_debug(channel,...)
Definition: log.h:74
log_info
#define log_info(channel,...)
Definition: log.h:70
log_warning
#define log_warning(channel,...)
Definition: log.h:76
netlist.h
ERR
#define ERR(message)
Definition: result.h:60
OK
#define OK(...)
Definition: result.h:56
ERR_APPEND
#define ERR_APPEND(prev_error, message)
Definition: result.h:64
hal::gate_library_manager::save
bool save(std::filesystem::path file_path, GateLibrary *gate_lib, bool overwrite=false)
Definition: gate_library_manager.cpp:147
hal::gate_library_parser_manager::parse
std::unique_ptr< GateLibrary > parse(std::filesystem::path file_path)
Definition: gate_library_parser_manager.cpp:77
hal::netlist_preprocessing::remove_unconnected_gates
Result< u32 > remove_unconnected_gates(Netlist *nl)
Definition: netlist_preprocessing.cpp:1024
hal::netlist_preprocessing::parse_def_file
Result< std::monostate > parse_def_file(Netlist *nl, const std::filesystem::path &def_file)
Definition: netlist_preprocessing.cpp:2330
hal::netlist_preprocessing::manual_mux_optimizations
Result< u32 > manual_mux_optimizations(Netlist *nl, GateLibrary *mux_inv_gl)
Definition: netlist_preprocessing.cpp:1599
hal::netlist_preprocessing::simplify_lut_inits
Result< u32 > simplify_lut_inits(Netlist *nl)
Definition: netlist_preprocessing.cpp:1864
hal::netlist_preprocessing::create_nets_at_unconnected_pins
Result< std::vector< Net * > > create_nets_at_unconnected_pins(Netlist *nl)
Definition: netlist_preprocessing.cpp:2461
hal::netlist_preprocessing::remove_redundant_loops
Result< u32 > remove_redundant_loops(Netlist *nl)
Definition: netlist_preprocessing.cpp:622
hal::netlist_preprocessing::remove_redundant_logic_trees
Result< u32 > remove_redundant_logic_trees(Netlist *nl)
Definition: netlist_preprocessing.cpp:886
hal::netlist_preprocessing::reconstruct_top_module_pin_groups
Result< u32 > reconstruct_top_module_pin_groups(Netlist *nl)
Definition: netlist_preprocessing.cpp:2146
hal::netlist_preprocessing::remove_redundant_gates
Result< u32 > remove_redundant_gates(Netlist *nl, const std::function< bool(const Gate *)> &filter=nullptr)
Definition: netlist_preprocessing.cpp:379
hal::netlist_preprocessing::remove_buffers
Result< u32 > remove_buffers(Netlist *nl)
Definition: netlist_preprocessing.cpp:94
hal::netlist_preprocessing::propagate_constants
Result< u32 > propagate_constants(Netlist *nl)
Definition: netlist_preprocessing.cpp:1637
hal::netlist_preprocessing::remove_unused_lut_inputs
Result< u32 > remove_unused_lut_inputs(Netlist *nl)
Definition: netlist_preprocessing.cpp:27
hal::netlist_preprocessing::remove_unconnected_looped
Result< u32 > remove_unconnected_looped(Netlist *nl)
Definition: netlist_preprocessing.cpp:1096
hal::netlist_preprocessing::remove_unconnected_nets
Result< u32 > remove_unconnected_nets(Netlist *nl)
Definition: netlist_preprocessing.cpp:1066
hal::netlist_preprocessing::reconstruct_indexed_ff_identifiers
Result< u32 > reconstruct_indexed_ff_identifiers(Netlist *nl)
Definition: netlist_preprocessing.cpp:2108
hal::netlist_preprocessing::remove_consecutive_inverters
Result< u32 > remove_consecutive_inverters(Netlist *nl)
Definition: netlist_preprocessing.cpp:1749
hal::netlist_preprocessing::create_multi_bit_gate_modules
Result< std::vector< Module * > > create_multi_bit_gate_modules(Netlist *nl, const std::map< std::string, std::map< std::string, std::vector< std::string >>> &concatenated_pin_groups)
Definition: netlist_preprocessing.cpp:2393
hal::netlist_preprocessing::unify_ff_outputs
Result< u32 > unify_ff_outputs(Netlist *nl, const std::vector< Gate * > &ffs={}, GateType *inverter_type=nullptr)
Definition: netlist_preprocessing.cpp:2483
hal::resynthesis::replace_subgraph_with_netlist
Result< std::monostate > replace_subgraph_with_netlist(const std::vector< Gate * > &subgraph, const std::unordered_map< Net *, std::vector< Net * >> &global_io_mapping, const Netlist *src_nl, Netlist *dst_nl, const bool delete_subgraph_gates)
Definition: resynthesis.cpp:1118
hal::resynthesis::generate_resynth_netlist_for_boolean_functions
Result< std::unique_ptr< Netlist > > generate_resynth_netlist_for_boolean_functions(const std::unordered_map< std::string, BooleanFunction > &bfs, const std::filesystem::path &genlib_path, GateLibrary *target_gl, const bool optimize_area)
Definition: resynthesis.cpp:1268
hal::utils::replace
T replace(const T &str, const T &search, const T &replace)
Definition: utils.h:384
hal::utils::wrapped_stoull
Result< u64 > wrapped_stoull(const std::string &s, const u32 base=10)
Definition: utils.cpp:696
hal::utils::wrapped_stoul
Result< u32 > wrapped_stoul(const std::string &s, const u32 base=10)
Definition: utils.cpp:714
hal::utils::join
std::string join(const std::string &joiner, const Iterator &begin, const Iterator &end, const Transform &transform)
Definition: utils.h:414
hal::utils::get_unique_temp_directory
Result< std::filesystem::path > get_unique_temp_directory(const std::string &prefix="", const u32 max_attempts=5)
Definition: utils.cpp:276
hal::z3_utils::compare_nets
Result< bool > compare_nets(const Netlist *netlist_a, const Netlist *netlist_b, const Net *net_a, const Net *net_b, const bool fail_on_unknown=true, const u32 solver_timeout=10)
Compare two nets from two different netlists.
Definition: netlist_comparison.cpp:363
hal
Definition: defines.h:45
hal::PinType
PinType
Definition: pin_type.h:36
pins
std::vector< PinInformation > pins
Definition: netlist_serializer.cpp:66
net
Net * net
Definition: netlist_serializer.cpp:57
netlist_comparison.h
netlist_modification_decorator.h
x
u64 x
Definition: netlist_preprocessing.cpp:2204
y
u64 y
Definition: netlist_preprocessing.cpp:2205
identifier
std::string identifier
Definition: netlist_preprocessing.cpp:1962
type
GateType * type
Definition: netlist_preprocessing.cpp:1240
origin
std::string origin
Definition: netlist_preprocessing.cpp:1964
name
std::string name
Definition: netlist_preprocessing.cpp:2202
inverters
std::set< GatePin * > inverters
Definition: netlist_preprocessing.cpp:1241
index
u32 index
Definition: netlist_preprocessing.cpp:1963
netlist_preprocessing.h
resynthesis.h
This file contains functions to decompose or re-synthesize combinational parts of a gate-level netlis...
subgraph_netlist_decorator.h
token_stream.h