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 "HpinDrvrLoad.hh"
18
19 #include <stdio.h>
20
21 #include "Network.hh"
22
23 namespace sta {
24
25 static void
26 visitPinsAboveNet2(const Pin *hpin,
27 Net *above_net,
28 NetSet &visited,
29 HpinDrvrLoads &above_drvrs,
30 HpinDrvrLoads &above_loads,
31 PinSet *hpin_path,
32 const Network *network);
33 static void
34 visitPinsBelowNet2(const Pin *hpin,
35 Net *above_net,
36 Net *below_net,
37 NetSet &visited,
38 HpinDrvrLoads &below_drvrs,
39 HpinDrvrLoads &below_loads,
40 PinSet *hpin_path,
41 const Network *network);
42 static void
43 visitHpinDrvrLoads(HpinDrvrLoads drvrs,
44 HpinDrvrLoads loads,
45 HpinDrvrLoadVisitor *visitor);
46
47 void
visitHpinDrvrLoads(const Pin * pin,const Network * network,HpinDrvrLoadVisitor * visitor)48 visitHpinDrvrLoads(const Pin *pin,
49 const Network *network,
50 HpinDrvrLoadVisitor *visitor)
51 {
52 NetSet visited;
53 HpinDrvrLoads above_drvrs;
54 HpinDrvrLoads above_loads;
55 PinSet hpin_path;
56 Net *above_net = network->net(pin);
57 if (above_net) {
58 visitPinsAboveNet2(pin, above_net, visited,
59 above_drvrs, above_loads,
60 &hpin_path, network);
61 }
62
63 // Search down from hpin terminal.
64 HpinDrvrLoads below_drvrs;
65 HpinDrvrLoads below_loads;
66 Term *term = network->term(pin);
67 if (term) {
68 Net *below_net = network->net(term);
69 if (below_net)
70 visitPinsBelowNet2(pin, above_net, below_net, visited,
71 below_drvrs, below_loads,
72 &hpin_path, network);
73 }
74 if (network->isHierarchical(pin)) {
75 visitHpinDrvrLoads(above_drvrs, below_loads, visitor);
76 visitHpinDrvrLoads(below_drvrs, above_loads, visitor);
77 }
78 else {
79 if (network->isDriver(pin)) {
80 HpinDrvrLoad drvr(const_cast<Pin*>(pin), nullptr, &hpin_path, nullptr);
81 HpinDrvrLoads drvrs;
82 drvrs.insert(&drvr);
83 visitHpinDrvrLoads(drvrs, below_loads, visitor);
84 visitHpinDrvrLoads(drvrs, above_loads, visitor);
85 }
86 // Bidirects are drivers and loads.
87 if (network->isLoad(pin)) {
88 HpinDrvrLoad load(nullptr, const_cast<Pin*>(pin), nullptr, &hpin_path);
89 HpinDrvrLoads loads;
90 loads.insert(&load);
91 visitHpinDrvrLoads(below_drvrs, loads, visitor);
92 visitHpinDrvrLoads(above_drvrs, loads, visitor);
93 }
94 }
95 above_drvrs.deleteContents();
96 above_loads.deleteContents();
97 below_drvrs.deleteContents();
98 below_loads.deleteContents();
99 }
100
101 static void
visitPinsAboveNet2(const Pin * hpin,Net * above_net,NetSet & visited,HpinDrvrLoads & above_drvrs,HpinDrvrLoads & above_loads,PinSet * hpin_path,const Network * network)102 visitPinsAboveNet2(const Pin *hpin,
103 Net *above_net,
104 NetSet &visited,
105 HpinDrvrLoads &above_drvrs,
106 HpinDrvrLoads &above_loads,
107 PinSet *hpin_path,
108 const Network *network)
109 {
110 visited.insert(above_net);
111 // Visit above net pins.
112 NetPinIterator *pin_iter = network->pinIterator(above_net);
113 while (pin_iter->hasNext()) {
114 Pin *above_pin = pin_iter->next();
115 if (above_pin != hpin) {
116 if (network->isDriver(above_pin)) {
117 HpinDrvrLoad *drvr = new HpinDrvrLoad(above_pin, nullptr,
118 hpin_path, nullptr);
119 above_drvrs.insert(drvr);
120 }
121 if (network->isLoad(above_pin)) {
122 HpinDrvrLoad *load = new HpinDrvrLoad(nullptr, above_pin,
123 nullptr, hpin_path);
124 above_loads.insert(load);
125 }
126 Term *above_term = network->term(above_pin);
127 if (above_term) {
128 Net *above_net1 = network->net(above_term);
129 if (above_net1 && !visited.hasKey(above_net1)) {
130 hpin_path->insert(above_pin);
131 visitPinsAboveNet2(above_pin, above_net1, visited,
132 above_drvrs, above_loads,
133 hpin_path, network);
134 hpin_path->erase(above_pin);
135 }
136 }
137 }
138 }
139 delete pin_iter;
140
141 // Search up from net terminals.
142 NetTermIterator *term_iter = network->termIterator(above_net);
143 while (term_iter->hasNext()) {
144 Term *term = term_iter->next();
145 Pin *above_pin = network->pin(term);
146 if (above_pin
147 && above_pin != hpin) {
148 Net *above_net1 = network->net(above_pin);
149 if (above_net1 && !visited.hasKey(above_net1)) {
150 hpin_path->insert(above_pin);
151 visitPinsAboveNet2(above_pin, above_net1, visited,
152 above_drvrs, above_loads,
153 hpin_path, network);
154 hpin_path->erase(above_pin);
155 }
156
157 if (network->isDriver(above_pin)) {
158 HpinDrvrLoad *drvr = new HpinDrvrLoad(above_pin, nullptr,
159 hpin_path, nullptr);
160 above_drvrs.insert(drvr);
161 }
162 if (network->isLoad(above_pin)) {
163 HpinDrvrLoad *load = new HpinDrvrLoad(nullptr, above_pin,
164 nullptr, hpin_path);
165 above_loads.insert(load);
166 }
167 }
168 }
169 delete term_iter;
170 }
171
172 static void
visitPinsBelowNet2(const Pin * hpin,Net * above_net,Net * below_net,NetSet & visited,HpinDrvrLoads & below_drvrs,HpinDrvrLoads & below_loads,PinSet * hpin_path,const Network * network)173 visitPinsBelowNet2(const Pin *hpin,
174 Net *above_net,
175 Net *below_net,
176 NetSet &visited,
177 HpinDrvrLoads &below_drvrs,
178 HpinDrvrLoads &below_loads,
179 PinSet *hpin_path,
180 const Network *network)
181 {
182 visited.insert(below_net);
183 // Visit below net pins.
184 NetPinIterator *pin_iter = network->pinIterator(below_net);
185 while (pin_iter->hasNext()) {
186 Pin *below_pin = pin_iter->next();
187 if (below_pin != hpin) {
188 if (above_net && !visited.hasKey(above_net))
189 visitPinsAboveNet2(below_pin, above_net,
190 visited, below_drvrs, below_loads,
191 hpin_path, network);
192 if (network->isDriver(below_pin)) {
193 HpinDrvrLoad *drvr = new HpinDrvrLoad(below_pin, nullptr,
194 hpin_path, nullptr);
195 below_drvrs.insert(drvr);
196 }
197 if (network->isLoad(below_pin)) {
198 HpinDrvrLoad *load = new HpinDrvrLoad(nullptr, below_pin,
199 nullptr, hpin_path);
200 below_loads.insert(load);
201 }
202 if (network->isHierarchical(below_pin)) {
203 Term *term = network->term(below_pin);
204 if (term) {
205 Net *below_net1 = network->net(term);
206 if (below_net1 && !visited.hasKey(below_net1)) {
207 hpin_path->insert(below_pin);
208 visitPinsBelowNet2(below_pin, below_net, below_net1, visited,
209 below_drvrs, below_loads,
210 hpin_path, network);
211 hpin_path->erase(below_pin);
212 }
213 }
214 }
215 }
216 }
217 delete pin_iter;
218
219 // Search up from net terminals.
220 NetTermIterator *term_iter = network->termIterator(below_net);
221 while (term_iter->hasNext()) {
222 Term *term = term_iter->next();
223 Pin *above_pin = network->pin(term);
224 if (above_pin
225 && above_pin != hpin) {
226 Net *above_net1 = network->net(above_pin);
227 if (above_net1 && !visited.hasKey(above_net1)) {
228 hpin_path->insert(above_pin);
229 visitPinsAboveNet2(above_pin, above_net1,
230 visited, below_drvrs, below_loads,
231 hpin_path, network);
232 hpin_path->erase(above_pin);
233 }
234 }
235 }
236 delete term_iter;
237 }
238
239 static void
visitHpinDrvrLoads(HpinDrvrLoads drvrs,HpinDrvrLoads loads,HpinDrvrLoadVisitor * visitor)240 visitHpinDrvrLoads(HpinDrvrLoads drvrs,
241 HpinDrvrLoads loads,
242 HpinDrvrLoadVisitor *visitor)
243 {
244 HpinDrvrLoads::Iterator drvr_iter(drvrs);
245 while (drvr_iter.hasNext()) {
246 HpinDrvrLoad *drvr = drvr_iter.next();
247 HpinDrvrLoads::Iterator load_iter(loads);
248 while (load_iter.hasNext()) {
249 HpinDrvrLoad *load = load_iter.next();
250 HpinDrvrLoad clone(drvr->drvr(),
251 load->load(),
252 drvr->hpinsFromDrvr(),
253 load->hpinsToLoad());
254 visitor->visit(&clone);
255 }
256 }
257 }
258
259 ////////////////////////////////////////////////////////////////
260
HpinDrvrLoad(Pin * drvr,Pin * load,PinSet * hpins_from_drvr,PinSet * hpins_to_load)261 HpinDrvrLoad::HpinDrvrLoad(Pin *drvr,
262 Pin *load,
263 PinSet *hpins_from_drvr,
264 PinSet *hpins_to_load) :
265 drvr_(drvr),
266 load_(load),
267 hpins_from_drvr_(hpins_from_drvr ? new PinSet(*hpins_from_drvr) : nullptr),
268 hpins_to_load_(hpins_to_load ? new PinSet(*hpins_to_load) : nullptr)
269 {
270 }
271
HpinDrvrLoad(Pin * drvr,Pin * load)272 HpinDrvrLoad::HpinDrvrLoad(Pin *drvr,
273 Pin *load) :
274 drvr_(drvr),
275 load_(load)
276 {
277 }
278
~HpinDrvrLoad()279 HpinDrvrLoad::~HpinDrvrLoad()
280 {
281 delete hpins_from_drvr_;
282 delete hpins_to_load_;
283 }
284
285 void
report(const Network * network)286 HpinDrvrLoad::report(const Network *network)
287 {
288 printf("%s -> %s: ",
289 drvr_ ? network->pathName(drvr_) : "-",
290 load_ ? network->pathName(load_) : "-");
291 PinSet::Iterator pin_iter(hpins_from_drvr_);
292 while (pin_iter.hasNext()) {
293 Pin *pin = pin_iter.next();
294 printf("%s ", network->pathName(pin));
295 }
296 printf("* ");
297 PinSet::Iterator pin_iter2(hpins_to_load_);
298 while (pin_iter2.hasNext()) {
299 Pin *pin = pin_iter2.next();
300 printf("%s ", network->pathName(pin));
301 }
302 printf("\n");
303 }
304
305 void
setDrvr(Pin * drvr)306 HpinDrvrLoad::setDrvr(Pin *drvr)
307 {
308 drvr_ = drvr;
309 }
310
311 bool
operator ()(const HpinDrvrLoad * drvr_load1,const HpinDrvrLoad * drvr_load2) const312 HpinDrvrLoadLess::operator()(const HpinDrvrLoad *drvr_load1,
313 const HpinDrvrLoad *drvr_load2) const
314 {
315 Pin *load1 = drvr_load1->load();
316 Pin *load2 = drvr_load2->load();
317 if (load1 == load2) {
318 Pin *drvr1 = drvr_load1->drvr();
319 Pin *drvr2 = drvr_load2->drvr();
320 return drvr1 < drvr2;
321 }
322 else
323 return load1 < load2;
324 }
325
326 } // namespace
327