HAL
pre_processing.cpp
Go to the documentation of this file.
1 #include "dataflow_analysis/pre_processing/pre_processing.h"
2 
3 #include "dataflow_analysis/api/configuration.h"
4 #include "dataflow_analysis/common/grouping.h"
5 #include "dataflow_analysis/common/netlist_abstraction.h"
6 #include "dataflow_analysis/pre_processing/register_stage_identification.h"
7 #include "dataflow_analysis/utils/parallel_for_each.h"
8 #include "dataflow_analysis/utils/progress_printer.h"
9 #include "dataflow_analysis/utils/timing_utils.h"
10 #include "hal_core/netlist/gate.h"
11 #include "hal_core/netlist/module.h"
12 #include "hal_core/netlist/net.h"
13 #include "hal_core/netlist/netlist.h"
14 #include "hal_core/netlist/netlist_utils.h"
15 #include "hal_core/utilities/log.h"
16 
17 #include <algorithm>
18 #include <chrono>
19 #include <deque>
20 #include <queue>
21 
22 namespace hal
23 {
24  namespace dataflow
25  {
26  namespace pre_processing
27  {
28  namespace
29  {
30  void identify_all_target_gates(const dataflow::Configuration& config, NetlistAbstraction& netlist_abstr)
31  {
32  log_info("dataflow", "identifying target gates");
33  netlist_abstr.target_gates = netlist_abstr.nl->get_gates([config](auto g) { return config.gate_types.find(g->get_type()) != config.gate_types.end(); });
34  std::sort(netlist_abstr.target_gates.begin(), netlist_abstr.target_gates.end(), [](const Gate* g1, const Gate* g2) { return g1->get_id() < g2->get_id(); });
35  log_info("dataflow", " #gates: {}", netlist_abstr.nl->get_gates().size());
36  log_info("dataflow", " #target gates: {}", netlist_abstr.target_gates.size());
37  }
38 
39  void identify_all_control_signals(const dataflow::Configuration& config, NetlistAbstraction& netlist_abstr)
40  {
41  auto begin_time = std::chrono::high_resolution_clock::now();
42  log_info("dataflow", "identifying control signals");
43  for (auto sg : netlist_abstr.target_gates)
44  {
45  std::vector<u32> fingerprint;
46  auto id = sg->get_id();
47 
48  for (auto type : config.control_pin_types)
49  {
50  for (auto net :
51  netlist_utils::get_nets_at_pins(sg, sg->get_type()->get_pins([type](const GatePin* p) { return p->get_direction() == PinDirection::input && p->get_type() == type; })))
52  {
53  netlist_abstr.gate_to_control_signals[id][type].insert(net->get_id());
54  fingerprint.push_back(net->get_id());
55  }
56  }
57 
58  netlist_abstr.gate_to_fingerprint[id] = fingerprint;
59  }
60 
61  log_info("dataflow", " done after {:3.2f}s", seconds_since(begin_time));
62  }
63 
64  void identify_known_groups(const dataflow::Configuration& config, NetlistAbstraction& netlist_abstr, std::vector<std::vector<Gate*>>& known_target_groups)
65  {
66  // for known gates, only check if they all match the target gate types; discard groups that do not
67  for (const auto& gates : config.known_gate_groups)
68  {
69  if (std::all_of(
70  gates.begin(), gates.end(), [&netlist_abstr](const Gate* g) { return netlist_abstr.gate_to_fingerprint.find(g->get_id()) != netlist_abstr.gate_to_fingerprint.end(); }))
71  {
72  known_target_groups.push_back(gates);
73  }
74  else
75  {
76  log_warning("dataflow",
77  "known group containing gate '{}' with ID {} contains gates that are not of the target gate type, known group will be ignored...",
78  gates.front()->get_name(),
79  gates.front()->get_id());
80  }
81  }
82  }
83 
84  /* get all successor/predecessor FFs of all FFs */
85  void identify_successors_predecessors(const dataflow::Configuration& config, NetlistAbstraction& netlist_abstr)
86  {
87  log_info("dataflow", "identifying successors and predecessors of sequential gates...");
88  measure_block_time("identifying successors and predecessors of sequential gates") ProgressPrinter progress_bar;
89  float cnt = 0;
90 
91  progress_bar.print_message_to_gui("dataflow: preprocessing …");
92 
93  // cache map of nets to group indices of known net groups
94  std::unordered_map<const Net*, u32> net_to_group_index;
95  for (u32 i = 0; i < config.known_net_groups.size(); i++)
96  {
97  const auto& net_group = config.known_net_groups.at(i);
98  if (net_group.size() < config.min_group_size)
99  {
100  continue;
101  }
102 
103  for (const auto* net : net_group)
104  {
105  net_to_group_index[net] = i;
106  }
107  }
108 
109  // find successors
110  std::unordered_map<const Net*, std::pair<std::unordered_set<Gate*>, std::unordered_set<u32>>> suc_cache;
111  std::unordered_map<const Net*, std::unordered_set<u32>> pred_cache;
112  for (const auto& gate : netlist_abstr.target_gates)
113  {
114  cnt++;
115  progress_bar.print_progress_to_stderr(cnt / netlist_abstr.target_gates.size());
116  progress_bar.print_progress_to_gui();
117 
118  // create sets even if there are no successors
119  if (netlist_abstr.gate_to_successors.find(gate->get_id()) == netlist_abstr.gate_to_successors.end())
120  {
121  netlist_abstr.gate_to_successors[gate->get_id()] = std::unordered_set<u32>();
122  }
123  if (netlist_abstr.gate_to_predecessors.find(gate->get_id()) == netlist_abstr.gate_to_predecessors.end())
124  {
125  netlist_abstr.gate_to_predecessors[gate->get_id()] = std::unordered_set<u32>();
126  }
127  if (netlist_abstr.gate_to_known_successor_groups.find(gate->get_id()) == netlist_abstr.gate_to_known_successor_groups.end())
128  {
129  netlist_abstr.gate_to_known_successor_groups[gate->get_id()] = std::unordered_set<u32>();
130  }
131  if (netlist_abstr.gate_to_known_predecessor_groups.find(gate->get_id()) == netlist_abstr.gate_to_known_predecessor_groups.end())
132  {
133  netlist_abstr.gate_to_known_predecessor_groups[gate->get_id()] = std::unordered_set<u32>();
134  }
135 
136  const auto& start_fan_out_nets = gate->get_fan_out_nets();
137  std::vector<const Net*> stack(start_fan_out_nets.cbegin(), start_fan_out_nets.cend()); // init stack with fan-out of start gate
138  std::unordered_set<const Net*> visited;
139  std::vector<const Net*> previous; // will keep track of all predecessor nets of the current net
140  while (!stack.empty())
141  {
142  const Net* current = stack.back(); // do not pop last item yet
143 
144  if (!previous.empty() && current == previous.back())
145  {
146  // will execute when coming back to a net along the path of predecessor nets (i.e., after finding a target gate or when unable to propagate further)
147  stack.pop_back();
148  previous.pop_back();
149  continue;
150  }
151 
152  visited.insert(current);
153 
154  if (const auto suc_cache_it = suc_cache.find(current); suc_cache_it != suc_cache.end())
155  {
156  auto& suc_cache_current = std::get<1>(*suc_cache_it);
157  const auto& suc_cached_gates = std::get<0>(suc_cache_current);
158  const auto& suc_cached_net_groups = std::get<1>(suc_cache_current);
159 
160  // add cached target gates and known successor net groups to suc_cache of all predecessor nets
161  for (const auto* n : previous)
162  {
163  auto& suc_cache_n = suc_cache[n];
164  std::get<0>(suc_cache_n).insert(suc_cached_gates.cbegin(), suc_cached_gates.cend());
165  std::get<1>(suc_cache_n).insert(suc_cached_net_groups.cbegin(), suc_cached_net_groups.cend());
166  }
167 
168  // add cached net groups to known successor net groups of current gate
169  netlist_abstr.gate_to_known_successor_groups[gate->get_id()].insert(suc_cached_net_groups.cbegin(), suc_cached_net_groups.cend());
170 
171  stack.pop_back();
172  }
173  else
174  {
175  if (const auto group_it = net_to_group_index.find(current); group_it != net_to_group_index.end())
176  {
177  std::get<1>(suc_cache[current]).insert(group_it->second);
178  for (const auto* n : previous)
179  {
180  std::get<1>(suc_cache[n]).insert(group_it->second);
181  }
182  netlist_abstr.gate_to_known_successor_groups[gate->get_id()].insert(group_it->second);
183  }
184 
185  bool added = false;
186  for (const auto* ep : current->get_destinations())
187  {
188  auto* g = ep->get_gate();
189  if (config.gate_types.find(g->get_type()) != config.gate_types.end())
190  {
191  // if target gate found, add to suc_cache of all nets along the predecessor path
192  auto& suc_cache_current = suc_cache[current];
193  std::get<0>(suc_cache_current).insert(g);
194  for (const auto* n : previous)
195  {
196  std::get<0>(suc_cache[n]).insert(g);
197  }
198  }
199  else
200  {
201  // propagate further by adding successors to stack
202  for (const auto* n : g->get_fan_out_nets())
203  {
204  if (visited.find(n) == visited.end())
205  {
206  stack.push_back(n);
207  added = true;
208  }
209  }
210  }
211  }
212 
213  if (added)
214  {
215  // keep track of previous net whenever propagating further
216  previous.push_back(current);
217  }
218  else
219  {
220  // if no change to stack, go back
221  stack.pop_back();
222  }
223  }
224  }
225 
226  const auto& start_fan_in_nets = gate->get_fan_in_nets();
227  stack = std::vector<const Net*>(start_fan_in_nets.begin(), start_fan_in_nets.end());
228  visited.clear();
229  previous.clear();
230  while (!stack.empty())
231  {
232  const Net* current = stack.back(); // do not pop last item yet
233 
234  if (!previous.empty() && current == previous.back())
235  {
236  // will execute when coming back to a net along the path of predecessor nets (i.e., after finding a target gate or when unable to propagate further)
237  stack.pop_back();
238  previous.pop_back();
239  continue;
240  }
241 
242  visited.insert(current);
243 
244  if (const auto pred_cache_it = pred_cache.find(current); pred_cache_it != pred_cache.end())
245  {
246  auto& pred_cached_net_groups = std::get<1>(*pred_cache_it);
247 
248  // add cached known predecessor net groups to cache of all predecessor nets
249  for (const auto* n : previous)
250  {
251  pred_cache[n].insert(pred_cached_net_groups.cbegin(), pred_cached_net_groups.cend());
252  }
253 
254  // add cached net groups to known predecessor net groups of current gate
255  netlist_abstr.gate_to_known_predecessor_groups[gate->get_id()].insert(pred_cached_net_groups.cbegin(), pred_cached_net_groups.cend());
256 
257  stack.pop_back();
258  }
259  else
260  {
261  if (const auto group_it = net_to_group_index.find(current); group_it != net_to_group_index.end())
262  {
263  pred_cache[current].insert(group_it->second);
264  for (const auto* n : previous)
265  {
266  pred_cache[n].insert(group_it->second);
267  }
268  netlist_abstr.gate_to_known_predecessor_groups[gate->get_id()].insert(group_it->second);
269  }
270 
271  bool added = false;
272  for (const auto* ep : current->get_sources())
273  {
274  auto* g = ep->get_gate();
275  if (config.gate_types.find(g->get_type()) == config.gate_types.end())
276  {
277  // propagate further by adding predecessors to stack
278  for (const auto* n : g->get_fan_in_nets())
279  {
280  if (visited.find(n) == visited.end())
281  {
282  stack.push_back(n);
283  added = true;
284  }
285  }
286  }
287  }
288 
289  if (added)
290  {
291  // keep track of previous net whenever propagating further
292  previous.push_back(current);
293  }
294  else
295  {
296  // if no change to stack, go back
297  stack.pop_back();
298  }
299  }
300  }
301 
302  // collect successor target gates by getting cache of all fan-out nets of start gate
303  std::unordered_set<Gate*> next_target_gates;
304  for (const auto* n : start_fan_out_nets)
305  {
306  if (const auto it = suc_cache.find(n); it != suc_cache.end())
307  {
308  const auto& cached_gates = std::get<0>(std::get<1>(*it));
309  next_target_gates.insert(cached_gates.cbegin(), cached_gates.cend());
310  }
311  }
312 
313  for (const auto& suc : next_target_gates)
314  {
315  netlist_abstr.gate_to_successors[gate->get_id()].insert(suc->get_id());
316  netlist_abstr.gate_to_predecessors[suc->get_id()].insert(gate->get_id());
317  }
318  }
319  progress_bar.clear();
320  }
321  } // namespace
322 
323  NetlistAbstraction run(const dataflow::Configuration& config, std::shared_ptr<dataflow::Grouping>& initial_grouping)
324  {
325  log_info("dataflow", "pre-processing netlist...");
326  measure_block_time("pre-processing");
327  NetlistAbstraction netlist_abstr(config.netlist);
328  std::vector<std::vector<Gate*>> known_target_groups;
329  std::vector<std::vector<Net*>> known_net_groups;
330  identify_all_target_gates(config, netlist_abstr);
331  identify_all_control_signals(config, netlist_abstr);
332  identify_known_groups(config, netlist_abstr, known_target_groups);
333  identify_successors_predecessors(config, netlist_abstr);
334 
335  if (config.enable_stages)
336  {
337  identify_register_stages(netlist_abstr);
338  }
339 
340  initial_grouping = std::make_shared<dataflow::Grouping>(netlist_abstr, known_target_groups);
341 
342  return netlist_abstr;
343  }
344  } // namespace pre_processing
345  } // namespace dataflow
346 } // namespace hal
configuration.h
This file contains the struct that holds all information on a dataflow analysis configuration.
hal::ItemType::Net
@ Net
log_info
#define log_info(channel,...)
Definition: log.h:70
log_warning
#define log_warning(channel,...)
Definition: log.h:76
netlist.h
hal::dataflow::pre_processing::identify_register_stages
void identify_register_stages(NetlistAbstraction &netlist_abstr)
Definition: register_stage_identification.cpp:24
hal::dataflow::pre_processing::run
NetlistAbstraction run(const dataflow::Configuration &config, std::shared_ptr< dataflow::Grouping > &initial_grouping)
Definition: pre_processing.cpp:323
hal::netlist_utils::get_nets_at_pins
std::vector< Net * > get_nets_at_pins(Gate *gate, std::vector< GatePin * > pins)
Definition: netlist_utils.cpp:571
test_plugin.g
g
Definition: test_plugin.py:32
test.n
n
Definition: test.py:6
u32
quint32 u32
Definition: net_layout_point.h:40
type
PinType type
Definition: netlist_serializer.cpp:59
net
Net * net
Definition: netlist_serializer.cpp:57
id
i32 id
Definition: netlist_serializer.cpp:56
netlist_abstraction.h
This file contains the struct that holds all information on the netlist abstraction used for dataflow...
netlist_utils.h
parallel_for_each.h
grouping.h
This file contains the class that holds all information of a dataflow analysis grouping.
pre_processing.h
progress_printer.h
register_stage_identification.h
hal::dataflow::Configuration
Configuration of a dataflow analysis run.
Definition: configuration.h:61
hal::dataflow::Configuration::enable_stages
bool enable_stages
Enable stage identification as part of dataflow analysis. Defaults to false.
Definition: configuration.h:107
hal::dataflow::Configuration::netlist
Netlist * netlist
The netlist to be analyzed.
Definition: configuration.h:72
hal::dataflow::NetlistAbstraction
The abstraction of the netlist that only contains gates of a specified type, e.g.,...
Definition: netlist_abstraction.h:56
timing_utils.h
measure_block_time
#define measure_block_time(X)
Definition: timing_utils.h:36
seconds_since
#define seconds_since(X)
Definition: timing_utils.h:38