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  // cache map of nets to group indices of known net groups
92  std::unordered_map<const Net*, u32> net_to_group_index;
93  for (u32 i = 0; i < config.known_net_groups.size(); i++)
94  {
95  const auto& net_group = config.known_net_groups.at(i);
96  if (net_group.size() < config.min_group_size)
97  {
98  continue;
99  }
100 
101  for (const auto* net : net_group)
102  {
103  net_to_group_index[net] = i;
104  }
105  }
106 
107  // find successors
108  std::unordered_map<const Net*, std::pair<std::unordered_set<Gate*>, std::unordered_set<u32>>> suc_cache;
109  std::unordered_map<const Net*, std::unordered_set<u32>> pred_cache;
110  for (const auto& gate : netlist_abstr.target_gates)
111  {
112  cnt++;
113  progress_bar.print_progress(cnt / netlist_abstr.target_gates.size());
114 
115  // create sets even if there are no successors
116  if (netlist_abstr.gate_to_successors.find(gate->get_id()) == netlist_abstr.gate_to_successors.end())
117  {
118  netlist_abstr.gate_to_successors[gate->get_id()] = std::unordered_set<u32>();
119  }
120  if (netlist_abstr.gate_to_predecessors.find(gate->get_id()) == netlist_abstr.gate_to_predecessors.end())
121  {
122  netlist_abstr.gate_to_predecessors[gate->get_id()] = std::unordered_set<u32>();
123  }
124  if (netlist_abstr.gate_to_known_successor_groups.find(gate->get_id()) == netlist_abstr.gate_to_known_successor_groups.end())
125  {
126  netlist_abstr.gate_to_known_successor_groups[gate->get_id()] = std::unordered_set<u32>();
127  }
128  if (netlist_abstr.gate_to_known_predecessor_groups.find(gate->get_id()) == netlist_abstr.gate_to_known_predecessor_groups.end())
129  {
130  netlist_abstr.gate_to_known_predecessor_groups[gate->get_id()] = std::unordered_set<u32>();
131  }
132 
133  const auto& start_fan_out_nets = gate->get_fan_out_nets();
134  std::vector<const Net*> stack(start_fan_out_nets.cbegin(), start_fan_out_nets.cend()); // init stack with fan-out of start gate
135  std::unordered_set<const Net*> visited;
136  std::vector<const Net*> previous; // will keep track of all predecessor nets of the current net
137  while (!stack.empty())
138  {
139  const Net* current = stack.back(); // do not pop last item yet
140 
141  if (!previous.empty() && current == previous.back())
142  {
143  // 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)
144  stack.pop_back();
145  previous.pop_back();
146  continue;
147  }
148 
149  visited.insert(current);
150 
151  if (const auto suc_cache_it = suc_cache.find(current); suc_cache_it != suc_cache.end())
152  {
153  auto& suc_cache_current = std::get<1>(*suc_cache_it);
154  const auto& suc_cached_gates = std::get<0>(suc_cache_current);
155  const auto& suc_cached_net_groups = std::get<1>(suc_cache_current);
156 
157  // add cached target gates and known successor net groups to suc_cache of all predecessor nets
158  for (const auto* n : previous)
159  {
160  auto& suc_cache_n = suc_cache[n];
161  std::get<0>(suc_cache_n).insert(suc_cached_gates.cbegin(), suc_cached_gates.cend());
162  std::get<1>(suc_cache_n).insert(suc_cached_net_groups.cbegin(), suc_cached_net_groups.cend());
163  }
164 
165  // add cached net groups to known successor net groups of current gate
166  netlist_abstr.gate_to_known_successor_groups[gate->get_id()].insert(suc_cached_net_groups.cbegin(), suc_cached_net_groups.cend());
167 
168  stack.pop_back();
169  }
170  else
171  {
172  if (const auto group_it = net_to_group_index.find(current); group_it != net_to_group_index.end())
173  {
174  std::get<1>(suc_cache[current]).insert(group_it->second);
175  for (const auto* n : previous)
176  {
177  std::get<1>(suc_cache[n]).insert(group_it->second);
178  }
179  netlist_abstr.gate_to_known_successor_groups[gate->get_id()].insert(group_it->second);
180  }
181 
182  bool added = false;
183  for (const auto* ep : current->get_destinations())
184  {
185  auto* g = ep->get_gate();
186  if (config.gate_types.find(g->get_type()) != config.gate_types.end())
187  {
188  // if target gate found, add to suc_cache of all nets along the predecessor path
189  auto& suc_cache_current = suc_cache[current];
190  std::get<0>(suc_cache_current).insert(g);
191  for (const auto* n : previous)
192  {
193  std::get<0>(suc_cache[n]).insert(g);
194  }
195  }
196  else
197  {
198  // propagate further by adding successors to stack
199  for (const auto* n : g->get_fan_out_nets())
200  {
201  if (visited.find(n) == visited.end())
202  {
203  stack.push_back(n);
204  added = true;
205  }
206  }
207  }
208  }
209 
210  if (added)
211  {
212  // keep track of previous net whenever propagating further
213  previous.push_back(current);
214  }
215  else
216  {
217  // if no change to stack, go back
218  stack.pop_back();
219  }
220  }
221  }
222 
223  const auto& start_fan_in_nets = gate->get_fan_in_nets();
224  stack = std::vector<const Net*>(start_fan_in_nets.begin(), start_fan_in_nets.end());
225  visited.clear();
226  previous.clear();
227  while (!stack.empty())
228  {
229  const Net* current = stack.back(); // do not pop last item yet
230 
231  if (!previous.empty() && current == previous.back())
232  {
233  // 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)
234  stack.pop_back();
235  previous.pop_back();
236  continue;
237  }
238 
239  visited.insert(current);
240 
241  if (const auto pred_cache_it = pred_cache.find(current); pred_cache_it != pred_cache.end())
242  {
243  auto& pred_cached_net_groups = std::get<1>(*pred_cache_it);
244 
245  // add cached known predecessor net groups to cache of all predecessor nets
246  for (const auto* n : previous)
247  {
248  pred_cache[n].insert(pred_cached_net_groups.cbegin(), pred_cached_net_groups.cend());
249  }
250 
251  // add cached net groups to known predecessor net groups of current gate
252  netlist_abstr.gate_to_known_predecessor_groups[gate->get_id()].insert(pred_cached_net_groups.cbegin(), pred_cached_net_groups.cend());
253 
254  stack.pop_back();
255  }
256  else
257  {
258  if (const auto group_it = net_to_group_index.find(current); group_it != net_to_group_index.end())
259  {
260  pred_cache[current].insert(group_it->second);
261  for (const auto* n : previous)
262  {
263  pred_cache[n].insert(group_it->second);
264  }
265  netlist_abstr.gate_to_known_predecessor_groups[gate->get_id()].insert(group_it->second);
266  }
267 
268  bool added = false;
269  for (const auto* ep : current->get_sources())
270  {
271  auto* g = ep->get_gate();
272  if (config.gate_types.find(g->get_type()) == config.gate_types.end())
273  {
274  // propagate further by adding predecessors to stack
275  for (const auto* n : g->get_fan_in_nets())
276  {
277  if (visited.find(n) == visited.end())
278  {
279  stack.push_back(n);
280  added = true;
281  }
282  }
283  }
284  }
285 
286  if (added)
287  {
288  // keep track of previous net whenever propagating further
289  previous.push_back(current);
290  }
291  else
292  {
293  // if no change to stack, go back
294  stack.pop_back();
295  }
296  }
297  }
298 
299  // collect successor target gates by getting cache of all fan-out nets of start gate
300  std::unordered_set<Gate*> next_target_gates;
301  for (const auto* n : start_fan_out_nets)
302  {
303  if (const auto it = suc_cache.find(n); it != suc_cache.end())
304  {
305  const auto& cached_gates = std::get<0>(std::get<1>(*it));
306  next_target_gates.insert(cached_gates.cbegin(), cached_gates.cend());
307  }
308  }
309 
310  for (const auto& suc : next_target_gates)
311  {
312  netlist_abstr.gate_to_successors[gate->get_id()].insert(suc->get_id());
313  netlist_abstr.gate_to_predecessors[suc->get_id()].insert(gate->get_id());
314  }
315  }
316  progress_bar.clear();
317  }
318  } // namespace
319 
320  NetlistAbstraction run(const dataflow::Configuration& config, std::shared_ptr<dataflow::Grouping>& initial_grouping)
321  {
322  log_info("dataflow", "pre-processing netlist...");
323  measure_block_time("pre-processing");
324  NetlistAbstraction netlist_abstr(config.netlist);
325  std::vector<std::vector<Gate*>> known_target_groups;
326  std::vector<std::vector<Net*>> known_net_groups;
327  identify_all_target_gates(config, netlist_abstr);
328  identify_all_control_signals(config, netlist_abstr);
329  identify_known_groups(config, netlist_abstr, known_target_groups);
330  identify_successors_predecessors(config, netlist_abstr);
331 
332  if (config.enable_stages)
333  {
334  identify_register_stages(netlist_abstr);
335  }
336 
337  initial_grouping = std::make_shared<dataflow::Grouping>(netlist_abstr, known_target_groups);
338 
339  return netlist_abstr;
340  }
341  } // namespace pre_processing
342  } // namespace dataflow
343 } // 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:320
hal::netlist_utils::get_nets_at_pins
std::vector< Net * > get_nets_at_pins(Gate *gate, std::vector< GatePin * > pins)
Definition: netlist_utils.cpp:442
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