1 // -*- mode: C++; c-file-style: "cc-mode" -*-
2 //*************************************************************************
3 // DESCRIPTION: Verilator: Ast node structures
4 //
5 // Code available from: https://verilator.org
6 //
7 //*************************************************************************
8 //
9 // Copyright 2003-2021 by Wilson Snyder. This program is free software; you
10 // can redistribute it and/or modify it under the terms of either the GNU
11 // Lesser General Public License Version 3 or the Perl Artistic License
12 // Version 2.0.
13 // SPDX-License-Identifier: LGPL-3.0-only OR Artistic-2.0
14 //
15 //*************************************************************************
16
17 #include "config_build.h"
18 #include "verilatedos.h"
19
20 #include "V3Ast.h"
21 #include "V3File.h"
22 #include "V3Global.h"
23 #include "V3Broken.h"
24 #include "V3String.h"
25
26 #include <iomanip>
27 #include <memory>
28
29 //======================================================================
30 // Statics
31
32 vluint64_t AstNode::s_editCntLast = 0;
33 vluint64_t AstNode::s_editCntGbl = 0; // Hot cache line
34
35 // To allow for fast clearing of all user pointers, we keep a "timestamp"
36 // along with each userp, and thus by bumping this count we can make it look
37 // as if we iterated across the entire tree to set all the userp's to null.
38 int AstNode::s_cloneCntGbl = 0;
39 uint32_t AstUser1InUse::s_userCntGbl = 0; // Hot cache line, leave adjacent
40 uint32_t AstUser2InUse::s_userCntGbl = 0; // Hot cache line, leave adjacent
41 uint32_t AstUser3InUse::s_userCntGbl = 0; // Hot cache line, leave adjacent
42 uint32_t AstUser4InUse::s_userCntGbl = 0; // Hot cache line, leave adjacent
43 uint32_t AstUser5InUse::s_userCntGbl = 0; // Hot cache line, leave adjacent
44
45 bool AstUser1InUse::s_userBusy = false;
46 bool AstUser2InUse::s_userBusy = false;
47 bool AstUser3InUse::s_userBusy = false;
48 bool AstUser4InUse::s_userBusy = false;
49 bool AstUser5InUse::s_userBusy = false;
50
51 int AstNodeDType::s_uniqueNum = 0;
52
53 //######################################################################
54 // V3AstType
55
56 std::ostream& operator<<(std::ostream& os, AstType rhs);
57
58 //######################################################################
59 // Creators
60
AstNode(AstType t,FileLine * fl)61 AstNode::AstNode(AstType t, FileLine* fl)
62 : m_type{t}
63 , m_fileline{fl} {
64 editCountInc();
65 m_nextp = nullptr;
66 m_backp = nullptr;
67 m_headtailp = this; // When made, we're a list of only a single element
68 m_op1p = nullptr;
69 m_op2p = nullptr;
70 m_op3p = nullptr;
71 m_op4p = nullptr;
72 m_iterpp = nullptr;
73 m_dtypep = nullptr;
74 m_clonep = nullptr;
75 m_cloneCnt = 0;
76 // Attributes
77 m_flags.didWidth = false;
78 m_flags.doingWidth = false;
79 m_flags.protect = true;
80 m_flags.unused = 0; // Initializing this avoids a read-modify-write on construction
81 m_user1u = VNUser(0);
82 m_user1Cnt = 0;
83 m_user2u = VNUser(0);
84 m_user2Cnt = 0;
85 m_user3u = VNUser(0);
86 m_user3Cnt = 0;
87 m_user4u = VNUser(0);
88 m_user4Cnt = 0;
89 m_user5u = VNUser(0);
90 m_user5Cnt = 0;
91 }
92
abovep() const93 AstNode* AstNode::abovep() const {
94 // m_headtailp only valid at beginning or end of list
95 // Avoid supporting at other locations as would require walking
96 // list which is likely to cause performance issues.
97 UASSERT_OBJ(!m_nextp || firstAbovep(), this, "abovep() not allowed when in midlist");
98 const AstNode* const firstp = firstAbovep() ? this : m_headtailp;
99 return firstp->backp();
100 }
101
encodeName(const string & namein)102 string AstNode::encodeName(const string& namein) {
103 // Encode signal name raw from parser, then not called again on same signal
104 string out;
105 for (string::const_iterator pos = namein.begin(); pos != namein.end(); ++pos) {
106 if ((pos == namein.begin()) ? isalpha(pos[0]) // digits can't lead identifiers
107 : isalnum(pos[0])) {
108 out += pos[0];
109 } else if (pos[0] == '_') {
110 if (pos[1] == '_') {
111 out += "_";
112 out += "__05F"; // hex(_) = 0x5F
113 ++pos;
114 if (pos == namein.end()) break;
115 } else {
116 out += pos[0];
117 }
118 } else {
119 // Need the leading 0 so this will never collide with
120 // a user identifier nor a temp we create in Verilator.
121 // We also do *NOT* use __DOT__ etc, as we search for those
122 // in some replacements, and don't want to mangle the user's names.
123 const unsigned val = pos[0] & 0xff; // Mask to avoid sign extension
124 std::stringstream hex;
125 hex << std::setfill('0') << std::setw(2) << std::hex << val;
126 out += "__0" + hex.str();
127 }
128 }
129 // Shorten names
130 // TODO long term use VName in place of "string name"
131 // Then we also won't need to save the table of hased values
132 VName vname{out};
133 return vname.hashedName();
134 }
135
encodeNumber(vlsint64_t num)136 string AstNode::encodeNumber(vlsint64_t num) {
137 if (num < 0) {
138 return "__02D" + cvtToStr(-num); // 2D=-
139 } else {
140 return cvtToStr(num);
141 }
142 }
143
nameProtect() const144 string AstNode::nameProtect() const { return VIdProtect::protectIf(name(), protect()); }
origNameProtect() const145 string AstNode::origNameProtect() const { return VIdProtect::protectIf(origName(), protect()); }
146
shortName() const147 string AstNode::shortName() const {
148 string pretty = name();
149 string::size_type pos;
150 while ((pos = pretty.find("__PVT__")) != string::npos) pretty.replace(pos, 7, "");
151 return pretty;
152 }
153
dedotName(const string & namein)154 string AstNode::dedotName(const string& namein) {
155 string pretty = namein;
156 string::size_type pos;
157 while ((pos = pretty.find("__DOT__")) != string::npos) pretty.replace(pos, 7, ".");
158 if (pretty.substr(0, 4) == "TOP.") pretty.replace(0, 4, "");
159 return pretty;
160 }
161
vcdName(const string & namein)162 string AstNode::vcdName(const string& namein) {
163 // VCD tracing expects space to separate hierarchy
164 // Dots are reserved for dots the user put in the name
165 // We earlier hashed all symbols, dehash them so user sees real name
166 string pretty{VName::dehash(namein)};
167 string::size_type pos;
168 while ((pos = pretty.find("__DOT__")) != string::npos) pretty.replace(pos, 7, " ");
169 while ((pos = pretty.find('.')) != string::npos) pretty.replace(pos, 1, " ");
170 // Now convert escaped special characters, etc
171 return prettyName(pretty);
172 }
173
prettyName(const string & namein)174 string AstNode::prettyName(const string& namein) {
175 // This function is somewhat hot, so we short-circuit some compares
176 string pretty;
177 pretty = "";
178 pretty.reserve(namein.length());
179 for (const char* pos = namein.c_str(); *pos;) {
180 if (pos[0] == '-' && pos[1] == '>') { // ->
181 pretty += ".";
182 pos += 2;
183 continue;
184 }
185 if (pos[0] == '_' && pos[1] == '_') { // Short-circuit
186 if (0 == strncmp(pos, "__BRA__", 7)) {
187 pretty += "[";
188 pos += 7;
189 continue;
190 }
191 if (0 == strncmp(pos, "__KET__", 7)) {
192 pretty += "]";
193 pos += 7;
194 continue;
195 }
196 if (0 == strncmp(pos, "__DOT__", 7)) {
197 pretty += ".";
198 pos += 7;
199 continue;
200 }
201 if (0 == strncmp(pos, "__PVT__", 7)) {
202 pretty += "";
203 pos += 7;
204 continue;
205 }
206 if (pos[0] == '_' && pos[1] == '_' && pos[2] == '0' && isxdigit(pos[3])
207 && isxdigit(pos[4])) {
208 char value = 0;
209 value += 16 * (isdigit(pos[3]) ? (pos[3] - '0') : (tolower(pos[3]) - 'a' + 10));
210 value += (isdigit(pos[4]) ? (pos[4] - '0') : (tolower(pos[4]) - 'a' + 10));
211 pretty += value;
212 pos += 5;
213 continue;
214 }
215 }
216 // Default
217 pretty += pos[0];
218 ++pos;
219 }
220 if (pretty[0] == 'T' && pretty.substr(0, 4) == "TOP.") pretty.replace(0, 4, "");
221 if (pretty[0] == 'T' && pretty.substr(0, 5) == "TOP->") pretty.replace(0, 5, "");
222 return pretty;
223 }
224
prettyTypeName() const225 string AstNode::prettyTypeName() const {
226 if (name() == "") return typeName();
227 return string(typeName()) + " '" + prettyName() + "'";
228 }
229
230 //######################################################################
231 // Insertion
232
debugTreeChange(const AstNode * nodep,const char * prefix,int lineno,bool next)233 inline void AstNode::debugTreeChange(const AstNode* nodep, const char* prefix, int lineno,
234 bool next){
235 #ifdef VL_DEBUG
236 // Called on all major tree changers.
237 // Only for use for those really nasty bugs relating to internals
238 // Note this may be null.
239 // if (debug()) cout<<"-treeChange: V3Ast.cpp:"<<lineno<<" Tree Change for "
240 // <<prefix<<": "<<cvtToHex(this)<<" <e"<<AstNode::s_editCntGbl<<">"<<endl;
241 // if (debug()) {
242 // cout<<"-treeChange: V3Ast.cpp:"<<lineno<<" Tree Change for "<<prefix<<endl;
243 // // Commenting out the section below may crash, as the tree state
244 // // between edits is not always consistent for printing
245 // cout<<"-treeChange: V3Ast.cpp:"<<lineno<<" Tree Change for "<<prefix<<endl;
246 // v3Global.rootp()->dumpTree(cout, "-treeChange: ");
247 // if (next||1) this->dumpTreeAndNext(cout, prefix);
248 // else this->dumpTree(cout, prefix);
249 // this->checkTree();
250 // v3Global.rootp()->checkTree();
251 //}
252 #endif
253 }
254
addNext(AstNode * nodep,AstNode * newp)255 AstNode* AstNode::addNext(AstNode* nodep, AstNode* newp) {
256 // Add to m_nextp, returns this
257 UDEBUGONLY(UASSERT_OBJ(newp, nodep, "Null item passed to addNext"););
258 debugTreeChange(nodep, "-addNextThs: ", __LINE__, false);
259 debugTreeChange(newp, "-addNextNew: ", __LINE__, true);
260 if (!nodep) { // verilog.y and lots of other places assume this
261 return newp;
262 } else {
263 // Find end of old list
264 AstNode* oldtailp = nodep;
265 if (oldtailp->m_nextp) {
266 if (oldtailp->m_headtailp) {
267 oldtailp = oldtailp->m_headtailp; // This=beginning of list, jump to end
268 UDEBUGONLY(UASSERT_OBJ(!oldtailp->m_nextp, nodep,
269 "Node had next, but headtail says it shouldn't"););
270 } else {
271 // Though inefficient, we are occasionally passed an
272 // addNext in the middle of a list.
273 while (oldtailp->m_nextp) oldtailp = oldtailp->m_nextp;
274 }
275 }
276 // Link it in
277 oldtailp->m_nextp = newp;
278 newp->m_backp = oldtailp;
279 // New tail needs the head
280 AstNode* const newtailp = newp->m_headtailp;
281 AstNode* const headp = oldtailp->m_headtailp;
282 oldtailp->m_headtailp = nullptr; // May be written again as new head
283 newp->m_headtailp = nullptr; // May be written again as new tail
284 newtailp->m_headtailp = headp;
285 headp->m_headtailp = newtailp;
286 newp->editCountInc();
287 if (oldtailp->m_iterpp) *(oldtailp->m_iterpp) = newp; // Iterate on new item
288 }
289 debugTreeChange(nodep, "-addNextOut:", __LINE__, true);
290 return nodep;
291 }
292
addNextNull(AstNode * nodep,AstNode * newp)293 AstNode* AstNode::addNextNull(AstNode* nodep, AstNode* newp) {
294 if (!newp) return nodep;
295 return addNext(nodep, newp);
296 }
297
addNextHere(AstNode * newp)298 void AstNode::addNextHere(AstNode* newp) {
299 // Add to m_nextp on exact node passed, not at the end.
300 // This could be at head, tail, or both (single)
301 // New could be head of single node, or list
302 UASSERT(newp, "Null item passed to addNext");
303 UASSERT(!newp->backp(), "New node (back) already assigned?");
304 debugTreeChange(this, "-addHereThs: ", __LINE__, false);
305 debugTreeChange(newp, "-addHereNew: ", __LINE__, true);
306 newp->editCountInc();
307
308 AstNode* const addlastp = newp->m_headtailp; // Last node in list to be added
309 UASSERT(!addlastp->m_nextp, "Headtailp tail isn't at the tail");
310
311 // Forward links
312 AstNode* const oldnextp = this->m_nextp;
313 this->m_nextp = newp;
314 addlastp->m_nextp = oldnextp; // Perhaps null if 'this' is not list
315
316 // Backward links
317 if (oldnextp) oldnextp->m_backp = addlastp;
318 newp->m_backp = this;
319
320 // Head/tail
321 AstNode* const oldheadtailp = this->m_headtailp;
322 // (!oldheadtailp) // this was&is middle of list
323 // (oldheadtailp==this && !oldnext)// this was head AND tail (one node long list)
324 // (oldheadtailp && oldnextp) // this was&is head of list of not just one node, not
325 // tail (oldheadtailp && !oldnextp) // this was tail of list, might also
326 // be head of one-node list
327 //
328 newp->m_headtailp = nullptr; // Not at head any longer
329 addlastp->m_headtailp = nullptr; // Presume middle of list
330 // newp might happen to be head/tail after all, if so will be set again below
331 if (oldheadtailp) { // else in middle of list, no change
332 if (oldheadtailp == this) { // this was one node
333 this->m_headtailp = addlastp; // Was head/tail, now a tail
334 addlastp->m_headtailp = oldheadtailp; // Tail needs to remember head (or nullptr)
335 } else if (!oldnextp) { // this was tail
336 this->m_headtailp = nullptr; // No longer a tail
337 oldheadtailp->m_headtailp = addlastp; // Head gets new tail
338 addlastp->m_headtailp = oldheadtailp; // Tail needs to remember head (or nullptr)
339 } // else is head, and we're inserting into the middle, so no other change
340 }
341
342 if (this->m_iterpp) *(this->m_iterpp) = newp; // Iterate on new item
343 debugTreeChange(this, "-addHereOut: ", __LINE__, true);
344 }
345
setOp1p(AstNode * newp)346 void AstNode::setOp1p(AstNode* newp) {
347 UASSERT(newp, "Null item passed to setOp1p");
348 UDEBUGONLY(UASSERT_OBJ(!m_op1p, this, "Adding to non-empty, non-list op1"););
349 UDEBUGONLY(UASSERT_OBJ(!newp->m_backp, newp, "Adding already linked node"););
350 UDEBUGONLY(UASSERT_OBJ(!newp->m_nextp, newp, "Adding list to non-list op1"););
351 debugTreeChange(this, "-setOp1pThs: ", __LINE__, false);
352 debugTreeChange(newp, "-setOp1pNew: ", __LINE__, true);
353 m_op1p = newp;
354 newp->editCountInc();
355 newp->m_backp = this;
356 debugTreeChange(this, "-setOp1pOut: ", __LINE__, false);
357 }
358
setOp2p(AstNode * newp)359 void AstNode::setOp2p(AstNode* newp) {
360 UASSERT(newp, "Null item passed to setOp2p");
361 UDEBUGONLY(UASSERT_OBJ(!m_op2p, this, "Adding to non-empty, non-list op2"););
362 UDEBUGONLY(UASSERT_OBJ(!newp->m_backp, newp, "Adding already linked node"););
363 UDEBUGONLY(UASSERT_OBJ(!newp->m_nextp, newp, "Adding list to non-list op2"););
364 debugTreeChange(this, "-setOp2pThs: ", __LINE__, false);
365 debugTreeChange(newp, "-setOp2pNew: ", __LINE__, true);
366 m_op2p = newp;
367 newp->editCountInc();
368 newp->m_backp = this;
369 debugTreeChange(this, "-setOp2pOut: ", __LINE__, false);
370 }
371
setOp3p(AstNode * newp)372 void AstNode::setOp3p(AstNode* newp) {
373 UASSERT(newp, "Null item passed to setOp3p");
374 UDEBUGONLY(UASSERT_OBJ(!m_op3p, this, "Adding to non-empty, non-list op3"););
375 UDEBUGONLY(UASSERT_OBJ(!newp->m_backp, newp, "Adding already linked node"););
376 UDEBUGONLY(UASSERT_OBJ(!newp->m_nextp, newp, "Adding list to non-list op3"););
377 debugTreeChange(this, "-setOp3pThs: ", __LINE__, false);
378 debugTreeChange(newp, "-setOp3pNew: ", __LINE__, true);
379 m_op3p = newp;
380 newp->editCountInc();
381 newp->m_backp = this;
382 debugTreeChange(this, "-setOp3pOut: ", __LINE__, false);
383 }
384
setOp4p(AstNode * newp)385 void AstNode::setOp4p(AstNode* newp) {
386 UASSERT(newp, "Null item passed to setOp4p");
387 UDEBUGONLY(UASSERT_OBJ(!m_op4p, this, "Adding to non-empty, non-list op4"););
388 UDEBUGONLY(UASSERT_OBJ(!newp->m_backp, newp, "Adding already linked node"););
389 UDEBUGONLY(UASSERT_OBJ(!newp->m_nextp, newp, "Adding list to non-list op4"););
390 debugTreeChange(this, "-setOp4pThs: ", __LINE__, false);
391 debugTreeChange(newp, "-setOp4pNew: ", __LINE__, true);
392 m_op4p = newp;
393 newp->editCountInc();
394 newp->m_backp = this;
395 debugTreeChange(this, "-setOp4pOut: ", __LINE__, false);
396 }
397
addOp1p(AstNode * newp)398 void AstNode::addOp1p(AstNode* newp) {
399 UASSERT(newp, "Null item passed to addOp1p");
400 UDEBUGONLY(UASSERT_OBJ(!newp->m_backp, newp, "Adding already linked node"););
401 if (!m_op1p) {
402 op1p(newp);
403 } else {
404 m_op1p->addNext(newp);
405 }
406 }
407
addOp2p(AstNode * newp)408 void AstNode::addOp2p(AstNode* newp) {
409 UASSERT(newp, "Null item passed to addOp2p");
410 UDEBUGONLY(UASSERT_OBJ(!newp->m_backp, newp, "Adding already linked node"););
411 if (!m_op2p) {
412 op2p(newp);
413 } else {
414 m_op2p->addNext(newp);
415 }
416 }
417
addOp3p(AstNode * newp)418 void AstNode::addOp3p(AstNode* newp) {
419 UASSERT(newp, "Null item passed to addOp3p");
420 UDEBUGONLY(UASSERT_OBJ(!newp->m_backp, newp, "Adding already linked node"););
421 if (!m_op3p) {
422 op3p(newp);
423 } else {
424 m_op3p->addNext(newp);
425 }
426 }
427
addOp4p(AstNode * newp)428 void AstNode::addOp4p(AstNode* newp) {
429 UASSERT(newp, "Null item passed to addOp4p");
430 UDEBUGONLY(UASSERT_OBJ(!newp->m_backp, newp, "Adding already linked node"););
431 if (!m_op4p) {
432 op4p(newp);
433 } else {
434 m_op4p->addNext(newp);
435 }
436 }
437
replaceWith(AstNode * newp)438 void AstNode::replaceWith(AstNode* newp) {
439 // Replace oldp with this
440 // Unlike a unlink/relink, children are changed to point to the new node.
441 AstNRelinker repHandle;
442 this->unlinkFrBack(&repHandle);
443 repHandle.relink(newp);
444 }
445
dump(std::ostream & str) const446 void AstNRelinker::dump(std::ostream& str) const {
447 str << " BK=" << reinterpret_cast<uint32_t*>(m_backp);
448 str << " ITER=" << reinterpret_cast<uint32_t*>(m_iterpp);
449 str << " CHG=" << (m_chg == RELINK_NEXT ? "[NEXT] " : "");
450 str << (m_chg == RELINK_OP1 ? "[OP1] " : "");
451 str << (m_chg == RELINK_OP2 ? "[OP2] " : "");
452 str << (m_chg == RELINK_OP3 ? "[OP3] " : "");
453 str << (m_chg == RELINK_OP4 ? "[OP4] " : "");
454 }
455
unlinkFrBackWithNext(AstNRelinker * linkerp)456 AstNode* AstNode::unlinkFrBackWithNext(AstNRelinker* linkerp) {
457 debugTreeChange(this, "-unlinkWNextThs: ", __LINE__, true);
458 AstNode* const oldp = this;
459 UASSERT(oldp->m_backp, "Node has no back, already unlinked?");
460 oldp->editCountInc();
461 AstNode* const backp = oldp->m_backp;
462 if (linkerp) {
463 linkerp->m_oldp = oldp;
464 linkerp->m_backp = backp;
465 linkerp->m_iterpp = oldp->m_iterpp;
466 if (backp->m_nextp == oldp) {
467 linkerp->m_chg = AstNRelinker::RELINK_NEXT;
468 } else if (backp->m_op1p == oldp) {
469 linkerp->m_chg = AstNRelinker::RELINK_OP1;
470 } else if (backp->m_op2p == oldp) {
471 linkerp->m_chg = AstNRelinker::RELINK_OP2;
472 } else if (backp->m_op3p == oldp) {
473 linkerp->m_chg = AstNRelinker::RELINK_OP3;
474 } else if (backp->m_op4p == oldp) {
475 linkerp->m_chg = AstNRelinker::RELINK_OP4;
476 } else {
477 oldp->v3fatalSrc("Unlink of node with back not pointing to it.");
478 }
479 }
480 if (backp->m_nextp == oldp) {
481 backp->m_nextp = nullptr;
482 // Old list gets truncated
483 // New list becomes a list upon itself
484 // Most common case is unlinking a entire operand tree
485 // (else we'd probably call unlinkFrBack without next)
486 // We may be in the middle of a list; we have no way to find head or tail!
487 AstNode* oldtailp = oldp;
488 while (oldtailp->m_nextp) oldtailp = oldtailp->m_nextp;
489 // Create new head/tail of old list
490 AstNode* const oldheadp = oldtailp->m_headtailp;
491 oldheadp->m_headtailp = oldp->m_backp;
492 oldheadp->m_headtailp->m_headtailp = oldheadp;
493 // Create new head/tail of extracted list
494 oldp->m_headtailp = oldtailp;
495 oldp->m_headtailp->m_headtailp = oldp;
496 } else if (backp->m_op1p == oldp) {
497 backp->m_op1p = nullptr;
498 } else if (backp->m_op2p == oldp) {
499 backp->m_op2p = nullptr;
500 } else if (backp->m_op3p == oldp) {
501 backp->m_op3p = nullptr;
502 } else if (backp->m_op4p == oldp) {
503 backp->m_op4p = nullptr;
504 } else {
505 this->v3fatalSrc("Unlink of node with back not pointing to it.");
506 }
507 // Relink
508 oldp->m_backp = nullptr;
509 // Iterator fixup
510 if (oldp->m_iterpp) *(oldp->m_iterpp) = nullptr;
511 oldp->m_iterpp = nullptr;
512 debugTreeChange(oldp, "-unlinkWNextOut: ", __LINE__, true);
513 return oldp;
514 }
515
unlinkFrBack(AstNRelinker * linkerp)516 AstNode* AstNode::unlinkFrBack(AstNRelinker* linkerp) {
517 debugTreeChange(this, "-unlinkFrBkThs: ", __LINE__, true);
518 AstNode* const oldp = this;
519 UASSERT(oldp->m_backp, "Node has no back, already unlinked?");
520 oldp->editCountInc();
521 AstNode* const backp = oldp->m_backp;
522 if (linkerp) {
523 linkerp->m_oldp = oldp;
524 linkerp->m_backp = backp;
525 linkerp->m_iterpp = oldp->m_iterpp;
526 if (backp->m_nextp == oldp) {
527 linkerp->m_chg = AstNRelinker::RELINK_NEXT;
528 } else if (backp->m_op1p == oldp) {
529 linkerp->m_chg = AstNRelinker::RELINK_OP1;
530 } else if (backp->m_op2p == oldp) {
531 linkerp->m_chg = AstNRelinker::RELINK_OP2;
532 } else if (backp->m_op3p == oldp) {
533 linkerp->m_chg = AstNRelinker::RELINK_OP3;
534 } else if (backp->m_op4p == oldp) {
535 linkerp->m_chg = AstNRelinker::RELINK_OP4;
536 } else {
537 this->v3fatalSrc("Unlink of node with back not pointing to it.");
538 }
539 }
540 if (backp->m_nextp == oldp) {
541 // This node gets removed from middle (or tail) of list
542 // Not head, since then oldp wouldn't be a next of backp...
543 backp->m_nextp = oldp->m_nextp;
544 if (backp->m_nextp) backp->m_nextp->m_backp = backp;
545 // If it was a tail, back becomes new tail
546 if (oldp->m_headtailp) {
547 backp->m_headtailp = oldp->m_headtailp;
548 backp->m_headtailp->m_headtailp = backp;
549 }
550 } else {
551 if (backp->m_op1p == oldp) {
552 backp->m_op1p = oldp->m_nextp;
553 } else if (backp->m_op2p == oldp) {
554 backp->m_op2p = oldp->m_nextp;
555 } else if (backp->m_op3p == oldp) {
556 backp->m_op3p = oldp->m_nextp;
557 } else if (backp->m_op4p == oldp) {
558 backp->m_op4p = oldp->m_nextp;
559 } else {
560 this->v3fatalSrc("Unlink of node with back not pointing to it.");
561 }
562 if (oldp->m_nextp) {
563 AstNode* const newheadp = oldp->m_nextp;
564 newheadp->m_backp = backp;
565 newheadp->m_headtailp = oldp->m_headtailp;
566 newheadp->m_headtailp->m_headtailp = newheadp;
567 }
568 }
569 // Iterator fixup
570 if (oldp->m_iterpp) *(oldp->m_iterpp) = oldp->m_nextp;
571 // Relink
572 oldp->m_nextp = nullptr;
573 oldp->m_backp = nullptr;
574 oldp->m_headtailp = this;
575 oldp->m_iterpp = nullptr;
576 debugTreeChange(oldp, "-unlinkFrBkOut: ", __LINE__, true);
577 return oldp;
578 }
579
relink(AstNRelinker * linkerp)580 void AstNode::relink(AstNRelinker* linkerp) {
581 if (debug() > 8) {
582 UINFO(0, " EDIT: relink: ");
583 dumpPtrs();
584 }
585 AstNode* const newp = this;
586 UASSERT(linkerp && linkerp->m_backp, "Need non-empty linker");
587 UASSERT(!newp->backp(), "New node already linked?");
588 newp->editCountInc();
589
590 if (debug() > 8) {
591 linkerp->dump(cout);
592 cout << endl;
593 }
594
595 AstNode* const backp = linkerp->m_backp;
596 debugTreeChange(this, "-relinkNew: ", __LINE__, true);
597 debugTreeChange(backp, "-relinkTre: ", __LINE__, true);
598
599 switch (linkerp->m_chg) {
600 case AstNRelinker::RELINK_NEXT: backp->addNextHere(newp); break;
601 case AstNRelinker::RELINK_OP1: relinkOneLink(backp->m_op1p /*ref*/, newp); break;
602 case AstNRelinker::RELINK_OP2: relinkOneLink(backp->m_op2p /*ref*/, newp); break;
603 case AstNRelinker::RELINK_OP3: relinkOneLink(backp->m_op3p /*ref*/, newp); break;
604 case AstNRelinker::RELINK_OP4: relinkOneLink(backp->m_op4p /*ref*/, newp); break;
605 default: this->v3fatalSrc("Relink of node without any link to change."); break;
606 }
607 // Relink
608 newp->m_backp = backp;
609 linkerp->m_backp = nullptr;
610 // Iterator fixup
611 if (linkerp->m_iterpp) {
612 // If we're iterating over a next() link, we need to follow links off the
613 // NEW node. Thus we pass iteration information via a pointer in the node.
614 // This adds a unfortunate hot 8 bytes to every AstNode, but is faster than passing
615 // across every function.
616 // If anyone has a cleaner way, I'd be grateful.
617 *(linkerp->m_iterpp) = newp;
618 newp->m_iterpp = linkerp->m_iterpp;
619 }
620 // Empty the linker so not used twice accidentally
621 linkerp->m_backp = nullptr;
622 debugTreeChange(this, "-relinkOut: ", __LINE__, true);
623 }
624
relinkOneLink(AstNode * & pointpr,AstNode * newp)625 void AstNode::relinkOneLink(AstNode*& pointpr, // Ref to pointer that gets set to newp
626 AstNode* newp) {
627 if (pointpr) {
628 // We know there will be at least two elements when we are done,
629 // (newp & the old list).
630 // We *ALLOW* the new node to have its own next list.
631 // Likewise there may be a old list.
632 // Insert the whole old list following the new node's list.
633 // Thus a unlink without next, followed by relink, gives the same list.
634 AstNode* const newlistlastp = newp->m_headtailp;
635 UASSERT_OBJ(!(newlistlastp->m_nextp && newlistlastp != newp), newp,
636 "Headtailp tail isn't at the tail");
637 AstNode* const oldlistlastp = pointpr->m_headtailp;
638 UASSERT_OBJ(!(oldlistlastp->m_nextp && oldlistlastp != pointpr), newp,
639 "Old headtailp tail isn't at the tail");
640 // Next links
641 newlistlastp->m_nextp = pointpr;
642 pointpr->m_backp = newlistlastp;
643 // Head/tail
644 pointpr->m_headtailp = nullptr; // Old head
645 newlistlastp->m_headtailp = nullptr; // Old tail
646 newp->m_headtailp = oldlistlastp; // Head points to tail
647 oldlistlastp->m_headtailp = newp; // Tail points to head
648 }
649 pointpr = newp;
650 }
651
addHereThisAsNext(AstNode * newp)652 void AstNode::addHereThisAsNext(AstNode* newp) {
653 // {old}->this->{next} becomes {old}->new->this->{next}
654 AstNRelinker handle;
655 this->unlinkFrBackWithNext(&handle);
656 newp->addNext(this);
657 handle.relink(newp);
658 }
659
swapWith(AstNode * bp)660 void AstNode::swapWith(AstNode* bp) {
661 AstNRelinker aHandle;
662 AstNRelinker bHandle;
663 this->unlinkFrBack(&aHandle);
664 bp->unlinkFrBack(&bHandle);
665 aHandle.relink(bp);
666 bHandle.relink(this);
667 }
668
669 //======================================================================
670 // Clone
671
cloneTreeIter()672 AstNode* AstNode::cloneTreeIter() {
673 // private: Clone single node and children
674 AstNode* const newp = this->clone();
675 if (this->m_op1p) newp->op1p(this->m_op1p->cloneTreeIterList());
676 if (this->m_op2p) newp->op2p(this->m_op2p->cloneTreeIterList());
677 if (this->m_op3p) newp->op3p(this->m_op3p->cloneTreeIterList());
678 if (this->m_op4p) newp->op4p(this->m_op4p->cloneTreeIterList());
679 newp->m_iterpp = nullptr;
680 newp->clonep(this); // Save pointers to/from both to simplify relinking.
681 this->clonep(newp); // Save pointers to/from both to simplify relinking.
682 return newp;
683 }
684
cloneTreeIterList()685 AstNode* AstNode::cloneTreeIterList() {
686 // private: Clone list of nodes, set m_headtailp
687 AstNode* newheadp = nullptr;
688 AstNode* newtailp = nullptr;
689 // Audited to make sure this is never nullptr
690 for (AstNode* oldp = this; oldp; oldp = oldp->m_nextp) {
691 AstNode* const newp = oldp->cloneTreeIter();
692 newp->m_headtailp = nullptr;
693 newp->m_backp = newtailp;
694 if (newtailp) newtailp->m_nextp = newp;
695 if (!newheadp) newheadp = newp;
696 newtailp = newp;
697 }
698 newheadp->m_headtailp = newtailp;
699 newtailp->m_headtailp = newheadp;
700 return newheadp;
701 }
702
cloneTree(bool cloneNextLink)703 AstNode* AstNode::cloneTree(bool cloneNextLink) {
704 debugTreeChange(this, "-cloneThs: ", __LINE__, cloneNextLink);
705 cloneClearTree();
706 AstNode* newp;
707 if (cloneNextLink && this->m_nextp) {
708 newp = cloneTreeIterList();
709 } else {
710 newp = cloneTreeIter();
711 newp->m_nextp = nullptr;
712 newp->m_headtailp = newp;
713 }
714 newp->m_backp = nullptr;
715 newp->cloneRelinkTree();
716 debugTreeChange(newp, "-cloneOut: ", __LINE__, true);
717 return newp;
718 }
719
720 //======================================================================
721 // Delete
722
deleteNode()723 void AstNode::deleteNode() {
724 // private: Delete single node. Publicly call deleteTree() instead.
725 UASSERT(!m_backp, "Delete called on node with backlink still set");
726 editCountInc();
727 // Change links of old node so we coredump if used
728 this->m_nextp = reinterpret_cast<AstNode*>(0x1);
729 this->m_backp = reinterpret_cast<AstNode*>(0x1);
730 this->m_headtailp = reinterpret_cast<AstNode*>(0x1);
731 this->m_op1p = reinterpret_cast<AstNode*>(0x1);
732 this->m_op2p = reinterpret_cast<AstNode*>(0x1);
733 this->m_op3p = reinterpret_cast<AstNode*>(0x1);
734 this->m_op4p = reinterpret_cast<AstNode*>(0x1);
735 if (
736 #if !defined(VL_DEBUG) || defined(VL_LEAK_CHECKS)
737 true
738 #else
739 !v3Global.opt.debugLeak()
740 #endif
741 ) {
742 delete this;
743 }
744 // Else leak massively, so each pointer is unique
745 // and we can debug easier.
746 }
747
deleteTreeIter()748 void AstNode::deleteTreeIter() {
749 // private: Delete list of nodes. Publicly call deleteTree() instead.
750 // Audited to make sure this is never nullptr
751 for (AstNode *nodep = this, *nnextp; nodep; nodep = nnextp) {
752 nnextp = nodep->m_nextp;
753 // MUST be depth first!
754 if (nodep->m_op1p) nodep->m_op1p->deleteTreeIter();
755 if (nodep->m_op2p) nodep->m_op2p->deleteTreeIter();
756 if (nodep->m_op3p) nodep->m_op3p->deleteTreeIter();
757 if (nodep->m_op4p) nodep->m_op4p->deleteTreeIter();
758 nodep->m_nextp = nullptr;
759 nodep->m_backp = nullptr;
760 nodep->deleteNode();
761 }
762 }
763
deleteTree()764 void AstNode::deleteTree() {
765 // deleteTree always deletes the next link, because you must have called
766 // unlinkFromBack or unlinkFromBackWithNext as appropriate before calling this.
767 UASSERT(!m_backp, "Delete called on node with backlink still set");
768 debugTreeChange(this, "-delTree: ", __LINE__, true);
769 this->editCountInc();
770 // MUST be depth first!
771 deleteTreeIter();
772 }
773
774 //======================================================================
775 // Memory checks
776
777 #ifdef VL_LEAK_CHECKS
operator new(size_t size)778 void* AstNode::operator new(size_t size) {
779 // Optimization note: Aligning to cache line is a loss, due to lost packing
780 const AstNode* const objp = static_cast<AstNode*>(::operator new(size));
781 V3Broken::addNewed(objp);
782 return objp;
783 }
784
operator delete(void * objp,size_t size)785 void AstNode::operator delete(void* objp, size_t size) {
786 if (!objp) return;
787 const AstNode* const nodep = static_cast<AstNode*>(objp);
788 V3Broken::deleted(nodep);
789 ::operator delete(objp);
790 }
791 #endif
792
793 //======================================================================
794 // Iterators
795
iterateChildren(AstNVisitor & v)796 void AstNode::iterateChildren(AstNVisitor& v) {
797 // This is a very hot function
798 // Optimization note: Grabbing m_op#p->m_nextp is a net loss
799 ASTNODE_PREFETCH(m_op1p);
800 ASTNODE_PREFETCH(m_op2p);
801 ASTNODE_PREFETCH(m_op3p);
802 ASTNODE_PREFETCH(m_op4p);
803 if (m_op1p) m_op1p->iterateAndNext(v);
804 if (m_op2p) m_op2p->iterateAndNext(v);
805 if (m_op3p) m_op3p->iterateAndNext(v);
806 if (m_op4p) m_op4p->iterateAndNext(v);
807 }
808
iterateChildrenConst(AstNVisitor & v)809 void AstNode::iterateChildrenConst(AstNVisitor& v) {
810 // This is a very hot function
811 ASTNODE_PREFETCH(m_op1p);
812 ASTNODE_PREFETCH(m_op2p);
813 ASTNODE_PREFETCH(m_op3p);
814 ASTNODE_PREFETCH(m_op4p);
815 if (m_op1p) m_op1p->iterateAndNextConst(v);
816 if (m_op2p) m_op2p->iterateAndNextConst(v);
817 if (m_op3p) m_op3p->iterateAndNextConst(v);
818 if (m_op4p) m_op4p->iterateAndNextConst(v);
819 }
820
iterateAndNext(AstNVisitor & v)821 void AstNode::iterateAndNext(AstNVisitor& v) {
822 // This is a very hot function
823 // IMPORTANT: If you replace a node that's the target of this iterator,
824 // then the NEW node will be iterated on next, it isn't skipped!
825 // Future versions of this function may require the node to have a back to be iterated;
826 // there's no lower level reason yet though the back must exist.
827 AstNode* nodep = this;
828 #ifdef VL_DEBUG // Otherwise too hot of a function for debug
829 UASSERT_OBJ(!(nodep && !nodep->m_backp), nodep, "iterateAndNext node has no back");
830 #endif
831 if (nodep) ASTNODE_PREFETCH(nodep->m_nextp);
832 while (nodep) { // effectively: if (!this) return; // Callers rely on this
833 if (nodep->m_nextp) ASTNODE_PREFETCH(nodep->m_nextp->m_nextp);
834 AstNode* niterp = nodep; // Pointer may get stomped via m_iterpp if the node is edited
835 // Desirable check, but many places where multiple iterations are OK
836 // UASSERT_OBJ(!niterp->m_iterpp, niterp, "IterateAndNext under iterateAndNext may miss
837 // edits"); Optimization note: Doing PREFETCH_RW on m_iterpp is a net even
838 // cppcheck-suppress nullPointer
839 niterp->m_iterpp = &niterp;
840 niterp->accept(v);
841 // accept may do a replaceNode and change niterp on us...
842 // niterp maybe nullptr, so need cast if printing
843 // if (niterp != nodep) UINFO(1,"iterateAndNext edited "<<cvtToHex(nodep)
844 // <<" now into "<<cvtToHex(niterp)<<endl);
845 if (!niterp) return; // Perhaps node deleted inside accept
846 niterp->m_iterpp = nullptr;
847 if (VL_UNLIKELY(niterp != nodep)) { // Edited node inside accept
848 nodep = niterp;
849 } else { // Unchanged node, just continue loop
850 nodep = niterp->m_nextp;
851 }
852 }
853 }
854
iterateListBackwards(AstNVisitor & v)855 void AstNode::iterateListBackwards(AstNVisitor& v) {
856 AstNode* nodep = this;
857 while (nodep->m_nextp) nodep = nodep->m_nextp;
858 while (nodep) {
859 // Edits not supported: nodep->m_iterpp = &nodep;
860 nodep->accept(v);
861 if (nodep->backp()->m_nextp == nodep) {
862 nodep = nodep->backp();
863 } else {
864 nodep = nullptr;
865 } // else: backp points up the tree.
866 }
867 }
868
iterateChildrenBackwards(AstNVisitor & v)869 void AstNode::iterateChildrenBackwards(AstNVisitor& v) {
870 if (m_op1p) m_op1p->iterateListBackwards(v);
871 if (m_op2p) m_op2p->iterateListBackwards(v);
872 if (m_op3p) m_op3p->iterateListBackwards(v);
873 if (m_op4p) m_op4p->iterateListBackwards(v);
874 }
875
iterateAndNextConst(AstNVisitor & v)876 void AstNode::iterateAndNextConst(AstNVisitor& v) {
877 // Keep following the current list even if edits change it
878 AstNode* nodep = this;
879 do {
880 AstNode* const nnextp = nodep->m_nextp;
881 ASTNODE_PREFETCH(nnextp);
882 nodep->accept(v);
883 nodep = nnextp;
884 } while (nodep);
885 }
886
iterateSubtreeReturnEdits(AstNVisitor & v)887 AstNode* AstNode::iterateSubtreeReturnEdits(AstNVisitor& v) {
888 // Some visitors perform tree edits (such as V3Const), and may even
889 // replace/delete the exact nodep that the visitor is called with. If
890 // this happens, the parent will lose the handle to the node that was
891 // processed.
892 // To solve this, this function returns the pointer to the replacement node,
893 // which in many cases is just the same node that was passed in.
894 AstNode* nodep = this; // Note "this" may point to bogus point later in this function
895 if (VN_IS(nodep, Netlist)) {
896 // Calling on top level; we know the netlist won't get replaced
897 nodep->accept(v);
898 } else if (!nodep->backp()) {
899 // Calling on standalone tree; insert a shim node so we can keep
900 // track, then delete it on completion
901 AstBegin* const tempp = new AstBegin(nodep->fileline(), "[EditWrapper]", nodep);
902 {
903 VL_DO_DANGLING(tempp->stmtsp()->accept(v),
904 nodep); // nodep to null as may be replaced
905 }
906 nodep = tempp->stmtsp()->unlinkFrBackWithNext();
907 VL_DO_DANGLING(tempp->deleteTree(), tempp);
908 } else {
909 // Use back to determine who's pointing at us (IE assume new node
910 // grafts into same place as old one)
911 AstNode** nextnodepp = nullptr;
912 if (this->m_backp->m_op1p == this) {
913 nextnodepp = &(this->m_backp->m_op1p);
914 } else if (this->m_backp->m_op2p == this) {
915 nextnodepp = &(this->m_backp->m_op2p);
916 } else if (this->m_backp->m_op3p == this) {
917 nextnodepp = &(this->m_backp->m_op3p);
918 } else if (this->m_backp->m_op4p == this) {
919 nextnodepp = &(this->m_backp->m_op4p);
920 } else if (this->m_backp->m_nextp == this) {
921 nextnodepp = &(this->m_backp->m_nextp);
922 }
923 UASSERT_OBJ(nextnodepp, this, "Node's back doesn't point to forward to node itself");
924 {
925 VL_DO_DANGLING(nodep->accept(v), nodep); // nodep to null as may be replaced
926 }
927 nodep = *nextnodepp; // Grab new node from point where old was connected
928 }
929 return nodep;
930 }
931
932 //======================================================================
933
cloneRelinkTree()934 void AstNode::cloneRelinkTree() {
935 // private: Cleanup clone() operation on whole tree. Publicly call cloneTree() instead.
936 for (AstNode* nodep = this; nodep; nodep = nodep->m_nextp) {
937 if (nodep->m_dtypep && nodep->m_dtypep->clonep()) {
938 nodep->m_dtypep = nodep->m_dtypep->clonep();
939 }
940 nodep->cloneRelink();
941 if (nodep->m_op1p) nodep->m_op1p->cloneRelinkTree();
942 if (nodep->m_op2p) nodep->m_op2p->cloneRelinkTree();
943 if (nodep->m_op3p) nodep->m_op3p->cloneRelinkTree();
944 if (nodep->m_op4p) nodep->m_op4p->cloneRelinkTree();
945 }
946 }
947
948 //======================================================================
949 // Comparison
950
gateTreeIter() const951 bool AstNode::gateTreeIter() const {
952 // private: Return true if the two trees are identical
953 if (!isGateOptimizable()) return false;
954 if (m_op1p && !m_op1p->gateTreeIter()) return false;
955 if (m_op2p && !m_op2p->gateTreeIter()) return false;
956 if (m_op3p && !m_op3p->gateTreeIter()) return false;
957 if (m_op4p && !m_op4p->gateTreeIter()) return false;
958 return true;
959 }
960
sameTreeIter(const AstNode * node1p,const AstNode * node2p,bool ignNext,bool gateOnly)961 bool AstNode::sameTreeIter(const AstNode* node1p, const AstNode* node2p, bool ignNext,
962 bool gateOnly) {
963 // private: Return true if the two trees are identical
964 if (!node1p && !node2p) return true;
965 if (!node1p || !node2p) return false;
966 if (node1p->type() != node2p->type() || node1p->dtypep() != node2p->dtypep()
967 || !node1p->same(node2p) || (gateOnly && !node1p->isGateOptimizable())) {
968 return false;
969 }
970 return (sameTreeIter(node1p->m_op1p, node2p->m_op1p, false, gateOnly)
971 && sameTreeIter(node1p->m_op2p, node2p->m_op2p, false, gateOnly)
972 && sameTreeIter(node1p->m_op3p, node2p->m_op3p, false, gateOnly)
973 && sameTreeIter(node1p->m_op4p, node2p->m_op4p, false, gateOnly)
974 && (ignNext || sameTreeIter(node1p->m_nextp, node2p->m_nextp, false, gateOnly)));
975 }
976
977 //======================================================================
978 // Debugging
979
checkTreeIter(AstNode * backp)980 void AstNode::checkTreeIter(AstNode* backp) {
981 // private: Check a tree and children
982 UASSERT_OBJ(backp == this->backp(), this, "Back node inconsistent");
983 if (VN_IS(this, NodeTermop) || VN_IS(this, NodeVarRef)) {
984 // Termops have a short-circuited iterateChildren, so check usage
985 UASSERT_OBJ(!(op1p() || op2p() || op3p() || op4p()), this,
986 "Terminal operation with non-terminals");
987 }
988 if (m_op1p) m_op1p->checkTreeIterList(this);
989 if (m_op2p) m_op2p->checkTreeIterList(this);
990 if (m_op3p) m_op3p->checkTreeIterList(this);
991 if (m_op4p) m_op4p->checkTreeIterList(this);
992 }
993
checkTreeIterList(AstNode * backp)994 void AstNode::checkTreeIterList(AstNode* backp) {
995 // private: Check a (possible) list of nodes, this is always the head of the list
996 // Audited to make sure this is never nullptr
997 AstNode* const headp = this;
998 const AstNode* tailp = this;
999 for (AstNode* nodep = headp; nodep; nodep = nodep->nextp()) {
1000 nodep->checkTreeIter(backp);
1001 UASSERT_OBJ(headp == this || !nextp(), this,
1002 "Headtailp should be null in middle of lists");
1003 tailp = nodep;
1004 backp = nodep;
1005 }
1006 UASSERT_OBJ(headp->m_headtailp == tailp, headp, "Tail in headtailp is inconsistent");
1007 UASSERT_OBJ(tailp->m_headtailp == headp, tailp, "Head in headtailp is inconsistent");
1008 }
1009
checkTree()1010 void AstNode::checkTree() {
1011 if (!debug()) return;
1012 if (this->backp()) {
1013 // Linked tree- check only the passed node
1014 this->checkTreeIter(this->backp());
1015 } else {
1016 this->checkTreeIterList(this->backp());
1017 }
1018 }
1019
1020 // cppcheck-suppress unusedFunction // Debug only
dumpGdb(const AstNode * nodep)1021 void AstNode::dumpGdb(const AstNode* nodep) { // For GDB only // LCOV_EXCL_LINE
1022 if (!nodep) {
1023 cout << "<nullptr>" << endl;
1024 return;
1025 }
1026 nodep->dumpGdbHeader();
1027 cout << " ";
1028 nodep->dump(cout);
1029 cout << endl;
1030 } // LCOV_EXCL_STOP
1031 // cppcheck-suppress unusedFunction // Debug only
dumpGdbHeader() const1032 void AstNode::dumpGdbHeader() const { // For GDB only // LCOV_EXCL_START
1033 dumpPtrs(cout);
1034 cout << " Fileline = " << fileline() << endl;
1035 } // LCOV_EXCL_STOP
1036 // cppcheck-suppress unusedFunction // Debug only
dumpTreeGdb(const AstNode * nodep)1037 void AstNode::dumpTreeGdb(const AstNode* nodep) { // For GDB only // LCOV_EXCL_START
1038 if (!nodep) {
1039 cout << "<nullptr>" << endl;
1040 return;
1041 }
1042 nodep->dumpGdbHeader();
1043 nodep->dumpTree(cout);
1044 } // LCOV_EXCL_STOP
1045 // cppcheck-suppress unusedFunction // Debug only
dumpTreeFileGdb(const AstNode * nodep,const char * filenamep)1046 void AstNode::dumpTreeFileGdb(const AstNode* nodep, // LCOV_EXCL_START
1047 const char* filenamep) { // For GDB only
1048 if (!nodep) {
1049 cout << "<nullptr>" << endl;
1050 return;
1051 }
1052 const string filename = filenamep ? filenamep : v3Global.debugFilename("debug.tree", 98);
1053 v3Global.rootp()->dumpTreeFile(filename);
1054 } // LCOV_EXCL_STOP
1055
1056 // cppcheck-suppress unusedFunction // Debug only
checkIter() const1057 void AstNode::checkIter() const {
1058 if (m_iterpp) {
1059 dumpPtrs(cout);
1060 // Perhaps something forgot to clear m_iterpp?
1061 this->v3fatalSrc("Iteration link should be nullptr");
1062 }
1063 }
1064
dumpPtrs(std::ostream & os) const1065 void AstNode::dumpPtrs(std::ostream& os) const {
1066 os << "This=" << typeName() << " " << cvtToHex(this);
1067 os << " back=" << cvtToHex(backp());
1068 if (nextp()) os << " next=" << cvtToHex(nextp());
1069 if (m_headtailp == this) {
1070 os << " headtail=this";
1071 } else {
1072 os << " headtail=" << cvtToHex(m_headtailp);
1073 }
1074 if (op1p()) os << " op1p=" << cvtToHex(op1p());
1075 if (op2p()) os << " op2p=" << cvtToHex(op2p());
1076 if (op3p()) os << " op3p=" << cvtToHex(op3p());
1077 if (op4p()) os << " op4p=" << cvtToHex(op4p());
1078 if (user1p()) os << " user1p=" << cvtToHex(user1p());
1079 if (user2p()) os << " user2p=" << cvtToHex(user2p());
1080 if (user3p()) os << " user3p=" << cvtToHex(user3p());
1081 if (user4p()) os << " user4p=" << cvtToHex(user4p());
1082 if (user5p()) os << " user5p=" << cvtToHex(user5p());
1083 if (m_iterpp) {
1084 os << " iterpp=" << cvtToHex(m_iterpp);
1085 os << "*=" << cvtToHex(*m_iterpp);
1086 }
1087 os << endl;
1088 }
1089
dumpTree(std::ostream & os,const string & indent,int maxDepth) const1090 void AstNode::dumpTree(std::ostream& os, const string& indent, int maxDepth) const {
1091 static int s_debugFileline = v3Global.opt.debugSrcLevel("fileline"); // --debugi-fileline 9
1092 os << indent << " " << this << '\n';
1093 if (debug() > 8) {
1094 os << indent << " ";
1095 dumpPtrs(os);
1096 }
1097 if (s_debugFileline >= 9) os << fileline()->warnContextSecondary();
1098 if (maxDepth == 1) {
1099 if (op1p() || op2p() || op3p() || op4p()) os << indent << "1: ...(maxDepth)\n";
1100 } else {
1101 for (const AstNode* nodep = op1p(); nodep; nodep = nodep->nextp()) {
1102 nodep->dumpTree(os, indent + "1:", maxDepth - 1);
1103 }
1104 for (const AstNode* nodep = op2p(); nodep; nodep = nodep->nextp()) {
1105 nodep->dumpTree(os, indent + "2:", maxDepth - 1);
1106 }
1107 for (const AstNode* nodep = op3p(); nodep; nodep = nodep->nextp()) {
1108 nodep->dumpTree(os, indent + "3:", maxDepth - 1);
1109 }
1110 for (const AstNode* nodep = op4p(); nodep; nodep = nodep->nextp()) {
1111 nodep->dumpTree(os, indent + "4:", maxDepth - 1);
1112 }
1113 }
1114 }
1115
dumpTreeAndNext(std::ostream & os,const string & indent,int maxDepth) const1116 void AstNode::dumpTreeAndNext(std::ostream& os, const string& indent, int maxDepth) const {
1117 // Audited to make sure this is never nullptr
1118 for (const AstNode* nodep = this; nodep; nodep = nodep->nextp()) {
1119 nodep->dumpTree(os, indent, maxDepth);
1120 }
1121 }
1122
dumpTreeFile(const string & filename,bool append,bool doDump,bool doCheck)1123 void AstNode::dumpTreeFile(const string& filename, bool append, bool doDump, bool doCheck) {
1124 // Not const function as calls checkTree
1125 if (doDump) {
1126 { // Write log & close
1127 UINFO(2, "Dumping " << filename << endl);
1128 const std::unique_ptr<std::ofstream> logsp{V3File::new_ofstream(filename, append)};
1129 if (logsp->fail()) v3fatal("Can't write " << filename);
1130 *logsp << "Verilator Tree Dump (format 0x3900) from <e" << std::dec << editCountLast();
1131 *logsp << "> to <e" << std::dec << editCountGbl() << ">\n";
1132 if (editCountGbl() == editCountLast() && !(v3Global.opt.dumpTree() >= 9)) {
1133 *logsp << '\n';
1134 *logsp << "No changes since last dump!\n";
1135 } else {
1136 dumpTree(*logsp);
1137 editCountSetLast(); // Next dump can indicate start from here
1138 }
1139 }
1140 }
1141 if (doCheck && (v3Global.opt.debugCheck() || v3Global.opt.dumpTree())) {
1142 // Error check
1143 checkTree();
1144 // Broken isn't part of check tree because it can munge iterp's
1145 // set by other steps if it is called in the middle of other operations
1146 if (AstNetlist* const netp = VN_CAST(this, Netlist)) V3Broken::brokenAll(netp);
1147 }
1148 }
1149
v3errorEndFatal(std::ostringstream & str) const1150 void AstNode::v3errorEndFatal(std::ostringstream& str) const {
1151 v3errorEnd(str);
1152 assert(0); // LCOV_EXCL_LINE
1153 VL_UNREACHABLE
1154 }
1155
locationStr() const1156 string AstNode::locationStr() const {
1157 string str = "... In instance ";
1158 const AstNode* backp = this;
1159 int itmax = 10000; // Max iterations before giving up on location search
1160 while (backp) {
1161 if (VL_UNCOVERABLE(--itmax < 0)) {
1162 // Likely some circular back link, and V3Ast is trying to report a low-level error
1163 UINFO(1, "Ran out of iterations finding locationStr on " << backp << endl);
1164 return ""; // LCOV_EXCL_LINE
1165 }
1166 const AstScope* scopep;
1167 if ((scopep = VN_CAST(backp, Scope))) {
1168 // The design is flattened and there are no useful scopes
1169 // This is probably because of inlining
1170 if (scopep->isTop()) break;
1171
1172 str += scopep->prettyName();
1173 return str;
1174 }
1175 backp = backp->backp();
1176 }
1177 backp = this;
1178 while (backp) {
1179 const AstModule* modp;
1180 const AstNodeVarRef* nvrp;
1181 if ((modp = VN_CAST(backp, Module)) && !modp->hierName().empty()) {
1182 str += modp->hierName();
1183 return str;
1184 } else if ((nvrp = VN_CAST(backp, NodeVarRef))) {
1185 const string prettyName = nvrp->prettyName();
1186 // VarRefs have not been flattened yet and do not contain location information
1187 if (prettyName != nvrp->name()) {
1188 str += prettyName;
1189 return str;
1190 }
1191 }
1192 backp = backp->backp();
1193 }
1194 return "";
1195 }
v3errorEnd(std::ostringstream & str) const1196 void AstNode::v3errorEnd(std::ostringstream& str) const {
1197 if (!m_fileline) {
1198 V3Error::v3errorEnd(str, locationStr());
1199 } else {
1200 std::ostringstream nsstr;
1201 nsstr << str.str();
1202 if (debug()) {
1203 nsstr << '\n';
1204 nsstr << "-node: ";
1205 const_cast<AstNode*>(this)->dump(nsstr);
1206 nsstr << endl;
1207 }
1208 m_fileline->v3errorEnd(nsstr, locationStr());
1209 }
1210 }
1211
1212 //======================================================================
1213 // Data type conversion
1214
dtypeChgSigned(bool flag)1215 void AstNode::dtypeChgSigned(bool flag) {
1216 UASSERT_OBJ(dtypep(), this, "No dtype when changing to (un)signed");
1217 dtypeChgWidthSigned(dtypep()->width(), dtypep()->widthMin(), VSigning::fromBool(flag));
1218 }
dtypeChgWidth(int width,int widthMin)1219 void AstNode::dtypeChgWidth(int width, int widthMin) {
1220 UASSERT_OBJ(dtypep(), this,
1221 "No dtype when changing width"); // Use ChgWidthSigned(...UNSIGNED) otherwise
1222 dtypeChgWidthSigned(width, widthMin, dtypep()->numeric());
1223 }
1224
dtypeChgWidthSigned(int width,int widthMin,VSigning numeric)1225 void AstNode::dtypeChgWidthSigned(int width, int widthMin, VSigning numeric) {
1226 if (!dtypep()) {
1227 // We allow dtypep() to be null, as before/during widthing dtypes are not resolved
1228 dtypeSetLogicUnsized(width, widthMin, numeric);
1229 } else {
1230 if (width == dtypep()->width() && widthMin == dtypep()->widthMin()
1231 && numeric == dtypep()->numeric())
1232 return; // Correct already
1233 // FUTURE: We may be pointing at a two state data type, and this may
1234 // convert it to logic. Since the AstVar remains correct, we
1235 // work OK but this assumption may break in the future.
1236 // Note we can't just clone and do a widthForce, as if it's a BasicDType
1237 // the msb() indications etc will be incorrect.
1238 dtypeSetLogicUnsized(width, widthMin, numeric);
1239 }
1240 }
1241
findBasicDType(AstBasicDTypeKwd kwd) const1242 AstNodeDType* AstNode::findBasicDType(AstBasicDTypeKwd kwd) const {
1243 // For 'simple' types we use the global directory. These are all unsized.
1244 // More advanced types land under the module/task/etc
1245 return v3Global.rootp()->typeTablep()->findBasicDType(fileline(), kwd);
1246 }
findBitDType(int width,int widthMin,VSigning numeric) const1247 AstNodeDType* AstNode::findBitDType(int width, int widthMin, VSigning numeric) const {
1248 return v3Global.rootp()->typeTablep()->findLogicBitDType(fileline(), AstBasicDTypeKwd::BIT,
1249 width, widthMin, numeric);
1250 }
findLogicDType(int width,int widthMin,VSigning numeric) const1251 AstNodeDType* AstNode::findLogicDType(int width, int widthMin, VSigning numeric) const {
1252 return v3Global.rootp()->typeTablep()->findLogicBitDType(fileline(), AstBasicDTypeKwd::LOGIC,
1253 width, widthMin, numeric);
1254 }
findLogicRangeDType(const VNumRange & range,int widthMin,VSigning numeric) const1255 AstNodeDType* AstNode::findLogicRangeDType(const VNumRange& range, int widthMin,
1256 VSigning numeric) const {
1257 return v3Global.rootp()->typeTablep()->findLogicBitDType(fileline(), AstBasicDTypeKwd::LOGIC,
1258 range, widthMin, numeric);
1259 }
findBitRangeDType(const VNumRange & range,int widthMin,VSigning numeric) const1260 AstNodeDType* AstNode::findBitRangeDType(const VNumRange& range, int widthMin,
1261 VSigning numeric) const {
1262 return v3Global.rootp()->typeTablep()->findLogicBitDType(fileline(), AstBasicDTypeKwd::BIT,
1263 range, widthMin, numeric);
1264 }
findInsertSameDType(AstBasicDType * nodep)1265 AstBasicDType* AstNode::findInsertSameDType(AstBasicDType* nodep) {
1266 return v3Global.rootp()->typeTablep()->findInsertSameDType(nodep);
1267 }
findEmptyQueueDType() const1268 AstNodeDType* AstNode::findEmptyQueueDType() const {
1269 return v3Global.rootp()->typeTablep()->findEmptyQueueDType(fileline());
1270 }
findQueueIndexDType() const1271 AstNodeDType* AstNode::findQueueIndexDType() const {
1272 return v3Global.rootp()->typeTablep()->findQueueIndexDType(fileline());
1273 }
findVoidDType() const1274 AstNodeDType* AstNode::findVoidDType() const {
1275 return v3Global.rootp()->typeTablep()->findVoidDType(fileline());
1276 }
1277
1278 //######################################################################
1279 // AstNDeleter
1280
doDeletes()1281 void AstNDeleter::doDeletes() {
1282 for (AstNode* const nodep : m_deleteps) nodep->deleteTree();
1283 m_deleteps.clear();
1284 }
1285