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