1 // OpenSTA, Static Timing Analyzer
2 // Copyright (c) 2021, Parallax Software, Inc.
3 //
4 // This program is free software: you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation, either version 3 of the License, or
7 // (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program. If not, see <https://www.gnu.org/licenses/>.
16
17 #include "ConcreteLibrary.hh"
18
19 #include <stdlib.h>
20
21 #include "DisallowCopyAssign.hh"
22 #include "PatternMatch.hh"
23 #include "PortDirection.hh"
24 #include "ParseBus.hh"
25
26 namespace sta {
27
28 static constexpr char escape_ = '\\';
29
ConcreteLibrary(const char * name,const char * filename,bool is_liberty)30 ConcreteLibrary::ConcreteLibrary(const char *name,
31 const char *filename,
32 bool is_liberty) :
33 name_(stringCopy(name)),
34 filename_(stringCopy(filename)),
35 is_liberty_(is_liberty),
36 bus_brkt_left_('['),
37 bus_brkt_right_(']')
38 {
39 }
40
~ConcreteLibrary()41 ConcreteLibrary::~ConcreteLibrary()
42 {
43 stringDelete(name_);
44 stringDelete(filename_);
45 cell_map_.deleteContents();
46 }
47
48 ConcreteCell *
makeCell(const char * name,bool is_leaf,const char * filename)49 ConcreteLibrary::makeCell(const char *name,
50 bool is_leaf,
51 const char *filename)
52 {
53 ConcreteCell *cell = new ConcreteCell(this, name, is_leaf, filename);
54 addCell(cell);
55 return cell;
56 }
57
58 void
addCell(ConcreteCell * cell)59 ConcreteLibrary::addCell(ConcreteCell *cell)
60 {
61 cell_map_[cell->name()] = cell;
62 }
63
64 void
renameCell(ConcreteCell * cell,const char * cell_name)65 ConcreteLibrary::renameCell(ConcreteCell *cell,
66 const char *cell_name)
67 {
68 cell_map_.erase(cell->name());
69 cell_map_[cell_name] = cell;
70 }
71
72 void
deleteCell(ConcreteCell * cell)73 ConcreteLibrary::deleteCell(ConcreteCell *cell)
74 {
75 cell_map_.erase(cell->name());
76 delete cell;
77 }
78
79 ConcreteLibraryCellIterator *
cellIterator() const80 ConcreteLibrary::cellIterator() const
81 {
82 return new ConcreteLibraryCellIterator(cell_map_);
83 }
84
85 ConcreteCell *
findCell(const char * name) const86 ConcreteLibrary::findCell(const char *name) const
87 {
88 return cell_map_.findKey(name);
89 }
90
91 void
findCellsMatching(const PatternMatch * pattern,CellSeq * cells) const92 ConcreteLibrary::findCellsMatching(const PatternMatch *pattern,
93 CellSeq *cells) const
94 {
95 ConcreteLibraryCellIterator cell_iter=ConcreteLibraryCellIterator(cell_map_);
96 while (cell_iter.hasNext()) {
97 ConcreteCell *cell = cell_iter.next();
98 if (pattern->match(cell->name()))
99 cells->push_back(reinterpret_cast<Cell*>(cell));
100 }
101 }
102
103 void
setBusBrkts(char left,char right)104 ConcreteLibrary::setBusBrkts(char left,
105 char right)
106 {
107 bus_brkt_left_ = left;
108 bus_brkt_right_ = right;
109 }
110
111 ////////////////////////////////////////////////////////////////
112
ConcreteCell(ConcreteLibrary * library,const char * name,bool is_leaf,const char * filename)113 ConcreteCell::ConcreteCell(ConcreteLibrary *library,
114 const char *name,
115 bool is_leaf,
116 const char *filename):
117 library_(library),
118 name_(stringCopy(name)),
119 filename_(stringCopy(filename)),
120 liberty_cell_(nullptr),
121 ext_cell_(nullptr),
122 port_bit_count_(0),
123 is_leaf_(is_leaf)
124 {
125 }
126
~ConcreteCell()127 ConcreteCell::~ConcreteCell()
128 {
129 stringDelete(name_);
130 if (filename_)
131 stringDelete(filename_);
132 ports_.deleteContents();
133 }
134
135 void
setName(const char * name)136 ConcreteCell::setName(const char *name)
137 {
138 const char *name_cpy = stringCopy(name);
139 library_->renameCell(this, name_cpy);
140 stringDelete(name_);
141 name_ = name_cpy;
142 }
143
144 void
setLibertyCell(LibertyCell * cell)145 ConcreteCell::setLibertyCell(LibertyCell *cell)
146 {
147 liberty_cell_ = cell;
148 }
149
150 void
setExtCell(void * ext_cell)151 ConcreteCell::setExtCell(void *ext_cell)
152 {
153 ext_cell_ = ext_cell;
154 }
155
156 ConcretePort *
makePort(const char * name)157 ConcreteCell::makePort(const char *name)
158 {
159 ConcretePort *port = new ConcretePort(this, name, false, -1, -1, false, nullptr);
160 addPort(port);
161 return port;
162 }
163
164 ConcretePort *
makeBundlePort(const char * name,ConcretePortSeq * members)165 ConcreteCell::makeBundlePort(const char *name,
166 ConcretePortSeq *members)
167 {
168 ConcretePort *port = new ConcretePort(this, name, false, -1, -1,
169 true, members);
170 addPort(port);
171 return port;
172 }
173
174 ConcretePort *
makeBusPort(const char * name,int from_index,int to_index)175 ConcreteCell::makeBusPort(const char *name,
176 int from_index,
177 int to_index)
178 {
179 ConcretePort *port = new ConcretePort(this, name, true, from_index, to_index,
180 false, new ConcretePortSeq);
181 addPort(port);
182 makeBusPortBits(port, name, from_index, to_index);
183 return port;
184 }
185
186 ConcretePort *
makeBusPort(const char * name,int from_index,int to_index,ConcretePortSeq * members)187 ConcreteCell::makeBusPort(const char *name,
188 int from_index,
189 int to_index,
190 ConcretePortSeq *members)
191 {
192 ConcretePort *port = new ConcretePort(this, name, true, from_index, to_index,
193 false, members);
194 addPort(port);
195 return port;
196 }
197
198 void
makeBusPortBits(ConcretePort * bus_port,const char * name,int from_index,int to_index)199 ConcreteCell::makeBusPortBits(ConcretePort *bus_port,
200 const char *name,
201 int from_index,
202 int to_index)
203 {
204 if (from_index < to_index) {
205 for (int index = from_index; index <= to_index; index++)
206 makeBusPortBit(bus_port, name, index);
207 }
208 else {
209 for (int index = from_index; index >= to_index; index--)
210 makeBusPortBit(bus_port, name, index);
211 }
212 }
213
214 void
makeBusPortBit(ConcretePort * bus_port,const char * bus_name,int bit_index)215 ConcreteCell::makeBusPortBit(ConcretePort *bus_port,
216 const char *bus_name,
217 int bit_index)
218 {
219 string bit_name;
220 stringPrint(bit_name, "%s%c%d%c",
221 bus_name,
222 library_->busBrktLeft(),
223 bit_index,
224 library_->busBrktRight());
225 ConcretePort *port = makePort(bit_name.c_str(), bit_index);
226 bus_port->addPortBit(port);
227 addPortBit(port);
228 }
229
230 ConcretePort *
makePort(const char * bit_name,int bit_index)231 ConcreteCell::makePort(const char *bit_name,
232 int bit_index)
233 {
234 ConcretePort *port = new ConcretePort(this, bit_name, false, bit_index,
235 bit_index, false, nullptr);
236 addPortBit(port);
237 return port;
238 }
239
240 void
addPortBit(ConcretePort * port)241 ConcreteCell::addPortBit(ConcretePort *port)
242 {
243 port_map_[port->name()] = port;
244 port->setPinIndex(port_bit_count_++);
245 }
246
247 void
addPort(ConcretePort * port)248 ConcreteCell::addPort(ConcretePort *port)
249 {
250 port_map_[port->name()] = port;
251 ports_.push_back(port);
252 if (!port->hasMembers())
253 port->setPinIndex(port_bit_count_++);
254 }
255
256 void
setIsLeaf(bool is_leaf)257 ConcreteCell::setIsLeaf(bool is_leaf)
258 {
259 is_leaf_ = is_leaf;
260 }
261
262 ConcretePort *
findPort(const char * name) const263 ConcreteCell::findPort(const char *name) const
264 {
265 return port_map_.findKey(name);
266 }
267
268 size_t
portCount() const269 ConcreteCell::portCount() const
270 {
271 return ports_.size();
272 }
273
274 void
findPortsMatching(const PatternMatch * pattern,PortSeq * ports) const275 ConcreteCell::findPortsMatching(const PatternMatch *pattern,
276 PortSeq *ports) const
277 {
278 char bus_brkt_right = library_->busBrktRight();
279 const char *pattern1 = pattern->pattern();
280 bool bus_pattern = (pattern1[strlen(pattern1) - 1] == bus_brkt_right);
281 ConcreteCellPortIterator *port_iter = portIterator();
282 while (port_iter->hasNext()) {
283 ConcretePort *port = port_iter->next();
284 if (port->isBus() && bus_pattern) {
285 ConcretePortMemberIterator *member_iter = port->memberIterator();
286 while (member_iter->hasNext()) {
287 ConcretePort *port_bit = member_iter->next();
288 if (pattern->match(port_bit->name()))
289 ports->push_back(reinterpret_cast<Port*>(port_bit));
290 }
291 delete member_iter;
292 }
293 else if (pattern->match(port->name()))
294 ports->push_back(reinterpret_cast<Port*>(port));
295 }
296 delete port_iter;
297 }
298
299 ConcreteCellPortIterator *
portIterator() const300 ConcreteCell::portIterator() const
301 {
302 return new ConcreteCellPortIterator(ports_);
303 }
304
305 ConcreteCellPortBitIterator *
portBitIterator() const306 ConcreteCell::portBitIterator() const
307 {
308 return new ConcreteCellPortBitIterator(this);
309 }
310
311 ////////////////////////////////////////////////////////////////
312
313 class BusPort
314 {
315 public:
316 BusPort(const char *name,
317 int from,
318 PortDirection *direction);
319 ~BusPort();
name() const320 const char *name() const { return name_; }
321 void pushMember(ConcretePort *port);
322 void setFrom(int from);
323 void setTo(int to);
from() const324 int from() const { return from_; }
to() const325 int to() const { return to_; }
members()326 ConcretePortSeq *members() { return members_; }
direction()327 PortDirection *direction() { return direction_; }
328
329 private:
330 DISALLOW_COPY_AND_ASSIGN(BusPort);
331
332 const char *name_;
333 int from_;
334 int to_;
335 PortDirection *direction_;
336 ConcretePortSeq *members_;
337 };
338
BusPort(const char * name,int from,PortDirection * direction)339 BusPort::BusPort(const char *name,
340 int from,
341 PortDirection *direction) :
342 name_(name),
343 from_(from),
344 to_(from),
345 direction_(direction),
346 members_(new ConcretePortSeq)
347 {
348 }
349
~BusPort()350 BusPort::~BusPort()
351 {
352 // members_ ownership is transfered to bus port.
353 stringDelete(name_);
354 }
355
356 void
pushMember(ConcretePort * port)357 BusPort::pushMember(ConcretePort *port)
358 {
359 members_->push_back(port);
360 }
361
362 void
setFrom(int from)363 BusPort::setFrom(int from)
364 {
365 from_ = from;
366 }
367
368 void
setTo(int to)369 BusPort::setTo(int to)
370 {
371 to_ = to;
372 }
373
374 typedef Map<const char*, BusPort*, CharPtrLess> BusPortMap;
375
376 void
groupBusPorts(const char bus_brkt_left,const char bus_brkt_right)377 ConcreteCell::groupBusPorts(const char bus_brkt_left,
378 const char bus_brkt_right)
379 {
380 const char bus_brkts_left[2]{bus_brkt_left, '\0'};
381 const char bus_brkts_right[2]{bus_brkt_right, '\0'};
382 BusPortMap port_map;
383 // Find ungrouped bus ports.
384 // Remove bus bit ports from the ports_ vector during the scan by
385 // keeping an index to the next insertion index and skipping over
386 // the ones we want to remove.
387 ConcretePortSeq ports = ports_;
388 ports_.clear();
389 for (ConcretePort *port : ports) {
390 const char *port_name = port->name();
391 char *bus_name;
392 int index;
393 parseBusName(port_name, bus_brkts_left, bus_brkts_right, escape_,
394 bus_name, index);
395 if (bus_name) {
396 if (!port->isBusBit()) {
397 BusPort *bus_port = port_map.findKey(bus_name);
398 if (bus_port) {
399 // Treat it as [max:min]/[from:to], ie downto.
400 bus_port->setFrom(std::max(index, bus_port->from()));
401 bus_port->setTo(std::min(index, bus_port->to()));
402 stringDelete(bus_name);
403 }
404 else {
405 bus_port = new BusPort(bus_name, index, port->direction());
406 port_map[bus_name] = bus_port;
407 }
408 bus_port->pushMember(port);
409 }
410 else
411 ports_.push_back(port);
412 }
413 else
414 ports_.push_back(port);
415 }
416
417 // Make the bus ports.
418 BusPortMap::Iterator bus_iter(port_map);
419 while (bus_iter.hasNext()) {
420 BusPort *bus_port = bus_iter.next();
421 const char *bus_name = bus_port->name();
422 ConcretePortSeq *members = bus_port->members();
423 sort(members, [&](ConcretePort *port1,
424 ConcretePort *port2) {
425 char *bus_name;
426 int index1, index2;
427 parseBusName(port1->name(), bus_brkts_left, bus_brkts_right, escape_,
428 bus_name, index1);
429 stringDelete(bus_name);
430 parseBusName(port2->name(), bus_brkts_left, bus_brkts_right, escape_,
431 bus_name, index2);
432 stringDelete(bus_name);
433 return index1 > index2;
434 });
435 ConcretePort *port = makeBusPort(bus_name, bus_port->from(),
436 bus_port->to(), members);
437 port->setDirection(bus_port->direction());
438 delete bus_port;
439
440 for (ConcretePort *port : *members) {
441 char *bus_name;
442 int index;
443 parseBusName(port->name(), bus_brkts_left, bus_brkts_right, escape_,
444 bus_name, index);
445 port->setBusBitIndex(index);
446 stringDelete(bus_name);
447 }
448 }
449 }
450
451 ////////////////////////////////////////////////////////////////
452
ConcretePort(ConcreteCell * cell,const char * name,bool is_bus,int from_index,int to_index,bool is_bundle,ConcretePortSeq * member_ports)453 ConcretePort::ConcretePort(ConcreteCell *cell,
454 const char *name,
455 bool is_bus,
456 int from_index,
457 int to_index,
458 bool is_bundle,
459 ConcretePortSeq *member_ports) :
460 name_(stringCopy(name)),
461 cell_(cell),
462 direction_(PortDirection::unknown()),
463 liberty_port_(nullptr),
464 ext_port_(nullptr),
465 pin_index_(-1),
466 is_bundle_(is_bundle),
467 is_bus_(is_bus),
468 from_index_(from_index),
469 to_index_(to_index),
470 member_ports_(member_ports)
471 {
472 }
473
~ConcretePort()474 ConcretePort::~ConcretePort()
475 {
476 // The member ports of a bus are owned by the bus port.
477 // The member ports of a bundle are NOT owned by the bus port.
478 if (is_bus_)
479 member_ports_->deleteContents();
480 delete member_ports_;
481 stringDelete(name_);
482 }
483
484 Cell *
cell() const485 ConcretePort::cell() const
486 {
487 return reinterpret_cast<Cell*>(cell_);
488 }
489
490 void
setLibertyPort(LibertyPort * port)491 ConcretePort::setLibertyPort(LibertyPort *port)
492 {
493 liberty_port_ = port;
494 }
495
496 void
setExtPort(void * port)497 ConcretePort::setExtPort(void *port)
498 {
499 ext_port_ = port;
500 }
501
502 const char *
busName() const503 ConcretePort::busName() const
504 {
505 if (is_bus_) {
506 ConcreteLibrary *lib = cell_->library();
507 return stringPrintTmp("%s%c%d:%d%c",
508 name_,
509 lib->busBrktLeft(),
510 from_index_,
511 to_index_,
512 lib->busBrktRight());
513 }
514 else
515 return name_;
516 }
517
518 ConcretePort *
findMember(int index) const519 ConcretePort::findMember(int index) const
520 {
521 return (*member_ports_)[index];
522 }
523
524 bool
isBusBit() const525 ConcretePort::isBusBit() const
526 {
527 return from_index_ != -1
528 && from_index_ == to_index_;
529 }
530
531 void
setBusBitIndex(int index)532 ConcretePort::setBusBitIndex(int index)
533 {
534 from_index_ = to_index_ = index;
535 }
536
537 int
size() const538 ConcretePort::size() const
539 {
540 if (is_bus_)
541 return abs(to_index_ - from_index_) + 1;
542 else if (is_bundle_)
543 return static_cast<int>(member_ports_->size());
544 else
545 return 1;
546 }
547
548 void
setPinIndex(int index)549 ConcretePort::setPinIndex(int index)
550 {
551 pin_index_ = index;
552 }
553
554 void
setDirection(PortDirection * dir)555 ConcretePort::setDirection(PortDirection *dir)
556 {
557 direction_ = dir;
558 if (hasMembers()) {
559 ConcretePortMemberIterator *member_iter = memberIterator();
560 while (member_iter->hasNext()) {
561 ConcretePort *port_bit = member_iter->next();
562 port_bit->setDirection(dir);
563 }
564 delete member_iter;
565 }
566 }
567
568 void
addPortBit(ConcretePort * port)569 ConcretePort::addPortBit(ConcretePort *port)
570 {
571 member_ports_->push_back(port);
572 }
573
574 ConcretePort *
findBusBit(int index) const575 ConcretePort::findBusBit(int index) const
576 {
577 if (from_index_ < to_index_
578 && index <= to_index_
579 && index >= from_index_)
580 return (*member_ports_)[index - from_index_];
581 else if (from_index_ >= to_index_
582 && index >= to_index_
583 && index <= from_index_)
584 return (*member_ports_)[from_index_ - index];
585 else
586 return nullptr;
587 }
588
589 bool
busIndexInRange(int index) const590 ConcretePort::busIndexInRange(int index) const
591 {
592 return (from_index_ <= to_index_
593 && index <= to_index_
594 && index >= from_index_)
595 || (from_index_ > to_index_
596 && index >= to_index_
597 && index <= from_index_);
598 }
599
600 bool
hasMembers() const601 ConcretePort::hasMembers() const
602 {
603 return is_bus_ || is_bundle_;
604 }
605
606 ConcretePortMemberIterator *
memberIterator() const607 ConcretePort::memberIterator() const
608 {
609 return new ConcretePortMemberIterator(member_ports_);
610 }
611
612 ////////////////////////////////////////////////////////////////
613
ConcreteCellPortBitIterator(const ConcreteCell * cell)614 ConcreteCellPortBitIterator::ConcreteCellPortBitIterator(const ConcreteCell*
615 cell) :
616 port_iter_(cell->ports_),
617 member_iter_(nullptr),
618 next_(nullptr)
619 {
620 findNext();
621 }
622
623 bool
hasNext()624 ConcreteCellPortBitIterator::hasNext()
625 {
626 return next_ != nullptr;
627 }
628
629 ConcretePort *
next()630 ConcreteCellPortBitIterator::next()
631 {
632 ConcretePort *next = next_;
633 findNext();
634 return next;
635 }
636
637 void
findNext()638 ConcreteCellPortBitIterator::findNext()
639 {
640 if (member_iter_) {
641 if (member_iter_->hasNext()) {
642 next_ = member_iter_->next();
643 return;
644 }
645 else {
646 delete member_iter_;
647 member_iter_ = nullptr;
648 }
649 }
650 while (port_iter_.hasNext()) {
651 ConcretePort *next = port_iter_.next();
652 if (next->isBus()) {
653 member_iter_ = next->memberIterator();
654 next_ = member_iter_->next();
655 return;
656 }
657 else if (!next->isBundle()) {
658 next_ = next;
659 return;
660 }
661 next_ = nullptr;
662 }
663 next_ = nullptr;
664 }
665
666 } // namespace
667