1 /*
2 * Copyright (c) 1998-2013 Stephen Williams (steve@icarus.com)
3 *
4 * This source code is free software; you can redistribute it
5 * and/or modify it in source code form under the terms of the GNU
6 * General Public License as published by the Free Software
7 * Foundation; either version 2 of the License, or (at your option)
8 * any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
18 */
19
20 # include "config.h"
21
22 # include <algorithm>
23 # include <vector>
24 # include <cstdlib>
25 # include "netlist.h"
26 # include "netmisc.h"
27 # include "functor.h"
28 # include "compiler.h"
29 # include "ivl_assert.h"
30
31
32 /*
33 * The cprop function below invokes constant propagation where
34 * possible. The elaboration generates NetConst objects. I can remove
35 * these and replace the gates connected to it with simpler ones. I
36 * may even be able to replace nets with a new constant.
37 */
38
39 struct cprop_functor : public functor_t {
40
41 unsigned count;
42
43 virtual void signal(Design*des, NetNet*obj);
44 virtual void lpm_add_sub(Design*des, NetAddSub*obj);
45 virtual void lpm_compare(Design*des, NetCompare*obj);
46 virtual void lpm_concat(Design*des, NetConcat*obj);
47 virtual void lpm_ff(Design*des, NetFF*obj);
48 virtual void lpm_logic(Design*des, NetLogic*obj);
49 virtual void lpm_mux(Design*des, NetMux*obj);
50 virtual void lpm_part_select(Design*des, NetPartSelect*obj);
51
52 void lpm_compare_eq_(Design*des, NetCompare*obj);
53 };
54
signal(Design *,NetNet *)55 void cprop_functor::signal(Design*, NetNet*)
56 {
57 }
58
lpm_add_sub(Design *,NetAddSub *)59 void cprop_functor::lpm_add_sub(Design*, NetAddSub*)
60 {
61 }
62
lpm_compare(Design * des,NetCompare * obj)63 void cprop_functor::lpm_compare(Design*des, NetCompare*obj)
64 {
65 if (obj->pin_AEB().is_linked()) {
66 assert( ! obj->pin_AGB().is_linked() );
67 assert( ! obj->pin_AGEB().is_linked() );
68 assert( ! obj->pin_ALB().is_linked() );
69 assert( ! obj->pin_ALEB().is_linked() );
70 assert( ! obj->pin_AGB().is_linked() );
71 assert( ! obj->pin_ANEB().is_linked() );
72 lpm_compare_eq_(des, obj);
73 return;
74 }
75 }
76
lpm_compare_eq_(Design *,NetCompare *)77 void cprop_functor::lpm_compare_eq_(Design*, NetCompare*)
78 {
79 }
80
lpm_concat(Design * des,NetConcat * obj)81 void cprop_functor::lpm_concat(Design*des, NetConcat*obj)
82 {
83 // Sorry, I don't know how to constant-propagate through
84 // transparent concatenations.
85 if (obj->transparent())
86 return;
87
88 verinum result (verinum::Vz, obj->width());
89 unsigned off = 0;
90
91 for (unsigned idx = 1 ; idx < obj->pin_count() ; idx += 1) {
92 Nexus*nex = obj->pin(idx).nexus();
93 // If there are non-constant drivers, then give up.
94 if (! nex->drivers_constant())
95 return;
96
97 verinum tmp = nex->driven_vector();
98 result.set(off, tmp);
99 off += tmp.len();
100 }
101
102 if (debug_optimizer)
103 cerr << obj->get_fileline() << ": cprop_functor::lpm_concat: "
104 << "Replace NetConcat with " << result << "." << endl;
105
106
107 NetScope*scope = obj->scope();
108
109 // Create a NetConst object to carry the result. Give it the
110 // same name as the Concat object that we are replacing, and
111 // link the NetConst to the NetConcat object. Then delete the
112 // concat that is now replaced.
113 NetConst*result_obj = new NetConst(scope, obj->name(), result);
114 result_obj->set_line(*obj);
115 des->add_node(result_obj);
116 connect(obj->pin(0), result_obj->pin(0));
117
118 // Note that this will leave the const inputs to dangle. They
119 // will be reaped by other passes of cprop_functor.
120 delete obj;
121
122 count += 1;
123 }
124
lpm_ff(Design *,NetFF * obj)125 void cprop_functor::lpm_ff(Design*, NetFF*obj)
126 {
127 // Look for and count unlinked FF outputs. Note that if the
128 // Data and Q pins are connected together, they can be removed
129 // from the circuit, since it doesn't do anything.
130
131 if (connected(obj->pin_Data(), obj->pin_Q())
132 && (! obj->pin_Sclr().is_linked())
133 && (! obj->pin_Sset().is_linked())
134 && (! obj->pin_Aclr().is_linked())
135 && (! obj->pin_Aset().is_linked())) {
136 obj->pin_Data().unlink();
137 obj->pin_Q().unlink();
138 delete obj;
139 }
140 }
141
lpm_logic(Design *,NetLogic *)142 void cprop_functor::lpm_logic(Design*, NetLogic*)
143 {
144 }
145
146 /*
147 * This detects the case where the mux selects between a value and
148 * Vz. In this case, replace the device with a mos with the sel
149 * input used to enable the output.
150 */
lpm_mux(Design * des,NetMux * obj)151 void cprop_functor::lpm_mux(Design*des, NetMux*obj)
152 {
153 if (obj->size() != 2)
154 return;
155 if (obj->sel_width() != 1)
156 return;
157
158 Nexus*sel_nex = obj->pin_Sel().nexus();
159
160 /* If the select input is constant, then replace with a BUFZ */
161
162 // If the select is not constant, there is nothing we can do.
163 if (! sel_nex->drivers_constant())
164 return;
165
166 // If the constant select is 'bz or 'bx, then give up.
167 verinum::V sel_val = sel_nex->driven_value();
168 if (sel_val == verinum::Vz || sel_val == verinum::Vx)
169 return;
170
171 // The Select input must be a defined constant value, so we
172 // can replace the device with a BUFZ.
173
174 NetBUFZ*tmp = new NetBUFZ(obj->scope(), obj->name(), obj->width(), true);
175 tmp->set_line(*obj);
176
177 if (debug_optimizer)
178 cerr << obj->get_fileline() << ": debug: "
179 << "Replace binary MUX with constant select=" << sel_val
180 << " with a BUFZ to the selected input." << endl;
181
182 tmp->rise_time(obj->rise_time());
183 tmp->fall_time(obj->fall_time());
184 tmp->decay_time(obj->decay_time());
185
186 connect(tmp->pin(0), obj->pin_Result());
187 if (sel_val == verinum::V1)
188 connect(tmp->pin(1), obj->pin_Data(1));
189 else
190 connect(tmp->pin(1), obj->pin_Data(0));
191 delete obj;
192 des->add_node(tmp);
193 count += 1;
194 }
195
compare_base(NetPartSelect * a,NetPartSelect * b)196 static bool compare_base(NetPartSelect*a, NetPartSelect*b)
197 {
198 return a->base() < b->base();
199 }
200
201 /*
202 * This optimization searches for Nexa that are driven only by
203 * NetPartSelect(PV) outputs. These might turn from Verilog input that
204 * looks like this:
205 * wire [7:0] foo
206 * assign foo[7:4] = a;
207 * assign foo[3:0] = b;
208 * The idea is to convert the part selects of the above to a single
209 * concatenation that looks like this:
210 * assign foo = {a, b};
211 */
lpm_part_select(Design * des,NetPartSelect * obj)212 void cprop_functor::lpm_part_select(Design*des, NetPartSelect*obj)
213 {
214 if (obj->dir() != NetPartSelect::PV)
215 return;
216
217 NetScope*scope = obj->scope();
218 Nexus*nex = obj->pin(1).nexus();
219 vector<NetPartSelect*> obj_set;
220
221 for (Link*cur = nex->first_nlink() ; cur ; cur = cur->next_nlink()) {
222
223 // If this is an input (or passive) then ignore it.
224 if (cur->get_dir() != Link::OUTPUT)
225 continue;
226
227 // Check to see if this is the output of a
228 // NetPartSelect::PV. If not, then give up on the blend.
229 NetPins*tmp_obj = cur->get_obj();
230 unsigned tmp_pin = cur->get_pin();
231
232 NetPartSelect*cur_obj = dynamic_cast<NetPartSelect*> (tmp_obj);
233 if (cur_obj == 0)
234 return;
235
236 if (cur_obj->dir() != NetPartSelect::PV)
237 return;
238
239 if (tmp_pin != 1)
240 return;
241
242 obj_set.push_back(cur_obj);
243 }
244
245 if (obj_set.size() < 2)
246 return;
247
248 if (debug_optimizer)
249 cerr << obj->get_fileline() << ": cprop::lpm_part_select: "
250 << "Found " << obj_set.size() << " NetPartSelect(PV) objects."
251 << endl;
252
253 // Sort by increasing base offset.
254 sort(obj_set.begin(), obj_set.end(), compare_base);
255
256 // Check and make sure there are no overlaps. If there are,
257 // then give up on this optimization.
258 for (size_t idx = 1 ; idx < obj_set.size() ; idx += 1) {
259 unsigned top = obj_set[idx-1]->base() + obj_set[idx-1]->width();
260 if (top > obj_set[idx]->base()) {
261 if (debug_optimizer)
262 cerr << obj->get_fileline() << ": cprop::lpm_part_select: "
263 << "Range [" << obj_set[idx-1]->base()
264 << " " << top << ") overlaps PV starting at "
265 << obj_set[idx]->base() << ". Give up." << endl;
266 return;
267 }
268 }
269
270 // Check if the tail runs off the end of the target. If so it
271 // should be possible to replace it with a bit select to
272 // shorten the object for the target, but for now just give up.
273 unsigned sig_width = nex->vector_width();
274 if (obj_set.back()->base() + obj_set.back()->width() > sig_width) {
275 if (debug_optimizer)
276 cerr << obj->get_fileline() << ": cprop::lpm_part_select: "
277 << "Range [" << obj_set.back()->base()
278 << ":" << (obj_set.back()->base() + obj_set.back()->width() - 1)
279 << "] runs off the end of target." << endl;
280 return;
281 }
282
283 // Figure out how many components we are going to need.
284 unsigned part_count = 0;
285 unsigned off = 0;
286 for (size_t idx = 0 ; idx < obj_set.size() ; idx += 1) {
287 if (obj_set[idx]->base() > off) {
288 off = obj_set[idx]->base();
289 part_count += 1;
290 }
291 off += obj_set[idx]->width();
292 part_count += 1;
293 }
294
295 if (off < sig_width)
296 part_count += 1;
297
298 NetConcat*concat = new NetConcat(scope, scope->local_symbol(),
299 sig_width, part_count);
300 concat->set_line(*obj);
301 des->add_node(concat);
302 connect(concat->pin(0), obj->pin(1));
303
304 off = 0;
305 size_t concat_pin = 1;
306 for (size_t idx = 0 ; idx < obj_set.size() ; idx += 1) {
307 NetPartSelect*cobj = obj_set[idx];
308 if (cobj->base() > off) {
309 NetNet*zzz = make_const_z(des, scope, cobj->base()-off);
310 connect(concat->pin(concat_pin), zzz->pin(0));
311 concat_pin += 1;
312 off = cobj->base();
313 }
314 connect(concat->pin(concat_pin), cobj->pin(0));
315 concat_pin += 1;
316 off += cobj->width();
317 }
318 if (off < sig_width) {
319 NetNet*zzz = make_const_z(des, scope, sig_width-off);
320 connect(concat->pin(concat_pin), zzz->pin(0));
321 concat_pin += 1;
322 }
323 ivl_assert(*obj, concat_pin == concat->pin_count());
324
325 for (size_t idx = 0 ; idx < obj_set.size() ; idx += 1) {
326 delete obj_set[idx];
327 }
328
329 count += 1;
330 }
331
332 /*
333 * This functor looks to see if the constant is connected to nothing
334 * but signals. If that is the case, delete the dangling constant and
335 * the now useless signals. This functor is applied after the regular
336 * functor to clean up dangling constants that might be left behind.
337 */
338 struct cprop_dc_functor : public functor_t {
339
340 virtual void lpm_const(Design*des, NetConst*obj);
341 };
342
343 struct nexus_info_s {
344 Nexus*nex;
345 unsigned inp;
346 unsigned out;
347 };
348
lpm_const(Design *,NetConst * obj)349 void cprop_dc_functor::lpm_const(Design*, NetConst*obj)
350 {
351 // 'bz constant values drive high impedance to whatever is
352 // connected to it. In other words, it is a noop. But that is
353 // only true if *all* the bits of the vectors.
354 { unsigned tmp = 0;
355 ivl_assert(*obj, obj->pin_count()==1);
356 for (unsigned idx = 0 ; idx < obj->width() ; idx += 1) {
357 if (obj->value(idx) == verinum::Vz) {
358 tmp += 1;
359 }
360 }
361
362 if (tmp == obj->width()) {
363 delete obj;
364 return;
365 }
366 }
367
368 std::vector<nexus_info_s> nexus_info (obj->pin_count());
369 for (unsigned idx = 0 ; idx < obj->pin_count() ; idx += 1) {
370 nexus_info[idx].nex = obj->pin(idx).nexus();
371 unsigned inputs = 0, outputs = 0;
372 nexus_info[idx].nex -> count_io(inputs, outputs);
373 nexus_info[idx].inp = inputs;
374 nexus_info[idx].out = outputs;
375 }
376
377 // If there are any links that take input, the constant is
378 // used structurally somewhere.
379 for (unsigned idx = 0 ; idx < obj->pin_count() ; idx += 1)
380 if (nexus_info[idx].inp > 0)
381 return;
382
383 // Look for signals that have NetESignal nodes attached to
384 // them. If I find any, then this constant is used by a
385 // behavioral expression somewhere.
386 for (unsigned idx = 0 ; idx < obj->pin_count() ; idx += 1) {
387
388 for (Link*clnk = nexus_info[idx].nex->first_nlink()
389 ; clnk ; clnk = clnk->next_nlink()) {
390
391 NetPins*cur;
392 unsigned pin;
393 clnk->cur_link(cur, pin);
394
395 NetNet*tmp = dynamic_cast<NetNet*>(cur);
396 if (tmp == 0)
397 continue;
398
399 assert(tmp->scope());
400
401 // If the net is a signal name from the source,
402 // then users will probably want to see it in the
403 // waveform dump, so unhooking the constant will
404 // make it look wrong.
405 if (! tmp->local_flag())
406 return;
407
408 // If the net has an eref, then there is an
409 // expression somewhere that reads this signal. So
410 // the constant does get read.
411 if (tmp->peek_eref() > 0)
412 return;
413
414 // If the net is a port of the root module, then
415 // the constant may be driving something outside
416 // the design, so do not eliminate it.
417 if ((tmp->port_type() != NetNet::NOT_A_PORT)
418 && (tmp->scope()->parent() == 0))
419 return;
420
421 }
422 }
423
424 // Done. Found no reason to keep this object, so delete it.
425 delete obj;
426 }
427
428
cprop(Design * des)429 void cprop(Design*des)
430 {
431 // Continually propagate constants until a scan finds nothing
432 // to do.
433 cprop_functor prop;
434 do {
435 prop.count = 0;
436 des->functor(&prop);
437 if (verbose_flag) {
438 cout << " ... Iteration detected "
439 << prop.count << " optimizations." << endl << flush;
440 }
441 } while (prop.count > 0);
442
443 if (verbose_flag) {
444 cout << " ... Look for dangling constants" << endl << flush;
445 }
446 cprop_dc_functor dc;
447 des->functor(&dc);
448
449 if (verbose_flag) {
450 cout << " ... done" << endl << flush;
451 }
452 }
453