1 /*
2 * Copyright (c) 2000-2016 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 <iostream>
23
24 # include "netlist.h"
25 # include <sstream>
26 # include <cstring>
27 # include <string>
28 # include <typeinfo>
29 # include <cstdlib>
30 # include "ivl_alloc.h"
31
connect(Link & r)32 void Nexus::connect(Link&r)
33 {
34 Nexus*r_nexus = r.next_? r.find_nexus_() : 0;
35 if (this == r_nexus)
36 return;
37
38 delete[] name_;
39 name_ = 0;
40
41 // Special case: This nexus is empty. Simply copy all the
42 // links of the other nexus to this one, and delete the old
43 // nexus.
44 if (list_ == 0) {
45 if (r.next_ == 0) {
46 list_ = &r;
47 r.next_ = &r;
48 r.nexus_ = this;
49 driven_ = NO_GUESS;
50 } else {
51 driven_ = r_nexus->driven_;
52 list_ = r_nexus->list_;
53 list_->nexus_ = this;
54 r_nexus->list_ = 0;
55 delete r_nexus;
56 }
57 return;
58 }
59
60 // Special case: The Link is unconnected. Put it at the end of
61 // the current list and move the list_ pointer and nexus_ back
62 // pointer to suit.
63 if (r.next_ == 0) {
64 if (r.get_dir() != Link::INPUT)
65 driven_ = NO_GUESS;
66
67 r.nexus_ = this;
68 r.next_ = list_->next_;
69 list_->next_ = &r;
70 list_->nexus_ = 0;
71 list_ = &r;
72 return;
73 }
74
75 if (r_nexus->driven_ != Vz)
76 driven_ = NO_GUESS;
77
78 // Splice the list of links from the "tmp" nexus to the end of
79 // this nexus. Adjust the nexus pointers as needed.
80 Link*save_first = list_->next_;
81 list_->next_ = r_nexus->list_->next_;
82 r_nexus->list_->next_ = save_first;
83 list_->nexus_ = 0;
84 list_ = r_nexus->list_;
85 list_->nexus_ = this;
86
87 r_nexus->list_ = 0;
88 delete r_nexus;
89 }
90
connect(Link & l,Link & r)91 void connect(Link&l, Link&r)
92 {
93 Nexus*tmp;
94 assert(&l != &r);
95 // If either the l or r link already are part of a Nexus, then
96 // re-use that nexus. Go through some effort so that we are
97 // not gratuitously creating Nexus object.
98 if (l.next_ && (tmp=l.find_nexus_())) {
99 connect(tmp, r);
100 } else if (r.next_ && (tmp=r.find_nexus_())) {
101 connect(tmp, l);
102 } else {
103 // No existing Nexus (both links are so far unconnected)
104 // so start one.
105 tmp = new Nexus(l);
106 tmp->connect(r);
107 }
108 }
109
Link()110 Link::Link()
111 : dir_(PASSIVE), drive0_(IVL_DR_STRONG), drive1_(IVL_DR_STRONG),
112 next_(0), nexus_(0)
113 {
114 node_ = 0;
115 pin_zero_ = true;
116 }
117
~Link()118 Link::~Link()
119 {
120 if (next_) {
121 Nexus*tmp = nexus();
122 tmp->unlink(this);
123 if (tmp->list_ == 0)
124 delete tmp;
125 }
126 }
127
find_nexus_() const128 Nexus* Link::find_nexus_() const
129 {
130 assert(next_);
131 if (nexus_) return nexus_;
132 for (Link*cur = next_ ; cur != this ; cur = cur->next_) {
133 if (cur->nexus_) return cur->nexus_;
134 }
135 return 0;
136 }
137
nexus()138 Nexus* Link::nexus()
139 {
140 if (next_ == 0) {
141 assert(nexus_ == 0);
142 Nexus*tmp = new Nexus(*this);
143 return tmp;
144 }
145
146 return find_nexus_();
147 }
148
nexus() const149 const Nexus* Link::nexus() const
150 {
151 if (next_ == 0) return 0;
152 return find_nexus_();
153 }
154
set_dir(DIR d)155 void Link::set_dir(DIR d)
156 {
157 dir_ = d;
158 }
159
get_dir() const160 Link::DIR Link::get_dir() const
161 {
162 return dir_;
163 }
164
drivers_delays(NetExpr * rise,NetExpr * fall,NetExpr * decay)165 void Link::drivers_delays(NetExpr*rise, NetExpr*fall, NetExpr*decay)
166 {
167 find_nexus_()->drivers_delays(rise, fall, decay);
168 }
169
drivers_drive(ivl_drive_t drive0__,ivl_drive_t drive1__)170 void Link::drivers_drive(ivl_drive_t drive0__, ivl_drive_t drive1__)
171 {
172 find_nexus_()->drivers_drive(drive0__, drive1__);
173 }
174
175
drive0(ivl_drive_t str)176 void Link::drive0(ivl_drive_t str)
177 {
178 drive0_ = str;
179 }
180
drive1(ivl_drive_t str)181 void Link::drive1(ivl_drive_t str)
182 {
183 drive1_ = str;
184 }
185
drive0() const186 ivl_drive_t Link::drive0() const
187 {
188 return drive0_;
189 }
190
drive1() const191 ivl_drive_t Link::drive1() const
192 {
193 return drive1_;
194 }
195
cur_link(NetPins * & net,unsigned & pin)196 void Link::cur_link(NetPins*&net, unsigned &pin)
197 {
198 net = get_obj();
199 pin = get_pin();
200 }
201
cur_link(const NetPins * & net,unsigned & pin) const202 void Link::cur_link(const NetPins*&net, unsigned &pin) const
203 {
204 net = get_obj();
205 pin = get_pin();
206 }
207
unlink()208 void Link::unlink()
209 {
210 if (! is_linked())
211 return;
212
213 find_nexus_()->unlink(this);
214 }
215
is_equal(const Link & that) const216 bool Link::is_equal(const Link&that) const
217 {
218 return (get_obj() == that.get_obj()) && (get_pin() == that.get_pin());
219 }
220
is_linked() const221 bool Link::is_linked() const
222 {
223 if (next_ == 0)
224 return false;
225 if (next_ == this)
226 return false;
227
228 return true;
229 }
230
is_linked(const Link & that) const231 bool Link::is_linked(const Link&that) const
232 {
233 // If this or that link is linked to nothing, then they cannot
234 // be linked to each other.
235 if (! this->is_linked())
236 return false;
237 if (! that.is_linked())
238 return false;
239
240 const Link*cur = next_;
241 while (cur != this) {
242 if (cur == &that) return true;
243 cur = cur->next_;
244 }
245
246 return false;
247 }
248
Nexus(Link & that)249 Nexus::Nexus(Link&that)
250 {
251 name_ = 0;
252 driven_ = NO_GUESS;
253 t_cookie_ = 0;
254
255 if (that.next_ == 0) {
256 list_ = &that;
257 that.next_ = &that;
258 that.nexus_ = this;
259 driven_ = NO_GUESS;
260
261 } else {
262 Nexus*tmp = that.find_nexus_();
263 list_ = tmp->list_;
264 list_->nexus_ = this;
265 driven_ = tmp->driven_;
266 name_ = tmp->name_;
267
268 tmp->list_ = 0;
269 tmp->name_ = 0;
270 delete tmp;
271 }
272 }
273
~Nexus()274 Nexus::~Nexus()
275 {
276 assert(list_ == 0);
277 delete[] name_;
278 }
279
assign_lval() const280 bool Nexus::assign_lval() const
281 {
282 for (const Link*cur = first_nlink() ; cur ; cur = cur->next_nlink()) {
283
284 const NetPins*obj;
285 unsigned pin;
286 cur->cur_link(obj, pin);
287 const NetNet*net = dynamic_cast<const NetNet*> (obj);
288 if (net == 0)
289 continue;
290
291 if (net->peek_lref() > 0)
292 return true;
293 }
294
295 return false;
296 }
297
count_io(unsigned & inp,unsigned & out) const298 void Nexus::count_io(unsigned&inp, unsigned&out) const
299 {
300 for (const Link*cur = first_nlink() ; cur ; cur = cur->next_nlink()) {
301 switch (cur->get_dir()) {
302 case Link::INPUT:
303 inp += 1;
304 break;
305 case Link::OUTPUT:
306 out += 1;
307 break;
308 default:
309 break;
310 }
311 }
312 }
313
has_floating_input() const314 bool Nexus::has_floating_input() const
315 {
316 bool found_input = false;
317 for (const Link*cur = first_nlink() ; cur ; cur = cur->next_nlink()) {
318 if (cur->get_dir() == Link::OUTPUT)
319 return false;
320
321 if (cur->get_dir() == Link::INPUT)
322 found_input = true;
323 }
324
325 return found_input;
326 }
327
drivers_present() const328 bool Nexus::drivers_present() const
329 {
330 for (const Link*cur = first_nlink() ; cur ; cur = cur->next_nlink()) {
331 if (cur->get_dir() == Link::OUTPUT)
332 return true;
333
334 if (cur->get_dir() == Link::INPUT)
335 continue;
336
337 // Must be PASSIVE, so if it is some kind of net, see if
338 // it is the sort that might drive the nexus. Note that
339 // supply0/1 and tri0/1 nets are classified as OUTPUT.
340 const NetPins*obj;
341 unsigned pin;
342 cur->cur_link(obj, pin);
343 if (const NetNet*net = dynamic_cast<const NetNet*>(obj))
344 switch (net->type()) {
345 case NetNet::WAND:
346 case NetNet::WOR:
347 case NetNet::TRIAND:
348 case NetNet::TRIOR:
349 case NetNet::REG:
350 return true;
351 default:
352 break;
353 }
354 }
355
356 return false;
357 }
358
drivers_delays(NetExpr * rise,NetExpr * fall,NetExpr * decay)359 void Nexus::drivers_delays(NetExpr*rise, NetExpr*fall, NetExpr*decay)
360 {
361 for (Link*cur = first_nlink() ; cur ; cur = cur->next_nlink()) {
362 if (cur->get_dir() != Link::OUTPUT)
363 continue;
364
365 NetObj*obj = dynamic_cast<NetObj*>(cur->get_obj());
366 if (obj == 0)
367 continue;
368
369 obj->rise_time(rise);
370 obj->fall_time(fall);
371 obj->decay_time(decay);
372 }
373 }
374
drivers_drive(ivl_drive_t drive0,ivl_drive_t drive1)375 void Nexus::drivers_drive(ivl_drive_t drive0, ivl_drive_t drive1)
376 {
377 for (Link*cur = first_nlink() ; cur ; cur = cur->next_nlink()) {
378 if (cur->get_dir() != Link::OUTPUT)
379 continue;
380
381 cur->drive0(drive0);
382 cur->drive1(drive1);
383 }
384 }
385
unlink(Link * that)386 void Nexus::unlink(Link*that)
387 {
388 delete[] name_;
389 name_ = 0;
390
391 assert(that);
392
393 // Special case: the Link is the only link in the nexus. In
394 // this case, the unlink is trivial. Also clear the Nexus
395 // pointers.
396 if (that->next_ == that) {
397 assert(that->nexus_ == this);
398 assert(list_ == that);
399 list_ = 0;
400 driven_ = NO_GUESS;
401 that->nexus_ = 0;
402 that->next_ = 0;
403 return;
404 }
405
406 // If the link I'm removing was a driver for this nexus, then
407 // cancel my guess of the driven value.
408 if (that->get_dir() != Link::INPUT)
409 driven_ = NO_GUESS;
410
411 // Look for the Link that points to "that". We know that there
412 // will be one because the list is a circle. When we find the
413 // prev pointer, then remove that from the list.
414 Link*prev = list_;
415 while (prev->next_ != that)
416 prev = prev->next_;
417
418 prev->next_ = that->next_;
419
420 // If "that" was the last item in the list, then change the
421 // list_ pointer to point to the new end of the list.
422 if (list_ == that) {
423 assert(that->nexus_ == this);
424 list_ = prev;
425 list_->nexus_ = this;
426 }
427
428 that->nexus_ = 0;
429 that->next_ = 0;
430 }
431
first_nlink()432 Link* Nexus::first_nlink()
433 {
434 if (list_) return list_->next_;
435 else return 0;
436 }
437
first_nlink() const438 const Link* Nexus::first_nlink() const
439 {
440 if (list_) return list_->next_;
441 else return 0;
442 }
443
444 /*
445 * The t_cookie can be set exactly once. This attaches an ivl_nexus_t
446 * object to the Nexus, and causes the Link list to be marked up for
447 * efficient use by the code generator. The change is to give all the
448 * links a valid nexus_ pointer. This breaks most of the other
449 * methods, but they are not used during code generation.
450 */
t_cookie(ivl_nexus_t val) const451 void Nexus::t_cookie(ivl_nexus_t val) const
452 {
453 assert(val && !t_cookie_);
454 t_cookie_ = val;
455
456 for (Link*cur = list_->next_ ; cur->nexus_ == 0 ; cur = cur->next_)
457 cur->nexus_ = const_cast<Nexus*> (this);
458 }
459
vector_width() const460 unsigned Nexus::vector_width() const
461 {
462 for (const Link*cur = first_nlink() ; cur ; cur = cur->next_nlink()) {
463 const NetNet*sig = dynamic_cast<const NetNet*>(cur->get_obj());
464 if (sig == 0)
465 continue;
466
467 return sig->vector_width();
468 }
469
470 return 0;
471 }
472
pick_any_net()473 NetNet* Nexus::pick_any_net()
474 {
475 for (Link*cur = first_nlink() ; cur ; cur = cur->next_nlink()) {
476 NetNet*sig = dynamic_cast<NetNet*>(cur->get_obj());
477 if (sig != 0)
478 return sig;
479 }
480
481 return 0;
482 }
483
pick_any_node()484 NetNode* Nexus::pick_any_node()
485 {
486 for (Link*cur = first_nlink() ; cur ; cur = cur->next_nlink()) {
487 NetNode*node = dynamic_cast<NetNode*>(cur->get_obj());
488 if (node != 0)
489 return node;
490 }
491
492 return 0;
493 }
494
name() const495 const char* Nexus::name() const
496 {
497 if (name_)
498 return name_;
499
500 const NetNet*sig = 0;
501 unsigned pin = 0;
502 for (const Link*cur = first_nlink()
503 ; cur ; cur = cur->next_nlink()) {
504
505 const NetNet*cursig = dynamic_cast<const NetNet*>(cur->get_obj());
506 if (cursig == 0)
507 continue;
508
509 if (sig == 0) {
510 sig = cursig;
511 pin = cur->get_pin();
512 continue;
513 }
514
515 if ((cursig->pin_count() == 1) && (sig->pin_count() > 1))
516 continue;
517
518 if ((cursig->pin_count() > 1) && (sig->pin_count() == 1)) {
519 sig = cursig;
520 pin = cur->get_pin();
521 continue;
522 }
523
524 if (cursig->local_flag() && !sig->local_flag())
525 continue;
526
527 if (cursig->name() < sig->name())
528 continue;
529
530 sig = cursig;
531 pin = cur->get_pin();
532 }
533
534 if (sig == 0) {
535 const Link*lnk = first_nlink();
536 const NetObj*obj = dynamic_cast<const NetObj*>(lnk->get_obj());
537 pin = lnk->get_pin();
538 cerr << "internal error: No signal for nexus of "
539 << obj->name() << " pin " << pin
540 << " type=" << typeid(*obj).name() << "?" << endl;
541
542 ostringstream tmp;
543 tmp << "nex=" << this << ends;
544 const string tmps = tmp.str();
545 name_ = new char[strlen(tmps.c_str()) + 1];
546 strcpy(name_, tmps.c_str());
547 } else {
548 assert(sig);
549 ostringstream tmp;
550 tmp << scope_path(sig->scope()) << "." << sig->name();
551 if (sig->pin_count() > 1)
552 tmp << "<" << pin << ">";
553 tmp << ends;
554
555 const string tmps = tmp.str();
556 name_ = new char[strlen(tmps.c_str()) + 1];
557 strcpy(name_, tmps.c_str());
558 }
559
560 return name_;
561 }
562
563
NexusSet()564 NexusSet::NexusSet()
565 {
566 }
567
~NexusSet()568 NexusSet::~NexusSet()
569 {
570 for (size_t idx = 0 ; idx < items_.size() ; idx += 1)
571 delete items_[idx];
572 }
573
size() const574 size_t NexusSet::size() const
575 {
576 return items_.size();
577 }
578
add(Nexus * that,unsigned base,unsigned wid)579 void NexusSet::add(Nexus*that, unsigned base, unsigned wid)
580 {
581 assert(that);
582 elem_t*cur = new elem_t(that, base, wid);
583
584 if (items_.size() == 0) {
585 items_.resize(1);
586 items_[0] = cur;
587 return;
588 }
589
590 unsigned ptr = bsearch_(*cur);
591 if (ptr < items_.size()) {
592 delete cur;
593 return;
594 }
595
596 assert(ptr == items_.size());
597
598 items_.push_back(cur);
599 }
600
add(NexusSet & that)601 void NexusSet::add(NexusSet&that)
602 {
603 for (size_t idx = 0 ; idx < that.items_.size() ; idx += 1)
604 add(that.items_[idx]->lnk.nexus(), that.items_[idx]->base, that.items_[idx]->wid);
605 }
606
rem_(const NexusSet::elem_t * that)607 void NexusSet::rem_(const NexusSet::elem_t*that)
608 {
609 if (items_.empty())
610 return;
611
612 unsigned ptr = bsearch_(*that);
613 if (ptr >= items_.size())
614 return;
615
616 if (items_.size() == 1) {
617 delete items_[0];
618 items_.clear();
619 return;
620 }
621
622 delete items_[ptr];
623 for (unsigned idx = ptr ; idx < (items_.size()-1) ; idx += 1)
624 items_[idx] = items_[idx+1];
625
626 items_.pop_back();
627 }
628
rem(const NexusSet & that)629 void NexusSet::rem(const NexusSet&that)
630 {
631 for (size_t idx = 0 ; idx < that.items_.size() ; idx += 1)
632 rem_(that.items_[idx]);
633 }
634
find_nexus(const NexusSet::elem_t & that) const635 unsigned NexusSet::find_nexus(const NexusSet::elem_t&that) const
636 {
637 return bsearch_(that);
638 }
639
at(unsigned idx)640 NexusSet::elem_t& NexusSet::at (unsigned idx)
641 {
642 assert(idx < items_.size());
643 return *items_[idx];
644 }
645
bsearch_(const NexusSet::elem_t & that) const646 size_t NexusSet::bsearch_(const NexusSet::elem_t&that) const
647 {
648 for (unsigned idx = 0 ; idx < items_.size() ; idx += 1) {
649 if (*items_[idx] == that)
650 return idx;
651 }
652
653 return items_.size();
654 }
655
contains(const struct elem_t & that) const656 bool NexusSet::elem_t::contains(const struct elem_t&that) const
657 {
658 if (! lnk.is_linked(that.lnk))
659 return false;
660 if (that.base < base)
661 return false;
662 if ((that.base+that.wid) > (base+wid))
663 return false;
664
665 return true;
666 }
667
contains_(const NexusSet::elem_t & that) const668 bool NexusSet::contains_(const NexusSet::elem_t&that) const
669 {
670 for (unsigned idx = 0 ; idx < items_.size() ; idx += 1) {
671 if (items_[idx]->contains(that))
672 return true;
673 }
674 return false;
675 }
676
contains(const NexusSet & that) const677 bool NexusSet::contains(const NexusSet&that) const
678 {
679 for (size_t idx = 0 ; idx < that.items_.size() ; idx += 1) {
680 if (! contains_(*that.items_[idx]))
681 return false;
682 }
683
684 return true;
685 }
686
intersect(const NexusSet & that) const687 bool NexusSet::intersect(const NexusSet&that) const
688 {
689 for (size_t idx = 0 ; idx < that.items_.size() ; idx += 1) {
690 size_t where = bsearch_(*that.items_[idx]);
691 if (where == items_.size())
692 continue;
693
694 return true;
695 }
696
697 return false;
698 }
699