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