yosys-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
consteval.h
Go to the documentation of this file.
1 /*
2  * yosys -- Yosys Open SYnthesis Suite
3  *
4  * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at>
5  *
6  * Permission to use, copy, modify, and/or distribute this software for any
7  * purpose with or without fee is hereby granted, provided that the above
8  * copyright notice and this permission notice appear in all copies.
9  *
10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17  *
18  */
19 
20 #ifndef CONSTEVAL_H
21 #define CONSTEVAL_H
22 
23 #include "kernel/rtlil.h"
24 #include "kernel/sigtools.h"
25 #include "kernel/celltypes.h"
26 #include "kernel/macc.h"
27 
29 
30 struct ConstEval
31 {
37  std::set<RTLIL::Cell*> busy;
38  std::vector<SigMap> stack;
39 
40  ConstEval(RTLIL::Module *module) : module(module), assign_map(module)
41  {
42  CellTypes ct;
43  ct.setup_internals();
44  ct.setup_stdcells();
45 
46  for (auto &it : module->cells_) {
47  if (!ct.cell_known(it.second->type))
48  continue;
49  for (auto &it2 : it.second->connections())
50  if (ct.cell_output(it.second->type, it2.first))
51  sig2driver.insert(assign_map(it2.second), it.second);
52  }
53  }
54 
55  void clear()
56  {
57  values_map.clear();
59  }
60 
61  void push()
62  {
63  stack.push_back(values_map);
64  }
65 
66  void pop()
67  {
68  values_map.swap(stack.back());
69  stack.pop_back();
70  }
71 
72  void set(RTLIL::SigSpec sig, RTLIL::Const value)
73  {
74  assign_map.apply(sig);
75 #ifndef NDEBUG
76  RTLIL::SigSpec current_val = values_map(sig);
77  for (int i = 0; i < GetSize(current_val); i++)
78  log_assert(current_val[i].wire != NULL || current_val[i] == value.bits[i]);
79 #endif
80  values_map.add(sig, RTLIL::SigSpec(value));
81  }
82 
83  void stop(RTLIL::SigSpec sig)
84  {
85  assign_map.apply(sig);
86  stop_signals.add(sig);
87  }
88 
89  bool eval(RTLIL::Cell *cell, RTLIL::SigSpec &undef)
90  {
91  if (cell->type == "$lcu")
92  {
93  RTLIL::SigSpec sig_p = cell->getPort("\\P");
94  RTLIL::SigSpec sig_g = cell->getPort("\\G");
95  RTLIL::SigSpec sig_ci = cell->getPort("\\CI");
96  RTLIL::SigSpec sig_co = values_map(assign_map(cell->getPort("\\CO")));
97 
98  if (sig_co.is_fully_const())
99  return true;
100 
101  if (!eval(sig_p, undef, cell))
102  return false;
103 
104  if (!eval(sig_g, undef, cell))
105  return false;
106 
107  if (!eval(sig_ci, undef, cell))
108  return false;
109 
110  if (sig_p.is_fully_def() && sig_g.is_fully_def() && sig_ci.is_fully_def())
111  {
112  RTLIL::Const coval(RTLIL::Sx, GetSize(sig_co));
113  bool carry = sig_ci.as_bool();
114 
115  for (int i = 0; i < GetSize(coval); i++) {
116  carry = (sig_g[i] == RTLIL::S1) || (sig_p[i] == RTLIL::S1 && carry);
117  coval.bits[i] = carry ? RTLIL::S1 : RTLIL::S0;
118  }
119 
120  set(sig_co, coval);
121  }
122  else
123  set(sig_co, RTLIL::Const(RTLIL::Sx, GetSize(sig_co)));
124 
125  return true;
126  }
127 
128  RTLIL::SigSpec sig_a, sig_b, sig_s, sig_y;
129 
130  log_assert(cell->hasPort("\\Y"));
131  sig_y = values_map(assign_map(cell->getPort("\\Y")));
132  if (sig_y.is_fully_const())
133  return true;
134 
135  if (cell->hasPort("\\S")) {
136  sig_s = cell->getPort("\\S");
137  if (!eval(sig_s, undef, cell))
138  return false;
139  }
140 
141  if (cell->hasPort("\\A"))
142  sig_a = cell->getPort("\\A");
143 
144  if (cell->hasPort("\\B"))
145  sig_b = cell->getPort("\\B");
146 
147  if (cell->type == "$mux" || cell->type == "$pmux" || cell->type == "$_MUX_")
148  {
149  std::vector<RTLIL::SigSpec> y_candidates;
150  int count_maybe_set_s_bits = 0;
151  int count_set_s_bits = 0;
152 
153  for (int i = 0; i < sig_s.size(); i++)
154  {
155  RTLIL::State s_bit = sig_s.extract(i, 1).as_const().bits.at(0);
156  RTLIL::SigSpec b_slice = sig_b.extract(sig_y.size()*i, sig_y.size());
157 
158  if (s_bit == RTLIL::State::Sx || s_bit == RTLIL::State::S1)
159  y_candidates.push_back(b_slice);
160 
161  if (s_bit == RTLIL::State::S1 || s_bit == RTLIL::State::Sx)
162  count_maybe_set_s_bits++;
163 
164  if (s_bit == RTLIL::State::S1)
165  count_set_s_bits++;
166  }
167 
168  if (count_set_s_bits == 0)
169  y_candidates.push_back(sig_a);
170 
171  std::vector<RTLIL::Const> y_values;
172 
173  log_assert(y_candidates.size() > 0);
174  for (auto &yc : y_candidates) {
175  if (!eval(yc, undef, cell))
176  return false;
177  y_values.push_back(yc.as_const());
178  }
179 
180  if (y_values.size() > 1)
181  {
182  std::vector<RTLIL::State> master_bits = y_values.at(0).bits;
183 
184  for (size_t i = 1; i < y_values.size(); i++) {
185  std::vector<RTLIL::State> &slave_bits = y_values.at(i).bits;
186  log_assert(master_bits.size() == slave_bits.size());
187  for (size_t j = 0; j < master_bits.size(); j++)
188  if (master_bits[j] != slave_bits[j])
189  master_bits[j] = RTLIL::State::Sx;
190  }
191 
192  set(sig_y, RTLIL::Const(master_bits));
193  }
194  else
195  set(sig_y, y_values.front());
196  }
197  else if (cell->type == "$fa")
198  {
199  RTLIL::SigSpec sig_c = cell->getPort("\\C");
200  RTLIL::SigSpec sig_x = cell->getPort("\\X");
201  int width = GetSize(sig_c);
202 
203  if (!eval(sig_a, undef, cell))
204  return false;
205 
206  if (!eval(sig_b, undef, cell))
207  return false;
208 
209  if (!eval(sig_c, undef, cell))
210  return false;
211 
212  RTLIL::Const t1 = const_xor(sig_a.as_const(), sig_b.as_const(), false, false, width);
213  RTLIL::Const val_y = const_xor(t1, sig_c.as_const(), false, false, width);
214 
215  RTLIL::Const t2 = const_and(sig_a.as_const(), sig_b.as_const(), false, false, width);
216  RTLIL::Const t3 = const_and(sig_c.as_const(), t1, false, false, width);
217  RTLIL::Const val_x = const_or(t2, t3, false, false, width);
218 
219  for (int i = 0; i < GetSize(val_y); i++)
220  if (val_y.bits[i] == RTLIL::Sx)
221  val_x.bits[i] = RTLIL::Sx;
222 
223  set(sig_y, val_y);
224  set(sig_x, val_x);
225  }
226  else if (cell->type == "$alu")
227  {
228  bool signed_a = cell->parameters.count("\\A_SIGNED") > 0 && cell->parameters["\\A_SIGNED"].as_bool();
229  bool signed_b = cell->parameters.count("\\B_SIGNED") > 0 && cell->parameters["\\B_SIGNED"].as_bool();
230 
231  RTLIL::SigSpec sig_ci = cell->getPort("\\CI");
232  RTLIL::SigSpec sig_bi = cell->getPort("\\BI");
233 
234  if (!eval(sig_a, undef, cell))
235  return false;
236 
237  if (!eval(sig_b, undef, cell))
238  return false;
239 
240  if (!eval(sig_ci, undef, cell))
241  return false;
242 
243  if (!eval(sig_bi, undef, cell))
244  return false;
245 
246  RTLIL::SigSpec sig_x = cell->getPort("\\X");
247  RTLIL::SigSpec sig_co = cell->getPort("\\CO");
248 
249  bool any_input_undef = !(sig_a.is_fully_def() && sig_b.is_fully_def() && sig_ci.is_fully_def() && sig_bi.is_fully_def());
250  sig_a.extend_u0(GetSize(sig_y), signed_a);
251  sig_b.extend_u0(GetSize(sig_y), signed_b);
252 
253  bool carry = sig_ci[0] == RTLIL::S1;
254  bool b_inv = sig_bi[0] == RTLIL::S1;
255 
256  for (int i = 0; i < GetSize(sig_y); i++)
257  {
258  RTLIL::SigSpec x_inputs = { sig_a[i], sig_b[i], sig_bi[0] };
259 
260  if (!x_inputs.is_fully_def()) {
261  set(sig_x[i], RTLIL::Sx);
262  } else {
263  bool bit_a = sig_a[i] == RTLIL::S1;
264  bool bit_b = (sig_b[i] == RTLIL::S1) != b_inv;
265  bool bit_x = bit_a != bit_b;
266  set(sig_x[i], bit_x ? RTLIL::S1 : RTLIL::S0);
267  }
268 
269  if (any_input_undef) {
270  set(sig_y[i], RTLIL::Sx);
271  set(sig_co[i], RTLIL::Sx);
272  } else {
273  bool bit_a = sig_a[i] == RTLIL::S1;
274  bool bit_b = (sig_b[i] == RTLIL::S1) != b_inv;
275  bool bit_y = (bit_a != bit_b) != carry;
276  carry = (bit_a && bit_b) || (bit_a && carry) || (bit_b && carry);
277  set(sig_y[i], bit_y ? RTLIL::S1 : RTLIL::S0);
278  set(sig_co[i], carry ? RTLIL::S1 : RTLIL::S0);
279  }
280  }
281  }
282  else if (cell->type == "$macc")
283  {
284  Macc macc;
285  macc.from_cell(cell);
286 
287  if (!eval(macc.bit_ports, undef, cell))
288  return false;
289 
290  for (auto &port : macc.ports) {
291  if (!eval(port.in_a, undef, cell))
292  return false;
293  if (!eval(port.in_b, undef, cell))
294  return false;
295  }
296 
297  RTLIL::Const result(0, GetSize(cell->getPort("\\Y")));
298  if (!macc.eval(result))
299  log_abort();
300 
301  set(cell->getPort("\\Y"), result);
302  }
303  else
304  {
305  RTLIL::SigSpec sig_c, sig_d;
306 
307  if (cell->type.in("$_AOI3_", "$_OAI3_", "$_AOI4_", "$_OAI4_")) {
308  if (cell->hasPort("\\C"))
309  sig_c = cell->getPort("\\C");
310  if (cell->hasPort("\\D"))
311  sig_d = cell->getPort("\\D");
312  }
313 
314  if (sig_a.size() > 0 && !eval(sig_a, undef, cell))
315  return false;
316  if (sig_b.size() > 0 && !eval(sig_b, undef, cell))
317  return false;
318  if (sig_c.size() > 0 && !eval(sig_c, undef, cell))
319  return false;
320  if (sig_d.size() > 0 && !eval(sig_d, undef, cell))
321  return false;
322 
323  set(sig_y, CellTypes::eval(cell, sig_a.as_const(), sig_b.as_const(),
324  sig_c.as_const(), sig_d.as_const()));
325  }
326 
327  return true;
328  }
329 
330  bool eval(RTLIL::SigSpec &sig, RTLIL::SigSpec &undef, RTLIL::Cell *busy_cell = NULL)
331  {
332  assign_map.apply(sig);
333  values_map.apply(sig);
334 
335  if (sig.is_fully_const())
336  return true;
337 
338  if (stop_signals.check_any(sig)) {
339  undef = stop_signals.extract(sig);
340  return false;
341  }
342 
343  if (busy_cell) {
344  if (busy.count(busy_cell) > 0) {
345  undef = sig;
346  return false;
347  }
348  busy.insert(busy_cell);
349  }
350 
351  std::set<RTLIL::Cell*> driver_cells;
352  sig2driver.find(sig, driver_cells);
353  for (auto cell : driver_cells) {
354  if (!eval(cell, undef)) {
355  if (busy_cell)
356  busy.erase(busy_cell);
357  return false;
358  }
359  }
360 
361  if (busy_cell)
362  busy.erase(busy_cell);
363 
364  values_map.apply(sig);
365  if (sig.is_fully_const())
366  return true;
367 
368  for (auto &c : sig.chunks())
369  if (c.wire != NULL)
370  undef.append(c);
371  return false;
372  }
373 
374  bool eval(RTLIL::SigSpec &sig)
375  {
376  RTLIL::SigSpec undef;
377  return eval(sig, undef);
378  }
379 };
380 
382 
383 #endif
bool is_fully_def() const
Definition: rtlil.cc:2774
RTLIL::SigSpec extract(RTLIL::SigSpec sig)
Definition: sigtools.h:77
RTLIL::SigSpec bit_ports
Definition: macc.h:35
RTLIL::Const const_xor(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
Definition: calc.cc:175
void setup_stdcells()
Definition: celltypes.h:132
Definition: macc.h:27
CellTypes ct
Definition: opt_clean.cc:33
#define YOSYS_NAMESPACE_END
Definition: yosys.h:100
RTLIL::Const as_const() const
Definition: rtlil.cc:2857
bool as_bool() const
Definition: rtlil.cc:2818
bool eval(RTLIL::Const &result) const
Definition: macc.h:200
void clear()
Definition: sigtools.h:263
bool eval(RTLIL::SigSpec &sig)
Definition: consteval.h:374
bool eval(RTLIL::Cell *cell, RTLIL::SigSpec &undef)
Definition: consteval.h:89
SigMap assign_map
Definition: consteval.h:33
std::vector< SigMap > stack
Definition: consteval.h:38
std::vector< port_t > ports
Definition: macc.h:34
RTLIL::IdString type
Definition: rtlil.h:854
std::map< RTLIL::IdString, RTLIL::Const > parameters
Definition: rtlil.h:856
void extend_u0(int width, bool is_signed=false)
Definition: rtlil.cc:2612
int size() const
Definition: rtlil.h:1019
#define log_abort()
Definition: log.h:84
RTLIL::Const const_or(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
Definition: calc.cc:170
std::set< RTLIL::Cell * > busy
Definition: consteval.h:37
bool in(T first, Args...rest)
Definition: rtlil.h:241
void clear()
Definition: consteval.h:55
void push()
Definition: consteval.h:61
void swap(SigMap &other)
Definition: sigtools.h:253
void clear()
Definition: sigtools.h:36
RTLIL::Const const_and(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
Definition: calc.cc:165
void apply(RTLIL::SigBit &bit) const
Definition: sigtools.h:383
bool cell_known(RTLIL::IdString type)
Definition: celltypes.h:188
bool check_any(RTLIL::SigSpec sig)
Definition: sigtools.h:100
RTLIL_ATTRIBUTE_MEMBERS bool hasPort(RTLIL::IdString portname) const
Definition: rtlil.cc:1766
bool cell_output(RTLIL::IdString type, RTLIL::IdString port)
Definition: celltypes.h:193
const RTLIL::SigSpec & getPort(RTLIL::IdString portname) const
Definition: rtlil.cc:1809
int GetSize(RTLIL::Wire *wire)
Definition: yosys.cc:334
static RTLIL::Const eval(RTLIL::IdString type, const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
Definition: celltypes.h:219
#define log_assert(_assert_expr_)
Definition: log.h:85
RTLIL::Module * module
Definition: consteval.h:32
bool is_fully_const() const
Definition: rtlil.cc:2763
void stop(RTLIL::SigSpec sig)
Definition: consteval.h:83
ConstEval(RTLIL::Module *module)
Definition: consteval.h:40
void from_cell(RTLIL::Cell *cell)
Definition: macc.h:100
void add(RTLIL::SigSpec sig)
Definition: sigtools.h:41
SigSet< RTLIL::Cell * > sig2driver
Definition: consteval.h:36
#define NULL
std::map< RTLIL::IdString, RTLIL::Cell * > cells_
Definition: rtlil.h:596
#define YOSYS_NAMESPACE_BEGIN
Definition: yosys.h:99
void setup_internals()
Definition: celltypes.h:83
RTLIL::SigSpec extract(const RTLIL::SigSpec &pattern, const RTLIL::SigSpec *other=NULL) const
Definition: rtlil.cc:2414
std::vector< RTLIL::State > bits
Definition: rtlil.h:438
void append(const RTLIL::SigSpec &signal)
Definition: rtlil.cc:2523
SigPool stop_signals
Definition: consteval.h:35
State
Definition: rtlil.h:29
void add(RTLIL::SigSpec from, RTLIL::SigSpec to)
Definition: sigtools.h:347
bool eval(RTLIL::SigSpec &sig, RTLIL::SigSpec &undef, RTLIL::Cell *busy_cell=NULL)
Definition: consteval.h:330
void set(RTLIL::SigSpec sig, RTLIL::Const value)
Definition: consteval.h:72
void find(RTLIL::SigSpec sig, std::set< T > &result)
Definition: sigtools.h:187
void insert(RTLIL::SigSpec sig, T data)
Definition: sigtools.h:152
void pop()
Definition: consteval.h:66
const std::vector< RTLIL::SigChunk > & chunks() const
Definition: rtlil.h:1016
SigMap values_map
Definition: consteval.h:34